--- # try also 'default' to start simple theme: default # random image from a curated Unsplash collection by Anthony # like them? see https://unsplash.com/collections/94734566/slidev # background: https://source.unsplash.com/collection/94734566/1920x1080 # apply any windi css classes to the current slide class: 'text-center' # https://sli.dev/custom/highlighters.html highlighter: shiki # show line numbers in code blocks lineNumbers: false # persist drawings in exports and build drawings: persist: false # use UnoCSS (experimental) css: unocss routerMode: 'hash' --- # Relocation overflow and code models --- layout: 'intro' ---

MaskRay (宋方睿)

LLVM contributor since 2017, ld.lld and Clang Driver code owner, maintainer of a bunch of components
binutils, glibc, GCC
MaskRay
maskray.me
--- ## Relocation overflow Relocations can be seen as a protocol between the assembler and the linker. Relocations are needed to support multiple translation units. ``` % gcc -fuse-ld=bfd @response.txt ... a.o: in function `_start': (.text+0x0): relocation truncated to fit: R_X86_64_PC32 against `.text' % gcc -fuse-ld=lld @response.txt ld.lld: error: a.o:(.text+0x0): relocation R_X86_64_PC32 out of range: -2147483649 is not in [-2147483648, 2147483647]; references section '.text' ``` The executable is too large. --- ## Static linking By including all dependencies within the executable itself, it can run without relying on external shared objects. This eliminates the potential risks associated with updating dependencies separately. Certain users prefer static linking or mostly static linking for the sake of deployment convenience and performance aspects: * Link-time optimization is more effective when all dependencies are known. Providing shared object information during executable optimization is possible, but it may not be a worthwhile engineering effort. * Profiling techniques are more efficient dealing with one single executable. * The traditional ELF dynamic linking approach incurs overhead to support [symbol interposition](/blog/2021-05-16-elf-interposition-and-bsymbolic). * Dynamic linking involves PLT and GOT, which can introduce additional overhead. Static linking eliminates the overhead. * Loading libraries in the dynamic loader has a time complexity `O(|libs|^2*|libname|)`. The existing implementations are designed to handle tens of shared objects, rather than a thousand or more. In scenarios where the distributed program contains a significant amount of code (related: software bloat), employing full or mostly static linking can result in very large executable files. Consequently, certain relocations may be close to the distance limit, and even a minor disruption (e.g. add a function or introduce a dependency) can trigger relocation overflow linker errors. --- ## Relocation overflow ```c int var0; // known non-preemptible if -fno-pic or -fpie extern int var1; // possibly-preemptible int callee(); int caller() { return callee() + var0 + var1; } ``` ```asm # gcc -S -O1 -fpie -mno-direct-extern-access -masm=intel a.c .globl caller caller: call callee@PLT # R_X86_64_PLT32 add eax, DWORD PTR [rip + var0] # R_X86_64_PC32 mov rdx, QWORD PTR var1@GOTPCREL[rip] # R_X86_64_REX_GOTPCRELX; rdx = .got[n] = &var1 add eax, DWORD PTR [rdx] # load from &var1 .bss .globl var0 var0: .long 0 ``` All of `R_X86_64_PLT32`, `R_X86_64_PC32`, and `R_X86_64_REX_GOTPCRELX` have a value range of `[-2**31,2**31)`. If the referenced symbol is too far away from the relocated location, we may get a relocation overflow. --- * `.text <-> .rodata` * `.text <-> .eh_frame`: `.eh_frame` has 32-bit offsets. * `.text <-> .data/.bss` * `.rodata <-> .data/.bss` In many programs, `.text <-> .data/.bss` relocations have the most stringent constraints. Overflows due to `.text <-> .rodata` relocations are possible but rare (although I have encountered such issues in the past). `.rodata <-> .data/.bss` overflows are generally infrequent. However, caution must be exercised when working with metadata `.quad label-.` instead of `.long label-.`. Such issues can be easily addressed on the compiler side. --- ## x86-64 code models * Small: symbols are required to be located within the range `[0, 2**31 - 2**24)`. Use 32-bit PC-relative or absolute addressing * Kernel: similar to the small code model, but symbols are within the high end range * Medium: keep using 32-bit offsets for code and GOT, but split data sections into 2 parts: regular and large. Large data can be more than 2GiB away * Large: all of code, GOT, and data can be more than 2GiB away --- ### x86-64 medium code model The medium code model maintains the assumption that code and the GOT is within the ±2GiB range from the program counter, while allowing data to be located outside of that range. Data that resides outside the range is placed in large data sections such as `.lrodata`, `.ldata`, and `.lbss`, as well as `.ldata`'s variants like `.ldata.rel`, `.ldata.rel.local`, `.ldata.rel.ro`, and `.ldata.rel.ro.local`. `-mlarge-data-threshold` decides whether a data section should be treated as large. Accessing code and GOT-indirect data has the same code sequence as the small code model. To access data without GOT indirection (usually a known non-preemptible symbol, e.g. `var0`), GCC obtains the address of the GOT base symbol `_GLOBAL_OFFSET_TABLE_`, then adds the offset from `_GLOBAL_OFFSET_TABLE_` to the symbol. --- ```asm # gcc -S -O1 -fpie -mcmodel=medium -mlarge-data-threshold=3 -masm=intel a.c call callee@PLT # R_X86_64_PLT32 lea rdx, _GLOBAL_OFFSET_TABLE_[rip] # rdx = &_GLOBAL_OFFSET_TABLE_ movabs rcx, OFFSET FLAT:var0@GOTOFF # R_X86_64_GOTOFF64; rcx = &var0 - &_GLOBAL_OFFSET_TABLE_ add eax, DWORD PTR [rcx+rdx] # load from &var0 mov rdx, QWORD PTR var1@GOTPCREL[rip] # R_X86_64_REX_GOTPCRELX; rdx = .got[n] = &var1 add eax, DWORD PTR [rdx] # load from &var1 ``` For position-dependent code, accessing data without GOT indirection is simplified as we can just use abolute addressing. ```asm # gcc -S -O1 -fno-pic -mcmodel=medium -mno-direct-extern-access -mlarge-data-threshold=3 -masm=intel a.c call callee # R_X86_64_PLT32 mov edx, eax movabs eax, DWORD PTR [var0] # R_X86_64_64; load from &var0 add eax, edx mov rdx, QWORD PTR var1@GOTPCREL[rip] # R_X86_64_REX_GOTPCRELX; rdx = .got[n] = &var1 add eax, DWORD PTR [rdx] # load from &var1 ``` --- ### x86-64 large code model In the large code model, we no longer assume that GOT is within the ±2GiB range from the program counter, so `lea rdx, _GLOBAL_OFFSET_TABLE_[rip]` cannot be used. An extra `movabs` instruction is needed to obtain the address of `_GLOBAL_OFFSET_TABLE_`. Similarly, for a function call, we no longer assume that the address of the function or its PLT entry is within the ±2GiB range from the program counter, so `call callee` cannot be used. Actually, `call callee` can still be used if we implement range extension thunks in the linker, unfortunately GCC/GNU ld did not pursue this direction. --- ```asm # gcc -S -O1 -fpie -mcmodel=large -masm=intel .L2: lea r15, .L2[rip] # r15 = &.L2 movabs r11, OFFSET FLAT:_GLOBAL_OFFSET_TABLE_-.L2 # R_X86_64_GOTPC64; r11 = &_GLOBAL_OFFSET_TABLE_ - &.L2 add r15, r11 # r15 = &_GLOBAL_OFFSET_TABLE_ mov eax, 0 movabs rdx, OFFSET FLAT:callee@PLTOFF # R_X86_64_PLTOFF64; rdx = (the address of callee or its PLT) - &_GLOBAL_OFFSET_TABLE_ add rdx, r15 # rdx = the address of callee or its PLT call rdx # indirectly call callee movabs rdx, OFFSET FLAT:var0@GOTOFF # R_X86_64_GOTOFF64; rdx = &var0 - &_GLOBAL_OFFSET_TABLE_ add eax, DWORD PTR [rdx+r15] # load from &var0 movabs rdx, OFFSET FLAT:var1@GOT # R_X86_64_GOT64; rdx = &.got[n] - _GLOBAL_OFFSET_TABLE_ mov rdx, QWORD PTR [r15+rdx] # rdx = .got[n] = &var1 add eax, DWORD PTR [rdx] # load from &var1 ``` ```asm # gcc -S -O1 -fno-pic -mcmodel=large -masm=intel a.c movabs rdx, OFFSET FLAT:callee # R_X86_64_64; obstain the address of callee; canonical PLT entry if defined in a DSO call rdx mov edx, eax movabs eax, DWORD PTR [var0] # R_X86_64_64; load from &var0 add eax, edx movabs rdx, QWORD PTR [var1] # R_X86_64_64; load from &var1; copy relocation if var1 is defined in a DSO add eax, edx ``` --- ### x86-64 linker requirement GNU ld uses the following section layout in its internal linker scripts: ``` .text .rodata # if -z separate-code, MAXPAGESIZE alignment RELRO # DATA_SEGMENT_ALIGN .data # DATA_SEGMENT_RELRO_END .bss .lbss .lrodata # MAXPAGESIZE alignment .ldata # MAXPAGESIZE alignment ``` For ld.lld, I am contemplating the following section layout: ``` .lrodata .rodata .text # if --ro-segment, MAXPAGESIZE alignment RELRO # MAXPAGESIZE alignment .data # MAXPAGESIZE alignment .bss .ldata # MAXPAGESIZE alignment .lbss ``` --- ## Large data sections We have mentioned that when using `-mcmodel=medium`, GCC generates both regular and large data sections. In practice, programs often include a mix of object files built with small and medium/large code models. The small code model components may come from prebuilt object files (e.g. libc). The large data sections do not exert relocation pressure on sections in object files built with `-mcmodel=small`. However, GCC only generates regular data sections with `-mcmodel=large`. `-mlarge-data-threshold` is ignored. As a result, the data sections built with `-mcmodel=large` may exert relocation pressure on sections in object files with `-mcmodel=small`. I propose that we make `-mcmodel=large` respect `-mlarge-data-threshold` and generate large data sections as well. [Large data sections for the large code model](https://groups.google.com/g/x86-64-abi/c/jnQdJeabxiU). --- ## AArch64 code models * Small: a maximum text segment size of 2GiB and a maximum combined span of text and data segments of 4GiB. The maximum combined span of text and data segments is larger than that of x86-64. * Medium: ... * Large: ... For data references from code, x86-64 uses `R_X86_64_REX_GOTPCRELX`/`R_X86_64_PC32` relocations, which have a smaller range `[-2**31,2**31)`. In contrast, AArch64 employs `R_AARCH64_ADR_PREL_PG_HI21` relocations, which has a doubled range of `[-2**32,2**32)`. This larger range makes it unlikely for AArch64 to encounter relocation overflow issues before the binary becomes excessively oversized for x86-64. ```asm bl callee // R_AARCH64_CALL26; [-2**27, 2**27) adrp x8, var0 // R_AARCH64_ADR_PREL_PG_HI21; [-2**32,2**32) ldr w8, [x8, :lo12:var0] // R_AARCH64_LDST32_ABS_LO12_NC ``` The shorter range of `R_AARCH64_CALL26` doesn't matter. The linker will generate [range extension thunks](/blog/2023-03-05-linker-notes-on-aarch64) if `callee` is not directly reachable. GCC and Clang don't implement `-mcmodel=large` for PIC. Clang doesn't implement `-mcmodel=medium`. This makes sense as we haven't identified a use case for the unimplemented models yet. --- ## Power architecture code models Object file sizes are usually much larger than x86-64's. GCC defaults to the medium code model, which is like x86-64 and AArch64's small code model. Data symbols and TOC/GOT entries are assumed to be within the `[-0x80008000, 0x7fff8000)` range from the TOC. ```asm # powerpc64le-linux-gnu-gcc -S -O1 -fpie -mcmodel=medium -mcpu=power10 a.c bl callee@notoc # R_PPC64_REL24_NOTOC pld 9,var1@got@pcrel # R_PPC64_GOT_PCREL34; r9 = &.got[n] for var1 lwz 10,0(9) # load from &.got[n] plwz 8,.LANCHOR0@pcrel # R_PPC64_PCREL34; load from &var0 add 9,10,8 add 9,9,3 extsw 3,9 ``` --- In the large code model, GCC simply uses GOT-indirect addressing to access data symbols, including the non-preemptible ones. This maintains the assumption that the GOT entries are within the `[-0x80008000, 0x7fff8000)` range from the TOC, so the large code model is more limited than x86-64's. ```asm addis 9,2,.LC0@toc@ha # R_PPC64_TOC16_HA ld 9,.LC0@toc@l(9) # R_PPC64_TOC16_LO_DS lwz 8,0(9) addis 9,2,.LC1@toc@ha # R_PPC64_TOC16_HA ld 9,.LC1@toc@l(9) # R_PPC64_TOC16_LO_DS lwz 10,0(9) add 9,10,8 add 9,9,3 extsw 3,9 ``` --- ## Mitigation There are several strategies to mitigate relocation overflow issues. * Make the program smaller by reducing code and data size. * Partition the large monolithic executable into the main executable and a few shared objects. * Use compiler options such as `-Os`, `-Oz` and link-time optimization that focuses on decreasing the code size. * Use linker script commands [`INSERT BEFORE` and `INSERT AFTER`](/blog/2021-07-04-sections-and-overwrite-sections#insert-before-and-insert-after) to reorder output sections. --- ## Debug information For large executables, it is possible to encounter DWARF32 limitation (e.g. `relocation R_X86_64_32 out of range`). I will address this topic in another article.