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 */
dvmCardTableStartup(size_t heapMaximumSize,size_t growthLimit)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 */
dvmCardTableShutdown()92 void dvmCardTableShutdown()
93 {
94 gDvm.biasedCardTableBase = NULL;
95 munmap(gDvm.gcHeap->cardTableBase, gDvm.gcHeap->cardTableLength);
96 }
97
dvmClearCardTable()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 */
dvmIsValidCard(const u1 * cardAddr)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 */
dvmCardFromAddr(const void * addr)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 */
dvmAddrFromCard(const u1 * cardAddr)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 */
dvmMarkCard(const void * addr)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 */
isObjectDirty(const Object * obj)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 */
countWhiteReferenceVisitor(void * addr,void * arg)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 */
dumpWhiteReferenceVisitor(void * addr,void * arg)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 ALOGE("object %p is white", obj);
259 }
260
261 /*
262 * Visitor that signals the caller when a matching reference is found.
263 */
dumpReferencesVisitor(void * pObj,void * arg)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
dumpReferencesCallback(Object * obj,void * arg)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 ALOGD("Found %p in the heap @ %p", arg, obj);
281 dvmDumpObject(obj);
282 }
283 }
284
285 /*
286 * Root visitor that looks for matching references.
287 */
dumpReferencesRootVisitor(void * ptr,u4 threadId,RootType type,void * arg)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 ALOGD("Found %p in a root @ %p", arg, ptr);
295 }
296 }
297
298 /*
299 * Invokes visitors to search for references to an object.
300 */
dumpReferences(const Object * obj)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 */
isReferentUnmarked(const Object * obj,const WhiteReferenceCounter * ctx)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 */
isWeakInternedString(const Object * obj)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 */
isPushedOnMarkStack(const Object * obj)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 */
verifyCardTableCallback(Object * obj,void * arg)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 ALOGE("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 */
dvmVerifyCardTable()394 void dvmVerifyCardTable()
395 {
396 HeapBitmap *markBits = gDvm.gcHeap->markContext.bitmap;
397 dvmHeapBitmapWalk(markBits, verifyCardTableCallback, markBits);
398 }
399