Claudio Jeker([email protected]) on 2022.08.31 13:56:18 +0200:
> Like all other hash tables use an RB tree instead.
> Again the calculation of the hash can be skipped because the compare
> function is probably fast enough.
that sentence does parse, but i am semantically challenged by it.
diff is ok :)
>
> --
> :wq Claudio
>
> ? ktrace.out
> ? obj
> Index: rde.c
> ===================================================================
> RCS file: /cvs/src/usr.sbin/bgpd/rde.c,v
> retrieving revision 1.571
> diff -u -p -r1.571 rde.c
> --- rde.c 31 Aug 2022 11:25:36 -0000 1.571
> +++ rde.c 31 Aug 2022 11:27:54 -0000
> @@ -197,7 +197,6 @@ rde_main(int debug, int verbose)
>
> /* initialize the RIB structures */
> pt_init();
> - attr_init(attrhashsize);
> peer_init(peerhashsize);
>
> /* make sure the default RIBs are setup */
> @@ -360,7 +359,6 @@ rde_dispatch_imsg_session(struct imsgbuf
> struct session_up sup;
> struct rde_peer *peer;
> struct rde_aspath *asp;
> - struct rde_hashstats rdehash;
> struct filter_set *s;
> struct as_set *aset;
> struct rde_prefixset *pset;
> @@ -628,9 +626,6 @@ badnetdel:
> case IMSG_CTL_SHOW_RIB_MEM:
> imsg_compose(ibuf_se_ctl, IMSG_CTL_SHOW_RIB_MEM, 0,
> imsg.hdr.pid, -1, &rdemem, sizeof(rdemem));
> - attr_hash_stats(&rdehash);
> - imsg_compose(ibuf_se_ctl, IMSG_CTL_SHOW_RIB_HASH, 0,
> - imsg.hdr.pid, -1, &rdehash, sizeof(rdehash));
> imsg_compose(ibuf_se_ctl, IMSG_CTL_END, 0, imsg.hdr.pid,
> -1, NULL, 0);
> break;
> Index: rde.h
> ===================================================================
> RCS file: /cvs/src/usr.sbin/bgpd/rde.h,v
> retrieving revision 1.267
> diff -u -p -r1.267 rde.h
> --- rde.h 30 Aug 2022 18:50:21 -0000 1.267
> +++ rde.h 31 Aug 2022 11:27:54 -0000
> @@ -162,9 +162,8 @@ enum attrtypes {
> #define ATTR_WELL_KNOWN ATTR_TRANSITIVE
>
> struct attr {
> - LIST_ENTRY(attr) entry;
> + RB_ENTRY(attr) entry;
> u_char *data;
> - uint64_t hash;
> int refcnt;
> uint16_t len;
> uint8_t flags;
> @@ -429,9 +428,7 @@ int attr_write(void *, uint16_t, uint8
> uint16_t);
> int attr_writebuf(struct ibuf *, uint8_t, uint8_t, void *,
> uint16_t);
> -void attr_init(uint32_t);
> void attr_shutdown(void);
> -void attr_hash_stats(struct rde_hashstats *);
> int attr_optadd(struct rde_aspath *, uint8_t, uint8_t,
> void *, uint16_t);
> struct attr *attr_optget(const struct rde_aspath *, uint8_t);
> Index: rde_attr.c
> ===================================================================
> RCS file: /cvs/src/usr.sbin/bgpd/rde_attr.c,v
> retrieving revision 1.129
> diff -u -p -r1.129 rde_attr.c
> --- rde_attr.c 29 Aug 2022 18:18:55 -0000 1.129
> +++ rde_attr.c 31 Aug 2022 11:27:54 -0000
> @@ -92,74 +92,21 @@ attr_writebuf(struct ibuf *buf, uint8_t
> }
>
> /* optional attribute specific functions */
> -int attr_diff(struct attr *, struct attr *);
> -struct attr *attr_alloc(uint8_t, uint8_t, const void *, uint16_t);
> -struct attr *attr_lookup(uint8_t, uint8_t, const void *, uint16_t);
> +struct attr *attr_alloc(uint8_t, uint8_t, void *, uint16_t);
> +struct attr *attr_lookup(uint8_t, uint8_t, void *, uint16_t);
> void attr_put(struct attr *);
>
> -struct attr_table {
> - struct attr_list *hashtbl;
> - uint64_t hashmask;
> -} attrtable;
> +static inline int attr_diff(struct attr *, struct attr *);
>
> -SIPHASH_KEY attrtablekey;
> +RB_HEAD(attr_tree, attr) attrtable = RB_INITIALIZER(&attr);
> +RB_GENERATE_STATIC(attr_tree, attr, entry, attr_diff);
>
> -#define ATTR_HASH(x) \
> - &attrtable.hashtbl[(x) & attrtable.hashmask]
> -
> -void
> -attr_init(uint32_t hashsize)
> -{
> - uint32_t hs, i;
> -
> - arc4random_buf(&attrtablekey, sizeof(attrtablekey));
> - for (hs = 1; hs < hashsize; hs <<= 1)
> - ;
> - attrtable.hashtbl = calloc(hs, sizeof(struct attr_list));
> - if (attrtable.hashtbl == NULL)
> - fatal("%s", __func__);
> -
> - for (i = 0; i < hs; i++)
> - LIST_INIT(&attrtable.hashtbl[i]);
> -
> - attrtable.hashmask = hs - 1;
> -}
>
> void
> attr_shutdown(void)
> {
> - uint64_t i;
> -
> - for (i = 0; i <= attrtable.hashmask; i++)
> - if (!LIST_EMPTY(&attrtable.hashtbl[i]))
> - log_warnx("%s: free non-free table", __func__);
> -
> - free(attrtable.hashtbl);
> -}
> -
> -void
> -attr_hash_stats(struct rde_hashstats *hs)
> -{
> - struct attr *a;
> - uint64_t i;
> - int64_t n;
> -
> - memset(hs, 0, sizeof(*hs));
> - strlcpy(hs->name, "attr hash", sizeof(hs->name));
> - hs->min = LLONG_MAX;
> - hs->num = attrtable.hashmask + 1;
> -
> - for (i = 0; i <= attrtable.hashmask; i++) {
> - n = 0;
> - LIST_FOREACH(a, &attrtable.hashtbl[i], entry)
> - n++;
> - if (n < hs->min)
> - hs->min = n;
> - if (n > hs->max)
> - hs->max = n;
> - hs->sum += n;
> - hs->sumq += n * n;
> - }
> + if (!RB_EMPTY(&attrtable))
> + log_warnx("%s: free non-free attr table", __func__);
> }
>
> int
> @@ -259,7 +206,7 @@ attr_copy(struct rde_aspath *t, const st
> }
> }
>
> -int
> +static inline int
> attr_diff(struct attr *oa, struct attr *ob)
> {
> int r;
> @@ -285,8 +232,7 @@ attr_diff(struct attr *oa, struct attr *
> return (1);
> if (r < 0)
> return (-1);
> -
> - fatalx("attr_diff: equal attributes encountered");
> + return (0);
> }
>
> int
> @@ -312,18 +258,6 @@ attr_compare(struct rde_aspath *a, struc
> return (0);
> }
>
> -uint64_t
> -attr_hash(struct rde_aspath *a)
> -{
> - uint64_t hash = 0;
> - uint8_t l;
> -
> - for (l = 0; l < a->others_len; l++)
> - if (a->others[l] != NULL)
> - hash ^= a->others[l]->hash;
> - return (hash);
> -}
> -
> void
> attr_free(struct rde_aspath *asp, struct attr *attr)
> {
> @@ -355,10 +289,9 @@ attr_freeall(struct rde_aspath *asp)
> }
>
> struct attr *
> -attr_alloc(uint8_t flags, uint8_t type, const void *data, uint16_t len)
> +attr_alloc(uint8_t flags, uint8_t type, void *data, uint16_t len)
> {
> struct attr *a;
> - SIPHASH_CTX ctx;
>
> a = calloc(1, sizeof(struct attr));
> if (a == NULL)
> @@ -379,42 +312,24 @@ attr_alloc(uint8_t flags, uint8_t type,
> } else
> a->data = NULL;
>
> - SipHash24_Init(&ctx, &attrtablekey);
> - SipHash24_Update(&ctx, &flags, sizeof(flags));
> - SipHash24_Update(&ctx, &type, sizeof(type));
> - SipHash24_Update(&ctx, &len, sizeof(len));
> - SipHash24_Update(&ctx, a->data, a->len);
> - a->hash = SipHash24_End(&ctx);
> - LIST_INSERT_HEAD(ATTR_HASH(a->hash), a, entry);
> + if (RB_INSERT(attr_tree, &attrtable, a) != NULL)
> + fatalx("corrupted attr tree");
>
> return (a);
> }
>
> struct attr *
> -attr_lookup(uint8_t flags, uint8_t type, const void *data, uint16_t len)
> +attr_lookup(uint8_t flags, uint8_t type, void *data, uint16_t len)
> {
> - struct attr_list *head;
> - struct attr *a;
> - uint64_t hash;
> - SIPHASH_CTX ctx;
> + struct attr needle;
>
> flags &= ~ATTR_DEFMASK; /* normalize mask */
>
> - SipHash24_Init(&ctx, &attrtablekey);
> - SipHash24_Update(&ctx, &flags, sizeof(flags));
> - SipHash24_Update(&ctx, &type, sizeof(type));
> - SipHash24_Update(&ctx, &len, sizeof(len));
> - SipHash24_Update(&ctx, data, len);
> - hash = SipHash24_End(&ctx);
> - head = ATTR_HASH(hash);
> -
> - LIST_FOREACH(a, head, entry) {
> - if (hash == a->hash && type == a->type &&
> - flags == a->flags && len == a->len &&
> - memcmp(data, a->data, len) == 0)
> - return (a);
> - }
> - return (NULL);
> + needle.flags = flags;
> + needle.type = type;
> + needle.len = len;
> + needle.data = data;
> + return RB_FIND(attr_tree, &attrtable, &needle);
> }
>
> void
> @@ -429,7 +344,7 @@ attr_put(struct attr *a)
> return;
>
> /* unlink */
> - LIST_REMOVE(a, entry);
> + RB_REMOVE(attr_tree, &attrtable, a);
>
> if (a->len != 0)
> rdemem.attr_dcnt--;
>
