getpeerbyid() is currently walking the peer list to find the right one.
This is rather inefficent once you have more then a handful of peers.
Switch it to a RB tree and save a lot of time:
Before:
% cumulative self self total
time seconds seconds calls ms/call ms/call name
22.0 148.60 148.60 18197532 0.01 0.01 session_update [5]
After:
1.6 515.14 9.13 16887495 0.00 0.00 session_update [11]
Saves around 140sec or 20% of run time.
--
:wq Claudio
Index: bgpd.c
===================================================================
RCS file: /cvs/src/usr.sbin/bgpd/bgpd.c,v
retrieving revision 1.217
diff -u -p -r1.217 bgpd.c
--- bgpd.c 8 May 2019 18:48:34 -0000 1.217
+++ bgpd.c 24 May 2019 16:34:14 -0000
@@ -367,7 +367,7 @@ BROKEN if (pledge("stdio rpath wpath cpa
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_
}
/* 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);
Index: bgpd.h
===================================================================
RCS file: /cvs/src/usr.sbin/bgpd/bgpd.h,v
retrieving revision 1.383
diff -u -p -r1.383 bgpd.h
--- bgpd.h 23 May 2019 14:10:05 -0000 1.383
+++ bgpd.h 24 May 2019 16:30:52 -0000
@@ -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);
Index: config.c
===================================================================
RCS file: /cvs/src/usr.sbin/bgpd/config.c,v
retrieving revision 1.88
diff -u -p -r1.88 config.c
--- config.c 8 May 2019 12:41:55 -0000 1.88
+++ config.c 24 May 2019 17:04:46 -0000
@@ -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 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,
* 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,
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);
Index: control.c
===================================================================
RCS file: /cvs/src/usr.sbin/bgpd/control.c,v
retrieving revision 1.96
diff -u -p -r1.96 control.c
--- control.c 31 Mar 2019 16:57:38 -0000 1.96
+++ control.c 25 May 2019 08:05:35 -0000
@@ -295,7 +295,7 @@ control_dispatch_msg(struct pollfd *pfd,
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,
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,
}
}
}
- 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,
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,
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;
}
Index: parse.y
===================================================================
RCS file: /cvs/src/usr.sbin/bgpd/parse.y,v
retrieving revision 1.387
diff -u -p -r1.387 parse.y
--- parse.y 3 May 2019 15:08:47 -0000 1.387
+++ parse.y 24 May 2019 16:52:36 -0000
@@ -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;
Index: printconf.c
===================================================================
RCS file: /cvs/src/usr.sbin/bgpd/printconf.c,v
retrieving revision 1.134
diff -u -p -r1.134 printconf.c
--- printconf.c 31 Mar 2019 16:57:38 -0000 1.134
+++ printconf.c 25 May 2019 08:06:58 -0000
@@ -784,7 +784,7 @@ print_rule(struct bgpd_config *conf, str
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, str
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);
Index: session.c
===================================================================
RCS file: /cvs/src/usr.sbin/bgpd/session.c,v
retrieving revision 1.381
diff -u -p -r1.381 session.c
--- session.c 24 May 2019 11:37:52 -0000 1.381
+++ session.c 25 May 2019 14:54:24 -0000
@@ -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 *ib
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 *ib
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, con
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, struc
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, struc
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, struc
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, struc
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
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, struc
}
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, struc
/* 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, struc
}
/* 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__);
+ }
}
Index: session.h
===================================================================
RCS file: /cvs/src/usr.sbin/bgpd/session.h,v
retrieving revision 1.138
diff -u -p -r1.138 session.h
--- session.h 24 May 2019 11:37:52 -0000 1.138
+++ session.h 24 May 2019 16:31:11 -0000
@@ -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 *,
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);
