The hash table for communities is not great. Instead of implementing
dynamic hash resize use a RB tree. Also drop the hash calculation and
just use memcmp() for now. My non scientific test seems to indicate that
the overhead of SipHash is about the same as the memcmp().
--
:wq Claudio
Index: bgpd/rde.c
===================================================================
RCS file: /cvs/src/usr.sbin/bgpd/rde.c,v
retrieving revision 1.566
diff -u -p -r1.566 rde.c
--- bgpd/rde.c 29 Aug 2022 14:57:27 -0000 1.566
+++ bgpd/rde.c 29 Aug 2022 14:58:52 -0000
@@ -199,7 +199,6 @@ rde_main(int debug, int verbose)
pt_init();
path_init(pathhashsize);
aspath_init(pathhashsize);
- communities_init(attrhashsize);
attr_init(attrhashsize);
nexthop_init(nexthophashsize);
peer_init(peerhashsize);
@@ -636,9 +635,6 @@ badnetdel:
imsg_compose(ibuf_se_ctl, IMSG_CTL_SHOW_RIB_HASH, 0,
imsg.hdr.pid, -1, &rdehash, sizeof(rdehash));
aspath_hash_stats(&rdehash);
- imsg_compose(ibuf_se_ctl, IMSG_CTL_SHOW_RIB_HASH, 0,
- imsg.hdr.pid, -1, &rdehash, sizeof(rdehash));
- communities_hash_stats(&rdehash);
imsg_compose(ibuf_se_ctl, IMSG_CTL_SHOW_RIB_HASH, 0,
imsg.hdr.pid, -1, &rdehash, sizeof(rdehash));
attr_hash_stats(&rdehash);
Index: bgpd/rde.h
===================================================================
RCS file: /cvs/src/usr.sbin/bgpd/rde.h,v
retrieving revision 1.263
diff -u -p -r1.263 rde.h
--- bgpd/rde.h 26 Aug 2022 14:10:52 -0000 1.263
+++ bgpd/rde.h 29 Aug 2022 14:58:52 -0000
@@ -183,9 +183,9 @@ struct mpattr {
};
struct rde_community {
- LIST_ENTRY(rde_community) entry;
- size_t size;
- size_t nentries;
+ RB_ENTRY(rde_community) entry;
+ int size;
+ int nentries;
int flags;
int refcnt;
struct community *communities;
@@ -486,9 +486,7 @@ int community_large_write(struct rde_com
int community_ext_write(struct rde_community *, int, void *, uint16_t);
int community_writebuf(struct ibuf *, struct rde_community *);
-void communities_init(uint32_t);
void communities_shutdown(void);
-void communities_hash_stats(struct rde_hashstats *);
struct rde_community *communities_lookup(struct rde_community *);
struct rde_community *communities_link(struct rde_community *);
void communities_unlink(struct rde_community *);
Index: bgpd/rde_community.c
===================================================================
RCS file: /cvs/src/usr.sbin/bgpd/rde_community.c,v
retrieving revision 1.7
diff -u -p -r1.7 rde_community.c
--- bgpd/rde_community.c 28 Jul 2022 13:11:51 -0000 1.7
+++ bgpd/rde_community.c 29 Aug 2022 14:58:52 -0000
@@ -209,12 +209,12 @@ mask_match(struct community *a, struct c
static void
insert_community(struct rde_community *comm, struct community *c)
{
- size_t l;
+ int l;
int r;
if (comm->nentries + 1 > comm->size) {
struct community *new;
- size_t newsize = comm->size + 8;
+ int newsize = comm->size + 8;
if ((new = reallocarray(comm->communities, newsize,
sizeof(struct community))) == NULL)
@@ -261,7 +261,7 @@ community_match(struct rde_community *co
struct rde_peer *peer)
{
struct community test, mask;
- size_t l;
+ int l;
if (fc->flags >> 8 == 0) {
/* fast path */
@@ -288,7 +288,7 @@ struct rde_peer *peer)
int
community_count(struct rde_community *comm, uint8_t type)
{
- size_t l;
+ int l;
int count = 0;
/* use the fact that the array is ordered by type */
@@ -351,7 +351,7 @@ struct rde_peer *peer)
{
struct community test, mask;
struct community *match;
- size_t l = 0;
+ int l = 0;
if (fc->flags >> 8 == 0) {
/* fast path */
@@ -501,8 +501,8 @@ community_write(struct rde_community *co
{
uint8_t *b = buf;
uint16_t c;
- size_t l, n = 0;
- int r, flags = ATTR_OPTIONAL | ATTR_TRANSITIVE;
+ size_t n = 0;
+ int l, r, flags = ATTR_OPTIONAL | ATTR_TRANSITIVE;
if (comm->flags & PARTIAL_COMMUNITIES)
flags |= ATTR_PARTIAL;
@@ -545,8 +545,8 @@ community_large_write(struct rde_communi
{
uint8_t *b = buf;
uint32_t c;
- size_t l, n = 0;
- int r, flags = ATTR_OPTIONAL | ATTR_TRANSITIVE;
+ size_t n = 0;
+ int l, r, flags = ATTR_OPTIONAL | ATTR_TRANSITIVE;
if (comm->flags & PARTIAL_LARGE_COMMUNITIES)
flags |= ATTR_PARTIAL;
@@ -596,8 +596,8 @@ community_ext_write(struct rde_community
struct community *cp;
uint8_t *b = buf;
uint64_t ext;
- size_t l, n = 0;
- int r, flags = ATTR_OPTIONAL | ATTR_TRANSITIVE;
+ size_t n = 0;
+ int l, r, flags = ATTR_OPTIONAL | ATTR_TRANSITIVE;
if (comm->flags & PARTIAL_EXT_COMMUNITIES)
flags |= ATTR_PARTIAL;
@@ -654,8 +654,8 @@ community_ext_write(struct rde_community
int
community_writebuf(struct ibuf *buf, struct rde_community *comm)
{
- size_t l, basic_n = 0, large_n = 0, ext_n = 0;
- int flags;
+ size_t basic_n = 0, large_n = 0, ext_n = 0;
+ int l, flags;
/* first count how many communities will be written */
for (l = 0; l < comm->nentries; l++)
@@ -764,113 +764,44 @@ community_writebuf(struct ibuf *buf, str
/*
* Global RIB cache for communities
*/
-LIST_HEAD(commhead, rde_community);
-
-static struct comm_table {
- struct commhead *hashtbl;
- uint64_t hashmask;
-} commtable;
-
-static SIPHASH_KEY commtablekey;
-
-static inline struct commhead *
-communities_hash(struct rde_community *comm)
-{
- SIPHASH_CTX ctx;
- uint64_t hash;
-
- SipHash24_Init(&ctx, &commtablekey);
- SipHash24_Update(&ctx, &comm->nentries, sizeof(comm->nentries));
- SipHash24_Update(&ctx, &comm->flags, sizeof(comm->flags));
- if (comm->nentries > 0)
- SipHash24_Update(&ctx, comm->communities,
- comm->nentries * sizeof(*comm->communities));
- hash = SipHash24_End(&ctx);
-
- return &commtable.hashtbl[hash & commtable.hashmask];
-}
-
-void
-communities_init(uint32_t hashsize)
+static inline int
+communities_compare(struct rde_community *a, struct rde_community *b)
{
- uint32_t hs, i;
+ if (a->nentries != b->nentries)
+ return a->nentries - b->nentries;
+ if (a->flags != b->flags)
+ return a->flags - b->flags;
- arc4random_buf(&commtablekey, sizeof(commtablekey));
- for (hs = 1; hs < hashsize; hs <<= 1)
- ;
- commtable.hashtbl = calloc(hs, sizeof(*commtable.hashtbl));
- if (commtable.hashtbl == NULL)
- fatal(__func__);
-
- for (i = 0; i < hs; i++)
- LIST_INIT(&commtable.hashtbl[i]);
- commtable.hashmask = hs - 1;
+ return memcmp(a->communities, b->communities,
+ a->nentries * sizeof(struct community));
}
-void
-communities_shutdown(void)
-{
- uint64_t i;
-
- for (i = 0; i <= commtable.hashmask; i++)
- if (!LIST_EMPTY(&commtable.hashtbl[i]))
- log_warnx("%s: free non-free table", __func__);
-
- free(commtable.hashtbl);
-}
+RB_HEAD(comm_tree, rde_community) commtable = RB_INITIALIZER(&commtable);
+RB_GENERATE_STATIC(comm_tree, rde_community, entry, communities_compare);
void
-communities_hash_stats(struct rde_hashstats *hs)
+communities_shutdown(void)
{
- struct rde_community *c;
- uint64_t i;
- int64_t n;
-
- memset(hs, 0, sizeof(*hs));
- strlcpy(hs->name, "comm hash", sizeof(hs->name));
- hs->min = LLONG_MAX;
- hs->num = commtable.hashmask + 1;
-
- for (i = 0; i <= commtable.hashmask; i++) {
- n = 0;
- LIST_FOREACH(c, &commtable.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(&commtable))
+ log_warnx("%s: free non-free table", __func__);
}
struct rde_community *
communities_lookup(struct rde_community *comm)
{
- struct rde_community *c;
- struct commhead *head;
-
- head = communities_hash(comm);
- LIST_FOREACH(c, head, entry) {
- if (communities_equal(comm, c))
- return c;
- }
- return NULL;
+ return RB_FIND(comm_tree, &commtable, comm);
}
struct rde_community *
communities_link(struct rde_community *comm)
{
struct rde_community *n;
- struct commhead *head;
if ((n = malloc(sizeof(*n))) == NULL)
fatal(__func__);
-
communities_copy(n, comm);
- head = communities_hash(n);
- LIST_INSERT_HEAD(head, n, entry);
+ RB_INSERT(comm_tree, &commtable, n);
n->refcnt = 1; /* initial reference by the cache */
rdemem.comm_size += n->size;
@@ -886,7 +817,7 @@ communities_unlink(struct rde_community
if (comm->refcnt != 1)
fatalx("%s: unlinking still referenced communities", __func__);
- LIST_REMOVE(comm, entry);
+ RB_REMOVE(comm_tree, &commtable, comm);
rdemem.comm_size -= comm->size;
rdemem.comm_nmemb -= comm->nentries;
