UNIX Weapons School Weekplan

This syllabus is TENTATIVE! It covers only lecture material, not the design meetings.

Summary

• Week 1: C/C++ development in the x86 UEFI UNIX environment
• Week 2: Systems methods for efficient use of memory and buses
• Week 3: Algorithmic methods for efficient use of CPU and memory
• Week 4: Compilers and their limitations, both theoretical and practical
• Week 5: Parallelism I: Hardware parallelism
• Week 6: Parallelism II: Software parallelism
• Week 7: Effective use of intranets and the Internet
• Week 8: Debugging, dynamic work loads, and pathological behaviors
• Week 9: C++11, heterogeneity, and the future of systems programming

Week 1

• SHELL LIFE aka Things I Hope You Already Know
  • Job control
  • GNU readline
  • SSH tricks
  • effective use of interactive shells
  • shell scripting idioms.
• HOW COAL BECOMES CAT PICTURES aka Attack of the clone()s
  • UEFI. UNIX boot sequence.
  • Everything you wanted to know about /dev and /sys and /proc but never found out.
  • Where a process comes from, what composes it while alive, and where it goes when it dies.
  • lsof, netstat, memstat, etc
• C/C++ UNIX DEVELOPMENT aka Onward Christian Soldiers
  • Highlights of GCC, G++, LLVM, Clang, ICC, and NVCC.
  • strace, ltrace, ptrace().
  • GDB tricks.
  • Profiling with perf.
  • UNIX resource management.
  • Linker tricks both stupid and less stupid.
  • The C and C++ machine models.
• OUR EARTH MOTHERS aka C/C++
  • The system call interface.
  • Process-level memory management.
  • The C standard library.
  • The STL.
  • A glimpse of template metaprogramming

Week 2

• YOUR FRIEND THE COMPUTER aka Computer Architecture in Thirty Minutes.
  • Intel Core processors.
  • The memory hierarchy.
  • Branch prediction.
  • SIMD.
  • Memory fences.
  • Transactional memory.
  • Predication.
• DOUBLE-COPIED I/O aka Definitely More Copying Than Required.
  • C/C++ I/O using stdio.h and streams. Interactions of standard library buffering and I/O.
  • Semantics and side-effects of the I/O model.
  • popen() and the seven thousand ways it can be incorrectly used.
• SINGLE-COPIED I/O aka Not Good Enough, Try Again.
  • UNIX I/O using bytestreams, datagrams, and sequenced packets.
  • The AF_UNIX namespace.
  • That mysterious EAGAIN.
• ZERO-COPY I/O aka Now We're Getting Somewhere.
  • Mmap and shared memory.
  • CLONE_VM and a glimpse of threads.
  • RDMA. The PCIe bus.
• NEGATIVE-COPY I/O aka Oh Shit! There Go My Pages!
  • COW games.
  • sendfile() and TCP.
  • splice() your way to success.
• MORE MEMORY aka When in Doubt, Blame Memory.
  • Interactions of disk, disk paging, memory paging, caching, registers, and multiprocessing.
  • Memory characteristics of long-lived programs.
  • Life in a post-paged world.
  • Computational memory.
  • NUMA and you.

Week 3

• IN THE GRIM FUTURE OF WEEK 3 THERE ARE NO AKAs, ONLY ALGORITHMS
• Searching small spaces: Constant sorts. Dancing links.
• Searching large spaces: Trees for smoking and computing. PATRICIA

  tries. Skip lists. Suffix trees. Automata search.

• Searching by content: Hashes for smoking and computing. Algorithmic

  complexity attacks. Universal hashes. Cuckoo hashing. Adaptive

perfect hashes.

• Searching huge spaces: VLRU. Octet and quadtrees. Enumeration by

method of linear congruence and other space-filling parlor tricks.

• Real-time machine learning: Support vector machines. Non-negative

matrix factorization. Hierarchal hashing. Hidden Markov models.

• Three impossible things before breakfast: Detecting an infinite loop,

transforming an infinite list, and computing without executing.

• Yes, You Really Have to Learn Fourier Transforms.

Week 4

• SSA, aka Planet of the Compilers
• The Banerjee Test and the Polyhedral Model, aka Beneath the Planet

of the Compilers

• The limits of compiler-based optimization, aka Escape from the

Planet of the Compilers

• Inline assembly, aka Conquest of the Planet of the Compilers
• PGO and Genetic-O aka Battle for the Planet of the Compilers

Week 5.1

• Windows aka Unfathomably Wretched Function Naming: I/O Completion

Ports. With Fibers come Heaps.

• Libraries: objdump, nm, and how to design a shared library.
• Unpleasant Details of the UNIX Environment aka What Stevens Forgot

to Tell You. The OOM killer. Atime. Fragmentation, a spectre haunting your userspace. Hardware failures.

• Build systems aka They're All Shite
• Models of parallelism aka They're All Shite

Week 5.2

• Bit-level parallelism
• Parallelism within a register
• Parallelism among instructions
• Parallelism among memory accesses

Week 6

• Parallelism among tasks
• Algorithms simulating parallelism and nondeterminism.
• POSIX threads. Userspace threading. Coroutines.
• Parallel languages and libraries. IPP and TBB.

Week 7

• The Linux virtual memory implementation on x86
• The FreeBSD/Dragonfly virtual memory implementation
• The Linux process schedulers
• The Linux I/O schedulers
• Queueing theory of Kleinrock. The Linux packet queue disciplines
• The Internet backbone. Preserving service via anycast networking.

   Threats to the Internet. PMTUD / MSS black holes.

• Bufferbloat. Perils of the end-user network. Hardware design of

fast networking devices. The CODEL queue discipline.

• IPv6. Algorithms for IPv6. Zeroconf. PXE. Ad-hoc and mesh networking.

Algorithms for fragmentation and sequencing. Intranet threats.