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 static void abortMaybe() {
  23     // If CheckJNI is on, it'll give a more detailed error before aborting.
  24     // Otherwise, we want to abort rather than hand back a bad reference.
  25     if (!gDvmJni.useCheckJni) {
  26         dvmAbort();
  27     }
  28 }
  29
  30 bool IndirectRefTable::init(size_t initialCount,
  31         size_t maxCount, IndirectRefKind desiredKind)
  32 {
  33     assert(initialCount > 0);
  34     assert(initialCount <= maxCount);
  35     assert(desiredKind != kIndirectKindInvalid);
  36
  37     table_ = (IndirectRefSlot*) malloc(initialCount * sizeof(IndirectRefSlot));
  38     if (table_ == NULL) {
  39         return false;
  40     }
  41     memset(table_, 0xd1, initialCount * sizeof(IndirectRefSlot));
  42
  43     segmentState.all = IRT_FIRST_SEGMENT;
  44     alloc_entries_ = initialCount;
  45     max_entries_ = maxCount;
  46     kind_ = desiredKind;
  47
  48     return true;
  49 }
  50
  51 /*
  52  * Clears out the contents of a IndirectRefTable, freeing allocated storage.
  53  */
  54 void IndirectRefTable::destroy()
  55 {
  56     free(table_);
  57     table_ = NULL;
  58     alloc_entries_ = max_entries_ = -1;
  59 }
  60
  61 IndirectRef IndirectRefTable::add(u4 cookie, Object* obj)
  62 {
  63     IRTSegmentState prevState;
  64     prevState.all = cookie;
  65     size_t topIndex = segmentState.parts.topIndex;
  66
  67     assert(obj != NULL);
  68     assert(dvmIsHeapAddress(obj));
  69     assert(table_ != NULL);
  70     assert(alloc_entries_ <= max_entries_);
  71     assert(segmentState.parts.numHoles >= prevState.parts.numHoles);
  72
  73     /*
  74      * We know there's enough room in the table.  Now we just need to find
  75      * the right spot.  If there's a hole, find it and fill it; otherwise,
  76      * add to the end of the list.
  77      */
  78     IndirectRef result;
  79     IndirectRefSlot* slot;
  80     int numHoles = segmentState.parts.numHoles - prevState.parts.numHoles;
  81     if (numHoles > 0) {
  82         assert(topIndex > 1);
  83         /* find the first hole; likely to be near the end of the list,
  84          * we know the item at the topIndex is not a hole */
  85         slot = &table_[topIndex - 1];
  86         assert(slot->obj != NULL);
  87         while ((--slot)->obj != NULL) {
  88             assert(slot >= table_ + prevState.parts.topIndex);
  89         }
  90         segmentState.parts.numHoles--;
  91     } else {
  92         /* add to the end, grow if needed */
  93         if (topIndex == alloc_entries_) {
  94             /* reached end of allocated space; did we hit buffer max? */
  95             if (topIndex == max_entries_) {
  96                 ALOGE("JNI ERROR (app bug): %s reference table overflow (max=%d)",
  97                         indirectRefKindToString(kind_), max_entries_);
  98                 return NULL;
  99             }
 100
 101             size_t newSize = alloc_entries_ * 2;
 102             if (newSize > max_entries_) {
 103                 newSize = max_entries_;
 104             }
 105             assert(newSize > alloc_entries_);
 106
 107             IndirectRefSlot* newTable =
 108                     (IndirectRefSlot*) realloc(table_, newSize * sizeof(IndirectRefSlot));
 109             if (table_ == NULL) {
 110                 ALOGE("JNI ERROR (app bug): unable to expand %s reference table "
 111                         "(from %d to %d, max=%d)",
 112                         indirectRefKindToString(kind_),
 113                         alloc_entries_, newSize, max_entries_);
 114                 return NULL;
 115             }
 116
 117             memset(newTable + alloc_entries_, 0xd1,
 118                    (newSize - alloc_entries_) * sizeof(IndirectRefSlot));
 119
 120             alloc_entries_ = newSize;
 121             table_ = newTable;
 122         }
 123         slot = &table_[topIndex++];
 124         segmentState.parts.topIndex = topIndex;
 125     }
 126
 127     slot->obj = obj;
 128     slot->serial = nextSerial(slot->serial);
 129     result = toIndirectRef(slot - table_, slot->serial, kind_);
 130
 131     assert(result != NULL);
 132     return result;
 133 }
 134
 135 /*
 136  * Get the referent of an indirect ref from the table.
 137  *
 138  * Returns kInvalidIndirectRefObject if iref is invalid.
 139  */
 140 Object* IndirectRefTable::get(IndirectRef iref) const {
 141     IndirectRefKind kind = indirectRefKind(iref);
 142     if (kind != kind_) {
 143         if (iref == NULL) {
 144             ALOGW("Attempt to look up NULL %s reference", indirectRefKindToString(kind_));
 145             return kInvalidIndirectRefObject;
 146         }
 147         if (kind == kIndirectKindInvalid) {
 148             ALOGE("JNI ERROR (app bug): invalid %s reference %p",
 149                     indirectRefKindToString(kind_), iref);
 150             abortMaybe();
 151             return kInvalidIndirectRefObject;
 152         }
 153         // References of the requested kind cannot appear within this table.
 154         return kInvalidIndirectRefObject;
 155     }
 156
 157     u4 topIndex = segmentState.parts.topIndex;
 158     u4 index = extractIndex(iref);
 159     if (index >= topIndex) {
 160         /* bad -- stale reference? */
 161         ALOGE("JNI ERROR (app bug): accessed stale %s reference %p (index %d in a table of size %d)",
 162                 indirectRefKindToString(kind_), iref, index, topIndex);
 163         abortMaybe();
 164         return kInvalidIndirectRefObject;
 165     }
 166
 167     Object* obj = table_[index].obj;
 168     if (obj == NULL) {
 169         ALOGI("JNI ERROR (app bug): accessed deleted %s reference %p",
 170                 indirectRefKindToString(kind_), iref);
 171         abortMaybe();
 172         return kInvalidIndirectRefObject;
 173     }
 174
 175     u4 serial = extractSerial(iref);
 176     if (serial != table_[index].serial) {
 177         ALOGE("JNI ERROR (app bug): attempt to use stale %s reference %p",
 178                 indirectRefKindToString(kind_), iref);
 179         abortMaybe();
 180         return kInvalidIndirectRefObject;
 181     }
 182
 183     return obj;
 184 }
 185
 186 static int findObject(const Object* obj, int bottomIndex, int topIndex,
 187         const IndirectRefSlot* table) {
 188     for (int i = bottomIndex; i < topIndex; ++i) {
 189         if (table[i].obj == obj) {
 190             return i;
 191         }
 192     }
 193     return -1;
 194 }
 195
 196 bool IndirectRefTable::contains(const Object* obj) const {
 197     return findObject(obj, 0, segmentState.parts.topIndex, table_) >= 0;
 198 }
 199
 200 /*
 201  * Remove "obj" from "pRef".  We extract the table offset bits from "iref"
 202  * and zap the corresponding entry, leaving a hole if it's not at the top.
 203  *
 204  * If the entry is not between the current top index and the bottom index
 205  * specified by the cookie, we don't remove anything.  This is the behavior
 206  * required by JNI's DeleteLocalRef function.
 207  *
 208  * Note this is NOT called when a local frame is popped.  This is only used
 209  * for explicit single removals.
 210  *
 211  * Returns "false" if nothing was removed.
 212  */
 213 bool IndirectRefTable::remove(u4 cookie, IndirectRef iref)
 214 {
 215     IRTSegmentState prevState;
 216     prevState.all = cookie;
 217     u4 topIndex = segmentState.parts.topIndex;
 218     u4 bottomIndex = prevState.parts.topIndex;
 219
 220     assert(table_ != NULL);
 221     assert(alloc_entries_ <= max_entries_);
 222     assert(segmentState.parts.numHoles >= prevState.parts.numHoles);
 223
 224     IndirectRefKind kind = indirectRefKind(iref);
 225     u4 index;
 226     if (kind == kind_) {
 227         index = extractIndex(iref);
 228         if (index < bottomIndex) {
 229             /* wrong segment */
 230             ALOGV("Attempt to remove index outside index area (%ud vs %ud-%ud)",
 231                     index, bottomIndex, topIndex);
 232             return false;
 233         }
 234         if (index >= topIndex) {
 235             /* bad -- stale reference? */
 236             ALOGD("Attempt to remove invalid index %ud (bottom=%ud top=%ud)",
 237                     index, bottomIndex, topIndex);
 238             return false;
 239         }
 240         if (table_[index].obj == NULL) {
 241             ALOGD("Attempt to remove cleared %s reference %p",
 242                     indirectRefKindToString(kind_), iref);
 243             return false;
 244         }
 245         u4 serial = extractSerial(iref);
 246         if (table_[index].serial != serial) {
 247             ALOGD("Attempt to remove stale %s reference %p",
 248                     indirectRefKindToString(kind_), iref);
 249             return false;
 250         }
 251     } else if (kind == kIndirectKindInvalid && gDvmJni.workAroundAppJniBugs) {
 252         // reference looks like a pointer, scan the table to find the index
 253         int i = findObject(reinterpret_cast<Object*>(iref), bottomIndex, topIndex, table_);
 254         if (i < 0) {
 255             ALOGW("trying to work around app JNI bugs, but didn't find %p in table!", iref);
 256             return false;
 257         }
 258         index = i;
 259     } else {
 260         // References of the requested kind cannot appear within this table.
 261         return false;
 262     }
 263
 264     if (index == topIndex - 1) {
 265         // Top-most entry.  Scan up and consume holes.
 266         int numHoles = segmentState.parts.numHoles - prevState.parts.numHoles;
 267         if (numHoles != 0) {
 268             while (--topIndex > bottomIndex && numHoles != 0) {
 269                 ALOGV("+++ checking for hole at %d (cookie=0x%08x) val=%p",
 270                     topIndex-1, cookie, table_[topIndex-1].obj);
 271                 if (table_[topIndex-1].obj != NULL) {
 272                     break;
 273                 }
 274                 ALOGV("+++ ate hole at %d", topIndex-1);
 275                 numHoles--;
 276             }
 277             segmentState.parts.numHoles = numHoles + prevState.parts.numHoles;
 278             segmentState.parts.topIndex = topIndex;
 279         } else {
 280             segmentState.parts.topIndex = topIndex-1;
 281             ALOGV("+++ ate last entry %d", topIndex-1);
 282         }
 283     } else {
 284         /*
 285          * Not the top-most entry.  This creates a hole.  We NULL out the
 286          * entry to prevent somebody from deleting it twice and screwing up
 287          * the hole count.
 288          */
 289         table_[index].obj = NULL;
 290         segmentState.parts.numHoles++;
 291         ALOGV("+++ left hole at %d, holes=%d", index, segmentState.parts.numHoles);
 292     }
 293
 294     return true;
 295 }
 296
 297 const char* indirectRefKindToString(IndirectRefKind kind)
 298 {
 299     switch (kind) {
 300     case kIndirectKindInvalid:      return "invalid";
 301     case kIndirectKindLocal:        return "local";
 302     case kIndirectKindGlobal:       return "global";
 303     case kIndirectKindWeakGlobal:   return "weak global";
 304     default:                        return "UNKNOWN";
 305     }
 306 }
 307
 308 void IndirectRefTable::dump(const char* descr) const
 309 {
 310     size_t count = capacity();
 311     Object** copy = new Object*[count];
 312     for (size_t i = 0; i < count; i++) {
 313         copy[i] = table_[i].obj;
 314     }
 315     dvmDumpReferenceTableContents(copy, count, descr);
 316     delete[] copy;
 317 }