Concepts

Data representation

• Abstract machine
• Objects
• Lifetime
  • Static lifetime
  • Automatic lifetime
  • Dynamic lifetime
• Addresses
• Segments
  • Code (aka text)
  • Data
  • Heap
  • Stack
• Bytes
• Type sizes
  • size_t
• Byte order/endianness
• Two’s-complement representation for signed integers
  • Sign bit
• Type alignments
• Data layout
  • Compiler layout vs. abstract machine layout
  • Array layout
  • Struct layout
  • Union layout
  • Pointer representation
  • Padding
  • Malloc rule for alignment
• As-if rule of compiler optimization
  • C++-style memory allocation
• Pointer arithmetic
  • Contrasted with address arithmetic
  • Pointers and iterators
• Undefined behavior
  • Pointer undefined behavior
  • Signed integer undefined behavior
  • Undefined behavior and optimization
  • Sanitizers
• Bitwise arithmetic
  • Bitwise identities: negation; multiplication, division, remainder by powers of two
• Arena allocation

Assembly and machine programming

• Registers
  • General-purpose registers
  • Special-purpose registers
  • Different register sizes
• Calling convention
  • Argument registers
  • Return register
  • Stack alignment
  • Stack frames
  • Caller-saved registers and callee-saved registers
  • push and pop instructions
  • Entry and exit sequence
  • Frame pointer %rbp
• Instruction classes
  • Data movement
  • Computation
  • Control flow
• Address modes and address computations
  • %rip-relative addressing
• Branches
  • Unconditional branches
  • Conditional branches
  • Condition flags
  • test and cmp
• Compiler optimizations
  • Inlining
  • Tail call elimination
  • Argument elision
  • Loop unrolling
  • Arithmetic transformations
• Buffer overflows
  • Return-to-libc attacks
  • Stack canaries
  • Checksum functions

Storage hierarchy

• Caches
  • Processor cache
  • Buffer cache
  • Stdio cache
• File descriptors
• System calls
• Stdio
• Storage hierarchy
  • Storage technologies
  • Financial costs
  • Performance characteristics
• Latency and throughput
• Stable and volatile
• Cache model
  • Slots
  • Blocks
  • Addresses
  • Empty vs. full
  • Dirty vs. clean
• Eviction policies
  • Reference strings
  • Hit vs. miss
  • Hit rate
  • Bélády’s optimal algorithm
  • Bélády’s anomaly
  • FIFO
  • LRU
• Cache associativity
  • Fully-associative
  • Set-associative
  • Direct-mapped
  • Single-slot
• Unit sizes
• Request costs
  • C = NU + R
• Prefetching
• Batching
• Write coalescing
• Coherence
  • Coherent caches
  • Incoherent caches
• Kinds of files
  • Random-access files
  • Streams
  • File position
• Access patterns
  • Sequential
  • Reverse-sequential
  • Strided
  • Seeks
  • Cache alignment
• Memory-mapped I/O
• Advice

Kernel

• Kernel
• Protected control transfer
• Memory isolation
• Process isolation
• Virtualization vs. abstraction
• Attacks
  • Infinite loop
  • Memory attack
  • Fault (divide-by-zero)
• Defenses (hardware features)
  • Timer interrupt
  • Dangerous instructions
  • Current privilege level register
  • Current page table register %cr3
• Page tables
  • Page offset
  • Page indexes
  • Multi-level page table
  • Virtual address vs. physical address
  • Page table flags: P, W, U
• WeensyOS memory layout
  • CGA console and memory-mapped IO
  • WeensyOS control transfer
• System call implementation
  • syscall instruction
  • WeensyOS syscall calling convention
• Protected control transfers
  • Interrupts
  • Traps
  • Faults
• Confused deputy attack
• Scheduling

Shell

• UNIX philosophy
  • Modularity
• Process creation: fork system call (also)
  • Interaction of stdio buffers with fork
  • Virtual address space copied
  • File descriptor table copied
  • File structures shared
• Program running: execvp system call
  • posix_spawn
• [Interprocess communication]
• waitpid system call
  • Zombie processes
  • WIFEXITED, WEXITSTATUS
• Stream communication: pipe system call
  • Pipe dance (how a shell can set up a pipeline a | b)
  • Pipe buffer
  • Blocking behavior of pipes
  • Pipe sieve of Eratosthenes
  • What is a prime number? 🤷🏼‍♂️
  • File descriptor numbers 0, 1, 2
• Polling vs. blocking
• Signals
  • kill system call
  • How to receive a signal (sigaction)
  • Signal race conditions
  • Sleep–wakeup race
  • Self-pipes
  • select system call
  • signalfd system call

Synchronization

• Threads
  • std::thread
• Memory race conditions
  • Fundamental Law of Synchronization
  • Race conditions on basic memory accesses
• std::atomic and atomic instructions
• Mutual exclusion
  • std::mutex
  • lock and unlock operations
  • Polling implementation with atomic increment/decrement, compare-and-swap
  • Dynamic relationship of mutexes to protected state
  • Coarse-grained vs. fine-grained locking
• Condition variables
  • wait, notify_all, notify_one operations
  • Relationship between CVs and mutexes
  • Sleep–wakeup race conditions (solved by CVs)
• Bounded buffer
  • Unsynchronized (incorrect)
  • Mutex synchronization
  • Condition variable synchronization
• Scoped mutexes
  • std::unique_lock
  • std::scoped_lock
• Networking
  • Packets
  • System calls: socket, bind, listen, accept, connect
  • Three-way handshake
• Networking and synchronization
  • Denial-of-service attack
  • Thread-per-connection model
• Deadlock
  • Waiting-for/owned-by diagram
  • Lock order
• The 10,000 connection problem
  • Event-driven programming (select)
  • Connections vs. active connections
  • Persistent read set in kernel (epoll)