vm/IndirectRefTable.c

   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 }