Heap memory manager

How do we represent the notion of a heap memory in avr assembler? How to organize an efficient yet simple memory allocation and deallocation? How to track which address is free and which is reserved?
Having an answer to these questions will unlock the possibilities of working with dynamic data structures like trees,linked lists,hash tables and all sorts of dynamic stuff in the realm of 8bit CPU context.

We will build a heap manager working over the same user data type using 2 arrays - first array to store linked list of free addr indexes and second one to store the user data - corresponding to each addr index from the first array. It is important to understand that pointer here is used in the context of array index rather than physical RAM memory address.

As we know the array in memory is represented as a sequence of memory locations and each element in it could be calculated by adding an offset from the beginning - in other words - calculating the physical address is a matter of adding the array index(offset) to the beginning of array address.

The address index array on Fig.1 represents a simple linked list array of free/not used index positions. The given heap structure represents array index value order right after the heap manager is initialized.

Each array element stores the index position of the next free address index. The last element has 0 value, which indicates the end of the linked list. The heap manager stores the head of the linked list in global memory variable to keep track of the first address index ready to be reserved/allocated. In order to use index value 0, array indexing starts from index 1, something to be taken into account when implementing the heap manager.

Heap manager uses address index 0 to denote special heap conditions:

• 0 value which signals the end of free address list
• 0 value for reserved addresses to avoid double freeing a memory location

As Fig.1 implies - free linked list is 1 element bigger than data list because one element of it denotes the end of the list.

Allocation

Let us assume that heap consists of 4 data memory locations and see what happens after 4 consecutive  allocation calls.

Following the same allocation algorithm, the next 3 consecutive allocation requests will lead to state on (Fig.3) where linked list head points to the end of the list. If another allocation call is issued, the heap manager needs to signal the callee that no free memory is available - heap memory is reserved and only deallocation call could change its state.

Deallocation

Let us assume that 3th callee frees/deallocates its address index 3 (Fig.4).

Heap manager stores the value of list head 5 in the newly returned address index element thus keeping the integrity of the free linked list. Head of the list now stores the last returned address index 3, which is ready to be reserved/allocated again.

Assuming that 3 deallocation calls happen in the following index order {1,4,2}, will lead to  heap memory state of Fig.5. It is obvious that free list head points to the last released index, which will be the first to be allocated again on next allocation call.

Heap manager implementation on byte size user data.

/*
Heap memory manager implementation
* 2 arrays representation of dynamic memory allocation and release
* 1 byte data size
*/

//up to 255 memory addresses (1 address reserved for the end of list marker)
#define DYN_MEM_SIZE 5

#define DATA_SIZE 1 ;byte size data

.dseg

.byte DYN_MEM_SIZE

//data size is 1 byte data:
.byte (DYN_MEM_SIZE-1)*DATA_SIZE    ;array of user value

.cseg

.ENDMACRO

*@PARAMS:
*@USAGE Z,temp
*/
ldi    ZL,low(data)
ldi    ZH,high(data)
clr temp
ld @1,-Z
.ENDMACRO
/********Write pointer referenced value*************
*@PARAMS:
*@USAGE Z,temp
*/
.MACRO _WRITE_REF_VALUE
ldi    ZL,low(data)
ldi    ZH,high(data)
clr temp
st -Z,@1
.ENDMACRO

/********Init heap manager structure*************
* Initial state all addr are free for alloc
* Zero addr index is reserved for end of list marker. Offset the address index with 1
*            temp
*/
init:

ldi temp,1
loopin:
inc temp
st Z+,temp
cpi temp,DYN_MEM_SIZE  +1
brne loopin

//nullify the last addr cell value,mark the end of the free address list
ldi temp,0
st -Z,temp

ldi temp,1
ret

*Allocation could fail if short of memory
*if T flag is set -> no memory available
*@USAGE:    Z,axl,temp
*@OUTPUT:    axl: pointer / index
*        T flag: 0 success;1 failure
*/
alloc:

clr axl
ld axl,-Z      ;get content of the head addr index;index starts from 1

tst axl
breq no_memory_available

mov axl,temp    ;return free addr index

;mark reserved address with zero to guard against freeing address many times
clr temp
st Z,temp

rjmp memory_available

no_memory_available:
set
ret

memory_available:
clt
ret

*@INPUT:
*@USAGE: temp,axh
*@WARNING: there is a marker 0 test to prevent freeing address many times
*/
free:

clr axh

ld axh,-Z
tst axh
breq free1
ret
free1:
st Z,temp      ;get content of the head addr index;index starts from 1

//st -Z,temp