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