// Copyright 2023 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/objects/js-struct.h"
#include "src/heap/heap-layout-inl.h"
#include "src/objects/dictionary-inl.h"
#include "src/objects/lookup-inl.h"
#include "src/objects/map-inl.h"
#include "src/objects/off-heap-hash-table-inl.h"
#include "src/objects/property-descriptor.h"
namespace v8 {
namespace internal {
namespace {
void PrepareMapCommon(Tagged<Map> map) {
DCHECK(IsAlwaysSharedSpaceJSObjectMap(map));
DisallowGarbageCollection no_gc;
// Shared objects have fixed layout ahead of time, so there's no slack.
map->SetInObjectUnusedPropertyFields(0);
// Shared objects are not extensible and have a null prototype.
map->set_is_extensible(false);
// Shared space objects are not optimizable as prototypes because it is
// not threadsafe.
map->set_prototype_validity_cell(Map::kNoValidityCellSentinel, kRelaxedStore,
SKIP_WRITE_BARRIER);
}
} // namespace
// static
void AlwaysSharedSpaceJSObject::PrepareMapNoEnumerableProperties(
Tagged<Map> map) {
PrepareMapCommon(map);
map->SetEnumLength(0);
}
// static
void AlwaysSharedSpaceJSObject::PrepareMapNoEnumerableProperties(
Isolate* isolate, Tagged<Map> map, Tagged<DescriptorArray> descriptors) {
PrepareMapCommon(map);
map->InitializeDescriptors(descriptors);
DCHECK_EQ(0, map->NumberOfEnumerableProperties());
map->SetEnumLength(0);
}
// static
void AlwaysSharedSpaceJSObject::PrepareMapWithEnumerableProperties(
Isolate* isolate, DirectHandle<Map> map,
DirectHandle<DescriptorArray> descriptors, int enum_length) {
PrepareMapCommon(*map);
// Shared objects with enumerable own properties need to pre-create the enum
// cache, as creating it lazily is racy.
map->InitializeDescriptors(*descriptors);
FastKeyAccumulator::InitializeFastPropertyEnumCache(
isolate, map, enum_length, AllocationType::kSharedOld);
DCHECK_EQ(enum_length, map->EnumLength());
}
// static
Maybe<bool> AlwaysSharedSpaceJSObject::DefineOwnProperty(
Isolate* isolate, DirectHandle<AlwaysSharedSpaceJSObject> shared_obj,
DirectHandle<Object> key, PropertyDescriptor* desc,
Maybe<ShouldThrow> should_throw) {
// Shared objects are designed to have fixed layout, i.e. their maps are
// effectively immutable. They are constructed seal, but the semantics of
// ordinary ECMAScript objects allow writable properties to be upgraded to
// non-writable properties. This upgrade violates the fixed layout invariant
// and is disallowed.
DCHECK(IsName(*key) || IsNumber(*key)); // |key| is a PropertyKey.
PropertyKey lookup_key(isolate, key);
LookupIterator it(isolate, shared_obj, lookup_key, LookupIterator::OWN);
PropertyDescriptor current;
MAYBE_RETURN(JSReceiver::GetOwnPropertyDescriptor(&it, ¤t),
Nothing<bool>());
// The only redefinition allowed is to set the value if all attributes match.
if (!it.IsFound() ||
PropertyDescriptor::IsDataDescriptor(desc) !=
PropertyDescriptor::IsDataDescriptor(¤t) ||
desc->ToAttributes() != current.ToAttributes()) {
DCHECK(!shared_obj->map()->is_extensible());
RETURN_FAILURE(isolate, GetShouldThrow(isolate, should_throw),
NewTypeError(MessageTemplate::kDefineDisallowedFixedLayout,
it.GetName()));
}
DCHECK(it.property_attributes() == desc->ToAttributes());
if (desc->has_value()) {
if (Object::SameValue(*desc->value(), *current.value())) {
return Just(true);
}
// If the property is read-only, we cannot overwrite it with a different
// value (which we know it is because of the SameValue check above).
if (it.property_details().IsReadOnly()) {
RETURN_FAILURE(
isolate, GetShouldThrow(isolate, should_throw),
NewTypeError(MessageTemplate::kRedefineDisallowed, it.GetName()));
}
return Object::SetDataProperty(&it, desc->value());
}
return Just(true);
}
Maybe<bool> AlwaysSharedSpaceJSObject::HasInstance(
Isolate* isolate, DirectHandle<JSFunction> constructor,
DirectHandle<Object> object) {
if (!constructor->has_prototype_slot() || !constructor->has_initial_map() ||
!IsJSReceiver(*object)) {
return Just(false);
}
DirectHandle<Map> constructor_map(constructor->initial_map(), isolate);
PrototypeIterator iter(isolate, Cast<JSReceiver>(object), kStartAtReceiver);
DirectHandle<Map> current_map;
while (true) {
current_map =
direct_handle(PrototypeIterator::GetCurrent(iter)->map(), isolate);
if (current_map.is_identical_to(constructor_map)) {
return Just(true);
}
if (!iter.AdvanceFollowingProxies()) return Nothing<bool>();
if (iter.IsAtEnd()) return Just(false);
}
}
namespace {
// Currently there are 2, both optionally present:
// - Registry key
// - Elements template
constexpr int kSpecialSlots = 2;
InternalIndex GetSpecialSlotIndex(Tagged<Map> instance_map,
Tagged<Symbol> special_slot_name) {
DCHECK(IsJSSharedStructMap(instance_map));
DCHECK(IsPrivateSymbol(special_slot_name));
Tagged<DescriptorArray> descriptors = instance_map->instance_descriptors();
// Special slots are optional and start at descriptor number 0.
int end = std::min(static_cast<int>(descriptors->number_of_all_descriptors()),
kSpecialSlots);
for (int i = 0; i < end; ++i) {
InternalIndex idx(i);
if (descriptors->GetKey(idx) == special_slot_name) {
DCHECK_EQ(PropertyLocation::kDescriptor,
descriptors->GetDetails(idx).location());
return idx;
}
}
return InternalIndex::NotFound();
}
template <typename T>
MaybeHandle<T> GetSpecialSlotValue(Isolate* isolate, Tagged<Map> instance_map,
Tagged<Symbol> special_slot_name) {
DisallowGarbageCollection no_gc;
MaybeHandle<T> result;
InternalIndex entry = GetSpecialSlotIndex(instance_map, special_slot_name);
if (entry.is_found()) {
DCHECK_IMPLIES(
special_slot_name ==
ReadOnlyRoots(isolate).shared_struct_map_registry_key_symbol(),
entry.as_int() == 0);
result = handle(
Cast<T>(instance_map->instance_descriptors()->GetStrongValue(entry)),
isolate);
}
return result;
}
} // namespace
// static
DirectHandle<Map> JSSharedStruct::CreateInstanceMap(
Isolate* isolate, const base::Vector<const DirectHandle<Name>> field_names,
const std::set<uint32_t>& element_names,
MaybeDirectHandle<String> maybe_registry_key,
bool has_interesting_properties) {
auto* factory = isolate->factory();
int num_fields = static_cast<int>(field_names.size());
int num_descriptors = num_fields;
// If there are elements, an template NumberDictionary is created and stored
// as a data constant on a descriptor.
if (!element_names.empty()) num_descriptors++;
// If this is a registered map, the key is stored as a data constant on a
// descriptor because the registry stores the maps weakly. Storing the key in
// the map simplifies the weakness handling in the GC.
if (!maybe_registry_key.is_null()) num_descriptors++;
// Calculate the size for instances.
int instance_size;
int in_object_properties;
JSFunction::CalculateInstanceSizeHelper(JS_SHARED_STRUCT_TYPE, 0, num_fields,
&instance_size,
&in_object_properties);
// Create the DescriptorArray if there are fields or elements.
DirectHandle<DescriptorArray> descriptors;
if (num_descriptors != 0) {
descriptors = factory->NewDescriptorArray(num_descriptors, 0,
AllocationType::kSharedOld);
InternalIndex descriptor_index(0);
// Store the registry key if the map is registered. This must be the first
// slot if present. The registry depends on this for rehashing.
DirectHandle<String> registry_key;
if (maybe_registry_key.ToHandle(®istry_key)) {
Descriptor d = Descriptor::DataConstant(
factory->shared_struct_map_registry_key_symbol(), registry_key,
ALL_ATTRIBUTES_MASK);
DCHECK_EQ(InternalIndex(0), descriptor_index);
descriptors->Set(descriptor_index++, &d);
}
// Elements in shared structs are only supported as a dictionary. Create the
// template NumberDictionary if needed.
if (!element_names.empty()) {
DirectHandle<NumberDictionary> elements_template;
int num_elements = static_cast<int>(element_names.size());
elements_template = NumberDictionary::New(isolate, num_elements,
AllocationType::kSharedOld);
for (uint32_t index : element_names) {
PropertyDetails details(PropertyKind::kData, SEALED,
PropertyConstness::kMutable, 0);
NumberDictionary::UncheckedAdd<Isolate, DirectHandle,
AllocationType::kSharedOld>(
isolate, elements_template, index,
isolate->factory()->undefined_value(), details);
}
elements_template->SetInitialNumberOfElements(num_elements);
DCHECK(HeapLayout::InAnySharedSpace(*elements_template));
Descriptor d = Descriptor::DataConstant(
factory->shared_struct_map_elements_template_symbol(),
elements_template, ALL_ATTRIBUTES_MASK);
descriptors->Set(descriptor_index++, &d);
}
DCHECK_LE(descriptor_index.as_uint32(), kSpecialSlots);
int field_index = 0;
for (DirectHandle<Name> field_name : field_names) {
bool is_inobject = field_index < in_object_properties;
int field_offset =
is_inobject ? JSSharedStruct::kHeaderSize + field_index * kTaggedSize
: FixedArray::OffsetOfElementAt(field_index -
in_object_properties);
// Shared structs' fields need to be aligned, so make it all tagged.
PropertyDetails details(
PropertyKind::kData, SEALED, PropertyLocation::kField,
PropertyConstness::kMutable, Representation::Tagged(), field_offset,
is_inobject);
descriptors->Set(descriptor_index++, *field_name, FieldType::Any(),
details);
field_index++;
}
DCHECK_EQ(field_index, num_fields);
descriptors->Sort();
}
// Create the map.
DirectHandle<Map> instance_map = factory->NewContextlessMap(
JS_SHARED_STRUCT_TYPE, instance_size, DICTIONARY_ELEMENTS,
in_object_properties, AllocationType::kSharedMap);
if (has_interesting_properties) {
instance_map->set_may_have_interesting_properties(true);
}
// Prepare the enum cache if necessary.
if (num_descriptors == 0) {
DCHECK_EQ(0, num_fields);
// No properties at all.
AlwaysSharedSpaceJSObject::PrepareMapNoEnumerableProperties(*instance_map);
} else if (num_fields == 0) {
// Have descriptors, but no enumerable fields.
AlwaysSharedSpaceJSObject::PrepareMapNoEnumerableProperties(
isolate, *instance_map, *descriptors);
} else {
// Have enumerable fields.
AlwaysSharedSpaceJSObject::PrepareMapWithEnumerableProperties(
isolate, instance_map, descriptors, num_fields);
}
// Structs have fixed layout ahead of time, so there's no slack.
int out_of_object_properties = num_fields - in_object_properties;
if (out_of_object_properties != 0) {
instance_map->SetOutOfObjectUnusedPropertyFields(0);
}
return instance_map;
}
// static
MaybeHandle<String> JSSharedStruct::GetRegistryKey(Isolate* isolate,
Tagged<Map> instance_map) {
return GetSpecialSlotValue<String>(
isolate, instance_map,
ReadOnlyRoots(isolate).shared_struct_map_registry_key_symbol());
}
// static
bool JSSharedStruct::IsRegistryKeyDescriptor(Isolate* isolate,
Tagged<Map> instance_map,
InternalIndex i) {
DCHECK(IsJSSharedStructMap(instance_map));
return instance_map->instance_descriptors()->GetKey(i) ==
ReadOnlyRoots(isolate).shared_struct_map_registry_key_symbol();
}
// static
MaybeDirectHandle<NumberDictionary> JSSharedStruct::GetElementsTemplate(
Isolate* isolate, Tagged<Map> instance_map) {
return GetSpecialSlotValue<NumberDictionary>(
isolate, instance_map,
ReadOnlyRoots(isolate).shared_struct_map_elements_template_symbol());
}
// static
bool JSSharedStruct::IsElementsTemplateDescriptor(Isolate* isolate,
Tagged<Map> instance_map,
InternalIndex i) {
DCHECK(IsJSSharedStructMap(instance_map));
return instance_map->instance_descriptors()->GetKey(i) ==
ReadOnlyRoots(isolate).shared_struct_map_elements_template_symbol();
}
// Hash table mapping string keys to shared struct maps.
class SharedStructTypeRegistry::Data : public OffHeapHashTableBase<Data> {
public:
static constexpr int kEntrySize = 1;
static constexpr int kMaxEmptyFactor = 4;
static constexpr int kMinCapacity = 4;
explicit Data(int capacity) : OffHeapHashTableBase<Data>(capacity) {}
static uint32_t Hash(PtrComprCageBase cage_base, Tagged<Object> key) {
// Registry keys, if present, store them at the first descriptor. All maps
// in the registry have registry keys.
return Cast<String>(Cast<Map>(key)->instance_descriptors()->GetStrongValue(
InternalIndex(0)))
->hash();
}
template <typename IsolateT>
static bool KeyIsMatch(IsolateT* isolate, DirectHandle<String> key,
Tagged<Object> obj) {
DirectHandle<String> existing =
JSSharedStruct::GetRegistryKey(isolate, Cast<Map>(obj))
.ToHandleChecked();
DCHECK(IsInternalizedString(*key));
DCHECK(IsInternalizedString(*existing));
return *key == *existing;
}
Tagged<Object> GetKey(PtrComprCageBase cage_base, InternalIndex index) const {
return slot(index).load(cage_base);
}
void SetKey(InternalIndex index, Tagged<Object> key) {
DCHECK(IsMap(key));
slot(index).store(key);
}
void Set(InternalIndex index, Tagged<Map> map) { SetKey(index, map); }
void CopyEntryExcludingKeyInto(PtrComprCageBase cage_base,
InternalIndex from_index, Data* to,
InternalIndex to_index) {
// Do nothing, since kEntrySize is 1.
}
static std::unique_ptr<Data> New(int capacity) {
return std::unique_ptr<Data>(new (capacity) Data(capacity));
}
void* operator new(size_t size, int capacity) {
DCHECK_GE(capacity, kMinCapacity);
DCHECK_EQ(size, sizeof(Data));
return OffHeapHashTableBase<Data>::Allocate<Data,
offsetof(Data, elements_)>(
capacity);
}
void* operator new(size_t size) = delete;
void operator delete(void* table) { OffHeapHashTableBase<Data>::Free(table); }
};
SharedStructTypeRegistry::SharedStructTypeRegistry()
: data_(Data::New(Data::kMinCapacity)) {
DCHECK_EQ(deleted_element(), Data::deleted_element());
}
SharedStructTypeRegistry::~SharedStructTypeRegistry() = default;
MaybeDirectHandle<Map> SharedStructTypeRegistry::CheckIfEntryMatches(
Isolate* isolate, InternalIndex entry, DirectHandle<String> key,
const base::Vector<const DirectHandle<Name>> field_names,
const std::set<uint32_t>& element_names) {
Tagged<Map> existing_map = Cast<Map>(data_->GetKey(isolate, entry));
// A map is considered a match iff all of the following hold:
// - field names are the same element-wise (in order)
// - element indices are the same
// Registered types always have the key as the first descriptor.
DCHECK_EQ(
*JSSharedStruct::GetRegistryKey(isolate, existing_map).ToHandleChecked(),
*key);
int num_descriptors = static_cast<int>(field_names.size()) + 1;
if (!element_names.empty()) {
if (JSSharedStruct::GetElementsTemplate(isolate, existing_map).is_null()) {
return MaybeDirectHandle<Map>();
}
num_descriptors++;
}
if (num_descriptors != existing_map->NumberOfOwnDescriptors()) {
return MaybeDirectHandle<Map>();
}
Tagged<DescriptorArray> existing_descriptors =
existing_map->instance_descriptors();
auto field_names_iter = field_names.begin();
for (InternalIndex i : existing_map->IterateOwnDescriptors()) {
if (JSSharedStruct::IsElementsTemplateDescriptor(isolate, existing_map,
i)) {
DirectHandle<NumberDictionary> elements_template(
Cast<NumberDictionary>(
existing_map->instance_descriptors()->GetStrongValue(i)),
isolate);
if (element_names.size() != elements_template->NumberOfElements()) {
return MaybeDirectHandle<Map>();
}
for (int element : element_names) {
if (elements_template->FindEntry(isolate, element).is_not_found()) {
return MaybeDirectHandle<Map>();
}
}
continue;
}
if (JSSharedStruct::IsRegistryKeyDescriptor(isolate, existing_map, i)) {
continue;
}
Tagged<Name> existing_name = existing_descriptors->GetKey(i);
DCHECK(IsUniqueName(existing_name));
Tagged<Name> name = **field_names_iter;
DCHECK(IsUniqueName(name));
if (name != existing_name) return MaybeDirectHandle<Map>();
++field_names_iter;
}
return direct_handle(existing_map, isolate);
}
MaybeDirectHandle<Map> SharedStructTypeRegistry::RegisterNoThrow(
Isolate* isolate, Handle<String> key,
const base::Vector<const DirectHandle<Name>> field_names,
const std::set<uint32_t>& element_names, bool has_interesting_properties) {
key = isolate->factory()->InternalizeString(key);
// To avoid deadlock with iteration during GC and modifying the table, no GC
// must occur under lock.
{
NoGarbageCollectionMutexGuard data_guard(&data_mutex_);
InternalIndex entry = data_->FindEntry(isolate, key, key->hash());
if (entry.is_found()) {
return CheckIfEntryMatches(isolate, entry, key, field_names,
element_names);
}
}
// We have a likely miss. Create a new instance map outside of the lock.
DirectHandle<Map> map = JSSharedStruct::CreateInstanceMap(
isolate, field_names, element_names, key, has_interesting_properties);
// Relookup to see if it's in fact a miss.
NoGarbageCollectionMutexGuard data_guard(&data_mutex_);
EnsureCapacity(isolate, 1);
InternalIndex entry =
data_->FindEntryOrInsertionEntry(isolate, key, key->hash());
Tagged<Object> existing_key = data_->GetKey(isolate, entry);
if (existing_key == Data::empty_element()) {
data_->AddAt(isolate, entry, *map);
return map;
} else if (existing_key == Data::deleted_element()) {
data_->OverwriteDeletedAt(isolate, entry, *map);
return map;
} else {
// An entry with the same key was inserted between the two locks.
return CheckIfEntryMatches(isolate, entry, key, field_names, element_names);
}
}
MaybeDirectHandle<Map> SharedStructTypeRegistry::Register(
Isolate* isolate, Handle<String> key,
const base::Vector<const DirectHandle<Name>> field_names,
const std::set<uint32_t>& element_names, bool has_interesting_properties) {
MaybeDirectHandle<Map> canonical_map = RegisterNoThrow(
isolate, key, field_names, element_names, has_interesting_properties);
if (canonical_map.is_null()) {
THROW_NEW_ERROR(
isolate,
NewTypeError(MessageTemplate::kSharedStructTypeRegistryMismatch, key));
}
return canonical_map;
}
void SharedStructTypeRegistry::IterateElements(Isolate* isolate,
RootVisitor* visitor) {
// Ideally this should only happen during a global safepoint, when all
// workers and background threads are paused, so there would be no need to
// take the data mutex. However, the array left trimming has a verifier
// visitor that visits all roots (including weak ones), thus we take the
// mutex.
//
// TODO(v8:12547): Figure out how to do
// isolate->global_safepoint()->AssertActive() instead.
base::MutexGuard data_guard(&data_mutex_);
data_->IterateElements(Root::kSharedStructTypeRegistry, visitor);
}
void SharedStructTypeRegistry::NotifyElementsRemoved(int count) {
data_->ElementsRemoved(count);
}
void SharedStructTypeRegistry::EnsureCapacity(PtrComprCageBase cage_base,
int additional_elements) {
data_mutex_.AssertHeld();
int new_capacity;
if (data_->ShouldResizeToAdd(additional_elements, &new_capacity)) {
std::unique_ptr<Data> new_data(Data::New(new_capacity));
data_->RehashInto(cage_base, new_data.get());
data_ = std::move(new_data);
}
}
} // namespace internal
} // namespace v8