Allocate an object and mark bitmap which span the entire virtual
memory reservation of the heap.  Eliminates indirection during the
marking phase.
diff --git a/vm/alloc/HeapSource.c b/vm/alloc/HeapSource.c
index 9cae70a..104254b 100644
--- a/vm/alloc/HeapSource.c
+++ b/vm/alloc/HeapSource.c
@@ -100,10 +100,6 @@
      */
     mspace msp;
 
-    /* The bitmap that keeps track of where objects are in the heap.
-     */
-    HeapBitmap objectBitmap;
-
     /* The largest size that this heap is allowed to grow to.
      */
     size_t absoluteMaxSize;
@@ -117,6 +113,16 @@
     /* Number of objects currently allocated from this mspace.
      */
     size_t objectsAllocated;
+
+    /*
+     * The lowest address of this heap, inclusive.
+     */
+    char *base;
+
+    /*
+     * The highest address of this heap, exclusive.
+     */
+    char *limit;
 } Heap;
 
 struct HeapSource {
@@ -176,6 +182,16 @@
      * The length in bytes of the virtual memory reservation.
      */
     size_t heapLength;
+
+    /*
+     * The object (live, allocated) bitmap.
+     */
+    HeapBitmap objBits;
+
+    /*
+     * The mark bitmap.
+     */
+    HeapBitmap markBits;
 };
 
 #define hs2heap(hs_) (&((hs_)->heaps[0]))
@@ -231,8 +247,8 @@
     if (ptr != NULL) {
         for (i = 0; i < numHeaps; i++) {
             const Heap *const heap = &hs->heaps[i];
-            
-            if (dvmHeapBitmapMayContainObject(&heap->objectBitmap, ptr)) {
+
+            if ((const char *)ptr >= heap->base && (const char *)ptr < heap->limit) {
                 return (Heap *)heap;
             }
         }
@@ -251,13 +267,16 @@
 static inline void
 countAllocation(Heap *heap, const void *ptr, bool isObj)
 {
+    HeapSource *hs;
+
     assert(heap->bytesAllocated < mspace_footprint(heap->msp));
 
     heap->bytesAllocated += mspace_usable_size(heap->msp, ptr) +
             HEAP_SOURCE_CHUNK_OVERHEAD;
     if (isObj) {
         heap->objectsAllocated++;
-        dvmHeapBitmapSetObjectBit(&heap->objectBitmap, ptr);
+        hs = gDvm.gcHeap->heapSource;
+        dvmHeapBitmapSetObjectBit(&hs->objBits, ptr);
     }
 
     assert(heap->bytesAllocated < mspace_footprint(heap->msp));
@@ -266,6 +285,7 @@
 static inline void
 countFree(Heap *heap, const void *ptr, bool isObj)
 {
+    HeapSource *hs;
     size_t delta;
 
     delta = mspace_usable_size(heap->msp, ptr) + HEAP_SOURCE_CHUNK_OVERHEAD;
@@ -276,7 +296,8 @@
         heap->bytesAllocated = 0;
     }
     if (isObj) {
-        dvmHeapBitmapClearObjectBit(&heap->objectBitmap, ptr);
+        hs = gDvm.gcHeap->heapSource;
+        dvmHeapBitmapClearObjectBit(&hs->objBits, ptr);
         if (heap->objectsAllocated > 0) {
             heap->objectsAllocated--;
         }
@@ -336,8 +357,10 @@
     if (msp != NULL) {
         heap.msp = msp;
         heap.absoluteMaxSize = mspAbsoluteMaxSize;
+        heap.base = hs->heapBase;
+        heap.limit = hs->heapBase + heap.absoluteMaxSize;
     } else {
-        size_t diff, overhead;
+        size_t overhead;
 
         overhead = oldHeapOverhead(hs, true);
         if (overhead + HEAP_MIN_FREE >= hs->absoluteMaxSize) {
@@ -348,21 +371,14 @@
         }
         heap.absoluteMaxSize = hs->absoluteMaxSize - overhead;
         base = contiguous_mspace_sbrk0(hs->heaps[0].msp);
+        hs->heaps[0].limit = base;
         base = (void *)ALIGN_UP_TO_PAGE_SIZE(base);
         heap.msp = createMspace(base, HEAP_MIN_FREE, heap.absoluteMaxSize);
+        heap.base = base;
+        heap.limit = heap.base + heap.absoluteMaxSize;
         if (heap.msp == NULL) {
             return false;
         }
-        diff = (size_t)base - hs->heaps[0].objectBitmap.base;
-        hs->heaps[0].objectBitmap.bitsLen = HB_OFFSET_TO_INDEX(diff) * 4;
-    }
-    if (!dvmHeapBitmapInit(&heap.objectBitmap,
-                           (void *)ALIGN_DOWN_TO_PAGE_SIZE(heap.msp),
-                           heap.absoluteMaxSize,
-                           "objects"))
-    {
-        LOGE_HEAP("Can't create objectBitmap\n");
-        return false;
     }
 
     /* Don't let the soon-to-be-old heap grow any further.
@@ -462,7 +478,17 @@
         LOGE_HEAP("Can't add initial heap\n");
         goto fail;
     }
+    if (!dvmHeapBitmapInit(&hs->objBits, base, length, "dalvik-bitmap-1")) {
+        LOGE_HEAP("Can't create objBits\n");
+        goto fail;
+    }
+    if (!dvmHeapBitmapInit(&hs->markBits, base, length, "dalvik-bitmap-2")) {
+        LOGE_HEAP("Can't create markBits\n");
+        dvmHeapBitmapDelete(&hs->objBits);
+        goto fail;
+    }
 
+    gcHeap->markContext.bitmap = &hs->markBits;
     gcHeap->heapSource = hs;
 
     countAllocation(hs2heap(hs), gcHeap, false);
@@ -520,11 +546,8 @@
         assert((char *)*gcHeap >= hs->heapBase);
         assert((char *)*gcHeap < hs->heapBase + hs->heapLength);
 
-        for (i = 0; i < hs->numHeaps; i++) {
-            Heap *heap = &hs->heaps[i];
-
-            dvmHeapBitmapDelete(&heap->objectBitmap);
-        }
+        dvmHeapBitmapDelete(&hs->objBits);
+        dvmHeapBitmapDelete(&hs->markBits);
 
         munmap(hs->heapBase, hs->heapLength);
         gHs = NULL;
@@ -588,59 +611,49 @@
     return total;
 }
 
-/*
- * Writes shallow copies of the currently-used bitmaps into outBitmaps,
- * returning the number of bitmaps written.  Returns 0 if the array was
- * not long enough or if there are no heaps, either of which is an error.
- */
-size_t
-dvmHeapSourceGetObjectBitmaps(HeapBitmap outBitmaps[], size_t maxBitmaps)
-{
-    HeapSource *hs = gHs;
+static void aliasBitmap(HeapBitmap *dst, HeapBitmap *src,
+                        uintptr_t base, uintptr_t max) {
+    size_t offset;
 
-    HS_BOILERPLATE();
-
-    assert(hs->numHeaps != 0);
-    if (maxBitmaps >= hs->numHeaps) {
-        size_t i;
-
-        for (i = 0; i < hs->numHeaps; i++) {
-            outBitmaps[i] = hs->heaps[i].objectBitmap;
-        }
-        return i;
-    }
-    return 0;
+    dst->base = base;
+    dst->max = max;
+    dst->bitsLen = max - base;
+    offset = base - src->base;
+    assert(HB_OFFSET_TO_MASK(offset) == 1 << 31);
+    dst->bits = &src->bits[HB_OFFSET_TO_INDEX(offset)];
 }
 
 /*
- * Replaces the object location HeapBitmaps with the elements of
- * <objectBitmaps>.  The elements of <objectBitmaps> are overwritten
- * with shallow copies of the old bitmaps.
- *
- * Returns false if the number of bitmaps doesn't match the number
- * of heaps.
+ * Initializes a vector of object and mark bits to the object and mark
+ * bits of to each heap.  The bits are aliased to the heapsource
+ * object and mark bitmaps.  This routine is used by the sweep code
+ * which needs to free each object in the correct heap.
  */
-bool
-dvmHeapSourceReplaceObjectBitmaps(HeapBitmap objectBitmaps[], size_t nBitmaps)
+void dvmHeapSourceGetObjectBitmaps(HeapBitmap objBits[], HeapBitmap markBits[],
+                                   size_t numHeaps)
 {
     HeapSource *hs = gHs;
-    size_t i;
+    uintptr_t base, max;
+    size_t i, offset;
 
     HS_BOILERPLATE();
 
-    if (nBitmaps != hs->numHeaps) {
-        return false;
+    assert(numHeaps == hs->numHeaps);
+    for (i = 0; i < hs->numHeaps; ++i) {
+        base = (uintptr_t)hs->heaps[i].base;
+        max = (uintptr_t)hs->heaps[i].limit;
+        aliasBitmap(&objBits[i], &hs->objBits, base, max);
+        aliasBitmap(&markBits[i], &hs->markBits, base, max);
     }
+}
 
-    for (i = 0; i < hs->numHeaps; i++) {
-        Heap *heap = &hs->heaps[i];
-        HeapBitmap swap;
-
-        swap = heap->objectBitmap;
-        heap->objectBitmap = objectBitmaps[i];
-        objectBitmaps[i] = swap;
-    }
-    return true;
+void dvmHeapSourceSwapBitmaps(void)
+{
+    HeapBitmap tmp;
+    tmp = gHs->objBits;
+    gHs->objBits = gHs->markBits;
+    gHs->markBits = tmp;
+    dvmHeapBitmapZero(&gHs->markBits);
 }
 
 /*
@@ -865,13 +878,11 @@
 bool
 dvmHeapSourceContains(const void *ptr)
 {
-    Heap *heap;
-
     HS_BOILERPLATE();
 
-    heap = ptr2heap(gHs, ptr);
-    if (heap != NULL) {
-        return dvmHeapBitmapIsObjectBitSet(&heap->objectBitmap, ptr) != 0;
+    if (dvmHeapBitmapCoversAddress(&gHs->objBits, ptr)) {
+        return dvmHeapBitmapIsObjectBitSet(&gHs->objBits, ptr) != 0;
+        
     }
     return false;
 }
diff --git a/vm/alloc/HeapSource.h b/vm/alloc/HeapSource.h
index bbe074f..940b627 100644
--- a/vm/alloc/HeapSource.h
+++ b/vm/alloc/HeapSource.h
@@ -47,23 +47,11 @@
 void dvmHeapSourceShutdown(GcHeap **gcHeap);
 
 /*
- * Writes shallow copies of the currently-used bitmaps into outBitmaps,
- * returning the number of bitmaps written.  Returns 0 if the array was
- * not long enough or if there are no heaps, either of which is an error.
+ * Initializes a vector of object and mark bits to the object and mark
+ * bits of to each heap.
  */
-size_t dvmHeapSourceGetObjectBitmaps(HeapBitmap outBitmaps[],
-        size_t maxBitmaps);
-
-/*
- * Replaces the object location HeapBitmaps with the elements of
- * <objectBitmaps>.  The elements of <objectBitmaps> are overwritten
- * with shallow copies of the old bitmaps.
- *
- * Returns false if the number of bitmaps doesn't match the number
- * of heaps.
- */
-bool dvmHeapSourceReplaceObjectBitmaps(HeapBitmap objectBitmaps[],
-        size_t nBitmaps);
+void dvmHeapSourceGetObjectBitmaps(HeapBitmap objBits[], HeapBitmap markBits[],
+                                   size_t numHeaps);
 
 /*
  * Returns the requested value. If the per-heap stats are requested, fill
@@ -162,4 +150,9 @@
  */
 size_t dvmHeapSourceGetNumHeaps(void);
 
+/*
+ * Exchanges the mark and object bitmaps and zeros the mark bitmap.
+ */
+void dvmHeapSourceSwapBitmaps(void);
+
 #endif  // _DALVIK_HEAP_SOURCE
diff --git a/vm/alloc/MarkSweep.c b/vm/alloc/MarkSweep.c
index ca6aecd..0c8feca 100644
--- a/vm/alloc/MarkSweep.c
+++ b/vm/alloc/MarkSweep.c
@@ -78,7 +78,7 @@
         __attribute__((always_inline));
 static inline long isMarked(const void *obj, const GcMarkContext *ctx)
 {
-    return dvmHeapBitmapIsObjectBitSetInList(ctx->bitmaps, ctx->numBitmaps, obj);
+    return dvmHeapBitmapIsObjectBitSet(ctx->bitmap, obj);
 }
 
 static bool
@@ -137,31 +137,11 @@
 dvmHeapBeginMarkStep()
 {
     GcMarkContext *mc = &gDvm.gcHeap->markContext;
-    HeapBitmap objectBitmaps[HEAP_SOURCE_MAX_HEAP_COUNT];
-    size_t numBitmaps;
 
     if (!createMarkStack(&mc->stack)) {
         return false;
     }
-
-    numBitmaps = dvmHeapSourceGetObjectBitmaps(objectBitmaps,
-            HEAP_SOURCE_MAX_HEAP_COUNT);
-    if (numBitmaps == 0) {
-        return false;
-    }
-
-    /* Create mark bitmaps that cover the same ranges as the
-     * current object bitmaps.
-     */
-    if (!dvmHeapBitmapInitListFromTemplates(mc->bitmaps, objectBitmaps,
-            numBitmaps, "mark"))
-    {
-        return false;
-    }
-
-    mc->numBitmaps = numBitmaps;
     mc->finger = NULL;
-
     return true;
 }
 
@@ -170,8 +150,7 @@
 static long
 setAndReturnMarkBit(GcMarkContext *ctx, const void *obj)
 {
-    return dvmHeapBitmapSetAndReturnObjectBitInList(ctx->bitmaps,
-        ctx->numBitmaps, obj);
+    return dvmHeapBitmapSetAndReturnObjectBit(ctx->bitmap, obj);
 }
 
 static void _markObjectNonNullCommon(const Object *obj, GcMarkContext *ctx,
@@ -725,8 +704,7 @@
 #ifndef NDEBUG
     gLastFinger = 0;
 #endif
-    dvmHeapBitmapWalkList(ctx->bitmaps, ctx->numBitmaps,
-            scanBitmapCallback, ctx);
+    dvmHeapBitmapWalk(ctx->bitmap, scanBitmapCallback, ctx);
 
     /* We've walked the mark bitmaps.  Scan anything that's
      * left on the mark stack.
@@ -1058,20 +1036,14 @@
      * HeapSource bitmaps that didn't appear in the mark bitmaps.
      * The new state of the HeapSource is exactly the final
      * mark bitmaps, so swap them in.
-     *
-     * The old bitmaps will be swapped into the context so that
-     * we can clean them up.
      */
-    dvmHeapSourceReplaceObjectBitmaps(markContext->bitmaps,
-            markContext->numBitmaps);
+    dvmHeapSourceSwapBitmaps();
 
-    /* Clean up the old HeapSource bitmaps and anything else associated
-     * with the marking process.
+    /* Clean up everything else associated with the marking process.
      */
-    dvmHeapBitmapDeleteList(markContext->bitmaps, markContext->numBitmaps);
     destroyMarkStack(&markContext->stack);
 
-    memset(markContext, 0, sizeof(*markContext));
+    markContext->finger = NULL;
 }
 
 #if WITH_HPROF && WITH_HPROF_UNREACHABLE
@@ -1181,9 +1153,8 @@
 void
 dvmHeapSweepUnmarkedObjects(int *numFreed, size_t *sizeFreed)
 {
-    const HeapBitmap *markBitmaps;
-    const GcMarkContext *markContext;
-    HeapBitmap objectBitmaps[HEAP_SOURCE_MAX_HEAP_COUNT];
+    HeapBitmap markBits[HEAP_SOURCE_MAX_HEAP_COUNT];
+    HeapBitmap objBits[HEAP_SOURCE_MAX_HEAP_COUNT];
     size_t origObjectsAllocated;
     size_t origBytesAllocated;
     size_t numBitmaps;
@@ -1199,26 +1170,16 @@
     origObjectsAllocated = dvmHeapSourceGetValue(HS_OBJECTS_ALLOCATED, NULL, 0);
     origBytesAllocated = dvmHeapSourceGetValue(HS_BYTES_ALLOCATED, NULL, 0);
 
-    markContext = &gDvm.gcHeap->markContext;
-    markBitmaps = markContext->bitmaps;
-    numBitmaps = dvmHeapSourceGetObjectBitmaps(objectBitmaps,
-            HEAP_SOURCE_MAX_HEAP_COUNT);
-#ifndef NDEBUG
-    if (numBitmaps != markContext->numBitmaps) {
-        LOGE("heap bitmap count mismatch: %zd != %zd\n",
-                numBitmaps, markContext->numBitmaps);
-        dvmAbort();
-    }
-#endif
-
 #if WITH_HPROF && WITH_HPROF_UNREACHABLE
     hprofDumpUnmarkedObjects(markBitmaps, objectBitmaps, numBitmaps);
 #endif
 
     dvmSweepMonitorList(&gDvm.monitorList, isUnmarkedObject);
 
-    dvmHeapBitmapXorWalkLists(markBitmaps, objectBitmaps, numBitmaps,
-            sweepBitmapCallback, NULL);
+    numBitmaps = dvmHeapSourceGetNumHeaps();
+    dvmHeapSourceGetObjectBitmaps(objBits, markBits, numBitmaps);
+    dvmHeapBitmapXorWalkLists(markBits, objBits, numBitmaps,
+                              sweepBitmapCallback, NULL);
 
     *numFreed = origObjectsAllocated -
             dvmHeapSourceGetValue(HS_OBJECTS_ALLOCATED, NULL, 0);
diff --git a/vm/alloc/MarkSweep.h b/vm/alloc/MarkSweep.h
index b087b40..2f280bb 100644
--- a/vm/alloc/MarkSweep.h
+++ b/vm/alloc/MarkSweep.h
@@ -38,8 +38,7 @@
 /* This is declared publicly so that it can be included in gDvm.gcHeap.
  */
 typedef struct {
-    HeapBitmap bitmaps[HEAP_SOURCE_MAX_HEAP_COUNT];
-    size_t numBitmaps;
+    HeapBitmap *bitmap;
     GcMarkStack stack;
     const void *finger;   // only used while scanning/recursing.
 } GcMarkContext;