canonical-types.cc

Go to the documentation of this file.

// Copyright 2022 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/wasm/canonical-types.h"
 
#include "src/base/hashing.h"
#include "src/execution/isolate.h"
#include "src/handles/handles-inl.h"
#include "src/heap/heap-inl.h"
#include "src/init/v8.h"
#include "src/roots/roots-inl.h"
#include "src/utils/utils.h"
#include "src/wasm/names-provider.h"
#include "src/wasm/std-object-sizes.h"
#include "src/wasm/wasm-engine.h"
 
namespace v8::internal::wasm {
 
TypeCanonicalizer* GetTypeCanonicalizer() {
  return GetWasmEngine()->type_canonicalizer();
}
 
TypeCanonicalizer::TypeCanonicalizer() { AddPredefinedArrayTypes(); }
 
void TypeCanonicalizer::CheckMaxCanonicalIndex() const {
  if (V8_UNLIKELY(canonical_supertypes_.size() > kMaxCanonicalTypes)) {
    V8::FatalProcessOutOfMemory(nullptr, "too many canonicalized types");
  }
}
 
void TypeCanonicalizer::AddRecursiveGroup(WasmModule* module, uint32_t size) {
  if (size == 0) return;
  // If the caller knows statically that {size == 1}, it should have called
  // {AddRecursiveSingletonGroup} directly. For cases where this is not
  // statically determined we add this dispatch here.
  if (size == 1) return AddRecursiveSingletonGroup(module);
 
  uint32_t start_index = static_cast<uint32_t>(module->types.size() - size);
 
  // Multiple threads could try to register recursive groups concurrently.
  // TODO(manoskouk): Investigate if we can fine-grain the synchronization.
  base::MutexGuard mutex_guard(&mutex_);
  // Compute the first canonical index in the recgroup in the case that it does
  // not already exist.
  CanonicalTypeIndex first_new_canonical_index{
      static_cast<uint32_t>(canonical_supertypes_.size())};
 
  // Create a snapshot of the zone; this will be restored in case we find a
  // matching recursion group.
  ZoneSnapshot zone_snapshot = zone_.Snapshot();
 
  DCHECK_GE(module->types.size(), start_index + size);
  CanonicalGroup group{&zone_, size, first_new_canonical_index};
  for (uint32_t i = 0; i < size; i++) {
    group.types[i] = CanonicalizeTypeDef(
        module, ModuleTypeIndex{start_index + i}, ModuleTypeIndex{start_index},
        first_new_canonical_index);
  }
  if (CanonicalTypeIndex canonical_index = FindCanonicalGroup(group);
      canonical_index.valid()) {
    // Delete zone memory from {CanonicalizeTypeDef} and {CanonicalGroup}.
    zone_snapshot.Restore(&zone_);
 
    // Identical group found. Map new types to the old types's canonical
    // representatives.
    for (uint32_t i = 0; i < size; i++) {
      CanonicalTypeIndex existing_type_index =
          CanonicalTypeIndex{canonical_index.index + i};
      module->isorecursive_canonical_type_ids[start_index + i] =
          existing_type_index;
    }
    return;
  }
  canonical_supertypes_.resize(first_new_canonical_index.index + size);
  CheckMaxCanonicalIndex();
  canonical_types_.reserve(first_new_canonical_index.index + size, &zone_);
  for (uint32_t i = 0; i < size; i++) {
    CanonicalType& canonical_type = group.types[i];
    CanonicalTypeIndex canonical_id{first_new_canonical_index.index + i};
    // {CanonicalGroup} allocates types in the Zone.
    DCHECK(zone_.Contains(&canonical_type));
    canonical_types_.set(canonical_id, &canonical_type);
    canonical_supertypes_[canonical_id.index] = canonical_type.supertype;
    module->isorecursive_canonical_type_ids[start_index + i] = canonical_id;
  }
  // Check that this canonical ID is not used yet.
  DCHECK(std::none_of(
      canonical_singleton_groups_.begin(), canonical_singleton_groups_.end(),
      [=](auto& entry) { return entry.index == first_new_canonical_index; }));
  DCHECK(std::none_of(
      canonical_groups_.begin(), canonical_groups_.end(),
      [=](auto& entry) { return entry.first == first_new_canonical_index; }));
  canonical_groups_.emplace(group);
}
 
void TypeCanonicalizer::AddRecursiveSingletonGroup(WasmModule* module) {
  DCHECK(!module->types.empty());
  uint32_t type_index = static_cast<uint32_t>(module->types.size() - 1);
  base::MutexGuard guard(&mutex_);
  CanonicalTypeIndex new_canonical_index{
      static_cast<uint32_t>(canonical_supertypes_.size())};
  // Snapshot the zone before allocating the new type; the zone will be reset if
  // we find an identical type.
  ZoneSnapshot zone_snapshot = zone_.Snapshot();
  CanonicalType type =
      CanonicalizeTypeDef(module, ModuleTypeIndex{type_index},
                          ModuleTypeIndex{type_index}, new_canonical_index);
  CanonicalSingletonGroup group{type, new_canonical_index};
  if (CanonicalTypeIndex index = FindCanonicalGroup(group); index.valid()) {
    zone_snapshot.Restore(&zone_);
    module->isorecursive_canonical_type_ids[type_index] = index;
    return;
  }
  // Check that the new canonical ID is not used yet.
  DCHECK(std::none_of(
      canonical_singleton_groups_.begin(), canonical_singleton_groups_.end(),
      [=](auto& entry) { return entry.index == new_canonical_index; }));
  DCHECK(std::none_of(
      canonical_groups_.begin(), canonical_groups_.end(),
      [=](auto& entry) { return entry.first == new_canonical_index; }));
  // {group.type} is stack-allocated, whereas {canonical_singleton_groups_}
  // creates a long-lived zone-allocated copy of it.
  auto stored_group = canonical_singleton_groups_.emplace(group).first;
  canonical_supertypes_.push_back(type.supertype);
  CheckMaxCanonicalIndex();
  canonical_types_.reserve(new_canonical_index.index + 1, &zone_);
  canonical_types_.set(new_canonical_index, &stored_group->type);
  module->isorecursive_canonical_type_ids[type_index] = new_canonical_index;
}
 
CanonicalTypeIndex TypeCanonicalizer::AddRecursiveGroup(
    const FunctionSig* sig) {
// Types in the signature must be module-independent.
#if DEBUG
  for (ValueType type : sig->all()) DCHECK(!type.has_index());
#endif
  const bool kFinal = true;
  // Because of the checks above, we can treat the type_def as canonical.
  // TODO(366180605): It would be nice to not have to rely on a cast here.
  // Is there a way to avoid it? In the meantime, these asserts provide at
  // least partial assurances that the cast is safe:
  static_assert(sizeof(CanonicalValueType) == sizeof(ValueType));
  static_assert(
      CanonicalValueType::Primitive(NumericKind::kI32).raw_bit_field() ==
      ValueType::Primitive(kI32).raw_bit_field());
  CanonicalType canonical{reinterpret_cast<const CanonicalSig*>(sig),
                          CanonicalTypeIndex{kNoSuperType}, kFinal, kNotShared};
  base::MutexGuard guard(&mutex_);
  // Fast path lookup before canonicalizing (== copying into the
  // TypeCanonicalizer's zone) the function signature.
  CanonicalTypeIndex new_canonical_index{
      static_cast<uint32_t>(canonical_supertypes_.size())};
  CanonicalTypeIndex index = FindCanonicalGroup(
      CanonicalSingletonGroup{canonical, new_canonical_index});
  if (index.valid()) return index;
 
  // Copy into this class's zone to store this as a new canonical function type.
  CanonicalSig::Builder builder(&zone_, sig->return_count(),
                                sig->parameter_count());
  for (ValueType ret : sig->returns()) {
    builder.AddReturn(CanonicalValueType{ret});
  }
  for (ValueType param : sig->parameters()) {
    builder.AddParam(CanonicalValueType{param});
  }
  canonical.function_sig = builder.Get();
 
  CanonicalSingletonGroup group{canonical, new_canonical_index};
  // Copying the signature shouldn't make a difference: There is no match.
  DCHECK(!FindCanonicalGroup(group).valid());
  // Check that the new canonical ID is not used yet.
  DCHECK(std::none_of(
      canonical_singleton_groups_.begin(), canonical_singleton_groups_.end(),
      [=](auto& entry) { return entry.index == new_canonical_index; }));
  DCHECK(std::none_of(
      canonical_groups_.begin(), canonical_groups_.end(),
      [=](auto& entry) { return entry.first == new_canonical_index; }));
  // {group.type} is stack-allocated, whereas {canonical_singleton_groups_}
  // creates a long-lived zone-allocated copy of it.
  const CanonicalSingletonGroup& stored_group =
      *canonical_singleton_groups_.emplace(group).first;
  canonical_supertypes_.push_back(CanonicalTypeIndex{kNoSuperType});
  CheckMaxCanonicalIndex();
  canonical_types_.reserve(new_canonical_index.index + 1, &zone_);
  canonical_types_.set(new_canonical_index, &stored_group.type);
  return new_canonical_index;
}
 
const CanonicalSig* TypeCanonicalizer::LookupFunctionSignature(
    CanonicalTypeIndex index) const {
  const CanonicalType* type = canonical_types_[index];
  SBXCHECK_EQ(type->kind, CanonicalType::kFunction);
  return type->function_sig;
}
 
const CanonicalStructType* TypeCanonicalizer::LookupStruct(
    CanonicalTypeIndex index) const {
  const CanonicalType* type = canonical_types_[index];
  SBXCHECK_EQ(type->kind, CanonicalType::kStruct);
  return type->struct_type;
}
 
const CanonicalArrayType* TypeCanonicalizer::LookupArray(
    CanonicalTypeIndex index) const {
  const CanonicalType* type = canonical_types_[index];
  SBXCHECK_EQ(type->kind, CanonicalType::kArray);
  return type->array_type;
}
 
void TypeCanonicalizer::AddPredefinedArrayTypes() {
  static constexpr std::pair<CanonicalTypeIndex, CanonicalValueType>
      kPredefinedArrayTypes[] = {{kPredefinedArrayI8Index, {kWasmI8}},
                                 {kPredefinedArrayI16Index, {kWasmI16}}};
  canonical_types_.reserve(kNumberOfPredefinedTypes, &zone_);
  for (auto [index, element_type] : kPredefinedArrayTypes) {
    DCHECK_GT(kNumberOfPredefinedTypes, index.index);
    DCHECK_EQ(index.index, canonical_singleton_groups_.size());
    static constexpr bool kMutable = true;
    static constexpr bool kFinal = true;
    static constexpr bool kShared = false;  // TODO(14616): Fix this.
    CanonicalArrayType* type =
        zone_.New<CanonicalArrayType>(element_type, kMutable);
    CanonicalSingletonGroup group{
        .type = CanonicalType(type, CanonicalTypeIndex{kNoSuperType}, kFinal,
                              kShared),
        .index = index};
    const CanonicalSingletonGroup& stored_group =
        *canonical_singleton_groups_.emplace(group).first;
    canonical_types_.set(index, &stored_group.type);
    canonical_supertypes_.emplace_back(CanonicalTypeIndex{kNoSuperType});
    DCHECK_LE(canonical_supertypes_.size(), kMaxCanonicalTypes);
  }
}
 
bool TypeCanonicalizer::IsCanonicalSubtype(CanonicalTypeIndex sub_index,
                                           CanonicalTypeIndex super_index) {
  // Fast path without synchronization:
  if (sub_index == super_index) return true;
 
  // Multiple threads could try to register and access recursive groups
  // concurrently.
  // TODO(manoskouk): Investigate if we can improve this synchronization.
  base::MutexGuard mutex_guard(&mutex_);
  return IsCanonicalSubtype_Locked(sub_index, super_index);
}
bool TypeCanonicalizer::IsCanonicalSubtype_Locked(
    CanonicalTypeIndex sub_index, CanonicalTypeIndex super_index) const {
  while (sub_index.valid()) {
    if (sub_index == super_index) return true;
    // TODO(jkummerow): Investigate if replacing this with
    // `sub_index = canonical_types_[sub_index].supertype;`
    // has acceptable performance, which would allow us to save the memory
    // cost of storing {canonical_supertypes_}.
    sub_index = canonical_supertypes_[sub_index.index];
  }
  return false;
}
 
bool TypeCanonicalizer::IsCanonicalSubtype(ModuleTypeIndex sub_index,
                                           ModuleTypeIndex super_index,
                                           const WasmModule* sub_module,
                                           const WasmModule* super_module) {
  CanonicalTypeIndex canonical_super =
      super_module->canonical_type_id(super_index);
  CanonicalTypeIndex canonical_sub = sub_module->canonical_type_id(sub_index);
  return IsCanonicalSubtype(canonical_sub, canonical_super);
}
 
bool TypeCanonicalizer::IsHeapSubtype(CanonicalTypeIndex sub,
                                      CanonicalTypeIndex super) const {
  DCHECK_NE(sub, super);
  base::MutexGuard mutex_guard(&mutex_);
  return IsCanonicalSubtype_Locked(sub, super);
}
 
void TypeCanonicalizer::EmptyStorageForTesting() {
  // Any remaining native modules might reference the types we're about to
  // clear.
  CHECK_EQ(GetWasmEngine()->NativeModuleCount(), 0);
 
  base::MutexGuard mutex_guard(&mutex_);
  canonical_types_.ClearForTesting();
  canonical_supertypes_.clear();
  canonical_groups_.clear();
  canonical_singleton_groups_.clear();
  zone_.Reset();
  AddPredefinedArrayTypes();
}
 
TypeCanonicalizer::CanonicalType TypeCanonicalizer::CanonicalizeTypeDef(
    const WasmModule* module, ModuleTypeIndex module_type_idx,
    ModuleTypeIndex recgroup_start,
    CanonicalTypeIndex canonical_recgroup_start) {
  mutex_.AssertHeld();  // The caller must hold the mutex.
 
  auto CanonicalizeTypeIndex = [=](ModuleTypeIndex type_index) {
    if (!type_index.valid()) return CanonicalTypeIndex::Invalid();
    DCHECK(type_index.valid());
    if (type_index < recgroup_start) {
      // This references a type from an earlier recgroup; use the
      // already-canonicalized type index.
      return module->canonical_type_id(type_index);
    }
    // For types within the same recgroup, generate indexes assuming that this
    // is a new canonical recgroup. To prevent truncation in the
    // CanonicalValueType's bit field, we must check the range here.
    uint32_t new_index = canonical_recgroup_start.index +
                         (type_index.index - recgroup_start.index);
    if (V8_UNLIKELY(new_index >= kMaxCanonicalTypes)) {
      V8::FatalProcessOutOfMemory(nullptr, "too many canonicalized types");
    }
    return CanonicalTypeIndex{new_index};
  };
 
  auto CanonicalizeValueType = [=](ValueType type) {
    if (!type.has_index()) return CanonicalValueType{type};
    static_assert(kMaxCanonicalTypes <=
                  (1 << CanonicalValueType::kNumIndexBits));
    return type.Canonicalize(CanonicalizeTypeIndex(type.ref_index()));
  };
 
  TypeDefinition type = module->type(module_type_idx);
  CanonicalTypeIndex supertype = CanonicalizeTypeIndex(type.supertype);
  switch (type.kind) {
    case TypeDefinition::kFunction: {
      const FunctionSig* original_sig = type.function_sig;
      CanonicalSig::Builder builder(&zone_, original_sig->return_count(),
                                    original_sig->parameter_count());
      for (ValueType ret : original_sig->returns()) {
        builder.AddReturn(CanonicalizeValueType(ret));
      }
      for (ValueType param : original_sig->parameters()) {
        builder.AddParam(CanonicalizeValueType(param));
      }
      return CanonicalType(builder.Get(), supertype, type.is_final,
                           type.is_shared);
    }
    case TypeDefinition::kStruct: {
      const StructType* original_type = type.struct_type;
      CanonicalStructType::Builder builder(&zone_, original_type->field_count(),
                                           original_type->is_descriptor());
      for (uint32_t i = 0; i < original_type->field_count(); i++) {
        builder.AddField(CanonicalizeValueType(original_type->field(i)),
                         original_type->mutability(i),
                         original_type->field_offset(i));
      }
      builder.set_total_fields_size(original_type->total_fields_size());
      return CanonicalType(
          builder.Build(CanonicalStructType::Builder::kUseProvidedOffsets),
          supertype, CanonicalizeTypeIndex(type.descriptor),
          CanonicalizeTypeIndex(type.describes), type.is_final, type.is_shared);
    }
    case TypeDefinition::kArray: {
      CanonicalValueType element_type =
          CanonicalizeValueType(type.array_type->element_type());
      CanonicalArrayType* array_type = zone_.New<CanonicalArrayType>(
          element_type, type.array_type->mutability());
      return CanonicalType(array_type, supertype, type.is_final,
                           type.is_shared);
    }
    case TypeDefinition::kCont: {
      CanonicalTypeIndex canonical_index =
          CanonicalizeTypeIndex(type.cont_type->contfun_typeindex());
      CanonicalContType* canonical_cont =
          zone_.New<CanonicalContType>(canonical_index);
      return CanonicalType(canonical_cont, supertype, type.is_final,
                           type.is_shared);
    }
  }
}
 
// Returns the index of the canonical representative of the first type in this
// group if it exists, and `CanonicalTypeIndex::Invalid()` otherwise.
CanonicalTypeIndex TypeCanonicalizer::FindCanonicalGroup(
    const CanonicalGroup& group) const {
  // Groups of size 0 do not make sense here; groups of size 1 should use
  // {CanonicalSingletonGroup} (see below).
  DCHECK_LT(1, group.types.size());
  auto it = canonical_groups_.find(group);
  return it == canonical_groups_.end() ? CanonicalTypeIndex::Invalid()
                                       : it->first;
}
 
// Returns the canonical index of the given group if it already exists.
CanonicalTypeIndex TypeCanonicalizer::FindCanonicalGroup(
    const CanonicalSingletonGroup& group) const {
  auto it = canonical_singleton_groups_.find(group);
  static_assert(kMaxCanonicalTypes <= kMaxInt);
  return it == canonical_singleton_groups_.end() ? CanonicalTypeIndex::Invalid()
                                                 : it->index;
}
 
size_t TypeCanonicalizer::EstimateCurrentMemoryConsumption() const {
  UPDATE_WHEN_CLASS_CHANGES(TypeCanonicalizer, 8040);
  // The storage of the canonical group's types is accounted for via the
  // allocator below (which tracks the zone memory).
  base::MutexGuard mutex_guard(&mutex_);
  size_t result = ContentSize(canonical_supertypes_);
  result += ContentSize(canonical_groups_);
  result += ContentSize(canonical_singleton_groups_);
  // Note: the allocator also tracks zone allocations of `canonical_types_`.
  result += allocator_.GetCurrentMemoryUsage();
  if (v8_flags.trace_wasm_offheap_memory) {
    PrintF("TypeCanonicalizer: %zu\n", result);
  }
  return result;
}
 
size_t TypeCanonicalizer::GetCurrentNumberOfTypes() const {
  base::MutexGuard mutex_guard(&mutex_);
  return canonical_supertypes_.size();
}
 
// static
void TypeCanonicalizer::PrepareForCanonicalTypeId(Isolate* isolate,
                                                  CanonicalTypeIndex id) {
  if (!id.valid()) return;
  Heap* heap = isolate->heap();
  // {2 * (id + 1)} needs to fit in an int.
  CHECK_LE(id.index, kMaxInt / 2 - 1);
  // Canonical types and wrappers are zero-indexed.
  const int length = id.index + 1;
  // The fast path is non-handlified.
  Tagged<WeakFixedArray> old_rtts_raw = heap->wasm_canonical_rtts();
  Tagged<WeakFixedArray> old_wrappers_raw = heap->js_to_wasm_wrappers();
 
  // Fast path: Lengths are sufficient.
  int old_length = old_rtts_raw->length();
  DCHECK_EQ(old_length, old_wrappers_raw->length());
  if (old_length >= length) return;
 
  // Allocate bigger WeakFixedArrays for rtts and wrappers. Grow them
  // exponentially.
  const int new_length = std::max(old_length * 3 / 2, length);
  CHECK_LT(old_length, new_length);
 
  // Allocation can invalidate previous unhandled pointers.
  DirectHandle<WeakFixedArray> old_rtts{old_rtts_raw, isolate};
  DirectHandle<WeakFixedArray> old_wrappers{old_wrappers_raw, isolate};
  old_rtts_raw = old_wrappers_raw = {};
 
  // We allocate the WeakFixedArray filled with undefined values, as we cannot
  // pass the cleared value in a handle (see https://crbug.com/364591622). We
  // overwrite the new entries via {MemsetTagged} afterwards.
  DirectHandle<WeakFixedArray> new_rtts =
      WeakFixedArray::New(isolate, new_length, AllocationType::kOld);
  WeakFixedArray::CopyElements(isolate, *new_rtts, 0, *old_rtts, 0, old_length);
  MemsetTagged(new_rtts->RawFieldOfFirstElement() + old_length,
               ClearedValue(isolate), new_length - old_length);
  DirectHandle<WeakFixedArray> new_wrappers =
      WeakFixedArray::New(isolate, new_length, AllocationType::kOld);
  WeakFixedArray::CopyElements(isolate, *new_wrappers, 0, *old_wrappers, 0,
                               old_length);
  MemsetTagged(new_wrappers->RawFieldOfFirstElement() + old_length,
               ClearedValue(isolate), new_length - old_length);
  heap->SetWasmCanonicalRttsAndJSToWasmWrappers(*new_rtts, *new_wrappers);
}
 
// static
void TypeCanonicalizer::ClearWasmCanonicalTypesForTesting(Isolate* isolate) {
  ReadOnlyRoots roots(isolate);
  isolate->heap()->SetWasmCanonicalRttsAndJSToWasmWrappers(
      roots.empty_weak_fixed_array(), roots.empty_weak_fixed_array());
}
 
bool TypeCanonicalizer::IsFunctionSignature(CanonicalTypeIndex index) const {
  return canonical_types_[index]->kind == CanonicalType::kFunction;
}
bool TypeCanonicalizer::IsStruct(CanonicalTypeIndex index) const {
  return canonical_types_[index]->kind == CanonicalType::kStruct;
}
bool TypeCanonicalizer::IsArray(CanonicalTypeIndex index) const {
  return canonical_types_[index]->kind == CanonicalType::kArray;
}
 
CanonicalTypeIndex TypeCanonicalizer::FindIndex_Slow(
    const CanonicalSig* sig) const {
  // TODO(397489547): Make this faster. The plan is to allocate an extra
  // slot in the Zone immediately preceding each CanonicalSig, so we can
  // get from the sig's address to that slot's address via pointer arithmetic.
  // For now, just search through all known signatures, which is acceptable
  // as long as only the type-reflection proposal needs this.
  // TODO(42210967): Improve this before shipping Type Reflection.
  return canonical_types_.FindIndex_Slow(sig);
}
 
#ifdef DEBUG
bool TypeCanonicalizer::Contains(const CanonicalSig* sig) const {
  base::MutexGuard mutex_guard(&mutex_);
  return zone_.Contains(sig);
}
#endif
 
}  // namespace v8::internal::wasm