--- libev/ev.pod 2008/09/30 18:35:47 1.188 +++ libev/ev.pod 2010/10/14 05:07:04 1.305 @@ -11,15 +11,17 @@ // a single header file is required #include + #include // for puts + // every watcher type has its own typedef'd struct - // with the name ev_ + // with the name ev_TYPE ev_io stdin_watcher; ev_timer timeout_watcher; // all watcher callbacks have a similar signature // this callback is called when data is readable on stdin static void - stdin_cb (EV_P_ struct ev_io *w, int revents) + stdin_cb (EV_P_ ev_io *w, int revents) { puts ("stdin ready"); // for one-shot events, one must manually stop the watcher @@ -32,7 +34,7 @@ // another callback, this time for a time-out static void - timeout_cb (EV_P_ struct ev_timer *w, int revents) + timeout_cb (EV_P_ ev_timer *w, int revents) { puts ("timeout"); // this causes the innermost ev_loop to stop iterating @@ -62,12 +64,24 @@ return 0; } -=head1 DESCRIPTION +=head1 ABOUT THIS DOCUMENT + +This document documents the libev software package. The newest version of this document is also available as an html-formatted web page you might find easier to navigate when reading it for the first time: L. +While this document tries to be as complete as possible in documenting +libev, its usage and the rationale behind its design, it is not a tutorial +on event-based programming, nor will it introduce event-based programming +with libev. + +Familiarity with event based programming techniques in general is assumed +throughout this document. + +=head1 ABOUT LIBEV + Libev is an event loop: you register interest in certain events (such as a file descriptor being readable or a timeout occurring), and it will manage these event sources and provide your program with events. @@ -86,13 +100,14 @@ Libev supports C is buggy + +All that's left is C actively limits the number of file +descriptors you can pass in to 1024 - your program suddenly crashes when +you use more. + +There is an undocumented "workaround" for this - defining +C<_DARWIN_UNLIMITED_SELECT>, which libev tries to use, so select I +work on OS/X. + +=head2 SOLARIS PROBLEMS AND WORKAROUNDS + +=head3 C reentrancy + +The default compile environment on Solaris is unfortunately so +thread-unsafe that you can't even use components/libraries compiled +without C<-D_REENTRANT> (as long as they use C), which, of course, +isn't defined by default. + +If you want to use libev in threaded environments you have to make sure +it's compiled with C<_REENTRANT> defined. + +=head3 Event port backend + +The scalable event interface for Solaris is called "event ports". Unfortunately, +this mechanism is very buggy. If you run into high CPU usage, your program +freezes or you get a large number of spurious wakeups, make sure you have +all the relevant and latest kernel patches applied. No, I don't know which +ones, but there are multiple ones. + +If you can't get it to work, you can try running the program by setting +the environment variable C to only allow C and +C works fine +with large bitsets, and AIX is dead anyway. + +=head2 WIN32 PLATFORM LIMITATIONS AND WORKAROUNDS + +=head3 General issues Win32 doesn't support any of the standards (e.g. POSIX) that libev requires, and its I/O model is fundamentally incompatible with the POSIX model. Libev still offers limited functionality on this platform in the form of the C backend, and only supports socket descriptors. This only applies when using Win32 natively, not when using -e.g. cygwin. +e.g. cygwin. Actually, it only applies to the microsofts own compilers, +as every compielr comes with a slightly differently broken/incompatible +environment. Lifting these limitations would basically require the full -re-implementation of the I/O system. If you are into these kinds of -things, then note that glib does exactly that for you in a very portable -way (note also that glib is the slowest event library known to man). +re-implementation of the I/O system. If you are into this kind of thing, +then note that glib does exactly that for you in a very portable way (note +also that glib is the slowest event library known to man). There is no supported compilation method available on windows except embedding it into other applications. +Sensible signal handling is officially unsupported by Microsoft - libev +tries its best, but under most conditions, signals will simply not work. + Not a libev limitation but worth mentioning: windows apparently doesn't accept large writes: instead of resulting in a partial write, windows will either accept everything or return C if the buffer is too large, @@ -3481,7 +4518,7 @@ more than a hundred or so sockets, then likely it needs to use a totally different implementation for windows, as libev offers the POSIX readiness notification model, which cannot be implemented efficiently on windows -(Microsoft monopoly games). +(due to Microsoft monopoly games). A typical way to use libev under windows is to embed it (see the embedding section for details) and use the following F header file instead @@ -3498,9 +4535,7 @@ #include "evwrap.h" #include "ev.c" -=over 4 - -=item The winsocket select function +=head3 The winsocket C function doesn't follow POSIX in that it requires socket I and not socket I (it is @@ -3519,7 +4554,7 @@ Note that winsockets handling of fd sets is O(n), so you can easily get a complexity in the O(n²) range when using win32. -=item Limited number of file descriptors +=head3 Limited number of file descriptors Windows has numerous arbitrary (and low) limits on things. @@ -3527,32 +4562,27 @@ of C<64> handles (probably owning to the fact that all windows kernels can only wait for C<64> things at the same time internally; Microsoft recommends spawning a chain of threads and wait for 63 handles and the -previous thread in each. Great). +previous thread in each. Sounds great!). Newer versions support more handles, but you need to define C to some high number (e.g. C<2048>) before compiling the winsocket select -call (which might be in libev or elsewhere, for example, perl does its own -select emulation on windows). +call (which might be in libev or elsewhere, for example, perl and many +other interpreters do their own select emulation on windows). Another limit is the number of file descriptors in the Microsoft runtime -libraries, which by default is C<64> (there must be a hidden I<64> fetish -or something like this inside Microsoft). You can increase this by calling -C<_setmaxstdio>, which can increase this limit to C<2048> (another -arbitrary limit), but is broken in many versions of the Microsoft runtime -libraries. - -This might get you to about C<512> or C<2048> sockets (depending on -windows version and/or the phase of the moon). To get more, you need to -wrap all I/O functions and provide your own fd management, but the cost of -calling select (O(n²)) will likely make this unworkable. - -=back +libraries, which by default is C<64> (there must be a hidden I<64> +fetish or something like this inside Microsoft). You can increase this +by calling C<_setmaxstdio>, which can increase this limit to C<2048> +(another arbitrary limit), but is broken in many versions of the Microsoft +runtime libraries. This might get you to about C<512> or C<2048> sockets +(depending on windows version and/or the phase of the moon). To get more, +you need to wrap all I/O functions and provide your own fd management, but +the cost of calling select (O(n²)) will likely make this unworkable. +=head2 PORTABILITY REQUIREMENTS -=head1 PORTABILITY REQUIREMENTS - -In addition to a working ISO-C implementation, libev relies on a few -additional extensions: +In addition to a working ISO-C implementation and of course the +backend-specific APIs, libev relies on a few additional extensions: =over 4 @@ -3587,77 +4617,213 @@ =item C must be large enough for common memory allocation sizes -To improve portability and simplify using libev, libev uses C -internally instead of C when allocating its data structures. On -non-POSIX systems (Microsoft...) this might be unexpectedly low, but -is still at least 31 bits everywhere, which is enough for hundreds of -millions of watchers. +To improve portability and simplify its API, libev uses C internally +instead of C when allocating its data structures. On non-POSIX +systems (Microsoft...) this might be unexpectedly low, but is still at +least 31 bits everywhere, which is enough for hundreds of millions of +watchers. =item C must hold a time value in seconds with enough accuracy The type C is used to represent timestamps. It is required to have at least 51 bits of mantissa (and 9 bits of exponent), which is good enough for at least into the year 4000. This requirement is fulfilled by -implementations implementing IEEE 754 (basically all existing ones). +implementations implementing IEEE 754, which is basically all existing +ones. With IEEE 754 doubles, you get microsecond accuracy until at least +2200. =back If you know of other additional requirements drop me a note. -=head1 COMPILER WARNINGS +=head1 ALGORITHMIC COMPLEXITIES -Depending on your compiler and compiler settings, you might get no or a -lot of warnings when compiling libev code. Some people are apparently -scared by this. +In this section the complexities of (many of) the algorithms used inside +libev will be documented. For complexity discussions about backends see +the documentation for C. -However, these are unavoidable for many reasons. For one, each compiler -has different warnings, and each user has different tastes regarding -warning options. "Warn-free" code therefore cannot be a goal except when -targeting a specific compiler and compiler-version. +All of the following are about amortised time: If an array needs to be +extended, libev needs to realloc and move the whole array, but this +happens asymptotically rarer with higher number of elements, so O(1) might +mean that libev does a lengthy realloc operation in rare cases, but on +average it is much faster and asymptotically approaches constant time. -Another reason is that some compiler warnings require elaborate -workarounds, or other changes to the code that make it less clear and less -maintainable. +=over 4 -And of course, some compiler warnings are just plain stupid, or simply -wrong (because they don't actually warn about the condition their message -seems to warn about). +=item Starting and stopping timer/periodic watchers: O(log skipped_other_timers) -While libev is written to generate as few warnings as possible, -"warn-free" code is not a goal, and it is recommended not to build libev -with any compiler warnings enabled unless you are prepared to cope with -them (e.g. by ignoring them). Remember that warnings are just that: -warnings, not errors, or proof of bugs. +This means that, when you have a watcher that triggers in one hour and +there are 100 watchers that would trigger before that, then inserting will +have to skip roughly seven (C) of these watchers. +=item Changing timer/periodic watchers (by autorepeat or calling again): O(log skipped_other_timers) -=head1 VALGRIND +That means that changing a timer costs less than removing/adding them, +as only the relative motion in the event queue has to be paid for. -Valgrind has a special section here because it is a popular tool that is -highly useful, but valgrind reports are very hard to interpret. +=item Starting io/check/prepare/idle/signal/child/fork/async watchers: O(1) -If you think you found a bug (memory leak, uninitialised data access etc.) -in libev, then check twice: If valgrind reports something like: +These just add the watcher into an array or at the head of a list. - ==2274== definitely lost: 0 bytes in 0 blocks. - ==2274== possibly lost: 0 bytes in 0 blocks. - ==2274== still reachable: 256 bytes in 1 blocks. +=item Stopping check/prepare/idle/fork/async watchers: O(1) -Then there is no memory leak. Similarly, under some circumstances, -valgrind might report kernel bugs as if it were a bug in libev, or it -might be confused (it is a very good tool, but only a tool). +=item Stopping an io/signal/child watcher: O(number_of_watchers_for_this_(fd/signal/pid % EV_PID_HASHSIZE)) -If you are unsure about something, feel free to contact the mailing list -with the full valgrind report and an explanation on why you think this is -a bug in libev. However, don't be annoyed when you get a brisk "this is -no bug" answer and take the chance of learning how to interpret valgrind -properly. +These watchers are stored in lists, so they need to be walked to find the +correct watcher to remove. The lists are usually short (you don't usually +have many watchers waiting for the same fd or signal: one is typical, two +is rare). -If you need, for some reason, empty reports from valgrind for your project -I suggest using suppression lists. +=item Finding the next timer in each loop iteration: O(1) + +By virtue of using a binary or 4-heap, the next timer is always found at a +fixed position in the storage array. + +=item Each change on a file descriptor per loop iteration: O(number_of_watchers_for_this_fd) + +A change means an I/O watcher gets started or stopped, which requires +libev to recalculate its status (and possibly tell the kernel, depending +on backend and whether C was used). +=item Activating one watcher (putting it into the pending state): O(1) + +=item Priority handling: O(number_of_priorities) + +Priorities are implemented by allocating some space for each +priority. When doing priority-based operations, libev usually has to +linearly search all the priorities, but starting/stopping and activating +watchers becomes O(1) with respect to priority handling. + +=item Sending an ev_async: O(1) + +=item Processing ev_async_send: O(number_of_async_watchers) + +=item Processing signals: O(max_signal_number) + +Sending involves a system call I there were no other C +calls in the current loop iteration. Checking for async and signal events +involves iterating over all running async watchers or all signal numbers. + +=back + + +=head1 PORTING FROM LIBEV 3.X TO 4.X + +The major version 4 introduced some minor incompatible changes to the API. + +At the moment, the C header file tries to implement superficial +compatibility, so most programs should still compile. Those might be +removed in later versions of libev, so better update early than late. + +=over 4 + +=item C renamed to C + +=item C renamed to C + +=item C renamed to C + +Most functions working on C objects don't have an +C prefix, so it was removed. Note that C is +still called C because it would otherwise clash with the +C typedef. + +=item C renamed to C in C + +This is a simple rename - all other watcher types use their name +as revents flag, and now C does, too. + +Both C and C symbols were present in 3.x versions +and continue to be present for the foreseeable future, so this is mostly a +documentation change. + +=item C mechanism replaced by C + +The preprocessor symbol C has been replaced by a different +mechanism, C. Programs using C usually compile +and work, but the library code will of course be larger. + +=back + + +=head1 GLOSSARY + +=over 4 + +=item active + +A watcher is active as long as it has been started (has been attached to +an event loop) but not yet stopped (disassociated from the event loop). + +=item application + +In this document, an application is whatever is using libev. + +=item callback + +The address of a function that is called when some event has been +detected. Callbacks are being passed the event loop, the watcher that +received the event, and the actual event bitset. + +=item callback invocation + +The act of calling the callback associated with a watcher. + +=item event + +A change of state of some external event, such as data now being available +for reading on a file descriptor, time having passed or simply not having +any other events happening anymore. + +In libev, events are represented as single bits (such as C or +C). + +=item event library + +A software package implementing an event model and loop. + +=item event loop + +An entity that handles and processes external events and converts them +into callback invocations. + +=item event model + +The model used to describe how an event loop handles and processes +watchers and events. + +=item pending + +A watcher is pending as soon as the corresponding event has been detected, +and stops being pending as soon as the watcher will be invoked or its +pending status is explicitly cleared by the application. + +A watcher can be pending, but not active. Stopping a watcher also clears +its pending status. + +=item real time + +The physical time that is observed. It is apparently strictly monotonic :) + +=item wall-clock time + +The time and date as shown on clocks. Unlike real time, it can actually +be wrong and jump forwards and backwards, e.g. when the you adjust your +clock. + +=item watcher + +A data structure that describes interest in certain events. Watchers need +to be started (attached to an event loop) before they can receive events. + +=item watcher invocation + +The act of calling the callback associated with a watcher. + +=back =head1 AUTHOR -Marc Lehmann . +Marc Lehmann , with repeated corrections by Mikael Magnusson.