--- libev/ev.pod 2008/05/24 03:08:03 1.161 +++ libev/ev.pod 2008/10/21 20:52:30 1.197 @@ -4,63 +4,63 @@ =head1 SYNOPSIS - #include + #include =head2 EXAMPLE PROGRAM - // a single header file is required - #include + // a single header file is required + #include - // every watcher type has its own typedef'd struct - // with the name ev_ - 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) - { - puts ("stdin ready"); - // for one-shot events, one must manually stop the watcher - // with its corresponding stop function. - ev_io_stop (EV_A_ w); - - // this causes all nested ev_loop's to stop iterating - ev_unloop (EV_A_ EVUNLOOP_ALL); - } - - // another callback, this time for a time-out - static void - timeout_cb (EV_P_ struct ev_timer *w, int revents) - { - puts ("timeout"); - // this causes the innermost ev_loop to stop iterating - ev_unloop (EV_A_ EVUNLOOP_ONE); - } - - int - main (void) - { - // use the default event loop unless you have special needs - struct ev_loop *loop = ev_default_loop (0); - - // initialise an io watcher, then start it - // this one will watch for stdin to become readable - ev_io_init (&stdin_watcher, stdin_cb, /*STDIN_FILENO*/ 0, EV_READ); - ev_io_start (loop, &stdin_watcher); - - // initialise a timer watcher, then start it - // simple non-repeating 5.5 second timeout - ev_timer_init (&timeout_watcher, timeout_cb, 5.5, 0.); - ev_timer_start (loop, &timeout_watcher); - - // now wait for events to arrive - ev_loop (loop, 0); - - // unloop was called, so exit - return 0; - } + // every watcher type has its own typedef'd struct + // with the name ev_ + 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) + { + puts ("stdin ready"); + // for one-shot events, one must manually stop the watcher + // with its corresponding stop function. + ev_io_stop (EV_A_ w); + + // this causes all nested ev_loop's to stop iterating + ev_unloop (EV_A_ EVUNLOOP_ALL); + } + + // another callback, this time for a time-out + static void + timeout_cb (EV_P_ struct ev_timer *w, int revents) + { + puts ("timeout"); + // this causes the innermost ev_loop to stop iterating + ev_unloop (EV_A_ EVUNLOOP_ONE); + } + + int + main (void) + { + // use the default event loop unless you have special needs + struct ev_loop *loop = ev_default_loop (0); + + // initialise an io watcher, then start it + // this one will watch for stdin to become readable + ev_io_init (&stdin_watcher, stdin_cb, /*STDIN_FILENO*/ 0, EV_READ); + ev_io_start (loop, &stdin_watcher); + + // initialise a timer watcher, then start it + // simple non-repeating 5.5 second timeout + ev_timer_init (&timeout_watcher, timeout_cb, 5.5, 0.); + ev_timer_start (loop, &timeout_watcher); + + // now wait for events to arrive + ev_loop (loop, 0); + + // unloop was called, so exit + return 0; + } =head1 DESCRIPTION @@ -180,9 +180,9 @@ Example: Make sure we haven't accidentally been linked against the wrong version. - assert (("libev version mismatch", - ev_version_major () == EV_VERSION_MAJOR - && ev_version_minor () >= EV_VERSION_MINOR)); + assert (("libev version mismatch", + ev_version_major () == EV_VERSION_MAJOR + && ev_version_minor () >= EV_VERSION_MINOR)); =item unsigned int ev_supported_backends () @@ -194,8 +194,8 @@ Example: make sure we have the epoll method, because yeah this is cool and a must have and can we have a torrent of it please!!!11 - assert (("sorry, no epoll, no sex", - ev_supported_backends () & EVBACKEND_EPOLL)); + assert (("sorry, no epoll, no sex", + ev_supported_backends () & EVBACKEND_EPOLL)); =item unsigned int ev_recommended_backends () @@ -216,7 +216,7 @@ See the description of C watchers for more info. -=item ev_set_allocator (void *(*cb)(void *ptr, long size)) +=item ev_set_allocator (void *(*cb)(void *ptr, long size)) [NOT REENTRANT] Sets the allocation function to use (the prototype is similar - the semantics are identical to the C C89/SuS/POSIX function). It is @@ -252,7 +252,7 @@ ... ev_set_allocator (persistent_realloc); -=item ev_set_syserr_cb (void (*cb)(const char *msg)); +=item ev_set_syserr_cb (void (*cb)(const char *msg)); [NOT REENTRANT] Set the callback function to call on a retryable system call error (such as failed select, poll, epoll_wait). The message is a printable string @@ -361,6 +361,10 @@ a look at C to increase the amount of readiness notifications you get per iteration. +This backend maps C to the C set and C to the +C set (and to work around Microsoft Windows bugs, also onto the +C set on that platform). + =item C (value 2, poll backend, available everywhere except on windows) And this is your standard poll(2) backend. It's more complicated @@ -370,6 +374,9 @@ i.e. O(total_fds). See the entry for C, above, for performance tips. +This backend maps C to C, and +C to C. + =item C (value 4, Linux) For few fds, this backend is a bit little slower than poll and select, @@ -391,21 +398,25 @@ (or space) is available. Best performance from this backend is achieved by not unregistering all -watchers for a file descriptor until it has been closed, if possible, i.e. -keep at least one watcher active per fd at all times. +watchers for a file descriptor until it has been closed, if possible, +i.e. keep at least one watcher active per fd at all times. Stopping and +starting a watcher (without re-setting it) also usually doesn't cause +extra overhead. While nominally embeddable in other event loops, this feature is broken in all kernel versions tested so far. +This backend maps C and C in the same way as +C. + =item C (value 8, most BSD clones) -Kqueue deserves special mention, as at the time of this writing, it -was broken on all BSDs except NetBSD (usually it doesn't work reliably -with anything but sockets and pipes, except on Darwin, where of course -it's completely useless). For this reason it's not being "auto-detected" -unless you explicitly specify it explicitly in the flags (i.e. using -C) or libev was compiled on a known-to-be-good (-enough) -system like NetBSD. +Kqueue deserves special mention, as at the time of this writing, it was +broken on all BSDs except NetBSD (usually it doesn't work reliably with +anything but sockets and pipes, except on Darwin, where of course it's +completely useless). For this reason it's not being "auto-detected" unless +you explicitly specify it in the flags (i.e. using C) or +libev was compiled on a known-to-be-good (-enough) system like NetBSD. You still can embed kqueue into a normal poll or select backend and use it only for sockets (after having made sure that sockets work with kqueue on @@ -415,7 +426,7 @@ kernel is more efficient (which says nothing about its actual speed, of course). While stopping, setting and starting an I/O watcher does never cause an extra system call as with C, it still adds up to -two event changes per incident, support for C is very bad and it +two event changes per incident. Support for C is very bad and it drops fds silently in similarly hard-to-detect cases. This backend usually performs well under most conditions. @@ -424,8 +435,12 @@ everywhere, so you might need to test for this. And since it is broken almost everywhere, you should only use it when you have a lot of sockets (for which it usually works), by embedding it into another event loop -(e.g. C or C) and using it only for -sockets. +(e.g. C or C) and, did I mention it, +using it only for sockets. + +This backend maps C into an C kevent with +C, and C into an C kevent with +C. =item C (value 16, Solaris 8) @@ -448,9 +463,13 @@ descriptors a "slow" C or C backend might perform better. -On the positive side, ignoring the spurious readiness notifications, this -backend actually performed to specification in all tests and is fully -embeddable, which is a rare feat among the OS-specific backends. +On the positive side, with the exception of the spurious readiness +notifications, this backend actually performed fully to specification +in all tests and is fully embeddable, which is a rare feat among the +OS-specific backends. + +This backend maps C and C in the same way as +C. =item C @@ -466,21 +485,22 @@ backends will be tried (in the reverse order as listed here). If none are specified, all backends in C will be tried. -The most typical usage is like this: +Example: This is the most typical usage. - if (!ev_default_loop (0)) - fatal ("could not initialise libev, bad $LIBEV_FLAGS in environment?"); + if (!ev_default_loop (0)) + fatal ("could not initialise libev, bad $LIBEV_FLAGS in environment?"); -Restrict libev to the select and poll backends, and do not allow +Example: Restrict libev to the select and poll backends, and do not allow environment settings to be taken into account: - ev_default_loop (EVBACKEND_POLL | EVBACKEND_SELECT | EVFLAG_NOENV); + ev_default_loop (EVBACKEND_POLL | EVBACKEND_SELECT | EVFLAG_NOENV); -Use whatever libev has to offer, but make sure that kqueue is used if -available (warning, breaks stuff, best use only with your own private -event loop and only if you know the OS supports your types of fds): +Example: Use whatever libev has to offer, but make sure that kqueue is +used if available (warning, breaks stuff, best use only with your own +private event loop and only if you know the OS supports your types of +fds): - ev_default_loop (ev_recommended_backends () | EVBACKEND_KQUEUE); + ev_default_loop (ev_recommended_backends () | EVBACKEND_KQUEUE); =item struct ev_loop *ev_loop_new (unsigned int flags) @@ -495,9 +515,9 @@ Example: Try to create a event loop that uses epoll and nothing else. - struct ev_loop *epoller = ev_loop_new (EVBACKEND_EPOLL | EVFLAG_NOENV); - if (!epoller) - fatal ("no epoll found here, maybe it hides under your chair"); + struct ev_loop *epoller = ev_loop_new (EVBACKEND_EPOLL | EVFLAG_NOENV); + if (!epoller) + fatal ("no epoll found here, maybe it hides under your chair"); =item ev_default_destroy () @@ -546,11 +566,13 @@ Like C, but acts on an event loop created by C. Yes, you have to call this on every allocated event loop -after fork, and how you do this is entirely your own problem. +after fork that you want to re-use in the child, and how you do this is +entirely your own problem. =item int ev_is_default_loop (loop) -Returns true when the given loop actually is the default loop, false otherwise. +Returns true when the given loop is, in fact, the default loop, and false +otherwise. =item unsigned int ev_loop_count (loop) @@ -575,6 +597,18 @@ time used for relative timers. You can treat it as the timestamp of the event occurring (or more correctly, libev finding out about it). +=item ev_now_update (loop) + +Establishes the current time by querying the kernel, updating the time +returned by C in the progress. This is a costly operation and +is usually done automatically within C. + +This function is rarely useful, but when some event callback runs for a +very long time without entering the event loop, updating libev's idea of +the current time is a good idea. + +See also "The special problem of time updates" in the C section. + =item ev_loop (loop, int flags) Finally, this is it, the event handler. This function usually is called @@ -586,41 +620,48 @@ Please note that an explicit C is usually better than relying on all watchers to be stopped when deciding when a program has -finished (especially in interactive programs), but having a program that -automatically loops as long as it has to and no longer by virtue of -relying on its watchers stopping correctly is a thing of beauty. +finished (especially in interactive programs), but having a program +that automatically loops as long as it has to and no longer by virtue +of relying on its watchers stopping correctly, that is truly a thing of +beauty. A flags value of C will look for new events, will handle -those events and any outstanding ones, but will not block your process in -case there are no events and will return after one iteration of the loop. +those events and any already outstanding ones, but will not block your +process in case there are no events and will return after one iteration of +the loop. A flags value of C will look for new events (waiting if -necessary) and will handle those and any outstanding ones. It will block -your process until at least one new event arrives, and will return after -one iteration of the loop. This is useful if you are waiting for some -external event in conjunction with something not expressible using other -libev watchers. However, a pair of C/C watchers is +necessary) and will handle those and any already outstanding ones. It +will block your process until at least one new event arrives (which could +be an event internal to libev itself, so there is no guarentee that a +user-registered callback will be called), and will return after one +iteration of the loop. + +This is useful if you are waiting for some external event in conjunction +with something not expressible using other libev watchers (i.e. "roll your +own C"). However, a pair of C/C watchers is usually a better approach for this kind of thing. Here are the gory details of what C does: - Before the first iteration, call any pending watchers. * If EVFLAG_FORKCHECK was used, check for a fork. - - If a fork was detected, queue and call all fork watchers. + - If a fork was detected (by any means), queue and call all fork watchers. - Queue and call all prepare watchers. - - If we have been forked, recreate the kernel state. + - If we have been forked, detach and recreate the kernel state + as to not disturb the other process. - Update the kernel state with all outstanding changes. - - Update the "event loop time". + - Update the "event loop time" (ev_now ()). - Calculate for how long to sleep or block, if at all (active idle watchers, EVLOOP_NONBLOCK or not having any active watchers at all will result in not sleeping). - Sleep if the I/O and timer collect interval say so. - Block the process, waiting for any events. - Queue all outstanding I/O (fd) events. - - Update the "event loop time" and do time jump handling. - - Queue all outstanding timers. - - Queue all outstanding periodics. - - If no events are pending now, queue all idle watchers. + - Update the "event loop time" (ev_now ()), and do time jump adjustments. + - Queue all expired timers. + - Queue all expired periodics. + - Unless any events are pending now, queue all idle watchers. - Queue all check watchers. - Call all queued watchers in reverse order (i.e. check watchers first). Signals and child watchers are implemented as I/O watchers, and will @@ -635,7 +676,7 @@ ... queue jobs here, make sure they register event watchers as long ... as they still have work to do (even an idle watcher will do..) ev_loop (my_loop, 0); - ... jobs done. yeah! + ... jobs done or somebody called unloop. yeah! =item ev_unloop (loop, how) @@ -646,18 +687,23 @@ This "unloop state" will be cleared when entering C again. +It is safe to call C from otuside any C calls. + =item ev_ref (loop) =item ev_unref (loop) Ref/unref can be used to add or remove a reference count on the event loop: Every watcher keeps one reference, and as long as the reference -count is nonzero, C will not return on its own. If you have -a watcher you never unregister that should not keep C from -returning, ev_unref() after starting, and ev_ref() before stopping it. For -example, libev itself uses this for its internal signal pipe: It is not -visible to the libev user and should not keep C from exiting if -no event watchers registered by it are active. It is also an excellent +count is nonzero, C will not return on its own. + +If you have a watcher you never unregister that should not keep C +from returning, call ev_unref() after starting, and ev_ref() before +stopping it. + +As an example, libev itself uses this for its internal signal pipe: It is +not visible to the libev user and should not keep C from exiting +if no event watchers registered by it are active. It is also an excellent way to do this for generic recurring timers or from within third-party libraries. Just remember to I and I (but only if the watcher wasn't active before, or was active before, @@ -666,31 +712,33 @@ Example: Create a signal watcher, but keep it from keeping C running when nothing else is active. - struct ev_signal exitsig; - ev_signal_init (&exitsig, sig_cb, SIGINT); - ev_signal_start (loop, &exitsig); - evf_unref (loop); + struct ev_signal exitsig; + ev_signal_init (&exitsig, sig_cb, SIGINT); + ev_signal_start (loop, &exitsig); + evf_unref (loop); Example: For some weird reason, unregister the above signal handler again. - ev_ref (loop); - ev_signal_stop (loop, &exitsig); + ev_ref (loop); + ev_signal_stop (loop, &exitsig); =item ev_set_io_collect_interval (loop, ev_tstamp interval) =item ev_set_timeout_collect_interval (loop, ev_tstamp interval) These advanced functions influence the time that libev will spend waiting -for events. Both are by default C<0>, meaning that libev will try to -invoke timer/periodic callbacks and I/O callbacks with minimum latency. +for events. Both time intervals are by default C<0>, meaning that libev +will try to invoke timer/periodic callbacks and I/O callbacks with minimum +latency. Setting these to a higher value (the C I be >= C<0>) -allows libev to delay invocation of I/O and timer/periodic callbacks to -increase efficiency of loop iterations. - -The background is that sometimes your program runs just fast enough to -handle one (or very few) event(s) per loop iteration. While this makes -the program responsive, it also wastes a lot of CPU time to poll for new +allows libev to delay invocation of I/O and timer/periodic callbacks +to increase efficiency of loop iterations (or to increase power-saving +opportunities). + +The idea is that sometimes your program runs just fast enough to handle +one (or very few) event(s) per loop iteration. While this makes the +program responsive, it also wastes a lot of CPU time to poll for new events, especially with backends like C function doesn't follow POSIX in that it requires socket I and not socket I (it is also extremely buggy). This makes select very inefficient, and also -requires a mapping from file descriptors to socket handles. See the +requires a mapping from file descriptors to socket handles (the Microsoft +C runtime provides the function C<_open_osfhandle> for this). See the discussion of the C, C and C preprocessor symbols for more info. The configuration for a "naked" win32 using the Microsoft runtime libraries and raw winsocket select is: - #define EV_USE_SELECT 1 - #define EV_SELECT_IS_WINSOCKET 1 /* forces EV_SELECT_USE_FD_SET, too */ + #define EV_USE_SELECT 1 + #define EV_SELECT_IS_WINSOCKET 1 /* forces EV_SELECT_USE_FD_SET, too */ 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. @@ -3361,18 +3555,26 @@ =back +=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 +=item C must have compatible +calling conventions regardless of C. + +Libev assumes not only that all watcher pointers have the same internal +structure (guaranteed by POSIX but not by ISO C for example), but it also +assumes that the same (machine) code can be used to call any watcher +callback: The watcher callbacks have different type signatures, but libev +calls them using an C internally. + =item C must be thread-atomic as well The type C (or whatever is defined as -C) must be atomic w.r.t. accesses from different +C) must be atomic with respect to accesses from different threads. This is not part of the specification for C, but is believed to be sufficiently portable. @@ -3391,11 +3593,11 @@ =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 @@ -3409,56 +3611,75 @@ 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 AUTHOR