HeapBitmap.h revision 8eab1c515ef7f6bdb0252d49e6ea1c8ca7d8cfed
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 memory pointed to by bits, in bytes. 57 */ 58 size_t bitsLen; 59 60 /* The base address, which corresponds to the first bit in 61 * the bitmap. 62 */ 63 uintptr_t base; 64 65 /* The highest pointer value ever returned by an allocation 66 * from this heap. I.e., the highest address that may correspond 67 * to a set bit. If there are no bits set, (max < base). 68 */ 69 uintptr_t max; 70} HeapBitmap; 71 72 73/* 74 * Initialize a HeapBitmap so that it points to a bitmap large 75 * enough to cover a heap at <base> of <maxSize> bytes, where 76 * objects are guaranteed to be HB_OBJECT_ALIGNMENT-aligned. 77 */ 78bool dvmHeapBitmapInit(HeapBitmap *hb, const void *base, size_t maxSize, 79 const char *name); 80 81/* 82 * Initialize <hb> so that it covers the same extent as <templateBitmap>. 83 */ 84bool dvmHeapBitmapInitFromTemplate(HeapBitmap *hb, 85 const HeapBitmap *templateBitmap, const char *name); 86 87/* 88 * Initialize the bitmaps in <out> so that they cover the same extent as 89 * the corresponding bitmaps in <templates>. 90 */ 91bool dvmHeapBitmapInitListFromTemplates(HeapBitmap out[], 92 HeapBitmap templates[], size_t numBitmaps, const char *name); 93 94/* 95 * Clean up any resources associated with the bitmap. 96 */ 97void dvmHeapBitmapDelete(HeapBitmap *hb); 98 99/* 100 * Clean up any resources associated with the bitmaps. 101 */ 102void dvmHeapBitmapDeleteList(HeapBitmap hbs[], size_t numBitmaps); 103 104/* 105 * Fill the bitmap with zeroes. Returns the bitmap's memory to 106 * the system as a side-effect. 107 */ 108void dvmHeapBitmapZero(HeapBitmap *hb); 109 110/* 111 * Walk through the bitmaps in increasing address order, and find the 112 * object pointers that correspond to places where the bitmaps differ. 113 * Call <callback> zero or more times with lists of these object pointers. 114 * 115 * The <finger> argument to the callback indicates the next-highest 116 * address that hasn't been visited yet; setting bits for objects whose 117 * addresses are less than <finger> are not guaranteed to be seen by 118 * the current XorWalk. <finger> will be set to ULONG_MAX when the 119 * end of the bitmap is reached. 120 */ 121bool dvmHeapBitmapXorWalk(const HeapBitmap *hb1, const HeapBitmap *hb2, 122 bool (*callback)(size_t numPtrs, void **ptrs, 123 const void *finger, void *arg), 124 void *callbackArg); 125 126/* 127 * Similar to dvmHeapBitmapXorWalk(), but compare multiple bitmaps. 128 * Regardless of the order of the arrays, the bitmaps will be visited 129 * in address order, so that finger will increase monotonically. 130 */ 131bool dvmHeapBitmapXorWalkLists(const HeapBitmap hbs1[], const HeapBitmap hbs2[], 132 size_t numBitmaps, 133 bool (*callback)(size_t numPtrs, void **ptrs, 134 const void *finger, void *arg), 135 void *callbackArg); 136 137/* 138 * Similar to dvmHeapBitmapXorWalk(), but visit the set bits 139 * in a single bitmap. 140 */ 141bool dvmHeapBitmapWalk(const HeapBitmap *hb, 142 bool (*callback)(size_t numPtrs, void **ptrs, 143 const void *finger, void *arg), 144 void *callbackArg); 145 146/* 147 * Similar to dvmHeapBitmapXorWalkList(), but visit the set bits 148 * in a single list of bitmaps. Regardless of the order of the array, 149 * the bitmaps will be visited in address order, so that finger will 150 * increase monotonically. 151 */ 152bool dvmHeapBitmapWalkList(const HeapBitmap hbs[], size_t numBitmaps, 153 bool (*callback)(size_t numPtrs, void **ptrs, 154 const void *finger, void *arg), 155 void *callbackArg); 156/* 157 * Return true iff <obj> is within the range of pointers that 158 * have had corresponding bits set in this bitmap. 159 */ 160HB_INLINE_PROTO( 161 bool 162 dvmHeapBitmapMayContainObject(const HeapBitmap *hb, 163 const void *obj) 164) 165{ 166 const uintptr_t p = (const uintptr_t)obj; 167 168 assert((p & (HB_OBJECT_ALIGNMENT - 1)) == 0); 169 170 return p >= hb->base && p <= hb->max; 171} 172 173/* 174 * Return true iff <obj> is within the range of pointers that this 175 * bitmap could potentially cover, even if a bit has not been set 176 * for it. 177 */ 178HB_INLINE_PROTO( 179 bool 180 dvmHeapBitmapCoversAddress(const HeapBitmap *hb, const void *obj) 181) 182{ 183 assert(hb != NULL); 184 185 if (obj != NULL) { 186 const uintptr_t offset = (uintptr_t)obj - hb->base; 187 const size_t index = HB_OFFSET_TO_INDEX(offset); 188 return index < hb->bitsLen / sizeof(*hb->bits); 189 } 190 return false; 191} 192 193/* 194 * Internal function; do not call directly. 195 */ 196HB_INLINE_PROTO( 197 unsigned long int 198 _heapBitmapModifyObjectBit(HeapBitmap *hb, const void *obj, 199 bool setBit, bool returnOld) 200) 201{ 202 const uintptr_t offset = (uintptr_t)obj - hb->base; 203 const size_t index = HB_OFFSET_TO_INDEX(offset); 204 const unsigned long int mask = HB_OFFSET_TO_MASK(offset); 205 206#ifndef NDEBUG 207 assert(hb->bits != NULL); 208 assert((uintptr_t)obj >= hb->base); 209 assert(index < hb->bitsLen / sizeof(*hb->bits)); 210#endif 211 212 if (setBit) { 213 if ((uintptr_t)obj > hb->max) { 214 hb->max = (uintptr_t)obj; 215 } 216 if (returnOld) { 217 unsigned long int *p = hb->bits + index; 218 const unsigned long int word = *p; 219 *p |= mask; 220 return word & mask; 221 } else { 222 hb->bits[index] |= mask; 223 } 224 } else { 225 hb->bits[index] &= ~mask; 226 } 227 return false; 228} 229 230/* 231 * Sets the bit corresponding to <obj>, and returns the previous value 232 * of that bit (as zero or non-zero). Does no range checking to see if 233 * <obj> is outside of the coverage of the bitmap. 234 * 235 * NOTE: casting this value to a bool is dangerous, because higher 236 * set bits will be lost. 237 */ 238HB_INLINE_PROTO( 239 unsigned long int 240 dvmHeapBitmapSetAndReturnObjectBit(HeapBitmap *hb, const void *obj) 241) 242{ 243 return _heapBitmapModifyObjectBit(hb, obj, true, true); 244} 245 246/* 247 * Like dvmHeapBitmapSetAndReturnObjectBit(), but sets/returns the bit 248 * in the appropriate bitmap. Results are undefined if <obj> is not 249 * covered by any bitmap. 250 */ 251HB_INLINE_PROTO( 252 unsigned long int 253 dvmHeapBitmapSetAndReturnObjectBitInList(HeapBitmap hbs[], 254 size_t numBitmaps, const void *obj) 255) 256{ 257 size_t i; 258 259 for (i = 0; i < numBitmaps; i++) { 260 if (dvmHeapBitmapCoversAddress(&hbs[i], obj)) { 261 return dvmHeapBitmapSetAndReturnObjectBit(&hbs[i], obj); 262 } 263 } 264 265 assert(!"object not covered by any bitmap"); 266 return false; 267} 268 269/* 270 * Sets the bit corresponding to <obj>, and widens the range of seen 271 * pointers if necessary. Does no range checking. 272 */ 273HB_INLINE_PROTO( 274 void 275 dvmHeapBitmapSetObjectBit(HeapBitmap *hb, const void *obj) 276) 277{ 278 (void)_heapBitmapModifyObjectBit(hb, obj, true, false); 279} 280 281/* 282 * Clears the bit corresponding to <obj>. Does no range checking. 283 */ 284HB_INLINE_PROTO( 285 void 286 dvmHeapBitmapClearObjectBit(HeapBitmap *hb, const void *obj) 287) 288{ 289 (void)_heapBitmapModifyObjectBit(hb, obj, false, false); 290} 291 292/* 293 * Returns the current value of the bit corresponding to <obj>, 294 * as zero or non-zero. Does no range checking. 295 * 296 * NOTE: casting this value to a bool is dangerous, because higher 297 * set bits will be lost. 298 */ 299HB_INLINE_PROTO( 300 unsigned long int 301 dvmHeapBitmapIsObjectBitSet(const HeapBitmap *hb, const void *obj) 302) 303{ 304 assert(dvmHeapBitmapCoversAddress(hb, obj)); 305 assert(hb->bits != NULL); 306 assert((uintptr_t)obj >= hb->base); 307 308 if ((uintptr_t)obj <= hb->max) { 309 const uintptr_t offset = (uintptr_t)obj - hb->base; 310 return hb->bits[HB_OFFSET_TO_INDEX(offset)] & HB_OFFSET_TO_MASK(offset); 311 } else { 312 return 0; 313 } 314} 315 316/* 317 * Looks through the list of bitmaps and returns the current value of the 318 * bit corresponding to <obj>, which may be covered by any of the bitmaps. 319 * Does no range checking. 320 */ 321HB_INLINE_PROTO( 322 long 323 dvmHeapBitmapIsObjectBitSetInList(const HeapBitmap hbs[], size_t numBitmaps, 324 const void *obj) 325) 326{ 327 size_t i; 328 329 for (i = 0; i < numBitmaps; i++) { 330 if (dvmHeapBitmapCoversAddress(&hbs[i], obj)) { 331 return dvmHeapBitmapIsObjectBitSet(&hbs[i], obj); 332 } 333 } 334 return false; 335} 336 337#undef HB_INLINE_PROTO 338 339#endif // _DALVIK_HEAP_BITMAP 340