Check out my first novel, midnight's simulacra!

UNIX Weapons School Weekplan: Difference between revisions

From dankwiki
No edit summary
 
(53 intermediate revisions by the same user not shown)
Line 1: Line 1:
This syllabus is '''''TENTATIVE!''''' It covers only lecture material, not the design meetings.
==Week 1: C/C++ development in the x86 UNIX environment==
__NOTOC__
 
* Week 1: C/C++ development in the x86 UEFI UNIX environment
* Week 2: Systems methods for efficient use of memory and buses
* Week 3: Algorithmic methods for efficient use of CPU and memory
* Week 4: Compilers and their limitations, both theoretical and practical
* Week 5: Parallelism I: Hardware parallelism
* Week 6: Parallelism II: Software parallelism
* Week 7: Effective use of intranets and the Internet
* Week 8: Debugging, dynamic work loads, and pathological behaviors
* Week 9: C++11, heterogeneity, and the future of systems programming
 
==Week 1==


* SHELL LIFE aka Things I Hope You Already Know
* SHELL LIFE aka Things I Hope You Already Know
Line 20: Line 7:
** effective use of interactive shells
** effective use of interactive shells
** shell scripting idioms.
** 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
* HOW COAL BECOMES CAT PICTURES aka Attack of the clone()s
** UEFI. UNIX boot sequence.
** UEFI. UNIX boot sequence.
Line 26: Line 14:
** lsof, netstat, memstat, etc
** lsof, netstat, memstat, etc
* C/C++ UNIX DEVELOPMENT aka Onward Christian Soldiers
* C/C++ UNIX DEVELOPMENT aka Onward Christian Soldiers
** Highlights of GCC, G++, LLVM, Clang, ICC, and NVCC.
** Highlights of [[GCC]], G++, LLVM, Clang, ICC, and NVCC.
** [[GNU Make]]
** strace, ltrace, ptrace().
** strace, ltrace, ptrace().
** GDB tricks.
** GDB tricks.
Line 33: Line 22:
** Linker tricks both stupid and less stupid.
** Linker tricks both stupid and less stupid.
** The C and C++ machine models.
** 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++
* OUR EARTH MOTHERS aka C/C++
** The system call interface.
** The system call interface.
** Process-level memory management.
** Process-level memory management.
** The C standard library.
** The C standard library.
** The STL.
** [[X Macros|Xmacros]] / The STL.
** A glimpse of template metaprogramming
** A glimpse of template metaprogramming


==Week 2==
==Week 2: Systems methods for efficient use of memory and buses==


* YOUR FRIEND THE COMPUTER aka Computer Architecture in Thirty Minutes.
* YOUR FRIEND THE COMPUTER aka Computer Architecture in Thirty Minutes.
Line 46: Line 40:
**The memory hierarchy.
**The memory hierarchy.
** Branch prediction.
** Branch prediction.
** SIMD.
** [[SIMD]].
** Memory fences.
** Memory fences.
** Transactional memory.
** Transactional memory.
Line 60: Line 54:
* ZERO-COPY I/O aka Now We're Getting Somewhere.
* ZERO-COPY I/O aka Now We're Getting Somewhere.
** Mmap and shared memory.
** Mmap and shared memory.
** TLB invalidation and IPIs
** CLONE_VM and a glimpse of threads.  
** CLONE_VM and a glimpse of threads.  
** RDMA. The PCIe bus.
** RDMA. The PCIe bus.
Line 73: Line 68:
** NUMA and you.
** NUMA and you.


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


* IN THE GRIM FUTURE OF WEEK 3 THERE ARE NO AKAs, ONLY ALGORITHMS
* IN THE GRIM FUTURE OF WEEK 3 THERE ARE NO AKAs, ONLY ALGORITHMS
* Searching small spaces: Constant sorts. Dancing links.
* Searching small spaces: Constant sorts (sorting networks). Dancing links. Timer wheels.
* Searching large spaces: Trees for smoking and computing. PATRICIA tries. Skip lists. Suffix trees. Automata search.
* Searching large spaces: Trees. PATRICIA tries. Skip lists. Suffix trees. Automata search. Interval trees.
* Searching by content: Hashes for smoking and computing. Algorithmic complexity attacks. Universal hashes. Cuckoo hashing. Adaptive perfect hashes.
* Searching by content: Hashes. 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.
* 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.
* 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.
* 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.
* 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==
==Week 4: [[Compiler Design|Compilers]] and their limitations==


* SSA, aka Planet of the Compilers
* SSA and Basic Blocks, aka Planet of the Compilers
* The Banerjee Test and the Polyhedral Model, aka Beneath the 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
* The limits of compiler-based optimization, aka Escape from the Planet of the Compilers
Line 92: Line 96:
* PGO and Genetic-O aka Battle for the Planet of the Compilers
* PGO and Genetic-O aka Battle for the Planet of the Compilers


==Week 5.1==
==Week 5==
===Allotrios===
* Windows aka Unfathomably Wretched Function Naming: I/O Completion Ports. With Fibers come Heaps.
* Windows aka Unfathomably Wretched Function Naming: I/O Completion Ports. With Fibers come Heaps.
* Libraries: objdump, nm, and how to design a shared library.
* 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.
* Unpleasant Details of the UNIX Environment aka What Stevens Forgot to Tell You.
** The OOM killer.
** The OOM killer.
Line 103: Line 109:
* Build systems aka They're All Shite
* Build systems aka They're All Shite


==Week 5.2==
===Parallelism I: Hardware Parallelism===
* Models of parallelism aka They're All Shite
* Models of parallelism aka They're All Shite
* Bit-level parallelism
* Bit-level parallelism
Line 110: Line 116:
* Parallelism among memory accesses
* Parallelism among memory accesses


==Week 6==
==Week 6: Parallelism II: Software Parallelism==


* Parallelism among tasks
* Parallelism among tasks
* Algorithms simulating parallelism and nondeterminism.
* Algorithms simulating parallelism and nondeterminism.
* POSIX threads. Userspace threading. Coroutines.
* [[Pthreads|POSIX threads]]. Userspace threading. Coroutines.
* Parallel languages and libraries. IPP and TBB.
* Parallel languages and libraries. IPP and TBB.


==Week 7==
==Week 7: Effective use of intranets and the Internet==
 
* Sampling theory of Nyquist
* The Linux virtual memory implementation on x86
* Queueing theory of Kleinrock. The Linux packet queue disciplines.
* 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.
* 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.
* 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.
* 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

Latest revision as of 22:26, 5 April 2023

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
Retrieved from "https://nick-black.com/dankwiki/index.php?title=UNIX_Weapons_School_Weekplan&oldid=9704"