KeyKOS uses a combination of techniques for invalidating entries. A limited recursion is used first, and a dependency database is also used for mapping table entries that can't be found through the limited recursion.
The kernel performs a translation from the segment tree to the mapping tables that are used by the memory mapping hardware. This translation is easily performed as needed by walking the tree from the root to the leaf. The mapping tables are like a cache of the information in the segment tree.
The difficulty comes when the segment tree is changed; the kernel must invalidate portions of the mapping tables that are no longer logically mapped. The complex semantics of segment nodes makes this invalidation nontrivial.
EROS handles this by keeping a simple database of dependencies. When a key in a segment tree is changed, the database is consulted and tells what mapping table entries must be invalidated. Some drawbacks of this method are (1) the database takes space, and (2) when full, entries must be stolen, which requires invalidating entries that are still valid.
The tree itself has enough information to find the entries that must be invalidated. Every node has a list of all the keys that refer to it (at least, all the keys that might be responsible for generating mapping table entries). The entries to be invalidated are in mapping tables that are produced by the changed node, or by segment nodes containing keys that refer to the changed node, etc. recursively.
The problem here is that this recursion can be very deep. Consider the
situation in figure 13(a) from the patent. If the key labeled 1302 is changed,
we must recurse on keys in nodes 1306 and 1308 in order to find the entry
in mapping table 1310 that depended on that key.
KeyKOS uses a combination of techniques for invalidating entries. A
limited recursion is used first, and a dependency database is also used
for mapping table entries that can't be found through the limited recursion.
When the kernel fills in a mapping table entry by consulting the segment tree, it examines a sequence of keys. The kernel will set a bit, called "involved", in each key in this sequence except the last one.
When a key in a segment node is changed, the kernel first invalidates mapping table entries in mapping tables produced by that segment node. Then it recurses on keys that refer to that segment node. The central idea of the invention is that it is only necessary to recurse on involved keys. In common cases, this limits the recursion to only the necessary keys. It may still be necessary to recurse deeply in unusual cases.
The recursion also clears involved bits whenever it discovers that it is safe to do so, but it does not go out of its way to discover when a key no longer needs to be involved (that would be expensive). In theory, pollution could occur (too many involved bits left on), but in practice I think that is unlikely.
For details, see the
patent. Some differences to note with EROS/KeyKOS:
| Patent term | EROS/KeyKOS term |
| MOR | Key |
| PMO | Segment Node or Address Space |
In the patent, PMOs can have different spans and numbers of MORs, while in EROS nodes always have 32 keys (in KeyKOS, 16).
In the patent, a MOR contains an offset, while in EROS and KeyKOS an offset must be in a separate window key. The presence of window keys would complicate the application of this patent to EROS or KeyKOS.