IndirectRefTable.cpp revision ddbd6f44af283415162ea7bb1b4e7ef77c8de492 
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/*
18 * Indirect reference table management.
19 */
20#include "Dalvik.h"
21
22static void abortMaybe() {
23    // If CheckJNI is on, it'll give a more detailed error before aborting.
24    // Otherwise, we want to abort rather than hand back a bad reference.
25    if (!gDvmJni.useCheckJni) {
26        dvmAbort();
27    }
28}
29
30bool IndirectRefTable::init(size_t initialCount,
31        size_t maxCount, IndirectRefKind desiredKind)
32{
33    assert(initialCount > 0);
34    assert(initialCount <= maxCount);
35    assert(kind != kIndirectKindInvalid);
36
37    table = (Object**) malloc(initialCount * sizeof(Object*));
38    if (table == NULL) {
39        return false;
40    }
41#ifndef NDEBUG
42    memset(table, 0xd1, initialCount * sizeof(Object*));
43#endif
44
45    slotData =
46        (IndirectRefSlot*) calloc(maxCount, sizeof(IndirectRefSlot));
47    if (slotData == NULL) {
48        return false;
49    }
50
51    segmentState.all = IRT_FIRST_SEGMENT;
52    allocEntries = initialCount;
53    maxEntries = maxCount;
54    kind = desiredKind;
55
56    return true;
57}
58
59/*
60 * Clears out the contents of a IndirectRefTable, freeing allocated storage.
61 */
62void IndirectRefTable::destroy()
63{
64    free(table);
65    free(slotData);
66    table = NULL;
67    allocEntries = maxEntries = -1;
68}
69
70/*
71 * Make sure that the entry at "idx" is correctly paired with "iref".
72 */
73bool IndirectRefTable::checkEntry(const char* what, IndirectRef iref, int idx) const
74{
75    Object* obj = table[idx];
76    IndirectRef checkRef = toIndirectRef(obj, idx);
77    if (checkRef != iref) {
78        if (indirectRefKind(iref) != kIndirectKindWeakGlobal) {
79            LOGE("JNI ERROR (app bug): attempt to %s stale %s reference (req=%p vs cur=%p; table=%p)",
80                    what, indirectRefKindToString(kind), iref, checkRef, this);
81            abortMaybe();
82        }
83        return false;
84    }
85    return true;
86}
87
88IndirectRef IndirectRefTable::add(u4 cookie, Object* obj)
89{
90    IRTSegmentState prevState;
91    prevState.all = cookie;
92    size_t topIndex = segmentState.parts.topIndex;
93
94    assert(obj != NULL);
95    assert(dvmIsValidObject(obj));
96    assert(table != NULL);
97    assert(allocEntries <= maxEntries);
98    assert(segmentState.parts.numHoles >= prevState.parts.numHoles);
99
100    if (topIndex == allocEntries) {
101        /* reached end of allocated space; did we hit buffer max? */
102        if (topIndex == maxEntries) {
103            LOGE("JNI ERROR (app bug): %s reference table overflow (max=%d)",
104                    indirectRefKindToString(kind), maxEntries);
105            dump(indirectRefKindToString(kind));
106            dvmAbort();
107        }
108
109        size_t newSize = allocEntries * 2;
110        if (newSize > maxEntries) {
111            newSize = maxEntries;
112        }
113        assert(newSize > allocEntries);
114
115        Object** newTable = (Object**) realloc(table, newSize * sizeof(Object*));
116        if (newTable == NULL) {
117            LOGE("JNI ERROR (app bug): unable to expand %s reference table (from %d to %d, max=%d)",
118                    indirectRefKindToString(kind),
119                    allocEntries, newSize, maxEntries);
120            dump(indirectRefKindToString(kind));
121            dvmAbort();
122        }
123
124        /* update entries; adjust "nextEntry" in case memory moved */
125        table = newTable;
126        allocEntries = newSize;
127    }
128
129    IndirectRef result;
130
131    /*
132     * We know there's enough room in the table.  Now we just need to find
133     * the right spot.  If there's a hole, find it and fill it; otherwise,
134     * add to the end of the list.
135     */
136    int numHoles = segmentState.parts.numHoles - prevState.parts.numHoles;
137    if (numHoles > 0) {
138        assert(topIndex > 1);
139        /* find the first hole; likely to be near the end of the list */
140        Object** pScan = &table[topIndex - 1];
141        assert(*pScan != NULL);
142        while (*--pScan != NULL) {
143            assert(pScan >= table + prevState.parts.topIndex);
144        }
145        updateSlotAdd(obj, pScan - table);
146        result = toIndirectRef(obj, pScan - table);
147        *pScan = obj;
148        segmentState.parts.numHoles--;
149    } else {
150        /* add to the end */
151        updateSlotAdd(obj, topIndex);
152        result = toIndirectRef(obj, topIndex);
153        table[topIndex++] = obj;
154        segmentState.parts.topIndex = topIndex;
155    }
156
157    assert(result != NULL);
158    return result;
159}
160
161/*
162 * Verify that the indirect table lookup is valid.
163 *
164 * Returns "false" if something looks bad.
165 */
166bool IndirectRefTable::getChecked(IndirectRef iref) const
167{
168    if (iref == NULL) {
169        LOGW("Attempt to look up NULL %s reference",
170                indirectRefKindToString(kind));
171        return false;
172    }
173    if (indirectRefKind(iref) == kIndirectKindInvalid) {
174        LOGE("JNI ERROR (app bug): invalid %s reference (%p)",
175                indirectRefKindToString(kind), iref);
176        abortMaybe();
177        return false;
178    }
179
180    int topIndex = segmentState.parts.topIndex;
181    int idx = extractIndex(iref);
182    if (idx >= topIndex) {
183        /* bad -- stale reference? */
184        LOGE("JNI ERROR (app bug): accessed stale %s reference at index %d (top=%d)",
185                indirectRefKindToString(kind), idx, topIndex);
186        abortMaybe();
187        return false;
188    }
189
190    if (!checkEntry("use", iref, idx)) {
191        return false;
192    }
193
194    return true;
195}
196
197/*
198 * Remove "obj" from "pRef".  We extract the table offset bits from "iref"
199 * and zap the corresponding entry, leaving a hole if it's not at the top.
200 *
201 * If the entry is not between the current top index and the bottom index
202 * specified by the cookie, we don't remove anything.  This is the behavior
203 * required by JNI's DeleteLocalRef function.
204 *
205 * Note this is NOT called when a local frame is popped.  This is only used
206 * for explicit single removals.
207 *
208 * Returns "false" if nothing was removed.
209 */
210bool IndirectRefTable::remove(u4 cookie, IndirectRef iref)
211{
212    IRTSegmentState prevState;
213    prevState.all = cookie;
214    int topIndex = segmentState.parts.topIndex;
215    int bottomIndex = prevState.parts.topIndex;
216
217    assert(table != NULL);
218    assert(allocEntries <= maxEntries);
219    assert(segmentState.parts.numHoles >= prevState.parts.numHoles);
220
221    int idx = extractIndex(iref);
222    if (idx < bottomIndex) {
223        /* wrong segment */
224        LOGV("Attempt to remove index outside index area (%d vs %d-%d)",
225            idx, bottomIndex, topIndex);
226        return false;
227    }
228    if (idx >= topIndex) {
229        /* bad -- stale reference? */
230        LOGD("Attempt to remove invalid index %d (bottom=%d top=%d)",
231            idx, bottomIndex, topIndex);
232        return false;
233    }
234
235    if (idx == topIndex-1) {
236        /*
237         * Top-most entry.  Scan up and consume holes.  No need to NULL
238         * out the entry, since the test vs. topIndex will catch it.
239         */
240        if (!checkEntry("remove", iref, idx)) {
241            return false;
242        }
243        updateSlotRemove(idx);
244
245#ifndef NDEBUG
246        table[idx] = (Object*)0xd3d3d3d3;
247#endif
248
249        int numHoles =
250            segmentState.parts.numHoles - prevState.parts.numHoles;
251        if (numHoles != 0) {
252            while (--topIndex > bottomIndex && numHoles != 0) {
253                LOGV("+++ checking for hole at %d (cookie=0x%08x) val=%p",
254                    topIndex-1, cookie, table[topIndex-1]);
255                if (table[topIndex-1] != NULL)
256                    break;
257                LOGV("+++ ate hole at %d", topIndex-1);
258                numHoles--;
259            }
260            segmentState.parts.numHoles =
261                numHoles + prevState.parts.numHoles;
262            segmentState.parts.topIndex = topIndex;
263        } else {
264            segmentState.parts.topIndex = topIndex-1;
265            LOGV("+++ ate last entry %d", topIndex-1);
266        }
267    } else {
268        /*
269         * Not the top-most entry.  This creates a hole.  We NULL out the
270         * entry to prevent somebody from deleting it twice and screwing up
271         * the hole count.
272         */
273        if (table[idx] == NULL) {
274            LOGV("--- WEIRD: removing null entry %d", idx);
275            return false;
276        }
277        if (!checkEntry("remove", iref, idx)) {
278            return false;
279        }
280        updateSlotRemove(idx);
281
282        table[idx] = NULL;
283        segmentState.parts.numHoles++;
284        LOGV("+++ left hole at %d, holes=%d",
285            idx, segmentState.parts.numHoles);
286    }
287
288    return true;
289}
290
291const char* indirectRefKindToString(IndirectRefKind kind)
292{
293    switch (kind) {
294    case kIndirectKindInvalid:      return "invalid";
295    case kIndirectKindLocal:        return "local";
296    case kIndirectKindGlobal:       return "global";
297    case kIndirectKindWeakGlobal:   return "weak global";
298    default:                        return "UNKNOWN";
299    }
300}
301
302void IndirectRefTable::dump(const char* descr) const
303{
304    dvmDumpReferenceTableContents(table, capacity(), descr);
305}
306