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_SPACE_SPACE_H_
18 #define ART_RUNTIME_GC_SPACE_SPACE_H_
19 
20 #include <memory>
21 #include <string>
22 
23 #include "base/atomic.h"
24 #include "base/locks.h"
25 #include "base/macros.h"
26 #include "base/mem_map.h"
27 #include "gc/accounting/space_bitmap.h"
28 #include "gc/collector/object_byte_pair.h"
29 #include "runtime_globals.h"
30 
31 namespace art {
32 namespace mirror {
33 class Object;
34 }  // namespace mirror
35 
36 namespace gc {
37 
38 class Heap;
39 
40 namespace space {
41 
42 class AllocSpace;
43 class BumpPointerSpace;
44 class ContinuousMemMapAllocSpace;
45 class ContinuousSpace;
46 class DiscontinuousSpace;
47 class MallocSpace;
48 class DlMallocSpace;
49 class RosAllocSpace;
50 class ImageSpace;
51 class LargeObjectSpace;
52 class RegionSpace;
53 class ZygoteSpace;
54 
55 static constexpr bool kDebugSpaces = kIsDebugBuild;
56 
57 // See Space::GetGcRetentionPolicy.
58 enum GcRetentionPolicy {
59   // Objects are retained forever with this policy for a space.
60   kGcRetentionPolicyNeverCollect,
61   // Every GC cycle will attempt to collect objects in this space.
62   kGcRetentionPolicyAlwaysCollect,
63   // Objects will be considered for collection only in "full" GC cycles, ie faster partial
64   // collections won't scan these areas such as the Zygote.
65   kGcRetentionPolicyFullCollect,
66 };
67 std::ostream& operator<<(std::ostream& os, const GcRetentionPolicy& policy);
68 
69 enum SpaceType {
70   kSpaceTypeImageSpace,
71   kSpaceTypeMallocSpace,
72   kSpaceTypeZygoteSpace,
73   kSpaceTypeBumpPointerSpace,
74   kSpaceTypeLargeObjectSpace,
75   kSpaceTypeRegionSpace,
76 };
77 std::ostream& operator<<(std::ostream& os, const SpaceType& space_type);
78 
79 // A space contains memory allocated for managed objects.
80 class Space {
81  public:
82   // Dump space. Also key method for C++ vtables.
83   virtual void Dump(std::ostream& os) const;
84 
85   // Name of the space. May vary, for example before/after the Zygote fork.
GetName()86   const char* GetName() const {
87     return name_.c_str();
88   }
89 
90   // The policy of when objects are collected associated with this space.
GetGcRetentionPolicy()91   GcRetentionPolicy GetGcRetentionPolicy() const {
92     return gc_retention_policy_;
93   }
94 
95   // Is the given object contained within this space?
96   virtual bool Contains(const mirror::Object* obj) const = 0;
97 
98   // The kind of space this: image, alloc, zygote, large object.
99   virtual SpaceType GetType() const = 0;
100 
101   // Is this an image space, ie one backed by a memory mapped image file.
IsImageSpace()102   bool IsImageSpace() const {
103     return GetType() == kSpaceTypeImageSpace;
104   }
105   ImageSpace* AsImageSpace();
106 
107   // Is this a dlmalloc backed allocation space?
IsMallocSpace()108   bool IsMallocSpace() const {
109     SpaceType type = GetType();
110     return type == kSpaceTypeMallocSpace;
111   }
112   MallocSpace* AsMallocSpace();
113 
IsDlMallocSpace()114   virtual bool IsDlMallocSpace() const {
115     return false;
116   }
117   virtual DlMallocSpace* AsDlMallocSpace();
118 
IsRosAllocSpace()119   virtual bool IsRosAllocSpace() const {
120     return false;
121   }
122   virtual RosAllocSpace* AsRosAllocSpace();
123 
124   // Is this the space allocated into by the Zygote and no-longer in use for allocation?
IsZygoteSpace()125   bool IsZygoteSpace() const {
126     return GetType() == kSpaceTypeZygoteSpace;
127   }
128   virtual ZygoteSpace* AsZygoteSpace();
129 
130   // Is this space a bump pointer space?
IsBumpPointerSpace()131   bool IsBumpPointerSpace() const {
132     return GetType() == kSpaceTypeBumpPointerSpace;
133   }
134   virtual BumpPointerSpace* AsBumpPointerSpace();
135 
IsRegionSpace()136   bool IsRegionSpace() const {
137     return GetType() == kSpaceTypeRegionSpace;
138   }
139   virtual RegionSpace* AsRegionSpace();
140 
141   // Does this space hold large objects and implement the large object space abstraction?
IsLargeObjectSpace()142   bool IsLargeObjectSpace() const {
143     return GetType() == kSpaceTypeLargeObjectSpace;
144   }
145   LargeObjectSpace* AsLargeObjectSpace();
146 
IsContinuousSpace()147   virtual bool IsContinuousSpace() const {
148     return false;
149   }
150   ContinuousSpace* AsContinuousSpace();
151 
IsDiscontinuousSpace()152   virtual bool IsDiscontinuousSpace() const {
153     return false;
154   }
155   DiscontinuousSpace* AsDiscontinuousSpace();
156 
IsAllocSpace()157   virtual bool IsAllocSpace() const {
158     return false;
159   }
160   virtual AllocSpace* AsAllocSpace();
161 
IsContinuousMemMapAllocSpace()162   virtual bool IsContinuousMemMapAllocSpace() const {
163     return false;
164   }
165   virtual ContinuousMemMapAllocSpace* AsContinuousMemMapAllocSpace();
166 
167   // Returns true if objects in the space are movable.
168   virtual bool CanMoveObjects() const = 0;
169 
~Space()170   virtual ~Space() {}
171 
172  protected:
173   Space(const std::string& name, GcRetentionPolicy gc_retention_policy);
174 
SetGcRetentionPolicy(GcRetentionPolicy gc_retention_policy)175   void SetGcRetentionPolicy(GcRetentionPolicy gc_retention_policy) {
176     gc_retention_policy_ = gc_retention_policy;
177   }
178 
179   // Name of the space that may vary due to the Zygote fork.
180   std::string name_;
181 
182  protected:
183   // When should objects within this space be reclaimed? Not constant as we vary it in the case
184   // of Zygote forking.
185   GcRetentionPolicy gc_retention_policy_;
186 
187  private:
188   friend class art::gc::Heap;
189   DISALLOW_IMPLICIT_CONSTRUCTORS(Space);
190 };
191 std::ostream& operator<<(std::ostream& os, const Space& space);
192 
193 // AllocSpace interface.
194 class AllocSpace {
195  public:
196   // Number of bytes currently allocated.
197   virtual uint64_t GetBytesAllocated() = 0;
198   // Number of objects currently allocated.
199   virtual uint64_t GetObjectsAllocated() = 0;
200 
201   // Allocate num_bytes without allowing growth. If the allocation
202   // succeeds, the output parameter bytes_allocated will be set to the
203   // actually allocated bytes which is >= num_bytes.
204   // Alloc can be called from multiple threads at the same time and must be thread-safe.
205   //
206   // bytes_tl_bulk_allocated - bytes allocated in bulk ahead of time for a thread local allocation,
207   // if applicable. It is
208   // 1) equal to bytes_allocated if it's not a thread local allocation,
209   // 2) greater than bytes_allocated if it's a thread local
210   //    allocation that required a new buffer, or
211   // 3) zero if it's a thread local allocation in an existing
212   //    buffer.
213   // This is what is to be added to Heap::num_bytes_allocated_.
214   virtual mirror::Object* Alloc(Thread* self, size_t num_bytes, size_t* bytes_allocated,
215                                 size_t* usable_size, size_t* bytes_tl_bulk_allocated) = 0;
216 
217   // Thread-unsafe allocation for when mutators are suspended, used by the semispace collector.
AllocThreadUnsafe(Thread * self,size_t num_bytes,size_t * bytes_allocated,size_t * usable_size,size_t * bytes_tl_bulk_allocated)218   virtual mirror::Object* AllocThreadUnsafe(Thread* self, size_t num_bytes, size_t* bytes_allocated,
219                                             size_t* usable_size,
220                                             size_t* bytes_tl_bulk_allocated)
221       REQUIRES(Locks::mutator_lock_) {
222     return Alloc(self, num_bytes, bytes_allocated, usable_size, bytes_tl_bulk_allocated);
223   }
224 
225   // Return the storage space required by obj.
226   virtual size_t AllocationSize(mirror::Object* obj, size_t* usable_size) = 0;
227 
228   // Returns how many bytes were freed.
229   virtual size_t Free(Thread* self, mirror::Object* ptr) = 0;
230 
231   // Free (deallocate) all objects in a list, and return the number of bytes freed.
232   virtual size_t FreeList(Thread* self, size_t num_ptrs, mirror::Object** ptrs) = 0;
233 
234   // Revoke any sort of thread-local buffers that are used to speed up allocations for the given
235   // thread, if the alloc space implementation uses any.
236   // Returns the total free bytes in the revoked thread local runs that's to be subtracted
237   // from Heap::num_bytes_allocated_ or zero if unnecessary.
238   virtual size_t RevokeThreadLocalBuffers(Thread* thread) = 0;
239 
240   // Revoke any sort of thread-local buffers that are used to speed up allocations for all the
241   // threads, if the alloc space implementation uses any.
242   // Returns the total free bytes in the revoked thread local runs that's to be subtracted
243   // from Heap::num_bytes_allocated_ or zero if unnecessary.
244   virtual size_t RevokeAllThreadLocalBuffers() = 0;
245 
246   virtual void LogFragmentationAllocFailure(std::ostream& os, size_t failed_alloc_bytes) = 0;
247 
248  protected:
249   struct SweepCallbackContext {
250     SweepCallbackContext(bool swap_bitmaps, space::Space* space);
251     const bool swap_bitmaps;
252     space::Space* const space;
253     Thread* const self;
254     collector::ObjectBytePair freed;
255   };
256 
AllocSpace()257   AllocSpace() {}
~AllocSpace()258   virtual ~AllocSpace() {}
259 
260  private:
261   DISALLOW_COPY_AND_ASSIGN(AllocSpace);
262 };
263 
264 // Continuous spaces have bitmaps, and an address range. Although not required, objects within
265 // continuous spaces can be marked in the card table.
266 class ContinuousSpace : public Space {
267  public:
268   // Address at which the space begins.
Begin()269   uint8_t* Begin() const {
270     return begin_;
271   }
272 
273   // Current address at which the space ends, which may vary as the space is filled.
End()274   uint8_t* End() const {
275     return end_.load(std::memory_order_relaxed);
276   }
277 
278   // The end of the address range covered by the space.
Limit()279   uint8_t* Limit() const {
280     return limit_;
281   }
282 
283   // Change the end of the space. Be careful with use since changing the end of a space to an
284   // invalid value may break the GC.
SetEnd(uint8_t * end)285   void SetEnd(uint8_t* end) {
286     end_.store(end, std::memory_order_relaxed);
287   }
288 
SetLimit(uint8_t * limit)289   void SetLimit(uint8_t* limit) {
290     limit_ = limit;
291   }
292 
293   // Current size of space
Size()294   size_t Size() const {
295     return End() - Begin();
296   }
297 
298   virtual accounting::ContinuousSpaceBitmap* GetLiveBitmap() = 0;
299   virtual accounting::ContinuousSpaceBitmap* GetMarkBitmap() = 0;
300 
301   // Maximum which the mapped space can grow to.
Capacity()302   virtual size_t Capacity() const {
303     return Limit() - Begin();
304   }
305 
306   // Is object within this space? We check to see if the pointer is beyond the end first as
307   // continuous spaces are iterated over from low to high.
HasAddress(const mirror::Object * obj)308   bool HasAddress(const mirror::Object* obj) const {
309     const uint8_t* byte_ptr = reinterpret_cast<const uint8_t*>(obj);
310     return byte_ptr >= Begin() && byte_ptr < Limit();
311   }
312 
Contains(const mirror::Object * obj)313   bool Contains(const mirror::Object* obj) const {
314     return HasAddress(obj);
315   }
316 
IsContinuousSpace()317   virtual bool IsContinuousSpace() const {
318     return true;
319   }
320 
321   bool HasBoundBitmaps() REQUIRES(Locks::heap_bitmap_lock_);
322 
~ContinuousSpace()323   virtual ~ContinuousSpace() {}
324 
325  protected:
ContinuousSpace(const std::string & name,GcRetentionPolicy gc_retention_policy,uint8_t * begin,uint8_t * end,uint8_t * limit)326   ContinuousSpace(const std::string& name, GcRetentionPolicy gc_retention_policy,
327                   uint8_t* begin, uint8_t* end, uint8_t* limit) :
328       Space(name, gc_retention_policy), begin_(begin), end_(end), limit_(limit) {
329   }
330 
331   // The beginning of the storage for fast access.
332   uint8_t* begin_;
333 
334   // Current end of the space.
335   Atomic<uint8_t*> end_;
336 
337   // Limit of the space.
338   uint8_t* limit_;
339 
340  private:
341   DISALLOW_IMPLICIT_CONSTRUCTORS(ContinuousSpace);
342 };
343 
344 // A space where objects may be allocated higgledy-piggledy throughout virtual memory. Currently
345 // the card table can't cover these objects and so the write barrier shouldn't be triggered. This
346 // is suitable for use for large primitive arrays.
347 class DiscontinuousSpace : public Space {
348  public:
GetLiveBitmap()349   accounting::LargeObjectBitmap* GetLiveBitmap() {
350     return &live_bitmap_;
351   }
352 
GetMarkBitmap()353   accounting::LargeObjectBitmap* GetMarkBitmap() {
354     return &mark_bitmap_;
355   }
356 
IsDiscontinuousSpace()357   bool IsDiscontinuousSpace() const override {
358     return true;
359   }
360 
~DiscontinuousSpace()361   virtual ~DiscontinuousSpace() {}
362 
363  protected:
364   DiscontinuousSpace(const std::string& name, GcRetentionPolicy gc_retention_policy);
365 
366   accounting::LargeObjectBitmap live_bitmap_;
367   accounting::LargeObjectBitmap mark_bitmap_;
368 
369  private:
370   DISALLOW_IMPLICIT_CONSTRUCTORS(DiscontinuousSpace);
371 };
372 
373 class MemMapSpace : public ContinuousSpace {
374  public:
375   // Size of the space without a limit on its growth. By default this is just the Capacity, but
376   // for the allocation space we support starting with a small heap and then extending it.
NonGrowthLimitCapacity()377   virtual size_t NonGrowthLimitCapacity() const {
378     return Capacity();
379   }
380 
GetMemMap()381   MemMap* GetMemMap() {
382     return &mem_map_;
383   }
384 
GetMemMap()385   const MemMap* GetMemMap() const {
386     return &mem_map_;
387   }
388 
ReleaseMemMap()389   MemMap ReleaseMemMap() {
390     return std::move(mem_map_);
391   }
392 
393  protected:
MemMapSpace(const std::string & name,MemMap && mem_map,uint8_t * begin,uint8_t * end,uint8_t * limit,GcRetentionPolicy gc_retention_policy)394   MemMapSpace(const std::string& name,
395               MemMap&& mem_map,
396               uint8_t* begin,
397               uint8_t* end,
398               uint8_t* limit,
399               GcRetentionPolicy gc_retention_policy)
400       : ContinuousSpace(name, gc_retention_policy, begin, end, limit),
401         mem_map_(std::move(mem_map)) {
402   }
403 
404   // Underlying storage of the space
405   MemMap mem_map_;
406 
407  private:
408   DISALLOW_IMPLICIT_CONSTRUCTORS(MemMapSpace);
409 };
410 
411 // Used by the heap compaction interface to enable copying from one type of alloc space to another.
412 class ContinuousMemMapAllocSpace : public MemMapSpace, public AllocSpace {
413  public:
IsAllocSpace()414   bool IsAllocSpace() const override {
415     return true;
416   }
AsAllocSpace()417   AllocSpace* AsAllocSpace() override {
418     return this;
419   }
420 
IsContinuousMemMapAllocSpace()421   bool IsContinuousMemMapAllocSpace() const override {
422     return true;
423   }
AsContinuousMemMapAllocSpace()424   ContinuousMemMapAllocSpace* AsContinuousMemMapAllocSpace() override {
425     return this;
426   }
427 
428   // Make the mark bitmap an alias of the live bitmap. Save the current mark bitmap into
429   // `temp_bitmap_`, so that we can restore it later in ContinuousMemMapAllocSpace::UnBindBitmaps.
430   void BindLiveToMarkBitmap() REQUIRES(Locks::heap_bitmap_lock_);
431   // Unalias the mark bitmap from the live bitmap and restore the old mark bitmap.
432   void UnBindBitmaps() REQUIRES(Locks::heap_bitmap_lock_);
433   // Swap the live and mark bitmaps of this space. This is used by the GC for concurrent sweeping.
434   void SwapBitmaps() REQUIRES(Locks::heap_bitmap_lock_);
435 
436   // Clear the space back to an empty space.
437   virtual void Clear() = 0;
438 
GetLiveBitmap()439   accounting::ContinuousSpaceBitmap* GetLiveBitmap() override {
440     return &live_bitmap_;
441   }
442 
GetMarkBitmap()443   accounting::ContinuousSpaceBitmap* GetMarkBitmap() override {
444     return &mark_bitmap_;
445   }
446 
GetTempBitmap()447   accounting::ContinuousSpaceBitmap* GetTempBitmap() {
448     return &temp_bitmap_;
449   }
450 
451   collector::ObjectBytePair Sweep(bool swap_bitmaps);
452   virtual accounting::ContinuousSpaceBitmap::SweepCallback* GetSweepCallback() = 0;
453 
454  protected:
455   accounting::ContinuousSpaceBitmap live_bitmap_;
456   accounting::ContinuousSpaceBitmap mark_bitmap_;
457   accounting::ContinuousSpaceBitmap temp_bitmap_;
458 
ContinuousMemMapAllocSpace(const std::string & name,MemMap && mem_map,uint8_t * begin,uint8_t * end,uint8_t * limit,GcRetentionPolicy gc_retention_policy)459   ContinuousMemMapAllocSpace(const std::string& name,
460                              MemMap&& mem_map,
461                              uint8_t* begin,
462                              uint8_t* end,
463                              uint8_t* limit,
464                              GcRetentionPolicy gc_retention_policy)
465       : MemMapSpace(name, std::move(mem_map), begin, end, limit, gc_retention_policy) {
466   }
467 
468  private:
469   friend class gc::Heap;
470   DISALLOW_IMPLICIT_CONSTRUCTORS(ContinuousMemMapAllocSpace);
471 };
472 
473 }  // namespace space
474 }  // namespace gc
475 }  // namespace art
476 
477 #endif  // ART_RUNTIME_GC_SPACE_SPACE_H_
478