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