2.2.1 VFreeList

The uses of VFreeList [VFL] have been described, but the overview of it’s inner functionality have remained obscure. The operation of this object is elaborated.

The basic principle of the implementation for VFL is that of a list. In a normal environment, one would typically declare some sort of struct or class and either alloc or new blocks of memory. A possible scheme for indexing this memory might be to use an array, itself allocated from the heap, or possibly on the stack. Clearly in this environment we have no heap already available for implementing such a scheme.

The obvious solution is to allocate sysmem in the same way as for heap. In it’s own right this is simple and straightforward because the size of the objects that are to be stored is known. Unfortunately we have no prior knowledge about how many objects are to be stored. The solution to this problem is similar to many of the heap based functions that use this memory manager.

On instantiation it is possible to specify a break size to VFL. Once exceeded the system allocation is incremented by the break size. Should the content of a large allocation fall below the next lowest break interval then the overall allocation is reduced by the break size. In practice the expansion and reduction of the sysmem block used by VFL exhibits hysteresis, to minimise calls to the system allocation functions which are assumed to have significant performance overhead.

A significant issue with such a module is to determine the allocated / free status of the data space within the owned sysmem block. Clearly this is the same problem as that of VMM. Here the problem is simplified to a degree, because the elements of this object are of fixed size, rather than byte oriented. In essence, for a given byte count there are less elemental allocation boundaries.

All this leads to an allocation scheme similar to that of a filesystem. Essentially a bitmap is used to indicate the allocation state of each of the size prespecified cells within the sysmem block. The bitmap resides at the start of the block, and the first cell is located immediately after the bitmap.

The basic concept of the bitmap is that a single bit in the map represents the allocation state of a single cell in the sysmem block. In practice it is found, much like the VHeap problem, that iterating (in this case the bitmap) to find a free cell is a time consuming process. Unlike the overall memory manager there isn’t really an option to keep this problem in check by adding functionality. In this case the problem is addressed by a moderate increase in data size.

The basic allocation map is held closest in memory to the data cells that it represents, and as one approaches the base of the sysmem block one finds higher level bitmaps that represent groups of cells. Since the memory manager has been designed for a 32 bit system, a bit in the next higher level map represents a 32 bits in the lower level map. This process continues until all cells can be described by a single 32 bit word. As with the whole unit, recompilation for a 64 bit environment is a relatively straightforward task.

The allocation state of a higher level bit is set when all bits of the corresponding lower level word are set, and if a single bit in the lower level word is cleared then the higher level bit is cleared.

Tests on the bitmaps when seeking a free cell are two phase. The initial phase tests the entire word in a single cycle checking for a free bit. If a free bit is not found, then testing moves to the next word. If a free bit is detected, then the word is examined to find a specific free bit. This process repeats from the top level map through to the cells, using the identified free bit as an offset into the next map, or cell array in the case of the lowest level table. Using this scheme the first free cell in a sysmem block can be found much faster than iterating the actual cells directly.

The following diagram shows the arrangement of the sysmem block in VFL;

When the size of the cell array is changed, the size and count of the allocation bitmaps is adjusted to suit. During a resize it is necessary to move the bitmaps and cell array in relation to each other by copying and presetting ranges of memory. It is clearly critical that offsets for the various bitmaps, the actual cell array and the size of the table can be calculated fairly quickly.

The most efficient means for calculating these offsets is mathematically to take logs, which inherently causes one to use the floating point unit. This is by far the fastest way to calculate the offsets, but it is a problem to use the floating point unit for calculating highly consistent integer offsets. Great care has been taken to ensure reliable range checking, and a value of epsilon has explicitly been defined to ensure the appropriate precision for the task.

Where;

• The requested cell count is Nc
• The integer count of bitmaps required to describe the cell array is Mi
• The fractional count of bitmaps required to describe the cell array is Mf
• The index of a bitmap is m
• The size in 32bit words of a bitmap is SM(m)
• The offset of the cell array is S

The final issue in respect of VFL is associated with resize. Although the bitmaps are maintained to allow a fast find of a free cell, an allocated cell count is also maintained. This allocated cell count is used to determine when to expand and contract the sysmem block. Although cells are naturally allocated from the bottom cell array, it is still possible and actually beneficial to contract the cell array where allocated cells are freed from the bottom of the cell array, and leave a “free hole” in the cell array.

It has already been described when compaction takes place but it is important to note that the compaction operation will only occur when the allocated cell count falls below the hysteresis threshold.

When VFL allocates it returns a reference to the allocated block. This is much like the pointer VMM passes back to the user and for similar reasons, already discussed. Compaction requires that some cells move in memory, and this is inconsistent with the fixed reference passed back to the user. VFL provides a virtual function which notifies the user when a compaction operation is taking place, and updates a given reference. It is critical that these notifications are acted on because the integrity of the whole application depends upon them.