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
|