Linking, relocations and PIE in depth

An assembler that reads lea rsi, [msg] cannot know where msg will be loaded, so it writes four zero bytes into the instruction and a relocationrelocation: An entry beside a section's bytes that says which bytes the linker must patch, with which symbol's address, under which formula. Needed whenever the assembler cannot know a final address yet. More in “From source to executable: objects and linking” beside them: a record that names those bytes, a symbol and a formula for the linker to apply. Linking, relocations and PIE in depth come down to one question: which program writes each address into those bytes, and when?

A position-independent executableposition-independent executable: An executable whose code reaches other code and data through PC-relative addressing instead of fixed addresses, so it runs correctly at any load address. This is what lets the loader randomise its placement under ASLR. More in “Memory and a process's address space” can be loaded anywhere, so the linker can finish a field only when it holds a distance; an absolute address waits for the loader or is refused. Below, one NASM program’s records are read, one field is worked out byte by byte, and the PIE error is recorded.

A relocation tells the linker which bytes to patch, and how

rel.asm hands greet, a function in a shared library, the address of a 3-byte message. With default rel, [msg] is a distance from rip. The session assembles it, prints the object’s relocations, links a PIE against libgreet.so and disassembles the result:

; rel.asm: print "hi" through greet, then exit (NASM, ELF64, x86-64 Linux).
; The PC-relative version: every address is a distance from the instruction that uses it.
default rel                             ; [msg] means [rip + distance to msg]
global _start
extern greet                            ; defined in greet.asm: libgreet.so or greet.o

section .data
msg:    db "hi", 10
len     equ $ - msg                     ; 3 bytes

section .text
_start:
        lea     rsi, [msg]              ; address of msg, measured from rip
        mov     edx, len
        call    greet wrt ..plt         ; through the procedure linkage table
        mov     eax, 60                 ; exit(0)
        xor     edi, edi
        syscall

section .note.GNU-stack noalloc noexec nowrite progbits

"""Read the two relocations of rel.o, then link it into a PIE and read the bytes ld.lld wrote into each field.

greet.asm becomes libgreet.so, the shared library the PIE is linked against. Everything here is assembled, linked
and read back; starting the PIE takes an x86-64 Linux system, whose dynamic loader maps libgreet.so beside it.
"""

import pathlib
import sys

sys.path.insert(0, str(pathlib.Path(__file__).parent / "sessions"))
import session

session.run(
    """
# The object: two relocations, and four zero bytes at each offset they name.
nasm -f elf64 -o x86_64/rel.o x86_64/rel.asm
llvm-readelf -r x86_64/rel.o
llvm-objdump -d -r -M intel x86_64/rel.o
# Link a PIE against a shared library that defines greet, then look up where msg and _start ended up.
nasm -f elf64 -o x86_64/greet.o x86_64/greet.asm
ld.lld -shared -soname libgreet.so -o x86_64/libgreet.so x86_64/greet.o
ld.lld -pie --dynamic-linker /lib64/ld-linux-x86-64.so.2 -o x86_64/rel_pie x86_64/rel.o x86_64/libgreet.so
llvm-readelf -s x86_64/rel_pie | grep -E ' (msg|_start)$'
# The same instructions, with their fields filled in.
llvm-objdump -d -M intel --disassemble-symbols=_start x86_64/rel_pie
"""
)

# The object: two relocations, and four zero bytes at each offset they name.
$ nasm -f elf64 -o x86_64/rel.o x86_64/rel.asm
$ llvm-readelf -r x86_64/rel.o

Relocation section '.rela.text' at offset 0x3d0 contains 2 entries:
    Offset             Info             Type               Symbol's Value  Symbol's Name + Addend
0000000000000003  0000000200000002 R_X86_64_PC32          0000000000000000 .data - 4
000000000000000d  0000000700000004 R_X86_64_PLT32         0000000000000000 greet - 4
$ llvm-objdump -d -r -M intel x86_64/rel.o

x86_64/rel.o:	file format elf64-x86-64

Disassembly of section .text:

0000000000000000 <_start>:
       0: 48 8d 35 00 00 00 00         	lea	rsi, [rip]              # 0x7 <_start+0x7>
		0000000000000003:  R_X86_64_PC32	.data-0x4
       7: ba 03 00 00 00               	mov	edx, 0x3
       c: e8 00 00 00 00               	call	0x11 <_start+0x11>
		000000000000000d:  R_X86_64_PLT32	greet-0x4
      11: b8 3c 00 00 00               	mov	eax, 0x3c
      16: 31 ff                        	xor	edi, edi
      18: 0f 05                        	syscall
# Link a PIE against a shared library that defines greet, then look up where msg and _start ended up.
$ nasm -f elf64 -o x86_64/greet.o x86_64/greet.asm
$ ld.lld -shared -soname libgreet.so -o x86_64/libgreet.so x86_64/greet.o
$ ld.lld -pie --dynamic-linker /lib64/ld-linux-x86-64.so.2 -o x86_64/rel_pie x86_64/rel.o x86_64/libgreet.so
$ llvm-readelf -s x86_64/rel_pie | grep -E ' (msg|_start)$'
     2: 0000000000003410     0 NOTYPE  LOCAL  DEFAULT    11 msg
     6: 00000000000012f0     0 NOTYPE  GLOBAL DEFAULT     7 _start
# The same instructions, with their fields filled in.
$ llvm-objdump -d -M intel --disassemble-symbols=_start x86_64/rel_pie

x86_64/rel_pie:	file format elf64-x86-64

Disassembly of section .text:

00000000000012f0 <_start>:
    12f0: 48 8d 35 19 21 00 00         	lea	rsi, [rip + 0x2119]     # 0x3410 <msg>
    12f7: ba 03 00 00 00               	mov	edx, 0x3
    12fc: e8 1f 00 00 00               	call	0x1320 <greet@plt>
    1301: b8 3c 00 00 00               	mov	eax, 0x3c
    1306: 31 ff                        	xor	edi, edi
    1308: 0f 05                        	syscall

Each record has an offset into .text, a type, and a symbol with an addendaddend: A constant stored in a relocation entry that the linker adds to the symbol's address when it computes the value to write. The processor ABIs call it A in their formulas, as in S + A - P.. The relocation typerelocation type: The part of a relocation entry that names the formula the linker applies and the size of the field it writes, such as R_X86_64_PC32 for a 32-bit distance or R_X86_64_32S for a 32-bit absolute address. picks the formula, which the x86-64 psABI writes with S for the symbol’s value, A for the addend and P for the place being patched. R_X86_64_PC32 is S + A - P, the distance from the field to its target. R_X86_64_PLT32 does the same subtraction towards the function’s PLT entry. On AArch64 and RISC-V, one address takes two records: the high part for adrp or auipc, the low 12 bits for add or addi. In rel.o both fields hold zeros; in rel_pie the lea’s field holds 19 21 00 00. Step through the arithmetic that produced it:

An absolute address cannot be linked into a PIE

abs.asm changes one line, default abs, so the assembler stores [msg] as an absolute address in a 32-bit field. ld.lld refuses that object as a PIE and accepts it for an executable linked at a fixed address:

; abs.asm: the same program as rel.asm, with one line changed (NASM, ELF64, x86-64 Linux).
; default abs makes [msg] an absolute address, stored in the instruction as 32 signed bits.
default abs
global _start
extern greet

section .data
msg:    db "hi", 10
len     equ $ - msg

section .text
_start:
        lea     rsi, [msg]              ; the address of msg itself, as a 32-bit field
        mov     edx, len
        call    greet wrt ..plt
        mov     eax, 60
        xor     edi, edi
        syscall

section .note.GNU-stack noalloc noexec nowrite progbits

"""Assemble abs.asm, read its relocations, and link it two ways: as a PIE, which ld.lld refuses, and as a static
executable for one fixed address, which it accepts.

The sed filter keeps the instructions of _start and drops the padding bytes the linker placed after them.
"""

import pathlib
import sys

sys.path.insert(0, str(pathlib.Path(__file__).parent / "sessions"))
import session

session.run(
    """
# The absolute object: the lea's field is now R_X86_64_32S, an address in 32 signed bits.
nasm -f elf64 -o x86_64/abs.o x86_64/abs.asm
llvm-readelf -r x86_64/abs.o
# As a PIE, which may be loaded at any address, the link fails.
nasm -f elf64 -o x86_64/greet.o x86_64/greet.asm
ld.lld -shared -soname libgreet.so -o x86_64/libgreet.so x86_64/greet.o
ld.lld -pie --dynamic-linker /lib64/ld-linux-x86-64.so.2 -o x86_64/abs_pie x86_64/abs.o x86_64/libgreet.so
# Linked for one fixed address (static, not a PIE), the same object is accepted and the field holds msg itself.
ld.lld -o x86_64/abs_static x86_64/abs.o x86_64/greet.o
llvm-readelf -s x86_64/abs_static | grep -E ' msg$'
llvm-objdump -d -M intel --disassemble-symbols=_start x86_64/abs_static | sed -n '/<_start>:/,/syscall/p'
"""
)

# The absolute object: the lea's field is now R_X86_64_32S, an address in 32 signed bits.
$ nasm -f elf64 -o x86_64/abs.o x86_64/abs.asm
$ llvm-readelf -r x86_64/abs.o

Relocation section '.rela.text' at offset 0x3d0 contains 2 entries:
    Offset             Info             Type               Symbol's Value  Symbol's Name + Addend
0000000000000004  000000020000000b R_X86_64_32S           0000000000000000 .data + 0
000000000000000e  0000000700000004 R_X86_64_PLT32         0000000000000000 greet - 4
# As a PIE, which may be loaded at any address, the link fails.
$ nasm -f elf64 -o x86_64/greet.o x86_64/greet.asm
$ ld.lld -shared -soname libgreet.so -o x86_64/libgreet.so x86_64/greet.o
$ ld.lld -pie --dynamic-linker /lib64/ld-linux-x86-64.so.2 -o x86_64/abs_pie x86_64/abs.o x86_64/libgreet.so
ld.lld: error: relocation R_X86_64_32S cannot be used against local symbol; recompile with -fPIC
>>> defined in x86_64/abs.o
>>> referenced by x86_64/abs.asm
>>>               x86_64/abs.o:(.text+0x4)
[exit status 1]
# Linked for one fixed address (static, not a PIE), the same object is accepted and the field holds msg itself.
$ ld.lld -o x86_64/abs_static x86_64/abs.o x86_64/greet.o
$ llvm-readelf -s x86_64/abs_static | grep -E ' msg$'
     2: 0000000000202190     0 NOTYPE  LOCAL  DEFAULT     2 msg
$ llvm-objdump -d -M intel --disassemble-symbols=_start x86_64/abs_static | sed -n '/<_start>:/,/syscall/p'
0000000000201160 <_start>:
  201160: 48 8d 34 25 90 21 20 00      	lea	rsi, [0x202190]
  201168: ba 03 00 00 00               	mov	edx, 0x3
  20116d: e8 0e 00 00 00               	call	0x201180 <greet>
  201172: b8 3c 00 00 00               	mov	eax, 0x3c
  201177: 31 ff                        	xor	edi, edi
  201179: 0f 05                        	syscall

R_X86_64_32S is S + A, the address itself, which the linker must check sign-extends from 32 bits. Linked without -pie, abs_static puts msg at 0x202190, which fits: the field holds 90 21 20 00. A PIE has no address when it is linked, because the loader picks one at start, so S is unknown, and 32 bits cannot reach all of a 64-bit address space. The psABI’s small PIC model says “all addresses have to be relative to the instruction pointer”. In NASM the fix is default rel, or [rel msg] for one operand. The three records of the two objects, side by side:

Looking at a PIE in depth, from its object file to its first instruction, turns up four more choices that decide where each record ends up:

• Static or dynamic. Static linkingstatic linking: Linking that copies the code of every function a program calls into the executable itself, from object files and static libraries, so that no shared library has to be found when the program starts. copies the code of every function a program calls into the executable, while a dynamic one names a program interpreterprogram interpreter: The program a dynamically linked ELF executable names for the kernel to start first: the dynamic loader, which maps the shared libraries the executable needs before its _start runs. On x86-64 Linux it is /lib64/ld-linux-x86-64.so.2, the path that ld.lld's --dynamic-linker option names. that maps its shared libraries before _start runs.
• PIE or fixed address. A fixed-address executable is finished by the linker, while a PIE leaves dynamic relocationsdynamic relocation: A relocation that a linker leaves in an executable or a shared library for the dynamic loader to apply at load time, because its value depends on where the file or a library ends up in memory. for every pointer whose value depends on the load address.
• RISC-V relaxation. Linker relaxationlinker relaxation: A link-time rewrite that replaces a code sequence with a shorter one once the final addresses are known, such as a RISC-V auipc and jalr pair turned into one jal when the target is within about 1 MiB. An R_RISCV_RELAX relocation marks each place where it is allowed. More in “Calls, returns and the link register” lets the linker shorten code once the addresses are known, such as an auipc and jalr call that becomes one jal.
• Mach-O. Apple’s format has relocation types of its own for adrp, add, bl and pointers, and dyld applies what the linker leaves for load time.

Practise

Work on copies of rel.asm and abs.asm, and write each prediction down before you run the session again.

1. Put the line times 256 db 0 just before msg: in rel.asm, so msg moves 256 bytes later. Predict the four bytes of the lea’s field in rel_pie; the programmer calculator does the hex arithmetic.
2. In abs.asm, keep default abs and write lea rsi, [rel msg]. Predict the relocation type llvm-readelf -r prints for the lea, and whether the PIE link succeeds now.

Applying eight relocations by hand, checked against the linker Pro: opens with a Pro, Premium or Ultimate pass

How static and dynamic executables start, read from their headers Pro: opens with a Pro, Premium or Ultimate pass

RISC-V linker relaxation, before and after Pro: opens with a Pro, Premium or Ultimate pass

Interview questions

What do R_X86_64_PC32 and R_X86_64_32S ask the linker to write, and why can only one of them go into a PIE?

PC32 asks for a distance: the symbol’s address plus the addend minus the address of the field, S + A - P, in 32 signed bits. 32S asks for the address itself, S + A, checked to sign-extend from 32 bits. A PIE’s code and data move together, so a distance holds at every load address and the linker can finish the field. An absolute address depends on where the loader puts the file, unknown at link time, so ld.lld refuses R_X86_64_32S and suggests -fPIC. In NASM, default rel turns [msg] into a RIP-relative operand and the record into PC32.

Three harder questions follow, each set in a small project of its own.

Key takeaways

• A relocation names a field, a type and a symbol with an addend, and the type’s formula decides what the linker writes there.
• R_X86_64_PC32 stores S + A - P, a distance that stays right at any load address, which is why ld.lld could finish the lea of rel_pie with 19 21 00 00.
• R_X86_64_32S stores an address in 32 signed bits, so a PIE link refuses it, and default rel turns it into a PC32 record.
• Static or dynamic linking, a PIE or a fixed address, RISC-V relaxation and Mach-O’s own types decide where the remaining records end up and who applies them.