Enable mod union table
Enable mod union table(bitmap). This change aims to reduce the second pause times by processing dirty image cards and cleaning them by storing their alloc space references in a bitmap. The bitmap is then scanned concurrently(if CMS) before recursive mark.
Reduces second pause time. Second pause time now typically < 5 ms instead of 30-40ms.
Change-Id: I831eeb8af7299d4e86cf2dd9c29d0b7e230cd387
diff --git a/build/Android.common.mk b/build/Android.common.mk
index 99aa167..1dcea2a 100644
--- a/build/Android.common.mk
+++ b/build/Android.common.mk
@@ -168,6 +168,7 @@
src/mark_sweep.cc \
src/mem_map.cc \
src/memory_region.cc \
+ src/mod_union_table.cc \
src/monitor.cc \
src/mutex.cc \
src/native/dalvik_system_DexFile.cc \
diff --git a/src/card_table.h b/src/card_table.h
index d61a47e..8fde9fe 100644
--- a/src/card_table.h
+++ b/src/card_table.h
@@ -51,6 +51,19 @@
return *CardFromAddr(obj) == GC_CARD_DIRTY;
}
+ // Visit cards within memory range.
+ template <typename Visitor>
+ void VisitClear(const void* start, const void* end, const Visitor& visitor) {
+ byte* card_start = CardFromAddr(start);
+ byte* card_end = CardFromAddr(end);
+ for (byte* cur = card_start; cur != card_end; ++cur) {
+ if (*cur == GC_CARD_DIRTY) {
+ *cur = GC_CARD_CLEAN;
+ visitor(cur);
+ }
+ }
+ }
+
// Returns a value that when added to a heap address >> GC_CARD_SHIFT will address the appropriate
// card table byte. For convenience this value is cached in every Thread
byte* GetBiasedBegin() const {
@@ -61,16 +74,24 @@
typedef void Callback(Object* obj, void* arg);
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.
+ // Resets all of the bytes in the card table which do not map to the image space.
void ClearNonImageSpaceCards(Heap* heap);
+ // Returns the first address in the heap which maps to this card.
+ void* AddrFromCard(const byte *card_addr) const {
+ DCHECK(IsValidCard(card_addr))
+ << " card_addr: " << reinterpret_cast<const void*>(card_addr)
+ << " begin: " << reinterpret_cast<void*>(mem_map_->Begin() + offset_)
+ << " end: " << reinterpret_cast<void*>(mem_map_->End());
+ uintptr_t offset = card_addr - biased_begin_;
+ return reinterpret_cast<void*>(offset << GC_CARD_SHIFT);
+ }
private:
CardTable(MemMap* begin, byte* biased_begin, size_t offset);
@@ -83,16 +104,6 @@
return card_addr;
}
- // Returns the first address in the heap which maps to this card.
- void* AddrFromCard(const byte *card_addr) const {
- DCHECK(IsValidCard(card_addr))
- << " card_addr: " << reinterpret_cast<const void*>(card_addr)
- << " begin: " << reinterpret_cast<void*>(mem_map_->Begin() + offset_)
- << " end: " << reinterpret_cast<void*>(mem_map_->End());
- uintptr_t offset = card_addr - biased_begin_;
- return reinterpret_cast<void*>(offset << GC_CARD_SHIFT);
- }
-
// Returns true iff the card table address is within the bounds of the card table.
bool IsValidCard(const byte* card_addr) const {
byte* begin = mem_map_->Begin() + offset_;
diff --git a/src/heap.cc b/src/heap.cc
index 459597a..9fbfa32 100644
--- a/src/heap.cc
+++ b/src/heap.cc
@@ -26,6 +26,7 @@
#include "debugger.h"
#include "image.h"
#include "mark_sweep.h"
+#include "mod_union_table.h"
#include "object.h"
#include "object_utils.h"
#include "os.h"
@@ -239,6 +240,11 @@
LOG(FATAL) << "Failed to create card table";
}
+ // Allocate the mod-union table
+ ModUnionTableBitmap* mod_union_table = new ModUnionTableBitmap(this);
+ mod_union_table->Init();
+ mod_union_table_ = mod_union_table;
+
live_bitmap_ = live_bitmap.release();
mark_bitmap_ = mark_bitmap.release();
card_table_ = card_table.release();
@@ -275,6 +281,7 @@
delete mark_bitmap_;
delete live_bitmap_;
delete card_table_;
+ delete mod_union_table_;
delete mark_stack_;
delete condition_;
delete lock_;
@@ -608,7 +615,7 @@
void Heap::CollectGarbageInternal(bool concurrent, bool clear_soft_references) {
lock_->AssertHeld();
- DCHECK(!is_gc_running_);
+ CHECK(!is_gc_running_);
is_gc_running_ = true;
TimingLogger timings("CollectGarbageInternal");
@@ -629,17 +636,16 @@
if (concurrent) {
card_table_->ClearNonImageSpaceCards(this);
+ timings.AddSplit("ClearNonImageSpaceCards");
}
+ // Clear image space cards and keep track of cards we cleared in the mod-union table.
+ mod_union_table_->ClearCards();
+
mark_sweep.MarkRoots();
timings.AddSplit("MarkRoots");
- if (!concurrent) {
- mark_sweep.ScanDirtyImageRoots();
- timings.AddSplit("ScanDirtyImageRoots");
- }
-
- // Roots are marked on the bitmap and the mark_stack is empty
+ // Roots are marked on the bitmap and the mark_stack is empty.
DCHECK(mark_sweep.IsMarkStackEmpty());
if (concurrent) {
@@ -651,7 +657,15 @@
timings.AddSplit("RootEnd");
}
- // Recursively mark all bits set in the non-image mark bitmap
+ // Processes the cards we cleared earlier and adds their objects into the mod-union table.
+ mod_union_table_->Update(&mark_sweep);
+ timings.AddSplit("UpdateModUnionBitmap");
+
+ // Scans all objects in the mod-union table.
+ mod_union_table_->MarkReferences(&mark_sweep);
+ timings.AddSplit("ProcessModUnionBitmap");
+
+ // Recursively mark all the non-image bits set in the mark bitmap.
mark_sweep.RecursiveMark();
timings.AddSplit("RecursiveMark");
@@ -665,8 +679,7 @@
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.
+ // Scan dirty objects, this is only required if we are not doing concurrent GC.
mark_sweep.RecursiveMarkDirtyObjects();
timings.AddSplit("RecursiveMarkDirtyObjects");
}
@@ -683,6 +696,11 @@
mark_sweep.VerifyImageRoots();
timings.AddSplit("VerifyImageRoots");
+ if (concurrent) {
+ thread_list->ResumeAll();
+ dirty_end = NanoTime();
+ }
+
mark_sweep.Sweep();
timings.AddSplit("Sweep");
@@ -691,35 +709,43 @@
GrowForUtilization();
timings.AddSplit("GrowForUtilization");
- thread_list->ResumeAll();
- dirty_end = NanoTime();
+
+ if (!concurrent) {
+ thread_list->ResumeAll();
+ dirty_end = NanoTime();
+ }
EnqueueClearedReferences(&cleared_references);
RequestHeapTrim();
timings.AddSplit("Finish");
- uint64_t t1 = NanoTime();
- uint64_t duration_ns = t1 - t0;
- bool gc_was_particularly_slow = duration_ns > MsToNs(50); // TODO: crank this down for concurrent.
- if (VLOG_IS_ON(gc) || gc_was_particularly_slow) {
+ if (VLOG_IS_ON(gc)) {
+ uint64_t t1 = NanoTime();
+
// TODO: somehow make the specific GC implementation (here MarkSweep) responsible for logging.
// Reason: For CMS sometimes initial_size < num_bytes_allocated_ results in overflow (3GB freed message).
size_t bytes_freed = initial_size - num_bytes_allocated_;
- // lose low nanoseconds in duration. TODO: make this part of PrettyDuration
- duration_ns = (duration_ns / 1000) * 1000;
+ uint64_t duration_ns = t1 - t0;
+ duration_ns -= duration_ns % 1000;
+
+ // If the GC was slow, then print timings in the log.
if (concurrent) {
uint64_t pause_roots_time = (root_end - t0) / 1000 * 1000;
uint64_t pause_dirty_time = (dirty_end - dirty_begin) / 1000 * 1000;
- LOG(INFO) << "GC freed " << PrettySize(bytes_freed) << ", " << GetPercentFree() << "% free, "
- << PrettySize(num_bytes_allocated_) << "/" << PrettySize(GetTotalMemory()) << ", "
- << "paused " << PrettyDuration(pause_roots_time) << "+" << PrettyDuration(pause_dirty_time)
- << ", total " << PrettyDuration(duration_ns);
+ if (pause_roots_time > MsToNs(5) || pause_dirty_time > MsToNs(5)) {
+ LOG(INFO) << "GC freed " << PrettySize(bytes_freed) << ", " << GetPercentFree() << "% free, "
+ << PrettySize(num_bytes_allocated_) << "/" << PrettySize(GetTotalMemory()) << ", "
+ << "paused " << PrettyDuration(pause_roots_time) << "+" << PrettyDuration(pause_dirty_time)
+ << ", total " << PrettyDuration(duration_ns);
+ }
} else {
- uint64_t markSweepTime = (dirty_end - t0) / 1000 * 1000;
- LOG(INFO) << "GC freed " << PrettySize(bytes_freed) << ", " << GetPercentFree() << "% free, "
- << PrettySize(num_bytes_allocated_) << "/" << PrettySize(GetTotalMemory()) << ", "
- << "paused " << PrettyDuration(markSweepTime)
- << ", total " << PrettyDuration(duration_ns);
+ if (duration_ns > MsToNs(50)) {
+ uint64_t markSweepTime = (dirty_end - t0) / 1000 * 1000;
+ LOG(INFO) << "GC freed " << PrettySize(bytes_freed) << ", " << GetPercentFree() << "% free, "
+ << PrettySize(num_bytes_allocated_) << "/" << PrettySize(GetTotalMemory()) << ", "
+ << "paused " << PrettyDuration(markSweepTime)
+ << ", total " << PrettyDuration(duration_ns);
+ }
}
}
Dbg::GcDidFinish();
diff --git a/src/heap.h b/src/heap.h
index 23053f5..b91868c 100644
--- a/src/heap.h
+++ b/src/heap.h
@@ -37,13 +37,14 @@
class HeapBitmap;
class ImageSpace;
class MarkStack;
+class ModUnionTable;
+class ModUnionTableBitmap;
class Object;
class Space;
class SpaceTest;
class Thread;
class LOCKABLE Heap {
- friend class ScopedHeapLock;
public:
static const size_t kInitialSize = 2 * MB;
@@ -287,6 +288,10 @@
HeapBitmap* live_bitmap_;
+ // TODO: Reduce memory usage, this bitmap currently takes 1 bit per 8 bytes
+ // of image space.
+ ModUnionTable* mod_union_table_;
+
CardTable* card_table_;
// Used by the image writer to disable card marking on copied objects
@@ -341,6 +346,7 @@
bool verify_objects_;
+ friend class ScopedHeapLock;
FRIEND_TEST(SpaceTest, AllocAndFree);
FRIEND_TEST(SpaceTest, AllocAndFreeList);
friend class SpaceTest;
diff --git a/src/heap_bitmap.h b/src/heap_bitmap.h
index aaa764a..34c11b9 100644
--- a/src/heap_bitmap.h
+++ b/src/heap_bitmap.h
@@ -24,6 +24,7 @@
#include "globals.h"
#include "logging.h"
#include "mem_map.h"
+#include "utils.h"
namespace art {
@@ -88,6 +89,45 @@
void VisitRange(uintptr_t base, uintptr_t max, Callback* visitor, void* arg) const;
+ class ClearVisitor {
+ public:
+ explicit ClearVisitor(HeapBitmap* const bitmap)
+ : bitmap_(bitmap) {
+ }
+
+ void operator ()(Object* obj) const {
+ bitmap_->Clear(obj);
+ }
+ private:
+ HeapBitmap* const bitmap_;
+ };
+
+ template <typename Visitor>
+ void VisitRange(uintptr_t visit_begin, uintptr_t visit_end, const Visitor& visitor) const {
+ for (; visit_begin < visit_end; visit_begin += kAlignment ) {
+ visitor(reinterpret_cast<Object*>(visit_begin));
+ }
+ }
+
+ template <typename Visitor>
+ void VisitMarkedRange(uintptr_t visit_begin, uintptr_t visit_end, const Visitor& visitor) const {
+ size_t start = HB_OFFSET_TO_INDEX(visit_begin - heap_begin_);
+ size_t end = HB_OFFSET_TO_INDEX(visit_end - heap_begin_ - 1);
+ for (size_t i = start; i <= end; i++) {
+ word w = bitmap_begin_[i];
+ if (w != 0) {
+ word high_bit = 1 << (kBitsPerWord - 1);
+ uintptr_t ptr_base = HB_INDEX_TO_OFFSET(i) + heap_begin_;
+ do {
+ const int shift = CLZ(w);
+ Object* obj = reinterpret_cast<Object*>(ptr_base + shift * kAlignment);
+ visitor(obj);
+ w &= ~(high_bit >> shift);
+ } while (w != 0);
+ }
+ }
+ }
+
void Walk(Callback* callback, void* arg);
void InOrderWalk(HeapBitmap::Callback* callback, void* arg);
diff --git a/src/mark_sweep.cc b/src/mark_sweep.cc
index 25b5c6b..63801a1 100644
--- a/src/mark_sweep.cc
+++ b/src/mark_sweep.cc
@@ -63,7 +63,7 @@
// TODO: check that the mark bitmap is entirely clear.
}
-inline void MarkSweep::MarkObject0(const Object* obj, bool check_finger) {
+void MarkSweep::MarkObject0(const Object* obj, bool check_finger) {
DCHECK(obj != NULL);
if (obj < condemned_) {
DCHECK(IsMarked(obj));
@@ -85,7 +85,7 @@
// objects. Any newly-marked objects whose addresses are lower than
// the finger won't be visited by the bitmap scan, so those objects
// need to be added to the mark stack.
-inline void MarkSweep::MarkObject(const Object* obj) {
+void MarkSweep::MarkObject(const Object* obj) {
if (obj != NULL) {
MarkObject0(obj, true);
}
@@ -115,11 +115,41 @@
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
+ // Sanity tests
+ DCHECK(mark_sweep->live_bitmap_->Test(root));
mark_sweep->MarkObject0(root, false);
mark_sweep->ScanObject(root);
}
+class CheckObjectVisitor {
+ public:
+ CheckObjectVisitor(MarkSweep* const mark_sweep)
+ : mark_sweep_(mark_sweep) {
+
+ }
+
+ void operator ()(const Object* obj, const Object* ref, MemberOffset offset, bool is_static) const {
+ mark_sweep_->CheckReference(obj, ref, offset, is_static);
+ }
+
+ private:
+ MarkSweep* const mark_sweep_;
+};
+
+void MarkSweep::CheckObject(const Object* obj) {
+ DCHECK(obj != NULL);
+ CheckObjectVisitor visitor(this);
+ VisitObjectReferences(obj, visitor);
+}
+
+void MarkSweep::VerifyImageRootVisitor(Object* root, void* arg) {
+ DCHECK(root != NULL);
+ DCHECK(arg != NULL);
+ MarkSweep* mark_sweep = reinterpret_cast<MarkSweep*>(arg);
+ DCHECK(mark_sweep->IsMarked(root));
+ mark_sweep->CheckObject(root);
+}
+
// Marks all objects that are in images and have been touched by the mutator
void MarkSweep::ScanDirtyImageRoots() {
const std::vector<Space*>& spaces = heap_->GetSpaces();
@@ -139,6 +169,11 @@
mark_sweep->CheckObject(obj);
}
+void MarkSweep::CheckBitmapNoFingerCallback(Object* obj, void* arg) {
+ MarkSweep* mark_sweep = reinterpret_cast<MarkSweep*>(arg);
+ mark_sweep->CheckObject(obj);
+}
+
void MarkSweep::ScanBitmapCallback(Object* obj, void* finger, void* arg) {
MarkSweep* mark_sweep = reinterpret_cast<MarkSweep*>(arg);
mark_sweep->finger_ = reinterpret_cast<Object*>(finger);
@@ -180,7 +215,7 @@
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);
+ live_bitmap_->ScanWalk(begin, end, &MarkSweep::CheckBitmapCallback, arg);
}
}
finger_ = reinterpret_cast<Object*>(~0);
@@ -280,6 +315,8 @@
void MarkSweep::Sweep() {
SweepSystemWeaks();
+ DCHECK(mark_stack_->IsEmpty());
+
const std::vector<Space*>& spaces = heap_->GetSpaces();
SweepCallbackContext scc;
scc.heap = heap_;
@@ -302,21 +339,12 @@
ScanFields(obj, klass->GetReferenceInstanceOffsets(), false);
}
-inline void MarkSweep::CheckInstanceFields(const Object* obj) {
- Class* klass = obj->GetClass();
- CheckFields(obj, klass->GetReferenceInstanceOffsets(), false);
-}
-
// Scans static storage on a Class.
inline void MarkSweep::ScanStaticFields(const Class* klass) {
DCHECK(klass != NULL);
ScanFields(klass, klass->GetReferenceStaticOffsets(), true);
}
-inline void MarkSweep::CheckStaticFields(const Class* klass) {
- CheckFields(klass, klass->GetReferenceStaticOffsets(), true);
-}
-
inline void MarkSweep::ScanFields(const Object* obj, uint32_t ref_offsets, bool is_static) {
if (ref_offsets != CLASS_WALK_SUPER) {
// Found a reference offset bitmap. Mark the specified offsets.
@@ -350,9 +378,11 @@
}
}
-inline void MarkSweep::CheckReference(const Object* obj, const Object* ref, MemberOffset offset, bool is_static) {
+void MarkSweep::CheckReference(const Object* obj, const Object* ref, MemberOffset offset, bool is_static) {
AllocSpace* alloc_space = heap_->GetAllocSpace();
if (alloc_space->Contains(ref)) {
+ DCHECK(IsMarked(obj));
+
bool is_marked = mark_bitmap_->Test(ref);
if (!is_marked) {
@@ -389,39 +419,6 @@
}
}
-inline void MarkSweep::CheckFields(const Object* obj, uint32_t ref_offsets, bool is_static) {
- if (ref_offsets != CLASS_WALK_SUPER) {
- // Found a reference offset bitmap. Mark the specified offsets.
- while (ref_offsets != 0) {
- size_t right_shift = CLZ(ref_offsets);
- MemberOffset field_offset = CLASS_OFFSET_FROM_CLZ(right_shift);
- const Object* ref = obj->GetFieldObject<const Object*>(field_offset, false);
- CheckReference(obj, ref, field_offset, is_static);
- ref_offsets &= ~(CLASS_HIGH_BIT >> right_shift);
- }
- } else {
- // There is no reference offset bitmap. In the non-static case,
- // walk up the class inheritance hierarchy and find reference
- // offsets the hard way. In the static case, just consider this
- // class.
- for (const Class* klass = is_static ? obj->AsClass() : obj->GetClass();
- klass != NULL;
- klass = is_static ? NULL : klass->GetSuperClass()) {
- size_t num_reference_fields = (is_static
- ? klass->NumReferenceStaticFields()
- : klass->NumReferenceInstanceFields());
- for (size_t i = 0; i < num_reference_fields; ++i) {
- Field* field = (is_static
- ? klass->GetStaticField(i)
- : klass->GetInstanceField(i));
- MemberOffset field_offset = field->GetOffset();
- const Object* ref = obj->GetFieldObject<const Object*>(field_offset, false);
- CheckReference(obj, ref, field_offset, is_static);
- }
- }
- }
-}
-
// Scans the header, static field references, and interface pointers
// of a class object.
inline void MarkSweep::ScanClass(const Object* obj) {
@@ -432,11 +429,6 @@
ScanStaticFields(obj->AsClass());
}
-inline void MarkSweep::CheckClass(const Object* obj) {
- CheckInstanceFields(obj);
- CheckStaticFields(obj->AsClass());
-}
-
// Scans the header of all array objects. If the array object is
// specialized to a reference type, scans the array data as well.
inline void MarkSweep::ScanArray(const Object* obj) {
@@ -453,19 +445,6 @@
}
}
-inline void MarkSweep::CheckArray(const Object* obj) {
- CheckReference(obj, obj->GetClass(), Object::ClassOffset(), false);
- if (obj->IsObjectArray()) {
- const ObjectArray<Object>* array = obj->AsObjectArray<Object>();
- for (int32_t i = 0; i < array->GetLength(); ++i) {
- const Object* element = array->GetWithoutChecks(i);
- size_t width = sizeof(Object*);
- CheckReference(obj, element, MemberOffset(i * width +
- Array::DataOffset(width).Int32Value()), false);
- }
- }
-}
-
// Process the "referent" field in a java.lang.ref.Reference. If the
// referent has not yet been marked, put it on the appropriate list in
// the gcHeap for later processing.
@@ -505,10 +484,6 @@
}
}
-inline void MarkSweep::CheckOther(const Object* obj) {
- CheckInstanceFields(obj);
-}
-
// Scans an object reference. Determines the type of the reference
// and dispatches to a specialized scanning routine.
inline void MarkSweep::ScanObject(const Object* obj) {
@@ -524,20 +499,6 @@
}
}
-// Check to see that all alloc space references are marked for the given object
-inline void MarkSweep::CheckObject(const Object* obj) {
- DCHECK(obj != NULL);
- DCHECK(obj->GetClass() != NULL);
- DCHECK(IsMarked(obj));
- if (obj->IsClass()) {
- CheckClass(obj);
- } else if (obj->IsArrayInstance()) {
- CheckArray(obj);
- } else {
- CheckOther(obj);
- }
-}
-
// Scan anything that's on the mark stack.
void MarkSweep::ProcessMarkStack() {
Space* alloc_space = heap_->GetAllocSpace();
@@ -557,6 +518,9 @@
DCHECK(list != NULL);
Object* clear = NULL;
size_t counter = 0;
+
+ DCHECK(mark_stack_->IsEmpty());
+
while (*list != NULL) {
Object* ref = heap_->DequeuePendingReference(list);
Object* referent = heap_->GetReferenceReferent(ref);
diff --git a/src/mark_sweep.h b/src/mark_sweep.h
index 7b0272c..00fdcfb 100644
--- a/src/mark_sweep.h
+++ b/src/mark_sweep.h
@@ -20,12 +20,18 @@
#include "macros.h"
#include "mark_stack.h"
#include "heap_bitmap.h"
+#include "object.h"
#include "offsets.h"
namespace art {
+class CheckObjectVisitor;
class Class;
class Heap;
+class MarkIfReachesAllocspaceVisitor;
+class ModUnionClearCardVisitor;
+class ModUnionVisitor;
+class ModUnionTableBitmap;
class Object;
class MarkSweep {
@@ -90,6 +96,8 @@
static void ScanImageRootVisitor(Object* root, void* arg);
+ static void VerifyImageRootVisitor(Object* root, void* arg);
+
static void ScanDirtyCardCallback(Object* obj, void* arg);
// Marks an object.
@@ -102,6 +110,8 @@
static void CheckBitmapCallback(Object* obj, void* finger, void* arg);
+ static void CheckBitmapNoFingerCallback(Object* obj, void* arg);
+
static void SweepCallback(size_t num_ptrs, Object** ptrs, void* arg);
void CheckReference(const Object* obj, const Object* ref, MemberOffset offset, bool is_static);
@@ -111,34 +121,107 @@
void CheckObject(const Object* obj);
+ template <typename Visitor>
+ void VisitObjectReferences(const Object* obj, const Visitor& visitor) {
+ DCHECK(obj != NULL);
+ DCHECK(obj->GetClass() != NULL);
+ if (obj->IsClass()) {
+ VisitClassReferences(obj, visitor);
+ } else if (obj->IsArrayInstance()) {
+ VisitArrayReferences(obj, visitor);
+ } else {
+ VisitOtherReferences(obj, visitor);
+ }
+ }
+
// Grays references in instance fields.
void ScanInstanceFields(const Object* obj);
- void CheckInstanceFields(const Object* obj);
+ template <typename Visitor>
+ void VisitInstanceFieldsReferences(const Object* obj, const Visitor& visitor) {
+ DCHECK(obj != NULL);
+ Class* klass = obj->GetClass();
+ DCHECK(klass != NULL);
+ VisitFieldsReferences(obj, klass->GetReferenceInstanceOffsets(), false, visitor);
+ }
// Blackens a class object.
void ScanClass(const Object* obj);
- void CheckClass(const Object* obj);
+ template <typename Visitor>
+ void VisitClassReferences(const Object* obj, const Visitor& visitor) {
+ VisitInstanceFieldsReferences(obj, visitor);
+ VisitStaticFieldsReferences(obj->AsClass(), visitor);
+ }
// Grays references in static fields.
void ScanStaticFields(const Class* klass);
- void CheckStaticFields(const Class* klass);
+ template <typename Visitor>
+ void VisitStaticFieldsReferences(const Class* klass, const Visitor& visitor) {
+ DCHECK(klass != NULL);
+ VisitFieldsReferences(klass, klass->GetReferenceStaticOffsets(), true, visitor);
+ }
// Used by ScanInstanceFields and ScanStaticFields
void ScanFields(const Object* obj, uint32_t ref_offsets, bool is_static);
- void CheckFields(const Object* obj, uint32_t ref_offsets, bool is_static);
+ template <typename Visitor>
+ void VisitFieldsReferences(const Object* obj, uint32_t ref_offsets, bool is_static, const Visitor& visitor) {
+ if (ref_offsets != CLASS_WALK_SUPER) {
+ // Found a reference offset bitmap. Mark the specified offsets.
+ while (ref_offsets != 0) {
+ size_t right_shift = CLZ(ref_offsets);
+ MemberOffset field_offset = CLASS_OFFSET_FROM_CLZ(right_shift);
+ const Object* ref = obj->GetFieldObject<const Object*>(field_offset, false);
+ visitor(obj, ref, field_offset, is_static);
+ ref_offsets &= ~(CLASS_HIGH_BIT >> right_shift);
+ }
+ } else {
+ // There is no reference offset bitmap. In the non-static case,
+ // walk up the class inheritance hierarchy and find reference
+ // offsets the hard way. In the static case, just consider this
+ // class.
+ for (const Class* klass = is_static ? obj->AsClass() : obj->GetClass();
+ klass != NULL;
+ klass = is_static ? NULL : klass->GetSuperClass()) {
+ size_t num_reference_fields = (is_static
+ ? klass->NumReferenceStaticFields()
+ : klass->NumReferenceInstanceFields());
+ for (size_t i = 0; i < num_reference_fields; ++i) {
+ Field* field = (is_static
+ ? klass->GetStaticField(i)
+ : klass->GetInstanceField(i));
+ MemberOffset field_offset = field->GetOffset();
+ const Object* ref = obj->GetFieldObject<const Object*>(field_offset, false);
+ visitor(obj, ref, field_offset, is_static);
+ }
+ }
+ }
+ }
// Grays references in an array.
void ScanArray(const Object* obj);
- void CheckArray(const Object* obj);
+ template <typename Visitor>
+ void VisitArrayReferences(const Object* obj, const Visitor& visitor) {
+ visitor(obj, obj->GetClass(), Object::ClassOffset(), false);
+ if (obj->IsObjectArray()) {
+ const ObjectArray<Object>* array = obj->AsObjectArray<Object>();
+ for (int32_t i = 0; i < array->GetLength(); ++i) {
+ const Object* element = array->GetWithoutChecks(i);
+ size_t width = sizeof(Object*);
+ visitor(obj, element, MemberOffset(i * width + Array::DataOffset(width).Int32Value()), false);
+ }
+ }
+ }
void ScanOther(const Object* obj);
- void CheckOther(const Object* obj);
+ template <typename Visitor>
+ void VisitOtherReferences(const Object* obj, const Visitor& visitor) {
+ return VisitInstanceFieldsReferences(obj, visitor);
+ }
// Blackens objects grayed during a garbage collection.
void ScanGrayObjects();
@@ -187,7 +270,12 @@
size_t array_count_;
size_t other_count_;
+ friend class CheckObjectVisitor;
friend class InternTableEntryIsUnmarked;
+ friend class MarkIfReachesAllocspaceVisitor;
+ friend class ModUnionClearCardVisitor;
+ friend class ModUnionVisitor;
+ friend class ModUnionTableBitmap;
DISALLOW_COPY_AND_ASSIGN(MarkSweep);
};
diff --git a/src/mod_union_table.cc b/src/mod_union_table.cc
new file mode 100644
index 0000000..c73dd6b
--- /dev/null
+++ b/src/mod_union_table.cc
@@ -0,0 +1,161 @@
+/*
+ * Copyright (C) 2012 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.
+ */
+
+#include "heap.h"
+#include "heap_bitmap.h"
+#include "mark_sweep.h"
+#include "mod_union_table.h"
+#include "space.h"
+#include "stl_util.h"
+#include "UniquePtr.h"
+
+namespace art {
+
+class MarkIfReachesAllocspaceVisitor {
+ public:
+ explicit MarkIfReachesAllocspaceVisitor(MarkSweep* const mark_sweep, HeapBitmap* bitmap)
+ : mark_sweep_(mark_sweep),
+ bitmap_(bitmap) {
+ }
+
+ // Extra parameters are required since we use this same visitor signature for checking objects.
+ void operator ()(const Object* obj, const Object* ref, MemberOffset offset, bool is_static) const {
+ if (mark_sweep_->heap_->GetAllocSpace()->Contains(ref)) {
+ // This can mark the same object multiple times, but is unlikely to be a performance problem.
+ bitmap_->Set(obj);
+ }
+ // Avoid warnings.
+ (void)obj;(void)offset;(void)is_static;
+ }
+
+ private:
+ MarkSweep* const mark_sweep_;
+ HeapBitmap* bitmap_;
+};
+
+class ModUnionVisitor {
+ public:
+ explicit ModUnionVisitor(MarkSweep* const mark_sweep, HeapBitmap* bitmap)
+ : mark_sweep_(mark_sweep),
+ bitmap_(bitmap) {
+ }
+
+ void operator ()(Object* obj) const {
+ DCHECK(obj != NULL);
+ // We don't have an early exit since we use the visitor pattern, an early
+ // exit should significantly speed this up.
+ MarkIfReachesAllocspaceVisitor visitor(mark_sweep_, bitmap_);
+ mark_sweep_->VisitObjectReferences(obj, visitor);
+ }
+ private:
+ MarkSweep* const mark_sweep_;
+ HeapBitmap* bitmap_;
+};
+
+class ModUnionClearCardVisitor {
+ public:
+ explicit ModUnionClearCardVisitor(std::vector<byte*>* cleared_cards)
+ : cleared_cards_(cleared_cards) {
+ }
+
+ void operator ()(byte* card) const {
+ cleared_cards_->push_back(card);
+ }
+ private:
+ std::vector<byte*>* cleared_cards_;
+};
+
+ModUnionTableBitmap::ModUnionTableBitmap(Heap* heap) : heap_(heap) {
+ // Prevent fragmentation of the heap which is caused by resizing of the vector.
+ // TODO: Make a new vector which uses madvise (basically same as a mark stack).
+ cleared_cards_.reserve(4 * KB);
+}
+
+ModUnionTableBitmap::~ModUnionTableBitmap() {
+ STLDeleteValues(&bitmaps_);
+}
+
+void ModUnionTableBitmap::Init() {
+ const std::vector<Space*>& spaces = heap_->GetSpaces();
+
+ // Create one heap bitmap per image space.
+ for (size_t i = 0; i < spaces.size(); ++i) {
+ if (spaces[i]->IsImageSpace()) {
+ // Allocate the mod-union table
+ // The mod-union table is only needed when we have an image space since it's purpose is to cache image roots.
+ UniquePtr<HeapBitmap> bitmap(HeapBitmap::Create("mod-union table bitmap", spaces[i]->Begin(), spaces[i]->Capacity()));
+ if (bitmap.get() == NULL) {
+ LOG(FATAL) << "Failed to create mod-union bitmap";
+ }
+
+ bitmaps_.Put(spaces[i], bitmap.release());
+ }
+ }
+}
+
+void ModUnionTableBitmap::ClearCards() {
+ CardTable* card_table = heap_->GetCardTable();
+ for (BitmapMap::iterator cur = bitmaps_.begin(); cur != bitmaps_.end(); ++cur) {
+ const Space* space = cur->first;
+ ModUnionClearCardVisitor visitor(&cleared_cards_);
+ // Clear dirty cards in the this image space and update the corresponding mod-union bits.
+ card_table->VisitClear(space->Begin(), space->End(), visitor);
+ }
+}
+
+void ModUnionTableBitmap::Update(MarkSweep* mark_sweep) {
+ CardTable* card_table = heap_->GetCardTable();
+
+ while (!cleared_cards_.empty()) {
+ byte* card = cleared_cards_.back();
+ cleared_cards_.pop_back();
+
+ // Find out which bitmap the card maps to.
+ HeapBitmap* bitmap = 0;
+ for (BitmapMap::iterator cur = bitmaps_.begin(); cur != bitmaps_.end(); ++cur) {
+ if (cur->first->Contains(reinterpret_cast<Object*>(card_table->AddrFromCard(card)))) {
+ bitmap = cur->second;
+ break;
+ }
+ }
+ DCHECK(bitmap != NULL);
+
+ uintptr_t start = reinterpret_cast<uintptr_t>(card_table->AddrFromCard(card));
+ uintptr_t end = reinterpret_cast<uintptr_t>(card_table->AddrFromCard(card + 1));
+
+ // Clear the mod-union bitmap range corresponding to this card so that we
+ // don't have any objects marked which do not reach the alloc space.
+ bitmap->VisitRange(start, end, HeapBitmap::ClearVisitor(bitmap));
+
+ // At this point we need to update the mod-union bitmap to contain all the
+ // objects which reach the alloc space.
+ ModUnionVisitor visitor(mark_sweep, bitmap);
+ heap_->GetLiveBits()->VisitMarkedRange(start, end, visitor);
+ }
+}
+
+void ModUnionTableBitmap::MarkReferences(MarkSweep* mark_sweep) {
+ // Some tests have no image space, and therefore no mod-union bitmap.
+ for (BitmapMap::iterator cur = bitmaps_.begin(); cur != bitmaps_.end(); ++cur) {
+ const Space* space = cur->first;
+ uintptr_t begin = reinterpret_cast<uintptr_t>(space->Begin());
+ uintptr_t end = reinterpret_cast<uintptr_t>(space->End());
+ cur->second->VisitRange(begin, end, MarkSweep::ScanImageRootVisitor, mark_sweep);
+ }
+}
+
+} // namespace art
+
diff --git a/src/mod_union_table.h b/src/mod_union_table.h
new file mode 100644
index 0000000..2f4ca5f
--- /dev/null
+++ b/src/mod_union_table.h
@@ -0,0 +1,74 @@
+/*
+ * Copyright (C) 2012 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.
+ */
+
+#ifndef ART_SRC_MOD_UNION_TABLE_H_
+#define ART_SRC_MOD_UNION_TABLE_H_
+
+#include "safe_map.h"
+
+namespace art {
+
+class Heap;
+class HeapBitmap;
+class Space;
+
+class ModUnionTable {
+ public:
+ // Clear cards image space cards.
+ virtual void ClearCards() = 0;
+
+ // Update the mod-union table.
+ virtual void Update(MarkSweep* mark_sweep) = 0;
+
+ // Mark all references to the alloc space(s).
+ virtual void MarkReferences(MarkSweep* mark_sweep) = 0;
+
+ virtual ~ModUnionTable() {
+
+ }
+};
+
+// Bitmap implementation.
+class ModUnionTableBitmap : public ModUnionTable {
+ public:
+ ModUnionTableBitmap(Heap* heap);
+ virtual ~ModUnionTableBitmap();
+
+ void Init();
+
+ // Clear image space cards.
+ void ClearCards();
+
+ // Update table based on cleared cards.
+ void Update(MarkSweep* mark_sweep);
+
+ // Mark all references to the alloc space(s).
+ void MarkReferences(MarkSweep* mark_sweep);
+ private:
+ // Cleared card array, used to update the mod-union table.
+ std::vector<byte*> cleared_cards_;
+
+ // One bitmap per image space.
+ // TODO: Add support for zygote spaces?
+ typedef SafeMap<const Space*, HeapBitmap*> BitmapMap;
+ BitmapMap bitmaps_;
+
+ Heap* heap_;
+};
+
+} // namespace art
+
+#endif // ART_SRC_MOD_UNION_TABLE_H_
