Convert the rde_peer hash table to an RB tree. This is a bit more complex
because rde_peer list is used in a lot of places. As a bonus use
peer_foreach in mrt.c to write the table v2 peer header (this needs a
special callback struct because two values need to be passed to the
callback).
The rest of the code is mostly a simple conversion. Only peer_match
required to be adjusted because the code is now able to use peer_get()
to find the start point.
--
:wq Claudio
Index: mrt.c
===================================================================
RCS file: /cvs/src/usr.sbin/bgpd/mrt.c,v
retrieving revision 1.109
diff -u -p -r1.109 mrt.c
--- mrt.c 17 Aug 2022 15:15:26 -0000 1.109
+++ mrt.c 1 Sep 2022 00:25:24 -0000
@@ -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
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);
Index: rde.c
===================================================================
RCS file: /cvs/src/usr.sbin/bgpd/rde.c,v
retrieving revision 1.573
diff -u -p -r1.573 rde.c
--- rde.c 31 Aug 2022 15:51:44 -0000 1.573
+++ rde.c 1 Sep 2022 08:29:31 -0000
@@ -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
}
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, uint
}
}
- LIST_FOREACH(peer, &peerlist, peer_l) {
+ RB_FOREACH(peer, peer_tree, &peertable) {
uint8_t aid;
if (peer->reconf_out) {
Index: rde.h
===================================================================
RCS file: /cvs/src/usr.sbin/bgpd/rde.h,v
retrieving revision 1.268
diff -u -p -r1.268 rde.h
--- rde.h 31 Aug 2022 14:29:36 -0000 1.268
+++ rde.h 1 Sep 2022 08:16:31 -0000
@@ -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;
@@ -375,8 +373,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 */
@@ -404,7 +401,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 @@ void peer_imsg_push(struct rde_peer *,
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 *,
Index: rde_peer.c
===================================================================
RCS file: /cvs/src/usr.sbin/bgpd/rde_peer.c,v
retrieving revision 1.22
diff -u -p -r1.22 rde_peer.c
--- rde_peer.c 26 Aug 2022 14:10:52 -0000 1.22
+++ rde_peer.c 1 Sep 2022 09:44:57 -0000
@@ -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 *p
}
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
{
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
struct rde_peer *
peer_get(uint32_t id)
{
- struct rde_peer_head *head;
- struct rde_peer *peer;
+ struct rde_peer needle;
- head = PEER_HASH(id);
-
- 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, uint3
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
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, st
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 *b
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);
}
