IndirectRefTable.h revision 259a8a5154c63a793ea0ee438d146acda7d990b6
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 reinterpret_cast<Object*>(0xdead4321) 90 91#define kClearedJniWeakGlobal reinterpret_cast<Object*>(0xdead1234) 92 93/* 94 * Indirect reference kind, used as the two low bits of IndirectRef. 95 * 96 * For convenience these match up with enum jobjectRefType from jni.h. 97 */ 98enum IndirectRefKind { 99 kIndirectKindInvalid = 0, 100 kIndirectKindLocal = 1, 101 kIndirectKindGlobal = 2, 102 kIndirectKindWeakGlobal = 3 103}; 104const char* indirectRefKindToString(IndirectRefKind kind); 105 106/* 107 * Determine what kind of indirect reference this is. 108 */ 109INLINE IndirectRefKind indirectRefKind(IndirectRef iref) 110{ 111 return (IndirectRefKind)((u4) iref & 0x03); 112} 113 114/* 115 * Extended debugging structure. We keep a parallel array of these, one 116 * per slot in the table. 117 */ 118#define kIRTPrevCount 4 119struct IndirectRefSlot { 120 u4 serial; /* slot serial */ 121 Object* previous[kIRTPrevCount]; 122}; 123 124/* use as initial value for "cookie", and when table has only one segment */ 125#define IRT_FIRST_SEGMENT 0 126 127/* 128 * Table definition. 129 * 130 * For the global reference table, the expected common operations are 131 * adding a new entry and removing a recently-added entry (usually the 132 * most-recently-added entry). For JNI local references, the common 133 * operations are adding a new entry and removing an entire table segment. 134 * 135 * If "allocEntries" is not equal to "maxEntries", the table may expand 136 * when entries are added, which means the memory may move. If you want 137 * to keep pointers into "table" rather than offsets, you must use a 138 * fixed-size table. 139 * 140 * If we delete entries from the middle of the list, we will be left with 141 * "holes". We track the number of holes so that, when adding new elements, 142 * we can quickly decide to do a trivial append or go slot-hunting. 143 * 144 * When the top-most entry is removed, any holes immediately below it are 145 * also removed. Thus, deletion of an entry may reduce "topIndex" by more 146 * than one. 147 * 148 * To get the desired behavior for JNI locals, we need to know the bottom 149 * and top of the current "segment". The top is managed internally, and 150 * the bottom is passed in as a function argument (the VM keeps it in a 151 * slot in the interpreted stack frame). When we call a native method or 152 * push a local frame, the current top index gets pushed on, and serves 153 * as the new bottom. When we pop a frame off, the value from the stack 154 * becomes the new top index, and the value stored in the previous frame 155 * becomes the new bottom. 156 * 157 * To avoid having to re-scan the table after a pop, we want to push the 158 * number of holes in the table onto the stack. Because of our 64K-entry 159 * cap, we can combine the two into a single unsigned 32-bit value. 160 * Instead of a "bottom" argument we take a "cookie", which includes the 161 * bottom index and the count of holes below the bottom. 162 * 163 * We need to minimize method call/return overhead. If we store the 164 * "cookie" externally, on the interpreted call stack, the VM can handle 165 * pushes and pops with a single 4-byte load and store. (We could also 166 * store it internally in a public structure, but the local JNI refs are 167 * logically tied to interpreted stack frames anyway.) 168 * 169 * Common alternative implementation: make IndirectRef a pointer to the 170 * actual reference slot. Instead of getting a table and doing a lookup, 171 * the lookup can be done instantly. Operations like determining the 172 * type and deleting the reference are more expensive because the table 173 * must be hunted for (i.e. you have to do a pointer comparison to see 174 * which table it's in), you can't move the table when expanding it (so 175 * realloc() is out), and tricks like serial number checking to detect 176 * stale references aren't possible (though we may be able to get similar 177 * benefits with other approaches). 178 * 179 * TODO: consider a "lastDeleteIndex" for quick hole-filling when an 180 * add immediately follows a delete; must invalidate after segment pop 181 * (which could increase the cost/complexity of method call/return). 182 * Might be worth only using it for JNI globals. 183 * 184 * TODO: may want completely different add/remove algorithms for global 185 * and local refs to improve performance. A large circular buffer might 186 * reduce the amortized cost of adding global references. 187 * 188 * TODO: if we can guarantee that the underlying storage doesn't move, 189 * e.g. by using oversized mmap regions to handle expanding tables, we may 190 * be able to avoid having to synchronize lookups. Might make sense to 191 * add a "synchronized lookup" call that takes the mutex as an argument, 192 * and either locks or doesn't lock based on internal details. 193 */ 194union IRTSegmentState { 195 u4 all; 196 struct { 197 u4 topIndex:16; /* index of first unused entry */ 198 u4 numHoles:16; /* #of holes in entire table */ 199 } parts; 200}; 201 202class iref_iterator { 203public: 204 explicit iref_iterator(Object** table, size_t i, size_t capacity) 205 : table_(table), i_(i), capacity_(capacity) 206 { 207 skipNullsAndTombstones(); 208 } 209 210 iref_iterator& operator++() { 211 ++i_; 212 skipNullsAndTombstones(); 213 return *this; 214 } 215 216 Object** operator*() { 217 return &table_[i_]; 218 } 219 220 bool equals(const iref_iterator& rhs) const { 221 return (i_ == rhs.i_ && table_ == rhs.table_); 222 } 223 224 size_t to_i() const { return i_; } 225 226private: 227 void skipNullsAndTombstones() { 228 // We skip NULLs and tombstones. Clients don't want to see implementation details. 229 while (i_ < capacity_ && (table_[i_] == NULL || table_[i_] == kClearedJniWeakGlobal)) { 230 ++i_; 231 } 232 } 233 234 Object** table_; 235 size_t i_; 236 size_t capacity_; 237}; 238 239bool inline operator!=(const iref_iterator& lhs, const iref_iterator& rhs) { 240 return !lhs.equals(rhs); 241} 242 243struct IndirectRefTable { 244public: 245 typedef iref_iterator iterator; 246 247 /* semi-public - read/write by interpreter in native call handler */ 248 IRTSegmentState segmentState; 249 250 /* 251 * private: 252 * 253 * TODO: we can't make these private as long as the interpreter 254 * uses offsetof, since private member data makes us non-POD. 255 */ 256 Object** table; /* bottom of the stack */ 257 IndirectRefKind kind; /* bit mask, ORed into all irefs */ 258 IndirectRefSlot* slotData; /* extended debugging info */ 259 size_t allocEntries; /* #of entries we have space for */ 260 size_t maxEntries; /* max #of entries allowed */ 261 262 // TODO: want hole-filling stats (#of holes filled, total entries scanned) 263 // for performance evaluation. 264 265 /* 266 * Add a new entry. "obj" must be a valid non-NULL object reference 267 * (though it's okay if it's not fully-formed, e.g. the result from 268 * dvmMalloc doesn't have obj->clazz set). 269 * 270 * Returns NULL if the table is full (max entries reached, or alloc 271 * failed during expansion). 272 */ 273 IndirectRef add(u4 cookie, Object* obj); 274 275 /* 276 * Given an IndirectRef in the table, return the Object it refers to. 277 * 278 * Returns kInvalidIndirectRefObject if iref is invalid. 279 */ 280 Object* get(IndirectRef iref) const { 281 if (!getChecked(iref)) { 282 return kInvalidIndirectRefObject; 283 } 284 return table[extractIndex(iref)]; 285 } 286 287 // TODO: only used for workAroundAppJniBugs support. 288 bool contains(IndirectRef iref) const; 289 290 /* 291 * Remove an existing entry. 292 * 293 * If the entry is not between the current top index and the bottom index 294 * specified by the cookie, we don't remove anything. This is the behavior 295 * required by JNI's DeleteLocalRef function. 296 * 297 * Returns "false" if nothing was removed. 298 */ 299 bool remove(u4 cookie, IndirectRef iref); 300 301 /* 302 * Initialize an IndirectRefTable. 303 * 304 * If "initialCount" != "maxCount", the table will expand as required. 305 * 306 * "kind" should be Local or Global. The Global table may also hold 307 * WeakGlobal refs. 308 * 309 * Returns "false" if table allocation fails. 310 */ 311 bool init(size_t initialCount, size_t maxCount, IndirectRefKind kind); 312 313 /* 314 * Clear out the contents, freeing allocated storage. 315 * 316 * You must call dvmInitReferenceTable() before you can re-use this table. 317 * 318 * TODO: this should be a destructor. 319 */ 320 void destroy(); 321 322 /* 323 * Dump the contents of a reference table to the log file. 324 * 325 * The caller should lock any external sync before calling. 326 * 327 * TODO: we should name the table in a constructor and remove 328 * the argument here. 329 */ 330 void dump(const char* descr) const; 331 332 /* 333 * Return the #of entries in the entire table. This includes holes, and 334 * so may be larger than the actual number of "live" entries. 335 */ 336 size_t capacity() const { 337 return segmentState.parts.topIndex; 338 } 339 340 iterator begin() { 341 return iterator(table, 0, capacity()); 342 } 343 344 iterator end() { 345 return iterator(table, capacity(), capacity()); 346 } 347 348private: 349 /* 350 * Extract the table index from an indirect reference. 351 */ 352 static u4 extractIndex(IndirectRef iref) { 353 u4 uref = (u4) iref; 354 return (uref >> 2) & 0xffff; 355 } 356 357 /* 358 * The object pointer itself is subject to relocation in some GC 359 * implementations, so we shouldn't really be using it here. 360 */ 361 IndirectRef toIndirectRef(Object* obj, u4 tableIndex) const { 362 assert(tableIndex < 65536); 363 //u4 objChunk = (((u4) obj >> 3) ^ ((u4) obj >> 19)) & 0x3fff; 364 //u4 uref = objChunk << 18 | (tableIndex << 2) | kind; 365 u4 serialChunk = slotData[tableIndex].serial; 366 u4 uref = serialChunk << 20 | (tableIndex << 2) | kind; 367 return (IndirectRef) uref; 368 } 369 370 /* 371 * Update extended debug info when an entry is added. 372 * 373 * We advance the serial number, invalidating any outstanding references to 374 * this slot. 375 */ 376 void updateSlotAdd(Object* obj, int slot) { 377 if (slotData != NULL) { 378 IndirectRefSlot* pSlot = &slotData[slot]; 379 pSlot->serial++; 380 pSlot->previous[pSlot->serial % kIRTPrevCount] = obj; 381 } 382 } 383 384 /* extra debugging checks */ 385 bool getChecked(IndirectRef) const; 386 bool checkEntry(const char*, IndirectRef, int) const; 387}; 388 389#endif // DALVIK_INDIRECTREFTABLE_H_ 390