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 <memory> 21 22 #include "atomic.h" 23 #include "barrier.h" 24 #include "base/macros.h" 25 #include "base/mutex.h" 26 #include "garbage_collector.h" 27 #include "gc_root.h" 28 #include "gc/accounting/heap_bitmap.h" 29 #include "immune_region.h" 30 #include "object_callbacks.h" 31 #include "offsets.h" 32 33 namespace art { 34 35 namespace mirror { 36 class Class; 37 class Object; 38 class Reference; 39 } // namespace mirror 40 41 class Thread; 42 enum VisitRootFlags : uint8_t; 43 44 namespace gc { 45 46 class Heap; 47 48 namespace accounting { 49 template<typename T> class AtomicStack; 50 typedef AtomicStack<mirror::Object> ObjectStack; 51 } // namespace accounting 52 53 namespace collector { 54 55 class MarkSweep : public GarbageCollector { 56 public: 57 explicit MarkSweep(Heap* heap, bool is_concurrent, const std::string& name_prefix = ""); 58 ~MarkSweep()59 ~MarkSweep() {} 60 61 virtual void RunPhases() OVERRIDE NO_THREAD_SAFETY_ANALYSIS; 62 void InitializePhase(); 63 void MarkingPhase() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 64 void PausePhase() EXCLUSIVE_LOCKS_REQUIRED(Locks::mutator_lock_); 65 void ReclaimPhase() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 66 void FinishPhase() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 67 virtual void MarkReachableObjects() 68 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) 69 EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_); 70 IsConcurrent()71 bool IsConcurrent() const { 72 return is_concurrent_; 73 } 74 GetGcType()75 virtual GcType GetGcType() const OVERRIDE { 76 return kGcTypeFull; 77 } 78 GetCollectorType()79 virtual CollectorType GetCollectorType() const OVERRIDE { 80 return is_concurrent_ ? kCollectorTypeCMS : kCollectorTypeMS; 81 } 82 83 // Initializes internal structures. 84 void Init(); 85 86 // Find the default mark bitmap. 87 void FindDefaultSpaceBitmap(); 88 89 // Marks all objects in the root set at the start of a garbage collection. 90 void MarkRoots(Thread* self) 91 EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_) 92 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 93 94 void MarkNonThreadRoots() 95 EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_) 96 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 97 98 void MarkConcurrentRoots(VisitRootFlags flags) 99 EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_) 100 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 101 102 void MarkRootsCheckpoint(Thread* self, bool revoke_ros_alloc_thread_local_buffers_at_checkpoint) 103 EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_) 104 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 105 106 // Builds a mark stack and recursively mark until it empties. 107 void RecursiveMark() 108 EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_) 109 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 110 111 // Bind the live bits to the mark bits of bitmaps for spaces that are never collected, ie 112 // the image. Mark that portion of the heap as immune. 113 virtual void BindBitmaps() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 114 115 // Builds a mark stack with objects on dirty cards and recursively mark until it empties. 116 void RecursiveMarkDirtyObjects(bool paused, uint8_t minimum_age) 117 EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_) 118 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 119 120 // Remarks the root set after completing the concurrent mark. 121 void ReMarkRoots() 122 EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_) 123 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 124 125 void ProcessReferences(Thread* self) 126 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 127 128 // Update and mark references from immune spaces. 129 void UpdateAndMarkModUnion() 130 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 131 132 // Pre clean cards to reduce how much work is needed in the pause. 133 void PreCleanCards() 134 EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_) 135 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 136 137 // Sweeps unmarked objects to complete the garbage collection. Virtual as by default it sweeps 138 // all allocation spaces. Partial and sticky GCs want to just sweep a subset of the heap. 139 virtual void Sweep(bool swap_bitmaps) EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_) 140 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 141 142 // Sweeps unmarked objects to complete the garbage collection. 143 void SweepLargeObjects(bool swap_bitmaps) EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_); 144 145 // Sweep only pointers within an array. WARNING: Trashes objects. 146 void SweepArray(accounting::ObjectStack* allocation_stack_, bool swap_bitmaps) 147 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) 148 EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_); 149 150 // Blackens an object. 151 void ScanObject(mirror::Object* obj) 152 EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_) 153 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 154 155 // No thread safety analysis due to lambdas. 156 template<typename MarkVisitor, typename ReferenceVisitor> 157 void ScanObjectVisit(mirror::Object* obj, const MarkVisitor& visitor, 158 const ReferenceVisitor& ref_visitor) 159 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) 160 EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_); 161 162 void SweepSystemWeaks(Thread* self) 163 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) LOCKS_EXCLUDED(Locks::heap_bitmap_lock_); 164 165 static mirror::Object* VerifySystemWeakIsLiveCallback(mirror::Object* obj, void* arg) 166 SHARED_LOCKS_REQUIRED(Locks::heap_bitmap_lock_, Locks::mutator_lock_); 167 168 void VerifySystemWeaks() 169 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_, Locks::heap_bitmap_lock_); 170 171 // Verify that an object is live, either in a live bitmap or in the allocation stack. 172 void VerifyIsLive(const mirror::Object* obj) 173 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) 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 bool HeapReferenceMarkedCallback(mirror::HeapReference<mirror::Object>* ref, void* arg) 185 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) 186 EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_); 187 188 virtual void VisitRoots(mirror::Object*** roots, size_t count, const RootInfo& info) OVERRIDE 189 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) 190 EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_); 191 192 virtual void VisitRoots(mirror::CompressedReference<mirror::Object>** roots, size_t count, 193 const RootInfo& info) OVERRIDE 194 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) 195 EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_); 196 197 static void ProcessMarkStackCallback(void* arg) 198 EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_) 199 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 200 201 // Marks an object. 202 void MarkObject(mirror::Object* obj, mirror::Object* holder = nullptr, 203 MemberOffset offset = MemberOffset(0)) 204 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) 205 EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_); 206 GetBarrier()207 Barrier& GetBarrier() { 208 return *gc_barrier_; 209 } 210 211 // Schedules an unmarked object for reference processing. 212 void DelayReferenceReferent(mirror::Class* klass, mirror::Reference* reference) 213 SHARED_LOCKS_REQUIRED(Locks::heap_bitmap_lock_, Locks::mutator_lock_); 214 215 protected: 216 // Returns true if the object has its bit set in the mark bitmap. 217 bool IsMarked(const mirror::Object* object) const 218 SHARED_LOCKS_REQUIRED(Locks::heap_bitmap_lock_); 219 220 static mirror::Object* IsMarkedCallback(mirror::Object* object, void* arg) 221 SHARED_LOCKS_REQUIRED(Locks::heap_bitmap_lock_); 222 223 static void VerifyImageRootVisitor(mirror::Object* root, void* arg) 224 SHARED_LOCKS_REQUIRED(Locks::heap_bitmap_lock_, Locks::mutator_lock_); 225 226 void MarkObjectNonNull(mirror::Object* obj, mirror::Object* holder = nullptr, 227 MemberOffset offset = MemberOffset(0)) 228 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) 229 EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_); 230 231 // Marks an object atomically, safe to use from multiple threads. 232 void MarkObjectNonNullParallel(mirror::Object* obj) 233 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 234 235 // Returns true if we need to add obj to a mark stack. 236 bool MarkObjectParallel(const mirror::Object* obj) NO_THREAD_SAFETY_ANALYSIS; 237 238 // Verify the roots of the heap and print out information related to any invalid roots. 239 // Called in MarkObject, so may we may not hold the mutator lock. 240 void VerifyRoots() 241 NO_THREAD_SAFETY_ANALYSIS; 242 243 // Expand mark stack to 2x its current size. 244 void ExpandMarkStack() EXCLUSIVE_LOCKS_REQUIRED(mark_stack_lock_) 245 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 246 void ResizeMarkStack(size_t new_size) EXCLUSIVE_LOCKS_REQUIRED(mark_stack_lock_) 247 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 248 249 // Returns how many threads we should use for the current GC phase based on if we are paused, 250 // whether or not we care about pauses. 251 size_t GetThreadCount(bool paused) const; 252 253 // Push a single reference on a mark stack. 254 void PushOnMarkStack(mirror::Object* obj) SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); 255 256 // Blackens objects grayed during a garbage collection. 257 void ScanGrayObjects(bool paused, uint8_t 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 std::unique_ptr<Barrier> gc_barrier_; 311 Mutex mark_stack_lock_ ACQUIRED_AFTER(Locks::classlinker_classes_lock_); 312 313 const bool is_concurrent_; 314 315 // Verification. 316 size_t live_stack_freeze_size_; 317 318 std::unique_ptr<MemMap> sweep_array_free_buffer_mem_map_; 319 320 private: 321 friend class AddIfReachesAllocSpaceVisitor; // Used by mod-union table. 322 friend class CardScanTask; 323 friend class CheckBitmapVisitor; 324 friend class CheckReferenceVisitor; 325 friend class CheckpointMarkThreadRoots; 326 friend class art::gc::Heap; 327 friend class FifoMarkStackChunk; 328 friend class MarkObjectVisitor; 329 template<bool kUseFinger> friend class MarkStackTask; 330 friend class MarkSweepMarkObjectSlowPath; 331 friend class ModUnionCheckReferences; 332 friend class ModUnionClearCardVisitor; 333 friend class ModUnionReferenceVisitor; 334 friend class ModUnionScanImageRootVisitor; 335 friend class ModUnionTableBitmap; 336 friend class ModUnionTableReferenceCache; 337 friend class ModUnionVisitor; 338 friend class VerifyRootMarkedVisitor; 339 friend class VerifyRootVisitor; 340 341 DISALLOW_IMPLICIT_CONSTRUCTORS(MarkSweep); 342 }; 343 344 } // namespace collector 345 } // namespace gc 346 } // namespace art 347 348 #endif // ART_RUNTIME_GC_COLLECTOR_MARK_SWEEP_H_ 349