Revision: 8165
Author: [email protected]
Date: Fri Jun 3 07:48:09 2011
Log: Fix traversal of the map transition tree to take the prototype
transitions into account.
Review URL: http://codereview.chromium.org/7074052
http://code.google.com/p/v8/source/detail?r=8165
Added:
/branches/bleeding_edge/test/mjsunit/regress/regress-84234.js
Modified:
/branches/bleeding_edge/src/mark-compact.cc
/branches/bleeding_edge/src/objects.cc
/branches/bleeding_edge/src/objects.h
=======================================
--- /dev/null
+++ /branches/bleeding_edge/test/mjsunit/regress/regress-84234.js Fri Jun
3 07:48:09 2011
@@ -0,0 +1,55 @@
+// Copyright 2011 the V8 project authors. All rights reserved.
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are
+// met:
+//
+// * Redistributions of source code must retain the above copyright
+// notice, this list of conditions and the following disclaimer.
+// * Redistributions in binary form must reproduce the above
+// copyright notice, this list of conditions and the following
+// disclaimer in the documentation and/or other materials provided
+// with the distribution.
+// * Neither the name of Google Inc. nor the names of its
+// contributors may be used to endorse or promote products derived
+// from this software without specific prior written permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+// Flags: --expose-gc --noopt
+
+var gTestcases = new Array();
+
+function TestCase(n, d, e, a) {
+ gTestcases[gTc++] = this;
+ for ( gTc=0; gTc < gTestcases.length; gTc++ );
+}
+
+for ( var i = 0x0530; i <= 0x058F; i++ ) {
+ new TestCase("15.5.4.11-6",
+ eval("var s = new String(String.fromCharCode(i));
s.toLowerCase().charCodeAt(0)"));
+}
+var gTc= 0;
+
+
+for (var j = 0; j < 10; j++) {
+ test();
+ function test() {
+ for ( 0; gTc < gTestcases.length; gTc++ ) {
+ var MYOBJECT = new MyObject();
+ }
+ gc();
+ }
+ function MyObject( n ) {
+ this.__proto__ = Number.prototype;
+ }
+}
=======================================
--- /branches/bleeding_edge/src/mark-compact.cc Tue May 31 09:38:40 2011
+++ /branches/bleeding_edge/src/mark-compact.cc Fri Jun 3 07:48:09 2011
@@ -1535,38 +1535,45 @@
}
// Clear dead prototype transitions.
+ int number_of_transitions = map->NumberOfProtoTransitions();
FixedArray* prototype_transitions =
map->unchecked_prototype_transitions();
- if (prototype_transitions->length() > 0) {
- int finger = Smi::cast(prototype_transitions->get(0))->value();
- int new_finger = 1;
- for (int i = 1; i < finger; i += 2) {
- Object* prototype = prototype_transitions->get(i);
- Object* cached_map = prototype_transitions->get(i + 1);
- if (HeapObject::cast(prototype)->IsMarked() &&
- HeapObject::cast(cached_map)->IsMarked()) {
- if (new_finger != i) {
- prototype_transitions->set_unchecked(heap_,
- new_finger,
- prototype,
- UPDATE_WRITE_BARRIER);
- prototype_transitions->set_unchecked(heap_,
- new_finger + 1,
- cached_map,
- SKIP_WRITE_BARRIER);
- }
- new_finger += 2;
- }
+ int new_number_of_transitions = 0;
+ const int header = Map::kProtoTransitionHeaderSize;
+ const int proto_offset =
+ header + Map::kProtoTransitionPrototypeOffset;
+ const int map_offset = header + Map::kProtoTransitionMapOffset;
+ const int step = Map::kProtoTransitionElementsPerEntry;
+ for (int i = 0; i < number_of_transitions; i++) {
+ Object* prototype = prototype_transitions->get(proto_offset + i *
step);
+ Object* cached_map = prototype_transitions->get(map_offset + i *
step);
+ if (HeapObject::cast(prototype)->IsMarked() &&
+ HeapObject::cast(cached_map)->IsMarked()) {
+ if (new_number_of_transitions != i) {
+ prototype_transitions->set_unchecked(
+ heap_,
+ proto_offset + new_number_of_transitions * step,
+ prototype,
+ UPDATE_WRITE_BARRIER);
+ prototype_transitions->set_unchecked(
+ heap_,
+ map_offset + new_number_of_transitions * step,
+ cached_map,
+ SKIP_WRITE_BARRIER);
+ }
+ new_number_of_transitions++;
}
// Fill slots that became free with undefined value.
Object* undefined = heap()->raw_unchecked_undefined_value();
- for (int i = new_finger; i < finger; i++) {
+ for (int i = new_number_of_transitions * step;
+ i < number_of_transitions * step;
+ i++) {
prototype_transitions->set_unchecked(heap_,
- i,
+ header + i,
undefined,
SKIP_WRITE_BARRIER);
}
- prototype_transitions->set_unchecked(0, Smi::FromInt(new_finger));
+ map->SetNumberOfProtoTransitions(new_number_of_transitions);
}
// Follow the chain of back pointers to find the prototype.
=======================================
--- /branches/bleeding_edge/src/objects.cc Fri Jun 3 03:15:49 2011
+++ /branches/bleeding_edge/src/objects.cc Fri Jun 3 07:48:09 2011
@@ -3928,39 +3928,68 @@
void Map::TraverseTransitionTree(TraverseCallback callback, void* data) {
+ // Traverse the transition tree without using a stack. We do this by
+ // reversing the pointers in the maps and descriptor arrays.
Map* current = this;
Map* meta_map = heap()->meta_map();
+ Object** map_or_index_field = NULL;
while (current != meta_map) {
DescriptorArray* d = reinterpret_cast<DescriptorArray*>(
*RawField(current, Map::kInstanceDescriptorsOrBitField3Offset));
- if (d->IsEmpty()) {
- Map* prev = current->map();
- current->set_map(meta_map);
- callback(current, data);
- current = prev;
- continue;
- }
-
- FixedArray* contents = reinterpret_cast<FixedArray*>(
- d->get(DescriptorArray::kContentArrayIndex));
- Object** map_or_index_field = RawField(contents,
HeapObject::kMapOffset);
- Object* map_or_index = *map_or_index_field;
- bool map_done = true;
- for (int i = map_or_index->IsSmi() ?
Smi::cast(map_or_index)->value() : 0;
- i < contents->length();
- i += 2) {
- PropertyDetails details(Smi::cast(contents->get(i + 1)));
- if (details.IsTransition()) {
- Map* next = reinterpret_cast<Map*>(contents->get(i));
+ if (!d->IsEmpty()) {
+ FixedArray* contents = reinterpret_cast<FixedArray*>(
+ d->get(DescriptorArray::kContentArrayIndex));
+ map_or_index_field = RawField(contents, HeapObject::kMapOffset);
+ Object* map_or_index = *map_or_index_field;
+ bool map_done = true; // Controls a nested continue statement.
+ for (int i = map_or_index->IsSmi() ?
Smi::cast(map_or_index)->value() : 0;
+ i < contents->length();
+ i += 2) {
+ PropertyDetails details(Smi::cast(contents->get(i + 1)));
+ if (details.IsTransition()) {
+ // Found a map in the transition array. We record our progress
in
+ // the transition array by recording the current map in the map
field
+ // of the next map and recording the index in the transition
array in
+ // the map field of the array.
+ Map* next = Map::cast(contents->get(i));
+ next->set_map(current);
+ *map_or_index_field = Smi::FromInt(i + 2);
+ current = next;
+ map_done = false;
+ break;
+ }
+ }
+ if (!map_done) continue;
+ }
+ // That was the regular transitions, now for the prototype transitions.
+ FixedArray* prototype_transitions =
+ current->unchecked_prototype_transitions();
+ Object** proto_map_or_index_field =
+ RawField(prototype_transitions, HeapObject::kMapOffset);
+ Object* map_or_index = *proto_map_or_index_field;
+ const int start = kProtoTransitionHeaderSize +
kProtoTransitionMapOffset;
+ int i = map_or_index->IsSmi() ? Smi::cast(map_or_index)->value() :
start;
+ if (i < prototype_transitions->length()) {
+ // Found a map in the prototype transition array. Record progress in
+ // an analogous way to the regular transitions array above.
+ Object* perhaps_map = prototype_transitions->get(i);
+ if (perhaps_map->IsMap()) {
+ Map* next = Map::cast(perhaps_map);
next->set_map(current);
- *map_or_index_field = Smi::FromInt(i + 2);
+ *proto_map_or_index_field =
+ Smi::FromInt(i + kProtoTransitionElementsPerEntry);
current = next;
- map_done = false;
- break;
+ continue;
}
}
- if (!map_done) continue;
- *map_or_index_field = heap()->fixed_array_map();
+ *proto_map_or_index_field = heap()->fixed_array_map();
+ if (map_or_index_field != NULL) {
+ *map_or_index_field = heap()->fixed_array_map();
+ }
+
+ // The callback expects a map to have a real map as its map, so we save
+ // the map field, which is being used to track the traversal and put
the
+ // correct map (the meta_map) in place while we do the callback.
Map* prev = current->map();
current->set_map(meta_map);
callback(current, data);
@@ -6398,6 +6427,7 @@
if (slack != 0) {
// Resize the initial map and all maps in its transition tree.
map->TraverseTransitionTree(&ShrinkInstanceSize, &slack);
+
// Give the correct expected_nof_properties to initial maps created
later.
ASSERT(expected_nof_properties() >= slack);
set_expected_nof_properties(expected_nof_properties() - slack);
@@ -7117,42 +7147,59 @@
Object* Map::GetPrototypeTransition(Object* prototype) {
FixedArray* cache = prototype_transitions();
- int capacity = cache->length();
- if (capacity == 0) return NULL;
- int finger = Smi::cast(cache->get(0))->value();
- for (int i = 1; i < finger; i += 2) {
- if (cache->get(i) == prototype) return cache->get(i + 1);
+ int number_of_transitions = NumberOfProtoTransitions();
+ const int proto_offset =
+ kProtoTransitionHeaderSize + kProtoTransitionPrototypeOffset;
+ const int map_offset = kProtoTransitionHeaderSize +
kProtoTransitionMapOffset;
+ const int step = kProtoTransitionElementsPerEntry;
+ for (int i = 0; i < number_of_transitions; i++) {
+ if (cache->get(proto_offset + i * step) == prototype) {
+ Object* map = cache->get(map_offset + i * step);
+ ASSERT(map->IsMap());
+ return map;
+ }
}
return NULL;
}
MaybeObject* Map::PutPrototypeTransition(Object* prototype, Map* map) {
+ ASSERT(map->IsMap());
+ ASSERT(HeapObject::cast(prototype)->map()->IsMap());
// Don't cache prototype transition if this map is shared.
if (is_shared() || !FLAG_cache_prototype_transitions) return this;
FixedArray* cache = prototype_transitions();
- int capacity = cache->length();
-
- int finger = (capacity == 0) ? 1 : Smi::cast(cache->get(0))->value();
-
- if (finger >= capacity) {
+ const int step = kProtoTransitionElementsPerEntry;
+ const int header = kProtoTransitionHeaderSize;
+
+ int capacity = (cache->length() - header) / step;
+
+ int transitions = NumberOfProtoTransitions() + 1;
+
+ if (transitions > capacity) {
if (capacity > kMaxCachedPrototypeTransitions) return this;
FixedArray* new_cache;
- { MaybeObject* maybe_cache = heap()->AllocateFixedArray(finger * 2 +
1);
+ // Grow array by factor 2 over and above what we need.
+ { MaybeObject* maybe_cache =
+ heap()->AllocateFixedArray(transitions * 2 * step + header);
if (!maybe_cache->To<FixedArray>(&new_cache)) return maybe_cache;
}
- for (int i = 1; i < capacity; i++) new_cache->set(i, cache->get(i));
+ for (int i = 0; i < capacity * step; i++) {
+ new_cache->set(i + header, cache->get(i + header));
+ }
cache = new_cache;
set_prototype_transitions(cache);
}
- cache->set(finger, prototype);
- cache->set(finger + 1, map);
- cache->set(0, Smi::FromInt(finger + 2));
+ int last = transitions - 1;
+
+ cache->set(header + last * step + kProtoTransitionPrototypeOffset,
prototype);
+ cache->set(header + last * step + kProtoTransitionMapOffset, map);
+ SetNumberOfProtoTransitions(transitions);
return cache;
}
@@ -7160,6 +7207,10 @@
MaybeObject* JSReceiver::SetPrototype(Object* value,
bool skip_hidden_prototypes) {
+#ifdef DEBUG
+ int size = Size();
+#endif
+
Heap* heap = GetHeap();
// Silently ignore the change if value is not a JSObject or null.
// SpiderMonkey behaves this way.
@@ -7230,7 +7281,7 @@
real_receiver->set_map(Map::cast(new_map));
heap->ClearInstanceofCache();
-
+ ASSERT(size == Size());
return value;
}
=======================================
--- /branches/bleeding_edge/src/objects.h Fri Jun 3 00:41:37 2011
+++ /branches/bleeding_edge/src/objects.h Fri Jun 3 07:48:09 2011
@@ -3867,6 +3867,26 @@
// 2 + 2 * i: target map
DECL_ACCESSORS(prototype_transitions, FixedArray)
inline FixedArray* unchecked_prototype_transitions();
+
+ static const int kProtoTransitionHeaderSize = 1;
+ static const int kProtoTransitionNumberOfEntriesOffset = 0;
+ static const int kProtoTransitionElementsPerEntry = 2;
+ static const int kProtoTransitionPrototypeOffset = 0;
+ static const int kProtoTransitionMapOffset = 1;
+
+ inline int NumberOfProtoTransitions() {
+ FixedArray* cache = unchecked_prototype_transitions();
+ if (cache->length() == 0) return 0;
+ return
+
Smi::cast(cache->get(kProtoTransitionNumberOfEntriesOffset))->value();
+ }
+
+ inline void SetNumberOfProtoTransitions(int value) {
+ FixedArray* cache = unchecked_prototype_transitions();
+ ASSERT(cache->length() != 0);
+ cache->set_unchecked(kProtoTransitionNumberOfEntriesOffset,
+ Smi::FromInt(value));
+ }
// Lookup in the map's instance descriptors and fill out the result
// with the given holder if the name is found. The holder may be
--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
