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