2.2.2 VFreeLUT

Like VFreeList, the use of VFreeLUT [VFU] has been described. The operation of VFU is elaborated.

VFU inherits VFL and consequently gains the benefit of it’s inherent capability to implement storage of many similarly sized objects or structures. In addition to the sysmem block associated with VFL and inherited, VFU also owns it’s own sysmem block. In combination these two blocks of memory implement the sized lookup used to improve allocation performance on the heap.

VFU sysmem contains a sorted list of indices. Each index contains a length value, which is the sort field, and two references, one to each end of a descriptor linked list. The actual descriptor linked list is held by the inherited VFL sysmem. The descriptors will be covered shortly, but it is important first to consider the importance and meaning of the length value.

The length value represents the length of a free identity somewhere in one of the heaps. It represents the first stage of an alloc operation at the request of the user. For time efficiency the index lookup is sorted and resizable. Fortunately nothing directly references the index lookup, and as a consequence resizing the lookup never requires any other information to be modified as a result of moving indices during the resize. Like VFL the VFU exhibits hysteresis on resize operations, and it is possible to specify a size threshold for resize operations.

The indices must be kept contiguous because the insert and retrieve operations use a Newton-Raphson style algorithm to find the sorted location for insertion and removal. This approach requires that the data is continuous, but also ensures a minimum number of operations to retrieve or insert a given length into the lookup.

As a result of an allocation request, the nearest larger identity length that would become a set usermem length is sought using Newton's method. Once this is found the head item associated with that length is inspected and removed from the inherited VFL. If the linked list becomes empty then the index is removed from the VFU lookup. Using the descriptor an associated identity on any current heap can instantaneously be found.

The reverse is true when a new free identity is created on the heap. If the length already exists in the lookup then the a new descriptor is created and added to the tail of the linked list. If the length index does not exist then a new index is created, a linked list is created and it contains a new descriptor that refers to the new free identity.

During other operations an existing free identity, may be resized, and updates are made to VFU to maintain it’s integrity. Particular care is taken during such operations because, the usually occur as a result of a prior access to VFU. Clearly modifications to the state of VFU must be made atomically to ensure that a secondary update of VFU is not made during the period of indeterminate VFU state that exists as a result of the primary operation.

The inherited VFL of VMM is already seen to operate in a straightforward manner. There it works as a pool of VHeap objects. From the perspective of VMM there is no requirement that compaction operations update referred VMM objects.

VFU also inherits VFL, and it uses VFL as a linked list of descriptors to free identities. It is important to remember that VFL is capable of compacting the objects that it contains. VFU refers directly to the head and tail of each linked list stored in the inherited VFL, and consequently VFU must implement a handler that updates the index lookup when compaction occurs in VFL.