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