change timer internals so that we use a timewheel (tailq, sorted by expiry

so that the timer that will expire first is always the first element,
and so on). will make the checking a bit faster and moreelegant and more
conveniant. ok claudio

3 files changed, 91 insertions, 52 deletions

diff --git a/usr.sbin/bgpd/session.c b/usr.sbin/bgpd/session.c
index 484640c07cd..729afaf1a8f 100644
--- a/usr.sbin/bgpd/session.c
+++ b/usr.sbin/bgpd/session.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: session.c,v 1.279 2007/12/23 18:56:17 henning Exp $ */
+/*	$OpenBSD: session.c,v 1.280 2008/05/08 06:52:13 henning Exp $ */
 
 /*
  * Copyright (c) 2003, 2004, 2005 Henning Brauer <henning@openbsd.org>
@@ -317,6 +317,7 @@ session_main(struct bgpd_config *config, struct peer *cpeers,
 						last->next = next;
 					else
 						peers = next;
+					timer_remove_all(p);
 					free(p);
 					peer_cnt--;
 					continue;
@@ -586,6 +587,7 @@ init_conf(struct bgpd_config *c)
 void
 init_peer(struct peer *p)
 {
+	TAILQ_INIT(&p->timers);
 	p->fd = p->wbuf.fd = -1;
 
 	if (p->conf.if_depend[0])
diff --git a/usr.sbin/bgpd/session.h b/usr.sbin/bgpd/session.h
index ca143f3706e..25bada9c5b3 100644
--- a/usr.sbin/bgpd/session.h
+++ b/usr.sbin/bgpd/session.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: session.h,v 1.95 2007/12/23 18:56:17 henning Exp $ */
+/*	$OpenBSD: session.h,v 1.96 2008/05/08 06:52:13 henning Exp $ */
 
 /*
  * Copyright (c) 2003, 2004 Henning Brauer <henning@openbsd.org>
@@ -164,6 +164,24 @@ struct peer_stats {
 	u_int8_t		 last_sent_suberr;
 };
 
+enum Timer {
+	Timer_None,
+	Timer_ConnectRetry,
+	Timer_Keepalive,
+	Timer_Hold,
+	Timer_IdleHold,
+	Timer_IdleHoldReset,
+	Timer_Max
+};
+
+struct peer_timer {
+	TAILQ_ENTRY(peer_timer)	entry;
+	enum Timer		type;
+	time_t			val;
+};
+
+TAILQ_HEAD(peer_timer_head, peer_timer);
+
 struct peer {
 	struct peer_config	 conf;
 	struct peer_stats	 stats;
@@ -180,14 +198,10 @@ struct peer {
 	} auth;
 	struct sockaddr_storage	 sa_local;
 	struct sockaddr_storage	 sa_remote;
+	struct peer_timer_head	 timers;
 	struct msgbuf		 wbuf;
 	struct buf_read		*rbuf;
 	struct peer		*next;
-	time_t			 ConnectRetryTimer;
-	time_t			 KeepaliveTimer;
-	time_t			 HoldTimer;
-	time_t			 IdleHoldTimer;
-	time_t			 IdleHoldResetTimer;
 	int			 fd;
 	int			 lasterr;
 	u_int			 errcnt;
@@ -204,16 +218,6 @@ struct peer {
 
 struct peer	*peers;
 
-enum Timer {
-	Timer_None,
-	Timer_ConnectRetry,
-	Timer_Keepalive,
-	Timer_Hold,
-	Timer_IdleHold,
-	Timer_IdleHoldReset,
-	Timer_Max
-};
-
 struct ctl_timer {
 	enum Timer	type;
 	time_t		val;
@@ -276,9 +280,11 @@ int	 carp_demote_get(char *);
 int	 carp_demote_set(char *, int);
 
 /* timer.c */
-time_t		*timer_get(struct peer *, enum Timer);
-int		 timer_due(struct peer *, enum Timer);
-time_t		 timer_nextduein(struct peer *);
-int		 timer_running(struct peer *, enum Timer, time_t *);
-void		 timer_set(struct peer *, enum Timer, u_int);
-void		 timer_stop(struct peer *, enum Timer);
+struct peer_timer	*timer_get(struct peer *, enum Timer);
+int			 timer_due(struct peer *, enum Timer);
+time_t			 timer_nextduein(struct peer *);
+int			 timer_running(struct peer *, enum Timer, time_t *);
+void			 timer_set(struct peer *, enum Timer, u_int);
+void			 timer_stop(struct peer *, enum Timer);
+void			 timer_remove(struct peer *, enum Timer);
+void			 timer_remove_all(struct peer *);
diff --git a/usr.sbin/bgpd/timer.c b/usr.sbin/bgpd/timer.c
index a924a5d4339..74093c62864 100644
--- a/usr.sbin/bgpd/timer.c
+++ b/usr.sbin/bgpd/timer.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: timer.c,v 1.4 2007/12/23 18:56:17 henning Exp $ */
+/*	$OpenBSD: timer.c,v 1.5 2008/05/08 06:52:13 henning Exp $ */
 
 /*
  * Copyright (c) 2003-2007 Henning Brauer <henning@openbsd.org>
@@ -18,39 +18,29 @@
 
 #include <sys/param.h>
 #include <sys/types.h>
+#include <stdlib.h>
 
 #include "bgpd.h"
 #include "session.h"
 
-time_t *
+struct peer_timer *
 timer_get(struct peer *p, enum Timer timer)
 {
-	switch (timer) {
-	case Timer_None:
-		fatal("timer_get called with Timer_None");
-	case Timer_ConnectRetry:
-		return (&p->ConnectRetryTimer);
-	case Timer_Keepalive:
-		return (&p->KeepaliveTimer);
-	case Timer_Hold:
-		return (&p->HoldTimer);
-	case Timer_IdleHold:
-		return (&p->IdleHoldTimer);
-	case Timer_IdleHoldReset:
-		return (&p->IdleHoldResetTimer);
-	case Timer_Max:
-		fatal("timer_get called with Timer_Max");
-	}
+	struct peer_timer *pt;
+
+	TAILQ_FOREACH(pt, &p->timers, entry)
+		if (pt->type == timer)
+				break;
 
-	fatal("King Bula lost in time");
+	return (pt);
 }
 
 int
 timer_due(struct peer *p, enum Timer timer)
 {
-	time_t	*t = timer_get(p, timer);
+	struct peer_timer	*pt = timer_get(p, timer);
 
-	if (t != NULL && *t > 0 && *t <= time(NULL))
+	if (pt != NULL && pt->val > 0 && pt->val <= time(NULL))
 		return (1);
 	return (0);
 }
@@ -72,11 +62,11 @@ timer_nextduein(struct peer *p)
 int
 timer_running(struct peer *p, enum Timer timer, time_t *left)
 {
-	time_t	*t = timer_get(p, timer);
+	struct peer_timer	*pt = timer_get(p, timer);
 
-	if (t != NULL && *t > 0) {
+	if (pt != NULL && pt->val > 0) {
 		if (left != NULL)
-			*left = *t - time(NULL);
+			*left = pt->val - time(NULL);
 		return (1);
 	}
 	return (0);
@@ -85,16 +75,57 @@ timer_running(struct peer *p, enum Timer timer, time_t *left)
 void
 timer_set(struct peer *p, enum Timer timer, u_int offset)
 {
-	time_t	*t = timer_get(p, timer);
+	struct peer_timer	*t, *pt = timer_get(p, timer);
+
+	if (pt == NULL) {	/* have to create */
+		if ((pt = malloc(sizeof(*pt))) == NULL)
+			fatal("timer_set");
+		pt->type = timer;
+	} else {
+		TAILQ_REMOVE(&p->timers, pt, entry);
+	}
 
-	*t = time(NULL) + offset;
+	pt->val = time(NULL) + offset;
+
+	TAILQ_FOREACH(t, &p->timers, entry)
+		if (t->val > pt->val)
+			break;
+	if (t != NULL)
+		TAILQ_INSERT_BEFORE(t, pt, entry);
+	else
+		TAILQ_INSERT_TAIL(&p->timers, pt, entry);
 }
 
 void
 timer_stop(struct peer *p, enum Timer timer)
 {
-	time_t	*t = timer_get(p, timer);
+	struct peer_timer	*pt = timer_get(p, timer);
 
-	if (t != NULL)
-		*t = 0;
+	if (pt != NULL) {
+		pt->val = 0;
+		TAILQ_REMOVE(&p->timers, pt, entry);
+		TAILQ_INSERT_TAIL(&p->timers, pt, entry);
+	}
+}
+
+void
+timer_remove(struct peer *p, enum Timer timer)
+{
+	struct peer_timer	*pt = timer_get(p, timer);
+
+	if (pt != NULL) {
+		TAILQ_REMOVE(&p->timers, pt, entry);
+		free (pt);
+	}
+}
+
+void
+timer_remove_all(struct peer *p)
+{
+	struct peer_timer	*pt;
+
+	while ((pt = TAILQ_FIRST(&p->timers)) != NULL) {
+		TAILQ_REMOVE(&p->timers, pt, entry);
+		free(pt);
+	}
 }