1 /* 2 * Copyright (C) 2009 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 /* 18 * Indirect reference table management. 19 */ 20 #include "Dalvik.h" 21 22 /* 23 * Initialize an IndirectRefTable structure. 24 */ 25 bool dvmInitIndirectRefTable(IndirectRefTable* pRef, int initialCount, 26 int maxCount, IndirectRefKind kind) 27 { 28 assert(initialCount > 0); 29 assert(initialCount <= maxCount); 30 assert(kind == kIndirectKindLocal || kind == kIndirectKindGlobal); 31 32 pRef->table = (Object**) malloc(initialCount * sizeof(Object*)); 33 if (pRef->table == NULL) 34 return false; 35 #ifndef NDEBUG 36 memset(pRef->table, 0xd1, initialCount * sizeof(Object*)); 37 #endif 38 39 pRef->slotData = 40 (IndirectRefSlot*) calloc(maxCount, sizeof(IndirectRefSlot)); 41 if (pRef->slotData == NULL) 42 return false; 43 44 pRef->segmentState.all = IRT_FIRST_SEGMENT; 45 pRef->allocEntries = initialCount; 46 pRef->maxEntries = maxCount; 47 pRef->kind = kind; 48 49 return true; 50 } 51 52 /* 53 * Clears out the contents of a IndirectRefTable, freeing allocated storage. 54 */ 55 void dvmClearIndirectRefTable(IndirectRefTable* pRef) 56 { 57 free(pRef->table); 58 pRef->table = NULL; 59 pRef->allocEntries = pRef->maxEntries = -1; 60 } 61 62 /* 63 * Remove one or more segments from the top. The table entry identified 64 * by "cookie" becomes the new top-most entry. 65 * 66 * Returns false if "cookie" is invalid or the table has only one segment. 67 */ 68 bool dvmPopIndirectRefTableSegmentCheck(IndirectRefTable* pRef, u4 cookie) 69 { 70 IRTSegmentState sst; 71 72 /* 73 * The new value for "top" must be <= the current value. Otherwise 74 * this would represent an expansion of the table. 75 */ 76 sst.all = cookie; 77 if (sst.parts.topIndex > pRef->segmentState.parts.topIndex) { 78 LOGE("Attempt to expand table with segment pop (%d to %d)\n", 79 pRef->segmentState.parts.topIndex, sst.parts.topIndex); 80 return false; 81 } 82 if (sst.parts.numHoles >= sst.parts.topIndex) { 83 LOGE("Absurd numHoles in cookie (%d bi=%d)\n", 84 sst.parts.numHoles, sst.parts.topIndex); 85 return false; 86 } 87 88 LOGV("IRT %p[%d]: pop, top=%d holes=%d\n", 89 pRef, pRef->kind, sst.parts.topIndex, sst.parts.numHoles); 90 91 return true; 92 } 93 94 /* 95 * Make sure that the entry at "idx" is correctly paired with "iref". 96 */ 97 static bool checkEntry(IndirectRefTable* pRef, IndirectRef iref, int idx) 98 { 99 Object* obj = pRef->table[idx]; 100 IndirectRef checkRef = dvmObjectToIndirectRef(pRef, obj, idx, pRef->kind); 101 if (checkRef != iref) { 102 LOGW("IRT %p[%d]: iref mismatch (req=%p vs cur=%p)\n", 103 pRef, pRef->kind, iref, checkRef); 104 return false; 105 } 106 return true; 107 } 108 109 /* 110 * Update extended debug info when an entry is added. 111 * 112 * We advance the serial number, invalidating any outstanding references to 113 * this slot. 114 */ 115 static inline void updateSlotAdd(IndirectRefTable* pRef, Object* obj, int slot) 116 { 117 if (pRef->slotData != NULL) { 118 IndirectRefSlot* pSlot = &pRef->slotData[slot]; 119 pSlot->serial++; 120 //LOGI("+++ add [%d] slot %d (%p->%p), serial=%d\n", 121 // pRef->kind, slot, obj, iref, pSlot->serial); 122 pSlot->previous[pSlot->serial % kIRTPrevCount] = obj; 123 } 124 } 125 126 /* 127 * Update extended debug info when an entry is removed. 128 */ 129 static inline void updateSlotRemove(IndirectRefTable* pRef, int slot) 130 { 131 if (pRef->slotData != NULL) { 132 //IndirectRefSlot* pSlot = &pRef->slotData[slot]; 133 //LOGI("+++ remove [%d] slot %d, serial now %d\n", 134 // pRef->kind, slot, pSlot->serial); 135 } 136 } 137 138 /* 139 * Add "obj" to "pRef". 140 */ 141 IndirectRef dvmAddToIndirectRefTable(IndirectRefTable* pRef, u4 cookie, 142 Object* obj) 143 { 144 IRTSegmentState prevState; 145 prevState.all = cookie; 146 int topIndex = pRef->segmentState.parts.topIndex; 147 148 assert(obj != NULL); 149 assert(dvmIsValidObject(obj)); 150 assert(pRef->table != NULL); 151 assert(pRef->allocEntries <= pRef->maxEntries); 152 assert(pRef->segmentState.parts.numHoles >= prevState.parts.numHoles); 153 154 if (topIndex == pRef->allocEntries) { 155 /* reached end of allocated space; did we hit buffer max? */ 156 if (topIndex == pRef->maxEntries) { 157 LOGW("IndirectRefTable overflow (max=%d)\n", pRef->maxEntries); 158 return NULL; 159 } 160 161 Object** newTable; 162 int newSize; 163 164 newSize = pRef->allocEntries * 2; 165 if (newSize > pRef->maxEntries) 166 newSize = pRef->maxEntries; 167 assert(newSize > pRef->allocEntries); 168 169 newTable = (Object**) realloc(pRef->table, newSize * sizeof(Object*)); 170 if (newTable == NULL) { 171 LOGE("Unable to expand iref table (from %d to %d, max=%d)\n", 172 pRef->allocEntries, newSize, pRef->maxEntries); 173 return false; 174 } 175 LOGI("Growing ireftab %p from %d to %d (max=%d)\n", 176 pRef, pRef->allocEntries, newSize, pRef->maxEntries); 177 178 /* update entries; adjust "nextEntry" in case memory moved */ 179 pRef->table = newTable; 180 pRef->allocEntries = newSize; 181 } 182 183 IndirectRef result; 184 185 /* 186 * We know there's enough room in the table. Now we just need to find 187 * the right spot. If there's a hole, find it and fill it; otherwise, 188 * add to the end of the list. 189 */ 190 int numHoles = pRef->segmentState.parts.numHoles - prevState.parts.numHoles; 191 if (numHoles > 0) { 192 assert(topIndex > 1); 193 /* find the first hole; likely to be near the end of the list */ 194 Object** pScan = &pRef->table[topIndex - 1]; 195 assert(*pScan != NULL); 196 while (*--pScan != NULL) { 197 assert(pScan >= pRef->table + prevState.parts.topIndex); 198 } 199 updateSlotAdd(pRef, obj, pScan - pRef->table); 200 result = dvmObjectToIndirectRef(pRef, obj, pScan - pRef->table, 201 pRef->kind); 202 *pScan = obj; 203 pRef->segmentState.parts.numHoles--; 204 } else { 205 /* add to the end */ 206 updateSlotAdd(pRef, obj, topIndex); 207 result = dvmObjectToIndirectRef(pRef, obj, topIndex, pRef->kind); 208 pRef->table[topIndex++] = obj; 209 pRef->segmentState.parts.topIndex = topIndex; 210 } 211 212 assert(result != NULL); 213 return result; 214 } 215 216 /* 217 * Verify that the indirect table lookup is valid. 218 * 219 * Returns "false" if something looks bad. 220 */ 221 bool dvmGetFromIndirectRefTableCheck(IndirectRefTable* pRef, IndirectRef iref) 222 { 223 if (dvmGetIndirectRefType(iref) == kIndirectKindInvalid) { 224 LOGW("Invalid indirect reference 0x%08x\n", (u4) iref); 225 return false; 226 } 227 228 int topIndex = pRef->segmentState.parts.topIndex; 229 int idx = dvmIndirectRefToIndex(iref); 230 231 if (iref == NULL) { 232 LOGI("--- lookup on NULL iref\n"); 233 return false; 234 } 235 if (idx >= topIndex) { 236 /* bad -- stale reference? */ 237 LOGI("Attempt to access invalid index %d (top=%d)\n", 238 idx, topIndex); 239 return false; 240 } 241 242 Object* obj = pRef->table[idx]; 243 if (obj == NULL) { 244 LOGI("Attempt to read from hole, iref=%p\n", iref); 245 return false; 246 } 247 if (!checkEntry(pRef, iref, idx)) 248 return false; 249 250 return true; 251 } 252 253 /* 254 * Remove "obj" from "pRef". We extract the table offset bits from "iref" 255 * and zap the corresponding entry, leaving a hole if it's not at the top. 256 * 257 * If the entry is not between the current top index and the bottom index 258 * specified by the cookie, we don't remove anything. This is the behavior 259 * required by JNI's DeleteLocalRef function. 260 * 261 * Note this is NOT called when a local frame is popped. This is only used 262 * for explict single removals. 263 * 264 * Returns "false" if nothing was removed. 265 */ 266 bool dvmRemoveFromIndirectRefTable(IndirectRefTable* pRef, u4 cookie, 267 IndirectRef iref) 268 { 269 IRTSegmentState prevState; 270 prevState.all = cookie; 271 int topIndex = pRef->segmentState.parts.topIndex; 272 int bottomIndex = prevState.parts.topIndex; 273 274 assert(pRef->table != NULL); 275 assert(pRef->allocEntries <= pRef->maxEntries); 276 assert(pRef->segmentState.parts.numHoles >= prevState.parts.numHoles); 277 278 int idx = dvmIndirectRefToIndex(iref); 279 if (idx < bottomIndex) { 280 /* wrong segment */ 281 LOGV("Attempt to remove index outside index area (%d vs %d-%d)\n", 282 idx, bottomIndex, topIndex); 283 return false; 284 } 285 if (idx >= topIndex) { 286 /* bad -- stale reference? */ 287 LOGI("Attempt to remove invalid index %d (bottom=%d top=%d)\n", 288 idx, bottomIndex, topIndex); 289 return false; 290 } 291 292 if (idx == topIndex-1) { 293 /* 294 * Top-most entry. Scan up and consume holes. No need to NULL 295 * out the entry, since the test vs. topIndex will catch it. 296 */ 297 if (!checkEntry(pRef, iref, idx)) 298 return false; 299 updateSlotRemove(pRef, idx); 300 301 #ifndef NDEBUG 302 pRef->table[idx] = (IndirectRef) 0xd3d3d3d3; 303 #endif 304 305 int numHoles = 306 pRef->segmentState.parts.numHoles - prevState.parts.numHoles; 307 if (numHoles != 0) { 308 while (--topIndex > bottomIndex && numHoles != 0) { 309 LOGV("+++ checking for hole at %d (cookie=0x%08x) val=%p\n", 310 topIndex-1, cookie, pRef->table[topIndex-1]); 311 if (pRef->table[topIndex-1] != NULL) 312 break; 313 LOGV("+++ ate hole at %d\n", topIndex-1); 314 numHoles--; 315 } 316 pRef->segmentState.parts.numHoles = 317 numHoles + prevState.parts.numHoles; 318 pRef->segmentState.parts.topIndex = topIndex; 319 } else { 320 pRef->segmentState.parts.topIndex = topIndex-1; 321 LOGV("+++ ate last entry %d\n", topIndex-1); 322 } 323 } else { 324 /* 325 * Not the top-most entry. This creates a hole. We NULL out the 326 * entry to prevent somebody from deleting it twice and screwing up 327 * the hole count. 328 */ 329 if (pRef->table[idx] == NULL) { 330 LOGV("--- WEIRD: removing null entry %d\n", idx); 331 return false; 332 } 333 if (!checkEntry(pRef, iref, idx)) 334 return false; 335 updateSlotRemove(pRef, idx); 336 337 pRef->table[idx] = NULL; 338 pRef->segmentState.parts.numHoles++; 339 LOGV("+++ left hole at %d, holes=%d\n", 340 idx, pRef->segmentState.parts.numHoles); 341 } 342 343 return true; 344 } 345 346 /* 347 * This is a qsort() callback. We sort Object* by class, allocation size, 348 * and then by the Object* itself. 349 */ 350 static int compareObject(const void* vobj1, const void* vobj2) 351 { 352 Object* obj1 = *((Object**) vobj1); 353 Object* obj2 = *((Object**) vobj2); 354 355 /* ensure null references appear at the end */ 356 if (obj1 == NULL) { 357 if (obj2 == NULL) { 358 return 0; 359 } else { 360 return 1; 361 } 362 } else if (obj2 == NULL) { 363 return -1; 364 } 365 366 if (obj1->clazz != obj2->clazz) { 367 return (u1*)obj1->clazz - (u1*)obj2->clazz; 368 } else { 369 int size1 = dvmObjectSizeInHeap(obj1); 370 int size2 = dvmObjectSizeInHeap(obj2); 371 if (size1 != size2) { 372 return size1 - size2; 373 } else { 374 return (u1*)obj1 - (u1*)obj2; 375 } 376 } 377 } 378 379 /* 380 * Log an object with some additional info. 381 * 382 * Pass in the number of additional elements that are identical to or 383 * equivalent to the original. 384 */ 385 static void logObject(Object* obj, int size, int identical, int equiv) 386 { 387 if (obj == NULL) { 388 LOGW(" NULL reference (count=%d)\n", equiv); 389 return; 390 } 391 392 if (identical + equiv != 0) { 393 LOGW("%5d of %s %dB (%d unique)\n", identical + equiv +1, 394 obj->clazz->descriptor, size, equiv +1); 395 } else { 396 LOGW("%5d of %s %dB\n", identical + equiv +1, 397 obj->clazz->descriptor, size); 398 } 399 } 400 401 /* 402 * Dump the contents of a IndirectRefTable to the log. 403 */ 404 void dvmDumpIndirectRefTable(const IndirectRefTable* pRef, const char* descr) 405 { 406 const int kLast = 10; 407 int count = dvmIndirectRefTableEntries(pRef); 408 Object** refs; 409 int i; 410 411 if (count == 0) { 412 LOGW("Reference table has no entries\n"); 413 return; 414 } 415 assert(count > 0); 416 417 /* 418 * Dump the most recent N entries. If there are holes, we will show 419 * fewer than N. 420 */ 421 LOGW("Last %d entries in %s reference table:\n", kLast, descr); 422 refs = pRef->table; // use unsorted list 423 int size; 424 int start = count - kLast; 425 if (start < 0) 426 start = 0; 427 428 for (i = start; i < count; i++) { 429 if (refs[i] == NULL) 430 continue; 431 size = dvmObjectSizeInHeap(refs[i]); 432 Object* ref = refs[i]; 433 if (ref->clazz == gDvm.classJavaLangClass) { 434 ClassObject* clazz = (ClassObject*) ref; 435 LOGW("%5d: %p cls=%s '%s' (%d bytes)\n", i, ref, 436 (refs[i] == NULL) ? "-" : ref->clazz->descriptor, 437 clazz->descriptor, size); 438 } else { 439 LOGW("%5d: %p cls=%s (%d bytes)\n", i, ref, 440 (refs[i] == NULL) ? "-" : ref->clazz->descriptor, size); 441 } 442 } 443 444 /* 445 * Make a copy of the table, and sort it. 446 * 447 * The NULL "holes" wind up at the end, so we can strip them off easily. 448 */ 449 Object** tableCopy = (Object**)malloc(sizeof(Object*) * count); 450 memcpy(tableCopy, pRef->table, sizeof(Object*) * count); 451 qsort(tableCopy, count, sizeof(Object*), compareObject); 452 refs = tableCopy; // use sorted list 453 454 if (false) { 455 int q; 456 for (q = 0; q < count; q++) 457 LOGI("%d %p\n", q, refs[q]); 458 } 459 460 int holes = 0; 461 while (refs[count-1] == NULL) { 462 count--; 463 holes++; 464 } 465 466 /* 467 * Dump uniquified table summary. While we're at it, generate a 468 * cumulative total amount of pinned memory based on the unique entries. 469 */ 470 LOGW("%s reference table summary (%d entries / %d holes):\n", 471 descr, count, holes); 472 int equiv, identical, total; 473 total = equiv = identical = 0; 474 for (i = 1; i < count; i++) { 475 size = dvmObjectSizeInHeap(refs[i-1]); 476 477 if (refs[i] == refs[i-1]) { 478 /* same reference, added more than once */ 479 identical++; 480 } else if (refs[i]->clazz == refs[i-1]->clazz && 481 (int) dvmObjectSizeInHeap(refs[i]) == size) 482 { 483 /* same class / size, different object */ 484 total += size; 485 equiv++; 486 } else { 487 /* different class */ 488 total += size; 489 logObject(refs[i-1], size, identical, equiv); 490 equiv = identical = 0; 491 } 492 } 493 494 /* handle the last entry (everything above outputs refs[i-1]) */ 495 size = (refs[count-1] == NULL) ? 0 : dvmObjectSizeInHeap(refs[count-1]); 496 total += size; 497 logObject(refs[count-1], size, identical, equiv); 498 499 LOGW("Memory held directly by native code is %d bytes\n", total); 500 free(tableCopy); 501 } 502