summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--usr.sbin/bgpd/rde.h13
-rw-r--r--usr.sbin/bgpd/rde_attr.c19
-rw-r--r--usr.sbin/bgpd/rde_rib.c58
3 files changed, 62 insertions, 28 deletions
diff --git a/usr.sbin/bgpd/rde.h b/usr.sbin/bgpd/rde.h
index 80dd6005336..54e6395f0a0 100644
--- a/usr.sbin/bgpd/rde.h
+++ b/usr.sbin/bgpd/rde.h
@@ -1,4 +1,4 @@
-/* $OpenBSD: rde.h,v 1.177 2018/07/11 16:34:36 claudio Exp $ */
+/* $OpenBSD: rde.h,v 1.178 2018/07/11 19:05:41 claudio Exp $ */
/*
* Copyright (c) 2003, 2004 Claudio Jeker <claudio@openbsd.org> and
@@ -140,8 +140,8 @@ enum attrtypes {
struct attr {
LIST_ENTRY(attr) entry;
u_char *data;
+ u_int64_t hash;
int refcnt;
- u_int32_t hash;
u_int16_t len;
u_int8_t flags;
u_int8_t type;
@@ -154,11 +154,6 @@ struct mpattr {
u_int16_t unreach_len;
};
-struct path_table {
- struct aspath_head *path_hashtbl;
- u_int32_t path_hashmask;
-};
-
#define F_ATTR_ORIGIN 0x00001
#define F_ATTR_ASPATH 0x00002
#define F_ATTR_NEXTHOP 0x00004
@@ -195,10 +190,11 @@ struct rde_aspath {
struct rde_peer *peer;
struct aspath *aspath;
struct nexthop *nexthop; /* may be NULL */
+ u_int64_t hash;
+ u_int32_t flags; /* internally used */
u_int32_t med; /* multi exit disc */
u_int32_t lpref; /* local pref */
u_int32_t weight; /* low prio lpref */
- u_int32_t flags; /* internally used */
u_int16_t rtlabelid; /* route label id */
u_int16_t pftableid; /* pf table id */
u_int8_t origin;
@@ -358,6 +354,7 @@ int attr_optadd(struct rde_aspath *, u_int8_t, u_int8_t,
struct attr *attr_optget(const struct rde_aspath *, u_int8_t);
void attr_copy(struct rde_aspath *, const struct rde_aspath *);
int attr_compare(struct rde_aspath *, struct rde_aspath *);
+u_int64_t attr_hash(struct rde_aspath *);
void attr_freeall(struct rde_aspath *);
void attr_free(struct rde_aspath *, struct attr *);
#define attr_optlen(x) \
diff --git a/usr.sbin/bgpd/rde_attr.c b/usr.sbin/bgpd/rde_attr.c
index a806ce83537..a78bdaddb6c 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.103 2018/07/11 16:34:36 claudio Exp $ */
+/* $OpenBSD: rde_attr.c,v 1.104 2018/07/11 19:05:41 claudio Exp $ */
/*
* Copyright (c) 2004 Claudio Jeker <claudio@openbsd.org>
@@ -99,7 +99,7 @@ void attr_put(struct attr *);
struct attr_table {
struct attr_list *hashtbl;
- u_int32_t hashmask;
+ u_int64_t hashmask;
} attrtable;
SIPHASH_KEY attrtablekey;
@@ -287,7 +287,6 @@ attr_diff(struct attr *oa, struct attr *ob)
return (-1);
fatalx("attr_diff: equal attributes encountered");
- return (0);
}
int
@@ -313,6 +312,18 @@ attr_compare(struct rde_aspath *a, struct rde_aspath *b)
return (0);
}
+u_int64_t
+attr_hash(struct rde_aspath *a)
+{
+ u_int64_t hash = 0;
+ u_int8_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)
{
@@ -384,7 +395,7 @@ attr_lookup(u_int8_t flags, u_int8_t type, const void *data, u_int16_t len)
{
struct attr_list *head;
struct attr *a;
- u_int32_t hash;
+ u_int64_t hash;
SIPHASH_CTX ctx;
flags &= ~ATTR_DEFMASK; /* normalize mask */
diff --git a/usr.sbin/bgpd/rde_rib.c b/usr.sbin/bgpd/rde_rib.c
index 54c6fcc029b..1ccd70c33b0 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.169 2018/07/11 16:34:36 claudio Exp $ */
+/* $OpenBSD: rde_rib.c,v 1.170 2018/07/11 19:05:41 claudio Exp $ */
/*
* Copyright (c) 2003, 2004 Claudio Jeker <claudio@openbsd.org>
@@ -348,17 +348,17 @@ rib_restart(struct rib_context *ctx)
/* path specific functions */
static struct rde_aspath *path_lookup(struct rde_aspath *, struct rde_peer *);
-static void path_link(struct rde_aspath *, struct rde_peer *);
+static u_int64_t path_hash(struct rde_aspath *);
+static void path_link(struct rde_aspath *, struct rde_peer *);
-struct path_table pathtable;
+struct path_table {
+ struct aspath_head *path_hashtbl;
+ u_int64_t path_hashmask;
+} pathtable;
SIPHASH_KEY pathtablekey;
-/* XXX the hash should also include communities and the other attrs */
-#define PATH_HASH(x) \
- &pathtable.path_hashtbl[x == NULL ? 0 : \
- SipHash24(&pathtablekey, (x)->data, (x)->len) & \
- pathtable.path_hashmask]
+#define PATH_HASH(x) &pathtable.path_hashtbl[x & pathtable.path_hashmask]
void
path_init(u_int32_t hashsize)
@@ -511,16 +511,42 @@ path_compare(struct rde_aspath *a, struct rde_aspath *b)
return (attr_compare(a, b));
}
+static u_int64_t
+path_hash(struct rde_aspath *asp)
+{
+ SIPHASH_CTX ctx;
+ u_int64_t hash;
+
+ SipHash24_Init(&ctx, &pathtablekey);
+ SipHash24_Update(&ctx, &asp->origin, sizeof(asp->origin));
+ SipHash24_Update(&ctx, &asp->med, sizeof(asp->med));
+ SipHash24_Update(&ctx, &asp->lpref, sizeof(asp->lpref));
+ SipHash24_Update(&ctx, &asp->weight, sizeof(asp->weight));
+ SipHash24_Update(&ctx, &asp->rtlabelid, sizeof(asp->rtlabelid));
+ SipHash24_Update(&ctx, &asp->pftableid, sizeof(asp->pftableid));
+
+ if (asp->aspath)
+ SipHash24_Update(&ctx, asp->aspath->data, asp->aspath->len);
+
+ hash = attr_hash(asp);
+ SipHash24_Update(&ctx, &hash, sizeof(hash));
+
+ return (SipHash24_End(&ctx));
+}
+
static struct rde_aspath *
path_lookup(struct rde_aspath *aspath, struct rde_peer *peer)
{
struct aspath_head *head;
struct rde_aspath *asp;
+ u_int64_t hash;
- head = PATH_HASH(aspath->aspath);
+ hash = path_hash(aspath);
+ head = PATH_HASH(hash);
LIST_FOREACH(asp, head, path_l) {
- if (peer == asp->peer && path_compare(aspath, asp) == 0)
+ if (asp->hash == hash && peer == asp->peer &&
+ path_compare(aspath, asp) == 0)
return (asp);
}
return (NULL);
@@ -654,11 +680,13 @@ path_link(struct rde_aspath *asp, struct rde_peer *peer)
{
struct aspath_head *head;
- head = PATH_HASH(asp->aspath);
+ asp->peer = peer;
+
+ asp->hash = path_hash(asp);
+ head = PATH_HASH(asp->hash);
LIST_INSERT_HEAD(head, asp, path_l);
- TAILQ_INSERT_TAIL(&peer->path_h, asp, peer_l);
- asp->peer = peer;
+ TAILQ_INSERT_HEAD(&peer->path_h, asp, peer_l);
nexthop_link(asp);
asp->flags |= F_ATTR_LINKED;
}
@@ -676,6 +704,7 @@ path_copy(struct rde_aspath *dst, const struct rde_aspath *src)
rdemem.aspath_refs++;
}
dst->nexthop = nexthop_ref(src->nexthop);
+ dst->hash = 0;
dst->med = src->med;
dst->lpref = src->lpref;
dst->weight = src->weight;
@@ -698,9 +727,6 @@ path_prep(struct rde_aspath *asp)
TAILQ_INIT(&asp->updates);
asp->origin = ORIGIN_INCOMPLETE;
asp->lpref = DEFAULT_LPREF;
- /* med = 0 */
- /* weight = 0 */
- /* rtlabel = 0 */
return (asp);
}
generated by cgit v1.2.3 (git 2.25.1) at 2024-12-26 03:50:14 +0000