15 Linking

Lecture from: 05.11.2025 | Video: Videos ETHZ

This lecture covers linking, a critical step in turning C code into a program the machine can execute. Previous lectures have discussed the C preprocessor, the compiler, and the assembler. The final step is linking.

For a single-file program, this process is simple. However, real-world software is rarely written in a single file. Large, sophisticated programs like an OS kernel, a web browser, or an IDE are built from many source files. Linking is the process of combining these elements. The compiler operates on one compilation unit at a time (typically a .c file and its included headers), but programs need to reference functions and variables across these units. It is the job of the linker to resolve these cross-file references and stitch everything together into a single, executable program.

An Example C Program

Consider a simple two-file program that serves as an example throughout this section.

main.c:

int buf[2] = {1, 2};
 
int main() {
    swap();
    return 0;
}

• Global Array: It defines a global array buf.
• External Reference: It calls a function swap(), but swap() is not defined in this file.

swap.c:

extern int buf[]; // Declares that buf is defined elsewhere
 
static int *bufp0 = &buf[0];
static int *bufp1;
 
void swap() {
    int temp;
    bufp1 = &buf[1];
    temp = *bufp0;
    *bufp0 = *bufp1;
    *bufp1 = temp;
}

• Definition: It defines the swap() function.
• Extern: The extern keyword tells the compiler that buf is a global variable that will be defined in another module.
• Static: The static keyword on the global pointers bufp0 and bufp1 makes them local to this file; they cannot be accessed by main.c or any other module.

Static Linking

The process of combining these files is called static linking. It is typically handled automatically by a compiler driver like gcc.

unix> gcc -O2 -g -o p main.c swap.c

When this command is run, gcc orchestrates a whole toolchain:

1. Translation: Each source file (main.c, swap.c) is run through the C preprocessor (cpp), the compiler (cc1), and the assembler (as).
2. Relocatable Object Files: This process produces an intermediate relocatable object file (.o file) for each source file (main.o, swap.o). These files contain machine code, but the addresses are not yet final.
3. Linking: The linker (ld) takes all the .o files as input. It merges them together, resolves cross-file references, and produces a single, fully linked executable object file (p). This file contains all the code and data from all the input files, ready to be run.

Why Do We Need Linkers?

Linkers exist for two primary reasons: modularity and efficiency.

Modularity

• Program Organization: Linkers allow a large program to be broken into smaller, more manageable source files. This is essential for team collaboration and for keeping a large codebase organized.
• Libraries: They enable the creation of libraries, collections of common functions (like the standard C library or the math library) that can be easily reused across many different programs.

Efficiency

• Time (Separate Compilation): If a project has 100 source files and one line is changed in one file, only that single file needs to be recompiled to produce a new .o file. The linking step is then very fast, as it just re-combines the existing .o files. Recompilation from scratch is avoided, saving significant time on large projects.
• Space (Libraries): When linking against a library like libc.a, which may contain hundreds of functions, the linker is smart enough to include only the code for the functions the program actually uses (e.g., printf). This keeps the final executable file and its memory footprint much smaller than if the entire library were included.

What Do Linkers Do? The Two-Step Process

The linker’s job can be broken down into two main steps:

Step 1: Symbol Resolution

Programs are built from symbols, which are names for variables and functions.

• Definition: void swap() {...} is a definition of the symbol swap.
• Reference: swap(); is a reference to the symbol swap.
• Definition/Reference: int *xp = &x; defines the symbol xp and references the symbol x.

During compilation, the compiler stores all the symbols defined or referenced in a file in a symbol table within the .o file. Each entry in this table includes the symbol’s name, type, size, and its location relative to its own file.

The linker’s first job is to scan all the input .o files and libraries. For every symbol reference it finds, it must find exactly one corresponding symbol definition.

Step 2: Relocation

Once all symbols have been resolved, the linker performs relocation.

1. Merge Sections: It merges all the sections of the same type (e.g., all .text sections, all .data sections) from the input files into a single, aggregate section in the final executable.
2. Assign Absolute Addresses: It assigns final, absolute virtual memory addresses to each section and each symbol. It relocates the symbols from their relative locations (e.g., “offset 0 in swap.o’s .text section”) to their final absolute locations (e.g., “virtual address 0x400505”).
3. Update References: It traverses the code and data and updates every reference to a symbol with the final absolute address just calculated. For example, the call swap instruction in main.o is patched to become call 0x400505.

Object Files

The linker works with three kinds of object files, or modules. In modern Unix-like systems, they all share a common format.

The Three Kinds of Object Files

1. Relocatable Object File (.o file): The output of the assembler for a single source file. It contains binary code and data, but in a form that is not yet ready to run. It includes relocation information that the linker uses to modify addresses.
2. Executable Object File: The output of the linker. It contains binary code and data in a form that can be loaded directly into memory by the OS loader and executed.
3. Shared Object File (.so file): A special type of relocatable object file that can be loaded into memory and linked dynamically, either when a program is first loaded or even during its runtime. In Windows, these are called Dynamic Link Libraries (DLLs).

Executable and Linkable Format (ELF)

On modern systems like Linux, all three types of object files use a single, unified format called the Executable and Linkable Format (ELF). This standardizes the structure of these files, making the toolchain’s job easier.

The ELF Object File Format

An ELF file is composed of several well-defined sections.

• ELF Header: Contains metadata about the file: the magic number identifying it as ELF, word size (32/64-bit), byte ordering (endianness), machine type (x86, ARM), and file type (.o, executable, .so).
• .text: The compiled machine code of the program.
• .rodata: Read-only data, such as string literals and jump tables for switch statements.
• .data: Initialized global and static variables.
• .bss: Uninitialized global and static variables (or those initialized to zero). The name is a historical artifact, sometimes remembered as “Block Started by Symbol” or “Better Save Space.” This section is just a placeholder; it occupies no actual space in the object file, but the header specifies its size. The OS loader allocates zero-filled memory for it at runtime.
• .symtab: The symbol table. It contains information about every global symbol defined or referenced in the module.
• .rel.text / .rel.data: Relocation information. This is the crucial part for the linker. It contains a list of instructions and data locations in the .text and .data sections that need to be patched with absolute addresses during relocation.
• .debug: Contains debugging information (like mappings from machine code addresses to C source file lines) if the program was compiled with the -g flag.

Linker Symbols

The linker categorizes symbols to manage their visibility across different modules.

• Global Symbols: Symbols defined in the current module (m) that are intended to be referenced by other modules. These are non-static C functions and non-static global variables.
• External Symbols: Global symbols that are referenced by the current module m but are defined in some other module. The extern keyword in C is used to declare an external symbol.
• Local Symbols: Symbols that are defined and used exclusively within the current module m. These are C functions and global variables defined with the static attribute. They are invisible to other modules.

  Local Linker Symbols vs. Local Program Variables static int file_scope_var;) is very different from a local program variable defined inside a function (e.g., int temp;). The linker knows nothing about temp; it lives only on the stack during the function's execution and is managed entirely by the compiler.

  A local linker symbol (e.g.,

Strong and Weak Symbols

To handle situations where the same global symbol might be defined in multiple files, the linker uses a concept of “strong” and “weak” symbols.

• Strong Symbols: Procedures (functions) and initialized global variables.
• Weak Symbols: Uninitialized global variables.

3. Multiple weak symbols: The linker picks an arbitrary one. This is where things get dangerous and can lead to subtle bugs.

Practice: Linker Symbols

Predicting how a linker will handle overlapping names is a common exam topic and a frequent source of bugs.

Exercise: Strong/Weak Resolution

Consider three files. Determine if they link, and what the value of x is in each case.

Case A: File 1: int x = 7; File 2: int x = 8;

• Result: Linker Error. Two strong definitions of the same name are not allowed.

Case B: File 1: int x = 7; File 2: int x;

• Result: Links. x is 7. The strong definition (initialized) beats the weak definition (uninitialized).

Case C: File 1: int x; File 2: int x;

• Result: Links. x is 0 (initialized in .bss). The linker picks an arbitrary weak definition.

Exercise: The Static Trap

File 1: static int x = 10; void f() { x++; } File 2: int x = 20; Question: Does call to f() change the x in File 2? Answer: No. The x in File 1 is local to that module because of the static keyword. It is a completely different memory location than the global x in File 2.

The -fcommon Flag and Its Dangers

Historically, GCC’s default behavior (-fcommon) was to treat uninitialized global variables as weak symbols in a “common block.” This led to some non-intuitive behaviors:

• int count; in one file and int count = 1; in another would link successfully, with all references to count pointing to the initialized (strong) version.
• int count; in one file and int count; in another would also link, with the linker merging them into a single uninitialized variable.

This was a source of subtle and nasty bugs. For example, if one file declared int x; and another declared double x;, the linker might merge them, causing an 8-byte write to double x to silently overwrite an adjacent variable y in memory.

Because of these issues, modern compilers now default to -fno-common. With this flag, an uninitialized global variable is also treated as a strong symbol. This means that any duplicate global definition, whether initialized or not, will now correctly result in a “symbol multiply defined” linker error, forcing the programmer to be explicit.

Rules for Global Variables

To avoid these linker puzzles, the following rules should be observed:

1. Avoid global variables if possible.
2. If they must be used, and they are only needed within a single file, declare them static.
3. If a global variable that must be shared is defined, initialize it to make it a strong symbol.
4. In all other files that need to use that global variable, declare it with the extern keyword. This creates a reference, not a definition.

Static Libraries

How are commonly used functions like printf or sqrt packaged? Putting them all in one .o file is inefficient. Putting each in its own .o file is a nightmare for the programmer to manage on the command line.

The solution is a static library (.a archive file).

• A static library is essentially a single file that bundles together many related .o files. It also contains an index (or catalog) that maps symbol names to the .o file that defines them.
• The linker is enhanced to work with these archives. When it has an unresolved symbol, it will search the archives provided on the command line to find the .o file that defines that symbol.
• If it finds a match, it copies only that specific .o file from the archive into the final executable.

This gives the best of both worlds: the convenience of a single library file and the efficiency of only linking the code actually needed.

Linker’s Algorithm and Command-Line Order

The linker processes files in the order they appear on the command line. This is extremely important.

1. The linker maintains a list of currently unresolved symbols.
2. It scans .o and .a files from left to right.
3. When it sees a .o file, it adds its code and data to the executable and updates its list of defined and unresolved symbols.
4. When it sees a .a file (an archive), it checks if any symbols defined in the archive can resolve any symbols in its current list of unresolved symbols. If so, it copies the corresponding .o file from the archive.
5. After scanning all files, if any symbols remain unresolved, the linker reports an error.

This leads to a common problem: command-line order matters!

• gcc -L. libtest.o -lmine: Works. The linker processes libtest.o, sees an unresolved reference to libfun, but it has not seen -lmine yet. It then processes -lmine and resolves the unresolved reference from before.
• gcc -L. -lmine libtest.o: Fails. The linker sees -lmine first. At this point, its list of unresolved symbols is empty, so it does nothing with the library. Then it sees libtest.o and adds libfun to its unresolved list. It’s too late; it has already passed the library that could have solved it.

The Linker Moral

Always put libraries at the end of the command line. This ensures that by the time the linker processes the library, it has already accumulated all the unresolved symbol references from the .o files. unix> gcc -L. libtest.o -lmine (CORRECT if libtest uses libmine) unix> gcc -L. -lmine libtest.o (WRONG)

Shared Libraries

Static libraries have some disadvantages:

• Duplication on Disk: Every executable that uses printf gets its own copy of the printf.o code baked into it. This wastes disk space.
• Duplication in Memory: If 10 different programs are running and all use printf, there will be 10 copies of the printf machine code in physical memory.
• Maintenance: If a bug is found in a library function, every single application that uses it must be explicitly relinked to get the fix.

The solution is shared libraries (.so files), also known as dynamic link libraries (DLLs).

A shared library is an object file that is loaded and linked into an application dynamically, at either load-time or run-time.

Dynamic Linking at Load-Time

This is the most common case.

1. When the program is compiled, linking is done against a shared library (e.g., libc.so). The linker does not copy the library code. Instead, it creates a partially linked executable that contains metadata saying, “This program needs libc.so to run.”
2. When the program is run, the OS loader (execve) loads the executable into memory.
3. The loader sees the metadata and invokes the dynamic linker (ld-linux.so).
4. The dynamic linker finds libc.so on disk, loads its code and data into memory, and performs the final relocation step right there in memory, patching the code to call the functions in the shared library.

This process allows multiple processes to share a single copy of the library code in physical memory, saving a huge amount of RAM.

Dynamic Linking at Run-Time

A program can also explicitly load and use a shared library after it has already started running, using the dlopen() interface.

// Dynamically load the shared library
handle = dlopen("./libvector.so", RTLD_LAZY);
 
// Get a pointer to the 'addvec' function inside the library
addvec = dlsym(handle, "addvec");
 
// Call the function through the pointer
addvec(x, y, z, 2);
 
// Unload the library
dlclose(handle);

This is a powerful technique used for things like plug-in architectures or high-performance web servers that need to load new modules without restarting.

---

Continue here: 16 Security Vulnerabilities and Floating Point Representation