§ 1.2 Kernel Boot Process

1. Overview

After the bootloader decompresses the kernel and jumps to startup_64 (x86) or _text (ARM64), a few dozen assembly instructions enable paging and branch to start_kernel() — the first C function ever called. From here the kernel must bootstrap everything from scratch: memory allocators, interrupt handling, scheduling, filesystems, and the network stack, all in a carefully ordered sequence where each subsystem may only use services already initialized before it.

The entire sequence runs on a single CPU with interrupts disabled until local_irq_enable() is explicitly called. When rest_init() is reached, the kernel spawns PID 1 (kernel_init) and PID 2 (kthreadd), then becomes the idle thread (PID 0).

2. Key Data Structures

struct boot_params — x86 Boot Protocol

On x86, the bootloader fills a 4 KB boot_params structure at physical address 0x90000 and passes its address in register rsi. setup_arch() reads it in the very first lines of kernel C code. The most important sub-structure is the e820_table — the physical memory map.

struct e820_entry — Physical Memory Map

Each entry describes one contiguous physical region. The BIOS/UEFI firmware fills these via INT 0x15, AX=0xe820. The kernel uses this map to know which RAM is free, which is reserved (MMIO, ACPI tables), and which is unusable. It is the foundation for memblock.

memblock — The Boot-Time Allocator

Before the buddy allocator exists there must be a simpler allocator to manage memory. memblock is that allocator: it keeps two sorted arrays of physical ranges — memory[] (available) and reserved[] (in use). Allocation is a simple range split; there is no free — everything is freed at once when mem_init() hands the remaining ranges to the buddy allocator.

3. Core Mechanism — From memblock to Buddy

Background: The kernel needs to allocate memory for its own data structures before the buddy allocator exists (page tables, IRQ descriptors, CPU stacks…). But it also needs to give the buddy allocator the correct list of free physical pages once it is ready. memblock is the bridge: it answers early allocation requests, then transfers ownership to the buddy allocator in a single pass during mem_init().

Plan:

1. setup_arch() calls e820__memblock_setup(): every E820_RAM range becomes a memblock.memory entry; the kernel image, initrd, and ACPI tables are immediately reserved.
2. Subsystems allocate from memblock via memblock_alloc(size, align). The allocator finds the last free range that fits and splits it, adding the allocated portion to memblock.reserved.
3. mm_init() calls free_area_init() to set up zone descriptors (DMA, Normal, HighMem on 32-bit) without touching actual pages yet.
4. mem_init() iterates every memblock.memory range, skips reserved sub-ranges, and calls __free_pages_memory() on the gaps — this puts pages into the buddy free lists.
5. After mem_init() returns, the buddy allocator is live. memblock data can still be read (for NUMA queries) but is no longer used for allocation.

Example — 512 MB RAM, kernel at 0x1000000:

After mem_init(), the buddy allocator owns approximately 480 MB of free pages split across order-0 through order-10 free lists. The kernel image and initrd are permanently reserved and never returned to the allocator.

4. Minimal C Demos

Demo A — memblock Range Allocator

memblock keeps a sorted array of free ranges and a sorted array of reserved ranges. Allocation is a top-down scan: find the last free range that fits, mark the tail as reserved, return its address.

Demo B — e820 Memory Map Parser

setup_arch() walks the e820 table from boot_params.e820_table and calls memblock_add() for every E820_RAM entry. The demo below simulates this scan, computing total usable RAM and the largest contiguous free region — the same logic as e820__memblock_setup().

5. Kernel Source Pointers

6. Interview Prep