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