From 3af7813d88284b99c550f1a20696536ebc579b32 Mon Sep 17 00:00:00 2001 Message-Id: <3af7813d88284b99c550f1a20696536ebc579b32.1715225864.git.mdw@distorted.org.uk> From: Mark Wooding Date: Fri, 23 May 2008 17:51:51 +0100 Subject: [PATCH] DisOrder's event loop now stores its timeouts in heap sorted by trigger time. Organization: Straylight/Edgeware From: Richard Kettlewell --- .bzrignore | 2 +- lib/Makefile.am | 12 ++++-- lib/event.c | 105 +++++++++++++++++++++--------------------------- lib/t-event.c | 80 ++++++++++++++++++++++++++++++++++++ lib/timeval.h | 33 ++++++++++++++- 5 files changed, 167 insertions(+), 65 deletions(-) create mode 100644 lib/t-event.c diff --git a/.bzrignore b/.bzrignore index 1c02594..d14bd69 100644 --- a/.bzrignore +++ b/.bzrignore @@ -189,4 +189,4 @@ doc/disorder_actions.5.in doc/disorder_templates.5.in lib/t-arcfour lib/t-charset - +lib/t-event diff --git a/lib/Makefile.am b/lib/Makefile.am index 2058de2..6b7aec8 100644 --- a/lib/Makefile.am +++ b/lib/Makefile.am @@ -19,10 +19,10 @@ # TESTS=t-addr t-arcfour t-basen t-bits t-cache t-casefold t-charset \ - t-cookies t-filepart t-hash t-heap t-hex t-kvp t-mime t-printf \ - t-regsub t-selection t-signame t-sink t-split t-syscalls \ - t-trackname t-unicode t-url t-utf8 t-vector t-words t-wstat \ - t-macros t-cgi + t-cookies t-event t-filepart t-hash t-heap t-hex t-kvp t-mime \ + t-printf t-regsub t-selection t-signame t-sink t-split \ + t-syscalls t-trackname t-unicode t-url t-utf8 t-vector t-words \ + t-wstat t-macros t-cgi noinst_LIBRARIES=libdisorder.a include_HEADERS=disorder.h @@ -161,6 +161,10 @@ t_cookies_SOURCES=t-cookies.c test.c test.h t_cookies_LDADD=libdisorder.a $(LIBPCRE) $(LIBICONV) $(LIBGC) t_cookies_DEPENDENCIES=libdisorder.a +t_event_SOURCES=t-event.c test.c test.h +t_event_LDADD=libdisorder.a $(LIBPCRE) $(LIBICONV) $(LIBGC) +t_event_DEPENDENCIES=libdisorder.a + t_filepart_SOURCES=t-filepart.c test.c test.h t_filepart_LDADD=libdisorder.a $(LIBPCRE) $(LIBICONV) $(LIBGC) t_filepart_DEPENDENCIES=libdisorder.a diff --git a/lib/event.c b/lib/event.c index 0e97596..4c3e9af 100644 --- a/lib/event.c +++ b/lib/event.c @@ -47,6 +47,8 @@ #include "printf.h" #include "sink.h" #include "vector.h" +#include "timeval.h" +#include "heap.h" /** @brief A timeout */ struct timeout { @@ -54,9 +56,18 @@ struct timeout { struct timeval when; ev_timeout_callback *callback; void *u; - int resolve; + int active; }; +/** @brief Comparison function for timeouts */ +static int timeout_lt(const struct timeout *a, + const struct timeout *b) { + return tvlt(&a->when, &b->when); +} + +HEAP_TYPE(timeout_heap, struct timeout *, timeout_lt); +HEAP_DEFINE(timeout_heap, struct timeout *, timeout_lt); + /** @brief A file descriptor in one mode */ struct fd { int fd; @@ -106,11 +117,8 @@ struct ev_source { /** @brief File descriptors, per mode */ struct fdmode mode[ev_nmodes]; - /** @brief Sorted linked list of timeouts - * - * We could use @ref HEAP_TYPE now, but there aren't many timeouts. - */ - struct timeout *timeouts; + /** @brief Heap of timeouts */ + struct timeout_heap timeouts[1]; /** @brief Array of handled signals */ struct signal signals[NSIG]; @@ -146,27 +154,6 @@ static const char *modenames[] = { "read", "write", "except" }; /* utilities ******************************************************************/ -/** @brief Great-than comparison for timevals - * - * Ought to be in @file lib/timeval.h - */ -static inline int gt(const struct timeval *a, const struct timeval *b) { - if(a->tv_sec > b->tv_sec) - return 1; - if(a->tv_sec == b->tv_sec - && a->tv_usec > b->tv_usec) - return 1; - return 0; -} - -/** @brief Greater-than-or-equal comparison for timevals - * - * Ought to be in @ref lib/timeval.h - */ -static inline int ge(const struct timeval *a, const struct timeval *b) { - return !gt(b, a); -} - /* creation *******************************************************************/ /** @brief Create a new event loop */ @@ -179,6 +166,7 @@ ev_source *ev_new(void) { FD_ZERO(&ev->mode[n].enabled); ev->sigpipe[0] = ev->sigpipe[1] = -1; sigemptyset(&ev->sigmask); + timeout_heap_init(ev->timeouts); return ev; } @@ -194,7 +182,7 @@ int ev_run(ev_source *ev) { int n, mode; int ret; int maxfd; - struct timeout *t, **tt; + struct timeout *timeouts, *t, **tt; struct stat sb; xgettimeofday(&now, 0); @@ -202,10 +190,24 @@ int ev_run(ev_source *ev) { * while we're handling them (otherwise we'd have to break out of infinite * loops, preferrably without starving better-behaved subsystems). Hence * the slightly complicated two-phase approach here. */ - for(t = ev->timeouts; - t && ge(&now, &t->when); - t = t->next) { - t->resolve = 1; + /* First we read those timeouts that have triggered out of the heap. We + * keep them in the same order they came out of the heap in. */ + tt = &timeouts; + while(timeout_heap_count(ev->timeouts) + && tvle(&timeout_heap_first(ev->timeouts)->when, &now)) { + /* This timeout has reached its trigger time; provided it has not been + * cancelled we add it to the timeouts list. */ + t = timeout_heap_remove(ev->timeouts); + if(t->active) { + *tt = t; + tt = &t->next; + } + } + *tt = 0; + /* Now we can run the callbacks for those timeouts. They might add further + * timeouts that are already in the past but they won't trigger until the + * next time round the event loop. */ + for(t = timeouts; t; t = t->next) { D(("calling timeout for %ld.%ld callback %p %p", (long)t->when.tv_sec, (long)t->when.tv_usec, (void *)t->callback, t->u)); @@ -213,13 +215,6 @@ int ev_run(ev_source *ev) { if(ret) return ret; } - tt = &ev->timeouts; - while((t = *tt)) { - if(t->resolve) - *tt = t->next; - else - tt = &t->next; - } maxfd = 0; for(mode = 0; mode < ev_nmodes; ++mode) { ev->mode[mode].tripped = ev->mode[mode].enabled; @@ -228,10 +223,11 @@ int ev_run(ev_source *ev) { } xsigprocmask(SIG_UNBLOCK, &ev->sigmask, 0); do { - if(ev->timeouts) { + if(timeout_heap_count(ev->timeouts)) { + t = timeout_heap_first(ev->timeouts); xgettimeofday(&now, 0); - delta.tv_sec = ev->timeouts->when.tv_sec - now.tv_sec; - delta.tv_usec = ev->timeouts->when.tv_usec - now.tv_usec; + delta.tv_sec = t->when.tv_sec - now.tv_sec; + delta.tv_usec = t->when.tv_usec - now.tv_usec; if(delta.tv_usec < 0) { delta.tv_usec += 1000000; --delta.tv_sec; @@ -473,7 +469,7 @@ int ev_timeout(ev_source *ev, const struct timeval *when, ev_timeout_callback *callback, void *u) { - struct timeout *t, *p, **pp; + struct timeout *t; D(("registering timeout at %ld.%ld callback %p %p", when ? (long)when->tv_sec : 0, when ? (long)when->tv_usec : 0, @@ -483,11 +479,8 @@ int ev_timeout(ev_source *ev, t->when = *when; t->callback = callback; t->u = u; - pp = &ev->timeouts; - while((p = *pp) && gt(&t->when, &p->when)) - pp = &p->next; - t->next = p; - *pp = t; + t->active = 1; + timeout_heap_insert(ev->timeouts, t); if(handlep) *handlep = t; return 0; @@ -500,19 +493,13 @@ int ev_timeout(ev_source *ev, * * If @p handle is 0 then this is a no-op. */ -int ev_timeout_cancel(ev_source *ev, +int ev_timeout_cancel(ev_source attribute((unused)) *ev, ev_timeout_handle handle) { - struct timeout *t = handle, *p, **pp; + struct timeout *t = handle; - if(!t) - return 0; - for(pp = &ev->timeouts; (p = *pp) && p != t; pp = &p->next) - ; - if(p) { - *pp = p->next; - return 0; - } else - return -1; + if(t) + t->active = 0; + return 0; } /* signals ********************************************************************/ diff --git a/lib/t-event.c b/lib/t-event.c new file mode 100644 index 0000000..9172833 --- /dev/null +++ b/lib/t-event.c @@ -0,0 +1,80 @@ +/* + * This file is part of DisOrder. + * Copyright (C) 2008 Richard Kettlewell + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 + * USA + */ +#include "test.h" +#include "event.h" + +#include + +static ev_source *ev; + +static int run1, run2, run3; +static ev_timeout_handle t1, t2, t3; + +static int callback1(ev_source attribute((unused)) *ev, + const struct timeval attribute((unused)) *now, + void attribute((unused)) *u) { + run1 = 1; + ev_timeout_cancel(ev, t2); + return 0; +} + +static int callback2(ev_source attribute((unused)) *ev, + const struct timeval attribute((unused)) *now, + void attribute((unused)) *u) { + run2 = 1; + return 0; +} + +static int callback3(ev_source attribute((unused)) *ev, + const struct timeval attribute((unused)) *now, + void attribute((unused)) *u) { + run3 = 1; + return 1; +} + +static void test_event(void) { + struct timeval w; + + ev = ev_new(); + w.tv_sec = time(0) + 2; + w.tv_usec = 0; + ev_timeout(ev, &t1, &w, callback1, 0); + w.tv_sec = time(0) + 3; + w.tv_usec = 0; + ev_timeout(ev, &t2, &w, callback2, 0); + w.tv_sec = time(0) + 4; + w.tv_usec = 0; + ev_timeout(ev, &t3, &w, callback3, 0); + check_integer(ev_run(ev), 1); + check_integer(run1, 1); + check_integer(run2, 0); + check_integer(run3, 1); +} + +TEST(event); + +/* +Local Variables: +c-basic-offset:2 +comment-column:40 +fill-column:79 +indent-tabs-mode:nil +End: +*/ diff --git a/lib/timeval.h b/lib/timeval.h index 16c08e9..c2cd106 100644 --- a/lib/timeval.h +++ b/lib/timeval.h @@ -1,6 +1,6 @@ /* * This file is part of DisOrder. - * Copyright (C) 2007 Richard Kettlewell + * Copyright (C) 2007, 2008 Richard Kettlewell * * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by @@ -65,6 +65,37 @@ static inline int64_t tvsub_us(const struct timeval a, - ((uint64_t)b.tv_sec * 1000000 + b.tv_usec)); } +/** @brief Great-than comparison for timevals */ +static inline int tvgt(const struct timeval *a, const struct timeval *b) { + if(a->tv_sec > b->tv_sec) + return 1; + if(a->tv_sec == b->tv_sec + && a->tv_usec > b->tv_usec) + return 1; + return 0; +} + +/** @brief Less-than + comparison for timevals */ +static inline int tvlt(const struct timeval *a, const struct timeval *b) { + if(a->tv_sec < b->tv_sec) + return 1; + if(a->tv_sec == b->tv_sec + && a->tv_usec < b->tv_usec) + return 1; + return 0; +} + +/** @brief Greater-than-or-equal comparison for timevals */ +static inline int tvge(const struct timeval *a, const struct timeval *b) { + return !tvlt(a, b); +} + +/** @brief Less-than-or-equal comparison for timevals */ +static inline int tvle(const struct timeval *a, const struct timeval *b) { + return !tvgt(a, b); +} + #endif /* TIMEVAL_H */ /* -- [mdw]