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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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