UNIX Weapons School Weekplan

UNIX WEAPONS SCHOOL 2013

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

Week 1: C/C++ development in the x86 UEFI UNIX environment

• 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: Systems methods for efficient use of memory and buses

• 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.
• Event systems
  • select(), poll(), interaction with signals
  • Linux's epoll, FreeBSD's kqueue. Level- vs edge-triggered events.
  • Everything as events: timerfd, signalfd, V_NODE
  • Wrapping pthread events
  • Multithreaded event engines
  • Robust systems and judicious fork()ing
  • libev, libevent, libtorque

Week 3: Algorithmic methods for efficient use of CPU and memory

• 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: Compilers and their limitations, both theoretical and practical

• 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: Allotrion

• 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

Week 5.2: Parallelism I: Hardware Parallelism

• Models of parallelism aka They're All Shite
• Bit-level parallelism
• Parallelism within a register
• Parallelism among instructions
• Parallelism among memory accesses

Week 6: Parallelism II: Software Parallelism

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

Week 7: Effective use of intranets and the Internet

• 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.
• Packet sockets. Linux's netlink(7).