The logic of prepared segments is the most complex as it connects with the hardware mapping tables and the TLB, which are themselves variations on the idea of adapted data.
There is also the logic to share the real facilities that support the logical structures, so that two segments that share a subsegment logically, are reified so as to share in reality.
The ultimate assertion is that whatever access the TLB provides must be warranted by the nodes that define the segment as they are now.
This assertion depends on these assertions:
- The access provided by the TLB is a subset of the access defined by the memory maps in RAM,
- The access defined by the RAM memory maps is a subset of the access defined by the nodes prepared as segment nodes.
- The prepared segment nodes are, of course, a subset of the memory tree for the domain.
The kernel is involved in each of these assertions for the kernel must inform the TLB of changes that it makes to the mapping tables.
On the 88K the state of the TLB is accessible to the kernel via real addresses and the routine CHECK, for the 88K, verifies the first assertion.
These assertions hold even as the memory tree consists of nodes which are mutable via keys to these nodes.
Changes must take effect immediately.
By “segment nodes”, we mean here nodes, segmode keys which have appeared in a memory defining context, such as an initial slot of another segment node, or as in the address slot of a node prepared as a domain root.
How a segment node is prepared and data is adapted data therefrom, depends on the segmode key, or keys via which it was accessed.
For instance the same node may be used to define at once a 232 byte space and a 216 byte space if two different segment keys with distinct data bytes to that node have each been recently used.
This is rarely, if ever, useful but it was found a good idea to allow this for two reasons:
- It was easier to allow it than to prevent it.
- It was not even clear how to specify kernel semantics that would prevent it.
It would be sort of like building a CPU that would balk at trying to obey a floating point number.
Some early machines actually devoted a bit in the word to prevent this.
It was soon decided that this bit was not worth the cost and indeed it was unclear that there was any worth.
A segment node produces a set of mapping tables whose detailed nature depends on the specifics of the mapping hardware of the system.
More than one such table may be produced due to distinct segment keys to the same node, or different contexts of segment keys to the node.
Two segment keys to a segment node may differ in the data byte which includes
- The read only bit,
- The segment size code.
Contexts of segment keys may differ as follows:
- Distinct background keys.
- The two keys come from slots with different low order index bits.
This is a necessary wrinkle on machines whose hardware mapping tables define blocks of virtual addresses whose size is not a power of 16.
(One of the 88K mapping tables defined 222 bytes and a segment node defining 224 bytes would produce up to 4 hardware maps.)
Each mapping table known to the hardware has an associated header known to the kernel.
The header has a pointer to the producer of the table.
The producer is either a segment node or a page.
The critical idea behind the producer relationship between a node and a mapping table is that details of the map are determined entirely by context information recorded in the header, and the sub-memory-tree whose root is the node (or page).
Good machines have a RO bit in the map entry for each kind of table.
There are few good machines.
When a level of the map cannot specify RO accesses for the addresses it defines, it is necessary for such entries to locate lower maps all of whose entries are RO.
Otherwise two memory slot contexts that hold segmode keys to the same node may share the tables that they produce if they agree on all of the details listed above.
Each hardware table header codes those details for quick resolution of this matter.
The tables produced by a segment node are on a singly linked list thru an array of table headers.
Those table headers point back to the producing node.
Aging Tables
Most hardware memory map architectures have some bit that you can turn on in the page table entry to make that entry invalid without displacing the information in the entry that is otherwise appropriate.
The kernel occasionally turns on such a bit and calls the entry xvalid.
The real address of the page remains in the entry but the entry is invalid as far as the hardware is concerned.
When the hardware reports such an invalid entry, the kernel discovers that that entry, and the entire table that it is in, is still in use and should not be reclaimed.
The original data in the entry is still there and the kernel merely makes the entry valid once more with little work.
This is also a signal that the indicated page is still in use.
(I do not recall whether the Keykos kernel used this opportunity.)
The kernel currently has no good way to age prepared segment nodes and presumably goes to too much work unpreparing and quickly repreparing them.
We should instrument this.
Taking Page Faults
Most hardware architectures report to the privileged code just what invalid entry of what mapping table produced the fault, or which RO bit conflicted with a store.
The kernel starts from that table and locates the segment node that produced it.
The offset within the table of the invalid entry immediately identifies which slot of the producing segment node is responsible for defining the virtual address that caused the fault.
It may be that there is a good memory key in that slot and this is merely the first use of such an address for a long time.
This is repaired by locating the page or segment node.
If it is a segment node, tables are sought among those already produced by that node.
This is how real sharing comes about.
If the slot is indeed DK(0) or some other key that cannot define memory, the segment keeper is invoked, or lacking that the domain keeper of the referencing domain is invoked.
Little Keys in Big Slots
It is sometime convenient to build segments with a small size segment in a slot that would normally define a large range of virtual addresses.
This can cause the kernel to build more than one level of hardware map table to access the small segment.
These extra levels are produced by the page or segment node that defines the small segment.
The extreme example of this is a domain whose entire address is a single page.
That page will produce one table for each of the levels defined by the hardware.
Even these tables will be shared for another domain built the same way will share each of these produced tables.
It can be confusing but requires little extra code.
Keeping Current
Little in the above addresses issues in keeping the mapping tables, as provided by the kernel to the hardware, current with the wishes of the domain code that constructs memory trees by storing keys in segment nodes.
So far we have described things as if segment nodes and memory trees were constant.
We have already mentioned that the mapping tables must grant no more access than segment nodes, but we also decided to make the tables grant no more access than the segment nodes that are currently in item space in RAM — these being a subset of all of the segment nodes.
This design decision is justified by considerations that should become clear later in this note.
How may we assure that the access provided by the memory map dwindles synchronously with the node structures that authorize that access?
Keykos warrants that such denial of access is prompt unlike many access control mechanisms which merely offer to deny access at some point in the future when access is reestablished.
These stimuli, which are external to the kernel, cause the kernel to proactively tear down mapping tables, and concomitantly purge the TLB:
- Expulsion of a segment node from item space, due to congestion or destruction of the node.
- Modification of the node by a holder of a node key.
The kernel is the agent in these events and must arrange the necessary side effects upon the mapping tables.
It would suffice for the kernel to tear down all mapping tables upon displacement of a node form item space or modification of a node in item space.
This would be a simple but far too extreme an action.
Instead the kernel keeps a relation in RAM with entries that relate a particular slot in a node in item space, with a particular entry in a mapping table.
This relation is called Depend and is indexed to make access by slot fast.
A routine zap takes a slot address as an argument and invalidates mapping table entries whose construction consulted that slot.
Among the invariants that make this work are:
- Mapping entries depend only on prepared slots.
The 370 kernel omitted a class of depend entries when the logical relationship was efficiently discovered in other ways.
This saved time and space.
For instance a segment node whose slots define successive pages in virtual memory produce a mapping table with successive entries.
The production pointer from the node to the table is followed by kernel code that responds to modification to a prepared slot in a segment node.
The mapping entries corresponding to the modified slots are zapped.
Just a few such simple classes of Depend entries were thus elided from the 370 version of Depend.
The C kernel did not take this short-cut.
Congestion of depend space leads to reclaiming depend entries and zapping the indicated innocent mapping table entries, but this violates no invariants and also provides adequate aging of the Depend entries.