Neel Mishra
← All Posts
From Scratch · C++ » Project Structure

The Linker

From Scratch Series · 20 min read

What the Linker Does

In the previous article, we traced how a .cpp file becomes an object file (.o / .obj). Each object file contains compiled machine code, but it is incomplete: it references functions and variables that are defined in other translation units. The linker is the program that takes all the object files, resolves these cross-references, and produces a final executable (or shared library).

The linker is the least understood part of the C++ build pipeline, yet it is the source of some of the most confusing errors programmers encounter: "undefined reference to," "multiple definition of," "symbol not found." Understanding the linker transforms these cryptic messages into immediately diagnosable problems.

The linker operates in two fundamental phases: symbol resolution (matching every reference to a definition) and relocation (patching addresses now that the final layout is known). Everything the linker does serves one of these two purposes.

Symbol Tables

Every object file contains a symbol table: a list of all symbols (functions and global variables) that the translation unit defines or references. Each entry in the symbol table records:

# Inspect symbol table with nm:
$ nm -C main.o
                 U _GLOBAL_OFFSET_TABLE_
0000000000000000 T main
                 U _ZN6Engine3runEv         # undefined: Engine::run()
                 U _ZN6EngineC1Ev           # undefined: Engine::Engine()
                 U _ZN6EngineD1Ev           # undefined: Engine::~Engine()

$ nm -C engine.o
0000000000000000 T _ZN6Engine3runEv         # defined: Engine::run()
0000000000000030 T _ZN6EngineC1Ev           # defined: Engine::Engine()
0000000000000050 T _ZN6EngineD1Ev           # defined: Engine::~Engine()

In main.o, the symbols for Engine::run(), Engine::Engine(), and Engine::~Engine() are marked U (undefined). In engine.o, they are marked T (defined in the .text section). The linker's job is to match every U with a corresponding T across all object files.

Name Mangling

C++ supports function overloading, namespaces, templates, and classes, which means the same function name can refer to many different functions. To create unique linker symbols, the compiler mangles C++ names into a flat string that encodes the full signature:

// C++ source                          // Mangled symbol (Itanium ABI)
void foo(int)                        // _Z3fooi
void foo(double)                     // _Z3food
void foo(int, int)                   // _Z3fooii
namespace ns { void foo(int); }      // _ZN2ns3fooEi
class C { void bar(int); };          // _ZN1C3barEi
template<> void func<int>(int)      // _Z4funcIiEvT_

MSVC uses a different mangling scheme, which is why you cannot link GCC-compiled object files with MSVC-compiled ones (among other ABI differences).

The nm -C command demangles symbols, showing you the original C++ names. The c++filt utility also demangles interactively.

When you interface C++ with C, you use extern "C" to disable mangling:

extern "C" {
    void c_function(int x);    // mangled as just "c_function"
    // Allows C code (or any language using the C ABI) to call this function
}

External vs. Internal Linkage

Linkage determines whether a symbol is visible to other translation units. There are three kinds:

External Linkage

A symbol with external linkage can be seen and referenced by other TUs. By default, functions and non-const global variables have external linkage:

// util.cpp
int global_counter = 0;       // external linkage: visible to all TUs
void helper() { /* ... */ }   // external linkage

// main.cpp
extern int global_counter;    // declaration: references the same symbol
void helper();                // declaration: references the same function

Internal Linkage

A symbol with internal linkage is visible only within its own TU. Other TUs cannot see or reference it. You get internal linkage with the static keyword (at namespace scope) or by placing code in an anonymous namespace:

// util.cpp
static int counter = 0;          // internal linkage: only util.cpp can see this
static void helper() { /* ... */ } // internal linkage

// Equivalent using anonymous namespace:
namespace {
    int counter2 = 0;             // internal linkage
    void helper2() { /* ... */ }  // internal linkage
}

The linker never sees internally-linked symbols from other TUs. This is how you avoid name collisions between TUs: two different TUs can each define a static int counter, and they are completely independent symbols.

No Linkage

Local variables (inside functions) have no linkage. They exist only within their scope and have no symbol table entry at all.

Key insight: static at namespace scope means "internal linkage" (invisible to other TUs). static inside a class means "class-level, not per-instance." static inside a function means "persists across calls." The keyword is overloaded with three different meanings depending on context.

Special Case: const and constexpr

In C++, a const global variable has internal linkage by default (unlike in C, where it has external linkage). A constexpr variable also has internal linkage. This means each TU that includes a header defining a const global gets its own private copy:

// constants.h
#pragma once
const int MAX_SIZE = 1024;         // internal linkage in each TU
constexpr double PI = 3.14159;     // internal linkage in each TU
inline constexpr int VERSION = 5;  // external linkage (inline permits multiple defs)

If you want a const with external linkage (one shared definition across all TUs), you must explicitly say extern const:

// constants.h
extern const int MAX_SIZE;         // declaration (external linkage)

// constants.cpp
extern const int MAX_SIZE = 1024;  // definition

Symbol Resolution

Symbol resolution is the linker's core task: for every undefined symbol in every object file, find exactly one definition. The linker maintains a global table of all symbols it has seen, and processes object files one by one:

  1. For each object file, scan its symbol table.
  2. For each defined symbol, add it to the global table. If the symbol is already defined (from another object file), report a "multiple definition" error.
  3. For each undefined symbol, note that it needs to be resolved.
  4. After all object files are processed, check that every undefined symbol has been matched to a definition. If any remain unresolved, report "undefined reference" errors.

The "Undefined Reference" Error Explained

This is the most common linker error. It means the linker found a reference to a symbol but could not find a definition in any of the provided object files or libraries:

$ g++ main.o -o app
/usr/bin/ld: main.o: undefined reference to `Engine::run()'
collect2: error: ld returned 1 exit status

Common causes:

The "Multiple Definition" Error

This error means two or more object files define the same externally-linked symbol:

$ g++ a.o b.o -o app
/usr/bin/ld: b.o: multiple definition of `helper()'; a.o: first defined here

Common causes:

Key insight: The "undefined reference" and "multiple definition" errors are two sides of the same coin. The linker requires exactly one definition for each externally-linked symbol: zero definitions is "undefined reference," two or more is "multiple definition."

Static Linking

A static library is simply an archive of object files, bundled together for convenience. On Unix, the tool is ar (archiver), producing .a files. On Windows/MSVC, the tool is lib.exe, producing .lib files.

# Create a static library from object files:
ar rcs libengine.a engine.o physics.o renderer.o

# Link against it:
g++ main.o -L. -lengine -o app

# MSVC equivalent:
lib /out:engine.lib engine.obj physics.obj renderer.obj
cl main.obj engine.lib /Fe:app.exe

When the linker processes a static library, it does not include all object files from the archive. It only pulls in those object files that define symbols that are currently unresolved. This is a critical detail: the linker is selective.

Library Ordering Matters

On Unix linkers (GNU ld, gold, lld), the order of libraries on the command line matters. The linker processes inputs left to right. When it encounters a library, it scans for symbols that resolve current unresolved references. If a library is listed before the object file that needs it, the linker cannot go back:

# This may FAIL:
g++ -lengine main.o -o app
# The linker processes libengine.a first, but main.o hasn't been seen yet,
# so no symbols are unresolved, and no object files are pulled from the library.

# This WORKS:
g++ main.o -lengine -o app
# main.o is processed first, creating unresolved references.
# Then libengine.a is scanned, and the needed object files are pulled in.

The rule: libraries go after the object files that reference them. For mutual dependencies between libraries, you may need to list a library twice or use linker groups (--start-group, --end-group). The lld linker (used by Clang) is more forgiving and rescans by default.

Advantages and Disadvantages of Static Linking

Dynamic Linking

A dynamic library (shared library) is a compiled binary that is loaded at runtime rather than baked into the executable. On Unix, these are .so (shared object) files. On Windows, they are .dll (Dynamic Link Library) files. On macOS, .dylib.

# Create a shared library:
g++ -shared -fPIC -o libengine.so engine.o physics.o renderer.o

# Link against it:
g++ main.o -L. -lengine -o app
# At runtime, the dynamic linker (ld-linux.so / dyld / ntdll) loads libengine.so

# MSVC equivalent:
cl /LD engine.cpp physics.cpp renderer.cpp    # produces engine.dll + engine.lib (import lib)
cl main.cpp engine.lib /Fe:app.exe

The -fPIC flag (Position-Independent Code) is essential for shared libraries on most Unix platforms. It tells the compiler to generate code that works regardless of where in memory the library is loaded, using relative addresses instead of absolute ones.

Runtime Symbol Resolution

When you run an executable that depends on shared libraries, the operating system's dynamic linker (also called the runtime linker or loader) takes over before your main() runs:

  1. Read the executable's list of required shared libraries (stored in the ELF NEEDED entries).
  2. Find each library on the filesystem (using LD_LIBRARY_PATH, /etc/ld.so.conf, rpath, etc.).
  3. Map each library into the process's address space.
  4. Resolve all undefined symbols against the loaded libraries.
  5. Perform relocations (patch addresses).
  6. Call library initializers (__attribute__((constructor)) functions, C++ global constructors).
  7. Finally, call main().
# See what shared libraries an executable needs:
ldd ./app
# Output:
#   libengine.so => /usr/local/lib/libengine.so (0x7f...)
#   libstdc++.so.6 => /usr/lib/x86_64-linux-gnu/libstdc++.so.6 (0x7f...)
#   libc.so.6 => /usr/lib/x86_64-linux-gnu/libc.so.6 (0x7f...)

The PLT and GOT: How Dynamic Calls Work

Dynamic linking uses two data structures to resolve function calls efficiently:

This mechanism is called lazy binding: symbols are resolved on first use, not at load time. It speeds up startup at the cost of a small overhead on the first call. You can force eager binding with LD_BIND_NOW=1 or by linking with -z now.

Advantages and Disadvantages of Dynamic Linking

Key insight: Static linking resolves all symbols at build time and bakes them into the executable. Dynamic linking defers resolution to load time (or even first-call time with lazy binding). The choice affects executable size, deployment complexity, and performance characteristics.

Weak Symbols

A weak symbol is a symbol that can be overridden by a strong (regular) definition without causing a "multiple definition" error. If no strong definition exists, the weak definition is used. If neither exists, the symbol resolves to zero/null (for weak undefined references).

// Default implementation (weak):
__attribute__((weak)) void on_error(int code) {
    std::cerr << "Error: " << code << "\n";
    std::abort();
}

// User can override with a strong definition:
void on_error(int code) {
    // Custom error handler: log and continue
    log_error(code);
}

Weak symbols are used extensively in the C++ runtime and linker infrastructure:

COMDAT: The Windows/COFF Equivalent

On Windows (COFF object format), the equivalent of weak symbols for inline functions and templates is COMDAT sections. Each inline function or template instantiation is placed in its own COMDAT section. The linker is instructed to keep only one copy and discard duplicates. On ELF (Linux), COMDAT groups serve the same purpose.

Relocation

After symbol resolution, the linker knows the final address of every symbol. But the machine code in each object file uses placeholder addresses (often zero) for external symbols. The linker must patch these placeholders with the real addresses. This process is called relocation.

Each object file contains a relocation table listing every location in the code or data that needs patching:

# View relocations:
$ readelf -r main.o
Relocation section '.rela.text':
  Offset          Type           Symbol
  000000000015    R_X86_64_PLT32 _ZN6Engine3runEv - 4
  000000000020    R_X86_64_PLT32 _ZN6EngineC1Ev - 4
  000000000028    R_X86_64_PLT32 _ZN6EngineD1Ev - 4

Each relocation entry says: "at offset 0x15 in the .text section, insert the address of Engine::run()." The linker computes the final address of Engine::run() in the output executable and patches the instruction at offset 0x15.

Linker Output: Executables and Memory Layout

The linker combines all the sections from all input object files into a single output file. It merges all .text sections into one, all .data sections into one, and so on. The linker also assigns virtual memory addresses to each section, creates the program header table (which tells the OS how to load the executable into memory), and writes the entry point address (the address of _start, which eventually calls main).

# View the sections and layout of an executable:
readelf -S app

# View program headers (loading instructions for the OS):
readelf -l app

# On MSVC:
dumpbin /headers app.exe

On Linux, the default linker script places sections in a standard order: .text (code), .rodata (read-only data), .data (initialized data), .bss (uninitialized data). You can customize this with a linker script, though this is rare outside embedded systems.

▶ Linker: Resolving Symbols Between Two Object Files

Step through the linking process: two .o files with symbol tables are merged into a final executable.

Link-Time Optimization (LTO)

Traditionally, the compiler optimizes each TU independently. It cannot inline a function from engine.cpp into main.cpp, because when compiling main.cpp, the compiler has no access to engine.cpp's code. The linker sees only machine code, not the high-level IR needed for optimization.

Link-Time Optimization changes this. With LTO enabled, the compiler writes its intermediate representation (IR) into the object files instead of (or in addition to) machine code. The linker then invokes the optimizer on the combined IR of the entire program, enabling cross-TU optimizations:

# Enable LTO with GCC:
g++ -flto -O2 main.cpp engine.cpp -o app

# Enable LTO with Clang (thin LTO for faster builds):
clang++ -flto=thin -O2 main.cpp engine.cpp -o app

# Enable LTO with MSVC:
cl /GL main.cpp engine.cpp    # /GL = whole-program optimization
link /LTCG main.obj engine.obj /out:app.exe

Thin LTO vs. Full LTO

Full LTO merges all IR into one giant module and optimizes it as a whole. This gives the best optimization results but can be very slow and memory-hungry on large projects.

Thin LTO (introduced by LLVM/Clang) is a compromise: it does cross-module analysis (builds a summary of all functions and their call relationships) but optimizes each module independently, guided by the global summary. Thin LTO is parallelizable and much faster than full LTO, with most of the optimization benefit (typically 80-90% of full LTO's gains).

For most projects, Thin LTO is the recommended choice. Full LTO is reserved for final release builds where every last percent of performance matters.

LTO Costs

Key insight: LTO breaks down the walls between translation units at optimization time. It enables the optimizer to see the whole program and make decisions that are impossible when each TU is compiled in isolation. For performance-critical applications, LTO is one of the highest-impact optimizations you can enable.

Shared Library Versioning

Shared libraries need versioning because multiple applications may depend on different versions of the same library. On Linux, the convention uses soname versioning:

# Real file:        libengine.so.2.3.1
# Soname (symlink): libengine.so.2       -> libengine.so.2.3.1
# Linker name:      libengine.so         -> libengine.so.2

# The version numbers mean:
# 2 = major version (ABI-breaking changes)
# 3 = minor version (backward-compatible additions)
# 1 = patch version (bug fixes, no API/ABI changes)

# Set the soname when building:
g++ -shared -Wl,-soname,libengine.so.2 -o libengine.so.2.3.1 *.o

# Create symlinks:
ln -s libengine.so.2.3.1 libengine.so.2
ln -s libengine.so.2 libengine.so

The soname is embedded in the executable. At runtime, the dynamic linker looks for the soname (libengine.so.2), not the full filename. This means you can upgrade to libengine.so.2.4.0 by updating the symlink without changing any executables.

On Windows, versioning is less formalized. DLLs are identified by name, and "DLL hell" (conflicting versions of the same DLL) was historically a major problem. Modern Windows mitigates this with side-by-side assemblies and the WinSxS directory.

Runtime Loading: dlopen and LoadLibrary

You can also load shared libraries at runtime, without specifying them at link time. This is the foundation of plugin systems:

// POSIX (Linux/macOS):
#include <dlfcn.h>
void* handle = dlopen("./libplugin.so", RTLD_LAZY);
if (!handle) { /* error: dlerror() */ }

using CreateFunc = Plugin* (*)();
auto create = reinterpret_cast<CreateFunc>(dlsym(handle, "create_plugin"));
Plugin* p = create();
// ... use plugin ...
dlclose(handle);

// Windows:
#include <windows.h>
HMODULE h = LoadLibrary(TEXT("plugin.dll"));
auto create = (CreateFunc)GetProcAddress(h, "create_plugin");
Plugin* p = create();
// ... use plugin ...
FreeLibrary(h);

The functions loaded via dlsym/GetProcAddress must be exported with extern "C" to avoid name mangling issues.

Diagnosing Common Linker Errors

// "undefined reference to `vtable for Foo'"
// Cause: a virtual function is declared but not defined
// Fix: define all virtual functions (even if body is empty)

// "undefined reference to `typeinfo for Foo'"
// Cause: same as above, or RTTI is disabled for one TU but not another
// Fix: define all virtual functions; use consistent -fno-rtti flag

// "multiple definition of `helper()'"
// Cause: non-inline function defined in a header, included in multiple TUs
// Fix: make it inline, or move to a .cpp file

// "relocation R_X86_64_32 against `.text' can not be used; recompile with -fPIC"
// Cause: trying to put non-PIC code into a shared library
// Fix: recompile with -fPIC

// "cannot find -lfoo"
// Cause: library libfoo.so / libfoo.a not found in search paths
// Fix: install the library or add -L/path to the link command

Summary