On Mon, Aug 29, 2022 at 05:49:06PM +0200, Theo Buehler wrote:
> On Mon, Aug 29, 2022 at 05:28:50PM +0200, Claudio Jeker wrote:
> > This is the 2nd RB tree transformation instead of the hash table.
> >
> > The rde.c part will probably conflict with the change for communities.
>
> Apart from an unchecked RB_INSERT() this also looks fine.
I just fatal in this case because this is a serious bug.
--
:wq Claudio
Index: rde.c
===================================================================
RCS file: /cvs/src/usr.sbin/bgpd/rde.c,v
retrieving revision 1.566
diff -u -p -r1.566 rde.c
--- rde.c 29 Aug 2022 14:57:27 -0000 1.566
+++ rde.c 29 Aug 2022 15:11:57 -0000
@@ -197,7 +197,6 @@ rde_main(int debug, int verbose)
/* initialize the RIB structures */
pt_init();
- path_init(pathhashsize);
aspath_init(pathhashsize);
communities_init(attrhashsize);
attr_init(attrhashsize);
@@ -632,9 +631,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));
- path_hash_stats(&rdehash);
- 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));
Index: rde.h
===================================================================
RCS file: /cvs/src/usr.sbin/bgpd/rde.h,v
retrieving revision 1.263
diff -u -p -r1.263 rde.h
--- rde.h 26 Aug 2022 14:10:52 -0000 1.263
+++ rde.h 29 Aug 2022 15:11:16 -0000
@@ -73,7 +73,6 @@ struct rib {
LIST_HEAD(rde_peer_head, rde_peer);
LIST_HEAD(aspath_list, aspath);
LIST_HEAD(attr_list, attr);
-LIST_HEAD(aspath_head, rde_aspath);
RB_HEAD(prefix_tree, prefix);
RB_HEAD(prefix_index, prefix);
struct iq;
@@ -219,20 +218,18 @@ struct rde_community {
#define DEFAULT_LPREF 100
struct rde_aspath {
- LIST_ENTRY(rde_aspath) path_l;
+ RB_ENTRY(rde_aspath) entry;
struct attr **others;
struct aspath *aspath;
uint64_t hash;
int refcnt;
uint32_t flags; /* internally used */
-#define aspath_hashstart med
uint32_t med; /* multi exit disc */
uint32_t lpref; /* local pref */
uint32_t weight; /* low prio lpref */
uint16_t rtlabelid; /* route label id */
uint16_t pftableid; /* pf table id */
uint8_t origin;
-#define aspath_hashend others_len
uint8_t others_len;
};
@@ -594,10 +591,7 @@ re_rib(struct rib_entry *re)
return rib_byid(re->rib_id);
}
-void path_init(uint32_t);
void path_shutdown(void);
-void path_hash_stats(struct rde_hashstats *);
-int path_compare(struct rde_aspath *, struct rde_aspath *);
uint32_t path_remove_stale(struct rde_aspath *, uint8_t, time_t);
struct rde_aspath *path_copy(struct rde_aspath *, const struct rde_aspath *);
struct rde_aspath *path_prep(struct rde_aspath *);
Index: rde_rib.c
===================================================================
RCS file: /cvs/src/usr.sbin/bgpd/rde_rib.c,v
retrieving revision 1.244
diff -u -p -r1.244 rde_rib.c
--- rde_rib.c 25 Aug 2022 08:10:25 -0000 1.244
+++ rde_rib.c 29 Aug 2022 15:56:59 -0000
@@ -547,99 +547,10 @@ rib_dump_new(uint16_t id, uint8_t aid, u
/* path specific functions */
static struct rde_aspath *path_lookup(struct rde_aspath *);
-static uint64_t path_hash(struct rde_aspath *);
static void path_link(struct rde_aspath *);
static void path_unlink(struct rde_aspath *);
-struct path_table {
- struct aspath_head *path_hashtbl;
- uint64_t path_hashmask;
-} pathtable;
-
-SIPHASH_KEY pathtablekey;
-
-#define PATH_HASH(x) &pathtable.path_hashtbl[x &
pathtable.path_hashmask]
-
-static inline struct rde_aspath *
-path_ref(struct rde_aspath *asp)
-{
- if ((asp->flags & F_ATTR_LINKED) == 0)
- fatalx("%s: unlinked object", __func__);
- asp->refcnt++;
- rdemem.path_refs++;
-
- return asp;
-}
-
-static inline void
-path_unref(struct rde_aspath *asp)
-{
- if (asp == NULL)
- return;
- if ((asp->flags & F_ATTR_LINKED) == 0)
- fatalx("%s: unlinked object", __func__);
- asp->refcnt--;
- rdemem.path_refs--;
- if (asp->refcnt <= 0)
- path_unlink(asp);
-}
-
-void
-path_init(uint32_t hashsize)
-{
- uint32_t hs, i;
-
- for (hs = 1; hs < hashsize; hs <<= 1)
- ;
- pathtable.path_hashtbl = calloc(hs, sizeof(*pathtable.path_hashtbl));
- if (pathtable.path_hashtbl == NULL)
- fatal("path_init");
-
- for (i = 0; i < hs; i++)
- LIST_INIT(&pathtable.path_hashtbl[i]);
-
- pathtable.path_hashmask = hs - 1;
- arc4random_buf(&pathtablekey, sizeof(pathtablekey));
-}
-
-void
-path_shutdown(void)
-{
- uint32_t i;
-
- for (i = 0; i <= pathtable.path_hashmask; i++)
- if (!LIST_EMPTY(&pathtable.path_hashtbl[i]))
- log_warnx("path_free: free non-free table");
-
- free(pathtable.path_hashtbl);
-}
-
-void
-path_hash_stats(struct rde_hashstats *hs)
-{
- struct rde_aspath *a;
- uint32_t i;
- int64_t n;
-
- memset(hs, 0, sizeof(*hs));
- strlcpy(hs->name, "path hash", sizeof(hs->name));
- hs->min = LLONG_MAX;
- hs->num = pathtable.path_hashmask + 1;
-
- for (i = 0; i <= pathtable.path_hashmask; i++) {
- n = 0;
- LIST_FOREACH(a, &pathtable.path_hashtbl[i], path_l)
- n++;
- if (n < hs->min)
- hs->min = n;
- if (n > hs->max)
- hs->max = n;
- hs->sum += n;
- hs->sumq += n * n;
- }
-}
-
-int
+static inline int
path_compare(struct rde_aspath *a, struct rde_aspath *b)
{
int r;
@@ -688,40 +599,44 @@ path_compare(struct rde_aspath *a, struc
return (attr_compare(a, b));
}
-static uint64_t
-path_hash(struct rde_aspath *asp)
-{
- SIPHASH_CTX ctx;
- uint64_t hash;
+RB_HEAD(path_tree, rde_aspath) pathtable = RB_INITIALIZER(&pathtable);
+RB_GENERATE_STATIC(path_tree, rde_aspath, entry, path_compare);
- SipHash24_Init(&ctx, &pathtablekey);
- SipHash24_Update(&ctx, &asp->aspath_hashstart,
- (char *)&asp->aspath_hashend - (char *)&asp->aspath_hashstart);
+static inline struct rde_aspath *
+path_ref(struct rde_aspath *asp)
+{
+ if ((asp->flags & F_ATTR_LINKED) == 0)
+ fatalx("%s: unlinked object", __func__);
+ asp->refcnt++;
+ rdemem.path_refs++;
- if (asp->aspath)
- SipHash24_Update(&ctx, asp->aspath->data, asp->aspath->len);
+ return asp;
+}
- hash = attr_hash(asp);
- SipHash24_Update(&ctx, &hash, sizeof(hash));
+static inline void
+path_unref(struct rde_aspath *asp)
+{
+ if (asp == NULL)
+ return;
+ if ((asp->flags & F_ATTR_LINKED) == 0)
+ fatalx("%s: unlinked object", __func__);
+ asp->refcnt--;
+ rdemem.path_refs--;
+ if (asp->refcnt <= 0)
+ path_unlink(asp);
+}
- return (SipHash24_End(&ctx));
+void
+path_shutdown(void)
+{
+ if (!RB_EMPTY(&pathtable))
+ log_warnx("path_free: free non-free table");
}
static struct rde_aspath *
path_lookup(struct rde_aspath *aspath)
{
- struct aspath_head *head;
- struct rde_aspath *asp;
- uint64_t hash;
-
- hash = path_hash(aspath);
- head = PATH_HASH(hash);
-
- LIST_FOREACH(asp, head, path_l) {
- if (asp->hash == hash && path_compare(aspath, asp) == 0)
- return (asp);
- }
- return (NULL);
+ return (RB_FIND(path_tree, &pathtable, aspath));
}
/*
@@ -731,12 +646,8 @@ path_lookup(struct rde_aspath *aspath)
static void
path_link(struct rde_aspath *asp)
{
- struct aspath_head *head;
-
- asp->hash = path_hash(asp);
- head = PATH_HASH(asp->hash);
-
- LIST_INSERT_HEAD(head, asp, path_l);
+ if (RB_INSERT(path_tree, &pathtable, asp) != NULL)
+ fatalx("%s: already linked object", __func__);
asp->flags |= F_ATTR_LINKED;
}
@@ -754,7 +665,7 @@ path_unlink(struct rde_aspath *asp)
if (asp->refcnt != 0)
fatalx("%s: still holds references", __func__);
- LIST_REMOVE(asp, path_l);
+ RB_REMOVE(path_tree, &pathtable, asp);
asp->flags &= ~F_ATTR_LINKED;
path_put(asp);
