(In celebration of my 2800th llvm-project commit) Happy Halloween!

This article describes how improving the representation of ELF relative relocations can greatly decrease file sizes. My /usr/bin executables can be 8% smaller and my /usr/lib/lib*.so* shared objects can be 4.8% with the optimization.

An ELF linker performs the following steps to process an absolute relocation type whose width equals the word size (e.g. R_AARCH64_ABS64, R_X86_64_64).

1
2
3
4
5
6
7
8
9
10
11
12

if (undefined_weak || (!preemptible && (no_pie || is_shn_abs)))
  link-time constant
else if (SHF_WRITE || znotext) {
  if (preemptible)
    emit a symbolic relocation (e.g. R_X86_64_64)
  else
    emit a relative relocation (e.g. R_X86_64_RELATIVE)
} else if (!shared && (copy_relocation || canonical_plt_entry)) {
  ...
} else {
  error
}

In -pie or -shared mode, the linker produces a relative relocation (R_*_RELATIVE) if the symbol is non-preemptible. The dynamic relocation is called a relative relocation. -no-pie moe does not produce relative relocations.

1
2
3
4
5
6

.section .meta.foo,"a",@progbits
.quad .text.foo-.    # link-time constant

# Without 'w', text relocation.
.section .meta.foo,"aw",@progbits
.quad .text.foo      # R_*_RELATIVE dynamic relocation if -pie or -shared

Another source of R_*_RELATIVE relocations are GOT entries. See All about Global Offset Table.

1
2
3
4
5
6

if (preemptible)
  emit an R_*_GLOB_DAT  
else if (!pic || is_shn_abs)
  link-time constant  
else
  emit a relative relocation  

The linker can produce an R_*_RELATIVE relocation in some other circumstances, but they are rare, e.g. the unfortunate R_386_GOT32X/R_386_TLS_IE, PowerPC64's position-independent long branch thunks.

Some architectures have R_*_RELATIVE variants. On x86-32 (ILP32), R_X86_64_RELATIVE applies to a word32 location while R_X86_64_RELATIVE64 applies to a word64 location. Itanium seems to have multiple relative relocation types for different endianness.

Representation

ELF has two relocation formats, REL and RELA. 64-bit capability and RELA are improvements on previous formats used by a.out and COFF.

1
2
3
4
5
6
7
8
9
10

typedef struct {
  Elf64_Addr    r_offset;   
  Elf64_Xword   r_info;	    
} Elf64_Rel;

typedef struct {
  Elf64_Addr    r_offset;   
  Elf64_Xword   r_info;	    
  Elf64_Sxword  r_addend;   
} Elf64_Rela;

RELA is nice for static relocations on RISC architectures but is very size inefficient for dynamic relocations. REL is 33% more efficient but is still bloated when encoding relative relocations. For a relative relocation, the symbol index is 0, but we have to pay a word for r_info.

The dynamic loader performs *(Elf_Addr*)(base+r_offset) += base + addend;. For the REL format (used by arm and x86-32), addend is an implicit addend read from the to-be-relocated location. For the RELA format (used by most architectures), addend is r_addend stored in the relocation record.

Relative relocations have great locality. On a 64-bit platform, consecutive 8-byte locations are typically all relocated, e.g.

1
2
3
4

{r_offset = 0x2000, r_info = (R_X86_64_RELATIVE << 32) | 0},
{r_offset = 0x2008, r_info = (R_X86_64_RELATIVE << 32) | 0},
{r_offset = 0x2010, r_info = (R_X86_64_RELATIVE << 32) | 0},
{r_offset = 0x2018, r_info = (R_X86_64_RELATIVE << 32) | 0},

Sources of relative relocations

Before we jump into compressing relative relocations, let's think of the sources of relative relocations and whether we can decrease their number.

In a position-independent executable, R_*_RELATIVE relocations typically dominate: they easily take 90% of the total dynamic relocations. The ratio is larger if there are fewer R_*_JUMP_SLOT relocations. For a mostly statically linked position-independent executable, the ratio can be as large as 99%.

A symbolic shared object has a similar distribution of dynamic relocations. But non-symbolic shared objects are much more common and R_*_RELATIVE relocations usually take a very small portion of their dynamic relocations. (See ELF interposition and -Bsymbolic about symbol interposition.)

1
2
3
4
5
6
7
8

void *ptr = &foo;


static void *ptr = &foo;


const char *str[] = {"a", "b"};

For string literal arrays, if setting a capacity wastes more space (const char a[][CAP] = {"a", "b", ...};), then there is no elegant way in C. If you are not concerned of making the code less readable, you can leverage the trick from musl's strerror implementation:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

E(0,            "No error information")

E(EILSEQ,       "Illegal byte sequence")
E(EDOM,         "Domain error")


#include <errno.h>
#include <stddef.h>

static const struct errmsgstr_t {
#define E(n, s) char str##n[sizeof(s)];
#include "__strerror.h"
#undef E
} errmsgstr = {
#define E(n, s) s,
#include "__strerror.h"
#undef E
};

static const unsigned short errmsgidx[] = {
#define E(n, s) [n] = offsetof(struct errmsgstr_t, str##n),
#include "__strerror.h"
#undef E
};

const char *foo(int i) { return (const char *)&errmsgstr + errmsgidx[i]; }

For C++, virtual tables can contribute many R_*_RELATIVE relocations through function pointers. Fuchsia folks contributed -fexperimental-relative-c++-abi-vtables to Clang which is also available on Linux. (underneath i64 sub (lhs, rhs) in a LLVM IR constant expression uses a PC-relative relocation.) This can make a large portion of the memory image read-only and save a lot of space (32-bit PC-relative offsets instead of 64-bit absolute addresses), but is difficult to deploy in practice because of the ABI change.

For some modern architectures (AArch64, RISC-V, x86-64), PIC does not have a size penalty on text sections compared to non-PIC. The number of R_*_RELATIVE relocations is the most significant source of code size bloat when changing from non-PIC to PIC.

I believe that for many applications relative relocations can be decreased but that may come with costs to readability or ABI issues. Sometimes you can't have it both ways.

Compressing REL/RELA relocations

One intuive idea is to omit r_type. We will need a new section but the size has been cut in half compared to REL.

1
2
3
4
5

.section naive,"a"
  .quad 0x2000
  .quad 0x2008
  .quad 0x2010
  .quad 0x2018

Next, we can think of delta encoding and narrower entries. But note that ELF tries to avoid unaligned/packed structures. In addition, delta encoding, if not designed carefully, can make medium/large code models hard.

For a new format, the minimum is linker support and dynamic loader support. Debuggers and binary manipulation tools may need to understand the format as well.

Over the years, there have been multiple attempts compressing the ELF relocation formats.

In 2010, Mike Hommey added "elfhack" to Firefox (https://bugzilla.mozilla.org/show_bug.cgi?id=606145). Improving libxul startup I/O by hacking the ELF format is a write-up. It appeared to move most relative relocations from .rel.dyn/.rela.dyn into a custom section. The section basically has multiple pairs of a base offset and a count of subsequent consecutive relocations. The savings are quite significant.

In 2015, Android bionic got DT_ANDROID_REL/DT_ANDROID_RELA. This is somewhat over-engineered but does not optimize relative relocations well.

In 2017, Cary Coutant proposed a prototype of the RELR relative relocation format https://sourceware.org/legacy-ml/gnu-gabi/2017-q2/msg00003.html. Rahul Chaudhry started a thread on the generic-abi forum: Proposal for a new section type SHT_RELR. Ali Bahrami refined it to the format we have today: an even entry indicates an address while an odd entry indicates a bitmap. It is a very simple format but with a significant saving. Read on for the format. RELR has been accepted by multiple parties. Unfortunately, generic-abi had been unmaintained since around 2016, so the changes could not be applied.

In 2018, Rahul Chaudhry added LLD/llvm-readelf support for RELR.

In 2019, I fixed an LLD bug which could cause the size of .relr.dyn to oscillate between 2 numbers.

In November 2021, I added dumping support to GNU readelf.

RELR relative relocation format

This is currently a generic-abi pre-standard. We have Cary Coutant's oral agreement that after he converts generic-abi to Markdown and makes it open, RELR will be applied.

From Proposal for a new section type SHT_RELR

Description

SHT_RELR: The section holds an array of relocation entries, used to encode relative relocations that do not require explicit addends or other information. Array elements are of type Elf32_Relr for ELFCLASS32 objects, and Elf64_Relr for ELFCLASS64 objects. SHT_RELR sections are for dynamic linking, and may only appear in object files of type ET_EXEC or ET_DYN. An object file may have multiple relocation sections. See ``Relocation'' below for details.

[...]

The format is best described by code. When --pack-dyn-relocs=relr is specified (the feature is enabled), LLD creates .relr.dyn (of type SHT_RELR) which holds an array of relocation entries, used to encode relative relocations that do not require explicit addends. Regular R_*_RELATIVE from .rel.dyn/.rela.dyn are removed.

In the .relr.dyn section,

• An even entry indicates a location which needs a relocation and sets up where for subsequent odd entries.
• An odd entry indicates a bitmap encoding up to 63 locations following where.
• Odd entries can be chained.

1
2
3
4
5
6
7
8
9
10
11
12
13

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;
  }
}

RELR can typically encode the same information in .rela.dyn in less than 3% space.

1
2
3
4

q() { file $1 | grep -q ELF || return; local s=$(stat -c %s $1); printf "$1\t$s\t"; bc <<< "scale=2; $(readelf -Wr $1 | grep -c _RELATIVE)*24 * 100 / $s" | sed 's/^\./0./' }

for i in /usr/bin/*(.x); do q $i; done > /tmp/0
awk '{c+=$2*$3/100; s+=$2} END {print s, " ", c/s}' /tmp/0

On my Arch Linux, among /usr/bin/* executables, relative relocations take 7.9% of the total file size. These large executables spend 10+% in the .rela.dyn section: as, audacity, fzf, ndisarm, objdump, ocaml*, perf_*, qemu-system-*, pdftosrc, php*, strace, virt-*. Among /usr/lib/lib*.so* shared objects, relative relocations take 4.92% of the total file size.

I get similar savings on my Debian Linux.

Application

Android, Chrome OS, and Fuchsia have used ld.lld --pack-dyn-relocs=relr and a DT_RELR capable loader for quite a while now.

Chrome OS uses glibc and appears to only patch binutils-gdb and glibc. No user application needs to adapt to the new format!

This probably gives *BSD and Linux distributions a signal: this feature is rather easy to ship:)

FreeBSD

I added DT_RELR support to libexec/rtld-elf in https://reviews.freebsd.org/D32524. Thanks to [email protected] for review/commit and making it available to the future 13.1 release!

FreeBSD uses LLD by default for most ports. Someone needs to test switching to default -Wl,--pack-dyn-relocs=relr.

musl

There is an unapplied patch https://www.openwall.com/lists/musl/2019/03/06/3. The BDFL says it is a nice improvement but not a critical change blocking anything, so the fate of the feature is still unclear.

glibc

I submitted [PATCH v2] elf: Support DT_RELR relative relocation format [BZ #27924] in October 2021. The good news is that it got some discussion and people agree that it is useful. The bad news is that due to complicated factors it is unclear when the patch can be merged.

Lack of binutils support

• GNU ld does not support --pack-dyn-relocs=relr. I wish someone can work on this.
• readelf and objdump cannot dump relocation sections.
• objcopy reports an error when operating on a DT_RELR object.
• gold does not support synthesizing the .relr.dyn section. ChromeOS folks maintain a patch. I have a rewritten patch (https://sourceware.org/bugzilla/show_bug.cgi?id=28601)

How to test?

[PATCH v2] elf: Support DT_RELR relative relocation format [BZ #27924] includes a test.

LLD 13 can link glibc and pass all testsuite for aarch64 and x86-64 now. This streghtens the argument that glibc should support DT_RELR. However, LLD is not in the build configurations of scripts/build-many-glibcs.py which is more commonly used by maintainers.

glibc ld.so has some severe architectural problems. I find that linking ld.so itself with --pack-dyn-relocs=relr may make symbol lookup fail because ld.so itself's relative relocations may be doubly applied. DT_REL/DT_RELA are doubly applied as well, but some complex if guards prevent serious issues.

I hacked /usr/local/bin/ld to use --pack-dyn-relocs=relr if the output name has tst-|test- (typical glibc test files).

1
2
3
4
5
6
7
8
9
10
11
12
13

#!/bin/zsh
output=
prev_arg=
for arg in "[email protected]"; do
  [[ $prev_arg == -o ]] && output=$arg
  prev_arg=$arg
done

if [[ $output =~ 'tst-|test-' ]]; then
  exec ~/Stable/bin/ld.lld --pack-dyn-relocs=relr "[email protected]"
else
  exec ~/Stable/bin/ld.lld "[email protected]"
fi

There are just 7 more failures.

1
2
3
4
5
6
7
8

% comm -3 <(grep '^FAIL' tests.sum | sort) <(grep '^FAIL' ../lld0/tests.sum | sort)
FAIL: nptl/test-condattr-printers
FAIL: nptl/test-cond-printers
FAIL: nptl/test-mutexattr-printers
FAIL: nptl/test-mutex-printers
FAIL: nptl/test-rwlockattr-printers
FAIL: nptl/test-rwlock-printers
FAIL: nptl/tst-pthread-gdb-attach-static

Time travel compatibility

Programs with new features run the risk of mysterious crashes or malfunction on old systems. Ali Bahrami calls new objects on old systems "time travel compatibility". For Solaris: "And yet, our experience is that although we don't go to great effort to catch time traveling objects, they very rarely cause problems for us. People seem to understand that they can't do that."

For DT_RELR objects, they will immediately segfault on an old glibc. For some groups (ChromeOS, FreeBSD, Fuchsia, NetBSD, and Solaris), they just don't support "time travel compatibility" development model and can accept that new objects may have poor diagnostics.

However, some folks within the glibc community are overly cautious about a nice diagnostic. Such "time travel compatibility" mechanism is not consistently applied. See When to prevent execution of new binaries with old glibc for a summary.

My idea is that such a diagnostic should not be a blocker for the DT_RELR feature.

• We don't flip the default for GCC/Clang.
• GNU ld doesn't support RELR yet. For most Linux distributions, there is no impact to their packages.
• The users who opt in the feature accept the poor diagnostic if they back port that to older systems.
• If we merge the glibc patch early, we will make the future flip less of a problem.

I wish that the glibc community can listen to what Ali suggested in the generic-abi post (January 2018):

My free advice (worth what you paid for it) is to roll out the support, and then wait a bit before turning on the use widely, so that the support is in place before it is needed, and to not complicate things with a way to catch time travelers. The window of time where this can be a problem is finite, and once you're past it, you'll be glad to have a simpler system.

This advice applies to many things, including a GCC 5 regression for x86-64 -fpie I am trying to fix (but still pending) [PATCH] x86-64: Remove HAVE_LD_PIE_COPYRELOC and copy relocations on protected data.

Anyway, since there is interest on time travel compatibility, let's discuss potential solutions.

EI_ABIVERSION

Some might ask whether we could use EI_ABIVERSION.

The System V ABI says:

Byte e_ident[EI_ABIVERSION] identifies the version of the ABI to which the object is targeted. This field is used to distinguish among incompatible versions of an ABI. The interpretation of this version number is dependent on the ABI identified by the EI_OSABI field. If no values are specified for the EI_OSABI field by the processor supplement or no version values are specified for the ABI determined by a particular value of the EI_OSABI byte, the value 0 shall be used for the EI_ABIVERSION byte; it indicates unspecified.

EI_ABIVERSION is dependent on EI_OSABI. Operating systems decide their EI_ABIVERSION. We need to discuss ELFOSABI_NONE/ELFOSABI_GNU separately.

For ELFOSABI_GNU (alias: ELFOSABI_LINUX), different architectures may have different EI_ABIVERSION values. I know that mips may use EI_ABIVERSION==1 for (e_eflags & (EF_MIPS_PIC | EF_MIPS_CPIC)) == EF_MIPS_CPIC position-dependent executables. For glibc, we would need to bump LIBC_ABI_MAX.

ELFOSABI_NONE is the domain of the generic ABI. Many Linux executables don't use STB_GNU_UNIQUE/STT_GNU_IFUNC and therefore use ELFOSABI_NONE. Solaris folks have ruled out the possibility to bump EI_OSABIVERSION because this is not a development model they need. I think Android bionic/Chrome OS/FreeBSD fall in the same boat.

Even if EI_ABIVERSION could be bumped: as of glibc 2.34, ld.so does not check EI_ABIVERSION for kernel mapped objects. It does check ld.so mapped objects (including all DT_NEEDED shared objects), though.

1
2
3
4

% r2 -nwqc 'wx 01 @ 8' a  
% ./a
% /lib/x86_64-linux-gnu/ld-linux-x86-64.so.2 ./a
./a: error while loading shared libraries: ./a: ELF file ABI version invalid

For ELFOSABI_GNU (r2 -nwqc 'wx 03 @ 7'), changing EI_ABIVERSION to 4 or above will observe the failure with ld.so mapped objects but not kernel mapped objects.

In addition, bumping the ABI version can immediately lock out some ELF utilities which only deal with e_ident[EI_ABIVERSION] == 0 objects. For example, elflint from elfutils reports an error.

Synthesized undefined dynamic symbol

We could let the linker synthesizes an undefined symbol in the dynamic symbol table (.dynsym) to indicate the usage of DT_RELR, then let ld.so define the symbol to indicate feature availability. (See the _dl_have_relr idea by Michael Matz.)

In glibc, an unreferenced unversioned undefined dynamic symbol does not trigger an undefined symbol error, so the linker would need to synthesize a fake relocation. R_*_NONE is typically ignored so we would need a relocation which does something, e.g. R_X86_64_64. Then the linker has to synthesize a .data.rel.ro section to accommodate the relocation.

As an alternative, the linker can make the undefined dynamic symbol versioned, then a diagnostic will be reported even if the symbol is unreferenced. A versioned undefined symbol can lead to a link-time error even for -z undefs (unfortunate default for ld -shared).

If GNU ld adds, say, --pack-dyn-relocs=relr-glibc or -z relr-glibc, with the functionality, I will probably just add a compatibility alias to LLD but not actually add the symbol (https://sourceware.org/pipermail/libc-alpha/2021-October/132460.html):

• Some users don't need "time travel compatibility".
• --pack-dyn-relocs=relr is quite popular in some platforms now. --pack-dyn-relocs=relr would still be usable to bypass the relr-glibc restriction on glibc.
• I don't want users to migrate away from --pack-dyn-relocs=relr (churn) just because glibc has a different development model.

Symbol versioning

glibc 2.34 added [email protected]@GLIBC_2.34.

A *crt1.o file references __libc_start_main. A new program linking against new libc.so cannot run on glibc older than 2.34.

*crt1.o is for executables, but a similar trick can be used in crti.o or crtbegin*.o to catch both executables and shared objects.

This mechanism is coarse in that it does not check whether DT_RELR is used.

The DT_CRITICAL_* proposal

See Critical program headers and dynamic tags.

Solaris does not support the development model, so this proposal will unlikely enter generic ABI.

AFAIK this is not in the GNU ABI and glibc does not support this feature. It is not suitable to do time travel compatibility with this proposal.

Since several groups (FreeBSD/Fuchsia/ChromeOS) don't find bumping EI_ABIVERSION necessary, ld.lld --pack-dyn-relocs=relr should remain its current semantics.

glibc 2.35 will be released around 2022-02-01. I hope that DT_RELR can catch the release, but currently there is significant risk for that goal. See Can DT_RELR catch up glibc 2.35?

glibc consumes objects rather than produces objects. It doesn't decide the default. We don't switch GCC/binutils default. The final word should be in the platform providers' hands. They decide whether they accept a silent segfault.

When will Linux distributions adopt RELR?

I have filed tickets for several large Linux distributions to bring the size saving to their attention. I also wish that distributions' support/petition can move the glibc patch forward.

• Arch Linux: https://bugs.archlinux.org/task/72433
• Debian: https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=996598
• Fedora: https://bugzilla.redhat.com/show_bug.cgi?id=2014699
• Gentoo: https://bugs.gentoo.org/818376

Mach-O

Mach-O __LINKEDIT,__rebase serves a similar purpose as ELF R_*_RELATIVE relocations`. It uses a bytecode encoding to decrease space consumption. The bytecode schemes uses run-length encoding and encodes the delta between two offsets to save bytes on encoding the offset. Empirically I think it is inferior to ELF RELR in the majority of cases.