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