Some Unconventional Hardware Capability Ideas

I doubt that hardware and compilers can be designed to run the large bulk of legacy C and C++ code while enforcing the rules implicit in the official definitions of C and C++ simply because most such programs occasionally violate those rules. This intuition comes partly from my own coding habits. This is a testable hypothesis by someone who knows certain compiler innards well and has a representative sample of legacy code. In short I claim that many production C programs are not strictly valid; they do conform however to an unformulated set of rules governing C on modern processors.

I do suspect however that modest additional language features can be added to C that depend on less modest new hardware features that let lightly modified legacy code run and call and be called across protection boundaries (gates), passing access to memory, with little runtime cost. I imagine the hardware costs to be in the 10% range but my intuition here is not well informed.

The central idea around which I organize these ideas is the buddy system of allocating virtual memory. Assume hardware support for a protected descriptor for any block as defined in the buddy system. We call these descriptors caps or capabilities in these notes. The buddy system is somewhat inefficient of virtual addresses but not nearly so inefficient of real memory (cache and DRAM) which is allocated only as actually used. A variation on malloc would return a true buddy block. I do not propose that all heap data be allocated in buddy blocks; only that data, access to which must be passed thru security boundaries.

I assume a virtual cache (cache tags hold virtual addresses) and those virtual addresses cannot be seen by any but very privileged platform code. This allows virtual addresses to be recycled and reassigned even as applications using those addresses continue to run. This proposal is orthogonal to the question of segregated capabilities.

Capabilities have some sort of type field as well. Keykos has 17 different key types at the kernel level and I would presume about as many here. In particular there will be RO and RW memory caps. If capabilities are segregated from data in memory, there would be RP, RW and sensory caps to cap blocks. There would be gate capabilities via which to call routines whose initial state is located by gate cap.

An access to memory is always via a memory cap designated by the code, and an integer offset within the block, provided or computed by the code. There is one data cap that is held in a special register that some load and store ops do not name; this is merely coding and execution efficiency; it suits the expectations of legacy code. Aside from conventional malloc that returns a number, there is another like routine that returns a RW cap. Legacy code can call the first and run as usual. Cap savvy code will sometimes, perhaps always call the other. The plan is to preserve C’s reputation as the universal assembler that allows one to do just about anything that can be done in assembler. Perhaps there is a compiler mode that treats all pointers as caps but I doubt that mode is fruitful.

Compilers need to distinguish between two types of pointer according to some distinction in its declared type. I adopt ★ as an alternative here for * which C uses to indicate conventional pointers. The classic malloc returns an old pointer which can be coerced to an int. Commands to access data at such addresses would be implicitly invoke a capability in a special cap register. There is no add in this for the bits do not overlap. The new malloc would return a cap (capability). To access data via a cap (new pointer) requires the compiled code to nominate the that pointer presumably by naming a register holding that cap.

Several software capability patterns depend on indirection, such as selective revocation. This is naïvely achieved thru classic indirection but the Keykos kernel achieves virtual indirection on machines without real indirection in order to achieve prompt revocation. Such access is fast to invoke but slow yet prompt to revoke.

Consider unduplicable caps (Linear Janus); call a routine passing such a cap. If you get it back you know it is only yours once again. But how to recognize it upon return? Perhaps an op on a cap yielding a recognizer and an undup-cap. The undup-cap can be invoked and moved but not duplicated. You can also make a recognizer from an undup-cap. The recognizer, brought together with the undup-cap says yes or no; yes only if it is its sibling. If you passed a RW cap then you check that you got the cap back before you consider the answer stable. If you passed a RO cap then you check before you put any new secrets there. An undup-cap can be stored in memory but then disappears from register. It can be loaded from memory, but then disappears in memory. Question: What patterns require a duplicable cap? (One pattern: weakening a cap, e.g. from RW to RO)

Another advantage of this plan over the better known ‘single shared address space’ scheme, such as HP/PA, is that virtual addresses are entirely hidden from the user and thus can be reclaimed without ruining user program states.

Meta Ops To hold top, the most powerful memory cap, is to be able to create any other cap. It may be powerful enough to recycle virtual addresses. It may be powerful enough to perform generational GC.

An abstract algebra, of sorts, is suggested here.

A precise and concise description of how caps address memory.

Some Scheme code to explore details.

There is a variety of hardware schemes that support the above ideas. With segregated storage it is unnecessary for the number of bits in a cap to be 64. The design so far does not benefit much from longer caps and non powers of 2 cap bit count makes DRAM cap storage inefficient. I do not yet have a plan for disk format of caps but Keykos never puts RAM addresses on disk.

These ideas are incompatible with this idea which exploits the memory map and TLB for their capability similarities. Just now I think that to get those functions it is necessary to have something vaguely like paging tables. I have no plans just now.