Bug 1226416 - Expose a method to get a node's set of immediately dominated nodes in the dominator tree; r=bz,sfink
authorNick Fitzgerald <fitzgen@gmail.com>
Mon, 30 Nov 2015 17:38:06 -0800
changeset 308950 518be0ecf0713bb8424c74ee89aa76706e06182f
parent 308949 ef6971d9f7196b030b23a96c8e81f23cac4b8e34
child 308951 a28821163fff5d0db7a5015e0eeb891b30bb38b7
push id5513
push userraliiev@mozilla.com
push dateMon, 25 Jan 2016 13:55:34 +0000
treeherdermozilla-beta@5ee97dd05b5c [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersbz, sfink
bugs1226416
milestone45.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 1226416 - Expose a method to get a node's set of immediately dominated nodes in the dominator tree; r=bz,sfink This adds the `getImmediatelyDominated` method to `DominatorTree` which takes a node id and returns the set of each node ids for every node that is immediately dominated by the node with the given id. The results are sorted by greatest to least retained size. In conjunction with the `root` attribute, this can be used to traverse the whole dominator tree.
devtools/shared/heapsnapshot/DominatorTree.cpp
devtools/shared/heapsnapshot/DominatorTree.h
devtools/shared/heapsnapshot/tests/unit/test_DominatorTree_05.js
devtools/shared/heapsnapshot/tests/unit/xpcshell.ini
dom/webidl/DominatorTree.webidl
js/public/UbiNodeDominatorTree.h
--- a/devtools/shared/heapsnapshot/DominatorTree.cpp
+++ b/devtools/shared/heapsnapshot/DominatorTree.cpp
@@ -1,48 +1,126 @@
 /* -*-  Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2; -*- */
 /* This Source Code Form is subject to the terms of the Mozilla Public
  * License, v. 2.0. If a copy of the MPL was not distributed with this
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 #include "mozilla/devtools/DominatorTree.h"
-
 #include "js/Debug.h"
 #include "mozilla/CycleCollectedJSRuntime.h"
 #include "mozilla/dom/DominatorTreeBinding.h"
 
 namespace mozilla {
 namespace devtools {
 
+static MallocSizeOf
+getCurrentThreadDebuggerMallocSizeOf()
+{
+  auto ccrt = CycleCollectedJSRuntime::Get();
+  MOZ_ASSERT(ccrt);
+  auto rt = ccrt->Runtime();
+  MOZ_ASSERT(rt);
+  auto mallocSizeOf = JS::dbg::GetDebuggerMallocSizeOf(rt);
+  MOZ_ASSERT(mallocSizeOf);
+  return mallocSizeOf;
+}
+
 dom::Nullable<uint64_t>
 DominatorTree::GetRetainedSize(uint64_t aNodeId, ErrorResult& aRv)
 {
   JS::ubi::Node::Id id(aNodeId);
   auto node = mHeapSnapshot->getNodeById(id);
   if (node.isNothing())
     return dom::Nullable<uint64_t>();
 
-  auto ccrt = CycleCollectedJSRuntime::Get();
-  MOZ_ASSERT(ccrt);
-  auto rt = ccrt->Runtime();
-  MOZ_ASSERT(rt);
-  auto mallocSizeOf = JS::dbg::GetDebuggerMallocSizeOf(rt);
-  MOZ_ASSERT(mallocSizeOf);
-
+  auto mallocSizeOf = getCurrentThreadDebuggerMallocSizeOf();
   JS::ubi::Node::Size size = 0;
   if (!mDominatorTree.getRetainedSize(*node, mallocSizeOf, size)) {
     aRv.Throw(NS_ERROR_OUT_OF_MEMORY);
     return dom::Nullable<uint64_t>();
   }
 
   MOZ_ASSERT(size != 0,
              "The node should not have been unknown since we got it from the heap snapshot.");
   return dom::Nullable<uint64_t>(size);
 }
 
+struct NodeAndRetainedSize
+{
+  JS::ubi::Node mNode;
+  JS::ubi::Node::Size mSize;
+
+  NodeAndRetainedSize(const JS::ubi::Node& aNode, JS::ubi::Node::Size aSize)
+    : mNode(aNode)
+    , mSize(aSize)
+  { }
+
+  struct Comparator
+  {
+    static bool
+    Equals(const NodeAndRetainedSize& aLhs, const NodeAndRetainedSize& aRhs)
+    {
+      return aLhs.mSize == aRhs.mSize;
+    }
+
+    static bool
+    LessThan(const NodeAndRetainedSize& aLhs, const NodeAndRetainedSize& aRhs)
+    {
+      // Use > because we want to sort from greatest to least retained size.
+      return aLhs.mSize > aRhs.mSize;
+    }
+  };
+};
+
+void
+DominatorTree::GetImmediatelyDominated(uint64_t aNodeId,
+                                       dom::Nullable<nsTArray<uint64_t>>& aOutResult,
+                                       ErrorResult& aRv)
+{
+  MOZ_ASSERT(aOutResult.IsNull());
+
+  JS::ubi::Node::Id id(aNodeId);
+  Maybe<JS::ubi::Node> node = mHeapSnapshot->getNodeById(id);
+  if (node.isNothing())
+    return;
+
+  // Get all immediately dominated nodes and their retained sizes.
+  MallocSizeOf mallocSizeOf = getCurrentThreadDebuggerMallocSizeOf();
+  Maybe<JS::ubi::DominatorTree::DominatedSetRange> range = mDominatorTree.getDominatedSet(*node);
+  MOZ_ASSERT(range.isSome(), "The node should be known, since we got it from the heap snapshot.");
+  size_t length = range->length();
+  nsTArray<NodeAndRetainedSize> dominatedNodes(length);
+  for (const JS::ubi::Node& dominatedNode : *range) {
+    JS::ubi::Node::Size retainedSize = 0;
+    if (NS_WARN_IF(!mDominatorTree.getRetainedSize(dominatedNode, mallocSizeOf, retainedSize))) {
+      aRv.Throw(NS_ERROR_OUT_OF_MEMORY);
+      return;
+    }
+    MOZ_ASSERT(retainedSize != 0,
+               "retainedSize should not be zero since we know the node is in the dominator tree.");
+
+    dominatedNodes.AppendElement(NodeAndRetainedSize(dominatedNode, retainedSize));
+  }
+
+  // Sort them by retained size.
+  NodeAndRetainedSize::Comparator comparator;
+  dominatedNodes.Sort(comparator);
+
+  // Fill the result with the nodes' ids.
+  JS::ubi::Node root = mDominatorTree.root();
+  aOutResult.SetValue(nsTArray<uint64_t>(length));
+  for (const NodeAndRetainedSize& entry : dominatedNodes) {
+    // The root dominates itself, but we don't want to expose that to JS.
+    if (entry.mNode == root)
+      continue;
+
+    aOutResult.Value().AppendElement(entry.mNode.identifier());
+  }
+}
+
 
 /*** Cycle Collection Boilerplate *****************************************************************/
 
 NS_IMPL_CYCLE_COLLECTION_WRAPPERCACHE(DominatorTree, mParent, mHeapSnapshot)
 
 NS_IMPL_CYCLE_COLLECTING_ADDREF(DominatorTree)
 NS_IMPL_CYCLE_COLLECTING_RELEASE(DominatorTree)
 
--- a/devtools/shared/heapsnapshot/DominatorTree.h
+++ b/devtools/shared/heapsnapshot/DominatorTree.h
@@ -47,14 +47,18 @@ public:
   virtual JSObject* WrapObject(JSContext* aCx,
                                JS::Handle<JSObject*> aGivenProto) override;
 
   // readonly attribute NodeId root
   uint64_t Root() const { return mDominatorTree.root().identifier(); }
 
   // [Throws] NodeSize getRetainedSize(NodeId node)
   dom::Nullable<uint64_t> GetRetainedSize(uint64_t aNodeId, ErrorResult& aRv);
+
+  // [Throws] sequence<NodeId>? getImmediatelyDominated(NodeId node);
+  void GetImmediatelyDominated(uint64_t aNodeId, dom::Nullable<nsTArray<uint64_t>>& aOutDominated,
+                               ErrorResult& aRv);
 };
 
 } // namespace devtools
 } // namespace mozilla
 
 #endif // mozilla_devtools_DominatorTree__
new file mode 100644
--- /dev/null
+++ b/devtools/shared/heapsnapshot/tests/unit/test_DominatorTree_05.js
@@ -0,0 +1,68 @@
+/* Any copyright is dedicated to the Public Domain.
+   http://creativecommons.org/publicdomain/zero/1.0/ */
+
+// Test that we can get the set of immediately dominated nodes for any given
+// node and that this forms a tree.
+
+function run_test() {
+  var dominatorTree = saveHeapSnapshotAndComputeDominatorTree();
+  equal(typeof dominatorTree.getImmediatelyDominated, "function",
+        "getImmediatelyDominated should be a function");
+
+  // Do a traversal of the dominator tree.
+  //
+  // Note that we don't assert directly, only if we get an unexpected
+  // value. There are just way too many nodes in the heap graph to assert for
+  // every one. This test would constantly time out and assertion messages would
+  // overflow the log size.
+
+  var root = dominatorTree.root;
+  var seen = new Set();
+  var stack = [root];
+  while (stack.length > 0) {
+    var top = stack.pop();
+
+    if (seen.has(top)) {
+      ok(false,
+         "This is a tree, not a graph: we shouldn't have multiple edges to the same node");
+    }
+    seen.add(top);
+    if (seen.size % 1000 === 0) {
+      dumpn("Progress update: seen size = " + seen.size);
+    }
+
+    var newNodes = dominatorTree.getImmediatelyDominated(top);
+    if (Object.prototype.toString.call(newNodes) !== "[object Array]") {
+      ok(false, "getImmediatelyDominated should return an array for known node ids");
+    }
+
+    var topSize = dominatorTree.getRetainedSize(top);
+
+    var lastSize = Infinity;
+    for (var i = 0; i < newNodes.length; i++) {
+      if (typeof newNodes[i] !== "number") {
+        ok(false, "Every dominated id should be a number");
+      }
+
+      var thisSize = dominatorTree.getRetainedSize(newNodes[i]);
+
+      if (thisSize >= topSize) {
+        ok(false, "the size of children in the dominator tree should always be less than that of their parent");
+      }
+
+      if (thisSize > lastSize) {
+        ok(false,
+           "children should be sorted by greatest to least retained size, "
+           + "lastSize = " + lastSize + ", thisSize = " + thisSize);
+      }
+
+      lastSize = thisSize;
+      stack.push(newNodes[i]);
+    }
+  }
+
+  ok(true, "Successfully walked the tree");
+  dumpn("Walked " + seen.size + " nodes");
+
+  do_test_finished();
+}
--- a/devtools/shared/heapsnapshot/tests/unit/xpcshell.ini
+++ b/devtools/shared/heapsnapshot/tests/unit/xpcshell.ini
@@ -27,16 +27,17 @@ support-files =
 [test_census-tree-node-05.js]
 [test_census-tree-node-06.js]
 [test_census-tree-node-07.js]
 [test_census-tree-node-08.js]
 [test_DominatorTree_01.js]
 [test_DominatorTree_02.js]
 [test_DominatorTree_03.js]
 [test_DominatorTree_04.js]
+[test_DominatorTree_05.js]
 [test_HeapAnalyses_getCreationTime_01.js]
 [test_HeapAnalyses_readHeapSnapshot_01.js]
 [test_HeapAnalyses_takeCensusDiff_01.js]
 [test_HeapAnalyses_takeCensusDiff_02.js]
 [test_HeapAnalyses_takeCensus_01.js]
 [test_HeapAnalyses_takeCensus_02.js]
 [test_HeapAnalyses_takeCensus_03.js]
 [test_HeapAnalyses_takeCensus_04.js]
--- a/dom/webidl/DominatorTree.webidl
+++ b/dom/webidl/DominatorTree.webidl
@@ -48,9 +48,17 @@ interface DominatorTree {
   readonly attribute NodeId root;
 
   /**
    * Get the retained size of the node with the given id. If given an invalid
    * id, null is returned. Throws an error on OOM.
    */
   [Throws]
   NodeSize? getRetainedSize(NodeId node);
+
+  /**
+   * Get the set of ids of nodes immediately dominated by the node with the
+   * given id. The resulting array is sorted by greatest to least retained
+   * size. If given an invalid id, null is returned. Throws an error on OOM.
+   */
+  [Throws]
+  sequence<NodeId>? getImmediatelyDominated(NodeId node);
 };
--- a/js/public/UbiNodeDominatorTree.h
+++ b/js/public/UbiNodeDominatorTree.h
@@ -136,16 +136,21 @@ class JS_PUBLIC_API(DominatorTree)
             MOZ_ASSERT(beginPtr <= endPtr);
             return DominatedNodePtr(postOrder, beginPtr);
         }
 
         DominatedNodePtr end() const {
             return DominatedNodePtr(postOrder, endPtr);
         }
 
+        size_t length() const {
+            MOZ_ASSERT(beginPtr <= endPtr);
+            return endPtr - beginPtr;
+        }
+
         /**
          * Safely skip ahead `n` dominators in the range, in O(1) time.
          *
          * Example usage:
          *
          *     mozilla::Maybe<DominatedSetRange> range = myDominatorTree.getDominatedSet(myNode);
          *     if (range.isNothing()) {
          *         // Handle unknown nodes however you see fit...