Why Cap Pages?

[Jonathan S. Shapiro]

On Mon, Mar 2, 2026 at 11:11 PM William ML Leslie <william.l...@gmail.com> wrote:

On Tue, 3 Mar 2026 at 16:59, William ML Leslie <william.l...@gmail.com> wrote:

There might be some tricks we can use to get there.  An algorithm for building ... precliques? comes to mind.  We have shared weak address spaces, processes that add mutable storage on top of those, and endpoints that connect processes together.

Endpoints and cappages.  I don't think we know clearly yet just how extensively people will use cappages but I guess that's the challenging part.

Circling back to this, though I will take these up in separate replies.

Cabbages are a terrible solution for capability storage. Words to live by. Thanks, gmail! :-)

CapPages are too. :-) The first problem they solve is that a few objects need to store capabilities in bulk. The second problem is that we sometimes want to pass capabilities as function arguments (e.g. in libraries). With capability pages you can hypothetically build a shadow stack for capabilities, but that requires more significant compiler modifications that we haven't ever gotten around to doing yet. Tagged memory would remove the need to have a different kind of page or a shadow stack, because it would allow capabilities and data to be commingled in the same page. One way or another we really need that part of the user-visible programming model not to suck.

In KeyKOS, the practice was to leave capabilities in the capability registers, effectively using some of them as global storage allocators. From the compiler perspective, they look like static register allocations.

Maybe it's just the applications I happened to try to write first, but I found "all caps have to go in registers" constraining even for surprisingly simple applications.

Jonathan

[William ML Leslie]

On Wed, 4 Mar 2026 at 13:54, Jonathan S. Shapiro <jonathan....@gmail.com> wrote:

On Mon, Mar 2, 2026 at 11:11 PM William ML Leslie <william.l...@gmail.com> wrote:

On Tue, 3 Mar 2026 at 16:59, William ML Leslie <william.l...@gmail.com> wrote:

There might be some tricks we can use to get there.  An algorithm for building ... precliques? comes to mind.  We have shared weak address spaces, processes that add mutable storage on top of those, and endpoints that connect processes together.

Endpoints and cappages.  I don't think we know clearly yet just how extensively people will use cappages but I guess that's the challenging part.

Circling back to this, though I will take these up in separate replies.

Cabbages are a terrible solution for capability storage. Words to live by. Thanks, gmail! :-)

CapPages are too. :-) The first problem they solve is that a few objects need to store capabilities in bulk. The second problem is that we sometimes want to pass capabilities as function arguments (e.g. in libraries). With capability pages you can hypothetically build a shadow stack for capabilities, but that requires more significant compiler modifications that we haven't ever gotten around to doing yet. Tagged memory would remove the need to have a different kind of page or a shadow stack, because it would allow capabilities and data to be commingled in the same page. One way or another we really need that part of the user-visible programming model not to suck.

They are clunky, but they can be made to work.  I think I've done a heap allocator out cappages in one of my branches.  The Coyotos-large runtime includes a capability stack but you have to use it manually.

I've been writing a C generator from CapnProto schemas, and CapnProto separates pointers to composite objects from data.  Most usage of capability pages looks very similar, where you've got a pointer (caploc_t) in your data to the relevant cap.  It's weird, but you can do it.

I think the CapTP-style 4-tables has some space advantages over directly using cappages, especially when you have eq.  I don't know what to do about that.

 

In KeyKOS, the practice was to leave capabilities in the capability registers, effectively using some of them as global storage allocators. From the compiler perspective, they look like static register allocations.

Maybe it's just the applications I happened to try to write first, but I found "all caps have to go in registers" constraining even for surprisingly simple applications.

Anyone wondering the degree to which this is true is invited to enjoy coyotos/src/base/domain/ElfSpace/ElfSpace.c:process_fault().

Registers also don't extend to async very well, my current model basically doesn't support them, if you want to do async you need to move everything into memory somewhere.

--

William ML Leslie

A tool for making incorrect guesses and generating large volumes of plausible-looking nonsense.  Who is this very useful tool for?

[William ML Leslie]

> I don't think we know clearly yet just how extensively people will use cappages but I guess that's the challenging part.

Just to expand on this: at least for existing programs, I guess we'll have roughly as many capabilities as they currently do open file descriptors.  Outside a few pathological cases (valgrind?), that's hundreds of thousands at most.  So, I don't think they will have such a big impact on GC.  Just a guess from when I was attempting to write the glibc integration.