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.

First allocation request (Fig.2), makes the heap manager shift the head of the linked list to the address index 2, pointed to by the array element to be yielded as reserved/allocated address. Marks address index 1’s value with 0 thus preventing multiple deallocations. Address index 1 is returned to the callee to manipulate d0 data. The callee could read/write manipulate d0 user data at its own will. Since heap manager handles indexes rather than memory addresses, finding the data element to manipulate is a matter of adding address index - the heap manager returned to callee - to the beginning of data array in memory. Heap manager head always points to the next free/not reserved address index.

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 address/index
 * 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

 //heap manager linked list to keep track of free addr:  
.byte DYN_MEM_SIZE
 
 //data size is 1 byte data:  
.byte (DYN_MEM_SIZE-1)*DATA_SIZE    ;array of user value

 //head of the free list
 free_head:  .byte 1    
 
 .cseg

.MACRO ADD16
    add @0,@2 ;Add low bytes
    adc @1,@3 ;Add high bytes with carry
.ENDMACRO


 
/********Read pointer referenced value*************
*@PARAMS:
*        0:  addr index(input)
*        1:  addr value(output)
*@USAGE Z,temp
*/
.MACRO _READ_REF_VALUE
   ldi    ZL,low(data)
   ldi    ZH,high(data)
   clr temp
   ADD16 ZL,ZH,@0,temp   
   ld @1,-Z
.ENDMACRO
/********Write pointer referenced value*************
*@PARAMS:
*        0: addr index(input)
*        1: addr value(input)
*@USAGE Z,temp
*/
.MACRO _WRITE_REF_VALUE
   ldi    ZL,low(data)
   ldi    ZH,high(data)
   clr temp
   ADD16 ZL,ZH,@0,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
* when doing address indexing.
*@USAGE: Z: points to address index linked list
*            temp
*/
init:
   ldi    ZL,low(addr)
   ldi    ZH,high(addr)
   
   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
   sts free_head,temp    ;make the head point to first free element       
ret
 
 /********Allocate address index**************
 *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:
   lds temp,free_head  ;last addr index
   ldi    ZL,low(addr)
   ldi    ZH,high(addr)
   
   clr axl   
   ADD16 ZL,ZH,temp,axl
   ld axl,-Z      ;get content of the head addr index;index starts from 1

   tst axl
   breq no_memory_available

   sts free_head,axl  ;save next free addr index
   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


/********Allocate address index**************
*@INPUT:
     axl: addr index
*@USAGE: temp,axh
*@WARNING: there is a marker 0 test to prevent freeing address many times
*/
free:
   lds temp,free_head  ;last addr index
   ldi    ZL,low(addr)
   ldi    ZH,high(addr)

   clr axh   
   ADD16 ZL,ZH,axl,axh

   //is this address already freed?
   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
   
   sts free_head,axl
ret