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