On Mon, Dec 08, 2014 at 18:58, Ted Unangst wrote:
> bgpd seemed like a good place to try out the new siphash functions.
>
> Three hash tables are pretty straight forward conversions. Diff below.
Done.
> rde_rib.c nexthop_hash uses hash32 for ipv6, and a simple xor hash for
> ipv4. I left that alone as the diff would be more than mechanical.
>
> red_update.c up_generate also uses hash32 to generate a "hint" for the
> RB tree. I left that alone as well.
Now for these two. Convert nexthop_hash to actually hash the ip4
address. Probably an improvement. Am I missing a reason why this would
need to be deterministic?
The rb tree hint probably doesn't matter as much, but for the sake of
consistency, I think it's best.
Index: rde_rib.c
===================================================================
RCS file: /cvs/src/usr.sbin/bgpd/rde_rib.c,v
retrieving revision 1.140
diff -u -p -r1.140 rde_rib.c
--- rde_rib.c 12 Dec 2014 18:15:51 -0000 1.140
+++ rde_rib.c 12 Dec 2014 20:12:01 -0000
@@ -18,7 +18,6 @@
#include <sys/types.h>
#include <sys/queue.h>
-#include <sys/hash.h>
#include <stdlib.h>
#include <string.h>
@@ -1065,6 +1064,8 @@ struct nexthop_table {
u_int32_t nexthop_hashmask;
} nexthoptable;
+SIPHASH_KEY nexthoptablekey;
+
void
nexthop_init(u_int32_t hashsize)
{
@@ -1078,6 +1079,7 @@ nexthop_init(u_int32_t hashsize)
for (i = 0; i < hs; i++)
LIST_INIT(&nexthoptable.nexthop_hashtbl[i]);
+ arc4random_buf(&nexthoptablekey, sizeof(nexthoptablekey));
nexthoptable.nexthop_hashmask = hs - 1;
}
@@ -1308,17 +1310,16 @@ nexthop_hash(struct bgpd_addr *nexthop)
switch (nexthop->aid) {
case AID_INET:
- h = (AF_INET ^ ntohl(nexthop->v4.s_addr) ^
- ntohl(nexthop->v4.s_addr) >> 13) &
- nexthoptable.nexthop_hashmask;
+ h = SipHash24(&nexthoptablekey, &nexthop->v4.s_addr,
+ sizeof(nexthop->v4.s_addr));
break;
case AID_INET6:
- h = hash32_buf(&nexthop->v6, sizeof(struct in6_addr),
- HASHINIT) & nexthoptable.nexthop_hashmask;
+ h = SipHash24(&nexthoptablekey, &nexthop->v6,
+ sizeof(struct in6_addr));
break;
default:
fatalx("nexthop_hash: unsupported AF");
}
- return (&nexthoptable.nexthop_hashtbl[h]);
+ return (&nexthoptable.nexthop_hashtbl[h &
nexthoptable.nexthop_hashmask]);
}
Index: rde_update.c
===================================================================
RCS file: /cvs/src/usr.sbin/bgpd/rde_update.c,v
retrieving revision 1.81
diff -u -p -r1.81 rde_update.c
--- rde_update.c 14 Aug 2013 20:34:27 -0000 1.81
+++ rde_update.c 12 Dec 2014 20:17:19 -0000
@@ -17,11 +17,11 @@
*/
#include <sys/types.h>
#include <sys/queue.h>
-#include <sys/hash.h>
#include <limits.h>
#include <stdlib.h>
#include <string.h>
+#include <siphash.h>
#include "bgpd.h"
#include "rde.h"
@@ -63,6 +63,8 @@ RB_GENERATE(uptree_prefix, update_prefix
RB_PROTOTYPE(uptree_attr, update_attr, entry, up_attr_cmp)
RB_GENERATE(uptree_attr, update_attr, entry, up_attr_cmp)
+SIPHASH_KEY uptree_key;
+
void
up_init(struct rde_peer *peer)
{
@@ -78,6 +80,7 @@ up_init(struct rde_peer *peer)
peer->up_acnt = 0;
peer->up_nlricnt = 0;
peer->up_wcnt = 0;
+ arc4random_buf(&uptree_key, sizeof(uptree_key));
}
void
@@ -363,6 +366,7 @@ up_generate(struct rde_peer *peer, struc
{
struct update_attr *ua = NULL;
struct update_prefix *up;
+ SIPHASH_CTX ctx;
if (asp) {
ua = calloc(1, sizeof(struct update_attr));
@@ -378,10 +382,11 @@ up_generate(struct rde_peer *peer, struc
* use aspath_hash as attr_hash, this may be unoptimal
* but currently I don't care.
*/
- ua->attr_hash = hash32_buf(ua->attr, ua->attr_len, HASHINIT);
+ SipHash24_Init(&ctx, &uptree_key);
+ SipHash24_Update(&ctx, ua->attr, ua->attr_len);
if (ua->mpattr)
- ua->attr_hash = hash32_buf(ua->mpattr, ua->mpattr_len,
- ua->attr_hash);
+ SipHash24_Update(&ctx, ua->mpattr, ua->mpattr_len);
+ ua->attr_hash = SipHash24_End(&ctx);
}
up = calloc(1, sizeof(struct update_prefix));
