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