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.

Oof, that seems like a complete deal breaker to me. My main interests are in low latency hard realtime code, and that would completely kill any RT guarantees.

I don't see it scaling well to large workloads either. Imagine a database server with hundreds of GB of memory mapped into the process, no way that you want to sweep through all the pointers in that either. And even if you do it in the background concurrently, you will eat a lot of memory bandwidth, and you risk falling behind.

Which means we are left with a small niche: small systems with no RT guarantees.

> during the pendency of a concurrent background sweep, a CoW-like scheme temporarily traps all reads to sweep specific pages on demand, permitting forward progress before the concurrent sweep completes.

Isn't there a race condition in that: if you copy the capability around you may be able to copy it from a yet-to-be-swept page to an already swept page while the sweep is somewhere in between those pages? Or maybe I'm misunderstanding you.