vm/ReferenceTable.cpp

   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(obj != NULL);
  60     assert(dvmIsHeapAddress(obj));
  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             ALOGW("ReferenceTable overflow (max=%d)", 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             ALOGE("Unable to expand ref table (from %d to %d %d-byte entries)",
  82                 pRef->allocEntries, newSize, sizeof(Object*));
  83             return false;
  84         }
  85         LOGVV("Growing %p from %d to %d", 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         //ALOGV("LREF delete %p, shift %d down", obj, moveCount);
 145     } else {
 146         /* last entry, falls off the end */
 147         //ALOGV("LREF delete %p from end", obj);
 148     }
 149
 150     return true;
 151 }
 152
 153 /*
 154  * If "obj" is an array, return the number of elements in the array.
 155  * Otherwise, return zero.
 156  */
 157 static size_t getElementCount(const Object* obj)
 158 {
 159     const ArrayObject* arrayObj = (ArrayObject*) obj;
 160     if (arrayObj == NULL || arrayObj == kClearedJniWeakGlobal ||
 161             arrayObj->clazz == NULL || !dvmIsArray(arrayObj)) {
 162         return 0;
 163     }
 164     return arrayObj->length;
 165 }
 166
 167 /*
 168  * This is a qsort() callback.  We sort Object* by class, allocation size,
 169  * and then by the Object* itself.
 170  */
 171 static int compareObject(const void* vobj1, const void* vobj2)
 172 {
 173     const Object* obj1 = *((Object* const*) vobj1);
 174     const Object* obj2 = *((Object* const*) vobj2);
 175
 176     // Ensure null references and cleared jweaks appear at the end.
 177     if (obj1 == NULL) {
 178         if (obj2 == NULL) {
 179             return 0;
 180         } else {
 181             return 1;
 182         }
 183     } else if (obj2 == NULL) {
 184         return -1;
 185     }
 186     if (obj1 == kClearedJniWeakGlobal) {
 187         if (obj2 == kClearedJniWeakGlobal) {
 188             return 0;
 189         } else {
 190             return 1;
 191         }
 192     } else if (obj2 == kClearedJniWeakGlobal) {
 193         return -1;
 194     }
 195
 196     if (obj1->clazz != obj2->clazz) {
 197         return (u1*)obj1->clazz - (u1*)obj2->clazz;
 198     } else {
 199         size_t count1 = getElementCount(obj1);
 200         size_t count2 = getElementCount(obj2);
 201         if (count1 != count2) {
 202             return count1 - count2;
 203         } else {
 204             return (u1*)obj1 - (u1*)obj2;
 205         }
 206     }
 207 }
 208
 209 /*
 210  * Log an object with some additional info.
 211  *
 212  * Pass in the number of elements in the array (or 0 if this is not an
 213  * array object), and the number of additional objects that are identical
 214  * or equivalent to the original.
 215  */
 216 static void logSummaryLine(const Object* obj, size_t elems, int identical, int equiv)
 217 {
 218     if (obj == NULL) {
 219         ALOGW("    NULL reference (count=%d)", equiv);
 220         return;
 221     }
 222     if (obj == kClearedJniWeakGlobal) {
 223         ALOGW("    cleared jweak (count=%d)", equiv);
 224         return;
 225     }
 226
 227     std::string className(dvmHumanReadableType(obj));
 228     if (obj->clazz == gDvm.classJavaLangClass) {
 229         // We're summarizing multiple instances, so using the exemplar
 230         // Class' type parameter here would be misleading.
 231         className = "java.lang.Class";
 232     }
 233     if (elems != 0) {
 234         StringAppendF(&className, " (%zd elements)", elems);
 235     }
 236
 237     size_t total = identical + equiv + 1;
 238     std::string msg(StringPrintf("%5d of %s", total, className.c_str()));
 239     if (identical + equiv != 0) {
 240         StringAppendF(&msg, " (%d unique instances)", equiv + 1);
 241     }
 242     ALOGW("    %s", msg.c_str());
 243 }
 244
 245 /*
 246  * Dump a summary of an array of references to the log file.
 247  *
 248  * This is used to dump the contents of ReferenceTable and IndirectRefTable
 249  * structs.
 250  */
 251 void dvmDumpReferenceTableContents(Object* const* refs, size_t count,
 252     const char* descr)
 253 {
 254     ALOGW("%s reference table (%p) dump:", descr, refs);
 255
 256     if (count == 0) {
 257         ALOGW("  (empty)");
 258         return;
 259     }
 260
 261     // Dump the most recent N entries.
 262     const size_t kLast = 10;
 263     int first = count - kLast;
 264     if (first < 0) {
 265         first = 0;
 266     }
 267     ALOGW("  Last %d entries (of %d):", (count - first), count);
 268     for (int idx = count - 1; idx >= first; --idx) {
 269         const Object* ref = refs[idx];
 270         if (ref == NULL) {
 271             continue;
 272         }
 273         if (ref == kClearedJniWeakGlobal) {
 274             ALOGW("    %5d: cleared jweak", idx);
 275             continue;
 276         }
 277         if (ref->clazz == NULL) {
 278             // should only be possible right after a plain dvmMalloc().
 279             size_t size = dvmObjectSizeInHeap(ref);
 280             ALOGW("    %5d: %p (raw) (%zd bytes)", idx, ref, size);
 281             continue;
 282         }
 283
 284         std::string className(dvmHumanReadableType(ref));
 285
 286         std::string extras;
 287         size_t elems = getElementCount(ref);
 288         if (elems != 0) {
 289             StringAppendF(&extras, " (%zd elements)", elems);
 290         } else if (ref->clazz == gDvm.classJavaLangString) {
 291             const StringObject* str =
 292                     reinterpret_cast<const StringObject*>(ref);
 293             extras += " \"";
 294             size_t count = 0;
 295             char* s = dvmCreateCstrFromString(str);
 296             char* p = s;
 297             for (; *p && count < 16; ++p, ++count) {
 298                 extras += *p;
 299             }
 300             if (*p == 0) {
 301                 extras += "\"";
 302             } else {
 303                 StringAppendF(&extras, "... (%d chars)", str->length());
 304             }
 305             free(s);
 306         }
 307         ALOGW("    %5d: %p %s%s", idx, ref, className.c_str(), extras.c_str());
 308     }
 309
 310     // Make a copy of the table, and sort it.
 311     Object** tableCopy = (Object**)malloc(sizeof(Object*) * count);
 312     if (tableCopy == NULL) {
 313         ALOGE("Unable to copy table with %d elements", count);
 314         return;
 315     }
 316     memcpy(tableCopy, refs, sizeof(Object*) * count);
 317     qsort(tableCopy, count, sizeof(Object*), compareObject);
 318     refs = tableCopy;       // use sorted list
 319
 320     // Remove any uninteresting stuff from the list. The sort moved them all to the end.
 321     while (count > 0 && refs[count-1] == NULL) {
 322         --count;
 323     }
 324     while (count > 0 && refs[count-1] == kClearedJniWeakGlobal) {
 325         --count;
 326     }
 327     if (count == 0) {
 328         return;
 329     }
 330
 331     // Dump a summary of the whole table.
 332     ALOGW("  Summary:");
 333     size_t equiv, identical;
 334     equiv = identical = 0;
 335     size_t idx;
 336     size_t elems;
 337     for (idx = 1; idx < count; idx++) {
 338         elems = getElementCount(refs[idx-1]);
 339
 340         if (refs[idx] == refs[idx-1]) {
 341             // same reference, added more than once.
 342             identical++;
 343         } else if (refs[idx]->clazz == refs[idx-1]->clazz &&
 344             getElementCount(refs[idx]) == elems)
 345         {
 346             // same class / element count, different object.
 347             equiv++;
 348         } else {
 349             // different class.
 350             logSummaryLine(refs[idx-1], elems, identical, equiv);
 351             equiv = identical = 0;
 352         }
 353     }
 354
 355     // Handle the last entry (everything above outputs refs[i-1]).
 356     elems = getElementCount(refs[idx-1]);
 357     logSummaryLine(refs[count-1], elems, identical, equiv);
 358
 359     free(tableCopy);
 360 }
 361
 362 /*
 363  * Dump the contents of a ReferenceTable to the log.
 364  */
 365 void dvmDumpReferenceTable(const ReferenceTable* pRef, const char* descr)
 366 {
 367     dvmDumpReferenceTableContents(pRef->table, dvmReferenceTableEntries(pRef),
 368         descr);
 369 }