Everything in the previous three modules was reading. This one writes, and the whole point is that a relocation applier is not a large program. Three numbers and an arithmetic rule, plus enough ELF to find the fields:
And the specimen is chosen so the answer is checkable. This is the constraint that makes the exercise possible, and it is worth stating before the code, because getting it wrong is the reason most attempts at this fail silently:
$ cat closed.c
volatile int table[4] = {10, 20, 30, 40};
__attribute__((noinline)) int pick(int i){ return table[i & 3]; }
int sum4(int i){ return pick(i) + table[(i + 1) & 3]; }
$ clang -O1 -fno-pic -fno-pie -c closed.c -o closed.o
$ llvm-nm-21 -u closed.o
$ <-- EMPTY. The object is closed.
Every symbol it references is defined in it. That is what makes “apply the relocations” a question with a right answer instead of a question about a layout the applier was never told. Every other specimen in this course’s sample directory references externs, which makes them good for measuring and useless for building.
Two annotations in that file are load-bearing, and both were found by measuring:
volatile: at -O1 without it, the whole file
collapses to a single 16-byte constant
load from .rodata.cst16. nothing left
to relocate.
noinline: without it `pick` is inlined, the call
disappears, and with it the only
PC-RELATIVE relocation in the file.
The exercise needs one relocation of each rule, and without both annotations there is only one. That is not a C detail; it is a measurement lesson in disguise, and it is the same trap the TLS concept fell into with -O1.
What the applier has to hold in its head, and it is shorter than you expect.
That trap is the one to spend time on. For an ET_REL object, st_value is an offset within its section, because the section has no address until layout. So S must become section_address + st_value before it can be compared with P. Every tutorial on relocations gets this right and nobody ever says why it matters, because the example always has the symbol in the first section and the base at zero.
Choose a base that is not zero, and the difference becomes impossible to miss — which is what the exercise does.
The three relocations, and the arithmetic for each, with every number shown:
$ llvm-objdump-21 -r closed.o | sed -n '/.text/,/^$/p' 0000000000000006 R_X86_64_32S table 0000000000000014 R_X86_64_PLT32 pick-0x4 0000000000000020 R_X86_64_32S table $ python3 apply_relocs.py closed.o e_type=1 3 relocations in .rela.text base = 0x400000 0x0006 R_X86_64_32S table S=0x00000000 A=+0 -> value=0x4000f0 0x0014 R_X86_64_PLT32 pick S=0x00000000 A=-4 -> value=-0x18 0x0020 R_X86_64_32S table S=0x00000000 A=+0 -> value=0x4000f0 all 3 relocations applied; 38 bytes of .text
Work the middle one by hand, because it is the only one with non-obvious arithmetic:
That last check is the whole exercise in one line. You do not need to trust the applier; you can read the bytes and see where they point. A tool you can verify by hand is a tool you can extend, and the ability to do that check is the difference between having written a linker and having called one.
Now the off-by-one that makes this a real trap rather than a formality. The callq opcode is at 0x13. The relocation field is at 0x14. They are different addresses, one byte apart, because the opcode byte comes first:
$ llvm-objdump-21 -d --no-show-raw-insn closed.o | sed -n '/<sum4>/,/ret/p' 0000000000000010 <sum4>: 10: pushq %rbx 11: movl %edi, %ebx 13: callq 0x18 <sum4+0x8> <-- the INSTRUCTION is at 0x13 18: incl %ebx 1a: andl $0x3, %ebx 1d: addl (,%rdi,4), %eax 24: popq %rbx 25: retq $ python3 crosscheck.py -v | grep 'the callq opcode' ok the callq opcode is at 0x13, one byte before its field 'e8'
Use the instruction’s address for P and every PC-relative relocation in the file is off by one. The result is a call into the middle of the incl %ebx at 0x18, which is a perfectly valid instruction, in a perfectly valid program, that computes something else. It assembles. It links. It runs. It is wrong — and nothing anywhere reports it.
And the absolute ones, for contrast, are the easy case and the reason this is a fair exercise:
R_X86_64_32S at 0x06, symbol `table`, A = 0
S = 0x4000f0 .data was placed here by the layout
P = 0x400006
A = 0
value = S + A (no subtraction: ABSOLUTE)
= 0x4000f0
the bytes become f0 00 40 00, and the instruction
reads them as the base of a scaled index:
movl 0x4000f0(,%rax,4), %eax
which is table[rax]. correct.
The second thing the applier does, and it is the behaviour that separates a patcher from a truncator. It refuses. Push the load address high enough and a 4-byte field cannot hold the answer:
$ python3 apply_relocs.py --all-bases
sweeping the load base until a 4-byte field stops fitting
(64MB steps, 0..4GB)...
base=0x0040000000 ok
base=0x0080000000 OVERFLOW: offset 0x6: R_X86_64_32S overflow:
2147483888 does not fit in 32 signed bits
(P=0x80000086, S=0x800000f0, A=0, ADDRESS)
first failure at base=0x80000000 (== 2^31 exactly)
the last base that worked was 0x7c000000
Exactly 231, and the breaker is the absolute relocation. That is the finding, and it is the direct payoff of the randomisation concept: translate the image and a distance is unchanged, so the PLT32 kept working at every base in the sweep. The absolute form stores an address, and an address stops fitting in 32 bits once the base passes 231. This is why the vocabulary has a PC-relative form at all, demonstrated by watching the other one break.
And that maps exactly onto the two relocation types the third concept paired off:
What the applier deliberately does not do, and the list is the interesting part:
IT DOES NOT WHY
apply TLSGD / TLSLD there is no arithmetic. the value
is a function result. see the
TLS concept.
handle GOT-relative forms they need a GOT, and deciding
what goes in the GOT is layout,
not patching.
invent a jump stub an out-of-range call needs MORE
INSTRUCTIONS, not a wider field.
lay out sections it accepts a layout. deciding the
layout is a different program with
a much harder problem.
THAT DIVISION IS THE POINT. "apply the relocations that are
arithmetic" is a complete, shippable, testable program. "be
a linker" is not. Most of the difficulty of real linkers is
on the other side of this line.
$ cd courses/reloc/assets/samples $ ./build_samples.sh $ python3 apply_relocs.py $ python3 apply_relocs.py --show $ python3 apply_relocs.py --all-bases $ python3 crosscheck.py ALL 87 CHECKS PASS
Then extend it, in the order that builds understanding fastest:
1. BREAK IT ON PURPOSE. Change P from
base + r_offset to base + r_offset - 1 and
re-run. Then disassemble --show. Where does the call
actually land now? (It lands in the middle of an
instruction, and nothing tells you.)
2. Change the base to 0. Which relocations change their
value and which do not? (Only the absolute ones.
Prove it with two runs and diff.)
3. Add the GOT-relative case. Compile closed.c with
-fPIC instead of -fno-pic. Now you need a .got.
Decide: does it belong in this program or not?
(Defending either answer is the exercise.)
4. Add R_X86_64_PC64 and R_X86_64_64 to the table. They
are one line each. Then find a construct that emits
them -- -mcmodel=large is the obvious candidate.
5. Make the applier REFUSE to run on a reloc type it
does not know, rather than guessing. Then run it on
a TLS object and watch it decline cleanly.
Exercise 1 is the one that teaches the most, and it takes thirty seconds. You have just broken the tool in the exact way everyone breaks it, and the only symptom is that the disassembly shows a call to a different address. There is no error, no warning, no non-zero exit. That is what an off-by-one in a relocation applier looks like from the outside, and having produced one deliberately makes the lesson stick in a way that reading about it does not.
Exercise 5 is the professional version of the same instinct. Declining correctly is part of applying correctly — a tool that guesses at a relocation it does not understand will produce output, and that output will be wrong, and the wrongness will surface somewhere else entirely. The apply_relocs.py in this course’s sample directory recognises the TLS relocations by name only so that it can refuse them with a message pointing at the concept; everything else it does not recognise it refuses as “unknown type number”, which is the behaviour you want.
This closes the course, and it is the concept that makes the other eight into a single thing. One Relocation, or Two said the vocabulary follows from reach. Why There Are So Many Kinds organised the set into four groups and found the dividing line between the linker’s arithmetic and the loader’s. The Limits That Shaped the Table gave the ±2GB boundary. The Flags, Does the Executable Actually Move? and What Position Independence Costs gave PIE as a measured, quantified decision. The Relocation That Cannot Be Fixed and The One Relocation That Calls the Loader gave the two ways it fails. This concept takes three of them and writes arithmetic on them, and the arithmetic is short enough to hold in your head. That is the shape the whole chain is aiming at: nine concepts of reading, ending in one page of writing.
Three specific debts are paid off here. The P trap from the third concept — that S - P cannot be computed at compile time because P does not exist yet — is now a line of code, and the zero displacement that the Object Files course called “the hole” gets filled in front of you. The 32 against 32S policy from the same concept becomes a raise instead of a truncation. The loader’s group from the second concept becomes the list of things this program declines to do, which is a more useful form of the same knowledge than a table would have been.
The chain out of this course is the static-linker course, and this concept is what makes it approachable. The PIC violation said a linker’s error message can point back at a compile flag, and this program is the other half of that loop: it is a minimal consumer of object files that has no idea a linker exists. The next step is to add a second object, which is where “where does this symbol come from” becomes a question with an answer that depends on search order, archives, and which definition wins. That is the symbol-resolution course, and this exercise is deliberately the last thing that can be built before it — one object, one layout, no names to resolve.
And the connection that closes the course’s argument is to the Object Files course it follows. That course established that an object file is a to-do list with zeros in it, and could not say who did the list. Position Independence showed the list changing shape under -fPIC without explaining why the shapes were necessary. This course answered the why, and then wrote the thing that consumes the list. The object file is the interface; a relocation applier is the smallest honest program that honours it, and having written one, the phrase “linker magic” has a specific meaning: it is the part of apply_relocs.py that this concept deliberately did not write.