Use the card marks to find gray objects during a concurrent collection.
Presently, the garbage collector scans the mark bits looking for gray
objects. As of this change, only objects spanning dirty cards will be
reexamined during re-marking.
As part of this change, re-marking of roots will push objects onto the
mark stack instead of setting their mark bits. The number of gray
roots discovered during re-marking is small. If this changes we can
dirty the cards instead and let re-scanning push the gray objects.
Change-Id: If270812821e070d09af344edb63dfede26d10410
diff --git a/vm/alloc/CardTable.c b/vm/alloc/CardTable.c
index 45fc1d4..bd8de9a 100644
--- a/vm/alloc/CardTable.c
+++ b/vm/alloc/CardTable.c
@@ -38,21 +38,6 @@
* ObjectInlines.h [such as dvmSetFieldObject] do this for you. The
* JIT and fast interpreters also contain code to mark cards as dirty.
*
- * [TODO: Concurrent collection will have to expand on this, as it
- * uses the card table as well.]
- *
- * The card table is used to support partial collection, which at the
- * moment means "treat the zygote's heap as permanent, and only GC
- * objects in the application heap". In order to do this efficiently,
- * the GC need to find quickly references to objects in the
- * application heap from the zygote heap. When an application creates
- * an object and stores it into an object on the zygote heap, it will
- * mark the corresponding card in the zygote heap as "dirty". When the
- * GC does a partial collection, it can efficiently find all the
- * cross-heap objects, since they are all on dirty cards. The GC also
- * takes the opportunity to mark as "clean" any cards which are dirty,
- * but no longer contain cross-heap pointers.
- *
* The card table's base [the "biased card table"] gets set to a
* rather strange value. In order to keep the JIT from having to
* fabricate or load GC_DIRTY_CARD to store into the card table,
@@ -109,6 +94,12 @@
munmap(gDvm.gcHeap->cardTableBase, gDvm.gcHeap->cardTableLength);
}
+void dvmClearCardTable(void)
+{
+ assert(gDvm.gcHeap->cardTableBase != NULL);
+ memset(gDvm.gcHeap->cardTableBase, GC_CARD_CLEAN, gDvm.gcHeap->cardTableLength);
+}
+
/*
* Returns true iff the address is within the bounds of the card table.
*/
@@ -149,92 +140,3 @@
u1 *cardAddr = dvmCardFromAddr(addr);
*cardAddr = GC_CARD_DIRTY;
}
-
-/*
- * Returns true iff all address within the Object are on unmarked cards.
- */
-static bool objectIsClean(const Object *obj)
-{
- assert(dvmIsValidObject(obj));
- size_t size = dvmHeapSourceChunkSize(obj);
- u1 *start = dvmCardFromAddr(obj);
- u1 *end = dvmCardFromAddr((char *)obj + size-1);
- u1 *index;
-
- for (index = start; index <= end; index++) {
- if (*index != GC_CARD_CLEAN) {
- return false;
- }
- }
- return true;
-}
-
-/*
- * A Visitor callback in support of checkCleanObjects. "arg" is
- * expected to be the immuneLimit.
- */
-static void crossGenCheckVisitor(void *ptr, void *arg)
-{
- Object *ref = *(Object **)ptr;
- Object *immuneLimit = (Object *)arg;
-
- if (ref >= immuneLimit) {
- LOGE("Clean obj contains threatened ref %p: %p", ptr, ref);
- dvmAbort();
- }
-}
-
-/*
- * A HeapBitmap callback in support of checkCleanObjects.
- */
-static bool crossGenCheckCallback(size_t numPtrs, void **ptrs,
- const void *finger, void *arg)
-{
- size_t i;
- for (i = 0; i < numPtrs; i++) {
- Object *obj = ptrs[i];
- if (objectIsClean(obj)) {
- dvmVisitObject(crossGenCheckVisitor, obj, arg);
- }
- }
-
- return true;
-}
-
-/*
- * dvmAbort if any clean object in the Zygote heap contains a
- * reference to the application heap, or if the immune limit is not as
- * expected.
- */
-void dvmVerifyCardTable(void)
-{
- HeapBitmap markBits[HEAP_SOURCE_MAX_HEAP_COUNT];
- HeapBitmap liveBits[HEAP_SOURCE_MAX_HEAP_COUNT];
- size_t numBitmaps;
- void *immuneLimit;
- numBitmaps = dvmHeapSourceGetNumHeaps();
- if (numBitmaps < 2) {
- return;
- }
- if (numBitmaps > 2) {
- LOGE("More heaps than expected.");
- dvmAbort();
- }
- immuneLimit = dvmHeapSourceGetImmuneLimit(GC_PARTIAL);
- dvmHeapSourceGetObjectBitmaps(liveBits, markBits, numBitmaps);
- if (markBits[0].base <= markBits[1].base) {
- LOGE("Heaps are not in the expected order.");
- dvmAbort();
- }
- if (markBits[0].base < (uintptr_t)immuneLimit ||
- markBits[0].max < (uintptr_t)immuneLimit) {
- LOGE("Application heap should not be immune.");
- dvmAbort();
- }
- if (markBits[1].base >= (uintptr_t)immuneLimit ||
- markBits[1].max >= (uintptr_t)immuneLimit) {
- LOGE("Zygote heap should not be threatened.");
- dvmAbort();
- }
- dvmHeapBitmapWalk(&markBits[1], crossGenCheckCallback, immuneLimit);
-}
diff --git a/vm/alloc/CardTable.h b/vm/alloc/CardTable.h
index 4c4bee6..7a86bd0 100644
--- a/vm/alloc/CardTable.h
+++ b/vm/alloc/CardTable.h
@@ -44,6 +44,11 @@
void dvmCardTableShutdown(void);
/*
+ * Resets all of the bytes in the card table to clean.
+ */
+void dvmClearCardTable(void);
+
+/*
* Returns the address of the relevent byte in the card table, given
* an address on the heap.
*/
diff --git a/vm/alloc/Heap.c b/vm/alloc/Heap.c
index 02eb920..f063b45 100644
--- a/vm/alloc/Heap.c
+++ b/vm/alloc/Heap.c
@@ -25,6 +25,7 @@
#include "alloc/DdmHeap.h"
#include "alloc/HeapSource.h"
#include "alloc/MarkSweep.h"
+#include "alloc/Visit.h"
#include "utils/threads.h" // need Android thread priorities
#define kInvalidPriority 10000
@@ -582,11 +583,10 @@
/*
* Scan every live object in the heap, holding the locks.
*/
-static void verifyHeap()
+static void verifyHeap(void)
{
- // TODO: check the locks.
- HeapBitmap *liveBits = dvmHeapSourceGetLiveBits();
- dvmVerifyBitmap(liveBits);
+ dvmVerifyRoots();
+ dvmVerifyBitmap(dvmHeapSourceGetLiveBits());
}
/*
@@ -757,6 +757,7 @@
* heap to allow mutator threads to allocate from free space.
*/
rootEnd = dvmGetRelativeTimeMsec();
+ dvmClearCardTable();
dvmUnlockHeap();
dvmResumeAllThreads(SUSPEND_FOR_GC);
rootSuspendTime = rootStart - suspendStart;
@@ -783,12 +784,12 @@
* As no barrier intercepts root updates, we conservatively
* assume all roots may be gray and re-mark them.
*/
- dvmHeapMarkRootSet();
+ dvmHeapReMarkRootSet();
/*
* Recursively mark gray objects pointed to by the roots or by
* heap objects dirtied during the concurrent mark.
*/
- dvmMarkDirtyObjects();
+ dvmHeapReScanMarkedObjects();
}
/* All strongly-reachable objects have now been marked.
diff --git a/vm/alloc/MarkSweep.c b/vm/alloc/MarkSweep.c
index 574a731..94179e4 100644
--- a/vm/alloc/MarkSweep.c
+++ b/vm/alloc/MarkSweep.c
@@ -112,8 +112,7 @@
}
static void
-markObjectNonNull(const Object *obj, GcMarkContext *ctx,
- bool checkFinger, bool forceStack)
+markObjectNonNull(const Object *obj, GcMarkContext *ctx, bool checkFinger)
{
assert(ctx != NULL);
assert(obj != NULL);
@@ -126,7 +125,7 @@
if (!setAndReturnMarkBit(ctx, obj)) {
/* This object was not previously marked.
*/
- if (forceStack || (checkFinger && (void *)obj < ctx->finger)) {
+ if (checkFinger && (void *)obj < ctx->finger) {
/* This object will need to go on the mark stack.
*/
MARK_STACK_PUSH(ctx->stack, obj);
@@ -149,7 +148,7 @@
static void markObject(const Object *obj, GcMarkContext *ctx)
{
if (obj != NULL) {
- markObjectNonNull(obj, ctx, true, false);
+ markObjectNonNull(obj, ctx, true);
}
}
@@ -166,7 +165,7 @@
dvmMarkObjectNonNull(const Object *obj)
{
assert(obj != NULL);
- markObjectNonNull(obj, &gDvm.gcHeap->markContext, false, false);
+ markObjectNonNull(obj, &gDvm.gcHeap->markContext, false);
}
/* Mark the set of root objects.
@@ -256,6 +255,32 @@
}
/*
+ * Callback applied to root references. If the root location contains
+ * a white reference it is pushed on the mark stack and grayed.
+ */
+static void markObjectVisitor(void *addr, void *arg)
+{
+ Object *obj;
+
+ assert(addr != NULL);
+ assert(arg != NULL);
+ obj = *(Object **)addr;
+ if (obj != NULL) {
+ markObjectNonNull(obj, arg, true);
+ }
+}
+
+/*
+ * Grays all references in the roots.
+ */
+void dvmHeapReMarkRootSet(void)
+{
+ GcMarkContext *ctx = &gDvm.gcHeap->markContext;
+ assert(ctx->finger == (void *)ULONG_MAX);
+ dvmVisitRoots(markObjectVisitor, ctx);
+}
+
+/*
* Nothing past this point is allowed to use dvmMarkObject() or
* dvmMarkObjectNonNull(), which are for root-marking only.
* Scanning/recursion must use markObject(), which takes the finger
@@ -524,6 +549,107 @@
}
}
+static size_t objectSize(const Object *obj)
+{
+ assert(dvmIsValidObject(obj));
+ assert(dvmIsValidObject((Object *)obj->clazz));
+ if (IS_CLASS_FLAG_SET(obj->clazz, CLASS_ISARRAY)) {
+ return dvmArrayObjectSize((ArrayObject *)obj);
+ } else if (obj->clazz == gDvm.classJavaLangClass) {
+ return dvmClassObjectSize((ClassObject *)obj);
+ } else {
+ return obj->clazz->objectSize;
+ }
+}
+
+/*
+ * Scans backward to the header of a marked object that spans the
+ * given address. Returns NULL if there is no spanning marked object.
+ */
+static Object *previousGrayObject(u1 *start, GcMarkContext *ctx)
+{
+ u1 *end = (u1 *)ctx->bitmap->base;
+ u1 *ptr;
+
+ assert(start >= end);
+ for (ptr = start; ptr >= end; ptr -= HB_OBJECT_ALIGNMENT) {
+ if (dvmIsValidObject((Object *)ptr))
+ break;
+ }
+ if (ptr < end || !isMarked(ptr, ctx)) {
+ return NULL;
+ } else {
+ Object *obj = (Object *)ptr;
+ size_t size = objectSize(obj);
+ if (ptr + size < start) {
+ return NULL;
+ }
+ return obj;
+ }
+}
+
+/*
+ * Scans forward to the header of the next marked object between start
+ * and limit. Returns NULL if no marked objects are in that region.
+ */
+static Object *nextGrayObject(u1 *base, u1 *limit, GcMarkContext *ctx)
+{
+ u1 *ptr;
+
+ assert(base < limit);
+ assert(limit - base <= GC_CARD_SIZE);
+ for (ptr = base; ptr < limit; ptr += HB_OBJECT_ALIGNMENT) {
+ if (isMarked(ptr, ctx))
+ return (Object *)ptr;
+ }
+ return NULL;
+}
+
+/*
+ * Scan the card table looking for objects that have been grayed by
+ * the mutator.
+ */
+static void scanGrayObjects(GcMarkContext *ctx)
+{
+ GcHeap *h = gDvm.gcHeap;
+ u1 *card, *baseCard, *limitCard;
+
+ baseCard = &h->cardTableBase[0];
+ limitCard = &h->cardTableBase[h->cardTableLength];
+ for (card = baseCard; card != limitCard; ++card) {
+ if (*card == GC_CARD_DIRTY) {
+ /*
+ * The card is dirty. Scan all of the objects that
+ * intersect with the card address.
+ */
+ u1 *addr = dvmAddrFromCard(card);
+ /*
+ * If the last object on the previous card terminates on
+ * the current card it is gray and must be scanned.
+ */
+ if (!dvmIsValidObject((Object *)addr)) {
+ Object *prev = previousGrayObject(addr, ctx);
+ if (prev != NULL) {
+ scanObject(prev, ctx);
+ }
+ }
+ /*
+ * Scan through all black objects that start on the
+ * current card.
+ */
+ u1 *limit = addr + GC_CARD_SIZE;
+ u1 *next = addr;
+ while (next < limit) {
+ Object *obj = nextGrayObject(next, limit, ctx);
+ if (obj == NULL)
+ break;
+ scanObject(obj, ctx);
+ next = (u1*)obj + HB_OBJECT_ALIGNMENT;
+ }
+ }
+ }
+}
+
#ifndef NDEBUG
static uintptr_t gLastFinger = 0;
#endif
@@ -573,43 +699,16 @@
LOG_SCAN("done with marked objects\n");
}
-/*
- * Callback applied to each gray object to blacken it.
- */
-static bool dirtyObjectCallback(size_t numPtrs, void **ptrs,
- const void *finger, void *arg)
+void dvmHeapReScanMarkedObjects(void)
{
- size_t i;
+ GcMarkContext *ctx = &gDvm.gcHeap->markContext;
- for (i = 0; i < numPtrs; ++i) {
- scanObject(ptrs[i], arg);
- }
- return true;
-}
-
-/*
- * Re-mark dirtied objects. Iterates through all blackened objects
- * looking for references to white objects.
- */
-void dvmMarkDirtyObjects(void)
-{
- HeapBitmap markBits[HEAP_SOURCE_MAX_HEAP_COUNT];
- HeapBitmap liveBits[HEAP_SOURCE_MAX_HEAP_COUNT];
- GcMarkContext *ctx;
- size_t numBitmaps;
- size_t i;
-
- ctx = &gDvm.gcHeap->markContext;
/*
* The finger must have been set to the maximum value to ensure
* that gray objects will be pushed onto the mark stack.
*/
assert(ctx->finger == (void *)ULONG_MAX);
- numBitmaps = dvmHeapSourceGetNumHeaps();
- dvmHeapSourceGetObjectBitmaps(liveBits, markBits, numBitmaps);
- for (i = 0; i < numBitmaps; i++) {
- dvmHeapBitmapWalk(&markBits[i], dirtyObjectCallback, ctx);
- }
+ scanGrayObjects(ctx);
processMarkStack(ctx);
}
diff --git a/vm/alloc/MarkSweep.h b/vm/alloc/MarkSweep.h
index e143b35..46066c6 100644
--- a/vm/alloc/MarkSweep.h
+++ b/vm/alloc/MarkSweep.h
@@ -47,8 +47,9 @@
bool dvmHeapBeginMarkStep(GcMode mode);
void dvmHeapMarkRootSet(void);
+void dvmHeapReMarkRootSet(void);
void dvmHeapScanMarkedObjects(void);
-void dvmMarkDirtyObjects(void);
+void dvmHeapReScanMarkedObjects(void);
void dvmHandleSoftRefs(Object **list);
void dvmClearWhiteRefs(Object **list);
void dvmHeapScheduleFinalizations(void);
diff --git a/vm/alloc/Visit.c b/vm/alloc/Visit.c
index 0124e29..9a799f2 100644
--- a/vm/alloc/Visit.c
+++ b/vm/alloc/Visit.c
@@ -201,5 +201,8 @@
visitLargeHeapRefTable(visitor, gDvm.gcHeap->referenceOperations, arg);
visitLargeHeapRefTable(visitor, gDvm.gcHeap->pendingFinalizationRefs, arg);
visitThreads(visitor, arg);
+ (*visitor)(&gDvm.outOfMemoryObj, arg);
+ (*visitor)(&gDvm.internalErrorObj, arg);
+ (*visitor)(&gDvm.noClassDefFoundErrorObj, arg);
/* TODO: visit cached global references. */
}
