Orus

Capabilities · 6 of 7

Growing the capability table, and what each way costs

If 65,024 slots ever prove too few, the table can grow in four ways. Each keeps lookup a fixed number of loads and keeps tables out of reach of capabilities; they differ in what a small process pays and how far the table grows.

The table today

The root is the first page of the process object, and holds 512 pointers. A leaf is a block of two pages, 8 KiB: a page of list nodes and a page of payloads, retyped when the process needs it. Each leaf has 127 slots, since its first node is its hidden node, so a full table holds 65,024 slots in 4 MiB of leaves. The smallest table that holds anything is one leaf.11 TableRoot and LEAF_BYTES in table.rs; NODES_PER_PAGE in list.rs. The design record is process-holds-capabilities.

Two properties have to survive any growth. Lookup is a fixed number of loads, the root, the leaf’s hidden node and the payload, with no tree to walk. And no capability names a table: if one did, a table could be reachable from itself, and deleting it could cascade without end. Revoke and delete walk the depth-first list, not tables. A leaf is reclaimed through its hidden node, a child of the untyped it came from, and the root goes only with its process.22 Tables::lookup in table.rs, and CapKernel::delete in delete.rs. The design records are revoke-by-depth-first-list and teardown-driven-by-retype.

Every way below also needs a wider index. A table position travels in one register word whose low 16 bits are the index, room for 65,536, which today’s table fills exactly.33 POSITION_INDEX_MASK in position.rs. The bits above name which table the index is in, and the design record syscall-abi-in-registers lays the word out.

WaySlotsTable sizeMemory reached, one block per slot
smallestfull4 KiB2 MiB1 GiB
Today65,0248 KiB4 MiB254 MiB127 GiB65,024 GiB
More root pages260,0968 KiB16 MiB1,016 MiB508 GiB254 TiB
Doubled leaf130,56016 KiB8 MiB510 MiB255 GiB130,560 GiB
Large-page leaf33,553,9204 MiB2 GiB131,070 MiB65,535 GiB256 TiB
Third level33,292,28812 KiB2,050 MiB127 GiB65,024 GiB256 TiB

The memory columns are the slots times the block, or the 256 TiB address space where that is smaller, as on where the budget runs out.

More root pages

A process object is eight pages. After the root and the process’s record come three pages kept for later, and the address space starts at the sixth. Using those three as root pages gives four, 2,048 entries, and 260,096 slots, with leaves unchanged. A small process pays nothing, since the pages are already part of every process, and lookup does the same loads: which root page an index lands in is arithmetic on the process’s address, not another load.44 spare_kept in process.rs keeps those pages, and SPACE_ROOT_PAGE in space.rs is where the address space starts.

It is the cheapest way, and the smallest: four times today’s table.

Larger leaves

A doubled leaf is four pages, two of nodes and two of payloads, with 255 slots. The smallest table is then 16 KiB. Retype makes small blocks of one, two and eight pages, and four is none of those, so this would be a new block size.55 small_order and order_pages in block.rs.

A large-page leaf makes each of the leaf’s two pages 2 MiB. A 2 MiB page holds 65,536 nodes or payloads, so one leaf has 65,535 slots, and the table grows to 33,553,920. The price is that the smallest table is 4 MiB, a high floor for a process that holds a handful of capabilities. The pair of 2 MiB pages is not a block the kernel’s page metadata knows either: a large block is one 2 MiB or 1 GiB region.

Either leaf is still one block that a root entry points at, with one hidden node, so lookup and revoke do not change. Only the split of the index into entry and position follows the leaf’s new node count.

A third level

A page of 512 pointers between the root and the leaf, the same shape as the root, gives 512 × 512 leaves and 33,292,288 slots. The smallest table is a middle page and a leaf, 12 KiB, and a full one is 2 GiB of leaves plus 2 MiB of middle pages. Lookup takes one more dependent load; the depth is still fixed, so lookup is still constant time.

A middle page is where a table would start holding a table, and the rule that keeps tables acyclic does not depend on there being two levels. It depends on no capability naming a table. A middle page holds pointers, not payloads, and no capability kind names it. To be reclaimed it would carry a hidden node under the untyped it came from, as a leaf and a page-table page already do.

None of these is chosen. The design revisits the table when a process needs more slots than two levels give, and the costs above are what that choice will weigh.

Numbers on this page are from kernel commit 31399c5, 17 November 2026.