Describing the new async model
2 views
Skip to first unread message
William ML Leslie
Dec 11, 2025, 2:40:10 AM (5 days ago) Dec 11
to cap-talk
Well, why not.
I thought it might be time to start describing the new objects I've begun introducing to handle async IPC in the system I've been building. I've probably missed a lot of use cases that could cause these mechanisms to be completely re-engineered. If you think of anything I might be missing, I'd love to know. This description is both not detailed enough to be a spec and still low-level enough to be a tough read, I'm sorry in advance. I imagine the process of using this thing to feel a bit like sending messages in E, but I haven't built the user-level component in any capacity yet.
In this message, I'm not going to go into detail into the mechanisms for queing up messages to send, or for receiving messages asynchronously. We won't need to know much about the other new async objects to deal with this first thing, other than how you can use the send buffer to program the object I'm going to focus on here by filling it up with instructions in reverse order.
The new kernel object I want to talk about is called the Continuation, by analogy with the concept in programming language theory. The continuation is the stack of tasks to do next, and the fact that it's a stack rather than a sequence is the secret sauce that makes me think it's a really good fit for a KeyKOS family system. The problem with any sort of resource used for async message passing is that if the server is making any async requests on the client's behalf, those resources should really be provided by the client. To enable this, the capability to /reply/ to a continuation can also be used to /program it/ to make further requests.
The details of the object are relevant - there were lots of edge cases I wanted to check off, to ensure that resources allocated by a server can be cleaned up if the client aborts the request.
A continuation internally consists of an array of capabilities, an array of word-sized data fields, and a command stack. It includes a few additional fields to track state: the active top of stack, executing top of stack (used during truncation), mapped strings, allocated fields, the schedule it runs under, and the next version number. In particular, it can track when a message receive has begun, but truncation isn't complete. It can also track which capability and data indexes are currently available to a client sending it a program to run.
Enforcing stack discipline
A capability to a continuation - that is, a capability that allows you to reply to a continuation, or use it to make further requests - has a specific value for its Protected Payload field that is used to determine if the capability is still valid. The first byte in the payload indicates the stack offset of a valid "await" instruction, where "valid" requires that it be found by walking down from the top-of-stack. The remaining part of the payload must match the version number in the "await" instruction at that location.
This version number is incremented on each "await" instruction added to the continuation, so that each capability to a continuation follows the stack discipline. When these capabilities are used successfully, the stack is first truncated to the indicated "await" instruction, invalidating any capabilities derived from the one invoked.
Truncation first involves recording the current top-of-stack as the executing-top-of-stack, then setting the top-of-stack variable to the location of the instruction, and finally evaluating each instruction between them in a special "truncation" mode allowing clean-up. Evaluation in this mode never blocks, so any actions you want to take in case a continuation is aborted out from under you must ensure that their receivers are ready to receive. There are new objects to help you do this, but we won't describe them here.
Understanding the following descriptions
Instructions can have behaviour for four different cases:
- The instruction is being evaluated as part of normal behaviour; that is, the continuation has been placed onto a CPU which is actively evaluating instructions.
- The instruction is being evaluated as part of truncation; that is, something is reclaiming the continuation as a resource, but there may be clean-up to perform first.
- The instruction is being evaluated as part of receive. When you send a message to a continuation that you don't own, that message targets an instruction of the "await" variety, and those instructions can request specific behaviour.
- The instruction is being evaluated as part of programming the continuation. Most instructions are simply checked for validity and placed onto the command stack, but a few take immediate action as they are added.
The first two always need to be described, all "await"-style instructions need to describe their behaviour when receiving, and instructions that operate immediately describe their own effects.
Send, NBSend, Finally, Except
The continuation can be programmed to send messages for you. A send instruction, when executed, causes the continuation to wait for the target to receive, giving you a cheap way to enqueue a send and then get on with your work. If you need to send multiple messages to different processes, you can stack a series of send instructions onto a continuation.
In addition to the Send instruction, you can also perform a NBSend, which will be skipped if the target is not receiving. A Finally instruction is available to perform a NBSend both during normal execution and when truncating the continuation, and an Except instruction NBSends only when the instruction is being truncated. When the stack is being truncated, a normal Send instruction is simply skipped.
Here is the representation of this instruction family in the continuation. The uint8_t for target, caps, and data are indexes into the data and capability arrays. When sending instructions to the continuation, the indexes you supply are relative to the program you have placed on the stack. We will deal with that when we get to the allocate instruction.
struct send_sig_t {
uint8_t compact : 1;
uint8_t words : 3;
uint8_t caps : 2;
uint8_t str_in : 1;
uint8_t str_out : 1;
};
struct op_send_t {
uint8_t opcode;
struct send_sig_t sig;
uint8_t target;
uint8_t _pad;
uint8_t caps[4];
uint8_t data[8];
};
Await, Accept, AwaitLast, AcceptLast
Similarly, you can instruct a Continuation to accept and/or wait for a message. When you install one of these instructions into the Continuation, you indicate a location in its capability stack to place the matching Continuation capability to the instruction. Sending a message to one of these instructions never blocks the sender: it appears as a regular server reply to an eager client. However, how the continuation progresses after the send can differ.
When a reply message is sent to one of these capabilities, the stack is walked from the top to the offset named in the protected payload for the capability, and the type and version of the instruction there are checked to make sure the Continuation is still waiting for this message.
struct op_await_t {
uint8_t opcode;
uint8_t version[3];
uint8_t caps[4];
uint8_t data[8];
};
Each of these instructions sets the data and capability slots it names according to the message received. If fewer items are sent than requested, the additional slots are cleared (set to 0ull or cap_Null according to type).
On receiving, the Await instruction immediately truncates the continuation past its position, and then continues execution. On execution, the Await instruction removes the Continuation from the schedule. It won't run until something interacts with it. On truncate, it is skipped.
On receiving, the Accept instruction rewrites itself to be a no-op, but does not truncate the stack. The expectation is that when the Continuation is next scheduled or sent-to, it will continue execution. If the Accept instruction is the top of stack, then it continues execution. On execution, the Accept instruction acts as Await: it waits for a message to be received. On truncate, it is skipped.
On receiving, the AwaitLast instruction rewrites itself to AcceptLast. It does not truncate the stack, unless it is already the top-of-stack, in which case execution continues from this instruction. It sets the data and capability slots that it names, including clearing any that are not populated by the message. On execution, it behaves as Await: the expectation is that at least one message is received before it can execute. On truncate, it is skipped.
On receiving, the AcceptLast instruction populates the fields it names, and nothing further. On execute, it is skipped. On truncate, it is skipped.
The key feature of these instructions is that anybody sending a message to them doesn't need to wait. Truncation can cause additional messages to be sent, but all of these are sent non-blocking.
Note that await instructions never accept indirect strings. This is because string regions, both read-only and writable, are optionally provided by the client. The sender can "send" a string by filling the buffer the client earlier gave it.
Allocate (or, Deallocate)
When you add the allocate instruction to a continuation, you open up a new range of indexes to use in further instructions. When this instruction is placed on the stack, it becomes a deallocate instruction, restoring the top of the data and capability stacks to their location when the instruction was pushed. On truncate, this instruction truncates the data and capability stacks to their previous position as if executed.
Set/Restore String
When you add the set-string instruction to the continuation, you select one or two capabilities that can be revokably mapped into a receiver. Flags in the "send" operation allow you to share the configured string with a target.
When placed on the stack, this instruction sets the value(s) of the "current-string" fields, and becomes a "restore" instruction, naming the previous string values. When executed, or truncated, this instruction sets the value of the current string back to the original values.
There is not yet a mechanism to ensure that a continuation's string is mapped into at most one target. There should be.
It is the programmer's responsibility to ensure that a memory object used as a string is cleared as necessary (usually with a "NBSend") after interactions with clients, but "the programmer" here is probably capidl.
Set
There is a command for filling slots on the capability and data stacks. These don't put any instructions onto the continuation, just modify the data available to your continuation program.
Set instructions name the slot in the continuation using a local index, as well as a location to draw the value from, either a coyaddr_t in the case of data or a caploc_t for a capability.
I thought it might be time to start describing the new objects I've begun introducing to handle async IPC in the system I've been building. I've probably missed a lot of use cases that could cause these mechanisms to be completely re-engineered. If you think of anything I might be missing, I'd love to know. This description is both not detailed enough to be a spec and still low-level enough to be a tough read, I'm sorry in advance. I imagine the process of using this thing to feel a bit like sending messages in E, but I haven't built the user-level component in any capacity yet.
In this message, I'm not going to go into detail into the mechanisms for queing up messages to send, or for receiving messages asynchronously. We won't need to know much about the other new async objects to deal with this first thing, other than how you can use the send buffer to program the object I'm going to focus on here by filling it up with instructions in reverse order.
The new kernel object I want to talk about is called the Continuation, by analogy with the concept in programming language theory. The continuation is the stack of tasks to do next, and the fact that it's a stack rather than a sequence is the secret sauce that makes me think it's a really good fit for a KeyKOS family system. The problem with any sort of resource used for async message passing is that if the server is making any async requests on the client's behalf, those resources should really be provided by the client. To enable this, the capability to /reply/ to a continuation can also be used to /program it/ to make further requests.
The details of the object are relevant - there were lots of edge cases I wanted to check off, to ensure that resources allocated by a server can be cleaned up if the client aborts the request.
A continuation internally consists of an array of capabilities, an array of word-sized data fields, and a command stack. It includes a few additional fields to track state: the active top of stack, executing top of stack (used during truncation), mapped strings, allocated fields, the schedule it runs under, and the next version number. In particular, it can track when a message receive has begun, but truncation isn't complete. It can also track which capability and data indexes are currently available to a client sending it a program to run.
Enforcing stack discipline
A capability to a continuation - that is, a capability that allows you to reply to a continuation, or use it to make further requests - has a specific value for its Protected Payload field that is used to determine if the capability is still valid. The first byte in the payload indicates the stack offset of a valid "await" instruction, where "valid" requires that it be found by walking down from the top-of-stack. The remaining part of the payload must match the version number in the "await" instruction at that location.
This version number is incremented on each "await" instruction added to the continuation, so that each capability to a continuation follows the stack discipline. When these capabilities are used successfully, the stack is first truncated to the indicated "await" instruction, invalidating any capabilities derived from the one invoked.
Truncation first involves recording the current top-of-stack as the executing-top-of-stack, then setting the top-of-stack variable to the location of the instruction, and finally evaluating each instruction between them in a special "truncation" mode allowing clean-up. Evaluation in this mode never blocks, so any actions you want to take in case a continuation is aborted out from under you must ensure that their receivers are ready to receive. There are new objects to help you do this, but we won't describe them here.
Understanding the following descriptions
Instructions can have behaviour for four different cases:
- The instruction is being evaluated as part of normal behaviour; that is, the continuation has been placed onto a CPU which is actively evaluating instructions.
- The instruction is being evaluated as part of truncation; that is, something is reclaiming the continuation as a resource, but there may be clean-up to perform first.
- The instruction is being evaluated as part of receive. When you send a message to a continuation that you don't own, that message targets an instruction of the "await" variety, and those instructions can request specific behaviour.
- The instruction is being evaluated as part of programming the continuation. Most instructions are simply checked for validity and placed onto the command stack, but a few take immediate action as they are added.
The first two always need to be described, all "await"-style instructions need to describe their behaviour when receiving, and instructions that operate immediately describe their own effects.
Send, NBSend, Finally, Except
The continuation can be programmed to send messages for you. A send instruction, when executed, causes the continuation to wait for the target to receive, giving you a cheap way to enqueue a send and then get on with your work. If you need to send multiple messages to different processes, you can stack a series of send instructions onto a continuation.
In addition to the Send instruction, you can also perform a NBSend, which will be skipped if the target is not receiving. A Finally instruction is available to perform a NBSend both during normal execution and when truncating the continuation, and an Except instruction NBSends only when the instruction is being truncated. When the stack is being truncated, a normal Send instruction is simply skipped.
Here is the representation of this instruction family in the continuation. The uint8_t for target, caps, and data are indexes into the data and capability arrays. When sending instructions to the continuation, the indexes you supply are relative to the program you have placed on the stack. We will deal with that when we get to the allocate instruction.
struct send_sig_t {
uint8_t compact : 1;
uint8_t words : 3;
uint8_t caps : 2;
uint8_t str_in : 1;
uint8_t str_out : 1;
};
struct op_send_t {
uint8_t opcode;
struct send_sig_t sig;
uint8_t target;
uint8_t _pad;
uint8_t caps[4];
uint8_t data[8];
};
Await, Accept, AwaitLast, AcceptLast
Similarly, you can instruct a Continuation to accept and/or wait for a message. When you install one of these instructions into the Continuation, you indicate a location in its capability stack to place the matching Continuation capability to the instruction. Sending a message to one of these instructions never blocks the sender: it appears as a regular server reply to an eager client. However, how the continuation progresses after the send can differ.
When a reply message is sent to one of these capabilities, the stack is walked from the top to the offset named in the protected payload for the capability, and the type and version of the instruction there are checked to make sure the Continuation is still waiting for this message.
struct op_await_t {
uint8_t opcode;
uint8_t version[3];
uint8_t caps[4];
uint8_t data[8];
};
Each of these instructions sets the data and capability slots it names according to the message received. If fewer items are sent than requested, the additional slots are cleared (set to 0ull or cap_Null according to type).
On receiving, the Await instruction immediately truncates the continuation past its position, and then continues execution. On execution, the Await instruction removes the Continuation from the schedule. It won't run until something interacts with it. On truncate, it is skipped.
On receiving, the Accept instruction rewrites itself to be a no-op, but does not truncate the stack. The expectation is that when the Continuation is next scheduled or sent-to, it will continue execution. If the Accept instruction is the top of stack, then it continues execution. On execution, the Accept instruction acts as Await: it waits for a message to be received. On truncate, it is skipped.
On receiving, the AwaitLast instruction rewrites itself to AcceptLast. It does not truncate the stack, unless it is already the top-of-stack, in which case execution continues from this instruction. It sets the data and capability slots that it names, including clearing any that are not populated by the message. On execution, it behaves as Await: the expectation is that at least one message is received before it can execute. On truncate, it is skipped.
On receiving, the AcceptLast instruction populates the fields it names, and nothing further. On execute, it is skipped. On truncate, it is skipped.
The key feature of these instructions is that anybody sending a message to them doesn't need to wait. Truncation can cause additional messages to be sent, but all of these are sent non-blocking.
Note that await instructions never accept indirect strings. This is because string regions, both read-only and writable, are optionally provided by the client. The sender can "send" a string by filling the buffer the client earlier gave it.
Allocate (or, Deallocate)
When you add the allocate instruction to a continuation, you open up a new range of indexes to use in further instructions. When this instruction is placed on the stack, it becomes a deallocate instruction, restoring the top of the data and capability stacks to their location when the instruction was pushed. On truncate, this instruction truncates the data and capability stacks to their previous position as if executed.
Set/Restore String
When you add the set-string instruction to the continuation, you select one or two capabilities that can be revokably mapped into a receiver. Flags in the "send" operation allow you to share the configured string with a target.
When placed on the stack, this instruction sets the value(s) of the "current-string" fields, and becomes a "restore" instruction, naming the previous string values. When executed, or truncated, this instruction sets the value of the current string back to the original values.
There is not yet a mechanism to ensure that a continuation's string is mapped into at most one target. There should be.
It is the programmer's responsibility to ensure that a memory object used as a string is cleared as necessary (usually with a "NBSend") after interactions with clients, but "the programmer" here is probably capidl.
Set
There is a command for filling slots on the capability and data stacks. These don't put any instructions onto the continuation, just modify the data available to your continuation program.
Set instructions name the slot in the continuation using a local index, as well as a location to draw the value from, either a coyaddr_t in the case of data or a caploc_t for a capability.
Why this approach sucks
First, the good bits: this approach requires clients to provide the resources a server needs to perform further asynchronous requests on its behalf, while still providing the means to revoke access to those resources in a structured way. It fits within a larger model that allows you to program, reply to, or receive from multiple continuations without a context switch, although we haven't explored the mechanisms that let you do this.
This was heavily inspired by how Midori allows regions to be handed to other threads. In Midori, it appears that a solid protection from mutable shared state was that there was a class of messages that could only be mapped into one task at a time, when the task was done, the message was unmapped and invalidated.
The continuation feels like the programming language theory concept of a Context, which we have discussed here before. A Context (as they are named in Go and Racket) can represent the request that is currently being handled, including support for things like cancellation or configuration.
One question that seems natural is, do we really want this object to be a set of fixed-size arrays? If this is just a Context, it would be nice if the primary things it held were a SpaceBank and a Schedule, and that the command stack, capability stack, data stack, and strings were simply allocated out of that when needed. Maybe even endpoints for the "await" style instructions could be allocated, too. I have an intuition that this would feel less KeyKOS-like, but I would like to be convinced otherwise.
At one point, I also worked really hard to support promises and saguaro stacks within this framework. Promises behaved like a broadcast technique, where sending to a promise would give it a value and mark anything waiting on it as runnable. Saguaro stacks allowed you to break a Continuation into two, and make requests in parallel. My feeling was that these complicated truncation and scheduling in ways I wasn't quite able to reconcile.
Another conceptual brain-fart is that the Continuation is a migrating thread, and it might be interesting to recast processes in terms of them.
First, the good bits: this approach requires clients to provide the resources a server needs to perform further asynchronous requests on its behalf, while still providing the means to revoke access to those resources in a structured way. It fits within a larger model that allows you to program, reply to, or receive from multiple continuations without a context switch, although we haven't explored the mechanisms that let you do this.
This was heavily inspired by how Midori allows regions to be handed to other threads. In Midori, it appears that a solid protection from mutable shared state was that there was a class of messages that could only be mapped into one task at a time, when the task was done, the message was unmapped and invalidated.
The continuation feels like the programming language theory concept of a Context, which we have discussed here before. A Context (as they are named in Go and Racket) can represent the request that is currently being handled, including support for things like cancellation or configuration.
One question that seems natural is, do we really want this object to be a set of fixed-size arrays? If this is just a Context, it would be nice if the primary things it held were a SpaceBank and a Schedule, and that the command stack, capability stack, data stack, and strings were simply allocated out of that when needed. Maybe even endpoints for the "await" style instructions could be allocated, too. I have an intuition that this would feel less KeyKOS-like, but I would like to be convinced otherwise.
At one point, I also worked really hard to support promises and saguaro stacks within this framework. Promises behaved like a broadcast technique, where sending to a promise would give it a value and mark anything waiting on it as runnable. Saguaro stacks allowed you to break a Continuation into two, and make requests in parallel. My feeling was that these complicated truncation and scheduling in ways I wasn't quite able to reconcile.
Another conceptual brain-fart is that the Continuation is a migrating thread, and it might be interesting to recast processes in terms of them.
--
William ML Leslie
Reply all
Reply to author
Forward
0 new messages