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!
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.
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.
The Virtual Copy Segment Keeper delivers manifestly discreet segments while abstracting its own mechanism.
A segment snapshot proposal. A keeper?