Relocation Arithmetic: Patching Machine Code at Link Time

A relocation is a small arithmetic instruction stored in the object file for the linker to execute later. It says which bytes to modify, which symbol to read, and which formula to apply. The formulas differ by architecture and by the kind of addressing the compiler chose, and each formula has a range outside of which the patch cannot be represented in the instruction’s immediate field. Most link failures that look mysterious are range failures or formula mismatches, and reading the relocation type explains both.

The general form and its four variants

Nearly every relocation in a modern ELF file computes one of four things from a symbol address S, an addend A, and the address P of the storage being patched:

• S + A, an absolute address.
• S + A - P, a displacement from the patch site.
• G + GOT + A - P, the displacement from the patch site to the global offset table entry that will hold the symbol’s address, where G is the entry’s offset within the table and GOT is the table’s own address.
• S + A - TP, an offset from the thread pointer, used for thread-local storage.

The first form cannot be used in a shared object, because S is not known until load time and the field being patched is in a read-only page that the loader would have to modify. The second form is position-independent as long as the distance between the patch site and the target is fixed at link time, which it is for references within a single output. The third and fourth forms are the ones that make shared objects and thread-local storage work.

Consider the x86-64 R_X86_64_PC32 relocation. The instruction at the patch site is typically a call or a lea with a 32-bit displacement field. The linker computes S + A - P, writes the low 32 bits into the field, and relies on the processor to sign-extend the displacement and add it to the address of the next instruction. The psABI defines P as the address of the relocation’s offset, so a compiler emitting a call must set the addend to −4 to account for the instruction length; that −4 is not a quirk but the standard way the formula is reconciled with the hardware’s use of the end of the instruction as the base.

The range is signed 32 bits, so the target must lie within about two gigabytes of the patch site. That is generous for a single executable and insufficient for a very large one, which is why large builds occasionally need the medium or large code models that use different sequences. The check that catches the overflow is the same one described in Sections, Symbols, and Relocations in an ELF Object File: the relocation record carries both the type and the symbol, so the linker can compare the computed value against the type’s field width before writing anything.

Absolute relocations and their discontents

R_X86_64_32 and R_X86_64_32S write an absolute 32-bit address, the second treating it as signed. Both are only usable when the final address is known at link time and fits, which rules out shared objects and rules out position-independent executables on most systems. A non-PIE executable can use them freely; that is the main reason non-PIE binaries were historically faster to start, since they need no relocation processing at load time beyond the ones the linker could not resolve.

R_X86_64_64 writes a full 64-bit absolute address and has no range problem, but still cannot appear in a shared object’s read-only data. It appears in writable data sections, where the dynamic linker is permitted to patch at load time, and in executables.

The 32-bit forms are also how a linker detects an address-space collision. If the linker assigns an address above 4 GiB and a R_X86_64_32 relocation refers to it, the patch would silently truncate. The linker must therefore check the value against the type’s range and emit a diagnostic rather than writing the low half. This is the origin of the message that an object was not compiled with position-independent code: the object used absolute 32-bit relocations, and the link target is a shared object or a high-address PIE where those cannot be satisfied.

Why some architectures need explicit addends

On a machine where the field to be patched is a contiguous aligned word, the linker can read the existing value as the addend, add S, and write the result back. That is the REL encoding, and it works on 32-bit x86 and on several RISC architectures.

It breaks down when the patch spans bytes that are not contiguous with the value they represent, or when the instruction encoding splits an immediate across fields. The MIPS J instruction, for instance, holds a 26-bit target field that is shifted left by two when used, and the upper bits come from the delay slot’s address; recovering the addend from the encoded instruction is possible but requires architecture-specific decoding in the linker. The PowerPC branch instruction has a 24-bit displacement field that is sign-extended and concatenated, so the stored bits are not the addend either.

The RELA encoding sidesteps all of this by carrying the addend in the relocation record. The linker never reads the patch site, so the encoding of the instruction is irrelevant: it computes the value and stores it with whatever bit manipulation the relocation type specifies. x86-64, ARM64, and RISC-V use RELA; i386 and ARM32 use REL. The cost is eight extra bytes per relocation, which for a large program is measurable but small compared with the code itself.

/* Apply a few common x86-64 relocations to a section image in memory. */
#include <stdint.h>
#include <string.h>

struct reloc { uint64_t offset; uint32_t sym; uint32_t type; int64_t addend; };

static void patch32(uint8_t *img, uint64_t off, uint32_t v) { memcpy(img + off, &v, 4); }

/* symaddr[] holds final symbol addresses; base is where the section will live,
   so P = base + offset.  Returns nonzero if a value does not fit its field. */
int apply(const struct reloc *r, size_t n, uint8_t *img,
          const uint64_t *symaddr, uint64_t base) {
    for (size_t i = 0; i < n; i++) {
        uint64_t S = symaddr[r[i].sym];
        uint64_t P = base + r[i].offset;
        uint64_t v = S + (uint64_t)r[i].addend;

        switch (r[i].type) {
        case 1:  /* R_X86_64_64: absolute 64-bit */
            memcpy(img + r[i].offset, &v, 8);
            break;
        case 2:  /* R_X86_64_PC32: signed 32-bit displacement */
            v -= P;
            if ((int64_t)v < INT32_MIN || (int64_t)v > INT32_MAX) return 1;
            patch32(img, r[i].offset, (uint32_t)(int32_t)v);
            break;
        case 10: /* R_X86_64_32: unsigned 32-bit absolute */
            if (v > UINT32_MAX) return 1;
            patch32(img, r[i].offset, (uint32_t)v);
            break;
        default:
            return 2;                     /* type not handled */
        }
    }
    return 0;
}

The range checks in that sketch are the part that matters. A linker that writes the truncated value and continues produces a binary that crashes at an address unrelated to the offending reference, which is the hardest kind of bug to trace back to a link-time cause.

The GOT and TLS forms

R_X86_64_GOTPCREL is the third form: it computes the displacement from the patch site to the symbol’s global offset table entry. The instruction patched is a load from memory, so the result is the displacement from the instruction to a pointer that the dynamic linker will fill with the symbol’s address. The relocation is resolved at static link time — the offset of the GOT entry within the GOT is known then — but the contents of that entry are not.

Thread-local storage adds a second indirection. A TPOFF relocation yields a signed offset from the thread pointer to the variable, which is what the local-exec and initial-exec sequences consume. It is resolved at load time for a shared object, because the offset depends on where the loader placed the module’s TLS block among all the others. The details, including the four TLS models that trade relocations against runtime lookup, are covered in Thread-Local Storage Access Models.

Sizing and overflow as a design constraint

The choice of relocation type is made by the compiler, not the linker, and it is constrained by the code model the compiler was told to target. The default small model assumes code and data fit in the low 2 GiB, permitting PC32 and 32S. The medium model allows data anywhere by loading addresses with 64-bit immediates, at the cost of longer instruction sequences. The large model allows code anywhere too, using register-indirect calls.

Each step up costs instruction bytes and instruction cache pressure. A program that would fit the small model but is compiled with the large model pays for longer instruction sequences with no benefit; a program that exceeds the small model and is compiled with it fails to link with range errors. Build systems that hard-code the default are therefore betting on the size of the final binary, and the bet is invisible until it fails.

Overflow can also occur for a reason unrelated to size: a section placed at an address chosen by the linker’s script may sit far from the code that references it. A linker script that puts a data section in a high memory region while code stays low breaks every PC32 reference between them. The diagnostic names the relocation and the symbol, which is enough to identify the placement decision responsible.

Alignment, padding, and the patched bytes

Relocation offsets are relative to the section, and the linker must apply them after final section placement, when both P and every S are known. That means the patched image exists in the linker’s memory or in an output file, never as a partially patched object on disk. Static executables therefore contain no relocation records for the patches the linker applied; the records were consumed. Only relocations the linker could not resolve — those against symbols in shared objects, or those deferred by design — survive into the output, in sections the dynamic linker reads.

One consequence is that a linked executable’s .text is final. It contains absolute or relative values baked in for one specific load address. Re-linking is the only way to change them, and a position-independent executable keeps this property only by having the dynamic linker apply the remaining relocations to a writable copy of the pages before making them read-only. That two-phase permission change is a visible cost of PIE, and it is the reason the loader’s work is larger for PIE than for a fixed-address executable.