Flexibility of Capability Foundations

Definitions of ‘capabilities’ sometimes contradict each other. We explore some of those variations here. Two mathematicians may define the group concept differently by providing different axioms, but they really agree for each axiom set may be derived from the other set. Whereas the mathematicians converge after proving just a few simple theorems, capability systems converge after implementing a few simple objects using their respective foundations.

Capabilities always designate individual objects and the systems we consider here always allow for writing some code to define new objects. Such code is itself constrained by capability discipline. The systems we consider here all have some small fixed number of types of objects partly defined partly by privileged code and perhaps partly by hardware. There is a combination of engineering and logical reasons for the code which is not constrained by capability discipline.

Access Rights and ‘Facets’

It is common to say that two capabilities to the same object differ in the rights they convey to that object. This is the facet pattern. Some go further and say that there are bits within the capability and more bits means more authority. In the latter case a simple fast ‘hardware’ function can derive weaker caps from stronger caps to the same object. This is seductive but Keykos chose not to do this. It gets other advantages. Instead Keykos (and seL4) include a little data in the cap and let the recipient decide what it means. Most capability systems indeed provide this.

The Keykos pattern of selecting a method with the “parameter word” in the message which conveyed an integer from the caller to the callee, together with the callee’s access to the ‘data byte’ from the capability, proves a convenient and efficient method for deciding who can do what to the called object. Among these methods were the creation of weaker capabilities to the same object. Sometimes these creations were contingent on variable object state.

This facet style is not a vital kernel function; one could create ‘front ends’ that append badge like information to invocation messages but we found this kernel hack well worth the various costs.

Number Keys

Some try to limit the scope of the word “capability” to those situations where there is some real abstracted state. Keykos and some other systems are more ‘generous’ and include things like “number keys” which do little more than afford the convenience of keeping an 88 bits in an otherwise unused node slot along with related keys. We thus gain the convenience of saying that a slot of a node always holds a capability. “DK(0)” is the number key for 0 which displaces keys that denote objects that are dissolving. It is convenient to say that number keys designate numbers, but with no abstraction involved. Then we can say that every key designates something — harmless pedantry.

Segregating Capabilities

This is a decision that the hardware already makes. A few capability hardware systems have been built. Early versions of IBM’s System 38 included memory bits indicating locations holding a capability (‘tagged memory’). Later version of that system lack these tags but do not run arbitrary machine code and thus rely on trusted processing of application code to provide security. This is how Java might be said to have capabilities. I know no principled objection to this plan but I have not delved into the ramifications.

Keykos needs to run much legacy code where that plan is not available. The Plessey 250 segregates capabilities into their own pages, like Keykos, and discriminates those pages with a bit in the page table entry as well as flipping the memory parity bit.

This variation in capability systems remains visible throughout the capability savvy software within the system.

Space and Time Accountability, all the way down

Language designers very seldom participate in the art of “saying no” to programs that want more space or time. That discipline is left to some platform functionality which makes it difficult to build custom policy for space or time limits. Many capability platforms follow this shortcut. Keykos addresses space with the space bank and time with meters. Many capability platforms provide a free stack with obscur consequences for runaway recursion. The Keykos ‘Fortran II’ attitude toward the stack (there is none) is unusual here. Code that defines user objects is naturally reentrant but not recursive. Invoking a factory (which is space savvy) within a recursion loop is the obvious plan for recursive capability invocations. I do not recall that that was much needed.


I think that synergy starts at the bottom.
Similar note