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

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 00355803aa7818925f2d804e417a1e031895d59a..5dca93173423b0a1e72d409501b577dd2635a05f 100644
--- a/runtime/observatory/lib/object_graph.dart
+++ b/runtime/observatory/lib/object_graph.dart
@@ -10,6 +10,65 @@ 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;
@@ -33,17 +92,102 @@ class _ReadStream {
     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;
@@ -69,28 +213,50 @@ class ObjectVertex {
   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() {
@@ -128,17 +294,16 @@ class _SuccessorsIterator implements Iterator<ObjectVertex> {
   _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;
@@ -232,7 +397,7 @@ class ObjectGraph {
   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.
@@ -245,32 +410,34 @@ class ObjectGraph {
 
   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;
-
-      var succAddr = stream.readUnsigned();
-      while (succAddr != 0) {
-        succAddr = stream.readUnsigned();
+      stream.readUnsigned(); // addr
+      addrToId.put(stream.high, stream.mid, stream.low, id);
+      stream.skipUnsigned(); // shallowSize
+      stream.skipUnsigned(); // cid
+
+      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;
   }
 
@@ -294,9 +461,9 @@ class ObjectGraph {
 
     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;
 
@@ -305,10 +472,10 @@ class ObjectGraph {
       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;
@@ -317,9 +484,9 @@ class ObjectGraph {
         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 {
@@ -356,18 +523,18 @@ class ObjectGraph {
     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
       }
     }
 
@@ -387,19 +554,19 @@ class ObjectGraph {
     // 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
       }
     }
 
@@ -498,8 +665,9 @@ class ObjectGraph {
     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;
     }