Relocation Entries and the Arithmetic a Linker Performs

A compiled object file cannot know where its functions and variables will end up. The instruction call printf must be encoded as a relative branch to a 32-bit displacement, but at assembly time the distance is unknown: it depends on where the linker places the call site and where the library’s printf lands in the process image. Rather than leave the instruction in a guessed state, the assembler emits a placeholder and records, alongside it, enough information for the linker to compute the missing value later. That record is a relocation entry, and the entire static and dynamic linking process is largely the application of these patches.

The format is more subtle than “fill in the address”, because the required value differs per instruction encoding and per target. A relative branch needs the difference between two addresses. An absolute 64-bit immediate needs an address. A GOT-relative access needs an offset into a table. Each case has its own relocation type, its own arithmetic, and its own range limit, and the type numbers are part of the ABI rather than the generic ELF specification.

What one entry contains

An ELF64 relocation entry in RELA form is 24 bytes: r_offset, r_info, and r_addend. The r_offset field gives the location to patch, interpreted as a section offset in a relocatable object and as a virtual address in a linked shared object or executable. r_info packs two values into one 64-bit word: the symbol table index in the upper 32 bits and the relocation type in the lower 32 bits. The ABI provides macros such as ELF64_R_SYM and ELF64_R_TYPE to extract them, and code that shifts by the wrong amount silently produces wrong results on every entry.

The r_addend field is a signed value that participates in the computation. In REL form, used by 32-bit x86 and a few other targets, the entry has no addend field and is 8 bytes on a 32-bit object or 16 on a 64-bit one: the addend is read from the bytes at the patch location itself. RELA entries are 12 bytes on a 32-bit object and 24 on a 64-bit one. Both encodings express the same arithmetic; they differ in where the constant lives. RELA was introduced because a separate addend field allows the patch site to be written with any value, which matters when the linker must also inspect the original bytes, and because an in-place addend cannot express the full range of a 64-bit computation when the patch site is only 32 bits wide.

The symbol index is meaningful only for relocations that reference a symbol. Some types are self-contained: R_X86_64_RELATIVE carries no symbol, and its symbol index is zero. A reader that indexes the symbol table unconditionally for every entry will fail on these, which is a common defect in hand-written ELF readers.

The arithmetic, type by type

Nearly every relocation reduces to a formula over four quantities: S, the address of the symbol; A, the addend; P, the address of the patch location; and B, the base address at which the containing object was loaded. The result is written to the patch location, truncated to the width the type specifies.

R_X86_64_64 computes S + A and writes a full 64-bit absolute value. R_X86_64_PC32 computes S + A - P, a signed 32-bit displacement relative to the patch site, which is what a direct call or jmp to an external function needs. R_X86_64_PLT32 computes the same value but directs the linker to route the reference through the procedure linkage table entry for the symbol rather than to the symbol’s own address. R_X86_64_GOTPCREL computes G + GOT + A - P, where G is the offset of the symbol’s entry in the global offset table, producing a displacement that reaches the GOT from the patch site.

R_X86_64_RELATIVE computes B + A. It has no symbol because the addend already holds the link-time address of the target relative to the object’s own base. When a position-independent executable is loaded at a base other than zero, every absolute address it contains must be rebased, and the relocations of this type are exactly the list of places to add the load bias to. This is why R_X86_64_RELATIVE entries dominate the relocation count of a PIE and why they are the expensive part of loading one.

A worked case makes the arithmetic concrete. Suppose a shared object is linked with .text at virtual address 0x1000 and .data at 0x3000, and .data holds a pointer to a function at 0x1150. The linker emits an R_X86_64_RELATIVE relocation at offset 0x3000 with addend 0x1150. If the object is loaded at base 0x7f0000000000, the value written is 0x7f0000001150. The file never contains the final address; it contains the offset that the loader rebases.

/* Apply a table of RELA entries to an image mapped at `base`. Only the
   base-relative type is handled; the rest are reported as unhandled. */
#include <stdint.h>

struct rela { uint64_t offset, info; int64_t addend; };

/* Returns the number of entries applied, or -1 on an unknown type. */
int apply_rela(const struct rela *rela, uint64_t count,
               uint8_t *image, uint64_t image_size, uint64_t base) {
    for (uint64_t i = 0; i < count; i++) {
        uint32_t type = (uint32_t)(rela[i].info & 0xffffffffu);
        uint64_t at = rela[i].offset;
        if (type != 8)                  /* R_X86_64_RELATIVE */
            return -1;
        if (at > image_size || image_size - at < 8)
            return -1;                  /* patch site outside the image */
        uint64_t value = base + (uint64_t)rela[i].addend;
        for (unsigned b = 0; b < 8; b++)    /* little-endian store */
            image[at + b] = (uint8_t)(value >> (8 * b));
    }
    return (int)count;
}

The two bounds checks are not incidental. r_offset comes from the file, and an offset pointing outside the mapped image is the simplest way to make a loader write into unrelated memory. The byte-wise store avoids assuming that the patch site is aligned for a uint64_t, which the format does not guarantee for every relocation type.

Range limits and why they are checked

Each relocation type has a width, and the linker must verify that the computed value fits. R_X86_64_PC32 writes 32 signed bits, so the distance from the patch site to the target must fall in the range that a signed 32-bit value can express: roughly ±2 GiB. A program whose text and data are separated by more than that cannot use direct PC-relative calls to symbols in the far region, and the linker reports the failure as a relocation overflow naming the symbol and the type.

This limit is why large binaries use the “code model” distinction. The small model assumes all code and data fit within 2 GiB of each other and uses 32-bit PC-relative references throughout. The medium model places code anywhere but assumes data stays within 2 GiB, using 64-bit absolute addressing for code and 32-bit relative for data. The large model assumes nothing and uses the longest encodings everywhere, at a cost in code size and instruction cache pressure. The compiler selects a model at build time, and a mismatch between the model and the actual layout produces overflow errors at link time rather than wrong addresses at run time, which is the safer failure.

Absolute relocations have a related constraint under position independence. An R_X86_64_32 or R_X86_64_32S writes a 32-bit absolute address, which cannot be correct if the object can be loaded above 4 GiB. Building a shared object or a PIE from code containing such a relocation is an error, and the diagnostic names the relocation rather than the source construct that caused it. This is the mechanism behind the familiar instruction to compile with position-independent code enabled when producing a shared library, and the consequences for the file’s relocation count are set out in Position-Independent Executables and the Cost of PC-relative Addressing.

Static relocations, dynamic relocations, and who applies them

A relocatable object’s relocations are resolved at link time by the static linker, which knows the final addresses of everything it places. Sections named .rela.text, .rela.data, and so on hold them, and each such section names its target through sh_info and its symbol table through sh_link.

An executable or shared object contains a much smaller set of relocations that could not be resolved at link time: references to symbols defined in other shared objects, references to symbols that may be interposed at run time, and the base-relative fixups a position-independent image needs. These live in .rela.dyn and .rela.plt, both reachable through the DT_RELA, DT_RELASZ, DT_JMPREL, and DT_PLTRELSZ entries of the dynamic section. The split is meaningful: .rela.plt entries correspond to the jump slots that the lazy binding mechanism patches, described in The PLT and GOT Protocol That Defers Symbol Resolution, and the loader treats them differently from the rest.

The count of dynamic relocations is a rough proxy for load cost. A shared object built without position independence, or one that takes the address of many global variables, carries a large .rela.dyn. The same code compiled with hidden visibility for internal symbols and PC-relative addressing throughout can reduce the dynamic relocation set to nearly the GOT entries alone, because internal references then need no run-time fixup.

Copy relocations and the odd case they create

One relocation type deserves separate mention because it breaks the clean model. When an executable references a data object defined in a shared library, the compiler cannot know the object’s size at compile time, so it cannot reserve space for a direct reference. The traditional solution is a copy relocation: the linker allocates space in the executable’s .bss, records the size and alignment from the shared library’s symbol, and emits a relocation that instructs the dynamic linker to copy the initial contents into that space at startup. The symbol is then defined in the executable and the library’s own references are bound to the executable’s copy.

Copy relocations make the executable’s data section grow and force the library to redirect its internal references through the GOT. They also mean the executable and the library must agree on the object’s size; a library upgrade that enlarges a copied object produces a mismatch that the dynamic linker may detect through a symbol size check or may not. Modern toolchains avoid the situation by compiling with position-independent code and accessing such objects through the GOT, which is why copy relocations are increasingly rare in newly built executables and still common in older ones.

What a relocation table cannot tell you

A relocation says where to patch and what to compute, not why. The same R_X86_64_PC32 entry can come from a function call, an access to a static variable, or a reference to a string literal. Reconstructing intent requires the disassembly, and reconstructing the original source requires debug information. Tools that present relocations as a list of symbols are therefore presenting a projection: they show the target, not the operation.

The table is also incomplete in the other direction. Relocations that the linker resolved at link time were applied and then, in a fully linked executable, their entries discarded. The bytes at the call sites hold final displacements with no record of how they were computed. Only the unresolved remainder survives into the file, and its size is a measure of what the loader still has to do rather than a measure of how much linking happened.