Heap Memory Allocation








Heap definition

The heap is allocated from a predefined section of memory. Facilities are provided for user expansion of the heap to mass storage, although the current code makes no provision for page management. When the heap is initialised, a free block and an end block are created. The end block is of zero size, and is used only as a marker. The address returned by ALLOCATE and RESIZE is the address of the first data byte, as is the address consumed by FREE.

The heap MUST be initialised before use by calling INIT-HEAP. Heap access words return status=0 for success, and status<>0 for error.

Two equates are required during compilation to allocate a contiguous block of RAM for the heap.


  STARTOFHEAP is the start address of the heap
  SIZEOFHEAP is the size of the RAM for the heap

There are two versions of this code provided. HEAP32.FTH is provided for 32 bit targets and is optimised for the VFX code generator. HEAP16.FTH is for 16 bit targets, and is optimised for code density.

16 bit targets - HEAP16.FTH

The heap is controlled using two cells per block. This information is used in three parts:


cell = #bytes, number of bytes in this block
cell = flag, split between a four bit and a 12 bit field

The top four bits of the flag are used to indicate the block type, where $E = End, $F = Free, $A = Allocated. Others may be added later for type management.

The bottom 12 bits of the flag are currently unused, and should be set to zero.

32 bit targets - HEAP32.FTH

The heap is controlled using a single cell per block. This information is used in two parts:


bits 31..24: $EE - End, $FF - Free, $AA - Allocated
bits 23..0: 24 bits for number of data bytes in block.

A consequence of this is that the maximum block size that can be allocated is 16Mb-1 bytes.

If you use a pre-emptive scheduler or need to use the heap routines inside interrupt routines, you must define suitable heap lock and unlock routines and set the equate LOCKHEAP? to non-zero.

LockHeap=0

no heap locking

LockHeap=1

heap locking by turning off interrupts

LockHeap=2

heap locking by semaphore.




Gotchas

The heap routines must be protected if they are to be used both in normal code and in interrupts. In this case the code must be modified to be interrupt safe, but this may have a significant impact on interrupt latency. Examples may be found in HEAP32.FTH.




Glossary

The glossary does not include all the factors used in the code. If you are interested in the implementation, please read the sources.

: allocate      \ #bytes -- addr status
Attempt to allocate some memory from the heap. Walk the heap looking for a single big enough block. If the block is larger than than required split it into two blocks. Allocate part or all of the free block. Status=0 for success.

: free          \ address -- status
Attempt to free a heap block. Status=0 for success.

: resize        \ addr1 size -- addr2 ior
Try to resize an allocated block to a new size, allowing for alignment. If the existing memory block is not big enough, the data will be copied to a new block, and the returned addr2 will not be the same as addr1. Status=0 for success.

: init-heap     \ -- ; initialise the heap structures
The heap is initialised by creating 2 blocks. Block 1 starts at the beginning and is marked as a free block. Block 2 Is a null marker at the end of heap space.




Diagnostics

: size          \ addr -- currsize | -1
Return the size of an allocated block or -1 if there's an error.

: .heap         \ -- ; display heap info
Walk the heap displaying block information.

: heapok?       \ -- t/f ; check heap
Walk the heap and return TRUE if the heap is "well".