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 <limits.h> 20 #include <stdint.h> 21 #include "clz.h" 22 23 #define HB_OBJECT_ALIGNMENT 8 24 #define HB_BITS_PER_WORD (sizeof(unsigned long) * CHAR_BIT) 25 26 /* <offset> is the difference from .base to a pointer address. 27 * <index> is the index of .bits that contains the bit representing 28 * <offset>. 29 */ 30 #define HB_OFFSET_TO_INDEX(offset_) \ 31 ((uintptr_t)(offset_) / HB_OBJECT_ALIGNMENT / HB_BITS_PER_WORD) 32 #define HB_INDEX_TO_OFFSET(index_) \ 33 ((uintptr_t)(index_) * HB_OBJECT_ALIGNMENT * HB_BITS_PER_WORD) 34 35 #define HB_OFFSET_TO_BYTE_INDEX(offset_) \ 36 (HB_OFFSET_TO_INDEX(offset_) * sizeof(*((HeapBitmap *)0)->bits)) 37 38 /* Pack the bits in backwards so they come out in address order 39 * when using CLZ. 40 */ 41 #define HB_OFFSET_TO_MASK(offset_) \ 42 (1 << \ 43 (31-(((uintptr_t)(offset_) / HB_OBJECT_ALIGNMENT) % HB_BITS_PER_WORD))) 44 45 /* Return the maximum offset (exclusive) that <hb> can represent. 46 */ 47 #define HB_MAX_OFFSET(hb_) \ 48 HB_INDEX_TO_OFFSET((hb_)->bitsLen / sizeof(*(hb_)->bits)) 49 50 #define HB_INLINE_PROTO(p) \ 51 static inline p __attribute__((always_inline)); \ 52 static inline p 53 54 typedef struct { 55 /* The bitmap data, which points to an mmap()ed area of zeroed 56 * anonymous memory. 57 */ 58 unsigned long *bits; 59 60 /* The size of the used memory pointed to by bits, in bytes. This 61 * value changes when the bitmap is shrunk. 62 */ 63 size_t bitsLen; 64 65 /* The real size of the memory pointed to by bits. This is the 66 * number of bytes we requested from the allocator and does not 67 * change. 68 */ 69 size_t allocLen; 70 71 /* The base address, which corresponds to the first bit in 72 * the bitmap. 73 */ 74 uintptr_t base; 75 76 /* The highest pointer value ever returned by an allocation 77 * from this heap. I.e., the highest address that may correspond 78 * to a set bit. If there are no bits set, (max < base). 79 */ 80 uintptr_t max; 81 } HeapBitmap; 82 83 typedef void BitmapCallback(void *addr, void *arg); 84 typedef void BitmapScanCallback(void *addr, void *finger, void *arg); 85 typedef void BitmapSweepCallback(size_t numPtrs, void **ptrs, void *arg); 86 87 /* 88 * Initialize a HeapBitmap so that it points to a bitmap large 89 * enough to cover a heap at <base> of <maxSize> bytes, where 90 * objects are guaranteed to be HB_OBJECT_ALIGNMENT-aligned. 91 */ 92 bool dvmHeapBitmapInit(HeapBitmap *hb, const void *base, size_t maxSize, 93 const char *name); 94 95 /* 96 * Clean up any resources associated with the bitmap. 97 */ 98 void dvmHeapBitmapDelete(HeapBitmap *hb); 99 100 /* 101 * Fill the bitmap with zeroes. Returns the bitmap's memory to 102 * the system as a side-effect. 103 */ 104 void dvmHeapBitmapZero(HeapBitmap *hb); 105 106 /* 107 * Visits set bits in address order. The callback is not permitted to 108 * change the bitmap bits or max during the traversal. 109 */ 110 HB_INLINE_PROTO( 111 void 112 dvmHeapBitmapWalk(const HeapBitmap *bitmap, 113 BitmapCallback *callback, void *arg) 114 ) 115 { 116 assert(bitmap != NULL); 117 assert(bitmap->bits != NULL); 118 assert(callback != NULL); 119 uintptr_t end = HB_OFFSET_TO_INDEX(bitmap->max - bitmap->base); 120 uintptr_t i; 121 for (i = 0; i <= end; ++i) { 122 unsigned long word = bitmap->bits[i]; 123 if (UNLIKELY(word != 0)) { 124 unsigned long highBit = 1 << (HB_BITS_PER_WORD - 1); 125 uintptr_t ptrBase = HB_INDEX_TO_OFFSET(i) + bitmap->base; 126 while (word != 0) { 127 const int shift = CLZ(word); 128 void *addr = (void *)(ptrBase + shift * HB_OBJECT_ALIGNMENT); 129 (*callback)(addr, arg); 130 word &= ~(highBit >> shift); 131 } 132 } 133 } 134 } 135 136 /* 137 * Similar to dvmHeapBitmapWalk but the callback routine is permitted 138 * to change the bitmap bits and max during traversal. Used by the 139 * the root marking scan exclusively. 140 * 141 * The callback is invoked with a finger argument. The finger is a 142 * pointer to an address not yet visited by the traversal. If the 143 * callback sets a bit for an address at or above the finger, this 144 * address will be visited by the traversal. If the callback sets a 145 * bit for an address below the finger, this address will not be 146 * visited. 147 */ 148 HB_INLINE_PROTO( 149 void 150 dvmHeapBitmapScanWalk(HeapBitmap *bitmap, 151 BitmapScanCallback *callback, void *arg) 152 ) 153 { 154 assert(bitmap != NULL); 155 assert(bitmap->bits != NULL); 156 assert(callback != NULL); 157 uintptr_t end = HB_OFFSET_TO_INDEX(bitmap->max - bitmap->base); 158 uintptr_t i; 159 for (i = 0; i <= end; ++i) { 160 unsigned long word = bitmap->bits[i]; 161 if (UNLIKELY(word != 0)) { 162 unsigned long highBit = 1 << (HB_BITS_PER_WORD - 1); 163 uintptr_t ptrBase = HB_INDEX_TO_OFFSET(i) + bitmap->base; 164 void *finger = (void *)(HB_INDEX_TO_OFFSET(i + 1) + bitmap->base); 165 while (word != 0) { 166 const int shift = CLZ(word); 167 void *addr = (void *)(ptrBase + shift * HB_OBJECT_ALIGNMENT); 168 (*callback)(addr, finger, arg); 169 word &= ~(highBit >> shift); 170 } 171 end = HB_OFFSET_TO_INDEX(bitmap->max - bitmap->base); 172 } 173 } 174 } 175 176 /* 177 * Walk through the bitmaps in increasing address order, and find the 178 * object pointers that correspond to garbage objects. Call 179 * <callback> zero or more times with lists of these object pointers. 180 * 181 * The callback is permitted to increase the bitmap's max; the walk 182 * will use the updated max as a terminating condition. 183 */ 184 void dvmHeapBitmapSweepWalk(const HeapBitmap *liveHb, const HeapBitmap *markHb, 185 BitmapSweepCallback *callback, void *callbackArg); 186 187 /* 188 * Return true iff <obj> is within the range of pointers that this 189 * bitmap could potentially cover, even if a bit has not been set 190 * for it. 191 */ 192 HB_INLINE_PROTO( 193 bool 194 dvmHeapBitmapCoversAddress(const HeapBitmap *hb, const void *obj) 195 ) 196 { 197 assert(hb != NULL); 198 199 if (obj != NULL) { 200 const uintptr_t offset = (uintptr_t)obj - hb->base; 201 const size_t index = HB_OFFSET_TO_INDEX(offset); 202 return index < hb->bitsLen / sizeof(*hb->bits); 203 } 204 return false; 205 } 206 207 /* 208 * Internal function; do not call directly. 209 */ 210 HB_INLINE_PROTO( 211 unsigned long 212 _heapBitmapModifyObjectBit(HeapBitmap *hb, const void *obj, 213 bool setBit, bool returnOld) 214 ) 215 { 216 const uintptr_t offset = (uintptr_t)obj - hb->base; 217 const size_t index = HB_OFFSET_TO_INDEX(offset); 218 const unsigned long mask = HB_OFFSET_TO_MASK(offset); 219 220 assert(hb->bits != NULL); 221 assert((uintptr_t)obj >= hb->base); 222 assert(index < hb->bitsLen / sizeof(*hb->bits)); 223 224 if (setBit) { 225 if ((uintptr_t)obj > hb->max) { 226 hb->max = (uintptr_t)obj; 227 } 228 if (returnOld) { 229 unsigned long *p = hb->bits + index; 230 const unsigned long word = *p; 231 *p |= mask; 232 return word & mask; 233 } else { 234 hb->bits[index] |= mask; 235 } 236 } else { 237 hb->bits[index] &= ~mask; 238 } 239 return false; 240 } 241 242 /* 243 * Sets the bit corresponding to <obj>, and returns the previous value 244 * of that bit (as zero or non-zero). Does no range checking to see if 245 * <obj> is outside of the coverage of the bitmap. 246 * 247 * NOTE: casting this value to a bool is dangerous, because higher 248 * set bits will be lost. 249 */ 250 HB_INLINE_PROTO( 251 unsigned long 252 dvmHeapBitmapSetAndReturnObjectBit(HeapBitmap *hb, const void *obj) 253 ) 254 { 255 return _heapBitmapModifyObjectBit(hb, obj, true, true); 256 } 257 258 /* 259 * Sets the bit corresponding to <obj>, and widens the range of seen 260 * pointers if necessary. Does no range checking. 261 */ 262 HB_INLINE_PROTO( 263 void 264 dvmHeapBitmapSetObjectBit(HeapBitmap *hb, const void *obj) 265 ) 266 { 267 (void)_heapBitmapModifyObjectBit(hb, obj, true, false); 268 } 269 270 /* 271 * Clears the bit corresponding to <obj>. Does no range checking. 272 */ 273 HB_INLINE_PROTO( 274 void 275 dvmHeapBitmapClearObjectBit(HeapBitmap *hb, const void *obj) 276 ) 277 { 278 (void)_heapBitmapModifyObjectBit(hb, obj, false, false); 279 } 280 281 /* 282 * Returns the current value of the bit corresponding to <obj>, 283 * as zero or non-zero. Does no range checking. 284 * 285 * NOTE: casting this value to a bool is dangerous, because higher 286 * set bits will be lost. 287 */ 288 HB_INLINE_PROTO( 289 unsigned long 290 dvmHeapBitmapIsObjectBitSet(const HeapBitmap *hb, const void *obj) 291 ) 292 { 293 assert(dvmHeapBitmapCoversAddress(hb, obj)); 294 assert(hb->bits != NULL); 295 assert((uintptr_t)obj >= hb->base); 296 297 if ((uintptr_t)obj <= hb->max) { 298 const uintptr_t offset = (uintptr_t)obj - hb->base; 299 return hb->bits[HB_OFFSET_TO_INDEX(offset)] & HB_OFFSET_TO_MASK(offset); 300 } else { 301 return 0; 302 } 303 } 304 305 #undef HB_INLINE_PROTO 306 307 #endif // _DALVIK_HEAP_BITMAP 308
