From ebd3241b05603ddc895ff92aa06ac6a71d7088bc Mon Sep 17 00:00:00 2001 From: "verwaest@chromium.org" Date: Wed, 12 Sep 2012 16:43:57 +0000 Subject: [PATCH] Sharing of descriptor arrays. This CL adds multiple things: Transition arrays do not directly point at their descriptor array anymore, but rather do so via an indirect pointer (a JSGlobalPropertyCell). An ownership bit is added to maps indicating whether it owns its own descriptor array or not. Maps owning a descriptor array can pass on ownership if a transition from that map is generated; but only if the descriptor array stays exactly the same; or if a descriptor is added. Maps that don't have ownership get ownership back if their direct child to which ownership was passed is cleared in ClearNonLiveTransitions. To detect which descriptors in an array are valid, each map knows its own NumberOfOwnDescriptors. Since the descriptors are sorted in order of addition, if we search and find a descriptor with index bigger than this number, it is not valid for the given map. We currently still build up an enumeration cache (although this may disappear). The enumeration cache is always built for the entire descriptor array, even if not all descriptors are owned by the map. Once a descriptor array has an enumeration cache for a given map; this invariant will always be true, even if the descriptor array was extended. The extended array will inherit the enumeration cache from the smaller descriptor array. If a map with more descriptors needs an enumeration cache, it's EnumLength will still be set to invalid, so it will have to recompute the enumeration cache. This new cache will also be valid for smaller maps since they have their own enumlength; and use this to loop over the cache. If the EnumLength is still invalid, but there is already a cache present that is big enough; we just initialize the EnumLength field for the map. When we apply ClearNonLiveTransitions and descriptor ownership is passed back to a parent map, the descriptor array is trimmed in-place and resorted. At the same time, the enumeration cache is trimmed in-place. Only transition arrays contain descriptor arrays. If we transition to a map and pass ownership of the descriptor array along, the child map will not store the descriptor array it owns. Rather its parent will keep the pointer. So for every leaf-map, we find the descriptor array by following the back pointer, reading out the transition array, and fetching the descriptor array from the JSGlobalPropertyCell. If a map has a transition array, we fetch it from there. If a map has undefined as its back-pointer and has no transition array; it is considered to have an empty descriptor array. When we modify properties, we cannot share the descriptor array. To accommodate this, the child map will get its own transition array; even if there are not necessarily any transitions leaving from the child map. This is necessary since it's the only way to store its own descriptor array. Review URL: https://chromiumcodereview.appspot.com/10909007 git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@12492 ce2b1a6d-e550-0410-aec6-3dcde31c8c00 --- src/arm/full-codegen-arm.cc | 34 ++- src/arm/macro-assembler-arm.cc | 21 +- src/arm/macro-assembler-arm.h | 9 + src/bootstrapper.cc | 5 +- src/handles.cc | 48 +++- src/handles.h | 1 + src/heap.cc | 9 +- src/heap.h | 26 +- src/ia32/full-codegen-ia32.cc | 24 +- src/ia32/macro-assembler-ia32.cc | 21 +- src/ia32/macro-assembler-ia32.h | 9 +- src/mark-compact.cc | 8 +- src/objects-debug.cc | 8 +- src/objects-inl.h | 133 ++++++--- src/objects.cc | 441 +++++++++++++++++++++++------- src/objects.h | 72 +++-- src/profile-generator.cc | 35 ++- src/property.h | 3 +- src/runtime.cc | 2 +- src/string-stream.cc | 5 +- src/transitions-inl.h | 26 +- src/transitions.cc | 23 +- src/transitions.h | 24 +- src/x64/full-codegen-x64.cc | 23 +- src/x64/macro-assembler-x64.cc | 21 +- src/x64/macro-assembler-x64.h | 10 +- test/cctest/test-heap-profiler.cc | 19 +- 27 files changed, 780 insertions(+), 280 deletions(-) diff --git a/src/arm/full-codegen-arm.cc b/src/arm/full-codegen-arm.cc index b2f629b26..de09516cc 100644 --- a/src/arm/full-codegen-arm.cc +++ b/src/arm/full-codegen-arm.cc @@ -2729,26 +2729,31 @@ void FullCodeGenerator::EmitIsStringWrapperSafeForDefaultValueOf( __ b(eq, if_false); // Look for valueOf symbol in the descriptor array, and indicate false if - // found. The type is not checked, so if it is a transition it is a false - // negative. - __ LoadInstanceDescriptors(r1, r4, r3); - __ ldr(r3, FieldMemOperand(r4, FixedArray::kLengthOffset)); - // r4: descriptor array - // r3: length of descriptor array - // Calculate the end of the descriptor array. + // found. Since we omit an enumeration index check, if it is added via a + // transition that shares its descriptor array, this is a false positive. + Label entry, loop, done; + + // Skip loop if no descriptors are valid. + __ NumberOfOwnDescriptors(r3, r1); + __ cmp(r3, Operand(0)); + __ b(eq, &done); + + __ LoadInstanceDescriptors(r1, r4, r2); + // r4: descriptor array. + // r3: valid entries in the descriptor array. STATIC_ASSERT(kSmiTag == 0); STATIC_ASSERT(kSmiTagSize == 1); STATIC_ASSERT(kPointerSize == 4); - __ add(r2, r4, Operand(FixedArray::kHeaderSize - kHeapObjectTag)); + __ mov(ip, Operand(DescriptorArray::kDescriptorSize)); + __ mul(r3, r3, ip); + // Calculate location of the first key name. + __ add(r4, r4, Operand(DescriptorArray::kFirstOffset - kHeapObjectTag)); + // Calculate the end of the descriptor array. + __ mov(r2, r4); __ add(r2, r2, Operand(r3, LSL, kPointerSizeLog2 - kSmiTagSize)); - // Calculate location of the first key name. - __ add(r4, - r4, - Operand(DescriptorArray::kFirstOffset - kHeapObjectTag)); // Loop through all the keys in the descriptor array. If one of these is the // symbol valueOf the result is false. - Label entry, loop; // The use of ip to store the valueOf symbol asumes that it is not otherwise // used in the loop below. __ mov(ip, Operand(FACTORY->value_of_symbol())); @@ -2762,7 +2767,8 @@ void FullCodeGenerator::EmitIsStringWrapperSafeForDefaultValueOf( __ cmp(r4, Operand(r2)); __ b(ne, &loop); - // If a valueOf property is not found on the object check that it's + __ bind(&done); + // If a valueOf property is not found on the object check that its // prototype is the un-modified String prototype. If not result is false. __ ldr(r2, FieldMemOperand(r1, Map::kPrototypeOffset)); __ JumpIfSmi(r2, if_false); diff --git a/src/arm/macro-assembler-arm.cc b/src/arm/macro-assembler-arm.cc index 2a677be52..d26631026 100644 --- a/src/arm/macro-assembler-arm.cc +++ b/src/arm/macro-assembler-arm.cc @@ -3703,20 +3703,37 @@ void MacroAssembler::LoadInstanceDescriptors(Register map, Register temp = descriptors; ldr(temp, FieldMemOperand(map, Map::kTransitionsOrBackPointerOffset)); - Label ok, fail; + Label ok, fail, load_from_back_pointer; CheckMap(temp, scratch, isolate()->factory()->fixed_array_map(), &fail, DONT_DO_SMI_CHECK); - ldr(descriptors, FieldMemOperand(temp, TransitionArray::kDescriptorsOffset)); + ldr(temp, FieldMemOperand(temp, TransitionArray::kDescriptorsPointerOffset)); + ldr(descriptors, FieldMemOperand(temp, JSGlobalPropertyCell::kValueOffset)); jmp(&ok); + bind(&fail); + CompareRoot(temp, Heap::kUndefinedValueRootIndex); + b(ne, &load_from_back_pointer); mov(descriptors, Operand(FACTORY->empty_descriptor_array())); + jmp(&ok); + + bind(&load_from_back_pointer); + ldr(temp, FieldMemOperand(temp, Map::kTransitionsOrBackPointerOffset)); + ldr(temp, FieldMemOperand(temp, TransitionArray::kDescriptorsPointerOffset)); + ldr(descriptors, FieldMemOperand(temp, JSGlobalPropertyCell::kValueOffset)); + bind(&ok); } +void MacroAssembler::NumberOfOwnDescriptors(Register dst, Register map) { + ldr(dst, FieldMemOperand(map, Map::kBitFieldOffset)); + DecodeField(dst); +} + + void MacroAssembler::EnumLength(Register dst, Register map) { STATIC_ASSERT(Map::EnumLengthBits::kShift == 0); ldr(dst, FieldMemOperand(map, Map::kBitField3Offset)); diff --git a/src/arm/macro-assembler-arm.h b/src/arm/macro-assembler-arm.h index 8eb97125e..7d127b5e8 100644 --- a/src/arm/macro-assembler-arm.h +++ b/src/arm/macro-assembler-arm.h @@ -1273,6 +1273,15 @@ class MacroAssembler: public Assembler { Register descriptors, Register scratch); void EnumLength(Register dst, Register map); + void NumberOfOwnDescriptors(Register dst, Register map); + + template + void DecodeField(Register reg) { + static const int shift = Field::kShift; + static const int mask = (Field::kMask >> shift) << kSmiTagSize; + mov(reg, Operand(reg, LSR, shift)); + and_(reg, reg, Operand(mask)); + } // Activation support. void EnterFrame(StackFrame::Type type); diff --git a/src/bootstrapper.cc b/src/bootstrapper.cc index 992659edc..9de105859 100644 --- a/src/bootstrapper.cc +++ b/src/bootstrapper.cc @@ -637,7 +637,7 @@ static void SetAccessors(Handle map, Handle name, Handle func) { DescriptorArray* descs = map->instance_descriptors(); - int number = descs->Search(*name); + int number = descs->SearchWithCache(*name, *map); AccessorPair* accessors = AccessorPair::cast(descs->GetValue(number)); accessors->set_getter(*func); accessors->set_setter(*func); @@ -1774,7 +1774,8 @@ bool Genesis::InstallNatives() { Handle array_descriptors( array_function->initial_map()->instance_descriptors()); String* length = heap()->length_symbol(); - int old = array_descriptors->SearchWithCache(length); + int old = array_descriptors->SearchWithCache( + length, array_function->initial_map()); ASSERT(old != DescriptorArray::kNotFound); CallbacksDescriptor desc(length, array_descriptors->GetValue(old), diff --git a/src/handles.cc b/src/handles.cc index 6aa7a6a87..7999a1061 100644 --- a/src/handles.cc +++ b/src/handles.cc @@ -705,24 +705,46 @@ Handle GetKeysFor(Handle object, bool* threw) { } +Handle ReduceFixedArrayTo(Handle array, int length) { + ASSERT(array->length() >= length); + if (array->length() == length) return array; + + Handle new_array = + array->GetIsolate()->factory()->NewFixedArray(length); + for (int i = 0; i < length; ++i) new_array->set(i, array->get(i)); + return new_array; +} + + Handle GetEnumPropertyKeys(Handle object, bool cache_result) { Isolate* isolate = object->GetIsolate(); if (object->HasFastProperties()) { if (object->map()->instance_descriptors()->HasEnumCache()) { int own_property_count = object->map()->EnumLength(); - - // Mark that we have an enum cache if we are allowed to cache it. - if (cache_result && own_property_count == Map::kInvalidEnumCache) { - int num_enum = object->map()->NumberOfDescribedProperties(DONT_ENUM); - object->map()->SetEnumLength(num_enum); + // If we have an enum cache, but the enum length of the given map is set + // to kInvalidEnumCache, this means that the map itself has never used the + // present enum cache. The first step to using the cache is to set the + // enum length of the map by counting the number of own descriptors that + // are not DONT_ENUM. + if (own_property_count == Map::kInvalidEnumCache) { + own_property_count = object->map()->NumberOfDescribedProperties( + OWN_DESCRIPTORS, DONT_ENUM); + + if (cache_result) object->map()->SetEnumLength(own_property_count); } DescriptorArray* desc = object->map()->instance_descriptors(); Handle keys(FixedArray::cast(desc->GetEnumCache()), isolate); - isolate->counters()->enum_cache_hits()->Increment(); - return keys; + // In case the number of properties required in the enum are actually + // present, we can reuse the enum cache. Otherwise, this means that the + // enum cache was generated for a previous (smaller) version of the + // Descriptor Array. In that case we regenerate the enum cache. + if (own_property_count <= keys->length()) { + isolate->counters()->enum_cache_hits()->Increment(); + return ReduceFixedArrayTo(keys, own_property_count); + } } Handle map(object->map()); @@ -734,8 +756,7 @@ Handle GetEnumPropertyKeys(Handle object, } isolate->counters()->enum_cache_misses()->Increment(); - - int num_enum = map->NumberOfDescribedProperties(DONT_ENUM); + int num_enum = map->NumberOfDescribedProperties(ALL_DESCRIPTORS, DONT_ENUM); Handle storage = isolate->factory()->NewFixedArray(num_enum); Handle indices = isolate->factory()->NewFixedArray(num_enum); @@ -743,10 +764,14 @@ Handle GetEnumPropertyKeys(Handle object, Handle descs = Handle(object->map()->instance_descriptors(), isolate); + int real_size = map->NumberOfOwnDescriptors(); + int enum_size = 0; int index = 0; + for (int i = 0; i < descs->number_of_descriptors(); i++) { PropertyDetails details = descs->GetDetails(i); if (!details.IsDontEnum()) { + if (i < real_size) ++enum_size; storage->set(index, descs->GetKey(i)); if (!indices.is_null()) { if (details.type() != FIELD) { @@ -773,9 +798,10 @@ Handle GetEnumPropertyKeys(Handle object, indices.is_null() ? Object::cast(Smi::FromInt(0)) : Object::cast(*indices)); if (cache_result) { - object->map()->SetEnumLength(index); + object->map()->SetEnumLength(enum_size); } - return storage; + + return ReduceFixedArrayTo(storage, enum_size); } else { Handle dictionary(object->property_dictionary()); diff --git a/src/handles.h b/src/handles.h index b35693e95..a1d88c2f8 100644 --- a/src/handles.h +++ b/src/handles.h @@ -276,6 +276,7 @@ Handle GetKeysInFixedArrayFor(Handle object, KeyCollectionType type, bool* threw); Handle GetKeysFor(Handle object, bool* threw); +Handle ReduceFixedArrayTo(Handle array, int length); Handle GetEnumPropertyKeys(Handle object, bool cache_result); diff --git a/src/heap.cc b/src/heap.cc index 6d5162001..73b565a98 100644 --- a/src/heap.cc +++ b/src/heap.cc @@ -2065,7 +2065,9 @@ MaybeObject* Heap::AllocatePartialMap(InstanceType instance_type, reinterpret_cast(result)->set_unused_property_fields(0); reinterpret_cast(result)->set_bit_field(0); reinterpret_cast(result)->set_bit_field2(0); - reinterpret_cast(result)->set_bit_field3(0); + int bit_field3 = Map::EnumLengthBits::encode(Map::kInvalidEnumCache) | + Map::OwnsDescriptors::encode(true); + reinterpret_cast(result)->set_bit_field3(bit_field3); return result; } @@ -2092,7 +2094,8 @@ MaybeObject* Heap::AllocateMap(InstanceType instance_type, map->set_unused_property_fields(0); map->set_bit_field(0); map->set_bit_field2(1 << Map::kIsExtensible); - int bit_field3 = Map::EnumLengthBits::encode(Map::kInvalidEnumCache); + int bit_field3 = Map::EnumLengthBits::encode(Map::kInvalidEnumCache) | + Map::OwnsDescriptors::encode(true); map->set_bit_field3(bit_field3); map->set_elements_kind(elements_kind); @@ -7126,7 +7129,7 @@ void KeyedLookupCache::Clear() { void DescriptorLookupCache::Clear() { - for (int index = 0; index < kLength; index++) keys_[index].array = NULL; + for (int index = 0; index < kLength; index++) keys_[index].source = NULL; } diff --git a/src/heap.h b/src/heap.h index cb167d30a..2ee1a2c47 100644 --- a/src/heap.h +++ b/src/heap.h @@ -2374,7 +2374,7 @@ class KeyedLookupCache { }; -// Cache for mapping (array, property name) into descriptor index. +// Cache for mapping (map, property name) into descriptor index. // The cache contains both positive and negative results. // Descriptor index equals kNotFound means the property is absent. // Cleared at startup and prior to any gc. @@ -2382,21 +2382,21 @@ class DescriptorLookupCache { public: // Lookup descriptor index for (map, name). // If absent, kAbsent is returned. - int Lookup(DescriptorArray* array, String* name) { + int Lookup(Map* source, String* name) { if (!StringShape(name).IsSymbol()) return kAbsent; - int index = Hash(array, name); + int index = Hash(source, name); Key& key = keys_[index]; - if ((key.array == array) && (key.name == name)) return results_[index]; + if ((key.source == source) && (key.name == name)) return results_[index]; return kAbsent; } // Update an element in the cache. - void Update(DescriptorArray* array, String* name, int result) { + void Update(Map* source, String* name, int result) { ASSERT(result != kAbsent); if (StringShape(name).IsSymbol()) { - int index = Hash(array, name); + int index = Hash(source, name); Key& key = keys_[index]; - key.array = array; + key.source = source; key.name = name; results_[index] = result; } @@ -2410,26 +2410,26 @@ class DescriptorLookupCache { private: DescriptorLookupCache() { for (int i = 0; i < kLength; ++i) { - keys_[i].array = NULL; + keys_[i].source = NULL; keys_[i].name = NULL; results_[i] = kAbsent; } } - static int Hash(DescriptorArray* array, String* name) { + static int Hash(Object* source, String* name) { // Uses only lower 32 bits if pointers are larger. - uint32_t array_hash = - static_cast(reinterpret_cast(array)) + uint32_t source_hash = + static_cast(reinterpret_cast(source)) >> kPointerSizeLog2; uint32_t name_hash = static_cast(reinterpret_cast(name)) >> kPointerSizeLog2; - return (array_hash ^ name_hash) % kLength; + return (source_hash ^ name_hash) % kLength; } static const int kLength = 64; struct Key { - DescriptorArray* array; + Map* source; String* name; }; diff --git a/src/ia32/full-codegen-ia32.cc b/src/ia32/full-codegen-ia32.cc index 7fb7cc321..a058701aa 100644 --- a/src/ia32/full-codegen-ia32.cc +++ b/src/ia32/full-codegen-ia32.cc @@ -2669,22 +2669,28 @@ void FullCodeGenerator::EmitIsStringWrapperSafeForDefaultValueOf( __ j(equal, if_false); // Look for valueOf symbol in the descriptor array, and indicate false if - // found. The type is not checked, so if it is a transition it is a false - // negative. + // found. Since we omit an enumeration index check, if it is added via a + // transition that shares its descriptor array, this is a false positive. + Label entry, loop, done; + + // Skip loop if no descriptors are valid. + __ NumberOfOwnDescriptors(ecx, ebx); + __ cmp(ecx, 0); + __ j(equal, &done); + __ LoadInstanceDescriptors(ebx, ebx); - __ mov(ecx, FieldOperand(ebx, FixedArray::kLengthOffset)); - // ebx: descriptor array - // ecx: length of descriptor array + // ebx: descriptor array. + // ecx: valid entries in the descriptor array. // Calculate the end of the descriptor array. STATIC_ASSERT(kSmiTag == 0); STATIC_ASSERT(kSmiTagSize == 1); STATIC_ASSERT(kPointerSize == 4); - __ lea(ecx, Operand(ebx, ecx, times_2, FixedArray::kHeaderSize)); + __ imul(ecx, ecx, DescriptorArray::kDescriptorSize); + __ lea(ecx, Operand(ebx, ecx, times_2, DescriptorArray::kFirstOffset)); // Calculate location of the first key name. __ add(ebx, Immediate(DescriptorArray::kFirstOffset)); // Loop through all the keys in the descriptor array. If one of these is the // symbol valueOf the result is false. - Label entry, loop; __ jmp(&entry); __ bind(&loop); __ mov(edx, FieldOperand(ebx, 0)); @@ -2695,10 +2701,12 @@ void FullCodeGenerator::EmitIsStringWrapperSafeForDefaultValueOf( __ cmp(ebx, ecx); __ j(not_equal, &loop); + __ bind(&done); + // Reload map as register ebx was used as temporary above. __ mov(ebx, FieldOperand(eax, HeapObject::kMapOffset)); - // If a valueOf property is not found on the object check that it's + // If a valueOf property is not found on the object check that its // prototype is the un-modified String prototype. If not result is false. __ mov(ecx, FieldOperand(ebx, Map::kPrototypeOffset)); __ JumpIfSmi(ecx, if_false); diff --git a/src/ia32/macro-assembler-ia32.cc b/src/ia32/macro-assembler-ia32.cc index 9c5f31e2c..c71fa005c 100644 --- a/src/ia32/macro-assembler-ia32.cc +++ b/src/ia32/macro-assembler-ia32.cc @@ -2576,19 +2576,36 @@ void MacroAssembler::LoadInstanceDescriptors(Register map, Register temp = descriptors; mov(temp, FieldOperand(map, Map::kTransitionsOrBackPointerOffset)); - Label ok, fail; + Label ok, fail, load_from_back_pointer; CheckMap(temp, isolate()->factory()->fixed_array_map(), &fail, DONT_DO_SMI_CHECK); - mov(descriptors, FieldOperand(temp, TransitionArray::kDescriptorsOffset)); + mov(temp, FieldOperand(temp, TransitionArray::kDescriptorsPointerOffset)); + mov(descriptors, FieldOperand(temp, JSGlobalPropertyCell::kValueOffset)); jmp(&ok); + bind(&fail); + cmp(temp, isolate()->factory()->undefined_value()); + j(not_equal, &load_from_back_pointer, Label::kNear); mov(descriptors, isolate()->factory()->empty_descriptor_array()); + jmp(&ok); + + bind(&load_from_back_pointer); + mov(temp, FieldOperand(temp, Map::kTransitionsOrBackPointerOffset)); + mov(temp, FieldOperand(temp, TransitionArray::kDescriptorsPointerOffset)); + mov(descriptors, FieldOperand(temp, JSGlobalPropertyCell::kValueOffset)); + bind(&ok); } +void MacroAssembler::NumberOfOwnDescriptors(Register dst, Register map) { + mov(dst, FieldOperand(map, Map::kBitField3Offset)); + DecodeField(dst); +} + + void MacroAssembler::LoadPowerOf2(XMMRegister dst, Register scratch, int power) { diff --git a/src/ia32/macro-assembler-ia32.h b/src/ia32/macro-assembler-ia32.h index 7d475e7d7..909000ec0 100644 --- a/src/ia32/macro-assembler-ia32.h +++ b/src/ia32/macro-assembler-ia32.h @@ -493,13 +493,14 @@ class MacroAssembler: public Assembler { void LoadInstanceDescriptors(Register map, Register descriptors); void EnumLength(Register dst, Register map); + void NumberOfOwnDescriptors(Register dst, Register map); template void DecodeField(Register reg) { - static const int full_shift = Field::kShift + kSmiTagSize; - static const int low_mask = Field::kMask >> Field::kShift; - sar(reg, full_shift); - and_(reg, Immediate(low_mask)); + static const int shift = Field::kShift; + static const int mask = (Field::kMask >> Field::kShift) << kSmiTagSize; + sar(reg, shift); + and_(reg, Immediate(mask)); } void LoadPowerOf2(XMMRegister dst, Register scratch, int power); diff --git a/src/mark-compact.cc b/src/mark-compact.cc index a9a90bdf6..c83548fe2 100644 --- a/src/mark-compact.cc +++ b/src/mark-compact.cc @@ -1942,10 +1942,10 @@ void Marker::MarkTransitionArray(TransitionArray* transitions) { if (!base_marker()->MarkObjectWithoutPush(transitions)) return; Object** transitions_start = transitions->data_start(); - DescriptorArray* descriptors = transitions->descriptors(); - base_marker()->MarkObjectAndPush(descriptors); - mark_compact_collector()->RecordSlot( - transitions_start, transitions->GetDescriptorsSlot(), descriptors); + // We don't have to record the descriptors_pointer slot since the cell space + // is not compacted. + JSGlobalPropertyCell* descriptors_cell = transitions->descriptors_pointer(); + base_marker()->MarkObjectAndPush(descriptors_cell); if (transitions->HasPrototypeTransitions()) { // Mark prototype transitions array but don't push it into marking stack. diff --git a/src/objects-debug.cc b/src/objects-debug.cc index 9761ed160..d5691611b 100644 --- a/src/objects-debug.cc +++ b/src/objects-debug.cc @@ -901,10 +901,11 @@ void JSObject::SpillInformation::Print() { } -bool DescriptorArray::IsSortedNoDuplicates() { +bool DescriptorArray::IsSortedNoDuplicates(int valid_entries) { + if (valid_entries == -1) valid_entries = number_of_descriptors(); String* current_key = NULL; uint32_t current = 0; - for (int i = 0; i < number_of_descriptors(); i++) { + for (int i = 0; i < valid_entries; i++) { String* key = GetSortedKey(i); if (key == current_key) { PrintDescriptors(); @@ -922,7 +923,8 @@ bool DescriptorArray::IsSortedNoDuplicates() { } -bool TransitionArray::IsSortedNoDuplicates() { +bool TransitionArray::IsSortedNoDuplicates(int valid_entries) { + ASSERT(valid_entries == -1); String* current_key = NULL; uint32_t current = 0; for (int i = 0; i < number_of_transitions(); i++) { diff --git a/src/objects-inl.h b/src/objects-inl.h index 391358386..65a96612b 100644 --- a/src/objects-inl.h +++ b/src/objects-inl.h @@ -1940,31 +1940,45 @@ int BinarySearch(T* array, String* name, int low, int high) { // Perform a linear search in this fixed array. len is the number of entry // indices that are valid. -template -int LinearSearch(T* array, String* name, int len) { +template +int LinearSearch(T* array, String* name, int len, int valid_entries) { uint32_t hash = name->Hash(); - for (int number = 0; number < len; number++) { - int sorted_index = array->GetSortedKeyIndex(number); - String* entry = array->GetKey(sorted_index); - uint32_t current_hash = entry->Hash(); - if (current_hash > hash) break; - if (current_hash == hash && entry->Equals(name)) return sorted_index; + if (search_mode == ALL_ENTRIES) { + for (int number = 0; number < len; number++) { + int sorted_index = array->GetSortedKeyIndex(number); + String* entry = array->GetKey(sorted_index); + uint32_t current_hash = entry->Hash(); + if (current_hash > hash) break; + if (current_hash == hash && entry->Equals(name)) return sorted_index; + } + } else { + ASSERT(len >= valid_entries); + for (int number = 0; number < valid_entries; number++) { + String* entry = array->GetKey(number); + uint32_t current_hash = entry->Hash(); + if (current_hash == hash && entry->Equals(name)) return number; + } } return T::kNotFound; } -template -int Search(T* array, String* name) { - SLOW_ASSERT(array->IsSortedNoDuplicates()); +template +int Search(T* array, String* name, int valid_entries) { + if (search_mode == VALID_ENTRIES) { + SLOW_ASSERT(array->IsSortedNoDuplicates(valid_entries)); + } else { + SLOW_ASSERT(array->IsSortedNoDuplicates()); + } int nof = array->number_of_entries(); if (nof == 0) return T::kNotFound; // Fast case: do linear search for small arrays. const int kMaxElementsForLinearSearch = 8; - if (nof < kMaxElementsForLinearSearch) { - return LinearSearch(array, name, nof); + if (search_mode == VALID_ENTRIES || + (search_mode == ALL_ENTRIES && nof < kMaxElementsForLinearSearch)) { + return LinearSearch(array, name, nof, valid_entries); } // Slow case: perform binary search. @@ -1972,20 +1986,21 @@ int Search(T* array, String* name) { } -int DescriptorArray::Search(String* name) { - return internal::Search(this, name); +int DescriptorArray::Search(String* name, int valid_descriptors) { + return internal::Search(this, name, valid_descriptors); } -int DescriptorArray::SearchWithCache(String* name) { - if (number_of_descriptors() == 0) return kNotFound; +int DescriptorArray::SearchWithCache(String* name, Map* map) { + int number_of_own_descriptors = map->NumberOfOwnDescriptors(); + if (number_of_own_descriptors == 0) return kNotFound; DescriptorLookupCache* cache = GetIsolate()->descriptor_lookup_cache(); - int number = cache->Lookup(this, name); + int number = cache->Lookup(map, name); if (number == DescriptorLookupCache::kAbsent) { - number = Search(name); - cache->Update(this, name, number); + number = Search(name, number_of_own_descriptors); + cache->Update(map, name, number); } return number; @@ -1996,7 +2011,7 @@ void Map::LookupDescriptor(JSObject* holder, String* name, LookupResult* result) { DescriptorArray* descriptors = this->instance_descriptors(); - int number = descriptors->SearchWithCache(name); + int number = descriptors->SearchWithCache(name, this); if (number == DescriptorArray::kNotFound) return result->NotFound(); result->DescriptorResult(holder, descriptors->GetDetails(number), number); } @@ -2040,10 +2055,9 @@ String* DescriptorArray::GetSortedKey(int descriptor_number) { } -void DescriptorArray::SetSortedKey(int pointer, int descriptor_number) { - int details_index = ToDetailsIndex(pointer); - PropertyDetails details = PropertyDetails(Smi::cast(get(details_index))); - set_unchecked(details_index, details.set_pointer(descriptor_number).AsSmi()); +void DescriptorArray::SetSortedKey(int descriptor_index, int pointer) { + PropertyDetails details = GetDetails(descriptor_index); + set(ToDetailsIndex(descriptor_index), details.set_pointer(pointer).AsSmi()); } @@ -2127,21 +2141,22 @@ void DescriptorArray::Set(int descriptor_number, void DescriptorArray::Append(Descriptor* desc, const WhitenessWitness& witness, int number_of_set_descriptors) { - int enumeration_index = number_of_set_descriptors + 1; + int descriptor_number = number_of_set_descriptors; + int enumeration_index = descriptor_number + 1; desc->SetEnumerationIndex(enumeration_index); - Set(number_of_set_descriptors, desc, witness); + Set(descriptor_number, desc, witness); uint32_t hash = desc->GetKey()->Hash(); int insertion; - for (insertion = number_of_set_descriptors; insertion > 0; --insertion) { + for (insertion = descriptor_number; insertion > 0; --insertion) { String* key = GetSortedKey(insertion - 1); if (key->Hash() <= hash) break; SetSortedKey(insertion, GetSortedKeyIndex(insertion - 1)); } - SetSortedKey(insertion, number_of_set_descriptors); + SetSortedKey(insertion, descriptor_number); } @@ -3040,6 +3055,16 @@ Code::Flags Code::flags() { } +void Map::set_owns_descriptors(bool is_shared) { + set_bit_field3(OwnsDescriptors::update(bit_field3(), is_shared)); +} + + +bool Map::owns_descriptors() { + return OwnsDescriptors::decode(bit_field3()); +} + + void Code::set_flags(Code::Flags flags) { STATIC_ASSERT(Code::NUMBER_OF_KINDS <= KindField::kMax + 1); // Make sure that all call stubs have an arguments count. @@ -3475,9 +3500,17 @@ void Map::set_prototype(Object* value, WriteBarrierMode mode) { } +JSGlobalPropertyCell* Map::descriptors_pointer() { + ASSERT(HasTransitionArray()); + return transitions()->descriptors_pointer(); +} + + DescriptorArray* Map::instance_descriptors() { - if (!HasTransitionArray()) return GetHeap()->empty_descriptor_array(); - return transitions()->descriptors(); + if (HasTransitionArray()) return transitions()->descriptors(); + Object* back_pointer = GetBackPointer(); + if (!back_pointer->IsMap()) return GetHeap()->empty_descriptor_array(); + return Map::cast(back_pointer)->instance_descriptors(); } @@ -3487,29 +3520,31 @@ static MaybeObject* EnsureHasTransitionArray(Map* map) { if (map->HasTransitionArray()) return map; TransitionArray* transitions; - MaybeObject* maybe_transitions = TransitionArray::Allocate(0); + JSGlobalPropertyCell* pointer = map->RetrieveDescriptorsPointer(); + MaybeObject* maybe_transitions = TransitionArray::Allocate(0, pointer); if (!maybe_transitions->To(&transitions)) return maybe_transitions; + + transitions->set_back_pointer_storage(map->GetBackPointer()); map->set_transitions(transitions); return transitions; } -MaybeObject* Map::SetDescriptors(DescriptorArray* value, - WriteBarrierMode mode) { +MaybeObject* Map::SetDescriptors(DescriptorArray* value) { ASSERT(!is_shared()); MaybeObject* maybe_failure = EnsureHasTransitionArray(this); if (maybe_failure->IsFailure()) return maybe_failure; - transitions()->set_descriptors(value, mode); + ASSERT(NumberOfOwnDescriptors() <= value->number_of_descriptors()); + transitions()->set_descriptors(value); return this; } MaybeObject* Map::InitializeDescriptors(DescriptorArray* descriptors) { -#ifdef DEBUG int len = descriptors->number_of_descriptors(); +#ifdef DEBUG ASSERT(len <= DescriptorArray::kMaxNumberOfDescriptors); - SLOW_ASSERT(descriptors->IsSortedNoDuplicates()); bool used_indices[DescriptorArray::kMaxNumberOfDescriptors]; for (int i = 0; i < len; ++i) used_indices[i] = false; @@ -3528,8 +3563,7 @@ MaybeObject* Map::InitializeDescriptors(DescriptorArray* descriptors) { MaybeObject* maybe_failure = SetDescriptors(descriptors); if (maybe_failure->IsFailure()) return maybe_failure; - SetNumberOfOwnDescriptors(descriptors->number_of_descriptors()); - + SetNumberOfOwnDescriptors(len); return this; } @@ -3598,9 +3632,21 @@ bool Map::CanHaveMoreTransitions() { } +JSGlobalPropertyCell* Map::RetrieveDescriptorsPointer() { + if (!owns_descriptors()) return NULL; + Object* back_pointer = GetBackPointer(); + if (back_pointer->IsUndefined()) return NULL; + Map* map = Map::cast(back_pointer); + ASSERT(map->HasTransitionArray()); + return map->transitions()->descriptors_pointer(); +} + + MaybeObject* Map::AddTransition(String* key, Map* target) { if (HasTransitionArray()) return transitions()->CopyInsert(key, target); - return TransitionArray::NewWith(key, target); + JSGlobalPropertyCell* descriptors_pointer = RetrieveDescriptorsPointer(); + return TransitionArray::NewWith( + key, target, descriptors_pointer, GetBackPointer()); } @@ -3609,6 +3655,11 @@ void Map::SetTransition(int transition_index, Map* target) { } +Map* Map::GetTransition(int transition_index) { + return transitions()->GetTarget(transition_index); +} + + MaybeObject* Map::set_elements_transition_map(Map* transitioned_map) { MaybeObject* allow_elements = EnsureHasTransitionArray(this); if (allow_elements->IsFailure()) return allow_elements; @@ -3654,8 +3705,6 @@ TransitionArray* Map::transitions() { void Map::set_transitions(TransitionArray* transition_array, WriteBarrierMode mode) { - transition_array->set_descriptors(instance_descriptors()); - transition_array->set_back_pointer_storage(GetBackPointer()); #ifdef DEBUG if (HasTransitionArray()) { ASSERT(transitions() != transition_array); diff --git a/src/objects.cc b/src/objects.cc index 57882a4d2..fe0683e04 100644 --- a/src/objects.cc +++ b/src/objects.cc @@ -1532,8 +1532,9 @@ MaybeObject* JSObject::AddFastProperty(String* name, PropertyAttributes attributes, StoreFromKeyed store_mode) { ASSERT(!IsJSGlobalProxy()); - ASSERT(map()->instance_descriptors()->Search(name) == - DescriptorArray::kNotFound); + ASSERT(DescriptorArray::kNotFound == + map()->instance_descriptors()->Search( + name, map()->NumberOfOwnDescriptors())); // Normalize the object if the name is an actual string (not the // hidden symbols) and is not a real identifier. @@ -1753,8 +1754,33 @@ MaybeObject* JSObject::ConvertTransitionToMapTransition( Object* new_value, PropertyAttributes attributes) { Map* old_map = map(); + Map* old_target = old_map->GetTransition(transition_index); Object* result; + // To sever a transition to a map with which the descriptors are shared, the + // larger map (more descriptors) needs to store its own descriptors array. + // Both sides of the severed chain need to have their own descriptors pointer + // to store distinct descriptor arrays. + + // If the old_target did not yet store its own descriptors, the new + // descriptors pointer is created for the old_target by temporarily clearing + // the back pointer and setting its descriptor array. The ownership of the + // descriptor array is returned to the smaller maps by installing a reduced + // copy of the descriptor array in the old_map. + + // This phase is executed before creating the new map since it requires + // allocation that may fail. + if (!old_target->StoresOwnDescriptors()) { + DescriptorArray* old_descriptors = old_map->instance_descriptors(); + + old_target->SetBackPointer(GetHeap()->undefined_value()); + MaybeObject* maybe_failure = old_target->SetDescriptors(old_descriptors); + if (maybe_failure->IsFailure()) return maybe_failure; + old_target->SetBackPointer(old_map); + + old_map->set_owns_descriptors(true); + } + MaybeObject* maybe_result = ConvertDescriptorToField(name, new_value, attributes); if (!maybe_result->To(&result)) return maybe_result; @@ -1763,13 +1789,46 @@ MaybeObject* JSObject::ConvertTransitionToMapTransition( // This method should only be used to convert existing transitions. Objects // with the map of "new Object()" cannot have transitions in the first place. - ASSERT(map() != GetIsolate()->empty_object_map()); + Map* new_map = map(); + ASSERT(new_map != GetIsolate()->empty_object_map()); // TODO(verwaest): From here on we lose existing map transitions, causing // invalid back pointers. This will change once we can store multiple // transitions with the same key. - old_map->SetTransition(transition_index, map()); - map()->SetBackPointer(old_map); + + if (old_map->owns_descriptors()) { + // If the old map owns its own descriptors, transfer ownership to the + // new_map and install its descriptors in the old_map. Since the old_map + // stores the descriptors for the new_map, remove the transition array of + // the new_map that is only in place to store the descriptors. + old_map->transitions()->set_descriptors(new_map->instance_descriptors()); + new_map->ClearTransitions(GetHeap()); + old_map->set_owns_descriptors(false); + } else if (old_target->instance_descriptors() == + old_map->instance_descriptors()) { + // Since the conversion above generated a new fast map with an additional + // property which can be shared as well, install this descriptor pointer + // along the entire chain of smaller maps; and remove the transition array + // that is only in place to hold the descriptor array in the new map. + Map* map; + JSGlobalPropertyCell* new_pointer = + new_map->transitions()->descriptors_pointer(); + JSGlobalPropertyCell* old_pointer = + old_map->transitions()->descriptors_pointer(); + for (Object* current = old_map; + !current->IsUndefined(); + current = map->GetBackPointer()) { + map = Map::cast(current); + if (!map->HasTransitionArray()) break; + TransitionArray* transitions = map->transitions(); + if (transitions->descriptors_pointer() != old_pointer) break; + transitions->set_descriptors_pointer(new_pointer); + } + new_map->ClearTransitions(GetHeap()); + } + + old_map->SetTransition(transition_index, new_map); + new_map->SetBackPointer(old_map); return result; } @@ -2145,6 +2204,7 @@ void Map::CopyAppendCallbackDescriptors(Handle map, v8::NeanderArray callbacks(descriptors); int nof_callbacks = callbacks.length(); int descriptor_count = array->number_of_descriptors(); + ASSERT(descriptor_count == map->NumberOfOwnDescriptors()); // Ensure the keys are symbols before writing them into the instance // descriptor. Since it may cause a GC, it has to be done before we @@ -2164,10 +2224,8 @@ void Map::CopyAppendCallbackDescriptors(Handle map, DescriptorArray::WhitenessWitness witness(*result); // Copy the descriptors from the array. - if (0 < descriptor_count) { - for (int i = 0; i < descriptor_count; i++) { - result->CopyFrom(i, *array, i, witness); - } + for (int i = 0; i < descriptor_count; i++) { + result->CopyFrom(i, *array, i, witness); } // After this point the GC is not allowed to run anymore until the map is in a @@ -2178,26 +2236,28 @@ void Map::CopyAppendCallbackDescriptors(Handle map, // Fill in new callback descriptors. Process the callbacks from // back to front so that the last callback with a given name takes // precedence over previously added callbacks with that name. + int nof = descriptor_count; for (int i = nof_callbacks - 1; i >= 0; i--) { AccessorInfo* entry = AccessorInfo::cast(callbacks.get(i)); String* key = String::cast(entry->name()); // Check if a descriptor with this name already exists before writing. - if (LinearSearch(*result, key, map->NumberOfOwnDescriptors()) == - DescriptorArray::kNotFound) { + if (result->Search(key, nof) == DescriptorArray::kNotFound) { CallbacksDescriptor desc(key, entry, entry->property_attributes()); map->AppendDescriptor(&desc, witness); + nof += 1; } } - int new_number_of_descriptors = map->NumberOfOwnDescriptors(); + ASSERT(nof == map->NumberOfOwnDescriptors()); + // Reinstall the original descriptor array if no new elements were added. - if (new_number_of_descriptors == descriptor_count) { + if (nof == descriptor_count) { Map::SetDescriptors(map, array); return; } // If duplicates were detected, trim the descriptor array to the right size. - int new_array_size = DescriptorArray::LengthFor(new_number_of_descriptors); + int new_array_size = DescriptorArray::LengthFor(nof); if (new_array_size < result->length()) { RightTrimFixedArray( isolate->heap(), *result, result->length() - new_array_size); @@ -3264,19 +3324,20 @@ MaybeObject* JSObject::NormalizeProperties(PropertyNormalizationMode mode, Map* map_of_this = map(); // Allocate new content. - int property_count = map_of_this->NumberOfDescribedProperties(); + int real_size = map_of_this->NumberOfOwnDescriptors(); + int property_count = + map_of_this->NumberOfDescribedProperties(OWN_DESCRIPTORS); if (expected_additional_properties > 0) { property_count += expected_additional_properties; } else { property_count += 2; // Make space for two more properties. } StringDictionary* dictionary; - { MaybeObject* maybe_dictionary = StringDictionary::Allocate(property_count); - if (!maybe_dictionary->To(&dictionary)) return maybe_dictionary; - } + MaybeObject* maybe_dictionary = StringDictionary::Allocate(property_count); + if (!maybe_dictionary->To(&dictionary)) return maybe_dictionary; DescriptorArray* descs = map_of_this->instance_descriptors(); - for (int i = 0; i < descs->number_of_descriptors(); i++) { + for (int i = 0; i < real_size; i++) { PropertyDetails details = descs->GetDetails(i); switch (details.type()) { case CONSTANT_FUNCTION: { @@ -3321,8 +3382,7 @@ MaybeObject* JSObject::NormalizeProperties(PropertyNormalizationMode mode, Heap* current_heap = GetHeap(); // Copy the next enumeration index from instance descriptor. - int index = map_of_this->instance_descriptors()->NextEnumerationIndex(); - dictionary->SetNextEnumerationIndex(index); + dictionary->SetNextEnumerationIndex(real_size + 1); Map* new_map; MaybeObject* maybe_map = @@ -3668,10 +3728,11 @@ MaybeObject* JSObject::GetHiddenPropertiesHashTable( DescriptorArray* descriptors = this->map()->instance_descriptors(); if (descriptors->number_of_descriptors() > 0) { int sorted_index = descriptors->GetSortedKeyIndex(0); - if (descriptors->GetKey(sorted_index) == GetHeap()->hidden_symbol()) { + if (descriptors->GetKey(sorted_index) == GetHeap()->hidden_symbol() && + sorted_index < map()->NumberOfOwnDescriptors()) { ASSERT(descriptors->GetType(sorted_index) == FIELD); - inline_value = this->FastPropertyAt( - descriptors->GetFieldIndex(sorted_index)); + inline_value = + this->FastPropertyAt(descriptors->GetFieldIndex(sorted_index)); } else { inline_value = GetHeap()->undefined_value(); } @@ -3736,7 +3797,8 @@ MaybeObject* JSObject::SetHiddenPropertiesHashTable(Object* value) { DescriptorArray* descriptors = this->map()->instance_descriptors(); if (descriptors->number_of_descriptors() > 0) { int sorted_index = descriptors->GetSortedKeyIndex(0); - if (descriptors->GetKey(sorted_index) == GetHeap()->hidden_symbol()) { + if (descriptors->GetKey(sorted_index) == GetHeap()->hidden_symbol() && + sorted_index < map()->NumberOfOwnDescriptors()) { ASSERT(descriptors->GetType(sorted_index) == FIELD); this->FastPropertyAtPut(descriptors->GetFieldIndex(sorted_index), value); @@ -4178,14 +4240,15 @@ void Map::SetDescriptors(Handle map, } -int Map::NumberOfDescribedProperties(PropertyAttributes filter) { +int Map::NumberOfDescribedProperties(DescriptorFlag which, + PropertyAttributes filter) { int result = 0; DescriptorArray* descs = instance_descriptors(); - for (int i = 0; i < descs->number_of_descriptors(); i++) { - PropertyDetails details = descs->GetDetails(i); - if ((details.attributes() & filter) == 0) { - result++; - } + int limit = which == ALL_DESCRIPTORS + ? descs->number_of_descriptors() + : NumberOfOwnDescriptors(); + for (int i = 0; i < limit; i++) { + if ((descs->GetDetails(i).attributes() & filter) == 0) result++; } return result; } @@ -4193,7 +4256,8 @@ int Map::NumberOfDescribedProperties(PropertyAttributes filter) { int Map::PropertyIndexFor(String* name) { DescriptorArray* descs = instance_descriptors(); - for (int i = 0; i < descs->number_of_descriptors(); i++) { + int limit = NumberOfOwnDescriptors(); + for (int i = 0; i < limit; i++) { if (name->Equals(descs->GetKey(i))) return descs->GetFieldIndex(i); } return -1; @@ -4202,8 +4266,9 @@ int Map::PropertyIndexFor(String* name) { int Map::NextFreePropertyIndex() { int max_index = -1; + int number_of_own_descriptors = NumberOfOwnDescriptors(); DescriptorArray* descs = instance_descriptors(); - for (int i = 0; i < descs->number_of_descriptors(); i++) { + for (int i = 0; i < number_of_own_descriptors; i++) { if (descs->GetType(i) == FIELD) { int current_index = descs->GetFieldIndex(i); if (current_index > max_index) max_index = current_index; @@ -4215,8 +4280,9 @@ int Map::NextFreePropertyIndex() { AccessorDescriptor* Map::FindAccessor(String* name) { DescriptorArray* descs = instance_descriptors(); - for (int i = 0; i < descs->number_of_descriptors(); i++) { - if (name->Equals(descs->GetKey(i)) && descs->GetType(i) == CALLBACKS) { + int number_of_own_descriptors = NumberOfOwnDescriptors(); + for (int i = 0; i < number_of_own_descriptors; i++) { + if (descs->GetType(i) == CALLBACKS && name->Equals(descs->GetKey(i))) { return descs->GetCallbacks(i); } } @@ -4640,9 +4706,10 @@ MaybeObject* JSObject::DefineFastAccessor(String* name, if (result.IsFound()) { Map* target = result.GetTransitionTarget(); - ASSERT(target->instance_descriptors()->number_of_descriptors() == - map()->instance_descriptors()->number_of_descriptors()); - ASSERT(target->instance_descriptors()->GetKey(descriptor_number) == name); + ASSERT(target->NumberOfOwnDescriptors() == + map()->NumberOfOwnDescriptors()); + // This works since descriptors are sorted in order of addition. + ASSERT(map()->instance_descriptors()->GetKey(descriptor_number) == name); return TryAccessorTransition( this, target, descriptor_number, component, accessor, attributes); } @@ -4825,8 +4892,9 @@ Object* JSObject::LookupAccessor(String* name, AccessorComponent component) { Object* JSObject::SlowReverseLookup(Object* value) { if (HasFastProperties()) { + int number_of_own_descriptors = map()->NumberOfOwnDescriptors(); DescriptorArray* descs = map()->instance_descriptors(); - for (int i = 0; i < descs->number_of_descriptors(); i++) { + for (int i = 0; i < number_of_own_descriptors; i++) { if (descs->GetType(i) == FIELD) { if (FastPropertyAt(descs->GetFieldIndex(i)) == value) { return descs->GetKey(i); @@ -4855,8 +4923,11 @@ MaybeObject* Map::RawCopy(int instance_size) { result->set_bit_field(bit_field()); result->set_bit_field2(bit_field2()); result->set_bit_field3(bit_field3()); - result->SetNumberOfOwnDescriptors(0); - result->SetEnumLength(kInvalidEnumCache); + int new_bit_field3 = bit_field3(); + new_bit_field3 = OwnsDescriptors::update(new_bit_field3, true); + new_bit_field3 = NumberOfOwnDescriptorsBits::update(new_bit_field3, 0); + new_bit_field3 = EnumLengthBits::update(new_bit_field3, kInvalidEnumCache); + result->set_bit_field3(new_bit_field3); return result; } @@ -4906,14 +4977,68 @@ MaybeObject* Map::CopyDropDescriptors() { } +MaybeObject* Map::ShareDescriptor(Descriptor* descriptor) { + // Sanity check. This path is only to be taken if the map owns its descriptor + // array, implying that its NumberOfOwnDescriptors equals the number of + // descriptors in the descriptor array. + ASSERT(NumberOfOwnDescriptors() == + instance_descriptors()->number_of_descriptors()); + Map* result; + MaybeObject* maybe_result = CopyDropDescriptors(); + if (!maybe_result->To(&result)) return maybe_result; + + String* name = descriptor->GetKey(); + + TransitionArray* transitions; + MaybeObject* maybe_transitions = AddTransition(name, result); + if (!maybe_transitions->To(&transitions)) return maybe_transitions; + + DescriptorArray* descriptors = instance_descriptors(); + int old_size = descriptors->number_of_descriptors(); + + DescriptorArray* new_descriptors; + MaybeObject* maybe_descriptors = DescriptorArray::Allocate(old_size + 1); + if (!maybe_descriptors->To(&new_descriptors)) return maybe_descriptors; + FixedArray::WhitenessWitness witness(new_descriptors); + + for (int i = 0; i < old_size; ++i) { + new_descriptors->CopyFrom(i, descriptors, i, witness); + } + new_descriptors->Append(descriptor, witness, old_size); + + // If the source descriptors had an enum cache we copy it. This ensures that + // the maps to which we push the new descriptor array back can rely on a + // cache always being available once it is set. If the map has more + // enumerated descriptors than available in the original cache, the cache + // will be lazily replaced by the extended cache when needed. + if (descriptors->HasEnumCache()) { + new_descriptors->CopyEnumCacheFrom(descriptors); + } + + transitions->set_descriptors(new_descriptors); + set_transitions(transitions); + result->SetBackPointer(this); + set_owns_descriptors(false); + + result->SetNumberOfOwnDescriptors(new_descriptors->number_of_descriptors()); + ASSERT(result->NumberOfOwnDescriptors() == NumberOfOwnDescriptors() + 1); + + return result; +} + + MaybeObject* Map::CopyReplaceDescriptors(DescriptorArray* descriptors, String* name, TransitionFlag flag) { + ASSERT(descriptors->IsSortedNoDuplicates()); + Map* result; MaybeObject* maybe_result = CopyDropDescriptors(); if (!maybe_result->To(&result)) return maybe_result; - if (descriptors->number_of_descriptors() != 0) { + // Unless we are creating a map with no descriptors and no back pointer, we + // insert the descriptor array locally. + if (!descriptors->IsEmpty()) { MaybeObject* maybe_failure = result->SetDescriptors(descriptors); if (maybe_failure->IsFailure()) return maybe_failure; result->SetNumberOfOwnDescriptors(descriptors->number_of_descriptors()); @@ -4924,6 +5049,23 @@ MaybeObject* Map::CopyReplaceDescriptors(DescriptorArray* descriptors, MaybeObject* maybe_transitions = AddTransition(name, result); if (!maybe_transitions->To(&transitions)) return maybe_transitions; + if (descriptors->IsEmpty()) { + if (owns_descriptors()) { + // If the copied map has no added fields, and the parent map owns its + // descriptors, those descriptors have to be empty. In that case, + // transfer ownership of the descriptors to the new child. + ASSERT(instance_descriptors()->IsEmpty()); + set_owns_descriptors(false); + } else { + // If the parent did not own its own descriptors, it may share a larger + // descriptors array already. In that case, force a split by setting + // the descriptor array of the new map to the empty descriptor array. + MaybeObject* maybe_failure = + result->SetDescriptors(GetHeap()->empty_descriptor_array()); + if (maybe_failure->IsFailure()) return maybe_failure; + } + } + set_transitions(transitions); result->SetBackPointer(this); } @@ -4933,12 +5075,6 @@ MaybeObject* Map::CopyReplaceDescriptors(DescriptorArray* descriptors, MaybeObject* Map::CopyAsElementsKind(ElementsKind kind, TransitionFlag flag) { - // Create a new free-floating map only if we are not allowed to store it. - Map* new_map = NULL; - MaybeObject* maybe_new_map = Copy(); - if (!maybe_new_map->To(&new_map)) return maybe_new_map; - new_map->set_elements_kind(kind); - if (flag == INSERT_TRANSITION) { ASSERT(!HasElementsTransition() || ((elements_transition_map()->elements_kind() == DICTIONARY_ELEMENTS || @@ -4949,7 +5085,46 @@ MaybeObject* Map::CopyAsElementsKind(ElementsKind kind, TransitionFlag flag) { ASSERT(!IsFastElementsKind(kind) || IsMoreGeneralElementsKindTransition(elements_kind(), kind)); ASSERT(kind != elements_kind()); + } + + if (flag == INSERT_TRANSITION && owns_descriptors()) { + // In case the map owned its own descriptors, share the descriptors and + // transfer ownership to the new map. + Map* new_map; + MaybeObject* maybe_new_map = CopyDropDescriptors(); + if (!maybe_new_map->To(&new_map)) return maybe_new_map; + + MaybeObject* added_elements = set_elements_transition_map(new_map); + if (added_elements->IsFailure()) return added_elements; + + new_map->set_elements_kind(kind); + new_map->SetBackPointer(this); + new_map->SetNumberOfOwnDescriptors(NumberOfOwnDescriptors()); + set_owns_descriptors(false); + return new_map; + } + + // In case the map did not own its own descriptors, a split is forced by + // copying the map; creating a new descriptor array cell. + // Create a new free-floating map only if we are not allowed to store it. + Map* new_map; + MaybeObject* maybe_new_map = Copy(); + if (!maybe_new_map->To(&new_map)) return maybe_new_map; + ASSERT(new_map->NumberOfOwnDescriptors() == NumberOfOwnDescriptors()); + new_map->set_elements_kind(kind); + if (flag == INSERT_TRANSITION) { + // Map::Copy does not store the descriptor array in case it is empty, since + // it does not insert a back pointer; implicitly indicating that its + // descriptor array is empty. Since in this case we do want to insert a back + // pointer, we have to manually set the empty descriptor array to force a + // split. + if (!new_map->StoresOwnDescriptors()) { + ASSERT(new_map->NumberOfOwnDescriptors() == 0); + MaybeObject* maybe_failure = + new_map->SetDescriptors(GetHeap()->empty_descriptor_array()); + if (maybe_failure->IsFailure()) return maybe_failure; + } MaybeObject* added_elements = set_elements_transition_map(new_map); if (added_elements->IsFailure()) return added_elements; @@ -4970,13 +5145,25 @@ MaybeObject* Map::CopyWithPreallocatedFieldDescriptors() { Map* map = ctor->initial_map(); DescriptorArray* descriptors = map->instance_descriptors(); - return CopyReplaceDescriptors(descriptors, NULL, OMIT_TRANSITION); + int number_of_own_descriptors = map->NumberOfOwnDescriptors(); + DescriptorArray* new_descriptors; + MaybeObject* maybe_descriptors = + descriptors->CopyUpTo(number_of_own_descriptors); + if (!maybe_descriptors->To(&new_descriptors)) return maybe_descriptors; + + return CopyReplaceDescriptors(new_descriptors, NULL, OMIT_TRANSITION); } MaybeObject* Map::Copy() { DescriptorArray* descriptors = instance_descriptors(); - return CopyReplaceDescriptors(descriptors, NULL, OMIT_TRANSITION); + DescriptorArray* new_descriptors; + int number_of_own_descriptors = NumberOfOwnDescriptors(); + MaybeObject* maybe_descriptors = + descriptors->CopyUpTo(number_of_own_descriptors); + if (!maybe_descriptors->To(&new_descriptors)) return maybe_descriptors; + + return CopyReplaceDescriptors(new_descriptors, NULL, OMIT_TRANSITION); } @@ -4988,14 +5175,18 @@ MaybeObject* Map::CopyAddDescriptor(Descriptor* descriptor, MaybeObject* maybe_failure = descriptor->KeyToSymbol(); if (maybe_failure->IsFailure()) return maybe_failure; - String* key = descriptor->GetKey(); - ASSERT(descriptors->Search(key) == DescriptorArray::kNotFound); - - int old_size = descriptors->number_of_descriptors(); + int old_size = NumberOfOwnDescriptors(); int new_size = old_size + 1; + descriptor->SetEnumerationIndex(new_size); + + if (flag == INSERT_TRANSITION && + owns_descriptors() && + CanHaveMoreTransitions()) { + return ShareDescriptor(descriptor); + } DescriptorArray* new_descriptors; - MaybeObject* maybe_descriptors = DescriptorArray::Allocate(new_size); + MaybeObject* maybe_descriptors = DescriptorArray::Allocate(old_size + 1); if (!maybe_descriptors->To(&new_descriptors)) return maybe_descriptors; FixedArray::WhitenessWitness witness(new_descriptors); @@ -5005,11 +5196,10 @@ MaybeObject* Map::CopyAddDescriptor(Descriptor* descriptor, new_descriptors->CopyFrom(i, descriptors, i, witness); } - new_descriptors->Append(descriptor, witness, old_size); - - SLOW_ASSERT(new_descriptors->IsSortedNoDuplicates()); + new_descriptors->Set(old_size, descriptor, witness); + new_descriptors->Sort(); - return CopyReplaceDescriptors(new_descriptors, key, flag); + return CopyReplaceDescriptors(new_descriptors, descriptor->GetKey(), flag); } @@ -5022,7 +5212,7 @@ MaybeObject* Map::CopyInsertDescriptor(Descriptor* descriptor, if (maybe_result->IsFailure()) return maybe_result; // We replace the key if it is already present. - int index = old_descriptors->SearchWithCache(descriptor->GetKey()); + int index = old_descriptors->SearchWithCache(descriptor->GetKey(), this); if (index != DescriptorArray::kNotFound) { return CopyReplaceDescriptor(descriptor, index, flag); } @@ -5030,39 +5220,60 @@ MaybeObject* Map::CopyInsertDescriptor(Descriptor* descriptor, } +MaybeObject* DescriptorArray::CopyUpTo(int enumeration_index) { + if (enumeration_index == 0) return GetHeap()->empty_descriptor_array(); + + int size = enumeration_index; + + DescriptorArray* descriptors; + MaybeObject* maybe_descriptors = Allocate(size); + if (!maybe_descriptors->To(&descriptors)) return maybe_descriptors; + DescriptorArray::WhitenessWitness witness(descriptors); + + for (int i = 0; i < size; ++i) { + descriptors->CopyFrom(i, this, i, witness); + } + + if (number_of_descriptors() != enumeration_index) descriptors->Sort(); + + return descriptors; +} + + MaybeObject* Map::CopyReplaceDescriptor(Descriptor* descriptor, int insertion_index, TransitionFlag flag) { - DescriptorArray* descriptors = instance_descriptors(); - int size = descriptors->number_of_descriptors(); - ASSERT(0 <= insertion_index && insertion_index < size); - // Ensure the key is a symbol. MaybeObject* maybe_failure = descriptor->KeyToSymbol(); if (maybe_failure->IsFailure()) return maybe_failure; + DescriptorArray* descriptors = instance_descriptors(); + String* key = descriptor->GetKey(); ASSERT(key == descriptors->GetKey(insertion_index)); + int new_size = NumberOfOwnDescriptors(); + ASSERT(0 <= insertion_index && insertion_index < new_size); + + PropertyDetails details = descriptors->GetDetails(insertion_index); + ASSERT_LE(details.descriptor_index(), new_size); + descriptor->SetEnumerationIndex(details.descriptor_index()); + DescriptorArray* new_descriptors; - MaybeObject* maybe_descriptors = DescriptorArray::Allocate(size); + MaybeObject* maybe_descriptors = DescriptorArray::Allocate(new_size); if (!maybe_descriptors->To(&new_descriptors)) return maybe_descriptors; + DescriptorArray::WhitenessWitness witness(new_descriptors); - FixedArray::WhitenessWitness witness(new_descriptors); - - // Copy the descriptors, replacing a descriptor. - for (int index = 0; index < size; ++index) { - if (index == insertion_index) continue; - new_descriptors->CopyFrom(index, descriptors, index, witness); + for (int i = 0; i < new_size; ++i) { + if (i == insertion_index) { + new_descriptors->Set(i, descriptor, witness); + } else { + new_descriptors->CopyFrom(i, descriptors, i, witness); + } } - PropertyDetails original_details = descriptors->GetDetails(insertion_index); - descriptor->SetEnumerationIndex(original_details.descriptor_index()); - descriptor->SetSortedKey(original_details.pointer()); - - new_descriptors->Set(insertion_index, descriptor, witness); - - SLOW_ASSERT(new_descriptors->IsSortedNoDuplicates()); + // Re-sort if descriptors were removed. + if (new_size != descriptors->length()) new_descriptors->Sort(); return CopyReplaceDescriptors(new_descriptors, key, flag); } @@ -5860,12 +6071,13 @@ void DescriptorArray::SetEnumCache(FixedArray* bridge_storage, ASSERT(bridge_storage->length() >= kEnumCacheBridgeLength); ASSERT(new_index_cache->IsSmi() || new_index_cache->IsFixedArray()); if (HasEnumCache()) { + ASSERT(new_cache->length() > FixedArray::cast(GetEnumCache())->length()); FixedArray::cast(get(kEnumCacheIndex))-> set(kEnumCacheBridgeCacheIndex, new_cache); FixedArray::cast(get(kEnumCacheIndex))-> set(kEnumCacheBridgeIndicesCacheIndex, new_index_cache); } else { - if (IsEmpty()) return; // Do nothing for empty descriptor array. + ASSERT(!IsEmpty()); FixedArray::cast(bridge_storage)-> set(kEnumCacheBridgeCacheIndex, new_cache); FixedArray::cast(bridge_storage)-> @@ -5941,6 +6153,7 @@ void DescriptorArray::Sort() { parent_index = child_index; } } + ASSERT(IsSortedNoDuplicates()); } @@ -7188,11 +7401,9 @@ void String::PrintOn(FILE* file) { // Clear a possible back pointer in case the transition leads to a dead map. // Return true in case a back pointer has been cleared and false otherwise. -static bool ClearBackPointer(Heap* heap, Object* target) { - ASSERT(target->IsMap()); - Map* map = Map::cast(target); - if (Marking::MarkBitFrom(map).Get()) return false; - map->SetBackPointer(heap->undefined_value(), SKIP_WRITE_BARRIER); +static bool ClearBackPointer(Heap* heap, Map* target) { + if (Marking::MarkBitFrom(target).Get()) return false; + target->SetBackPointer(heap->undefined_value(), SKIP_WRITE_BARRIER); return true; } @@ -7211,9 +7422,21 @@ void Map::ClearNonLiveTransitions(Heap* heap) { int transition_index = 0; + DescriptorArray* descriptors = t->descriptors(); + bool descriptors_owner_died = false; + // Compact all live descriptors to the left. for (int i = 0; i < t->number_of_transitions(); ++i) { - if (!ClearBackPointer(heap, t->GetTarget(i))) { + Map* target = t->GetTarget(i); + if (ClearBackPointer(heap, target)) { + ASSERT(!Marking::IsGrey(Marking::MarkBitFrom(target))); + DescriptorArray* target_descriptors = target->instance_descriptors(); + if ((target_descriptors->number_of_descriptors() == 0 && + target->NumberOfOwnDescriptors() > 0) || + target_descriptors == descriptors) { + descriptors_owner_died = true; + } + } else { if (i != transition_index) { String* key = t->GetKey(i); t->SetKey(transition_index, key); @@ -7228,6 +7451,9 @@ void Map::ClearNonLiveTransitions(Heap* heap) { if (t->HasElementsTransition() && ClearBackPointer(heap, t->elements_transition())) { + if (t->elements_transition()->instance_descriptors() == descriptors) { + descriptors_owner_died = true; + } t->ClearElementsTransition(); } else { // If there are no transitions to be cleared, return. @@ -7236,12 +7462,41 @@ void Map::ClearNonLiveTransitions(Heap* heap) { if (transition_index == t->number_of_transitions()) return; } + int number_of_own_descriptors = NumberOfOwnDescriptors(); + + if (descriptors_owner_died) { + if (number_of_own_descriptors > 0) { + int live_enum = NumberOfDescribedProperties(OWN_DESCRIPTORS, DONT_ENUM); + int number_of_descriptors = descriptors->number_of_descriptors(); + int to_trim = number_of_descriptors - number_of_own_descriptors; + if (to_trim > 0) { + RightTrimFixedArray( + heap, descriptors, to_trim * DescriptorArray::kDescriptorSize); + if (descriptors->HasEnumCache()) { + FixedArray* enum_cache = + FixedArray::cast(descriptors->GetEnumCache()); + to_trim = enum_cache->length() - live_enum; + if (to_trim > 0) { + RightTrimFixedArray( + heap, FixedArray::cast(descriptors->GetEnumCache()), to_trim); + } + } + descriptors->Sort(); + } + ASSERT(descriptors->number_of_descriptors() == number_of_own_descriptors); + } else { + t->set_descriptors(heap->empty_descriptor_array()); + } + set_owns_descriptors(true); + } + // If the final transition array does not contain any live transitions, remove // the transition array from the map. if (transition_index == 0 && !t->HasElementsTransition() && !t->HasPrototypeTransitions() && - t->descriptors()->IsEmpty()) { + number_of_own_descriptors == 0) { + ASSERT(owns_descriptors()); return ClearTransitions(heap); } @@ -10366,7 +10621,7 @@ bool JSObject::HasRealNamedCallbackProperty(String* key) { int JSObject::NumberOfLocalProperties(PropertyAttributes filter) { return HasFastProperties() ? - map()->NumberOfDescribedProperties(filter) : + map()->NumberOfDescribedProperties(OWN_DESCRIPTORS, filter) : property_dictionary()->NumberOfElementsFilterAttributes(filter); } @@ -10490,9 +10745,10 @@ void FixedArray::SortPairs(FixedArray* numbers, uint32_t len) { void JSObject::GetLocalPropertyNames(FixedArray* storage, int index) { ASSERT(storage->length() >= (NumberOfLocalProperties() - index)); if (HasFastProperties()) { + int real_size = map()->NumberOfOwnDescriptors(); DescriptorArray* descs = map()->instance_descriptors(); - ASSERT(storage->length() >= index + descs->number_of_descriptors()); - for (int i = 0; i < descs->number_of_descriptors(); i++) { + ASSERT(storage->length() >= index + real_size); + for (int i = 0; i < real_size; i++) { storage->set(index + i, descs->GetKey(i)); } } else { @@ -12195,8 +12451,8 @@ MaybeObject* Dictionary::GenerateNewEnumerationIndices() { int pos = 0; for (int i = 0; i < capacity; i++) { if (Dictionary::IsKey(Dictionary::KeyAt(i))) { - enumeration_order->set( - pos++, Smi::FromInt(DetailsAt(i).dictionary_index())); + int index = DetailsAt(i).dictionary_index(); + enumeration_order->set(pos++, Smi::FromInt(index)); } } @@ -12325,7 +12581,8 @@ MaybeObject* Dictionary::AddEntry(Key key, uint32_t entry = Dictionary::FindInsertionEntry(hash); // Insert element at empty or deleted entry if (!details.IsDeleted() && - details.dictionary_index() == 0 && Shape::kIsEnumerable) { + details.dictionary_index() == 0 && + Shape::kIsEnumerable) { // Assign an enumeration index to the property and update // SetNextEnumerationIndex. int index = NextEnumerationIndex(); diff --git a/src/objects.h b/src/objects.h index 45a2ac0d8..e1f1d3bad 100644 --- a/src/objects.h +++ b/src/objects.h @@ -177,6 +177,13 @@ enum TransitionFlag { OMIT_TRANSITION }; +// Indicates whether we are only interested in the descriptors of a particular +// map, or in all descriptors in the descriptor array. +enum DescriptorFlag { + ALL_DESCRIPTORS, + OWN_DESCRIPTORS +}; + // Instance size sentinel for objects of variable size. const int kVariableSizeSentinel = 0; @@ -2481,12 +2488,15 @@ class DescriptorArray: public FixedArray { } inline int number_of_entries() { return number_of_descriptors(); } - inline int NextEnumerationIndex() { return number_of_descriptors() + 1; } bool HasEnumCache() { return !IsEmpty() && !get(kEnumCacheIndex)->IsSmi(); } + void CopyEnumCacheFrom(DescriptorArray* array) { + set(kEnumCacheIndex, array->get(kEnumCacheIndex)); + } + Object* GetEnumCache() { ASSERT(HasEnumCache()); FixedArray* bridge = FixedArray::cast(get(kEnumCacheIndex)); @@ -2541,19 +2551,17 @@ class DescriptorArray: public FixedArray { int src_index, const WhitenessWitness&); + MUST_USE_RESULT MaybeObject* CopyUpTo(int enumeration_index); + // Sort the instance descriptors by the hash codes of their keys. void Sort(); - inline void SwapSortedKeys(int first, int second); // Search the instance descriptors for given name. - INLINE(int Search(String* name)); + INLINE(int Search(String* name, int number_of_own_descriptors)); // As the above, but uses DescriptorLookupCache and updates it when // necessary. - INLINE(int SearchWithCache(String* name)); - - // Tells whether the name is present int the array. - bool Contains(String* name) { return kNotFound != Search(name); } + INLINE(int SearchWithCache(String* name, Map* map)); // Allocates a DescriptorArray, but returns the singleton // empty descriptor array object if number_of_descriptors is 0. @@ -2596,7 +2604,7 @@ class DescriptorArray: public FixedArray { #ifdef DEBUG // Is the descriptor array sorted and without duplicates? - bool IsSortedNoDuplicates(); + bool IsSortedNoDuplicates(int valid_descriptors = -1); // Is the descriptor array consistent with the back pointers in targets? bool IsConsistentWithBackPointers(Map* current_map); @@ -2649,24 +2657,21 @@ class DescriptorArray: public FixedArray { kDescriptorValue; } - // Swap operation on FixedArray without using write barriers. - static inline void NoIncrementalWriteBarrierSwap( - FixedArray* array, int first, int second); - // Swap first and second descriptor. - inline void NoIncrementalWriteBarrierSwapDescriptors( - int first, int second); + inline void SwapSortedKeys(int first, int second); DISALLOW_IMPLICIT_CONSTRUCTORS(DescriptorArray); }; -template -inline int LinearSearch(T* array, String* name, int len); +enum SearchMode { ALL_ENTRIES, VALID_ENTRIES }; +template +inline int LinearSearch(T* array, String* name, int len, int valid_entries); -template -inline int Search(T* array, String* name); + +template +inline int Search(T* array, String* name, int valid_entries = 0); // HashTable is a subclass of FixedArray that implements a hash table @@ -4672,6 +4677,7 @@ class Map: public HeapObject { class IsShared: public BitField {}; class FunctionWithPrototype: public BitField {}; class DictionaryMap: public BitField {}; + class OwnsDescriptors: public BitField {}; // Tells whether the object in the prototype property will be used // for instances created from this function. If the prototype @@ -4792,12 +4798,14 @@ class Map: public HeapObject { static bool IsValidElementsTransition(ElementsKind from_kind, ElementsKind to_kind); + bool StoresOwnDescriptors() { return HasTransitionArray(); } inline bool HasTransitionArray(); inline bool HasElementsTransition(); inline Map* elements_transition_map(); MUST_USE_RESULT inline MaybeObject* set_elements_transition_map( Map* transitioned_map); - inline void SetTransition(int index, Map* target); + inline void SetTransition(int transition_index, Map* target); + inline Map* GetTransition(int transition_index); MUST_USE_RESULT inline MaybeObject* AddTransition(String* key, Map* target); DECL_ACCESSORS(transitions, TransitionArray) inline void ClearTransitions(Heap* heap, @@ -4837,9 +4845,9 @@ class Map: public HeapObject { // [instance descriptors]: describes the object. inline DescriptorArray* instance_descriptors(); + inline JSGlobalPropertyCell* descriptors_pointer(); MUST_USE_RESULT inline MaybeObject* SetDescriptors( - DescriptorArray* descriptors, - WriteBarrierMode mode = UPDATE_WRITE_BARRIER); + DescriptorArray* descriptors); static void SetDescriptors(Handle map, Handle descriptors); MUST_USE_RESULT inline MaybeObject* InitializeDescriptors( @@ -4920,17 +4928,29 @@ class Map: public HeapObject { } void SetNumberOfOwnDescriptors(int number) { + ASSERT(number <= instance_descriptors()->number_of_descriptors()); set_bit_field3(NumberOfOwnDescriptorsBits::update(bit_field3(), number)); } + inline JSGlobalPropertyCell* RetrieveDescriptorsPointer(); + int EnumLength() { return EnumLengthBits::decode(bit_field3()); } - void SetEnumLength(int index) { - set_bit_field3(EnumLengthBits::update(bit_field3(), index)); + void SetEnumLength(int length) { + if (length != kInvalidEnumCache) { + ASSERT(length >= 0); + ASSERT(length == 0 || instance_descriptors()->HasEnumCache()); + ASSERT(length <= NumberOfOwnDescriptors()); + } + set_bit_field3(EnumLengthBits::update(bit_field3(), length)); } + + inline bool owns_descriptors(); + inline void set_owns_descriptors(bool is_shared); + MUST_USE_RESULT MaybeObject* RawCopy(int instance_size); MUST_USE_RESULT MaybeObject* CopyWithPreallocatedFieldDescriptors(); MUST_USE_RESULT MaybeObject* CopyDropDescriptors(); @@ -4938,6 +4958,7 @@ class Map: public HeapObject { DescriptorArray* descriptors, String* name, TransitionFlag flag); + MUST_USE_RESULT MaybeObject* ShareDescriptor(Descriptor* descriptor); MUST_USE_RESULT MaybeObject* CopyAddDescriptor(Descriptor* descriptor, TransitionFlag flag); MUST_USE_RESULT MaybeObject* CopyInsertDescriptor(Descriptor* descriptor, @@ -4966,7 +4987,8 @@ class Map: public HeapObject { // Returns the number of properties described in instance_descriptors // filtering out properties with the specified attributes. - int NumberOfDescribedProperties(PropertyAttributes filter = NONE); + int NumberOfDescribedProperties(DescriptorFlag which = OWN_DESCRIPTORS, + PropertyAttributes filter = NONE); // Casting. static inline Map* cast(Object* obj); @@ -5070,7 +5092,7 @@ class Map: public HeapObject { static const int kMaxPreAllocatedPropertyFields = 255; - // Constant for denoting that the Enum Cache field was not yet used. + // Constant for denoting that the enum cache is not yet initialized. static const int kInvalidEnumCache = EnumLengthBits::kMax; // Layout description. diff --git a/src/profile-generator.cc b/src/profile-generator.cc index c3b7622b0..64abc7dac 100644 --- a/src/profile-generator.cc +++ b/src/profile-generator.cc @@ -2009,20 +2009,33 @@ void V8HeapExplorer::ExtractMapReferences(int entry, Map* map) { Map::kConstructorOffset); if (map->HasTransitionArray()) { TransitionArray* transitions = map->transitions(); - if (!transitions->descriptors()->IsEmpty()) { - DescriptorArray* descriptors = transitions->descriptors(); - TagObject(descriptors, "(map descriptors)"); - SetInternalReference(transitions, entry, - "descriptors", descriptors, - TransitionArray::kDescriptorsOffset); - IndexedReferencesExtractor refs_extractor( - this, transitions, entry); - transitions->Iterate(&refs_extractor); - } + JSGlobalPropertyCell* pointer = transitions->descriptors_pointer(); + DescriptorArray* descriptors = transitions->descriptors(); + TagObject(descriptors, "(map descriptors)"); + SetInternalReference(pointer, entry, + "descriptors", descriptors, + JSGlobalPropertyCell::kValueOffset); + IndexedReferencesExtractor pointer_refs(this, pointer, entry); + pointer->Iterate(&pointer_refs); + + Object* back_pointer = transitions->back_pointer_storage(); + TagObject(transitions->back_pointer_storage(), "(back pointer)"); + SetInternalReference(transitions, entry, + "backpointer", back_pointer, + TransitionArray::kBackPointerStorageOffset); + IndexedReferencesExtractor transitions_refs(this, transitions, entry); + transitions->Iterate(&transitions_refs); + TagObject(transitions, "(transition array)"); SetInternalReference(map, entry, "transitions", transitions, Map::kTransitionsOrBackPointerOffset); + } else { + Object* back_pointer = map->GetBackPointer(); + TagObject(back_pointer, "(back pointer)"); + SetInternalReference(map, entry, + "backpointer", back_pointer, + Map::kTransitionsOrBackPointerOffset); } SetInternalReference(map, entry, "code_cache", map->code_cache(), @@ -2179,7 +2192,9 @@ void V8HeapExplorer::ExtractClosureReferences(JSObject* js_obj, int entry) { void V8HeapExplorer::ExtractPropertyReferences(JSObject* js_obj, int entry) { if (js_obj->HasFastProperties()) { DescriptorArray* descs = js_obj->map()->instance_descriptors(); + int real_size = js_obj->map()->NumberOfOwnDescriptors(); for (int i = 0; i < descs->number_of_descriptors(); i++) { + if (descs->GetDetails(i).descriptor_index() > real_size) continue; switch (descs->GetType(i)) { case FIELD: { int index = descs->GetFieldIndex(i); diff --git a/src/property.h b/src/property.h index 6bf52a701..9eb4194b4 100644 --- a/src/property.h +++ b/src/property.h @@ -68,7 +68,7 @@ class Descriptor BASE_EMBEDDED { details_ = PropertyDetails(details_.attributes(), details_.type(), index); } - void SetSortedKey(int index) { details_ = details_.set_pointer(index); } + void SetSortedKeyIndex(int index) { details_ = details_.set_pointer(index); } private: String* key_; @@ -384,6 +384,7 @@ class LookupResult BASE_EMBEDDED { Object* GetValueFromMap(Map* map) const { ASSERT(lookup_type_ == DESCRIPTOR_TYPE); + ASSERT(number_ < map->NumberOfOwnDescriptors()); return map->instance_descriptors()->GetValue(number_); } diff --git a/src/runtime.cc b/src/runtime.cc index 93e0199ea..f21608f19 100644 --- a/src/runtime.cc +++ b/src/runtime.cc @@ -2166,7 +2166,7 @@ RUNTIME_FUNCTION(MaybeObject*, Runtime_FunctionSetReadOnlyPrototype) { // Construct a new field descriptor with updated attributes. DescriptorArray* instance_desc = function->map()->instance_descriptors(); - int index = instance_desc->SearchWithCache(name); + int index = instance_desc->SearchWithCache(name, function->map()); ASSERT(index != DescriptorArray::kNotFound); PropertyDetails details = instance_desc->GetDetails(index); diff --git a/src/string-stream.cc b/src/string-stream.cc index 51aa2bb32..30519b561 100644 --- a/src/string-stream.cc +++ b/src/string-stream.cc @@ -348,9 +348,12 @@ void StringStream::PrintUsingMap(JSObject* js_object) { Add("\n"); return; } + int real_size = map->NumberOfOwnDescriptors(); DescriptorArray* descs = map->instance_descriptors(); for (int i = 0; i < descs->number_of_descriptors(); i++) { - if (descs->GetType(i) == FIELD) { + PropertyDetails details = descs->GetDetails(i); + if (details.descriptor_index() > real_size) continue; + if (details.type() == FIELD) { Object* key = descs->GetKey(i); if (key->IsString() || key->IsNumber()) { int len = 3; diff --git a/src/transitions-inl.h b/src/transitions-inl.h index 385bdd119..fd97ad25a 100644 --- a/src/transitions-inl.h +++ b/src/transitions-inl.h @@ -83,22 +83,26 @@ void TransitionArray::set_elements_transition(Map* transition_map, DescriptorArray* TransitionArray::descriptors() { - return DescriptorArray::cast(get(kDescriptorsIndex)); + return DescriptorArray::cast(descriptors_pointer()->value()); } -void TransitionArray::set_descriptors(DescriptorArray* descriptors, - WriteBarrierMode mode) { - Heap* heap = GetHeap(); - WRITE_FIELD(this, kDescriptorsOffset, descriptors); - CONDITIONAL_WRITE_BARRIER( - heap, this, kDescriptorsOffset, descriptors, mode); +void TransitionArray::set_descriptors(DescriptorArray* descriptors) { + ASSERT(!this->descriptors()->IsDescriptorArray() || + descriptors->number_of_descriptors() == 0 || + descriptors->HasEnumCache() || + !this->descriptors()->HasEnumCache()); + descriptors_pointer()->set_value(descriptors); } -Object** TransitionArray::GetDescriptorsSlot() { - return HeapObject::RawField(reinterpret_cast(this), - kDescriptorsOffset); +JSGlobalPropertyCell* TransitionArray::descriptors_pointer() { + return JSGlobalPropertyCell::cast(get(kDescriptorsPointerIndex)); +} + + +void TransitionArray::set_descriptors_pointer(JSGlobalPropertyCell* pointer) { + set(kDescriptorsPointerIndex, pointer); } @@ -192,7 +196,7 @@ PropertyDetails TransitionArray::GetTargetDetails(int transition_number) { int TransitionArray::Search(String* name) { - return internal::Search(this, name); + return internal::Search(this, name); } diff --git a/src/transitions.cc b/src/transitions.cc index 6f8b2fec5..0ea58c7d5 100644 --- a/src/transitions.cc +++ b/src/transitions.cc @@ -35,14 +35,23 @@ namespace v8 { namespace internal { -MaybeObject* TransitionArray::Allocate(int number_of_transitions) { +MaybeObject* TransitionArray::Allocate(int number_of_transitions, + JSGlobalPropertyCell* descriptors_cell) { Heap* heap = Isolate::Current()->heap(); + + if (descriptors_cell == NULL) { + MaybeObject* maybe_cell = + heap->AllocateJSGlobalPropertyCell(heap->empty_descriptor_array()); + if (!maybe_cell->To(&descriptors_cell)) return maybe_cell; + } + // Use FixedArray to not use DescriptorArray::cast on incomplete object. FixedArray* array; MaybeObject* maybe_array = heap->AllocateFixedArray(ToKeyIndex(number_of_transitions)); if (!maybe_array->To(&array)) return maybe_array; + array->set(kDescriptorsPointerIndex, descriptors_cell); array->set(kElementsTransitionIndex, Smi::FromInt(0)); array->set(kPrototypeTransitionsIndex, Smi::FromInt(0)); return array; @@ -65,15 +74,20 @@ static bool InsertionPointFound(String* key1, String* key2) { } -MaybeObject* TransitionArray::NewWith(String* name, Map* target) { +MaybeObject* TransitionArray::NewWith( + String* name, + Map* target, + JSGlobalPropertyCell* descriptors_pointer, + Object* back_pointer) { TransitionArray* result; - MaybeObject* maybe_array = TransitionArray::Allocate(1); + MaybeObject* maybe_array = TransitionArray::Allocate(1, descriptors_pointer); if (!maybe_array->To(&result)) return maybe_array; FixedArray::WhitenessWitness witness(result); result->Set(0, name, target, witness); + result->set_back_pointer_storage(back_pointer); return result; } @@ -88,7 +102,7 @@ MaybeObject* TransitionArray::CopyInsert(String* name, Map* target) { if (insertion_index == kNotFound) ++new_size; MaybeObject* maybe_array; - maybe_array = TransitionArray::Allocate(new_size); + maybe_array = TransitionArray::Allocate(new_size, descriptors_pointer()); if (!maybe_array->To(&result)) return maybe_array; if (HasElementsTransition()) { @@ -121,6 +135,7 @@ MaybeObject* TransitionArray::CopyInsert(String* name, Map* target) { result->CopyFrom(this, insertion_index, insertion_index + 1, witness); } + result->set_back_pointer_storage(back_pointer_storage()); return result; } diff --git a/src/transitions.h b/src/transitions.h index 63e52badc..e79d6cae5 100644 --- a/src/transitions.h +++ b/src/transitions.h @@ -72,9 +72,9 @@ class TransitionArray: public FixedArray { inline void ClearElementsTransition(); inline DescriptorArray* descriptors(); - inline void set_descriptors(DescriptorArray* descriptors, - WriteBarrierMode mode = UPDATE_WRITE_BARRIER); - inline Object** GetDescriptorsSlot(); + inline void set_descriptors(DescriptorArray* descriptors); + inline JSGlobalPropertyCell* descriptors_pointer(); + inline void set_descriptors_pointer(JSGlobalPropertyCell* pointer); inline Object* back_pointer_storage(); inline void set_back_pointer_storage( @@ -99,7 +99,11 @@ class TransitionArray: public FixedArray { inline int number_of_entries() { return number_of_transitions(); } // Allocate a new transition array with a single entry. - static MUST_USE_RESULT MaybeObject* NewWith(String* name, Map* target); + static MUST_USE_RESULT MaybeObject* NewWith( + String* name, + Map* target, + JSGlobalPropertyCell* descriptor_pointer, + Object* back_pointer); // Copy the transition array, inserting a new transition. // TODO(verwaest): This should not cause an existing transition to be @@ -116,7 +120,9 @@ class TransitionArray: public FixedArray { inline int Search(String* name); // Allocates a TransitionArray. - MUST_USE_RESULT static MaybeObject* Allocate(int number_of_transitions); + MUST_USE_RESULT static MaybeObject* Allocate( + int number_of_transitions, + JSGlobalPropertyCell* descriptors_cell); // Casting. static inline TransitionArray* cast(Object* obj); @@ -124,15 +130,15 @@ class TransitionArray: public FixedArray { // Constant for denoting key was not found. static const int kNotFound = -1; - static const int kDescriptorsIndex = 0; + static const int kDescriptorsPointerIndex = 0; static const int kBackPointerStorageIndex = 1; static const int kElementsTransitionIndex = 2; static const int kPrototypeTransitionsIndex = 3; static const int kFirstIndex = 4; // Layout transition array header. - static const int kDescriptorsOffset = FixedArray::kHeaderSize; - static const int kBackPointerStorageOffset = kDescriptorsOffset + + static const int kDescriptorsPointerOffset = FixedArray::kHeaderSize; + static const int kBackPointerStorageOffset = kDescriptorsPointerOffset + kPointerSize; static const int kElementsTransitionOffset = kBackPointerStorageOffset + kPointerSize; @@ -153,7 +159,7 @@ class TransitionArray: public FixedArray { #endif #ifdef DEBUG - bool IsSortedNoDuplicates(); + bool IsSortedNoDuplicates(int valid_entries = -1); bool IsConsistentWithBackPointers(Map* current_map); bool IsEqualTo(TransitionArray* other); #endif diff --git a/src/x64/full-codegen-x64.cc b/src/x64/full-codegen-x64.cc index 78e1dec51..954d043a9 100644 --- a/src/x64/full-codegen-x64.cc +++ b/src/x64/full-codegen-x64.cc @@ -2642,22 +2642,28 @@ void FullCodeGenerator::EmitIsStringWrapperSafeForDefaultValueOf( __ j(equal, if_false); // Look for valueOf symbol in the descriptor array, and indicate false if - // found. The type is not checked, so if it is a transition it is a false - // negative. + // found. Since we omit an enumeration index check, if it is added via a + // transition that shares its descriptor array, this is a false positive. + Label entry, loop, done; + + // Skip loop if no descriptors are valid. + __ NumberOfOwnDescriptors(rcx, rbx); + __ cmpq(rcx, Immediate(0)); + __ j(equal, &done); + __ LoadInstanceDescriptors(rbx, rbx); - __ movq(rcx, FieldOperand(rbx, FixedArray::kLengthOffset)); - // rbx: descriptor array - // rcx: length of descriptor array + // rbx: descriptor array. + // rcx: valid entries in the descriptor array. // Calculate the end of the descriptor array. + __ imul(rcx, rcx, Immediate(DescriptorArray::kDescriptorSize)); SmiIndex index = masm_->SmiToIndex(rdx, rcx, kPointerSizeLog2); __ lea(rcx, Operand( - rbx, index.reg, index.scale, FixedArray::kHeaderSize)); + rbx, index.reg, index.scale, DescriptorArray::kFirstOffset)); // Calculate location of the first key name. __ addq(rbx, Immediate(DescriptorArray::kFirstOffset)); // Loop through all the keys in the descriptor array. If one of these is the // symbol valueOf the result is false. - Label entry, loop; __ jmp(&entry); __ bind(&loop); __ movq(rdx, FieldOperand(rbx, 0)); @@ -2668,10 +2674,11 @@ void FullCodeGenerator::EmitIsStringWrapperSafeForDefaultValueOf( __ cmpq(rbx, rcx); __ j(not_equal, &loop); + __ bind(&done); // Reload map as register rbx was used as temporary above. __ movq(rbx, FieldOperand(rax, HeapObject::kMapOffset)); - // If a valueOf property is not found on the object check that it's + // If a valueOf property is not found on the object check that its // prototype is the un-modified String prototype. If not result is false. __ movq(rcx, FieldOperand(rbx, Map::kPrototypeOffset)); __ testq(rcx, Immediate(kSmiTagMask)); diff --git a/src/x64/macro-assembler-x64.cc b/src/x64/macro-assembler-x64.cc index 1b0f2fa2d..6759b19a2 100644 --- a/src/x64/macro-assembler-x64.cc +++ b/src/x64/macro-assembler-x64.cc @@ -2920,19 +2920,36 @@ void MacroAssembler::LoadInstanceDescriptors(Register map, Register temp = descriptors; movq(temp, FieldOperand(map, Map::kTransitionsOrBackPointerOffset)); - Label ok, fail; + Label ok, fail, load_from_back_pointer; CheckMap(temp, isolate()->factory()->fixed_array_map(), &fail, DONT_DO_SMI_CHECK); - movq(descriptors, FieldOperand(temp, TransitionArray::kDescriptorsOffset)); + movq(temp, FieldOperand(temp, TransitionArray::kDescriptorsPointerOffset)); + movq(descriptors, FieldOperand(temp, JSGlobalPropertyCell::kValueOffset)); jmp(&ok); + bind(&fail); + CompareRoot(temp, Heap::kUndefinedValueRootIndex); + j(not_equal, &load_from_back_pointer, Label::kNear); Move(descriptors, isolate()->factory()->empty_descriptor_array()); + jmp(&ok); + + bind(&load_from_back_pointer); + movq(temp, FieldOperand(temp, Map::kTransitionsOrBackPointerOffset)); + movq(temp, FieldOperand(temp, TransitionArray::kDescriptorsPointerOffset)); + movq(descriptors, FieldOperand(temp, JSGlobalPropertyCell::kValueOffset)); + bind(&ok); } +void MacroAssembler::NumberOfOwnDescriptors(Register dst, Register map) { + movq(dst, FieldOperand(map, Map::kBitField3Offset)); + DecodeField(dst); +} + + void MacroAssembler::EnumLength(Register dst, Register map) { STATIC_ASSERT(Map::EnumLengthBits::kShift == 0); movq(dst, FieldOperand(map, Map::kBitField3Offset)); diff --git a/src/x64/macro-assembler-x64.h b/src/x64/macro-assembler-x64.h index 5268fe2a2..89b796223 100644 --- a/src/x64/macro-assembler-x64.h +++ b/src/x64/macro-assembler-x64.h @@ -949,13 +949,15 @@ class MacroAssembler: public Assembler { void LoadInstanceDescriptors(Register map, Register descriptors); void EnumLength(Register dst, Register map); + void NumberOfOwnDescriptors(Register dst, Register map); template void DecodeField(Register reg) { - static const int full_shift = Field::kShift + kSmiShift; - static const int low_mask = Field::kMask >> Field::kShift; - shr(reg, Immediate(full_shift)); - and_(reg, Immediate(low_mask)); + static const int shift = Field::kShift + kSmiShift; + static const int mask = Field::kMask >> Field::kShift; + shr(reg, Immediate(shift)); + and_(reg, Immediate(mask)); + shl(reg, Immediate(kSmiShift)); } // Abort execution if argument is not a number. Used in debug code. diff --git a/test/cctest/test-heap-profiler.cc b/test/cctest/test-heap-profiler.cc index 1004104dd..4f7421be8 100644 --- a/test/cctest/test-heap-profiler.cc +++ b/test/cctest/test-heap-profiler.cc @@ -1670,13 +1670,24 @@ TEST(MapHasDescriptorsAndTransitions) { const v8::HeapGraphNode* global_object = GetProperty(global, v8::HeapGraphEdge::kProperty, "obj"); CHECK_NE(NULL, global_object); + const v8::HeapGraphNode* map = GetProperty(global_object, v8::HeapGraphEdge::kInternal, "map"); CHECK_NE(NULL, map); - const v8::HeapGraphNode* descriptors = - GetProperty(map, v8::HeapGraphEdge::kInternal, "descriptors"); + const v8::HeapGraphNode* own_descriptors = GetProperty( + map, v8::HeapGraphEdge::kInternal, "descriptors"); + CHECK_EQ(NULL, own_descriptors); + const v8::HeapGraphNode* own_transitions = GetProperty( + map, v8::HeapGraphEdge::kInternal, "transitions"); + CHECK_EQ(NULL, own_transitions); + + const v8::HeapGraphNode* back_pointer_map = + GetProperty(map, v8::HeapGraphEdge::kInternal, "backpointer"); + CHECK_NE(NULL, back_pointer_map); + const v8::HeapGraphNode* descriptors = GetProperty( + back_pointer_map, v8::HeapGraphEdge::kInternal, "descriptors"); CHECK_NE(NULL, descriptors); - const v8::HeapGraphNode* transitions = - GetProperty(map, v8::HeapGraphEdge::kInternal, "transitions"); + const v8::HeapGraphNode* transitions = GetProperty( + back_pointer_map, v8::HeapGraphEdge::kInternal, "transitions"); CHECK_NE(NULL, transitions); } -- 2.34.1