CD Notes

The Linker

Comprehensive guide to linking, symbol resolution, relocation, and executable creation

The linker is a crucial system software component that combines multiple object files and libraries into a single executable program. It resolves external references, manages memory layout, and creates the final runnable binary.

What is a Linker?

A linker is a program that takes object files (and libraries) produced by compilers/assemblers, resolves cross-file references, and creates an executable or shared library. It handles the complex task of combining multiple compiled modules into one coherent program.

Object Files + Libraries │ │ │ ├────┼────┤ │ │ │ ▼ ▼ ▼ ┌──────────────────┐ │ Linker │ │ (Resolve refs) │ └──────────────────┘ │ ▼ Executable Program

Linker Functions

1. Symbol Resolution

The linker resolves external references across object files.

│ Exports	main() │
│ Imports	add() │ <-- add() undefined here
│ Exports	add() │ <-- Defined here!
│ Imports	(none) │
file1's "add()" call	file2's add() definition

2. Relocation

Adjusts addresses in code when the final layout is determined.

Before Linking:

Example

file1.o: main() at 0x0000 call 0x1000 (expecting add at 0x1000) file2.o: add() at 0x0000 ...

After Linking:

Example

Executable: main() at 0x401000 call 0x401100 (updated to new add location) add() at 0x401100 ...

3. Layout

Organizes all sections from different object files into memory:

Memory Layout in Executable: ┌─────────────────────┐ │ Header │ ├─────────────────────┤ │ .text (Code) │ All .text sections combined │ from file1.o │ │ from file2.o │ │ from file3.o │ ├─────────────────────┤ │ .data (Data) │ All .data sections combined │ initialized data │ ├─────────────────────┤ │ .bss (BSS) │ Uninitialized data │ (zero-filled) │ ├─────────────────────┤ │ .symtab │ Symbol table ├─────────────────────┤ │ .strtab │ String table ├─────────────────────┤ │ Other sections │ └─────────────────────┘

Linker Process

┌────────────────────────────────────────┐ │ Input: Object Files & Libraries │ │ file1.o, file2.o, libstd.a │ └────────────────┬───────────────────────┘ │ ┌───────▼────────┐ │ Symbol Table │ Collect all symbols │ Gathering │ from all objects └───────┬────────┘ │ ┌───────▼──────────────┐ │ Undefined Symbols │ │ Resolution │ └───────┬──────────────┘ │ ┌───────▼────────┐ │ Address │ Assign addresses │ Assignment │ to sections └───────┬────────┘ │ ┌───────▼────────┐ │ Relocation │ Update addresses │ Processing │ in code └───────┬────────┘ │ ┌───────▼────────────────┐ │ Section Merging │ │ & Layout │ └───────┬────────────────┘ │ ┌───────▼────────┐ │ Output │ │ Executable │ └────────────────┘

Example: Linking Two Files

File 1: main.c

c example

int add(int a, int b);  // External declaration

int main() {
    int result = add(5, 3);
    return result;
}

File 2: add.c

c example

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

Compilation:

bash example

gcc -c main.c    → main.o (main() defined, add() undefined)
gcc -c add.c     → add.o (add() defined)

Object Files (simplified):

main.o:

Symbol Table

main @ 0x0000

add @ undefined (external symbol)

Code Section

0x0000: CALL add (address to be resolved)

...

add.o:

Symbol Table

add @ 0x0000

Code Section

0x0000: MOV EAX, [EBP+8]

0x0003: ADD EAX, [EBP+12]

0x0006: RET

Linking:

bash example

gcc main.o add.o -o program

Result (Executable):

Example

Final Executable: .text section: main @ 0x401000 CALL 0x401010 add @ 0x401010 MOV EAX, [EBP+8] ADD EAX, [EBP+12] RET

Symbol Resolution Process

│ Symbols found	│
│ main references	add ✓, printf ✓ │
│ add references	none │
│ main.o: CALL at 0x0000	resolve add │
│ main.o: CALL at 0x0005	resolve printf

Symbol Table Merging

When linking multiple files, symbol tables are merged:

Symbol	Object File	Address	Type
main	main.o	0x401000	function
add	add.o	0x401010	function
printf	libc.a	0x401020	function
global_var	main.o	0x402000	data

Common Linker Errors

Cause	Function called but never defined
Cause	Symbol defined in multiple files
Cause	Library not found or path incorrect
Cause	External reference not satisfied
Cause	Library A needs B, B needs A

Linking Model: Static vs Dynamic

Static Linking

Example

program.o + libfoo.a → program (all code included) Larger file size, no runtime dependencies

Dynamic Linking

Example

program.o + libfoo.so → program (stub references) Smaller file, library loaded at runtime

Interview Q&A

Q: What does a linker do? A: A linker combines object files and libraries into an executable or shared library. It resolves external references, assigns memory addresses, and processes relocations.

Q: What is symbol resolution? A: Symbol resolution is the process of matching external symbol references from one object file to their definitions in other object files or libraries.

Q: What is relocation? A: Relocation is adjusting memory addresses in machine code after the final memory layout is determined. It converts relative addresses to absolute addresses.

Q: What's the difference between static and dynamic linking? A: Static linking includes all library code in the executable at link time. Dynamic linking creates references to external libraries that are resolved at runtime.

Q: What causes "undefined reference" errors? A: A function or variable is called/used but never defined anywhere in the linked object files or libraries. The linker cannot find its definition.

Exam Focus

Revise definitions, diagrams, examples, and short-answer points for The Linker.

Interview Use

Prepare one clear explanation, one practical example, and one common mistake for this Compiler Design topic.

Search Terms

compiler-design, compiler design, compiler, design, language, processing, system, linker

Continue learning this concept

Language Processing SystemThe AssemblerLearn about assembly language, assembler functions, machine code generation, and assembly instruction set details Language Processing SystemCompiler OverviewComprehensive guide to compiler architecture, phases, and how source code is transformed into executable code Language Processing SystemComplete Compilation ProcessDetailed walkthrough of the entire compilation pipeline from source code to program execution Language Processing SystemThe LoaderDetailed guide to program loading, memory allocation, relocation, and execution setup Language Processing SystemThe PreprocessorLearn about preprocessors, macro expansion, file inclusion, and conditional compilation in detail IntroductionLanguage ProcessorsComplete guide to language processors including compilers, interpreters, assemblers, linkers, loaders, and preprocessors in the compilation system.

PreviousComplete Compilation Process NextThe Loader

CD Notes

The Linker

Comprehensive guide to linking, symbol resolution, relocation, and executable creation

What is a Linker?

Linker Functions

1. Symbol Resolution

The linker resolves external references across object files.

│ Exports	main() │
│ Imports	add() │ <-- add() undefined here
│ Exports	add() │ <-- Defined here!
│ Imports	(none) │
file1's "add()" call	file2's add() definition

2. Relocation

Adjusts addresses in code when the final layout is determined.

Before Linking:

Example

file1.o: main() at 0x0000 call 0x1000 (expecting add at 0x1000) file2.o: add() at 0x0000 ...

After Linking:

Example

Executable: main() at 0x401000 call 0x401100 (updated to new add location) add() at 0x401100 ...

3. Layout

Organizes all sections from different object files into memory:

Linker Process

Example: Linking Two Files

File 1: main.c

c example

int add(int a, int b);  // External declaration

int main() {
    int result = add(5, 3);
    return result;
}

File 2: add.c

c example

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

Compilation:

bash example

gcc -c main.c    → main.o (main() defined, add() undefined)
gcc -c add.c     → add.o (add() defined)

Object Files (simplified):

main.o:

Symbol Table

main @ 0x0000

add @ undefined (external symbol)

Code Section

0x0000: CALL add (address to be resolved)

...

add.o:

Symbol Table

add @ 0x0000

Code Section

0x0000: MOV EAX, [EBP+8]

0x0003: ADD EAX, [EBP+12]

0x0006: RET

Linking:

bash example

gcc main.o add.o -o program

Result (Executable):

Example

Final Executable: .text section: main @ 0x401000 CALL 0x401010 add @ 0x401010 MOV EAX, [EBP+8] ADD EAX, [EBP+12] RET

Symbol Resolution Process

│ Symbols found	│
│ main references	add ✓, printf ✓ │
│ add references	none │
│ main.o: CALL at 0x0000	resolve add │
│ main.o: CALL at 0x0005	resolve printf

Symbol Table Merging

When linking multiple files, symbol tables are merged:

Symbol	Object File	Address	Type
main	main.o	0x401000	function
add	add.o	0x401010	function
printf	libc.a	0x401020	function
global_var	main.o	0x402000	data

Common Linker Errors

Cause	Function called but never defined
Cause	Symbol defined in multiple files
Cause	Library not found or path incorrect
Cause	External reference not satisfied
Cause	Library A needs B, B needs A

Linking Model: Static vs Dynamic

Static Linking

Example

program.o + libfoo.a → program (all code included) Larger file size, no runtime dependencies

Dynamic Linking

Example

program.o + libfoo.so → program (stub references) Smaller file, library loaded at runtime

Interview Q&A

Q: What is symbol resolution? A: Symbol resolution is the process of matching external symbol references from one object file to their definitions in other object files or libraries.

Q: What is relocation? A: Relocation is adjusting memory addresses in machine code after the final memory layout is determined. It converts relative addresses to absolute addresses.

Q: What causes "undefined reference" errors? A: A function or variable is called/used but never defined anywhere in the linked object files or libraries. The linker cannot find its definition.

Exam Focus

Revise definitions, diagrams, examples, and short-answer points for The Linker.

Interview Use

Prepare one clear explanation, one practical example, and one common mistake for this Compiler Design topic.

Search Terms

compiler-design, compiler design, compiler, design, language, processing, system, linker

Continue learning this concept

PreviousComplete Compilation Process NextThe Loader