Initialising the Heap

Before we write a single allocation function, we need to establish the heap. This means:

• Decide where it lives in memory
• How big is it
• Create an initial block

Where does the heap start

The kernel heap starts just after the kernel binary and initial page tables, within the identity-mapped 4MB region:

0x00400000  ← End of identity-mapped region
            ← Heap upper bound (can grow up to here)
   (heap)   ← kmalloc manages this region
~0x00200000 ← Heap start (approximate, after page tables)

The heap is a fixed region reserved at initialisation time. We’re not doing dynamic expansion (kbrk) in the first pass — just a fixed-size heap.

How big should it be

For now we are going to make this fixed sized. This being said we need to pick a size that fits comfortably in the identity-mapped 4MB but leaves room for the frame allocator above it.

What does the initial state look like?

When init_heap returns, the entire heap region should be represented as a single large free block with a header at the start. That header is the foundation of the free list. Every subsequent allocation and free is just reshaping that initial block

Initial Memory State

HEAP_START →  [Header: size=HEAP_SIZE, used=false, next=null]
              [                                             ]
              [               (all free space)              ]
              [                                             ]
HEAP_START + HEAP_SIZE

BlockHeader

The BlockHeader sits at the start of every single block in the heap. Both free and used ones. It gets stamped into memory millions of times potentially.

But every block does not need to know about the page tables, this is something the heap as a whole knows once at initialisation. Things like page tables, heap start addresses and the free list belong to the heaps global state.

A single block needs to answer three questions:

• Is the block currently free or in use?
• How big is the block?
• Where is the next block? (So we can walk the list)

The BlockHeader should give just enough metadata to navigate and manage one block. We can structure it like this

#[repr(C)]
pub struct BlockHeader {
    free: bool,
    size: u32,
    next: *mut BlockHeader,
}

The size field needs to be precise. The size can differ depending on what the compiler decides. A bool is one byte, but the compiler will likely pad it to align with the u32 that follows. So we need to add #[repr(C)]. Without it we might get:

[bool: 1 byte][padding: 3 bytes][size: 4 bytes][next: 4 bytes] = 12 bytes

This means to find the header of the block of memory, you only need to use ptr - 12 meaning using size_of::<BlockHeader>() will be consistent. So we can now add this const,

pub const HEADER_SIZE: usize = core::mem::size_of::<BlockHeader>();

With the next field, we can walk the blocks to find adjacent free blocks for coalescing later and lets kfree find its neighbours.

Start of the Heap

There one another const we are going to need to provide, and that’s HEAP_START. We can already get the next free frame by checking NEXT_FREE_FRAME as it sits right after the page directory and the first page table. That means, everything from there on is untouched.

But there is a small problem. That is, NEXT_FREE_FRAME is private to paging.rs so we need to pass the heap as a parameter to init_heap and make a getter for NEXT_FREE_FRAME

// paging.rs
pub unsafe fn get_heap_start() -> u32 {
    NEXT_FREE_FRAME
}

// lib.rs
unsafe {
   init_paging(16 * 1024 * 1024);
   init_heap(get_heap_start(), HEAP_SIZE)
}

But for this, we also need to have define HEAP_SIZE. We know that given the identity-mapped region ends at 4MB(x00400000) and NEXT_FREE_FRAME will be somewhere around 0x00200000 after paging, that we have roughly 2MB of useable space. So we can define HEAP_SIZE as so:

pub const HEAP_SIZE: u32 = 1024 * 1024; // 1MB

Free-list Allocator

When the heap is initialised, there will be one BlockHeader containing all of the stack, set to free and the next being null. Then when we allocate 256b and this happens:

At init_heap:
HEAP_START → [Header: free=true, size=HEAP_SIZE, next=null ]
             [                                             ]
             [          one big free block                 ]
             [                                             ]
HEAP_START + HEAP_SIZE

After allocation:
HEAP_START → [Header: free=false, size=256, next=→                        ]
             [256 bytes of user data                                      ]
             [Header: free=true, size=HEAP_SIZE-256-HEADER_SIZE, next=null]
             [          remaining free space                              ]
             [                                                            ]
HEAP_START + HEAP_SIZE

The original block is split into two, one allocated block the right size, and one free block with whatever is left. The next pointer of the first header points to the second header.

Every subsequent kmalloc call either:

• Splits the big free block again
• Finds a previously freed block that’s big enough to reuse.

Every kfree marks a block as free again, making it available for reuse.

init_heap

Now lets start filling out the body. We have the start of the heap and its size. We need to save these initial values and create a BlockHeader to send back containing the initial heap.

let header = HEAP_START as *mut BlockHeader;
(*header).free = true;
(*header).size = HEAP_SIZE - HEADER_SIZE as u32; // space minus the header itself
(*header).next = 0 as *mut BlockHeader; // there is no next

It’s important to note that after allocation, the available heap is smaller than what we specified because the header itself takes up space. kmalloc will use the size to decide of the block is big enough and it needs to be accurate.