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.
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.
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.
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.