Back to series
· 10 min read

Program Loading & Linking


I. What Are Program Loading and Linking?

A program is usually composed of multiple source files, object files, and external libraries. The compiler is responsible for converting source code into object code, while program loading and linking are responsible for organizing these independent pieces of code and data so that they can execute correctly in the runtime environment.

Three concepts need to be distinguished:

  • Compilation: converting source code into object code or an intermediate representation.
  • Linking: resolving symbol references and combining multiple object files and libraries into an executable file or loadable module.
  • Loading: mapping an executable file or module into the process address space and completing the necessary runtime preparation.

Typical program build and run process:

flowchart TB
    A["Source code files"] --> B["Compiler"]
    B --> C["Object files"]
    C --> D["Linker"]
    E["Static or shared libraries"] --> D
    D --> F["Executable file"]
    F --> G["Operating system loader"]
    G --> H["Process address space"]
    H --> I["Program starts executing"]

    style A fill:#E5F4EC,stroke:#A3CBB5,color:#334155
    style B fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
    style C fill:#F3EDFC,stroke:#C4B2E3,color:#334155
    style D fill:#FFF5DE,stroke:#E8D29A,color:#334155
    style E fill:#E8EDF2,stroke:#B8C3CE,color:#334155
    style F fill:#E5F4EC,stroke:#A3CBB5,color:#334155
    style G fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
    style H fill:#F3EDFC,stroke:#C4B2E3,color:#334155
    style I fill:#E5F4EC,stroke:#A3CBB5,color:#334155

    linkStyle default stroke:#A3B8AC,stroke-width:1.5px

It should be noted that compilation, linking, and loading do not necessarily occur in three strictly independent stages. For example, the dynamic linker can participate in symbol resolution when the program starts, and new shared libraries or modules can also be loaded during runtime.

II. Why Do Programs Need Linking?

In actual development, a program usually does not put all code in a single source file.

For example:

project/
├── main.c
├── math.c
├── math.h
└── logger.c

Among them:

  • main.c: program entry and main logic.
  • math.c: implementation of mathematical calculations.
  • math.h: declarations of math functions.
  • logger.c: implementation of logging functionality.

main.c can call functions defined in math.c, but when compiling main.c separately, the compiler may not yet be able to determine which object file the add() function will ultimately be in or what its concrete address is.

For example:

main.c

#include <stdio.h>
#include "math.h"

int main(void) {
    int result = add(10, 20);
    printf("%d\n", result);
    return 0;
}

math.h

#ifndef MATH_H
#define MATH_H

int add(int a, int b);

#endif

math.c

int add(int a, int b) {
    return a + b;
}

Compile separately:

gcc -c main.c -o main.o
gcc -c math.c -o math.o

At this point, two object files are generated:

main.o
math.o

main.o contains an external symbol reference to add, while math.o contains the symbol definition for add.

The linker needs to find the correspondence between these two symbols and correct the relevant address references.

flowchart TB
    A["main.o"] --> B["Referenced symbol add"]
    C["math.o"] --> D["Defined symbol add"]
    B --> E["Linker resolves symbols"]
    D --> E
    E --> F["Establish symbol correspondence"]
    F --> G["Generate executable file"]

    style A fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
    style B fill:#FFF5DE,stroke:#E8D29A,color:#334155
    style C fill:#E5F4EC,stroke:#A3CBB5,color:#334155
    style D fill:#F3EDFC,stroke:#C4B2E3,color:#334155
    style E fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
    style F fill:#E8EDF2,stroke:#B8C3CE,color:#334155
    style G fill:#E5F4EC,stroke:#A3CBB5,color:#334155

    linkStyle default stroke:#A3B8AC,stroke-width:1.5px

Perform linking:

gcc main.o math.o -o app

This generates the executable file app.

Modular program development relies on this mechanism. Different modules can be compiled independently and ultimately combined through the linker.

III. Object Files and Executable Files

To understand the linking process, you first need to understand the structure of object files.

An object file is usually not a simple collection of machine code, but a structured file containing code, data, symbol information, relocation information, and other content.

On ELF platforms such as Linux, common object files and executable files use the ELF (Executable and Linkable Format) format.

1. Main Components of an Object File

Component Purpose
.text Stores program instruction code
.data Stores initialized global variables and static variables
.bss Stores static storage duration data that is not explicitly initialized or is initialized to zero
.rodata Stores read-only data, such as string constants
.symtab Symbol table, records symbol definitions and related information
.strtab Symbol string table
.rel.text / .rela.text Records relocation information in the code section
.debug_* Debug information; whether it exists depends on the build configuration

Specific structures differ across object file formats and platforms. The names above mainly use ELF as an example.

2. Code Sections and Data Sections

Take C as an example:

int global_init = 100;
int global_uninit;

const char *message = "Hello";

int calculate(int a, int b) {
    return a + b;
}

In a typical ELF object file:

  • The machine instructions of calculate() are usually located in .text.
  • The data corresponding to global_init is usually located in .data.
  • global_uninit is usually located in .bss.
  • String literals are usually located in .rodata.
  • message itself is a pointer variable, usually located in .data, and the string content it points to is usually located in .rodata.

Note here that .bss usually does not need to store the actual zero-value bytes of each variable in the file; instead, by recording information such as the required memory size, it allows the loading process to provide zero-initialized memory for it.

3. Two Perspectives on ELF Files

ELF files have two important organizational perspectives:

  • Section: mainly serves linking, symbol resolution, and debugging.
  • Segment: mainly serves program loading and memory mapping.

For example, multiple sections can be combined into one loadable segment.

Perspective Primary User Focus
Section Linker Code, data, symbols, relocations
Segment Loader Memory mapping, permissions, file offsets

Section and Segment should not be treated as the same concept.

IV. What Are Symbols and Symbol Tables?

A symbol is a name and related attributes used during linking to identify a function, variable, or other program entity.

For example:

```c int count = 10; int add(int a, int b) { return a + b; } ``` Among them:
  • count is a variable symbol.
  • add is a function symbol.

The compiler records symbol information in the object file, and the linker uses this information to resolve references between modules.

1. Symbol Table

A symbol table typically records:

  • The symbol name.
  • The symbol type.
  • The symbol binding attribute.
  • The section it belongs to.
  • Information related to the symbol value or address.
  • The symbol size.

Taking ELF as an example, common information in the symbol table includes:

Field Meaning
st_name Offset of the symbol name in the string table
st_value Symbol value; the exact meaning depends on the file type and symbol category
st_size Symbol size
st_info Symbol type and binding attribute
st_other Information such as symbol visibility
st_shndx Index of the section the symbol belongs to

2. Common Symbol Types

Type Meaning
Local symbol Mainly used within the current object file
Global symbol Can be referenced by other object files
Weak symbol Has lower priority during symbol resolution
Undefined symbol The current object file references this symbol but does not define it in this file

For example:

extern int global_count;

int get_count(void) {
    return global_count;
}

The current object file references global_count but does not define it, so an undefined symbol is recorded in the symbol table.

The linker needs to find the corresponding definition in other object files or libraries.

3. Symbol Resolution Rules

When the linker resolves symbols, it needs to consider symbol binding attributes, visibility, definition status, and linking rules.

Common cases:

  • Strong symbols usually take precedence over weak symbols.
  • Multiple strong symbol definitions may cause a duplicate definition error.
  • When there is only an undefined reference and no corresponding definition can be found, an unresolved symbol error usually occurs.
  • Local symbols usually do not participate in global symbol resolution across object files.

Different platforms and linkers may handle the specific rules somewhat differently.

V. What Is Relocation?

Relocation is a crucial mechanism in the linking process.

When the compiler generates an object file, it usually does not yet know what addresses certain external functions or variables will ultimately be placed at.

Therefore, the object file may retain address references that are not yet determined, and use relocation information to tell the linker:

  • Which location needs to be modified.
  • Which symbol needs to be referenced.
  • Which relocation type should be used.
  • How to compute the value to write based on the final address.

1. Why Is Relocation Needed?

For example:

extern int global_value;

int get_value(void) {
    return global_value;
}

When compiling get_value(), the compiler knows that global_value needs to be accessed, but if that variable is defined in another object file, its final address is not yet determined.

Therefore, the compiler may first generate a machine instruction containing an address to be patched, and record a corresponding relocation entry.

After determining the final location of the symbol, the linker modifies the relevant fields in the instruction or data according to the relocation rules of the target platform.

2. The Basic Relocation Process

flowchart TB
    A["Generate object file"] --> B["Keep references with unresolved addresses"]
    B --> C["Record relocation entries"]
    C --> D["Linker determines symbol locations"]
    D --> E["Compute relocation value"]
    E --> F["Patch code or data"]
    F --> G["Produce executable or shared library"]

    style A fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
    style B fill:#FFF5DE,stroke:#E8D29A,color:#334155
    style C fill:#F3EDFC,stroke:#C4B2E3,color:#334155
    style D fill:#E5F4EC,stroke:#A3CBB5,color:#334155
    style E fill:#E8EDF2,stroke:#B8C3CE,color:#334155
    style F fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
    style G fill:#E5F4EC,stroke:#A3CBB5,color:#334155

    linkStyle default stroke:#A3B8AC,stroke-width:1.5px

3. The Computational Idea Behind Relocation

Relocation is not simply writing a symbol's address directly into an instruction.

Different CPU architectures have different instruction encodings and addressing modes, so the corresponding relocation types must be used.

Common calculation forms include:

Absolute address relocation:

R = S + A

PC-relative relocation:

R = S + A - P

Where:

  • R: the relocation result to be written.
  • S: the address of the target symbol.
  • A: the addend recorded in the relocation entry.
  • P: the address of the location being relocated.

These two formulas illustrate common relocation computation models; actual ELF relocation types may have different definitions and calculation rules.

PC-relative addressing is commonly used in scenarios such as function calls and jumps, and can reduce dependence on absolute addresses.

4. Why Is Position-Independent Code Important?

Modern operating systems generally support Address Space Layout Randomization (ASLR).

Each time the same program runs, its code and data may be mapped to different virtual addresses.

If machine code relies heavily on fixed absolute addresses, additional address fixups are required.

Position-independent code (PIC) can reduce dependence on a fixed load address and is particularly well suited to shared libraries.

In GCC, position-independent code can be generated with the following option:

gcc -fPIC -c math.c -o math.o

-fPIC is the common option for generating position-independent code; the specific implementation depends on the target platform and compiler.

VI. What Is a Linker?

The linker is the tool responsible for combining multiple object files and libraries and resolving the symbol reference relationships between them.

The linker's main tasks include:

  1. Parsing input files.
  2. Collecting symbol tables.
  3. Symbol resolution.
  4. Section merging and layout.
  5. Address assignment.
  6. Relocation processing.
  7. Output file generation.

1. The Linker's Basic Workflow

flowchart TB
    A["Read object files and libraries"] --> B["Parse file structure"]
    B --> C["Collect symbol tables"]
    C --> D["Resolve symbol references"]
    D --> E{"Are there unresolved symbols?"}
    E -->|"Yes"| F["Keep searching object files or libraries"]
    F --> D
    E -->|"No"| G["Merge code and data sections"]
    G --> H["Lay out memory"]
    H --> I["Perform relocation"]
    I --> J["Generate output file"]

    style A fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
    style B fill:#E8EDF2,stroke:#B8C3CE,color:#334155
    style C fill:#F3EDFC,stroke:#C4B2E3,color:#334155
    style D fill:#FFF5DE,stroke:#E8D29A,color:#334155
    style E fill:#FFF5DE,stroke:#E8D29A,color:#334155
    style F fill:#E5F4EC,stroke:#A3CBB5,color:#334155
    style G fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
    style H fill:#E8EDF2,stroke:#B8C3CE,color:#334155
    style I fill:#F3EDFC,stroke:#C4B2E3,color:#334155
    style J fill:#E5F4EC,stroke:#A3CBB5,color:#334155

    linkStyle default stroke:#A3B8AC,stroke-width:1.5px

2. Static Linking

Static linking means copying or merging the required static library code into the output file when generating the final executable.

For example:

gcc main.o math.o -o app

If a static library is used:

gcc main.o -L. -lmath -o app

Here -lmath means to link the library named math; which file is actually chosen depends on the linker's search rules and arguments.

Static libraries usually exist in forms such as .a (common on Linux) or .lib (common on Windows).

Characteristics of static linking:

  • Library code is usually incorporated into the final executable.
  • At runtime, the program does not need to look up these static libraries through the dynamic linker.
  • The executable is usually larger.
  • After a library is updated, the program usually must be relinked to use the new version.

Note that static linking does not mean the program has no dynamic dependencies at all. The program may still depend on dynamic libraries provided by the operating system.

3. Dynamic Linking

Dynamic linking does not copy the code of all dependent libraries into the executable; instead, it retains dependencies on shared libraries.

For example:

```bash gcc -shared -fPIC math.c -o libmath.so ```

Generate the shared library:

```text libmath.so ```

Then perform dynamic linking:

```bash gcc main.o -L. -lmath -o app ```

At runtime, the system needs to locate and load the corresponding shared library.

Characteristics of dynamic linking:

  • Multiple processes can share the same code mapping of a shared library.
  • Executables are usually smaller.
  • Libraries can be updated independently, but the interface and ABI compatibility must be maintained.
  • At runtime, shared library dependencies and symbol addresses must be resolved.

4. Comparison of Static Linking and Dynamic Linking

Comparison Dimension Static Linking Dynamic Linking
Library code Usually merged into the executable Shared library loaded at runtime
File size Usually larger Usually smaller
Runtime dependency Does not require the corresponding static library file Requires the shared library and its dependencies
Library updates Usually requires relinking Can be updated independently under compatible conditions
Memory sharing Code is not shared as shared-library mappings Multiple processes can share the library's read-only code pages
Deployment complexity May be lower Requires managing library versions and dependencies

5. Illustration of the Difference Between Static Linking and Dynamic Linking

```mermaid flowchart TB A["Application object file"] --> B["Static linker"] C["Static library"] --> B B --> D["Executable containing library code"] E["Application object file"] --> F["Dynamic linker or linking process"] G["Shared library dependency information"] --> F F --> H["Executable"] H --> I["Load shared libraries at runtime"] J["Shared library files"] --> I I --> K["Complete dynamic symbol binding"] style A fill:#E0F0FE,stroke:#93BCE8,color:#1E4976 style B fill:#FFF5DE,stroke:#E8D29A,color:#334155 style C fill:#E5F4EC,stroke:#A3CBB5,color:#334155 style D fill:#E5F4EC,stroke:#A3CBB5,color:#334155 style E fill:#E0F0FE,stroke:#93BCE8,color:#1E4976 style F fill:#FFF5DE,stroke:#E8D29A,color:#334155 style G fill:#F3EDFC,stroke:#C4B2E3,color:#334155 style H fill:#E8EDF2,stroke:#B8C3CE,color:#334155 style I fill:#E0F0FE,stroke:#93BCE8,color:#1E4976 style J fill:#E5F4EC,stroke:#A3CBB5,color:#334155 style K fill:#F3EDFC,stroke:#C4B2E3,color:#334155 linkStyle default stroke:#A3B8AC,stroke-width:1.5px ```

VII. What Is a Loader?

The loader is the mechanism in the operating system or runtime that is responsible for loading an executable file into the process address space and completing the preparations for program startup.

On Linux, program execution typically involves the kernel loader and the dynamic linker.

The loader needs to handle:

  • Identifying the executable file format.
  • Creating the process address space.
  • Mapping the code segment and data segment.
  • Setting memory access permissions.
  • Preparing the stack and program arguments.
  • Establishing the necessary runtime environment.
  • Transferring control to the program entry point.