The Allocation Count

In the Keykos system, the allocation count changed its size at one point and was renamed “allocation ID”. I will use the old term, or AC, here as it is still more familiar and seems more natural.

A page or node 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 and return a new key. 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) and in fact replaced by DK(0) as soon as the kernel notices them, generally in the process of preparing 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 key backchain suffices to rescind all keys. 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,
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 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.