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/HeapSource.h" 21 #include "alloc/Visit.h" 22 23 /* 24 * Maintain a card table from the the write barrier. All writes of 25 * non-NULL values to heap addresses should go through an entry in 26 * WriteBarrier, and from there to here. 27 * 28 * The heap is divided into "cards" of GC_CARD_SIZE bytes, as 29 * determined by GC_CARD_SHIFT. The card table contains one byte of 30 * data per card, to be used by the GC. The value of the byte will be 31 * one of GC_CARD_CLEAN or GC_CARD_DIRTY. 32 * 33 * After any store of a non-NULL object pointer into a heap object, 34 * code is obliged to mark the card dirty. The setters in 35 * ObjectInlines.h [such as dvmSetFieldObject] do this for you. The 36 * JIT and fast interpreters also contain code to mark cards as dirty. 37 * 38 * The card table's base [the "biased card table"] gets set to a 39 * rather strange value. In order to keep the JIT from having to 40 * fabricate or load GC_DIRTY_CARD to store into the card table, 41 * biased base is within the mmap allocation at a point where it's low 42 * byte is equal to GC_DIRTY_CARD. See dvmCardTableStartup for details. 43 */ 44 45 /* 46 * Initializes the card table; must be called before any other 47 * dvmCardTable*() functions. 48 */ 49 bool dvmCardTableStartup(void) 50 { 51 size_t length; 52 void *allocBase; 53 u1 *biasedBase; 54 GcHeap *gcHeap = gDvm.gcHeap; 55 void *heapBase = dvmHeapSourceGetBase(); 56 assert(gcHeap != NULL); 57 assert(heapBase != NULL); 58 59 /* Set up the card table */ 60 length = gDvm.heapSizeMax / GC_CARD_SIZE; 61 /* Allocate an extra 256 bytes to allow fixed low-byte of base */ 62 allocBase = dvmAllocRegion(length + 0x100, PROT_READ | PROT_WRITE, 63 "dalvik-card-table"); 64 if (allocBase == NULL) { 65 return false; 66 } 67 gcHeap->cardTableBase = allocBase; 68 gcHeap->cardTableLength = length; 69 /* All zeros is the correct initial value; all clean. */ 70 assert(GC_CARD_CLEAN == 0); 71 72 biasedBase = (u1 *)((uintptr_t)allocBase - 73 ((uintptr_t)heapBase >> GC_CARD_SHIFT)); 74 if (((uintptr_t)biasedBase & 0xff) != GC_CARD_DIRTY) { 75 int offset = GC_CARD_DIRTY - ((uintptr_t)biasedBase & 0xff); 76 biasedBase += offset + (offset < 0 ? 0x100 : 0); 77 } 78 assert(((uintptr_t)biasedBase & 0xff) == GC_CARD_DIRTY); 79 gDvm.biasedCardTableBase = biasedBase; 80 81 return true; 82 } 83 84 /* 85 * Tears down the entire CardTable. 86 */ 87 void dvmCardTableShutdown() 88 { 89 gDvm.biasedCardTableBase = NULL; 90 munmap(gDvm.gcHeap->cardTableBase, gDvm.gcHeap->cardTableLength); 91 } 92 93 void dvmClearCardTable(void) 94 { 95 assert(gDvm.gcHeap->cardTableBase != NULL); 96 memset(gDvm.gcHeap->cardTableBase, GC_CARD_CLEAN, gDvm.gcHeap->cardTableLength); 97 } 98 99 /* 100 * Returns true iff the address is within the bounds of the card table. 101 */ 102 bool dvmIsValidCard(const u1 *cardAddr) 103 { 104 GcHeap *h = gDvm.gcHeap; 105 return cardAddr >= h->cardTableBase && 106 cardAddr < &h->cardTableBase[h->cardTableLength]; 107 } 108 109 /* 110 * Returns the address of the relevent byte in the card table, given 111 * an address on the heap. 112 */ 113 u1 *dvmCardFromAddr(const void *addr) 114 { 115 u1 *biasedBase = gDvm.biasedCardTableBase; 116 u1 *cardAddr = biasedBase + ((uintptr_t)addr >> GC_CARD_SHIFT); 117 assert(dvmIsValidCard(cardAddr)); 118 return cardAddr; 119 } 120 121 /* 122 * Returns the first address in the heap which maps to this card. 123 */ 124 void *dvmAddrFromCard(const u1 *cardAddr) 125 { 126 assert(dvmIsValidCard(cardAddr)); 127 uintptr_t offset = cardAddr - gDvm.biasedCardTableBase; 128 return (void *)(offset << GC_CARD_SHIFT); 129 } 130 131 /* 132 * Dirties the card for the given address. 133 */ 134 void dvmMarkCard(const void *addr) 135 { 136 u1 *cardAddr = dvmCardFromAddr(addr); 137 *cardAddr = GC_CARD_DIRTY; 138 } 139 140 /* 141 * Returns true if the object is on a dirty card. 142 */ 143 static bool isObjectDirty(const Object *obj) 144 { 145 assert(obj != NULL); 146 assert(dvmIsValidObject(obj)); 147 u1 *card = dvmCardFromAddr(obj); 148 return *card == GC_CARD_DIRTY; 149 } 150 151 /* 152 * Context structure for verifying the card table. 153 */ 154 typedef struct { 155 HeapBitmap *markBits; 156 size_t whiteRefs; 157 } WhiteReferenceCounter; 158 159 /* 160 * Visitor that counts white referents. 161 */ 162 static void countWhiteReferenceVisitor(void *addr, void *arg) 163 { 164 WhiteReferenceCounter *ctx; 165 Object *obj; 166 167 assert(addr != NULL); 168 assert(arg != NULL); 169 obj = *(Object **)addr; 170 if (obj == NULL) { 171 return; 172 } 173 assert(dvmIsValidObject(obj)); 174 ctx = arg; 175 if (dvmHeapBitmapIsObjectBitSet(ctx->markBits, obj)) { 176 return; 177 } 178 ctx->whiteRefs += 1; 179 } 180 181 /* 182 * Returns true if the given object is a reference object and the 183 * just the referent is unmarked. 184 */ 185 static bool isReferentUnmarked(const Object *obj, 186 const WhiteReferenceCounter* ctx) 187 { 188 assert(obj != NULL); 189 assert(obj->clazz != NULL); 190 assert(ctx != NULL); 191 if (ctx->whiteRefs != 1) { 192 return false; 193 } else if (IS_CLASS_FLAG_SET(obj->clazz, CLASS_ISREFERENCE)) { 194 size_t offset = gDvm.offJavaLangRefReference_referent; 195 const Object *referent = dvmGetFieldObject(obj, offset); 196 return !dvmHeapBitmapIsObjectBitSet(ctx->markBits, referent); 197 } else { 198 return false; 199 } 200 } 201 202 /* 203 * Returns true if the given object is a string and has been interned 204 * by the user. 205 */ 206 static bool isWeakInternedString(const Object *obj) 207 { 208 assert(obj != NULL); 209 if (obj->clazz == gDvm.classJavaLangString) { 210 return dvmIsWeakInternedString((StringObject *)obj); 211 } else { 212 return false; 213 } 214 } 215 216 /* 217 * Returns true if the given object has been pushed on the mark stack 218 * by root marking. 219 */ 220 static bool isPushedOnMarkStack(const Object *obj) 221 { 222 GcMarkContext *ctx = &gDvm.gcHeap->markContext; 223 const Object **ptr; 224 225 for (ptr = ctx->stack.top; ptr != ctx->stack.base; ++ptr) { 226 if (*ptr == obj) { 227 return true; 228 } 229 } 230 return false; 231 } 232 233 /* 234 * Callback applied to marked objects. If the object is gray and on 235 * an unmarked card an error is logged and the VM is aborted. Card 236 * table verification occurs between root marking and weak reference 237 * processing. We treat objects marked from the roots and weak 238 * references specially as it is permissible for these objects to be 239 * gray and on an unmarked card. 240 */ 241 static void verifyCardTableCallback(void *ptr, void *arg) 242 { 243 Object *obj = ptr; 244 WhiteReferenceCounter ctx = { arg, 0 }; 245 246 dvmVisitObject(countWhiteReferenceVisitor, obj, &ctx); 247 if (ctx.whiteRefs == 0) { 248 return; 249 } else if (isObjectDirty(obj)) { 250 return; 251 } else if (isReferentUnmarked(obj, &ctx)) { 252 return; 253 } else if (isWeakInternedString(obj)) { 254 return; 255 } else if (isPushedOnMarkStack(obj)) { 256 return; 257 } else { 258 LOGE("Verify failed, object %p is gray and on an unmarked card", obj); 259 dvmDumpObject(obj); 260 dvmAbort(); 261 } 262 } 263 264 /* 265 * Verifies that gray objects are on a dirty card. 266 */ 267 void dvmVerifyCardTable(void) 268 { 269 HeapBitmap *markBits = gDvm.gcHeap->markContext.bitmap; 270 dvmHeapBitmapWalk(markBits, verifyCardTableCallback, markBits); 271 } 272
