8.4.1 Heap allocation strategy

The heap is a memory structure which is organized as a stack. The heap bottom is stored in the variable HeapOrg. Initially the heap pointer (HeapPtr) points to the bottom of the heap. When a variable is allocated on the heap, HeapPtr is incremented by the size of the allocated memory block. This has the eect of stacking dynamic variables on top of each other.

Each time a block is allocated, its size is normalized to have a granularity of 16 bytes.

When Dispose or FreeMem is called to dispose of a memory block which is not on the top of the heap, the heap becomes fragmented. The deallocation routines also add the freed blocks to the freelist which is actually a linked list of free blocks. Furthermore, if the deallocated block was less then 8K in size, the free list cache is also updated.

The free list cache is actually a cache of free heap blocks which have specic lengths (the adjusted block size divided by 16 gives the index into the free list cache table). It is faster to access then searching through the entire freelist.

The format of an entry in the freelist is as follows:

The Next eld points to the next free block, while the Prev eld points to the previous free block.

The algorithm for allocating memory is as follows:

1. The size of the block to allocate is adjusted to a 16 byte granularity.
2. The cached free list is searched to nd a free block of the specied size or bigger size, if so it is allocated and the routine exits.
3. The freelist is searched to nd a free block of the specied size or of bigger size, if so it is allocated and the routine exits.
4. If not found in the freelist the heap is grown to allocate the specied memory, and the routine exits.
5. If the heap cannot be grown internally anymore, the runtime library generates a runtime error 203.