Home | History | Annotate | Download | only in alloc
      1 /*
      2  * Copyright (C) 2010 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 <sys/mman.h>  /* for PROT_* */
     18 
     19 #include "Dalvik.h"
     20 #include "alloc/HeapBitmap.h"
     21 #include "alloc/HeapBitmapInlines.h"
     22 #include "alloc/HeapSource.h"
     23 #include "alloc/Visit.h"
     24 
     25 /*
     26  * Maintain a card table from the the write barrier. All writes of
     27  * non-NULL values to heap addresses should go through an entry in
     28  * WriteBarrier, and from there to here.
     29  *
     30  * The heap is divided into "cards" of GC_CARD_SIZE bytes, as
     31  * determined by GC_CARD_SHIFT. The card table contains one byte of
     32  * data per card, to be used by the GC. The value of the byte will be
     33  * one of GC_CARD_CLEAN or GC_CARD_DIRTY.
     34  *
     35  * After any store of a non-NULL object pointer into a heap object,
     36  * code is obliged to mark the card dirty. The setters in
     37  * ObjectInlines.h [such as dvmSetFieldObject] do this for you. The
     38  * JIT and fast interpreters also contain code to mark cards as dirty.
     39  *
     40  * The card table's base [the "biased card table"] gets set to a
     41  * rather strange value.  In order to keep the JIT from having to
     42  * fabricate or load GC_DIRTY_CARD to store into the card table,
     43  * biased base is within the mmap allocation at a point where it's low
     44  * byte is equal to GC_DIRTY_CARD. See dvmCardTableStartup for details.
     45  */
     46 
     47 /*
     48  * Initializes the card table; must be called before any other
     49  * dvmCardTable*() functions.
     50  */
     51 bool dvmCardTableStartup(size_t heapMaximumSize, size_t growthLimit)
     52 {
     53     size_t length;
     54     void *allocBase;
     55     u1 *biasedBase;
     56     GcHeap *gcHeap = gDvm.gcHeap;
     57     void *heapBase = dvmHeapSourceGetBase();
     58     assert(gcHeap != NULL);
     59     assert(heapBase != NULL);
     60 
     61     /* Set up the card table */
     62     length = heapMaximumSize / GC_CARD_SIZE;
     63     /* Allocate an extra 256 bytes to allow fixed low-byte of base */
     64     allocBase = dvmAllocRegion(length + 0x100, PROT_READ | PROT_WRITE,
     65                             "dalvik-card-table");
     66     if (allocBase == NULL) {
     67         return false;
     68     }
     69     gcHeap->cardTableBase = (u1*)allocBase;
     70     gcHeap->cardTableLength = growthLimit / GC_CARD_SIZE;
     71     gcHeap->cardTableMaxLength = length;
     72     gcHeap->cardTableOffset = 0;
     73     /* All zeros is the correct initial value; all clean. */
     74     assert(GC_CARD_CLEAN == 0);
     75 
     76     biasedBase = (u1 *)((uintptr_t)allocBase -
     77                         ((uintptr_t)heapBase >> GC_CARD_SHIFT));
     78     if (((uintptr_t)biasedBase & 0xff) != GC_CARD_DIRTY) {
     79         int offset = GC_CARD_DIRTY - ((uintptr_t)biasedBase & 0xff);
     80         gcHeap->cardTableOffset = offset + (offset < 0 ? 0x100 : 0);
     81         biasedBase += gcHeap->cardTableOffset;
     82     }
     83     assert(((uintptr_t)biasedBase & 0xff) == GC_CARD_DIRTY);
     84     gDvm.biasedCardTableBase = biasedBase;
     85 
     86     return true;
     87 }
     88 
     89 /*
     90  * Tears down the entire CardTable.
     91  */
     92 void dvmCardTableShutdown()
     93 {
     94     gDvm.biasedCardTableBase = NULL;
     95     munmap(gDvm.gcHeap->cardTableBase, gDvm.gcHeap->cardTableLength);
     96 }
     97 
     98 void dvmClearCardTable()
     99 {
    100     /*
    101      * The goal is to zero out some mmap-allocated pages.  We can accomplish
    102      * this with memset() or madvise(MADV_DONTNEED).  The latter has some
    103      * useful properties, notably that the pages are returned to the system,
    104      * so cards for parts of the heap we haven't expanded into won't be
    105      * allocated physical pages.  On the other hand, if we un-map the card
    106      * area, we'll have to fault it back in as we resume dirtying objects,
    107      * which reduces performance.
    108      *
    109      * We don't cause any correctness issues by failing to clear cards; we
    110      * just take a performance hit during the second pause of the concurrent
    111      * collection.  The "advisory" nature of madvise() isn't a big problem.
    112      *
    113      * What we really want to do is:
    114      * (1) zero out all cards that were touched
    115      * (2) use madvise() to release any pages that won't be used in the near
    116      *     future
    117      *
    118      * For #1, we don't really know which cards were touched, but we can
    119      * approximate it with the "live bits max" value, which tells us the
    120      * highest start address at which an object was allocated.  This may
    121      * leave vestigial nonzero entries at the end if temporary objects are
    122      * created during a concurrent GC, but that should be harmless.  (We
    123      * can round up to the end of the card table page to reduce this.)
    124      *
    125      * For #2, we don't know which pages will be used in the future.  Some
    126      * simple experiments suggested that a "typical" app will touch about
    127      * 60KB of pages while initializing, but drops down to 20-24KB while
    128      * idle.  We can save a few hundred KB system-wide with aggressive
    129      * use of madvise().  The cost of mapping those pages back in is paid
    130      * outside of the GC pause, which reduces the impact.  (We might be
    131      * able to get the benefits by only doing this occasionally, e.g. if
    132      * the heap shrinks a lot or we somehow notice that we've been idle.)
    133      *
    134      * Note that cardTableLength is initially set to the growth limit, and
    135      * on request will be expanded to the heap maximum.
    136      */
    137     assert(gDvm.gcHeap->cardTableBase != NULL);
    138 
    139 #if 1
    140     // zero out cards with memset(), using liveBits as an estimate
    141     const HeapBitmap* liveBits = dvmHeapSourceGetLiveBits();
    142     size_t maxLiveCard = (liveBits->max - liveBits->base) / GC_CARD_SIZE;
    143     maxLiveCard = ALIGN_UP_TO_PAGE_SIZE(maxLiveCard);
    144     if (maxLiveCard > gDvm.gcHeap->cardTableLength) {
    145         maxLiveCard = gDvm.gcHeap->cardTableLength;
    146     }
    147 
    148     memset(gDvm.gcHeap->cardTableBase, GC_CARD_CLEAN, maxLiveCard);
    149 #else
    150     // zero out cards with madvise(), discarding all pages in the card table
    151     madvise(gDvm.gcHeap->cardTableBase, gDvm.gcHeap->cardTableLength,
    152         MADV_DONTNEED);
    153 #endif
    154 }
    155 
    156 /*
    157  * Returns true iff the address is within the bounds of the card table.
    158  */
    159 bool dvmIsValidCard(const u1 *cardAddr)
    160 {
    161     GcHeap *h = gDvm.gcHeap;
    162     u1* begin = h->cardTableBase + h->cardTableOffset;
    163     u1* end = &begin[h->cardTableLength];
    164     return cardAddr >= begin && cardAddr < end;
    165 }
    166 
    167 /*
    168  * Returns the address of the relevent byte in the card table, given
    169  * an address on the heap.
    170  */
    171 u1 *dvmCardFromAddr(const void *addr)
    172 {
    173     u1 *biasedBase = gDvm.biasedCardTableBase;
    174     u1 *cardAddr = biasedBase + ((uintptr_t)addr >> GC_CARD_SHIFT);
    175     assert(dvmIsValidCard(cardAddr));
    176     return cardAddr;
    177 }
    178 
    179 /*
    180  * Returns the first address in the heap which maps to this card.
    181  */
    182 void *dvmAddrFromCard(const u1 *cardAddr)
    183 {
    184     assert(dvmIsValidCard(cardAddr));
    185     uintptr_t offset = cardAddr - gDvm.biasedCardTableBase;
    186     return (void *)(offset << GC_CARD_SHIFT);
    187 }
    188 
    189 /*
    190  * Dirties the card for the given address.
    191  */
    192 void dvmMarkCard(const void *addr)
    193 {
    194     u1 *cardAddr = dvmCardFromAddr(addr);
    195     *cardAddr = GC_CARD_DIRTY;
    196 }
    197 
    198 /*
    199  * Returns true if the object is on a dirty card.
    200  */
    201 static bool isObjectDirty(const Object *obj)
    202 {
    203     assert(obj != NULL);
    204     assert(dvmIsValidObject(obj));
    205     u1 *card = dvmCardFromAddr(obj);
    206     return *card == GC_CARD_DIRTY;
    207 }
    208 
    209 /*
    210  * Context structure for verifying the card table.
    211  */
    212 struct WhiteReferenceCounter {
    213     HeapBitmap *markBits;
    214     size_t whiteRefs;
    215 };
    216 
    217 /*
    218  * Visitor that counts white referents.
    219  */
    220 static void countWhiteReferenceVisitor(void *addr, void *arg)
    221 {
    222     WhiteReferenceCounter *ctx;
    223     Object *obj;
    224 
    225     assert(addr != NULL);
    226     assert(arg != NULL);
    227     obj = *(Object **)addr;
    228     if (obj == NULL) {
    229         return;
    230     }
    231     assert(dvmIsValidObject(obj));
    232     ctx = (WhiteReferenceCounter *)arg;
    233     if (dvmHeapBitmapIsObjectBitSet(ctx->markBits, obj)) {
    234         return;
    235     }
    236     ctx->whiteRefs += 1;
    237 }
    238 
    239 /*
    240  * Visitor that logs white references.
    241  */
    242 static void dumpWhiteReferenceVisitor(void *addr, void *arg)
    243 {
    244     WhiteReferenceCounter *ctx;
    245     Object *obj;
    246 
    247     assert(addr != NULL);
    248     assert(arg != NULL);
    249     obj = *(Object **)addr;
    250     if (obj == NULL) {
    251         return;
    252     }
    253     assert(dvmIsValidObject(obj));
    254     ctx = (WhiteReferenceCounter*)arg;
    255     if (dvmHeapBitmapIsObjectBitSet(ctx->markBits, obj)) {
    256         return;
    257     }
    258     LOGE("object %p is white", obj);
    259 }
    260 
    261 /*
    262  * Visitor that signals the caller when a matching reference is found.
    263  */
    264 static void dumpReferencesVisitor(void *pObj, void *arg)
    265 {
    266     Object *obj = *(Object **)pObj;
    267     Object *lookingFor = *(Object **)arg;
    268     if (lookingFor != NULL && lookingFor == obj) {
    269         *(Object **)arg = NULL;
    270     }
    271 }
    272 
    273 static void dumpReferencesCallback(Object *obj, void *arg)
    274 {
    275     if (obj == (Object *)arg) {
    276         return;
    277     }
    278     dvmVisitObject(dumpReferencesVisitor, obj, &arg);
    279     if (arg == NULL) {
    280         LOGD("Found %p in the heap @ %p", arg, obj);
    281         dvmDumpObject(obj);
    282     }
    283 }
    284 
    285 /*
    286  * Root visitor that looks for matching references.
    287  */
    288 static void dumpReferencesRootVisitor(void *ptr, u4 threadId,
    289                                       RootType type, void *arg)
    290 {
    291     Object *obj = *(Object **)ptr;
    292     Object *lookingFor = *(Object **)arg;
    293     if (obj == lookingFor) {
    294         LOGD("Found %p in a root @ %p", arg, ptr);
    295     }
    296 }
    297 
    298 /*
    299  * Invokes visitors to search for references to an object.
    300  */
    301 static void dumpReferences(const Object *obj)
    302 {
    303     HeapBitmap *bitmap = dvmHeapSourceGetLiveBits();
    304     void *arg = (void *)obj;
    305     dvmVisitRoots(dumpReferencesRootVisitor, arg);
    306     dvmHeapBitmapWalk(bitmap, dumpReferencesCallback, arg);
    307 }
    308 
    309 /*
    310  * Returns true if the given object is a reference object and the
    311  * just the referent is unmarked.
    312  */
    313 static bool isReferentUnmarked(const Object *obj,
    314                                const WhiteReferenceCounter* ctx)
    315 {
    316     assert(obj != NULL);
    317     assert(obj->clazz != NULL);
    318     assert(ctx != NULL);
    319     if (ctx->whiteRefs != 1) {
    320         return false;
    321     } else if (IS_CLASS_FLAG_SET(obj->clazz, CLASS_ISREFERENCE)) {
    322         size_t offset = gDvm.offJavaLangRefReference_referent;
    323         const Object *referent = dvmGetFieldObject(obj, offset);
    324         return !dvmHeapBitmapIsObjectBitSet(ctx->markBits, referent);
    325     } else {
    326         return false;
    327     }
    328 }
    329 
    330 /*
    331  * Returns true if the given object is a string and has been interned
    332  * by the user.
    333  */
    334 static bool isWeakInternedString(const Object *obj)
    335 {
    336     assert(obj != NULL);
    337     if (obj->clazz == gDvm.classJavaLangString) {
    338         return dvmIsWeakInternedString((StringObject *)obj);
    339     } else {
    340         return false;
    341     }
    342 }
    343 
    344 /*
    345  * Returns true if the given object has been pushed on the mark stack
    346  * by root marking.
    347  */
    348 static bool isPushedOnMarkStack(const Object *obj)
    349 {
    350     GcMarkStack *stack = &gDvm.gcHeap->markContext.stack;
    351     for (const Object **ptr = stack->base; ptr < stack->top; ++ptr) {
    352         if (*ptr == obj) {
    353             return true;
    354         }
    355     }
    356     return false;
    357 }
    358 
    359 /*
    360  * Callback applied to marked objects.  If the object is gray and on
    361  * an unmarked card an error is logged and the VM is aborted.  Card
    362  * table verification occurs between root marking and weak reference
    363  * processing.  We treat objects marked from the roots and weak
    364  * references specially as it is permissible for these objects to be
    365  * gray and on an unmarked card.
    366  */
    367 static void verifyCardTableCallback(Object *obj, void *arg)
    368 {
    369     WhiteReferenceCounter ctx = { (HeapBitmap *)arg, 0 };
    370 
    371     dvmVisitObject(countWhiteReferenceVisitor, obj, &ctx);
    372     if (ctx.whiteRefs == 0) {
    373         return;
    374     } else if (isObjectDirty(obj)) {
    375         return;
    376     } else if (isReferentUnmarked(obj, &ctx)) {
    377         return;
    378     } else if (isWeakInternedString(obj)) {
    379         return;
    380     } else if (isPushedOnMarkStack(obj)) {
    381         return;
    382     } else {
    383         LOGE("Verify failed, object %p is gray and on an unmarked card", obj);
    384         dvmDumpObject(obj);
    385         dvmVisitObject(dumpWhiteReferenceVisitor, obj, &ctx);
    386         dumpReferences(obj);
    387         dvmAbort();
    388     }
    389 }
    390 
    391 /*
    392  * Verifies that gray objects are on a dirty card.
    393  */
    394 void dvmVerifyCardTable()
    395 {
    396     HeapBitmap *markBits = gDvm.gcHeap->markContext.bitmap;
    397     dvmHeapBitmapWalk(markBits, verifyCardTableCallback, markBits);
    398 }
    399