Add a symmetric toeplitz implementation, with integration for nics.

This is another bit of the puzzle for supporting multiple rx rings
and receive side scaling (RSS) on nics. It borrows heavily from
DragonflyBSD, but I've made some tweaks on the way.

The interesting bits that dfly came up with was a way to use Toeplitz
hashing so the kernel AND network interfaces hash packets so packets
in both directions onto the same bucket. The other interesting thing
is that the optimised the hash calculation by building a cache of
all the intermediate results possible for each input byte. Their
hash calculation is simply xoring these intermediate reults together.

So this diff adds an API for the kernel to use for calculating a
hash for ip addresses and ports, and adds a function for network
drivers to call that gives them a key to use with RSS. If all drivers
use the same key, then the same flows should be steered to the same
place when they enter the network stack regardless of which hardware
they came in on.

The changes I made relative to dfly are around reducing the size
of the caches. DragonflyBSD builds a cache of 32bit values, but
because of how the Toeplitz key is constructed, the 32bits are made
up of a repeated 16bit pattern. We can just store the 16 bits and
reconstruct the 32 bits if we want. Both us and dragonfly only
use 15 or 16 bits of the result anyway, so 32bits is unecessary.

Secondly, the dfly implementation keeps a cache of values for the
high and low bytes of input, but the values in the two caches are
almost the same. You can byteswap the values in one of the byte
caches to get the values for the other, but you can also just
byteswap values at runtime to get the same value, which is what
this implementation does. The result of both these changes is that
the byte cache is a quarter of the size of the one in dragonflybsd.

tb@ has had a close look at this and found a bunch of other
optimisations that can be implemented, and because he's a
wizard^Wmathematician he has proofs (and also did tests).

ok tb@ jmatthew@

2 files changed, 344 insertions, 0 deletions

diff --git a/sys/net/toeplitz.c b/sys/net/toeplitz.c
new file mode 100644
index 00000000000..0c07ccf2ea7
--- /dev/null
+++ b/sys/net/toeplitz.c
@@ -0,0 +1,231 @@
+/* $OpenBSD: toeplitz.c,v 1.1 2020/06/16 04:46:49 dlg Exp $ */
+
+/*
+ * Copyright (c) 2009 The DragonFly Project.  All rights reserved.
+ *
+ * This code is derived from software contributed to The DragonFly Project
+ * by Sepherosa Ziehau <sepherosa@gmail.com>
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in
+ *    the documentation and/or other materials provided with the
+ *    distribution.
+ * 3. Neither the name of The DragonFly Project nor the names of its
+ *    contributors may be used to endorse or promote products derived
+ *    from this software without specific, prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
+ * FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE
+ * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
+ * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
+ * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+ * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
+ * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+/*
+ * Copyright (c) 2019 David Gwynne <dlg@openbsd.org>
+ *
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+
+#include <sys/param.h>
+#include <sys/systm.h>
+#include <sys/kernel.h>
+#include <sys/sysctl.h>
+
+#include <netinet/in.h>
+
+#include <net/toeplitz.h>
+
+/*
+ * symmetric toeplitz
+ */
+
+static stoeplitz_key		stoeplitz_keyseed = STOEPLITZ_KEYSEED;
+static struct stoeplitz_cache	stoeplitz_syskey_cache;
+const struct stoeplitz_cache *const
+				stoeplitz_cache = &stoeplitz_syskey_cache; 
+
+void
+stoeplitz_init(void)
+{
+	stoeplitz_cache_init(&stoeplitz_syskey_cache, stoeplitz_keyseed);
+}
+
+#define NBSK (NBBY * sizeof(stoeplitz_key))
+
+void
+stoeplitz_cache_init(struct stoeplitz_cache *scache, stoeplitz_key skey)
+{
+	uint32_t key[NBBY];
+	unsigned int j, b, shift, val;
+
+	bzero(key, sizeof(key));
+
+	/*
+	 * Calculate 32bit keys for one byte; one key for each bit.
+	 */
+	for (b = 0; b < NBBY; ++b) {
+		for (j = 0; j < 32; ++j) {
+			unsigned int bit;
+
+			bit = b + j;
+
+			shift = NBSK - (bit % NBSK) - 1;
+			if (skey & (1 << shift))
+				key[b] |= 1 << (31 - j);
+		}
+	}
+
+	/*
+	 * Cache the results of all possible bit combination of
+	 * one byte.
+	 */
+	for (val = 0; val < 256; ++val) {
+		uint32_t res = 0;
+
+		for (b = 0; b < NBBY; ++b) {
+			shift = NBBY - b - 1;
+			if (val & (1 << shift))
+				res ^= key[b];
+		}
+		scache->bytes[val] = res;
+	}
+}
+
+uint16_t
+stoeplitz_hash_ip4(const struct stoeplitz_cache *scache,
+    in_addr_t faddr, in_addr_t laddr)
+{
+	uint16_t lo, hi;
+
+	lo  = stoeplitz_cache_entry(scache, faddr >> 0);
+	lo ^= stoeplitz_cache_entry(scache, faddr >> 16);
+	lo ^= stoeplitz_cache_entry(scache, laddr >> 0);
+	lo ^= stoeplitz_cache_entry(scache, laddr >> 16);
+
+	hi  = stoeplitz_cache_entry(scache, faddr >> 8);
+	hi ^= stoeplitz_cache_entry(scache, faddr >> 24);
+	hi ^= stoeplitz_cache_entry(scache, laddr >> 8);
+	hi ^= stoeplitz_cache_entry(scache, laddr >> 24);
+
+	return (swap16(lo) ^ hi);
+}
+
+uint16_t
+stoeplitz_hash_ip4port(const struct stoeplitz_cache *scache,
+    in_addr_t faddr, in_addr_t laddr, in_port_t fport, in_port_t lport)
+{
+	uint16_t hi, lo;
+
+	lo  = stoeplitz_cache_entry(scache, faddr >> 0);
+	lo ^= stoeplitz_cache_entry(scache, faddr >> 16);
+	lo ^= stoeplitz_cache_entry(scache, laddr >> 0);
+	lo ^= stoeplitz_cache_entry(scache, laddr >> 16);
+	lo ^= stoeplitz_cache_entry(scache, fport >> 0);
+	lo ^= stoeplitz_cache_entry(scache, lport >> 0);
+
+	hi  = stoeplitz_cache_entry(scache, faddr >> 8);
+	hi ^= stoeplitz_cache_entry(scache, faddr >> 24);
+	hi ^= stoeplitz_cache_entry(scache, laddr >> 8);
+	hi ^= stoeplitz_cache_entry(scache, laddr >> 24);
+	hi ^= stoeplitz_cache_entry(scache, fport >> 8);
+	hi ^= stoeplitz_cache_entry(scache, lport >> 8);
+
+	return (swap16(lo) ^ hi);
+}
+
+#ifdef INET6
+uint16_t
+stoeplitz_hash_ip6(const struct stoeplitz_cache *scache,
+    const struct in6_addr *faddr6, const struct in6_addr *laddr6)
+{
+	uint16_t hi = 0, lo = 0;
+	size_t i;
+
+	for (i = 0; i < nitems(faddr6->s6_addr32); i++) {
+		uint32_t faddr = faddr6->s6_addr32[i];
+		uint32_t laddr = laddr6->s6_addr32[i];
+
+		lo ^= stoeplitz_cache_entry(scache, faddr >> 0);
+		lo ^= stoeplitz_cache_entry(scache, faddr >> 16);
+		lo ^= stoeplitz_cache_entry(scache, laddr >> 0);
+		lo ^= stoeplitz_cache_entry(scache, laddr >> 16);
+
+		hi ^= stoeplitz_cache_entry(scache, faddr >> 8);
+		hi ^= stoeplitz_cache_entry(scache, faddr >> 24);
+		hi ^= stoeplitz_cache_entry(scache, laddr >> 8);
+		hi ^= stoeplitz_cache_entry(scache, laddr >> 24);
+	}
+
+	return (swap16(lo) ^ hi);
+}
+
+uint16_t
+stoeplitz_hash_ip6port(const struct stoeplitz_cache *scache,
+    const struct in6_addr *faddr6, const struct in6_addr * laddr6,
+    in_port_t fport, in_port_t lport)
+{
+	uint16_t hi = 0, lo = 0;
+	size_t i;
+
+	for (i = 0; i < nitems(faddr6->s6_addr32); i++) {
+		uint32_t faddr = faddr6->s6_addr32[i];
+		uint32_t laddr = laddr6->s6_addr32[i];
+
+		lo ^= stoeplitz_cache_entry(scache, faddr >> 0);
+		lo ^= stoeplitz_cache_entry(scache, faddr >> 16);
+		lo ^= stoeplitz_cache_entry(scache, laddr >> 0);
+		lo ^= stoeplitz_cache_entry(scache, laddr >> 16);
+
+		hi ^= stoeplitz_cache_entry(scache, faddr >> 8);
+		hi ^= stoeplitz_cache_entry(scache, faddr >> 24);
+		hi ^= stoeplitz_cache_entry(scache, laddr >> 8);
+		hi ^= stoeplitz_cache_entry(scache, laddr >> 24);
+	}
+
+	lo ^= stoeplitz_cache_entry(scache, fport >> 0);
+	lo ^= stoeplitz_cache_entry(scache, lport >> 0);
+
+	hi ^= stoeplitz_cache_entry(scache, fport >> 8);
+	hi ^= stoeplitz_cache_entry(scache, lport >> 8);
+
+	return (swap16(lo) ^ hi);
+}
+#endif /* INET6 */
+
+void
+stoeplitz_to_key(uint8_t *k, size_t klen)
+{
+	uint16_t skey = htons(stoeplitz_keyseed);
+	size_t i;
+
+	KASSERT((klen % 2) == 0);
+
+	for (i = 0; i < klen; i += sizeof(skey)) {
+		k[i + 0] = skey >> 8;
+		k[i + 1] = skey;
+	}
+}
diff --git a/sys/net/toeplitz.h b/sys/net/toeplitz.h
new file mode 100644
index 00000000000..52ccfa4e611
--- /dev/null
+++ b/sys/net/toeplitz.h
@@ -0,0 +1,113 @@
+/*	$OpenBSD: toeplitz.h,v 1.1 2020/06/16 04:46:49 dlg Exp $ */
+
+/*
+ * Copyright (c) 2019 David Gwynne <dlg@openbsd.org>
+ *
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+
+#ifndef _SYS_NET_TOEPLITZ_H_
+#define _SYS_NET_TOEPLITZ_H_
+
+#include <sys/endian.h>
+
+/*
+ * symmetric toeplitz
+ */
+
+typedef uint16_t stoeplitz_key;
+
+struct stoeplitz_cache {
+	uint16_t	bytes[256];
+};
+
+static __unused inline uint16_t
+stoeplitz_cache_entry(const struct stoeplitz_cache *scache, uint8_t byte)
+{
+	return (scache->bytes[byte]);
+}
+
+void		stoeplitz_cache_init(struct stoeplitz_cache *, stoeplitz_key);
+
+uint16_t	stoeplitz_hash_ip4(const struct stoeplitz_cache *,
+		    uint32_t, uint32_t);
+uint16_t	stoeplitz_hash_ip4port(const struct stoeplitz_cache *,
+		    uint32_t, uint32_t, uint16_t, uint16_t);
+
+#ifdef INET6
+struct in6_addr;
+uint16_t	stoeplitz_hash_ip6(const struct stoeplitz_cache *,
+		    const struct in6_addr *, const struct in6_addr *);
+uint16_t	stoeplitz_hash_ip6port(const struct stoeplitz_cache *,
+		    const struct in6_addr *, const struct in6_addr *,
+		    uint16_t, uint16_t);
+#endif
+
+/* hash a uint16_t in network byte order */
+static __unused inline uint16_t
+stoeplitz_hash_n16(const struct stoeplitz_cache *scache, uint16_t n16)
+{
+	uint16_t hi, lo;
+
+	hi = stoeplitz_cache_entry(scache, n16 >> 8);
+	lo = stoeplitz_cache_entry(scache, n16);
+
+	return (hi ^ swap16(lo));
+}
+
+/* hash a uint16_t in host byte order */
+static __unused inline uint16_t
+stoeplitz_hash_h16(const struct stoeplitz_cache *scache, uint16_t h16)
+{
+	uint16_t lo, hi;
+
+	lo = stoeplitz_cache_entry(scache, h16);
+	hi = stoeplitz_cache_entry(scache, h16 >> 8);
+
+#if _BYTE_ORDER == _BIG_ENDIAN
+	return (hi ^ swap16(lo));
+#else
+	return (swap16(hi) ^ lo);
+#endif
+}
+
+/*
+ * system provided symmetric toeplitz
+ */
+
+#define STOEPLITZ_KEYSEED	0x6d5a
+
+void		stoeplitz_init(void);
+
+void		stoeplitz_to_key(uint8_t *, size_t)
+		    __bounded((__buffer__, 1, 2));
+
+extern const struct stoeplitz_cache *const stoeplitz_cache;
+
+#define	stoeplitz_n16(_n16) \
+	stoeplitz_cache_n16(stoeplitz_cache, (_n16))
+#define stoeplitz_h16(_h16) \
+	stoeplitz_cache_h16(stoeplitz_cache, (_h16))
+#define stoeplitz_port(_p)	stoeplitz_n16((_p))
+#define stoeplitz_ip4(_sa4, _da4) \
+	stoeplitz_hash_ip4(stoeplitz_cache, (_sa4), (_da4))
+#define stoeplitz_ip4port(_sa4, _da4, _sp, _dp) \
+	stoeplitz_hash_ip4port(stoeplitz_cache, (_sa4), (_da4), (_sp), (_dp))
+#ifdef INET6
+#define stoeplitz_ip6(_sa6, _da6) \
+	stoeplitz_hash_ip6(stoeplitz_cache, (_sa6), (_da6))
+#define stoeplitz_ip6port(_sa6, _da6, _sp, _dp) \
+	stoeplitz_hash_ip6port(stoeplitz_cache, (_sa6), (_da6), (_sp), (_dp))
+#endif
+
+#endif /* _SYS_NET_TOEPLITZ_H_ */