mark_compact.h revision e63db27db913f1a88e2095a1ee8239b2bb9124e8 
1/*
2 * Copyright (C) 2014 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_COMPACT_H_
18#define ART_RUNTIME_GC_COLLECTOR_MARK_COMPACT_H_
19
20#include <deque>
21#include <memory>  // For unique_ptr.
22
23#include "atomic.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 "lock_word.h"
30#include "object_callbacks.h"
31#include "offsets.h"
32
33namespace art {
34
35class Thread;
36
37namespace mirror {
38  class Class;
39  class Object;
40}  // namespace mirror
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 space {
52  class BumpPointerSpace;
53  class ContinuousMemMapAllocSpace;
54  class ContinuousSpace;
55}  // namespace space
56
57namespace collector {
58
59class MarkCompact : public GarbageCollector {
60 public:
61  explicit MarkCompact(Heap* heap, const std::string& name_prefix = "");
62  ~MarkCompact() {}
63
64  virtual void RunPhases() OVERRIDE NO_THREAD_SAFETY_ANALYSIS;
65  void InitializePhase();
66  void MarkingPhase() EXCLUSIVE_LOCKS_REQUIRED(Locks::mutator_lock_)
67      LOCKS_EXCLUDED(Locks::heap_bitmap_lock_);
68  void ReclaimPhase() EXCLUSIVE_LOCKS_REQUIRED(Locks::mutator_lock_)
69      LOCKS_EXCLUDED(Locks::heap_bitmap_lock_);
70  void FinishPhase() EXCLUSIVE_LOCKS_REQUIRED(Locks::mutator_lock_);
71  void MarkReachableObjects()
72      EXCLUSIVE_LOCKS_REQUIRED(Locks::mutator_lock_, Locks::heap_bitmap_lock_);
73  virtual GcType GetGcType() const OVERRIDE {
74    return kGcTypePartial;
75  }
76  virtual CollectorType GetCollectorType() const OVERRIDE {
77    return kCollectorTypeMC;
78  }
79
80  // Sets which space we will be copying objects in.
81  void SetSpace(space::BumpPointerSpace* space);
82
83  // Initializes internal structures.
84  void Init();
85
86  // Find the default mark bitmap.
87  void FindDefaultMarkBitmap();
88
89  void ScanObject(mirror::Object* obj)
90      EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_, Locks::mutator_lock_);
91
92  // Marks the root set at the start of a garbage collection.
93  void MarkRoots()
94      EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_, Locks::mutator_lock_);
95
96  // Bind the live bits to the mark bits of bitmaps for spaces that are never collected, ie
97  // the image. Mark that portion of the heap as immune.
98  void BindBitmaps() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_)
99      LOCKS_EXCLUDED(Locks::heap_bitmap_lock_);
100
101  void UnBindBitmaps()
102      EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_);
103
104  void ProcessReferences(Thread* self) EXCLUSIVE_LOCKS_REQUIRED(Locks::mutator_lock_)
105      EXCLUSIVE_LOCKS_REQUIRED(Locks::mutator_lock_);
106
107  // Sweeps unmarked objects to complete the garbage collection.
108  void Sweep(bool swap_bitmaps) EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_);
109
110  // Sweeps unmarked objects to complete the garbage collection.
111  void SweepLargeObjects(bool swap_bitmaps) EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_);
112
113  void SweepSystemWeaks()
114      SHARED_LOCKS_REQUIRED(Locks::heap_bitmap_lock_, Locks::mutator_lock_);
115
116  static void MarkRootCallback(mirror::Object** root, void* arg, uint32_t /*tid*/,
117                               RootType /*root_type*/)
118      EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_, Locks::mutator_lock_);
119
120  static mirror::Object* MarkObjectCallback(mirror::Object* root, void* arg)
121      EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_, Locks::mutator_lock_);
122
123  static void MarkHeapReferenceCallback(mirror::HeapReference<mirror::Object>* obj_ptr, void* arg)
124      EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_, Locks::mutator_lock_);
125
126  static bool HeapReferenceMarkedCallback(mirror::HeapReference<mirror::Object>* ref_ptr,
127                                          void* arg)
128      EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_, Locks::mutator_lock_);
129
130  static void ProcessMarkStackCallback(void* arg)
131      EXCLUSIVE_LOCKS_REQUIRED(Locks::mutator_lock_, Locks::heap_bitmap_lock_);
132
133  static void DelayReferenceReferentCallback(mirror::Class* klass, mirror::Reference* ref,
134                                             void* arg)
135      SHARED_LOCKS_REQUIRED(Locks::heap_bitmap_lock_, Locks::mutator_lock_);
136
137  // Schedules an unmarked object for reference processing.
138  void DelayReferenceReferent(mirror::Class* klass, mirror::Reference* reference)
139      SHARED_LOCKS_REQUIRED(Locks::heap_bitmap_lock_, Locks::mutator_lock_);
140
141 protected:
142  // Returns null if the object is not marked, otherwise returns the forwarding address (same as
143  // object for non movable things).
144  mirror::Object* GetMarkedForwardAddress(mirror::Object* object) const
145      EXCLUSIVE_LOCKS_REQUIRED(Locks::mutator_lock_)
146      SHARED_LOCKS_REQUIRED(Locks::heap_bitmap_lock_);
147
148  static mirror::Object* MarkedForwardingAddressCallback(mirror::Object* object, void* arg)
149      EXCLUSIVE_LOCKS_REQUIRED(Locks::mutator_lock_)
150      SHARED_LOCKS_REQUIRED(Locks::heap_bitmap_lock_);
151
152  // Marks or unmarks a large object based on whether or not set is true. If set is true, then we
153  // mark, otherwise we unmark.
154  bool MarkLargeObject(const mirror::Object* obj)
155      EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_)
156      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
157
158  // Expand mark stack to 2x its current size.
159  void ResizeMarkStack(size_t new_size);
160
161  // Returns true if we should sweep the space.
162  bool ShouldSweepSpace(space::ContinuousSpace* space) const;
163
164  // Push an object onto the mark stack.
165  void MarkStackPush(mirror::Object* obj);
166
167  void UpdateAndMarkModUnion()
168      EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_)
169      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
170
171  // Recursively blackens objects on the mark stack.
172  void ProcessMarkStack()
173      EXCLUSIVE_LOCKS_REQUIRED(Locks::mutator_lock_, Locks::heap_bitmap_lock_);
174
175  // 3 pass mark compact approach.
176  void Compact() EXCLUSIVE_LOCKS_REQUIRED(Locks::mutator_lock_, Locks::heap_bitmap_lock_);
177  // Calculate the forwarding address of objects marked as "live" in the objects_before_forwarding
178  // bitmap.
179  void CalculateObjectForwardingAddresses()
180      EXCLUSIVE_LOCKS_REQUIRED(Locks::mutator_lock_, Locks::heap_bitmap_lock_);
181  // Update the references of objects by using the forwarding addresses.
182  void UpdateReferences() EXCLUSIVE_LOCKS_REQUIRED(Locks::mutator_lock_, Locks::heap_bitmap_lock_);
183  static void UpdateRootCallback(mirror::Object** root, void* arg, uint32_t /*thread_id*/,
184                                 RootType /*root_type*/)
185      EXCLUSIVE_LOCKS_REQUIRED(Locks::mutator_lock_)
186      SHARED_LOCKS_REQUIRED(Locks::heap_bitmap_lock_);
187  // Move objects and restore lock words.
188  void MoveObjects() EXCLUSIVE_LOCKS_REQUIRED(Locks::mutator_lock_);
189  // Move a single object to its forward address.
190  void MoveObject(mirror::Object* obj, size_t len) EXCLUSIVE_LOCKS_REQUIRED(Locks::mutator_lock_);
191  // Mark a single object.
192  void MarkObject(mirror::Object* obj) EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_,
193                                                                Locks::mutator_lock_);
194  bool IsMarked(const mirror::Object* obj) const
195      SHARED_LOCKS_REQUIRED(Locks::heap_bitmap_lock_);
196  static mirror::Object* IsMarkedCallback(mirror::Object* object, void* arg)
197      SHARED_LOCKS_REQUIRED(Locks::heap_bitmap_lock_);
198  void ForwardObject(mirror::Object* obj) EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_,
199                                                                   Locks::mutator_lock_);
200  // Update a single heap reference.
201  void UpdateHeapReference(mirror::HeapReference<mirror::Object>* reference)
202      SHARED_LOCKS_REQUIRED(Locks::heap_bitmap_lock_)
203      EXCLUSIVE_LOCKS_REQUIRED(Locks::mutator_lock_);
204  static void UpdateHeapReferenceCallback(mirror::HeapReference<mirror::Object>* reference,
205                                          void* arg)
206      SHARED_LOCKS_REQUIRED(Locks::heap_bitmap_lock_)
207      EXCLUSIVE_LOCKS_REQUIRED(Locks::mutator_lock_);
208  // Update all of the references of a single object.
209  void UpdateObjectReferences(mirror::Object* obj)
210      SHARED_LOCKS_REQUIRED(Locks::heap_bitmap_lock_)
211      EXCLUSIVE_LOCKS_REQUIRED(Locks::mutator_lock_);
212
213  // Revoke all the thread-local buffers.
214  void RevokeAllThreadLocalBuffers();
215
216  accounting::ObjectStack* mark_stack_;
217
218  // Immune region, every object inside the immune region is assumed to be marked.
219  ImmuneRegion immune_region_;
220
221  // Bump pointer space which we are collecting.
222  space::BumpPointerSpace* space_;
223  // Cached mark bitmap as an optimization.
224  accounting::HeapBitmap* mark_bitmap_;
225
226  // The name of the collector.
227  std::string collector_name_;
228
229  // The bump pointer in the space where the next forwarding address will be.
230  byte* bump_pointer_;
231  // How many live objects we have in the space.
232  size_t live_objects_in_space_;
233
234  // Bitmap which describes which objects we have to move, need to do / 2 so that we can handle
235  // objects which are only 8 bytes.
236  std::unique_ptr<accounting::ContinuousSpaceBitmap> objects_before_forwarding_;
237  // Bitmap which describes which lock words we need to restore.
238  std::unique_ptr<accounting::ContinuousSpaceBitmap> objects_with_lockword_;
239  // Which lock words we need to restore as we are moving objects.
240  std::deque<LockWord> lock_words_to_restore_;
241
242 private:
243  friend class BitmapSetSlowPathVisitor;
244  friend class CalculateObjectForwardingAddressVisitor;
245  friend class MarkCompactMarkObjectVisitor;
246  friend class MoveObjectVisitor;
247  friend class UpdateObjectReferencesVisitor;
248  friend class UpdateReferenceVisitor;
249  DISALLOW_COPY_AND_ASSIGN(MarkCompact);
250};
251
252}  // namespace collector
253}  // namespace gc
254}  // namespace art
255
256#endif  // ART_RUNTIME_GC_COLLECTOR_MARK_COMPACT_H_
257