text: /*
   * Copyright (C) 2010 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 <sys/mman.h>  /* for PROT_* */
  
  #include "Dalvik.h"
  #include "alloc/HeapBitmap.h"
  #include "alloc/HeapBitmapInlines.h"
  #include "alloc/HeapSource.h"
  #include "alloc/Visit.h"
  
  /*
   * Maintain a card table from the the write barrier. All writes of
   * non-NULL values to heap addresses should go through an entry in
   * WriteBarrier, and from there to here.
   *
   * The heap is divided into "cards" of GC_CARD_SIZE bytes, as
   * determined by GC_CARD_SHIFT. The card table contains one byte of
   * data per card, to be used by the GC. The value of the byte will be
   * one of GC_CARD_CLEAN or GC_CARD_DIRTY.
   *
   * After any store of a non-NULL object pointer into a heap object,
   * code is obliged to mark the card dirty. The setters in
   * ObjectInlines.h [such as dvmSetFieldObject] do this for you. The
   * JIT and fast interpreters also contain code to mark cards as dirty.
   *
   * The card table's base [the "biased card table"] gets set to a
   * rather strange value.  In order to keep the JIT from having to
   * fabricate or load GC_DIRTY_CARD to store into the card table,
   * biased base is within the mmap allocation at a point where it's low
   * byte is equal to GC_DIRTY_CARD. See dvmCardTableStartup for details.
   */
  
  /*
   * Initializes the card table; must be called before any other
   * dvmCardTable*() functions.
   */
  bool dvmCardTableStartup(size_t heapMaximumSize, size_t growthLimit)
  {
      size_t length;
      void *allocBase;
      u1 *biasedBase;
      GcHeap *gcHeap = gDvm.gcHeap;
      int offset;
      void *heapBase = dvmHeapSourceGetBase();
      assert(gcHeap != NULL);
      assert(heapBase != NULL);
      /* All zeros is the correct initial value; all clean. */
      assert(GC_CARD_CLEAN == 0);
  
      /* Set up the card table */
      length = heapMaximumSize / GC_CARD_SIZE;
      /* Allocate an extra 256 bytes to allow fixed low-byte of base */
      allocBase = dvmAllocRegion(length + 0x100, PROT_READ | PROT_WRITE,
                              "dalvik-card-table");
      if (allocBase == NULL) {
          return false;
      }
      gcHeap->cardTableBase = (u1*)allocBase;
      gcHeap->cardTableLength = growthLimit / GC_CARD_SIZE;
      gcHeap->cardTableMaxLength = length;
      biasedBase = (u1 *)((uintptr_t)allocBase -
                         ((uintptr_t)heapBase >> GC_CARD_SHIFT));
      offset = GC_CARD_DIRTY - ((uintptr_t)biasedBase & 0xff);
      gcHeap->cardTableOffset = offset + (offset < 0 ? 0x100 : 0);
      biasedBase += gcHeap->cardTableOffset;
      assert(((uintptr_t)biasedBase & 0xff) == GC_CARD_DIRTY);
      gDvm.biasedCardTableBase = biasedBase;
  
      return true;
  }
  
  /*
   * Tears down the entire CardTable.
   */
  void dvmCardTableShutdown()
  {
      gDvm.biasedCardTableBase = NULL;
      munmap(gDvm.gcHeap->cardTableBase, gDvm.gcHeap->cardTableLength);
  }
  
  void dvmClearCardTable()
  {
      /*
       * The goal is to zero out some mmap-allocated pages.  We can accomplish
       * this with memset() or madvise(MADV_DONTNEED).  The latter has some
       * useful properties, notably that the pages are returned to the system,
       * so cards for parts of the heap we haven't expanded into won't be
       * allocated physical pages.  On the other hand, if we un-map the card
       * area, we'll have to fault it back in as we resume dirtying objects,
       * which reduces performance.
       *
       * We don't cause any correctness issues by failing to clear cards; we
       * just take a performance hit during the second pause of the concurrent
       * collection.  The "advisory" nature of madvise() isn't a big problem.
       *
       * What we really want to do is:
       * (1) zero out all cards that were touched
       * (2) use madvise() to release any pages that won't be used in the near
       *     future
       *
       * For #1, we don't really know which cards were touched, but we can
       * approximate it with the "live bits max" value, which tells us the
       * highest start address at which an object was allocated.  This may
       * leave vestigial nonzero entries at the end if temporary objects are
       * created during a concurrent GC, but that should be harmless.  (We
       * can round up to the end of the card table page to reduce this.)
       *
       * For #2, we don't know which pages will be used in the future.  Some
       * simple experiments suggested that a "typical" app will touch about
       * 60KB of pages while initializing, but drops down to 20-24KB while
       * idle.  We can save a few hundred KB system-wide with aggressive
       * use of madvise().  The cost of mapping those pages back in is paid
       * outside of the GC pause, which reduces the impact.  (We might be
       * able to get the benefits by only doing this occasionally, e.g. if
       * the heap shrinks a lot or we somehow notice that we've been idle.)
       *
       * Note that cardTableLength is initially set to the growth limit, and
       * on request will be expanded to the heap maximum.
       */
      assert(gDvm.gcHeap->cardTableBase != NULL);
  
      if (gDvm.lowMemoryMode) {
        // zero out cards with madvise(), discarding all pages in the card table
        madvise(gDvm.gcHeap->cardTableBase, gDvm.gcHeap->cardTableLength, MADV_DONTNEED);
      } else {
        // zero out cards with memset(), using liveBits as an estimate
        const HeapBitmap* liveBits = dvmHeapSourceGetLiveBits();
        size_t maxLiveCard = (liveBits->max - liveBits->base) / GC_CARD_SIZE;
        maxLiveCard = ALIGN_UP_TO_PAGE_SIZE(maxLiveCard);
        if (maxLiveCard > gDvm.gcHeap->cardTableLength) {
            maxLiveCard = gDvm.gcHeap->cardTableLength;
        }
  
        memset(gDvm.gcHeap->cardTableBase, GC_CARD_CLEAN, maxLiveCard);
      }
  }
  
  /*
   * Returns true iff the address is within the bounds of the card table.
   */
  bool dvmIsValidCard(const u1 *cardAddr)
  {
      GcHeap *h = gDvm.gcHeap;
      u1* begin = h->cardTableBase + h->cardTableOffset;
      u1* end = &begin[h->cardTableLength];
      return cardAddr >= begin && cardAddr < end;
  }
  
  /*
   * Returns the address of the relevant byte in the card table, given
   * an address on the heap.
   */
  u1 *dvmCardFromAddr(const void *addr)
  {
      u1 *biasedBase = gDvm.biasedCardTableBase;
      u1 *cardAddr = biasedBase + ((uintptr_t)addr >> GC_CARD_SHIFT);
      assert(dvmIsValidCard(cardAddr));
      return cardAddr;
  }
  
  /*
   * Returns the first address in the heap which maps to this card.
   */
  void *dvmAddrFromCard(const u1 *cardAddr)
  {
      assert(dvmIsValidCard(cardAddr));
      uintptr_t offset = cardAddr - gDvm.biasedCardTableBase;
      return (void *)(offset << GC_CARD_SHIFT);
  }
  
  /*
   * Dirties the card for the given address.
   */
  void dvmMarkCard(const void *addr)
  {
      u1 *cardAddr = dvmCardFromAddr(addr);
      *cardAddr = GC_CARD_DIRTY;
  }
  
  /*
   * Returns true if the object is on a dirty card.
   */
  static bool isObjectDirty(const Object *obj)
  {
      assert(obj != NULL);
      assert(dvmIsValidObject(obj));
      u1 *card = dvmCardFromAddr(obj);
      return *card == GC_CARD_DIRTY;
  }
  
  /*
   * Context structure for verifying the card table.
   */
  struct WhiteReferenceCounter {
      HeapBitmap *markBits;
      size_t whiteRefs;
  };
  
  /*
   * Visitor that counts white referents.
   */
  static void countWhiteReferenceVisitor(void *addr, void *arg)
  {
      WhiteReferenceCounter *ctx;
      Object *obj;
  
      assert(addr != NULL);
      assert(arg != NULL);
      obj = *(Object **)addr;
      if (obj == NULL) {
          return;
      }
      assert(dvmIsValidObject(obj));
      ctx = (WhiteReferenceCounter *)arg;
      if (dvmHeapBitmapIsObjectBitSet(ctx->markBits, obj)) {
          return;
      }
      ctx->whiteRefs += 1;
  }
  
  /*
   * Visitor that logs white references.
   */
  static void dumpWhiteReferenceVisitor(void *addr, void *arg)
  {
      WhiteReferenceCounter *ctx;
      Object *obj;
  
      assert(addr != NULL);
      assert(arg != NULL);
      obj = *(Object **)addr;
      if (obj == NULL) {
          return;
      }
      assert(dvmIsValidObject(obj));
      ctx = (WhiteReferenceCounter*)arg;
      if (dvmHeapBitmapIsObjectBitSet(ctx->markBits, obj)) {
          return;
      }
      ALOGE("object %p is white", obj);
  }
  
  /*
   * Visitor that signals the caller when a matching reference is found.
   */
  static void dumpReferencesVisitor(void *pObj, void *arg)
  {
      Object *obj = *(Object **)pObj;
      Object *lookingFor = *(Object **)arg;
      if (lookingFor != NULL && lookingFor == obj) {
          *(Object **)arg = NULL;
      }
  }
  
  static void dumpReferencesCallback(Object *obj, void *arg)
  {
      if (obj == (Object *)arg) {
          return;
      }
      dvmVisitObject(dumpReferencesVisitor, obj, &arg);
      if (arg == NULL) {
          ALOGD("Found %p in the heap @ %p", arg, obj);
          dvmDumpObject(obj);
      }
  }
  
  /*
   * Root visitor that looks for matching references.
   */
  static void dumpReferencesRootVisitor(void *ptr, u4 threadId,
                                        RootType type, void *arg)
  {
      Object *obj = *(Object **)ptr;
      Object *lookingFor = *(Object **)arg;
      if (obj == lookingFor) {
          ALOGD("Found %p in a root @ %p", arg, ptr);
      }
  }
  
  /*
   * Invokes visitors to search for references to an object.
   */
  static void dumpReferences(const Object *obj)
  {
      HeapBitmap *bitmap = dvmHeapSourceGetLiveBits();
      void *arg = (void *)obj;
      dvmVisitRoots(dumpReferencesRootVisitor, arg);
      dvmHeapBitmapWalk(bitmap, dumpReferencesCallback, arg);
  }
  
  /*
   * Returns true if the given object is a reference object and the
   * just the referent is unmarked.
   */
  static bool isReferentUnmarked(const Object *obj,
                                 const WhiteReferenceCounter* ctx)
  {
      assert(obj != NULL);
      assert(obj->clazz != NULL);
      assert(ctx != NULL);
      if (ctx->whiteRefs != 1) {
          return false;
      } else if (IS_CLASS_FLAG_SET(obj->clazz, CLASS_ISREFERENCE)) {
          size_t offset = gDvm.offJavaLangRefReference_referent;
          const Object *referent = dvmGetFieldObject(obj, offset);
          return !dvmHeapBitmapIsObjectBitSet(ctx->markBits, referent);
      } else {
          return false;
      }
  }
  
  /*
   * Returns true if the given object is a string and has been interned
   * by the user.
   */
  static bool isWeakInternedString(const Object *obj)
  {
      assert(obj != NULL);
      if (obj->clazz == gDvm.classJavaLangString) {
          return dvmIsWeakInternedString((StringObject *)obj);
      } else {
          return false;
      }
  }
  
  /*
   * Returns true if the given object has been pushed on the mark stack
   * by root marking.
   */
  static bool isPushedOnMarkStack(const Object *obj)
  {
      GcMarkStack *stack = &gDvm.gcHeap->markContext.stack;
      for (const Object **ptr = stack->base; ptr < stack->top; ++ptr) {
          if (*ptr == obj) {
              return true;
          }
      }
      return false;
  }
  
  /*
   * Callback applied to marked objects.  If the object is gray and on
   * an unmarked card an error is logged and the VM is aborted.  Card
   * table verification occurs between root marking and weak reference
   * processing.  We treat objects marked from the roots and weak
   * references specially as it is permissible for these objects to be
   * gray and on an unmarked card.
   */
  static void verifyCardTableCallback(Object *obj, void *arg)
  {
      WhiteReferenceCounter ctx = { (HeapBitmap *)arg, 0 };
  
      dvmVisitObject(countWhiteReferenceVisitor, obj, &ctx);
      if (ctx.whiteRefs == 0) {
          return;
      } else if (isObjectDirty(obj)) {
          return;
      } else if (isReferentUnmarked(obj, &ctx)) {
          return;
      } else if (isWeakInternedString(obj)) {
          return;
      } else if (isPushedOnMarkStack(obj)) {
          return;
      } else {
          ALOGE("Verify failed, object %p is gray and on an unmarked card", obj);
          dvmDumpObject(obj);
          dvmVisitObject(dumpWhiteReferenceVisitor, obj, &ctx);
          dumpReferences(obj);
          dvmAbort();
      }
  }
  
  /*
   * Verifies that gray objects are on a dirty card.
   */
  void dvmVerifyCardTable()
  {
      HeapBitmap *markBits = gDvm.gcHeap->markContext.bitmap;
      dvmHeapBitmapWalk(markBits, verifyCardTableCallback, markBits);
  }
  