diff options
| -rw-r--r-- | runtime/gc/accounting/space_bitmap-inl.h | 2 | ||||
| -rw-r--r-- | runtime/gc/accounting/space_bitmap.cc | 11 | ||||
| -rw-r--r-- | runtime/gc/accounting/space_bitmap.h | 21 | ||||
| -rw-r--r-- | runtime/gc/accounting/space_bitmap_test.cc | 2 | ||||
| -rw-r--r-- | runtime/gc/collector/concurrent_copying-inl.h | 2 | ||||
| -rw-r--r-- | runtime/gc/collector/concurrent_copying.cc | 7 | ||||
| -rw-r--r-- | runtime/gc/collector/concurrent_copying.h | 15 | ||||
| -rw-r--r-- | runtime/gc/collector/mark_sweep.cc | 28 | ||||
| -rw-r--r-- | runtime/gc/heap.cc | 3 | ||||
| -rw-r--r-- | runtime/gc/heap.h | 4 | ||||
| -rw-r--r-- | runtime/gc/space/region_space-inl.h | 2 | ||||
| -rw-r--r-- | runtime/gc/space/region_space.cc | 49 | ||||
| -rw-r--r-- | runtime/gc/space/region_space.h | 47 | ||||
| -rw-r--r-- | runtime/gc/space/space.cc | 1 | ||||
| -rw-r--r-- | runtime/gc/space/space.h | 11 |
15 files changed, 168 insertions, 37 deletions
diff --git a/runtime/gc/accounting/space_bitmap-inl.h b/runtime/gc/accounting/space_bitmap-inl.h index a3fd1ba84a..354b9e1dbd 100644 --- a/runtime/gc/accounting/space_bitmap-inl.h +++ b/runtime/gc/accounting/space_bitmap-inl.h @@ -122,6 +122,7 @@ inline void SpaceBitmap<kAlignment>::VisitMarkedRange(uintptr_t visit_begin, uintptr_t w = bitmap_begin_[i].LoadRelaxed(); if (w != 0) { const uintptr_t ptr_base = IndexToOffset(i) + heap_begin_; + // Iterate on the bits set in word `w`, from the least to the most significant bit. do { const size_t shift = CTZ(w); mirror::Object* obj = reinterpret_cast<mirror::Object*>(ptr_base + shift * kAlignment); @@ -148,6 +149,7 @@ inline void SpaceBitmap<kAlignment>::VisitMarkedRange(uintptr_t visit_begin, right_edge &= ((static_cast<uintptr_t>(1) << bit_end) - 1); if (right_edge != 0) { const uintptr_t ptr_base = IndexToOffset(index_end) + heap_begin_; + // Iterate on the bits set in word `right_edge`, from the least to the most significant bit. do { const size_t shift = CTZ(right_edge); mirror::Object* obj = reinterpret_cast<mirror::Object*>(ptr_base + shift * kAlignment); diff --git a/runtime/gc/accounting/space_bitmap.cc b/runtime/gc/accounting/space_bitmap.cc index 237ee80ba0..0247564a8c 100644 --- a/runtime/gc/accounting/space_bitmap.cc +++ b/runtime/gc/accounting/space_bitmap.cc @@ -33,7 +33,12 @@ using android::base::StringPrintf; template<size_t kAlignment> size_t SpaceBitmap<kAlignment>::ComputeBitmapSize(uint64_t capacity) { + // Number of space (heap) bytes covered by one bitmap word. + // (Word size in bytes = `sizeof(intptr_t)`, which is expected to be + // 4 on a 32-bit architecture and 8 on a 64-bit one.) const uint64_t kBytesCoveredPerWord = kAlignment * kBitsPerIntPtrT; + // Calculate the number of words required to cover a space (heap) + // having a size of `capacity` bytes. return (RoundUp(capacity, kBytesCoveredPerWord) / kBytesCoveredPerWord) * sizeof(intptr_t); } @@ -74,7 +79,8 @@ SpaceBitmap<kAlignment>::~SpaceBitmap() {} template<size_t kAlignment> SpaceBitmap<kAlignment>* SpaceBitmap<kAlignment>::Create( const std::string& name, uint8_t* heap_begin, size_t heap_capacity) { - // Round up since heap_capacity is not necessarily a multiple of kAlignment * kBitsPerWord. + // Round up since `heap_capacity` is not necessarily a multiple of `kAlignment * kBitsPerIntPtrT` + // (we represent one word as an `intptr_t`). const size_t bitmap_size = ComputeBitmapSize(heap_capacity); std::string error_msg; std::unique_ptr<MemMap> mem_map(MemMap::MapAnonymous(name.c_str(), nullptr, bitmap_size, @@ -116,7 +122,7 @@ template<size_t kAlignment> void SpaceBitmap<kAlignment>::ClearRange(const mirror::Object* begin, const mirror::Object* end) { uintptr_t begin_offset = reinterpret_cast<uintptr_t>(begin) - heap_begin_; uintptr_t end_offset = reinterpret_cast<uintptr_t>(end) - heap_begin_; - // Align begin and end to word boundaries. + // Align begin and end to bitmap word boundaries. while (begin_offset < end_offset && OffsetBitIndex(begin_offset) != 0) { Clear(reinterpret_cast<mirror::Object*>(heap_begin_ + begin_offset)); begin_offset += kAlignment; @@ -125,6 +131,7 @@ void SpaceBitmap<kAlignment>::ClearRange(const mirror::Object* begin, const mirr end_offset -= kAlignment; Clear(reinterpret_cast<mirror::Object*>(heap_begin_ + end_offset)); } + // Bitmap word boundaries. const uintptr_t start_index = OffsetToIndex(begin_offset); const uintptr_t end_index = OffsetToIndex(end_offset); ZeroAndReleasePages(reinterpret_cast<uint8_t*>(&bitmap_begin_[start_index]), diff --git a/runtime/gc/accounting/space_bitmap.h b/runtime/gc/accounting/space_bitmap.h index 2f33bac902..437aecc2b1 100644 --- a/runtime/gc/accounting/space_bitmap.h +++ b/runtime/gc/accounting/space_bitmap.h @@ -55,6 +55,10 @@ class SpaceBitmap { ~SpaceBitmap(); + // Return the bitmap word index corresponding to memory offset (relative to + // `HeapBegin()`) `offset`. + // See also SpaceBitmap::OffsetBitIndex. + // // <offset> is the difference from .base to a pointer address. // <index> is the index of .bits that contains the bit representing // <offset>. @@ -62,24 +66,32 @@ class SpaceBitmap { return offset / kAlignment / kBitsPerIntPtrT; } + // Return the memory offset (relative to `HeapBegin()`) corresponding to + // bitmap word index `index`. template<typename T> static constexpr T IndexToOffset(T index) { return static_cast<T>(index * kAlignment * kBitsPerIntPtrT); } + // Return the bit within the bitmap word index corresponding to + // memory offset (relative to `HeapBegin()`) `offset`. + // See also SpaceBitmap::OffsetToIndex. ALWAYS_INLINE static constexpr uintptr_t OffsetBitIndex(uintptr_t offset) { return (offset / kAlignment) % kBitsPerIntPtrT; } + // Return the word-wide bit mask corresponding to `OffsetBitIndex(offset)`. // Bits are packed in the obvious way. static constexpr uintptr_t OffsetToMask(uintptr_t offset) { return static_cast<size_t>(1) << OffsetBitIndex(offset); } + // Set the bit corresponding to `obj` in the bitmap and return the previous value of that bit. bool Set(const mirror::Object* obj) ALWAYS_INLINE { return Modify<true>(obj); } + // Clear the bit corresponding to `obj` in the bitmap and return the previous value of that bit. bool Clear(const mirror::Object* obj) ALWAYS_INLINE { return Modify<false>(obj); } @@ -90,9 +102,14 @@ class SpaceBitmap { // Fill the bitmap with zeroes. Returns the bitmap's memory to the system as a side-effect. void Clear(); - // Clear a covered by the bitmap using madvise if possible. + // Clear a range covered by the bitmap using madvise if possible. void ClearRange(const mirror::Object* begin, const mirror::Object* end); + // Test whether `obj` is part of the bitmap (i.e. return whether the bit + // corresponding to `obj` has been set in the bitmap). + // + // Precondition: `obj` is within the range of pointers that this bitmap could + // potentially cover (i.e. `this->HasAddress(obj)` is true) bool Test(const mirror::Object* obj) const; // Return true iff <obj> is within the range of pointers that this bitmap could potentially cover, @@ -204,6 +221,8 @@ class SpaceBitmap { const void* heap_begin, size_t heap_capacity); + // Change the value of the bit corresponding to `obj` in the bitmap + // to `kSetBit` and return the previous value of that bit. template<bool kSetBit> bool Modify(const mirror::Object* obj); diff --git a/runtime/gc/accounting/space_bitmap_test.cc b/runtime/gc/accounting/space_bitmap_test.cc index bd5f77ebb1..1ca3fd6d12 100644 --- a/runtime/gc/accounting/space_bitmap_test.cc +++ b/runtime/gc/accounting/space_bitmap_test.cc @@ -74,7 +74,7 @@ TEST_F(SpaceBitmapTest, ScanRange) { } } // Try every possible starting bit in the first word. Then for each starting bit, try each - // possible length up to a maximum of kBitsPerWord * 2 - 1 bits. + // possible length up to a maximum of `kBitsPerIntPtrT * 2 - 1` bits. // This handles all the cases, having runs which start and end on the same word, and different // words. for (size_t i = 0; i < static_cast<size_t>(kBitsPerIntPtrT); ++i) { diff --git a/runtime/gc/collector/concurrent_copying-inl.h b/runtime/gc/collector/concurrent_copying-inl.h index 20e754554e..d739ed2867 100644 --- a/runtime/gc/collector/concurrent_copying-inl.h +++ b/runtime/gc/collector/concurrent_copying-inl.h @@ -134,6 +134,8 @@ inline mirror::Object* ConcurrentCopying::Mark(mirror::Object* from_ref, // It isn't marked yet. Mark it by copying it to the to-space. to_ref = Copy(from_ref, holder, offset); } + // The copy should either be in a to-space region, or in the + // non-moving space, if it could not fit in a to-space region. DCHECK(region_space_->IsInToSpace(to_ref) || heap_->non_moving_space_->HasAddress(to_ref)) << "from_ref=" << from_ref << " to_ref=" << to_ref; return to_ref; diff --git a/runtime/gc/collector/concurrent_copying.cc b/runtime/gc/collector/concurrent_copying.cc index 8bb36c98bd..3770085c07 100644 --- a/runtime/gc/collector/concurrent_copying.cc +++ b/runtime/gc/collector/concurrent_copying.cc @@ -1761,13 +1761,14 @@ void ConcurrentCopying::ReclaimPhase() { } CHECK_LE(to_objects, from_objects); CHECK_LE(to_bytes, from_bytes); - // cleared_bytes and cleared_objects may be greater than the from space equivalents since - // ClearFromSpace may clear empty unevac regions. + // Cleared bytes and objects, populated by the call to RegionSpace::ClearFromSpace below. uint64_t cleared_bytes; uint64_t cleared_objects; { TimingLogger::ScopedTiming split4("ClearFromSpace", GetTimings()); region_space_->ClearFromSpace(&cleared_bytes, &cleared_objects); + // `cleared_bytes` and `cleared_objects` may be greater than the from space equivalents since + // RegionSpace::ClearFromSpace may clear empty unevac regions. CHECK_GE(cleared_bytes, from_bytes); CHECK_GE(cleared_objects, from_objects); } @@ -2103,7 +2104,6 @@ class ConcurrentCopying::RefFieldsVisitor { ConcurrentCopying* const collector_; }; -// Scan ref fields of an object. inline void ConcurrentCopying::Scan(mirror::Object* to_ref) { if (kDisallowReadBarrierDuringScan && !Runtime::Current()->IsActiveTransaction()) { // Avoid all read barriers during visit references to help performance. @@ -2122,7 +2122,6 @@ inline void ConcurrentCopying::Scan(mirror::Object* to_ref) { } } -// Process a field. inline void ConcurrentCopying::Process(mirror::Object* obj, MemberOffset offset) { DCHECK_EQ(Thread::Current(), thread_running_gc_); mirror::Object* ref = obj->GetFieldObject< diff --git a/runtime/gc/collector/concurrent_copying.h b/runtime/gc/collector/concurrent_copying.h index 42d37d8395..c58dd44648 100644 --- a/runtime/gc/collector/concurrent_copying.h +++ b/runtime/gc/collector/concurrent_copying.h @@ -111,6 +111,7 @@ class ConcurrentCopying : public GarbageCollector { return IsMarked(ref) == ref; } template<bool kGrayImmuneObject = true, bool kFromGCThread = false> + // Mark object `from_ref`, copying it to the to-space if needed. ALWAYS_INLINE mirror::Object* Mark(mirror::Object* from_ref, mirror::Object* holder = nullptr, MemberOffset offset = MemberOffset(0)) @@ -150,8 +151,10 @@ class ConcurrentCopying : public GarbageCollector { MemberOffset offset) REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(!mark_stack_lock_, !skipped_blocks_lock_, !immune_gray_stack_lock_); + // Scan the reference fields of object `to_ref`. void Scan(mirror::Object* to_ref) REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(!mark_stack_lock_); + // Process a field. void Process(mirror::Object* obj, MemberOffset offset) REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(!mark_stack_lock_ , !skipped_blocks_lock_, !immune_gray_stack_lock_); @@ -278,8 +281,20 @@ class ConcurrentCopying : public GarbageCollector { space::RegionSpace* region_space_; // The underlying region space. std::unique_ptr<Barrier> gc_barrier_; std::unique_ptr<accounting::ObjectStack> gc_mark_stack_; + + // The read-barrier mark-bit stack. Stores object references whose + // mark bit has been set by ConcurrentCopying::MarkFromReadBarrier, + // so that this bit can be reset at the end of the collection in + // ConcurrentCopying::FinishPhase. The mark bit of an object can be + // used by mutator read barrier code to quickly test whether that + // object has been already marked. std::unique_ptr<accounting::ObjectStack> rb_mark_bit_stack_; + // Thread-unsafe Boolean value hinting that `rb_mark_bit_stack_` is + // full. A thread-safe test of whether the read-barrier mark-bit + // stack is full is implemented by `rb_mark_bit_stack_->AtomicPushBack(ref)` + // (see use case in ConcurrentCopying::MarkFromReadBarrier). bool rb_mark_bit_stack_full_; + std::vector<mirror::Object*> false_gray_stack_ GUARDED_BY(mark_stack_lock_); Mutex mark_stack_lock_ DEFAULT_MUTEX_ACQUIRED_AFTER; std::vector<accounting::ObjectStack*> revoked_mark_stacks_ diff --git a/runtime/gc/collector/mark_sweep.cc b/runtime/gc/collector/mark_sweep.cc index 74ee2d1d74..9ab965ec78 100644 --- a/runtime/gc/collector/mark_sweep.cc +++ b/runtime/gc/collector/mark_sweep.cc @@ -191,7 +191,7 @@ void MarkSweep::PausePhase() { WriterMutexLock mu(self, *Locks::heap_bitmap_lock_); // Re-mark root set. ReMarkRoots(); - // Scan dirty objects, this is only required if we are not doing concurrent GC. + // Scan dirty objects, this is only required if we are doing concurrent GC. RecursiveMarkDirtyObjects(true, accounting::CardTable::kCardDirty); } { @@ -259,8 +259,30 @@ void MarkSweep::MarkingPhase() { BindBitmaps(); FindDefaultSpaceBitmap(); // Process dirty cards and add dirty cards to mod union tables. - // If the GC type is non sticky, then we just clear the cards instead of ageing them. - heap_->ProcessCards(GetTimings(), false, true, GetGcType() != kGcTypeSticky); + // If the GC type is non sticky, then we just clear the cards of the + // alloc space instead of aging them. + // + // Note that it is fine to clear the cards of the alloc space here, + // in the case of a concurrent (non-sticky) mark-sweep GC (whose + // marking phase _is_ performed concurrently with mutator threads + // running and possibly dirtying cards), as the whole alloc space + // will be traced in that case, starting *after* this call to + // Heap::ProcessCards (see calls to MarkSweep::MarkRoots and + // MarkSweep::MarkReachableObjects). References held by objects on + // cards that became dirty *after* the actual marking work started + // will be marked in the pause (see MarkSweep::PausePhase), in a + // *non-concurrent* way to prevent races with mutator threads. + // + // TODO: Do we need some sort of fence between the call to + // Heap::ProcessCard and the calls to MarkSweep::MarkRoot / + // MarkSweep::MarkReachableObjects below to make sure write + // operations in the card table clearing the alloc space's dirty + // cards (during the call to Heap::ProcessCard) are not reordered + // *after* marking actually starts? + heap_->ProcessCards(GetTimings(), + /* use_rem_sets */ false, + /* process_alloc_space_cards */ true, + /* clear_alloc_space_cards */ GetGcType() != kGcTypeSticky); WriterMutexLock mu(self, *Locks::heap_bitmap_lock_); MarkRoots(self); MarkReachableObjects(); diff --git a/runtime/gc/heap.cc b/runtime/gc/heap.cc index d8d215bf76..17913fc2dc 100644 --- a/runtime/gc/heap.cc +++ b/runtime/gc/heap.cc @@ -434,6 +434,7 @@ Heap::Heap(size_t initial_size, // Create other spaces based on whether or not we have a moving GC. if (foreground_collector_type_ == kCollectorTypeCC) { CHECK(separate_non_moving_space); + // Reserve twice the capacity, to allow evacuating every region for explicit GCs. MemMap* region_space_mem_map = space::RegionSpace::CreateMemMap(kRegionSpaceName, capacity_ * 2, request_begin); @@ -517,7 +518,7 @@ Heap::Heap(size_t initial_size, // Since we don't know where in the low_4gb the app image will be located, make the card table // cover the whole low_4gb. TODO: Extend the card table in AddSpace. UNUSED(heap_capacity); - // Start at 64 KB, we can be sure there are no spaces mapped this low since the address range is + // Start at 4 KB, we can be sure there are no spaces mapped this low since the address range is // reserved by the kernel. static constexpr size_t kMinHeapAddress = 4 * KB; card_table_.reset(accounting::CardTable::Create(reinterpret_cast<uint8_t*>(kMinHeapAddress), diff --git a/runtime/gc/heap.h b/runtime/gc/heap.h index 9f84d6dd03..7fb634fcf7 100644 --- a/runtime/gc/heap.h +++ b/runtime/gc/heap.h @@ -1293,8 +1293,9 @@ class Heap { // Parallel GC data structures. std::unique_ptr<ThreadPool> thread_pool_; - // For a GC cycle, a bitmap that is set corresponding to the + // A bitmap that is set corresponding to the known live objects since the last GC cycle. std::unique_ptr<accounting::HeapBitmap> live_bitmap_ GUARDED_BY(Locks::heap_bitmap_lock_); + // A bitmap that is set corresponding to the marked objects in the current GC cycle. std::unique_ptr<accounting::HeapBitmap> mark_bitmap_ GUARDED_BY(Locks::heap_bitmap_lock_); // Mark stack that we reuse to avoid re-allocating the mark stack. @@ -1320,6 +1321,7 @@ class Heap { // Temp space is the space which the semispace collector copies to. space::BumpPointerSpace* temp_space_; + // Region space, used by the concurrent collector. space::RegionSpace* region_space_; // Minimum free guarantees that you always have at least min_free_ free bytes after growing for diff --git a/runtime/gc/space/region_space-inl.h b/runtime/gc/space/region_space-inl.h index 305f0bca0a..410931cbe5 100644 --- a/runtime/gc/space/region_space-inl.h +++ b/runtime/gc/space/region_space-inl.h @@ -258,7 +258,7 @@ inline mirror::Object* RegionSpace::AllocLarge(size_t num_bytes, return nullptr; } } - // Find a large enough contiguous free regions. + // Find a large enough set of contiguous free regions. size_t left = 0; while (left + num_regs - 1 < num_regions_) { bool found = true; diff --git a/runtime/gc/space/region_space.cc b/runtime/gc/space/region_space.cc index 8f9f1a91b0..8d94c86701 100644 --- a/runtime/gc/space/region_space.cc +++ b/runtime/gc/space/region_space.cc @@ -158,9 +158,9 @@ size_t RegionSpace::ToSpaceSize() { inline bool RegionSpace::Region::ShouldBeEvacuated() { DCHECK((IsAllocated() || IsLarge()) && IsInToSpace()); - // if the region was allocated after the start of the - // previous GC or the live ratio is below threshold, evacuate - // it. + // The region should be evacuated if: + // - the region was allocated after the start of the previous GC (newly allocated region); or + // - the live ratio is below threshold (`kEvacuateLivePercentThreshold`). bool result; if (is_newly_allocated_) { result = true; @@ -198,7 +198,10 @@ void RegionSpace::SetFromSpace(accounting::ReadBarrierTable* rb_table, bool forc rb_table->SetAll(); } MutexLock mu(Thread::Current(), region_lock_); - size_t num_expected_large_tails = 0; + // Counter for the number of expected large tail regions following a large region. + size_t num_expected_large_tails = 0U; + // Flag to store whether the previously seen large region has been evacuated. + // This is used to apply the same evacuation policy to related large tail regions. bool prev_large_evacuated = false; VerifyNonFreeRegionLimit(); const size_t iter_limit = kUseTableLookupReadBarrier @@ -273,18 +276,32 @@ void RegionSpace::ClearFromSpace(/* out */ uint64_t* cleared_bytes, // Update max of peak non free region count before reclaiming evacuated regions. max_peak_num_non_free_regions_ = std::max(max_peak_num_non_free_regions_, num_non_free_regions_); - // Combine zeroing and releasing pages to reduce how often madvise is called. This helps - // reduce contention on the mmap semaphore. b/62194020 - // clear_region adds a region to the current block. If the region is not adjacent, the - // clear block is zeroed, released, and a new block begins. + + // Lambda expression `clear_region` clears a region and adds a region to the + // "clear block". + // + // As we sweep regions to clear them, we maintain a "clear block", composed of + // adjacent cleared regions and whose bounds are `clear_block_begin` and + // `clear_block_end`. When processing a new region which is not adjacent to + // the clear block (discontinuity in cleared regions), the clear block + // is zeroed and released and the clear block is reset (to the most recent + // cleared region). + // + // This is done in order to combine zeroing and releasing pages to reduce how + // often madvise is called. This helps reduce contention on the mmap semaphore + // (see b/62194020). uint8_t* clear_block_begin = nullptr; uint8_t* clear_block_end = nullptr; auto clear_region = [&clear_block_begin, &clear_block_end](Region* r) { r->Clear(/*zero_and_release_pages*/false); if (clear_block_end != r->Begin()) { + // Region `r` is not adjacent to the current clear block; zero and release + // pages within the current block and restart a new clear block at the + // beginning of region `r`. ZeroAndProtectRegion(clear_block_begin, clear_block_end); clear_block_begin = r->Begin(); } + // Add region `r` to the clear block. clear_block_end = r->End(); }; for (size_t i = 0; i < std::min(num_regions_, non_free_region_index_limit_); ++i) { @@ -335,12 +352,22 @@ void RegionSpace::ClearFromSpace(/* out */ uint64_t* cleared_bytes, ++regions_to_clear_bitmap; } + // Optimization: If the live bytes are *all* live in a region + // then the live-bit information for these objects is superfluous: + // - We can determine that these objects are all live by using + // Region::AllAllocatedBytesAreLive (which just checks whether + // `LiveBytes() == static_cast<size_t>(Top() - Begin())`. + // - We can visit the objects in this region using + // RegionSpace::GetNextObject, i.e. without resorting to the + // live bits (see RegionSpace::WalkInternal). + // Therefore, we can clear the bits for these objects in the + // (live) region space bitmap (and release the corresponding pages). GetLiveBitmap()->ClearRange( reinterpret_cast<mirror::Object*>(r->Begin()), reinterpret_cast<mirror::Object*>(r->Begin() + regions_to_clear_bitmap * kRegionSize)); - // Skip over extra regions we cleared the bitmaps: we don't need to clear them, as they - // are unevac region sthat are live. - // Subtract one for the for loop. + // Skip over extra regions for which we cleared the bitmaps: we shall not clear them, + // as they are unevac regions that are live. + // Subtract one for the for-loop. i += regions_to_clear_bitmap - 1; } } diff --git a/runtime/gc/space/region_space.h b/runtime/gc/space/region_space.h index d026ffd803..c3b7ff72ef 100644 --- a/runtime/gc/space/region_space.h +++ b/runtime/gc/space/region_space.h @@ -239,6 +239,8 @@ class RegionSpace FINAL : public ContinuousMemMapAllocSpace { return RegionType::kRegionTypeNone; } + // Determine which regions to evacuate and tag them as + // from-space. Tag the rest as unevacuated from-space. void SetFromSpace(accounting::ReadBarrierTable* rb_table, bool force_evacuate_all) REQUIRES(!region_lock_); @@ -332,9 +334,11 @@ class RegionSpace FINAL : public ContinuousMemMapAllocSpace { void Unfree(RegionSpace* region_space, uint32_t alloc_time) REQUIRES(region_space->region_lock_); + // Given a free region, declare it non-free (allocated) and large. void UnfreeLarge(RegionSpace* region_space, uint32_t alloc_time) REQUIRES(region_space->region_lock_); + // Given a free region, declare it non-free (allocated) and large tail. void UnfreeLargeTail(RegionSpace* region_space, uint32_t alloc_time) REQUIRES(region_space->region_lock_); @@ -392,23 +396,33 @@ class RegionSpace FINAL : public ContinuousMemMapAllocSpace { return type_ == RegionType::kRegionTypeNone; } + // Set this region as evacuated from-space. At the end of the + // collection, RegionSpace::ClearFromSpace will clear and reclaim + // the space used by this region, and tag it as unallocated/free. void SetAsFromSpace() { DCHECK(!IsFree() && IsInToSpace()); type_ = RegionType::kRegionTypeFromSpace; live_bytes_ = static_cast<size_t>(-1); } + // Set this region as unevacuated from-space. At the end of the + // collection, RegionSpace::ClearFromSpace will preserve the space + // used by this region, and tag it as to-space (see + // Region::SetUnevacFromSpaceAsToSpace below). void SetAsUnevacFromSpace() { DCHECK(!IsFree() && IsInToSpace()); type_ = RegionType::kRegionTypeUnevacFromSpace; live_bytes_ = 0U; } + // Set this region as to-space. Used by RegionSpace::ClearFromSpace. + // This is only valid if it is currently an unevac from-space region. void SetUnevacFromSpaceAsToSpace() { DCHECK(!IsFree() && IsInUnevacFromSpace()); type_ = RegionType::kRegionTypeToSpace; } + // Return whether this region should be evacuated. Used by RegionSpace::SetFromSpace. ALWAYS_INLINE bool ShouldBeEvacuated(); void AddLiveBytes(size_t live_bytes) { @@ -467,12 +481,17 @@ class RegionSpace FINAL : public ContinuousMemMapAllocSpace { private: size_t idx_; // The region's index in the region space. uint8_t* begin_; // The begin address of the region. + // Note that `top_` can be higher than `end_` in the case of a + // large region, where an allocated object spans multiple regions + // (large region + one or more large tail regions). Atomic<uint8_t*> top_; // The current position of the allocation. uint8_t* end_; // The end address of the region. RegionState state_; // The region state (see RegionState). RegionType type_; // The region type (see RegionType). Atomic<size_t> objects_allocated_; // The number of objects allocated. uint32_t alloc_time_; // The allocation time of the region. + // Note that newly allocated and evacuated regions use -1 as + // special value for `live_bytes_`. size_t live_bytes_; // The live bytes. Used to compute the live percent. bool is_newly_allocated_; // True if it's allocated after the last collection. bool is_a_tlab_; // True if it's a tlab. @@ -488,12 +507,12 @@ class RegionSpace FINAL : public ContinuousMemMapAllocSpace { Region* RefToRegionUnlocked(mirror::Object* ref) NO_THREAD_SAFETY_ANALYSIS { // For a performance reason (this is frequently called via - // IsInFromSpace() etc.) we avoid taking a lock here. Note that - // since we only change a region from to-space to from-space only - // during a pause (SetFromSpace()) and from from-space to free - // (after GC is done) as long as ref is a valid reference into an - // allocated region, it's safe to access the region state without - // the lock. + // RegionSpace::IsInFromSpace, etc.) we avoid taking a lock here. + // Note that since we only change a region from to-space to (evac) + // from-space during a pause (in RegionSpace::SetFromSpace) and + // from (evac) from-space to free (after GC is done), as long as + // `ref` is a valid reference into an allocated region, it's safe + // to access the region state without the lock. return RefToRegionLocked(ref); } @@ -508,6 +527,13 @@ class RegionSpace FINAL : public ContinuousMemMapAllocSpace { return reg; } + // Return the object location following `obj` in the region space + // (i.e., the object location at `obj + obj->SizeOf()`). + // + // Note that + // - unless the region containing `obj` is fully used; and + // - `obj` is not the last object of that region; + // the returned location is not guaranteed to be a valid object. mirror::Object* GetNextObject(mirror::Object* obj) REQUIRES_SHARED(Locks::mutator_lock_); @@ -524,6 +550,8 @@ class RegionSpace FINAL : public ContinuousMemMapAllocSpace { VerifyNonFreeRegionLimit(); } + // Implementation of this invariant: + // for all `i >= non_free_region_index_limit_`, `regions_[i].IsFree()` is true. void VerifyNonFreeRegionLimit() REQUIRES(region_lock_) { if (kIsDebugBuild && non_free_region_index_limit_ < num_regions_) { for (size_t i = non_free_region_index_limit_; i < num_regions_; ++i) { @@ -549,8 +577,8 @@ class RegionSpace FINAL : public ContinuousMemMapAllocSpace { // regions are in non-free. size_t max_peak_num_non_free_regions_; + // The pointer to the region array. std::unique_ptr<Region[]> regions_ GUARDED_BY(region_lock_); - // The pointer to the region array. // The upper-bound index of the non-free regions. Used to avoid scanning all regions in // RegionSpace::SetFromSpace and RegionSpace::ClearFromSpace. @@ -558,8 +586,9 @@ class RegionSpace FINAL : public ContinuousMemMapAllocSpace { // Invariant (verified by RegionSpace::VerifyNonFreeRegionLimit): // for all `i >= non_free_region_index_limit_`, `regions_[i].IsFree()` is true. size_t non_free_region_index_limit_ GUARDED_BY(region_lock_); - Region* current_region_; // The region that's being currently allocated. - Region* evac_region_; // The region that's being currently evacuated to. + + Region* current_region_; // The region currently used for allocation. + Region* evac_region_; // The region currently used for evacuation. Region full_region_; // The dummy/sentinel region that looks full. // Mark bitmap used by the GC. diff --git a/runtime/gc/space/space.cc b/runtime/gc/space/space.cc index 82f9905683..a8bd7b816e 100644 --- a/runtime/gc/space/space.cc +++ b/runtime/gc/space/space.cc @@ -107,7 +107,6 @@ collector::ObjectBytePair ContinuousMemMapAllocSpace::Sweep(bool swap_bitmaps) { return scc.freed; } -// Returns the old mark bitmap. void ContinuousMemMapAllocSpace::BindLiveToMarkBitmap() { CHECK(!HasBoundBitmaps()); accounting::ContinuousSpaceBitmap* live_bitmap = GetLiveBitmap(); diff --git a/runtime/gc/space/space.h b/runtime/gc/space/space.h index 964824abd5..12bccb35e7 100644 --- a/runtime/gc/space/space.h +++ b/runtime/gc/space/space.h @@ -389,8 +389,12 @@ class MemMapSpace : public ContinuousSpace { } protected: - MemMapSpace(const std::string& name, MemMap* mem_map, uint8_t* begin, uint8_t* end, - uint8_t* limit, GcRetentionPolicy gc_retention_policy) + MemMapSpace(const std::string& name, + MemMap* mem_map, + uint8_t* begin, + uint8_t* end, + uint8_t* limit, + GcRetentionPolicy gc_retention_policy) : ContinuousSpace(name, gc_retention_policy, begin, end, limit), mem_map_(mem_map) { } @@ -420,7 +424,10 @@ class ContinuousMemMapAllocSpace : public MemMapSpace, public AllocSpace { } bool HasBoundBitmaps() const REQUIRES(Locks::heap_bitmap_lock_); + // Make the mark bitmap an alias of the live bitmap. Save the current mark bitmap into + // `temp_bitmap_`, so that we can restore it later in ContinuousMemMapAllocSpace::UnBindBitmaps. void BindLiveToMarkBitmap() REQUIRES(Locks::heap_bitmap_lock_); + // Unalias the mark bitmap from the live bitmap and restore the old mark bitmap. void UnBindBitmaps() REQUIRES(Locks::heap_bitmap_lock_); // Swap the live and mark bitmaps of this space. This is used by the GC for concurrent sweeping. void SwapBitmaps(); |