Segments are mutable arrays of bytes. They are used to hold what files hold in other systems and also to provide the virtual memory for user mode programs.

The description of segments in the architecture paper is the densest part of a dense paper. Indeed describing the exact function of KeyKos segments has resisted all attempts at lucidity so far. Yet those who use them find them easy to understand. So here goes yet another attempt with an emphasis on rationale, which often aids understanding.

Several standard segment keepers are available that suit conventional file semantics and thus few KeyKos programmers need even the details described here. Yet knowledge of just this much makes it possible to know when to match the application implementation more closely to the deeper system architecture, if performance or space are an issue. Sometimes the Keykos segment structure yields a simpler solution than conventional file semantics, or solutions to problems unavailable in conventional systems.

In most hardware architectures there is a construct that divides the set of virtual addresses into several contiguous ranges. The number of ranges and their size is a power of two. Often these ranges are themselves divided into smaller ranges. The term “segment” is often used to refer to one of these sizes and “page” is used to refer to the smallest subdivision. Usually the segments are all the same size. There is the hierarchy of:

(As of 2007 more levels are often required or other organizations are used.)

By contrast Keykos segments are of many sizes and recursively composed of other (usually) smaller segments, down to the page. The entire address space and the individual page are themselves segments in our terminology. The largest segments may be larger than an address space.

Starting from the primitive pages there are four primitive ways of composing new derivative segments from old segments: concatenation, windowing, making read-only and keeping. Each of these derivatives leaves the old segment intact and functional. The derivative does not consume or displace its input!

Concatenation
Several component segments can be concatenated together to form a larger compound segment and each component segment has its own range of addresses thru which it is accessible via the compound segment. Reading and writing the compound segment is equivalent to reading and writing some component segment.
Windowing
A portion of a segment can be selected to serve as a new smaller segment. Loads and stores to the new segment behave as loads and stores to the selected portion of the original segment.
Read_Only
A new segment can be formed to which reads are equivalent to reads of the original but to which writes always report errors to the writer without affecting the either new or old segment.
Keeping
The new segment nominates a keeper which receives the error reports that would otherwise go to the accessor of the original segment. Upon invocation the keeper receives information and authority necessary to repair the situation. The keeper may then repair the segment and restart the domain whose access the prior segment state could not satisfy. The accessing domain cannot sense these actions.
None of these derivatives acquires new storage for the data and each relies on the original segment. For instance if a read-only version R of segment S is made, and then S is modified, then that modification is visible in R. Since segments are not consumed by these derivatives, segment X may appear at once in two derivatives and then X is shared between derivative segments and between address spaces. A derivative can be deleted while preserving the original — a derivative can thus provide selectively rescindable access to a segment.

All of the above function is supported by the kernel. It is misleading as I have omitted some serious limitations. The size of a Keykos segment, as used above, is a power of sixteen and concatenation is in groups of sixteen. If some of these 16 segments are too short, gaps appear and some addresses within the resulting segment will be invalid and report errors upon reference. The portion selected in a windowing operation must be at an offset that is a multiple of the window size which is a power of 16. These limitations make the kernel simpler, faster and result in greater sharing of hardware features such as page tables. It is possible to build similar constructs outside the kernel with fewer limitations but we have not yet found this necessary.

Each of the derivatives is made by putting segment keys for the old segment(s) into a new node, putting magic number keys in other slots of the node, and then requesting a segment key to the node which serves as the segment key to the new derivative segment. Depending on several details one node can achieve all of the above compositions at once. Details of how to choose these number keys can be found here where number keys are called “data keys”.

One detail we mention here is the kludge to allow all 16 slots of a node to define subsegments, which is, after all necessary to support addresses with hex “F” in them. The black segment is identified by a segment key thereto whose data byte so indicates. That data byte also provides the “stride” for the segment, or in other words, which bits of the virtual address are used to index into the node’s 16 slots. Other nodes that define segments are called “red”. Red segment nodes reserve slot 15 to hold a number key with several control fields.

Abstraction of Construction Details

The above information is critical to the design of programs that allocate virtual addresses and especially those responsible for sharing real storage.

Just as procedural abstraction modularizes algorithms, the KeyKos segment key construct modularizes the construction of address spaces. A program may construct a segment according to the above rules, producing a seamless segment while hiding the details of how this is done, thus providing the classic freedom to change the implementation.

Program X can produce a segment following the rules above, and present the result to another program Y as a segment key so that Y cannot depend on the details of the construction of the segment. The segment that X produced may be incorporated into a segment that Y produces. This can be extended for several levels. There are arbitrary limits on how many levels may be constructed. This is supported by the fact that the segment key, referred to above, does not let its holder delve into the construction details. Messages directed to a segment key of a kept segment go to the keeper and references to the segment key as a memory key invoke the keeper as well, whenever real storage is undefined in the underlying node structure. The keeper is thus in a position to maintain the illusion that the storage was always there, or cause the referencing domain to fault as the keeper wishes.

See about the NoCall bit.
Another twist on segment logic.

Charlie Landau describes details on how to implement such structures as these upon modern hardware.
Here is a possibly useful wrinkle to reclaim space sooner. I think it has not been implemented.

The Virtual Copy Segment Keeper delivers manifestly discreet segments while abstracting its own mechanism.
A segment snapshot proposal. A keeper?