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 */
86typedef 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 */
93typedef 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
105typedef 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 */
177typedef 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;
184typedef 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 */
212INLINE 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 */
228INLINE 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 */
237INLINE 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 */
252bool 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 */
260void 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 */
272INLINE u4 dvmPushIndirectRefTableSegment(IndirectRefTable* pRef)
273{
274    return pRef->segmentState.all;
275}
276
277/* extra debugging checks */
278bool 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 */
288INLINE 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 */
298INLINE 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 */
307INLINE 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 */
320IndirectRef 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 */
331INLINE 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 */
348bool 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 */
355INLINE 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 */
374bool dvmRemoveFromIndirectRefTable(IndirectRefTable* pRef, u4 cookie,
375    IndirectRef iref);
376
377/*
378 * Dump the contents of a reference table to the log file.
379 */
380void dvmDumpIndirectRefTable(const IndirectRefTable* pRef, const char* descr);
381
382#endif /*_DALVIK_INDIRECTREFTABLE*/
383