CardTable.cpp revision af6cf54652d1b27885b99e216bee29b955052630
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 */ 51bool 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 */ 92void dvmCardTableShutdown() 93{ 94 gDvm.biasedCardTableBase = NULL; 95 munmap(gDvm.gcHeap->cardTableBase, gDvm.gcHeap->cardTableLength); 96} 97 98void 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. (Also, "the kernel is free to ignore the 108 * advice" makes this sound like something we can't necessarily rely on 109 * to synchronously clear memory; may need to memset *and* madvise.) 110 * 111 * TODO: use memset() to clear out to the current "soft" limit, and 112 * madvise() to clear out the rest. 113 * 114 * Note that cardTableLength is initially set to the growth limit, and 115 * on request will be expanded to the heap maximum. 116 */ 117 assert(gDvm.gcHeap->cardTableBase != NULL); 118 memset(gDvm.gcHeap->cardTableBase, GC_CARD_CLEAN, gDvm.gcHeap->cardTableLength); 119 //madvise(gDvm.gcHeap->cardTableBase, gDvm.gcHeap->cardTableLength, MADV_DONTNEED); 120} 121 122/* 123 * Returns true iff the address is within the bounds of the card table. 124 */ 125bool dvmIsValidCard(const u1 *cardAddr) 126{ 127 GcHeap *h = gDvm.gcHeap; 128 u1* begin = h->cardTableBase + h->cardTableOffset; 129 u1* end = &begin[h->cardTableLength]; 130 return cardAddr >= begin && cardAddr < end; 131} 132 133/* 134 * Returns the address of the relevent byte in the card table, given 135 * an address on the heap. 136 */ 137u1 *dvmCardFromAddr(const void *addr) 138{ 139 u1 *biasedBase = gDvm.biasedCardTableBase; 140 u1 *cardAddr = biasedBase + ((uintptr_t)addr >> GC_CARD_SHIFT); 141 assert(dvmIsValidCard(cardAddr)); 142 return cardAddr; 143} 144 145/* 146 * Returns the first address in the heap which maps to this card. 147 */ 148void *dvmAddrFromCard(const u1 *cardAddr) 149{ 150 assert(dvmIsValidCard(cardAddr)); 151 uintptr_t offset = cardAddr - gDvm.biasedCardTableBase; 152 return (void *)(offset << GC_CARD_SHIFT); 153} 154 155/* 156 * Dirties the card for the given address. 157 */ 158void dvmMarkCard(const void *addr) 159{ 160 u1 *cardAddr = dvmCardFromAddr(addr); 161 *cardAddr = GC_CARD_DIRTY; 162} 163 164/* 165 * Returns true if the object is on a dirty card. 166 */ 167static bool isObjectDirty(const Object *obj) 168{ 169 assert(obj != NULL); 170 assert(dvmIsValidObject(obj)); 171 u1 *card = dvmCardFromAddr(obj); 172 return *card == GC_CARD_DIRTY; 173} 174 175/* 176 * Context structure for verifying the card table. 177 */ 178struct WhiteReferenceCounter { 179 HeapBitmap *markBits; 180 size_t whiteRefs; 181}; 182 183/* 184 * Visitor that counts white referents. 185 */ 186static void countWhiteReferenceVisitor(void *addr, void *arg) 187{ 188 WhiteReferenceCounter *ctx; 189 Object *obj; 190 191 assert(addr != NULL); 192 assert(arg != NULL); 193 obj = *(Object **)addr; 194 if (obj == NULL) { 195 return; 196 } 197 assert(dvmIsValidObject(obj)); 198 ctx = (WhiteReferenceCounter *)arg; 199 if (dvmHeapBitmapIsObjectBitSet(ctx->markBits, obj)) { 200 return; 201 } 202 ctx->whiteRefs += 1; 203} 204 205/* 206 * Visitor that logs white references. 207 */ 208static void dumpWhiteReferenceVisitor(void *addr, void *arg) 209{ 210 WhiteReferenceCounter *ctx; 211 Object *obj; 212 213 assert(addr != NULL); 214 assert(arg != NULL); 215 obj = *(Object **)addr; 216 if (obj == NULL) { 217 return; 218 } 219 assert(dvmIsValidObject(obj)); 220 ctx = (WhiteReferenceCounter*)arg; 221 if (dvmHeapBitmapIsObjectBitSet(ctx->markBits, obj)) { 222 return; 223 } 224 LOGE("object %p is white", obj); 225} 226 227/* 228 * Visitor that signals the caller when a matching reference is found. 229 */ 230static void dumpReferencesVisitor(void *pObj, void *arg) 231{ 232 Object *obj = *(Object **)pObj; 233 Object *lookingFor = *(Object **)arg; 234 if (lookingFor != NULL && lookingFor == obj) { 235 *(Object **)arg = NULL; 236 } 237} 238 239static void dumpReferencesCallback(Object *obj, void *arg) 240{ 241 if (obj == (Object *)arg) { 242 return; 243 } 244 dvmVisitObject(dumpReferencesVisitor, obj, &arg); 245 if (arg == NULL) { 246 LOGD("Found %p in the heap @ %p", arg, obj); 247 dvmDumpObject(obj); 248 } 249} 250 251/* 252 * Root visitor that looks for matching references. 253 */ 254static void dumpReferencesRootVisitor(void *ptr, u4 threadId, 255 RootType type, void *arg) 256{ 257 Object *obj = *(Object **)ptr; 258 Object *lookingFor = *(Object **)arg; 259 if (obj == lookingFor) { 260 LOGD("Found %p in a root @ %p", arg, ptr); 261 } 262} 263 264/* 265 * Invokes visitors to search for references to an object. 266 */ 267static void dumpReferences(const Object *obj) 268{ 269 HeapBitmap *bitmap = dvmHeapSourceGetLiveBits(); 270 void *arg = (void *)obj; 271 dvmVisitRoots(dumpReferencesRootVisitor, arg); 272 dvmHeapBitmapWalk(bitmap, dumpReferencesCallback, arg); 273} 274 275/* 276 * Returns true if the given object is a reference object and the 277 * just the referent is unmarked. 278 */ 279static bool isReferentUnmarked(const Object *obj, 280 const WhiteReferenceCounter* ctx) 281{ 282 assert(obj != NULL); 283 assert(obj->clazz != NULL); 284 assert(ctx != NULL); 285 if (ctx->whiteRefs != 1) { 286 return false; 287 } else if (IS_CLASS_FLAG_SET(obj->clazz, CLASS_ISREFERENCE)) { 288 size_t offset = gDvm.offJavaLangRefReference_referent; 289 const Object *referent = dvmGetFieldObject(obj, offset); 290 return !dvmHeapBitmapIsObjectBitSet(ctx->markBits, referent); 291 } else { 292 return false; 293 } 294} 295 296/* 297 * Returns true if the given object is a string and has been interned 298 * by the user. 299 */ 300static bool isWeakInternedString(const Object *obj) 301{ 302 assert(obj != NULL); 303 if (obj->clazz == gDvm.classJavaLangString) { 304 return dvmIsWeakInternedString((StringObject *)obj); 305 } else { 306 return false; 307 } 308} 309 310/* 311 * Returns true if the given object has been pushed on the mark stack 312 * by root marking. 313 */ 314static bool isPushedOnMarkStack(const Object *obj) 315{ 316 GcMarkStack *stack = &gDvm.gcHeap->markContext.stack; 317 for (const Object **ptr = stack->base; ptr < stack->top; ++ptr) { 318 if (*ptr == obj) { 319 return true; 320 } 321 } 322 return false; 323} 324 325/* 326 * Callback applied to marked objects. If the object is gray and on 327 * an unmarked card an error is logged and the VM is aborted. Card 328 * table verification occurs between root marking and weak reference 329 * processing. We treat objects marked from the roots and weak 330 * references specially as it is permissible for these objects to be 331 * gray and on an unmarked card. 332 */ 333static void verifyCardTableCallback(Object *obj, void *arg) 334{ 335 WhiteReferenceCounter ctx = { (HeapBitmap *)arg, 0 }; 336 337 dvmVisitObject(countWhiteReferenceVisitor, obj, &ctx); 338 if (ctx.whiteRefs == 0) { 339 return; 340 } else if (isObjectDirty(obj)) { 341 return; 342 } else if (isReferentUnmarked(obj, &ctx)) { 343 return; 344 } else if (isWeakInternedString(obj)) { 345 return; 346 } else if (isPushedOnMarkStack(obj)) { 347 return; 348 } else { 349 LOGE("Verify failed, object %p is gray and on an unmarked card", obj); 350 dvmDumpObject(obj); 351 dvmVisitObject(dumpWhiteReferenceVisitor, obj, &ctx); 352 dumpReferences(obj); 353 dvmAbort(); 354 } 355} 356 357/* 358 * Verifies that gray objects are on a dirty card. 359 */ 360void dvmVerifyCardTable() 361{ 362 HeapBitmap *markBits = gDvm.gcHeap->markContext.bitmap; 363 dvmHeapBitmapWalk(markBits, verifyCardTableCallback, markBits); 364} 365