|I recall an image like the following in a paper several decades ago on this subject:|
The general pattern is that I have C and wish to let Bob use it for a while. I create a rescindable version, Cb for Bob and retain the corresponding Rb. For Sue I create Cs and Rs. I can now rescind either independently of the other. This is ‘selective revocation’. Note that preplanning is necessary and that some extra cost is involved. Note also that when R is created, we need not know when we will decide to invoke R.
It has been suggested that all capabilities be rescindable. This falters on the observation that the ability to rescind is itself a capability and should thus be rescindable. This is indeed useful and I have seen real life contracts with such clauses. The idea that all capabilities be rescindable however leads to infinite regress.
Another possible goal is that for any capability it be possible to produce a rescindable equivalent. Keykos very nearly achieves this but fails as noted at the end.
In Keykos the start key to a non-kernel object O is used to invoke O, by sending a message to O. To build a rescindable version O' of O, one creates a new domain D instructed to relay any message that it receives to O. O' is the start key to D. To rescind O' it suffices to delete D or modify its instructions so as to cease delivering messages to O. It is like installing a fuse in a circuit. This works as well for kernel objects whose use is via sending messages (calls). This pattern works for Java, Smalltalk, Scheme etc.
Keykos delivers CPU time and memory access via capabilities that perform for their holders in ways that cannot be explained by messages to and fro. If I hold a capability to memory in the form of a segment key then I can nearly always produce an equivalent segment key except for my new ability to rescind access via the new segment key. The exception is when the segment depth limit is reached. There is a similar meter depth limit in Keykos which results in meters for which rescindable versions cannot be produced. The reason for these limits is essentially the same as why machine architectures limited the number of recursions available to indirect addressing. Machines that ignored this problem might find themselves in infinite loops during the execution of a single instruction, unable to interrupt short of rebooting the entire system. CTSS was vulnerable to the “XEC *” instruction which would require reboot.
When a user mode instruction accesses memory it logically relies on several segment nodes generally and actually relies on memory maps defined by the kernel and consulted by the hardware. (Even more actually it relies on TLB entries but we ignore that detail here.) We say that the map entries depend on the segment nodes. Such nodes are pinned in RAM while there are map entries that depend on them. Data structures are maintained by the kernel that allow the kernel to quickly find and invalidate those map entries when the segment nodes are changed. (The TLB is (selectively) purged when map entries are invalidated.)
Meters are somewhat easier. Prepared domains have a cache of time they may use, borrowed from superior meters. The kernel uses the backchain mechanism to find caches that become invalid due to cancelation by someone with a service key to a superior meter.
This troubling observation suggests that rescinding need not be prompt in order to reproduce the behavior of Unix (or at least BSD).
The schemes used by the Plessey 250 is a source of further ideas.
If there were an order on a node to renew itself this would serve to rescind all access to the node without the overhead of the space bank and it’s use of its range key. This is an efficient kernel operation. This does not support selective revocation.
It is perhaps possible to design hardware that does iterated indirection which can be interrupted and resumed without starting over. I have not seen such a design. I think it must be complex. I do not recommend it.
Perhaps the GE 635 allowed this. It had the most complex addressing semantics that I have seen. Modern machines do not provide indirect addressing or the execute instruction. For Keykos to allow accessing the memory tree to be non-atomic, would add considerable complexity to the system’s semantics regarding set of domain states.
I recommend a hard numeric limit to iterated indirection whether in hardware or software, painful though this may be.