From 00ad2e9e1c6cf9e14c76660f2b748247c1f4bd83 Mon Sep 17 00:00:00 2001 From: "/C=EU/ST=EU/CN=Pablo Neira Ayuso/emailAddress=pablo@netfilter.org" Date: Fri, 18 Jan 2008 13:46:30 +0000 Subject: yet another rework of the alarm scheduler --- src/alarm.c | 140 +++++++++++++++++++++++++++++++++++++++++++++++-------- src/run.c | 42 +++++++++++------ src/sync-alarm.c | 4 +- src/sync-ftfw.c | 2 - 4 files changed, 150 insertions(+), 38 deletions(-) (limited to 'src') diff --git a/src/alarm.c b/src/alarm.c index 576839a..13a790e 100644 --- a/src/alarm.c +++ b/src/alarm.c @@ -17,8 +17,14 @@ */ #include "alarm.h" +#include "jhash.h" +#include +#include -static LIST_HEAD(alarm_list); +#define ALARM_HASH_SIZE 2048 + +static struct list_head *alarm_hash; +int alarm_counter; void init_alarm(struct alarm_list *t, void *data, @@ -35,14 +41,15 @@ static void __add_alarm(struct alarm_list *alarm) { struct alarm_list *t; + int i = jhash(alarm, sizeof(alarm), 0) % ALARM_HASH_SIZE; - list_for_each_entry(t, &alarm_list, head) { + list_for_each_entry(t, &alarm_hash[i], head) { if (timercmp(&alarm->tv, &t->tv, <)) { list_add_tail(&alarm->head, &t->head); return; } } - list_add_tail(&alarm->head, &alarm_list); + list_add_tail(&alarm->head, &alarm_hash[i]); } void add_alarm(struct alarm_list *alarm) @@ -52,50 +59,143 @@ void add_alarm(struct alarm_list *alarm) gettimeofday(&tv, NULL); timeradd(&alarm->tv, &tv, &alarm->tv); __add_alarm(alarm); + alarm_counter++; } void del_alarm(struct alarm_list *alarm) { /* don't remove a non-inserted node */ - if (!list_empty(&alarm->head)) + if (!list_empty(&alarm->head)) { list_del_init(&alarm->head); + alarm_counter--; + } } void mod_alarm(struct alarm_list *alarm, unsigned long sc, unsigned long usc) { - list_del(&alarm->head); + struct timeval tv; + set_alarm_expiration(alarm, sc, usc); - add_alarm(alarm); + gettimeofday(&tv, NULL); + timeradd(&alarm->tv, &tv, &alarm->tv); + list_del(&alarm->head); + __add_alarm(alarm); } -int get_next_alarm(struct timeval *tv, struct timeval *next_alarm) +static int +calculate_next_run(struct timeval *cand, + struct timeval *tv, + struct timeval *next_run) { + if (cand->tv_sec != LONG_MAX) { + if (timercmp(cand, tv, >)) + timersub(cand, tv, next_run); + else { + /* loop again inmediately */ + next_run->tv_sec = 0; + next_run->tv_usec = 0; + } + return 1; + } + return 0; +} + +int get_next_alarm_run(struct timeval *next_run) +{ + int i; struct alarm_list *t; + struct timeval tv; + struct timeval cand = { + .tv_sec = LONG_MAX, + .tv_usec = LONG_MAX + }; + + gettimeofday(&tv, NULL); - list_for_each_entry(t, &alarm_list, head) { - timersub(&t->tv, tv, next_alarm); + for (i=0; itv, &cand, <)) { + cand.tv_sec = t->tv.tv_sec; + cand.tv_usec = t->tv.tv_usec; + } + } + } + + return calculate_next_run(&cand, &tv, next_run); +} + +static inline int +tv_compare(struct alarm_list *a, struct timeval *cur, struct timeval *cand) +{ + if (timercmp(&a->tv, cur, >)) { + /* select the next alarm candidate */ + if (timercmp(&a->tv, cand, <)) { + cand->tv_sec = a->tv.tv_sec; + cand->tv_usec = a->tv.tv_usec; + } return 1; } return 0; } -int do_alarm_run(struct timeval *next_alarm) +int do_alarm_run(struct timeval *next_run) { - struct alarm_list *t, *tmp; + int i; + struct alarm_list *t, *next, *prev; struct timeval tv; + struct timeval cand = { + .tv_sec = LONG_MAX, + .tv_usec = LONG_MAX + }; gettimeofday(&tv, NULL); - list_for_each_entry_safe(t, tmp, &alarm_list, head) { - if (timercmp(&t->tv, &tv, >)) { - timersub(&t->tv, &tv, next_alarm); - return 1; + for (i=0; ihead.prev, + struct alarm_list, + head); + + del_alarm(t); + t->function(t, t->data); + + /* Special case: One deleted node is inserted + * again in the same place */ + if (next->head.prev == &prev->head) { + t = list_entry(next->head.prev, + struct alarm_list, + head); + if (tv_compare(t, &tv, &cand)) + break; + } } - - del_alarm(t); - t->function(t, t->data); } - /* check for refreshed alarms to get the next one */ - return get_next_alarm(&tv, next_alarm); + return calculate_next_run(&cand, &tv, next_run); +} + +int init_alarm_hash(void) +{ + int i; + + alarm_hash = malloc(sizeof(struct list_head) * ALARM_HASH_SIZE); + if (alarm_hash == NULL) + return -1; + + for (i=0; ikill(); + destroy_alarm_hash(); unlink(CONFIG(lockfile)); dlog(LOG_NOTICE, "---- shutdown received ----"); close_log(); @@ -102,6 +103,11 @@ init(void) STATE(mode) = &stats_mode; } + if (init_alarm_hash() == -1) { + dlog(LOG_ERR, "can't initialize alarm hash"); + return -1; + } + /* Initialization */ if (STATE(mode)->init() == -1) { dlog(LOG_ERR, "initialization failed"); @@ -152,10 +158,15 @@ init(void) return 0; } -static int __run(struct timeval *next_alarm) +static int __run(struct timeval *next_alarm, int *timeout) { int max, ret; fd_set readfds; + struct timeval *tmp = next_alarm; + + /* No alarms, select must block */ + if (*timeout == 0) + tmp = NULL; FD_ZERO(&readfds); FD_SET(STATE(local), &readfds); @@ -166,7 +177,7 @@ static int __run(struct timeval *next_alarm) if (STATE(mode)->add_fds_to_set) max = MAX(max, STATE(mode)->add_fds_to_set(&readfds)); - ret = select(max+1, &readfds, NULL, NULL, next_alarm); + ret = select(max+1, &readfds, NULL, NULL, tmp); if (ret == -1) { /* interrupted syscall, retry */ if (errno == EINTR) @@ -178,7 +189,7 @@ static int __run(struct timeval *next_alarm) } /* timeout expired, run the alarm list */ - if (ret == 0) + if (tmp != NULL && !timerisset(tmp)) return 1; /* signals are racy */ @@ -224,6 +235,14 @@ static int __run(struct timeval *next_alarm) if (STATE(mode)->run) STATE(mode)->run(&readfds); + /* check if we have introduced any new alarms */ + if (*timeout == 0 && alarm_counter > 0) { + *timeout = 1; + if (!get_next_alarm_run(next_alarm)) + dlog(LOG_ERR, "Bug in alarm?"); + return 0; + } + sigprocmask(SIG_UNBLOCK, &STATE(block), NULL); return 0; @@ -232,21 +251,16 @@ static int __run(struct timeval *next_alarm) void __attribute__((noreturn)) run(void) { - struct timeval next_alarm; - struct timeval *next = &next_alarm; - struct timeval tv; + int timeout; + struct timeval next_alarm; - /* initialization: get the first alarm available */ - gettimeofday(&tv, NULL); - if (!get_next_alarm(&tv, next)) - next = NULL; + /* initialization: get the next alarm available */ + timeout = get_next_alarm_run(&next_alarm); while(1) { - if (__run(next)) { + if (__run(&next_alarm, &timeout)) { sigprocmask(SIG_BLOCK, &STATE(block), NULL); - next = &next_alarm; - if (!do_alarm_run(next)) - next = NULL; /* no next alarms */ + timeout = do_alarm_run(&next_alarm); sigprocmask(SIG_UNBLOCK, &STATE(block), NULL); } } diff --git a/src/sync-alarm.c b/src/sync-alarm.c index 6ee306e..9ab9d96 100644 --- a/src/sync-alarm.c +++ b/src/sync-alarm.c @@ -38,7 +38,7 @@ static void refresher(struct alarm_list *a, void *data) init_alarm(a, u, refresher); set_alarm_expiration(a, random() % CONFIG(refresh) + 1, - random() % 999999 + 1); + ((random() % 5 + 1) * 200000) - 1); add_alarm(a); @@ -54,7 +54,7 @@ static void cache_alarm_add(struct us_conntrack *u, void *data) init_alarm(alarm, u, refresher); set_alarm_expiration(alarm, random() % CONFIG(refresh) + 1, - random() % 999999 + 1); + ((random() % 5 + 1) * 200000) - 1); add_alarm(alarm); } diff --git a/src/sync-ftfw.c b/src/sync-ftfw.c index 94df5f9..004dd21 100644 --- a/src/sync-ftfw.c +++ b/src/sync-ftfw.c @@ -340,8 +340,6 @@ static void ftfw_run(void) u = cache_get_conntrack(STATE_SYNC(internal), cn); tx_list_xmit(&cn->tx_list, u); } - - mod_alarm(&alive_alarm, 1, 0); } struct sync_mode sync_ftfw = { -- cgit v1.2.3