Deal with Javascript integer limitations in heap snapshot processing to handle 64-bit target VMs.

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';
 
+// Map<[uint32, uint32, uint32], uint32>
+class AddressMapper {
+  final Uint32List _table;
+
+  // * 4 ~/3 for 75% load factor
+  // * 4 for four-tuple entries
+  AddressMapper(int N) : _table = new Uint32List((N * 4 ~/ 3) * 4);
+
+  // Jenkin's smi hash.
+  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);
+    return 0x1fffffff & (hash + ((0x00003fff & hash) << 15));
+  }
+
+  static int hash3(a, b, c) => finish(combine(combine(combine(0, a), b), c));
+
+  int scanFor(int high, int mid, int low) {
+    var hash = hash3(high, mid, low);
+    var start = (hash % _table.length) & ~3;
+    var index = start;
+    do {
+      if (_table[index + 3] == 0) return index;
+      if (_table[index] == high &&
+          _table[index + 1] == mid &&
+          _table[index + 2] == low) return index;
+      index = (index + 4) % _table.length;
+    } while (index != start);
+
+    throw new Exception("Interal error: table full");
+  }
+
+  int get(int high, int mid, int low) {
+    int index = scanFor(high, mid, low);
+    if (_table[index + 3] == 0) return null;
+    return _table[index + 3];
+  }
+
+  int put(int high, int mid, int low, int id) {
+    if (id == 0) throw new Exception("Invalid error: invalid key");
+
+    int index = scanFor(high, mid, low);
+    if ((_table[index + 3] != 0)) {
+      throw new Exception("Internal error: attempt to overwrite key");
+    }
+    _table[index] = high;
+    _table[index + 1] = mid;
+    _table[index + 2] = low;
+    _table[index + 3] = id;
+  }
+}
+
+
 // Port of dart::ReadStream from vm/datastream.h.
 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 (getUint8(position) <= maxUnsignedDataPerByte) {
-      result |= getUint8(position) << shift;
-      shift += dataBitsPerByte;
-      position++;
+  int low = 0;
+  int mid = 0;
+  int high = 0;
+
+  int get smallValue {
+    assert(high == 0);
+    assert(mid == 0);
+    return (high << 56) | (mid << 28) | low;

[sra1, 2015/07/01 17:09:33]

why do this when they are zero?

You can get correct values up to 2^53 if you multiply and add instead of shift
and or.

return low + 0x10000000 * mid;

<< 56 doesn't work on dart2js since bit ops are 32 bit.
I think it is optimized to 0, but I'm not sure.

[rmacnak, 2015/07/07 23:19:05]

The intent was to still allow large values on Dartium. But we need to fit in
uint32 for typed arrays even on Dartium in a few places, so replaced with
clampedUint32. Using multiplication to get that last bit.

+  }
+
+  bool get isZero {
+    return (high == 0) && (mid == 0) && (low == 0);
+  }
+
+  void readUnsigned() {
+    low = 0;
+    mid = 0;
+    high = 0;
+
+    // Low 28 bits.
+    var digit = getUint8(position++);
+    if (digit > maxUnsignedDataPerByte) {
+      low |= (digit & byteMask << 0);
+      return;
     }
-    result |= (getUint8(position) & byteMask) << shift;
-    position++;
-    return result;
+    low |= (digit << 0);
+
+    digit = getUint8(position++);
+    if (digit > maxUnsignedDataPerByte) {
+      low |= ((digit & byteMask) << 7);
+      return;
+    }
+    low |= (digit << 7);
+
+    digit = getUint8(position++);
+    if (digit > maxUnsignedDataPerByte) {
+      low |= ((digit & byteMask) << 14);
+      return;
+    }
+    low |= (digit << 14);
+
+    digit = getUint8(position++);
+    if (digit > maxUnsignedDataPerByte) {
+      low |= ((digit & byteMask) << 21);
+      return;
+    }
+    low |= (digit << 21);
+
+    // Mid 28 bits.
+    digit = getUint8(position++);
+    if (digit > maxUnsignedDataPerByte) {
+      mid |= (digit & byteMask << 0);
+      return;
+    }
+    mid |= (digit << 0);
+
+    digit = getUint8(position++);
+    if (digit > maxUnsignedDataPerByte) {
+      mid |= ((digit & byteMask) << 7);
+      return;
+    }
+    mid |= (digit << 7);
+
+    digit = getUint8(position++);
+    if (digit > maxUnsignedDataPerByte) {
+      mid |= ((digit & byteMask) << 14);
+      return;
+    }
+    mid |= (digit << 14);
+
+    digit = getUint8(position++);
+    if (digit > maxUnsignedDataPerByte) {
+      mid |= ((digit & byteMask) << 21);
+      return;
+    }
+    mid |= (digit << 21);
+
+    // High 28 bits.
+    digit = getUint8(position++);
+    if (digit > maxUnsignedDataPerByte) {
+      high |= (digit & byteMask << 0);
+      return;
+    }
+    high |= (digit << 0);
+
+    digit = getUint8(position++);
+    if (digit > maxUnsignedDataPerByte) {
+      high |= ((digit & byteMask) << 7);
+      return;
+    }
+    high |= (digit << 7);
+    throw new Exception("Format error: snapshot field exceeds 64 bits");
+  }
+
+  void skipUnsigned() {
+    while (getUint8(position++) <= maxUnsignedDataPerByte);
   }
 
   static const int dataBitsPerByte = 7;
   static const int byteMask = (1 << dataBitsPerByte) - 1;
   static const int maxUnsignedDataPerByte = byteMask;
 }
 
 class ObjectVertex {
   // 0 represents invalid/uninitialized, 1 is the root.
   final int _id;
   final ObjectGraph _graph;
 
   ObjectVertex._(this._id, this._graph);
 
   bool get isRoot => _id == 1;
 
   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
+    stream.skipUnsigned(); // addr
+    stream.readUnsigned(); // shallowSize
+    return stream.smallValue;
   }
 
   int get vmCid {
     var stream = new _ReadStream(_graph._chunks);
     stream.position = _graph._positions[_id];
-    stream.readUnsigned(); // addr
-    stream.readUnsigned(); // shallowSize
-    return stream.readUnsigned(); // cid
+    stream.skipUnsigned(); // addr
+    stream.skipUnsigned(); // shallowSize
+    stream.readUnsigned(); // cid
+    return stream.smallValue;
   }
 
   get successors => new _SuccessorsIterable(_graph, _id);
 
-  int get address {
+  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 stream = new _ReadStream(_graph._chunks);
     stream.position = _graph._positions[_id];
-    var scaledAddr = stream.readUnsigned();
-    return scaledAddr * _graph._kObjectAlignment;
+    stream.readUnsigned();
+
+    // Complicated way to do (high:mid:low * _kObjectAlignment).toHexString()
+    // without intermediate values exceeding int32.
+
+    var strAddr = "";
+    var carry = 0;
+    combine4(nibble) {
+      nibble = nibble * _graph._kObjectAlignment + carry;
+      carry = nibble >> 4;
+      nibble = nibble & 0xF;
+      strAddr = nibble.toRadixString(16) + strAddr;
+    }
+    combine28(twentyEightBits) {
+      for (int shift = 0; shift < 28; shift += 4) {
+        combine4((twentyEightBits >> shift) & 0xF);
+      }
+    }
+    combine28(stream.low);
+    combine28(stream.mid);
+    combine28(stream.high);

[sra1, 2015/07/01 17:09:33]

A trick which probably runs faster in dart2js is

(1) premultiply

int high = stream.high;
int mid = stream.mid;
int low = stream.low;
int multiplier = _graph._kObjectAlignment;

low = multiplier * low;
mid = multiplier * mid + (low >> 28);
high = multiplier * high + (mid >> 28);
low = 0xFFFFFFF & low;
mid = 0xFFFFFFF & mid;

(2) Chunked hex conversion

if (high == 0 && mid == 0) return low.toRadixString(16);
String lowDigits = (low + 0x10000000).toRadixString(16).substring(1);
if (high == 0) return mid.toString(16) + lowDigits;
String midDigits = (mid + 0x10000000).toRadixString(16).substring(1);
return high.toRadixString(16) + midDigits + lowDigits;


The above will work better by avoiding non-smi intermediates in the premultiply
if you arrange that low/mid/high are 24/24/16 or 20/20/24 rather than 28/28/8.
It might even be necessary for the shift that computes the carry since that is
32 bit arithmetic on JS.

pkg/fixnum/lib/src/int64.dart is full of this kind of hackery.

[rmacnak, 2015/07/07 23:19:05]

The hot path is the use of readUnsigned parsing the snapshot, which dictates the
28/28/8 representation. This getter will only run for a hundred or so objects
compared to hundreds of thousands for parsing, so it's worth a slow down here.
But thanks for the tip.

+    return strAddr;
   }
 
   List<ObjectVertex> dominatorTreeChildren() {
     var N = _graph._N;
     var doms = _graph._doms;
 
     var parentId = _id;
     var domChildren = [];
 
     for (var childId = 1; childId <= N; childId++) {
@@ skipping 17 matching lines @@
 
 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.
+    _stream.skipUnsigned(); // addr
+    _stream.skipUnsigned(); // shallowSize
+    _stream.skipUnsigned(); // cid
   }
 
   bool moveNext() {
     while (true) {
-      var nextAddr = _stream.readUnsigned();
-      if (nextAddr == 0) return false;
-      var nextId = _graph._addrToId[nextAddr];
+      _stream.readUnsigned();
+      if (_stream.isZero) return false;
+      var nextId = _graph._addrToId.get(_stream.high, _stream.mid, _stream.low);
       if (nextId == null) continue; // Reference to VM isolate's heap.
       current = new ObjectVertex._(nextId, _graph);
       return true;
     }
   }
 }
 
 class _VerticesIterable extends IterableBase<ObjectVertex> {
   final ObjectGraph _graph;
 
@@ skipping 73 matching lines @@
     return this;
   }
 
   final List<ByteData> _chunks;
 
   int _kObjectAlignment;
   int _N;
   int _E;
   int _size;
 
-  Map<int, int> _addrToId = new Map<int, int>();
+  AddressMapper _addrToId;
 
   // 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 addrToId = new AddressMapper(N);
 
     var positions = new Uint32List(N + 1);
 
     var stream = new _ReadStream(_chunks);
-    _kObjectAlignment = stream.readUnsigned();
+    stream.readUnsigned();
+    _kObjectAlignment = stream.smallValue;
 
     var id = 1;
     while (stream.pendingBytes > 0) {
       positions[id] = stream.position;
-      var addr = stream.readUnsigned();
-      stream.readUnsigned(); // shallowSize
-      stream.readUnsigned(); // cid
-      addrToId[addr] = id;
+      stream.readUnsigned(); // addr
+      addrToId.put(stream.high, stream.mid, stream.low, id);
+      stream.skipUnsigned(); // shallowSize
+      stream.skipUnsigned(); // cid
 
-      var succAddr = stream.readUnsigned();
-      while (succAddr != 0) {
-        succAddr = stream.readUnsigned();
+      stream.readUnsigned();
+      while (!stream.isZero) {
+        stream.readUnsigned();
       }
       id++;
     }
     assert(id == (N + 1));
 
-    var root = addrToId[0];
+    var root = addrToId.get(0, 0, 0);
     assert(root == 1);
 
+    _addrToId = addrToId;
     _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
+    stream.skipUnsigned(); // addr
+    stream.skipUnsigned(); // shallowSize
+    stream.skipUnsigned(); // 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) {
+      stream.readUnsigned();  // childAddr
+      if (!stream.isZero) {
         stackCurrentEdgePos[stackTop] = stream.position;
-        var childId = addrToId[childAddr];
+        var childId = addrToId.get(stream.high, stream.mid, stream.low);
         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
+        stream.skipUnsigned(); // addr
+        stream.skipUnsigned(); // shallowSize
+        stream.skipUnsigned(); // cid
         stackCurrentEdgePos[stackTop] = stream.position; // i.e., first edge
         visited[childId] = 1;
       } else {
         // Done with all children.
         postOrderIndices[n] = postOrderIndex;
         postOrderOrdinals[postOrderIndex++] = n;
         stackTop--;
       }
     }
 
@@ skipping 16 matching lines @@
     // + 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];
+      stream.skipUnsigned(); // addr
+      stream.skipUnsigned(); // shallowSize
+      stream.skipUnsigned(); // cid
+      stream.readUnsigned(); // succAddr
+      while (!stream.isZero) {
+        var succId = addrToId.get(stream.high, stream.mid, stream.low);
         if (succId != null) {
           numPreds[succId]++;
         } else {
           // Reference to VM isolate's heap.
         }
-        succAddr = stream.readUnsigned();
+        stream.readUnsigned(); // succAddr
       }
     }
 
     // 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];
+      stream.skipUnsigned(); // addr
+      stream.skipUnsigned(); // shallowSize
+      stream.skipUnsigned(); // cid
+      stream.readUnsigned(); // succAddr
+      while (!stream.isZero) {
+        var succId = addrToId.get(stream.high, stream.mid, stream.low);
         if (succId != null) {
           var predIndex = nextPreds[succId]++;
           preds[predIndex] = i;
         } else {
           // Reference to VM isolate's heap.
         }
-        succAddr = stream.readUnsigned();
+        stream.readUnsigned(); // succAddr
       }
     }
 
     _firstPreds = firstPreds;
     _preds = preds;
   }
 
   // "A Simple, Fast Dominance Algorithm"
   // Keith D. Cooper, Timothy J. Harvey, and Ken Kennedy
   void _buildDominators() {
@@ skipping 78 matching lines @@
     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();
+      reader.skipUnsigned(); // addr
+      reader.readUnsigned(); // shallowSize
+      var shallowSize = reader.smallValue;
       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;
   }
 }