Simplify the bitmap walker subroutines.
This change...
* Separates walking from sweeping. Walking had been implemented by a
sweeping with an empty mark bitmap argument.
* Localizes the finger machinations to scanBitmapCallback. There is
one use of the finger but all callbacks received the argument.
* Inlines a simplified bitmap walking routine operating a pointer at a
time. Only sweeping benefits from batching decoded addresses.
Change-Id: I87485ac58d3ecf07916f142534fe96f77e7ff227
diff --git a/vm/alloc/Alloc.c b/vm/alloc/Alloc.c
index 50f6ed9..02955bc 100644
--- a/vm/alloc/Alloc.c
+++ b/vm/alloc/Alloc.c
@@ -306,18 +306,14 @@
size_t count;
} CountInstancesOfClassContext;
-static void countInstancesOfClassCallback(size_t numPtrs, void **ptrs,
- const void *finger, void *arg)
+static void countInstancesOfClassCallback(void *ptr, void *arg)
{
CountInstancesOfClassContext *ctx = arg;
- size_t i;
+ const Object *obj = ptr;
assert(ctx != NULL);
- for (i = 0; i < numPtrs; ++i) {
- const Object *obj = ptrs[i];
- if (obj->clazz == ctx->clazz) {
- ctx->count += 1;
- }
+ if (obj->clazz == ctx->clazz) {
+ ctx->count += 1;
}
}
diff --git a/vm/alloc/CardTable.c b/vm/alloc/CardTable.c
index 4645a4d..06512ed 100644
--- a/vm/alloc/CardTable.c
+++ b/vm/alloc/CardTable.c
@@ -244,24 +244,21 @@
* table verification occurs weak references have yet to be blackened
* and so their containing objects are permitted to be gray.
*/
-static void verifyCardTableCallback(size_t numPtrs, void **ptrs,
- const void *finger, void *arg)
+static void verifyCardTableCallback(void *ptr, void *arg)
{
- size_t i;
+ Object *obj = ptr;
+ WhiteReferenceCounter ctx = { arg, 0 };
- for (i = 0; i < numPtrs; ++i) {
- Object *obj = ptrs[i];
- WhiteReferenceCounter ctx = { arg, 0 };
- dvmVisitObject(countWhiteReferenceVisitor, obj, &ctx);
- if (ctx.whiteRefs == 0) {
- continue;
- } else if (isObjectDirty(obj)) {
- continue;
- } else if (isReferentUnmarked(obj, &ctx)) {
- continue;
- } else if (isWeakInternedString(obj)) {
- continue;
- }
+ dvmVisitObject(countWhiteReferenceVisitor, obj, &ctx);
+ if (ctx.whiteRefs == 0) {
+ return;
+ } else if (isObjectDirty(obj)) {
+ return;
+ } else if (isReferentUnmarked(obj, &ctx)) {
+ return;
+ } else if (isWeakInternedString(obj)) {
+ return;
+ } else {
LOGE("Verify failed, object %p is gray", obj);
dvmDumpObject(obj);
dvmAbort();
diff --git a/vm/alloc/HeapBitmap.c b/vm/alloc/HeapBitmap.c
index 03269ba..08d5976 100644
--- a/vm/alloc/HeapBitmap.c
+++ b/vm/alloc/HeapBitmap.c
@@ -83,19 +83,11 @@
* object pointers that correspond to garbage objects. Call
* <callback> zero or more times with lists of these object pointers.
*
- * The <finger> argument to the callback indicates the next-highest
- * address that hasn't been visited yet; setting bits for objects whose
- * addresses are less than <finger> are not guaranteed to be seen by
- * the current walk.
- *
* The callback is permitted to increase the bitmap's max; the walk
* will use the updated max as a terminating condition,
- *
- * <finger> will be set to some value beyond the bitmap max when the
- * end of the bitmap is reached.
*/
void dvmHeapBitmapSweepWalk(const HeapBitmap *liveHb, const HeapBitmap *markHb,
- BitmapCallback *callback, void *callbackArg)
+ BitmapSweepCallback *callback, void *callbackArg)
{
static const size_t kPointerBufSize = 128;
void *pointerBuf[kPointerBufSize];
@@ -103,10 +95,10 @@
size_t index;
size_t i;
-#define FLUSH_POINTERBUF(finger_) \
+#define FLUSH_POINTERBUF() \
do { \
(*callback)(pb - pointerBuf, (void **)pointerBuf, \
- (void *)(finger_), callbackArg); \
+ callbackArg); \
pb = pointerBuf; \
} while (false)
@@ -126,8 +118,7 @@
/* Make sure that there are always enough slots available */ \
/* for an entire word of 1s. */ \
if (kPointerBufSize - (pb - pointerBuf) < HB_BITS_PER_WORD) { \
- FLUSH_POINTERBUF(ptrBase + \
- HB_BITS_PER_WORD * HB_OBJECT_ALIGNMENT); \
+ FLUSH_POINTERBUF(); \
if (update_index_) { \
/* The callback may have caused hb_->max to grow. */ \
index = HB_OFFSET_TO_INDEX(hb_->max - hb_->base); \
@@ -202,31 +193,8 @@
}
if (pb > pointerBuf) {
- /* Set the finger to the end of the heap (rather than
- * longHb->max) so that the callback doesn't expect to be
- * called again if it happens to change the current max.
- */
- uintptr_t finalFinger = longHb->base + HB_MAX_OFFSET(longHb);
- FLUSH_POINTERBUF(finalFinger);
- assert(finalFinger > longHb->max);
+ FLUSH_POINTERBUF();
}
#undef FLUSH_POINTERBUF
#undef DECODE_BITS
}
-
-/*
- * dvmHeapBitmapWalk is equivalent to dvmHeapBitmapSweepWalk with
- * nothing marked.
- */
-void dvmHeapBitmapWalk(const HeapBitmap *hb,
- BitmapCallback *callback, void *callbackArg)
-{
- /* Create an empty bitmap with the same extent as <hb>.
- * Don't actually allocate any memory.
- */
- HeapBitmap emptyHb = *hb;
- emptyHb.max = emptyHb.base - 1; // empty
- emptyHb.bits = (void *)1; // non-NULL but intentionally bad
-
- dvmHeapBitmapSweepWalk(hb, &emptyHb, callback, callbackArg);
-}
diff --git a/vm/alloc/HeapBitmap.h b/vm/alloc/HeapBitmap.h
index 5810d9a..b0dea99 100644
--- a/vm/alloc/HeapBitmap.h
+++ b/vm/alloc/HeapBitmap.h
@@ -18,6 +18,7 @@
#include <limits.h>
#include <stdint.h>
+#include "clz.h"
#define HB_OBJECT_ALIGNMENT 8
#define HB_BITS_PER_WORD (sizeof(unsigned long) * CHAR_BIT)
@@ -79,8 +80,8 @@
uintptr_t max;
} HeapBitmap;
-typedef void BitmapCallback(size_t numPtrs, void **ptrs,
- const void *finger, void *arg);
+typedef void BitmapCallback(void *addr, void *arg);
+typedef void BitmapSweepCallback(size_t numPtrs, void **ptrs, void *arg);
/*
* Initialize a HeapBitmap so that it points to a bitmap large
@@ -118,14 +119,38 @@
* end of the bitmap is reached.
*/
void dvmHeapBitmapSweepWalk(const HeapBitmap *liveHb, const HeapBitmap *markHb,
- BitmapCallback *callback, void *callbackArg);
+ BitmapSweepCallback *callback, void *callbackArg);
/*
* Similar to dvmHeapBitmapSweepWalk(), but visit the set bits
* in a single bitmap.
*/
-void dvmHeapBitmapWalk(const HeapBitmap *hb,
- BitmapCallback *callback, void *callbackArg);
+HB_INLINE_PROTO(
+ void
+ dvmHeapBitmapWalk(const HeapBitmap *bitmap,
+ BitmapCallback *callback, void *arg)
+)
+{
+ assert(bitmap != NULL);
+ assert(bitmap->bits != NULL);
+ assert(callback != NULL);
+ uintptr_t end = HB_OFFSET_TO_INDEX(bitmap->max - bitmap->base);
+ uintptr_t i;
+ for (i = 0; i <= end; ++i) {
+ unsigned long word = bitmap->bits[i];
+ if (UNLIKELY(word != 0)) {
+ unsigned long highBit = 1 << (HB_BITS_PER_WORD - 1);
+ uintptr_t ptrBase = HB_INDEX_TO_OFFSET(i) + bitmap->base;
+ while (word != 0) {
+ const int shift = CLZ(word);
+ word &= ~(highBit >> shift);
+ void *addr = (void *)(ptrBase + shift * HB_OBJECT_ALIGNMENT);
+ (*callback)(addr, arg);
+ end = HB_OFFSET_TO_INDEX(bitmap->max - bitmap->base);
+ }
+ }
+ }
+}
/*
* Return true iff <obj> is within the range of pointers that this
diff --git a/vm/alloc/MarkSweep.c b/vm/alloc/MarkSweep.c
index eaf73c7..095e2c7 100644
--- a/vm/alloc/MarkSweep.c
+++ b/vm/alloc/MarkSweep.c
@@ -41,8 +41,8 @@
#define LOG_SCAN(...) LOGV_GC("SCAN: " __VA_ARGS__)
-#define ALIGN_UP_TO_PAGE_SIZE(p) \
- (((size_t)(p) + (SYSTEM_PAGE_SIZE - 1)) & ~(SYSTEM_PAGE_SIZE - 1))
+#define ALIGN_UP(x, n) (((size_t)(x) + (n) - 1) & ~((n) - 1))
+#define ALIGN_UP_TO_PAGE_SIZE(p) ALIGN_UP(p, SYSTEM_PAGE_SIZE)
/* Do not cast the result of this to a boolean; the only set bit
* may be > 1<<8.
@@ -653,25 +653,18 @@
}
}
-#ifndef NDEBUG
-static uintptr_t gLastFinger = 0;
-#endif
-
-static void scanBitmapCallback(size_t numPtrs, void **ptrs,
- const void *finger, void *arg)
+/*
+ * Callback for scanning each object in the bitmap. The finger is set
+ * to the address corresponding to the lowest address in the next word
+ * of bits in the bitmap.
+ */
+static void scanBitmapCallback(void *addr, void *arg)
{
GcMarkContext *ctx = arg;
- size_t i;
-
-#ifndef NDEBUG
- assert((uintptr_t)finger >= gLastFinger);
- gLastFinger = (uintptr_t)finger;
-#endif
-
- ctx->finger = finger;
- for (i = 0; i < numPtrs; i++) {
- scanObject(*ptrs++, ctx);
- }
+ void *nextAddr = (void *)((size_t)addr + 1);
+ size_t finger = ALIGN_UP(nextAddr, HB_BITS_PER_WORD * HB_OBJECT_ALIGNMENT);
+ ctx->finger = (void *)finger;
+ scanObject(addr, ctx);
}
/* Given bitmaps with the root set marked, find and mark all
@@ -687,9 +680,6 @@
/* The bitmaps currently have bits set for the root set.
* Walk across the bitmaps and scan each object.
*/
-#ifndef NDEBUG
- gLastFinger = 0;
-#endif
dvmHeapBitmapWalk(ctx->bitmap, scanBitmapCallback, ctx);
/* We've walked the mark bitmaps. Scan anything that's
@@ -963,8 +953,7 @@
bool isConcurrent;
} SweepContext;
-static void sweepBitmapCallback(size_t numPtrs, void **ptrs,
- const void *finger, void *arg)
+static void sweepBitmapCallback(size_t numPtrs, void **ptrs, void *arg)
{
SweepContext *ctx = arg;
diff --git a/vm/alloc/Verify.c b/vm/alloc/Verify.c
index 47d28d8..c4222ad 100644
--- a/vm/alloc/Verify.c
+++ b/vm/alloc/Verify.c
@@ -56,14 +56,9 @@
/*
* Helper function to call dvmVerifyObject from a bitmap walker.
*/
-static void verifyBitmapCallback(size_t numPtrs, void **ptrs,
- const void *finger, void *arg)
+static void verifyBitmapCallback(void *ptrs, void *arg)
{
- size_t i;
-
- for (i = 0; i < numPtrs; i++) {
- dvmVerifyObject(ptrs[i]);
- }
+ dvmVerifyObject(ptrs);
}
/*
