From a29fb691be0c199fb643de22a7969a410c3b1e31 Mon Sep 17 00:00:00 2001 From: root Date: Tue, 30 Oct 2007 23:10:33 +0000 Subject: much better --- README | 58 +++++++++++++++++++++-- ev.c | 164 +++++++++++++++++++++++++++++++++++++++++++++++++++-------------- ev.h | 7 +-- 3 files changed, 187 insertions(+), 42 deletions(-) diff --git a/README b/README index 4e8ec2d..5895388 100644 --- a/README +++ b/README @@ -2,8 +2,58 @@ libev is modelled after libevent (http://monkey.org/~provos/libevent/), but aims to be faster and more correct, and also more featureful. Examples: - multiple watchers can wait for the same event without deregistering others. -- fork() is supported and can be handled. -- timers are handled as a priority queue (faster) -- watchers use less memory (faster) -- less calls to epoll_ctl (faster) + (registering two read events on fd 10 and unregistering one will not + break the other) + +- fork() is supported and can be handled + (there is no way to recover from a fork when libevent is active) + +- timers are handled as a priority queue + (libevent uses a less efficient red-black tree) + +- supports absolute (wallclock-based) timers in addition to relative ones, + i.e. can schedule timers to occur after n seconds, or at a specific time. + +- timers can be repeating (both absolute and relative ones) + +- detects time jumps and adjusts timers + (works for both forward and backward time jumps and also for absolute timers) + +- can correctly remove timers while executing callbacks + (libevent doesn't handle this reliably and can crash) + +- less calls to epoll_ctl + (stopping and starting an io watcher between two loop iterations will now + result in spuriois epoll_ctl calls) + +- usually less calls to gettimeofday and clock_gettime + (libevent calls it on every timer event change, libev twice per iteration) + +- watchers use less memory + (libevent on amd64: 152 bytes, libev: <= 56 bytes) + +- library uses less memory + (libevent allocates large data structures wether used or not, libev + scales all its data structures dynamically) + +- no hardcoded arbitrary limits + (libevent contains an off-by-one bug and sometimes hardcodes a limit of + 32000 fds) + +- libev separates timer, signal and io watchers from each other + (libevent combines them, but with libev you can combine them yourself + by reusing the same callback and still save memory) + +- simpler design, backends are potentially much simpler + (in libevent, backends have to deal with watchers, thus the problems) + (epoll backend in libevent: 366 lines, libev: 89 lines, and more features) + +whats missing? + +- evdns, evhttp, bufferevent are missing, libev is only an even library at + the moment. + +- no priority support at the moment. + +- kqueue, poll (libev currently implements epoll and select). diff --git a/ev.c b/ev.c index 3105078..67d0368 100644 --- a/ev.c +++ b/ev.c @@ -3,6 +3,7 @@ #include +#include #include #include #include @@ -15,6 +16,7 @@ #define HAVE_REALTIME 1 #define HAVE_SELECT 0 +#define MIN_TIMEJUMP 1. /* minimum timejump that gets detected (if monotonic clock available) */ #define MAX_BLOCKTIME 60. #include "ev.h" @@ -27,6 +29,7 @@ struct ev_watcher_list { EV_WATCHER_LIST (ev_watcher_list); }; +static ev_tstamp now, diff; /* monotonic clock */ ev_tstamp ev_now; int ev_method; @@ -131,11 +134,14 @@ fd_event (int fd, int events) } } -static struct ev_timer **timers; -static int timermax, timercnt; +static struct ev_timer **atimers; +static int atimermax, atimercnt; + +static struct ev_timer **rtimers; +static int rtimermax, rtimercnt; static void -upheap (int k) +upheap (struct ev_timer **timers, int k) { struct ev_timer *w = timers [k]; @@ -152,15 +158,15 @@ upheap (int k) } static void -downheap (int k) +downheap (struct ev_timer **timers, int N, int k) { struct ev_timer *w = timers [k]; - while (k < (timercnt >> 1)) + while (k < (N >> 1)) { int j = k << 1; - if (j + 1 < timercnt && timers [j]->at > timers [j + 1]->at) + if (j + 1 < N && timers [j]->at > timers [j + 1]->at) ++j; if (w->at <= timers [j]->at) @@ -176,7 +182,7 @@ downheap (int k) } static struct ev_signal **signals; -static int signalmax, signalcnt; +static int signalmax; static void signals_init (struct ev_signal **base, int count) @@ -203,6 +209,8 @@ int ev_init (int flags) #endif ev_now = ev_time (); + now = get_clock (); + diff = ev_now - now; #if HAVE_EPOLL if (epoll_init (flags)) @@ -252,32 +260,77 @@ call_pending () } static void -timer_reify (void) +timers_reify (struct ev_timer **timers, int timercnt, ev_tstamp now) { - while (timercnt && timers [0]->at <= ev_now) + while (timercnt && timers [0]->at <= now) { struct ev_timer *w = timers [0]; - /* first reschedule timer */ + /* first reschedule or stop timer */ if (w->repeat) { if (w->is_abs) - w->at += ceil ((ev_now - w->at) / w->repeat + 1.) * w->repeat; + w->at += floor ((now - w->at) / w->repeat + 1.) * w->repeat; else - w->at = ev_now + w->repeat; + w->at = now + w->repeat; + + assert (w->at > now); - downheap (0); + downheap (timers, timercnt, 0); } else - evtimer_stop (w); /* nonrepeating: stop timer */ + { + evtimer_stop (w); /* nonrepeating: stop timer */ + --timercnt; /* maybe pass by reference instead? */ + } event ((struct ev_watcher *)w, EV_TIMEOUT); } } +static void +time_update () +{ + int i; + ev_now = ev_time (); + + if (have_monotonic) + { + ev_tstamp odiff = diff; + + /* detecting time jumps is much more difficult */ + for (i = 2; --i; ) /* loop a few times, before making important decisions */ + { + now = get_clock (); + diff = ev_now - now; + + if (fabs (odiff - diff) < MIN_TIMEJUMP) + return; /* all is well */ + + ev_now = ev_time (); + } + + /* time jump detected, reschedule atimers */ + for (i = 0; i < atimercnt; ++i) + { + struct ev_timer *w = atimers [i]; + w->at += ceil ((ev_now - w->at) / w->repeat + 1.) * w->repeat; + } + } + else + { + if (now > ev_now || now < ev_now - MAX_BLOCKTIME - MIN_TIMEJUMP) + /* time jump detected, adjust rtimers */ + for (i = 0; i < rtimercnt; ++i) + rtimers [i]->at += ev_now - now; + + now = ev_now; + } +} + int ev_loop_done; -int ev_loop (int flags) +void ev_loop (int flags) { double block; ev_loop_done = flags & EVLOOP_ONESHOT; @@ -288,25 +341,38 @@ int ev_loop (int flags) method_reify (); fdchangecnt = 0; /* calculate blocking time */ - ev_now = ev_time (); - if (flags & EVLOOP_NONBLOCK) block = 0.; - else if (!timercnt) - block = MAX_BLOCKTIME; else { - block = timers [0]->at - ev_now + method_fudge; + block = MAX_BLOCKTIME; + + if (rtimercnt) + { + ev_tstamp to = rtimers [0]->at - get_clock () + method_fudge; + if (block > to) block = to; + } + + if (atimercnt) + { + ev_tstamp to = atimers [0]->at - ev_time () + method_fudge; + if (block > to) block = to; + } + if (block < 0.) block = 0.; - else if (block > MAX_BLOCKTIME) block = MAX_BLOCKTIME; } method_poll (block); + /* update ev_now, do magic */ + time_update (); + /* put pending timers into pendign queue and reschedule them */ - timer_reify (); + /* absolute timers first */ + timers_reify (atimers, atimercnt, ev_now); + /* relative timers second */ + timers_reify (rtimers, rtimercnt, now); - ev_now = ev_time (); call_pending (); } while (!ev_loop_done); @@ -393,14 +459,22 @@ evtimer_start (struct ev_timer *w) /* this formula differs from the one in timer_reify becuse we do not round up */ if (w->repeat) w->at += ceil ((ev_now - w->at) / w->repeat) * w->repeat; + + ev_start ((struct ev_watcher *)w, ++atimercnt); + array_needsize (atimers, atimermax, atimercnt, ); + atimers [atimercnt - 1] = w; + upheap (atimers, atimercnt - 1); } else - w->at += ev_now; + { + w->at += now; + + ev_start ((struct ev_watcher *)w, ++rtimercnt); + array_needsize (rtimers, rtimermax, rtimercnt, ); + rtimers [rtimercnt - 1] = w; + upheap (rtimers, rtimercnt - 1); + } - ev_start ((struct ev_watcher *)w, ++timercnt); - array_needsize (timers, timermax, timercnt, ); - timers [timercnt - 1] = w; - upheap (timercnt - 1); } void @@ -409,10 +483,21 @@ evtimer_stop (struct ev_timer *w) if (!ev_is_active (w)) return; - if (w->active < timercnt--) + if (w->is_abs) { - timers [w->active - 1] = timers [timercnt]; - downheap (w->active - 1); + if (w->active < atimercnt--) + { + atimers [w->active - 1] = atimers [atimercnt]; + downheap (atimers, atimercnt, w->active - 1); + } + } + else + { + if (w->active < rtimercnt--) + { + rtimers [w->active - 1] = rtimers [rtimercnt]; + downheap (rtimers, rtimercnt, w->active - 1); + } } ev_stop ((struct ev_watcher *)w); @@ -451,7 +536,9 @@ sin_cb (struct ev_io *w, int revents) static void ocb (struct ev_timer *w, int revents) { - fprintf (stderr, "timer %f,%f (%x) (%f) d%p\n", w->at, w->repeat, revents, w->at - ev_time (), w->data); + //fprintf (stderr, "timer %f,%f (%x) (%f) d%p\n", w->at, w->repeat, revents, w->at - ev_time (), w->data); + evtimer_stop (w); + evtimer_start (w); } int main (void) @@ -464,18 +551,25 @@ int main (void) evio_set (&sin, 0, EV_READ); evio_start (&sin); - struct ev_timer t[1000]; + struct ev_timer t[10000]; +#if 1 int i; - for (i = 0; i < 1000; ++i) + for (i = 0; i < 10000; ++i) { struct ev_timer *w = t + i; evw_init (w, ocb, i); - evtimer_set_rel (w, drand48 (), 0); + evtimer_set_abs (w, drand48 (), 0.99775533); evtimer_start (w); if (drand48 () < 0.5) evtimer_stop (w); } +#endif + + struct ev_timer t1; + evw_init (&t1, ocb, 0); + evtimer_set_abs (&t1, 5, 10); + evtimer_start (&t1); ev_loop (0); diff --git a/ev.h b/ev.h index 865338f..3467060 100644 --- a/ev.h +++ b/ev.h @@ -26,9 +26,9 @@ struct ev_timer { EV_WATCHER_LIST (ev_timer); - ev_tstamp at; /* ro */ + ev_tstamp at; /* private */ ev_tstamp repeat; /* rw */ - unsigned char is_abs; /* rw */ + unsigned char is_abs; /* ro */ }; struct ev_io @@ -61,11 +61,12 @@ ev_tstamp ev_time (void); #define EVLOOP_NONBLOCK 1 /* do not block/wait */ #define EVLOOP_ONESHOT 2 /* block *once* only */ -int ev_loop (int flags); +void ev_loop (int flags); extern int ev_loop_done; /* set to 1 to break out of event loop */ /* these may evaluate ev multiple times, and the other arguments at most once */ #define evw_init(ev,cb_,data_) do { (ev)->active = 0; (ev)->cb = (cb_); (ev)->data = (void *)data_; } while (0) + #define evio_set(ev,fd_,events_) do { (ev)->fd = (fd_); (ev)->events = (events_); } while (0) #define evtimer_set_rel(ev,after_,repeat_) do { (ev)->at = (after_); (ev)->repeat = (repeat_); (ev)->is_abs = 0; } while (0) #define evtimer_set_abs(ev,at_,repeat_) do { (ev)->at = (at_); (ev)->repeat = (repeat_); (ev)->is_abs = 1; } while (0) -- cgit v1.2.3