vm/alloc/HeapSource.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 #include <cutils/mspace.h>
  18 #include <limits.h>     // for SIZE_T_MAX
  19 #include <sys/mman.h>
  20 #include <errno.h>
  21
  22 #include "Dalvik.h"
  23 #include "alloc/Heap.h"
  24 #include "alloc/HeapInternal.h"
  25 #include "alloc/HeapSource.h"
  26 #include "alloc/HeapBitmap.h"
  27
  28 // TODO: find a real header file for these.
  29 extern int dlmalloc_trim(size_t);
  30 extern void dlmalloc_walk_free_pages(void(*)(void*, void*, void*), void*);
  31
  32 static void snapIdealFootprint(void);
  33 static void setIdealFootprint(size_t max);
  34
  35 #define ALIGN_UP_TO_PAGE_SIZE(p) \
  36     (((size_t)(p) + (SYSTEM_PAGE_SIZE - 1)) & ~(SYSTEM_PAGE_SIZE - 1))
  37 #define ALIGN_DOWN_TO_PAGE_SIZE(p) \
  38     ((size_t)(p) & ~(SYSTEM_PAGE_SIZE - 1))
  39
  40 #define HEAP_UTILIZATION_MAX        1024
  41 #define DEFAULT_HEAP_UTILIZATION    512     // Range 1..HEAP_UTILIZATION_MAX
  42 #define HEAP_IDEAL_FREE             (2 * 1024 * 1024)
  43 #define HEAP_MIN_FREE               (HEAP_IDEAL_FREE / 4)
  44
  45 /* Start a concurrent collection when free memory falls under this
  46  * many bytes.
  47  */
  48 #define CONCURRENT_START (128 << 10)
  49
  50 /* The next GC will not be concurrent when free memory after a GC is
  51  * under this many bytes.
  52  */
  53 #define CONCURRENT_MIN_FREE (CONCURRENT_START + (128 << 10))
  54
  55 #define HS_BOILERPLATE() \
  56     do { \
  57         assert(gDvm.gcHeap != NULL); \
  58         assert(gDvm.gcHeap->heapSource != NULL); \
  59         assert(gHs == gDvm.gcHeap->heapSource); \
  60     } while (0)
  61
  62 #define DEBUG_HEAP_SOURCE 0
  63 #if DEBUG_HEAP_SOURCE
  64 #define HSTRACE(...)  LOG(LOG_INFO, LOG_TAG "-hs", __VA_ARGS__)
  65 #else
  66 #define HSTRACE(...)  /**/
  67 #endif
  68
  69 /*
  70 =======================================================
  71 =======================================================
  72 =======================================================
  73
  74 How will this be used?
  75 allocating/freeing: Heap.c just wants to say "alloc(n)" and get a ptr
  76     - if allocating in large doesn't work, try allocating from small
  77 Heap.c will use HeapSource.h; HeapSource.c will do the right thing
  78     between small and large
  79     - some operations should be abstracted; put in a structure
  80
  81 How do we manage the size trade-offs?
  82 - keep mspace max footprint clamped to actual footprint
  83 - if small-alloc returns null, adjust large vs. small ratio
  84     - give small all available slack and retry
  85     - success or fail, snap back to actual footprint and give rest to large
  86
  87 managed as "small actual" + "large actual" + "delta to allowed total footprint"
  88 - when allocating from one source or the other, give the delta to the
  89     active source, but snap back afterwards
  90 - that may not work so great for a gc heap, because small will always consume.
  91     - but we need to use the memory, and the current max is the amount we
  92       need to fill before a GC.
  93
  94 Find a way to permanently steal pages from the middle of the heap
  95     - segment tricks?
  96
  97 Allocate String and char[] in a separate heap?
  98
  99 Maybe avoid growing small heap, even if there's slack?  Look at
 100 live ratio of small heap after a gc; scale it based on that.
 101
 102 =======================================================
 103 =======================================================
 104 =======================================================
 105 */
 106
 107 typedef struct {
 108     /* The mspace to allocate from.
 109      */
 110     mspace msp;
 111
 112     /* The largest size that this heap is allowed to grow to.
 113      */
 114     size_t absoluteMaxSize;
 115
 116     /* Number of bytes allocated from this mspace for objects,
 117      * including any overhead.  This value is NOT exact, and
 118      * should only be used as an input for certain heuristics.
 119      */
 120     size_t bytesAllocated;
 121
 122     /* Number of bytes allocated from this mspace at which a
 123      * concurrent garbage collection will be started.
 124      */
 125     size_t concurrentStartBytes;
 126
 127     /* Number of objects currently allocated from this mspace.
 128      */
 129     size_t objectsAllocated;
 130
 131     /*
 132      * The lowest address of this heap, inclusive.
 133      */
 134     char *base;
 135
 136     /*
 137      * The highest address of this heap, exclusive.
 138      */
 139     char *limit;
 140 } Heap;
 141
 142 struct HeapSource {
 143     /* Target ideal heap utilization ratio; range 1..HEAP_UTILIZATION_MAX
 144      */
 145     size_t targetUtilization;
 146
 147     /* Requested minimum heap size, or zero if there is no minimum.
 148      */
 149     size_t minimumSize;
 150
 151     /* The starting heap size.
 152      */
 153     size_t startSize;
 154
 155     /* The largest that the heap source as a whole is allowed to grow.
 156      */
 157     size_t absoluteMaxSize;
 158
 159     /* The desired max size of the heap source as a whole.
 160      */
 161     size_t idealSize;
 162
 163     /* The maximum number of bytes allowed to be allocated from the
 164      * active heap before a GC is forced.  This is used to "shrink" the
 165      * heap in lieu of actual compaction.
 166      */
 167     size_t softLimit;
 168
 169     /* The heaps; heaps[0] is always the active heap,
 170      * which new objects should be allocated from.
 171      */
 172     Heap heaps[HEAP_SOURCE_MAX_HEAP_COUNT];
 173
 174     /* The current number of heaps.
 175      */
 176     size_t numHeaps;
 177
 178     /* External allocation count.
 179      */
 180     size_t externalBytesAllocated;
 181
 182     /* The maximum number of external bytes that may be allocated.
 183      */
 184     size_t externalLimit;
 185
 186     /* True if zygote mode was active when the HeapSource was created.
 187      */
 188     bool sawZygote;
 189
 190     /*
 191      * The base address of the virtual memory reservation.
 192      */
 193     char *heapBase;
 194
 195     /*
 196      * The length in bytes of the virtual memory reservation.
 197      */
 198     size_t heapLength;
 199
 200     /*
 201      * The live object bitmap.
 202      */
 203     HeapBitmap liveBits;
 204
 205     /*
 206      * The mark bitmap.
 207      */
 208     HeapBitmap markBits;
 209
 210     /*
 211      * State for the GC daemon.
 212      */
 213     bool hasGcThread;
 214     pthread_t gcThread;
 215     bool gcThreadShutdown;
 216     pthread_mutex_t gcThreadMutex;
 217     pthread_cond_t gcThreadCond;
 218 };
 219
 220 #define hs2heap(hs_) (&((hs_)->heaps[0]))
 221
 222 /*
 223  * Returns true iff a soft limit is in effect for the active heap.
 224  */
 225 static inline bool
 226 softLimited(const HeapSource *hs)
 227 {
 228     /* softLimit will be either SIZE_T_MAX or the limit for the
 229      * active mspace.  idealSize can be greater than softLimit
 230      * if there is more than one heap.  If there is only one
 231      * heap, a non-SIZE_T_MAX softLimit should always be the same
 232      * as idealSize.
 233      */
 234     return hs->softLimit <= hs->idealSize;
 235 }
 236
 237 /*
 238  * Returns approximately the maximum number of bytes allowed to be
 239  * allocated from the active heap before a GC is forced.
 240  */
 241 static size_t
 242 getAllocLimit(const HeapSource *hs)
 243 {
 244     if (softLimited(hs)) {
 245         return hs->softLimit;
 246     } else {
 247         return mspace_max_allowed_footprint(hs2heap(hs)->msp);
 248     }
 249 }
 250
 251 /*
 252  * Returns the current footprint of all heaps.  If includeActive
 253  * is false, don't count the heap at index 0.
 254  */
 255 static inline size_t
 256 oldHeapOverhead(const HeapSource *hs, bool includeActive)
 257 {
 258     size_t footprint = 0;
 259     size_t i;
 260
 261     if (includeActive) {
 262         i = 0;
 263     } else {
 264         i = 1;
 265     }
 266     for (/* i = i */; i < hs->numHeaps; i++) {
 267 //TODO: include size of bitmaps?  If so, don't use bitsLen, listen to .max
 268         footprint += mspace_footprint(hs->heaps[i].msp);
 269     }
 270     return footprint;
 271 }
 272
 273 /*
 274  * Returns the heap that <ptr> could have come from, or NULL
 275  * if it could not have come from any heap.
 276  */
 277 static inline Heap *
 278 ptr2heap(const HeapSource *hs, const void *ptr)
 279 {
 280     const size_t numHeaps = hs->numHeaps;
 281     size_t i;
 282
 283 //TODO: unroll this to HEAP_SOURCE_MAX_HEAP_COUNT
 284     if (ptr != NULL) {
 285         for (i = 0; i < numHeaps; i++) {
 286             const Heap *const heap = &hs->heaps[i];
 287
 288             if ((const char *)ptr >= heap->base && (const char *)ptr < heap->limit) {
 289                 return (Heap *)heap;
 290             }
 291         }
 292     }
 293     return NULL;
 294 }
 295
 296 /*
 297  * Functions to update heapSource->bytesAllocated when an object
 298  * is allocated or freed.  mspace_usable_size() will give
 299  * us a much more accurate picture of heap utilization than
 300  * the requested byte sizes would.
 301  *
 302  * These aren't exact, and should not be treated as such.
 303  */
 304 static void countAllocation(Heap *heap, const void *ptr, bool isObj)
 305 {
 306     HeapSource *hs;
 307
 308     assert(heap->bytesAllocated < mspace_footprint(heap->msp));
 309
 310     heap->bytesAllocated += mspace_usable_size(heap->msp, ptr) +
 311             HEAP_SOURCE_CHUNK_OVERHEAD;
 312     if (isObj) {
 313         heap->objectsAllocated++;
 314         hs = gDvm.gcHeap->heapSource;
 315         dvmHeapBitmapSetObjectBit(&hs->liveBits, ptr);
 316     }
 317
 318     assert(heap->bytesAllocated < mspace_footprint(heap->msp));
 319 }
 320
 321 static void countFree(Heap *heap, const void *ptr, size_t *numBytes)
 322 {
 323     HeapSource *hs;
 324     size_t delta;
 325
 326     delta = mspace_usable_size(heap->msp, ptr) + HEAP_SOURCE_CHUNK_OVERHEAD;
 327     assert(delta > 0);
 328     if (delta < heap->bytesAllocated) {
 329         heap->bytesAllocated -= delta;
 330     } else {
 331         heap->bytesAllocated = 0;
 332     }
 333     hs = gDvm.gcHeap->heapSource;
 334     dvmHeapBitmapClearObjectBit(&hs->liveBits, ptr);
 335     if (heap->objectsAllocated > 0) {
 336         heap->objectsAllocated--;
 337     }
 338     *numBytes += delta;
 339 }
 340
 341 static HeapSource *gHs = NULL;
 342
 343 static mspace
 344 createMspace(void *base, size_t startSize, size_t absoluteMaxSize)
 345 {
 346     mspace msp;
 347
 348     /* Create an unlocked dlmalloc mspace to use as
 349      * a small-object heap source.
 350      *
 351      * We start off reserving heapSizeStart/2 bytes but
 352      * letting the heap grow to heapSizeStart.  This saves
 353      * memory in the case where a process uses even less
 354      * than the starting size.
 355      */
 356     LOGV_HEAP("Creating VM heap of size %u\n", startSize);
 357     errno = 0;
 358     msp = create_contiguous_mspace_with_base(startSize/2,
 359             absoluteMaxSize, /*locked=*/false, base);
 360     if (msp != NULL) {
 361         /* Don't let the heap grow past the starting size without
 362          * our intervention.
 363          */
 364         mspace_set_max_allowed_footprint(msp, startSize);
 365     } else {
 366         /* There's no guarantee that errno has meaning when the call
 367          * fails, but it often does.
 368          */
 369         LOGE_HEAP("Can't create VM heap of size (%u,%u): %s\n",
 370             startSize/2, absoluteMaxSize, strerror(errno));
 371     }
 372
 373     return msp;
 374 }
 375
 376 static bool
 377 addNewHeap(HeapSource *hs, mspace msp, size_t mspAbsoluteMaxSize)
 378 {
 379     Heap heap;
 380     void *base;
 381
 382     if (hs->numHeaps >= HEAP_SOURCE_MAX_HEAP_COUNT) {
 383         LOGE("Attempt to create too many heaps (%zd >= %zd)\n",
 384                 hs->numHeaps, HEAP_SOURCE_MAX_HEAP_COUNT);
 385         dvmAbort();
 386         return false;
 387     }
 388
 389     memset(&heap, 0, sizeof(heap));
 390
 391     if (msp != NULL) {
 392         heap.msp = msp;
 393         heap.absoluteMaxSize = mspAbsoluteMaxSize;
 394         heap.concurrentStartBytes = SIZE_T_MAX;
 395         heap.base = hs->heapBase;
 396         heap.limit = hs->heapBase + heap.absoluteMaxSize;
 397     } else {
 398         size_t overhead;
 399
 400         overhead = ALIGN_UP_TO_PAGE_SIZE(oldHeapOverhead(hs, true));
 401         if (overhead + HEAP_MIN_FREE >= hs->absoluteMaxSize) {
 402             LOGE_HEAP("No room to create any more heaps "
 403                     "(%zd overhead, %zd max)\n",
 404                     overhead, hs->absoluteMaxSize);
 405             return false;
 406         }
 407         hs->heaps[0].absoluteMaxSize = overhead;
 408         heap.absoluteMaxSize = hs->absoluteMaxSize - overhead;
 409         base = contiguous_mspace_sbrk0(hs->heaps[0].msp);
 410         hs->heaps[0].limit = base;
 411         base = (void *)ALIGN_UP_TO_PAGE_SIZE(base);
 412         heap.msp = createMspace(base, HEAP_MIN_FREE, heap.absoluteMaxSize);
 413         heap.concurrentStartBytes = HEAP_MIN_FREE - CONCURRENT_START;
 414         heap.base = base;
 415         heap.limit = heap.base + heap.absoluteMaxSize;
 416         if (heap.msp == NULL) {
 417             return false;
 418         }
 419     }
 420
 421     /* Don't let the soon-to-be-old heap grow any further.
 422      */
 423     if (hs->numHeaps > 0) {
 424         mspace msp = hs->heaps[0].msp;
 425         mspace_set_max_allowed_footprint(msp, mspace_footprint(msp));
 426     }
 427
 428     /* Put the new heap in the list, at heaps[0].
 429      * Shift existing heaps down.
 430      */
 431     memmove(&hs->heaps[1], &hs->heaps[0], hs->numHeaps * sizeof(hs->heaps[0]));
 432     hs->heaps[0] = heap;
 433     hs->numHeaps++;
 434
 435     return true;
 436 }
 437
 438 /*
 439  * The garbage collection daemon.  Initiates a concurrent collection
 440  * when signaled.
 441  */
 442 static void *gcDaemonThread(void* arg)
 443 {
 444     dvmChangeStatus(NULL, THREAD_VMWAIT);
 445     dvmLockMutex(&gHs->gcThreadMutex);
 446     while (gHs->gcThreadShutdown != true) {
 447         dvmWaitCond(&gHs->gcThreadCond, &gHs->gcThreadMutex);
 448         dvmLockHeap();
 449         dvmChangeStatus(NULL, THREAD_RUNNING);
 450         dvmCollectGarbageInternal(false, GC_CONCURRENT);
 451         dvmChangeStatus(NULL, THREAD_VMWAIT);
 452         dvmUnlockHeap();
 453     }
 454     dvmChangeStatus(NULL, THREAD_RUNNING);
 455     return NULL;
 456 }
 457
 458 static bool gcDaemonStartup(void)
 459 {
 460     dvmInitMutex(&gHs->gcThreadMutex);
 461     pthread_cond_init(&gHs->gcThreadCond, NULL);
 462     gHs->gcThreadShutdown = false;
 463     gHs->hasGcThread = dvmCreateInternalThread(&gHs->gcThread, "GC",
 464                                                gcDaemonThread, NULL);
 465     return gHs->hasGcThread;
 466 }
 467
 468 static void gcDaemonShutdown(void)
 469 {
 470     if (gHs->hasGcThread) {
 471         dvmLockMutex(&gHs->gcThreadMutex);
 472         gHs->gcThreadShutdown = true;
 473         dvmSignalCond(&gHs->gcThreadCond);
 474         dvmUnlockMutex(&gHs->gcThreadMutex);
 475         pthread_join(gHs->gcThread, NULL);
 476     }
 477 }
 478
 479 /*
 480  * Initializes the heap source; must be called before any other
 481  * dvmHeapSource*() functions.  Returns a GcHeap structure
 482  * allocated from the heap source.
 483  */
 484 GcHeap *
 485 dvmHeapSourceStartup(size_t startSize, size_t absoluteMaxSize)
 486 {
 487     GcHeap *gcHeap;
 488     HeapSource *hs;
 489     mspace msp;
 490     size_t length;
 491     void *base;
 492
 493     assert(gHs == NULL);
 494
 495     if (startSize > absoluteMaxSize) {
 496         LOGE("Bad heap parameters (start=%d, max=%d)\n",
 497            startSize, absoluteMaxSize);
 498         return NULL;
 499     }
 500
 501     /*
 502      * Allocate a contiguous region of virtual memory to subdivided
 503      * among the heaps managed by the garbage collector.
 504      */
 505     length = ALIGN_UP_TO_PAGE_SIZE(absoluteMaxSize);
 506     base = dvmAllocRegion(length, PROT_NONE, "dalvik-heap");
 507     if (base == NULL) {
 508         return NULL;
 509     }
 510
 511     /* Create an unlocked dlmalloc mspace to use as
 512      * the small object heap source.
 513      */
 514     msp = createMspace(base, startSize, absoluteMaxSize);
 515     if (msp == NULL) {
 516         goto fail;
 517     }
 518
 519     /* Allocate a descriptor from the heap we just created.
 520      */
 521     gcHeap = mspace_malloc(msp, sizeof(*gcHeap));
 522     if (gcHeap == NULL) {
 523         LOGE_HEAP("Can't allocate heap descriptor\n");
 524         goto fail;
 525     }
 526     memset(gcHeap, 0, sizeof(*gcHeap));
 527
 528     hs = mspace_malloc(msp, sizeof(*hs));
 529     if (hs == NULL) {
 530         LOGE_HEAP("Can't allocate heap source\n");
 531         goto fail;
 532     }
 533     memset(hs, 0, sizeof(*hs));
 534
 535     hs->targetUtilization = DEFAULT_HEAP_UTILIZATION;
 536     hs->minimumSize = 0;
 537     hs->startSize = startSize;
 538     hs->absoluteMaxSize = absoluteMaxSize;
 539     hs->idealSize = startSize;
 540     hs->softLimit = SIZE_T_MAX;    // no soft limit at first
 541     hs->numHeaps = 0;
 542     hs->sawZygote = gDvm.zygote;
 543     hs->hasGcThread = false;
 544     hs->heapBase = base;
 545     hs->heapLength = length;
 546     if (!addNewHeap(hs, msp, absoluteMaxSize)) {
 547         LOGE_HEAP("Can't add initial heap\n");
 548         goto fail;
 549     }
 550     if (!dvmHeapBitmapInit(&hs->liveBits, base, length, "dalvik-bitmap-1")) {
 551         LOGE_HEAP("Can't create liveBits\n");
 552         goto fail;
 553     }
 554     if (!dvmHeapBitmapInit(&hs->markBits, base, length, "dalvik-bitmap-2")) {
 555         LOGE_HEAP("Can't create markBits\n");
 556         dvmHeapBitmapDelete(&hs->liveBits);
 557         goto fail;
 558     }
 559
 560     gcHeap->markContext.bitmap = &hs->markBits;
 561     gcHeap->heapSource = hs;
 562
 563     countAllocation(hs2heap(hs), gcHeap, false);
 564     countAllocation(hs2heap(hs), hs, false);
 565
 566     gHs = hs;
 567     return gcHeap;
 568
 569 fail:
 570     munmap(base, length);
 571     return NULL;
 572 }
 573
 574 bool dvmHeapSourceStartupAfterZygote(void)
 575 {
 576     return gDvm.concurrentMarkSweep ? gcDaemonStartup() : true;
 577 }
 578
 579 /*
 580  * This is called while in zygote mode, right before we fork() for the
 581  * first time.  We create a heap for all future zygote process allocations,
 582  * in an attempt to avoid touching pages in the zygote heap.  (This would
 583  * probably be unnecessary if we had a compacting GC -- the source of our
 584  * troubles is small allocations filling in the gaps from larger ones.)
 585  */
 586 bool
 587 dvmHeapSourceStartupBeforeFork()
 588 {
 589     HeapSource *hs = gHs; // use a local to avoid the implicit "volatile"
 590
 591     HS_BOILERPLATE();
 592
 593     assert(gDvm.zygote);
 594
 595     if (!gDvm.newZygoteHeapAllocated) {
 596         /* Create a new heap for post-fork zygote allocations.  We only
 597          * try once, even if it fails.
 598          */
 599         LOGV("Splitting out new zygote heap\n");
 600         gDvm.newZygoteHeapAllocated = true;
 601         return addNewHeap(hs, NULL, 0);
 602     }
 603     return true;
 604 }
 605
 606 void dvmHeapSourceThreadShutdown(void)
 607 {
 608     if (gDvm.gcHeap != NULL && gDvm.concurrentMarkSweep) {
 609         gcDaemonShutdown();
 610     }
 611 }
 612
 613 /*
 614  * Tears down the entire GcHeap structure and all of the substructures
 615  * attached to it.  This call has the side effect of setting the given
 616  * gcHeap pointer and gHs to NULL.
 617  */
 618 void
 619 dvmHeapSourceShutdown(GcHeap **gcHeap)
 620 {
 621     if (*gcHeap != NULL && (*gcHeap)->heapSource != NULL) {
 622         HeapSource *hs;
 623
 624         hs = (*gcHeap)->heapSource;
 625
 626         assert((char *)*gcHeap >= hs->heapBase);
 627         assert((char *)*gcHeap < hs->heapBase + hs->heapLength);
 628
 629         dvmHeapBitmapDelete(&hs->liveBits);
 630         dvmHeapBitmapDelete(&hs->markBits);
 631
 632         munmap(hs->heapBase, hs->heapLength);
 633         gHs = NULL;
 634         *gcHeap = NULL;
 635     }
 636 }
 637
 638 /*
 639  * Gets the begining of the allocation for the HeapSource.
 640  */
 641 void *dvmHeapSourceGetBase(void)
 642 {
 643     return gHs->heapBase;
 644 }
 645
 646 /*
 647  * Returns the requested value. If the per-heap stats are requested, fill
 648  * them as well.
 649  *
 650  * Caller must hold the heap lock.
 651  */
 652 size_t
 653 dvmHeapSourceGetValue(enum HeapSourceValueSpec spec, size_t perHeapStats[],
 654                       size_t arrayLen)
 655 {
 656     HeapSource *hs = gHs;
 657     size_t value = 0;
 658     size_t total = 0;
 659     size_t i;
 660
 661     HS_BOILERPLATE();
 662
 663     switch (spec) {
 664     case HS_EXTERNAL_BYTES_ALLOCATED:
 665         return hs->externalBytesAllocated;
 666     case HS_EXTERNAL_LIMIT:
 667         return hs->externalLimit;
 668     default:
 669         // look at all heaps.
 670         ;
 671     }
 672
 673     assert(arrayLen >= hs->numHeaps || perHeapStats == NULL);
 674     for (i = 0; i < hs->numHeaps; i++) {
 675         Heap *const heap = &hs->heaps[i];
 676
 677         switch (spec) {
 678         case HS_FOOTPRINT:
 679             value = mspace_footprint(heap->msp);
 680             break;
 681         case HS_ALLOWED_FOOTPRINT:
 682             value = mspace_max_allowed_footprint(heap->msp);
 683             break;
 684         case HS_BYTES_ALLOCATED:
 685             value = heap->bytesAllocated;
 686             break;
 687         case HS_OBJECTS_ALLOCATED:
 688             value = heap->objectsAllocated;
 689             break;
 690         default:
 691             // quiet gcc
 692             break;
 693         }
 694         if (perHeapStats) {
 695             perHeapStats[i] = value;
 696         }
 697         total += value;
 698     }
 699     return total;
 700 }
 701
 702 static void aliasBitmap(HeapBitmap *dst, HeapBitmap *src,
 703                         uintptr_t base, uintptr_t max) {
 704     size_t offset;
 705
 706     dst->base = base;
 707     dst->max = max;
 708     dst->bitsLen = HB_OFFSET_TO_BYTE_INDEX(max - base) + sizeof(dst->bits);
 709     /* The exclusive limit from bitsLen is greater than the inclusive max. */
 710     assert(base + HB_MAX_OFFSET(dst) > max);
 711     /* The exclusive limit is at most one word of bits beyond max. */
 712     assert((base + HB_MAX_OFFSET(dst)) - max <=
 713            HB_OBJECT_ALIGNMENT * HB_BITS_PER_WORD);
 714     dst->allocLen = dst->bitsLen;
 715     offset = base - src->base;
 716     assert(HB_OFFSET_TO_MASK(offset) == 1 << 31);
 717     dst->bits = &src->bits[HB_OFFSET_TO_INDEX(offset)];
 718 }
 719
 720 /*
 721  * Initializes a vector of object and mark bits to the object and mark
 722  * bits of each heap.  The bits are aliased to the heapsource
 723  * object and mark bitmaps.  This routine is used by the sweep code
 724  * which needs to free each object in the correct heap.
 725  */
 726 void dvmHeapSourceGetObjectBitmaps(HeapBitmap liveBits[], HeapBitmap markBits[],
 727                                    size_t numHeaps)
 728 {
 729     HeapSource *hs = gHs;
 730     uintptr_t base, max;
 731     size_t i;
 732
 733     HS_BOILERPLATE();
 734
 735     assert(numHeaps == hs->numHeaps);
 736     for (i = 0; i < hs->numHeaps; ++i) {
 737         base = (uintptr_t)hs->heaps[i].base;
 738         /* -1 because limit is exclusive but max is inclusive. */
 739         max = MIN((uintptr_t)hs->heaps[i].limit - 1, hs->markBits.max);
 740         aliasBitmap(&liveBits[i], &hs->liveBits, base, max);
 741         aliasBitmap(&markBits[i], &hs->markBits, base, max);
 742     }
 743 }
 744
 745 /*
 746  * Get the bitmap representing all live objects.
 747  */
 748 HeapBitmap *dvmHeapSourceGetLiveBits(void)
 749 {
 750     HS_BOILERPLATE();
 751
 752     return &gHs->liveBits;
 753 }
 754
 755 void dvmHeapSourceSwapBitmaps(void)
 756 {
 757     HeapBitmap tmp;
 758
 759     tmp = gHs->liveBits;
 760     gHs->liveBits = gHs->markBits;
 761     gHs->markBits = tmp;
 762 }
 763
 764 void dvmHeapSourceZeroMarkBitmap(void)
 765 {
 766     HS_BOILERPLATE();
 767
 768     dvmHeapBitmapZero(&gHs->markBits);
 769 }
 770
 771 void dvmMarkImmuneObjects(const char *immuneLimit)
 772 {
 773     char *dst, *src;
 774     size_t i, index, length;
 775
 776     /*
 777      * Copy the contents of the live bit vector for immune object
 778      * range into the mark bit vector.
 779      */
 780     /* The only values generated by dvmHeapSourceGetImmuneLimit() */
 781     assert(immuneLimit == gHs->heaps[0].base ||
 782            immuneLimit == NULL);
 783     assert(gHs->liveBits.base == gHs->markBits.base);
 784     assert(gHs->liveBits.bitsLen == gHs->markBits.bitsLen);
 785     /* heap[0] is never immune */
 786     assert(gHs->heaps[0].base >= immuneLimit);
 787     assert(gHs->heaps[0].limit > immuneLimit);
 788
 789     for (i = 1; i < gHs->numHeaps; ++i) {
 790         if (gHs->heaps[i].base < immuneLimit) {
 791             assert(gHs->heaps[i].limit <= immuneLimit);
 792             /* Compute the number of words to copy in the bitmap. */
 793             index = HB_OFFSET_TO_INDEX(
 794                 (uintptr_t)gHs->heaps[i].base - gHs->liveBits.base);
 795             /* Compute the starting offset in the live and mark bits. */
 796             src = (char *)(gHs->liveBits.bits + index);
 797             dst = (char *)(gHs->markBits.bits + index);
 798             /* Compute the number of bytes of the live bitmap to copy. */
 799             length = HB_OFFSET_TO_BYTE_INDEX(
 800                 gHs->heaps[i].limit - gHs->heaps[i].base);
 801             /* Do the copy. */
 802             memcpy(dst, src, length);
 803             /* Make sure max points to the address of the highest set bit. */
 804             if (gHs->markBits.max < (uintptr_t)gHs->heaps[i].limit) {
 805                 gHs->markBits.max = (uintptr_t)gHs->heaps[i].limit;
 806             }
 807         }
 808     }
 809 }
 810
 811 /*
 812  * Allocates <n> bytes of zeroed data.
 813  */
 814 void *
 815 dvmHeapSourceAlloc(size_t n)
 816 {
 817     HeapSource *hs = gHs;
 818     Heap *heap;
 819     void *ptr;
 820
 821     HS_BOILERPLATE();
 822     heap = hs2heap(hs);
 823     if (heap->bytesAllocated + n > hs->softLimit) {
 824         /*
 825          * This allocation would push us over the soft limit; act as
 826          * if the heap is full.
 827          */
 828         LOGV_HEAP("softLimit of %zd.%03zdMB hit for %zd-byte allocation\n",
 829                   FRACTIONAL_MB(hs->softLimit), n);
 830         return NULL;
 831     }
 832     ptr = mspace_calloc(heap->msp, 1, n);
 833     if (ptr == NULL) {
 834         return NULL;
 835     }
 836     countAllocation(heap, ptr, true);
 837     /*
 838      * Check to see if a concurrent GC should be initiated.
 839      */
 840     if (gDvm.gcHeap->gcRunning || !hs->hasGcThread) {
 841         /*
 842          * The garbage collector thread is already running or has yet
 843          * to be started.  Do nothing.
 844          */
 845         return ptr;
 846     }
 847     if (heap->bytesAllocated > heap->concurrentStartBytes) {
 848         /*
 849          * We have exceeded the allocation threshold.  Wake up the
 850          * garbage collector.
 851          */
 852         dvmSignalCond(&gHs->gcThreadCond);
 853     }
 854     return ptr;
 855 }
 856
 857 /* Remove any hard limits, try to allocate, and shrink back down.
 858  * Last resort when trying to allocate an object.
 859  */
 860 static void *
 861 heapAllocAndGrow(HeapSource *hs, Heap *heap, size_t n)
 862 {
 863     void *ptr;
 864     size_t max;
 865
 866     /* Grow as much as possible, but don't let the real footprint
 867      * plus external allocations go over the absolute max.
 868      */
 869     max = heap->absoluteMaxSize;
 870     if (max > hs->externalBytesAllocated) {
 871         max -= hs->externalBytesAllocated;
 872
 873         mspace_set_max_allowed_footprint(heap->msp, max);
 874         ptr = dvmHeapSourceAlloc(n);
 875
 876         /* Shrink back down as small as possible.  Our caller may
 877          * readjust max_allowed to a more appropriate value.
 878          */
 879         mspace_set_max_allowed_footprint(heap->msp,
 880                 mspace_footprint(heap->msp));
 881     } else {
 882         ptr = NULL;
 883     }
 884
 885     return ptr;
 886 }
 887
 888 /*
 889  * Allocates <n> bytes of zeroed data, growing as much as possible
 890  * if necessary.
 891  */
 892 void *
 893 dvmHeapSourceAllocAndGrow(size_t n)
 894 {
 895     HeapSource *hs = gHs;
 896     Heap *heap;
 897     void *ptr;
 898     size_t oldIdealSize;
 899
 900     HS_BOILERPLATE();
 901     heap = hs2heap(hs);
 902
 903     ptr = dvmHeapSourceAlloc(n);
 904     if (ptr != NULL) {
 905         return ptr;
 906     }
 907
 908     oldIdealSize = hs->idealSize;
 909     if (softLimited(hs)) {
 910         /* We're soft-limited.  Try removing the soft limit to
 911          * see if we can allocate without actually growing.
 912          */
 913         hs->softLimit = SIZE_T_MAX;
 914         ptr = dvmHeapSourceAlloc(n);
 915         if (ptr != NULL) {
 916             /* Removing the soft limit worked;  fix things up to
 917              * reflect the new effective ideal size.
 918              */
 919             snapIdealFootprint();
 920             return ptr;
 921         }
 922         // softLimit intentionally left at SIZE_T_MAX.
 923     }
 924
 925     /* We're not soft-limited.  Grow the heap to satisfy the request.
 926      * If this call fails, no footprints will have changed.
 927      */
 928     ptr = heapAllocAndGrow(hs, heap, n);
 929     if (ptr != NULL) {
 930         /* The allocation succeeded.  Fix up the ideal size to
 931          * reflect any footprint modifications that had to happen.
 932          */
 933         snapIdealFootprint();
 934     } else {
 935         /* We just couldn't do it.  Restore the original ideal size,
 936          * fixing up softLimit if necessary.
 937          */
 938         setIdealFootprint(oldIdealSize);
 939     }
 940     return ptr;
 941 }
 942
 943 /*
 944  * Frees the first numPtrs objects in the ptrs list and returns the
 945  * amount of reclaimed storage. The list must contain addresses all in
 946  * the same mspace, and must be in increasing order. This implies that
 947  * there are no duplicates, and no entries are NULL.
 948  */
 949 size_t dvmHeapSourceFreeList(size_t numPtrs, void **ptrs)
 950 {
 951     Heap *heap;
 952     size_t numBytes;
 953
 954     HS_BOILERPLATE();
 955
 956     if (numPtrs == 0) {
 957         return 0;
 958     }
 959
 960     assert(ptrs != NULL);
 961     assert(*ptrs != NULL);
 962     heap = ptr2heap(gHs, *ptrs);
 963     numBytes = 0;
 964     if (heap != NULL) {
 965         mspace *msp = heap->msp;
 966         // Calling mspace_free on shared heaps disrupts sharing too
 967         // much. For heap[0] -- the 'active heap' -- we call
 968         // mspace_free, but on the other heaps we only do some
 969         // accounting.
 970         if (heap == gHs->heaps) {
 971             // mspace_merge_objects takes two allocated objects, and
 972             // if the second immediately follows the first, will merge
 973             // them, returning a larger object occupying the same
 974             // memory. This is a local operation, and doesn't require
 975             // dlmalloc to manipulate any freelists. It's pretty
 976             // inexpensive compared to free().
 977
 978             // ptrs is an array of objects all in memory order, and if
 979             // client code has been allocating lots of short-lived
 980             // objects, this is likely to contain runs of objects all
 981             // now garbage, and thus highly amenable to this optimization.
 982
 983             // Unroll the 0th iteration around the loop below,
 984             // countFree ptrs[0] and initializing merged.
 985             assert(ptrs[0] != NULL);
 986             assert(ptr2heap(gHs, ptrs[0]) == heap);
 987             countFree(heap, ptrs[0], &numBytes);
 988             void *merged = ptrs[0];
 989
 990             size_t i;
 991             for (i = 1; i < numPtrs; i++) {
 992                 assert(merged != NULL);
 993                 assert(ptrs[i] != NULL);
 994                 assert((intptr_t)merged < (intptr_t)ptrs[i]);
 995                 assert(ptr2heap(gHs, ptrs[i]) == heap);
 996                 countFree(heap, ptrs[i], &numBytes);
 997                 // Try to merge. If it works, merged now includes the
 998                 // memory of ptrs[i]. If it doesn't, free merged, and
 999                 // see if ptrs[i] starts a new run of adjacent
1000                 // objects to merge.
1001                 if (mspace_merge_objects(msp, merged, ptrs[i]) == NULL) {
1002                     mspace_free(msp, merged);
1003                     merged = ptrs[i];
1004                 }
1005             }
1006             assert(merged != NULL);
1007             mspace_free(msp, merged);
1008         } else {
1009             // This is not an 'active heap'. Only do the accounting.
1010             size_t i;
1011             for (i = 0; i < numPtrs; i++) {
1012                 assert(ptrs[i] != NULL);
1013                 assert(ptr2heap(gHs, ptrs[i]) == heap);
1014                 countFree(heap, ptrs[i], &numBytes);
1015             }
1016         }
1017     }
1018     return numBytes;
1019 }
1020
1021 /*
1022  * Returns true iff <ptr> is in the heap source.
1023  */
1024 bool
1025 dvmHeapSourceContainsAddress(const void *ptr)
1026 {
1027     HS_BOILERPLATE();
1028
1029     return (dvmHeapBitmapCoversAddress(&gHs->liveBits, ptr));
1030 }
1031
1032 /*
1033  * Returns true iff <ptr> was allocated from the heap source.
1034  */
1035 bool
1036 dvmHeapSourceContains(const void *ptr)
1037 {
1038     HS_BOILERPLATE();
1039
1040     if (dvmHeapSourceContainsAddress(ptr)) {
1041         return dvmHeapBitmapIsObjectBitSet(&gHs->liveBits, ptr) != 0;
1042     }
1043     return false;
1044 }
1045
1046 /*
1047  * Returns the value of the requested flag.
1048  */
1049 bool
1050 dvmHeapSourceGetPtrFlag(const void *ptr, enum HeapSourcePtrFlag flag)
1051 {
1052     if (ptr == NULL) {
1053         return false;
1054     }
1055
1056     if (flag == HS_CONTAINS) {
1057         return dvmHeapSourceContains(ptr);
1058     } else if (flag == HS_ALLOCATED_IN_ZYGOTE) {
1059         HeapSource *hs = gHs;
1060
1061         HS_BOILERPLATE();
1062
1063         if (hs->sawZygote) {
1064             Heap *heap;
1065
1066             heap = ptr2heap(hs, ptr);
1067             if (heap != NULL) {
1068                 /* If the object is not in the active heap, we assume that
1069                  * it was allocated as part of zygote.
1070                  */
1071                 return heap != hs->heaps;
1072             }
1073         }
1074         /* The pointer is outside of any known heap, or we are not
1075          * running in zygote mode.
1076          */
1077         return false;
1078     }
1079
1080     return false;
1081 }
1082
1083 /*
1084  * Returns the number of usable bytes in an allocated chunk; the size
1085  * may be larger than the size passed to dvmHeapSourceAlloc().
1086  */
1087 size_t
1088 dvmHeapSourceChunkSize(const void *ptr)
1089 {
1090     Heap *heap;
1091
1092     HS_BOILERPLATE();
1093
1094     heap = ptr2heap(gHs, ptr);
1095     if (heap != NULL) {
1096         return mspace_usable_size(heap->msp, ptr);
1097     }
1098     return 0;
1099 }
1100
1101 /*
1102  * Returns the number of bytes that the heap source has allocated
1103  * from the system using sbrk/mmap, etc.
1104  *
1105  * Caller must hold the heap lock.
1106  */
1107 size_t
1108 dvmHeapSourceFootprint()
1109 {
1110     HS_BOILERPLATE();
1111
1112 //TODO: include size of bitmaps?
1113     return oldHeapOverhead(gHs, true);
1114 }
1115
1116 /*
1117  * Return the real bytes used by old heaps and external memory
1118  * plus the soft usage of the current heap.  When a soft limit
1119  * is in effect, this is effectively what it's compared against
1120  * (though, in practice, it only looks at the current heap).
1121  */
1122 static size_t
1123 getSoftFootprint(bool includeActive)
1124 {
1125     HeapSource *hs = gHs;
1126     size_t ret;
1127
1128     HS_BOILERPLATE();
1129
1130     ret = oldHeapOverhead(hs, false) + hs->externalBytesAllocated;
1131     if (includeActive) {
1132         ret += hs->heaps[0].bytesAllocated;
1133     }
1134
1135     return ret;
1136 }
1137
1138 /*
1139  * Gets the maximum number of bytes that the heap source is allowed
1140  * to allocate from the system.
1141  */
1142 size_t
1143 dvmHeapSourceGetIdealFootprint()
1144 {
1145     HeapSource *hs = gHs;
1146
1147     HS_BOILERPLATE();
1148
1149     return hs->idealSize;
1150 }
1151
1152 /*
1153  * Sets the soft limit, handling any necessary changes to the allowed
1154  * footprint of the active heap.
1155  */
1156 static void
1157 setSoftLimit(HeapSource *hs, size_t softLimit)
1158 {
1159     /* Compare against the actual footprint, rather than the
1160      * max_allowed, because the heap may not have grown all the
1161      * way to the allowed size yet.
1162      */
1163     mspace msp = hs->heaps[0].msp;
1164     size_t currentHeapSize = mspace_footprint(msp);
1165     if (softLimit < currentHeapSize) {
1166         /* Don't let the heap grow any more, and impose a soft limit.
1167          */
1168         mspace_set_max_allowed_footprint(msp, currentHeapSize);
1169         hs->softLimit = softLimit;
1170     } else {
1171         /* Let the heap grow to the requested max, and remove any
1172          * soft limit, if set.
1173          */
1174         mspace_set_max_allowed_footprint(msp, softLimit);
1175         hs->softLimit = SIZE_T_MAX;
1176     }
1177 }
1178
1179 /*
1180  * Sets the maximum number of bytes that the heap source is allowed
1181  * to allocate from the system.  Clamps to the appropriate maximum
1182  * value.
1183  */
1184 static void
1185 setIdealFootprint(size_t max)
1186 {
1187     HeapSource *hs = gHs;
1188 #if DEBUG_HEAP_SOURCE
1189     HeapSource oldHs = *hs;
1190     mspace msp = hs->heaps[0].msp;
1191     size_t oldAllowedFootprint =
1192             mspace_max_allowed_footprint(msp);
1193 #endif
1194
1195     HS_BOILERPLATE();
1196
1197     if (max > hs->absoluteMaxSize) {
1198         LOGI_HEAP("Clamp target GC heap from %zd.%03zdMB to %u.%03uMB\n",
1199                 FRACTIONAL_MB(max),
1200                 FRACTIONAL_MB(hs->absoluteMaxSize));
1201         max = hs->absoluteMaxSize;
1202     } else if (max < hs->minimumSize) {
1203         max = hs->minimumSize;
1204     }
1205
1206     /* Convert max into a size that applies to the active heap.
1207      * Old heaps and external allocations will count against the ideal size.
1208      */
1209     size_t overhead = getSoftFootprint(false);
1210     size_t activeMax;
1211     if (overhead < max) {
1212         activeMax = max - overhead;
1213     } else {
1214         activeMax = 0;
1215     }
1216
1217     setSoftLimit(hs, activeMax);
1218     hs->idealSize = max;
1219
1220     HSTRACE("IDEAL %zd->%zd (%d), soft %zd->%zd (%d), allowed %zd->%zd (%d), "
1221             "ext %zd\n",
1222             oldHs.idealSize, hs->idealSize, hs->idealSize - oldHs.idealSize,
1223             oldHs.softLimit, hs->softLimit, hs->softLimit - oldHs.softLimit,
1224             oldAllowedFootprint, mspace_max_allowed_footprint(msp),
1225             mspace_max_allowed_footprint(msp) - oldAllowedFootprint,
1226             hs->externalBytesAllocated);
1227
1228 }
1229
1230 /*
1231  * Make the ideal footprint equal to the current footprint.
1232  */
1233 static void
1234 snapIdealFootprint()
1235 {
1236     HS_BOILERPLATE();
1237
1238     setIdealFootprint(getSoftFootprint(true));
1239 }
1240
1241 /*
1242  * Gets the current ideal heap utilization, represented as a number
1243  * between zero and one.
1244  */
1245 float dvmGetTargetHeapUtilization()
1246 {
1247     HeapSource *hs = gHs;
1248
1249     HS_BOILERPLATE();
1250
1251     return (float)hs->targetUtilization / (float)HEAP_UTILIZATION_MAX;
1252 }
1253
1254 /*
1255  * Sets the new ideal heap utilization, represented as a number
1256  * between zero and one.
1257  */
1258 void dvmSetTargetHeapUtilization(float newTarget)
1259 {
1260     HeapSource *hs = gHs;
1261
1262     HS_BOILERPLATE();
1263
1264     /* Clamp it to a reasonable range.
1265      */
1266     // TODO: This may need some tuning.
1267     if (newTarget < 0.2) {
1268         newTarget = 0.2;
1269     } else if (newTarget > 0.8) {
1270         newTarget = 0.8;
1271     }
1272
1273     hs->targetUtilization =
1274             (size_t)(newTarget * (float)HEAP_UTILIZATION_MAX);
1275     LOGV("Set heap target utilization to %zd/%d (%f)\n",
1276             hs->targetUtilization, HEAP_UTILIZATION_MAX, newTarget);
1277 }
1278
1279 /*
1280  * If set is true, sets the new minimum heap size to size; always
1281  * returns the current (or previous) size.  If size is negative,
1282  * removes the current minimum constraint (if present).
1283  */
1284 size_t
1285 dvmMinimumHeapSize(size_t size, bool set)
1286 {
1287     HeapSource *hs = gHs;
1288     size_t oldMinimumSize;
1289
1290     /* gHs caches an entry in gDvm.gcHeap;  we need to hold the
1291      * heap lock if we're going to look at it.  We also need the
1292      * lock for the call to setIdealFootprint().
1293      */
1294     dvmLockHeap();
1295
1296     HS_BOILERPLATE();
1297
1298     oldMinimumSize = hs->minimumSize;
1299
1300     if (set) {
1301         /* Don't worry about external allocations right now.
1302          * setIdealFootprint() will take them into account when
1303          * minimumSize is used, and it's better to hold onto the
1304          * intended minimumSize than to clamp it arbitrarily based
1305          * on the current allocations.
1306          */
1307         if (size > hs->absoluteMaxSize) {
1308             size = hs->absoluteMaxSize;
1309         }
1310         hs->minimumSize = size;
1311         if (size > hs->idealSize) {
1312             /* Force a snap to the minimum value, which we just set
1313              * and which setIdealFootprint() will take into consideration.
1314              */
1315             setIdealFootprint(hs->idealSize);
1316         }
1317         /* Otherwise we'll just keep it in mind the next time
1318          * setIdealFootprint() is called.
1319          */
1320     }
1321
1322     dvmUnlockHeap();
1323
1324     return oldMinimumSize;
1325 }
1326
1327 /*
1328  * Given the size of a live set, returns the ideal heap size given
1329  * the current target utilization and MIN/MAX values.
1330  *
1331  * targetUtilization is in the range 1..HEAP_UTILIZATION_MAX.
1332  */
1333 static size_t
1334 getUtilizationTarget(size_t liveSize, size_t targetUtilization)
1335 {
1336     size_t targetSize;
1337
1338     /* Use the current target utilization ratio to determine the
1339      * ideal heap size based on the size of the live set.
1340      */
1341     targetSize = (liveSize / targetUtilization) * HEAP_UTILIZATION_MAX;
1342
1343     /* Cap the amount of free space, though, so we don't end up
1344      * with, e.g., 8MB of free space when the live set size hits 8MB.
1345      */
1346     if (targetSize > liveSize + HEAP_IDEAL_FREE) {
1347         targetSize = liveSize + HEAP_IDEAL_FREE;
1348     } else if (targetSize < liveSize + HEAP_MIN_FREE) {
1349         targetSize = liveSize + HEAP_MIN_FREE;
1350     }
1351     return targetSize;
1352 }
1353
1354 /*
1355  * Given the current contents of the active heap, increase the allowed
1356  * heap footprint to match the target utilization ratio.  This
1357  * should only be called immediately after a full mark/sweep.
1358  */
1359 void dvmHeapSourceGrowForUtilization()
1360 {
1361     HeapSource *hs = gHs;
1362     Heap *heap;
1363     size_t targetHeapSize;
1364     size_t currentHeapUsed;
1365     size_t oldIdealSize;
1366     size_t newHeapMax;
1367     size_t overhead;
1368     size_t freeBytes;
1369
1370     HS_BOILERPLATE();
1371     heap = hs2heap(hs);
1372
1373     /* Use the current target utilization ratio to determine the
1374      * ideal heap size based on the size of the live set.
1375      * Note that only the active heap plays any part in this.
1376      *
1377      * Avoid letting the old heaps influence the target free size,
1378      * because they may be full of objects that aren't actually
1379      * in the working set.  Just look at the allocated size of
1380      * the current heap.
1381      */
1382     currentHeapUsed = heap->bytesAllocated;
1383 #define LET_EXTERNAL_INFLUENCE_UTILIZATION 1
1384 #if LET_EXTERNAL_INFLUENCE_UTILIZATION
1385     /* This is a hack to deal with the side-effects of moving
1386      * bitmap data out of the Dalvik heap.  Since the amount
1387      * of free space after a GC scales with the size of the
1388      * live set, many apps expected the large free space that
1389      * appeared along with megabytes' worth of bitmaps.  When
1390      * the bitmaps were removed, the free size shrank significantly,
1391      * and apps started GCing constantly.  This makes it so the
1392      * post-GC free space is the same size it would have been
1393      * if the bitmaps were still in the Dalvik heap.
1394      */
1395     currentHeapUsed += hs->externalBytesAllocated;
1396 #endif
1397     targetHeapSize =
1398             getUtilizationTarget(currentHeapUsed, hs->targetUtilization);
1399 #if LET_EXTERNAL_INFLUENCE_UTILIZATION
1400     currentHeapUsed -= hs->externalBytesAllocated;
1401     targetHeapSize -= hs->externalBytesAllocated;
1402 #endif
1403
1404     /* The ideal size includes the old heaps; add overhead so that
1405      * it can be immediately subtracted again in setIdealFootprint().
1406      * If the target heap size would exceed the max, setIdealFootprint()
1407      * will clamp it to a legal value.
1408      */
1409     overhead = getSoftFootprint(false);
1410     oldIdealSize = hs->idealSize;
1411     setIdealFootprint(targetHeapSize + overhead);
1412
1413     freeBytes = getAllocLimit(hs);
1414     if (freeBytes < CONCURRENT_MIN_FREE) {
1415         /* Not enough free memory to allow a concurrent GC. */
1416         heap->concurrentStartBytes = SIZE_T_MAX;
1417     } else {
1418         heap->concurrentStartBytes = freeBytes - CONCURRENT_START;
1419     }
1420     newHeapMax = mspace_max_allowed_footprint(heap->msp);
1421     if (softLimited(hs)) {
1422         LOGD_HEAP("GC old usage %zd.%zd%%; now "
1423                 "%zd.%03zdMB used / %zd.%03zdMB soft max "
1424                 "(%zd.%03zdMB over, "
1425                 "%zd.%03zdMB ext, "
1426                 "%zd.%03zdMB real max)\n",
1427                 FRACTIONAL_PCT(currentHeapUsed, oldIdealSize),
1428                 FRACTIONAL_MB(currentHeapUsed),
1429                 FRACTIONAL_MB(hs->softLimit),
1430                 FRACTIONAL_MB(overhead),
1431                 FRACTIONAL_MB(hs->externalBytesAllocated),
1432                 FRACTIONAL_MB(newHeapMax));
1433     } else {
1434         LOGD_HEAP("GC old usage %zd.%zd%%; now "
1435                 "%zd.%03zdMB used / %zd.%03zdMB real max "
1436                 "(%zd.%03zdMB over, "
1437                 "%zd.%03zdMB ext)\n",
1438                 FRACTIONAL_PCT(currentHeapUsed, oldIdealSize),
1439                 FRACTIONAL_MB(currentHeapUsed),
1440                 FRACTIONAL_MB(newHeapMax),
1441                 FRACTIONAL_MB(overhead),
1442                 FRACTIONAL_MB(hs->externalBytesAllocated));
1443     }
1444 }
1445
1446 /*
1447  * Return free pages to the system.
1448  * TODO: move this somewhere else, especially the native heap part.
1449  */
1450
1451 static void releasePagesInRange(void *start, void *end, void *nbytes)
1452 {
1453     /* Linux requires that the madvise() start address is page-aligned.
1454     * We also align the end address.
1455     */
1456     start = (void *)ALIGN_UP_TO_PAGE_SIZE(start);
1457     end = (void *)((size_t)end & ~(SYSTEM_PAGE_SIZE - 1));
1458     if (start < end) {
1459         size_t length = (char *)end - (char *)start;
1460         madvise(start, length, MADV_DONTNEED);
1461         *(size_t *)nbytes += length;
1462     }
1463 }
1464
1465 /*
1466  * Return unused memory to the system if possible.
1467  */
1468 void
1469 dvmHeapSourceTrim(size_t bytesTrimmed[], size_t arrayLen)
1470 {
1471     HeapSource *hs = gHs;
1472     size_t nativeBytes, heapBytes;
1473     size_t i;
1474
1475     HS_BOILERPLATE();
1476
1477     assert(arrayLen >= hs->numHeaps);
1478
1479     heapBytes = 0;
1480     for (i = 0; i < hs->numHeaps; i++) {
1481         Heap *heap = &hs->heaps[i];
1482
1483         /* Return the wilderness chunk to the system.
1484          */
1485         mspace_trim(heap->msp, 0);
1486
1487         /* Return any whole free pages to the system.
1488          */
1489         bytesTrimmed[i] = 0;
1490         mspace_walk_free_pages(heap->msp, releasePagesInRange,
1491                                &bytesTrimmed[i]);
1492         heapBytes += bytesTrimmed[i];
1493     }
1494
1495     /* Same for the native heap.
1496      */
1497     dlmalloc_trim(0);
1498     nativeBytes = 0;
1499     dlmalloc_walk_free_pages(releasePagesInRange, &nativeBytes);
1500
1501     LOGD_HEAP("madvised %zd (GC) + %zd (native) = %zd total bytes\n",
1502             heapBytes, nativeBytes, heapBytes + nativeBytes);
1503 }
1504
1505 /*
1506  * Walks over the heap source and passes every allocated and
1507  * free chunk to the callback.
1508  */
1509 void
1510 dvmHeapSourceWalk(void(*callback)(const void *chunkptr, size_t chunklen,
1511                                       const void *userptr, size_t userlen,
1512                                       void *arg),
1513                   void *arg)
1514 {
1515     HeapSource *hs = gHs;
1516     size_t i;
1517
1518     HS_BOILERPLATE();
1519
1520     /* Walk the heaps from oldest to newest.
1521      */
1522 //TODO: do this in address order
1523     for (i = hs->numHeaps; i > 0; --i) {
1524         mspace_walk_heap(hs->heaps[i-1].msp, callback, arg);
1525     }
1526 }
1527
1528 /*
1529  * Gets the number of heaps available in the heap source.
1530  *
1531  * Caller must hold the heap lock, because gHs caches a field
1532  * in gDvm.gcHeap.
1533  */
1534 size_t
1535 dvmHeapSourceGetNumHeaps()
1536 {
1537     HeapSource *hs = gHs;
1538
1539     HS_BOILERPLATE();
1540
1541     return hs->numHeaps;
1542 }
1543
1544
1545 /*
1546  * External allocation tracking
1547  *
1548  * In some situations, memory outside of the heap is tied to the
1549  * lifetime of objects in the heap.  Since that memory is kept alive
1550  * by heap objects, it should provide memory pressure that can influence
1551  * GCs.
1552  */
1553
1554
1555 static bool
1556 externalAllocPossible(const HeapSource *hs, size_t n)
1557 {
1558     const Heap *heap;
1559     size_t currentHeapSize;
1560
1561     /* Make sure that this allocation is even possible.
1562      * Don't let the external size plus the actual heap size
1563      * go over the absolute max.  This essentially treats
1564      * external allocations as part of the active heap.
1565      *
1566      * Note that this will fail "mysteriously" if there's
1567      * a small softLimit but a large heap footprint.
1568      */
1569     heap = hs2heap(hs);
1570     currentHeapSize = mspace_max_allowed_footprint(heap->msp);
1571     if (currentHeapSize + hs->externalBytesAllocated + n <=
1572             heap->absoluteMaxSize)
1573     {
1574         return true;
1575     }
1576     HSTRACE("externalAllocPossible(): "
1577             "footprint %zu + extAlloc %zu + n %zu >= max %zu (space for %zu)\n",
1578             currentHeapSize, hs->externalBytesAllocated, n,
1579             heap->absoluteMaxSize,
1580             heap->absoluteMaxSize -
1581                     (currentHeapSize + hs->externalBytesAllocated));
1582     return false;
1583 }
1584
1585 #define EXTERNAL_TARGET_UTILIZATION 820  // 80%
1586
1587 /*
1588  * Tries to update the internal count of externally-allocated memory.
1589  * If there's enough room for that memory, returns true.  If not, returns
1590  * false and does not update the count.
1591  *
1592  * The caller must ensure externalAllocPossible(hs, n) == true.
1593  */
1594 static bool
1595 externalAlloc(HeapSource *hs, size_t n, bool grow)
1596 {
1597     assert(hs->externalLimit >= hs->externalBytesAllocated);
1598
1599     HSTRACE("externalAlloc(%zd%s)\n", n, grow ? ", grow" : "");
1600     assert(externalAllocPossible(hs, n));  // The caller must ensure this.
1601
1602     /* External allocations have their own "free space" that they
1603      * can allocate from without causing a GC.
1604      */
1605     if (hs->externalBytesAllocated + n <= hs->externalLimit) {
1606         hs->externalBytesAllocated += n;
1607 #if PROFILE_EXTERNAL_ALLOCATIONS
1608         if (gDvm.allocProf.enabled) {
1609             Thread* self = dvmThreadSelf();
1610             gDvm.allocProf.externalAllocCount++;
1611             gDvm.allocProf.externalAllocSize += n;
1612             if (self != NULL) {
1613                 self->allocProf.externalAllocCount++;
1614                 self->allocProf.externalAllocSize += n;
1615             }
1616         }
1617 #endif
1618         return true;
1619     }
1620     if (!grow) {
1621         return false;
1622     }
1623
1624     /* GROW */
1625     hs->externalBytesAllocated += n;
1626     hs->externalLimit = getUtilizationTarget(
1627             hs->externalBytesAllocated, EXTERNAL_TARGET_UTILIZATION);
1628     HSTRACE("EXTERNAL grow limit to %zd\n", hs->externalLimit);
1629     return true;
1630 }
1631
1632 static void
1633 gcForExternalAlloc(bool collectSoftReferences)
1634 {
1635     if (gDvm.allocProf.enabled) {
1636         Thread* self = dvmThreadSelf();
1637         gDvm.allocProf.gcCount++;
1638         if (self != NULL) {
1639             self->allocProf.gcCount++;
1640         }
1641     }
1642     dvmCollectGarbageInternal(collectSoftReferences, GC_EXTERNAL_ALLOC);
1643 }
1644
1645 /*
1646  * Updates the internal count of externally-allocated memory.  If there's
1647  * enough room for that memory, returns true.  If not, returns false and
1648  * does not update the count.
1649  *
1650  * May cause a GC as a side-effect.
1651  */
1652 bool
1653 dvmTrackExternalAllocation(size_t n)
1654 {
1655     HeapSource *hs = gHs;
1656     bool ret = false;
1657
1658     /* gHs caches an entry in gDvm.gcHeap;  we need to hold the
1659      * heap lock if we're going to look at it.
1660      */
1661     dvmLockHeap();
1662
1663     HS_BOILERPLATE();
1664     assert(hs->externalLimit >= hs->externalBytesAllocated);
1665
1666     if (!externalAllocPossible(hs, n)) {
1667         LOGE_HEAP("%zd-byte external allocation "
1668                 "too large for this process.\n", n);
1669         goto out;
1670     }
1671
1672     /* Try "allocating" using the existing "free space".
1673      */
1674     HSTRACE("EXTERNAL alloc %zu (%zu < %zu)\n",
1675             n, hs->externalBytesAllocated, hs->externalLimit);
1676     if (externalAlloc(hs, n, false)) {
1677         ret = true;
1678         goto out;
1679     }
1680
1681     if (gDvm.gcHeap->gcRunning) {
1682         /*
1683          * The GC is concurrently tracing the heap.  Release the heap
1684          * lock, wait for the GC to complete, and try again.
1685          */
1686         dvmWaitForConcurrentGcToComplete();
1687         if (externalAlloc(hs, n, false)) {
1688             ret = true;
1689             goto out;
1690         }
1691     }
1692
1693     /* The "allocation" failed.  Free up some space by doing
1694      * a full garbage collection.  This may grow the heap source
1695      * if the live set is sufficiently large.
1696      */
1697     HSTRACE("EXTERNAL alloc %zd: GC 1\n", n);
1698     gcForExternalAlloc(false);  // don't collect SoftReferences
1699     if (externalAlloc(hs, n, false)) {
1700         ret = true;
1701         goto out;
1702     }
1703
1704     /* Even that didn't work;  this is an exceptional state.
1705      * Try harder, growing the heap source if necessary.
1706      */
1707     HSTRACE("EXTERNAL alloc %zd: frag\n", n);
1708     ret = externalAlloc(hs, n, true);
1709     if (ret) {
1710         goto out;
1711     }
1712
1713     /* We couldn't even grow enough to satisfy the request.
1714      * Try one last GC, collecting SoftReferences this time.
1715      */
1716     HSTRACE("EXTERNAL alloc %zd: GC 2\n", n);
1717     gcForExternalAlloc(true);  // collect SoftReferences
1718     ret = externalAlloc(hs, n, true);
1719     if (!ret) {
1720         LOGE_HEAP("Out of external memory on a %zu-byte allocation.\n", n);
1721     }
1722
1723 #if PROFILE_EXTERNAL_ALLOCATIONS
1724     if (gDvm.allocProf.enabled) {
1725         Thread* self = dvmThreadSelf();
1726         gDvm.allocProf.failedExternalAllocCount++;
1727         gDvm.allocProf.failedExternalAllocSize += n;
1728         if (self != NULL) {
1729             self->allocProf.failedExternalAllocCount++;
1730             self->allocProf.failedExternalAllocSize += n;
1731         }
1732     }
1733 #endif
1734
1735 out:
1736     dvmUnlockHeap();
1737
1738     return ret;
1739 }
1740
1741 /*
1742  * Reduces the internal count of externally-allocated memory.
1743  */
1744 void
1745 dvmTrackExternalFree(size_t n)
1746 {
1747     HeapSource *hs = gHs;
1748     size_t newExternalLimit;
1749     size_t oldExternalBytesAllocated;
1750
1751     HSTRACE("EXTERNAL free %zu (%zu < %zu)\n",
1752             n, hs->externalBytesAllocated, hs->externalLimit);
1753
1754     /* gHs caches an entry in gDvm.gcHeap;  we need to hold the
1755      * heap lock if we're going to look at it.
1756      */
1757     dvmLockHeap();
1758
1759     HS_BOILERPLATE();
1760     assert(hs->externalLimit >= hs->externalBytesAllocated);
1761
1762     oldExternalBytesAllocated = hs->externalBytesAllocated;
1763     if (n <= hs->externalBytesAllocated) {
1764         hs->externalBytesAllocated -= n;
1765     } else {
1766         n = hs->externalBytesAllocated;
1767         hs->externalBytesAllocated = 0;
1768     }
1769
1770 #if PROFILE_EXTERNAL_ALLOCATIONS
1771     if (gDvm.allocProf.enabled) {
1772         Thread* self = dvmThreadSelf();
1773         gDvm.allocProf.externalFreeCount++;
1774         gDvm.allocProf.externalFreeSize += n;
1775         if (self != NULL) {
1776             self->allocProf.externalFreeCount++;
1777             self->allocProf.externalFreeSize += n;
1778         }
1779     }
1780 #endif
1781
1782     /* Shrink as quickly as we can.
1783      */
1784     newExternalLimit = getUtilizationTarget(
1785             hs->externalBytesAllocated, EXTERNAL_TARGET_UTILIZATION);
1786     if (newExternalLimit < oldExternalBytesAllocated) {
1787         /* Make sure that the remaining free space is at least
1788          * big enough to allocate something of the size that was
1789          * just freed.  This makes it more likely that
1790          *     externalFree(N); externalAlloc(N);
1791          * will work without causing a GC.
1792          */
1793         HSTRACE("EXTERNAL free preserved %zu extra free bytes\n",
1794                 oldExternalBytesAllocated - newExternalLimit);
1795         newExternalLimit = oldExternalBytesAllocated;
1796     }
1797     if (newExternalLimit < hs->externalLimit) {
1798         hs->externalLimit = newExternalLimit;
1799     }
1800
1801     dvmUnlockHeap();
1802 }
1803
1804 /*
1805  * Returns the number of externally-allocated bytes being tracked by
1806  * dvmTrackExternalAllocation/Free().
1807  */
1808 size_t
1809 dvmGetExternalBytesAllocated()
1810 {
1811     const HeapSource *hs = gHs;
1812     size_t ret;
1813
1814     /* gHs caches an entry in gDvm.gcHeap;  we need to hold the
1815      * heap lock if we're going to look at it.  We also need the
1816      * lock for the call to setIdealFootprint().
1817      */
1818     dvmLockHeap();
1819     HS_BOILERPLATE();
1820     ret = hs->externalBytesAllocated;
1821     dvmUnlockHeap();
1822
1823     return ret;
1824 }
1825
1826 void *dvmHeapSourceGetImmuneLimit(GcMode mode)
1827 {
1828     if (mode == GC_PARTIAL) {
1829         return hs2heap(gHs)->base;
1830     } else {
1831         return NULL;
1832     }
1833 }