// Copyright 2021 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_SANDBOX_EXTERNAL_POINTER_TABLE_INL_H_
#define V8_SANDBOX_EXTERNAL_POINTER_TABLE_INL_H_

#include "src/base/atomicops.h"
#include "src/sandbox/external-pointer-table.h"
#include "src/sandbox/external-pointer.h"
#include "src/utils/allocation.h"

#ifdef V8_SANDBOX_IS_AVAILABLE

namespace v8 {
namespace internal {

void ExternalPointerTable::Init(Isolate* isolate) {
  DCHECK(!is_initialized());

  VirtualAddressSpace* root_space = GetPlatformVirtualAddressSpace();
  DCHECK(IsAligned(kExternalPointerTableReservationSize,
                   root_space->allocation_granularity()));
  buffer_ = root_space->AllocatePages(
      VirtualAddressSpace::kNoHint, kExternalPointerTableReservationSize,
      root_space->allocation_granularity(), PagePermissions::kNoAccess);
  if (!buffer_) {
    V8::FatalProcessOutOfMemory(
        isolate,
        "Failed to reserve memory for ExternalPointerTable backing buffer");
  }

  mutex_ = new base::Mutex;
  if (!mutex_) {
    V8::FatalProcessOutOfMemory(
        isolate, "Failed to allocate mutex for ExternalPointerTable");
  }

  // Allocate the initial block. Mutex must be held for that.
  base::MutexGuard guard(mutex_);
  Grow();

  // Set up the special null entry. This entry must contain nullptr so that
  // empty EmbedderDataSlots represent nullptr.
  STATIC_ASSERT(kNullExternalPointer == 0);
  store(kNullExternalPointer, kNullAddress);
}

void ExternalPointerTable::TearDown() {
  DCHECK(is_initialized());

  GetPlatformVirtualAddressSpace()->FreePages(
      buffer_, kExternalPointerTableReservationSize);
  delete mutex_;

  buffer_ = kNullAddress;
  capacity_ = 0;
  freelist_head_ = 0;
  mutex_ = nullptr;
}

Address ExternalPointerTable::Get(uint32_t index,
                                  ExternalPointerTag tag) const {
  DCHECK_LT(index, capacity_);

  Address entry = load_atomic(index);
  DCHECK(!is_free(entry));

  return entry & ~tag;
}

void ExternalPointerTable::Set(uint32_t index, Address value,
                               ExternalPointerTag tag) {
  DCHECK_LT(index, capacity_);
  DCHECK_NE(kNullExternalPointer, index);
  DCHECK_EQ(0, value & kExternalPointerTagMask);
  DCHECK(is_marked(tag));

  store_atomic(index, value | tag);
}

uint32_t ExternalPointerTable::Allocate() {
  DCHECK(is_initialized());

  base::Atomic32* freelist_head_ptr =
      reinterpret_cast<base::Atomic32*>(&freelist_head_);

  uint32_t index;
  bool success = false;
  while (!success) {
    // This is essentially DCLP (see
    // https://preshing.com/20130930/double-checked-locking-is-fixed-in-cpp11/)
    // and so requires an acquire load as well as a release store in Grow() to
    // prevent reordering of memory accesses, which could for example cause one
    // thread to read a freelist entry before it has been properly initialized.
    uint32_t freelist_head = base::Acquire_Load(freelist_head_ptr);
    if (!freelist_head) {
      // Freelist is empty. Need to take the lock, then attempt to grow the
      // table if no other thread has done it in the meantime.
      base::MutexGuard guard(mutex_);

      // Reload freelist head in case another thread already grew the table.
      freelist_head = base::Relaxed_Load(freelist_head_ptr);

      if (!freelist_head) {
        // Freelist is (still) empty so grow the table.
        freelist_head = Grow();
      }
    }

    DCHECK(freelist_head);
    DCHECK_LT(freelist_head, capacity_);
    index = freelist_head;

    // The next free element is stored in the lower 32 bits of the entry.
    uint32_t new_freelist_head = static_cast<uint32_t>(load_atomic(index));

    uint32_t old_val = base::Relaxed_CompareAndSwap(
        freelist_head_ptr, freelist_head, new_freelist_head);
    success = old_val == freelist_head;
  }

  return index;
}

void ExternalPointerTable::Mark(uint32_t index) {
  DCHECK_LT(index, capacity_);
  STATIC_ASSERT(sizeof(base::Atomic64) == sizeof(Address));

  base::Atomic64 old_val = load_atomic(index);
  DCHECK(!is_free(old_val));
  base::Atomic64 new_val = set_mark_bit(old_val);

  // We don't need to perform the CAS in a loop: if the new value is not equal
  // to the old value, then the mutator must've just written a new value into
  // the entry. This in turn must've set the marking bit already (see
  // ExternalPointerTable::Set), so we don't need to do it again.
  base::Atomic64* ptr = reinterpret_cast<base::Atomic64*>(entry_address(index));
  base::Atomic64 val = base::Relaxed_CompareAndSwap(ptr, old_val, new_val);
  DCHECK((val == old_val) || is_marked(val));
  USE(val);
}

}  // namespace internal
}  // namespace v8

#endif  // V8_SANDBOX_IS_AVAILABLE

#endif  // V8_SANDBOX_EXTERNAL_POINTER_TABLE_INL_H_