1// Copyright 2011 the V8 project authors. All rights reserved.
2// Redistribution and use in source and binary forms, with or without
3// modification, are permitted provided that the following conditions are
4// met:
5//
6//     * Redistributions of source code must retain the above copyright
7//       notice, this list of conditions and the following disclaimer.
8//     * Redistributions in binary form must reproduce the above
9//       copyright notice, this list of conditions and the following
10//       disclaimer in the documentation and/or other materials provided
11//       with the distribution.
12//     * Neither the name of Google Inc. nor the names of its
13//       contributors may be used to endorse or promote products derived
14//       from this software without specific prior written permission.
15//
16// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
19// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
20// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
22// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
26// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27
28#include "v8.h"
29
30#include "incremental-marking.h"
31
32#include "code-stubs.h"
33#include "compilation-cache.h"
34#include "v8conversions.h"
35
36namespace v8 {
37namespace internal {
38
39
40IncrementalMarking::IncrementalMarking(Heap* heap)
41    : heap_(heap),
42      state_(STOPPED),
43      marking_deque_memory_(NULL),
44      marking_deque_memory_committed_(false),
45      steps_count_(0),
46      steps_took_(0),
47      longest_step_(0.0),
48      old_generation_space_available_at_start_of_incremental_(0),
49      old_generation_space_used_at_start_of_incremental_(0),
50      steps_count_since_last_gc_(0),
51      steps_took_since_last_gc_(0),
52      should_hurry_(false),
53      allocation_marking_factor_(0),
54      allocated_(0),
55      no_marking_scope_depth_(0) {
56}
57
58
59void IncrementalMarking::TearDown() {
60  delete marking_deque_memory_;
61}
62
63
64void IncrementalMarking::RecordWriteSlow(HeapObject* obj,
65                                         Object** slot,
66                                         Object* value) {
67  if (BaseRecordWrite(obj, slot, value) && is_compacting_ && slot != NULL) {
68    MarkBit obj_bit = Marking::MarkBitFrom(obj);
69    if (Marking::IsBlack(obj_bit)) {
70      // Object is not going to be rescanned we need to record the slot.
71      heap_->mark_compact_collector()->RecordSlot(
72          HeapObject::RawField(obj, 0), slot, value);
73    }
74  }
75}
76
77
78void IncrementalMarking::RecordWriteFromCode(HeapObject* obj,
79                                             Object* value,
80                                             Isolate* isolate) {
81  ASSERT(obj->IsHeapObject());
82
83  // Fast cases should already be covered by RecordWriteStub.
84  ASSERT(value->IsHeapObject());
85  ASSERT(!value->IsHeapNumber());
86  ASSERT(!value->IsString() ||
87         value->IsConsString() ||
88         value->IsSlicedString());
89  ASSERT(Marking::IsWhite(Marking::MarkBitFrom(HeapObject::cast(value))));
90
91  IncrementalMarking* marking = isolate->heap()->incremental_marking();
92  ASSERT(!marking->is_compacting_);
93  marking->RecordWrite(obj, NULL, value);
94}
95
96
97void IncrementalMarking::RecordWriteForEvacuationFromCode(HeapObject* obj,
98                                                          Object** slot,
99                                                          Isolate* isolate) {
100  IncrementalMarking* marking = isolate->heap()->incremental_marking();
101  ASSERT(marking->is_compacting_);
102  marking->RecordWrite(obj, slot, *slot);
103}
104
105
106void IncrementalMarking::RecordCodeTargetPatch(Code* host,
107                                               Address pc,
108                                               HeapObject* value) {
109  if (IsMarking()) {
110    RelocInfo rinfo(pc, RelocInfo::CODE_TARGET, 0, host);
111    RecordWriteIntoCode(host, &rinfo, value);
112  }
113}
114
115
116void IncrementalMarking::RecordCodeTargetPatch(Address pc, HeapObject* value) {
117  if (IsMarking()) {
118    Code* host = heap_->isolate()->inner_pointer_to_code_cache()->
119        GcSafeFindCodeForInnerPointer(pc);
120    RelocInfo rinfo(pc, RelocInfo::CODE_TARGET, 0, host);
121    RecordWriteIntoCode(host, &rinfo, value);
122  }
123}
124
125
126void IncrementalMarking::RecordWriteOfCodeEntrySlow(JSFunction* host,
127                                                Object** slot,
128                                                Code* value) {
129  if (BaseRecordWrite(host, slot, value) && is_compacting_) {
130    ASSERT(slot != NULL);
131    heap_->mark_compact_collector()->
132        RecordCodeEntrySlot(reinterpret_cast<Address>(slot), value);
133  }
134}
135
136
137void IncrementalMarking::RecordWriteIntoCodeSlow(HeapObject* obj,
138                                                 RelocInfo* rinfo,
139                                                 Object* value) {
140  MarkBit value_bit = Marking::MarkBitFrom(HeapObject::cast(value));
141  if (Marking::IsWhite(value_bit)) {
142    MarkBit obj_bit = Marking::MarkBitFrom(obj);
143    if (Marking::IsBlack(obj_bit)) {
144      BlackToGreyAndUnshift(obj, obj_bit);
145      RestartIfNotMarking();
146    }
147    // Object is either grey or white.  It will be scanned if survives.
148    return;
149  }
150
151  if (is_compacting_) {
152    MarkBit obj_bit = Marking::MarkBitFrom(obj);
153    if (Marking::IsBlack(obj_bit)) {
154      // Object is not going to be rescanned.  We need to record the slot.
155      heap_->mark_compact_collector()->RecordRelocSlot(rinfo,
156                                                       Code::cast(value));
157    }
158  }
159}
160
161
162class IncrementalMarkingMarkingVisitor : public ObjectVisitor {
163 public:
164  IncrementalMarkingMarkingVisitor(Heap* heap,
165                                   IncrementalMarking* incremental_marking)
166      : heap_(heap),
167        incremental_marking_(incremental_marking) {
168  }
169
170  void VisitEmbeddedPointer(RelocInfo* rinfo) {
171    ASSERT(rinfo->rmode() == RelocInfo::EMBEDDED_OBJECT);
172    Object* target = rinfo->target_object();
173    if (target->NonFailureIsHeapObject()) {
174      heap_->mark_compact_collector()->RecordRelocSlot(rinfo, target);
175      MarkObject(target);
176    }
177  }
178
179  void VisitCodeTarget(RelocInfo* rinfo) {
180    ASSERT(RelocInfo::IsCodeTarget(rinfo->rmode()));
181    Code* target = Code::GetCodeFromTargetAddress(rinfo->target_address());
182    if (FLAG_cleanup_code_caches_at_gc && target->is_inline_cache_stub()
183        && (target->ic_age() != heap_->global_ic_age())) {
184      IC::Clear(rinfo->pc());
185      target = Code::GetCodeFromTargetAddress(rinfo->target_address());
186    }
187    heap_->mark_compact_collector()->RecordRelocSlot(rinfo, Code::cast(target));
188    MarkObject(target);
189  }
190
191  void VisitDebugTarget(RelocInfo* rinfo) {
192    ASSERT((RelocInfo::IsJSReturn(rinfo->rmode()) &&
193            rinfo->IsPatchedReturnSequence()) ||
194           (RelocInfo::IsDebugBreakSlot(rinfo->rmode()) &&
195            rinfo->IsPatchedDebugBreakSlotSequence()));
196    Object* target = Code::GetCodeFromTargetAddress(rinfo->call_address());
197    heap_->mark_compact_collector()->RecordRelocSlot(rinfo, Code::cast(target));
198    MarkObject(target);
199  }
200
201  void VisitCodeEntry(Address entry_address) {
202    Object* target = Code::GetObjectFromEntryAddress(entry_address);
203    heap_->mark_compact_collector()->
204        RecordCodeEntrySlot(entry_address, Code::cast(target));
205    MarkObject(target);
206  }
207
208  void VisitSharedFunctionInfo(SharedFunctionInfo* shared) {
209    if (shared->ic_age() != heap_->global_ic_age()) {
210      shared->ResetForNewContext(heap_->global_ic_age());
211    }
212  }
213
214  void VisitPointer(Object** p) {
215    Object* obj = *p;
216    if (obj->NonFailureIsHeapObject()) {
217      heap_->mark_compact_collector()->RecordSlot(p, p, obj);
218      MarkObject(obj);
219    }
220  }
221
222  void VisitPointers(Object** start, Object** end) {
223    for (Object** p = start; p < end; p++) {
224      Object* obj = *p;
225      if (obj->NonFailureIsHeapObject()) {
226        heap_->mark_compact_collector()->RecordSlot(start, p, obj);
227        MarkObject(obj);
228      }
229    }
230  }
231
232 private:
233  // Mark object pointed to by p.
234  INLINE(void MarkObject(Object* obj)) {
235    HeapObject* heap_object = HeapObject::cast(obj);
236    MarkBit mark_bit = Marking::MarkBitFrom(heap_object);
237    if (mark_bit.data_only()) {
238      if (incremental_marking_->MarkBlackOrKeepGrey(mark_bit)) {
239        MemoryChunk::IncrementLiveBytesFromGC(heap_object->address(),
240                                              heap_object->Size());
241      }
242    } else if (Marking::IsWhite(mark_bit)) {
243      incremental_marking_->WhiteToGreyAndPush(heap_object, mark_bit);
244    }
245  }
246
247  Heap* heap_;
248  IncrementalMarking* incremental_marking_;
249};
250
251
252class IncrementalMarkingRootMarkingVisitor : public ObjectVisitor {
253 public:
254  IncrementalMarkingRootMarkingVisitor(Heap* heap,
255                                       IncrementalMarking* incremental_marking)
256      : heap_(heap),
257        incremental_marking_(incremental_marking) {
258  }
259
260  void VisitPointer(Object** p) {
261    MarkObjectByPointer(p);
262  }
263
264  void VisitPointers(Object** start, Object** end) {
265    for (Object** p = start; p < end; p++) MarkObjectByPointer(p);
266  }
267
268 private:
269  void MarkObjectByPointer(Object** p) {
270    Object* obj = *p;
271    if (!obj->IsHeapObject()) return;
272
273    HeapObject* heap_object = HeapObject::cast(obj);
274    MarkBit mark_bit = Marking::MarkBitFrom(heap_object);
275    if (mark_bit.data_only()) {
276      if (incremental_marking_->MarkBlackOrKeepGrey(mark_bit)) {
277          MemoryChunk::IncrementLiveBytesFromGC(heap_object->address(),
278                                                heap_object->Size());
279      }
280    } else {
281      if (Marking::IsWhite(mark_bit)) {
282        incremental_marking_->WhiteToGreyAndPush(heap_object, mark_bit);
283      }
284    }
285  }
286
287  Heap* heap_;
288  IncrementalMarking* incremental_marking_;
289};
290
291
292void IncrementalMarking::SetOldSpacePageFlags(MemoryChunk* chunk,
293                                              bool is_marking,
294                                              bool is_compacting) {
295  if (is_marking) {
296    chunk->SetFlag(MemoryChunk::POINTERS_TO_HERE_ARE_INTERESTING);
297    chunk->SetFlag(MemoryChunk::POINTERS_FROM_HERE_ARE_INTERESTING);
298
299    // It's difficult to filter out slots recorded for large objects.
300    if (chunk->owner()->identity() == LO_SPACE &&
301        chunk->size() > static_cast<size_t>(Page::kPageSize) &&
302        is_compacting) {
303      chunk->SetFlag(MemoryChunk::RESCAN_ON_EVACUATION);
304    }
305  } else if (chunk->owner()->identity() == CELL_SPACE ||
306             chunk->scan_on_scavenge()) {
307    chunk->ClearFlag(MemoryChunk::POINTERS_TO_HERE_ARE_INTERESTING);
308    chunk->ClearFlag(MemoryChunk::POINTERS_FROM_HERE_ARE_INTERESTING);
309  } else {
310    chunk->ClearFlag(MemoryChunk::POINTERS_TO_HERE_ARE_INTERESTING);
311    chunk->SetFlag(MemoryChunk::POINTERS_FROM_HERE_ARE_INTERESTING);
312  }
313}
314
315
316void IncrementalMarking::SetNewSpacePageFlags(NewSpacePage* chunk,
317                                              bool is_marking) {
318  chunk->SetFlag(MemoryChunk::POINTERS_TO_HERE_ARE_INTERESTING);
319  if (is_marking) {
320    chunk->SetFlag(MemoryChunk::POINTERS_FROM_HERE_ARE_INTERESTING);
321  } else {
322    chunk->ClearFlag(MemoryChunk::POINTERS_FROM_HERE_ARE_INTERESTING);
323  }
324  chunk->SetFlag(MemoryChunk::SCAN_ON_SCAVENGE);
325}
326
327
328void IncrementalMarking::DeactivateIncrementalWriteBarrierForSpace(
329    PagedSpace* space) {
330  PageIterator it(space);
331  while (it.has_next()) {
332    Page* p = it.next();
333    SetOldSpacePageFlags(p, false, false);
334  }
335}
336
337
338void IncrementalMarking::DeactivateIncrementalWriteBarrierForSpace(
339    NewSpace* space) {
340  NewSpacePageIterator it(space);
341  while (it.has_next()) {
342    NewSpacePage* p = it.next();
343    SetNewSpacePageFlags(p, false);
344  }
345}
346
347
348void IncrementalMarking::DeactivateIncrementalWriteBarrier() {
349  DeactivateIncrementalWriteBarrierForSpace(heap_->old_pointer_space());
350  DeactivateIncrementalWriteBarrierForSpace(heap_->old_data_space());
351  DeactivateIncrementalWriteBarrierForSpace(heap_->cell_space());
352  DeactivateIncrementalWriteBarrierForSpace(heap_->map_space());
353  DeactivateIncrementalWriteBarrierForSpace(heap_->code_space());
354  DeactivateIncrementalWriteBarrierForSpace(heap_->new_space());
355
356  LargePage* lop = heap_->lo_space()->first_page();
357  while (lop->is_valid()) {
358    SetOldSpacePageFlags(lop, false, false);
359    lop = lop->next_page();
360  }
361}
362
363
364void IncrementalMarking::ActivateIncrementalWriteBarrier(PagedSpace* space) {
365  PageIterator it(space);
366  while (it.has_next()) {
367    Page* p = it.next();
368    SetOldSpacePageFlags(p, true, is_compacting_);
369  }
370}
371
372
373void IncrementalMarking::ActivateIncrementalWriteBarrier(NewSpace* space) {
374  NewSpacePageIterator it(space->ToSpaceStart(), space->ToSpaceEnd());
375  while (it.has_next()) {
376    NewSpacePage* p = it.next();
377    SetNewSpacePageFlags(p, true);
378  }
379}
380
381
382void IncrementalMarking::ActivateIncrementalWriteBarrier() {
383  ActivateIncrementalWriteBarrier(heap_->old_pointer_space());
384  ActivateIncrementalWriteBarrier(heap_->old_data_space());
385  ActivateIncrementalWriteBarrier(heap_->cell_space());
386  ActivateIncrementalWriteBarrier(heap_->map_space());
387  ActivateIncrementalWriteBarrier(heap_->code_space());
388  ActivateIncrementalWriteBarrier(heap_->new_space());
389
390  LargePage* lop = heap_->lo_space()->first_page();
391  while (lop->is_valid()) {
392    SetOldSpacePageFlags(lop, true, is_compacting_);
393    lop = lop->next_page();
394  }
395}
396
397
398bool IncrementalMarking::WorthActivating() {
399#ifndef DEBUG
400  static const intptr_t kActivationThreshold = 8 * MB;
401#else
402  // TODO(gc) consider setting this to some low level so that some
403  // debug tests run with incremental marking and some without.
404  static const intptr_t kActivationThreshold = 0;
405#endif
406
407  return !FLAG_expose_gc &&
408      FLAG_incremental_marking &&
409      !Serializer::enabled() &&
410      heap_->PromotedSpaceSizeOfObjects() > kActivationThreshold;
411}
412
413
414void IncrementalMarking::ActivateGeneratedStub(Code* stub) {
415  ASSERT(RecordWriteStub::GetMode(stub) ==
416         RecordWriteStub::STORE_BUFFER_ONLY);
417
418  if (!IsMarking()) {
419    // Initially stub is generated in STORE_BUFFER_ONLY mode thus
420    // we don't need to do anything if incremental marking is
421    // not active.
422  } else if (IsCompacting()) {
423    RecordWriteStub::Patch(stub, RecordWriteStub::INCREMENTAL_COMPACTION);
424  } else {
425    RecordWriteStub::Patch(stub, RecordWriteStub::INCREMENTAL);
426  }
427}
428
429
430static void PatchIncrementalMarkingRecordWriteStubs(
431    Heap* heap, RecordWriteStub::Mode mode) {
432  UnseededNumberDictionary* stubs = heap->code_stubs();
433
434  int capacity = stubs->Capacity();
435  for (int i = 0; i < capacity; i++) {
436    Object* k = stubs->KeyAt(i);
437    if (stubs->IsKey(k)) {
438      uint32_t key = NumberToUint32(k);
439
440      if (CodeStub::MajorKeyFromKey(key) ==
441          CodeStub::RecordWrite) {
442        Object* e = stubs->ValueAt(i);
443        if (e->IsCode()) {
444          RecordWriteStub::Patch(Code::cast(e), mode);
445        }
446      }
447    }
448  }
449}
450
451
452void IncrementalMarking::EnsureMarkingDequeIsCommitted() {
453  if (marking_deque_memory_ == NULL) {
454    marking_deque_memory_ = new VirtualMemory(4 * MB);
455  }
456  if (!marking_deque_memory_committed_) {
457    bool success = marking_deque_memory_->Commit(
458        reinterpret_cast<Address>(marking_deque_memory_->address()),
459        marking_deque_memory_->size(),
460        false);  // Not executable.
461    CHECK(success);
462    marking_deque_memory_committed_ = true;
463  }
464}
465
466void IncrementalMarking::UncommitMarkingDeque() {
467  if (state_ == STOPPED && marking_deque_memory_committed_) {
468    bool success = marking_deque_memory_->Uncommit(
469        reinterpret_cast<Address>(marking_deque_memory_->address()),
470        marking_deque_memory_->size());
471    CHECK(success);
472    marking_deque_memory_committed_ = false;
473  }
474}
475
476
477void IncrementalMarking::Start() {
478  if (FLAG_trace_incremental_marking) {
479    PrintF("[IncrementalMarking] Start\n");
480  }
481  ASSERT(FLAG_incremental_marking);
482  ASSERT(state_ == STOPPED);
483
484  ResetStepCounters();
485
486  if (heap_->old_pointer_space()->IsSweepingComplete() &&
487      heap_->old_data_space()->IsSweepingComplete()) {
488    StartMarking(ALLOW_COMPACTION);
489  } else {
490    if (FLAG_trace_incremental_marking) {
491      PrintF("[IncrementalMarking] Start sweeping.\n");
492    }
493    state_ = SWEEPING;
494  }
495
496  heap_->new_space()->LowerInlineAllocationLimit(kAllocatedThreshold);
497}
498
499
500static void MarkObjectGreyDoNotEnqueue(Object* obj) {
501  if (obj->IsHeapObject()) {
502    HeapObject* heap_obj = HeapObject::cast(obj);
503    MarkBit mark_bit = Marking::MarkBitFrom(HeapObject::cast(obj));
504    if (Marking::IsBlack(mark_bit)) {
505      MemoryChunk::IncrementLiveBytesFromGC(heap_obj->address(),
506                                            -heap_obj->Size());
507    }
508    Marking::AnyToGrey(mark_bit);
509  }
510}
511
512
513void IncrementalMarking::StartMarking(CompactionFlag flag) {
514  if (FLAG_trace_incremental_marking) {
515    PrintF("[IncrementalMarking] Start marking\n");
516  }
517
518  is_compacting_ = !FLAG_never_compact && (flag == ALLOW_COMPACTION) &&
519      heap_->mark_compact_collector()->StartCompaction(
520          MarkCompactCollector::INCREMENTAL_COMPACTION);
521
522  state_ = MARKING;
523
524  RecordWriteStub::Mode mode = is_compacting_ ?
525      RecordWriteStub::INCREMENTAL_COMPACTION : RecordWriteStub::INCREMENTAL;
526
527  PatchIncrementalMarkingRecordWriteStubs(heap_, mode);
528
529  EnsureMarkingDequeIsCommitted();
530
531  // Initialize marking stack.
532  Address addr = static_cast<Address>(marking_deque_memory_->address());
533  size_t size = marking_deque_memory_->size();
534  if (FLAG_force_marking_deque_overflows) size = 64 * kPointerSize;
535  marking_deque_.Initialize(addr, addr + size);
536
537  ActivateIncrementalWriteBarrier();
538
539#ifdef DEBUG
540  // Marking bits are cleared by the sweeper.
541  if (FLAG_verify_heap) {
542    heap_->mark_compact_collector()->VerifyMarkbitsAreClean();
543  }
544#endif
545
546  heap_->CompletelyClearInstanceofCache();
547  heap_->isolate()->compilation_cache()->MarkCompactPrologue();
548
549  if (FLAG_cleanup_code_caches_at_gc) {
550    // We will mark cache black with a separate pass
551    // when we finish marking.
552    MarkObjectGreyDoNotEnqueue(heap_->polymorphic_code_cache());
553  }
554
555  // Mark strong roots grey.
556  IncrementalMarkingRootMarkingVisitor visitor(heap_, this);
557  heap_->IterateStrongRoots(&visitor, VISIT_ONLY_STRONG);
558
559  // Ready to start incremental marking.
560  if (FLAG_trace_incremental_marking) {
561    PrintF("[IncrementalMarking] Running\n");
562  }
563}
564
565
566void IncrementalMarking::PrepareForScavenge() {
567  if (!IsMarking()) return;
568  NewSpacePageIterator it(heap_->new_space()->FromSpaceStart(),
569                          heap_->new_space()->FromSpaceEnd());
570  while (it.has_next()) {
571    Bitmap::Clear(it.next());
572  }
573}
574
575
576void IncrementalMarking::UpdateMarkingDequeAfterScavenge() {
577  if (!IsMarking()) return;
578
579  int current = marking_deque_.bottom();
580  int mask = marking_deque_.mask();
581  int limit = marking_deque_.top();
582  HeapObject** array = marking_deque_.array();
583  int new_top = current;
584
585  Map* filler_map = heap_->one_pointer_filler_map();
586
587  while (current != limit) {
588    HeapObject* obj = array[current];
589    ASSERT(obj->IsHeapObject());
590    current = ((current + 1) & mask);
591    if (heap_->InNewSpace(obj)) {
592      MapWord map_word = obj->map_word();
593      if (map_word.IsForwardingAddress()) {
594        HeapObject* dest = map_word.ToForwardingAddress();
595        array[new_top] = dest;
596        new_top = ((new_top + 1) & mask);
597        ASSERT(new_top != marking_deque_.bottom());
598#ifdef DEBUG
599        MarkBit mark_bit = Marking::MarkBitFrom(obj);
600        ASSERT(Marking::IsGrey(mark_bit) ||
601               (obj->IsFiller() && Marking::IsWhite(mark_bit)));
602#endif
603      }
604    } else if (obj->map() != filler_map) {
605      // Skip one word filler objects that appear on the
606      // stack when we perform in place array shift.
607      array[new_top] = obj;
608      new_top = ((new_top + 1) & mask);
609      ASSERT(new_top != marking_deque_.bottom());
610#ifdef DEBUG
611        MarkBit mark_bit = Marking::MarkBitFrom(obj);
612        ASSERT(Marking::IsGrey(mark_bit) ||
613               (obj->IsFiller() && Marking::IsWhite(mark_bit)));
614#endif
615    }
616  }
617  marking_deque_.set_top(new_top);
618
619  steps_took_since_last_gc_ = 0;
620  steps_count_since_last_gc_ = 0;
621  longest_step_ = 0.0;
622}
623
624
625void IncrementalMarking::VisitGlobalContext(Context* ctx, ObjectVisitor* v) {
626  v->VisitPointers(
627      HeapObject::RawField(
628          ctx, Context::MarkCompactBodyDescriptor::kStartOffset),
629      HeapObject::RawField(
630          ctx, Context::MarkCompactBodyDescriptor::kEndOffset));
631
632  MarkCompactCollector* collector = heap_->mark_compact_collector();
633  for (int idx = Context::FIRST_WEAK_SLOT;
634       idx < Context::GLOBAL_CONTEXT_SLOTS;
635       ++idx) {
636    Object** slot =
637        HeapObject::RawField(ctx, FixedArray::OffsetOfElementAt(idx));
638    collector->RecordSlot(slot, slot, *slot);
639  }
640}
641
642
643void IncrementalMarking::Hurry() {
644  if (state() == MARKING) {
645    double start = 0.0;
646    if (FLAG_trace_incremental_marking) {
647      PrintF("[IncrementalMarking] Hurry\n");
648      start = OS::TimeCurrentMillis();
649    }
650    // TODO(gc) hurry can mark objects it encounters black as mutator
651    // was stopped.
652    Map* filler_map = heap_->one_pointer_filler_map();
653    Map* global_context_map = heap_->global_context_map();
654    IncrementalMarkingMarkingVisitor marking_visitor(heap_, this);
655    while (!marking_deque_.IsEmpty()) {
656      HeapObject* obj = marking_deque_.Pop();
657
658      // Explicitly skip one word fillers. Incremental markbit patterns are
659      // correct only for objects that occupy at least two words.
660      Map* map = obj->map();
661      if (map == filler_map) {
662        continue;
663      } else if (map == global_context_map) {
664        // Global contexts have weak fields.
665        VisitGlobalContext(Context::cast(obj), &marking_visitor);
666      } else {
667        obj->Iterate(&marking_visitor);
668      }
669
670      MarkBit mark_bit = Marking::MarkBitFrom(obj);
671      ASSERT(!Marking::IsBlack(mark_bit));
672      Marking::MarkBlack(mark_bit);
673      MemoryChunk::IncrementLiveBytesFromGC(obj->address(), obj->Size());
674    }
675    state_ = COMPLETE;
676    if (FLAG_trace_incremental_marking) {
677      double end = OS::TimeCurrentMillis();
678      PrintF("[IncrementalMarking] Complete (hurry), spent %d ms.\n",
679             static_cast<int>(end - start));
680    }
681  }
682
683  if (FLAG_cleanup_code_caches_at_gc) {
684    PolymorphicCodeCache* poly_cache = heap_->polymorphic_code_cache();
685    Marking::GreyToBlack(Marking::MarkBitFrom(poly_cache));
686    MemoryChunk::IncrementLiveBytesFromGC(poly_cache->address(),
687                                          PolymorphicCodeCache::kSize);
688  }
689
690  Object* context = heap_->global_contexts_list();
691  while (!context->IsUndefined()) {
692    // GC can happen when the context is not fully initialized,
693    // so the cache can be undefined.
694    HeapObject* cache = HeapObject::cast(
695        Context::cast(context)->get(Context::NORMALIZED_MAP_CACHE_INDEX));
696    if (!cache->IsUndefined()) {
697      MarkBit mark_bit = Marking::MarkBitFrom(cache);
698      if (Marking::IsGrey(mark_bit)) {
699        Marking::GreyToBlack(mark_bit);
700        MemoryChunk::IncrementLiveBytesFromGC(cache->address(), cache->Size());
701      }
702    }
703    context = Context::cast(context)->get(Context::NEXT_CONTEXT_LINK);
704  }
705}
706
707
708void IncrementalMarking::Abort() {
709  if (IsStopped()) return;
710  if (FLAG_trace_incremental_marking) {
711    PrintF("[IncrementalMarking] Aborting.\n");
712  }
713  heap_->new_space()->LowerInlineAllocationLimit(0);
714  IncrementalMarking::set_should_hurry(false);
715  ResetStepCounters();
716  if (IsMarking()) {
717    PatchIncrementalMarkingRecordWriteStubs(heap_,
718                                            RecordWriteStub::STORE_BUFFER_ONLY);
719    DeactivateIncrementalWriteBarrier();
720
721    if (is_compacting_) {
722      LargeObjectIterator it(heap_->lo_space());
723      for (HeapObject* obj = it.Next(); obj != NULL; obj = it.Next()) {
724        Page* p = Page::FromAddress(obj->address());
725        if (p->IsFlagSet(Page::RESCAN_ON_EVACUATION)) {
726          p->ClearFlag(Page::RESCAN_ON_EVACUATION);
727        }
728      }
729    }
730  }
731  heap_->isolate()->stack_guard()->Continue(GC_REQUEST);
732  state_ = STOPPED;
733  is_compacting_ = false;
734}
735
736
737void IncrementalMarking::Finalize() {
738  Hurry();
739  state_ = STOPPED;
740  is_compacting_ = false;
741  heap_->new_space()->LowerInlineAllocationLimit(0);
742  IncrementalMarking::set_should_hurry(false);
743  ResetStepCounters();
744  PatchIncrementalMarkingRecordWriteStubs(heap_,
745                                          RecordWriteStub::STORE_BUFFER_ONLY);
746  DeactivateIncrementalWriteBarrier();
747  ASSERT(marking_deque_.IsEmpty());
748  heap_->isolate()->stack_guard()->Continue(GC_REQUEST);
749}
750
751
752void IncrementalMarking::MarkingComplete(CompletionAction action) {
753  state_ = COMPLETE;
754  // We will set the stack guard to request a GC now.  This will mean the rest
755  // of the GC gets performed as soon as possible (we can't do a GC here in a
756  // record-write context).  If a few things get allocated between now and then
757  // that shouldn't make us do a scavenge and keep being incremental, so we set
758  // the should-hurry flag to indicate that there can't be much work left to do.
759  set_should_hurry(true);
760  if (FLAG_trace_incremental_marking) {
761    PrintF("[IncrementalMarking] Complete (normal).\n");
762  }
763  if (action == GC_VIA_STACK_GUARD) {
764    heap_->isolate()->stack_guard()->RequestGC();
765  }
766}
767
768
769void IncrementalMarking::Step(intptr_t allocated_bytes,
770                              CompletionAction action) {
771  if (heap_->gc_state() != Heap::NOT_IN_GC ||
772      !FLAG_incremental_marking ||
773      !FLAG_incremental_marking_steps ||
774      (state_ != SWEEPING && state_ != MARKING)) {
775    return;
776  }
777
778  allocated_ += allocated_bytes;
779
780  if (allocated_ < kAllocatedThreshold) return;
781
782  if (state_ == MARKING && no_marking_scope_depth_ > 0) return;
783
784  intptr_t bytes_to_process = allocated_ * allocation_marking_factor_;
785  bytes_scanned_ += bytes_to_process;
786
787  double start = 0;
788
789  if (FLAG_trace_incremental_marking || FLAG_trace_gc) {
790    start = OS::TimeCurrentMillis();
791  }
792
793  if (state_ == SWEEPING) {
794    if (heap_->AdvanceSweepers(static_cast<int>(bytes_to_process))) {
795      bytes_scanned_ = 0;
796      StartMarking(PREVENT_COMPACTION);
797    }
798  } else if (state_ == MARKING) {
799    Map* filler_map = heap_->one_pointer_filler_map();
800    Map* global_context_map = heap_->global_context_map();
801    IncrementalMarkingMarkingVisitor marking_visitor(heap_, this);
802    while (!marking_deque_.IsEmpty() && bytes_to_process > 0) {
803      HeapObject* obj = marking_deque_.Pop();
804
805      // Explicitly skip one word fillers. Incremental markbit patterns are
806      // correct only for objects that occupy at least two words.
807      Map* map = obj->map();
808      if (map == filler_map) continue;
809
810      if (obj->IsMap()) {
811        Map* map = Map::cast(obj);
812        heap_->ClearCacheOnMap(map);
813      }
814
815
816      int size = obj->SizeFromMap(map);
817      bytes_to_process -= size;
818      MarkBit map_mark_bit = Marking::MarkBitFrom(map);
819      if (Marking::IsWhite(map_mark_bit)) {
820        WhiteToGreyAndPush(map, map_mark_bit);
821      }
822
823      // TODO(gc) switch to static visitor instead of normal visitor.
824      if (map == global_context_map) {
825        // Global contexts have weak fields.
826        Context* ctx = Context::cast(obj);
827
828        // We will mark cache black with a separate pass
829        // when we finish marking.
830        MarkObjectGreyDoNotEnqueue(ctx->normalized_map_cache());
831
832        VisitGlobalContext(ctx, &marking_visitor);
833      } else {
834        obj->IterateBody(map->instance_type(), size, &marking_visitor);
835      }
836
837      MarkBit obj_mark_bit = Marking::MarkBitFrom(obj);
838      SLOW_ASSERT(Marking::IsGrey(obj_mark_bit) ||
839                  (obj->IsFiller() && Marking::IsWhite(obj_mark_bit)));
840      Marking::MarkBlack(obj_mark_bit);
841      MemoryChunk::IncrementLiveBytesFromGC(obj->address(), size);
842    }
843    if (marking_deque_.IsEmpty()) MarkingComplete(action);
844  }
845
846  allocated_ = 0;
847
848  steps_count_++;
849  steps_count_since_last_gc_++;
850
851  bool speed_up = false;
852
853  if ((steps_count_ % kAllocationMarkingFactorSpeedupInterval) == 0) {
854    if (FLAG_trace_gc) {
855      PrintF("Speed up marking after %d steps\n",
856             static_cast<int>(kAllocationMarkingFactorSpeedupInterval));
857    }
858    speed_up = true;
859  }
860
861  bool space_left_is_very_small =
862      (old_generation_space_available_at_start_of_incremental_ < 10 * MB);
863
864  bool only_1_nth_of_space_that_was_available_still_left =
865      (SpaceLeftInOldSpace() * (allocation_marking_factor_ + 1) <
866          old_generation_space_available_at_start_of_incremental_);
867
868  if (space_left_is_very_small ||
869      only_1_nth_of_space_that_was_available_still_left) {
870    if (FLAG_trace_gc) PrintF("Speed up marking because of low space left\n");
871    speed_up = true;
872  }
873
874  bool size_of_old_space_multiplied_by_n_during_marking =
875      (heap_->PromotedTotalSize() >
876       (allocation_marking_factor_ + 1) *
877           old_generation_space_used_at_start_of_incremental_);
878  if (size_of_old_space_multiplied_by_n_during_marking) {
879    speed_up = true;
880    if (FLAG_trace_gc) {
881      PrintF("Speed up marking because of heap size increase\n");
882    }
883  }
884
885  int64_t promoted_during_marking = heap_->PromotedTotalSize()
886      - old_generation_space_used_at_start_of_incremental_;
887  intptr_t delay = allocation_marking_factor_ * MB;
888  intptr_t scavenge_slack = heap_->MaxSemiSpaceSize();
889
890  // We try to scan at at least twice the speed that we are allocating.
891  if (promoted_during_marking > bytes_scanned_ / 2 + scavenge_slack + delay) {
892    if (FLAG_trace_gc) {
893      PrintF("Speed up marking because marker was not keeping up\n");
894    }
895    speed_up = true;
896  }
897
898  if (speed_up) {
899    if (state_ != MARKING) {
900      if (FLAG_trace_gc) {
901        PrintF("Postponing speeding up marking until marking starts\n");
902      }
903    } else {
904      allocation_marking_factor_ += kAllocationMarkingFactorSpeedup;
905      allocation_marking_factor_ = static_cast<int>(
906          Min(kMaxAllocationMarkingFactor,
907              static_cast<intptr_t>(allocation_marking_factor_ * 1.3)));
908      if (FLAG_trace_gc) {
909        PrintF("Marking speed increased to %d\n", allocation_marking_factor_);
910      }
911    }
912  }
913
914  if (FLAG_trace_incremental_marking || FLAG_trace_gc) {
915    double end = OS::TimeCurrentMillis();
916    double delta = (end - start);
917    longest_step_ = Max(longest_step_, delta);
918    steps_took_ += delta;
919    steps_took_since_last_gc_ += delta;
920  }
921}
922
923
924void IncrementalMarking::ResetStepCounters() {
925  steps_count_ = 0;
926  steps_took_ = 0;
927  longest_step_ = 0.0;
928  old_generation_space_available_at_start_of_incremental_ =
929      SpaceLeftInOldSpace();
930  old_generation_space_used_at_start_of_incremental_ =
931      heap_->PromotedTotalSize();
932  steps_count_since_last_gc_ = 0;
933  steps_took_since_last_gc_ = 0;
934  bytes_rescanned_ = 0;
935  allocation_marking_factor_ = kInitialAllocationMarkingFactor;
936  bytes_scanned_ = 0;
937}
938
939
940int64_t IncrementalMarking::SpaceLeftInOldSpace() {
941  return heap_->MaxOldGenerationSize() - heap_->PromotedSpaceSize();
942}
943
944} }  // namespace v8::internal
945