mark_sweep.h revision 6f365cc033654a5a3b45eaa1379d4b5f156b0cee
1/* 2 * Copyright (C) 2011 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17#ifndef ART_RUNTIME_GC_COLLECTOR_MARK_SWEEP_H_ 18#define ART_RUNTIME_GC_COLLECTOR_MARK_SWEEP_H_ 19 20#include "atomic.h" 21#include "barrier.h" 22#include "base/macros.h" 23#include "base/mutex.h" 24#include "garbage_collector.h" 25#include "gc/accounting/space_bitmap.h" 26#include "immune_region.h" 27#include "object_callbacks.h" 28#include "offsets.h" 29#include "UniquePtr.h" 30 31namespace art { 32 33namespace mirror { 34 class Class; 35 class Object; 36 class Reference; 37} // namespace mirror 38 39class Thread; 40enum VisitRootFlags : uint8_t; 41 42namespace gc { 43 44class Heap; 45 46namespace accounting { 47 template<typename T> class AtomicStack; 48 typedef AtomicStack<mirror::Object*> ObjectStack; 49} // namespace accounting 50 51namespace collector { 52 53class MarkSweep : public GarbageCollector { 54 public: 55 explicit MarkSweep(Heap* heap, bool is_concurrent, const std::string& name_prefix = ""); 56 57 ~MarkSweep() {} 58 59 virtual void RunPhases() OVERRIDE NO_THREAD_SAFETY_ANALYSIS; 60 void InitializePhase(); 61 void MarkingPhase() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 62 void PausePhase() EXCLUSIVE_LOCKS_REQUIRED(Locks::mutator_lock_); 63 void ReclaimPhase() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 64 void FinishPhase() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 65 virtual void MarkReachableObjects() 66 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) 67 EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_); 68 69 bool IsConcurrent() const { 70 return is_concurrent_; 71 } 72 73 virtual GcType GetGcType() const OVERRIDE { 74 return kGcTypeFull; 75 } 76 77 virtual CollectorType GetCollectorType() const OVERRIDE { 78 return is_concurrent_ ? kCollectorTypeCMS : kCollectorTypeMS; 79 } 80 81 // Initializes internal structures. 82 void Init(); 83 84 // Find the default mark bitmap. 85 void FindDefaultSpaceBitmap(); 86 87 // Marks all objects in the root set at the start of a garbage collection. 88 void MarkRoots(Thread* self) 89 EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_) 90 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 91 92 void MarkNonThreadRoots() 93 EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_) 94 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 95 96 void MarkConcurrentRoots(VisitRootFlags flags) 97 EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_) 98 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 99 100 void MarkRootsCheckpoint(Thread* self, bool revoke_ros_alloc_thread_local_buffers_at_checkpoint) 101 EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_) 102 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 103 104 // Builds a mark stack and recursively mark until it empties. 105 void RecursiveMark() 106 EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_) 107 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 108 109 // Bind the live bits to the mark bits of bitmaps for spaces that are never collected, ie 110 // the image. Mark that portion of the heap as immune. 111 virtual void BindBitmaps() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 112 113 // Builds a mark stack with objects on dirty cards and recursively mark until it empties. 114 void RecursiveMarkDirtyObjects(bool paused, byte minimum_age) 115 EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_) 116 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 117 118 // Remarks the root set after completing the concurrent mark. 119 void ReMarkRoots() 120 EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_) 121 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 122 123 void ProcessReferences(Thread* self) 124 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 125 126 void PreProcessReferences() 127 EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_) 128 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 129 130 // Update and mark references from immune spaces. 131 void UpdateAndMarkModUnion() 132 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 133 134 // Pre clean cards to reduce how much work is needed in the pause. 135 void PreCleanCards() 136 EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_) 137 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 138 139 // Sweeps unmarked objects to complete the garbage collection. Virtual as by default it sweeps 140 // all allocation spaces. Partial and sticky GCs want to just sweep a subset of the heap. 141 virtual void Sweep(bool swap_bitmaps) EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_); 142 143 // Sweeps unmarked objects to complete the garbage collection. 144 void SweepLargeObjects(bool swap_bitmaps) EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_); 145 146 // Sweep only pointers within an array. WARNING: Trashes objects. 147 void SweepArray(accounting::ObjectStack* allocation_stack_, bool swap_bitmaps) 148 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) 149 EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_); 150 151 // Blackens an object. 152 void ScanObject(mirror::Object* obj) 153 EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_) 154 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 155 156 // No thread safety analysis due to lambdas. 157 template<typename MarkVisitor, typename ReferenceVisitor> 158 void ScanObjectVisit(mirror::Object* obj, const MarkVisitor& visitor, 159 const ReferenceVisitor& ref_visitor) 160 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) 161 EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_); 162 163 void SweepSystemWeaks(Thread* self) 164 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) LOCKS_EXCLUDED(Locks::heap_bitmap_lock_); 165 166 static mirror::Object* VerifySystemWeakIsLiveCallback(mirror::Object* obj, void* arg) 167 SHARED_LOCKS_REQUIRED(Locks::heap_bitmap_lock_); 168 169 void VerifySystemWeaks() 170 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_, Locks::heap_bitmap_lock_); 171 172 // Verify that an object is live, either in a live bitmap or in the allocation stack. 173 void VerifyIsLive(const mirror::Object* obj) 174 SHARED_LOCKS_REQUIRED(Locks::heap_bitmap_lock_); 175 176 static mirror::Object* MarkObjectCallback(mirror::Object* obj, void* arg) 177 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) 178 EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_); 179 180 static void MarkHeapReferenceCallback(mirror::HeapReference<mirror::Object>* ref, void* arg) 181 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) 182 EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_); 183 184 static void MarkRootCallback(mirror::Object** root, void* arg, uint32_t thread_id, 185 RootType root_type) 186 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) 187 EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_); 188 189 static void VerifyRootMarked(mirror::Object** root, void* arg, uint32_t /*thread_id*/, 190 RootType /*root_type*/) 191 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) 192 EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_); 193 194 static void ProcessMarkStackPausedCallback(void* arg) 195 EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_, Locks::mutator_lock_); 196 197 static void MarkRootParallelCallback(mirror::Object** root, void* arg, uint32_t thread_id, 198 RootType root_type) 199 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 200 201 // Marks an object. 202 void MarkObject(mirror::Object* obj) 203 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) 204 EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_); 205 206 Barrier& GetBarrier() { 207 return *gc_barrier_; 208 } 209 210 // Schedules an unmarked object for reference processing. 211 void DelayReferenceReferent(mirror::Class* klass, mirror::Reference* reference) 212 SHARED_LOCKS_REQUIRED(Locks::heap_bitmap_lock_, Locks::mutator_lock_); 213 214 protected: 215 // Returns true if the object has its bit set in the mark bitmap. 216 bool IsMarked(const mirror::Object* object) const; 217 218 static mirror::Object* IsMarkedCallback(mirror::Object* object, void* arg) 219 SHARED_LOCKS_REQUIRED(Locks::heap_bitmap_lock_); 220 221 static void VerifyImageRootVisitor(mirror::Object* root, void* arg) 222 SHARED_LOCKS_REQUIRED(Locks::heap_bitmap_lock_, Locks::mutator_lock_); 223 224 void MarkObjectNonNull(mirror::Object* obj) 225 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) 226 EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_); 227 228 // Marks an object atomically, safe to use from multiple threads. 229 void MarkObjectNonNullParallel(mirror::Object* obj); 230 231 // Returns true if we need to add obj to a mark stack. 232 bool MarkObjectParallel(const mirror::Object* obj) NO_THREAD_SAFETY_ANALYSIS; 233 234 // Verify the roots of the heap and print out information related to any invalid roots. 235 // Called in MarkObject, so may we may not hold the mutator lock. 236 void VerifyRoots() 237 NO_THREAD_SAFETY_ANALYSIS; 238 239 // Expand mark stack to 2x its current size. 240 void ExpandMarkStack() EXCLUSIVE_LOCKS_REQUIRED(mark_stack_lock_); 241 void ResizeMarkStack(size_t new_size) EXCLUSIVE_LOCKS_REQUIRED(mark_stack_lock_); 242 243 // Returns how many threads we should use for the current GC phase based on if we are paused, 244 // whether or not we care about pauses. 245 size_t GetThreadCount(bool paused) const; 246 247 static void VerifyRootCallback(const mirror::Object* root, void* arg, size_t vreg, 248 const StackVisitor *visitor, RootType root_type); 249 250 void VerifyRoot(const mirror::Object* root, size_t vreg, const StackVisitor* visitor, 251 RootType root_type) NO_THREAD_SAFETY_ANALYSIS; 252 253 // Push a single reference on a mark stack. 254 void PushOnMarkStack(mirror::Object* obj); 255 256 // Blackens objects grayed during a garbage collection. 257 void ScanGrayObjects(bool paused, byte minimum_age) 258 EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_) 259 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 260 261 // Recursively blackens objects on the mark stack. 262 void ProcessMarkStack(bool paused) 263 EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_) 264 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 265 266 void ProcessMarkStackParallel(size_t thread_count) 267 EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_) 268 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 269 270 // Used to get around thread safety annotations. The call is from MarkingPhase and is guarded by 271 // IsExclusiveHeld. 272 void RevokeAllThreadLocalAllocationStacks(Thread* self) NO_THREAD_SAFETY_ANALYSIS; 273 274 // Revoke all the thread-local buffers. 275 void RevokeAllThreadLocalBuffers(); 276 277 // Whether or not we count how many of each type of object were scanned. 278 static const bool kCountScannedTypes = false; 279 280 // Current space, we check this space first to avoid searching for the appropriate space for an 281 // object. 282 accounting::ContinuousSpaceBitmap* current_space_bitmap_; 283 // Cache the heap's mark bitmap to prevent having to do 2 loads during slow path marking. 284 accounting::HeapBitmap* mark_bitmap_; 285 286 accounting::ObjectStack* mark_stack_; 287 288 // Immune region, every object inside the immune range is assumed to be marked. 289 ImmuneRegion immune_region_; 290 291 // Parallel finger. 292 AtomicInteger atomic_finger_; 293 // Number of classes scanned, if kCountScannedTypes. 294 AtomicInteger class_count_; 295 // Number of arrays scanned, if kCountScannedTypes. 296 AtomicInteger array_count_; 297 // Number of non-class/arrays scanned, if kCountScannedTypes. 298 AtomicInteger other_count_; 299 AtomicInteger large_object_test_; 300 AtomicInteger large_object_mark_; 301 AtomicInteger overhead_time_; 302 AtomicInteger work_chunks_created_; 303 AtomicInteger work_chunks_deleted_; 304 AtomicInteger reference_count_; 305 AtomicInteger mark_null_count_; 306 AtomicInteger mark_immune_count_; 307 AtomicInteger mark_fastpath_count_; 308 AtomicInteger mark_slowpath_count_; 309 310 // Verification. 311 size_t live_stack_freeze_size_; 312 313 UniquePtr<Barrier> gc_barrier_; 314 Mutex mark_stack_lock_ ACQUIRED_AFTER(Locks::classlinker_classes_lock_); 315 316 const bool is_concurrent_; 317 318 private: 319 friend class AddIfReachesAllocSpaceVisitor; // Used by mod-union table. 320 friend class CardScanTask; 321 friend class CheckBitmapVisitor; 322 friend class CheckReferenceVisitor; 323 friend class art::gc::Heap; 324 friend class MarkObjectVisitor; 325 friend class ModUnionCheckReferences; 326 friend class ModUnionClearCardVisitor; 327 friend class ModUnionReferenceVisitor; 328 friend class ModUnionVisitor; 329 friend class ModUnionTableBitmap; 330 friend class ModUnionTableReferenceCache; 331 friend class ModUnionScanImageRootVisitor; 332 template<bool kUseFinger> friend class MarkStackTask; 333 friend class FifoMarkStackChunk; 334 friend class MarkSweepMarkObjectSlowPath; 335 336 DISALLOW_COPY_AND_ASSIGN(MarkSweep); 337}; 338 339} // namespace collector 340} // namespace gc 341} // namespace art 342 343#endif // ART_RUNTIME_GC_COLLECTOR_MARK_SWEEP_H_ 344