src/v8/src/mark-compact.cc

   1 // Copyright 2012 the V8 project authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #include "src/v8.h"
   6
   7 #include "src/base/atomicops.h"
   8 #include "src/code-stubs.h"
   9 #include "src/compilation-cache.h"
  10 #include "src/cpu-profiler.h"
  11 #include "src/deoptimizer.h"
  12 #include "src/execution.h"
  13 #include "src/gdb-jit.h"
  14 #include "src/global-handles.h"
  15 #include "src/heap-profiler.h"
  16 #include "src/ic-inl.h"
  17 #include "src/incremental-marking.h"
  18 #include "src/mark-compact.h"
  19 #include "src/objects-visiting.h"
  20 #include "src/objects-visiting-inl.h"
  21 #include "src/spaces-inl.h"
  22 #include "src/stub-cache.h"
  23 #include "src/sweeper-thread.h"
  24
  25 namespace v8 {
  26 namespace internal {
  27
  28
  29 const char* Marking::kWhiteBitPattern = "00";
  30 const char* Marking::kBlackBitPattern = "10";
  31 const char* Marking::kGreyBitPattern = "11";
  32 const char* Marking::kImpossibleBitPattern = "01";
  33
  34
  35 // -------------------------------------------------------------------------
  36 // MarkCompactCollector
  37
  38 MarkCompactCollector::MarkCompactCollector(Heap* heap) :  // NOLINT
  39 #ifdef DEBUG
  40       state_(IDLE),
  41 #endif
  42       sweep_precisely_(false),
  43       reduce_memory_footprint_(false),
  44       abort_incremental_marking_(false),
  45       marking_parity_(ODD_MARKING_PARITY),
  46       compacting_(false),
  47       was_marked_incrementally_(false),
  48       sweeping_pending_(false),
  49       pending_sweeper_jobs_semaphore_(0),
  50       sequential_sweeping_(false),
  51       tracer_(NULL),
  52       migration_slots_buffer_(NULL),
  53       heap_(heap),
  54       code_flusher_(NULL),
  55       have_code_to_deoptimize_(false) { }
  56
  57 #ifdef VERIFY_HEAP
  58 class VerifyMarkingVisitor: public ObjectVisitor {
  59  public:
  60   explicit VerifyMarkingVisitor(Heap* heap) : heap_(heap) {}
  61
  62   void VisitPointers(Object** start, Object** end) {
  63     for (Object** current = start; current < end; current++) {
  64       if ((*current)->IsHeapObject()) {
  65         HeapObject* object = HeapObject::cast(*current);
  66         CHECK(heap_->mark_compact_collector()->IsMarked(object));
  67       }
  68     }
  69   }
  70
  71   void VisitEmbeddedPointer(RelocInfo* rinfo) {
  72     ASSERT(rinfo->rmode() == RelocInfo::EMBEDDED_OBJECT);
  73     if (!rinfo->host()->IsWeakObject(rinfo->target_object())) {
  74       Object* p = rinfo->target_object();
  75       VisitPointer(&p);
  76     }
  77   }
  78
  79   void VisitCell(RelocInfo* rinfo) {
  80     Code* code = rinfo->host();
  81     ASSERT(rinfo->rmode() == RelocInfo::CELL);
  82     if (!code->IsWeakObject(rinfo->target_cell())) {
  83       ObjectVisitor::VisitCell(rinfo);
  84     }
  85   }
  86
  87  private:
  88   Heap* heap_;
  89 };
  90
  91
  92 static void VerifyMarking(Heap* heap, Address bottom, Address top) {
  93   VerifyMarkingVisitor visitor(heap);
  94   HeapObject* object;
  95   Address next_object_must_be_here_or_later = bottom;
  96
  97   for (Address current = bottom;
  98        current < top;
  99        current += kPointerSize) {
 100     object = HeapObject::FromAddress(current);
 101     if (MarkCompactCollector::IsMarked(object)) {
 102       CHECK(current >= next_object_must_be_here_or_later);
 103       object->Iterate(&visitor);
 104       next_object_must_be_here_or_later = current + object->Size();
 105     }
 106   }
 107 }
 108
 109
 110 static void VerifyMarking(NewSpace* space) {
 111   Address end = space->top();
 112   NewSpacePageIterator it(space->bottom(), end);
 113   // The bottom position is at the start of its page. Allows us to use
 114   // page->area_start() as start of range on all pages.
 115   CHECK_EQ(space->bottom(),
 116             NewSpacePage::FromAddress(space->bottom())->area_start());
 117   while (it.has_next()) {
 118     NewSpacePage* page = it.next();
 119     Address limit = it.has_next() ? page->area_end() : end;
 120     CHECK(limit == end || !page->Contains(end));
 121     VerifyMarking(space->heap(), page->area_start(), limit);
 122   }
 123 }
 124
 125
 126 static void VerifyMarking(PagedSpace* space) {
 127   PageIterator it(space);
 128
 129   while (it.has_next()) {
 130     Page* p = it.next();
 131     VerifyMarking(space->heap(), p->area_start(), p->area_end());
 132   }
 133 }
 134
 135
 136 static void VerifyMarking(Heap* heap) {
 137   VerifyMarking(heap->old_pointer_space());
 138   VerifyMarking(heap->old_data_space());
 139   VerifyMarking(heap->code_space());
 140   VerifyMarking(heap->cell_space());
 141   VerifyMarking(heap->property_cell_space());
 142   VerifyMarking(heap->map_space());
 143   VerifyMarking(heap->new_space());
 144
 145   VerifyMarkingVisitor visitor(heap);
 146
 147   LargeObjectIterator it(heap->lo_space());
 148   for (HeapObject* obj = it.Next(); obj != NULL; obj = it.Next()) {
 149     if (MarkCompactCollector::IsMarked(obj)) {
 150       obj->Iterate(&visitor);
 151     }
 152   }
 153
 154   heap->IterateStrongRoots(&visitor, VISIT_ONLY_STRONG);
 155 }
 156
 157
 158 class VerifyEvacuationVisitor: public ObjectVisitor {
 159  public:
 160   void VisitPointers(Object** start, Object** end) {
 161     for (Object** current = start; current < end; current++) {
 162       if ((*current)->IsHeapObject()) {
 163         HeapObject* object = HeapObject::cast(*current);
 164         CHECK(!MarkCompactCollector::IsOnEvacuationCandidate(object));
 165       }
 166     }
 167   }
 168 };
 169
 170
 171 static void VerifyEvacuation(Address bottom, Address top) {
 172   VerifyEvacuationVisitor visitor;
 173   HeapObject* object;
 174   Address next_object_must_be_here_or_later = bottom;
 175
 176   for (Address current = bottom;
 177        current < top;
 178        current += kPointerSize) {
 179     object = HeapObject::FromAddress(current);
 180     if (MarkCompactCollector::IsMarked(object)) {
 181       CHECK(current >= next_object_must_be_here_or_later);
 182       object->Iterate(&visitor);
 183       next_object_must_be_here_or_later = current + object->Size();
 184     }
 185   }
 186 }
 187
 188
 189 static void VerifyEvacuation(NewSpace* space) {
 190   NewSpacePageIterator it(space->bottom(), space->top());
 191   VerifyEvacuationVisitor visitor;
 192
 193   while (it.has_next()) {
 194     NewSpacePage* page = it.next();
 195     Address current = page->area_start();
 196     Address limit = it.has_next() ? page->area_end() : space->top();
 197     CHECK(limit == space->top() || !page->Contains(space->top()));
 198     while (current < limit) {
 199       HeapObject* object = HeapObject::FromAddress(current);
 200       object->Iterate(&visitor);
 201       current += object->Size();
 202     }
 203   }
 204 }
 205
 206
 207 static void VerifyEvacuation(PagedSpace* space) {
 208   // TODO(hpayer): Bring back VerifyEvacuation for parallel-concurrently
 209   // swept pages.
 210   if ((FLAG_concurrent_sweeping || FLAG_parallel_sweeping) &&
 211       space->was_swept_conservatively()) return;
 212   PageIterator it(space);
 213
 214   while (it.has_next()) {
 215     Page* p = it.next();
 216     if (p->IsEvacuationCandidate()) continue;
 217     VerifyEvacuation(p->area_start(), p->area_end());
 218   }
 219 }
 220
 221
 222 static void VerifyEvacuation(Heap* heap) {
 223   VerifyEvacuation(heap->old_pointer_space());
 224   VerifyEvacuation(heap->old_data_space());
 225   VerifyEvacuation(heap->code_space());
 226   VerifyEvacuation(heap->cell_space());
 227   VerifyEvacuation(heap->property_cell_space());
 228   VerifyEvacuation(heap->map_space());
 229   VerifyEvacuation(heap->new_space());
 230
 231   VerifyEvacuationVisitor visitor;
 232   heap->IterateStrongRoots(&visitor, VISIT_ALL);
 233 }
 234 #endif  // VERIFY_HEAP
 235
 236
 237 #ifdef DEBUG
 238 class VerifyNativeContextSeparationVisitor: public ObjectVisitor {
 239  public:
 240   VerifyNativeContextSeparationVisitor() : current_native_context_(NULL) {}
 241
 242   void VisitPointers(Object** start, Object** end) {
 243     for (Object** current = start; current < end; current++) {
 244       if ((*current)->IsHeapObject()) {
 245         HeapObject* object = HeapObject::cast(*current);
 246         if (object->IsString()) continue;
 247         switch (object->map()->instance_type()) {
 248           case JS_FUNCTION_TYPE:
 249             CheckContext(JSFunction::cast(object)->context());
 250             break;
 251           case JS_GLOBAL_PROXY_TYPE:
 252             CheckContext(JSGlobalProxy::cast(object)->native_context());
 253             break;
 254           case JS_GLOBAL_OBJECT_TYPE:
 255           case JS_BUILTINS_OBJECT_TYPE:
 256             CheckContext(GlobalObject::cast(object)->native_context());
 257             break;
 258           case JS_ARRAY_TYPE:
 259           case JS_DATE_TYPE:
 260           case JS_OBJECT_TYPE:
 261           case FLOAT32x4_TYPE:
 262           case FLOAT64x2_TYPE:
 263           case INT32x4_TYPE:
 264           case JS_REGEXP_TYPE:
 265             VisitPointer(HeapObject::RawField(object, JSObject::kMapOffset));
 266             break;
 267           case MAP_TYPE:
 268             VisitPointer(HeapObject::RawField(object, Map::kPrototypeOffset));
 269             VisitPointer(HeapObject::RawField(object, Map::kConstructorOffset));
 270             break;
 271           case FIXED_ARRAY_TYPE:
 272             if (object->IsContext()) {
 273               CheckContext(object);
 274             } else {
 275               FixedArray* array = FixedArray::cast(object);
 276               int length = array->length();
 277               // Set array length to zero to prevent cycles while iterating
 278               // over array bodies, this is easier than intrusive marking.
 279               array->set_length(0);
 280               array->IterateBody(
 281                   FIXED_ARRAY_TYPE, FixedArray::SizeFor(length), this);
 282               array->set_length(length);
 283             }
 284             break;
 285           case CELL_TYPE:
 286           case JS_PROXY_TYPE:
 287           case JS_VALUE_TYPE:
 288           case TYPE_FEEDBACK_INFO_TYPE:
 289             object->Iterate(this);
 290             break;
 291           case DECLARED_ACCESSOR_INFO_TYPE:
 292           case EXECUTABLE_ACCESSOR_INFO_TYPE:
 293           case BYTE_ARRAY_TYPE:
 294           case CALL_HANDLER_INFO_TYPE:
 295           case CODE_TYPE:
 296           case FIXED_DOUBLE_ARRAY_TYPE:
 297           case HEAP_NUMBER_TYPE:
 298           case INTERCEPTOR_INFO_TYPE:
 299           case ODDBALL_TYPE:
 300           case SCRIPT_TYPE:
 301           case SHARED_FUNCTION_INFO_TYPE:
 302             break;
 303           default:
 304             UNREACHABLE();
 305         }
 306       }
 307     }
 308   }
 309
 310  private:
 311   void CheckContext(Object* context) {
 312     if (!context->IsContext()) return;
 313     Context* native_context = Context::cast(context)->native_context();
 314     if (current_native_context_ == NULL) {
 315       current_native_context_ = native_context;
 316     } else {
 317       CHECK_EQ(current_native_context_, native_context);
 318     }
 319   }
 320
 321   Context* current_native_context_;
 322 };
 323
 324
 325 static void VerifyNativeContextSeparation(Heap* heap) {
 326   HeapObjectIterator it(heap->code_space());
 327
 328   for (Object* object = it.Next(); object != NULL; object = it.Next()) {
 329     VerifyNativeContextSeparationVisitor visitor;
 330     Code::cast(object)->CodeIterateBody(&visitor);
 331   }
 332 }
 333 #endif
 334
 335
 336 void MarkCompactCollector::SetUp() {
 337   free_list_old_data_space_.Reset(new FreeList(heap_->old_data_space()));
 338   free_list_old_pointer_space_.Reset(new FreeList(heap_->old_pointer_space()));
 339 }
 340
 341
 342 void MarkCompactCollector::TearDown() {
 343   AbortCompaction();
 344 }
 345
 346
 347 void MarkCompactCollector::AddEvacuationCandidate(Page* p) {
 348   p->MarkEvacuationCandidate();
 349   evacuation_candidates_.Add(p);
 350 }
 351
 352
 353 static void TraceFragmentation(PagedSpace* space) {
 354   int number_of_pages = space->CountTotalPages();
 355   intptr_t reserved = (number_of_pages * space->AreaSize());
 356   intptr_t free = reserved - space->SizeOfObjects();
 357   PrintF("[%s]: %d pages, %d (%.1f%%) free\n",
 358          AllocationSpaceName(space->identity()),
 359          number_of_pages,
 360          static_cast<int>(free),
 361          static_cast<double>(free) * 100 / reserved);
 362 }
 363
 364
 365 bool MarkCompactCollector::StartCompaction(CompactionMode mode) {
 366   if (!compacting_) {
 367     ASSERT(evacuation_candidates_.length() == 0);
 368
 369 #ifdef ENABLE_GDB_JIT_INTERFACE
 370     // If GDBJIT interface is active disable compaction.
 371     if (FLAG_gdbjit) return false;
 372 #endif
 373
 374     CollectEvacuationCandidates(heap()->old_pointer_space());
 375     CollectEvacuationCandidates(heap()->old_data_space());
 376
 377     if (FLAG_compact_code_space &&
 378         (mode == NON_INCREMENTAL_COMPACTION ||
 379          FLAG_incremental_code_compaction)) {
 380       CollectEvacuationCandidates(heap()->code_space());
 381     } else if (FLAG_trace_fragmentation) {
 382       TraceFragmentation(heap()->code_space());
 383     }
 384
 385     if (FLAG_trace_fragmentation) {
 386       TraceFragmentation(heap()->map_space());
 387       TraceFragmentation(heap()->cell_space());
 388       TraceFragmentation(heap()->property_cell_space());
 389     }
 390
 391     heap()->old_pointer_space()->EvictEvacuationCandidatesFromFreeLists();
 392     heap()->old_data_space()->EvictEvacuationCandidatesFromFreeLists();
 393     heap()->code_space()->EvictEvacuationCandidatesFromFreeLists();
 394
 395     compacting_ = evacuation_candidates_.length() > 0;
 396   }
 397
 398   return compacting_;
 399 }
 400
 401
 402 void MarkCompactCollector::CollectGarbage() {
 403   // Make sure that Prepare() has been called. The individual steps below will
 404   // update the state as they proceed.
 405   ASSERT(state_ == PREPARE_GC);
 406
 407   MarkLiveObjects();
 408   ASSERT(heap_->incremental_marking()->IsStopped());
 409
 410   if (FLAG_collect_maps) ClearNonLiveReferences();
 411
 412   ClearWeakCollections();
 413
 414 #ifdef VERIFY_HEAP
 415   if (FLAG_verify_heap) {
 416     VerifyMarking(heap_);
 417   }
 418 #endif
 419
 420   SweepSpaces();
 421
 422 #ifdef DEBUG
 423   if (FLAG_verify_native_context_separation) {
 424     VerifyNativeContextSeparation(heap_);
 425   }
 426 #endif
 427
 428 #ifdef VERIFY_HEAP
 429   if (heap()->weak_embedded_objects_verification_enabled()) {
 430     VerifyWeakEmbeddedObjectsInCode();
 431   }
 432   if (FLAG_collect_maps && FLAG_omit_map_checks_for_leaf_maps) {
 433     VerifyOmittedMapChecks();
 434   }
 435 #endif
 436
 437   Finish();
 438
 439   if (marking_parity_ == EVEN_MARKING_PARITY) {
 440     marking_parity_ = ODD_MARKING_PARITY;
 441   } else {
 442     ASSERT(marking_parity_ == ODD_MARKING_PARITY);
 443     marking_parity_ = EVEN_MARKING_PARITY;
 444   }
 445
 446   tracer_ = NULL;
 447 }
 448
 449
 450 #ifdef VERIFY_HEAP
 451 void MarkCompactCollector::VerifyMarkbitsAreClean(PagedSpace* space) {
 452   PageIterator it(space);
 453
 454   while (it.has_next()) {
 455     Page* p = it.next();
 456     CHECK(p->markbits()->IsClean());
 457     CHECK_EQ(0, p->LiveBytes());
 458   }
 459 }
 460
 461
 462 void MarkCompactCollector::VerifyMarkbitsAreClean(NewSpace* space) {
 463   NewSpacePageIterator it(space->bottom(), space->top());
 464
 465   while (it.has_next()) {
 466     NewSpacePage* p = it.next();
 467     CHECK(p->markbits()->IsClean());
 468     CHECK_EQ(0, p->LiveBytes());
 469   }
 470 }
 471
 472
 473 void MarkCompactCollector::VerifyMarkbitsAreClean() {
 474   VerifyMarkbitsAreClean(heap_->old_pointer_space());
 475   VerifyMarkbitsAreClean(heap_->old_data_space());
 476   VerifyMarkbitsAreClean(heap_->code_space());
 477   VerifyMarkbitsAreClean(heap_->cell_space());
 478   VerifyMarkbitsAreClean(heap_->property_cell_space());
 479   VerifyMarkbitsAreClean(heap_->map_space());
 480   VerifyMarkbitsAreClean(heap_->new_space());
 481
 482   LargeObjectIterator it(heap_->lo_space());
 483   for (HeapObject* obj = it.Next(); obj != NULL; obj = it.Next()) {
 484     MarkBit mark_bit = Marking::MarkBitFrom(obj);
 485     CHECK(Marking::IsWhite(mark_bit));
 486     CHECK_EQ(0, Page::FromAddress(obj->address())->LiveBytes());
 487   }
 488 }
 489
 490
 491 void MarkCompactCollector::VerifyWeakEmbeddedObjectsInCode() {
 492   HeapObjectIterator code_iterator(heap()->code_space());
 493   for (HeapObject* obj = code_iterator.Next();
 494        obj != NULL;
 495        obj = code_iterator.Next()) {
 496     Code* code = Code::cast(obj);
 497     if (!code->is_optimized_code() && !code->is_weak_stub()) continue;
 498     if (WillBeDeoptimized(code)) continue;
 499     code->VerifyEmbeddedObjectsDependency();
 500   }
 501 }
 502
 503
 504 void MarkCompactCollector::VerifyOmittedMapChecks() {
 505   HeapObjectIterator iterator(heap()->map_space());
 506   for (HeapObject* obj = iterator.Next();
 507        obj != NULL;
 508        obj = iterator.Next()) {
 509     Map* map = Map::cast(obj);
 510     map->VerifyOmittedMapChecks();
 511   }
 512 }
 513 #endif  // VERIFY_HEAP
 514
 515
 516 static void ClearMarkbitsInPagedSpace(PagedSpace* space) {
 517   PageIterator it(space);
 518
 519   while (it.has_next()) {
 520     Bitmap::Clear(it.next());
 521   }
 522 }
 523
 524
 525 static void ClearMarkbitsInNewSpace(NewSpace* space) {
 526   NewSpacePageIterator it(space->ToSpaceStart(), space->ToSpaceEnd());
 527
 528   while (it.has_next()) {
 529     Bitmap::Clear(it.next());
 530   }
 531 }
 532
 533
 534 void MarkCompactCollector::ClearMarkbits() {
 535   ClearMarkbitsInPagedSpace(heap_->code_space());
 536   ClearMarkbitsInPagedSpace(heap_->map_space());
 537   ClearMarkbitsInPagedSpace(heap_->old_pointer_space());
 538   ClearMarkbitsInPagedSpace(heap_->old_data_space());
 539   ClearMarkbitsInPagedSpace(heap_->cell_space());
 540   ClearMarkbitsInPagedSpace(heap_->property_cell_space());
 541   ClearMarkbitsInNewSpace(heap_->new_space());
 542
 543   LargeObjectIterator it(heap_->lo_space());
 544   for (HeapObject* obj = it.Next(); obj != NULL; obj = it.Next()) {
 545     MarkBit mark_bit = Marking::MarkBitFrom(obj);
 546     mark_bit.Clear();
 547     mark_bit.Next().Clear();
 548     Page::FromAddress(obj->address())->ResetProgressBar();
 549     Page::FromAddress(obj->address())->ResetLiveBytes();
 550   }
 551 }
 552
 553
 554 class MarkCompactCollector::SweeperTask : public v8::Task {
 555  public:
 556   SweeperTask(Heap* heap, PagedSpace* space)
 557     : heap_(heap), space_(space) {}
 558
 559   virtual ~SweeperTask() {}
 560
 561  private:
 562   // v8::Task overrides.
 563   virtual void Run() V8_OVERRIDE {
 564     heap_->mark_compact_collector()->SweepInParallel(space_);
 565     heap_->mark_compact_collector()->pending_sweeper_jobs_semaphore_.Signal();
 566   }
 567
 568   Heap* heap_;
 569   PagedSpace* space_;
 570
 571   DISALLOW_COPY_AND_ASSIGN(SweeperTask);
 572 };
 573
 574
 575 void MarkCompactCollector::StartSweeperThreads() {
 576   ASSERT(free_list_old_pointer_space_.get()->IsEmpty());
 577   ASSERT(free_list_old_data_space_.get()->IsEmpty());
 578   sweeping_pending_ = true;
 579   for (int i = 0; i < isolate()->num_sweeper_threads(); i++) {
 580     isolate()->sweeper_threads()[i]->StartSweeping();
 581   }
 582   if (FLAG_job_based_sweeping) {
 583     V8::GetCurrentPlatform()->CallOnBackgroundThread(
 584         new SweeperTask(heap(), heap()->old_data_space()),
 585         v8::Platform::kShortRunningTask);
 586     V8::GetCurrentPlatform()->CallOnBackgroundThread(
 587         new SweeperTask(heap(), heap()->old_pointer_space()),
 588         v8::Platform::kShortRunningTask);
 589   }
 590 }
 591
 592
 593 void MarkCompactCollector::WaitUntilSweepingCompleted() {
 594   ASSERT(sweeping_pending_ == true);
 595   for (int i = 0; i < isolate()->num_sweeper_threads(); i++) {
 596     isolate()->sweeper_threads()[i]->WaitForSweeperThread();
 597   }
 598   if (FLAG_job_based_sweeping) {
 599     // Wait twice for both jobs.
 600     pending_sweeper_jobs_semaphore_.Wait();
 601     pending_sweeper_jobs_semaphore_.Wait();
 602   }
 603   ParallelSweepSpacesComplete();
 604   sweeping_pending_ = false;
 605   RefillFreeList(heap()->paged_space(OLD_DATA_SPACE));
 606   RefillFreeList(heap()->paged_space(OLD_POINTER_SPACE));
 607   heap()->paged_space(OLD_DATA_SPACE)->ResetUnsweptFreeBytes();
 608   heap()->paged_space(OLD_POINTER_SPACE)->ResetUnsweptFreeBytes();
 609 }
 610
 611
 612 bool MarkCompactCollector::IsSweepingCompleted() {
 613   for (int i = 0; i < isolate()->num_sweeper_threads(); i++) {
 614     if (!isolate()->sweeper_threads()[i]->SweepingCompleted()) {
 615       return false;
 616     }
 617   }
 618   if (FLAG_job_based_sweeping) {
 619     if (!pending_sweeper_jobs_semaphore_.WaitFor(TimeDelta::FromSeconds(0))) {
 620       return false;
 621     }
 622     pending_sweeper_jobs_semaphore_.Signal();
 623   }
 624   return true;
 625 }
 626
 627
 628 void MarkCompactCollector::RefillFreeList(PagedSpace* space) {
 629   FreeList* free_list;
 630
 631   if (space == heap()->old_pointer_space()) {
 632     free_list = free_list_old_pointer_space_.get();
 633   } else if (space == heap()->old_data_space()) {
 634     free_list = free_list_old_data_space_.get();
 635   } else {
 636     // Any PagedSpace might invoke RefillFreeLists, so we need to make sure
 637     // to only refill them for old data and pointer spaces.
 638     return;
 639   }
 640
 641   intptr_t freed_bytes = space->free_list()->Concatenate(free_list);
 642   space->AddToAccountingStats(freed_bytes);
 643   space->DecrementUnsweptFreeBytes(freed_bytes);
 644 }
 645
 646
 647 bool MarkCompactCollector::AreSweeperThreadsActivated() {
 648   return isolate()->sweeper_threads() != NULL || FLAG_job_based_sweeping;
 649 }
 650
 651
 652 bool MarkCompactCollector::IsConcurrentSweepingInProgress() {
 653   return sweeping_pending_;
 654 }
 655
 656
 657 void Marking::TransferMark(Address old_start, Address new_start) {
 658   // This is only used when resizing an object.
 659   ASSERT(MemoryChunk::FromAddress(old_start) ==
 660          MemoryChunk::FromAddress(new_start));
 661
 662   if (!heap_->incremental_marking()->IsMarking()) return;
 663
 664   // If the mark doesn't move, we don't check the color of the object.
 665   // It doesn't matter whether the object is black, since it hasn't changed
 666   // size, so the adjustment to the live data count will be zero anyway.
 667   if (old_start == new_start) return;
 668
 669   MarkBit new_mark_bit = MarkBitFrom(new_start);
 670   MarkBit old_mark_bit = MarkBitFrom(old_start);
 671
 672 #ifdef DEBUG
 673   ObjectColor old_color = Color(old_mark_bit);
 674 #endif
 675
 676   if (Marking::IsBlack(old_mark_bit)) {
 677     old_mark_bit.Clear();
 678     ASSERT(IsWhite(old_mark_bit));
 679     Marking::MarkBlack(new_mark_bit);
 680     return;
 681   } else if (Marking::IsGrey(old_mark_bit)) {
 682     old_mark_bit.Clear();
 683     old_mark_bit.Next().Clear();
 684     ASSERT(IsWhite(old_mark_bit));
 685     heap_->incremental_marking()->WhiteToGreyAndPush(
 686         HeapObject::FromAddress(new_start), new_mark_bit);
 687     heap_->incremental_marking()->RestartIfNotMarking();
 688   }
 689
 690 #ifdef DEBUG
 691   ObjectColor new_color = Color(new_mark_bit);
 692   ASSERT(new_color == old_color);
 693 #endif
 694 }
 695
 696
 697 const char* AllocationSpaceName(AllocationSpace space) {
 698   switch (space) {
 699     case NEW_SPACE: return "NEW_SPACE";
 700     case OLD_POINTER_SPACE: return "OLD_POINTER_SPACE";
 701     case OLD_DATA_SPACE: return "OLD_DATA_SPACE";
 702     case CODE_SPACE: return "CODE_SPACE";
 703     case MAP_SPACE: return "MAP_SPACE";
 704     case CELL_SPACE: return "CELL_SPACE";
 705     case PROPERTY_CELL_SPACE:
 706       return "PROPERTY_CELL_SPACE";
 707     case LO_SPACE: return "LO_SPACE";
 708     default:
 709       UNREACHABLE();
 710   }
 711
 712   return NULL;
 713 }
 714
 715
 716 // Returns zero for pages that have so little fragmentation that it is not
 717 // worth defragmenting them.  Otherwise a positive integer that gives an
 718 // estimate of fragmentation on an arbitrary scale.
 719 static int FreeListFragmentation(PagedSpace* space, Page* p) {
 720   // If page was not swept then there are no free list items on it.
 721   if (!p->WasSwept()) {
 722     if (FLAG_trace_fragmentation) {
 723       PrintF("%p [%s]: %d bytes live (unswept)\n",
 724              reinterpret_cast<void*>(p),
 725              AllocationSpaceName(space->identity()),
 726              p->LiveBytes());
 727     }
 728     return 0;
 729   }
 730
 731   PagedSpace::SizeStats sizes;
 732   space->ObtainFreeListStatistics(p, &sizes);
 733
 734   intptr_t ratio;
 735   intptr_t ratio_threshold;
 736   intptr_t area_size = space->AreaSize();
 737   if (space->identity() == CODE_SPACE) {
 738     ratio = (sizes.medium_size_ * 10 + sizes.large_size_ * 2) * 100 /
 739         area_size;
 740     ratio_threshold = 10;
 741   } else {
 742     ratio = (sizes.small_size_ * 5 + sizes.medium_size_) * 100 /
 743         area_size;
 744     ratio_threshold = 15;
 745   }
 746
 747   if (FLAG_trace_fragmentation) {
 748     PrintF("%p [%s]: %d (%.2f%%) %d (%.2f%%) %d (%.2f%%) %d (%.2f%%) %s\n",
 749            reinterpret_cast<void*>(p),
 750            AllocationSpaceName(space->identity()),
 751            static_cast<int>(sizes.small_size_),
 752            static_cast<double>(sizes.small_size_ * 100) /
 753            area_size,
 754            static_cast<int>(sizes.medium_size_),
 755            static_cast<double>(sizes.medium_size_ * 100) /
 756            area_size,
 757            static_cast<int>(sizes.large_size_),
 758            static_cast<double>(sizes.large_size_ * 100) /
 759            area_size,
 760            static_cast<int>(sizes.huge_size_),
 761            static_cast<double>(sizes.huge_size_ * 100) /
 762            area_size,
 763            (ratio > ratio_threshold) ? "[fragmented]" : "");
 764   }
 765
 766   if (FLAG_always_compact && sizes.Total() != area_size) {
 767     return 1;
 768   }
 769
 770   if (ratio <= ratio_threshold) return 0;  // Not fragmented.
 771
 772   return static_cast<int>(ratio - ratio_threshold);
 773 }
 774
 775
 776 void MarkCompactCollector::CollectEvacuationCandidates(PagedSpace* space) {
 777   ASSERT(space->identity() == OLD_POINTER_SPACE ||
 778          space->identity() == OLD_DATA_SPACE ||
 779          space->identity() == CODE_SPACE);
 780
 781   static const int kMaxMaxEvacuationCandidates = 1000;
 782   int number_of_pages = space->CountTotalPages();
 783   int max_evacuation_candidates =
 784       static_cast<int>(std::sqrt(number_of_pages / 2.0) + 1);
 785
 786   if (FLAG_stress_compaction || FLAG_always_compact) {
 787     max_evacuation_candidates = kMaxMaxEvacuationCandidates;
 788   }
 789
 790   class Candidate {
 791    public:
 792     Candidate() : fragmentation_(0), page_(NULL) { }
 793     Candidate(int f, Page* p) : fragmentation_(f), page_(p) { }
 794
 795     int fragmentation() { return fragmentation_; }
 796     Page* page() { return page_; }
 797
 798    private:
 799     int fragmentation_;
 800     Page* page_;
 801   };
 802
 803   enum CompactionMode {
 804     COMPACT_FREE_LISTS,
 805     REDUCE_MEMORY_FOOTPRINT
 806   };
 807
 808   CompactionMode mode = COMPACT_FREE_LISTS;
 809
 810   intptr_t reserved = number_of_pages * space->AreaSize();
 811   intptr_t over_reserved = reserved - space->SizeOfObjects();
 812   static const intptr_t kFreenessThreshold = 50;
 813
 814   if (reduce_memory_footprint_ && over_reserved >= space->AreaSize()) {
 815     // If reduction of memory footprint was requested, we are aggressive
 816     // about choosing pages to free.  We expect that half-empty pages
 817     // are easier to compact so slightly bump the limit.
 818     mode = REDUCE_MEMORY_FOOTPRINT;
 819     max_evacuation_candidates += 2;
 820   }
 821
 822
 823   if (over_reserved > reserved / 3 && over_reserved >= 2 * space->AreaSize()) {
 824     // If over-usage is very high (more than a third of the space), we
 825     // try to free all mostly empty pages.  We expect that almost empty
 826     // pages are even easier to compact so bump the limit even more.
 827     mode = REDUCE_MEMORY_FOOTPRINT;
 828     max_evacuation_candidates *= 2;
 829   }
 830
 831   if (FLAG_trace_fragmentation && mode == REDUCE_MEMORY_FOOTPRINT) {
 832     PrintF("Estimated over reserved memory: %.1f / %.1f MB (threshold %d), "
 833            "evacuation candidate limit: %d\n",
 834            static_cast<double>(over_reserved) / MB,
 835            static_cast<double>(reserved) / MB,
 836            static_cast<int>(kFreenessThreshold),
 837            max_evacuation_candidates);
 838   }
 839
 840   intptr_t estimated_release = 0;
 841
 842   Candidate candidates[kMaxMaxEvacuationCandidates];
 843
 844   max_evacuation_candidates =
 845       Min(kMaxMaxEvacuationCandidates, max_evacuation_candidates);
 846
 847   int count = 0;
 848   int fragmentation = 0;
 849   Candidate* least = NULL;
 850
 851   PageIterator it(space);
 852   if (it.has_next()) it.next();  // Never compact the first page.
 853
 854   while (it.has_next()) {
 855     Page* p = it.next();
 856     p->ClearEvacuationCandidate();
 857
 858     if (FLAG_stress_compaction) {
 859       unsigned int counter = space->heap()->ms_count();
 860       uintptr_t page_number = reinterpret_cast<uintptr_t>(p) >> kPageSizeBits;
 861       if ((counter & 1) == (page_number & 1)) fragmentation = 1;
 862     } else if (mode == REDUCE_MEMORY_FOOTPRINT) {
 863       // Don't try to release too many pages.
 864       if (estimated_release >= over_reserved) {
 865         continue;
 866       }
 867
 868       intptr_t free_bytes = 0;
 869
 870       if (!p->WasSwept()) {
 871         free_bytes = (p->area_size() - p->LiveBytes());
 872       } else {
 873         PagedSpace::SizeStats sizes;
 874         space->ObtainFreeListStatistics(p, &sizes);
 875         free_bytes = sizes.Total();
 876       }
 877
 878       int free_pct = static_cast<int>(free_bytes * 100) / p->area_size();
 879
 880       if (free_pct >= kFreenessThreshold) {
 881         estimated_release += free_bytes;
 882         fragmentation = free_pct;
 883       } else {
 884         fragmentation = 0;
 885       }
 886
 887       if (FLAG_trace_fragmentation) {
 888         PrintF("%p [%s]: %d (%.2f%%) free %s\n",
 889                reinterpret_cast<void*>(p),
 890                AllocationSpaceName(space->identity()),
 891                static_cast<int>(free_bytes),
 892                static_cast<double>(free_bytes * 100) / p->area_size(),
 893                (fragmentation > 0) ? "[fragmented]" : "");
 894       }
 895     } else {
 896       fragmentation = FreeListFragmentation(space, p);
 897     }
 898
 899     if (fragmentation != 0) {
 900       if (count < max_evacuation_candidates) {
 901         candidates[count++] = Candidate(fragmentation, p);
 902       } else {
 903         if (least == NULL) {
 904           for (int i = 0; i < max_evacuation_candidates; i++) {
 905             if (least == NULL ||
 906                 candidates[i].fragmentation() < least->fragmentation()) {
 907               least = candidates + i;
 908             }
 909           }
 910         }
 911         if (least->fragmentation() < fragmentation) {
 912           *least = Candidate(fragmentation, p);
 913           least = NULL;
 914         }
 915       }
 916     }
 917   }
 918
 919   for (int i = 0; i < count; i++) {
 920     AddEvacuationCandidate(candidates[i].page());
 921   }
 922
 923   if (count > 0 && FLAG_trace_fragmentation) {
 924     PrintF("Collected %d evacuation candidates for space %s\n",
 925            count,
 926            AllocationSpaceName(space->identity()));
 927   }
 928 }
 929
 930
 931 void MarkCompactCollector::AbortCompaction() {
 932   if (compacting_) {
 933     int npages = evacuation_candidates_.length();
 934     for (int i = 0; i < npages; i++) {
 935       Page* p = evacuation_candidates_[i];
 936       slots_buffer_allocator_.DeallocateChain(p->slots_buffer_address());
 937       p->ClearEvacuationCandidate();
 938       p->ClearFlag(MemoryChunk::RESCAN_ON_EVACUATION);
 939     }
 940     compacting_ = false;
 941     evacuation_candidates_.Rewind(0);
 942     invalidated_code_.Rewind(0);
 943   }
 944   ASSERT_EQ(0, evacuation_candidates_.length());
 945 }
 946
 947
 948 void MarkCompactCollector::Prepare(GCTracer* tracer) {
 949   was_marked_incrementally_ = heap()->incremental_marking()->IsMarking();
 950
 951   // Rather than passing the tracer around we stash it in a static member
 952   // variable.
 953   tracer_ = tracer;
 954
 955 #ifdef DEBUG
 956   ASSERT(state_ == IDLE);
 957   state_ = PREPARE_GC;
 958 #endif
 959
 960   ASSERT(!FLAG_never_compact || !FLAG_always_compact);
 961
 962   if (IsConcurrentSweepingInProgress()) {
 963     // Instead of waiting we could also abort the sweeper threads here.
 964     WaitUntilSweepingCompleted();
 965   }
 966
 967   // Clear marking bits if incremental marking is aborted.
 968   if (was_marked_incrementally_ && abort_incremental_marking_) {
 969     heap()->incremental_marking()->Abort();
 970     ClearMarkbits();
 971     AbortCompaction();
 972     was_marked_incrementally_ = false;
 973   }
 974
 975   // Don't start compaction if we are in the middle of incremental
 976   // marking cycle. We did not collect any slots.
 977   if (!FLAG_never_compact && !was_marked_incrementally_) {
 978     StartCompaction(NON_INCREMENTAL_COMPACTION);
 979   }
 980
 981   PagedSpaces spaces(heap());
 982   for (PagedSpace* space = spaces.next();
 983        space != NULL;
 984        space = spaces.next()) {
 985     space->PrepareForMarkCompact();
 986   }
 987
 988 #ifdef VERIFY_HEAP
 989   if (!was_marked_incrementally_ && FLAG_verify_heap) {
 990     VerifyMarkbitsAreClean();
 991   }
 992 #endif
 993 }
 994
 995
 996 void MarkCompactCollector::Finish() {
 997 #ifdef DEBUG
 998   ASSERT(state_ == SWEEP_SPACES || state_ == RELOCATE_OBJECTS);
 999   state_ = IDLE;
1000 #endif
1001   // The stub cache is not traversed during GC; clear the cache to
1002   // force lazy re-initialization of it. This must be done after the
1003   // GC, because it relies on the new address of certain old space
1004   // objects (empty string, illegal builtin).
1005   isolate()->stub_cache()->Clear();
1006
1007   if (have_code_to_deoptimize_) {
1008     // Some code objects were marked for deoptimization during the GC.
1009     Deoptimizer::DeoptimizeMarkedCode(isolate());
1010     have_code_to_deoptimize_ = false;
1011   }
1012 }
1013
1014
1015 // -------------------------------------------------------------------------
1016 // Phase 1: tracing and marking live objects.
1017 //   before: all objects are in normal state.
1018 //   after: a live object's map pointer is marked as '00'.
1019
1020 // Marking all live objects in the heap as part of mark-sweep or mark-compact
1021 // collection.  Before marking, all objects are in their normal state.  After
1022 // marking, live objects' map pointers are marked indicating that the object
1023 // has been found reachable.
1024 //
1025 // The marking algorithm is a (mostly) depth-first (because of possible stack
1026 // overflow) traversal of the graph of objects reachable from the roots.  It
1027 // uses an explicit stack of pointers rather than recursion.  The young
1028 // generation's inactive ('from') space is used as a marking stack.  The
1029 // objects in the marking stack are the ones that have been reached and marked
1030 // but their children have not yet been visited.
1031 //
1032 // The marking stack can overflow during traversal.  In that case, we set an
1033 // overflow flag.  When the overflow flag is set, we continue marking objects
1034 // reachable from the objects on the marking stack, but no longer push them on
1035 // the marking stack.  Instead, we mark them as both marked and overflowed.
1036 // When the stack is in the overflowed state, objects marked as overflowed
1037 // have been reached and marked but their children have not been visited yet.
1038 // After emptying the marking stack, we clear the overflow flag and traverse
1039 // the heap looking for objects marked as overflowed, push them on the stack,
1040 // and continue with marking.  This process repeats until all reachable
1041 // objects have been marked.
1042
1043 void CodeFlusher::ProcessJSFunctionCandidates() {
1044   Code* lazy_compile =
1045       isolate_->builtins()->builtin(Builtins::kCompileUnoptimized);
1046   Object* undefined = isolate_->heap()->undefined_value();
1047
1048   JSFunction* candidate = jsfunction_candidates_head_;
1049   JSFunction* next_candidate;
1050   while (candidate != NULL) {
1051     next_candidate = GetNextCandidate(candidate);
1052     ClearNextCandidate(candidate, undefined);
1053
1054     SharedFunctionInfo* shared = candidate->shared();
1055
1056     Code* code = shared->code();
1057     MarkBit code_mark = Marking::MarkBitFrom(code);
1058     if (!code_mark.Get()) {
1059       if (FLAG_trace_code_flushing && shared->is_compiled()) {
1060         PrintF("[code-flushing clears: ");
1061         shared->ShortPrint();
1062         PrintF(" - age: %d]\n", code->GetAge());
1063       }
1064       shared->set_code(lazy_compile);
1065       candidate->set_code(lazy_compile);
1066     } else {
1067       candidate->set_code(code);
1068     }
1069
1070     // We are in the middle of a GC cycle so the write barrier in the code
1071     // setter did not record the slot update and we have to do that manually.
1072     Address slot = candidate->address() + JSFunction::kCodeEntryOffset;
1073     Code* target = Code::cast(Code::GetObjectFromEntryAddress(slot));
1074     isolate_->heap()->mark_compact_collector()->
1075         RecordCodeEntrySlot(slot, target);
1076
1077     Object** shared_code_slot =
1078         HeapObject::RawField(shared, SharedFunctionInfo::kCodeOffset);
1079     isolate_->heap()->mark_compact_collector()->
1080         RecordSlot(shared_code_slot, shared_code_slot, *shared_code_slot);
1081
1082     candidate = next_candidate;
1083   }
1084
1085   jsfunction_candidates_head_ = NULL;
1086 }
1087
1088
1089 void CodeFlusher::ProcessSharedFunctionInfoCandidates() {
1090   Code* lazy_compile =
1091       isolate_->builtins()->builtin(Builtins::kCompileUnoptimized);
1092
1093   SharedFunctionInfo* candidate = shared_function_info_candidates_head_;
1094   SharedFunctionInfo* next_candidate;
1095   while (candidate != NULL) {
1096     next_candidate = GetNextCandidate(candidate);
1097     ClearNextCandidate(candidate);
1098
1099     Code* code = candidate->code();
1100     MarkBit code_mark = Marking::MarkBitFrom(code);
1101     if (!code_mark.Get()) {
1102       if (FLAG_trace_code_flushing && candidate->is_compiled()) {
1103         PrintF("[code-flushing clears: ");
1104         candidate->ShortPrint();
1105         PrintF(" - age: %d]\n", code->GetAge());
1106       }
1107       candidate->set_code(lazy_compile);
1108     }
1109
1110     Object** code_slot =
1111         HeapObject::RawField(candidate, SharedFunctionInfo::kCodeOffset);
1112     isolate_->heap()->mark_compact_collector()->
1113         RecordSlot(code_slot, code_slot, *code_slot);
1114
1115     candidate = next_candidate;
1116   }
1117
1118   shared_function_info_candidates_head_ = NULL;
1119 }
1120
1121
1122 void CodeFlusher::ProcessOptimizedCodeMaps() {
1123   STATIC_ASSERT(SharedFunctionInfo::kEntryLength == 4);
1124
1125   SharedFunctionInfo* holder = optimized_code_map_holder_head_;
1126   SharedFunctionInfo* next_holder;
1127
1128   while (holder != NULL) {
1129     next_holder = GetNextCodeMap(holder);
1130     ClearNextCodeMap(holder);
1131
1132     FixedArray* code_map = FixedArray::cast(holder->optimized_code_map());
1133     int new_length = SharedFunctionInfo::kEntriesStart;
1134     int old_length = code_map->length();
1135     for (int i = SharedFunctionInfo::kEntriesStart;
1136          i < old_length;
1137          i += SharedFunctionInfo::kEntryLength) {
1138       Code* code =
1139           Code::cast(code_map->get(i + SharedFunctionInfo::kCachedCodeOffset));
1140       if (!Marking::MarkBitFrom(code).Get()) continue;
1141
1142       // Move every slot in the entry.
1143       for (int j = 0; j < SharedFunctionInfo::kEntryLength; j++) {
1144         int dst_index = new_length++;
1145         Object** slot = code_map->RawFieldOfElementAt(dst_index);
1146         Object* object = code_map->get(i + j);
1147         code_map->set(dst_index, object);
1148         if (j == SharedFunctionInfo::kOsrAstIdOffset) {
1149           ASSERT(object->IsSmi());
1150         } else {
1151           ASSERT(Marking::IsBlack(
1152               Marking::MarkBitFrom(HeapObject::cast(*slot))));
1153           isolate_->heap()->mark_compact_collector()->
1154               RecordSlot(slot, slot, *slot);
1155         }
1156       }
1157     }
1158
1159     // Trim the optimized code map if entries have been removed.
1160     if (new_length < old_length) {
1161       holder->TrimOptimizedCodeMap(old_length - new_length);
1162     }
1163
1164     holder = next_holder;
1165   }
1166
1167   optimized_code_map_holder_head_ = NULL;
1168 }
1169
1170
1171 void CodeFlusher::EvictCandidate(SharedFunctionInfo* shared_info) {
1172   // Make sure previous flushing decisions are revisited.
1173   isolate_->heap()->incremental_marking()->RecordWrites(shared_info);
1174
1175   if (FLAG_trace_code_flushing) {
1176     PrintF("[code-flushing abandons function-info: ");
1177     shared_info->ShortPrint();
1178     PrintF("]\n");
1179   }
1180
1181   SharedFunctionInfo* candidate = shared_function_info_candidates_head_;
1182   SharedFunctionInfo* next_candidate;
1183   if (candidate == shared_info) {
1184     next_candidate = GetNextCandidate(shared_info);
1185     shared_function_info_candidates_head_ = next_candidate;
1186     ClearNextCandidate(shared_info);
1187   } else {
1188     while (candidate != NULL) {
1189       next_candidate = GetNextCandidate(candidate);
1190
1191       if (next_candidate == shared_info) {
1192         next_candidate = GetNextCandidate(shared_info);
1193         SetNextCandidate(candidate, next_candidate);
1194         ClearNextCandidate(shared_info);
1195         break;
1196       }
1197
1198       candidate = next_candidate;
1199     }
1200   }
1201 }
1202
1203
1204 void CodeFlusher::EvictCandidate(JSFunction* function) {
1205   ASSERT(!function->next_function_link()->IsUndefined());
1206   Object* undefined = isolate_->heap()->undefined_value();
1207
1208   // Make sure previous flushing decisions are revisited.
1209   isolate_->heap()->incremental_marking()->RecordWrites(function);
1210   isolate_->heap()->incremental_marking()->RecordWrites(function->shared());
1211
1212   if (FLAG_trace_code_flushing) {
1213     PrintF("[code-flushing abandons closure: ");
1214     function->shared()->ShortPrint();
1215     PrintF("]\n");
1216   }
1217
1218   JSFunction* candidate = jsfunction_candidates_head_;
1219   JSFunction* next_candidate;
1220   if (candidate == function) {
1221     next_candidate = GetNextCandidate(function);
1222     jsfunction_candidates_head_ = next_candidate;
1223     ClearNextCandidate(function, undefined);
1224   } else {
1225     while (candidate != NULL) {
1226       next_candidate = GetNextCandidate(candidate);
1227
1228       if (next_candidate == function) {
1229         next_candidate = GetNextCandidate(function);
1230         SetNextCandidate(candidate, next_candidate);
1231         ClearNextCandidate(function, undefined);
1232         break;
1233       }
1234
1235       candidate = next_candidate;
1236     }
1237   }
1238 }
1239
1240
1241 void CodeFlusher::EvictOptimizedCodeMap(SharedFunctionInfo* code_map_holder) {
1242   ASSERT(!FixedArray::cast(code_map_holder->optimized_code_map())->
1243          get(SharedFunctionInfo::kNextMapIndex)->IsUndefined());
1244
1245   // Make sure previous flushing decisions are revisited.
1246   isolate_->heap()->incremental_marking()->RecordWrites(code_map_holder);
1247
1248   if (FLAG_trace_code_flushing) {
1249     PrintF("[code-flushing abandons code-map: ");
1250     code_map_holder->ShortPrint();
1251     PrintF("]\n");
1252   }
1253
1254   SharedFunctionInfo* holder = optimized_code_map_holder_head_;
1255   SharedFunctionInfo* next_holder;
1256   if (holder == code_map_holder) {
1257     next_holder = GetNextCodeMap(code_map_holder);
1258     optimized_code_map_holder_head_ = next_holder;
1259     ClearNextCodeMap(code_map_holder);
1260   } else {
1261     while (holder != NULL) {
1262       next_holder = GetNextCodeMap(holder);
1263
1264       if (next_holder == code_map_holder) {
1265         next_holder = GetNextCodeMap(code_map_holder);
1266         SetNextCodeMap(holder, next_holder);
1267         ClearNextCodeMap(code_map_holder);
1268         break;
1269       }
1270
1271       holder = next_holder;
1272     }
1273   }
1274 }
1275
1276
1277 void CodeFlusher::EvictJSFunctionCandidates() {
1278   JSFunction* candidate = jsfunction_candidates_head_;
1279   JSFunction* next_candidate;
1280   while (candidate != NULL) {
1281     next_candidate = GetNextCandidate(candidate);
1282     EvictCandidate(candidate);
1283     candidate = next_candidate;
1284   }
1285   ASSERT(jsfunction_candidates_head_ == NULL);
1286 }
1287
1288
1289 void CodeFlusher::EvictSharedFunctionInfoCandidates() {
1290   SharedFunctionInfo* candidate = shared_function_info_candidates_head_;
1291   SharedFunctionInfo* next_candidate;
1292   while (candidate != NULL) {
1293     next_candidate = GetNextCandidate(candidate);
1294     EvictCandidate(candidate);
1295     candidate = next_candidate;
1296   }
1297   ASSERT(shared_function_info_candidates_head_ == NULL);
1298 }
1299
1300
1301 void CodeFlusher::EvictOptimizedCodeMaps() {
1302   SharedFunctionInfo* holder = optimized_code_map_holder_head_;
1303   SharedFunctionInfo* next_holder;
1304   while (holder != NULL) {
1305     next_holder = GetNextCodeMap(holder);
1306     EvictOptimizedCodeMap(holder);
1307     holder = next_holder;
1308   }
1309   ASSERT(optimized_code_map_holder_head_ == NULL);
1310 }
1311
1312
1313 void CodeFlusher::IteratePointersToFromSpace(ObjectVisitor* v) {
1314   Heap* heap = isolate_->heap();
1315
1316   JSFunction** slot = &jsfunction_candidates_head_;
1317   JSFunction* candidate = jsfunction_candidates_head_;
1318   while (candidate != NULL) {
1319     if (heap->InFromSpace(candidate)) {
1320       v->VisitPointer(reinterpret_cast<Object**>(slot));
1321     }
1322     candidate = GetNextCandidate(*slot);
1323     slot = GetNextCandidateSlot(*slot);
1324   }
1325 }
1326
1327
1328 MarkCompactCollector::~MarkCompactCollector() {
1329   if (code_flusher_ != NULL) {
1330     delete code_flusher_;
1331     code_flusher_ = NULL;
1332   }
1333 }
1334
1335
1336 static inline HeapObject* ShortCircuitConsString(Object** p) {
1337   // Optimization: If the heap object pointed to by p is a non-internalized
1338   // cons string whose right substring is HEAP->empty_string, update
1339   // it in place to its left substring.  Return the updated value.
1340   //
1341   // Here we assume that if we change *p, we replace it with a heap object
1342   // (i.e., the left substring of a cons string is always a heap object).
1343   //
1344   // The check performed is:
1345   //   object->IsConsString() && !object->IsInternalizedString() &&
1346   //   (ConsString::cast(object)->second() == HEAP->empty_string())
1347   // except the maps for the object and its possible substrings might be
1348   // marked.
1349   HeapObject* object = HeapObject::cast(*p);
1350   if (!FLAG_clever_optimizations) return object;
1351   Map* map = object->map();
1352   InstanceType type = map->instance_type();
1353   if ((type & kShortcutTypeMask) != kShortcutTypeTag) return object;
1354
1355   Object* second = reinterpret_cast<ConsString*>(object)->second();
1356   Heap* heap = map->GetHeap();
1357   if (second != heap->empty_string()) {
1358     return object;
1359   }
1360
1361   // Since we don't have the object's start, it is impossible to update the
1362   // page dirty marks. Therefore, we only replace the string with its left
1363   // substring when page dirty marks do not change.
1364   Object* first = reinterpret_cast<ConsString*>(object)->first();
1365   if (!heap->InNewSpace(object) && heap->InNewSpace(first)) return object;
1366
1367   *p = first;
1368   return HeapObject::cast(first);
1369 }
1370
1371
1372 class MarkCompactMarkingVisitor
1373     : public StaticMarkingVisitor<MarkCompactMarkingVisitor> {
1374  public:
1375   static void ObjectStatsVisitBase(StaticVisitorBase::VisitorId id,
1376                                    Map* map, HeapObject* obj);
1377
1378   static void ObjectStatsCountFixedArray(
1379       FixedArrayBase* fixed_array,
1380       FixedArraySubInstanceType fast_type,
1381       FixedArraySubInstanceType dictionary_type);
1382
1383   template<MarkCompactMarkingVisitor::VisitorId id>
1384   class ObjectStatsTracker {
1385    public:
1386     static inline void Visit(Map* map, HeapObject* obj);
1387   };
1388
1389   static void Initialize();
1390
1391   INLINE(static void VisitPointer(Heap* heap, Object** p)) {
1392     MarkObjectByPointer(heap->mark_compact_collector(), p, p);
1393   }
1394
1395   INLINE(static void VisitPointers(Heap* heap, Object** start, Object** end)) {
1396     // Mark all objects pointed to in [start, end).
1397     const int kMinRangeForMarkingRecursion = 64;
1398     if (end - start >= kMinRangeForMarkingRecursion) {
1399       if (VisitUnmarkedObjects(heap, start, end)) return;
1400       // We are close to a stack overflow, so just mark the objects.
1401     }
1402     MarkCompactCollector* collector = heap->mark_compact_collector();
1403     for (Object** p = start; p < end; p++) {
1404       MarkObjectByPointer(collector, start, p);
1405     }
1406   }
1407
1408   // Marks the object black and pushes it on the marking stack.
1409   INLINE(static void MarkObject(Heap* heap, HeapObject* object)) {
1410     MarkBit mark = Marking::MarkBitFrom(object);
1411     heap->mark_compact_collector()->MarkObject(object, mark);
1412   }
1413
1414   // Marks the object black without pushing it on the marking stack.
1415   // Returns true if object needed marking and false otherwise.
1416   INLINE(static bool MarkObjectWithoutPush(Heap* heap, HeapObject* object)) {
1417     MarkBit mark_bit = Marking::MarkBitFrom(object);
1418     if (!mark_bit.Get()) {
1419       heap->mark_compact_collector()->SetMark(object, mark_bit);
1420       return true;
1421     }
1422     return false;
1423   }
1424
1425   // Mark object pointed to by p.
1426   INLINE(static void MarkObjectByPointer(MarkCompactCollector* collector,
1427                                          Object** anchor_slot,
1428                                          Object** p)) {
1429     if (!(*p)->IsHeapObject()) return;
1430     HeapObject* object = ShortCircuitConsString(p);
1431     collector->RecordSlot(anchor_slot, p, object);
1432     MarkBit mark = Marking::MarkBitFrom(object);
1433     collector->MarkObject(object, mark);
1434   }
1435
1436
1437   // Visit an unmarked object.
1438   INLINE(static void VisitUnmarkedObject(MarkCompactCollector* collector,
1439                                          HeapObject* obj)) {
1440 #ifdef DEBUG
1441     ASSERT(collector->heap()->Contains(obj));
1442     ASSERT(!collector->heap()->mark_compact_collector()->IsMarked(obj));
1443 #endif
1444     Map* map = obj->map();
1445     Heap* heap = obj->GetHeap();
1446     MarkBit mark = Marking::MarkBitFrom(obj);
1447     heap->mark_compact_collector()->SetMark(obj, mark);
1448     // Mark the map pointer and the body.
1449     MarkBit map_mark = Marking::MarkBitFrom(map);
1450     heap->mark_compact_collector()->MarkObject(map, map_mark);
1451     IterateBody(map, obj);
1452   }
1453
1454   // Visit all unmarked objects pointed to by [start, end).
1455   // Returns false if the operation fails (lack of stack space).
1456   INLINE(static bool VisitUnmarkedObjects(Heap* heap,
1457                                           Object** start,
1458                                           Object** end)) {
1459     // Return false is we are close to the stack limit.
1460     StackLimitCheck check(heap->isolate());
1461     if (check.HasOverflowed()) return false;
1462
1463     MarkCompactCollector* collector = heap->mark_compact_collector();
1464     // Visit the unmarked objects.
1465     for (Object** p = start; p < end; p++) {
1466       Object* o = *p;
1467       if (!o->IsHeapObject()) continue;
1468       collector->RecordSlot(start, p, o);
1469       HeapObject* obj = HeapObject::cast(o);
1470       MarkBit mark = Marking::MarkBitFrom(obj);
1471       if (mark.Get()) continue;
1472       VisitUnmarkedObject(collector, obj);
1473     }
1474     return true;
1475   }
1476
1477  private:
1478   template<int id>
1479   static inline void TrackObjectStatsAndVisit(Map* map, HeapObject* obj);
1480
1481   // Code flushing support.
1482
1483   static const int kRegExpCodeThreshold = 5;
1484
1485   static void UpdateRegExpCodeAgeAndFlush(Heap* heap,
1486                                           JSRegExp* re,
1487                                           bool is_ascii) {
1488     // Make sure that the fixed array is in fact initialized on the RegExp.
1489     // We could potentially trigger a GC when initializing the RegExp.
1490     if (HeapObject::cast(re->data())->map()->instance_type() !=
1491             FIXED_ARRAY_TYPE) return;
1492
1493     // Make sure this is a RegExp that actually contains code.
1494     if (re->TypeTag() != JSRegExp::IRREGEXP) return;
1495
1496     Object* code = re->DataAt(JSRegExp::code_index(is_ascii));
1497     if (!code->IsSmi() &&
1498         HeapObject::cast(code)->map()->instance_type() == CODE_TYPE) {
1499       // Save a copy that can be reinstated if we need the code again.
1500       re->SetDataAt(JSRegExp::saved_code_index(is_ascii), code);
1501
1502       // Saving a copy might create a pointer into compaction candidate
1503       // that was not observed by marker.  This might happen if JSRegExp data
1504       // was marked through the compilation cache before marker reached JSRegExp
1505       // object.
1506       FixedArray* data = FixedArray::cast(re->data());
1507       Object** slot = data->data_start() + JSRegExp::saved_code_index(is_ascii);
1508       heap->mark_compact_collector()->
1509           RecordSlot(slot, slot, code);
1510
1511       // Set a number in the 0-255 range to guarantee no smi overflow.
1512       re->SetDataAt(JSRegExp::code_index(is_ascii),
1513                     Smi::FromInt(heap->sweep_generation() & 0xff));
1514     } else if (code->IsSmi()) {
1515       int value = Smi::cast(code)->value();
1516       // The regexp has not been compiled yet or there was a compilation error.
1517       if (value == JSRegExp::kUninitializedValue ||
1518           value == JSRegExp::kCompilationErrorValue) {
1519         return;
1520       }
1521
1522       // Check if we should flush now.
1523       if (value == ((heap->sweep_generation() - kRegExpCodeThreshold) & 0xff)) {
1524         re->SetDataAt(JSRegExp::code_index(is_ascii),
1525                       Smi::FromInt(JSRegExp::kUninitializedValue));
1526         re->SetDataAt(JSRegExp::saved_code_index(is_ascii),
1527                       Smi::FromInt(JSRegExp::kUninitializedValue));
1528       }
1529     }
1530   }
1531
1532
1533   // Works by setting the current sweep_generation (as a smi) in the
1534   // code object place in the data array of the RegExp and keeps a copy
1535   // around that can be reinstated if we reuse the RegExp before flushing.
1536   // If we did not use the code for kRegExpCodeThreshold mark sweep GCs
1537   // we flush the code.
1538   static void VisitRegExpAndFlushCode(Map* map, HeapObject* object) {
1539     Heap* heap = map->GetHeap();
1540     MarkCompactCollector* collector = heap->mark_compact_collector();
1541     if (!collector->is_code_flushing_enabled()) {
1542       VisitJSRegExp(map, object);
1543       return;
1544     }
1545     JSRegExp* re = reinterpret_cast<JSRegExp*>(object);
1546     // Flush code or set age on both ASCII and two byte code.
1547     UpdateRegExpCodeAgeAndFlush(heap, re, true);
1548     UpdateRegExpCodeAgeAndFlush(heap, re, false);
1549     // Visit the fields of the RegExp, including the updated FixedArray.
1550     VisitJSRegExp(map, object);
1551   }
1552
1553   static VisitorDispatchTable<Callback> non_count_table_;
1554 };
1555
1556
1557 void MarkCompactMarkingVisitor::ObjectStatsCountFixedArray(
1558     FixedArrayBase* fixed_array,
1559     FixedArraySubInstanceType fast_type,
1560     FixedArraySubInstanceType dictionary_type) {
1561   Heap* heap = fixed_array->map()->GetHeap();
1562   if (fixed_array->map() != heap->fixed_cow_array_map() &&
1563       fixed_array->map() != heap->fixed_double_array_map() &&
1564       fixed_array != heap->empty_fixed_array()) {
1565     if (fixed_array->IsDictionary()) {
1566       heap->RecordFixedArraySubTypeStats(dictionary_type,
1567                                          fixed_array->Size());
1568     } else {
1569       heap->RecordFixedArraySubTypeStats(fast_type,
1570                                          fixed_array->Size());
1571     }
1572   }
1573 }
1574
1575
1576 void MarkCompactMarkingVisitor::ObjectStatsVisitBase(
1577     MarkCompactMarkingVisitor::VisitorId id, Map* map, HeapObject* obj) {
1578   Heap* heap = map->GetHeap();
1579   int object_size = obj->Size();
1580   heap->RecordObjectStats(map->instance_type(), object_size);
1581   non_count_table_.GetVisitorById(id)(map, obj);
1582   if (obj->IsJSObject()) {
1583     JSObject* object = JSObject::cast(obj);
1584     ObjectStatsCountFixedArray(object->elements(),
1585                                DICTIONARY_ELEMENTS_SUB_TYPE,
1586                                FAST_ELEMENTS_SUB_TYPE);
1587     ObjectStatsCountFixedArray(object->properties(),
1588                                DICTIONARY_PROPERTIES_SUB_TYPE,
1589                                FAST_PROPERTIES_SUB_TYPE);
1590   }
1591 }
1592
1593
1594 template<MarkCompactMarkingVisitor::VisitorId id>
1595 void MarkCompactMarkingVisitor::ObjectStatsTracker<id>::Visit(
1596     Map* map, HeapObject* obj) {
1597   ObjectStatsVisitBase(id, map, obj);
1598 }
1599
1600
1601 template<>
1602 class MarkCompactMarkingVisitor::ObjectStatsTracker<
1603     MarkCompactMarkingVisitor::kVisitMap> {
1604  public:
1605   static inline void Visit(Map* map, HeapObject* obj) {
1606     Heap* heap = map->GetHeap();
1607     Map* map_obj = Map::cast(obj);
1608     ASSERT(map->instance_type() == MAP_TYPE);
1609     DescriptorArray* array = map_obj->instance_descriptors();
1610     if (map_obj->owns_descriptors() &&
1611         array != heap->empty_descriptor_array()) {
1612       int fixed_array_size = array->Size();
1613       heap->RecordFixedArraySubTypeStats(DESCRIPTOR_ARRAY_SUB_TYPE,
1614                                          fixed_array_size);
1615     }
1616     if (map_obj->HasTransitionArray()) {
1617       int fixed_array_size = map_obj->transitions()->Size();
1618       heap->RecordFixedArraySubTypeStats(TRANSITION_ARRAY_SUB_TYPE,
1619                                          fixed_array_size);
1620     }
1621     if (map_obj->has_code_cache()) {
1622       CodeCache* cache = CodeCache::cast(map_obj->code_cache());
1623       heap->RecordFixedArraySubTypeStats(MAP_CODE_CACHE_SUB_TYPE,
1624                                          cache->default_cache()->Size());
1625       if (!cache->normal_type_cache()->IsUndefined()) {
1626         heap->RecordFixedArraySubTypeStats(
1627             MAP_CODE_CACHE_SUB_TYPE,
1628             FixedArray::cast(cache->normal_type_cache())->Size());
1629       }
1630     }
1631     ObjectStatsVisitBase(kVisitMap, map, obj);
1632   }
1633 };
1634
1635
1636 template<>
1637 class MarkCompactMarkingVisitor::ObjectStatsTracker<
1638     MarkCompactMarkingVisitor::kVisitCode> {
1639  public:
1640   static inline void Visit(Map* map, HeapObject* obj) {
1641     Heap* heap = map->GetHeap();
1642     int object_size = obj->Size();
1643     ASSERT(map->instance_type() == CODE_TYPE);
1644     Code* code_obj = Code::cast(obj);
1645     heap->RecordCodeSubTypeStats(code_obj->kind(), code_obj->GetRawAge(),
1646                                  object_size);
1647     ObjectStatsVisitBase(kVisitCode, map, obj);
1648   }
1649 };
1650
1651
1652 template<>
1653 class MarkCompactMarkingVisitor::ObjectStatsTracker<
1654     MarkCompactMarkingVisitor::kVisitSharedFunctionInfo> {
1655  public:
1656   static inline void Visit(Map* map, HeapObject* obj) {
1657     Heap* heap = map->GetHeap();
1658     SharedFunctionInfo* sfi = SharedFunctionInfo::cast(obj);
1659     if (sfi->scope_info() != heap->empty_fixed_array()) {
1660       heap->RecordFixedArraySubTypeStats(
1661           SCOPE_INFO_SUB_TYPE,
1662           FixedArray::cast(sfi->scope_info())->Size());
1663     }
1664     ObjectStatsVisitBase(kVisitSharedFunctionInfo, map, obj);
1665   }
1666 };
1667
1668
1669 template<>
1670 class MarkCompactMarkingVisitor::ObjectStatsTracker<
1671     MarkCompactMarkingVisitor::kVisitFixedArray> {
1672  public:
1673   static inline void Visit(Map* map, HeapObject* obj) {
1674     Heap* heap = map->GetHeap();
1675     FixedArray* fixed_array = FixedArray::cast(obj);
1676     if (fixed_array == heap->string_table()) {
1677       heap->RecordFixedArraySubTypeStats(
1678           STRING_TABLE_SUB_TYPE,
1679           fixed_array->Size());
1680     }
1681     ObjectStatsVisitBase(kVisitFixedArray, map, obj);
1682   }
1683 };
1684
1685
1686 void MarkCompactMarkingVisitor::Initialize() {
1687   StaticMarkingVisitor<MarkCompactMarkingVisitor>::Initialize();
1688
1689   table_.Register(kVisitJSRegExp,
1690                   &VisitRegExpAndFlushCode);
1691
1692   if (FLAG_track_gc_object_stats) {
1693     // Copy the visitor table to make call-through possible.
1694     non_count_table_.CopyFrom(&table_);
1695 #define VISITOR_ID_COUNT_FUNCTION(id)                                   \
1696     table_.Register(kVisit##id, ObjectStatsTracker<kVisit##id>::Visit);
1697     VISITOR_ID_LIST(VISITOR_ID_COUNT_FUNCTION)
1698 #undef VISITOR_ID_COUNT_FUNCTION
1699   }
1700 }
1701
1702
1703 VisitorDispatchTable<MarkCompactMarkingVisitor::Callback>
1704     MarkCompactMarkingVisitor::non_count_table_;
1705
1706
1707 class CodeMarkingVisitor : public ThreadVisitor {
1708  public:
1709   explicit CodeMarkingVisitor(MarkCompactCollector* collector)
1710       : collector_(collector) {}
1711
1712   void VisitThread(Isolate* isolate, ThreadLocalTop* top) {
1713     collector_->PrepareThreadForCodeFlushing(isolate, top);
1714   }
1715
1716  private:
1717   MarkCompactCollector* collector_;
1718 };
1719
1720
1721 class SharedFunctionInfoMarkingVisitor : public ObjectVisitor {
1722  public:
1723   explicit SharedFunctionInfoMarkingVisitor(MarkCompactCollector* collector)
1724       : collector_(collector) {}
1725
1726   void VisitPointers(Object** start, Object** end) {
1727     for (Object** p = start; p < end; p++) VisitPointer(p);
1728   }
1729
1730   void VisitPointer(Object** slot) {
1731     Object* obj = *slot;
1732     if (obj->IsSharedFunctionInfo()) {
1733       SharedFunctionInfo* shared = reinterpret_cast<SharedFunctionInfo*>(obj);
1734       MarkBit shared_mark = Marking::MarkBitFrom(shared);
1735       MarkBit code_mark = Marking::MarkBitFrom(shared->code());
1736       collector_->MarkObject(shared->code(), code_mark);
1737       collector_->MarkObject(shared, shared_mark);
1738     }
1739   }
1740
1741  private:
1742   MarkCompactCollector* collector_;
1743 };
1744
1745
1746 void MarkCompactCollector::PrepareThreadForCodeFlushing(Isolate* isolate,
1747                                                         ThreadLocalTop* top) {
1748   for (StackFrameIterator it(isolate, top); !it.done(); it.Advance()) {
1749     // Note: for the frame that has a pending lazy deoptimization
1750     // StackFrame::unchecked_code will return a non-optimized code object for
1751     // the outermost function and StackFrame::LookupCode will return
1752     // actual optimized code object.
1753     StackFrame* frame = it.frame();
1754     Code* code = frame->unchecked_code();
1755     MarkBit code_mark = Marking::MarkBitFrom(code);
1756     MarkObject(code, code_mark);
1757     if (frame->is_optimized()) {
1758       MarkCompactMarkingVisitor::MarkInlinedFunctionsCode(heap(),
1759                                                           frame->LookupCode());
1760     }
1761   }
1762 }
1763
1764
1765 void MarkCompactCollector::PrepareForCodeFlushing() {
1766   // Enable code flushing for non-incremental cycles.
1767   if (FLAG_flush_code && !FLAG_flush_code_incrementally) {
1768     EnableCodeFlushing(!was_marked_incrementally_);
1769   }
1770
1771   // If code flushing is disabled, there is no need to prepare for it.
1772   if (!is_code_flushing_enabled()) return;
1773
1774   // Ensure that empty descriptor array is marked. Method MarkDescriptorArray
1775   // relies on it being marked before any other descriptor array.
1776   HeapObject* descriptor_array = heap()->empty_descriptor_array();
1777   MarkBit descriptor_array_mark = Marking::MarkBitFrom(descriptor_array);
1778   MarkObject(descriptor_array, descriptor_array_mark);
1779
1780   // Make sure we are not referencing the code from the stack.
1781   ASSERT(this == heap()->mark_compact_collector());
1782   PrepareThreadForCodeFlushing(heap()->isolate(),
1783                                heap()->isolate()->thread_local_top());
1784
1785   // Iterate the archived stacks in all threads to check if
1786   // the code is referenced.
1787   CodeMarkingVisitor code_marking_visitor(this);
1788   heap()->isolate()->thread_manager()->IterateArchivedThreads(
1789       &code_marking_visitor);
1790
1791   SharedFunctionInfoMarkingVisitor visitor(this);
1792   heap()->isolate()->compilation_cache()->IterateFunctions(&visitor);
1793   heap()->isolate()->handle_scope_implementer()->Iterate(&visitor);
1794
1795   ProcessMarkingDeque();
1796 }
1797
1798
1799 // Visitor class for marking heap roots.
1800 class RootMarkingVisitor : public ObjectVisitor {
1801  public:
1802   explicit RootMarkingVisitor(Heap* heap)
1803     : collector_(heap->mark_compact_collector()) { }
1804
1805   void VisitPointer(Object** p) {
1806     MarkObjectByPointer(p);
1807   }
1808
1809   void VisitPointers(Object** start, Object** end) {
1810     for (Object** p = start; p < end; p++) MarkObjectByPointer(p);
1811   }
1812
1813   // Skip the weak next code link in a code object, which is visited in
1814   // ProcessTopOptimizedFrame.
1815   void VisitNextCodeLink(Object** p) { }
1816
1817  private:
1818   void MarkObjectByPointer(Object** p) {
1819     if (!(*p)->IsHeapObject()) return;
1820
1821     // Replace flat cons strings in place.
1822     HeapObject* object = ShortCircuitConsString(p);
1823     MarkBit mark_bit = Marking::MarkBitFrom(object);
1824     if (mark_bit.Get()) return;
1825
1826     Map* map = object->map();
1827     // Mark the object.
1828     collector_->SetMark(object, mark_bit);
1829
1830     // Mark the map pointer and body, and push them on the marking stack.
1831     MarkBit map_mark = Marking::MarkBitFrom(map);
1832     collector_->MarkObject(map, map_mark);
1833     MarkCompactMarkingVisitor::IterateBody(map, object);
1834
1835     // Mark all the objects reachable from the map and body.  May leave
1836     // overflowed objects in the heap.
1837     collector_->EmptyMarkingDeque();
1838   }
1839
1840   MarkCompactCollector* collector_;
1841 };
1842
1843
1844 // Helper class for pruning the string table.
1845 template<bool finalize_external_strings>
1846 class StringTableCleaner : public ObjectVisitor {
1847  public:
1848   explicit StringTableCleaner(Heap* heap)
1849     : heap_(heap), pointers_removed_(0) { }
1850
1851   virtual void VisitPointers(Object** start, Object** end) {
1852     // Visit all HeapObject pointers in [start, end).
1853     for (Object** p = start; p < end; p++) {
1854       Object* o = *p;
1855       if (o->IsHeapObject() &&
1856           !Marking::MarkBitFrom(HeapObject::cast(o)).Get()) {
1857         if (finalize_external_strings) {
1858           ASSERT(o->IsExternalString());
1859           heap_->FinalizeExternalString(String::cast(*p));
1860         } else {
1861           pointers_removed_++;
1862         }
1863         // Set the entry to the_hole_value (as deleted).
1864         *p = heap_->the_hole_value();
1865       }
1866     }
1867   }
1868
1869   int PointersRemoved() {
1870     ASSERT(!finalize_external_strings);
1871     return pointers_removed_;
1872   }
1873
1874  private:
1875   Heap* heap_;
1876   int pointers_removed_;
1877 };
1878
1879
1880 typedef StringTableCleaner<false> InternalizedStringTableCleaner;
1881 typedef StringTableCleaner<true> ExternalStringTableCleaner;
1882
1883
1884 // Implementation of WeakObjectRetainer for mark compact GCs. All marked objects
1885 // are retained.
1886 class MarkCompactWeakObjectRetainer : public WeakObjectRetainer {
1887  public:
1888   virtual Object* RetainAs(Object* object) {
1889     if (Marking::MarkBitFrom(HeapObject::cast(object)).Get()) {
1890       return object;
1891     } else if (object->IsAllocationSite() &&
1892                !(AllocationSite::cast(object)->IsZombie())) {
1893       // "dead" AllocationSites need to live long enough for a traversal of new
1894       // space. These sites get a one-time reprieve.
1895       AllocationSite* site = AllocationSite::cast(object);
1896       site->MarkZombie();
1897       site->GetHeap()->mark_compact_collector()->MarkAllocationSite(site);
1898       return object;
1899     } else {
1900       return NULL;
1901     }
1902   }
1903 };
1904
1905
1906 // Fill the marking stack with overflowed objects returned by the given
1907 // iterator.  Stop when the marking stack is filled or the end of the space
1908 // is reached, whichever comes first.
1909 template<class T>
1910 static void DiscoverGreyObjectsWithIterator(Heap* heap,
1911                                             MarkingDeque* marking_deque,
1912                                             T* it) {
1913   // The caller should ensure that the marking stack is initially not full,
1914   // so that we don't waste effort pointlessly scanning for objects.
1915   ASSERT(!marking_deque->IsFull());
1916
1917   Map* filler_map = heap->one_pointer_filler_map();
1918   for (HeapObject* object = it->Next();
1919        object != NULL;
1920        object = it->Next()) {
1921     MarkBit markbit = Marking::MarkBitFrom(object);
1922     if ((object->map() != filler_map) && Marking::IsGrey(markbit)) {
1923       Marking::GreyToBlack(markbit);
1924       MemoryChunk::IncrementLiveBytesFromGC(object->address(), object->Size());
1925       marking_deque->PushBlack(object);
1926       if (marking_deque->IsFull()) return;
1927     }
1928   }
1929 }
1930
1931
1932 static inline int MarkWordToObjectStarts(uint32_t mark_bits, int* starts);
1933
1934
1935 static void DiscoverGreyObjectsOnPage(MarkingDeque* marking_deque,
1936                                       MemoryChunk* p) {
1937   ASSERT(!marking_deque->IsFull());
1938   ASSERT(strcmp(Marking::kWhiteBitPattern, "00") == 0);
1939   ASSERT(strcmp(Marking::kBlackBitPattern, "10") == 0);
1940   ASSERT(strcmp(Marking::kGreyBitPattern, "11") == 0);
1941   ASSERT(strcmp(Marking::kImpossibleBitPattern, "01") == 0);
1942
1943   for (MarkBitCellIterator it(p); !it.Done(); it.Advance()) {
1944     Address cell_base = it.CurrentCellBase();
1945     MarkBit::CellType* cell = it.CurrentCell();
1946
1947     const MarkBit::CellType current_cell = *cell;
1948     if (current_cell == 0) continue;
1949
1950     MarkBit::CellType grey_objects;
1951     if (it.HasNext()) {
1952       const MarkBit::CellType next_cell = *(cell+1);
1953       grey_objects = current_cell &
1954           ((current_cell >> 1) | (next_cell << (Bitmap::kBitsPerCell - 1)));
1955     } else {
1956       grey_objects = current_cell & (current_cell >> 1);
1957     }
1958
1959     int offset = 0;
1960     while (grey_objects != 0) {
1961       int trailing_zeros = CompilerIntrinsics::CountTrailingZeros(grey_objects);
1962       grey_objects >>= trailing_zeros;
1963       offset += trailing_zeros;
1964       MarkBit markbit(cell, 1 << offset, false);
1965       ASSERT(Marking::IsGrey(markbit));
1966       Marking::GreyToBlack(markbit);
1967       Address addr = cell_base + offset * kPointerSize;
1968       HeapObject* object = HeapObject::FromAddress(addr);
1969       MemoryChunk::IncrementLiveBytesFromGC(object->address(), object->Size());
1970       marking_deque->PushBlack(object);
1971       if (marking_deque->IsFull()) return;
1972       offset += 2;
1973       grey_objects >>= 2;
1974     }
1975
1976     grey_objects >>= (Bitmap::kBitsPerCell - 1);
1977   }
1978 }
1979
1980
1981 int MarkCompactCollector::DiscoverAndPromoteBlackObjectsOnPage(
1982     NewSpace* new_space,
1983     NewSpacePage* p) {
1984   ASSERT(strcmp(Marking::kWhiteBitPattern, "00") == 0);
1985   ASSERT(strcmp(Marking::kBlackBitPattern, "10") == 0);
1986   ASSERT(strcmp(Marking::kGreyBitPattern, "11") == 0);
1987   ASSERT(strcmp(Marking::kImpossibleBitPattern, "01") == 0);
1988
1989   MarkBit::CellType* cells = p->markbits()->cells();
1990   int survivors_size = 0;
1991
1992   for (MarkBitCellIterator it(p); !it.Done(); it.Advance()) {
1993     Address cell_base = it.CurrentCellBase();
1994     MarkBit::CellType* cell = it.CurrentCell();
1995
1996     MarkBit::CellType current_cell = *cell;
1997     if (current_cell == 0) continue;
1998
1999     int offset = 0;
2000     while (current_cell != 0) {
2001       int trailing_zeros = CompilerIntrinsics::CountTrailingZeros(current_cell);
2002       current_cell >>= trailing_zeros;
2003       offset += trailing_zeros;
2004       Address address = cell_base + offset * kPointerSize;
2005       HeapObject* object = HeapObject::FromAddress(address);
2006
2007       int size = object->Size();
2008       survivors_size += size;
2009
2010       Heap::UpdateAllocationSiteFeedback(object, Heap::RECORD_SCRATCHPAD_SLOT);
2011
2012       offset++;
2013       current_cell >>= 1;
2014       // Aggressively promote young survivors to the old space.
2015       if (TryPromoteObject(object, size)) {
2016         continue;
2017       }
2018
2019       // Promotion failed. Just migrate object to another semispace.
2020       AllocationResult allocation = new_space->AllocateRaw(size);
2021       if (allocation.IsRetry()) {
2022         if (!new_space->AddFreshPage()) {
2023           // Shouldn't happen. We are sweeping linearly, and to-space
2024           // has the same number of pages as from-space, so there is
2025           // always room.
2026           UNREACHABLE();
2027         }
2028         allocation = new_space->AllocateRaw(size);
2029         ASSERT(!allocation.IsRetry());
2030       }
2031       Object* target = allocation.ToObjectChecked();
2032
2033       MigrateObject(HeapObject::cast(target),
2034                     object,
2035                     size,
2036                     NEW_SPACE);
2037       heap()->IncrementSemiSpaceCopiedObjectSize(size);
2038     }
2039     *cells = 0;
2040   }
2041   return survivors_size;
2042 }
2043
2044
2045 static void DiscoverGreyObjectsInSpace(Heap* heap,
2046                                        MarkingDeque* marking_deque,
2047                                        PagedSpace* space) {
2048   if (!space->was_swept_conservatively()) {
2049     HeapObjectIterator it(space);
2050     DiscoverGreyObjectsWithIterator(heap, marking_deque, &it);
2051   } else {
2052     PageIterator it(space);
2053     while (it.has_next()) {
2054       Page* p = it.next();
2055       DiscoverGreyObjectsOnPage(marking_deque, p);
2056       if (marking_deque->IsFull()) return;
2057     }
2058   }
2059 }
2060
2061
2062 static void DiscoverGreyObjectsInNewSpace(Heap* heap,
2063                                           MarkingDeque* marking_deque) {
2064   NewSpace* space = heap->new_space();
2065   NewSpacePageIterator it(space->bottom(), space->top());
2066   while (it.has_next()) {
2067     NewSpacePage* page = it.next();
2068     DiscoverGreyObjectsOnPage(marking_deque, page);
2069     if (marking_deque->IsFull()) return;
2070   }
2071 }
2072
2073
2074 bool MarkCompactCollector::IsUnmarkedHeapObject(Object** p) {
2075   Object* o = *p;
2076   if (!o->IsHeapObject()) return false;
2077   HeapObject* heap_object = HeapObject::cast(o);
2078   MarkBit mark = Marking::MarkBitFrom(heap_object);
2079   return !mark.Get();
2080 }
2081
2082
2083 bool MarkCompactCollector::IsUnmarkedHeapObjectWithHeap(Heap* heap,
2084                                                         Object** p) {
2085   Object* o = *p;
2086   ASSERT(o->IsHeapObject());
2087   HeapObject* heap_object = HeapObject::cast(o);
2088   MarkBit mark = Marking::MarkBitFrom(heap_object);
2089   return !mark.Get();
2090 }
2091
2092
2093 void MarkCompactCollector::MarkStringTable(RootMarkingVisitor* visitor) {
2094   StringTable* string_table = heap()->string_table();
2095   // Mark the string table itself.
2096   MarkBit string_table_mark = Marking::MarkBitFrom(string_table);
2097   if (!string_table_mark.Get()) {
2098     // String table could have already been marked by visiting the handles list.
2099     SetMark(string_table, string_table_mark);
2100   }
2101   // Explicitly mark the prefix.
2102   string_table->IteratePrefix(visitor);
2103   ProcessMarkingDeque();
2104 }
2105
2106
2107 void MarkCompactCollector::MarkAllocationSite(AllocationSite* site) {
2108   MarkBit mark_bit = Marking::MarkBitFrom(site);
2109   SetMark(site, mark_bit);
2110 }
2111
2112
2113 void MarkCompactCollector::MarkRoots(RootMarkingVisitor* visitor) {
2114   // Mark the heap roots including global variables, stack variables,
2115   // etc., and all objects reachable from them.
2116   heap()->IterateStrongRoots(visitor, VISIT_ONLY_STRONG);
2117
2118   // Handle the string table specially.
2119   MarkStringTable(visitor);
2120
2121   MarkWeakObjectToCodeTable();
2122
2123   // There may be overflowed objects in the heap.  Visit them now.
2124   while (marking_deque_.overflowed()) {
2125     RefillMarkingDeque();
2126     EmptyMarkingDeque();
2127   }
2128 }
2129
2130
2131 void MarkCompactCollector::MarkImplicitRefGroups() {
2132   List<ImplicitRefGroup*>* ref_groups =
2133       isolate()->global_handles()->implicit_ref_groups();
2134
2135   int last = 0;
2136   for (int i = 0; i < ref_groups->length(); i++) {
2137     ImplicitRefGroup* entry = ref_groups->at(i);
2138     ASSERT(entry != NULL);
2139
2140     if (!IsMarked(*entry->parent)) {
2141       (*ref_groups)[last++] = entry;
2142       continue;
2143     }
2144
2145     Object*** children = entry->children;
2146     // A parent object is marked, so mark all child heap objects.
2147     for (size_t j = 0; j < entry->length; ++j) {
2148       if ((*children[j])->IsHeapObject()) {
2149         HeapObject* child = HeapObject::cast(*children[j]);
2150         MarkBit mark = Marking::MarkBitFrom(child);
2151         MarkObject(child, mark);
2152       }
2153     }
2154
2155     // Once the entire group has been marked, dispose it because it's
2156     // not needed anymore.
2157     delete entry;
2158   }
2159   ref_groups->Rewind(last);
2160 }
2161
2162
2163 void MarkCompactCollector::MarkWeakObjectToCodeTable() {
2164   HeapObject* weak_object_to_code_table =
2165       HeapObject::cast(heap()->weak_object_to_code_table());
2166   if (!IsMarked(weak_object_to_code_table)) {
2167     MarkBit mark = Marking::MarkBitFrom(weak_object_to_code_table);
2168     SetMark(weak_object_to_code_table, mark);
2169   }
2170 }
2171
2172
2173 // Mark all objects reachable from the objects on the marking stack.
2174 // Before: the marking stack contains zero or more heap object pointers.
2175 // After: the marking stack is empty, and all objects reachable from the
2176 // marking stack have been marked, or are overflowed in the heap.
2177 void MarkCompactCollector::EmptyMarkingDeque() {
2178   while (!marking_deque_.IsEmpty()) {
2179     HeapObject* object = marking_deque_.Pop();
2180     ASSERT(object->IsHeapObject());
2181     ASSERT(heap()->Contains(object));
2182     ASSERT(Marking::IsBlack(Marking::MarkBitFrom(object)));
2183
2184     Map* map = object->map();
2185     MarkBit map_mark = Marking::MarkBitFrom(map);
2186     MarkObject(map, map_mark);
2187
2188     MarkCompactMarkingVisitor::IterateBody(map, object);
2189   }
2190 }
2191
2192
2193 // Sweep the heap for overflowed objects, clear their overflow bits, and
2194 // push them on the marking stack.  Stop early if the marking stack fills
2195 // before sweeping completes.  If sweeping completes, there are no remaining
2196 // overflowed objects in the heap so the overflow flag on the markings stack
2197 // is cleared.
2198 void MarkCompactCollector::RefillMarkingDeque() {
2199   ASSERT(marking_deque_.overflowed());
2200
2201   DiscoverGreyObjectsInNewSpace(heap(), &marking_deque_);
2202   if (marking_deque_.IsFull()) return;
2203
2204   DiscoverGreyObjectsInSpace(heap(),
2205                              &marking_deque_,
2206                              heap()->old_pointer_space());
2207   if (marking_deque_.IsFull()) return;
2208
2209   DiscoverGreyObjectsInSpace(heap(),
2210                              &marking_deque_,
2211                              heap()->old_data_space());
2212   if (marking_deque_.IsFull()) return;
2213
2214   DiscoverGreyObjectsInSpace(heap(),
2215                              &marking_deque_,
2216                              heap()->code_space());
2217   if (marking_deque_.IsFull()) return;
2218
2219   DiscoverGreyObjectsInSpace(heap(),
2220                              &marking_deque_,
2221                              heap()->map_space());
2222   if (marking_deque_.IsFull()) return;
2223
2224   DiscoverGreyObjectsInSpace(heap(),
2225                              &marking_deque_,
2226                              heap()->cell_space());
2227   if (marking_deque_.IsFull()) return;
2228
2229   DiscoverGreyObjectsInSpace(heap(),
2230                              &marking_deque_,
2231                              heap()->property_cell_space());
2232   if (marking_deque_.IsFull()) return;
2233
2234   LargeObjectIterator lo_it(heap()->lo_space());
2235   DiscoverGreyObjectsWithIterator(heap(),
2236                                   &marking_deque_,
2237                                   &lo_it);
2238   if (marking_deque_.IsFull()) return;
2239
2240   marking_deque_.ClearOverflowed();
2241 }
2242
2243
2244 // Mark all objects reachable (transitively) from objects on the marking
2245 // stack.  Before: the marking stack contains zero or more heap object
2246 // pointers.  After: the marking stack is empty and there are no overflowed
2247 // objects in the heap.
2248 void MarkCompactCollector::ProcessMarkingDeque() {
2249   EmptyMarkingDeque();
2250   while (marking_deque_.overflowed()) {
2251     RefillMarkingDeque();
2252     EmptyMarkingDeque();
2253   }
2254 }
2255
2256
2257 // Mark all objects reachable (transitively) from objects on the marking
2258 // stack including references only considered in the atomic marking pause.
2259 void MarkCompactCollector::ProcessEphemeralMarking(ObjectVisitor* visitor) {
2260   bool work_to_do = true;
2261   ASSERT(marking_deque_.IsEmpty());
2262   while (work_to_do) {
2263     isolate()->global_handles()->IterateObjectGroups(
2264         visitor, &IsUnmarkedHeapObjectWithHeap);
2265     MarkImplicitRefGroups();
2266     ProcessWeakCollections();
2267     work_to_do = !marking_deque_.IsEmpty();
2268     ProcessMarkingDeque();
2269   }
2270 }
2271
2272
2273 void MarkCompactCollector::ProcessTopOptimizedFrame(ObjectVisitor* visitor) {
2274   for (StackFrameIterator it(isolate(), isolate()->thread_local_top());
2275        !it.done(); it.Advance()) {
2276     if (it.frame()->type() == StackFrame::JAVA_SCRIPT) {
2277       return;
2278     }
2279     if (it.frame()->type() == StackFrame::OPTIMIZED) {
2280       Code* code = it.frame()->LookupCode();
2281       if (!code->CanDeoptAt(it.frame()->pc())) {
2282         code->CodeIterateBody(visitor);
2283       }
2284       ProcessMarkingDeque();
2285       return;
2286     }
2287   }
2288 }
2289
2290
2291 void MarkCompactCollector::MarkLiveObjects() {
2292   GCTracer::Scope gc_scope(tracer_, GCTracer::Scope::MC_MARK);
2293   // The recursive GC marker detects when it is nearing stack overflow,
2294   // and switches to a different marking system.  JS interrupts interfere
2295   // with the C stack limit check.
2296   PostponeInterruptsScope postpone(isolate());
2297
2298   bool incremental_marking_overflowed = false;
2299   IncrementalMarking* incremental_marking = heap_->incremental_marking();
2300   if (was_marked_incrementally_) {
2301     // Finalize the incremental marking and check whether we had an overflow.
2302     // Both markers use grey color to mark overflowed objects so
2303     // non-incremental marker can deal with them as if overflow
2304     // occured during normal marking.
2305     // But incremental marker uses a separate marking deque
2306     // so we have to explicitly copy its overflow state.
2307     incremental_marking->Finalize();
2308     incremental_marking_overflowed =
2309         incremental_marking->marking_deque()->overflowed();
2310     incremental_marking->marking_deque()->ClearOverflowed();
2311   } else {
2312     // Abort any pending incremental activities e.g. incremental sweeping.
2313     incremental_marking->Abort();
2314   }
2315
2316 #ifdef DEBUG
2317   ASSERT(state_ == PREPARE_GC);
2318   state_ = MARK_LIVE_OBJECTS;
2319 #endif
2320   // The to space contains live objects, a page in from space is used as a
2321   // marking stack.
2322   Address marking_deque_start = heap()->new_space()->FromSpacePageLow();
2323   Address marking_deque_end = heap()->new_space()->FromSpacePageHigh();
2324   if (FLAG_force_marking_deque_overflows) {
2325     marking_deque_end = marking_deque_start + 64 * kPointerSize;
2326   }
2327   marking_deque_.Initialize(marking_deque_start,
2328                             marking_deque_end);
2329   ASSERT(!marking_deque_.overflowed());
2330
2331   if (incremental_marking_overflowed) {
2332     // There are overflowed objects left in the heap after incremental marking.
2333     marking_deque_.SetOverflowed();
2334   }
2335
2336   PrepareForCodeFlushing();
2337
2338   if (was_marked_incrementally_) {
2339     // There is no write barrier on cells so we have to scan them now at the end
2340     // of the incremental marking.
2341     {
2342       HeapObjectIterator cell_iterator(heap()->cell_space());
2343       HeapObject* cell;
2344       while ((cell = cell_iterator.Next()) != NULL) {
2345         ASSERT(cell->IsCell());
2346         if (IsMarked(cell)) {
2347           int offset = Cell::kValueOffset;
2348           MarkCompactMarkingVisitor::VisitPointer(
2349               heap(),
2350               reinterpret_cast<Object**>(cell->address() + offset));
2351         }
2352       }
2353     }
2354     {
2355       HeapObjectIterator js_global_property_cell_iterator(
2356           heap()->property_cell_space());
2357       HeapObject* cell;
2358       while ((cell = js_global_property_cell_iterator.Next()) != NULL) {
2359         ASSERT(cell->IsPropertyCell());
2360         if (IsMarked(cell)) {
2361           MarkCompactMarkingVisitor::VisitPropertyCell(cell->map(), cell);
2362         }
2363       }
2364     }
2365   }
2366
2367   RootMarkingVisitor root_visitor(heap());
2368   MarkRoots(&root_visitor);
2369
2370   ProcessTopOptimizedFrame(&root_visitor);
2371
2372   // The objects reachable from the roots are marked, yet unreachable
2373   // objects are unmarked.  Mark objects reachable due to host
2374   // application specific logic or through Harmony weak maps.
2375   ProcessEphemeralMarking(&root_visitor);
2376
2377   // The objects reachable from the roots, weak maps or object groups
2378   // are marked, yet unreachable objects are unmarked.  Mark objects
2379   // reachable only from weak global handles.
2380   //
2381   // First we identify nonlive weak handles and mark them as pending
2382   // destruction.
2383   heap()->isolate()->global_handles()->IdentifyWeakHandles(
2384       &IsUnmarkedHeapObject);
2385   // Then we mark the objects and process the transitive closure.
2386   heap()->isolate()->global_handles()->IterateWeakRoots(&root_visitor);
2387   while (marking_deque_.overflowed()) {
2388     RefillMarkingDeque();
2389     EmptyMarkingDeque();
2390   }
2391
2392   // Repeat host application specific and Harmony weak maps marking to
2393   // mark unmarked objects reachable from the weak roots.
2394   ProcessEphemeralMarking(&root_visitor);
2395
2396   AfterMarking();
2397 }
2398
2399
2400 void MarkCompactCollector::AfterMarking() {
2401   // Object literal map caches reference strings (cache keys) and maps
2402   // (cache values). At this point still useful maps have already been
2403   // marked. Mark the keys for the alive values before we process the
2404   // string table.
2405   ProcessMapCaches();
2406
2407   // Prune the string table removing all strings only pointed to by the
2408   // string table.  Cannot use string_table() here because the string
2409   // table is marked.
2410   StringTable* string_table = heap()->string_table();
2411   InternalizedStringTableCleaner internalized_visitor(heap());
2412   string_table->IterateElements(&internalized_visitor);
2413   string_table->ElementsRemoved(internalized_visitor.PointersRemoved());
2414
2415   ExternalStringTableCleaner external_visitor(heap());
2416   heap()->external_string_table_.Iterate(&external_visitor);
2417   heap()->external_string_table_.CleanUp();
2418
2419   // Process the weak references.
2420   MarkCompactWeakObjectRetainer mark_compact_object_retainer;
2421   heap()->ProcessWeakReferences(&mark_compact_object_retainer);
2422
2423   // Remove object groups after marking phase.
2424   heap()->isolate()->global_handles()->RemoveObjectGroups();
2425   heap()->isolate()->global_handles()->RemoveImplicitRefGroups();
2426
2427   // Flush code from collected candidates.
2428   if (is_code_flushing_enabled()) {
2429     code_flusher_->ProcessCandidates();
2430     // If incremental marker does not support code flushing, we need to
2431     // disable it before incremental marking steps for next cycle.
2432     if (FLAG_flush_code && !FLAG_flush_code_incrementally) {
2433       EnableCodeFlushing(false);
2434     }
2435   }
2436
2437   if (FLAG_track_gc_object_stats) {
2438     heap()->CheckpointObjectStats();
2439   }
2440 }
2441
2442
2443 void MarkCompactCollector::ProcessMapCaches() {
2444   Object* raw_context = heap()->native_contexts_list();
2445   while (raw_context != heap()->undefined_value()) {
2446     Context* context = reinterpret_cast<Context*>(raw_context);
2447     if (IsMarked(context)) {
2448       HeapObject* raw_map_cache =
2449           HeapObject::cast(context->get(Context::MAP_CACHE_INDEX));
2450       // A map cache may be reachable from the stack. In this case
2451       // it's already transitively marked and it's too late to clean
2452       // up its parts.
2453       if (!IsMarked(raw_map_cache) &&
2454           raw_map_cache != heap()->undefined_value()) {
2455         MapCache* map_cache = reinterpret_cast<MapCache*>(raw_map_cache);
2456         int existing_elements = map_cache->NumberOfElements();
2457         int used_elements = 0;
2458         for (int i = MapCache::kElementsStartIndex;
2459              i < map_cache->length();
2460              i += MapCache::kEntrySize) {
2461           Object* raw_key = map_cache->get(i);
2462           if (raw_key == heap()->undefined_value() ||
2463               raw_key == heap()->the_hole_value()) continue;
2464           STATIC_ASSERT(MapCache::kEntrySize == 2);
2465           Object* raw_map = map_cache->get(i + 1);
2466           if (raw_map->IsHeapObject() && IsMarked(raw_map)) {
2467             ++used_elements;
2468           } else {
2469             // Delete useless entries with unmarked maps.
2470             ASSERT(raw_map->IsMap());
2471             map_cache->set_the_hole(i);
2472             map_cache->set_the_hole(i + 1);
2473           }
2474         }
2475         if (used_elements == 0) {
2476           context->set(Context::MAP_CACHE_INDEX, heap()->undefined_value());
2477         } else {
2478           // Note: we don't actually shrink the cache here to avoid
2479           // extra complexity during GC. We rely on subsequent cache
2480           // usages (EnsureCapacity) to do this.
2481           map_cache->ElementsRemoved(existing_elements - used_elements);
2482           MarkBit map_cache_markbit = Marking::MarkBitFrom(map_cache);
2483           MarkObject(map_cache, map_cache_markbit);
2484         }
2485       }
2486     }
2487     // Move to next element in the list.
2488     raw_context = context->get(Context::NEXT_CONTEXT_LINK);
2489   }
2490   ProcessMarkingDeque();
2491 }
2492
2493
2494 void MarkCompactCollector::ClearNonLiveReferences() {
2495   // Iterate over the map space, setting map transitions that go from
2496   // a marked map to an unmarked map to null transitions.  This action
2497   // is carried out only on maps of JSObjects and related subtypes.
2498   HeapObjectIterator map_iterator(heap()->map_space());
2499   for (HeapObject* obj = map_iterator.Next();
2500        obj != NULL;
2501        obj = map_iterator.Next()) {
2502     Map* map = Map::cast(obj);
2503
2504     if (!map->CanTransition()) continue;
2505
2506     MarkBit map_mark = Marking::MarkBitFrom(map);
2507     ClearNonLivePrototypeTransitions(map);
2508     ClearNonLiveMapTransitions(map, map_mark);
2509
2510     if (map_mark.Get()) {
2511       ClearNonLiveDependentCode(map->dependent_code());
2512     } else {
2513       ClearDependentCode(map->dependent_code());
2514       map->set_dependent_code(DependentCode::cast(heap()->empty_fixed_array()));
2515     }
2516   }
2517
2518   // Iterate over property cell space, removing dependent code that is not
2519   // otherwise kept alive by strong references.
2520   HeapObjectIterator cell_iterator(heap_->property_cell_space());
2521   for (HeapObject* cell = cell_iterator.Next();
2522        cell != NULL;
2523        cell = cell_iterator.Next()) {
2524     if (IsMarked(cell)) {
2525       ClearNonLiveDependentCode(PropertyCell::cast(cell)->dependent_code());
2526     }
2527   }
2528
2529   // Iterate over allocation sites, removing dependent code that is not
2530   // otherwise kept alive by strong references.
2531   Object* undefined = heap()->undefined_value();
2532   for (Object* site = heap()->allocation_sites_list();
2533        site != undefined;
2534        site = AllocationSite::cast(site)->weak_next()) {
2535     if (IsMarked(site)) {
2536       ClearNonLiveDependentCode(AllocationSite::cast(site)->dependent_code());
2537     }
2538   }
2539
2540   if (heap_->weak_object_to_code_table()->IsHashTable()) {
2541     WeakHashTable* table =
2542         WeakHashTable::cast(heap_->weak_object_to_code_table());
2543     uint32_t capacity = table->Capacity();
2544     for (uint32_t i = 0; i < capacity; i++) {
2545       uint32_t key_index = table->EntryToIndex(i);
2546       Object* key = table->get(key_index);
2547       if (!table->IsKey(key)) continue;
2548       uint32_t value_index = table->EntryToValueIndex(i);
2549       Object* value = table->get(value_index);
2550       if (key->IsCell() && !IsMarked(key)) {
2551         Cell* cell = Cell::cast(key);
2552         Object* object = cell->value();
2553         if (IsMarked(object)) {
2554           MarkBit mark = Marking::MarkBitFrom(cell);
2555           SetMark(cell, mark);
2556           Object** value_slot = HeapObject::RawField(cell, Cell::kValueOffset);
2557           RecordSlot(value_slot, value_slot, *value_slot);
2558         }
2559       }
2560       if (IsMarked(key)) {
2561         if (!IsMarked(value)) {
2562           HeapObject* obj = HeapObject::cast(value);
2563           MarkBit mark = Marking::MarkBitFrom(obj);
2564           SetMark(obj, mark);
2565         }
2566         ClearNonLiveDependentCode(DependentCode::cast(value));
2567       } else {
2568         ClearDependentCode(DependentCode::cast(value));
2569         table->set(key_index, heap_->the_hole_value());
2570         table->set(value_index, heap_->the_hole_value());
2571         table->ElementRemoved();
2572       }
2573     }
2574   }
2575 }
2576
2577
2578 void MarkCompactCollector::ClearNonLivePrototypeTransitions(Map* map) {
2579   int number_of_transitions = map->NumberOfProtoTransitions();
2580   FixedArray* prototype_transitions = map->GetPrototypeTransitions();
2581
2582   int new_number_of_transitions = 0;
2583   const int header = Map::kProtoTransitionHeaderSize;
2584   const int proto_offset = header + Map::kProtoTransitionPrototypeOffset;
2585   const int map_offset = header + Map::kProtoTransitionMapOffset;
2586   const int step = Map::kProtoTransitionElementsPerEntry;
2587   for (int i = 0; i < number_of_transitions; i++) {
2588     Object* prototype = prototype_transitions->get(proto_offset + i * step);
2589     Object* cached_map = prototype_transitions->get(map_offset + i * step);
2590     if (IsMarked(prototype) && IsMarked(cached_map)) {
2591       ASSERT(!prototype->IsUndefined());
2592       int proto_index = proto_offset + new_number_of_transitions * step;
2593       int map_index = map_offset + new_number_of_transitions * step;
2594       if (new_number_of_transitions != i) {
2595         prototype_transitions->set(
2596             proto_index,
2597             prototype,
2598             UPDATE_WRITE_BARRIER);
2599         prototype_transitions->set(
2600             map_index,
2601             cached_map,
2602             SKIP_WRITE_BARRIER);
2603       }
2604       Object** slot = prototype_transitions->RawFieldOfElementAt(proto_index);
2605       RecordSlot(slot, slot, prototype);
2606       new_number_of_transitions++;
2607     }
2608   }
2609
2610   if (new_number_of_transitions != number_of_transitions) {
2611     map->SetNumberOfProtoTransitions(new_number_of_transitions);
2612   }
2613
2614   // Fill slots that became free with undefined value.
2615   for (int i = new_number_of_transitions * step;
2616        i < number_of_transitions * step;
2617        i++) {
2618     prototype_transitions->set_undefined(header + i);
2619   }
2620 }
2621
2622
2623 void MarkCompactCollector::ClearNonLiveMapTransitions(Map* map,
2624                                                       MarkBit map_mark) {
2625   Object* potential_parent = map->GetBackPointer();
2626   if (!potential_parent->IsMap()) return;
2627   Map* parent = Map::cast(potential_parent);
2628
2629   // Follow back pointer, check whether we are dealing with a map transition
2630   // from a live map to a dead path and in case clear transitions of parent.
2631   bool current_is_alive = map_mark.Get();
2632   bool parent_is_alive = Marking::MarkBitFrom(parent).Get();
2633   if (!current_is_alive && parent_is_alive) {
2634     parent->ClearNonLiveTransitions(heap());
2635   }
2636 }
2637
2638
2639 void MarkCompactCollector::ClearDependentICList(Object* head) {
2640   Object* current = head;
2641   Object* undefined = heap()->undefined_value();
2642   while (current != undefined) {
2643     Code* code = Code::cast(current);
2644     if (IsMarked(code)) {
2645       ASSERT(code->is_weak_stub());
2646       IC::InvalidateMaps(code);
2647     }
2648     current = code->next_code_link();
2649     code->set_next_code_link(undefined);
2650   }
2651 }
2652
2653
2654 void MarkCompactCollector::ClearDependentCode(
2655     DependentCode* entries) {
2656   DisallowHeapAllocation no_allocation;
2657   DependentCode::GroupStartIndexes starts(entries);
2658   int number_of_entries = starts.number_of_entries();
2659   if (number_of_entries == 0) return;
2660   int g = DependentCode::kWeakICGroup;
2661   if (starts.at(g) != starts.at(g + 1)) {
2662     int i = starts.at(g);
2663     ASSERT(i + 1 == starts.at(g + 1));
2664     Object* head = entries->object_at(i);
2665     ClearDependentICList(head);
2666   }
2667   g = DependentCode::kWeakCodeGroup;
2668   for (int i = starts.at(g); i < starts.at(g + 1); i++) {
2669     // If the entry is compilation info then the map must be alive,
2670     // and ClearDependentCode shouldn't be called.
2671     ASSERT(entries->is_code_at(i));
2672     Code* code = entries->code_at(i);
2673     if (IsMarked(code) && !code->marked_for_deoptimization()) {
2674       code->set_marked_for_deoptimization(true);
2675       code->InvalidateEmbeddedObjects();
2676       have_code_to_deoptimize_ = true;
2677     }
2678   }
2679   for (int i = 0; i < number_of_entries; i++) {
2680     entries->clear_at(i);
2681   }
2682 }
2683
2684
2685 int MarkCompactCollector::ClearNonLiveDependentCodeInGroup(
2686     DependentCode* entries, int group, int start, int end, int new_start) {
2687   int survived = 0;
2688   if (group == DependentCode::kWeakICGroup) {
2689     // Dependent weak IC stubs form a linked list and only the head is stored
2690     // in the dependent code array.
2691     if (start != end) {
2692       ASSERT(start + 1 == end);
2693       Object* old_head = entries->object_at(start);
2694       MarkCompactWeakObjectRetainer retainer;
2695       Object* head = VisitWeakList<Code>(heap(), old_head, &retainer);
2696       entries->set_object_at(new_start, head);
2697       Object** slot = entries->slot_at(new_start);
2698       RecordSlot(slot, slot, head);
2699       // We do not compact this group even if the head is undefined,
2700       // more dependent ICs are likely to be added later.
2701       survived = 1;
2702     }
2703   } else {
2704     for (int i = start; i < end; i++) {
2705       Object* obj = entries->object_at(i);
2706       ASSERT(obj->IsCode() || IsMarked(obj));
2707       if (IsMarked(obj) &&
2708           (!obj->IsCode() || !WillBeDeoptimized(Code::cast(obj)))) {
2709         if (new_start + survived != i) {
2710           entries->set_object_at(new_start + survived, obj);
2711         }
2712         Object** slot = entries->slot_at(new_start + survived);
2713         RecordSlot(slot, slot, obj);
2714         survived++;
2715       }
2716     }
2717   }
2718   entries->set_number_of_entries(
2719       static_cast<DependentCode::DependencyGroup>(group), survived);
2720   return survived;
2721 }
2722
2723
2724 void MarkCompactCollector::ClearNonLiveDependentCode(DependentCode* entries) {
2725   DisallowHeapAllocation no_allocation;
2726   DependentCode::GroupStartIndexes starts(entries);
2727   int number_of_entries = starts.number_of_entries();
2728   if (number_of_entries == 0) return;
2729   int new_number_of_entries = 0;
2730   // Go through all groups, remove dead codes and compact.
2731   for (int g = 0; g < DependentCode::kGroupCount; g++) {
2732     int survived = ClearNonLiveDependentCodeInGroup(
2733         entries, g, starts.at(g), starts.at(g + 1), new_number_of_entries);
2734     new_number_of_entries += survived;
2735   }
2736   for (int i = new_number_of_entries; i < number_of_entries; i++) {
2737     entries->clear_at(i);
2738   }
2739 }
2740
2741
2742 void MarkCompactCollector::ProcessWeakCollections() {
2743   GCTracer::Scope gc_scope(tracer_, GCTracer::Scope::MC_WEAKCOLLECTION_PROCESS);
2744   Object* weak_collection_obj = heap()->encountered_weak_collections();
2745   while (weak_collection_obj != Smi::FromInt(0)) {
2746     JSWeakCollection* weak_collection =
2747         reinterpret_cast<JSWeakCollection*>(weak_collection_obj);
2748     ASSERT(MarkCompactCollector::IsMarked(weak_collection));
2749     if (weak_collection->table()->IsHashTable()) {
2750       ObjectHashTable* table = ObjectHashTable::cast(weak_collection->table());
2751       Object** anchor = reinterpret_cast<Object**>(table->address());
2752       for (int i = 0; i < table->Capacity(); i++) {
2753         if (MarkCompactCollector::IsMarked(HeapObject::cast(table->KeyAt(i)))) {
2754           Object** key_slot =
2755               table->RawFieldOfElementAt(ObjectHashTable::EntryToIndex(i));
2756           RecordSlot(anchor, key_slot, *key_slot);
2757           Object** value_slot =
2758               table->RawFieldOfElementAt(ObjectHashTable::EntryToValueIndex(i));
2759           MarkCompactMarkingVisitor::MarkObjectByPointer(
2760               this, anchor, value_slot);
2761         }
2762       }
2763     }
2764     weak_collection_obj = weak_collection->next();
2765   }
2766 }
2767
2768
2769 void MarkCompactCollector::ClearWeakCollections() {
2770   GCTracer::Scope gc_scope(tracer_, GCTracer::Scope::MC_WEAKCOLLECTION_CLEAR);
2771   Object* weak_collection_obj = heap()->encountered_weak_collections();
2772   while (weak_collection_obj != Smi::FromInt(0)) {
2773     JSWeakCollection* weak_collection =
2774         reinterpret_cast<JSWeakCollection*>(weak_collection_obj);
2775     ASSERT(MarkCompactCollector::IsMarked(weak_collection));
2776     if (weak_collection->table()->IsHashTable()) {
2777       ObjectHashTable* table = ObjectHashTable::cast(weak_collection->table());
2778       for (int i = 0; i < table->Capacity(); i++) {
2779         HeapObject* key = HeapObject::cast(table->KeyAt(i));
2780         if (!MarkCompactCollector::IsMarked(key)) {
2781           table->RemoveEntry(i);
2782         }
2783       }
2784     }
2785     weak_collection_obj = weak_collection->next();
2786     weak_collection->set_next(heap()->undefined_value());
2787   }
2788   heap()->set_encountered_weak_collections(Smi::FromInt(0));
2789 }
2790
2791
2792 // We scavange new space simultaneously with sweeping. This is done in two
2793 // passes.
2794 //
2795 // The first pass migrates all alive objects from one semispace to another or
2796 // promotes them to old space.  Forwarding address is written directly into
2797 // first word of object without any encoding.  If object is dead we write
2798 // NULL as a forwarding address.
2799 //
2800 // The second pass updates pointers to new space in all spaces.  It is possible
2801 // to encounter pointers to dead new space objects during traversal of pointers
2802 // to new space.  We should clear them to avoid encountering them during next
2803 // pointer iteration.  This is an issue if the store buffer overflows and we
2804 // have to scan the entire old space, including dead objects, looking for
2805 // pointers to new space.
2806 void MarkCompactCollector::MigrateObject(HeapObject* dst,
2807                                          HeapObject* src,
2808                                          int size,
2809                                          AllocationSpace dest) {
2810   Address dst_addr = dst->address();
2811   Address src_addr = src->address();
2812   HeapProfiler* heap_profiler = heap()->isolate()->heap_profiler();
2813   if (heap_profiler->is_tracking_object_moves()) {
2814     heap_profiler->ObjectMoveEvent(src_addr, dst_addr, size);
2815   }
2816   ASSERT(heap()->AllowedToBeMigrated(src, dest));
2817   ASSERT(dest != LO_SPACE && size <= Page::kMaxRegularHeapObjectSize);
2818   if (dest == OLD_POINTER_SPACE) {
2819     Address src_slot = src_addr;
2820     Address dst_slot = dst_addr;
2821     ASSERT(IsAligned(size, kPointerSize));
2822
2823     for (int remaining = size / kPointerSize; remaining > 0; remaining--) {
2824       Object* value = Memory::Object_at(src_slot);
2825
2826       Memory::Object_at(dst_slot) = value;
2827
2828       if (heap_->InNewSpace(value)) {
2829         heap_->store_buffer()->Mark(dst_slot);
2830       } else if (value->IsHeapObject() && IsOnEvacuationCandidate(value)) {
2831         SlotsBuffer::AddTo(&slots_buffer_allocator_,
2832                            &migration_slots_buffer_,
2833                            reinterpret_cast<Object**>(dst_slot),
2834                            SlotsBuffer::IGNORE_OVERFLOW);
2835       }
2836
2837       src_slot += kPointerSize;
2838       dst_slot += kPointerSize;
2839     }
2840
2841     if (compacting_ && dst->IsJSFunction()) {
2842       Address code_entry_slot = dst_addr + JSFunction::kCodeEntryOffset;
2843       Address code_entry = Memory::Address_at(code_entry_slot);
2844
2845       if (Page::FromAddress(code_entry)->IsEvacuationCandidate()) {
2846         SlotsBuffer::AddTo(&slots_buffer_allocator_,
2847                            &migration_slots_buffer_,
2848                            SlotsBuffer::CODE_ENTRY_SLOT,
2849                            code_entry_slot,
2850                            SlotsBuffer::IGNORE_OVERFLOW);
2851       }
2852     } else if (compacting_ && dst->IsConstantPoolArray()) {
2853       ConstantPoolArray* array = ConstantPoolArray::cast(dst);
2854       ConstantPoolArray::Iterator code_iter(array, ConstantPoolArray::CODE_PTR);
2855       while (!code_iter.is_finished()) {
2856         Address code_entry_slot =
2857             dst_addr + array->OffsetOfElementAt(code_iter.next_index());
2858         Address code_entry = Memory::Address_at(code_entry_slot);
2859
2860         if (Page::FromAddress(code_entry)->IsEvacuationCandidate()) {
2861           SlotsBuffer::AddTo(&slots_buffer_allocator_,
2862                              &migration_slots_buffer_,
2863                              SlotsBuffer::CODE_ENTRY_SLOT,
2864                              code_entry_slot,
2865                              SlotsBuffer::IGNORE_OVERFLOW);
2866         }
2867       }
2868     }
2869   } else if (dest == CODE_SPACE) {
2870     PROFILE(isolate(), CodeMoveEvent(src_addr, dst_addr));
2871     heap()->MoveBlock(dst_addr, src_addr, size);
2872     SlotsBuffer::AddTo(&slots_buffer_allocator_,
2873                        &migration_slots_buffer_,
2874                        SlotsBuffer::RELOCATED_CODE_OBJECT,
2875                        dst_addr,
2876                        SlotsBuffer::IGNORE_OVERFLOW);
2877     Code::cast(dst)->Relocate(dst_addr - src_addr);
2878   } else {
2879     ASSERT(dest == OLD_DATA_SPACE || dest == NEW_SPACE);
2880     heap()->MoveBlock(dst_addr, src_addr, size);
2881   }
2882   Memory::Address_at(src_addr) = dst_addr;
2883 }
2884
2885
2886 // Visitor for updating pointers from live objects in old spaces to new space.
2887 // It does not expect to encounter pointers to dead objects.
2888 class PointersUpdatingVisitor: public ObjectVisitor {
2889  public:
2890   explicit PointersUpdatingVisitor(Heap* heap) : heap_(heap) { }
2891
2892   void VisitPointer(Object** p) {
2893     UpdatePointer(p);
2894   }
2895
2896   void VisitPointers(Object** start, Object** end) {
2897     for (Object** p = start; p < end; p++) UpdatePointer(p);
2898   }
2899
2900   void VisitEmbeddedPointer(RelocInfo* rinfo) {
2901     ASSERT(rinfo->rmode() == RelocInfo::EMBEDDED_OBJECT);
2902     Object* target = rinfo->target_object();
2903     Object* old_target = target;
2904     VisitPointer(&target);
2905     // Avoid unnecessary changes that might unnecessary flush the instruction
2906     // cache.
2907     if (target != old_target) {
2908       rinfo->set_target_object(target);
2909     }
2910   }
2911
2912   void VisitCodeTarget(RelocInfo* rinfo) {
2913     ASSERT(RelocInfo::IsCodeTarget(rinfo->rmode()));
2914     Object* target = Code::GetCodeFromTargetAddress(rinfo->target_address());
2915     Object* old_target = target;
2916     VisitPointer(&target);
2917     if (target != old_target) {
2918       rinfo->set_target_address(Code::cast(target)->instruction_start());
2919     }
2920   }
2921
2922   void VisitCodeAgeSequence(RelocInfo* rinfo) {
2923     ASSERT(RelocInfo::IsCodeAgeSequence(rinfo->rmode()));
2924     Object* stub = rinfo->code_age_stub();
2925     ASSERT(stub != NULL);
2926     VisitPointer(&stub);
2927     if (stub != rinfo->code_age_stub()) {
2928       rinfo->set_code_age_stub(Code::cast(stub));
2929     }
2930   }
2931
2932   void VisitDebugTarget(RelocInfo* rinfo) {
2933     ASSERT((RelocInfo::IsJSReturn(rinfo->rmode()) &&
2934             rinfo->IsPatchedReturnSequence()) ||
2935            (RelocInfo::IsDebugBreakSlot(rinfo->rmode()) &&
2936             rinfo->IsPatchedDebugBreakSlotSequence()));
2937     Object* target = Code::GetCodeFromTargetAddress(rinfo->call_address());
2938     VisitPointer(&target);
2939     rinfo->set_call_address(Code::cast(target)->instruction_start());
2940   }
2941
2942   static inline void UpdateSlot(Heap* heap, Object** slot) {
2943     Object* obj = *slot;
2944
2945     if (!obj->IsHeapObject()) return;
2946
2947     HeapObject* heap_obj = HeapObject::cast(obj);
2948
2949     MapWord map_word = heap_obj->map_word();
2950     if (map_word.IsForwardingAddress()) {
2951       ASSERT(heap->InFromSpace(heap_obj) ||
2952              MarkCompactCollector::IsOnEvacuationCandidate(heap_obj));
2953       HeapObject* target = map_word.ToForwardingAddress();
2954       *slot = target;
2955       ASSERT(!heap->InFromSpace(target) &&
2956              !MarkCompactCollector::IsOnEvacuationCandidate(target));
2957     }
2958   }
2959
2960  private:
2961   inline void UpdatePointer(Object** p) {
2962     UpdateSlot(heap_, p);
2963   }
2964
2965   Heap* heap_;
2966 };
2967
2968
2969 static void UpdatePointer(HeapObject** address, HeapObject* object) {
2970   Address new_addr = Memory::Address_at(object->address());
2971
2972   // The new space sweep will overwrite the map word of dead objects
2973   // with NULL. In this case we do not need to transfer this entry to
2974   // the store buffer which we are rebuilding.
2975   // We perform the pointer update with a no barrier compare-and-swap. The
2976   // compare and swap may fail in the case where the pointer update tries to
2977   // update garbage memory which was concurrently accessed by the sweeper.
2978   if (new_addr != NULL) {
2979     base::NoBarrier_CompareAndSwap(
2980         reinterpret_cast<base::AtomicWord*>(address),
2981         reinterpret_cast<base::AtomicWord>(object),
2982         reinterpret_cast<base::AtomicWord>(HeapObject::FromAddress(new_addr)));
2983   } else {
2984     // We have to zap this pointer, because the store buffer may overflow later,
2985     // and then we have to scan the entire heap and we don't want to find
2986     // spurious newspace pointers in the old space.
2987     // TODO(mstarzinger): This was changed to a sentinel value to track down
2988     // rare crashes, change it back to Smi::FromInt(0) later.
2989     base::NoBarrier_CompareAndSwap(
2990         reinterpret_cast<base::AtomicWord*>(address),
2991         reinterpret_cast<base::AtomicWord>(object),
2992         reinterpret_cast<base::AtomicWord>(Smi::FromInt(0x0f100d00 >> 1)));
2993   }
2994 }
2995
2996
2997 static String* UpdateReferenceInExternalStringTableEntry(Heap* heap,
2998                                                          Object** p) {
2999   MapWord map_word = HeapObject::cast(*p)->map_word();
3000
3001   if (map_word.IsForwardingAddress()) {
3002     return String::cast(map_word.ToForwardingAddress());
3003   }
3004
3005   return String::cast(*p);
3006 }
3007
3008
3009 bool MarkCompactCollector::TryPromoteObject(HeapObject* object,
3010                                             int object_size) {
3011   ASSERT(object_size <= Page::kMaxRegularHeapObjectSize);
3012
3013   OldSpace* target_space = heap()->TargetSpace(object);
3014
3015   ASSERT(target_space == heap()->old_pointer_space() ||
3016          target_space == heap()->old_data_space());
3017   HeapObject* target;
3018   AllocationResult allocation = target_space->AllocateRaw(object_size);
3019   if (allocation.To(&target)) {
3020     MigrateObject(target,
3021                   object,
3022                   object_size,
3023                   target_space->identity());
3024     heap()->IncrementPromotedObjectsSize(object_size);
3025     return true;
3026   }
3027
3028   return false;
3029 }
3030
3031
3032 void MarkCompactCollector::EvacuateNewSpace() {
3033   // There are soft limits in the allocation code, designed trigger a mark
3034   // sweep collection by failing allocations.  But since we are already in
3035   // a mark-sweep allocation, there is no sense in trying to trigger one.
3036   AlwaysAllocateScope scope(isolate());
3037
3038   NewSpace* new_space = heap()->new_space();
3039
3040   // Store allocation range before flipping semispaces.
3041   Address from_bottom = new_space->bottom();
3042   Address from_top = new_space->top();
3043
3044   // Flip the semispaces.  After flipping, to space is empty, from space has
3045   // live objects.
3046   new_space->Flip();
3047   new_space->ResetAllocationInfo();
3048
3049   int survivors_size = 0;
3050
3051   // First pass: traverse all objects in inactive semispace, remove marks,
3052   // migrate live objects and write forwarding addresses.  This stage puts
3053   // new entries in the store buffer and may cause some pages to be marked
3054   // scan-on-scavenge.
3055   NewSpacePageIterator it(from_bottom, from_top);
3056   while (it.has_next()) {
3057     NewSpacePage* p = it.next();
3058     survivors_size += DiscoverAndPromoteBlackObjectsOnPage(new_space, p);
3059   }
3060
3061   heap_->IncrementYoungSurvivorsCounter(survivors_size);
3062   new_space->set_age_mark(new_space->top());
3063 }
3064
3065
3066 void MarkCompactCollector::EvacuateLiveObjectsFromPage(Page* p) {
3067   AlwaysAllocateScope always_allocate(isolate());
3068   PagedSpace* space = static_cast<PagedSpace*>(p->owner());
3069   ASSERT(p->IsEvacuationCandidate() && !p->WasSwept());
3070   p->MarkSweptPrecisely();
3071
3072   int offsets[16];
3073
3074   for (MarkBitCellIterator it(p); !it.Done(); it.Advance()) {
3075     Address cell_base = it.CurrentCellBase();
3076     MarkBit::CellType* cell = it.CurrentCell();
3077
3078     if (*cell == 0) continue;
3079
3080     int live_objects = MarkWordToObjectStarts(*cell, offsets);
3081     for (int i = 0; i < live_objects; i++) {
3082       Address object_addr = cell_base + offsets[i] * kPointerSize;
3083       HeapObject* object = HeapObject::FromAddress(object_addr);
3084       ASSERT(Marking::IsBlack(Marking::MarkBitFrom(object)));
3085
3086       int size = object->Size();
3087
3088       HeapObject* target_object;
3089       AllocationResult allocation = space->AllocateRaw(size);
3090       if (!allocation.To(&target_object)) {
3091         // OS refused to give us memory.
3092         V8::FatalProcessOutOfMemory("Evacuation");
3093         return;
3094       }
3095
3096       MigrateObject(target_object, object, size, space->identity());
3097       ASSERT(object->map_word().IsForwardingAddress());
3098     }
3099
3100     // Clear marking bits for current cell.
3101     *cell = 0;
3102   }
3103   p->ResetLiveBytes();
3104 }
3105
3106
3107 void MarkCompactCollector::EvacuatePages() {
3108   int npages = evacuation_candidates_.length();
3109   for (int i = 0; i < npages; i++) {
3110     Page* p = evacuation_candidates_[i];
3111     ASSERT(p->IsEvacuationCandidate() ||
3112            p->IsFlagSet(Page::RESCAN_ON_EVACUATION));
3113     ASSERT(static_cast<int>(p->parallel_sweeping()) ==
3114            MemoryChunk::PARALLEL_SWEEPING_DONE);
3115     if (p->IsEvacuationCandidate()) {
3116       // During compaction we might have to request a new page.
3117       // Check that space still have room for that.
3118       if (static_cast<PagedSpace*>(p->owner())->CanExpand()) {
3119         EvacuateLiveObjectsFromPage(p);
3120       } else {
3121         // Without room for expansion evacuation is not guaranteed to succeed.
3122         // Pessimistically abandon unevacuated pages.
3123         for (int j = i; j < npages; j++) {
3124           Page* page = evacuation_candidates_[j];
3125           slots_buffer_allocator_.DeallocateChain(page->slots_buffer_address());
3126           page->ClearEvacuationCandidate();
3127           page->SetFlag(Page::RESCAN_ON_EVACUATION);
3128         }
3129         return;
3130       }
3131     }
3132   }
3133 }
3134
3135
3136 class EvacuationWeakObjectRetainer : public WeakObjectRetainer {
3137  public:
3138   virtual Object* RetainAs(Object* object) {
3139     if (object->IsHeapObject()) {
3140       HeapObject* heap_object = HeapObject::cast(object);
3141       MapWord map_word = heap_object->map_word();
3142       if (map_word.IsForwardingAddress()) {
3143         return map_word.ToForwardingAddress();
3144       }
3145     }
3146     return object;
3147   }
3148 };
3149
3150
3151 static inline void UpdateSlot(Isolate* isolate,
3152                               ObjectVisitor* v,
3153                               SlotsBuffer::SlotType slot_type,
3154                               Address addr) {
3155   switch (slot_type) {
3156     case SlotsBuffer::CODE_TARGET_SLOT: {
3157       RelocInfo rinfo(addr, RelocInfo::CODE_TARGET, 0, NULL);
3158       rinfo.Visit(isolate, v);
3159       break;
3160     }
3161     case SlotsBuffer::CODE_ENTRY_SLOT: {
3162       v->VisitCodeEntry(addr);
3163       break;
3164     }
3165     case SlotsBuffer::RELOCATED_CODE_OBJECT: {
3166       HeapObject* obj = HeapObject::FromAddress(addr);
3167       Code::cast(obj)->CodeIterateBody(v);
3168       break;
3169     }
3170     case SlotsBuffer::DEBUG_TARGET_SLOT: {
3171       RelocInfo rinfo(addr, RelocInfo::DEBUG_BREAK_SLOT, 0, NULL);
3172       if (rinfo.IsPatchedDebugBreakSlotSequence()) rinfo.Visit(isolate, v);
3173       break;
3174     }
3175     case SlotsBuffer::JS_RETURN_SLOT: {
3176       RelocInfo rinfo(addr, RelocInfo::JS_RETURN, 0, NULL);
3177       if (rinfo.IsPatchedReturnSequence()) rinfo.Visit(isolate, v);
3178       break;
3179     }
3180     case SlotsBuffer::EMBEDDED_OBJECT_SLOT: {
3181       RelocInfo rinfo(addr, RelocInfo::EMBEDDED_OBJECT, 0, NULL);
3182       rinfo.Visit(isolate, v);
3183       break;
3184     }
3185     default:
3186       UNREACHABLE();
3187       break;
3188   }
3189 }
3190
3191
3192 enum SweepingMode {
3193   SWEEP_ONLY,
3194   SWEEP_AND_VISIT_LIVE_OBJECTS
3195 };
3196
3197
3198 enum SkipListRebuildingMode {
3199   REBUILD_SKIP_LIST,
3200   IGNORE_SKIP_LIST
3201 };
3202
3203
3204 enum FreeSpaceTreatmentMode {
3205   IGNORE_FREE_SPACE,
3206   ZAP_FREE_SPACE
3207 };
3208
3209
3210 // Sweep a space precisely.  After this has been done the space can
3211 // be iterated precisely, hitting only the live objects.  Code space
3212 // is always swept precisely because we want to be able to iterate
3213 // over it.  Map space is swept precisely, because it is not compacted.
3214 // Slots in live objects pointing into evacuation candidates are updated
3215 // if requested.
3216 template<SweepingMode sweeping_mode,
3217          SkipListRebuildingMode skip_list_mode,
3218          FreeSpaceTreatmentMode free_space_mode>
3219 static void SweepPrecisely(PagedSpace* space,
3220                            Page* p,
3221                            ObjectVisitor* v) {
3222   ASSERT(!p->IsEvacuationCandidate() && !p->WasSwept());
3223   ASSERT_EQ(skip_list_mode == REBUILD_SKIP_LIST,
3224             space->identity() == CODE_SPACE);
3225   ASSERT((p->skip_list() == NULL) || (skip_list_mode == REBUILD_SKIP_LIST));
3226
3227   double start_time = 0.0;
3228   if (FLAG_print_cumulative_gc_stat) {
3229     start_time = OS::TimeCurrentMillis();
3230   }
3231
3232   p->MarkSweptPrecisely();
3233
3234   Address free_start = p->area_start();
3235   ASSERT(reinterpret_cast<intptr_t>(free_start) % (32 * kPointerSize) == 0);
3236   int offsets[16];
3237
3238   SkipList* skip_list = p->skip_list();
3239   int curr_region = -1;
3240   if ((skip_list_mode == REBUILD_SKIP_LIST) && skip_list) {
3241     skip_list->Clear();
3242   }
3243
3244   for (MarkBitCellIterator it(p); !it.Done(); it.Advance()) {
3245     Address cell_base = it.CurrentCellBase();
3246     MarkBit::CellType* cell = it.CurrentCell();
3247     int live_objects = MarkWordToObjectStarts(*cell, offsets);
3248     int live_index = 0;
3249     for ( ; live_objects != 0; live_objects--) {
3250       Address free_end = cell_base + offsets[live_index++] * kPointerSize;
3251       if (free_end != free_start) {
3252         if (free_space_mode == ZAP_FREE_SPACE) {
3253           memset(free_start, 0xcc, static_cast<int>(free_end - free_start));
3254         }
3255         space->Free(free_start, static_cast<int>(free_end - free_start));
3256 #ifdef ENABLE_GDB_JIT_INTERFACE
3257         if (FLAG_gdbjit && space->identity() == CODE_SPACE) {
3258           GDBJITInterface::RemoveCodeRange(free_start, free_end);
3259         }
3260 #endif
3261       }
3262       HeapObject* live_object = HeapObject::FromAddress(free_end);
3263       ASSERT(Marking::IsBlack(Marking::MarkBitFrom(live_object)));
3264       Map* map = live_object->map();
3265       int size = live_object->SizeFromMap(map);
3266       if (sweeping_mode == SWEEP_AND_VISIT_LIVE_OBJECTS) {
3267         live_object->IterateBody(map->instance_type(), size, v);
3268       }
3269       if ((skip_list_mode == REBUILD_SKIP_LIST) && skip_list != NULL) {
3270         int new_region_start =
3271             SkipList::RegionNumber(free_end);
3272         int new_region_end =
3273             SkipList::RegionNumber(free_end + size - kPointerSize);
3274         if (new_region_start != curr_region ||
3275             new_region_end != curr_region) {
3276           skip_list->AddObject(free_end, size);
3277           curr_region = new_region_end;
3278         }
3279       }
3280       free_start = free_end + size;
3281     }
3282     // Clear marking bits for current cell.
3283     *cell = 0;
3284   }
3285   if (free_start != p->area_end()) {
3286     if (free_space_mode == ZAP_FREE_SPACE) {
3287       memset(free_start, 0xcc, static_cast<int>(p->area_end() - free_start));
3288     }
3289     space->Free(free_start, static_cast<int>(p->area_end() - free_start));
3290 #ifdef ENABLE_GDB_JIT_INTERFACE
3291     if (FLAG_gdbjit && space->identity() == CODE_SPACE) {
3292       GDBJITInterface::RemoveCodeRange(free_start, p->area_end());
3293     }
3294 #endif
3295   }
3296   p->ResetLiveBytes();
3297   if (FLAG_print_cumulative_gc_stat) {
3298     space->heap()->AddSweepingTime(OS::TimeCurrentMillis() - start_time);
3299   }
3300 }
3301
3302
3303 static bool SetMarkBitsUnderInvalidatedCode(Code* code, bool value) {
3304   Page* p = Page::FromAddress(code->address());
3305
3306   if (p->IsEvacuationCandidate() ||
3307       p->IsFlagSet(Page::RESCAN_ON_EVACUATION)) {
3308     return false;
3309   }
3310
3311   Address code_start = code->address();
3312   Address code_end = code_start + code->Size();
3313
3314   uint32_t start_index = MemoryChunk::FastAddressToMarkbitIndex(code_start);
3315   uint32_t end_index =
3316       MemoryChunk::FastAddressToMarkbitIndex(code_end - kPointerSize);
3317
3318   Bitmap* b = p->markbits();
3319
3320   MarkBit start_mark_bit = b->MarkBitFromIndex(start_index);
3321   MarkBit end_mark_bit = b->MarkBitFromIndex(end_index);
3322
3323   MarkBit::CellType* start_cell = start_mark_bit.cell();
3324   MarkBit::CellType* end_cell = end_mark_bit.cell();
3325
3326   if (value) {
3327     MarkBit::CellType start_mask = ~(start_mark_bit.mask() - 1);
3328     MarkBit::CellType end_mask = (end_mark_bit.mask() << 1) - 1;
3329
3330     if (start_cell == end_cell) {
3331       *start_cell |= start_mask & end_mask;
3332     } else {
3333       *start_cell |= start_mask;
3334       for (MarkBit::CellType* cell = start_cell + 1; cell < end_cell; cell++) {
3335         *cell = ~0;
3336       }
3337       *end_cell |= end_mask;
3338     }
3339   } else {
3340     for (MarkBit::CellType* cell = start_cell ; cell <= end_cell; cell++) {
3341       *cell = 0;
3342     }
3343   }
3344
3345   return true;
3346 }
3347
3348
3349 static bool IsOnInvalidatedCodeObject(Address addr) {
3350   // We did not record any slots in large objects thus
3351   // we can safely go to the page from the slot address.
3352   Page* p = Page::FromAddress(addr);
3353
3354   // First check owner's identity because old pointer and old data spaces
3355   // are swept lazily and might still have non-zero mark-bits on some
3356   // pages.
3357   if (p->owner()->identity() != CODE_SPACE) return false;
3358
3359   // In code space only bits on evacuation candidates (but we don't record
3360   // any slots on them) and under invalidated code objects are non-zero.
3361   MarkBit mark_bit =
3362       p->markbits()->MarkBitFromIndex(Page::FastAddressToMarkbitIndex(addr));
3363
3364   return mark_bit.Get();
3365 }
3366
3367
3368 void MarkCompactCollector::InvalidateCode(Code* code) {
3369   if (heap_->incremental_marking()->IsCompacting() &&
3370       !ShouldSkipEvacuationSlotRecording(code)) {
3371     ASSERT(compacting_);
3372
3373     // If the object is white than no slots were recorded on it yet.
3374     MarkBit mark_bit = Marking::MarkBitFrom(code);
3375     if (Marking::IsWhite(mark_bit)) return;
3376
3377     invalidated_code_.Add(code);
3378   }
3379 }
3380
3381
3382 // Return true if the given code is deoptimized or will be deoptimized.
3383 bool MarkCompactCollector::WillBeDeoptimized(Code* code) {
3384   return code->is_optimized_code() && code->marked_for_deoptimization();
3385 }
3386
3387
3388 bool MarkCompactCollector::MarkInvalidatedCode() {
3389   bool code_marked = false;
3390
3391   int length = invalidated_code_.length();
3392   for (int i = 0; i < length; i++) {
3393     Code* code = invalidated_code_[i];
3394
3395     if (SetMarkBitsUnderInvalidatedCode(code, true)) {
3396       code_marked = true;
3397     }
3398   }
3399
3400   return code_marked;
3401 }
3402
3403
3404 void MarkCompactCollector::RemoveDeadInvalidatedCode() {
3405   int length = invalidated_code_.length();
3406   for (int i = 0; i < length; i++) {
3407     if (!IsMarked(invalidated_code_[i])) invalidated_code_[i] = NULL;
3408   }
3409 }
3410
3411
3412 void MarkCompactCollector::ProcessInvalidatedCode(ObjectVisitor* visitor) {
3413   int length = invalidated_code_.length();
3414   for (int i = 0; i < length; i++) {
3415     Code* code = invalidated_code_[i];
3416     if (code != NULL) {
3417       code->Iterate(visitor);
3418       SetMarkBitsUnderInvalidatedCode(code, false);
3419     }
3420   }
3421   invalidated_code_.Rewind(0);
3422 }
3423
3424
3425 void MarkCompactCollector::EvacuateNewSpaceAndCandidates() {
3426   Heap::RelocationLock relocation_lock(heap());
3427
3428   bool code_slots_filtering_required;
3429   { GCTracer::Scope gc_scope(tracer_, GCTracer::Scope::MC_SWEEP_NEWSPACE);
3430     code_slots_filtering_required = MarkInvalidatedCode();
3431     EvacuateNewSpace();
3432   }
3433
3434   { GCTracer::Scope gc_scope(tracer_, GCTracer::Scope::MC_EVACUATE_PAGES);
3435     EvacuatePages();
3436   }
3437
3438   // Second pass: find pointers to new space and update them.
3439   PointersUpdatingVisitor updating_visitor(heap());
3440
3441   { GCTracer::Scope gc_scope(tracer_,
3442                              GCTracer::Scope::MC_UPDATE_NEW_TO_NEW_POINTERS);
3443     // Update pointers in to space.
3444     SemiSpaceIterator to_it(heap()->new_space()->bottom(),
3445                             heap()->new_space()->top());
3446     for (HeapObject* object = to_it.Next();
3447          object != NULL;
3448          object = to_it.Next()) {
3449       Map* map = object->map();
3450       object->IterateBody(map->instance_type(),
3451                           object->SizeFromMap(map),
3452                           &updating_visitor);
3453     }
3454   }
3455
3456   { GCTracer::Scope gc_scope(tracer_,
3457                              GCTracer::Scope::MC_UPDATE_ROOT_TO_NEW_POINTERS);
3458     // Update roots.
3459     heap_->IterateRoots(&updating_visitor, VISIT_ALL_IN_SWEEP_NEWSPACE);
3460   }
3461
3462   { GCTracer::Scope gc_scope(tracer_,
3463                              GCTracer::Scope::MC_UPDATE_OLD_TO_NEW_POINTERS);
3464     StoreBufferRebuildScope scope(heap_,
3465                                   heap_->store_buffer(),
3466                                   &Heap::ScavengeStoreBufferCallback);
3467     heap_->store_buffer()->IteratePointersToNewSpaceAndClearMaps(
3468         &UpdatePointer);
3469   }
3470
3471   { GCTracer::Scope gc_scope(tracer_,
3472                              GCTracer::Scope::MC_UPDATE_POINTERS_TO_EVACUATED);
3473     SlotsBuffer::UpdateSlotsRecordedIn(heap_,
3474                                        migration_slots_buffer_,
3475                                        code_slots_filtering_required);
3476     if (FLAG_trace_fragmentation) {
3477       PrintF("  migration slots buffer: %d\n",
3478              SlotsBuffer::SizeOfChain(migration_slots_buffer_));
3479     }
3480
3481     if (compacting_ && was_marked_incrementally_) {
3482       // It's difficult to filter out slots recorded for large objects.
3483       LargeObjectIterator it(heap_->lo_space());
3484       for (HeapObject* obj = it.Next(); obj != NULL; obj = it.Next()) {
3485         // LargeObjectSpace is not swept yet thus we have to skip
3486         // dead objects explicitly.
3487         if (!IsMarked(obj)) continue;
3488
3489         Page* p = Page::FromAddress(obj->address());
3490         if (p->IsFlagSet(Page::RESCAN_ON_EVACUATION)) {
3491           obj->Iterate(&updating_visitor);
3492           p->ClearFlag(Page::RESCAN_ON_EVACUATION);
3493         }
3494       }
3495     }
3496   }
3497
3498   int npages = evacuation_candidates_.length();
3499   { GCTracer::Scope gc_scope(
3500       tracer_, GCTracer::Scope::MC_UPDATE_POINTERS_BETWEEN_EVACUATED);
3501     for (int i = 0; i < npages; i++) {
3502       Page* p = evacuation_candidates_[i];
3503       ASSERT(p->IsEvacuationCandidate() ||
3504              p->IsFlagSet(Page::RESCAN_ON_EVACUATION));
3505
3506       if (p->IsEvacuationCandidate()) {
3507         SlotsBuffer::UpdateSlotsRecordedIn(heap_,
3508                                            p->slots_buffer(),
3509                                            code_slots_filtering_required);
3510         if (FLAG_trace_fragmentation) {
3511           PrintF("  page %p slots buffer: %d\n",
3512                  reinterpret_cast<void*>(p),
3513                  SlotsBuffer::SizeOfChain(p->slots_buffer()));
3514         }
3515
3516         // Important: skip list should be cleared only after roots were updated
3517         // because root iteration traverses the stack and might have to find
3518         // code objects from non-updated pc pointing into evacuation candidate.
3519         SkipList* list = p->skip_list();
3520         if (list != NULL) list->Clear();
3521       } else {
3522         if (FLAG_gc_verbose) {
3523           PrintF("Sweeping 0x%" V8PRIxPTR " during evacuation.\n",
3524                  reinterpret_cast<intptr_t>(p));
3525         }
3526         PagedSpace* space = static_cast<PagedSpace*>(p->owner());
3527         p->ClearFlag(MemoryChunk::RESCAN_ON_EVACUATION);
3528
3529         switch (space->identity()) {
3530           case OLD_DATA_SPACE:
3531             SweepConservatively<SWEEP_SEQUENTIALLY>(space, NULL, p);
3532             break;
3533           case OLD_POINTER_SPACE:
3534             SweepPrecisely<SWEEP_AND_VISIT_LIVE_OBJECTS,
3535                            IGNORE_SKIP_LIST,
3536                            IGNORE_FREE_SPACE>(
3537                 space, p, &updating_visitor);
3538             break;
3539           case CODE_SPACE:
3540             if (FLAG_zap_code_space) {
3541               SweepPrecisely<SWEEP_AND_VISIT_LIVE_OBJECTS,
3542                              REBUILD_SKIP_LIST,
3543                              ZAP_FREE_SPACE>(
3544                   space, p, &updating_visitor);
3545             } else {
3546               SweepPrecisely<SWEEP_AND_VISIT_LIVE_OBJECTS,
3547                              REBUILD_SKIP_LIST,
3548                              IGNORE_FREE_SPACE>(
3549                   space, p, &updating_visitor);
3550             }
3551             break;
3552           default:
3553             UNREACHABLE();
3554             break;
3555         }
3556       }
3557     }
3558   }
3559
3560   GCTracer::Scope gc_scope(tracer_, GCTracer::Scope::MC_UPDATE_MISC_POINTERS);
3561
3562   // Update pointers from cells.
3563   HeapObjectIterator cell_iterator(heap_->cell_space());
3564   for (HeapObject* cell = cell_iterator.Next();
3565        cell != NULL;
3566        cell = cell_iterator.Next()) {
3567     if (cell->IsCell()) {
3568       Cell::BodyDescriptor::IterateBody(cell, &updating_visitor);
3569     }
3570   }
3571
3572   HeapObjectIterator js_global_property_cell_iterator(
3573       heap_->property_cell_space());
3574   for (HeapObject* cell = js_global_property_cell_iterator.Next();
3575        cell != NULL;
3576        cell = js_global_property_cell_iterator.Next()) {
3577     if (cell->IsPropertyCell()) {
3578       PropertyCell::BodyDescriptor::IterateBody(cell, &updating_visitor);
3579     }
3580   }
3581
3582   heap_->string_table()->Iterate(&updating_visitor);
3583   updating_visitor.VisitPointer(heap_->weak_object_to_code_table_address());
3584   if (heap_->weak_object_to_code_table()->IsHashTable()) {
3585     WeakHashTable* table =
3586         WeakHashTable::cast(heap_->weak_object_to_code_table());
3587     table->Iterate(&updating_visitor);
3588     table->Rehash(heap_->isolate()->factory()->undefined_value());
3589   }
3590
3591   // Update pointers from external string table.
3592   heap_->UpdateReferencesInExternalStringTable(
3593       &UpdateReferenceInExternalStringTableEntry);
3594
3595   EvacuationWeakObjectRetainer evacuation_object_retainer;
3596   heap()->ProcessWeakReferences(&evacuation_object_retainer);
3597
3598   // Visit invalidated code (we ignored all slots on it) and clear mark-bits
3599   // under it.
3600   ProcessInvalidatedCode(&updating_visitor);
3601
3602   heap_->isolate()->inner_pointer_to_code_cache()->Flush();
3603
3604 #ifdef VERIFY_HEAP
3605   if (FLAG_verify_heap) {
3606     VerifyEvacuation(heap_);
3607   }
3608 #endif
3609
3610   slots_buffer_allocator_.DeallocateChain(&migration_slots_buffer_);
3611   ASSERT(migration_slots_buffer_ == NULL);
3612 }
3613
3614
3615 void MarkCompactCollector::MoveEvacuationCandidatesToEndOfPagesList() {
3616   int npages = evacuation_candidates_.length();
3617   for (int i = 0; i < npages; i++) {
3618     Page* p = evacuation_candidates_[i];
3619     if (!p->IsEvacuationCandidate()) continue;
3620     p->Unlink();
3621     PagedSpace* space = static_cast<PagedSpace*>(p->owner());
3622     p->InsertAfter(space->LastPage());
3623   }
3624 }
3625
3626
3627 void MarkCompactCollector::ReleaseEvacuationCandidates() {
3628   int npages = evacuation_candidates_.length();
3629   for (int i = 0; i < npages; i++) {
3630     Page* p = evacuation_candidates_[i];
3631     if (!p->IsEvacuationCandidate()) continue;
3632     PagedSpace* space = static_cast<PagedSpace*>(p->owner());
3633     space->Free(p->area_start(), p->area_size());
3634     p->set_scan_on_scavenge(false);
3635     slots_buffer_allocator_.DeallocateChain(p->slots_buffer_address());
3636     p->ResetLiveBytes();
3637     space->ReleasePage(p);
3638   }
3639   evacuation_candidates_.Rewind(0);
3640   compacting_ = false;
3641   heap()->FreeQueuedChunks();
3642 }
3643
3644
3645 static const int kStartTableEntriesPerLine = 5;
3646 static const int kStartTableLines = 171;
3647 static const int kStartTableInvalidLine = 127;
3648 static const int kStartTableUnusedEntry = 126;
3649
3650 #define _ kStartTableUnusedEntry
3651 #define X kStartTableInvalidLine
3652 // Mark-bit to object start offset table.
3653 //
3654 // The line is indexed by the mark bits in a byte.  The first number on
3655 // the line describes the number of live object starts for the line and the
3656 // other numbers on the line describe the offsets (in words) of the object
3657 // starts.
3658 //
3659 // Since objects are at least 2 words large we don't have entries for two
3660 // consecutive 1 bits.  All entries after 170 have at least 2 consecutive bits.
3661 char kStartTable[kStartTableLines * kStartTableEntriesPerLine] = {
3662   0, _, _, _, _,  // 0
3663   1, 0, _, _, _,  // 1
3664   1, 1, _, _, _,  // 2
3665   X, _, _, _, _,  // 3
3666   1, 2, _, _, _,  // 4
3667   2, 0, 2, _, _,  // 5
3668   X, _, _, _, _,  // 6
3669   X, _, _, _, _,  // 7
3670   1, 3, _, _, _,  // 8
3671   2, 0, 3, _, _,  // 9
3672   2, 1, 3, _, _,  // 10
3673   X, _, _, _, _,  // 11
3674   X, _, _, _, _,  // 12
3675   X, _, _, _, _,  // 13
3676   X, _, _, _, _,  // 14
3677   X, _, _, _, _,  // 15
3678   1, 4, _, _, _,  // 16
3679   2, 0, 4, _, _,  // 17
3680   2, 1, 4, _, _,  // 18
3681   X, _, _, _, _,  // 19
3682   2, 2, 4, _, _,  // 20
3683   3, 0, 2, 4, _,  // 21
3684   X, _, _, _, _,  // 22
3685   X, _, _, _, _,  // 23
3686   X, _, _, _, _,  // 24
3687   X, _, _, _, _,  // 25
3688   X, _, _, _, _,  // 26
3689   X, _, _, _, _,  // 27
3690   X, _, _, _, _,  // 28
3691   X, _, _, _, _,  // 29
3692   X, _, _, _, _,  // 30
3693   X, _, _, _, _,  // 31
3694   1, 5, _, _, _,  // 32
3695   2, 0, 5, _, _,  // 33
3696   2, 1, 5, _, _,  // 34
3697   X, _, _, _, _,  // 35
3698   2, 2, 5, _, _,  // 36
3699   3, 0, 2, 5, _,  // 37
3700   X, _, _, _, _,  // 38
3701   X, _, _, _, _,  // 39
3702   2, 3, 5, _, _,  // 40
3703   3, 0, 3, 5, _,  // 41
3704   3, 1, 3, 5, _,  // 42
3705   X, _, _, _, _,  // 43
3706   X, _, _, _, _,  // 44
3707   X, _, _, _, _,  // 45
3708   X, _, _, _, _,  // 46
3709   X, _, _, _, _,  // 47
3710   X, _, _, _, _,  // 48
3711   X, _, _, _, _,  // 49
3712   X, _, _, _, _,  // 50
3713   X, _, _, _, _,  // 51
3714   X, _, _, _, _,  // 52
3715   X, _, _, _, _,  // 53
3716   X, _, _, _, _,  // 54
3717   X, _, _, _, _,  // 55
3718   X, _, _, _, _,  // 56
3719   X, _, _, _, _,  // 57
3720   X, _, _, _, _,  // 58
3721   X, _, _, _, _,  // 59
3722   X, _, _, _, _,  // 60
3723   X, _, _, _, _,  // 61
3724   X, _, _, _, _,  // 62
3725   X, _, _, _, _,  // 63
3726   1, 6, _, _, _,  // 64
3727   2, 0, 6, _, _,  // 65
3728   2, 1, 6, _, _,  // 66
3729   X, _, _, _, _,  // 67
3730   2, 2, 6, _, _,  // 68
3731   3, 0, 2, 6, _,  // 69
3732   X, _, _, _, _,  // 70
3733   X, _, _, _, _,  // 71
3734   2, 3, 6, _, _,  // 72
3735   3, 0, 3, 6, _,  // 73
3736   3, 1, 3, 6, _,  // 74
3737   X, _, _, _, _,  // 75
3738   X, _, _, _, _,  // 76
3739   X, _, _, _, _,  // 77
3740   X, _, _, _, _,  // 78
3741   X, _, _, _, _,  // 79
3742   2, 4, 6, _, _,  // 80
3743   3, 0, 4, 6, _,  // 81
3744   3, 1, 4, 6, _,  // 82
3745   X, _, _, _, _,  // 83
3746   3, 2, 4, 6, _,  // 84
3747   4, 0, 2, 4, 6,  // 85
3748   X, _, _, _, _,  // 86
3749   X, _, _, _, _,  // 87
3750   X, _, _, _, _,  // 88
3751   X, _, _, _, _,  // 89
3752   X, _, _, _, _,  // 90
3753   X, _, _, _, _,  // 91
3754   X, _, _, _, _,  // 92
3755   X, _, _, _, _,  // 93
3756   X, _, _, _, _,  // 94
3757   X, _, _, _, _,  // 95
3758   X, _, _, _, _,  // 96
3759   X, _, _, _, _,  // 97
3760   X, _, _, _, _,  // 98
3761   X, _, _, _, _,  // 99
3762   X, _, _, _, _,  // 100
3763   X, _, _, _, _,  // 101
3764   X, _, _, _, _,  // 102
3765   X, _, _, _, _,  // 103
3766   X, _, _, _, _,  // 104
3767   X, _, _, _, _,  // 105
3768   X, _, _, _, _,  // 106
3769   X, _, _, _, _,  // 107
3770   X, _, _, _, _,  // 108
3771   X, _, _, _, _,  // 109
3772   X, _, _, _, _,  // 110
3773   X, _, _, _, _,  // 111
3774   X, _, _, _, _,  // 112
3775   X, _, _, _, _,  // 113
3776   X, _, _, _, _,  // 114
3777   X, _, _, _, _,  // 115
3778   X, _, _, _, _,  // 116
3779   X, _, _, _, _,  // 117
3780   X, _, _, _, _,  // 118
3781   X, _, _, _, _,  // 119
3782   X, _, _, _, _,  // 120
3783   X, _, _, _, _,  // 121
3784   X, _, _, _, _,  // 122
3785   X, _, _, _, _,  // 123
3786   X, _, _, _, _,  // 124
3787   X, _, _, _, _,  // 125
3788   X, _, _, _, _,  // 126
3789   X, _, _, _, _,  // 127
3790   1, 7, _, _, _,  // 128
3791   2, 0, 7, _, _,  // 129
3792   2, 1, 7, _, _,  // 130
3793   X, _, _, _, _,  // 131
3794   2, 2, 7, _, _,  // 132
3795   3, 0, 2, 7, _,  // 133
3796   X, _, _, _, _,  // 134
3797   X, _, _, _, _,  // 135
3798   2, 3, 7, _, _,  // 136
3799   3, 0, 3, 7, _,  // 137
3800   3, 1, 3, 7, _,  // 138
3801   X, _, _, _, _,  // 139
3802   X, _, _, _, _,  // 140
3803   X, _, _, _, _,  // 141
3804   X, _, _, _, _,  // 142
3805   X, _, _, _, _,  // 143
3806   2, 4, 7, _, _,  // 144
3807   3, 0, 4, 7, _,  // 145
3808   3, 1, 4, 7, _,  // 146
3809   X, _, _, _, _,  // 147
3810   3, 2, 4, 7, _,  // 148
3811   4, 0, 2, 4, 7,  // 149
3812   X, _, _, _, _,  // 150
3813   X, _, _, _, _,  // 151
3814   X, _, _, _, _,  // 152
3815   X, _, _, _, _,  // 153
3816   X, _, _, _, _,  // 154
3817   X, _, _, _, _,  // 155
3818   X, _, _, _, _,  // 156
3819   X, _, _, _, _,  // 157
3820   X, _, _, _, _,  // 158
3821   X, _, _, _, _,  // 159
3822   2, 5, 7, _, _,  // 160
3823   3, 0, 5, 7, _,  // 161
3824   3, 1, 5, 7, _,  // 162
3825   X, _, _, _, _,  // 163
3826   3, 2, 5, 7, _,  // 164
3827   4, 0, 2, 5, 7,  // 165
3828   X, _, _, _, _,  // 166
3829   X, _, _, _, _,  // 167
3830   3, 3, 5, 7, _,  // 168
3831   4, 0, 3, 5, 7,  // 169
3832   4, 1, 3, 5, 7   // 170
3833 };
3834 #undef _
3835 #undef X
3836
3837
3838 // Takes a word of mark bits.  Returns the number of objects that start in the
3839 // range.  Puts the offsets of the words in the supplied array.
3840 static inline int MarkWordToObjectStarts(uint32_t mark_bits, int* starts) {
3841   int objects = 0;
3842   int offset = 0;
3843
3844   // No consecutive 1 bits.
3845   ASSERT((mark_bits & 0x180) != 0x180);
3846   ASSERT((mark_bits & 0x18000) != 0x18000);
3847   ASSERT((mark_bits & 0x1800000) != 0x1800000);
3848
3849   while (mark_bits != 0) {
3850     int byte = (mark_bits & 0xff);
3851     mark_bits >>= 8;
3852     if (byte != 0) {
3853       ASSERT(byte < kStartTableLines);  // No consecutive 1 bits.
3854       char* table = kStartTable + byte * kStartTableEntriesPerLine;
3855       int objects_in_these_8_words = table[0];
3856       ASSERT(objects_in_these_8_words != kStartTableInvalidLine);
3857       ASSERT(objects_in_these_8_words < kStartTableEntriesPerLine);
3858       for (int i = 0; i < objects_in_these_8_words; i++) {
3859         starts[objects++] = offset + table[1 + i];
3860       }
3861     }
3862     offset += 8;
3863   }
3864   return objects;
3865 }
3866
3867
3868 static inline Address DigestFreeStart(Address approximate_free_start,
3869                                       uint32_t free_start_cell) {
3870   ASSERT(free_start_cell != 0);
3871
3872   // No consecutive 1 bits.
3873   ASSERT((free_start_cell & (free_start_cell << 1)) == 0);
3874
3875   int offsets[16];
3876   uint32_t cell = free_start_cell;
3877   int offset_of_last_live;
3878   if ((cell & 0x80000000u) != 0) {
3879     // This case would overflow below.
3880     offset_of_last_live = 31;
3881   } else {
3882     // Remove all but one bit, the most significant.  This is an optimization
3883     // that may or may not be worthwhile.
3884     cell |= cell >> 16;
3885     cell |= cell >> 8;
3886     cell |= cell >> 4;
3887     cell |= cell >> 2;
3888     cell |= cell >> 1;
3889     cell = (cell + 1) >> 1;
3890     int live_objects = MarkWordToObjectStarts(cell, offsets);
3891     ASSERT(live_objects == 1);
3892     offset_of_last_live = offsets[live_objects - 1];
3893   }
3894   Address last_live_start =
3895       approximate_free_start + offset_of_last_live * kPointerSize;
3896   HeapObject* last_live = HeapObject::FromAddress(last_live_start);
3897   Address free_start = last_live_start + last_live->Size();
3898   return free_start;
3899 }
3900
3901
3902 static inline Address StartOfLiveObject(Address block_address, uint32_t cell) {
3903   ASSERT(cell != 0);
3904
3905   // No consecutive 1 bits.
3906   ASSERT((cell & (cell << 1)) == 0);
3907
3908   int offsets[16];
3909   if (cell == 0x80000000u) {  // Avoid overflow below.
3910     return block_address + 31 * kPointerSize;
3911   }
3912   uint32_t first_set_bit = ((cell ^ (cell - 1)) + 1) >> 1;
3913   ASSERT((first_set_bit & cell) == first_set_bit);
3914   int live_objects = MarkWordToObjectStarts(first_set_bit, offsets);
3915   ASSERT(live_objects == 1);
3916   USE(live_objects);
3917   return block_address + offsets[0] * kPointerSize;
3918 }
3919
3920
3921 template<MarkCompactCollector::SweepingParallelism mode>
3922 static intptr_t Free(PagedSpace* space,
3923                      FreeList* free_list,
3924                      Address start,
3925                      int size) {
3926   if (mode == MarkCompactCollector::SWEEP_SEQUENTIALLY) {
3927     return space->Free(start, size);
3928   } else {
3929     return size - free_list->Free(start, size);
3930   }
3931 }
3932
3933
3934 // Force instantiation of templatized SweepConservatively method for
3935 // SWEEP_SEQUENTIALLY mode.
3936 template intptr_t MarkCompactCollector::
3937     SweepConservatively<MarkCompactCollector::SWEEP_SEQUENTIALLY>(
3938         PagedSpace*, FreeList*, Page*);
3939
3940
3941 // Force instantiation of templatized SweepConservatively method for
3942 // SWEEP_IN_PARALLEL mode.
3943 template intptr_t MarkCompactCollector::
3944     SweepConservatively<MarkCompactCollector::SWEEP_IN_PARALLEL>(
3945         PagedSpace*, FreeList*, Page*);
3946
3947
3948 // Sweeps a space conservatively.  After this has been done the larger free
3949 // spaces have been put on the free list and the smaller ones have been
3950 // ignored and left untouched.  A free space is always either ignored or put
3951 // on the free list, never split up into two parts.  This is important
3952 // because it means that any FreeSpace maps left actually describe a region of
3953 // memory that can be ignored when scanning.  Dead objects other than free
3954 // spaces will not contain the free space map.
3955 template<MarkCompactCollector::SweepingParallelism mode>
3956 intptr_t MarkCompactCollector::SweepConservatively(PagedSpace* space,
3957                                                    FreeList* free_list,
3958                                                    Page* p) {
3959   ASSERT(!p->IsEvacuationCandidate() && !p->WasSwept());
3960   ASSERT((mode == MarkCompactCollector::SWEEP_IN_PARALLEL &&
3961          free_list != NULL) ||
3962          (mode == MarkCompactCollector::SWEEP_SEQUENTIALLY &&
3963          free_list == NULL));
3964
3965   // When parallel sweeping is active, the page will be marked after
3966   // sweeping by the main thread.
3967   if (mode != MarkCompactCollector::SWEEP_IN_PARALLEL) {
3968     p->MarkSweptConservatively();
3969   }
3970
3971   intptr_t freed_bytes = 0;
3972   size_t size = 0;
3973
3974   // Skip over all the dead objects at the start of the page and mark them free.
3975   Address cell_base = 0;
3976   MarkBit::CellType* cell = NULL;
3977   MarkBitCellIterator it(p);
3978   for (; !it.Done(); it.Advance()) {
3979     cell_base = it.CurrentCellBase();
3980     cell = it.CurrentCell();
3981     if (*cell != 0) break;
3982   }
3983
3984   if (it.Done()) {
3985     size = p->area_end() - p->area_start();
3986     freed_bytes += Free<mode>(space, free_list, p->area_start(),
3987                               static_cast<int>(size));
3988     ASSERT_EQ(0, p->LiveBytes());
3989     return freed_bytes;
3990   }
3991
3992   // Grow the size of the start-of-page free space a little to get up to the
3993   // first live object.
3994   Address free_end = StartOfLiveObject(cell_base, *cell);
3995   // Free the first free space.
3996   size = free_end - p->area_start();
3997   freed_bytes += Free<mode>(space, free_list, p->area_start(),
3998                             static_cast<int>(size));
3999
4000   // The start of the current free area is represented in undigested form by
4001   // the address of the last 32-word section that contained a live object and
4002   // the marking bitmap for that cell, which describes where the live object
4003   // started.  Unless we find a large free space in the bitmap we will not
4004   // digest this pair into a real address.  We start the iteration here at the
4005   // first word in the marking bit map that indicates a live object.
4006   Address free_start = cell_base;
4007   MarkBit::CellType free_start_cell = *cell;
4008
4009   for (; !it.Done(); it.Advance()) {
4010     cell_base = it.CurrentCellBase();
4011     cell = it.CurrentCell();
4012     if (*cell != 0) {
4013       // We have a live object.  Check approximately whether it is more than 32
4014       // words since the last live object.
4015       if (cell_base - free_start > 32 * kPointerSize) {
4016         free_start = DigestFreeStart(free_start, free_start_cell);
4017         if (cell_base - free_start > 32 * kPointerSize) {
4018           // Now that we know the exact start of the free space it still looks
4019           // like we have a large enough free space to be worth bothering with.
4020           // so now we need to find the start of the first live object at the
4021           // end of the free space.
4022           free_end = StartOfLiveObject(cell_base, *cell);
4023           freed_bytes += Free<mode>(space, free_list, free_start,
4024                                     static_cast<int>(free_end - free_start));
4025         }
4026       }
4027       // Update our undigested record of where the current free area started.
4028       free_start = cell_base;
4029       free_start_cell = *cell;
4030       // Clear marking bits for current cell.
4031       *cell = 0;
4032     }
4033   }
4034
4035   // Handle the free space at the end of the page.
4036   if (cell_base - free_start > 32 * kPointerSize) {
4037     free_start = DigestFreeStart(free_start, free_start_cell);
4038     freed_bytes += Free<mode>(space, free_list, free_start,
4039                               static_cast<int>(p->area_end() - free_start));
4040   }
4041
4042   p->ResetLiveBytes();
4043   return freed_bytes;
4044 }
4045
4046
4047 void MarkCompactCollector::SweepInParallel(PagedSpace* space) {
4048   PageIterator it(space);
4049   FreeList* free_list = space == heap()->old_pointer_space()
4050                             ? free_list_old_pointer_space_.get()
4051                             : free_list_old_data_space_.get();
4052   FreeList private_free_list(space);
4053   while (it.has_next()) {
4054     Page* p = it.next();
4055
4056     if (p->TryParallelSweeping()) {
4057       SweepConservatively<SWEEP_IN_PARALLEL>(space, &private_free_list, p);
4058       free_list->Concatenate(&private_free_list);
4059       p->set_parallel_sweeping(MemoryChunk::PARALLEL_SWEEPING_FINALIZE);
4060     }
4061     if (p == space->end_of_unswept_pages()) break;
4062   }
4063 }
4064
4065
4066 void MarkCompactCollector::SweepSpace(PagedSpace* space, SweeperType sweeper) {
4067   space->set_was_swept_conservatively(sweeper == CONSERVATIVE ||
4068                                       sweeper == PARALLEL_CONSERVATIVE ||
4069                                       sweeper == CONCURRENT_CONSERVATIVE);
4070   space->ClearStats();
4071
4072   // We defensively initialize end_of_unswept_pages_ here with the first page
4073   // of the pages list.
4074   space->set_end_of_unswept_pages(space->FirstPage());
4075
4076   PageIterator it(space);
4077
4078   int pages_swept = 0;
4079   bool unused_page_present = false;
4080   bool parallel_sweeping_active = false;
4081
4082   while (it.has_next()) {
4083     Page* p = it.next();
4084     ASSERT(p->parallel_sweeping() == MemoryChunk::PARALLEL_SWEEPING_DONE);
4085
4086     // Clear sweeping flags indicating that marking bits are still intact.
4087     p->ClearSweptPrecisely();
4088     p->ClearSweptConservatively();
4089
4090     if (p->IsFlagSet(Page::RESCAN_ON_EVACUATION) ||
4091         p->IsEvacuationCandidate()) {
4092       // Will be processed in EvacuateNewSpaceAndCandidates.
4093       ASSERT(evacuation_candidates_.length() > 0);
4094       continue;
4095     }
4096
4097     // One unused page is kept, all further are released before sweeping them.
4098     if (p->LiveBytes() == 0) {
4099       if (unused_page_present) {
4100         if (FLAG_gc_verbose) {
4101           PrintF("Sweeping 0x%" V8PRIxPTR " released page.\n",
4102                  reinterpret_cast<intptr_t>(p));
4103         }
4104         // Adjust unswept free bytes because releasing a page expects said
4105         // counter to be accurate for unswept pages.
4106         space->IncreaseUnsweptFreeBytes(p);
4107         space->ReleasePage(p);
4108         continue;
4109       }
4110       unused_page_present = true;
4111     }
4112
4113     switch (sweeper) {
4114       case CONSERVATIVE: {
4115         if (FLAG_gc_verbose) {
4116           PrintF("Sweeping 0x%" V8PRIxPTR " conservatively.\n",
4117                  reinterpret_cast<intptr_t>(p));
4118         }
4119         SweepConservatively<SWEEP_SEQUENTIALLY>(space, NULL, p);
4120         pages_swept++;
4121         break;
4122       }
4123       case CONCURRENT_CONSERVATIVE:
4124       case PARALLEL_CONSERVATIVE: {
4125         if (!parallel_sweeping_active) {
4126           if (FLAG_gc_verbose) {
4127             PrintF("Sweeping 0x%" V8PRIxPTR " conservatively.\n",
4128                    reinterpret_cast<intptr_t>(p));
4129           }
4130           SweepConservatively<SWEEP_SEQUENTIALLY>(space, NULL, p);
4131           pages_swept++;
4132           parallel_sweeping_active = true;
4133         } else {
4134           if (FLAG_gc_verbose) {
4135             PrintF("Sweeping 0x%" V8PRIxPTR " conservatively in parallel.\n",
4136                    reinterpret_cast<intptr_t>(p));
4137           }
4138           p->set_parallel_sweeping(MemoryChunk::PARALLEL_SWEEPING_PENDING);
4139           space->IncreaseUnsweptFreeBytes(p);
4140         }
4141         space->set_end_of_unswept_pages(p);
4142         break;
4143       }
4144       case PRECISE: {
4145         if (FLAG_gc_verbose) {
4146           PrintF("Sweeping 0x%" V8PRIxPTR " precisely.\n",
4147                  reinterpret_cast<intptr_t>(p));
4148         }
4149         if (space->identity() == CODE_SPACE && FLAG_zap_code_space) {
4150           SweepPrecisely<SWEEP_ONLY, REBUILD_SKIP_LIST, ZAP_FREE_SPACE>(
4151               space, p, NULL);
4152         } else if (space->identity() == CODE_SPACE) {
4153           SweepPrecisely<SWEEP_ONLY, REBUILD_SKIP_LIST, IGNORE_FREE_SPACE>(
4154               space, p, NULL);
4155         } else {
4156           SweepPrecisely<SWEEP_ONLY, IGNORE_SKIP_LIST, IGNORE_FREE_SPACE>(
4157               space, p, NULL);
4158         }
4159         pages_swept++;
4160         break;
4161       }
4162       default: {
4163         UNREACHABLE();
4164       }
4165     }
4166   }
4167
4168   if (FLAG_gc_verbose) {
4169     PrintF("SweepSpace: %s (%d pages swept)\n",
4170            AllocationSpaceName(space->identity()),
4171            pages_swept);
4172   }
4173
4174   // Give pages that are queued to be freed back to the OS.
4175   heap()->FreeQueuedChunks();
4176 }
4177
4178
4179 void MarkCompactCollector::SweepSpaces() {
4180   GCTracer::Scope gc_scope(tracer_, GCTracer::Scope::MC_SWEEP);
4181 #ifdef DEBUG
4182   state_ = SWEEP_SPACES;
4183 #endif
4184   SweeperType how_to_sweep = CONSERVATIVE;
4185   if (AreSweeperThreadsActivated()) {
4186     if (FLAG_parallel_sweeping) how_to_sweep = PARALLEL_CONSERVATIVE;
4187     if (FLAG_concurrent_sweeping) how_to_sweep = CONCURRENT_CONSERVATIVE;
4188   }
4189   if (sweep_precisely_) how_to_sweep = PRECISE;
4190
4191   MoveEvacuationCandidatesToEndOfPagesList();
4192
4193   // Noncompacting collections simply sweep the spaces to clear the mark
4194   // bits and free the nonlive blocks (for old and map spaces).  We sweep
4195   // the map space last because freeing non-live maps overwrites them and
4196   // the other spaces rely on possibly non-live maps to get the sizes for
4197   // non-live objects.
4198   { GCTracer::Scope sweep_scope(tracer_, GCTracer::Scope::MC_SWEEP_OLDSPACE);
4199     { SequentialSweepingScope scope(this);
4200       SweepSpace(heap()->old_pointer_space(), how_to_sweep);
4201       SweepSpace(heap()->old_data_space(), how_to_sweep);
4202     }
4203
4204     if (how_to_sweep == PARALLEL_CONSERVATIVE ||
4205         how_to_sweep == CONCURRENT_CONSERVATIVE) {
4206       StartSweeperThreads();
4207     }
4208
4209     if (how_to_sweep == PARALLEL_CONSERVATIVE) {
4210       WaitUntilSweepingCompleted();
4211     }
4212   }
4213   RemoveDeadInvalidatedCode();
4214   SweepSpace(heap()->code_space(), PRECISE);
4215
4216   SweepSpace(heap()->cell_space(), PRECISE);
4217   SweepSpace(heap()->property_cell_space(), PRECISE);
4218
4219   EvacuateNewSpaceAndCandidates();
4220
4221   // ClearNonLiveTransitions depends on precise sweeping of map space to
4222   // detect whether unmarked map became dead in this collection or in one
4223   // of the previous ones.
4224   SweepSpace(heap()->map_space(), PRECISE);
4225
4226   // Deallocate unmarked objects and clear marked bits for marked objects.
4227   heap_->lo_space()->FreeUnmarkedObjects();
4228
4229   // Deallocate evacuated candidate pages.
4230   ReleaseEvacuationCandidates();
4231 }
4232
4233
4234 void MarkCompactCollector::ParallelSweepSpaceComplete(PagedSpace* space) {
4235   PageIterator it(space);
4236   while (it.has_next()) {
4237     Page* p = it.next();
4238     if (p->parallel_sweeping() == MemoryChunk::PARALLEL_SWEEPING_FINALIZE) {
4239       p->set_parallel_sweeping(MemoryChunk::PARALLEL_SWEEPING_DONE);
4240       p->MarkSweptConservatively();
4241     }
4242     ASSERT(p->parallel_sweeping() == MemoryChunk::PARALLEL_SWEEPING_DONE);
4243   }
4244 }
4245
4246
4247 void MarkCompactCollector::ParallelSweepSpacesComplete() {
4248   ParallelSweepSpaceComplete(heap()->old_pointer_space());
4249   ParallelSweepSpaceComplete(heap()->old_data_space());
4250 }
4251
4252
4253 void MarkCompactCollector::EnableCodeFlushing(bool enable) {
4254   if (isolate()->debug()->is_loaded() ||
4255       isolate()->debug()->has_break_points()) {
4256     enable = false;
4257   }
4258
4259   if (enable) {
4260     if (code_flusher_ != NULL) return;
4261     code_flusher_ = new CodeFlusher(isolate());
4262   } else {
4263     if (code_flusher_ == NULL) return;
4264     code_flusher_->EvictAllCandidates();
4265     delete code_flusher_;
4266     code_flusher_ = NULL;
4267   }
4268
4269   if (FLAG_trace_code_flushing) {
4270     PrintF("[code-flushing is now %s]\n", enable ? "on" : "off");
4271   }
4272 }
4273
4274
4275 // TODO(1466) ReportDeleteIfNeeded is not called currently.
4276 // Our profiling tools do not expect intersections between
4277 // code objects. We should either reenable it or change our tools.
4278 void MarkCompactCollector::ReportDeleteIfNeeded(HeapObject* obj,
4279                                                 Isolate* isolate) {
4280 #ifdef ENABLE_GDB_JIT_INTERFACE
4281   if (obj->IsCode()) {
4282     GDBJITInterface::RemoveCode(reinterpret_cast<Code*>(obj));
4283   }
4284 #endif
4285   if (obj->IsCode()) {
4286     PROFILE(isolate, CodeDeleteEvent(obj->address()));
4287   }
4288 }
4289
4290
4291 Isolate* MarkCompactCollector::isolate() const {
4292   return heap_->isolate();
4293 }
4294
4295
4296 void MarkCompactCollector::Initialize() {
4297   MarkCompactMarkingVisitor::Initialize();
4298   IncrementalMarking::Initialize();
4299 }
4300
4301
4302 bool SlotsBuffer::IsTypedSlot(ObjectSlot slot) {
4303   return reinterpret_cast<uintptr_t>(slot) < NUMBER_OF_SLOT_TYPES;
4304 }
4305
4306
4307 bool SlotsBuffer::AddTo(SlotsBufferAllocator* allocator,
4308                         SlotsBuffer** buffer_address,
4309                         SlotType type,
4310                         Address addr,
4311                         AdditionMode mode) {
4312   SlotsBuffer* buffer = *buffer_address;
4313   if (buffer == NULL || !buffer->HasSpaceForTypedSlot()) {
4314     if (mode == FAIL_ON_OVERFLOW && ChainLengthThresholdReached(buffer)) {
4315       allocator->DeallocateChain(buffer_address);
4316       return false;
4317     }
4318     buffer = allocator->AllocateBuffer(buffer);
4319     *buffer_address = buffer;
4320   }
4321   ASSERT(buffer->HasSpaceForTypedSlot());
4322   buffer->Add(reinterpret_cast<ObjectSlot>(type));
4323   buffer->Add(reinterpret_cast<ObjectSlot>(addr));
4324   return true;
4325 }
4326
4327
4328 static inline SlotsBuffer::SlotType SlotTypeForRMode(RelocInfo::Mode rmode) {
4329   if (RelocInfo::IsCodeTarget(rmode)) {
4330     return SlotsBuffer::CODE_TARGET_SLOT;
4331   } else if (RelocInfo::IsEmbeddedObject(rmode)) {
4332     return SlotsBuffer::EMBEDDED_OBJECT_SLOT;
4333   } else if (RelocInfo::IsDebugBreakSlot(rmode)) {
4334     return SlotsBuffer::DEBUG_TARGET_SLOT;
4335   } else if (RelocInfo::IsJSReturn(rmode)) {
4336     return SlotsBuffer::JS_RETURN_SLOT;
4337   }
4338   UNREACHABLE();
4339   return SlotsBuffer::NUMBER_OF_SLOT_TYPES;
4340 }
4341
4342
4343 void MarkCompactCollector::RecordRelocSlot(RelocInfo* rinfo, Object* target) {
4344   Page* target_page = Page::FromAddress(reinterpret_cast<Address>(target));
4345   RelocInfo::Mode rmode = rinfo->rmode();
4346   if (target_page->IsEvacuationCandidate() &&
4347       (rinfo->host() == NULL ||
4348        !ShouldSkipEvacuationSlotRecording(rinfo->host()))) {
4349     bool success;
4350     if (RelocInfo::IsEmbeddedObject(rmode) && rinfo->IsInConstantPool()) {
4351       // This doesn't need to be typed since it is just a normal heap pointer.
4352       Object** target_pointer =
4353           reinterpret_cast<Object**>(rinfo->constant_pool_entry_address());
4354       success = SlotsBuffer::AddTo(&slots_buffer_allocator_,
4355                                    target_page->slots_buffer_address(),
4356                                    target_pointer,
4357                                    SlotsBuffer::FAIL_ON_OVERFLOW);
4358     } else if (RelocInfo::IsCodeTarget(rmode) && rinfo->IsInConstantPool()) {
4359       success = SlotsBuffer::AddTo(&slots_buffer_allocator_,
4360                                    target_page->slots_buffer_address(),
4361                                    SlotsBuffer::CODE_ENTRY_SLOT,
4362                                    rinfo->constant_pool_entry_address(),
4363                                    SlotsBuffer::FAIL_ON_OVERFLOW);
4364     } else {
4365       success = SlotsBuffer::AddTo(&slots_buffer_allocator_,
4366                                   target_page->slots_buffer_address(),
4367                                   SlotTypeForRMode(rmode),
4368                                   rinfo->pc(),
4369                                   SlotsBuffer::FAIL_ON_OVERFLOW);
4370     }
4371     if (!success) {
4372       EvictEvacuationCandidate(target_page);
4373     }
4374   }
4375 }
4376
4377
4378 void MarkCompactCollector::RecordCodeEntrySlot(Address slot, Code* target) {
4379   Page* target_page = Page::FromAddress(reinterpret_cast<Address>(target));
4380   if (target_page->IsEvacuationCandidate() &&
4381       !ShouldSkipEvacuationSlotRecording(reinterpret_cast<Object**>(slot))) {
4382     if (!SlotsBuffer::AddTo(&slots_buffer_allocator_,
4383                             target_page->slots_buffer_address(),
4384                             SlotsBuffer::CODE_ENTRY_SLOT,
4385                             slot,
4386                             SlotsBuffer::FAIL_ON_OVERFLOW)) {
4387       EvictEvacuationCandidate(target_page);
4388     }
4389   }
4390 }
4391
4392
4393 void MarkCompactCollector::RecordCodeTargetPatch(Address pc, Code* target) {
4394   ASSERT(heap()->gc_state() == Heap::MARK_COMPACT);
4395   if (is_compacting()) {
4396     Code* host = isolate()->inner_pointer_to_code_cache()->
4397         GcSafeFindCodeForInnerPointer(pc);
4398     MarkBit mark_bit = Marking::MarkBitFrom(host);
4399     if (Marking::IsBlack(mark_bit)) {
4400       RelocInfo rinfo(pc, RelocInfo::CODE_TARGET, 0, host);
4401       RecordRelocSlot(&rinfo, target);
4402     }
4403   }
4404 }
4405
4406
4407 static inline SlotsBuffer::SlotType DecodeSlotType(
4408     SlotsBuffer::ObjectSlot slot) {
4409   return static_cast<SlotsBuffer::SlotType>(reinterpret_cast<intptr_t>(slot));
4410 }
4411
4412
4413 void SlotsBuffer::UpdateSlots(Heap* heap) {
4414   PointersUpdatingVisitor v(heap);
4415
4416   for (int slot_idx = 0; slot_idx < idx_; ++slot_idx) {
4417     ObjectSlot slot = slots_[slot_idx];
4418     if (!IsTypedSlot(slot)) {
4419       PointersUpdatingVisitor::UpdateSlot(heap, slot);
4420     } else {
4421       ++slot_idx;
4422       ASSERT(slot_idx < idx_);
4423       UpdateSlot(heap->isolate(),
4424                  &v,
4425                  DecodeSlotType(slot),
4426                  reinterpret_cast<Address>(slots_[slot_idx]));
4427     }
4428   }
4429 }
4430
4431
4432 void SlotsBuffer::UpdateSlotsWithFilter(Heap* heap) {
4433   PointersUpdatingVisitor v(heap);
4434
4435   for (int slot_idx = 0; slot_idx < idx_; ++slot_idx) {
4436     ObjectSlot slot = slots_[slot_idx];
4437     if (!IsTypedSlot(slot)) {
4438       if (!IsOnInvalidatedCodeObject(reinterpret_cast<Address>(slot))) {
4439         PointersUpdatingVisitor::UpdateSlot(heap, slot);
4440       }
4441     } else {
4442       ++slot_idx;
4443       ASSERT(slot_idx < idx_);
4444       Address pc = reinterpret_cast<Address>(slots_[slot_idx]);
4445       if (!IsOnInvalidatedCodeObject(pc)) {
4446         UpdateSlot(heap->isolate(),
4447                    &v,
4448                    DecodeSlotType(slot),
4449                    reinterpret_cast<Address>(slots_[slot_idx]));
4450       }
4451     }
4452   }
4453 }
4454
4455
4456 SlotsBuffer* SlotsBufferAllocator::AllocateBuffer(SlotsBuffer* next_buffer) {
4457   return new SlotsBuffer(next_buffer);
4458 }
4459
4460
4461 void SlotsBufferAllocator::DeallocateBuffer(SlotsBuffer* buffer) {
4462   delete buffer;
4463 }
4464
4465
4466 void SlotsBufferAllocator::DeallocateChain(SlotsBuffer** buffer_address) {
4467   SlotsBuffer* buffer = *buffer_address;
4468   while (buffer != NULL) {
4469     SlotsBuffer* next_buffer = buffer->next();
4470     DeallocateBuffer(buffer);
4471     buffer = next_buffer;
4472   }
4473   *buffer_address = NULL;
4474 }
4475
4476
4477 } }  // namespace v8::internal