text: /*
   * Copyright (C) 2008 The Android Open Source Project
   *
   * Licensed under the Apache License, Version 2.0 (the "License");
   * you may not use this file except in compliance with the License.
   * You may obtain a copy of the License at
   *
   *      http://www.apache.org/licenses/LICENSE-2.0
   *
   * Unless required by applicable law or agreed to in writing, software
   * distributed under the License is distributed on an "AS IS" BASIS,
   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   * See the License for the specific language governing permissions and
   * limitations under the License.
   */
  
  #include <stdint.h>
  #include <sys/mman.h>
  #include <errno.h>
  #include <cutils/ashmem.h>
  
  #define SIZE_MAX UINT_MAX  // TODO: get SIZE_MAX from stdint.h
  
  #include "Dalvik.h"
  #include "alloc/DlMalloc.h"
  #include "alloc/Heap.h"
  #include "alloc/HeapInternal.h"
  #include "alloc/HeapSource.h"
  #include "alloc/HeapBitmap.h"
  #include "alloc/HeapBitmapInlines.h"
  
  static void dvmHeapSourceUpdateMaxNativeFootprint();
  static void snapIdealFootprint();
  static void setIdealFootprint(size_t max);
  static size_t getMaximumSize(const HeapSource *hs);
  static void trimHeaps();
  
  #define HEAP_UTILIZATION_MAX        1024
  
  /* How long to wait after a GC before performing a heap trim
   * operation to reclaim unused pages.
   */
  #define HEAP_TRIM_IDLE_TIME_MS (5 * 1000)
  
  /* Start a concurrent collection when free memory falls under this
   * many bytes.
   */
  #define CONCURRENT_START (128 << 10)
  
  /* The next GC will not be concurrent when free memory after a GC is
   * under this many bytes.
   */
  #define CONCURRENT_MIN_FREE (CONCURRENT_START + (128 << 10))
  
  #define HS_BOILERPLATE() \
      do { \
          assert(gDvm.gcHeap != NULL); \
          assert(gDvm.gcHeap->heapSource != NULL); \
          assert(gHs == gDvm.gcHeap->heapSource); \
      } while (0)
  
  struct Heap {
      /* The mspace to allocate from.
       */
      mspace msp;
  
      /* The largest size that this heap is allowed to grow to.
       */
      size_t maximumSize;
  
      /* Number of bytes allocated from this mspace for objects,
       * including any overhead.  This value is NOT exact, and
       * should only be used as an input for certain heuristics.
       */
      size_t bytesAllocated;
  
      /* Number of bytes allocated from this mspace at which a
       * concurrent garbage collection will be started.
       */
      size_t concurrentStartBytes;
  
      /* Number of objects currently allocated from this mspace.
       */
      size_t objectsAllocated;
  
      /*
       * The lowest address of this heap, inclusive.
       */
      char *base;
  
      /*
       * The highest address of this heap, exclusive.
       */
      char *limit;
  
      /*
       * If the heap has an mspace, the current high water mark in
       * allocations requested via dvmHeapSourceMorecore.
       */
      char *brk;
  };
  
  struct HeapSource {
      /* Target ideal heap utilization ratio; range 1..HEAP_UTILIZATION_MAX
       */
      size_t targetUtilization;
  
      /* The starting heap size.
       */
      size_t startSize;
  
      /* The largest that the heap source as a whole is allowed to grow.
       */
      size_t maximumSize;
  
      /*
       * The largest size we permit the heap to grow.  This value allows
       * the user to limit the heap growth below the maximum size.  This
       * is a work around until we can dynamically set the maximum size.
       * This value can range between the starting size and the maximum
       * size but should never be set below the current footprint of the
       * heap.
       */
      size_t growthLimit;
  
      /* The desired max size of the heap source as a whole.
       */
      size_t idealSize;
  
      /* The maximum number of bytes allowed to be allocated from the
       * active heap before a GC is forced.  This is used to "shrink" the
       * heap in lieu of actual compaction.
       */
      size_t softLimit;
  
      /* Minimum number of free bytes. Used with the target utilization when
       * setting the softLimit. Never allows less bytes than this to be free
       * when the heap size is below the maximum size or growth limit.
       */
      size_t minFree;
  
      /* Maximum number of free bytes. Used with the target utilization when
       * setting the softLimit. Never allows more bytes than this to be free
       * when the heap size is below the maximum size or growth limit.
       */
      size_t maxFree;
  
      /* The heaps; heaps[0] is always the active heap,
       * which new objects should be allocated from.
       */
      Heap heaps[HEAP_SOURCE_MAX_HEAP_COUNT];
  
      /* The current number of heaps.
       */
      size_t numHeaps;
  
      /* True if zygote mode was active when the HeapSource was created.
       */
      bool sawZygote;
  
      /*
       * The base address of the virtual memory reservation.
       */
      char *heapBase;
  
      /*
       * The length in bytes of the virtual memory reservation.
       */
      size_t heapLength;
  
      /*
       * The live object bitmap.
       */
      HeapBitmap liveBits;
  
      /*
       * The mark bitmap.
       */
      HeapBitmap markBits;
  
      /*
       * Native allocations.
       */
      int32_t nativeBytesAllocated;
      size_t nativeFootprintGCWatermark;
      size_t nativeFootprintLimit;
      bool nativeNeedToRunFinalization;
  
      /*
       * State for the GC daemon.
       */
      bool hasGcThread;
      pthread_t gcThread;
      bool gcThreadShutdown;
      pthread_mutex_t gcThreadMutex;
      pthread_cond_t gcThreadCond;
      bool gcThreadTrimNeeded;
  };
  
  #define hs2heap(hs_) (&((hs_)->heaps[0]))
  
  /*
   * Returns true iff a soft limit is in effect for the active heap.
   */
  static bool isSoftLimited(const HeapSource *hs)
  {
      /* softLimit will be either SIZE_MAX or the limit for the
       * active mspace.  idealSize can be greater than softLimit
       * if there is more than one heap.  If there is only one
       * heap, a non-SIZE_MAX softLimit should always be the same
       * as idealSize.
       */
      return hs->softLimit <= hs->idealSize;
  }
  
  /*
   * Returns approximately the maximum number of bytes allowed to be
   * allocated from the active heap before a GC is forced.
   */
  static size_t getAllocLimit(const HeapSource *hs)
  {
      if (isSoftLimited(hs)) {
          return hs->softLimit;
      } else {
          return mspace_footprint_limit(hs2heap(hs)->msp);
      }
  }
  
  /*
   * Returns the current footprint of all heaps.  If includeActive
   * is false, don't count the heap at index 0.
   */
  static size_t oldHeapOverhead(const HeapSource *hs, bool includeActive)
  {
      size_t footprint = 0;
      size_t i;
  
      if (includeActive) {
          i = 0;
      } else {
          i = 1;
      }
      for (/* i = i */; i < hs->numHeaps; i++) {
  //TODO: include size of bitmaps?  If so, don't use bitsLen, listen to .max
          footprint += mspace_footprint(hs->heaps[i].msp);
      }
      return footprint;
  }
  
  /*
   * Returns the heap that <ptr> could have come from, or NULL
   * if it could not have come from any heap.
   */
  static Heap *ptr2heap(const HeapSource *hs, const void *ptr)
  {
      const size_t numHeaps = hs->numHeaps;
  
      if (ptr != NULL) {
          for (size_t i = 0; i < numHeaps; i++) {
              const Heap *const heap = &hs->heaps[i];
  
              if ((const char *)ptr >= heap->base && (const char *)ptr < heap->limit) {
                  return (Heap *)heap;
              }
          }
      }
      return NULL;
  }
  
  /*
   * Functions to update heapSource->bytesAllocated when an object
   * is allocated or freed.  mspace_usable_size() will give
   * us a much more accurate picture of heap utilization than
   * the requested byte sizes would.
   *
   * These aren't exact, and should not be treated as such.
   */
  static void countAllocation(Heap *heap, const void *ptr)
  {
      assert(heap->bytesAllocated < mspace_footprint(heap->msp));
  
      heap->bytesAllocated += mspace_usable_size(ptr) +
              HEAP_SOURCE_CHUNK_OVERHEAD;
      heap->objectsAllocated++;
      HeapSource* hs = gDvm.gcHeap->heapSource;
      dvmHeapBitmapSetObjectBit(&hs->liveBits, ptr);
  
      assert(heap->bytesAllocated < mspace_footprint(heap->msp));
  }
  
  static void countFree(Heap *heap, const void *ptr, size_t *numBytes)
  {
      size_t delta = mspace_usable_size(ptr) + HEAP_SOURCE_CHUNK_OVERHEAD;
      assert(delta > 0);
      if (delta < heap->bytesAllocated) {
          heap->bytesAllocated -= delta;
      } else {
          heap->bytesAllocated = 0;
      }
      HeapSource* hs = gDvm.gcHeap->heapSource;
      dvmHeapBitmapClearObjectBit(&hs->liveBits, ptr);
      if (heap->objectsAllocated > 0) {
          heap->objectsAllocated--;
      }
      *numBytes += delta;
  }
  
  static HeapSource *gHs = NULL;
  
  static mspace createMspace(void* begin, size_t morecoreStart, size_t startingSize)
  {
      // Clear errno to allow strerror on error.
      errno = 0;
      // Allow access to inital pages that will hold mspace.
      mprotect(begin, morecoreStart, PROT_READ | PROT_WRITE);
      // Create mspace using our backing storage starting at begin and with a footprint of
      // morecoreStart. Don't use an internal dlmalloc lock. When morecoreStart bytes of memory are
      // exhausted morecore will be called.
      mspace msp = create_mspace_with_base(begin, morecoreStart, false /*locked*/);
      if (msp != NULL) {
          // Do not allow morecore requests to succeed beyond the starting size of the heap.
          mspace_set_footprint_limit(msp, startingSize);
      } else {
          ALOGE("create_mspace_with_base failed %s", strerror(errno));
      }
      return msp;
  }
  
  /*
   * Service request from DlMalloc to increase heap size.
   */
  void* dvmHeapSourceMorecore(void* mspace, intptr_t increment)
  {
      Heap* heap = NULL;
      for (size_t i = 0; i < gHs->numHeaps; i++) {
          if (gHs->heaps[i].msp == mspace) {
              heap = &gHs->heaps[i];
              break;
          }
      }
      if (heap == NULL) {
          ALOGE("Failed to find heap for mspace %p", mspace);
          dvmAbort();
      }
      char* original_brk = heap->brk;
      if (increment != 0) {
          char* new_brk = original_brk + increment;
          if (increment > 0) {
              // Should never be asked to increase the allocation beyond the capacity of the space.
              // Enforced by mspace_set_footprint_limit.
              assert(new_brk <= heap->limit);
              mprotect(original_brk, increment, PROT_READ | PROT_WRITE);
          } else {
              // Should never be asked for negative footprint (ie before base).
              assert(original_brk + increment > heap->base);
              // Advise we don't need the pages and protect them.
              size_t size = -increment;
              madvise(new_brk, size, MADV_DONTNEED);
              mprotect(new_brk, size, PROT_NONE);
          }
          // Update brk.
          heap->brk = new_brk;
      }
      return original_brk;
  }
  
  const size_t kInitialMorecoreStart = SYSTEM_PAGE_SIZE;
  /*
   * Add the initial heap.  Returns false if the initial heap was
   * already added to the heap source.
   */
  static bool addInitialHeap(HeapSource *hs, mspace msp, size_t maximumSize)
  {
      assert(hs != NULL);
      assert(msp != NULL);
      if (hs->numHeaps != 0) {
          return false;
      }
      hs->heaps[0].msp = msp;
      hs->heaps[0].maximumSize = maximumSize;
      hs->heaps[0].concurrentStartBytes = SIZE_MAX;
      hs->heaps[0].base = hs->heapBase;
      hs->heaps[0].limit = hs->heapBase + maximumSize;
      hs->heaps[0].brk = hs->heapBase + kInitialMorecoreStart;
      hs->numHeaps = 1;
      return true;
  }
  
  /*
   * A helper for addNewHeap(). Remap the new heap so that it will have
   * a separate ashmem region with possibly a different name, etc. In
   * practice, this is used to give the app heap a separate ashmem
   * region from the zygote heap's.
   */
  static bool remapNewHeap(HeapSource* hs, Heap* newHeap)
  {
    char* newHeapBase = newHeap->base;
    size_t rem_size = hs->heapBase + hs->heapLength - newHeapBase;
    munmap(newHeapBase, rem_size);
    int fd = ashmem_create_region("dalvik-heap", rem_size);
    if (fd == -1) {
      ALOGE("Unable to create an ashmem region for the new heap");
      return false;
    }
    void* addr = mmap(newHeapBase, rem_size, PROT_READ | PROT_WRITE, MAP_PRIVATE, fd, 0);
    int ret = close(fd);
    if (addr == MAP_FAILED) {
      ALOGE("Unable to map an ashmem region for the new heap");
      return false;
    }
    if (ret == -1) {
      ALOGE("Unable to close fd for the ashmem region for the new heap");
      munmap(newHeapBase, rem_size);
      return false;
    }
    return true;
  }
  
  /*
   * Adds an additional heap to the heap source.  Returns false if there
   * are too many heaps or insufficient free space to add another heap.
   */
  static bool addNewHeap(HeapSource *hs)
  {
      Heap heap;
  
      assert(hs != NULL);
      if (hs->numHeaps >= HEAP_SOURCE_MAX_HEAP_COUNT) {
          ALOGE("Attempt to create too many heaps (%zd >= %zd)",
                  hs->numHeaps, HEAP_SOURCE_MAX_HEAP_COUNT);
          dvmAbort();
          return false;
      }
  
      memset(&heap, 0, sizeof(heap));
  
      /*
       * Heap storage comes from a common virtual memory reservation.
       * The new heap will start on the page after the old heap.
       */
      char *base = hs->heaps[0].brk;
      size_t overhead = base - hs->heaps[0].base;
      assert(((size_t)hs->heaps[0].base & (SYSTEM_PAGE_SIZE - 1)) == 0);
  
      if (overhead + hs->minFree >= hs->maximumSize) {
          LOGE_HEAP("No room to create any more heaps "
                    "(%zd overhead, %zd max)",
                    overhead, hs->maximumSize);
          return false;
      }
      size_t morecoreStart = SYSTEM_PAGE_SIZE;
      heap.maximumSize = hs->growthLimit - overhead;
      heap.concurrentStartBytes = hs->minFree - CONCURRENT_START;
      heap.base = base;
      heap.limit = heap.base + heap.maximumSize;
      heap.brk = heap.base + morecoreStart;
      if (!remapNewHeap(hs, &heap)) {
        return false;
      }
      heap.msp = createMspace(base, morecoreStart, hs->minFree);
      if (heap.msp == NULL) {
          return false;
      }
  
      /* Don't let the soon-to-be-old heap grow any further.
       */
      hs->heaps[0].maximumSize = overhead;
      hs->heaps[0].limit = base;
      mspace_set_footprint_limit(hs->heaps[0].msp, overhead);
  
      /* Put the new heap in the list, at heaps[0].
       * Shift existing heaps down.
       */
      memmove(&hs->heaps[1], &hs->heaps[0], hs->numHeaps * sizeof(hs->heaps[0]));
      hs->heaps[0] = heap;
      hs->numHeaps++;
  
      return true;
  }
  
  /*
   * The garbage collection daemon.  Initiates a concurrent collection
   * when signaled.  Also periodically trims the heaps when a few seconds
   * have elapsed since the last concurrent GC.
   */
  static void *gcDaemonThread(void* arg)
  {
      dvmChangeStatus(NULL, THREAD_VMWAIT);
      dvmLockMutex(&gHs->gcThreadMutex);
      while (gHs->gcThreadShutdown != true) {
          bool trim = false;
          if (gHs->gcThreadTrimNeeded) {
              int result = dvmRelativeCondWait(&gHs->gcThreadCond, &gHs->gcThreadMutex,
                      HEAP_TRIM_IDLE_TIME_MS, 0);
              if (result == ETIMEDOUT) {
                  /* Timed out waiting for a GC request, schedule a heap trim. */
                  trim = true;
              }
          } else {
              dvmWaitCond(&gHs->gcThreadCond, &gHs->gcThreadMutex);
          }
  
          // Many JDWP requests cause allocation. We can't take the heap lock and wait to
          // transition to runnable so we can start a GC if a debugger is connected, because
          // we don't know that the JDWP thread isn't about to allocate and require the
          // heap lock itself, leading to deadlock. http://b/8191824.
          if (gDvm.debuggerConnected) {
              continue;
          }
  
          dvmLockHeap();
          /*
           * Another thread may have started a concurrent garbage
           * collection before we were scheduled.  Check for this
           * condition before proceeding.
           */
          if (!gDvm.gcHeap->gcRunning) {
              dvmChangeStatus(NULL, THREAD_RUNNING);
              if (trim) {
                  trimHeaps();
                  gHs->gcThreadTrimNeeded = false;
              } else {
                  dvmCollectGarbageInternal(GC_CONCURRENT);
                  gHs->gcThreadTrimNeeded = true;
              }
              dvmChangeStatus(NULL, THREAD_VMWAIT);
          }
          dvmUnlockHeap();
      }
      dvmChangeStatus(NULL, THREAD_RUNNING);
      return NULL;
  }
  
  static bool gcDaemonStartup()
  {
      dvmInitMutex(&gHs->gcThreadMutex);
      pthread_cond_init(&gHs->gcThreadCond, NULL);
      gHs->gcThreadShutdown = false;
      gHs->hasGcThread = dvmCreateInternalThread(&gHs->gcThread, "GC",
                                                 gcDaemonThread, NULL);
      return gHs->hasGcThread;
  }
  
  static void gcDaemonShutdown()
  {
      if (gHs->hasGcThread) {
          dvmLockMutex(&gHs->gcThreadMutex);
          gHs->gcThreadShutdown = true;
          dvmSignalCond(&gHs->gcThreadCond);
          dvmUnlockMutex(&gHs->gcThreadMutex);
          pthread_join(gHs->gcThread, NULL);
      }
  }
  
  /*
   * Create a stack big enough for the worst possible case, where the
   * heap is perfectly full of the smallest object.
   * TODO: be better about memory usage; use a smaller stack with
   *       overflow detection and recovery.
   */
  static bool allocMarkStack(GcMarkStack *stack, size_t maximumSize)
  {
      const char *name = "dalvik-mark-stack";
      void *addr;
  
      assert(stack != NULL);
      stack->length = maximumSize * sizeof(Object*) /
          (sizeof(Object) + HEAP_SOURCE_CHUNK_OVERHEAD);
      addr = dvmAllocRegion(stack->length, PROT_READ | PROT_WRITE, name);
      if (addr == NULL) {
          return false;
      }
      stack->base = (const Object **)addr;
      stack->limit = (const Object **)((char *)addr + stack->length);
      stack->top = NULL;
      madvise(stack->base, stack->length, MADV_DONTNEED);
      return true;
  }
  
  static void freeMarkStack(GcMarkStack *stack)
  {
      assert(stack != NULL);
      munmap(stack->base, stack->length);
      memset(stack, 0, sizeof(*stack));
  }
  
  /*
   * Initializes the heap source; must be called before any other
   * dvmHeapSource*() functions.  Returns a GcHeap structure
   * allocated from the heap source.
   */
  GcHeap* dvmHeapSourceStartup(size_t startSize, size_t maximumSize,
                               size_t growthLimit)
  {
      GcHeap *gcHeap;
      HeapSource *hs;
      mspace msp;
      size_t length;
      void *base;
  
      assert(gHs == NULL);
  
      if (!(startSize <= growthLimit && growthLimit <= maximumSize)) {
          ALOGE("Bad heap size parameters (start=%zd, max=%zd, limit=%zd)",
               startSize, maximumSize, growthLimit);
          return NULL;
      }
  
      /*
       * Allocate a contiguous region of virtual memory to subdivided
       * among the heaps managed by the garbage collector.
       */
      length = ALIGN_UP_TO_PAGE_SIZE(maximumSize);
      base = dvmAllocRegion(length, PROT_NONE, gDvm.zygote ? "dalvik-zygote" : "dalvik-heap");
      if (base == NULL) {
          return NULL;
      }
  
      /* Create an unlocked dlmalloc mspace to use as
       * a heap source.
       */
      msp = createMspace(base, kInitialMorecoreStart, startSize);
      if (msp == NULL) {
          goto fail;
      }
  
      gcHeap = (GcHeap *)calloc(1, sizeof(*gcHeap));
      if (gcHeap == NULL) {
          LOGE_HEAP("Can't allocate heap descriptor");
          goto fail;
      }
  
      hs = (HeapSource *)calloc(1, sizeof(*hs));
      if (hs == NULL) {
          LOGE_HEAP("Can't allocate heap source");
          free(gcHeap);
          goto fail;
      }
  
      hs->targetUtilization = gDvm.heapTargetUtilization * HEAP_UTILIZATION_MAX;
      hs->minFree = gDvm.heapMinFree;
      hs->maxFree = gDvm.heapMaxFree;
      hs->startSize = startSize;
      hs->maximumSize = maximumSize;
      hs->growthLimit = growthLimit;
      hs->idealSize = startSize;
      hs->softLimit = SIZE_MAX;    // no soft limit at first
      hs->numHeaps = 0;
      hs->sawZygote = gDvm.zygote;
      hs->nativeBytesAllocated = 0;
      hs->nativeFootprintGCWatermark = startSize;
      hs->nativeFootprintLimit = startSize * 2;
      hs->nativeNeedToRunFinalization = false;
      hs->hasGcThread = false;
      hs->heapBase = (char *)base;
      hs->heapLength = length;
  
      if (hs->maxFree > hs->maximumSize) {
        hs->maxFree = hs->maximumSize;
      }
      if (hs->minFree < CONCURRENT_START) {
        hs->minFree = CONCURRENT_START;
      } else if (hs->minFree > hs->maxFree) {
        hs->minFree = hs->maxFree;
      }
  
      if (!addInitialHeap(hs, msp, growthLimit)) {
          LOGE_HEAP("Can't add initial heap");
          goto fail;
      }
      if (!dvmHeapBitmapInit(&hs->liveBits, base, length, "dalvik-bitmap-1")) {
          LOGE_HEAP("Can't create liveBits");
          goto fail;
      }
      if (!dvmHeapBitmapInit(&hs->markBits, base, length, "dalvik-bitmap-2")) {
          LOGE_HEAP("Can't create markBits");
          dvmHeapBitmapDelete(&hs->liveBits);
          goto fail;
      }
      if (!allocMarkStack(&gcHeap->markContext.stack, hs->maximumSize)) {
          ALOGE("Can't create markStack");
          dvmHeapBitmapDelete(&hs->markBits);
          dvmHeapBitmapDelete(&hs->liveBits);
          goto fail;
      }
      gcHeap->markContext.bitmap = &hs->markBits;
      gcHeap->heapSource = hs;
  
      gHs = hs;
      return gcHeap;
  
  fail:
      munmap(base, length);
      return NULL;
  }
  
  bool dvmHeapSourceStartupAfterZygote()
  {
      return gDvm.concurrentMarkSweep ? gcDaemonStartup() : true;
  }
  
  /*
   * This is called while in zygote mode, right before we fork() for the
   * first time.  We create a heap for all future zygote process allocations,
   * in an attempt to avoid touching pages in the zygote heap.  (This would
   * probably be unnecessary if we had a compacting GC -- the source of our
   * troubles is small allocations filling in the gaps from larger ones.)
   */
  bool dvmHeapSourceStartupBeforeFork()
  {
      HeapSource *hs = gHs; // use a local to avoid the implicit "volatile"
  
      HS_BOILERPLATE();
  
      assert(gDvm.zygote);
  
      if (!gDvm.newZygoteHeapAllocated) {
         /* Ensure heaps are trimmed to minimize footprint pre-fork.
          */
          trimHeaps();
          /* Create a new heap for post-fork zygote allocations.  We only
           * try once, even if it fails.
           */
          ALOGV("Splitting out new zygote heap");
          gDvm.newZygoteHeapAllocated = true;
          return addNewHeap(hs);
      }
      return true;
  }
  
  void dvmHeapSourceThreadShutdown()
  {
      if (gDvm.gcHeap != NULL && gDvm.concurrentMarkSweep) {
          gcDaemonShutdown();
      }
  }
  
  /*
   * Tears down the entire GcHeap structure and all of the substructures
   * attached to it.  This call has the side effect of setting the given
   * gcHeap pointer and gHs to NULL.
   */
  void dvmHeapSourceShutdown(GcHeap **gcHeap)
  {
      assert(gcHeap != NULL);
      if (*gcHeap != NULL && (*gcHeap)->heapSource != NULL) {
          HeapSource *hs = (*gcHeap)->heapSource;
          dvmHeapBitmapDelete(&hs->liveBits);
          dvmHeapBitmapDelete(&hs->markBits);
          freeMarkStack(&(*gcHeap)->markContext.stack);
          munmap(hs->heapBase, hs->heapLength);
          free(hs);
          gHs = NULL;
          free(*gcHeap);
          *gcHeap = NULL;
      }
  }
  
  /*
   * Gets the begining of the allocation for the HeapSource.
   */
  void *dvmHeapSourceGetBase()
  {
      return gHs->heapBase;
  }
  
  /*
   * Returns a high water mark, between base and limit all objects must have been
   * allocated.
   */
  void *dvmHeapSourceGetLimit()
  {
      HeapSource *hs = gHs;
      void *max_brk = hs->heaps[0].brk;
  
  #ifndef NDEBUG
      for (size_t i = 1; i < hs->numHeaps; i++) {
          Heap *const heap = &hs->heaps[i];
          void *heap_brk = heap->brk;
          assert (max_brk > heap_brk);
      }
  #endif
      return max_brk;
  }
  
  /*
   * Returns the requested value. If the per-heap stats are requested, fill
   * them as well.
   *
   * Caller must hold the heap lock.
   */
  size_t dvmHeapSourceGetValue(HeapSourceValueSpec spec, size_t perHeapStats[],
                               size_t arrayLen)
  {
      HeapSource *hs = gHs;
      size_t value = 0;
      size_t total = 0;
  
      HS_BOILERPLATE();
  
      assert(arrayLen >= hs->numHeaps || perHeapStats == NULL);
      for (size_t i = 0; i < hs->numHeaps; i++) {
          Heap *const heap = &hs->heaps[i];
  
          switch (spec) {
          case HS_FOOTPRINT:
              value = heap->brk - heap->base;
              assert(value == mspace_footprint(heap->msp));
              break;
          case HS_ALLOWED_FOOTPRINT:
              value = mspace_footprint_limit(heap->msp);
              break;
          case HS_BYTES_ALLOCATED:
              value = heap->bytesAllocated;
              break;
          case HS_OBJECTS_ALLOCATED:
              value = heap->objectsAllocated;
              break;
          default:
              // quiet gcc
              break;
          }
          if (perHeapStats) {
              perHeapStats[i] = value;
          }
          total += value;
      }
      return total;
  }
  
  void dvmHeapSourceGetRegions(uintptr_t *base, uintptr_t *max, size_t numHeaps)
  {
      HeapSource *hs = gHs;
  
      HS_BOILERPLATE();
  
      assert(numHeaps <= hs->numHeaps);
      for (size_t i = 0; i < numHeaps; ++i) {
          base[i] = (uintptr_t)hs->heaps[i].base;
          max[i] = MIN((uintptr_t)hs->heaps[i].limit - 1, hs->markBits.max);
      }
  }
  
  /*
   * Get the bitmap representing all live objects.
   */
  HeapBitmap *dvmHeapSourceGetLiveBits()
  {
      HS_BOILERPLATE();
  
      return &gHs->liveBits;
  }
  
  /*
   * Get the bitmap representing all marked objects.
   */
  HeapBitmap *dvmHeapSourceGetMarkBits()
  {
      HS_BOILERPLATE();
  
      return &gHs->markBits;
  }
  
  void dvmHeapSourceSwapBitmaps()
  {
      HeapBitmap tmp = gHs->liveBits;
      gHs->liveBits = gHs->markBits;
      gHs->markBits = tmp;
  }
  
  void dvmHeapSourceZeroMarkBitmap()
  {
      HS_BOILERPLATE();
  
      dvmHeapBitmapZero(&gHs->markBits);
  }
  
  void dvmMarkImmuneObjects(const char *immuneLimit)
  {
      /*
       * Copy the contents of the live bit vector for immune object
       * range into the mark bit vector.
       */
      /* The only values generated by dvmHeapSourceGetImmuneLimit() */
      assert(immuneLimit == gHs->heaps[0].base ||
             immuneLimit == NULL);
      assert(gHs->liveBits.base == gHs->markBits.base);
      assert(gHs->liveBits.bitsLen == gHs->markBits.bitsLen);
      /* heap[0] is never immune */
      assert(gHs->heaps[0].base >= immuneLimit);
      assert(gHs->heaps[0].limit > immuneLimit);
  
      for (size_t i = 1; i < gHs->numHeaps; ++i) {
          if (gHs->heaps[i].base < immuneLimit) {
              assert(gHs->heaps[i].limit <= immuneLimit);
              /* Compute the number of words to copy in the bitmap. */
              size_t index = HB_OFFSET_TO_INDEX(
                  (uintptr_t)gHs->heaps[i].base - gHs->liveBits.base);
              /* Compute the starting offset in the live and mark bits. */
              char *src = (char *)(gHs->liveBits.bits + index);
              char *dst = (char *)(gHs->markBits.bits + index);
              /* Compute the number of bytes of the live bitmap to copy. */
              size_t length = HB_OFFSET_TO_BYTE_INDEX(
                  gHs->heaps[i].limit - gHs->heaps[i].base);
              /* Do the copy. */
              memcpy(dst, src, length);
              /* Make sure max points to the address of the highest set bit. */
              if (gHs->markBits.max < (uintptr_t)gHs->heaps[i].limit) {
                  gHs->markBits.max = (uintptr_t)gHs->heaps[i].limit;
              }
          }
      }
  }
  
  /*
   * Allocates <n> bytes of zeroed data.
   */
  void* dvmHeapSourceAlloc(size_t n)
  {
      HS_BOILERPLATE();
  
      HeapSource *hs = gHs;
      Heap* heap = hs2heap(hs);
      if (heap->bytesAllocated + n > hs->softLimit) {
          /*
           * This allocation would push us over the soft limit; act as
           * if the heap is full.
           */
          LOGV_HEAP("softLimit of %zd.%03zdMB hit for %zd-byte allocation",
                    FRACTIONAL_MB(hs->softLimit), n);
          return NULL;
      }
      void* ptr;
      if (gDvm.lowMemoryMode) {
          /* This is only necessary because mspace_calloc always memsets the
           * allocated memory to 0. This is bad for memory usage since it leads
           * to dirty zero pages. If low memory mode is enabled, we use
           * mspace_malloc which doesn't memset the allocated memory and madvise
           * the page aligned region back to the kernel.
           */
          ptr = mspace_malloc(heap->msp, n);
          if (ptr == NULL) {
              return NULL;
          }
          uintptr_t zero_begin = (uintptr_t)ptr;
          uintptr_t zero_end = (uintptr_t)ptr + n;
          /* Calculate the page aligned region.
           */
          uintptr_t begin = ALIGN_UP_TO_PAGE_SIZE(zero_begin);
          uintptr_t end = zero_end & ~(uintptr_t)(SYSTEM_PAGE_SIZE - 1);
          /* If our allocation spans more than one page, we attempt to madvise.
           */
          if (begin < end) {
              /* madvise the page aligned region to kernel.
               */
              madvise((void*)begin, end - begin, MADV_DONTNEED);
              /* Zero the region after the page aligned region.
               */
              memset((void*)end, 0, zero_end - end);
              /* Zero out the region before the page aligned region.
               */
              zero_end = begin;
          }
          memset((void*)zero_begin, 0, zero_end - zero_begin);
      } else {
          ptr = mspace_calloc(heap->msp, 1, n);
          if (ptr == NULL) {
              return NULL;
          }
      }
  
      countAllocation(heap, ptr);
      /*
       * Check to see if a concurrent GC should be initiated.
       */
      if (gDvm.gcHeap->gcRunning || !hs->hasGcThread) {
          /*
           * The garbage collector thread is already running or has yet
           * to be started.  Do nothing.
           */
          return ptr;
      }
      if (heap->bytesAllocated > heap->concurrentStartBytes) {
          /*
           * We have exceeded the allocation threshold.  Wake up the
           * garbage collector.
           */
          dvmSignalCond(&gHs->gcThreadCond);
      }
      return ptr;
  }
  
  /* Remove any hard limits, try to allocate, and shrink back down.
   * Last resort when trying to allocate an object.
   */
  static void* heapAllocAndGrow(HeapSource *hs, Heap *heap, size_t n)
  {
      /* Grow as much as possible, but don't let the real footprint
       * go over the absolute max.
       */
      size_t max = heap->maximumSize;
  
      mspace_set_footprint_limit(heap->msp, max);
      void* ptr = dvmHeapSourceAlloc(n);
  
      /* Shrink back down as small as possible.  Our caller may
       * readjust max_allowed to a more appropriate value.
       */
      mspace_set_footprint_limit(heap->msp,
                                 mspace_footprint(heap->msp));
      return ptr;
  }
  
  /*
   * Allocates <n> bytes of zeroed data, growing as much as possible
   * if necessary.
   */
  void* dvmHeapSourceAllocAndGrow(size_t n)
  {
      HS_BOILERPLATE();
  
      HeapSource *hs = gHs;
      Heap* heap = hs2heap(hs);
      void* ptr = dvmHeapSourceAlloc(n);
      if (ptr != NULL) {
          return ptr;
      }
  
      size_t oldIdealSize = hs->idealSize;
      if (isSoftLimited(hs)) {
          /* We're soft-limited.  Try removing the soft limit to
           * see if we can allocate without actually growing.
           */
          hs->softLimit = SIZE_MAX;
          ptr = dvmHeapSourceAlloc(n);
          if (ptr != NULL) {
              /* Removing the soft limit worked;  fix things up to
               * reflect the new effective ideal size.
               */
              snapIdealFootprint();
              return ptr;
          }
          // softLimit intentionally left at SIZE_MAX.
      }
  
      /* We're not soft-limited.  Grow the heap to satisfy the request.
       * If this call fails, no footprints will have changed.
       */
      ptr = heapAllocAndGrow(hs, heap, n);
      if (ptr != NULL) {
          /* The allocation succeeded.  Fix up the ideal size to
           * reflect any footprint modifications that had to happen.
           */
          snapIdealFootprint();
      } else {
          /* We just couldn't do it.  Restore the original ideal size,
           * fixing up softLimit if necessary.
           */
          setIdealFootprint(oldIdealSize);
      }
      return ptr;
  }
  
  /*
   * Frees the first numPtrs objects in the ptrs list and returns the
   * amount of reclaimed storage. The list must contain addresses all in
   * the same mspace, and must be in increasing order. This implies that
   * there are no duplicates, and no entries are NULL.
   */
  size_t dvmHeapSourceFreeList(size_t numPtrs, void **ptrs)
  {
      HS_BOILERPLATE();
  
      if (numPtrs == 0) {
          return 0;
      }
  
      assert(ptrs != NULL);
      assert(*ptrs != NULL);
      Heap* heap = ptr2heap(gHs, *ptrs);
      size_t numBytes = 0;
      if (heap != NULL) {
          mspace msp = heap->msp;
          // Calling mspace_free on shared heaps disrupts sharing too
          // much. For heap[0] -- the 'active heap' -- we call
          // mspace_free, but on the other heaps we only do some
          // accounting.
          if (heap == gHs->heaps) {
              // Count freed objects.
              for (size_t i = 0; i < numPtrs; i++) {
                  assert(ptrs[i] != NULL);
                  assert(ptr2heap(gHs, ptrs[i]) == heap);
                  countFree(heap, ptrs[i], &numBytes);
              }
              // Bulk free ptrs.
              mspace_bulk_free(msp, ptrs, numPtrs);
          } else {
              // This is not an 'active heap'. Only do the accounting.
              for (size_t i = 0; i < numPtrs; i++) {
                  assert(ptrs[i] != NULL);
                  assert(ptr2heap(gHs, ptrs[i]) == heap);
                  countFree(heap, ptrs[i], &numBytes);
              }
          }
      }
      return numBytes;
  }
  
  /*
   * Returns true iff <ptr> is in the heap source.
   */
  bool dvmHeapSourceContainsAddress(const void *ptr)
  {
      HS_BOILERPLATE();
  
      return (dvmHeapSourceGetBase() <= ptr) && (ptr <= dvmHeapSourceGetLimit());
  }
  
  /*
   * Returns true iff <ptr> was allocated from the heap source.
   */
  bool dvmHeapSourceContains(const void *ptr)
  {
      HS_BOILERPLATE();
  
      if (dvmHeapSourceContainsAddress(ptr)) {
          return dvmHeapBitmapIsObjectBitSet(&gHs->liveBits, ptr) != 0;
      }
      return false;
  }
  
  bool dvmIsZygoteObject(const Object* obj)
  {
      HeapSource *hs = gHs;
  
      HS_BOILERPLATE();
  
      if (dvmHeapSourceContains(obj) && hs->sawZygote) {
          Heap *heap = ptr2heap(hs, obj);
          if (heap != NULL) {
              /* If the object is not in the active heap, we assume that
               * it was allocated as part of zygote.
               */
              return heap != hs->heaps;
          }
      }
      /* The pointer is outside of any known heap, or we are not
       * running in zygote mode.
       */
      return false;
  }
  
  /*
   * Returns the number of usable bytes in an allocated chunk; the size
   * may be larger than the size passed to dvmHeapSourceAlloc().
   */
  size_t dvmHeapSourceChunkSize(const void *ptr)
  {
      HS_BOILERPLATE();
  
      Heap* heap = ptr2heap(gHs, ptr);
      if (heap != NULL) {
          return mspace_usable_size(ptr);
      }
      return 0;
  }
  
  /*
   * Returns the number of bytes that the heap source has allocated
   * from the system using sbrk/mmap, etc.
   *
   * Caller must hold the heap lock.
   */
  size_t dvmHeapSourceFootprint()
  {
      HS_BOILERPLATE();
  
  //TODO: include size of bitmaps?
      return oldHeapOverhead(gHs, true);
  }
  
  static size_t getMaximumSize(const HeapSource *hs)
  {
      return hs->growthLimit;
  }
  
  /*
   * Returns the current maximum size of the heap source respecting any
   * growth limits.
   */
  size_t dvmHeapSourceGetMaximumSize()
  {
      HS_BOILERPLATE();
      return getMaximumSize(gHs);
  }
  
  /*
   * Removes any growth limits.  Allows the user to allocate up to the
   * maximum heap size.
   */
  void dvmClearGrowthLimit()
  {
      HS_BOILERPLATE();
      dvmLockHeap();
      dvmWaitForConcurrentGcToComplete();
      gDvm.gcHeap->cardTableLength = gDvm.gcHeap->cardTableMaxLength;
      gHs->growthLimit = gHs->maximumSize;
      size_t overhead = oldHeapOverhead(gHs, false);
      gHs->heaps[0].maximumSize = gHs->maximumSize - overhead;
      gHs->heaps[0].limit = gHs->heaps[0].base + gHs->heaps[0].maximumSize;
      dvmUnlockHeap();
  }
  
  /*
   * Return the real bytes used by old heaps plus the soft usage of the
   * current heap.  When a soft limit is in effect, this is effectively
   * what it's compared against (though, in practice, it only looks at
   * the current heap).
   */
  static size_t getSoftFootprint(bool includeActive)
  {
      HS_BOILERPLATE();
  
      HeapSource *hs = gHs;
      size_t ret = oldHeapOverhead(hs, false);
      if (includeActive) {
          ret += hs->heaps[0].bytesAllocated;
      }
  
      return ret;
  }
  
  /*
   * Gets the maximum number of bytes that the heap source is allowed
   * to allocate from the system.
   */
  size_t dvmHeapSourceGetIdealFootprint()
  {
      HeapSource *hs = gHs;
  
      HS_BOILERPLATE();
  
      return hs->idealSize;
  }
  
  /*
   * Sets the soft limit, handling any necessary changes to the allowed
   * footprint of the active heap.
   */
  static void setSoftLimit(HeapSource *hs, size_t softLimit)
  {
      /* Compare against the actual footprint, rather than the
       * max_allowed, because the heap may not have grown all the
       * way to the allowed size yet.
       */
      mspace msp = hs->heaps[0].msp;
      size_t currentHeapSize = mspace_footprint(msp);
      if (softLimit < currentHeapSize) {
          /* Don't let the heap grow any more, and impose a soft limit.
           */
          mspace_set_footprint_limit(msp, currentHeapSize);
          hs->softLimit = softLimit;
      } else {
          /* Let the heap grow to the requested max, and remove any
           * soft limit, if set.
           */
          mspace_set_footprint_limit(msp, softLimit);
          hs->softLimit = SIZE_MAX;
      }
  }
  
  /*
   * Sets the maximum number of bytes that the heap source is allowed
   * to allocate from the system.  Clamps to the appropriate maximum
   * value.
   */
  static void setIdealFootprint(size_t max)
  {
      HS_BOILERPLATE();
  
      HeapSource *hs = gHs;
      size_t maximumSize = getMaximumSize(hs);
      if (max > maximumSize) {
          LOGI_HEAP("Clamp target GC heap from %zd.%03zdMB to %u.%03uMB",
                  FRACTIONAL_MB(max),
                  FRACTIONAL_MB(maximumSize));
          max = maximumSize;
      }
  
      /* Convert max into a size that applies to the active heap.
       * Old heaps will count against the ideal size.
       */
      size_t overhead = getSoftFootprint(false);
      size_t activeMax;
      if (overhead < max) {
          activeMax = max - overhead;
      } else {
          activeMax = 0;
      }
  
      setSoftLimit(hs, activeMax);
      hs->idealSize = max;
  }
  
  /*
   * Make the ideal footprint equal to the current footprint.
   */
  static void snapIdealFootprint()
  {
      HS_BOILERPLATE();
  
      setIdealFootprint(getSoftFootprint(true));
  }
  
  /*
   * Gets the current ideal heap utilization, represented as a number
   * between zero and one.
   */
  float dvmGetTargetHeapUtilization()
  {
      HeapSource *hs = gHs;
  
      HS_BOILERPLATE();
  
      return (float)hs->targetUtilization / (float)HEAP_UTILIZATION_MAX;
  }
  
  /*
   * Sets the new ideal heap utilization, represented as a number
   * between zero and one.
   */
  void dvmSetTargetHeapUtilization(float newTarget)
  {
      HeapSource *hs = gHs;
  
      HS_BOILERPLATE();
  
      /* Clamp it to a reasonable range.
       */
      // TODO: This may need some tuning.
      if (newTarget < 0.2) {
          newTarget = 0.2;
      } else if (newTarget > 0.8) {
          newTarget = 0.8;
      }
  
      hs->targetUtilization =
              (size_t)(newTarget * (float)HEAP_UTILIZATION_MAX);
      ALOGV("Set heap target utilization to %zd/%d (%f)",
              hs->targetUtilization, HEAP_UTILIZATION_MAX, newTarget);
  }
  
  /*
   * Given the size of a live set, returns the ideal heap size given
   * the current target utilization and MIN/MAX values.
   */
  static size_t getUtilizationTarget(const HeapSource* hs, size_t liveSize)
  {
      /* Use the current target utilization ratio to determine the
       * ideal heap size based on the size of the live set.
       */
      size_t targetSize = (liveSize / hs->targetUtilization) * HEAP_UTILIZATION_MAX;
  
      /* Cap the amount of free space, though, so we don't end up
       * with, e.g., 8MB of free space when the live set size hits 8MB.
       */
      if (targetSize > liveSize + hs->maxFree) {
          targetSize = liveSize + hs->maxFree;
      } else if (targetSize < liveSize + hs->minFree) {
          targetSize = liveSize + hs->minFree;
      }
      return targetSize;
  }
  
  /*
   * Given the current contents of the active heap, increase the allowed
   * heap footprint to match the target utilization ratio.  This
   * should only be called immediately after a full mark/sweep.
   */
  void dvmHeapSourceGrowForUtilization()
  {
      HS_BOILERPLATE();
  
      HeapSource *hs = gHs;
      Heap* heap = hs2heap(hs);
  
      /* Use the current target utilization ratio to determine the
       * ideal heap size based on the size of the live set.
       * Note that only the active heap plays any part in this.
       *
       * Avoid letting the old heaps influence the target free size,
       * because they may be full of objects that aren't actually
       * in the working set.  Just look at the allocated size of
       * the current heap.
       */
      size_t currentHeapUsed = heap->bytesAllocated;
      size_t targetHeapSize = getUtilizationTarget(hs, currentHeapUsed);
  
      /* The ideal size includes the old heaps; add overhead so that
       * it can be immediately subtracted again in setIdealFootprint().
       * If the target heap size would exceed the max, setIdealFootprint()
       * will clamp it to a legal value.
       */
      size_t overhead = getSoftFootprint(false);
      setIdealFootprint(targetHeapSize + overhead);
  
      size_t freeBytes = getAllocLimit(hs);
      if (freeBytes < CONCURRENT_MIN_FREE) {
          /* Not enough free memory to allow a concurrent GC. */
          heap->concurrentStartBytes = SIZE_MAX;
      } else {
          heap->concurrentStartBytes = freeBytes - CONCURRENT_START;
      }
  
      /* Mark that we need to run finalizers and update the native watermarks
       * next time we attempt to register a native allocation.
       */
      gHs->nativeNeedToRunFinalization = true;
  }
  
  /*
   * Return free pages to the system.
   * TODO: move this somewhere else, especially the native heap part.
   */
  static void releasePagesInRange(void* start, void* end, size_t used_bytes,
                                  void* releasedBytes)
  {
      if (used_bytes == 0) {
          /*
           * We have a range of memory we can try to madvise()
           * back. Linux requires that the madvise() start address is
           * page-aligned.  We also align the end address.
           */
          start = (void *)ALIGN_UP_TO_PAGE_SIZE(start);
          end = (void *)((size_t)end & ~(SYSTEM_PAGE_SIZE - 1));
          if (end > start) {
              size_t length = (char *)end - (char *)start;
              madvise(start, length, MADV_DONTNEED);
              *(size_t *)releasedBytes += length;
          }
      }
  }
  
  /*
   * Return unused memory to the system if possible.
   */
  static void trimHeaps()
  {
      HS_BOILERPLATE();
  
      HeapSource *hs = gHs;
      size_t heapBytes = 0;
      for (size_t i = 0; i < hs->numHeaps; i++) {
          Heap *heap = &hs->heaps[i];
  
          /* Return the wilderness chunk to the system. */
          mspace_trim(heap->msp, 0);
  
          /* Return any whole free pages to the system. */
          mspace_inspect_all(heap->msp, releasePagesInRange, &heapBytes);
      }
  
      /* Same for the native heap. */
      dlmalloc_trim(0);
      size_t nativeBytes = 0;
      dlmalloc_inspect_all(releasePagesInRange, &nativeBytes);
  
      LOGD_HEAP("madvised %zd (GC) + %zd (native) = %zd total bytes",
              heapBytes, nativeBytes, heapBytes + nativeBytes);
  }
  
  /*
   * Walks over the heap source and passes every allocated and
   * free chunk to the callback.
   */
  void dvmHeapSourceWalk(void(*callback)(void* start, void* end,
                                         size_t used_bytes, void* arg),
                         void *arg)
  {
      HS_BOILERPLATE();
  
      /* Walk the heaps from oldest to newest.
       */
  //TODO: do this in address order
      HeapSource *hs = gHs;
      for (size_t i = hs->numHeaps; i > 0; --i) {
          mspace_inspect_all(hs->heaps[i-1].msp, callback, arg);
          callback(NULL, NULL, 0, arg);  // Indicate end of a heap.
      }
  }
  
  /*
   * Gets the number of heaps available in the heap source.
   *
   * Caller must hold the heap lock, because gHs caches a field
   * in gDvm.gcHeap.
   */
  size_t dvmHeapSourceGetNumHeaps()
  {
      HS_BOILERPLATE();
  
      return gHs->numHeaps;
  }
  
  void *dvmHeapSourceGetImmuneLimit(bool isPartial)
  {
      if (isPartial) {
          return hs2heap(gHs)->base;
      } else {
          return NULL;
      }
  }
  
  static void dvmHeapSourceUpdateMaxNativeFootprint()
  {
      /* Use the current target utilization ratio to determine the new native GC
       * watermarks.
       */
      size_t nativeSize = gHs->nativeBytesAllocated;
      size_t targetSize =
          (nativeSize / gHs->targetUtilization) * HEAP_UTILIZATION_MAX;
  
      if (targetSize > nativeSize + gHs->maxFree) {
          targetSize = nativeSize + gHs->maxFree;
      } else if (targetSize < nativeSize + gHs->minFree) {
          targetSize = nativeSize + gHs->minFree;
      }
      gHs->nativeFootprintGCWatermark = targetSize;
      gHs->nativeFootprintLimit = 2 * targetSize - nativeSize;
  }
  
  void dvmHeapSourceRegisterNativeAllocation(int bytes)
  {
      /* If we have just done a GC, ensure that the finalizers are done and update
       * the native watermarks.
       */
      if (gHs->nativeNeedToRunFinalization) {
          dvmRunFinalization();
          dvmHeapSourceUpdateMaxNativeFootprint();
          gHs->nativeNeedToRunFinalization = false;
      }
  
      android_atomic_add(bytes, &gHs->nativeBytesAllocated);
  
      if ((size_t)gHs->nativeBytesAllocated > gHs->nativeFootprintGCWatermark) {
          /* The second watermark is higher than the gc watermark. If you hit
           * this it means you are allocating native objects faster than the GC
           * can keep up with. If this occurs, we do a GC for alloc.
           */
          if ((size_t)gHs->nativeBytesAllocated > gHs->nativeFootprintLimit) {
              Thread* self = dvmThreadSelf();
              dvmRunFinalization();
              if (dvmCheckException(self)) {
                  return;
              }
              dvmLockHeap();
              bool waited = dvmWaitForConcurrentGcToComplete();
              dvmUnlockHeap();
              if (waited) {
                  // Just finished a GC, attempt to run finalizers.
                  dvmRunFinalization();
                  if (dvmCheckException(self)) {
                      return;
                  }
              }
  
              // If we still are over the watermark, attempt a GC for alloc and run finalizers.
              if ((size_t)gHs->nativeBytesAllocated > gHs->nativeFootprintLimit) {
                  dvmLockHeap();
                  dvmWaitForConcurrentGcToComplete();
                  dvmCollectGarbageInternal(GC_FOR_MALLOC);
                  dvmUnlockHeap();
                  dvmRunFinalization();
                  gHs->nativeNeedToRunFinalization = false;
                  if (dvmCheckException(self)) {
                      return;
                  }
              }
              /* We have just run finalizers, update the native watermark since
               * it is very likely that finalizers released native managed
               * allocations.
               */
              dvmHeapSourceUpdateMaxNativeFootprint();
          } else {
              dvmSignalCond(&gHs->gcThreadCond);
          }
      }
  }
  
  /*
   * Called from VMRuntime.registerNativeFree.
   */
  void dvmHeapSourceRegisterNativeFree(int bytes)
  {
      int expected_size, new_size;
      do {
          expected_size = gHs->nativeBytesAllocated;
          new_size = expected_size - bytes;
          if (new_size < 0) {
              break;
          }
      } while (android_atomic_cas(expected_size, new_size,
                                  &gHs->nativeBytesAllocated));
  }
  