1f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/* 2f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Copyright (C) 2008 The Android Open Source Project 3f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 4f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Licensed under the Apache License, Version 2.0 (the "License"); 5f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * you may not use this file except in compliance with the License. 6f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * You may obtain a copy of the License at 7f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 8f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * http://www.apache.org/licenses/LICENSE-2.0 9f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 10f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Unless required by applicable law or agreed to in writing, software 11f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * distributed under the License is distributed on an "AS IS" BASIS, 12f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * See the License for the specific language governing permissions and 14f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * limitations under the License. 15f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 16f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project#ifndef _DALVIK_HEAP_BITMAP 17f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project#define _DALVIK_HEAP_BITMAP 18f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 19f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project#include <stdint.h> 20f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project#include <assert.h> 21f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 22f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project#define HB_OBJECT_ALIGNMENT 8 23f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project#define HB_BITS_PER_WORD (sizeof (unsigned long int) * 8) 24f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 25f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/* <offset> is the difference from .base to a pointer address. 26f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * <index> is the index of .bits that contains the bit representing 27f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * <offset>. 28f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 29f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project#define HB_OFFSET_TO_INDEX(offset_) \ 30f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ((uintptr_t)(offset_) / HB_OBJECT_ALIGNMENT / HB_BITS_PER_WORD) 31f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project#define HB_INDEX_TO_OFFSET(index_) \ 32f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ((uintptr_t)(index_) * HB_OBJECT_ALIGNMENT * HB_BITS_PER_WORD) 33f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 34f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/* Pack the bits in backwards so they come out in address order 35f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * when using CLZ. 36f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 37f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project#define HB_OFFSET_TO_MASK(offset_) \ 38f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project (1 << \ 39f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project (31-(((uintptr_t)(offset_) / HB_OBJECT_ALIGNMENT) % HB_BITS_PER_WORD))) 40f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 41f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/* Return the maximum offset (exclusive) that <hb> can represent. 42f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 43f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project#define HB_MAX_OFFSET(hb_) \ 44f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project HB_INDEX_TO_OFFSET((hb_)->bitsLen / sizeof(*(hb_)->bits)) 45f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 46f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project#define HB_INLINE_PROTO(p) \ 47f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project static inline p __attribute__((always_inline)); \ 48f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project static inline p 49f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 50f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 51f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projecttypedef struct { 52f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* The bitmap data, which points to an mmap()ed area of zeroed 53f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * anonymous memory. 54f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 55f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project unsigned long int *bits; 56f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 57f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* The size of the memory pointed to by bits, in bytes. 58f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 59f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project size_t bitsLen; 60f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 61f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* The base address, which corresponds to the first bit in 62f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * the bitmap. 63f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 64f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project uintptr_t base; 65f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 66f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* The highest pointer value ever returned by an allocation 67f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * from this heap. I.e., the highest address that may correspond 68f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * to a set bit. If there are no bits set, (max < base). 69f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 70f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project uintptr_t max; 71f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project} HeapBitmap; 72f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 73f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 74f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/* 75f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Initialize a HeapBitmap so that it points to a bitmap large 76f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * enough to cover a heap at <base> of <maxSize> bytes, where 77f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * objects are guaranteed to be HB_OBJECT_ALIGNMENT-aligned. 78f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 79f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectbool dvmHeapBitmapInit(HeapBitmap *hb, const void *base, size_t maxSize, 80f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project const char *name); 81f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 82f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/* 83f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Initialize <hb> so that it covers the same extent as <templateBitmap>. 84f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 85f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectbool dvmHeapBitmapInitFromTemplate(HeapBitmap *hb, 86f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project const HeapBitmap *templateBitmap, const char *name); 87f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 88f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/* 89f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Initialize the bitmaps in <out> so that they cover the same extent as 90f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * the corresponding bitmaps in <templates>. 91f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 92f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectbool dvmHeapBitmapInitListFromTemplates(HeapBitmap out[], 93f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project HeapBitmap templates[], size_t numBitmaps, const char *name); 94f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 95f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/* 96f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Clean up any resources associated with the bitmap. 97f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 98f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectvoid dvmHeapBitmapDelete(HeapBitmap *hb); 99f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 100f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/* 101f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Clean up any resources associated with the bitmaps. 102f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 103f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectvoid dvmHeapBitmapDeleteList(HeapBitmap hbs[], size_t numBitmaps); 104f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 105f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/* 106f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Fill the bitmap with zeroes. Returns the bitmap's memory to 107f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * the system as a side-effect. 108f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 109f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectvoid dvmHeapBitmapZero(HeapBitmap *hb); 110f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 111f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/* 112f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Walk through the bitmaps in increasing address order, and find the 113f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * object pointers that correspond to places where the bitmaps differ. 114f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Call <callback> zero or more times with lists of these object pointers. 115f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 116f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * The <finger> argument to the callback indicates the next-highest 117f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * address that hasn't been visited yet; setting bits for objects whose 118f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * addresses are less than <finger> are not guaranteed to be seen by 119f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * the current XorWalk. <finger> will be set to ULONG_MAX when the 120f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * end of the bitmap is reached. 121f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 122f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectbool dvmHeapBitmapXorWalk(const HeapBitmap *hb1, const HeapBitmap *hb2, 123f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project bool (*callback)(size_t numPtrs, void **ptrs, 124f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project const void *finger, void *arg), 125f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project void *callbackArg); 126f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 127f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/* 128f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Similar to dvmHeapBitmapXorWalk(), but compare multiple bitmaps. 129f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Regardless of the order of the arrays, the bitmaps will be visited 130f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * in address order, so that finger will increase monotonically. 131f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 132f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectbool dvmHeapBitmapXorWalkLists(const HeapBitmap hbs1[], const HeapBitmap hbs2[], 133f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project size_t numBitmaps, 134f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project bool (*callback)(size_t numPtrs, void **ptrs, 135f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project const void *finger, void *arg), 136f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project void *callbackArg); 137f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 138f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/* 139f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Similar to dvmHeapBitmapXorWalk(), but visit the set bits 140f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * in a single bitmap. 141f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 142f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectbool dvmHeapBitmapWalk(const HeapBitmap *hb, 143f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project bool (*callback)(size_t numPtrs, void **ptrs, 144f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project const void *finger, void *arg), 145f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project void *callbackArg); 146f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 147f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/* 148f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Similar to dvmHeapBitmapXorWalkList(), but visit the set bits 149f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * in a single list of bitmaps. Regardless of the order of the array, 150f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * the bitmaps will be visited in address order, so that finger will 151f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * increase monotonically. 152f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 153f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectbool dvmHeapBitmapWalkList(const HeapBitmap hbs[], size_t numBitmaps, 154f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project bool (*callback)(size_t numPtrs, void **ptrs, 155f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project const void *finger, void *arg), 156f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project void *callbackArg); 157f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/* 158f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Return true iff <obj> is within the range of pointers that 159f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * have had corresponding bits set in this bitmap. 160f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 161f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source ProjectHB_INLINE_PROTO( 162f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project bool 163f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project dvmHeapBitmapMayContainObject(const HeapBitmap *hb, 164f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project const void *obj) 165f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project) 166f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project{ 167f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project const uintptr_t p = (const uintptr_t)obj; 168f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 169f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project assert((p & (HB_OBJECT_ALIGNMENT - 1)) == 0); 170f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 171f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return p >= hb->base && p <= hb->max; 172f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project} 173f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 174f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/* 175f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Return true iff <obj> is within the range of pointers that this 176f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * bitmap could potentially cover, even if a bit has not been set 177f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * for it. 178f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 179f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source ProjectHB_INLINE_PROTO( 180f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project bool 181f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project dvmHeapBitmapCoversAddress(const HeapBitmap *hb, const void *obj) 182f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project) 183f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project{ 184f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project assert(hb != NULL); 185f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 186f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (obj != NULL) { 187f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project const uintptr_t offset = (uintptr_t)obj - hb->base; 188f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project const size_t index = HB_OFFSET_TO_INDEX(offset); 189f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return index < hb->bitsLen / sizeof(*hb->bits); 190f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 191f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return false; 192f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project} 193f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 194f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/* 195f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Internal function; do not call directly. 196f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 197f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source ProjectHB_INLINE_PROTO( 198f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project unsigned long int 199f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project _heapBitmapModifyObjectBit(HeapBitmap *hb, const void *obj, 200f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project bool setBit, bool returnOld) 201f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project) 202f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project{ 203f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project const uintptr_t offset = (uintptr_t)obj - hb->base; 204f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project const size_t index = HB_OFFSET_TO_INDEX(offset); 205f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project const unsigned long int mask = HB_OFFSET_TO_MASK(offset); 206f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 207f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project#ifndef NDEBUG 208f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project assert(hb->bits != NULL); 209f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project assert((uintptr_t)obj >= hb->base); 210f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project assert(index < hb->bitsLen / sizeof(*hb->bits)); 211f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project#endif 212f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 213f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (setBit) { 214f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if ((uintptr_t)obj > hb->max) { 215f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project hb->max = (uintptr_t)obj; 216f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 217f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (returnOld) { 218f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project unsigned long int *p = hb->bits + index; 219f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project const unsigned long int word = *p; 220f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project *p |= mask; 221f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return word & mask; 222f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else { 223f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project hb->bits[index] |= mask; 224f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 225f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else { 226f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project hb->bits[index] &= ~mask; 227f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 228f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return false; 229f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project} 230f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 231f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/* 232f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Sets the bit corresponding to <obj>, and returns the previous value 233f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * of that bit (as zero or non-zero). Does no range checking to see if 234f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * <obj> is outside of the coverage of the bitmap. 235f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 236f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * NOTE: casting this value to a bool is dangerous, because higher 237f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * set bits will be lost. 238f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 239f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source ProjectHB_INLINE_PROTO( 240f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project unsigned long int 241f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project dvmHeapBitmapSetAndReturnObjectBit(HeapBitmap *hb, const void *obj) 242f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project) 243f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project{ 244f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return _heapBitmapModifyObjectBit(hb, obj, true, true); 245f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project} 246f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 247f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/* 248f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Like dvmHeapBitmapSetAndReturnObjectBit(), but sets/returns the bit 249f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * in the appropriate bitmap. Results are undefined if <obj> is not 250f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * covered by any bitmap. 251f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 252f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source ProjectHB_INLINE_PROTO( 253f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project unsigned long int 254f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project dvmHeapBitmapSetAndReturnObjectBitInList(HeapBitmap hbs[], 255f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project size_t numBitmaps, const void *obj) 256f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project) 257f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project{ 258f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project size_t i; 259f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 260f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (i = 0; i < numBitmaps; i++) { 261f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (dvmHeapBitmapCoversAddress(&hbs[i], obj)) { 262f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return dvmHeapBitmapSetAndReturnObjectBit(&hbs[i], obj); 263f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 264f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 265f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 266f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project assert(!"object not covered by any bitmap"); 267f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return false; 268f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project} 269f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 270f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/* 271f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Sets the bit corresponding to <obj>, and widens the range of seen 272f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * pointers if necessary. Does no range checking. 273f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 274f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source ProjectHB_INLINE_PROTO( 275f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project void 276f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project dvmHeapBitmapSetObjectBit(HeapBitmap *hb, const void *obj) 277f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project) 278f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project{ 279f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project (void)_heapBitmapModifyObjectBit(hb, obj, true, false); 280f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project} 281f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 282f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/* 283f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Clears the bit corresponding to <obj>. Does no range checking. 284f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 285f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source ProjectHB_INLINE_PROTO( 286f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project void 287f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project dvmHeapBitmapClearObjectBit(HeapBitmap *hb, const void *obj) 288f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project) 289f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project{ 290f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project (void)_heapBitmapModifyObjectBit(hb, obj, false, false); 291f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project} 292f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 293f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/* 294f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Returns the current value of the bit corresponding to <obj>, 295f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * as zero or non-zero. Does no range checking. 296f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 297f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * NOTE: casting this value to a bool is dangerous, because higher 298f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * set bits will be lost. 299f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 300f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source ProjectHB_INLINE_PROTO( 301f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project unsigned long int 302f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project dvmHeapBitmapIsObjectBitSet(const HeapBitmap *hb, const void *obj) 303f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project) 304f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project{ 305f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project assert(dvmHeapBitmapCoversAddress(hb, obj)); 306f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project assert(hb->bits != NULL); 307f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project assert((uintptr_t)obj >= hb->base); 308f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 309f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if ((uintptr_t)obj <= hb->max) { 310f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project const uintptr_t offset = (uintptr_t)obj - hb->base; 311f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return hb->bits[HB_OFFSET_TO_INDEX(offset)] & HB_OFFSET_TO_MASK(offset); 312f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else { 313f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return 0; 314f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 315f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project} 316f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 317f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/* 318f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Looks through the list of bitmaps and returns the current value of the 319f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * bit corresponding to <obj>, which may be covered by any of the bitmaps. 320f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Does no range checking. 321f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 322f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source ProjectHB_INLINE_PROTO( 323f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project long 324f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project dvmHeapBitmapIsObjectBitSetInList(const HeapBitmap hbs[], size_t numBitmaps, 325f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project const void *obj) 326f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project) 327f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project{ 328f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project size_t i; 329f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 330f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (i = 0; i < numBitmaps; i++) { 331f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (dvmHeapBitmapCoversAddress(&hbs[i], obj)) { 332f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return dvmHeapBitmapIsObjectBitSet(&hbs[i], obj); 333f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 334f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 335f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return false; 336f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project} 337f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 338f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project#undef HB_INLINE_PROTO 339f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 340f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project#endif // _DALVIK_HEAP_BITMAP 341