CSE361_Final_Note

Table of Contents

1. Number Representation & Bit-Level Operations
2. Integer Arithmetic & Overflow
3. Floating Point
4. x86-64 Assembly
5. Control Flow in Assembly
6. Procedures, Stack & Calling Convention
7. Arrays, Structs & Unions
8. Buffer Overflow & Security
9. Linking
10. Memory Hierarchy & Caches
11. Exceptional Control Flow: Processes
12. Exceptional Control Flow: Signals
13. Virtual Memory & Address Translation
14. Common Exam Patterns & Traps

1. Number Representation & Bit-Level Operations

Type Sizes (x86-64 Linux)

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

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.

-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

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

| 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

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

Operand Forms

Instruction Suffixes (Operand Size)

Common Data Movement

Arithmetic & Logic

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

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

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

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:

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

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

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:

// 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

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

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

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

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

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

Static vs Extern vs Default

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

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

// 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.

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.

execve(path, argv, envp);
// returns only on error

wait / waitpid

Parent waits for child(ren) to terminate and reaps them (frees their PCB).

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

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 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()

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

Sending Signals

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

Blocking Signals

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):

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

Counterexamples for Common False Claims

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

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

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

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

// 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