The red segment node is an artifact in the Keykos memory tree logic by which Keykos programs define address spaces. It has found strategic uses outside of memory logic but detailed descriptions are available only inside the somewhat turgid descriptions of the memory logic. In the following we use the Keykos terminology “key” for “capability”.

The most accurate definition of memory tree logic, including red segments, can be found here which is the document from which the code was written.

This is an easier document concentrating again on memory logic and emphasizing function while omitting coding details.

Here are two new sections

Rationale of Red Segment

The simplest and most common pattern of segment nodes in Keykos is when successive 4 bit nibbles of an effective address, from left to right, are used to walk down a memory tree (away from the root) to reach a page which holds the sought byte. Each of these nodes hold 16 keys and each key slot must be available to hold a capability to a portion of the address space. The four bit index of that slot is directly from the relative byte address within the segment. If a slot were architecturally reserved in the segment node, say slot 15, then virtual addresses with a hexadecimal F could never be defined in a memory tree. Segment nodes without reserved slots are called “black segment nodes”. The key to a node has a byte of data that indicates whether the designated node is red or black. That data byte also defines which byte of the effective address is used to index into the designated node.

There are several features of the memory tree architecture that require annotations within the tree itself. For these the kernel recognizes a variant on the segment key that causes the kernel to treat the designated node as a “red segment node” and then the kernel inspects slot 15 of the node for signals from the builder of the memory tree. Slot 15 will contain the “format key” which is a number key. The format key specifies some subset of several special memory tree functions.

One of the special functions is a segment keeper for this part of the address space. The keeper is invoked when address faults occur in the segment. When access is made to a portion of this space that is undefined, the keeper is invoked with the authority necessary to repair the segment.

Calling a Segment Key

A Keykos design pattern is that any key can be called even when its main use is not in its calling. The main use of a memory key is to sit in a special domain (process) slot in order to define its address space. A memory key is also the normally found in a segment node as the tree is walked to define the meaning of an effective address.

When a black segment key is called, only the data byte from the key is returned to the caller along with an alleged type “segment key”. When a red segment key is called and the red segment node has a keeper, as determined by the format key in the node, the message goes to the keeper. This was soon discovered to be an efficient indirection for things that you might call. It is at least a means of rescinding access to a callable service. The red segment node can be deleted and the holder of the corresponding segment key is left holding a null key in effect. Alternatively the slot in the red segment node holding the key to the keeper can be overwritten with another key thus redirecting calls to another server domain. The message addressed with the segment key is delivered directly to the keeper—there is no double copying.

There is a bit in the format key of the red segment node indicating that one of the keys of the delivered message is to be displaced by a node key to the red segment node. The key displaced from the message is placed in the node wherefrom the keeper can retrieve the displaced key. In this scheme the keeper can access other keys in that particular red segment node which thereby serves as a context. Red segment keys to a variety of red segment nodes provide access to a corresponding variety if ‘instantiations’ of the object—all instantiations implemented by the same domain (process).