Kernel Decompression and Physical Relocation

A kernel binary on disk is not a single flat blob. It is a small uncompressed stub followed by a compressed payload, and the stub’s job is to decompress the payload into memory at the location the kernel was linked for. The reason for the split is size: a kernel image with debug information and a large configuration can be tens of megabytes, while the compressed form that ships is a fraction of that, and the firmware or loader that reads it may be working through a slow interface.

The stub has a harder problem than decompression. It has been loaded at an arbitrary physical address by the loader, it must decompress to a specific address, and those two addresses may overlap. It also runs with whatever page tables the loader built, which map the kernel’s link-time virtual address but may not map the physical range where the decompressed output will land.

Where the stub runs and where it wants to be

On x86-64 the kernel is linked to run in the top of the canonical address space, typically in the 0xFFFFFFFF80000000 region. The loader cannot place it there: physical memory does not extend to those addresses, and the firmware’s memory map describes RAM well below them. So the loader places the image wherever it can, the stub runs at that physical address through an identity mapping, and the kernel’s own code is linked to a virtual address that the stub must arrange for.

The stub itself is position-independent, compiled with the assumption that it may be loaded anywhere. That rules out absolute references to its own data and requires the stub to compute addresses relative to its own program counter. In practice the stub is written in assembly with a small amount of C compiled with -fPIC and no global offset table, or it is compiled as a single position-independent unit where every access to a static variable is resolved through a register holding the load base.

The stub’s first task is to determine where it is. On x86-64 a call to the next instruction followed by a pop of the return address gives the current instruction pointer; subtracting the link-time address of that label gives the load offset. Every subsequent address calculation adds that offset.

Choosing the decompression target

The decompressed kernel needs a contiguous physical region large enough for its text, data, and initial heap. The stub knows the size from a field in its own header and knows the available memory from the boot protocol’s memory map, which the loader passed in a register or in a structure.

The naive approach is to decompress to the start of the largest usable region above 1 MiB. That fails when the compressed image itself sits in that region, because the output would overwrite the input while it is still being read. The standard resolution is to find a region that does not overlap the input, or to move the compressed payload out of the way first: copy it to the end of the chosen region, then decompress from there downward, or decompress from a temporary buffer allocated above the target.

A second constraint is alignment. The kernel’s link-time layout assumes its text begins on a page boundary and that the physical and virtual offsets are congruent modulo the page size, because the identity mapping that the stub installs maps the physical region to the kernel’s virtual address with a fixed offset. If the physical placement is not page-aligned, the offset between physical and virtual addresses is not representable by page-table entries, and the stub cannot build the mapping.

The mapping the kernel expects

After decompression, the stub builds page tables that map the kernel’s virtual address range to the physical region it just filled. On x86-64 with 4-level paging this means allocating a PML4, a PDPT, and a page directory for the relevant range, and mapping the kernel’s text, read-only data, writable data, and the initial heap with appropriate permissions. Read-execute for text, read-only for data that must not change, read-write for the rest.

The mapping is not identity. If the kernel is linked at virtual 0xFFFFFFFF80000000 and decompressed at physical 0x1000000, the mapping must translate the first to the second. The stub computes the difference and applies it to each page-table entry’s physical address field. Because the offset is constant across the whole image, one set of tables covers the entire kernel.

The stub also needs the code it is currently executing to remain mapped. If the stub’s own physical location falls outside the range it is about to remap, the next instruction fetch after loading CR3 faults. The usual arrangement maps the stub’s own region identically as well, or keeps the loader’s tables and adds entries to them rather than replacing them.

Jumping to the decompressed kernel

The final sequence disables interrupts, loads the new CR3, and jumps to the kernel’s entry point at its virtual address. Between the CR3 load and the jump, the stub is executing at a physical address that the new tables must still map; if the jump target is at a different virtual address, the stub’s own code must be mapped for the duration.

There is a second subtlety: the kernel’s entry code expects certain registers to hold the boot parameters pointer and, on some architectures, a pointer to the device tree or an equivalent. The stub passes those through, converting physical addresses to the kernel’s virtual mapping where necessary, because the boot parameters structure was placed by the loader at a physical address and the kernel will read it after the mapping switch.

/* the essential shape of the handoff, after the new tables are built */
void __attribute__((noreturn)) jump_to_kernel(uint64_t cr3_phys, uint64_t entry,
                                              void *params)
{
    __asm__ volatile (
        "mov %0, %%cr3\n\t"
        "mov %1, %%rsi\n\t"     /* boot parameters in the second argument register */
        "jmp *%2\n\t"
        :
        : "r" (cr3_phys), "r" (params), "r" (entry)
        : "memory");
    __builtin_unreachable();
}

The register choice is part of the architecture’s boot protocol, not a free decision; a stub that puts the parameters in the wrong register produces a kernel that starts and then faults while reading a pointer that was never set.

What breaks

The most common failure is a decompression target that overlaps the compressed payload. The stub’s overlap check must account for the compressed data, the decompression window if the algorithm requires one, and the output. A DEFLATE stream, as specified in RFC 1951, encodes matches against a history window of up to 32 KiB. A decompressor that uses the output buffer as that window must therefore have at least 32 KiB of output already produced before it can decode a match that reaches back the full distance, which means the buffer must be sized for the window even when the compressed input is much smaller.

A second failure is the page-table permission mismatch. Mapping the kernel’s text as writable is not a correctness problem at this stage, but mapping the boot parameters structure as read-only, or failing to map it at all, causes a fault on the first field the kernel reads. The stub typically maps the low physical region identically and leaves it writable for exactly this reason.

A third is the stack. The stub’s stack is wherever the loader put it, and the decompressed kernel will use its own stack from the moment it takes over. The stub must not switch stacks before the jump, because the kernel’s entry code sets up its own, and a stub that switches to a stack inside the region it is about to overwrite loses its return path.

On architectures without a decompressing stub, the same work happens in the loader: an ARM64 image is often decompressed by the boot loader and placed at the physical address the kernel expects, with the device tree passed in a register. The relocation is then the loader’s responsibility, and the kernel’s entry code assumes it has already been done.

Once the kernel is running at its link-time address, the next problem is that it has no output device. The path from that state to a working console is described in early console output before drivers exist, and the memory map the stub used to choose its target is the one discussed in how firmware describes physical memory.