marshal: add context argument to valToSlot/slotToVal

[warner]

What is the Problem Being Solved?

As @FUDCo is working on retiring the c-list entries for resolved promises (#1124 and PR #2110), we identified an enhancement to marshal that could make the liveslots code cleaner and less error-prone. The basic need is for a context argument, passed into m.serialize(value, context) and made available to each call to slot = valToSlot(val, context). Likewise, m.unserialize(data, context) and val = slotToVal(slot, context). Our use case would be better served by a separate context object for each act of serialization/unserialization than by having a single context object for the marshaller as a whole.

Our most concise example that motivates the problem is a pair of recursively-resolved promises:

const { pA: promise, rA: resolve } = makePromiseKit();
const { pB: promise, rB: resolve } = makePromiseKit();
rA([pB]);
rB([pA]);
alice~.foo(pA);

(there are minor differences depending upon wheter foo() is serialized before or after pA/pB's .then callbacks are fired, but the same problem arises in both cases)

Before Chip's work, when liveslots needs to serialize the arguments of foo(pA), it would get into an infinite loop, with the following steps:

• serialize the args = [pA]: allocate a new vpid for pA (call it pA.1), use pA.then() to register for its resolution, do syscall.send(foo, ... pA.1)
• since pA is already resolved, on the next turn (still in the same crank), the .then fires, and liveslots learns of the resolution data (i.e. [pB]). Liveslots serializes that, allocating a new vpid for pB (call it pB.1), and registering pB.then() to learn about its resolution. Liveslots then does syscall.resolve(pA.1, data=...pB.1).
  • at this point, our rules about "retire the identifiers for all resolved promises" kicks in: liveslots forgets pA.1, and the kernel deletes the c-list entry for pA.1
• on the next turn (still in the same crank), the pB .then fires, and liveslots learns of the pB resolution data (i.e. [pA]). Liveslots serializes that, but since we retired pA.1 and no longer recognize pA, liveslots must allocate a new identifier: call it pA.2. Liveslots attaches a new then, and does syscall.resolve(pB.1, data=...pA.2)
  • our rule kicks in again, and both liveslots and kernel forget about pB.1
• now the second pA.then fires, with data of [pB], which is unrecognized, so we allocate pB.2, etc
• the crank goes on forever, emitting a constant stream of mutually-recursive resolutions that never converges

The core problem was that we walk a cyclic graph one edge per turn, and forget each edge before the next turn can execute, so we don't have enough memory to handle the cycle.

Our fix is to defer retiring the identifiers until we've finished walking the graph. In our example (where the vat is initiating the resolution), we must add a WeakMap that remembers the data of resolved promises, so that we can walk the resolved subset of the graph in a single turn (note: we don't need to know that the promise is resolved per se, just whether liveslots has observed it to be resolved or not, so a WeakMap is sufficient). In addition, when liveslots reacts to a resolved exported Promise and walks the graph of its resolution, we build up a list of all the new promise identifiers that we've introduced (some of which might be resolved, while the rest are unresolved). We change syscall.resolve to accept a batch of resolutions, and change our rule about retiring c-list entries to run at the end of the batch. We may create some very short-lived promise identifiers: they'll be introduced, resolved, and retired, all in a single syscall.

The loop starts by serializing the one promise results whose .then has fired, creating a capdata and a list of newly-introduced promises. Once that first promise is handled, we scan the list to find any which are already known to be resolved. We then serialize the results of that one, possibly adding to our list. We keep going until there are no more already-resolved promises in our list. Then we build a batch syscall.resolve that contains all of them. After executing this syscall, we retire the liveslots table entries for every identifier the syscall resolved.

This will convert our mutually-recursive example (assuming liveslots has not yet seen either promise) to:

• serialize the args = [pA]: allocate a new vpid for pA (call it pA.1), use pA.then() to register for its resolution, and do syscall.send(foo, ... pA.1)
• since pA is already resolved, on the next turn (still in the same crank), the .then fires, and liveslots learns of the resolution data (i.e. [pB]). We first record pA -> [pB] in the WeakMap. Then liveslots serializes [pB], allocating a new vpid for pB (call it pB.1), and registering pB.then() to learn about its resolution. The "list of introduced promises" includes pB, but pB is not yet known to be resolved, so the syscall.resolve([ [pA.1, [pB.1]] ]) call only resolves a single promise. We retire pA.1 as usual.
• on the next turn (still in the same crank), the pB .then fires, and liveslots learns of the pB resolution data (i.e. [pA]) and stashes pB -> [pA] in the WeakMap. Liveslots serializes [pA], but since we retired pA.1 and no longer recognize pA, liveslots must allocate a new identifier: call it pA.2. The first serialization's "list of introduced promises" contains pA, which now we do recognize as being resolved. So liveslots re-serializes pA's resolution data ([pB]). We haven't retired pB.1 yet (we're still serializing), so the serialized data gets to reference pB.1, closing the cycle. Liveslots does a batch-size=2 syscall.resolve([ [pB.1, [pA.2]], [pA.2, [pB.1]] ]). When this is done, liveslots retires both pB.1 and pA.2, as does the kernel.
• the cycle stops

(if liveslots happened to see pA earlier, it wouldn't need to allocate pA.2)

A similar process will happen when it is the kernel that resolves a batch of promises in a single delivery. The kernel has the full capdata.slots list available immediately, so the task of building the bundle is much easier. When liveslots receives the dispatch.notify(promisesAndResolutions), it must unserialize each one in turn, which may create new Promise objects, some of which may be resolved by other elements of the bundle (and the rest remain unresolved until some future delivery). Liveslots needs to syscall.subscribe() to only the unresolved remnants. So we need a way for unserialization to accumulate a list of promise identifiers that were encountered during the revival process, so we can filter it into the resolved and the unresolved.

Context object via serialize/unserialize wrapper

So we need a way for liveslot's use of serialize and unserialize to accumulate a list of things (promises and/or promise identifiers) encountered by the valToSlot and slotToVal callbacks. Our initial implementation will introduce an accumulator array, closed over (and appended to) by both valToSlot and slotToVal. When liveslots is about to call serialize, it will assert that this accumulator is empty. After serialize is done, it will retrieve (and clear) the array. It will do the same for unserialize.

The risk of this "dynamic scope" approach is that any accidental recursion (valToSlot calling serialize again: unlikely but conceivable) would corrupt this single/shared array. Plus, it introduces some unnecessary coupling between parts of liveslots.

Context object as part of marshal

If serialize() accepted an extra context argument, liveslots could pass a new mutable array in. Then valToSlot(val, context) would append the introduced promise with context.push(p) instead of closing over something from a higher scope.

Description of the Design

• serialize(val) becomes serialize(val, context)
• valToSlot(val) becomes valToSlot(val, context)
• unserialize(data) becomes unserialize(data, context)
• slotToVal(slot) becomes slotToVal(slot, context)

There are probably other ways to approach this. We could decide that a completely generic context object is unnecessary if we really only need to accumulate an array. In that case, we could let valToSlot() return an additional list of things to append to the list, and have marshal manage the list:

• { data, list } = serialize(val)
• { slot, list } = valToSlot(val)
• { val, list } = unserialize(data)
• { val, list } = slotToVal(slot)

We might be uncomfortable with passing a mutable array into a function (harden all the things!), in which case we'd need to build an append-only facet object in as the context.

Security Considerations

I don't think this introduces any. The caller of marshal already gets to provide slotToVal and valToSlot. And the fact that we can implement similar functionality (less safely) via closed-over accumulator variables suggests that this change would not introduce any additional authority.

Test Plan

Regular unit tests.

[warner]

Alternate Approaches

In reviewing this writeup, I'm now wondering if it's possible that we could implement this entirely by scanning the slots portion of the capdata after serialize, or before unserialize.

During serialize, the graph traversal will encounter Promises that may or may not be in the liveslots tables. If they are present, they're probably unresolved (since we retire everything as soon as we learn about their resolution). If they aren't yet in the table, they might be resolved. If so, they'll be in the WeakMap, and the outer loop should spot them and add them to the resolution bundle we're creating, so they'll be removed from the table before the turn ends.

For this latter category, we need to not add a .then (we're handling the resolution in this turn, and we notify the kernel twice for the same promise). We could do the following (without an accumulator or context argument):

• valToSlot (specifically exportPromise) would not add a .then
• all code which calls serialize would need to examine the capdata.slots that results
  • for each type = promise identifier in the list, use the slotToVal table to look up the corresponding Promise object
  • if that Promise is in the WeakMap, push it onto the list for the batch
  • if not, check a (new?) table that remembers if we've already added a .then
    • if it isn't in that table, add it to the table, and attach a .then

Similarly, we could scan the capdata.slots list before submitting that capdata to unserialize, to get a list of promise identifiers that will be referenced by the unserialized result. This would give us the same information as an accumulator or context argument would provide.

Let's keep discussing this, but hold off on implementing the marshal-side feature until we decide which approach would be simplest overall.

[warner]

cc @erights

[FUDCo]

The alternate approach outlined seems more complicated to me, because it relies on inference rather than direct observation of what was done. It buys avoidance of modification to the marshal API at the cost of a significantly trickier analytical phase.

[erights]

@FUDCo @warner is this still relevant? Can we close this?