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_SPACE_REGION_SPACE_H_
18 #define ART_RUNTIME_GC_SPACE_REGION_SPACE_H_
19 
20 #include "base/macros.h"
21 #include "base/mutex.h"
22 #include "space.h"
23 #include "thread.h"
24 
25 #include <functional>
26 #include <map>
27 
28 namespace art {
29 namespace gc {
30 
31 namespace accounting {
32 class ReadBarrierTable;
33 }  // namespace accounting
34 
35 namespace space {
36 
37 // Cyclic region allocation strategy. If `true`, region allocation
38 // will not try to allocate a new region from the beginning of the
39 // region space, but from the last allocated region. This allocation
40 // strategy reduces region reuse and should help catch some GC bugs
41 // earlier. However, cyclic region allocation can also create memory
42 // fragmentation at the region level (see b/33795328); therefore, we
43 // only enable it in debug mode.
44 static constexpr bool kCyclicRegionAllocation = kIsDebugBuild;
45 
46 // A space that consists of equal-sized regions.
47 class RegionSpace final : public ContinuousMemMapAllocSpace {
48  public:
49   typedef void(*WalkCallback)(void *start, void *end, size_t num_bytes, void* callback_arg);
50 
51   enum EvacMode {
52     kEvacModeNewlyAllocated,
53     kEvacModeLivePercentNewlyAllocated,
54     kEvacModeForceAll,
55   };
56 
GetType()57   SpaceType GetType() const override {
58     return kSpaceTypeRegionSpace;
59   }
60 
61   // Create a region space mem map with the requested sizes. The requested base address is not
62   // guaranteed to be granted, if it is required, the caller should call Begin on the returned
63   // space to confirm the request was granted.
64   static MemMap CreateMemMap(const std::string& name, size_t capacity, uint8_t* requested_begin);
65   static RegionSpace* Create(const std::string& name, MemMap&& mem_map, bool use_generational_cc);
66 
67   // Allocate `num_bytes`, returns null if the space is full.
68   mirror::Object* Alloc(Thread* self,
69                         size_t num_bytes,
70                         /* out */ size_t* bytes_allocated,
71                         /* out */ size_t* usable_size,
72                         /* out */ size_t* bytes_tl_bulk_allocated)
73       override REQUIRES(!region_lock_);
74   // Thread-unsafe allocation for when mutators are suspended, used by the semispace collector.
75   mirror::Object* AllocThreadUnsafe(Thread* self,
76                                     size_t num_bytes,
77                                     /* out */ size_t* bytes_allocated,
78                                     /* out */ size_t* usable_size,
79                                     /* out */ size_t* bytes_tl_bulk_allocated)
80       override REQUIRES(Locks::mutator_lock_) REQUIRES(!region_lock_);
81   // The main allocation routine.
82   template<bool kForEvac>
83   ALWAYS_INLINE mirror::Object* AllocNonvirtual(size_t num_bytes,
84                                                 /* out */ size_t* bytes_allocated,
85                                                 /* out */ size_t* usable_size,
86                                                 /* out */ size_t* bytes_tl_bulk_allocated)
87       REQUIRES(!region_lock_);
88   // Allocate/free large objects (objects that are larger than the region size).
89   template<bool kForEvac>
90   mirror::Object* AllocLarge(size_t num_bytes,
91                              /* out */ size_t* bytes_allocated,
92                              /* out */ size_t* usable_size,
93                              /* out */ size_t* bytes_tl_bulk_allocated) REQUIRES(!region_lock_);
94   template<bool kForEvac>
95   void FreeLarge(mirror::Object* large_obj, size_t bytes_allocated) REQUIRES(!region_lock_);
96 
97   // Return the storage space required by obj.
AllocationSize(mirror::Object * obj,size_t * usable_size)98   size_t AllocationSize(mirror::Object* obj, size_t* usable_size) override
99       REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(!region_lock_) {
100     return AllocationSizeNonvirtual(obj, usable_size);
101   }
102   size_t AllocationSizeNonvirtual(mirror::Object* obj, size_t* usable_size)
103       REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(!region_lock_);
104 
Free(Thread *,mirror::Object *)105   size_t Free(Thread*, mirror::Object*) override {
106     UNIMPLEMENTED(FATAL);
107     return 0;
108   }
FreeList(Thread *,size_t,mirror::Object **)109   size_t FreeList(Thread*, size_t, mirror::Object**) override {
110     UNIMPLEMENTED(FATAL);
111     return 0;
112   }
GetLiveBitmap()113   accounting::ContinuousSpaceBitmap* GetLiveBitmap() override {
114     return &mark_bitmap_;
115   }
GetMarkBitmap()116   accounting::ContinuousSpaceBitmap* GetMarkBitmap() override {
117     return &mark_bitmap_;
118   }
119 
120   void Clear() override REQUIRES(!region_lock_);
121 
122   // Remove read and write memory protection from the whole region space,
123   // i.e. make memory pages backing the region area not readable and not
124   // writable.
125   void Protect();
126 
127   // Remove memory protection from the whole region space, i.e. make memory
128   // pages backing the region area readable and writable. This method is useful
129   // to avoid page protection faults when dumping information about an invalid
130   // reference.
131   void Unprotect();
132 
133   // Change the non growth limit capacity to new capacity by shrinking or expanding the map.
134   // Currently, only shrinking is supported.
135   // Unlike implementations of this function in other spaces, we need to pass
136   // new capacity as argument here as region space doesn't have any notion of
137   // growth limit.
138   void ClampGrowthLimit(size_t new_capacity) REQUIRES(!region_lock_);
139 
140   void Dump(std::ostream& os) const override;
141   void DumpRegions(std::ostream& os) REQUIRES(!region_lock_);
142   // Dump region containing object `obj`. Precondition: `obj` is in the region space.
143   void DumpRegionForObject(std::ostream& os, mirror::Object* obj) REQUIRES(!region_lock_);
144   void DumpNonFreeRegions(std::ostream& os) REQUIRES(!region_lock_);
145 
146   size_t RevokeThreadLocalBuffers(Thread* thread) override REQUIRES(!region_lock_);
147   size_t RevokeThreadLocalBuffers(Thread* thread, const bool reuse) REQUIRES(!region_lock_);
148   size_t RevokeAllThreadLocalBuffers() override
149       REQUIRES(!Locks::runtime_shutdown_lock_, !Locks::thread_list_lock_, !region_lock_);
150   void AssertThreadLocalBuffersAreRevoked(Thread* thread) REQUIRES(!region_lock_);
151   void AssertAllThreadLocalBuffersAreRevoked()
152       REQUIRES(!Locks::runtime_shutdown_lock_, !Locks::thread_list_lock_, !region_lock_);
153 
154   enum class RegionType : uint8_t {
155     kRegionTypeAll,              // All types.
156     kRegionTypeFromSpace,        // From-space. To be evacuated.
157     kRegionTypeUnevacFromSpace,  // Unevacuated from-space. Not to be evacuated.
158     kRegionTypeToSpace,          // To-space.
159     kRegionTypeNone,             // None.
160   };
161 
162   enum class RegionState : uint8_t {
163     kRegionStateFree,            // Free region.
164     kRegionStateAllocated,       // Allocated region.
165     kRegionStateLarge,           // Large allocated (allocation larger than the region size).
166     kRegionStateLargeTail,       // Large tail (non-first regions of a large allocation).
167   };
168 
169   template<RegionType kRegionType> uint64_t GetBytesAllocatedInternal() REQUIRES(!region_lock_);
170   template<RegionType kRegionType> uint64_t GetObjectsAllocatedInternal() REQUIRES(!region_lock_);
GetBytesAllocated()171   uint64_t GetBytesAllocated() override REQUIRES(!region_lock_) {
172     return GetBytesAllocatedInternal<RegionType::kRegionTypeAll>();
173   }
GetObjectsAllocated()174   uint64_t GetObjectsAllocated() override REQUIRES(!region_lock_) {
175     return GetObjectsAllocatedInternal<RegionType::kRegionTypeAll>();
176   }
GetBytesAllocatedInFromSpace()177   uint64_t GetBytesAllocatedInFromSpace() REQUIRES(!region_lock_) {
178     return GetBytesAllocatedInternal<RegionType::kRegionTypeFromSpace>();
179   }
GetObjectsAllocatedInFromSpace()180   uint64_t GetObjectsAllocatedInFromSpace() REQUIRES(!region_lock_) {
181     return GetObjectsAllocatedInternal<RegionType::kRegionTypeFromSpace>();
182   }
GetBytesAllocatedInUnevacFromSpace()183   uint64_t GetBytesAllocatedInUnevacFromSpace() REQUIRES(!region_lock_) {
184     return GetBytesAllocatedInternal<RegionType::kRegionTypeUnevacFromSpace>();
185   }
GetObjectsAllocatedInUnevacFromSpace()186   uint64_t GetObjectsAllocatedInUnevacFromSpace() REQUIRES(!region_lock_) {
187     return GetObjectsAllocatedInternal<RegionType::kRegionTypeUnevacFromSpace>();
188   }
GetMaxPeakNumNonFreeRegions()189   size_t GetMaxPeakNumNonFreeRegions() const {
190     return max_peak_num_non_free_regions_;
191   }
GetNumRegions()192   size_t GetNumRegions() const {
193     return num_regions_;
194   }
GetNumNonFreeRegions()195   size_t GetNumNonFreeRegions() const NO_THREAD_SAFETY_ANALYSIS {
196     return num_non_free_regions_;
197   }
198 
CanMoveObjects()199   bool CanMoveObjects() const override {
200     return true;
201   }
202 
Contains(const mirror::Object * obj)203   bool Contains(const mirror::Object* obj) const override {
204     const uint8_t* byte_obj = reinterpret_cast<const uint8_t*>(obj);
205     return byte_obj >= Begin() && byte_obj < Limit();
206   }
207 
AsRegionSpace()208   RegionSpace* AsRegionSpace() override {
209     return this;
210   }
211 
212   // Go through all of the blocks and visit the continuous objects.
213   template <typename Visitor>
214   ALWAYS_INLINE void Walk(Visitor&& visitor) REQUIRES(Locks::mutator_lock_);
215   template <typename Visitor>
216   ALWAYS_INLINE void WalkToSpace(Visitor&& visitor) REQUIRES(Locks::mutator_lock_);
217 
218   // Scans regions and calls visitor for objects in unevac-space corresponding
219   // to the bits set in 'bitmap'.
220   // Cannot acquire region_lock_ as visitor may need to acquire it for allocation.
221   // Should not be called concurrently with functions (like SetFromSpace()) which
222   // change regions' type.
223   template <typename Visitor>
224   ALWAYS_INLINE void ScanUnevacFromSpace(accounting::ContinuousSpaceBitmap* bitmap,
225                                          Visitor&& visitor) NO_THREAD_SAFETY_ANALYSIS;
226 
GetSweepCallback()227   accounting::ContinuousSpaceBitmap::SweepCallback* GetSweepCallback() override {
228     return nullptr;
229   }
230   bool LogFragmentationAllocFailure(std::ostream& os, size_t failed_alloc_bytes) override
231       REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(!region_lock_);
232 
233   // Object alignment within the space.
234   static constexpr size_t kAlignment = kObjectAlignment;
235   // The region size.
236   static constexpr size_t kRegionSize = 256 * KB;
237 
IsInFromSpace(mirror::Object * ref)238   bool IsInFromSpace(mirror::Object* ref) {
239     if (HasAddress(ref)) {
240       Region* r = RefToRegionUnlocked(ref);
241       return r->IsInFromSpace();
242     }
243     return false;
244   }
245 
IsRegionNewlyAllocated(size_t idx)246   bool IsRegionNewlyAllocated(size_t idx) const NO_THREAD_SAFETY_ANALYSIS {
247     DCHECK_LT(idx, num_regions_);
248     return regions_[idx].IsNewlyAllocated();
249   }
250 
IsInNewlyAllocatedRegion(mirror::Object * ref)251   bool IsInNewlyAllocatedRegion(mirror::Object* ref) {
252     if (HasAddress(ref)) {
253       Region* r = RefToRegionUnlocked(ref);
254       return r->IsNewlyAllocated();
255     }
256     return false;
257   }
258 
IsInUnevacFromSpace(mirror::Object * ref)259   bool IsInUnevacFromSpace(mirror::Object* ref) {
260     if (HasAddress(ref)) {
261       Region* r = RefToRegionUnlocked(ref);
262       return r->IsInUnevacFromSpace();
263     }
264     return false;
265   }
266 
IsLargeObject(mirror::Object * ref)267   bool IsLargeObject(mirror::Object* ref) {
268     if (HasAddress(ref)) {
269       Region* r = RefToRegionUnlocked(ref);
270       return r->IsLarge();
271     }
272     return false;
273   }
274 
IsInToSpace(mirror::Object * ref)275   bool IsInToSpace(mirror::Object* ref) {
276     if (HasAddress(ref)) {
277       Region* r = RefToRegionUnlocked(ref);
278       return r->IsInToSpace();
279     }
280     return false;
281   }
282 
283   // If `ref` is in the region space, return the type of its region;
284   // otherwise, return `RegionType::kRegionTypeNone`.
GetRegionType(mirror::Object * ref)285   RegionType GetRegionType(mirror::Object* ref) {
286     if (HasAddress(ref)) {
287       return GetRegionTypeUnsafe(ref);
288     }
289     return RegionType::kRegionTypeNone;
290   }
291 
292   // Unsafe version of RegionSpace::GetRegionType.
293   // Precondition: `ref` is in the region space.
GetRegionTypeUnsafe(mirror::Object * ref)294   RegionType GetRegionTypeUnsafe(mirror::Object* ref) {
295     DCHECK(HasAddress(ref)) << ref;
296     Region* r = RefToRegionUnlocked(ref);
297     return r->Type();
298   }
299 
300   // Zero live bytes for a large object, used by young gen CC for marking newly allocated large
301   // objects.
302   void ZeroLiveBytesForLargeObject(mirror::Object* obj) REQUIRES_SHARED(Locks::mutator_lock_);
303 
304   // Determine which regions to evacuate and tag them as
305   // from-space. Tag the rest as unevacuated from-space.
306   void SetFromSpace(accounting::ReadBarrierTable* rb_table,
307                     EvacMode evac_mode,
308                     bool clear_live_bytes)
309       REQUIRES(!region_lock_);
310 
311   size_t FromSpaceSize() REQUIRES(!region_lock_);
312   size_t UnevacFromSpaceSize() REQUIRES(!region_lock_);
313   size_t ToSpaceSize() REQUIRES(!region_lock_);
314   void ClearFromSpace(/* out */ uint64_t* cleared_bytes,
315                       /* out */ uint64_t* cleared_objects,
316                       const bool clear_bitmap)
317       REQUIRES(!region_lock_);
318 
AddLiveBytes(mirror::Object * ref,size_t alloc_size)319   void AddLiveBytes(mirror::Object* ref, size_t alloc_size) {
320     Region* reg = RefToRegionUnlocked(ref);
321     reg->AddLiveBytes(alloc_size);
322   }
323 
AssertAllRegionLiveBytesZeroOrCleared()324   void AssertAllRegionLiveBytesZeroOrCleared() REQUIRES(!region_lock_) {
325     if (kIsDebugBuild) {
326       MutexLock mu(Thread::Current(), region_lock_);
327       for (size_t i = 0; i < num_regions_; ++i) {
328         Region* r = &regions_[i];
329         size_t live_bytes = r->LiveBytes();
330         CHECK(live_bytes == 0U || live_bytes == static_cast<size_t>(-1)) << live_bytes;
331       }
332     }
333   }
334 
SetAllRegionLiveBytesZero()335   void SetAllRegionLiveBytesZero() REQUIRES(!region_lock_) {
336     MutexLock mu(Thread::Current(), region_lock_);
337     const size_t iter_limit = kUseTableLookupReadBarrier
338         ? num_regions_
339         : std::min(num_regions_, non_free_region_index_limit_);
340     for (size_t i = 0; i < iter_limit; ++i) {
341       Region* r = &regions_[i];
342       // Newly allocated regions don't need up-to-date live_bytes_ for deciding
343       // whether to be evacuated or not. See Region::ShouldBeEvacuated().
344       if (!r->IsFree() && !r->IsNewlyAllocated()) {
345         r->ZeroLiveBytes();
346       }
347     }
348   }
349 
RegionIdxForRefUnchecked(mirror::Object * ref)350   size_t RegionIdxForRefUnchecked(mirror::Object* ref) const NO_THREAD_SAFETY_ANALYSIS {
351     DCHECK(HasAddress(ref));
352     uintptr_t offset = reinterpret_cast<uintptr_t>(ref) - reinterpret_cast<uintptr_t>(Begin());
353     size_t reg_idx = offset / kRegionSize;
354     DCHECK_LT(reg_idx, num_regions_);
355     Region* reg = &regions_[reg_idx];
356     DCHECK_EQ(reg->Idx(), reg_idx);
357     DCHECK(reg->Contains(ref));
358     return reg_idx;
359   }
360   // Return -1 as region index for references outside this region space.
RegionIdxForRef(mirror::Object * ref)361   size_t RegionIdxForRef(mirror::Object* ref) const NO_THREAD_SAFETY_ANALYSIS {
362     if (HasAddress(ref)) {
363       return RegionIdxForRefUnchecked(ref);
364     } else {
365       return static_cast<size_t>(-1);
366     }
367   }
368 
369   // Increment object allocation count for region containing ref.
370   void RecordAlloc(mirror::Object* ref) REQUIRES(!region_lock_);
371 
372   bool AllocNewTlab(Thread* self, const size_t tlab_size, size_t* bytes_tl_bulk_allocated)
373       REQUIRES(!region_lock_);
374 
Time()375   uint32_t Time() {
376     return time_;
377   }
378 
EvacBytes()379   size_t EvacBytes() const NO_THREAD_SAFETY_ANALYSIS {
380     return num_evac_regions_ * kRegionSize;
381   }
382 
GetMadviseTime()383   uint64_t GetMadviseTime() const {
384     return madvise_time_;
385   }
386 
387  private:
388   RegionSpace(const std::string& name, MemMap&& mem_map, bool use_generational_cc);
389 
390   class Region {
391    public:
Region()392     Region()
393         : idx_(static_cast<size_t>(-1)),
394           live_bytes_(static_cast<size_t>(-1)),
395           begin_(nullptr),
396           thread_(nullptr),
397           top_(nullptr),
398           end_(nullptr),
399           objects_allocated_(0),
400           alloc_time_(0),
401           is_newly_allocated_(false),
402           is_a_tlab_(false),
403           state_(RegionState::kRegionStateAllocated),
404           type_(RegionType::kRegionTypeToSpace) {}
405 
Init(size_t idx,uint8_t * begin,uint8_t * end)406     void Init(size_t idx, uint8_t* begin, uint8_t* end) {
407       idx_ = idx;
408       begin_ = begin;
409       top_.store(begin, std::memory_order_relaxed);
410       end_ = end;
411       state_ = RegionState::kRegionStateFree;
412       type_ = RegionType::kRegionTypeNone;
413       objects_allocated_.store(0, std::memory_order_relaxed);
414       alloc_time_ = 0;
415       live_bytes_ = static_cast<size_t>(-1);
416       is_newly_allocated_ = false;
417       is_a_tlab_ = false;
418       thread_ = nullptr;
419       DCHECK_LT(begin, end);
420       DCHECK_EQ(static_cast<size_t>(end - begin), kRegionSize);
421     }
422 
State()423     RegionState State() const {
424       return state_;
425     }
426 
Type()427     RegionType Type() const {
428       return type_;
429     }
430 
431     void Clear(bool zero_and_release_pages);
432 
433     ALWAYS_INLINE mirror::Object* Alloc(size_t num_bytes,
434                                         /* out */ size_t* bytes_allocated,
435                                         /* out */ size_t* usable_size,
436                                         /* out */ size_t* bytes_tl_bulk_allocated);
437 
IsFree()438     bool IsFree() const {
439       bool is_free = (state_ == RegionState::kRegionStateFree);
440       if (is_free) {
441         DCHECK(IsInNoSpace());
442         DCHECK_EQ(begin_, Top());
443         DCHECK_EQ(objects_allocated_.load(std::memory_order_relaxed), 0U);
444       }
445       return is_free;
446     }
447 
448     // Given a free region, declare it non-free (allocated).
449     void Unfree(RegionSpace* region_space, uint32_t alloc_time)
450         REQUIRES(region_space->region_lock_);
451 
452     // Given a free region, declare it non-free (allocated) and large.
453     void UnfreeLarge(RegionSpace* region_space, uint32_t alloc_time)
454         REQUIRES(region_space->region_lock_);
455 
456     // Given a free region, declare it non-free (allocated) and large tail.
457     void UnfreeLargeTail(RegionSpace* region_space, uint32_t alloc_time)
458         REQUIRES(region_space->region_lock_);
459 
460     void MarkAsAllocated(RegionSpace* region_space, uint32_t alloc_time)
461         REQUIRES(region_space->region_lock_);
462 
SetNewlyAllocated()463     void SetNewlyAllocated() {
464       is_newly_allocated_ = true;
465     }
466 
467     // Non-large, non-large-tail allocated.
IsAllocated()468     bool IsAllocated() const {
469       return state_ == RegionState::kRegionStateAllocated;
470     }
471 
472     // Large allocated.
IsLarge()473     bool IsLarge() const {
474       bool is_large = (state_ == RegionState::kRegionStateLarge);
475       if (is_large) {
476         DCHECK_LT(begin_ + kRegionSize, Top());
477       }
478       return is_large;
479     }
480 
ZeroLiveBytes()481     void ZeroLiveBytes() {
482       live_bytes_ = 0;
483     }
484 
485     // Large-tail allocated.
IsLargeTail()486     bool IsLargeTail() const {
487       bool is_large_tail = (state_ == RegionState::kRegionStateLargeTail);
488       if (is_large_tail) {
489         DCHECK_EQ(begin_, Top());
490       }
491       return is_large_tail;
492     }
493 
Idx()494     size_t Idx() const {
495       return idx_;
496     }
497 
IsNewlyAllocated()498     bool IsNewlyAllocated() const {
499       return is_newly_allocated_;
500     }
501 
IsTlab()502     bool IsTlab() const {
503       return is_a_tlab_;
504     }
505 
IsInFromSpace()506     bool IsInFromSpace() const {
507       return type_ == RegionType::kRegionTypeFromSpace;
508     }
509 
IsInToSpace()510     bool IsInToSpace() const {
511       return type_ == RegionType::kRegionTypeToSpace;
512     }
513 
IsInUnevacFromSpace()514     bool IsInUnevacFromSpace() const {
515       return type_ == RegionType::kRegionTypeUnevacFromSpace;
516     }
517 
IsInNoSpace()518     bool IsInNoSpace() const {
519       return type_ == RegionType::kRegionTypeNone;
520     }
521 
522     // Set this region as evacuated from-space. At the end of the
523     // collection, RegionSpace::ClearFromSpace will clear and reclaim
524     // the space used by this region, and tag it as unallocated/free.
SetAsFromSpace()525     void SetAsFromSpace() {
526       DCHECK(!IsFree() && IsInToSpace());
527       type_ = RegionType::kRegionTypeFromSpace;
528       if (IsNewlyAllocated()) {
529         // Clear the "newly allocated" status here, as we do not want the
530         // GC to see it when encountering references in the from-space.
531         //
532         // Invariant: There should be no newly-allocated region in the
533         // from-space (when the from-space exists, which is between the calls
534         // to RegionSpace::SetFromSpace and RegionSpace::ClearFromSpace).
535         is_newly_allocated_ = false;
536       }
537       // Set live bytes to an invalid value, as we have made an
538       // evacuation decision (possibly based on the percentage of live
539       // bytes).
540       live_bytes_ = static_cast<size_t>(-1);
541     }
542 
543     // Set this region as unevacuated from-space. At the end of the
544     // collection, RegionSpace::ClearFromSpace will preserve the space
545     // used by this region, and tag it as to-space (see
546     // Region::SetUnevacFromSpaceAsToSpace below).
547     void SetAsUnevacFromSpace(bool clear_live_bytes);
548 
549     // Set this region as to-space. Used by RegionSpace::ClearFromSpace.
550     // This is only valid if it is currently an unevac from-space region.
SetUnevacFromSpaceAsToSpace()551     void SetUnevacFromSpaceAsToSpace() {
552       DCHECK(!IsFree() && IsInUnevacFromSpace());
553       type_ = RegionType::kRegionTypeToSpace;
554     }
555 
556     // Return whether this region should be evacuated. Used by RegionSpace::SetFromSpace.
557     ALWAYS_INLINE bool ShouldBeEvacuated(EvacMode evac_mode);
558 
AddLiveBytes(size_t live_bytes)559     void AddLiveBytes(size_t live_bytes) {
560       DCHECK(GetUseGenerationalCC() || IsInUnevacFromSpace());
561       DCHECK(!IsLargeTail());
562       DCHECK_NE(live_bytes_, static_cast<size_t>(-1));
563       // For large allocations, we always consider all bytes in the regions live.
564       live_bytes_ += IsLarge() ? Top() - begin_ : live_bytes;
565       DCHECK_LE(live_bytes_, BytesAllocated());
566     }
567 
AllAllocatedBytesAreLive()568     bool AllAllocatedBytesAreLive() const {
569       return LiveBytes() == static_cast<size_t>(Top() - Begin());
570     }
571 
LiveBytes()572     size_t LiveBytes() const {
573       return live_bytes_;
574     }
575 
576     // Returns the number of allocated bytes.  "Bulk allocated" bytes in active TLABs are excluded.
577     size_t BytesAllocated() const;
578 
579     size_t ObjectsAllocated() const;
580 
Begin()581     uint8_t* Begin() const {
582       return begin_;
583     }
584 
Top()585     ALWAYS_INLINE uint8_t* Top() const {
586       return top_.load(std::memory_order_relaxed);
587     }
588 
SetTop(uint8_t * new_top)589     void SetTop(uint8_t* new_top) {
590       top_.store(new_top, std::memory_order_relaxed);
591     }
592 
End()593     uint8_t* End() const {
594       return end_;
595     }
596 
Contains(mirror::Object * ref)597     bool Contains(mirror::Object* ref) const {
598       return begin_ <= reinterpret_cast<uint8_t*>(ref) && reinterpret_cast<uint8_t*>(ref) < end_;
599     }
600 
601     void Dump(std::ostream& os) const;
602 
RecordThreadLocalAllocations(size_t num_objects,size_t num_bytes)603     void RecordThreadLocalAllocations(size_t num_objects, size_t num_bytes) {
604       DCHECK(IsAllocated());
605       DCHECK_EQ(Top(), end_);
606       objects_allocated_.fetch_add(num_objects, std::memory_order_relaxed);
607       top_.store(begin_ + num_bytes, std::memory_order_relaxed);
608       DCHECK_LE(Top(), end_);
609     }
610 
611     uint64_t GetLongestConsecutiveFreeBytes() const;
612 
613    private:
614     static bool GetUseGenerationalCC();
615 
616     size_t idx_;                        // The region's index in the region space.
617     size_t live_bytes_;                 // The live bytes. Used to compute the live percent.
618     uint8_t* begin_;                    // The begin address of the region.
619     Thread* thread_;                    // The owning thread if it's a tlab.
620     // Note that `top_` can be higher than `end_` in the case of a
621     // large region, where an allocated object spans multiple regions
622     // (large region + one or more large tail regions).
623     Atomic<uint8_t*> top_;              // The current position of the allocation.
624     uint8_t* end_;                      // The end address of the region.
625     // objects_allocated_ is accessed using memory_order_relaxed. Treat as approximate when there
626     // are concurrent updates.
627     Atomic<size_t> objects_allocated_;  // The number of objects allocated.
628     uint32_t alloc_time_;               // The allocation time of the region.
629     // Note that newly allocated and evacuated regions use -1 as
630     // special value for `live_bytes_`.
631     bool is_newly_allocated_;           // True if it's allocated after the last collection.
632     bool is_a_tlab_;                    // True if it's a tlab.
633     RegionState state_;                 // The region state (see RegionState).
634     RegionType type_;                   // The region type (see RegionType).
635 
636     friend class RegionSpace;
637   };
638 
639   template<bool kToSpaceOnly, typename Visitor>
640   ALWAYS_INLINE void WalkInternal(Visitor&& visitor) NO_THREAD_SAFETY_ANALYSIS;
641 
642   // Visitor will be iterating on objects in increasing address order.
643   template<typename Visitor>
644   ALWAYS_INLINE void WalkNonLargeRegion(Visitor&& visitor, const Region* r)
645       NO_THREAD_SAFETY_ANALYSIS;
646 
RefToRegion(mirror::Object * ref)647   Region* RefToRegion(mirror::Object* ref) REQUIRES(!region_lock_) {
648     MutexLock mu(Thread::Current(), region_lock_);
649     return RefToRegionLocked(ref);
650   }
651 
652   void TraceHeapSize() REQUIRES(region_lock_);
653 
RefToRegionUnlocked(mirror::Object * ref)654   Region* RefToRegionUnlocked(mirror::Object* ref) NO_THREAD_SAFETY_ANALYSIS {
655     // For a performance reason (this is frequently called via
656     // RegionSpace::IsInFromSpace, etc.) we avoid taking a lock here.
657     // Note that since we only change a region from to-space to (evac)
658     // from-space during a pause (in RegionSpace::SetFromSpace) and
659     // from (evac) from-space to free (after GC is done), as long as
660     // `ref` is a valid reference into an allocated region, it's safe
661     // to access the region state without the lock.
662     return RefToRegionLocked(ref);
663   }
664 
RefToRegionLocked(mirror::Object * ref)665   Region* RefToRegionLocked(mirror::Object* ref) REQUIRES(region_lock_) {
666     DCHECK(HasAddress(ref));
667     uintptr_t offset = reinterpret_cast<uintptr_t>(ref) - reinterpret_cast<uintptr_t>(Begin());
668     size_t reg_idx = offset / kRegionSize;
669     DCHECK_LT(reg_idx, num_regions_);
670     Region* reg = &regions_[reg_idx];
671     DCHECK_EQ(reg->Idx(), reg_idx);
672     DCHECK(reg->Contains(ref));
673     return reg;
674   }
675 
676   // Return the object location following `obj` in the region space
677   // (i.e., the object location at `obj + obj->SizeOf()`).
678   //
679   // Note that unless
680   // - the region containing `obj` is fully used; and
681   // - `obj` is not the last object of that region;
682   // the returned location is not guaranteed to be a valid object.
683   static mirror::Object* GetNextObject(mirror::Object* obj)
684       REQUIRES_SHARED(Locks::mutator_lock_);
685 
AdjustNonFreeRegionLimit(size_t new_non_free_region_index)686   void AdjustNonFreeRegionLimit(size_t new_non_free_region_index) REQUIRES(region_lock_) {
687     DCHECK_LT(new_non_free_region_index, num_regions_);
688     non_free_region_index_limit_ = std::max(non_free_region_index_limit_,
689                                             new_non_free_region_index + 1);
690     VerifyNonFreeRegionLimit();
691   }
692 
SetNonFreeRegionLimit(size_t new_non_free_region_index_limit)693   void SetNonFreeRegionLimit(size_t new_non_free_region_index_limit) REQUIRES(region_lock_) {
694     DCHECK_LE(new_non_free_region_index_limit, num_regions_);
695     non_free_region_index_limit_ = new_non_free_region_index_limit;
696     VerifyNonFreeRegionLimit();
697   }
698 
699   // Implementation of this invariant:
700   // for all `i >= non_free_region_index_limit_`, `regions_[i].IsFree()` is true.
VerifyNonFreeRegionLimit()701   void VerifyNonFreeRegionLimit() REQUIRES(region_lock_) {
702     if (kIsDebugBuild && non_free_region_index_limit_ < num_regions_) {
703       for (size_t i = non_free_region_index_limit_; i < num_regions_; ++i) {
704         CHECK(regions_[i].IsFree());
705       }
706     }
707   }
708 
709   Region* AllocateRegion(bool for_evac) REQUIRES(region_lock_);
710   void RevokeThreadLocalBuffersLocked(Thread* thread, bool reuse) REQUIRES(region_lock_);
711 
712   // Scan region range [`begin`, `end`) in increasing order to try to
713   // allocate a large region having a size of `num_regs_in_large_region`
714   // regions. If there is no space in the region space to allocate this
715   // large region, return null.
716   //
717   // If argument `next_region` is not null, use `*next_region` to
718   // return the index to the region next to the allocated large region
719   // returned by this method.
720   template<bool kForEvac>
721   mirror::Object* AllocLargeInRange(size_t begin,
722                                     size_t end,
723                                     size_t num_regs_in_large_region,
724                                     /* out */ size_t* bytes_allocated,
725                                     /* out */ size_t* usable_size,
726                                     /* out */ size_t* bytes_tl_bulk_allocated,
727                                     /* out */ size_t* next_region = nullptr) REQUIRES(region_lock_);
728 
729   // Check that the value of `r->LiveBytes()` matches the number of
730   // (allocated) bytes used by live objects according to the live bits
731   // in the region space bitmap range corresponding to region `r`.
732   void CheckLiveBytesAgainstRegionBitmap(Region* r);
733 
734   // Poison memory areas used by dead objects within unevacuated
735   // region `r`. This is meant to detect dangling references to dead
736   // objects earlier in debug mode.
737   void PoisonDeadObjectsInUnevacuatedRegion(Region* r);
738 
739   Mutex region_lock_ DEFAULT_MUTEX_ACQUIRED_AFTER;
740 
741   // Cached version of Heap::use_generational_cc_.
742   const bool use_generational_cc_;
743   uint32_t time_;                  // The time as the number of collections since the startup.
744   size_t num_regions_;             // The number of regions in this space.
745   uint64_t madvise_time_;          // The amount of time spent in madvise for purging pages.
746   // The number of non-free regions in this space.
747   size_t num_non_free_regions_ GUARDED_BY(region_lock_);
748 
749   // The number of evac regions allocated during collection. 0 when GC not running.
750   size_t num_evac_regions_ GUARDED_BY(region_lock_);
751 
752   // Maintain the maximum of number of non-free regions collected just before
753   // reclaim in each GC cycle. At this moment in cycle, highest number of
754   // regions are in non-free.
755   size_t max_peak_num_non_free_regions_;
756 
757   // The pointer to the region array.
758   std::unique_ptr<Region[]> regions_ GUARDED_BY(region_lock_);
759 
760   // To hold partially used TLABs which can be reassigned to threads later for
761   // utilizing the un-used portion.
762   std::multimap<size_t, Region*, std::greater<size_t>> partial_tlabs_ GUARDED_BY(region_lock_);
763   // The upper-bound index of the non-free regions. Used to avoid scanning all regions in
764   // RegionSpace::SetFromSpace and RegionSpace::ClearFromSpace.
765   //
766   // Invariant (verified by RegionSpace::VerifyNonFreeRegionLimit):
767   //   for all `i >= non_free_region_index_limit_`, `regions_[i].IsFree()` is true.
768   size_t non_free_region_index_limit_ GUARDED_BY(region_lock_);
769 
770   Region* current_region_;         // The region currently used for allocation.
771   Region* evac_region_;            // The region currently used for evacuation.
772   Region full_region_;             // The fake/sentinel region that looks full.
773 
774   // Index into the region array pointing to the starting region when
775   // trying to allocate a new region. Only used when
776   // `kCyclicRegionAllocation` is true.
777   size_t cyclic_alloc_region_index_ GUARDED_BY(region_lock_);
778 
779   // Mark bitmap used by the GC.
780   accounting::ContinuousSpaceBitmap mark_bitmap_;
781 
782   DISALLOW_COPY_AND_ASSIGN(RegionSpace);
783 };
784 
785 std::ostream& operator<<(std::ostream& os, RegionSpace::RegionState value);
786 std::ostream& operator<<(std::ostream& os, RegionSpace::RegionType value);
787 
788 }  // namespace space
789 }  // namespace gc
790 }  // namespace art
791 
792 #endif  // ART_RUNTIME_GC_SPACE_REGION_SPACE_H_
793