previousupnext

2.2 Big-Block Area Data Structure

This section is concerned with the storage of memory allocations over 4 KB in size.

That portion of LeapHeap address range not compartmentalised is devoted to big blocks. The blocks, of mixed sizes, are emplaced contiguously, starting from the lowest address in this dedicated area. Each block, whether allocated or free, is tracked by a fixed-size block descriptor. Free blocks are inevitable but undesirable because they are not used by the program yet consume memory.

A block descriptor consists of four fields:

The fields of the descriptor record have been given names that are not English words deliberately, in order to avoid ambiguities in the descriptions of the data structure and algorithm.

The allocd field is a single bit (or may be so implemented). The other three fields are multi-bit. There is a special constraint on the implementation of the nxt and penult fields: they must be adjacent in memory and their combined size must be writable atomically by a compare and exchange instruction of the target processor, explained in section 3 LeapHeap Algorithms.


The diagram above shows a trivial list consisting of two blocks, the first allocated (A) and the second free (F).

The number of active descriptors is always one greater than the number of blocks, because of the end-marker. The descriptor said to correspond to a block is that descriptor the addr field of which points to the start of the block. Note that the descriptor following that must also be read if it is required to know the size of the block.

Block descriptors are regarded as drawn from a finite pool (such as a fixed-size array of records). Threads perform insert, delete and append operations on the descriptor list, causing a gradual recycling of the pool as the program runs. A descriptor is said to be in-use if it belongs to the set of descriptors that would be met by instantaneously navigating through the list from the head descriptor to the end-marker. A descriptor that is not in this set because it has been elided from the list is termed unused. A descriptor may also be known as reused; a looser definition referring to an in-use descriptor that was recently either unused or else in-use at a different position in the list. Unused descriptors are important because it is common (in a multithreaded program) for threads to encounter them. On the other hand fresh descriptors, those in the pool that have never been in-use, are inaccessible and may be ignored.

The material in section 3.2 List Algorithm lays out the rules which threads observe when navigating and manipulating the descriptor list. The methods by which the descriptor pool itself is handled, such as how an unused or fresh descriptor is located for a thread that wishes to insert into the list, are regarded as part of the implementation.