Sweep only objects in the live stack in sticky-bit CC collections.
Reuse the same strategy used in sticky-bit Concurrent Mark-Sweep
(CMS) collections for sticky-bit Concurrent Copying (CC) collections
walk the live stack (which contains allocations made outside the
region space since the previous GC thread flip phase) and free
unmarked objects.
As a side effect, this change address a bug that used to trigger GC
crashes during a sticky-bit CC (young-generation) collection involving
an unreachable newly allocated object in the non-moving space with a
dangling reference to an object cleared or moved from a newly
allocated region of the region space.
Test: ART run-tests & gtests, libcore tests, JDWP tests (host & device)
Test: Device/emulator boot test
Bug: 67628039
Bug: 12687968
Change-Id: If5d94d854effdc8a614c1c3e3facb2221824aff2
diff --git a/runtime/gc/collector/concurrent_copying.cc b/runtime/gc/collector/concurrent_copying.cc
index bff6881..c12424b 100644
--- a/runtime/gc/collector/concurrent_copying.cc
+++ b/runtime/gc/collector/concurrent_copying.cc
@@ -60,6 +60,8 @@
// Slow path mark stack size, increase this if the stack is getting full and it is causing
// performance problems.
static constexpr size_t kReadBarrierMarkStackSize = 512 * KB;
+// Size (in the number of objects) of the sweep array free buffer.
+static constexpr size_t kSweepArrayChunkFreeSize = 1024;
// Verify that there are no missing card marks.
static constexpr bool kVerifyNoMissingCardMarks = kIsDebugBuild;
@@ -128,6 +130,20 @@
pooled_mark_stacks_.push_back(mark_stack);
}
}
+ if (kEnableGenerationalConcurrentCopyingCollection) {
+ // Allocate sweep array free buffer.
+ std::string error_msg;
+ sweep_array_free_buffer_mem_map_ = MemMap::MapAnonymous(
+ "concurrent copying sweep array free buffer",
+ /* addr */ nullptr,
+ RoundUp(kSweepArrayChunkFreeSize * sizeof(mirror::Object*), kPageSize),
+ PROT_READ | PROT_WRITE,
+ /* low_4gb */ false,
+ /* reuse */ false,
+ &error_msg);
+ CHECK(sweep_array_free_buffer_mem_map_.IsValid())
+ << "Couldn't allocate sweep array free buffer: " << error_msg;
+ }
}
void ConcurrentCopying::MarkHeapReference(mirror::HeapReference<mirror::Object>* field,
@@ -1790,29 +1806,126 @@
}
void ConcurrentCopying::Sweep(bool swap_bitmaps) {
- {
- TimingLogger::ScopedTiming t("MarkStackAsLive", GetTimings());
- accounting::ObjectStack* live_stack = heap_->GetLiveStack();
- if (kEnableFromSpaceAccountingCheck) {
- CHECK_GE(live_stack_freeze_size_, live_stack->Size());
+ if (kEnableGenerationalConcurrentCopyingCollection && young_gen_) {
+ // Only sweep objects on the live stack.
+ SweepArray(heap_->GetLiveStack(), /* swap_bitmaps */ false);
+ } else {
+ {
+ TimingLogger::ScopedTiming t("MarkStackAsLive", GetTimings());
+ accounting::ObjectStack* live_stack = heap_->GetLiveStack();
+ if (kEnableFromSpaceAccountingCheck) {
+ // Ensure that nobody inserted items in the live stack after we swapped the stacks.
+ CHECK_GE(live_stack_freeze_size_, live_stack->Size());
+ }
+ heap_->MarkAllocStackAsLive(live_stack);
+ live_stack->Reset();
}
- heap_->MarkAllocStackAsLive(live_stack);
- live_stack->Reset();
+ CheckEmptyMarkStack();
+ TimingLogger::ScopedTiming split("Sweep", GetTimings());
+ for (const auto& space : GetHeap()->GetContinuousSpaces()) {
+ if (space->IsContinuousMemMapAllocSpace()) {
+ space::ContinuousMemMapAllocSpace* alloc_space = space->AsContinuousMemMapAllocSpace();
+ if (space == region_space_ || immune_spaces_.ContainsSpace(space)) {
+ continue;
+ }
+ TimingLogger::ScopedTiming split2(
+ alloc_space->IsZygoteSpace() ? "SweepZygoteSpace" : "SweepAllocSpace", GetTimings());
+ RecordFree(alloc_space->Sweep(swap_bitmaps));
+ }
+ }
+ SweepLargeObjects(swap_bitmaps);
}
+}
+
+// Copied and adapted from MarkSweep::SweepArray.
+void ConcurrentCopying::SweepArray(accounting::ObjectStack* allocations, bool swap_bitmaps) {
+ // This method is only used when Generational CC collection is enabled.
+ DCHECK(kEnableGenerationalConcurrentCopyingCollection);
CheckEmptyMarkStack();
- TimingLogger::ScopedTiming split("Sweep", GetTimings());
- for (const auto& space : GetHeap()->GetContinuousSpaces()) {
- if (space->IsContinuousMemMapAllocSpace()) {
- space::ContinuousMemMapAllocSpace* alloc_space = space->AsContinuousMemMapAllocSpace();
- if (space == region_space_ || immune_spaces_.ContainsSpace(space)) {
+ TimingLogger::ScopedTiming t("SweepArray", GetTimings());
+ Thread* self = Thread::Current();
+ mirror::Object** chunk_free_buffer = reinterpret_cast<mirror::Object**>(
+ sweep_array_free_buffer_mem_map_.BaseBegin());
+ size_t chunk_free_pos = 0;
+ ObjectBytePair freed;
+ ObjectBytePair freed_los;
+ // How many objects are left in the array, modified after each space is swept.
+ StackReference<mirror::Object>* objects = allocations->Begin();
+ size_t count = allocations->Size();
+ // Start by sweeping the continuous spaces.
+ for (space::ContinuousSpace* space : heap_->GetContinuousSpaces()) {
+ if (!space->IsAllocSpace() ||
+ space == region_space_ ||
+ immune_spaces_.ContainsSpace(space) ||
+ space->GetLiveBitmap() == nullptr) {
+ continue;
+ }
+ space::AllocSpace* alloc_space = space->AsAllocSpace();
+ accounting::ContinuousSpaceBitmap* live_bitmap = space->GetLiveBitmap();
+ accounting::ContinuousSpaceBitmap* mark_bitmap = space->GetMarkBitmap();
+ if (swap_bitmaps) {
+ std::swap(live_bitmap, mark_bitmap);
+ }
+ StackReference<mirror::Object>* out = objects;
+ for (size_t i = 0; i < count; ++i) {
+ mirror::Object* const obj = objects[i].AsMirrorPtr();
+ if (kUseThreadLocalAllocationStack && obj == nullptr) {
continue;
}
- TimingLogger::ScopedTiming split2(
- alloc_space->IsZygoteSpace() ? "SweepZygoteSpace" : "SweepAllocSpace", GetTimings());
- RecordFree(alloc_space->Sweep(swap_bitmaps));
+ if (space->HasAddress(obj)) {
+ // This object is in the space, remove it from the array and add it to the sweep buffer
+ // if needed.
+ if (!mark_bitmap->Test(obj)) {
+ if (chunk_free_pos >= kSweepArrayChunkFreeSize) {
+ TimingLogger::ScopedTiming t2("FreeList", GetTimings());
+ freed.objects += chunk_free_pos;
+ freed.bytes += alloc_space->FreeList(self, chunk_free_pos, chunk_free_buffer);
+ chunk_free_pos = 0;
+ }
+ chunk_free_buffer[chunk_free_pos++] = obj;
+ }
+ } else {
+ (out++)->Assign(obj);
+ }
+ }
+ if (chunk_free_pos > 0) {
+ TimingLogger::ScopedTiming t2("FreeList", GetTimings());
+ freed.objects += chunk_free_pos;
+ freed.bytes += alloc_space->FreeList(self, chunk_free_pos, chunk_free_buffer);
+ chunk_free_pos = 0;
+ }
+ // All of the references which space contained are no longer in the allocation stack, update
+ // the count.
+ count = out - objects;
+ }
+ // Handle the large object space.
+ space::LargeObjectSpace* large_object_space = GetHeap()->GetLargeObjectsSpace();
+ if (large_object_space != nullptr) {
+ accounting::LargeObjectBitmap* large_live_objects = large_object_space->GetLiveBitmap();
+ accounting::LargeObjectBitmap* large_mark_objects = large_object_space->GetMarkBitmap();
+ if (swap_bitmaps) {
+ std::swap(large_live_objects, large_mark_objects);
+ }
+ for (size_t i = 0; i < count; ++i) {
+ mirror::Object* const obj = objects[i].AsMirrorPtr();
+ // Handle large objects.
+ if (kUseThreadLocalAllocationStack && obj == nullptr) {
+ continue;
+ }
+ if (!large_mark_objects->Test(obj)) {
+ ++freed_los.objects;
+ freed_los.bytes += large_object_space->Free(self, obj);
+ }
}
}
- SweepLargeObjects(swap_bitmaps);
+ {
+ TimingLogger::ScopedTiming t2("RecordFree", GetTimings());
+ RecordFree(freed);
+ RecordFreeLOS(freed_los);
+ t2.NewTiming("ResetStack");
+ allocations->Reset();
+ }
+ sweep_array_free_buffer_mem_map_.MadviseDontNeedAndZero();
}
void ConcurrentCopying::MarkZygoteLargeObjects() {
@@ -1922,7 +2035,7 @@
{
WriterMutexLock mu(self, *Locks::heap_bitmap_lock_);
- Sweep(false);
+ Sweep(/* swap_bitmaps */ false);
SwapBitmaps();
heap_->UnBindBitmaps();
diff --git a/runtime/gc/collector/concurrent_copying.h b/runtime/gc/collector/concurrent_copying.h
index 10502ea..e1ff97a 100644
--- a/runtime/gc/collector/concurrent_copying.h
+++ b/runtime/gc/collector/concurrent_copying.h
@@ -222,8 +222,14 @@
REQUIRES_SHARED(Locks::mutator_lock_);
void SweepSystemWeaks(Thread* self)
REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(!Locks::heap_bitmap_lock_);
+ // Sweep unmarked objects to complete the garbage collection. Full GCs sweep
+ // all allocation spaces (except the region space). Sticky-bit GCs just sweep
+ // a subset of the heap.
void Sweep(bool swap_bitmaps)
REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(Locks::heap_bitmap_lock_, !mark_stack_lock_);
+ // Sweep only pointers within an array.
+ void SweepArray(accounting::ObjectStack* allocation_stack_, bool swap_bitmaps)
+ REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(Locks::heap_bitmap_lock_, !mark_stack_lock_);
void SweepLargeObjects(bool swap_bitmaps)
REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(Locks::heap_bitmap_lock_);
void MarkZygoteLargeObjects()
@@ -390,6 +396,11 @@
// ObjPtr since the GC may transition to suspended and runnable between phases.
mirror::Class* java_lang_Object_;
+ // Sweep array free buffer, used to sweep the spaces based on an array more
+ // efficiently, by recording dead objects to be freed in batches (see
+ // ConcurrentCopying::SweepArray).
+ MemMap sweep_array_free_buffer_mem_map_;
+
class ActivateReadBarrierEntrypointsCallback;
class ActivateReadBarrierEntrypointsCheckpoint;
class AssertToSpaceInvariantFieldVisitor;
diff --git a/runtime/gc/collector/mark_sweep.h b/runtime/gc/collector/mark_sweep.h
index 70e4432..af2bb97 100644
--- a/runtime/gc/collector/mark_sweep.h
+++ b/runtime/gc/collector/mark_sweep.h
@@ -351,6 +351,9 @@
// Verification.
size_t live_stack_freeze_size_;
+ // Sweep array free buffer, used to sweep the spaces based on an array more
+ // efficiently, by recording dead objects to be freed in batches (see
+ // MarkSweep::SweepArray).
MemMap sweep_array_free_buffer_mem_map_;
private:
diff --git a/test/1000-non-moving-space-stress/expected.txt b/test/1000-non-moving-space-stress/expected.txt
new file mode 100644
index 0000000..b0aad4d
--- /dev/null
+++ b/test/1000-non-moving-space-stress/expected.txt
@@ -0,0 +1 @@
+passed
diff --git a/test/1000-non-moving-space-stress/info.txt b/test/1000-non-moving-space-stress/info.txt
new file mode 100644
index 0000000..a20459f
--- /dev/null
+++ b/test/1000-non-moving-space-stress/info.txt
@@ -0,0 +1,5 @@
+Regression test for a bug that used to trigger GC crashes during a
+sticky-bit CC (young-generation) collection involving an unreachable
+newly allocated object in the non-moving space with a dangling
+reference to an object cleared or moved from a newly allocated region
+of the region space.
diff --git a/test/1000-non-moving-space-stress/src-art/Main.java b/test/1000-non-moving-space-stress/src-art/Main.java
new file mode 100644
index 0000000..18bfdd3
--- /dev/null
+++ b/test/1000-non-moving-space-stress/src-art/Main.java
@@ -0,0 +1,53 @@
+/*
+ * Copyright (C) 2018 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+import dalvik.system.VMRuntime;
+
+public class Main {
+
+ public static void main(String[] args) throws Exception {
+ VMRuntime runtime = VMRuntime.getRuntime();
+
+ try {
+ int N = 1024 * 1024;
+ int S = 512;
+ for (int n = 0; n < N; ++n) {
+ // Allocate unreachable objects.
+ $noinline$Alloc(runtime);
+ // Allocate an object with a substantial size to increase memory
+ // pressure and eventually trigger non-explicit garbage collection
+ // (explicit garbage collections triggered by java.lang.Runtime.gc()
+ // are always full GCs). Upon garbage collection, the objects
+ // allocated in $noinline$Alloc used to trigger a crash.
+ Object[] moving_array = new Object[S];
+ }
+ } catch (OutOfMemoryError e) {
+ // Stop here.
+ }
+ System.out.println("passed");
+ }
+
+ // When using the Concurrent Copying (CC) collector (default collector),
+ // this method allocates an object in the non-moving space and an object
+ // in the region space, make the former reference the later, and returns
+ // nothing (so that none of these objects are reachable when upon return).
+ static void $noinline$Alloc(VMRuntime runtime) {
+ Object[] non_moving_array = (Object[]) runtime.newNonMovableArray(Object.class, 1);
+ // Small object, unlikely to trigger garbage collection.
+ non_moving_array[0] = new Object();
+ }
+
+}
diff --git a/test/knownfailures.json b/test/knownfailures.json
index 7322a35..9ade2b1 100644
--- a/test/knownfailures.json
+++ b/test/knownfailures.json
@@ -986,6 +986,7 @@
"678-quickening",
"679-locks",
"999-redefine-hiddenapi",
+ "1000-non-moving-space-stress",
"1951-monitor-enter-no-suspend"],
"variant": "jvm",
"description": ["Doesn't run on RI."]