MarkSweep.cpp revision 485dfb5ccb6d8b2c5d498ff6ee41b14e79103e3c 
1/*
2 * Copyright (C) 2008 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 "Dalvik.h"
18#include "alloc/CardTable.h"
19#include "alloc/HeapBitmap.h"
20#include "alloc/HeapBitmapInlines.h"
21#include "alloc/HeapInternal.h"
22#include "alloc/HeapSource.h"
23#include "alloc/MarkSweep.h"
24#include "alloc/Visit.h"
25#include <limits.h>     // for ULONG_MAX
26#include <sys/mman.h>   // for madvise(), mmap()
27#include <errno.h>
28
29typedef unsigned long Word;
30const size_t kWordSize = sizeof(Word);
31
32/*
33 * Returns true if the given object is marked.
34 */
35static bool isMarked(const Object *obj, const GcMarkContext *ctx)
36{
37    return dvmHeapBitmapIsObjectBitSet(ctx->bitmap, obj);
38}
39
40/*
41 * Initializes the stack top and advises the mark stack pages as needed.
42 */
43static bool createMarkStack(GcMarkStack *stack)
44{
45    assert(stack != NULL);
46    size_t length = dvmHeapSourceGetIdealFootprint() * sizeof(Object*) /
47        (sizeof(Object) + HEAP_SOURCE_CHUNK_OVERHEAD);
48    madvise(stack->base, length, MADV_NORMAL);
49    stack->top = stack->base;
50    return true;
51}
52
53/*
54 * Assigns NULL to the stack top and advises the mark stack pages as
55 * not needed.
56 */
57static void destroyMarkStack(GcMarkStack *stack)
58{
59    assert(stack != NULL);
60    madvise(stack->base, stack->length, MADV_DONTNEED);
61    stack->top = NULL;
62}
63
64/*
65 * Pops an object from the mark stack.
66 */
67static void markStackPush(GcMarkStack *stack, const Object *obj)
68{
69    assert(stack != NULL);
70    assert(stack->base <= stack->top);
71    assert(stack->limit > stack->top);
72    assert(obj != NULL);
73    *stack->top = obj;
74    ++stack->top;
75}
76
77/*
78 * Pushes an object on the mark stack.
79 */
80static const Object *markStackPop(GcMarkStack *stack)
81{
82    assert(stack != NULL);
83    assert(stack->base < stack->top);
84    assert(stack->limit > stack->top);
85    --stack->top;
86    return *stack->top;
87}
88
89bool dvmHeapBeginMarkStep(bool isPartial)
90{
91    GcMarkContext *ctx = &gDvm.gcHeap->markContext;
92
93    if (!createMarkStack(&ctx->stack)) {
94        return false;
95    }
96    ctx->finger = NULL;
97    ctx->immuneLimit = (char*)dvmHeapSourceGetImmuneLimit(isPartial);
98    return true;
99}
100
101static long setAndReturnMarkBit(GcMarkContext *ctx, const void *obj)
102{
103    return dvmHeapBitmapSetAndReturnObjectBit(ctx->bitmap, obj);
104}
105
106static void markObjectNonNull(const Object *obj, GcMarkContext *ctx,
107                              bool checkFinger)
108{
109    assert(ctx != NULL);
110    assert(obj != NULL);
111    assert(dvmIsValidObject(obj));
112    if (obj < (Object *)ctx->immuneLimit) {
113        assert(isMarked(obj, ctx));
114        return;
115    }
116    if (!setAndReturnMarkBit(ctx, obj)) {
117        /* This object was not previously marked.
118         */
119        if (checkFinger && (void *)obj < ctx->finger) {
120            /* This object will need to go on the mark stack.
121             */
122            markStackPush(&ctx->stack, obj);
123        }
124    }
125}
126
127/* Used to mark objects when recursing.  Recursion is done by moving
128 * the finger across the bitmaps in address order and marking child
129 * objects.  Any newly-marked objects whose addresses are lower than
130 * the finger won't be visited by the bitmap scan, so those objects
131 * need to be added to the mark stack.
132 */
133static void markObject(const Object *obj, GcMarkContext *ctx)
134{
135    if (obj != NULL) {
136        markObjectNonNull(obj, ctx, true);
137    }
138}
139
140/*
141 * Callback applied to root references during the initial root
142 * marking.  Marks white objects but does not push them on the mark
143 * stack.
144 */
145static void rootMarkObjectVisitor(void *addr, u4 thread, RootType type,
146                                  void *arg)
147{
148    assert(addr != NULL);
149    assert(arg != NULL);
150    Object *obj = *(Object **)addr;
151    GcMarkContext *ctx = (GcMarkContext *)arg;
152    if (obj != NULL) {
153        markObjectNonNull(obj, ctx, false);
154    }
155}
156
157/* Mark the set of root objects.
158 *
159 * Things we need to scan:
160 * - System classes defined by root classloader
161 * - For each thread:
162 *   - Interpreted stack, from top to "curFrame"
163 *     - Dalvik registers (args + local vars)
164 *   - JNI local references
165 *   - Automatic VM local references (TrackedAlloc)
166 *   - Associated Thread/VMThread object
167 *   - ThreadGroups (could track & start with these instead of working
168 *     upward from Threads)
169 *   - Exception currently being thrown, if present
170 * - JNI global references
171 * - Interned string table
172 * - Primitive classes
173 * - Special objects
174 *   - gDvm.outOfMemoryObj
175 * - Objects in debugger object registry
176 *
177 * Don't need:
178 * - Native stack (for in-progress stuff in the VM)
179 *   - The TrackedAlloc stuff watches all native VM references.
180 */
181void dvmHeapMarkRootSet()
182{
183    GcHeap *gcHeap = gDvm.gcHeap;
184    dvmMarkImmuneObjects(gcHeap->markContext.immuneLimit);
185    dvmVisitRoots(rootMarkObjectVisitor, &gcHeap->markContext);
186}
187
188/*
189 * Callback applied to root references during root remarking.  Marks
190 * white objects and pushes them on the mark stack.
191 */
192static void rootReMarkObjectVisitor(void *addr, u4 thread, RootType type,
193                                    void *arg)
194{
195    assert(addr != NULL);
196    assert(arg != NULL);
197    Object *obj = *(Object **)addr;
198    GcMarkContext *ctx = (GcMarkContext *)arg;
199    if (obj != NULL) {
200        markObjectNonNull(obj, ctx, true);
201    }
202}
203
204/*
205 * Grays all references in the roots.
206 */
207void dvmHeapReMarkRootSet()
208{
209    GcMarkContext *ctx = &gDvm.gcHeap->markContext;
210    assert(ctx->finger == (void *)ULONG_MAX);
211    dvmVisitRoots(rootReMarkObjectVisitor, ctx);
212}
213
214/*
215 * Scans instance fields.
216 */
217static void scanFields(const Object *obj, GcMarkContext *ctx)
218{
219    assert(obj != NULL);
220    assert(obj->clazz != NULL);
221    assert(ctx != NULL);
222    if (obj->clazz->refOffsets != CLASS_WALK_SUPER) {
223        unsigned int refOffsets = obj->clazz->refOffsets;
224        while (refOffsets != 0) {
225            size_t rshift = CLZ(refOffsets);
226            size_t offset = CLASS_OFFSET_FROM_CLZ(rshift);
227            Object *ref = dvmGetFieldObject(obj, offset);
228            markObject(ref, ctx);
229            refOffsets &= ~(CLASS_HIGH_BIT >> rshift);
230        }
231    } else {
232        for (ClassObject *clazz = obj->clazz;
233             clazz != NULL;
234             clazz = clazz->super) {
235            InstField *field = clazz->ifields;
236            for (int i = 0; i < clazz->ifieldRefCount; ++i, ++field) {
237                void *addr = BYTE_OFFSET(obj, field->byteOffset);
238                Object *ref = ((JValue *)addr)->l;
239                markObject(ref, ctx);
240            }
241        }
242    }
243}
244
245/*
246 * Scans the static fields of a class object.
247 */
248static void scanStaticFields(const ClassObject *clazz, GcMarkContext *ctx)
249{
250    assert(clazz != NULL);
251    assert(ctx != NULL);
252    for (int i = 0; i < clazz->sfieldCount; ++i) {
253        char ch = clazz->sfields[i].signature[0];
254        if (ch == '[' || ch == 'L') {
255            Object *obj = clazz->sfields[i].value.l;
256            markObject(obj, ctx);
257        }
258    }
259}
260
261/*
262 * Visit the interfaces of a class object.
263 */
264static void scanInterfaces(const ClassObject *clazz, GcMarkContext *ctx)
265{
266    assert(clazz != NULL);
267    assert(ctx != NULL);
268    for (int i = 0; i < clazz->interfaceCount; ++i) {
269        markObject((const Object *)clazz->interfaces[i], ctx);
270    }
271}
272
273/*
274 * Scans the header, static field references, and interface
275 * pointers of a class object.
276 */
277static void scanClassObject(const Object *obj, GcMarkContext *ctx)
278{
279    assert(obj != NULL);
280    assert(dvmIsClassObject(obj));
281    assert(ctx != NULL);
282    markObject((const Object *)obj->clazz, ctx);
283    const ClassObject *asClass = (const ClassObject *)obj;
284    if (IS_CLASS_FLAG_SET(asClass, CLASS_ISARRAY)) {
285        markObject((const Object *)asClass->elementClass, ctx);
286    }
287    /* Do super and the interfaces contain Objects and not dex idx values? */
288    if (asClass->status > CLASS_IDX) {
289        markObject((const Object *)asClass->super, ctx);
290    }
291    markObject((const Object *)asClass->classLoader, ctx);
292    scanFields(obj, ctx);
293    scanStaticFields(asClass, ctx);
294    if (asClass->status > CLASS_IDX) {
295        scanInterfaces(asClass, ctx);
296    }
297}
298
299/*
300 * Scans the header of all array objects.  If the array object is
301 * specialized to a reference type, scans the array data as well.
302 */
303static void scanArrayObject(const Object *obj, GcMarkContext *ctx)
304{
305    assert(obj != NULL);
306    assert(obj->clazz != NULL);
307    assert(ctx != NULL);
308    markObject((const Object *)obj->clazz, ctx);
309    if (IS_CLASS_FLAG_SET(obj->clazz, CLASS_ISOBJECTARRAY)) {
310        const ArrayObject *array = (const ArrayObject *)obj;
311        const Object **contents = (const Object **)(void *)array->contents;
312        for (size_t i = 0; i < array->length; ++i) {
313            markObject(contents[i], ctx);
314        }
315    }
316}
317
318/*
319 * Returns class flags relating to Reference subclasses.
320 */
321static int referenceClassFlags(const Object *obj)
322{
323    int flags = CLASS_ISREFERENCE |
324                CLASS_ISWEAKREFERENCE |
325                CLASS_ISFINALIZERREFERENCE |
326                CLASS_ISPHANTOMREFERENCE;
327    return GET_CLASS_FLAG_GROUP(obj->clazz, flags);
328}
329
330/*
331 * Returns true if the object derives from SoftReference.
332 */
333static bool isSoftReference(const Object *obj)
334{
335    return referenceClassFlags(obj) == CLASS_ISREFERENCE;
336}
337
338/*
339 * Returns true if the object derives from WeakReference.
340 */
341static bool isWeakReference(const Object *obj)
342{
343    return referenceClassFlags(obj) & CLASS_ISWEAKREFERENCE;
344}
345
346/*
347 * Returns true if the object derives from FinalizerReference.
348 */
349static bool isFinalizerReference(const Object *obj)
350{
351    return referenceClassFlags(obj) & CLASS_ISFINALIZERREFERENCE;
352}
353
354/*
355 * Returns true if the object derives from PhantomReference.
356 */
357static bool isPhantomReference(const Object *obj)
358{
359    return referenceClassFlags(obj) & CLASS_ISPHANTOMREFERENCE;
360}
361
362/*
363 * Adds a reference to the tail of a circular queue of references.
364 */
365static void enqueuePendingReference(Object *ref, Object **list)
366{
367    assert(ref != NULL);
368    assert(list != NULL);
369    size_t offset = gDvm.offJavaLangRefReference_pendingNext;
370    if (*list == NULL) {
371        dvmSetFieldObject(ref, offset, ref);
372        *list = ref;
373    } else {
374        Object *head = dvmGetFieldObject(*list, offset);
375        dvmSetFieldObject(ref, offset, head);
376        dvmSetFieldObject(*list, offset, ref);
377    }
378}
379
380/*
381 * Removes the reference at the head of a circular queue of
382 * references.
383 */
384static Object *dequeuePendingReference(Object **list)
385{
386    assert(list != NULL);
387    assert(*list != NULL);
388    size_t offset = gDvm.offJavaLangRefReference_pendingNext;
389    Object *head = dvmGetFieldObject(*list, offset);
390    Object *ref;
391    if (*list == head) {
392        ref = *list;
393        *list = NULL;
394    } else {
395        Object *next = dvmGetFieldObject(head, offset);
396        dvmSetFieldObject(*list, offset, next);
397        ref = head;
398    }
399    dvmSetFieldObject(ref, offset, NULL);
400    return ref;
401}
402
403/*
404 * Process the "referent" field in a java.lang.ref.Reference.  If the
405 * referent has not yet been marked, put it on the appropriate list in
406 * the gcHeap for later processing.
407 */
408static void delayReferenceReferent(Object *obj, GcMarkContext *ctx)
409{
410    assert(obj != NULL);
411    assert(obj->clazz != NULL);
412    assert(IS_CLASS_FLAG_SET(obj->clazz, CLASS_ISREFERENCE));
413    assert(ctx != NULL);
414    GcHeap *gcHeap = gDvm.gcHeap;
415    size_t pendingNextOffset = gDvm.offJavaLangRefReference_pendingNext;
416    size_t referentOffset = gDvm.offJavaLangRefReference_referent;
417    Object *pending = dvmGetFieldObject(obj, pendingNextOffset);
418    Object *referent = dvmGetFieldObject(obj, referentOffset);
419    if (pending == NULL && referent != NULL && !isMarked(referent, ctx)) {
420        Object **list = NULL;
421        if (isSoftReference(obj)) {
422            list = &gcHeap->softReferences;
423        } else if (isWeakReference(obj)) {
424            list = &gcHeap->weakReferences;
425        } else if (isFinalizerReference(obj)) {
426            list = &gcHeap->finalizerReferences;
427        } else if (isPhantomReference(obj)) {
428            list = &gcHeap->phantomReferences;
429        }
430        assert(list != NULL);
431        enqueuePendingReference(obj, list);
432    }
433}
434
435/*
436 * Scans the header and field references of a data object.
437 */
438static void scanDataObject(const Object *obj, GcMarkContext *ctx)
439{
440    assert(obj != NULL);
441    assert(obj->clazz != NULL);
442    assert(ctx != NULL);
443    markObject((const Object *)obj->clazz, ctx);
444    scanFields(obj, ctx);
445    if (IS_CLASS_FLAG_SET(obj->clazz, CLASS_ISREFERENCE)) {
446        delayReferenceReferent((Object *)obj, ctx);
447    }
448}
449
450/*
451 * Scans an object reference.  Determines the type of the reference
452 * and dispatches to a specialized scanning routine.
453 */
454static void scanObject(const Object *obj, GcMarkContext *ctx)
455{
456    assert(obj != NULL);
457    assert(obj->clazz != NULL);
458    if (obj->clazz == gDvm.classJavaLangClass) {
459        scanClassObject(obj, ctx);
460    } else if (IS_CLASS_FLAG_SET(obj->clazz, CLASS_ISARRAY)) {
461        scanArrayObject(obj, ctx);
462    } else {
463        scanDataObject(obj, ctx);
464    }
465}
466
467/*
468 * Scan anything that's on the mark stack.  We can't use the bitmaps
469 * anymore, so use a finger that points past the end of them.
470 */
471static void processMarkStack(GcMarkContext *ctx)
472{
473    assert(ctx != NULL);
474    assert(ctx->finger == (void *)ULONG_MAX);
475    assert(ctx->stack.top >= ctx->stack.base);
476    GcMarkStack *stack = &ctx->stack;
477    while (stack->top > stack->base) {
478        const Object *obj = markStackPop(stack);
479        scanObject(obj, ctx);
480    }
481}
482
483static size_t objectSize(const Object *obj)
484{
485    assert(dvmIsValidObject(obj));
486    assert(dvmIsValidObject((Object *)obj->clazz));
487    if (IS_CLASS_FLAG_SET(obj->clazz, CLASS_ISARRAY)) {
488        return dvmArrayObjectSize((ArrayObject *)obj);
489    } else if (obj->clazz == gDvm.classJavaLangClass) {
490        return dvmClassObjectSize((ClassObject *)obj);
491    } else {
492        return obj->clazz->objectSize;
493    }
494}
495
496/*
497 * Scans forward to the header of the next marked object between start
498 * and limit.  Returns NULL if no marked objects are in that region.
499 */
500static Object *nextGrayObject(const u1 *base, const u1 *limit,
501                              const HeapBitmap *markBits)
502{
503    const u1 *ptr;
504
505    assert(base < limit);
506    assert(limit - base <= GC_CARD_SIZE);
507    for (ptr = base; ptr < limit; ptr += HB_OBJECT_ALIGNMENT) {
508        if (dvmHeapBitmapIsObjectBitSet(markBits, ptr))
509            return (Object *)ptr;
510    }
511    return NULL;
512}
513
514/*
515 * Scans range of dirty cards between start and end.  A range of dirty
516 * cards is composed consecutively dirty cards or dirty cards spanned
517 * by a gray object.  Returns the address of a clean card if the scan
518 * reached a clean card or NULL if the scan reached the end.
519 */
520const u1 *scanDirtyCards(const u1 *start, const u1 *end,
521                         GcMarkContext *ctx)
522{
523    const HeapBitmap *markBits = ctx->bitmap;
524    const u1 *card = start, *prevAddr = NULL;
525    while (card < end) {
526        if (*card != GC_CARD_DIRTY) {
527            return card;
528        }
529        const u1 *ptr = prevAddr ? prevAddr : (u1*)dvmAddrFromCard(card);
530        const u1 *limit = ptr + GC_CARD_SIZE;
531        while (ptr < limit) {
532            Object *obj = nextGrayObject(ptr, limit, markBits);
533            if (obj == NULL) {
534                break;
535            }
536            scanObject(obj, ctx);
537            ptr = (u1*)obj + ALIGN_UP(objectSize(obj), HB_OBJECT_ALIGNMENT);
538        }
539        if (ptr < limit) {
540            /* Ended within the current card, advance to the next card. */
541            ++card;
542            prevAddr = NULL;
543        } else {
544            /* Ended past the current card, skip ahead. */
545            card = dvmCardFromAddr(ptr);
546            prevAddr = ptr;
547        }
548    }
549    return NULL;
550}
551
552/*
553 * Blackens gray objects found on dirty cards.
554 */
555static void scanGrayObjects(GcMarkContext *ctx)
556{
557    GcHeap *h = gDvm.gcHeap;
558    const u1 *base, *limit, *ptr, *dirty;
559
560    base = &h->cardTableBase[0];
561    limit = dvmCardFromAddr((u1 *)dvmHeapSourceGetLimit());
562    assert(limit <= &h->cardTableBase[h->cardTableLength]);
563
564    ptr = base;
565    for (;;) {
566        dirty = (const u1 *)memchr(ptr, GC_CARD_DIRTY, limit - ptr);
567        if (dirty == NULL) {
568            break;
569        }
570        assert((dirty > ptr) && (dirty < limit));
571        ptr = scanDirtyCards(dirty, limit, ctx);
572        if (ptr == NULL) {
573            break;
574        }
575        assert((ptr > dirty) && (ptr < limit));
576    }
577}
578
579/*
580 * Callback for scanning each object in the bitmap.  The finger is set
581 * to the address corresponding to the lowest address in the next word
582 * of bits in the bitmap.
583 */
584static void scanBitmapCallback(Object *obj, void *finger, void *arg)
585{
586    GcMarkContext *ctx = (GcMarkContext *)arg;
587    ctx->finger = (void *)finger;
588    scanObject(obj, ctx);
589}
590
591/* Given bitmaps with the root set marked, find and mark all
592 * reachable objects.  When this returns, the entire set of
593 * live objects will be marked and the mark stack will be empty.
594 */
595void dvmHeapScanMarkedObjects(void)
596{
597    GcMarkContext *ctx = &gDvm.gcHeap->markContext;
598
599    assert(ctx->finger == NULL);
600
601    /* The bitmaps currently have bits set for the root set.
602     * Walk across the bitmaps and scan each object.
603     */
604    dvmHeapBitmapScanWalk(ctx->bitmap, scanBitmapCallback, ctx);
605
606    ctx->finger = (void *)ULONG_MAX;
607
608    /* We've walked the mark bitmaps.  Scan anything that's
609     * left on the mark stack.
610     */
611    processMarkStack(ctx);
612}
613
614void dvmHeapReScanMarkedObjects()
615{
616    GcMarkContext *ctx = &gDvm.gcHeap->markContext;
617
618    /*
619     * The finger must have been set to the maximum value to ensure
620     * that gray objects will be pushed onto the mark stack.
621     */
622    assert(ctx->finger == (void *)ULONG_MAX);
623    scanGrayObjects(ctx);
624    processMarkStack(ctx);
625}
626
627/*
628 * Clear the referent field.
629 */
630static void clearReference(Object *reference)
631{
632    size_t offset = gDvm.offJavaLangRefReference_referent;
633    dvmSetFieldObject(reference, offset, NULL);
634}
635
636/*
637 * Returns true if the reference was registered with a reference queue
638 * and has not yet been enqueued.
639 */
640static bool isEnqueuable(const Object *reference)
641{
642    assert(reference != NULL);
643    Object *queue = dvmGetFieldObject(reference,
644            gDvm.offJavaLangRefReference_queue);
645    Object *queueNext = dvmGetFieldObject(reference,
646            gDvm.offJavaLangRefReference_queueNext);
647    return queue != NULL && queueNext == NULL;
648}
649
650/*
651 * Schedules a reference to be appended to its reference queue.
652 */
653static void enqueueReference(Object *ref)
654{
655    assert(ref != NULL);
656    assert(dvmGetFieldObject(ref, gDvm.offJavaLangRefReference_queue) != NULL);
657    assert(dvmGetFieldObject(ref, gDvm.offJavaLangRefReference_queueNext) == NULL);
658    enqueuePendingReference(ref, &gDvm.gcHeap->clearedReferences);
659}
660
661/*
662 * Walks the reference list marking any references subject to the
663 * reference clearing policy.  References with a black referent are
664 * removed from the list.  References with white referents biased
665 * toward saving are blackened and also removed from the list.
666 */
667static void preserveSomeSoftReferences(Object **list)
668{
669    assert(list != NULL);
670    GcMarkContext *ctx = &gDvm.gcHeap->markContext;
671    size_t referentOffset = gDvm.offJavaLangRefReference_referent;
672    Object *clear = NULL;
673    size_t counter = 0;
674    while (*list != NULL) {
675        Object *ref = dequeuePendingReference(list);
676        Object *referent = dvmGetFieldObject(ref, referentOffset);
677        if (referent == NULL) {
678            /* Referent was cleared by the user during marking. */
679            continue;
680        }
681        bool marked = isMarked(referent, ctx);
682        if (!marked && ((++counter) & 1)) {
683            /* Referent is white and biased toward saving, mark it. */
684            markObject(referent, ctx);
685            marked = true;
686        }
687        if (!marked) {
688            /* Referent is white, queue it for clearing. */
689            enqueuePendingReference(ref, &clear);
690        }
691    }
692    *list = clear;
693    /*
694     * Restart the mark with the newly black references added to the
695     * root set.
696     */
697    processMarkStack(ctx);
698}
699
700/*
701 * Unlink the reference list clearing references objects with white
702 * referents.  Cleared references registered to a reference queue are
703 * scheduled for appending by the heap worker thread.
704 */
705static void clearWhiteReferences(Object **list)
706{
707    assert(list != NULL);
708    GcMarkContext *ctx = &gDvm.gcHeap->markContext;
709    size_t referentOffset = gDvm.offJavaLangRefReference_referent;
710    while (*list != NULL) {
711        Object *ref = dequeuePendingReference(list);
712        Object *referent = dvmGetFieldObject(ref, referentOffset);
713        if (referent != NULL && !isMarked(referent, ctx)) {
714            /* Referent is white, clear it. */
715            clearReference(ref);
716            if (isEnqueuable(ref)) {
717                enqueueReference(ref);
718            }
719        }
720    }
721    assert(*list == NULL);
722}
723
724/*
725 * Enqueues finalizer references with white referents.  White
726 * referents are blackened, moved to the zombie field, and the
727 * referent field is cleared.
728 */
729static void enqueueFinalizerReferences(Object **list)
730{
731    assert(list != NULL);
732    GcMarkContext *ctx = &gDvm.gcHeap->markContext;
733    size_t referentOffset = gDvm.offJavaLangRefReference_referent;
734    size_t zombieOffset = gDvm.offJavaLangRefFinalizerReference_zombie;
735    bool hasEnqueued = false;
736    while (*list != NULL) {
737        Object *ref = dequeuePendingReference(list);
738        Object *referent = dvmGetFieldObject(ref, referentOffset);
739        if (referent != NULL && !isMarked(referent, ctx)) {
740            markObject(referent, ctx);
741            /* If the referent is non-null the reference must queuable. */
742            assert(isEnqueuable(ref));
743            dvmSetFieldObject(ref, zombieOffset, referent);
744            clearReference(ref);
745            enqueueReference(ref);
746            hasEnqueued = true;
747        }
748    }
749    if (hasEnqueued) {
750        processMarkStack(ctx);
751    }
752    assert(*list == NULL);
753}
754
755/*
756 * This object is an instance of a class that overrides finalize().  Mark
757 * it as finalizable.
758 *
759 * This is called when Object.<init> completes normally.  It's also
760 * called for clones of finalizable objects.
761 */
762void dvmSetFinalizable(Object *obj)
763{
764    assert(obj != NULL);
765    Thread *self = dvmThreadSelf();
766    assert(self != NULL);
767    Method *meth = gDvm.methJavaLangRefFinalizerReferenceAdd;
768    assert(meth != NULL);
769    JValue unusedResult;
770    dvmCallMethod(self, meth, NULL, &unusedResult, obj);
771}
772
773/*
774 * Process reference class instances and schedule finalizations.
775 */
776void dvmHeapProcessReferences(Object **softReferences, bool clearSoftRefs,
777                              Object **weakReferences,
778                              Object **finalizerReferences,
779                              Object **phantomReferences)
780{
781    assert(softReferences != NULL);
782    assert(weakReferences != NULL);
783    assert(finalizerReferences != NULL);
784    assert(phantomReferences != NULL);
785    /*
786     * Unless we are in the zygote or required to clear soft
787     * references with white references, preserve some white
788     * referents.
789     */
790    if (!gDvm.zygote && !clearSoftRefs) {
791        preserveSomeSoftReferences(softReferences);
792    }
793    /*
794     * Clear all remaining soft and weak references with white
795     * referents.
796     */
797    clearWhiteReferences(softReferences);
798    clearWhiteReferences(weakReferences);
799    /*
800     * Preserve all white objects with finalize methods and schedule
801     * them for finalization.
802     */
803    enqueueFinalizerReferences(finalizerReferences);
804    /*
805     * Clear all f-reachable soft and weak references with white
806     * referents.
807     */
808    clearWhiteReferences(softReferences);
809    clearWhiteReferences(weakReferences);
810    /*
811     * Clear all phantom references with white referents.
812     */
813    clearWhiteReferences(phantomReferences);
814    /*
815     * At this point all reference lists should be empty.
816     */
817    assert(*softReferences == NULL);
818    assert(*weakReferences == NULL);
819    assert(*finalizerReferences == NULL);
820    assert(*phantomReferences == NULL);
821}
822
823/*
824 * Pushes a list of cleared references out to the managed heap.
825 */
826void dvmEnqueueClearedReferences(Object **cleared)
827{
828    assert(cleared != NULL);
829    if (*cleared != NULL) {
830        Thread *self = dvmThreadSelf();
831        assert(self != NULL);
832        Method *meth = gDvm.methJavaLangRefReferenceQueueAdd;
833        assert(meth != NULL);
834        JValue unused;
835        Object *reference = *cleared;
836        dvmCallMethod(self, meth, NULL, &unused, reference);
837        *cleared = NULL;
838    }
839}
840
841void dvmHeapFinishMarkStep()
842{
843    GcMarkContext *ctx = &gDvm.gcHeap->markContext;
844
845    /* The mark bits are now not needed.
846     */
847    dvmHeapSourceZeroMarkBitmap();
848
849    /* Clean up everything else associated with the marking process.
850     */
851    destroyMarkStack(&ctx->stack);
852
853    ctx->finger = NULL;
854}
855
856struct SweepContext {
857    size_t numObjects;
858    size_t numBytes;
859    bool isConcurrent;
860};
861
862static void sweepBitmapCallback(size_t numPtrs, void **ptrs, void *arg)
863{
864    assert(arg != NULL);
865    SweepContext *ctx = (SweepContext *)arg;
866    if (ctx->isConcurrent) {
867        dvmLockHeap();
868    }
869    ctx->numBytes += dvmHeapSourceFreeList(numPtrs, ptrs);
870    ctx->numObjects += numPtrs;
871    if (ctx->isConcurrent) {
872        dvmUnlockHeap();
873    }
874}
875
876/*
877 * Returns true if the given object is unmarked.  This assumes that
878 * the bitmaps have not yet been swapped.
879 */
880static int isUnmarkedObject(void *obj)
881{
882    return !isMarked((Object *)obj, &gDvm.gcHeap->markContext);
883}
884
885static void sweepWeakJniGlobals()
886{
887    IndirectRefTable* table = &gDvm.jniWeakGlobalRefTable;
888    GcMarkContext* ctx = &gDvm.gcHeap->markContext;
889    typedef IndirectRefTable::iterator It; // TODO: C++0x auto
890    for (It it = table->begin(), end = table->end(); it != end; ++it) {
891        Object** entry = *it;
892        if (!isMarked(*entry, ctx)) {
893            *entry = kClearedJniWeakGlobal;
894        }
895    }
896}
897
898/*
899 * Process all the internal system structures that behave like
900 * weakly-held objects.
901 */
902void dvmHeapSweepSystemWeaks()
903{
904    dvmGcDetachDeadInternedStrings(isUnmarkedObject);
905    dvmSweepMonitorList(&gDvm.monitorList, isUnmarkedObject);
906    sweepWeakJniGlobals();
907}
908
909/*
910 * Walk through the list of objects that haven't been marked and free
911 * them.  Assumes the bitmaps have been swapped.
912 */
913void dvmHeapSweepUnmarkedObjects(bool isPartial, bool isConcurrent,
914                                 size_t *numObjects, size_t *numBytes)
915{
916    uintptr_t base[HEAP_SOURCE_MAX_HEAP_COUNT];
917    uintptr_t max[HEAP_SOURCE_MAX_HEAP_COUNT];
918    SweepContext ctx;
919    HeapBitmap *prevLive, *prevMark;
920    size_t numHeaps, numSweepHeaps;
921
922    numHeaps = dvmHeapSourceGetNumHeaps();
923    dvmHeapSourceGetRegions(base, max, numHeaps);
924    if (isPartial) {
925        assert((uintptr_t)gDvm.gcHeap->markContext.immuneLimit == base[0]);
926        numSweepHeaps = 1;
927    } else {
928        numSweepHeaps = numHeaps;
929    }
930    ctx.numObjects = ctx.numBytes = 0;
931    ctx.isConcurrent = isConcurrent;
932    prevLive = dvmHeapSourceGetMarkBits();
933    prevMark = dvmHeapSourceGetLiveBits();
934    for (size_t i = 0; i < numSweepHeaps; ++i) {
935        dvmHeapBitmapSweepWalk(prevLive, prevMark, base[i], max[i],
936                               sweepBitmapCallback, &ctx);
937    }
938    *numObjects = ctx.numObjects;
939    *numBytes = ctx.numBytes;
940    if (gDvm.allocProf.enabled) {
941        gDvm.allocProf.freeCount += ctx.numObjects;
942        gDvm.allocProf.freeSize += ctx.numBytes;
943    }
944}
945