Heap snapshot visualizations

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 9c9ad34aa4e1bfe018c8fca7b3d560664573df26..a616043bb55cb03a98548b978ed77da45cee3e3f 100644
--- a/runtime/observatory/lib/object_graph.dart
+++ b/runtime/observatory/lib/object_graph.dart
@@ -4,29 +4,45 @@
 
 library object_graph;
 
+import 'dart:async';
+import 'dart:collection';
 import 'dart:typed_data';
 
-import 'dominator_tree.dart';
+import 'package:logging/logging.dart';
 
 // Port of dart::ReadStream from vm/datastream.h.
-class ReadStream {
-  int _cur = 0;
-  final ByteData _data;
-  
-  ReadStream(this._data);
-  
-  int get pendingBytes => _data.lengthInBytes - _cur;
-  
+class _ReadStream {
+  int position = 0;
+  int _size = 0;
+  final List<ByteData> _chunks;
+
+  _ReadStream(this._chunks) {
+    int n = _chunks.length;
+    for (var i = 0; i < n; i++) {
+      var chunk = _chunks[i];
+      if (i + 1 != n) {
+        assert(chunk.lengthInBytes == (1 << 20));
+      }
+      _size += chunk.lengthInBytes;
+    }
+  }
+
+  int get pendingBytes => _size - position;
+
+  int getUint8(i) {
+    return _chunks[i >> 20].getUint8(i & 0xFFFFF);
+  }
+
   int readUnsigned() {
     int result = 0;
     int shift = 0;
-    while (_data.getUint8(_cur) <= maxUnsignedDataPerByte) {
-      result |= _data.getUint8(_cur) << shift;
+    while (getUint8(position) <= maxUnsignedDataPerByte) {
+      result |= getUint8(position) << shift;
       shift += dataBitsPerByte;
-      ++_cur;
+      position++;
     }
-    result |= (_data.getUint8(_cur) & byteMask) << shift;
-    ++_cur;
+    result |= (getUint8(position) & byteMask) << shift;
+    position++;
     return result;
   }
 
@@ -36,59 +52,138 @@ class ReadStream {
 }
 
 class ObjectVertex {
-  // Never null. The isolate root has id 0.
+  // 0 represents invalid/uninitialized, 1 is the root.
   final int _id;
-  bool get isRoot => _id == 0;
-  // TODO(koda): Include units in object graph metadata.
-  int addressForWordSize(int bytesPerWord) => _id * 2 * bytesPerWord;
-  // null for VM-heap objects.
-  int _shallowSize;
-  int get shallowSize => _shallowSize;
-  int _retainedSize;
-  int get retainedSize => _retainedSize;
-  // null for VM-heap objects.
-  int _classId;
-  int get classId => _classId;
-  final List<ObjectVertex> succ = new List<ObjectVertex>();
-  ObjectVertex(this._id) : _retainedSize = 0;
-  String toString() => '$_id,$_shallowSize,$succ';
-}
+  final ObjectGraph _graph;
 
-// See implementation of ObjectGraph::Serialize for format.
-class ObjectGraph {
-  final Map<int, ObjectVertex> _idToVertex = new Map<int, ObjectVertex>();
+  ObjectVertex._(this._id, this._graph);
+
+  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 {
+    var stream = new _ReadStream(_graph._chunks);
+    stream.position = _graph._positions[_id];
+    stream.readUnsigned(); // addr
+    return stream.readUnsigned(); // shallowSize
+  }
 
-  ObjectVertex _asVertex(int id) {
-    return _idToVertex.putIfAbsent(id, () => new ObjectVertex(id));
+  int get vmCid {
+    var stream = new _ReadStream(_graph._chunks);
+    stream.position = _graph._positions[_id];
+    stream.readUnsigned(); // addr
+    stream.readUnsigned(); // shallowSize
+    return stream.readUnsigned(); // cid
   }
 
-  void _addFrom(ReadStream stream) {
-    ObjectVertex obj = _asVertex(stream.readUnsigned());
-    obj._shallowSize = stream.readUnsigned();
-    obj._classId = stream.readUnsigned();
-    int last = stream.readUnsigned();
-    while (last != 0) {
-      obj.succ.add(_asVertex(last));
-      last = stream.readUnsigned();
+  get successors => new _SuccessorsIterable(_graph, _id);
+
+  int 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 stream = new _ReadStream(_graph._chunks);
+    stream.position = _graph._positions[_id];
+    var scaledAddr = stream.readUnsigned();
+    return scaledAddr * _graph._kObjectAlignment;
+  }
+
+  List<ObjectVertex> dominatorTreeChildren() {
+    var N = _graph._N;
+    var doms = _graph._doms;
+
+    var parentId = _id;
+    var domChildren = [];
+
+    for (var childId = 1; childId <= N; childId++) {
+      if (doms[childId] == parentId) {
+        domChildren.add(new ObjectVertex._(childId, _graph));
+      }
     }
+
+    return domChildren;
+  }
+}
+
+class _SuccessorsIterable extends IterableBase<ObjectVertex> {
+  final ObjectGraph _graph;
+  final int _id;
+
+  _SuccessorsIterable(this._graph, this._id);
+
+  Iterator<ObjectVertex> get iterator => new _SuccessorsIterator(_graph, _id);
+}
+
+class _SuccessorsIterator implements Iterator<ObjectVertex> {
+  final ObjectGraph _graph;
+  _ReadStream _stream;
+
+  ObjectVertex current;
+
+  _SuccessorsIterator(this._graph, int id) {
+    _stream = new _ReadStream(this._graph._chunks);
+    _stream.position = _graph._positions[id];
+    _stream.readUnsigned(); // addr
+    _stream.readUnsigned(); // shallowSize
+    var cid = _stream.readUnsigned();
+    assert((cid & ~0xFFFF) == 0); // Sanity check: cid's are 16 bit.
   }
 
-  ObjectGraph(ReadStream reader) {
-    while (reader.pendingBytes > 0) {
-      _addFrom(reader);
+  bool moveNext() {
+    while (true) {
+      var nextAddr = _stream.readUnsigned();
+      if (nextAddr == 0) return false;
+      var nextId = _graph._addrToId[nextAddr];
+      if (nextId == null) continue; // Reference to VM isolate's heap.
+      current = new ObjectVertex._(nextId, _graph);
+      return true;
     }
-    _computeRetainedSizes();
-    _mostRetained = new List<ObjectVertex>.from(
-        vertices.where((u) => !u.isRoot));
-    _mostRetained.sort((u, v) => v.retainedSize - u.retainedSize);
   }
+}
+
+class _VerticesIterable extends IterableBase<ObjectVertex> {
+  final ObjectGraph _graph;
+
+  _VerticesIterable(this._graph);
+
+  Iterator<ObjectVertex> get iterator => new _VerticesIterator(_graph);
+}
+
+class _VerticesIterator implements Iterator<ObjectVertex> {
+  final ObjectGraph _graph;
+
+  int _nextId = 0;
+  ObjectVertex current;
+
+  _VerticesIterator(this._graph);
+
+  bool moveNext() {
+    if (_nextId == _graph._N) return false;
+    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 vertexCount => _N;
+  int get edgeCount => _E;
 
-  Iterable<ObjectVertex> get vertices => _idToVertex.values;
-  List<ObjectVertex> _mostRetained;
+  ObjectVertex get root => new ObjectVertex._(1, this);
+  Iterable<ObjectVertex> get vertices => new _VerticesIterable(this);
 
-  ObjectVertex get root => _asVertex(0);
-  
   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.classId == classId);
@@ -98,41 +193,326 @@ class ObjectGraph {
     }
     return result;
   }
-  
-  void _computeRetainedSizes() {
-    // The retained size for an object is the sum of the shallow sizes of
-    // all its descendants in the dominator tree (including itself).
-    var d = new Dominator();
-    for (ObjectVertex u in vertices) {
-      if (u.shallowSize != null) {
-        u._retainedSize = u.shallowSize;
-        d.addEdges(u, u.succ.where((ObjectVertex v) => v.shallowSize != null));
+
+  Future process(statusReporter) async {
+    // We build futures here instead of marking the steps as async to avoid the
+    // heavy lifting being inside a transformed method.
+
+    statusReporter.add("Finding node positions...");
+    await new Future(() => _buildPositions());
+
+    statusReporter.add("Finding post order...");
+    await new Future(() => _buildPostOrder());
+
+    statusReporter.add("Finding predecessors...");
+    await new Future(() => _buildPredecessors());
+
+    statusReporter.add("Finding dominators...");
+    await new Future(() => _buildDominators());
+
+    _firstPreds = null;
+    _preds = null;
+    _postOrderIndices = null;
+
+    statusReporter.add("Finding retained sizes...");
+    await new Future(() => _calculateRetainedSizes());
+
+    _postOrderOrdinals = null;
+
+    statusReporter.add("Loaded");
+    return this;
+  }
+
+  final List<ByteData> _chunks;
+
+  int _kObjectAlignment;
+  int _N;
+  int _E;
+  int _size;
+
+  Map<int, int> _addrToId = new Map<int, int>();
+
+  // Indexed by node id, with id 0 representing invalid/uninitialized.
+  Uint32List _positions; // Position of the node in the snapshot.
+  Uint32List _postOrderOrdinals; // post-order index -> id
+  Uint32List _postOrderIndices; // id -> post-order index
+  Uint32List _firstPreds; // Offset into preds.
+  Uint32List _preds;
+  Uint32List _doms;
+  Uint32List _retainedSizes;
+
+  void _buildPositions() {
+    var N = _N;
+    var addrToId = _addrToId;
+
+    var positions = new Uint32List(N + 1);
+
+    var stream = new _ReadStream(_chunks);
+    _kObjectAlignment = stream.readUnsigned();
+
+    var id = 1;
+    while (stream.pendingBytes > 0) {
+      positions[id] = stream.position;
+      var addr = stream.readUnsigned();
+      var shallowSize = stream.readUnsigned();
+      var cid = stream.readUnsigned();
+      addrToId[addr] = id;
+
+      var succAddr = stream.readUnsigned();
+      while (succAddr != 0) {
+        succAddr = stream.readUnsigned();
+      }
+      id++;
+    }
+    assert(id == (N + 1));
+
+    var root = addrToId[0];
+    assert(root == 1);
+
+    _positions = positions;
+  }
+
+  void _buildPostOrder() {
+    var N = _N;
+    var E = 0;
+    var addrToId = _addrToId;
+    var positions = _positions;
+
+    var postOrderOrdinals = new Uint32List(N);
+    var postOrderIndices = new Uint32List(N + 1);
+    var stackNodes = new Uint32List(N);
+    var stackCurrentEdgePos = new Uint32List(N);
+
+    var visited = new Uint8List(N + 1);
+    var postOrderIndex = 0;
+    var stackTop = 0;
+    var root = 1;
+
+    stackNodes[0] = root;
+
+    var stream = new _ReadStream(_chunks);
+    stream.position = positions[root];
+    stream.readUnsigned(); // addr
+    stream.readUnsigned(); // shallowSize
+    stream.readUnsigned(); // cid
+    stackCurrentEdgePos[0] = stream.position;
+    visited[root] = 1;
+
+    while (stackTop >= 0) {
+      var n = stackNodes[stackTop];
+      var edgePos = stackCurrentEdgePos[stackTop];
+
+      stream.position = edgePos;
+      var childAddr = stream.readUnsigned();
+      if (childAddr != 0) {
+        stackCurrentEdgePos[stackTop] = stream.position;
+        var childId = addrToId[childAddr];
+        if (childId == null) continue; // Reference to VM isolate's heap.
+        E++;
+        if (visited[childId] == 1) continue;
+
+        stackTop++;
+        stackNodes[stackTop] = childId;
+
+        stream.position = positions[childId];
+        stream.readUnsigned(); // addr
+        stream.readUnsigned(); // shallowSize
+        stream.readUnsigned(); // cid
+        stackCurrentEdgePos[stackTop] = stream.position; // i.e., first edge
+        visited[childId] = 1;
+      } else {
+        // Done with all children.
+        postOrderIndices[n] = postOrderIndex;
+        postOrderOrdinals[postOrderIndex++] = n;
+        stackTop--;
       }
     }
-    d.computeDominatorTree(root);
-    // Compute all retained sizes "bottom up", starting from the leaves.
-    // Keep track of number of remaining children of each vertex.
-    var degree = new Map<ObjectVertex, int>();
-    for (ObjectVertex u in vertices) {
-      var v = d.dominator(u);
-      if (v != null) {
-        degree[v] = 1 + degree.putIfAbsent(v, () => 0);
+
+    assert(postOrderIndex == N);
+    assert(postOrderOrdinals[N - 1] == root);
+
+    _postOrderOrdinals = postOrderOrdinals;
+    _postOrderIndices = postOrderIndices;
+    _E = E;
+  }
+
+  void _buildPredecessors() {
+    var N = _N;
+    var E = _E;
+    var addrToId = _addrToId;
+    var positions = _positions;
+
+    // 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.
+    var stream = new _ReadStream(_chunks);
+    for (var i = 1; i <= N; i++) {
+      stream.position = positions[i];
+      stream.readUnsigned(); // addr
+      stream.readUnsigned(); // shallowSize
+      stream.readUnsigned(); // cid
+      var succAddr = stream.readUnsigned();
+      while (succAddr != 0) {
+        var succId = addrToId[succAddr];
+        if (succId != null) {
+          numPreds[succId]++;
+        } else {
+          // Reference to VM isolate's heap.
+        }
+        succAddr = stream.readUnsigned();
       }
     }
-    var leaves = new List<ObjectVertex>();
-    for (ObjectVertex u in vertices) {
-      if (!degree.containsKey(u)) {
-        leaves.add(u);
+
+    // 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.
+
+    // Fill predecessors array.
+    for (var i = 1; i <= N; i++) {
+      stream.position = positions[i];
+      stream.readUnsigned(); // addr
+      stream.readUnsigned(); // shallowSize
+      stream.readUnsigned(); // cid
+      var succAddr = stream.readUnsigned();
+      while (succAddr != 0) {
+        var succId = addrToId[succAddr];
+        if (succId != null) {
+          var predIndex = nextPreds[succId]++;
+          preds[predIndex] = i;
+        } else {
+          // Reference to VM isolate's heap.
+        }
+        succAddr = stream.readUnsigned();
       }
     }
-    while (!leaves.isEmpty) {
-      var v = leaves.removeLast();
-      var u = d.dominator(v);
-      if (u == null) continue;
-      u._retainedSize += v._retainedSize;
-      if (--degree[u] == 0) {
-        leaves.add(u);
+
+    _firstPreds = firstPreds;
+    _preds = preds;
+  }
+
+  // "A Simple, Fast Dominance Algorithm"
+  // Keith D. Cooper, Timothy J. Harvey, and Ken Kennedy
+  void _buildDominators() {
+    var N = _N;
+    var E = _E;
+    var addrToId = _addrToId;
+    var postOrder = _postOrderOrdinals;
+    var postOrderIndex = _postOrderIndices;
+    var firstPreds = _firstPreds;
+    var preds = _preds;
+
+    var root = 1;
+    var rootPostOrderIndex = postOrderIndex[root];
+    var domByPOI = new Uint32List(N + 1);
+
+    domByPOI[rootPostOrderIndex] = rootPostOrderIndex;
+
+    var iteration = 0;
+    var changed = true;
+    while (changed) {
+      changed = false;
+      Logger.root.info("Find dominators iteration $iteration");
+      iteration++; // dart2js heaps typically converge in 10 iterations.
+
+      // Visit the nodes, except the root, in reverse post order (top down).
+      for (var curPostOrderIndex = rootPostOrderIndex - 1;
+           curPostOrderIndex > 1;
+           curPostOrderIndex--) {
+        if (domByPOI[curPostOrderIndex] == rootPostOrderIndex)
+          continue;
+
+        var nodeOrdinal = postOrder[curPostOrderIndex];
+        var newDomIndex = 0; // 0 = undefined
+
+        // Intersect the DOM sets of the node's precedessors.
+        var beginPredIndex = firstPreds[nodeOrdinal];
+        var endPredIndex = firstPreds[nodeOrdinal + 1];
+        for (var predIndex = beginPredIndex;
+             predIndex < endPredIndex;
+             predIndex++) {
+          var predOrdinal = preds[predIndex];
+          var predPostOrderIndex = postOrderIndex[predOrdinal];
+          if (domByPOI[predPostOrderIndex] != 0) {
+            if (newDomIndex == 0) {
+              newDomIndex = predPostOrderIndex;
+            } else {
+              // Note this two finger algorithm to find the DOM intersection
+              // relies on comparing nodes by their post order index.
+              while (predPostOrderIndex != newDomIndex) {
+                while(predPostOrderIndex < newDomIndex)
+                  predPostOrderIndex = domByPOI[predPostOrderIndex];
+                while (newDomIndex < predPostOrderIndex)
+                  newDomIndex = domByPOI[newDomIndex];
+              }
+            }
+            if (newDomIndex == rootPostOrderIndex) {
+              break;
+            }
+          }
+        }
+        if (newDomIndex != 0 && domByPOI[curPostOrderIndex] != newDomIndex) {
+          domByPOI[curPostOrderIndex] = newDomIndex;
+          changed = true;
+        }
       }
     }
+
+    // Reindex doms by id instead of post order index so we can throw away
+    // the post order arrays.
+    var domById = new Uint32List(N + 1);
+    for (var id = 1; id <= N; id++) {
+      domById[id] = postOrder[domByPOI[postOrderIndex[id]]];
+    }
+
+    domById[root] = 0;
+
+    _doms = domById;
+  }
+
+  void _calculateRetainedSizes() {
+    var N = _N;
+    var E = _E;
+
+    var size = 0;
+    var positions = _positions;
+    var postOrderOrdinals = _postOrderOrdinals;
+    var doms = _doms;
+    var retainedSizes = new Uint32List(N + 1);
+
+    // Start with retained size as shallow size.
+    var reader = new _ReadStream(_chunks);
+    for (var i = 1; i <= N; i++) {
+      reader.position = positions[i];
+      reader.readUnsigned(); // addr
+      var shallowSize = reader.readUnsigned();
+      retainedSizes[i] = shallowSize;
+      size += shallowSize;
+    }
+
+    // In post order (bottom up), add retained size to dominator's retained
+    // size, skipping root.
+    for (var o = 0; o < (N - 1); o++) {
+      var i = postOrderOrdinals[o];
+      assert(i != 1);
+      retainedSizes[doms[i]] += retainedSizes[i];
+    }
+
+    _retainedSizes = retainedSizes;
+    _size = size;
   }
-}
+}