CSAPP Core Concepts Reference: Compilation, Data Representation, x86-64 Assembly, Caching, Linking, Processes and Virtual Memory

Posted by Anonymous and classified in Computers

Written on October 14, 2026 in English with a size of 32.84 KB

Chapter 1: Program Generation and Execution

The compilation process consists of 4 steps:

Preprocessing: Input a .c file, output a .i file. It expands all macro definitions, processes #include (inserts header file contents), handles conditional compilation directives such as #ifdef, and removes comments.
Compilation: Input a .i file, output a .s file (assembly code). It translates C into assembly language, performing syntax analysis, semantic analysis, and optimization.
Assembly: Input a .s file, output a .o file (relocatable object file). It translates assembly language into machine code (binary), but addresses are not yet determined.
Linking: Input multiple .o files and library files, output an executable file. It performs symbol resolution (associating function names and variable names with their addresses) and relocation (determining final memory addresses).

Common GCC Options

-E: Preprocessing only, outputs a .i file
-S: Compile up to assembly, outputs a .s assembly file
-c: Assemble up to object code, outputs a .o object file
-o filename: Specifies the output file name
-O1, -O2, -O3: Optimization levels; the higher the number, the more aggressive the optimization
-g: Generates debugging information for use with gdb

Chapter 2: Data Representation and Operations

1. Two's Complement

Formula: B2T(x) = -x[w-1] × 2^(w-1) + x[w-2] × 2^(w-2) + ... + x[1] × 2^1 + x[0] × 2^0

The most significant bit is the sign bit, with weight -2^(w-1); all other bits have positive weights.

Range of a w-bit two's complement number: minimum = -2^(w-1) (only the sign bit is 1), maximum = 2^(w-1) - 1
Example, 8-bit: range is -128 to 127
Negating a number: invert all bits, then add 1. Example: 5 = 00000101 → invert to 11111010 → add 1 gives 11111011 = -5
Sign extension: when extending to more bits, fill the high bits with the sign bit. Example: 8-bit -3 = 11111101 → 16-bit 1111111111111101
Truncation: discard high bits and keep low bits. This may change the value or even the sign.

2. IEEE 754 Floating-Point Numbers

Formula: V = (-1)^s × M × 2^E, where s is the sign bit (0 positive, 1 negative), M is the significand, and E is the exponent, which determines the position of the binary point.

Single precision (float, 32-bit): 1 sign bit + 8 exponent bits + 23 significand bits, Bias = 127
Double precision (double, 64-bit): 1 sign bit + 11 exponent bits + 52 significand bits, Bias = 1023
Normalized numbers (exponent field neither all 0s nor all 1s): E = exponent field - Bias, M = 1.fraction (implicit leading 1)
Denormalized numbers (exponent field all 0s): E = 1 - Bias, M = 0.fraction (no implicit 1), used to represent very small numbers and zero
Special values (exponent field all 1s): fraction all 0s represents infinity ±∞; fraction non-zero represents NaN (not a number)
Single-precision example: exponent field = 10000001 (129), fraction = 01000...0, so E = 129 - 127 = 2, M = 1.01 = 1.25, V = 1.25 × 2^2 = 5.0

3. UTF-8 Encoding

UTF-8 is a variable-length encoding; the number of bytes depends on the Unicode code point:

Code point U+0000 to U+007F (ASCII): 1 byte, format 0xxxxxxx
Code point U+0080 to U+07FF: 2 bytes, format 110xxxxx 10xxxxxx
Code point U+0800 to U+FFFF (including Chinese characters): 3 bytes, format 1110xxxx 10xxxxxx 10xxxxxx
Code point U+10000 to U+10FFFF: 4 bytes, format 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx

Example, the character "中": its Unicode code point is U+4E2D = 0100 1110 0010 1101, which falls in the U+0800–U+FFFF range and uses 3 bytes. Splitting the bits into 4+6+6: 0100 111000 101101, then filling the template gives 11100100 10111000 10101101 = E4 B8 AD.

4. Type Conversion Pitfalls

Signed to unsigned: the bit pattern is unchanged, but its interpretation changes. Negative numbers become very large positive numbers! Example: (unsigned)(-1) = 4294967295
Unsigned to signed: the bit pattern is unchanged; large positive values may become negative
int to float: precision may be lost, because float has only 23 significand bits while int has 32 bits. For example, a large integer converted to float and back to int may not match the original.
float to int: truncates the fractional part (rounds toward zero), and may overflow

Chapter 3: Machine-Level Representation of Programs

1. x86-64 Registers

General-purpose registers (64-bit / 32-bit / 16-bit / 8-bit names):

%rax / %eax / %ax / %al: return value register; function return values are placed here
%rbx / %ebx / %bx / %bl: callee-saved register
%rcx / %ecx / %cx / %cl: 4th argument
%rdx / %edx / %dx / %dl: 3rd argument
%rsi / %esi / %si / %sil: 2nd argument
%rdi / %edi / %di / %dil: 1st argument
%rbp / %ebp / %bp / %bpl: frame pointer (callee-saved)
%rsp / %esp / %sp / %spl: stack pointer, points to the top of the stack
%r8 through %r15: %r8 is the 5th argument, %r9 is the 6th argument, and %r12 through %r15 are callee-saved

Argument passing order: the first six integer/pointer arguments use registers in the order %rdi, %rsi, %rdx, %rcx, %r8, %r9. The 7th and subsequent arguments are passed on the stack. Return values are placed in %rax.

2. Common Assembly Instructions

Data transfer: movq S, D copies S to D (q = 64-bit, l = 32-bit, w = 16-bit, b = 8-bit)
leaq S, D places the address of S (not its value) into D; commonly used for address computation and simple arithmetic
Arithmetic: addq S, D computes D = D + S; subq S, D computes D = D - S; imulq S, D computes D = D × S (signed multiplication); negq D computes D = -D
Shifts: salq k, D computes D = D << k (arithmetic left shift, equivalent to shlq); sarq k, D computes D = D >> k (arithmetic right shift, fills high bits with the sign bit, for signed numbers); shrq k, D computes D = D >> k (logical right shift, fills high bits with 0, for unsigned numbers)
Logical: andq S, D (D = D & S); orq S, D (D = D | S); xorq S, D (D = D ^ S); notq D (D = ~D)
Comparison and test: cmpq S2, S1 computes S1 - S2 and sets condition codes without saving the result; testq S1, S2 computes S1 & S2 and sets condition codes without saving the result
Jumps: jmp Label (unconditional); je/jz (jump if equal/zero, ZF = 1); jne/jnz (jump if not equal/not zero); jg/jnle (jump if greater, signed); jl/jnge (jump if less, signed); ja/jnbe (jump if above, unsigned); jb/jnae (jump if below, unsigned)

3. Condition Code Registers

ZF (Zero Flag): set to 1 when the result is 0
SF (Sign Flag): set to 1 when the result is negative
CF (Carry Flag): set to 1 when an unsigned operation overflows
OF (Overflow Flag): set to 1 when a signed operation overflows

4. Stack Frame Layout (memory addresses from high to low)

Caller's frame: the 7th and later arguments (if any), and the return address (automatically pushed by the call instruction)
Callee's frame: the saved old %rbp (if a frame pointer is used), local variables, saved callee-saved registers, temporary variables; %rsp points here (the top of the stack)

5. Buffer Overflow and Defenses

Principle: when more data is written into an array than it can hold, adjacent memory is overwritten, including the return address. An attacker can overwrite the return address to execute malicious code.

Stack randomization (ASLR): the starting address of the stack differs each time the program runs, making the return address hard to predict
Stack protector / canary: a random value is placed between the return address and local variables; the function checks whether this value was modified before returning
Non-executable stack (NX/DEP): the stack is marked non-executable, so even injected code cannot run

Chapter 4: Processor Architecture

1. The Six Elements of an ISA (Instruction Set Architecture)

Data types: the kinds of data the processor handles, such as integers, floating-point numbers, and characters
Instruction format: instruction length and the meaning and position of each field
Addressing modes: how operand locations are specified, such as immediate values, registers, and memory addresses
Instruction set: the available instructions, such as arithmetic, logical, data transfer, and control transfer
Register organization: how many registers exist and what each is used for
Exception and interrupt handling: how errors and external events are handled

2. The Six Stages of the SEQ Processor

Fetch: read the instruction from memory using the PC; determine the instruction type and length
Decode: read register values and prepare operands
Execute: the ALU performs computation or calculates memory addresses
Memory: read from or write to memory if needed
Write back: write results back to registers
PC update: set the address of the next instruction

3. Three Pipeline Hazards and Solutions

Data hazard: a later instruction needs a result that an earlier instruction has not yet produced. Solutions: forwarding — pass the result directly from pipeline registers to where it is needed, without waiting for write-back; stalling — insert a bubble and wait until the result is ready
Control hazard: when a branch is encountered, it is unknown which instruction to execute next. Solutions: branch prediction — guess the branch direction, and flush the pipeline if the guess is wrong; delay slot — the instruction after the branch always executes
Structural hazard: multiple instructions need the same hardware resource simultaneously. Solutions: add hardware resources (such as separate instruction and data memories); stall the pipeline

Chapter 5: Program Optimization

★★★ Key Topics: Loop Unrolling and Separate Accumulators ★★★

1. General Optimization Techniques

Code motion: move computations that do not change within a loop outside the loop. Bad: for(i=0; i<strlen(s); i++) ... (calls strlen on every iteration). Good: int len = strlen(s); for(i=0; i<len; i++) ...
Reduce function calls: function calls have overhead; inline functions or reduce the number of calls
Reduce memory accesses: use local variables (registers) to hold intermediate values instead of repeatedly reading and writing memory. Bad: for(i=0; i<n; i++) *dest = *dest + a[i]; (reads and writes *dest every time). Good: int acc = *dest; for(i=0; i<n; i++) acc += a[i]; *dest = acc;

2. Loop Unrolling

Principle: reduce the overhead of loop control (comparison and jumps) by doing more work per iteration.

Example with unrolling factor k = 2. Original code:

for (i = 0; i < n; i++) {
    acc = acc + a[i];
}

After unrolling:

for (i = 0; i < n-1; i += 2) {
    acc = acc + a[i];
    acc = acc + a[i+1];
}
for (; i < n; i++) {   // handle remaining elements
    acc = acc + a[i];
}

Note: after unrolling, you must handle the case where n is not divisible by k!

3. ★★★ Separate Accumulators (Multiple Parallel Accumulation) ★★★ — Key exam topic!

Problem: even after loop unrolling, performance may still be limited by data dependencies, because each operation depends on the previous result (acc = acc + ...).

Solution: use multiple accumulators to break the dependency chain so the CPU can execute operations in parallel.

Separate accumulators with k = 2:

int acc0 = 0;
int acc1 = 0;
for (i = 0; i < n-1; i += 2) {
    acc0 = acc0 + a[i];
    acc1 = acc1 + a[i+1];
}
for (; i < n; i++) {
    acc0 = acc0 + a[i];
}
int result = acc0 + acc1;

Separate accumulators with k = 4:

int acc0 = 0, acc1 = 0, acc2 = 0, acc3 = 0;
for (i = 0; i < n-3; i += 4) {
    acc0 = acc0 + a[i];
    acc1 = acc1 + a[i+1];
    acc2 = acc2 + a[i+2];
    acc3 = acc3 + a[i+3];
}
for (; i < n; i++)
    acc0 = acc0 + a[i];
int result = (acc0 + acc1) + (acc2 + acc3);

Why it works: modern CPUs have multiple execution units that can perform several additions simultaneously. Separate accumulators remove dependencies between additions, allowing them to execute in parallel.

Chapter 6: Memory Hierarchy and Cache

★★★ Key Topic: Blocking Method ★★★

1. Memory Hierarchy (fastest to slowest)

Registers: capacity < 1 KB, access time about 0 cycles, fastest
L1 cache: capacity 32–64 KB, access time about 4 cycles
L2 cache: capacity 256 KB–1 MB, access time about 10 cycles
L3 cache: capacity 8–32 MB, access time about 40–75 cycles
Main memory (RAM): capacity 4–64 GB, access time about 100 ns (about 200 cycles)
Disk/SSD: capacity 1 TB+, access time about 10 ms (disk) or 100 µs (SSD)

Key numbers: main memory is about 100 times slower than L1, and disk is about 100,000 times slower than main memory.

2. Locality Principles

Temporal locality: data that was recently accessed is likely to be accessed again soon (for example, loop variables)
Spatial locality: data near recently accessed data is likely to be accessed (for example, iterating through an array)

Good programs exhibit good locality. Good: traverse a 2D array row by row, for(i) for(j) a[i][j], which accesses memory contiguously. Bad: traverse column by column, for(j) for(i) a[i][j], which accesses memory with large jumps.

3. Cache Structure

A cache is organized into S sets, each with E lines, and each line holds a B-byte block. Total cache size = S × E × B bytes.

Direct-mapped cache: E = 1, each set has only one line; simple but prone to conflicts
Set-associative cache: 1 < E < total number of lines; each set has multiple lines, balancing performance and cost
Fully associative cache: only one set containing all lines; most flexible but slow to search

4. Cache Address Breakdown (for an m-bit address)

The address is split into three parts: | tag (t bits) | set index (s bits) | block offset (b bits) |

Set index: determines which set the data belongs to, s = log2(S)
Block offset: determines the position within the block, b = log2(B)
Tag: distinguishes different addresses mapping to the same set, t = m - s - b

Cache access process: (1) use the set index to locate the set; (2) compare tags within the set to check for a hit; (3) on a hit, use the block offset to extract the data; (4) on a miss, load the entire block from memory.

5. ★★★ Blocking Optimization (Blocking) ★★★ — Key exam topic!

Problem: in matrix multiplication C = A × B, computing in the naive way accesses B by column, which has poor spatial locality.

Naive matrix multiplication (poor spatial locality):

for (i = 0; i < n; i++)
    for (j = 0; j < n; j++)
        for (k = 0; k < n; k++)
            C[i][j] += A[i][k] * B[k][j];   // B[k][j] is accessed by column!

Blocked matrix multiplication (B is the block size):

for (i = 0; i < n; i += B)
    for (j = 0; j < n; j += B)
        for (k = 0; k < n; k += B)
            for (ii = i; ii < min(i+B, n); ii++)
                for (jj = j; jj < min(j+B, n); jj++)
                    for (kk = k; kk < min(k+B, n); kk++)
                        C[ii][jj] += A[ii][kk] * B[kk][jj];

Why it works: each step processes one small block, which can fit entirely in the cache. While working on a small block, all the data stays in the cache, avoiding many cache misses.

Choosing the block size: blocks that are too small incur high overhead; blocks that are too large will not fit in the cache. A common choice is one where three B × B blocks fit in the cache.

Chapter 7: Linking

1. Types of Symbols

Global symbols: defined in the current module and can be referenced by other modules (non-static functions and global variables)
External symbols: defined in other modules and referenced by the current module (declared with extern)
Local symbols: used only within the current module (static functions and static variables)

2. Strong and Weak Symbols

Strong symbols: functions and initialized global variables
Weak symbols: uninitialized global variables

Rules for handling multiple definitions:

Multiple strong symbols with the same name are not allowed (link error)
If there is one strong symbol and multiple weak symbols, the strong symbol is chosen
If there are only multiple weak symbols, one is chosen arbitrarily (this is dangerous, as the wrong one may be chosen)

3. Important Sections of an ELF File

.text: compiled machine code
.rodata: read-only data, such as string constants and switch jump tables
.data: initialized global and static variables
.bss: uninitialized global and static variables (occupies no space in the file; only its size is recorded)
.symtab: symbol table, recording the name, address, size, and other information for all symbols
.rel.text: relocation information for .text, telling the linker which locations need modification
.rel.data: relocation information for .data

4. Static Linking vs. Dynamic Linking

Static linking (.a static libraries): library code is copied into the executable at link time; the executable is larger, no library file is needed at runtime, and updating the library requires relinking
Dynamic linking (.so shared libraries): only references are recorded at link time, with no code copied; the executable is smaller, the library file must exist at runtime, and updating the library does not require relinking since the new version is used automatically

5. Library Interpositioning

Compile-time interpositioning: use -I to specify a header directory, replacing system headers
Link-time interpositioning: use -Wl,--wrap,func to redirect calls to func to __wrap_func
Run-time interpositioning: set the LD_PRELOAD environment variable to load your own library, overriding system functions

Chapter 8: Exceptional Control Flow and Processes

1. Four Types of Exceptions (Must Know!)

Interrupt: caused by external I/O devices (such as keyboard input or timers); asynchronous (unrelated to the current instruction); returns to the next instruction
Trap: intentionally executed by the program, mainly system calls (such as read, write, fork); synchronous (caused by an instruction); returns to the next instruction
Fault: a potentially recoverable error (such as a page fault, division by zero, or segmentation fault); synchronous; if recoverable, the faulting instruction is re-executed; otherwise the program is terminated
Abort: an unrecoverable serious error (such as a hardware failure or illegal instruction); synchronous; does not return, and the program is terminated immediately

2. Process States

Running: currently executing on the CPU
Ready: ready to run, waiting to be scheduled onto the CPU
Blocked/Waiting: waiting for some event (such as I/O completion)

State transitions: Running → Ready: time slice expired, or preempted by another process; Ready → Running: selected by the scheduler; Running → Blocked: waiting for I/O or another event; Blocked → Ready: the awaited event has occurred.

3. The fork() System Call

Function: creates a child process, which is a copy of the parent process
Return value: in the parent, returns the child's PID (a positive integer); in the child, returns 0; returns -1 on failure
Characteristics: called once but returns twice (once in the parent and once in the child); the child gets copies of the parent's data, code, stack, and heap (copy-on-write); the child inherits copies of the parent's open file descriptors

pid_t pid = fork();
if (pid == 0) {
    /* code executed by the child */
} else if (pid > 0) {
    /* code executed by the parent */
} else {
    /* fork failed */
}

4. The execve() System Call

Function: loads and runs a new program within the current process
Prototype: int execve(const char *filename, char *const argv[], char *const envp[]);
Parameters: filename is the path of the program to run; argv[] is the argument array (argv[0] is the program name, terminated by NULL); envp[] is the environment variable array (terminated by NULL)
Return value: does not return on success (since a new program is now running); returns -1 on failure
Difference from fork: fork creates a new process; execve does not — it replaces the current process's program. After fork, two processes run the same program; after execve, it is still one process, but running a different program. Typically fork and execve are used together to create a new process running a new program.

5. Signals

SIGINT (2): sent when the user presses Ctrl+C; terminates the process by default
SIGKILL (9): kills the process; cannot be caught or ignored
SIGSEGV (11): segmentation fault (illegal memory access); terminates the process and generates a core dump by default
SIGCHLD (17): sent to the parent when a child stops or terminates; ignored by default
SIGSTOP (19): stops the process; cannot be caught or ignored
SIGALRM (14): timer expired; terminates the process by default

Signal handling: signal(signum, handler) sets a signal handler; the handler can be SIG_IGN (ignore), SIG_DFL (default), or a custom function. sigprocmask(how, &set, &oldset) blocks or unblocks signals: SIG_BLOCK adds the signals in set to the blocked set, SIG_UNBLOCK removes them, and SIG_SETMASK sets the blocked set to set.

Characteristics of signals: signals may be lost (only one pending signal of each type is kept); signal handlers should be kept simple, avoiding non-reentrant functions.

Chapter 9: Virtual Memory

1. Address Spaces

Physical address space: the actual memory addresses, whose size is determined by the hardware
Virtual address space: the address space seen by each process, usually larger than physical memory (for example, a 64-bit system has 2^48 bytes)
Linear address space: a contiguous address space; on x86, virtual addresses are linear addresses
Pages: both virtual and physical memory are divided into fixed-size blocks, typically 4 KB (2^12 bytes)

2. Page Tables and Address Translation

Virtual address structure: | virtual page number VPN | virtual page offset VPO |
Physical address structure: | physical page number PPN | physical page offset PPO |
Key point: VPO = PPO; the page offset does not need translation!

Translation process: use the VPN to look up the page table, obtain the PPN, then concatenate the PPN with the VPO to form the physical address.

Page table entry (PTE) contents: valid bit (whether the page is in memory), physical page number, permission bits (read/write/execute), and so on.

Address translation example (assume 4 KB = 2^12 page size, 32-bit virtual address, 30-bit physical address): page offset is 12 bits; VPN is 32 − 12 = 20 bits; PPN is 30 − 12 = 18 bits. For virtual address 0x12345678: VPN = 0x12345, VPO = 0x678. If the page table maps VPN 0x12345 to PPN 0x3ABCD, the physical address = PPN || VPO = 0x3ABCD678.

3. TLB (Translation Lookaside Buffer)

Problem: every memory access requires first accessing the page table, which is slow.

Solution: the TLB caches recently used page table entries.

The TLB is a small, fast cache storing VPN-to-PPN mappings
TLB hit: the PPN is obtained directly, without accessing the page table
TLB miss: the page table is accessed, and the result is stored in the TLB

4. Page Faults

When the accessed page is not in physical memory, a page fault interrupt occurs.

Handling process: (1) the CPU raises a page fault exception; (2) the operating system finds the page's location on disk; (3) if physical memory is full, a victim page is selected, and if it has been modified, it is written back to disk; (4) the required page is read from disk into physical memory; (5) the page table entry is updated (the valid bit is set and the physical page number is filled in); (6) control returns, and the instruction that caused the fault is re-executed.

5. Multi-Level Page Tables

Problem: if the virtual address space is large (such as 48 bits), a single-level page table becomes too large.

Solution: use multi-level page tables, allocating page tables only for the address space that is actually used.

Structure of a 4-level page table (using a 48-bit virtual address as an example):

Translation process: the CR3 register points to the L1 page table → the L1 index locates the L2 page table → the L2 index locates the L3 page table → the L3 index locates the L4 page table → the L4 index yields the PPN.

Advantage: most of the address space is unused, so corresponding page table entries need not be allocated, saving memory.

6. mmap Memory Mapping

Prototype: void *mmap(void *addr, size_t length, int prot, int flags, int fd, off_t offset);

Parameters: addr is a suggested mapping address (usually NULL to let the system decide); length is the length of the mapping; prot is the protection flags (PROT_READ | PROT_WRITE | PROT_EXEC); flags is MAP_PRIVATE (copy-on-write; modifications do not affect the file) or MAP_SHARED (modifications are written back to the file); fd is the file descriptor (-1 for anonymous mappings); offset is the offset within the file
Uses: file mapping (map a file into memory so it can be accessed like an array), anonymous mapping (allocate a block of memory not associated with a file, which can be used for inter-process shared memory)
vm_area_struct: the Linux kernel manages a process's virtual address space with a linked list; each region is described by a vm_area_struct

Chapter 10: System-Level I/O

(For reference only; not on the exam.)

Three I/O methods:

Unix I/O (low-level I/O): open, read, write, close. Advantage: most general, suitable for networks and devices. Disadvantage: no buffering; every call is a system call.
Standard I/O (stdio): fopen, fread, fwrite, fclose, fgets, fputs. Advantage: buffered, reducing the number of system calls, and easy to use. Disadvantage: poor support for network I/O and signal handling.
Memory-mapped I/O (mmap): maps a file into memory. Advantage: efficient for large files, supports random access. Disadvantage: not suitable for streaming.

Common Pitfalls and Memory Tips

Argument register order: rdi, rsi, rdx, rcx, r8, r9
fork return value: the parent receives the child's PID; the child receives 0. Remember: "parent gets the child's ID, child gets zero."
Four exception types: interrupt (external, asynchronous, returns to next instruction); trap (requested by the program, synchronous, returns to next instruction); fault (something went wrong, may be recoverable, re-executes the instruction); abort (unrecoverable, program terminates)
Symbol resolution rules: "strong-strong is an error, strong-weak picks strong, weak-weak is random"
Address translation: the page offset is never translated; only the page number is translated.
Separate accumulators: use multiple variables to accumulate and combine at the end, breaking data dependency chains.
Blocking: divide a large matrix into small blocks so each block fits entirely in the cache.
Memory hierarchy speed: registers (0) < L1 (4) < L2 (10) < L3 (40) < main memory (about 200 cycles) < disk (tens of millions of cycles)

Related entries:

Tags: