Module Name: src
Committed By: jmcneill
Date: Sat Jan 30 21:23:08 UTC 2021
Modified Files:
src/sys/net: files.net
Added Files:
src/sys/net: toeplitz.c toeplitz.h
Log Message:
Add symmetric toeplitz implementation with integration for NICs, from OpenBSD.
To generate a diff of this commit:
cvs rdiff -u -r1.29 -r1.30 src/sys/net/files.net
cvs rdiff -u -r0 -r1.1 src/sys/net/toeplitz.c src/sys/net/toeplitz.h
Please note that diffs are not public domain; they are subject to the
copyright notices on the relevant files.
Modified files:
Index: src/sys/net/files.net
diff -u src/sys/net/files.net:1.29 src/sys/net/files.net:1.30
--- src/sys/net/files.net:1.29 Sun Sep 27 13:31:04 2020
+++ src/sys/net/files.net Sat Jan 30 21:23:08 2021
@@ -1,4 +1,4 @@
-# $NetBSD: files.net,v 1.29 2020/09/27 13:31:04 roy Exp $
+# $NetBSD: files.net,v 1.30 2021/01/30 21:23:08 jmcneill Exp $
# XXX CLEANUP
define net
@@ -49,6 +49,7 @@ file net/rss_config.c net
file net/rtbl.c net
file net/rtsock.c net
file net/slcompress.c sl | ppp | (irip & irip_vj)
+file net/toeplitz.c toeplitz
file net/zlib.c (ppp & ppp_deflate) | swcrypto | vnd_compression
file netinet/accf_data.c accf_data
file netinet/accf_http.c accf_http
Added files:
Index: src/sys/net/toeplitz.c
diff -u /dev/null src/sys/net/toeplitz.c:1.1
--- /dev/null Sat Jan 30 21:23:08 2021
+++ src/sys/net/toeplitz.c Sat Jan 30 21:23:08 2021
@@ -0,0 +1,204 @@
+/* $OpenBSD: toeplitz.c,v 1.9 2020/09/01 19:18:26 tb Exp $ */
+
+/*
+ * Copyright (c) 2009 The DragonFly Project. All rights reserved.
+ *
+ * This code is derived from software contributed to The DragonFly Project
+ * by Sepherosa Ziehau <sepher...@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 <d...@openbsd.org>
+ * Copyright (c) 2020 Theo Buehler <t...@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 <sys/cprng.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;
+
+/* parity of n16: count (mod 2) of ones in the binary representation. */
+static int
+parity(uint16_t n16)
+{
+ n16 = ((n16 & 0xaaaa) >> 1) ^ (n16 & 0x5555);
+ n16 = ((n16 & 0xcccc) >> 2) ^ (n16 & 0x3333);
+ n16 = ((n16 & 0xf0f0) >> 4) ^ (n16 & 0x0f0f);
+ n16 = ((n16 & 0xff00) >> 8) ^ (n16 & 0x00ff);
+
+ return (n16);
+}
+
+/*
+ * The Toeplitz matrix obtained from a seed is invertible if and only if the
+ * parity of the seed is 1. Generate such a seed uniformly at random.
+ */
+static stoeplitz_key
+stoeplitz_random_seed(void)
+{
+ stoeplitz_key seed;
+
+ seed = cprng_strong32() & UINT16_MAX;
+ if (parity(seed) == 0)
+ seed ^= 1;
+
+ return (seed);
+}
+
+void
+stoeplitz_init(void)
+{
+ stoeplitz_keyseed = stoeplitz_random_seed();
+ stoeplitz_cache_init(&stoeplitz_syskey_cache, stoeplitz_keyseed);
+}
+
+#define NBSK (NBBY * sizeof(stoeplitz_key))
+
+/*
+ * The Toeplitz hash of a 16-bit number considered as a column vector over
+ * the field with two elements is calculated as a matrix multiplication with
+ * a 16x16 circulant Toeplitz matrix T generated by skey.
+ *
+ * The first eight columns H of T generate the remaining eight columns using
+ * the byteswap operation J = swap16: T = [H JH]. Thus, the Toeplitz hash of
+ * n = [hi lo] is computed via the formula T * n = (H * hi) ^ swap16(H * lo).
+ *
+ * Therefore the results H * val for all values of a byte are cached in scache.
+ */
+void
+stoeplitz_cache_init(struct stoeplitz_cache *scache, stoeplitz_key skey)
+{
+ uint16_t column[NBBY];
+ unsigned int b, shift, val;
+
+ bzero(column, sizeof(column));
+
+ /* Calculate the first eight columns H of the Toeplitz matrix T. */
+ for (b = 0; b < NBBY; ++b)
+ column[b] = skey << b | skey >> (NBSK - b);
+
+ /* Cache the results of H * val for all possible values of a byte. */
+ for (val = 0; val < 256; ++val) {
+ uint16_t res = 0;
+
+ for (b = 0; b < NBBY; ++b) {
+ shift = NBBY - b - 1;
+ if (val & (1 << shift))
+ res ^= column[b];
+ }
+ scache->bytes[val] = res;
+ }
+}
+
+uint16_t
+stoeplitz_hash_ip4(const struct stoeplitz_cache *scache,
+ in_addr_t faddr, in_addr_t laddr)
+{
+ return (stoeplitz_hash_n32(scache, faddr ^ laddr));
+}
+
+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)
+{
+ return (stoeplitz_hash_n32(scache, faddr ^ laddr ^ fport ^ lport));
+}
+
+#ifdef INET6
+uint16_t
+stoeplitz_hash_ip6(const struct stoeplitz_cache *scache,
+ const struct in6_addr *faddr6, const struct in6_addr *laddr6)
+{
+ uint32_t n32 = 0;
+ size_t i;
+
+ for (i = 0; i < nitems(faddr6->s6_addr32); i++)
+ n32 ^= faddr6->s6_addr32[i] ^ laddr6->s6_addr32[i];
+
+ return (stoeplitz_hash_n32(scache, n32));
+}
+
+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)
+{
+ uint32_t n32 = 0;
+ size_t i;
+
+ for (i = 0; i < nitems(faddr6->s6_addr32); i++)
+ n32 ^= faddr6->s6_addr32[i] ^ laddr6->s6_addr32[i];
+
+ n32 ^= fport ^ lport;
+
+ return (stoeplitz_hash_n32(scache, n32));
+}
+#endif /* INET6 */
+
+void
+stoeplitz_to_key(void *key, size_t klen)
+{
+ uint8_t *k = key;
+ 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;
+ }
+}
Index: src/sys/net/toeplitz.h
diff -u /dev/null src/sys/net/toeplitz.h:1.1
--- /dev/null Sat Jan 30 21:23:08 2021
+++ src/sys/net/toeplitz.h Sat Jan 30 21:23:08 2021
@@ -0,0 +1,119 @@
+/* $OpenBSD: toeplitz.h,v 1.3 2020/06/19 08:48:15 dlg Exp $ */
+
+/*
+ * Copyright (c) 2019 David Gwynne <d...@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 ^ bswap16(lo));
+}
+
+/* hash a uint32_t in network byte order */
+static __unused inline uint16_t
+stoeplitz_hash_n32(const struct stoeplitz_cache *scache, uint32_t n32)
+{
+ return (stoeplitz_hash_n16(scache, n32 ^ (n32 >> 16)));
+}
+
+/* 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 ^ bswap16(lo));
+#else
+ return (bswap16(hi) ^ lo);
+#endif
+}
+
+/*
+ * system provided symmetric toeplitz
+ */
+
+#define STOEPLITZ_KEYSEED 0x6d5a
+
+void stoeplitz_init(void);
+
+void stoeplitz_to_key(void *, size_t);
+
+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_ */
