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 "atomic.h"
23 #include "base/macros.h"
24 #include "base/mutex.h"
25 #include "garbage_collector.h"
26 #include "gc_root.h"
27 #include "gc/accounting/heap_bitmap.h"
28 #include "immune_spaces.h"
29 #include "mirror/object_reference.h"
30 #include "object_callbacks.h"
31 #include "offsets.h"
32 
33 namespace art {
34 
35 class Thread;
36 
37 namespace mirror {
38   class Class;
39   class Object;
40 }  // namespace mirror
41 
42 namespace gc {
43 
44 class Heap;
45 
46 namespace accounting {
47   template <typename T> class AtomicStack;
48   typedef AtomicStack<mirror::Object> ObjectStack;
49 }  // namespace accounting
50 
51 namespace space {
52   class ContinuousMemMapAllocSpace;
53   class ContinuousSpace;
54 }  // namespace space
55 
56 namespace collector {
57 
58 class SemiSpace : public GarbageCollector {
59  public:
60   // If true, use remembered sets in the generational mode.
61   static constexpr bool kUseRememberedSet = true;
62 
63   explicit SemiSpace(Heap* heap, bool generational = false, const std::string& name_prefix = "");
64 
~SemiSpace()65   ~SemiSpace() {}
66 
67   virtual void RunPhases() OVERRIDE NO_THREAD_SAFETY_ANALYSIS;
68   virtual void InitializePhase();
69   virtual void MarkingPhase() REQUIRES(Locks::mutator_lock_)
70       REQUIRES(!Locks::heap_bitmap_lock_);
71   virtual void ReclaimPhase() REQUIRES(Locks::mutator_lock_)
72       REQUIRES(!Locks::heap_bitmap_lock_);
73   virtual void FinishPhase() REQUIRES(Locks::mutator_lock_);
74   void MarkReachableObjects()
75       REQUIRES(Locks::mutator_lock_, Locks::heap_bitmap_lock_);
GetGcType()76   virtual GcType GetGcType() const OVERRIDE {
77     return kGcTypePartial;
78   }
GetCollectorType()79   virtual CollectorType GetCollectorType() const OVERRIDE {
80     return generational_ ? kCollectorTypeGSS : kCollectorTypeSS;
81   }
82 
83   // Sets which space we will be copying objects to.
84   void SetToSpace(space::ContinuousMemMapAllocSpace* to_space);
85 
86   // Set the space where we copy objects from.
87   void SetFromSpace(space::ContinuousMemMapAllocSpace* from_space);
88 
89   // Set whether or not we swap the semi spaces in the heap. This needs to be done with mutators
90   // suspended.
SetSwapSemiSpaces(bool swap_semi_spaces)91   void SetSwapSemiSpaces(bool swap_semi_spaces) {
92     swap_semi_spaces_ = swap_semi_spaces;
93   }
94 
95   // Initializes internal structures.
96   void Init();
97 
98   // Find the default mark bitmap.
99   void FindDefaultMarkBitmap();
100 
101   // Updates obj_ptr if the object has moved.
102   template<bool kPoisonReferences>
103   void MarkObject(mirror::ObjectReference<kPoisonReferences, mirror::Object>* obj_ptr)
104       REQUIRES(Locks::heap_bitmap_lock_, Locks::mutator_lock_);
105 
106   template<bool kPoisonReferences>
107   void MarkObjectIfNotInToSpace(mirror::ObjectReference<kPoisonReferences, mirror::Object>* obj_ptr)
108       REQUIRES(Locks::heap_bitmap_lock_, Locks::mutator_lock_);
109 
110   virtual mirror::Object* MarkObject(mirror::Object* root) OVERRIDE
111       REQUIRES(Locks::heap_bitmap_lock_, Locks::mutator_lock_);
112 
113   virtual void MarkHeapReference(mirror::HeapReference<mirror::Object>* obj_ptr,
114                                  bool do_atomic_update) OVERRIDE
115       REQUIRES(Locks::heap_bitmap_lock_, Locks::mutator_lock_);
116 
117   void ScanObject(mirror::Object* obj)
118       REQUIRES(Locks::heap_bitmap_lock_, Locks::mutator_lock_);
119 
120   void VerifyNoFromSpaceReferences(mirror::Object* obj)
121       REQUIRES_SHARED(Locks::heap_bitmap_lock_, Locks::mutator_lock_);
122 
123   // Marks the root set at the start of a garbage collection.
124   void MarkRoots()
125       REQUIRES(Locks::heap_bitmap_lock_, Locks::mutator_lock_);
126 
127   // Bind the live bits to the mark bits of bitmaps for spaces that are never collected, ie
128   // the image. Mark that portion of the heap as immune.
129   virtual void BindBitmaps() REQUIRES_SHARED(Locks::mutator_lock_)
130       REQUIRES(!Locks::heap_bitmap_lock_);
131 
132   void UnBindBitmaps()
133       REQUIRES(Locks::heap_bitmap_lock_);
134 
135   void ProcessReferences(Thread* self) REQUIRES(Locks::mutator_lock_)
136       REQUIRES(Locks::mutator_lock_);
137 
138   // Sweeps unmarked objects to complete the garbage collection.
139   virtual void Sweep(bool swap_bitmaps)
140       REQUIRES(Locks::heap_bitmap_lock_)
141       REQUIRES_SHARED(Locks::mutator_lock_);
142 
143   // Sweeps unmarked objects to complete the garbage collection.
144   void SweepLargeObjects(bool swap_bitmaps) REQUIRES(Locks::heap_bitmap_lock_);
145 
146   void SweepSystemWeaks()
147       REQUIRES_SHARED(Locks::heap_bitmap_lock_, Locks::mutator_lock_);
148 
149   virtual void VisitRoots(mirror::Object*** roots, size_t count, const RootInfo& info) OVERRIDE
150       REQUIRES(Locks::mutator_lock_, Locks::heap_bitmap_lock_);
151 
152   virtual void VisitRoots(mirror::CompressedReference<mirror::Object>** roots, 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       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   virtual mirror::Object* IsMarked(mirror::Object* object) OVERRIDE
167       REQUIRES(Locks::mutator_lock_)
168       REQUIRES_SHARED(Locks::heap_bitmap_lock_);
169 
170   virtual 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()
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();
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