AllocTracker.cpp revision 4308417beec548c2b2c06ecec4f7f4a965b09fb2 
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 * Allocation tracking and reporting.  We maintain a circular buffer with
19 * the most recent allocations.  The data can be viewed through DDMS.
20 *
21 * There are two basic approaches: manage the buffer with atomic updates
22 * and do a system-wide suspend when DDMS requests it, or protect all
23 * accesses with a mutex.  The former is potentially more efficient, but
24 * the latter is much simpler and more reliable.
25 *
26 * Ideally we'd just use the object heap allocation mutex to guard this
27 * structure, but at the point we grab that (under dvmMalloc()) we're just
28 * allocating a collection of bytes and no longer have the class reference.
29 * Because this is an optional feature it's best to leave the existing
30 * code undisturbed and just use an additional lock.
31 *
32 * We don't currently track allocations of class objects.  We could, but
33 * with the possible exception of Proxy objects they're not that interesting.
34 *
35 * TODO: if we add support for class unloading, we need to add the class
36 * references here to the root set (or just disable class unloading while
37 * this is active).
38 *
39 * TODO: consider making the parameters configurable, so DDMS can decide
40 * how many allocations it wants to see and what the stack depth should be.
41 * Changing the window size is easy, changing the max stack depth is harder
42 * because we go from an array of fixed-size structs to variable-sized data.
43 */
44#include "Dalvik.h"
45
46#define kMaxAllocRecordStackDepth   16      /* max 255 */
47#define kNumAllocRecords            512     /* MUST be power of 2 */
48
49/*
50 * Record the details of an allocation.
51 */
52struct AllocRecord {
53    ClassObject*    clazz;      /* class allocated in this block */
54    u4              size;       /* total size requested */
55    u2              threadId;   /* simple thread ID; could be recycled */
56
57    /* stack trace elements; unused entries have method==NULL */
58    struct {
59        const Method* method;   /* which method we're executing in */
60        int         pc;         /* current execution offset, in 16-bit units */
61    } stackElem[kMaxAllocRecordStackDepth];
62
63    /*
64     * This was going to be either wall-clock time in seconds or monotonic
65     * time in milliseconds since the VM started, to give a rough sense for
66     * how long ago an allocation happened.  This adds a system call per
67     * allocation, which is too much overhead.
68     */
69    //u4      timestamp;
70};
71
72/*
73 * Initialize a few things.  This gets called early, so keep activity to
74 * a minimum.
75 */
76bool dvmAllocTrackerStartup()
77{
78    /* prep locks */
79    dvmInitMutex(&gDvm.allocTrackerLock);
80
81    /* initialized when enabled by DDMS */
82    assert(gDvm.allocRecords == NULL);
83
84    return true;
85}
86
87/*
88 * Release anything we're holding on to.
89 */
90void dvmAllocTrackerShutdown()
91{
92    free(gDvm.allocRecords);
93    dvmDestroyMutex(&gDvm.allocTrackerLock);
94}
95
96
97/*
98 * ===========================================================================
99 *      Collection
100 * ===========================================================================
101 */
102
103/*
104 * Enable allocation tracking.  Does nothing if tracking is already enabled.
105 *
106 * Returns "true" on success.
107 */
108bool dvmEnableAllocTracker()
109{
110    bool result = true;
111    dvmLockMutex(&gDvm.allocTrackerLock);
112
113    if (gDvm.allocRecords == NULL) {
114        ALOGI("Enabling alloc tracker (%d entries, %d frames --> %d bytes)",
115            kNumAllocRecords, kMaxAllocRecordStackDepth,
116            sizeof(AllocRecord) * kNumAllocRecords);
117        gDvm.allocRecordHead = gDvm.allocRecordCount = 0;
118        gDvm.allocRecords =
119            (AllocRecord*) malloc(sizeof(AllocRecord) * kNumAllocRecords);
120
121        if (gDvm.allocRecords == NULL)
122            result = false;
123    }
124
125    dvmUnlockMutex(&gDvm.allocTrackerLock);
126    return result;
127}
128
129/*
130 * Disable allocation tracking.  Does nothing if tracking is not enabled.
131 */
132void dvmDisableAllocTracker()
133{
134    dvmLockMutex(&gDvm.allocTrackerLock);
135
136    if (gDvm.allocRecords != NULL) {
137        free(gDvm.allocRecords);
138        gDvm.allocRecords = NULL;
139    }
140
141    dvmUnlockMutex(&gDvm.allocTrackerLock);
142}
143
144/*
145 * Get the last few stack frames.
146 */
147static void getStackFrames(Thread* self, AllocRecord* pRec)
148{
149    int stackDepth = 0;
150    void* fp;
151
152    fp = self->interpSave.curFrame;
153
154    while ((fp != NULL) && (stackDepth < kMaxAllocRecordStackDepth)) {
155        const StackSaveArea* saveArea = SAVEAREA_FROM_FP(fp);
156        const Method* method = saveArea->method;
157
158        if (!dvmIsBreakFrame((u4*) fp)) {
159            pRec->stackElem[stackDepth].method = method;
160            if (dvmIsNativeMethod(method)) {
161                pRec->stackElem[stackDepth].pc = 0;
162            } else {
163                assert(saveArea->xtra.currentPc >= method->insns &&
164                        saveArea->xtra.currentPc <
165                        method->insns + dvmGetMethodInsnsSize(method));
166                pRec->stackElem[stackDepth].pc =
167                    (int) (saveArea->xtra.currentPc - method->insns);
168            }
169            stackDepth++;
170        }
171
172        assert(fp != saveArea->prevFrame);
173        fp = saveArea->prevFrame;
174    }
175
176    /* clear out the rest (normally there won't be any) */
177    while (stackDepth < kMaxAllocRecordStackDepth) {
178        pRec->stackElem[stackDepth].method = NULL;
179        pRec->stackElem[stackDepth].pc = 0;
180        stackDepth++;
181    }
182}
183
184/*
185 * Add a new allocation to the set.
186 */
187void dvmDoTrackAllocation(ClassObject* clazz, size_t size)
188{
189    Thread* self = dvmThreadSelf();
190    if (self == NULL) {
191        LOGW("alloc tracker: no thread");
192        return;
193    }
194
195    dvmLockMutex(&gDvm.allocTrackerLock);
196    if (gDvm.allocRecords == NULL) {
197        dvmUnlockMutex(&gDvm.allocTrackerLock);
198        return;
199    }
200
201    /* advance and clip */
202    if (++gDvm.allocRecordHead == kNumAllocRecords)
203        gDvm.allocRecordHead = 0;
204
205    AllocRecord* pRec = &gDvm.allocRecords[gDvm.allocRecordHead];
206
207    pRec->clazz = clazz;
208    pRec->size = size;
209    pRec->threadId = self->threadId;
210    getStackFrames(self, pRec);
211
212    if (gDvm.allocRecordCount < kNumAllocRecords)
213        gDvm.allocRecordCount++;
214
215    dvmUnlockMutex(&gDvm.allocTrackerLock);
216}
217
218
219/*
220 * ===========================================================================
221 *      Reporting
222 * ===========================================================================
223 */
224
225/*
226The data we send to DDMS contains everything we have recorded.
227
228Message header (all values big-endian):
229  (1b) message header len (to allow future expansion); includes itself
230  (1b) entry header len
231  (1b) stack frame len
232  (2b) number of entries
233  (4b) offset to string table from start of message
234  (2b) number of class name strings
235  (2b) number of method name strings
236  (2b) number of source file name strings
237  For each entry:
238    (4b) total allocation size
239    (2b) threadId
240    (2b) allocated object's class name index
241    (1b) stack depth
242    For each stack frame:
243      (2b) method's class name
244      (2b) method name
245      (2b) method source file
246      (2b) line number, clipped to 32767; -2 if native; -1 if no source
247  (xb) class name strings
248  (xb) method name strings
249  (xb) source file strings
250
251  As with other DDM traffic, strings are sent as a 4-byte length
252  followed by UTF-16 data.
253
254We send up 16-bit unsigned indexes into string tables.  In theory there
255can be (kMaxAllocRecordStackDepth * kNumAllocRecords) unique strings in
256each table, but in practice there should be far fewer.
257
258The chief reason for using a string table here is to keep the size of
259the DDMS message to a minimum.  This is partly to make the protocol
260efficient, but also because we have to form the whole thing up all at
261once in a memory buffer.
262
263We use separate string tables for class names, method names, and source
264files to keep the indexes small.  There will generally be no overlap
265between the contents of these tables.
266*/
267const int kMessageHeaderLen = 15;
268const int kEntryHeaderLen = 9;
269const int kStackFrameLen = 8;
270
271/*
272 * Return the index of the head element.
273 *
274 * We point at the most-recently-written record, so if allocRecordCount is 1
275 * we want to use the current element.  Take "head+1" and subtract count
276 * from it.
277 *
278 * We need to handle underflow in our circular buffer, so we add
279 * kNumAllocRecords and then mask it back down.
280 */
281inline static int headIndex()
282{
283    return (gDvm.allocRecordHead+1 + kNumAllocRecords - gDvm.allocRecordCount)
284        & (kNumAllocRecords-1);
285}
286
287/*
288 * Dump the contents of a PointerSet full of character pointers.
289 */
290static void dumpStringTable(PointerSet* strings)
291{
292    int count = dvmPointerSetGetCount(strings);
293    int i;
294
295    for (i = 0; i < count; i++)
296        printf("  %s\n", (const char*) dvmPointerSetGetEntry(strings, i));
297}
298
299/*
300 * Get the method's source file.  If we don't know it, return "" instead
301 * of a NULL pointer.
302 */
303static const char* getMethodSourceFile(const Method* method)
304{
305    const char* fileName = dvmGetMethodSourceFile(method);
306    if (fileName == NULL)
307        fileName = "";
308    return fileName;
309}
310
311/*
312 * Generate string tables.
313 *
314 * Our source material is UTF-8 string constants from DEX files.  If we
315 * want to be thorough we can generate a hash value for each string and
316 * use the VM hash table implementation, or we can do a quick & dirty job
317 * by just maintaining a list of unique pointers.  If the same string
318 * constant appears in multiple DEX files we'll end up with duplicates,
319 * but in practice this shouldn't matter (and if it does, we can uniq-sort
320 * the result in a second pass).
321 */
322static bool populateStringTables(PointerSet* classNames,
323    PointerSet* methodNames, PointerSet* fileNames)
324{
325    int count = gDvm.allocRecordCount;
326    int idx = headIndex();
327    int classCount, methodCount, fileCount;         /* debug stats */
328
329    classCount = methodCount = fileCount = 0;
330
331    while (count--) {
332        AllocRecord* pRec = &gDvm.allocRecords[idx];
333
334        dvmPointerSetAddEntry(classNames, pRec->clazz->descriptor);
335        classCount++;
336
337        int i;
338        for (i = 0; i < kMaxAllocRecordStackDepth; i++) {
339            if (pRec->stackElem[i].method == NULL)
340                break;
341
342            const Method* method = pRec->stackElem[i].method;
343            dvmPointerSetAddEntry(classNames, method->clazz->descriptor);
344            classCount++;
345            dvmPointerSetAddEntry(methodNames, method->name);
346            methodCount++;
347            dvmPointerSetAddEntry(fileNames, getMethodSourceFile(method));
348            fileCount++;
349        }
350
351        idx = (idx + 1) & (kNumAllocRecords-1);
352    }
353
354    ALOGI("class %d/%d, method %d/%d, file %d/%d",
355        dvmPointerSetGetCount(classNames), classCount,
356        dvmPointerSetGetCount(methodNames), methodCount,
357        dvmPointerSetGetCount(fileNames), fileCount);
358
359    return true;
360}
361
362/*
363 * Generate the base info (i.e. everything but the string tables).
364 *
365 * This should be called twice.  On the first call, "ptr" is NULL and
366 * "baseLen" is zero.  The return value is used to allocate a buffer.
367 * On the second call, "ptr" points to a data buffer, and "baseLen"
368 * holds the value from the result of the first call.
369 *
370 * The size of the output data is returned.
371 */
372static size_t generateBaseOutput(u1* ptr, size_t baseLen,
373    const PointerSet* classNames, const PointerSet* methodNames,
374    const PointerSet* fileNames)
375{
376    u1* origPtr = ptr;
377    int count = gDvm.allocRecordCount;
378    int idx = headIndex();
379
380    if (origPtr != NULL) {
381        set1(&ptr[0], kMessageHeaderLen);
382        set1(&ptr[1], kEntryHeaderLen);
383        set1(&ptr[2], kStackFrameLen);
384        set2BE(&ptr[3], count);
385        set4BE(&ptr[5], baseLen);
386        set2BE(&ptr[9], dvmPointerSetGetCount(classNames));
387        set2BE(&ptr[11], dvmPointerSetGetCount(methodNames));
388        set2BE(&ptr[13], dvmPointerSetGetCount(fileNames));
389    }
390    ptr += kMessageHeaderLen;
391
392    while (count--) {
393        AllocRecord* pRec = &gDvm.allocRecords[idx];
394
395        /* compute depth */
396        int  depth;
397        for (depth = 0; depth < kMaxAllocRecordStackDepth; depth++) {
398            if (pRec->stackElem[depth].method == NULL)
399                break;
400        }
401
402        /* output header */
403        if (origPtr != NULL) {
404            set4BE(&ptr[0], pRec->size);
405            set2BE(&ptr[4], pRec->threadId);
406            set2BE(&ptr[6],
407                dvmPointerSetFind(classNames, pRec->clazz->descriptor));
408            set1(&ptr[8], depth);
409        }
410        ptr += kEntryHeaderLen;
411
412        /* convert stack frames */
413        int i;
414        for (i = 0; i < depth; i++) {
415            if (origPtr != NULL) {
416                const Method* method = pRec->stackElem[i].method;
417                int lineNum;
418
419                lineNum = dvmLineNumFromPC(method, pRec->stackElem[i].pc);
420                if (lineNum > 32767)
421                    lineNum = 32767;
422
423                set2BE(&ptr[0], dvmPointerSetFind(classNames,
424                        method->clazz->descriptor));
425                set2BE(&ptr[2], dvmPointerSetFind(methodNames,
426                        method->name));
427                set2BE(&ptr[4], dvmPointerSetFind(fileNames,
428                        getMethodSourceFile(method)));
429                set2BE(&ptr[6], (u2)lineNum);
430            }
431            ptr += kStackFrameLen;
432        }
433
434        idx = (idx + 1) & (kNumAllocRecords-1);
435    }
436
437    return ptr - origPtr;
438}
439
440/*
441 * Compute the size required to store a string table.  Includes the length
442 * word and conversion to UTF-16.
443 */
444static size_t computeStringTableSize(PointerSet* strings)
445{
446    int count = dvmPointerSetGetCount(strings);
447    size_t size = 0;
448    int i;
449
450    for (i = 0; i < count; i++) {
451        const char* str = (const char*) dvmPointerSetGetEntry(strings, i);
452
453        size += 4 + dvmUtf8Len(str) * 2;
454    }
455
456    return size;
457}
458
459/*
460 * Convert a UTF-8 string to UTF-16.  We also need to byte-swap the values
461 * to big-endian, and we can't assume even alignment on the target.
462 *
463 * Returns the string's length, in characters.
464 */
465static int convertUtf8ToUtf16BEUA(u1* utf16Str, const char* utf8Str)
466{
467    u1* origUtf16Str = utf16Str;
468
469    while (*utf8Str != '\0') {
470        u2 utf16 = dexGetUtf16FromUtf8(&utf8Str);       /* advances utf8Str */
471        set2BE(utf16Str, utf16);
472        utf16Str += 2;
473    }
474
475    return (utf16Str - origUtf16Str) / 2;
476}
477
478/*
479 * Output a string table serially.
480 */
481static size_t outputStringTable(PointerSet* strings, u1* ptr)
482{
483    int count = dvmPointerSetGetCount(strings);
484    u1* origPtr = ptr;
485    int i;
486
487    for (i = 0; i < count; i++) {
488        const char* str = (const char*) dvmPointerSetGetEntry(strings, i);
489        int charLen;
490
491        /* copy UTF-8 string to big-endian unaligned UTF-16 */
492        charLen = convertUtf8ToUtf16BEUA(&ptr[4], str);
493        set4BE(&ptr[0], charLen);
494
495        ptr += 4 + charLen * 2;
496    }
497
498    return ptr - origPtr;
499}
500
501/*
502 * Generate a DDM packet with all of the tracked allocation data.
503 *
504 * On success, returns "true" with "*pData" and "*pDataLen" set.
505 */
506bool dvmGenerateTrackedAllocationReport(u1** pData, size_t* pDataLen)
507{
508    bool result = false;
509    u1* buffer = NULL;
510
511    dvmLockMutex(&gDvm.allocTrackerLock);
512
513    /*
514     * Part 1: generate string tables.
515     */
516    PointerSet* classNames = NULL;
517    PointerSet* methodNames = NULL;
518    PointerSet* fileNames = NULL;
519
520    /*
521     * Allocate storage.  Usually there's 60-120 of each thing (sampled
522     * when max=512), but it varies widely and isn't closely bound to
523     * the number of allocations we've captured.  The sets expand quickly
524     * if needed.
525     */
526    classNames = dvmPointerSetAlloc(128);
527    methodNames = dvmPointerSetAlloc(128);
528    fileNames = dvmPointerSetAlloc(128);
529    if (classNames == NULL || methodNames == NULL || fileNames == NULL) {
530        LOGE("Failed allocating pointer sets");
531        goto bail;
532    }
533
534    if (!populateStringTables(classNames, methodNames, fileNames))
535        goto bail;
536
537    if (false) {
538        printf("Classes:\n");
539        dumpStringTable(classNames);
540        printf("Methods:\n");
541        dumpStringTable(methodNames);
542        printf("Files:\n");
543        dumpStringTable(fileNames);
544    }
545
546    /*
547     * Part 2: compute the size of the output.
548     *
549     * (Could also just write to an expanding buffer.)
550     */
551    size_t baseSize, totalSize;
552    baseSize = generateBaseOutput(NULL, 0, classNames, methodNames, fileNames);
553    assert(baseSize > 0);
554    totalSize = baseSize;
555    totalSize += computeStringTableSize(classNames);
556    totalSize += computeStringTableSize(methodNames);
557    totalSize += computeStringTableSize(fileNames);
558    ALOGI("Generated AT, size is %zd/%zd", baseSize, totalSize);
559
560    /*
561     * Part 3: allocate a buffer and generate the output.
562     */
563    u1* strPtr;
564
565    buffer = (u1*) malloc(totalSize);
566    strPtr = buffer + baseSize;
567    generateBaseOutput(buffer, baseSize, classNames, methodNames, fileNames);
568    strPtr += outputStringTable(classNames, strPtr);
569    strPtr += outputStringTable(methodNames, strPtr);
570    strPtr += outputStringTable(fileNames, strPtr);
571    if (strPtr - buffer != (int)totalSize) {
572        LOGE("size mismatch (%d vs %zd)", strPtr - buffer, totalSize);
573        dvmAbort();
574    }
575    //dvmPrintHexDump(buffer, totalSize);
576
577    *pData = buffer;
578    *pDataLen = totalSize;
579    buffer = NULL;          // don't free -- caller will own
580    result = true;
581
582bail:
583    dvmPointerSetFree(classNames);
584    dvmPointerSetFree(methodNames);
585    dvmPointerSetFree(fileNames);
586    free(buffer);
587    dvmUnlockMutex(&gDvm.allocTrackerLock);
588    //dvmDumpTrackedAllocations(false);
589    return result;
590}
591
592/*
593 * Dump the tracked allocations to the log file.
594 *
595 * If "enable" is set, we try to enable the feature if it's not already
596 * active.
597 */
598void dvmDumpTrackedAllocations(bool enable)
599{
600    if (enable)
601        dvmEnableAllocTracker();
602
603    dvmLockMutex(&gDvm.allocTrackerLock);
604    if (gDvm.allocRecords == NULL) {
605        dvmUnlockMutex(&gDvm.allocTrackerLock);
606        return;
607    }
608
609    /*
610     * "idx" is the head of the list.  We want to start at the end of the
611     * list and move forward to the tail.
612     */
613    int idx = headIndex();
614    int count = gDvm.allocRecordCount;
615
616    ALOGI("Tracked allocations, (head=%d count=%d)",
617        gDvm.allocRecordHead, count);
618    while (count--) {
619        AllocRecord* pRec = &gDvm.allocRecords[idx];
620        ALOGI(" T=%-2d %6d %s",
621            pRec->threadId, pRec->size, pRec->clazz->descriptor);
622
623        if (true) {
624            for (int i = 0; i < kMaxAllocRecordStackDepth; i++) {
625                if (pRec->stackElem[i].method == NULL)
626                    break;
627
628                const Method* method = pRec->stackElem[i].method;
629                if (dvmIsNativeMethod(method)) {
630                    ALOGI("    %s.%s (Native)",
631                        method->clazz->descriptor, method->name);
632                } else {
633                    ALOGI("    %s.%s +%d",
634                        method->clazz->descriptor, method->name,
635                        pRec->stackElem[i].pc);
636                }
637            }
638        }
639
640        /* pause periodically to help logcat catch up */
641        if ((count % 5) == 0)
642            usleep(40000);
643
644        idx = (idx + 1) & (kNumAllocRecords-1);
645    }
646
647    dvmUnlockMutex(&gDvm.allocTrackerLock);
648    if (false) {
649        u1* data;
650        size_t dataLen;
651        if (dvmGenerateTrackedAllocationReport(&data, &dataLen))
652            free(data);
653    }
654}
655