diff options
Diffstat (limited to '04_dynld_nostd/README.md')
| -rw-r--r-- | 04_dynld_nostd/README.md | 505 |
1 files changed, 490 insertions, 15 deletions
diff --git a/04_dynld_nostd/README.md b/04_dynld_nostd/README.md index e71246b..fc5c338 100644 --- a/04_dynld_nostd/README.md +++ b/04_dynld_nostd/README.md @@ -9,6 +9,9 @@ environment, by mapping the shared library dependency and resolving all relocations. +> In code blocks included in this page, the error checking code is omitted to +> purely focus on the functionality they are trying to show-case. + --- ## Creating the shared library `libgreet.so` @@ -213,7 +216,8 @@ void dl_entry(const uint64_t* prctx) { With the SystemV ABI descriptor, the next step is to extract the information of the user program that are of interest to the dynamic linker. -That information is captured in a `dynamic shared object (dso)` structure: +That information is captured in a `dynamic shared object (dso)` structure as +defined below. ```c typedef struct { uint8_t* base; // Base address. @@ -234,11 +238,11 @@ However before using the `vaddr` field, first the `base address` of the `dso` needs to be computed. This is important because addresses in the program header and the dynamic section are relative to the `base address`. -Computing the `base address` can be done by using the `PT_PHDR` program header -which describes the program headers itself. The absolute `base address` is then +The `base address` can be computed by using the `PT_PHDR` program header which +describes the program headers itself. The absolute `base address` is then computed by subtracting the relative `PT_PHDR->vaddr` from the absolute address in the `AT_PDHR` entry from the auxiliary vector. Looking at the figure below -this becomes more clearer. +this becomes more clear. ```text VMA | | @@ -255,8 +259,8 @@ base address -> | | - > `pie` executables it is typically **not** `0x0`. Looking at the concrete implementation in the dynamic linker, computing the -`base address` can be see here and the result is stored in the `dso` object -representing the user program. +`base address` is done while iterating over the program headers. The result is +stored in the `dso` object representing the user program. ```c static Dso get_prog_dso(const SystemVDescriptor* sysv) { ... @@ -282,12 +286,12 @@ typedef struct { }; } Elf64Dyn; ``` -> Tags are defined in [elf.h](../lib/include/elf.h). +> Available `tags` are defined in [elf.h](../lib/include/elf.h). -With the absolute `base address` of the `dso` the `.dynamic` section can be -located by using the address from the `PT_DYNAMIC->vaddr`. When iterating over -the program headers above, this offset was already stored in `dynoff` and -passed to the `decode_dynamic` function. +The `.dynamic` section is located by using the offset from the +`PT_DYNAMIC->vaddr` entry and adding it to the absolute `base address` of the +`dso`. When iterating over the program headers above, this offset was already +stored in `dynoff` and passed to the `decode_dynamic` function. ```c static void decode_dynamic(Dso* dso, uint64_t dynoff) { for (const Elf64Dyn* dyn = (const Elf64Dyn*)(dso->base + dynoff); dyn->tag != DT_NULL; ++dyn) { @@ -299,10 +303,14 @@ static void decode_dynamic(Dso* dso, uint64_t dynoff) { } ... ``` - -The last step to extract the info of the user program is to store the address -of the entry function where the dynamic linker will pass control to later. This -can be found in the auxiliary vector in the `AT_ENTRY` entry. +> The value of `DT_NEEDED` entries contain indexes into the `string table +> (DR_STRTAB)` to get the name of the share library dependency. + +The last step to extract the information of the user program is to store the +address of the `entry function` where the dynamic linker will pass control to +once the execution environment is set up. +The address of the `entry function` can be retrieved from the `AT_ENTRY` entry +in the auxiliary vector. ```c static Dso get_prog_dso(const SystemVDescriptor* sysv) { ... @@ -310,9 +318,476 @@ static Dso get_prog_dso(const SystemVDescriptor* sysv) { ``` ### (2) Map `libgreet.so` + +The next step of the dynamic linker is to map the shared library dependency of +the main program. Therefore the value of the `DT_NEEDED` entry in the +`.dynamic` section is used. This entry holds an index into the `string table` +where the name of the dependency can be retrieved from. +```c +static const char* get_str(const Dso* dso, uint64_t idx) { + return (const char*)(dso->base + dso->dynamic[DT_STRTAB] + idx); +} + +void dl_entry(const uint64_t* prctx) { + ... + const Dso dso_lib = map_dependency(get_str(&dso_prog, dso_prog.needed[0])); +``` +> In this concrete case the main program only has a single shared library +> dependency. However ELF files can have multiple dependencies, in that case +> the `.dynamic` section contains multiple `DT_NEEDED` entries. + +The task of the `map_dependency` function now is to iterate over the program +headers of the shared library and map the segments described by each `PT_LOAD` +entry from file system into the virtual address space of the process. + +To find the program headers, the first step is to read in the ELF header +because this header contains the file offset and the number of program headers. +This information is then used to read in the program headers from the file. +```c +typedef struct { + uint64_t phoff; // Program header file offset. + uint16_t phnum; // Number of program header entries. + ... +} Elf64Ehdr; + +static Dso map_dependency(const char* dependency) { + const int fd = open(dependency, O_RDONLY); + + // Read ELF header. + Elf64Ehdr ehdr; + read(fd, &ehdr, sizeof(ehdr); + + // Read Program headers at offset `phoff`. + Elf64Phdr phdr[ehdr.phnum]; + pread(fd, &phdr, sizeof(phdr), ehdr.phoff); + ... +``` +> Full definition of the `Elf64Ehdr` and `Elf64Phdr` structures are available +> in [elf.h](../lib/include/elf.h). + +With the program headers available, the different `PT_LOAD` segments can be +mapped. The strategy here is to first map a whole region in the virtual address +space, big enough to hold all the `PT_LOAD` segments. Once the allocation +succeeded the single `PT_LOAD` segments can be mapped over the allocated +region. + +To compute the length of the initial allocation, the `start` and `end` address +must be computed by iterating over all `PT_LOAD` entries and saving the minimal +and maximal address. +After that, the memory region is `mmaped` as private & anonymous mapping with +`address == 0`, telling the OS to choose a virtual address, and `PROT_NONE` +as the `PT_LOAD` segments define their own protection flags. +```c +static Dso map_dependency(const char* dependency) { + ... + // Compute start and end address. + uint64_t addr_start = (uint64_t)-1; + uint64_t addr_end = 0; + for (unsigned i = 0; i < ehdr.phnum; ++i) { + const Elf64Phdr* p = &phdr[i]; + if (p->type == PT_LOAD) { + if (p->vaddr < addr_start) { + addr_start = p->vaddr; + } else if (p->vaddr + p->memsz > addr_end) { + addr_end = p->vaddr + p->memsz; + } + } + } + + // Page align addresses. + addr_start = addr_start & ~(PAGE_SIZE - 1); + addr_end = (addr_end + PAGE_SIZE - 1) & ~(PAGE_SIZE - 1); + + // Allocate region big enough to fit all `PT_LOAD` sections. + uint8_t* map = mmap(0 /* addr */, addr_end - addr_start /* len */, + PROT_NONE /* prot */, MAP_PRIVATE | MAP_ANONYMOUS /* flags */, + -1 /* fd */, 0 /* file offset */); +``` + +Now the single `PT_LOAD` segments can be mapped from the ELF file of the shared +library using the open file descriptor `fd` from above.<br> +A segment could contain ELF sections of type `SHT_NOBITS` which contributes to +the segments memory image but don't contain actual data in the ELF file on disk +(typical for `.bss` the zero initialized section). Those sections are normally +at the end of the segment making the `PT_LOAD->memzsz > PT_LOAD->filesz` and +are initialized to `0` during runtime. +```c +static Dso map_dependency(const char* dependency) { + ... + // Compute base address for library. + uint8_t* base = map - addr_start; + + for (unsigned i = 0; i < ehdr.phnum; ++i) { + const Elf64Phdr* p = &phdr[i]; + if (p->type != PT_LOAD) { + continue; + } + + // Page align addresses. + uint64_t addr_start = p->vaddr & ~(PAGE_SIZE - 1); + uint64_t addr_end = (p->vaddr + p->memsz + PAGE_SIZE - 1) & ~(PAGE_SIZE - 1); + uint64_t off = p->offset & ~(PAGE_SIZE - 1); + + // Compute segment permissions. + uint32_t prot = (p->flags & PF_X ? PROT_EXEC : 0) | + (p->flags & PF_R ? PROT_READ : 0) | + (p->flags & PF_W ? PROT_WRITE : 0); + + // Mmap single `PT_LOAD` segment. + mmap(base + addr_start, addr_end - addr_start, prot, MAP_PRIVATE | MAP_FIXED, fd, off); + + // Initialize trailing length (no allocated in ELF file). + if (p->memsz > p->filesz) { + memset(base + p->vaddr + p->filesz, 0 /* byte */, p->memsz - p->filesz /*len*/); + } + } +``` + +With that the shared library dependency is mapped in to the virtual address +space of the user program. The last step is to decode the `.dynamic` section +and initialize the `dso` structure. This is the same as already done for the +user program above and details can be seen in the implementation in +[map_dependency - dynld.c](./dynld.c). + ### (3) Resolve relocations + +After mapping the shared library the next step is to resolve relocations. +This is the process of resolving references to symbols to actual addresses. For +shared libraries this must be done at runtime rather than static link time as +the `base address` of a shared library is only known at runtime. + +One central structure for resolving relocations is the `LinkMap`. This is a +linked list of `dso` objects which defines the order in which `dso` objects are +used when performing symbol lookup. + +```c +typedef struct LinkMap { + const Dso* dso; // Pointer to Dso list object. + const struct LinkMap* next; // Pointer to next LinkMap entry ('0' terminates the list). +} LinkMap; +``` + +In this implementation the `LinkMap` is setup as follows `main -> libgreet.so`, +meaning that symbols are first looked up in `main` and only if they are not +found, `libgreet.so` will be searched. +```c +void dl_entry(const uint64_t* prctx) { + ... + const LinkMap map_lib = {.dso = &dso_lib, .next = 0}; + const LinkMap map_prog = {.dso = &dso_prog, .next = &map_lib}; +``` + +With the `LinkMap` setup the `dynld.so` can start processing relocations of the +main program and the shared library. The dynamic linker will process the +following two relocation tables for all `dso` objects on startup: +- `DT_RELA`: Relocations that **must** be resolved during startup. +- `DT_JMPREL`: Relocations associated with the procedure linkage table (those + could be resolved lazily during runtime, but here they are directly resolved + during startup). + +```c +static void resolve_relocs(const Dso* dso, const LinkMap* map) { + for (unsigned long relocidx = 0; relocidx < (dso->dynamic[DT_RELASZ] / sizeof(Elf64Rela)); ++relocidx) { + const Elf64Rela* reloc = get_reloca(dso, relocidx); + resolve_reloc(dso, map, reloc); + } + + for (unsigned long relocidx = 0; relocidx < (dso->dynamic[DT_PLTRELSZ] / sizeof(Elf64Rela)); ++relocidx) { + const Elf64Rela* reloc = get_pltreloca(dso, relocidx); + resolve_reloc(dso, map, reloc); + } +} +``` + +The x86_64 SystemV ABI states that x86_64 only uses `RELA` relocation entries, +which are defined as: +```c +typedef struct { + uint64_t offset; // Virtual address of the storage unit affected by the relocation. + uint64_t info; // Symbol table index + relocation type. + int64_t addend; // Constant value used to compute the relocation value. +} Elf64Rela; +``` +So each relocation entry provides the following information required to perform +the relocation +- Virtual address of the storage unit that is affected by the relocation. This + is the address in memory where the actual address of the resolved symbol will + be stored to. It is encoded in the `Elf64Rela->offset` field. +- The symbol that needs to be looked up to resolve the relocation. The + **upper** 32 bit of the `Elf64Rela->info` encode the index into the symbol + table. +- The relocation type which describes how the relocation should be performed in + detail. It is encoded in the **lower** 32 bit of the `Elf64Rela->info` field. + +The x86_64 SystemV ABI defines many relocation types. As an example, the +following two sub-sections will discuss the relocation types +`R_X86_64_JUMP_SLOT` and `R_X86_64_COPY`. + +#### Example: Resolving `R_X86_64_JUMP_SLOT` relocation from `DT_JMPREL` table + +Relocation of type `R_X86_64_JUMP_SLOT` are used for entries related to the +`procedure linkage table (PLT)` which is used for function calls between `dso` +objects. This can be seen here, as the main program calls for example the +`get_greet` function provided by the `libgreet.so` shared library which creates +such a relocation entry. +```bash +> readelf -r main libgreet.so +... + +Relocation section '.rela.plt' at offset 0x490 contains 2 entries: + Offset Info Type Sym. Value Sym. Name + Addend +000000404018 000200000007 R_X86_64_JUMP_SLO 0000000000000000 get_greet + 0 +000000404020 000400000007 R_X86_64_JUMP_SLO 0000000000000000 get_greet2 + 0 +``` + +To resolve relocations of this type the following steps need to be performed: +1. Extract the name of the symbol from the relocation entry. +1. Find the address of the symbol by walking the `LinkMap` and searching for + the symbol. +1. Patch the affected address of the relocation entry with the address of the + symbol. + +The code block below shows a simplified version of the `resolve_reloc` function +which only shows lines that are important for handling relocations of type. +`R_X86_64_JUMP_SLOT`. +```c +static void resolve_reloc(const Dso* dso, const LinkMap* map, const Elf64Rela* reloc) { + // Get symbol information. + const int symidx = ELF64_R_SYM(reloc->info); + const Elf64Sym* sym = get_sym(dso, symidx); + const char* symname = get_str(dso, sym->name); + + // Get relocation type. + const unsigned reloctype = ELF64_R_TYPE(reloc->info); + // assume reloctype == R_X86_64_JUMP_SLOT + + // Lookup address of symbol. + void* symaddr = 0; + for (const LinkMap* lmap = map->next; lmap && symaddr == 0; lmap = lmap->next) { + symaddr = lookup_sym(lmap->dso, symname); + } + + // Patch address affected by the relocation. + *(uint64_t*)(dso->base + reloc->offset) = (uint64_t)symaddr; +} +``` +> The full implementation of the `resolve_reloc` function can be reviewed in +> [resolve_reloc - dynld.c](./dynld.c). + +#### Example: Resolving `R_X86_64_COPY` relocation from `DT_RELA` table + +Relocations of type `R_X86_64_COPY` are used in the main program when referring +to an external object provided by a shared library, as for example a global +variable. Here the main program makes use the global variable `extern int +gCalled;` defined in the `libgreet.so` which creates relocations as shown +in the `readelf` dump below. +```bash +> readelf -r main libgreet.so + +File: main + +Relocation section '.rela.dyn' at offset 0x478 contains 1 entry: + Offset Info Type Sym. Value Sym. Name + Addend +000000404028 000300000005 R_X86_64_COPY 0000000000404028 gCalled + 0 + +... + +File: libgreet.so + +Relocation section '.rela.dyn' at offset 0x3f0 contains 3 entries: + Offset Info Type Sym. Value Sym. Name + Addend +... +000000003ff8 000400000006 R_X86_64_GLOB_DAT 0000000000004020 gCalled + 0 + +... +``` + +For relocations of this type, the static linker allocates space for the +external symbol in the main programs `.bss` sections. +```bash +> objdump -M intel -d -j .bss main + +main: file format elf64-x86-64 + +Disassembly of section .bss: + +0000000000404028 <gCalled>: + 404028: 00 00 00 00 +``` + +Any reference to the symbol from within the main program is directly resolved +during static link time into the `.bss` section. +```bash +> objdump -M intel -d main + +main: file format elf64-x86-64 + +Disassembly of section .text: + +0000000000401030 <_start>: + ... + 401088: 8b 05 9a 2f 00 00 mov eax,DWORD PTR [rip+0x2f9a] # 404028 <gCalled> + ... +``` + +The `R_X86_64_COPY` relocation instructs the dynamic linker now to copy the +initial value from the shared library that provides it into the allocated space +in the main programs `.bss` section. + +Shared libraries on the other hand that also reference the same symbol will go +though a `GOT` entry that is patched by the dynamic linker to point to the +location in the `.bss` section of the main program. +Below this can be seen by the `mov` instruction at address `1024` that the +relative address `3ff8` is dereferenced to get the value of the `gCalled` +variable. In the `readelf` dump above it can be seen that there is a relocation +of type `R_X86_64_GLOB_DAT` for symbol `gCalled` affecting the relative address +`3ff8` in the shared library. +```bash +> objdump -M intel -d -j .text -j .got libgreet.so + +libgreet.so: file format elf64-x86-64 + +Disassembly of section .text: + +0000000000001020 <get_greet>: + 1020: 55 push rbp + 1021: 48 89 e5 mov rbp,rsp + 1024: 48 8b 05 cd 2f 00 00 mov rax,QWORD PTR [rip+0x2fcd] # 3ff8 <gCalled-0x28> + +... + +Disassembly of section .got: + +0000000000003ff8 <.got>: + ... +``` + +The following figure visualizes the described layout above in some more detail. +```text + libso + +-----------+ + | .text | + main prog | | ref + +-----------+ | ... [foo] |--+ + | .text | R_X86_64_GLOB_DAT | | | +ref | | Patch address of +-----------+ | + +--| ... [foo] | foo in .got. | .got | | + | | | +------------------>| foo: |<-+ + | +-----------+ | | | + | | .bss | | +-----------+ + | | | / | .data | + +->| foo: ... |<--------------------| foo: ... | + | | R_X86_64_COPY | | + +-----------+ Copy initial value. +-----------+ +``` + +To resolve relocations of type `R_X86_64_COPY` the following steps need to be +performed: +1. Extract the name of the symbol from the relocation entry. +1. Find the address of the symbol by walking the `LinkMap` and searching for + the symbol and excluding the symbol table of the main program `dso`. +1. Copy over the initial value of the symbol into the affected address of the + relocation entry (`.bss` section of the main program). + +The code block below shows a simplified version of the `resolve_reloc` function +which only shows lines that are important for handling relocations of type. +```c +static void resolve_reloc(const Dso* dso, const LinkMap* map, const Elf64Rela* reloc) { + // Get symbol information. + const int symidx = ELF64_R_SYM(reloc->info); + const Elf64Sym* sym = get_sym(dso, symidx); + const char* symname = get_str(dso, sym->name); + + // Get relocation type. + const unsigned reloctype = ELF64_R_TYPE(reloc->info); + // assume reloctype == R_X86_64_COPY + + // Lookup address of symbol. + void* symaddr = 0; + for (const LinkMap* lmap = (reloctype == R_X86_64_COPY ? map->next : map); lmap && symaddr == 0; lmap = lmap->next) { + symaddr = lookup_sym(lmap->dso, symname); + } + + // Copy initial value of variable into address affected by the relocation. + memcpy(dso->base + reloc->offset, (void*)symaddr, sym->size); +} +``` +> The full implementation of the `resolve_reloc` function can be reviewed in +> [resolve_reloc - dynld.c](./dynld.c). + ### (4) Run `init` functions + +The next step before transferring control to the main program is to run all the +`init` functions for the `dso` objects. Examples for those are global +`constructors`. +```c +typedef void (*initfptr)(); + +static void init(const Dso* dso) { + if (dso->dynamic[DT_INIT]) { + initfptr* fn = (initfptr*)(dso->base + dso->dynamic[DT_INIT]); + (*fn)(); + } + + size_t nfns = dso->dynamic[DT_INIT_ARRAYSZ] / sizeof(initfptr); + initfptr* fns = (initfptr*)(dso->base + dso->dynamic[DT_INIT_ARRAY]); + while (nfns--) { + (*fns++)(); + } +} + +void dl_entry(const uint64_t* prctx) { + ... + // Initialize library. + init(&dso_lib); + // Initialize main program. + init(&dso_prog); + ... +} +``` + ### (5) Run the user program + +At that point the execution environment is setup and control can be transferred +from the dynamic linker to the main program. +```c +void dl_entry(const uint64_t* prctx) { + ... + // Transfer control to user program. + dso_prog.entry(); + ... +} +``` + ### (6) Run `fini` functions +After the main program returned and before terminating the process all the +`fini` functions for the `dso` objects are executed. Examples for those are +global `destructors`. +```c +typedef void (*finifptr)(); + +static void fini(const Dso* dso) { + size_t nfns = dso->dynamic[DT_FINI_ARRAYSZ] / sizeof(finifptr); + finifptr* fns = (finifptr*)(dso->base + dso->dynamic[DT_FINI_ARRAY]) + nfns /* reverse destruction order */; + while (nfns--) { + (*--fns)(); + } + + if (dso->dynamic[DT_FINI]) { + finifptr* fn = (finifptr*)(dso->base + dso->dynamic[DT_FINI]); + (*fn)(); + } +} + +void dl_entry(const uint64_t* prctx) { + ... + // Finalize main program. + fini(&dso_prog); + // Finalize library. + fini(&dso_lib); + ... +} +``` + [gcc-fn-attributes]: https://gcc.gnu.org/onlinedocs/gcc/Common-Function-Attributes.html#Common-Function-Attributes |