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 */
dvmInitReferenceTable(ReferenceTable * pRef,int initialCount,int maxCount)25 bool 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 */
dvmClearReferenceTable(ReferenceTable * pRef)47 void 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 */
dvmAddToReferenceTable(ReferenceTable * pRef,Object * obj)57 bool 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)\n", 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)\n",
82 pRef->allocEntries, newSize, sizeof(Object*));
83 return false;
84 }
85 LOGVV("Growing %p from %d to %d\n", 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 */
dvmFindInReferenceTable(const ReferenceTable * pRef,Object ** bottom,Object * obj)100 Object** 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 */
dvmRemoveFromReferenceTable(ReferenceTable * pRef,Object ** bottom,Object * obj)121 bool 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\n", obj, moveCount);
145 } else {
146 /* last entry, falls off the end */
147 //LOGV("LREF delete %p from end\n", obj);
148 }
149
150 return true;
151 }
152
153 /*
154 * This is a qsort() callback. We sort Object* by class, allocation size,
155 * and then by the Object* itself.
156 */
compareObject(const void * vobj1,const void * vobj2)157 static int compareObject(const void* vobj1, const void* vobj2)
158 {
159 Object* obj1 = *((Object**) vobj1);
160 Object* obj2 = *((Object**) vobj2);
161
162 if (obj1 == NULL || obj2 == NULL)
163 return (u1*)obj1 - (u1*)obj2;
164
165 if (obj1->clazz != obj2->clazz) {
166 return (u1*)obj1->clazz - (u1*)obj2->clazz;
167 } else {
168 int size1 = dvmObjectSizeInHeap(obj1);
169 int size2 = dvmObjectSizeInHeap(obj2);
170 if (size1 != size2) {
171 return size1 - size2;
172 } else {
173 return (u1*)obj1 - (u1*)obj2;
174 }
175 }
176 }
177
178 /*
179 * Log an object with some additional info.
180 *
181 * Pass in the number of additional elements that are identical to or
182 * equivalent to the original.
183 */
logObject(Object * obj,int size,int identical,int equiv)184 static void logObject(Object* obj, int size, int identical, int equiv)
185 {
186 if (obj == NULL) {
187 LOGW(" NULL reference (count=%d)\n", equiv);
188 return;
189 }
190
191 /* handle "raw" dvmMalloc case */
192 const char* descriptor =
193 (obj->clazz != NULL) ? obj->clazz->descriptor : "(raw)";
194
195 if (identical + equiv != 0) {
196 LOGW("%5d of %s %dB (%d unique)\n", identical + equiv +1,
197 descriptor, size, equiv +1);
198 } else {
199 LOGW("%5d of %s %dB\n", identical + equiv +1, descriptor, size);
200 }
201 }
202
203 /*
204 * Dump the contents of a ReferenceTable to the log.
205 *
206 * The caller should lock any external sync before calling.
207 *
208 * (This was originally written to be tolerant of null entries in the table.
209 * I don't think that can happen anymore.)
210 */
dvmDumpReferenceTable(const ReferenceTable * pRef,const char * descr)211 void dvmDumpReferenceTable(const ReferenceTable* pRef, const char* descr)
212 {
213 const int kLast = 10;
214 int count = dvmReferenceTableEntries(pRef);
215 Object** refs;
216 int i;
217
218 if (count == 0) {
219 LOGW("%s reference table has no entries\n", descr);
220 return;
221 }
222 assert(count > 0);
223
224 /*
225 * Dump the most recent N entries.
226 */
227 LOGW("Last %d entries in %s reference table:\n", kLast, descr);
228 refs = pRef->table; // use unsorted list
229 int size;
230 int start = count - kLast;
231 if (start < 0)
232 start = 0;
233
234 for (i = start; i < count; i++) {
235 size = (refs[i] == NULL) ? 0 : dvmObjectSizeInHeap(refs[i]);
236 Object* ref = refs[i];
237 if (ref->clazz == gDvm.classJavaLangClass) {
238 ClassObject* clazz = (ClassObject*) ref;
239 LOGW("%5d: %p cls=%s '%s' (%d bytes)\n", i, ref,
240 (refs[i] == NULL) ? "-" : ref->clazz->descriptor,
241 clazz->descriptor, size);
242 } else if (ref->clazz == NULL) {
243 /* should only be possible right after a plain dvmMalloc() */
244 LOGW("%5d: %p cls=(raw) (%d bytes)\n", i, ref, size);
245 } else {
246 LOGW("%5d: %p cls=%s (%d bytes)\n", i, ref,
247 (refs[i] == NULL) ? "-" : ref->clazz->descriptor, size);
248 }
249 }
250
251 /*
252 * Make a copy of the table, and sort it.
253 */
254 Object** tableCopy = (Object**)malloc(sizeof(Object*) * count);
255 memcpy(tableCopy, pRef->table, sizeof(Object*) * count);
256 qsort(tableCopy, count, sizeof(Object*), compareObject);
257 refs = tableCopy; // use sorted list
258
259 /*
260 * Dump uniquified table summary. While we're at it, generate a
261 * cumulative total amount of pinned memory based on the unique entries.
262 */
263 LOGW("%s reference table summary (%d entries):\n", descr, count);
264 int equiv, identical, total;
265 total = equiv = identical = 0;
266 for (i = 1; i < count; i++) {
267 size = (refs[i-1] == NULL) ? 0 : dvmObjectSizeInHeap(refs[i-1]);
268
269 if (refs[i] == refs[i-1]) {
270 /* same reference, added more than once */
271 identical++;
272 } else if (refs[i]->clazz == refs[i-1]->clazz &&
273 (int) dvmObjectSizeInHeap(refs[i]) == size)
274 {
275 /* same class / size, different object */
276 total += size;
277 equiv++;
278 } else {
279 /* different class */
280 total += size;
281 logObject(refs[i-1], size, identical, equiv);
282 equiv = identical = 0;
283 }
284 }
285
286 /* handle the last entry (everything above outputs refs[i-1]) */
287 size = (refs[count-1] == NULL) ? 0 : dvmObjectSizeInHeap(refs[count-1]);
288 total += size;
289 logObject(refs[count-1], size, identical, equiv);
290
291 LOGW("Memory held directly by tracked refs is %d bytes\n", total);
292 free(tableCopy);
293 }
294