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