Home | History | Annotate | Download | only in src 
      1 // Copyright 2013 the V8 project authors. All rights reserved.
      2 // Redistribution and use in source and binary forms, with or without
      3 // modification, are permitted provided that the following conditions are
      4 // met:
      5 //
      6 //     * Redistributions of source code must retain the above copyright
      7 //       notice, this list of conditions and the following disclaimer.
      8 //     * Redistributions in binary form must reproduce the above
      9 //       copyright notice, this list of conditions and the following
     10 //       disclaimer in the documentation and/or other materials provided
     11 //       with the distribution.
     12 //     * Neither the name of Google Inc. nor the names of its
     13 //       contributors may be used to endorse or promote products derived
     14 //       from this software without specific prior written permission.
     15 //
     16 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
     17 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
     18 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
     19 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
     20 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
     21 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
     22 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
     23 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
     24 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
     25 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
     26 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
     27 
     28 #ifndef V8_HEAP_SNAPSHOT_GENERATOR_H_
     29 #define V8_HEAP_SNAPSHOT_GENERATOR_H_
     30 
     31 #include "profile-generator-inl.h"
     32 
     33 namespace v8 {
     34 namespace internal {
     35 
     36 class HeapEntry;
     37 class HeapSnapshot;
     38 
     39 class HeapGraphEdge BASE_EMBEDDED {
     40  public:
     41   enum Type {
     42     kContextVariable = v8::HeapGraphEdge::kContextVariable,
     43     kElement = v8::HeapGraphEdge::kElement,
     44     kProperty = v8::HeapGraphEdge::kProperty,
     45     kInternal = v8::HeapGraphEdge::kInternal,
     46     kHidden = v8::HeapGraphEdge::kHidden,
     47     kShortcut = v8::HeapGraphEdge::kShortcut,
     48     kWeak = v8::HeapGraphEdge::kWeak
     49   };
     50 
     51   HeapGraphEdge() { }
     52   HeapGraphEdge(Type type, const char* name, int from, int to);
     53   HeapGraphEdge(Type type, int index, int from, int to);
     54   void ReplaceToIndexWithEntry(HeapSnapshot* snapshot);
     55 
     56   Type type() const { return static_cast<Type>(type_); }
     57   int index() const {
     58     ASSERT(type_ == kElement || type_ == kHidden || type_ == kWeak);
     59     return index_;
     60   }
     61   const char* name() const {
     62     ASSERT(type_ == kContextVariable
     63         || type_ == kProperty
     64         || type_ == kInternal
     65         || type_ == kShortcut);
     66     return name_;
     67   }
     68   INLINE(HeapEntry* from() const);
     69   HeapEntry* to() const { return to_entry_; }
     70 
     71  private:
     72   INLINE(HeapSnapshot* snapshot() const);
     73 
     74   unsigned type_ : 3;
     75   int from_index_ : 29;
     76   union {
     77     // During entries population |to_index_| is used for storing the index,
     78     // afterwards it is replaced with a pointer to the entry.
     79     int to_index_;
     80     HeapEntry* to_entry_;
     81   };
     82   union {
     83     int index_;
     84     const char* name_;
     85   };
     86 };
     87 
     88 
     89 // HeapEntry instances represent an entity from the heap (or a special
     90 // virtual node, e.g. root).
     91 class HeapEntry BASE_EMBEDDED {
     92  public:
     93   enum Type {
     94     kHidden = v8::HeapGraphNode::kHidden,
     95     kArray = v8::HeapGraphNode::kArray,
     96     kString = v8::HeapGraphNode::kString,
     97     kObject = v8::HeapGraphNode::kObject,
     98     kCode = v8::HeapGraphNode::kCode,
     99     kClosure = v8::HeapGraphNode::kClosure,
    100     kRegExp = v8::HeapGraphNode::kRegExp,
    101     kHeapNumber = v8::HeapGraphNode::kHeapNumber,
    102     kNative = v8::HeapGraphNode::kNative,
    103     kSynthetic = v8::HeapGraphNode::kSynthetic
    104   };
    105   static const int kNoEntry;
    106 
    107   HeapEntry() { }
    108   HeapEntry(HeapSnapshot* snapshot,
    109             Type type,
    110             const char* name,
    111             SnapshotObjectId id,
    112             int self_size);
    113 
    114   HeapSnapshot* snapshot() { return snapshot_; }
    115   Type type() { return static_cast<Type>(type_); }
    116   const char* name() { return name_; }
    117   void set_name(const char* name) { name_ = name; }
    118   inline SnapshotObjectId id() { return id_; }
    119   int self_size() { return self_size_; }
    120   INLINE(int index() const);
    121   int children_count() const { return children_count_; }
    122   INLINE(int set_children_index(int index));
    123   void add_child(HeapGraphEdge* edge) {
    124     children_arr()[children_count_++] = edge;
    125   }
    126   Vector<HeapGraphEdge*> children() {
    127     return Vector<HeapGraphEdge*>(children_arr(), children_count_); }
    128 
    129   void SetIndexedReference(
    130       HeapGraphEdge::Type type, int index, HeapEntry* entry);
    131   void SetNamedReference(
    132       HeapGraphEdge::Type type, const char* name, HeapEntry* entry);
    133 
    134   void Print(
    135       const char* prefix, const char* edge_name, int max_depth, int indent);
    136 
    137   Handle<HeapObject> GetHeapObject();
    138 
    139  private:
    140   INLINE(HeapGraphEdge** children_arr());
    141   const char* TypeAsString();
    142 
    143   unsigned type_: 4;
    144   int children_count_: 28;
    145   int children_index_;
    146   int self_size_;
    147   SnapshotObjectId id_;
    148   HeapSnapshot* snapshot_;
    149   const char* name_;
    150 };
    151 
    152 
    153 class HeapSnapshotsCollection;
    154 
    155 // HeapSnapshot represents a single heap snapshot. It is stored in
    156 // HeapSnapshotsCollection, which is also a factory for
    157 // HeapSnapshots. All HeapSnapshots share strings copied from JS heap
    158 // to be able to return them even if they were collected.
    159 // HeapSnapshotGenerator fills in a HeapSnapshot.
    160 class HeapSnapshot {
    161  public:
    162   HeapSnapshot(HeapSnapshotsCollection* collection,
    163                const char* title,
    164                unsigned uid);
    165   void Delete();
    166 
    167   HeapSnapshotsCollection* collection() { return collection_; }
    168   const char* title() { return title_; }
    169   unsigned uid() { return uid_; }
    170   size_t RawSnapshotSize() const;
    171   HeapEntry* root() { return &entries_[root_index_]; }
    172   HeapEntry* gc_roots() { return &entries_[gc_roots_index_]; }
    173   HeapEntry* natives_root() { return &entries_[natives_root_index_]; }
    174   HeapEntry* gc_subroot(int index) {
    175     return &entries_[gc_subroot_indexes_[index]];
    176   }
    177   List<HeapEntry>& entries() { return entries_; }
    178   List<HeapGraphEdge>& edges() { return edges_; }
    179   List<HeapGraphEdge*>& children() { return children_; }
    180   void RememberLastJSObjectId();
    181   SnapshotObjectId max_snapshot_js_object_id() const {
    182     return max_snapshot_js_object_id_;
    183   }
    184 
    185   HeapEntry* AddEntry(HeapEntry::Type type,
    186                       const char* name,
    187                       SnapshotObjectId id,
    188                       int size);
    189   HeapEntry* AddRootEntry();
    190   HeapEntry* AddGcRootsEntry();
    191   HeapEntry* AddGcSubrootEntry(int tag);
    192   HeapEntry* AddNativesRootEntry();
    193   HeapEntry* GetEntryById(SnapshotObjectId id);
    194   List<HeapEntry*>* GetSortedEntriesList();
    195   void FillChildren();
    196 
    197   void Print(int max_depth);
    198   void PrintEntriesSize();
    199 
    200  private:
    201   HeapSnapshotsCollection* collection_;
    202   const char* title_;
    203   unsigned uid_;
    204   int root_index_;
    205   int gc_roots_index_;
    206   int natives_root_index_;
    207   int gc_subroot_indexes_[VisitorSynchronization::kNumberOfSyncTags];
    208   List<HeapEntry> entries_;
    209   List<HeapGraphEdge> edges_;
    210   List<HeapGraphEdge*> children_;
    211   List<HeapEntry*> sorted_entries_;
    212   SnapshotObjectId max_snapshot_js_object_id_;
    213 
    214   friend class HeapSnapshotTester;
    215 
    216   DISALLOW_COPY_AND_ASSIGN(HeapSnapshot);
    217 };
    218 
    219 
    220 class HeapObjectsMap {
    221  public:
    222   explicit HeapObjectsMap(Heap* heap);
    223 
    224   Heap* heap() const { return heap_; }
    225 
    226   void SnapshotGenerationFinished();
    227   SnapshotObjectId FindEntry(Address addr);
    228   SnapshotObjectId FindOrAddEntry(Address addr, unsigned int size);
    229   void MoveObject(Address from, Address to);
    230   SnapshotObjectId last_assigned_id() const {
    231     return next_id_ - kObjectIdStep;
    232   }
    233 
    234   void StopHeapObjectsTracking();
    235   SnapshotObjectId PushHeapObjectsStats(OutputStream* stream);
    236   size_t GetUsedMemorySize() const;
    237 
    238   static SnapshotObjectId GenerateId(v8::RetainedObjectInfo* info);
    239   static inline SnapshotObjectId GetNthGcSubrootId(int delta);
    240 
    241   static const int kObjectIdStep = 2;
    242   static const SnapshotObjectId kInternalRootObjectId;
    243   static const SnapshotObjectId kGcRootsObjectId;
    244   static const SnapshotObjectId kNativesRootObjectId;
    245   static const SnapshotObjectId kGcRootsFirstSubrootId;
    246   static const SnapshotObjectId kFirstAvailableObjectId;
    247 
    248  private:
    249   struct EntryInfo {
    250   EntryInfo(SnapshotObjectId id, Address addr, unsigned int size)
    251       : id(id), addr(addr), size(size), accessed(true) { }
    252   EntryInfo(SnapshotObjectId id, Address addr, unsigned int size, bool accessed)
    253       : id(id), addr(addr), size(size), accessed(accessed) { }
    254     SnapshotObjectId id;
    255     Address addr;
    256     unsigned int size;
    257     bool accessed;
    258   };
    259   struct TimeInterval {
    260     explicit TimeInterval(SnapshotObjectId id) : id(id), size(0), count(0) { }
    261     SnapshotObjectId id;
    262     uint32_t size;
    263     uint32_t count;
    264   };
    265 
    266   void UpdateHeapObjectsMap();
    267   void RemoveDeadEntries();
    268 
    269   SnapshotObjectId next_id_;
    270   HashMap entries_map_;
    271   List<EntryInfo> entries_;
    272   List<TimeInterval> time_intervals_;
    273   Heap* heap_;
    274 
    275   DISALLOW_COPY_AND_ASSIGN(HeapObjectsMap);
    276 };
    277 
    278 
    279 class HeapSnapshotsCollection {
    280  public:
    281   explicit HeapSnapshotsCollection(Heap* heap);
    282   ~HeapSnapshotsCollection();
    283 
    284   Heap* heap() const { return ids_.heap(); }
    285 
    286   bool is_tracking_objects() { return is_tracking_objects_; }
    287   SnapshotObjectId PushHeapObjectsStats(OutputStream* stream) {
    288     return ids_.PushHeapObjectsStats(stream);
    289   }
    290   void StartHeapObjectsTracking() { is_tracking_objects_ = true; }
    291   void StopHeapObjectsTracking() { ids_.StopHeapObjectsTracking(); }
    292 
    293   HeapSnapshot* NewSnapshot(const char* name, unsigned uid);
    294   void SnapshotGenerationFinished(HeapSnapshot* snapshot);
    295   List<HeapSnapshot*>* snapshots() { return &snapshots_; }
    296   void RemoveSnapshot(HeapSnapshot* snapshot);
    297 
    298   StringsStorage* names() { return &names_; }
    299 
    300   SnapshotObjectId FindObjectId(Address object_addr) {
    301     return ids_.FindEntry(object_addr);
    302   }
    303   SnapshotObjectId GetObjectId(Address object_addr, int object_size) {
    304     return ids_.FindOrAddEntry(object_addr, object_size);
    305   }
    306   Handle<HeapObject> FindHeapObjectById(SnapshotObjectId id);
    307   void ObjectMoveEvent(Address from, Address to) { ids_.MoveObject(from, to); }
    308   SnapshotObjectId last_assigned_id() const {
    309     return ids_.last_assigned_id();
    310   }
    311   size_t GetUsedMemorySize() const;
    312 
    313  private:
    314   bool is_tracking_objects_;  // Whether tracking object moves is needed.
    315   List<HeapSnapshot*> snapshots_;
    316   StringsStorage names_;
    317   // Mapping from HeapObject addresses to objects' uids.
    318   HeapObjectsMap ids_;
    319 
    320   DISALLOW_COPY_AND_ASSIGN(HeapSnapshotsCollection);
    321 };
    322 
    323 
    324 // A typedef for referencing anything that can be snapshotted living
    325 // in any kind of heap memory.
    326 typedef void* HeapThing;
    327 
    328 
    329 // An interface that creates HeapEntries by HeapThings.
    330 class HeapEntriesAllocator {
    331  public:
    332   virtual ~HeapEntriesAllocator() { }
    333   virtual HeapEntry* AllocateEntry(HeapThing ptr) = 0;
    334 };
    335 
    336 
    337 // The HeapEntriesMap instance is used to track a mapping between
    338 // real heap objects and their representations in heap snapshots.
    339 class HeapEntriesMap {
    340  public:
    341   HeapEntriesMap();
    342 
    343   int Map(HeapThing thing);
    344   void Pair(HeapThing thing, int entry);
    345 
    346  private:
    347   static uint32_t Hash(HeapThing thing) {
    348     return ComputeIntegerHash(
    349         static_cast<uint32_t>(reinterpret_cast<uintptr_t>(thing)),
    350         v8::internal::kZeroHashSeed);
    351   }
    352   static bool HeapThingsMatch(HeapThing key1, HeapThing key2) {
    353     return key1 == key2;
    354   }
    355 
    356   HashMap entries_;
    357 
    358   friend class HeapObjectsSet;
    359 
    360   DISALLOW_COPY_AND_ASSIGN(HeapEntriesMap);
    361 };
    362 
    363 
    364 class HeapObjectsSet {
    365  public:
    366   HeapObjectsSet();
    367   void Clear();
    368   bool Contains(Object* object);
    369   void Insert(Object* obj);
    370   const char* GetTag(Object* obj);
    371   void SetTag(Object* obj, const char* tag);
    372   bool is_empty() const { return entries_.occupancy() == 0; }
    373 
    374  private:
    375   HashMap entries_;
    376 
    377   DISALLOW_COPY_AND_ASSIGN(HeapObjectsSet);
    378 };
    379 
    380 
    381 // An interface used to populate a snapshot with nodes and edges.
    382 class SnapshotFillerInterface {
    383  public:
    384   virtual ~SnapshotFillerInterface() { }
    385   virtual HeapEntry* AddEntry(HeapThing ptr,
    386                               HeapEntriesAllocator* allocator) = 0;
    387   virtual HeapEntry* FindEntry(HeapThing ptr) = 0;
    388   virtual HeapEntry* FindOrAddEntry(HeapThing ptr,
    389                                     HeapEntriesAllocator* allocator) = 0;
    390   virtual void SetIndexedReference(HeapGraphEdge::Type type,
    391                                    int parent_entry,
    392                                    int index,
    393                                    HeapEntry* child_entry) = 0;
    394   virtual void SetIndexedAutoIndexReference(HeapGraphEdge::Type type,
    395                                             int parent_entry,
    396                                             HeapEntry* child_entry) = 0;
    397   virtual void SetNamedReference(HeapGraphEdge::Type type,
    398                                  int parent_entry,
    399                                  const char* reference_name,
    400                                  HeapEntry* child_entry) = 0;
    401   virtual void SetNamedAutoIndexReference(HeapGraphEdge::Type type,
    402                                           int parent_entry,
    403                                           HeapEntry* child_entry) = 0;
    404 };
    405 
    406 
    407 class SnapshottingProgressReportingInterface {
    408  public:
    409   virtual ~SnapshottingProgressReportingInterface() { }
    410   virtual void ProgressStep() = 0;
    411   virtual bool ProgressReport(bool force) = 0;
    412 };
    413 
    414 
    415 // An implementation of V8 heap graph extractor.
    416 class V8HeapExplorer : public HeapEntriesAllocator {
    417  public:
    418   V8HeapExplorer(HeapSnapshot* snapshot,
    419                  SnapshottingProgressReportingInterface* progress,
    420                  v8::HeapProfiler::ObjectNameResolver* resolver);
    421   virtual ~V8HeapExplorer();
    422   virtual HeapEntry* AllocateEntry(HeapThing ptr);
    423   void AddRootEntries(SnapshotFillerInterface* filler);
    424   int EstimateObjectsCount(HeapIterator* iterator);
    425   bool IterateAndExtractReferences(SnapshotFillerInterface* filler);
    426   void TagGlobalObjects();
    427 
    428   static String* GetConstructorName(JSObject* object);
    429 
    430   static HeapObject* const kInternalRootObject;
    431 
    432  private:
    433   HeapEntry* AddEntry(HeapObject* object);
    434   HeapEntry* AddEntry(HeapObject* object,
    435                       HeapEntry::Type type,
    436                       const char* name);
    437   const char* GetSystemEntryName(HeapObject* object);
    438 
    439   void ExtractReferences(HeapObject* obj);
    440   void ExtractJSGlobalProxyReferences(int entry, JSGlobalProxy* proxy);
    441   void ExtractJSObjectReferences(int entry, JSObject* js_obj);
    442   void ExtractStringReferences(int entry, String* obj);
    443   void ExtractContextReferences(int entry, Context* context);
    444   void ExtractMapReferences(int entry, Map* map);
    445   void ExtractSharedFunctionInfoReferences(int entry,
    446                                            SharedFunctionInfo* shared);
    447   void ExtractScriptReferences(int entry, Script* script);
    448   void ExtractAccessorPairReferences(int entry, AccessorPair* accessors);
    449   void ExtractCodeCacheReferences(int entry, CodeCache* code_cache);
    450   void ExtractCodeReferences(int entry, Code* code);
    451   void ExtractCellReferences(int entry, Cell* cell);
    452   void ExtractPropertyCellReferences(int entry, PropertyCell* cell);
    453   void ExtractAllocationSiteReferences(int entry, AllocationSite* site);
    454   void ExtractClosureReferences(JSObject* js_obj, int entry);
    455   void ExtractPropertyReferences(JSObject* js_obj, int entry);
    456   bool ExtractAccessorPairProperty(JSObject* js_obj, int entry,
    457                                    Object* key, Object* callback_obj);
    458   void ExtractElementReferences(JSObject* js_obj, int entry);
    459   void ExtractInternalReferences(JSObject* js_obj, int entry);
    460   bool IsEssentialObject(Object* object);
    461   void SetContextReference(HeapObject* parent_obj,
    462                            int parent,
    463                            String* reference_name,
    464                            Object* child,
    465                            int field_offset);
    466   void SetNativeBindReference(HeapObject* parent_obj,
    467                               int parent,
    468                               const char* reference_name,
    469                               Object* child);
    470   void SetElementReference(HeapObject* parent_obj,
    471                            int parent,
    472                            int index,
    473                            Object* child);
    474   void SetInternalReference(HeapObject* parent_obj,
    475                             int parent,
    476                             const char* reference_name,
    477                             Object* child,
    478                             int field_offset = -1);
    479   void SetInternalReference(HeapObject* parent_obj,
    480                             int parent,
    481                             int index,
    482                             Object* child,
    483                             int field_offset = -1);
    484   void SetHiddenReference(HeapObject* parent_obj,
    485                           int parent,
    486                           int index,
    487                           Object* child);
    488   void SetWeakReference(HeapObject* parent_obj,
    489                         int parent,
    490                         int index,
    491                         Object* child_obj,
    492                         int field_offset);
    493   void SetPropertyReference(HeapObject* parent_obj,
    494                             int parent,
    495                             Name* reference_name,
    496                             Object* child,
    497                             const char* name_format_string = NULL,
    498                             int field_offset = -1);
    499   void SetUserGlobalReference(Object* user_global);
    500   void SetRootGcRootsReference();
    501   void SetGcRootsReference(VisitorSynchronization::SyncTag tag);
    502   void SetGcSubrootReference(
    503       VisitorSynchronization::SyncTag tag, bool is_weak, Object* child);
    504   const char* GetStrongGcSubrootName(Object* object);
    505   void TagObject(Object* obj, const char* tag);
    506 
    507   HeapEntry* GetEntry(Object* obj);
    508 
    509   static inline HeapObject* GetNthGcSubrootObject(int delta);
    510   static inline int GetGcSubrootOrder(HeapObject* subroot);
    511 
    512   Heap* heap_;
    513   HeapSnapshot* snapshot_;
    514   HeapSnapshotsCollection* collection_;
    515   SnapshottingProgressReportingInterface* progress_;
    516   SnapshotFillerInterface* filler_;
    517   HeapObjectsSet objects_tags_;
    518   HeapObjectsSet strong_gc_subroot_names_;
    519   HeapObjectsSet user_roots_;
    520   v8::HeapProfiler::ObjectNameResolver* global_object_name_resolver_;
    521 
    522   static HeapObject* const kGcRootsObject;
    523   static HeapObject* const kFirstGcSubrootObject;
    524   static HeapObject* const kLastGcSubrootObject;
    525 
    526   friend class IndexedReferencesExtractor;
    527   friend class GcSubrootsEnumerator;
    528   friend class RootsReferencesExtractor;
    529 
    530   DISALLOW_COPY_AND_ASSIGN(V8HeapExplorer);
    531 };
    532 
    533 
    534 class NativeGroupRetainedObjectInfo;
    535 
    536 
    537 // An implementation of retained native objects extractor.
    538 class NativeObjectsExplorer {
    539  public:
    540   NativeObjectsExplorer(HeapSnapshot* snapshot,
    541                       SnapshottingProgressReportingInterface* progress);
    542   virtual ~NativeObjectsExplorer();
    543   void AddRootEntries(SnapshotFillerInterface* filler);
    544   int EstimateObjectsCount();
    545   bool IterateAndExtractReferences(SnapshotFillerInterface* filler);
    546 
    547  private:
    548   void FillRetainedObjects();
    549   void FillImplicitReferences();
    550   List<HeapObject*>* GetListMaybeDisposeInfo(v8::RetainedObjectInfo* info);
    551   void SetNativeRootReference(v8::RetainedObjectInfo* info);
    552   void SetRootNativeRootsReference();
    553   void SetWrapperNativeReferences(HeapObject* wrapper,
    554                                       v8::RetainedObjectInfo* info);
    555   void VisitSubtreeWrapper(Object** p, uint16_t class_id);
    556 
    557   static uint32_t InfoHash(v8::RetainedObjectInfo* info) {
    558     return ComputeIntegerHash(static_cast<uint32_t>(info->GetHash()),
    559                               v8::internal::kZeroHashSeed);
    560   }
    561   static bool RetainedInfosMatch(void* key1, void* key2) {
    562     return key1 == key2 ||
    563         (reinterpret_cast<v8::RetainedObjectInfo*>(key1))->IsEquivalent(
    564             reinterpret_cast<v8::RetainedObjectInfo*>(key2));
    565   }
    566   INLINE(static bool StringsMatch(void* key1, void* key2)) {
    567     return strcmp(reinterpret_cast<char*>(key1),
    568                   reinterpret_cast<char*>(key2)) == 0;
    569   }
    570 
    571   NativeGroupRetainedObjectInfo* FindOrAddGroupInfo(const char* label);
    572 
    573   HeapSnapshot* snapshot_;
    574   HeapSnapshotsCollection* collection_;
    575   SnapshottingProgressReportingInterface* progress_;
    576   bool embedder_queried_;
    577   HeapObjectsSet in_groups_;
    578   // RetainedObjectInfo* -> List<HeapObject*>*
    579   HashMap objects_by_info_;
    580   HashMap native_groups_;
    581   HeapEntriesAllocator* synthetic_entries_allocator_;
    582   HeapEntriesAllocator* native_entries_allocator_;
    583   // Used during references extraction.
    584   SnapshotFillerInterface* filler_;
    585 
    586   static HeapThing const kNativesRootObject;
    587 
    588   friend class GlobalHandlesExtractor;
    589 
    590   DISALLOW_COPY_AND_ASSIGN(NativeObjectsExplorer);
    591 };
    592 
    593 
    594 class HeapSnapshotGenerator : public SnapshottingProgressReportingInterface {
    595  public:
    596   HeapSnapshotGenerator(HeapSnapshot* snapshot,
    597                         v8::ActivityControl* control,
    598                         v8::HeapProfiler::ObjectNameResolver* resolver,
    599                         Heap* heap);
    600   bool GenerateSnapshot();
    601 
    602  private:
    603   bool FillReferences();
    604   void ProgressStep();
    605   bool ProgressReport(bool force = false);
    606   void SetProgressTotal(int iterations_count);
    607 
    608   HeapSnapshot* snapshot_;
    609   v8::ActivityControl* control_;
    610   V8HeapExplorer v8_heap_explorer_;
    611   NativeObjectsExplorer dom_explorer_;
    612   // Mapping from HeapThing pointers to HeapEntry* pointers.
    613   HeapEntriesMap entries_;
    614   // Used during snapshot generation.
    615   int progress_counter_;
    616   int progress_total_;
    617   Heap* heap_;
    618 
    619   DISALLOW_COPY_AND_ASSIGN(HeapSnapshotGenerator);
    620 };
    621 
    622 class OutputStreamWriter;
    623 
    624 class HeapSnapshotJSONSerializer {
    625  public:
    626   explicit HeapSnapshotJSONSerializer(HeapSnapshot* snapshot)
    627       : snapshot_(snapshot),
    628         strings_(ObjectsMatch),
    629         next_node_id_(1),
    630         next_string_id_(1),
    631         writer_(NULL) {
    632   }
    633   void Serialize(v8::OutputStream* stream);
    634 
    635  private:
    636   INLINE(static bool ObjectsMatch(void* key1, void* key2)) {
    637     return key1 == key2;
    638   }
    639 
    640   INLINE(static uint32_t ObjectHash(const void* key)) {
    641     return ComputeIntegerHash(
    642         static_cast<uint32_t>(reinterpret_cast<uintptr_t>(key)),
    643         v8::internal::kZeroHashSeed);
    644   }
    645 
    646   int GetStringId(const char* s);
    647   int entry_index(HeapEntry* e) { return e->index() * kNodeFieldsCount; }
    648   void SerializeEdge(HeapGraphEdge* edge, bool first_edge);
    649   void SerializeEdges();
    650   void SerializeImpl();
    651   void SerializeNode(HeapEntry* entry);
    652   void SerializeNodes();
    653   void SerializeSnapshot();
    654   void SerializeString(const unsigned char* s);
    655   void SerializeStrings();
    656   void SortHashMap(HashMap* map, List<HashMap::Entry*>* sorted_entries);
    657 
    658   static const int kEdgeFieldsCount;
    659   static const int kNodeFieldsCount;
    660 
    661   HeapSnapshot* snapshot_;
    662   HashMap strings_;
    663   int next_node_id_;
    664   int next_string_id_;
    665   OutputStreamWriter* writer_;
    666 
    667   friend class HeapSnapshotJSONSerializerEnumerator;
    668   friend class HeapSnapshotJSONSerializerIterator;
    669 
    670   DISALLOW_COPY_AND_ASSIGN(HeapSnapshotJSONSerializer);
    671 };
    672 
    673 
    674 } }  // namespace v8::internal
    675 
    676 #endif  // V8_HEAP_SNAPSHOT_GENERATOR_H_
    677 
    678