Skip to content

Instantly share code, notes, and snippets.

@Zoxc
Last active August 18, 2016 07:34
Show Gist options
  • Save Zoxc/5fac5a844060fee9a74cb4d8b5cf1e65 to your computer and use it in GitHub Desktop.
Save Zoxc/5fac5a844060fee9a74cb4d8b5cf1e65 to your computer and use it in GitHub Desktop.

Remote procedure calls in Avery

Introduction

Avery's RPCs are based on capabilities. A capability is a reference to an object which the process has previously received. If you do not have a capability to an object, you cannot communicate with it.

You can do asynchronous calls to objects. These in calls, arguments and return values can contain both bytes and capabilities. If you send a capability to another process it gains access to it.

Objects belong to an event loop (a kernel object) and all messages sent to it is queued there.

Capabilities are represented as an pair of an event loop reference and an integer. The integer identifies which object under the event loop the capability references.

An event loop can create capabilities to local objects at will.

Each process has a map from capabilities to local capability information. When a capability is sent to another process or if you do a call on it, the kernel ensures that the sender has access to it already. When an event loop receives a capability, the kernel will add it to the receiving's process map.

In code, these things could look like this:

struct Cap(EventLoopId, usize);

struct EventLoop {
  inbox: Map<ProcessId, Vec<Message>>,
}

struct Process {
  caps: Map<Cap, CapInfo>,
  event_loops: Map<EventLoopId, EventLoop>,
}

enum Message {
  Call(RPC, Cap, Vec<u8>, Vec<Future>),
  Return(RPC, Vec<u8>),
  Resolve(Future, Cap),
  Release(Cap, usize)
}

Here event loops has an inbox for each process.

Messages are created and processed by the kernel so they are unforgable.

RPC objects

To represent a RPC in progress, a RPC kernel object is allocated. The callee will gain a return capability to it, which gives the ability to return a value.

The caller field gives the event loop to send the return value to.

During a RPC, the Call message is sent with a newly created RPC object. The receiver should return a value for that call, which causes a Return message to be sent back (to the event loop in caller).

The RPC kernel object is atomically reference counted.

struct RPC {
  caller: EventLoopId
}

Future objects

When a RPC returns a capability, a Future object is allocated. This represents a capability that will later be known. The caller will gain a future capability to it, which gives access to the returned capability. The callee will gain a promise capability to it, which gives the ability to resolve the future to a value.

enum Future {
  resolved: bool,
  value: Option<Cap>,
  queue: Vec<Message>,
}

The caller can immediately call the future and sent it in arguments. Messages sent to the future is queued in the Future object instead of being sent to the yet unknown inbox of the returned capability. This is called promise pipelining and helps reduce context switches.

When the callee resolves the future, the value field gets updated with the capability and a Resolve message is sent to the owner of the capability.

When the owner processes the Resolve message, it will set the resolved field to true, which will cause calls to the future to go directly to the destination instead of into queue. The owner will then process the messages in queue before any other.

When we are sending a capability in a message to another event loop and neither we nor the receiver owns the capability we create Future object and the future capability to it will be sent instead. We send a Resolve message to the owner of the real capability with the real capability as an argument. This is required in the case were we have sent messages to the real capability, but the owner hasn't processed them yet.

The Future kernel object is atomically reference counted.

Garbage collection

Capability garbage collection is handled by reference counts. Each process stores a CapInfo struct per capability it has access to.

enum CapInfo {
  user_rc: usize,
  pending_rc: usize,
  remote_rc: usize,
}

When the kernel receives a capability, it will increase both user_rc and pending_rc in the receiver. Usermode can increase and decrease the user_rc field by syscalls. When user_rc goes to 0, access to the capability it removed and a Release message with the pending_rc count it sent to the owner of the capability.

When the kernel is sending a capability which is owned by the sender, it will increase the remote_rc field in the sender. When it receives a Release message, it will subtract the argument from the remote_rc field. If it reaches 0, the object is freed.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment