2021-10-fun-with-elf-dynamic-loaders slides
Fun with ELF dynamic loaders
MaskRay
How does the kernel load an executable?
% llvm-readelf -l /tmp/RelA/bin/clang
Elf file type is EXEC (Executable file)
Entry point 0x3c5db90
There are 12 program headers, starting at offset 64
Program Headers:
Type Offset VirtAddr PhysAddr FileSiz MemSiz Flg Align
PHDR 0x000040 0x0000000000200040 0x0000000000200040 0x0002a0 0x0002a0 R 0x8
INTERP 0x0002e0 0x00000000002002e0 0x00000000002002e0 0x00001c 0x00001c R 0x1
[Requesting program interpreter: /lib64/ld-linux-x86-64.so.2]
LOAD 0x000000 0x0000000000200000 0x0000000000200000 0x3a5cb84 0x3a5cb84 R 0x1000
LOAD 0x3a5cb90 0x0000000003c5db90 0x0000000003c5db90 0x52ae1b0 0x52ae1b0 R E 0x1000
LOAD 0x8d0ad40 0x0000000008f0cd40 0x0000000008f0cd40 0xa013f0 0xa013f0 RW 0x1000
LOAD 0x970c130 0x000000000990f130 0x000000000990f130 0x01d290 0x098240 RW 0x1000
TLS 0x8d0ad40 0x0000000008f0bd40 0x0000000008f0bd40 0x000000 0x000020 R 0x8
DYNAMIC 0x9702538 0x0000000009904538 0x0000000009904538 0x000230 0x000230 RW 0x8
GNU_RELRO 0x8d0ad40 0x0000000008f0cd40 0x0000000008f0cd40 0xa013f0 0xa022c0 R 0x1
GNU_EH_FRAME 0x30a2668 0x00000000032a2668 0x00000000032a2668 0x13461c 0x13461c R 0x4
GNU_STACK 0x000000 0x0000000000000000 0x0000000000000000 0x000000 0x000000 RW 0x0
NOTE 0x0002fc 0x00000000002002fc 0x00000000002002fc 0x000020 0x000020 R 0x4
The kernel maps PT_LOAD program headers, and if PT_INTERP exists, loads the interpreter's PT_LOAD program headers.
It doesn't care about relocations, TLS, shared object dependencies, RELRO, etc.
ELF dynamic loader
A position-dependent statically linked executable does not need relocations or dependencies.
A position-independent statically linked executable needs relocations.
All other types of executables need a dynamic loader (aka dynamic linker, rtld (run-time link editor)). People usually name it ld.so because its filename is typically a variant of literal "ld.so".
- load shared object dependencies (
DT_NEEDED) - resolve relocations (
DT_RELA, DT_PLTREL) - call initialization/termination functions (
DT_INIT_ARRAY, DT_FINI_ARRAY) - initialize TLS (
PT_TLS) dlopen, dlsym
A libc implementation typically provides ld.so along with libc/libm/libpthread.
ELF dynamic loaders
- System V release 4 (1988), Solaris 2.0 (1992)
- NetBSD (1993), FreeBSD (1998)
- glibc (1995)
- Android bionic (200x)
It's a pity that glibc did not learn from NetBSD's implementation.
It is (one of?) the most complex part in glibc.
FreeBSD rtld-elf
https://maskray.me/blog/freebsd-src-browsing-on-linux-and-my-rtld-contribution
STB_WEAKin symbol lookupp_memszofPT_GNU_RELROp_vaddr % p_align != 0forPT_TLS
Build glibc 2.35 with LLD 13
https://maskray.me/blog/2021-09-05-build-glibc-with-lld
Per aspera ad astra
The next release glibc 2.35 should be buildable with LLD 13.0.0, with no test regression on aarch64/i386/x86-64 (GCC 10.3.0, 11.2.0)
Remaining work:
- Add a build configuration to
scripts/build-many-glibcs.py
scripts/build-many-glibcs.py compilers x86_64-linux-gnu created GCC has many failures. Needs investigation.
Build glibc with Clang
https://maskray.me/blog/2021-10-10-when-can-glibc-be-built-with-clang
- GCC nested functions
- asm label after first use
- assembly (inline asm parsing, integrated assembler)
- Clang warnings are more picky
Pushed 5 commits to glibc trunk so far.
Improve sanitizer reliability related to TLS
[PATCH] elf: Add __libc_get_static_tls_bounds [BZ #16291] (pending)
- asan/hwasan/msan/tsan need to unpoison static TLS blocks to prevent false positives due to reusing the TLS blocks with a previous thread.
- lsan needs TCB for pointers into
pthread_setspecificregions.
Relocations
typedef struct {
Elf64_Addr r_offset; // Address
Elf64_Xword r_info; // 32-bit relocation type; 32-bit symbol index
} Elf64_Rel;
typedef struct {
Elf64_Addr r_offset; // Address
Elf64_Xword r_info; // 32-bit relocation type; 32-bit symbol index
Elf64_Sxword r_addend; // Addend
} Elf64_Rela;
Dynamic relocations ordered by decreasing count:
R_*_RELATIVE: relative relocationsR_*_JUMP_SLOT: PLT relocations- symbolic (e.g.
R_X86_64_64) R_*_GLOB_DAT: GOT relocations. Identical to a symbolic relocation.R_*_COPY(unfortunate)- TLS descriptor/global-dynamic/local-dynamic/initial-exec
Relative relocations
Many psABI documents use RELA. 24 bytes for one relocation in ELFCLASS64.
Relocations have locality. R_*_RELATIVE are almost always consecutive.
For an R_*_RELATIVE, symbol index = addend = 0.
{r_offset = 0x2000, r_info = (R_X86_64_RELATIVE << 32) | 0, r_addend = 0},
{r_offset = 0x2008, r_info = (R_X86_64_RELATIVE << 32) | 0, r_addend = 0},
{r_offset = 0x2010, r_info = (R_X86_64_RELATIVE << 32) | 0, r_addend = 0},
{r_offset = 0x2018, r_info = (R_X86_64_RELATIVE << 32) | 0, r_addend = 0},
How about a compact representation?
Brainstorm: remove relative relocations
Taking the address of a non-preemptible symbol (and does not trigger GOT optimization).
- virtual table (
clang -fexperimental-relative-c++-abi-vtables) - jump tables
- string literal array (
const char *a[] = {"hello", "world"};) - function pointer array
- ...
There is a (not-too-large) upper bound on the number of removable relative relocations. Some require new ABI and keeping compatibility is difficult. References to preemptible symbols are fundamentally not optimizable.
Idea A: omit r_info
This needs a new relocation section.
section:
.quad 0x2000
.quad 0x2008
.quad 0x2010
.quad 0x2018
Delta encoding with sorting? Try avoiding unaligned/packed structures for ELF. Think about medium/large code models.
Idea B: run-length encoding
Firefox's ELF hack. Improving libxul startup I/O by hacking the ELF format
A base offset followed by a count of subsequent consecutive relocations.
There are many lossless compression techniques. We need one which is easy and efficient.
Idea C: RELR
A base offset followed by 63-bit bitmaps encoding the subsequent relocations.
/* Process RELR relative relocations. */
static void
reloc_relr(Obj_Entry *obj)
{
const Elf_Relr *relr, *relrlim;
Elf_Addr *where;
relrlim = (const Elf_Relr *)((const char *)obj->relr + obj->relrsize);
for (relr = obj->relr; relr < relrlim; relr++) {
Elf_Relr entry = *relr;
if ((entry & 1) == 0) {
where = (Elf_Addr *)(obj->relocbase + entry);
*where++ += (Elf_Addr)obj->relocbase;
} else {
for (long i = 0; (entry >>= 1) != 0; i++)
if ((entry & 1) != 0)
where[i] += (Elf_Addr)obj->relocbase;
where += CHAR_BIT * sizeof(Elf_Relr) - 1;
}
}
}
This is simple and efficient (usually 3% or smaller than R_*_RELATIVE in .rela.dyn)
% ~/projects/bloaty/Release/bloaty clang.pie.relr -- clang.pie
FILE SIZE VM SIZE
-------------- --------------
[NEW] +163Ki [NEW] +163Ki .relr.dyn
+4.9% +32 +5.4% +32 .dynamic
+2.5% +8 [ = ] 0 .shstrtab
-99.5% -13.8Mi -99.5% -13.8Mi .rela.dyn
-8.3% -13.6Mi -8.2% -13.6Mi TOTAL
FreeBSD rtld-elf and glibc ld.so
FreeBSD took it quickly (thanks to kib).
(I think FreeBSD libexec/rtld-elf needs more tests.)
Future work: enable it by default.
* [v2] elf: Support DT_RELR relative relocation format [BZ #27924]
* Need official gABI assignment (Carry Coutant status?)
* Needs to be reserved verbally by Carry (Action item)
* Required for patch acceptance.
* Need BFD port or a released llvm/lld that supports DT_RELR to review patches.
* Minimally a 32-bit and 64-bit port that can build glibc and passes regression testing.
* Required for patch review.
* Official glibc relese with feature?
* Need BFD port to support build-many-glibcs to provide testing confidence.
* HJ: Would like to see a BFD port before a glibc release with the features.
* Sufficient to have a released binutils with DT_RELR also.
* Release date of released static linkers with support should be close to glibc release with feature.
* When glibc is released users can pick a static linker to test with (binutils or lld).
Lack of GNU ld support (PR27923) is an issue. (If you are not a binutils maintainer, think again before taking a stab. Actually MaskRay has sent a message to Nick Clifton for this task.)