dovecot: Use priority queue to implement timeout handling. Added...
dovecot at dovecot.org
dovecot at dovecot.org
Thu Jan 3 23:19:37 EET 2008
details: http://hg.dovecot.org/dovecot/rev/becdf2eacdce
changeset: 7098:becdf2eacdce
user: Timo Sirainen <tss at iki.fi>
date: Thu Jan 03 23:19:33 2008 +0200
description:
Use priority queue to implement timeout handling. Added timeout_reset().
diffstat:
7 files changed, 121 insertions(+), 130 deletions(-)
src/lib/ioloop-epoll.c | 4
src/lib/ioloop-internal.h | 14 +-
src/lib/ioloop-kqueue.c | 4
src/lib/ioloop-poll.c | 4
src/lib/ioloop-select.c | 4
src/lib/ioloop.c | 219 +++++++++++++++++++++------------------------
src/lib/ioloop.h | 2
diffs (truncated from 426 to 300 lines):
diff -r 618472c2c3c5 -r becdf2eacdce src/lib/ioloop-epoll.c
--- a/src/lib/ioloop-epoll.c Thu Jan 03 23:18:46 2008 +0200
+++ b/src/lib/ioloop-epoll.c Thu Jan 03 23:19:33 2008 +0200
@@ -162,7 +162,7 @@ void io_loop_handler_run(struct ioloop *
bool call;
/* get the time left for next timeout task */
- msecs = io_loop_get_wait_time(ioloop->timeouts, &tv, NULL);
+ msecs = io_loop_get_wait_time(ioloop, &tv, NULL);
events = array_get_modifiable(&ctx->events, &events_count);
ret = epoll_wait(ctx->epfd, events, events_count, msecs);
@@ -170,7 +170,7 @@ void io_loop_handler_run(struct ioloop *
i_fatal("epoll_wait(): %m");
/* execute timeout handlers */
- io_loop_handle_timeouts(ioloop, ret == 0);
+ io_loop_handle_timeouts(ioloop);
if (!ioloop->running)
return;
diff -r 618472c2c3c5 -r becdf2eacdce src/lib/ioloop-internal.h
--- a/src/lib/ioloop-internal.h Thu Jan 03 23:18:46 2008 +0200
+++ b/src/lib/ioloop-internal.h Thu Jan 03 23:19:33 2008 +0200
@@ -1,6 +1,7 @@
#ifndef IOLOOP_INTERNAL_H
#define IOLOOP_INTERNAL_H
+#include "priorityq.h"
#include "ioloop.h"
#ifndef IOLOOP_INITIAL_FD_COUNT
@@ -12,7 +13,7 @@ struct ioloop {
struct io_file *io_files;
struct io_file *next_io_file;
- struct timeout *timeouts; /* sorted by next_run */
+ struct priorityq *timeouts;
struct ioloop_handler_context *handler_context;
struct ioloop_notify_handler_context *notify_handler_context;
@@ -38,21 +39,18 @@ struct io_file {
};
struct timeout {
- struct timeout *next;
+ struct priorityq_item item;
+ unsigned int msecs;
struct timeval next_run;
- unsigned int msecs;
-
- unsigned int run_now:1;
- unsigned int destroyed:1;
timeout_callback_t *callback;
void *context;
};
-int io_loop_get_wait_time(struct timeout *timeout, struct timeval *tv,
+int io_loop_get_wait_time(struct ioloop *ioloop, struct timeval *tv,
struct timeval *tv_now);
-void io_loop_handle_timeouts(struct ioloop *ioloop, bool update_run_now);
+void io_loop_handle_timeouts(struct ioloop *ioloop);
/* I/O handler calls */
void io_loop_handle_add(struct ioloop *ioloop, struct io_file *io);
diff -r 618472c2c3c5 -r becdf2eacdce src/lib/ioloop-kqueue.c
--- a/src/lib/ioloop-kqueue.c Thu Jan 03 23:18:46 2008 +0200
+++ b/src/lib/ioloop-kqueue.c Thu Jan 03 23:19:33 2008 +0200
@@ -118,7 +118,7 @@ void io_loop_handler_run(struct ioloop *
int msecs, ret, i;
/* get the time left for next timeout task */
- msecs = io_loop_get_wait_time(ioloop->timeouts, &tv, NULL);
+ msecs = io_loop_get_wait_time(ioloop, &tv, NULL);
ts.tv_sec = tv.tv_sec;
ts.tv_nsec = tv.tv_usec * 1000;
@@ -135,7 +135,7 @@ void io_loop_handler_run(struct ioloop *
}
/* execute timeout handlers */
- io_loop_handle_timeouts(ioloop, ret == 0);
+ io_loop_handle_timeouts(ioloop);
for (i = 0; i < ret; i++) {
/* io_loop_handle_add() may cause events array reallocation,
diff -r 618472c2c3c5 -r becdf2eacdce src/lib/ioloop-poll.c
--- a/src/lib/ioloop-poll.c Thu Jan 03 23:18:46 2008 +0200
+++ b/src/lib/ioloop-poll.c Thu Jan 03 23:19:33 2008 +0200
@@ -149,14 +149,14 @@ void io_loop_handler_run(struct ioloop *
bool call;
/* get the time left for next timeout task */
- msecs = io_loop_get_wait_time(ioloop->timeouts, &tv, NULL);
+ msecs = io_loop_get_wait_time(ioloop, &tv, NULL);
ret = poll(ctx->fds, ctx->fds_pos, msecs);
if (ret < 0 && errno != EINTR)
i_fatal("poll(): %m");
/* execute timeout handlers */
- io_loop_handle_timeouts(ioloop, ret == 0);
+ io_loop_handle_timeouts(ioloop);
if (ret <= 0 || !ioloop->running) {
/* no I/O events */
diff -r 618472c2c3c5 -r becdf2eacdce src/lib/ioloop-select.c
--- a/src/lib/ioloop-select.c Thu Jan 03 23:18:46 2008 +0200
+++ b/src/lib/ioloop-select.c Thu Jan 03 23:19:33 2008 +0200
@@ -111,7 +111,7 @@ void io_loop_handler_run(struct ioloop *
int ret;
/* get the time left for next timeout task */
- io_loop_get_wait_time(ioloop->timeouts, &tv, NULL);
+ io_loop_get_wait_time(ioloop, &tv, NULL);
memcpy(&ctx->tmp_read_fds, &ctx->read_fds, sizeof(fd_set));
memcpy(&ctx->tmp_write_fds, &ctx->write_fds, sizeof(fd_set));
@@ -123,7 +123,7 @@ void io_loop_handler_run(struct ioloop *
i_warning("select() : %m");
/* execute timeout handlers */
- io_loop_handle_timeouts(ioloop, ret == 0);
+ io_loop_handle_timeouts(ioloop);
if (ret <= 0 || !ioloop->running) {
/* no I/O events */
diff -r 618472c2c3c5 -r becdf2eacdce src/lib/ioloop.c
--- a/src/lib/ioloop.c Thu Jan 03 23:18:46 2008 +0200
+++ b/src/lib/ioloop.c Thu Jan 03 23:19:33 2008 +0200
@@ -86,21 +86,6 @@ void io_remove(struct io **_io)
}
}
-static void timeout_list_insert(struct ioloop *ioloop, struct timeout *timeout)
-{
- struct timeout **t;
- struct timeval *next_run;
-
- next_run = &timeout->next_run;
- for (t = &ioloop->timeouts; *t != NULL; t = &(*t)->next) {
- if (timer_is_larger(&(*t)->next_run, next_run))
- break;
- }
-
- timeout->next = *t;
- *t = timeout;
-}
-
static void timeout_update_next(struct timeout *timeout, struct timeval *tv_now)
{
if (tv_now == NULL) {
@@ -138,27 +123,44 @@ struct timeout *timeout_add(unsigned int
timeout_update_next(timeout, current_ioloop->running ?
NULL : &ioloop_timeval);
- timeout_list_insert(current_ioloop, timeout);
+ priorityq_add(current_ioloop->timeouts, &timeout->item);
return timeout;
}
-void timeout_remove(struct timeout **timeout)
-{
- i_assert(*timeout != NULL);
-
- (*timeout)->destroyed = TRUE;
- *timeout = NULL;
-}
-
-int io_loop_get_wait_time(struct timeout *timeout, struct timeval *tv,
- struct timeval *tv_now)
-{
- if (timeout == NULL) {
- /* no timeouts. give it INT_MAX msecs. */
- tv->tv_sec = INT_MAX / 1000;
- tv->tv_usec = 0;
- return INT_MAX;
- }
+void timeout_remove(struct timeout **_timeout)
+{
+ struct timeout *timeout = *_timeout;
+
+ *_timeout = NULL;
+ priorityq_remove(current_ioloop->timeouts, &timeout->item);
+ i_free(timeout);
+}
+
+static void
+timeout_reset_timeval(struct timeout *timeout, struct timeval *tv_now)
+{
+ timeout_update_next(timeout, tv_now);
+ if (timeout->msecs == 0) {
+ /* if we came here from io_loop_handle_timeouts(),
+ next_run must be larger than tv_now or we could go to
+ infinite loop */
+ if (++timeout->next_run.tv_usec == 0)
+ timeout->next_run.tv_sec++;
+ }
+ priorityq_remove(current_ioloop->timeouts, &timeout->item);
+ priorityq_add(current_ioloop->timeouts, &timeout->item);
+}
+
+void timeout_reset(struct timeout *timeout)
+{
+ timeout_reset_timeval(timeout, current_ioloop->running ? NULL :
+ &ioloop_timeval);
+}
+
+static int timeout_get_wait_time(struct timeout *timeout, struct timeval *tv,
+ struct timeval *tv_now)
+{
+ int ret;
if (tv_now == NULL) {
if (gettimeofday(tv, NULL) < 0)
@@ -175,21 +177,44 @@ int io_loop_get_wait_time(struct timeout
tv->tv_usec += 1000000;
}
- if (tv->tv_sec > 0 || (tv->tv_sec == 0 && tv->tv_usec > 0)) {
- /* round wait times up to next millisecond */
- return tv->tv_sec * 1000 + (tv->tv_usec + 999) / 1000;
- }
-
- /* no need to calculate the times again with this timeout */
- tv->tv_sec = tv->tv_usec = 0;
- timeout->run_now = TRUE;
- return 0;
-}
-
-void io_loop_handle_timeouts(struct ioloop *ioloop, bool update_run_now)
-{
- struct timeout *called_timeouts;
- struct timeval tv;
+ /* round wait times up to next millisecond */
+ ret = tv->tv_sec * 1000 + (tv->tv_usec + 999) / 1000;
+ return ret < 0 ? 0 : ret;
+}
+
+int io_loop_get_wait_time(struct ioloop *ioloop, struct timeval *tv,
+ struct timeval *tv_now)
+{
+ struct priorityq_item *item;
+ struct timeout *timeout;
+
+ item = priorityq_peek(ioloop->timeouts);
+ timeout = (struct timeout *)item;
+ if (timeout == NULL) {
+ /* no timeouts. give it INT_MAX msecs. */
+ tv->tv_sec = INT_MAX / 1000;
+ tv->tv_usec = 0;
+ return INT_MAX;
+ }
+
+ return timeout_get_wait_time(timeout, tv, tv_now);
+}
+
+static int timeout_cmp(const void *p1, const void *p2)
+{
+ const struct timeout *to1 = p1, *to2 = p2;
+ int diff;
+
+ diff = to1->next_run.tv_sec - to2->next_run.tv_sec;
+ if (diff == 0)
+ diff = to1->next_run.tv_usec - to2->next_run.tv_usec;
+ return diff;
+}
+
+static void io_loop_handle_timeouts_real(struct ioloop *ioloop)
+{
+ struct priorityq_item *item;
+ struct timeval tv, tv_call;
unsigned int t_id;
if (gettimeofday(&ioloop_timeval, &ioloop_timezone) < 0)
@@ -227,72 +252,37 @@ void io_loop_handle_timeouts(struct iolo
}
/* Try again. */
- io_loop_handle_timeouts(ioloop, TRUE);
+ io_loop_handle_timeouts(ioloop);
}
}
-
ioloop_time = ioloop_timeval.tv_sec;
-
- if (ioloop->timeouts == NULL ||
- (!ioloop->timeouts->run_now && !update_run_now))
- return;
-
- called_timeouts = NULL;
- while (ioloop->timeouts != NULL) {
- struct timeout *t = ioloop->timeouts;
-
- if (t->destroyed) {
- ioloop->timeouts = t->next;
- i_free(t);
- continue;
More information about the dovecot-cvs
mailing list