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#include "Hprof.h"
18#include "HprofStack.h"
19#include "alloc/HeapInternal.h"
20
21static HashTable *gStackTraceHashTable = NULL;
22static int gSerialNumber = 0;
23
24/* Number of stack frames to cache */
25#define STACK_DEPTH 8
26
27typedef struct {
28    int serialNumber;
29    int threadSerialNumber;
30    int frameIds[STACK_DEPTH];
31} StackTrace;
32
33typedef struct {
34    StackTrace trace;
35    u1 live;
36} StackTraceEntry;
37
38static u4 computeStackTraceHash(const StackTraceEntry *stackTraceEntry);
39
40int
41hprofStartup_Stack()
42{
43    HashIter iter;
44
45    /* This will be called when a GC begins. */
46    for (dvmHashIterBegin(gStackTraceHashTable, &iter);
47         !dvmHashIterDone(&iter);
48         dvmHashIterNext(&iter)) {
49        StackTraceEntry *stackTraceEntry;
50
51        /* Clear the 'live' bit at the start of the GC pass. */
52        stackTraceEntry = (StackTraceEntry *) dvmHashIterData(&iter);
53        stackTraceEntry->live = 0;
54    }
55
56    return 0;
57}
58
59int
60hprofShutdown_Stack()
61{
62    HashIter iter;
63
64    /* This will be called when a GC has completed. */
65    for (dvmHashIterBegin(gStackTraceHashTable, &iter);
66         !dvmHashIterDone(&iter);
67         dvmHashIterNext(&iter)) {
68        StackTraceEntry *stackTraceEntry;
69
70        /*
71         * If the 'live' bit is 0, the trace is not in use by any current
72         * heap object and may be destroyed.
73         */
74        stackTraceEntry = (StackTraceEntry *) dvmHashIterData(&iter);
75        if (!stackTraceEntry->live) {
76            dvmHashTableRemove(gStackTraceHashTable,
77                    computeStackTraceHash(stackTraceEntry), stackTraceEntry);
78            free(stackTraceEntry);
79        }
80    }
81
82    return 0;
83}
84
85static u4
86computeStackTraceHash(const StackTraceEntry *stackTraceEntry)
87{
88    u4 hash = 0;
89    const char *cp = (const char *) &stackTraceEntry->trace;
90    int i;
91
92    for (i = 0; i < (int) sizeof(StackTrace); i++) {
93        hash = hash * 31 + cp[i];
94    }
95
96    return hash;
97}
98
99/* Only compare the 'trace' portion of the StackTraceEntry. */
100static int
101stackCmp(const void *tableItem, const void *looseItem)
102{
103    return memcmp(&((StackTraceEntry *) tableItem)->trace,
104            &((StackTraceEntry *) looseItem)->trace, sizeof(StackTrace));
105}
106
107static StackTraceEntry *
108stackDup(const StackTraceEntry *stackTrace)
109{
110    StackTraceEntry *newStackTrace = malloc(sizeof(StackTraceEntry));
111    memcpy(newStackTrace, stackTrace, sizeof(StackTraceEntry));
112    return newStackTrace;
113}
114
115static u4
116hprofLookupStackSerialNumber(const StackTraceEntry *stackTrace)
117{
118    StackTraceEntry *val;
119    u4 hashValue;
120    int serial;
121
122    /*
123     * Create the hash table on first contact.  We can't do this in
124     * hprofStartupStack, because we have to compute stack trace
125     * serial numbers and place them into object headers before the
126     * rest of hprof is triggered by a GC event.
127     */
128    if (gStackTraceHashTable == NULL) {
129        gStackTraceHashTable = dvmHashTableCreate(512, free);
130    }
131    dvmHashTableLock(gStackTraceHashTable);
132
133    hashValue = computeStackTraceHash(stackTrace);
134    val = dvmHashTableLookup(gStackTraceHashTable, hashValue, (void *)stackTrace,
135            (HashCompareFunc)stackCmp, false);
136    if (val == NULL) {
137        StackTraceEntry *newStackTrace;
138
139        newStackTrace = stackDup(stackTrace);
140        newStackTrace->trace.serialNumber = ++gSerialNumber;
141        val = dvmHashTableLookup(gStackTraceHashTable, hashValue,
142                (void *)newStackTrace, (HashCompareFunc)stackCmp, true);
143        assert(val != NULL);
144    }
145
146    /* Mark the trace as live (in use by an object in the current heap). */
147    val->live = 1;
148
149    /* Grab the serial number before unlocking the table. */
150    serial = val->trace.serialNumber;
151
152    dvmHashTableUnlock(gStackTraceHashTable);
153
154    return serial;
155}
156
157int
158hprofDumpStacks(hprof_context_t *ctx)
159{
160    HashIter iter;
161    hprof_record_t *rec = &ctx->curRec;
162
163    dvmHashTableLock(gStackTraceHashTable);
164
165    for (dvmHashIterBegin(gStackTraceHashTable, &iter);
166         !dvmHashIterDone(&iter);
167         dvmHashIterNext(&iter))
168    {
169        const StackTraceEntry *stackTraceEntry;
170        int count;
171        int i;
172
173        hprofStartNewRecord(ctx, HPROF_TAG_STACK_TRACE, HPROF_TIME);
174
175        stackTraceEntry = (const StackTraceEntry *) dvmHashIterData(&iter);
176        assert(stackTraceEntry != NULL);
177
178        /* STACK TRACE format:
179         *
180         * u4:     serial number for this stack
181         * u4:     serial number for the running thread
182         * u4:     number of frames
183         * [ID]*:  ID for the stack frame
184         */
185        hprofAddU4ToRecord(rec, stackTraceEntry->trace.serialNumber);
186        hprofAddU4ToRecord(rec, stackTraceEntry->trace.threadSerialNumber);
187
188        count = 0;
189        while ((count < STACK_DEPTH) &&
190               (stackTraceEntry->trace.frameIds[count] != 0)) {
191            count++;
192        }
193        hprofAddU4ToRecord(rec, count);
194        for (i = 0; i < count; i++) {
195            hprofAddU4ToRecord(rec, stackTraceEntry->trace.frameIds[i]);
196        }
197    }
198
199    dvmHashTableUnlock(gStackTraceHashTable);
200
201    return 0;
202}
203
204void
205hprofFillInStackTrace(void *objectPtr)
206
207{
208    DvmHeapChunk *chunk;
209    StackTraceEntry stackTraceEntry;
210    Thread* self;
211    void* fp;
212    int i;
213
214    if (objectPtr == NULL) {
215        return;
216    }
217    self = dvmThreadSelf();
218    if (self == NULL) {
219        return;
220    }
221    fp = self->curFrame;
222
223    /* Serial number to be filled in later. */
224    stackTraceEntry.trace.serialNumber = -1;
225
226    /*
227     * TODO - The HAT tool doesn't care about thread data, so we can defer
228     * actually emitting thread records and assigning thread serial numbers.
229     */
230    stackTraceEntry.trace.threadSerialNumber = (int) self;
231
232    memset(&stackTraceEntry.trace.frameIds, 0,
233            sizeof(stackTraceEntry.trace.frameIds));
234
235    i = 0;
236    while ((fp != NULL) && (i < STACK_DEPTH)) {
237        const StackSaveArea* saveArea = SAVEAREA_FROM_FP(fp);
238        const Method* method = saveArea->method;
239        StackFrameEntry frame;
240
241        if (!dvmIsBreakFrame(fp)) {
242            frame.frame.method = method;
243            if (dvmIsNativeMethod(method)) {
244                frame.frame.pc = 0; /* no saved PC for native methods */
245            } else {
246                assert(saveArea->xtra.currentPc >= method->insns &&
247                        saveArea->xtra.currentPc <
248                        method->insns + dvmGetMethodInsnsSize(method));
249                frame.frame.pc = (int) (saveArea->xtra.currentPc -
250                        method->insns);
251            }
252
253            // Canonicalize the frame and cache it in the hprof context
254            stackTraceEntry.trace.frameIds[i++] =
255                hprofLookupStackFrameId(&frame);
256        }
257
258        assert(fp != saveArea->prevFrame);
259        fp = saveArea->prevFrame;
260    }
261
262    /* Store the stack trace serial number in the object header */
263    chunk = ptr2chunk(objectPtr);
264    chunk->stackTraceSerialNumber =
265            hprofLookupStackSerialNumber(&stackTraceEntry);
266}
267