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  * Reference table management.
  18  */
  19 #include "Dalvik.h"
  20
  21 /*
  22  * Initialize a ReferenceTable structure.
  23  */
  24 bool dvmInitReferenceTable(ReferenceTable* pRef, int initialCount,
  25     int maxCount)
  26 {
  27     assert(initialCount > 0);
  28     assert(initialCount <= maxCount);
  29
  30     pRef->table = (Object**) malloc(initialCount * sizeof(Object*));
  31     if (pRef->table == NULL)
  32         return false;
  33 #ifndef NDEBUG
  34     memset(pRef->table, 0xdd, initialCount * sizeof(Object*));
  35 #endif
  36     pRef->nextEntry = pRef->table;
  37     pRef->allocEntries = initialCount;
  38     pRef->maxEntries = maxCount;
  39
  40     return true;
  41 }
  42
  43 /*
  44  * Clears out the contents of a ReferenceTable, freeing allocated storage.
  45  */
  46 void dvmClearReferenceTable(ReferenceTable* pRef)
  47 {
  48     free(pRef->table);
  49     pRef->table = pRef->nextEntry = NULL;
  50     pRef->allocEntries = pRef->maxEntries = -1;
  51 }
  52
  53 /*
  54  * Add "obj" to "pRef".
  55  */
  56 bool dvmAddToReferenceTable(ReferenceTable* pRef, Object* obj)
  57 {
  58     assert(dvmIsValidObject(obj));
  59     assert(obj != NULL);
  60     assert(pRef->table != NULL);
  61
  62     if (pRef->nextEntry == pRef->table + pRef->maxEntries) {
  63         LOGW("ReferenceTable overflow (max=%d)\n", pRef->maxEntries);
  64         return false;
  65     } else if (pRef->nextEntry == pRef->table + pRef->allocEntries) {
  66         Object** newTable;
  67         int newSize;
  68
  69         newSize = pRef->allocEntries * 2;
  70         if (newSize > pRef->maxEntries)
  71             newSize = pRef->maxEntries;
  72         assert(newSize > pRef->allocEntries);
  73
  74         newTable = (Object**) realloc(pRef->table, newSize * sizeof(Object*));
  75         if (newTable == NULL) {
  76             LOGE("Unable to expand ref table (from %d to %d %d-byte entries)\n",
  77                 pRef->allocEntries, newSize, sizeof(Object*));
  78             return false;
  79         }
  80         LOGVV("Growing %p from %d to %d\n", pRef, pRef->allocEntries, newSize);
  81
  82         /* update entries; adjust "nextEntry" in case memory moved */
  83         pRef->nextEntry = newTable + (pRef->nextEntry - pRef->table);
  84         pRef->table = newTable;
  85         pRef->allocEntries = newSize;
  86     }
  87
  88     *pRef->nextEntry++ = obj;
  89     return true;
  90 }
  91
  92 /*
  93  * Returns NULL if not found.
  94  */
  95 Object** dvmFindInReferenceTable(const ReferenceTable* pRef, Object** top,
  96     Object* obj)
  97 {
  98     Object** ptr;
  99
 100     ptr = pRef->nextEntry;
 101     while (--ptr >= top) {
 102         if (*ptr == obj)
 103             return ptr;
 104     }
 105     return NULL;
 106 }
 107
 108 /*
 109  * Remove "obj" from "pRef".  We start at the end of the list (where the
 110  * most-recently-added element is), and stop searching for a match after
 111  * examining the element at "top".
 112  *
 113  * Most of the time "obj" is at or near the end of the list.  If not, we
 114  * compact it down.
 115  */
 116 bool dvmRemoveFromReferenceTable(ReferenceTable* pRef, Object** top,
 117     Object* obj)
 118 {
 119     Object** ptr;
 120
 121     assert(pRef->table != NULL);
 122
 123     /*
 124      * Scan from the most-recently-added entry up to the top entry for
 125      * this frame.
 126      */
 127     ptr = dvmFindInReferenceTable(pRef, top, obj);
 128     if (ptr == NULL)
 129         return false;
 130
 131     /*
 132      * Delete the entry.
 133      */
 134     pRef->nextEntry--;
 135     int moveCount = pRef->nextEntry - ptr;
 136     if (moveCount != 0) {
 137         /* remove from middle, slide the rest down */
 138         memmove(ptr, ptr+1, moveCount * sizeof(Object*));
 139         //LOGV("LREF delete %p, shift %d down\n", obj, moveCount);
 140     } else {
 141         /* last entry, falls off the end */
 142         //LOGV("LREF delete %p from end\n", obj);
 143     }
 144
 145     return true;
 146 }
 147
 148 /*
 149  * This is a qsort() callback.  We sort Object* by class, allocation size,
 150  * and then by the Object* itself.
 151  */
 152 static int compareObject(const void* vobj1, const void* vobj2)
 153 {
 154     Object* obj1 = *((Object**) vobj1);
 155     Object* obj2 = *((Object**) vobj2);
 156
 157     if (obj1 == NULL || obj2 == NULL)
 158         return (u1*)obj1 - (u1*)obj2;
 159
 160     if (obj1->clazz != obj2->clazz) {
 161         return (u1*)obj1->clazz - (u1*)obj2->clazz;
 162     } else {
 163         int size1 = dvmObjectSizeInHeap(obj1);
 164         int size2 = dvmObjectSizeInHeap(obj2);
 165         if (size1 != size2) {
 166             return size1 - size2;
 167         } else {
 168             return (u1*)obj1 - (u1*)obj2;
 169         }
 170     }
 171 }
 172
 173 /*
 174  * Log an object with some additional info.
 175  *
 176  * Pass in the number of additional elements that are identical to or
 177  * equivalent to the original.
 178  */
 179 static void logObject(Object* obj, int size, int identical, int equiv)
 180 {
 181     if (obj == NULL) {
 182         LOGW("  NULL reference (count=%d)\n", equiv);
 183         return;
 184     }
 185
 186     if (identical + equiv != 0) {
 187         LOGW("%5d of %s %dB (%d unique)\n", identical + equiv +1,
 188             obj->clazz->descriptor, size, equiv +1);
 189     } else {
 190         LOGW("%5d of %s %dB\n", identical + equiv +1,
 191             obj->clazz->descriptor, size);
 192     }
 193 }
 194
 195 /*
 196  * Dump the contents of a ReferenceTable to the log.
 197  *
 198  * The caller should lock any external sync before calling.
 199  *
 200  * (This was originally written to be tolerant of null entries in the table.
 201  * I don't think that can happen anymore.)
 202  */
 203 void dvmDumpReferenceTable(const ReferenceTable* pRef, const char* descr)
 204 {
 205     const int kLast = 10;
 206     int count = dvmReferenceTableEntries(pRef);
 207     Object** refs;
 208     int i;
 209
 210     if (count == 0) {
 211         LOGW("Reference table has no entries\n");
 212         return;
 213     }
 214     assert(count > 0);
 215
 216     /*
 217      * Dump the most recent N entries.
 218      */
 219     LOGW("Last %d entries in %s reference table:\n", kLast, descr);
 220     refs = pRef->table;         // use unsorted list
 221     int size;
 222     int start = count - kLast;
 223     if (start < 0)
 224         start = 0;
 225
 226     for (i = start; i < count; i++) {
 227         size = (refs[i] == NULL) ? 0 : dvmObjectSizeInHeap(refs[i]);
 228         Object* ref = refs[i];
 229         if (ref->clazz == gDvm.classJavaLangClass) {
 230             ClassObject* clazz = (ClassObject*) ref;
 231             LOGW("%5d: %p cls=%s '%s' (%d bytes)\n", i, ref,
 232                 (refs[i] == NULL) ? "-" : ref->clazz->descriptor,
 233                 clazz->descriptor, size);
 234         } else {
 235             LOGW("%5d: %p cls=%s (%d bytes)\n", i, ref,
 236                 (refs[i] == NULL) ? "-" : ref->clazz->descriptor, size);
 237         }
 238     }
 239
 240     /*
 241      * Make a copy of the table, and sort it.
 242      */
 243     Object** tableCopy = (Object**)malloc(sizeof(Object*) * count);
 244     memcpy(tableCopy, pRef->table, sizeof(Object*) * count);
 245     qsort(tableCopy, count, sizeof(Object*), compareObject);
 246     refs = tableCopy;       // use sorted list
 247
 248     /*
 249      * Dump uniquified table summary.  While we're at it, generate a
 250      * cumulative total amount of pinned memory based on the unique entries.
 251      */
 252     LOGW("%s reference table summary (%d entries):\n", descr, count);
 253     int equiv, identical, total;
 254     total = equiv = identical = 0;
 255     for (i = 1; i < count; i++) {
 256         size = (refs[i-1] == NULL) ? 0 : dvmObjectSizeInHeap(refs[i-1]);
 257
 258         if (refs[i] == refs[i-1]) {
 259             /* same reference, added more than once */
 260             identical++;
 261         } else if (refs[i]->clazz == refs[i-1]->clazz &&
 262             (int) dvmObjectSizeInHeap(refs[i]) == size)
 263         {
 264             /* same class / size, different object */
 265             total += size;
 266             equiv++;
 267         } else {
 268             /* different class */
 269             total += size;
 270             logObject(refs[i-1], size, identical, equiv);
 271             equiv = identical = 0;
 272         }
 273     }
 274
 275     /* handle the last entry (everything above outputs refs[i-1]) */
 276     size = (refs[count-1] == NULL) ? 0 : dvmObjectSizeInHeap(refs[count-1]);
 277     total += size;
 278     logObject(refs[count-1], size, identical, equiv);
 279
 280     LOGW("Memory held directly by native code is %d bytes\n", total);
 281     free(tableCopy);
 282 }
 283