vm/IndirectRefTable.cpp

   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 != kIndirectKindInvalid);
  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     free(pRef->slotData);
  59     pRef->table = NULL;
  60     pRef->allocEntries = pRef->maxEntries = -1;
  61 }
  62
  63 /*
  64  * Remove one or more segments from the top.  The table entry identified
  65  * by "cookie" becomes the new top-most entry.
  66  *
  67  * Returns false if "cookie" is invalid or the table has only one segment.
  68  */
  69 bool dvmPopIndirectRefTableSegmentCheck(IndirectRefTable* pRef, u4 cookie)
  70 {
  71     IRTSegmentState sst;
  72
  73     /*
  74      * The new value for "top" must be <= the current value.  Otherwise
  75      * this would represent an expansion of the table.
  76      */
  77     sst.all = cookie;
  78     if (sst.parts.topIndex > pRef->segmentState.parts.topIndex) {
  79         LOGE("Attempt to expand table with segment pop (%d to %d)\n",
  80             pRef->segmentState.parts.topIndex, sst.parts.topIndex);
  81         return false;
  82     }
  83     if (sst.parts.numHoles >= sst.parts.topIndex) {
  84         LOGE("Absurd numHoles in cookie (%d bi=%d)\n",
  85             sst.parts.numHoles, sst.parts.topIndex);
  86         return false;
  87     }
  88
  89     LOGV("IRT %p[%d]: pop, top=%d holes=%d\n",
  90         pRef, pRef->kind, sst.parts.topIndex, sst.parts.numHoles);
  91
  92     return true;
  93 }
  94
  95 /*
  96  * Make sure that the entry at "idx" is correctly paired with "iref".
  97  */
  98 static bool checkEntry(IndirectRefTable* pRef, IndirectRef iref, int idx)
  99 {
 100     Object* obj = pRef->table[idx];
 101     IndirectRef checkRef = dvmObjectToIndirectRef(pRef, obj, idx, pRef->kind);
 102     if (checkRef != iref) {
 103         LOGW("IRT %p[%d]: iref mismatch (req=%p vs cur=%p)\n",
 104             pRef, pRef->kind, iref, checkRef);
 105         return false;
 106     }
 107     return true;
 108 }
 109
 110 /*
 111  * Update extended debug info when an entry is added.
 112  *
 113  * We advance the serial number, invalidating any outstanding references to
 114  * this slot.
 115  */
 116 static inline void updateSlotAdd(IndirectRefTable* pRef, Object* obj, int slot)
 117 {
 118     if (pRef->slotData != NULL) {
 119         IndirectRefSlot* pSlot = &pRef->slotData[slot];
 120         pSlot->serial++;
 121         //LOGI("+++ add [%d] slot %d (%p->%p), serial=%d\n",
 122         //    pRef->kind, slot, obj, iref, pSlot->serial);
 123         pSlot->previous[pSlot->serial % kIRTPrevCount] = obj;
 124     }
 125 }
 126
 127 /*
 128  * Update extended debug info when an entry is removed.
 129  */
 130 static inline void updateSlotRemove(IndirectRefTable* pRef, int slot)
 131 {
 132     if (pRef->slotData != NULL) {
 133         //IndirectRefSlot* pSlot = &pRef->slotData[slot];
 134         //LOGI("+++ remove [%d] slot %d, serial now %d\n",
 135         //    pRef->kind, slot, pSlot->serial);
 136     }
 137 }
 138
 139 /*
 140  * Add "obj" to "pRef".
 141  */
 142 IndirectRef dvmAddToIndirectRefTable(IndirectRefTable* pRef, u4 cookie,
 143     Object* obj)
 144 {
 145     IRTSegmentState prevState;
 146     prevState.all = cookie;
 147     int topIndex = pRef->segmentState.parts.topIndex;
 148
 149     assert(obj != NULL);
 150     assert(dvmIsValidObject(obj));
 151     assert(pRef->table != NULL);
 152     assert(pRef->allocEntries <= pRef->maxEntries);
 153     assert(pRef->segmentState.parts.numHoles >= prevState.parts.numHoles);
 154
 155     if (topIndex == pRef->allocEntries) {
 156         /* reached end of allocated space; did we hit buffer max? */
 157         if (topIndex == pRef->maxEntries) {
 158             LOGW("IndirectRefTable overflow (max=%d)\n", pRef->maxEntries);
 159             return NULL;
 160         }
 161
 162         Object** newTable;
 163         int newSize;
 164
 165         newSize = pRef->allocEntries * 2;
 166         if (newSize > pRef->maxEntries)
 167             newSize = pRef->maxEntries;
 168         assert(newSize > pRef->allocEntries);
 169
 170         newTable = (Object**) realloc(pRef->table, newSize * sizeof(Object*));
 171         if (newTable == NULL) {
 172             LOGE("Unable to expand iref table (from %d to %d, max=%d)\n",
 173                 pRef->allocEntries, newSize, pRef->maxEntries);
 174             return false;
 175         }
 176         LOGV("Growing ireftab %p from %d to %d (max=%d)\n",
 177             pRef, pRef->allocEntries, newSize, pRef->maxEntries);
 178
 179         /* update entries; adjust "nextEntry" in case memory moved */
 180         pRef->table = newTable;
 181         pRef->allocEntries = newSize;
 182     }
 183
 184     IndirectRef result;
 185
 186     /*
 187      * We know there's enough room in the table.  Now we just need to find
 188      * the right spot.  If there's a hole, find it and fill it; otherwise,
 189      * add to the end of the list.
 190      */
 191     int numHoles = pRef->segmentState.parts.numHoles - prevState.parts.numHoles;
 192     if (numHoles > 0) {
 193         assert(topIndex > 1);
 194         /* find the first hole; likely to be near the end of the list */
 195         Object** pScan = &pRef->table[topIndex - 1];
 196         assert(*pScan != NULL);
 197         while (*--pScan != NULL) {
 198             assert(pScan >= pRef->table + prevState.parts.topIndex);
 199         }
 200         updateSlotAdd(pRef, obj, pScan - pRef->table);
 201         result = dvmObjectToIndirectRef(pRef, obj, pScan - pRef->table,
 202             pRef->kind);
 203         *pScan = obj;
 204         pRef->segmentState.parts.numHoles--;
 205     } else {
 206         /* add to the end */
 207         updateSlotAdd(pRef, obj, topIndex);
 208         result = dvmObjectToIndirectRef(pRef, obj, topIndex, pRef->kind);
 209         pRef->table[topIndex++] = obj;
 210         pRef->segmentState.parts.topIndex = topIndex;
 211     }
 212
 213     assert(result != NULL);
 214     return result;
 215 }
 216
 217 /*
 218  * Verify that the indirect table lookup is valid.
 219  *
 220  * Returns "false" if something looks bad.
 221  */
 222 bool dvmGetFromIndirectRefTableCheck(IndirectRefTable* pRef, IndirectRef iref)
 223 {
 224     if (dvmGetIndirectRefType(iref) == kIndirectKindInvalid) {
 225         LOGW("Invalid indirect reference 0x%08x\n", (u4) iref);
 226         return false;
 227     }
 228
 229     int topIndex = pRef->segmentState.parts.topIndex;
 230     int idx = dvmIndirectRefToIndex(iref);
 231
 232     if (iref == NULL) {
 233         LOGD("Attempt to look up NULL iref\n");
 234         return false;
 235     }
 236     if (idx >= topIndex) {
 237         /* bad -- stale reference? */
 238         LOGD("Attempt to access invalid index %d (top=%d)\n",
 239             idx, topIndex);
 240         return false;
 241     }
 242
 243     Object* obj = pRef->table[idx];
 244     if (obj == NULL) {
 245         LOGD("Attempt to read from hole, iref=%p\n", iref);
 246         return false;
 247     }
 248     if (!checkEntry(pRef, iref, idx))
 249         return false;
 250
 251     return true;
 252 }
 253
 254 /*
 255  * Remove "obj" from "pRef".  We extract the table offset bits from "iref"
 256  * and zap the corresponding entry, leaving a hole if it's not at the top.
 257  *
 258  * If the entry is not between the current top index and the bottom index
 259  * specified by the cookie, we don't remove anything.  This is the behavior
 260  * required by JNI's DeleteLocalRef function.
 261  *
 262  * Note this is NOT called when a local frame is popped.  This is only used
 263  * for explict single removals.
 264  *
 265  * Returns "false" if nothing was removed.
 266  */
 267 bool dvmRemoveFromIndirectRefTable(IndirectRefTable* pRef, u4 cookie,
 268     IndirectRef iref)
 269 {
 270     IRTSegmentState prevState;
 271     prevState.all = cookie;
 272     int topIndex = pRef->segmentState.parts.topIndex;
 273     int bottomIndex = prevState.parts.topIndex;
 274
 275     assert(pRef->table != NULL);
 276     assert(pRef->allocEntries <= pRef->maxEntries);
 277     assert(pRef->segmentState.parts.numHoles >= prevState.parts.numHoles);
 278
 279     int idx = dvmIndirectRefToIndex(iref);
 280     if (idx < bottomIndex) {
 281         /* wrong segment */
 282         LOGV("Attempt to remove index outside index area (%d vs %d-%d)\n",
 283             idx, bottomIndex, topIndex);
 284         return false;
 285     }
 286     if (idx >= topIndex) {
 287         /* bad -- stale reference? */
 288         LOGD("Attempt to remove invalid index %d (bottom=%d top=%d)\n",
 289             idx, bottomIndex, topIndex);
 290         return false;
 291     }
 292
 293     if (idx == topIndex-1) {
 294         /*
 295          * Top-most entry.  Scan up and consume holes.  No need to NULL
 296          * out the entry, since the test vs. topIndex will catch it.
 297          */
 298         if (!checkEntry(pRef, iref, idx))
 299             return false;
 300         updateSlotRemove(pRef, idx);
 301
 302 #ifndef NDEBUG
 303         pRef->table[idx] = (Object*)0xd3d3d3d3;
 304 #endif
 305
 306         int numHoles =
 307             pRef->segmentState.parts.numHoles - prevState.parts.numHoles;
 308         if (numHoles != 0) {
 309             while (--topIndex > bottomIndex && numHoles != 0) {
 310                 LOGV("+++ checking for hole at %d (cookie=0x%08x) val=%p\n",
 311                     topIndex-1, cookie, pRef->table[topIndex-1]);
 312                 if (pRef->table[topIndex-1] != NULL)
 313                     break;
 314                 LOGV("+++ ate hole at %d\n", topIndex-1);
 315                 numHoles--;
 316             }
 317             pRef->segmentState.parts.numHoles =
 318                 numHoles + prevState.parts.numHoles;
 319             pRef->segmentState.parts.topIndex = topIndex;
 320         } else {
 321             pRef->segmentState.parts.topIndex = topIndex-1;
 322             LOGV("+++ ate last entry %d\n", topIndex-1);
 323         }
 324     } else {
 325         /*
 326          * Not the top-most entry.  This creates a hole.  We NULL out the
 327          * entry to prevent somebody from deleting it twice and screwing up
 328          * the hole count.
 329          */
 330         if (pRef->table[idx] == NULL) {
 331             LOGV("--- WEIRD: removing null entry %d\n", idx);
 332             return false;
 333         }
 334         if (!checkEntry(pRef, iref, idx))
 335             return false;
 336         updateSlotRemove(pRef, idx);
 337
 338         pRef->table[idx] = NULL;
 339         pRef->segmentState.parts.numHoles++;
 340         LOGV("+++ left hole at %d, holes=%d\n",
 341             idx, pRef->segmentState.parts.numHoles);
 342     }
 343
 344     return true;
 345 }
 346
 347 /*
 348  * Return a type name, useful for debugging.
 349  */
 350 const char* dvmIndirectRefTypeName(IndirectRef iref)
 351 {
 352     switch (dvmGetIndirectRefType(iref)) {
 353     case kIndirectKindInvalid:      return "invalid";
 354     case kIndirectKindLocal:        return "local";
 355     case kIndirectKindGlobal:       return "global";
 356     case kIndirectKindWeakGlobal:   return "weak global";
 357     default:                        return "UNKNOWN";
 358     }
 359 }
 360
 361 /*
 362  * Dump the contents of a IndirectRefTable to the log.
 363  */
 364 void dvmDumpIndirectRefTable(const IndirectRefTable* pRef, const char* descr)
 365 {
 366     dvmDumpReferenceTableContents(pRef->table, dvmIndirectRefTableEntries(pRef),
 367         descr);
 368 }