From 3487a0407f2d91c6883cbf77298d49f609f74c97 Mon Sep 17 00:00:00 2001 From: claudio Date: Mon, 29 Aug 2022 18:18:55 +0000 Subject: [PATCH] Instead of a global aspath cache copy the aspath attribute per rde_aspath struct. It uses a bit more memory but improves performance a lot on really big systems because aspath_get() becomes a very hot function. OK tb@ --- usr.sbin/bgpd/bgpd.h | 3 +- usr.sbin/bgpd/rde.c | 11 +-- usr.sbin/bgpd/rde.h | 9 +-- usr.sbin/bgpd/rde_attr.c | 161 +++++++++------------------------------ usr.sbin/bgpd/rde_rib.c | 9 +-- 5 files changed, 46 insertions(+), 147 deletions(-) diff --git a/usr.sbin/bgpd/bgpd.h b/usr.sbin/bgpd/bgpd.h index de8d50ba97c..86c09676c57 100644 --- a/usr.sbin/bgpd/bgpd.h +++ b/usr.sbin/bgpd/bgpd.h @@ -1,4 +1,4 @@ -/* $OpenBSD: bgpd.h,v 1.450 2022/08/26 14:10:52 claudio Exp $ */ +/* $OpenBSD: bgpd.h,v 1.451 2022/08/29 18:18:55 claudio Exp $ */ /* * Copyright (c) 2003, 2004 Henning Brauer @@ -1193,7 +1193,6 @@ struct rde_memstats { long long nexthop_cnt; long long aspath_cnt; long long aspath_size; - long long aspath_refs; long long comm_cnt; long long comm_nmemb; long long comm_size; diff --git a/usr.sbin/bgpd/rde.c b/usr.sbin/bgpd/rde.c index b6a3db148f6..12339b3f251 100644 --- a/usr.sbin/bgpd/rde.c +++ b/usr.sbin/bgpd/rde.c @@ -1,4 +1,4 @@ -/* $OpenBSD: rde.c,v 1.568 2022/08/29 16:44:47 claudio Exp $ */ +/* $OpenBSD: rde.c,v 1.569 2022/08/29 18:18:55 claudio Exp $ */ /* * Copyright (c) 2003, 2004 Henning Brauer @@ -197,7 +197,6 @@ rde_main(int debug, int verbose) /* initialize the RIB structures */ pt_init(); - aspath_init(pathhashsize); attr_init(attrhashsize); nexthop_init(nexthophashsize); peer_init(peerhashsize); @@ -630,9 +629,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)); - aspath_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); imsg_compose(ibuf_se_ctl, IMSG_CTL_SHOW_RIB_HASH, 0, imsg.hdr.pid, -1, &rdehash, sizeof(rdehash)); @@ -1631,7 +1627,9 @@ pathid_assign(struct rde_peer *peer, uint32_t path_id, struct prefix *p = NULL; uint32_t path_id_tx; - /* Assign a send side path_id to all paths */ + /* + * Assign a send side path_id to all paths. + */ re = rib_get(rib_byid(RIB_ADJ_IN), prefix, prefixlen); if (re != NULL) p = prefix_bypeer(re, peer, path_id); @@ -4308,7 +4306,6 @@ rde_shutdown(void) rib_shutdown(); nexthop_shutdown(); path_shutdown(); - aspath_shutdown(); attr_shutdown(); pt_shutdown(); peer_shutdown(); diff --git a/usr.sbin/bgpd/rde.h b/usr.sbin/bgpd/rde.h index 774e847f35a..8b15b47fbb2 100644 --- a/usr.sbin/bgpd/rde.h +++ b/usr.sbin/bgpd/rde.h @@ -1,4 +1,4 @@ -/* $OpenBSD: rde.h,v 1.265 2022/08/29 16:44:47 claudio Exp $ */ +/* $OpenBSD: rde.h,v 1.266 2022/08/29 18:18:55 claudio Exp $ */ /* * Copyright (c) 2003, 2004 Claudio Jeker and @@ -71,7 +71,6 @@ struct rib { * Currently I assume that we can do that with the neighbor_ip... */ LIST_HEAD(rde_peer_head, rde_peer); -LIST_HEAD(aspath_list, aspath); LIST_HEAD(attr_list, attr); RB_HEAD(prefix_tree, prefix); RB_HEAD(prefix_index, prefix); @@ -122,9 +121,7 @@ struct rde_peer { #define ASPATH_HEADER_SIZE (offsetof(struct aspath, data)) struct aspath { - LIST_ENTRY(aspath) entry; uint32_t source_as; /* cached source_as */ - int refcnt; /* reference count */ uint16_t len; /* total length of aspath in octets */ uint16_t ascnt; /* number of AS hops in data */ u_char data[1]; /* placeholder for actual data */ @@ -446,10 +443,8 @@ void attr_free(struct rde_aspath *, struct attr *); #define attr_optlen(x) \ ((x)->len > 255 ? (x)->len + 4 : (x)->len + 3) -void aspath_init(uint32_t); -void aspath_shutdown(void); -void aspath_hash_stats(struct rde_hashstats *); struct aspath *aspath_get(void *, uint16_t); +struct aspath *aspath_copy(struct aspath *); void aspath_put(struct aspath *); u_char *aspath_deflate(u_char *, uint16_t *, int *); void aspath_merge(struct rde_aspath *, struct attr *); diff --git a/usr.sbin/bgpd/rde_attr.c b/usr.sbin/bgpd/rde_attr.c index 5a765ab68c1..b235dc316c1 100644 --- a/usr.sbin/bgpd/rde_attr.c +++ b/usr.sbin/bgpd/rde_attr.c @@ -1,4 +1,4 @@ -/* $OpenBSD: rde_attr.c,v 1.128 2022/08/29 18:04:51 claudio Exp $ */ +/* $OpenBSD: rde_attr.c,v 1.129 2022/08/29 18:18:55 claudio Exp $ */ /* * Copyright (c) 2004 Claudio Jeker @@ -446,102 +446,57 @@ static uint32_t aspath_extract_origin(const void *, uint16_t); static uint16_t aspath_countlength(struct aspath *, uint16_t, int); static void aspath_countcopy(struct aspath *, uint16_t, uint8_t *, uint16_t, int); -struct aspath *aspath_lookup(const void *, uint16_t); -struct aspath_table { - struct aspath_list *hashtbl; - uint32_t hashmask; -} astable; - -SIPHASH_KEY astablekey; - -#define ASPATH_HASH(x) \ - &astable.hashtbl[(x) & astable.hashmask] - -void -aspath_init(uint32_t hashsize) +int +aspath_compare(struct aspath *a1, struct aspath *a2) { - uint32_t hs, i; - - for (hs = 1; hs < hashsize; hs <<= 1) - ; - astable.hashtbl = calloc(hs, sizeof(struct aspath_list)); - if (astable.hashtbl == NULL) - fatal("aspath_init"); - - for (i = 0; i < hs; i++) - LIST_INIT(&astable.hashtbl[i]); + int r; - astable.hashmask = hs - 1; - arc4random_buf(&astablekey, sizeof(astablekey)); + if (a1->len > a2->len) + return (1); + if (a1->len < a2->len) + return (-1); + r = memcmp(a1->data, a2->data, a1->len); + if (r > 0) + return (1); + if (r < 0) + return (-1); + return (0); } -void -aspath_shutdown(void) +struct aspath * +aspath_get(void *data, uint16_t len) { - uint32_t i; + struct aspath *aspath; - for (i = 0; i <= astable.hashmask; i++) - if (!LIST_EMPTY(&astable.hashtbl[i])) - log_warnx("aspath_shutdown: free non-free table"); + aspath = malloc(ASPATH_HEADER_SIZE + len); + if (aspath == NULL) + fatal("%s", __func__); - free(astable.hashtbl); -} + rdemem.aspath_cnt++; + rdemem.aspath_size += ASPATH_HEADER_SIZE + len; -void -aspath_hash_stats(struct rde_hashstats *hs) -{ - struct aspath *a; - uint32_t i; - int64_t n; + aspath->len = len; + aspath->ascnt = aspath_count(data, len); + aspath->source_as = aspath_extract_origin(data, len); + memcpy(aspath->data, data, len); - memset(hs, 0, sizeof(*hs)); - strlcpy(hs->name, "aspath hash", sizeof(hs->name)); - hs->min = LLONG_MAX; - hs->num = astable.hashmask + 1; - - for (i = 0; i <= astable.hashmask; i++) { - n = 0; - LIST_FOREACH(a, &astable.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; - } + return (aspath); } struct aspath * -aspath_get(void *data, uint16_t len) +aspath_copy(struct aspath *a) { - struct aspath_list *head; struct aspath *aspath; - /* The aspath must already have been checked for correctness. */ - aspath = aspath_lookup(data, len); - if (aspath == NULL) { - aspath = malloc(ASPATH_HEADER_SIZE + len); - if (aspath == NULL) - fatal("aspath_get"); - - rdemem.aspath_cnt++; - rdemem.aspath_size += ASPATH_HEADER_SIZE + len; - - aspath->refcnt = 0; - aspath->len = len; - aspath->ascnt = aspath_count(data, len); - aspath->source_as = aspath_extract_origin(data, len); - memcpy(aspath->data, data, len); - - /* link */ - head = ASPATH_HASH(SipHash24(&astablekey, aspath->data, - aspath->len)); - LIST_INSERT_HEAD(head, aspath, entry); - } - aspath->refcnt++; - rdemem.aspath_refs++; + aspath = malloc(ASPATH_HEADER_SIZE + a->len); + if (aspath == NULL) + fatal("%s", __func__); + + rdemem.aspath_cnt++; + rdemem.aspath_size += ASPATH_HEADER_SIZE + a->len; + + memcpy(aspath, a, ASPATH_HEADER_SIZE + a->len); return (aspath); } @@ -552,15 +507,6 @@ aspath_put(struct aspath *aspath) if (aspath == NULL) return; - rdemem.aspath_refs--; - if (--aspath->refcnt > 0) { - /* somebody still holds a reference */ - return; - } - - /* unlink */ - LIST_REMOVE(aspath, entry); - rdemem.aspath_cnt--; rdemem.aspath_size -= ASPATH_HEADER_SIZE + aspath->len; free(aspath); @@ -850,41 +796,6 @@ aspath_loopfree(struct aspath *aspath, uint32_t myAS) return (1); } -int -aspath_compare(struct aspath *a1, struct aspath *a2) -{ - int r; - - if (a1->len > a2->len) - return (1); - if (a1->len < a2->len) - return (-1); - r = memcmp(a1->data, a2->data, a1->len); - if (r > 0) - return (1); - if (r < 0) - return (-1); - return (0); -} - -struct aspath * -aspath_lookup(const void *data, uint16_t len) -{ - struct aspath_list *head; - struct aspath *aspath; - uint32_t hash; - - hash = SipHash24(&astablekey, data, len); - head = ASPATH_HASH(hash); - - LIST_FOREACH(aspath, head, entry) { - if (len == aspath->len && memcmp(data, aspath->data, len) == 0) - return (aspath); - } - return (NULL); -} - - static int as_compare(struct filter_as *f, uint32_t as, uint32_t neighas) { diff --git a/usr.sbin/bgpd/rde_rib.c b/usr.sbin/bgpd/rde_rib.c index e1c552e508c..dd6b84149b7 100644 --- a/usr.sbin/bgpd/rde_rib.c +++ b/usr.sbin/bgpd/rde_rib.c @@ -1,4 +1,4 @@ -/* $OpenBSD: rde_rib.c,v 1.245 2022/08/29 16:43:07 claudio Exp $ */ +/* $OpenBSD: rde_rib.c,v 1.246 2022/08/29 18:18:55 claudio Exp $ */ /* * Copyright (c) 2003, 2004 Claudio Jeker @@ -678,11 +678,7 @@ path_unlink(struct rde_aspath *asp) struct rde_aspath * path_copy(struct rde_aspath *dst, const struct rde_aspath *src) { - dst->aspath = src->aspath; - if (dst->aspath != NULL) { - dst->aspath->refcnt++; - rdemem.aspath_refs++; - } + dst->aspath = aspath_copy(src->aspath); dst->hash = 0; /* not linked so no hash and no refcnt */ dst->refcnt = 0; dst->flags = src->flags & ~F_ATTR_LINKED; @@ -734,6 +730,7 @@ path_clean(struct rde_aspath *asp) rtlabel_unref(asp->rtlabelid); pftable_unref(asp->pftableid); aspath_put(asp->aspath); + asp->aspath = NULL; attr_freeall(asp); } -- 2.20.1