2.1 Representation

A capability is 16 bytes, and uses the same representation on both 32-bit and 64-bit platforms. The capability structure is a ``tagged union'' whose details depend on the capability type field. The kernel is entitled to use optimized representations internally. The representation given below is the representation disclosed by KeyBits, which is the representation typically used on disk.

Except where otherwise indicated, reserved fields must be zero-filled. The P (prepared) bit and the hz (hazard) bit are kernel internal, and are always zeroed by keybits when the capability representation is returned.

2.2 Valid Capabilities

Wherever this specification refers to a capability of a specific type, it should be taken to mean a valid capability of the stated type. The meaning of an invocation of a valid capability is determined by its implementation provider (kernel or server).

A non-object capability is any capability whose external representation does not include an allocation count. A non-object capability is always valid. Non-object capabilities are not revocable.

All other capabilities are object capabilities. An object capability is valid if and only if all of the following conditions are met:

• There exists some object with a matching object identifier (OID) whose type is compatible with the type of the capability.⁴

  This condition may be violated if backing store is lost or corrupted, or through a bug in the object manager.

• The allocation count in the capability matches the allocation count in the object.

  This condition ceases to be true when an object is revoked (see coyotos.range.rescind).

• In the case of an endpoint capability whose PM bit is set, the protected payload field of the endpoint capability matches the protected payload field of the endpoint object that it names.

All other object capabilities are invalid. An invalid capability behaves in all observable respects as if it were the Null capability. This applies both to invocation of an invalid capability and to operations that act on invalid capabilities (notably KeyBits, which has implications for debugging invalid capabilities). The kernel is free to overwrite any capability location with a Null capability when it determines that the capability contained in that location is invalid.

2.3 Capability Prepare

Coyotos is an object paging system. Both object load and object unload are driven by the use of capabilities. Ignoring latency, this paging behavior is normally invisible to applications. The exception is that object page-in may reveal low-level storage failures that make an object unrecoverable.

Whenever a capability is used, the kernel internally performs a prepare operation on the capability. Conceptually, this prepare step is being done by the process that is performing the current system call. The prepare operation may have several outcomes:

• If the capability is a non-object capability, the prepare operation succeeds (by definition).

• If the capability names an object, but its allocCount does not match the allocCount of the corresponding object, the capability is re-written (in place) to the Null capability.

  The containing object is not marked modified. If other operations cause the containing object to be modified, the Null capability will be written to disk. Otherwise, subsequent reloads of the object will re-obtain the stale capability and this check will be performed again with the same result.

  Several optimizations and mechanisms are used to ensure that the disk allocation count does not overflow.

• If the object named by the capability is not in memory, steps are taken to load it. The preparing process is enqueued to wait for the completion of this request, and re-starts its operation when the object has been loaded. In rare cases, this step may result in an ObjectContentLost exception if the backing store has experienced an unrecoverable storage error.

• If the object named by the capability is in memory, it is locked for the duration of the current system call unless they are unlocked explicitly.

A capability is ``used'' if:

• The capability is invoked by the current system call.

• The capability designates the invokee of the current system call.

• Fetching a capability argument or storing a capability result requires memory traversal, in which case all capabilities in the traversed slots are used.

• The operation requested by the current system call accesses or mutates the target object of the capability.

Coyotos implementations are required to be atomic. This implies that all resource acquisitions (and therefore all capability prepares) must be acquired before any observable side-effect of a system call occurs.

2.4 Extensibility

Coyotos is an extensible object system in the sense of Hydra [16]. New objects may be introduced by designing a process that implements the desired object. Capabilities to these objects are implemented as Entry capabilities. The kernel checks these capabilities for validity, and optionally for a protected payload match (see Chapter 5), but does not otherwise define semantics for these capabilities.

Because the kernel does not know the semantics of these extensions, entry capabilities are not considered ``safe'' by the coyotos.discrim.classify operation.

3.1 State of a Process

The state of a process may be divided conceptually into kernel (privileged or sensitive) state and user (non-privileged) state. User state is that state which a process may modify directly without kernel intervention. This includes architecture-defined non-privileged register state. It also includes additional ``pseudo registers'' defined by Coyotos that support the capability invocation mechanism.

Kernel state is that state which records or discloses protection information, or for which the kernel must guarantee invariants for reasons of security, robustness, or operational consistency. The representation of capabilities, for example, is kernel state. The Coyotos process structure contains space to save both the kernel state and the user state of a process.

On some hardware architectures, the separation between kernel state and user state is not cleanly accomplished by the architecture. The most common examples of this involve design failures in the architected processor status word. The IA-32 eflags register, for example, includes state such as the supervisor mode bit and the current ``IO privilege level.'' Such fields present a problem because the balance of the eflags register must be modifiable by untrusted code. When an unprivileged application runs normal instructions, the hardware generally protects these bits from modification. On such architectures, Coyotos must ensure that any registers modified by get/set registers and similar operations properly protect these fields. The architecture-specific annex for each architecture identifies any such registers and their update constraints.

3.2 Execution Model

The instruction set available to a Coyotos process consists of the user mode (non-privileged) instruction set of the underlying processor architecture, the kernel-implemented InvokeCap instruction (which is the subject of Chapter 5).

From the perspective of the kernel, a process exists in one of the following run states:

The state transition diagram is shown in Figure 3.3.

Figure 8.

Process state transitions

The blocked state is not externally observable. A blocked process has an externally reported runState of ``running''. Such a process is deemed to be running without making progress or consuming CPU cycles. The receiving state it also not externally observable. A receiving process is executing the receive phase of a capability invocation very slowly.

A process that is in the running state will initiate instructions as long as its process faultCode field is set to FC_NoFault (0). Execution behavior when any other value is stored in the faultCode field is discussed in Section 3.3.

3.3 Exception Handling

An exception occurs as the result of an instruction executed by the process. Every exception has an associated fault code. Specific exceptions may define an additional pointer value to be delivered as additional fault information. The fault code and fault information are delivered to the process by storing them in the faultCode and faultInfo fields of the Process and causing the process to resume execution.

3.4 Application-Defined Notifications

Coyotos supports application-defined non-blocking notifications via the AppNotice capability type. A notification is posted by invoking the AppNotice capability with 32-bit mask indicating the notifications (in the range 0..31) to be posted. The set of authorized notifications is determined at the time the AppNotice capability is fabricated. The effect of posting a set of application-defined notices is to set the corresponding bits of the target process softNotices word, and to set the sn bit of the target process flags if the value of notices has changed as a consequence of this posting (i.e. if the notice was not already pending). Of the set of notices posted, only the authorized subset is delivered.

If any notices are pending when the recipient enters an open wait, they will be delivered as a message, with a specified endpoint ID of ~0ull and a protected payload value of zero. Delivery of pending notices has higher priority than other incoming messages.

Delivery of application-defined notices is suppressed during a closed wait.

4.1 Memory Objects and Address Interpretation

Three objects are used to define Coyotos address spaces: pages, cappages, and GPTs. Capabilities to these objects may be invoked in the usual way. The interface definitions for these objects are provided in Part II.

The meaning of a data (capability) address reference is determined by starting at the data (capability) address space capability of the referencing process and traversing memory objects until the address has been successfully translated or an exception has occurred. The traversal process is similar to the traversal of hardware-based hierarchical translation tables, but there are several differences:

• The Coyotos mapping structures provide support for per-region fault handlers. Any region of size 2^k pages may have an associated fault handler. When a memory fault is reported to the in-process fault handler, the in-process handler may optionally forward memory fault messages to the per-region handler in order to request region-specific fault handling.

• The ``levels'' of the mapping hierarchy are dynamically determined. Smaller subspaces may appear where a larger space is expected, with the effect that the ``missing'' regions are considered invalid addresses. Larger subspaces may appear where a smaller space would naturally appear, with the effect that only the leading subrange of the larger subspace is addressable through this mapping.

• A mechanism is provided for mapping ``windows'' onto other address spaces by reference. This enables one address space to map (portions of) another even when the second space is opaque.

• In order to support certain essential types of addressing flexibility — notably windows — it is necessary to allow some unusual arrangements of the hierarchical structures. An unfortunate consequence of this is that it is possible for a hostile or erroneous program to create statically cyclic address spaces. Such spaces are malformed, and attempts to reference a cyclically defined address generate a MalformedSpace exception.

4.2 Pages and Capability Pages

The smallest mappable unit, and therefore the smallest address space, is the page or the cappage. A page is the atomic unit of data storage whose size is implementation-defined. A capability page is a page-sized unit that holds capabilities rather than data. Capabilities are byte-addressed opaque 16-byte quantities that are aligned at 16 byte boundaries.

With the exception of device pages, Coyotos implements a single page size whose size matches some hardware page size implemented by the underlying hardware. This size is specified by the architecture-specific annex. On processors that implement multiple page sizes, the selected page size need not be the smallest size supported by the underlying hardware. It is implementation-dependent whether the kernel will attempt to exploit larger hardware page mapping sizes if available. If such exploitation is attempted, it is accomplished by re-synthesizing larger pages by physical arrangement of standard-sized pages. The atomic unit of mapping and permissions remains the Coyotos page size. Pages always appear in both the physical and virtual memory maps at naturally aligned addresses.

A device page may be any size 2^k that is greater than or equal to the basic page size. If they are larger than the basic page size, they appear in both the physical and virtual memory maps aligned at a 2^k address. Device pages may be marked non-cacheable or write-through.

A page capability may be inserted into the address space slot of a process, with the effect of defining an address space having valid offsets between [guard,guard+pgsize-1]. Attempts to reference offsets outside this range result in an invalid address exception.

Capability pages are byte-addressable units. However, capabilities must be stored and referenced at naturally aligned (16 byte) boundaries.

Address translation of an address addr with respect to a page or cappage capability is defined as follows:

1. If the value of addr exceeds the page size, an InvalidAddress exception is generated.

2. Otherwise: the addr is a valid offset, and the overall address reference is valid.

4.3 Address Space Composition

Address spaces are composed by means of the GPT object. A GPT is simply a fixed-length vector of capabilities (currently 16), each of which is paired with a guard. In Coyotos, the guard has been incorporated into the capability format itself. The state of a GPT is shown below.

Invariant:    l2v ≥ log2(page size)

The meanings of the GPT fields are:

When the ha or bg bits are set, it is the responsibility of the process managing the GPT to ensure that the l2v value prevents collision.

g = va >> C.l2g;
guard = C.guard << C.l2g;
u = (va - guard) >> C.l2v;
v = va & ((1u << C.l2v) - 1);

4.4 Address Space Splitting

In order to support the subspace transfer item described in the capability invocation chapter, Coyotos introduces a new type of exception that may occur in an address space: the SplitFault.

Split faults allow an invoker to send a single capability to an arbitrary 2^k page region of an address space, provided that the region is naturally aligned and the invoker has sufficient access rights to extract the dominating capability. Similarly, they permit a receiver to generate appropriate ``holes'' into which such a capability must be received.

The problem solved by split faults is that there may not be any naturally dominating GPT for the subspace. For example, in a system having 4 kilobyte (2¹² byte) pages, the invoker may wish to transmit a 2¹¹ page (2²³ byte) subspace, but the subspace may currently be dominated by a GPT having l2v=21. That is: there is no single slot in the GPT that directly holds a capability of the desired span. Before a single dominating capability can be sent, this GPT must be ``split'' into an arrangement where the target subtree has a single dominating GPT with l2v=23. When such a send is attempted, the invoker will receive a SplitFault exception. This is an advisory that the GPT must be split in order to bring a dominating GPT into existence.

Similarly, if a receiver specifies a ``hole'' of some size 2^hlsz pages, there must exist some GPT in the receiver tree that could receive (with an appropriate guard value) a capability dominating a tree of the requested size.

The reason this feature is considered experimental is that the correct strategy for splitting GPTs is not obvious.

The address space splitting idea is not yet fully developed. There are certainly holes, including necessary but undefined exception types, that need to be resolved in the definition above.

5.1 Invocation Payload

An invocation passes a message that consists of:

• Up to 8 direct words, the first of which is the invocation control word. The size of these words is architecture dependent. These words may be carried in registers or memory, as specified by the architecture-specific annex for the target platform. The index of the last word transmitted is given by IPR0.ldw.

  Input parameter word 0 of the invoke capability operation contains control information describing the rest of the message payload:

  Figure 11.

  Invocation control word (input)

  Provided the invokee is valid and well-formed, a message consisting solely of untyped parameter words is guaranteed to proceed without exceptions on all architectures.

• Up to four capabilities. Capabilities are transmitted if IPR0.SC=1. If so, IPR0.lsc gives the index of the last capability transmitted. Capabilities are received if IPR0.AC=1. If so, IPR0.lrc gives the index of the last capability that will be accepted.

• An indirect string of up to 64 kilobytes. The length of this string is given in a parameter word to the system call.

In addition to the payload of the invocation, the invoker specifies:

• The capability to be invoked.

• Whether they are willing to block in order for the message to be delivered (IPR0.NB).

• Whether to fabricate a reply capability (IPR0.RC).

• Whether the receive phase should be performed (IPR0.RP).

• Whether copy-out of soft registers should be performed on those architectures that define soft registers. (IPR0.CO).

• Whether the receive phase should accept messages only from a particular endpoint (IPR0.CW, upcb.rcvEpID).

If a receive phase is executed, the receiver receives the following information in addition to the invocation payload:

• The endpoint identifier of the Endpoint on which the invocation was received.

• The ``protected payload'' of the capability that was invoked.

• The length of the string that was sent, it any.

• A modified copy of the invocation control word, which indicates various information about the incoming message. In this returned word, the u, RC, and SC, fields are copied from the sender's input invocation control word. The lsc field indicates the number of capabilities that have been received. The ldw field indicates the number of data words that have been received.

The protected payload and the endpoint ID can be used to determine the receiver-defined context in which the received message should be interpreted. One common use of these fields is for the endpoint ID to identify the object invoked and the protected payload to identify the permissions on that object.

5.2 Invocation-Related Exceptions

Exceptions may occur during invocation on either the sender or the receiver side of the transmission. All such exceptions logically occur before the invocation. In practice, exceptions are generated as a consequence of payload transfer. If an exception occurs, the implementation is free to resume the transfer at the point of interruption if it is able to do so. However, the receiver of an interrupted transmission logically reverts to the beginning of its receive phase when an exception occurs. In the event that a second sender is attempting to send when a messaging exception is incurred, the second sender's message may prevail.

If the sender specifies non-blocking transmission, the transfer of indirect strings and capabilities is ``best effort.'' If the receiver incurs a page fault during the receipt of an indirect string or a capability argument, that argument will be truncated. In this case the receiver will be notified of truncation, but no receiver-side exception will be generated.

The meaning of a non-blocking send is that the sender is unwilling to be blocked for any cause whose handling is controlled by the receiver. The use-case for this option is a server returning a reply to an untrusted client. For purposes of understanding truncation, a hardware page fault that is successfully resolved by the object paging subsystem is not considered to be an architecturally observable fault. Similarly, an exception that can be satisfied by reconstructing a hardware mapping entry from an already defined GPT hierarchy is not considered an architecturally observable fault.

5.3 Endpoints

A process that wishes to accept capability invocations does so by means of one or more endpoints (Figure 5.2). Endpoints have two capability types: the Endpoint capability, which implements the control interface for the endpoint object, and the Entry capability, which provides the means for extending the object system. When an Entry capability is invoked, the invocation parameters are delivered as a message to the process named by the recipient field of the Endpoint.

The meanings of the endpoint fields are:

5.4 Semantics of Kernel Capability Invocation

To ensure consistent invocation behavior, it is necessary to specify the externally observable behavior when a kernel-implemented method is invoked. In particular, the observable effect on process state and the sequencing of operations and events during a kernel invocation must be defined.

When a kernel capability is invoked, the externally observable behavior should be as if the invoker had invoked an endpoint to some application providing the service. Because no kernel operation accepts an indirect string, the invocation of a kernel capability behaves as if this hypothetical provider had performed a receive phase with IPR0.AS=0 (no strings will be accepted). This hypothetical provider arrives at the specified answer and accomplishes any effects of the invocation by unspecified means. It then replies as if it had invoked the InvCap system call with the control bits of the first input parameter word set as follows: NB=1 (non-blocking), RC=0 (no reply capability is generated), CW=0 (the kernel conceptually enters an open wait state), and RP=1 (the kernel waits for the next invocation). In addition, the SC (send capabilities) control bit will be set (clear) if capabilities are (are not) returned by the method. Note that because the kernel reply is non-blocking, and the kernel is deemed to be in the running state until it has replied, the reply from a kernel-implemented capability cannot cause a second kernel-implemented capability to be invoked.

This statement of behavior has (at least) the following implications:

• The effects of a kernel capability invocation occur whether or not the invocation returns successfully, provided any preconditions specified for the method are satisfied.

• There exist several kernel operations that alter the state of a process. When the process altered is also the process receiving the kernel reply (the ``invokee''), the kernel behavior must be well-defined. There are two such cases:

  1. The invokee process is destroyed as an effect of the invoked method. In this case, the reply proceeds as if via an endpoint that contains a Null capability.

By intention, kernel-implemented operations satisfy two invariants that simplify or eliminate other potentially obscure corner cases:

• No kernel-implemented interface accepts or returns an indirect string.

• Kernel methods that modify address space mappings or revoke objects return only scalar return values (and therefore behave as if SC=0). This ensures that changes in the meaning of the receive capability capitem_t values cannot impact the return of these operations.

Undefined Locations    The content of receive buffers, receive parameters, and receive capability locations is undefined between the start of the IPC receive phase and the completion of the IPC receive phase. For performance reasons, the kernel is entitled to arbitrarily modify state whose content is undefined during invocation. In particular, the kernel is entitled to modify the receive parameters or the receive string buffers of a waiting process without releasing that process from its wait state. This allows the kernel to more efficiently implement indirect string moves that may induce invoker or invokee page faults during the transfer. This means that all of the receive string buffers of a recipient may be modified during receive, even if the final message received sends only a single indirect byte. Similarly, any valid receive capability locations may be overwritten even if a smaller number of capabilities was transferred.

State Transitions    The overwhelming majority of kernel capability invocations return to the invoker without generating any exception. In these cases, the kernel may behave as if the operation occurred instantaneously, with the consequence that the invoker may never be observed to leave the running state.

Elided Reply Capability    When a kernel capability is invoked and replies to the invoker without an exception, the kernel implementation is free to elide the fabrication of the reply capability. Elided reply capabilities are observable because the protected payload value of the reply endpoint will not be incremented.

6.1 Parameters and Parameter Words

At the system call trap interface, arguments and return values are conveyed by means of a combination of registerized parameter values and (optionally) a system-call specific stack frame. Every architecture-specific annex specifies a subset of hardware registers that are be used to convey system call parameters. No annex defines fewer than four registers to be available at this interface. Where a specialized stack frame is specified, the architecture-specific annex may specify that some or all of that stack frame is conveyed across the user/supervisor boundary in registers. The corresponding fields of the stack frame will never be accessed by the kernel.

The Coyotos system call specification ensures that all arguments and return values of system calls other than InvokeCap can be marshalled in registers. In addition, the majority of kernel-implemented capabilities, including all capabilities likely to be invoked in performance-critical application paths, can be invoked without a string parameter.

In the system call specifications that follow, the notation IPRn and OPRn indicate input and output parameter registers, respectively. Except where required by the architecture-specific system call mechanism, or explicitly noted by the system call, output registers retain their value at the time of system call entry.

6.2 Exceptions

The following exceptions may be incurred by the caller during system call execution.

Any system call may generate the MalformedSyscall exception if bits marked ``reserved'' are non-zero or specified field value bounds are exceeded. Individual system call descriptions below specify which of the other exceptions may be incurred by that system call.

6.3 Capability Locations

A caploc_t parameter (Figure ) describes a generalized capability location that is either a capability register (ty=0) or a memory address (ty=1).

The encoding of register caploc_t values is identical to the encoding used for capreg_t values, modulo the wider location field. When the caploc_t describes a memory address, the location field holds the most significant bits of the address. Capability addresses are required to be 16 byte aligned. In consequence, the expression of valid capability addresses is not restricted by the re-use of the least significant bit for this purpose.

The size of a caploc_t matches the architecture-defined word size.

6.4 Pseudo-Instructions

The Yield and CopyCap system calls are best thought of as pseudo-instructions.

6.5 InvokeCap [syscall]

The InvokeCap system call invokes a capability, passing the supplied parameters to the implementing server. It is both the most complex and the most commonly used system call in the interface. It invokes one capability and optionally blocks for an incoming message on an Endpoint. InvokeCap takes a variable number of parameters determined by the invocation control word provided in IPR0 and a system-call specific stack frame.

Any of the exceptions listed in Section 6.2 may be generated by this system call.

typedef struct {
  uintptr_t pw[8];
  union {
    caploc_t  invCap;		/* on entry */
    uintptr_t pp;		/* on exit */
  } u;
  caploc_t  sndCap[4];
  caploc_t  rcvCap[4];
  uint32_t  sndLen;		/* FIX: Should be 16 bits */
  uint32_t  rcvBound;		/* FIX: Should be 16 bits */
  void     *sndPtr;
  void     *rcvPtr;
  uint64_t  epID;
} InvParameterBlock_t;

7.1 Scheduling Model

9.1 Device I/O Registers

Some hardware implementations provide a hardware register address space (I/O space) that is independent of the memory address space. This is most notably true on the Pentium, but more selectively true on other processors (e.g. Coldfire MOVCR). Authorization of access to the hardware register address space is determined by the per-process I/O space capability. The mechanics of hardware control register access is inherently target-dependent, and the mechanism used should be specified by the architecture-specific annex.

On some architectures, device registers can be memory mapped, and page-level protections are sufficient to provide effective isolation. On those systems, device registers can be treated as a form of device memory.

9.2 Device Memory

Some devices publish memory to the device bus that can be mapped wholly or partially into the main memory address space. Modern video cards are an example of this.

Typically, the mechanical and electrical bus architectures of a given machine limit the number of devices that are able to publish memory-mapped device memory. Busses such as SCSI, ATAPI, USB, and FireWire, by contrast, generally do not support memory mapped interfaces for their attached client devices. The controllers themselves may use memory mapping, but the attached devices do not.

This design allows the kernel to pre-plan for memory attached device memory by reserving a pre-planned constant number of page frames for each device, where the total number of memory-attachable devices is bounded at compile time. The size of these pages may be larger than the hardware page size defined by the MMU.

9.3 Object DMA

Because device pages exist at known physical addresses, it is possible for device drivers to use physical direct memory access (DMA) mechanisms to move data to and from these pages. This does not address the problem of DMA to and from conventional pages. For example, it is desirable for drivers to be able to transfer data directly to and from user space.

In abstract, there are three issues that need to be addressed in order to support this:

1. Discovering the physical address at which DMA should occur to reach the target page.

2. In some cases, ensuring that the target page falls within the physical address span reachable by the specific DMA subsystem, and satisfies any alignment or address congruency requirements of that DMA engine.

   An ancillary problem here is that two DMA engines may compete for the same page with incompatible addressing constraints. This either needs to be prevented or resolved consistently.

3. Ensuring that the target of DMA remains in memory (pinned) until the DMA operation has completed.

10.1 Unprepared Capabilities

An unprepared capability may be valid or invalid, because it is not known from the capability whether the object it names has been destroyed subsequent to the creation of the capability. This can only be known by comparing the allocCount of the capability to the allocCount of the object itself.

Assuming the capability is valid, the object designated by an unprepared capability may or may not be in memory. This can only be determined by performing an object lookup to discover whether the object is in memory. In all current implementations of KeyKOS, EROS, and Coyotos, a hash table is maintained that provides a mapping from object id (OID) to the actual object for every object that is currently in memory. In systems supporting transparent persistence, there may be two objects for a given OID: the current one and the one that was current at the time of the last snapshot.

10.2 Prepared Capabilities — Linked Implementation

In KeyKOS and EROS, a prepared capability designates an object that is known to be in memory. The prepared capability points directly to this object. In addition, the prepared capability resides on a ``key chain'', which is a circularly linked list whose ``head'' is part of the object header. This allows the object to be efficiently found given the capability, and also allows all prepared capabilities to be found given the object.

Figure 14.

EROS/KeyKOS key chain

There are several advantages to this design:

• Once a capability is determined to be prepared, the object is known to be in memory as a consequence of invariants, and few further checks related to residency or well-formedness are necessary. In addition, the capability is known to be valid, in the sense that its allocCount matches that of the target object.

• When an object is destroyed, it is straightforward to locate the active capabilities to the object and rewrite them as invalid capabilities.

• When an object is to be removed from memory, it is straightforward to locate all capabilities to the object and restore them to their unprepared form.

• In either the destruction or pageout case, it is straightforward to identify the locations of all prepared capabilities. KeyKOS and EROS exploit this property very aggressively. They maintain a significant amount of dependency information in hashed structures that are indexed by capability address. For example, the KeyKOS/EROS ``depend table'' is a hash table of (capability address, page table entry address) pairs.

However, there is a key disadvantage as well:

• Capability copy is a frequent operation. Empirically, we found in EROS that many copied capabilities were prepared, that most overwritten capabilities were prepared, and that updating the key chain when both the source and destination capabilities are prepared entails three cache misses per copy to access the neighbors (Figure 10.2). On modern machines, this cost is a substantial fraction of the total IPC cost.

• Capability invocation may take time O(n), where n is the size of memory. This is possible because an arbitrary number of resume capabilities may accumulate on the key chain, and the chain needs to be traversed in order to destroy them.

Figure 15.

EROS/KeyKOS key copy

10.3 Prepared Capabilities — Scavenged Implementation

In Coyotos, a prepared capability does not guarantee either that the target object is in memory or that the prepared capability is valid. We are accepting weaker invariants in order to improve capability copy performance. Instead of a linked list, the relationship between a capability and its object is shown in Figure 10.3.

Figure 16.

Capability/object relationship

In this design, the capability points to the object (equivalently: holds an index), but also contains a pointer (equivalently: an index) to an ObTable structure. The object pointer is valid only if the capability's ObTable reference matches the ObTable reference in the object itself. The purpose of the ObTable structure is to hold the information needed to deprepare the capability back to its on-disk form. This consists of a copy of the object ID (because that field of the capability is overwritten by the references) and a valid bit. Under normal circumstances, an object has one ObTable entry.⁷

When an object is paged out, the first step is to change the ObTable reference in the object header to Null. This ensures that all outstanding capabilities will be deprepared back to their on-disk format. When an object is destroyed, the valid bit in the current ObTable entry is set to ``invalid'' before the ObTable reference in the object header is nullified. In this situation, outstanding capabilities will be deprepared to the Null capability. Capabilities are deprepared through a combination of proactive update when the containing object is written to store and background scavenging.

11.1 Page Removal

In KeyKOS and EROS, the key chain meant that any implementation of requirement (3) also satisfied requirement (1). When a page is removed from memory, its key chain can be traversed to locate all of the capability slots that reference the page. These can then be used to invalidate the necessary page table entries.

In the Coyotos implementation, which does not have a key chain, we maintain a reverse page table structure known as PTE^-1. For every valid page table entry in the hardware page table, we maintain a reverse entry that provides a mapping from the physical object address to the kernel virtual address of its referencing page table entry.

In systems having hierarchical page tables, we maintain this inverse page table structure at all levels of the translation hierarchy. This allows mapping tables to be aged and reclaimed.

11.2 GPT Dependencies

The statement of requirements in (2, 3) is a bit subtle. The straightforward implementation of these requirements is to record a pairwise relationship between capability slot addresses and page table entry addresses, and use this to invalidate all page table entries when a slot is overwritten or a GPT is removed. This was, in essence, the implementation used by KeyKOS and EROS, and it is fairly straightforward to see why it satisfies the requirement that ``the permissions of the implementation state must never exceed those of the abstract state.'' However, this implementation is both unnecessarily aggressive and unnecessarily expensive.

Because we do not rely on key rings for page removal, Coyotos has slightly different properties than KeyKOS or EROS. Whenever we consider changing the value of a slot, we always have the address of its containing GPT in hand.⁸. Coyotos therefore maintains a dependency table that maps from GPT addresses to page table entry addresses. There may be multiple entries in this table for a given GPT. This can happen for two reasons:

1. A GPT may produce multiple page tables because it spans multiple entries in a page directory (Figure 11.1). This arises only in hardware system having hierarchical translation systems, but it can arise at any ``layer'' of the translation system. In fact, a single GPT can span three or more layers if it describes the only valid path across multiple levels of the hardware tables.

2. Because of page table reuse, a GPT may produce both read-only and read-write variants of the same page table.

Figure 17.

Capability/object relationship

The hierarchical case is complicated by the desire for page table sharing. In KeyKOS and EROS, we recorded dependency information at all implicated levels of the hardware translation hierarchy. In Coyotos we do not. Instead, we record dependencies only when the GPT wholly or partially dominates the hardware table. This is sufficient to let is invalidate all paths through the hardware tree that are implicated by changes to a GPT. It does not allow us to invalidate all of the page table entries, but we assert this is not actually necessary to satisfy the requirements.

This assertion is not obvious and will need to be confirmed by demonstration as we develop a statement of invariants maintained by the translation logic in this case. The substance of it, however, is that valid entries higher in the hardware structures do not matter if all of the lower entries they span are correctly invalidated. If the GPT is being destroyed, the lower tables will in due course be reclaimed and the higher-level page table entries will then be invalidated. If the GPT is being overwritten, the higher-level page table entries would get rebuilt in any case, and the permissions of the lower-level page table entries are sufficient to ensure a conservative mapping of the abstract machine's permission state.

11.3 Optimizations

Ironically, the new structure should be more compact than the old structure.

Inverse Page Table    The PTE^-1 table requires only a single word per entry, because the pointer to the PTE can be used to read the physical page address in order to detect hash collisions and stale dependency table entries.

Observe further that the majority of pages and page tables have only one or two simultaneous page table entries. A possible storage optimization is to dedicate two PTE^-1 entries in the frame management structures for each of these, leaving the general PTE^-1 table to handle only those pages that are widely shared. Whether this is worthwhile depends on whether a sufficiently good hash function can be discovered to keep hash chains short in the usual case.

GPT Dependencies    Because we use GPT object pointers rather than GPT slot pointers in the GPT dependency table, our GPT dependency table will have a factor of 16 (well, given underutilization probably a factor of 5 to 8) reduction in space requirements compared to the old dependency tracking scheme.

Observe that while a GPT may produce entries in multiple page tables, it always produces 2^k entries at a natural alignment boundary within those tables. This statement is also true of GPT slots, and offered a basis for run length compression of the GPT dependency table in some implementations. We note that this option remains available in the new implementation.