kernel/kalloc.c

Headers

The comment states the allocator’s whole contract: whole pages only. The headers provide PGSIZE and PGROUNDUP (kernel/riscv.h), PHYSTOP (kernel/memlayout.h), and struct spinlock with its functions (kernel/spinlock.h, kernel/defs.h).

Declarations

freerange is used by kinit before its definition, hence the prototype. end is not a variable in any C file: the linker script defines the symbol at the first address after the kernel’s .bss (kernel/kernel.ld). Declaring it as a char array means that writing end gives its address, which is the only thing that matters about it; there is no data there to read.

A free page holds the list link

run describes what is stored in a free page: only a pointer to the next free page. The allocator needs no memory of its own for bookkeeping, because the first 8 bytes of each free page hold the list link. Once kalloc hands a page out, the caller owns all 4096 bytes and the run interpretation no longer applies.

The allocator's state

kmem is the only global state: the head of the free list and the spinlock that protects it. Every hart can call kalloc and kfree at any moment, and each one reads the head and then writes a new head; without the lock, two harts could both read the same head and hand out the same page twice, or one hart’s push could overwrite the other’s. The struct type has no name because only this one variable of it exists.

kinit(): fill the free list at boot

main calls this once, on hart 0, before paging is on. It initializes the lock (the name "kmem" is stored in it, for someone inspecting the lock in a debugger) and frees every page between end and PHYSTOP, which is how the free list gets its initial contents. In this build end is 0x80020bb0 (see kernel/kernel.sym), so the free pages run from 0x80021000 to 0x87fff000: 32,735 pages, almost 128 MiB.

freerange(): free every whole page in a range

Rounds the start up to a page boundary, since end is usually not page-aligned and the part of a page that the kernel image occupies must not be handed out. Then it calls kfree on each page that fits entirely below pa_end: the test p + PGSIZE <= pa_end stops before a final partial page.

kfree pushes each page on the front of the list, so after the loop the list runs from the highest page down: the first kalloc returns 0x87fff000.

kfree(): give a page back

Called when a page is no longer needed (by uvmunmap, freewalk, freeproc, pipeclose, …) and at boot by freerange.

1. Check the address (line 51). The page must be page-aligned and lie between end and PHYSTOP. A misaligned pointer would make the “page” straddle two real pages, and a later kalloc would hand out memory that partly belongs to someone else; a pointer into the kernel image or past the end of RAM would let the allocator hand out the kernel’s own code or memory that does not exist. Such a call is always a kernel bug, so it panics at once rather than corrupting memory later. The check does not catch freeing the same page twice, which would put it on the list twice (and make the list loop back on itself).
2. Fill with junk (line 55). Every byte becomes 0x01. Code that wrongly keeps using the page after freeing it (“a dangling reference”) then reads garbage such as the pointer 0x0101010101010101, and is likely to crash soon, close to the bug, instead of quietly reading old data that looks valid.
3. Push it on the list (lines 57–62), under the lock.

The junk fill must come before line 60: it would otherwise overwrite the next pointer just stored in the page.

kalloc(): take a page

Pops the first page off the free list under the lock and returns it, or returns 0 when the list is empty: out of memory. Every caller must check for 0; most pass the failure up as an error (for example uvmalloc makes sbrk fail), while the boot-time callers proc_mapstacks and virtio_disk_init panic, and kvmmake does not check at all (at boot, memory cannot have run out).

The fill with 0x05 bytes happens after the lock is released: the page is already off the list, so no other hart can reach it. It overwrites the stale next pointer in the first 8 bytes and any old contents, so a caller that forgets to initialize the page sees obvious junk rather than plausible leftovers of a previous user (and the different value, 5 instead of 1, lets you tell “allocated but never initialized” from “freed” in a debugger). Callers that need zeros, such as page tables and user pages, must memset the page to 0 themselves.