The idea: four programs between your C code and a running program

A program written in C cannot run as it is. Four programs translate it and start it (Figure 6.32 in Harris and Harris, drawn on the left of the canvas):

  1. The compiler turns high-level code into assembly code.
  2. The assembler turns assembly code into machine code in an object file.
  3. The linker puts the object files and library files together into one executable.
  4. The loader copies the executable into memory and starts it.
main.c and sum.c go through the compiler to main.s and sum.s, through the assembler to main.o and sum.o, the linker joins them into prog, and the loader copies its text to 0x00400000 and data to 0x10000000 in memory
Compiler and assembler work on one file at a time; the linker is the first program that sees the whole program, and the loader puts it in memory.

The page follows the book's example (Code Example 6.30) the whole way, down to the 13 machine words of Figure 6.34:

int f, g, y;   // global variables
int sum(int a, int b);

int main(void)
{
  f = 2;
  g = 3;
  y = sum(f, g);
  return y;
}

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

The tabs run it as one file (as in the book), as two files main.c and sum.c, with sum taken from a library, and two ways to get a link error.

The MIPS memory map

MIPS has a 32-bit address space, split by convention (Figure 6.31). The linker and the loader both follow it:

SegmentAddressesHolds
reserved0x80000000–0xFFFFFFFCthe operating system, memory-mapped I/O
stack and dynamic data0x10010000–0x7FFFFFFCthe stack grows down from $sp = 0x7FFFFFFC, the heap grows up
global data0x10000000–0x1000FFFFglobal variables, reached through $gp = 0x10008000
text0x00400000–0x0FFFFFFCthe machine code
reserved0x00000000–0x003FFFFCthe operating system

$gp sits in the middle of the 64 KB global data segment. A load or store has a signed 16-bit offset, −32768 to 32767, so lw and sw with $gp reach every global in one instruction: f at 0x10000000 is 0x8000($gp), that is $gp − 32768.

Compiling

The compiler reads one C file and writes one assembly file. It decides where things live: globals in the data segment, arguments in $a0–$a3, the return value in $v0. Because main calls sum, and jal overwrites $ra, main saves $ra on the stack first. sum calls nothing (a leaf function), so it needs no stack frame. The compiler sees one file only: to call sum from main.c, it needs a declaration of sum, not its code.

Assembling: two passes and the symbol table

Pass 1 encodes nothing. It walks the file with a location counter per segment: every instruction and every .word takes 4 bytes. Every label gets the counter's current value, in the symbol table. Pass 2 walks the file again and encodes every instruction into a 32-bit word: the opcode, the register numbers, and the value of every symbol, taken from the symbol table.

Two passes are needed because of forward references: jal sum comes before the line sum:. When pass 2 reaches jal sum, pass 1 has already recorded where sum is (Demo: two passes and the symbol table).

FormatFields (bits)Example
R-typeop 6 · rs 5 · rt 5 · rd 5 · shamt 5 · funct 6add $v0, $a0, $a1 = 00851020
I-typeop 6 · rs 5 · rt 5 · imm 16addi $sp, $sp, -4 = 23BDFFFC
J-typeop 6 · addr 26jal 0x0040002C = 0C10000B

The object file: holes and relocations

With one file, the assembler can give every line its final address, which is what the book does (Table 6.4, Figure 6.33). Real assemblers cannot: they don't know which other files the program will have. So each segment of an object file starts at 0, and every field that holds an address is left as a hole (0) plus a relocation entry: "at offset 0x18, put the address of sum, as a jump target". In main.o there are four:

OffsetIn main.oRelocationThe linker computesIn prog
0x0CAF840000R_MIPS_GPREL16 ff − $gp = 0x10000000 − 0x10008000 = −32768AF848000
0x14AF850000R_MIPS_GPREL16 gg − $gp = −32764AF858004
0x180C000000R_MIPS_26 sumsum >> 2 = 0x0040002C >> 2 = 0x10000B0C10000B
0x1CAF820000R_MIPS_GPREL16 yy − $gp = −32760AF828008

A symbol used but not defined in the file (sum in main.o) is in the symbol table as undefined (UND). PC-relative fields, like a beq offset to a label in the same file, need no relocation: the distance does not change when the whole segment moves.

Linking: resolve, lay out, patch

The linker does three jobs (Demo: the linker relocates):

  1. Resolve: read the inputs in order, and find exactly one definition for every global symbol that some object file uses.
  2. Lay out: put the text segments one after the other from 0x00400000 (main.o's 0x2C bytes, then sum.o's, so sum = 0x0040002C), the data segments from 0x10000000. Now every symbol has its final address.
  3. Relocate: go through the relocation entries and fill each hole.
main.o starts at offset 0 with holes at 0x0C, 0x14, 0x18 and 0x1C for f, g, sum and y; in prog main starts at 0x00400000, sum is moved to 0x0040002C, and the holes become AF848000, AF858004, 0C10000B and AF828008
Each object file starts at 0 with holes where addresses go; once the linker knows the final layout it fills every hole from the relocation entries.

Then it writes the executable: a header with the text size (0x34), the data size (0xC) and the entry point, then the two segments. Two files and a linker give exactly the words the book got from one file.

Libraries

A static library (libmath.a) is an archive: a bag of object files with an index of the symbols they define. The linker takes a member only if it defines a symbol that is still undefined. Here it pulls sum.o and leaves diff.o out, because nothing calls diff (Demo: only sum.o is pulled in). That is why the C library does not end up whole in every program.

Loading

The operating system's loader reads the header, copies the text segment to 0x00400000 and the data segment to 0x10000000, sets $gp = 0x10008000 and $sp = 0x7FFFFFFC, and does jal 0x00400000 (Figure 6.35). main runs, calls sum, stores 2, 3 and 5 in f, g and y, and returns to the OS through $ra with 5 in $v0 (Demo: load and run).

What main does with $sp and $ra once it runs, how jal and jr $ra call and return, and which registers a procedure must save on the stack: MIPS Procedure Calls.

Link errors

The compiler and the assembler only see one file, so some mistakes only show up in the linker, the first program that sees the whole program:

MistakeMessageFix
link main.o without sum.oundefined reference to `sum'add the object file or library that defines sum
sum defined in main.c and in sum.cmultiple definition of `sum'define it in one file; only declare it in the others

Compared with real toolchains

The commands on the canvas (cc -S, as, ld -e main) are a simplified toolchain. A real one, such as mips-linux-gnu-gcc, does the same steps, and adds a preprocessor before the compiler, start-up code (crt0) that calls main, the C library, and the ELF file format. With -G 0 (no small-data section), sw $a0, f becomes two instructions, lui plus sw, with R_MIPS_HI16 / R_MIPS_LO16 relocations. The same journey on x86-64 Linux, with real gcc output, dynamic linking and ld.so, is in How a C Program Is Compiled, Linked, Loaded and Started. The loader's side on Linux (execve, ELF program headers, page faults) is in How Linux Loads a Program. How the loaded instructions then run on the hardware is in The Single-Cycle MIPS Processor.

What the page leaves out

The preprocessor, compiler optimisation, pseudo-instructions that expand to two instructions (li, la), branches and their PC-relative offsets, the .bss section (real compilers put zero-initialised globals there, not in .data), static functions and local symbols in relocations, the ELF format and its section headers, start-up code, shared libraries and dynamic linking, position-independent code, and virtual memory: on a real OS, the loader maps the file into a fresh address space instead of copying it.