Libtorque: Difference between revisions
update links |
|||
| (56 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
[[File:Libtorque.svg|thumb|right|alt="architecture model"|Architecture of a libtorque-enabled process.]] | |||
| | '''My [[Fast UNIX Servers]] page is a useful companion to this article.''' | ||
<tt>libtorque</tt> is a multithreaded event library for UNIX designed to take full advantage of the manycore, heterogenous, [[NUMA]] future. The [[media:Libtorque-proposal.pdf|project proposal]] suggests motivation for <tt>libtorque</tt>: I believe it necessary to take scheduling and memory-placement decisions into account to most optimally handle events, especially on manycore machines and ''especially'' to handle unexpected traffic sets (denial of service attacks, oversubscribed pipes, mixed-latency connections, etc). Along the way, I intend to shake up the UNIX programming idiom; my hope is that <tt>libtorque</tt> leads to more network programmers thinking about the complex issues involved, but simplifies rather than aggravates a task already fraught with difficulty. | <tt>libtorque</tt> is a multithreaded event library for UNIX designed to take full advantage of the manycore, heterogenous, [[NUMA]] future. The [[media:Libtorque-proposal.pdf|project proposal]] suggests motivation for <tt>libtorque</tt>: I believe it necessary to take scheduling and memory-placement decisions into account to most optimally handle events, especially on manycore machines and ''especially'' to handle unexpected traffic sets (denial of service attacks, oversubscribed pipes, mixed-latency connections, etc). Along the way, I intend to shake up the UNIX programming idiom; my hope is that <tt>libtorque</tt> leads to more network programmers thinking about the complex issues involved, but simplifies rather than aggravates a task already fraught with difficulty. | ||
Other open source event libraries include [http://www.monkey.org/~provos/libevent/ libevent], [http://software.schmorp.de/pkg/libev.html libev] and [http://liboop.ofb.net liboop]. | |||
==Resources | |||
==Resources== | |||
* "[[Media:hotpar2010.pdf|libtorque: Portable Multithreaded Continuations for Scalable Event-Driven Programs]]" | |||
* [[git]] hosting from [http://github.com GitHub] (dankamongmen/libtorque [http://github.com/dankamongmen/libtorque project page]) | |||
** Lots of good data in the [http://github.com/dankamongmen/libtorque/blob/master/README README!] | ** Lots of good data in the [http://github.com/dankamongmen/libtorque/blob/master/README README!] | ||
** <tt>git clone</tt> from git://github.com/dankamongmen/libtorque.git | ** <tt>git clone</tt> from git://github.com/dankamongmen/libtorque.git | ||
* [http://www.bugzilla.org/ bugzilla], hosted here on | * [http://www.bugzilla.org/ bugzilla], hosted here on https://nick-black.com/bugzilla/. See [[#Current_Issues|below]] for a snapshot bug report. | ||
* A [[Media:Libtorque-presentation.pdf|presentation]] I did for GT's [http://comparch.gatech.edu/arch_whisky/fall09.html Arch-Whiskey] seminar, 2009-11-13 | * A [[Media:Libtorque-presentation.pdf|presentation]] I did for GT's [http://comparch.gatech.edu/arch_whisky/fall09.html Arch-Whiskey] seminar, 2009-11-13 | ||
* Fo sho there's a [http://groups.google.com/group/libtorque-devel mailing list]! | * Fo sho there's a [http://groups.google.com/group/libtorque-devel mailing list]! | ||
===Documentation from the source tree=== | |||
The [http://github.com/dankamongmen/libtorque/tree/master/doc/ doc/ subdirectory] of a libtorque checkout contains several pieces of documentation, most of it quite technical. Some highlights include: | |||
* <tt>[http://github.com/dankamongmen/libtorque/raw/master/doc/mteventqueues mteventqueues]</tt> - "Multithreaded Event Queues". Details of [[epoll]] and [[kqueue]] semantics, especially with regard to locking. Correctness and performance implications thereof. | |||
* <tt>[http://github.com/dankamongmen/libtorque/raw/master/doc/termination termination]</tt> - "Termination". Interaction with POSIX cancellation and signals. API and semantics for initiating and blocking on a libtorque context's shutdown. Design justification and details. | |||
<!-- ===Recent commits (via [http://github.com/feeds/dankamongmen/commits/libtorque/master Atom])=== | |||
<rss>http://github.com/feeds/dankamongmen/commits/libtorque/master</rss> --> | |||
==Design/Functionality== | ==Design/Functionality== | ||
| Line 30: | Line 28: | ||
*'''Q:''' Why not just launch a thread per configured processing element, and use an existing event-handling library? | *'''Q:''' Why not just launch a thread per configured processing element, and use an existing event-handling library? | ||
*'''A:''' These threads will have to communicate with one another to spread around event sources. If reshuffling is desired, they must communicate further; if not, the system can be forced into dynamic behavior. The information most pertinent to this shuffling is at the event-handling level; we thus make the decisions there. | *'''A:''' These threads will have to communicate with one another to spread around event sources. If reshuffling is desired, they must communicate further; if not, the system can be forced into dynamic behavior. The information most pertinent to this shuffling is at the event-handling level; we thus make the decisions there. | ||
*'''Q''' How is this any better than Win32's [http://msdn.microsoft.com/en-us/library/aa365198%28VS.85%29.aspx I/O Completion Ports] or Solaris 10's [http://developers.sun.com/solaris/articles/event_completion.html Event Completion Framework]? | *'''Q''' How (aside from being open source) is this any better than Win32's [http://msdn.microsoft.com/en-us/library/aa365198%28VS.85%29.aspx I/O Completion Ports] or Solaris 10's [http://developers.sun.com/solaris/articles/event_completion.html Event Completion Framework]? | ||
*'''A''' These two systems are laudable, and provide much of libtorque's functionality (on different operating systems, of course). An algorithm expressible in IOCP can be expressed in libtorque's CPS; the opposite might not always be true (that is, I suspect IOCP ⊆ libtorque, but that the converse is not strictly true '''FIXME detail'''). More importantly, libtorque performs architecture- and topology-aware event handling within its CPUSet, which a user of IOCP must provide. | *'''A''' These two systems are laudable, and provide much of libtorque's functionality (on different operating systems, of course). An algorithm expressible in IOCP can be expressed in libtorque's CPS; the opposite might not always be true (that is, I suspect IOCP ⊆ libtorque, but that the converse is not strictly true '''FIXME detail'''). More importantly, libtorque performs architecture- and topology-aware event handling within its CPUSet, which a user of IOCP must provide. | ||
** This having been said, they ought be much easier to build atop than the linux and FreeBSD primitives. | ** This having been said, they ought be much easier to build atop than the linux and FreeBSD primitives. | ||
===Event Unification=== | |||
Libtorque handles a wide variety of event sources, including: | |||
* any <tt>poll(2)</tt>able file descriptor | |||
* regular and realtime signals (via [[signalfd|signalfd()s]] and <tt>EVFILT_SIGNAL</tt>) | |||
* optionally-periodic absolute and interval timers (via [[timerfd|timerfd()s]] and <tt>EVFILT_TIMER</tt>) | |||
* filesystem changes (via <tt>inotify(9)</tt> and <tt>EVFILT_NODE</tt>) | |||
* network changes (via <tt>netlink(7)</tt> and <tt>EVFILT_MII</tt>) | |||
* condition variables | |||
===System discovery=== | ===System discovery=== | ||
* '''Exciting news!''' Thanks to the efforts of Dr. David Bader and Dr. Richard Vuduc of Georgia Tech's Computational Science and Engineering program, I now have access to a Niagara 2 machine. Expect SPARC and OpenSolaris support soon! | * '''Exciting news!''' Thanks to the efforts of Dr. David Bader and Dr. Richard Vuduc of Georgia Tech's Computational Science and Engineering program, I now have access to a Niagara 2 machine. Expect SPARC and OpenSolaris support soon! | ||
| Line 52: | Line 59: | ||
====archdetect==== | ====archdetect==== | ||
* Utility built/packaged with libtorque: | * Utility built/packaged with libtorque: | ||
<pre> Package 0: (8 threads total) | <pre>Testing archdetect: env LD_LIBRARY_PATH=.out/lib .out/bin/archdetect | ||
Core 0: | Package 0: (8 threads total) | ||
Core 1: | Core 0: 0 4 (2x processor type 1) | ||
Core 1: 1 5 (2x processor type 1) | |||
Core | Core 2: 2 6 (2x processor type 1) | ||
Core 3: 3 7 (2x processor type 1) | |||
Core | |||
( 1x) Memory node 1 of 1: | ( 1x) Memory node 1 of 1: | ||
8,131,244KB (7.754 GB) total in 4KB and 4MB pages | |||
( | ( 8x) Processing unit type 1 of 2: x86 | ||
Extensions: MMX SSE SSE2 SSE3 SSSE3 SSE4.1 SSE4.2 SSE4a | |||
Family: 0x006 (6) Model: | Family: 0x006 (6) Model: 0x1e (30) Stepping: 5 (OEM) | ||
Brand name: Intel(R) Core(TM) i7 CPU Q 720 @ 1.60GHz | |||
2 threads per processing core, 8 cores (4 logical) per package | 2 threads per processing core, 8 cores (4 logical) per package | ||
Cache 1 of 4: 32KB total, 64B line, | Cache 1 of 4: 32KB total, 64B line, 4-assoc, 2-shared (L1 code) | ||
Cache 2 of 4: 32KB total, 64B line, | Cache 2 of 4: 32KB total, 64B line, 8-assoc, 2-shared (L1 data) | ||
Cache 3 of 4: 256KB total, 64B line, 8-assoc, 2-shared (L2 unified) | Cache 3 of 4: 256KB total, 64B line, 8-assoc, 2-shared (L2 unified) | ||
Cache 4 of 4: | Cache 4 of 4: 6MB total, 64B line, 12-assoc, 16-shared (L3 unified) | ||
TLB 1 of 5: 4KB pages, | TLB 1 of 5: 4KB pages, 64-entry, 4-assoc, 2-shared (L1 code) | ||
TLB 2 of 5: | TLB 2 of 5: 4MB pages, 32-entry, 4-assoc, 2-shared (L1 data) | ||
TLB 3 of 5: | TLB 3 of 5: 4KB pages, 7-entry, 7-assoc, 2-shared (L2 code) | ||
TLB 4 of 5: 4KB pages, 64-entry, 4-assoc, 2-shared ( | TLB 4 of 5: 4KB pages, 64-entry, 4-assoc, 2-shared (L2 data) | ||
TLB 5 of 5: 4KB pages, 512-entry, 4-assoc, 2-shared (L2 data)</pre> | TLB 5 of 5: 4KB pages, 512-entry, 4-assoc, 2-shared (L2 data) | ||
( 1x) Processing unit type 2 of 2: CUDA | |||
CUDA compute capabilities: 1.2 | |||
Brand name: GeForce GTS 360M | |||
1 thread per processing core, 96 cores per package</pre> | |||
===Scheduling=== | ===Scheduling=== | ||
| Line 125: | Line 133: | ||
** Network servers are not matrix kernels! Assume crappy IPC (syscalls, branching, I/O), and exploit sharing purely in terms of memory | ** Network servers are not matrix kernels! Assume crappy IPC (syscalls, branching, I/O), and exploit sharing purely in terms of memory | ||
* Let's ''color'' connections | * Let's ''color'' connections | ||
====Some techniques from networking theory==== | ====Some techniques from networking theory==== | ||
* We have an event queue backed by ''n'' elements, but we can artificially limit the amount filled in | * We have an event queue backed by ''n'' elements, but we can artificially limit the amount filled in | ||
| Line 136: | Line 138: | ||
* Stochastic Fair Queueing is trying to solve a semi-similar problem | * Stochastic Fair Queueing is trying to solve a semi-similar problem | ||
** Use its concepts of [http://en.wikipedia.org/wiki/Pareto_efficiency Pareto frontiers] for distribution | ** Use its concepts of [http://en.wikipedia.org/wiki/Pareto_efficiency Pareto frontiers] for distribution | ||
====Fail gracefully and usefully==== | |||
A denial-of-service attack that doesn't degrade the service isn't one to worry about, so we can postpone DoS detection/response to the point of maximum service at some quality level. Once we start failing, either due to: | |||
* Resource acquisition failure, or | |||
* Event backup (really a special case of resource acquisition failure) | |||
we might start prefailing some connections. How ought we choose connections to prefail? Are we reinventing the OOM killer? | |||
* Fail on resource fail. Fairly nondeterministic, and if a connection can hold arbitrary resources at length, vulnerable to DoS (slowloris, sockstress) | |||
* Kill state-hoggy connections. Non-trivial to identify, tends to kill important connections. | |||
* Better to abort early than late, so as not to waste work, but... | |||
* Want to keep traffic flowing at all times | |||
There is a thin line between attack and underprovision. | |||
====Edge-triggered event handling==== | |||
* libtorque deals only in edge-triggered event notification, thus evading an entire level of otherwise necessary locking. '''FIXME EXPLAIN''' | |||
* Multiple threads share a kernel event queue, but write results to distinct portions (|largest cache line|-spaced). Only one goes into the event dispatch system call at a time. If there's a good spread of events, they'll each get a portion. If not, we're either way ahead of current traffic, or there's some lengthy events. | |||
** We can steal work in the case of lengthy events. | |||
** We must implement an event cache anyway in such cases (lengthy unboundable receipts) | |||
===Allocation=== | ===Allocation=== | ||
'''FIXME EXPLAIN''' | '''FIXME EXPLAIN''' | ||
| Line 147: | Line 164: | ||
===Scalability=== | ===Scalability=== | ||
Commonly-used algorithms (anything in the event-handling hotpath) oughtn't depend on the number of processors, depth of the scheduling topology, or number of memories -- that is, O(1) as these grow. Performance per processor ought exhibit linear growth from top to bottom, save perhaps superlinear growth when a scheduling level shares caches. | Commonly-used algorithms (anything in the event-handling hotpath) oughtn't depend on the number of processors, depth of the scheduling topology, or number of memories -- that is, O(1) as these grow. Performance per processor ought exhibit linear growth from top to bottom, save perhaps superlinear growth when a scheduling level shares caches (event queues also must not be O(n) on cpus; sharing is a critical feature). | ||
===Robustness=== | ===Robustness=== | ||
| Line 188: | Line 205: | ||
===Papers/Presentations=== | ===Papers/Presentations=== | ||
* Mucci. "[http://icl.cs.utk.edu/~mucci/latest/pubs/Notur2009-new.pdf Linux Multicore Performance Analysis and Optimization in a Nutshell]", NOTUR 2009. | * Mucci. "[http://icl.cs.utk.edu/~mucci/latest/pubs/Notur2009-new.pdf Linux Multicore Performance Analysis and Optimization in a Nutshell]", NOTUR 2009. | ||
* Sibai. "[http://journal.info.unlp.edu.ar/journal/journal24/papers/JCST-Oct08-3.pdf Nearest Neighbor Affinity Scheduling in Heterogeneous Multicore Architectures]", JCST 2008. | |||
* Veal, Foong. "[http://www.cse.wustl.edu/ANCS/2007/slides/Bryan%20Veal%20ANCS%20Presentation.pdf Performance Scalability of a Multicore Web Server]", ANCS 2007. | |||
* Eker. "[http://www.ece.ncsu.edu/news/theses/etd-03302007-161856 Characterization of Context Switch Effects on L2 Cache]", 2007. | * Eker. "[http://www.ece.ncsu.edu/news/theses/etd-03302007-161856 Characterization of Context Switch Effects on L2 Cache]", 2007. | ||
* Williams, Vuduc, Oliker, Shalf, Yelick, Demmel. "[http://bebop.cs.berkeley.edu/pubs/williams2007-multicore-spmv-slides.pdf Tuning Sparse Matrix Vector Multiplication for | * Chen et al. "Scheduling Threads for Constructive Cache Sharing on CMPs", SPAA 2007. | ||
* Tsafrir | * Milfled, Goto, Purkayastha, Guiang, Schulz. Effective Use of Multi-Core Commodity Systems in HPC, LCI 2007. | ||
* | * Williams, Vuduc, Oliker, Shalf, Yelick, Demmel. "[http://bebop.cs.berkeley.edu/pubs/williams2007-multicore-spmv-slides.pdf Tuning Sparse Matrix Vector Multiplication for Multicore SMPs]", 2007. | ||
* Elmeleegy | * Tsafrir. "[http://www.citeulike.org/user/dankamongmen/article/2052076 The Context-Switch Overhead Inflicted by Hardware Interrupts (and the enigma of do-nothing loops)]", 2007. | ||
* Yelick. "[http://www.sdsc.edu/pmac/workshops/geo2006/pubs/Yelick.pdf Performance and Productivity Opportunities using Global Address Space Programming Models]", 2006. | |||
* Mohamood. "[http://smartech.gatech.edu/handle/1853/10560 DLL-Conscious Instruction Fetch Optimization for SMT Processors]", 2006. | |||
* Elmeleegy, Chanda, Cox, Zwaenepeol. "[http://www.cs.rice.edu/~kdiaa/laio/ Lazy Asynchronous I/O for Event-Driven Servers]", USENIX 2004. | |||
* Sibai's "[http://journal.info.unlp.edu.ar/journal/journal24/papers/JCST-Oct08-3.pdf Nearest neighbor affinity scheduling in heterogeneous multicore architectures]", 2003. | * Sibai's "[http://journal.info.unlp.edu.ar/journal/journal24/papers/JCST-Oct08-3.pdf Nearest neighbor affinity scheduling in heterogeneous multicore architectures]", 2003. | ||
* Suh, Devadas, Rudolph. "[http://portal.acm.org/citation.cfm?id=377792.377797 Analytical cache models with applications to cache partitioning]", Supercomputing 2001. | |||
* Anderson, Bershad, Lazowska, Levy. "[http://www.cs.washington.edu/homes/tom/pubs/sched_act.pdf Scheduler Activations: Effective Kernel Support for the User-Level Management of Parallelism]", 1992. | * Anderson, Bershad, Lazowska, Levy. "[http://www.cs.washington.edu/homes/tom/pubs/sched_act.pdf Scheduler Activations: Effective Kernel Support for the User-Level Management of Parallelism]", 1992. | ||
===Projects=== | ===Projects=== | ||
* Matt Welsh's [http://www.eecs.harvard.edu/~mdw/proj/seda/ SEDA] (Staged Event-Driven Architecture) | |||
* [http://eventlet.net/ Eventlet] is a python implementation of asynchronous triggers | |||
* The [[Radovic-Hagersten lock]] team has a page on [http://www.it.uu.se/research/group/uart/projects/nucasynch NUMA locking] | * The [[Radovic-Hagersten lock]] team has a page on [http://www.it.uu.se/research/group/uart/projects/nucasynch NUMA locking] | ||
* Emery Berger's [http://www.hoard.org/ Hoard] and other manycore-capable [[allocators|allocators]] (libumem aka magazined slab, Google's [http://goog-perftools.sourceforge.net/doc/tcmalloc.html ctmalloc], etc). | * Emery Berger's [http://www.hoard.org/ Hoard] and other manycore-capable [[allocators|allocators]] (libumem aka magazined slab, Google's [http://goog-perftools.sourceforge.net/doc/tcmalloc.html ctmalloc], etc). | ||
* The [http://netstreamline.org/general/pipesfs.php PipesFS project] at Vrije Universiteit Amsterdam | |||
* A lot of discursive theorizing/ruminating is captured on my [[Fast UNIX Servers]] page | * A lot of discursive theorizing/ruminating is captured on my [[Fast UNIX Servers]] page | ||
====libev==== | |||
* Works on (refcounted) loop contexts, with an implicit "default" loop. | |||
* <tt>ev_signal_init</tt> operates on an <tt>int</tt> signal rather than a <tt>sigset_t</tt> | |||
** it doesn't compile under -fstrict-aliasing (use -Werror and -Wstrict-aliasing) :/ | |||
==Miscellanea== | ==Miscellanea== | ||
| Line 204: | Line 235: | ||
<tt>libtorque</tt>, under that name, began as a project for Professor [http://vuduc.org/ Rich Vuduc's] Fall 2009 [[High Performance Parallel Computing|CSE6230]]. It really began gestating in three parts: | <tt>libtorque</tt>, under that name, began as a project for Professor [http://vuduc.org/ Rich Vuduc's] Fall 2009 [[High Performance Parallel Computing|CSE6230]]. It really began gestating in three parts: | ||
* Work on intrusion prevention at [http://www.reflexsystems.com/ Reflex] got me hooked on automata-based networking activations and [[Fast UNIX Servers|fast networking]] | * Work on intrusion prevention at [http://www.reflexsystems.com/ Reflex] got me hooked on automata-based networking activations and [[Fast UNIX Servers|fast networking]] | ||
* Work on [[ICAP]] servers and [http://en.wikipedia.org/wiki/Reverse_proxy reverse proxies] at [http://www.mcafee.com/ McAfee], especially <tt>snare</tt>, got me thinking about networking | * Work on [[ICAP]] servers and [http://en.wikipedia.org/wiki/Reverse_proxy reverse proxies] at [http://www.mcafee.com/ McAfee], especially <tt>snare</tt>, got me thinking about networking APIs | ||
* Professor [http://www.cc.gatech.edu/directory/faculty/faculty/school-of-computer-science/directory/thomas-conte Tom Conte's] Spring 2009 "CS 8803 MCA: Multicore and Manycore Architecture" lit up the parallelism fire | * Professor [http://www.cc.gatech.edu/directory/faculty/faculty/school-of-computer-science/directory/thomas-conte Tom Conte's] Spring 2009 "CS 8803 MCA: Multicore and Manycore Architecture" lit up the parallelism fire | ||
===Milestones=== | ===Milestones=== | ||
* 2009-10-22: [http://github.com/dankamongmen/libtorque/commit/e7429294beb9dc581a7cdab2371d2ddca3169047 First commit] (e7429294beb9dc581a7cdab2371d2ddca3169047) | * 2009-10-22: [http://github.com/dankamongmen/libtorque/commit/e7429294beb9dc581a7cdab2371d2ddca3169047 First commit] (e7429294beb9dc581a7cdab2371d2ddca3169047) | ||
* 2009-11-12: CSE 6230 checkpoint (see [ | * 2009-11-12: CSE 6230 checkpoint (see [https://nick-black.com/tabpower/cse6230proposal.pdf proposal]) | ||
* 2009-11-13: CS 8001-CAS [http://comparch.gatech.edu/arch_whisky/fall09.html Arch-Whiskey] presentation | * 2009-11-13: CS 8001-CAS [http://comparch.gatech.edu/arch_whisky/fall09.html Arch-Whiskey] presentation | ||
* 2009-12-10: CSE 6230 | * 2009-12-10: CSE 6230 [https://nick-black.com/tabpower/cse6230finalpaper.pdf final report] (again, see proposal) | ||
* 2010-01-24: [http://www.usenix.org/events/hotpar10/cfp/ HotPar 2010] submission deadline | |||
=== | ===Logo=== | ||
<pre>888 ,e, 888 d8 "...tear the roof off the sucka..." | <pre>888 ,e, 888 d8 "...tear the roof off the sucka..." | ||
888 " 888 88e d88 e88 88e 888,8, e88 888 8888 8888 ,e e, | 888 " 888 88e d88 e88 88e 888,8, e88 888 8888 8888 ,e e, | ||
| Line 229: | Line 253: | ||
_____________________________________________ 888 _________________ | _____________________________________________ 888 _________________ | ||
continuation-based unix i/o for manycore numa\888/© nick black 2009</pre> | continuation-based unix i/o for manycore numa\888/© nick black 2009</pre> | ||
==Corrections== | |||
* Marc Lehmann of the [http://software.schmorp.de/pkg/libev.html libev] project pointed out some errors regarding my characterization of that library. Thanks, Marc! | |||
[[Category: Projects]] | |||