Use hash map to look for objects in the root array when serializing.

src/serialize.cc

Index: src/serialize.cc
diff --git a/src/serialize.cc b/src/serialize.cc
index 5e6de03f63dd53ab4be51f08908084b0b309e3b8..c9e656637385a9f8f9e62560d70093646b04b60e 100644
--- a/src/serialize.cc
+++ b/src/serialize.cc
@@ -481,6 +481,25 @@ ExternalReferenceDecoder::~ExternalReferenceDecoder() {
 }
 
 
+RootIndexMap::RootIndexMap(Isolate* isolate) {
+  map_ = new HashMap(HashMap::PointersMatch);
+  Object** root_array = isolate->heap()->roots_array_start();
+  for (int i = 0; i < Heap::kStrongRootListLength; i++) {
+    Object* root = root_array[i];
+    if (root->IsHeapObject() && !isolate->heap()->InNewSpace(root)) {
+      HeapObject* heap_object = HeapObject::cast(root);
+      if (LookupEntry(map_, heap_object, false) != NULL) {
+        // Some root values are initialized to the empty FixedArray();
+        // Do not add them to the map.
+        DCHECK_EQ(isolate->heap()->empty_fixed_array(), heap_object);
+      } else {
+        SetValue(LookupEntry(map_, heap_object, true), i);
+      }
+    }
+  }
+}
+
+
 class CodeAddressMap: public CodeEventLogger {
  public:
   explicit CodeAddressMap(Isolate* isolate)
@@ -1237,7 +1256,7 @@ Serializer::Serializer(Isolate* isolate, SnapshotByteSink* sink)
     : isolate_(isolate),
       sink_(sink),
       external_reference_encoder_(new ExternalReferenceEncoder(isolate)),
-      root_index_wave_front_(0),
+      root_index_map_(isolate),
       code_address_map_(NULL),
       seen_large_objects_index_(0) {
   // The serializer is meant to be used only to generate initial heap images
@@ -1267,6 +1286,27 @@ void StartupSerializer::SerializeStrongReferences() {
 }
 
 
+void StartupSerializer::VisitPointers(Object** start, Object** end) {
+  for (Object** current = start; current < end; current++) {
+    if (start == isolate()->heap()->roots_array_start()) {
+      root_index_wave_front_ =
+          Max(root_index_wave_front_, static_cast<intptr_t>(current - start));
+    }
+    if (ShouldBeSkipped(current)) {
+      sink_->Put(kSkip, "Skip");
+      sink_->PutInt(kPointerSize, "SkipOneWord");
+    } else if ((*current)->IsSmi()) {
+      sink_->Put(kRawData + 1, "Smi");
+      for (int i = 0; i < kPointerSize; i++) {
+        sink_->Put(reinterpret_cast<byte*>(current)[i], "Byte");
+      }
+    } else {
+      SerializeObject(HeapObject::cast(*current), kPlain, kStartOfObject, 0);
+    }
+  }
+}
+
+
 void PartialSerializer::Serialize(Object** object) {
   this->VisitPointer(object);
   Pad();
@@ -1282,23 +1322,14 @@ bool Serializer::ShouldBeSkipped(Object** current) {
 
 
 void Serializer::VisitPointers(Object** start, Object** end) {
-  Isolate* isolate = this->isolate();;
-
   for (Object** current = start; current < end; current++) {
-    if (start == isolate->heap()->roots_array_start()) {
-      root_index_wave_front_ =
-          Max(root_index_wave_front_, static_cast<intptr_t>(current - start));
-    }
-    if (ShouldBeSkipped(current)) {
-      sink_->Put(kSkip, "Skip");
-      sink_->PutInt(kPointerSize, "SkipOneWord");
-    } else if ((*current)->IsSmi()) {
+    if ((*current)->IsSmi()) {
       sink_->Put(kRawData + 1, "Smi");
       for (int i = 0; i < kPointerSize; i++) {
         sink_->Put(reinterpret_cast<byte*>(current)[i], "Byte");
       }
     } else {
-      SerializeObject(*current, kPlain, kStartOfObject, 0);
+      SerializeObject(HeapObject::cast(*current), kPlain, kStartOfObject, 0);
     }
   }
 }
@@ -1368,29 +1399,14 @@ int PartialSerializer::PartialSnapshotCacheIndex(HeapObject* heap_object) {
 }
 
 
-int Serializer::RootIndex(HeapObject* heap_object, HowToCode from) {
-  Heap* heap = isolate()->heap();
-  if (heap->InNewSpace(heap_object)) return kInvalidRootIndex;
-  for (int i = 0; i < root_index_wave_front_; i++) {
-    Object* root = heap->roots_array_start()[i];
-    if (!root->IsSmi() && root == heap_object) {
-      return i;
-    }
-  }
-  return kInvalidRootIndex;
-}
-
-
 // Encode the location of an already deserialized object in order to write its
 // location into a later object.  We can encode the location as an offset from
 // the start of the deserialized objects or as an offset backwards from the
 // current allocation pointer.
-void Serializer::SerializeReferenceToPreviousObject(HeapObject* heap_object,
-                                                    HowToCode how_to_code,
-                                                    WhereToPoint where_to_point,
-                                                    int skip) {
-  int space = SpaceOfObject(heap_object);
-
+void Serializer::SerializeBackReference(BackReference back_reference,
+                                        HowToCode how_to_code,
+                                        WhereToPoint where_to_point, int skip) {
+  AllocationSpace space = back_reference.space();
   if (skip == 0) {
     sink_->Put(kBackref + how_to_code + where_to_point + space, "BackRefSer");
   } else {
@@ -1399,50 +1415,39 @@ void Serializer::SerializeReferenceToPreviousObject(HeapObject* heap_object,
     sink_->PutInt(skip, "BackRefSkipDistance");
   }
 
-  if (space == LO_SPACE) {
-    int index = address_mapper_.MappedTo(heap_object);
-    sink_->PutInt(index, "large object index");
-  } else {
-    uint32_t existing_allocation = address_mapper_.MappedTo(heap_object);
-    // Shift out the bits that are always 0.
-    existing_allocation >>= kObjectAlignmentBits;
-    sink_->PutInt(existing_allocation, "allocation");
-  }
+  sink_->PutInt(back_reference.reference(),
+                (space == LO_SPACE) ? "large object index" : "allocation");
 }
 
 
-void StartupSerializer::SerializeObject(
-    Object* o,
-    HowToCode how_to_code,
-    WhereToPoint where_to_point,
-    int skip) {
-  CHECK(o->IsHeapObject());
-  HeapObject* heap_object = HeapObject::cast(o);
-  DCHECK(!heap_object->IsJSFunction());
+void StartupSerializer::SerializeObject(HeapObject* obj, HowToCode how_to_code,
+                                        WhereToPoint where_to_point, int skip) {
+  DCHECK(!obj->IsJSFunction());
 
-  int root_index;
-  if ((root_index = RootIndex(heap_object, how_to_code)) != kInvalidRootIndex) {
-    PutRoot(root_index, heap_object, how_to_code, where_to_point, skip);
+  int root_index = root_index_map_.Lookup(obj);
+  // We can only encode roots as such if it has already been serialized.
+  // That applies to root indices below the wave front.
+  if (root_index != RootIndexMap::kInvalidRootIndex &&
+      root_index < root_index_wave_front_) {
+    PutRoot(root_index, obj, how_to_code, where_to_point, skip);
     return;
   }
 
-  if (address_mapper_.IsMapped(heap_object)) {
-    SerializeReferenceToPreviousObject(heap_object, how_to_code, where_to_point,
-                                       skip);
-  } else {
-    if (skip != 0) {
-      sink_->Put(kSkip, "FlushPendingSkip");
-      sink_->PutInt(skip, "SkipDistance");
-    }
+  BackReference back_reference = back_reference_map_.Lookup(obj);
+  if (back_reference.is_valid()) {
+    SerializeBackReference(back_reference, how_to_code, where_to_point, skip);
+    return;
+  }
 
-    // Object has not yet been serialized.  Serialize it here.
-    ObjectSerializer object_serializer(this,
-                                       heap_object,
-                                       sink_,
-                                       how_to_code,
-                                       where_to_point);
-    object_serializer.Serialize();
+  if (skip != 0) {
+    sink_->Put(kSkip, "FlushPendingSkip");
+    sink_->PutInt(skip, "SkipDistance");
   }
+
+  // Object has not yet been serialized.  Serialize it here.
+  ObjectSerializer object_serializer(this, obj, sink_, how_to_code,
+                                     where_to_point);
+  object_serializer.Serialize();
 }
 
 
@@ -1487,34 +1492,27 @@ void Serializer::PutRoot(int root_index,
 }
 
 
-void PartialSerializer::SerializeObject(
-    Object* o,
-    HowToCode how_to_code,
-    WhereToPoint where_to_point,
-    int skip) {
-  CHECK(o->IsHeapObject());
-  HeapObject* heap_object = HeapObject::cast(o);
-
-  if (heap_object->IsMap()) {
+void PartialSerializer::SerializeObject(HeapObject* obj, HowToCode how_to_code,
+                                        WhereToPoint where_to_point, int skip) {
+  if (obj->IsMap()) {
     // The code-caches link to context-specific code objects, which
     // the startup and context serializes cannot currently handle.
-    DCHECK(Map::cast(heap_object)->code_cache() ==
-           heap_object->GetHeap()->empty_fixed_array());
+    DCHECK(Map::cast(obj)->code_cache() == obj->GetHeap()->empty_fixed_array());
   }
 
-  int root_index;
-  if ((root_index = RootIndex(heap_object, how_to_code)) != kInvalidRootIndex) {
-    PutRoot(root_index, heap_object, how_to_code, where_to_point, skip);
+  int root_index = root_index_map_.Lookup(obj);
+  if (root_index != RootIndexMap::kInvalidRootIndex) {
+    PutRoot(root_index, obj, how_to_code, where_to_point, skip);
     return;
   }
 
-  if (ShouldBeInThePartialSnapshotCache(heap_object)) {
+  if (ShouldBeInThePartialSnapshotCache(obj)) {
     if (skip != 0) {
       sink_->Put(kSkip, "SkipFromSerializeObject");
       sink_->PutInt(skip, "SkipDistanceFromSerializeObject");
     }
 
-    int cache_index = PartialSnapshotCacheIndex(heap_object);
+    int cache_index = PartialSnapshotCacheIndex(obj);
     sink_->Put(kPartialSnapshotCache + how_to_code + where_to_point,
                "PartialSnapshotCache");
     sink_->PutInt(cache_index, "partial_snapshot_cache_index");
@@ -1524,32 +1522,29 @@ void PartialSerializer::SerializeObject(
   // Pointers from the partial snapshot to the objects in the startup snapshot
   // should go through the root array or through the partial snapshot cache.
   // If this is not the case you may have to add something to the root array.
-  DCHECK(!startup_serializer_->address_mapper()->IsMapped(heap_object));
+  DCHECK(!startup_serializer_->back_reference_map()->Lookup(obj).is_valid());
   // All the internalized strings that the partial snapshot needs should be
   // either in the root table or in the partial snapshot cache.
-  DCHECK(!heap_object->IsInternalizedString());
+  DCHECK(!obj->IsInternalizedString());
 
-  if (address_mapper_.IsMapped(heap_object)) {
-    SerializeReferenceToPreviousObject(heap_object, how_to_code, where_to_point,
-                                       skip);
-  } else {
-    if (skip != 0) {
-      sink_->Put(kSkip, "SkipFromSerializeObject");
-      sink_->PutInt(skip, "SkipDistanceFromSerializeObject");
-    }
-    // Object has not yet been serialized.  Serialize it here.
-    ObjectSerializer serializer(this,
-                                heap_object,
-                                sink_,
-                                how_to_code,
-                                where_to_point);
-    serializer.Serialize();
+  BackReference back_reference = back_reference_map_.Lookup(obj);
+  if (back_reference.is_valid()) {
+    SerializeBackReference(back_reference, how_to_code, where_to_point, skip);
+    return;
   }
+
+  if (skip != 0) {
+    sink_->Put(kSkip, "SkipFromSerializeObject");
+    sink_->PutInt(skip, "SkipDistanceFromSerializeObject");
+  }
+  // Object has not yet been serialized.  Serialize it here.
+  ObjectSerializer serializer(this, obj, sink_, how_to_code, where_to_point);
+  serializer.Serialize();
 }
 
 
-void Serializer::ObjectSerializer::SerializePrologue(int space, int size,
-                                                     Map* map) {
+void Serializer::ObjectSerializer::SerializePrologue(AllocationSpace space,
+                                                     int size, Map* map) {
   sink_->Put(kNewObject + reference_representation_ + space,
              "ObjectSerialization");
   sink_->PutInt(size >> kObjectAlignmentBits, "Size in words");
@@ -1564,18 +1559,18 @@ void Serializer::ObjectSerializer::SerializePrologue(int space, int size,
   }
 
   // Mark this object as already serialized.
+  BackReference back_reference;
   if (space == LO_SPACE) {
     if (object_->IsCode()) {
       sink_->Put(EXECUTABLE, "executable large object");
     } else {
       sink_->Put(NOT_EXECUTABLE, "not executable large object");
     }
-    int index = serializer_->AllocateLargeObject(size);
-    serializer_->address_mapper()->AddMapping(object_, index);
+    back_reference = serializer_->AllocateLargeObject(size);
   } else {
-    int allocation = serializer_->Allocate(space, size);
-    serializer_->address_mapper()->AddMapping(object_, allocation);
+    back_reference = serializer_->Allocate(space, size);
   }
+  serializer_->back_reference_map()->Add(object_, back_reference);
 
   // Serialize the map (first word of the object).
   serializer_->SerializeObject(map, kPlain, kStartOfObject, 0);
@@ -1605,7 +1600,7 @@ void Serializer::ObjectSerializer::SerializeExternalString() {
         ExternalTwoByteString::cast(string)->resource()->data());
   }
 
-  int space =
+  AllocationSpace space =
       (size > Page::kMaxRegularHeapObjectSize) ? LO_SPACE : OLD_DATA_SPACE;
   SerializePrologue(space, size, map);
 
@@ -1670,12 +1665,11 @@ void Serializer::ObjectSerializer::VisitPointers(Object** start,
 
     while (current < end && !(*current)->IsSmi()) {
       HeapObject* current_contents = HeapObject::cast(*current);
-      int root_index = serializer_->RootIndex(current_contents, kPlain);
+      int root_index = serializer_->root_index_map()->Lookup(current_contents);
       // Repeats are not subject to the write barrier so there are only some
       // objects that can be used in a repeat encoding.  These are the early
       // ones in the root array that are never in new space.

[Erik Corry, 2014/10/23 12:57:15]

I think now this is _all_ the entries in the root array that are _not currently_
in new space.

-      if (current != start &&
-          root_index != kInvalidRootIndex &&
+      if (current != start && root_index != RootIndexMap::kInvalidRootIndex &&
           root_index < kRootArrayNumberOfConstantEncodings &&
           current_contents == current[-1]) {
         DCHECK(!serializer_->isolate()->heap()->InNewSpace(current_contents));
@@ -1711,7 +1705,8 @@ void Serializer::ObjectSerializer::VisitEmbeddedPointer(RelocInfo* rinfo) {
                            kCanReturnSkipInsteadOfSkipping);
   HowToCode how_to_code = rinfo->IsCodedSpecially() ? kFromCode : kPlain;
   Object* object = rinfo->target_object();
-  serializer_->SerializeObject(object, how_to_code, kStartOfObject, skip);
+  serializer_->SerializeObject(HeapObject::cast(object), how_to_code,
+                               kStartOfObject, skip);
   bytes_processed_so_far_ += rinfo->target_address_size();
 }
 
@@ -1887,32 +1882,31 @@ int Serializer::ObjectSerializer::OutputRawData(
 }
 
 
-int Serializer::SpaceOfObject(HeapObject* object) {
+AllocationSpace Serializer::SpaceOfObject(HeapObject* object) {
   for (int i = FIRST_SPACE; i <= LAST_SPACE; i++) {
     AllocationSpace s = static_cast<AllocationSpace>(i);
     if (object->GetHeap()->InSpace(object, s)) {
       DCHECK(i < kNumberOfSpaces);
-      return i;
+      return s;
     }
   }
   UNREACHABLE();
-  return 0;
+  return INVALID_SPACE;
 }
 
 
-uint32_t Serializer::AllocateLargeObject(int size) {
+BackReference Serializer::AllocateLargeObject(int size) {
   // Large objects are allocated one-by-one when deserializing. We do not
   // have to keep track of multiple chunks.
   pending_chunk_[LO_SPACE] += size;
-  return seen_large_objects_index_++;
+  return BackReference(LO_SPACE, 0, seen_large_objects_index_++);
 }
 
 
-uint32_t Serializer::Allocate(int space, int size) {
+BackReference Serializer::Allocate(AllocationSpace space, int size) {
   CHECK(space >= 0 && space < kNumberOfPreallocatedSpaces);
   DCHECK(size > 0 && size < Page::kMaxRegularHeapObjectSize);
   uint32_t new_chunk_size = pending_chunk_[space] + size;
-  uint32_t allocation;
   if (new_chunk_size > static_cast<uint32_t>(Page::kMaxRegularHeapObjectSize)) {
     // The new chunk size would not fit onto a single page. Complete the
     // current chunk and start a new one.
@@ -1920,12 +1914,9 @@ uint32_t Serializer::Allocate(int space, int size) {
     pending_chunk_[space] = 0;
     new_chunk_size = size;
   }
-  // For back-referencing, each allocation is encoded as a combination
-  // of chunk index and offset inside the chunk.
-  allocation = ChunkIndexBits::encode(completed_chunks_[space].length()) |
-               OffsetBits::encode(pending_chunk_[space]);
+  uint32_t offset = pending_chunk_[space];
   pending_chunk_[space] = new_chunk_size;
-  return allocation;
+  return BackReference(space, completed_chunks_[space].length(), offset);
 }
 
 
@@ -1979,6 +1970,13 @@ ScriptData* CodeSerializer::Serialize(Isolate* isolate,
   cs.Pad();
   cs.FinalizeAllocation();
 
+  for (int i = 0; i < kNumberOfPreallocatedSpaces; i++) {
+    // Fail if any chunk index exceeds the limit.
+    if (cs.FinalAllocationChunks(i).length() > BackReference::kMaxChunkIndex) {
+      return NULL;
+    }
+  }
+
   SerializedCodeData data(&payload, &cs);
   ScriptData* script_data = data.GetScriptData();
 
@@ -1992,27 +1990,25 @@ ScriptData* CodeSerializer::Serialize(Isolate* isolate,
 }
 
 
-void CodeSerializer::SerializeObject(Object* o, HowToCode how_to_code,
+void CodeSerializer::SerializeObject(HeapObject* obj, HowToCode how_to_code,
                                      WhereToPoint where_to_point, int skip) {
-  HeapObject* heap_object = HeapObject::cast(o);
-
-  int root_index;
-  if ((root_index = RootIndex(heap_object, how_to_code)) != kInvalidRootIndex) {
+  int root_index = root_index_map_.Lookup(obj);
+  if (root_index != RootIndexMap::kInvalidRootIndex) {
     if (FLAG_serializer_trace_level > 0) {
       PrintF(" Encoding root: %d\n", root_index);
     }
-    PutRoot(root_index, heap_object, how_to_code, where_to_point, skip);
+    PutRoot(root_index, obj, how_to_code, where_to_point, skip);
     return;
   }
 
-  if (address_mapper_.IsMapped(heap_object)) {
+  BackReference back_reference = back_reference_map_.Lookup(obj);
+  if (back_reference.is_valid()) {
     if (FLAG_serializer_trace_level > 0) {
       PrintF(" Encoding back reference to: ");
-      heap_object->ShortPrint();
+      obj->ShortPrint();
       PrintF("\n");
     }
-    SerializeReferenceToPreviousObject(heap_object, how_to_code, where_to_point,
-                                       skip);
+    SerializeBackReference(back_reference, how_to_code, where_to_point, skip);
     return;
   }
 
@@ -2021,8 +2017,8 @@ void CodeSerializer::SerializeObject(Object* o, HowToCode how_to_code,
     sink_->PutInt(skip, "SkipDistanceFromSerializeObject");
   }
 
-  if (heap_object->IsCode()) {
-    Code* code_object = Code::cast(heap_object);
+  if (obj->IsCode()) {
+    Code* code_object = Code::cast(obj);
     switch (code_object->kind()) {
       case Code::OPTIMIZED_FUNCTION:  // No optimized code compiled yet.
       case Code::HANDLER:             // No handlers patched in yet.
@@ -2049,32 +2045,32 @@ void CodeSerializer::SerializeObject(Object* o, HowToCode how_to_code,
           SerializeBuiltin(Builtins::kCompileLazy, how_to_code, where_to_point);
         } else {
           code_object->MakeYoung();
-          SerializeHeapObject(code_object, how_to_code, where_to_point);
+          SerializeGeneric(code_object, how_to_code, where_to_point);
         }
         return;
     }
     UNREACHABLE();
   }
 
-  if (heap_object == source_) {
+  if (obj == source_) {
     SerializeSourceObject(how_to_code, where_to_point);
     return;
   }
 
   // Past this point we should not see any (context-specific) maps anymore.
-  CHECK(!heap_object->IsMap());
+  CHECK(!obj->IsMap());
   // There should be no references to the global object embedded.
-  CHECK(!heap_object->IsJSGlobalProxy() && !heap_object->IsGlobalObject());
+  CHECK(!obj->IsJSGlobalProxy() && !obj->IsGlobalObject());
   // There should be no hash table embedded. They would require rehashing.
-  CHECK(!heap_object->IsHashTable());
+  CHECK(!obj->IsHashTable());
 
-  SerializeHeapObject(heap_object, how_to_code, where_to_point);
+  SerializeGeneric(obj, how_to_code, where_to_point);
 }
 
 
-void CodeSerializer::SerializeHeapObject(HeapObject* heap_object,
-                                         HowToCode how_to_code,
-                                         WhereToPoint where_to_point) {
+void CodeSerializer::SerializeGeneric(HeapObject* heap_object,
+                                      HowToCode how_to_code,
+                                      WhereToPoint where_to_point) {
   if (FLAG_serializer_trace_level > 0) {
     PrintF(" Encoding heap object: ");
     heap_object->ShortPrint();
@@ -2161,7 +2157,7 @@ void CodeSerializer::SerializeIC(Code* ic, HowToCode how_to_code,
     PrintF(" %s has no special handling\n", Code::Kind2String(ic->kind()));
   }
   DCHECK(ic->kind() == Code::LOAD_IC || ic->kind() == Code::STORE_IC);
-  SerializeHeapObject(ic, how_to_code, where_to_point);
+  SerializeGeneric(ic, how_to_code, where_to_point);
 }
 
 
@@ -2243,7 +2239,7 @@ MaybeHandle<SharedFunctionInfo> CodeSerializer::Deserialize(
 
 
 SerializedCodeData::SerializedCodeData(List<byte>* payload, CodeSerializer* cs)
-    : owns_script_data_(true) {
+    : script_data_(NULL), owns_script_data_(true) {
   DisallowHeapAllocation no_gc;
   List<uint32_t>* stub_keys = cs->stub_keys();