src/v8/src/serialize.h

   1 // Copyright 2012 the V8 project authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #ifndef V8_SERIALIZE_H_
   6 #define V8_SERIALIZE_H_
   7
   8 #include "hashmap.h"
   9
  10 namespace v8 {
  11 namespace internal {
  12
  13 // A TypeCode is used to distinguish different kinds of external reference.
  14 // It is a single bit to make testing for types easy.
  15 enum TypeCode {
  16   UNCLASSIFIED,        // One-of-a-kind references.
  17   BUILTIN,
  18   RUNTIME_FUNCTION,
  19   IC_UTILITY,
  20   DEBUG_ADDRESS,
  21   STATS_COUNTER,
  22   TOP_ADDRESS,
  23   C_BUILTIN,
  24   EXTENSION,
  25   ACCESSOR,
  26   RUNTIME_ENTRY,
  27   STUB_CACHE_TABLE,
  28   LAZY_DEOPTIMIZATION
  29 };
  30
  31 const int kTypeCodeCount = LAZY_DEOPTIMIZATION + 1;
  32 const int kFirstTypeCode = UNCLASSIFIED;
  33
  34 const int kReferenceIdBits = 16;
  35 const int kReferenceIdMask = (1 << kReferenceIdBits) - 1;
  36 const int kReferenceTypeShift = kReferenceIdBits;
  37 const int kDebugRegisterBits = 4;
  38 const int kDebugIdShift = kDebugRegisterBits;
  39
  40 const int kDeoptTableSerializeEntryCount = 12;
  41
  42 // ExternalReferenceTable is a helper class that defines the relationship
  43 // between external references and their encodings. It is used to build
  44 // hashmaps in ExternalReferenceEncoder and ExternalReferenceDecoder.
  45 class ExternalReferenceTable {
  46  public:
  47   static ExternalReferenceTable* instance(Isolate* isolate);
  48
  49   ~ExternalReferenceTable() { }
  50
  51   int size() const { return refs_.length(); }
  52
  53   Address address(int i) { return refs_[i].address; }
  54
  55   uint32_t code(int i) { return refs_[i].code; }
  56
  57   const char* name(int i) { return refs_[i].name; }
  58
  59   int max_id(int code) { return max_id_[code]; }
  60
  61  private:
  62   explicit ExternalReferenceTable(Isolate* isolate) : refs_(64) {
  63       PopulateTable(isolate);
  64   }
  65
  66   struct ExternalReferenceEntry {
  67     Address address;
  68     uint32_t code;
  69     const char* name;
  70   };
  71
  72   void PopulateTable(Isolate* isolate);
  73
  74   // For a few types of references, we can get their address from their id.
  75   void AddFromId(TypeCode type,
  76                  uint16_t id,
  77                  const char* name,
  78                  Isolate* isolate);
  79
  80   // For other types of references, the caller will figure out the address.
  81   void Add(Address address, TypeCode type, uint16_t id, const char* name);
  82
  83   List<ExternalReferenceEntry> refs_;
  84   int max_id_[kTypeCodeCount];
  85 };
  86
  87
  88 class ExternalReferenceEncoder {
  89  public:
  90   explicit ExternalReferenceEncoder(Isolate* isolate);
  91
  92   uint32_t Encode(Address key) const;
  93
  94   const char* NameOfAddress(Address key) const;
  95
  96  private:
  97   HashMap encodings_;
  98   static uint32_t Hash(Address key) {
  99     return static_cast<uint32_t>(reinterpret_cast<uintptr_t>(key) >> 2);
 100   }
 101
 102   int IndexOf(Address key) const;
 103
 104   void Put(Address key, int index);
 105
 106   Isolate* isolate_;
 107 };
 108
 109
 110 class ExternalReferenceDecoder {
 111  public:
 112   explicit ExternalReferenceDecoder(Isolate* isolate);
 113   ~ExternalReferenceDecoder();
 114
 115   Address Decode(uint32_t key) const {
 116     if (key == 0) return NULL;
 117     return *Lookup(key);
 118   }
 119
 120  private:
 121   Address** encodings_;
 122
 123   Address* Lookup(uint32_t key) const {
 124     int type = key >> kReferenceTypeShift;
 125     ASSERT(kFirstTypeCode <= type && type < kTypeCodeCount);
 126     int id = key & kReferenceIdMask;
 127     return &encodings_[type][id];
 128   }
 129
 130   void Put(uint32_t key, Address value) {
 131     *Lookup(key) = value;
 132   }
 133
 134   Isolate* isolate_;
 135 };
 136
 137
 138 class SnapshotByteSource {
 139  public:
 140   SnapshotByteSource(const byte* array, int length)
 141     : data_(array), length_(length), position_(0) { }
 142
 143   bool HasMore() { return position_ < length_; }
 144
 145   int Get() {
 146     ASSERT(position_ < length_);
 147     return data_[position_++];
 148   }
 149
 150   int32_t GetUnalignedInt() {
 151 #if defined(V8_HOST_CAN_READ_UNALIGNED) &&  __BYTE_ORDER == __LITTLE_ENDIAN
 152     int32_t answer;
 153     ASSERT(position_ + sizeof(answer) <= length_ + 0u);
 154     answer = *reinterpret_cast<const int32_t*>(data_ + position_);
 155 #else
 156     int32_t answer = data_[position_];
 157     answer |= data_[position_ + 1] << 8;
 158     answer |= data_[position_ + 2] << 16;
 159     answer |= data_[position_ + 3] << 24;
 160 #endif
 161     return answer;
 162   }
 163
 164   void Advance(int by) { position_ += by; }
 165
 166   inline void CopyRaw(byte* to, int number_of_bytes);
 167
 168   inline int GetInt();
 169
 170   bool AtEOF();
 171
 172   int position() { return position_; }
 173
 174  private:
 175   const byte* data_;
 176   int length_;
 177   int position_;
 178 };
 179
 180
 181 // The Serializer/Deserializer class is a common superclass for Serializer and
 182 // Deserializer which is used to store common constants and methods used by
 183 // both.
 184 class SerializerDeserializer: public ObjectVisitor {
 185  public:
 186   static void Iterate(Isolate* isolate, ObjectVisitor* visitor);
 187
 188   static int nop() { return kNop; }
 189
 190  protected:
 191   // Where the pointed-to object can be found:
 192   enum Where {
 193     kNewObject = 0,                 // Object is next in snapshot.
 194     // 1-6                             One per space.
 195     kRootArray = 0x9,               // Object is found in root array.
 196     kPartialSnapshotCache = 0xa,    // Object is in the cache.
 197     kExternalReference = 0xb,       // Pointer to an external reference.
 198     kSkip = 0xc,                    // Skip n bytes.
 199     kNop = 0xd,                     // Does nothing, used to pad.
 200     // 0xe-0xf                         Free.
 201     kBackref = 0x10,                // Object is described relative to end.
 202     // 0x11-0x16                       One per space.
 203     kBackrefWithSkip = 0x18,        // Object is described relative to end.
 204     // 0x19-0x1e                       One per space.
 205     // 0x20-0x3f                       Used by misc. tags below.
 206     kPointedToMask = 0x3f
 207   };
 208
 209   // How to code the pointer to the object.
 210   enum HowToCode {
 211     kPlain = 0,                          // Straight pointer.
 212     // What this means depends on the architecture:
 213     kFromCode = 0x40,                    // A pointer inlined in code.
 214     kHowToCodeMask = 0x40
 215   };
 216
 217   // For kRootArrayConstants
 218   enum WithSkip {
 219     kNoSkipDistance = 0,
 220     kHasSkipDistance = 0x40,
 221     kWithSkipMask = 0x40
 222   };
 223
 224   // Where to point within the object.
 225   enum WhereToPoint {
 226     kStartOfObject = 0,
 227     kInnerPointer = 0x80,  // First insn in code object or payload of cell.
 228     kWhereToPointMask = 0x80
 229   };
 230
 231   // Misc.
 232   // Raw data to be copied from the snapshot.  This byte code does not advance
 233   // the current pointer, which is used for code objects, where we write the
 234   // entire code in one memcpy, then fix up stuff with kSkip and other byte
 235   // codes that overwrite data.
 236   static const int kRawData = 0x20;
 237   // Some common raw lengths: 0x21-0x3f.  These autoadvance the current pointer.
 238   // A tag emitted at strategic points in the snapshot to delineate sections.
 239   // If the deserializer does not find these at the expected moments then it
 240   // is an indication that the snapshot and the VM do not fit together.
 241   // Examine the build process for architecture, version or configuration
 242   // mismatches.
 243   static const int kSynchronize = 0x70;
 244   // Used for the source code of the natives, which is in the executable, but
 245   // is referred to from external strings in the snapshot.
 246   static const int kNativesStringResource = 0x71;
 247   static const int kRepeat = 0x72;
 248   static const int kConstantRepeat = 0x73;
 249   // 0x73-0x7f            Repeat last word (subtract 0x72 to get the count).
 250   static const int kMaxRepeats = 0x7f - 0x72;
 251   static int CodeForRepeats(int repeats) {
 252     ASSERT(repeats >= 1 && repeats <= kMaxRepeats);
 253     return 0x72 + repeats;
 254   }
 255   static int RepeatsForCode(int byte_code) {
 256     ASSERT(byte_code >= kConstantRepeat && byte_code <= 0x7f);
 257     return byte_code - 0x72;
 258   }
 259   static const int kRootArrayConstants = 0xa0;
 260   // 0xa0-0xbf            Things from the first 32 elements of the root array.
 261   static const int kRootArrayNumberOfConstantEncodings = 0x20;
 262   static int RootArrayConstantFromByteCode(int byte_code) {
 263     return byte_code & 0x1f;
 264   }
 265
 266   static const int kNumberOfSpaces = LO_SPACE;
 267   static const int kAnyOldSpace = -1;
 268
 269   // A bitmask for getting the space out of an instruction.
 270   static const int kSpaceMask = 7;
 271 };
 272
 273
 274 int SnapshotByteSource::GetInt() {
 275   // This way of variable-length encoding integers does not suffer from branch
 276   // mispredictions.
 277   uint32_t answer = GetUnalignedInt();
 278   int bytes = answer & 3;
 279   Advance(bytes);
 280   uint32_t mask = 0xffffffffu;
 281   mask >>= 32 - (bytes << 3);
 282   answer &= mask;
 283   answer >>= 2;
 284   return answer;
 285 }
 286
 287
 288 void SnapshotByteSource::CopyRaw(byte* to, int number_of_bytes) {
 289   OS::MemCopy(to, data_ + position_, number_of_bytes);
 290   position_ += number_of_bytes;
 291 }
 292
 293
 294 // A Deserializer reads a snapshot and reconstructs the Object graph it defines.
 295 class Deserializer: public SerializerDeserializer {
 296  public:
 297   // Create a deserializer from a snapshot byte source.
 298   explicit Deserializer(SnapshotByteSource* source);
 299
 300   virtual ~Deserializer();
 301
 302   // Deserialize the snapshot into an empty heap.
 303   void Deserialize(Isolate* isolate);
 304
 305   // Deserialize a single object and the objects reachable from it.
 306   void DeserializePartial(Isolate* isolate, Object** root);
 307
 308   void set_reservation(int space_number, int reservation) {
 309     ASSERT(space_number >= 0);
 310     ASSERT(space_number <= LAST_SPACE);
 311     reservations_[space_number] = reservation;
 312   }
 313
 314  private:
 315   virtual void VisitPointers(Object** start, Object** end);
 316
 317   virtual void VisitRuntimeEntry(RelocInfo* rinfo) {
 318     UNREACHABLE();
 319   }
 320
 321   // Allocation sites are present in the snapshot, and must be linked into
 322   // a list at deserialization time.
 323   void RelinkAllocationSite(AllocationSite* site);
 324
 325   // Fills in some heap data in an area from start to end (non-inclusive).  The
 326   // space id is used for the write barrier.  The object_address is the address
 327   // of the object we are writing into, or NULL if we are not writing into an
 328   // object, i.e. if we are writing a series of tagged values that are not on
 329   // the heap.
 330   void ReadChunk(
 331       Object** start, Object** end, int space, Address object_address);
 332   void ReadObject(int space_number, Object** write_back);
 333
 334   // This routine both allocates a new object, and also keeps
 335   // track of where objects have been allocated so that we can
 336   // fix back references when deserializing.
 337   Address Allocate(int space_index, int size) {
 338     Address address = high_water_[space_index];
 339     high_water_[space_index] = address + size;
 340     HeapProfiler* profiler = isolate_->heap_profiler();
 341     if (profiler->is_tracking_allocations()) {
 342       profiler->AllocationEvent(address, size);
 343     }
 344     return address;
 345   }
 346
 347   // This returns the address of an object that has been described in the
 348   // snapshot as being offset bytes back in a particular space.
 349   HeapObject* GetAddressFromEnd(int space) {
 350     int offset = source_->GetInt();
 351     offset <<= kObjectAlignmentBits;
 352     return HeapObject::FromAddress(high_water_[space] - offset);
 353   }
 354
 355   void FlushICacheForNewCodeObjects();
 356
 357   // Cached current isolate.
 358   Isolate* isolate_;
 359
 360   SnapshotByteSource* source_;
 361   // This is the address of the next object that will be allocated in each
 362   // space.  It is used to calculate the addresses of back-references.
 363   Address high_water_[LAST_SPACE + 1];
 364
 365   int reservations_[LAST_SPACE + 1];
 366   static const intptr_t kUninitializedReservation = -1;
 367
 368   ExternalReferenceDecoder* external_reference_decoder_;
 369
 370   DISALLOW_COPY_AND_ASSIGN(Deserializer);
 371 };
 372
 373
 374 class SnapshotByteSink {
 375  public:
 376   virtual ~SnapshotByteSink() { }
 377   virtual void Put(int byte, const char* description) = 0;
 378   virtual void PutSection(int byte, const char* description) {
 379     Put(byte, description);
 380   }
 381   void PutInt(uintptr_t integer, const char* description);
 382   virtual int Position() = 0;
 383 };
 384
 385
 386 // Mapping objects to their location after deserialization.
 387 // This is used during building, but not at runtime by V8.
 388 class SerializationAddressMapper {
 389  public:
 390   SerializationAddressMapper()
 391       : no_allocation_(),
 392         serialization_map_(new HashMap(HashMap::PointersMatch)) { }
 393
 394   ~SerializationAddressMapper() {
 395     delete serialization_map_;
 396   }
 397
 398   bool IsMapped(HeapObject* obj) {
 399     return serialization_map_->Lookup(Key(obj), Hash(obj), false) != NULL;
 400   }
 401
 402   int MappedTo(HeapObject* obj) {
 403     ASSERT(IsMapped(obj));
 404     return static_cast<int>(reinterpret_cast<intptr_t>(
 405         serialization_map_->Lookup(Key(obj), Hash(obj), false)->value));
 406   }
 407
 408   void AddMapping(HeapObject* obj, int to) {
 409     ASSERT(!IsMapped(obj));
 410     HashMap::Entry* entry =
 411         serialization_map_->Lookup(Key(obj), Hash(obj), true);
 412     entry->value = Value(to);
 413   }
 414
 415  private:
 416   static uint32_t Hash(HeapObject* obj) {
 417     return static_cast<int32_t>(reinterpret_cast<intptr_t>(obj->address()));
 418   }
 419
 420   static void* Key(HeapObject* obj) {
 421     return reinterpret_cast<void*>(obj->address());
 422   }
 423
 424   static void* Value(int v) {
 425     return reinterpret_cast<void*>(v);
 426   }
 427
 428   DisallowHeapAllocation no_allocation_;
 429   HashMap* serialization_map_;
 430   DISALLOW_COPY_AND_ASSIGN(SerializationAddressMapper);
 431 };
 432
 433
 434 class CodeAddressMap;
 435
 436 // There can be only one serializer per V8 process.
 437 class Serializer : public SerializerDeserializer {
 438  public:
 439   Serializer(Isolate* isolate, SnapshotByteSink* sink);
 440   ~Serializer();
 441   void VisitPointers(Object** start, Object** end);
 442   // You can call this after serialization to find out how much space was used
 443   // in each space.
 444   int CurrentAllocationAddress(int space) const {
 445     ASSERT(space < kNumberOfSpaces);
 446     return fullness_[space];
 447   }
 448
 449   Isolate* isolate() const { return isolate_; }
 450   static void RequestEnable(Isolate* isolate);
 451   static void InitializeOncePerProcess();
 452   static void TearDown();
 453
 454   static bool enabled(Isolate* isolate) {
 455     SerializationState state = static_cast<SerializationState>(
 456         NoBarrier_Load(&serialization_state_));
 457     ASSERT(state != SERIALIZER_STATE_UNINITIALIZED);
 458     return state == SERIALIZER_STATE_ENABLED;
 459   }
 460   SerializationAddressMapper* address_mapper() { return &address_mapper_; }
 461   void PutRoot(int index,
 462                HeapObject* object,
 463                HowToCode how,
 464                WhereToPoint where,
 465                int skip);
 466
 467  protected:
 468   static const int kInvalidRootIndex = -1;
 469
 470   int RootIndex(HeapObject* heap_object, HowToCode from);
 471   virtual bool ShouldBeInThePartialSnapshotCache(HeapObject* o) = 0;
 472   intptr_t root_index_wave_front() { return root_index_wave_front_; }
 473   void set_root_index_wave_front(intptr_t value) {
 474     ASSERT(value >= root_index_wave_front_);
 475     root_index_wave_front_ = value;
 476   }
 477
 478   class ObjectSerializer : public ObjectVisitor {
 479    public:
 480     ObjectSerializer(Serializer* serializer,
 481                      Object* o,
 482                      SnapshotByteSink* sink,
 483                      HowToCode how_to_code,
 484                      WhereToPoint where_to_point)
 485       : serializer_(serializer),
 486         object_(HeapObject::cast(o)),
 487         sink_(sink),
 488         reference_representation_(how_to_code + where_to_point),
 489         bytes_processed_so_far_(0),
 490         code_object_(o->IsCode()),
 491         code_has_been_output_(false) { }
 492     void Serialize();
 493     void VisitPointers(Object** start, Object** end);
 494     void VisitEmbeddedPointer(RelocInfo* target);
 495     void VisitExternalReference(Address* p);
 496     void VisitExternalReference(RelocInfo* rinfo);
 497     void VisitCodeTarget(RelocInfo* target);
 498     void VisitCodeEntry(Address entry_address);
 499     void VisitCell(RelocInfo* rinfo);
 500     void VisitRuntimeEntry(RelocInfo* reloc);
 501     // Used for seralizing the external strings that hold the natives source.
 502     void VisitExternalAsciiString(
 503         v8::String::ExternalAsciiStringResource** resource);
 504     // We can't serialize a heap with external two byte strings.
 505     void VisitExternalTwoByteString(
 506         v8::String::ExternalStringResource** resource) {
 507       UNREACHABLE();
 508     }
 509
 510    private:
 511     enum ReturnSkip { kCanReturnSkipInsteadOfSkipping, kIgnoringReturn };
 512     // This function outputs or skips the raw data between the last pointer and
 513     // up to the current position.  It optionally can just return the number of
 514     // bytes to skip instead of performing a skip instruction, in case the skip
 515     // can be merged into the next instruction.
 516     int OutputRawData(Address up_to, ReturnSkip return_skip = kIgnoringReturn);
 517
 518     Serializer* serializer_;
 519     HeapObject* object_;
 520     SnapshotByteSink* sink_;
 521     int reference_representation_;
 522     int bytes_processed_so_far_;
 523     bool code_object_;
 524     bool code_has_been_output_;
 525   };
 526
 527   virtual void SerializeObject(Object* o,
 528                                HowToCode how_to_code,
 529                                WhereToPoint where_to_point,
 530                                int skip) = 0;
 531   void SerializeReferenceToPreviousObject(
 532       int space,
 533       int address,
 534       HowToCode how_to_code,
 535       WhereToPoint where_to_point,
 536       int skip);
 537   void InitializeAllocators();
 538   // This will return the space for an object.
 539   static int SpaceOfObject(HeapObject* object);
 540   int Allocate(int space, int size);
 541   int EncodeExternalReference(Address addr) {
 542     return external_reference_encoder_->Encode(addr);
 543   }
 544
 545   int SpaceAreaSize(int space);
 546
 547   // Some roots should not be serialized, because their actual value depends on
 548   // absolute addresses and they are reset after deserialization, anyway.
 549   bool ShouldBeSkipped(Object** current);
 550
 551   Isolate* isolate_;
 552   // Keep track of the fullness of each space in order to generate
 553   // relative addresses for back references.
 554   int fullness_[LAST_SPACE + 1];
 555   SnapshotByteSink* sink_;
 556   ExternalReferenceEncoder* external_reference_encoder_;
 557
 558   enum SerializationState {
 559     SERIALIZER_STATE_UNINITIALIZED = 0,
 560     SERIALIZER_STATE_DISABLED = 1,
 561     SERIALIZER_STATE_ENABLED = 2
 562   };
 563
 564   static AtomicWord serialization_state_;
 565
 566   SerializationAddressMapper address_mapper_;
 567   intptr_t root_index_wave_front_;
 568   void Pad();
 569
 570   friend class ObjectSerializer;
 571   friend class Deserializer;
 572
 573  private:
 574   static CodeAddressMap* code_address_map_;
 575   DISALLOW_COPY_AND_ASSIGN(Serializer);
 576 };
 577
 578
 579 class PartialSerializer : public Serializer {
 580  public:
 581   PartialSerializer(Isolate* isolate,
 582                     Serializer* startup_snapshot_serializer,
 583                     SnapshotByteSink* sink)
 584     : Serializer(isolate, sink),
 585       startup_serializer_(startup_snapshot_serializer) {
 586     set_root_index_wave_front(Heap::kStrongRootListLength);
 587   }
 588
 589   // Serialize the objects reachable from a single object pointer.
 590   virtual void Serialize(Object** o);
 591   virtual void SerializeObject(Object* o,
 592                                HowToCode how_to_code,
 593                                WhereToPoint where_to_point,
 594                                int skip);
 595
 596  protected:
 597   virtual int PartialSnapshotCacheIndex(HeapObject* o);
 598   virtual bool ShouldBeInThePartialSnapshotCache(HeapObject* o) {
 599     // Scripts should be referred only through shared function infos.  We can't
 600     // allow them to be part of the partial snapshot because they contain a
 601     // unique ID, and deserializing several partial snapshots containing script
 602     // would cause dupes.
 603     ASSERT(!o->IsScript());
 604     return o->IsName() || o->IsSharedFunctionInfo() ||
 605            o->IsHeapNumber() || o->IsCode() ||
 606            o->IsScopeInfo() ||
 607            o->map() ==
 608                startup_serializer_->isolate()->heap()->fixed_cow_array_map();
 609   }
 610
 611  private:
 612   Serializer* startup_serializer_;
 613   DISALLOW_COPY_AND_ASSIGN(PartialSerializer);
 614 };
 615
 616
 617 class StartupSerializer : public Serializer {
 618  public:
 619   StartupSerializer(Isolate* isolate, SnapshotByteSink* sink)
 620     : Serializer(isolate, sink) {
 621     // Clear the cache of objects used by the partial snapshot.  After the
 622     // strong roots have been serialized we can create a partial snapshot
 623     // which will repopulate the cache with objects needed by that partial
 624     // snapshot.
 625     isolate->set_serialize_partial_snapshot_cache_length(0);
 626   }
 627   // Serialize the current state of the heap.  The order is:
 628   // 1) Strong references.
 629   // 2) Partial snapshot cache.
 630   // 3) Weak references (e.g. the string table).
 631   virtual void SerializeStrongReferences();
 632   virtual void SerializeObject(Object* o,
 633                                HowToCode how_to_code,
 634                                WhereToPoint where_to_point,
 635                                int skip);
 636   void SerializeWeakReferences();
 637   void Serialize() {
 638     SerializeStrongReferences();
 639     SerializeWeakReferences();
 640     Pad();
 641   }
 642
 643  private:
 644   virtual bool ShouldBeInThePartialSnapshotCache(HeapObject* o) {
 645     return false;
 646   }
 647 };
 648
 649
 650 } }  // namespace v8::internal
 651
 652 #endif  // V8_SERIALIZE_H_