How to Access a Thing under Capability Discipline

What’s in a Name

This note is related to this (not to mention this & this).

Within a program which is a client of a platform (OS, kernel) there are constructs which might be viewed as objects with the obligation to protect their invariants against other parts of the same program. Some programming languages make this feasible. This note, however, is about platforms that extend such protection to objects in various languages, even machine language, interoperating with each other. ‘Program’ here means a client of such a platform.

The state of most modern programs is a set of data structures linked together with ordinary addresses which are in fact integers; one structure may include the address of another.

Most programs relate to a small fixed number of things (acquaintances) each of which is defined by code in another protection domain. A few programs by their charter need to relate to a dynamic set of such acquaintances. Some programs will be an assemblage under the discipline of some computer language of several sub-programs each protecting their own integrity. Several of those sub-programs may each have platform level capabilities unknown to other sub-programs. Such collections will hold a dynamic set of capabilities.

This ‘protection talk’ is true even of Unix where details of how and where files are stored is managed by the kernel, in its own protection domain.

This note is meant to transcend Keykos but I locate Keykos in the landscape that I paint here. There are two sorts of programs that run in Keykos, those entirely written for Keykos—the natives, and those imported programs such as compilers. All of the Keykos natives but two have a small fixed number of acquaintances and the slots for the capabilities to these acquaintances are fixed as the application is built. The Keykos loader and command language interpreter (shell) were both in need of a variable number of capabilities. The imported programs each ran in a domain with a keeper that fooled the program to thinking it was in Unix—even X11 thought so. On the 370 we emulated the CMS environment for the IBM compilers. In each case these complex programs have simple demands on their environment.

What and Where are capabilities?

I know two general solutions to this. They are both represented in Hank Levy’s Capability Based Computer Systems.

Integrated Capabilities

In this vision words of memory can be marked by the hardware so that a program with normal access to those words can neither read nor write the bits within. They can copy those words to other words to which they have normal access whereupon the new word is likewise opaque. They can copy such words between memory and special ‘capability registers’ where they are still opaque. These words hold capabilities and besides copying them they may be invoked probably by system calls to the privileged kernel who can see the bits. Such calls thus directly land in code with infinite authority, or shortly thereafter in code with different authority. Variations on these capabilities might contribute to the calculation of an ‘address’ of data where the program has high performance access to data contingent to holding that capability. Note the quotes on ‘address’.

Some think that C compilers might be modified and other hardware changes made so that C programs written without capabilities in mind will run correctly even while protecting against remaining bugs in those programs. This would surprise me but I would love to be surprised. Even allowing small changes to those programs would make this plan worthwhile.

IBM’s System 38 was of this plan but that system has perhaps evolved away from the plan, perhaps for the wrong reasons. I would love to know.

Segregated (or partitioned) Capabilities

In such platforms as these capabilities still have addresses but they are numbers which serve as an index into a C-list. All ‘normal addresses’ hold data whose bits may be read and written by the program. The C-list is in fact kept in protected space but space known to the kernel to be owned by the program much as its normal address space. For simple native programs there is usually a small known limit and C-list indexes are assigned as the program is built, or even sooner. For programs with dynamic requirements some ‘library routine’ running with the program’s authority and probably in the programs address space must dynamically allocate C-list numbers much as malloc allocates dynamic memory requirements for data. In this plan the program’s data structures probably hold C-list indexes and there is often a requirement for reclaiming them just as there is for data. Garbage collection should serve as well here as it does for data and indeed reclaiming C-list space should probably be integrated into any normal GC.

The Register

Not all capabilities and all data are in addressable memory. Just about all computers today define the state of a running program as including the state of some registers. In conventional machines registers hold data. What of capabilities? The 370 Keykos adhered to the parallel between data and caps and decreed 16 capability registers to complement the 16 data registers. Of course the cap-regs were a figment of the kernel. The Plessey 250 had real capability registers to hold caps with special load and store commands to move caps between those registers and capability pages. Thus we have another orthogonal architecture dichotomy, or perhaps this is only an implementation dichotomy. In Keykos you could ‘load a capability register’ but at the cost of about 120 kernel commands.

A closely related decision is whether to have ambidextrous registers that can hold either data or caps. Keykos did not; it had two register sets—one was interpretive. Consider how the common library command memcpy is to be implemented for systems with integrated memory.

Indirection

Indirection seems to be necessary for general revokability and it has other uses. The indirection mechanism must be via something which is itself named and controlled by a capability. Capabilities that are invoked by sending a message (calling, returning, etc.) can be made indirect by a normal intervening object that passes on the message. A capability to access memory with plain load and store instructions is another matter. Much of Keykos was inspired by noticing that conventional memory maps were indeed pretty good capability mechanisms. We observed that to have a page table in your address space was like holding a capability; one has a powerful indirection mechanism. The concept map worked at all levels of the hardware address map. The Keykos segment provides for sharing, copy on write, and other common patterns used by conventional kernels to be done in user code. The TLB did not interfere with this view. Burroughs systems lacked indirect memory access and I think that this led some to claim that capability systems could not revoke. I do not know how other capability systems handle memory indirection.

Behind the Scenes

The objects that capabilities designate occupy real physical space. This space must be allocated and in most platforms the objects must be occasionally moved about to different physical addresses and perhaps to different sorts of media. This moving is typically orthogonal to the logic of the object owner. When it is necessary to reclaim the space of an object one must be sure to disable all the capabilities before allocating the space to new objects.

Capability systems differ considerably in what indirection is used between the program held opaque bits of the capability and the physical address of the denoted object. Each level of indirection needs some form of ‘inverted index’ to facilitate following the pointers backwards from the physical address to the capability. We should not forget indirection levels mentioned above when the data structure includes a C-list pointer instead of a capability. Reallocating a page frame in SDRAM must be preceded by removing TLB entries, memory map entries, and information that instructs the program that builds the memory map.

Logical access to memory may traverse a number of nodes (capability pages) and these logical indirections must be shortened to the real TLB. If any of these logical links are disrupted the TLB and its proxy causes must be nullified.

One frequent pattern to solve many of these problems is the ‘Object Table’ thru which all references go. It suffices to zap the entry in the object table upon deallocation but then one must eventually reclaim space in the object table. That may be less frequent but a still difficult task.

Keykos used one principle to ensure that reclamation never involved disk I/O: Never write physical SDRAM addresses to disk. Instead convert those addresses to disk addresses even if the designated object is not on disk and never will be. It is easy to allocate a disk address, it is merely expensive to actually write it there.

In a sense the item space of Keykos serves as an object table. It is accessed not by index but by hash of the disk address of the home of the object. (Most objects are born and die never going to disk.) The cold capability includes to coded disk address (CDA) of the designated object. The warm capability holds the address of the object in item space.

In Keykos rescinding access generally consists of modifying or deleting a node thru which that access is logically indirect. When that node is swapped in no disk accesses are needed to rescind. At most 2 disk accesses are needed to bring it in. In systems with integrated capabilities I wonder whether one must scan each page to see what capabilities there are before swapping a page out. If the real capability points to an object table, how is the swapped out page located when it is necessary to reclaim space in object table? If caps to the same thing are linked together what must happen when the user copies a cap? You don’t want to skim a petabyte of files in order to reclaim all references to some ‘object table’ in RAM. Keykos found solutions to these problems but I don’t think I have covered all of them here. Eros and Coyotos modified these solutions a bit.

The Plessey 250 has another set of solutions to these problems; I learned them twice, and forgot them twice.

Daira Hopwood sends these pointers for a course “Advanced Operating Systems” at UNSW:
Tagged, Partitioned as in ‘segregated’, Cap Systems.