Project 18: ELF Linker and Loader
Build a tiny static linker for a constrained subset of ELF64, so “undefined reference” stops being mysterious and relocation becomes something you can explain byte-for-byte.
Quick Reference
| Attribute | Value |
|---|---|
| Language | C (alt: Rust) |
| Difficulty | Expert |
| Time | 2-3 weeks |
| Chapters | 7 |
| Coolness | Hardcore Tech Flex |
| Portfolio Value | Deep Systems Knowledge |
Learning Objectives
By completing this project, you will:
- Master ELF64 file format: Parse headers, section headers, program headers, and understand how object files are structured
- Understand symbol tables: Parse
.symtaband.strtabsections, interpret symbol binding (local/global/weak), and symbol types - Implement symbol resolution: Apply strong/weak/common symbol rules to resolve symbols across multiple object files
- Master relocation mechanics: Understand relocation entries, compute relocation addresses, and apply fixups to machine code
- Build a section merger: Combine
.text,.rodata,.data, and.bsssections with proper alignment - Generate valid ELF output: Create well-formed ELF files that pass validation with
readelfandobjdump - Debug linking errors: Provide actionable diagnostics for undefined symbols, multiple definitions, and relocation failures
- Connect theory to practice: Understand how
ldtransforms separate compilation units into runnable executables - Prepare for systems interviews: Answer questions about linking, loading, and binary formats confidently
- Build foundation for loaders: Understand the groundwork needed for dynamic linking and runtime loading
Deep Theoretical Foundation
What is Linking and Why Does It Exist?
Linking is the process of combining multiple object files and libraries into a single executable or shared library. It exists because:
┌────────────────────────────────────────────────────────────────────────┐
│ WHY LINKING EXISTS │
├────────────────────────────────────────────────────────────────────────┤
│ │
│ THE PROBLEM: Separate Compilation │
│ ───────────────────────────────── │
│ │
│ Modern programs are built from many source files: │
│ │
│ main.c ──────┐ │
│ utils.c ─────┼──→ Compile separately ──→ Need to combine somehow │
│ network.c ───┘ │
│ │
│ Benefits of separate compilation: │
│ • Change one file → only recompile that file │
│ • Different programmers work on different files │
│ • Reuse code via libraries (libc, libm, etc.) │
│ • Manage complexity of large programs │
│ │
│ THE SOLUTION: The Linker │
│ ──────────────────────────── │
│ │
│ The linker performs three critical tasks: │
│ │
│ 1. SYMBOL RESOLUTION │
│ - Match symbol references to definitions │
│ - Example: main.c calls printf() → find printf in libc │
│ │
│ 2. RELOCATION │
│ - Assign runtime addresses to sections and symbols │
│ - Patch code/data that references those addresses │
│ │
│ 3. SECTION MERGING │
│ - Combine .text from all objects into single .text │
│ - Same for .data, .rodata, .bss │
│ │
│ Without linking, every program would be a single monolithic file! │
│ │
└────────────────────────────────────────────────────────────────────────┘
The Compilation Pipeline
Understanding where linking fits in the build process:
┌────────────────────────────────────────────────────────────────────────┐
│ COMPILATION PIPELINE │
├────────────────────────────────────────────────────────────────────────┤
│ │
│ SOURCE CODE │
│ ────────── │
│ │
│ main.c utils.c │
│ │ │ │
│ ▼ ▼ │
│ ┌───────────────┐ ┌───────────────┐ │
│ │ PREPROCESS │ │ PREPROCESS │ cpp (preprocessor) │
│ │ #include │ │ #include │ - Expands macros │
│ │ #define │ │ #define │ - Includes headers │
│ └───────┬───────┘ └───────┬───────┘ │
│ │ │ │
│ ▼ ▼ │
│ ┌───────────────┐ ┌───────────────┐ │
│ │ COMPILE │ │ COMPILE │ cc1 (compiler) │
│ │ C → ASM │ │ C → ASM │ - Semantic analysis │
│ └───────┬───────┘ └───────┬───────┘ - Optimization │
│ │ │ - Code generation │
│ ▼ ▼ │
│ ┌───────────────┐ ┌───────────────┐ │
│ │ ASSEMBLE │ │ ASSEMBLE │ as (assembler) │
│ │ ASM → OBJ │ │ ASM → OBJ │ - Machine code │
│ └───────┬───────┘ └───────┬───────┘ - Relocations │
│ │ │ - Symbol table │
│ ▼ ▼ │
│ main.o utils.o │
│ │ │ │
│ └──────────┬─────────────┘ │
│ │ │
│ ▼ │
│ ┌───────────────┐ │
│ │ LINK │ ld (linker) ← THIS PROJECT │
│ │ Resolve syms │ - Symbol resolution │
│ │ Apply relocs │ - Relocation │
│ │ Merge sections│ - Section merging │
│ └───────┬───────┘ │
│ │ │
│ ▼ │
│ a.out │
│ (executable) │
│ │
└────────────────────────────────────────────────────────────────────────┘
ELF File Format Deep Dive
The Executable and Linkable Format (ELF) is the standard binary format on Linux/Unix systems. Understanding it is essential for building a linker.
ELF File Structure Overview
┌────────────────────────────────────────────────────────────────────────┐
│ ELF FILE STRUCTURE │
├────────────────────────────────────────────────────────────────────────┤
│ │
│ Offset 0 │
│ ┌─────────────────────────────────────────────────────────────────┐ │
│ │ ELF HEADER (64 bytes) │ │
│ │ - Magic: 0x7f 'E' 'L' 'F' │ │
│ │ - Class: 32-bit or 64-bit │ │
│ │ - Endianness: little or big │ │
│ │ - Machine type: x86-64, ARM, etc. │ │
│ │ - Entry point address │ │
│ │ - Program header offset and count │ │
│ │ - Section header offset and count │ │
│ │ - Section name string table index │ │
│ ├─────────────────────────────────────────────────────────────────┤ │
│ │ PROGRAM HEADERS (if executable) │ │
│ │ - Describes segments for runtime loading │ │
│ │ - Not present in relocatable objects (.o files) │ │
│ ├─────────────────────────────────────────────────────────────────┤ │
│ │ │ │
│ │ SECTION 1: .text (code) │ │
│ │ ───────────────────────── │ │
│ │ Machine instructions │ │
│ │ │ │
│ ├─────────────────────────────────────────────────────────────────┤ │
│ │ │ │
│ │ SECTION 2: .rodata (read-only data) │ │
│ │ ─────────────────────────────────── │ │
│ │ String literals, constants │ │
│ │ │ │
│ ├─────────────────────────────────────────────────────────────────┤ │
│ │ │ │
│ │ SECTION 3: .data (initialized data) │ │
│ │ ─────────────────────────────────── │ │
│ │ Initialized global/static variables │ │
│ │ │ │
│ ├─────────────────────────────────────────────────────────────────┤ │
│ │ │ │
│ │ SECTION 4: .bss (uninitialized data) │ │
│ │ ──────────────────────────────────── │ │
│ │ Zero-initialized globals (no file space) │ │
│ │ │ │
│ ├─────────────────────────────────────────────────────────────────┤ │
│ │ │ │
│ │ SECTION 5: .symtab (symbol table) │ │
│ │ ───────────────────────────────── │ │
│ │ Array of Elf64_Sym structures │ │
│ │ │ │
│ ├─────────────────────────────────────────────────────────────────┤ │
│ │ │ │
│ │ SECTION 6: .strtab (string table) │ │
│ │ ───────────────────────────────── │ │
│ │ Null-terminated symbol names │ │
│ │ │ │
│ ├─────────────────────────────────────────────────────────────────┤ │
│ │ │ │
│ │ SECTION 7: .rela.text (relocations for .text) │ │
│ │ ───────────────────────────────────────────── │ │
│ │ Array of Elf64_Rela structures │ │
│ │ │ │
│ ├─────────────────────────────────────────────────────────────────┤ │
│ │ │ │
│ │ SECTION 8: .shstrtab (section name string table) │ │
│ │ ──────────────────────────────────────────────── │ │
│ │ Section names: ".text", ".data", etc. │ │
│ │ │ │
│ ├─────────────────────────────────────────────────────────────────┤ │
│ │ SECTION HEADER TABLE │ │
│ │ - Array of Elf64_Shdr structures │ │
│ │ - One entry per section │ │
│ │ - Describes section name, type, flags, offset, size │ │
│ └─────────────────────────────────────────────────────────────────┘ │
│ │
└────────────────────────────────────────────────────────────────────────┘
ELF Header (Elf64_Ehdr)
┌────────────────────────────────────────────────────────────────────────┐
│ ELF64 HEADER STRUCTURE │
├────────────────────────────────────────────────────────────────────────┤
│ │
│ typedef struct { │
│ unsigned char e_ident[16]; /* Magic number and other info */ │
│ uint16_t e_type; /* Object file type */ │
│ uint16_t e_machine; /* Machine type */ │
│ uint32_t e_version; /* Object file version */ │
│ uint64_t e_entry; /* Entry point virtual address */ │
│ uint64_t e_phoff; /* Program header table offset */ │
│ uint64_t e_shoff; /* Section header table offset */ │
│ uint32_t e_flags; /* Processor-specific flags */ │
│ uint16_t e_ehsize; /* ELF header size */ │
│ uint16_t e_phentsize; /* Program header entry size */ │
│ uint16_t e_phnum; /* Program header entry count */ │
│ uint16_t e_shentsize; /* Section header entry size */ │
│ uint16_t e_shnum; /* Section header entry count */ │
│ uint16_t e_shstrndx; /* Section name string table index */│
│ } Elf64_Ehdr; /* Total: 64 bytes */ │
│ │
│ e_ident breakdown: │
│ ───────────────── │
│ [0-3] Magic: 0x7f, 'E', 'L', 'F' │
│ [4] Class: 1 = 32-bit, 2 = 64-bit │
│ [5] Data: 1 = little-endian, 2 = big-endian │
│ [6] Version: 1 = current │
│ [7] OS/ABI: 0 = System V │
│ [8-15] Padding (zero) │
│ │
│ e_type values: │
│ ────────────── │
│ ET_NONE (0) - No file type │
│ ET_REL (1) - Relocatable object file (.o) ← Your input │
│ ET_EXEC (2) - Executable file ← Your output (opt) │
│ ET_DYN (3) - Shared object (.so) │
│ │
│ e_machine for x86-64: EM_X86_64 (62) │
│ │
└────────────────────────────────────────────────────────────────────────┘
Section Headers (Elf64_Shdr)
┌────────────────────────────────────────────────────────────────────────┐
│ SECTION HEADER STRUCTURE │
├────────────────────────────────────────────────────────────────────────┤
│ │
│ typedef struct { │
│ uint32_t sh_name; /* Section name (index into shstrtab) */ │
│ uint32_t sh_type; /* Section type */ │
│ uint64_t sh_flags; /* Section flags */ │
│ uint64_t sh_addr; /* Virtual address in memory */ │
│ uint64_t sh_offset; /* Offset in file */ │
│ uint64_t sh_size; /* Size of section */ │
│ uint32_t sh_link; /* Link to another section */ │
│ uint32_t sh_info; /* Additional section information */ │
│ uint64_t sh_addralign; /* Section alignment */ │
│ uint64_t sh_entsize; /* Entry size if section holds table */ │
│ } Elf64_Shdr; /* Total: 64 bytes */ │
│ │
│ Common Section Types (sh_type): │
│ ─────────────────────────────── │
│ SHT_NULL (0) - Inactive section │
│ SHT_PROGBITS (1) - Program-defined data (.text, .data, .rodata) │
│ SHT_SYMTAB (2) - Symbol table │
│ SHT_STRTAB (3) - String table │
│ SHT_RELA (4) - Relocation entries with addends │
│ SHT_NOBITS (8) - No file space (.bss) │
│ SHT_REL (9) - Relocation entries without addends │
│ │
│ Section Flags (sh_flags): │
│ ───────────────────────── │
│ SHF_WRITE (1) - Writable at runtime │
│ SHF_ALLOC (2) - Occupies memory during execution │
│ SHF_EXECINSTR (4) - Contains executable instructions │
│ │
│ Common Combinations: │
│ .text: SHF_ALLOC | SHF_EXECINSTR │
│ .rodata: SHF_ALLOC │
│ .data: SHF_ALLOC | SHF_WRITE │
│ .bss: SHF_ALLOC | SHF_WRITE │
│ │
└────────────────────────────────────────────────────────────────────────┘
Symbol Tables
Symbol tables are the core data structure for linking. They record every function and variable that might need to be referenced across object files.
Symbol Entry Structure (Elf64_Sym)
┌────────────────────────────────────────────────────────────────────────┐
│ SYMBOL TABLE ENTRY │
├────────────────────────────────────────────────────────────────────────┤
│ │
│ typedef struct { │
│ uint32_t st_name; /* Symbol name (index into strtab) */ │
│ uint8_t st_info; /* Symbol type and binding */ │
│ uint8_t st_other; /* Symbol visibility */ │
│ uint16_t st_shndx; /* Section index */ │
│ uint64_t st_value; /* Symbol value (address or offset) */ │
│ uint64_t st_size; /* Size of object */ │
│ } Elf64_Sym; /* Total: 24 bytes */ │
│ │
│ st_info breakdown (8 bits): │
│ ─────────────────────────── │
│ [0-3] Type: STT_NOTYPE(0), STT_OBJECT(1), STT_FUNC(2), │
│ STT_SECTION(3), STT_FILE(4) │
│ [4-7] Binding: STB_LOCAL(0), STB_GLOBAL(1), STB_WEAK(2) │
│ │
│ Macros: │
│ #define ELF64_ST_BIND(info) ((info) >> 4) │
│ #define ELF64_ST_TYPE(info) ((info) & 0xf) │
│ #define ELF64_ST_INFO(bind,type) (((bind) << 4) + ((type) & 0xf)) │
│ │
│ st_shndx special values: │
│ ───────────────────────── │
│ SHN_UNDEF (0) - Undefined symbol (external reference) │
│ SHN_ABS (0xfff1) - Absolute value, not relocated │
│ SHN_COMMON (0xfff2) - Common block (uninitialized tentative def) │
│ │
│ Example symbols from a typical object file: │
│ ─────────────────────────────────────────── │
│ │
│ Index Name Value Size Type Bind Ndx Description │
│ ───── ──── ───── ──── ──── ──── ─── ─────────── │
│ 0 (null) 0 0 NOTYPE LOCAL UND (always first) │
│ 1 main.c 0 0 FILE LOCAL ABS source filename │
│ 2 .text 0 0 SECTION LOCAL 1 section symbol │
│ 3 helper 0 24 FUNC LOCAL 1 static function │
│ 4 global_x 0 4 OBJECT GLOBAL 3 global variable │
│ 5 main 0 48 FUNC GLOBAL 1 main function │
│ 6 printf 0 0 NOTYPE GLOBAL UND external reference │
│ │
└────────────────────────────────────────────────────────────────────────┘
Symbol Resolution Rules
┌────────────────────────────────────────────────────────────────────────┐
│ SYMBOL RESOLUTION RULES │
├────────────────────────────────────────────────────────────────────────┤
│ │
│ When multiple object files define the same symbol, the linker must │
│ decide which definition to use. Symbols are categorized as: │
│ │
│ STRONG SYMBOLS │
│ ────────────── │
│ - Functions │
│ - Initialized global variables │
│ - Example: int x = 5; or void foo() { ... } │
│ │
│ WEAK SYMBOLS │
│ ──────────── │
│ - Uninitialized global variables (tentative definitions) │
│ - Explicitly marked weak (__attribute__((weak))) │
│ - Example: int x; (without initializer) │
│ │
│ RESOLUTION RULES: │
│ ───────────────── │
│ │
│ Rule 1: Multiple strong symbols with same name → ERROR │
│ ────────────────────────────────────────────────────── │
│ │
│ main.o: int x = 1; (strong) │
│ util.o: int x = 2; (strong) │
│ Result: ERROR: multiple definition of 'x' │
│ │
│ Rule 2: One strong + one or more weak → choose strong │
│ ──────────────────────────────────────────────────── │
│ │
│ main.o: int x = 1; (strong) │
│ util.o: int x; (weak) │
│ Result: Use main.o's definition (value = 1) │
│ │
│ Rule 3: Multiple weak symbols → choose any one (typically first) │
│ ─────────────────────────────────────────────────────────── │
│ │
│ main.o: int x; (weak) │
│ util.o: int x; (weak) │
│ Result: Use either (linker dependent, potentially size-based) │
│ │
│ COMMON SYMBOLS (SHN_COMMON): │
│ ──────────────────────────── │
│ │
│ Tentative definitions in C are placed in COMMON: │
│ - st_shndx = SHN_COMMON │
│ - st_value = alignment requirement │
│ - st_size = object size │
│ │
│ The linker allocates COMMON symbols in .bss, choosing the largest │
│ size among all definitions: │
│ │
│ main.o: int x; (COMMON, size=4) │
│ util.o: double x; (COMMON, size=8) │
│ Result: Allocate 8 bytes in .bss (DANGEROUS TYPE MISMATCH!) │
│ │
└────────────────────────────────────────────────────────────────────────┘
Relocation
Relocation is the process of adjusting symbol references once their final addresses are known.
Why Relocation is Needed
┌────────────────────────────────────────────────────────────────────────┐
│ WHY RELOCATION IS NEEDED │
├────────────────────────────────────────────────────────────────────────┤
│ │
│ When the compiler generates code, it doesn't know: │
│ - Where functions will be placed in the final executable │
│ - Where global variables will reside │
│ - The final addresses of external symbols │
│ │
│ Example: main.c calling helper() │
│ ────────────────────────────────── │
│ │
│ void helper(void); │
│ int main() { │
│ helper(); // Where is helper() located? │
│ return 0; │
│ } │
│ │
│ Generated assembly: │
│ ─────────────────── │
│ main: │
│ push rbp │
│ mov rbp, rsp │
│ call ???????? ← Address unknown at compile time! │
│ xor eax, eax │
│ pop rbp │
│ ret │
│ │
│ In the .o file, the call instruction contains: │
│ ─────────────────────────────────────────────── │
│ │
│ Offset Bytes Instruction │
│ 0x00 55 push rbp │
│ 0x01 48 89 e5 mov rbp, rsp │
│ 0x04 e8 00000000 call 0x9 ← Target is placeholder (next instr) │
│ 0x09 31 c0 xor eax, eax │
│ 0x0b 5d pop rbp │
│ 0x0c c3 ret │
│ │
│ The relocation entry says: │
│ "At offset 0x05, patch in (helper_addr - 0x09) as a 32-bit value" │
│ │
│ After linking (if helper is at 0x401100 and call is at 0x401004): │
│ ────────────────────────────────────────────────────────────────── │
│ 0x04 e8 f7100000 call 0x401100 │
│ └─ Computed: 0x401100 - 0x401009 = 0x10f7 │
│ │
└────────────────────────────────────────────────────────────────────────┘
Relocation Entry Structure (Elf64_Rela)
┌────────────────────────────────────────────────────────────────────────┐
│ RELOCATION ENTRY STRUCTURE │
├────────────────────────────────────────────────────────────────────────┤
│ │
│ typedef struct { │
│ uint64_t r_offset; /* Offset in section to patch */ │
│ uint64_t r_info; /* Symbol index and relocation type */ │
│ int64_t r_addend; /* Constant addend */ │
│ } Elf64_Rela; /* Total: 24 bytes */ │
│ │
│ r_info breakdown: │
│ ───────────────── │
│ [0-31] Relocation type (e.g., R_X86_64_PC32) │
│ [32-63] Symbol table index │
│ │
│ Macros: │
│ #define ELF64_R_SYM(info) ((info) >> 32) │
│ #define ELF64_R_TYPE(info) ((info) & 0xffffffff) │
│ #define ELF64_R_INFO(sym, type) (((uint64_t)(sym) << 32) + (type)) │
│ │
│ Example .rela.text entry: │
│ ───────────────────────── │
│ r_offset = 0x05 (patch location in .text) │
│ r_info = (6 << 32) | 4 (symbol #6, type R_X86_64_PLT32) │
│ r_addend = -4 (adjustment for PC-relative) │
│ │
│ Interpretation: "At .text+0x05, insert a 32-bit PC-relative │
│ reference to symbol #6, with addend -4" │
│ │
└────────────────────────────────────────────────────────────────────────┘
Common x86-64 Relocation Types
┌────────────────────────────────────────────────────────────────────────┐
│ X86-64 RELOCATION TYPES │
├────────────────────────────────────────────────────────────────────────┤
│ │
│ Type Value Calculation Use Case │
│ ──── ───── ─────────── ──────── │
│ R_X86_64_64 1 S + A 64-bit absolute addr │
│ R_X86_64_PC32 2 S + A - P 32-bit PC-relative │
│ R_X86_64_PLT32 4 L + A - P Call via PLT │
│ R_X86_64_32 10 S + A 32-bit absolute │
│ R_X86_64_32S 11 S + A 32-bit signed │
│ │
│ Legend: │
│ S = Symbol value (final address of symbol) │
│ A = Addend (from r_addend field) │
│ P = Patch location (section addr + r_offset) │
│ L = PLT entry address │
│ │
│ EXAMPLE 1: R_X86_64_64 (Absolute 64-bit reference) │
│ ────────────────────────────────────────────────── │
│ │
│ Used for: Data pointers, jump tables │
│ │
│ .data: │
│ .quad my_function ; pointer to function │
│ │
│ Relocation: │
│ r_offset = 0 (patch at .data+0) │
│ r_type = R_X86_64_64 │
│ r_addend = 0 │
│ │
│ Calculation: value = my_function_addr + 0 │
│ Write 64-bit value at .data+0 │
│ │
│ │
│ EXAMPLE 2: R_X86_64_PC32 (PC-relative 32-bit) │
│ ───────────────────────────────────────────── │
│ │
│ Used for: Direct function calls, RIP-relative addressing │
│ │
│ .text at 0x1000: │
│ call helper ; e8 ?? ?? ?? ?? │
│ │
│ If helper is at 0x2000: │
│ P = 0x1000 + 1 + 4 = 0x1005 (address after the instruction) │
│ S = 0x2000 │
│ A = -4 (standard for calls) │
│ Value = 0x2000 + (-4) - 0x1005 = 0xff7 (hex: f7 0f 00 00) │
│ │
│ Actually, recalculating properly: │
│ P = 0x1001 (offset of the 32-bit displacement) │
│ After instruction: 0x1005 │
│ Displacement needed: 0x2000 - 0x1005 = 0xffb │
│ But with A=-4: 0x2000 - 4 - 0x1001 = 0xffb │
│ │
└────────────────────────────────────────────────────────────────────────┘
Relocation Workflow
┌────────────────────────────────────────────────────────────────────────┐
│ RELOCATION WORKFLOW │
├────────────────────────────────────────────────────────────────────────┤
│ │
│ Step 1: Read relocation section │
│ ─────────────────────────────── │
│ │
│ For each .rela.* section: │
│ - Parse array of Elf64_Rela entries │
│ - Associated section is named (e.g., .rela.text → patches .text) │
│ │
│ Step 2: For each relocation entry │
│ ───────────────────────────────── │
│ │
│ ┌─────────────────────────────────────────────────────────────────┐ │
│ │ r_offset = 0x05 │ │
│ │ r_info = symbol_index=6, type=R_X86_64_PC32 │ │
│ │ r_addend = -4 │ │
│ └─────────────────────────────────────────────────────────────────┘ │
│ │
│ Step 3: Look up the symbol │
│ ────────────────────────── │
│ │
│ symbol = symtab[6] │
│ name = strtab + symbol.st_name → "helper" │
│ symbol_addr = resolved_symbols["helper"] → 0x401100 │
│ │
│ Step 4: Calculate patch location │
│ ───────────────────────────────── │
│ │
│ patch_addr = output_section_addr + r_offset │
│ = 0x401000 + 0x05 = 0x401005 │
│ │
│ Step 5: Compute relocation value │
│ ───────────────────────────────── │
│ │
│ For R_X86_64_PC32: │
│ value = S + A - P │
│ = 0x401100 + (-4) - 0x401005 │
│ = 0x4010fc - 0x401005 │
│ = 0xf7 (as 32-bit: 0x000000f7) │
│ │
│ Step 6: Apply the patch │
│ ─────────────────────── │
│ │
│ Write value at patch_addr (considering size and endianness): │
│ memcpy(&output_section[r_offset], &value, 4); // 32-bit LE │
│ │
│ Before: e8 00 00 00 00 │
│ After: e8 f7 00 00 00 │
│ │
└────────────────────────────────────────────────────────────────────────┘
Section Merging
When linking multiple object files, the linker must combine sections with the same name:
┌────────────────────────────────────────────────────────────────────────┐
│ SECTION MERGING │
├────────────────────────────────────────────────────────────────────────┤
│ │
│ INPUT OBJECT FILES: │
│ ─────────────────── │
│ │
│ main.o util.o │
│ ┌─────────────────┐ ┌─────────────────┐ │
│ │ .text (48 bytes)│ │ .text (96 bytes)│ │
│ │ [main code] │ │ [helper, foo] │ │
│ ├─────────────────┤ ├─────────────────┤ │
│ │ .data (8 bytes) │ │ .data (16 bytes)│ │
│ │ [initialized] │ │ [initialized] │ │
│ ├─────────────────┤ ├─────────────────┤ │
│ │ .bss (4 bytes) │ │ .bss (8 bytes) │ │
│ │ [zero-init] │ │ [zero-init] │ │
│ └─────────────────┘ └─────────────────┘ │
│ │
│ LINKER'S MERGING PROCESS: │
│ ───────────────────────── │
│ │
│ 1. Group sections by name │
│ 2. Calculate total size for each merged section │
│ 3. Assign offsets to each input section's contribution │
│ 4. Update symbol values (add section base + contribution offset) │
│ │
│ OUTPUT MERGED SECTIONS: │
│ ─────────────────────── │
│ │
│ ┌─────────────────────────────────────────────────────────────────┐ │
│ │ MERGED .text (144 bytes) │ │
│ │ ┌────────────────────────────┬─────────────────────────────────┐ │ │
│ │ │ main.o .text (48 bytes) │ util.o .text (96 bytes) │ │ │
│ │ │ Offset: 0x0 │ Offset: 0x30 (48, aligned) │ │ │
│ │ └────────────────────────────┴─────────────────────────────────┘ │ │
│ │ │ │
│ │ Symbol updates: │ │
│ │ main (main.o): 0x0 + text_base │ │
│ │ helper (util.o): 0x30 + text_base │ │
│ │ foo (util.o): 0x30 + 0x40 + text_base = 0x70 + text_base │ │
│ └─────────────────────────────────────────────────────────────────┘ │
│ │
│ ┌─────────────────────────────────────────────────────────────────┐ │
│ │ MERGED .data (24 bytes) │ │
│ │ ┌────────────────────────────┬─────────────────────────────────┐ │ │
│ │ │ main.o .data (8 bytes) │ util.o .data (16 bytes) │ │ │
│ │ │ Offset: 0x0 │ Offset: 0x8 │ │ │
│ │ └────────────────────────────┴─────────────────────────────────┘ │ │
│ └─────────────────────────────────────────────────────────────────┘ │
│ │
│ ┌─────────────────────────────────────────────────────────────────┐ │
│ │ MERGED .bss (12 bytes) │ │
│ │ ┌────────────────────────────┬─────────────────────────────────┐ │ │
│ │ │ main.o .bss (4 bytes) │ util.o .bss (8 bytes) │ │ │
│ │ │ Offset: 0x0 │ Offset: 0x8 (aligned to 8) │ │ │
│ │ └────────────────────────────┴─────────────────────────────────┘ │ │
│ └─────────────────────────────────────────────────────────────────┘ │
│ │
│ ALIGNMENT CONSIDERATIONS: │
│ ───────────────────────── │
│ │
│ Each contribution must start at an address that satisfies its │
│ original alignment requirement (sh_addralign): │
│ │
│ If util.o .text has sh_addralign = 16: │
│ main.o .text: offset 0 │
│ util.o .text: offset 48 → pad to 48 (already aligned to 16) │
│ │
│ If util.o .text had sh_addralign = 64: │
│ main.o .text: offset 0 │
│ util.o .text: offset 48 → pad to 64 (next multiple of 64) │
│ │
└────────────────────────────────────────────────────────────────────────┘
Project Specification
What You Will Build
A command-line static linker called myld that:
- Reads multiple ELF64 relocatable object files (
.o) - Parses ELF headers, section tables, symbol tables, and relocation entries
- Resolves symbols across all input files (applying strong/weak rules)
- Merges sections with proper alignment
- Applies relocations to produce correct machine code
- Writes a valid ELF output file
Milestones
┌────────────────────────────────────────────────────────────────────────┐
│ PROJECT MILESTONES │
├────────────────────────────────────────────────────────────────────────┤
│ │
│ MILESTONE A: Parse and Dump (Week 1) │
│ ───────────────────────────────────── │
│ Goal: Replicate `readelf` functionality for a subset of ELF │
│ - Parse ELF header │
│ - Parse section headers │
│ - Parse and display symbol table │
│ - Parse and display relocation entries │
│ - Match output of `readelf -S -s -r` │
│ │
│ MILESTONE B: Symbol Resolution (Week 1-2) │
│ ───────────────────────────────────────── │
│ Goal: Build global symbol table from multiple objects │
│ - Collect all symbols from all input files │
│ - Apply strong/weak resolution rules │
│ - Detect and report multiple definitions │
│ - Detect and report undefined references │
│ - Handle COMMON symbols │
│ │
│ MILESTONE C: Section Merging (Week 2) │
│ ───────────────────────────────────── │
│ Goal: Combine sections from all inputs │
│ - Merge .text, .rodata, .data, .bss │
│ - Maintain proper alignment │
│ - Update symbol values with new offsets │
│ - Build output section layout │
│ │
│ MILESTONE D: Relocation (Week 2-3) │
│ ───────────────────────────────── │
│ Goal: Apply relocations to produce correct code │
│ - Support R_X86_64_64 (absolute 64-bit) │
│ - Support R_X86_64_PC32 (PC-relative 32-bit) │
│ - Support R_X86_64_32 (absolute 32-bit) │
│ - Verify correctness with objdump │
│ │
│ MILESTONE E: ELF Output (Week 3) │
│ ───────────────────────────────── │
│ Goal: Write valid ELF file │
│ - Generate ELF header │
│ - Generate section headers │
│ - Generate .shstrtab, .strtab, .symtab │
│ - Write merged section contents │
│ - Verify with readelf │
│ │
│ MILESTONE F: Executable (Optional) │
│ ───────────────────────────────── │
│ Goal: Produce runnable executable │
│ - Add program headers │
│ - Set entry point │
│ - Support minimal _start entry point │
│ - Execute the linked program! │
│ │
└────────────────────────────────────────────────────────────────────────┘
Functional Requirements
┌────────────────────────────────────────────────────────────────────────┐
│ FUNCTIONAL REQUIREMENTS │
├────────────────────────────────────────────────────────────────────────┤
│ │
│ INPUT VALIDATION: │
│ ───────────────── │
│ - Verify ELF magic number (0x7f 'E' 'L' 'F') │
│ - Verify 64-bit format (ELFCLASS64) │
│ - Verify little-endian (ELFDATA2LSB) │
│ - Verify x86-64 architecture (EM_X86_64) │
│ - Verify relocatable type (ET_REL) │
│ - Report clear error for invalid inputs │
│ │
│ SYMBOL RESOLUTION: │
│ ────────────────── │
│ - Resolve global symbols across all object files │
│ - Apply strong/weak resolution rules correctly │
│ - Handle COMMON symbols (allocate in .bss) │
│ - Error on multiple strong definitions │
│ - Error on unresolved references (undefined symbols) │
│ - Local symbols remain file-local (not exported) │
│ │
│ SECTION MERGING: │
│ ──────────────── │
│ - Merge .text sections in input order │
│ - Merge .rodata, .data, .bss similarly │
│ - Respect alignment requirements (sh_addralign) │
│ - Update symbol values with section offsets │
│ │
│ RELOCATION: │
│ ─────────── │
│ - Support at minimum: R_X86_64_64, R_X86_64_PC32, R_X86_64_32 │
│ - Apply relocations correctly using resolved symbol values │
│ - Handle addends (r_addend) correctly │
│ - Report unsupported relocation types │
│ │
│ OUTPUT: │
│ ─────── │
│ - Valid ELF64 file readable by readelf/objdump │
│ - Correct section contents with applied relocations │
│ - Valid symbol table (.symtab) with resolved values │
│ - Valid string tables (.strtab, .shstrtab) │
│ │
│ DIAGNOSTICS: │
│ ──────────── │
│ - Show which file defines each symbol │
│ - Show which file references undefined symbols │
│ - Actionable error messages with file:symbol context │
│ │
└────────────────────────────────────────────────────────────────────────┘
Command-Line Interface
# Basic usage
$ ./myld -o output.o input1.o input2.o [input3.o ...]
# With verbose output
$ ./myld -v -o output.o main.o utils.o
# Dump mode (like readelf)
$ ./myld --dump input.o
# Symbol trace
$ ./myld --trace-symbol printf -o output.o main.o utils.o
# Link map output
$ ./myld --map output.map -o output.o main.o utils.o
Example Output
$ ./myld -v -o combined.o main.o utils.o math.o
myld: ELF Static Linker v0.1
Parsing input files...
main.o: 5 sections, 12 symbols, 4 relocations
utils.o: 4 sections, 8 symbols, 2 relocations
math.o: 3 sections, 6 symbols, 3 relocations
Symbol resolution...
Resolved: main (main.o .text+0x0)
Resolved: helper (utils.o .text+0x0)
Resolved: calculate (math.o .text+0x0)
Resolved: global_counter (main.o .data+0x0)
Resolved: config (utils.o .rodata+0x0)
Section merging...
.text: 256 bytes (main.o: 80, utils.o: 96, math.o: 80)
.rodata: 64 bytes (main.o: 32, utils.o: 32)
.data: 24 bytes (main.o: 8, utils.o: 8, math.o: 8)
.bss: 16 bytes (main.o: 8, math.o: 8)
Applying relocations...
main.o .text+0x15: R_X86_64_PC32 -> helper (resolved)
main.o .text+0x23: R_X86_64_PC32 -> calculate (resolved)
main.o .text+0x31: R_X86_64_PC32 -> global_counter (resolved)
utils.o .text+0x0a: R_X86_64_64 -> config (resolved)
... (5 more relocations)
Writing output...
Output: combined.o
Sections: 9
Symbols: 18 (6 global, 12 local)
File size: 2048 bytes
Success!
$ readelf -S combined.o
There are 9 section headers, starting at offset 0x6a0:
Section Headers:
[Nr] Name Type Addr Off Size ES Flg Lk Inf Al
[ 0] NULL 00000000 000000 000000 00 0 0 0
[ 1] .text PROGBITS 00000000 000040 000100 00 AX 0 0 16
[ 2] .rodata PROGBITS 00000000 000140 000040 00 A 0 0 8
[ 3] .data PROGBITS 00000000 000180 000018 00 WA 0 0 8
[ 4] .bss NOBITS 00000000 000198 000010 00 WA 0 0 8
[ 5] .symtab SYMTAB 00000000 000198 0001b0 18 6 9 8
[ 6] .strtab STRTAB 00000000 000348 000080 00 0 0 1
[ 7] .shstrtab STRTAB 00000000 0003c8 000040 00 0 0 1
[ 8] .rela.text RELA 00000000 000408 000090 18 5 1 8
Solution Architecture
High-Level Design
┌────────────────────────────────────────────────────────────────────────┐
│ MYLD ARCHITECTURE │
├────────────────────────────────────────────────────────────────────────┤
│ │
│ INPUT FILES │
│ ─────────── │
│ │
│ main.o utils.o math.o │
│ │ │ │ │
│ └───────┼────────┘ │
│ │ │
│ ▼ │
│ ┌─────────────────────────────────────────────────────────────────┐ │
│ │ ELF READER MODULE │ │
│ │ ───────────────────────────────────── │ │
│ │ - Parse ELF header │ │
│ │ - Parse section headers │ │
│ │ - Parse symbol table │ │
│ │ - Parse relocation entries │ │
│ │ - Load section contents into memory │ │
│ └─────────────────────────────┬───────────────────────────────────┘ │
│ │ │
│ ▼ │
│ ┌─────────────────────────────────────────────────────────────────┐ │
│ │ LINK STATE MODEL │ │
│ │ ───────────────────────────────────── │ │
│ │ │ │
│ │ ┌───────────────┐ ┌───────────────┐ ┌───────────────┐ │ │
│ │ │ Input Objects │ │ Global Symbol │ │ Merged Section│ │ │
│ │ │ Array │ │ Table │ │ Layouts │ │ │
│ │ └───────────────┘ └───────────────┘ └───────────────┘ │ │
│ │ │ │
│ └──────┬──────────────────┬──────────────────┬─────────────────────┘ │
│ │ │ │ │
│ ▼ ▼ ▼ │
│ ┌──────────────┐ ┌──────────────┐ ┌──────────────┐ │
│ │ SYMBOL │ │ SECTION │ │ RELOCATION │ │
│ │ RESOLVER │ │ MERGER │ │ ENGINE │ │
│ │ │ │ │ │ │ │
│ │ - Collect │ │ - Combine │ │ - Parse .rela│ │
│ │ - Resolve │ │ - Align │ │ - Lookup sym │ │
│ │ - Validate │ │ - Assign │ │ - Calculate │ │
│ │ │ │ offsets │ │ - Patch bytes│ │
│ └──────┬───────┘ └──────┬───────┘ └──────┬───────┘ │
│ │ │ │ │
│ └──────────────────┼──────────────────┘ │
│ │ │
│ ▼ │
│ ┌─────────────────────────────────────────────────────────────────┐ │
│ │ ELF WRITER MODULE │ │
│ │ ───────────────────────────────────── │ │
│ │ - Build ELF header │ │
│ │ - Build section headers │ │
│ │ - Build string tables │ │
│ │ - Build symbol table │ │
│ │ - Write to output file │ │
│ └─────────────────────────────┬───────────────────────────────────┘ │
│ │ │
│ ▼ │
│ combined.o │
│ │
└────────────────────────────────────────────────────────────────────────┘
Core Data Structures
/* ==================== INPUT OBJECT FILE REPRESENTATION ==================== */
/* Parsed input object file */
typedef struct {
char *filename; /* Source filename */
uint8_t *data; /* Raw file contents */
size_t size; /* File size */
/* Parsed ELF header */
Elf64_Ehdr *ehdr; /* Pointer into data */
/* Section information */
Elf64_Shdr *shdrs; /* Section header array */
uint16_t shnum; /* Number of sections */
char *shstrtab; /* Section name string table */
/* Symbol information */
Elf64_Sym *symtab; /* Symbol table */
uint32_t symcount; /* Number of symbols */
char *strtab; /* Symbol name string table */
/* Section contents (pointers into data) */
uint8_t *text_data;
size_t text_size;
uint8_t *rodata_data;
size_t rodata_size;
uint8_t *data_data;
size_t data_size;
size_t bss_size;
/* Relocation entries */
Elf64_Rela *rela_text;
uint32_t rela_text_count;
Elf64_Rela *rela_data;
uint32_t rela_data_count;
} InputObject;
/* ==================== GLOBAL SYMBOL TABLE ==================== */
/* Symbol binding strength for resolution */
typedef enum {
BIND_UNDEFINED = 0, /* Referenced but not defined */
BIND_WEAK, /* Weak definition */
BIND_COMMON, /* Common symbol (uninitialized global) */
BIND_STRONG /* Strong definition */
} SymbolStrength;
/* Resolved global symbol */
typedef struct {
char *name; /* Symbol name (owned copy) */
SymbolStrength strength; /* Resolution strength */
/* Definition source */
InputObject *defining_obj; /* Object that defines this symbol */
uint32_t sym_index; /* Index in defining object's symtab */
/* Resolved value (after section merging) */
uint64_t resolved_value; /* Final symbol value */
uint16_t resolved_section; /* Output section index */
/* For COMMON symbols */
uint64_t common_size; /* Size if COMMON */
uint64_t common_align; /* Alignment if COMMON */
} GlobalSymbol;
/* Global symbol table (hash table for fast lookup) */
typedef struct {
GlobalSymbol **buckets; /* Hash buckets */
size_t bucket_count; /* Number of buckets */
size_t symbol_count; /* Total symbols */
/* Linear list for iteration */
GlobalSymbol **symbols;
size_t capacity;
} GlobalSymbolTable;
/* ==================== MERGED SECTION LAYOUT ==================== */
/* Contribution from one input object to merged section */
typedef struct {
InputObject *source; /* Source object */
uint64_t input_offset; /* Offset within input section */
uint64_t input_size; /* Size of contribution */
uint64_t output_offset; /* Offset in merged output section */
} SectionContribution;
/* Merged output section */
typedef struct {
char *name; /* Section name (e.g., ".text") */
uint32_t type; /* SHT_PROGBITS, SHT_NOBITS, etc. */
uint64_t flags; /* SHF_ALLOC, SHF_EXECINSTR, etc. */
/* Layout information */
uint64_t total_size; /* Total merged size */
uint64_t alignment; /* Maximum alignment of contributions */
uint64_t file_offset; /* Offset in output file */
/* Merged content (NULL for .bss) */
uint8_t *data;
/* Contribution tracking */
SectionContribution *contributions;
size_t contribution_count;
size_t contribution_capacity;
} MergedSection;
/* ==================== LINKER STATE ==================== */
typedef struct {
/* Input files */
InputObject *objects;
size_t object_count;
/* Global symbol table */
GlobalSymbolTable *symtab;
/* Merged sections */
MergedSection text;
MergedSection rodata;
MergedSection data;
MergedSection bss;
/* Output configuration */
char *output_filename;
int verbose;
/* Statistics */
size_t relocations_applied;
size_t symbols_resolved;
} LinkerState;
Module Responsibilities
┌────────────────────────────────────────────────────────────────────────┐
│ MODULE RESPONSIBILITIES │
├────────────────────────────────────────────────────────────────────────┤
│ │
│ elf_reader.c │
│ ──────────── │
│ - read_elf_file(filename) → InputObject │
│ - validate_elf_header(ehdr) → bool │
│ - parse_section_headers(obj) │
│ - parse_symbol_table(obj) │
│ - parse_relocations(obj) │
│ - get_section_by_name(obj, name) → Elf64_Shdr* │
│ - get_symbol_name(obj, sym) → char* │
│ │
│ symbol_resolver.c │
│ ───────────────── │
│ - create_global_symtab() → GlobalSymbolTable* │
│ - add_symbols_from_object(symtab, obj) │
│ - resolve_symbol(symtab, name) → GlobalSymbol* │
│ - check_undefined_symbols(symtab) → error list │
│ - allocate_common_symbols(symtab, bss) │
│ - get_symbol_strength(sym) → SymbolStrength │
│ │
│ section_merger.c │
│ ──────────────── │
│ - init_merged_section(name, type, flags) → MergedSection │
│ - add_contribution(section, obj, input_section) │
│ - finalize_layout(section) → total_size │
│ - get_contribution_offset(section, obj) → offset │
│ - merge_section_data(section, output_buffer) │
│ │
│ relocation_engine.c │
│ ─────────────────── │
│ - apply_relocations(state, merged_section) │
│ - compute_relocation(type, S, A, P) → value │
│ - patch_bytes(data, offset, value, size) │
│ - is_pc_relative(type) → bool │
│ - relocation_type_name(type) → string │
│ │
│ elf_writer.c │
│ ──────────── │
│ - write_elf_file(state, filename) │
│ - build_elf_header(state) → Elf64_Ehdr │
│ - build_section_headers(state) → Elf64_Shdr[] │
│ - build_symbol_table(state) → (Elf64_Sym[], strtab) │
│ - build_shstrtab(state) → string table │
│ - calculate_file_layout(state) │
│ │
│ main.c │
│ ────── │
│ - Parse command line arguments │
│ - Initialize linker state │
│ - Orchestrate linking phases │
│ - Handle errors and diagnostics │
│ │
└────────────────────────────────────────────────────────────────────────┘
Implementation Guide
The Core Question You’re Answering
“When I compile
main.candutils.cseparately and then link them, how does the linker know wherehelper()is whenmain()calls it, and how does thecallinstruction get the right address?”
This project reveals the complete answer:
- Each
.ofile has a symbol table listing what it defines and what it references - The linker collects all symbols and resolves references to definitions
- Relocation entries tell the linker exactly where to patch and how to compute the address
- After linking, every
call,mov, andleainstruction has the correct target address
Concepts You Must Understand First
Before starting this project, ensure you understand these concepts:
| Concept | Why It Matters | Where to Learn |
|---|---|---|
| C compilation process | You need to understand what .o files contain |
CS:APP 7.1-7.2 |
| Binary file structure | You’ll be reading/writing binary formats | Any systems book |
| Pointer arithmetic | Essential for navigating ELF structures | K&R C, any C book |
| Endianness | ELF encodes multi-byte values | CS:APP 2.1.3 |
| x86-64 addressing modes | Understand PC-relative vs absolute | CS:APP 3.4-3.5 |
| Hash tables | Efficient symbol lookup | Data structures course |
Self-assessment questions:
- What is the difference between a relocatable object file and an executable?
- Why does
int x;(without initializer) create a “weak” symbol? - What does the assembler put in the
callinstruction when the target function is in another file? - Why are function calls on x86-64 typically PC-relative rather than absolute?
Questions to Guide Your Design
Work through these questions BEFORE writing code:
ELF Parsing:
- How will you map the file into memory? (
mmapvsmalloc+read) - How do you navigate from the ELF header to a specific section’s data?
- How do you find the section that a symbol belongs to?
Symbol Resolution:
- What data structure will you use for the global symbol table? (hash table? list?)
- How do you handle the case where two files both define
int x = 5;? - How do you track which object file provided the winning definition?
Section Merging:
- In what order will you process sections? Does order matter?
- How do you handle alignment requirements between contributions?
- When do you update symbol values - during or after merging?
Relocation:
- How do you find the symbol referenced by a relocation entry?
- For PC-relative relocations, what is “P” exactly?
- How do you verify your relocation calculations are correct?
Thinking Exercise
Before writing any code, work through this example by hand:
Given two object files:
main.o:
Symbols:
main (FUNC, GLOBAL, .text+0x0, size=32)
printf (NOTYPE, GLOBAL, UNDEF)
helper (NOTYPE, GLOBAL, UNDEF)
.text (32 bytes):
0x00: 55 push rbp
0x01: 48 89 e5 mov rbp, rsp
0x04: e8 00 00 00 00 call helper (RELOC: R_X86_64_PC32, sym=helper, addend=-4)
0x09: 89 c7 mov edi, eax
0x0b: e8 00 00 00 00 call printf (RELOC: R_X86_64_PLT32, sym=printf, addend=-4)
0x10: ...
util.o:
Symbols:
helper (FUNC, GLOBAL, .text+0x0, size=20)
result (OBJECT, GLOBAL, .data+0x0, size=4)
.text (20 bytes):
0x00: 55 push rbp
0x01: 48 89 e5 mov rbp, rsp
0x04: 8b 05 00 00 00 00 mov eax, [rip + result] (RELOC: R_X86_64_PC32, sym=result, addend=-4)
0x0a: ...
.data (4 bytes):
0x00: 2a 00 00 00 (int result = 42)
Exercise Questions:
-
Symbol Collection: List all symbols from both files. Which are defined? Which are undefined?
-
Resolution: What happens to each undefined symbol? What if
printfremains undefined? - Section Merging: If merged
.textstarts at offset 0:- Where does
main.o’s.textcontribution start? - Where does
util.o’s.textcontribution start? - What are the final values of symbols
mainandhelper?
- Where does
- Relocation: For the
call helperinstruction inmain.o:- What is the patch location (P)?
- What is the symbol value (S)?
- What is the addend (A)?
- What 32-bit value gets written?
- Result Check: After linking, what bytes are at the
call helperlocation?
Hints in Layers
If you’re stuck, reveal hints one at a time:
Hint 1: Reading ELF Files
Use mmap to map the file into memory, then cast pointers to ELF structures:
#include <sys/mman.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <elf.h>
InputObject *read_elf_file(const char *filename) {
int fd = open(filename, O_RDONLY);
if (fd < 0) {
perror("open");
return NULL;
}
struct stat st;
fstat(fd, &st);
uint8_t *data = mmap(NULL, st.st_size, PROT_READ, MAP_PRIVATE, fd, 0);
close(fd);
if (data == MAP_FAILED) {
perror("mmap");
return NULL;
}
InputObject *obj = calloc(1, sizeof(InputObject));
obj->filename = strdup(filename);
obj->data = data;
obj->size = st.st_size;
/* Cast to ELF header */
obj->ehdr = (Elf64_Ehdr *)data;
/* Validate magic number */
if (memcmp(obj->ehdr->e_ident, ELFMAG, SELFMAG) != 0) {
fprintf(stderr, "%s: not an ELF file\n", filename);
return NULL;
}
/* Get section header table */
obj->shdrs = (Elf64_Shdr *)(data + obj->ehdr->e_shoff);
obj->shnum = obj->ehdr->e_shnum;
/* Get section name string table */
Elf64_Shdr *shstrtab_hdr = &obj->shdrs[obj->ehdr->e_shstrndx];
obj->shstrtab = (char *)(data + shstrtab_hdr->sh_offset);
return obj;
}
/* Helper to get section by name */
Elf64_Shdr *get_section_by_name(InputObject *obj, const char *name) {
for (int i = 0; i < obj->shnum; i++) {
char *sec_name = obj->shstrtab + obj->shdrs[i].sh_name;
if (strcmp(sec_name, name) == 0) {
return &obj->shdrs[i];
}
}
return NULL;
}
Hint 2: Parsing Symbol Tables
Symbol tables have a specific structure. Find .symtab and .strtab:
void parse_symbol_table(InputObject *obj) {
/* Find .symtab section */
Elf64_Shdr *symtab_hdr = NULL;
Elf64_Shdr *strtab_hdr = NULL;
for (int i = 0; i < obj->shnum; i++) {
char *name = obj->shstrtab + obj->shdrs[i].sh_name;
if (strcmp(name, ".symtab") == 0) {
symtab_hdr = &obj->shdrs[i];
} else if (strcmp(name, ".strtab") == 0) {
strtab_hdr = &obj->shdrs[i];
}
}
if (!symtab_hdr || !strtab_hdr) {
fprintf(stderr, "%s: missing symbol table\n", obj->filename);
return;
}
/* Parse symbol table */
obj->symtab = (Elf64_Sym *)(obj->data + symtab_hdr->sh_offset);
obj->symcount = symtab_hdr->sh_size / sizeof(Elf64_Sym);
obj->strtab = (char *)(obj->data + strtab_hdr->sh_offset);
/* Iterate symbols */
for (uint32_t i = 0; i < obj->symcount; i++) {
Elf64_Sym *sym = &obj->symtab[i];
char *name = obj->strtab + sym->st_name;
int bind = ELF64_ST_BIND(sym->st_info);
int type = ELF64_ST_TYPE(sym->st_info);
printf("Symbol %d: name=%s, bind=%d, type=%d, shndx=%d, value=0x%lx\n",
i, name, bind, type, sym->st_shndx, sym->st_value);
}
}
Understanding symbol attributes:
/* Symbol binding determines visibility */
#define STB_LOCAL 0 /* Not visible outside object file */
#define STB_GLOBAL 1 /* Visible to all objects */
#define STB_WEAK 2 /* Like global, but lower precedence */
/* Symbol type indicates what the symbol represents */
#define STT_NOTYPE 0 /* Type not specified */
#define STT_OBJECT 1 /* Data object (variable) */
#define STT_FUNC 2 /* Function */
#define STT_SECTION 3 /* Section */
#define STT_FILE 4 /* Source file name */
/* Special section indices */
#define SHN_UNDEF 0 /* Undefined symbol */
#define SHN_ABS 0xfff1 /* Absolute value */
#define SHN_COMMON 0xfff2 /* Common block */
Hint 3: Symbol Resolution Algorithm
Implement strong/weak resolution rules:
SymbolStrength get_symbol_strength(Elf64_Sym *sym) {
if (sym->st_shndx == SHN_UNDEF) {
return BIND_UNDEFINED;
}
if (sym->st_shndx == SHN_COMMON) {
return BIND_COMMON;
}
int bind = ELF64_ST_BIND(sym->st_info);
if (bind == STB_WEAK) {
return BIND_WEAK;
}
/* STB_GLOBAL with definition = strong */
return BIND_STRONG;
}
int add_symbol(GlobalSymbolTable *table, InputObject *obj, uint32_t sym_idx) {
Elf64_Sym *sym = &obj->symtab[sym_idx];
char *name = obj->strtab + sym->st_name;
/* Skip local symbols */
if (ELF64_ST_BIND(sym->st_info) == STB_LOCAL) {
return 0;
}
/* Skip empty names */
if (name[0] == '\0') {
return 0;
}
SymbolStrength new_strength = get_symbol_strength(sym);
/* Look up existing symbol */
GlobalSymbol *existing = lookup_symbol(table, name);
if (existing == NULL) {
/* First occurrence - add it */
GlobalSymbol *gsym = calloc(1, sizeof(GlobalSymbol));
gsym->name = strdup(name);
gsym->strength = new_strength;
gsym->defining_obj = obj;
gsym->sym_index = sym_idx;
if (new_strength == BIND_COMMON) {
gsym->common_size = sym->st_size;
gsym->common_align = sym->st_value; /* COMMON uses st_value for align */
}
insert_symbol(table, gsym);
return 0;
}
/* Symbol exists - apply resolution rules */
if (new_strength == BIND_UNDEFINED) {
/* Reference only - no conflict */
return 0;
}
if (existing->strength == BIND_STRONG && new_strength == BIND_STRONG) {
/* Rule 1: Multiple strong definitions = ERROR */
fprintf(stderr, "error: multiple definition of '%s'\n", name);
fprintf(stderr, " first defined in: %s\n", existing->defining_obj->filename);
fprintf(stderr, " also defined in: %s\n", obj->filename);
return -1;
}
if (new_strength > existing->strength) {
/* New definition is stronger - replace */
existing->strength = new_strength;
existing->defining_obj = obj;
existing->sym_index = sym_idx;
}
/* Handle COMMON - take largest size */
if (existing->strength == BIND_COMMON && new_strength == BIND_COMMON) {
if (sym->st_size > existing->common_size) {
existing->common_size = sym->st_size;
}
if (sym->st_value > existing->common_align) {
existing->common_align = sym->st_value;
}
}
return 0;
}
Hint 4: Section Merging Implementation
Merge sections with proper alignment:
void add_contribution(MergedSection *section, InputObject *obj,
Elf64_Shdr *input_shdr, uint8_t *input_data) {
/* Expand contribution array if needed */
if (section->contribution_count >= section->contribution_capacity) {
section->contribution_capacity = section->contribution_capacity * 2 + 4;
section->contributions = realloc(section->contributions,
section->contribution_capacity * sizeof(SectionContribution));
}
SectionContribution *contrib = §ion->contributions[section->contribution_count];
contrib->source = obj;
contrib->input_size = input_shdr->sh_size;
/* Calculate aligned offset */
uint64_t align = input_shdr->sh_addralign;
if (align == 0) align = 1;
/* Round current size up to alignment boundary */
uint64_t aligned_offset = (section->total_size + align - 1) & ~(align - 1);
contrib->output_offset = aligned_offset;
/* Update total size */
section->total_size = aligned_offset + input_shdr->sh_size;
/* Track maximum alignment */
if (align > section->alignment) {
section->alignment = align;
}
section->contribution_count++;
}
void merge_section_data(MergedSection *section) {
if (section->type == SHT_NOBITS) {
/* .bss has no data */
return;
}
section->data = calloc(1, section->total_size);
for (size_t i = 0; i < section->contribution_count; i++) {
SectionContribution *contrib = §ion->contributions[i];
InputObject *obj = contrib->source;
/* Find the input section data */
Elf64_Shdr *input_shdr = /* ... find matching section ... */;
uint8_t *input_data = obj->data + input_shdr->sh_offset;
/* Copy to output location */
memcpy(section->data + contrib->output_offset,
input_data, contrib->input_size);
}
}
/* Update symbol values after merging */
void update_symbol_values(LinkerState *state) {
for (size_t i = 0; i < state->symtab->symbol_count; i++) {
GlobalSymbol *gsym = state->symtab->symbols[i];
if (gsym->strength == BIND_UNDEFINED) {
continue; /* Still undefined */
}
InputObject *obj = gsym->defining_obj;
Elf64_Sym *sym = &obj->symtab[gsym->sym_index];
/* Find which merged section this symbol belongs to */
char *sec_name = obj->shstrtab + obj->shdrs[sym->st_shndx].sh_name;
MergedSection *merged = get_merged_section_by_name(state, sec_name);
/* Find the contribution from this object */
SectionContribution *contrib = find_contribution(merged, obj);
/* New value = contribution offset + original offset within section */
gsym->resolved_value = contrib->output_offset + sym->st_value;
}
}
Hint 5: Relocation Engine
Apply relocations with correct formulas:
void apply_relocations(LinkerState *state, MergedSection *section,
const char *rela_name) {
for (size_t i = 0; i < state->object_count; i++) {
InputObject *obj = &state->objects[i];
/* Find relocation section for this object */
Elf64_Shdr *rela_shdr = get_section_by_name(obj, rela_name);
if (!rela_shdr) continue;
Elf64_Rela *relas = (Elf64_Rela *)(obj->data + rela_shdr->sh_offset);
size_t rela_count = rela_shdr->sh_size / sizeof(Elf64_Rela);
/* Find this object's contribution to the section */
SectionContribution *contrib = find_contribution(section, obj);
for (size_t j = 0; j < rela_count; j++) {
Elf64_Rela *rela = &relas[j];
uint32_t sym_idx = ELF64_R_SYM(rela->r_info);
uint32_t type = ELF64_R_TYPE(rela->r_info);
/* Look up the symbol */
Elf64_Sym *sym = &obj->symtab[sym_idx];
char *sym_name = obj->strtab + sym->st_name;
GlobalSymbol *gsym = lookup_symbol(state->symtab, sym_name);
if (!gsym || gsym->strength == BIND_UNDEFINED) {
fprintf(stderr, "error: undefined reference to '%s'\n", sym_name);
continue;
}
/* Calculate relocation values */
uint64_t S = gsym->resolved_value; /* Symbol value */
int64_t A = rela->r_addend; /* Addend */
uint64_t P = contrib->output_offset + rela->r_offset; /* Patch location */
uint64_t value;
int size;
switch (type) {
case R_X86_64_64:
/* S + A (64-bit absolute) */
value = S + A;
size = 8;
break;
case R_X86_64_PC32:
case R_X86_64_PLT32:
/* S + A - P (32-bit PC-relative) */
value = S + A - P;
size = 4;
/* Verify it fits in 32 bits signed */
if ((int64_t)value != (int32_t)value) {
fprintf(stderr, "error: relocation overflow for '%s'\n", sym_name);
}
break;
case R_X86_64_32:
case R_X86_64_32S:
/* S + A (32-bit absolute) */
value = S + A;
size = 4;
break;
default:
fprintf(stderr, "error: unsupported relocation type %d\n", type);
continue;
}
/* Patch the bytes (little-endian) */
memcpy(section->data + P, &value, size);
if (state->verbose) {
printf(" Reloc: %s+0x%lx: %s %s -> 0x%lx\n",
section->name, P,
relocation_type_name(type), sym_name, value);
}
}
}
}
const char *relocation_type_name(uint32_t type) {
switch (type) {
case R_X86_64_64: return "R_X86_64_64";
case R_X86_64_PC32: return "R_X86_64_PC32";
case R_X86_64_PLT32: return "R_X86_64_PLT32";
case R_X86_64_32: return "R_X86_64_32";
case R_X86_64_32S: return "R_X86_64_32S";
default: return "UNKNOWN";
}
}
The Interview Questions They’ll Ask
After completing this project, you’ll be ready for these common interview questions:
1. “Walk me through what happens when you compile and link two C files.”
Expected answer:
- Each file compiled to
.o(relocatable object) with unresolved symbols - Linker collects symbols, resolves references to definitions
- Sections merged (all
.textcombined, etc.) - Relocations applied to patch addresses
- Output is executable with correct addresses
2. “What’s the difference between a symbol and a relocation?”
Expected answer:
- Symbol: Named entity (function, variable) with attributes (value, type, binding)
- Relocation: Instruction to patch code/data when final address is known
- Symbols define names; relocations describe how to use them
- Example:
printfis a symbol;call printfgenerates a relocation
3. “Explain strong vs weak symbols and what happens with conflicts.”
Expected answer:
- Strong: functions, initialized globals
- Weak: uninitialized globals (tentative definitions)
- Two strong symbols with same name = linker error
- Strong + weak = strong wins
- Multiple weak = any one chosen (dangerous!)
4. “Why are function calls on x86-64 usually PC-relative?”
Expected answer:
- 32-bit displacement fits most cases (+-2GB range)
- Smaller instruction encoding than 64-bit absolute
- Position-independent: code can be loaded anywhere
- RIP-relative addressing is natural for x86-64
5. “What is a relocation addend and why is it needed?”
Expected answer:
- Constant adjustment added to computed address
- For
call: addend is -4 because displacement is from end of instruction - For struct fields: addend is field offset
- Allows one relocation to reference different offsets from a symbol
6. “How would you debug an ‘undefined reference’ error?”
Expected answer:
- Check if symbol is defined anywhere (
nm -A *.o | grep symbol) - Verify library is being linked (
-lflags) - Check symbol visibility (static vs extern)
- Verify spelling and name mangling (C++ needs
extern "C") - Use
readelf -sto inspect symbol tables
Testing Strategy
Test Cases by Milestone
┌────────────────────────────────────────────────────────────────────────┐
│ TESTING STRATEGY │
├────────────────────────────────────────────────────────────────────────┤
│ │
│ MILESTONE A: ELF Parsing │
│ ──────────────────────── │
│ │
│ Test: Compare output with readelf │
│ │
│ $ gcc -c test.c -o test.o │
│ $ readelf -S test.o > expected_sections.txt │
│ $ ./myld --dump-sections test.o > actual_sections.txt │
│ $ diff expected_sections.txt actual_sections.txt │
│ │
│ $ readelf -s test.o > expected_symbols.txt │
│ $ ./myld --dump-symbols test.o > actual_symbols.txt │
│ $ diff expected_symbols.txt actual_symbols.txt │
│ │
│ MILESTONE B: Symbol Resolution │
│ ────────────────────────────── │
│ │
│ Test Case: Strong/strong conflict │
│ ───────────────────────────────── │
│ strong1.c: int x = 1; │
│ strong2.c: int x = 2; │
│ Expected: Error "multiple definition of 'x'" │
│ │
│ Test Case: Strong/weak resolution │
│ ──────────────────────────────── │
│ strong.c: int x = 42; │
│ weak.c: int x; /* tentative */ │
│ Expected: Use strong definition (value 42) │
│ │
│ Test Case: Undefined reference │
│ ─────────────────────────────── │
│ main.c: extern void foo(void); int main() { foo(); return 0; } │
│ /* foo.c not provided */ │
│ Expected: Error "undefined reference to 'foo'" │
│ │
│ MILESTONE C: Section Merging │
│ ──────────────────────────── │
│ │
│ Test: Verify merged section sizes │
│ ────────────────────────────────── │
│ main.c: int main() { return helper(); } /* 32 bytes */│
│ util.c: int helper() { return 42; } /* 24 bytes */│
│ Expected: .text size >= 56 bytes (with alignment) │
│ │
│ Test: Verify symbol offsets │
│ ─────────────────────────────── │
│ After merging: │
│ - main should be at offset 0 │
│ - helper should be at offset >= 32 (aligned) │
│ │
│ MILESTONE D: Relocation │
│ ──────────────────────── │
│ │
│ Test: Verify call instruction patching │
│ ────────────────────────────────────── │
│ $ ./myld -o combined.o main.o util.o │
│ $ objdump -d combined.o | grep "call.*helper" │
│ Expected: call should show correct target address │
│ │
│ Test: Verify data relocations │
│ ────────────────────────────── │
│ data.c: int *ptr = &x; (pointer to global) │
│ Expected: ptr contains correct address of x │
│ │
│ MILESTONE E: ELF Output │
│ ──────────────────────── │
│ │
│ Test: Output validation with readelf │
│ ───────────────────────────────────── │
│ $ ./myld -o output.o input1.o input2.o │
│ $ readelf -a output.o # Should parse without errors │
│ $ objdump -d output.o # Should disassemble correctly │
│ │
└────────────────────────────────────────────────────────────────────────┘
Automated Test Script
#!/bin/bash
# test_myld.sh - Automated test suite for myld
MYLD="./myld"
PASS=0
FAIL=0
# Test helper function
test_case() {
local name=$1
local expected=$2
local actual=$3
if [ "$expected" = "$actual" ]; then
echo "PASS: $name"
((PASS++))
else
echo "FAIL: $name"
echo " Expected: $expected"
echo " Actual: $actual"
((FAIL++))
fi
}
# Test 1: Parse single object file
echo "=== Test 1: Parse single object ==="
cat > test1.c << 'EOF'
int global_var = 42;
int func(int x) { return x + global_var; }
EOF
gcc -c test1.c -o test1.o
$MYLD --dump-symbols test1.o | grep -c "func" > /dev/null
test_case "Find func symbol" "0" "$?"
# Test 2: Symbol resolution (strong/strong conflict)
echo "=== Test 2: Multiple strong definitions ==="
cat > multi1.c << 'EOF'
int x = 1;
EOF
cat > multi2.c << 'EOF'
int x = 2;
EOF
gcc -c multi1.c -o multi1.o
gcc -c multi2.c -o multi2.o
$MYLD -o multi.o multi1.o multi2.o 2>&1 | grep -q "multiple definition"
test_case "Detect multiple definition" "0" "$?"
# Test 3: Undefined reference
echo "=== Test 3: Undefined reference ==="
cat > undef.c << 'EOF'
extern void unknown_func(void);
void test(void) { unknown_func(); }
EOF
gcc -c undef.c -o undef.o
$MYLD -o undef_out.o undef.o 2>&1 | grep -q "undefined"
test_case "Detect undefined reference" "0" "$?"
# Test 4: Successful link
echo "=== Test 4: Successful link ==="
cat > main4.c << 'EOF'
extern int helper(int);
int main(void) { return helper(5); }
EOF
cat > util4.c << 'EOF'
int helper(int x) { return x * 2; }
EOF
gcc -c main4.c -o main4.o
gcc -c util4.c -o util4.o
$MYLD -o linked4.o main4.o util4.o
readelf -S linked4.o > /dev/null 2>&1
test_case "Produce valid ELF" "0" "$?"
# Test 5: Relocation correctness
echo "=== Test 5: Relocation correctness ==="
objdump -d linked4.o | grep -q "call"
test_case "Call instruction present" "0" "$?"
# Summary
echo ""
echo "=== Summary ==="
echo "Passed: $PASS"
echo "Failed: $FAIL"
# Cleanup
rm -f test1.c test1.o multi1.c multi2.c multi1.o multi2.o multi.o
rm -f undef.c undef.o undef_out.o
rm -f main4.c util4.c main4.o util4.o linked4.o
exit $FAIL
Common Pitfalls and Debugging
Pitfall 1: Endianness Confusion
┌────────────────────────────────────────────────────────────────────────┐
│ BUG: Reading multi-byte values incorrectly │
├────────────────────────────────────────────────────────────────────────┤
│ │
│ Symptom: Parsed values are nonsensical (e.g., section size = 2^40) │
│ │
│ Cause: ELF is little-endian on x86-64, but you might be: │
│ - Manually reading bytes in wrong order │
│ - Using wrong struct packing │
│ │
│ Wrong: │
│ uint32_t val = (data[0] << 24) | (data[1] << 16) | │
│ (data[2] << 8) | data[3]; // Big-endian! │
│ │
│ Right: │
│ /* Just cast - x86 is little-endian like ELF */ │
│ uint32_t val = *(uint32_t *)data; │
│ │
│ Or use ELF header structures directly: │
│ Elf64_Ehdr *ehdr = (Elf64_Ehdr *)data; │
│ uint16_t shnum = ehdr->e_shnum; // Correct! │
│ │
│ Debug: Print raw bytes and expected values │
│ printf("Raw: %02x %02x %02x %02x, Parsed: %u\n", │
│ data[0], data[1], data[2], data[3], val); │
│ │
└────────────────────────────────────────────────────────────────────────┘
Pitfall 2: Section Index Confusion
┌────────────────────────────────────────────────────────────────────────┐
│ BUG: Using wrong section index for symbols │
├────────────────────────────────────────────────────────────────────────┤
│ │
│ Symptom: Symbols have wrong values or reference wrong sections │
│ │
│ Cause: Symbol st_shndx is index in THAT file's section table, │
│ not the output file's table │
│ │
│ Wrong: │
│ uint64_t sym_value = sym->st_value; // Offset in input section │
│ /* Use directly as output address - WRONG! */ │
│ │
│ Right: │
│ /* Map input section index to merged section */ │
│ Elf64_Shdr *input_sec = &obj->shdrs[sym->st_shndx]; │
│ char *sec_name = obj->shstrtab + input_sec->sh_name; │
│ MergedSection *merged = get_merged_by_name(sec_name); │
│ /* Find contribution from this object */ │
│ SectionContribution *contrib = find_contrib(merged, obj); │
│ /* Final value = contribution base + original offset */ │
│ uint64_t final_value = contrib->output_offset + sym->st_value; │
│ │
│ Debug: Print section mapping │
│ printf("Symbol %s: input_sec=%s(%d), orig_val=0x%lx, final=0x%lx\n",│
│ sym_name, sec_name, sym->st_shndx, sym->st_value, final); │
│ │
└────────────────────────────────────────────────────────────────────────┘
Pitfall 3: PC-Relative Relocation Off-by-4
┌────────────────────────────────────────────────────────────────────────┐
│ BUG: Call target is 4 bytes off │
├────────────────────────────────────────────────────────────────────────┤
│ │
│ Symptom: Disassembly shows call to wrong address (off by 4) │
│ │
│ Cause: Forgetting that PC-relative is from END of instruction │
│ │
│ x86-64 call instruction: │
│ ┌────────┬────────────────────────────────────────┐ │
│ │ e8 │ 32-bit displacement (little-endian) │ │
│ │ 1 byte │ 4 bytes │ │
│ └────────┴────────────────────────────────────────┘ │
│ │
│ The displacement is relative to the NEXT instruction's address: │
│ target = (address_after_call) + displacement │
│ target = (P + 4) + displacement │
│ │
│ So: displacement = target - (P + 4) = S - P - 4 │
│ │
│ The r_addend of -4 handles this: │
│ value = S + A - P = S + (-4) - P = S - P - 4 ✓ │
│ │
│ Wrong (ignoring addend): │
│ value = S - P; // Will be 4 bytes off! │
│ │
│ Right: │
│ value = S + A - P; // A = -4 for calls │
│ │
│ Debug: Verify with objdump │
│ $ objdump -d output.o │
│ Look for: e8 XX XX XX XX call <target> │
│ Compute: does instruction_addr + 5 + displacement == target? │
│ │
└────────────────────────────────────────────────────────────────────────┘
Pitfall 4: Local vs Global Symbol Handling
┌────────────────────────────────────────────────────────────────────────┐
│ BUG: Wrong symbol resolved for local symbol │
├────────────────────────────────────────────────────────────────────────┤
│ │
│ Symptom: static function calls wrong function │
│ │
│ Cause: Local symbols (STB_LOCAL) should NOT be in global table │
│ Each file's local "helper" is different! │
│ │
│ file1.c: static int helper(void) { return 1; } │
│ file2.c: static int helper(void) { return 2; } │
│ int main(void) { return helper(); } │
│ │
│ Wrong: Put both "helper" symbols in global table, second one wins │
│ file2.c's main() ends up calling file1.c's helper! │
│ │
│ Right: │
│ - Only add GLOBAL and WEAK symbols to global table │
│ - For LOCAL symbol relocations, look up in THAT file's symtab only │
│ │
│ int resolve_relocation_symbol(InputObject *obj, uint32_t sym_idx) { │
│ Elf64_Sym *sym = &obj->symtab[sym_idx]; │
│ int bind = ELF64_ST_BIND(sym->st_info); │
│ │
│ if (bind == STB_LOCAL) { │
│ /* Resolve within THIS object only */ │
│ return resolve_local(obj, sym); │
│ } else { │
│ /* Look up in global table */ │
│ char *name = obj->strtab + sym->st_name; │
│ return lookup_global(global_symtab, name); │
│ } │
│ } │
│ │
└────────────────────────────────────────────────────────────────────────┘
Pitfall 5: Alignment Padding Errors
┌────────────────────────────────────────────────────────────────────────┐
│ BUG: Section contributions overlap or have gaps │
├────────────────────────────────────────────────────────────────────────┤
│ │
│ Symptom: objdump shows garbage instructions, data corrupted │
│ │
│ Cause: Not padding to alignment boundary between contributions │
│ │
│ Example: │
│ file1.o .text: 18 bytes, align=1 │
│ file2.o .text: 32 bytes, align=16 │
│ │
│ Wrong: │
│ file1 at offset 0, size 18 → ends at 18 │
│ file2 at offset 18, size 32 → ERROR: 18 is not 16-aligned! │
│ │
│ Right: │
│ file1 at offset 0, size 18 → ends at 18 │
│ (pad 14 bytes to reach 32) │
│ file2 at offset 32, size 32 → ends at 64 ✓ │
│ │
│ Code fix: │
│ uint64_t next_offset = current_size; │
│ uint64_t align = input_shdr->sh_addralign; │
│ if (align > 1) { │
│ /* Round up to alignment boundary */ │
│ next_offset = (next_offset + align - 1) & ~(align - 1); │
│ } │
│ contrib->output_offset = next_offset; │
│ current_size = next_offset + input_shdr->sh_size; │
│ │
└────────────────────────────────────────────────────────────────────────┘
Extensions and Challenges
Beginner Extensions
- Link map output: Generate a file showing where each symbol and section ended up
- Symbol tracing:
--trace-symbol fooshows every reference and definition offoo - Version display: Show each input file’s symbols with their resolution status
- Section statistics: Report sizes, alignment waste, and contribution counts
Intermediate Extensions
- More relocation types: Support R_X86_64_GOTPCREL, R_X86_64_REX_GOTPCRELX
- Archive support: Link against
.astatic library files (parse ar format) - Executable output: Generate runnable ELF with program headers and entry point
- Discard sections: Support
-gc-sectionsto remove unused code/data
Advanced Extensions
- Dynamic linking preparation: Generate
.pltand.gotsections - LTO integration: Handle LLVM bitcode sections
- Incremental linking: Only re-link changed objects
- Parallel relocation: Apply relocations in parallel with thread pool
Executable Extension Detail
┌────────────────────────────────────────────────────────────────────────┐
│ CREATING EXECUTABLES │
├────────────────────────────────────────────────────────────────────────┤
│ │
│ To produce a runnable executable instead of a relocatable object: │
│ │
│ 1. Add program headers (Elf64_Phdr) │
│ - PT_LOAD for .text segment (RX permissions) │
│ - PT_LOAD for .data segment (RW permissions) │
│ │
│ 2. Assign virtual addresses │
│ - Text segment: 0x400000 (typical Linux default) │
│ - Data segment: 0x600000 or after text │
│ │
│ 3. Set entry point │
│ - e_entry = address of _start or main │
│ │
│ 4. Change ELF type │
│ - e_type = ET_EXEC │
│ │
│ 5. Minimal _start for testing: │
│ │
│ _start: │
│ call main │
│ mov edi, eax ; exit code = main return value │
│ mov eax, 60 ; sys_exit │
│ syscall │
│ │
└────────────────────────────────────────────────────────────────────────┘
Books That Will Help
| Topic | Book | Chapter/Section |
|---|---|---|
| Linking fundamentals | CS:APP 3rd Ed | Chapter 7 “Linking” |
| Object file formats | CS:APP 3rd Ed | Chapter 7.4 “Relocatable Object Files” |
| Symbol resolution | CS:APP 3rd Ed | Chapter 7.6 “Symbol Resolution” |
| Relocation | CS:APP 3rd Ed | Chapter 7.7 “Relocation” |
| Static linking | CS:APP 3rd Ed | Chapter 7.6-7.7 |
| Dynamic linking | CS:APP 3rd Ed | Chapter 7.10-7.12 |
| ELF format specification | Tool Interface Standard | ELF Specification v1.2 |
| Complete linker/loader | Linkers & Loaders (Levine) | Entire book |
| x86-64 architecture | Intel SDM | Volume 2 (Instruction Set Reference) |
| Position-independent code | CS:APP 3rd Ed | Chapter 7.12 |
Self-Assessment Checklist
Understanding
- I can explain the purpose of linking in the compilation pipeline
- I understand the difference between relocatable objects and executables
- I can describe the ELF file structure (header, sections, segments)
- I understand symbol binding (local, global, weak) and resolution rules
- I can explain what a relocation entry contains and how it’s used
- I understand PC-relative vs absolute addressing
- I know why the addend is typically -4 for call instructions
Implementation
- My linker parses ELF headers correctly
- My linker extracts symbol tables and string tables
- My linker applies strong/weak resolution rules correctly
- My linker detects and reports multiple definitions
- My linker detects and reports undefined references
- My linker merges sections with proper alignment
- My linker applies at least 3 relocation types correctly
- My linker produces output that passes
readelfvalidation
Testing
- I have test cases for symbol resolution edge cases
- I have test cases comparing output with system linker
- I verify relocation correctness with objdump
- I have negative tests for error conditions
Growth
- I can debug “undefined reference” errors in real projects
- I understand how dynamic linking extends static linking concepts
- I can explain linker behavior in interviews
- I know what tools to use for binary analysis (readelf, nm, objdump)
Submission / Completion Criteria
Minimum Viable Completion:
- Parse ELF64 relocatable objects correctly
- Implement symbol collection and resolution (strong/weak)
- Merge at least .text and .data sections
- Apply R_X86_64_PC32 relocations
- Output valid ELF readable by readelf
Full Completion:
- All of the above plus R_X86_64_64 and R_X86_64_32 relocations
- Handle COMMON symbols
- Merge all standard sections (.text, .rodata, .data, .bss)
- Actionable error messages for undefined/multiple definitions
- Verbose mode showing resolution and relocation details
Excellence (Going Above & Beyond):
- Archive (.a) file support
- Executable output with program headers
- Link map generation
- Additional relocation types (GOT-related)
- Performance optimization for large inputs
This guide was expanded from CSAPP_3E_DEEP_LEARNING_PROJECTS.md. For the complete learning path, see the project index.