Capability Revocation and Indirection

1. Every "regular" capability is really a double indirection (a pointer-to-a-pointer) in disguise. I will use the term "outer pointer" to refer to the first layer of indirection (exposed to user code) and "inner pointer" to refer to the second layer (the pointee of the outer pointer).
2. When an allocation is created, we create an inner pointer for it. When an allocation is deallocated, we mark its inner pointer as invalid.
3. Inner pointers live in a special region of address space. When it fills up with dead pointers, you unmap the whole region, and map a fresh one somewhere else. The region is not allowed to contain any object other than an inner pointer (no "real" allocations).
4. A region that has ever been mapped for inner pointers during the lifetime of a process can never again be remapped to contain inner pointers (but it can be remapped for any other purpose, so this is not a pervasive restriction and should not break anything else). malloc or its equivalent would be responsible for the necessary bookkeeping, which might involve mapping regions at some fixed or regular pattern of offsets to reduce the amount of data that you need to track.
5. When an outer pointer is dereferenced by user code, you first check the validity of the outer pointer, then check that it points to a region currently mapped for inner pointers, and finally check the validity of the inner pointer.
6. In principle, you could run out of address space doing this, but that ought to take a rather long time if we're using 64-bit addresses. If we really insist on reusing inner pointer regions, one option could be to give each mapping and each outer pointer a generation number, but CHERI pointers are already wider than standard pointers, and I'm not sure this is worth it. Besides, then you're just running out of generation numbers instead.

I know that double indirection is significantly more expensive than single indirection... but sweeping address space not only seems like it should be similarly expensive, it gets slower the more memory we allocate (whereas double indirection is a fixed cost per dereference). How much memory do you have to allocate before you hit the break-even point?

The other obvious question is how much of this you can hardware-accelerate, and to what extent.