vm/AllocTracker.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  * Allocation tracking and reporting.  We maintain a circular buffer with
  18  * the most recent allocations.  The data can be viewed through DDMS.
  19  *
  20  * There are two basic approaches: manage the buffer with atomic updates
  21  * and do a system-wide suspend when DDMS requests it, or protect all
  22  * accesses with a mutex.  The former is potentially more efficient, but
  23  * the latter is much simpler and more reliable.
  24  *
  25  * Ideally we'd just use the object heap allocation mutex to guard this
  26  * structure, but at the point we grab that (under dvmMalloc()) we're just
  27  * allocating a collection of bytes and no longer have the class reference.
  28  * Because this is an optional feature it's best to leave the existing
  29  * code undisturbed and just use an additional lock.
  30  *
  31  * We don't currently track allocations of class objects.  We could, but
  32  * with the possible exception of Proxy objects they're not that interesting.
  33  *
  34  * TODO: if we add support for class unloading, we need to add the class
  35  * references here to the root set (or just disable class unloading while
  36  * this is active).
  37  *
  38  * TODO: consider making the parameters configurable, so DDMS can decide
  39  * how many allocations it wants to see and what the stack depth should be.
  40  */
  41 #include "Dalvik.h"
  42
  43 #define kMaxAllocRecordStackDepth   8       /* max 255 */
  44 #define kNumAllocRecords            512     /* MUST be power of 2 */
  45
  46 /*
  47  * Record the details of an allocation.
  48  */
  49 struct AllocRecord {
  50     ClassObject*    clazz;      /* class allocated in this block */
  51     u4              size;       /* total size requested */
  52     u2              threadId;   /* simple thread ID; could be recycled */
  53
  54     /* stack trace elements; unused entries have method==NULL */
  55     struct {
  56         const Method* method;   /* which method we're executing in */
  57         int         pc;         /* current execution offset, in 16-bit units */
  58     } stackElem[kMaxAllocRecordStackDepth];
  59
  60     /*
  61      * This was going to be either wall-clock time in seconds or monotonic
  62      * time in milliseconds since the VM started, to give a rough sense for
  63      * how long ago an allocation happened.  This adds a system call per
  64      * allocation, which is too much overhead.
  65      */
  66     //u4      timestamp;
  67 };
  68
  69 /*
  70  * Initialize a few things.  This gets called early, so keep activity to
  71  * a minimum.
  72  */
  73 bool dvmAllocTrackerStartup(void)
  74 {
  75     /* prep locks */
  76     dvmInitMutex(&gDvm.allocTrackerLock);
  77
  78     /* initialized when enabled by DDMS */
  79     assert(gDvm.allocRecords == NULL);
  80
  81     return true;
  82 }
  83
  84 /*
  85  * Release anything we're holding on to.
  86  */
  87 void dvmAllocTrackerShutdown(void)
  88 {
  89     free(gDvm.allocRecords);
  90     dvmDestroyMutex(&gDvm.allocTrackerLock);
  91 }
  92
  93
  94 /*
  95  * ===========================================================================
  96  *      Collection
  97  * ===========================================================================
  98  */
  99
 100 /*
 101  * Enable allocation tracking.  Does nothing if tracking is already enabled.
 102  *
 103  * Returns "true" on success.
 104  */
 105 bool dvmEnableAllocTracker(void)
 106 {
 107     bool result = true;
 108     dvmLockMutex(&gDvm.allocTrackerLock);
 109
 110     if (gDvm.allocRecords == NULL) {
 111         LOGI("Enabling alloc tracker (%d entries / %d bytes)\n",
 112             kNumAllocRecords, sizeof(AllocRecord) * kNumAllocRecords);
 113         gDvm.allocRecordHead = gDvm.allocRecordCount = 0;
 114         gDvm.allocRecords =
 115             (AllocRecord*) malloc(sizeof(AllocRecord) * kNumAllocRecords);
 116
 117         if (gDvm.allocRecords == NULL)
 118             result = false;
 119     }
 120
 121     dvmUnlockMutex(&gDvm.allocTrackerLock);
 122     return result;
 123 }
 124
 125 /*
 126  * Disable allocation tracking.  Does nothing if tracking is not enabled.
 127  */
 128 void dvmDisableAllocTracker(void)
 129 {
 130     dvmLockMutex(&gDvm.allocTrackerLock);
 131
 132     if (gDvm.allocRecords != NULL) {
 133         free(gDvm.allocRecords);
 134         gDvm.allocRecords = NULL;
 135     }
 136
 137     dvmUnlockMutex(&gDvm.allocTrackerLock);
 138 }
 139
 140 /*
 141  * Get the last few stack frames.
 142  */
 143 static void getStackFrames(Thread* self, AllocRecord* pRec)
 144 {
 145     int stackDepth = 0;
 146     void* fp;
 147
 148     fp = self->curFrame;
 149
 150     while ((fp != NULL) && (stackDepth < kMaxAllocRecordStackDepth)) {
 151         const StackSaveArea* saveArea = SAVEAREA_FROM_FP(fp);
 152         const Method* method = saveArea->method;
 153
 154         if (!dvmIsBreakFrame(fp)) {
 155             pRec->stackElem[stackDepth].method = method;
 156             if (dvmIsNativeMethod(method)) {
 157                 pRec->stackElem[stackDepth].pc = 0;
 158             } else {
 159                 assert(saveArea->xtra.currentPc >= method->insns &&
 160                         saveArea->xtra.currentPc <
 161                         method->insns + dvmGetMethodInsnsSize(method));
 162                 pRec->stackElem[stackDepth].pc =
 163                     (int) (saveArea->xtra.currentPc - method->insns);
 164             }
 165             stackDepth++;
 166         }
 167
 168         assert(fp != saveArea->prevFrame);
 169         fp = saveArea->prevFrame;
 170     }
 171
 172     /* clear out the rest (normally there won't be any) */
 173     while (stackDepth < kMaxAllocRecordStackDepth) {
 174         pRec->stackElem[stackDepth].method = NULL;
 175         pRec->stackElem[stackDepth].pc = 0;
 176         stackDepth++;
 177     }
 178 }
 179
 180 /*
 181  * Add a new allocation to the set.
 182  */
 183 void dvmDoTrackAllocation(ClassObject* clazz, int size)
 184 {
 185     dvmLockMutex(&gDvm.allocTrackerLock);
 186     if (gDvm.allocRecords == NULL)
 187         goto bail;
 188
 189     Thread* self = dvmThreadSelf();
 190     if (self == NULL) {
 191         LOGW("alloc tracker: no thread\n");
 192         goto bail;
 193     }
 194
 195     /* advance and clip */
 196     if (++gDvm.allocRecordHead == kNumAllocRecords)
 197         gDvm.allocRecordHead = 0;
 198
 199     AllocRecord* pRec = &gDvm.allocRecords[gDvm.allocRecordHead];
 200
 201     pRec->clazz = clazz;
 202     pRec->size = size;
 203     pRec->threadId = self->threadId;
 204     getStackFrames(self, pRec);
 205
 206     if (gDvm.allocRecordCount < kNumAllocRecords)
 207         gDvm.allocRecordCount++;
 208
 209 bail:
 210     dvmUnlockMutex(&gDvm.allocTrackerLock);
 211 }
 212
 213
 214 /*
 215  * ===========================================================================
 216  *      Reporting
 217  * ===========================================================================
 218  */
 219
 220 /*
 221 The data we send to DDMS contains everything we have recorded.
 222
 223 Message header (all values big-endian):
 224   (1b) message header len (to allow future expansion); includes itself
 225   (1b) entry header len
 226   (1b) stack frame len
 227   (2b) number of entries
 228   (4b) offset to string table from start of message
 229   (2b) number of class name strings
 230   (2b) number of method name strings
 231   (2b) number of source file name strings
 232   For each entry:
 233     (4b) total allocation size
 234     (2b) threadId
 235     (2b) allocated object's class name index
 236     (1b) stack depth
 237     For each stack frame:
 238       (2b) method's class name
 239       (2b) method name
 240       (2b) method source file
 241       (2b) line number, clipped to 32767; -2 if native; -1 if no source
 242   (xb) class name strings
 243   (xb) method name strings
 244   (xb) source file strings
 245
 246   As with other DDM traffic, strings are sent as a 4-byte length
 247   followed by UTF-16 data.
 248
 249 We send up 16-bit unsigned indexes into string tables.  In theory there
 250 can be (kMaxAllocRecordStackDepth * kNumAllocRecords) unique strings in
 251 each table, but in practice there should be far fewer.
 252
 253 The chief reason for using a string table here is to keep the size of
 254 the DDMS message to a minimum.  This is partly to make the protocol
 255 efficient, but also because we have to form the whole thing up all at
 256 once in a memory buffer.
 257
 258 We use separate string tables for class names, method names, and source
 259 files to keep the indexes small.  There will generally be no overlap
 260 between the contents of these tables.
 261 */
 262 const int kMessageHeaderLen = 15;
 263 const int kEntryHeaderLen = 9;
 264 const int kStackFrameLen = 8;
 265
 266 /*
 267  * Return the index of the head element.
 268  *
 269  * We point at the most-recently-written record, so if allocRecordCount is 1
 270  * we want to use the current element.  Take "head+1" and subtract count
 271  * from it.
 272  *
 273  * We need to handle underflow in our circular buffer, so we add
 274  * kNumAllocRecords and then mask it back down.
 275  */
 276 inline static int headIndex(void)
 277 {
 278     return (gDvm.allocRecordHead+1 + kNumAllocRecords - gDvm.allocRecordCount)
 279         & (kNumAllocRecords-1);
 280 }
 281
 282 /*
 283  * Dump the contents of a PointerSet full of character pointers.
 284  */
 285 static void dumpStringTable(PointerSet* strings)
 286 {
 287     int count = dvmPointerSetGetCount(strings);
 288     int i;
 289
 290     for (i = 0; i < count; i++)
 291         printf("  %s\n", (const char*) dvmPointerSetGetEntry(strings, i));
 292 }
 293
 294 /*
 295  * Get the method's source file.  If we don't know it, return "" instead
 296  * of a NULL pointer.
 297  */
 298 static const char* getMethodSourceFile(const Method* method)
 299 {
 300     const char* fileName = dvmGetMethodSourceFile(method);
 301     if (fileName == NULL)
 302         fileName = "";
 303     return fileName;
 304 }
 305
 306 /*
 307  * Generate string tables.
 308  *
 309  * Our source material is UTF-8 string constants from DEX files.  If we
 310  * want to be thorough we can generate a hash value for each string and
 311  * use the VM hash table implementation, or we can do a quick & dirty job
 312  * by just maintaining a list of unique pointers.  If the same string
 313  * constant appears in multiple DEX files we'll end up with duplicates,
 314  * but in practice this shouldn't matter (and if it does, we can uniq-sort
 315  * the result in a second pass).
 316  */
 317 static bool populateStringTables(PointerSet* classNames,
 318     PointerSet* methodNames, PointerSet* fileNames)
 319 {
 320     int count = gDvm.allocRecordCount;
 321     int idx = headIndex();
 322     int classCount, methodCount, fileCount;         /* debug stats */
 323
 324     classCount = methodCount = fileCount = 0;
 325
 326     while (count--) {
 327         AllocRecord* pRec = &gDvm.allocRecords[idx];
 328
 329         dvmPointerSetAddEntry(classNames, pRec->clazz->descriptor);
 330         classCount++;
 331
 332         int i;
 333         for (i = 0; i < kMaxAllocRecordStackDepth; i++) {
 334             if (pRec->stackElem[i].method == NULL)
 335                 break;
 336
 337             const Method* method = pRec->stackElem[i].method;
 338             dvmPointerSetAddEntry(classNames, method->clazz->descriptor);
 339             classCount++;
 340             dvmPointerSetAddEntry(methodNames, method->name);
 341             methodCount++;
 342             dvmPointerSetAddEntry(fileNames, getMethodSourceFile(method));
 343             fileCount++;
 344         }
 345
 346         idx = (idx + 1) & (kNumAllocRecords-1);
 347     }
 348
 349     LOGI("class %d/%d, method %d/%d, file %d/%d\n",
 350         dvmPointerSetGetCount(classNames), classCount,
 351         dvmPointerSetGetCount(methodNames), methodCount,
 352         dvmPointerSetGetCount(fileNames), fileCount);
 353
 354     return true;
 355 }
 356
 357 /*
 358  * Generate the base info (i.e. everything but the string tables).
 359  *
 360  * This should be called twice.  On the first call, "ptr" is NULL and
 361  * "baseLen" is zero.  The return value is used to allocate a buffer.
 362  * On the second call, "ptr" points to a data buffer, and "baseLen"
 363  * holds the value from the result of the first call.
 364  *
 365  * The size of the output data is returned.
 366  */
 367 static size_t generateBaseOutput(u1* ptr, size_t baseLen,
 368     const PointerSet* classNames, const PointerSet* methodNames,
 369     const PointerSet* fileNames)
 370 {
 371     u1* origPtr = ptr;
 372     int count = gDvm.allocRecordCount;
 373     int idx = headIndex();
 374
 375     if (origPtr != NULL) {
 376         set1(&ptr[0], kMessageHeaderLen);
 377         set1(&ptr[1], kEntryHeaderLen);
 378         set1(&ptr[2], kStackFrameLen);
 379         set2BE(&ptr[3], count);
 380         set4BE(&ptr[5], baseLen);
 381         set2BE(&ptr[9], dvmPointerSetGetCount(classNames));
 382         set2BE(&ptr[11], dvmPointerSetGetCount(methodNames));
 383         set2BE(&ptr[13], dvmPointerSetGetCount(fileNames));
 384     }
 385     ptr += kMessageHeaderLen;
 386
 387     while (count--) {
 388         AllocRecord* pRec = &gDvm.allocRecords[idx];
 389
 390         /* compute depth */
 391         int  depth;
 392         for (depth = 0; depth < kMaxAllocRecordStackDepth; depth++) {
 393             if (pRec->stackElem[depth].method == NULL)
 394                 break;
 395         }
 396
 397         /* output header */
 398         if (origPtr != NULL) {
 399             set4BE(&ptr[0], pRec->size);
 400             set2BE(&ptr[4], pRec->threadId);
 401             set2BE(&ptr[6],
 402                 dvmPointerSetFind(classNames, pRec->clazz->descriptor));
 403             set1(&ptr[8], depth);
 404         }
 405         ptr += kEntryHeaderLen;
 406
 407         /* convert stack frames */
 408         int i;
 409         for (i = 0; i < depth; i++) {
 410             if (origPtr != NULL) {
 411                 const Method* method = pRec->stackElem[i].method;
 412                 int lineNum;
 413
 414                 lineNum = dvmLineNumFromPC(method, pRec->stackElem[i].pc);
 415                 if (lineNum > 32767)
 416                     lineNum = 32767;
 417
 418                 set2BE(&ptr[0], dvmPointerSetFind(classNames,
 419                         method->clazz->descriptor));
 420                 set2BE(&ptr[2], dvmPointerSetFind(methodNames,
 421                         method->name));
 422                 set2BE(&ptr[4], dvmPointerSetFind(fileNames,
 423                         getMethodSourceFile(method)));
 424                 set2BE(&ptr[6], (u2)lineNum);
 425             }
 426             ptr += kStackFrameLen;
 427         }
 428
 429         idx = (idx + 1) & (kNumAllocRecords-1);
 430     }
 431
 432     return ptr - origPtr;
 433 }
 434
 435 /*
 436  * Compute the size required to store a string table.  Includes the length
 437  * word and conversion to UTF-16.
 438  */
 439 static size_t computeStringTableSize(PointerSet* strings)
 440 {
 441     int count = dvmPointerSetGetCount(strings);
 442     size_t size = 0;
 443     int i;
 444
 445     for (i = 0; i < count; i++) {
 446         const char* str = (const char*) dvmPointerSetGetEntry(strings, i);
 447
 448         size += 4 + dvmUtf8Len(str) * 2;
 449     }
 450
 451     return size;
 452 }
 453
 454 /*
 455  * Convert a UTF-8 string to UTF-16.  We also need to byte-swap the values
 456  * to big-endian, and we can't assume even alignment on the target.
 457  *
 458  * Returns the string's length, in characters.
 459  */
 460 int convertUtf8ToUtf16BEUA(u1* utf16Str, const char* utf8Str)
 461 {
 462     u1* origUtf16Str = utf16Str;
 463
 464     while (*utf8Str != '\0') {
 465         u2 utf16 = dexGetUtf16FromUtf8(&utf8Str);       /* advances utf8Str */
 466         set2BE(utf16Str, utf16);
 467         utf16Str += 2;
 468     }
 469
 470     return (utf16Str - origUtf16Str) / 2;
 471 }
 472
 473 /*
 474  * Output a string table serially.
 475  */
 476 static size_t outputStringTable(PointerSet* strings, u1* ptr)
 477 {
 478     int count = dvmPointerSetGetCount(strings);
 479     u1* origPtr = ptr;
 480     int i;
 481
 482     for (i = 0; i < count; i++) {
 483         const char* str = (const char*) dvmPointerSetGetEntry(strings, i);
 484         int charLen;
 485
 486         /* copy UTF-8 string to big-endian unaligned UTF-16 */
 487         charLen = convertUtf8ToUtf16BEUA(&ptr[4], str);
 488         set4BE(&ptr[0], charLen);
 489
 490         ptr += 4 + charLen * 2;
 491     }
 492
 493     return ptr - origPtr;
 494 }
 495
 496 /*
 497  * Generate a DDM packet with all of the tracked allocation data.
 498  *
 499  * On success, returns "true" with "*pData" and "*pDataLen" set.
 500  */
 501 bool dvmGenerateTrackedAllocationReport(u1** pData, size_t* pDataLen)
 502 {
 503     bool result = false;
 504     u1* buffer = NULL;
 505
 506     dvmLockMutex(&gDvm.allocTrackerLock);
 507
 508     /*
 509      * Part 1: generate string tables.
 510      */
 511     PointerSet* classNames = NULL;
 512     PointerSet* methodNames = NULL;
 513     PointerSet* fileNames = NULL;
 514
 515     /*
 516      * Allocate storage.  Usually there's 60-120 of each thing (sampled
 517      * when max=512), but it varies widely and isn't closely bound to
 518      * the number of allocations we've captured.  The sets expand quickly
 519      * if needed.
 520      */
 521     classNames = dvmPointerSetAlloc(128);
 522     methodNames = dvmPointerSetAlloc(128);
 523     fileNames = dvmPointerSetAlloc(128);
 524     if (classNames == NULL || methodNames == NULL || fileNames == NULL) {
 525         LOGE("Failed allocating pointer sets\n");
 526         goto bail;
 527     }
 528
 529     if (!populateStringTables(classNames, methodNames, fileNames))
 530         goto bail;
 531
 532     if (false) {
 533         printf("Classes:\n");
 534         dumpStringTable(classNames);
 535         printf("Methods:\n");
 536         dumpStringTable(methodNames);
 537         printf("Files:\n");
 538         dumpStringTable(fileNames);
 539     }
 540
 541     /*
 542      * Part 2: compute the size of the output.
 543      *
 544      * (Could also just write to an expanding buffer.)
 545      */
 546     size_t baseSize, totalSize;
 547     baseSize = generateBaseOutput(NULL, 0, classNames, methodNames, fileNames);
 548     assert(baseSize > 0);
 549     totalSize = baseSize;
 550     totalSize += computeStringTableSize(classNames);
 551     totalSize += computeStringTableSize(methodNames);
 552     totalSize += computeStringTableSize(fileNames);
 553     LOGI("Generated AT, size is %zd/%zd\n", baseSize, totalSize);
 554
 555     /*
 556      * Part 3: allocate a buffer and generate the output.
 557      */
 558     u1* strPtr;
 559
 560     buffer = (u1*) malloc(totalSize);
 561     strPtr = buffer + baseSize;
 562     generateBaseOutput(buffer, baseSize, classNames, methodNames, fileNames);
 563     strPtr += outputStringTable(classNames, strPtr);
 564     strPtr += outputStringTable(methodNames, strPtr);
 565     strPtr += outputStringTable(fileNames, strPtr);
 566     if (strPtr - buffer != (int)totalSize) {
 567         LOGE("size mismatch (%d vs %zd)\n", strPtr - buffer, totalSize);
 568         dvmAbort();
 569     }
 570     //dvmPrintHexDump(buffer, totalSize);
 571
 572     *pData = buffer;
 573     *pDataLen = totalSize;
 574     buffer = NULL;          // don't free -- caller will own
 575     result = true;
 576
 577 bail:
 578     dvmPointerSetFree(classNames);
 579     dvmPointerSetFree(methodNames);
 580     dvmPointerSetFree(fileNames);
 581     free(buffer);
 582     dvmUnlockMutex(&gDvm.allocTrackerLock);
 583     //dvmDumpTrackedAllocations(false);
 584     return result;
 585 }
 586
 587 /*
 588  * Dump the tracked allocations to the log file.
 589  *
 590  * If "enable" is set, we try to enable the feature if it's not already
 591  * active.
 592  */
 593 void dvmDumpTrackedAllocations(bool enable)
 594 {
 595     if (enable)
 596         dvmEnableAllocTracker();
 597
 598     dvmLockMutex(&gDvm.allocTrackerLock);
 599     if (gDvm.allocRecords == NULL)
 600         goto bail;
 601
 602     /*
 603      * "idx" is the head of the list.  We want to start at the end of the
 604      * list and move forward to the tail.
 605      */
 606     int idx = headIndex();
 607     int count = gDvm.allocRecordCount;
 608
 609     LOGI("Tracked allocations, (head=%d count=%d)\n",
 610         gDvm.allocRecordHead, count);
 611     while (count--) {
 612         AllocRecord* pRec = &gDvm.allocRecords[idx];
 613         LOGI(" T=%-2d %6d %s\n",
 614             pRec->threadId, pRec->size, pRec->clazz->descriptor);
 615
 616         if (true) {
 617             int i;
 618             for (i = 0; i < kMaxAllocRecordStackDepth; i++) {
 619                 if (pRec->stackElem[i].method == NULL)
 620                     break;
 621
 622                 const Method* method = pRec->stackElem[i].method;
 623                 if (dvmIsNativeMethod(method)) {
 624                     LOGI("    %s.%s (Native)\n",
 625                         method->clazz->descriptor, method->name);
 626                 } else {
 627                     LOGI("    %s.%s +%d\n",
 628                         method->clazz->descriptor, method->name,
 629                         pRec->stackElem[i].pc);
 630                 }
 631             }
 632         }
 633
 634         /* pause periodically to help logcat catch up */
 635         if ((count % 5) == 0)
 636             usleep(40000);
 637
 638         idx = (idx + 1) & (kNumAllocRecords-1);
 639     }
 640
 641 bail:
 642     dvmUnlockMutex(&gDvm.allocTrackerLock);
 643     if (false) {
 644         u1* data;
 645         size_t dataLen;
 646         if (dvmGenerateTrackedAllocationReport(&data, &dataLen))
 647             free(data);
 648     }
 649 }
 650