Keys live only in nodes whether in RAM or on disk. Node pots are page sized vessels for nodes with consecutive CDAs. They have a coded disk address (CDA) that can be computed from the CDA of the node. RAM is used to cache node pots, from the disk, just like pages.
A key in a slot of a node in a pot is 12 bytes long. Its format there depends weakly on its type. For types that designate pages or nodes the key is a 1 byte type field, 1 byte data byte, 6 byte CDA and 4 byte allocation count. A number key is just the type byte and 11 bytes of number. With other types, it depends.
To find a node from its CDA look first in item space where hash chains link nodes whose CDAs hash is the same. If the node is not there, its node pot is identified by its own CDA = f((CDA of node)/(nodes / pot)). (f is a small associative function.) See if its disk node pot is cached in RAM. If the pot is not in RAM we do page like faulting to get it there. We allocate a node frame in item space and copy the node to the frame, expanding each keys from 12 bytes to 16 bytes. This expansion again weakly depends on the key type.
Slots in nodes in item space are either prepared or unprepared and a bit in the slot indicates which. Just after the node has moved into its item space frame its keys are all unprepared. Most keys, depending on type and transaction, must be prepared to participate, except number keys are never prepared.
The key precepts about prepared keys are that:
A prepared key holds the RAM address of what it designates. Prepared keys that designate the same thing are doubly linked together by the backchain thru their slots. The backchain passes thru the designated thing so that the keys may be quickly found starting from the designated thing. The backchain is doubly linked so that a slot may be quickly removed from the backchain when the slot is made to hold a key pointing elsewhere. When the CDA or allocation count are required for a prepared key, they can be found in the designee, whose RAM address is in the prepared key.
In summary the prepared key consists of:
Prepared keys are adaptive formats.
The origin of “Item Space” is obscure and is not now relevant. It might become relevant once again, however so I will explain.
The first 370 kernel used 8 byte keys in item space. A prepared key requires 3 pointers and the early kernel used 16 bit “pointers”. 16 bits isn’t much of a pointer range so we allocated an array of 8 byte items. Pointers within prepared keys only located things in item space. A 16 bit pointer was really a signed index into this array called item space. The index was signed to suit the instruction set of the 370. The virtual origin of the array was usually outside of the real array. The virtual origin was in a known register for most of the kernel. Node frames, the core table, queue heads, and a few miscellaneous things that need to be located by keys, were allocated in item space on 8 byte boundaries. A node occupied 19 consecutive items; three for the node header and 16 for the respective slots. Item space was thus 512KB which was ample in that early era. Nodes occupied the majority of item space. The core table occupies contiguous item space too—two items per core page frame.
See ‘backchain’ above for the predominant use of these pointers. Very often in following these backchains which link keys together it is necessary to also visit the head of the node in which the key resides. One could convert the pointer into an item index, reduce modulo 19, convert back to a pointer, but there was a multiply that would accomplish this accurately and directly. This is a trick that I learned from reading the ‘Program Logic Manual’ for IBM’s ‘PL/I Checkout Compiler’ which was written in 360 assembler language.
The most recent 370 kernel uses 16 byte items and a prepared key has three 32 bit standard pointers.
There is now some migration to platforms where pointers are naturally 64 bits long. I belong to the school that believes infrastructure should expend some effort at being efficient. How much item space could be used with 32 bit indexes into an array of 16 byte items? A node frame, which includes a header, occupies 19 items. A core table entry is 2 items. This leaves room for 190M node frames and 190M core table entries. This is a 64G item space which is about right for a machine with 760G of real RAM.
A more modest hack which is better supported by extant compilers is to let a kernel that runs in 32 bit mode administer a machine where some domains run in 32 bit mode and others run in 64 bit mode. With nearly 4G for the kernel’s working space, this would suit a machine with about 80G of real RAM. This is not much of a mod to the current kernel. The main changes are to deal with page frames at real addresses larger than 32 bits.