Refactoring of snapshots. This simplifies and improves

src/serialize.h

 // 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 152 matching lines @@
   SnapshotByteSource(const byte* array, int length)
     : data_(array), length_(length), position_(0) { }
 
   bool HasMore() { return position_ < length_; }
 
   int Get() {
     ASSERT(position_ < length_);
     return data_[position_++];
   }
 
+  int32_t GetUnalignedInt() {
+#ifdef V8_HOST_CAN_READ_UNALIGNED
+    int32_t answer;
+    ASSERT(position_ + sizeof(answer) <= length_ + 0u);
+    answer = *reinterpret_cast<const int32_t*>(data_ + position_);

[Yang, 2012/09/13 08:47:59]

Since GetInt() uses this: we assume the least significant two bits to tell how
many bytes are part of the integer, so the byte order matters. This would only
work on little endian systems, right? The #else block seems to work for big
endian as well. I don't think we have any big endian system that reads
unaligned, but an assertion won't hurt?

[Erik Corry, 2012/09/13 12:13:35]

Fixed to go into the slow case for big endian.

+#else
+    int32_t answer = data_[position_];
+    answer |= data_[position_ + 1] << 8;
+    answer |= data_[position_ + 2] << 16;
+    answer |= data_[position_ + 3] << 24;

[Yang, 2012/09/13 08:47:59]

In PutInt we only take integers that can be encoded in 3 bytes. Why even fetch a
4th byte?

[Erik Corry, 2012/09/13 12:13:35]

Otherwise it will do something different depending on the ifdefs.  I don't want
to rename it to
GetUnalignedIntOrGetUnaligned24BitValueDependingOnSomeObscureIfdefs because then
I would run into problems with the 80 character limit.

+#endif
+    return answer;
+  }
+
+  void Advance(int by) { position_ += by; }
+
   inline void CopyRaw(byte* to, int number_of_bytes);
 
   inline int GetInt();
 
-  bool AtEOF() {
-    return position_ == length_;
-  }
+  bool AtEOF();
 
   int position() { return position_; }
 
  private:
   const byte* data_;
   int length_;
   int position_;
 };
 
 
 #define COMMON_RAW_LENGTHS(f)        \
-  f(1, 1)  \
-  f(2, 2)  \
-  f(3, 3)  \
-  f(4, 4)  \
-  f(5, 5)  \
-  f(6, 6)  \
-  f(7, 7)  \
-  f(8, 8)  \
-  f(9, 12)  \
-  f(10, 16) \
-  f(11, 20) \
-  f(12, 24) \
-  f(13, 28) \
-  f(14, 32) \
-  f(15, 36)
+  f(1, 4)  \
+  f(2, 8)  \
+  f(3, 12)  \
+  f(4, 16)  \
+  f(5, 20)  \
+  f(6, 24)  \
+  f(7, 28)  \
+  f(8, 32)  \
+  f(9, 36)  \
+  f(10, 40) \
+  f(11, 44) \
+  f(12, 48) \
+  f(13, 52) \
+  f(14, 56) \
+  f(15, 60) \
+  f(16, 64) \
+  f(17, 68) \
+  f(18, 72) \
+  f(19, 76) \
+  f(20, 80) \
+  f(21, 84) \
+  f(22, 88) \
+  f(23, 92) \
+  f(24, 96) \
+  f(25, 100) \
+  f(26, 104) \
+  f(27, 108) \
+  f(28, 112) \
+  f(29, 116) \
+  f(30, 120) \
+  f(31, 124)

[Yang, 2012/09/13 08:47:59]

if the second arg is always 4x the first arg, why not make that part of f? Or at
least add a few STATIC_CHECK in some of the f.

[Erik Corry, 2012/09/13 12:13:35]

Made it part of f, and moved this to the .cc file.

 
 // 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(ObjectVisitor* visitor);
 
+  static int nop() { return kNop; }
+
  protected:
   // Where the pointed-to object can be found:
   enum Where {
     kNewObject = 0,                 // Object is next in snapshot.
-    // 1-8                             One per space.
+    // 1-6                             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 a pointer sized cell.
-    // 0xd-0xf                         Free.
-    kBackref = 0x10,                 // Object is described relative to end.
-    // 0x11-0x18                       One per space.
-    // 0x19-0x1f                       Free.
-    kFromStart = 0x20,              // Object is described relative to start.
-    // 0x21-0x28                       One per space.
-    // 0x29-0x2f                       Free.
-    // 0x30-0x3f                       Used by misc. tags below.
+    kSkip = 0xc,                    // Skip n bytes.
+    kNop = 0xd,                     // Does nothing, used to pad.
+    // 0xe-0xf                         Free.
+    kBackref = 0x10,                // Object is described relative to end.
+    // 0x11-0x16                       One per space.
+    kBackrefWithSkip = 0x18,        // Object is described relative to end.
+    // 0x19-0x1e                       One per space.
+    // 0x20-0x3f                       Used by misc. tags below.
     kPointedToMask = 0x3f
   };
 
   // How to code the pointer to the object.
   enum HowToCode {
     kPlain = 0,                          // Straight pointer.
     // What this means depends on the architecture:
     kFromCode = 0x40,                    // A pointer inlined in code.
     kHowToCodeMask = 0x40
   };
 
+  // For kRootArrayConstants
+  enum WithSkip {
+    kNoSkipDistance = 0,
+    kHasSkipDistance = 0x40,
+    kWithSkipMask = 0x40
+  };
+
   // Where to point within the object.
   enum WhereToPoint {
     kStartOfObject = 0,
     kInnerPointer = 0x80,  // First insn in code object or payload of cell.
     kWhereToPointMask = 0x80
   };
 
   // Misc.
-  // Raw data to be copied from the snapshot.
-  static const int kRawData = 0x30;
-  // Some common raw lengths: 0x31-0x3f
+  // Raw data to be copied from the snapshot.  This byte code does not advance
+  // the current pointer, which is used for code objects, where we write the
+  // entire code in one memcpy, then fix up stuff with kSkip and other byte
+  // codes that overwrite data.
+  static const int kRawData = 0x20;
+  // Some common raw lengths: 0x21-0x3f.  These autoadvance the current pointer.
   // A tag emitted at strategic points in the snapshot to delineate sections.
   // If the deserializer does not find these at the expected moments then it
   // is an indication that the snapshot and the VM do not fit together.
   // Examine the build process for architecture, version or configuration
   // mismatches.
   static const int kSynchronize = 0x70;
   // Used for the source code of the natives, which is in the executable, but
   // is referred to from external strings in the snapshot.
   static const int kNativesStringResource = 0x71;
-  static const int kNewPage = 0x72;
-  static const int kRepeat = 0x73;
-  static const int kConstantRepeat = 0x74;
-  // 0x74-0x7f            Repeat last word (subtract 0x73 to get the count).
-  static const int kMaxRepeats = 0x7f - 0x73;
+  static const int kRepeat = 0x72;
+  static const int kConstantRepeat = 0x73;
+  // 0x73-0x7f            Repeat last word (subtract 0x72 to get the count).
+  static const int kMaxRepeats = 0x7f - 0x72;
   static int CodeForRepeats(int repeats) {
     ASSERT(repeats >= 1 && repeats <= kMaxRepeats);
-    return 0x73 + repeats;
+    return 0x72 + repeats;
   }
   static int RepeatsForCode(int byte_code) {
     ASSERT(byte_code >= kConstantRepeat && byte_code <= 0x7f);
-    return byte_code - 0x73;
+    return byte_code - 0x72;
   }
-  static const int kRootArrayLowConstants = 0xb0;
-  // 0xb0-0xbf            Things from the first 16 elements of the root array.
-  static const int kRootArrayHighConstants = 0xf0;
-  // 0xf0-0xff            Things from the next 16 elements of the root array.
+  static const int kRootArrayConstants = 0xa0;
+  // 0xa0-0xbf            Things from the first 32 elements of the root array.
   static const int kRootArrayNumberOfConstantEncodings = 0x20;
-  static const int kRootArrayNumberOfLowConstantEncodings = 0x10;
   static int RootArrayConstantFromByteCode(int byte_code) {
-    int constant = (byte_code & 0xf) | ((byte_code & 0x40) >> 2);
-    ASSERT(constant >= 0 && constant < kRootArrayNumberOfConstantEncodings);
-    return constant;
+    return byte_code & 0x1f;
   }
 
-
-  static const int kLargeData = LAST_SPACE;
-  static const int kLargeCode = kLargeData + 1;
-  static const int kLargeFixedArray = kLargeCode + 1;
-  static const int kNumberOfSpaces = kLargeFixedArray + 1;
+  static const int kNumberOfSpaces = LO_SPACE;
   static const int kAnyOldSpace = -1;
 
   // A bitmask for getting the space out of an instruction.
-  static const int kSpaceMask = 15;
-
-  static inline bool SpaceIsLarge(int space) { return space >= kLargeData; }
-  static inline bool SpaceIsPaged(int space) {
-    return space >= FIRST_PAGED_SPACE && space <= LAST_PAGED_SPACE;
-  }
+  static const int kSpaceMask = 7;
 };
 
 
 int SnapshotByteSource::GetInt() {
-  // A little unwind to catch the really small ints.
-  int snapshot_byte = Get();
-  if ((snapshot_byte & 0x80) == 0) {
-    return snapshot_byte;
-  }
-  int accumulator = (snapshot_byte & 0x7f) << 7;
-  while (true) {
-    snapshot_byte = Get();
-    if ((snapshot_byte & 0x80) == 0) {
-      return accumulator | snapshot_byte;
-    }
-    accumulator = (accumulator | (snapshot_byte & 0x7f)) << 7;
-  }
-  UNREACHABLE();
-  return accumulator;
+  // This way of variable-length encoding integers does not suffer from branch
+  // mispredictions.
+  uint32_t answer = GetUnalignedInt();
+  int bytes = answer & 3;
+  Advance(bytes);
+  uint32_t mask = 0xffffffffu;
+  mask >>= 32 - (bytes << 3);
+  answer &= mask;
+  answer >>= 2;
+  return answer;
 }
 
 
 void SnapshotByteSource::CopyRaw(byte* to, int number_of_bytes) {
   memcpy(to, data_ + position_, number_of_bytes);
   position_ += number_of_bytes;
 }
 
 
 // A Deserializer reads a snapshot and reconstructs the Object graph it defines.
 class Deserializer: public SerializerDeserializer {
  public:
   // Create a deserializer from a snapshot byte source.
   explicit Deserializer(SnapshotByteSource* source);
 
   virtual ~Deserializer();
 
   // Deserialize the snapshot into an empty heap.
   void Deserialize();
 
   // Deserialize a single object and the objects reachable from it.
   void DeserializePartial(Object** root);
 
+  void set_reservation(int space_number, uintptr_t reservation) {
+    ASSERT(space_number >= 0);
+    ASSERT(space_number <= LAST_SPACE);
+    reservations_[space_number] = reservation;
+  }
+
  private:
   virtual void VisitPointers(Object** start, Object** end);
 
   virtual void VisitExternalReferences(Address* start, Address* end) {
     UNREACHABLE();
   }
 
   virtual void VisitRuntimeEntry(RelocInfo* rinfo) {
     UNREACHABLE();
   }
 
   // Fills in some heap data in an area from start to end (non-inclusive).  The
   // space id is used for the write barrier.  The object_address is the address
   // of the object we are writing into, or NULL if we are not writing into an
   // object, i.e. if we are writing a series of tagged values that are not on
   // the heap.
   void ReadChunk(
       Object** start, Object** end, int space, Address object_address);
-  HeapObject* GetAddressFromStart(int space);
-  inline HeapObject* GetAddressFromEnd(int space);
-  Address Allocate(int space_number, Space* space, int size);
-  void ReadObject(int space_number, Space* space, Object** write_back);
+  void ReadObject(int space_number, Object** write_back);
+
+  // This routine both allocates a new object, and also keeps
+  // track of where objects have been allocated so that we can
+  // fix back references when deserializing.
+  Address Allocate(int space_index, int size) {
+    Address address = high_water_[space_index];
+    high_water_[space_index] = address + size;
+    return address;
+  }
+
+  // This returns the address of an object that has been described in the
+  // snapshot as being offset bytes back in a particular space.
+  HeapObject* GetAddressFromEnd(int space) {
+    int offset = source_->GetInt();
+    offset <<= kObjectAlignmentBits;
+    return HeapObject::FromAddress(high_water_[space] - offset);
+  }
+
 
   // Cached current isolate.
   Isolate* isolate_;
 
-  // Keep track of the pages in the paged spaces.
-  // (In large object space we are keeping track of individual objects
-  // rather than pages.)  In new space we just need the address of the
-  // first object and the others will flow from that.
-  List<Address> pages_[SerializerDeserializer::kNumberOfSpaces];
-
   SnapshotByteSource* source_;
   // This is the address of the next object that will be allocated in each
   // space.  It is used to calculate the addresses of back-references.
   Address high_water_[LAST_SPACE + 1];
-  // This is the address of the most recent object that was allocated.  It
-  // is used to set the location of the new page when we encounter a
-  // START_NEW_PAGE_SERIALIZATION tag.
-  Address last_object_address_;
+
+  intptr_t reservations_[LAST_SPACE + 1];
+  static const intptr_t kUninitializedReservation = -1;
 
   ExternalReferenceDecoder* external_reference_decoder_;
 
   DISALLOW_COPY_AND_ASSIGN(Deserializer);
 };
 
 
 class SnapshotByteSink {
  public:
   virtual ~SnapshotByteSink() { }
@@ skipping 61 matching lines @@
 
 // There can be only one serializer per V8 process.
 class Serializer : public SerializerDeserializer {
  public:
   explicit Serializer(SnapshotByteSink* sink);
   ~Serializer();
   void VisitPointers(Object** start, Object** end);
   // You can call this after serialization to find out how much space was used
   // in each space.
   int CurrentAllocationAddress(int space) {
-    if (SpaceIsLarge(space)) return large_object_total_;
+    ASSERT(space < kNumberOfSpaces);
     return fullness_[space];
   }
 
   static void Enable() {
     if (!serialization_enabled_) {
       ASSERT(!too_late_to_enable_now_);
     }
     serialization_enabled_ = true;
   }
 
   static void Disable() { serialization_enabled_ = false; }
   // Call this when you have made use of the fact that there is no serialization
   // going on.
   static void TooLateToEnableNow() { too_late_to_enable_now_ = true; }
   static bool enabled() { return serialization_enabled_; }
   SerializationAddressMapper* address_mapper() { return &address_mapper_; }
-  void PutRoot(
-      int index, HeapObject* object, HowToCode how, WhereToPoint where);
+  void PutRoot(int index,
+               HeapObject* object,
+               HowToCode how,
+               WhereToPoint where,
+               int skip);
 
  protected:
   static const int kInvalidRootIndex = -1;
 
   int RootIndex(HeapObject* heap_object, HowToCode from);
   virtual bool ShouldBeInThePartialSnapshotCache(HeapObject* o) = 0;
   intptr_t root_index_wave_front() { return root_index_wave_front_; }
   void set_root_index_wave_front(intptr_t value) {
     ASSERT(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),
         reference_representation_(how_to_code + where_to_point),
-        bytes_processed_so_far_(0) { }
+        bytes_processed_so_far_(0),
+        code_has_been_output_(false) {
+      code_object_ = o->IsCode();

[Yang, 2012/09/13 08:47:59]

I guess this could also be put into the initialization list.

[Erik Corry, 2012/09/13 12:13:35]

Done.

+    }
     void Serialize();
     void VisitPointers(Object** start, Object** end);
     void VisitEmbeddedPointer(RelocInfo* target);
     void VisitExternalReferences(Address* start, Address* end);
     void VisitExternalReference(RelocInfo* rinfo);
     void VisitCodeTarget(RelocInfo* target);
     void VisitCodeEntry(Address entry_address);
     void VisitGlobalPropertyCell(RelocInfo* rinfo);
     void VisitRuntimeEntry(RelocInfo* reloc);
     // Used for seralizing the external strings that hold the natives source.
     void VisitExternalAsciiString(
         v8::String::ExternalAsciiStringResource** resource);
     // We can't serialize a heap with external two byte strings.
     void VisitExternalTwoByteString(
         v8::String::ExternalStringResource** resource) {
       UNREACHABLE();
     }
 
    private:
-    void OutputRawData(Address up_to);
+    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);
 
     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) = 0;
+                               WhereToPoint where_to_point,
+                               int skip) = 0;
   void SerializeReferenceToPreviousObject(
       int space,
       int address,
       HowToCode how_to_code,
-      WhereToPoint where_to_point);
+      WhereToPoint where_to_point,
+      int skip);
   void InitializeAllocators();
-  // This will return the space for an object.  If the object is in large
-  // object space it may return kLargeCode or kLargeFixedArray in order
-  // to indicate to the deserializer what kind of large object allocation
-  // to make.
+  // This will return the space for an object.
   static int SpaceOfObject(HeapObject* object);
-  // This just returns the space of the object.  It will return LO_SPACE
-  // for all large objects since you can't check the type of the object
-  // once the map has been used for the serialization address.
-  static int SpaceOfAlreadySerializedObject(HeapObject* object);
-  int Allocate(int space, int size, bool* new_page_started);
+  int Allocate(int space, int size);
   int EncodeExternalReference(Address addr) {
     return external_reference_encoder_->Encode(addr);
   }
 
   int SpaceAreaSize(int space);
 
   Isolate* isolate_;
   // Keep track of the fullness of each space in order to generate
-  // relative addresses for back references.  Large objects are
-  // just numbered sequentially since relative addresses make no
-  // sense in large object space.
+  // relative addresses for back references.
   int fullness_[LAST_SPACE + 1];
   SnapshotByteSink* sink_;
   int current_root_index_;
   ExternalReferenceEncoder* external_reference_encoder_;
   static bool serialization_enabled_;
   // Did we already make use of the fact that serialization was not enabled?
   static bool too_late_to_enable_now_;
-  int large_object_total_;
   SerializationAddressMapper address_mapper_;
   intptr_t root_index_wave_front_;
+  void Pad();
 
   friend class ObjectSerializer;
   friend class Deserializer;
 
  private:
   DISALLOW_COPY_AND_ASSIGN(Serializer);
 };
 
 
 class PartialSerializer : public Serializer {
  public:
   PartialSerializer(Serializer* startup_snapshot_serializer,
                     SnapshotByteSink* sink)
     : Serializer(sink),
       startup_serializer_(startup_snapshot_serializer) {
     set_root_index_wave_front(Heap::kStrongRootListLength);
   }
 
   // Serialize the objects reachable from a single object pointer.
   virtual void Serialize(Object** o);
   virtual void SerializeObject(Object* o,
                                HowToCode how_to_code,
-                               WhereToPoint where_to_point);
+                               WhereToPoint where_to_point,
+                               int skip);
 
  protected:
   virtual int PartialSnapshotCacheIndex(HeapObject* o);
   virtual 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.
     ASSERT(!o->IsScript());
     return o->IsString() || o->IsSharedFunctionInfo() ||
@@ skipping 17 matching lines @@
     // snapshot.
     Isolate::Current()->set_serialize_partial_snapshot_cache_length(0);
   }
   // Serialize the current state of the heap.  The order is:
   // 1) Strong references.
   // 2) Partial snapshot cache.
   // 3) Weak references (e.g. the symbol table).
   virtual void SerializeStrongReferences();
   virtual void SerializeObject(Object* o,
                                HowToCode how_to_code,
-                               WhereToPoint where_to_point);
+                               WhereToPoint where_to_point,
+                               int skip);
   void SerializeWeakReferences();
   void Serialize() {
     SerializeStrongReferences();
     SerializeWeakReferences();
+    Pad();
   }
 
  private:
   virtual bool ShouldBeInThePartialSnapshotCache(HeapObject* o) {
     return false;
   }
 };
 
 
 } }  // namespace v8::internal
 
 #endif  // V8_SERIALIZE_H_