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 17 #include "Dalvik.h" 18 #include "HeapBitmap.h" 19 #include "clz.h" 20 #include <limits.h> // for ULONG_MAX 21 #include <sys/mman.h> // for madvise(), mmap() 22 #include <cutils/ashmem.h> 23 24 #define HB_ASHMEM_NAME "dalvik-heap-bitmap" 25 26 #define ALIGN_UP_TO_PAGE_SIZE(p) \ 27 (((size_t)(p) + (SYSTEM_PAGE_SIZE - 1)) & ~(SYSTEM_PAGE_SIZE - 1)) 28 29 #define LIKELY(exp) (__builtin_expect((exp) != 0, true)) 30 #define UNLIKELY(exp) (__builtin_expect((exp) != 0, false)) 31 32 /* 33 * Initialize a HeapBitmap so that it points to a bitmap large 34 * enough to cover a heap at <base> of <maxSize> bytes, where 35 * objects are guaranteed to be HB_OBJECT_ALIGNMENT-aligned. 36 */ 37 bool 38 dvmHeapBitmapInit(HeapBitmap *hb, const void *base, size_t maxSize, 39 const char *name) 40 { 41 void *bits; 42 size_t bitsLen; 43 size_t allocLen; 44 int fd; 45 char nameBuf[ASHMEM_NAME_LEN] = HB_ASHMEM_NAME; 46 47 assert(hb != NULL); 48 49 bitsLen = HB_OFFSET_TO_INDEX(maxSize) * sizeof(*hb->bits); 50 allocLen = ALIGN_UP_TO_PAGE_SIZE(bitsLen); // required by ashmem 51 52 if (name != NULL) { 53 snprintf(nameBuf, sizeof(nameBuf), HB_ASHMEM_NAME "/%s", name); 54 } 55 fd = ashmem_create_region(nameBuf, allocLen); 56 if (fd < 0) { 57 LOGE("Could not create %zu-byte ashmem region \"%s\" to cover " 58 "%zu-byte heap (%d)\n", 59 allocLen, nameBuf, maxSize, fd); 60 return false; 61 } 62 63 bits = mmap(NULL, bitsLen, PROT_READ | PROT_WRITE, MAP_PRIVATE, fd, 0); 64 close(fd); 65 if (bits == MAP_FAILED) { 66 LOGE("Could not mmap %d-byte ashmem region \"%s\"\n", 67 bitsLen, nameBuf); 68 return false; 69 } 70 71 memset(hb, 0, sizeof(*hb)); 72 hb->bits = bits; 73 hb->bitsLen = bitsLen; 74 hb->base = (uintptr_t)base; 75 hb->max = hb->base - 1; 76 77 return true; 78 } 79 80 /* 81 * Initialize <hb> so that it covers the same extent as <templateBitmap>. 82 */ 83 bool 84 dvmHeapBitmapInitFromTemplate(HeapBitmap *hb, const HeapBitmap *templateBitmap, 85 const char *name) 86 { 87 return dvmHeapBitmapInit(hb, 88 (void *)templateBitmap->base, HB_MAX_OFFSET(templateBitmap), name); 89 } 90 91 /* 92 * Initialize the bitmaps in <out> so that they cover the same extent as 93 * the corresponding bitmaps in <templates>. 94 */ 95 bool 96 dvmHeapBitmapInitListFromTemplates(HeapBitmap out[], HeapBitmap templates[], 97 size_t numBitmaps, const char *name) 98 { 99 size_t i; 100 char fullName[PATH_MAX]; 101 102 fullName[sizeof(fullName)-1] = '\0'; 103 for (i = 0; i < numBitmaps; i++) { 104 bool ok; 105 106 /* If two ashmem regions have the same name, only one gets 107 * the name when looking at the maps. 108 */ 109 snprintf(fullName, sizeof(fullName)-1, "%s/%zd", name, i); 110 111 ok = dvmHeapBitmapInitFromTemplate(&out[i], &templates[i], fullName); 112 if (!ok) { 113 dvmHeapBitmapDeleteList(out, i); 114 return false; 115 } 116 } 117 return true; 118 } 119 120 /* 121 * Clean up any resources associated with the bitmap. 122 */ 123 void 124 dvmHeapBitmapDelete(HeapBitmap *hb) 125 { 126 assert(hb != NULL); 127 128 if (hb->bits != NULL) { 129 // Re-calculate the size we passed to mmap(). 130 size_t allocLen = ALIGN_UP_TO_PAGE_SIZE(hb->bitsLen); 131 munmap((char *)hb->bits, allocLen); 132 } 133 memset(hb, 0, sizeof(*hb)); 134 } 135 136 /* 137 * Clean up any resources associated with the bitmaps. 138 */ 139 void 140 dvmHeapBitmapDeleteList(HeapBitmap hbs[], size_t numBitmaps) 141 { 142 size_t i; 143 144 for (i = 0; i < numBitmaps; i++) { 145 dvmHeapBitmapDelete(&hbs[i]); 146 } 147 } 148 149 /* 150 * Fill the bitmap with zeroes. Returns the bitmap's memory to 151 * the system as a side-effect. 152 */ 153 void 154 dvmHeapBitmapZero(HeapBitmap *hb) 155 { 156 assert(hb != NULL); 157 158 if (hb->bits != NULL) { 159 /* This returns the memory to the system. 160 * Successive page faults will return zeroed memory. 161 */ 162 madvise(hb->bits, hb->bitsLen, MADV_DONTNEED); 163 hb->max = hb->base - 1; 164 } 165 } 166 167 /* 168 * Walk through the bitmaps in increasing address order, and find the 169 * object pointers that correspond to places where the bitmaps differ. 170 * Call <callback> zero or more times with lists of these object pointers. 171 * 172 * The <finger> argument to the callback indicates the next-highest 173 * address that hasn't been visited yet; setting bits for objects whose 174 * addresses are less than <finger> are not guaranteed to be seen by 175 * the current XorWalk. <finger> will be set to ULONG_MAX when the 176 * end of the bitmap is reached. 177 */ 178 bool 179 dvmHeapBitmapXorWalk(const HeapBitmap *hb1, const HeapBitmap *hb2, 180 bool (*callback)(size_t numPtrs, void **ptrs, 181 const void *finger, void *arg), 182 void *callbackArg) 183 { 184 static const size_t kPointerBufSize = 128; 185 void *pointerBuf[kPointerBufSize]; 186 void **pb = pointerBuf; 187 size_t index; 188 size_t i; 189 190 #define FLUSH_POINTERBUF(finger_) \ 191 do { \ 192 if (!callback(pb - pointerBuf, (void **)pointerBuf, \ 193 (void *)(finger_), callbackArg)) \ 194 { \ 195 LOGW("dvmHeapBitmapXorWalk: callback failed\n"); \ 196 return false; \ 197 } \ 198 pb = pointerBuf; \ 199 } while (false) 200 201 #define DECODE_BITS(hb_, bits_, update_index_) \ 202 do { \ 203 if (UNLIKELY(bits_ != 0)) { \ 204 static const unsigned long kHighBit = \ 205 (unsigned long)1 << (HB_BITS_PER_WORD - 1); \ 206 const uintptr_t ptrBase = HB_INDEX_TO_OFFSET(i) + hb_->base; \ 207 /*TODO: hold onto ptrBase so we can shrink max later if possible */ \ 208 /*TODO: see if this is likely or unlikely */ \ 209 while (bits_ != 0) { \ 210 const int rshift = CLZ(bits_); \ 211 bits_ &= ~(kHighBit >> rshift); \ 212 *pb++ = (void *)(ptrBase + rshift * HB_OBJECT_ALIGNMENT); \ 213 } \ 214 /* Make sure that there are always enough slots available */ \ 215 /* for an entire word of 1s. */ \ 216 if (kPointerBufSize - (pb - pointerBuf) < HB_BITS_PER_WORD) { \ 217 FLUSH_POINTERBUF(ptrBase + \ 218 HB_BITS_PER_WORD * HB_OBJECT_ALIGNMENT); \ 219 if (update_index_) { \ 220 /* The callback may have caused hb_->max to grow. */ \ 221 index = HB_OFFSET_TO_INDEX(hb_->max - hb_->base); \ 222 } \ 223 } \ 224 } \ 225 } while (false) 226 227 assert(hb1 != NULL); 228 assert(hb1->bits != NULL); 229 assert(hb2 != NULL); 230 assert(hb2->bits != NULL); 231 assert(callback != NULL); 232 233 if (hb1->base != hb2->base) { 234 LOGW("dvmHeapBitmapXorWalk: bitmaps cover different heaps " 235 "(0x%08x != 0x%08x)\n", 236 (uintptr_t)hb1->base, (uintptr_t)hb2->base); 237 return false; 238 } 239 if (hb1->bitsLen != hb2->bitsLen) { 240 LOGW("dvmHeapBitmapXorWalk: size of bitmaps differ (%zd != %zd)\n", 241 hb1->bitsLen, hb2->bitsLen); 242 return false; 243 } 244 if (hb1->max < hb1->base && hb2->max < hb2->base) { 245 /* Easy case; both are obviously empty. 246 */ 247 return true; 248 } 249 250 /* First, walk along the section of the bitmaps that may be the same. 251 */ 252 if (hb1->max >= hb1->base && hb2->max >= hb2->base) { 253 unsigned long int *p1, *p2; 254 uintptr_t offset; 255 256 offset = ((hb1->max < hb2->max) ? hb1->max : hb2->max) - hb1->base; 257 //TODO: keep track of which (and whether) one is longer for later 258 index = HB_OFFSET_TO_INDEX(offset); 259 260 p1 = hb1->bits; 261 p2 = hb2->bits; 262 for (i = 0; i <= index; i++) { 263 //TODO: unroll this. pile up a few in locals? 264 unsigned long int diff = *p1++ ^ *p2++; 265 DECODE_BITS(hb1, diff, false); 266 //BUG: if the callback was called, either max could have changed. 267 } 268 /* The next index to look at. 269 */ 270 index++; 271 } else { 272 /* One of the bitmaps is empty. 273 */ 274 index = 0; 275 } 276 277 /* If one bitmap's max is larger, walk through the rest of the 278 * set bits. 279 */ 280 const HeapBitmap *longHb; 281 unsigned long int *p; 282 //TODO: may be the same size, in which case this is wasted work 283 longHb = (hb1->max > hb2->max) ? hb1 : hb2; 284 i = index; 285 index = HB_OFFSET_TO_INDEX(longHb->max - longHb->base); 286 p = longHb->bits + i; 287 for (/* i = i */; i <= index; i++) { 288 //TODO: unroll this 289 unsigned long bits = *p++; 290 DECODE_BITS(longHb, bits, true); 291 } 292 293 if (pb > pointerBuf) { 294 /* Set the finger to the end of the heap (rather than longHb->max) 295 * so that the callback doesn't expect to be called again 296 * if it happens to change the current max. 297 */ 298 FLUSH_POINTERBUF(longHb->base + HB_MAX_OFFSET(longHb)); 299 } 300 301 return true; 302 303 #undef FLUSH_POINTERBUF 304 #undef DECODE_BITS 305 } 306 307 /* 308 * Fills outIndexList with indices so that for all i: 309 * 310 * hb[outIndexList[i]].base < hb[outIndexList[i+1]].base 311 */ 312 static void 313 createSortedBitmapIndexList(const HeapBitmap hbs[], size_t numBitmaps, 314 size_t outIndexList[]) 315 { 316 int i, j; 317 318 /* numBitmaps is usually 2 or 3, so use a simple sort */ 319 for (i = 0; i < (int) numBitmaps; i++) { 320 outIndexList[i] = i; 321 for (j = 0; j < i; j++) { 322 if (hbs[j].base > hbs[i].base) { 323 int tmp = outIndexList[i]; 324 outIndexList[i] = outIndexList[j]; 325 outIndexList[j] = tmp; 326 } 327 } 328 } 329 } 330 331 /* 332 * Similar to dvmHeapBitmapXorWalk(), but compare multiple bitmaps. 333 * Regardless of the order of the arrays, the bitmaps will be visited 334 * in address order, so that finger will increase monotonically. 335 */ 336 bool 337 dvmHeapBitmapXorWalkLists(const HeapBitmap hbs1[], const HeapBitmap hbs2[], 338 size_t numBitmaps, 339 bool (*callback)(size_t numPtrs, void **ptrs, 340 const void *finger, void *arg), 341 void *callbackArg) 342 { 343 size_t indexList[numBitmaps]; 344 size_t i; 345 346 /* Sort the bitmaps by address. Assume that the two lists contain 347 * congruent bitmaps. 348 */ 349 createSortedBitmapIndexList(hbs1, numBitmaps, indexList); 350 351 /* Walk each pair of bitmaps, lowest address first. 352 */ 353 for (i = 0; i < numBitmaps; i++) { 354 bool ok; 355 356 ok = dvmHeapBitmapXorWalk(&hbs1[indexList[i]], &hbs2[indexList[i]], 357 callback, callbackArg); 358 if (!ok) { 359 return false; 360 } 361 } 362 363 return true; 364 } 365 366 /* 367 * Similar to dvmHeapBitmapXorWalk(), but visit the set bits 368 * in a single bitmap. 369 */ 370 bool 371 dvmHeapBitmapWalk(const HeapBitmap *hb, 372 bool (*callback)(size_t numPtrs, void **ptrs, 373 const void *finger, void *arg), 374 void *callbackArg) 375 { 376 /* Create an empty bitmap with the same extent as <hb>. 377 * Don't actually allocate any memory. 378 */ 379 HeapBitmap emptyHb = *hb; 380 emptyHb.max = emptyHb.base - 1; // empty 381 emptyHb.bits = (void *)1; // non-NULL but intentionally bad 382 383 return dvmHeapBitmapXorWalk(hb, &emptyHb, callback, callbackArg); 384 } 385 386 /* 387 * Similar to dvmHeapBitmapXorWalkList(), but visit the set bits 388 * in a single list of bitmaps. Regardless of the order of the array, 389 * the bitmaps will be visited in address order, so that finger will 390 * increase monotonically. 391 */ 392 bool dvmHeapBitmapWalkList(const HeapBitmap hbs[], size_t numBitmaps, 393 bool (*callback)(size_t numPtrs, void **ptrs, 394 const void *finger, void *arg), 395 void *callbackArg) 396 { 397 size_t indexList[numBitmaps]; 398 size_t i; 399 400 /* Sort the bitmaps by address. 401 */ 402 createSortedBitmapIndexList(hbs, numBitmaps, indexList); 403 404 /* Walk each bitmap, lowest address first. 405 */ 406 for (i = 0; i < numBitmaps; i++) { 407 bool ok; 408 409 ok = dvmHeapBitmapWalk(&hbs[indexList[i]], callback, callbackArg); 410 if (!ok) { 411 return false; 412 } 413 } 414 415 return true; 416 } 417