lib/VM/DictPropertyMap.cpp

/*
 * Copyright (c) Meta Platforms, Inc. and affiliates.
 *
 * This source code is licensed under the MIT license found in the
 * LICENSE file in the root directory of this source tree.
 */

#define DEBUG_TYPE "vm"
#include "hermes/VM/DictPropertyMap.h"
#include "hermes/Support/Statistic.h"
#include "hermes/VM/SymbolID-inline.h"

HERMES_SLOW_STATISTIC(NumDictLookups, "Number of dictionary lookups");
HERMES_SLOW_STATISTIC(NumExtraHashProbes, "Number of extra hash probes");

namespace hermes {
namespace vm {

struct DictPropertyMap::detail {
  /// The upper bound of the search when trying to find the maximum capacity
  /// of this object, given GC::maxAllocationSize().
  /// It was chosen to be a value that is certain to not fit into an allocation;
  /// at the same time we want to make it smaller, so/ we have arbitrarily
  /// chosen to divide the max allocation size by two, which is still guaranteed
  /// not to fit.
  static constexpr uint32_t kSearchUpperBound = GC::maxAllocationSize() / 2;

  static_assert(
      !DictPropertyMap::constWouldFitAllocation(kSearchUpperBound),
      "kSearchUpperBound should not fit into an allocation");

  /// The maximum capacity of DictPropertyMap, given GC::maxAllocationSize().
  static constexpr uint32_t kMaxCapacity =
      DictPropertyMap::constFindMaxCapacity(0, kSearchUpperBound);

  // Double-check that kMaxCapacity is reasonable.
  static_assert(
      DictPropertyMap::constApproxAllocSize64(kMaxCapacity) <=
          GC::maxAllocationSize(),
      "invalid kMaxCapacity");

  // Ensure that it is safe to double capacities without checking for overflow
  // until we exceed kMaxCapacity.
  static_assert(
      kMaxCapacity < (1u << 31),
      "kMaxCapacity is unrealistically large");

  static_assert(
      DictPropertyMap::HashPair::canStore(kMaxCapacity),
      "too few bits to store max possible descriptor index");
};

const VTable DictPropertyMap::vt{CellKind::DictPropertyMapKind, 0};

void DictPropertyMapBuildMeta(const GCCell *cell, Metadata::Builder &mb) {
  const auto *self = static_cast<const DictPropertyMap *>(cell);
  mb.setVTable(&DictPropertyMap::vt);
  mb.addArray(
      &self->getDescriptorPairs()->first,
      &self->numDescriptors_,
      sizeof(DictPropertyMap::DescriptorPair));
}

DictPropertyMap::size_type DictPropertyMap::getMaxCapacity() {
  return detail::kMaxCapacity;
}

CallResult<PseudoHandle<DictPropertyMap>> DictPropertyMap::create(
    Runtime &runtime,
    size_type capacity) {
  if (LLVM_UNLIKELY(capacity > detail::kMaxCapacity)) {
    return runtime.raiseRangeError(
        TwineChar16("Property storage exceeds ") + detail::kMaxCapacity +
        " properties");
  }
  size_type hashCapacity = calcHashCapacity(capacity);
  auto *cell = runtime.makeAVariable<DictPropertyMap>(
      allocationSize(capacity, hashCapacity), capacity, hashCapacity);
  return createPseudoHandle(cell);
}

std::pair<bool, DictPropertyMap::HashPair *> DictPropertyMap::lookupEntryFor(
    DictPropertyMap *self,
    SymbolID symbolID) {
  ++NumDictLookups;

  size_type const mask = self->hashCapacity_ - 1;
  size_type index = hash(symbolID) & mask;

  // Probing step.
  size_type step = 1;
  // Save the address of the start of the table to avoid recalculating it.
  HashPair *const tableStart = self->getHashPairs();
  // The first deleted entry we found.
  HashPair *deleted = nullptr;

  assert(symbolID.isValid() && "looking for an invalid SymbolID");

  for (;;) {
    HashPair *curEntry = tableStart + index;

    if (curEntry->isValid()) {
      if (self->isMatch(curEntry, symbolID))
        return {true, curEntry};
    } else if (curEntry->isEmpty()) {
      // If we encountered an empty pair, the search is over - we failed.
      // Return either this entry or a deleted one, if we encountered one.

      return {false, deleted ? deleted : curEntry};
    } else {
      assert(curEntry->isDeleted() && "unexpected HashPair state");
      // The first time we encounter a deleted entry, record it so we can
      // potentially reuse it for insertion.
      if (!deleted)
        deleted = curEntry;
    }

    ++NumExtraHashProbes;
    index = (index + step) & mask;
    ++step;
  }
}

ExecutionStatus DictPropertyMap::grow(
    MutableHandle<DictPropertyMap> &selfHandleRef,
    Runtime &runtime,
    size_type newCapacity) {
  auto res = create(runtime, newCapacity);
  if (LLVM_UNLIKELY(res == ExecutionStatus::EXCEPTION)) {
    return ExecutionStatus::EXCEPTION;
  }
  auto *newSelf = res->get();
  auto *self = *selfHandleRef;

  selfHandleRef = newSelf;

  auto *dst = newSelf->getDescriptorPairs();
  size_type count = 0;

  for (auto *src = self->getDescriptorPairs(),
            *e = src + self->numDescriptors_.load(std::memory_order_relaxed);
       src != e;
       ++src) {
    if (src->first.isInvalid())
      continue;

    const SymbolID key = src->first;

    // The new property map doesn't have any valid symbols in it yet, use a
    // constructor instead of assignment to avoid an invalid write barrier.
    new (&dst->first) GCSymbolID(key);
    dst->second = src->second;

    auto result = lookupEntryFor(newSelf, key);
    assert(!result.first && "found duplicate entry while growing");
    result.second->setDescIndex(count, key);

    ++dst;
    ++count;
  }

  assert(
      count == self->numProperties_ && "numProperties mismatch when growing");

  newSelf->numProperties_ = count;

  // Transfer the deleted list to the new instance.
  auto deletedIndex = self->deletedListHead_;
  if (deletedIndex != END_OF_LIST) {
    newSelf->deletedListHead_ = count;
    newSelf->deletedListSize_ = self->deletedListSize_;

    do {
      const auto *src = self->getDescriptorPairs() + deletedIndex;
      assert(
          src->first == SymbolID::deleted() &&
          "pair in the deleted list is not marked as deleted");

      // The new property map doesn't have any valid symbols in it yet, use a
      // constructor instead of assignment to avoid an invalid write barrier.
      new (&dst->first) GCSymbolID(SymbolID::deleted());
      dst->second.slot = src->second.slot;

      deletedIndex = getNextDeletedIndex(src);
      setNextDeletedIndex(
          dst, deletedIndex != END_OF_LIST ? count + 1 : END_OF_LIST);

      ++dst;
      ++count;
    } while (deletedIndex != END_OF_LIST);
  }

  newSelf->numDescriptors_.store(count, std::memory_order_release);
  assert(count <= newSelf->descriptorCapacity_);
  return ExecutionStatus::RETURNED;
}

CallResult<std::pair<NamedPropertyDescriptor *, bool>>
DictPropertyMap::findOrAdd(
    MutableHandle<DictPropertyMap> &selfHandleRef,
    Runtime &runtime,
    SymbolID id) {
  auto *self = *selfHandleRef;
  auto numDescriptors = self->numDescriptors_.load(std::memory_order_relaxed);
  auto found = lookupEntryFor(self, id);
  if (found.first) {
    return std::make_pair(
        &self->getDescriptorPairs()[found.second->getDescIndex()].second,
        false);
  }

  // We want to grow the hash table if the number of occupied hash entries
  // exceeds 75% of capacity or if the descriptor array is full. Since the
  // capacity of the table is 4/3 of the capacity of the descriptor array, it is
  // sufficient to only check for the latter.

  if (numDescriptors == self->descriptorCapacity_) {
    size_type newCapacity;
    if (self->numProperties_ == self->descriptorCapacity_) {
      // Double the new capacity, up to kMaxCapacity. However make sure that
      // we try to allocate at least one extra property. If we are already
      // exactly at kMaxCapacity, there is nothing we can do, so grow() will
      // simply fail.
      newCapacity = self->numProperties_ * 2;
      if (newCapacity > detail::kMaxCapacity)
        newCapacity =
            std::max(toRValue(detail::kMaxCapacity), self->numProperties_ + 1);
    } else {
      // Calculate the new capacity to be exactly as much as we need to
      // accommodate the deleted list plus one extra property. It it happens
      // to exceed kMaxCapacity, there is nothing we can do, so grow() will
      // raise an exception.
      newCapacity = self->numProperties_ + 1 + self->deletedListSize_;
    }

    if (LLVM_UNLIKELY(
            grow(selfHandleRef, runtime, newCapacity) ==
            ExecutionStatus::EXCEPTION)) {
      return ExecutionStatus::EXCEPTION;
    }

    self = *selfHandleRef;
    numDescriptors = self->numDescriptors_.load(std::memory_order_relaxed);

    found = lookupEntryFor(self, id);
  }

  ++self->numProperties_;
  if (found.second->isDeleted())
    self->decDeletedHashCount();

  found.second->setDescIndex(numDescriptors, id);

  auto *descPair = self->getDescriptorPairs() + numDescriptors;

  descPair->first.set(id, &runtime.getHeap());
  self->numDescriptors_.fetch_add(1, std::memory_order_acq_rel);

  return std::make_pair(&descPair->second, true);
}

void DictPropertyMap::erase(
    DictPropertyMap *self,
    Runtime &runtime,
    PropertyPos pos) {
  auto *hashPair = self->getHashPairs() + pos.hashPairIndex;
  auto descIndex = hashPair->getDescIndex();
  assert(
      descIndex < self->numDescriptors_.load(std::memory_order_relaxed) &&
      "descriptor index out of range");

  auto *descPair = self->getDescriptorPairs() + descIndex;
  assert(
      descPair->first != SymbolID::empty() &&
      "accessing deleted descriptor pair");

  hashPair->setDeleted();
  descPair->first.set(SymbolID::deleted(), &runtime.getHeap());
  // Add the descriptor to the deleted list.
  setNextDeletedIndex(descPair, self->deletedListHead_);
  self->deletedListHead_ = descIndex;
  ++self->deletedListSize_;

  assert(self->numProperties_ != 0 && "num properties out of sync");
  --self->numProperties_;
  self->incDeletedHashCount();
}

SlotIndex DictPropertyMap::allocatePropertySlot(
    DictPropertyMap *self,
    Runtime &runtime) {
  // If there are no deleted properties, the number of properties corresponds
  // exactly to the number of slots.
  if (self->deletedListHead_ == END_OF_LIST)
    return self->numProperties_;

  auto *deletedPair = self->getDescriptorPairs() + self->deletedListHead_;
  assert(
      deletedPair->first == SymbolID::deleted() &&
      "Head of deleted list is not deleted");

  // Remove the first element from the deleted list.
  self->deletedListHead_ = getNextDeletedIndex(deletedPair);
  --self->deletedListSize_;

  // Mark the pair as "invalid" instead of "deleted".
  // No need for symbol write barrier because the previous value was deleted.
  new (&deletedPair->first) GCSymbolID(SymbolID::empty());

  return deletedPair->second.slot;
}

void DictPropertyMap::dump() {
  auto &OS = llvh::errs();

  OS << "DictPropertyMap:" << getDebugAllocationId() << "\n";
  OS << "  HashPairs[" << hashCapacity_ << "]:\n";
  for (unsigned i = 0; i < hashCapacity_; ++i) {
    auto *pair = getHashPairs() + i;
    if (pair->isValid()) {
      OS << "    " << pair->getDescIndex() << "\n";
    } else if (pair->isEmpty()) {
      OS << "    (empty)\n";
    } else {
      assert(pair->isDeleted());
      OS << "    (deleted)\n";
    }
  }
  OS << "  Descriptors[" << descriptorCapacity_ << "]:\n";
  for (unsigned i = 0; i < descriptorCapacity_; ++i) {
    auto *pair = getDescriptorPairs() + i;
    OS << "    (" << pair->first << ", "
       << "(slot=" << pair->second.slot << "))\n";
  }
}

} // namespace vm
} // namespace hermes

#undef DEBUG_TYPE