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 #ifndef _DALVIK_INDIRECTREFTABLE 18 #define _DALVIK_INDIRECTREFTABLE 19 /* 20 * Maintain a table of indirect references. Used for local/global JNI 21 * references. 22 * 23 * The table contains object references that are part of the GC root set. 24 * When an object is added we return an IndirectRef that is not a valid 25 * pointer but can be used to find the original value in O(1) time. 26 * Conversions to and from indirect refs are performed on JNI method calls 27 * in and out of the VM, so they need to be very fast. 28 * 29 * To be efficient for JNI local variable storage, we need to provide 30 * operations that allow us to operate on segments of the table, where 31 * segments are pushed and popped as if on a stack. For example, deletion 32 * of an entry should only succeed if it appears in the current segment, 33 * and we want to be able to strip off the current segment quickly when 34 * a method returns. Additions to the table must be made in the current 35 * segment even if space is available in an earlier area. 36 * 37 * A new segment is created when we call into native code from interpreted 38 * code, or when we handle the JNI PushLocalFrame function. 39 * 40 * The GC must be able to scan the entire table quickly. 41 * 42 * In summary, these must be very fast: 43 * - adding or removing a segment 44 * - adding references to a new segment 45 * - converting an indirect reference back to an Object 46 * These can be a little slower, but must still be pretty quick: 47 * - adding references to a "mature" segment 48 * - removing individual references 49 * - scanning the entire table straight through 50 * 51 * If there's more than one segment, we don't guarantee that the table 52 * will fill completely before we fail due to lack of space. We do ensure 53 * that the current segment will pack tightly, which should satisfy JNI 54 * requirements (e.g. EnsureLocalCapacity). 55 * 56 * To make everything fit nicely in 32-bit integers, the maximum size of 57 * the table is capped at 64K. 58 * 59 * None of the table functions are synchronized. 60 */ 61 62 /* 63 * Indirect reference definition. This must be interchangeable with JNI's 64 * jobject, and it's convenient to let null be null, so we use void*. 65 * 66 * We need a 16-bit table index and a 2-bit reference type (global, local, 67 * weak global). Real object pointers will have zeroes in the low 2 or 3 68 * bits (4- or 8-byte alignment), so it's useful to put the ref type 69 * in the low bits and reserve zero as an invalid value. 70 * 71 * The remaining 14 bits can be used to detect stale indirect references. 72 * For example, if objects don't move, we can use a hash of the original 73 * Object* to make sure the entry hasn't been re-used. (If the Object* 74 * we find there doesn't match because of heap movement, we could do a 75 * secondary check on the preserved hash value; this implies that creating 76 * a global/local ref queries the hash value and forces it to be saved.) 77 * This is only done when CheckJNI is enabled. 78 * 79 * A more rigorous approach would be to put a serial number in the extra 80 * bits, and keep a copy of the serial number in a parallel table. This is 81 * easier when objects can move, but requires 2x the memory and additional 82 * memory accesses on add/get. It will catch additional problems, e.g.: 83 * create iref1 for obj, delete iref1, create iref2 for same obj, lookup 84 * iref1. A pattern based on object bits will miss this. 85 */ 86 typedef void* IndirectRef; 87 88 /* 89 * Indirect reference kind, used as the two low bits of IndirectRef. 90 * 91 * For convenience these match up with enum jobjectRefType from jni.h. 92 */ 93 typedef enum IndirectRefKind { 94 kIndirectKindInvalid = 0, 95 kIndirectKindLocal = 1, 96 kIndirectKindGlobal = 2, 97 kIndirectKindWeakGlobal = 3 98 } IndirectRefKind; 99 100 /* 101 * Extended debugging structure. We keep a parallel array of these, one 102 * per slot in the table. 103 */ 104 #define kIRTPrevCount 4 105 typedef struct IndirectRefSlot { 106 u4 serial; /* slot serial */ 107 Object* previous[kIRTPrevCount]; 108 } IndirectRefSlot; 109 110 /* 111 * Table definition. 112 * 113 * For the global reference table, the expected common operations are 114 * adding a new entry and removing a recently-added entry (usually the 115 * most-recently-added entry). For JNI local references, the common 116 * operations are adding a new entry and removing an entire table segment. 117 * 118 * If "allocEntries" is not equal to "maxEntries", the table may expand 119 * when entries are added, which means the memory may move. If you want 120 * to keep pointers into "table" rather than offsets, you must use a 121 * fixed-size table. 122 * 123 * If we delete entries from the middle of the list, we will be left with 124 * "holes". We track the number of holes so that, when adding new elements, 125 * we can quickly decide to do a trivial append or go slot-hunting. 126 * 127 * When the top-most entry is removed, any holes immediately below it are 128 * also removed. Thus, deletion of an entry may reduce "topIndex" by more 129 * than one. 130 * 131 * To get the desired behavior for JNI locals, we need to know the bottom 132 * and top of the current "segment". The top is managed internally, and 133 * the bottom is passed in as a function argument (the VM keeps it in a 134 * slot in the interpreted stack frame). When we call a native method or 135 * push a local frame, the current top index gets pushed on, and serves 136 * as the new bottom. When we pop a frame off, the value from the stack 137 * becomes the new top index, and the value stored in the previous frame 138 * becomes the new bottom. 139 * 140 * To avoid having to re-scan the table after a pop, we want to push the 141 * number of holes in the table onto the stack. Because of our 64K-entry 142 * cap, we can combine the two into a single unsigned 32-bit value. 143 * Instead of a "bottom" argument we take a "cookie", which includes the 144 * bottom index and the count of holes below the bottom. 145 * 146 * We need to minimize method call/return overhead. If we store the 147 * "cookie" externally, on the interpreted call stack, the VM can handle 148 * pushes and pops with a single 4-byte load and store. (We could also 149 * store it internally in a public structure, but the local JNI refs are 150 * logically tied to interpreted stack frames anyway.) 151 * 152 * Common alternative implementation: make IndirectRef a pointer to the 153 * actual reference slot. Instead of getting a table and doing a lookup, 154 * the lookup can be done instantly. Operations like determining the 155 * type and deleting the reference are more expensive because the table 156 * must be hunted for (i.e. you have to do a pointer comparison to see 157 * which table it's in), you can't move the table when expanding it (so 158 * realloc() is out), and tricks like serial number checking to detect 159 * stale references aren't possible (though we may be able to get similar 160 * benefits with other approaches). 161 * 162 * TODO: consider a "lastDeleteIndex" for quick hole-filling when an 163 * add immediately follows a delete; must invalidate after segment pop 164 * (which could increase the cost/complexity of method call/return). 165 * Might be worth only using it for JNI globals. 166 * 167 * TODO: may want completely different add/remove algorithms for global 168 * and local refs to improve performance. A large circular buffer might 169 * reduce the amortized cost of adding global references. 170 * 171 * TODO: if we can guarantee that the underlying storage doesn't move, 172 * e.g. by using oversized mmap regions to handle expanding tables, we may 173 * be able to avoid having to synchronize lookups. Might make sense to 174 * add a "synchronized lookup" call that takes the mutex as an argument, 175 * and either locks or doesn't lock based on internal details. 176 */ 177 typedef union IRTSegmentState { 178 u4 all; 179 struct { 180 u4 topIndex:16; /* index of first unused entry */ 181 u4 numHoles:16; /* #of holes in entire table */ 182 } parts; 183 } IRTSegmentState; 184 typedef struct IndirectRefTable { 185 /* semi-public - read/write by interpreter in native call handler */ 186 IRTSegmentState segmentState; 187 188 /* semi-public - read-only during GC scan; pointer must not be kept */ 189 Object** table; /* bottom of the stack */ 190 191 /* private */ 192 IndirectRefSlot* slotData; /* extended debugging info */ 193 int allocEntries; /* #of entries we have space for */ 194 int maxEntries; /* max #of entries allowed */ 195 IndirectRefKind kind; /* bit mask, ORed into all irefs */ 196 197 // TODO: want hole-filling stats (#of holes filled, total entries scanned) 198 // for performance evaluation. 199 } IndirectRefTable; 200 201 /* use as initial value for "cookie", and when table has only one segment */ 202 #define IRT_FIRST_SEGMENT 0 203 204 /* 205 * (This is PRIVATE, but we want it inside other inlines in this header.) 206 * 207 * Indirectify the object. 208 * 209 * The object pointer itself is subject to relocation in some GC 210 * implementations, so we shouldn't really be using it here. 211 */ 212 INLINE IndirectRef dvmObjectToIndirectRef(IndirectRefTable* pRef, 213 Object* obj, u4 tableIndex, IndirectRefKind kind) 214 { 215 assert(tableIndex < 65536); 216 //u4 objChunk = (((u4) obj >> 3) ^ ((u4) obj >> 19)) & 0x3fff; 217 //u4 uref = objChunk << 18 | (tableIndex << 2) | kind; 218 u4 serialChunk = pRef->slotData[tableIndex].serial; 219 u4 uref = serialChunk << 20 | (tableIndex << 2) | kind; 220 return (IndirectRef) uref; 221 } 222 223 /* 224 * (This is PRIVATE, but we want it inside other inlines in this header.) 225 * 226 * Extract the table index from an indirect reference. 227 */ 228 INLINE u4 dvmIndirectRefToIndex(IndirectRef iref) 229 { 230 u4 uref = (u4) iref; 231 return (uref >> 2) & 0xffff; 232 } 233 234 /* 235 * Determine what kind of indirect reference this is. 236 */ 237 INLINE IndirectRefKind dvmGetIndirectRefType(IndirectRef iref) 238 { 239 return (u4) iref & 0x03; 240 } 241 242 /* 243 * Initialize an IndirectRefTable. 244 * 245 * If "initialCount" != "maxCount", the table will expand as required. 246 * 247 * "kind" should be Local or Global. The Global table may also hold 248 * WeakGlobal refs. 249 * 250 * Returns "false" if table allocation fails. 251 */ 252 bool dvmInitIndirectRefTable(IndirectRefTable* pRef, int initialCount, 253 int maxCount, IndirectRefKind kind); 254 255 /* 256 * Clear out the contents, freeing allocated storage. Does not free "pRef". 257 * 258 * You must call dvmInitReferenceTable() before you can re-use this table. 259 */ 260 void dvmClearIndirectRefTable(IndirectRefTable* pRef); 261 262 /* 263 * Start a new segment at the top of the table. 264 * 265 * Returns an opaque 32-bit value that must be provided when the segment 266 * is to be removed. 267 * 268 * IMPORTANT: this is implemented as a single instruction in mterp, rather 269 * than a call here. You can add debugging aids for the C-language 270 * interpreters, but the basic implementation may not change. 271 */ 272 INLINE u4 dvmPushIndirectRefTableSegment(IndirectRefTable* pRef) 273 { 274 return pRef->segmentState.all; 275 } 276 277 /* extra debugging checks */ 278 bool dvmPopIndirectRefTableSegmentCheck(IndirectRefTable* pRef, u4 cookie); 279 280 /* 281 * Remove one or more segments from the top. The table entry identified 282 * by "cookie" becomes the new top-most entry. 283 * 284 * IMPORTANT: this is implemented as a single instruction in mterp, rather 285 * than a call here. You can add debugging aids for the C-language 286 * interpreters, but the basic implementation must not change. 287 */ 288 INLINE void dvmPopIndirectRefTableSegment(IndirectRefTable* pRef, u4 cookie) 289 { 290 dvmPopIndirectRefTableSegmentCheck(pRef, cookie); 291 pRef->segmentState.all = cookie; 292 } 293 294 /* 295 * Return the #of entries in the entire table. This includes holes, and 296 * so may be larger than the actual number of "live" entries. 297 */ 298 INLINE size_t dvmIndirectRefTableEntries(const IndirectRefTable* pRef) 299 { 300 return pRef->segmentState.parts.topIndex; 301 } 302 303 /* 304 * Returns "true" if the table is full. The table is considered full if 305 * we would need to expand it to add another entry to the current segment. 306 */ 307 INLINE size_t dvmIsIndirectRefTableFull(const IndirectRefTable* pRef) 308 { 309 return dvmIndirectRefTableEntries(pRef) == (size_t)pRef->allocEntries; 310 } 311 312 /* 313 * Add a new entry. "obj" must be a valid non-NULL object reference 314 * (though it's okay if it's not fully-formed, e.g. the result from 315 * dvmMalloc doesn't have obj->clazz set). 316 * 317 * Returns NULL if the table is full (max entries reached, or alloc 318 * failed during expansion). 319 */ 320 IndirectRef dvmAddToIndirectRefTable(IndirectRefTable* pRef, u4 cookie, 321 Object* obj); 322 323 /* 324 * Add a new entry at the end. Similar to Add but does not usually attempt 325 * to fill in holes. This is only appropriate to use right after a new 326 * segment has been pushed. 327 * 328 * (This is intended for use when calling into a native JNI method, so 329 * performance is critical.) 330 */ 331 INLINE IndirectRef dvmAppendToIndirectRefTable(IndirectRefTable* pRef, 332 u4 cookie, Object* obj) 333 { 334 int topIndex = pRef->segmentState.parts.topIndex; 335 if (topIndex == pRef->allocEntries) { 336 /* up against alloc or max limit, call the fancy version */ 337 return dvmAddToIndirectRefTable(pRef, cookie, obj); 338 } else { 339 IndirectRef result = dvmObjectToIndirectRef(pRef, obj, topIndex, 340 pRef->kind); 341 pRef->table[topIndex++] = obj; 342 pRef->segmentState.parts.topIndex = topIndex; 343 return result; 344 } 345 } 346 347 /* extra debugging checks */ 348 bool dvmGetFromIndirectRefTableCheck(IndirectRefTable* pRef, IndirectRef iref); 349 350 /* 351 * Given an IndirectRef in the table, return the Object it refers to. 352 * 353 * Returns NULL if iref is invalid. 354 */ 355 INLINE Object* dvmGetFromIndirectRefTable(IndirectRefTable* pRef, 356 IndirectRef iref) 357 { 358 if (!dvmGetFromIndirectRefTableCheck(pRef, iref)) 359 return NULL; 360 361 int idx = dvmIndirectRefToIndex(iref); 362 return pRef->table[idx]; 363 } 364 365 /* 366 * Remove an existing entry. 367 * 368 * If the entry is not between the current top index and the bottom index 369 * specified by the cookie, we don't remove anything. This is the behavior 370 * required by JNI's DeleteLocalRef function. 371 * 372 * Returns "false" if nothing was removed. 373 */ 374 bool dvmRemoveFromIndirectRefTable(IndirectRefTable* pRef, u4 cookie, 375 IndirectRef iref); 376 377 /* 378 * Dump the contents of a reference table to the log file. 379 */ 380 void dvmDumpIndirectRefTable(const IndirectRefTable* pRef, const char* descr); 381 382 #endif /*_DALVIK_INDIRECTREFTABLE*/ 383