Every OS whose insides I have learned of has an array, the core table, and usually by that name. There is a one to one correspondence between core table entries and physical RAM page frames and the core table indexes correspond closely to the physical page frame numbers of the hardware. A few instructions can transform a core table index into the physical address of the page and conversely. A core table entry identifies the occupant of the corresponding RAM page frame. (RAM replaced core in about 1969.) The list of free pages frames is likely chained thru the core table.

Keykos

Page identification in Keykos is via the CDA, or coded disk address which is found in the core table entry for each occupied page frame. The core table also holds the allocation count which distinguishes serial tenants of one disk page frame. The core table is also the head of the backchain of prepared keys that designate the page. If a page is deallocated the space bank invokes its range key to disable all extant keys to the page. The kernel responds by locating the core table if the page is in RAM and immediately zapping all of the prepared keys to that page. Whenever a key to the page is unprepared, the core table entry is marked to so indicate. In this case the allocation count of the disk page frame will be incremented so as to cause a mismatch if preparation of remaining unprepared keys to the old page were to be attempted.

The allocation count for disk page frames is kept in the key area of the older IBM CKD disks and otherwise in a special page sized disk block called the allocation pot which is found regularly scattered among the disk page frames. If an unprepared disk key to a page is zapped, the allocation count in the allocation pot is incremented.

When it becomes necessary to remove a page from RAM, its core table locates all of the keys to the page. All page table entries for the page must be invalidated. When a page table entry for a page is created it is by virtue of consulting some node with a key to the page. All page keys to the page, and thus all nodes holding such keys will be found. Considering the location of the key in such a node and consulting the production chain rooted at the node’s node frame, we find all of the page tables which might hold entries to the doomed page. These production chains determine a many to many relation between segment nodes and mapping tables. If a slot of a segment node is consulted to build a mapping table entry (upon a mapping fault) then the production chains will record this and make it fast to find the tables produced by any segment node. In the obvious cases a segment node produces only one sort of mapping table. Exotic, perhaps non-sensical memory trees, can cause one segment node to produce tables are several levels. This is merely confusing and not a security problem. It is necessary to think about while writing the code. It costs nothing to allow it and would require complex semantics and obscure code to prevent it.

See about prepared segments for a fuller description.