ReferenceTable.cpp revision 60fc806b679a3655c228b4093058c59941a49cfe 
1/*
2 * Copyright (C) 2008 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 * Reference table management.
19 */
20#include "Dalvik.h"
21
22/*
23 * Initialize a ReferenceTable structure.
24 */
25bool dvmInitReferenceTable(ReferenceTable* pRef, int initialCount,
26    int maxCount)
27{
28    assert(initialCount > 0);
29    assert(initialCount <= maxCount);
30
31    pRef->table = (Object**) malloc(initialCount * sizeof(Object*));
32    if (pRef->table == NULL)
33        return false;
34#ifndef NDEBUG
35    memset(pRef->table, 0xdd, initialCount * sizeof(Object*));
36#endif
37    pRef->nextEntry = pRef->table;
38    pRef->allocEntries = initialCount;
39    pRef->maxEntries = maxCount;
40
41    return true;
42}
43
44/*
45 * Clears out the contents of a ReferenceTable, freeing allocated storage.
46 */
47void dvmClearReferenceTable(ReferenceTable* pRef)
48{
49    free(pRef->table);
50    pRef->table = pRef->nextEntry = NULL;
51    pRef->allocEntries = pRef->maxEntries = -1;
52}
53
54/*
55 * Add "obj" to "pRef".
56 */
57bool dvmAddToReferenceTable(ReferenceTable* pRef, Object* obj)
58{
59    assert(dvmIsValidObject(obj));
60    assert(obj != NULL);
61    assert(pRef->table != NULL);
62    assert(pRef->allocEntries <= pRef->maxEntries);
63
64    if (pRef->nextEntry == pRef->table + pRef->allocEntries) {
65        /* reached end of allocated space; did we hit buffer max? */
66        if (pRef->nextEntry == pRef->table + pRef->maxEntries) {
67            LOGW("ReferenceTable overflow (max=%d)", pRef->maxEntries);
68            return false;
69        }
70
71        Object** newTable;
72        int newSize;
73
74        newSize = pRef->allocEntries * 2;
75        if (newSize > pRef->maxEntries)
76            newSize = pRef->maxEntries;
77        assert(newSize > pRef->allocEntries);
78
79        newTable = (Object**) realloc(pRef->table, newSize * sizeof(Object*));
80        if (newTable == NULL) {
81            LOGE("Unable to expand ref table (from %d to %d %d-byte entries)",
82                pRef->allocEntries, newSize, sizeof(Object*));
83            return false;
84        }
85        LOGVV("Growing %p from %d to %d", pRef, pRef->allocEntries, newSize);
86
87        /* update entries; adjust "nextEntry" in case memory moved */
88        pRef->nextEntry = newTable + (pRef->nextEntry - pRef->table);
89        pRef->table = newTable;
90        pRef->allocEntries = newSize;
91    }
92
93    *pRef->nextEntry++ = obj;
94    return true;
95}
96
97/*
98 * Returns NULL if not found.
99 */
100Object** dvmFindInReferenceTable(const ReferenceTable* pRef, Object** bottom,
101    Object* obj)
102{
103    Object** ptr;
104
105    ptr = pRef->nextEntry;
106    while (--ptr >= bottom) {
107        if (*ptr == obj)
108            return ptr;
109    }
110    return NULL;
111}
112
113/*
114 * Remove "obj" from "pRef".  We start at the end of the list (where the
115 * most-recently-added element is), and stop searching for a match after
116 * examining the element at "bottom".
117 *
118 * Most of the time "obj" is at or near the end of the list.  If not, we
119 * compact it down.
120 */
121bool dvmRemoveFromReferenceTable(ReferenceTable* pRef, Object** bottom,
122    Object* obj)
123{
124    Object** ptr;
125
126    assert(pRef->table != NULL);
127
128    /*
129     * Scan from the most-recently-added entry up to the bottom entry for
130     * this frame.
131     */
132    ptr = dvmFindInReferenceTable(pRef, bottom, obj);
133    if (ptr == NULL)
134        return false;
135
136    /*
137     * Delete the entry.
138     */
139    pRef->nextEntry--;
140    int moveCount = pRef->nextEntry - ptr;
141    if (moveCount != 0) {
142        /* remove from middle, slide the rest down */
143        memmove(ptr, ptr+1, moveCount * sizeof(Object*));
144        //LOGV("LREF delete %p, shift %d down", obj, moveCount);
145    } else {
146        /* last entry, falls off the end */
147        //LOGV("LREF delete %p from end", obj);
148    }
149
150    return true;
151}
152
153/*
154 * If "obj" is an array, return the number of elements in the array.
155 * Otherwise, return zero.
156 */
157static size_t getElementCount(const Object* obj)
158{
159    const ArrayObject* arrayObj = (ArrayObject*) obj;
160    if (arrayObj == NULL || arrayObj->clazz == NULL || !dvmIsArray(arrayObj))
161        return 0;
162    return arrayObj->length;
163}
164
165/*
166 * This is a qsort() callback.  We sort Object* by class, allocation size,
167 * and then by the Object* itself.
168 */
169static int compareObject(const void* vobj1, const void* vobj2)
170{
171    const Object* obj1 = *((Object* const*) vobj1);
172    const Object* obj2 = *((Object* const*) vobj2);
173
174    /* ensure null references appear at the end */
175    if (obj1 == NULL) {
176        if (obj2 == NULL) {
177            return 0;
178        } else {
179            return 1;
180        }
181    } else if (obj2 == NULL) {
182        return -1;
183    }
184
185    if (obj1->clazz != obj2->clazz) {
186        return (u1*)obj1->clazz - (u1*)obj2->clazz;
187    } else {
188        size_t count1 = getElementCount(obj1);
189        size_t count2 = getElementCount(obj2);
190        if (count1 != count2) {
191            return count1 - count2;
192        } else {
193            return (u1*)obj1 - (u1*)obj2;
194        }
195    }
196}
197
198/*
199 * Log an object with some additional info.
200 *
201 * Pass in the number of elements in the array (or 0 if this is not an
202 * array object), and the number of additional objects that are identical
203 * or equivalent to the original.
204 */
205static void logObject(const Object* obj, size_t elems, int identical, int equiv)
206{
207    if (obj == NULL) {
208        LOGW("  NULL reference (count=%d)", equiv);
209        return;
210    }
211
212    /* handle "raw" dvmMalloc case */
213    const char* descriptor =
214        (obj->clazz != NULL) ? obj->clazz->descriptor : "(raw)";
215
216    char elemStr[16];
217
218    if (elems != 0) {
219        snprintf(elemStr, sizeof(elemStr), " [%zd]", elems);
220    } else {
221        elemStr[0] = '\0';
222    }
223
224    if (identical + equiv != 0) {
225        LOGW("%5d of %s%s (%d unique)", identical + equiv +1,
226            descriptor, elemStr, equiv +1);
227    } else {
228        LOGW("%5d of %s%s", identical + equiv +1, descriptor, elemStr);
229    }
230}
231
232/*
233 * Dump a summary of an array of references to the log file.
234 *
235 * This is used to dump the contents of ReferenceTable and IndirectRefTable
236 * structs.
237 */
238void dvmDumpReferenceTableContents(Object* const* refs, size_t count,
239    const char* descr)
240{
241    if (count == 0) {
242        LOGW("%s reference table has no entries", descr);
243        return;
244    }
245
246    /*
247     * Dump the most recent N entries.
248     */
249    const size_t kLast = 10;
250    LOGW("Last %d entries in %s reference table:", kLast, descr);
251    int start = count - kLast;
252    if (start < 0)
253        start = 0;
254
255    size_t idx, elems;
256    for (idx = start; idx < count; idx++) {
257        const Object* ref = refs[idx];
258        if (ref == NULL)
259            continue;
260
261        elems = getElementCount(ref);
262
263        if (ref->clazz == NULL) {
264            /* should only be possible right after a plain dvmMalloc() */
265            size_t size = dvmObjectSizeInHeap(ref);
266            LOGW("%5d: %p cls=(raw) (%zd bytes)", idx, ref, size);
267        } else if (dvmIsClassObject(ref)) {
268            ClassObject* clazz = (ClassObject*) ref;
269            LOGW("%5d: %p cls=%s '%s'", idx, ref, ref->clazz->descriptor,
270                clazz->descriptor);
271        } else if (elems != 0) {
272            LOGW("%5d: %p cls=%s [%zd]",
273                idx, ref, ref->clazz->descriptor, elems);
274        } else {
275            LOGW("%5d: %p cls=%s", idx, ref, ref->clazz->descriptor);
276        }
277    }
278
279    /*
280     * Make a copy of the table, and sort it.
281     */
282    Object** tableCopy = (Object**)malloc(sizeof(Object*) * count);
283    if (tableCopy == NULL) {
284        LOGE("Unable to copy table with %d elements", count);
285        return;
286    }
287    memcpy(tableCopy, refs, sizeof(Object*) * count);
288    qsort(tableCopy, count, sizeof(Object*), compareObject);
289    refs = tableCopy;       // use sorted list
290
291    /*
292     * Find and remove any "holes" in the list.  The sort moved them all
293     * to the end.
294     *
295     * A table with nothing but NULL entries should have count==0, which
296     * was handled above, so this operation should not leave us with an
297     * empty list.
298     */
299    while (refs[count-1] == NULL) {
300        count--;
301    }
302    assert(count > 0);
303
304    /*
305     * Dump uniquified table summary.
306     */
307    LOGW("%s reference table summary (%d entries):", descr, count);
308    size_t equiv, identical;
309    equiv = identical = 0;
310    for (idx = 1; idx < count; idx++) {
311        elems = getElementCount(refs[idx-1]);
312
313        if (refs[idx] == refs[idx-1]) {
314            /* same reference, added more than once */
315            identical++;
316        } else if (refs[idx]->clazz == refs[idx-1]->clazz &&
317            getElementCount(refs[idx]) == elems)
318        {
319            /* same class / element count, different object */
320            equiv++;
321        } else {
322            /* different class */
323            logObject(refs[idx-1], elems, identical, equiv);
324            equiv = identical = 0;
325        }
326    }
327
328    /* handle the last entry (everything above outputs refs[i-1]) */
329    elems = getElementCount(refs[idx-1]);
330    logObject(refs[count-1], elems, identical, equiv);
331
332    free(tableCopy);
333}
334
335/*
336 * Dump the contents of a ReferenceTable to the log.
337 */
338void dvmDumpReferenceTable(const ReferenceTable* pRef, const char* descr)
339{
340    dvmDumpReferenceTableContents(pRef->table, dvmReferenceTableEntries(pRef),
341        descr);
342}
343