UNIX Weapons School Weekplan: Difference between revisions
| (33 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
==Week 1: C/C++ development in the x86 UNIX environment== | ==Week 1: C/C++ development in the x86 UNIX environment== | ||
| Line 20: | 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 | ** [[GNU Make]] | ||
** strace, ltrace, ptrace(). | ** strace, ltrace, ptrace(). | ||
** GDB tricks. | ** GDB tricks. | ||
| Line 28: | 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 | ||
| Line 41: | Line 40: | ||
**The memory hierarchy. | **The memory hierarchy. | ||
** Branch prediction. | ** Branch prediction. | ||
** SIMD. | ** [[SIMD]]. | ||
** Memory fences. | ** Memory fences. | ||
** Transactional memory. | ** Transactional memory. | ||
| Line 55: | 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 71: | Line 71: | ||
* 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 | * Searching large spaces: Trees. PATRICIA tries. Skip lists. Suffix trees. Automata search. Interval trees. | ||
* Searching by content: Hashes | * Searching by content: Hashes. Algorithmic complexity attacks. Universal hashes. Cuckoo hashing. Adaptive perfect hashes. | ||
* Searching huge spaces: | * 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. | ||
| Line 81: | Line 81: | ||
* select(), poll(), interaction with signals | * select(), poll(), interaction with signals | ||
* Linux's epoll, FreeBSD's kqueue. Level- vs edge-triggered events. | * Linux's epoll, FreeBSD's kqueue. Level- vs edge-triggered events. | ||
** Algorithms for oneshot edge-triggered interfaces. | ** Algorithms for oneshot edge-triggered interfaces. Asynchronous I/O on POSIX systems. | ||
* Everything as events: timerfd, signalfd, V_NODE | * Everything as events: timerfd, signalfd, V_NODE | ||
* Wrapping pthread events. Multithreaded event engines. Work queues, work stealing, tasklets. | * Wrapping pthread events. Multithreaded event engines. Work queues, work stealing, tasklets. | ||
| Line 88: | Line 88: | ||
* libev, libevent, libtorque | * libev, libevent, libtorque | ||
==Week 4: Compilers and their limitations | ==Week 4: [[Compiler Design|Compilers]] and their limitations== | ||
* SSA and Basic Blocks, aka Planet of the Compilers | * SSA and Basic Blocks, aka Planet of the Compilers | ||
* The Banerjee Test and the | * 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 | ||
* Inline assembly, aka Conquest of the Planet of the Compilers | * Inline assembly, aka Conquest of the Planet of the Compilers | ||
| Line 97: | Line 97: | ||
==Week 5== | ==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 119: | Line 120: | ||
* 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: Effective use of intranets and the Internet== | ==Week 7: Effective use of intranets and the Internet== | ||
* Sampling theory of Nyquist | |||
* | * Queueing theory of Kleinrock. The Linux packet queue disciplines. | ||
* 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 | * 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). | * [[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: C++11, | ==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 | |||