From dcbb4522321f5e10875533da6565e7d12234fe9e Mon Sep 17 00:00:00 2001 From: claudio Date: Thu, 1 Sep 2022 13:23:24 +0000 Subject: [PATCH] Switch the rde_peer hashtable and peer list to a single RB tree. Only the RDE used a hashtable for lookups while the session engine switched from a list to RB tree some time ago. Use peer_foreach() in the mrt code instead of passing the peer list as an argument. OK benno@ tb@ --- usr.sbin/bgpd/mrt.c | 42 +++++++++++----- usr.sbin/bgpd/rde.c | 26 +++++----- usr.sbin/bgpd/rde.h | 15 +++--- usr.sbin/bgpd/rde_peer.c | 102 ++++++++++++++------------------------- 4 files changed, 84 insertions(+), 101 deletions(-) diff --git a/usr.sbin/bgpd/mrt.c b/usr.sbin/bgpd/mrt.c index c34cedf8768..fe104727d72 100644 --- a/usr.sbin/bgpd/mrt.c +++ b/usr.sbin/bgpd/mrt.c @@ -1,4 +1,4 @@ -/* $OpenBSD: mrt.c,v 1.109 2022/08/17 15:15:26 claudio Exp $ */ +/* $OpenBSD: mrt.c,v 1.110 2022/09/01 13:23:24 claudio Exp $ */ /* * Copyright (c) 2003, 2004 Claudio Jeker @@ -783,14 +783,33 @@ fail: return (-1); } +struct cb_arg { + struct ibuf *buf; + int nump; +}; + +static void +mrt_dump_v2_hdr_peer(struct rde_peer *peer, void *arg) +{ + struct cb_arg *a = arg; + + if (a->nump == -1) + return; + peer->mrt_idx = a->nump; + if (mrt_dump_peer(a->buf, peer) == -1) { + a->nump = -1; + return; + } + a->nump++; +} + int -mrt_dump_v2_hdr(struct mrt *mrt, struct bgpd_config *conf, - struct rde_peer_head *ph) +mrt_dump_v2_hdr(struct mrt *mrt, struct bgpd_config *conf) { - struct rde_peer *peer; struct ibuf *buf, *hbuf = NULL; size_t len, off; uint16_t nlen, nump; + struct cb_arg arg; if ((buf = ibuf_dynamic(0, UINT_MAX)) == NULL) { log_warn("%s: ibuf_dynamic", __func__); @@ -812,14 +831,13 @@ mrt_dump_v2_hdr(struct mrt *mrt, struct bgpd_config *conf, log_warn("%s: ibuf_reserve error", __func__); goto fail; } - nump = 0; - LIST_FOREACH(peer, ph, peer_l) { - peer->mrt_idx = nump; - if (mrt_dump_peer(buf, peer) == -1) - goto fail; - nump++; - } - nump = htons(nump); + arg.nump = 0; + arg.buf = buf; + peer_foreach(mrt_dump_v2_hdr_peer, &arg); + if (arg.nump == -1) + goto fail; + + nump = htons(arg.nump); memcpy(ibuf_seek(buf, off, sizeof(nump)), &nump, sizeof(nump)); len = ibuf_size(buf); diff --git a/usr.sbin/bgpd/rde.c b/usr.sbin/bgpd/rde.c index 6aa47b9037d..4cb65f01512 100644 --- a/usr.sbin/bgpd/rde.c +++ b/usr.sbin/bgpd/rde.c @@ -1,4 +1,4 @@ -/* $OpenBSD: rde.c,v 1.573 2022/08/31 15:51:44 claudio Exp $ */ +/* $OpenBSD: rde.c,v 1.574 2022/09/01 13:23:24 claudio Exp $ */ /* * Copyright (c) 2003, 2004 Henning Brauer @@ -114,8 +114,8 @@ struct rde_memstats rdemem; int softreconfig; static int rde_eval_all; -extern struct rde_peer_head peerlist; -extern struct rde_peer *peerself; +extern struct peer_tree peertable; +extern struct rde_peer *peerself; struct rde_dump_ctx { LIST_ENTRY(rde_dump_ctx) entry; @@ -145,8 +145,6 @@ rde_sighdlr(int sig) } } -uint32_t peerhashsize = 1024; - void rde_main(int debug, int verbose) { @@ -194,7 +192,7 @@ rde_main(int debug, int verbose) /* initialize the RIB structures */ pt_init(); - peer_init(peerhashsize); + peer_init(); /* make sure the default RIBs are setup */ rib_new("Adj-RIB-In", 0, F_RIB_NOFIB | F_RIB_NOEVALUATE); @@ -2982,7 +2980,7 @@ rde_dump_mrt_new(struct mrt *mrt, pid_t pid, int fd) } if (ctx->mrt.type == MRT_TABLE_DUMP_V2) - mrt_dump_v2_hdr(&ctx->mrt, conf, &peerlist); + mrt_dump_v2_hdr(&ctx->mrt, conf); if (rib_dump_new(rid, AID_UNSPEC, CTL_MSG_HIGH_MARK, &ctx->mrt, mrt_dump_upcall, rde_mrt_done, rde_mrt_throttled) == -1) @@ -3105,7 +3103,7 @@ rde_update_queue_pending(void) if (ibuf_se && ibuf_se->w.queued >= SESS_MSG_HIGH_MARK) return 0; - LIST_FOREACH(peer, &peerlist, peer_l) { + RB_FOREACH(peer, peer_tree, &peertable) { if (peer->conf.id == 0) continue; if (peer->state != PEER_UP) @@ -3131,7 +3129,7 @@ rde_update_queue_runner(void) len = sizeof(queue_buf) - MSGSIZE_HEADER; do { sent = 0; - LIST_FOREACH(peer, &peerlist, peer_l) { + RB_FOREACH(peer, peer_tree, &peertable) { if (peer->conf.id == 0) continue; if (peer->state != PEER_UP) @@ -3189,7 +3187,7 @@ rde_update6_queue_runner(uint8_t aid) /* first withdraws ... */ do { sent = 0; - LIST_FOREACH(peer, &peerlist, peer_l) { + RB_FOREACH(peer, peer_tree, &peertable) { if (peer->conf.id == 0) continue; if (peer->state != PEER_UP) @@ -3214,7 +3212,7 @@ rde_update6_queue_runner(uint8_t aid) max = RDE_RUNNER_ROUNDS / 2; do { sent = 0; - LIST_FOREACH(peer, &peerlist, peer_l) { + RB_FOREACH(peer, peer_tree, &peertable) { if (peer->conf.id == 0) continue; if (peer->state != PEER_UP) @@ -3447,7 +3445,7 @@ rde_reload_done(void) rde_eval_all = 0; /* check if filter changed */ - LIST_FOREACH(peer, &peerlist, peer_l) { + RB_FOREACH(peer, peer_tree, &peertable) { if (peer->conf.id == 0) /* ignore peerself */ continue; peer->reconf_out = 0; @@ -3533,7 +3531,7 @@ rde_reload_done(void) break; case RECONF_RELOAD: if (rib_update(rib)) { - LIST_FOREACH(peer, &peerlist, peer_l) { + RB_FOREACH(peer, peer_tree, &peertable) { /* ignore peerself */ if (peer->conf.id == 0) continue; @@ -3644,7 +3642,7 @@ rde_softreconfig_in_done(void *arg, uint8_t dummy) } } - LIST_FOREACH(peer, &peerlist, peer_l) { + RB_FOREACH(peer, peer_tree, &peertable) { uint8_t aid; if (peer->reconf_out) { diff --git a/usr.sbin/bgpd/rde.h b/usr.sbin/bgpd/rde.h index 3778d9991a0..ffc327f1bc1 100644 --- a/usr.sbin/bgpd/rde.h +++ b/usr.sbin/bgpd/rde.h @@ -1,4 +1,4 @@ -/* $OpenBSD: rde.h,v 1.269 2022/09/01 13:19:11 claudio Exp $ */ +/* $OpenBSD: rde.h,v 1.270 2022/09/01 13:23:24 claudio Exp $ */ /* * Copyright (c) 2003, 2004 Claudio Jeker and @@ -70,15 +70,13 @@ struct rib { * How do we identify peers between the session handler and the rde? * Currently I assume that we can do that with the neighbor_ip... */ -LIST_HEAD(rde_peer_head, rde_peer); -LIST_HEAD(attr_list, attr); +RB_HEAD(peer_tree, rde_peer); RB_HEAD(prefix_tree, prefix); RB_HEAD(prefix_index, prefix); struct iq; struct rde_peer { - LIST_ENTRY(rde_peer) hash_l; /* hash list over all peers */ - LIST_ENTRY(rde_peer) peer_l; /* list of all peers */ + RB_ENTRY(rde_peer) entry; SIMPLEQ_HEAD(, iq) imsg_queue; struct peer_config conf; struct bgpd_addr remote_addr; @@ -374,8 +372,7 @@ extern struct rde_memstats rdemem; /* prototypes */ /* mrt.c */ -int mrt_dump_v2_hdr(struct mrt *, struct bgpd_config *, - struct rde_peer_head *); +int mrt_dump_v2_hdr(struct mrt *, struct bgpd_config *); void mrt_dump_upcall(struct rib_entry *, void *); /* rde.c */ @@ -403,7 +400,7 @@ int peer_has_as4byte(struct rde_peer *); int peer_has_add_path(struct rde_peer *, uint8_t, int); int peer_has_open_policy(struct rde_peer *, uint8_t *); int peer_accept_no_as_set(struct rde_peer *); -void peer_init(uint32_t); +void peer_init(void); void peer_shutdown(void); void peer_foreach(void (*)(struct rde_peer *, void *), void *); struct rde_peer *peer_get(uint32_t); @@ -422,6 +419,8 @@ int peer_imsg_pop(struct rde_peer *, struct imsg *); int peer_imsg_pending(void); void peer_imsg_flush(struct rde_peer *); +RB_PROTOTYPE(peer_tree, rde_peer, entry, peer_cmp); + /* rde_attr.c */ int attr_write(void *, uint16_t, uint8_t, uint8_t, void *, uint16_t); diff --git a/usr.sbin/bgpd/rde_peer.c b/usr.sbin/bgpd/rde_peer.c index 6df25161b99..7964405495e 100644 --- a/usr.sbin/bgpd/rde_peer.c +++ b/usr.sbin/bgpd/rde_peer.c @@ -1,4 +1,4 @@ -/* $OpenBSD: rde_peer.c,v 1.22 2022/08/26 14:10:52 claudio Exp $ */ +/* $OpenBSD: rde_peer.c,v 1.23 2022/09/01 13:23:24 claudio Exp $ */ /* * Copyright (c) 2019 Claudio Jeker @@ -26,15 +26,7 @@ #include "bgpd.h" #include "rde.h" -struct peer_table { - struct rde_peer_head *peer_hashtbl; - uint32_t peer_hashmask; -} peertable; - -#define PEER_HASH(x) \ - &peertable.peer_hashtbl[(x) & peertable.peer_hashmask] - -struct rde_peer_head peerlist; +struct peer_tree peertable; struct rde_peer *peerself; CTASSERT(sizeof(peerself->recv_eor) * 8 > AID_MAX); @@ -82,22 +74,11 @@ peer_accept_no_as_set(struct rde_peer *peer) } void -peer_init(uint32_t hashsize) +peer_init(void) { struct peer_config pc; - uint32_t hs, i; - - for (hs = 1; hs < hashsize; hs <<= 1) - ; - peertable.peer_hashtbl = calloc(hs, sizeof(struct rde_peer_head)); - if (peertable.peer_hashtbl == NULL) - fatal("peer_init"); - for (i = 0; i < hs; i++) - LIST_INIT(&peertable.peer_hashtbl[i]); - LIST_INIT(&peerlist); - - peertable.peer_hashmask = hs - 1; + RB_INIT(&peertable); memset(&pc, 0, sizeof(pc)); snprintf(pc.descr, sizeof(pc.descr), "LOCAL"); @@ -110,13 +91,8 @@ peer_init(uint32_t hashsize) void peer_shutdown(void) { - uint32_t i; - - for (i = 0; i <= peertable.peer_hashmask; i++) - if (!LIST_EMPTY(&peertable.peer_hashtbl[i])) - log_warnx("peer_free: free non-free table"); - - free(peertable.peer_hashtbl); + if (!RB_EMPTY(&peertable)) + log_warnx("%s: free non-free table", __func__); } /* @@ -127,7 +103,7 @@ peer_foreach(void (*callback)(struct rde_peer *, void *), void *arg) { struct rde_peer *peer, *np; - LIST_FOREACH_SAFE(peer, &peerlist, peer_l, np) + RB_FOREACH_SAFE(peer, peer_tree, &peertable, np) callback(peer, arg); } @@ -137,16 +113,10 @@ peer_foreach(void (*callback)(struct rde_peer *, void *), void *arg) struct rde_peer * peer_get(uint32_t id) { - struct rde_peer_head *head; - struct rde_peer *peer; - - head = PEER_HASH(id); + struct rde_peer needle; - LIST_FOREACH(peer, head, hash_l) { - if (peer->conf.id == id) - return (peer); - } - return (NULL); + needle.conf.id = id; + return RB_FIND(peer_tree, &peertable, &needle); } /* @@ -157,28 +127,18 @@ peer_get(uint32_t id) struct rde_peer * peer_match(struct ctl_neighbor *n, uint32_t peerid) { - struct rde_peer_head *head; struct rde_peer *peer; - uint32_t i = 0; - if (peerid != 0) - i = peerid & peertable.peer_hashmask; + if (peerid != 0) { + peer = peer_get(peerid); + if (peer) + peer = RB_NEXT(peer_tree, &peertable, peer); + } else + peer = RB_MIN(peer_tree, &peertable); - while (i <= peertable.peer_hashmask) { - head = &peertable.peer_hashtbl[i]; - LIST_FOREACH(peer, head, hash_l) { - /* skip peers until peerid is found */ - if (peerid == peer->conf.id) { - peerid = 0; - continue; - } - if (peerid != 0) - continue; - - if (rde_match_peer(peer, n)) - return (peer); - } - i++; + for (; peer != NULL; peer = RB_NEXT(peer_tree, &peertable, peer)) { + if (rde_match_peer(peer, n)) + return (peer); } return (NULL); } @@ -186,7 +146,6 @@ peer_match(struct ctl_neighbor *n, uint32_t peerid) struct rde_peer * peer_add(uint32_t id, struct peer_config *p_conf) { - struct rde_peer_head *head; struct rde_peer *peer; if ((peer = peer_get(id))) { @@ -209,14 +168,24 @@ peer_add(uint32_t id, struct peer_config *p_conf) peer->flags = peer->conf.flags; SIMPLEQ_INIT(&peer->imsg_queue); - head = PEER_HASH(id); - - LIST_INSERT_HEAD(head, peer, hash_l); - LIST_INSERT_HEAD(&peerlist, peer, peer_l); + if (RB_INSERT(peer_tree, &peertable, peer) != NULL) + fatalx("rde peer table corrupted"); return (peer); } +static inline int +peer_cmp(struct rde_peer *a, struct rde_peer *b) +{ + if (a->conf.id > b->conf.id) + return 1; + if (a->conf.id < b->conf.id) + return -1; + return 0; +} + +RB_GENERATE(peer_tree, rde_peer, entry, peer_cmp); + static void peer_generate_update(struct rde_peer *peer, uint16_t rib_id, struct prefix *new, struct prefix *old, enum eval_mode mode) @@ -276,7 +245,7 @@ rde_generate_updates(struct rib *rib, struct prefix *new, struct prefix *old, if (old == NULL && new == NULL) return; - LIST_FOREACH(peer, &peerlist, peer_l) + RB_FOREACH(peer, peer_tree, &peertable) peer_generate_update(peer, rib->id, new, old, mode); } @@ -475,8 +444,7 @@ peer_down(struct rde_peer *peer, void *bula) peer->prefix_cnt = 0; peer->prefix_out_cnt = 0; - LIST_REMOVE(peer, hash_l); - LIST_REMOVE(peer, peer_l); + RB_REMOVE(peer_tree, &peertable, peer); free(peer); } -- 2.20.1