/*
* 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;
void *heapBase = dvmHeapSourceGetBase();
assert(gcHeap != NULL);
assert(heapBase != NULL);
/* 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;
gcHeap->cardTableOffset = 0;
/* All zeros is the correct initial value; all clean. */
assert(GC_CARD_CLEAN == 0);
biasedBase = (u1 *)((uintptr_t)allocBase -
((uintptr_t)heapBase >> GC_CARD_SHIFT));
if (((uintptr_t)biasedBase & 0xff) != GC_CARD_DIRTY) {
int 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 1
// 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);
#else
// zero out cards with madvise(), discarding all pages in the card table
madvise(gDvm.gcHeap->cardTableBase, gDvm.gcHeap->cardTableLength,
MADV_DONTNEED);
#endif
}
/*
* 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 relevent 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);
}