Fun with ELF dynamic loaders

MaskRay

How does the kernel load an executable?

{all|3-5,10-15,20}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
% 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/2021-08-22-freebsd-src-browsing-on-linux-and-my-rtld-contribution

  • STB_WEAK in symbol lookup
  • p_memsz of PT_GNU_RELRO
  • p_vaddr % p_align != 0 for PT_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.

[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_setspecific regions.

Relocations

1
2
3
4
5
6
7
8
9
10
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 relocations
  • R_*_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.

1
2
3
4
{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.

1
2
3
4
5
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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/* 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)

1
2
3
4
5
6
7
8
% ~/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.

glibc

1
2
3
4
5
6
7
8
9
10
11
12
13
* [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.)