// 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_HEAP_INL_H_
#define V8_HEAP_HEAP_INL_H_

#include <cmath>

// Clients of this interface shouldn't depend on lots of heap internals.
// Do not include anything from src/heap other than src/heap/heap.h and its
// write barrier here!
#include "src/heap/heap-write-barrier.h"
#include "src/heap/heap.h"

#include "src/base/atomic-utils.h"
#include "src/base/platform/platform.h"
#include "src/feedback-vector.h"

// TODO(mstarzinger): There is one more include to remove in order to no longer
// leak heap internals to users of this interface!
#include "src/heap/spaces-inl.h"
#include "src/isolate-data.h"
#include "src/isolate.h"
#include "src/msan.h"
#include "src/objects-inl.h"
#include "src/objects/allocation-site-inl.h"
#include "src/objects/api-callbacks-inl.h"
#include "src/objects/cell-inl.h"
#include "src/objects/descriptor-array.h"
#include "src/objects/feedback-cell-inl.h"
#include "src/objects/literal-objects-inl.h"
#include "src/objects/oddball.h"
#include "src/objects/property-cell.h"
#include "src/objects/scope-info.h"
#include "src/objects/script-inl.h"
#include "src/objects/slots-inl.h"
#include "src/objects/struct-inl.h"
#include "src/profiler/heap-profiler.h"
#include "src/string-hasher.h"
#include "src/zone/zone-list-inl.h"

namespace v8 {
namespace internal {

AllocationSpace AllocationResult::RetrySpace() {
  DCHECK(IsRetry());
  return static_cast<AllocationSpace>(Smi::ToInt(object_));
}

HeapObject AllocationResult::ToObjectChecked() {
  CHECK(!IsRetry());
  return HeapObject::cast(object_);
}

Isolate* Heap::isolate() {
  return reinterpret_cast<Isolate*>(
      reinterpret_cast<intptr_t>(this) -
      reinterpret_cast<size_t>(reinterpret_cast<Isolate*>(16)->heap()) + 16);
}

int64_t Heap::external_memory() {
  return isolate()->isolate_data()->external_memory_;
}

void Heap::update_external_memory(int64_t delta) {
  isolate()->isolate_data()->external_memory_ += delta;
}

void Heap::update_external_memory_concurrently_freed(intptr_t freed) {
  external_memory_concurrently_freed_ += freed;
}

void Heap::account_external_memory_concurrently_freed() {
  isolate()->isolate_data()->external_memory_ -=
      external_memory_concurrently_freed_;
  external_memory_concurrently_freed_ = 0;
}

RootsTable& Heap::roots_table() { return isolate()->roots_table(); }

#define ROOT_ACCESSOR(Type, name, CamelName)                           \
  Type Heap::name() {                                                  \
    return Type::cast(Object(roots_table()[RootIndex::k##CamelName])); \
  }
MUTABLE_ROOT_LIST(ROOT_ACCESSOR)
#undef ROOT_ACCESSOR

#define ROOT_ACCESSOR(type, name, CamelName)                                   \
  void Heap::set_##name(type value) {                                          \
    /* The deserializer makes use of the fact that these common roots are */   \
    /* never in new space and never on a page that is being compacted.    */   \
    DCHECK_IMPLIES(deserialization_complete(),                                 \
                   !RootsTable::IsImmortalImmovable(RootIndex::k##CamelName)); \
    DCHECK_IMPLIES(RootsTable::IsImmortalImmovable(RootIndex::k##CamelName),   \
                   IsImmovable(HeapObject::cast(value)));                      \
    roots_table()[RootIndex::k##CamelName] = value->ptr();                     \
  }
ROOT_LIST(ROOT_ACCESSOR)
#undef ROOT_ACCESSOR

void Heap::SetRootMaterializedObjects(FixedArray objects) {
  roots_table()[RootIndex::kMaterializedObjects] = objects->ptr();
}

void Heap::SetRootScriptList(Object value) {
  roots_table()[RootIndex::kScriptList] = value->ptr();
}

void Heap::SetRootStringTable(StringTable value) {
  roots_table()[RootIndex::kStringTable] = value->ptr();
}

void Heap::SetRootNoScriptSharedFunctionInfos(Object value) {
  roots_table()[RootIndex::kNoScriptSharedFunctionInfos] = value->ptr();
}

void Heap::SetMessageListeners(TemplateList value) {
  roots_table()[RootIndex::kMessageListeners] = value->ptr();
}

void Heap::SetPendingOptimizeForTestBytecode(Object hash_table) {
  DCHECK(hash_table->IsObjectHashTable() || hash_table->IsUndefined(isolate()));
  roots_table()[RootIndex::kPendingOptimizeForTestBytecode] = hash_table->ptr();
}

PagedSpace* Heap::paged_space(int idx) {
  DCHECK_NE(idx, LO_SPACE);
  DCHECK_NE(idx, NEW_SPACE);
  DCHECK_NE(idx, CODE_LO_SPACE);
  DCHECK_NE(idx, NEW_LO_SPACE);
  return static_cast<PagedSpace*>(space_[idx]);
}

Space* Heap::space(int idx) { return space_[idx]; }

Address* Heap::NewSpaceAllocationTopAddress() {
  return new_space_->allocation_top_address();
}

Address* Heap::NewSpaceAllocationLimitAddress() {
  return new_space_->allocation_limit_address();
}

Address* Heap::OldSpaceAllocationTopAddress() {
  return old_space_->allocation_top_address();
}

Address* Heap::OldSpaceAllocationLimitAddress() {
  return old_space_->allocation_limit_address();
}

void Heap::UpdateNewSpaceAllocationCounter() {
  new_space_allocation_counter_ = NewSpaceAllocationCounter();
}

size_t Heap::NewSpaceAllocationCounter() {
  return new_space_allocation_counter_ + new_space()->AllocatedSinceLastGC();
}

AllocationResult Heap::AllocateRaw(int size_in_bytes, AllocationType type,
                                   AllocationAlignment alignment) {
  DCHECK(AllowHandleAllocation::IsAllowed());
  DCHECK(AllowHeapAllocation::IsAllowed());
  DCHECK(gc_state_ == NOT_IN_GC);
#ifdef V8_ENABLE_ALLOCATION_TIMEOUT
  if (FLAG_random_gc_interval > 0 || FLAG_gc_interval >= 0) {
    if (!always_allocate() && Heap::allocation_timeout_-- <= 0) {
      return AllocationResult::Retry();
    }
  }
#endif
#ifdef DEBUG
  IncrementObjectCounters();
#endif

  bool large_object = size_in_bytes > kMaxRegularHeapObjectSize;

  HeapObject object;
  AllocationResult allocation;

  if (AllocationType::kYoung == type) {
    if (large_object) {
      if (FLAG_young_generation_large_objects) {
        allocation = new_lo_space_->AllocateRaw(size_in_bytes);
      } else {
        // If young generation large objects are disalbed we have to tenure the
        // allocation and violate the given allocation type. This could be
        // dangerous. We may want to remove FLAG_young_generation_large_objects
        // and avoid patching.
        allocation = lo_space_->AllocateRaw(size_in_bytes);
      }
    } else {
      allocation = new_space_->AllocateRaw(size_in_bytes, alignment);
    }
  } else if (AllocationType::kOld == type) {
    if (large_object) {
      allocation = lo_space_->AllocateRaw(size_in_bytes);
    } else {
      allocation = old_space_->AllocateRaw(size_in_bytes, alignment);
    }
  } else if (AllocationType::kCode == type) {
    if (size_in_bytes <= code_space()->AreaSize() && !large_object) {
      allocation = code_space_->AllocateRawUnaligned(size_in_bytes);
    } else {
      allocation = code_lo_space_->AllocateRaw(size_in_bytes);
    }
  } else if (AllocationType::kMap == type) {
    allocation = map_space_->AllocateRawUnaligned(size_in_bytes);
  } else if (AllocationType::kReadOnly == type) {
#ifdef V8_USE_SNAPSHOT
    DCHECK(isolate_->serializer_enabled());
#endif
    DCHECK(!large_object);
    DCHECK(CanAllocateInReadOnlySpace());
    allocation = read_only_space_->AllocateRaw(size_in_bytes, alignment);
  } else {
    UNREACHABLE();
  }

  if (allocation.To(&object)) {
    if (AllocationType::kCode == type) {
      // Unprotect the memory chunk of the object if it was not unprotected
      // already.
      UnprotectAndRegisterMemoryChunk(object);
      ZapCodeObject(object->address(), size_in_bytes);
      if (!large_object) {
        MemoryChunk::FromHeapObject(object)
            ->GetCodeObjectRegistry()
            ->RegisterNewlyAllocatedCodeObject(object->address());
      }
    }
    OnAllocationEvent(object, size_in_bytes);
  }

  return allocation;
}

void Heap::OnAllocationEvent(HeapObject object, int size_in_bytes) {
  for (auto& tracker : allocation_trackers_) {
    tracker->AllocationEvent(object->address(), size_in_bytes);
  }

  if (FLAG_verify_predictable) {
    ++allocations_count_;
    // Advance synthetic time by making a time request.
    MonotonicallyIncreasingTimeInMs();

    UpdateAllocationsHash(object);
    UpdateAllocationsHash(size_in_bytes);

    if (allocations_count_ % FLAG_dump_allocations_digest_at_alloc == 0) {
      PrintAllocationsHash();
    }
  } else if (FLAG_fuzzer_gc_analysis) {
    ++allocations_count_;
  } else if (FLAG_trace_allocation_stack_interval > 0) {
    ++allocations_count_;
    if (allocations_count_ % FLAG_trace_allocation_stack_interval == 0) {
      isolate()->PrintStack(stdout, Isolate::kPrintStackConcise);
    }
  }
}

bool Heap::CanAllocateInReadOnlySpace() {
  return !deserialization_complete_ &&
         (isolate()->serializer_enabled() ||
          !isolate()->initialized_from_snapshot());
}

void Heap::UpdateAllocationsHash(HeapObject object) {
  Address object_address = object->address();
  MemoryChunk* memory_chunk = MemoryChunk::FromAddress(object_address);
  AllocationSpace allocation_space = memory_chunk->owner()->identity();

  STATIC_ASSERT(kSpaceTagSize + kPageSizeBits <= 32);
  uint32_t value =
      static_cast<uint32_t>(object_address - memory_chunk->address()) |
      (static_cast<uint32_t>(allocation_space) << kPageSizeBits);

  UpdateAllocationsHash(value);
}

void Heap::UpdateAllocationsHash(uint32_t value) {
  uint16_t c1 = static_cast<uint16_t>(value);
  uint16_t c2 = static_cast<uint16_t>(value >> 16);
  raw_allocations_hash_ =
      StringHasher::AddCharacterCore(raw_allocations_hash_, c1);
  raw_allocations_hash_ =
      StringHasher::AddCharacterCore(raw_allocations_hash_, c2);
}

void Heap::RegisterExternalString(String string) {
  DCHECK(string->IsExternalString());
  DCHECK(!string->IsThinString());
  external_string_table_.AddString(string);
}

void Heap::FinalizeExternalString(String string) {
  DCHECK(string->IsExternalString());
  Page* page = Page::FromHeapObject(string);
  ExternalString ext_string = ExternalString::cast(string);

  page->DecrementExternalBackingStoreBytes(
      ExternalBackingStoreType::kExternalString,
      ext_string->ExternalPayloadSize());

  ext_string->DisposeResource();
}

Address Heap::NewSpaceTop() { return new_space_->top(); }

bool Heap::InYoungGeneration(Object object) {
  DCHECK(!HasWeakHeapObjectTag(object));
  return object->IsHeapObject() && InYoungGeneration(HeapObject::cast(object));
}

// static
bool Heap::InYoungGeneration(MaybeObject object) {
  HeapObject heap_object;
  return object->GetHeapObject(&heap_object) && InYoungGeneration(heap_object);
}

// static
bool Heap::InYoungGeneration(HeapObject heap_object) {
  bool result = MemoryChunk::FromHeapObject(heap_object)->InYoungGeneration();
#ifdef DEBUG
  // If in the young generation, then check we're either not in the middle of
  // GC or the object is in to-space.
  if (result) {
    // If the object is in the young generation, then it's not in RO_SPACE so
    // this is safe.
    Heap* heap = Heap::FromWritableHeapObject(heap_object);
    DCHECK_IMPLIES(heap->gc_state_ == NOT_IN_GC, InToPage(heap_object));
  }
#endif
  return result;
}

// static
bool Heap::InFromPage(Object object) {
  DCHECK(!HasWeakHeapObjectTag(object));
  return object->IsHeapObject() && InFromPage(HeapObject::cast(object));
}

// static
bool Heap::InFromPage(MaybeObject object) {
  HeapObject heap_object;
  return object->GetHeapObject(&heap_object) && InFromPage(heap_object);
}

// static
bool Heap::InFromPage(HeapObject heap_object) {
  return MemoryChunk::FromHeapObject(heap_object)->IsFromPage();
}

// static
bool Heap::InToPage(Object object) {
  DCHECK(!HasWeakHeapObjectTag(object));
  return object->IsHeapObject() && InToPage(HeapObject::cast(object));
}

// static
bool Heap::InToPage(MaybeObject object) {
  HeapObject heap_object;
  return object->GetHeapObject(&heap_object) && InToPage(heap_object);
}

// static
bool Heap::InToPage(HeapObject heap_object) {
  return MemoryChunk::FromHeapObject(heap_object)->IsToPage();
}

bool Heap::InOldSpace(Object object) { return old_space_->Contains(object); }

// static
Heap* Heap::FromWritableHeapObject(const HeapObject obj) {
  MemoryChunk* chunk = MemoryChunk::FromHeapObject(obj);
  // RO_SPACE can be shared between heaps, so we can't use RO_SPACE objects to
  // find a heap. The exception is when the ReadOnlySpace is writeable, during
  // bootstrapping, so explicitly allow this case.
  SLOW_DCHECK(chunk->owner()->identity() != RO_SPACE ||
              static_cast<ReadOnlySpace*>(chunk->owner())->writable());
  Heap* heap = chunk->heap();
  SLOW_DCHECK(heap != nullptr);
  return heap;
}

bool Heap::ShouldBePromoted(Address old_address) {
  Page* page = Page::FromAddress(old_address);
  Address age_mark = new_space_->age_mark();
  return page->IsFlagSet(MemoryChunk::NEW_SPACE_BELOW_AGE_MARK) &&
         (!page->ContainsLimit(age_mark) || old_address < age_mark);
}

void Heap::CopyBlock(Address dst, Address src, int byte_size) {
  DCHECK(IsAligned(byte_size, kTaggedSize));
  CopyTagged(dst, src, static_cast<size_t>(byte_size / kTaggedSize));
}

template <Heap::FindMementoMode mode>
AllocationMemento Heap::FindAllocationMemento(Map map, HeapObject object) {
  Address object_address = object->address();
  Address memento_address = object_address + object->SizeFromMap(map);
  Address last_memento_word_address = memento_address + kTaggedSize;
  // If the memento would be on another page, bail out immediately.
  if (!Page::OnSamePage(object_address, last_memento_word_address)) {
    return AllocationMemento();
  }
  HeapObject candidate = HeapObject::FromAddress(memento_address);
  MapWordSlot candidate_map_slot = candidate->map_slot();
  // This fast check may peek at an uninitialized word. However, the slow check
  // below (memento_address == top) ensures that this is safe. Mark the word as
  // initialized to silence MemorySanitizer warnings.
  MSAN_MEMORY_IS_INITIALIZED(candidate_map_slot.address(), kTaggedSize);
  if (!candidate_map_slot.contains_value(
          ReadOnlyRoots(this).allocation_memento_map().ptr())) {
    return AllocationMemento();
  }

  // Bail out if the memento is below the age mark, which can happen when
  // mementos survived because a page got moved within new space.
  Page* object_page = Page::FromAddress(object_address);
  if (object_page->IsFlagSet(Page::NEW_SPACE_BELOW_AGE_MARK)) {
    Address age_mark =
        reinterpret_cast<SemiSpace*>(object_page->owner())->age_mark();
    if (!object_page->Contains(age_mark)) {
      return AllocationMemento();
    }
    // Do an exact check in the case where the age mark is on the same page.
    if (object_address < age_mark) {
      return AllocationMemento();
    }
  }

  AllocationMemento memento_candidate = AllocationMemento::cast(candidate);

  // Depending on what the memento is used for, we might need to perform
  // additional checks.
  Address top;
  switch (mode) {
    case Heap::kForGC:
      return memento_candidate;
    case Heap::kForRuntime:
      if (memento_candidate.is_null()) return AllocationMemento();
      // Either the object is the last object in the new space, or there is
      // another object of at least word size (the header map word) following
      // it, so suffices to compare ptr and top here.
      top = NewSpaceTop();
      DCHECK(memento_address == top ||
             memento_address + HeapObject::kHeaderSize <= top ||
             !Page::OnSamePage(memento_address, top - 1));
      if ((memento_address != top) && memento_candidate->IsValid()) {
        return memento_candidate;
      }
      return AllocationMemento();
    default:
      UNREACHABLE();
  }
  UNREACHABLE();
}

void Heap::UpdateAllocationSite(Map map, HeapObject object,
                                PretenuringFeedbackMap* pretenuring_feedback) {
  DCHECK_NE(pretenuring_feedback, &global_pretenuring_feedback_);
#ifdef DEBUG
  MemoryChunk* chunk = MemoryChunk::FromHeapObject(object);
  DCHECK_IMPLIES(chunk->IsToPage(),
                 chunk->IsFlagSet(MemoryChunk::PAGE_NEW_NEW_PROMOTION));
  DCHECK_IMPLIES(!chunk->InYoungGeneration(),
                 chunk->IsFlagSet(MemoryChunk::PAGE_NEW_OLD_PROMOTION));
#endif
  if (!FLAG_allocation_site_pretenuring ||
      !AllocationSite::CanTrack(map->instance_type())) {
    return;
  }
  AllocationMemento memento_candidate =
      FindAllocationMemento<kForGC>(map, object);
  if (memento_candidate.is_null()) return;

  // Entering cached feedback is used in the parallel case. We are not allowed
  // to dereference the allocation site and rather have to postpone all checks
  // till actually merging the data.
  Address key = memento_candidate->GetAllocationSiteUnchecked();
  (*pretenuring_feedback)[AllocationSite::unchecked_cast(Object(key))]++;
}

void Heap::ExternalStringTable::AddString(String string) {
  DCHECK(string->IsExternalString());
  DCHECK(!Contains(string));

  if (InYoungGeneration(string)) {
    young_strings_.push_back(string);
  } else {
    old_strings_.push_back(string);
  }
}

Oddball Heap::ToBoolean(bool condition) {
  ReadOnlyRoots roots(this);
  return condition ? roots.true_value() : roots.false_value();
}

int Heap::NextScriptId() {
  int last_id = last_script_id()->value();
  if (last_id == Smi::kMaxValue) last_id = v8::UnboundScript::kNoScriptId;
  last_id++;
  set_last_script_id(Smi::FromInt(last_id));
  return last_id;
}

int Heap::NextDebuggingId() {
  int last_id = last_debugging_id()->value();
  if (last_id == DebugInfo::DebuggingIdBits::kMax) {
    last_id = DebugInfo::kNoDebuggingId;
  }
  last_id++;
  set_last_debugging_id(Smi::FromInt(last_id));
  return last_id;
}

int Heap::GetNextTemplateSerialNumber() {
  int next_serial_number = next_template_serial_number()->value() + 1;
  set_next_template_serial_number(Smi::FromInt(next_serial_number));
  return next_serial_number;
}

int Heap::MaxNumberToStringCacheSize() const {
  // Compute the size of the number string cache based on the max newspace size.
  // The number string cache has a minimum size based on twice the initial cache
  // size to ensure that it is bigger after being made 'full size'.
  size_t number_string_cache_size = max_semi_space_size_ / 512;
  number_string_cache_size =
      Max(static_cast<size_t>(kInitialNumberStringCacheSize * 2),
          Min<size_t>(0x4000u, number_string_cache_size));
  // There is a string and a number per entry so the length is twice the number
  // of entries.
  return static_cast<int>(number_string_cache_size * 2);
}

void Heap::IncrementExternalBackingStoreBytes(ExternalBackingStoreType type,
                                              size_t amount) {
  base::CheckedIncrement(&backing_store_bytes_, amount);
  // TODO(mlippautz): Implement interrupt for global memory allocations that can
  // trigger garbage collections.
}

void Heap::DecrementExternalBackingStoreBytes(ExternalBackingStoreType type,
                                              size_t amount) {
  base::CheckedDecrement(&backing_store_bytes_, amount);
}

AlwaysAllocateScope::AlwaysAllocateScope(Heap* heap) : heap_(heap) {
  heap_->always_allocate_scope_count_++;
}

AlwaysAllocateScope::AlwaysAllocateScope(Isolate* isolate)
    : AlwaysAllocateScope(isolate->heap()) {}

AlwaysAllocateScope::~AlwaysAllocateScope() {
  heap_->always_allocate_scope_count_--;
}

CodeSpaceMemoryModificationScope::CodeSpaceMemoryModificationScope(Heap* heap)
    : heap_(heap) {
  if (heap_->write_protect_code_memory()) {
    heap_->increment_code_space_memory_modification_scope_depth();
    heap_->code_space()->SetReadAndWritable();
    LargePage* page = heap_->code_lo_space()->first_page();
    while (page != nullptr) {
      DCHECK(page->IsFlagSet(MemoryChunk::IS_EXECUTABLE));
      CHECK(heap_->memory_allocator()->IsMemoryChunkExecutable(page));
      page->SetReadAndWritable();
      page = page->next_page();
    }
  }
}

CodeSpaceMemoryModificationScope::~CodeSpaceMemoryModificationScope() {
  if (heap_->write_protect_code_memory()) {
    heap_->decrement_code_space_memory_modification_scope_depth();
    heap_->code_space()->SetDefaultCodePermissions();
    LargePage* page = heap_->code_lo_space()->first_page();
    while (page != nullptr) {
      DCHECK(page->IsFlagSet(MemoryChunk::IS_EXECUTABLE));
      CHECK(heap_->memory_allocator()->IsMemoryChunkExecutable(page));
      page->SetDefaultCodePermissions();
      page = page->next_page();
    }
  }
}

CodePageCollectionMemoryModificationScope::
    CodePageCollectionMemoryModificationScope(Heap* heap)
    : heap_(heap) {
  if (heap_->write_protect_code_memory() &&
      !heap_->code_space_memory_modification_scope_depth()) {
    heap_->EnableUnprotectedMemoryChunksRegistry();
  }
}

CodePageCollectionMemoryModificationScope::
    ~CodePageCollectionMemoryModificationScope() {
  if (heap_->write_protect_code_memory() &&
      !heap_->code_space_memory_modification_scope_depth()) {
    heap_->ProtectUnprotectedMemoryChunks();
    heap_->DisableUnprotectedMemoryChunksRegistry();
  }
}

CodePageMemoryModificationScope::CodePageMemoryModificationScope(
    MemoryChunk* chunk)
    : chunk_(chunk),
      scope_active_(chunk_->heap()->write_protect_code_memory() &&
                    chunk_->IsFlagSet(MemoryChunk::IS_EXECUTABLE)) {
  if (scope_active_) {
    DCHECK(chunk_->owner()->identity() == CODE_SPACE ||
           (chunk_->owner()->identity() == CODE_LO_SPACE));
    chunk_->SetReadAndWritable();
  }
}

CodePageMemoryModificationScope::~CodePageMemoryModificationScope() {
  if (scope_active_) {
    chunk_->SetDefaultCodePermissions();
  }
}

}  // namespace internal
}  // namespace v8

#endif  // V8_HEAP_HEAP_INL_H_