ELF Loader (Part 1)
So far we used a flat binary format for our user task. But it's becoming more difficult as we have to manually specify the layout of the binary using a linker script, and arrange the sections in a fixed way so that the kernel can load them, apply relocations, and jump to the entry point. We also haven't told the kernel what sections should be marked as read-only, read-write, and/or executable. This is where the ELF format comes in.
ELF is a self-describing format that contains all the information needed to load and run a program. Although implementing an ELF loader is more complex than a flat binary loader, it's more flexible and and will save us a lot of time in the long run. Let's go ahead and implement an ELF loader.
ELF Format
ELF files contain executable code and data, as well as metadata about the file so that the loader can load the file into memory and run it. The parts of the ELF format that are relevant to us are:
- ELF Header
- Contains metadata about the file, such as the target architecture, the entry point, and the offsets of the other sections.
- Program Header Table
- Contains a list of segments to be loaded into memory. Each segment can contain one or more sections.
- Section Header Table
- Contains a list of sections, which are used for debugging and linking.
- Sections
- Contains the actual code and data of the program.
- Symbol Table
- Contains information about the symbols in the program.
- String Table
- Contains strings used by the symbol table.
- Relocation Table
- Contains information about the relocations to be applied to the program.
Building an ELF binary
Let's modify our user program to build an ELF binary instead of a flat binary. We previously used a linker script to have control over the binary layout, such that the kernel could load the binary in a straightforward way. To produce an ELF binary, we'll simply remove the linker script and let the compiler and linker generate a default ELF binary.
$ rm src/user/linker.ld
$ just user
$ file build/user/utask.bin
build/user/utask.bin: ELF 64-bit LSB pie executable, x86-64, version 1 (SYSV), static-pie linked, not stripped
Looks good. Let's inspect the ELF binary using readelf.
$ readelf -eW build/user/utask.bin
ELF Header:
Magic: 7f 45 4c 46 02 01 01 00 00 00 00 00 00 00 00 00
Class: ELF64
Data: 2's complement, little endian
Version: 1 (current)
OS/ABI: UNIX - System V
ABI Version: 0
Type: DYN (Position-Independent Executable file)
Machine: Advanced Micro Devices X86-64
Version: 0x1
Entry point address: 0xf5f0
Start of program headers: 64 (bytes into file)
Start of section headers: 78256 (bytes into file)
Flags: 0x0
Size of this header: 64 (bytes)
Size of program headers: 56 (bytes)
Number of program headers: 8
Size of section headers: 64 (bytes)
Number of section headers: 18
Section header string table index: 16
Section Headers:
[Nr] Name Type Address Off Size ES Flg Lk Inf Al
[ 0] NULL 0000000000000000 000000 000000 00 0 0 0
[ 1] .dynsym DYNSYM 0000000000000200 000200 000018 18 A 4 1 8
[ 2] .gnu.hash GNU_HASH 0000000000000218 000218 00001c 00 A 1 0 8
[ 3] .hash HASH 0000000000000234 000234 000010 04 A 1 0 4
[ 4] .dynstr STRTAB 0000000000000244 000244 000001 00 A 0 0 1
[ 5] .rela.dyn RELA 0000000000000248 000248 000498 18 A 1 0 8
[ 6] .rodata PROGBITS 00000000000006e0 0006e0 000ea8 00 AMS 0 0 16
[ 7] .text PROGBITS 0000000000002590 001590 00d712 00 AX 0 0 16
[ 8] .data.rel.ro PROGBITS 0000000000010cb0 00ecb0 000270 00 WA 0 0 16
[ 9] .dynamic DYNAMIC 0000000000010f20 00ef20 0000d0 10 WA 4 0 8
[10] .got PROGBITS 0000000000010ff0 00eff0 000000 00 WA 0 0 8
[11] .relro_padding NOBITS 0000000000010ff0 00eff0 000010 00 WA 0 0 1
[12] .data PROGBITS 0000000000011ff0 00eff0 000118 00 WA 0 0 8
[13] .bss NOBITS 0000000000012110 00f108 200490 00 WA 0 0 16
[14] .comment PROGBITS 0000000000000000 00f108 00003e 01 MS 0 0 1
[15] .symtab SYMTAB 0000000000000000 00f148 001f38 18 17 332 8
[16] .shstrtab STRTAB 0000000000000000 011080 000091 00 0 0 1
[17] .strtab STRTAB 0000000000000000 011111 002099 00 0 0 1
Key to Flags:
W (write), A (alloc), X (execute), M (merge), S (strings), I (info),
L (link order), O (extra OS processing required), G (group), T (TLS),
C (compressed), x (unknown), o (OS specific), E (exclude),
D (mbind), l (large), p (processor specific)
Program Headers:
Type Offset VirtAddr PhysAddr FileSiz MemSiz Flg Align
PHDR 0x000040 0x0000000000000040 0x0000000000000040 0x0001c0 0x0001c0 R 0x8
LOAD 0x000000 0x0000000000000000 0x0000000000000000 0x001588 0x001588 R 0x1000
LOAD 0x001590 0x0000000000002590 0x0000000000002590 0x00d712 0x00d712 R E 0x1000
LOAD 0x00ecb0 0x0000000000010cb0 0x0000000000010cb0 0x000340 0x000350 RW 0x1000
LOAD 0x00eff0 0x0000000000011ff0 0x0000000000011ff0 0x000118 0x2005b0 RW 0x1000
DYNAMIC 0x00ef20 0x0000000000010f20 0x0000000000010f20 0x0000d0 0x0000d0 RW 0x8
GNU_RELRO 0x00ecb0 0x0000000000010cb0 0x0000000000010cb0 0x000340 0x000350 R 0x1
GNU_STACK 0x000000 0x0000000000000000 0x0000000000000000 0x000000 0x000000 RW 0
Section to Segment mapping:
Segment Sections...
00
01 .dynsym .gnu.hash .hash .dynstr .rela.dyn .rodata
02 .text
03 .data.rel.ro .dynamic .relro_padding
04 .data .bss
05 .dynamic
06 .data.rel.ro .dynamic .relro_padding
07
We can see there are many sections and serveral segments. The last part shows how the sections are mapped to the segments. We are mainly interested in the segments of type LOAD, which are the ones to be loaded into memory. We also need the DYNAMIC segment for applying relocations. The nice thing here is that we don't need to worry about which section is code, data, or bss. The segments include a flags field that tells us the permissions of the segment (read, write, execute). We'll use this information to set the correct permissions on the virtual memory regions.
Notice also that the VirtAddr of some segments doesn't necessarily start on a page boundary. However, their Align field tells us that the first page of the segment should be aligned to a page boundary (I'm making a simplifying assumption here that Align values are always equal to x86-64's page size, i.e. 4KiB). Thus, a segment's start page is the segment's VirtAddr rounded down to the nearest page boundary.
ELF Reader
To keep the loader simple, we'll implement a separate ELF reader module that provides an interface to iterate over the sections and segments of an ELF file. Let's add a new file elf.nim to the kernel directory, which will contain the various types and procedures needed to read an ELF file.
We'll start by defining an ElfImage and ElfHeader types, along with supporting types.
# src/kernel/elf.nim
type
ElfImage = object
header: ptr ElfHeader
ElfHeader {.packed.} = object
ident: ElfIdent
`type`: ElfType
machine: ElfMachine
version: uint32
entry: uint64
phoff: uint64
shoff: uint64
flags: uint32
ehsize: uint16
phentsize: uint16
phnum: uint16
shentsize: uint16
shnum: uint16
shstrndx: uint16
ElfIdent {.packed.} = object
magic: array[4, char]
class: ElfClass
endianness: ElfEndianness
version: ElfVersion
osabi: uint8
abiversion: uint8
pad: array[7, uint8]
ElfClass = enum
None = (0, "None")
Bits32 = (1, "32-bit")
Bits64 = (2, "64-bit")
ElfEndianness = enum
None = (0, "None")
Little = (1, "Little-endian")
Big = (2, "Big-endian")
ElfVersion = enum
None = (0, "None")
Current = (1, "Current")
ElfType {.size: sizeof(uint16).} = enum
None = (0, "Unknown")
Relocatable = (1, "Relocatable")
Executable = (2, "Executable")
Shared = (3, "Shared object")
Core = (4, "Core")
ElfMachine {.size: sizeof(uint16).} = enum
None = (0, "None")
Sparc = (0x02, "Sparc")
X86 = (0x03, "x86")
Mips = (0x08, "MIPS")
PowerPC = (0x14, "PowerPC")
ARM = (0x28, "Arm")
Sparc64 = (0x2b, "Sparc64")
IA64 = (0x32, "IA-64")
X86_64 = (0x3e, "x86-64")
AArch64 = (0xb7, "AArch64")
RiscV = (0xf3, "RISC-V")
This should be straightforward. The following fields in ElfHeader are relevant to us:
entry: The virtual address of the entry point. We'll use this to jump to the user task once it's loaded.phoff: The offset of the program header table.phentsize: The size of each entry in the program header table.phnum: The number of entries in the program header table.shoff: The offset of the section header table.shentsize: The size of each entry in the section header table.shnum: The number of entries in the section header table.shstrndx: The index of the section header table entry that contains the section names.
Next, let's define the ElfProgramHeader type.
type
ElfProgramHeader {.packed.} = object
`type`: ElfProgramHeaderType
flags: ElfProgramHeaderFlags
offset: uint64
vaddr: uint64
paddr: uint64
filesz: uint64
memsz: uint64
align: uint64
ElfProgramHeaderType {.size: sizeof(uint32).} = enum
Null = (0, "NULL")
Load = (1, "LOAD")
Dynamic = (2, "DYNAMIC")
Interp = (3, "INTERP")
Note = (4, "NOTE")
ShLib = (5, "SHLIB")
Phdr = (6, "PHDR")
Tls = (7, "TLS")
ElfProgramHeaderFlag = enum
Executable = (0, "E")
Writable = (1, "W")
Readable = (2, "R")
ElfProgramHeaderFlags {.size: sizeof(uint32).} = set[ElfProgramHeaderFlag]
The ElfProgramHeader type contains the following fields:
type: The type of the segment. We're only interested inLOADsegments (to be loaded into memory) andDYNAMICsegments (for applying relocations).flags: The permissions of the segment. We'll use this to mark the segments as read-only, read-write, or executable.offset: The offset of the segment in the file.vaddr: The virtual address of the segment. This is the address where the segment should be loaded into memory relative to the base address.paddr: The physical address of the segment. This is not used in our case.filesz: The size of the segment in the file.memsz: The size of the segment in memory. This can be larger thanfileszif the segment contains uninitialized data (e.g.bsssection).align: The alignment of the segment in memory.
Next, let's define the ElfSectionHeader type.
type
ElfSectionHeader {.packed.} = object
nameoffset: uint32
`type`: ElfSectionType
flags: uint64
vaddr: uint64
offset: uint64
size: uint64
link: uint32
info: uint32
addralign: uint64
entsize: uint64
ElfSectionType {.size: sizeof(uint32).} = enum
Null = (0, "NULL")
ProgBits = (1, "PROGBITS")
SymTab = (2, "SYMTAB")
StrTab = (3, "STRTAB")
Rela = (4, "RELA")
Hash = (5, "HASH")
Dynamic = (6, "DYNAMIC")
Note = (7, "NOTE")
NoBits = (8, "NOBITS")
Rel = (9, "REL")
ShLib = (10, "SHLIB")
DynSym = (11, "DYNSYM")
InitArray = (14, "INIT_ARRAY")
FiniArray = (15, "FINI_ARRAY")
PreInitArray = (16, "PREINIT_ARRAY")
Group = (17, "GROUP")
SymTabShndx = (18, "SYMTAB_SHNDX")
Sections are mostly relevant to the linker, not the loader (which deals with segments). I'm just including it for the sake of completeness.
Now, let's add a proc to initialize an ElfImage object from a pointer to the ELF image in memory. We'll validate some assumptions about the ELF image (e.g. the magic number, the architecture, etc.) and raise an error if the image is not a valid ELF file or if it doesn't meet our expectations.
type
InvalidElfImage = object of CatchableError
UnsupportedElfImage = object of CatchableError
proc initElfImage(image: pointer): ElfImage =
result.header = cast[ptr ElfHeader](image)
if result.header.ident.magic != [0x7f.char, 'E', 'L', 'F']:
raise newException(InvalidElfImage, "Not an ELF file")
if result.header.ident.class != ElfClass.Bits64:
raise newException(UnsupportedElfImage, "Only 64-bit ELF files are supported")
if result.header.ident.endianness != ElfEndianness.Little:
raise newException(UnsupportedElfImage, "Only little-endian ELF files are supported")
if result.header.ident.version != ElfVersion.Current:
raise newException(UnsupportedElfImage, &"Only ELF version {ElfVersion.Current} is supported.")
if result.header.type != ElfType.Shared:
raise newException(UnsupportedElfImage, "Only PIE type ELF files are supported.")
if result.header.machine != ElfMachine.X86_64:
raise newException(UnsupportedElfImage, "Only x86-64 ELF files are supported.")
Next, let's add an iterator to iterate over the segments (i.e. program headers) of the ELF image. The iterator will yield a tuple containing the index of the program header and the program header itself.
iterator segments(image: ElfImage): tuple[i: uint16, ph: ptr ElfProgramHeader] =
let header = image.header
let phoff = header.phoff
let phentsize = header.phentsize
let phnum = header.phnum
for i in 0.uint16 ..< phnum:
let ph = cast[ptr ElfProgramHeader](header +! (phoff + phentsize * i))
yield (i, ph)
Similarily, let's add an iterator to iterate over the section headers of the ELF image.
iterator sections(image: ElfImage): tuple[i: uint16, sh: ptr ElfSectionHeader] =
let header = image.header
let shoff = header.shoff
let shentsize = header.shentsize
let shnum = header.shnum
for i in 0.uint16 ..< shnum:
let sh = cast[ptr ElfSectionHeader](header +! (shoff + shentsize * i))
yield (i, sh)
That's it for the ELF reader. In the next part, we'll use this module to load the loadable segments of an ELF file into memory, apply relocations, and jump to the entry point.