Home | History | Annotate | Download | only in heap 
      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/heap/incremental-marking.h"
      8 
      9 #include "src/code-stubs.h"
     10 #include "src/compilation-cache.h"
     11 #include "src/conversions.h"
     12 #include "src/heap/objects-visiting.h"
     13 #include "src/heap/objects-visiting-inl.h"
     14 
     15 namespace v8 {
     16 namespace internal {
     17 
     18 
     19 IncrementalMarking::IncrementalMarking(Heap* heap)
     20     : heap_(heap),
     21       state_(STOPPED),
     22       marking_deque_memory_(NULL),
     23       marking_deque_memory_committed_(false),
     24       steps_count_(0),
     25       old_generation_space_available_at_start_of_incremental_(0),
     26       old_generation_space_used_at_start_of_incremental_(0),
     27       should_hurry_(false),
     28       marking_speed_(0),
     29       allocated_(0),
     30       no_marking_scope_depth_(0),
     31       unscanned_bytes_of_large_object_(0) {}
     32 
     33 
     34 void IncrementalMarking::TearDown() { delete marking_deque_memory_; }
     35 
     36 
     37 void IncrementalMarking::RecordWriteSlow(HeapObject* obj, Object** slot,
     38                                          Object* value) {
     39   if (BaseRecordWrite(obj, slot, value) && slot != NULL) {
     40     MarkBit obj_bit = Marking::MarkBitFrom(obj);
     41     if (Marking::IsBlack(obj_bit)) {
     42       // Object is not going to be rescanned we need to record the slot.
     43       heap_->mark_compact_collector()->RecordSlot(HeapObject::RawField(obj, 0),
     44                                                   slot, value);
     45     }
     46   }
     47 }
     48 
     49 
     50 void IncrementalMarking::RecordWriteFromCode(HeapObject* obj, Object** slot,
     51                                              Isolate* isolate) {
     52   DCHECK(obj->IsHeapObject());
     53   IncrementalMarking* marking = isolate->heap()->incremental_marking();
     54 
     55   MemoryChunk* chunk = MemoryChunk::FromAddress(obj->address());
     56   int counter = chunk->write_barrier_counter();
     57   if (counter < (MemoryChunk::kWriteBarrierCounterGranularity / 2)) {
     58     marking->write_barriers_invoked_since_last_step_ +=
     59         MemoryChunk::kWriteBarrierCounterGranularity -
     60         chunk->write_barrier_counter();
     61     chunk->set_write_barrier_counter(
     62         MemoryChunk::kWriteBarrierCounterGranularity);
     63   }
     64 
     65   marking->RecordWrite(obj, slot, *slot);
     66 }
     67 
     68 
     69 void IncrementalMarking::RecordCodeTargetPatch(Code* host, Address pc,
     70                                                HeapObject* value) {
     71   if (IsMarking()) {
     72     RelocInfo rinfo(pc, RelocInfo::CODE_TARGET, 0, host);
     73     RecordWriteIntoCode(host, &rinfo, value);
     74   }
     75 }
     76 
     77 
     78 void IncrementalMarking::RecordCodeTargetPatch(Address pc, HeapObject* value) {
     79   if (IsMarking()) {
     80     Code* host = heap_->isolate()
     81                      ->inner_pointer_to_code_cache()
     82                      ->GcSafeFindCodeForInnerPointer(pc);
     83     RelocInfo rinfo(pc, RelocInfo::CODE_TARGET, 0, host);
     84     RecordWriteIntoCode(host, &rinfo, value);
     85   }
     86 }
     87 
     88 
     89 void IncrementalMarking::RecordWriteOfCodeEntrySlow(JSFunction* host,
     90                                                     Object** slot,
     91                                                     Code* value) {
     92   if (BaseRecordWrite(host, slot, value)) {
     93     DCHECK(slot != NULL);
     94     heap_->mark_compact_collector()->RecordCodeEntrySlot(
     95         reinterpret_cast<Address>(slot), value);
     96   }
     97 }
     98 
     99 
    100 void IncrementalMarking::RecordWriteIntoCodeSlow(HeapObject* obj,
    101                                                  RelocInfo* rinfo,
    102                                                  Object* value) {
    103   MarkBit value_bit = Marking::MarkBitFrom(HeapObject::cast(value));
    104   if (Marking::IsWhite(value_bit)) {
    105     MarkBit obj_bit = Marking::MarkBitFrom(obj);
    106     if (Marking::IsBlack(obj_bit)) {
    107       BlackToGreyAndUnshift(obj, obj_bit);
    108       RestartIfNotMarking();
    109     }
    110     // Object is either grey or white.  It will be scanned if survives.
    111     return;
    112   }
    113 
    114   if (is_compacting_) {
    115     MarkBit obj_bit = Marking::MarkBitFrom(obj);
    116     if (Marking::IsBlack(obj_bit)) {
    117       // Object is not going to be rescanned.  We need to record the slot.
    118       heap_->mark_compact_collector()->RecordRelocSlot(rinfo,
    119                                                        Code::cast(value));
    120     }
    121   }
    122 }
    123 
    124 
    125 static void MarkObjectGreyDoNotEnqueue(Object* obj) {
    126   if (obj->IsHeapObject()) {
    127     HeapObject* heap_obj = HeapObject::cast(obj);
    128     MarkBit mark_bit = Marking::MarkBitFrom(HeapObject::cast(obj));
    129     if (Marking::IsBlack(mark_bit)) {
    130       MemoryChunk::IncrementLiveBytesFromGC(heap_obj->address(),
    131                                             -heap_obj->Size());
    132     }
    133     Marking::AnyToGrey(mark_bit);
    134   }
    135 }
    136 
    137 
    138 static inline void MarkBlackOrKeepGrey(HeapObject* heap_object,
    139                                        MarkBit mark_bit, int size) {
    140   DCHECK(!Marking::IsImpossible(mark_bit));
    141   if (mark_bit.Get()) return;
    142   mark_bit.Set();
    143   MemoryChunk::IncrementLiveBytesFromGC(heap_object->address(), size);
    144   DCHECK(Marking::IsBlack(mark_bit));
    145 }
    146 
    147 
    148 static inline void MarkBlackOrKeepBlack(HeapObject* heap_object,
    149                                         MarkBit mark_bit, int size) {
    150   DCHECK(!Marking::IsImpossible(mark_bit));
    151   if (Marking::IsBlack(mark_bit)) return;
    152   Marking::MarkBlack(mark_bit);
    153   MemoryChunk::IncrementLiveBytesFromGC(heap_object->address(), size);
    154   DCHECK(Marking::IsBlack(mark_bit));
    155 }
    156 
    157 
    158 class IncrementalMarkingMarkingVisitor
    159     : public StaticMarkingVisitor<IncrementalMarkingMarkingVisitor> {
    160  public:
    161   static void Initialize() {
    162     StaticMarkingVisitor<IncrementalMarkingMarkingVisitor>::Initialize();
    163     table_.Register(kVisitFixedArray, &VisitFixedArrayIncremental);
    164     table_.Register(kVisitNativeContext, &VisitNativeContextIncremental);
    165     table_.Register(kVisitJSRegExp, &VisitJSRegExp);
    166   }
    167 
    168   static const int kProgressBarScanningChunk = 32 * 1024;
    169 
    170   static void VisitFixedArrayIncremental(Map* map, HeapObject* object) {
    171     MemoryChunk* chunk = MemoryChunk::FromAddress(object->address());
    172     // TODO(mstarzinger): Move setting of the flag to the allocation site of
    173     // the array. The visitor should just check the flag.
    174     if (FLAG_use_marking_progress_bar &&
    175         chunk->owner()->identity() == LO_SPACE) {
    176       chunk->SetFlag(MemoryChunk::HAS_PROGRESS_BAR);
    177     }
    178     if (chunk->IsFlagSet(MemoryChunk::HAS_PROGRESS_BAR)) {
    179       Heap* heap = map->GetHeap();
    180       // When using a progress bar for large fixed arrays, scan only a chunk of
    181       // the array and try to push it onto the marking deque again until it is
    182       // fully scanned. Fall back to scanning it through to the end in case this
    183       // fails because of a full deque.
    184       int object_size = FixedArray::BodyDescriptor::SizeOf(map, object);
    185       int start_offset =
    186           Max(FixedArray::BodyDescriptor::kStartOffset, chunk->progress_bar());
    187       int end_offset =
    188           Min(object_size, start_offset + kProgressBarScanningChunk);
    189       int already_scanned_offset = start_offset;
    190       bool scan_until_end = false;
    191       do {
    192         VisitPointersWithAnchor(heap, HeapObject::RawField(object, 0),
    193                                 HeapObject::RawField(object, start_offset),
    194                                 HeapObject::RawField(object, end_offset));
    195         start_offset = end_offset;
    196         end_offset = Min(object_size, end_offset + kProgressBarScanningChunk);
    197         scan_until_end = heap->incremental_marking()->marking_deque()->IsFull();
    198       } while (scan_until_end && start_offset < object_size);
    199       chunk->set_progress_bar(start_offset);
    200       if (start_offset < object_size) {
    201         heap->incremental_marking()->marking_deque()->UnshiftGrey(object);
    202         heap->incremental_marking()->NotifyIncompleteScanOfObject(
    203             object_size - (start_offset - already_scanned_offset));
    204       }
    205     } else {
    206       FixedArrayVisitor::Visit(map, object);
    207     }
    208   }
    209 
    210   static void VisitNativeContextIncremental(Map* map, HeapObject* object) {
    211     Context* context = Context::cast(object);
    212 
    213     // We will mark cache black with a separate pass when we finish marking.
    214     // Note that GC can happen when the context is not fully initialized,
    215     // so the cache can be undefined.
    216     Object* cache = context->get(Context::NORMALIZED_MAP_CACHE_INDEX);
    217     if (!cache->IsUndefined()) {
    218       MarkObjectGreyDoNotEnqueue(cache);
    219     }
    220     VisitNativeContext(map, context);
    221   }
    222 
    223   INLINE(static void VisitPointer(Heap* heap, Object** p)) {
    224     Object* obj = *p;
    225     if (obj->IsHeapObject()) {
    226       heap->mark_compact_collector()->RecordSlot(p, p, obj);
    227       MarkObject(heap, obj);
    228     }
    229   }
    230 
    231   INLINE(static void VisitPointers(Heap* heap, Object** start, Object** end)) {
    232     for (Object** p = start; p < end; p++) {
    233       Object* obj = *p;
    234       if (obj->IsHeapObject()) {
    235         heap->mark_compact_collector()->RecordSlot(start, p, obj);
    236         MarkObject(heap, obj);
    237       }
    238     }
    239   }
    240 
    241   INLINE(static void VisitPointersWithAnchor(Heap* heap, Object** anchor,
    242                                              Object** start, Object** end)) {
    243     for (Object** p = start; p < end; p++) {
    244       Object* obj = *p;
    245       if (obj->IsHeapObject()) {
    246         heap->mark_compact_collector()->RecordSlot(anchor, p, obj);
    247         MarkObject(heap, obj);
    248       }
    249     }
    250   }
    251 
    252   // Marks the object grey and pushes it on the marking stack.
    253   INLINE(static void MarkObject(Heap* heap, Object* obj)) {
    254     HeapObject* heap_object = HeapObject::cast(obj);
    255     MarkBit mark_bit = Marking::MarkBitFrom(heap_object);
    256     if (mark_bit.data_only()) {
    257       MarkBlackOrKeepGrey(heap_object, mark_bit, heap_object->Size());
    258     } else if (Marking::IsWhite(mark_bit)) {
    259       heap->incremental_marking()->WhiteToGreyAndPush(heap_object, mark_bit);
    260     }
    261   }
    262 
    263   // Marks the object black without pushing it on the marking stack.
    264   // Returns true if object needed marking and false otherwise.
    265   INLINE(static bool MarkObjectWithoutPush(Heap* heap, Object* obj)) {
    266     HeapObject* heap_object = HeapObject::cast(obj);
    267     MarkBit mark_bit = Marking::MarkBitFrom(heap_object);
    268     if (Marking::IsWhite(mark_bit)) {
    269       mark_bit.Set();
    270       MemoryChunk::IncrementLiveBytesFromGC(heap_object->address(),
    271                                             heap_object->Size());
    272       return true;
    273     }
    274     return false;
    275   }
    276 };
    277 
    278 
    279 class IncrementalMarkingRootMarkingVisitor : public ObjectVisitor {
    280  public:
    281   explicit IncrementalMarkingRootMarkingVisitor(
    282       IncrementalMarking* incremental_marking)
    283       : incremental_marking_(incremental_marking) {}
    284 
    285   void VisitPointer(Object** p) { MarkObjectByPointer(p); }
    286 
    287   void VisitPointers(Object** start, Object** end) {
    288     for (Object** p = start; p < end; p++) MarkObjectByPointer(p);
    289   }
    290 
    291  private:
    292   void MarkObjectByPointer(Object** p) {
    293     Object* obj = *p;
    294     if (!obj->IsHeapObject()) return;
    295 
    296     HeapObject* heap_object = HeapObject::cast(obj);
    297     MarkBit mark_bit = Marking::MarkBitFrom(heap_object);
    298     if (mark_bit.data_only()) {
    299       MarkBlackOrKeepGrey(heap_object, mark_bit, heap_object->Size());
    300     } else {
    301       if (Marking::IsWhite(mark_bit)) {
    302         incremental_marking_->WhiteToGreyAndPush(heap_object, mark_bit);
    303       }
    304     }
    305   }
    306 
    307   IncrementalMarking* incremental_marking_;
    308 };
    309 
    310 
    311 void IncrementalMarking::Initialize() {
    312   IncrementalMarkingMarkingVisitor::Initialize();
    313 }
    314 
    315 
    316 void IncrementalMarking::SetOldSpacePageFlags(MemoryChunk* chunk,
    317                                               bool is_marking,
    318                                               bool is_compacting) {
    319   if (is_marking) {
    320     chunk->SetFlag(MemoryChunk::POINTERS_TO_HERE_ARE_INTERESTING);
    321     chunk->SetFlag(MemoryChunk::POINTERS_FROM_HERE_ARE_INTERESTING);
    322 
    323     // It's difficult to filter out slots recorded for large objects.
    324     if (chunk->owner()->identity() == LO_SPACE &&
    325         chunk->size() > static_cast<size_t>(Page::kPageSize) && is_compacting) {
    326       chunk->SetFlag(MemoryChunk::RESCAN_ON_EVACUATION);
    327     }
    328   } else if (chunk->owner()->identity() == CELL_SPACE ||
    329              chunk->owner()->identity() == PROPERTY_CELL_SPACE ||
    330              chunk->scan_on_scavenge()) {
    331     chunk->ClearFlag(MemoryChunk::POINTERS_TO_HERE_ARE_INTERESTING);
    332     chunk->ClearFlag(MemoryChunk::POINTERS_FROM_HERE_ARE_INTERESTING);
    333   } else {
    334     chunk->ClearFlag(MemoryChunk::POINTERS_TO_HERE_ARE_INTERESTING);
    335     chunk->SetFlag(MemoryChunk::POINTERS_FROM_HERE_ARE_INTERESTING);
    336   }
    337 }
    338 
    339 
    340 void IncrementalMarking::SetNewSpacePageFlags(NewSpacePage* chunk,
    341                                               bool is_marking) {
    342   chunk->SetFlag(MemoryChunk::POINTERS_TO_HERE_ARE_INTERESTING);
    343   if (is_marking) {
    344     chunk->SetFlag(MemoryChunk::POINTERS_FROM_HERE_ARE_INTERESTING);
    345   } else {
    346     chunk->ClearFlag(MemoryChunk::POINTERS_FROM_HERE_ARE_INTERESTING);
    347   }
    348   chunk->SetFlag(MemoryChunk::SCAN_ON_SCAVENGE);
    349 }
    350 
    351 
    352 void IncrementalMarking::DeactivateIncrementalWriteBarrierForSpace(
    353     PagedSpace* space) {
    354   PageIterator it(space);
    355   while (it.has_next()) {
    356     Page* p = it.next();
    357     SetOldSpacePageFlags(p, false, false);
    358   }
    359 }
    360 
    361 
    362 void IncrementalMarking::DeactivateIncrementalWriteBarrierForSpace(
    363     NewSpace* space) {
    364   NewSpacePageIterator it(space);
    365   while (it.has_next()) {
    366     NewSpacePage* p = it.next();
    367     SetNewSpacePageFlags(p, false);
    368   }
    369 }
    370 
    371 
    372 void IncrementalMarking::DeactivateIncrementalWriteBarrier() {
    373   DeactivateIncrementalWriteBarrierForSpace(heap_->old_pointer_space());
    374   DeactivateIncrementalWriteBarrierForSpace(heap_->old_data_space());
    375   DeactivateIncrementalWriteBarrierForSpace(heap_->cell_space());
    376   DeactivateIncrementalWriteBarrierForSpace(heap_->property_cell_space());
    377   DeactivateIncrementalWriteBarrierForSpace(heap_->map_space());
    378   DeactivateIncrementalWriteBarrierForSpace(heap_->code_space());
    379   DeactivateIncrementalWriteBarrierForSpace(heap_->new_space());
    380 
    381   LargePage* lop = heap_->lo_space()->first_page();
    382   while (lop->is_valid()) {
    383     SetOldSpacePageFlags(lop, false, false);
    384     lop = lop->next_page();
    385   }
    386 }
    387 
    388 
    389 void IncrementalMarking::ActivateIncrementalWriteBarrier(PagedSpace* space) {
    390   PageIterator it(space);
    391   while (it.has_next()) {
    392     Page* p = it.next();
    393     SetOldSpacePageFlags(p, true, is_compacting_);
    394   }
    395 }
    396 
    397 
    398 void IncrementalMarking::ActivateIncrementalWriteBarrier(NewSpace* space) {
    399   NewSpacePageIterator it(space->ToSpaceStart(), space->ToSpaceEnd());
    400   while (it.has_next()) {
    401     NewSpacePage* p = it.next();
    402     SetNewSpacePageFlags(p, true);
    403   }
    404 }
    405 
    406 
    407 void IncrementalMarking::ActivateIncrementalWriteBarrier() {
    408   ActivateIncrementalWriteBarrier(heap_->old_pointer_space());
    409   ActivateIncrementalWriteBarrier(heap_->old_data_space());
    410   ActivateIncrementalWriteBarrier(heap_->cell_space());
    411   ActivateIncrementalWriteBarrier(heap_->property_cell_space());
    412   ActivateIncrementalWriteBarrier(heap_->map_space());
    413   ActivateIncrementalWriteBarrier(heap_->code_space());
    414   ActivateIncrementalWriteBarrier(heap_->new_space());
    415 
    416   LargePage* lop = heap_->lo_space()->first_page();
    417   while (lop->is_valid()) {
    418     SetOldSpacePageFlags(lop, true, is_compacting_);
    419     lop = lop->next_page();
    420   }
    421 }
    422 
    423 
    424 bool IncrementalMarking::ShouldActivate() {
    425   return WorthActivating() && heap_->NextGCIsLikelyToBeFull();
    426 }
    427 
    428 
    429 bool IncrementalMarking::WorthActivating() {
    430 #ifndef DEBUG
    431   static const intptr_t kActivationThreshold = 8 * MB;
    432 #else
    433   // TODO(gc) consider setting this to some low level so that some
    434   // debug tests run with incremental marking and some without.
    435   static const intptr_t kActivationThreshold = 0;
    436 #endif
    437   // Only start incremental marking in a safe state: 1) when incremental
    438   // marking is turned on, 2) when we are currently not in a GC, and
    439   // 3) when we are currently not serializing or deserializing the heap.
    440   return FLAG_incremental_marking && FLAG_incremental_marking_steps &&
    441          heap_->gc_state() == Heap::NOT_IN_GC &&
    442          !heap_->isolate()->serializer_enabled() &&
    443          heap_->isolate()->IsInitialized() &&
    444          heap_->PromotedSpaceSizeOfObjects() > kActivationThreshold;
    445 }
    446 
    447 
    448 void IncrementalMarking::ActivateGeneratedStub(Code* stub) {
    449   DCHECK(RecordWriteStub::GetMode(stub) == RecordWriteStub::STORE_BUFFER_ONLY);
    450 
    451   if (!IsMarking()) {
    452     // Initially stub is generated in STORE_BUFFER_ONLY mode thus
    453     // we don't need to do anything if incremental marking is
    454     // not active.
    455   } else if (IsCompacting()) {
    456     RecordWriteStub::Patch(stub, RecordWriteStub::INCREMENTAL_COMPACTION);
    457   } else {
    458     RecordWriteStub::Patch(stub, RecordWriteStub::INCREMENTAL);
    459   }
    460 }
    461 
    462 
    463 static void PatchIncrementalMarkingRecordWriteStubs(
    464     Heap* heap, RecordWriteStub::Mode mode) {
    465   UnseededNumberDictionary* stubs = heap->code_stubs();
    466 
    467   int capacity = stubs->Capacity();
    468   for (int i = 0; i < capacity; i++) {
    469     Object* k = stubs->KeyAt(i);
    470     if (stubs->IsKey(k)) {
    471       uint32_t key = NumberToUint32(k);
    472 
    473       if (CodeStub::MajorKeyFromKey(key) == CodeStub::RecordWrite) {
    474         Object* e = stubs->ValueAt(i);
    475         if (e->IsCode()) {
    476           RecordWriteStub::Patch(Code::cast(e), mode);
    477         }
    478       }
    479     }
    480   }
    481 }
    482 
    483 
    484 void IncrementalMarking::EnsureMarkingDequeIsCommitted() {
    485   if (marking_deque_memory_ == NULL) {
    486     marking_deque_memory_ = new base::VirtualMemory(4 * MB);
    487   }
    488   if (!marking_deque_memory_committed_) {
    489     bool success = marking_deque_memory_->Commit(
    490         reinterpret_cast<Address>(marking_deque_memory_->address()),
    491         marking_deque_memory_->size(),
    492         false);  // Not executable.
    493     CHECK(success);
    494     marking_deque_memory_committed_ = true;
    495   }
    496 }
    497 
    498 
    499 void IncrementalMarking::UncommitMarkingDeque() {
    500   if (state_ == STOPPED && marking_deque_memory_committed_) {
    501     bool success = marking_deque_memory_->Uncommit(
    502         reinterpret_cast<Address>(marking_deque_memory_->address()),
    503         marking_deque_memory_->size());
    504     CHECK(success);
    505     marking_deque_memory_committed_ = false;
    506   }
    507 }
    508 
    509 
    510 void IncrementalMarking::Start(CompactionFlag flag) {
    511   if (FLAG_trace_incremental_marking) {
    512     PrintF("[IncrementalMarking] Start\n");
    513   }
    514   DCHECK(FLAG_incremental_marking);
    515   DCHECK(FLAG_incremental_marking_steps);
    516   DCHECK(state_ == STOPPED);
    517   DCHECK(heap_->gc_state() == Heap::NOT_IN_GC);
    518   DCHECK(!heap_->isolate()->serializer_enabled());
    519   DCHECK(heap_->isolate()->IsInitialized());
    520 
    521   ResetStepCounters();
    522 
    523   if (!heap_->mark_compact_collector()->sweeping_in_progress()) {
    524     StartMarking(flag);
    525   } else {
    526     if (FLAG_trace_incremental_marking) {
    527       PrintF("[IncrementalMarking] Start sweeping.\n");
    528     }
    529     state_ = SWEEPING;
    530   }
    531 
    532   heap_->new_space()->LowerInlineAllocationLimit(kAllocatedThreshold);
    533 }
    534 
    535 
    536 void IncrementalMarking::StartMarking(CompactionFlag flag) {
    537   if (FLAG_trace_incremental_marking) {
    538     PrintF("[IncrementalMarking] Start marking\n");
    539   }
    540 
    541   is_compacting_ = !FLAG_never_compact && (flag == ALLOW_COMPACTION) &&
    542                    heap_->mark_compact_collector()->StartCompaction(
    543                        MarkCompactCollector::INCREMENTAL_COMPACTION);
    544 
    545   state_ = MARKING;
    546 
    547   RecordWriteStub::Mode mode = is_compacting_
    548                                    ? RecordWriteStub::INCREMENTAL_COMPACTION
    549                                    : RecordWriteStub::INCREMENTAL;
    550 
    551   PatchIncrementalMarkingRecordWriteStubs(heap_, mode);
    552 
    553   EnsureMarkingDequeIsCommitted();
    554 
    555   // Initialize marking stack.
    556   Address addr = static_cast<Address>(marking_deque_memory_->address());
    557   size_t size = marking_deque_memory_->size();
    558   if (FLAG_force_marking_deque_overflows) size = 64 * kPointerSize;
    559   marking_deque_.Initialize(addr, addr + size);
    560 
    561   ActivateIncrementalWriteBarrier();
    562 
    563 // Marking bits are cleared by the sweeper.
    564 #ifdef VERIFY_HEAP
    565   if (FLAG_verify_heap) {
    566     heap_->mark_compact_collector()->VerifyMarkbitsAreClean();
    567   }
    568 #endif
    569 
    570   heap_->CompletelyClearInstanceofCache();
    571   heap_->isolate()->compilation_cache()->MarkCompactPrologue();
    572 
    573   if (FLAG_cleanup_code_caches_at_gc) {
    574     // We will mark cache black with a separate pass
    575     // when we finish marking.
    576     MarkObjectGreyDoNotEnqueue(heap_->polymorphic_code_cache());
    577   }
    578 
    579   // Mark strong roots grey.
    580   IncrementalMarkingRootMarkingVisitor visitor(this);
    581   heap_->IterateStrongRoots(&visitor, VISIT_ONLY_STRONG);
    582 
    583   heap_->mark_compact_collector()->MarkWeakObjectToCodeTable();
    584 
    585   // Ready to start incremental marking.
    586   if (FLAG_trace_incremental_marking) {
    587     PrintF("[IncrementalMarking] Running\n");
    588   }
    589 }
    590 
    591 
    592 void IncrementalMarking::PrepareForScavenge() {
    593   if (!IsMarking()) return;
    594   NewSpacePageIterator it(heap_->new_space()->FromSpaceStart(),
    595                           heap_->new_space()->FromSpaceEnd());
    596   while (it.has_next()) {
    597     Bitmap::Clear(it.next());
    598   }
    599 }
    600 
    601 
    602 void IncrementalMarking::UpdateMarkingDequeAfterScavenge() {
    603   if (!IsMarking()) return;
    604 
    605   int current = marking_deque_.bottom();
    606   int mask = marking_deque_.mask();
    607   int limit = marking_deque_.top();
    608   HeapObject** array = marking_deque_.array();
    609   int new_top = current;
    610 
    611   Map* filler_map = heap_->one_pointer_filler_map();
    612 
    613   while (current != limit) {
    614     HeapObject* obj = array[current];
    615     DCHECK(obj->IsHeapObject());
    616     current = ((current + 1) & mask);
    617     if (heap_->InNewSpace(obj)) {
    618       MapWord map_word = obj->map_word();
    619       if (map_word.IsForwardingAddress()) {
    620         HeapObject* dest = map_word.ToForwardingAddress();
    621         array[new_top] = dest;
    622         new_top = ((new_top + 1) & mask);
    623         DCHECK(new_top != marking_deque_.bottom());
    624 #ifdef DEBUG
    625         MarkBit mark_bit = Marking::MarkBitFrom(obj);
    626         DCHECK(Marking::IsGrey(mark_bit) ||
    627                (obj->IsFiller() && Marking::IsWhite(mark_bit)));
    628 #endif
    629       }
    630     } else if (obj->map() != filler_map) {
    631       // Skip one word filler objects that appear on the
    632       // stack when we perform in place array shift.
    633       array[new_top] = obj;
    634       new_top = ((new_top + 1) & mask);
    635       DCHECK(new_top != marking_deque_.bottom());
    636 #ifdef DEBUG
    637       MarkBit mark_bit = Marking::MarkBitFrom(obj);
    638       MemoryChunk* chunk = MemoryChunk::FromAddress(obj->address());
    639       DCHECK(Marking::IsGrey(mark_bit) ||
    640              (obj->IsFiller() && Marking::IsWhite(mark_bit)) ||
    641              (chunk->IsFlagSet(MemoryChunk::HAS_PROGRESS_BAR) &&
    642               Marking::IsBlack(mark_bit)));
    643 #endif
    644     }
    645   }
    646   marking_deque_.set_top(new_top);
    647 }
    648 
    649 
    650 void IncrementalMarking::VisitObject(Map* map, HeapObject* obj, int size) {
    651   MarkBit map_mark_bit = Marking::MarkBitFrom(map);
    652   if (Marking::IsWhite(map_mark_bit)) {
    653     WhiteToGreyAndPush(map, map_mark_bit);
    654   }
    655 
    656   IncrementalMarkingMarkingVisitor::IterateBody(map, obj);
    657 
    658   MarkBit mark_bit = Marking::MarkBitFrom(obj);
    659 #if ENABLE_SLOW_DCHECKS
    660   MemoryChunk* chunk = MemoryChunk::FromAddress(obj->address());
    661   SLOW_DCHECK(Marking::IsGrey(mark_bit) ||
    662               (obj->IsFiller() && Marking::IsWhite(mark_bit)) ||
    663               (chunk->IsFlagSet(MemoryChunk::HAS_PROGRESS_BAR) &&
    664                Marking::IsBlack(mark_bit)));
    665 #endif
    666   MarkBlackOrKeepBlack(obj, mark_bit, size);
    667 }
    668 
    669 
    670 intptr_t IncrementalMarking::ProcessMarkingDeque(intptr_t bytes_to_process) {
    671   intptr_t bytes_processed = 0;
    672   Map* filler_map = heap_->one_pointer_filler_map();
    673   while (!marking_deque_.IsEmpty() && bytes_processed < bytes_to_process) {
    674     HeapObject* obj = marking_deque_.Pop();
    675 
    676     // Explicitly skip one word fillers. Incremental markbit patterns are
    677     // correct only for objects that occupy at least two words.
    678     Map* map = obj->map();
    679     if (map == filler_map) continue;
    680 
    681     int size = obj->SizeFromMap(map);
    682     unscanned_bytes_of_large_object_ = 0;
    683     VisitObject(map, obj, size);
    684     int delta = (size - unscanned_bytes_of_large_object_);
    685     // TODO(jochen): remove after http://crbug.com/381820 is resolved.
    686     CHECK_LT(0, delta);
    687     bytes_processed += delta;
    688   }
    689   return bytes_processed;
    690 }
    691 
    692 
    693 void IncrementalMarking::ProcessMarkingDeque() {
    694   Map* filler_map = heap_->one_pointer_filler_map();
    695   while (!marking_deque_.IsEmpty()) {
    696     HeapObject* obj = marking_deque_.Pop();
    697 
    698     // Explicitly skip one word fillers. Incremental markbit patterns are
    699     // correct only for objects that occupy at least two words.
    700     Map* map = obj->map();
    701     if (map == filler_map) continue;
    702 
    703     VisitObject(map, obj, obj->SizeFromMap(map));
    704   }
    705 }
    706 
    707 
    708 void IncrementalMarking::Hurry() {
    709   if (state() == MARKING) {
    710     double start = 0.0;
    711     if (FLAG_trace_incremental_marking || FLAG_print_cumulative_gc_stat) {
    712       start = base::OS::TimeCurrentMillis();
    713       if (FLAG_trace_incremental_marking) {
    714         PrintF("[IncrementalMarking] Hurry\n");
    715       }
    716     }
    717     // TODO(gc) hurry can mark objects it encounters black as mutator
    718     // was stopped.
    719     ProcessMarkingDeque();
    720     state_ = COMPLETE;
    721     if (FLAG_trace_incremental_marking || FLAG_print_cumulative_gc_stat) {
    722       double end = base::OS::TimeCurrentMillis();
    723       double delta = end - start;
    724       heap_->tracer()->AddMarkingTime(delta);
    725       if (FLAG_trace_incremental_marking) {
    726         PrintF("[IncrementalMarking] Complete (hurry), spent %d ms.\n",
    727                static_cast<int>(delta));
    728       }
    729     }
    730   }
    731 
    732   if (FLAG_cleanup_code_caches_at_gc) {
    733     PolymorphicCodeCache* poly_cache = heap_->polymorphic_code_cache();
    734     Marking::GreyToBlack(Marking::MarkBitFrom(poly_cache));
    735     MemoryChunk::IncrementLiveBytesFromGC(poly_cache->address(),
    736                                           PolymorphicCodeCache::kSize);
    737   }
    738 
    739   Object* context = heap_->native_contexts_list();
    740   while (!context->IsUndefined()) {
    741     // GC can happen when the context is not fully initialized,
    742     // so the cache can be undefined.
    743     HeapObject* cache = HeapObject::cast(
    744         Context::cast(context)->get(Context::NORMALIZED_MAP_CACHE_INDEX));
    745     if (!cache->IsUndefined()) {
    746       MarkBit mark_bit = Marking::MarkBitFrom(cache);
    747       if (Marking::IsGrey(mark_bit)) {
    748         Marking::GreyToBlack(mark_bit);
    749         MemoryChunk::IncrementLiveBytesFromGC(cache->address(), cache->Size());
    750       }
    751     }
    752     context = Context::cast(context)->get(Context::NEXT_CONTEXT_LINK);
    753   }
    754 }
    755 
    756 
    757 void IncrementalMarking::Abort() {
    758   if (IsStopped()) return;
    759   if (FLAG_trace_incremental_marking) {
    760     PrintF("[IncrementalMarking] Aborting.\n");
    761   }
    762   heap_->new_space()->LowerInlineAllocationLimit(0);
    763   IncrementalMarking::set_should_hurry(false);
    764   ResetStepCounters();
    765   if (IsMarking()) {
    766     PatchIncrementalMarkingRecordWriteStubs(heap_,
    767                                             RecordWriteStub::STORE_BUFFER_ONLY);
    768     DeactivateIncrementalWriteBarrier();
    769 
    770     if (is_compacting_) {
    771       LargeObjectIterator it(heap_->lo_space());
    772       for (HeapObject* obj = it.Next(); obj != NULL; obj = it.Next()) {
    773         Page* p = Page::FromAddress(obj->address());
    774         if (p->IsFlagSet(Page::RESCAN_ON_EVACUATION)) {
    775           p->ClearFlag(Page::RESCAN_ON_EVACUATION);
    776         }
    777       }
    778     }
    779   }
    780   heap_->isolate()->stack_guard()->ClearGC();
    781   state_ = STOPPED;
    782   is_compacting_ = false;
    783 }
    784 
    785 
    786 void IncrementalMarking::Finalize() {
    787   Hurry();
    788   state_ = STOPPED;
    789   is_compacting_ = false;
    790   heap_->new_space()->LowerInlineAllocationLimit(0);
    791   IncrementalMarking::set_should_hurry(false);
    792   ResetStepCounters();
    793   PatchIncrementalMarkingRecordWriteStubs(heap_,
    794                                           RecordWriteStub::STORE_BUFFER_ONLY);
    795   DeactivateIncrementalWriteBarrier();
    796   DCHECK(marking_deque_.IsEmpty());
    797   heap_->isolate()->stack_guard()->ClearGC();
    798 }
    799 
    800 
    801 void IncrementalMarking::MarkingComplete(CompletionAction action) {
    802   state_ = COMPLETE;
    803   // We will set the stack guard to request a GC now.  This will mean the rest
    804   // of the GC gets performed as soon as possible (we can't do a GC here in a
    805   // record-write context).  If a few things get allocated between now and then
    806   // that shouldn't make us do a scavenge and keep being incremental, so we set
    807   // the should-hurry flag to indicate that there can't be much work left to do.
    808   set_should_hurry(true);
    809   if (FLAG_trace_incremental_marking) {
    810     PrintF("[IncrementalMarking] Complete (normal).\n");
    811   }
    812   if (action == GC_VIA_STACK_GUARD) {
    813     heap_->isolate()->stack_guard()->RequestGC();
    814   }
    815 }
    816 
    817 
    818 void IncrementalMarking::OldSpaceStep(intptr_t allocated) {
    819   if (IsStopped() && ShouldActivate()) {
    820     // TODO(hpayer): Let's play safe for now, but compaction should be
    821     // in principle possible.
    822     Start(PREVENT_COMPACTION);
    823   } else {
    824     Step(allocated * kFastMarking / kInitialMarkingSpeed, GC_VIA_STACK_GUARD);
    825   }
    826 }
    827 
    828 
    829 void IncrementalMarking::SpeedUp() {
    830   bool speed_up = false;
    831 
    832   if ((steps_count_ % kMarkingSpeedAccellerationInterval) == 0) {
    833     if (FLAG_trace_gc) {
    834       PrintPID("Speed up marking after %d steps\n",
    835                static_cast<int>(kMarkingSpeedAccellerationInterval));
    836     }
    837     speed_up = true;
    838   }
    839 
    840   bool space_left_is_very_small =
    841       (old_generation_space_available_at_start_of_incremental_ < 10 * MB);
    842 
    843   bool only_1_nth_of_space_that_was_available_still_left =
    844       (SpaceLeftInOldSpace() * (marking_speed_ + 1) <
    845        old_generation_space_available_at_start_of_incremental_);
    846 
    847   if (space_left_is_very_small ||
    848       only_1_nth_of_space_that_was_available_still_left) {
    849     if (FLAG_trace_gc) PrintPID("Speed up marking because of low space left\n");
    850     speed_up = true;
    851   }
    852 
    853   bool size_of_old_space_multiplied_by_n_during_marking =
    854       (heap_->PromotedTotalSize() >
    855        (marking_speed_ + 1) *
    856            old_generation_space_used_at_start_of_incremental_);
    857   if (size_of_old_space_multiplied_by_n_during_marking) {
    858     speed_up = true;
    859     if (FLAG_trace_gc) {
    860       PrintPID("Speed up marking because of heap size increase\n");
    861     }
    862   }
    863 
    864   int64_t promoted_during_marking =
    865       heap_->PromotedTotalSize() -
    866       old_generation_space_used_at_start_of_incremental_;
    867   intptr_t delay = marking_speed_ * MB;
    868   intptr_t scavenge_slack = heap_->MaxSemiSpaceSize();
    869 
    870   // We try to scan at at least twice the speed that we are allocating.
    871   if (promoted_during_marking > bytes_scanned_ / 2 + scavenge_slack + delay) {
    872     if (FLAG_trace_gc) {
    873       PrintPID("Speed up marking because marker was not keeping up\n");
    874     }
    875     speed_up = true;
    876   }
    877 
    878   if (speed_up) {
    879     if (state_ != MARKING) {
    880       if (FLAG_trace_gc) {
    881         PrintPID("Postponing speeding up marking until marking starts\n");
    882       }
    883     } else {
    884       marking_speed_ += kMarkingSpeedAccelleration;
    885       marking_speed_ = static_cast<int>(
    886           Min(kMaxMarkingSpeed, static_cast<intptr_t>(marking_speed_ * 1.3)));
    887       if (FLAG_trace_gc) {
    888         PrintPID("Marking speed increased to %d\n", marking_speed_);
    889       }
    890     }
    891   }
    892 }
    893 
    894 
    895 void IncrementalMarking::Step(intptr_t allocated_bytes, CompletionAction action,
    896                               bool force_marking) {
    897   if (heap_->gc_state() != Heap::NOT_IN_GC || !FLAG_incremental_marking ||
    898       !FLAG_incremental_marking_steps ||
    899       (state_ != SWEEPING && state_ != MARKING)) {
    900     return;
    901   }
    902 
    903   allocated_ += allocated_bytes;
    904 
    905   if (!force_marking && allocated_ < kAllocatedThreshold &&
    906       write_barriers_invoked_since_last_step_ <
    907           kWriteBarriersInvokedThreshold) {
    908     return;
    909   }
    910 
    911   if (state_ == MARKING && no_marking_scope_depth_ > 0) return;
    912 
    913   {
    914     HistogramTimerScope incremental_marking_scope(
    915         heap_->isolate()->counters()->gc_incremental_marking());
    916     double start = base::OS::TimeCurrentMillis();
    917 
    918     // The marking speed is driven either by the allocation rate or by the rate
    919     // at which we are having to check the color of objects in the write
    920     // barrier.
    921     // It is possible for a tight non-allocating loop to run a lot of write
    922     // barriers before we get here and check them (marking can only take place
    923     // on
    924     // allocation), so to reduce the lumpiness we don't use the write barriers
    925     // invoked since last step directly to determine the amount of work to do.
    926     intptr_t bytes_to_process =
    927         marking_speed_ *
    928         Max(allocated_, write_barriers_invoked_since_last_step_);
    929     allocated_ = 0;
    930     write_barriers_invoked_since_last_step_ = 0;
    931 
    932     bytes_scanned_ += bytes_to_process;
    933     intptr_t bytes_processed = 0;
    934 
    935     if (state_ == SWEEPING) {
    936       if (heap_->mark_compact_collector()->sweeping_in_progress() &&
    937           heap_->mark_compact_collector()->IsSweepingCompleted()) {
    938         heap_->mark_compact_collector()->EnsureSweepingCompleted();
    939       }
    940       if (!heap_->mark_compact_collector()->sweeping_in_progress()) {
    941         bytes_scanned_ = 0;
    942         StartMarking(PREVENT_COMPACTION);
    943       }
    944     } else if (state_ == MARKING) {
    945       bytes_processed = ProcessMarkingDeque(bytes_to_process);
    946       if (marking_deque_.IsEmpty()) MarkingComplete(action);
    947     }
    948 
    949     steps_count_++;
    950 
    951     // Speed up marking if we are marking too slow or if we are almost done
    952     // with marking.
    953     SpeedUp();
    954 
    955     double end = base::OS::TimeCurrentMillis();
    956     double duration = (end - start);
    957     // Note that we report zero bytes here when sweeping was in progress or
    958     // when we just started incremental marking. In these cases we did not
    959     // process the marking deque.
    960     heap_->tracer()->AddIncrementalMarkingStep(duration, bytes_processed);
    961   }
    962 }
    963 
    964 
    965 void IncrementalMarking::ResetStepCounters() {
    966   steps_count_ = 0;
    967   old_generation_space_available_at_start_of_incremental_ =
    968       SpaceLeftInOldSpace();
    969   old_generation_space_used_at_start_of_incremental_ =
    970       heap_->PromotedTotalSize();
    971   bytes_rescanned_ = 0;
    972   marking_speed_ = kInitialMarkingSpeed;
    973   bytes_scanned_ = 0;
    974   write_barriers_invoked_since_last_step_ = 0;
    975 }
    976 
    977 
    978 int64_t IncrementalMarking::SpaceLeftInOldSpace() {
    979   return heap_->MaxOldGenerationSize() - heap_->PromotedSpaceSizeOfObjects();
    980 }
    981 }
    982 }  // namespace v8::internal
    983