Skip to content
Tutorials Center
My learning

Topics

Lesson 45 of 61 ยท Code Generation and Runtimes

Assemblers, Linkers and Loaders

Follow code from assembly to a running program: the two-pass assembler, symbol tables, relocation entries, symbol resolution in the linker, and what the loader does.

A compiler's last real output is usually not a running program. It is assembly language, or an object file made from it. Between that output and a process that executes on the CPU there are three more tools. The assembler turns text into machine code. The linker joins several pieces of machine code into one program. The loader, part of the operating system, copies the program into memory and starts it. Understanding them clears up a whole family of mysterious errors: "undefined reference to foo", "multiple definition of bar", and "relocation truncated to fit".

In this lesson you will build all three for a small imaginary machine, so that every concept (two passes, symbol tables, relocation, symbol resolution) is something you have run and can see. The mechanics are the same as for real formats such as ELF, Mach-O and PE.

The pipeline

flowchart LR
    S1["main.s"] --> A1["Assembler"] --> O1["main.o"]
    S2["lib.s"] --> A2["Assembler"] --> O2["lib.o"]
    O1 --> L["Linker"]
    O2 --> L
    LIB["Libraries"] --> L
    L --> X["Executable"]
    X --> LD["Loader"] --> P["Process in memory"]

Each source file is assembled separately. The linker combines the object files into one executable and the loader runs it.

Compilers could do all of this in one step, but separate stages bring real benefits. Each source file can be compiled and assembled alone, so after a small edit only that file is rebuilt. Libraries can be written once and combined with any program. And the later stages do not need to know which language produced the code.

The assembler

Assembly language gives names to opcodes (LOAD, ADD) and to addresses (labels). The assembler must translate the instruction JMP loop into a binary opcode plus the address of loop. The trouble is that loop may be defined later in the file: a forward reference. The classic solution is two passes over the source:

  • Pass 1 reads every line and keeps a location counter, the offset of the next instruction. Each time it sees a label it records label -> location counter in the symbol table. It does not generate any code yet.
  • Pass 2 reads the lines again, encodes each instruction, and now every label has an address, so forward references are resolved.

The other solution is the single-pass assembler with backpatching, as in backpatching: it leaves holes and fills them in as labels appear.

The assembler also handles directives, instructions to itself rather than to the CPU: .word 20 reserves a memory word with a value, .global main says that the name main may be used from other files, and .extern double says that the name double is defined elsewhere.

Relocatable object code

The assembler does not know where the program will be placed in memory. Addresses inside a module are therefore offsets from the start of the module. When the linker later puts the module at some position, these offsets must be adjusted. So the assembler produces an object file with three parts:

  1. The machine code and data, with offsets in place of final addresses.
  2. A table of exported symbols: the global names this module defines, with their offsets.
  3. A table of relocation entries: for every place in the code that holds an address, "this operand needs the module's base address added", or "this operand needs the address of the external symbol double".

Real object files also split these parts into sections (segments): the text section holds the machine code, the data section holds variables with initial values, and the bss section only records how many bytes of zero-initialized variables to reserve, so it takes no space in the file. The linker merges the sections of the same kind from all modules, and the loader gives each kind its own memory protection (text read-only and executable, data read-write).

Pseudo-operations, literals and LTORG

Besides real instructions, assembly source contains pseudo-operations, instructions for the assembler that produce no machine code of their own. The classic set is START n (the program begins at address n), END (the end of the source), DS k (reserve k words of storage) and DC v (store the constant v). Pass 1 handles them by changing the location counter, never by emitting an instruction.

A literal is a constant written straight in an operand, such as ='3' in MOVER R1, ='3', meaning "the address of a word that contains 3". The assembler has to put that word somewhere, so it keeps a literal table next to the symbol table. Literals are collected into a literal pool, and the pool is given addresses at the next LTORG pseudo-operation or, if there is none, at END. Each pool is placed right after the last instruction before LTORG, one word per literal, and identical literals inside one pool share a word.

The program below runs both passes. The first LTORG allocates ='3' and ='2'; the literal ='3' appears again later and gets a new word in the pool flushed at END, because the first pool is already placed.

Python Two passes with a symbol table and a literal pool

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Read the result: instructions occupy 200 to 202, LTORG places the first pool at 203 and 204, so the first instruction's operand is 203 and ='2' is at 204. The code after LTORG continues at 205 and 206, X (a DS 1) takes 207, and the second ='3' lands at 208. The symbol table shows L1 at 202 and X at 207. This is also why a single-pass assembler needs backpatching or a pending list for forward references, while the two-pass design simply waits until pass 1 has seen everything.

The linker

The linker has two main jobs.

Symbol resolution. It collects the exported symbols of all modules into one global table. Then it checks every external reference. If some module uses double and nobody defines it, you get undefined reference. If two modules both define main, you get multiple definition. This is the origin of the most common linker errors.

Relocation. It decides where each module will be placed in the final image, usually one after the other, and so learns each module's base address. Then it goes through the relocation entries: module-relative operands get the base address added, and external operands are filled with the final address of the symbol.

The output is an executable: all symbols resolved, and every address fixed relative to the start of the image. (Real linkers also merge the code, data and other sections of all modules into one code area and one data area. The model below keeps one section for simplicity.)

The loader

The loader is part of the operating system. It reads the executable, creates the process's address space, copies code and data into memory, sets up the stack, and jumps to the entry point. If the program was linked for a fixed address, the loader can simply place it there. If it must run at an address chosen at load time (for example, with address-space randomization, or for shared libraries), the executable carries its relocation entries, and the loader applies the final fix: it adds the load address to every address that has to move. Code written so that it needs no such fixing is called position-independent, because it uses relative jumps and relative data access.

Kinds of loaders

Textbooks sort loaders by how much work they leave to the loader and how much to earlier tools:

  • Absolute loader. The object file already contains final addresses, so the loader only copies the code to those addresses. It is the simplest, but the programmer (or assembler) must choose the address, and two programs cannot share it. It still describes how many microcontrollers are programmed.
  • Compile-and-go loader. The assembler or compiler places the code in memory itself and starts it, with no object file at all. It is quick for small programs and wasteful, because everything is translated again on every run.
  • Relocating loader. The file carries relocation information, so the loader can place the code at any address and fix every address-dependent operand, like the loader in the toolchain below. Most operating systems do this.
  • Direct-linking loader. The loader also does the linker's job: it reads several object modules, builds the global symbol table and resolves external references while loading. This is the model behind dynamic linking.
  • Bootstrap loader. A tiny program stored in ROM that runs at power-on and loads the next, larger program (the boot loader, then the operating system kernel).
  • Dynamic loader. Loads libraries while the program runs, when a function is first needed, as with ld.so or dlopen.

The usual trade-offs are simplicity versus flexibility. A loader that does less is smaller and faster to run, but it needs a smarter assembler and linker, and limits where the program can live in memory. Modern loaders also need the OS to protect memory, which a bare relocating loader does not do on its own.

A complete toolchain for a toy machine

The machine has an accumulator, a 256-word memory and eight instructions: HALT LOAD STORE ADD JMP JZ CALL RET. Each instruction is one 16-bit word, the opcode in the high byte and an address in the low byte. The program below contains:

  • assemble, a real two-pass assembler. It prints the pass-1 symbol table, the object code and the relocation entries.
  • link, which lays out modules, resolves symbols and applies relocations, and reports undefined and duplicate symbols.
  • load_and_run, a loader that applies the final fix for a chosen base address and then executes the program with a tiny CPU.

The program in main.s adds two numbers, calls double from lib.s, and stores the answer in out.

Python An assembler, a linker and a loader

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Trace the output step by step:

  1. Pass 1 of main.s finds the symbols main at offset 0, x at 5, y at 6 and out at 7. Instructions 0, 1 and 3 refer to local labels, so they each get a reloc entry. Instruction 2, CALL double, has the operand 0 and an extern entry: the assembler cannot know where double is.
  2. The linker places main.o at 0 and lib.o at 8 (the length of main.o), so double is exported as address 8. CALL double becomes 0608, and lib.o's operands, which referred to its own tmp at offset 3, become 0b (11). The fix-up list contains every position that holds an address.
  3. The loader adds the base to every fix-up, so the program works at base 0, 50 and 120. At every base the result in out is 42, which is (20 + 1) * 2, but out itself lives at a different address each time.
  4. Linking main.o alone fails with undefined reference to 'double', and linking two copies of it fails with duplicate symbol 'main'. These are the same checks that real linkers do.

Static and dynamic linking

The linker above is static: the final executable contains a copy of every library function it uses. This is simple and self-contained, but every program carries its own copy of the C library, and fixing a library bug means rebuilding every program.

With dynamic linking, the executable contains only a reference to the library. A dynamic linker (also called the runtime linker or loader), ld.so on Linux and the loader of Windows, finds the shared library file when the program starts, maps it into memory and fixes the references. Many processes can share a single copy of the library code in memory. Calls to library functions usually go through a small table (the procedure linkage table and global offset table in ELF), and with lazy binding the address of a function is resolved on its first call.

Static linking Dynamic linking
Executable size Large Small
Startup Fast, nothing to resolve Slower, libraries must be found
Library updates Rebuild every program Replace one file
Memory use One copy per program One shared copy
Deployment One file runs anywhere compatible Needs the right library versions

Practical consequences

  • Header files do not link. A declaration (int double(int);) satisfies the compiler, but the linker needs a definition from some object file or library. Forgetting to pass the library is the usual reason for "undefined reference".
  • Order can matter. A traditional linker scans libraries from left to right and takes only the objects that resolve symbols it already needs. A library listed before the object that needs it may seem empty.
  • Symbols are names, not types. C does not encode parameter types in the symbol, so a wrong declaration links fine and fails at run time. C++ mangles names to include types and namespaces, which is why error messages show strange text.
  • Strong and weak symbols. Some linkers allow a weak definition that is silently replaced by a strong one, which is how default hooks and overridable functions are done.
  • Link-time optimization. A modern linker can keep the compiler's intermediate representation inside object files, then optimize across all of them at once.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why does an assembler need two passes?

    Pass 1 builds the symbol table with a location counter, pass 2 uses it to encode instructions, which resolves forward references.
  2. 2. What is a relocation entry?

    Object files contain module-relative addresses, and relocation entries mark every place that needs the base address or an external symbol added.
  3. 3. The linker reports 'undefined reference to double'. What is the most likely cause?

    An external reference with no matching exported definition is an undefined reference. Check that the right object file or library is linked.
  4. 4. What does the loader do for a program that must run at an address chosen at load time?

    The final relocation uses the table kept in the executable (or position-independent code that needs none).
  5. 5. What is one advantage of dynamic linking over static linking?

    Shared libraries save memory and disk space and let one fixed library benefit all programs. The cost is slower startup and version dependencies.

Summary

  • The assembler turns assembly into relocatable object code in two passes: the first builds the symbol table, the second encodes instructions.
  • Object files hold code with module-relative addresses, exported symbols and relocation entries.
  • The linker resolves symbols across modules (reporting undefined and duplicate symbols) and relocates each module to its place in the image.
  • The loader puts the executable into memory, applies any remaining relocation for the chosen load address, and starts execution.
  • Static linking copies library code into every executable. Dynamic linking shares libraries and binds them at load time or on first call.

Next, return to the code generator and decide where values live in Register Allocation.