Add a version of heap snapshots that use only fields and stack frames as roots and only include ins…

runtime/observatory/lib/object_graph.dart

Index: runtime/observatory/lib/object_graph.dart
diff --git a/runtime/observatory/lib/object_graph.dart b/runtime/observatory/lib/object_graph.dart
index d1c171bfe017a6ceb8118ba67054e412d412b80c..a691beba685c7f97b05bb4319a25f984dd1746fc 100644
--- a/runtime/observatory/lib/object_graph.dart
+++ b/runtime/observatory/lib/object_graph.dart
@@ -219,6 +219,8 @@ class ReadStream {
 // elements as the sentinel.
 const ROOT = 1;
 const SENTINEL = 0;
+// Keep in sync with runtime/vm/object_graph.cc.
+const kStackCid = 1;

[Cutch, 2016/11/18 20:40:31]

can we get this from the VM over the protocol somehow?

[rmacnak, 2016/11/18 22:34:02]

pushing in the header alongside the object alignment

 
 class ObjectVertex {
   final int _id;
@@ -227,6 +229,7 @@ class ObjectVertex {
   ObjectVertex._(this._id, this._graph);
 
   bool get isRoot => ROOT == _id;
+  bool get isStack => kStackCid == vmCid;
 
   bool operator ==(other) => _id == other._id && _graph == other._graph;
   int get hashCode => _id;
@@ -300,6 +303,7 @@ class MergedObjectVertex {
   MergedObjectVertex._(this._id, this._graph);
 
   bool get isRoot => ROOT == _id;
+  bool get isStack => kStackCid == vmCid;
 
   bool operator ==(other) => _id == other._id && _graph == other._graph;
   int get hashCode => _id;
@@ -497,8 +501,9 @@ class ObjectGraph {
   List<ByteData> _chunks;
 
   int _kObjectAlignment;
-  int _N;
-  int _E;
+  int _N;  // Objects in the snapshot.
+  int _Nconnected;  // Objects reachable from root.
+  int _E;  // References in the snapshot.
   int _size;
 
   // Indexed by node id, with id 0 representing invalid/uninitialized.
@@ -660,15 +665,37 @@ class ObjectGraph {
       }
     }
 
-    assert(dfsNumber == N);
-    for (var i = ROOT; i <= N; i++) {
-      assert(semi[i] != SENTINEL);
+    if (dfsNumber != N) {
+      // This may happen in filtered snapshots.
+      print("Warning: graph has unconnected nodes");

[Cutch, 2016/11/18 20:40:31]

remove or use the logger?

[rmacnak, 2016/11/18 22:34:02]

Changed to use logger.

+    }
+
+    for (var i = 1; i <= dfsNumber; i++) {

[Cutch, 2016/11/18 20:40:31]

assert(() {
....
});

[rmacnak, 2016/11/18 22:34:02]

Done.

+      var v = vertex[i];
+      assert(semi[v] != SENTINEL);
     }
-    assert(parent[ROOT] == SENTINEL);
-    for (var i = ROOT + 1; i <= N; i++) {
-      assert(parent[i] != SENTINEL);
+    assert(parent[1] == SENTINEL);
+    for (var i = 2; i <= dfsNumber; i++) {
+      var v = vertex[i];
+      assert(parent[v] != SENTINEL);
     }
 
+    if (dfsNumber != N) {
+      // Remove successors of unconnected nodes
+      for (var i = ROOT + 1; i <= N; i++) {

[Cutch, 2016/11/18 20:40:31]

how about we add a:

const FIRST_OBJECT = ROOT + 1;

and use that everywhere?

[rmacnak, 2016/11/18 22:34:02]

ROOT is the first object.

+        if (parent[i] == SENTINEL) {
+          var startSuccIndex = firstSuccs[i];
+          var limitSuccIndex = firstSuccs[i + 1];
+          for (var succIndex = startSuccIndex;
+               succIndex < limitSuccIndex;
+               succIndex++) {
+            succs[succIndex] = SENTINEL;
+          }
+        }
+      }
+    }
+
+    _Nconnected = dfsNumber;
     _vertex = vertex;
     _semi = semi;
     _parent = parent;
@@ -676,6 +703,7 @@ class ObjectGraph {
 
   void _buildPredecessors() {
     var N = _N;
+    var Nconnected = _Nconnected;
     var E = _E;
     var firstSuccs = _firstSuccs;
     var succs = _succs;
@@ -691,7 +719,9 @@ class ObjectGraph {
     // Count predecessors of each node.
     for (var succIndex = 0; succIndex < E; succIndex++) {
       var succId = succs[succIndex];
-      numPreds[succId]++;
+      if (succId != SENTINEL) {
+        numPreds[succId]++;
+      }
     }
 
     // Assign indices into predecessors array.
@@ -704,8 +734,10 @@ class ObjectGraph {
       firstPreds[i] = thisPredIndex;
       nextPreds[i] = thisPredIndex;
     }
-    assert(predIndex == E);
-    firstPreds[N + 1] = E; // Extra entry for cheap boundary detection.
+    if (N == Nconnected) {
+      assert(predIndex == E);
+    }
+    firstPreds[N + 1] = predIndex; // Extra entry for cheap boundary detection.
 
     // Fill predecessors array.
     for (var i = 1; i <= N; i++) {
@@ -715,8 +747,10 @@ class ObjectGraph {
           succIndex < limitSuccIndex;
           succIndex++) {
         var succId = succs[succIndex];
-        var predIndex = nextPreds[succId]++;
-        preds[predIndex] = i;
+        if (succId != SENTINEL) {
+          var predIndex = nextPreds[succId]++;
+          preds[predIndex] = i;
+        }
       }
     }
 
@@ -802,6 +836,7 @@ class ObjectGraph {
   // in a Flowgraph."
   void _buildDominators() {
     var N = _N;
+    var Nconnected = _Nconnected;
 
     var vertex = _vertex;
     var semi = _semi;
@@ -825,7 +860,7 @@ class ObjectGraph {
     var stackNode = new Uint32List(N + 1);
     var stackState = new Uint8List(N + 1);
 
-    for (var i = N; i > 1; i--) {
+    for (var i = Nconnected; i > 1; i--) {
       var w = vertex[i];
       assert(w != ROOT);
 
@@ -864,7 +899,7 @@ class ObjectGraph {
       assert(buckets[i] == null);
     }
     // Lengauer & Tarjan Step 4.
-    for (var i = 2; i <= N; i++) {
+    for (var i = 2; i <= Nconnected; i++) {
       var w = vertex[i];
       if (dom[w] != vertex[semi[w]]) {
         dom[w] = dom[dom[w]];
@@ -876,6 +911,7 @@ class ObjectGraph {
 
   void _calculateRetainedSizes() {
     var N = _N;
+    var Nconnected = _Nconnected;
 
     var size = 0;
     var shallowSizes = _shallowSizes;
@@ -883,8 +919,9 @@ class ObjectGraph {
     var doms = _doms;
 
     // Sum shallow sizes.
-    for (var i = ROOT; i < N; i++) {
-      size += shallowSizes[i];
+    for (var i = 1; i <= Nconnected; i++) {

[Cutch, 2016/11/18 20:40:31]

FIRST_OBJECT

[rmacnak, 2016/11/18 22:34:02]

1 here is a DFS number, not a node index.

+      var v = vertex[i];
+      size += shallowSizes[v];
     }
 
     // Start with retained size as shallow size.
@@ -892,12 +929,14 @@ class ObjectGraph {
 
     // In post order (bottom up), add retained size to dominator's retained
     // size, skipping root.
-    for (var i = N; i > 1; i--) {
+    for (var i = Nconnected; i > 1; i--) {
       var v = vertex[i];
       assert(v != ROOT);
-      retainedSizes[doms[i]] += retainedSizes[i];
+      retainedSizes[doms[v]] += retainedSizes[v];
     }
 
+    assert(retainedSizes[ROOT] == size);  // Root retains everything.
+
     _retainedSizes = retainedSizes;
     _size = size;
   }