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