Home | History | Annotate | Download | only in vm 
      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 }
    370