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

src/serialize.h

 // Copyright 2012 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #ifndef V8_SERIALIZE_H_
 #define V8_SERIALIZE_H_
 
 #include "src/compiler.h"
 #include "src/hashmap.h"
 #include "src/heap-profiler.h"
@@ skipping 121 matching lines @@
   }
 
   void Put(uint32_t key, Address value) {
     *Lookup(key) = value;
   }
 
   Isolate* isolate_;
 };
 
 
+class AddressMapBase {
+ protected:
+  static void SetValue(HashMap::Entry* entry, uint32_t v) {
+    entry->value = reinterpret_cast<void*>(v);
+  }
+
+  static uint32_t GetValue(HashMap::Entry* entry) {
+    return reinterpret_cast<uint32_t>(entry->value);
+  }
+
+  static HashMap::Entry* LookupEntry(HashMap* map, HeapObject* obj,
+                                     bool insert) {
+    return map->Lookup(Key(obj), Hash(obj), insert);
+  }
+
+ private:
+  static uint32_t Hash(HeapObject* obj) {
+    return static_cast<int32_t>(reinterpret_cast<intptr_t>(obj->address()));
+  }
+
+  static void* Key(HeapObject* obj) {
+    return reinterpret_cast<void*>(obj->address());
+  }
+};
+
+
+class RootIndexMap : public AddressMapBase {
+ public:
+  explicit RootIndexMap(Isolate* isolate);
+
+  static const int kInvalidRootIndex = -1;
+  int Lookup(HeapObject* obj) {
+    HashMap::Entry* entry = LookupEntry(map_, obj, false);
+    if (entry) return GetValue(entry);
+    return kInvalidRootIndex;
+  }
+
+ private:
+  HashMap* map_;
+
+  DISALLOW_COPY_AND_ASSIGN(RootIndexMap);
+};
+
+
+class BackReference {
+ public:
+  explicit BackReference(uint32_t bitfield) : bitfield_(bitfield) {}
+
+  BackReference(AllocationSpace space, uint32_t chunk_index,
+                uint32_t chunk_offset) {
+    DCHECK(IsAligned(chunk_offset, kObjectAlignment));
+    bitfield_ = SpaceBits::encode(space) | ChunkIndexBits::encode(chunk_index) |
+                ChunkOffsetBits::encode(chunk_offset >> kObjectAlignmentBits);
+  }
+
+  BackReference() : bitfield_(kInvalidValue) {}
+
+  bool is_valid() const { return bitfield_ != kInvalidValue; }
+
+  AllocationSpace space() const {
+    DCHECK(is_valid());
+    return SpaceBits::decode(bitfield_);
+  }
+
+  uint32_t chunk_offset() const {
+    DCHECK(is_valid());
+    return ChunkOffsetBits::decode(bitfield_) << kObjectAlignmentBits;
+  }
+
+  uint32_t chunk_index() const {
+    DCHECK(is_valid());
+    return ChunkIndexBits::decode(bitfield_);
+  }
+
+  uint32_t reference() const {
+    DCHECK(is_valid());
+    return bitfield_ & (ChunkOffsetBits::kMask | ChunkIndexBits::kMask);
+  }
+
+  uint32_t bitfield() const { return bitfield_; }
+
+ private:
+  static const uint32_t kInvalidValue = 0xFFFFFFFF;
+  static const int kChunkOffsetSize = kPageSizeBits - kObjectAlignmentBits;
+  static const int kChunkIndexSize = 32 - kChunkOffsetSize - kSpaceTagSize;
+
+ public:
+  static const int kMaxChunkIndex = (1 << kChunkIndexSize) - 1;
+
+ private:
+  class ChunkOffsetBits : public BitField<uint32_t, 0, kChunkOffsetSize> {};
+  class ChunkIndexBits
+      : public BitField<uint32_t, ChunkOffsetBits::kNext, kChunkIndexSize> {};
+  class SpaceBits
+      : public BitField<AllocationSpace, ChunkIndexBits::kNext, kSpaceTagSize> {
+  };
+
+  uint32_t bitfield_;
+};
+
+
+// Mapping objects to their location after deserialization.
+// This is used during building, but not at runtime by V8.
+class BackReferenceMap : public AddressMapBase {
+ public:
+  BackReferenceMap()
+      : no_allocation_(), map_(new HashMap(HashMap::PointersMatch)) {}
+
+  ~BackReferenceMap() { delete map_; }
+
+  BackReference Lookup(HeapObject* obj) {
+    HashMap::Entry* entry = LookupEntry(map_, obj, false);
+    return entry ? BackReference(GetValue(entry)) : BackReference();
+  }
+
+  void Add(HeapObject* obj, BackReference b) {
+    DCHECK(b.is_valid());
+    DCHECK_EQ(NULL, LookupEntry(map_, obj, false));
+    HashMap::Entry* entry = LookupEntry(map_, obj, true);
+    SetValue(entry, b.bitfield());
+  }
+
+ private:
+  DisallowHeapAllocation no_allocation_;

[mvstanton, 2014/10/23 08:02:15]

I like this use of DisallowHeapAllocation, neat!

+  HashMap* map_;
+  DISALLOW_COPY_AND_ASSIGN(BackReferenceMap);
+};
+
+
 // The Serializer/Deserializer class is a common superclass for Serializer and
 // Deserializer which is used to store common constants and methods used by
 // both.
 class SerializerDeserializer: public ObjectVisitor {
  public:
   static void Iterate(Isolate* isolate, ObjectVisitor* visitor);
 
   static int nop() { return kNop; }
 
   // No reservation for large object space necessary.
   static const int kNumberOfPreallocatedSpaces = LO_SPACE;
   static const int kNumberOfSpaces = INVALID_SPACE;
 
-  // To encode object for back-references.
-  class OffsetBits : public BitField<uint32_t, 0, kPageSizeBits> {};
-  class ChunkIndexBits
-      : public BitField<uint32_t, kPageSizeBits, 32 - kPageSizeBits> {};
-
  protected:
   // Where the pointed-to object can be found:
   enum Where {
     kNewObject = 0,  // Object is next in snapshot.
     // 1-7                             One per space.
     kRootArray = 0x9,             // Object is found in root array.
     kPartialSnapshotCache = 0xa,  // Object is in the cache.
     kExternalReference = 0xb,     // Pointer to an external reference.
     kSkip = 0xc,                  // Skip n bytes.
     kBuiltin = 0xd,               // Builtin code object.
@@ skipping 135 matching lines @@
   HeapObject* ProcessNewObjectFromSerializedCode(HeapObject* obj);
   Object* ProcessBackRefInSerializedCode(Object* obj);
 
   // This returns the address of an object that has been described in the
   // snapshot by chunk index and offset.
   HeapObject* GetBackReferencedObject(int space) {
     if (space == LO_SPACE) {
       uint32_t index = source_->GetInt();
       return deserialized_large_objects_[index];
     } else {
-      uint32_t allocation = source_->GetInt() << kObjectAlignmentBits;
+      BackReference back_reference(source_->GetInt());
       DCHECK(space < kNumberOfPreallocatedSpaces);
-      uint32_t chunk_index = ChunkIndexBits::decode(allocation);
-      uint32_t offset = OffsetBits::decode(allocation);
+      uint32_t chunk_index = back_reference.chunk_index();
       DCHECK_LE(chunk_index, current_chunk_[space]);
+      uint32_t chunk_offset = back_reference.chunk_offset();
       return HeapObject::FromAddress(reservations_[space][chunk_index].start +
-                                     offset);
+                                     chunk_offset);
     }
   }
 
   // Cached current isolate.
   Isolate* isolate_;
 
   // Objects from the attached object descriptions in the serialized user code.
   Vector<Handle<Object> >* attached_objects_;
 
   SnapshotByteSource* source_;
   // The address of the next object that will be allocated in each space.
   // Each space has a number of chunks reserved by the GC, with each chunk
   // fitting into a page. Deserialized objects are allocated into the
   // current chunk of the target space by bumping up high water mark.
   Heap::Reservation reservations_[kNumberOfSpaces];
   uint32_t current_chunk_[kNumberOfPreallocatedSpaces];
   Address high_water_[kNumberOfPreallocatedSpaces];
 
   ExternalReferenceDecoder* external_reference_decoder_;
 
   List<HeapObject*> deserialized_large_objects_;
 
   DISALLOW_COPY_AND_ASSIGN(Deserializer);
 };
 
 
-// Mapping objects to their location after deserialization.
-// This is used during building, but not at runtime by V8.
-class SerializationAddressMapper {
- public:
-  SerializationAddressMapper()
-      : no_allocation_(),
-        serialization_map_(new HashMap(HashMap::PointersMatch)) { }
-
-  ~SerializationAddressMapper() {
-    delete serialization_map_;
-  }
-
-  bool IsMapped(HeapObject* obj) {
-    return serialization_map_->Lookup(Key(obj), Hash(obj), false) != NULL;
-  }
-
-  int MappedTo(HeapObject* obj) {
-    DCHECK(IsMapped(obj));
-    return static_cast<int>(reinterpret_cast<intptr_t>(
-        serialization_map_->Lookup(Key(obj), Hash(obj), false)->value));
-  }
-
-  void AddMapping(HeapObject* obj, int to) {
-    DCHECK(!IsMapped(obj));
-    HashMap::Entry* entry =
-        serialization_map_->Lookup(Key(obj), Hash(obj), true);
-    entry->value = Value(to);
-  }
-
- private:
-  static uint32_t Hash(HeapObject* obj) {
-    return static_cast<int32_t>(reinterpret_cast<intptr_t>(obj->address()));
-  }
-
-  static void* Key(HeapObject* obj) {
-    return reinterpret_cast<void*>(obj->address());
-  }
-
-  static void* Value(int v) {
-    return reinterpret_cast<void*>(v);
-  }
-
-  DisallowHeapAllocation no_allocation_;
-  HashMap* serialization_map_;
-  DISALLOW_COPY_AND_ASSIGN(SerializationAddressMapper);
-};
-
-
 class CodeAddressMap;
 
 // There can be only one serializer per V8 process.
 class Serializer : public SerializerDeserializer {
  public:
   Serializer(Isolate* isolate, SnapshotByteSink* sink);
   ~Serializer();
-  void VisitPointers(Object** start, Object** end);
+  virtual void VisitPointers(Object** start, Object** end) OVERRIDE;
 
   void FinalizeAllocation();
 
   Vector<const uint32_t> FinalAllocationChunks(int space) const {
     DCHECK_EQ(1, completed_chunks_[LO_SPACE].length());  // Already finalized.
     DCHECK_EQ(0, pending_chunk_[space]);                 // No pending chunks.
     return completed_chunks_[space].ToConstVector();
   }
 
   Isolate* isolate() const { return isolate_; }
 
-  SerializationAddressMapper* address_mapper() { return &address_mapper_; }
-  void PutRoot(int index,
-               HeapObject* object,
-               HowToCode how,
-               WhereToPoint where,
-               int skip);
+  BackReferenceMap* back_reference_map() { return &back_reference_map_; }
+  RootIndexMap* root_index_map() { return &root_index_map_; }
 
  protected:
-  static const int kInvalidRootIndex = -1;
-
-  int RootIndex(HeapObject* heap_object, HowToCode from);
-  intptr_t root_index_wave_front() { return root_index_wave_front_; }
-  void set_root_index_wave_front(intptr_t value) {
-    DCHECK(value >= root_index_wave_front_);
-    root_index_wave_front_ = value;
-  }
-
   class ObjectSerializer : public ObjectVisitor {
    public:
     ObjectSerializer(Serializer* serializer,
                      Object* o,
                      SnapshotByteSink* sink,
                      HowToCode how_to_code,
                      WhereToPoint where_to_point)
       : serializer_(serializer),
         object_(HeapObject::cast(o)),
         sink_(sink),
@@ skipping 13 matching lines @@
     // Used for seralizing the external strings that hold the natives source.
     void VisitExternalOneByteString(
         v8::String::ExternalOneByteStringResource** resource);
     // We can't serialize a heap with external two byte strings.
     void VisitExternalTwoByteString(
         v8::String::ExternalStringResource** resource) {
       UNREACHABLE();
     }
 
    private:
-    void SerializePrologue(int space, int size, Map* map);
+    void SerializePrologue(AllocationSpace space, int size, Map* map);

[mvstanton, 2014/10/23 08:02:15]

+1 for use of the enum instead of int.

 
     enum ReturnSkip { kCanReturnSkipInsteadOfSkipping, kIgnoringReturn };
     // This function outputs or skips the raw data between the last pointer and
     // up to the current position.  It optionally can just return the number of
     // bytes to skip instead of performing a skip instruction, in case the skip
     // can be merged into the next instruction.
     int OutputRawData(Address up_to, ReturnSkip return_skip = kIgnoringReturn);
     // External strings are serialized in a way to resemble sequential strings.
     void SerializeExternalString();
 
     Serializer* serializer_;
     HeapObject* object_;
     SnapshotByteSink* sink_;
     int reference_representation_;
     int bytes_processed_so_far_;
     bool code_object_;
     bool code_has_been_output_;
   };
 
-  virtual void SerializeObject(Object* o,
-                               HowToCode how_to_code,
-                               WhereToPoint where_to_point,
-                               int skip) = 0;
-  void SerializeReferenceToPreviousObject(HeapObject* heap_object,
-                                          HowToCode how_to_code,
-                                          WhereToPoint where_to_point,
-                                          int skip);
+  virtual void SerializeObject(HeapObject* o, HowToCode how_to_code,
+                               WhereToPoint where_to_point, int skip) = 0;
+
+  void PutRoot(int index, HeapObject* object, HowToCode how, WhereToPoint where,
+               int skip);
+
+  void SerializeBackReference(BackReference back_reference,
+                              HowToCode how_to_code,
+                              WhereToPoint where_to_point, int skip);
   void InitializeAllocators();
   // This will return the space for an object.
-  static int SpaceOfObject(HeapObject* object);
-  uint32_t AllocateLargeObject(int size);
-  uint32_t Allocate(int space, int size);
+  static AllocationSpace SpaceOfObject(HeapObject* object);
+  BackReference AllocateLargeObject(int size);
+  BackReference Allocate(AllocationSpace space, int size);
   int EncodeExternalReference(Address addr) {
     return external_reference_encoder_->Encode(addr);
   }
 
   int SpaceAreaSize(int space);
 
   // Some roots should not be serialized, because their actual value depends on
   // absolute addresses and they are reset after deserialization, anyway.
   bool ShouldBeSkipped(Object** current);
 
   Isolate* isolate_;
 
   // Objects from the same space are put into chunks for bulk-allocation
   // when deserializing. We have to make sure that each chunk fits into a
   // page. So we track the chunk size in pending_chunk_ of a space, but
   // when it exceeds a page, we complete the current chunk and start a new one.
   uint32_t pending_chunk_[kNumberOfSpaces];
   List<uint32_t> completed_chunks_[kNumberOfSpaces];
 
   SnapshotByteSink* sink_;
   ExternalReferenceEncoder* external_reference_encoder_;
 
-  SerializationAddressMapper address_mapper_;
-  intptr_t root_index_wave_front_;
+  BackReferenceMap back_reference_map_;
+  RootIndexMap root_index_map_;
   void Pad();
 
   friend class ObjectSerializer;
   friend class Deserializer;
 
   // We may not need the code address map for logging for every instance
   // of the serializer.  Initialize it on demand.
   void InitializeCodeAddressMap();
 
  private:
   CodeAddressMap* code_address_map_;
   // We map serialized large objects to indexes for back-referencing.
   uint32_t seen_large_objects_index_;
   DISALLOW_COPY_AND_ASSIGN(Serializer);
 };
 
 
 class PartialSerializer : public Serializer {
  public:
   PartialSerializer(Isolate* isolate,
                     Serializer* startup_snapshot_serializer,
                     SnapshotByteSink* sink)
     : Serializer(isolate, sink),
       startup_serializer_(startup_snapshot_serializer) {
-    set_root_index_wave_front(Heap::kStrongRootListLength);
     InitializeCodeAddressMap();
   }
 
   // Serialize the objects reachable from a single object pointer.
   void Serialize(Object** o);
-  virtual void SerializeObject(Object* o,
-                               HowToCode how_to_code,
-                               WhereToPoint where_to_point,
-                               int skip);
+  virtual void SerializeObject(HeapObject* o, HowToCode how_to_code,
+                               WhereToPoint where_to_point, int skip);
 
  private:
   int PartialSnapshotCacheIndex(HeapObject* o);
   bool ShouldBeInThePartialSnapshotCache(HeapObject* o) {
     // Scripts should be referred only through shared function infos.  We can't
     // allow them to be part of the partial snapshot because they contain a
     // unique ID, and deserializing several partial snapshots containing script
     // would cause dupes.
     DCHECK(!o->IsScript());
     return o->IsName() || o->IsSharedFunctionInfo() ||
            o->IsHeapNumber() || o->IsCode() ||
            o->IsScopeInfo() ||
            o->map() ==
                startup_serializer_->isolate()->heap()->fixed_cow_array_map();
   }
 
 
   Serializer* startup_serializer_;
   DISALLOW_COPY_AND_ASSIGN(PartialSerializer);
 };
 
 
 class StartupSerializer : public Serializer {
  public:
   StartupSerializer(Isolate* isolate, SnapshotByteSink* sink)
-    : Serializer(isolate, sink) {
+      : Serializer(isolate, sink), root_index_wave_front_(0) {
     // Clear the cache of objects used by the partial snapshot.  After the
     // strong roots have been serialized we can create a partial snapshot
     // which will repopulate the cache with objects needed by that partial
     // snapshot.
     isolate->set_serialize_partial_snapshot_cache_length(0);
     InitializeCodeAddressMap();
   }
+
+  // The StartupSerializer has to serialize the root array, which is slightly
+  // different.
+  virtual void VisitPointers(Object** start, Object** end) OVERRIDE;
+
   // Serialize the current state of the heap.  The order is:
   // 1) Strong references.
   // 2) Partial snapshot cache.
   // 3) Weak references (e.g. the string table).
   virtual void SerializeStrongReferences();
-  virtual void SerializeObject(Object* o,
-                               HowToCode how_to_code,
-                               WhereToPoint where_to_point,
-                               int skip);
+  virtual void SerializeObject(HeapObject* o, HowToCode how_to_code,
+                               WhereToPoint where_to_point, int skip);
   void SerializeWeakReferences();
   void Serialize() {
     SerializeStrongReferences();
     SerializeWeakReferences();
     Pad();
   }
 
  private:
+  int root_index_wave_front_;
   DISALLOW_COPY_AND_ASSIGN(StartupSerializer);
 };
 
 
 class CodeSerializer : public Serializer {
  public:
   static ScriptData* Serialize(Isolate* isolate,
                                Handle<SharedFunctionInfo> info,
                                Handle<String> source);
 
   MUST_USE_RESULT static MaybeHandle<SharedFunctionInfo> Deserialize(
       Isolate* isolate, ScriptData* data, Handle<String> source);
 
   static const int kSourceObjectIndex = 0;
   static const int kCodeStubsBaseIndex = 1;
 
   String* source() {
     DCHECK(!AllowHeapAllocation::IsAllowed());
     return source_;
   }
 
   List<uint32_t>* stub_keys() { return &stub_keys_; }
 
  private:
   CodeSerializer(Isolate* isolate, SnapshotByteSink* sink, String* source,
                  Code* main_code)
       : Serializer(isolate, sink), source_(source), main_code_(main_code) {
-    set_root_index_wave_front(Heap::kStrongRootListLength);
     InitializeCodeAddressMap();
   }
 
-  virtual void SerializeObject(Object* o, HowToCode how_to_code,
+  virtual void SerializeObject(HeapObject* o, HowToCode how_to_code,
                                WhereToPoint where_to_point, int skip);
 
   void SerializeBuiltin(int builtin_index, HowToCode how_to_code,
                         WhereToPoint where_to_point);
   void SerializeIC(Code* ic, HowToCode how_to_code,
                    WhereToPoint where_to_point);
   void SerializeCodeStub(uint32_t stub_key, HowToCode how_to_code,
                          WhereToPoint where_to_point);
   void SerializeSourceObject(HowToCode how_to_code,
                              WhereToPoint where_to_point);
-  void SerializeHeapObject(HeapObject* heap_object, HowToCode how_to_code,
-                           WhereToPoint where_to_point);
+  void SerializeGeneric(HeapObject* heap_object, HowToCode how_to_code,
+                        WhereToPoint where_to_point);
   int AddCodeStubKey(uint32_t stub_key);
 
   DisallowHeapAllocation no_gc_;
   String* source_;
   Code* main_code_;
   List<uint32_t> stub_keys_;
   DISALLOW_COPY_AND_ASSIGN(CodeSerializer);
 };
 
 
@@ skipping 92 matching lines @@
   // Following the header, we store, in sequential order
   // - code stub keys
   // - serialization payload
 
   ScriptData* script_data_;
   bool owns_script_data_;
 };
 } }  // namespace v8::internal
 
 #endif  // V8_SERIALIZE_H_