Claudio Jeker([email protected]) on 2022.08.30 19:11:15 +0200:
> I'm on a mission to remove the hash tables :)
>
> This one is for struct nexthop. Hopefully it makes nexthop_get a bit
> better.
ok, but one __func__ below
>
> --
> :wq Claudio
>
> Index: rde.c
> ===================================================================
> RCS file: /cvs/src/usr.sbin/bgpd/rde.c,v
> retrieving revision 1.569
> diff -u -p -r1.569 rde.c
> --- rde.c 29 Aug 2022 18:18:55 -0000 1.569
> +++ rde.c 30 Aug 2022 16:01:11 -0000
> @@ -198,7 +198,6 @@ rde_main(int debug, int verbose)
> /* initialize the RIB structures */
> pt_init();
> attr_init(attrhashsize);
> - nexthop_init(nexthophashsize);
> peer_init(peerhashsize);
>
> /* make sure the default RIBs are setup */
> Index: rde.h
> ===================================================================
> RCS file: /cvs/src/usr.sbin/bgpd/rde.h,v
> retrieving revision 1.266
> diff -u -p -r1.266 rde.h
> --- rde.h 29 Aug 2022 18:18:55 -0000 1.266
> +++ rde.h 30 Aug 2022 16:00:55 -0000
> @@ -238,7 +238,7 @@ enum nexthop_state {
> };
>
> struct nexthop {
> - LIST_ENTRY(nexthop) nexthop_l;
> + RB_ENTRY(nexthop) entry;
> TAILQ_ENTRY(nexthop) runner_l;
> struct prefix_list prefix_h;
> struct prefix *next_prefix;
> @@ -677,7 +677,6 @@ prefix_re(struct prefix *p)
> return (p->entry.list.re);
> }
>
> -void nexthop_init(uint32_t);
> void nexthop_shutdown(void);
> int nexthop_pending(void);
> void nexthop_runner(void);
> Index: rde_rib.c
> ===================================================================
> RCS file: /cvs/src/usr.sbin/bgpd/rde_rib.c,v
> retrieving revision 1.246
> diff -u -p -r1.246 rde_rib.c
> --- rde_rib.c 29 Aug 2022 18:18:55 -0000 1.246
> +++ rde_rib.c 30 Aug 2022 15:58:37 -0000
> @@ -1515,7 +1515,6 @@ prefix_free(struct prefix *p)
> /*
> * nexthop functions
> */
> -struct nexthop_head *nexthop_hash(struct bgpd_addr *);
> struct nexthop *nexthop_lookup(struct bgpd_addr *);
>
> /*
> @@ -1527,56 +1526,28 @@ struct nexthop *nexthop_lookup(struct b
> * may be passed to the external neighbor if the neighbor and the exit
> nexthop
> * reside in the same subnet -- directly connected.
> */
> -struct nexthop_table {
> - LIST_HEAD(nexthop_head, nexthop) *nexthop_hashtbl;
> - uint32_t nexthop_hashmask;
> -} nexthoptable;
>
> -SIPHASH_KEY nexthoptablekey;
> +TAILQ_HEAD(nexthop_queue, nexthop) nexthop_runners =
> + TAILQ_HEAD_INITIALIZER(nexthop_runners);
>
> -TAILQ_HEAD(nexthop_queue, nexthop) nexthop_runners;
> -
> -void
> -nexthop_init(uint32_t hashsize)
> -{
> - uint32_t hs, i;
> -
> - for (hs = 1; hs < hashsize; hs <<= 1)
> - ;
> - nexthoptable.nexthop_hashtbl = calloc(hs, sizeof(struct nexthop_head));
> - if (nexthoptable.nexthop_hashtbl == NULL)
> - fatal("nextop_init");
> -
> - TAILQ_INIT(&nexthop_runners);
> - for (i = 0; i < hs; i++)
> - LIST_INIT(&nexthoptable.nexthop_hashtbl[i]);
> - arc4random_buf(&nexthoptablekey, sizeof(nexthoptablekey));
> -
> - nexthoptable.nexthop_hashmask = hs - 1;
> -}
> +RB_HEAD(nexthop_tree, nexthop) nexthoptable =
> + RB_INITIALIZER(&nexthoptree);
> +RB_GENERATE_STATIC(nexthop_tree, nexthop, entry, nexthop_compare);
>
> void
> nexthop_shutdown(void)
> {
> - uint32_t i;
> struct nexthop *nh, *nnh;
>
> - for (i = 0; i <= nexthoptable.nexthop_hashmask; i++) {
> - for (nh = LIST_FIRST(&nexthoptable.nexthop_hashtbl[i]);
> - nh != NULL; nh = nnh) {
> - nnh = LIST_NEXT(nh, nexthop_l);
> - nh->state = NEXTHOP_UNREACH;
> - nexthop_unref(nh);
> - }
> - if (!LIST_EMPTY(&nexthoptable.nexthop_hashtbl[i])) {
> - nh = LIST_FIRST(&nexthoptable.nexthop_hashtbl[i]);
> - log_warnx("nexthop_shutdown: non-free table, "
> - "nexthop %s refcnt %d",
> - log_addr(&nh->exit_nexthop), nh->refcnt);
> - }
> + RB_FOREACH_SAFE(nh, nexthop_tree, &nexthoptable, nnh) {
> + nh->state = NEXTHOP_UNREACH;
> + nexthop_unref(nh);
> }
>
> - free(nexthoptable.nexthop_hashtbl);
> + RB_FOREACH(nh, nexthop_tree, &nexthoptable) {
> + log_warnx("nexthop_shutdown: nexthop %s refcnt %d",
__func__
> + log_addr(&nh->exit_nexthop), nh->refcnt);
> + }
> }
>
> int
> @@ -1758,8 +1729,8 @@ nexthop_get(struct bgpd_addr *nexthop)
> nh->state = NEXTHOP_LOOKUP;
> nexthop_ref(nh); /* take reference for lookup */
> nh->exit_nexthop = *nexthop;
> - LIST_INSERT_HEAD(nexthop_hash(nexthop), nh,
> - nexthop_l);
> + if (RB_INSERT(nexthop_tree, &nexthoptable, nh) != NULL)
> + fatalx("nexthop tree inconsistency");
>
> rde_send_nexthop(&nh->exit_nexthop, 1);
> }
> @@ -1791,7 +1762,7 @@ nexthop_unref(struct nexthop *nh)
> if (nh->next_prefix)
> fatalx("%s: next_prefix not NULL", __func__);
>
> - LIST_REMOVE(nh, nexthop_l);
> + RB_REMOVE(nexthop_tree, &nexthoptable, nh);
> rde_send_nexthop(&nh->exit_nexthop, 0);
>
> rdemem.nexthop_cnt--;
> @@ -1835,32 +1806,8 @@ nexthop_compare(struct nexthop *na, stru
> struct nexthop *
> nexthop_lookup(struct bgpd_addr *nexthop)
> {
> - struct nexthop *nh;
> -
> - LIST_FOREACH(nh, nexthop_hash(nexthop), nexthop_l) {
> - if (memcmp(&nh->exit_nexthop, nexthop,
> - sizeof(struct bgpd_addr)) == 0)
> - return (nh);
> - }
> - return (NULL);
> -}
> -
> -struct nexthop_head *
> -nexthop_hash(struct bgpd_addr *nexthop)
> -{
> - uint32_t h = 0;
> + struct nexthop needle = { 0 };
>
> - switch (nexthop->aid) {
> - case AID_INET:
> - h = SipHash24(&nexthoptablekey, &nexthop->v4.s_addr,
> - sizeof(nexthop->v4.s_addr));
> - break;
> - case AID_INET6:
> - h = SipHash24(&nexthoptablekey, &nexthop->v6,
> - sizeof(struct in6_addr));
> - break;
> - default:
> - fatalx("nexthop_hash: unsupported AID %d", nexthop->aid);
> - }
> - return (&nexthoptable.nexthop_hashtbl[h &
> nexthoptable.nexthop_hashmask]);
> + needle.exit_nexthop = *nexthop;
> + return RB_FIND(nexthop_tree, &nexthoptable, &needle);
> }
>
