deps/v8/src/heap-snapshot-generator.cc

   1 // Copyright 2013 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 #include "src/v8.h"
   6
   7 #include "src/heap-snapshot-generator-inl.h"
   8
   9 #include "src/allocation-tracker.h"
  10 #include "src/code-stubs.h"
  11 #include "src/conversions.h"
  12 #include "src/debug.h"
  13 #include "src/heap-profiler.h"
  14 #include "src/types.h"
  15
  16 namespace v8 {
  17 namespace internal {
  18
  19
  20 HeapGraphEdge::HeapGraphEdge(Type type, const char* name, int from, int to)
  21     : bit_field_(TypeField::encode(type) | FromIndexField::encode(from)),
  22       to_index_(to),
  23       name_(name) {
  24   DCHECK(type == kContextVariable
  25       || type == kProperty
  26       || type == kInternal
  27       || type == kShortcut
  28       || type == kWeak);
  29 }
  30
  31
  32 HeapGraphEdge::HeapGraphEdge(Type type, int index, int from, int to)
  33     : bit_field_(TypeField::encode(type) | FromIndexField::encode(from)),
  34       to_index_(to),
  35       index_(index) {
  36   DCHECK(type == kElement || type == kHidden);
  37 }
  38
  39
  40 void HeapGraphEdge::ReplaceToIndexWithEntry(HeapSnapshot* snapshot) {
  41   to_entry_ = &snapshot->entries()[to_index_];
  42 }
  43
  44
  45 const int HeapEntry::kNoEntry = -1;
  46
  47 HeapEntry::HeapEntry(HeapSnapshot* snapshot,
  48                      Type type,
  49                      const char* name,
  50                      SnapshotObjectId id,
  51                      size_t self_size,
  52                      unsigned trace_node_id)
  53     : type_(type),
  54       children_count_(0),
  55       children_index_(-1),
  56       self_size_(self_size),
  57       snapshot_(snapshot),
  58       name_(name),
  59       id_(id),
  60       trace_node_id_(trace_node_id) { }
  61
  62
  63 void HeapEntry::SetNamedReference(HeapGraphEdge::Type type,
  64                                   const char* name,
  65                                   HeapEntry* entry) {
  66   HeapGraphEdge edge(type, name, this->index(), entry->index());
  67   snapshot_->edges().Add(edge);
  68   ++children_count_;
  69 }
  70
  71
  72 void HeapEntry::SetIndexedReference(HeapGraphEdge::Type type,
  73                                     int index,
  74                                     HeapEntry* entry) {
  75   HeapGraphEdge edge(type, index, this->index(), entry->index());
  76   snapshot_->edges().Add(edge);
  77   ++children_count_;
  78 }
  79
  80
  81 void HeapEntry::Print(
  82     const char* prefix, const char* edge_name, int max_depth, int indent) {
  83   STATIC_ASSERT(sizeof(unsigned) == sizeof(id()));
  84   base::OS::Print("%6" V8PRIuPTR " @%6u %*c %s%s: ", self_size(), id(), indent,
  85                   ' ', prefix, edge_name);
  86   if (type() != kString) {
  87     base::OS::Print("%s %.40s\n", TypeAsString(), name_);
  88   } else {
  89     base::OS::Print("\"");
  90     const char* c = name_;
  91     while (*c && (c - name_) <= 40) {
  92       if (*c != '\n')
  93         base::OS::Print("%c", *c);
  94       else
  95         base::OS::Print("\\n");
  96       ++c;
  97     }
  98     base::OS::Print("\"\n");
  99   }
 100   if (--max_depth == 0) return;
 101   Vector<HeapGraphEdge*> ch = children();
 102   for (int i = 0; i < ch.length(); ++i) {
 103     HeapGraphEdge& edge = *ch[i];
 104     const char* edge_prefix = "";
 105     EmbeddedVector<char, 64> index;
 106     const char* edge_name = index.start();
 107     switch (edge.type()) {
 108       case HeapGraphEdge::kContextVariable:
 109         edge_prefix = "#";
 110         edge_name = edge.name();
 111         break;
 112       case HeapGraphEdge::kElement:
 113         SNPrintF(index, "%d", edge.index());
 114         break;
 115       case HeapGraphEdge::kInternal:
 116         edge_prefix = "$";
 117         edge_name = edge.name();
 118         break;
 119       case HeapGraphEdge::kProperty:
 120         edge_name = edge.name();
 121         break;
 122       case HeapGraphEdge::kHidden:
 123         edge_prefix = "$";
 124         SNPrintF(index, "%d", edge.index());
 125         break;
 126       case HeapGraphEdge::kShortcut:
 127         edge_prefix = "^";
 128         edge_name = edge.name();
 129         break;
 130       case HeapGraphEdge::kWeak:
 131         edge_prefix = "w";
 132         edge_name = edge.name();
 133         break;
 134       default:
 135         SNPrintF(index, "!!! unknown edge type: %d ", edge.type());
 136     }
 137     edge.to()->Print(edge_prefix, edge_name, max_depth, indent + 2);
 138   }
 139 }
 140
 141
 142 const char* HeapEntry::TypeAsString() {
 143   switch (type()) {
 144     case kHidden: return "/hidden/";
 145     case kObject: return "/object/";
 146     case kClosure: return "/closure/";
 147     case kString: return "/string/";
 148     case kCode: return "/code/";
 149     case kArray: return "/array/";
 150     case kRegExp: return "/regexp/";
 151     case kHeapNumber: return "/number/";
 152     case kNative: return "/native/";
 153     case kSynthetic: return "/synthetic/";
 154     case kConsString: return "/concatenated string/";
 155     case kSlicedString: return "/sliced string/";
 156     case kSymbol: return "/symbol/";
 157     default: return "???";
 158   }
 159 }
 160
 161
 162 // It is very important to keep objects that form a heap snapshot
 163 // as small as possible.
 164 namespace {  // Avoid littering the global namespace.
 165
 166 template <size_t ptr_size> struct SnapshotSizeConstants;
 167
 168 template <> struct SnapshotSizeConstants<4> {
 169   static const int kExpectedHeapGraphEdgeSize = 12;
 170   static const int kExpectedHeapEntrySize = 28;
 171 };
 172
 173 template <> struct SnapshotSizeConstants<8> {
 174   static const int kExpectedHeapGraphEdgeSize = 24;
 175   static const int kExpectedHeapEntrySize = 40;
 176 };
 177
 178 }  // namespace
 179
 180
 181 HeapSnapshot::HeapSnapshot(HeapProfiler* profiler)
 182     : profiler_(profiler),
 183       root_index_(HeapEntry::kNoEntry),
 184       gc_roots_index_(HeapEntry::kNoEntry),
 185       max_snapshot_js_object_id_(0) {
 186   STATIC_ASSERT(
 187       sizeof(HeapGraphEdge) ==
 188       SnapshotSizeConstants<kPointerSize>::kExpectedHeapGraphEdgeSize);
 189   STATIC_ASSERT(
 190       sizeof(HeapEntry) ==
 191       SnapshotSizeConstants<kPointerSize>::kExpectedHeapEntrySize);
 192   USE(SnapshotSizeConstants<4>::kExpectedHeapGraphEdgeSize);
 193   USE(SnapshotSizeConstants<4>::kExpectedHeapEntrySize);
 194   USE(SnapshotSizeConstants<8>::kExpectedHeapGraphEdgeSize);
 195   USE(SnapshotSizeConstants<8>::kExpectedHeapEntrySize);
 196   for (int i = 0; i < VisitorSynchronization::kNumberOfSyncTags; ++i) {
 197     gc_subroot_indexes_[i] = HeapEntry::kNoEntry;
 198   }
 199 }
 200
 201
 202 void HeapSnapshot::Delete() {
 203   profiler_->RemoveSnapshot(this);
 204   delete this;
 205 }
 206
 207
 208 void HeapSnapshot::RememberLastJSObjectId() {
 209   max_snapshot_js_object_id_ = profiler_->heap_object_map()->last_assigned_id();
 210 }
 211
 212
 213 void HeapSnapshot::AddSyntheticRootEntries() {
 214   AddRootEntry();
 215   AddGcRootsEntry();
 216   SnapshotObjectId id = HeapObjectsMap::kGcRootsFirstSubrootId;
 217   for (int tag = 0; tag < VisitorSynchronization::kNumberOfSyncTags; tag++) {
 218     AddGcSubrootEntry(tag, id);
 219     id += HeapObjectsMap::kObjectIdStep;
 220   }
 221   DCHECK(HeapObjectsMap::kFirstAvailableObjectId == id);
 222 }
 223
 224
 225 HeapEntry* HeapSnapshot::AddRootEntry() {
 226   DCHECK(root_index_ == HeapEntry::kNoEntry);
 227   DCHECK(entries_.is_empty());  // Root entry must be the first one.
 228   HeapEntry* entry = AddEntry(HeapEntry::kSynthetic,
 229                               "",
 230                               HeapObjectsMap::kInternalRootObjectId,
 231                               0,
 232                               0);
 233   root_index_ = entry->index();
 234   DCHECK(root_index_ == 0);
 235   return entry;
 236 }
 237
 238
 239 HeapEntry* HeapSnapshot::AddGcRootsEntry() {
 240   DCHECK(gc_roots_index_ == HeapEntry::kNoEntry);
 241   HeapEntry* entry = AddEntry(HeapEntry::kSynthetic,
 242                               "(GC roots)",
 243                               HeapObjectsMap::kGcRootsObjectId,
 244                               0,
 245                               0);
 246   gc_roots_index_ = entry->index();
 247   return entry;
 248 }
 249
 250
 251 HeapEntry* HeapSnapshot::AddGcSubrootEntry(int tag, SnapshotObjectId id) {
 252   DCHECK(gc_subroot_indexes_[tag] == HeapEntry::kNoEntry);
 253   DCHECK(0 <= tag && tag < VisitorSynchronization::kNumberOfSyncTags);
 254   HeapEntry* entry = AddEntry(HeapEntry::kSynthetic,
 255                               VisitorSynchronization::kTagNames[tag], id, 0, 0);
 256   gc_subroot_indexes_[tag] = entry->index();
 257   return entry;
 258 }
 259
 260
 261 HeapEntry* HeapSnapshot::AddEntry(HeapEntry::Type type,
 262                                   const char* name,
 263                                   SnapshotObjectId id,
 264                                   size_t size,
 265                                   unsigned trace_node_id) {
 266   HeapEntry entry(this, type, name, id, size, trace_node_id);
 267   entries_.Add(entry);
 268   return &entries_.last();
 269 }
 270
 271
 272 void HeapSnapshot::FillChildren() {
 273   DCHECK(children().is_empty());
 274   children().Allocate(edges().length());
 275   int children_index = 0;
 276   for (int i = 0; i < entries().length(); ++i) {
 277     HeapEntry* entry = &entries()[i];
 278     children_index = entry->set_children_index(children_index);
 279   }
 280   DCHECK(edges().length() == children_index);
 281   for (int i = 0; i < edges().length(); ++i) {
 282     HeapGraphEdge* edge = &edges()[i];
 283     edge->ReplaceToIndexWithEntry(this);
 284     edge->from()->add_child(edge);
 285   }
 286 }
 287
 288
 289 class FindEntryById {
 290  public:
 291   explicit FindEntryById(SnapshotObjectId id) : id_(id) { }
 292   int operator()(HeapEntry* const* entry) {
 293     if ((*entry)->id() == id_) return 0;
 294     return (*entry)->id() < id_ ? -1 : 1;
 295   }
 296  private:
 297   SnapshotObjectId id_;
 298 };
 299
 300
 301 HeapEntry* HeapSnapshot::GetEntryById(SnapshotObjectId id) {
 302   List<HeapEntry*>* entries_by_id = GetSortedEntriesList();
 303   // Perform a binary search by id.
 304   int index = SortedListBSearch(*entries_by_id, FindEntryById(id));
 305   if (index == -1)
 306     return NULL;
 307   return entries_by_id->at(index);
 308 }
 309
 310
 311 template<class T>
 312 static int SortByIds(const T* entry1_ptr,
 313                      const T* entry2_ptr) {
 314   if ((*entry1_ptr)->id() == (*entry2_ptr)->id()) return 0;
 315   return (*entry1_ptr)->id() < (*entry2_ptr)->id() ? -1 : 1;
 316 }
 317
 318
 319 List<HeapEntry*>* HeapSnapshot::GetSortedEntriesList() {
 320   if (sorted_entries_.is_empty()) {
 321     sorted_entries_.Allocate(entries_.length());
 322     for (int i = 0; i < entries_.length(); ++i) {
 323       sorted_entries_[i] = &entries_[i];
 324     }
 325     sorted_entries_.Sort(SortByIds);
 326   }
 327   return &sorted_entries_;
 328 }
 329
 330
 331 void HeapSnapshot::Print(int max_depth) {
 332   root()->Print("", "", max_depth, 0);
 333 }
 334
 335
 336 size_t HeapSnapshot::RawSnapshotSize() const {
 337   return
 338       sizeof(*this) +
 339       GetMemoryUsedByList(entries_) +
 340       GetMemoryUsedByList(edges_) +
 341       GetMemoryUsedByList(children_) +
 342       GetMemoryUsedByList(sorted_entries_);
 343 }
 344
 345
 346 // We split IDs on evens for embedder objects (see
 347 // HeapObjectsMap::GenerateId) and odds for native objects.
 348 const SnapshotObjectId HeapObjectsMap::kInternalRootObjectId = 1;
 349 const SnapshotObjectId HeapObjectsMap::kGcRootsObjectId =
 350     HeapObjectsMap::kInternalRootObjectId + HeapObjectsMap::kObjectIdStep;
 351 const SnapshotObjectId HeapObjectsMap::kGcRootsFirstSubrootId =
 352     HeapObjectsMap::kGcRootsObjectId + HeapObjectsMap::kObjectIdStep;
 353 const SnapshotObjectId HeapObjectsMap::kFirstAvailableObjectId =
 354     HeapObjectsMap::kGcRootsFirstSubrootId +
 355     VisitorSynchronization::kNumberOfSyncTags * HeapObjectsMap::kObjectIdStep;
 356
 357
 358 static bool AddressesMatch(void* key1, void* key2) {
 359   return key1 == key2;
 360 }
 361
 362
 363 HeapObjectsMap::HeapObjectsMap(Heap* heap)
 364     : next_id_(kFirstAvailableObjectId),
 365       entries_map_(AddressesMatch),
 366       heap_(heap) {
 367   // This dummy element solves a problem with entries_map_.
 368   // When we do lookup in HashMap we see no difference between two cases:
 369   // it has an entry with NULL as the value or it has created
 370   // a new entry on the fly with NULL as the default value.
 371   // With such dummy element we have a guaranty that all entries_map_ entries
 372   // will have the value field grater than 0.
 373   // This fact is using in MoveObject method.
 374   entries_.Add(EntryInfo(0, NULL, 0));
 375 }
 376
 377
 378 bool HeapObjectsMap::MoveObject(Address from, Address to, int object_size) {
 379   DCHECK(to != NULL);
 380   DCHECK(from != NULL);
 381   if (from == to) return false;
 382   void* from_value = entries_map_.Remove(from, ComputePointerHash(from));
 383   if (from_value == NULL) {
 384     // It may occur that some untracked object moves to an address X and there
 385     // is a tracked object at that address. In this case we should remove the
 386     // entry as we know that the object has died.
 387     void* to_value = entries_map_.Remove(to, ComputePointerHash(to));
 388     if (to_value != NULL) {
 389       int to_entry_info_index =
 390           static_cast<int>(reinterpret_cast<intptr_t>(to_value));
 391       entries_.at(to_entry_info_index).addr = NULL;
 392     }
 393   } else {
 394     HashMap::Entry* to_entry = entries_map_.Lookup(to, ComputePointerHash(to),
 395                                                    true);
 396     if (to_entry->value != NULL) {
 397       // We found the existing entry with to address for an old object.
 398       // Without this operation we will have two EntryInfo's with the same
 399       // value in addr field. It is bad because later at RemoveDeadEntries
 400       // one of this entry will be removed with the corresponding entries_map_
 401       // entry.
 402       int to_entry_info_index =
 403           static_cast<int>(reinterpret_cast<intptr_t>(to_entry->value));
 404       entries_.at(to_entry_info_index).addr = NULL;
 405     }
 406     int from_entry_info_index =
 407         static_cast<int>(reinterpret_cast<intptr_t>(from_value));
 408     entries_.at(from_entry_info_index).addr = to;
 409     // Size of an object can change during its life, so to keep information
 410     // about the object in entries_ consistent, we have to adjust size when the
 411     // object is migrated.
 412     if (FLAG_heap_profiler_trace_objects) {
 413       PrintF("Move object from %p to %p old size %6d new size %6d\n",
 414              from,
 415              to,
 416              entries_.at(from_entry_info_index).size,
 417              object_size);
 418     }
 419     entries_.at(from_entry_info_index).size = object_size;
 420     to_entry->value = from_value;
 421   }
 422   return from_value != NULL;
 423 }
 424
 425
 426 void HeapObjectsMap::UpdateObjectSize(Address addr, int size) {
 427   FindOrAddEntry(addr, size, false);
 428 }
 429
 430
 431 SnapshotObjectId HeapObjectsMap::FindEntry(Address addr) {
 432   HashMap::Entry* entry = entries_map_.Lookup(addr, ComputePointerHash(addr),
 433                                               false);
 434   if (entry == NULL) return 0;
 435   int entry_index = static_cast<int>(reinterpret_cast<intptr_t>(entry->value));
 436   EntryInfo& entry_info = entries_.at(entry_index);
 437   DCHECK(static_cast<uint32_t>(entries_.length()) > entries_map_.occupancy());
 438   return entry_info.id;
 439 }
 440
 441
 442 SnapshotObjectId HeapObjectsMap::FindOrAddEntry(Address addr,
 443                                                 unsigned int size,
 444                                                 bool accessed) {
 445   DCHECK(static_cast<uint32_t>(entries_.length()) > entries_map_.occupancy());
 446   HashMap::Entry* entry = entries_map_.Lookup(addr, ComputePointerHash(addr),
 447                                               true);
 448   if (entry->value != NULL) {
 449     int entry_index =
 450         static_cast<int>(reinterpret_cast<intptr_t>(entry->value));
 451     EntryInfo& entry_info = entries_.at(entry_index);
 452     entry_info.accessed = accessed;
 453     if (FLAG_heap_profiler_trace_objects) {
 454       PrintF("Update object size : %p with old size %d and new size %d\n",
 455              addr,
 456              entry_info.size,
 457              size);
 458     }
 459     entry_info.size = size;
 460     return entry_info.id;
 461   }
 462   entry->value = reinterpret_cast<void*>(entries_.length());
 463   SnapshotObjectId id = next_id_;
 464   next_id_ += kObjectIdStep;
 465   entries_.Add(EntryInfo(id, addr, size, accessed));
 466   DCHECK(static_cast<uint32_t>(entries_.length()) > entries_map_.occupancy());
 467   return id;
 468 }
 469
 470
 471 void HeapObjectsMap::StopHeapObjectsTracking() {
 472   time_intervals_.Clear();
 473 }
 474
 475
 476 void HeapObjectsMap::UpdateHeapObjectsMap() {
 477   if (FLAG_heap_profiler_trace_objects) {
 478     PrintF("Begin HeapObjectsMap::UpdateHeapObjectsMap. map has %d entries.\n",
 479            entries_map_.occupancy());
 480   }
 481   heap_->CollectAllGarbage(Heap::kMakeHeapIterableMask,
 482                           "HeapObjectsMap::UpdateHeapObjectsMap");
 483   HeapIterator iterator(heap_);
 484   for (HeapObject* obj = iterator.next();
 485        obj != NULL;
 486        obj = iterator.next()) {
 487     FindOrAddEntry(obj->address(), obj->Size());
 488     if (FLAG_heap_profiler_trace_objects) {
 489       PrintF("Update object      : %p %6d. Next address is %p\n",
 490              obj->address(),
 491              obj->Size(),
 492              obj->address() + obj->Size());
 493     }
 494   }
 495   RemoveDeadEntries();
 496   if (FLAG_heap_profiler_trace_objects) {
 497     PrintF("End HeapObjectsMap::UpdateHeapObjectsMap. map has %d entries.\n",
 498            entries_map_.occupancy());
 499   }
 500 }
 501
 502
 503 namespace {
 504
 505
 506 struct HeapObjectInfo {
 507   HeapObjectInfo(HeapObject* obj, int expected_size)
 508     : obj(obj),
 509       expected_size(expected_size) {
 510   }
 511
 512   HeapObject* obj;
 513   int expected_size;
 514
 515   bool IsValid() const { return expected_size == obj->Size(); }
 516
 517   void Print() const {
 518     if (expected_size == 0) {
 519       PrintF("Untracked object   : %p %6d. Next address is %p\n",
 520              obj->address(),
 521              obj->Size(),
 522              obj->address() + obj->Size());
 523     } else if (obj->Size() != expected_size) {
 524       PrintF("Wrong size %6d: %p %6d. Next address is %p\n",
 525              expected_size,
 526              obj->address(),
 527              obj->Size(),
 528              obj->address() + obj->Size());
 529     } else {
 530       PrintF("Good object      : %p %6d. Next address is %p\n",
 531              obj->address(),
 532              expected_size,
 533              obj->address() + obj->Size());
 534     }
 535   }
 536 };
 537
 538
 539 static int comparator(const HeapObjectInfo* a, const HeapObjectInfo* b) {
 540   if (a->obj < b->obj) return -1;
 541   if (a->obj > b->obj) return 1;
 542   return 0;
 543 }
 544
 545
 546 }  // namespace
 547
 548
 549 int HeapObjectsMap::FindUntrackedObjects() {
 550   List<HeapObjectInfo> heap_objects(1000);
 551
 552   HeapIterator iterator(heap_);
 553   int untracked = 0;
 554   for (HeapObject* obj = iterator.next();
 555        obj != NULL;
 556        obj = iterator.next()) {
 557     HashMap::Entry* entry = entries_map_.Lookup(
 558       obj->address(), ComputePointerHash(obj->address()), false);
 559     if (entry == NULL) {
 560       ++untracked;
 561       if (FLAG_heap_profiler_trace_objects) {
 562         heap_objects.Add(HeapObjectInfo(obj, 0));
 563       }
 564     } else {
 565       int entry_index = static_cast<int>(
 566           reinterpret_cast<intptr_t>(entry->value));
 567       EntryInfo& entry_info = entries_.at(entry_index);
 568       if (FLAG_heap_profiler_trace_objects) {
 569         heap_objects.Add(HeapObjectInfo(obj,
 570                          static_cast<int>(entry_info.size)));
 571         if (obj->Size() != static_cast<int>(entry_info.size))
 572           ++untracked;
 573       } else {
 574         CHECK_EQ(obj->Size(), static_cast<int>(entry_info.size));
 575       }
 576     }
 577   }
 578   if (FLAG_heap_profiler_trace_objects) {
 579     PrintF("\nBegin HeapObjectsMap::FindUntrackedObjects. %d entries in map.\n",
 580            entries_map_.occupancy());
 581     heap_objects.Sort(comparator);
 582     int last_printed_object = -1;
 583     bool print_next_object = false;
 584     for (int i = 0; i < heap_objects.length(); ++i) {
 585       const HeapObjectInfo& object_info = heap_objects[i];
 586       if (!object_info.IsValid()) {
 587         ++untracked;
 588         if (last_printed_object != i - 1) {
 589           if (i > 0) {
 590             PrintF("%d objects were skipped\n", i - 1 - last_printed_object);
 591             heap_objects[i - 1].Print();
 592           }
 593         }
 594         object_info.Print();
 595         last_printed_object = i;
 596         print_next_object = true;
 597       } else if (print_next_object) {
 598         object_info.Print();
 599         print_next_object = false;
 600         last_printed_object = i;
 601       }
 602     }
 603     if (last_printed_object < heap_objects.length() - 1) {
 604       PrintF("Last %d objects were skipped\n",
 605              heap_objects.length() - 1 - last_printed_object);
 606     }
 607     PrintF("End HeapObjectsMap::FindUntrackedObjects. %d entries in map.\n\n",
 608            entries_map_.occupancy());
 609   }
 610   return untracked;
 611 }
 612
 613
 614 SnapshotObjectId HeapObjectsMap::PushHeapObjectsStats(OutputStream* stream,
 615                                                       int64_t* timestamp_us) {
 616   UpdateHeapObjectsMap();
 617   time_intervals_.Add(TimeInterval(next_id_));
 618   int prefered_chunk_size = stream->GetChunkSize();
 619   List<v8::HeapStatsUpdate> stats_buffer;
 620   DCHECK(!entries_.is_empty());
 621   EntryInfo* entry_info = &entries_.first();
 622   EntryInfo* end_entry_info = &entries_.last() + 1;
 623   for (int time_interval_index = 0;
 624        time_interval_index < time_intervals_.length();
 625        ++time_interval_index) {
 626     TimeInterval& time_interval = time_intervals_[time_interval_index];
 627     SnapshotObjectId time_interval_id = time_interval.id;
 628     uint32_t entries_size = 0;
 629     EntryInfo* start_entry_info = entry_info;
 630     while (entry_info < end_entry_info && entry_info->id < time_interval_id) {
 631       entries_size += entry_info->size;
 632       ++entry_info;
 633     }
 634     uint32_t entries_count =
 635         static_cast<uint32_t>(entry_info - start_entry_info);
 636     if (time_interval.count != entries_count ||
 637         time_interval.size != entries_size) {
 638       stats_buffer.Add(v8::HeapStatsUpdate(
 639           time_interval_index,
 640           time_interval.count = entries_count,
 641           time_interval.size = entries_size));
 642       if (stats_buffer.length() >= prefered_chunk_size) {
 643         OutputStream::WriteResult result = stream->WriteHeapStatsChunk(
 644             &stats_buffer.first(), stats_buffer.length());
 645         if (result == OutputStream::kAbort) return last_assigned_id();
 646         stats_buffer.Clear();
 647       }
 648     }
 649   }
 650   DCHECK(entry_info == end_entry_info);
 651   if (!stats_buffer.is_empty()) {
 652     OutputStream::WriteResult result = stream->WriteHeapStatsChunk(
 653         &stats_buffer.first(), stats_buffer.length());
 654     if (result == OutputStream::kAbort) return last_assigned_id();
 655   }
 656   stream->EndOfStream();
 657   if (timestamp_us) {
 658     *timestamp_us = (time_intervals_.last().timestamp -
 659                      time_intervals_[0].timestamp).InMicroseconds();
 660   }
 661   return last_assigned_id();
 662 }
 663
 664
 665 void HeapObjectsMap::RemoveDeadEntries() {
 666   DCHECK(entries_.length() > 0 &&
 667          entries_.at(0).id == 0 &&
 668          entries_.at(0).addr == NULL);
 669   int first_free_entry = 1;
 670   for (int i = 1; i < entries_.length(); ++i) {
 671     EntryInfo& entry_info = entries_.at(i);
 672     if (entry_info.accessed) {
 673       if (first_free_entry != i) {
 674         entries_.at(first_free_entry) = entry_info;
 675       }
 676       entries_.at(first_free_entry).accessed = false;
 677       HashMap::Entry* entry = entries_map_.Lookup(
 678           entry_info.addr, ComputePointerHash(entry_info.addr), false);
 679       DCHECK(entry);
 680       entry->value = reinterpret_cast<void*>(first_free_entry);
 681       ++first_free_entry;
 682     } else {
 683       if (entry_info.addr) {
 684         entries_map_.Remove(entry_info.addr,
 685                             ComputePointerHash(entry_info.addr));
 686       }
 687     }
 688   }
 689   entries_.Rewind(first_free_entry);
 690   DCHECK(static_cast<uint32_t>(entries_.length()) - 1 ==
 691          entries_map_.occupancy());
 692 }
 693
 694
 695 SnapshotObjectId HeapObjectsMap::GenerateId(v8::RetainedObjectInfo* info) {
 696   SnapshotObjectId id = static_cast<SnapshotObjectId>(info->GetHash());
 697   const char* label = info->GetLabel();
 698   id ^= StringHasher::HashSequentialString(label,
 699                                            static_cast<int>(strlen(label)),
 700                                            heap_->HashSeed());
 701   intptr_t element_count = info->GetElementCount();
 702   if (element_count != -1)
 703     id ^= ComputeIntegerHash(static_cast<uint32_t>(element_count),
 704                              v8::internal::kZeroHashSeed);
 705   return id << 1;
 706 }
 707
 708
 709 size_t HeapObjectsMap::GetUsedMemorySize() const {
 710   return
 711       sizeof(*this) +
 712       sizeof(HashMap::Entry) * entries_map_.capacity() +
 713       GetMemoryUsedByList(entries_) +
 714       GetMemoryUsedByList(time_intervals_);
 715 }
 716
 717
 718 HeapEntriesMap::HeapEntriesMap()
 719     : entries_(HashMap::PointersMatch) {
 720 }
 721
 722
 723 int HeapEntriesMap::Map(HeapThing thing) {
 724   HashMap::Entry* cache_entry = entries_.Lookup(thing, Hash(thing), false);
 725   if (cache_entry == NULL) return HeapEntry::kNoEntry;
 726   return static_cast<int>(reinterpret_cast<intptr_t>(cache_entry->value));
 727 }
 728
 729
 730 void HeapEntriesMap::Pair(HeapThing thing, int entry) {
 731   HashMap::Entry* cache_entry = entries_.Lookup(thing, Hash(thing), true);
 732   DCHECK(cache_entry->value == NULL);
 733   cache_entry->value = reinterpret_cast<void*>(static_cast<intptr_t>(entry));
 734 }
 735
 736
 737 HeapObjectsSet::HeapObjectsSet()
 738     : entries_(HashMap::PointersMatch) {
 739 }
 740
 741
 742 void HeapObjectsSet::Clear() {
 743   entries_.Clear();
 744 }
 745
 746
 747 bool HeapObjectsSet::Contains(Object* obj) {
 748   if (!obj->IsHeapObject()) return false;
 749   HeapObject* object = HeapObject::cast(obj);
 750   return entries_.Lookup(object, HeapEntriesMap::Hash(object), false) != NULL;
 751 }
 752
 753
 754 void HeapObjectsSet::Insert(Object* obj) {
 755   if (!obj->IsHeapObject()) return;
 756   HeapObject* object = HeapObject::cast(obj);
 757   entries_.Lookup(object, HeapEntriesMap::Hash(object), true);
 758 }
 759
 760
 761 const char* HeapObjectsSet::GetTag(Object* obj) {
 762   HeapObject* object = HeapObject::cast(obj);
 763   HashMap::Entry* cache_entry =
 764       entries_.Lookup(object, HeapEntriesMap::Hash(object), false);
 765   return cache_entry != NULL
 766       ? reinterpret_cast<const char*>(cache_entry->value)
 767       : NULL;
 768 }
 769
 770
 771 void HeapObjectsSet::SetTag(Object* obj, const char* tag) {
 772   if (!obj->IsHeapObject()) return;
 773   HeapObject* object = HeapObject::cast(obj);
 774   HashMap::Entry* cache_entry =
 775       entries_.Lookup(object, HeapEntriesMap::Hash(object), true);
 776   cache_entry->value = const_cast<char*>(tag);
 777 }
 778
 779
 780 V8HeapExplorer::V8HeapExplorer(
 781     HeapSnapshot* snapshot,
 782     SnapshottingProgressReportingInterface* progress,
 783     v8::HeapProfiler::ObjectNameResolver* resolver)
 784     : heap_(snapshot->profiler()->heap_object_map()->heap()),
 785       snapshot_(snapshot),
 786       names_(snapshot_->profiler()->names()),
 787       heap_object_map_(snapshot_->profiler()->heap_object_map()),
 788       progress_(progress),
 789       filler_(NULL),
 790       global_object_name_resolver_(resolver) {
 791 }
 792
 793
 794 V8HeapExplorer::~V8HeapExplorer() {
 795 }
 796
 797
 798 HeapEntry* V8HeapExplorer::AllocateEntry(HeapThing ptr) {
 799   return AddEntry(reinterpret_cast<HeapObject*>(ptr));
 800 }
 801
 802
 803 HeapEntry* V8HeapExplorer::AddEntry(HeapObject* object) {
 804   if (object->IsJSFunction()) {
 805     JSFunction* func = JSFunction::cast(object);
 806     SharedFunctionInfo* shared = func->shared();
 807     const char* name = shared->bound() ? "native_bind" :
 808         names_->GetName(String::cast(shared->name()));
 809     return AddEntry(object, HeapEntry::kClosure, name);
 810   } else if (object->IsJSRegExp()) {
 811     JSRegExp* re = JSRegExp::cast(object);
 812     return AddEntry(object,
 813                     HeapEntry::kRegExp,
 814                     names_->GetName(re->Pattern()));
 815   } else if (object->IsJSObject()) {
 816     const char* name = names_->GetName(
 817         GetConstructorName(JSObject::cast(object)));
 818     if (object->IsJSGlobalObject()) {
 819       const char* tag = objects_tags_.GetTag(object);
 820       if (tag != NULL) {
 821         name = names_->GetFormatted("%s / %s", name, tag);
 822       }
 823     }
 824     return AddEntry(object, HeapEntry::kObject, name);
 825   } else if (object->IsString()) {
 826     String* string = String::cast(object);
 827     if (string->IsConsString())
 828       return AddEntry(object,
 829                       HeapEntry::kConsString,
 830                       "(concatenated string)");
 831     if (string->IsSlicedString())
 832       return AddEntry(object,
 833                       HeapEntry::kSlicedString,
 834                       "(sliced string)");
 835     return AddEntry(object,
 836                     HeapEntry::kString,
 837                     names_->GetName(String::cast(object)));
 838   } else if (object->IsSymbol()) {
 839     return AddEntry(object, HeapEntry::kSymbol, "symbol");
 840   } else if (object->IsCode()) {
 841     return AddEntry(object, HeapEntry::kCode, "");
 842   } else if (object->IsSharedFunctionInfo()) {
 843     String* name = String::cast(SharedFunctionInfo::cast(object)->name());
 844     return AddEntry(object,
 845                     HeapEntry::kCode,
 846                     names_->GetName(name));
 847   } else if (object->IsScript()) {
 848     Object* name = Script::cast(object)->name();
 849     return AddEntry(object,
 850                     HeapEntry::kCode,
 851                     name->IsString()
 852                         ? names_->GetName(String::cast(name))
 853                         : "");
 854   } else if (object->IsNativeContext()) {
 855     return AddEntry(object, HeapEntry::kHidden, "system / NativeContext");
 856   } else if (object->IsContext()) {
 857     return AddEntry(object, HeapEntry::kObject, "system / Context");
 858   } else if (object->IsFixedArray() ||
 859              object->IsFixedDoubleArray() ||
 860              object->IsByteArray() ||
 861              object->IsExternalArray()) {
 862     return AddEntry(object, HeapEntry::kArray, "");
 863   } else if (object->IsHeapNumber()) {
 864     return AddEntry(object, HeapEntry::kHeapNumber, "number");
 865   }
 866   return AddEntry(object, HeapEntry::kHidden, GetSystemEntryName(object));
 867 }
 868
 869
 870 HeapEntry* V8HeapExplorer::AddEntry(HeapObject* object,
 871                                     HeapEntry::Type type,
 872                                     const char* name) {
 873   return AddEntry(object->address(), type, name, object->Size());
 874 }
 875
 876
 877 HeapEntry* V8HeapExplorer::AddEntry(Address address,
 878                                     HeapEntry::Type type,
 879                                     const char* name,
 880                                     size_t size) {
 881   SnapshotObjectId object_id = heap_object_map_->FindOrAddEntry(
 882       address, static_cast<unsigned int>(size));
 883   unsigned trace_node_id = 0;
 884   if (AllocationTracker* allocation_tracker =
 885       snapshot_->profiler()->allocation_tracker()) {
 886     trace_node_id =
 887         allocation_tracker->address_to_trace()->GetTraceNodeId(address);
 888   }
 889   return snapshot_->AddEntry(type, name, object_id, size, trace_node_id);
 890 }
 891
 892
 893 class SnapshotFiller {
 894  public:
 895   explicit SnapshotFiller(HeapSnapshot* snapshot, HeapEntriesMap* entries)
 896       : snapshot_(snapshot),
 897         names_(snapshot->profiler()->names()),
 898         entries_(entries) { }
 899   HeapEntry* AddEntry(HeapThing ptr, HeapEntriesAllocator* allocator) {
 900     HeapEntry* entry = allocator->AllocateEntry(ptr);
 901     entries_->Pair(ptr, entry->index());
 902     return entry;
 903   }
 904   HeapEntry* FindEntry(HeapThing ptr) {
 905     int index = entries_->Map(ptr);
 906     return index != HeapEntry::kNoEntry ? &snapshot_->entries()[index] : NULL;
 907   }
 908   HeapEntry* FindOrAddEntry(HeapThing ptr, HeapEntriesAllocator* allocator) {
 909     HeapEntry* entry = FindEntry(ptr);
 910     return entry != NULL ? entry : AddEntry(ptr, allocator);
 911   }
 912   void SetIndexedReference(HeapGraphEdge::Type type,
 913                            int parent,
 914                            int index,
 915                            HeapEntry* child_entry) {
 916     HeapEntry* parent_entry = &snapshot_->entries()[parent];
 917     parent_entry->SetIndexedReference(type, index, child_entry);
 918   }
 919   void SetIndexedAutoIndexReference(HeapGraphEdge::Type type,
 920                                     int parent,
 921                                     HeapEntry* child_entry) {
 922     HeapEntry* parent_entry = &snapshot_->entries()[parent];
 923     int index = parent_entry->children_count() + 1;
 924     parent_entry->SetIndexedReference(type, index, child_entry);
 925   }
 926   void SetNamedReference(HeapGraphEdge::Type type,
 927                          int parent,
 928                          const char* reference_name,
 929                          HeapEntry* child_entry) {
 930     HeapEntry* parent_entry = &snapshot_->entries()[parent];
 931     parent_entry->SetNamedReference(type, reference_name, child_entry);
 932   }
 933   void SetNamedAutoIndexReference(HeapGraphEdge::Type type,
 934                                   int parent,
 935                                   HeapEntry* child_entry) {
 936     HeapEntry* parent_entry = &snapshot_->entries()[parent];
 937     int index = parent_entry->children_count() + 1;
 938     parent_entry->SetNamedReference(
 939         type,
 940         names_->GetName(index),
 941         child_entry);
 942   }
 943
 944  private:
 945   HeapSnapshot* snapshot_;
 946   StringsStorage* names_;
 947   HeapEntriesMap* entries_;
 948 };
 949
 950
 951 const char* V8HeapExplorer::GetSystemEntryName(HeapObject* object) {
 952   switch (object->map()->instance_type()) {
 953     case MAP_TYPE:
 954       switch (Map::cast(object)->instance_type()) {
 955 #define MAKE_STRING_MAP_CASE(instance_type, size, name, Name) \
 956         case instance_type: return "system / Map (" #Name ")";
 957       STRING_TYPE_LIST(MAKE_STRING_MAP_CASE)
 958 #undef MAKE_STRING_MAP_CASE
 959         default: return "system / Map";
 960       }
 961     case CELL_TYPE: return "system / Cell";
 962     case PROPERTY_CELL_TYPE: return "system / PropertyCell";
 963     case FOREIGN_TYPE: return "system / Foreign";
 964     case ODDBALL_TYPE: return "system / Oddball";
 965 #define MAKE_STRUCT_CASE(NAME, Name, name) \
 966     case NAME##_TYPE: return "system / "#Name;
 967   STRUCT_LIST(MAKE_STRUCT_CASE)
 968 #undef MAKE_STRUCT_CASE
 969     default: return "system";
 970   }
 971 }
 972
 973
 974 int V8HeapExplorer::EstimateObjectsCount(HeapIterator* iterator) {
 975   int objects_count = 0;
 976   for (HeapObject* obj = iterator->next();
 977        obj != NULL;
 978        obj = iterator->next()) {
 979     objects_count++;
 980   }
 981   return objects_count;
 982 }
 983
 984
 985 class IndexedReferencesExtractor : public ObjectVisitor {
 986  public:
 987   IndexedReferencesExtractor(V8HeapExplorer* generator,
 988                              HeapObject* parent_obj,
 989                              int parent)
 990       : generator_(generator),
 991         parent_obj_(parent_obj),
 992         parent_(parent),
 993         next_index_(0) {
 994   }
 995   void VisitCodeEntry(Address entry_address) {
 996      Code* code = Code::cast(Code::GetObjectFromEntryAddress(entry_address));
 997      generator_->SetInternalReference(parent_obj_, parent_, "code", code);
 998      generator_->TagCodeObject(code);
 999   }
1000   void VisitPointers(Object** start, Object** end) {
1001     for (Object** p = start; p < end; p++) {
1002       ++next_index_;
1003       if (CheckVisitedAndUnmark(p)) continue;
1004       generator_->SetHiddenReference(parent_obj_, parent_, next_index_, *p);
1005     }
1006   }
1007   static void MarkVisitedField(HeapObject* obj, int offset) {
1008     if (offset < 0) return;
1009     Address field = obj->address() + offset;
1010     DCHECK(Memory::Object_at(field)->IsHeapObject());
1011     intptr_t p = reinterpret_cast<intptr_t>(Memory::Object_at(field));
1012     DCHECK(!IsMarked(p));
1013     intptr_t p_tagged = p | kTag;
1014     Memory::Object_at(field) = reinterpret_cast<Object*>(p_tagged);
1015   }
1016
1017  private:
1018   bool CheckVisitedAndUnmark(Object** field) {
1019     intptr_t p = reinterpret_cast<intptr_t>(*field);
1020     if (IsMarked(p)) {
1021       intptr_t p_untagged = (p & ~kTaggingMask) | kHeapObjectTag;
1022       *field = reinterpret_cast<Object*>(p_untagged);
1023       DCHECK((*field)->IsHeapObject());
1024       return true;
1025     }
1026     return false;
1027   }
1028
1029   static const intptr_t kTaggingMask = 3;
1030   static const intptr_t kTag = 3;
1031
1032   static bool IsMarked(intptr_t p) { return (p & kTaggingMask) == kTag; }
1033
1034   V8HeapExplorer* generator_;
1035   HeapObject* parent_obj_;
1036   int parent_;
1037   int next_index_;
1038 };
1039
1040
1041 bool V8HeapExplorer::ExtractReferencesPass1(int entry, HeapObject* obj) {
1042   if (obj->IsFixedArray()) return false;  // FixedArrays are processed on pass 2
1043
1044   if (obj->IsJSGlobalProxy()) {
1045     ExtractJSGlobalProxyReferences(entry, JSGlobalProxy::cast(obj));
1046   } else if (obj->IsJSArrayBuffer()) {
1047     ExtractJSArrayBufferReferences(entry, JSArrayBuffer::cast(obj));
1048   } else if (obj->IsJSObject()) {
1049     if (obj->IsJSWeakSet()) {
1050       ExtractJSWeakCollectionReferences(entry, JSWeakSet::cast(obj));
1051     } else if (obj->IsJSWeakMap()) {
1052       ExtractJSWeakCollectionReferences(entry, JSWeakMap::cast(obj));
1053     } else if (obj->IsJSSet()) {
1054       ExtractJSCollectionReferences(entry, JSSet::cast(obj));
1055     } else if (obj->IsJSMap()) {
1056       ExtractJSCollectionReferences(entry, JSMap::cast(obj));
1057     }
1058     ExtractJSObjectReferences(entry, JSObject::cast(obj));
1059   } else if (obj->IsString()) {
1060     ExtractStringReferences(entry, String::cast(obj));
1061   } else if (obj->IsSymbol()) {
1062     ExtractSymbolReferences(entry, Symbol::cast(obj));
1063   } else if (obj->IsMap()) {
1064     ExtractMapReferences(entry, Map::cast(obj));
1065   } else if (obj->IsSharedFunctionInfo()) {
1066     ExtractSharedFunctionInfoReferences(entry, SharedFunctionInfo::cast(obj));
1067   } else if (obj->IsScript()) {
1068     ExtractScriptReferences(entry, Script::cast(obj));
1069   } else if (obj->IsAccessorInfo()) {
1070     ExtractAccessorInfoReferences(entry, AccessorInfo::cast(obj));
1071   } else if (obj->IsAccessorPair()) {
1072     ExtractAccessorPairReferences(entry, AccessorPair::cast(obj));
1073   } else if (obj->IsCodeCache()) {
1074     ExtractCodeCacheReferences(entry, CodeCache::cast(obj));
1075   } else if (obj->IsCode()) {
1076     ExtractCodeReferences(entry, Code::cast(obj));
1077   } else if (obj->IsBox()) {
1078     ExtractBoxReferences(entry, Box::cast(obj));
1079   } else if (obj->IsCell()) {
1080     ExtractCellReferences(entry, Cell::cast(obj));
1081   } else if (obj->IsPropertyCell()) {
1082     ExtractPropertyCellReferences(entry, PropertyCell::cast(obj));
1083   } else if (obj->IsAllocationSite()) {
1084     ExtractAllocationSiteReferences(entry, AllocationSite::cast(obj));
1085   }
1086   return true;
1087 }
1088
1089
1090 bool V8HeapExplorer::ExtractReferencesPass2(int entry, HeapObject* obj) {
1091   if (!obj->IsFixedArray()) return false;
1092
1093   if (obj->IsContext()) {
1094     ExtractContextReferences(entry, Context::cast(obj));
1095   } else {
1096     ExtractFixedArrayReferences(entry, FixedArray::cast(obj));
1097   }
1098   return true;
1099 }
1100
1101
1102 void V8HeapExplorer::ExtractJSGlobalProxyReferences(
1103     int entry, JSGlobalProxy* proxy) {
1104   SetInternalReference(proxy, entry,
1105                        "native_context", proxy->native_context(),
1106                        JSGlobalProxy::kNativeContextOffset);
1107 }
1108
1109
1110 void V8HeapExplorer::ExtractJSObjectReferences(
1111     int entry, JSObject* js_obj) {
1112   HeapObject* obj = js_obj;
1113   ExtractClosureReferences(js_obj, entry);
1114   ExtractPropertyReferences(js_obj, entry);
1115   ExtractElementReferences(js_obj, entry);
1116   ExtractInternalReferences(js_obj, entry);
1117   PrototypeIterator iter(heap_->isolate(), js_obj);
1118   SetPropertyReference(obj, entry, heap_->proto_string(), iter.GetCurrent());
1119   if (obj->IsJSFunction()) {
1120     JSFunction* js_fun = JSFunction::cast(js_obj);
1121     Object* proto_or_map = js_fun->prototype_or_initial_map();
1122     if (!proto_or_map->IsTheHole()) {
1123       if (!proto_or_map->IsMap()) {
1124         SetPropertyReference(
1125             obj, entry,
1126             heap_->prototype_string(), proto_or_map,
1127             NULL,
1128             JSFunction::kPrototypeOrInitialMapOffset);
1129       } else {
1130         SetPropertyReference(
1131             obj, entry,
1132             heap_->prototype_string(), js_fun->prototype());
1133         SetInternalReference(
1134             obj, entry, "initial_map", proto_or_map,
1135             JSFunction::kPrototypeOrInitialMapOffset);
1136       }
1137     }
1138     SharedFunctionInfo* shared_info = js_fun->shared();
1139     // JSFunction has either bindings or literals and never both.
1140     bool bound = shared_info->bound();
1141     TagObject(js_fun->literals_or_bindings(),
1142               bound ? "(function bindings)" : "(function literals)");
1143     SetInternalReference(js_fun, entry,
1144                          bound ? "bindings" : "literals",
1145                          js_fun->literals_or_bindings(),
1146                          JSFunction::kLiteralsOffset);
1147     TagObject(shared_info, "(shared function info)");
1148     SetInternalReference(js_fun, entry,
1149                          "shared", shared_info,
1150                          JSFunction::kSharedFunctionInfoOffset);
1151     TagObject(js_fun->context(), "(context)");
1152     SetInternalReference(js_fun, entry,
1153                          "context", js_fun->context(),
1154                          JSFunction::kContextOffset);
1155     SetWeakReference(js_fun, entry,
1156                      "next_function_link", js_fun->next_function_link(),
1157                      JSFunction::kNextFunctionLinkOffset);
1158     STATIC_ASSERT(JSFunction::kNextFunctionLinkOffset
1159                  == JSFunction::kNonWeakFieldsEndOffset);
1160     STATIC_ASSERT(JSFunction::kNextFunctionLinkOffset + kPointerSize
1161                  == JSFunction::kSize);
1162   } else if (obj->IsGlobalObject()) {
1163     GlobalObject* global_obj = GlobalObject::cast(obj);
1164     SetInternalReference(global_obj, entry,
1165                          "builtins", global_obj->builtins(),
1166                          GlobalObject::kBuiltinsOffset);
1167     SetInternalReference(global_obj, entry,
1168                          "native_context", global_obj->native_context(),
1169                          GlobalObject::kNativeContextOffset);
1170     SetInternalReference(global_obj, entry,
1171                          "global_proxy", global_obj->global_proxy(),
1172                          GlobalObject::kGlobalProxyOffset);
1173     STATIC_ASSERT(GlobalObject::kHeaderSize - JSObject::kHeaderSize ==
1174                  3 * kPointerSize);
1175   } else if (obj->IsJSArrayBufferView()) {
1176     JSArrayBufferView* view = JSArrayBufferView::cast(obj);
1177     SetInternalReference(view, entry, "buffer", view->buffer(),
1178                          JSArrayBufferView::kBufferOffset);
1179     SetWeakReference(view, entry, "weak_next", view->weak_next(),
1180                      JSArrayBufferView::kWeakNextOffset);
1181   }
1182   TagObject(js_obj->properties(), "(object properties)");
1183   SetInternalReference(obj, entry,
1184                        "properties", js_obj->properties(),
1185                        JSObject::kPropertiesOffset);
1186   TagObject(js_obj->elements(), "(object elements)");
1187   SetInternalReference(obj, entry,
1188                        "elements", js_obj->elements(),
1189                        JSObject::kElementsOffset);
1190 }
1191
1192
1193 void V8HeapExplorer::ExtractStringReferences(int entry, String* string) {
1194   if (string->IsConsString()) {
1195     ConsString* cs = ConsString::cast(string);
1196     SetInternalReference(cs, entry, "first", cs->first(),
1197                          ConsString::kFirstOffset);
1198     SetInternalReference(cs, entry, "second", cs->second(),
1199                          ConsString::kSecondOffset);
1200   } else if (string->IsSlicedString()) {
1201     SlicedString* ss = SlicedString::cast(string);
1202     SetInternalReference(ss, entry, "parent", ss->parent(),
1203                          SlicedString::kParentOffset);
1204   }
1205 }
1206
1207
1208 void V8HeapExplorer::ExtractSymbolReferences(int entry, Symbol* symbol) {
1209   SetInternalReference(symbol, entry,
1210                        "name", symbol->name(),
1211                        Symbol::kNameOffset);
1212 }
1213
1214
1215 void V8HeapExplorer::ExtractJSCollectionReferences(int entry,
1216                                                    JSCollection* collection) {
1217   SetInternalReference(collection, entry, "table", collection->table(),
1218                        JSCollection::kTableOffset);
1219 }
1220
1221
1222 void V8HeapExplorer::ExtractJSWeakCollectionReferences(
1223     int entry, JSWeakCollection* collection) {
1224   MarkAsWeakContainer(collection->table());
1225   SetInternalReference(collection, entry,
1226                        "table", collection->table(),
1227                        JSWeakCollection::kTableOffset);
1228 }
1229
1230
1231 void V8HeapExplorer::ExtractContextReferences(int entry, Context* context) {
1232   if (context == context->declaration_context()) {
1233     ScopeInfo* scope_info = context->closure()->shared()->scope_info();
1234     // Add context allocated locals.
1235     int context_locals = scope_info->ContextLocalCount();
1236     for (int i = 0; i < context_locals; ++i) {
1237       String* local_name = scope_info->ContextLocalName(i);
1238       int idx = Context::MIN_CONTEXT_SLOTS + i;
1239       SetContextReference(context, entry, local_name, context->get(idx),
1240                           Context::OffsetOfElementAt(idx));
1241     }
1242     if (scope_info->HasFunctionName()) {
1243       String* name = scope_info->FunctionName();
1244       VariableMode mode;
1245       int idx = scope_info->FunctionContextSlotIndex(name, &mode);
1246       if (idx >= 0) {
1247         SetContextReference(context, entry, name, context->get(idx),
1248                             Context::OffsetOfElementAt(idx));
1249       }
1250     }
1251   }
1252
1253 #define EXTRACT_CONTEXT_FIELD(index, type, name) \
1254   if (Context::index < Context::FIRST_WEAK_SLOT || \
1255       Context::index == Context::MAP_CACHE_INDEX) { \
1256     SetInternalReference(context, entry, #name, context->get(Context::index), \
1257         FixedArray::OffsetOfElementAt(Context::index)); \
1258   } else { \
1259     SetWeakReference(context, entry, #name, context->get(Context::index), \
1260         FixedArray::OffsetOfElementAt(Context::index)); \
1261   }
1262   EXTRACT_CONTEXT_FIELD(CLOSURE_INDEX, JSFunction, closure);
1263   EXTRACT_CONTEXT_FIELD(PREVIOUS_INDEX, Context, previous);
1264   EXTRACT_CONTEXT_FIELD(EXTENSION_INDEX, Object, extension);
1265   EXTRACT_CONTEXT_FIELD(GLOBAL_OBJECT_INDEX, GlobalObject, global);
1266   if (context->IsNativeContext()) {
1267     TagObject(context->jsfunction_result_caches(),
1268               "(context func. result caches)");
1269     TagObject(context->normalized_map_cache(), "(context norm. map cache)");
1270     TagObject(context->runtime_context(), "(runtime context)");
1271     TagObject(context->embedder_data(), "(context data)");
1272     NATIVE_CONTEXT_FIELDS(EXTRACT_CONTEXT_FIELD);
1273     EXTRACT_CONTEXT_FIELD(OPTIMIZED_FUNCTIONS_LIST, unused,
1274                           optimized_functions_list);
1275     EXTRACT_CONTEXT_FIELD(OPTIMIZED_CODE_LIST, unused, optimized_code_list);
1276     EXTRACT_CONTEXT_FIELD(DEOPTIMIZED_CODE_LIST, unused, deoptimized_code_list);
1277     EXTRACT_CONTEXT_FIELD(NEXT_CONTEXT_LINK, unused, next_context_link);
1278 #undef EXTRACT_CONTEXT_FIELD
1279     STATIC_ASSERT(Context::OPTIMIZED_FUNCTIONS_LIST ==
1280                   Context::FIRST_WEAK_SLOT);
1281     STATIC_ASSERT(Context::NEXT_CONTEXT_LINK + 1 ==
1282                   Context::NATIVE_CONTEXT_SLOTS);
1283     STATIC_ASSERT(Context::FIRST_WEAK_SLOT + 4 ==
1284                   Context::NATIVE_CONTEXT_SLOTS);
1285   }
1286 }
1287
1288
1289 void V8HeapExplorer::ExtractMapReferences(int entry, Map* map) {
1290   Object* raw_transitions = map->raw_transitions();
1291   if (TransitionArray::IsFullTransitionArray(raw_transitions)) {
1292     TransitionArray* transitions = TransitionArray::cast(raw_transitions);
1293     int transitions_entry = GetEntry(transitions)->index();
1294
1295     if (FLAG_collect_maps && map->CanTransition()) {
1296       if (transitions->HasPrototypeTransitions()) {
1297         FixedArray* prototype_transitions =
1298             transitions->GetPrototypeTransitions();
1299         MarkAsWeakContainer(prototype_transitions);
1300         TagObject(prototype_transitions, "(prototype transitions");
1301         SetInternalReference(transitions, transitions_entry,
1302                              "prototype_transitions", prototype_transitions);
1303       }
1304       // TODO(alph): transitions keys are strong links.
1305       MarkAsWeakContainer(transitions);
1306     }
1307
1308     TagObject(transitions, "(transition array)");
1309     SetInternalReference(map, entry, "transitions", transitions,
1310                          Map::kTransitionsOffset);
1311   } else if (TransitionArray::IsSimpleTransition(raw_transitions)) {
1312     TagObject(raw_transitions, "(transition)");
1313     SetInternalReference(map, entry, "transition", raw_transitions,
1314                          Map::kTransitionsOffset);
1315   }
1316   DescriptorArray* descriptors = map->instance_descriptors();
1317   TagObject(descriptors, "(map descriptors)");
1318   SetInternalReference(map, entry,
1319                        "descriptors", descriptors,
1320                        Map::kDescriptorsOffset);
1321
1322   MarkAsWeakContainer(map->code_cache());
1323   SetInternalReference(map, entry,
1324                        "code_cache", map->code_cache(),
1325                        Map::kCodeCacheOffset);
1326   SetInternalReference(map, entry,
1327                        "prototype", map->prototype(), Map::kPrototypeOffset);
1328   Object* constructor_or_backpointer = map->constructor_or_backpointer();
1329   if (constructor_or_backpointer->IsMap()) {
1330     TagObject(constructor_or_backpointer, "(back pointer)");
1331     SetInternalReference(map, entry, "back_pointer", constructor_or_backpointer,
1332                          Map::kConstructorOrBackPointerOffset);
1333   } else {
1334     SetInternalReference(map, entry, "constructor", constructor_or_backpointer,
1335                          Map::kConstructorOrBackPointerOffset);
1336   }
1337   TagObject(map->dependent_code(), "(dependent code)");
1338   MarkAsWeakContainer(map->dependent_code());
1339   SetInternalReference(map, entry,
1340                        "dependent_code", map->dependent_code(),
1341                        Map::kDependentCodeOffset);
1342 }
1343
1344
1345 void V8HeapExplorer::ExtractSharedFunctionInfoReferences(
1346     int entry, SharedFunctionInfo* shared) {
1347   HeapObject* obj = shared;
1348   String* shared_name = shared->DebugName();
1349   const char* name = NULL;
1350   if (shared_name != *heap_->isolate()->factory()->empty_string()) {
1351     name = names_->GetName(shared_name);
1352     TagObject(shared->code(), names_->GetFormatted("(code for %s)", name));
1353   } else {
1354     TagObject(shared->code(), names_->GetFormatted("(%s code)",
1355         Code::Kind2String(shared->code()->kind())));
1356   }
1357
1358   SetInternalReference(obj, entry,
1359                        "name", shared->name(),
1360                        SharedFunctionInfo::kNameOffset);
1361   SetInternalReference(obj, entry,
1362                        "code", shared->code(),
1363                        SharedFunctionInfo::kCodeOffset);
1364   TagObject(shared->scope_info(), "(function scope info)");
1365   SetInternalReference(obj, entry,
1366                        "scope_info", shared->scope_info(),
1367                        SharedFunctionInfo::kScopeInfoOffset);
1368   SetInternalReference(obj, entry,
1369                        "instance_class_name", shared->instance_class_name(),
1370                        SharedFunctionInfo::kInstanceClassNameOffset);
1371   SetInternalReference(obj, entry,
1372                        "script", shared->script(),
1373                        SharedFunctionInfo::kScriptOffset);
1374   const char* construct_stub_name = name ?
1375       names_->GetFormatted("(construct stub code for %s)", name) :
1376       "(construct stub code)";
1377   TagObject(shared->construct_stub(), construct_stub_name);
1378   SetInternalReference(obj, entry,
1379                        "construct_stub", shared->construct_stub(),
1380                        SharedFunctionInfo::kConstructStubOffset);
1381   SetInternalReference(obj, entry,
1382                        "function_data", shared->function_data(),
1383                        SharedFunctionInfo::kFunctionDataOffset);
1384   SetInternalReference(obj, entry,
1385                        "debug_info", shared->debug_info(),
1386                        SharedFunctionInfo::kDebugInfoOffset);
1387   SetInternalReference(obj, entry,
1388                        "inferred_name", shared->inferred_name(),
1389                        SharedFunctionInfo::kInferredNameOffset);
1390   SetInternalReference(obj, entry,
1391                        "optimized_code_map", shared->optimized_code_map(),
1392                        SharedFunctionInfo::kOptimizedCodeMapOffset);
1393   SetInternalReference(obj, entry,
1394                        "feedback_vector", shared->feedback_vector(),
1395                        SharedFunctionInfo::kFeedbackVectorOffset);
1396 }
1397
1398
1399 void V8HeapExplorer::ExtractScriptReferences(int entry, Script* script) {
1400   HeapObject* obj = script;
1401   SetInternalReference(obj, entry,
1402                        "source", script->source(),
1403                        Script::kSourceOffset);
1404   SetInternalReference(obj, entry,
1405                        "name", script->name(),
1406                        Script::kNameOffset);
1407   SetInternalReference(obj, entry,
1408                        "context_data", script->context_data(),
1409                        Script::kContextOffset);
1410   TagObject(script->line_ends(), "(script line ends)");
1411   SetInternalReference(obj, entry,
1412                        "line_ends", script->line_ends(),
1413                        Script::kLineEndsOffset);
1414 }
1415
1416
1417 void V8HeapExplorer::ExtractAccessorInfoReferences(
1418     int entry, AccessorInfo* accessor_info) {
1419   SetInternalReference(accessor_info, entry, "name", accessor_info->name(),
1420                        AccessorInfo::kNameOffset);
1421   SetInternalReference(accessor_info, entry, "expected_receiver_type",
1422                        accessor_info->expected_receiver_type(),
1423                        AccessorInfo::kExpectedReceiverTypeOffset);
1424   if (accessor_info->IsExecutableAccessorInfo()) {
1425     ExecutableAccessorInfo* executable_accessor_info =
1426         ExecutableAccessorInfo::cast(accessor_info);
1427     SetInternalReference(executable_accessor_info, entry, "getter",
1428                          executable_accessor_info->getter(),
1429                          ExecutableAccessorInfo::kGetterOffset);
1430     SetInternalReference(executable_accessor_info, entry, "setter",
1431                          executable_accessor_info->setter(),
1432                          ExecutableAccessorInfo::kSetterOffset);
1433     SetInternalReference(executable_accessor_info, entry, "data",
1434                          executable_accessor_info->data(),
1435                          ExecutableAccessorInfo::kDataOffset);
1436   }
1437 }
1438
1439
1440 void V8HeapExplorer::ExtractAccessorPairReferences(
1441     int entry, AccessorPair* accessors) {
1442   SetInternalReference(accessors, entry, "getter", accessors->getter(),
1443                        AccessorPair::kGetterOffset);
1444   SetInternalReference(accessors, entry, "setter", accessors->setter(),
1445                        AccessorPair::kSetterOffset);
1446 }
1447
1448
1449 void V8HeapExplorer::ExtractCodeCacheReferences(
1450     int entry, CodeCache* code_cache) {
1451   TagObject(code_cache->default_cache(), "(default code cache)");
1452   SetInternalReference(code_cache, entry,
1453                        "default_cache", code_cache->default_cache(),
1454                        CodeCache::kDefaultCacheOffset);
1455   TagObject(code_cache->normal_type_cache(), "(code type cache)");
1456   SetInternalReference(code_cache, entry,
1457                        "type_cache", code_cache->normal_type_cache(),
1458                        CodeCache::kNormalTypeCacheOffset);
1459 }
1460
1461
1462 void V8HeapExplorer::TagBuiltinCodeObject(Code* code, const char* name) {
1463   TagObject(code, names_->GetFormatted("(%s builtin)", name));
1464 }
1465
1466
1467 void V8HeapExplorer::TagCodeObject(Code* code) {
1468   if (code->kind() == Code::STUB) {
1469     TagObject(code, names_->GetFormatted(
1470                         "(%s code)", CodeStub::MajorName(
1471                                          CodeStub::GetMajorKey(code), true)));
1472   }
1473 }
1474
1475
1476 void V8HeapExplorer::ExtractCodeReferences(int entry, Code* code) {
1477   TagCodeObject(code);
1478   TagObject(code->relocation_info(), "(code relocation info)");
1479   SetInternalReference(code, entry,
1480                        "relocation_info", code->relocation_info(),
1481                        Code::kRelocationInfoOffset);
1482   SetInternalReference(code, entry,
1483                        "handler_table", code->handler_table(),
1484                        Code::kHandlerTableOffset);
1485   TagObject(code->deoptimization_data(), "(code deopt data)");
1486   SetInternalReference(code, entry,
1487                        "deoptimization_data", code->deoptimization_data(),
1488                        Code::kDeoptimizationDataOffset);
1489   if (code->kind() == Code::FUNCTION) {
1490     SetInternalReference(code, entry,
1491                          "type_feedback_info", code->type_feedback_info(),
1492                          Code::kTypeFeedbackInfoOffset);
1493   }
1494   SetInternalReference(code, entry,
1495                        "gc_metadata", code->gc_metadata(),
1496                        Code::kGCMetadataOffset);
1497   SetInternalReference(code, entry,
1498                        "constant_pool", code->constant_pool(),
1499                        Code::kConstantPoolOffset);
1500   if (code->kind() == Code::OPTIMIZED_FUNCTION) {
1501     SetWeakReference(code, entry,
1502                      "next_code_link", code->next_code_link(),
1503                      Code::kNextCodeLinkOffset);
1504   }
1505 }
1506
1507
1508 void V8HeapExplorer::ExtractBoxReferences(int entry, Box* box) {
1509   SetInternalReference(box, entry, "value", box->value(), Box::kValueOffset);
1510 }
1511
1512
1513 void V8HeapExplorer::ExtractCellReferences(int entry, Cell* cell) {
1514   SetInternalReference(cell, entry, "value", cell->value(), Cell::kValueOffset);
1515 }
1516
1517
1518 void V8HeapExplorer::ExtractPropertyCellReferences(int entry,
1519                                                    PropertyCell* cell) {
1520   SetInternalReference(cell, entry, "value", cell->value(),
1521                        PropertyCell::kValueOffset);
1522   MarkAsWeakContainer(cell->dependent_code());
1523   SetInternalReference(cell, entry, "dependent_code", cell->dependent_code(),
1524                        PropertyCell::kDependentCodeOffset);
1525 }
1526
1527
1528 void V8HeapExplorer::ExtractAllocationSiteReferences(int entry,
1529                                                      AllocationSite* site) {
1530   SetInternalReference(site, entry, "transition_info", site->transition_info(),
1531                        AllocationSite::kTransitionInfoOffset);
1532   SetInternalReference(site, entry, "nested_site", site->nested_site(),
1533                        AllocationSite::kNestedSiteOffset);
1534   MarkAsWeakContainer(site->dependent_code());
1535   SetInternalReference(site, entry, "dependent_code", site->dependent_code(),
1536                        AllocationSite::kDependentCodeOffset);
1537   // Do not visit weak_next as it is not visited by the StaticVisitor,
1538   // and we're not very interested in weak_next field here.
1539   STATIC_ASSERT(AllocationSite::kWeakNextOffset >=
1540                AllocationSite::BodyDescriptor::kEndOffset);
1541 }
1542
1543
1544 class JSArrayBufferDataEntryAllocator : public HeapEntriesAllocator {
1545  public:
1546   JSArrayBufferDataEntryAllocator(size_t size, V8HeapExplorer* explorer)
1547       : size_(size)
1548       , explorer_(explorer) {
1549   }
1550   virtual HeapEntry* AllocateEntry(HeapThing ptr) {
1551     return explorer_->AddEntry(
1552         static_cast<Address>(ptr),
1553         HeapEntry::kNative, "system / JSArrayBufferData", size_);
1554   }
1555  private:
1556   size_t size_;
1557   V8HeapExplorer* explorer_;
1558 };
1559
1560
1561 void V8HeapExplorer::ExtractJSArrayBufferReferences(
1562     int entry, JSArrayBuffer* buffer) {
1563   SetWeakReference(buffer, entry, "weak_next", buffer->weak_next(),
1564                    JSArrayBuffer::kWeakNextOffset);
1565   SetWeakReference(buffer, entry,
1566                    "weak_first_view", buffer->weak_first_view(),
1567                    JSArrayBuffer::kWeakFirstViewOffset);
1568   // Setup a reference to a native memory backing_store object.
1569   if (!buffer->backing_store())
1570     return;
1571   size_t data_size = NumberToSize(heap_->isolate(), buffer->byte_length());
1572   JSArrayBufferDataEntryAllocator allocator(data_size, this);
1573   HeapEntry* data_entry =
1574       filler_->FindOrAddEntry(buffer->backing_store(), &allocator);
1575   filler_->SetNamedReference(HeapGraphEdge::kInternal,
1576                              entry, "backing_store", data_entry);
1577 }
1578
1579
1580 void V8HeapExplorer::ExtractFixedArrayReferences(int entry, FixedArray* array) {
1581   bool is_weak = weak_containers_.Contains(array);
1582   for (int i = 0, l = array->length(); i < l; ++i) {
1583     if (is_weak) {
1584       SetWeakReference(array, entry,
1585                        i, array->get(i), array->OffsetOfElementAt(i));
1586     } else {
1587       SetInternalReference(array, entry,
1588                            i, array->get(i), array->OffsetOfElementAt(i));
1589     }
1590   }
1591 }
1592
1593
1594 void V8HeapExplorer::ExtractClosureReferences(JSObject* js_obj, int entry) {
1595   if (!js_obj->IsJSFunction()) return;
1596
1597   JSFunction* func = JSFunction::cast(js_obj);
1598   if (func->shared()->bound()) {
1599     FixedArray* bindings = func->function_bindings();
1600     SetNativeBindReference(js_obj, entry, "bound_this",
1601                            bindings->get(JSFunction::kBoundThisIndex));
1602     SetNativeBindReference(js_obj, entry, "bound_function",
1603                            bindings->get(JSFunction::kBoundFunctionIndex));
1604     for (int i = JSFunction::kBoundArgumentsStartIndex;
1605          i < bindings->length(); i++) {
1606       const char* reference_name = names_->GetFormatted(
1607           "bound_argument_%d",
1608           i - JSFunction::kBoundArgumentsStartIndex);
1609       SetNativeBindReference(js_obj, entry, reference_name,
1610                              bindings->get(i));
1611     }
1612   }
1613 }
1614
1615
1616 void V8HeapExplorer::ExtractPropertyReferences(JSObject* js_obj, int entry) {
1617   if (js_obj->HasFastProperties()) {
1618     DescriptorArray* descs = js_obj->map()->instance_descriptors();
1619     int real_size = js_obj->map()->NumberOfOwnDescriptors();
1620     for (int i = 0; i < real_size; i++) {
1621       PropertyDetails details = descs->GetDetails(i);
1622       switch (details.location()) {
1623         case kField: {
1624           Representation r = details.representation();
1625           if (r.IsSmi() || r.IsDouble()) break;
1626
1627           Name* k = descs->GetKey(i);
1628           FieldIndex field_index = FieldIndex::ForDescriptor(js_obj->map(), i);
1629           Object* value = js_obj->RawFastPropertyAt(field_index);
1630           int field_offset =
1631               field_index.is_inobject() ? field_index.offset() : -1;
1632
1633           if (k != heap_->hidden_string()) {
1634             SetDataOrAccessorPropertyReference(details.kind(), js_obj, entry, k,
1635                                                value, NULL, field_offset);
1636           } else {
1637             TagObject(value, "(hidden properties)");
1638             SetInternalReference(js_obj, entry, "hidden_properties", value,
1639                                  field_offset);
1640           }
1641           break;
1642         }
1643         case kDescriptor:
1644           SetDataOrAccessorPropertyReference(details.kind(), js_obj, entry,
1645                                              descs->GetKey(i),
1646                                              descs->GetValue(i));
1647           break;
1648       }
1649     }
1650   } else {
1651     NameDictionary* dictionary = js_obj->property_dictionary();
1652     int length = dictionary->Capacity();
1653     for (int i = 0; i < length; ++i) {
1654       Object* k = dictionary->KeyAt(i);
1655       if (dictionary->IsKey(k)) {
1656         Object* target = dictionary->ValueAt(i);
1657         // We assume that global objects can only have slow properties.
1658         Object* value = target->IsPropertyCell()
1659             ? PropertyCell::cast(target)->value()
1660             : target;
1661         if (k == heap_->hidden_string()) {
1662           TagObject(value, "(hidden properties)");
1663           SetInternalReference(js_obj, entry, "hidden_properties", value);
1664           continue;
1665         }
1666         PropertyDetails details = dictionary->DetailsAt(i);
1667         SetDataOrAccessorPropertyReference(details.kind(), js_obj, entry,
1668                                            Name::cast(k), value);
1669       }
1670     }
1671   }
1672 }
1673
1674
1675 void V8HeapExplorer::ExtractAccessorPairProperty(JSObject* js_obj, int entry,
1676                                                  Name* key,
1677                                                  Object* callback_obj,
1678                                                  int field_offset) {
1679   if (!callback_obj->IsAccessorPair()) return;
1680   AccessorPair* accessors = AccessorPair::cast(callback_obj);
1681   SetPropertyReference(js_obj, entry, key, accessors, NULL, field_offset);
1682   Object* getter = accessors->getter();
1683   if (!getter->IsOddball()) {
1684     SetPropertyReference(js_obj, entry, key, getter, "get %s");
1685   }
1686   Object* setter = accessors->setter();
1687   if (!setter->IsOddball()) {
1688     SetPropertyReference(js_obj, entry, key, setter, "set %s");
1689   }
1690 }
1691
1692
1693 void V8HeapExplorer::ExtractElementReferences(JSObject* js_obj, int entry) {
1694   if (js_obj->HasFastObjectElements()) {
1695     FixedArray* elements = FixedArray::cast(js_obj->elements());
1696     int length = js_obj->IsJSArray() ?
1697         Smi::cast(JSArray::cast(js_obj)->length())->value() :
1698         elements->length();
1699     for (int i = 0; i < length; ++i) {
1700       if (!elements->get(i)->IsTheHole()) {
1701         SetElementReference(js_obj, entry, i, elements->get(i));
1702       }
1703     }
1704   } else if (js_obj->HasDictionaryElements()) {
1705     SeededNumberDictionary* dictionary = js_obj->element_dictionary();
1706     int length = dictionary->Capacity();
1707     for (int i = 0; i < length; ++i) {
1708       Object* k = dictionary->KeyAt(i);
1709       if (dictionary->IsKey(k)) {
1710         DCHECK(k->IsNumber());
1711         uint32_t index = static_cast<uint32_t>(k->Number());
1712         SetElementReference(js_obj, entry, index, dictionary->ValueAt(i));
1713       }
1714     }
1715   }
1716 }
1717
1718
1719 void V8HeapExplorer::ExtractInternalReferences(JSObject* js_obj, int entry) {
1720   int length = js_obj->GetInternalFieldCount();
1721   for (int i = 0; i < length; ++i) {
1722     Object* o = js_obj->GetInternalField(i);
1723     SetInternalReference(
1724         js_obj, entry, i, o, js_obj->GetInternalFieldOffset(i));
1725   }
1726 }
1727
1728
1729 String* V8HeapExplorer::GetConstructorName(JSObject* object) {
1730   Heap* heap = object->GetHeap();
1731   if (object->IsJSFunction()) return heap->closure_string();
1732   String* constructor_name = object->constructor_name();
1733   if (constructor_name == heap->Object_string()) {
1734     // TODO(verwaest): Try to get object.constructor.name in this case.
1735     // This requires handlification of the V8HeapExplorer.
1736   }
1737   return object->constructor_name();
1738 }
1739
1740
1741 HeapEntry* V8HeapExplorer::GetEntry(Object* obj) {
1742   if (!obj->IsHeapObject()) return NULL;
1743   return filler_->FindOrAddEntry(obj, this);
1744 }
1745
1746
1747 class RootsReferencesExtractor : public ObjectVisitor {
1748  private:
1749   struct IndexTag {
1750     IndexTag(int index, VisitorSynchronization::SyncTag tag)
1751         : index(index), tag(tag) { }
1752     int index;
1753     VisitorSynchronization::SyncTag tag;
1754   };
1755
1756  public:
1757   explicit RootsReferencesExtractor(Heap* heap)
1758       : collecting_all_references_(false),
1759         previous_reference_count_(0),
1760         heap_(heap) {
1761   }
1762
1763   void VisitPointers(Object** start, Object** end) {
1764     if (collecting_all_references_) {
1765       for (Object** p = start; p < end; p++) all_references_.Add(*p);
1766     } else {
1767       for (Object** p = start; p < end; p++) strong_references_.Add(*p);
1768     }
1769   }
1770
1771   void SetCollectingAllReferences() { collecting_all_references_ = true; }
1772
1773   void FillReferences(V8HeapExplorer* explorer) {
1774     DCHECK(strong_references_.length() <= all_references_.length());
1775     Builtins* builtins = heap_->isolate()->builtins();
1776     int strong_index = 0, all_index = 0, tags_index = 0, builtin_index = 0;
1777     while (all_index < all_references_.length()) {
1778       bool is_strong = strong_index < strong_references_.length()
1779           && strong_references_[strong_index] == all_references_[all_index];
1780       explorer->SetGcSubrootReference(reference_tags_[tags_index].tag,
1781                                       !is_strong,
1782                                       all_references_[all_index]);
1783       if (reference_tags_[tags_index].tag ==
1784           VisitorSynchronization::kBuiltins) {
1785         DCHECK(all_references_[all_index]->IsCode());
1786         explorer->TagBuiltinCodeObject(
1787             Code::cast(all_references_[all_index]),
1788             builtins->name(builtin_index++));
1789       }
1790       ++all_index;
1791       if (is_strong) ++strong_index;
1792       if (reference_tags_[tags_index].index == all_index) ++tags_index;
1793     }
1794   }
1795
1796   void Synchronize(VisitorSynchronization::SyncTag tag) {
1797     if (collecting_all_references_ &&
1798         previous_reference_count_ != all_references_.length()) {
1799       previous_reference_count_ = all_references_.length();
1800       reference_tags_.Add(IndexTag(previous_reference_count_, tag));
1801     }
1802   }
1803
1804  private:
1805   bool collecting_all_references_;
1806   List<Object*> strong_references_;
1807   List<Object*> all_references_;
1808   int previous_reference_count_;
1809   List<IndexTag> reference_tags_;
1810   Heap* heap_;
1811 };
1812
1813
1814 bool V8HeapExplorer::IterateAndExtractReferences(
1815     SnapshotFiller* filler) {
1816   filler_ = filler;
1817
1818   // Create references to the synthetic roots.
1819   SetRootGcRootsReference();
1820   for (int tag = 0; tag < VisitorSynchronization::kNumberOfSyncTags; tag++) {
1821     SetGcRootsReference(static_cast<VisitorSynchronization::SyncTag>(tag));
1822   }
1823
1824   // Make sure builtin code objects get their builtin tags
1825   // first. Otherwise a particular JSFunction object could set
1826   // its custom name to a generic builtin.
1827   RootsReferencesExtractor extractor(heap_);
1828   heap_->IterateRoots(&extractor, VISIT_ONLY_STRONG);
1829   extractor.SetCollectingAllReferences();
1830   heap_->IterateRoots(&extractor, VISIT_ALL);
1831   extractor.FillReferences(this);
1832
1833   // We have to do two passes as sometimes FixedArrays are used
1834   // to weakly hold their items, and it's impossible to distinguish
1835   // between these cases without processing the array owner first.
1836   bool interrupted =
1837       IterateAndExtractSinglePass<&V8HeapExplorer::ExtractReferencesPass1>() ||
1838       IterateAndExtractSinglePass<&V8HeapExplorer::ExtractReferencesPass2>();
1839
1840   if (interrupted) {
1841     filler_ = NULL;
1842     return false;
1843   }
1844
1845   filler_ = NULL;
1846   return progress_->ProgressReport(true);
1847 }
1848
1849
1850 template<V8HeapExplorer::ExtractReferencesMethod extractor>
1851 bool V8HeapExplorer::IterateAndExtractSinglePass() {
1852   // Now iterate the whole heap.
1853   bool interrupted = false;
1854   HeapIterator iterator(heap_, HeapIterator::kFilterUnreachable);
1855   // Heap iteration with filtering must be finished in any case.
1856   for (HeapObject* obj = iterator.next();
1857        obj != NULL;
1858        obj = iterator.next(), progress_->ProgressStep()) {
1859     if (interrupted) continue;
1860
1861     HeapEntry* heap_entry = GetEntry(obj);
1862     int entry = heap_entry->index();
1863     if ((this->*extractor)(entry, obj)) {
1864       SetInternalReference(obj, entry,
1865                            "map", obj->map(), HeapObject::kMapOffset);
1866       // Extract unvisited fields as hidden references and restore tags
1867       // of visited fields.
1868       IndexedReferencesExtractor refs_extractor(this, obj, entry);
1869       obj->Iterate(&refs_extractor);
1870     }
1871
1872     if (!progress_->ProgressReport(false)) interrupted = true;
1873   }
1874   return interrupted;
1875 }
1876
1877
1878 bool V8HeapExplorer::IsEssentialObject(Object* object) {
1879   return object->IsHeapObject()
1880       && !object->IsOddball()
1881       && object != heap_->empty_byte_array()
1882       && object != heap_->empty_fixed_array()
1883       && object != heap_->empty_descriptor_array()
1884       && object != heap_->fixed_array_map()
1885       && object != heap_->cell_map()
1886       && object != heap_->global_property_cell_map()
1887       && object != heap_->shared_function_info_map()
1888       && object != heap_->free_space_map()
1889       && object != heap_->one_pointer_filler_map()
1890       && object != heap_->two_pointer_filler_map();
1891 }
1892
1893
1894 void V8HeapExplorer::SetContextReference(HeapObject* parent_obj,
1895                                          int parent_entry,
1896                                          String* reference_name,
1897                                          Object* child_obj,
1898                                          int field_offset) {
1899   DCHECK(parent_entry == GetEntry(parent_obj)->index());
1900   HeapEntry* child_entry = GetEntry(child_obj);
1901   if (child_entry != NULL) {
1902     filler_->SetNamedReference(HeapGraphEdge::kContextVariable,
1903                                parent_entry,
1904                                names_->GetName(reference_name),
1905                                child_entry);
1906     IndexedReferencesExtractor::MarkVisitedField(parent_obj, field_offset);
1907   }
1908 }
1909
1910
1911 void V8HeapExplorer::SetNativeBindReference(HeapObject* parent_obj,
1912                                             int parent_entry,
1913                                             const char* reference_name,
1914                                             Object* child_obj) {
1915   DCHECK(parent_entry == GetEntry(parent_obj)->index());
1916   HeapEntry* child_entry = GetEntry(child_obj);
1917   if (child_entry != NULL) {
1918     filler_->SetNamedReference(HeapGraphEdge::kShortcut,
1919                                parent_entry,
1920                                reference_name,
1921                                child_entry);
1922   }
1923 }
1924
1925
1926 void V8HeapExplorer::SetElementReference(HeapObject* parent_obj,
1927                                          int parent_entry,
1928                                          int index,
1929                                          Object* child_obj) {
1930   DCHECK(parent_entry == GetEntry(parent_obj)->index());
1931   HeapEntry* child_entry = GetEntry(child_obj);
1932   if (child_entry != NULL) {
1933     filler_->SetIndexedReference(HeapGraphEdge::kElement,
1934                                  parent_entry,
1935                                  index,
1936                                  child_entry);
1937   }
1938 }
1939
1940
1941 void V8HeapExplorer::SetInternalReference(HeapObject* parent_obj,
1942                                           int parent_entry,
1943                                           const char* reference_name,
1944                                           Object* child_obj,
1945                                           int field_offset) {
1946   DCHECK(parent_entry == GetEntry(parent_obj)->index());
1947   HeapEntry* child_entry = GetEntry(child_obj);
1948   if (child_entry == NULL) return;
1949   if (IsEssentialObject(child_obj)) {
1950     filler_->SetNamedReference(HeapGraphEdge::kInternal,
1951                                parent_entry,
1952                                reference_name,
1953                                child_entry);
1954   }
1955   IndexedReferencesExtractor::MarkVisitedField(parent_obj, field_offset);
1956 }
1957
1958
1959 void V8HeapExplorer::SetInternalReference(HeapObject* parent_obj,
1960                                           int parent_entry,
1961                                           int index,
1962                                           Object* child_obj,
1963                                           int field_offset) {
1964   DCHECK(parent_entry == GetEntry(parent_obj)->index());
1965   HeapEntry* child_entry = GetEntry(child_obj);
1966   if (child_entry == NULL) return;
1967   if (IsEssentialObject(child_obj)) {
1968     filler_->SetNamedReference(HeapGraphEdge::kInternal,
1969                                parent_entry,
1970                                names_->GetName(index),
1971                                child_entry);
1972   }
1973   IndexedReferencesExtractor::MarkVisitedField(parent_obj, field_offset);
1974 }
1975
1976
1977 void V8HeapExplorer::SetHiddenReference(HeapObject* parent_obj,
1978                                         int parent_entry,
1979                                         int index,
1980                                         Object* child_obj) {
1981   DCHECK(parent_entry == GetEntry(parent_obj)->index());
1982   HeapEntry* child_entry = GetEntry(child_obj);
1983   if (child_entry != NULL && IsEssentialObject(child_obj)) {
1984     filler_->SetIndexedReference(HeapGraphEdge::kHidden,
1985                                  parent_entry,
1986                                  index,
1987                                  child_entry);
1988   }
1989 }
1990
1991
1992 void V8HeapExplorer::SetWeakReference(HeapObject* parent_obj,
1993                                       int parent_entry,
1994                                       const char* reference_name,
1995                                       Object* child_obj,
1996                                       int field_offset) {
1997   DCHECK(parent_entry == GetEntry(parent_obj)->index());
1998   HeapEntry* child_entry = GetEntry(child_obj);
1999   if (child_entry == NULL) return;
2000   if (IsEssentialObject(child_obj)) {
2001     filler_->SetNamedReference(HeapGraphEdge::kWeak,
2002                                parent_entry,
2003                                reference_name,
2004                                child_entry);
2005   }
2006   IndexedReferencesExtractor::MarkVisitedField(parent_obj, field_offset);
2007 }
2008
2009
2010 void V8HeapExplorer::SetWeakReference(HeapObject* parent_obj,
2011                                       int parent_entry,
2012                                       int index,
2013                                       Object* child_obj,
2014                                       int field_offset) {
2015   DCHECK(parent_entry == GetEntry(parent_obj)->index());
2016   HeapEntry* child_entry = GetEntry(child_obj);
2017   if (child_entry == NULL) return;
2018   if (IsEssentialObject(child_obj)) {
2019     filler_->SetNamedReference(HeapGraphEdge::kWeak,
2020                                parent_entry,
2021                                names_->GetFormatted("%d", index),
2022                                child_entry);
2023   }
2024   IndexedReferencesExtractor::MarkVisitedField(parent_obj, field_offset);
2025 }
2026
2027
2028 void V8HeapExplorer::SetDataOrAccessorPropertyReference(
2029     PropertyKind kind, JSObject* parent_obj, int parent_entry,
2030     Name* reference_name, Object* child_obj, const char* name_format_string,
2031     int field_offset) {
2032   if (kind == kAccessor) {
2033     ExtractAccessorPairProperty(parent_obj, parent_entry, reference_name,
2034                                 child_obj, field_offset);
2035   } else {
2036     SetPropertyReference(parent_obj, parent_entry, reference_name, child_obj,
2037                          name_format_string, field_offset);
2038   }
2039 }
2040
2041
2042 void V8HeapExplorer::SetPropertyReference(HeapObject* parent_obj,
2043                                           int parent_entry,
2044                                           Name* reference_name,
2045                                           Object* child_obj,
2046                                           const char* name_format_string,
2047                                           int field_offset) {
2048   DCHECK(parent_entry == GetEntry(parent_obj)->index());
2049   HeapEntry* child_entry = GetEntry(child_obj);
2050   if (child_entry != NULL) {
2051     HeapGraphEdge::Type type =
2052         reference_name->IsSymbol() || String::cast(reference_name)->length() > 0
2053             ? HeapGraphEdge::kProperty : HeapGraphEdge::kInternal;
2054     const char* name = name_format_string != NULL && reference_name->IsString()
2055         ? names_->GetFormatted(
2056               name_format_string,
2057               String::cast(reference_name)->ToCString(
2058                   DISALLOW_NULLS, ROBUST_STRING_TRAVERSAL).get()) :
2059         names_->GetName(reference_name);
2060
2061     filler_->SetNamedReference(type,
2062                                parent_entry,
2063                                name,
2064                                child_entry);
2065     IndexedReferencesExtractor::MarkVisitedField(parent_obj, field_offset);
2066   }
2067 }
2068
2069
2070 void V8HeapExplorer::SetRootGcRootsReference() {
2071   filler_->SetIndexedAutoIndexReference(
2072       HeapGraphEdge::kElement,
2073       snapshot_->root()->index(),
2074       snapshot_->gc_roots());
2075 }
2076
2077
2078 void V8HeapExplorer::SetUserGlobalReference(Object* child_obj) {
2079   HeapEntry* child_entry = GetEntry(child_obj);
2080   DCHECK(child_entry != NULL);
2081   filler_->SetNamedAutoIndexReference(
2082       HeapGraphEdge::kShortcut,
2083       snapshot_->root()->index(),
2084       child_entry);
2085 }
2086
2087
2088 void V8HeapExplorer::SetGcRootsReference(VisitorSynchronization::SyncTag tag) {
2089   filler_->SetIndexedAutoIndexReference(
2090       HeapGraphEdge::kElement,
2091       snapshot_->gc_roots()->index(),
2092       snapshot_->gc_subroot(tag));
2093 }
2094
2095
2096 void V8HeapExplorer::SetGcSubrootReference(
2097     VisitorSynchronization::SyncTag tag, bool is_weak, Object* child_obj) {
2098   HeapEntry* child_entry = GetEntry(child_obj);
2099   if (child_entry != NULL) {
2100     const char* name = GetStrongGcSubrootName(child_obj);
2101     if (name != NULL) {
2102       filler_->SetNamedReference(
2103           HeapGraphEdge::kInternal,
2104           snapshot_->gc_subroot(tag)->index(),
2105           name,
2106           child_entry);
2107     } else {
2108       if (is_weak) {
2109         filler_->SetNamedAutoIndexReference(
2110             HeapGraphEdge::kWeak,
2111             snapshot_->gc_subroot(tag)->index(),
2112             child_entry);
2113       } else {
2114         filler_->SetIndexedAutoIndexReference(
2115             HeapGraphEdge::kElement,
2116             snapshot_->gc_subroot(tag)->index(),
2117             child_entry);
2118       }
2119     }
2120
2121     // Add a shortcut to JS global object reference at snapshot root.
2122     if (child_obj->IsNativeContext()) {
2123       Context* context = Context::cast(child_obj);
2124       GlobalObject* global = context->global_object();
2125       if (global->IsJSGlobalObject()) {
2126         bool is_debug_object = false;
2127         is_debug_object = heap_->isolate()->debug()->IsDebugGlobal(global);
2128         if (!is_debug_object && !user_roots_.Contains(global)) {
2129           user_roots_.Insert(global);
2130           SetUserGlobalReference(global);
2131         }
2132       }
2133     }
2134   }
2135 }
2136
2137
2138 const char* V8HeapExplorer::GetStrongGcSubrootName(Object* object) {
2139   if (strong_gc_subroot_names_.is_empty()) {
2140 #define NAME_ENTRY(name) strong_gc_subroot_names_.SetTag(heap_->name(), #name);
2141 #define ROOT_NAME(type, name, camel_name) NAME_ENTRY(name)
2142     STRONG_ROOT_LIST(ROOT_NAME)
2143 #undef ROOT_NAME
2144 #define STRUCT_MAP_NAME(NAME, Name, name) NAME_ENTRY(name##_map)
2145     STRUCT_LIST(STRUCT_MAP_NAME)
2146 #undef STRUCT_MAP_NAME
2147 #define STRING_NAME(name, str) NAME_ENTRY(name)
2148     INTERNALIZED_STRING_LIST(STRING_NAME)
2149 #undef STRING_NAME
2150 #define SYMBOL_NAME(name) NAME_ENTRY(name)
2151     PRIVATE_SYMBOL_LIST(SYMBOL_NAME)
2152 #undef SYMBOL_NAME
2153 #define SYMBOL_NAME(name, varname, description) NAME_ENTRY(name)
2154     PUBLIC_SYMBOL_LIST(SYMBOL_NAME)
2155 #undef SYMBOL_NAME
2156 #undef NAME_ENTRY
2157     CHECK(!strong_gc_subroot_names_.is_empty());
2158   }
2159   return strong_gc_subroot_names_.GetTag(object);
2160 }
2161
2162
2163 void V8HeapExplorer::TagObject(Object* obj, const char* tag) {
2164   if (IsEssentialObject(obj)) {
2165     HeapEntry* entry = GetEntry(obj);
2166     if (entry->name()[0] == '\0') {
2167       entry->set_name(tag);
2168     }
2169   }
2170 }
2171
2172
2173 void V8HeapExplorer::MarkAsWeakContainer(Object* object) {
2174   if (IsEssentialObject(object) && object->IsFixedArray()) {
2175     weak_containers_.Insert(object);
2176   }
2177 }
2178
2179
2180 class GlobalObjectsEnumerator : public ObjectVisitor {
2181  public:
2182   virtual void VisitPointers(Object** start, Object** end) {
2183     for (Object** p = start; p < end; p++) {
2184       if ((*p)->IsNativeContext()) {
2185         Context* context = Context::cast(*p);
2186         JSObject* proxy = context->global_proxy();
2187         if (proxy->IsJSGlobalProxy()) {
2188           Object* global = proxy->map()->prototype();
2189           if (global->IsJSGlobalObject()) {
2190             objects_.Add(Handle<JSGlobalObject>(JSGlobalObject::cast(global)));
2191           }
2192         }
2193       }
2194     }
2195   }
2196   int count() { return objects_.length(); }
2197   Handle<JSGlobalObject>& at(int i) { return objects_[i]; }
2198
2199  private:
2200   List<Handle<JSGlobalObject> > objects_;
2201 };
2202
2203
2204 // Modifies heap. Must not be run during heap traversal.
2205 void V8HeapExplorer::TagGlobalObjects() {
2206   Isolate* isolate = heap_->isolate();
2207   HandleScope scope(isolate);
2208   GlobalObjectsEnumerator enumerator;
2209   isolate->global_handles()->IterateAllRoots(&enumerator);
2210   const char** urls = NewArray<const char*>(enumerator.count());
2211   for (int i = 0, l = enumerator.count(); i < l; ++i) {
2212     if (global_object_name_resolver_) {
2213       HandleScope scope(isolate);
2214       Handle<JSGlobalObject> global_obj = enumerator.at(i);
2215       urls[i] = global_object_name_resolver_->GetName(
2216           Utils::ToLocal(Handle<JSObject>::cast(global_obj)));
2217     } else {
2218       urls[i] = NULL;
2219     }
2220   }
2221
2222   DisallowHeapAllocation no_allocation;
2223   for (int i = 0, l = enumerator.count(); i < l; ++i) {
2224     objects_tags_.SetTag(*enumerator.at(i), urls[i]);
2225   }
2226
2227   DeleteArray(urls);
2228 }
2229
2230
2231 class GlobalHandlesExtractor : public ObjectVisitor {
2232  public:
2233   explicit GlobalHandlesExtractor(NativeObjectsExplorer* explorer)
2234       : explorer_(explorer) {}
2235   virtual ~GlobalHandlesExtractor() {}
2236   virtual void VisitPointers(Object** start, Object** end) {
2237     UNREACHABLE();
2238   }
2239   virtual void VisitEmbedderReference(Object** p, uint16_t class_id) {
2240     explorer_->VisitSubtreeWrapper(p, class_id);
2241   }
2242  private:
2243   NativeObjectsExplorer* explorer_;
2244 };
2245
2246
2247 class BasicHeapEntriesAllocator : public HeapEntriesAllocator {
2248  public:
2249   BasicHeapEntriesAllocator(
2250       HeapSnapshot* snapshot,
2251       HeapEntry::Type entries_type)
2252     : snapshot_(snapshot),
2253       names_(snapshot_->profiler()->names()),
2254       heap_object_map_(snapshot_->profiler()->heap_object_map()),
2255       entries_type_(entries_type) {
2256   }
2257   virtual HeapEntry* AllocateEntry(HeapThing ptr);
2258  private:
2259   HeapSnapshot* snapshot_;
2260   StringsStorage* names_;
2261   HeapObjectsMap* heap_object_map_;
2262   HeapEntry::Type entries_type_;
2263 };
2264
2265
2266 HeapEntry* BasicHeapEntriesAllocator::AllocateEntry(HeapThing ptr) {
2267   v8::RetainedObjectInfo* info = reinterpret_cast<v8::RetainedObjectInfo*>(ptr);
2268   intptr_t elements = info->GetElementCount();
2269   intptr_t size = info->GetSizeInBytes();
2270   const char* name = elements != -1
2271       ? names_->GetFormatted(
2272             "%s / %" V8_PTR_PREFIX "d entries", info->GetLabel(), elements)
2273       : names_->GetCopy(info->GetLabel());
2274   return snapshot_->AddEntry(
2275       entries_type_,
2276       name,
2277       heap_object_map_->GenerateId(info),
2278       size != -1 ? static_cast<int>(size) : 0,
2279       0);
2280 }
2281
2282
2283 NativeObjectsExplorer::NativeObjectsExplorer(
2284     HeapSnapshot* snapshot,
2285     SnapshottingProgressReportingInterface* progress)
2286     : isolate_(snapshot->profiler()->heap_object_map()->heap()->isolate()),
2287       snapshot_(snapshot),
2288       names_(snapshot_->profiler()->names()),
2289       embedder_queried_(false),
2290       objects_by_info_(RetainedInfosMatch),
2291       native_groups_(StringsMatch),
2292       filler_(NULL) {
2293   synthetic_entries_allocator_ =
2294       new BasicHeapEntriesAllocator(snapshot, HeapEntry::kSynthetic);
2295   native_entries_allocator_ =
2296       new BasicHeapEntriesAllocator(snapshot, HeapEntry::kNative);
2297 }
2298
2299
2300 NativeObjectsExplorer::~NativeObjectsExplorer() {
2301   for (HashMap::Entry* p = objects_by_info_.Start();
2302        p != NULL;
2303        p = objects_by_info_.Next(p)) {
2304     v8::RetainedObjectInfo* info =
2305         reinterpret_cast<v8::RetainedObjectInfo*>(p->key);
2306     info->Dispose();
2307     List<HeapObject*>* objects =
2308         reinterpret_cast<List<HeapObject*>* >(p->value);
2309     delete objects;
2310   }
2311   for (HashMap::Entry* p = native_groups_.Start();
2312        p != NULL;
2313        p = native_groups_.Next(p)) {
2314     v8::RetainedObjectInfo* info =
2315         reinterpret_cast<v8::RetainedObjectInfo*>(p->value);
2316     info->Dispose();
2317   }
2318   delete synthetic_entries_allocator_;
2319   delete native_entries_allocator_;
2320 }
2321
2322
2323 int NativeObjectsExplorer::EstimateObjectsCount() {
2324   FillRetainedObjects();
2325   return objects_by_info_.occupancy();
2326 }
2327
2328
2329 void NativeObjectsExplorer::FillRetainedObjects() {
2330   if (embedder_queried_) return;
2331   Isolate* isolate = isolate_;
2332   const GCType major_gc_type = kGCTypeMarkSweepCompact;
2333   // Record objects that are joined into ObjectGroups.
2334   isolate->heap()->CallGCPrologueCallbacks(
2335       major_gc_type, kGCCallbackFlagConstructRetainedObjectInfos);
2336   List<ObjectGroup*>* groups = isolate->global_handles()->object_groups();
2337   for (int i = 0; i < groups->length(); ++i) {
2338     ObjectGroup* group = groups->at(i);
2339     if (group->info == NULL) continue;
2340     List<HeapObject*>* list = GetListMaybeDisposeInfo(group->info);
2341     for (size_t j = 0; j < group->length; ++j) {
2342       HeapObject* obj = HeapObject::cast(*group->objects[j]);
2343       list->Add(obj);
2344       in_groups_.Insert(obj);
2345     }
2346     group->info = NULL;  // Acquire info object ownership.
2347   }
2348   isolate->global_handles()->RemoveObjectGroups();
2349   isolate->heap()->CallGCEpilogueCallbacks(major_gc_type, kNoGCCallbackFlags);
2350   // Record objects that are not in ObjectGroups, but have class ID.
2351   GlobalHandlesExtractor extractor(this);
2352   isolate->global_handles()->IterateAllRootsWithClassIds(&extractor);
2353   embedder_queried_ = true;
2354 }
2355
2356
2357 void NativeObjectsExplorer::FillImplicitReferences() {
2358   Isolate* isolate = isolate_;
2359   List<ImplicitRefGroup*>* groups =
2360       isolate->global_handles()->implicit_ref_groups();
2361   for (int i = 0; i < groups->length(); ++i) {
2362     ImplicitRefGroup* group = groups->at(i);
2363     HeapObject* parent = *group->parent;
2364     int parent_entry =
2365         filler_->FindOrAddEntry(parent, native_entries_allocator_)->index();
2366     DCHECK(parent_entry != HeapEntry::kNoEntry);
2367     Object*** children = group->children;
2368     for (size_t j = 0; j < group->length; ++j) {
2369       Object* child = *children[j];
2370       HeapEntry* child_entry =
2371           filler_->FindOrAddEntry(child, native_entries_allocator_);
2372       filler_->SetNamedReference(
2373           HeapGraphEdge::kInternal,
2374           parent_entry,
2375           "native",
2376           child_entry);
2377     }
2378   }
2379   isolate->global_handles()->RemoveImplicitRefGroups();
2380 }
2381
2382 List<HeapObject*>* NativeObjectsExplorer::GetListMaybeDisposeInfo(
2383     v8::RetainedObjectInfo* info) {
2384   HashMap::Entry* entry =
2385       objects_by_info_.Lookup(info, InfoHash(info), true);
2386   if (entry->value != NULL) {
2387     info->Dispose();
2388   } else {
2389     entry->value = new List<HeapObject*>(4);
2390   }
2391   return reinterpret_cast<List<HeapObject*>* >(entry->value);
2392 }
2393
2394
2395 bool NativeObjectsExplorer::IterateAndExtractReferences(
2396     SnapshotFiller* filler) {
2397   filler_ = filler;
2398   FillRetainedObjects();
2399   FillImplicitReferences();
2400   if (EstimateObjectsCount() > 0) {
2401     for (HashMap::Entry* p = objects_by_info_.Start();
2402          p != NULL;
2403          p = objects_by_info_.Next(p)) {
2404       v8::RetainedObjectInfo* info =
2405           reinterpret_cast<v8::RetainedObjectInfo*>(p->key);
2406       SetNativeRootReference(info);
2407       List<HeapObject*>* objects =
2408           reinterpret_cast<List<HeapObject*>* >(p->value);
2409       for (int i = 0; i < objects->length(); ++i) {
2410         SetWrapperNativeReferences(objects->at(i), info);
2411       }
2412     }
2413     SetRootNativeRootsReference();
2414   }
2415   filler_ = NULL;
2416   return true;
2417 }
2418
2419
2420 class NativeGroupRetainedObjectInfo : public v8::RetainedObjectInfo {
2421  public:
2422   explicit NativeGroupRetainedObjectInfo(const char* label)
2423       : disposed_(false),
2424         hash_(reinterpret_cast<intptr_t>(label)),
2425         label_(label) {
2426   }
2427
2428   virtual ~NativeGroupRetainedObjectInfo() {}
2429   virtual void Dispose() {
2430     CHECK(!disposed_);
2431     disposed_ = true;
2432     delete this;
2433   }
2434   virtual bool IsEquivalent(RetainedObjectInfo* other) {
2435     return hash_ == other->GetHash() && !strcmp(label_, other->GetLabel());
2436   }
2437   virtual intptr_t GetHash() { return hash_; }
2438   virtual const char* GetLabel() { return label_; }
2439
2440  private:
2441   bool disposed_;
2442   intptr_t hash_;
2443   const char* label_;
2444 };
2445
2446
2447 NativeGroupRetainedObjectInfo* NativeObjectsExplorer::FindOrAddGroupInfo(
2448     const char* label) {
2449   const char* label_copy = names_->GetCopy(label);
2450   uint32_t hash = StringHasher::HashSequentialString(
2451       label_copy,
2452       static_cast<int>(strlen(label_copy)),
2453       isolate_->heap()->HashSeed());
2454   HashMap::Entry* entry = native_groups_.Lookup(const_cast<char*>(label_copy),
2455                                                 hash, true);
2456   if (entry->value == NULL) {
2457     entry->value = new NativeGroupRetainedObjectInfo(label);
2458   }
2459   return static_cast<NativeGroupRetainedObjectInfo*>(entry->value);
2460 }
2461
2462
2463 void NativeObjectsExplorer::SetNativeRootReference(
2464     v8::RetainedObjectInfo* info) {
2465   HeapEntry* child_entry =
2466       filler_->FindOrAddEntry(info, native_entries_allocator_);
2467   DCHECK(child_entry != NULL);
2468   NativeGroupRetainedObjectInfo* group_info =
2469       FindOrAddGroupInfo(info->GetGroupLabel());
2470   HeapEntry* group_entry =
2471       filler_->FindOrAddEntry(group_info, synthetic_entries_allocator_);
2472   filler_->SetNamedAutoIndexReference(
2473       HeapGraphEdge::kInternal,
2474       group_entry->index(),
2475       child_entry);
2476 }
2477
2478
2479 void NativeObjectsExplorer::SetWrapperNativeReferences(
2480     HeapObject* wrapper, v8::RetainedObjectInfo* info) {
2481   HeapEntry* wrapper_entry = filler_->FindEntry(wrapper);
2482   DCHECK(wrapper_entry != NULL);
2483   HeapEntry* info_entry =
2484       filler_->FindOrAddEntry(info, native_entries_allocator_);
2485   DCHECK(info_entry != NULL);
2486   filler_->SetNamedReference(HeapGraphEdge::kInternal,
2487                              wrapper_entry->index(),
2488                              "native",
2489                              info_entry);
2490   filler_->SetIndexedAutoIndexReference(HeapGraphEdge::kElement,
2491                                         info_entry->index(),
2492                                         wrapper_entry);
2493 }
2494
2495
2496 void NativeObjectsExplorer::SetRootNativeRootsReference() {
2497   for (HashMap::Entry* entry = native_groups_.Start();
2498        entry;
2499        entry = native_groups_.Next(entry)) {
2500     NativeGroupRetainedObjectInfo* group_info =
2501         static_cast<NativeGroupRetainedObjectInfo*>(entry->value);
2502     HeapEntry* group_entry =
2503         filler_->FindOrAddEntry(group_info, native_entries_allocator_);
2504     DCHECK(group_entry != NULL);
2505     filler_->SetIndexedAutoIndexReference(
2506         HeapGraphEdge::kElement,
2507         snapshot_->root()->index(),
2508         group_entry);
2509   }
2510 }
2511
2512
2513 void NativeObjectsExplorer::VisitSubtreeWrapper(Object** p, uint16_t class_id) {
2514   if (in_groups_.Contains(*p)) return;
2515   Isolate* isolate = isolate_;
2516   v8::RetainedObjectInfo* info =
2517       isolate->heap_profiler()->ExecuteWrapperClassCallback(class_id, p);
2518   if (info == NULL) return;
2519   GetListMaybeDisposeInfo(info)->Add(HeapObject::cast(*p));
2520 }
2521
2522
2523 HeapSnapshotGenerator::HeapSnapshotGenerator(
2524     HeapSnapshot* snapshot,
2525     v8::ActivityControl* control,
2526     v8::HeapProfiler::ObjectNameResolver* resolver,
2527     Heap* heap)
2528     : snapshot_(snapshot),
2529       control_(control),
2530       v8_heap_explorer_(snapshot_, this, resolver),
2531       dom_explorer_(snapshot_, this),
2532       heap_(heap) {
2533 }
2534
2535
2536 bool HeapSnapshotGenerator::GenerateSnapshot() {
2537   v8_heap_explorer_.TagGlobalObjects();
2538
2539   // TODO(1562) Profiler assumes that any object that is in the heap after
2540   // full GC is reachable from the root when computing dominators.
2541   // This is not true for weakly reachable objects.
2542   // As a temporary solution we call GC twice.
2543   heap_->CollectAllGarbage(
2544       Heap::kMakeHeapIterableMask,
2545       "HeapSnapshotGenerator::GenerateSnapshot");
2546   heap_->CollectAllGarbage(
2547       Heap::kMakeHeapIterableMask,
2548       "HeapSnapshotGenerator::GenerateSnapshot");
2549
2550 #ifdef VERIFY_HEAP
2551   Heap* debug_heap = heap_;
2552   if (FLAG_verify_heap) {
2553     debug_heap->Verify();
2554   }
2555 #endif
2556
2557   SetProgressTotal(2);  // 2 passes.
2558
2559 #ifdef VERIFY_HEAP
2560   if (FLAG_verify_heap) {
2561     debug_heap->Verify();
2562   }
2563 #endif
2564
2565   snapshot_->AddSyntheticRootEntries();
2566
2567   if (!FillReferences()) return false;
2568
2569   snapshot_->FillChildren();
2570   snapshot_->RememberLastJSObjectId();
2571
2572   progress_counter_ = progress_total_;
2573   if (!ProgressReport(true)) return false;
2574   return true;
2575 }
2576
2577
2578 void HeapSnapshotGenerator::ProgressStep() {
2579   ++progress_counter_;
2580 }
2581
2582
2583 bool HeapSnapshotGenerator::ProgressReport(bool force) {
2584   const int kProgressReportGranularity = 10000;
2585   if (control_ != NULL
2586       && (force || progress_counter_ % kProgressReportGranularity == 0)) {
2587       return
2588           control_->ReportProgressValue(progress_counter_, progress_total_) ==
2589           v8::ActivityControl::kContinue;
2590   }
2591   return true;
2592 }
2593
2594
2595 void HeapSnapshotGenerator::SetProgressTotal(int iterations_count) {
2596   if (control_ == NULL) return;
2597   HeapIterator iterator(heap_, HeapIterator::kFilterUnreachable);
2598   progress_total_ = iterations_count * (
2599       v8_heap_explorer_.EstimateObjectsCount(&iterator) +
2600       dom_explorer_.EstimateObjectsCount());
2601   progress_counter_ = 0;
2602 }
2603
2604
2605 bool HeapSnapshotGenerator::FillReferences() {
2606   SnapshotFiller filler(snapshot_, &entries_);
2607   return v8_heap_explorer_.IterateAndExtractReferences(&filler)
2608       && dom_explorer_.IterateAndExtractReferences(&filler);
2609 }
2610
2611
2612 template<int bytes> struct MaxDecimalDigitsIn;
2613 template<> struct MaxDecimalDigitsIn<4> {
2614   static const int kSigned = 11;
2615   static const int kUnsigned = 10;
2616 };
2617 template<> struct MaxDecimalDigitsIn<8> {
2618   static const int kSigned = 20;
2619   static const int kUnsigned = 20;
2620 };
2621
2622
2623 class OutputStreamWriter {
2624  public:
2625   explicit OutputStreamWriter(v8::OutputStream* stream)
2626       : stream_(stream),
2627         chunk_size_(stream->GetChunkSize()),
2628         chunk_(chunk_size_),
2629         chunk_pos_(0),
2630         aborted_(false) {
2631     DCHECK(chunk_size_ > 0);
2632   }
2633   bool aborted() { return aborted_; }
2634   void AddCharacter(char c) {
2635     DCHECK(c != '\0');
2636     DCHECK(chunk_pos_ < chunk_size_);
2637     chunk_[chunk_pos_++] = c;
2638     MaybeWriteChunk();
2639   }
2640   void AddString(const char* s) {
2641     AddSubstring(s, StrLength(s));
2642   }
2643   void AddSubstring(const char* s, int n) {
2644     if (n <= 0) return;
2645     DCHECK(static_cast<size_t>(n) <= strlen(s));
2646     const char* s_end = s + n;
2647     while (s < s_end) {
2648       int s_chunk_size =
2649           Min(chunk_size_ - chunk_pos_, static_cast<int>(s_end - s));
2650       DCHECK(s_chunk_size > 0);
2651       MemCopy(chunk_.start() + chunk_pos_, s, s_chunk_size);
2652       s += s_chunk_size;
2653       chunk_pos_ += s_chunk_size;
2654       MaybeWriteChunk();
2655     }
2656   }
2657   void AddNumber(unsigned n) { AddNumberImpl<unsigned>(n, "%u"); }
2658   void Finalize() {
2659     if (aborted_) return;
2660     DCHECK(chunk_pos_ < chunk_size_);
2661     if (chunk_pos_ != 0) {
2662       WriteChunk();
2663     }
2664     stream_->EndOfStream();
2665   }
2666
2667  private:
2668   template<typename T>
2669   void AddNumberImpl(T n, const char* format) {
2670     // Buffer for the longest value plus trailing \0
2671     static const int kMaxNumberSize =
2672         MaxDecimalDigitsIn<sizeof(T)>::kUnsigned + 1;
2673     if (chunk_size_ - chunk_pos_ >= kMaxNumberSize) {
2674       int result = SNPrintF(
2675           chunk_.SubVector(chunk_pos_, chunk_size_), format, n);
2676       DCHECK(result != -1);
2677       chunk_pos_ += result;
2678       MaybeWriteChunk();
2679     } else {
2680       EmbeddedVector<char, kMaxNumberSize> buffer;
2681       int result = SNPrintF(buffer, format, n);
2682       USE(result);
2683       DCHECK(result != -1);
2684       AddString(buffer.start());
2685     }
2686   }
2687   void MaybeWriteChunk() {
2688     DCHECK(chunk_pos_ <= chunk_size_);
2689     if (chunk_pos_ == chunk_size_) {
2690       WriteChunk();
2691     }
2692   }
2693   void WriteChunk() {
2694     if (aborted_) return;
2695     if (stream_->WriteAsciiChunk(chunk_.start(), chunk_pos_) ==
2696         v8::OutputStream::kAbort) aborted_ = true;
2697     chunk_pos_ = 0;
2698   }
2699
2700   v8::OutputStream* stream_;
2701   int chunk_size_;
2702   ScopedVector<char> chunk_;
2703   int chunk_pos_;
2704   bool aborted_;
2705 };
2706
2707
2708 // type, name|index, to_node.
2709 const int HeapSnapshotJSONSerializer::kEdgeFieldsCount = 3;
2710 // type, name, id, self_size, edge_count, trace_node_id.
2711 const int HeapSnapshotJSONSerializer::kNodeFieldsCount = 6;
2712
2713 void HeapSnapshotJSONSerializer::Serialize(v8::OutputStream* stream) {
2714   if (AllocationTracker* allocation_tracker =
2715       snapshot_->profiler()->allocation_tracker()) {
2716     allocation_tracker->PrepareForSerialization();
2717   }
2718   DCHECK(writer_ == NULL);
2719   writer_ = new OutputStreamWriter(stream);
2720   SerializeImpl();
2721   delete writer_;
2722   writer_ = NULL;
2723 }
2724
2725
2726 void HeapSnapshotJSONSerializer::SerializeImpl() {
2727   DCHECK(0 == snapshot_->root()->index());
2728   writer_->AddCharacter('{');
2729   writer_->AddString("\"snapshot\":{");
2730   SerializeSnapshot();
2731   if (writer_->aborted()) return;
2732   writer_->AddString("},\n");
2733   writer_->AddString("\"nodes\":[");
2734   SerializeNodes();
2735   if (writer_->aborted()) return;
2736   writer_->AddString("],\n");
2737   writer_->AddString("\"edges\":[");
2738   SerializeEdges();
2739   if (writer_->aborted()) return;
2740   writer_->AddString("],\n");
2741
2742   writer_->AddString("\"trace_function_infos\":[");
2743   SerializeTraceNodeInfos();
2744   if (writer_->aborted()) return;
2745   writer_->AddString("],\n");
2746   writer_->AddString("\"trace_tree\":[");
2747   SerializeTraceTree();
2748   if (writer_->aborted()) return;
2749   writer_->AddString("],\n");
2750
2751   writer_->AddString("\"samples\":[");
2752   SerializeSamples();
2753   if (writer_->aborted()) return;
2754   writer_->AddString("],\n");
2755
2756   writer_->AddString("\"strings\":[");
2757   SerializeStrings();
2758   if (writer_->aborted()) return;
2759   writer_->AddCharacter(']');
2760   writer_->AddCharacter('}');
2761   writer_->Finalize();
2762 }
2763
2764
2765 int HeapSnapshotJSONSerializer::GetStringId(const char* s) {
2766   HashMap::Entry* cache_entry = strings_.Lookup(
2767       const_cast<char*>(s), StringHash(s), true);
2768   if (cache_entry->value == NULL) {
2769     cache_entry->value = reinterpret_cast<void*>(next_string_id_++);
2770   }
2771   return static_cast<int>(reinterpret_cast<intptr_t>(cache_entry->value));
2772 }
2773
2774
2775 namespace {
2776
2777 template<size_t size> struct ToUnsigned;
2778
2779 template<> struct ToUnsigned<4> {
2780   typedef uint32_t Type;
2781 };
2782
2783 template<> struct ToUnsigned<8> {
2784   typedef uint64_t Type;
2785 };
2786
2787 }  // namespace
2788
2789
2790 template<typename T>
2791 static int utoa_impl(T value, const Vector<char>& buffer, int buffer_pos) {
2792   STATIC_ASSERT(static_cast<T>(-1) > 0);  // Check that T is unsigned
2793   int number_of_digits = 0;
2794   T t = value;
2795   do {
2796     ++number_of_digits;
2797   } while (t /= 10);
2798
2799   buffer_pos += number_of_digits;
2800   int result = buffer_pos;
2801   do {
2802     int last_digit = static_cast<int>(value % 10);
2803     buffer[--buffer_pos] = '0' + last_digit;
2804     value /= 10;
2805   } while (value);
2806   return result;
2807 }
2808
2809
2810 template<typename T>
2811 static int utoa(T value, const Vector<char>& buffer, int buffer_pos) {
2812   typename ToUnsigned<sizeof(value)>::Type unsigned_value = value;
2813   STATIC_ASSERT(sizeof(value) == sizeof(unsigned_value));
2814   return utoa_impl(unsigned_value, buffer, buffer_pos);
2815 }
2816
2817
2818 void HeapSnapshotJSONSerializer::SerializeEdge(HeapGraphEdge* edge,
2819                                                bool first_edge) {
2820   // The buffer needs space for 3 unsigned ints, 3 commas, \n and \0
2821   static const int kBufferSize =
2822       MaxDecimalDigitsIn<sizeof(unsigned)>::kUnsigned * 3 + 3 + 2;  // NOLINT
2823   EmbeddedVector<char, kBufferSize> buffer;
2824   int edge_name_or_index = edge->type() == HeapGraphEdge::kElement
2825       || edge->type() == HeapGraphEdge::kHidden
2826       ? edge->index() : GetStringId(edge->name());
2827   int buffer_pos = 0;
2828   if (!first_edge) {
2829     buffer[buffer_pos++] = ',';
2830   }
2831   buffer_pos = utoa(edge->type(), buffer, buffer_pos);
2832   buffer[buffer_pos++] = ',';
2833   buffer_pos = utoa(edge_name_or_index, buffer, buffer_pos);
2834   buffer[buffer_pos++] = ',';
2835   buffer_pos = utoa(entry_index(edge->to()), buffer, buffer_pos);
2836   buffer[buffer_pos++] = '\n';
2837   buffer[buffer_pos++] = '\0';
2838   writer_->AddString(buffer.start());
2839 }
2840
2841
2842 void HeapSnapshotJSONSerializer::SerializeEdges() {
2843   List<HeapGraphEdge*>& edges = snapshot_->children();
2844   for (int i = 0; i < edges.length(); ++i) {
2845     DCHECK(i == 0 ||
2846            edges[i - 1]->from()->index() <= edges[i]->from()->index());
2847     SerializeEdge(edges[i], i == 0);
2848     if (writer_->aborted()) return;
2849   }
2850 }
2851
2852
2853 void HeapSnapshotJSONSerializer::SerializeNode(HeapEntry* entry) {
2854   // The buffer needs space for 4 unsigned ints, 1 size_t, 5 commas, \n and \0
2855   static const int kBufferSize =
2856       5 * MaxDecimalDigitsIn<sizeof(unsigned)>::kUnsigned  // NOLINT
2857       + MaxDecimalDigitsIn<sizeof(size_t)>::kUnsigned  // NOLINT
2858       + 6 + 1 + 1;
2859   EmbeddedVector<char, kBufferSize> buffer;
2860   int buffer_pos = 0;
2861   if (entry_index(entry) != 0) {
2862     buffer[buffer_pos++] = ',';
2863   }
2864   buffer_pos = utoa(entry->type(), buffer, buffer_pos);
2865   buffer[buffer_pos++] = ',';
2866   buffer_pos = utoa(GetStringId(entry->name()), buffer, buffer_pos);
2867   buffer[buffer_pos++] = ',';
2868   buffer_pos = utoa(entry->id(), buffer, buffer_pos);
2869   buffer[buffer_pos++] = ',';
2870   buffer_pos = utoa(entry->self_size(), buffer, buffer_pos);
2871   buffer[buffer_pos++] = ',';
2872   buffer_pos = utoa(entry->children_count(), buffer, buffer_pos);
2873   buffer[buffer_pos++] = ',';
2874   buffer_pos = utoa(entry->trace_node_id(), buffer, buffer_pos);
2875   buffer[buffer_pos++] = '\n';
2876   buffer[buffer_pos++] = '\0';
2877   writer_->AddString(buffer.start());
2878 }
2879
2880
2881 void HeapSnapshotJSONSerializer::SerializeNodes() {
2882   List<HeapEntry>& entries = snapshot_->entries();
2883   for (int i = 0; i < entries.length(); ++i) {
2884     SerializeNode(&entries[i]);
2885     if (writer_->aborted()) return;
2886   }
2887 }
2888
2889
2890 void HeapSnapshotJSONSerializer::SerializeSnapshot() {
2891   writer_->AddString("\"meta\":");
2892   // The object describing node serialization layout.
2893   // We use a set of macros to improve readability.
2894 #define JSON_A(s) "[" s "]"
2895 #define JSON_O(s) "{" s "}"
2896 #define JSON_S(s) "\"" s "\""
2897   writer_->AddString(JSON_O(
2898     JSON_S("node_fields") ":" JSON_A(
2899         JSON_S("type") ","
2900         JSON_S("name") ","
2901         JSON_S("id") ","
2902         JSON_S("self_size") ","
2903         JSON_S("edge_count") ","
2904         JSON_S("trace_node_id")) ","
2905     JSON_S("node_types") ":" JSON_A(
2906         JSON_A(
2907             JSON_S("hidden") ","
2908             JSON_S("array") ","
2909             JSON_S("string") ","
2910             JSON_S("object") ","
2911             JSON_S("code") ","
2912             JSON_S("closure") ","
2913             JSON_S("regexp") ","
2914             JSON_S("number") ","
2915             JSON_S("native") ","
2916             JSON_S("synthetic") ","
2917             JSON_S("concatenated string") ","
2918             JSON_S("sliced string")) ","
2919         JSON_S("string") ","
2920         JSON_S("number") ","
2921         JSON_S("number") ","
2922         JSON_S("number") ","
2923         JSON_S("number") ","
2924         JSON_S("number")) ","
2925     JSON_S("edge_fields") ":" JSON_A(
2926         JSON_S("type") ","
2927         JSON_S("name_or_index") ","
2928         JSON_S("to_node")) ","
2929     JSON_S("edge_types") ":" JSON_A(
2930         JSON_A(
2931             JSON_S("context") ","
2932             JSON_S("element") ","
2933             JSON_S("property") ","
2934             JSON_S("internal") ","
2935             JSON_S("hidden") ","
2936             JSON_S("shortcut") ","
2937             JSON_S("weak")) ","
2938         JSON_S("string_or_number") ","
2939         JSON_S("node")) ","
2940     JSON_S("trace_function_info_fields") ":" JSON_A(
2941         JSON_S("function_id") ","
2942         JSON_S("name") ","
2943         JSON_S("script_name") ","
2944         JSON_S("script_id") ","
2945         JSON_S("line") ","
2946         JSON_S("column")) ","
2947     JSON_S("trace_node_fields") ":" JSON_A(
2948         JSON_S("id") ","
2949         JSON_S("function_info_index") ","
2950         JSON_S("count") ","
2951         JSON_S("size") ","
2952         JSON_S("children")) ","
2953     JSON_S("sample_fields") ":" JSON_A(
2954         JSON_S("timestamp_us") ","
2955         JSON_S("last_assigned_id"))));
2956 #undef JSON_S
2957 #undef JSON_O
2958 #undef JSON_A
2959   writer_->AddString(",\"node_count\":");
2960   writer_->AddNumber(snapshot_->entries().length());
2961   writer_->AddString(",\"edge_count\":");
2962   writer_->AddNumber(snapshot_->edges().length());
2963   writer_->AddString(",\"trace_function_count\":");
2964   uint32_t count = 0;
2965   AllocationTracker* tracker = snapshot_->profiler()->allocation_tracker();
2966   if (tracker) {
2967     count = tracker->function_info_list().length();
2968   }
2969   writer_->AddNumber(count);
2970 }
2971
2972
2973 static void WriteUChar(OutputStreamWriter* w, unibrow::uchar u) {
2974   static const char hex_chars[] = "0123456789ABCDEF";
2975   w->AddString("\\u");
2976   w->AddCharacter(hex_chars[(u >> 12) & 0xf]);
2977   w->AddCharacter(hex_chars[(u >> 8) & 0xf]);
2978   w->AddCharacter(hex_chars[(u >> 4) & 0xf]);
2979   w->AddCharacter(hex_chars[u & 0xf]);
2980 }
2981
2982
2983 void HeapSnapshotJSONSerializer::SerializeTraceTree() {
2984   AllocationTracker* tracker = snapshot_->profiler()->allocation_tracker();
2985   if (!tracker) return;
2986   AllocationTraceTree* traces = tracker->trace_tree();
2987   SerializeTraceNode(traces->root());
2988 }
2989
2990
2991 void HeapSnapshotJSONSerializer::SerializeTraceNode(AllocationTraceNode* node) {
2992   // The buffer needs space for 4 unsigned ints, 4 commas, [ and \0
2993   const int kBufferSize =
2994       4 * MaxDecimalDigitsIn<sizeof(unsigned)>::kUnsigned  // NOLINT
2995       + 4 + 1 + 1;
2996   EmbeddedVector<char, kBufferSize> buffer;
2997   int buffer_pos = 0;
2998   buffer_pos = utoa(node->id(), buffer, buffer_pos);
2999   buffer[buffer_pos++] = ',';
3000   buffer_pos = utoa(node->function_info_index(), buffer, buffer_pos);
3001   buffer[buffer_pos++] = ',';
3002   buffer_pos = utoa(node->allocation_count(), buffer, buffer_pos);
3003   buffer[buffer_pos++] = ',';
3004   buffer_pos = utoa(node->allocation_size(), buffer, buffer_pos);
3005   buffer[buffer_pos++] = ',';
3006   buffer[buffer_pos++] = '[';
3007   buffer[buffer_pos++] = '\0';
3008   writer_->AddString(buffer.start());
3009
3010   Vector<AllocationTraceNode*> children = node->children();
3011   for (int i = 0; i < children.length(); i++) {
3012     if (i > 0) {
3013       writer_->AddCharacter(',');
3014     }
3015     SerializeTraceNode(children[i]);
3016   }
3017   writer_->AddCharacter(']');
3018 }
3019
3020
3021 // 0-based position is converted to 1-based during the serialization.
3022 static int SerializePosition(int position, const Vector<char>& buffer,
3023                              int buffer_pos) {
3024   if (position == -1) {
3025     buffer[buffer_pos++] = '0';
3026   } else {
3027     DCHECK(position >= 0);
3028     buffer_pos = utoa(static_cast<unsigned>(position + 1), buffer, buffer_pos);
3029   }
3030   return buffer_pos;
3031 }
3032
3033
3034 void HeapSnapshotJSONSerializer::SerializeTraceNodeInfos() {
3035   AllocationTracker* tracker = snapshot_->profiler()->allocation_tracker();
3036   if (!tracker) return;
3037   // The buffer needs space for 6 unsigned ints, 6 commas, \n and \0
3038   const int kBufferSize =
3039       6 * MaxDecimalDigitsIn<sizeof(unsigned)>::kUnsigned  // NOLINT
3040       + 6 + 1 + 1;
3041   EmbeddedVector<char, kBufferSize> buffer;
3042   const List<AllocationTracker::FunctionInfo*>& list =
3043       tracker->function_info_list();
3044   for (int i = 0; i < list.length(); i++) {
3045     AllocationTracker::FunctionInfo* info = list[i];
3046     int buffer_pos = 0;
3047     if (i > 0) {
3048       buffer[buffer_pos++] = ',';
3049     }
3050     buffer_pos = utoa(info->function_id, buffer, buffer_pos);
3051     buffer[buffer_pos++] = ',';
3052     buffer_pos = utoa(GetStringId(info->name), buffer, buffer_pos);
3053     buffer[buffer_pos++] = ',';
3054     buffer_pos = utoa(GetStringId(info->script_name), buffer, buffer_pos);
3055     buffer[buffer_pos++] = ',';
3056     // The cast is safe because script id is a non-negative Smi.
3057     buffer_pos = utoa(static_cast<unsigned>(info->script_id), buffer,
3058         buffer_pos);
3059     buffer[buffer_pos++] = ',';
3060     buffer_pos = SerializePosition(info->line, buffer, buffer_pos);
3061     buffer[buffer_pos++] = ',';
3062     buffer_pos = SerializePosition(info->column, buffer, buffer_pos);
3063     buffer[buffer_pos++] = '\n';
3064     buffer[buffer_pos++] = '\0';
3065     writer_->AddString(buffer.start());
3066   }
3067 }
3068
3069
3070 void HeapSnapshotJSONSerializer::SerializeSamples() {
3071   const List<HeapObjectsMap::TimeInterval>& samples =
3072       snapshot_->profiler()->heap_object_map()->samples();
3073   if (samples.is_empty()) return;
3074   base::TimeTicks start_time = samples[0].timestamp;
3075   // The buffer needs space for 2 unsigned ints, 2 commas, \n and \0
3076   const int kBufferSize = MaxDecimalDigitsIn<sizeof(
3077                               base::TimeDelta().InMicroseconds())>::kUnsigned +
3078                           MaxDecimalDigitsIn<sizeof(samples[0].id)>::kUnsigned +
3079                           2 + 1 + 1;
3080   EmbeddedVector<char, kBufferSize> buffer;
3081   for (int i = 0; i < samples.length(); i++) {
3082     HeapObjectsMap::TimeInterval& sample = samples[i];
3083     int buffer_pos = 0;
3084     if (i > 0) {
3085       buffer[buffer_pos++] = ',';
3086     }
3087     base::TimeDelta time_delta = sample.timestamp - start_time;
3088     buffer_pos = utoa(time_delta.InMicroseconds(), buffer, buffer_pos);
3089     buffer[buffer_pos++] = ',';
3090     buffer_pos = utoa(sample.last_assigned_id(), buffer, buffer_pos);
3091     buffer[buffer_pos++] = '\n';
3092     buffer[buffer_pos++] = '\0';
3093     writer_->AddString(buffer.start());
3094   }
3095 }
3096
3097
3098 void HeapSnapshotJSONSerializer::SerializeString(const unsigned char* s) {
3099   writer_->AddCharacter('\n');
3100   writer_->AddCharacter('\"');
3101   for ( ; *s != '\0'; ++s) {
3102     switch (*s) {
3103       case '\b':
3104         writer_->AddString("\\b");
3105         continue;
3106       case '\f':
3107         writer_->AddString("\\f");
3108         continue;
3109       case '\n':
3110         writer_->AddString("\\n");
3111         continue;
3112       case '\r':
3113         writer_->AddString("\\r");
3114         continue;
3115       case '\t':
3116         writer_->AddString("\\t");
3117         continue;
3118       case '\"':
3119       case '\\':
3120         writer_->AddCharacter('\\');
3121         writer_->AddCharacter(*s);
3122         continue;
3123       default:
3124         if (*s > 31 && *s < 128) {
3125           writer_->AddCharacter(*s);
3126         } else if (*s <= 31) {
3127           // Special character with no dedicated literal.
3128           WriteUChar(writer_, *s);
3129         } else {
3130           // Convert UTF-8 into \u UTF-16 literal.
3131           size_t length = 1, cursor = 0;
3132           for ( ; length <= 4 && *(s + length) != '\0'; ++length) { }
3133           unibrow::uchar c = unibrow::Utf8::CalculateValue(s, length, &cursor);
3134           if (c != unibrow::Utf8::kBadChar) {
3135             WriteUChar(writer_, c);
3136             DCHECK(cursor != 0);
3137             s += cursor - 1;
3138           } else {
3139             writer_->AddCharacter('?');
3140           }
3141         }
3142     }
3143   }
3144   writer_->AddCharacter('\"');
3145 }
3146
3147
3148 void HeapSnapshotJSONSerializer::SerializeStrings() {
3149   ScopedVector<const unsigned char*> sorted_strings(
3150       strings_.occupancy() + 1);
3151   for (HashMap::Entry* entry = strings_.Start();
3152        entry != NULL;
3153        entry = strings_.Next(entry)) {
3154     int index = static_cast<int>(reinterpret_cast<uintptr_t>(entry->value));
3155     sorted_strings[index] = reinterpret_cast<const unsigned char*>(entry->key);
3156   }
3157   writer_->AddString("\"<dummy>\"");
3158   for (int i = 1; i < sorted_strings.length(); ++i) {
3159     writer_->AddCharacter(',');
3160     SerializeString(sorted_strings[i]);
3161     if (writer_->aborted()) return;
3162   }
3163 }
3164
3165
3166 } }  // namespace v8::internal