vm/IndirectRefTable.h

   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  * Table definition.
 102  *
 103  * For the global reference table, the expected common operations are
 104  * adding a new entry and removing a recently-added entry (usually the
 105  * most-recently-added entry).  For JNI local references, the common
 106  * operations are adding a new entry and removing an entire table segment.
 107  *
 108  * If "allocEntries" is not equal to "maxEntries", the table may expand
 109  * when entries are added, which means the memory may move.  If you want
 110  * to keep pointers into "table" rather than offsets, you must use a
 111  * fixed-size table.
 112  *
 113  * If we delete entries from the middle of the list, we will be left with
 114  * "holes".  We track the number of holes so that, when adding new elements,
 115  * we can quickly decide to do a trivial append or go slot-hunting.
 116  *
 117  * When the top-most entry is removed, any holes immediately below it are
 118  * also removed.  Thus, deletion of an entry may reduce "topIndex" by more
 119  * than one.
 120  *
 121  * To get the desired behavior for JNI locals, we need to know the bottom
 122  * and top of the current "segment".  The top is managed internally, and
 123  * the bottom is passed in as a function argument (the VM keeps it in a
 124  * slot in the interpreted stack frame).  When we call a native method or
 125  * push a local frame, the current top index gets pushed on, and serves
 126  * as the new bottom.  When we pop a frame off, the value from the stack
 127  * becomes the new top index, and the value stored in the previous frame
 128  * becomes the new bottom.
 129  *
 130  * To avoid having to re-scan the table after a pop, we want to push the
 131  * number of holes in the table onto the stack.  Because of our 64K-entry
 132  * cap, we can combine the two into a single unsigned 32-bit value.
 133  * Instead of a "bottom" argument we take a "cookie", which includes the
 134  * bottom index and the count of holes below the bottom.
 135  *
 136  * We need to minimize method call/return overhead.  If we store the
 137  * "cookie" externally, on the interpreted call stack, the VM can handle
 138  * pushes and pops with a single 4-byte load and store.  (We could also
 139  * store it internally in a public structure, but the local JNI refs are
 140  * logically tied to interpreted stack frames anyway.)
 141  *
 142  * TODO: consider a "lastDeleteIndex" for quick hole-filling when an
 143  * add immediately follows a delete; must invalidate after segment pop
 144  * (which could increase the cost/complexity of method call/return).
 145  * Might be worth only using it for JNI globals.
 146  *
 147  * TODO: may want completely different add/remove algorithms for global
 148  * and local refs to improve performance.  A large circular buffer might
 149  * reduce the amortized cost of adding global references.
 150  */
 151 typedef union IRTSegmentState {
 152     u4          all;
 153     struct {
 154         u4      topIndex:16;            /* index of first unused entry */
 155         u4      numHoles:16;            /* #of holes in entire table */
 156     } parts;
 157 } IRTSegmentState;
 158 typedef struct IndirectRefTable {
 159     /* semi-public - read/write by interpreter in native call handler */
 160     IRTSegmentState segmentState;
 161
 162     /* semi-public - read-only during GC scan; pointer must not be kept */
 163     Object**        table;              /* bottom of the stack */
 164
 165     /* private */
 166     int             allocEntries;       /* #of entries we have space for */
 167     int             maxEntries;         /* max #of entries allowed */
 168     IndirectRefKind kind;               /* bit mask, ORed into all irefs */
 169
 170     // TODO: want hole-filling stats (#of holes filled, total entries scanned)
 171     //       for performance evaluation.
 172 } IndirectRefTable;
 173
 174 /* initial value to use for the "cookie" */
 175 #define IRT_SEGMENT_INIT    0
 176
 177 /*
 178  * (This is PRIVATE, but we want it inside other inlines in this header.)
 179  *
 180  * Indirectify the object.
 181  *
 182  * The object pointer itself is subject to relocation in some GC
 183  * implementations, so we shouldn't really be using it here.
 184  */
 185 INLINE IndirectRef dvmObjectToIndirectRef(Object* obj, u4 tableIndex,
 186     IndirectRefKind kind)
 187 {
 188     assert(tableIndex < 65536);
 189     u4 objChunk = (((u4) obj >> 3) ^ ((u4) obj >> 19)) & 0x3fff;
 190     u4 uref = objChunk << 18 | (tableIndex << 2) | kind;
 191     return (IndirectRef) uref;
 192 }
 193
 194 /*
 195  * (This is PRIVATE, but we want it inside other inlines in this header.)
 196  *
 197  * Extract the table index from an indirect reference.
 198  */
 199 INLINE u4 dvmIndirectRefToIndex(IndirectRef iref)
 200 {
 201     u4 uref = (u4) iref;
 202     return (uref >> 2) & 0xffff;
 203 }
 204
 205 /*
 206  * Initialize an IndirectRefTable.
 207  *
 208  * If "initialCount" != "maxCount", the table will expand as required.
 209  *
 210  * "kind" should be Local or Global.  The Global table may also hold
 211  * WeakGlobal refs.
 212  *
 213  * Returns "false" if table allocation fails.
 214  */
 215 bool dvmInitIndirectRefTable(IndirectRefTable* pRef, int initialCount,
 216     int maxCount, IndirectRefKind kind);
 217
 218 /*
 219  * Clear out the contents, freeing allocated storage.  Does not free "pRef".
 220  *
 221  * You must call dvmInitReferenceTable() before you can re-use this table.
 222  */
 223 void dvmClearIndirectRefTable(IndirectRefTable* pRef);
 224
 225 /*
 226  * Start a new segment at the top of the table.
 227  *
 228  * Returns an opaque 32-bit value that must be provided when the segment
 229  * is to be removed.
 230  *
 231  * IMPORTANT: this is implemented as a single instruction in mterp, rather
 232  * than a call here.  You can add debugging aids for the C-language
 233  * interpreters, but the basic implementation may not change.
 234  */
 235 INLINE u4 dvmPushIndirectRefTableSegment(IndirectRefTable* pRef)
 236 {
 237     return pRef->segmentState.all;
 238 }
 239
 240 /* extra debugging checks */
 241 bool dvmPopIndirectRefTableSegmentCheck(IndirectRefTable* pRef, u4 cookie);
 242
 243 /*
 244  * Remove one or more segments from the top.  The table entry identified
 245  * by "cookie" becomes the new top-most entry.
 246  *
 247  * IMPORTANT: this is implemented as a single instruction in mterp, rather
 248  * than a call here.  You can add debugging aids for the C-language
 249  * interpreters, but the basic implementation may not change.
 250  */
 251 INLINE void dvmPopIndirectRefTableSegment(IndirectRefTable* pRef, u4 cookie)
 252 {
 253     dvmPopIndirectRefTableSegmentCheck(pRef, cookie);
 254     pRef->segmentState.all = cookie;
 255 }
 256
 257 /*
 258  * Return the #of entries in the entire table.  This includes holes, and
 259  * so may be larger than the actual number of "live" entries.
 260  */
 261 INLINE size_t dvmIndirectRefTableEntries(const IndirectRefTable* pRef)
 262 {
 263     return pRef->segmentState.parts.topIndex;
 264 }
 265
 266 /*
 267  * Returns "true" if the table is full.  The table is considered full if
 268  * we would need to expand it to add another entry to the current segment.
 269  */
 270 INLINE size_t dvmIsIndirectRefTableFull(const IndirectRefTable* pRef)
 271 {
 272     return dvmIndirectRefTableEntries(pRef) == (size_t)pRef->allocEntries;
 273 }
 274
 275 /*
 276  * Add a new entry.  "obj" must be a valid non-NULL object reference
 277  * (though it's okay if it's not fully-formed, e.g. the result from
 278  * dvmMalloc doesn't have obj->clazz set).
 279  *
 280  * Returns NULL if the table is full (max entries reached, or alloc
 281  * failed during expansion).
 282  */
 283 IndirectRef dvmAddToIndirectRefTable(IndirectRefTable* pRef, u4 cookie,
 284     Object* obj);
 285
 286 /*
 287  * Add a new entry at the end.  Similar to Add but does not usually attempt
 288  * to fill in holes.  This is only appropriate to use right after a new
 289  * segment has been pushed.
 290  *
 291  * (This is intended for use when calling into a native JNI method, so
 292  * performance is critical.)
 293  */
 294 INLINE IndirectRef dvmAppendToIndirectRefTable(IndirectRefTable* pRef,
 295     u4 cookie, Object* obj)
 296 {
 297     int topIndex = pRef->segmentState.parts.topIndex;
 298     if (topIndex == pRef->allocEntries) {
 299         /* up against alloc or max limit, call the fancy version */
 300         return dvmAddToIndirectRefTable(pRef, cookie, obj);
 301     } else {
 302         IndirectRef result = dvmObjectToIndirectRef(obj, topIndex, pRef->kind);
 303         pRef->table[topIndex++] = obj;
 304         pRef->segmentState.parts.topIndex = topIndex;
 305         return result;
 306     }
 307 }
 308
 309 /* extra debugging checks */
 310 bool dvmGetFromIndirectRefTableCheck(IndirectRefTable* pRef, IndirectRef iref);
 311
 312 /*
 313  * Given an IndirectRef in the table, return the Object it refers to.
 314  *
 315  * Returns NULL if iref is invalid.
 316  */
 317 INLINE Object* dvmGetFromIndirectRefTable(IndirectRefTable* pRef,
 318     IndirectRef iref)
 319 {
 320     if (!dvmGetFromIndirectRefTableCheck(pRef, iref))
 321         return NULL;
 322
 323     int idx = dvmIndirectRefToIndex(iref);
 324     return pRef->table[idx];
 325 }
 326
 327 /*
 328  * Remove an existing entry.
 329  *
 330  * If the entry is not between the current top index and the bottom index
 331  * specified by the cookie, we don't remove anything.  This is the behavior
 332  * required by JNI's DeleteLocalRef function.
 333  *
 334  * Returns "false" if nothing was removed.
 335  */
 336 bool dvmRemoveFromIndirectRefTable(IndirectRefTable* pRef, u4 cookie,
 337     IndirectRef iref);
 338
 339 /*
 340  * Dump the contents of a reference table to the log file.
 341  */
 342 void dvmDumpIndirectRefTable(const IndirectRefTable* pRef, const char* descr);
 343
 344 #endif /*_DALVIK_INDIRECTREFTABLE*/