Merging ContentArray into DescriptorArray

src/objects.cc

 // Copyright 2012 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 4871 matching lines @@
 
 // An iterator over all map transitions in an descriptor array, reusing the map
 // field of the contens array while it is running.
 class IntrusiveMapTransitionIterator {
  public:
   explicit IntrusiveMapTransitionIterator(DescriptorArray* descriptor_array)
       : descriptor_array_(descriptor_array) { }
 
   void Start() {
     ASSERT(!IsIterating());
-    if (HasContentArray()) *ContentHeader() = Smi::FromInt(0);
+    if (HasDescriptors()) *DescriptorArrayHeader() = Smi::FromInt(0);
   }
 
   bool IsIterating() {
-    return HasContentArray() && (*ContentHeader())->IsSmi();
+    return HasDescriptors() && (*DescriptorArrayHeader())->IsSmi();
   }
 
   Map* Next() {
     ASSERT(IsIterating());
-    FixedArray* contents = ContentArray();
-    // Attention, tricky index manipulation ahead: Every entry in the contents
-    // array consists of a value/details pair, so the index is typically even.
-    // An exception is made for CALLBACKS entries: An even index means we look
-    // at its getter, and an odd index means we look at its setter.
-    int index = Smi::cast(*ContentHeader())->value();
-    while (index < contents->length()) {
-      PropertyDetails details(Smi::cast(contents->get(index | 1)));
+    // Attention, tricky index manipulation ahead: Two two consecutive indices
+    // are assigned to each descriptor. Most descriptors directly advance to the
+    // next descriptor by adding 2 to the index. The exceptions are the
+    // CALLBACKS entries: An even index means we look at its getter, and an odd
+    // index means we look at its setter.
+    int index = Smi::cast(*DescriptorArrayHeader())->value();
+    while ((index / 2) < descriptor_array_->number_of_descriptors()) {
+      PropertyDetails details(descriptor_array_->GetDetails(index / 2));
       switch (details.type()) {
         case MAP_TRANSITION:
         case CONSTANT_TRANSITION:
         case ELEMENTS_TRANSITION:
           // We definitely have a map transition.
-          *ContentHeader() = Smi::FromInt(index + 2);
-          return static_cast<Map*>(contents->get(index));
+          *DescriptorArrayHeader() = Smi::FromInt(index + 2);
+          return static_cast<Map*>(descriptor_array_->GetValue(index / 2));
         case CALLBACKS: {
           // We might have a map transition in a getter or in a setter.
           AccessorPair* accessors =
-              static_cast<AccessorPair*>(contents->get(index & ~1));
+              static_cast<AccessorPair*>(descriptor_array_->GetValue(index / 2));

[Florian Schneider, 2012/05/22 16:53:09]

Long line.

           Object* accessor =
               ((index & 1) == 0) ? accessors->getter() : accessors->setter();
           index++;
           if (accessor->IsMap()) {
-            *ContentHeader() = Smi::FromInt(index);
+            *DescriptorArrayHeader() = Smi::FromInt(index);
             return static_cast<Map*>(accessor);
           }
           break;
         }
         case NORMAL:
         case FIELD:
         case CONSTANT_FUNCTION:
         case HANDLER:
         case INTERCEPTOR:
         case NULL_DESCRIPTOR:
           // We definitely have no map transition.
           index += 2;
           break;
       }
     }
-    *ContentHeader() = descriptor_array_->GetHeap()->fixed_array_map();
+    *DescriptorArrayHeader() = descriptor_array_->GetHeap()->fixed_array_map();
     return NULL;
   }
 
  private:
-  bool HasContentArray() {
-    return descriptor_array_-> length() > DescriptorArray::kContentArrayIndex;
+  bool HasDescriptors() {
+    return !descriptor_array_->IsEmpty();
   }
 
-  FixedArray* ContentArray() {
-    Object* array = descriptor_array_->get(DescriptorArray::kContentArrayIndex);
-    return static_cast<FixedArray*>(array);
-  }
-
-  Object** ContentHeader() {
-    return HeapObject::RawField(ContentArray(), DescriptorArray::kMapOffset);
+  Object** DescriptorArrayHeader() {
+    return HeapObject::RawField(descriptor_array_, DescriptorArray::kMapOffset);
   }
 
   DescriptorArray* descriptor_array_;
 };
 
 
 // An iterator over all prototype transitions, reusing the map field of the
 // underlying array while it is running.
 class IntrusivePrototypeTransitionIterator {
  public:
@@ skipping 80 matching lines @@
   // 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;
   }
 
+  // Can either be Smi (no instance descriptors), or a descriptor array with the
+  // header overwritten as a Smi (thus iterating).
+  DescriptorArray* MutatedInstanceDescriptors() {
+    Object* object = *HeapObject::RawField(this, kInstanceDescriptorsOrBitField3Offset);

[Florian Schneider, 2012/05/22 16:53:09]

Long line.

+    if (object->IsSmi()) {
+      return GetHeap()->empty_descriptor_array();
+    } else {
+      DescriptorArray* descriptor_array = static_cast<DescriptorArray*>(object);
+      ASSERT((*HeapObject::RawField(descriptor_array,
+                                    DescriptorArray::kMapOffset))->IsSmi());
+      return descriptor_array;
+    }
+  }
+
   // Start iterating over this map's children, possibly destroying a FixedArray
   // map (see explanation above).
   void ChildIteratorStart() {
     IntrusiveMapTransitionIterator(instance_descriptors()).Start();
     IntrusivePrototypeTransitionIterator(
         unchecked_prototype_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() {
-    IntrusiveMapTransitionIterator descriptor_iterator(instance_descriptors());
-    if (descriptor_iterator.IsIterating()) {
-      Map* next = descriptor_iterator.Next();
-      if (next != NULL) return static_cast<TraversableMap*>(next);
-    }
     IntrusivePrototypeTransitionIterator
         proto_iterator(unchecked_prototype_transitions());
     if (proto_iterator.IsIterating()) {
       Map* next = proto_iterator.Next();
       if (next != NULL) return static_cast<TraversableMap*>(next);
     }
+    IntrusiveMapTransitionIterator descriptor_iterator(MutatedInstanceDescriptors());

[Florian Schneider, 2012/05/22 16:53:09]

Long line.

+    if (descriptor_iterator.IsIterating()) {
+      Map* next = descriptor_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();
@@ skipping 543 matching lines @@
   }
   // Allocate the array of keys.
   Object* array;
   { MaybeObject* maybe_array =
         heap->AllocateFixedArray(ToKeyIndex(number_of_descriptors));
     if (!maybe_array->ToObject(&array)) return maybe_array;
   }
   // Do not use DescriptorArray::cast on incomplete object.
   FixedArray* result = FixedArray::cast(array);
 
-  // Allocate the content array and set it in the descriptor array.
-  { MaybeObject* maybe_array =
-        heap->AllocateFixedArray(number_of_descriptors << 1);
-    if (!maybe_array->ToObject(&array)) return maybe_array;
-  }
   result->set(kBitField3StorageIndex, Smi::FromInt(0));
-  result->set(kContentArrayIndex, array);
   result->set(kEnumerationIndexIndex,
               Smi::FromInt(PropertyDetails::kInitialIndex));
   return result;
 }
 
 
 void DescriptorArray::SetEnumCache(FixedArray* bridge_storage,
                                    FixedArray* new_cache,
                                    Object* new_index_cache) {
   ASSERT(bridge_storage->length() >= kEnumCacheBridgeLength);
@@ skipping 164 matching lines @@
       MaybeObject* copy_result =
           new_descriptors->CopyFrom(next_descriptor++, this, i, witness);
       if (copy_result->IsFailure()) return copy_result;
     }
   }
   ASSERT(next_descriptor == new_descriptors->number_of_descriptors());
 
   return new_descriptors;
 }
 
-
+// The whiteness witness is needed since sort will reshuffle the entries in the
+// descriptor array. If the descriptor array were to be gray, the sort would
+// potentially swap a black and a white member. This would result in
+// accidentally reclaiming the white member if the descriptor array owned the
+// unique pointer.
 void DescriptorArray::SortUnchecked(const WhitenessWitness& witness) {
   // In-place heap sort.
   int len = number_of_descriptors();
 
   // Bottom-up max-heap construction.
   // Index of the last node with children
   const int max_parent_index = (len / 2) - 1;
   for (int i = max_parent_index; i >= 0; --i) {
     int parent_index = i;
     const uint32_t parent_hash = GetKey(i)->Hash();
@@ skipping 124 matching lines @@
                                   pretenure);
 }
 
 
 #ifdef DEBUG
 bool DescriptorArray::IsEqualTo(DescriptorArray* other) {
   if (IsEmpty()) return other->IsEmpty();
   if (other->IsEmpty()) return false;
   if (length() != other->length()) return false;
   for (int i = 0; i < length(); ++i) {
-    if (get(i) != other->get(i) && i != kContentArrayIndex) return false;
+    if (get(i) != other->get(i)) return false;
   }
-  return GetContentArray()->IsEqualTo(other->GetContentArray());
+  return true;
 }
 #endif
 
 
 bool String::LooksValid() {
   if (!Isolate::Current()->heap()->Contains(this)) return false;
   return true;
 }
 
 
@@ skipping 1201 matching lines @@
   }
 }
 
 
 void Map::ClearNonLiveTransitions(Heap* heap) {
   DescriptorArray* d = DescriptorArray::cast(
       *RawField(this, Map::kInstanceDescriptorsOrBitField3Offset));
   if (d->IsEmpty()) return;
   Smi* NullDescriptorDetails =
     PropertyDetails(NONE, NULL_DESCRIPTOR).AsSmi();
-  FixedArray* contents = FixedArray::cast(
-      d->get(DescriptorArray::kContentArrayIndex));
-  ASSERT(contents->length() >= 2);
-  for (int i = 0; i < contents->length(); i += 2) {
+  for (int i = 0; i < d->number_of_descriptors(); ++i) {
     // If the pair (value, details) is a map transition, check if the target is
     // live. If not, null the descriptor. Also drop the back pointer for that
     // map transition, so that this map is not reached again by following a back
     // pointer from that non-live map.
     bool keep_entry = false;
-    PropertyDetails details(Smi::cast(contents->get(i + 1)));
+    PropertyDetails details(d->GetDetails(i));
     switch (details.type()) {
       case MAP_TRANSITION:
       case CONSTANT_TRANSITION:
-        ClearBackPointer(heap, contents->get(i), &keep_entry);
+        ClearBackPointer(heap, d->GetValue(i), &keep_entry);
         break;
       case ELEMENTS_TRANSITION: {
-        Object* object = contents->get(i);
+        Object* object = d->GetValue(i);
         if (object->IsMap()) {
           ClearBackPointer(heap, object, &keep_entry);
         } else {
           FixedArray* array = FixedArray::cast(object);
           for (int j = 0; j < array->length(); ++j) {
             if (ClearBackPointer(heap, array->get(j), &keep_entry)) {
               array->set_undefined(j);
             }
           }
         }
         break;
       }
       case CALLBACKS: {
-        Object* object = contents->get(i);
+        Object* object = d->GetValue(i);
         if (object->IsAccessorPair()) {
           AccessorPair* accessors = AccessorPair::cast(object);
           if (ClearBackPointer(heap, accessors->getter(), &keep_entry)) {
             accessors->set_getter(heap->the_hole_value());
           }
           if (ClearBackPointer(heap, accessors->setter(), &keep_entry)) {
             accessors->set_setter(heap->the_hole_value());
           }
         } else {
           keep_entry = true;
         }
         break;
       }
       case NORMAL:
       case FIELD:
       case CONSTANT_FUNCTION:
       case HANDLER:
       case INTERCEPTOR:
       case NULL_DESCRIPTOR:
         keep_entry = true;
         break;
     }
     // Make sure that an entry containing only dead transitions gets collected.
     // What we *really* want to do here is removing this entry completely, but
     // for technical reasons we can't do this, so we zero it out instead.
     if (!keep_entry) {
-      contents->set_unchecked(i + 1, NullDescriptorDetails);
-      contents->set_null_unchecked(heap, i);
+      d->SetDetailsUnchecked(i, NullDescriptorDetails);
+      d->SetNullValueUnchecked(i, heap);
     }
   }
 }
 
 
 int Map::Hash() {
   // For performance reasons we only hash the 3 most variable fields of a map:
   // constructor, prototype and bit_field2.
 
   // Shift away the tag.
@@ skipping 5661 matching lines @@
   set_year(Smi::FromInt(year), SKIP_WRITE_BARRIER);
   set_month(Smi::FromInt(month), SKIP_WRITE_BARRIER);
   set_day(Smi::FromInt(day), SKIP_WRITE_BARRIER);
   set_weekday(Smi::FromInt(weekday), SKIP_WRITE_BARRIER);
   set_hour(Smi::FromInt(hour), SKIP_WRITE_BARRIER);
   set_min(Smi::FromInt(min), SKIP_WRITE_BARRIER);
   set_sec(Smi::FromInt(sec), SKIP_WRITE_BARRIER);
 }
 
 } }  // namespace v8::internal