// Copyright 2012 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.

#ifndef V8_HEAP_MARK_COMPACT_INL_H_
#define V8_HEAP_MARK_COMPACT_INL_H_

#include "src/base/bits.h"
#include "src/heap/mark-compact.h"
#include "src/heap/objects-visiting-inl.h"
#include "src/heap/remembered-set.h"
#include "src/objects/js-collection-inl.h"
#include "src/objects/js-weak-refs-inl.h"
#include "src/objects/slots.h"

namespace v8 {
namespace internal {

template <typename ConcreteState, AccessMode access_mode>
bool MarkingStateBase<ConcreteState, access_mode>::GreyToBlack(
    HeapObject* obj) {
  MemoryChunk* p = MemoryChunk::FromAddress(obj->address());
  MarkBit markbit = MarkBitFrom(p, obj->address());
  if (!Marking::GreyToBlack<access_mode>(markbit)) return false;
  static_cast<ConcreteState*>(this)->IncrementLiveBytes(p, obj->Size());
  return true;
}

template <typename ConcreteState, AccessMode access_mode>
bool MarkingStateBase<ConcreteState, access_mode>::WhiteToGrey(
    HeapObject* obj) {
  return Marking::WhiteToGrey<access_mode>(MarkBitFrom(obj));
}

template <typename ConcreteState, AccessMode access_mode>
bool MarkingStateBase<ConcreteState, access_mode>::WhiteToBlack(
    HeapObject* obj) {
  return WhiteToGrey(obj) && GreyToBlack(obj);
}

template <FixedArrayVisitationMode fixed_array_mode,
          TraceRetainingPathMode retaining_path_mode, typename MarkingState>
MarkingVisitor<fixed_array_mode, retaining_path_mode,
               MarkingState>::MarkingVisitor(MarkCompactCollector* collector,
                                             MarkingState* marking_state)
    : heap_(collector->heap()),
      collector_(collector),
      marking_state_(marking_state) {}

template <FixedArrayVisitationMode fixed_array_mode,
          TraceRetainingPathMode retaining_path_mode, typename MarkingState>
int MarkingVisitor<fixed_array_mode, retaining_path_mode,
                   MarkingState>::VisitBytecodeArray(Map* map,
                                                     BytecodeArray* array) {
  int size = BytecodeArray::BodyDescriptor::SizeOf(map, array);
  BytecodeArray::BodyDescriptor::IterateBody(map, array, size, this);
  array->MakeOlder();
  return size;
}

template <FixedArrayVisitationMode fixed_array_mode,
          TraceRetainingPathMode retaining_path_mode, typename MarkingState>
int MarkingVisitor<fixed_array_mode, retaining_path_mode,
                   MarkingState>::VisitFixedArray(Map* map,
                                                  FixedArray* object) {
  return (fixed_array_mode == FixedArrayVisitationMode::kRegular)
             ? Parent::VisitFixedArray(map, object)
             : VisitFixedArrayIncremental(map, object);
}

template <FixedArrayVisitationMode fixed_array_mode,
          TraceRetainingPathMode retaining_path_mode, typename MarkingState>
template <typename T>
V8_INLINE int
MarkingVisitor<fixed_array_mode, retaining_path_mode,
               MarkingState>::VisitEmbedderTracingSubclass(Map* map,
                                                           T* object) {
  if (heap_->local_embedder_heap_tracer()->InUse()) {
    heap_->TracePossibleWrapper(object);
  }
  int size = T::BodyDescriptor::SizeOf(map, object);
  T::BodyDescriptor::IterateBody(map, object, size, this);
  return size;
}

template <FixedArrayVisitationMode fixed_array_mode,
          TraceRetainingPathMode retaining_path_mode, typename MarkingState>
int MarkingVisitor<fixed_array_mode, retaining_path_mode,
                   MarkingState>::VisitJSApiObject(Map* map, JSObject* object) {
  return VisitEmbedderTracingSubclass(map, object);
}

template <FixedArrayVisitationMode fixed_array_mode,
          TraceRetainingPathMode retaining_path_mode, typename MarkingState>
int MarkingVisitor<fixed_array_mode, retaining_path_mode,
                   MarkingState>::VisitJSArrayBuffer(Map* map,
                                                     JSArrayBuffer* object) {
  return VisitEmbedderTracingSubclass(map, object);
}

template <FixedArrayVisitationMode fixed_array_mode,
          TraceRetainingPathMode retaining_path_mode, typename MarkingState>
int MarkingVisitor<fixed_array_mode, retaining_path_mode,
                   MarkingState>::VisitJSDataView(Map* map,
                                                  JSDataView* object) {
  return VisitEmbedderTracingSubclass(map, object);
}

template <FixedArrayVisitationMode fixed_array_mode,
          TraceRetainingPathMode retaining_path_mode, typename MarkingState>
int MarkingVisitor<fixed_array_mode, retaining_path_mode,
                   MarkingState>::VisitJSTypedArray(Map* map,
                                                    JSTypedArray* object) {
  return VisitEmbedderTracingSubclass(map, object);
}

template <FixedArrayVisitationMode fixed_array_mode,
          TraceRetainingPathMode retaining_path_mode, typename MarkingState>
int MarkingVisitor<fixed_array_mode, retaining_path_mode, MarkingState>::
    VisitEphemeronHashTable(Map* map, EphemeronHashTable* table) {
  collector_->AddEphemeronHashTable(table);

  for (int i = 0; i < table->Capacity(); i++) {
    ObjectSlot key_slot =
        table->RawFieldOfElementAt(EphemeronHashTable::EntryToIndex(i));
    HeapObject* key = HeapObject::cast(table->KeyAt(i));
    collector_->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 = *value_slot;

      if (value_obj->IsHeapObject()) {
        HeapObject* value = HeapObject::cast(value_obj);
        collector_->RecordSlot(table, value_slot, value);

        // Revisit ephemerons with both key and value unreachable at end
        // of concurrent marking cycle.
        if (marking_state()->IsWhite(value)) {
          collector_->AddEphemeron(key, value);
        }
      }
    }
  }

  return table->SizeFromMap(map);
}

template <FixedArrayVisitationMode fixed_array_mode,
          TraceRetainingPathMode retaining_path_mode, typename MarkingState>
int MarkingVisitor<fixed_array_mode, retaining_path_mode,
                   MarkingState>::VisitMap(Map* map, Map* object) {
  // When map collection is enabled we have to mark through map's transitions
  // and back pointers in a special way to make these links weak.
  int size = Map::BodyDescriptor::SizeOf(map, object);
  if (object->CanTransition()) {
    MarkMapContents(object);
  } else {
    Map::BodyDescriptor::IterateBody(map, object, size, this);
  }
  return size;
}

template <FixedArrayVisitationMode fixed_array_mode,
          TraceRetainingPathMode retaining_path_mode, typename MarkingState>
int MarkingVisitor<fixed_array_mode, retaining_path_mode,
                   MarkingState>::VisitTransitionArray(Map* map,
                                                       TransitionArray* array) {
  int size = TransitionArray::BodyDescriptor::SizeOf(map, array);
  TransitionArray::BodyDescriptor::IterateBody(map, array, size, this);
  collector_->AddTransitionArray(array);
  return size;
}

template <FixedArrayVisitationMode fixed_array_mode,
          TraceRetainingPathMode retaining_path_mode, typename MarkingState>
int MarkingVisitor<fixed_array_mode, retaining_path_mode,
                   MarkingState>::VisitJSWeakCell(Map* map,
                                                  JSWeakCell* weak_cell) {
  if (weak_cell->target()->IsHeapObject()) {
    HeapObject* target = HeapObject::cast(weak_cell->target());
    if (marking_state()->IsBlackOrGrey(target)) {
      // Record the slot inside the JSWeakCell, since the IterateBody below
      // won't visit it.
      ObjectSlot slot =
          HeapObject::RawField(weak_cell, JSWeakCell::kTargetOffset);
      collector_->RecordSlot(weak_cell, slot, target);
    } else {
      // JSWeakCell points to a potentially dead object. We have to process
      // them when we know the liveness of the whole transitive closure.
      collector_->AddWeakCell(weak_cell);
    }
  }
  int size = JSWeakCell::BodyDescriptor::SizeOf(map, weak_cell);
  JSWeakCell::BodyDescriptor::IterateBody(map, weak_cell, size, this);
  return size;
}

template <FixedArrayVisitationMode fixed_array_mode,
          TraceRetainingPathMode retaining_path_mode, typename MarkingState>
void MarkingVisitor<fixed_array_mode, retaining_path_mode,
                    MarkingState>::VisitPointer(HeapObject* host,
                                                ObjectSlot p) {
  if (!(*p)->IsHeapObject()) return;
  HeapObject* target_object = HeapObject::cast(*p);
  collector_->RecordSlot(host, p, target_object);
  MarkObject(host, target_object);
}

template <FixedArrayVisitationMode fixed_array_mode,
          TraceRetainingPathMode retaining_path_mode, typename MarkingState>
void MarkingVisitor<fixed_array_mode, retaining_path_mode,
                    MarkingState>::VisitPointer(HeapObject* host,
                                                MaybeObjectSlot p) {
  HeapObject* target_object;
  if ((*p)->GetHeapObjectIfStrong(&target_object)) {
    collector_->RecordSlot(host, HeapObjectSlot(p), target_object);
    MarkObject(host, target_object);
  } else if ((*p)->GetHeapObjectIfWeak(&target_object)) {
    if (marking_state()->IsBlackOrGrey(target_object)) {
      // Weak references with live values are directly processed here to reduce
      // the processing time of weak cells during the main GC pause.
      collector_->RecordSlot(host, HeapObjectSlot(p), target_object);
    } else {
      // If we do not know about liveness of values of weak cells, we have to
      // process them when we know the liveness of the whole transitive
      // closure.
      collector_->AddWeakReference(host, HeapObjectSlot(p));
    }
  }
}

template <FixedArrayVisitationMode fixed_array_mode,
          TraceRetainingPathMode retaining_path_mode, typename MarkingState>
void MarkingVisitor<fixed_array_mode, retaining_path_mode,
                    MarkingState>::VisitPointers(HeapObject* host,
                                                 ObjectSlot start,
                                                 ObjectSlot end) {
  for (ObjectSlot p = start; p < end; ++p) {
    VisitPointer(host, p);
  }
}

template <FixedArrayVisitationMode fixed_array_mode,
          TraceRetainingPathMode retaining_path_mode, typename MarkingState>
void MarkingVisitor<fixed_array_mode, retaining_path_mode,
                    MarkingState>::VisitPointers(HeapObject* host,
                                                 MaybeObjectSlot start,
                                                 MaybeObjectSlot end) {
  for (MaybeObjectSlot p = start; p < end; ++p) {
    VisitPointer(host, p);
  }
}

template <FixedArrayVisitationMode fixed_array_mode,
          TraceRetainingPathMode retaining_path_mode, typename MarkingState>
void MarkingVisitor<fixed_array_mode, retaining_path_mode,
                    MarkingState>::VisitEmbeddedPointer(Code* host,
                                                        RelocInfo* rinfo) {
  DCHECK(rinfo->rmode() == RelocInfo::EMBEDDED_OBJECT);
  HeapObject* object = HeapObject::cast(rinfo->target_object());
  collector_->RecordRelocSlot(host, rinfo, object);
  if (!host->IsWeakObject(object)) {
    MarkObject(host, object);
  } else if (!marking_state()->IsBlackOrGrey(object)) {
    collector_->AddWeakObjectInCode(object, host);
  }
}

template <FixedArrayVisitationMode fixed_array_mode,
          TraceRetainingPathMode retaining_path_mode, typename MarkingState>
void MarkingVisitor<fixed_array_mode, retaining_path_mode,
                    MarkingState>::VisitCodeTarget(Code* host,
                                                   RelocInfo* rinfo) {
  DCHECK(RelocInfo::IsCodeTargetMode(rinfo->rmode()));
  Code* target = Code::GetCodeFromTargetAddress(rinfo->target_address());
  collector_->RecordRelocSlot(host, rinfo, target);
  MarkObject(host, target);
}

template <FixedArrayVisitationMode fixed_array_mode,
          TraceRetainingPathMode retaining_path_mode, typename MarkingState>
bool MarkingVisitor<fixed_array_mode, retaining_path_mode,
                    MarkingState>::MarkObjectWithoutPush(HeapObject* host,
                                                         HeapObject* object) {
  if (marking_state()->WhiteToBlack(object)) {
    if (retaining_path_mode == TraceRetainingPathMode::kEnabled &&
        V8_UNLIKELY(FLAG_track_retaining_path)) {
      heap_->AddRetainer(host, object);
    }
    return true;
  }
  return false;
}

template <FixedArrayVisitationMode fixed_array_mode,
          TraceRetainingPathMode retaining_path_mode, typename MarkingState>
void MarkingVisitor<fixed_array_mode, retaining_path_mode,
                    MarkingState>::MarkObject(HeapObject* host,
                                              HeapObject* object) {
  if (marking_state()->WhiteToGrey(object)) {
    marking_worklist()->Push(object);
    if (retaining_path_mode == TraceRetainingPathMode::kEnabled &&
        V8_UNLIKELY(FLAG_track_retaining_path)) {
      heap_->AddRetainer(host, object);
    }
  }
}

template <FixedArrayVisitationMode fixed_array_mode,
          TraceRetainingPathMode retaining_path_mode, typename MarkingState>
int MarkingVisitor<fixed_array_mode, retaining_path_mode, MarkingState>::
    VisitFixedArrayIncremental(Map* map, FixedArray* object) {
  MemoryChunk* chunk = MemoryChunk::FromAddress(object->address());
  int object_size = FixedArray::BodyDescriptor::SizeOf(map, object);
  if (chunk->IsFlagSet(MemoryChunk::HAS_PROGRESS_BAR)) {
    DCHECK(!FLAG_use_marking_progress_bar ||
           chunk->owner()->identity() == LO_SPACE);
    // When using a progress bar for large fixed arrays, scan only a chunk of
    // the array and try to push it onto the marking deque again until it is
    // fully scanned. Fall back to scanning it through to the end in case this
    // fails because of a full deque.
    int start_offset =
        Max(FixedArray::BodyDescriptor::kStartOffset, chunk->progress_bar());
    if (start_offset < object_size) {
      // Ensure that the object is either grey or black before pushing it
      // into marking worklist.
      marking_state()->WhiteToGrey(object);
      if (FLAG_concurrent_marking || FLAG_parallel_marking) {
        marking_worklist()->PushBailout(object);
      } else {
        marking_worklist()->Push(object);
      }
      DCHECK(marking_state()->IsGrey(object) ||
             marking_state()->IsBlack(object));

      int end_offset =
          Min(object_size, start_offset + kProgressBarScanningChunk);
      int already_scanned_offset = start_offset;
      VisitPointers(object, HeapObject::RawField(object, start_offset),
                    HeapObject::RawField(object, end_offset));
      start_offset = end_offset;
      end_offset = Min(object_size, end_offset + kProgressBarScanningChunk);
      chunk->set_progress_bar(start_offset);
      if (start_offset < object_size) {
        heap_->incremental_marking()->NotifyIncompleteScanOfObject(
            object_size - (start_offset - already_scanned_offset));
      }
    }
  } else {
    FixedArray::BodyDescriptor::IterateBody(map, object, object_size, this);
  }
  return object_size;
}

template <FixedArrayVisitationMode fixed_array_mode,
          TraceRetainingPathMode retaining_path_mode, typename MarkingState>
void MarkingVisitor<fixed_array_mode, retaining_path_mode,
                    MarkingState>::MarkMapContents(Map* map) {
  // 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.  Prototype maps don't keep track of transitions, so
  // just mark the entire descriptor array.
  if (!map->is_prototype_map()) {
    DescriptorArray* descriptors = map->instance_descriptors();
    if (MarkObjectWithoutPush(map, descriptors) && descriptors->length() > 0) {
      VisitPointers(descriptors, descriptors->data_start(),
                    descriptors->GetDescriptorEndSlot(0));
    }
    int start = 0;
    int end = map->NumberOfOwnDescriptors();
    if (start < end) {
      VisitPointers(descriptors, descriptors->GetDescriptorStartSlot(start),
                    descriptors->GetDescriptorEndSlot(end));
    }
  }

  // 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(
      map->map(), map, Map::BodyDescriptor::SizeOf(map->map(), map), this);
}

void MarkCompactCollector::MarkObject(HeapObject* host, HeapObject* obj) {
  if (marking_state()->WhiteToGrey(obj)) {
    marking_worklist()->Push(obj);
    if (V8_UNLIKELY(FLAG_track_retaining_path)) {
      heap_->AddRetainer(host, obj);
    }
  }
}

void MarkCompactCollector::MarkRootObject(Root root, HeapObject* obj) {
  if (marking_state()->WhiteToGrey(obj)) {
    marking_worklist()->Push(obj);
    if (V8_UNLIKELY(FLAG_track_retaining_path)) {
      heap_->AddRetainingRoot(root, obj);
    }
  }
}

#ifdef ENABLE_MINOR_MC

void MinorMarkCompactCollector::MarkRootObject(HeapObject* obj) {
  if (Heap::InNewSpace(obj) && non_atomic_marking_state_.WhiteToGrey(obj)) {
    worklist_->Push(kMainThread, obj);
  }
}

#endif

void MarkCompactCollector::MarkExternallyReferencedObject(HeapObject* obj) {
  if (marking_state()->WhiteToGrey(obj)) {
    marking_worklist()->Push(obj);
    if (V8_UNLIKELY(FLAG_track_retaining_path)) {
      heap_->AddRetainingRoot(Root::kWrapperTracing, obj);
    }
  }
}

void MarkCompactCollector::RecordSlot(HeapObject* object, ObjectSlot slot,
                                      HeapObject* target) {
  RecordSlot(object, HeapObjectSlot(slot), target);
}

void MarkCompactCollector::RecordSlot(HeapObject* object, HeapObjectSlot slot,
                                      HeapObject* target) {
  Page* target_page = Page::FromAddress(reinterpret_cast<Address>(target));
  Page* source_page = Page::FromAddress(reinterpret_cast<Address>(object));
  if (target_page->IsEvacuationCandidate<AccessMode::ATOMIC>() &&
      !source_page->ShouldSkipEvacuationSlotRecording<AccessMode::ATOMIC>()) {
    RememberedSet<OLD_TO_OLD>::Insert(source_page, slot.address());
  }
}

template <LiveObjectIterationMode mode>
LiveObjectRange<mode>::iterator::iterator(MemoryChunk* chunk, Bitmap* bitmap,
                                          Address start)
    : chunk_(chunk),
      one_word_filler_map_(
          ReadOnlyRoots(chunk->heap()).one_pointer_filler_map()),
      two_word_filler_map_(
          ReadOnlyRoots(chunk->heap()).two_pointer_filler_map()),
      free_space_map_(ReadOnlyRoots(chunk->heap()).free_space_map()),
      it_(chunk, bitmap) {
  it_.Advance(Bitmap::IndexToCell(
      Bitmap::CellAlignIndex(chunk_->AddressToMarkbitIndex(start))));
  if (!it_.Done()) {
    cell_base_ = it_.CurrentCellBase();
    current_cell_ = *it_.CurrentCell();
    AdvanceToNextValidObject();
  } else {
    current_object_ = nullptr;
  }
}

template <LiveObjectIterationMode mode>
typename LiveObjectRange<mode>::iterator& LiveObjectRange<mode>::iterator::
operator++() {
  AdvanceToNextValidObject();
  return *this;
}

template <LiveObjectIterationMode mode>
typename LiveObjectRange<mode>::iterator LiveObjectRange<mode>::iterator::
operator++(int) {
  iterator retval = *this;
  ++(*this);
  return retval;
}

template <LiveObjectIterationMode mode>
void LiveObjectRange<mode>::iterator::AdvanceToNextValidObject() {
  while (!it_.Done()) {
    HeapObject* object = nullptr;
    int size = 0;
    while (current_cell_ != 0) {
      uint32_t trailing_zeros = base::bits::CountTrailingZeros(current_cell_);
      Address addr = cell_base_ + trailing_zeros * kPointerSize;

      // Clear the first bit of the found object..
      current_cell_ &= ~(1u << trailing_zeros);

      uint32_t second_bit_index = 0;
      if (trailing_zeros >= Bitmap::kBitIndexMask) {
        second_bit_index = 0x1;
        // The overlapping case; there has to exist a cell after the current
        // cell.
        // However, if there is a black area at the end of the page, and the
        // last word is a one word filler, we are not allowed to advance. In
        // that case we can return immediately.
        if (!it_.Advance()) {
          DCHECK(HeapObject::FromAddress(addr)->map() == one_word_filler_map_);
          current_object_ = nullptr;
          return;
        }
        cell_base_ = it_.CurrentCellBase();
        current_cell_ = *it_.CurrentCell();
      } else {
        second_bit_index = 1u << (trailing_zeros + 1);
      }

      Map* map = nullptr;
      if (current_cell_ & second_bit_index) {
        // We found a black object. If the black object is within a black area,
        // make sure that we skip all set bits in the black area until the
        // object ends.
        HeapObject* black_object = HeapObject::FromAddress(addr);
        map =
            base::AsAtomicPointer::Acquire_Load(reinterpret_cast<Map**>(addr));
        size = black_object->SizeFromMap(map);
        Address end = addr + size - kPointerSize;
        // One word filler objects do not borrow the second mark bit. We have
        // to jump over the advancing and clearing part.
        // Note that we know that we are at a one word filler when
        // object_start + object_size - kPointerSize == object_start.
        if (addr != end) {
          DCHECK_EQ(chunk_, MemoryChunk::FromAddress(end));
          uint32_t end_mark_bit_index = chunk_->AddressToMarkbitIndex(end);
          unsigned int end_cell_index =
              end_mark_bit_index >> Bitmap::kBitsPerCellLog2;
          MarkBit::CellType end_index_mask =
              1u << Bitmap::IndexInCell(end_mark_bit_index);
          if (it_.Advance(end_cell_index)) {
            cell_base_ = it_.CurrentCellBase();
            current_cell_ = *it_.CurrentCell();
          }

          // Clear all bits in current_cell, including the end index.
          current_cell_ &= ~(end_index_mask + end_index_mask - 1);
        }

        if (mode == kBlackObjects || mode == kAllLiveObjects) {
          object = black_object;
        }
      } else if ((mode == kGreyObjects || mode == kAllLiveObjects)) {
        map =
            base::AsAtomicPointer::Acquire_Load(reinterpret_cast<Map**>(addr));
        object = HeapObject::FromAddress(addr);
        size = object->SizeFromMap(map);
      }

      // We found a live object.
      if (object != nullptr) {
        // Do not use IsFiller() here. This may cause a data race for reading
        // out the instance type when a new map concurrently is written into
        // this object while iterating over the object.
        if (map == one_word_filler_map_ || map == two_word_filler_map_ ||
            map == free_space_map_) {
          // There are two reasons why we can get black or grey fillers:
          // 1) Black areas together with slack tracking may result in black one
          // word filler objects.
          // 2) Left trimming may leave black or grey fillers behind because we
          // do not clear the old location of the object start.
          // We filter these objects out in the iterator.
          object = nullptr;
        } else {
          break;
        }
      }
    }

    if (current_cell_ == 0) {
      if (it_.Advance()) {
        cell_base_ = it_.CurrentCellBase();
        current_cell_ = *it_.CurrentCell();
      }
    }
    if (object != nullptr) {
      current_object_ = object;
      current_size_ = size;
      return;
    }
  }
  current_object_ = nullptr;
}

template <LiveObjectIterationMode mode>
typename LiveObjectRange<mode>::iterator LiveObjectRange<mode>::begin() {
  return iterator(chunk_, bitmap_, start_);
}

template <LiveObjectIterationMode mode>
typename LiveObjectRange<mode>::iterator LiveObjectRange<mode>::end() {
  return iterator(chunk_, bitmap_, end_);
}

Isolate* MarkCompactCollectorBase::isolate() { return heap()->isolate(); }

}  // namespace internal
}  // namespace v8

#endif  // V8_HEAP_MARK_COMPACT_INL_H_