improve the path hash function (instead of just hashing the aspath put

most other attrs into the hash as well). At the same time use the full
64 bit of SipHash in various places.
Tested by and OK benno@ phessler@

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);
 }