kbrk and vbrk

What happens if you don’t have enough space left? You’ve done some allocations but realise you need more room. Well, all you need is a brk.

The brk functions move the “break point” — the boundary between used and free memory. Everything below the break is in use, everything above is available. kbrk and vbrk move this boundary for the heap and vmalloc region respectively.

kbrk

The kbrk version needs to do a bit of searching as we need to walk the linked list to find the end of the heap. It’s relatively easy to do but we need to be careful not to move outside of valid memory space. We have this check to make sure addr is in bounds:

let addr_u32 = addr as u32;
if addr_u32 < HEAP_START || addr_u32 > HEAP_MAX {
  return -1;
}

Notice that HEAP_MAX there? I found that when using kbrk to shrink the heap, that the original value gets lost and cannot be restored. Therefore when the heap is initialed, we save this value so we can always go back to it.

HEAP_MAX = start + size;

Then calculating and updating the size is simple:

HEAP_SIZE = addr as u32 - HEAP_START;

Now we need to walk from the start of the heap until we find the last block, then update its size to reflect the new boundary:

let mut head = HEAP_START as *mut BlockHeader;
while (*head).next != 0 as *mut BlockHeader {
    head = (*head).next;
}
if (*head).free == 1 {
    (*head).size = addr_u32 - (head as u32 + HEADER_SIZE as u32);
    return 1;
}
return -1;

We check (*head).free == 1 before updating — if the last block is occupied, we can’t safely resize it without corrupting live data. In that case we return -1 and let the caller handle the failure.

vbrk

The vbrk version is much simpler. It still needs the same bounds checks to make sure we stay within the vmalloc region, but because we already track where the next valid address is with VMALLOC_NEXT_VADDR, we just update it directly — no linked list walk needed.

if addr.is_null() {
    return 0;
}
let addr_u32 = addr as u32;
if addr_u32 < VMALLOC_START || addr_u32 > VMALLOC_END {
    return -1;
}
VMALLOC_NEXT_VADDR = addr_u32;
return 1;

This is the payoff of the cursor design — because VMALLOC_NEXT_VADDR already represents the break point of the vmalloc region, moving it is a one-liner.

Testing

Both functions are testable via the brk command in NPS:

brk -k    // test kbrk
brk -v    // test vbrk

Each test prints the current break point, moves it by one page (4096 bytes), verifies the change, then restores it:

Current size: 3522560
kbrk(curr - 4096)
New size: 3518464
Restored: 3522560

The restore is the important part — it proves that HEAP_MAX correctly preserves the original upper bound even after shrinking. Without it, kbrk would reject the restore address as out of range since HEAP_START + HEAP_SIZE would already be pointing to the shrunk value.