UNIX Weapons School Weekplan

UNIX WEAPONS SCHOOL 2013 FLYER

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

Accept the challenges so that you can feel the exhilaration of victory. -- George S. Patton

Week 1: C/C++ development in the x86 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.
  • rant: code is data and data is code so keep your home directory in source control
• 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.
  • GNU Make
  • 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.

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.

Algorithms for event systems

• select(), poll(), interaction with signals
• Linux's epoll, FreeBSD's kqueue. Level- vs edge-triggered events.
  • Algorithms for oneshot edge-triggered interfaces. Asycnhronous I/O on POSIX systems.
• Everything as events: timerfd, signalfd, V_NODE
• Wrapping pthread events. Multithreaded event engines. Work queues, work stealing, tasklets.
  • Digression: Kernel threads and interrupt handlers
• Robust systems and judicious fork()ing
• libev, libevent, libtorque

Week 4: Compilers and their limitations, both theoretical and practical

• SSA and Basic Blocks, aka Planet of the Compilers
• The Banerjee Test and the Polytopal 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

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

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