auto import from //depot/cupcake/@135843
diff --git a/vm/alloc/HeapBitmap.c b/vm/alloc/HeapBitmap.c
new file mode 100644
index 0000000..2c75678
--- /dev/null
+++ b/vm/alloc/HeapBitmap.c
@@ -0,0 +1,419 @@
+/*
+ * Copyright (C) 2008 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 "Dalvik.h"
+#include "HeapBitmap.h"
+#include "clz.h"
+#include <limits.h> // for ULONG_MAX
+#include <sys/mman.h> // for madvise(), mmap()
+#include <cutils/ashmem.h>
+
+#define HB_ASHMEM_NAME "dalvik-heap-bitmap"
+
+#ifndef PAGE_SIZE
+#define PAGE_SIZE 4096
+#endif
+#define ALIGN_UP_TO_PAGE_SIZE(p) \
+ (((size_t)(p) + (PAGE_SIZE - 1)) & ~(PAGE_SIZE - 1))
+
+#define LIKELY(exp) (__builtin_expect((exp) != 0, true))
+#define UNLIKELY(exp) (__builtin_expect((exp) != 0, false))
+
+/*
+ * Initialize a HeapBitmap so that it points to a bitmap large
+ * enough to cover a heap at <base> of <maxSize> bytes, where
+ * objects are guaranteed to be HB_OBJECT_ALIGNMENT-aligned.
+ */
+bool
+dvmHeapBitmapInit(HeapBitmap *hb, const void *base, size_t maxSize,
+ const char *name)
+{
+ void *bits;
+ size_t bitsLen;
+ size_t allocLen;
+ int fd;
+ char nameBuf[ASHMEM_NAME_LEN] = HB_ASHMEM_NAME;
+
+ assert(hb != NULL);
+
+ bitsLen = HB_OFFSET_TO_INDEX(maxSize) * sizeof(*hb->bits);
+ allocLen = ALIGN_UP_TO_PAGE_SIZE(bitsLen); // required by ashmem
+
+ if (name != NULL) {
+ snprintf(nameBuf, sizeof(nameBuf), HB_ASHMEM_NAME "/%s", name);
+ }
+ fd = ashmem_create_region(nameBuf, allocLen);
+ if (fd < 0) {
+ LOGE("Could not create %zu-byte ashmem region \"%s\" to cover "
+ "%zu-byte heap (%d)\n",
+ allocLen, nameBuf, maxSize, fd);
+ return false;
+ }
+
+ bits = mmap(NULL, bitsLen, PROT_READ | PROT_WRITE, MAP_PRIVATE, fd, 0);
+ close(fd);
+ if (bits == MAP_FAILED) {
+ LOGE("Could not mmap %d-byte ashmem region \"%s\"\n",
+ bitsLen, nameBuf);
+ return false;
+ }
+
+ memset(hb, 0, sizeof(*hb));
+ hb->bits = bits;
+ hb->bitsLen = bitsLen;
+ hb->base = (uintptr_t)base;
+ hb->max = hb->base - 1;
+
+ return true;
+}
+
+/*
+ * Initialize <hb> so that it covers the same extent as <templateBitmap>.
+ */
+bool
+dvmHeapBitmapInitFromTemplate(HeapBitmap *hb, const HeapBitmap *templateBitmap,
+ const char *name)
+{
+ return dvmHeapBitmapInit(hb,
+ (void *)templateBitmap->base, HB_MAX_OFFSET(templateBitmap), name);
+}
+
+/*
+ * Initialize the bitmaps in <out> so that they cover the same extent as
+ * the corresponding bitmaps in <templates>.
+ */
+bool
+dvmHeapBitmapInitListFromTemplates(HeapBitmap out[], HeapBitmap templates[],
+ size_t numBitmaps, const char *name)
+{
+ size_t i;
+ char fullName[PATH_MAX];
+
+ fullName[sizeof(fullName)-1] = '\0';
+ for (i = 0; i < numBitmaps; i++) {
+ bool ok;
+
+ /* If two ashmem regions have the same name, only one gets
+ * the name when looking at the maps.
+ */
+ snprintf(fullName, sizeof(fullName)-1, "%s/%zd", name, i);
+
+ ok = dvmHeapBitmapInitFromTemplate(&out[i], &templates[i], fullName);
+ if (!ok) {
+ dvmHeapBitmapDeleteList(out, i);
+ return false;
+ }
+ }
+ return true;
+}
+
+/*
+ * Clean up any resources associated with the bitmap.
+ */
+void
+dvmHeapBitmapDelete(HeapBitmap *hb)
+{
+ assert(hb != NULL);
+
+ if (hb->bits != NULL) {
+ // Re-calculate the size we passed to mmap().
+ size_t allocLen = ALIGN_UP_TO_PAGE_SIZE(hb->bitsLen);
+ munmap((char *)hb->bits, allocLen);
+ }
+ memset(hb, 0, sizeof(*hb));
+}
+
+/*
+ * Clean up any resources associated with the bitmaps.
+ */
+void
+dvmHeapBitmapDeleteList(HeapBitmap hbs[], size_t numBitmaps)
+{
+ size_t i;
+
+ for (i = 0; i < numBitmaps; i++) {
+ dvmHeapBitmapDelete(&hbs[i]);
+ }
+}
+
+/*
+ * Fill the bitmap with zeroes. Returns the bitmap's memory to
+ * the system as a side-effect.
+ */
+void
+dvmHeapBitmapZero(HeapBitmap *hb)
+{
+ assert(hb != NULL);
+
+ if (hb->bits != NULL) {
+ /* This returns the memory to the system.
+ * Successive page faults will return zeroed memory.
+ */
+ madvise(hb->bits, hb->bitsLen, MADV_DONTNEED);
+ hb->max = hb->base - 1;
+ }
+}
+
+/*
+ * Walk through the bitmaps in increasing address order, and find the
+ * object pointers that correspond to places where the bitmaps differ.
+ * 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 XorWalk. <finger> will be set to ULONG_MAX when the
+ * end of the bitmap is reached.
+ */
+bool
+dvmHeapBitmapXorWalk(const HeapBitmap *hb1, const HeapBitmap *hb2,
+ bool (*callback)(size_t numPtrs, void **ptrs,
+ const void *finger, void *arg),
+ void *callbackArg)
+{
+ static const size_t kPointerBufSize = 128;
+ void *pointerBuf[kPointerBufSize];
+ void **pb = pointerBuf;
+ size_t index;
+ size_t i;
+
+#define FLUSH_POINTERBUF(finger_) \
+ do { \
+ if (!callback(pb - pointerBuf, (void **)pointerBuf, \
+ (void *)(finger_), callbackArg)) \
+ { \
+ LOGW("dvmHeapBitmapXorWalk: callback failed\n"); \
+ return false; \
+ } \
+ pb = pointerBuf; \
+ } while (false)
+
+#define DECODE_BITS(hb_, bits_, update_index_) \
+ do { \
+ if (UNLIKELY(bits_ != 0)) { \
+ static const unsigned long kHighBit = \
+ (unsigned long)1 << (HB_BITS_PER_WORD - 1); \
+ const uintptr_t ptrBase = HB_INDEX_TO_OFFSET(i) + hb_->base; \
+/*TODO: hold onto ptrBase so we can shrink max later if possible */ \
+/*TODO: see if this is likely or unlikely */ \
+ while (bits_ != 0) { \
+ const int rshift = CLZ(bits_); \
+ bits_ &= ~(kHighBit >> rshift); \
+ *pb++ = (void *)(ptrBase + rshift * HB_OBJECT_ALIGNMENT); \
+ } \
+ /* 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); \
+ if (update_index_) { \
+ /* The callback may have caused hb_->max to grow. */ \
+ index = HB_OFFSET_TO_INDEX(hb_->max - hb_->base); \
+ } \
+ } \
+ } \
+ } while (false)
+
+ assert(hb1 != NULL);
+ assert(hb1->bits != NULL);
+ assert(hb2 != NULL);
+ assert(hb2->bits != NULL);
+ assert(callback != NULL);
+
+ if (hb1->base != hb2->base) {
+ LOGW("dvmHeapBitmapXorWalk: bitmaps cover different heaps "
+ "(0x%08x != 0x%08x)\n",
+ (uintptr_t)hb1->base, (uintptr_t)hb2->base);
+ return false;
+ }
+ if (hb1->bitsLen != hb2->bitsLen) {
+ LOGW("dvmHeapBitmapXorWalk: size of bitmaps differ (%zd != %zd)\n",
+ hb1->bitsLen, hb2->bitsLen);
+ return false;
+ }
+ if (hb1->max < hb1->base && hb2->max < hb2->base) {
+ /* Easy case; both are obviously empty.
+ */
+ return true;
+ }
+
+ /* First, walk along the section of the bitmaps that may be the same.
+ */
+ if (hb1->max >= hb1->base && hb2->max >= hb2->base) {
+ unsigned long int *p1, *p2;
+ uintptr_t offset;
+
+ offset = ((hb1->max < hb2->max) ? hb1->max : hb2->max) - hb1->base;
+//TODO: keep track of which (and whether) one is longer for later
+ index = HB_OFFSET_TO_INDEX(offset);
+
+ p1 = hb1->bits;
+ p2 = hb2->bits;
+ for (i = 0; i <= index; i++) {
+//TODO: unroll this. pile up a few in locals?
+ unsigned long int diff = *p1++ ^ *p2++;
+ DECODE_BITS(hb1, diff, false);
+//BUG: if the callback was called, either max could have changed.
+ }
+ /* The next index to look at.
+ */
+ index++;
+ } else {
+ /* One of the bitmaps is empty.
+ */
+ index = 0;
+ }
+
+ /* If one bitmap's max is larger, walk through the rest of the
+ * set bits.
+ */
+const HeapBitmap *longHb;
+unsigned long int *p;
+//TODO: may be the same size, in which case this is wasted work
+ longHb = (hb1->max > hb2->max) ? hb1 : hb2;
+ i = index;
+ index = HB_OFFSET_TO_INDEX(longHb->max - longHb->base);
+ p = longHb->bits + i;
+ for (/* i = i */; i <= index; i++) {
+//TODO: unroll this
+ unsigned long bits = *p++;
+ DECODE_BITS(longHb, bits, true);
+ }
+
+ 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.
+ */
+ FLUSH_POINTERBUF(longHb->base + HB_MAX_OFFSET(longHb));
+ }
+
+ return true;
+
+#undef FLUSH_POINTERBUF
+#undef DECODE_BITS
+}
+
+/*
+ * Fills outIndexList with indices so that for all i:
+ *
+ * hb[outIndexList[i]].base < hb[outIndexList[i+1]].base
+ */
+static void
+createSortedBitmapIndexList(const HeapBitmap hbs[], size_t numBitmaps,
+ size_t outIndexList[])
+{
+ int i, j;
+
+ /* numBitmaps is usually 2 or 3, so use a simple sort */
+ for (i = 0; i < (int) numBitmaps; i++) {
+ outIndexList[i] = i;
+ for (j = 0; j < i; j++) {
+ if (hbs[j].base > hbs[i].base) {
+ int tmp = outIndexList[i];
+ outIndexList[i] = outIndexList[j];
+ outIndexList[j] = tmp;
+ }
+ }
+ }
+}
+
+/*
+ * Similar to dvmHeapBitmapXorWalk(), but compare multiple bitmaps.
+ * Regardless of the order of the arrays, the bitmaps will be visited
+ * in address order, so that finger will increase monotonically.
+ */
+bool
+dvmHeapBitmapXorWalkLists(const HeapBitmap hbs1[], const HeapBitmap hbs2[],
+ size_t numBitmaps,
+ bool (*callback)(size_t numPtrs, void **ptrs,
+ const void *finger, void *arg),
+ void *callbackArg)
+{
+ size_t indexList[numBitmaps];
+ size_t i;
+
+ /* Sort the bitmaps by address. Assume that the two lists contain
+ * congruent bitmaps.
+ */
+ createSortedBitmapIndexList(hbs1, numBitmaps, indexList);
+
+ /* Walk each pair of bitmaps, lowest address first.
+ */
+ for (i = 0; i < numBitmaps; i++) {
+ bool ok;
+
+ ok = dvmHeapBitmapXorWalk(&hbs1[indexList[i]], &hbs2[indexList[i]],
+ callback, callbackArg);
+ if (!ok) {
+ return false;
+ }
+ }
+
+ return true;
+}
+
+/*
+ * Similar to dvmHeapBitmapXorWalk(), but visit the set bits
+ * in a single bitmap.
+ */
+bool
+dvmHeapBitmapWalk(const HeapBitmap *hb,
+ bool (*callback)(size_t numPtrs, void **ptrs,
+ const void *finger, void *arg),
+ 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
+
+ return dvmHeapBitmapXorWalk(hb, &emptyHb, callback, callbackArg);
+}
+
+/*
+ * Similar to dvmHeapBitmapXorWalkList(), but visit the set bits
+ * in a single list of bitmaps. Regardless of the order of the array,
+ * the bitmaps will be visited in address order, so that finger will
+ * increase monotonically.
+ */
+bool dvmHeapBitmapWalkList(const HeapBitmap hbs[], size_t numBitmaps,
+ bool (*callback)(size_t numPtrs, void **ptrs,
+ const void *finger, void *arg),
+ void *callbackArg)
+{
+ size_t indexList[numBitmaps];
+ size_t i;
+
+ /* Sort the bitmaps by address.
+ */
+ createSortedBitmapIndexList(hbs, numBitmaps, indexList);
+
+ /* Walk each bitmap, lowest address first.
+ */
+ for (i = 0; i < numBitmaps; i++) {
+ bool ok;
+
+ ok = dvmHeapBitmapWalk(&hbs[indexList[i]], callback, callbackArg);
+ if (!ok) {
+ return false;
+ }
+ }
+
+ return true;
+}