UNIX Weapons School Weekplan
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
- 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.
- Memory fences.
- Transactional memory.
- 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
- 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.
- 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 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).
- Local topology discovery
Week 8: Heterogeneity
- TCP offload engines
- SolarFlare's OpenPacket
- Microsoft AMP
- NVIDIA's CUDA
- System / guest emulation
- Transmeta CMS (Code Morphing Software)
- Popek and Goldberg virtualization requirements / KVM / Xen
Week 9: The future of systems programming
- Amorphous computing
- RAIN/RAIM, EMC-aware programming
- COMA, ccNUMA, directories, SCI, SCA
- Computational memory
- Software-defined networking
- MRAM / FeRam / PRAM / SONOS