To rescind

In general there is some facility, which given a capability C, will produce a pair of new capabilities <C', R> such that messages to C' have the same effects and return the same values as messages to C, until R is invoked, after which C' is useless while C lives on. The behavior of C is unchanged throughout this scenario. [In Scheme] C might be a piece of computer memory and instead of messages, load and store commands to that memory are possible. In that case C' is also memory from which you can load and into which you can store. In this case R is somewhere to which to send a message to rescind access to C'.
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.

Optimization

Revocation, as we preach it here, involves indirection which may become slow. Keykos had to confront this in architecting revocable access to memory and CPU time. Since CPU cycles and memory access are delivered to the user mode program for stretches of time without mediation of the kernel it is necessary to arrange such immediate access by conventional hardware means. The hardware provides no indirect means except insofar as the hardware memory maps are a form of indirection. Keykos semantics requires that revocation acts take place immediately—if a key-call modifies or deletes a segment node then the very next instruction after the call may safely know that the new access rules are in effect (in contrast to Unix). This describes how the kernel achieves revocation promptly yet efficiently.

When a user mode instruction accesses memory it may logically rely on several segment nodes and actually relies on memory maps produced 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.

Implementation

The abstract revocation pattern is indirection for the user of the revocable ability and write access to the indirection cell for the potential revoker. The general situation we must confront is a tree of nodes (indirect pointers) pointing towards the root which is the shared object. There are capabilities to nodes of this tree that might be used to disable or delete these nodes at any time. It was an advance to computer architectures when indirection was removed. The concrete revocation patterns that I know are:
indirection
Actually do the sequentially dependent memory accesses for each use.
tracking direct pointers
A direct pointer behaves as an indirect pointer but actually includes the direct address of the object as an optimization. Copies of the direct pointer are tracked somehow so they may be quickly found and canceled upon need to revoke. Perhaps the act of copying a direct pointer could be logged. This would not be in the critical path but it is complex and is a load. Interpreting the log seems complex, and probably a super-linear cost.
move or rename target
This assumes a faithful model of the tree probably kept by software. Kernel code would grant direct pointers which would include references to the model element. When some element is disabled the object is moved, perhaps only in virtual memory. As valid direct pointers are encountered a trap leads to code that will make new direct pointers. Vacated virtual addresses must remain vacant until a sweep is finished. This impacts cache logic. A cache purge could be avoided if there were a machine instruction to choose a cache line in some binary address range and report its address, or report ‘no such line’. This is probably infeasible with a real cache.
None of these is attractive. See how Keykos solves this, sort of.

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.

Here is a note on revocation in support of military style security. Here is a note on a system to help an individual manage the ability to rescind what he has granted to others.

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.

A Cheaper way to Rescind