// 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. #include "src/transitions.h" #include "src/objects-inl.h" #include "src/transitions-inl.h" #include "src/utils.h" namespace v8 { namespace internal { void TransitionsAccessor::Initialize() { raw_transitions_ = map_->raw_transitions(); if (raw_transitions_->IsSmi()) { encoding_ = kUninitialized; } else if (HeapObject::cast(raw_transitions_)->IsWeakCell()) { encoding_ = kWeakCell; } else if (HeapObject::cast(raw_transitions_)->IsStoreHandler()) { encoding_ = kHandler; } else if (HeapObject::cast(raw_transitions_)->IsTransitionArray()) { encoding_ = kFullTransitionArray; } else { DCHECK(HeapObject::cast(raw_transitions_)->IsPrototypeInfo()); encoding_ = kPrototypeInfo; } target_cell_ = nullptr; #if DEBUG needs_reload_ = false; #endif } Map* TransitionsAccessor::GetSimpleTransition() { switch (encoding()) { case kWeakCell: return Map::cast(GetTargetCell<kWeakCell>()->value()); case kHandler: return Map::cast(GetTargetCell<kHandler>()->value()); default: return nullptr; } } bool TransitionsAccessor::HasSimpleTransitionTo(WeakCell* cell) { DCHECK(cell->value()->IsMap()); switch (encoding()) { case kWeakCell: return raw_transitions_ == cell; case kHandler: return StoreHandler::GetTransitionCell(raw_transitions_) == cell; case kPrototypeInfo: case kUninitialized: case kFullTransitionArray: return false; } UNREACHABLE(); return false; // Make GCC happy. } void TransitionsAccessor::Insert(Handle<Name> name, Handle<Map> target, SimpleTransitionFlag flag) { DCHECK(!map_handle_.is_null()); Isolate* isolate = map_->GetIsolate(); Handle<WeakCell> weak_cell_with_target = Map::WeakCellForMap(target); Reload(); target->SetBackPointer(map_); // If the map doesn't have any transitions at all yet, install the new one. if (encoding() == kUninitialized) { if (flag == SIMPLE_PROPERTY_TRANSITION) { ReplaceTransitions(*weak_cell_with_target); return; } // If the flag requires a full TransitionArray, allocate one. Handle<TransitionArray> result = TransitionArray::Allocate(isolate, 0, 1); ReplaceTransitions(*result); Reload(); } bool is_special_transition = flag == SPECIAL_TRANSITION; // If the map has a simple transition, check if it should be overwritten. Map* simple_transition = GetSimpleTransition(); if (simple_transition != nullptr) { Name* key = GetSimpleTransitionKey(simple_transition); PropertyDetails old_details = GetSimpleTargetDetails(simple_transition); PropertyDetails new_details = is_special_transition ? PropertyDetails::Empty() : GetTargetDetails(*name, *target); if (flag == SIMPLE_PROPERTY_TRANSITION && key->Equals(*name) && old_details.kind() == new_details.kind() && old_details.attributes() == new_details.attributes()) { ReplaceTransitions(*weak_cell_with_target); return; } // Otherwise allocate a full TransitionArray with slack for a new entry. Handle<TransitionArray> result = TransitionArray::Allocate(isolate, 1, 1); // Reload state; the allocation might have caused it to be cleared. Reload(); simple_transition = GetSimpleTransition(); if (simple_transition != nullptr) { result->Set(0, GetSimpleTransitionKey(simple_transition), raw_transitions_); } else { result->SetNumberOfTransitions(0); } ReplaceTransitions(*result); Reload(); } // At this point, we know that the map has a full TransitionArray. DCHECK_EQ(kFullTransitionArray, encoding()); int number_of_transitions = 0; int new_nof = 0; int insertion_index = kNotFound; DCHECK_EQ(is_special_transition, IsSpecialTransition(*name)); PropertyDetails details = is_special_transition ? PropertyDetails::Empty() : GetTargetDetails(*name, *target); { DisallowHeapAllocation no_gc; TransitionArray* array = transitions(); number_of_transitions = array->number_of_transitions(); new_nof = number_of_transitions; int index = is_special_transition ? array->SearchSpecial(Symbol::cast(*name), &insertion_index) : array->Search(details.kind(), *name, details.attributes(), &insertion_index); // If an existing entry was found, overwrite it and return. if (index != kNotFound) { array->SetTarget(index, *weak_cell_with_target); return; } ++new_nof; CHECK_LE(new_nof, kMaxNumberOfTransitions); DCHECK(insertion_index >= 0 && insertion_index <= number_of_transitions); // If there is enough capacity, insert new entry into the existing array. if (new_nof <= array->Capacity()) { array->SetNumberOfTransitions(new_nof); for (index = number_of_transitions; index > insertion_index; --index) { array->SetKey(index, array->GetKey(index - 1)); array->SetTarget(index, array->GetRawTarget(index - 1)); } array->SetKey(index, *name); array->SetTarget(index, *weak_cell_with_target); SLOW_DCHECK(array->IsSortedNoDuplicates()); return; } } // We're gonna need a bigger TransitionArray. Handle<TransitionArray> result = TransitionArray::Allocate( isolate, new_nof, Map::SlackForArraySize(number_of_transitions, kMaxNumberOfTransitions)); // The map's transition array may have shrunk during the allocation above as // it was weakly traversed, though it is guaranteed not to disappear. Trim the // result copy if needed, and recompute variables. Reload(); DisallowHeapAllocation no_gc; TransitionArray* array = transitions(); if (array->number_of_transitions() != number_of_transitions) { DCHECK(array->number_of_transitions() < number_of_transitions); number_of_transitions = array->number_of_transitions(); new_nof = number_of_transitions; insertion_index = kNotFound; int index = is_special_transition ? array->SearchSpecial(Symbol::cast(*name), &insertion_index) : array->Search(details.kind(), *name, details.attributes(), &insertion_index); if (index == kNotFound) { ++new_nof; } else { insertion_index = index; } DCHECK(insertion_index >= 0 && insertion_index <= number_of_transitions); result->Shrink(TransitionArray::ToKeyIndex(new_nof)); result->SetNumberOfTransitions(new_nof); } if (array->HasPrototypeTransitions()) { result->SetPrototypeTransitions(array->GetPrototypeTransitions()); } DCHECK_NE(kNotFound, insertion_index); for (int i = 0; i < insertion_index; ++i) { result->Set(i, array->GetKey(i), array->GetRawTarget(i)); } result->Set(insertion_index, *name, *weak_cell_with_target); for (int i = insertion_index; i < number_of_transitions; ++i) { result->Set(i + 1, array->GetKey(i), array->GetRawTarget(i)); } SLOW_DCHECK(result->IsSortedNoDuplicates()); ReplaceTransitions(*result); } void TransitionsAccessor::UpdateHandler(Name* name, Object* handler) { if (map_->is_dictionary_map()) return; switch (encoding()) { case kPrototypeInfo: case kUninitialized: UNREACHABLE(); return; case kWeakCell: case kHandler: DCHECK_EQ(GetSimpleTransition(), GetTargetFromRaw(handler)); ReplaceTransitions(handler); return; case kFullTransitionArray: { PropertyAttributes attributes = name->IsPrivate() ? DONT_ENUM : NONE; int transition = transitions()->Search(kData, name, attributes); DCHECK_NE(kNotFound, transition); DCHECK_EQ(transitions()->GetTarget(transition), GetTargetFromRaw(handler)); transitions()->SetTarget(transition, handler); return; } } } Object* TransitionsAccessor::SearchHandler(Name* name, Handle<Map>* out_transition) { switch (encoding()) { case kPrototypeInfo: case kUninitialized: case kWeakCell: return nullptr; case kHandler: { Object* raw_handler = StoreHandler::ValidHandlerOrNull( raw_transitions_, name, out_transition); if (raw_handler == nullptr) return raw_handler; // Check transition key. WeakCell* target_cell = StoreHandler::GetTransitionCell(raw_handler); if (!IsMatchingMap(target_cell, name, kData, NONE)) return nullptr; return raw_handler; } case kFullTransitionArray: { int transition = transitions()->Search(kData, name, NONE); if (transition == kNotFound) return nullptr; Object* raw_handler = transitions()->GetRawTarget(transition); if (raw_handler->IsStoreHandler()) { return StoreHandler::ValidHandlerOrNull(raw_handler, name, out_transition); } return nullptr; } } UNREACHABLE(); return nullptr; // Make GCC happy. } Map* TransitionsAccessor::SearchTransition(Name* name, PropertyKind kind, PropertyAttributes attributes) { DCHECK(name->IsUniqueName()); WeakCell* cell = nullptr; switch (encoding()) { case kPrototypeInfo: case kUninitialized: return nullptr; case kWeakCell: cell = GetTargetCell<kWeakCell>(); break; case kHandler: cell = GetTargetCell<kHandler>(); break; case kFullTransitionArray: { int transition = transitions()->Search(kind, name, attributes); if (transition == kNotFound) return nullptr; return transitions()->GetTarget(transition); } } DCHECK(!cell->cleared()); if (!IsMatchingMap(cell, name, kind, attributes)) return nullptr; return Map::cast(cell->value()); } Map* TransitionsAccessor::SearchSpecial(Symbol* name) { if (encoding() != kFullTransitionArray) return nullptr; int transition = transitions()->SearchSpecial(name); if (transition == kNotFound) return nullptr; return transitions()->GetTarget(transition); } // static bool TransitionsAccessor::IsSpecialTransition(Name* name) { if (!name->IsSymbol()) return false; Heap* heap = name->GetHeap(); return name == heap->nonextensible_symbol() || name == heap->sealed_symbol() || name == heap->frozen_symbol() || name == heap->elements_transition_symbol() || name == heap->strict_function_transition_symbol(); } Handle<Map> TransitionsAccessor::FindTransitionToField(Handle<Name> name) { DCHECK(name->IsUniqueName()); DisallowHeapAllocation no_gc; Map* target = SearchTransition(*name, kData, NONE); if (target == nullptr) return Handle<Map>::null(); PropertyDetails details = target->GetLastDescriptorDetails(); DCHECK_EQ(NONE, details.attributes()); if (details.location() != kField) return Handle<Map>::null(); DCHECK_EQ(kData, details.kind()); return Handle<Map>(target); } Handle<String> TransitionsAccessor::ExpectedTransitionKey() { DisallowHeapAllocation no_gc; WeakCell* cell = nullptr; switch (encoding()) { case kPrototypeInfo: case kUninitialized: case kFullTransitionArray: return Handle<String>::null(); case kWeakCell: cell = GetTargetCell<kWeakCell>(); break; case kHandler: cell = GetTargetCell<kHandler>(); break; } DCHECK(!cell->cleared()); Map* target = Map::cast(cell->value()); PropertyDetails details = GetSimpleTargetDetails(target); if (details.location() != kField) return Handle<String>::null(); DCHECK_EQ(kData, details.kind()); if (details.attributes() != NONE) return Handle<String>::null(); Name* name = GetSimpleTransitionKey(target); if (!name->IsString()) return Handle<String>::null(); return handle(String::cast(name)); } Handle<Map> TransitionsAccessor::ExpectedTransitionTarget() { DCHECK(!ExpectedTransitionKey().is_null()); return handle(GetTarget(0)); } bool TransitionsAccessor::CanHaveMoreTransitions() { if (map_->is_dictionary_map()) return false; if (encoding() == kFullTransitionArray) { return transitions()->number_of_transitions() < kMaxNumberOfTransitions; } return true; } // static bool TransitionsAccessor::IsMatchingMap(WeakCell* target_cell, Name* name, PropertyKind kind, PropertyAttributes attributes) { Map* target = Map::cast(target_cell->value()); int descriptor = target->LastAdded(); DescriptorArray* descriptors = target->instance_descriptors(); Name* key = descriptors->GetKey(descriptor); if (key != name) return false; PropertyDetails details = descriptors->GetDetails(descriptor); return (details.kind() == kind && details.attributes() == attributes); } // static bool TransitionArray::CompactPrototypeTransitionArray(FixedArray* array) { const int header = kProtoTransitionHeaderSize; int number_of_transitions = NumberOfPrototypeTransitions(array); if (number_of_transitions == 0) { // Empty array cannot be compacted. return false; } int new_number_of_transitions = 0; for (int i = 0; i < number_of_transitions; i++) { Object* cell = array->get(header + i); if (!WeakCell::cast(cell)->cleared()) { if (new_number_of_transitions != i) { array->set(header + new_number_of_transitions, cell); } new_number_of_transitions++; } } // Fill slots that became free with undefined value. for (int i = new_number_of_transitions; i < number_of_transitions; i++) { array->set_undefined(header + i); } if (number_of_transitions != new_number_of_transitions) { SetNumberOfPrototypeTransitions(array, new_number_of_transitions); } return new_number_of_transitions < number_of_transitions; } // static Handle<FixedArray> TransitionArray::GrowPrototypeTransitionArray( Handle<FixedArray> array, int new_capacity, Isolate* isolate) { // Grow array by factor 2 up to MaxCachedPrototypeTransitions. int capacity = array->length() - kProtoTransitionHeaderSize; new_capacity = Min(kMaxCachedPrototypeTransitions, new_capacity); DCHECK_GT(new_capacity, capacity); int grow_by = new_capacity - capacity; array = isolate->factory()->CopyFixedArrayAndGrow(array, grow_by, TENURED); if (capacity < 0) { // There was no prototype transitions array before, so the size // couldn't be copied. Initialize it explicitly. SetNumberOfPrototypeTransitions(*array, 0); } return array; } void TransitionsAccessor::PutPrototypeTransition(Handle<Object> prototype, Handle<Map> target_map) { DCHECK(HeapObject::cast(*prototype)->map()->IsMap()); // Don't cache prototype transition if this map is either shared, or a map of // a prototype. if (map_->is_prototype_map()) return; if (map_->is_dictionary_map() || !FLAG_cache_prototype_transitions) return; const int header = TransitionArray::kProtoTransitionHeaderSize; Handle<FixedArray> cache(GetPrototypeTransitions()); int capacity = cache->length() - header; int transitions = TransitionArray::NumberOfPrototypeTransitions(*cache) + 1; if (transitions > capacity) { // Grow the array if compacting it doesn't free space. if (!TransitionArray::CompactPrototypeTransitionArray(*cache)) { if (capacity == TransitionArray::kMaxCachedPrototypeTransitions) return; cache = TransitionArray::GrowPrototypeTransitionArray( cache, 2 * transitions, target_map->GetIsolate()); Reload(); SetPrototypeTransitions(cache); } } // Reload number of transitions as they might have been compacted. int last = TransitionArray::NumberOfPrototypeTransitions(*cache); int entry = header + last; Handle<WeakCell> target_cell = Map::WeakCellForMap(target_map); Reload(); // Reload after possible GC. cache->set(entry, *target_cell); TransitionArray::SetNumberOfPrototypeTransitions(*cache, last + 1); } Handle<Map> TransitionsAccessor::GetPrototypeTransition( Handle<Object> prototype) { DisallowHeapAllocation no_gc; FixedArray* cache = GetPrototypeTransitions(); int length = TransitionArray::NumberOfPrototypeTransitions(cache); for (int i = 0; i < length; i++) { WeakCell* target_cell = WeakCell::cast( cache->get(TransitionArray::kProtoTransitionHeaderSize + i)); if (!target_cell->cleared() && Map::cast(target_cell->value())->prototype() == *prototype) { return handle(Map::cast(target_cell->value())); } } return Handle<Map>(); } FixedArray* TransitionsAccessor::GetPrototypeTransitions() { if (encoding() != kFullTransitionArray || !transitions()->HasPrototypeTransitions()) { return map_->GetHeap()->empty_fixed_array(); } return transitions()->GetPrototypeTransitions(); } // static void TransitionArray::SetNumberOfPrototypeTransitions( FixedArray* proto_transitions, int value) { DCHECK_NE(proto_transitions->length(), 0); proto_transitions->set(kProtoTransitionNumberOfEntriesOffset, Smi::FromInt(value)); } int TransitionsAccessor::NumberOfTransitions() { switch (encoding()) { case kPrototypeInfo: case kUninitialized: return 0; case kWeakCell: case kHandler: return 1; case kFullTransitionArray: return transitions()->number_of_transitions(); } UNREACHABLE(); return 0; // Make GCC happy. } Handle<TransitionArray> TransitionArray::Allocate(Isolate* isolate, int number_of_transitions, int slack) { Handle<FixedArray> array = isolate->factory()->NewTransitionArray( LengthFor(number_of_transitions + slack)); array->set(kPrototypeTransitionsIndex, Smi::kZero); array->set(kTransitionLengthIndex, Smi::FromInt(number_of_transitions)); return Handle<TransitionArray>::cast(array); } void TransitionArray::Zap() { MemsetPointer(data_start() + kPrototypeTransitionsIndex, GetHeap()->the_hole_value(), length() - kPrototypeTransitionsIndex); SetNumberOfTransitions(0); } void TransitionsAccessor::ReplaceTransitions(Object* new_transitions) { if (encoding() == kFullTransitionArray) { TransitionArray* old_transitions = transitions(); #if DEBUG CheckNewTransitionsAreConsistent(old_transitions, new_transitions); DCHECK(old_transitions != new_transitions); #endif // Transition arrays are not shared. When one is replaced, it should not // keep referenced objects alive, so we zap it. // When there is another reference to the array somewhere (e.g. a handle), // not zapping turns from a waste of memory into a source of crashes. old_transitions->Zap(); } map_->set_raw_transitions(new_transitions); MarkNeedsReload(); } void TransitionsAccessor::SetPrototypeTransitions( Handle<FixedArray> proto_transitions) { EnsureHasFullTransitionArray(); transitions()->SetPrototypeTransitions(*proto_transitions); } void TransitionsAccessor::EnsureHasFullTransitionArray() { if (encoding() == kFullTransitionArray) return; int nof = encoding() == kUninitialized ? 0 : 1; Handle<TransitionArray> result = TransitionArray::Allocate(map_->GetIsolate(), nof); Reload(); // Reload after possible GC. if (nof == 1) { if (encoding() == kUninitialized) { // If allocation caused GC and cleared the target, trim the new array. result->Shrink(TransitionArray::ToKeyIndex(0)); result->SetNumberOfTransitions(0); } else { // Otherwise populate the new array. Handle<Map> target(GetSimpleTransition()); Handle<WeakCell> weak_cell_with_target = Map::WeakCellForMap(target); Reload(); // Reload after possible GC. Name* key = GetSimpleTransitionKey(*target); result->Set(0, key, *weak_cell_with_target); } } ReplaceTransitions(*result); Reload(); // Reload after replacing transitions. } void TransitionsAccessor::TraverseTransitionTreeInternal( TraverseCallback callback, void* data, DisallowHeapAllocation* no_gc) { Map* simple_target = nullptr; switch (encoding()) { case kPrototypeInfo: case kUninitialized: break; case kWeakCell: simple_target = Map::cast(GetTargetCell<kWeakCell>()->value()); break; case kHandler: simple_target = Map::cast(GetTargetCell<kHandler>()->value()); break; case kFullTransitionArray: { if (transitions()->HasPrototypeTransitions()) { FixedArray* proto_trans = transitions()->GetPrototypeTransitions(); int length = TransitionArray::NumberOfPrototypeTransitions(proto_trans); for (int i = 0; i < length; ++i) { int index = TransitionArray::kProtoTransitionHeaderSize + i; WeakCell* cell = WeakCell::cast(proto_trans->get(index)); if (cell->cleared()) continue; TransitionsAccessor(Map::cast(cell->value()), no_gc) .TraverseTransitionTreeInternal(callback, data, no_gc); } } for (int i = 0; i < transitions()->number_of_transitions(); ++i) { TransitionsAccessor(transitions()->GetTarget(i), no_gc) .TraverseTransitionTreeInternal(callback, data, no_gc); } break; } } if (simple_target != nullptr) { TransitionsAccessor(simple_target, no_gc) .TraverseTransitionTreeInternal(callback, data, no_gc); } callback(map_, data); } #ifdef DEBUG void TransitionsAccessor::CheckNewTransitionsAreConsistent( TransitionArray* old_transitions, Object* transitions) { // This function only handles full transition arrays. DCHECK_EQ(kFullTransitionArray, encoding()); TransitionArray* new_transitions = TransitionArray::cast(transitions); for (int i = 0; i < old_transitions->number_of_transitions(); i++) { Map* target = old_transitions->GetTarget(i); if (target->instance_descriptors() == map_->instance_descriptors()) { Name* key = old_transitions->GetKey(i); int new_target_index; if (IsSpecialTransition(key)) { new_target_index = new_transitions->SearchSpecial(Symbol::cast(key)); } else { PropertyDetails details = GetTargetDetails(key, target); new_target_index = new_transitions->Search(details.kind(), key, details.attributes()); } DCHECK_NE(TransitionArray::kNotFound, new_target_index); DCHECK_EQ(target, new_transitions->GetTarget(new_target_index)); } } } #endif // Private non-static helper functions (operating on full transition arrays). int TransitionArray::SearchDetails(int transition, PropertyKind kind, PropertyAttributes attributes, int* out_insertion_index) { int nof_transitions = number_of_transitions(); DCHECK(transition < nof_transitions); Name* key = GetKey(transition); for (; transition < nof_transitions && GetKey(transition) == key; transition++) { Map* target = GetTarget(transition); PropertyDetails target_details = TransitionsAccessor::GetTargetDetails(key, target); int cmp = CompareDetails(kind, attributes, target_details.kind(), target_details.attributes()); if (cmp == 0) { return transition; } else if (cmp < 0) { break; } } if (out_insertion_index != nullptr) *out_insertion_index = transition; return kNotFound; } int TransitionArray::Search(PropertyKind kind, Name* name, PropertyAttributes attributes, int* out_insertion_index) { int transition = SearchName(name, out_insertion_index); if (transition == kNotFound) return kNotFound; return SearchDetails(transition, kind, attributes, out_insertion_index); } void TransitionArray::Sort() { DisallowHeapAllocation no_gc; // In-place insertion sort. int length = number_of_transitions(); for (int i = 1; i < length; i++) { Name* key = GetKey(i); Object* target = GetRawTarget(i); PropertyKind kind = kData; PropertyAttributes attributes = NONE; if (!TransitionsAccessor::IsSpecialTransition(key)) { Map* target_map = TransitionsAccessor::GetTargetFromRaw(target); PropertyDetails details = TransitionsAccessor::GetTargetDetails(key, target_map); kind = details.kind(); attributes = details.attributes(); } int j; for (j = i - 1; j >= 0; j--) { Name* temp_key = GetKey(j); Object* temp_target = GetRawTarget(j); PropertyKind temp_kind = kData; PropertyAttributes temp_attributes = NONE; if (!TransitionsAccessor::IsSpecialTransition(temp_key)) { Map* temp_target_map = TransitionsAccessor::GetTargetFromRaw(temp_target); PropertyDetails details = TransitionsAccessor::GetTargetDetails(temp_key, temp_target_map); temp_kind = details.kind(); temp_attributes = details.attributes(); } int cmp = CompareKeys(temp_key, temp_key->Hash(), temp_kind, temp_attributes, key, key->Hash(), kind, attributes); if (cmp > 0) { SetKey(j + 1, temp_key); SetTarget(j + 1, temp_target); } else { break; } } SetKey(j + 1, key); SetTarget(j + 1, target); } DCHECK(IsSortedNoDuplicates()); } } // namespace internal } // namespace v8