Enable card cleaning
Cards which do not map to image spaces are now cleared at the start of GC. Cards which map to image spaces are now processed when we go through all the dirty cards after recursive mark. Dirty cards are handled based on if they are either image space cards or cards invalidated by mutators during CMS.
Change-Id: I6c2dc177ebd3f7dc7bbbbd19ae67221371851ebe
diff --git a/src/card_table.cc b/src/card_table.cc
index d442306..0eac91f 100644
--- a/src/card_table.cc
+++ b/src/card_table.cc
@@ -22,6 +22,7 @@
#include "heap_bitmap.h"
#include "logging.h"
#include "runtime.h"
+#include "space.h"
#include "utils.h"
namespace art {
@@ -80,6 +81,18 @@
return new CardTable(mem_map.release(), biased_begin, offset);
}
+void CardTable::ClearNonImageSpaceCards(Heap* heap) {
+ // TODO: clear just the range of the table that has been modified
+ const std::vector<Space*>& spaces = heap->GetSpaces();
+ for (size_t i = 0; i < spaces.size(); ++i) {
+ if (!spaces[i]->IsImageSpace()) {
+ byte* card_start = CardFromAddr(spaces[i]->Begin());
+ byte* card_end = CardFromAddr(spaces[i]->End());
+ memset(reinterpret_cast<void*>(card_start), GC_CARD_CLEAN, card_end - card_start);
+ }
+ }
+}
+
void CardTable::ClearCardTable() {
// TODO: clear just the range of the table that has been modified
memset(mem_map_->Begin(), GC_CARD_CLEAN, mem_map_->Size());
@@ -97,8 +110,7 @@
}
}
-void CardTable::Scan(byte* heap_begin, byte* heap_end, Callback* visitor, void* arg) const {
- Heap* heap = Runtime::Current()->GetHeap();
+void CardTable::Scan(HeapBitmap* bitmap, byte* heap_begin, byte* heap_end, Callback* visitor, void* arg) const {
byte* card_cur = CardFromAddr(heap_begin);
byte* card_end = CardFromAddr(heap_end);
while (card_cur < card_end) {
@@ -113,7 +125,7 @@
}
if (run > 0) {
byte* run_end = &card_cur[run];
- heap->GetLiveBits()->VisitRange(reinterpret_cast<uintptr_t>(AddrFromCard(run_start)),
+ bitmap->VisitRange(reinterpret_cast<uintptr_t>(AddrFromCard(run_start)),
reinterpret_cast<uintptr_t>(AddrFromCard(run_end)),
visitor, arg);
}
diff --git a/src/card_table.h b/src/card_table.h
index 70d033e..9cfa70b 100644
--- a/src/card_table.h
+++ b/src/card_table.h
@@ -24,6 +24,8 @@
namespace art {
+class Heap;
+class HeapBitmap;
class Object;
#define GC_CARD_SHIFT 7
@@ -58,20 +60,22 @@
// For every dirty card between begin and end invoke the visitor with the specified argument
typedef void Callback(Object* obj, void* arg);
- void Scan(byte* begin, byte* end, Callback* visitor, void* arg) const;
+ void Scan(HeapBitmap* bitmap, byte* begin, byte* end, Callback* visitor, void* arg) const;
// Assertion used to check the given address is covered by the card table
void CheckAddrIsInCardTable(const byte* addr) const;
+ // Resets all of the bytes in the card table to clean.
+ void ClearCardTable();
+
+ // Resets all of the bytes in the card table to clean.
+ void ClearNonImageSpaceCards(Heap* heap);
private:
CardTable(MemMap* begin, byte* biased_begin, size_t offset) :
mem_map_(begin), biased_begin_(biased_begin), offset_(offset) {}
- // Resets all of the bytes in the card table to clean.
- void ClearCardTable();
-
// Returns the address of the relevant byte in the card table, given an address on the heap.
byte* CardFromAddr(const void *addr) const {
byte *cardAddr = biased_begin_ + ((uintptr_t)addr >> GC_CARD_SHIFT);
diff --git a/src/class_linker.cc b/src/class_linker.cc
index 000e2a5..98d5fe0 100644
--- a/src/class_linker.cc
+++ b/src/class_linker.cc
@@ -939,7 +939,9 @@
for (It it = classes_.begin(), end = classes_.end(); it != end; ++it) {
visitor(it->second, arg);
}
- // Note. we deliberately ignore the class roots in the image (held in image_classes_)
+
+ // We deliberately ignore the class roots in the image since we
+ // handle image roots by using the MS/CMS rescanning of dirty cards.
}
visitor(array_iftable_, arg);
diff --git a/src/heap.cc b/src/heap.cc
index 75b11ea..eb4f3e8 100644
--- a/src/heap.cc
+++ b/src/heap.cc
@@ -459,7 +459,7 @@
// Fail impossible allocations
if (alloc_size > space->Capacity()) {
// On failure collect soft references
- CollectGarbageInternal(true);
+ CollectGarbageInternal(false, true);
return NULL;
}
@@ -486,7 +486,7 @@
++Runtime::Current()->GetStats()->gc_for_alloc_count;
++Thread::Current()->GetStats()->gc_for_alloc_count;
}
- CollectGarbageInternal(false);
+ CollectGarbageInternal(false, false);
ptr = space->AllocWithoutGrowth(alloc_size);
if (ptr != NULL) {
return ptr;
@@ -512,7 +512,7 @@
// OLD-TODO: wait for the finalizers from the previous GC to finish
VLOG(gc) << "Forcing collection of SoftReferences for " << PrettySize(alloc_size) << " allocation";
- CollectGarbageInternal(true);
+ CollectGarbageInternal(false, true);
ptr = space->AllocWithGrowth(alloc_size);
if (ptr != NULL) {
return ptr;
@@ -575,10 +575,10 @@
void Heap::CollectGarbage(bool clear_soft_references) {
ScopedHeapLock heap_lock;
- CollectGarbageInternal(clear_soft_references);
+ CollectGarbageInternal(false, clear_soft_references);
}
-void Heap::CollectGarbageInternal(bool clear_soft_references) {
+void Heap::CollectGarbageInternal(bool concurrent, bool clear_soft_references) {
lock_->AssertHeld();
ThreadList* thread_list = Runtime::Current()->GetThreadList();
@@ -598,31 +598,43 @@
mark_sweep.MarkRoots();
timings.AddSplit("MarkRoots");
- mark_sweep.ScanDirtyImageRoots();
- timings.AddSplit("DirtyImageRoots");
-
// Roots are marked on the bitmap and the mark_stack is empty
DCHECK(mark_sweep.IsMarkStackEmpty());
- // TODO: if concurrent
- // unlock heap
- // thread_list->ResumeAll();
+ if (concurrent) {
+ Unlock();
+ thread_list->ResumeAll();
+ }
// Recursively mark all bits set in the non-image mark bitmap
mark_sweep.RecursiveMark();
timings.AddSplit("RecursiveMark");
- // TODO: if concurrent
- // lock heap
- // thread_list->SuspendAll();
- // re-mark root set
- // scan dirty objects
+ if (concurrent) {
+ Lock();
+ thread_list->SuspendAll();
+
+ // Re-mark root set.
+ mark_sweep.ReMarkRoots();
+ timings.AddSplit("ReMarkRoots");
+ }
+
+ // Scan dirty objects, this is required even if we are not doing a
+ // concurrent GC since we use the card table to locate image roots.
+ mark_sweep.RecursiveMarkDirtyObjects();
+ timings.AddSplit("RecursiveMarkDirtyObjects");
mark_sweep.ProcessReferences(clear_soft_references);
timings.AddSplit("ProcessReferences");
- // TODO: if concurrent
- // swap bitmaps
+ // TODO: swap live and marked bitmaps
+ // Note: Need to be careful about image spaces if we do this since not
+ // everything image space will be marked, resulting in things not being
+ // marked as live anymore.
+
+ // Verify that we only reach marked objects from the image space
+ mark_sweep.VerifyImageRoots();
+ timings.AddSplit("VerifyImageRoots");
mark_sweep.Sweep();
timings.AddSplit("Sweep");
diff --git a/src/heap.h b/src/heap.h
index d368158..de3caa2 100644
--- a/src/heap.h
+++ b/src/heap.h
@@ -233,7 +233,7 @@
void RecordAllocationLocked(AllocSpace* space, const Object* object);
void RecordImageAllocations(Space* space);
- void CollectGarbageInternal(bool clear_soft_references);
+ void CollectGarbageInternal(bool concurrent, bool clear_soft_references);
// Given the current contents of the alloc space, increase the allowed heap footprint to match
// the target utilization ratio. This should only be called immediately after a full garbage
diff --git a/src/mark_sweep.cc b/src/mark_sweep.cc
index 72b9ddb..d070a57 100644
--- a/src/mark_sweep.cc
+++ b/src/mark_sweep.cc
@@ -59,6 +59,7 @@
mark_stack_->Reset();
// TODO: if concurrent, clear the card table.
+ heap_->GetCardTable()->ClearNonImageSpaceCards(heap_);
// TODO: if concurrent, enable card marking in compiler
@@ -101,6 +102,13 @@
mark_sweep->MarkObject0(root, false);
}
+void MarkSweep::ReMarkObjectVisitor(const Object* root, void* arg) {
+ DCHECK(root != NULL);
+ DCHECK(arg != NULL);
+ MarkSweep* mark_sweep = reinterpret_cast<MarkSweep*>(arg);
+ mark_sweep->MarkObject0(root, true);
+}
+
// Marks all objects in the root set.
void MarkSweep::MarkRoots() {
Runtime::Current()->VisitRoots(MarkObjectVisitor, this);
@@ -110,7 +118,7 @@
DCHECK(root != NULL);
DCHECK(arg != NULL);
MarkSweep* mark_sweep = reinterpret_cast<MarkSweep*>(arg);
- DCHECK(mark_sweep->finger_ == NULL); // no point to check finger if it is NULL
+ //DCHECK(mark_sweep->finger_ == NULL); // no point to check finger if it is NULL
mark_sweep->MarkObject0(root, false);
mark_sweep->ScanObject(root);
}
@@ -123,7 +131,7 @@
if (spaces[i]->IsImageSpace()) {
byte* begin = spaces[i]->Begin();
byte* end = spaces[i]->End();
- card_table->Scan(begin, end, ScanImageRootVisitor, this);
+ card_table->Scan(heap_->GetLiveBits(), begin, end, ScanImageRootVisitor, this);
}
}
}
@@ -140,6 +148,48 @@
mark_sweep->ScanObject(obj);
}
+void MarkSweep::ScanDirtyCardCallback(Object* obj, void* arg) {
+ MarkSweep* mark_sweep = reinterpret_cast<MarkSweep*>(arg);
+ mark_sweep->ScanObject(obj);
+}
+
+void MarkSweep::ScanGrayObjects() {
+ const std::vector<Space*>& spaces = heap_->GetSpaces();
+ CardTable* card_table = heap_->GetCardTable();
+ for (size_t i = 0; i < spaces.size(); ++i) {
+ byte* begin = spaces[i]->Begin();
+ byte* end = spaces[i]->End();
+ // Normally, we only need to scan the black dirty objects
+ // But for image spaces, the roots will not be black objects.
+ // To address this we just scan the live bits instead of the mark bits.
+ if (UNLIKELY(spaces[i]->IsImageSpace())) {
+ // Image roots may not be marked so we may need to mark them.
+ // TODO: optimize this by offsetting some of the work to init.
+ card_table->Scan(heap_->GetLiveBits(), begin, end, ScanImageRootVisitor, this);
+ } else {
+ card_table->Scan(heap_->GetMarkBits(), begin, end, ScanDirtyCardCallback, this);
+ }
+ }
+}
+
+void MarkSweep::VerifyImageRoots() {
+ // Verify roots ensures that all the references inside the image space point
+ // objects which are either in the image space or marked objects in the alloc
+ // space
+#ifndef NDEBUG
+ void* arg = reinterpret_cast<void*>(this);
+ const std::vector<Space*>& spaces = heap_->GetSpaces();
+ for (size_t i = 0; i < spaces.size(); ++i) {
+ if (spaces[i]->IsImageSpace()) {
+ uintptr_t begin = reinterpret_cast<uintptr_t>(spaces[i]->Begin());
+ uintptr_t end = reinterpret_cast<uintptr_t>(spaces[i]->End());
+ mark_bitmap_->ScanWalk(begin, end, &MarkSweep::CheckBitmapCallback, arg);
+ }
+ }
+ finger_ = reinterpret_cast<Object*>(~0);
+#endif
+}
+
// Populates the mark stack based on the set of marked objects and
// recursively marks until the mark stack is emptied.
void MarkSweep::RecursiveMark() {
@@ -154,29 +204,22 @@
void* arg = reinterpret_cast<void*>(this);
const std::vector<Space*>& spaces = heap_->GetSpaces();
for (size_t i = 0; i < spaces.size(); ++i) {
-#ifndef NDEBUG
uintptr_t begin = reinterpret_cast<uintptr_t>(spaces[i]->Begin());
uintptr_t end = reinterpret_cast<uintptr_t>(spaces[i]->End());
- if (!spaces[i]->IsImageSpace()) {
- mark_bitmap_->ScanWalk(begin, end, &MarkSweep::ScanBitmapCallback, arg);
- } else {
- mark_bitmap_->ScanWalk(begin, end, &MarkSweep::CheckBitmapCallback, arg);
- }
-#else
- if (!spaces[i]->IsImageSpace()) {
- uintptr_t begin = reinterpret_cast<uintptr_t>(spaces[i]->Begin());
- uintptr_t end = reinterpret_cast<uintptr_t>(spaces[i]->End());
- mark_bitmap_->ScanWalk(begin, end, &MarkSweep::ScanBitmapCallback, arg);
- }
-#endif
+ mark_bitmap_->ScanWalk(begin, end, &MarkSweep::ScanBitmapCallback, arg);
}
finger_ = reinterpret_cast<Object*>(~0);
// TODO: tune the frequency of emptying the mark stack
ProcessMarkStack();
}
+void MarkSweep::RecursiveMarkDirtyObjects() {
+ ScanGrayObjects();
+ ProcessMarkStack();
+}
+
void MarkSweep::ReMarkRoots() {
- UNIMPLEMENTED(FATAL);
+ Runtime::Current()->VisitRoots(ReMarkObjectVisitor, this);
}
void MarkSweep::SweepJniWeakGlobals() {
@@ -312,12 +355,31 @@
AllocSpace* alloc_space = heap_->GetAllocSpace();
if (alloc_space->Contains(ref)) {
bool is_marked = mark_bitmap_->Test(ref);
+
if (!is_marked) {
LOG(INFO) << *alloc_space;
LOG(WARNING) << (is_static ? "Static ref'" : "Instance ref'") << PrettyTypeOf(ref)
<< "' (" << reinterpret_cast<const void*>(ref) << ") in '" << PrettyTypeOf(obj)
<< "' (" << reinterpret_cast<const void*>(obj) << ") at offset "
<< reinterpret_cast<void*>(offset.Int32Value()) << " wasn't marked";
+
+ const Class* klass = is_static ? obj->AsClass() : obj->GetClass();
+ DCHECK(klass != NULL);
+ const ObjectArray<Field>* fields = is_static ? klass->GetSFields() : klass->GetIFields();
+ DCHECK(fields != NULL);
+ bool found = false;
+ for (int32_t i = 0; i < fields->GetLength(); ++i) {
+ const Field* cur = fields->Get(i);
+ if (cur->GetOffset().Int32Value() == offset.Int32Value()) {
+ LOG(WARNING) << "Field referencing the alloc space was " << PrettyField(cur);
+ found = true;
+ break;
+ }
+ }
+ if (!found) {
+ LOG(WARNING) << "Could not find field in object alloc space with offset " << offset.Int32Value();
+ }
+
bool obj_marked = heap_->GetCardTable()->IsDirty(obj);
if (!obj_marked) {
LOG(WARNING) << "Object '" << PrettyTypeOf(obj) << "' "
@@ -488,10 +550,6 @@
}
}
-void MarkSweep::ScanDirtyObjects() {
- ProcessMarkStack();
-}
-
// Walks the reference list marking any references subject to the
// reference clearing policy. References with a black referent are
// removed from the list. References with white referents biased
diff --git a/src/mark_sweep.h b/src/mark_sweep.h
index 7fda6ea..43ed9b6 100644
--- a/src/mark_sweep.h
+++ b/src/mark_sweep.h
@@ -40,9 +40,12 @@
// Marks the root set at the start of a garbage collection.
void MarkRoots();
- // Marks the roots in the image space on dirty cards
+ // Marks the roots in the image space on dirty cards.
void ScanDirtyImageRoots();
+ // Verify that image roots point to only marked objects within the alloc space.
+ void VerifyImageRoots();
+
bool IsMarkStackEmpty() const {
return mark_stack_->IsEmpty();
}
@@ -50,6 +53,10 @@
// Builds a mark stack and recursively mark until it empties.
void RecursiveMark();
+ // Builds a mark stack with objects on dirty cards and recursively mark
+ // until it empties.
+ void RecursiveMarkDirtyObjects();
+
// Remarks the root set after completing the concurrent mark.
void ReMarkRoots();
@@ -79,8 +86,12 @@
static void MarkObjectVisitor(const Object* root, void* arg);
+ static void ReMarkObjectVisitor(const Object* root, void* arg);
+
static void ScanImageRootVisitor(Object* root, void* arg);
+ static void ScanDirtyCardCallback(Object* obj, void* arg);
+
// Marks an object.
void MarkObject(const Object* obj);
@@ -130,7 +141,7 @@
void CheckOther(const Object* obj);
// Blackens objects grayed during a garbage collection.
- void ScanDirtyObjects();
+ void ScanGrayObjects();
// Schedules an unmarked object for reference processing.
void DelayReferenceReferent(Object* reference);
diff --git a/src/object.h b/src/object.h
index e787933..9ad02a8 100644
--- a/src/object.h
+++ b/src/object.h
@@ -1676,7 +1676,7 @@
SetFieldObject(OFFSET_OF_OBJECT_MEMBER(Class, iftable_), new_iftable, false);
}
- // Get instance fields
+ // Get instance fields of the class (See also GetSFields).
ObjectArray<Field>* GetIFields() const {
DCHECK(IsLoaded() || IsErroneous());
return GetFieldObject<ObjectArray<Field>*>(OFFSET_OF_OBJECT_MEMBER(Class, ifields_), false);
@@ -1751,6 +1751,7 @@
SetField32(OFFSET_OF_OBJECT_MEMBER(Class, num_reference_static_fields_), new_num, false);
}
+ // Gets the static fields of the class.
ObjectArray<Field>* GetSFields() const {
DCHECK(IsLoaded() || IsErroneous());
return GetFieldObject<ObjectArray<Field>*>(OFFSET_OF_OBJECT_MEMBER(Class, sfields_), false);
