vm/AllocTracker.cpp

   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()
  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()
  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()
 109 {
 110     bool result = true;
 111     dvmLockMutex(&gDvm.allocTrackerLock);
 112
 113     if (gDvm.allocRecords == NULL) {
 114         ALOGI("Enabling alloc tracker (%d entries, %d frames --> %d bytes)",
 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()
 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->interpSave.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((u4*) 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, size_t size)
 188 {
 189     Thread* self = dvmThreadSelf();
 190     if (self == NULL) {
 191         ALOGW("alloc tracker: no thread");
 192         return;
 193     }
 194
 195     dvmLockMutex(&gDvm.allocTrackerLock);
 196     if (gDvm.allocRecords == NULL) {
 197         dvmUnlockMutex(&gDvm.allocTrackerLock);
 198         return;
 199     }
 200
 201     /* advance and clip */
 202     if (++gDvm.allocRecordHead == kNumAllocRecords)
 203         gDvm.allocRecordHead = 0;
 204
 205     AllocRecord* pRec = &gDvm.allocRecords[gDvm.allocRecordHead];
 206
 207     pRec->clazz = clazz;
 208     pRec->size = size;
 209     pRec->threadId = self->threadId;
 210     getStackFrames(self, pRec);
 211
 212     if (gDvm.allocRecordCount < kNumAllocRecords)
 213         gDvm.allocRecordCount++;
 214
 215     dvmUnlockMutex(&gDvm.allocTrackerLock);
 216 }
 217
 218
 219 /*
 220  * ===========================================================================
 221  *      Reporting
 222  * ===========================================================================
 223  */
 224
 225 /*
 226 The data we send to DDMS contains everything we have recorded.
 227
 228 Message header (all values big-endian):
 229   (1b) message header len (to allow future expansion); includes itself
 230   (1b) entry header len
 231   (1b) stack frame len
 232   (2b) number of entries
 233   (4b) offset to string table from start of message
 234   (2b) number of class name strings
 235   (2b) number of method name strings
 236   (2b) number of source file name strings
 237   For each entry:
 238     (4b) total allocation size
 239     (2b) threadId
 240     (2b) allocated object's class name index
 241     (1b) stack depth
 242     For each stack frame:
 243       (2b) method's class name
 244       (2b) method name
 245       (2b) method source file
 246       (2b) line number, clipped to 32767; -2 if native; -1 if no source
 247   (xb) class name strings
 248   (xb) method name strings
 249   (xb) source file strings
 250
 251   As with other DDM traffic, strings are sent as a 4-byte length
 252   followed by UTF-16 data.
 253
 254 We send up 16-bit unsigned indexes into string tables.  In theory there
 255 can be (kMaxAllocRecordStackDepth * kNumAllocRecords) unique strings in
 256 each table, but in practice there should be far fewer.
 257
 258 The chief reason for using a string table here is to keep the size of
 259 the DDMS message to a minimum.  This is partly to make the protocol
 260 efficient, but also because we have to form the whole thing up all at
 261 once in a memory buffer.
 262
 263 We use separate string tables for class names, method names, and source
 264 files to keep the indexes small.  There will generally be no overlap
 265 between the contents of these tables.
 266 */
 267 const int kMessageHeaderLen = 15;
 268 const int kEntryHeaderLen = 9;
 269 const int kStackFrameLen = 8;
 270
 271 /*
 272  * Return the index of the head element.
 273  *
 274  * We point at the most-recently-written record, so if allocRecordCount is 1
 275  * we want to use the current element.  Take "head+1" and subtract count
 276  * from it.
 277  *
 278  * We need to handle underflow in our circular buffer, so we add
 279  * kNumAllocRecords and then mask it back down.
 280  */
 281 inline static int headIndex()
 282 {
 283     return (gDvm.allocRecordHead+1 + kNumAllocRecords - gDvm.allocRecordCount)
 284         & (kNumAllocRecords-1);
 285 }
 286
 287 /*
 288  * Dump the contents of a PointerSet full of character pointers.
 289  */
 290 static void dumpStringTable(PointerSet* strings)
 291 {
 292     int count = dvmPointerSetGetCount(strings);
 293     int i;
 294
 295     for (i = 0; i < count; i++)
 296         printf("  %s\n", (const char*) dvmPointerSetGetEntry(strings, i));
 297 }
 298
 299 /*
 300  * Get the method's source file.  If we don't know it, return "" instead
 301  * of a NULL pointer.
 302  */
 303 static const char* getMethodSourceFile(const Method* method)
 304 {
 305     const char* fileName = dvmGetMethodSourceFile(method);
 306     if (fileName == NULL)
 307         fileName = "";
 308     return fileName;
 309 }
 310
 311 /*
 312  * Generate string tables.
 313  *
 314  * Our source material is UTF-8 string constants from DEX files.  If we
 315  * want to be thorough we can generate a hash value for each string and
 316  * use the VM hash table implementation, or we can do a quick & dirty job
 317  * by just maintaining a list of unique pointers.  If the same string
 318  * constant appears in multiple DEX files we'll end up with duplicates,
 319  * but in practice this shouldn't matter (and if it does, we can uniq-sort
 320  * the result in a second pass).
 321  */
 322 static bool populateStringTables(PointerSet* classNames,
 323     PointerSet* methodNames, PointerSet* fileNames)
 324 {
 325     int count = gDvm.allocRecordCount;
 326     int idx = headIndex();
 327     int classCount, methodCount, fileCount;         /* debug stats */
 328
 329     classCount = methodCount = fileCount = 0;
 330
 331     while (count--) {
 332         AllocRecord* pRec = &gDvm.allocRecords[idx];
 333
 334         dvmPointerSetAddEntry(classNames, pRec->clazz->descriptor);
 335         classCount++;
 336
 337         int i;
 338         for (i = 0; i < kMaxAllocRecordStackDepth; i++) {
 339             if (pRec->stackElem[i].method == NULL)
 340                 break;
 341
 342             const Method* method = pRec->stackElem[i].method;
 343             dvmPointerSetAddEntry(classNames, method->clazz->descriptor);
 344             classCount++;
 345             dvmPointerSetAddEntry(methodNames, method->name);
 346             methodCount++;
 347             dvmPointerSetAddEntry(fileNames, getMethodSourceFile(method));
 348             fileCount++;
 349         }
 350
 351         idx = (idx + 1) & (kNumAllocRecords-1);
 352     }
 353
 354     ALOGI("class %d/%d, method %d/%d, file %d/%d",
 355         dvmPointerSetGetCount(classNames), classCount,
 356         dvmPointerSetGetCount(methodNames), methodCount,
 357         dvmPointerSetGetCount(fileNames), fileCount);
 358
 359     return true;
 360 }
 361
 362 /*
 363  * Generate the base info (i.e. everything but the string tables).
 364  *
 365  * This should be called twice.  On the first call, "ptr" is NULL and
 366  * "baseLen" is zero.  The return value is used to allocate a buffer.
 367  * On the second call, "ptr" points to a data buffer, and "baseLen"
 368  * holds the value from the result of the first call.
 369  *
 370  * The size of the output data is returned.
 371  */
 372 static size_t generateBaseOutput(u1* ptr, size_t baseLen,
 373     const PointerSet* classNames, const PointerSet* methodNames,
 374     const PointerSet* fileNames)
 375 {
 376     u1* origPtr = ptr;
 377     int count = gDvm.allocRecordCount;
 378     int idx = headIndex();
 379
 380     if (origPtr != NULL) {
 381         set1(&ptr[0], kMessageHeaderLen);
 382         set1(&ptr[1], kEntryHeaderLen);
 383         set1(&ptr[2], kStackFrameLen);
 384         set2BE(&ptr[3], count);
 385         set4BE(&ptr[5], baseLen);
 386         set2BE(&ptr[9], dvmPointerSetGetCount(classNames));
 387         set2BE(&ptr[11], dvmPointerSetGetCount(methodNames));
 388         set2BE(&ptr[13], dvmPointerSetGetCount(fileNames));
 389     }
 390     ptr += kMessageHeaderLen;
 391
 392     while (count--) {
 393         AllocRecord* pRec = &gDvm.allocRecords[idx];
 394
 395         /* compute depth */
 396         int  depth;
 397         for (depth = 0; depth < kMaxAllocRecordStackDepth; depth++) {
 398             if (pRec->stackElem[depth].method == NULL)
 399                 break;
 400         }
 401
 402         /* output header */
 403         if (origPtr != NULL) {
 404             set4BE(&ptr[0], pRec->size);
 405             set2BE(&ptr[4], pRec->threadId);
 406             set2BE(&ptr[6],
 407                 dvmPointerSetFind(classNames, pRec->clazz->descriptor));
 408             set1(&ptr[8], depth);
 409         }
 410         ptr += kEntryHeaderLen;
 411
 412         /* convert stack frames */
 413         int i;
 414         for (i = 0; i < depth; i++) {
 415             if (origPtr != NULL) {
 416                 const Method* method = pRec->stackElem[i].method;
 417                 int lineNum;
 418
 419                 lineNum = dvmLineNumFromPC(method, pRec->stackElem[i].pc);
 420                 if (lineNum > 32767)
 421                     lineNum = 32767;
 422
 423                 set2BE(&ptr[0], dvmPointerSetFind(classNames,
 424                         method->clazz->descriptor));
 425                 set2BE(&ptr[2], dvmPointerSetFind(methodNames,
 426                         method->name));
 427                 set2BE(&ptr[4], dvmPointerSetFind(fileNames,
 428                         getMethodSourceFile(method)));
 429                 set2BE(&ptr[6], (u2)lineNum);
 430             }
 431             ptr += kStackFrameLen;
 432         }
 433
 434         idx = (idx + 1) & (kNumAllocRecords-1);
 435     }
 436
 437     return ptr - origPtr;
 438 }
 439
 440 /*
 441  * Compute the size required to store a string table.  Includes the length
 442  * word and conversion to UTF-16.
 443  */
 444 static size_t computeStringTableSize(PointerSet* strings)
 445 {
 446     int count = dvmPointerSetGetCount(strings);
 447     size_t size = 0;
 448     int i;
 449
 450     for (i = 0; i < count; i++) {
 451         const char* str = (const char*) dvmPointerSetGetEntry(strings, i);
 452
 453         size += 4 + dvmUtf8Len(str) * 2;
 454     }
 455
 456     return size;
 457 }
 458
 459 /*
 460  * Convert a UTF-8 string to UTF-16.  We also need to byte-swap the values
 461  * to big-endian, and we can't assume even alignment on the target.
 462  *
 463  * Returns the string's length, in characters.
 464  */
 465 static int convertUtf8ToUtf16BEUA(u1* utf16Str, const char* utf8Str)
 466 {
 467     u1* origUtf16Str = utf16Str;
 468
 469     while (*utf8Str != '\0') {
 470         u2 utf16 = dexGetUtf16FromUtf8(&utf8Str);       /* advances utf8Str */
 471         set2BE(utf16Str, utf16);
 472         utf16Str += 2;
 473     }
 474
 475     return (utf16Str - origUtf16Str) / 2;
 476 }
 477
 478 /*
 479  * Output a string table serially.
 480  */
 481 static size_t outputStringTable(PointerSet* strings, u1* ptr)
 482 {
 483     int count = dvmPointerSetGetCount(strings);
 484     u1* origPtr = ptr;
 485     int i;
 486
 487     for (i = 0; i < count; i++) {
 488         const char* str = (const char*) dvmPointerSetGetEntry(strings, i);
 489         int charLen;
 490
 491         /* copy UTF-8 string to big-endian unaligned UTF-16 */
 492         charLen = convertUtf8ToUtf16BEUA(&ptr[4], str);
 493         set4BE(&ptr[0], charLen);
 494
 495         ptr += 4 + charLen * 2;
 496     }
 497
 498     return ptr - origPtr;
 499 }
 500
 501 /*
 502  * Generate a DDM packet with all of the tracked allocation data.
 503  *
 504  * On success, returns "true" with "*pData" and "*pDataLen" set.
 505  */
 506 bool dvmGenerateTrackedAllocationReport(u1** pData, size_t* pDataLen)
 507 {
 508     bool result = false;
 509     u1* buffer = NULL;
 510
 511     dvmLockMutex(&gDvm.allocTrackerLock);
 512
 513     /*
 514      * Part 1: generate string tables.
 515      */
 516     PointerSet* classNames = NULL;
 517     PointerSet* methodNames = NULL;
 518     PointerSet* fileNames = NULL;
 519
 520     /*
 521      * Allocate storage.  Usually there's 60-120 of each thing (sampled
 522      * when max=512), but it varies widely and isn't closely bound to
 523      * the number of allocations we've captured.  The sets expand quickly
 524      * if needed.
 525      */
 526     classNames = dvmPointerSetAlloc(128);
 527     methodNames = dvmPointerSetAlloc(128);
 528     fileNames = dvmPointerSetAlloc(128);
 529     if (classNames == NULL || methodNames == NULL || fileNames == NULL) {
 530         ALOGE("Failed allocating pointer sets");
 531         goto bail;
 532     }
 533
 534     if (!populateStringTables(classNames, methodNames, fileNames))
 535         goto bail;
 536
 537     if (false) {
 538         printf("Classes:\n");
 539         dumpStringTable(classNames);
 540         printf("Methods:\n");
 541         dumpStringTable(methodNames);
 542         printf("Files:\n");
 543         dumpStringTable(fileNames);
 544     }
 545
 546     /*
 547      * Part 2: compute the size of the output.
 548      *
 549      * (Could also just write to an expanding buffer.)
 550      */
 551     size_t baseSize, totalSize;
 552     baseSize = generateBaseOutput(NULL, 0, classNames, methodNames, fileNames);
 553     assert(baseSize > 0);
 554     totalSize = baseSize;
 555     totalSize += computeStringTableSize(classNames);
 556     totalSize += computeStringTableSize(methodNames);
 557     totalSize += computeStringTableSize(fileNames);
 558     ALOGI("Generated AT, size is %zd/%zd", baseSize, totalSize);
 559
 560     /*
 561      * Part 3: allocate a buffer and generate the output.
 562      */
 563     u1* strPtr;
 564
 565     buffer = (u1*) malloc(totalSize);
 566     strPtr = buffer + baseSize;
 567     generateBaseOutput(buffer, baseSize, classNames, methodNames, fileNames);
 568     strPtr += outputStringTable(classNames, strPtr);
 569     strPtr += outputStringTable(methodNames, strPtr);
 570     strPtr += outputStringTable(fileNames, strPtr);
 571     if (strPtr - buffer != (int)totalSize) {
 572         ALOGE("size mismatch (%d vs %zd)", strPtr - buffer, totalSize);
 573         dvmAbort();
 574     }
 575     //dvmPrintHexDump(buffer, totalSize);
 576
 577     *pData = buffer;
 578     *pDataLen = totalSize;
 579     buffer = NULL;          // don't free -- caller will own
 580     result = true;
 581
 582 bail:
 583     dvmPointerSetFree(classNames);
 584     dvmPointerSetFree(methodNames);
 585     dvmPointerSetFree(fileNames);
 586     free(buffer);
 587     dvmUnlockMutex(&gDvm.allocTrackerLock);
 588     //dvmDumpTrackedAllocations(false);
 589     return result;
 590 }
 591
 592 /*
 593  * Dump the tracked allocations to the log file.
 594  *
 595  * If "enable" is set, we try to enable the feature if it's not already
 596  * active.
 597  */
 598 void dvmDumpTrackedAllocations(bool enable)
 599 {
 600     if (enable)
 601         dvmEnableAllocTracker();
 602
 603     dvmLockMutex(&gDvm.allocTrackerLock);
 604     if (gDvm.allocRecords == NULL) {
 605         dvmUnlockMutex(&gDvm.allocTrackerLock);
 606         return;
 607     }
 608
 609     /*
 610      * "idx" is the head of the list.  We want to start at the end of the
 611      * list and move forward to the tail.
 612      */
 613     int idx = headIndex();
 614     int count = gDvm.allocRecordCount;
 615
 616     ALOGI("Tracked allocations, (head=%d count=%d)",
 617         gDvm.allocRecordHead, count);
 618     while (count--) {
 619         AllocRecord* pRec = &gDvm.allocRecords[idx];
 620         ALOGI(" T=%-2d %6d %s",
 621             pRec->threadId, pRec->size, pRec->clazz->descriptor);
 622
 623         if (true) {
 624             for (int i = 0; i < kMaxAllocRecordStackDepth; i++) {
 625                 if (pRec->stackElem[i].method == NULL)
 626                     break;
 627
 628                 const Method* method = pRec->stackElem[i].method;
 629                 if (dvmIsNativeMethod(method)) {
 630                     ALOGI("    %s.%s (Native)",
 631                         method->clazz->descriptor, method->name);
 632                 } else {
 633                     ALOGI("    %s.%s +%d",
 634                         method->clazz->descriptor, method->name,
 635                         pRec->stackElem[i].pc);
 636                 }
 637             }
 638         }
 639
 640         /* pause periodically to help logcat catch up */
 641         if ((count % 5) == 0)
 642             usleep(40000);
 643
 644         idx = (idx + 1) & (kNumAllocRecords-1);
 645     }
 646
 647     dvmUnlockMutex(&gDvm.allocTrackerLock);
 648     if (false) {
 649         u1* data;
 650         size_t dataLen;
 651         if (dvmGenerateTrackedAllocationReport(&data, &dataLen))
 652             free(data);
 653     }
 654 }