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