Per vat priority (was: two run queues)

[warner]

What is the Problem Being Solved?

As a baby step towards #23, we're going to start with a simple two-level (high-priority + low-priority) scheduler. Combined with per-vat queues (#5025), this should provide a starting point to enable high priority processing of economy elements (#4318).

Description of the Design

Vats will be marked with a priority, either low or high.

The scheduler used by controller.step()/controller.run() will then process the active vats with high priority before considering vats with lower priority. To ensure that high priority processing doesn't starve low priority work, the scheduler may occasionally pick a low priority vat.

At first all vats will be created with the same priority. A later change will enable vats with different priorities.

[warner]

In today's kernel meeting, we figured that a good starting point would be to have vat-zoe, the AMM vat, and the Treasury vat be marked "high priority", and have everything else use the default. (Maybe the oracle vat needs to be high-priority too). The most important activity to prioritize is topping up a Vault (to reduce the risk of default and liquidation).. effectively anything that adds liquidity to the system is worth prioritizing over anything else.

@dtribble pointed out that a lot of recent DEX rollouts have left users asking the question "what is the status of my trade?", and that this could provoke some interesting engineering goals. So one thought is:

• when the Mailbox device receives messages from the outside world, it also accepts a "transaction ID" argument
• we augment the run-queue to include a "txnID" next to each queued item
• when a delivery occurs, any syscalls it provokes are also tagged with this txnID (unless overridden by some future mechanism)
• we copy the run-queue into the merklized cosmos state vector, or at least the sorted list of txnIDs and maybe some notion of their scheduling properties
  • ideally enough information to let an outsider predict when the item will run
• wallets will remember the txnID of their signed cosmos message when they first post it
• clients could do an RPC query to fetch this list, and show users a sort of queue diagram, with their txnID-tagged entries close or far from the top
• users watch their deliveries bubble up in this diagram to get a sense for how long it will take until their trade is complete

Later, we'd give e.g. the AMM contract a way to distinguish between the ACK it sends back when the trade is complete (which runs on the user's txnID) from the price-change signal it sends to any subscribers (which, while caused by the user's action, is not really a part of it, and should be given a distinct txnID, or none at all).

The txnID used for tracing causality is closely related to the handle we'd use to decide scheduling. Any messages on the run-queue with the same txnID should be using the same escalator, and drawing priority payments from the same account. It's not clear how we'd choose these scheduling parameters on the way in, but at this this hints at the datatypes we should be using to track them.

We also discussed the idea that external parties should be able to pay to increase the escalator slope of existing messages, maybe just given the handle visible in the run-queue. This could be a separate type of cosmos message, which is delivered to swingset but not added to the run-queue.

[dckc]

Does this design preserve order among messages successively sent on a single reference?

[dckc]

This didn't make the metering phase.

[warner]

@mhofman and I came up with more of a plan yesterday:

• objects have priority, subscriptions have priority, promises do not
  • the kernel object table (which current maps koid to ownerVatID) expands to include priority and messageQueue
  • instead of kvStore.runQueue, we have an ordered list of priority queues (initially just high and low)
    • the kernel services the entire high priority queue before looking at low
  • each priority queue contains a nominally-unordered set of "active targets": these are object IDs (which have a non-empty messageQueue) and (kpid, vatID) subscription records
• the kernel picks an active target from the top-most non-empty priority queue
  • this selection is allowed to be pseudo-random (we do not guarantee anything about ordering beyond the FIFO-per-object nature of .messageQueue), and could be driven by scheduler policy / computron usage / anti-thrashing policy / etc
  • if the active target is a subscription, the kernel does a dispatch.notify to the given vat
  • if the active target is an object, the kernel pops the first message off kernelObjects[koid].messageQueue and does a dispatch.deliver to the owner vat
    • the scheduler policy might prefer multiple messages for a single object before switching to a different object
  • (this requires syscall.send to resolved promise should run-queue to object, not to promise #4542 so that all active targets are objects, never a promise)
  • each delivery has a "delivery priority" which matches the priority queue from which the target was taken
• syscall.send(newtarget) gets the priority of the new target
• syscall.subscribe() inherits the priority of the delivery
  • so inside userspace, the code before and after an await runs at the same priority, and the notify that will satisfy the await will be delivered at that same priority
• "priority collapse" is when everything winds up converging to use the same priority because there aren't enough ways to control (reduce) the selected priority
  • exported objects (new vrefs that appear in syscall.send or .resolve arguments) are assigned the lowest priority
  • but vats can use syscall.elevate(object-ids, new-priority) to raise them back up
    • limited to the delivery priority
    • ALTERNATIVE: make vats pre-register their exports with syscall.export(vref, priority) before they're allowed to appear in syscall.send / syscall.resolve. Not sure I like this.
    • using syscall.elevate() means we don't need to mess with the serialization format to include priority in the capdata
    • and it means there's nothing special about the first export (e.g. "priority can only be set on first export", or "priority included in second export must match that of the first")
• vatAdminService.createVat(bundlecap, { rootObjectPriority }) to set the priority of the new root object

We explored, but didn't find a satisfactory answer for, the question of how userspace should express priority preferences.

• each delivery happens at a given priority, but we weren't sure if userspace ought to learn this priority
  • if it should, then vatPowers.getCurrentPriority() seemed the most likely
• Far(iface, obj, { priority }) wouldn't be a bad API to specify the desired priority, but implementation would entangle marshal with liveslots in a bad way
  • the priority option could be a number, but ocap style suggests it ought to be an object, which represents the authority to create a high-priority object
  • maybe highPriority = vatPowers.getPriority('high'), and then Far(iface, obj, { priority: highPriority })
• the marshal entanglement could be avoided with a liveslots-provided marking function
  • maybe prioritizer = vatPowers.makePrioritizer('high')
  • then obj = prioritizer(Far(iface, obj))
• in the two-queues era, priorities of 'high' / 'low' or 1 / 0 might make sense, but in the long run we want to think about esclators and arbitrarily-many priority queues, which might not even be totally ordered
  • so priority-as-object seems bettter, but userspace still needs to know what its options are, and why it might choose one over another
• limiting the syscall.elevate() to the current delivery priority is a simple way to prevent a vat without high-priority objects from creating one
  • it does allow vat code to elevate as many objects as it wants (during a high-priority delivery), is that too much authority? I'm not sure how to meaningfully limit it, at least not without tracking first-export more carefully
  • "current delivery priority" is a dynamic or temporal scope, but vatPowers.getPriority() implies something that works for the entire lifetime of the vat.. how to reconcile?

cc @erights (we'll do a proper presentation on this soon, but I figured you might like to hear about the work in progress)

[mhofman]

We also talked that we'll need some kind of way to check if an economic activity ends up entirely executed at higher priority without dropping down priority anywhere. The earlier discussion around "txnId" would be one way to accomplish this, but since we'll need a way to pause processing of lower priority messages for security reasons, we might be able to (ab)use that for sanity checks.

We also mentioned that mailbox messages, since we may not know anything about them at this point, may need to be processed by an even higher priority queue. Once processed, vattp would end up placing a message on the queue of "remote receivers" objects exposed by the comms vat, which could have a priority based on the sender. After a message is processed by the comms vat, we'd finally know the target objectId and use their priority queue. At lot of how the intake works depends on whether cosmic-swingset is able to pick high priority messages from the mempool, and inform swingset of their priority (see #4318). Regardless, the priority handling of a message would be sender based until handled by the comms vat, after which it becomes target object based.

Regarding promise subscriptions, I still have concerns that a vat may want to subscribe to a single promise with 2 different priorities, which if not discerned, would end up either dropping or raising the execution of the high / low reactions. The only way I see to how handle this is to consider a pair of [promiseId, priority] as a unique object for subscription purposes.

[warner]

Regarding promise subscriptions, I still have concerns that a vat may want to subscribe to a single promise with 2 different priorities, which if not discerned, would end up either dropping or raising the execution of the high / low reactions. The only way I see to how handle this is to consider a pair of [promiseId, priority] as a unique object for subscription purposes.

Oh, huh. Yeah I'm pretty sure we only want one subscription per promise (well, per (promise, vat) pair). I think I'd be ok with syscall.subscribe() on an already-subscribed promise causing elevation (but not depression) of the subscription's priority. If we're not making any guarantees about resolution order, then userspace shouldn't complain if sometimes they get resolved faster than they expected.

[mhofman]

If we're not making any guarantees about resolution order, then userspace shouldn't complain if sometimes they get resolved faster than they expected.

The problem is this is technically an elevation of privilege. The vat code might also expect that this low priority resolution would only every run after its other high priority code is done (that is a guarantee should make).

[mhofman]

After discussion with @dtribble, the suggestion was to switch to a model where a vat runs at a single priority level to avoid the complexity of exporting objects and subscribing to promises at different priorities within a vat. It also removes the requirement that message queues are per object (which we may still want for loosening ordering expectations, but it becomes an orthogonal problem).

However it does raise the issue that a lower priority sender may abuse its time slice to send multiple messages to a high priority vat (even if the target object in that vat may not do what would be considered high priority work). To solve that issue, we can introduce the concept of an "outbound queue", where message sends and promise resolutions are placed during a vat delivery. That outbound queue would be per vat, and be at the priority level of the vat. The messages would stay in that queue until picked by the kernel in FIFO order later.

There is some relation between the inbound queue (deliveries into a vat) and outbound queue (pending messages from the vat): if there are pending outbound messages, those must be processed before any pending inbound messages. We can come up with the concept of "active" queue, where the outbound queue is active if it contains any messages, the inbound queue is active if it contains any messages and the outbound queue is empty. That makes the active state for inbound and outbound queue mutually exclusive. The vat itself can be considered active if there are messages is in either of the queues.

A single outbound queue however doesn't work for the "system" vattp / comms vats. Since there is a single one of each, if we placed these vats at high priority, a low priority external sender would be able to send messages to a high priority vat (zoe, amm, etc.) without hitting any lower priority queue. One approach is to have 2 comms vat, one for each sender priority level. However that bundles all senders at a given priority into a single FIFO queue, which may not be desirable. An alternative is to allow the comms vat to create multiple outbound queues, one for each sender, at the priority level of the sender, and specify which outbound queue to use when performing syscalls. That makes the kernel free to pick messages from different senders in any order it wants. The onchain wallet, if implemented as a single vat, could use the same mechanism to generate messages in independent queues based on the wallet. This might also be the first step towards an activity concept.

Now the problem is reduced to the following:

• The kernel must process and drain queues from the higher priority level before processing a lower priority level.
• When processing a priority level, the kernel can either:
  • Pick a message from the top of any active inbound queue and deliver it into the vat
  • Pick one or more messages from the top of an any outbound queue, and place the corresponding messages at the back of the target's inbound queue
    • An object send results in a single message moved from an outbound queue to an inbound queue
    • A promise resolution results in notify messages for each pending subscriptions

Which queue to service first is a matter of scheduling policy. We can start with a pseudo-random order to verify no stronger ordering is relied upon.

Vattp and comms may run at an even higher priority level, to ensure external messages end up in the right outbound queues as early as possible. It's not clear at what priority level the onchain wallet should operate.

[warner]

We refined this a bit during this week's kernel meeting:

• one comms vat, runs at low priority
• two bridge vats, one high one low, since we think all the high-priority control/economic messages will arrive as distinct cosmos transactions, and will enter the kernel through the bridge rather than the mailbox/comms
• each vat has a priority
• each vat has an inbound queue and an outbound queue
  • the inbound queue holds dispatch.deliver and dispatch.notify DeliveryObjects
  • the outbound queue holds two object types (names TBD), one triggered by syscall.resolve, the other by syscall.send
    • this probably shouldn't hold exactly VatSyscallObject, and we have to think carefully about the GC implications: references are held by these messages just as much as if the message were in the old single run-queue
    • @mhofman oh hey, what if the outbound queue is allowed to hold sends directed at promises, and we defer the promise-status lookup until the outbound queue is processed? That might make the rate-limiting/fairness better, by not allowing vats to bypass their output queue by sending messages to known-resolved or known-to-be-soon-resolved promises.
• to service an inbound queue, the kernel performs a delivery
• to service an outbound queue:
  • for entries resulting from syscall.send, the kernel looks up the target of the message, and either transfers it to the target vat's inbound queue, transfers it to a kernel promise-table .pendingMessages queue, or discards it and rejects the result promise
    • TBD: how/when is that rejection handled?
  • for syscall.resolve entries, the kernel updates the kernel promise-table, pushes dispatch.notify entries onto the inbound queue of all subscribing vats, and (if the resolution is an object) transfers all .pendingMessages to the new target object's host vat's inbound queue

[mhofman]

• the outbound queue holds two object types (names TBD), one triggered by syscall.resolve, the other by syscall.send

I think we should hold subscribe the same way.

• oh hey, what if the outbound queue is allowed to hold sends directed at promises, and we defer the promise-status lookup until the outbound queue is processed?

That is the plan already as described in #4638, and the reason I split the run queue before changing the promise send behavior described in #4542.

• TBD: how/when is that rejection handled?

Rejection is just a notify, so promise is resolved to error right then, and regular notification logic runs queuing onto inbound queues.

[warner]

• the outbound queue holds two object types (names TBD), one triggered by syscall.resolve, the other by syscall.send

I think we should hold subscribe the same way.

That's plausible. It delays a vat's ability to hear its answer a bit longer (ideally the sender would be subscribed to the result promise before the message gets delivered and the promise gets resolved, so the promise can be deleted as quickly as possible). I'd want to see a trace of an overloaded kernel to get a sense for how much the delay matters.

• oh hey, what if the outbound queue is allowed to hold sends directed at promises, and we defer the promise-status lookup until the outbound queue is processed?

That is the plan already as described in #4638, and the reason I split the run queue before changing the promise send behavior described in #4542.

Perfect.

• TBD: how/when is that rejection handled?

Rejection is just a notify, so promise is resolved to error right then, and regular notification logic runs queuing onto inbound queues.

Hm, rejection is more like a syscall.resolve than a notify: it's a thing that will eventually fan out into some notifies. One option (maybe the one you're thinking of?) is to basically pretend that the vat rejected the result promise itself, right away, immediately after the doomed message got stomped, and during the same crank. Lemme think, what other work will that provoke immediately?:

• Any messages that were pending for that promise are now stomped, which brings up the same question. If we use the same answer, we're recursing.
• Any subscriptions on the promise turn into immediate notifies being pushed onto vat inbound queues
• If we make subscribe immediate, the sending vat gets an immediate push. If not, they won't have a notification pushed onto their own inbound queue until their subscribe makes it through their outbound queue.

The total work that could be provoked depends upon how deep the chain of pipelined messages is. My hunch is that all such messages will still be sitting behind the provoking message, so it's not an unbounded expansion of work (i.e. a vat can't arrange to cause a huge amount of kernel work to occur in a single crank with only a single outbound rejected message). If so, we're good.

[mhofman]

I think we should hold subscribe the same way.

That's plausible. It delays a vat's ability to hear its answer a bit longer

I suppose it may delay if the subscribe in the outbound queue gets processed after the promise is resolved. But that's a similar delay to enqueuing a send at a promise onto the promise queue until it gets resolved: the send only moves to the back of the inbound queue once the promise is resolved. In the subscribe case, I believe the delay is only observable by the vat if some other messages get queued onto the vat inbound queue in-between. For some reason I'm feeling less comfortable in ordering correctness if the subscribe is processed out-of-order with other send and resolve, but since we're supposed to move to inbound queues per object, that fear is probably misplaced.

Rejection is just a notify, so promise is resolved to error right then, and regular notification logic runs queuing onto inbound queues.

Hm, rejection is more like a syscall.resolve than a notify

Yes sorry I took a shortcut. For the result of a message send, it technically can become a fanout if the result promise was forwarded (except I believe you said liveslot is not currently capable of recognizing its result promises?).

pretend that the vat rejected the result promise itself, right away, immediately after the doomed message got stomped, and during the same crank

That is the current behavior and I was not planning on changing it.

My hunch is that all such messages will still be sitting behind the provoking message, so it's not an unbounded expansion of work (i.e. a vat can't arrange to cause a huge amount of kernel work to occur in a single crank with only a single outbound rejected message)

Right, all work would still have to be prearranged by other vats either subscribing or sending a messages to the shared promise. In all cases the reactions would be triggered by picking an event from an outbound queue. For regular promise settlement, it'd be from an explicit resolve placed on the outbound queue by the decider vat during a message delivery. In the scenario at hand, the promise is the result of a send being picked form an outbound queue and found invalid (e.g. target is settled promise previously rejected by an earlier delivery).

[warner]

(except I believe you said liveslot is not currently capable of recognizing its result promises?).

Mostly correct, userspace currently has no way to provoke liveslots into using a specific pre-existing promise reference (vpid) as the result of an outbound message (liveslots will always allocate a new one). We can imagine situations where we'd like to change that (tail-call optimization, if somehow liveslots could sense that foo() finishes with return E(bar).method(), it'd be neat to use the foo() result promise as the result of the syscall.send(bar)), but we can't yet imagine a way to achieve it. In any case, if the kernel is going to depend upon .result always being fresh, we need to enforce that in the syscall translation step, and then remove that enforcement (and redesign anything that depended upon it) if/when we find a way to improve liveslots and implement the optimization.

Userspace does get back a Promise from E().foo(), of course, and liveslots puts that Promise in the table under the newly-allocated vpid, and liveslots might send that out to other vats, who might subscribe to it. With the queuing approach we're taking, the they couldn't get that message (and learn the vpid, and subscribe to it) before the original message gets out. But if we ever implement multiple output queues, that property would change.

[mhofman]

With the queuing approach we're taking, the they couldn't get that message (and learn the vpid, and subscribe to it) before the original message gets out. But if we ever implement multiple output queues, that property would change.

Actually even just a pair of inbound and outbound queue per vat, the promise may be subscribed before the message is delivered:

• A sends message to Carol
• A sends result of above message as argument of message to Bob
• Both messages go through A's outbound queue in order, and get queued to B and C's inbound queues
• Kernel delivers message to B first, which subscribes to the promise
• B's outbound queue is processed, and the subscription registered
• Kernel delivers message to C, which resolves the promise.
• Both A and B are notified of the result

So I don't think it matters what order messages make it out of a vat in this case.

Anyway, I think we deviated, and the main concern was delay in notifies if subscriptions go through the outbound queue.

[warner]

I drew this up to describe our plan:

[warner]

I also realized an issue that might inhibit pipelining in too many cases.

 const p1 = E(obj).foo(); // obj is in comms vat, which enables pipelining
 const p2 = E(p1).bar();

When foo() comes off the vat-output-queue and hits the router, route(send) sees that the target is an object, the owner of that object is the comms vat, and the comms vat is still alive, so it pushes the foo onto the comms vat-input-queue.

If bar() comes off the vat-output-queue before foo() is delivered into the comms vat, p1 is still marked as being decided by the kernel, and bar() will get queued in the kernel promise table, because the kernel doesn't yet know that the message could be pipelined. We currently change the decider of a promise just before delivery into a vat, during translation of the KernelDeliveryObject (kref-space) into a VatDeliveryObject (vref-space).

If foo() makes it to comms first, then route(send) will see that bar is being sent to a promise with a decider, and that decider is both alive and has enabled pipelining. The router will add bar to the comms vat's input queue, and pipelining is happy.

I can think of three approaches to fix this:

• treat the comms vat input queue as special: high priority, to get everything delivered right away and update the decider before we route anything from any vat-output-queue
• set the result promise decider on a message when we add it to the vat-input-queue, not during delivery. The downside is that we have some useful invariant checking during message translation (the result promise must be owned by the kernel before translation, and owned by the target vat after translation), and I'm hesitant to give that up.
• let the message get queued on the promise, but when the decider is flipped, go through the promise's pendingMessages queue and move all of them into the new decider's vat-input-queue. I'd have to think about the ordering consequences of this, but my hunch is that it behaves the same

The first sounds wrong, and the second sounds bad, so I'm leaning towards the third.

[mhofman]

Yeah I was thinking we could do second, but 3rd sounds better, and I believe is what I had in mind originally anyway about updating deciders, and making sure a decider can only be set once for now so we don't have to go through the inbound queues to pluck messages out when a decider changes.