Skip to content

09. Memory Allocation - Managing the Heap

In a bare-metal OS, we don't have the luxury of malloc and free provided by the standard library. We must implement our own memory allocator to manage the heap.

Memory Layout

Our kernel is loaded at 0x80000. The memory layout looks like this:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
+------------------+ 0x00000000
| Reserved         |
+------------------+ 0x00080000
| Kernel Code      | (.text)
+------------------+
| Kernel Data      | (.data, .bss)
+------------------+
| Stack            | (Grows down)
+------------------+ _end (Defined in linker script)
|                  |
| Heap             | (Grows up)
|                  |
+------------------+

We need to know where the kernel ends so we can start the heap right after it. We use the _end symbol from the linker script.

Updating the Linker Script (boot/linker.ld)

1
2
3
4
5
    . = ALIGN(16);
    . += 0x4000; /* 16KB Stack size */
    __stack_top = .;

    _end = .; /* Start of heap */

Implementing a Simple Allocator

We'll implement a Linked List Allocator. The heap is treated as a linked list of memory blocks.

Block Header

Each block has a header containing its size and status (free/used).

1
2
3
4
5
typedef struct block_header {
    uint32_t size;           // Size of data block
    uint32_t is_free;        // 1 = Free, 0 = Used
    struct block_header* next;
} block_header_t;

Initialization

We initialize the heap as one giant free block starting at _end.

1
2
3
4
5
6
7
8
9
#define HEAP_START ((void*)&_end)
#define HEAP_SIZE  (1024 * 1024 * 64) // 64 MB

void memory_init(void) {
    block_header_t* head = (block_header_t*)HEAP_START;
    head->size = HEAP_SIZE - sizeof(block_header_t);
    head->is_free = 1;
    head->next = NULL;
}

malloc Implementation

To allocate memory: 1. Iterate through the list to find a free block large enough. 2. If the block is much larger than requested, split it into two blocks (one used, one free). 3. Mark the block as used and return a pointer to the data (skipping the header).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
void* malloc(uint32_t size) {
    // 1. Align size to 16 bytes
    size = (size + 15) & ~15;

    block_header_t* current = head;

    while (current) {
        if (current->is_free && current->size >= size) {
            // 2. Split block if needed
            if (current->size > size + sizeof(block_header_t) + 16) {
                block_header_t* new_block = (block_header_t*)((uint8_t*)current + sizeof(block_header_t) + size);
                new_block->size = current->size - size - sizeof(block_header_t);
                new_block->is_free = 1;
                new_block->next = current->next;

                current->size = size;
                current->next = new_block;
            }

            // 3. Mark as used
            current->is_free = 0;
            return (void*)((uint8_t*)current + sizeof(block_header_t));
        }
        current = current->next;
    }
    return NULL; // Out of memory
}

free Implementation

To free memory: 1. Calculate the header address from the data pointer. 2. Mark the block as free. 3. (Optional but recommended) Coalesce (merge) adjacent free blocks to prevent fragmentation.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
void free(void* ptr) {
    if (!ptr) return;
    block_header_t* block = (block_header_t*)((uint8_t*)ptr - sizeof(block_header_t));
    block->is_free = 1;

    // Merge with next block
    if (block->next && block->next->is_free) {
        block->size += sizeof(block_header_t) + block->next->size;
        block->next = block->next->next;
    }
}

Building and Testing

1. Build

1
2
3
cd simpian-os/build
cmake -DBUILD_EXAMPLES=ON ..
make

2. Deploy

Copy memory_demo.img to SD card (rename to kernel8.img).

3. Expected Output

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
Memory Allocation Demo
======================

Memory initialized. Heap start: OK
1. Allocating 100 bytes for string...
   Success! Address: OK
   Content: Dynamic Hello World!

2. Allocating array of integers...
   Values: 0 1 4 9 16 25 36 49 64 81 

3. Freeing memory...
   Freed.

4. Stress test (allocating many blocks)...
..........
   Freeing blocks...
..........

Test Complete!

Challenges

This simple allocator has issues: - Fragmentation: Memory gets chopped into small unusable pieces. - Performance: malloc is O(N) (linear scan). - No Protection: A buffer overflow can corrupt the heap headers!

Real OSes use advanced allocators like slab allocators or buddy systems to solve these problems.

Complete Source Code

What's Next?

Now that we can manage memory, we can implement more complex features. The next logical step is Virtual Memory using the MMU (Memory Management Unit) to protect the kernel and isolate processes.

The next article covers Virtual Memory (MMU).