Chapter 7. Linking

Linking is the process of collecting and combining various pieces of code and data into a single file that can be loaded into memory and executed. Linking can be performed at compile time by static linkers, at load time by dynamic linkers, and at run time by application calls into the dynamic linker.

Linking enables separate compilation: a large application is decomposed into modules that are modified and compiled independently, then relinked without recompiling the other files.

The chapter assumes an x86-64 Linux system using the ELF-64 object file format. The concepts are universal across operating systems, ISAs, and object file formats.

7.1 Compiler Drivers

A compiler driver invokes the language preprocessor, compiler, assembler, and linker on behalf of the user. For gcc -Og -o prog main.c sum.c the pipeline per source file is:

main.c ──cpp──▶ main.i ──cc1──▶ main.s ──as──▶ main.o ─┐
                (ASCII          (assembly      (relocatable │
                intermediate)   language)      object file)  ├──ld──▶ prog
sum.c  ─────────────────────────────────────▶ sum.o ────────┘        (executable
                                              + system object files    object file)

Stage	Program	Input	Output
Preprocessing	`cpp`	`main.c`	`main.i`
Compilation	`cc1`	`main.i`	`main.s`
Assembly	`as`	`main.s`	`main.o`
Linking	`ld`	`main.o`, `sum.o`, system object files	`prog`

Running ./prog causes the shell to invoke the loader, an operating system function that copies the code and data of prog into memory and transfers control to the beginning of the program. Pass -v to gcc to observe the individual stages.

7.2 Static Linking

A static linker takes a collection of relocatable object files and command-line arguments and produces a fully linked executable object file. Input files consist of sections, each a contiguous sequence of bytes: instructions in one section, initialized global variables in another, uninitialized variables in yet another.

The linker performs two tasks:

Symbol resolution. Associate each symbol reference with exactly one symbol definition. Object files define and reference symbols, where each symbol corresponds to a function, a global variable, or a static variable.
Relocation. Compilers and assemblers generate code and data sections that start at address 0. The linker assigns a memory location to each symbol definition and modifies every reference to point to that location, following relocation entries generated by the assembler.

Linkers are dumb

Object files are collections of byte blocks: code, data, and structures that guide the linker and loader. The linker concatenates blocks, decides run-time locations, and patches locations inside blocks. It has minimal understanding of the target machine; compilers and assemblers have already done most of the work.

7.3 Object Files

Form	Contents	Produced by
Relocatable object file	Code and data combinable with other relocatable files at compile time into an executable	Compilers and assemblers
Executable object file	Code and data that can be copied directly into memory and executed	Linkers
Shared object file	Special relocatable file loadable into memory and linked dynamically, at load time or run time	Compilers and assemblers

An object module is a sequence of bytes; an object file is an object module stored on disk. The terms are used interchangeably.

Formats vary by system: early Unix used a.out, Windows uses PE (Portable Executable), macOS uses Mach-O, and modern x86-64 Linux and Unix use ELF (Executable and Linkable Format).

7.4 Relocatable Object Files

Layout of a typical ELF relocatable object file:

┌──────────────────────┐ 0
│ ELF header           │
├──────────────────────┤
│ .text                │
│ .rodata              │
│ .data                │
│ .bss                 │
│ .symtab              │
│ .rel.text            │
│ .rel.data            │
│ .debug               │
│ .line                │
│ .strtab              │
├──────────────────────┤
│ Section header table │
└──────────────────────┘

The ELF header begins with a 16-byte sequence describing the word size and byte ordering of the generating system, followed by the header size, the object file type (relocatable, executable, shared), the machine type (e.g., x86-64), the file offset of the section header table, and the number and size of its entries. The section header table holds a fixed-size entry per section, describing its location and size.

Section	Contents
`.text`	Machine code of the compiled program
`.rodata`	Read-only data: format strings, jump tables for `switch` statements
`.data`	Initialized global and static C variables
`.bss`	Uninitialized global and static variables, plus global or static variables initialized to zero. Occupies no space in the file; allocated in memory at run time with initial value zero
`.symtab`	Symbol table for functions and global variables defined and referenced in the program. No entries for local variables
`.rel.text`	Locations in `.text` that must be modified when the file is combined with others: instructions that call external functions or reference global variables. Omitted from executables unless explicitly requested
`.rel.data`	Relocation information for global variables referenced or defined by the module, e.g., initialized globals whose value is the address of a global variable or external function
`.debug`	Debugging symbol table: local variables, typedefs, globals, original source. Present only with `-g`
`.line`	Mapping between source line numbers and `.text` instructions. Present only with `-g`
`.strtab`	String table of null-terminated strings for `.symtab`, `.debug`, and section names

Symbol tables and -g

Every relocatable object file has a .symtab symbol table regardless of compiler flags, unless it has been removed with strip. The -g option is required only for .debug and .line.

Local C variables are maintained at run time on the stack and appear in neither .data nor .bss.

7.5 Symbols and Symbol Tables

Each relocatable object module m has a symbol table describing symbols defined and referenced by m. Three kinds of linker symbols exist:

Kind	Corresponds to	Visibility
Global symbols defined by `m`	Nonstatic C functions and global variables	Referenceable by other modules
Externals: global symbols referenced by `m` but defined elsewhere	Nonstatic C functions and globals defined in other modules	Defined by some other module
Local symbols defined and referenced exclusively by `m`	`static` C functions and variables with the `static` attribute	Visible anywhere within `m`, not referenceable by other modules

Local linker symbols are not local program variables. Nonstatic local variables are managed at run time on the stack and are invisible to the linker. Local variables declared static are not on the stack; the compiler allocates space in .data or .bss and creates a local linker symbol with a unique name. Two functions in one module each defining static int x yield two symbols, e.g., x.1 and x.2.

Symbol tables are built by assemblers from symbols the compiler exports into the .s file. The ELF symbol table lives in .symtab as an array of entries:

typedef struct {
    int  name;        /* String table offset */
    char type:4,      /* Function or data (4 bits) */
         binding:4;   /* Local or global (4 bits) */
    char reserved;    /* Unused */
    short section;    /* Section header index */
    long value;       /* Section offset or absolute address */
    long size;        /* Object size in bytes */
} Elf64_Symbol;

value is a section offset in relocatable modules and an absolute run-time address in executables. type is usually data or function; entries also exist for sections and for the source file path name. section indexes the section header table.

Three pseudosections have no section header entries and exist only in relocatable object files:

Pseudosection	Meaning
ABS	Symbols that should not be relocated
UNDEF	Undefined symbols: referenced here, defined elsewhere
COMMON	Uninitialized data objects not yet allocated. `value` gives alignment requirement, `size` gives minimum size

Modern gcc assigns symbols in relocatable object files by this convention:

Location	Symbols
COMMON	Uninitialized global variables
`.bss`	Uninitialized static variables; global or static variables initialized to zero

7.6 Symbol Resolution

The linker resolves symbol references by associating each reference with exactly one symbol definition from the symbol tables of its input relocatable object files.

Resolution of local symbols is straightforward: the compiler permits one definition per local symbol per module and gives static locals unique names. Resolution of globals is harder. When the compiler encounters a symbol not defined in the current module, it assumes an external definition, generates a linker symbol table entry, and defers to the linker. If the linker cannot find a definition in any input module, it prints an error and terminates:

linux> gcc -Wall -Og -o linkerror linkerror.c
/tmp/ccSz5uti.o: In function ‘main’:
/tmp/ccSz5uti.o(.text+0x7): undefined reference to ‘foo’

Multiple modules may also define global symbols with the same name; the linker must flag an error or choose one definition and discard the rest.

7.6.1 How Linkers Resolve Duplicate Symbol Names

At compile time the compiler exports each global symbol to the assembler as strong or weak, and the assembler records this in the symbol table.

Strength	Symbols
Strong	Functions and initialized global variables
Weak	Uninitialized global variables

Linux linkers apply three rules for duplicate names:

Multiple strong symbols with the same name are not allowed (link error).
Given one strong symbol and multiple weak symbols with the same name, choose the strong symbol.
Given multiple weak symbols with the same name, choose any one of them.

Rules 2 and 3 resolve silently. If duplicate definitions have different types, the results are insidious. With int x = 15213; int y = 15212; in one module and double x; void f() { x = -0.0; } in another, the assignment writes 8 bytes over the 4-byte x and the adjacent y, corrupting both. The linker emits only an alignment warning; the failure manifests far from the cause.

Defensive flags

gcc -fno-common turns multiply-defined global symbols into an error. -Werror turns all warnings into errors. Use them.

The COMMON convention exists because of these rules. For a weak global x, the compiler cannot know whether another module defines x or which definition the linker will pick, so it defers the decision by placing x in COMMON. A global initialized to zero is strong and therefore unique by rule 2, so the compiler can confidently place it in .bss. Static symbols are unique by construction and go to .data or .bss.

7.6.2 Linking with Static Libraries

A static library packages related object modules into a single file that can be supplied as linker input. The linker copies only those member object modules that are referenced by the program, reducing executable size on disk and in memory, while the programmer names only a few library files on the command line.

Alternative designs and their defects:

Approach	Defect
Standard functions built into the compiler	Complexity in the compiler; every function change requires a new compiler version
One monolithic `libc.o` linked into every executable	Every executable and every running process carries a full copy; any change forces recompiling the whole library
One object file per function, linked explicitly	Error-prone and time-consuming for programmers

On Linux, static libraries are stored as archives: concatenated relocatable object files with a header describing the size and location of each member. Archive filenames use the .a suffix.

linux> gcc -c addvec.c multvec.c
linux> ar rcs libvector.a addvec.o multvec.o
linux> gcc -c main2.c
linux> gcc -static -o prog2c main2.o ./libvector.a        # or: -L. -lvector

-static requests a fully linked executable requiring no further linking at load time. -lvector abbreviates libvector.a; -L. adds the current directory to the library search path. If main2.o references only addvec, the linker copies addvec.o but not multvec.o into the executable. Compiler drivers always pass libc.a to the linker automatically.

7.6.3 How Linkers Use Static Libraries to Resolve References

During symbol resolution the linker scans object files and archives left to right in command-line order, maintaining three sets, all initially empty:

Set	Contents
E	Relocatable object files to be merged into the executable
U	Unresolved symbols: referenced but not yet defined
D	Symbols defined in previous input files

For each input file f:

If f is an object file: add f to E, update U and D from its definitions and references, continue.
If f is an archive: match symbols in U against symbols defined by archive members. If member m defines a symbol resolving a reference in U, add m to E and update U and D. Iterate over the members until U and D stop changing (fixed point). Members not added to E are discarded.
If U is nonempty after all input files are processed, the linker prints an error and terminates. Otherwise it merges and relocates the files in E.

Ordering on the command line is therefore significant. If a library appears before an object file that references it, the references remain unresolved:

linux> gcc -static ./libvector.a main2.c
/tmp/cc9XH6Rp.o(.text+0x18): undefined reference to ‘addvec’

Command-line ordering rules

Place libraries at the end of the command line. If libraries reference each other, order them so that each symbol reference precedes its definition in the scan. Cyclic dependences require repeating libraries (gcc foo.c libx.a liby.a libx.a) or combining archives.

7.7 Relocation

After symbol resolution, every reference is bound to exactly one definition and the linker knows the exact sizes of the code and data sections of its inputs. Relocation merges the input modules and assigns run-time addresses in two steps:

Relocating sections and symbol definitions. All sections of the same type are merged into one aggregate section of that type (e.g., all input .data sections become the output .data section). The linker assigns run-time addresses to the aggregate sections, to the input sections, and to every symbol definition. Every instruction and global variable now has a unique run-time address.
Relocating symbol references within sections. The linker modifies every symbol reference in code and data so that it points to the correct run-time address, guided by relocation entries.

7.7.1 Relocation Entries

The assembler does not know where code and data will reside in memory, nor where externally defined functions and variables will be. For each reference whose ultimate location is unknown it emits a relocation entry: code entries in .rel.text, data entries in .rel.data.

typedef struct {
    long offset;      /* Offset of the reference to relocate */
    long type:32,     /* Relocation type */
         symbol:32;   /* Symbol table index */
    long addend;      /* Constant part of relocation expression */
} Elf64_Rela;

ELF defines 32 relocation types. Two matter here:

Type	Meaning
`R_X86_64_PC32`	Relocate a reference using a 32-bit PC-relative address: an offset added to the run-time PC, which holds the address of the next instruction
`R_X86_64_32`	Relocate a reference using a 32-bit absolute address: the CPU uses the encoded value directly as the effective address

These two types support the x86-64 small code model, which assumes total code and data in the executable smaller than 2 GB, addressable with 32-bit PC-relative offsets. The small code model is the gcc default; -mcmodel=medium and -mcmodel=large exist for larger programs.

7.7.2 Relocating Symbol References

Relocation algorithm, where ADDR(s) and ADDR(r.symbol) are the chosen run-time addresses of section s and the referenced symbol:

foreach section s {
    foreach relocation entry r {
        refptr = s + r.offset;    /* ptr to reference to be relocated */

        /* Relocate a PC-relative reference */
        if (r.type == R_X86_64_PC32) {
            refaddr = ADDR(s) + r.offset;   /* ref's run-time address */
            *refptr = (unsigned) (ADDR(r.symbol) + r.addend - refaddr);
        }

        /* Relocate an absolute reference */
        if (r.type == R_X86_64_32)
            *refptr = (unsigned) (ADDR(r.symbol) + r.addend);
    }
}

PC-relative example. In main.o, callq to sum starts at section offset 0xe: opcode 0xe8 followed by a 32-bit placeholder. Relocation entry: offset = 0xf, symbol = sum, type = R_X86_64_PC32, addend = -4. With ADDR(.text) = 0x4004d0 and ADDR(sum) = 0x4004e8:

refaddr = 0x4004d0 + 0xf              = 0x4004df
*refptr = 0x4004e8 + (-4) - 0x4004df  = 0x5

Relocated instruction: 4004de: e8 05 00 00 00 callq 4004e8 <sum>. At run time the CPU pushes the PC (0x4004e3, the next instruction) and sets PC ← 0x4004e3 + 0x5 = 0x4004e8, the first instruction of sum. The addend of -4 compensates for the reference lying 4 bytes before the point from which the PC-relative offset is measured.

Absolute example. mov of the address of array into %edi has entry offset = 0xa, symbol = array, type = R_X86_64_32, addend = 0. With ADDR(array) = 0x601018:

*refptr = 0x601018 + 0 = 0x601018

Relocated instruction: 4004d9: bf 18 10 60 00 mov $0x601018,%edi. The loader can then copy the sections into memory and execute them without further modification.

7.8 Executable Object Files

Layout of a typical ELF executable:

┌──────────────────────┐ 0
│ ELF header           │ ┐
│ Segment header table │ │ Read-only memory segment
│ .init                │ │ (code segment)
│ .text                │ │
│ .rodata              │ ┘
├──────────────────────┤
│ .data                │ ┐ Read/write memory segment
│ .bss                 │ ┘ (data segment)
├──────────────────────┤
│ .symtab              │ ┐
│ .debug               │ │ Not loaded into memory
│ .line                │ │
│ .strtab              │ ┘
├──────────────────────┤
│ Section header table │
└──────────────────────┘

The format resembles a relocatable file. The ELF header additionally records the entry point, the address of the first instruction to execute. .init defines a small function _init called by program initialization code. Since the executable is fully relocated, .rel sections are unnecessary.

Executables are designed for easy loading: contiguous chunks of the file map to contiguous memory segments, as described by the program header table. For the example prog:

Segment	Permissions	Start address	Memory size	Initialized from
Code	read/execute	`0x400000`	`0x69c`	First `0x69c` bytes of the file: ELF header, program header table, `.init`, `.text`, `.rodata`
Data	read/write	`0x600df8`	`0x230`	`0x228` bytes of `.data` at file offset `0xdf8`; remaining 8 bytes are `.bss`, zeroed at run time

For any segment, the linker chooses a start address vaddr satisfying

vaddr mod align = off mod align

where off is the file offset of the segment's first section and align is the alignment in the program header (2^21 = 0x200000). This alignment requirement is an optimization tied to how virtual memory is organized in large power-of-2 chunks (Chapter 9).

7.9 Loading Executable Object Files

Typing ./prog makes the shell invoke the loader, memory-resident OS code that copies the code and data of the executable from disk into memory and jumps to the entry point. Any program can invoke the loader via the execve function (Section 8.4.6). The copy-then-run process is loading.

Run-time memory image of a Linux x86-64 process:

2^48-1 ┌───────────────────────────────┐
       │ Kernel memory                 │  invisible to user code
       ├───────────────────────────────┤
       │ User stack (grows down)       │ ◀── %rsp
       │              ▼                │
       ├───────────────────────────────┤
       │ Memory-mapped region for      │
       │ shared libraries              │
       ├───────────────────────────────┤
       │              ▲                │
       │ Run-time heap (grows up,      │ ◀── brk
       │ created by malloc)            │
       ├───────────────────────────────┤
       │ Read/write segment            │ ┐ loaded from the
       │ (.data, .bss)                 │ │ executable file
       ├───────────────────────────────┤ │
       │ Read-only code segment        │ │
0x400000 (.init, .text, .rodata)       │ ┘
       ├───────────────────────────────┤
0      └───────────────────────────────┘

In practice a gap exists between code and data segments due to the .data alignment requirement, and address-space layout randomization (ASLR) varies the run-time positions of stack, shared library, and heap segments per run; relative positions stay the same.

Guided by the program header table, the loader copies chunks of the executable into the code and data segments, then jumps to the entry point: the _start function, defined in the system object file crt1.o and identical for all C programs. _start calls __libc_start_main (defined in libc.so), which initializes the execution environment, calls the user main, handles its return value, and returns control to the kernel if needed.

How loading actually works

Each program runs in a process with its own virtual address space. The shell forks a child, the child invokes the loader via execve, and the loader deletes the child's existing virtual memory segments and creates fresh code, data, heap, and stack segments. The new stack and heap are zeroed. The new code and data segments are initialized by mapping virtual pages to page-size chunks of the executable file. No data is copied from disk at load time apart from header information; copying is deferred until the CPU first touches a mapped page, at which point the paging mechanism transfers it.

7.10 Dynamic Linking with Shared Libraries

Static libraries have drawbacks: applications must be explicitly relinked against updated libraries, and common code such as printf is duplicated in the text segment of every running process, wasting memory.

A shared library is an object module that can be loaded at an arbitrary memory address and linked with a program in memory, at load time or run time. The process is dynamic linking, performed by a dynamic linker. Shared libraries are also called shared objects, use the .so suffix on Linux, and correspond to DLLs on Microsoft systems.

Sharing happens in two senses:

One .so file per library per file system; its code and data are shared by all executables that reference it, rather than copied and embedded as with static libraries.
One copy of a shared library's .text section in memory can be shared by multiple running processes (mechanism in Chapter 9).

Building and using a shared library:

linux> gcc -shared -fpic -o libvector.so addvec.c multvec.c
linux> gcc -o prog2l main2.c ./libvector.so

-fpic requests position-independent code; -shared requests a shared object. Linking against libvector.so performs partial linking at link time: no code or data sections from the library are copied into the executable. The linker copies relocation and symbol table information that allows references to libvector.so to be resolved at load time.

Load-time sequence:

The loader loads the partially linked executable prog2l.
It finds a .interp section containing the path of the dynamic linker (itself a shared object, ld-linux.so on Linux) and runs the dynamic linker instead of passing control to the application.
The dynamic linker relocates the text and data of libc.so into a memory segment, relocates the text and data of libvector.so into another segment, and relocates all references in prog2l to symbols defined by the libraries.
The dynamic linker passes control to the application. From then on the locations of the shared libraries are fixed for the duration of execution.

7.11 Loading and Linking Shared Libraries from Applications

An application can request the dynamic linker to load and link arbitrary shared libraries while running, without linking against them at compile time. Uses:

Software distribution. Windows developers ship updates as new shared library versions that applications pick up automatically on the next run.
High-performance web servers. Instead of forking a child and running a CGI program via fork and execve, servers package content-generating functions in shared libraries, load and link them on demand, and call them directly. Functions stay cached in the server address space; subsequent requests cost a plain function call, and functions can be updated or added at run time without stopping the server.

Interface to the dynamic linker (#include <dlfcn.h>, link with -ldl):

Function	Behavior	Returns
`void dlopen(const char filename, int flag)`	Loads and links shared library `filename`. External symbol resolution uses previously opened libraries with the `RTLD_GLOBAL` flag. Flags `RTLD_NOW` (resolve at load) or `RTLD_LAZY` (defer resolution) may be ORed with `RTLD_GLOBAL`	Handle, or NULL on error
`void dlsym(void handle, char *symbol)`	Looks up `symbol` in the opened library	Symbol address, or NULL
`int dlclose(void *handle)`	Unloads the library if no other library still uses it	0, or −1 on error
`const char *dlerror(void)`	Reports the most recent error from `dlopen`, `dlsym`, or `dlclose`	Message string, or NULL if none

#include <stdio.h>
#include <stdlib.h>
#include <dlfcn.h>

int x[2] = {1, 2};
int y[2] = {3, 4};
int z[2];

int main()
{
    void *handle;
    void (*addvec)(int *, int *, int *, int);
    char *error;

    handle = dlopen("./libvector.so", RTLD_LAZY);
    if (!handle) {
        fprintf(stderr, "%s\n", dlerror());
        exit(1);
    }

    addvec = dlsym(handle, "addvec");
    if ((error = dlerror()) != NULL) {
        fprintf(stderr, "%s\n", error);
        exit(1);
    }

    addvec(x, y, z, 2);

    if (dlclose(handle) < 0) {
        fprintf(stderr, "%s\n", dlerror());
        exit(1);
    }
    return 0;
}

Compile with gcc -rdynamic -o prog2r dll.c -ldl.

7.12 Position-Independent Code (PIC)

Sharing one in-memory copy of library code across processes requires that the code run correctly regardless of its load address. Assigning each shared library a fixed a priori address range fails: it wastes address space on unused libraries, requires nonoverlapping chunk management as libraries grow and multiply, fragments the address space over time, and differs per system.

Code that can be loaded without any relocations is position-independent code (PIC), generated with gcc -fpic. Shared libraries must always be compiled with this option. A single copy of a PIC code segment can be shared by any number of processes; each process still gets its own copy of the read/write data segment.

On x86-64, references to symbols within the same executable object module need no special treatment: they compile to PC-relative addresses relocated by the static linker. External procedures and globals defined by shared modules require the techniques below.

PIC Data References

Key fact: wherever an object module is loaded, its data segment is always the same distance from its code segment. The distance between any instruction and any variable in the module is a run-time constant, independent of absolute addresses.

Compilers exploit this with a global offset table (GOT) at the beginning of the data segment. The GOT contains one 8-byte entry per global data object (procedure or global variable) referenced by the module, plus a relocation record per entry. At load time the dynamic linker fills each GOT entry with the absolute address of its object. Each object module that references globals has its own GOT.

addvec:
    mov  0x2008b9(%rip),%rax   # %rax = *GOT[3] = &addcnt
    addl $0x1,(%rax)           # addcnt++

The PC-relative offset to the GOT entry is a run-time constant; the indirection through the GOT supplies the run-time address. For a global defined in the same shared module the compiler could use a direct PC-relative reference, but it may use the GOT for all references as the most general solution. If the global is defined by another shared module, the GOT indirection is necessary.

PIC Function Calls and Lazy Binding

The run-time address of a function defined in a shared library is unknown at compile time. Rather than have the dynamic linker eagerly relocate every such reference at load time, GNU systems use lazy binding: address resolution is deferred until the first actual call. Since a typical application calls only a fraction of the hundreds or thousands of functions exported by a library such as libc.so, this avoids most relocations. The first call pays a nontrivial cost; each later call costs one extra instruction and one memory reference.

Lazy binding uses two structures, present in every object module that calls shared library functions:

Structure	Location	Contents
Procedure linkage table (PLT)	Code segment	Array of 16-byte code entries. `PLT[0]` jumps into the dynamic linker; each called library function has its own entry
Global offset table (GOT)	Data segment	`GOT[0]` and `GOT[1]` hold information the dynamic linker uses to resolve addresses (address of `.dynamic`, address of relocation entries); `GOT[2]` is the entry point of the dynamic linker in `ld-linux.so`; each remaining entry corresponds to a called function and has a matching PLT entry. Initially each such GOT entry points to the second instruction of its PLT entry

First call to addvec (PLT entry PLT[2], GOT entry GOT[4]):

callq PLT[2]                       # step 1: call the PLT entry, not addvec
PLT[2]: jmpq *GOT[4]               # step 2: indirect jump; GOT[4] initially
                                   #   points back to the next instruction
        pushq $0x1                 # step 3: push relocation ID for addvec
        jmpq  PLT[0]               #   and jump to PLT[0]
PLT[0]: pushq *GOT[1]              # step 4: push argument for dynamic linker
        jmpq  *GOT[2]              #   jump into dynamic linker, which uses the
                                   #   two stack entries to locate addvec,
                                   #   overwrites GOT[4] with its address,
                                   #   and passes control to addvec

Subsequent calls:

callq PLT[2]                       # step 1: as before
PLT[2]: jmpq *GOT[4]               # step 2: GOT[4] now holds &addvec;
                                   #   control transfers directly to addvec

7.13 Library Interpositioning

Library interpositioning intercepts calls to shared library functions and executes replacement code instead. The basic idea: given a target function, create a wrapper function with an identical prototype and, via an interpositioning mechanism, trick the system into calling the wrapper. The wrapper typically calls the target, performs extra work such as tracing, and returns to the caller. Interpositioning can occur at compile time, link time, or run time. The running example wraps malloc and free to trace allocations.

7.13.1 Compile-Time Interpositioning

The C preprocessor replaces calls to the targets with calls to wrappers. A local malloc.h supplies the macros:

/* malloc.h (local) */
#define malloc(size) mymalloc(size)
#define free(ptr)    myfree(ptr)

void *mymalloc(size_t size);
void myfree(void *ptr);

/* mymalloc.c, COMPILETIME case */
#include <stdio.h>
#include <malloc.h>            /* standard header: wrappers see real malloc */

void *mymalloc(size_t size)
{
    void *ptr = malloc(size);
    printf("malloc(%d)=%p\n", (int)size, ptr);
    return ptr;
}

void myfree(void *ptr)
{
    free(ptr);
    printf("free(%p)\n", ptr);
}

linux> gcc -DCOMPILETIME -c mymalloc.c
linux> gcc -I. -o intc int.c mymalloc.o

-I. makes the preprocessor find the local malloc.h before the system directories; the wrappers themselves are compiled against the standard header. Requires access to source files.

7.13.2 Link-Time Interpositioning

The static linker flag --wrap f resolves references to f as __wrap_f and references to __real_f as f:

/* mymalloc.c, LINKTIME case */
void *__real_malloc(size_t size);
void  __real_free(void *ptr);

void *__wrap_malloc(size_t size)
{
    void *ptr = __real_malloc(size);   /* call libc malloc */
    printf("malloc(%d) = %p\n", (int)size, ptr);
    return ptr;
}

void __wrap_free(void *ptr)
{
    __real_free(ptr);                  /* call libc free */
    printf("free(%p)\n", ptr);
}

linux> gcc -DLINKTIME -c mymalloc.c
linux> gcc -c int.c
linux> gcc -Wl,--wrap,malloc -Wl,--wrap,free -o intl int.o mymalloc.o

-Wl,option passes option to the linker, with each comma replaced by a space. Requires access to relocatable object files.

7.13.3 Run-Time Interpositioning

The dynamic linker's LD_PRELOAD environment variable names shared objects to search first when resolving undefined references at load and run time. Wrappers define functions with the original names and locate the real definitions with dlsym(RTLD_NEXT, ...), which searches the subsequent libraries in the load order:

/* mymalloc.c, RUNTIME case */
#define _GNU_SOURCE
#include <stdio.h>
#include <stdlib.h>
#include <dlfcn.h>

void *malloc(size_t size)
{
    void *(*mallocp)(size_t size);
    char *error;

    mallocp = dlsym(RTLD_NEXT, "malloc");  /* get address of libc malloc */
    if ((error = dlerror()) != NULL) {
        fputs(error, stderr);
        exit(1);
    }
    char *ptr = mallocp(size);
    printf("malloc(%d) = %p\n", (int)size, ptr);
    return ptr;
}

void free(void *ptr)
{
    void (*freep)(void *) = NULL;
    char *error;

    if (!ptr)
        return;

    freep = dlsym(RTLD_NEXT, "free");      /* get address of libc free */
    if ((error = dlerror()) != NULL) {
        fputs(error, stderr);
        exit(1);
    }
    freep(ptr);
    printf("free(%p)\n", ptr);
}

linux> gcc -DRUNTIME -shared -fpic -o mymalloc.so mymalloc.c -ldl
linux> gcc -o intr int.c
linux> LD_PRELOAD="./mymalloc.so" ./intr

Requires access only to the executable. LD_PRELOAD interposes on the library calls of any executable, including system binaries such as /usr/bin/uptime.

Mechanism	Requires access to	Tool
Compile time	Source files	C preprocessor macros
Link time	Relocatable object files	`ld --wrap f`
Run time	Executable only	`LD_PRELOAD` and `dlsym(RTLD_NEXT, ...)`

7.14 Tools for Manipulating Object Files

Tool	Function
`ar`	Creates static libraries; inserts, deletes, lists, extracts members
`strings`	Lists printable strings in an object file
`strip`	Deletes symbol table information
`nm`	Lists symbols in the symbol table
`size`	Lists names and sizes of sections
`readelf`	Displays the complete structure of an object file, including the ELF header; subsumes `size` and `nm`
`objdump`	Displays all information in an object file; most useful for disassembling `.text`
`ldd`	Lists the shared libraries an executable needs at run time

7.15 Summary

Linking is performed at compile time by static linkers and at load and run time by dynamic linkers. Object files come in relocatable, executable, and shared forms. The two main linker tasks are symbol resolution, binding each global symbol to a unique definition, and relocation, determining the run-time address of each symbol and modifying references accordingly. Multiple object files may define the same symbol; the silent resolution rules can introduce subtle bugs. The left-to-right scan of static libraries makes command-line ordering significant and is another source of link-time errors. Shared objects are loaded anywhere in memory and shared at run time by multiple processes via position-independent code; applications can invoke the dynamic linker at run time through the dlopen interface.