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
