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    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 */
89void dvmCardTableShutdown()
90{
91    gDvm.biasedCardTableBase = NULL;
92    munmap(gDvm.gcHeap->cardTableBase, gDvm.gcHeap->cardTableLength);
93}
94
95void 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 */
155bool 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 */
167u1 *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 */
178void *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 */
188void 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 */
197static 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 */
208struct WhiteReferenceCounter {
209    HeapBitmap *markBits;
210    size_t whiteRefs;
211};
212
213/*
214 * Visitor that counts white referents.
215 */
216static 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 */
238static 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 */
260static 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
269static 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 */
284static 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 */
297static 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 */
309static 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 */
330static 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 */
344static 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 */
363static 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 */
390void dvmVerifyCardTable()
391{
392    HeapBitmap *markBits = gDvm.gcHeap->markContext.bitmap;
393    dvmHeapBitmapWalk(markBits, verifyCardTableCallback, markBits);
394}
395