| /* |
| * 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 <sys/mman.h> /* for PROT_* */ |
| |
| /* |
| * 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; |
| |
| assert(hb != NULL); |
| assert(name != NULL); |
| bitsLen = HB_OFFSET_TO_INDEX(maxSize) * sizeof(*hb->bits); |
| bits = dvmAllocRegion(bitsLen, PROT_READ | PROT_WRITE, name); |
| if (bits == NULL) { |
| LOGE("Could not mmap %zd-byte ashmem region '%s'", bitsLen, name); |
| return false; |
| } |
| hb->bits = (unsigned long *)bits; |
| hb->bitsLen = hb->allocLen = bitsLen; |
| hb->base = (uintptr_t)base; |
| hb->max = hb->base - 1; |
| return true; |
| } |
| |
| /* |
| * Clean up any resources associated with the bitmap. |
| */ |
| void |
| dvmHeapBitmapDelete(HeapBitmap *hb) |
| { |
| assert(hb != NULL); |
| |
| if (hb->bits != NULL) { |
| munmap((char *)hb->bits, hb->allocLen); |
| } |
| memset(hb, 0, sizeof(*hb)); |
| } |
| |
| /* |
| * 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; |
| } |
| } |
| |
| /* |
| * Return true iff <obj> is within the range of pointers that this |
| * bitmap could potentially cover, even if a bit has not been set |
| * for it. |
| */ |
| bool dvmHeapBitmapCoversAddress(const HeapBitmap *hb, const void *obj) |
| { |
| assert(hb != NULL); |
| if (obj != NULL) { |
| const uintptr_t offset = (uintptr_t)obj - hb->base; |
| const size_t index = HB_OFFSET_TO_INDEX(offset); |
| return index < hb->bitsLen / sizeof(*hb->bits); |
| } |
| return false; |
| } |
| |
| /* |
| * Visits set bits in address order. The callback is not permitted to |
| * change the bitmap bits or max during the traversal. |
| */ |
| void dvmHeapBitmapWalk(const HeapBitmap *bitmap, BitmapCallback *callback, |
| void *arg) |
| { |
| uintptr_t end; |
| uintptr_t i; |
| |
| assert(bitmap != NULL); |
| assert(bitmap->bits != NULL); |
| assert(callback != NULL); |
| end = HB_OFFSET_TO_INDEX(bitmap->max - bitmap->base); |
| 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); |
| void *addr = (void *)(ptrBase + shift * HB_OBJECT_ALIGNMENT); |
| (*callback)(addr, arg); |
| word &= ~(highBit >> shift); |
| } |
| } |
| } |
| } |
| |
| /* |
| * Similar to dvmHeapBitmapWalk but the callback routine is permitted |
| * to change the bitmap bits and max during traversal. Used by the |
| * the root marking scan exclusively. |
| * |
| * The callback is invoked with a finger argument. The finger is a |
| * pointer to an address not yet visited by the traversal. If the |
| * callback sets a bit for an address at or above the finger, this |
| * address will be visited by the traversal. If the callback sets a |
| * bit for an address below the finger, this address will not be |
| * visited. |
| */ |
| void dvmHeapBitmapScanWalk(HeapBitmap *bitmap, |
| BitmapScanCallback *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; |
| void *finger = (void *)(HB_INDEX_TO_OFFSET(i + 1) + bitmap->base); |
| while (word != 0) { |
| const int shift = CLZ(word); |
| void *addr = (void *)(ptrBase + shift * HB_OBJECT_ALIGNMENT); |
| (*callback)(addr, finger, arg); |
| word &= ~(highBit >> shift); |
| } |
| end = HB_OFFSET_TO_INDEX(bitmap->max - bitmap->base); |
| } |
| } |
| } |
| |
| /* |
| * Walk through the bitmaps in increasing address order, and find the |
| * object pointers that correspond to garbage objects. Call |
| * <callback> zero or more times with lists of these object pointers. |
| * |
| * The callback is not permitted to increase the max of either bitmap. |
| */ |
| void dvmHeapBitmapSweepWalk(const HeapBitmap *liveHb, const HeapBitmap *markHb, |
| uintptr_t base, uintptr_t max, |
| BitmapSweepCallback *callback, void *callbackArg) |
| { |
| void *pointerBuf[4 * HB_BITS_PER_WORD]; |
| void **pb = pointerBuf; |
| size_t i; |
| size_t start, end; |
| unsigned long *live, *mark; |
| |
| assert(liveHb != NULL); |
| assert(liveHb->bits != NULL); |
| assert(markHb != NULL); |
| assert(markHb->bits != NULL); |
| assert(liveHb->base == markHb->base); |
| assert(liveHb->bitsLen == markHb->bitsLen); |
| assert(callback != NULL); |
| assert(base <= max); |
| assert(base >= liveHb->base); |
| assert(max <= liveHb->max); |
| if (liveHb->max < liveHb->base) { |
| /* Easy case; both are obviously empty. |
| */ |
| return; |
| } |
| start = HB_OFFSET_TO_INDEX(base - liveHb->base); |
| end = HB_OFFSET_TO_INDEX(max - liveHb->base); |
| live = liveHb->bits; |
| mark = markHb->bits; |
| for (i = start; i <= end; i++) { |
| unsigned long garbage = live[i] & ~mark[i]; |
| if (UNLIKELY(garbage != 0)) { |
| unsigned long highBit = 1 << (HB_BITS_PER_WORD - 1); |
| uintptr_t ptrBase = HB_INDEX_TO_OFFSET(i) + liveHb->base; |
| while (garbage != 0) { |
| int shift = CLZ(garbage); |
| garbage &= ~(highBit >> shift); |
| *pb++ = (void *)(ptrBase + shift * HB_OBJECT_ALIGNMENT); |
| } |
| /* Make sure that there are always enough slots available */ |
| /* for an entire word of 1s. */ |
| if (pb >= &pointerBuf[NELEM(pointerBuf) - HB_BITS_PER_WORD]) { |
| (*callback)(pb - pointerBuf, pointerBuf, callbackArg); |
| pb = pointerBuf; |
| } |
| } |
| } |
| if (pb > pointerBuf) { |
| (*callback)(pb - pointerBuf, pointerBuf, callbackArg); |
| } |
| } |