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