serialize.h revision 6ded16be15dd865a9b21ea304d5273c8be299c87
1// Copyright 2006-2009 the V8 project authors. All rights reserved. 2// Redistribution and use in source and binary forms, with or without 3// modification, are permitted provided that the following conditions are 4// met: 5// 6// * Redistributions of source code must retain the above copyright 7// notice, this list of conditions and the following disclaimer. 8// * Redistributions in binary form must reproduce the above 9// copyright notice, this list of conditions and the following 10// disclaimer in the documentation and/or other materials provided 11// with the distribution. 12// * Neither the name of Google Inc. nor the names of its 13// contributors may be used to endorse or promote products derived 14// from this software without specific prior written permission. 15// 16// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 17// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 18// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 19// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 20// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 21// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 22// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 26// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27 28#ifndef V8_SERIALIZE_H_ 29#define V8_SERIALIZE_H_ 30 31#include "hashmap.h" 32 33namespace v8 { 34namespace internal { 35 36// A TypeCode is used to distinguish different kinds of external reference. 37// It is a single bit to make testing for types easy. 38enum TypeCode { 39 UNCLASSIFIED, // One-of-a-kind references. 40 BUILTIN, 41 RUNTIME_FUNCTION, 42 IC_UTILITY, 43 DEBUG_ADDRESS, 44 STATS_COUNTER, 45 TOP_ADDRESS, 46 C_BUILTIN, 47 EXTENSION, 48 ACCESSOR, 49 RUNTIME_ENTRY, 50 STUB_CACHE_TABLE 51}; 52 53const int kTypeCodeCount = STUB_CACHE_TABLE + 1; 54const int kFirstTypeCode = UNCLASSIFIED; 55 56const int kReferenceIdBits = 16; 57const int kReferenceIdMask = (1 << kReferenceIdBits) - 1; 58const int kReferenceTypeShift = kReferenceIdBits; 59const int kDebugRegisterBits = 4; 60const int kDebugIdShift = kDebugRegisterBits; 61 62 63class ExternalReferenceEncoder { 64 public: 65 ExternalReferenceEncoder(); 66 67 uint32_t Encode(Address key) const; 68 69 const char* NameOfAddress(Address key) const; 70 71 private: 72 HashMap encodings_; 73 static uint32_t Hash(Address key) { 74 return static_cast<uint32_t>(reinterpret_cast<uintptr_t>(key) >> 2); 75 } 76 77 int IndexOf(Address key) const; 78 79 static bool Match(void* key1, void* key2) { return key1 == key2; } 80 81 void Put(Address key, int index); 82}; 83 84 85class ExternalReferenceDecoder { 86 public: 87 ExternalReferenceDecoder(); 88 ~ExternalReferenceDecoder(); 89 90 Address Decode(uint32_t key) const { 91 if (key == 0) return NULL; 92 return *Lookup(key); 93 } 94 95 private: 96 Address** encodings_; 97 98 Address* Lookup(uint32_t key) const { 99 int type = key >> kReferenceTypeShift; 100 ASSERT(kFirstTypeCode <= type && type < kTypeCodeCount); 101 int id = key & kReferenceIdMask; 102 return &encodings_[type][id]; 103 } 104 105 void Put(uint32_t key, Address value) { 106 *Lookup(key) = value; 107 } 108}; 109 110 111class SnapshotByteSource { 112 public: 113 SnapshotByteSource(const byte* array, int length) 114 : data_(array), length_(length), position_(0) { } 115 116 bool HasMore() { return position_ < length_; } 117 118 int Get() { 119 ASSERT(position_ < length_); 120 return data_[position_++]; 121 } 122 123 inline void CopyRaw(byte* to, int number_of_bytes); 124 125 inline int GetInt(); 126 127 bool AtEOF() { 128 return position_ == length_; 129 } 130 131 int position() { return position_; } 132 133 private: 134 const byte* data_; 135 int length_; 136 int position_; 137}; 138 139 140// It is very common to have a reference to the object at word 10 in space 2, 141// the object at word 5 in space 2 and the object at word 28 in space 4. This 142// only works for objects in the first page of a space. 143#define COMMON_REFERENCE_PATTERNS(f) \ 144 f(kNumberOfSpaces, 2, 10) \ 145 f(kNumberOfSpaces + 1, 2, 5) \ 146 f(kNumberOfSpaces + 2, 4, 28) \ 147 f(kNumberOfSpaces + 3, 2, 21) \ 148 f(kNumberOfSpaces + 4, 2, 98) \ 149 f(kNumberOfSpaces + 5, 2, 67) \ 150 f(kNumberOfSpaces + 6, 4, 132) 151 152#define COMMON_RAW_LENGTHS(f) \ 153 f(1, 1) \ 154 f(2, 2) \ 155 f(3, 3) \ 156 f(4, 4) \ 157 f(5, 5) \ 158 f(6, 6) \ 159 f(7, 7) \ 160 f(8, 8) \ 161 f(9, 12) \ 162 f(10, 16) \ 163 f(11, 20) \ 164 f(12, 24) \ 165 f(13, 28) \ 166 f(14, 32) \ 167 f(15, 36) 168 169// The Serializer/Deserializer class is a common superclass for Serializer and 170// Deserializer which is used to store common constants and methods used by 171// both. 172class SerializerDeserializer: public ObjectVisitor { 173 public: 174 static void Iterate(ObjectVisitor* visitor); 175 static void SetSnapshotCacheSize(int size); 176 177 protected: 178 enum DataType { 179 RAW_DATA_SERIALIZATION = 0, 180 // And 15 common raw lengths. 181 OBJECT_SERIALIZATION = 16, 182 // One variant per space. 183 CODE_OBJECT_SERIALIZATION = 25, 184 // One per space (only code spaces in use). 185 EXTERNAL_REFERENCE_SERIALIZATION = 34, 186 EXTERNAL_BRANCH_TARGET_SERIALIZATION = 35, 187 SYNCHRONIZE = 36, 188 START_NEW_PAGE_SERIALIZATION = 37, 189 NATIVES_STRING_RESOURCE = 38, 190 ROOT_SERIALIZATION = 39, 191 PARTIAL_SNAPSHOT_CACHE_ENTRY = 40, 192 // Free: 41-47. 193 BACKREF_SERIALIZATION = 48, 194 // One per space, must be kSpaceMask aligned. 195 // Free: 57-63. 196 REFERENCE_SERIALIZATION = 64, 197 // One per space and common references. Must be kSpaceMask aligned. 198 CODE_BACKREF_SERIALIZATION = 80, 199 // One per space, must be kSpaceMask aligned. 200 // Free: 89-95. 201 CODE_REFERENCE_SERIALIZATION = 96 202 // One per space, must be kSpaceMask aligned. 203 // Free: 105-255. 204 }; 205 static const int kLargeData = LAST_SPACE; 206 static const int kLargeCode = kLargeData + 1; 207 static const int kLargeFixedArray = kLargeCode + 1; 208 static const int kNumberOfSpaces = kLargeFixedArray + 1; 209 210 // A bitmask for getting the space out of an instruction. 211 static const int kSpaceMask = 15; 212 213 static inline bool SpaceIsLarge(int space) { return space >= kLargeData; } 214 static inline bool SpaceIsPaged(int space) { 215 return space >= FIRST_PAGED_SPACE && space <= LAST_PAGED_SPACE; 216 } 217 218 static int partial_snapshot_cache_length_; 219 static const int kPartialSnapshotCacheCapacity = 1300; 220 static Object* partial_snapshot_cache_[]; 221}; 222 223 224int SnapshotByteSource::GetInt() { 225 // A little unwind to catch the really small ints. 226 int snapshot_byte = Get(); 227 if ((snapshot_byte & 0x80) == 0) { 228 return snapshot_byte; 229 } 230 int accumulator = (snapshot_byte & 0x7f) << 7; 231 while (true) { 232 snapshot_byte = Get(); 233 if ((snapshot_byte & 0x80) == 0) { 234 return accumulator | snapshot_byte; 235 } 236 accumulator = (accumulator | (snapshot_byte & 0x7f)) << 7; 237 } 238 UNREACHABLE(); 239 return accumulator; 240} 241 242 243void SnapshotByteSource::CopyRaw(byte* to, int number_of_bytes) { 244 memcpy(to, data_ + position_, number_of_bytes); 245 position_ += number_of_bytes; 246} 247 248 249// A Deserializer reads a snapshot and reconstructs the Object graph it defines. 250class Deserializer: public SerializerDeserializer { 251 public: 252 // Create a deserializer from a snapshot byte source. 253 explicit Deserializer(SnapshotByteSource* source); 254 255 virtual ~Deserializer(); 256 257 // Deserialize the snapshot into an empty heap. 258 void Deserialize(); 259 260 // Deserialize a single object and the objects reachable from it. 261 void DeserializePartial(Object** root); 262 263#ifdef DEBUG 264 virtual void Synchronize(const char* tag); 265#endif 266 267 private: 268 virtual void VisitPointers(Object** start, Object** end); 269 270 virtual void VisitExternalReferences(Address* start, Address* end) { 271 UNREACHABLE(); 272 } 273 274 virtual void VisitRuntimeEntry(RelocInfo* rinfo) { 275 UNREACHABLE(); 276 } 277 278 void ReadChunk(Object** start, Object** end, int space, Address address); 279 HeapObject* GetAddressFromStart(int space); 280 inline HeapObject* GetAddressFromEnd(int space); 281 Address Allocate(int space_number, Space* space, int size); 282 void ReadObject(int space_number, Space* space, Object** write_back); 283 284 // Keep track of the pages in the paged spaces. 285 // (In large object space we are keeping track of individual objects 286 // rather than pages.) In new space we just need the address of the 287 // first object and the others will flow from that. 288 List<Address> pages_[SerializerDeserializer::kNumberOfSpaces]; 289 290 SnapshotByteSource* source_; 291 static ExternalReferenceDecoder* external_reference_decoder_; 292 // This is the address of the next object that will be allocated in each 293 // space. It is used to calculate the addresses of back-references. 294 Address high_water_[LAST_SPACE + 1]; 295 // This is the address of the most recent object that was allocated. It 296 // is used to set the location of the new page when we encounter a 297 // START_NEW_PAGE_SERIALIZATION tag. 298 Address last_object_address_; 299 300 DISALLOW_COPY_AND_ASSIGN(Deserializer); 301}; 302 303 304class SnapshotByteSink { 305 public: 306 virtual ~SnapshotByteSink() { } 307 virtual void Put(int byte, const char* description) = 0; 308 virtual void PutSection(int byte, const char* description) { 309 Put(byte, description); 310 } 311 void PutInt(uintptr_t integer, const char* description); 312 virtual int Position() = 0; 313}; 314 315 316// Mapping objects to their location after deserialization. 317// This is used during building, but not at runtime by V8. 318class SerializationAddressMapper { 319 public: 320 SerializationAddressMapper() 321 : serialization_map_(new HashMap(&SerializationMatchFun)), 322 no_allocation_(new AssertNoAllocation()) { } 323 324 ~SerializationAddressMapper() { 325 delete serialization_map_; 326 delete no_allocation_; 327 } 328 329 bool IsMapped(HeapObject* obj) { 330 return serialization_map_->Lookup(Key(obj), Hash(obj), false) != NULL; 331 } 332 333 int MappedTo(HeapObject* obj) { 334 ASSERT(IsMapped(obj)); 335 return static_cast<int>(reinterpret_cast<intptr_t>( 336 serialization_map_->Lookup(Key(obj), Hash(obj), false)->value)); 337 } 338 339 void AddMapping(HeapObject* obj, int to) { 340 ASSERT(!IsMapped(obj)); 341 HashMap::Entry* entry = 342 serialization_map_->Lookup(Key(obj), Hash(obj), true); 343 entry->value = Value(to); 344 } 345 346 private: 347 static bool SerializationMatchFun(void* key1, void* key2) { 348 return key1 == key2; 349 } 350 351 static uint32_t Hash(HeapObject* obj) { 352 return static_cast<int32_t>(reinterpret_cast<intptr_t>(obj->address())); 353 } 354 355 static void* Key(HeapObject* obj) { 356 return reinterpret_cast<void*>(obj->address()); 357 } 358 359 static void* Value(int v) { 360 return reinterpret_cast<void*>(v); 361 } 362 363 HashMap* serialization_map_; 364 AssertNoAllocation* no_allocation_; 365 DISALLOW_COPY_AND_ASSIGN(SerializationAddressMapper); 366}; 367 368 369class Serializer : public SerializerDeserializer { 370 public: 371 explicit Serializer(SnapshotByteSink* sink); 372 ~Serializer(); 373 void VisitPointers(Object** start, Object** end); 374 // You can call this after serialization to find out how much space was used 375 // in each space. 376 int CurrentAllocationAddress(int space) { 377 if (SpaceIsLarge(space)) return large_object_total_; 378 return fullness_[space]; 379 } 380 381 static void Enable() { 382 if (!serialization_enabled_) { 383 ASSERT(!too_late_to_enable_now_); 384 } 385 serialization_enabled_ = true; 386 } 387 388 static void Disable() { serialization_enabled_ = false; } 389 // Call this when you have made use of the fact that there is no serialization 390 // going on. 391 static void TooLateToEnableNow() { too_late_to_enable_now_ = true; } 392 static bool enabled() { return serialization_enabled_; } 393 SerializationAddressMapper* address_mapper() { return &address_mapper_; } 394#ifdef DEBUG 395 virtual void Synchronize(const char* tag); 396#endif 397 398 protected: 399 enum ReferenceRepresentation { 400 TAGGED_REPRESENTATION, // A tagged object reference. 401 CODE_TARGET_REPRESENTATION // A reference to first instruction in target. 402 }; 403 static const int kInvalidRootIndex = -1; 404 virtual int RootIndex(HeapObject* heap_object) = 0; 405 virtual bool ShouldBeInThePartialSnapshotCache(HeapObject* o) = 0; 406 407 class ObjectSerializer : public ObjectVisitor { 408 public: 409 ObjectSerializer(Serializer* serializer, 410 Object* o, 411 SnapshotByteSink* sink, 412 ReferenceRepresentation representation) 413 : serializer_(serializer), 414 object_(HeapObject::cast(o)), 415 sink_(sink), 416 reference_representation_(representation), 417 bytes_processed_so_far_(0) { } 418 void Serialize(); 419 void VisitPointers(Object** start, Object** end); 420 void VisitExternalReferences(Address* start, Address* end); 421 void VisitCodeTarget(RelocInfo* target); 422 void VisitRuntimeEntry(RelocInfo* reloc); 423 // Used for seralizing the external strings that hold the natives source. 424 void VisitExternalAsciiString( 425 v8::String::ExternalAsciiStringResource** resource); 426 // We can't serialize a heap with external two byte strings. 427 void VisitExternalTwoByteString( 428 v8::String::ExternalStringResource** resource) { 429 UNREACHABLE(); 430 } 431 432 private: 433 void OutputRawData(Address up_to); 434 435 Serializer* serializer_; 436 HeapObject* object_; 437 SnapshotByteSink* sink_; 438 ReferenceRepresentation reference_representation_; 439 int bytes_processed_so_far_; 440 }; 441 442 virtual void SerializeObject(Object* o, 443 ReferenceRepresentation representation) = 0; 444 void SerializeReferenceToPreviousObject( 445 int space, 446 int address, 447 ReferenceRepresentation reference_representation); 448 void InitializeAllocators(); 449 // This will return the space for an object. If the object is in large 450 // object space it may return kLargeCode or kLargeFixedArray in order 451 // to indicate to the deserializer what kind of large object allocation 452 // to make. 453 static int SpaceOfObject(HeapObject* object); 454 // This just returns the space of the object. It will return LO_SPACE 455 // for all large objects since you can't check the type of the object 456 // once the map has been used for the serialization address. 457 static int SpaceOfAlreadySerializedObject(HeapObject* object); 458 int Allocate(int space, int size, bool* new_page_started); 459 int EncodeExternalReference(Address addr) { 460 return external_reference_encoder_->Encode(addr); 461 } 462 463 // Keep track of the fullness of each space in order to generate 464 // relative addresses for back references. Large objects are 465 // just numbered sequentially since relative addresses make no 466 // sense in large object space. 467 int fullness_[LAST_SPACE + 1]; 468 SnapshotByteSink* sink_; 469 int current_root_index_; 470 ExternalReferenceEncoder* external_reference_encoder_; 471 static bool serialization_enabled_; 472 // Did we already make use of the fact that serialization was not enabled? 473 static bool too_late_to_enable_now_; 474 int large_object_total_; 475 SerializationAddressMapper address_mapper_; 476 477 friend class ObjectSerializer; 478 friend class Deserializer; 479 480 DISALLOW_COPY_AND_ASSIGN(Serializer); 481}; 482 483 484class PartialSerializer : public Serializer { 485 public: 486 PartialSerializer(Serializer* startup_snapshot_serializer, 487 SnapshotByteSink* sink) 488 : Serializer(sink), 489 startup_serializer_(startup_snapshot_serializer) { 490 } 491 492 // Serialize the objects reachable from a single object pointer. 493 virtual void Serialize(Object** o); 494 virtual void SerializeObject(Object* o, 495 ReferenceRepresentation representation); 496 497 protected: 498 virtual int RootIndex(HeapObject* o); 499 virtual int PartialSnapshotCacheIndex(HeapObject* o); 500 virtual bool ShouldBeInThePartialSnapshotCache(HeapObject* o) { 501 // Scripts should be referred only through shared function infos. We can't 502 // allow them to be part of the partial snapshot because they contain a 503 // unique ID, and deserializing several partial snapshots containing script 504 // would cause dupes. 505 ASSERT(!o->IsScript()); 506 return o->IsString() || o->IsSharedFunctionInfo() || 507 o->IsHeapNumber() || o->IsCode(); 508 } 509 510 private: 511 Serializer* startup_serializer_; 512 DISALLOW_COPY_AND_ASSIGN(PartialSerializer); 513}; 514 515 516class StartupSerializer : public Serializer { 517 public: 518 explicit StartupSerializer(SnapshotByteSink* sink) : Serializer(sink) { 519 // Clear the cache of objects used by the partial snapshot. After the 520 // strong roots have been serialized we can create a partial snapshot 521 // which will repopulate the cache with objects neede by that partial 522 // snapshot. 523 partial_snapshot_cache_length_ = 0; 524 } 525 // Serialize the current state of the heap. The order is: 526 // 1) Strong references. 527 // 2) Partial snapshot cache. 528 // 3) Weak references (eg the symbol table). 529 virtual void SerializeStrongReferences(); 530 virtual void SerializeObject(Object* o, 531 ReferenceRepresentation representation); 532 void SerializeWeakReferences(); 533 void Serialize() { 534 SerializeStrongReferences(); 535 SerializeWeakReferences(); 536 } 537 538 private: 539 virtual int RootIndex(HeapObject* o) { return kInvalidRootIndex; } 540 virtual bool ShouldBeInThePartialSnapshotCache(HeapObject* o) { 541 return false; 542 } 543}; 544 545 546} } // namespace v8::internal 547 548#endif // V8_SERIALIZE_H_ 549