store relay sessions in SPLAY trees instead of TAILQ lists. this will

be used for faster lookups of sessions based on different criteria.

ok pyr@

8 files changed, 74 insertions, 32 deletions

diff --git a/usr.sbin/hoststated/hoststated.c b/usr.sbin/hoststated/hoststated.c
index c31588dacce..e6c9cddf0fe 100644
--- a/usr.sbin/hoststated/hoststated.c
+++ b/usr.sbin/hoststated/hoststated.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: hoststated.c,v 1.38 2007/07/05 09:42:26 thib Exp $	*/
+/*	$OpenBSD: hoststated.c,v 1.39 2007/09/05 08:48:42 reyk Exp $	*/
 
 /*
  * Copyright (c) 2006 Pierre-Yves Ritschard <pyr@spootnik.org>
@@ -472,8 +472,8 @@ purge_config(struct hoststated *env, u_int8_t what)
 	if (what & PURGE_RELAYS) {
 		while ((rly = TAILQ_FIRST(&env->relays)) != NULL) {
 			TAILQ_REMOVE(&env->relays, rly, entry);
-			while ((sess = TAILQ_FIRST(&rly->sessions)) != NULL) {
-				TAILQ_REMOVE(&rly->sessions, sess, entry);
+			while ((sess = SPLAY_ROOT(&rly->sessions)) != NULL) {
+				SPLAY_REMOVE(session_tree, &rly->sessions, sess);
 				free(sess);
 			}
 			if (rly->bev != NULL)
@@ -744,7 +744,7 @@ session_find(struct hoststated *env, objid_t id)
 	struct session		*con;
 
 	TAILQ_FOREACH(rlay, &env->relays, entry)
-		TAILQ_FOREACH(con, &rlay->sessions, entry)
+		SPLAY_FOREACH(con, session_tree, &rlay->sessions)
 			if (con->id == id)
 				return (con);
 	return (NULL);
diff --git a/usr.sbin/hoststated/hoststated.h b/usr.sbin/hoststated/hoststated.h
index 0af4c6fe502..44b65162d33 100644
--- a/usr.sbin/hoststated/hoststated.h
+++ b/usr.sbin/hoststated/hoststated.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: hoststated.h,v 1.54 2007/09/05 07:32:33 reyk Exp $	*/
+/*	$OpenBSD: hoststated.h,v 1.55 2007/09/05 08:48:42 reyk Exp $	*/
 
 /*
  * Copyright (c) 2006, 2007 Pierre-Yves Ritschard <pyr@spootnik.org>
@@ -402,9 +402,10 @@ struct session {
 	struct evbuffer			*log;
 	void				*relay;
 	struct ctl_natlook		*cnl;
-	TAILQ_ENTRY(session)		 entry;
+
+	SPLAY_ENTRY(session)		 nodes;
 };
-TAILQ_HEAD(sessionlist, session);
+SPLAY_HEAD(session_tree, session);
 
 enum nodeaction {
 	NODE_ACTION_NONE	= 0,
@@ -489,6 +490,9 @@ struct protocol {
 	struct proto_tree	 request_tree;
 	int			 response_nodes;
 	struct proto_tree	 response_tree;
+
+	int			(*cmp)(struct session *, struct session *);
+
 	TAILQ_ENTRY(protocol)	 entry;
 };
 TAILQ_HEAD(protolist, protocol);
@@ -530,7 +534,7 @@ struct relay {
 
 	struct ctl_stats	 stats[RELAY_MAXPROC + 1];
 
-	struct sessionlist	 sessions;
+	struct session_tree	 sessions;
 };
 TAILQ_HEAD(relaylist, relay);
 
@@ -689,8 +693,10 @@ void	 hce_notify_done(struct host *, const char *);
 pid_t	 relay(struct hoststated *, int [2], int [2], int [RELAY_MAXPROC][2],
 	    int [2], int [RELAY_MAXPROC][2]);
 void	 relay_notify_done(struct host *, const char *);
+int	 relay_session_cmp(struct session *, struct session *);
 
 RB_PROTOTYPE(proto_tree, protonode, nodes, relay_proto_cmp);
+SPLAY_PROTOTYPE(session_tree, session, nodes, relay_session_cmp);
 
 /* check_icmp.c */
 void	 icmp_init(struct hoststated *);
diff --git a/usr.sbin/hoststated/parse.y b/usr.sbin/hoststated/parse.y
index 0e7d448fd63..1c7d83d8d0b 100644
--- a/usr.sbin/hoststated/parse.y
+++ b/usr.sbin/hoststated/parse.y
@@ -1,4 +1,4 @@
-/*	$OpenBSD: parse.y,v 1.51 2007/09/04 14:15:05 pyr Exp $	*/
+/*	$OpenBSD: parse.y,v 1.52 2007/09/05 08:48:42 reyk Exp $	*/
 
 /*
  * Copyright (c) 2006 Pierre-Yves Ritschard <pyr@spootnik.org>
@@ -906,7 +906,7 @@ relay		: RELAY STRING	{
 				rlay->conf.proto = conf->proto_default.id;
 			}
 			conf->relaycount++;
-			TAILQ_INIT(&rlay->sessions);
+			SPLAY_INIT(&rlay->sessions);
 			TAILQ_INSERT_HEAD(&conf->relays, rlay, entry);
 		}
 		;
diff --git a/usr.sbin/hoststated/relay.c b/usr.sbin/hoststated/relay.c
index efd7f20e730..d7eb3e9f3c9 100644
--- a/usr.sbin/hoststated/relay.c
+++ b/usr.sbin/hoststated/relay.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: relay.c,v 1.38 2007/09/04 10:58:08 reyk Exp $	*/
+/*	$OpenBSD: relay.c,v 1.39 2007/09/05 08:48:42 reyk Exp $	*/
 
 /*
  * Copyright (c) 2006, 2007 Reyk Floeter <reyk@openbsd.org>
@@ -260,7 +260,7 @@ relay_shutdown(void)
 		if (rlay->conf.flags & F_DISABLE)
 			continue;
 		close(rlay->s);
-		while ((con = TAILQ_FIRST(&rlay->sessions)) != NULL)
+		while ((con = SPLAY_ROOT(&rlay->sessions)) != NULL)
 			relay_close(con, "shutdown");
 	}
 	usleep(200);	/* XXX relay needs to shutdown last */
@@ -467,9 +467,10 @@ relay_statistics(int fd, short events, void *arg)
 		imsg_compose(ibuf_pfe, IMSG_STATISTICS, 0, 0, -1,
 		    &crs, sizeof(crs));
 
-		for (con = TAILQ_FIRST(&rlay->sessions);
+		for (con = SPLAY_ROOT(&rlay->sessions);
 		    con != NULL; con = next_con) {
-			next_con = TAILQ_NEXT(con, entry);
+			next_con = SPLAY_NEXT(session_tree,
+			    &rlay->sessions, con);
 			timersub(&tv_now, &con->tv_last, &tv);
 			if (timercmp(&tv, &rlay->conf.timeout, >=))
 				relay_close(con, "hard timeout");
@@ -1493,7 +1494,7 @@ relay_accept(int fd, short sig, void *arg)
 	bcopy(&ss, &con->in.ss, sizeof(con->in.ss));
 
 	relay_sessions++;
-	TAILQ_INSERT_HEAD(&rlay->sessions, con, entry);
+	SPLAY_INSERT(session_tree, &rlay->sessions, con);
 
 	/* Increment the per-relay session counter */
 	rlay->stats[proc_id].last++;
@@ -1720,7 +1721,7 @@ relay_close(struct session *con, const char *msg)
 	struct relay	*rlay = (struct relay *)con->relay;
 	char		 ibuf[128], obuf[128], *ptr = NULL;
 
-	TAILQ_REMOVE(&rlay->sessions, con, entry);
+	SPLAY_REMOVE(session_tree, &rlay->sessions, con);
 
 	event_del(&con->ev);
 	if (con->in.bev != NULL)
@@ -2359,3 +2360,17 @@ relay_proto_cmp(struct protonode *a, struct protonode *b)
 }
 
 RB_GENERATE(proto_tree, protonode, nodes, relay_proto_cmp);
+
+int
+relay_session_cmp(struct session *a, struct session *b)
+{
+	struct relay	*rlay = (struct relay *)a->relay;
+	struct protocol	*proto = rlay->proto;
+
+	if (proto->cmp != NULL)
+		return ((*proto->cmp)(a, b));
+
+	return ((int)a->id - b->id);
+}
+
+SPLAY_GENERATE(session_tree, session, nodes, relay_session_cmp);
diff --git a/usr.sbin/relayd/parse.y b/usr.sbin/relayd/parse.y
index 0e7d448fd63..1c7d83d8d0b 100644
--- a/usr.sbin/relayd/parse.y
+++ b/usr.sbin/relayd/parse.y
@@ -1,4 +1,4 @@
-/*	$OpenBSD: parse.y,v 1.51 2007/09/04 14:15:05 pyr Exp $	*/
+/*	$OpenBSD: parse.y,v 1.52 2007/09/05 08:48:42 reyk Exp $	*/
 
 /*
  * Copyright (c) 2006 Pierre-Yves Ritschard <pyr@spootnik.org>
@@ -906,7 +906,7 @@ relay		: RELAY STRING	{
 				rlay->conf.proto = conf->proto_default.id;
 			}
 			conf->relaycount++;
-			TAILQ_INIT(&rlay->sessions);
+			SPLAY_INIT(&rlay->sessions);
 			TAILQ_INSERT_HEAD(&conf->relays, rlay, entry);
 		}
 		;
diff --git a/usr.sbin/relayd/relay.c b/usr.sbin/relayd/relay.c
index efd7f20e730..d7eb3e9f3c9 100644
--- a/usr.sbin/relayd/relay.c
+++ b/usr.sbin/relayd/relay.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: relay.c,v 1.38 2007/09/04 10:58:08 reyk Exp $	*/
+/*	$OpenBSD: relay.c,v 1.39 2007/09/05 08:48:42 reyk Exp $	*/
 
 /*
  * Copyright (c) 2006, 2007 Reyk Floeter <reyk@openbsd.org>
@@ -260,7 +260,7 @@ relay_shutdown(void)
 		if (rlay->conf.flags & F_DISABLE)
 			continue;
 		close(rlay->s);
-		while ((con = TAILQ_FIRST(&rlay->sessions)) != NULL)
+		while ((con = SPLAY_ROOT(&rlay->sessions)) != NULL)
 			relay_close(con, "shutdown");
 	}
 	usleep(200);	/* XXX relay needs to shutdown last */
@@ -467,9 +467,10 @@ relay_statistics(int fd, short events, void *arg)
 		imsg_compose(ibuf_pfe, IMSG_STATISTICS, 0, 0, -1,
 		    &crs, sizeof(crs));
 
-		for (con = TAILQ_FIRST(&rlay->sessions);
+		for (con = SPLAY_ROOT(&rlay->sessions);
 		    con != NULL; con = next_con) {
-			next_con = TAILQ_NEXT(con, entry);
+			next_con = SPLAY_NEXT(session_tree,
+			    &rlay->sessions, con);
 			timersub(&tv_now, &con->tv_last, &tv);
 			if (timercmp(&tv, &rlay->conf.timeout, >=))
 				relay_close(con, "hard timeout");
@@ -1493,7 +1494,7 @@ relay_accept(int fd, short sig, void *arg)
 	bcopy(&ss, &con->in.ss, sizeof(con->in.ss));
 
 	relay_sessions++;
-	TAILQ_INSERT_HEAD(&rlay->sessions, con, entry);
+	SPLAY_INSERT(session_tree, &rlay->sessions, con);
 
 	/* Increment the per-relay session counter */
 	rlay->stats[proc_id].last++;
@@ -1720,7 +1721,7 @@ relay_close(struct session *con, const char *msg)
 	struct relay	*rlay = (struct relay *)con->relay;
 	char		 ibuf[128], obuf[128], *ptr = NULL;
 
-	TAILQ_REMOVE(&rlay->sessions, con, entry);
+	SPLAY_REMOVE(session_tree, &rlay->sessions, con);
 
 	event_del(&con->ev);
 	if (con->in.bev != NULL)
@@ -2359,3 +2360,17 @@ relay_proto_cmp(struct protonode *a, struct protonode *b)
 }
 
 RB_GENERATE(proto_tree, protonode, nodes, relay_proto_cmp);
+
+int
+relay_session_cmp(struct session *a, struct session *b)
+{
+	struct relay	*rlay = (struct relay *)a->relay;
+	struct protocol	*proto = rlay->proto;
+
+	if (proto->cmp != NULL)
+		return ((*proto->cmp)(a, b));
+
+	return ((int)a->id - b->id);
+}
+
+SPLAY_GENERATE(session_tree, session, nodes, relay_session_cmp);
diff --git a/usr.sbin/relayd/relayd.c b/usr.sbin/relayd/relayd.c
index 2de941c0367..22a72cf18c1 100644
--- a/usr.sbin/relayd/relayd.c
+++ b/usr.sbin/relayd/relayd.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: relayd.c,v 1.38 2007/07/05 09:42:26 thib Exp $	*/
+/*	$OpenBSD: relayd.c,v 1.39 2007/09/05 08:48:42 reyk Exp $	*/
 
 /*
  * Copyright (c) 2006 Pierre-Yves Ritschard <pyr@spootnik.org>
@@ -472,8 +472,8 @@ purge_config(struct hoststated *env, u_int8_t what)
 	if (what & PURGE_RELAYS) {
 		while ((rly = TAILQ_FIRST(&env->relays)) != NULL) {
 			TAILQ_REMOVE(&env->relays, rly, entry);
-			while ((sess = TAILQ_FIRST(&rly->sessions)) != NULL) {
-				TAILQ_REMOVE(&rly->sessions, sess, entry);
+			while ((sess = SPLAY_ROOT(&rly->sessions)) != NULL) {
+				SPLAY_REMOVE(session_tree, &rly->sessions, sess);
 				free(sess);
 			}
 			if (rly->bev != NULL)
@@ -744,7 +744,7 @@ session_find(struct hoststated *env, objid_t id)
 	struct session		*con;
 
 	TAILQ_FOREACH(rlay, &env->relays, entry)
-		TAILQ_FOREACH(con, &rlay->sessions, entry)
+		SPLAY_FOREACH(con, session_tree, &rlay->sessions)
 			if (con->id == id)
 				return (con);
 	return (NULL);
diff --git a/usr.sbin/relayd/relayd.h b/usr.sbin/relayd/relayd.h
index 194a63f6757..da4435b8b90 100644
--- a/usr.sbin/relayd/relayd.h
+++ b/usr.sbin/relayd/relayd.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: relayd.h,v 1.54 2007/09/05 07:32:33 reyk Exp $	*/
+/*	$OpenBSD: relayd.h,v 1.55 2007/09/05 08:48:42 reyk Exp $	*/
 
 /*
  * Copyright (c) 2006, 2007 Pierre-Yves Ritschard <pyr@spootnik.org>
@@ -402,9 +402,10 @@ struct session {
 	struct evbuffer			*log;
 	void				*relay;
 	struct ctl_natlook		*cnl;
-	TAILQ_ENTRY(session)		 entry;
+
+	SPLAY_ENTRY(session)		 nodes;
 };
-TAILQ_HEAD(sessionlist, session);
+SPLAY_HEAD(session_tree, session);
 
 enum nodeaction {
 	NODE_ACTION_NONE	= 0,
@@ -489,6 +490,9 @@ struct protocol {
 	struct proto_tree	 request_tree;
 	int			 response_nodes;
 	struct proto_tree	 response_tree;
+
+	int			(*cmp)(struct session *, struct session *);
+
 	TAILQ_ENTRY(protocol)	 entry;
 };
 TAILQ_HEAD(protolist, protocol);
@@ -530,7 +534,7 @@ struct relay {
 
 	struct ctl_stats	 stats[RELAY_MAXPROC + 1];
 
-	struct sessionlist	 sessions;
+	struct session_tree	 sessions;
 };
 TAILQ_HEAD(relaylist, relay);
 
@@ -689,8 +693,10 @@ void	 hce_notify_done(struct host *, const char *);
 pid_t	 relay(struct hoststated *, int [2], int [2], int [RELAY_MAXPROC][2],
 	    int [2], int [RELAY_MAXPROC][2]);
 void	 relay_notify_done(struct host *, const char *);
+int	 relay_session_cmp(struct session *, struct session *);
 
 RB_PROTOTYPE(proto_tree, protonode, nodes, relay_proto_cmp);
+SPLAY_PROTOTYPE(session_tree, session, nodes, relay_session_cmp);
 
 /* check_icmp.c */
 void	 icmp_init(struct hoststated *);