Kernel booting process. Part 5.

Kernel decompression

This is the fifth part of the Kernel booting process series. We saw transition to the 64-bit mode in the previous part and we will continue from this point in this part. We will see the last steps before we jump to the kernel code as preparation for kernel decompression, relocation and directly kernel decompression. So… let’s start to dive in the kernel code again.

Preparation before kernel decompression

We stopped right before the jump on the 64-bit entry point - startup_64 which is located in the arch/x86/boot/compressed/head_64.S source code file. We already saw the jump to the startup_64 in the startup_32:

  1.     pushl    $__KERNEL_CS
  2.     leal    startup_64(%ebp), %eax
  3.     ...
  4.     ...
  5.     ...
  6.     pushl    %eax
  7.     ...
  8.     ...
  9.     ...
  10.     lret

in the previous part. Since we loaded the new Global Descriptor Table and there was CPU transition in other mode (64-bit mode in our case), we can see the setup of the data segments:

  1.     .code64
  2.     .org 0x200
  3. ENTRY(startup_64)
  4.     xorl    %eax, %eax
  5.     movl    %eax, %ds
  6.     movl    %eax, %es
  7.     movl    %eax, %ss
  8.     movl    %eax, %fs
  9.     movl    %eax, %gs

in the beginning of the startup_64. All segment registers besides cs register now reseted as we joined into the long mode.

The next step is computation of difference between where the kernel was compiled and where it was loaded:

  1. #ifdef CONFIG_RELOCATABLE
  2.     leaq    startup_32(%rip), %rbp
  3.     movl    BP_kernel_alignment(%rsi), %eax
  4.     decl    %eax
  5.     addq    %rax, %rbp
  6.     notq    %rax
  7.     andq    %rax, %rbp
  8.     cmpq    $LOAD_PHYSICAL_ADDR, %rbp
  9.     jge    1f
  10. #endif
  11.     movq    $LOAD_PHYSICAL_ADDR, %rbp
  12. 1:
  13.     movl    BP_init_size(%rsi), %ebx
  14.     subl    $_end, %ebx
  15.     addq    %rbp, %rbx

The rbp contains the decompressed kernel start address and after this code executes rbx register will contain address to relocate the kernel code for decompression. We already saw code like this in the startup_32 ( you can read about it in the previous part - Calculate relocation address), but we need to do this calculation again because the bootloader can use 64-bit boot protocol and startup_32 just will not be executed in this case.

In the next step we can see setup of the stack pointer and resetting of the flags register:

  1.     leaq    boot_stack_end(%rbx), %rsp
  3.     pushq    $0
  4.     popfq

As you can see above, the rbx register contains the start address of the kernel decompressor code and we just put this address with boot_stack_end offset to the rsp register which represents pointer to the top of the stack. After this step, the stack will be correct. You can find definition of the boot_stack_end in the end of arch/x86/boot/compressed/head_64.S assembly source code file:

  1.     .bss
  2.     .balign 4
  3. boot_heap:
  4.     .fill BOOT_HEAP_SIZE, 1, 0
  5. boot_stack:
  6.     .fill BOOT_STACK_SIZE, 1, 0
  7. boot_stack_end:

It located in the end of the .bss section, right before the .pgtable. If you will look into arch/x86/boot/compressed/vmlinux.lds.S linker script, you will find Definition of the .bss and .pgtable there.

As we set the stack, now we can copy the compressed kernel to the address that we got above, when we calculated the relocation address of the decompressed kernel. Before details, let’s look at this assembly code:

  1.     pushq    %rsi
  2.     leaq    (_bss-8)(%rip), %rsi
  3.     leaq    (_bss-8)(%rbx), %rdi
  4.     movq    $_bss, %rcx
  5.     shrq    $3, %rcx
  6.     std
  7.     rep    movsq
  8.     cld
  9.     popq    %rsi

First of all we push rsi to the stack. We need preserve the value of rsi, because this register now stores a pointer to the boot_params which is real mode structure that contains booting related data (you must remember this structure, we filled it in the start of kernel setup). In the end of this code we’ll restore the pointer to the boot_params into rsi again.

The next two leaq instructions calculates effective addresses of the rip and rbx with _bss - 8 offset and put it to the rsi and rdi. Why do we calculate these addresses? Actually the compressed kernel image is located between this copying code (from startup_32 to the current code) and the decompression code. You can verify this by looking at the linker script - arch/x86/boot/compressed/vmlinux.lds.S:

  1.     . = 0;
  2.     .head.text : {
  3.         _head = . ;
  4.         HEAD_TEXT
  5.         _ehead = . ;
  6.     }
  7.     .rodata..compressed : {
  8.         *(.rodata..compressed)
  9.     }
  10.     .text :    {
  11.         _text = .;     /* Text */
  12.         *(.text)
  13.         *(.text.*)
  14.         _etext = . ;
  15.     }

Note that .head.text section contains startup_32. You may remember it from the previous part:

  1.     __HEAD
  2.     .code32
  3. ENTRY(startup_32)
  4. ...
  5. ...
  6. ...

The .text section contains decompression code:

  1.     .text
  2. relocated:
  3. ...
  4. ...
  5. ...
  6. /*
  7.  * Do the decompression, and jump to the new kernel..
  8.  */
  9. ...

And .rodata..compressed contains the compressed kernel image. So rsi will contain the absolute address of _bss - 8, and rdi will contain the relocation relative address of _bss - 8. As we store these addresses in registers, we put the address of _bss in the rcx register. As you can see in the vmlinux.lds.S linker script, it’s located at the end of all sections with the setup/kernel code. Now we can start to copy data from rsi to rdi, 8 bytes at the time, with the movsq instruction.

Note that there is an std instruction before data copying: it sets the DF flag, which means that rsi and rdi will be decremented. In other words, we will copy the bytes backwards. At the end, we clear the DF flag with the cld instruction, and restore boot_params structure to rsi.

Now we have the address of the .text section address after relocation, and we can jump to it:

  1.     leaq    relocated(%rbx), %rax
  2.     jmp    *%rax

Last preparation before kernel decompression

In the previous paragraph we saw that the .text section starts with the relocated label. The first thing it does is clearing the bss section with:

  1.     xorl    %eax, %eax
  2.     leaq    _bss(%rip), %rdi
  3.     leaq    _ebss(%rip), %rcx
  4.     subq    %rdi, %rcx
  5.     shrq    $3, %rcx
  6.     rep    stosq

We need to initialize the .bss section, because we’ll soon jump to C code. Here we just clear eax, put the address of _bss in rdi and _ebss in rcx, and fill it with zeros with the rep stosq instruction.

At the end, we can see the call to the extract_kernel function:

  1.     pushq    %rsi
  2.     movq    %rsi, %rdi
  3.     leaq    boot_heap(%rip), %rsi
  4.     leaq    input_data(%rip), %rdx
  5.     movl    $z_input_len, %ecx
  6.     movq    %rbp, %r8
  7.     movq    $z_output_len, %r9
  8.     call    extract_kernel
  9.     popq    %rsi

Again we set rdi to a pointer to the boot_params structure and preserve it on the stack. In the same time we set rsi to point to the area which should be used for kernel uncompression. The last step is preparation of the extract_kernel parameters and call of this function which will uncompres the kernel. The extract_kernel function is defined in the arch/x86/boot/compressed/misc.c source code file and takes six arguments:

  • rmode - pointer to the boot_params structure which is filled by bootloader or during early kernel initialization;
  • heap - pointer to the boot_heap which represents start address of the early boot heap;
  • input_data - pointer to the start of the compressed kernel or in other words pointer to the arch/x86/boot/compressed/vmlinux.bin.bz2;
  • input_len - size of the compressed kernel;
  • output - start address of the future decompressed kernel;
  • output_len - size of decompressed kernel;

All arguments will be passed through the registers according to System V Application Binary Interface. We’ve finished all preparation and can now look at the kernel decompression.

Kernel decompression

As we saw in previous paragraph, the extract_kernel function is defined in the arch/x86/boot/compressed/misc.c source code file and takes six arguments. This function starts with the video/console initialization that we already saw in the previous parts. We need to do this again because we don’t know if we started in real mode or a bootloader was used, or whether the bootloader used the 32 or 64-bit boot protocol.

After the first initialization steps, we store pointers to the start of the free memory and to the end of it:

  1. free_mem_ptr     = heap;
  2. free_mem_end_ptr = heap + BOOT_HEAP_SIZE;

where the heap is the second parameter of the extract_kernel function which we got in the arch/x86/boot/compressed/head_64.S:

  1. leaq    boot_heap(%rip), %rsi

As you saw above, the boot_heap is defined as:

  1. boot_heap:
  2.     .fill BOOT_HEAP_SIZE, 1, 0

where the BOOT_HEAP_SIZE is macro which expands to 0x10000 (0x400000 in a case of bzip2 kernel) and represents the size of the heap.

After heap pointers initialization, the next step is the call of the choose_random_location function from arch/x86/boot/compressed/kaslr.c source code file. As we can guess from the function name, it chooses the memory location where the kernel image will be decompressed. It may look weird that we need to find or even choose location where to decompress the compressed kernel image, but the Linux kernel supports kASLR which allows decompression of the kernel into a random address, for security reasons.

We will not consider randomization of the Linux kernel load address in this part, but will do it in the next part.

Now let’s back to misc.c. After getting the address for the kernel image, there need to be some checks to be sure that the retrieved random address is correctly aligned and address is not wrong:

  1. if ((unsigned long)output & (MIN_KERNEL_ALIGN - 1))
  2.     error("Destination physical address inappropriately aligned");
  4. if (virt_addr & (MIN_KERNEL_ALIGN - 1))
  5.     error("Destination virtual address inappropriately aligned");
  7. if (heap > 0x3fffffffffffUL)
  8.     error("Destination address too large");
  10. if (virt_addr + max(output_len, kernel_total_size) > KERNEL_IMAGE_SIZE)
  11.     error("Destination virtual address is beyond the kernel mapping area");
  13. if ((unsigned long)output != LOAD_PHYSICAL_ADDR)
  14.     error("Destination address does not match LOAD_PHYSICAL_ADDR");
  16. if (virt_addr != LOAD_PHYSICAL_ADDR)
  17.     error("Destination virtual address changed when not relocatable");

After all these checks we will see the familiar message:

  1. Decompressing Linux...

and call the __decompress function:

  1. __decompress(input_data, input_len, NULL, NULL, output, output_len, NULL, error);

which will decompress the kernel. The implementation of the __decompress function depends on what decompression algorithm was chosen during kernel compilation:

  1. #ifdef CONFIG_KERNEL_GZIP
  2. #include "../../../../lib/decompress_inflate.c"
  3. #endif
  5. #ifdef CONFIG_KERNEL_BZIP2
  6. #include "../../../../lib/decompress_bunzip2.c"
  7. #endif
  9. #ifdef CONFIG_KERNEL_LZMA
  10. #include "../../../../lib/decompress_unlzma.c"
  11. #endif
  13. #ifdef CONFIG_KERNEL_XZ
  14. #include "../../../../lib/decompress_unxz.c"
  15. #endif
  17. #ifdef CONFIG_KERNEL_LZO
  18. #include "../../../../lib/decompress_unlzo.c"
  19. #endif
  21. #ifdef CONFIG_KERNEL_LZ4
  22. #include "../../../../lib/decompress_unlz4.c"
  23. #endif

After kernel is decompressed, the last two functions are parse_elf and handle_relocations. The main point of these functions is to move the uncompressed kernel image to the correct memory place. The fact is that the decompression will decompress in-place, and we still need to move kernel to the correct address. As we already know, the kernel image is an ELF executable, so the main goal of the parse_elf function is to move loadable segments to the correct address. We can see loadable segments in the output of the readelf program:

  1. readelf -l vmlinux
  3. Elf file type is EXEC (Executable file)
  4. Entry point 0x1000000
  5. There are 5 program headers, starting at offset 64
  7. Program Headers:
  8.   Type           Offset             VirtAddr           PhysAddr
  9.                  FileSiz            MemSiz              Flags  Align
  10.   LOAD           0x0000000000200000 0xffffffff81000000 0x0000000001000000
  11.                  0x0000000000893000 0x0000000000893000  R E    200000
  12.   LOAD           0x0000000000a93000 0xffffffff81893000 0x0000000001893000
  13.                  0x000000000016d000 0x000000000016d000  RW     200000
  14.   LOAD           0x0000000000c00000 0x0000000000000000 0x0000000001a00000
  15.                  0x00000000000152d8 0x00000000000152d8  RW     200000
  16.   LOAD           0x0000000000c16000 0xffffffff81a16000 0x0000000001a16000
  17.                  0x0000000000138000 0x000000000029b000  RWE    200000

The goal of the parse_elf function is to load these segments to the output address we got from the choose_random_location function. This function starts with checking the ELF signature:

  1. Elf64_Ehdr ehdr;
  2. Elf64_Phdr *phdrs, *phdr;
  4. memcpy(&ehdr, output, sizeof(ehdr));
  6. if (ehdr.e_ident[EI_MAG0] != ELFMAG0 ||
  7.     ehdr.e_ident[EI_MAG1] != ELFMAG1 ||
  8.     ehdr.e_ident[EI_MAG2] != ELFMAG2 ||
  9.     ehdr.e_ident[EI_MAG3] != ELFMAG3) {
  10.         error("Kernel is not a valid ELF file");
  11.         return;
  12. }

and if it’s not valid, it prints an error message and halts. If we got a valid ELF file, we go through all program headers from the given ELF file and copy all loadable segments with correct address to the output buffer:

  1.     for (i = 0; i < ehdr.e_phnum; i++) {
  2.         phdr = &phdrs[i];
  4.         switch (phdr->p_type) {
  5.         case PT_LOAD:
  6. #ifdef CONFIG_RELOCATABLE
  7.             dest = output;
  8.             dest += (phdr->p_paddr - LOAD_PHYSICAL_ADDR);
  9. #else
  10.             dest = (void *)(phdr->p_paddr);
  11. #endif
  12.             memmove(dest, output + phdr->p_offset, phdr->p_filesz);
  13.             break;
  14.         default:
  15.             break;
  16.         }
  17.     }

That’s all.

From this moment, all loadable segments are in the correct place.

The next step after the parse_elf function is the call of the handle_relocations function. Implementation of this function depends on the CONFIG_X86_NEED_RELOCS kernel configuration option and if it is enabled, this function adjusts addresses in the kernel image, and is called only if the CONFIG_RANDOMIZE_BASE configuration option was enabled during kernel configuration. Implementation of the handle_relocations function is easy enough. This function subtracts value of the LOAD_PHYSICAL_ADDR from the value of the base load address of the kernel and thus we obtain the difference between where the kernel was linked to load and where it was actually loaded. After this we can perform kernel relocation as we know actual address where the kernel was loaded, its address where it was linked to run and relocation table which is in the end of the kernel image.

After the kernel is relocated, we return back from the extract_kernel to arch/x86/boot/compressed/head_64.S.

The address of the kernel will be in the rax register and we jump to it:

  1. jmp    *%rax

That’s all. Now we are in the kernel!

Conclusion

This is the end of the fifth part about linux kernel booting process. We will not see posts about kernel booting anymore (maybe updates to this and previous posts), but there will be many posts about other kernel internals.

Next chapter will describe more advanced details about linux kernel booting process, like a load address randomization and etc.

If you have any questions or suggestions write me a comment or ping me in twitter.

Please note that English is not my first language, And I am really sorry for any inconvenience. If you find any mistakes please send me PR to linux-insides.