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.