| // 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:typed_data'; |
| |
| import 'dominator_tree.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; |
| |
| int readUnsigned() { |
| int result = 0; |
| int shift = 0; |
| while (_data.getUint8(_cur) <= maxUnsignedDataPerByte) { |
| result |= _data.getUint8(_cur) << shift; |
| shift += dataBitsPerByte; |
| ++_cur; |
| } |
| result |= (_data.getUint8(_cur) & byteMask) << shift; |
| ++_cur; |
| return result; |
| } |
| |
| static const int dataBitsPerByte = 7; |
| static const int byteMask = (1 << dataBitsPerByte) - 1; |
| static const int maxUnsignedDataPerByte = byteMask; |
| } |
| |
| class ObjectVertex { |
| // Never null. The isolate root has id 0. |
| 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'; |
| } |
| |
| // See implementation of ObjectGraph::Serialize for format. |
| class ObjectGraph { |
| final Map<int, ObjectVertex> _idToVertex = new Map<int, ObjectVertex>(); |
| |
| ObjectVertex _asVertex(int id) { |
| return _idToVertex.putIfAbsent(id, () => new ObjectVertex(id)); |
| } |
| |
| 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(); |
| } |
| } |
| |
| ObjectGraph(ReadStream reader) { |
| while (reader.pendingBytes > 0) { |
| _addFrom(reader); |
| } |
| _computeRetainedSizes(); |
| _mostRetained = new List<ObjectVertex>.from( |
| vertices.where((u) => !u.isRoot)); |
| _mostRetained.sort((u, v) => v.retainedSize - u.retainedSize); |
| } |
| |
| Iterable<ObjectVertex> get vertices => _idToVertex.values; |
| List<ObjectVertex> _mostRetained; |
| |
| ObjectVertex get root => _asVertex(0); |
| |
| Iterable<ObjectVertex> getMostRetained({int classId, int limit}) { |
| var result = _mostRetained; |
| if (classId != null) { |
| result = result.where((u) => u.classId == classId); |
| } |
| if (limit != null) { |
| result = result.take(limit); |
| } |
| 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)); |
| } |
| } |
| 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); |
| } |
| } |
| var leaves = new List<ObjectVertex>(); |
| for (ObjectVertex u in vertices) { |
| if (!degree.containsKey(u)) { |
| leaves.add(u); |
| } |
| } |
| 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); |
| } |
| } |
| } |
| } |