UNIX Weapons School Weekplan

From dankwiki
Jump to navigation Jump to search

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

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

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