Switch the peer TAILQ to a RB tree indexed by the peer id. This way

getpeerbyid() gets a lot quicker at finding the peer when many peers
are configured. In my test case the difference is around 20% runtime.
OK denis@

8 files changed, 79 insertions, 62 deletions

diff --git a/usr.sbin/bgpd/bgpd.c b/usr.sbin/bgpd/bgpd.c
index e61981a156d..be8bec14fc4 100644
--- a/usr.sbin/bgpd/bgpd.c
+++ b/usr.sbin/bgpd/bgpd.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: bgpd.c,v 1.217 2019/05/08 18:48:34 claudio Exp $ */
+/*	$OpenBSD: bgpd.c,v 1.218 2019/05/27 09:14:32 claudio Exp $ */
 
 /*
  * Copyright (c) 2003, 2004 Henning Brauer <henning@openbsd.org>
@@ -367,7 +367,7 @@ BROKEN	if (pledge("stdio rpath wpath cpath fattr unix route recvfd sendfd",
 	kr_shutdown(conf->fib_priority, conf->default_tableid);
 	pftable_clear_all();
 
-	TAILQ_FOREACH(p, &conf->peers, entry)
+	RB_FOREACH(p, peer_head, &conf->peers)
 		pfkey_remove(p);
 
 	while ((rr = SIMPLEQ_FIRST(&ribnames)) != NULL) {
@@ -532,7 +532,7 @@ reconfigure(char *conffile, struct bgpd_config *conf)
 	}
 
 	/* send peer list to the SE */
-	TAILQ_FOREACH(p, &conf->peers, entry) {
+	RB_FOREACH(p, peer_head, &conf->peers) {
 		if (imsg_compose(ibuf_se, IMSG_RECONF_PEER, p->conf.id, 0, -1,
 		    &p->conf, sizeof(p->conf)) == -1)
 			return (-1);
diff --git a/usr.sbin/bgpd/bgpd.h b/usr.sbin/bgpd/bgpd.h
index 2265de0390c..6c579370ae4 100644
--- a/usr.sbin/bgpd/bgpd.h
+++ b/usr.sbin/bgpd/bgpd.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: bgpd.h,v 1.383 2019/05/23 14:10:05 claudio Exp $ */
+/*	$OpenBSD: bgpd.h,v 1.384 2019/05/27 09:14:32 claudio Exp $ */
 
 /*
  * Copyright (c) 2003, 2004 Henning Brauer <henning@openbsd.org>
@@ -233,7 +233,7 @@ TAILQ_HEAD(listen_addrs, listen_addr);
 TAILQ_HEAD(filter_set_head, filter_set);
 
 struct peer;
-TAILQ_HEAD(peer_head, peer);
+RB_HEAD(peer_head, peer);
 
 struct l3vpn;
 SIMPLEQ_HEAD(l3vpn_head, l3vpn);
diff --git a/usr.sbin/bgpd/config.c b/usr.sbin/bgpd/config.c
index 57d6aa158e4..845c0b59017 100644
--- a/usr.sbin/bgpd/config.c
+++ b/usr.sbin/bgpd/config.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: config.c,v 1.88 2019/05/08 12:41:55 claudio Exp $ */
+/*	$OpenBSD: config.c,v 1.89 2019/05/27 09:14:32 claudio Exp $ */
 
 /*
  * Copyright (c) 2003, 2004, 2005 Henning Brauer <henning@openbsd.org>
@@ -54,7 +54,7 @@ new_config(void)
 		fatal(NULL);
 
 	/* init the various list for later */
-	TAILQ_INIT(&conf->peers);
+	RB_INIT(&conf->peers);
 	TAILQ_INIT(&conf->networks);
 	SIMPLEQ_INIT(&conf->l3vpns);
 	SIMPLEQ_INIT(&conf->prefixsets);
@@ -157,7 +157,7 @@ free_prefixtree(struct prefixset_tree *p)
 void
 free_config(struct bgpd_config *conf)
 {
-	struct peer		*p;
+	struct peer		*p, *next;
 	struct listen_addr	*la;
 	struct mrt		*m;
 
@@ -183,8 +183,8 @@ free_config(struct bgpd_config *conf)
 	}
 	free(conf->mrt);
 
-	while ((p = TAILQ_FIRST(&conf->peers)) != NULL) {
-		TAILQ_REMOVE(&conf->peers, p, entry);
+	RB_FOREACH_SAFE(p, peer_head, &conf->peers, next) {
+		RB_REMOVE(peer_head, &conf->peers, p);
 		free(p);
 	}
 
@@ -199,7 +199,7 @@ merge_config(struct bgpd_config *xconf, struct bgpd_config *conf)
 {
 	struct listen_addr	*nla, *ola, *next;
 	struct network		*n;
-	struct peer		*p, *np;
+	struct peer		*p, *np, *nextp;
 
 	/*
 	 * merge the freshly parsed conf into the running xconf
@@ -314,9 +314,9 @@ merge_config(struct bgpd_config *xconf, struct bgpd_config *conf)
 	 *   peer if so mark it RECONF_KEEP. Remove all old peers.
 	 * - swap lists (old peer list is actually empty).
 	 */
-	TAILQ_FOREACH(p, &conf->peers, entry)
+	RB_FOREACH(p, peer_head, &conf->peers)
 		p->reconf_action = RECONF_REINIT;
-	while ((p = TAILQ_FIRST(&xconf->peers)) != NULL) {
+	RB_FOREACH_SAFE(p, peer_head, &xconf->peers, nextp) {
 		np = getpeerbyid(conf, p->conf.id);
 		if (np != NULL) {
 			np->reconf_action = RECONF_KEEP;
@@ -324,10 +324,14 @@ merge_config(struct bgpd_config *xconf, struct bgpd_config *conf)
 			np->auth = p->auth;
 		}
 
-		TAILQ_REMOVE(&xconf->peers, p, entry);
+		RB_REMOVE(peer_head, &xconf->peers, p);
 		free(p);
 	}
-	TAILQ_CONCAT(&xconf->peers, &conf->peers, entry);
+	RB_FOREACH_SAFE(np, peer_head, &conf->peers, nextp) {
+		RB_REMOVE(peer_head, &conf->peers, np);
+		if (RB_INSERT(peer_head, &xconf->peers, np) != NULL)
+			fatalx("%s: peer tree is corrupt", __func__);
+	}
 
 	/* conf is merged so free it */
 	free_config(conf);
diff --git a/usr.sbin/bgpd/control.c b/usr.sbin/bgpd/control.c
index b6684e9bfe4..f3b0f3da2b5 100644
--- a/usr.sbin/bgpd/control.c
+++ b/usr.sbin/bgpd/control.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: control.c,v 1.96 2019/03/31 16:57:38 claudio Exp $ */
+/*	$OpenBSD: control.c,v 1.97 2019/05/27 09:14:32 claudio Exp $ */
 
 /*
  * Copyright (c) 2003, 2004 Henning Brauer <henning@openbsd.org>
@@ -295,7 +295,7 @@ control_dispatch_msg(struct pollfd *pfd, u_int *ctl_cnt,
 			    0, NULL, 0);
 			break;
 		case IMSG_CTL_SHOW_TERSE:
-			TAILQ_FOREACH(p, peers, entry)
+			RB_FOREACH(p, peer_head, peers)
 				imsg_compose(&c->ibuf, IMSG_CTL_SHOW_NEIGHBOR,
 				    0, 0, -1, p, sizeof(struct peer));
 			imsg_compose(&c->ibuf, IMSG_CTL_END, 0, 0, -1, NULL, 0);
@@ -311,7 +311,7 @@ control_dispatch_msg(struct pollfd *pfd, u_int *ctl_cnt,
 				neighbor = NULL;
 			}
 			matched = 0;
-			TAILQ_FOREACH(p, peers, entry) {
+			RB_FOREACH(p, peer_head, peers) {
 				if (!peer_matched(p, neighbor))
 					continue;
 
@@ -339,7 +339,7 @@ control_dispatch_msg(struct pollfd *pfd, u_int *ctl_cnt,
 					}
 				}
 			}
-			if (!matched && TAILQ_EMPTY(peers)) {
+			if (!matched && RB_EMPTY(peers)) {
 				control_result(c, CTL_RES_NOSUCHPEER);
 			} else if (!neighbor || !neighbor->show_timers) {
 				imsg_ctl_rde(IMSG_CTL_END, imsg.hdr.pid,
@@ -365,7 +365,7 @@ control_dispatch_msg(struct pollfd *pfd, u_int *ctl_cnt,
 			neighbor->descr[PEER_DESCR_LEN - 1] = 0;
 
 			matched = 0;
-			TAILQ_FOREACH(p, peers, entry) {
+			RB_FOREACH(p, peer_head, peers) {
 				if (!peer_matched(p, neighbor))
 					continue;
 
@@ -461,10 +461,10 @@ control_dispatch_msg(struct pollfd *pfd, u_int *ctl_cnt,
 			neighbor->descr[PEER_DESCR_LEN - 1] = 0;
 
 			/* check if at least one neighbor exists */
-			TAILQ_FOREACH(p, peers, entry)
+			RB_FOREACH(p, peer_head, peers)
 				if (peer_matched(p, neighbor))
 					break;
-			if (p == NULL && TAILQ_EMPTY(peers)) {
+			if (p == NULL && RB_EMPTY(peers)) {
 				control_result(c, CTL_RES_NOSUCHPEER);
 				break;
 			}
diff --git a/usr.sbin/bgpd/parse.y b/usr.sbin/bgpd/parse.y
index 3447519cd0c..c7321d139c4 100644
--- a/usr.sbin/bgpd/parse.y
+++ b/usr.sbin/bgpd/parse.y
@@ -1,4 +1,4 @@
-/*	$OpenBSD: parse.y,v 1.387 2019/05/03 15:08:47 claudio Exp $ */
+/*	$OpenBSD: parse.y,v 1.388 2019/05/27 09:14:32 claudio Exp $ */
 
 /*
  * Copyright (c) 2002, 2003, 2004 Henning Brauer <henning@openbsd.org>
@@ -1208,7 +1208,8 @@ neighbor	: {	curpeer = new_peer(); }
 
 			if (neighbor_consistent(curpeer) == -1)
 				YYERROR;
-			TAILQ_INSERT_TAIL(new_peers, curpeer, entry);
+			if (RB_INSERT(peer_head, new_peers, curpeer) != NULL)
+				fatalx("%s: peer tree is corrupt", __func__);
 			curpeer = curgroup;
 		}
 		;
@@ -1816,7 +1817,7 @@ filter_peer	: ANY		{
 				fatal(NULL);
 			$$->p.remote_as = $$->p.groupid = $$->p.peerid = 0;
 			$$->next = NULL;
-			TAILQ_FOREACH(p, new_peers, entry)
+			RB_FOREACH(p, peer_head, new_peers)
 				if (!memcmp(&p->conf.remote_addr,
 				    &$1, sizeof(p->conf.remote_addr))) {
 					$$->p.peerid = p->conf.id;
@@ -1843,7 +1844,7 @@ filter_peer	: ANY		{
 				fatal(NULL);
 			$$->p.remote_as = $$->p.peerid = 0;
 			$$->next = NULL;
-			TAILQ_FOREACH(p, new_peers, entry)
+			RB_FOREACH(p, peer_head, new_peers)
 				if (!strcmp(p->conf.group, $2)) {
 					$$->p.groupid = p->conf.groupid;
 					break;
@@ -3965,7 +3966,7 @@ get_id(struct peer *newpeer)
 	if (newpeer->conf.remote_addr.aid) {
 		/* neighbor */
 		if (cur_peers)
-			TAILQ_FOREACH(p, cur_peers, entry)
+			RB_FOREACH(p, peer_head, cur_peers)
 				if (memcmp(&p->conf.remote_addr,
 				    &newpeer->conf.remote_addr,
 				    sizeof(p->conf.remote_addr)) == 0)
@@ -3977,7 +3978,7 @@ get_id(struct peer *newpeer)
 	} else {
 		/* group */
 		if (cur_peers)
-			TAILQ_FOREACH(p, cur_peers, entry)
+			RB_FOREACH(p, peer_head, cur_peers)
 				if (strcmp(p->conf.group,
 				    newpeer->conf.group) == 0)
 					break;
diff --git a/usr.sbin/bgpd/printconf.c b/usr.sbin/bgpd/printconf.c
index 9a4e99d4785..d969b3e8d49 100644
--- a/usr.sbin/bgpd/printconf.c
+++ b/usr.sbin/bgpd/printconf.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: printconf.c,v 1.134 2019/03/31 16:57:38 claudio Exp $	*/
+/*	$OpenBSD: printconf.c,v 1.135 2019/05/27 09:14:32 claudio Exp $	*/
 
 /*
  * Copyright (c) 2003, 2004 Henning Brauer <henning@openbsd.org>
@@ -784,7 +784,7 @@ print_rule(struct bgpd_config *conf, struct filter_rule *r)
 		printf("eeeeeeeps. ");
 
 	if (r->peer.peerid) {
-		TAILQ_FOREACH(p, &conf->peers, entry)
+		RB_FOREACH(p, peer_head, &conf->peers)
 			if (p->conf.id == r->peer.peerid)
 				break;
 		if (p == NULL)
@@ -792,7 +792,7 @@ print_rule(struct bgpd_config *conf, struct filter_rule *r)
 		else
 			printf("%s ", log_addr(&p->conf.remote_addr));
 	} else if (r->peer.groupid) {
-		TAILQ_FOREACH(p, &conf->peers, entry)
+		RB_FOREACH(p, peer_head, &conf->peers)
 			if (p->conf.groupid == r->peer.groupid)
 				break;
 		if (p == NULL)
@@ -939,14 +939,14 @@ print_groups(struct bgpd_config *conf)
 	const char		 *c;
 
 	peer_cnt = 0;
-	TAILQ_FOREACH(p, &conf->peers, entry)
+	RB_FOREACH(p, peer_head, &conf->peers)
 		peer_cnt++;
 
 	if ((peerlist = calloc(peer_cnt, sizeof(struct peer_config *))) == NULL)
 		fatal("print_groups calloc");
 
 	i = 0;
-	TAILQ_FOREACH(p, &conf->peers, entry)
+	RB_FOREACH(p, peer_head, &conf->peers)
 		peerlist[i++] = &p->conf;
 
 	qsort(peerlist, peer_cnt, sizeof(struct peer_config *), peer_compare);
diff --git a/usr.sbin/bgpd/session.c b/usr.sbin/bgpd/session.c
index 921b0b3a84a..e3e64aa31bf 100644
--- a/usr.sbin/bgpd/session.c
+++ b/usr.sbin/bgpd/session.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: session.c,v 1.381 2019/05/24 11:37:52 claudio Exp $ */
+/*	$OpenBSD: session.c,v 1.382 2019/05/27 09:14:33 claudio Exp $ */
 
 /*
  * Copyright (c) 2003, 2004, 2005 Henning Brauer <henning@openbsd.org>
@@ -113,6 +113,14 @@ struct imsgbuf		*ibuf_main;
 struct mrt_head		 mrthead;
 time_t			 pauseaccept;
 
+static inline int
+peer_compare(const struct peer *a, const struct peer *b)
+{
+	return a->conf.id - b->conf.id;
+}
+
+RB_GENERATE(peer_head, peer, entry, peer_compare);
+
 void
 session_sighdlr(int sig)
 {
@@ -241,9 +249,7 @@ session_main(int debug, int verbose)
 	while (session_quit == 0) {
 		/* check for peers to be initialized or deleted */
 		if (!pending_reconf) {
-			for (p = TAILQ_FIRST(&conf->peers); p != NULL;
-			   p = next) {
-				next = TAILQ_NEXT(p, entry);
+			RB_FOREACH_SAFE(p, peer_head, &conf->peers, next) {
 				/* cloned peer that idled out? */
 				if (p->template && (p->state == STATE_IDLE ||
 				    p->state == STATE_ACTIVE) &&
@@ -269,7 +275,7 @@ session_main(int debug, int verbose)
 					p->conf.demote_group[0] = 0;
 					session_stop(p, ERR_CEASE_PEER_UNCONF);
 					log_peer_warnx(&p->conf, "removed");
-					TAILQ_REMOVE(&conf->peers, p, entry);
+					RB_REMOVE(peer_head, &conf->peers, p);
 					timer_remove_all(p);
 					pfkey_remove(p);
 					free(p);
@@ -360,7 +366,7 @@ session_main(int debug, int verbose)
 		timeout = 240;	/* loop every 240s at least */
 
 		now = getmonotime();
-		TAILQ_FOREACH(p, &conf->peers, entry) {
+		RB_FOREACH(p, peer_head, &conf->peers) {
 			time_t	nextaction;
 			struct peer_timer *pt;
 
@@ -504,7 +510,7 @@ session_main(int debug, int verbose)
 			session_dispatch_msg(&pfd[j],
 			    peer_l[j - idx_listeners]);
 
-		TAILQ_FOREACH(p, &conf->peers, entry)
+		RB_FOREACH(p, peer_head, &conf->peers)
 			if (p->rbuf && p->rbuf->wpos)
 				session_process_msg(p);
 
@@ -516,8 +522,8 @@ session_main(int debug, int verbose)
 			control_dispatch_msg(&pfd[j], &ctl_cnt, &conf->peers);
 	}
 
-	while ((p = TAILQ_FIRST(&conf->peers)) != NULL) {
-		TAILQ_REMOVE(&conf->peers, p, entry);
+	RB_FOREACH_SAFE(p, peer_head, &conf->peers, next) {
+		RB_REMOVE(peer_head, &conf->peers, p);
 		strlcpy(p->conf.shutcomm,
 		    "bgpd shutting down",
 		    sizeof(p->conf.shutcomm));
@@ -2560,7 +2566,8 @@ session_dispatch_imsg(struct imsgbuf *ibuf, int idx, u_int *listener_cnt)
 			memcpy(&p->conf, imsg.data, sizeof(struct peer_config));
 			p->state = p->prev_state = STATE_NONE;
 			p->reconf_action = RECONF_REINIT;
-			TAILQ_INSERT_TAIL(&nconf->peers, p, entry);
+			if (RB_INSERT(peer_head, &nconf->peers, p) != NULL)
+				fatalx("%s: peer tree is corrupt", __func__);
 			break;
 		case IMSG_RECONF_LISTENER:
 			if (idx != PFD_PIPE_MAIN)
@@ -2673,7 +2680,7 @@ session_dispatch_imsg(struct imsgbuf *ibuf, int idx, u_int *listener_cnt)
 			kif = imsg.data;
 			depend_ok = kif->depend_state;
 
-			TAILQ_FOREACH(p, &conf->peers, entry)
+			RB_FOREACH(p, peer_head, &conf->peers)
 				if (!strcmp(p->conf.if_depend, kif->ifname)) {
 					if (depend_ok && !p->depend_ok) {
 						p->depend_ok = depend_ok;
@@ -2890,7 +2897,7 @@ getpeerbydesc(struct bgpd_config *c, const char *descr)
 	struct peer	*p, *res = NULL;
 	int		 match = 0;
 
-	TAILQ_FOREACH(p, &c->peers, entry)
+	RB_FOREACH(p, peer_head, &conf->peers)
 		if (!strcmp(p->conf.descr, descr)) {
 			res = p;
 			match++;
@@ -2916,13 +2923,13 @@ getpeerbyip(struct bgpd_config *c, struct sockaddr *ip)
 	sa2addr(ip, &addr, NULL);
 
 	/* we might want a more effective way to find peers by IP */
-	TAILQ_FOREACH(p, &c->peers, entry)
+	RB_FOREACH(p, peer_head, &conf->peers)
 		if (!p->conf.template &&
 		    !memcmp(&addr, &p->conf.remote_addr, sizeof(addr)))
 			return (p);
 
 	/* try template matching */
-	TAILQ_FOREACH(p, &c->peers, entry)
+	RB_FOREACH(p, peer_head, &conf->peers)
 		if (p->conf.template &&
 		    p->conf.remote_addr.aid == addr.aid &&
 		    session_match_mask(p, &addr))
@@ -2936,7 +2943,7 @@ getpeerbyip(struct bgpd_config *c, struct sockaddr *ip)
 			fatal(NULL);
 		memcpy(newpeer, loose, sizeof(struct peer));
 		for (id = UINT_MAX; id > UINT_MAX / 2; id--) {
-			TAILQ_FOREACH(p, &c->peers, entry)
+			RB_FOREACH(p, peer_head, &conf->peers)
 				if (p->conf.id == id)
 					break;
 			if (p == NULL)		/* we found a free id */
@@ -2949,7 +2956,8 @@ getpeerbyip(struct bgpd_config *c, struct sockaddr *ip)
 		newpeer->rbuf = NULL;
 		init_peer(newpeer);
 		bgp_fsm(newpeer, EVNT_START);
-		TAILQ_INSERT_TAIL(&c->peers, newpeer, entry);
+		if (RB_INSERT(peer_head, &c->peers, newpeer) != NULL)
+			fatalx("%s: peer tree is corrupt", __func__);
 		return (newpeer);
 	}
 
@@ -2959,13 +2967,11 @@ getpeerbyip(struct bgpd_config *c, struct sockaddr *ip)
 struct peer *
 getpeerbyid(struct bgpd_config *c, u_int32_t peerid)
 {
-	struct peer *p;
+	static struct peer lookup;
 
-	/* we might want a more effective way to find peers by id */
-	TAILQ_FOREACH(p, &c->peers, entry)
-		if (p->conf.id == peerid)
-			return (p);
-	return (NULL);
+	lookup.conf.id = peerid;
+
+	return RB_FIND(peer_head, &c->peers, &lookup);
 }
 
 int
@@ -3167,9 +3173,9 @@ session_stop(struct peer *peer, u_int8_t subcode)
 void
 merge_peers(struct bgpd_config *c, struct bgpd_config *nc)
 {
-	struct peer *p, *np;
+	struct peer *p, *np, *next;
 
-	TAILQ_FOREACH(p, &c->peers, entry) {
+	RB_FOREACH(p, peer_head, &conf->peers) {
 		/* templates are handled specially */
 		if (p->template != NULL)
 			continue;
@@ -3180,7 +3186,7 @@ merge_peers(struct bgpd_config *c, struct bgpd_config *nc)
 		}
 
 		memcpy(&p->conf, &np->conf, sizeof(p->conf));
-		TAILQ_REMOVE(&nc->peers, np, entry);
+		RB_REMOVE(peer_head, &nc->peers, np);
 		free(np);
 
 		p->reconf_action = RECONF_KEEP;
@@ -3202,7 +3208,7 @@ merge_peers(struct bgpd_config *c, struct bgpd_config *nc)
 		/* apply the config to all clones of a template */
 		if (p->conf.template) {
 			struct peer *xp;
-			TAILQ_FOREACH(xp, &conf->peers, entry) {
+			RB_FOREACH(xp, peer_head, &conf->peers) {
 				if (xp->template != p)
 					continue;
 				session_template_clone(xp, NULL, xp->conf.id,
@@ -3215,5 +3221,9 @@ merge_peers(struct bgpd_config *c, struct bgpd_config *nc)
 	}
 
 	/* pfkeys of new peers already loaded by the parent process */
-	TAILQ_CONCAT(&c->peers, &nc->peers, entry);
+	RB_FOREACH_SAFE(np, peer_head, &nc->peers, next) {
+		RB_REMOVE(peer_head, &nc->peers, np);
+		if (RB_INSERT(peer_head, &conf->peers, np) != NULL)
+			fatalx("%s: peer tree is corrupt", __func__);
+	}
 }
diff --git a/usr.sbin/bgpd/session.h b/usr.sbin/bgpd/session.h
index c9448e132f0..41884e75c58 100644
--- a/usr.sbin/bgpd/session.h
+++ b/usr.sbin/bgpd/session.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: session.h,v 1.138 2019/05/24 11:37:52 claudio Exp $ */
+/*	$OpenBSD: session.h,v 1.139 2019/05/27 09:14:33 claudio Exp $ */
 
 /*
  * Copyright (c) 2003, 2004 Henning Brauer <henning@openbsd.org>
@@ -196,7 +196,7 @@ TAILQ_HEAD(peer_timer_head, peer_timer);
 struct peer {
 	struct peer_config	 conf;
 	struct peer_stats	 stats;
-	TAILQ_ENTRY(peer)	 entry;
+	RB_ENTRY(peer)		 entry;
 	struct {
 		struct capabilities	ann;
 		struct capabilities	peer;
@@ -294,6 +294,8 @@ void	print_config(struct bgpd_config *, struct rib_names *);
 void	 rde_main(int, int);
 
 /* session.c */
+RB_PROTOTYPE(peer_head, peer, entry, peer_compare);
+
 void		 session_main(int, int);
 void		 bgp_fsm(struct peer *, enum session_events);
 int		 session_neighbor_rrefresh(struct peer *p);