The Allocation Count

In the Keykos system, the allocation count changed its size at one point and was renamed “allocation ID”. Here we use the old term, or AC, as it seems more natural.

Pages and nodes are alike for the purposes of this note and we will speak here only of pages. A page frame on the disk will be occupied by successive tenant pages. When a page is sold back to a bank the bank uses its range key to rescind all outstanding keys to that page. This note is about how the kernel rescinds keys.

In the page header there is an allocation count, (once it was 16 bits but now 32 bits), that is duplicated in unprepared keys to the page. Keys whose AC does not match that in the page header are observed as DK(0) outside the kernel and in fact replaced by DK(0) as soon as the kernel notices them, generally in an attempt to prepare them. The page header is something that stays with the page thru checkpoint restarts. When the AC is incremented in the page header, extant keys to the page appear to vanish.

Actually there is a bit in the page header that remembers whether any prepared key to the page has become unprepared, for if there are no such events, zapping the keys on the page’s backchain suffices to locate and rescind all keys to the page. Ditto nodes. The 32 bit AC thus will not increase more quickly than I/O. The range key returns an error if the AC cannot be incremented. Such a page is “worn out” and cannot be resold.

It is easy also to imagine a background kernel job that every few years:

Scans the page headers looking for large ACs,
Selects and keeps a list of a bunch of them in RAM indexed by their respective CDAs,
Marks the selected pages that are in RAM,
Passes over all the nodes, including on disk, in order to see all the keys in the world,
Zaps stale keys to selected pages,
Zeros the ACs in current page keys to selected pages,
Rescans the page headers setting the ACs of selected pages to 0.

A few extra tests are necessary in normal paths if normal system operation is to continue during this process. The reader will see, however that the information is always available to proceed even as these phases proceed. Checkpoint during this process can be avoided by choosing the bunches small enough so as not to unduly delay the checkpoint.

Almost exactly the same goes for nodes except nodes have in addition to the AC the call count which is duplicated in current resume keys to root nodes of domains. This count is incremented in the node when a resume key is invoked, unless no resume keys for this node have been unprepared. This ensures that other resume keys die upon restarting a waiting domain.

The page headers on modern disks live in periodically placed page sized pots on the disk, scattered regularly among the pages. One pot read gets a bunch of headers. They are cached in RAM as are node pots and user pages. Node headers live in node pots next to their nodes.

All of this logic might be simplified with a classic object table with an entry per object. But we avoid several costs with our allocation count logic:

Frequent indirections thru the table,
Space for the table; is it swapped? (no other kernel thing is swapped), Its core cache would probably very sparse and inefficient.
When a page is sold, do we use a new table entry? Either answer has problems.