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

 // Copyright (c) 2014, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 library object_graph;
 
 import 'dart:async';
 import 'dart:collection';
 import 'dart:typed_data';
 
+import 'package:logging/logging.dart';
+
 class _JenkinsSmiHash {
   static int combine(int hash, int value) {
     hash = 0x1fffffff & (hash + value);
     hash = 0x1fffffff & (hash + ((0x0007ffff & hash) << 10));
     return hash ^ (hash >> 6);
   }
 
   static int finish(int hash) {
     hash = 0x1fffffff & (hash + ((0x03ffffff & hash) << 3));
     hash = hash ^ (hash >> 11);
@@ skipping 199 matching lines @@
 const ROOT = 1;
 const SENTINEL = 0;
 
 class ObjectVertex {
   final int _id;
   final ObjectGraph _graph;
 
   ObjectVertex._(this._id, this._graph);
 
   bool get isRoot => ROOT == _id;
+  bool get isStack => vmCid == _graph._kStackCid;
 
   bool operator ==(other) => _id == other._id && _graph == other._graph;
   int get hashCode => _id;
 
   int get retainedSize => _graph._retainedSizes[_id];
   ObjectVertex get dominator => new ObjectVertex._(_graph._doms[_id], _graph);
 
   int get shallowSize => _graph._shallowSizes[_id];
   int get vmCid => _graph._cids[_id];
 
@@ skipping 53 matching lines @@
 // object of this set. The other members of the set are found by walking the
 // mergedDomNext links until finding the sentinel node or a node with a
 // different class.
 class MergedObjectVertex {
   final int _id;
   final ObjectGraph _graph;
 
   MergedObjectVertex._(this._id, this._graph);
 
   bool get isRoot => ROOT == _id;
+  bool get isStack => vmCid == _graph._kStackCid;
 
   bool operator ==(other) => _id == other._id && _graph == other._graph;
   int get hashCode => _id;
 
   int get vmCid => _graph._cids[_id];
 
   int get shallowSize {
     var cids = _graph._cids;
     var size = 0;
     var sibling = _id;
@@ skipping 177 matching lines @@
 
       controller.add(["Processed", 100.0]);
       controller.close();
     }());
     return controller.stream;
   }
 
   List<ByteData> _chunks;
 
   int _kObjectAlignment;
-  int _N;
-  int _E;
+  int _kStackCid;
+  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.
   // From snapshot.
   Uint16List _cids;
   Uint32List _shallowSizes;
   Uint32List _firstSuccs;
   Uint32List _succs;
   Uint32List _addressesLow; // No Uint64List in Javascript.
   Uint32List _addressesHigh;
@@ skipping 18 matching lines @@
     var addrToId = new AddressMapper(N);
 
     var addressesHigh = new Uint32List(N + 1);
     var addressesLow = new Uint32List(N + 1);
     var shallowSizes = new Uint32List(N + 1);
     var cids = new Uint16List(N + 1);
 
     var stream = new ReadStream(_chunks);
     stream.readUnsigned();
     _kObjectAlignment = stream.clampedUint32;
+    stream.readUnsigned();
+    _kStackCid = stream.clampedUint32;
 
     var id = ROOT;
     while (stream.pendingBytes > 0) {
       stream.readUnsigned(); // addr
       addrToId.put(stream.high, stream.mid, stream.low, id);
       addressesHigh[id] = stream.highUint32;
       addressesLow[id] = stream.lowUint32;
       stream.readUnsigned(); // shallowSize
       shallowSizes[id] = stream.clampedUint32;
       stream.readUnsigned(); // cid
@@ skipping 20 matching lines @@
 
   void _remapEdges() {
     var N = _N;
     var E = _E;
     var addrToId = _addrToId;
 
     var firstSuccs = new Uint32List(N + 2);
     var succs = new Uint32List(E);
 
     var stream = new ReadStream(_chunks);
-    stream.skipUnsigned(); // addr alignment
+    stream.skipUnsigned(); // kObjectAlignment
+    stream.skipUnsigned(); // kStackCid
 
     var id = 1, edge = 0;
     while (stream.pendingBytes > 0) {
       stream.skipUnsigned(); // addr
       stream.skipUnsigned(); // shallowSize
       stream.skipUnsigned(); // cid
 
       firstSuccs[id] = edge;
 
       stream.readUnsigned();
@@ skipping 62 matching lines @@
           stackTop++;
           stackNodes[stackTop] = childId;
           stackCurrentEdgePos[stackTop] = firstSuccs[childId];
         }
       } else {
         // Done with all children.
         stackTop--;
       }
     }
 
-    assert(dfsNumber == N);
-    for (var i = ROOT; i <= N; i++) {
-      assert(semi[i] != SENTINEL);
-    }
-    assert(parent[ROOT] == SENTINEL);
-    for (var i = ROOT + 1; i <= N; i++) {
-      assert(parent[i] != SENTINEL);
+    if (dfsNumber != N) {
+      // This may happen in filtered snapshots.
+      Logger.root.warning('Heap snapshot contains unreachable nodes.');
     }
 
+    assert(() {
+      for (var i = 1; i <= dfsNumber; i++) {
+        var v = vertex[i];
+        assert(semi[v] != SENTINEL);
+      }
+      assert(parent[1] == SENTINEL);
+      for (var i = 2; i <= dfsNumber; i++) {
+        var v = vertex[i];
+        assert(parent[v] != SENTINEL);
+      }
+      return true;
+    });
+
+    if (dfsNumber != N) {
+      // Remove successors of unconnected nodes
+      for (var i = ROOT + 1; i <= N; i++) {
+        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;
   }
 
   void _buildPredecessors() {
     var N = _N;
+    var Nconnected = _Nconnected;
     var E = _E;
     var firstSuccs = _firstSuccs;
     var succs = _succs;
 
     // This is first filled with the predecessor counts, then reused to hold the
     // offset to the first predecessor (see alias below).
     // + 1 because 0 is a sentinel
     // + 1 so the number of predecessors can be found from the difference with
     // the next node's offset.
     var numPreds = new Uint32List(N + 2);
     var preds = new Uint32List(E);
 
     // 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.
     var firstPreds = numPreds; // Alias.
     var nextPreds = new Uint32List(N + 1);
     var predIndex = 0;
     for (var i = 1; i <= N; i++) {
       var thisPredIndex = predIndex;
       predIndex += numPreds[i];
       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++) {
       var startSuccIndex = firstSuccs[i];
       var limitSuccIndex = firstSuccs[i + 1];
       for (var succIndex = startSuccIndex;
           succIndex < limitSuccIndex;
           succIndex++) {
         var succId = succs[succIndex];
-        var predIndex = nextPreds[succId]++;
-        preds[predIndex] = i;
+        if (succId != SENTINEL) {
+          var predIndex = nextPreds[succId]++;
+          preds[predIndex] = i;
+        }
       }
     }
 
     _firstPreds = firstPreds;
     _preds = preds;
   }
 
   static int _eval(int v, Uint32List ancestor, Uint32List semi,
       Uint32List label, Uint32List stackNode, Uint8List stackState) {
     if (ancestor[v] == SENTINEL) {
@@ skipping 65 matching lines @@
     while (s != 0) {
       ancestor[s] = v;
       s = child[s];
     }
   }
 
   // T. Lengauer and R. E. Tarjan. "A Fast Algorithm for Finding Dominators
   // in a Flowgraph."
   void _buildDominators() {
     var N = _N;
+    var Nconnected = _Nconnected;
 
     var vertex = _vertex;
     var semi = _semi;
     var parent = _parent;
     var firstPreds = _firstPreds;
     var preds = _preds;
 
     var dom = new Uint32List(N + 1);
 
     var ancestor = new Uint32List(N + 1);
     var label = new Uint32List(N + 1);
     for (var i = 1; i <= N; i++) {
       label[i] = i;
     }
     var buckets = new List(N + 1);
     var child = new Uint32List(N + 1);
     var size = new Uint32List(N + 1);
     for (var i = 1; i <= N; i++) {
       size[i] = 1;
     }
     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);
 
       // Lengauer & Tarjan Step 2.
       var startPred = firstPreds[w];
       var limitPred = firstPreds[w + 1];
       for (var predIndex = startPred; predIndex < limitPred; predIndex++) {
         var v = preds[predIndex];
         var u = _eval(v, ancestor, semi, label, stackNode, stackState);
         if (semi[u] < semi[w]) {
@@ skipping 18 matching lines @@
         for (var v in bucket) {
           var u = _eval(v, ancestor, semi, label, stackNode, stackState);
           dom[v] = semi[u] < semi[v] ? u : parent[w];
         }
       }
     }
     for (var i = ROOT; i <= N; i++) {
       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]];
       }
     }
 
     _doms = dom;
   }
 
   void _calculateRetainedSizes() {
     var N = _N;
+    var Nconnected = _Nconnected;
 
     var size = 0;
     var shallowSizes = _shallowSizes;
     var vertex = _vertex;
     var doms = _doms;
 
     // Sum shallow sizes.
-    for (var i = ROOT; i < N; i++) {
-      size += shallowSizes[i];
+    for (var i = 1; i <= Nconnected; i++) {
+      var v = vertex[i];
+      size += shallowSizes[v];
     }
 
     // Start with retained size as shallow size.
     var retainedSizes = new Uint32List.fromList(shallowSizes);
 
     // 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;
   }
 
   // Build linked lists of the children for each node in the dominator tree.
   void _linkDominatorChildren() {
     var N = _N;
     var doms = _doms;
     var head = new Uint32List(N + 1);
     var next = new Uint32List(N + 1);
@@ skipping 145 matching lines @@
 
         // From all the siblings between child and after, take their children,
         // merge them and given to child.
         mergeChildrenAndSort(child, after);
 
         child = after;
       }
     }
   }
 }