## Table of Contents

1. [Number Representation & Bit-Level Operations](#1-number-representation--bit-level-operations)
2. [Integer Arithmetic & Overflow](#2-integer-arithmetic--overflow)
3. [Floating Point](#3-floating-point)
4. [x86-64 Assembly](#4-x86-64-assembly)
5. [Control Flow in Assembly](#5-control-flow-in-assembly)
6. [Procedures, Stack & Calling Convention](#6-procedures-stack--calling-convention)
7. [Arrays, Structs & Unions](#7-arrays-structs--unions)
8. [Buffer Overflow & Security](#8-buffer-overflow--security)
9. [Linking](#9-linking)
10. [Memory Hierarchy & Caches](#10-memory-hierarchy--caches)
11. [Exceptional Control Flow: Processes](#11-exceptional-control-flow-processes)
12. [Exceptional Control Flow: Signals](#12-exceptional-control-flow-signals)
13. [Virtual Memory & Address Translation](#13-virtual-memory--address-translation)
14. [Common Exam Patterns & Traps](#14-common-exam-patterns--traps)

---

## 1. Number Representation & Bit-Level Operations

### Type Sizes (x86-64 Linux)

| Type | Bytes | Bits |
|---|---|---|
| `char` | 1 | 8 |
| `short` | 2 | 16 |
| `int`, `unsigned`, `float` | 4 | 32 |
| `long`, `double`, pointers | 8 | 64 |
| `long long` | 8 | 64 |

### Two's Complement (w bits)

- Range: `[-2^(w-1), 2^(w-1) - 1]`
- For 32-bit `int`: `[-2,147,483,648, 2,147,483,647]` = `[INT_MIN, INT_MAX]`
- For 64-bit `long`: `[-2^63, 2^63 - 1]`
- Negation: `-x = ~x + 1`
- Therefore: `~x = -x - 1`
- **Asymmetric range:** `|INT_MIN| > INT_MAX`, so `-INT_MIN` overflows back to `INT_MIN`

### Sign Extension vs Zero Extension

- **Signed widening** (e.g., `int` → `long`): replicate the sign bit. Instruction: `movslq`, `movsbl`, etc.
- **Unsigned widening:** fill with zeros. Instruction: `movzbl`, `movzwl`. Note: `movl` already zero-extends to 64 bits.
- **Narrowing:** truncate (drop high bits). Same bit pattern interpretation, no instruction needed beyond using a smaller register.

### Bitwise vs Logical Operators

| Bitwise | Logical | Notes |
|---|---|---|
| `&` | `&&` | Logical short-circuits, returns 0 or 1 |
| `\|` | `\|\|` | Logical short-circuits |
| `~` | `!` | `!x` = `(x == 0)` |
| `^` | (none) | XOR — bit flipping |

### Useful Bit Tricks

- **Get bit n:** `(x >> n) & 1`
- **Set bit n:** `x \| (1 << n)`
- **Clear bit n:** `x & ~(1 << n)`
- **Toggle bit n:** `x ^ (1 << n)`
- **Mask of low k bits:** `(1 << k) - 1`
- **Multiply by 2^k:** `x << k`
- **Unsigned divide by 2^k:** `x >> k` (logical shift)
- **Signed divide by 2^k (rounded toward zero):** `(x < 0 ? x + (1<<k) - 1 : x) >> k`
- **XOR swap:** `a^=b; b^=a; a^=b;` (don't actually use this)
- **Check if power of 2:** `x && !(x & (x-1))`

### Shift Operators

- **Left shift `<<`:** fills with zeros (same for signed/unsigned)
- **Logical right shift `>>`:** fills with zeros (used for unsigned)
- **Arithmetic right shift `>>`:** fills with sign bit (used for signed)
- **C standard:** signed `>>` is implementation-defined, but on x86-64/GCC it's arithmetic
- **Undefined behavior:** shifting by ≥ width or by negative amount

---

## 2. Integer Arithmetic & Overflow

### Modular Arithmetic

All integer arithmetic in C is modulo `2^w` (wraps around). This means:

- Addition, subtraction, multiplication: **same bit pattern** for signed and unsigned
- Equality `==` compares bit patterns
- The interpretation only matters for **comparison** (`<`, `>`, `<=`, `>=`) and **division/modulo**

### Mixed Signed/Unsigned Comparison

⚠️ **Critical rule:** When `<`, `>`, `<=`, `>=`, `==` involves one signed and one unsigned operand, **the signed operand is converted to unsigned**.

```c
-1 < 0U          // FALSE: -1 becomes 0xFFFFFFFF
-1 == 0xFFFFFFFFU // TRUE: same bits
2147483647 > -2147483648 - 1  // beware: RHS is INT_MIN, OK
```

### Overflow Behavior

- **Unsigned overflow:** well-defined, wraps mod `2^w`
- **Signed overflow:** **undefined behavior** in C standard (compiler may assume it can't happen!)
- On x86-64 hardware, both wrap mod `2^w`, but compiler optimizations may exploit UB

### Common Identity Pitfalls

| Expression | True? | Reason |
|---|---|---|
| `(x < y) == (-x > -y)` | ❌ | Fails when `x = INT_MIN` |
| `x * 2 / 2 == x` | ❌ | Overflow can lose info |
| `(x + y) - x == y` | ✅ | Mod arithmetic preserves this |
| `~x + ~y + 1 == ~(x + y)` | ✅ | Both = `-(x+y) - 1` |
| `ux - uy == -(y - x)` | ✅ | Same bit pattern |
| `(x >= 0) \|\| (x < (unsigned)x)` | ❌ | When `x < 0`, `x` promotes to same unsigned value |
| `((x + y) << k) + y - x == (2^k+1)*y + (2^k-1)*x` | ✅ | Algebra in mod arithmetic |

### Integer Division Rules in C

- Truncates toward **zero** (since C99): `-7 / 2 == -3`
- `%` follows: `(a/b)*b + a%b == a`, so `-7 % 2 == -1`
- `-INT_MIN` and `INT_MIN / -1` are **undefined** (would overflow)

---

## 3. Floating Point

### IEEE 754 Format

| Type | Total bits | Sign | Exp | Frac | Bias |
|---|---|---|---|---|---|
| `float` | 32 | 1 | 8 | 23 | 127 |
| `double` | 64 | 1 | 11 | 52 | 1023 |

```
| s |  exp  |    frac    |
```

### Three Categories of Encoding

1. **Normalized** (exp ≠ 0 and exp ≠ all-1s):
   - Value = `(-1)^s × 1.frac × 2^(exp - bias)`
   - Implicit leading 1
2. **Denormalized** (exp = 0):
   - Value = `(-1)^s × 0.frac × 2^(1 - bias)`
   - Used for very small numbers and `±0`
3. **Special** (exp = all-1s):
   - frac = 0: `±∞`
   - frac ≠ 0: `NaN`

### Properties

- `+0.0 == -0.0` (compare equal but different bits)
- `NaN != NaN` (never equal to anything, even itself)
- Floating point math is **not associative**: `(a + b) + c ≠ a + (b + c)` in general
- Floating point math **is commutative** (except NaN)

### Conversions

- `int` → `float`: may lose precision (32-bit int has more precision than 23-bit frac)
- `int` → `double`: exact (32-bit int fits in 52-bit frac)
- `float`/`double` → `int`: truncates toward zero; out-of-range is **undefined** (typically returns `INT_MIN` on x86)

### Rounding (Round-to-Even, default)

- Round to nearest representable
- On exact halfway: round to even (avoids statistical bias)
- Examples: `1.5 → 2`, `2.5 → 2`, `-0.5 → 0`

---

## 4. x86-64 Assembly

### Register File

| 64-bit | 32-bit | 16-bit | 8-bit | Convention |
|---|---|---|---|---|
| `%rax` | `%eax` | `%ax` | `%al` | Return value, caller-saved |
| `%rbx` | `%ebx` | `%bx` | `%bl` | **Callee-saved** |
| `%rcx` | `%ecx` | `%cx` | `%cl` | Arg 4, caller-saved |
| `%rdx` | `%edx` | `%dx` | `%dl` | Arg 3, caller-saved |
| `%rsi` | `%esi` | `%si` | `%sil` | Arg 2, caller-saved |
| `%rdi` | `%edi` | `%di` | `%dil` | Arg 1, caller-saved |
| `%rbp` | `%ebp` | `%bp` | `%bpl` | **Callee-saved** (frame ptr) |
| `%rsp` | `%esp` | `%sp` | `%spl` | **Stack pointer** |
| `%r8`–`%r9` | `%r8d`–`%r9d` | ... | ... | Args 5, 6, caller-saved |
| `%r10`–`%r11` | ... | ... | ... | Caller-saved |
| `%r12`–`%r15` | ... | ... | ... | **Callee-saved** |

⚠️ **Writing to a 32-bit register zeros the upper 32 bits.** Writing to 8/16-bit does not.

### Operand Forms

| Syntax | Meaning |
|---|---|
| `$Imm` | Immediate (constant) |
| `%reg` | Register |
| `Imm` | Memory at address `Imm` |
| `(%reg)` | Memory at `*reg` |
| `Imm(%reg)` | Memory at `Imm + *reg` |
| `(%base, %index)` | Memory at `*base + *index` |
| `(%base, %index, scale)` | Memory at `*base + *index * scale` (scale ∈ {1,2,4,8}) |
| `Imm(%base, %index, scale)` | Memory at `Imm + *base + *index * scale` |

### Instruction Suffixes (Operand Size)

| Suffix | Size | Example |
|---|---|---|
| `b` | 1 byte | `movb` |
| `w` | 2 bytes | `movw` |
| `l` | 4 bytes | `movl` |
| `q` | 8 bytes | `movq` |

### Common Data Movement

| Instruction | Effect |
|---|---|
| `mov S, D` | `D = S` |
| `movz** S, D` | Zero-extend |
| `movs** S, D` | Sign-extend |
| `movslq S, D` | Sign-extend 32-bit signed → 64-bit |
| `cltq` | Sign-extend `%eax` → `%rax` |
| `pushq S` | `*--rsp = S` (stack grows down) |
| `popq D` | `D = *rsp++` |
| `lea S, D` | `D = &S` (compute address, no memory access) |

### Arithmetic & Logic

| Instruction | Effect |
|---|---|
| `add S, D` | `D = D + S` |
| `sub S, D` | `D = D - S` |
| `imul S, D` | Signed multiply: `D = D * S` |
| `xor S, D` | `D = D ^ S` |
| `and S, D` | `D = D & S` |
| `or S, D` | `D = D \| S` |
| `inc D` / `dec D` | `D++` / `D--` |
| `neg D` | `D = -D` |
| `not D` | `D = ~D` |
| `sal/shl k, D` | Left shift |
| `sar k, D` | Arithmetic right shift |
| `shr k, D` | Logical right shift |

### `lea` is Magic

`leaq` doesn't access memory — it just **computes the address**. Compilers use it as a 3-operand add/multiply:

```
leaq 7(%rdi, %rsi, 4), %rax     # rax = rdi + 4*rsi + 7
leaq (%rdi, %rdi, 2), %rax      # rax = rdi * 3
leaq (,%rdi, 8), %rax           # rax = rdi * 8
```

### Assembly Idioms

| Idiom | Meaning |
|---|---|
| `xor %eax, %eax` | `eax = 0` (smaller encoding than `mov $0, %eax`) |
| `test %rax, %rax` | Sets flags based on `rax` (used before conditional jump) |
| `cmp B, A` | Sets flags based on `A - B` |
| `lea k-1(%r), %s; test; cmovns; sar $k` | Signed division by `2^k` |
| `(addr, idx, 4)` | Indexing into `int` array |
| `(addr, idx, 8)` | Indexing into pointer/`long` array |

---

## 5. Control Flow in Assembly

### Condition Codes (Flags)

Set by `cmp`, `test`, and most arithmetic instructions:

- **CF (Carry Flag):** unsigned overflow
- **ZF (Zero Flag):** result was zero
- **SF (Sign Flag):** result was negative (high bit set)
- **OF (Overflow Flag):** signed overflow

### Conditional Set/Move/Jump Suffixes

| Suffix | Meaning | Test |
|---|---|---|
| `e`/`z` | Equal / Zero | `ZF` |
| `ne`/`nz` | Not Equal | `~ZF` |
| `s` | Negative | `SF` |
| `ns` | Non-negative | `~SF` |
| `g` | Greater (signed) | `~(SF^OF) & ~ZF` |
| `ge` | ≥ (signed) | `~(SF^OF)` |
| `l` | Less (signed) | `SF^OF` |
| `le` | ≤ (signed) | `(SF^OF) \| ZF` |
| `a` | Above (unsigned >) | `~CF & ~ZF` |
| `ae` | ≥ (unsigned) | `~CF` |
| `b` | Below (unsigned <) | `CF` |
| `be` | ≤ (unsigned) | `CF \| ZF` |

Used as: `je`, `jne`, `jg`, `setl`, `cmovne`, etc.

### `cmp B, A` reads as "compare A to B"

So `cmp $5, %eax; jl L` jumps if `eax < 5`. Operand order is reversed from intuition.

### Loop Patterns

**While loop (jump-to-middle):**
```
    jmp .Ltest
.Lloop:
    <body>
.Ltest:
    <condition>
    jcc .Lloop
```

**For loop (do-while transform):**
```
    <init>
    jmp .Ltest      # initial test (sometimes skipped if known true)
.Lloop:
    <body>
    <update>
.Ltest:
    <condition>
    jcc .Lloop
```

**Translating `for (i = 0; i < n; i++)`:**
- Init: `mov $0, %ecx`
- Update: `add $1, %ecx`
- Test: `cmp %esi, %ecx; jl ...` (if `n` is in `%esi`)

### Switch Statements

Compiled with **jump tables** when cases are dense:
```
    cmpq $5, %rdi
    ja .Ldefault
    jmp *.Ltable(,%rdi,8)
.Ltable:
    .quad .Lcase0
    .quad .Lcase1
    ...
```

---

## 6. Procedures, Stack & Calling Convention

### x86-64 Linux Calling Convention

**First 6 integer/pointer arguments:** `%rdi, %rsi, %rdx, %rcx, %r8, %r9` (in order)

**Return value:** `%rax` (and `%rdx` for 128-bit returns)

**Stack arguments:** 7th and beyond go on the stack

**Caller-saved (volatile):** `%rax, %rcx, %rdx, %rsi, %rdi, %r8–%r11` — caller must save before `call` if needed

**Callee-saved (non-volatile):** `%rbx, %rbp, %r12–%r15` — callee must restore before returning

**Stack pointer:** `%rsp` — must be 16-byte aligned at function entry

### Stack Frame Anatomy

```
High addresses
   │ Caller's frame   │
   ├──────────────────┤
   │ Args 7+          │ <- pushed by caller
   ├──────────────────┤
   │ Return address   │ <- pushed by `call`
   ├──────────────────┤  <- %rsp on entry
   │ Saved %rbp       │ (optional, frame pointer)
   ├──────────────────┤
   │ Saved callee-    │
   │ saved regs       │
   ├──────────────────┤
   │ Locals           │
   ├──────────────────┤
   │ Args for callees │ <- pushed/space allocated for inner calls
   └──────────────────┘  <- %rsp now
Low addresses
```

### Function Prologue/Epilogue

**Prologue:**
```
pushq %rbp              # save old frame pointer
movq %rsp, %rbp         # set new frame pointer (optional)
subq $N, %rsp           # allocate locals
pushq %rbx              # save callee-saved regs we'll use
```

**Epilogue:**
```
popq %rbx               # restore callee-saved
addq $N, %rsp           # deallocate locals (or `leave`)
popq %rbp
ret
```

### `call` and `ret`

- `call addr`: pushes return address (8 bytes), jumps to `addr`
- `ret`: pops return address into `%rip`

### Recursion Patterns

- Save needed values in **callee-saved registers** (so they survive recursive calls)
- Common pattern: `pushq %rbx; movq %rdi, %rbx;` — save arg in `%rbx` for use after recursive call

---

## 7. Arrays, Structs & Unions

### Array Basics

```c
int A[10];       // 10 ints = 40 bytes contiguous
A[i]   ≡  *(A + i)
&A[i]  ≡  A + i  ≡  (char*)A + i*sizeof(int)
```

**Multidimensional arrays are row-major:**
```c
int M[R][C];
M[i][j] is at offset (i*C + j) * sizeof(int)
```

### Pointer Arithmetic

`p + i` advances by `i * sizeof(*p)` bytes. Always.

### Struct Alignment Rules (x86-64)

1. Each field aligns to a multiple of its own size (or its alignment).
   - `char` → align 1
   - `short` → align 2
   - `int`, `float` → align 4
   - `long`, `double`, pointers → align 8
2. **Struct alignment** = max alignment of any field
3. **Struct size** is rounded up to a multiple of the struct's alignment (tail padding)
4. **Nested struct** has alignment equal to its own max field alignment

### Layout Procedure

```c
struct S {
    char a;     // offset 0, size 1
                // pad to align next field
    long b;     // offset 8, size 8
    short c;    // offset 16, size 2
                // pad if needed for next field
    int d;      // align 4, so pad 2 bytes; offset 20, size 4
};
// Total: 24 bytes (already multiple of 8)
```

### Worked Example

```c
struct my_struct {
    char a;       // offset 0
    // pad 7 bytes
    long b;       // offset 8
    short c;      // offset 16
    // pad 6 bytes (next field aligns 8)
    struct {
        float *d[2];  // 2 × 8 = 16 bytes; align 8
    } f;          // offset 24, size 16
    float e;      // offset 40
    // pad 4 bytes (struct must be multiple of 8)
};
// Total: 48 bytes
```

### Reordering for Compactness

Group large fields first to minimize padding:
```c
// 24 bytes (compact)
struct Good { long b; int d; short c; char a; };

// 32 bytes (wasteful)
struct Bad  { char a; long b; short c; int d; };
```

### Unions

All members share the same memory; size = max member size, alignment = max member alignment. Useful for:
- Reinterpreting bits (e.g., `float` ↔ `int`)
- Tagged variants (with a separate tag field)

---

## 8. Buffer Overflow & Security

### How Stack Smashing Works

```c
void vulnerable() {
    char buf[8];
    gets(buf);   // no bounds check!
}
```

If user inputs > 8 bytes, the overflow corrupts:
1. Other locals
2. Saved registers
3. Saved `%rbp`
4. **Return address** ← attacker target

### Mitigations

| Mitigation | How it works |
|---|---|
| **Stack canaries** | Random value placed before return address; checked on return |
| **ASLR** (Address Space Layout Randomization) | Stack/heap base randomized |
| **NX bit** (No-eXecute) | Stack pages marked non-executable |
| **PIE** (Position-Independent Executable) | Code base also randomized |

### Attack Types

- **Code injection:** put shellcode in buffer, redirect return address to it (defeated by NX)
- **Return-oriented programming (ROP):** chain existing code "gadgets" ending in `ret` (defeats NX)

---

## 9. Linking

### Compilation Pipeline

```
source.c → [preprocessor] → source.i → [compiler] → source.s
        → [assembler] → source.o → [linker + libs] → executable
```

### Symbols

Every `.o` file has a symbol table. Each symbol is either:

- **Defined** in this file (function body, initialized global)
- **Referenced** but not defined (extern)

### Symbol Categories

| Category | Storage | Examples |
|---|---|---|
| **Global** | Visible to other modules | `int x = 5;`, functions |
| **Local** | This module only | `static` variables, function locals (not in symbol table) |
| **External** | Defined elsewhere | `extern int x;` |

### Strong vs Weak

- **Strong:** functions, **initialized** globals
- **Weak:** **uninitialized** globals (and `extern` declarations)

### Linker Rules for Duplicate Symbols

1. ❌ Two strong symbols with same name → **error**
2. ✅ One strong + many weak → **strong wins**
3. ⚠️ Multiple weak → **linker picks one** (often the largest); silent corruption risk

⚠️ **Modern GCC (default `-fno-common`)** treats this stricter — multiple weak symbols may also error. Older GCC with `-fcommon` allowed it.

### Memory Segments

| Segment | Contents |
|---|---|
| `.text` | Code (read-only, executable) |
| `.rodata` | String literals, `const` globals |
| `.data` | Initialized non-zero globals/statics |
| `.bss` | Uninitialized or zero-initialized globals/statics (no actual bytes in file) |
| **Heap** | `malloc`'d memory; grows up |
| **Stack** | Function calls, locals; grows down |

### Static vs Dynamic Libraries

- **Static (`.a`):** archive of `.o` files; linker copies needed code into the executable at link time
- **Dynamic (`.so`):** loaded at runtime; smaller executables, can update libraries without recompiling

### Library Link Order ⚠️

GCC processes the command line **left to right**, maintaining a list of unresolved symbols.

- A `.a` file only contributes objects that resolve **currently unresolved** symbols
- ⚠️ **Files using a library must come BEFORE the library**

```bash
gcc main.c libsum.a       # ✅ works
gcc libsum.a main.c       # ❌ symbol not found
```

### Static vs Extern vs Default

```c
int x;            // global, weak (uninit)
int x = 0;        // global, strong (init)
static int x;     // file-local
extern int x;     // declaration only, defined elsewhere
```

---

## 10. Memory Hierarchy & Caches

### Hierarchy (top = fast/small, bottom = slow/big)

```
Registers          (~1 cycle)
L1 cache           (~4 cycles)
L2 cache           (~10 cycles)
L3 cache           (~30 cycles)
DRAM               (~100 cycles)
SSD/disk           (~100,000 cycles)
```

### Locality

- **Temporal locality:** recently accessed → likely accessed again
- **Spatial locality:** addresses near recent accesses → likely accessed soon

### Cache Anatomy

A cache has:
- **S sets**, each with **E lines** (a.k.a. ways)
- Each line has:
  - **Valid bit** (1 if line holds data)
  - **Tag** (identifies which block)
  - **Block** of `B` bytes of data

**Total cache capacity:** `C = S × E × B`

### Cache Types

| Type | E (lines/set) | Notes |
|---|---|---|
| **Direct-mapped** | 1 | Fast, simple, suffers from conflict misses |
| **Set-associative** | 2, 4, 8, ... | Most common (e.g., "8-way") |
| **Fully-associative** | All blocks in one set | Flexible but expensive hardware |

### Address Decomposition

For a cache with `B = 2^b` byte blocks and `S = 2^s` sets:

```
| Tag (rest) | Set Index (s bits) | Block Offset (b bits) |
```

- **Block offset:** which byte within the block
- **Set index:** which set to look in
- **Tag:** identifies which block currently in the set

### Cache Operation

1. Extract set index from address; go to that set.
2. Check all lines in that set for valid bit + matching tag.
3. **Hit:** return data at block offset.
4. **Miss:** fetch block from next level; place in set (evict using LRU if full).

### Cache Misses

- **Cold (compulsory):** first access; unavoidable
- **Conflict:** would have hit but evicted due to limited associativity
- **Capacity:** working set > cache size

### Write Policies

- **Write-back + write-allocate:** writes go to cache; only flushed on eviction; missed writes load the block first. (Common.)
- **Write-through + no-write-allocate:** writes go directly to memory; missed writes don't load the block.

### Cache Performance Recipe (Exam)

For a sequence of accesses:

1. Compute address breakdown.
2. For each access:
   - Compute set index = `(addr / B) mod S`
   - Compute tag = `addr / (B × S)`
3. Track contents of each set (using LRU for eviction).
4. Mark hit/miss.

### Common Patterns to Recognize

**Sequential access on int array, 16B blocks:**
- 1 miss every 4 accesses → 25% miss rate

**Two arrays at start addresses differing by exact cache size:**
- They map to identical sets → **conflict-miss disaster** in direct-mapped
- 100% miss rate possible
- More associativity (≥ 2-way) often fixes this

**Stride > block size:**
- Every access misses → 100% miss rate (no spatial locality benefit)

### Matrix Traversal

```c
// Row-major access (good)
for (i = 0; i < N; i++)
    for (j = 0; j < N; j++)
        sum += A[i][j];

// Column-major access (bad)
for (j = 0; j < N; j++)
    for (i = 0; i < N; i++)
        sum += A[i][j];   // stride = N*sizeof(int)
```

### Cache-Friendly Coding Tips

- Loops with stride 1 (row-major in C)
- Block/tile algorithms for matrix operations
- Avoid pointer-heavy structures with poor locality
- Pad arrays to avoid catastrophic conflict misses

---

## 11. Exceptional Control Flow: Processes

### Process

A process is an instance of a running program with:
- Its own **virtual address space**
- Its own **register state**
- Open file descriptors

### `fork()`

Creates a (nearly) identical child process.

```c
pid_t pid = fork();
if (pid == 0) {
    // CHILD code
} else if (pid > 0) {
    // PARENT code; pid = child's PID
} else {
    // error
}
```

⚠️ **Both processes continue from the line after `fork()`.** They have **separate copies** of all memory (copy-on-write).

### Process Counting Recipe

To count outputs after `n` forks:
- After 1 fork: 2 processes
- After 2 forks: up to 4 processes
- After k forks: up to `2^k` processes
- Draw the **process tree** to track who's alive when

### `exec` Family

Replaces current process's program with a new one. Same PID, but new code/data.
```c
execve(path, argv, envp);
// returns only on error
```

### `wait` / `waitpid`

Parent waits for child(ren) to terminate and reaps them (frees their PCB).
```c
pid_t wait(int *status);                    // wait for any child
pid_t waitpid(pid_t pid, int *status, int opts);
// opts: WNOHANG = don't block; WUNTRACED, etc.
```

⚠️ **Zombie:** child has exited but not been reaped. Reap them or they leak resources.

### Status Macros

```c
WIFEXITED(status)    // child exited normally
WEXITSTATUS(status)  // exit code
WIFSIGNALED(status)  // killed by signal
WTERMSIG(status)     // signal number
```

### `exit()` vs `_exit()` vs `return`

- `exit(n)`: clean exit, runs atexit handlers, flushes buffers
- `_exit(n)`: immediate exit, no cleanup (use in signal handlers / after fork)
- `return n` from main: equivalent to `exit(n)`

---

## 12. Exceptional Control Flow: Signals

### What is a Signal?

A small int message from kernel/process to a process. Examples:

| Signal | Number (typical) | Meaning |
|---|---|---|
| `SIGINT` | 2 | Ctrl+C |
| `SIGKILL` | 9 | Force kill (can't catch/block) |
| `SIGSEGV` | 11 | Invalid memory access |
| `SIGCHLD` | 17 | Child stopped/terminated |
| `SIGSTOP` | 19 | Stop (can't catch/block) |
| `SIGCONT` | 18 | Continue stopped process |
| `SIGUSR1`/`SIGUSR2` | 10/12 | User-defined |

### Signal Lifecycle

1. **Sent** (e.g., `kill(pid, SIGINT)`)
2. **Pending** at recipient
3. **Delivered** (handler runs, or default action: terminate, ignore, stop, continue)

### Per-Signal State

For each signal, the kernel tracks:
- **Pending bit** — only **0 or 1**, no counter!
- **Blocked bit** — if set, the signal stays pending and is not delivered

### ⚠️ Signal Coalescing

**Signals do not queue.** If a signal is pending and another of the same type arrives, the second is **lost** (only one bit). Different signal types can each be pending simultaneously.

### `signal()` and `sigaction()`

```c
signal(SIGCHLD, handler);
// safer: sigaction() with explicit options
```

### Sending Signals

```c
kill(pid, SIGUSR1);          // to a process
raise(SIGUSR1);              // to self (= kill(getpid(),...))
alarm(seconds);              // schedule SIGALRM
```

### Blocking Signals

```c
sigset_t mask, old;
sigemptyset(&mask);
sigaddset(&mask, SIGCHLD);
sigprocmask(SIG_BLOCK, &mask, &old);
// critical section
sigprocmask(SIG_SETMASK, &old, NULL);
```

### Signal Handler Rules

⚠️ **In handlers:**
- Only call **async-signal-safe** functions (`write`, `_exit`, `kill`, `signal`...) — **NOT `printf`, `malloc`, `free`!**
- Save/restore `errno` if you call functions that might modify it
- Use `volatile sig_atomic_t` for shared variables
- Keep handlers short

### SIGCHLD Handler Idiom

To handle multiple children dying together (avoid coalescing bug):
```c
void handler(int sig) {
    int saved_errno = errno;
    while (waitpid(-1, NULL, WNOHANG) > 0)
        ;  // reap all available
    errno = saved_errno;
}
```

### Important Facts (Exam Trivia)

- ✅ Process can send signal to itself
- ✅ Some signals (SIGKILL, SIGSTOP) **cannot be blocked or caught**
- ✅ During handler, **same signal** is automatically blocked, but **other signals** may interrupt
- ❌ Handlers cannot use `printf`, `malloc` safely
- ❌ Signals do **not** queue per-type

### Signals + fork() Interactions

- After `fork()`, child inherits parent's signal handlers and signal mask
- After `exec()`, custom handlers reset to default; mask preserved

---

## 13. Virtual Memory & Address Translation

### The Big Picture

Each process has its own **virtual address space**. The MMU translates virtual addresses (VA) to physical addresses (PA) using a **page table** maintained by the OS.

### Pages

- **Page:** fixed-size chunk of virtual memory (e.g., 4 KB)
- **Frame (or Physical Page):** same-sized chunk in physical memory
- **VPN** (Virtual Page Number) → **PPN** (Physical Page Number) via page table
- **Offset within page** is preserved (VPO == PPO, same bits)

### Address Decomposition

For page size `P = 2^p`:

```
Virtual Address (n bits):
| VPN (n - p bits)  |  VPO (p bits) |

Physical Address (m bits):
| PPN (m - p bits)  |  PPO (p bits) |
```

### Page Table Entry (PTE)

Per VPN, the PTE typically holds:
- **Valid bit**: is the page in physical memory?
- **PPN**: where in physical memory
- **Permission bits**: read/write/execute, user/kernel
- **Dirty bit, Reference bit, ...**

### Translation Steps

1. Extract VPN from VA.
2. Look up page table entry at index VPN.
3. If **valid = 1**: extract PPN; PA = PPN ‖ VPO (concatenate).
4. If **valid = 0**: **page fault** (kernel handles: load page from disk, or kill if invalid).

### TLB (Translation Lookaside Buffer)

A small cache of recent **PTEs** to skip the page-table walk.

- Typically **set-associative** (e.g., 16 entries, 2-way → 8 sets)
- Indexed by **TLB index** (low bits of VPN)
- Tagged by **TLB tag** (high bits of VPN)

### Address Decomposition for TLB

```
VPN = | TLBT (high bits) | TLBI (low bits) |
```

If TLB has `2^t` sets:
- TLBI = `t` bits (low bits of VPN)
- TLBT = `(VPN bits) - t` bits (high bits of VPN)

### Translation Pipeline

```
VA → split into VPN + VPO
VPN → split into TLBT + TLBI
Look up TLB at set TLBI:
   TLB hit? → use cached PPN
   TLB miss? → walk page table:
       Page valid? → cache in TLB, use PPN
       Page invalid? → PAGE FAULT
PA = PPN ‖ VPO
```

### Worked Example: 20-bit VA, 18-bit PA, 1024-byte pages, 16-entry 2-way TLB

- Page size 1024 = 2¹⁰ → **VPO = PPO = 10 bits**
- VPN = 20 - 10 = **10 bits**
- PPN = 18 - 10 = **8 bits**
- TLB sets = 16/2 = 8 = 2³ → **TLBI = 3 bits**
- TLBT = 10 - 3 = **7 bits**

VA bit field: `[19:13] = TLBT, [12:10] = TLBI, [9:0] = VPO`
PA bit field: `[17:10] = PPN, [9:0] = PPO`

### Translation Walkthrough Example

VA = `0x078E6` = `0000 0111 1000 1110 0110`

- VPO = bits [9:0] = `11 1110 0110` = `0x0E6`
- VPN = bits [19:10] = `0000 0111 10` = `0x01E`
- TLBI = low 3 bits of VPN = `110` = `0x6`
- TLBT = high 7 bits of VPN = `0000 011` = `0x03`

Then look up TLB set 6 with tag 03 → either hit or miss → consult PT if miss.

### Multi-Level Page Tables

For very large address spaces, page tables themselves are huge. Solution: hierarchical page tables.

- e.g., x86-64 uses **4-level page table**, each level indexed by 9 bits of VPN
- VA = `[L1 idx | L2 idx | L3 idx | L4 idx | offset]`

### Page Fault

Triggered when:
- Valid bit = 0 (page on disk or not allocated)
- Permission violation (write to read-only, etc.)

Kernel handler:
1. Find a free physical frame (evict if needed)
2. Load the page from disk (or zero-fill)
3. Update PTE
4. Restart faulting instruction

### Why VM is Useful

1. **Isolation:** processes can't see each other's memory
2. **Memory > physical RAM:** disk-backed virtual memory
3. **Sharing:** multiple processes can map same physical page (libraries, fork copy-on-write)
4. **Protection:** read-only `.text`, no-execute stack

---

## 14. Common Exam Patterns & Traps

### Bit-Level Trick Catalog

| Expression | Reduces to |
|---|---|
| `~x + 1` | `-x` |
| `~x` | `-x - 1` |
| `x ^ x` | `0` |
| `x \| ~x` | `-1` (all 1s) |
| `(x + (1<<k) - 1) >> k` | Signed divide by `2^k` (for negative `x`) |
| `x & (x - 1)` | Clears lowest set bit |
| `x & -x` | Isolates lowest set bit |

### Counterexamples for Common False Claims

| Claim | Counterexample |
|---|---|
| `x * 2 > x` for all `int x` | `x = INT_MAX` |
| `-x < 0` when `x > 0` | (true, but `-INT_MIN = INT_MIN < 0`) |
| `x < y` ↔ `-x > -y` | `x = INT_MIN, y = 0` |
| Signed `x < unsigned u` works as expected | `x = -1, u = 0` (false negative) |
| Float arithmetic is associative | `1e20 + 1 - 1e20 ≠ 1` |

### Assembly Reading Cheat-Recipe

1. Identify register usage: `%rdi/%rsi/...` = args, `%rax` = return.
2. Find the loop: `jmp` forward followed by labels and a back-edge `jcc`.
3. Recognize idioms:
   - `lea` = arithmetic
   - `cmov` = branchless if-else
   - `(r1, r2, scale)` = array indexing
   - `lea k-1; test; cmovns; sar k` = signed `/2^k`
4. Trace one iteration carefully; the rest follows.

### Linking Trap Catalog

- Library order: `gcc main.c lib.a`, **not** `gcc lib.a main.c`
- `static` makes things file-local
- Multiple uninit globals of different types → silent corruption
- Initialized non-zero → `.data`; uninit/zero → `.bss`; functions → `.text`; string literals → `.rodata`

### Cache Trap Catalog

- Two arrays separated by exactly cache size → 100% miss in direct-mapped
- Stride > block size → no spatial locality benefit
- Write-allocate caches: writing to a missed line loads the entire block first
- Cold misses are unavoidable; conflict misses are reduceable with associativity

### Process/Signal Trap Catalog

- Always count from a process tree diagram
- Variables after `fork()` are **separate copies**
- `printf` buffers may flush twice in child if not flushed before fork
- Signals don't queue — handler counts ≠ signal-send counts
- `printf` is **not** safe in handlers; use `write` instead
- Reap children in a `waitpid(-1, ..., WNOHANG)` loop

### VM Trap Catalog

- TLB index uses **low bits of VPN**, tag uses **high bits**
- VPO bits = PPO bits = log₂(page size); they're never translated
- PA size and VA size can differ
- TLB miss ≠ page fault; page fault is when PT entry says invalid

---

## Quick Reference: Bit Field Decomposition Cheatsheet

### For a Cache

Given **B = 2^b** byte blocks, **S = 2^s** sets:
- Block offset: `b` bits (low)
- Set index: `s` bits (next)
- Tag: rest (high)

### For Virtual Memory

Given page size **P = 2^p** bytes, VA = `n` bits, PA = `m` bits:
- VPO = `p` bits (low of VA)
- VPN = `n - p` bits (high of VA)
- PPO = `p` bits (low of PA, same as VPO)
- PPN = `m - p` bits (high of PA)

### For TLB

Given TLB sets = `2^t`, VPN bits = `v`:
- TLBI = `t` bits (low of VPN)
- TLBT = `v - t` bits (high of VPN)

### Combined VA Layout (when using both cache and TLB on physical addresses)

```
| TLBT | TLBI | VPO |     ← virtual address split
| TAG  | SET  | OFF |     ← cache split (on PA, but VPO is same as PPO)
```

If page size ≥ cache size, the cache index falls within VPO and you can index the cache **before translation finishes** (virtually-indexed, physically-tagged caches).

---

## Top 30 Things to Memorize

1. `~x = -x - 1`
2. `-INT_MIN = INT_MIN` (overflow)
3. Mixed signed/unsigned compare → signed promoted to unsigned
4. `lea` is for arithmetic, doesn't access memory
5. `cmov` is branchless if-else
6. `(base, idx, scale)` is array indexing
7. Signed div by `2^k`: `(x + (x<0 ? 2^k - 1 : 0)) >> k`
8. Calling convention args: `rdi, rsi, rdx, rcx, r8, r9`
9. Caller-saved: `rax, rcx, rdx, rsi, rdi, r8-r11`; callee-saved: `rbx, rbp, r12-r15`
10. Return value: `%rax`
11. Stack grows toward lower addresses
12. `pushq`: `*--rsp = X`; `popq`: `X = *rsp++`
13. `cmp B, A` sets flags as if computing `A - B`
14. Struct field aligns to its own size; total rounds up to max field alignment
15. `.text` (code), `.data` (init non-zero), `.bss` (uninit/zero), `.rodata` (const)
16. Library order: files using lib come BEFORE the lib
17. Strong/weak: strong wins; multiple weak = picked one (often largest)
18. Cache address = `[Tag | Set | Offset]`; offset = log₂(block), set = log₂(num sets)
19. Direct-mapped cache + two arrays at cache-size offset = catastrophe
20. Write-allocate + write-back means writes load the block first
21. `fork()` returns 0 in child, child PID in parent
22. After `fork()`, separate memory spaces (copy-on-write)
23. To count prints with fork: draw the process tree
24. `wait`/`waitpid` reaps zombie children
25. Signals don't queue per-type; coalesce
26. SIGKILL and SIGSTOP can't be blocked or caught
27. In handlers: no `printf`, no `malloc`; use `write`, `_exit`
28. SIGCHLD handler: `while(waitpid(-1, NULL, WNOHANG) > 0);`
29. VM: VA = `[VPN | VPO]`, PA = `[PPN | PPO]`; offsets identical
30. TLB: tag = high bits of VPN, index = low bits of VPN

---

## Process Tree Quick Examples

```c
// Example 1
fork(); fork();
// 4 processes total
```

```c
// Example 2
for (i = 0; i < 2; i++) fork();
// 4 processes total (same as above)
```

```c
// Example 3
if (fork() == 0) fork();
// Parent forks; child also forks → 3 processes
```

```c
// Example 4: counting prints
for (i = 0; i < n; i++) {
    fork();
    printf("hi\n");
}
// Print count: 2 + 4 + 8 + ... + 2^n = 2^(n+1) - 2
```