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