vm/alloc/MarkSweep.c

   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/HeapBitmap.h"
  19 #include "alloc/HeapInternal.h"
  20 #include "alloc/HeapSource.h"
  21 #include "alloc/MarkSweep.h"
  22 #include <limits.h>     // for ULONG_MAX
  23 #include <sys/mman.h>   // for madvise(), mmap()
  24 #include <cutils/ashmem.h>
  25 #include <errno.h>
  26
  27 #define GC_DEBUG_PARANOID   2
  28 #define GC_DEBUG_BASIC      1
  29 #define GC_DEBUG_OFF        0
  30 #define GC_DEBUG(l)         (GC_DEBUG_LEVEL >= (l))
  31
  32 #if 1
  33 #define GC_DEBUG_LEVEL      GC_DEBUG_PARANOID
  34 #else
  35 #define GC_DEBUG_LEVEL      GC_DEBUG_OFF
  36 #endif
  37
  38 #define VERBOSE_GC          0
  39
  40 #define GC_LOG_TAG      LOG_TAG "-gc"
  41
  42 #if LOG_NDEBUG
  43 #define LOGV_GC(...)    ((void)0)
  44 #define LOGD_GC(...)    ((void)0)
  45 #else
  46 #define LOGV_GC(...)    LOG(LOG_VERBOSE, GC_LOG_TAG, __VA_ARGS__)
  47 #define LOGD_GC(...)    LOG(LOG_DEBUG, GC_LOG_TAG, __VA_ARGS__)
  48 #endif
  49
  50 #if VERBOSE_GC
  51 #define LOGVV_GC(...)   LOGV_GC(__VA_ARGS__)
  52 #else
  53 #define LOGVV_GC(...)   ((void)0)
  54 #endif
  55
  56 #define LOGI_GC(...)    LOG(LOG_INFO, GC_LOG_TAG, __VA_ARGS__)
  57 #define LOGW_GC(...)    LOG(LOG_WARN, GC_LOG_TAG, __VA_ARGS__)
  58 #define LOGE_GC(...)    LOG(LOG_ERROR, GC_LOG_TAG, __VA_ARGS__)
  59
  60 #define LOG_SCAN(...)   LOGV_GC("SCAN: " __VA_ARGS__)
  61 #define LOG_MARK(...)   LOGV_GC("MARK: " __VA_ARGS__)
  62 #define LOG_SWEEP(...)  LOGV_GC("SWEEP: " __VA_ARGS__)
  63 #define LOG_REF(...)    LOGV_GC("REF: " __VA_ARGS__)
  64
  65 #define LOGV_SCAN(...)  LOGVV_GC("SCAN: " __VA_ARGS__)
  66 #define LOGV_MARK(...)  LOGVV_GC("MARK: " __VA_ARGS__)
  67 #define LOGV_SWEEP(...) LOGVV_GC("SWEEP: " __VA_ARGS__)
  68 #define LOGV_REF(...)   LOGVV_GC("REF: " __VA_ARGS__)
  69
  70 #if WITH_OBJECT_HEADERS
  71 u2 gGeneration = 0;
  72 static const Object *gMarkParent = NULL;
  73 #endif
  74
  75 #ifndef PAGE_SIZE
  76 #define PAGE_SIZE 4096
  77 #endif
  78 #define ALIGN_UP_TO_PAGE_SIZE(p) \
  79     (((size_t)(p) + (PAGE_SIZE - 1)) & ~(PAGE_SIZE - 1))
  80
  81 /* Do not cast the result of this to a boolean; the only set bit
  82  * may be > 1<<8.
  83  */
  84 static inline long isMarked(const DvmHeapChunk *hc, const GcMarkContext *ctx)
  85         __attribute__((always_inline));
  86 static inline long isMarked(const DvmHeapChunk *hc, const GcMarkContext *ctx)
  87 {
  88     return dvmHeapBitmapIsObjectBitSetInList(ctx->bitmaps, ctx->numBitmaps, hc);
  89 }
  90
  91 static bool
  92 createMarkStack(GcMarkStack *stack)
  93 {
  94     const Object **limit;
  95     size_t size;
  96     int fd, err;
  97
  98     /* Create a stack big enough for the worst possible case,
  99      * where the heap is perfectly full of the smallest object.
 100      * TODO: be better about memory usage; use a smaller stack with
 101      *       overflow detection and recovery.
 102      */
 103     size = dvmHeapSourceGetIdealFootprint() * sizeof(Object*) /
 104             (sizeof(Object) + HEAP_SOURCE_CHUNK_OVERHEAD);
 105     size = ALIGN_UP_TO_PAGE_SIZE(size);
 106     fd = ashmem_create_region("dalvik-heap-markstack", size);
 107     if (fd < 0) {
 108         LOGE_GC("Could not create %d-byte ashmem mark stack: %s\n",
 109             size, strerror(errno));
 110         return false;
 111     }
 112     limit = (const Object **)mmap(NULL, size, PROT_READ | PROT_WRITE,
 113             MAP_PRIVATE, fd, 0);
 114     err = errno;
 115     close(fd);
 116     if (limit == MAP_FAILED) {
 117         LOGE_GC("Could not mmap %d-byte ashmem mark stack: %s\n",
 118             size, strerror(err));
 119         return false;
 120     }
 121
 122     memset(stack, 0, sizeof(*stack));
 123     stack->limit = limit;
 124     stack->base = (const Object **)((uintptr_t)limit + size);
 125     stack->top = stack->base;
 126
 127     return true;
 128 }
 129
 130 static void
 131 destroyMarkStack(GcMarkStack *stack)
 132 {
 133     munmap((char *)stack->limit,
 134             (uintptr_t)stack->base - (uintptr_t)stack->limit);
 135     memset(stack, 0, sizeof(*stack));
 136 }
 137
 138 #define MARK_STACK_PUSH(stack, obj) \
 139     do { \
 140         *--(stack).top = (obj); \
 141     } while (false)
 142
 143 bool
 144 dvmHeapBeginMarkStep()
 145 {
 146     GcMarkContext *mc = &gDvm.gcHeap->markContext;
 147     HeapBitmap objectBitmaps[HEAP_SOURCE_MAX_HEAP_COUNT];
 148     size_t numBitmaps;
 149
 150     if (!createMarkStack(&mc->stack)) {
 151         return false;
 152     }
 153
 154     numBitmaps = dvmHeapSourceGetObjectBitmaps(objectBitmaps,
 155             HEAP_SOURCE_MAX_HEAP_COUNT);
 156     if (numBitmaps <= 0) {
 157         return false;
 158     }
 159
 160     /* Create mark bitmaps that cover the same ranges as the
 161      * current object bitmaps.
 162      */
 163     if (!dvmHeapBitmapInitListFromTemplates(mc->bitmaps, objectBitmaps,
 164             numBitmaps, "mark"))
 165     {
 166         return false;
 167     }
 168
 169     mc->numBitmaps = numBitmaps;
 170     mc->finger = NULL;
 171
 172 #if WITH_OBJECT_HEADERS
 173     gGeneration++;
 174 #endif
 175
 176     return true;
 177 }
 178
 179 static long setAndReturnMarkBit(GcMarkContext *ctx, const DvmHeapChunk *hc)
 180         __attribute__((always_inline));
 181 static long
 182 setAndReturnMarkBit(GcMarkContext *ctx, const DvmHeapChunk *hc)
 183 {
 184     return dvmHeapBitmapSetAndReturnObjectBitInList(ctx->bitmaps,
 185         ctx->numBitmaps, hc);
 186 }
 187
 188 static void _markObjectNonNullCommon(const Object *obj, GcMarkContext *ctx,
 189         bool checkFinger, bool forceStack)
 190         __attribute__((always_inline));
 191 static void
 192 _markObjectNonNullCommon(const Object *obj, GcMarkContext *ctx,
 193         bool checkFinger, bool forceStack)
 194 {
 195     DvmHeapChunk *hc;
 196
 197     assert(obj != NULL);
 198
 199 #if GC_DEBUG(GC_DEBUG_PARANOID)
 200 //TODO: make sure we're locked
 201     assert(obj != (Object *)gDvm.unlinkedJavaLangClass);
 202     assert(dvmIsValidObject(obj));
 203 #endif
 204
 205     hc = ptr2chunk(obj);
 206     if (!setAndReturnMarkBit(ctx, hc)) {
 207         /* This object was not previously marked.
 208          */
 209         if (forceStack || (checkFinger && (void *)hc < ctx->finger)) {
 210             /* This object will need to go on the mark stack.
 211              */
 212             MARK_STACK_PUSH(ctx->stack, obj);
 213         }
 214
 215 #if WITH_OBJECT_HEADERS
 216         if (hc->scanGeneration != hc->markGeneration) {
 217             LOGE("markObject(0x%08x): wasn't scanned last time\n", (uint)obj);
 218             dvmAbort();
 219         }
 220         if (hc->markGeneration == gGeneration) {
 221             LOGE("markObject(0x%08x): already marked this generation\n",
 222                     (uint)obj);
 223             dvmAbort();
 224         }
 225         hc->oldMarkGeneration = hc->markGeneration;
 226         hc->markGeneration = gGeneration;
 227         hc->markFingerOld = hc->markFinger;
 228         hc->markFinger = ctx->finger;
 229         if (gMarkParent != NULL) {
 230             hc->parentOld = hc->parent;
 231             hc->parent = gMarkParent;
 232         } else {
 233             hc->parent = (const Object *)((uintptr_t)hc->parent | 1);
 234         }
 235         hc->markCount++;
 236 #endif
 237 #if WITH_HPROF
 238         if (gDvm.gcHeap->hprofContext != NULL) {
 239             hprofMarkRootObject(gDvm.gcHeap->hprofContext, obj, 0);
 240         }
 241 #endif
 242 #if DVM_TRACK_HEAP_MARKING
 243         gDvm.gcHeap->markCount++;
 244         gDvm.gcHeap->markSize += dvmHeapSourceChunkSize((void *)hc) +
 245                 HEAP_SOURCE_CHUNK_OVERHEAD;
 246 #endif
 247
 248         /* obj->clazz can be NULL if we catch an object between
 249          * dvmMalloc() and DVM_OBJECT_INIT().  This is ok.
 250          */
 251         LOGV_MARK("0x%08x %s\n", (uint)obj,
 252                 obj->clazz == NULL ? "<null class>" : obj->clazz->name);
 253     }
 254 }
 255
 256 /* Used to mark objects when recursing.  Recursion is done by moving
 257  * the finger across the bitmaps in address order and marking child
 258  * objects.  Any newly-marked objects whose addresses are lower than
 259  * the finger won't be visited by the bitmap scan, so those objects
 260  * need to be added to the mark stack.
 261  */
 262 static void
 263 markObjectNonNull(const Object *obj, GcMarkContext *ctx)
 264 {
 265     _markObjectNonNullCommon(obj, ctx, true, false);
 266 }
 267
 268 #define markObject(obj, ctx) \
 269     do { \
 270         Object *MO_obj_ = (Object *)(obj); \
 271         if (MO_obj_ != NULL) { \
 272             markObjectNonNull(MO_obj_, (ctx)); \
 273         } \
 274     } while (false)
 275
 276 /* If the object hasn't already been marked, mark it and
 277  * schedule it to be scanned for references.
 278  *
 279  * obj may not be NULL.  The macro dvmMarkObject() should
 280  * be used in situations where a reference may be NULL.
 281  *
 282  * This function may only be called when marking the root
 283  * set.  When recursing, use the internal markObject[NonNull]().
 284  */
 285 void
 286 dvmMarkObjectNonNull(const Object *obj)
 287 {
 288     _markObjectNonNullCommon(obj, &gDvm.gcHeap->markContext, false, false);
 289 }
 290
 291 /* Mark the set of root objects.
 292  *
 293  * Things we need to scan:
 294  * - System classes defined by root classloader
 295  * - For each thread:
 296  *   - Interpreted stack, from top to "curFrame"
 297  *     - Dalvik registers (args + local vars)
 298  *   - JNI local references
 299  *   - Automatic VM local references (TrackedAlloc)
 300  *   - Associated Thread/VMThread object
 301  *   - ThreadGroups (could track & start with these instead of working
 302  *     upward from Threads)
 303  *   - Exception currently being thrown, if present
 304  * - JNI global references
 305  * - Interned string table
 306  * - Primitive classes
 307  * - Special objects
 308  *   - gDvm.outOfMemoryObj
 309  * - Objects allocated with ALLOC_NO_GC
 310  * - Objects pending finalization (but not yet finalized)
 311  * - Objects in debugger object registry
 312  *
 313  * Don't need:
 314  * - Native stack (for in-progress stuff in the VM)
 315  *   - The TrackedAlloc stuff watches all native VM references.
 316  */
 317 void dvmHeapMarkRootSet()
 318 {
 319     HeapRefTable *refs;
 320     GcHeap *gcHeap;
 321     Object **op;
 322
 323     gcHeap = gDvm.gcHeap;
 324
 325     HPROF_SET_GC_SCAN_STATE(HPROF_ROOT_STICKY_CLASS, 0);
 326
 327     LOG_SCAN("root class loader\n");
 328     dvmGcScanRootClassLoader();
 329     LOG_SCAN("primitive classes\n");
 330     dvmGcScanPrimitiveClasses();
 331
 332     /* dvmGcScanRootThreadGroups() sets a bunch of
 333      * different scan states internally.
 334      */
 335     HPROF_CLEAR_GC_SCAN_STATE();
 336
 337     LOG_SCAN("root thread groups\n");
 338     dvmGcScanRootThreadGroups();
 339
 340     HPROF_SET_GC_SCAN_STATE(HPROF_ROOT_INTERNED_STRING, 0);
 341
 342     LOG_SCAN("interned strings\n");
 343     dvmGcScanInternedStrings();
 344
 345     HPROF_SET_GC_SCAN_STATE(HPROF_ROOT_JNI_GLOBAL, 0);
 346
 347     LOG_SCAN("JNI global refs\n");
 348     dvmGcMarkJniGlobalRefs();
 349
 350     HPROF_SET_GC_SCAN_STATE(HPROF_ROOT_REFERENCE_CLEANUP, 0);
 351
 352     LOG_SCAN("pending reference operations\n");
 353     dvmHeapMarkLargeTableRefs(gcHeap->referenceOperations, true);
 354
 355     HPROF_SET_GC_SCAN_STATE(HPROF_ROOT_FINALIZING, 0);
 356
 357     LOG_SCAN("pending finalizations\n");
 358     dvmHeapMarkLargeTableRefs(gcHeap->pendingFinalizationRefs, false);
 359
 360     HPROF_SET_GC_SCAN_STATE(HPROF_ROOT_DEBUGGER, 0);
 361
 362     LOG_SCAN("debugger refs\n");
 363     dvmGcMarkDebuggerRefs();
 364
 365     HPROF_SET_GC_SCAN_STATE(HPROF_ROOT_VM_INTERNAL, 0);
 366
 367     /* Mark all ALLOC_NO_GC objects.
 368      */
 369     LOG_SCAN("ALLOC_NO_GC objects\n");
 370     refs = &gcHeap->nonCollectableRefs;
 371     op = refs->table;
 372     while ((uintptr_t)op < (uintptr_t)refs->nextEntry) {
 373         dvmMarkObjectNonNull(*(op++));
 374     }
 375
 376     /* Mark any special objects we have sitting around.
 377      */
 378     LOG_SCAN("special objects\n");
 379     dvmMarkObjectNonNull(gDvm.outOfMemoryObj);
 380     dvmMarkObjectNonNull(gDvm.internalErrorObj);
 381 //TODO: scan object references sitting in gDvm;  use pointer begin & end
 382
 383     HPROF_CLEAR_GC_SCAN_STATE();
 384 }
 385
 386 /*
 387  * Nothing past this point is allowed to use dvmMarkObject*().
 388  * Scanning/recursion must use markObject*(), which takes the
 389  * finger into account.
 390  */
 391 #define dvmMarkObjectNonNull __dont_use_dvmMarkObjectNonNull__
 392
 393
 394 /* Mark all of a ClassObject's interfaces.
 395  */
 396 static void markInterfaces(const ClassObject *clazz, GcMarkContext *ctx)
 397 {
 398     ClassObject **interfaces;
 399     int interfaceCount;
 400     int i;
 401
 402     /* Mark all interfaces.
 403      */
 404     interfaces = clazz->interfaces;
 405     interfaceCount = clazz->interfaceCount;
 406     for (i = 0; i < interfaceCount; i++) {
 407         markObjectNonNull((Object *)*interfaces, ctx);
 408         interfaces++;
 409     }
 410 }
 411
 412 /* Mark all objects referred to by a ClassObject's static fields.
 413  */
 414 static void scanStaticFields(const ClassObject *clazz, GcMarkContext *ctx)
 415 {
 416     StaticField *f;
 417     int i;
 418
 419     //TODO: Optimize this with a bit vector or something
 420     f = clazz->sfields;
 421     for (i = 0; i < clazz->sfieldCount; i++) {
 422         char c = f->field.signature[0];
 423         if (c == '[' || c == 'L') {
 424             /* It's an array or class reference.
 425              */
 426             markObject((Object *)f->value.l, ctx);
 427         }
 428         f++;
 429     }
 430 }
 431
 432 /* Mark all objects referred to by a DataObject's instance fields.
 433  */
 434 static void scanInstanceFields(const DataObject *obj, ClassObject *clazz,
 435         GcMarkContext *ctx)
 436 {
 437 //TODO: Optimize this by avoiding walking the superclass chain
 438     while (clazz != NULL) {
 439         InstField *f;
 440         int i;
 441
 442         /* All of the fields that contain object references
 443          * are guaranteed to be at the beginning of the ifields list.
 444          */
 445         f = clazz->ifields;
 446         for (i = 0; i < clazz->ifieldRefCount; i++) {
 447             /* Mark the array or object reference.
 448              * May be NULL.
 449              *
 450              * Note that, per the comment on struct InstField,
 451              * f->byteOffset is the offset from the beginning of
 452              * obj, not the offset into obj->instanceData.
 453              */
 454             markObject(dvmGetFieldObject((Object*)obj, f->byteOffset), ctx);
 455             f++;
 456         }
 457
 458         /* This will be NULL when we hit java.lang.Object
 459          */
 460         clazz = clazz->super;
 461     }
 462 }
 463
 464 /* Mark all objects referred to by the array's contents.
 465  */
 466 static void scanObjectArray(const ArrayObject *array, GcMarkContext *ctx)
 467 {
 468     Object **contents;
 469     u4 length;
 470     u4 i;
 471
 472     contents = (Object **)array->contents;
 473     length = array->length;
 474
 475     for (i = 0; i < length; i++) {
 476         markObject(*contents, ctx); // may be NULL
 477         contents++;
 478     }
 479 }
 480
 481 /* Mark all objects referred to by the ClassObject.
 482  */
 483 static void scanClassObject(const ClassObject *clazz, GcMarkContext *ctx)
 484 {
 485     LOGV_SCAN("---------> %s\n", clazz->name);
 486
 487     if (IS_CLASS_FLAG_SET(clazz, CLASS_ISARRAY)) {
 488         /* We're an array; mark the class object of the contents
 489          * of the array.
 490          *
 491          * Note that we won't necessarily reach the array's element
 492          * class by scanning the array contents;  the array may be
 493          * zero-length, or may only contain null objects.
 494          */
 495         markObjectNonNull((Object *)clazz->elementClass, ctx);
 496     }
 497
 498     /* We scan these explicitly in case the only remaining
 499      * reference to a particular class object is via a data
 500      * object;  we may not be guaranteed to reach all
 501      * live class objects via a classloader.
 502      */
 503     markObject((Object *)clazz->super, ctx);  // may be NULL (java.lang.Object)
 504     markObject(clazz->classLoader, ctx);      // may be NULL
 505
 506     scanStaticFields(clazz, ctx);
 507     markInterfaces(clazz, ctx);
 508 }
 509
 510 /* Mark all objects that obj refers to.
 511  *
 512  * Called on every object in markList.
 513  */
 514 static void scanObject(const Object *obj, GcMarkContext *ctx)
 515 {
 516     ClassObject *clazz;
 517
 518     assert(dvmIsValidObject(obj));
 519     LOGV_SCAN("0x%08x %s\n", (uint)obj, obj->clazz->name);
 520
 521 #if WITH_HPROF
 522     if (gDvm.gcHeap->hprofContext != NULL) {
 523         hprofDumpHeapObject(gDvm.gcHeap->hprofContext, obj);
 524     }
 525 #endif
 526
 527     /* Get and mark the class object for this particular instance.
 528      */
 529     clazz = obj->clazz;
 530     if (clazz == NULL) {
 531         /* This can happen if we catch an object between
 532          * dvmMalloc() and DVM_OBJECT_INIT().  The object
 533          * won't contain any references yet, so we can
 534          * just skip it.
 535          */
 536         return;
 537     } else if (clazz == gDvm.unlinkedJavaLangClass) {
 538         /* This class hasn't been linked yet.  We're guaranteed
 539          * that the object doesn't contain any references that
 540          * aren't already tracked, so we can skip scanning it.
 541          *
 542          * NOTE: unlinkedJavaLangClass is not on the heap, so
 543          * it's very important that we don't try marking it.
 544          */
 545         return;
 546     }
 547 #if WITH_OBJECT_HEADERS
 548     gMarkParent = obj;
 549     if (ptr2chunk(obj)->scanGeneration == gGeneration) {
 550         LOGE("object 0x%08x was already scanned this generation\n",
 551                 (uintptr_t)obj);
 552         dvmAbort();
 553     }
 554     ptr2chunk(obj)->oldScanGeneration = ptr2chunk(obj)->scanGeneration;
 555     ptr2chunk(obj)->scanGeneration = gGeneration;
 556     ptr2chunk(obj)->scanCount++;
 557 #endif
 558
 559     assert(dvmIsValidObject((Object *)clazz));
 560     markObjectNonNull((Object *)clazz, ctx);
 561
 562     /* Mark any references in this object.
 563      */
 564     if (IS_CLASS_FLAG_SET(clazz, CLASS_ISARRAY)) {
 565         /* It's an array object.
 566          */
 567         if (IS_CLASS_FLAG_SET(clazz, CLASS_ISOBJECTARRAY)) {
 568             /* It's an array of object references.
 569              */
 570             scanObjectArray((ArrayObject *)obj, ctx);
 571         }
 572         // else there's nothing else to scan
 573     } else {
 574         /* It's a DataObject-compatible object.
 575          */
 576         scanInstanceFields((DataObject *)obj, clazz, ctx);
 577
 578         if (IS_CLASS_FLAG_SET(clazz, CLASS_ISREFERENCE)) {
 579             GcHeap *gcHeap = gDvm.gcHeap;
 580             Object *referent;
 581
 582             /* It's a subclass of java/lang/ref/Reference.
 583              * The fields in this class have been arranged
 584              * such that scanInstanceFields() did not actually
 585              * mark the "referent" field;  we need to handle
 586              * it specially.
 587              *
 588              * If the referent already has a strong mark (isMarked(referent)),
 589              * we don't care about its reference status.
 590              */
 591             referent = dvmGetFieldObject(obj,
 592                     gDvm.offJavaLangRefReference_referent);
 593             if (referent != NULL &&
 594                     !isMarked(ptr2chunk(referent), &gcHeap->markContext))
 595             {
 596                 u4 refFlags;
 597
 598                 if (gcHeap->markAllReferents) {
 599                     LOG_REF("Hard-marking a reference\n");
 600
 601                     /* Don't bother with normal reference-following
 602                      * behavior, just mark the referent.  This should
 603                      * only be used when following objects that just
 604                      * became scheduled for finalization.
 605                      */
 606                     markObjectNonNull(referent, ctx);
 607                     goto skip_reference;
 608                 }
 609
 610                 /* See if this reference was handled by a previous GC.
 611                  */
 612                 if (dvmGetFieldObject(obj,
 613                             gDvm.offJavaLangRefReference_vmData) ==
 614                         SCHEDULED_REFERENCE_MAGIC)
 615                 {
 616                     LOG_REF("Skipping scheduled reference\n");
 617
 618                     /* Don't reschedule it, but make sure that its
 619                      * referent doesn't get collected (in case it's
 620                      * a PhantomReference and wasn't cleared automatically).
 621                      */
 622                     //TODO: Mark these after handling all new refs of
 623                     //      this strength, in case the new refs refer
 624                     //      to the same referent.  Not a very common
 625                     //      case, though.
 626                     markObjectNonNull(referent, ctx);
 627                     goto skip_reference;
 628                 }
 629
 630                 /* Find out what kind of reference is pointing
 631                  * to referent.
 632                  */
 633                 refFlags = GET_CLASS_FLAG_GROUP(clazz,
 634                     CLASS_ISREFERENCE |
 635                     CLASS_ISWEAKREFERENCE |
 636                     CLASS_ISPHANTOMREFERENCE);
 637
 638             /* We use the vmData field of Reference objects
 639              * as a next pointer in a singly-linked list.
 640              * That way, we don't need to allocate any memory
 641              * while we're doing a GC.
 642              */
 643 #define ADD_REF_TO_LIST(list, ref) \
 644             do { \
 645                 Object *ARTL_ref_ = (/*de-const*/Object *)(ref); \
 646                 dvmSetFieldObject(ARTL_ref_, \
 647                         gDvm.offJavaLangRefReference_vmData, list); \
 648                 list = ARTL_ref_; \
 649             } while (false)
 650
 651                 /* At this stage, we just keep track of all of
 652                  * the live references that we've seen.  Later,
 653                  * we'll walk through each of these lists and
 654                  * deal with the referents.
 655                  */
 656                 if (refFlags == CLASS_ISREFERENCE) {
 657                     /* It's a soft reference.  Depending on the state,
 658                      * we'll attempt to collect all of them, some of
 659                      * them, or none of them.
 660                      */
 661                     if (gcHeap->softReferenceCollectionState ==
 662                             SR_COLLECT_NONE)
 663                     {
 664                 sr_collect_none:
 665                         markObjectNonNull(referent, ctx);
 666                     } else if (gcHeap->softReferenceCollectionState ==
 667                             SR_COLLECT_ALL)
 668                     {
 669                 sr_collect_all:
 670                         ADD_REF_TO_LIST(gcHeap->softReferences, obj);
 671                     } else {
 672                         /* We'll only try to collect half of the
 673                          * referents.
 674                          */
 675                         if (gcHeap->softReferenceColor++ & 1) {
 676                             goto sr_collect_none;
 677                         }
 678                         goto sr_collect_all;
 679                     }
 680                 } else {
 681                     /* It's a weak or phantom reference.
 682                      * Clearing CLASS_ISREFERENCE will reveal which.
 683                      */
 684                     refFlags &= ~CLASS_ISREFERENCE;
 685                     if (refFlags == CLASS_ISWEAKREFERENCE) {
 686                         ADD_REF_TO_LIST(gcHeap->weakReferences, obj);
 687                     } else if (refFlags == CLASS_ISPHANTOMREFERENCE) {
 688                         ADD_REF_TO_LIST(gcHeap->phantomReferences, obj);
 689                     } else {
 690                         assert(!"Unknown reference type");
 691                     }
 692                 }
 693 #undef ADD_REF_TO_LIST
 694             }
 695         }
 696
 697     skip_reference:
 698         /* If this is a class object, mark various other things that
 699          * its internals point to.
 700          *
 701          * All class objects are instances of java.lang.Class,
 702          * including the java.lang.Class class object.
 703          */
 704         if (clazz == gDvm.classJavaLangClass) {
 705             scanClassObject((ClassObject *)obj, ctx);
 706         }
 707     }
 708
 709 #if WITH_OBJECT_HEADERS
 710     gMarkParent = NULL;
 711 #endif
 712 }
 713
 714 static void
 715 processMarkStack(GcMarkContext *ctx)
 716 {
 717     const Object **const base = ctx->stack.base;
 718
 719     /* Scan anything that's on the mark stack.
 720      * We can't use the bitmaps anymore, so use
 721      * a finger that points past the end of them.
 722      */
 723     ctx->finger = (void *)ULONG_MAX;
 724     while (ctx->stack.top != base) {
 725         scanObject(*ctx->stack.top++, ctx);
 726     }
 727 }
 728
 729 #ifndef NDEBUG
 730 static uintptr_t gLastFinger = 0;
 731 #endif
 732
 733 static bool
 734 scanBitmapCallback(size_t numPtrs, void **ptrs, const void *finger, void *arg)
 735 {
 736     GcMarkContext *ctx = (GcMarkContext *)arg;
 737     size_t i;
 738
 739 #ifndef NDEBUG
 740     assert((uintptr_t)finger >= gLastFinger);
 741     gLastFinger = (uintptr_t)finger;
 742 #endif
 743
 744     ctx->finger = finger;
 745     for (i = 0; i < numPtrs; i++) {
 746         /* The pointers we're getting back are DvmHeapChunks,
 747          * not Objects.
 748          */
 749         scanObject(chunk2ptr(*ptrs++), ctx);
 750     }
 751
 752     return true;
 753 }
 754
 755 /* Given bitmaps with the root set marked, find and mark all
 756  * reachable objects.  When this returns, the entire set of
 757  * live objects will be marked and the mark stack will be empty.
 758  */
 759 void dvmHeapScanMarkedObjects()
 760 {
 761     GcMarkContext *ctx = &gDvm.gcHeap->markContext;
 762
 763     assert(ctx->finger == NULL);
 764
 765     /* The bitmaps currently have bits set for the root set.
 766      * Walk across the bitmaps and scan each object.
 767      */
 768 #ifndef NDEBUG
 769     gLastFinger = 0;
 770 #endif
 771     dvmHeapBitmapWalkList(ctx->bitmaps, ctx->numBitmaps,
 772             scanBitmapCallback, ctx);
 773
 774     /* We've walked the mark bitmaps.  Scan anything that's
 775      * left on the mark stack.
 776      */
 777     processMarkStack(ctx);
 778
 779     LOG_SCAN("done with marked objects\n");
 780 }
 781
 782 /** @return true if we need to schedule a call to clear().
 783  */
 784 static bool clearReference(Object *reference)
 785 {
 786     /* This is what the default implementation of Reference.clear()
 787      * does.  We're required to clear all references to a given
 788      * referent atomically, so we can't pop in and out of interp
 789      * code each time.
 790      *
 791      * Also, someone may have subclassed one of the basic Reference
 792      * types, overriding clear().  We can't trust the clear()
 793      * implementation to call super.clear();  we cannot let clear()
 794      * resurrect the referent.  If we clear it here, we can safely
 795      * call any overriding implementations.
 796      */
 797     dvmSetFieldObject(reference,
 798             gDvm.offJavaLangRefReference_referent, NULL);
 799
 800 #if FANCY_REFERENCE_SUBCLASS
 801     /* See if clear() has actually been overridden.  If so,
 802      * we need to schedule a call to it before calling enqueue().
 803      */
 804     if (reference->clazz->vtable[gDvm.voffJavaLangRefReference_clear]->clazz !=
 805             gDvm.classJavaLangRefReference)
 806     {
 807         /* clear() has been overridden;  return true to indicate
 808          * that we need to schedule a call to the real clear()
 809          * implementation.
 810          */
 811         return true;
 812     }
 813 #endif
 814
 815     return false;
 816 }
 817
 818 /** @return true if we need to schedule a call to enqueue().
 819  */
 820 static bool enqueueReference(Object *reference)
 821 {
 822 #if FANCY_REFERENCE_SUBCLASS
 823     /* See if this reference class has overridden enqueue();
 824      * if not, we can take a shortcut.
 825      */
 826     if (reference->clazz->vtable[gDvm.voffJavaLangRefReference_enqueue]->clazz
 827             == gDvm.classJavaLangRefReference)
 828 #endif
 829     {
 830         Object *queue = dvmGetFieldObject(reference,
 831                 gDvm.offJavaLangRefReference_queue);
 832         Object *queueNext = dvmGetFieldObject(reference,
 833                 gDvm.offJavaLangRefReference_queueNext);
 834         if (queue == NULL || queueNext != NULL) {
 835             /* There is no queue, or the reference has already
 836              * been enqueued.  The Reference.enqueue() method
 837              * will do nothing even if we call it.
 838              */
 839             return false;
 840         }
 841     }
 842
 843     /* We need to call enqueue(), but if we called it from
 844      * here we'd probably deadlock.  Schedule a call.
 845      */
 846     return true;
 847 }
 848
 849 /* All objects for stronger reference levels have been
 850  * marked before this is called.
 851  */
 852 void dvmHeapHandleReferences(Object *refListHead, enum RefType refType)
 853 {
 854     Object *reference;
 855     GcMarkContext *markContext = &gDvm.gcHeap->markContext;
 856     const int offVmData = gDvm.offJavaLangRefReference_vmData;
 857     const int offReferent = gDvm.offJavaLangRefReference_referent;
 858     bool workRequired = false;
 859
 860 size_t numCleared = 0;
 861 size_t numEnqueued = 0;
 862     reference = refListHead;
 863     while (reference != NULL) {
 864         Object *next;
 865         Object *referent;
 866
 867         /* Pull the interesting fields out of the Reference object.
 868          */
 869         next = dvmGetFieldObject(reference, offVmData);
 870         referent = dvmGetFieldObject(reference, offReferent);
 871
 872         //TODO: when handling REF_PHANTOM, unlink any references
 873         //      that fail this initial if().  We need to re-walk
 874         //      the list, and it would be nice to avoid the extra
 875         //      work.
 876         if (referent != NULL && !isMarked(ptr2chunk(referent), markContext)) {
 877             bool schedClear, schedEnqueue;
 878
 879             /* This is the strongest reference that refers to referent.
 880              * Do the right thing.
 881              */
 882             switch (refType) {
 883             case REF_SOFT:
 884             case REF_WEAK:
 885                 schedClear = clearReference(reference);
 886                 schedEnqueue = enqueueReference(reference);
 887                 break;
 888             case REF_PHANTOM:
 889                 /* PhantomReferences are not cleared automatically.
 890                  * Until someone clears it (or the reference itself
 891                  * is collected), the referent must remain alive.
 892                  *
 893                  * It's necessary to fully mark the referent because
 894                  * it will still be present during the next GC, and
 895                  * all objects that it points to must be valid.
 896                  * (The referent will be marked outside of this loop,
 897                  * after handing all references of this strength, in
 898                  * case multiple references point to the same object.)
 899                  */
 900                 schedClear = false;
 901
 902                 /* A PhantomReference is only useful with a
 903                  * queue, but since it's possible to create one
 904                  * without a queue, we need to check.
 905                  */
 906                 schedEnqueue = enqueueReference(reference);
 907                 break;
 908             default:
 909                 assert(!"Bad reference type");
 910                 schedClear = false;
 911                 schedEnqueue = false;
 912                 break;
 913             }
 914 numCleared += schedClear ? 1 : 0;
 915 numEnqueued += schedEnqueue ? 1 : 0;
 916
 917             if (schedClear || schedEnqueue) {
 918                 uintptr_t workBits;
 919
 920                 /* Stuff the clear/enqueue bits in the bottom of
 921                  * the pointer.  Assumes that objects are 8-byte
 922                  * aligned.
 923                  *
 924                  * Note that we are adding the *Reference* (which
 925                  * is by definition already marked at this point) to
 926                  * this list; we're not adding the referent (which
 927                  * has already been cleared).
 928                  */
 929                 assert(((intptr_t)reference & 3) == 0);
 930                 assert(((WORKER_CLEAR | WORKER_ENQUEUE) & ~3) == 0);
 931                 workBits = (schedClear ? WORKER_CLEAR : 0) |
 932                            (schedEnqueue ? WORKER_ENQUEUE : 0);
 933                 if (!dvmHeapAddRefToLargeTable(
 934                         &gDvm.gcHeap->referenceOperations,
 935                         (Object *)((uintptr_t)reference | workBits)))
 936                 {
 937                     LOGE_HEAP("dvmMalloc(): no room for any more "
 938                             "reference operations\n");
 939                     dvmAbort();
 940                 }
 941                 workRequired = true;
 942             }
 943
 944             if (refType != REF_PHANTOM) {
 945                 /* Let later GCs know not to reschedule this reference.
 946                  */
 947                 dvmSetFieldObject(reference, offVmData,
 948                         SCHEDULED_REFERENCE_MAGIC);
 949             } // else this is handled later for REF_PHANTOM
 950
 951         } // else there was a stronger reference to the referent.
 952
 953         reference = next;
 954     }
 955 #define refType2str(r) \
 956     ((r) == REF_SOFT ? "soft" : ( \
 957      (r) == REF_WEAK ? "weak" : ( \
 958      (r) == REF_PHANTOM ? "phantom" : "UNKNOWN" )))
 959 LOGD_HEAP("dvmHeapHandleReferences(): cleared %zd, enqueued %zd %s references\n", numCleared, numEnqueued, refType2str(refType));
 960
 961     /* Walk though the reference list again, and mark any non-clear/marked
 962      * referents.  Only PhantomReferences can have non-clear referents
 963      * at this point.
 964      */
 965     if (refType == REF_PHANTOM) {
 966         bool scanRequired = false;
 967
 968         HPROF_SET_GC_SCAN_STATE(HPROF_ROOT_REFERENCE_CLEANUP, 0);
 969         reference = refListHead;
 970         while (reference != NULL) {
 971             Object *next;
 972             Object *referent;
 973
 974             /* Pull the interesting fields out of the Reference object.
 975              */
 976             next = dvmGetFieldObject(reference, offVmData);
 977             referent = dvmGetFieldObject(reference, offReferent);
 978
 979             if (referent != NULL && !isMarked(ptr2chunk(referent), markContext)) {
 980                 markObjectNonNull(referent, markContext);
 981                 scanRequired = true;
 982
 983                 /* Let later GCs know not to reschedule this reference.
 984                  */
 985                 dvmSetFieldObject(reference, offVmData,
 986                         SCHEDULED_REFERENCE_MAGIC);
 987             }
 988
 989             reference = next;
 990         }
 991         HPROF_CLEAR_GC_SCAN_STATE();
 992
 993         if (scanRequired) {
 994             processMarkStack(markContext);
 995         }
 996     }
 997
 998     if (workRequired) {
 999         dvmSignalHeapWorker(false);
1000     }
1001 }
1002
1003
1004 /* Find unreachable objects that need to be finalized,
1005  * and schedule them for finalization.
1006  */
1007 void dvmHeapScheduleFinalizations()
1008 {
1009     HeapRefTable newPendingRefs;
1010     LargeHeapRefTable *finRefs = gDvm.gcHeap->finalizableRefs;
1011     Object **ref;
1012     Object **lastRef;
1013     size_t totalPendCount;
1014     GcMarkContext *markContext = &gDvm.gcHeap->markContext;
1015
1016     /*
1017      * All reachable objects have been marked.
1018      * Any unmarked finalizable objects need to be finalized.
1019      */
1020
1021     /* Create a table that the new pending refs will
1022      * be added to.
1023      */
1024     if (!dvmHeapInitHeapRefTable(&newPendingRefs, 128)) {
1025         //TODO: mark all finalizable refs and hope that
1026         //      we can schedule them next time.  Watch out,
1027         //      because we may be expecting to free up space
1028         //      by calling finalizers.
1029         LOGE_GC("dvmHeapScheduleFinalizations(): no room for "
1030                 "pending finalizations\n");
1031         dvmAbort();
1032     }
1033
1034     /* Walk through finalizableRefs and move any unmarked references
1035      * to the list of new pending refs.
1036      */
1037     totalPendCount = 0;
1038     while (finRefs != NULL) {
1039         Object **gapRef;
1040         size_t newPendCount = 0;
1041
1042         gapRef = ref = finRefs->refs.table;
1043         lastRef = finRefs->refs.nextEntry;
1044         while (ref < lastRef) {
1045             DvmHeapChunk *hc;
1046
1047             hc = ptr2chunk(*ref);
1048             if (!isMarked(hc, markContext)) {
1049                 if (!dvmHeapAddToHeapRefTable(&newPendingRefs, *ref)) {
1050                     //TODO: add the current table and allocate
1051                     //      a new, smaller one.
1052                     LOGE_GC("dvmHeapScheduleFinalizations(): "
1053                             "no room for any more pending finalizations: %zd\n",
1054                             dvmHeapNumHeapRefTableEntries(&newPendingRefs));
1055                     dvmAbort();
1056                 }
1057                 newPendCount++;
1058             } else {
1059                 /* This ref is marked, so will remain on finalizableRefs.
1060                  */
1061                 if (newPendCount > 0) {
1062                     /* Copy it up to fill the holes.
1063                      */
1064                     *gapRef++ = *ref;
1065                 } else {
1066                     /* No holes yet; don't bother copying.
1067                      */
1068                     gapRef++;
1069                 }
1070             }
1071             ref++;
1072         }
1073         finRefs->refs.nextEntry = gapRef;
1074         //TODO: if the table is empty when we're done, free it.
1075         totalPendCount += newPendCount;
1076         finRefs = finRefs->next;
1077     }
1078     LOGD_GC("dvmHeapScheduleFinalizations(): %zd finalizers triggered.\n",
1079             totalPendCount);
1080     if (totalPendCount == 0) {
1081         /* No objects required finalization.
1082          * Free the empty temporary table.
1083          */
1084         dvmClearReferenceTable(&newPendingRefs);
1085         return;
1086     }
1087
1088     /* Add the new pending refs to the main list.
1089      */
1090     if (!dvmHeapAddTableToLargeTable(&gDvm.gcHeap->pendingFinalizationRefs,
1091                 &newPendingRefs))
1092     {
1093         LOGE_GC("dvmHeapScheduleFinalizations(): can't insert new "
1094                 "pending finalizations\n");
1095         dvmAbort();
1096     }
1097
1098     //TODO: try compacting the main list with a memcpy loop
1099
1100     /* Mark the refs we just moved;  we don't want them or their
1101      * children to get swept yet.
1102      */
1103     ref = newPendingRefs.table;
1104     lastRef = newPendingRefs.nextEntry;
1105     assert(ref < lastRef);
1106     HPROF_SET_GC_SCAN_STATE(HPROF_ROOT_FINALIZING, 0);
1107     while (ref < lastRef) {
1108         markObjectNonNull(*ref, markContext);
1109         ref++;
1110     }
1111     HPROF_CLEAR_GC_SCAN_STATE();
1112
1113     /* Set markAllReferents so that we don't collect referents whose
1114      * only references are in final-reachable objects.
1115      * TODO: eventually provide normal reference behavior by properly
1116      *       marking these references.
1117      */
1118     gDvm.gcHeap->markAllReferents = true;
1119     processMarkStack(markContext);
1120     gDvm.gcHeap->markAllReferents = false;
1121
1122     dvmSignalHeapWorker(false);
1123 }
1124
1125 void dvmHeapFinishMarkStep()
1126 {
1127     HeapBitmap *markBitmap;
1128     HeapBitmap objectBitmap;
1129     GcMarkContext *markContext;
1130
1131     markContext = &gDvm.gcHeap->markContext;
1132
1133     /* The sweep step freed every object that appeared in the
1134      * HeapSource bitmaps that didn't appear in the mark bitmaps.
1135      * The new state of the HeapSource is exactly the final
1136      * mark bitmaps, so swap them in.
1137      *
1138      * The old bitmaps will be swapped into the context so that
1139      * we can clean them up.
1140      */
1141     dvmHeapSourceReplaceObjectBitmaps(markContext->bitmaps,
1142             markContext->numBitmaps);
1143
1144     /* Clean up the old HeapSource bitmaps and anything else associated
1145      * with the marking process.
1146      */
1147     dvmHeapBitmapDeleteList(markContext->bitmaps, markContext->numBitmaps);
1148     destroyMarkStack(&markContext->stack);
1149
1150     memset(markContext, 0, sizeof(*markContext));
1151 }
1152
1153 #if WITH_HPROF && WITH_HPROF_UNREACHABLE
1154 static bool
1155 hprofUnreachableBitmapCallback(size_t numPtrs, void **ptrs,
1156         const void *finger, void *arg)
1157 {
1158     hprof_context_t *hctx = (hprof_context_t *)arg;
1159     size_t i;
1160
1161     for (i = 0; i < numPtrs; i++) {
1162         Object *obj;
1163
1164         /* The pointers we're getting back are DvmHeapChunks, not
1165          * Objects.
1166          */
1167         obj = (Object *)chunk2ptr(*ptrs++);
1168
1169         hprofMarkRootObject(hctx, obj, 0);
1170         hprofDumpHeapObject(hctx, obj);
1171     }
1172
1173     return true;
1174 }
1175
1176 static void
1177 hprofDumpUnmarkedObjects(const HeapBitmap markBitmaps[],
1178         const HeapBitmap objectBitmaps[], size_t numBitmaps)
1179 {
1180     hprof_context_t *hctx = gDvm.gcHeap->hprofContext;
1181     if (hctx == NULL) {
1182         return;
1183     }
1184
1185     LOGI("hprof: dumping unreachable objects\n");
1186
1187     HPROF_SET_GC_SCAN_STATE(HPROF_UNREACHABLE, 0);
1188
1189     dvmHeapBitmapXorWalkLists(markBitmaps, objectBitmaps, numBitmaps,
1190             hprofUnreachableBitmapCallback, hctx);
1191
1192     HPROF_CLEAR_GC_SCAN_STATE();
1193 }
1194 #endif
1195
1196 static bool
1197 sweepBitmapCallback(size_t numPtrs, void **ptrs, const void *finger, void *arg)
1198 {
1199     const ClassObject *const classJavaLangClass = gDvm.classJavaLangClass;
1200     size_t i;
1201
1202     for (i = 0; i < numPtrs; i++) {
1203         DvmHeapChunk *hc;
1204         Object *obj;
1205
1206         /* The pointers we're getting back are DvmHeapChunks, not
1207          * Objects.
1208          */
1209         hc = (DvmHeapChunk *)*ptrs++;
1210         obj = (Object *)chunk2ptr(hc);
1211
1212 #if WITH_OBJECT_HEADERS
1213         if (hc->markGeneration == gGeneration) {
1214             LOGE("sweeping marked object: 0x%08x\n", (uint)obj);
1215             dvmAbort();
1216         }
1217 #endif
1218
1219         /* Free the monitor associated with the object.
1220          */
1221         dvmFreeObjectMonitor(obj);
1222
1223         /* NOTE: Dereferencing clazz is dangerous.  If obj was the last
1224          * one to reference its class object, the class object could be
1225          * on the sweep list, and could already have been swept, leaving
1226          * us with a stale pointer.
1227          */
1228         LOGV_SWEEP("FREE: 0x%08x %s\n", (uint)obj, obj->clazz->name);
1229
1230         /* This assumes that java.lang.Class will never go away.
1231          * If it can, and we were the last reference to it, it
1232          * could have already been swept.  However, even in that case,
1233          * gDvm.classJavaLangClass should still have a useful
1234          * value.
1235          */
1236         if (obj->clazz == classJavaLangClass) {
1237             LOGV_SWEEP("---------------> %s\n", ((ClassObject *)obj)->name);
1238             /* dvmFreeClassInnards() may have already been called,
1239              * but it's safe to call on the same ClassObject twice.
1240              */
1241             dvmFreeClassInnards((ClassObject *)obj);
1242         }
1243
1244 #if 0
1245         /* Overwrite the to-be-freed object to make stale references
1246          * more obvious.
1247          */
1248         {
1249             int chunklen;
1250             ClassObject *clazz = obj->clazz;
1251 #if WITH_OBJECT_HEADERS
1252             DvmHeapChunk chunk = *hc;
1253             chunk.header = ~OBJECT_HEADER | 1;
1254 #endif
1255             chunklen = dvmHeapSourceChunkSize(hc);
1256             memset(hc, 0xa5, chunklen);
1257             obj->clazz = (ClassObject *)((uintptr_t)clazz ^ 0xffffffff);
1258 #if WITH_OBJECT_HEADERS
1259             *hc = chunk;
1260 #endif
1261         }
1262 #endif
1263
1264 //TODO: provide a heapsource function that takes a list of pointers to free
1265 //      and call it outside of this loop.
1266         dvmHeapSourceFree(hc);
1267     }
1268
1269     return true;
1270 }
1271
1272 /* A function suitable for passing to dvmHashForeachRemove()
1273  * to clear out any unmarked objects.  Clears the low bits
1274  * of the pointer because the intern table may set them.
1275  */
1276 static int isUnmarkedObject(void *object)
1277 {
1278     return !isMarked(ptr2chunk((uintptr_t)object & ~(HB_OBJECT_ALIGNMENT-1)),
1279             &gDvm.gcHeap->markContext);
1280 }
1281
1282 /* Walk through the list of objects that haven't been
1283  * marked and free them.
1284  */
1285 void
1286 dvmHeapSweepUnmarkedObjects(int *numFreed, size_t *sizeFreed)
1287 {
1288     const HeapBitmap *markBitmaps;
1289     const GcMarkContext *markContext;
1290     HeapBitmap objectBitmaps[HEAP_SOURCE_MAX_HEAP_COUNT];
1291     size_t origObjectsAllocated;
1292     size_t origBytesAllocated;
1293     size_t numBitmaps;
1294
1295     /* All reachable objects have been marked.
1296      * Detach any unreachable interned strings before
1297      * we sweep.
1298      */
1299     dvmGcDetachDeadInternedStrings(isUnmarkedObject);
1300
1301     /* Free any known objects that are not marked.
1302      */
1303     origObjectsAllocated = dvmHeapSourceGetValue(HS_OBJECTS_ALLOCATED, NULL, 0);
1304     origBytesAllocated = dvmHeapSourceGetValue(HS_BYTES_ALLOCATED, NULL, 0);
1305
1306     markContext = &gDvm.gcHeap->markContext;
1307     markBitmaps = markContext->bitmaps;
1308     numBitmaps = dvmHeapSourceGetObjectBitmaps(objectBitmaps,
1309             HEAP_SOURCE_MAX_HEAP_COUNT);
1310 #ifndef NDEBUG
1311     if (numBitmaps != markContext->numBitmaps) {
1312         LOGE("heap bitmap count mismatch: %zd != %zd\n",
1313                 numBitmaps, markContext->numBitmaps);
1314         dvmAbort();
1315     }
1316 #endif
1317
1318 #if WITH_HPROF && WITH_HPROF_UNREACHABLE
1319     hprofDumpUnmarkedObjects(markBitmaps, objectBitmaps, numBitmaps);
1320 #endif
1321
1322     dvmHeapBitmapXorWalkLists(markBitmaps, objectBitmaps, numBitmaps,
1323             sweepBitmapCallback, NULL);
1324
1325     *numFreed = origObjectsAllocated -
1326             dvmHeapSourceGetValue(HS_OBJECTS_ALLOCATED, NULL, 0);
1327     *sizeFreed = origBytesAllocated -
1328             dvmHeapSourceGetValue(HS_BYTES_ALLOCATED, NULL, 0);
1329
1330 #ifdef WITH_PROFILER
1331     if (gDvm.allocProf.enabled) {
1332         gDvm.allocProf.freeCount += *numFreed;
1333         gDvm.allocProf.freeSize += *sizeFreed;
1334     }
1335 #endif
1336 }