Claudio Jeker(cje...@diehard.n-r-g.com) on 2022.09.01 12:04:03 +0200:
> 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
ok benno@
>
> 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);
> }
>
>
