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