Add external sizes to the heap dominator tree.

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 220 matching lines @@
   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 externalSize => _graph._externalSizes[_id];
   int get vmCid => _graph._cids[_id];
 
   get successors => new _SuccessorsIterable(_graph, _id);
 
   String get address {
     // Note that everywhere else in this file, "address" really means an address
     // scaled down by kObjectAlignment. They were scaled down so they would fit
     // into Smis on the client.
 
     var high32 = _graph._addressesHigh[_id];
@@ skipping 63 matching lines @@
     var cids = _graph._cids;
     var size = 0;
     var sibling = _id;
     while (sibling != SENTINEL && cids[sibling] == cids[_id]) {
       size += _graph._shallowSizes[sibling];
       sibling = _graph._mergedDomNext[sibling];
     }
     return size;
   }
 
+  int get externalSize {
+    var cids = _graph._cids;
+    var size = 0;
+    var sibling = _id;
+    while (sibling != SENTINEL && cids[sibling] == cids[_id]) {
+      size += _graph._externalSizes[sibling];
+      sibling = _graph._mergedDomNext[sibling];
+    }
+    return size;
+  }
+
   int get retainedSize {
     var cids = _graph._cids;
     var size = 0;
     var sibling = _id;
     while (sibling != SENTINEL && cids[sibling] == cids[_id]) {
       size += _graph._retainedSizes[sibling];
       sibling = _graph._mergedDomNext[sibling];
     }
     return size;
   }
@@ skipping 82 matching lines @@
     current = new ObjectVertex._(_nextId++, _graph);
     return true;
   }
 }
 
 class ObjectGraph {
   ObjectGraph(List<ByteData> chunks, int nodeCount)
       : this._chunks = chunks,
         this._N = nodeCount;
 
-  int get size => _size;
+  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);
 
   Iterable<ObjectVertex> getMostRetained({int classId, int limit}) {
     List<ObjectVertex> _mostRetained =
         new List<ObjectVertex>.from(vertices.where((u) => !u.isRoot));
@@ skipping 59 matching lines @@
     return controller.stream;
   }
 
   List<ByteData> _chunks;
 
   int _kObjectAlignment;
   int _kStackCid;
   int _N; // Objects in the snapshot.
   int _Nconnected; // Objects reachable from root.
   int _E; // References in the snapshot.
-  int _size;
+  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;
 
   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;
 
     var id = ROOT;
-    while (stream.pendingBytes > 0) {
+    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
       cids[id] = stream.clampedUint32;
 
       stream.readUnsigned();
       while (!stream.isZero) {
         E++;
         stream.readUnsigned();
       }
       id++;
     }
     assert(id == (N + 1));

[cbernaschina, 2017/08/28 16:15:18]

Is this assertion still needed?

[rmacnak, 2017/08/28 17:08:20]

No, this isn't useful anymore. Removed.

 
     assert(ROOT == addrToId.get(0, 0, 0));
 
+    stream.readUnsigned();
+    assert(stream.isZero);
+
+    stream.readUnsigned(); // addr
+    while (!stream.isZero) {
+      var nodeId = addrToId.get(stream.high, stream.mid, stream.low);
+      stream.readUnsigned(); // externalSize
+      externalSizes[nodeId] += stream.clampedUint32;
+
+      stream.readUnsigned(); // addr
+    }
+
     _E = E;
     _addrToId = addrToId;
     _addressesLow = addressesLow;
     _addressesHigh = addressesHigh;
     _shallowSizes = shallowSizes;
+    _externalSizes = externalSizes;
     _cids = cids;
   }
 
   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(); // kObjectAlignment
     stream.skipUnsigned(); // kStackCid
 
     var id = 1, edge = 0;
-    while (stream.pendingBytes > 0) {
+    while (id <= N) {
       stream.skipUnsigned(); // addr
       stream.skipUnsigned(); // shallowSize
       stream.skipUnsigned(); // cid
 
       firstSuccs[id] = edge;
 
       stream.readUnsigned();
       while (!stream.isZero) {
         var childId = addrToId.get(stream.high, stream.mid, stream.low);
         if (childId != null) {
@@ skipping 307 matching lines @@
       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 internalSize = 0;
+    var externalSize = 0;
     var shallowSizes = _shallowSizes;
+    var externalSizes = _externalSizes;
     var vertex = _vertex;
     var doms = _doms;
 
-    // Sum shallow sizes.
+    // Sum internal and external sizes.
     for (var i = 1; i <= Nconnected; i++) {
       var v = vertex[i];
-      size += shallowSizes[v];
+      internalSize += shallowSizes[v];
+      externalSize += externalSizes[v];
     }
 
-    // Start with retained size as shallow size.
-    var retainedSizes = new Uint32List.fromList(shallowSizes);
+    // Start with retained size as shallow size + external size.
+    var retainedSizes = new Uint32List(N + 1);
+    for (var i = 0; i < N + 1; i++) {
+      retainedSizes[i] = shallowSizes[i] + externalSizes[i];
+    }
 
     // In post order (bottom up), add retained size to dominator's retained
     // size, skipping root.
     for (var i = Nconnected; i > 1; i--) {
       var v = vertex[i];
       assert(v != ROOT);
       retainedSizes[doms[v]] += retainedSizes[v];
     }
 
-    assert(retainedSizes[ROOT] == size); // Root retains everything.
+    // Root retains everything.
+    assert(retainedSizes[ROOT] == (internalSize + externalSize));
 
     _retainedSizes = retainedSizes;
-    _size = size;
+    _internalSize = internalSize;
+    _externalSize = externalSize;
   }
 
   // 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);
 
     for (var child = ROOT; child <= N; child++) {
@@ skipping 138 matching lines @@
 
         // From all the siblings between child and after, take their children,
         // merge them and given to child.
         mergeChildrenAndSort(child, after);
 
         child = after;
       }
     }
   }
 }