Don't overwrite transition array map while iterating over the transition tree.

src/objects.cc

 // Copyright 2013 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
@@ skipping 7224 matching lines @@
 
 
 void Map::RemoveFromCodeCache(Name* name, Code* code, int index) {
   // No GC is supposed to happen between a call to IndexInCodeCache and
   // RemoveFromCodeCache so the code cache must be there.
   ASSERT(!code_cache()->IsFixedArray());
   CodeCache::cast(code_cache())->RemoveByIndex(name, code, index);
 }
 
 
-// An iterator over all map transitions in an descriptor array, reusing the map
-// field of the contens array while it is running.
+// An iterator over all map transitions in an descriptor array, reusing the
+// constructor field of the map while it is running. Negative values in
+// the constructor field indicate an active map transition iteration. The
+// original constructor is restored after iterating over all entries.
 class IntrusiveMapTransitionIterator {
  public:
-  explicit IntrusiveMapTransitionIterator(TransitionArray* transition_array)
-      : transition_array_(transition_array) { }
+  explicit IntrusiveMapTransitionIterator(

[Michael Starzinger, 2014/04/03 13:07:37]

nit: Doesn't need to be "explicit" any longer.

[Hannes Payer (out of office), 2014/04/03 20:01:35]

Done.

+      Map* map, TransitionArray* transition_array, Object* constructor)
+      : map_(map),
+        transition_array_(transition_array),
+        constructor_(constructor) { }
 
-  void Start() {
-    ASSERT(!IsIterating());
-    *TransitionArrayHeader() = Smi::FromInt(0);
+  void StartIfNotStarted() {
+    ASSERT(!(*IteratorField())->IsSmi() || IsIterating());
+    if (!(*IteratorField())->IsSmi()) {
+      *IteratorField() = Smi::FromInt(-1);

[Michael Starzinger, 2014/04/03 13:07:37]

Can we ASSERT(*IteratorField() == constructor_) here before storing the smi?

[Hannes Payer (out of office), 2014/04/03 20:01:35]

Done.

+    }
   }
 
   bool IsIterating() {
-    return (*TransitionArrayHeader())->IsSmi();
+    return (*IteratorField())->IsSmi() &&
+           Smi::cast(*IteratorField())->value() < 0;
   }
 
   Map* Next() {
     ASSERT(IsIterating());
-    int index = Smi::cast(*TransitionArrayHeader())->value();
+    int value = Smi::cast(*IteratorField())->value();
+    int index = (value * -1) - 1;

[Michael Starzinger, 2014/04/03 13:07:37]

nit: Would "-value - 1" be easier to read?

[Hannes Payer (out of office), 2014/04/03 20:01:35]

Done.

     int number_of_transitions = transition_array_->number_of_transitions();
     while (index < number_of_transitions) {
-      *TransitionArrayHeader() = Smi::FromInt(index + 1);
+      *IteratorField() = Smi::FromInt(value - 1);
       return transition_array_->GetTarget(index);
     }
 
-    *TransitionArrayHeader() = transition_array_->GetHeap()->fixed_array_map();
+    *IteratorField() = constructor_;
     return NULL;
   }
 
  private:
-  Object** TransitionArrayHeader() {
-    return HeapObject::RawField(transition_array_, TransitionArray::kMapOffset);
+  Object** IteratorField() {
+    return HeapObject::RawField(map_, Map::kConstructorOffset);
   }
 
+  Map* map_;
   TransitionArray* transition_array_;
+  Object* constructor_;
 };
 
 
-// An iterator over all prototype transitions, reusing the map field of the
-// underlying array while it is running.
+// An iterator over all prototype transitions, reusing the constructor field
+// of map while it is running.  Positive values in the constructor field

[Michael Starzinger, 2014/04/03 13:07:37]

nit: s/of map/of the map/

[Hannes Payer (out of office), 2014/04/03 20:01:35]

Done.

+// indicate an active prototype transition iteration. The original constructor
+// is restored after iterating over all entries.
 class IntrusivePrototypeTransitionIterator {
  public:
-  explicit IntrusivePrototypeTransitionIterator(HeapObject* proto_trans)
-      : proto_trans_(proto_trans) { }
+  explicit IntrusivePrototypeTransitionIterator(

[Michael Starzinger, 2014/04/03 13:07:37]

nit: Doesn't need to be "explicit" any longer.

[Hannes Payer (out of office), 2014/04/03 20:01:35]

Done.

+      Map* map, HeapObject* proto_trans, Object* constructor)
+      : map_(map), proto_trans_(proto_trans), constructor_(constructor) { }
 
   void Start() {
     ASSERT(!IsIterating());
-    *Header() = Smi::FromInt(0);
+    *IteratorField() = Smi::FromInt(0);

[Michael Starzinger, 2014/04/03 13:07:37]

Can we ASSERT(*IteratorField() == constructor_) here before storing the smi?

[Hannes Payer (out of office), 2014/04/03 20:01:35]

Done.

   }
 
   bool IsIterating() {
-    return (*Header())->IsSmi();
+    return (*IteratorField())->IsSmi() &&
+           Smi::cast(*IteratorField())->value() >= 0;
   }
 
   Map* Next() {
     ASSERT(IsIterating());
-    int transitionNumber = Smi::cast(*Header())->value();
+    int transitionNumber = Smi::cast(*IteratorField())->value();
     if (transitionNumber < NumberOfTransitions()) {
-      *Header() = Smi::FromInt(transitionNumber + 1);
+      *IteratorField() = Smi::FromInt(transitionNumber + 1);
       return GetTransition(transitionNumber);
     }
-    *Header() = proto_trans_->GetHeap()->fixed_array_map();
+    *IteratorField() = constructor_;
     return NULL;
   }
 
  private:
-  Object** Header() {
-    return HeapObject::RawField(proto_trans_, FixedArray::kMapOffset);
+  Object** IteratorField() {
+    return HeapObject::RawField(map_, Map::kConstructorOffset);
   }
 
   int NumberOfTransitions() {
     FixedArray* proto_trans = reinterpret_cast<FixedArray*>(proto_trans_);
     Object* num = proto_trans->get(Map::kProtoTransitionNumberOfEntriesOffset);
     return Smi::cast(num)->value();
   }
 
   Map* GetTransition(int transitionNumber) {
     FixedArray* proto_trans = reinterpret_cast<FixedArray*>(proto_trans_);
     return Map::cast(proto_trans->get(IndexFor(transitionNumber)));
   }
 
   int IndexFor(int transitionNumber) {
     return Map::kProtoTransitionHeaderSize +
         Map::kProtoTransitionMapOffset +
         transitionNumber * Map::kProtoTransitionElementsPerEntry;
   }
 
+  Map* map_;
   HeapObject* proto_trans_;
+  Object* constructor_;
 };
 
 
 // To traverse the transition tree iteratively, we have to store two kinds of
 // information in a map: The parent map in the traversal and which children of a
 // node have already been visited. To do this without additional memory, we
-// temporarily reuse two maps with known values:
+// temporarily reuse two fields with known values:
 //
 //  (1) The map of the map temporarily holds the parent, and is restored to the
 //      meta map afterwards.
 //
 //  (2) The info which children have already been visited depends on which part
-//      of the map we currently iterate:
+//      of the map we currently iterate. We use the constructor field of the
+//      map to store the current index. We can do that because the constructor
+//      is the same for all involved maps.
 //
 //    (a) If we currently follow normal map transitions, we temporarily store
-//        the current index in the map of the FixedArray of the desciptor
-//        array's contents, and restore it to the fixed array map afterwards.
-//        Note that a single descriptor can have 0, 1, or 2 transitions.
+//        the current index in the constructor field, and restore it to the
+//        original constructor afterwards. Note that a single descriptor can
+//        have 0, 1, or 2 transitions.
 //
 //    (b) If we currently follow prototype transitions, we temporarily store
-//        the current index in the map of the FixedArray holding the prototype
-//        transitions, and restore it to the fixed array map afterwards.
+//        the current index in the constructor field, and restore it to the
+//        original constructor afterwards.
 //
 // Note that the child iterator is just a concatenation of two iterators: One
 // iterating over map transitions and one iterating over prototype transisitons.
 class TraversableMap : public Map {
  public:
   // Record the parent in the traversal within this map. Note that this destroys
   // this map's map!
   void SetParent(TraversableMap* parent) { set_map_no_write_barrier(parent); }
 
   // Reset the current map's map, returning the parent previously stored in it.
   TraversableMap* GetAndResetParent() {
     TraversableMap* old_parent = static_cast<TraversableMap*>(map());
     set_map_no_write_barrier(GetHeap()->meta_map());
     return old_parent;
   }
 
-  // Start iterating over this map's children, possibly destroying a FixedArray
-  // map (see explanation above).
-  void ChildIteratorStart() {
+  // Start iterating over this map's children, possibly overwritting the
+  // constructor field of the map.
+  void ChildIteratorStart(Object* constructor) {

[Michael Starzinger, 2014/04/03 13:07:37]

It might make it more uniform to to get rid of the explicit ChildIteratorStart()
and do implicit StartOfNotStarted() within ChildIteratorNext() for both of the
sub-iterators. WDYT?

[Hannes Payer (out of office), 2014/04/03 20:01:35]

Done. That is an awesome comment, thanks! Note that it is not completely
symmetric, since I cannot ASSERT(!(*IteratorField())->IsSmi() || IsIterating());
in the IntrusivePrototypeTransitionIterator.

     if (HasTransitionArray()) {
       if (HasPrototypeTransitions()) {
-        IntrusivePrototypeTransitionIterator(GetPrototypeTransitions()).Start();
+        // We start the iterator for prototype transitions here. The map
+        // transition iterator is started in ChildIteratorNext, after finishing
+        // the prototype transitions (if such exist).
+        IntrusivePrototypeTransitionIterator(this,
+                                             GetPrototypeTransitions(),
+                                             constructor).Start();
       }
-
-      IntrusiveMapTransitionIterator(transitions()).Start();
     }
   }
 
   // If we have an unvisited child map, return that one and advance. If we have
-  // none, return NULL and reset any destroyed FixedArray maps.
-  TraversableMap* ChildIteratorNext() {
-    TransitionArray* transition_array = unchecked_transition_array();
-    if (!transition_array->map()->IsSmi() &&
-        !transition_array->IsTransitionArray()) {
-      return NULL;
-    }
+  // none, return NULL and restore the overwritten constructor field.
+  TraversableMap* ChildIteratorNext(Object* constructor) {
+    if (!HasTransitionArray()) return NULL;
 
+    TransitionArray* transition_array = transitions();
     if (transition_array->HasPrototypeTransitions()) {
       HeapObject* proto_transitions =
-          transition_array->UncheckedPrototypeTransitions();
-      IntrusivePrototypeTransitionIterator proto_iterator(proto_transitions);
+          transition_array->GetPrototypeTransitions();
+      IntrusivePrototypeTransitionIterator proto_iterator(this,
+                                                          proto_transitions,
+                                                          constructor);
       if (proto_iterator.IsIterating()) {
         Map* next = proto_iterator.Next();
         if (next != NULL) return static_cast<TraversableMap*>(next);
       }
     }
 
-    IntrusiveMapTransitionIterator transition_iterator(transition_array);
+    IntrusiveMapTransitionIterator transition_iterator(this,
+                                                       transition_array,
+                                                       constructor);
+    transition_iterator.StartIfNotStarted();
     if (transition_iterator.IsIterating()) {
       Map* next = transition_iterator.Next();
       if (next != NULL) return static_cast<TraversableMap*>(next);
     }
 
     return NULL;
   }
 };
 
 
 // Traverse the transition tree in postorder without using the C++ stack by
 // doing pointer reversal.
 void Map::TraverseTransitionTree(TraverseCallback callback, void* data) {
   TraversableMap* current = static_cast<TraversableMap*>(this);
-  current->ChildIteratorStart();
+  // Get the root constructor here to restore it later when finished iterating
+  // over maps.
+  Object* root_constructor = constructor();
+  current->ChildIteratorStart(root_constructor);
   while (true) {
-    TraversableMap* child = current->ChildIteratorNext();
+    TraversableMap* child = current->ChildIteratorNext(root_constructor);
     if (child != NULL) {
-      child->ChildIteratorStart();
+      child->ChildIteratorStart(root_constructor);
       child->SetParent(current);
       current = child;
     } else {
       TraversableMap* parent = current->GetAndResetParent();
       callback(current, data);
       if (current == this) break;
       current = parent;
     }
   }
 }
@@ skipping 9047 matching lines @@
 #define ERROR_MESSAGES_TEXTS(C, T) T,
   static const char* error_messages_[] = {
       ERROR_MESSAGES_LIST(ERROR_MESSAGES_TEXTS)
   };
 #undef ERROR_MESSAGES_TEXTS
   return error_messages_[reason];
 }
 
 
 } }  // namespace v8::internal