Lib: Improve IP/net hashing

Backport some changes from branch oz-parametric-hashes. Replace naive
hash function for IPv6 addresses, fix hashing of VPNx (where upper half
of RD was ignored), fix hashing of MPLS labels (where identity was used).

3 files changed, 75 insertions, 17 deletions

diff --git a/lib/birdlib.h b/lib/birdlib.h
index e03bd0b2..b7226411 100644
--- a/lib/birdlib.h
+++ b/lib/birdlib.h
@@ -162,6 +162,7 @@ void bug(const char *msg, ...) NORET;
 void debug(const char *msg, ...);	/* Printf to debug output */
 void debug_safe(const char *msg);	/* Printf to debug output, async-safe */
 
+
 /* Debugging */
 
 #if defined(LOCAL_DEBUG) || defined(GLOBAL_DEBUG)
@@ -196,10 +197,36 @@ asm(
    );
 #endif
 
+
 /* Pseudorandom numbers */
 
 u32 random_u32(void);
 void random_init(void);
 void random_bytes(void *buf, size_t size);
 
+
+/* Hashing */
+
+/* Constant parameter for non-parametrized hashes */
+#define HASH_PARAM 2902958171u
+
+/* Precomputed powers of HASH_PARAM */
+#define HASH_PARAM1 ((u64) HASH_PARAM)
+#define HASH_PARAM2 (HASH_PARAM1 * HASH_PARAM)
+#define HASH_PARAM3 (HASH_PARAM2 * HASH_PARAM)
+#define HASH_PARAM4 (HASH_PARAM3 * HASH_PARAM)
+
+/* Reduce intermediate 64-bit value to final 32-bit value */
+static inline u32 hash_value(u64 a)
+{ return ((u32) a) ^ ((u32) (a >> 32)); }
+
+static inline u64 u32_hash0(u32 v, u32 p, u64 acc)
+{ return (acc + v) * p; }
+
+static inline u64 u64_hash0(u64 v, u32 p, u64 acc)
+{ return u32_hash0(v >> 32, p, u32_hash0(v, p, acc)); }
+
+static inline u32 u64_hash(u64 v)
+{ return hash_value(u64_hash0(v, HASH_PARAM, 0)); }
+
 #endif
diff --git a/lib/ip.h b/lib/ip.h
index 9eef2e16..0e232f97 100644
--- a/lib/ip.h
+++ b/lib/ip.h
@@ -194,14 +194,37 @@ static inline int ipa_nonzero2(ip_addr a)
  *	Hash and compare functions
  */
 
+static inline u64 ip4_hash0(ip4_addr a, u32 p, u64 acc)
+{ return (acc + _I(a)) * p; }
+
 static inline u32 ip4_hash(ip4_addr a)
-{ return u32_hash(_I(a)); }
+{
+  // return hash_value(ip4_hash0(a, HASH_PARAM, 0));
+
+  /* For some reason, the old hash works slightly better */
+  return u32_hash(_I(a));
+}
+
+static inline u64 ip6_hash0(ip6_addr a, u32 p, u64 acc)
+{
+  acc += _I0(a); acc *= p;
+  acc += _I1(a); acc *= p;
+  acc += _I2(a); acc *= p;
+  acc += _I3(a); acc *= p;
+  return acc;
+}
 
 static inline u32 ip6_hash(ip6_addr a)
 {
-  /* Returns a 32-bit hash key, although low-order bits are not mixed */
-  u32 x = _I0(a) ^ _I1(a) ^ _I2(a) ^ _I3(a);
-  return x ^ (x << 16) ^ (x << 24);
+  // return hash_value(ip6_hash0(a, HASH_PARAM, 0));
+
+  /* Just use the expanded form */
+  u64 acc =
+    _I0(a) * HASH_PARAM4 +
+    _I1(a) * HASH_PARAM3 +
+    _I2(a) * HASH_PARAM2 +
+    _I3(a) * HASH_PARAM1;
+  return hash_value(acc);
 }
 
 static inline int ip4_compare(ip4_addr a, ip4_addr b)
diff --git a/lib/net.h b/lib/net.h
index da7254c2..e9828557 100644
--- a/lib/net.h
+++ b/lib/net.h
@@ -479,39 +479,47 @@ static inline void net_copy_mpls(net_addr_mpls *dst, const net_addr_mpls *src)
 { memcpy(dst, src, sizeof(net_addr_mpls)); }
 
 
-/* XXXX */
-static inline u32 u64_hash(u64 a)
-{ return u32_hash(a); }
+static inline u32 px4_hash(ip4_addr prefix, u32 pxlen)
+{ return ip4_hash(prefix) ^ (pxlen << 26); }
+
+static inline u32 px6_hash(ip6_addr prefix, u32 pxlen)
+{ return ip6_hash(prefix) ^ (pxlen << 26); }
 
 static inline u32 net_hash_ip4(const net_addr_ip4 *n)
-{ return ip4_hash(n->prefix) ^ ((u32) n->pxlen << 26); }
+{ return px4_hash(n->prefix, n->pxlen); }
 
 static inline u32 net_hash_ip6(const net_addr_ip6 *n)
-{ return ip6_hash(n->prefix) ^ ((u32) n->pxlen << 26); }
+{ return px6_hash(n->prefix, n->pxlen); }
 
 static inline u32 net_hash_vpn4(const net_addr_vpn4 *n)
-{ return ip4_hash(n->prefix) ^ ((u32) n->pxlen << 26) ^ u64_hash(n->rd); }
+{
+  u64 acc = ip4_hash0(n->prefix, HASH_PARAM, 0) ^ (n->pxlen << 26);
+  return hash_value(u64_hash0(n->rd, HASH_PARAM, acc));
+}
 
 static inline u32 net_hash_vpn6(const net_addr_vpn6 *n)
-{ return ip6_hash(n->prefix) ^ ((u32) n->pxlen << 26) ^ u64_hash(n->rd); }
+{
+  u64 acc = ip6_hash0(n->prefix, HASH_PARAM, 0) ^ (n->pxlen << 26);
+  return hash_value(u64_hash0(n->rd, HASH_PARAM, acc));
+}
 
 static inline u32 net_hash_roa4(const net_addr_roa4 *n)
-{ return ip4_hash(n->prefix) ^ ((u32) n->pxlen << 26); }
+{ return px4_hash(n->prefix, n->pxlen); }
 
 static inline u32 net_hash_roa6(const net_addr_roa6 *n)
-{ return ip6_hash(n->prefix) ^ ((u32) n->pxlen << 26); }
+{ return px6_hash(n->prefix, n->pxlen); }
 
 static inline u32 net_hash_flow4(const net_addr_flow4 *n)
-{ return ip4_hash(n->prefix) ^ ((u32) n->pxlen << 26); }
+{ return px4_hash(n->prefix, n->pxlen); }
 
 static inline u32 net_hash_flow6(const net_addr_flow6 *n)
-{ return ip6_hash(n->prefix) ^ ((u32) n->pxlen << 26); }
+{ return px6_hash(n->prefix, n->pxlen); }
 
 static inline u32 net_hash_ip6_sadr(const net_addr_ip6_sadr *n)
-{ return net_hash_ip6((net_addr_ip6 *) n); }
+{ return px6_hash(n->dst_prefix, n->dst_pxlen); }
 
 static inline u32 net_hash_mpls(const net_addr_mpls *n)
-{ return n->label; }
+{ return u32_hash(n->label); }
 
 u32 net_hash(const net_addr *a);