src/3rdparty/v8/src/profile-generator.h

   1 // Copyright 2011 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_PROFILE_GENERATOR_H_
  29 #define V8_PROFILE_GENERATOR_H_
  30
  31 #include "allocation.h"
  32 #include "hashmap.h"
  33 #include "../include/v8-profiler.h"
  34
  35 namespace v8 {
  36 namespace internal {
  37
  38 class TokenEnumerator {
  39  public:
  40   TokenEnumerator();
  41   ~TokenEnumerator();
  42   int GetTokenId(Object* token);
  43
  44   static const int kNoSecurityToken = -1;
  45   static const int kInheritsSecurityToken = -2;
  46
  47  private:
  48   static void TokenRemovedCallback(v8::Persistent<v8::Value> handle,
  49                                    void* parameter);
  50   void TokenRemoved(Object** token_location);
  51
  52   List<Object**> token_locations_;
  53   List<bool> token_removed_;
  54
  55   friend class TokenEnumeratorTester;
  56
  57   DISALLOW_COPY_AND_ASSIGN(TokenEnumerator);
  58 };
  59
  60
  61 // Provides a storage of strings allocated in C++ heap, to hold them
  62 // forever, even if they disappear from JS heap or external storage.
  63 class StringsStorage {
  64  public:
  65   StringsStorage();
  66   ~StringsStorage();
  67
  68   const char* GetCopy(const char* src);
  69   const char* GetFormatted(const char* format, ...);
  70   const char* GetVFormatted(const char* format, va_list args);
  71   const char* GetName(String* name);
  72   const char* GetName(int index);
  73   inline const char* GetFunctionName(String* name);
  74   inline const char* GetFunctionName(const char* name);
  75
  76  private:
  77   static const int kMaxNameSize = 1024;
  78
  79   INLINE(static bool StringsMatch(void* key1, void* key2)) {
  80     return strcmp(reinterpret_cast<char*>(key1),
  81                   reinterpret_cast<char*>(key2)) == 0;
  82   }
  83   const char* AddOrDisposeString(char* str, uint32_t hash);
  84
  85   // Mapping of strings by String::Hash to const char* strings.
  86   HashMap names_;
  87
  88   DISALLOW_COPY_AND_ASSIGN(StringsStorage);
  89 };
  90
  91
  92 class CodeEntry {
  93  public:
  94   // CodeEntry doesn't own name strings, just references them.
  95   INLINE(CodeEntry(Logger::LogEventsAndTags tag,
  96                    const char* name_prefix,
  97                    const char* name,
  98                    const char* resource_name,
  99                    int line_number,
 100                    int security_token_id));
 101
 102   INLINE(bool is_js_function() const) { return is_js_function_tag(tag_); }
 103   INLINE(const char* name_prefix() const) { return name_prefix_; }
 104   INLINE(bool has_name_prefix() const) { return name_prefix_[0] != '\0'; }
 105   INLINE(const char* name() const) { return name_; }
 106   INLINE(const char* resource_name() const) { return resource_name_; }
 107   INLINE(int line_number() const) { return line_number_; }
 108   INLINE(int shared_id() const) { return shared_id_; }
 109   INLINE(void set_shared_id(int shared_id)) { shared_id_ = shared_id; }
 110   INLINE(int security_token_id() const) { return security_token_id_; }
 111
 112   INLINE(static bool is_js_function_tag(Logger::LogEventsAndTags tag));
 113
 114   void CopyData(const CodeEntry& source);
 115   uint32_t GetCallUid() const;
 116   bool IsSameAs(CodeEntry* entry) const;
 117
 118   static const char* const kEmptyNamePrefix;
 119
 120  private:
 121   Logger::LogEventsAndTags tag_;
 122   const char* name_prefix_;
 123   const char* name_;
 124   const char* resource_name_;
 125   int line_number_;
 126   int shared_id_;
 127   int security_token_id_;
 128
 129   DISALLOW_COPY_AND_ASSIGN(CodeEntry);
 130 };
 131
 132
 133 class ProfileTree;
 134
 135 class ProfileNode {
 136  public:
 137   INLINE(ProfileNode(ProfileTree* tree, CodeEntry* entry));
 138
 139   ProfileNode* FindChild(CodeEntry* entry);
 140   ProfileNode* FindOrAddChild(CodeEntry* entry);
 141   INLINE(void IncrementSelfTicks()) { ++self_ticks_; }
 142   INLINE(void IncreaseSelfTicks(unsigned amount)) { self_ticks_ += amount; }
 143   INLINE(void IncreaseTotalTicks(unsigned amount)) { total_ticks_ += amount; }
 144
 145   INLINE(CodeEntry* entry() const) { return entry_; }
 146   INLINE(unsigned self_ticks() const) { return self_ticks_; }
 147   INLINE(unsigned total_ticks() const) { return total_ticks_; }
 148   INLINE(const List<ProfileNode*>* children() const) { return &children_list_; }
 149   double GetSelfMillis() const;
 150   double GetTotalMillis() const;
 151
 152   void Print(int indent);
 153
 154  private:
 155   INLINE(static bool CodeEntriesMatch(void* entry1, void* entry2)) {
 156     return reinterpret_cast<CodeEntry*>(entry1)->IsSameAs(
 157         reinterpret_cast<CodeEntry*>(entry2));
 158   }
 159
 160   INLINE(static uint32_t CodeEntryHash(CodeEntry* entry)) {
 161     return entry->GetCallUid();
 162   }
 163
 164   ProfileTree* tree_;
 165   CodeEntry* entry_;
 166   unsigned total_ticks_;
 167   unsigned self_ticks_;
 168   // Mapping from CodeEntry* to ProfileNode*
 169   HashMap children_;
 170   List<ProfileNode*> children_list_;
 171
 172   DISALLOW_COPY_AND_ASSIGN(ProfileNode);
 173 };
 174
 175
 176 class ProfileTree {
 177  public:
 178   ProfileTree();
 179   ~ProfileTree();
 180
 181   void AddPathFromEnd(const Vector<CodeEntry*>& path);
 182   void AddPathFromStart(const Vector<CodeEntry*>& path);
 183   void CalculateTotalTicks();
 184   void FilteredClone(ProfileTree* src, int security_token_id);
 185
 186   double TicksToMillis(unsigned ticks) const {
 187     return ticks * ms_to_ticks_scale_;
 188   }
 189   ProfileNode* root() const { return root_; }
 190   void SetTickRatePerMs(double ticks_per_ms);
 191
 192   void ShortPrint();
 193   void Print() {
 194     root_->Print(0);
 195   }
 196
 197  private:
 198   template <typename Callback>
 199   void TraverseDepthFirst(Callback* callback);
 200
 201   CodeEntry root_entry_;
 202   ProfileNode* root_;
 203   double ms_to_ticks_scale_;
 204
 205   DISALLOW_COPY_AND_ASSIGN(ProfileTree);
 206 };
 207
 208
 209 class CpuProfile {
 210  public:
 211   CpuProfile(const char* title, unsigned uid)
 212       : title_(title), uid_(uid) { }
 213
 214   // Add pc -> ... -> main() call path to the profile.
 215   void AddPath(const Vector<CodeEntry*>& path);
 216   void CalculateTotalTicks();
 217   void SetActualSamplingRate(double actual_sampling_rate);
 218   CpuProfile* FilteredClone(int security_token_id);
 219
 220   INLINE(const char* title() const) { return title_; }
 221   INLINE(unsigned uid() const) { return uid_; }
 222   INLINE(const ProfileTree* top_down() const) { return &top_down_; }
 223   INLINE(const ProfileTree* bottom_up() const) { return &bottom_up_; }
 224
 225   void UpdateTicksScale();
 226
 227   void ShortPrint();
 228   void Print();
 229
 230  private:
 231   const char* title_;
 232   unsigned uid_;
 233   ProfileTree top_down_;
 234   ProfileTree bottom_up_;
 235
 236   DISALLOW_COPY_AND_ASSIGN(CpuProfile);
 237 };
 238
 239
 240 class CodeMap {
 241  public:
 242   CodeMap() : next_shared_id_(1) { }
 243   void AddCode(Address addr, CodeEntry* entry, unsigned size);
 244   void MoveCode(Address from, Address to);
 245   CodeEntry* FindEntry(Address addr);
 246   int GetSharedId(Address addr);
 247
 248   void Print();
 249
 250  private:
 251   struct CodeEntryInfo {
 252     CodeEntryInfo(CodeEntry* an_entry, unsigned a_size)
 253         : entry(an_entry), size(a_size) { }
 254     CodeEntry* entry;
 255     unsigned size;
 256   };
 257
 258   struct CodeTreeConfig {
 259     typedef Address Key;
 260     typedef CodeEntryInfo Value;
 261     static const Key kNoKey;
 262     static const Value NoValue() { return CodeEntryInfo(NULL, 0); }
 263     static int Compare(const Key& a, const Key& b) {
 264       return a < b ? -1 : (a > b ? 1 : 0);
 265     }
 266   };
 267   typedef SplayTree<CodeTreeConfig> CodeTree;
 268
 269   class CodeTreePrinter {
 270    public:
 271     void Call(const Address& key, const CodeEntryInfo& value);
 272   };
 273
 274   void DeleteAllCoveredCode(Address start, Address end);
 275
 276   // Fake CodeEntry pointer to distinguish shared function entries.
 277   static CodeEntry* const kSharedFunctionCodeEntry;
 278
 279   CodeTree tree_;
 280   int next_shared_id_;
 281
 282   DISALLOW_COPY_AND_ASSIGN(CodeMap);
 283 };
 284
 285
 286 class CpuProfilesCollection {
 287  public:
 288   CpuProfilesCollection();
 289   ~CpuProfilesCollection();
 290
 291   bool StartProfiling(const char* title, unsigned uid);
 292   bool StartProfiling(String* title, unsigned uid);
 293   CpuProfile* StopProfiling(int security_token_id,
 294                             const char* title,
 295                             double actual_sampling_rate);
 296   List<CpuProfile*>* Profiles(int security_token_id);
 297   const char* GetName(String* name) {
 298     return function_and_resource_names_.GetName(name);
 299   }
 300   const char* GetName(int args_count) {
 301     return function_and_resource_names_.GetName(args_count);
 302   }
 303   CpuProfile* GetProfile(int security_token_id, unsigned uid);
 304   bool IsLastProfile(const char* title);
 305   void RemoveProfile(CpuProfile* profile);
 306   bool HasDetachedProfiles() { return detached_profiles_.length() > 0; }
 307
 308   CodeEntry* NewCodeEntry(Logger::LogEventsAndTags tag,
 309                           String* name, String* resource_name, int line_number);
 310   CodeEntry* NewCodeEntry(Logger::LogEventsAndTags tag, const char* name);
 311   CodeEntry* NewCodeEntry(Logger::LogEventsAndTags tag,
 312                           const char* name_prefix, String* name);
 313   CodeEntry* NewCodeEntry(Logger::LogEventsAndTags tag, int args_count);
 314   CodeEntry* NewCodeEntry(int security_token_id);
 315
 316   // Called from profile generator thread.
 317   void AddPathToCurrentProfiles(const Vector<CodeEntry*>& path);
 318
 319   // Limits the number of profiles that can be simultaneously collected.
 320   static const int kMaxSimultaneousProfiles = 100;
 321
 322  private:
 323   const char* GetFunctionName(String* name) {
 324     return function_and_resource_names_.GetFunctionName(name);
 325   }
 326   const char* GetFunctionName(const char* name) {
 327     return function_and_resource_names_.GetFunctionName(name);
 328   }
 329   int GetProfileIndex(unsigned uid);
 330   List<CpuProfile*>* GetProfilesList(int security_token_id);
 331   int TokenToIndex(int security_token_id);
 332
 333   INLINE(static bool UidsMatch(void* key1, void* key2)) {
 334     return key1 == key2;
 335   }
 336
 337   StringsStorage function_and_resource_names_;
 338   List<CodeEntry*> code_entries_;
 339   List<List<CpuProfile*>* > profiles_by_token_;
 340   // Mapping from profiles' uids to indexes in the second nested list
 341   // of profiles_by_token_.
 342   HashMap profiles_uids_;
 343   List<CpuProfile*> detached_profiles_;
 344
 345   // Accessed by VM thread and profile generator thread.
 346   List<CpuProfile*> current_profiles_;
 347   Semaphore* current_profiles_semaphore_;
 348
 349   DISALLOW_COPY_AND_ASSIGN(CpuProfilesCollection);
 350 };
 351
 352
 353 class SampleRateCalculator {
 354  public:
 355   SampleRateCalculator()
 356       : result_(Logger::kSamplingIntervalMs * kResultScale),
 357         ticks_per_ms_(Logger::kSamplingIntervalMs),
 358         measurements_count_(0),
 359         wall_time_query_countdown_(1) {
 360   }
 361
 362   double ticks_per_ms() {
 363     return result_ / static_cast<double>(kResultScale);
 364   }
 365   void Tick();
 366   void UpdateMeasurements(double current_time);
 367
 368   // Instead of querying current wall time each tick,
 369   // we use this constant to control query intervals.
 370   static const unsigned kWallTimeQueryIntervalMs = 100;
 371
 372  private:
 373   // As the result needs to be accessed from a different thread, we
 374   // use type that guarantees atomic writes to memory.  There should
 375   // be <= 1000 ticks per second, thus storing a value of a 10 ** 5
 376   // order should provide enough precision while keeping away from a
 377   // potential overflow.
 378   static const int kResultScale = 100000;
 379
 380   AtomicWord result_;
 381   // All other fields are accessed only from the sampler thread.
 382   double ticks_per_ms_;
 383   unsigned measurements_count_;
 384   unsigned wall_time_query_countdown_;
 385   double last_wall_time_;
 386
 387   DISALLOW_COPY_AND_ASSIGN(SampleRateCalculator);
 388 };
 389
 390
 391 class ProfileGenerator {
 392  public:
 393   explicit ProfileGenerator(CpuProfilesCollection* profiles);
 394
 395   INLINE(CodeEntry* NewCodeEntry(Logger::LogEventsAndTags tag,
 396                                  String* name,
 397                                  String* resource_name,
 398                                  int line_number)) {
 399     return profiles_->NewCodeEntry(tag, name, resource_name, line_number);
 400   }
 401
 402   INLINE(CodeEntry* NewCodeEntry(Logger::LogEventsAndTags tag,
 403                                  const char* name)) {
 404     return profiles_->NewCodeEntry(tag, name);
 405   }
 406
 407   INLINE(CodeEntry* NewCodeEntry(Logger::LogEventsAndTags tag,
 408                                  const char* name_prefix,
 409                                  String* name)) {
 410     return profiles_->NewCodeEntry(tag, name_prefix, name);
 411   }
 412
 413   INLINE(CodeEntry* NewCodeEntry(Logger::LogEventsAndTags tag,
 414                                  int args_count)) {
 415     return profiles_->NewCodeEntry(tag, args_count);
 416   }
 417
 418   INLINE(CodeEntry* NewCodeEntry(int security_token_id)) {
 419     return profiles_->NewCodeEntry(security_token_id);
 420   }
 421
 422   void RecordTickSample(const TickSample& sample);
 423
 424   INLINE(CodeMap* code_map()) { return &code_map_; }
 425
 426   INLINE(void Tick()) { sample_rate_calc_.Tick(); }
 427   INLINE(double actual_sampling_rate()) {
 428     return sample_rate_calc_.ticks_per_ms();
 429   }
 430
 431   static const char* const kAnonymousFunctionName;
 432   static const char* const kProgramEntryName;
 433   static const char* const kGarbageCollectorEntryName;
 434
 435  private:
 436   INLINE(CodeEntry* EntryForVMState(StateTag tag));
 437
 438   CpuProfilesCollection* profiles_;
 439   CodeMap code_map_;
 440   CodeEntry* program_entry_;
 441   CodeEntry* gc_entry_;
 442   SampleRateCalculator sample_rate_calc_;
 443
 444   DISALLOW_COPY_AND_ASSIGN(ProfileGenerator);
 445 };
 446
 447
 448 class HeapEntry;
 449 class HeapSnapshot;
 450
 451 class HeapGraphEdge BASE_EMBEDDED {
 452  public:
 453   enum Type {
 454     kContextVariable = v8::HeapGraphEdge::kContextVariable,
 455     kElement = v8::HeapGraphEdge::kElement,
 456     kProperty = v8::HeapGraphEdge::kProperty,
 457     kInternal = v8::HeapGraphEdge::kInternal,
 458     kHidden = v8::HeapGraphEdge::kHidden,
 459     kShortcut = v8::HeapGraphEdge::kShortcut,
 460     kWeak = v8::HeapGraphEdge::kWeak
 461   };
 462
 463   HeapGraphEdge() { }
 464   HeapGraphEdge(Type type, const char* name, int from, int to);
 465   HeapGraphEdge(Type type, int index, int from, int to);
 466   void ReplaceToIndexWithEntry(HeapSnapshot* snapshot);
 467
 468   Type type() const { return static_cast<Type>(type_); }
 469   int index() const {
 470     ASSERT(type_ == kElement || type_ == kHidden || type_ == kWeak);
 471     return index_;
 472   }
 473   const char* name() const {
 474     ASSERT(type_ == kContextVariable
 475         || type_ == kProperty
 476         || type_ == kInternal
 477         || type_ == kShortcut);
 478     return name_;
 479   }
 480   INLINE(HeapEntry* from() const);
 481   HeapEntry* to() const { return to_entry_; }
 482
 483  private:
 484   INLINE(HeapSnapshot* snapshot() const);
 485
 486   unsigned type_ : 3;
 487   int from_index_ : 29;
 488   union {
 489     // During entries population |to_index_| is used for storing the index,
 490     // afterwards it is replaced with a pointer to the entry.
 491     int to_index_;
 492     HeapEntry* to_entry_;
 493   };
 494   union {
 495     int index_;
 496     const char* name_;
 497   };
 498 };
 499
 500
 501 // HeapEntry instances represent an entity from the heap (or a special
 502 // virtual node, e.g. root).
 503 class HeapEntry BASE_EMBEDDED {
 504  public:
 505   enum Type {
 506     kHidden = v8::HeapGraphNode::kHidden,
 507     kArray = v8::HeapGraphNode::kArray,
 508     kString = v8::HeapGraphNode::kString,
 509     kObject = v8::HeapGraphNode::kObject,
 510     kCode = v8::HeapGraphNode::kCode,
 511     kClosure = v8::HeapGraphNode::kClosure,
 512     kRegExp = v8::HeapGraphNode::kRegExp,
 513     kHeapNumber = v8::HeapGraphNode::kHeapNumber,
 514     kNative = v8::HeapGraphNode::kNative,
 515     kSynthetic = v8::HeapGraphNode::kSynthetic
 516   };
 517   static const int kNoEntry;
 518
 519   HeapEntry() { }
 520   HeapEntry(HeapSnapshot* snapshot,
 521             Type type,
 522             const char* name,
 523             SnapshotObjectId id,
 524             int self_size);
 525
 526   HeapSnapshot* snapshot() { return snapshot_; }
 527   Type type() { return static_cast<Type>(type_); }
 528   const char* name() { return name_; }
 529   void set_name(const char* name) { name_ = name; }
 530   inline SnapshotObjectId id() { return id_; }
 531   int self_size() { return self_size_; }
 532   int retained_size() { return retained_size_; }
 533   void add_retained_size(int size) { retained_size_ += size; }
 534   void set_retained_size(int size) { retained_size_ = size; }
 535   INLINE(int index() const);
 536   int postorder_index() { return postorder_index_; }
 537   void set_postorder_index(int value) { postorder_index_ = value; }
 538   int children_count() const { return children_count_; }
 539   INLINE(int set_children_index(int index));
 540   INLINE(int set_retainers_index(int index));
 541   void add_child(HeapGraphEdge* edge) {
 542     children_arr()[children_count_++] = edge;
 543   }
 544   void add_retainer(HeapGraphEdge* edge) {
 545     retainers_arr()[retainers_count_++] = edge;
 546   }
 547   Vector<HeapGraphEdge*> children() {
 548     return Vector<HeapGraphEdge*>(children_arr(), children_count_); }
 549   Vector<HeapGraphEdge*> retainers() {
 550     return Vector<HeapGraphEdge*>(retainers_arr(), retainers_count_); }
 551   INLINE(HeapEntry* dominator() const);
 552   void set_dominator(HeapEntry* entry) {
 553     ASSERT(entry != NULL);
 554     dominator_ = entry->index();
 555   }
 556   void clear_paint() { painted_ = false; }
 557   bool painted() { return painted_; }
 558   void paint() { painted_ = true; }
 559   bool user_reachable() { return user_reachable_; }
 560   void set_user_reachable() { user_reachable_ = true; }
 561
 562   void SetIndexedReference(
 563       HeapGraphEdge::Type type, int index, HeapEntry* entry);
 564   void SetNamedReference(
 565       HeapGraphEdge::Type type, const char* name, HeapEntry* entry);
 566
 567   void Print(
 568       const char* prefix, const char* edge_name, int max_depth, int indent);
 569
 570   Handle<HeapObject> GetHeapObject();
 571
 572  private:
 573   INLINE(HeapGraphEdge** children_arr());
 574   INLINE(HeapGraphEdge** retainers_arr());
 575   const char* TypeAsString();
 576
 577   unsigned painted_: 1;
 578   unsigned user_reachable_: 1;
 579   int dominator_: 30;
 580   unsigned type_: 4;
 581   int retainers_count_: 28;
 582   int retainers_index_;
 583   int children_count_;
 584   int children_index_;
 585   int self_size_;
 586   union {
 587     int postorder_index_;  // Used during dominator tree building.
 588     int retained_size_;    // At that moment, there is no retained size yet.
 589   };
 590   SnapshotObjectId id_;
 591   HeapSnapshot* snapshot_;
 592   const char* name_;
 593 };
 594
 595
 596 class HeapSnapshotsCollection;
 597
 598 // HeapSnapshot represents a single heap snapshot. It is stored in
 599 // HeapSnapshotsCollection, which is also a factory for
 600 // HeapSnapshots. All HeapSnapshots share strings copied from JS heap
 601 // to be able to return them even if they were collected.
 602 // HeapSnapshotGenerator fills in a HeapSnapshot.
 603 class HeapSnapshot {
 604  public:
 605   enum Type {
 606     kFull = v8::HeapSnapshot::kFull
 607   };
 608
 609   HeapSnapshot(HeapSnapshotsCollection* collection,
 610                Type type,
 611                const char* title,
 612                unsigned uid);
 613   void Delete();
 614
 615   HeapSnapshotsCollection* collection() { return collection_; }
 616   Type type() { return type_; }
 617   const char* title() { return title_; }
 618   unsigned uid() { return uid_; }
 619   size_t RawSnapshotSize() const;
 620   HeapEntry* root() { return &entries_[root_index_]; }
 621   HeapEntry* gc_roots() { return &entries_[gc_roots_index_]; }
 622   HeapEntry* natives_root() { return &entries_[natives_root_index_]; }
 623   HeapEntry* gc_subroot(int index) {
 624     return &entries_[gc_subroot_indexes_[index]];
 625   }
 626   List<HeapEntry>& entries() { return entries_; }
 627   List<HeapGraphEdge>& edges() { return edges_; }
 628   List<HeapGraphEdge*>& children() { return children_; }
 629   List<HeapGraphEdge*>& retainers() { return retainers_; }
 630   void RememberLastJSObjectId();
 631   SnapshotObjectId max_snapshot_js_object_id() const {
 632     return max_snapshot_js_object_id_;
 633   }
 634
 635   HeapEntry* AddEntry(HeapEntry::Type type,
 636                       const char* name,
 637                       SnapshotObjectId id,
 638                       int size);
 639   HeapEntry* AddRootEntry();
 640   HeapEntry* AddGcRootsEntry();
 641   HeapEntry* AddGcSubrootEntry(int tag);
 642   HeapEntry* AddNativesRootEntry();
 643   void ClearPaint();
 644   HeapEntry* GetEntryById(SnapshotObjectId id);
 645   List<HeapEntry*>* GetSortedEntriesList();
 646   void SetDominatorsToSelf();
 647   void FillChildrenAndRetainers();
 648
 649   void Print(int max_depth);
 650   void PrintEntriesSize();
 651
 652  private:
 653   HeapSnapshotsCollection* collection_;
 654   Type type_;
 655   const char* title_;
 656   unsigned uid_;
 657   int root_index_;
 658   int gc_roots_index_;
 659   int natives_root_index_;
 660   int gc_subroot_indexes_[VisitorSynchronization::kNumberOfSyncTags];
 661   List<HeapEntry> entries_;
 662   List<HeapGraphEdge> edges_;
 663   List<HeapGraphEdge*> children_;
 664   List<HeapGraphEdge*> retainers_;
 665   List<HeapEntry*> sorted_entries_;
 666   SnapshotObjectId max_snapshot_js_object_id_;
 667
 668   friend class HeapSnapshotTester;
 669
 670   DISALLOW_COPY_AND_ASSIGN(HeapSnapshot);
 671 };
 672
 673
 674 class HeapObjectsMap {
 675  public:
 676   HeapObjectsMap();
 677
 678   void SnapshotGenerationFinished();
 679   SnapshotObjectId FindEntry(Address addr);
 680   SnapshotObjectId FindOrAddEntry(Address addr, unsigned int size);
 681   void MoveObject(Address from, Address to);
 682   SnapshotObjectId last_assigned_id() const {
 683     return next_id_ - kObjectIdStep;
 684   }
 685
 686   void StopHeapObjectsTracking();
 687   void PushHeapObjectsStats(OutputStream* stream);
 688
 689   static SnapshotObjectId GenerateId(v8::RetainedObjectInfo* info);
 690   static inline SnapshotObjectId GetNthGcSubrootId(int delta);
 691
 692   static const int kObjectIdStep = 2;
 693   static const SnapshotObjectId kInternalRootObjectId;
 694   static const SnapshotObjectId kGcRootsObjectId;
 695   static const SnapshotObjectId kNativesRootObjectId;
 696   static const SnapshotObjectId kGcRootsFirstSubrootId;
 697   static const SnapshotObjectId kFirstAvailableObjectId;
 698
 699  private:
 700   struct EntryInfo {
 701   EntryInfo(SnapshotObjectId id, Address addr, unsigned int size)
 702       : id(id), addr(addr), size(size), accessed(true) { }
 703   EntryInfo(SnapshotObjectId id, Address addr, unsigned int size, bool accessed)
 704       : id(id), addr(addr), size(size), accessed(accessed) { }
 705     SnapshotObjectId id;
 706     Address addr;
 707     unsigned int size;
 708     bool accessed;
 709   };
 710   struct TimeInterval {
 711     explicit TimeInterval(SnapshotObjectId id) : id(id), size(0), count(0) { }
 712     SnapshotObjectId id;
 713     uint32_t size;
 714     uint32_t count;
 715   };
 716
 717   void UpdateHeapObjectsMap();
 718   void RemoveDeadEntries();
 719
 720   static bool AddressesMatch(void* key1, void* key2) {
 721     return key1 == key2;
 722   }
 723
 724   static uint32_t AddressHash(Address addr) {
 725     return ComputeIntegerHash(
 726         static_cast<uint32_t>(reinterpret_cast<uintptr_t>(addr)),
 727         v8::internal::kZeroHashSeed);
 728   }
 729
 730   SnapshotObjectId next_id_;
 731   HashMap entries_map_;
 732   List<EntryInfo> entries_;
 733   List<TimeInterval> time_intervals_;
 734
 735   DISALLOW_COPY_AND_ASSIGN(HeapObjectsMap);
 736 };
 737
 738
 739 class HeapSnapshotsCollection {
 740  public:
 741   HeapSnapshotsCollection();
 742   ~HeapSnapshotsCollection();
 743
 744   bool is_tracking_objects() { return is_tracking_objects_; }
 745   void PushHeapObjectsStats(OutputStream* stream) {
 746     return ids_.PushHeapObjectsStats(stream);
 747   }
 748   void StartHeapObjectsTracking() { is_tracking_objects_ = true; }
 749   void StopHeapObjectsTracking() { ids_.StopHeapObjectsTracking(); }
 750
 751   HeapSnapshot* NewSnapshot(
 752       HeapSnapshot::Type type, const char* name, unsigned uid);
 753   void SnapshotGenerationFinished(HeapSnapshot* snapshot);
 754   List<HeapSnapshot*>* snapshots() { return &snapshots_; }
 755   HeapSnapshot* GetSnapshot(unsigned uid);
 756   void RemoveSnapshot(HeapSnapshot* snapshot);
 757
 758   StringsStorage* names() { return &names_; }
 759   TokenEnumerator* token_enumerator() { return token_enumerator_; }
 760
 761   SnapshotObjectId FindObjectId(Address object_addr) {
 762     return ids_.FindEntry(object_addr);
 763   }
 764   SnapshotObjectId GetObjectId(Address object_addr, int object_size) {
 765     return ids_.FindOrAddEntry(object_addr, object_size);
 766   }
 767   Handle<HeapObject> FindHeapObjectById(SnapshotObjectId id);
 768   void ObjectMoveEvent(Address from, Address to) { ids_.MoveObject(from, to); }
 769   SnapshotObjectId last_assigned_id() const {
 770     return ids_.last_assigned_id();
 771   }
 772
 773  private:
 774   INLINE(static bool HeapSnapshotsMatch(void* key1, void* key2)) {
 775     return key1 == key2;
 776   }
 777
 778   bool is_tracking_objects_;  // Whether tracking object moves is needed.
 779   List<HeapSnapshot*> snapshots_;
 780   // Mapping from snapshots' uids to HeapSnapshot* pointers.
 781   HashMap snapshots_uids_;
 782   StringsStorage names_;
 783   TokenEnumerator* token_enumerator_;
 784   // Mapping from HeapObject addresses to objects' uids.
 785   HeapObjectsMap ids_;
 786
 787   DISALLOW_COPY_AND_ASSIGN(HeapSnapshotsCollection);
 788 };
 789
 790
 791 // A typedef for referencing anything that can be snapshotted living
 792 // in any kind of heap memory.
 793 typedef void* HeapThing;
 794
 795
 796 // An interface that creates HeapEntries by HeapThings.
 797 class HeapEntriesAllocator {
 798  public:
 799   virtual ~HeapEntriesAllocator() { }
 800   virtual HeapEntry* AllocateEntry(HeapThing ptr) = 0;
 801 };
 802
 803
 804 // The HeapEntriesMap instance is used to track a mapping between
 805 // real heap objects and their representations in heap snapshots.
 806 class HeapEntriesMap {
 807  public:
 808   HeapEntriesMap();
 809
 810   int Map(HeapThing thing);
 811   void Pair(HeapThing thing, int entry);
 812
 813  private:
 814   static uint32_t Hash(HeapThing thing) {
 815     return ComputeIntegerHash(
 816         static_cast<uint32_t>(reinterpret_cast<uintptr_t>(thing)),
 817         v8::internal::kZeroHashSeed);
 818   }
 819   static bool HeapThingsMatch(HeapThing key1, HeapThing key2) {
 820     return key1 == key2;
 821   }
 822
 823   HashMap entries_;
 824
 825   friend class HeapObjectsSet;
 826
 827   DISALLOW_COPY_AND_ASSIGN(HeapEntriesMap);
 828 };
 829
 830
 831 class HeapObjectsSet {
 832  public:
 833   HeapObjectsSet();
 834   void Clear();
 835   bool Contains(Object* object);
 836   void Insert(Object* obj);
 837   const char* GetTag(Object* obj);
 838   void SetTag(Object* obj, const char* tag);
 839   bool is_empty() const { return entries_.occupancy() == 0; }
 840
 841  private:
 842   HashMap entries_;
 843
 844   DISALLOW_COPY_AND_ASSIGN(HeapObjectsSet);
 845 };
 846
 847
 848 // An interface used to populate a snapshot with nodes and edges.
 849 class SnapshotFillerInterface {
 850  public:
 851   virtual ~SnapshotFillerInterface() { }
 852   virtual HeapEntry* AddEntry(HeapThing ptr,
 853                               HeapEntriesAllocator* allocator) = 0;
 854   virtual HeapEntry* FindEntry(HeapThing ptr) = 0;
 855   virtual HeapEntry* FindOrAddEntry(HeapThing ptr,
 856                                     HeapEntriesAllocator* allocator) = 0;
 857   virtual void SetIndexedReference(HeapGraphEdge::Type type,
 858                                    int parent_entry,
 859                                    int index,
 860                                    HeapEntry* child_entry) = 0;
 861   virtual void SetIndexedAutoIndexReference(HeapGraphEdge::Type type,
 862                                             int parent_entry,
 863                                             HeapEntry* child_entry) = 0;
 864   virtual void SetNamedReference(HeapGraphEdge::Type type,
 865                                  int parent_entry,
 866                                  const char* reference_name,
 867                                  HeapEntry* child_entry) = 0;
 868   virtual void SetNamedAutoIndexReference(HeapGraphEdge::Type type,
 869                                           int parent_entry,
 870                                           HeapEntry* child_entry) = 0;
 871 };
 872
 873
 874 class SnapshottingProgressReportingInterface {
 875  public:
 876   virtual ~SnapshottingProgressReportingInterface() { }
 877   virtual void ProgressStep() = 0;
 878   virtual bool ProgressReport(bool force) = 0;
 879 };
 880
 881
 882 // An implementation of V8 heap graph extractor.
 883 class V8HeapExplorer : public HeapEntriesAllocator {
 884  public:
 885   V8HeapExplorer(HeapSnapshot* snapshot,
 886                  SnapshottingProgressReportingInterface* progress);
 887   virtual ~V8HeapExplorer();
 888   virtual HeapEntry* AllocateEntry(HeapThing ptr);
 889   void AddRootEntries(SnapshotFillerInterface* filler);
 890   int EstimateObjectsCount(HeapIterator* iterator);
 891   bool IterateAndExtractReferences(SnapshotFillerInterface* filler);
 892   void TagGlobalObjects();
 893
 894   static String* GetConstructorName(JSObject* object);
 895
 896   static HeapObject* const kInternalRootObject;
 897
 898  private:
 899   HeapEntry* AddEntry(HeapObject* object);
 900   HeapEntry* AddEntry(HeapObject* object,
 901                       HeapEntry::Type type,
 902                       const char* name);
 903   const char* GetSystemEntryName(HeapObject* object);
 904
 905   void ExtractReferences(HeapObject* obj);
 906   void ExtractJSGlobalProxyReferences(JSGlobalProxy* proxy);
 907   void ExtractJSObjectReferences(int entry, JSObject* js_obj);
 908   void ExtractStringReferences(int entry, String* obj);
 909   void ExtractContextReferences(int entry, Context* context);
 910   void ExtractMapReferences(int entry, Map* map);
 911   void ExtractSharedFunctionInfoReferences(int entry,
 912                                            SharedFunctionInfo* shared);
 913   void ExtractScriptReferences(int entry, Script* script);
 914   void ExtractCodeCacheReferences(int entry, CodeCache* code_cache);
 915   void ExtractCodeReferences(int entry, Code* code);
 916   void ExtractJSGlobalPropertyCellReferences(int entry,
 917                                              JSGlobalPropertyCell* cell);
 918   void ExtractClosureReferences(JSObject* js_obj, int entry);
 919   void ExtractPropertyReferences(JSObject* js_obj, int entry);
 920   void ExtractElementReferences(JSObject* js_obj, int entry);
 921   void ExtractInternalReferences(JSObject* js_obj, int entry);
 922   bool IsEssentialObject(Object* object);
 923   void SetClosureReference(HeapObject* parent_obj,
 924                            int parent,
 925                            String* reference_name,
 926                            Object* child);
 927   void SetNativeBindReference(HeapObject* parent_obj,
 928                               int parent,
 929                               const char* reference_name,
 930                               Object* child);
 931   void SetElementReference(HeapObject* parent_obj,
 932                            int parent,
 933                            int index,
 934                            Object* child);
 935   void SetInternalReference(HeapObject* parent_obj,
 936                             int parent,
 937                             const char* reference_name,
 938                             Object* child,
 939                             int field_offset = -1);
 940   void SetInternalReference(HeapObject* parent_obj,
 941                             int parent,
 942                             int index,
 943                             Object* child,
 944                             int field_offset = -1);
 945   void SetHiddenReference(HeapObject* parent_obj,
 946                           int parent,
 947                           int index,
 948                           Object* child);
 949   void SetWeakReference(HeapObject* parent_obj,
 950                         int parent,
 951                         int index,
 952                         Object* child_obj,
 953                         int field_offset);
 954   void SetPropertyReference(HeapObject* parent_obj,
 955                             int parent,
 956                             String* reference_name,
 957                             Object* child,
 958                             const char* name_format_string = NULL,
 959                             int field_offset = -1);
 960   void SetPropertyShortcutReference(HeapObject* parent_obj,
 961                                     int parent,
 962                                     String* reference_name,
 963                                     Object* child);
 964   void SetUserGlobalReference(Object* user_global);
 965   void SetRootGcRootsReference();
 966   void SetGcRootsReference(VisitorSynchronization::SyncTag tag);
 967   void SetGcSubrootReference(
 968       VisitorSynchronization::SyncTag tag, bool is_weak, Object* child);
 969   const char* GetStrongGcSubrootName(Object* object);
 970   void TagObject(Object* obj, const char* tag);
 971
 972   HeapEntry* GetEntry(Object* obj);
 973
 974   static inline HeapObject* GetNthGcSubrootObject(int delta);
 975   static inline int GetGcSubrootOrder(HeapObject* subroot);
 976
 977   Heap* heap_;
 978   HeapSnapshot* snapshot_;
 979   HeapSnapshotsCollection* collection_;
 980   SnapshottingProgressReportingInterface* progress_;
 981   SnapshotFillerInterface* filler_;
 982   HeapObjectsSet objects_tags_;
 983   HeapObjectsSet strong_gc_subroot_names_;
 984
 985   static HeapObject* const kGcRootsObject;
 986   static HeapObject* const kFirstGcSubrootObject;
 987   static HeapObject* const kLastGcSubrootObject;
 988
 989   friend class IndexedReferencesExtractor;
 990   friend class GcSubrootsEnumerator;
 991   friend class RootsReferencesExtractor;
 992
 993   DISALLOW_COPY_AND_ASSIGN(V8HeapExplorer);
 994 };
 995
 996
 997 class NativeGroupRetainedObjectInfo;
 998
 999
1000 // An implementation of retained native objects extractor.
1001 class NativeObjectsExplorer {
1002  public:
1003   NativeObjectsExplorer(HeapSnapshot* snapshot,
1004                       SnapshottingProgressReportingInterface* progress);
1005   virtual ~NativeObjectsExplorer();
1006   void AddRootEntries(SnapshotFillerInterface* filler);
1007   int EstimateObjectsCount();
1008   bool IterateAndExtractReferences(SnapshotFillerInterface* filler);
1009
1010  private:
1011   void FillRetainedObjects();
1012   void FillImplicitReferences();
1013   List<HeapObject*>* GetListMaybeDisposeInfo(v8::RetainedObjectInfo* info);
1014   void SetNativeRootReference(v8::RetainedObjectInfo* info);
1015   void SetRootNativeRootsReference();
1016   void SetWrapperNativeReferences(HeapObject* wrapper,
1017                                       v8::RetainedObjectInfo* info);
1018   void VisitSubtreeWrapper(Object** p, uint16_t class_id);
1019
1020   static uint32_t InfoHash(v8::RetainedObjectInfo* info) {
1021     return ComputeIntegerHash(static_cast<uint32_t>(info->GetHash()),
1022                               v8::internal::kZeroHashSeed);
1023   }
1024   static bool RetainedInfosMatch(void* key1, void* key2) {
1025     return key1 == key2 ||
1026         (reinterpret_cast<v8::RetainedObjectInfo*>(key1))->IsEquivalent(
1027             reinterpret_cast<v8::RetainedObjectInfo*>(key2));
1028   }
1029   INLINE(static bool StringsMatch(void* key1, void* key2)) {
1030     return strcmp(reinterpret_cast<char*>(key1),
1031                   reinterpret_cast<char*>(key2)) == 0;
1032   }
1033
1034   NativeGroupRetainedObjectInfo* FindOrAddGroupInfo(const char* label);
1035
1036   HeapSnapshot* snapshot_;
1037   HeapSnapshotsCollection* collection_;
1038   SnapshottingProgressReportingInterface* progress_;
1039   bool embedder_queried_;
1040   HeapObjectsSet in_groups_;
1041   // RetainedObjectInfo* -> List<HeapObject*>*
1042   HashMap objects_by_info_;
1043   HashMap native_groups_;
1044   HeapEntriesAllocator* synthetic_entries_allocator_;
1045   HeapEntriesAllocator* native_entries_allocator_;
1046   // Used during references extraction.
1047   SnapshotFillerInterface* filler_;
1048
1049   static HeapThing const kNativesRootObject;
1050
1051   friend class GlobalHandlesExtractor;
1052
1053   DISALLOW_COPY_AND_ASSIGN(NativeObjectsExplorer);
1054 };
1055
1056
1057 class HeapSnapshotGenerator : public SnapshottingProgressReportingInterface {
1058  public:
1059   HeapSnapshotGenerator(HeapSnapshot* snapshot,
1060                         v8::ActivityControl* control);
1061   bool GenerateSnapshot();
1062
1063  private:
1064   bool BuildDominatorTree(const Vector<HeapEntry*>& entries,
1065                           Vector<int>* dominators);
1066   bool CalculateRetainedSizes();
1067   bool FillReferences();
1068   void FillPostorderIndexes(Vector<HeapEntry*>* entries);
1069   bool IsUserGlobalReference(const HeapGraphEdge* edge);
1070   void MarkUserReachableObjects();
1071   void ProgressStep();
1072   bool ProgressReport(bool force = false);
1073   bool SetEntriesDominators();
1074   void SetProgressTotal(int iterations_count);
1075
1076   HeapSnapshot* snapshot_;
1077   v8::ActivityControl* control_;
1078   V8HeapExplorer v8_heap_explorer_;
1079   NativeObjectsExplorer dom_explorer_;
1080   // Mapping from HeapThing pointers to HeapEntry* pointers.
1081   HeapEntriesMap entries_;
1082   // Used during snapshot generation.
1083   int progress_counter_;
1084   int progress_total_;
1085
1086   DISALLOW_COPY_AND_ASSIGN(HeapSnapshotGenerator);
1087 };
1088
1089 class OutputStreamWriter;
1090
1091 class HeapSnapshotJSONSerializer {
1092  public:
1093   explicit HeapSnapshotJSONSerializer(HeapSnapshot* snapshot)
1094       : snapshot_(snapshot),
1095         strings_(ObjectsMatch),
1096         next_node_id_(1),
1097         next_string_id_(1),
1098         writer_(NULL) {
1099   }
1100   void Serialize(v8::OutputStream* stream);
1101
1102  private:
1103   INLINE(static bool ObjectsMatch(void* key1, void* key2)) {
1104     return key1 == key2;
1105   }
1106
1107   INLINE(static uint32_t ObjectHash(const void* key)) {
1108     return ComputeIntegerHash(
1109         static_cast<uint32_t>(reinterpret_cast<uintptr_t>(key)),
1110         v8::internal::kZeroHashSeed);
1111   }
1112
1113   HeapSnapshot* CreateFakeSnapshot();
1114   int GetStringId(const char* s);
1115   int entry_index(HeapEntry* e) { return e->index() * kNodeFieldsCount; }
1116   void SerializeEdge(HeapGraphEdge* edge, bool first_edge);
1117   void SerializeEdges(const List<HeapEntry>& nodes);
1118   void SerializeImpl();
1119   void SerializeNode(HeapEntry* entry, int edges_index);
1120   void SerializeNodes(const List<HeapEntry>& nodes);
1121   void SerializeSnapshot();
1122   void SerializeString(const unsigned char* s);
1123   void SerializeStrings();
1124   void SortHashMap(HashMap* map, List<HashMap::Entry*>* sorted_entries);
1125
1126   static const int kEdgeFieldsCount;
1127   static const int kNodeFieldsCount;
1128
1129   HeapSnapshot* snapshot_;
1130   HashMap strings_;
1131   int next_node_id_;
1132   int next_string_id_;
1133   OutputStreamWriter* writer_;
1134
1135   friend class HeapSnapshotJSONSerializerEnumerator;
1136   friend class HeapSnapshotJSONSerializerIterator;
1137
1138   DISALLOW_COPY_AND_ASSIGN(HeapSnapshotJSONSerializer);
1139 };
1140
1141 } }  // namespace v8::internal
1142
1143 #endif  // V8_PROFILE_GENERATOR_H_