yet another rework of the alarm scheduler

5 files changed, 157 insertions, 39 deletions

diff --git a/include/alarm.h b/include/alarm.h
index 532084a..2f78885 100644
--- a/include/alarm.h
+++ b/include/alarm.h
@@ -5,6 +5,8 @@
 
 #include <sys/time.h>
 
+extern int alarm_counter;
+
 struct alarm_list {
 	struct list_head	head;
 	struct timeval		tv;
@@ -19,6 +21,10 @@ set_alarm_expiration(struct alarm_list *t, long tv_sec, long tv_usec)
 	t->tv.tv_usec = tv_usec;
 }
 
+int init_alarm_hash(void);
+
+void destroy_alarm_hash(void);
+
 void init_alarm(struct alarm_list *t,
 		void *data,
 		void (*fcn)(struct alarm_list *a, void *data));
@@ -29,7 +35,7 @@ void del_alarm(struct alarm_list *alarm);
 
 void mod_alarm(struct alarm_list *alarm, unsigned long sc, unsigned long usc);
 
-int get_next_alarm(struct timeval *tv, struct timeval *next_alarm);
+int get_next_alarm_run(struct timeval *next_alarm);
 
 int do_alarm_run(struct timeval *next_alarm);
 
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 <stdlib.h>
+#include <limits.h>
 
-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; i<ALARM_HASH_SIZE; i++) {
+		if (!list_empty(&alarm_hash[i])) {
+			t = list_entry(alarm_hash[i].next, 
+				       struct alarm_list,
+				       head);
+			if (timercmp(&t->tv, &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; i<ALARM_HASH_SIZE; i++) {
+		list_for_each_entry_safe(t, next, &alarm_hash[i], head) {
+			if (tv_compare(t, &tv, &cand))
+				break;
+
+			/* annotate previous alarm */
+			prev = list_entry(next->head.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; i<ALARM_HASH_SIZE; i++)
+		INIT_LIST_HEAD(&alarm_hash[i]);
+
+	return 0;
+}
+
+void destroy_alarm_hash(void)
+{
+	free(alarm_hash);
 }
diff --git a/src/run.c b/src/run.c
index 6ae8b9d..efeda5a 100644
--- a/src/run.c
+++ b/src/run.c
@@ -42,6 +42,7 @@ void killer(int foo)
 	ignore_pool_destroy(STATE(ignore_pool));
 	local_server_destroy(STATE(local), CONFIG(local).path);
 	STATE(mode)->kill();
+	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 = {