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