Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(1193)

Unified Diff: src/transitions.cc

Issue 980573002: Simplify and compact transitions storage (Closed) Base URL: https://chromium.googlesource.com/v8/v8.git@master
Patch Set: fix -Werror=pedantic ( rebase Created 5 years, 10 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
« no previous file with comments | « src/transitions.h ('k') | src/transitions-inl.h » ('j') | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: src/transitions.cc
diff --git a/src/transitions.cc b/src/transitions.cc
index 43fc90b1b51796ddd8c96fd478f902ea822c8a3a..6154b4c1e10db478fc58186d4a396f2e4c5038c3 100644
--- a/src/transitions.cc
+++ b/src/transitions.cc
@@ -12,141 +12,110 @@ namespace v8 {
namespace internal {
-Handle<TransitionArray> TransitionArray::Allocate(Isolate* isolate,
- int number_of_transitions,
- int slack) {
- Handle<FixedArray> array = isolate->factory()->NewFixedArray(
- LengthFor(number_of_transitions + slack));
- array->set(kPrototypeTransitionsIndex, Smi::FromInt(0));
- array->set(kTransitionLengthIndex, Smi::FromInt(number_of_transitions));
- return Handle<TransitionArray>::cast(array);
-}
-
-
-Handle<TransitionArray> TransitionArray::AllocateSimple(Isolate* isolate,
- Handle<Map> target) {
- Handle<FixedArray> array =
- isolate->factory()->NewFixedArray(kSimpleTransitionSize);
- array->set(kSimpleTransitionTarget, *target);
- return Handle<TransitionArray>::cast(array);
-}
-
-
-void TransitionArray::NoIncrementalWriteBarrierCopyFrom(TransitionArray* origin,
- int origin_transition,
- int target_transition) {
- NoIncrementalWriteBarrierSet(target_transition,
- origin->GetKey(origin_transition),
- origin->GetTarget(origin_transition));
-}
-
-
-Handle<TransitionArray> TransitionArray::NewWith(Handle<Map> map,
- Handle<Name> name,
- Handle<Map> target,
- SimpleTransitionFlag flag) {
- Handle<TransitionArray> result;
- Isolate* isolate = name->GetIsolate();
-
- if (flag == SIMPLE_PROPERTY_TRANSITION) {
- result = AllocateSimple(isolate, target);
- } else {
- result = Allocate(isolate, 1);
- result->NoIncrementalWriteBarrierSet(0, *name, *target);
- }
- result->set_back_pointer_storage(map->GetBackPointer());
- return result;
-}
-
-
-Handle<TransitionArray> TransitionArray::ExtendToFullTransitionArray(
- Handle<Map> containing_map) {
- DCHECK(!containing_map->transitions()->IsFullTransitionArray());
- int nof = containing_map->transitions()->number_of_transitions();
-
- // A transition array may shrink during GC.
- Handle<TransitionArray> result = Allocate(containing_map->GetIsolate(), nof);
- DisallowHeapAllocation no_gc;
- int new_nof = containing_map->transitions()->number_of_transitions();
- if (new_nof != nof) {
- DCHECK(new_nof == 0);
- result->Shrink(ToKeyIndex(0));
- result->SetNumberOfTransitions(0);
- } else if (nof == 1) {
- result->NoIncrementalWriteBarrierCopyFrom(
- containing_map->transitions(), kSimpleTransitionIndex, 0);
+// static
+void TransitionArray::Insert(Handle<Map> map, Handle<Name> name,
+ Handle<Map> target, SimpleTransitionFlag flag) {
+ Isolate* isolate = map->GetIsolate();
+ target->SetBackPointer(*map);
+
+ // If the map doesn't have any transitions at all yet, install the new one.
+ if (CanStoreSimpleTransition(map->raw_transitions())) {
+ if (flag == SIMPLE_PROPERTY_TRANSITION) {
+ Handle<WeakCell> cell = Map::WeakCellForMap(target);
+ map->set_raw_transitions(*cell);
+ return;
+ }
+ // If the flag requires a full TransitionArray, allocate one.
+ Handle<TransitionArray> result = Allocate(isolate, 0, 1);
+ map->set_raw_transitions(*result);
}
- result->set_back_pointer_storage(
- containing_map->transitions()->back_pointer_storage());
- return result;
-}
-
-
-Handle<TransitionArray> TransitionArray::Insert(Handle<Map> map,
- Handle<Name> name,
- Handle<Map> target,
- SimpleTransitionFlag flag) {
- if (!map->HasTransitionArray()) {
- return TransitionArray::NewWith(map, name, target, flag);
+ bool is_special_transition = flag == SPECIAL_TRANSITION;
+ // If the map has a simple transition, check if it should be overwritten.
+ if (IsSimpleTransition(map->raw_transitions())) {
+ Map* old_target = GetSimpleTransition(map->raw_transitions());
+ Name* key = GetSimpleTransitionKey(old_target);
+ PropertyDetails old_details = GetSimpleTargetDetails(old_target);
+ PropertyDetails new_details = is_special_transition
+ ? PropertyDetails(NONE, DATA, 0)
+ : GetTargetDetails(*name, *target);
+ if (flag == SIMPLE_PROPERTY_TRANSITION && key->Equals(*name) &&
+ old_details.kind() == new_details.kind() &&
+ old_details.attributes() == new_details.attributes()) {
+ Handle<WeakCell> cell = Map::WeakCellForMap(target);
+ map->set_raw_transitions(*cell);
+ return;
+ }
+ // Otherwise allocate a full TransitionArray with slack for a new entry.
+ Handle<TransitionArray> result = Allocate(isolate, 1, 1);
+ // Re-read existing data; the allocation might have caused it to be cleared.
+ if (IsSimpleTransition(map->raw_transitions())) {
+ old_target = GetSimpleTransition(map->raw_transitions());
+ result->NoIncrementalWriteBarrierSet(
+ 0, GetSimpleTransitionKey(old_target), old_target);
+ } else {
+ result->SetNumberOfTransitions(0);
+ }
+ map->set_raw_transitions(*result);
}
- int number_of_transitions = map->transitions()->number_of_transitions();
- int new_nof = number_of_transitions;
+ // At this point, we know that the map has a full TransitionArray.
+ DCHECK(IsFullTransitionArray(map->raw_transitions()));
- bool is_special_transition = flag == SPECIAL_TRANSITION;
+ 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(NONE, DATA, 0)
: GetTargetDetails(*name, *target);
- int insertion_index = kNotFound;
- int index =
- is_special_transition
- ? map->transitions()->SearchSpecial(Symbol::cast(*name),
- &insertion_index)
- : map->transitions()->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);
-
- CHECK(new_nof <= kMaxNumberOfTransitions);
-
- if (new_nof <= map->transitions()->number_of_transitions_storage()) {
+ {
DisallowHeapAllocation no_gc;
- TransitionArray* array = map->transitions();
+ TransitionArray* array = TransitionArray::cast(map->raw_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, *target);
- return handle(array);
+ return;
}
- array->SetNumberOfTransitions(new_nof);
- for (index = number_of_transitions; index > insertion_index; --index) {
- Name* key = array->GetKey(index - 1);
- array->SetKey(index, key);
- array->SetTarget(index, array->GetTarget(index - 1));
+ ++new_nof;
+ CHECK(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 <= Capacity(array)) {
+ array->SetNumberOfTransitions(new_nof);
+ for (index = number_of_transitions; index > insertion_index; --index) {
+ array->SetKey(index, array->GetKey(index - 1));
+ array->SetTarget(index, array->GetTarget(index - 1));
+ }
+ array->SetKey(index, *name);
+ array->SetTarget(index, *target);
+ SLOW_DCHECK(array->IsSortedNoDuplicates());
+ return;
}
- array->SetKey(index, *name);
- array->SetTarget(index, *target);
- SLOW_DCHECK(array->IsSortedNoDuplicates());
- return handle(array);
}
+ // We're gonna need a bigger TransitionArray.
Handle<TransitionArray> result = Allocate(
map->GetIsolate(), new_nof,
Map::SlackForArraySize(number_of_transitions, kMaxNumberOfTransitions));
- // The map's transition array may grown smaller during the allocation above as
+ // 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.
- DCHECK(map->HasTransitionArray());
+ DCHECK(IsFullTransitionArray(map->raw_transitions()));
DisallowHeapAllocation no_gc;
- TransitionArray* array = map->transitions();
+ TransitionArray* array = TransitionArray::cast(map->raw_transitions());
if (array->number_of_transitions() != number_of_transitions) {
DCHECK(array->number_of_transitions() < number_of_transitions);
@@ -154,11 +123,11 @@ Handle<TransitionArray> TransitionArray::Insert(Handle<Map> map,
new_nof = number_of_transitions;
insertion_index = kNotFound;
- index = is_special_transition ? map->transitions()->SearchSpecial(
- Symbol::cast(*name), &insertion_index)
- : map->transitions()->Search(
- details.kind(), *name,
- details.attributes(), &insertion_index);
+ 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 {
@@ -183,12 +152,332 @@ Handle<TransitionArray> TransitionArray::Insert(Handle<Map> map,
result->NoIncrementalWriteBarrierCopyFrom(array, i, i + 1);
}
- result->set_back_pointer_storage(array->back_pointer_storage());
SLOW_DCHECK(result->IsSortedNoDuplicates());
- return result;
+ map->set_raw_transitions(*result);
+}
+
+
+// static
+Map* TransitionArray::SearchTransition(Map* map, PropertyKind kind, Name* name,
+ PropertyAttributes attributes) {
+ Object* raw_transitions = map->raw_transitions();
+ if (IsSimpleTransition(raw_transitions)) {
+ Map* target = GetSimpleTransition(raw_transitions);
+ Name* key = GetSimpleTransitionKey(target);
+ if (!key->Equals(name)) return NULL;
+ PropertyDetails details = GetSimpleTargetDetails(target);
+ if (details.attributes() != attributes) return NULL;
+ if (details.kind() != kind) return NULL;
+ return target;
+ }
+ if (IsFullTransitionArray(raw_transitions)) {
+ TransitionArray* transitions = TransitionArray::cast(raw_transitions);
+ int transition = transitions->Search(kind, name, attributes);
+ if (transition == kNotFound) return NULL;
+ return transitions->GetTarget(transition);
+ }
+ return NULL;
}
+// static
+Map* TransitionArray::SearchSpecial(Map* map, Symbol* name) {
+ Object* raw_transitions = map->raw_transitions();
+ if (IsFullTransitionArray(raw_transitions)) {
+ TransitionArray* transitions = TransitionArray::cast(raw_transitions);
+ int transition = transitions->SearchSpecial(name);
+ if (transition == kNotFound) return NULL;
+ return transitions->GetTarget(transition);
+ }
+ return NULL;
+}
+
+
+// static
+Handle<Map> TransitionArray::FindTransitionToField(Handle<Map> map,
+ Handle<Name> name) {
+ DisallowHeapAllocation no_gc;
+ Map* target = SearchTransition(*map, kData, *name, NONE);
+ if (target == NULL) return Handle<Map>::null();
+ PropertyDetails details = target->GetLastDescriptorDetails();
+ DCHECK_EQ(NONE, details.attributes());
+ if (details.type() != DATA) return Handle<Map>::null();
+ return Handle<Map>(target);
+}
+
+
+// static
+Handle<String> TransitionArray::ExpectedTransitionKey(Handle<Map> map) {
+ DisallowHeapAllocation no_gc;
+ Object* raw_transition = map->raw_transitions();
+ if (!IsSimpleTransition(raw_transition)) return Handle<String>::null();
+ Map* target = GetSimpleTransition(raw_transition);
+ PropertyDetails details = GetSimpleTargetDetails(target);
+ if (details.type() != DATA) return Handle<String>::null();
+ if (details.attributes() != NONE) return Handle<String>::null();
+ Name* name = GetSimpleTransitionKey(target);
+ if (!name->IsString()) return Handle<String>::null();
+ return Handle<String>(String::cast(name));
+}
+
+
+// static
+bool TransitionArray::CanHaveMoreTransitions(Handle<Map> map) {
+ Object* raw_transitions = map->raw_transitions();
+ if (IsFullTransitionArray(raw_transitions)) {
+ TransitionArray* transitions = TransitionArray::cast(raw_transitions);
+ return transitions->number_of_transitions() < kMaxNumberOfTransitions;
+ }
+ return true;
+}
+
+
+// static
+Handle<Map> TransitionArray::PutPrototypeTransition(Handle<Map> map,
+ 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 map;
+ if (map->is_dictionary_map() || !FLAG_cache_prototype_transitions) return map;
+
+ const int header = kProtoTransitionHeaderSize;
+
+ Handle<FixedArray> cache(GetPrototypeTransitions(*map));
+ int capacity = cache->length() - header;
+ int transitions = NumberOfPrototypeTransitions(*cache) + 1;
+
+ if (transitions > capacity) {
+ // Grow array by factor 2 up to MaxCachedPrototypeTransitions.
+ int new_capacity = Min(kMaxCachedPrototypeTransitions, transitions * 2);
+ if (new_capacity == capacity) return map;
+
+ cache = FixedArray::CopySize(cache, header + new_capacity);
+ if (capacity < 0) {
+ // There was no prototype transitions array before, so the size
+ // couldn't be copied. Initialize it explicitly.
+ SetNumberOfPrototypeTransitions(*cache, 0);
+ }
+
+ SetPrototypeTransitions(map, cache);
+ }
+
+ // Reload number of transitions as GC might shrink them.
+ int last = NumberOfPrototypeTransitions(*cache);
+ int entry = header + last;
+
+ cache->set(entry, *target_map);
+ SetNumberOfPrototypeTransitions(*cache, last + 1);
+
+ return map;
+}
+
+
+// static
+Handle<Map> TransitionArray::GetPrototypeTransition(Handle<Map> map,
+ Handle<Object> prototype) {
+ DisallowHeapAllocation no_gc;
+ FixedArray* cache = GetPrototypeTransitions(*map);
+ int number_of_transitions = NumberOfPrototypeTransitions(cache);
+ for (int i = 0; i < number_of_transitions; i++) {
+ Map* target = Map::cast(cache->get(kProtoTransitionHeaderSize + i));
+ if (target->prototype() == *prototype) return handle(target);
+ }
+ return Handle<Map>();
+}
+
+
+// static
+FixedArray* TransitionArray::GetPrototypeTransitions(Map* map) {
+ Object* raw_transitions = map->raw_transitions();
+ Heap* heap = map->GetHeap();
+ if (!IsFullTransitionArray(raw_transitions)) {
+ return heap->empty_fixed_array();
+ }
+ TransitionArray* transitions = TransitionArray::cast(raw_transitions);
+ if (!transitions->HasPrototypeTransitions()) {
+ return heap->empty_fixed_array();
+ }
+ return transitions->GetPrototypeTransitions();
+}
+
+
+// static
+void TransitionArray::SetNumberOfPrototypeTransitions(
+ FixedArray* proto_transitions, int value) {
+ DCHECK(proto_transitions->length() != 0);
+ proto_transitions->set(kProtoTransitionNumberOfEntriesOffset,
+ Smi::FromInt(value));
+}
+
+
+// static
+int TransitionArray::NumberOfTransitions(Object* raw_transitions) {
+ if (CanStoreSimpleTransition(raw_transitions)) return 0;
+ if (IsSimpleTransition(raw_transitions)) return 1;
+ DCHECK(IsFullTransitionArray(raw_transitions));
+ return TransitionArray::cast(raw_transitions)->number_of_transitions();
+}
+
+
+// static
+int TransitionArray::Capacity(Object* raw_transitions) {
+ if (!IsFullTransitionArray(raw_transitions)) return 1;
+ TransitionArray* t = TransitionArray::cast(raw_transitions);
+ if (t->length() <= kFirstIndex) return 0;
+ return (t->length() - kFirstIndex) / kTransitionSize;
+}
+
+
+// Private static helper functions.
+
+Handle<TransitionArray> TransitionArray::Allocate(Isolate* isolate,
+ int number_of_transitions,
+ int slack) {
+ Handle<FixedArray> array = isolate->factory()->NewFixedArray(
+ LengthFor(number_of_transitions + slack));
+ array->set(kPrototypeTransitionsIndex, Smi::FromInt(0));
+ array->set(kTransitionLengthIndex, Smi::FromInt(number_of_transitions));
+ return Handle<TransitionArray>::cast(array);
+}
+
+
+void TransitionArray::NoIncrementalWriteBarrierCopyFrom(TransitionArray* origin,
+ int origin_transition,
+ int target_transition) {
+ NoIncrementalWriteBarrierSet(target_transition,
+ origin->GetKey(origin_transition),
+ origin->GetTarget(origin_transition));
+}
+
+
+static void ZapTransitionArray(TransitionArray* transitions) {
+ MemsetPointer(transitions->data_start(),
+ transitions->GetHeap()->the_hole_value(),
+ transitions->length());
+}
+
+
+void TransitionArray::ReplaceTransitions(Handle<Map> map,
+ Object* new_transitions) {
+ Object* raw_transitions = map->raw_transitions();
+ if (IsFullTransitionArray(raw_transitions)) {
+ TransitionArray* old_transitions = TransitionArray::cast(raw_transitions);
+#ifdef DEBUG
+ CheckNewTransitionsAreConsistent(map, 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.
+ ZapTransitionArray(old_transitions);
+ }
+ map->set_raw_transitions(new_transitions);
+}
+
+
+static void ZapPrototypeTransitions(Object* raw_transitions) {
+ DCHECK(TransitionArray::IsFullTransitionArray(raw_transitions));
+ TransitionArray* transitions = TransitionArray::cast(raw_transitions);
+ if (!transitions->HasPrototypeTransitions()) return;
+ FixedArray* proto_transitions = transitions->GetPrototypeTransitions();
+ MemsetPointer(proto_transitions->data_start(),
+ proto_transitions->GetHeap()->the_hole_value(),
+ proto_transitions->length());
+}
+
+
+void TransitionArray::SetPrototypeTransitions(
+ Handle<Map> map, Handle<FixedArray> proto_transitions) {
+ EnsureHasFullTransitionArray(map);
+ if (Heap::ShouldZapGarbage()) {
+ Object* raw_transitions = map->raw_transitions();
+ DCHECK(raw_transitions != *proto_transitions);
+ ZapPrototypeTransitions(raw_transitions);
+ }
+ TransitionArray* transitions = TransitionArray::cast(map->raw_transitions());
+ transitions->SetPrototypeTransitions(*proto_transitions);
+}
+
+
+void TransitionArray::EnsureHasFullTransitionArray(Handle<Map> map) {
+ Object* raw_transitions = map->raw_transitions();
+ if (IsFullTransitionArray(raw_transitions)) return;
+ int nof = IsSimpleTransition(raw_transitions) ? 1 : 0;
+ Handle<TransitionArray> result = Allocate(map->GetIsolate(), nof);
+ DisallowHeapAllocation no_gc;
+ // Reload pointer after the allocation that just happened.
+ raw_transitions = map->raw_transitions();
+ int new_nof = IsSimpleTransition(raw_transitions) ? 1 : 0;
+ if (new_nof != nof) {
+ DCHECK(new_nof == 0);
+ result->Shrink(ToKeyIndex(0));
+ result->SetNumberOfTransitions(0);
+ } else if (nof == 1) {
+ Map* target = GetSimpleTransition(raw_transitions);
+ Name* key = GetSimpleTransitionKey(target);
+ result->NoIncrementalWriteBarrierSet(0, key, target);
+ }
+ ReplaceTransitions(map, *result);
+}
+
+
+void TransitionArray::TraverseTransitionTreeInternal(Map* map,
+ TraverseCallback callback,
+ void* data) {
+ Object* raw_transitions = map->raw_transitions();
+ if (IsFullTransitionArray(raw_transitions)) {
+ TransitionArray* transitions = TransitionArray::cast(raw_transitions);
+ if (transitions->HasPrototypeTransitions()) {
+ FixedArray* proto_trans = transitions->GetPrototypeTransitions();
+ for (int i = 0; i < NumberOfPrototypeTransitions(proto_trans); ++i) {
+ int index = TransitionArray::kProtoTransitionHeaderSize + i;
+ TraverseTransitionTreeInternal(Map::cast(proto_trans->get(index)),
+ callback, data);
+ }
+ }
+ for (int i = 0; i < transitions->number_of_transitions(); ++i) {
+ TraverseTransitionTreeInternal(transitions->GetTarget(i), callback, data);
+ }
+ } else if (IsSimpleTransition(raw_transitions)) {
+ TraverseTransitionTreeInternal(GetSimpleTransition(raw_transitions),
+ callback, data);
+ }
+ callback(map, data);
+}
+
+
+#ifdef DEBUG
+void TransitionArray::CheckNewTransitionsAreConsistent(
+ Handle<Map> map, TransitionArray* old_transitions, Object* transitions) {
+ // This function only handles full transition arrays.
+ DCHECK(IsFullTransitionArray(transitions));
+ 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 (TransitionArray::IsSpecialTransition(key)) {
+ new_target_index = new_transitions->SearchSpecial(Symbol::cast(key));
+ } else {
+ PropertyDetails details =
+ TransitionArray::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) {
« no previous file with comments | « src/transitions.h ('k') | src/transitions-inl.h » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698