IndirectRefTable.cpp 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/*
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        LOGE("JNI ERROR (app bug): attempt to %s stale %s reference %p (should be %p)",
79                what, indirectRefKindToString(kind), iref, checkRef);
80        abortMaybe();
81        return false;
82    }
83    return true;
84}
85
86IndirectRef IndirectRefTable::add(u4 cookie, Object* obj)
87{
88    IRTSegmentState prevState;
89    prevState.all = cookie;
90    size_t topIndex = segmentState.parts.topIndex;
91
92    assert(obj != NULL);
93    assert(dvmIsValidObject(obj));
94    assert(table != NULL);
95    assert(allocEntries <= maxEntries);
96    assert(segmentState.parts.numHoles >= prevState.parts.numHoles);
97
98    if (topIndex == allocEntries) {
99        /* reached end of allocated space; did we hit buffer max? */
100        if (topIndex == maxEntries) {
101            LOGE("JNI ERROR (app bug): %s reference table overflow (max=%d)",
102                    indirectRefKindToString(kind), maxEntries);
103            dump(indirectRefKindToString(kind));
104            dvmAbort();
105        }
106
107        size_t newSize = allocEntries * 2;
108        if (newSize > maxEntries) {
109            newSize = maxEntries;
110        }
111        assert(newSize > allocEntries);
112
113        table = (Object**) realloc(table, newSize * sizeof(Object*));
114        if (table == NULL) {
115            LOGE("JNI ERROR (app bug): unable to expand %s reference table (from %d to %d, max=%d)",
116                    indirectRefKindToString(kind),
117                    allocEntries, newSize, maxEntries);
118            dump(indirectRefKindToString(kind));
119            dvmAbort();
120        }
121        allocEntries = newSize;
122    }
123
124    /*
125     * We know there's enough room in the table.  Now we just need to find
126     * the right spot.  If there's a hole, find it and fill it; otherwise,
127     * add to the end of the list.
128     */
129    IndirectRef result;
130    int numHoles = segmentState.parts.numHoles - prevState.parts.numHoles;
131    if (numHoles > 0) {
132        assert(topIndex > 1);
133        /* find the first hole; likely to be near the end of the list */
134        Object** pScan = &table[topIndex - 1];
135        assert(*pScan != NULL);
136        while (*--pScan != NULL) {
137            assert(pScan >= table + prevState.parts.topIndex);
138        }
139        updateSlotAdd(obj, pScan - table);
140        result = toIndirectRef(obj, pScan - table);
141        *pScan = obj;
142        segmentState.parts.numHoles--;
143    } else {
144        /* add to the end */
145        updateSlotAdd(obj, topIndex);
146        result = toIndirectRef(obj, topIndex);
147        table[topIndex++] = obj;
148        segmentState.parts.topIndex = topIndex;
149    }
150
151    assert(result != NULL);
152    return result;
153}
154
155/*
156 * Verify that the indirect table lookup is valid.
157 *
158 * Returns "false" if something looks bad.
159 */
160bool IndirectRefTable::getChecked(IndirectRef iref) const
161{
162    if (iref == NULL) {
163        LOGW("Attempt to look up NULL %s reference", indirectRefKindToString(kind));
164        return false;
165    }
166    if (indirectRefKind(iref) == kIndirectKindInvalid) {
167        LOGE("JNI ERROR (app bug): invalid %s reference %p",
168                indirectRefKindToString(kind), iref);
169        abortMaybe();
170        return false;
171    }
172
173    int topIndex = segmentState.parts.topIndex;
174    int idx = extractIndex(iref);
175    if (idx >= topIndex) {
176        /* bad -- stale reference? */
177        LOGE("JNI ERROR (app bug): accessed stale %s reference %p (index %d in a table of size %d)",
178                indirectRefKindToString(kind), iref, idx, topIndex);
179        abortMaybe();
180        return false;
181    }
182
183    if (table[idx] == NULL) {
184        LOGI("JNI ERROR (app bug): accessed deleted %s reference %p",
185                indirectRefKindToString(kind), iref);
186        abortMaybe();
187        return false;
188    }
189
190    if (!checkEntry("use", iref, idx)) {
191        return false;
192    }
193
194    return true;
195}
196
197static int linearScan(IndirectRef iref, int bottomIndex, int topIndex, Object** table) {
198    for (int i = bottomIndex; i < topIndex; ++i) {
199        if (table[i] == reinterpret_cast<Object*>(iref)) {
200            return i;
201        }
202    }
203    return -1;
204}
205
206bool IndirectRefTable::contains(IndirectRef iref) const {
207    return linearScan(iref, 0, segmentState.parts.topIndex, table) != -1;
208}
209
210/*
211 * Remove "obj" from "pRef".  We extract the table offset bits from "iref"
212 * and zap the corresponding entry, leaving a hole if it's not at the top.
213 *
214 * If the entry is not between the current top index and the bottom index
215 * specified by the cookie, we don't remove anything.  This is the behavior
216 * required by JNI's DeleteLocalRef function.
217 *
218 * Note this is NOT called when a local frame is popped.  This is only used
219 * for explicit single removals.
220 *
221 * Returns "false" if nothing was removed.
222 */
223bool IndirectRefTable::remove(u4 cookie, IndirectRef iref)
224{
225    IRTSegmentState prevState;
226    prevState.all = cookie;
227    int topIndex = segmentState.parts.topIndex;
228    int bottomIndex = prevState.parts.topIndex;
229
230    assert(table != NULL);
231    assert(allocEntries <= maxEntries);
232    assert(segmentState.parts.numHoles >= prevState.parts.numHoles);
233
234    int idx = extractIndex(iref);
235    bool workAroundAppJniBugs = false;
236
237    if (indirectRefKind(iref) == kIndirectKindInvalid && gDvmJni.workAroundAppJniBugs) {
238        idx = linearScan(iref, bottomIndex, topIndex, table);
239        workAroundAppJniBugs = true;
240        if (idx == -1) {
241            LOGW("trying to work around app JNI bugs, but didn't find %p in table!", iref);
242            return false;
243        }
244    }
245
246    if (idx < bottomIndex) {
247        /* wrong segment */
248        LOGV("Attempt to remove index outside index area (%d vs %d-%d)",
249            idx, bottomIndex, topIndex);
250        return false;
251    }
252    if (idx >= topIndex) {
253        /* bad -- stale reference? */
254        LOGD("Attempt to remove invalid index %d (bottom=%d top=%d)",
255            idx, bottomIndex, topIndex);
256        return false;
257    }
258
259    if (idx == topIndex-1) {
260        // Top-most entry.  Scan up and consume holes.
261
262        if (workAroundAppJniBugs == false && !checkEntry("remove", iref, idx)) {
263            return false;
264        }
265
266        table[idx] = NULL;
267        int numHoles = segmentState.parts.numHoles - prevState.parts.numHoles;
268        if (numHoles != 0) {
269            while (--topIndex > bottomIndex && numHoles != 0) {
270                LOGV("+++ checking for hole at %d (cookie=0x%08x) val=%p",
271                    topIndex-1, cookie, table[topIndex-1]);
272                if (table[topIndex-1] != NULL) {
273                    break;
274                }
275                LOGV("+++ ate hole at %d", topIndex-1);
276                numHoles--;
277            }
278            segmentState.parts.numHoles = numHoles + prevState.parts.numHoles;
279            segmentState.parts.topIndex = topIndex;
280        } else {
281            segmentState.parts.topIndex = topIndex-1;
282            LOGV("+++ ate last entry %d", topIndex-1);
283        }
284    } else {
285        /*
286         * Not the top-most entry.  This creates a hole.  We NULL out the
287         * entry to prevent somebody from deleting it twice and screwing up
288         * the hole count.
289         */
290        if (table[idx] == NULL) {
291            LOGV("--- WEIRD: removing null entry %d", idx);
292            return false;
293        }
294        if (workAroundAppJniBugs == false && !checkEntry("remove", iref, idx)) {
295            return false;
296        }
297
298        table[idx] = NULL;
299        segmentState.parts.numHoles++;
300        LOGV("+++ left hole at %d, holes=%d", idx, segmentState.parts.numHoles);
301    }
302
303    return true;
304}
305
306const char* indirectRefKindToString(IndirectRefKind kind)
307{
308    switch (kind) {
309    case kIndirectKindInvalid:      return "invalid";
310    case kIndirectKindLocal:        return "local";
311    case kIndirectKindGlobal:       return "global";
312    case kIndirectKindWeakGlobal:   return "weak global";
313    default:                        return "UNKNOWN";
314    }
315}
316
317void IndirectRefTable::dump(const char* descr) const
318{
319    dvmDumpReferenceTableContents(table, capacity(), descr);
320}
321