How Linkers Resolve External Symbols in C

When compiling a multi-file C program, each source file is translated independently into an object file containing machine code, data, and a symbol table. The linker's role is to merge these disjointed object files into a single, cohesive executable by matching references to functions and global variables with their actual definitions. This process, known as symbol resolution, relies on symbol tables, predefined precedence rules for strong and weak symbols, and an iterative matching algorithm that ensures every declared external reference corresponds to a single, valid memory address.

The Role of the Symbol Table

During the initial compilation phase, the compiler processes each translation unit (.c file) in isolation. When it encounters a function call or a variable declared with extern that is not defined within that file, it cannot determine the memory address. Instead of failing, the compiler creates a placeholder in the code and registers an entry in the object file's symbol table.

Each symbol in the table is categorized based on its scope and linkage:

Defined Global Symbols: Functions and global variables initialized within the file that are accessible to other modules.
External (Undefined) Symbols: Functions and variables referenced in the current file but defined elsewhere.
Local Symbols: Static functions and variables with internal linkage, which the linker ignores during cross-file resolution.

Strong and Weak Symbols

To resolve naming conflicts across multiple files, linkers classify global symbols as either "strong" or "weak":

Strong Symbols: Function definitions and initialized global variables (e.g., int count = 1; or void process() {}).
Weak Symbols: Uninitialized global variables (tentative definitions like int count;) and symbols explicitly marked with compiler-specific weak attributes.

The linker resolves conflicts using three standardized rules:

Multiple strong symbols are prohibited: If two object files define the same strong symbol, the linker halts and outputs a "multiple definition" error.
A strong symbol overrides weak symbols: If a symbol has one strong definition and one or more weak definitions across different files, the linker assigns the symbol to the strong definition.
Arbitrary choice among weak symbols: If only multiple weak symbols exist for a given name, the linker picks one arbitrarily and discards the rest.

The Resolution Algorithm

During static linking, the linker scans input files from left to right as specified on the command line. It maintains three dynamic sets:

\(E\) (Executable set): The collection of object files that will form the final binary.
\(U\) (Undefined set): The collection of unresolved external symbols that have been referenced but not yet matched with a definition.
\(D\) (Defined set): The collection of symbols that have been defined by files already added to \(E\).

For each input file:

If the file is a relocatable object file (.o), the linker adds it to \(E\), adds its definitions to \(D\) (checking for strong/weak conflicts), and adds its undefined references to \(U\). It then removes any symbols from \(U\) that are now satisfied by \(D\).
If the file is an archive or static library (.a), the linker scans the library's member object files. It only extracts and adds an object file to \(E\) if that specific object file defines a symbol currently listed in \(U\). This step repeats until no more symbols in \(U\) can be resolved by the library.
Once all files are processed, if the set \(U\) is not empty, the linker terminates with an "undefined reference" error.

Relocation

Resolving symbol names is only the first half of the linker's task. Once every external symbol in \(U\) is paired with a definition in \(D\), the linker performs relocation. It merges matching sections (such as .text for code and .data for initialized variables) from all object files into continuous runtime memory segments. Finally, the linker revisits the temporary placeholders left by the compiler and patches them with the actual virtual memory addresses of the resolved symbols.