xsnap + SES boot not deterministic

[dckc]

Describe the bug

xsnap produces deterministic snapshots on simple examples (including weakmaps since Moddable-OpenSource/moddable#564 was fixed) but on the SES lockdown bootstrap we use, snapshots vary between evaluations.

I can't say for certain that this is an xsnap bug yet; the problem could be in our 6200+ line SES bootstrap code somewhere.

To Reproduce

1. check out moddable rev 7abc931d Mar 19 and set $MODDABLE to that dir
2. build the original xsnap as usual (Feb 12 8b127bce95cd git@github.com:Moddable-OpenSource/agoric.git )
3. run ses-boot and take a snapshot (see below) and note the sha256sum
4. repeat step 3
5. note the checksums are different

bundle-ses-boot.umd.js is available in https://gist.github.com/dckc/bba5b752d8176cbb9777fcc5c0bd916a

xsnap$ ./makefiles/lin/bin/lin/release/xsnap bundle-ses-boot.umd.js -w out.xss
Removing intrinsics.%ArrayPrototype%.reverse.@@
Removing intrinsics.%ArrayPrototype%.sort.@@
connolly@jambox:~/projects/xs-snap/xsnap$ sha256sum out.xss 
7783723c37edee90d10618ea82f7b1b70c61d79920b38f3ec0efabb1c80da842  out.xss
xsnap$ ./makefiles/lin/bin/lin/release/xsnap bundle-ses-boot.umd.js -w out.xss
Removing intrinsics.%ArrayPrototype%.reverse.@@
Removing intrinsics.%ArrayPrototype%.sort.@@
connolly@jambox:~/projects/xs-snap/xsnap$ sha256sum out.xss 
e621b525dc314507a4996f4ec2c4cb72f7622a8a808f3b6f0fd4f46f3a418b3e  out.xss

Expected behavior

same snapshot

cc @warner @kriskowal @erights @michaelfig @phoddie

[kriskowal]

@dckc My understanding from conversations with @erights and @warner is that we expect deterministic JS execution from xsnapshots, but not binary identical snapshot files. I had come from the expectation that we’d be able to disseminate snapshots through a content address store among validators, but that appears to be a non-goal. That said, I would be unspeakably elated if snapshot binaries had consistent hashes.

[dckc]

@phoddie , after discussion with @warner , @erights , and @kriskowal , we don't think bundle-ses-boot.umd.js is doing anything that should cause problems with snapshots. It's not, for example, calling Math.random. And with mxTrace turned on, the trace does not vary.

Is it straightforward for you to reproduce this problem? That is: does xsnap produce different snapshots for you?

If so, is it straightforward for you to tell why the snapshots are different?

Once again, for reference:
bundle-ses-boot.umd.js is available in https://gist.github.com/dckc/bba5b752d8176cbb9777fcc5c0bd916a

It's possible that we can do a sort of binary search thru bundle-ses-boot.umd.js to reduce the size of the input that triggers the bug by putting return statements at various places.

p.s. re Math.random: SES turns that off, but even before that, we could / should provide a consistently seeded PRNG in our XS platform.

[erights]

We can also send you two snapshots that differ but should have been the same. Would that be useful?

[phoddie]

Our goal has been what @kriskowal describes: to have the hashes match. We always expected some challenges along the way. For example, the snapshot code works to avoid writing uninitialized values into a snapshot.

The recent changes to fix non-determinism in the snapshots for maps/sets was not because of uninitialized values. It was because some values changed depending on where in the address space the host operating system loaded the executable. The snapshot doesn't contain pointers, but it had hashes the included the address. (The snapshots were logically equivalent, but not identical data.)

The interesting thing was that sometimes the macOS would load the executable at the same address, and in those cases the hash of the snapshot matched. In this case, is there a mismatch each time you generate the snapshot or only some? If the latter, may be you can trace a C function address at the start of xsnap to know if your snapshot is loaded at the same address to see if there is an address dependency.

To the degree it is practical for you to simplify a test case that shows the problem, that will be helpful for us in looking into this further.

FWIW - we don't have tools to dump a snapshot yet. At some point that is likely to be necessary.

[dckc]

... It's possible that we can do a sort of binary search thru bundle-ses-boot.umd.js to reduce the size of the input that triggers the bug by putting return statements at various places.

Unfortunately, this only shrinks the input by 1 line.

There's a call to lockdown(); on line 6202. If I put a return anywhere before that, the snapshot is deterministic. But if I move the return after that, snapshots vary.

[dckc]

within the call to lockdown() I narrowed it down somewhat...

If I add a return; before this part of function whitelistProperties(), snapshots are consistent. If I move it after, they vary.

        if (subPermit) {
          // Property has a permit.
          if (isWhitelistProperty(subPath, obj, prop, subPermit)) {
            // Property is whitelisted.
            // eslint-disable-next-line no-continue
            continue;
          }
        }

https://gist.github.com/dckc/bba5b752d8176cbb9777fcc5c0bd916a#file-bundle-ses-boot-umd-js-L2682-L2689

[dckc]

Array.prototype.reverse and Array.prototype.sort look odd with xsnap (vs xst):

const info = Object.getOwnPropertyDescriptors(Array.prototype.reverse);
print('@@@array stuff', JSON.stringify(info));
      
const xx = Reflect.ownKeys(info).map(x => typeof x);
print('@@@@', JSON.stringify(xx));

const info2 = Reflect.ownKeys(Array.prototype.reverse);
print('@@@array stuff2', JSON.stringify(info2.map(x => typeof x)));

note the extra symbol under xsnap:

connolly@jambox:~/projects/xs-snap/xsnap$ xst arrayOdd.js
@@@array stuff {"length":{"value":0,"writable":false,"enumerable":false,"configurable":true},"name":{"value":"reverse","writable":false,"enumerable":false,"configurable":true}}
@@@@ ["string","string"]
@@@array stuff2 ["string","string"]


connolly@jambox:~/projects/xs-snap/xsnap$ ./makefiles/lin/bin/lin/debug/xsnap arrayOdd.js
@@@array stuff {"length":{"value":0,"writable":false,"enumerable":false,"configurable":true},"name":{"value":"reverse","writable":false,"enumerable":false,"configurable":true}}
@@@@ ["string","string","symbol"]
@@@array stuff2 ["string","string","symbol"]

[dckc]

(Object(val) !== val fails on this odd symbol attached to Array.prototype.reverse:

.../bundle-ses-boot.umd.js:2421: exception: Object: cannot coerce to instance: 18!

[dckc]

the Array.prototype.reverse stuff is probably a red herring related to metering.