Linking and Loading

The previous lesson said that code generation produces a separate output for each source file. A real program, however, consists of many files, and the libraries it uses have been compiled at different times and in different places.

This lesson asks: how are separately compiled pieces brought together into a single running program?

The Object File

The output the compiler produces for a source file cannot be executed directly; it is called an object file. It contains machine code but carries incomplete information.

An object file is divided into sections. Although naming varies by format, the content is common:

Section	Content
Code	Executable instructions
Read-only data	Constants, string literals
Initialized data	Global variables given an initial value
Uninitialized data	Space to be zeroed, with only its size recorded
Symbol table	Defined and required names
Relocation records	Locations that require address fixing

Only the size of the uninitialized data section is stored; its content takes no space in the file, because all of it is zero. This explains why files that define large arrays can stay small.

Symbols

A symbol is an address bound to a name: the start of a function, or the location of a global variable. An object file lists two kinds of symbols:

• Defined symbols: The names this file provides.
• Required symbols: The names this file uses but that are defined elsewhere.

When the compiler generates a call to a required symbol, it does not know the target address; it leaves a gap and records that gap in the relocation records — a note reading, in effect, “fill this address with the real address of the symbol named add.”

Linking

The linker takes object files and libraries and produces a single output. It does three things:

1. It merges the sections. The code sections of all files are placed one after another, and the data sections one after another.
2. It resolves symbols. For every required symbol, the file that defines it is found.
3. It fixes addresses. The gaps in the relocation records are filled with the addresses that become final after merging.

This stage has two well-known errors, and neither is a compiler error:

• Undefined symbol: A name is used but not defined in any file. A typo, a missing library, or a function that has only a declaration and no written body produces this.
• Duplicate symbol: The same name is defined in more than one file. The linker cannot know which one to choose.

That these errors surface at the linking stage rather than compilation shows that a single file compiling without problems does not mean the whole program is correct.

Visibility and Name Mangling

Not every name in a file has to be visible to the linker. Languages divide symbols into two visibility levels:

• External visibility: The name is written to the symbol table and can be resolved from other files.
• Internal visibility: The name is valid only in its own file; the linker does not see it.

Internal visibility serves two purposes: the same name can be used in different files without conflict, and the number of symbols the linker has to resolve is reduced. In large projects, this directly affects linking time.

A second detail arises in languages where the same name can carry more than one meaning: two functions with the same name but different parameter types cannot sit under the same name in the symbol table. The compiler encodes type information into the name to produce a unique symbol; this is called name mangling.

The name mangling scheme is specific to the compiler and is not standardized. This is the main reason object files produced by different compilers cannot be linked together; for cross-language calls, a declaration that turns off mangling is used instead.

Static and Dynamic Linking

How libraries join a program is resolved by two separate approaches.

In static linking, the library code is copied into the output. The result is a single, large file; it looks for nothing else on the system it runs on. A fix made to the library afterward requires the program to be relinked.

In dynamic linking, the library stays a separate file; the output only records which library it needs. Part of the linking work is deferred to the moment the program starts.

Criterion	Static	Dynamic
Output size	Large	Small
Memory sharing	Each process carries its own copy	The same library is shared across processes
Update	Requires relinking	All programs are affected when the library file changes
Startup cost	None	Locating the library and resolving symbols
Distribution	Self-sufficient	A compatible version must exist on the target system

The ease of updating in dynamic linking is also a source of fragility: finding a version different from what is expected produces a symbol error at run time. Documenting compatibility rules and version marking are, for this reason, an inseparable part of library development.

Loading

When a program is run, the loader takes over. What it does:

1. It places the executable file’s sections into the process’s address space.
2. It reserves space for the uninitialized data section and zeroes it.
3. It finds and loads the required dynamic libraries and resolves the remaining symbols.
4. It prepares space for the stack and places the starting arguments.
5. It writes the program counter to the entry point; from here, control belongs to the program.

The fifth step is the beginning of the fetch–decode–execute cycle from the previous topic. The loader is the component that determines that cycle’s first address.

The loader may place code at an address not known in advance, so the generated code is required to be position independent. Position independent code uses relative addresses instead of absolute ones, letting the same library load at different addresses in different processes.

Resolving Names at Run Time

The idea behind dynamic linking — not fixing a name’s target until the last moment — is taken even further in interpreted languages: name resolution happens on every access.

import math, sys

# Importing binds the name to a module object at run time.
print(type(math))                      # <class 'module'>
print(math.__name__)                   # math

# The module object is a dictionary that carries names.
print("sqrt" in vars(math))            # True

# The name is resolved at call time: the binding can be replaced.
original_sqrt = math.sqrt
math.sqrt = lambda x: "replacement"
print(math.sqrt(9))                    # replacement
math.sqrt = original_sqrt              # the original binding is restored
print(math.sqrt(9))                    # 3.0

# Loaded modules sit in a record similar to the table the loader keeps.
print("math" in sys.modules)           # True

The cost of this flexibility is the loss of the guarantees static linking provides: a misspelled name produces no error until the corresponding line runs. The relationship between linking time and error-detection time is the same one established for type checking in the previous lesson.

Summary

• The object file that is the compiler’s output is incomplete: it lists the symbols it defines and requires, and leaves gaps for external addresses.
• The linker merges sections, resolves symbols, and fixes addresses; undefined and duplicate symbol errors surface at this stage.
• Static linking copies the library code into the output; dynamic linking leaves it in a separate file and defers resolution to startup.
• Dynamic linking provides memory sharing and easy updates, and in return brings the responsibility of version compatibility.
• The loader places sections into the address space, links the libraries, and writes the program counter to the entry point.

Next Step

The inside of the address space the loader prepares has not been opened up yet: where does the code sit, where are the global variables, where are a function call’s local variables kept? The course’s final lesson takes up these regions and the lifetime rule for each.