From 23f5897daa3fcc4b2679a0aa5f7896279f66b955 Mon Sep 17 00:00:00 2001 From: claudio Date: Mon, 29 Aug 2022 16:44:47 +0000 Subject: [PATCH] Switch the DB of communities collections to a RB tree instead of an undersized hash table. OK tb@ --- usr.sbin/bgpd/rde.c | 6 +- usr.sbin/bgpd/rde.h | 10 +-- usr.sbin/bgpd/rde_community.c | 136 +++++++++------------------------- 3 files changed, 41 insertions(+), 111 deletions(-) diff --git a/usr.sbin/bgpd/rde.c b/usr.sbin/bgpd/rde.c index 7900a1e5b3c..b6a3db148f6 100644 --- a/usr.sbin/bgpd/rde.c +++ b/usr.sbin/bgpd/rde.c @@ -1,4 +1,4 @@ -/* $OpenBSD: rde.c,v 1.567 2022/08/29 16:43:07 claudio Exp $ */ +/* $OpenBSD: rde.c,v 1.568 2022/08/29 16:44:47 claudio Exp $ */ /* * Copyright (c) 2003, 2004 Henning Brauer @@ -198,7 +198,6 @@ rde_main(int debug, int verbose) /* initialize the RIB structures */ pt_init(); aspath_init(pathhashsize); - communities_init(attrhashsize); attr_init(attrhashsize); nexthop_init(nexthophashsize); peer_init(peerhashsize); @@ -632,9 +631,6 @@ badnetdel: imsg_compose(ibuf_se_ctl, IMSG_CTL_SHOW_RIB_MEM, 0, imsg.hdr.pid, -1, &rdemem, sizeof(rdemem)); 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); diff --git a/usr.sbin/bgpd/rde.h b/usr.sbin/bgpd/rde.h index 8c14ad4fa60..774e847f35a 100644 --- a/usr.sbin/bgpd/rde.h +++ b/usr.sbin/bgpd/rde.h @@ -1,4 +1,4 @@ -/* $OpenBSD: rde.h,v 1.264 2022/08/29 16:43:07 claudio Exp $ */ +/* $OpenBSD: rde.h,v 1.265 2022/08/29 16:44:47 claudio Exp $ */ /* * Copyright (c) 2003, 2004 Claudio Jeker and @@ -182,9 +182,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; @@ -483,9 +483,7 @@ int community_large_write(struct rde_community *, void *, uint16_t); 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 *); diff --git a/usr.sbin/bgpd/rde_community.c b/usr.sbin/bgpd/rde_community.c index 660b29716fe..d7d5aeaaea2 100644 --- a/usr.sbin/bgpd/rde_community.c +++ b/usr.sbin/bgpd/rde_community.c @@ -1,4 +1,4 @@ -/* $OpenBSD: rde_community.c,v 1.7 2022/07/28 13:11:51 deraadt Exp $ */ +/* $OpenBSD: rde_community.c,v 1.8 2022/08/29 16:44:47 claudio Exp $ */ /* * Copyright (c) 2019 Claudio Jeker @@ -209,12 +209,12 @@ mask_match(struct community *a, struct community *b, struct community *m) 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 *comm, struct community *fc, 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 *comm, void *buf, uint16_t len) { 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_community *comm, void *buf, uint16_t len) { 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 *comm, int ebgp, void *buf, 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 *comm, int ebgp, void *buf, 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,49 @@ community_writebuf(struct ibuf *buf, struct rde_community *comm) /* * 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; - - 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__); + if (a->nentries != b->nentries) + return a->nentries > b->nentries ? 1 : -1; + if (a->flags != b->flags) + return a->flags > b->flags ? 1 : -1; - 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)); } +RB_HEAD(comm_tree, rde_community) commtable = RB_INITIALIZER(&commtable); +RB_GENERATE_STATIC(comm_tree, rde_community, entry, communities_compare); + 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); -} - -void -communities_hash_stats(struct rde_hashstats *hs) -{ - 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; + struct rde_community *n, *f; if ((n = malloc(sizeof(*n))) == NULL) fatal(__func__); - communities_copy(n, comm); - head = communities_hash(n); - LIST_INSERT_HEAD(head, n, entry); + if ((f = RB_INSERT(comm_tree, &commtable, n)) != NULL) { + log_warnx("duplicate communities collection inserted"); + free(n->communities); + free(n); + return f; + } n->refcnt = 1; /* initial reference by the cache */ rdemem.comm_size += n->size; @@ -886,7 +822,7 @@ communities_unlink(struct rde_community *comm) 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; -- 2.20.1