Kernel Heap Allocators

The frame allocator hands out whole 4 KiB frames. The kernel mostly needs small things: a 120-byte process descriptor, a 40-byte file object, a 300-byte buffer. Giving each of those a frame would waste almost all of it, so on top of frames sits a heap: a kmalloc and kfree that carve small objects out of a region. In this lesson your program is that allocator, with real headers, splitting and coalescing, and you will watch fragmentation happen.

Two layers, two granularities

• Frames (physical, 4096 bytes): the unit of page tables and of the previous lesson.
• Objects (virtual, any size): what kmalloc returns. The heap asks the layer below for a region and slices it.

The simplest allocator, and why it is not enough

A bump allocator keeps one pointer and moves it forward for every request. It is fast and tiny and is used in early boot and for allocations that live forever, but it cannot free a single object, only reset the whole region. The moment objects die independently you need a record of which pieces are free.

A free-list allocator

Every piece of the heap, used or free, is a block with a 16-byte header in front of its payload. The block records its size (header included) and whether it is in use. Blocks tile the region exactly, so the heap is a sequence you can walk by address:

heap start                                                      heap end
| hdr | payload (used) | hdr | payload (free) ........... | hdr | payload (used) |

Three rules make it work:

1. Size and alignment. A request of n bytes becomes a payload of n rounded up to a multiple of 16, so every returned pointer is 16-byte aligned if the heap start is. A block therefore occupies 16 + rounded bytes. (Alignment matters: misaligned data breaks SSE instructions and slows everything else.)
2. First fit with splitting. Walk the blocks in address order and take the first free one that is big enough. If what is left over could hold a header plus a minimum 16-byte payload (32 bytes), cut it off as a new free block; otherwise hand over the whole block, because a leftover scrap with no room for a header is unusable.
3. Coalescing on free. When a block is freed, merge it with a free neighbour after it, and with a free neighbour before it. Without this the heap shatters into pieces no larger than the biggest block ever allocated.

A worked trace

Heap at 0x1000, size 0x100 (256 bytes). One free block: 0x1000, 256.

The returned pointer is the payload address, header address + 16. kfree is given that pointer, steps back 16 bytes to find the header and validates it. A pointer that is not exactly the payload of a block in use is a bug: a double free, a wild pointer, or an interior pointer.

Fragmentation

Free the second and fourth of five equal blocks and the heap has plenty of free bytes but no run big enough for a request twice the block size. That is external fragmentation, and it is why real kernels use slab allocators (one cache per object type, so every slot fits every request) over the general heap, and why kmalloc for big contiguous areas goes to the frame allocator.

Common mistakes

• Returning the block address instead of the payload address, or forgetting that the block is 16 bytes larger than the request.
• Splitting when the leftover is smaller than a header plus the minimum payload, creating a block you can never use.
• Coalescing in only one direction.
• Accepting any pointer in free without checking that it is the payload of a block currently in use.

Your exercise

The starter holds the block list and prints it. You write alloc and free as specified in the exercise.