ReferenceTable.cpp revision 92c1f6f1b4249e4e379452ee7b49f027052bf4ce 
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(obj != NULL);
60    assert(dvmIsHeapAddress(obj));
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        //ALOGV("LREF delete %p, shift %d down", obj, moveCount);
145    } else {
146        /* last entry, falls off the end */
147        //ALOGV("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 == kClearedJniWeakGlobal ||
161            arrayObj->clazz == NULL || !dvmIsArray(arrayObj)) {
162        return 0;
163    }
164    return arrayObj->length;
165}
166
167/*
168 * This is a qsort() callback.  We sort Object* by class, allocation size,
169 * and then by the Object* itself.
170 */
171static int compareObject(const void* vobj1, const void* vobj2)
172{
173    const Object* obj1 = *((Object* const*) vobj1);
174    const Object* obj2 = *((Object* const*) vobj2);
175
176    // Ensure null references and cleared jweaks appear at the end.
177    if (obj1 == NULL) {
178        if (obj2 == NULL) {
179            return 0;
180        } else {
181            return 1;
182        }
183    } else if (obj2 == NULL) {
184        return -1;
185    }
186    if (obj1 == kClearedJniWeakGlobal) {
187        if (obj2 == kClearedJniWeakGlobal) {
188            return 0;
189        } else {
190            return 1;
191        }
192    } else if (obj2 == kClearedJniWeakGlobal) {
193        return -1;
194    }
195
196    if (obj1->clazz != obj2->clazz) {
197        return (u1*)obj1->clazz - (u1*)obj2->clazz;
198    } else {
199        size_t count1 = getElementCount(obj1);
200        size_t count2 = getElementCount(obj2);
201        if (count1 != count2) {
202            return count1 - count2;
203        } else {
204            return (u1*)obj1 - (u1*)obj2;
205        }
206    }
207}
208
209/*
210 * Log an object with some additional info.
211 *
212 * Pass in the number of elements in the array (or 0 if this is not an
213 * array object), and the number of additional objects that are identical
214 * or equivalent to the original.
215 */
216static void logSummaryLine(const Object* obj, size_t elems, int identical, int equiv)
217{
218    if (obj == NULL) {
219        LOGW("    NULL reference (count=%d)", equiv);
220        return;
221    }
222    if (obj == kClearedJniWeakGlobal) {
223        LOGW("    cleared jweak (count=%d)", equiv);
224        return;
225    }
226
227    std::string className(dvmHumanReadableType(obj));
228    if (obj->clazz == gDvm.classJavaLangClass) {
229        // We're summarizing multiple instances, so using the exemplar
230        // Class' type parameter here would be misleading.
231        className = "java.lang.Class";
232    }
233    if (elems != 0) {
234        StringAppendF(&className, " (%zd elements)", elems);
235    }
236
237    size_t total = identical + equiv + 1;
238    std::string msg(StringPrintf("%5d of %s", total, className.c_str()));
239    if (identical + equiv != 0) {
240        StringAppendF(&msg, " (%d unique instances)", equiv + 1);
241    }
242    LOGW("    %s", msg.c_str());
243}
244
245/*
246 * Dump a summary of an array of references to the log file.
247 *
248 * This is used to dump the contents of ReferenceTable and IndirectRefTable
249 * structs.
250 */
251void dvmDumpReferenceTableContents(Object* const* refs, size_t count,
252    const char* descr)
253{
254    LOGW("%s reference table (%p) dump:", descr, refs);
255
256    if (count == 0) {
257        LOGW("  (empty)");
258        return;
259    }
260
261    // Dump the most recent N entries.
262    const size_t kLast = 10;
263    int first = count - kLast;
264    if (first < 0) {
265        first = 0;
266    }
267    LOGW("  Last %d entries (of %d):", (count - first), count);
268    for (int idx = count - 1; idx >= first; --idx) {
269        const Object* ref = refs[idx];
270        if (ref == NULL) {
271            continue;
272        }
273        if (ref == kClearedJniWeakGlobal) {
274            LOGW("    %5d: cleared jweak", idx);
275            continue;
276        }
277        if (ref->clazz == NULL) {
278            // should only be possible right after a plain dvmMalloc().
279            size_t size = dvmObjectSizeInHeap(ref);
280            LOGW("    %5d: %p (raw) (%zd bytes)", idx, ref, size);
281            continue;
282        }
283
284        std::string className(dvmHumanReadableType(ref));
285
286        std::string extras;
287        size_t elems = getElementCount(ref);
288        if (elems != 0) {
289            StringAppendF(&extras, " (%zd elements)", elems);
290        } else if (ref->clazz == gDvm.classJavaLangString) {
291            const StringObject* str =
292                    reinterpret_cast<const StringObject*>(ref);
293            extras += " \"";
294            size_t count = 0;
295            char* s = dvmCreateCstrFromString(str);
296            char* p = s;
297            for (; *p && count < 16; ++p, ++count) {
298                extras += *p;
299            }
300            if (*p == 0) {
301                extras += "\"";
302            } else {
303                StringAppendF(&extras, "... (%d chars)", str->length());
304            }
305            free(s);
306        }
307        LOGW("    %5d: %p %s%s", idx, ref, className.c_str(), extras.c_str());
308    }
309
310    // Make a copy of the table, and sort it.
311    Object** tableCopy = (Object**)malloc(sizeof(Object*) * count);
312    if (tableCopy == NULL) {
313        LOGE("Unable to copy table with %d elements", count);
314        return;
315    }
316    memcpy(tableCopy, refs, sizeof(Object*) * count);
317    qsort(tableCopy, count, sizeof(Object*), compareObject);
318    refs = tableCopy;       // use sorted list
319
320    // Remove any uninteresting stuff from the list. The sort moved them all to the end.
321    while (count > 0 && refs[count-1] == NULL) {
322        --count;
323    }
324    while (count > 0 && refs[count-1] == kClearedJniWeakGlobal) {
325        --count;
326    }
327    if (count == 0) {
328        return;
329    }
330
331    // Dump a summary of the whole table.
332    LOGW("  Summary:");
333    size_t equiv, identical;
334    equiv = identical = 0;
335    size_t idx;
336    size_t elems;
337    for (idx = 1; idx < count; idx++) {
338        elems = getElementCount(refs[idx-1]);
339
340        if (refs[idx] == refs[idx-1]) {
341            // same reference, added more than once.
342            identical++;
343        } else if (refs[idx]->clazz == refs[idx-1]->clazz &&
344            getElementCount(refs[idx]) == elems)
345        {
346            // same class / element count, different object.
347            equiv++;
348        } else {
349            // different class.
350            logSummaryLine(refs[idx-1], elems, identical, equiv);
351            equiv = identical = 0;
352        }
353    }
354
355    // Handle the last entry (everything above outputs refs[i-1]).
356    elems = getElementCount(refs[idx-1]);
357    logSummaryLine(refs[count-1], elems, identical, equiv);
358
359    free(tableCopy);
360}
361
362/*
363 * Dump the contents of a ReferenceTable to the log.
364 */
365void dvmDumpReferenceTable(const ReferenceTable* pRef, const char* descr)
366{
367    dvmDumpReferenceTableContents(pRef->table, dvmReferenceTableEntries(pRef),
368        descr);
369}
370