Merge bleeding_edge revisions 2971, 2972 (heap profiler updates) to trunk....

src/heap-profiler.cc

 // Copyright 2009 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 144 matching lines @@
                       const StringStream& retainers) {
     HeapStringAllocator allocator;
     StringStream stream(&allocator);
     cluster.Print(&stream);
     LOG(HeapSampleJSRetainersEvent(
         *(stream.ToCString()), *(retainers.ToCString())));
   }
 };
 
 
-class RetainerTreePrinter BASE_EMBEDDED {
+// Visitor for printing a cluster tree.
+class ClusterTreePrinter BASE_EMBEDDED {
  public:
-  explicit RetainerTreePrinter(StringStream* stream) : stream_(stream) {}
+  explicit ClusterTreePrinter(StringStream* stream) : stream_(stream) {}
   void Call(const JSObjectsCluster& cluster,
             const NumberAndSizeInfo& number_and_size) {
     Print(stream_, cluster, number_and_size);
   }
   static void Print(StringStream* stream,
                     const JSObjectsCluster& cluster,
-                    const NumberAndSizeInfo& numNNber_and_size);
+                    const NumberAndSizeInfo& number_and_size);
 
  private:
   StringStream* stream_;
 };
 
 
-void RetainerTreePrinter::Print(StringStream* stream,
-                                const JSObjectsCluster& cluster,
-                                const NumberAndSizeInfo& number_and_size) {
+void ClusterTreePrinter::Print(StringStream* stream,
+                               const JSObjectsCluster& cluster,
+                               const NumberAndSizeInfo& number_and_size) {
   stream->Put(',');
   cluster.Print(stream);
   stream->Add(";%d", number_and_size.number());
 }
 
 
+// Visitor for printing a retainer tree.
+class SimpleRetainerTreePrinter BASE_EMBEDDED {
+ public:
+  explicit SimpleRetainerTreePrinter(RetainerHeapProfile::Printer* printer)
+      : printer_(printer) {}
+  void Call(const JSObjectsCluster& cluster, JSObjectsClusterTree* tree);
+
+ private:
+  RetainerHeapProfile::Printer* printer_;
+};
+
+
+void SimpleRetainerTreePrinter::Call(const JSObjectsCluster& cluster,
+                                     JSObjectsClusterTree* tree) {
+  HeapStringAllocator allocator;
+  StringStream stream(&allocator);
+  ClusterTreePrinter retainers_printer(&stream);
+  tree->ForEach(&retainers_printer);
+  printer_->PrintRetainers(cluster, stream);
+}
+
+
+// Visitor for aggregating references count of equivalent clusters.
+class RetainersAggregator BASE_EMBEDDED {
+ public:
+  RetainersAggregator(ClustersCoarser* coarser, JSObjectsClusterTree* dest_tree)
+      : coarser_(coarser), dest_tree_(dest_tree) {}
+  void Call(const JSObjectsCluster& cluster,
+            const NumberAndSizeInfo& number_and_size);
+
+ private:
+  ClustersCoarser* coarser_;
+  JSObjectsClusterTree* dest_tree_;
+};
+
+
+void RetainersAggregator::Call(const JSObjectsCluster& cluster,
+                               const NumberAndSizeInfo& number_and_size) {
+  JSObjectsCluster eq = coarser_->GetCoarseEquivalent(cluster);
+  if (eq.is_null()) eq = cluster;
+  JSObjectsClusterTree::Locator loc;
+  dest_tree_->Insert(eq, &loc);
+  NumberAndSizeInfo aggregated_number = loc.value();
+  aggregated_number.increment_number(number_and_size.number());
+  loc.set_value(aggregated_number);
+}
+
+
+// Visitor for printing retainers tree. Aggregates equivalent retainer clusters.
+class AggregatingRetainerTreePrinter BASE_EMBEDDED {
+ public:
+  AggregatingRetainerTreePrinter(ClustersCoarser* coarser,
+                                 RetainerHeapProfile::Printer* printer)
+      : coarser_(coarser), printer_(printer) {}
+  void Call(const JSObjectsCluster& cluster, JSObjectsClusterTree* tree);
+
+ private:
+  ClustersCoarser* coarser_;
+  RetainerHeapProfile::Printer* printer_;
+};
+
+
+void AggregatingRetainerTreePrinter::Call(const JSObjectsCluster& cluster,
+                                          JSObjectsClusterTree* tree) {
+  if (!coarser_->GetCoarseEquivalent(cluster).is_null()) return;
+  JSObjectsClusterTree dest_tree_;
+  RetainersAggregator retainers_aggregator(coarser_, &dest_tree_);
+  tree->ForEach(&retainers_aggregator);
+  HeapStringAllocator allocator;
+  StringStream stream(&allocator);
+  ClusterTreePrinter retainers_printer(&stream);
+  dest_tree_.ForEach(&retainers_printer);
+  printer_->PrintRetainers(cluster, stream);
+}
+
+
+// A helper class for building a retainers tree, that aggregates
+// all equivalent clusters.
+class RetainerTreeAggregator BASE_EMBEDDED {
+ public:
+  explicit RetainerTreeAggregator(ClustersCoarser* coarser)
+      : coarser_(coarser) {}
+  void Process(JSObjectsRetainerTree* input_tree) {
+    input_tree->ForEach(this);
+  }
+  void Call(const JSObjectsCluster& cluster, JSObjectsClusterTree* tree);
+  JSObjectsRetainerTree& output_tree() { return output_tree_; }
+
+ private:
+  ClustersCoarser* coarser_;
+  JSObjectsRetainerTree output_tree_;
+};
+
+
+void RetainerTreeAggregator::Call(const JSObjectsCluster& cluster,
+                                  JSObjectsClusterTree* tree) {
+  JSObjectsCluster eq = coarser_->GetCoarseEquivalent(cluster);
+  if (eq.is_null()) return;
+  JSObjectsRetainerTree::Locator loc;
+  if (output_tree_.Insert(eq, &loc)) {
+    loc.set_value(new JSObjectsClusterTree());
+  }
+  RetainersAggregator retainers_aggregator(coarser_, loc.value());
+  tree->ForEach(&retainers_aggregator);
+}
+
 }  // namespace
 
 
 const JSObjectsClusterTreeConfig::Key JSObjectsClusterTreeConfig::kNoKey;
 const JSObjectsClusterTreeConfig::Value JSObjectsClusterTreeConfig::kNoValue;
 
 
 ConstructorHeapProfile::ConstructorHeapProfile()
     : zscope_(DELETE_ON_EXIT) {
 }
@@ skipping 19 matching lines @@
   js_objects_info_tree_.ForEach(this);
 }
 
 
 void JSObjectsCluster::Print(StringStream* accumulator) const {
   ASSERT(!is_null());
   if (constructor_ == FromSpecialCase(ROOTS)) {
     accumulator->Add("(roots)");
   } else if (constructor_ == FromSpecialCase(GLOBAL_PROPERTY)) {
     accumulator->Add("(global property)");
+  } else if (constructor_ == FromSpecialCase(SELF)) {
+    accumulator->Add("(self)");
   } else {
     SmartPointer<char> s_name(
         constructor_->ToCString(DISALLOW_NULLS, ROBUST_STRING_TRAVERSAL));
     accumulator->Add("%s", (*s_name)[0] != '\0' ? *s_name : "(anonymous)");
     if (instance_ != NULL) {
       accumulator->Add(":%p", static_cast<void*>(instance_));
     }
   }
 }
 
@@ skipping 40 matching lines @@
   if (a.refs.length() > b.refs.length()) return 1;
   for (int i = 0; i < a.refs.length(); ++i) {
     int cmp = JSObjectsCluster::Compare(a.refs[i], b.refs[i]);
     if (cmp != 0) return cmp;
   }
   return 0;
 }
 
 
 ClustersCoarser::ClustersCoarser()
-  : zscope_(DELETE_ON_EXIT),
-    sim_list_(ClustersCoarser::kInitialSimilarityListCapacity),
-    current_pair_(NULL) {
+    : zscope_(DELETE_ON_EXIT),
+      sim_list_(ClustersCoarser::kInitialSimilarityListCapacity),
+      current_pair_(NULL),
+      current_set_(NULL),
+      self_(NULL) {
 }
 
 
 void ClustersCoarser::Call(const JSObjectsCluster& cluster,
                            JSObjectsClusterTree* tree) {
   if (!cluster.can_be_coarsed()) return;
   ClusterBackRefs pair(cluster);
   ASSERT(current_pair_ == NULL);
   current_pair_ = &pair;
   current_set_ = new JSObjectsRetainerTree();
+  self_ = &cluster;
   tree->ForEach(this);
   sim_list_.Add(pair);
   current_pair_ = NULL;
   current_set_ = NULL;
+  self_ = NULL;
 }
 
 
 void ClustersCoarser::Call(const JSObjectsCluster& cluster,
                            const NumberAndSizeInfo& number_and_size) {
   ASSERT(current_pair_ != NULL);
   ASSERT(current_set_ != NULL);
+  ASSERT(self_ != NULL);
+  JSObjectsRetainerTree::Locator loc;
+  if (JSObjectsCluster::Compare(*self_, cluster) == 0) {
+    current_pair_->refs.Add(JSObjectsCluster(JSObjectsCluster::SELF));
+    return;
+  }
   JSObjectsCluster eq = GetCoarseEquivalent(cluster);
-  JSObjectsRetainerTree::Locator loc;
   if (!eq.is_null()) {
     if (current_set_->Find(eq, &loc)) return;
     current_pair_->refs.Add(eq);
     current_set_->Insert(eq, &loc);
   } else {
     current_pair_->refs.Add(cluster);
   }
 }
 
 
 void ClustersCoarser::Process(JSObjectsRetainerTree* tree) {
   int last_eq_clusters = -1;
   for (int i = 0; i < kMaxPassesCount; ++i) {
     sim_list_.Clear();
     const int curr_eq_clusters = DoProcess(tree);
     // If no new cluster equivalents discovered, abort processing.
     if (last_eq_clusters == curr_eq_clusters) break;
     last_eq_clusters = curr_eq_clusters;
   }
 }
 
 
 int ClustersCoarser::DoProcess(JSObjectsRetainerTree* tree) {
   tree->ForEach(this);
-  // To sort similarity list properly, references list of a cluster is
-  // required to be sorted, thus 'O1 <- A, B' and 'O2 <- B, A' would
-  // be considered equivalent. But we don't sort them explicitly
-  // because we know that they come from a splay tree traversal, so
-  // they are already sorted.
+  sim_list_.Iterate(ClusterBackRefs::SortRefsIterator);
   sim_list_.Sort(ClusterBackRefsCmp);
   return FillEqualityTree();
 }
 
 
 JSObjectsCluster ClustersCoarser::GetCoarseEquivalent(
     const JSObjectsCluster& cluster) {
   if (!cluster.can_be_coarsed()) return JSObjectsCluster();
   EqualityTree::Locator loc;
   return eq_tree_.Find(cluster, &loc) ? loc.value() : JSObjectsCluster();
 }
 
 
 bool ClustersCoarser::HasAnEquivalent(const JSObjectsCluster& cluster) {
   // Return true for coarsible clusters that have a non-identical equivalent.
-  return cluster.can_be_coarsed() &&
-      JSObjectsCluster::Compare(cluster, GetCoarseEquivalent(cluster)) != 0;
+  if (!cluster.can_be_coarsed()) return false;
+  JSObjectsCluster eq = GetCoarseEquivalent(cluster);
+  return !eq.is_null() && JSObjectsCluster::Compare(cluster, eq) != 0;
 }
 
 
 int ClustersCoarser::FillEqualityTree() {
   int eq_clusters_count = 0;
   int eq_to = 0;
   bool first_added = false;
   for (int i = 1; i < sim_list_.length(); ++i) {
     if (ClusterBackRefs::Compare(sim_list_[i], sim_list_[eq_to]) == 0) {
       EqualityTree::Locator loc;
@@ skipping 17 matching lines @@
 
 
 const JSObjectsCluster ClustersCoarser::ClusterEqualityConfig::kNoKey;
 const JSObjectsCluster ClustersCoarser::ClusterEqualityConfig::kNoValue;
 const JSObjectsRetainerTreeConfig::Key JSObjectsRetainerTreeConfig::kNoKey;
 const JSObjectsRetainerTreeConfig::Value JSObjectsRetainerTreeConfig::kNoValue =
     NULL;
 
 
 RetainerHeapProfile::RetainerHeapProfile()
-    : zscope_(DELETE_ON_EXIT),
-      coarse_cluster_tree_(NULL),
-      current_printer_(NULL),
-      current_stream_(NULL) {
+    : zscope_(DELETE_ON_EXIT) {
   JSObjectsCluster roots(JSObjectsCluster::ROOTS);
   ReferencesExtractor extractor(roots, this);
   Heap::IterateRoots(&extractor);
 }
 
 
 void RetainerHeapProfile::StoreReference(const JSObjectsCluster& cluster,
                                          HeapObject* ref) {
   JSObjectsCluster ref_cluster = Clusterizer::Clusterize(ref);
   JSObjectsRetainerTree::Locator ref_loc;
@@ skipping 14 matching lines @@
     JSObjectsCluster global_prop(JSObjectsCluster::GLOBAL_PROPERTY);
     ReferencesExtractor extractor(global_prop, this);
     obj->Iterate(&extractor);
   }
 }
 
 
 void RetainerHeapProfile::DebugPrintStats(
     RetainerHeapProfile::Printer* printer) {
   coarser_.Process(&retainers_tree_);
-  ASSERT(current_printer_ == NULL);
-  current_printer_ = printer;
-  retainers_tree_.ForEach(this);
-  current_printer_ = NULL;
+  // Print clusters that have no equivalents, aggregating their retainers.
+  AggregatingRetainerTreePrinter agg_printer(&coarser_, printer);
+  retainers_tree_.ForEach(&agg_printer);
+  // Now aggregate clusters that have equivalents...
+  RetainerTreeAggregator aggregator(&coarser_);
+  aggregator.Process(&retainers_tree_);
+  // ...and print them.
+  SimpleRetainerTreePrinter s_printer(printer);
+  aggregator.output_tree().ForEach(&s_printer);
 }
 
 
 void RetainerHeapProfile::PrintStats() {
   RetainersPrinter printer;
   DebugPrintStats(&printer);
 }
 
 
-void RetainerHeapProfile::Call(const JSObjectsCluster& cluster,
-                               JSObjectsClusterTree* tree) {
-  // First level of retainer graph.
-  if (coarser_.HasAnEquivalent(cluster)) return;
-  ASSERT(current_stream_ == NULL);
-  HeapStringAllocator allocator;
-  StringStream stream(&allocator);
-  current_stream_ = &stream;
-  ASSERT(coarse_cluster_tree_ == NULL);
-  coarse_cluster_tree_ = new JSObjectsClusterTree();
-  tree->ForEach(this);
-  // Print aggregated counts and sizes.
-  RetainerTreePrinter printer(current_stream_);
-  coarse_cluster_tree_->ForEach(&printer);
-  coarse_cluster_tree_ = NULL;
-  current_printer_->PrintRetainers(cluster, stream);
-  current_stream_ = NULL;
-}
-
-
-void RetainerHeapProfile::Call(const JSObjectsCluster& cluster,
-                               const NumberAndSizeInfo& number_and_size) {
-  ASSERT(coarse_cluster_tree_ != NULL);
-  ASSERT(current_stream_ != NULL);
-  JSObjectsCluster eq = coarser_.GetCoarseEquivalent(cluster);
-  if (eq.is_null()) {
-    RetainerTreePrinter::Print(current_stream_, cluster, number_and_size);
-  } else {
-    // Aggregate counts and sizes for equivalent clusters.
-    JSObjectsClusterTree::Locator loc;
-    coarse_cluster_tree_->Insert(eq, &loc);
-    NumberAndSizeInfo eq_number_and_size = loc.value();
-    eq_number_and_size.increment_number(number_and_size.number());
-    loc.set_value(eq_number_and_size);
-  }
-}
-
-
 //
 // HeapProfiler class implementation.
 //
 void HeapProfiler::CollectStats(HeapObject* obj, HistogramInfo* info) {
   InstanceType type = obj->map()->instance_type();
   ASSERT(0 <= type && type <= LAST_TYPE);
   info[type].increment_number(1);
   info[type].increment_bytes(obj->Size());
 }
 
@@ skipping 41 matching lines @@
   js_retainer_profile.PrintStats();
 
   LOG(HeapSampleEndEvent("Heap", "allocated"));
 }
 
 
 #endif  // ENABLE_LOGGING_AND_PROFILING
 
 
 } }  // namespace v8::internal