We describe here the low level mechanisms that Keykos uses to allocate persistent space. Even transient space in Keykos is persistent; it has ‘just in case’ disk space allocated to it even though its allocation, use and deallocation may require no disk operations. There are scenarios where application code could use these mechanisms. Normal application code is ignorant of these details.

Space in Keykos is segregated into space for data and space for keys (capabilities). Pages hold data and nodes hold keys. Some applications are cognizant of pages and nodes. There are these objects we consider here:

These are all kernel constructs. To a page or a range there is a key. (There is also the RO key to a page which we do not discuss here.) There are the corresponding three sorts of object with ‘node’ in place of ‘page’. We speak only of pages here; node logic is the same. A disk frame is a place on disk at a particular physical disk address. All disk page frames are the same size (4KB so far) and all disk node frames are the same size (16 key slots occupying about 220 bytes). Disk page frames are one or several disk blocks but node page frames are consolidated into ‘node pots’ which we do not discuss here.)

There is no mechanism in the kernel to produce range keys; range keys are necessarily primordial and exist in slots of nodes already as the big bang begins. As far as kernel code is concerned ranges can overlap but the plan is that keys for such overlapping ranges will not exist. In current practice only the root space bank holds range keys.

A range key is ‘for a span of disk frames’, in fact for disk frames with contiguous coded disk addresses. (The specific range is included in the representation of the key.) There is an order on the range object to return the page key for one of the range object’s disk frames—which frame is relative to the span; the offset is specified in the order.

Another order on the range passes a page key and if the range is for that page, the relative offset within the span is returned.

Another order zeros the data in the specified page. This is done without disk I/O even when the page is not in RAM.

Another order rescinds all page keys to the specified page.

range notion Underlying mechanism
Maybe merge this into that