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.
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);
 }
 
 /*