Revert "Remove skipped blocks reuse mechanism"
This reverts commit dbb57f3f8e3bc895ddc0dd1cd80cfa16bb1283db.
Reason for revert: Seems to cause 004-ThreadStress failure?
Change-Id: I4b40084c82d90cf8b7578f8aa681fba0d7756e1e
diff --git a/runtime/gc/collector/concurrent_copying.cc b/runtime/gc/collector/concurrent_copying.cc
index 7605af5..81bc445 100644
--- a/runtime/gc/collector/concurrent_copying.cc
+++ b/runtime/gc/collector/concurrent_copying.cc
@@ -104,6 +104,7 @@
region_space_inter_region_bitmap_(nullptr),
non_moving_space_inter_region_bitmap_(nullptr),
reclaimed_bytes_ratio_sum_(0.f),
+ skipped_blocks_lock_("concurrent copying bytes blocks lock", kMarkSweepMarkStackLock),
measure_read_barrier_slow_path_(measure_read_barrier_slow_path),
mark_from_read_barrier_measurements_(false),
rb_slow_path_ns_(0),
@@ -377,8 +378,6 @@
<< reinterpret_cast<void*>(region_space_->Limit());
}
CheckEmptyMarkStack();
- // currently_marking_ mght still contain an obsolete value.
- currently_copying_.store(nullptr, std::memory_order_relaxed);
rb_mark_bit_stack_full_ = false;
mark_from_read_barrier_measurements_ = measure_read_barrier_slow_path_;
if (measure_read_barrier_slow_path_) {
@@ -3250,6 +3249,65 @@
}
}
+// Reuse the memory blocks that were copy of objects that were lost in race.
+mirror::Object* ConcurrentCopying::AllocateInSkippedBlock(Thread* const self, size_t alloc_size) {
+ // Try to reuse the blocks that were unused due to CAS failures.
+ CHECK_ALIGNED(alloc_size, space::RegionSpace::kAlignment);
+ size_t min_object_size = RoundUp(sizeof(mirror::Object), space::RegionSpace::kAlignment);
+ size_t byte_size;
+ uint8_t* addr;
+ {
+ MutexLock mu(self, skipped_blocks_lock_);
+ auto it = skipped_blocks_map_.lower_bound(alloc_size);
+ if (it == skipped_blocks_map_.end()) {
+ // Not found.
+ return nullptr;
+ }
+ byte_size = it->first;
+ CHECK_GE(byte_size, alloc_size);
+ if (byte_size > alloc_size && byte_size - alloc_size < min_object_size) {
+ // If remainder would be too small for a dummy object, retry with a larger request size.
+ it = skipped_blocks_map_.lower_bound(alloc_size + min_object_size);
+ if (it == skipped_blocks_map_.end()) {
+ // Not found.
+ return nullptr;
+ }
+ CHECK_ALIGNED(it->first - alloc_size, space::RegionSpace::kAlignment);
+ CHECK_GE(it->first - alloc_size, min_object_size)
+ << "byte_size=" << byte_size << " it->first=" << it->first << " alloc_size=" << alloc_size;
+ }
+ // Found a block.
+ CHECK(it != skipped_blocks_map_.end());
+ byte_size = it->first;
+ addr = it->second;
+ CHECK_GE(byte_size, alloc_size);
+ CHECK(region_space_->IsInToSpace(reinterpret_cast<mirror::Object*>(addr)));
+ CHECK_ALIGNED(byte_size, space::RegionSpace::kAlignment);
+ if (kVerboseMode) {
+ LOG(INFO) << "Reusing skipped bytes : " << reinterpret_cast<void*>(addr) << ", " << byte_size;
+ }
+ skipped_blocks_map_.erase(it);
+ }
+ memset(addr, 0, byte_size);
+ if (byte_size > alloc_size) {
+ // Return the remainder to the map.
+ CHECK_ALIGNED(byte_size - alloc_size, space::RegionSpace::kAlignment);
+ CHECK_GE(byte_size - alloc_size, min_object_size);
+ // FillWithDummyObject may mark an object, avoid holding skipped_blocks_lock_ to prevent lock
+ // violation and possible deadlock. The deadlock case is a recursive case:
+ // FillWithDummyObject -> Mark(IntArray.class) -> Copy -> AllocateInSkippedBlock.
+ FillWithDummyObject(self,
+ reinterpret_cast<mirror::Object*>(addr + alloc_size),
+ byte_size - alloc_size);
+ CHECK(region_space_->IsInToSpace(reinterpret_cast<mirror::Object*>(addr + alloc_size)));
+ {
+ MutexLock mu(self, skipped_blocks_lock_);
+ skipped_blocks_map_.insert(std::make_pair(byte_size - alloc_size, addr + alloc_size));
+ }
+ }
+ return reinterpret_cast<mirror::Object*>(addr);
+}
+
mirror::Object* ConcurrentCopying::Copy(Thread* const self,
mirror::Object* from_ref,
mirror::Object* holder,
@@ -3267,27 +3325,6 @@
// Note that from_ref is a from space ref so the SizeOf() call will access the from-space meta
// objects, but it's ok and necessary.
size_t obj_size = from_ref->SizeOf<kDefaultVerifyFlags>();
- mirror::Object* old_currently_copying = nullptr;
- if (obj_size >= kCurrentlyCopyingMin) {
- old_currently_copying = currently_copying_.exchange(from_ref, std::memory_order_relaxed);
- if (old_currently_copying == from_ref) {
- VLOG(gc) << "GC: Waiting for another thread to copy, size = " << obj_size;
- // Somebody is already working on the copy. Just wait.
- LockWord old_lock_word(LockWord::Default());
- do {
- if (UNLIKELY(obj_size >= 1'000'000)) {
- // The copy will take on the order of a millisecond or longer.
- usleep(1'000);
- } else {
- sched_yield();
- }
- old_lock_word = from_ref->GetLockWord(false);
- } while (old_lock_word.GetState() != LockWord::kForwardingAddress);
- mirror::Object* to_ref = reinterpret_cast<mirror::Object*>(old_lock_word.ForwardingAddress());
- DCHECK(to_ref != nullptr);
- return to_ref;
- }
- }
size_t region_space_alloc_size = (obj_size <= space::RegionSpace::kRegionSize)
? RoundUp(obj_size, space::RegionSpace::kAlignment)
: RoundUp(obj_size, space::RegionSpace::kRegionSize);
@@ -3295,27 +3332,44 @@
size_t non_moving_space_bytes_allocated = 0U;
size_t bytes_allocated = 0U;
size_t dummy;
- bool fell_back_to_non_moving = false;
+ bool fall_back_to_non_moving = false;
mirror::Object* to_ref = region_space_->AllocNonvirtual</*kForEvac=*/ true>(
region_space_alloc_size, ®ion_space_bytes_allocated, nullptr, &dummy);
bytes_allocated = region_space_bytes_allocated;
if (LIKELY(to_ref != nullptr)) {
DCHECK_EQ(region_space_alloc_size, region_space_bytes_allocated);
} else {
- // Fall back to the non-moving space.
- fell_back_to_non_moving = true;
- if (kVerboseMode) {
- LOG(INFO) << "Out of memory in the to-space. Fell back to non-moving.";
+ // Failed to allocate in the region space. Try the skipped blocks.
+ to_ref = AllocateInSkippedBlock(self, region_space_alloc_size);
+ if (to_ref != nullptr) {
+ // Succeeded to allocate in a skipped block.
+ if (heap_->use_tlab_) {
+ // This is necessary for the tlab case as it's not accounted in the space.
+ region_space_->RecordAlloc(to_ref);
+ }
+ bytes_allocated = region_space_alloc_size;
+ heap_->num_bytes_allocated_.fetch_sub(bytes_allocated, std::memory_order_relaxed);
+ to_space_bytes_skipped_.fetch_sub(bytes_allocated, std::memory_order_relaxed);
+ to_space_objects_skipped_.fetch_sub(1, std::memory_order_relaxed);
+ } else {
+ // Fall back to the non-moving space.
+ fall_back_to_non_moving = true;
+ if (kVerboseMode) {
+ LOG(INFO) << "Out of memory in the to-space. Fall back to non-moving. skipped_bytes="
+ << to_space_bytes_skipped_.load(std::memory_order_relaxed)
+ << " skipped_objects="
+ << to_space_objects_skipped_.load(std::memory_order_relaxed);
+ }
+ to_ref = heap_->non_moving_space_->Alloc(self, obj_size,
+ &non_moving_space_bytes_allocated, nullptr, &dummy);
+ if (UNLIKELY(to_ref == nullptr)) {
+ LOG(FATAL_WITHOUT_ABORT) << "Fall-back non-moving space allocation failed for a "
+ << obj_size << " byte object in region type "
+ << region_space_->GetRegionType(from_ref);
+ LOG(FATAL) << "Object address=" << from_ref << " type=" << from_ref->PrettyTypeOf();
+ }
+ bytes_allocated = non_moving_space_bytes_allocated;
}
- to_ref = heap_->non_moving_space_->Alloc(self, obj_size,
- &non_moving_space_bytes_allocated, nullptr, &dummy);
- if (UNLIKELY(to_ref == nullptr)) {
- LOG(FATAL_WITHOUT_ABORT) << "Fall-back non-moving space allocation failed for a "
- << obj_size << " byte object in region type "
- << region_space_->GetRegionType(from_ref);
- LOG(FATAL) << "Object address=" << from_ref << " type=" << from_ref->PrettyTypeOf();
- }
- bytes_allocated = non_moving_space_bytes_allocated;
}
DCHECK(to_ref != nullptr);
@@ -3342,22 +3396,26 @@
// the forwarding pointer first. Make the lost copy (to_ref)
// look like a valid but dead (dummy) object and keep it for
// future reuse.
- VLOG(gc) << "GC: Lost copying race, size = " << obj_size;
- if (fell_back_to_non_moving) {
- DCHECK(heap_->non_moving_space_->HasAddress(to_ref));
- DCHECK_EQ(bytes_allocated, non_moving_space_bytes_allocated);
- // Free the non-moving-space chunk.
- heap_->non_moving_space_->Free(self, to_ref);
- } else {
+ FillWithDummyObject(self, to_ref, bytes_allocated);
+ if (!fall_back_to_non_moving) {
DCHECK(region_space_->IsInToSpace(to_ref));
if (bytes_allocated > space::RegionSpace::kRegionSize) {
// Free the large alloc.
region_space_->FreeLarge</*kForEvac=*/ true>(to_ref, bytes_allocated);
} else {
- // Make it look legitimate, record the object allocation, and then drop the object.
- FillWithDummyObject(self, to_ref, bytes_allocated);
+ // Record the lost copy for later reuse.
heap_->num_bytes_allocated_.fetch_add(bytes_allocated, std::memory_order_relaxed);
+ to_space_bytes_skipped_.fetch_add(bytes_allocated, std::memory_order_relaxed);
+ to_space_objects_skipped_.fetch_add(1, std::memory_order_relaxed);
+ MutexLock mu(self, skipped_blocks_lock_);
+ skipped_blocks_map_.insert(std::make_pair(bytes_allocated,
+ reinterpret_cast<uint8_t*>(to_ref)));
}
+ } else {
+ DCHECK(heap_->non_moving_space_->HasAddress(to_ref));
+ DCHECK_EQ(bytes_allocated, non_moving_space_bytes_allocated);
+ // Free the non-moving-space chunk.
+ heap_->non_moving_space_->Free(self, to_ref);
}
// Get the winner's forward ptr.
@@ -3379,10 +3437,7 @@
}
// Do a fence to prevent the field CAS in ConcurrentCopying::Process from possibly reordering
- // before the object copy. This serves the same purpose as the constructor fence in a new
- // object allocation. Another thread can get a pointer to this object either via the
- // forwarding address or via the returned to_ref. But it must read the to_space data via an
- // address dependency on one of those. Thus it cannot see old values in the copied object.
+ // before the object copy.
std::atomic_thread_fence(std::memory_order_release);
LockWord new_lock_word = LockWord::FromForwardingAddress(reinterpret_cast<size_t>(to_ref));
@@ -3394,12 +3449,6 @@
std::memory_order_relaxed);
if (LIKELY(success)) {
// The CAS succeeded.
- if (obj_size >= kCurrentlyCopyingMin) {
- // If someone else has since over-written currently_copying_, leave it alone. Otherwise
- // restore the old one. If the old one was already copied, the forwarding address will
- // already be there, and nobody will care. If not, then it's useful to put it back.
- currently_copying_.CompareAndSetStrongRelaxed(from_ref, old_currently_copying);
- }
DCHECK(thread_running_gc_ != nullptr);
if (LIKELY(self == thread_running_gc_)) {
objects_moved_gc_thread_ += 1;
@@ -3409,7 +3458,9 @@
bytes_moved_.fetch_add(bytes_allocated, std::memory_order_relaxed);
}
- if (UNLIKELY(fell_back_to_non_moving)) {
+ if (LIKELY(!fall_back_to_non_moving)) {
+ DCHECK(region_space_->IsInToSpace(to_ref));
+ } else {
DCHECK(heap_->non_moving_space_->HasAddress(to_ref));
DCHECK_EQ(bytes_allocated, non_moving_space_bytes_allocated);
if (!use_generational_cc_ || !young_gen_) {
@@ -3420,8 +3471,6 @@
// Mark it in the mark bitmap.
CHECK(!heap_->non_moving_space_->GetMarkBitmap()->AtomicTestAndSet(to_ref));
}
- } else {
- DCHECK(region_space_->IsInToSpace(to_ref));
}
if (kUseBakerReadBarrier) {
DCHECK(to_ref->GetReadBarrierState() == ReadBarrier::GrayState());
@@ -3588,6 +3637,10 @@
non_moving_space_inter_region_bitmap_->Clear();
}
{
+ MutexLock mu(self, skipped_blocks_lock_);
+ skipped_blocks_map_.clear();
+ }
+ {
ReaderMutexLock mu(self, *Locks::mutator_lock_);
{
WriterMutexLock mu2(self, *Locks::heap_bitmap_lock_);
diff --git a/runtime/gc/collector/concurrent_copying.h b/runtime/gc/collector/concurrent_copying.h
index 1bea029..2e5752b 100644
--- a/runtime/gc/collector/concurrent_copying.h
+++ b/runtime/gc/collector/concurrent_copying.h
@@ -75,16 +75,18 @@
void RunPhases() override
REQUIRES(!immune_gray_stack_lock_,
!mark_stack_lock_,
- !rb_slow_path_histogram_lock_);
+ !rb_slow_path_histogram_lock_,
+ !skipped_blocks_lock_);
void InitializePhase() REQUIRES_SHARED(Locks::mutator_lock_)
REQUIRES(!mark_stack_lock_, !immune_gray_stack_lock_);
void MarkingPhase() REQUIRES_SHARED(Locks::mutator_lock_)
REQUIRES(!mark_stack_lock_);
void CopyingPhase() REQUIRES_SHARED(Locks::mutator_lock_)
- REQUIRES(!mark_stack_lock_, !immune_gray_stack_lock_);
+ REQUIRES(!mark_stack_lock_, !skipped_blocks_lock_, !immune_gray_stack_lock_);
void ReclaimPhase() REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(!mark_stack_lock_);
void FinishPhase() REQUIRES(!mark_stack_lock_,
- !rb_slow_path_histogram_lock_);
+ !rb_slow_path_histogram_lock_,
+ !skipped_blocks_lock_);
void CaptureRssAtPeak() REQUIRES(!mark_stack_lock_);
void BindBitmaps() REQUIRES_SHARED(Locks::mutator_lock_)
@@ -125,10 +127,10 @@
mirror::Object* holder = nullptr,
MemberOffset offset = MemberOffset(0))
REQUIRES_SHARED(Locks::mutator_lock_)
- REQUIRES(!mark_stack_lock_, !immune_gray_stack_lock_);
+ REQUIRES(!mark_stack_lock_, !skipped_blocks_lock_, !immune_gray_stack_lock_);
ALWAYS_INLINE mirror::Object* MarkFromReadBarrier(mirror::Object* from_ref)
REQUIRES_SHARED(Locks::mutator_lock_)
- REQUIRES(!mark_stack_lock_, !immune_gray_stack_lock_);
+ REQUIRES(!mark_stack_lock_, !skipped_blocks_lock_, !immune_gray_stack_lock_);
bool IsMarking() const {
return is_marking_;
}
@@ -156,19 +158,12 @@
void PushOntoMarkStack(Thread* const self, mirror::Object* obj)
REQUIRES_SHARED(Locks::mutator_lock_)
REQUIRES(!mark_stack_lock_);
-
- // Return a pointer to the unique to-space copy of from_ref.
- // Ensures that copied data is visible to another thread that sees either the return
- // value or the forwarding pointer. The memory allocated to the copy is not yet
- // included in Heap::num_bytes_allocated_; it is instead tracked by the
- // {bytes,objects}_moved_... counters.
mirror::Object* Copy(Thread* const self,
mirror::Object* from_ref,
mirror::Object* holder,
MemberOffset offset)
REQUIRES_SHARED(Locks::mutator_lock_)
- REQUIRES(!mark_stack_lock_, !immune_gray_stack_lock_);
-
+ REQUIRES(!mark_stack_lock_, !skipped_blocks_lock_, !immune_gray_stack_lock_);
// Scan the reference fields of object `to_ref`.
template <bool kNoUnEvac>
void Scan(mirror::Object* to_ref) REQUIRES_SHARED(Locks::mutator_lock_)
@@ -184,19 +179,19 @@
template <bool kNoUnEvac>
void Process(mirror::Object* obj, MemberOffset offset)
REQUIRES_SHARED(Locks::mutator_lock_)
- REQUIRES(!mark_stack_lock_ , !immune_gray_stack_lock_);
+ REQUIRES(!mark_stack_lock_ , !skipped_blocks_lock_, !immune_gray_stack_lock_);
void VisitRoots(mirror::Object*** roots, size_t count, const RootInfo& info) override
REQUIRES_SHARED(Locks::mutator_lock_)
- REQUIRES(!mark_stack_lock_, !immune_gray_stack_lock_);
+ REQUIRES(!mark_stack_lock_, !skipped_blocks_lock_, !immune_gray_stack_lock_);
template<bool kGrayImmuneObject>
void MarkRoot(Thread* const self, mirror::CompressedReference<mirror::Object>* root)
REQUIRES_SHARED(Locks::mutator_lock_)
- REQUIRES(!mark_stack_lock_, !immune_gray_stack_lock_);
+ REQUIRES(!mark_stack_lock_, !skipped_blocks_lock_, !immune_gray_stack_lock_);
void VisitRoots(mirror::CompressedReference<mirror::Object>** roots,
size_t count,
const RootInfo& info) override
REQUIRES_SHARED(Locks::mutator_lock_)
- REQUIRES(!mark_stack_lock_, !immune_gray_stack_lock_);
+ REQUIRES(!mark_stack_lock_, !skipped_blocks_lock_, !immune_gray_stack_lock_);
void VerifyNoFromSpaceReferences() REQUIRES(Locks::mutator_lock_);
accounting::ObjectStack* GetAllocationStack();
accounting::ObjectStack* GetLiveStack();
@@ -233,11 +228,11 @@
void ProcessReferences(Thread* self) REQUIRES_SHARED(Locks::mutator_lock_);
mirror::Object* MarkObject(mirror::Object* from_ref) override
REQUIRES_SHARED(Locks::mutator_lock_)
- REQUIRES(!mark_stack_lock_, !immune_gray_stack_lock_);
+ REQUIRES(!mark_stack_lock_, !skipped_blocks_lock_, !immune_gray_stack_lock_);
void MarkHeapReference(mirror::HeapReference<mirror::Object>* from_ref,
bool do_atomic_update) override
REQUIRES_SHARED(Locks::mutator_lock_)
- REQUIRES(!mark_stack_lock_, !immune_gray_stack_lock_);
+ REQUIRES(!mark_stack_lock_, !skipped_blocks_lock_, !immune_gray_stack_lock_);
bool IsMarkedInUnevacFromSpace(mirror::Object* from_ref)
REQUIRES_SHARED(Locks::mutator_lock_);
bool IsMarkedInNonMovingSpace(mirror::Object* from_ref)
@@ -260,10 +255,10 @@
void MarkZygoteLargeObjects()
REQUIRES_SHARED(Locks::mutator_lock_);
void FillWithDummyObject(Thread* const self, mirror::Object* dummy_obj, size_t byte_size)
- REQUIRES(!mark_stack_lock_, !immune_gray_stack_lock_)
+ REQUIRES(!mark_stack_lock_, !skipped_blocks_lock_, !immune_gray_stack_lock_)
REQUIRES_SHARED(Locks::mutator_lock_);
mirror::Object* AllocateInSkippedBlock(Thread* const self, size_t alloc_size)
- REQUIRES(!mark_stack_lock_, !immune_gray_stack_lock_)
+ REQUIRES(!mark_stack_lock_, !skipped_blocks_lock_, !immune_gray_stack_lock_)
REQUIRES_SHARED(Locks::mutator_lock_);
void CheckEmptyMarkStack() REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(!mark_stack_lock_);
void IssueEmptyCheckpoint() REQUIRES_SHARED(Locks::mutator_lock_);
@@ -297,12 +292,12 @@
mirror::Object* holder = nullptr,
MemberOffset offset = MemberOffset(0))
REQUIRES_SHARED(Locks::mutator_lock_)
- REQUIRES(!mark_stack_lock_);
+ REQUIRES(!mark_stack_lock_, !skipped_blocks_lock_);
ALWAYS_INLINE mirror::Object* MarkUnevacFromSpaceRegion(Thread* const self,
mirror::Object* from_ref,
accounting::SpaceBitmap<kObjectAlignment>* bitmap)
REQUIRES_SHARED(Locks::mutator_lock_)
- REQUIRES(!mark_stack_lock_);
+ REQUIRES(!mark_stack_lock_, !skipped_blocks_lock_);
template<bool kGrayImmuneObject>
ALWAYS_INLINE mirror::Object* MarkImmuneSpace(Thread* const self,
mirror::Object* from_ref)
@@ -312,7 +307,7 @@
mirror::Object* MarkFromReadBarrierWithMeasurements(Thread* const self,
mirror::Object* from_ref)
REQUIRES_SHARED(Locks::mutator_lock_)
- REQUIRES(!mark_stack_lock_, !immune_gray_stack_lock_);
+ REQUIRES(!mark_stack_lock_, !skipped_blocks_lock_, !immune_gray_stack_lock_);
void DumpPerformanceInfo(std::ostream& os) override REQUIRES(!rb_slow_path_histogram_lock_);
// Set the read barrier mark entrypoints to non-null.
void ActivateReadBarrierEntrypoints();
@@ -420,14 +415,17 @@
// reclaimed_bytes_ratio = reclaimed_bytes/num_allocated_bytes per GC cycle
float reclaimed_bytes_ratio_sum_;
- // A largish from-space object that we're currently copying (or nullptr). A thread that sets
- // this to p promises that eiher p's forwarding address is set, or a thread is actively working
- // on ensuring that. Otherwise it's a hint; it may be cleared or set to a different value while
- // the object is still being copied.
- Atomic<mirror::Object*> currently_copying_;
-
- // The minimum object size in bytes for which we publicise copying in currently_copying_.
- static constexpr size_t kCurrentlyCopyingMin = 20'000;
+ // The skipped blocks are memory blocks/chucks that were copies of
+ // objects that were unused due to lost races (cas failures) at
+ // object copy/forward pointer install. They may be reused.
+ // Skipped blocks are always in region space. Their size is included directly
+ // in num_bytes_allocated_, i.e. they are treated as allocated, but may be directly
+ // used without going through a GC cycle like other objects. They are reused only
+ // if we run out of region space. TODO: Revisit this design.
+ Mutex skipped_blocks_lock_ DEFAULT_MUTEX_ACQUIRED_AFTER;
+ std::multimap<size_t, uint8_t*> skipped_blocks_map_ GUARDED_BY(skipped_blocks_lock_);
+ Atomic<size_t> to_space_bytes_skipped_;
+ Atomic<size_t> to_space_objects_skipped_;
// If measure_read_barrier_slow_path_ is true, we count how long is spent in MarkFromReadBarrier
// and also log.