1/*
2 * Copyright (C) 2010 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 "Dalvik.h"
18#include "alloc/clz.h"
19#include "alloc/HeapInternal.h"
20#include "alloc/Visit.h"
21#include "alloc/VisitInlines.h"
22
23/*
24 * Visits all of the reference locations in an object.
25 */
26void dvmVisitObject(Visitor *visitor, Object *obj, void *arg)
27{
28    assert(visitor != NULL);
29    assert(obj != NULL);
30    assert(obj->clazz != NULL);
31    visitObject(visitor, obj, arg);
32}
33
34/*
35 * Applies a verification function to all present values in the hash table.
36 */
37static void visitHashTable(Visitor *visitor, HashTable *table, void *arg)
38{
39    int i;
40
41    assert(visitor != NULL);
42    assert(table != NULL);
43    dvmHashTableLock(table);
44    for (i = 0; i < table->tableSize; ++i) {
45        HashEntry *entry = &table->pEntries[i];
46        if (entry->data != NULL && entry->data != HASH_TOMBSTONE) {
47            (*visitor)(&entry->data, arg);
48        }
49    }
50    dvmHashTableUnlock(table);
51}
52
53/*
54 * Visits all entries in the reference table.
55 */
56static void visitReferenceTable(Visitor *visitor, const ReferenceTable *table,
57                                void *arg)
58{
59    Object **entry;
60
61    assert(visitor != NULL);
62    assert(table != NULL);
63    for (entry = table->table; entry < table->nextEntry; ++entry) {
64        assert(entry != NULL);
65        (*visitor)(entry, arg);
66    }
67}
68
69/*
70 * Visits a large heap reference table.  These objects are list heads.
71 * As such, it is valid for table to be NULL.
72 */
73static void visitLargeHeapRefTable(Visitor *visitor, LargeHeapRefTable *table,
74                                   void *arg)
75{
76    assert(visitor != NULL);
77    for (; table != NULL; table = table->next) {
78        visitReferenceTable(visitor, &table->refs, arg);
79    }
80}
81
82/*
83 * Visits all stack slots. TODO: visit native methods.
84 */
85static void visitThreadStack(Visitor *visitor, Thread *thread, void *arg)
86{
87    const StackSaveArea *saveArea;
88    u4 *framePtr;
89
90    assert(visitor != NULL);
91    assert(thread != NULL);
92    framePtr = (u4 *)thread->curFrame;
93    for (; framePtr != NULL; framePtr = saveArea->prevFrame) {
94        Method *method;
95        saveArea = SAVEAREA_FROM_FP(framePtr);
96        method = (Method *)saveArea->method;
97        if (method != NULL && !dvmIsNativeMethod(method)) {
98            const RegisterMap* pMap = dvmGetExpandedRegisterMap(method);
99            const u1* regVector = NULL;
100            size_t i;
101
102            if (pMap != NULL) {
103                /* found map, get registers for this address */
104                int addr = saveArea->xtra.currentPc - method->insns;
105                regVector = dvmRegisterMapGetLine(pMap, addr);
106            }
107            if (regVector == NULL) {
108                /*
109                 * Either there was no register map or there is no
110                 * info for the current PC.  Perform a conservative
111                 * scan.
112                 */
113                for (i = 0; i < method->registersSize; ++i) {
114                    if (dvmIsValidObject((Object *)framePtr[i])) {
115                        (*visitor)(&framePtr[i], arg);
116                    }
117                }
118            } else {
119                /*
120                 * Precise scan.  v0 is at the lowest address on the
121                 * interpreted stack, and is the first bit in the
122                 * register vector, so we can walk through the
123                 * register map and memory in the same direction.
124                 *
125                 * A '1' bit indicates a live reference.
126                 */
127                u2 bits = 1 << 1;
128                for (i = 0; i < method->registersSize; ++i) {
129                    bits >>= 1;
130                    if (bits == 1) {
131                        /* set bit 9 so we can tell when we're empty */
132                        bits = *regVector++ | 0x0100;
133                    }
134                    if ((bits & 0x1) != 0) {
135                        /*
136                         * Register is marked as live, it's a valid root.
137                         */
138                        (*visitor)(&framePtr[i], arg);
139                    }
140                }
141                dvmReleaseRegisterMapLine(pMap, regVector);
142            }
143        }
144        /*
145         * Don't fall into an infinite loop if things get corrupted.
146         */
147        assert((uintptr_t)saveArea->prevFrame > (uintptr_t)framePtr ||
148               saveArea->prevFrame == NULL);
149    }
150}
151
152/*
153 * Visits all roots associated with a thread.
154 */
155static void visitThread(Visitor *visitor, Thread *thread, void *arg)
156{
157    assert(visitor != NULL);
158    assert(thread != NULL);
159    (*visitor)(&thread->threadObj, arg);
160    (*visitor)(&thread->exception, arg);
161    visitReferenceTable(visitor, &thread->internalLocalRefTable, arg);
162    visitReferenceTable(visitor, &thread->jniLocalRefTable, arg);
163    if (thread->jniMonitorRefTable.table) {
164        visitReferenceTable(visitor, &thread->jniMonitorRefTable, arg);
165    }
166    visitThreadStack(visitor, thread, arg);
167}
168
169/*
170 * Visits all threads on the thread list.
171 */
172static void visitThreads(Visitor *visitor, void *arg)
173{
174    Thread *thread;
175
176    assert(visitor != NULL);
177    dvmLockThreadList(dvmThreadSelf());
178    thread = gDvm.threadList;
179    while (thread) {
180        visitThread(visitor, thread, arg);
181        thread = thread->next;
182    }
183    dvmUnlockThreadList();
184}
185
186/*
187 * Visits roots.  TODO: visit all roots.
188 */
189void dvmVisitRoots(Visitor *visitor, void *arg)
190{
191    assert(visitor != NULL);
192    visitHashTable(visitor, gDvm.loadedClasses, arg);
193    visitHashTable(visitor, gDvm.dbgRegistry, arg);
194    visitHashTable(visitor, gDvm.internedStrings, arg);
195    visitHashTable(visitor, gDvm.literalStrings, arg);
196    visitReferenceTable(visitor, &gDvm.jniGlobalRefTable, arg);
197    visitReferenceTable(visitor, &gDvm.jniPinRefTable, arg);
198    visitLargeHeapRefTable(visitor, gDvm.gcHeap->referenceOperations, arg);
199    visitLargeHeapRefTable(visitor, gDvm.gcHeap->pendingFinalizationRefs, arg);
200    visitThreads(visitor, arg);
201    (*visitor)(&gDvm.outOfMemoryObj, arg);
202    (*visitor)(&gDvm.internalErrorObj, arg);
203    (*visitor)(&gDvm.noClassDefFoundErrorObj, arg);
204    /* TODO: visit cached global references. */
205}
206