Bug 1225588 - Expose DominatorTree to JavaScript; r=sfink,bz
authorNick Fitzgerald <fitzgen@gmail.com>
Wed, 18 Nov 2015 14:12:23 -0800
changeset 309843 b6c8ce8730d72856699345a4d3c52781e5a84fa7
parent 309842 0389acea3fc76584ffb374a2dc26d2c086b229ac
child 309844 bc5aaa4b23f26a844a4d5946583dc02d0af2132a
push id7649
push usermartin.thomson@gmail.com
push dateThu, 19 Nov 2015 00:06:17 +0000
reviewerssfink, bz
bugs1225588
milestone45.0a1
Bug 1225588 - Expose DominatorTree to JavaScript; r=sfink,bz This commit adds the DominatorTree.webidl interface, which is only exposed to chrome JS. The interface is implemented by mozilla::devtools::DominatorTree, which is a thin wrapper around JS::ubi::DominatorTree. This does not expose any methods on the DominatorTree interface, those will come as follow up changesets.
devtools/shared/heapsnapshot/DominatorTree.cpp
devtools/shared/heapsnapshot/DominatorTree.h
devtools/shared/heapsnapshot/HeapSnapshot.cpp
devtools/shared/heapsnapshot/HeapSnapshot.h
devtools/shared/heapsnapshot/moz.build
devtools/shared/heapsnapshot/tests/mochitest/chrome.ini
devtools/shared/heapsnapshot/tests/mochitest/test_DominatorTree_01.html
devtools/shared/heapsnapshot/tests/unit/dominator-tree-worker.js
devtools/shared/heapsnapshot/tests/unit/test_DominatorTree_01.js
devtools/shared/heapsnapshot/tests/unit/test_DominatorTree_02.js
devtools/shared/heapsnapshot/tests/unit/xpcshell.ini
dom/bindings/Bindings.conf
dom/webidl/DominatorTree.webidl
dom/webidl/HeapSnapshot.webidl
dom/webidl/moz.build
js/public/UbiNodeDominatorTree.h
new file mode 100644
--- /dev/null
+++ b/devtools/shared/heapsnapshot/DominatorTree.cpp
@@ -0,0 +1,30 @@
+/* -*-  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 "mozilla/dom/DominatorTreeBinding.h"
+
+namespace mozilla {
+namespace devtools {
+
+/*** Cycle Collection Boilerplate *****************************************************************/
+
+NS_IMPL_CYCLE_COLLECTION_WRAPPERCACHE(DominatorTree, mParent)
+NS_IMPL_CYCLE_COLLECTING_ADDREF(DominatorTree)
+NS_IMPL_CYCLE_COLLECTING_RELEASE(DominatorTree)
+
+NS_INTERFACE_MAP_BEGIN_CYCLE_COLLECTION(DominatorTree)
+  NS_WRAPPERCACHE_INTERFACE_MAP_ENTRY
+  NS_INTERFACE_MAP_ENTRY(nsISupports)
+NS_INTERFACE_MAP_END
+
+/* virtual */ JSObject*
+DominatorTree::WrapObject(JSContext* aCx, JS::HandleObject aGivenProto)
+{
+  return dom::DominatorTreeBinding::Wrap(aCx, this, aGivenProto);
+}
+
+} // namespace devtools
+} // namespace mozilla
new file mode 100644
--- /dev/null
+++ b/devtools/shared/heapsnapshot/DominatorTree.h
@@ -0,0 +1,50 @@
+/* -*-  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/. */
+
+#ifndef mozilla_devtools_DominatorTree__
+#define mozilla_devtools_DominatorTree__
+
+#include "mozilla/dom/BindingDeclarations.h"
+#include "mozilla/ErrorResult.h"
+#include "mozilla/RefCounted.h"
+#include "js/UbiNodeDominatorTree.h"
+#include "nsWrapperCache.h"
+
+namespace mozilla {
+namespace devtools {
+
+class DominatorTree final : public nsISupports
+                          , public nsWrapperCache
+{
+protected:
+  nsCOMPtr<nsISupports> mParent;
+
+  virtual ~DominatorTree() { }
+
+private:
+  JS::ubi::DominatorTree mDominatorTree;
+
+public:
+  explicit DominatorTree(JS::ubi::DominatorTree&& aDominatorTree, nsISupports* aParent)
+    : mParent(aParent)
+    , mDominatorTree(Move(aDominatorTree))
+  {
+    MOZ_ASSERT(aParent);
+  };
+
+  NS_DECL_CYCLE_COLLECTING_ISUPPORTS;
+  NS_DECL_CYCLE_COLLECTION_SCRIPT_HOLDER_CLASS(DominatorTree);
+
+  nsISupports* GetParentObject() const { return mParent; }
+
+  virtual JSObject* WrapObject(JSContext* aCx,
+                               JS::Handle<JSObject*> aGivenProto) override;
+
+};
+
+} // namespace devtools
+} // namespace mozilla
+
+#endif // mozilla_devtools_DominatorTree__
--- a/devtools/shared/heapsnapshot/HeapSnapshot.cpp
+++ b/devtools/shared/heapsnapshot/HeapSnapshot.cpp
@@ -47,16 +47,18 @@ using namespace dom;
 
 using ::google::protobuf::io::ArrayInputStream;
 using ::google::protobuf::io::CodedInputStream;
 using ::google::protobuf::io::GzipInputStream;
 using ::google::protobuf::io::ZeroCopyInputStream;
 
 using JS::ubi::AtomOrTwoByteChars;
 
+/*** Cycle Collection Boilerplate *****************************************************************/
+
 NS_IMPL_CYCLE_COLLECTION_CLASS(HeapSnapshot)
 
 NS_IMPL_CYCLE_COLLECTION_UNLINK_BEGIN(HeapSnapshot)
   NS_IMPL_CYCLE_COLLECTION_UNLINK(mParent)
 NS_IMPL_CYCLE_COLLECTION_UNLINK_END
 
 NS_IMPL_CYCLE_COLLECTION_TRAVERSE_BEGIN(HeapSnapshot)
   NS_IMPL_CYCLE_COLLECTION_TRAVERSE(mParent)
@@ -376,16 +378,19 @@ HeapSnapshot::saveStackFrame(const proto
   {
     return false;
   }
 
   outFrameId = id;
   return true;
 }
 
+#undef GET_STRING_OR_REF_WITH_PROP_NAMES
+#undef GET_STRING_OR_REF
+
 static inline bool
 StreamHasData(GzipInputStream& stream)
 {
   // Test for the end of the stream. The protobuf library gives no way to tell
   // the difference between an underlying read error and the stream being
   // done. All we can do is attempt to read data and extrapolate guestimations
   // from the result of that operation.
 
@@ -510,18 +515,36 @@ HeapSnapshot::TakeCensus(JSContext* cx, 
   }
 
   if (NS_WARN_IF(!handler.report(rval))) {
     rv.Throw(NS_ERROR_OUT_OF_MEMORY);
     return;
   }
 }
 
-#undef GET_STRING_OR_REF_WITH_PROP_NAMES
-#undef GET_STRING_OR_REF
+already_AddRefed<DominatorTree>
+HeapSnapshot::ComputeDominatorTree(ErrorResult& rv)
+{
+  Maybe<JS::ubi::DominatorTree> maybeTree;
+  {
+    auto ccrt = CycleCollectedJSRuntime::Get();
+    MOZ_ASSERT(ccrt);
+    auto rt = ccrt->Runtime();
+    MOZ_ASSERT(rt);
+    JS::AutoCheckCannotGC nogc(rt);
+    maybeTree = JS::ubi::DominatorTree::Create(rt, nogc, getRoot());
+  }
+
+  if (maybeTree.isNothing()) {
+    rv.Throw(NS_ERROR_OUT_OF_MEMORY);
+    return nullptr;
+  }
+
+  return MakeAndAddRef<DominatorTree>(Move(*maybeTree), mParent);
+}
 
 
 /*** Saving Heap Snapshots ************************************************************************/
 
 // If we are only taking a snapshot of the heap affected by the given set of
 // globals, find the set of zones the globals are allocated within. Returns
 // false on OOM failure.
 static bool
--- a/devtools/shared/heapsnapshot/HeapSnapshot.h
+++ b/devtools/shared/heapsnapshot/HeapSnapshot.h
@@ -4,16 +4,17 @@
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 #ifndef mozilla_devtools_HeapSnapshot__
 #define mozilla_devtools_HeapSnapshot__
 
 #include "js/HashTable.h"
 #include "mozilla/ErrorResult.h"
 #include "mozilla/devtools/DeserializedNode.h"
+#include "mozilla/devtools/DominatorTree.h"
 #include "mozilla/dom/BindingDeclarations.h"
 #include "mozilla/dom/Nullable.h"
 #include "mozilla/HashFunctions.h"
 #include "mozilla/Maybe.h"
 #include "mozilla/RefCounted.h"
 #include "mozilla/RefPtr.h"
 #include "mozilla/TimeStamp.h"
 #include "mozilla/UniquePtr.h"
@@ -145,16 +146,18 @@ public:
     MOZ_ASSERT(p);
     const DeserializedNode& node = *p;
     return JS::ubi::Node(const_cast<DeserializedNode*>(&node));
   }
 
   void TakeCensus(JSContext* cx, JS::HandleObject options,
                   JS::MutableHandleValue rval, ErrorResult& rv);
 
+  already_AddRefed<DominatorTree> ComputeDominatorTree(ErrorResult& rv);
+
   dom::Nullable<uint64_t> GetCreationTime() {
     static const uint64_t maxTime = uint64_t(1) << 53;
     if (timestamp.isSome() && timestamp.ref() <= maxTime) {
       return dom::Nullable<uint64_t>(timestamp.ref());
     }
 
     return dom::Nullable<uint64_t>();
   }
--- a/devtools/shared/heapsnapshot/moz.build
+++ b/devtools/shared/heapsnapshot/moz.build
@@ -10,16 +10,17 @@ if CONFIG['ENABLE_TESTS']:
 XPCSHELL_TESTS_MANIFESTS += [ 'tests/unit/xpcshell.ini' ]
 MOCHITEST_MANIFESTS += [ 'tests/mochitest/mochitest.ini' ]
 MOCHITEST_CHROME_MANIFESTS += [ 'tests/mochitest/chrome.ini' ]
 
 EXPORTS.mozilla.devtools += [
     'AutoMemMap.h',
     'CoreDump.pb.h',
     'DeserializedNode.h',
+    'DominatorTree.h',
     'FileDescriptorOutputStream.h',
     'HeapSnapshot.h',
     'HeapSnapshotTempFileHelperChild.h',
     'HeapSnapshotTempFileHelperParent.h',
     'ZeroCopyNSIOutputStream.h',
 ]
 
 IPDL_SOURCES += [
@@ -27,16 +28,17 @@ IPDL_SOURCES += [
 ]
 
 include('/ipc/chromium/chromium-config.mozbuild')
 
 SOURCES += [
     'AutoMemMap.cpp',
     'CoreDump.pb.cc',
     'DeserializedNode.cpp',
+    'DominatorTree.cpp',
     'FileDescriptorOutputStream.cpp',
     'HeapSnapshot.cpp',
     'HeapSnapshotTempFileHelperParent.cpp',
     'ZeroCopyNSIOutputStream.cpp',
 ]
 
 # Disable RTTI in google protocol buffer
 DEFINES['GOOGLE_PROTOBUF_NO_RTTI'] = True
--- a/devtools/shared/heapsnapshot/tests/mochitest/chrome.ini
+++ b/devtools/shared/heapsnapshot/tests/mochitest/chrome.ini
@@ -1,7 +1,8 @@
 [DEFAULT]
 tags = devtools devtools-memory
 skip-if = buildapp == 'b2g' || os == 'android'
 support-files =
 
+[test_DominatorTree_01.html]
 [test_SaveHeapSnapshot.html]
 
new file mode 100644
--- /dev/null
+++ b/devtools/shared/heapsnapshot/tests/mochitest/test_DominatorTree_01.html
@@ -0,0 +1,37 @@
+<!DOCTYPE HTML>
+<html>
+<!--
+Sanity test that we can compute dominator trees from a heap snapshot in a web window.
+-->
+<head>
+  <meta charset="utf-8">
+  <title>ChromeUtils.saveHeapSnapshot test</title>
+  <script type="application/javascript" src="chrome://mochikit/content/tests/SimpleTest/SimpleTest.js"></script>
+  <link rel="stylesheet" type="text/css" href="chrome://mochikit/content/tests/SimpleTest/test.css">
+</head>
+<body>
+<pre id="test">
+<script>
+SimpleTest.waitForExplicitFinish();
+window.onload = function() {
+  const path = ChromeUtils.saveHeapSnapshot({ runtime: true });
+  const snapshot = ChromeUtils.readHeapSnapshot(path);
+
+  const dominatorTree = snapshot.computeDominatorTree();
+  ok(dominatorTree);
+  ok(dominatorTree instanceof DominatorTree);
+
+  let threw = false;
+  try {
+    new DominatorTree();
+  } catch (e) {
+    threw = true;
+  }
+  ok(threw, "Constructor shouldn't be usable");
+
+  SimpleTest.finish();
+};
+</script>
+</pre>
+</body>
+</html>
new file mode 100644
--- /dev/null
+++ b/devtools/shared/heapsnapshot/tests/unit/dominator-tree-worker.js
@@ -0,0 +1,47 @@
+/* Any copyright is dedicated to the Public Domain.
+   http://creativecommons.org/publicdomain/zero/1.0/ */
+
+console.log("Initializing worker.");
+
+self.onmessage = e => {
+  console.log("Starting test.");
+  try {
+    const path = ThreadSafeChromeUtils.saveHeapSnapshot({ runtime: true });
+    const snapshot = ThreadSafeChromeUtils.readHeapSnapshot(path);
+
+    const dominatorTree = snapshot.computeDominatorTree();
+    ok(dominatorTree);
+    ok(dominatorTree instanceof DominatorTree);
+
+    let threw = false;
+    try {
+      new DominatorTree();
+    } catch (e) {
+      threw = true;
+    }
+    ok(threw, "Constructor shouldn't be usable");
+  } catch (e) {
+    ok(false, "Unexpected error inside worker:\n" + e.toString() + "\n" + e.stack);
+  } finally {
+    done();
+  }
+};
+
+// Proxy assertions to the main thread.
+function ok(val, msg) {
+  console.log("ok(" + !!val + ", \"" + msg + "\")");
+  self.postMessage({
+    type: "assertion",
+    passed: !!val,
+    msg,
+    stack: Error().stack
+  });
+}
+
+// Tell the main thread we are done with the tests.
+function done() {
+  console.log("done()");
+  self.postMessage({
+    type: "done"
+  });
+}
new file mode 100644
--- /dev/null
+++ b/devtools/shared/heapsnapshot/tests/unit/test_DominatorTree_01.js
@@ -0,0 +1,23 @@
+/* Any copyright is dedicated to the Public Domain.
+   http://creativecommons.org/publicdomain/zero/1.0/ */
+
+// Sanity test that we can compute dominator trees.
+
+function run_test() {
+  const path = ChromeUtils.saveHeapSnapshot({ runtime: true });
+  const snapshot = ChromeUtils.readHeapSnapshot(path);
+
+  const dominatorTree = snapshot.computeDominatorTree();
+  ok(dominatorTree);
+  ok(dominatorTree instanceof DominatorTree);
+
+  let threw = false;
+  try {
+    new DominatorTree();
+  } catch (e) {
+    threw = true;
+  }
+  ok(threw, "Constructor shouldn't be usable");
+
+  do_test_finished();
+}
new file mode 100644
--- /dev/null
+++ b/devtools/shared/heapsnapshot/tests/unit/test_DominatorTree_02.js
@@ -0,0 +1,40 @@
+/* Any copyright is dedicated to the Public Domain.
+   http://creativecommons.org/publicdomain/zero/1.0/ */
+
+// Test that we can compute dominator trees from a snapshot in a worker.
+
+add_task(function* () {
+  const worker = new ChromeWorker("resource://test/dominator-tree-worker.js");
+  worker.postMessage({});
+
+  let assertionCount = 0;
+  worker.onmessage = e => {
+    if (e.data.type !== "assertion") {
+      return;
+    }
+
+    ok(e.data.passed, e.data.msg + "\n" + e.data.stack);
+    assertionCount++;
+  };
+
+  yield waitForDone(worker);
+
+  ok(assertionCount > 0);
+  worker.terminate();
+});
+
+function waitForDone(w) {
+  return new Promise((resolve, reject) => {
+    w.onerror = e => {
+      reject();
+      ok(false, "Error in worker: " + e);
+    };
+
+    w.addEventListener("message", function listener(e) {
+      if (e.data.type === "done") {
+        w.removeEventListener("message", listener, false);
+        resolve();
+      }
+    }, false);
+  });
+}
--- a/devtools/shared/heapsnapshot/tests/unit/xpcshell.ini
+++ b/devtools/shared/heapsnapshot/tests/unit/xpcshell.ini
@@ -2,16 +2,17 @@
 tags = devtools heapsnapshot devtools-memory
 head = head_heapsnapshot.js
 tail =
 firefox-appdir = browser
 skip-if = toolkit == 'android' || toolkit == 'gonk'
 
 support-files =
   Census.jsm
+  dominator-tree-worker.js
   heap-snapshot-worker.js
   Match.jsm
 
 [test_census_diff_01.js]
 [test_census_diff_02.js]
 [test_census_diff_03.js]
 [test_census_diff_04.js]
 [test_census_diff_05.js]
@@ -22,16 +23,18 @@ support-files =
 [test_census-tree-node-01.js]
 [test_census-tree-node-02.js]
 [test_census-tree-node-03.js]
 [test_census-tree-node-04.js]
 [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_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/bindings/Bindings.conf
+++ b/dom/bindings/Bindings.conf
@@ -404,16 +404,20 @@ DOMInterfaces = {
 'Document': {
     'nativeType': 'nsIDocument',
     'binaryNames': {
         'documentURI': 'documentURIFromJS',
         'URL': 'documentURIFromJS'
     }
 },
 
+'DominatorTree': {
+    'nativeType': 'mozilla::devtools::DominatorTree'
+},
+
 'DOMException': {
     'binaryNames': {
         'message': 'messageMoz',
     },
 },
 
 'DOMMatrixReadOnly': {
     'headerFile': 'mozilla/dom/DOMMatrix.h',
new file mode 100644
--- /dev/null
+++ b/dom/webidl/DominatorTree.webidl
@@ -0,0 +1,41 @@
+/* -*- Mode: IDL; 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/.
+ */
+
+/**
+ * In a directed graph with a root node `R`, a node `A` is said to "dominate" a
+ * node `B` iff every path from `R` to `B` contains `A`. A node `A` is said to
+ * be the "immediate dominator" of a node `B` iff it dominates `B`, is not `B`
+ * itself, and does not dominate any other nodes which also dominate `B` in
+ * turn.
+ *
+ * If we take every node from a graph `G` and create a new graph `T` with edges
+ * to each node from its immediate dominator, then `T` is a tree (each node has
+ * only one immediate dominator, or none if it is the root). This tree is called
+ * a "dominator tree".
+ *
+ * This interface represents a dominator tree constructed from a HeapSnapshot's
+ * heap graph. The domination relationship and dominator trees are useful tools
+ * for analyzing heap graphs because they tell you:
+ *
+ *   - Exactly what could be reclaimed by the GC if some node `A` became
+ *     unreachable: those nodes which are dominated by `A`,
+ *
+ *   - The "retained size" of a node in the heap graph, in contrast to its
+ *     "shallow size". The "shallow size" is the space taken by a node itself,
+ *     not counting anything it references. The "retained size" of a node is its
+ *     shallow size plus the size of all the things that would be collected if
+ *     the original node wasn't (directly or indirectly) referencing them. In
+ *     other words, the retained size is the shallow size of a node plus the
+ *     shallow sizes of every other node it dominates. For example, the root
+ *     node in a binary tree might have a small shallow size that does not take
+ *     up much space itself, but it dominates the rest of the binary tree and
+ *     its retained size is therefore significant (assuming no external
+ *     references into the tree).
+ */
+[ChromeOnly, Exposed=(Window,System,Worker)]
+interface DominatorTree {
+
+};
--- a/dom/webidl/HeapSnapshot.webidl
+++ b/dom/webidl/HeapSnapshot.webidl
@@ -51,9 +51,17 @@ interface HeapSnapshot {
    *       }
    *     }
    *
    * See the `takeCensus` section of the `js/src/doc/Debugger/Debugger.Memory.md`
    * file for detailed documentation.
    */
   [Throws]
   any takeCensus(object? options);
+
+  /**
+   * Compute the dominator tree for this heap snapshot.
+   *
+   * @see DominatorTree.webidl
+   */
+  [Throws]
+  DominatorTree computeDominatorTree();
 };
--- a/dom/webidl/moz.build
+++ b/dom/webidl/moz.build
@@ -118,16 +118,17 @@ WEBIDL_FILES = [
     'Document.webidl',
     'DocumentFragment.webidl',
     'DocumentTimeline.webidl',
     'DocumentType.webidl',
     'DOMCursor.webidl',
     'DOMError.webidl',
     'DOMException.webidl',
     'DOMImplementation.webidl',
+    'DominatorTree.webidl',
     'DOMMatrix.webidl',
     'DOMMobileMessageError.webidl',
     'DOMParser.webidl',
     'DOMPoint.webidl',
     'DOMQuad.webidl',
     'DOMRect.webidl',
     'DOMRectList.webidl',
     'DOMRequest.webidl',
--- a/js/public/UbiNodeDominatorTree.h
+++ b/js/public/UbiNodeDominatorTree.h
@@ -116,17 +116,17 @@ class JS_PUBLIC_API(DominatorTree)
             if (MOZ_UNLIKELY(nodeCount == UINT32_MAX))
                 return false;
             return postOrder.append(node);
         };
 
         auto onEdge = [&](const Node& origin, const Edge& edge) {
             auto p = predecessorSets.lookupForAdd(edge.referent);
             if (!p) {
-                auto set = rt->make_unique<NodeSet>();
+                mozilla::UniquePtr<NodeSet, DeletePolicy<NodeSet>> set(js_new<NodeSet>());
                 if (!set ||
                     !set->init() ||
                     !predecessorSets.add(p, edge.referent, mozilla::Move(set)))
                 {
                     return false;
                 }
             }
             MOZ_ASSERT(p && p->value());