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