UNIX Weapons School

UNIX WEAPONS SCHOOL 2013 FLYER

This syllabus is TENTATIVE and PRELIMINARY!

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

UNIX Weapons School is an intense elective practicum. Its primary goal is to train formidably competent systems programmers.

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.
• THE WORLD FATHER aka UNIX
  • The Linux virtual memory implementation on x86
  • The FreeBSD/Dragonfly virtual memory implementation
  • The Linux process schedulers
  • The Linux I/O schedulers
• OUR EARTH MOTHERS aka C/C++
  • The system call interface.
  • Process-level memory management.
  • The C standard library.
  • Xmacros / 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.
  • TLB invalidation and IPIs
  • 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 (sorting networks). Dancing links. Timer wheels.
• Searching large spaces: Trees. PATRICIA tries. Skip lists. Suffix trees. Automata search. Interval trees.
• Searching by content: Hashes. Algorithmic complexity attacks. Universal hashes. Cuckoo hashing. Adaptive perfect hashes.
• Searching huge spaces: VLHU. 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. Asynchronous 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

• SSA and Basic Blocks, 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

Allotrios

• Windows aka Unfathomably Wretched Function Naming: I/O Completion Ports. With Fibers come Heaps.
• Libraries: objdump, nm, and how to design a shared library.
• Internationalization. UTF8
• 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

• Sampling theory of Nyquist
• 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 and CAKE queue disciplines.
• IPv6. Algorithms for IPv6. Zeroconf. PXE. Ad-hoc and mesh networking. Algorithms for fragmentation and sequencing. Intranet threats.
• Packet sockets. Linux's netlink(7).
• Local topology discovery

Week 8: Heterogeneity

Hardware

• TCP offload engines
• SolarFlare's OpenPacket
• Microsoft AMP
• NVIDIA's CUDA
• OpenCL

Software

• System / guest emulation
• Transmeta CMS (Code Morphing Software)
• Popek and Goldberg virtualization requirements / KVM / Xen

Week 9: The future of systems programming

• C++11
• Amorphous computing
• RAIN/RAIM, EMC-aware programming
• COMA, ccNUMA, directories, SCI, SCA
• Computational memory
• Software-defined networking
• MRAM / FeRam / PRAM / SONOS