1 /*
2  * Copyright (C) 2013 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_SEMI_SPACE_H_
18 #define ART_RUNTIME_GC_COLLECTOR_SEMI_SPACE_H_
19 
20 #include <memory>
21 
22 #include "base/atomic.h"
23 #include "base/locks.h"
24 #include "base/macros.h"
25 #include "garbage_collector.h"
26 #include "gc/accounting/heap_bitmap.h"
27 #include "gc_root.h"
28 #include "immune_spaces.h"
29 #include "mirror/object_reference.h"
30 #include "offsets.h"
31 
32 namespace art {
33 
34 class Thread;
35 
36 namespace mirror {
37 class Class;
38 class Object;
39 }  // namespace mirror
40 
41 namespace gc {
42 
43 class Heap;
44 
45 namespace accounting {
46 template <typename T> class AtomicStack;
47 typedef AtomicStack<mirror::Object> ObjectStack;
48 }  // namespace accounting
49 
50 namespace space {
51 class ContinuousMemMapAllocSpace;
52 class ContinuousSpace;
53 }  // namespace space
54 
55 namespace collector {
56 
57 class SemiSpace : public GarbageCollector {
58  public:
59   // If true, use remembered sets in the generational mode.
60   static constexpr bool kUseRememberedSet = true;
61 
62   explicit SemiSpace(Heap* heap, bool generational = false, const std::string& name_prefix = "");
63 
~SemiSpace()64   ~SemiSpace() {}
65 
66   void RunPhases() override NO_THREAD_SAFETY_ANALYSIS;
67   virtual void InitializePhase();
68   virtual void MarkingPhase() REQUIRES(Locks::mutator_lock_)
69       REQUIRES(!Locks::heap_bitmap_lock_);
70   virtual void ReclaimPhase() REQUIRES(Locks::mutator_lock_)
71       REQUIRES(!Locks::heap_bitmap_lock_);
72   virtual void FinishPhase() REQUIRES(Locks::mutator_lock_);
73   void MarkReachableObjects()
74       REQUIRES(Locks::mutator_lock_, Locks::heap_bitmap_lock_);
GetGcType()75   GcType GetGcType() const override {
76     return kGcTypePartial;
77   }
GetCollectorType()78   CollectorType GetCollectorType() const override {
79     return generational_ ? kCollectorTypeGSS : kCollectorTypeSS;
80   }
81 
82   // Sets which space we will be copying objects to.
83   void SetToSpace(space::ContinuousMemMapAllocSpace* to_space);
84 
85   // Set the space where we copy objects from.
86   void SetFromSpace(space::ContinuousMemMapAllocSpace* from_space);
87 
88   // Set whether or not we swap the semi spaces in the heap. This needs to be done with mutators
89   // suspended.
SetSwapSemiSpaces(bool swap_semi_spaces)90   void SetSwapSemiSpaces(bool swap_semi_spaces) {
91     swap_semi_spaces_ = swap_semi_spaces;
92   }
93 
94   // Initializes internal structures.
95   void Init();
96 
97   // Find the default mark bitmap.
98   void FindDefaultMarkBitmap();
99 
100   // Updates obj_ptr if the object has moved. Takes either an ObjectReference or a HeapReference.
101   template<typename CompressedReferenceType>
102   void MarkObject(CompressedReferenceType* obj_ptr)
103       REQUIRES(Locks::heap_bitmap_lock_, Locks::mutator_lock_);
104 
105   template<typename CompressedReferenceType>
106   void MarkObjectIfNotInToSpace(CompressedReferenceType* obj_ptr)
107       REQUIRES(Locks::heap_bitmap_lock_, Locks::mutator_lock_);
108 
109   mirror::Object* MarkObject(mirror::Object* root) override
110       REQUIRES(Locks::heap_bitmap_lock_, Locks::mutator_lock_);
111 
112   void MarkHeapReference(mirror::HeapReference<mirror::Object>* obj_ptr,
113                          bool do_atomic_update) override
114       REQUIRES(Locks::heap_bitmap_lock_, Locks::mutator_lock_);
115 
116   void ScanObject(mirror::Object* obj)
117       REQUIRES(Locks::heap_bitmap_lock_, Locks::mutator_lock_);
118 
119   void VerifyNoFromSpaceReferences(mirror::Object* obj)
120       REQUIRES_SHARED(Locks::heap_bitmap_lock_, Locks::mutator_lock_);
121 
122   // Marks the root set at the start of a garbage collection.
123   void MarkRoots()
124       REQUIRES(Locks::heap_bitmap_lock_, Locks::mutator_lock_);
125 
126   // Bind the live bits to the mark bits of bitmaps for spaces that are never collected, ie
127   // the image. Mark that portion of the heap as immune.
128   virtual void BindBitmaps() REQUIRES_SHARED(Locks::mutator_lock_)
129       REQUIRES(!Locks::heap_bitmap_lock_);
130 
131   void UnBindBitmaps()
132       REQUIRES(Locks::heap_bitmap_lock_);
133 
134   void ProcessReferences(Thread* self) REQUIRES(Locks::mutator_lock_)
135       REQUIRES(Locks::mutator_lock_);
136 
137   // Sweeps unmarked objects to complete the garbage collection.
138   virtual void Sweep(bool swap_bitmaps)
139       REQUIRES(Locks::heap_bitmap_lock_)
140       REQUIRES_SHARED(Locks::mutator_lock_);
141 
142   // Sweeps unmarked objects to complete the garbage collection.
143   void SweepLargeObjects(bool swap_bitmaps) REQUIRES(Locks::heap_bitmap_lock_);
144 
145   void SweepSystemWeaks()
146       REQUIRES_SHARED(Locks::heap_bitmap_lock_, Locks::mutator_lock_);
147 
148   void VisitRoots(mirror::Object*** roots, size_t count, const RootInfo& info) override
149       REQUIRES(Locks::mutator_lock_, Locks::heap_bitmap_lock_);
150 
151   void VisitRoots(mirror::CompressedReference<mirror::Object>** roots,
152                   size_t count,
153                   const RootInfo& info) override
154       REQUIRES(Locks::mutator_lock_, Locks::heap_bitmap_lock_);
155 
156   virtual mirror::Object* MarkNonForwardedObject(mirror::Object* obj)
157       REQUIRES(Locks::heap_bitmap_lock_, Locks::mutator_lock_);
158 
159   // Schedules an unmarked object for reference processing.
160   void DelayReferenceReferent(ObjPtr<mirror::Class> klass, ObjPtr<mirror::Reference> reference)
161       override REQUIRES_SHARED(Locks::heap_bitmap_lock_, Locks::mutator_lock_);
162 
163  protected:
164   // Returns null if the object is not marked, otherwise returns the forwarding address (same as
165   // object for non movable things).
166   mirror::Object* IsMarked(mirror::Object* object) override
167       REQUIRES(Locks::mutator_lock_)
168       REQUIRES_SHARED(Locks::heap_bitmap_lock_);
169 
170   bool IsNullOrMarkedHeapReference(mirror::HeapReference<mirror::Object>* object,
171                                    bool do_atomic_update) override
172       REQUIRES(Locks::mutator_lock_)
173       REQUIRES_SHARED(Locks::heap_bitmap_lock_);
174 
175   // Marks or unmarks a large object based on whether or not set is true. If set is true, then we
176   // mark, otherwise we unmark.
177   bool MarkLargeObject(const mirror::Object* obj)
178       REQUIRES(Locks::heap_bitmap_lock_)
179       REQUIRES_SHARED(Locks::mutator_lock_);
180 
181   // Expand mark stack to 2x its current size.
182   void ResizeMarkStack(size_t new_size) REQUIRES_SHARED(Locks::mutator_lock_);
183 
184   // Returns true if we should sweep the space.
185   virtual bool ShouldSweepSpace(space::ContinuousSpace* space) const;
186 
187   // Push an object onto the mark stack.
188   void MarkStackPush(mirror::Object* obj) REQUIRES_SHARED(Locks::mutator_lock_);
189 
190   void UpdateAndMarkModUnion()
191       REQUIRES(Locks::heap_bitmap_lock_)
192       REQUIRES_SHARED(Locks::mutator_lock_);
193 
194   // Recursively blackens objects on the mark stack.
195   void ProcessMarkStack() override
196       REQUIRES(Locks::mutator_lock_, Locks::heap_bitmap_lock_);
197 
198   inline mirror::Object* GetForwardingAddressInFromSpace(mirror::Object* obj) const
199       REQUIRES_SHARED(Locks::mutator_lock_);
200 
201   // Revoke all the thread-local buffers.
202   void RevokeAllThreadLocalBuffers() override;
203 
204   // Current space, we check this space first to avoid searching for the appropriate space for an
205   // object.
206   accounting::ObjectStack* mark_stack_;
207 
208   // Every object inside the immune spaces is assumed to be marked.
209   ImmuneSpaces immune_spaces_;
210 
211   // If true, the large object space is immune.
212   bool is_large_object_space_immune_;
213 
214   // Destination and source spaces (can be any type of ContinuousMemMapAllocSpace which either has
215   // a live bitmap or doesn't).
216   space::ContinuousMemMapAllocSpace* to_space_;
217   // Cached live bitmap as an optimization.
218   accounting::ContinuousSpaceBitmap* to_space_live_bitmap_;
219   space::ContinuousMemMapAllocSpace* from_space_;
220   // Cached mark bitmap as an optimization.
221   accounting::HeapBitmap* mark_bitmap_;
222 
223   Thread* self_;
224 
225   // When true, the generational mode (promotion and the bump pointer
226   // space only collection) is enabled. TODO: move these to a new file
227   // as a new garbage collector?
228   const bool generational_;
229 
230   // Used for the generational mode. the end/top of the bump
231   // pointer space at the end of the last collection.
232   uint8_t* last_gc_to_space_end_;
233 
234   // Used for the generational mode. During a collection, keeps track
235   // of how many bytes of objects have been copied so far from the
236   // bump pointer space to the non-moving space.
237   uint64_t bytes_promoted_;
238 
239   // Used for the generational mode. Keeps track of how many bytes of
240   // objects have been copied so far from the bump pointer space to
241   // the non-moving space, since the last whole heap collection.
242   uint64_t bytes_promoted_since_last_whole_heap_collection_;
243 
244   // Used for the generational mode. Keeps track of how many bytes of
245   // large objects were allocated at the last whole heap collection.
246   uint64_t large_object_bytes_allocated_at_last_whole_heap_collection_;
247 
248   // Used for generational mode. When true, we only collect the from_space_.
249   bool collect_from_space_only_;
250 
251   // The space which we are promoting into, only used for GSS.
252   space::ContinuousMemMapAllocSpace* promo_dest_space_;
253 
254   // The space which we copy to if the to_space_ is full.
255   space::ContinuousMemMapAllocSpace* fallback_space_;
256 
257   // How many objects and bytes we moved, used so that we don't need to Get the size of the
258   // to_space_ when calculating how many objects and bytes we freed.
259   size_t bytes_moved_;
260   size_t objects_moved_;
261 
262   // How many bytes we avoided dirtying.
263   size_t saved_bytes_;
264 
265   // The name of the collector.
266   std::string collector_name_;
267 
268   // Used for the generational mode. The default interval of the whole
269   // heap collection. If N, the whole heap collection occurs every N
270   // collections.
271   static constexpr int kDefaultWholeHeapCollectionInterval = 5;
272 
273   // Whether or not we swap the semi spaces in the heap during the marking phase.
274   bool swap_semi_spaces_;
275 
276  private:
277   class BitmapSetSlowPathVisitor;
278   class MarkObjectVisitor;
279   class VerifyNoFromSpaceReferencesVisitor;
280   DISALLOW_IMPLICIT_CONSTRUCTORS(SemiSpace);
281 };
282 
283 }  // namespace collector
284 }  // namespace gc
285 }  // namespace art
286 
287 #endif  // ART_RUNTIME_GC_COLLECTOR_SEMI_SPACE_H_
288