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_ */