ReferenceTable.cpp revision fe7f2b3920bf5d66eda262e643245b03df3e57c8 
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    std::string className;
213    if (obj->clazz == NULL) {
214        /* handle "raw" dvmMalloc case */
215        className = "(raw)";
216    } else {
217        className = dvmHumanReadableType(obj);
218        if (elems != 0) {
219            className += dvmStringPrintf(" (%zd elements)", elems);
220        }
221    }
222
223    size_t total = identical + equiv + 1;
224    std::string msg(dvmStringPrintf("%5d of %s", total, className.c_str()));
225    if (identical + equiv != 0) {
226        msg += dvmStringPrintf(" (%d unique instances)", equiv + 1);
227    }
228    LOGW("%s", msg.c_str());
229}
230
231/*
232 * Dump a summary of an array of references to the log file.
233 *
234 * This is used to dump the contents of ReferenceTable and IndirectRefTable
235 * structs.
236 */
237void dvmDumpReferenceTableContents(Object* const* refs, size_t count,
238    const char* descr)
239{
240    if (count == 0) {
241        LOGW("%s reference table has no entries", descr);
242        return;
243    }
244
245    /*
246     * Dump the most recent N entries.
247     */
248    const size_t kLast = 10;
249    LOGW("Last %d entries in %s reference table:", kLast, descr);
250    int first = count - kLast;
251    if (first < 0) {
252        first = 0;
253    }
254
255    for (int idx = count - 1; idx >= first; --idx) {
256        const Object* ref = refs[idx];
257        if (ref == NULL) {
258            continue;
259        }
260        if (ref->clazz == NULL) {
261            /* should only be possible right after a plain dvmMalloc() */
262            size_t size = dvmObjectSizeInHeap(ref);
263            LOGW("%5d: %p (raw) (%zd bytes)", idx, ref, size);
264            continue;
265        }
266
267        std::string className(dvmHumanReadableType(ref));
268
269        std::string extras;
270        size_t elems = getElementCount(ref);
271        if (elems != 0) {
272            extras += dvmStringPrintf(" (%zd elements)", elems);
273        } else if (ref->clazz == gDvm.classJavaLangString) {
274            const StringObject* str =
275                    reinterpret_cast<const StringObject*>(ref);
276            extras += " \"";
277            size_t count = 0;
278            char* s = dvmCreateCstrFromString(str);
279            char* p = s;
280            for (; *p && count < 16; ++p, ++count) {
281                extras += *p;
282            }
283            if (*p == 0) {
284                extras += "\"";
285            } else {
286                extras += dvmStringPrintf("... (%d chars)", dvmStringLen(str));
287            }
288            free(s);
289        }
290        LOGW("%5d: %p %s%s", idx, ref, className.c_str(), extras.c_str());
291    }
292
293    /*
294     * Make a copy of the table, and sort it.
295     */
296    Object** tableCopy = (Object**)malloc(sizeof(Object*) * count);
297    if (tableCopy == NULL) {
298        LOGE("Unable to copy table with %d elements", count);
299        return;
300    }
301    memcpy(tableCopy, refs, sizeof(Object*) * count);
302    qsort(tableCopy, count, sizeof(Object*), compareObject);
303    refs = tableCopy;       // use sorted list
304
305    /*
306     * Find and remove any "holes" in the list.  The sort moved them all
307     * to the end.
308     *
309     * A table with nothing but NULL entries should have count==0, which
310     * was handled above, so this operation should not leave us with an
311     * empty list.
312     */
313    while (refs[count-1] == NULL) {
314        count--;
315    }
316    assert(count > 0);
317
318    /*
319     * Dump uniquified table summary.
320     */
321    LOGW("%s reference table summary (%d entries):", descr, count);
322    size_t equiv, identical;
323    equiv = identical = 0;
324    size_t idx;
325    size_t elems;
326    for (idx = 1; idx < count; idx++) {
327        elems = getElementCount(refs[idx-1]);
328
329        if (refs[idx] == refs[idx-1]) {
330            /* same reference, added more than once */
331            identical++;
332        } else if (refs[idx]->clazz == refs[idx-1]->clazz &&
333            getElementCount(refs[idx]) == elems)
334        {
335            /* same class / element count, different object */
336            equiv++;
337        } else {
338            /* different class */
339            logObject(refs[idx-1], elems, identical, equiv);
340            equiv = identical = 0;
341        }
342    }
343
344    /* handle the last entry (everything above outputs refs[i-1]) */
345    elems = getElementCount(refs[idx-1]);
346    logObject(refs[count-1], elems, identical, equiv);
347
348    free(tableCopy);
349}
350
351/*
352 * Dump the contents of a ReferenceTable to the log.
353 */
354void dvmDumpReferenceTable(const ReferenceTable* pRef, const char* descr)
355{
356    dvmDumpReferenceTableContents(pRef->table, dvmReferenceTableEntries(pRef),
357        descr);
358}
359