vm/ReferenceTable.c

   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