[observatory] Add an "ownership" analysis for the heap snapshot.

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';
 
@@ skipping 426 matching lines @@
 
   int get internalSize => _internalSize;
   int get externalSize => _externalSize;
   int get vertexCount => _N;
   int get edgeCount => _E;
 
   ObjectVertex get root => new ObjectVertex._(ROOT, this);
   MergedObjectVertex get mergedRoot => new MergedObjectVertex._(ROOT, this);
   Iterable<ObjectVertex> get vertices => new _VerticesIterable(this);
 
+  int get numCids => _numCids;
+  int getOwnedByCid(int cid) => _ownedSizesByCid[cid];
+
   Iterable<ObjectVertex> getMostRetained({int classId, int limit}) {
     List<ObjectVertex> _mostRetained =
         new List<ObjectVertex>.from(vertices.where((u) => !u.isRoot));
     _mostRetained.sort((u, v) => v.retainedSize - u.retainedSize);
 
     var result = _mostRetained;
     if (classId != null) {
       result = result.where((u) => u.vmCid == classId);
     }
     if (limit != null) {
       result = result.take(limit);
     }
     return result;
   }
 
   Stream<List> process() {
     final controller = new StreamController<List>.broadcast();
     (() async {
       // We build futures here instead of marking the steps as async to avoid the
       // heavy lifting being inside a transformed method.
 
       controller.add(["Remapping $_N objects...", 0.0]);
       await new Future(() => _remapNodes());
 
-      controller.add(["Remapping $_E references...", 15.0]);
+      controller.add(["Remapping $_E references...", 10.0]);
       await new Future(() => _remapEdges());
 
       _addrToId = null;
       _chunks = null;
 
-      controller.add(["Finding depth-first order...", 30.0]);
+      controller.add(["Finding depth-first order...", 20.0]);
       await new Future(() => _dfs());
 
-      controller.add(["Finding predecessors...", 40.0]);
+      controller.add(["Finding predecessors...", 30.0]);
       await new Future(() => _buildPredecessors());
 
-      controller.add(["Finding dominators...", 50.0]);
+      controller.add(["Finding dominators...", 40.0]);
       await new Future(() => _buildDominators());
 
+      _semi = null;
+      _parent = null;
+
+      controller.add(["Finding in-degree(1) groups...", 50.0]);
+      await new Future(() => _buildOwnedSizes());
+
       _firstPreds = null;
       _preds = null;
 
-      _semi = null;
-      _parent = null;
-
       controller.add(["Finding retained sizes...", 60.0]);
       await new Future(() => _calculateRetainedSizes());
 
       _vertex = null;
 
       controller.add(["Linking dominator tree children...", 70.0]);
       await new Future(() => _linkDominatorChildren());
 
       controller.add(["Sorting dominator tree children...", 80.0]);
       await new Future(() => _sortDominatorChildren());
 
       controller.add(["Merging dominator tree siblings...", 90.0]);
       await new Future(() => _mergeDominatorSiblings());
 
       controller.add(["Processed", 100.0]);
       controller.close();
     }());
     return controller.stream;
   }
 
   List<ByteData> _chunks;
 
   int _kObjectAlignment;
   int _kStackCid;
+  int _kFieldCid;
+  int _numCids;
   int _N; // Objects in the snapshot.
   int _Nconnected; // Objects reachable from root.
   int _E; // References in the snapshot.
   int _internalSize;
   int _externalSize;
 
   // Indexed by node id, with id 0 representing invalid/uninitialized.
   // From snapshot.
   Uint16List _cids;
   Uint32List _shallowSizes;
   Uint32List _externalSizes;
   Uint32List _firstSuccs;
   Uint32List _succs;
   Uint32List _addressesLow; // No Uint64List in Javascript.
   Uint32List _addressesHigh;
 
   // Intermediates.
   AddressMapper _addrToId;
   Uint32List _vertex;
   Uint32List _parent;
   Uint32List _semi;
   Uint32List _firstPreds; // Offset into preds.
   Uint32List _preds;
 
   // Outputs.
   Uint32List _doms;
   Uint32List _retainedSizes;
   Uint32List _mergedDomHead;
   Uint32List _mergedDomNext;
+  Uint32List _ownedSizesByCid;
 
   void _remapNodes() {
     var N = _N;
     var E = 0;
     var addrToId = new AddressMapper(N);
 
     var addressesHigh = new Uint32List(N + 1);
     var addressesLow = new Uint32List(N + 1);
     var shallowSizes = new Uint32List(N + 1);
     var externalSizes = 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;
+    stream.readUnsigned();
+    _kFieldCid = stream.clampedUint32;
+    stream.readUnsigned();
+    _numCids = stream.clampedUint32;
 
     var id = ROOT;
     while (id <= N) {
       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 34 matching lines @@
     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(); // kObjectAlignment
     stream.skipUnsigned(); // kStackCid
+    stream.skipUnsigned(); // kFieldCid
+    stream.skipUnsigned(); // numCids
 
     var id = 1, edge = 0;
     while (id <= N) {
       stream.skipUnsigned(); // addr
       stream.skipUnsigned(); // shallowSize
       stream.skipUnsigned(); // cid
 
       firstSuccs[id] = edge;
 
       stream.readUnsigned();
@@ skipping 158 matching lines @@
           var predIndex = nextPreds[succId]++;
           preds[predIndex] = i;
         }
       }
     }
 
     _firstPreds = firstPreds;
     _preds = preds;
   }
 
+  // Fold the size of any object with in-degree(1) into its parent.
+  // Requires the DFS numbering and predecessor lists.
+  void _buildOwnedSizes() {
+    var N = _N;
+    var Nconnected = _Nconnected;
+    var kStackCid = _kStackCid;
+    var kFieldCid = _kFieldCid;
+
+    var cids = _cids;
+    var shallowSizes = _shallowSizes;
+    var externalSizes = _externalSizes;
+    var vertex = _vertex;
+    var firstPreds = _firstPreds;
+    var preds = _preds;
+
+    var ownedSizes = new Uint32List(N + 1);
+    for (var i = 1; i <= Nconnected; i++) {
+      var v = vertex[i];
+      ownedSizes[v] = shallowSizes[v] + externalSizes[v];
+      assert(ownedSizes[v] != 0);
+    }
+
+    for (var i = Nconnected; i > 1; i--) {
+      var w = vertex[i];
+      assert(w != ROOT);
+
+      var onlyPred = SENTINEL;
+
+      var startPred = firstPreds[w];
+      var limitPred = firstPreds[w + 1];
+      for (var predIndex = startPred; predIndex < limitPred; predIndex++) {
+        var v = preds[predIndex];
+        if (v == w) {
+          // Ignore self-predecessor.
+        } else if (onlyPred == SENTINEL) {
+          onlyPred = v;
+        } else if (onlyPred == v) {
+          // Repeated predecessor.
+        } else {
+          // Multiple-predecessors.
+          onlyPred = SENTINEL;
+          break;
+        }
+      }
+
+      // If this object has a single precessor which is not a Field, Stack or
+      // the root, blame its size against the precessor.
+      if ((onlyPred != SENTINEL) &&
+          (onlyPred != ROOT) &&
+          (cids[onlyPred] != kStackCid) &&
+          (cids[onlyPred] != kFieldCid)) {
+        assert(ownedSizes[w] != 0);
+        ownedSizes[onlyPred] += ownedSizes[w];
+        ownedSizes[w] = 0;
+      }
+    }
+
+    // TODO(rmacnak): Maybe keep the per-objects sizes to be able to provide
+    // examples of large owners for each class.
+    var ownedSizesByCid = new Uint32List(_numCids);
+    for (var i = 1; i <= Nconnected; i++) {
+      var v = vertex[i];
+      var cid = cids[v];
+      ownedSizesByCid[cid] += ownedSizes[v];
+    }
+
+    _ownedSizesByCid = ownedSizesByCid;
+  }
+
   static int _eval(int v, Uint32List ancestor, Uint32List semi,
       Uint32List label, Uint32List stackNode, Uint8List stackState) {
     if (ancestor[v] == SENTINEL) {
       return label[v];
     } else {
       {
         // Inlined 'compress' with an explicit stack to prevent JS stack
         // overflow.
         var top = 0;
         stackNode[top] = v;
@@ skipping 327 matching lines @@
 
         // From all the siblings between child and after, take their children,
         // merge them and given to child.
         mergeChildrenAndSort(child, after);
 
         child = after;
       }
     }
   }
 }