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