// Copyright 2017 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "src/heap/concurrent-marking.h"

#include <stack>
#include <unordered_map>

#include "include/v8config.h"
#include "src/base/template-utils.h"
#include "src/execution/isolate.h"
#include "src/heap/gc-tracer.h"
#include "src/heap/heap-inl.h"
#include "src/heap/heap.h"
#include "src/heap/mark-compact-inl.h"
#include "src/heap/mark-compact.h"
#include "src/heap/marking.h"
#include "src/heap/objects-visiting-inl.h"
#include "src/heap/objects-visiting.h"
#include "src/heap/worklist.h"
#include "src/init/v8.h"
#include "src/objects/data-handler-inl.h"
#include "src/objects/embedder-data-array-inl.h"
#include "src/objects/hash-table-inl.h"
#include "src/objects/slots-inl.h"
#include "src/objects/transitions-inl.h"
#include "src/utils/utils-inl.h"
#include "src/utils/utils.h"

namespace v8 {
namespace internal {

class ConcurrentMarkingState final
    : public MarkingStateBase<ConcurrentMarkingState, AccessMode::ATOMIC> {
 public:
  explicit ConcurrentMarkingState(MemoryChunkDataMap* memory_chunk_data)
      : memory_chunk_data_(memory_chunk_data) {}

  ConcurrentBitmap<AccessMode::ATOMIC>* bitmap(const MemoryChunk* chunk) {
    DCHECK_EQ(reinterpret_cast<intptr_t>(&chunk->marking_bitmap_) -
                  reinterpret_cast<intptr_t>(chunk),
              MemoryChunk::kMarkBitmapOffset);
    return chunk->marking_bitmap<AccessMode::ATOMIC>();
  }

  void IncrementLiveBytes(MemoryChunk* chunk, intptr_t by) {
    (*memory_chunk_data_)[chunk].live_bytes += by;
  }

  // The live_bytes and SetLiveBytes methods of the marking state are
  // not used by the concurrent marker.

 private:
  MemoryChunkDataMap* memory_chunk_data_;
};

// Helper class for storing in-object slot addresses and values.
class SlotSnapshot {
 public:
  SlotSnapshot() : number_of_slots_(0) {}
  int number_of_slots() const { return number_of_slots_; }
  ObjectSlot slot(int i) const { return snapshot_[i].first; }
  Object value(int i) const { return snapshot_[i].second; }
  void clear() { number_of_slots_ = 0; }
  void add(ObjectSlot slot, Object value) {
    snapshot_[number_of_slots_++] = {slot, value};
  }

 private:
  static const int kMaxSnapshotSize = JSObject::kMaxInstanceSize / kTaggedSize;
  int number_of_slots_;
  std::pair<ObjectSlot, Object> snapshot_[kMaxSnapshotSize];
  DISALLOW_COPY_AND_ASSIGN(SlotSnapshot);
};

class ConcurrentMarkingVisitor final
    : public HeapVisitor<int, ConcurrentMarkingVisitor> {
 public:
  using BaseClass = HeapVisitor<int, ConcurrentMarkingVisitor>;

  explicit ConcurrentMarkingVisitor(
      ConcurrentMarking::MarkingWorklist* shared,
      MemoryChunkDataMap* memory_chunk_data, WeakObjects* weak_objects,
      ConcurrentMarking::EmbedderTracingWorklist* embedder_objects, int task_id,
      bool embedder_tracing_enabled, unsigned mark_compact_epoch,
      bool is_forced_gc)
      : shared_(shared, task_id),
        weak_objects_(weak_objects),
        embedder_objects_(embedder_objects, task_id),
        marking_state_(memory_chunk_data),
        memory_chunk_data_(memory_chunk_data),
        task_id_(task_id),
        embedder_tracing_enabled_(embedder_tracing_enabled),
        mark_compact_epoch_(mark_compact_epoch),
        is_forced_gc_(is_forced_gc) {
    // It is not safe to access flags from concurrent marking visitor. So
    // set the bytecode flush mode based on the flags here
    bytecode_flush_mode_ = Heap::GetBytecodeFlushMode();
  }

  template <typename T>
  static V8_INLINE T Cast(HeapObject object) {
    return T::cast(object);
  }

  bool ShouldVisit(HeapObject object) {
    return marking_state_.GreyToBlack(object);
  }

  bool AllowDefaultJSObjectVisit() { return false; }

  template <typename THeapObjectSlot>
  void ProcessStrongHeapObject(HeapObject host, THeapObjectSlot slot,
                               HeapObject heap_object) {
    MarkObject(heap_object);
    MarkCompactCollector::RecordSlot(host, slot, heap_object);
  }

  template <typename THeapObjectSlot>
  void ProcessWeakHeapObject(HeapObject host, THeapObjectSlot slot,
                             HeapObject heap_object) {
#ifdef THREAD_SANITIZER
    MemoryChunk::FromHeapObject(heap_object)->SynchronizedHeapLoad();
#endif
    if (marking_state_.IsBlackOrGrey(heap_object)) {
      // Weak references with live values are directly processed here to
      // reduce the processing time of weak cells during the main GC
      // pause.
      MarkCompactCollector::RecordSlot(host, slot, heap_object);
    } else {
      // If we do not know about liveness of the value, we have to process
      // the reference when we know the liveness of the whole transitive
      // closure.
      weak_objects_->weak_references.Push(task_id_, std::make_pair(host, slot));
    }
  }

  void VisitPointers(HeapObject host, ObjectSlot start,
                     ObjectSlot end) override {
    VisitPointersImpl(host, start, end);
  }

  void VisitPointers(HeapObject host, MaybeObjectSlot start,
                     MaybeObjectSlot end) override {
    VisitPointersImpl(host, start, end);
  }

  template <typename TSlot>
  V8_INLINE void VisitPointersImpl(HeapObject host, TSlot start, TSlot end) {
    using THeapObjectSlot = typename TSlot::THeapObjectSlot;
    for (TSlot slot = start; slot < end; ++slot) {
      typename TSlot::TObject object = slot.Relaxed_Load();
      HeapObject heap_object;
      if (object.GetHeapObjectIfStrong(&heap_object)) {
        // If the reference changes concurrently from strong to weak, the write
        // barrier will treat the weak reference as strong, so we won't miss the
        // weak reference.
        ProcessStrongHeapObject(host, THeapObjectSlot(slot), heap_object);
      } else if (TSlot::kCanBeWeak &&
                 object.GetHeapObjectIfWeak(&heap_object)) {
        ProcessWeakHeapObject(host, THeapObjectSlot(slot), heap_object);
      }
    }
  }

  // Weak list pointers should be ignored during marking. The lists are
  // reconstructed after GC.
  void VisitCustomWeakPointers(HeapObject host, ObjectSlot start,
                               ObjectSlot end) final {}

  void VisitEmbeddedPointer(Code host, RelocInfo* rinfo) final {
    DCHECK(RelocInfo::IsEmbeddedObjectMode(rinfo->rmode()));
    HeapObject object = rinfo->target_object();
    RecordRelocSlot(host, rinfo, object);
    if (!marking_state_.IsBlackOrGrey(object)) {
      if (host.IsWeakObject(object)) {
        weak_objects_->weak_objects_in_code.Push(task_id_,
                                                 std::make_pair(object, host));
      } else {
        MarkObject(object);
      }
    }
  }

  void VisitCodeTarget(Code host, RelocInfo* rinfo) final {
    DCHECK(RelocInfo::IsCodeTargetMode(rinfo->rmode()));
    Code target = Code::GetCodeFromTargetAddress(rinfo->target_address());
    RecordRelocSlot(host, rinfo, target);
    MarkObject(target);
  }

  void VisitPointersInSnapshot(HeapObject host, const SlotSnapshot& snapshot) {
    for (int i = 0; i < snapshot.number_of_slots(); i++) {
      ObjectSlot slot = snapshot.slot(i);
      Object object = snapshot.value(i);
      DCHECK(!HasWeakHeapObjectTag(object));
      if (!object.IsHeapObject()) continue;
      HeapObject heap_object = HeapObject::cast(object);
      MarkObject(heap_object);
      MarkCompactCollector::RecordSlot(host, slot, heap_object);
    }
  }

  // ===========================================================================
  // JS object =================================================================
  // ===========================================================================

  int VisitJSObject(Map map, JSObject object) {
    return VisitJSObjectSubclass(map, object);
  }

  int VisitJSObjectFast(Map map, JSObject object) {
    return VisitJSObjectSubclassFast(map, object);
  }

  int VisitWasmInstanceObject(Map map, WasmInstanceObject object) {
    return VisitJSObjectSubclass(map, object);
  }

  int VisitJSWeakRef(Map map, JSWeakRef weak_ref) {
    int size = VisitJSObjectSubclass(map, weak_ref);
    if (size == 0) {
      return 0;
    }
    if (weak_ref.target().IsHeapObject()) {
      HeapObject target = HeapObject::cast(weak_ref.target());
      if (marking_state_.IsBlackOrGrey(target)) {
        // Record the slot inside the JSWeakRef, since the
        // VisitJSObjectSubclass above didn't visit it.
        ObjectSlot slot = weak_ref.RawField(JSWeakRef::kTargetOffset);
        MarkCompactCollector::RecordSlot(weak_ref, slot, target);
      } else {
        // JSWeakRef points to a potentially dead object. We have to process
        // them when we know the liveness of the whole transitive closure.
        weak_objects_->js_weak_refs.Push(task_id_, weak_ref);
      }
    }
    return size;
  }

  int VisitWeakCell(Map map, WeakCell weak_cell) {
    if (!ShouldVisit(weak_cell)) return 0;

    int size = WeakCell::BodyDescriptor::SizeOf(map, weak_cell);
    VisitMapPointer(weak_cell);
    WeakCell::BodyDescriptor::IterateBody(map, weak_cell, size, this);
    if (weak_cell.target().IsHeapObject()) {
      HeapObject target = HeapObject::cast(weak_cell.target());
      if (marking_state_.IsBlackOrGrey(target)) {
        // Record the slot inside the WeakCell, since the IterateBody above
        // didn't visit it.
        ObjectSlot slot = weak_cell.RawField(WeakCell::kTargetOffset);
        MarkCompactCollector::RecordSlot(weak_cell, slot, target);
      } else {
        // WeakCell points to a potentially dead object. We have to process
        // them when we know the liveness of the whole transitive closure.
        weak_objects_->weak_cells.Push(task_id_, weak_cell);
      }
    }
    return size;
  }

  // Some JS objects can carry back links to embedders that contain information
  // relevant to the garbage collectors.

  int VisitJSApiObject(Map map, JSObject object) {
    return VisitEmbedderTracingSubclass(map, object);
  }

  int VisitJSArrayBuffer(Map map, JSArrayBuffer object) {
    return VisitEmbedderTracingSubclass(map, object);
  }

  int VisitJSDataView(Map map, JSDataView object) {
    return VisitEmbedderTracingSubclass(map, object);
  }

  int VisitJSTypedArray(Map map, JSTypedArray object) {
    return VisitEmbedderTracingSubclass(map, object);
  }

  // ===========================================================================
  // Strings with pointers =====================================================
  // ===========================================================================

  int VisitConsString(Map map, ConsString object) {
    return VisitFullyWithSnapshot(map, object);
  }

  int VisitSlicedString(Map map, SlicedString object) {
    return VisitFullyWithSnapshot(map, object);
  }

  int VisitThinString(Map map, ThinString object) {
    return VisitFullyWithSnapshot(map, object);
  }

  // ===========================================================================
  // Strings without pointers ==================================================
  // ===========================================================================

  int VisitSeqOneByteString(Map map, SeqOneByteString object) {
    if (!ShouldVisit(object)) return 0;
    VisitMapPointer(object);
    return SeqOneByteString::SizeFor(object.synchronized_length());
  }

  int VisitSeqTwoByteString(Map map, SeqTwoByteString object) {
    if (!ShouldVisit(object)) return 0;
    VisitMapPointer(object);
    return SeqTwoByteString::SizeFor(object.synchronized_length());
  }

  // ===========================================================================
  // Fixed array object ========================================================
  // ===========================================================================

  int VisitFixedArrayWithProgressBar(Map map, FixedArray object,
                                     MemoryChunk* chunk) {
    // The concurrent marker can process larger chunks than the main thread
    // marker.
    const int kProgressBarScanningChunk =
        RoundUp(kMaxRegularHeapObjectSize, kTaggedSize);
    DCHECK(marking_state_.IsBlackOrGrey(object));
    marking_state_.GreyToBlack(object);
    int size = FixedArray::BodyDescriptor::SizeOf(map, object);
    size_t current_progress_bar = chunk->ProgressBar();
    int start = static_cast<int>(current_progress_bar);
    if (start == 0) start = FixedArray::BodyDescriptor::kStartOffset;
    int end = Min(size, start + kProgressBarScanningChunk);
    if (start < end) {
      VisitPointers(object, object.RawField(start), object.RawField(end));
      bool success = chunk->TrySetProgressBar(current_progress_bar, end);
      CHECK(success);
      if (end < size) {
        // The object can be pushed back onto the marking worklist only after
        // progress bar was updated.
        shared_.Push(object);
      }
    }
    return end - start;
  }

  int VisitFixedArray(Map map, FixedArray object) {
    // Arrays with the progress bar are not left-trimmable because they reside
    // in the large object space.
    MemoryChunk* chunk = MemoryChunk::FromHeapObject(object);
    return chunk->IsFlagSet<AccessMode::ATOMIC>(MemoryChunk::HAS_PROGRESS_BAR)
               ? VisitFixedArrayWithProgressBar(map, object, chunk)
               : VisitLeftTrimmableArray(map, object);
  }

  int VisitFixedDoubleArray(Map map, FixedDoubleArray object) {
    return VisitLeftTrimmableArray(map, object);
  }

  // ===========================================================================
  // Side-effectful visitation.
  // ===========================================================================

  int VisitSharedFunctionInfo(Map map, SharedFunctionInfo shared_info) {
    if (!ShouldVisit(shared_info)) return 0;

    int size = SharedFunctionInfo::BodyDescriptor::SizeOf(map, shared_info);
    VisitMapPointer(shared_info);
    SharedFunctionInfo::BodyDescriptor::IterateBody(map, shared_info, size,
                                                    this);

    // If the SharedFunctionInfo has old bytecode, mark it as flushable,
    // otherwise visit the function data field strongly.
    if (shared_info.ShouldFlushBytecode(bytecode_flush_mode_)) {
      weak_objects_->bytecode_flushing_candidates.Push(task_id_, shared_info);
    } else {
      VisitPointer(shared_info, shared_info.RawField(
                                    SharedFunctionInfo::kFunctionDataOffset));
    }
    return size;
  }

  int VisitBytecodeArray(Map map, BytecodeArray object) {
    if (!ShouldVisit(object)) return 0;
    int size = BytecodeArray::BodyDescriptor::SizeOf(map, object);
    VisitMapPointer(object);
    BytecodeArray::BodyDescriptor::IterateBody(map, object, size, this);
    if (!is_forced_gc_) {
      object.MakeOlder();
    }
    return size;
  }

  int VisitJSFunction(Map map, JSFunction object) {
    int size = VisitJSObjectSubclass(map, object);

    // Check if the JSFunction needs reset due to bytecode being flushed.
    if (bytecode_flush_mode_ != BytecodeFlushMode::kDoNotFlushBytecode &&
        object.NeedsResetDueToFlushedBytecode()) {
      weak_objects_->flushed_js_functions.Push(task_id_, object);
    }

    return size;
  }

  int VisitMap(Map meta_map, Map map) {
    if (!ShouldVisit(map)) return 0;
    int size = Map::BodyDescriptor::SizeOf(meta_map, map);
    if (map.CanTransition()) {
      // Maps that can transition share their descriptor arrays and require
      // special visiting logic to avoid memory leaks.
      // Since descriptor arrays are potentially shared, ensure that only the
      // descriptors that belong to this map are marked. The first time a
      // non-empty descriptor array is marked, its header is also visited. The
      // slot holding the descriptor array will be implicitly recorded when the
      // pointer fields of this map are visited.
      DescriptorArray descriptors = map.synchronized_instance_descriptors();
      MarkDescriptorArrayBlack(descriptors);
      int number_of_own_descriptors = map.NumberOfOwnDescriptors();
      if (number_of_own_descriptors) {
        // It is possible that the concurrent marker observes the
        // number_of_own_descriptors out of sync with the descriptors. In that
        // case the marking write barrier for the descriptor array will ensure
        // that all required descriptors are marked. The concurrent marker
        // just should avoid crashing in that case. That's why we need the
        // std::min<int>() below.
        VisitDescriptors(descriptors,
                         std::min<int>(number_of_own_descriptors,
                                       descriptors.number_of_descriptors()));
      }
      // Mark the pointer fields of the Map. Since the transitions array has
      // been marked already, it is fine that one of these fields contains a
      // pointer to it.
    }
    Map::BodyDescriptor::IterateBody(meta_map, map, size, this);
    return size;
  }

  void VisitDescriptors(DescriptorArray descriptor_array,
                        int number_of_own_descriptors) {
    int16_t new_marked = static_cast<int16_t>(number_of_own_descriptors);
    int16_t old_marked = descriptor_array.UpdateNumberOfMarkedDescriptors(
        mark_compact_epoch_, new_marked);
    if (old_marked < new_marked) {
      VisitPointers(
          descriptor_array,
          MaybeObjectSlot(descriptor_array.GetDescriptorSlot(old_marked)),
          MaybeObjectSlot(descriptor_array.GetDescriptorSlot(new_marked)));
    }
  }

  int VisitDescriptorArray(Map map, DescriptorArray array) {
    if (!ShouldVisit(array)) return 0;
    VisitMapPointer(array);
    int size = DescriptorArray::BodyDescriptor::SizeOf(map, array);
    VisitPointers(array, array.GetFirstPointerSlot(),
                  array.GetDescriptorSlot(0));
    VisitDescriptors(array, array.number_of_descriptors());
    return size;
  }

  int VisitTransitionArray(Map map, TransitionArray array) {
    if (!ShouldVisit(array)) return 0;
    VisitMapPointer(array);
    int size = TransitionArray::BodyDescriptor::SizeOf(map, array);
    TransitionArray::BodyDescriptor::IterateBody(map, array, size, this);
    weak_objects_->transition_arrays.Push(task_id_, array);
    return size;
  }

  int VisitJSWeakCollection(Map map, JSWeakCollection object) {
    return VisitJSObjectSubclass(map, object);
  }

  int VisitEphemeronHashTable(Map map, EphemeronHashTable table) {
    if (!ShouldVisit(table)) return 0;
    weak_objects_->ephemeron_hash_tables.Push(task_id_, table);

    for (int i = 0; i < table.Capacity(); i++) {
      ObjectSlot key_slot =
          table.RawFieldOfElementAt(EphemeronHashTable::EntryToIndex(i));
      HeapObject key = HeapObject::cast(table.KeyAt(i));
      MarkCompactCollector::RecordSlot(table, key_slot, key);

      ObjectSlot value_slot =
          table.RawFieldOfElementAt(EphemeronHashTable::EntryToValueIndex(i));

      if (marking_state_.IsBlackOrGrey(key)) {
        VisitPointer(table, value_slot);

      } else {
        Object value_obj = table.ValueAt(i);

        if (value_obj.IsHeapObject()) {
          HeapObject value = HeapObject::cast(value_obj);
          MarkCompactCollector::RecordSlot(table, value_slot, value);

          // Revisit ephemerons with both key and value unreachable at end
          // of concurrent marking cycle.
          if (marking_state_.IsWhite(value)) {
            weak_objects_->discovered_ephemerons.Push(task_id_,
                                                      Ephemeron{key, value});
          }
        }
      }
    }

    return table.SizeFromMap(map);
  }

  // Implements ephemeron semantics: Marks value if key is already reachable.
  // Returns true if value was actually marked.
  bool ProcessEphemeron(HeapObject key, HeapObject value) {
    if (marking_state_.IsBlackOrGrey(key)) {
      if (marking_state_.WhiteToGrey(value)) {
        shared_.Push(value);
        return true;
      }

    } else if (marking_state_.IsWhite(value)) {
      weak_objects_->next_ephemerons.Push(task_id_, Ephemeron{key, value});
    }

    return false;
  }

  void MarkObject(HeapObject object) {
#ifdef THREAD_SANITIZER
    MemoryChunk::FromHeapObject(object)->SynchronizedHeapLoad();
#endif
    if (marking_state_.WhiteToGrey(object)) {
      shared_.Push(object);
    }
  }

  void MarkDescriptorArrayBlack(DescriptorArray descriptors) {
    marking_state_.WhiteToGrey(descriptors);
    if (marking_state_.GreyToBlack(descriptors)) {
      VisitPointers(descriptors, descriptors.GetFirstPointerSlot(),
                    descriptors.GetDescriptorSlot(0));
    }
  }

 private:
  // Helper class for collecting in-object slot addresses and values.
  class SlotSnapshottingVisitor final : public ObjectVisitor {
   public:
    explicit SlotSnapshottingVisitor(SlotSnapshot* slot_snapshot)
        : slot_snapshot_(slot_snapshot) {
      slot_snapshot_->clear();
    }

    void VisitPointers(HeapObject host, ObjectSlot start,
                       ObjectSlot end) override {
      for (ObjectSlot p = start; p < end; ++p) {
        Object object = p.Relaxed_Load();
        slot_snapshot_->add(p, object);
      }
    }

    void VisitPointers(HeapObject host, MaybeObjectSlot start,
                       MaybeObjectSlot end) override {
      // This should never happen, because we don't use snapshotting for objects
      // which contain weak references.
      UNREACHABLE();
    }

    void VisitCodeTarget(Code host, RelocInfo* rinfo) final {
      // This should never happen, because snapshotting is performed only on
      // JSObjects (and derived classes).
      UNREACHABLE();
    }

    void VisitEmbeddedPointer(Code host, RelocInfo* rinfo) final {
      // This should never happen, because snapshotting is performed only on
      // JSObjects (and derived classes).
      UNREACHABLE();
    }

    void VisitCustomWeakPointers(HeapObject host, ObjectSlot start,
                                 ObjectSlot end) override {
      DCHECK(host.IsWeakCell() || host.IsJSWeakRef());
    }

   private:
    SlotSnapshot* slot_snapshot_;
  };

  template <typename T>
  int VisitJSObjectSubclassFast(Map map, T object) {
    DCHECK_IMPLIES(FLAG_unbox_double_fields, map.HasFastPointerLayout());
    using TBodyDescriptor = typename T::FastBodyDescriptor;
    return VisitJSObjectSubclass<T, TBodyDescriptor>(map, object);
  }

  template <typename T, typename TBodyDescriptor = typename T::BodyDescriptor>
  int VisitJSObjectSubclass(Map map, T object) {
    int size = TBodyDescriptor::SizeOf(map, object);
    int used_size = map.UsedInstanceSize();
    DCHECK_LE(used_size, size);
    DCHECK_GE(used_size, T::kHeaderSize);
    return VisitPartiallyWithSnapshot<T, TBodyDescriptor>(map, object,
                                                          used_size, size);
  }

  template <typename T>
  int VisitEmbedderTracingSubclass(Map map, T object) {
    DCHECK(object.IsApiWrapper());
    int size = VisitJSObjectSubclass(map, object);
    if (size && embedder_tracing_enabled_) {
      // Success: The object needs to be processed for embedder references on
      // the main thread.
      embedder_objects_.Push(object);
    }
    return size;
  }

  template <typename T>
  int VisitLeftTrimmableArray(Map map, T object) {
    // The synchronized_length() function checks that the length is a Smi.
    // This is not necessarily the case if the array is being left-trimmed.
    Object length = object.unchecked_synchronized_length();
    if (!ShouldVisit(object)) return 0;
    // The cached length must be the actual length as the array is not black.
    // Left trimming marks the array black before over-writing the length.
    DCHECK(length.IsSmi());
    int size = T::SizeFor(Smi::ToInt(length));
    VisitMapPointer(object);
    T::BodyDescriptor::IterateBody(map, object, size, this);
    return size;
  }

  template <typename T>
  int VisitFullyWithSnapshot(Map map, T object) {
    using TBodyDescriptor = typename T::BodyDescriptor;
    int size = TBodyDescriptor::SizeOf(map, object);
    return VisitPartiallyWithSnapshot<T, TBodyDescriptor>(map, object, size,
                                                          size);
  }

  template <typename T, typename TBodyDescriptor = typename T::BodyDescriptor>
  int VisitPartiallyWithSnapshot(Map map, T object, int used_size, int size) {
    const SlotSnapshot& snapshot =
        MakeSlotSnapshot<T, TBodyDescriptor>(map, object, used_size);
    if (!ShouldVisit(object)) return 0;
    VisitPointersInSnapshot(object, snapshot);
    return size;
  }

  template <typename T, typename TBodyDescriptor>
  const SlotSnapshot& MakeSlotSnapshot(Map map, T object, int size) {
    SlotSnapshottingVisitor visitor(&slot_snapshot_);
    visitor.VisitPointer(object, object.map_slot());
    TBodyDescriptor::IterateBody(map, object, size, &visitor);
    return slot_snapshot_;
  }

  void RecordRelocSlot(Code host, RelocInfo* rinfo, HeapObject target) {
    MarkCompactCollector::RecordRelocSlotInfo info =
        MarkCompactCollector::PrepareRecordRelocSlot(host, rinfo, target);
    if (info.should_record) {
      MemoryChunkData& data = (*memory_chunk_data_)[info.memory_chunk];
      if (!data.typed_slots) {
        data.typed_slots.reset(new TypedSlots());
      }
      data.typed_slots->Insert(info.slot_type, info.offset);
    }
  }

  ConcurrentMarking::MarkingWorklist::View shared_;
  WeakObjects* weak_objects_;
  ConcurrentMarking::EmbedderTracingWorklist::View embedder_objects_;
  ConcurrentMarkingState marking_state_;
  MemoryChunkDataMap* memory_chunk_data_;
  int task_id_;
  SlotSnapshot slot_snapshot_;
  bool embedder_tracing_enabled_;
  const unsigned mark_compact_epoch_;
  bool is_forced_gc_;
  BytecodeFlushMode bytecode_flush_mode_;
};

// Strings can change maps due to conversion to thin string or external strings.
// Use unchecked cast to avoid data race in slow dchecks.
template <>
ConsString ConcurrentMarkingVisitor::Cast(HeapObject object) {
  return ConsString::unchecked_cast(object);
}

template <>
SlicedString ConcurrentMarkingVisitor::Cast(HeapObject object) {
  return SlicedString::unchecked_cast(object);
}

template <>
ThinString ConcurrentMarkingVisitor::Cast(HeapObject object) {
  return ThinString::unchecked_cast(object);
}

template <>
SeqOneByteString ConcurrentMarkingVisitor::Cast(HeapObject object) {
  return SeqOneByteString::unchecked_cast(object);
}

template <>
SeqTwoByteString ConcurrentMarkingVisitor::Cast(HeapObject object) {
  return SeqTwoByteString::unchecked_cast(object);
}

// Fixed array can become a free space during left trimming.
template <>
FixedArray ConcurrentMarkingVisitor::Cast(HeapObject object) {
  return FixedArray::unchecked_cast(object);
}

class ConcurrentMarking::Task : public CancelableTask {
 public:
  Task(Isolate* isolate, ConcurrentMarking* concurrent_marking,
       TaskState* task_state, int task_id)
      : CancelableTask(isolate),
        concurrent_marking_(concurrent_marking),
        task_state_(task_state),
        task_id_(task_id) {}

  ~Task() override = default;

 private:
  // v8::internal::CancelableTask overrides.
  void RunInternal() override {
    concurrent_marking_->Run(task_id_, task_state_);
  }

  ConcurrentMarking* concurrent_marking_;
  TaskState* task_state_;
  int task_id_;
  DISALLOW_COPY_AND_ASSIGN(Task);
};

ConcurrentMarking::ConcurrentMarking(Heap* heap, MarkingWorklist* shared,
                                     MarkingWorklist* on_hold,
                                     WeakObjects* weak_objects,
                                     EmbedderTracingWorklist* embedder_objects)
    : heap_(heap),
      shared_(shared),
      on_hold_(on_hold),
      weak_objects_(weak_objects),
      embedder_objects_(embedder_objects) {
// The runtime flag should be set only if the compile time flag was set.
#ifndef V8_CONCURRENT_MARKING
  CHECK(!FLAG_concurrent_marking && !FLAG_parallel_marking);
#endif
}

void ConcurrentMarking::Run(int task_id, TaskState* task_state) {
  TRACE_BACKGROUND_GC(heap_->tracer(),
                      GCTracer::BackgroundScope::MC_BACKGROUND_MARKING);
  size_t kBytesUntilInterruptCheck = 64 * KB;
  int kObjectsUntilInterrupCheck = 1000;
  ConcurrentMarkingVisitor visitor(
      shared_, &task_state->memory_chunk_data, weak_objects_, embedder_objects_,
      task_id, heap_->local_embedder_heap_tracer()->InUse(),
      task_state->mark_compact_epoch, task_state->is_forced_gc);
  double time_ms;
  size_t marked_bytes = 0;
  if (FLAG_trace_concurrent_marking) {
    heap_->isolate()->PrintWithTimestamp(
        "Starting concurrent marking task %d\n", task_id);
  }
  bool ephemeron_marked = false;

  {
    TimedScope scope(&time_ms);

    {
      Ephemeron ephemeron;

      while (weak_objects_->current_ephemerons.Pop(task_id, &ephemeron)) {
        if (visitor.ProcessEphemeron(ephemeron.key, ephemeron.value)) {
          ephemeron_marked = true;
        }
      }
    }

    bool done = false;
    while (!done) {
      size_t current_marked_bytes = 0;
      int objects_processed = 0;
      while (current_marked_bytes < kBytesUntilInterruptCheck &&
             objects_processed < kObjectsUntilInterrupCheck) {
        HeapObject object;
        if (!shared_->Pop(task_id, &object)) {
          done = true;
          break;
        }
        objects_processed++;
        // The order of the two loads is important.
        Address new_space_top = heap_->new_space()->original_top_acquire();
        Address new_space_limit = heap_->new_space()->original_limit_relaxed();
        Address new_large_object = heap_->new_lo_space()->pending_object();
        Address addr = object.address();
        if ((new_space_top <= addr && addr < new_space_limit) ||
            addr == new_large_object) {
          on_hold_->Push(task_id, object);
        } else {
          Map map = object.synchronized_map();
          current_marked_bytes += visitor.Visit(map, object);
        }
      }
      marked_bytes += current_marked_bytes;
      base::AsAtomicWord::Relaxed_Store<size_t>(&task_state->marked_bytes,
                                                marked_bytes);
      if (task_state->preemption_request) {
        TRACE_EVENT0(TRACE_DISABLED_BY_DEFAULT("v8.gc"),
                     "ConcurrentMarking::Run Preempted");
        break;
      }
    }

    if (done) {
      Ephemeron ephemeron;

      while (weak_objects_->discovered_ephemerons.Pop(task_id, &ephemeron)) {
        if (visitor.ProcessEphemeron(ephemeron.key, ephemeron.value)) {
          ephemeron_marked = true;
        }
      }
    }

    shared_->FlushToGlobal(task_id);
    on_hold_->FlushToGlobal(task_id);
    embedder_objects_->FlushToGlobal(task_id);

    weak_objects_->transition_arrays.FlushToGlobal(task_id);
    weak_objects_->ephemeron_hash_tables.FlushToGlobal(task_id);
    weak_objects_->current_ephemerons.FlushToGlobal(task_id);
    weak_objects_->next_ephemerons.FlushToGlobal(task_id);
    weak_objects_->discovered_ephemerons.FlushToGlobal(task_id);
    weak_objects_->weak_references.FlushToGlobal(task_id);
    weak_objects_->js_weak_refs.FlushToGlobal(task_id);
    weak_objects_->weak_cells.FlushToGlobal(task_id);
    weak_objects_->weak_objects_in_code.FlushToGlobal(task_id);
    weak_objects_->bytecode_flushing_candidates.FlushToGlobal(task_id);
    weak_objects_->flushed_js_functions.FlushToGlobal(task_id);
    base::AsAtomicWord::Relaxed_Store<size_t>(&task_state->marked_bytes, 0);
    total_marked_bytes_ += marked_bytes;

    if (ephemeron_marked) {
      set_ephemeron_marked(true);
    }

    {
      base::MutexGuard guard(&pending_lock_);
      is_pending_[task_id] = false;
      --pending_task_count_;
      pending_condition_.NotifyAll();
    }
  }
  if (FLAG_trace_concurrent_marking) {
    heap_->isolate()->PrintWithTimestamp(
        "Task %d concurrently marked %dKB in %.2fms\n", task_id,
        static_cast<int>(marked_bytes / KB), time_ms);
  }
}

void ConcurrentMarking::ScheduleTasks() {
  DCHECK(FLAG_parallel_marking || FLAG_concurrent_marking);
  DCHECK(!heap_->IsTearingDown());
  base::MutexGuard guard(&pending_lock_);
  DCHECK_EQ(0, pending_task_count_);
  if (task_count_ == 0) {
    static const int num_cores =
        V8::GetCurrentPlatform()->NumberOfWorkerThreads() + 1;
#if defined(V8_OS_MACOSX)
    // Mac OSX 10.11 and prior seems to have trouble when doing concurrent
    // marking on competing hyper-threads (regresses Octane/Splay). As such,
    // only use num_cores/2, leaving one of those for the main thread.
    // TODO(ulan): Use all cores on Mac 10.12+.
    task_count_ = Max(1, Min(kMaxTasks, (num_cores / 2) - 1));
#else   // defined(OS_MACOSX)
    // On other platforms use all logical cores, leaving one for the main
    // thread.
    task_count_ = Max(1, Min(kMaxTasks, num_cores - 1));
#endif  // defined(OS_MACOSX)
  }
  // Task id 0 is for the main thread.
  for (int i = 1; i <= task_count_; i++) {
    if (!is_pending_[i]) {
      if (FLAG_trace_concurrent_marking) {
        heap_->isolate()->PrintWithTimestamp(
            "Scheduling concurrent marking task %d\n", i);
      }
      task_state_[i].preemption_request = false;
      task_state_[i].mark_compact_epoch =
          heap_->mark_compact_collector()->epoch();
      task_state_[i].is_forced_gc = heap_->is_current_gc_forced();
      is_pending_[i] = true;
      ++pending_task_count_;
      auto task =
          base::make_unique<Task>(heap_->isolate(), this, &task_state_[i], i);
      cancelable_id_[i] = task->id();
      V8::GetCurrentPlatform()->CallOnWorkerThread(std::move(task));
    }
  }
  DCHECK_EQ(task_count_, pending_task_count_);
}

void ConcurrentMarking::RescheduleTasksIfNeeded() {
  DCHECK(FLAG_parallel_marking || FLAG_concurrent_marking);
  if (heap_->IsTearingDown()) return;
  {
    base::MutexGuard guard(&pending_lock_);
    if (pending_task_count_ > 0) return;
  }
  if (!shared_->IsGlobalPoolEmpty() ||
      !weak_objects_->current_ephemerons.IsEmpty() ||
      !weak_objects_->discovered_ephemerons.IsEmpty()) {
    ScheduleTasks();
  }
}

bool ConcurrentMarking::Stop(StopRequest stop_request) {
  DCHECK(FLAG_parallel_marking || FLAG_concurrent_marking);
  base::MutexGuard guard(&pending_lock_);

  if (pending_task_count_ == 0) return false;

  if (stop_request != StopRequest::COMPLETE_TASKS_FOR_TESTING) {
    CancelableTaskManager* task_manager =
        heap_->isolate()->cancelable_task_manager();
    for (int i = 1; i <= task_count_; i++) {
      if (is_pending_[i]) {
        if (task_manager->TryAbort(cancelable_id_[i]) ==
            TryAbortResult::kTaskAborted) {
          is_pending_[i] = false;
          --pending_task_count_;
        } else if (stop_request == StopRequest::PREEMPT_TASKS) {
          task_state_[i].preemption_request = true;
        }
      }
    }
  }
  while (pending_task_count_ > 0) {
    pending_condition_.Wait(&pending_lock_);
  }
  for (int i = 1; i <= task_count_; i++) {
    DCHECK(!is_pending_[i]);
  }
  return true;
}

bool ConcurrentMarking::IsStopped() {
  if (!FLAG_concurrent_marking) return true;

  base::MutexGuard guard(&pending_lock_);
  return pending_task_count_ == 0;
}

void ConcurrentMarking::FlushMemoryChunkData(
    MajorNonAtomicMarkingState* marking_state) {
  DCHECK_EQ(pending_task_count_, 0);
  for (int i = 1; i <= task_count_; i++) {
    MemoryChunkDataMap& memory_chunk_data = task_state_[i].memory_chunk_data;
    for (auto& pair : memory_chunk_data) {
      // ClearLiveness sets the live bytes to zero.
      // Pages with zero live bytes might be already unmapped.
      MemoryChunk* memory_chunk = pair.first;
      MemoryChunkData& data = pair.second;
      if (data.live_bytes) {
        marking_state->IncrementLiveBytes(memory_chunk, data.live_bytes);
      }
      if (data.typed_slots) {
        RememberedSet<OLD_TO_OLD>::MergeTyped(memory_chunk,
                                              std::move(data.typed_slots));
      }
    }
    memory_chunk_data.clear();
    task_state_[i].marked_bytes = 0;
  }
  total_marked_bytes_ = 0;
}

void ConcurrentMarking::ClearMemoryChunkData(MemoryChunk* chunk) {
  for (int i = 1; i <= task_count_; i++) {
    auto it = task_state_[i].memory_chunk_data.find(chunk);
    if (it != task_state_[i].memory_chunk_data.end()) {
      it->second.live_bytes = 0;
      it->second.typed_slots.reset();
    }
  }
}

size_t ConcurrentMarking::TotalMarkedBytes() {
  size_t result = 0;
  for (int i = 1; i <= task_count_; i++) {
    result +=
        base::AsAtomicWord::Relaxed_Load<size_t>(&task_state_[i].marked_bytes);
  }
  result += total_marked_bytes_;
  return result;
}

ConcurrentMarking::PauseScope::PauseScope(ConcurrentMarking* concurrent_marking)
    : concurrent_marking_(concurrent_marking),
      resume_on_exit_(FLAG_concurrent_marking &&
                      concurrent_marking_->Stop(
                          ConcurrentMarking::StopRequest::PREEMPT_TASKS)) {
  DCHECK_IMPLIES(resume_on_exit_, FLAG_concurrent_marking);
}

ConcurrentMarking::PauseScope::~PauseScope() {
  if (resume_on_exit_) concurrent_marking_->RescheduleTasksIfNeeded();
}

}  // namespace internal
}  // namespace v8