vm/alloc/MarkSweep.cpp

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