src/v8/src/mark-compact.cc

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