[PATCH 00/10] siphash: cleanups and fixes
While working on unifying the hashing for the flow table, I noticed some awkwardness in the siphash functions. While looking into that I noticed some bugs. So.. here we are. David Gibson (10): siphash: Make siphash functions consistently return 64-bit results siphash: Make sip round calculations an inline function rather than macro siphash: Add siphash_feed() helper siphash: Clean up hash finalisation with posthash_final() function siphash: Fix bug in state initialisation siphash: Use more hygienic state initialiser siphash: Use specific structure for internal state siphash: Make internal helpers public siphash, checksum: Move TBAA explanation to checksum.c siphash: Use incremental rather than all-at-once siphash functions Makefile | 2 +- checksum.c | 19 ++-- inany.h | 16 +++- siphash.c | 243 --------------------------------------------------- siphash.h | 119 +++++++++++++++++++++++-- tcp.c | 37 +++----- tcp_splice.c | 1 + 7 files changed, 158 insertions(+), 279 deletions(-) delete mode 100644 siphash.c -- 2.41.0
Some of the siphas_*b() functions return 64-bit results, others 32-bit
results, with no obvious pattern. siphash_32b() also appears to do this
incorrectly - taking the 64-bit hash value and simply returning it
truncated, rather than folding the two halves together.
Since SipHash proper is defined to give a 64-bit hash, make all of them
return 64-bit results. In the one caller which needs a 32-bit value,
tcp_seq_init() do the fold down to 32-bits ourselves.
Signed-off-by: David Gibson
The SIPROUND(n) macro implements n rounds of SipHash shuffling. It relies
on 'v' and '__i' variables being available in the context it's used in
which isn't great hygeine. Replace it with an inline function instead.
Signed-off-by: David Gibson
We have macros or inlines for a number of common operations in the siphash
functions. However, in a number of places we still open code feeding
another 64-bits of data into the hash function: an xor, followed by 2
rounds of shuffling, followed by another xor.
Implement an inline function for this, which results in somewhat shortened
code.
Signed-off-by: David Gibson
The POSTAMBLE macro implements the finalisation steps of SipHash. It
relies on some variables in the environment, including returning the final
hash value that way. That isn't great hygeine.
In addition the PREAMBLE macro takes a length parameter which is used only
to initialize the 'b' value that's not used until the finalisation and is
also sometimes modified in a non-obvious way by the callers.
The 'b' value is always composed from the total length of the hash input
plus up to 7 bytes of "tail" data - that is the remainder of the hash input
after a multiple of 8 bytes has been consumed.
Simplify all this by replacing the POSTAMBLE macro with a siphash_final()
function which takes the length and tail data as parameters and returns the
final hash value.
Signed-off-by: David Gibson
The SipHash algorithm starts with initializing the 32 bytes of internal
state with some magic numbers XORed with the hash key. However, our
implementation has a bug - rather than XORing the hash key, it *sets* the
initial state to copies of the key.
I don't know if that affects any of the cryptographic properties of SipHash
but it's not what we should be doing. Fix it.
Signed-off-by: David Gibson
The PREAMBLE macro sets up the SipHash initial internal state. It also
defines that state as a variable, which isn't macro hygeinic. With
previous changes simplifying this premable, it's now possible to replace it
with a macro which simply expands to a C initialisedrfor that state.
Signed-off-by: David Gibson
On Sat, 23 Sep 2023 00:06:26 +1000
David Gibson
The PREAMBLE macro sets up the SipHash initial internal state. It also defines that state as a variable, which isn't macro hygeinic. With previous changes simplifying this premable, it's now possible to replace it with a macro which simply expands to a C initialisedrfor that state.
Signed-off-by: David Gibson
--- siphash.c | 29 ++++++++++++----------------- 1 file changed, 12 insertions(+), 17 deletions(-) diff --git a/siphash.c b/siphash.c index 6932da2..21c560d 100644 --- a/siphash.c +++ b/siphash.c @@ -58,15 +58,12 @@
#define ROTL(x, b) (uint64_t)(((x) << (b)) | ((x) >> (64 - (b))))
-#define PREAMBLE \ - uint64_t v[4] = { 0x736f6d6570736575ULL, 0x646f72616e646f6dULL, \ - 0x6c7967656e657261ULL, 0x7465646279746573ULL }; \ - int __i; \ - \ - do { \ - for (__i = sizeof(v) / sizeof(v[0]) - 1; __i >= 0; __i--) \ - v[__i] ^= k[__i % 2]; \ - } while (0) +#define SIPHASH_INIT(k) { \ + 0x736f6d6570736575ULL ^ (k)[0], \ + 0x646f72616e646f6dULL ^ (k)[1], \ + 0x6c7967656e657261ULL ^ (k)[0], \ + 0x7465646279746573ULL ^ (k)[1] \
I don't think it actually matters (given the rationale for the choice of these constants given in the paper), but earlier this was equivalent to: 0x736f6d6570736575ULL ^ (k)[1], 0x646f72616e646f6dULL ^ (k)[0], 0x6c7967656e657261ULL ^ (k)[1], 0x7465646279746573ULL ^ (k)[0] and it matched both reference implementations linked in the file header. Anyway, the paper says: ...where k0 and k1 are the little-endian 64-bit words encoding the key k. without giving an order, so I guess either interpretation is fine. -- Stefano
On Wed, Sep 27, 2023 at 07:04:50PM +0200, Stefano Brivio wrote:
On Sat, 23 Sep 2023 00:06:26 +1000 David Gibson
wrote: The PREAMBLE macro sets up the SipHash initial internal state. It also defines that state as a variable, which isn't macro hygeinic. With previous changes simplifying this premable, it's now possible to replace it with a macro which simply expands to a C initialisedrfor that state.
Signed-off-by: David Gibson
--- siphash.c | 29 ++++++++++++----------------- 1 file changed, 12 insertions(+), 17 deletions(-) diff --git a/siphash.c b/siphash.c index 6932da2..21c560d 100644 --- a/siphash.c +++ b/siphash.c @@ -58,15 +58,12 @@
#define ROTL(x, b) (uint64_t)(((x) << (b)) | ((x) >> (64 - (b))))
-#define PREAMBLE \ - uint64_t v[4] = { 0x736f6d6570736575ULL, 0x646f72616e646f6dULL, \ - 0x6c7967656e657261ULL, 0x7465646279746573ULL }; \ - int __i; \ - \ - do { \ - for (__i = sizeof(v) / sizeof(v[0]) - 1; __i >= 0; __i--) \ - v[__i] ^= k[__i % 2]; \ - } while (0) +#define SIPHASH_INIT(k) { \ + 0x736f6d6570736575ULL ^ (k)[0], \ + 0x646f72616e646f6dULL ^ (k)[1], \ + 0x6c7967656e657261ULL ^ (k)[0], \ + 0x7465646279746573ULL ^ (k)[1] \
I don't think it actually matters (given the rationale for the choice of these constants given in the paper), but earlier this was equivalent to:
0x736f6d6570736575ULL ^ (k)[1], 0x646f72616e646f6dULL ^ (k)[0], 0x6c7967656e657261ULL ^ (k)[1], 0x7465646279746573ULL ^ (k)[0]
No... I don't think it was. We had: for (__i = sizeof(v) / sizeof(v[0]) - 1; __i >= 0; __i--) v[__i] ^= k[__i % 2]; So in the first iteration __i == 3, so we get v[3] ^= k[1], and v[3] is 0x7465646279746573.
and it matched both reference implementations linked in the file header.
Again, I don't think that's correct. In https://github.com/veorq/SipHash.git we have: v3 ^= k1; v2 ^= k0; v1 ^= k1; v0 ^= k0; In both cases the order of operations is reversed, but since they're independent that doesn't matter. But the point is that the reference implementation has v0 <-> k0 and v3 <-> k1, rather than the other way around.
Anyway, the paper says:
...where k0 and k1 are the little-endian 64-bit words encoding the key k.
without giving an order, so I guess either interpretation is fine.
Right, I also don't think it actually matters. -- David Gibson | I'll have my music baroque, and my code david AT gibson.dropbear.id.au | minimalist, thank you. NOT _the_ _other_ | _way_ _around_! http://www.ozlabs.org/~dgibson
On Thu, 28 Sep 2023 11:20:21 +1000
David Gibson
On Wed, Sep 27, 2023 at 07:04:50PM +0200, Stefano Brivio wrote:
On Sat, 23 Sep 2023 00:06:26 +1000 David Gibson
wrote: The PREAMBLE macro sets up the SipHash initial internal state. It also defines that state as a variable, which isn't macro hygeinic. With previous changes simplifying this premable, it's now possible to replace it with a macro which simply expands to a C initialisedrfor that state.
Signed-off-by: David Gibson
--- siphash.c | 29 ++++++++++++----------------- 1 file changed, 12 insertions(+), 17 deletions(-) diff --git a/siphash.c b/siphash.c index 6932da2..21c560d 100644 --- a/siphash.c +++ b/siphash.c @@ -58,15 +58,12 @@
#define ROTL(x, b) (uint64_t)(((x) << (b)) | ((x) >> (64 - (b))))
-#define PREAMBLE \ - uint64_t v[4] = { 0x736f6d6570736575ULL, 0x646f72616e646f6dULL, \ - 0x6c7967656e657261ULL, 0x7465646279746573ULL }; \ - int __i; \ - \ - do { \ - for (__i = sizeof(v) / sizeof(v[0]) - 1; __i >= 0; __i--) \ - v[__i] ^= k[__i % 2]; \ - } while (0) +#define SIPHASH_INIT(k) { \ + 0x736f6d6570736575ULL ^ (k)[0], \ + 0x646f72616e646f6dULL ^ (k)[1], \ + 0x6c7967656e657261ULL ^ (k)[0], \ + 0x7465646279746573ULL ^ (k)[1] \
I don't think it actually matters (given the rationale for the choice of these constants given in the paper), but earlier this was equivalent to:
0x736f6d6570736575ULL ^ (k)[1], 0x646f72616e646f6dULL ^ (k)[0], 0x6c7967656e657261ULL ^ (k)[1], 0x7465646279746573ULL ^ (k)[0]
No... I don't think it was. We had: for (__i = sizeof(v) / sizeof(v[0]) - 1; __i >= 0; __i--) v[__i] ^= k[__i % 2];
So in the first iteration __i == 3, so we get v[3] ^= k[1], and v[3] is 0x7465646279746573.
Oops, sorry, I missed the fact that I was actually starting from the end of the array.
and it matched both reference implementations linked in the file header.
Again, I don't think that's correct. In https://github.com/veorq/SipHash.git we have: v3 ^= k1; v2 ^= k0; v1 ^= k1; v0 ^= k0;
In both cases the order of operations is reversed, but since they're independent that doesn't matter. But the point is that the reference implementation has v0 <-> k0 and v3 <-> k1, rather than the other way around.
Right. -- Stefano
To improve type safety, encapsulate the internal state of the SipHash
algorithm into a dedicated structure type.
Signed-off-by: David Gibson
Move a bunch of code from siphash.c to siphash.h, making it available to
other modules. This will allow places which need hashes of more complex
objects to construct them incrementally.
Signed-off-by: David Gibson
A number of checksum and hash functions require workarounds for the odd
behaviour of Type-Baased Alias Analysis. We have a detailed comment about
this on siphash_8b() and other functions reference that.
Move the main comment to csume_16b() instead, because we're going to
reorganise things in siphash.c.
Signed-off-by: David Gibson
We have a bunch of variants of the siphash functions for different data
sizes. The callers, in tcp.c, need to pack the various values they want to
hash into a temporary structure, then call the appropriate version. We can
avoid the copy into the temporary by directly using the incremental
siphash functions.
The length specific hash functions also have an undocumented constraint
that the data pointer they take must, in fact, be aligned to avoid
unaligned accesses, which may cause crashes on some architectures.
So, prefer the incremental approach and remove the length-specific
functions.
Signed-off-by: David Gibson
On Sat, Sep 23, 2023 at 12:06:30AM +1000, David Gibson wrote:
We have a bunch of variants of the siphash functions for different data sizes. The callers, in tcp.c, need to pack the various values they want to hash into a temporary structure, then call the appropriate version. We can avoid the copy into the temporary by directly using the incremental siphash functions.
The length specific hash functions also have an undocumented constraint that the data pointer they take must, in fact, be aligned to avoid unaligned accesses, which may cause crashes on some architectures.
So, prefer the incremental approach and remove the length-specific functions.
Signed-off-by: David Gibson
--- Makefile | 2 +- inany.h | 16 ++++++- siphash.c | 121 --------------------------------------------------- tcp.c | 32 +++++--------- tcp_splice.c | 1 + 5 files changed, 27 insertions(+), 145 deletions(-) delete mode 100644 siphash.c diff --git a/Makefile b/Makefile index 4435bd6..ec3c3fb 100644 --- a/Makefile +++ b/Makefile @@ -45,7 +45,7 @@ FLAGS += -DDUAL_STACK_SOCKETS=$(DUAL_STACK_SOCKETS)
PASST_SRCS = arch.c arp.c checksum.c conf.c dhcp.c dhcpv6.c icmp.c igmp.c \ isolation.c lineread.c log.c mld.c ndp.c netlink.c packet.c passt.c \ - pasta.c pcap.c siphash.c tap.c tcp.c tcp_splice.c udp.c util.c + pasta.c pcap.c tap.c tcp.c tcp_splice.c udp.c util.c QRAP_SRCS = qrap.c SRCS = $(PASST_SRCS) $(QRAP_SRCS)
diff --git a/inany.h b/inany.h index aadb20b..266d101 100644 --- a/inany.h +++ b/inany.h @@ -14,8 +14,9 @@ * @v4mapped.zero: All zero-bits for an IPv4 address * @v4mapped.one: All one-bits for an IPv4 address * @v4mapped.a4: If @a6 is an IPv4 mapped address, the IPv4 address + * @u64: As an array of u64s (solely for hashing) * - * @v4mapped shouldn't be accessed except via helpers. + * @v4mapped and @u64 shouldn't be accessed except via helpers. */ union inany_addr { struct in6_addr a6; @@ -24,7 +25,9 @@ union inany_addr { uint8_t one[2]; struct in_addr a4; } v4mapped; + uint64_t u64[2];
I realised this change alters the alignment of inany from 4 bytes to 8 bytes, which causes problems for things I have in the works. Revised version coming.
}; +static_assert(sizeof(union inany_addr) == sizeof(struct in6_addr));
/** inany_v4 - Extract IPv4 address, if present, from IPv[46] address * @addr: IPv4 or IPv6 address @@ -94,4 +97,15 @@ static inline void inany_from_sockaddr(union inany_addr *aa, in_port_t *port, } }
+/** inany_siphash_feed- Fold IPv[46] address into an in-progress siphash + * @state: siphash state + * @aa: inany to hash + */ +static inline void inany_siphash_feed(struct siphash_state *state, + const union inany_addr *aa) +{ + siphash_feed(state, aa->u64[0]); + siphash_feed(state, aa->u64[1]); +} + #endif /* INANY_H */ diff --git a/siphash.c b/siphash.c deleted file mode 100644 index d2b068c..0000000 --- a/siphash.c +++ /dev/null @@ -1,121 +0,0 @@ -// SPDX-License-Identifier: GPL-2.0-or-later - -/* PASST - Plug A Simple Socket Transport - * for qemu/UNIX domain socket mode - * - * PASTA - Pack A Subtle Tap Abstraction - * for network namespace/tap device mode - * - * siphash.c - SipHash routines - * - * Copyright (c) 2020-2021 Red Hat GmbH - * Author: Stefano Brivio
- */ - -#include -#include - -#include "siphash.h" - -/** - * siphash_8b() - Table index or timestamp offset for TCP over IPv4 (8 bytes in) - * @in: Input data (remote address and two ports, or two addresses) - * @k: Hash function key, 128 bits - * - * Return: the 64-bit hash output - */ -/* NOLINTNEXTLINE(clang-diagnostic-unknown-attributes) */ -__attribute__((optimize("-fno-strict-aliasing"))) /* See csum_16b() */ -/* cppcheck-suppress unusedFunction */ -uint64_t siphash_8b(const uint8_t *in, const uint64_t *k) -{ - struct siphash_state state = SIPHASH_INIT(k); - - siphash_feed(&state, *(uint64_t *)in); - - return siphash_final(&state, 8, 0); -} - -/** - * siphash_12b() - Initial sequence number for TCP over IPv4 (12 bytes in) - * @in: Input data (two addresses, two ports) - * @k: Hash function key, 128 bits - * - * Return: the 64-bit hash output - */ -/* NOLINTNEXTLINE(clang-diagnostic-unknown-attributes) */ -__attribute__((optimize("-fno-strict-aliasing"))) /* See csum_16b() */ -/* cppcheck-suppress unusedFunction */ -uint64_t siphash_12b(const uint8_t *in, const uint64_t *k) -{ - struct siphash_state state = SIPHASH_INIT(k); - uint32_t *in32 = (uint32_t *)in; - - siphash_feed(&state, (uint64_t)(*(in32 + 1)) << 32 | *in32); - - return siphash_final(&state, 12, *(in32 + 2)); -} - -/** - * siphash_20b() - Table index for TCP over IPv6 (20 bytes in) - * @in: Input data (remote address, two ports) - * @k: Hash function key, 128 bits - * - * Return: the 64-bit hash output - */ -/* NOLINTNEXTLINE(clang-diagnostic-unknown-attributes) */ -__attribute__((optimize("-fno-strict-aliasing"))) /* See csum_16b() */ -uint64_t siphash_20b(const uint8_t *in, const uint64_t *k) -{ - struct siphash_state state = SIPHASH_INIT(k); - uint32_t *in32 = (uint32_t *)in; - int i; - - for (i = 0; i < 2; i++, in32 += 2) - siphash_feed(&state, (uint64_t)(*(in32 + 1)) << 32 | *in32); - - return siphash_final(&state, 20, *in32); -} - -/** - * siphash_32b() - Timestamp offset for TCP over IPv6 (32 bytes in) - * @in: Input data (two addresses) - * @k: Hash function key, 128 bits - * - * Return: the 64-bit hash output - */ -/* NOLINTNEXTLINE(clang-diagnostic-unknown-attributes) */ -__attribute__((optimize("-fno-strict-aliasing"))) /* See csum_16b() */ -/* cppcheck-suppress unusedFunction */ -uint64_t siphash_32b(const uint8_t *in, const uint64_t *k) -{ - struct siphash_state state = SIPHASH_INIT(k); - uint64_t *in64 = (uint64_t *)in; - int i; - - for (i = 0; i < 4; i++, in64++) - siphash_feed(&state, *in64); - - return siphash_final(&state, 32, 0); -} - -/** - * siphash_36b() - Initial sequence number for TCP over IPv6 (36 bytes in) - * @in: Input data (two addresses, two ports) - * @k: Hash function key, 128 bits - * - * Return: the 64-bit hash output - */ -/* NOLINTNEXTLINE(clang-diagnostic-unknown-attributes) */ -__attribute__((optimize("-fno-strict-aliasing"))) /* See csum_16b() */ -uint64_t siphash_36b(const uint8_t *in, const uint64_t *k) -{ - struct siphash_state state = SIPHASH_INIT(k); - uint32_t *in32 = (uint32_t *)in; - int i; - - for (i = 0; i < 4; i++, in32 += 2) - siphash_feed(&state, (uint64_t)(*(in32 + 1)) << 32 | *in32); - - return siphash_final(&state, 36, *in32); -} diff --git a/tcp.c b/tcp.c index 9f28020..18ceed1 100644 --- a/tcp.c +++ b/tcp.c @@ -1165,18 +1165,13 @@ static int tcp_hash_match(const struct tcp_tap_conn *conn, static unsigned int tcp_hash(const struct ctx *c, const union inany_addr *faddr, in_port_t eport, in_port_t fport) { - struct { - union inany_addr faddr; - in_port_t eport; - in_port_t fport; - } __attribute__((__packed__)) in = { - *faddr, eport, fport - }; - uint64_t b = 0; + struct siphash_state state = SIPHASH_INIT(c->tcp.hash_secret); + uint64_t hash; - b = siphash_20b((uint8_t *)&in, c->tcp.hash_secret); + inany_siphash_feed(&state, faddr); + hash = siphash_final(&state, 20, (uint64_t)eport << 16 | fport);
- return (unsigned int)(b % TCP_HASH_TABLE_SIZE); + return (unsigned int)(hash % TCP_HASH_TABLE_SIZE); }
/** @@ -1815,17 +1810,8 @@ static void tcp_clamp_window(const struct ctx *c, struct tcp_tap_conn *conn, static void tcp_seq_init(const struct ctx *c, struct tcp_tap_conn *conn, const struct timespec *now) { + struct siphash_state state = SIPHASH_INIT(c->tcp.hash_secret); union inany_addr aany; - struct { - union inany_addr src; - in_port_t srcport; - union inany_addr dst; - in_port_t dstport; - } __attribute__((__packed__)) in = { - .src = conn->faddr, - .srcport = conn->fport, - .dstport = conn->eport, - }; uint64_t hash; uint32_t ns;
@@ -1833,9 +1819,11 @@ static void tcp_seq_init(const struct ctx *c, struct tcp_tap_conn *conn, inany_from_af(&aany, AF_INET, &c->ip4.addr); else inany_from_af(&aany, AF_INET6, &c->ip6.addr); - in.dst = aany;
- hash = siphash_36b((uint8_t *)&in, c->tcp.hash_secret); + inany_siphash_feed(&state, &conn->faddr); + inany_siphash_feed(&state, &aany); + hash = siphash_final(&state, 36, + (uint64_t)conn->fport << 16 | conn->eport);
/* 32ns ticks, overflows 32 bits every 137s */ ns = (now->tv_sec * 1000000000 + now->tv_nsec) >> 5; diff --git a/tcp_splice.c b/tcp_splice.c index 5b36975..3b98260 100644 --- a/tcp_splice.c +++ b/tcp_splice.c @@ -52,6 +52,7 @@ #include "passt.h" #include "log.h" #include "tcp_splice.h" +#include "siphash.h" #include "inany.h"
#include "tcp_conn.h"
-- David Gibson | I'll have my music baroque, and my code david AT gibson.dropbear.id.au | minimalist, thank you. NOT _the_ _other_ | _way_ _around_! http://www.ozlabs.org/~dgibson
On Tue, Sep 26, 2023 at 04:23:45PM +1000, David Gibson wrote:
On Sat, Sep 23, 2023 at 12:06:30AM +1000, David Gibson wrote:
We have a bunch of variants of the siphash functions for different data sizes. The callers, in tcp.c, need to pack the various values they want to hash into a temporary structure, then call the appropriate version. We can avoid the copy into the temporary by directly using the incremental siphash functions.
The length specific hash functions also have an undocumented constraint that the data pointer they take must, in fact, be aligned to avoid unaligned accesses, which may cause crashes on some architectures.
So, prefer the incremental approach and remove the length-specific functions.
Signed-off-by: David Gibson
--- Makefile | 2 +- inany.h | 16 ++++++- siphash.c | 121 --------------------------------------------------- tcp.c | 32 +++++--------- tcp_splice.c | 1 + 5 files changed, 27 insertions(+), 145 deletions(-) delete mode 100644 siphash.c diff --git a/Makefile b/Makefile index 4435bd6..ec3c3fb 100644 --- a/Makefile +++ b/Makefile @@ -45,7 +45,7 @@ FLAGS += -DDUAL_STACK_SOCKETS=$(DUAL_STACK_SOCKETS)
PASST_SRCS = arch.c arp.c checksum.c conf.c dhcp.c dhcpv6.c icmp.c igmp.c \ isolation.c lineread.c log.c mld.c ndp.c netlink.c packet.c passt.c \ - pasta.c pcap.c siphash.c tap.c tcp.c tcp_splice.c udp.c util.c + pasta.c pcap.c tap.c tcp.c tcp_splice.c udp.c util.c QRAP_SRCS = qrap.c SRCS = $(PASST_SRCS) $(QRAP_SRCS)
diff --git a/inany.h b/inany.h index aadb20b..266d101 100644 --- a/inany.h +++ b/inany.h @@ -14,8 +14,9 @@ * @v4mapped.zero: All zero-bits for an IPv4 address * @v4mapped.one: All one-bits for an IPv4 address * @v4mapped.a4: If @a6 is an IPv4 mapped address, the IPv4 address + * @u64: As an array of u64s (solely for hashing) * - * @v4mapped shouldn't be accessed except via helpers. + * @v4mapped and @u64 shouldn't be accessed except via helpers. */ union inany_addr { struct in6_addr a6; @@ -24,7 +25,9 @@ union inany_addr { uint8_t one[2]; struct in_addr a4; } v4mapped; + uint64_t u64[2];
I realised this change alters the alignment of inany from 4 bytes to 8 bytes, which causes problems for things I have in the works. Revised version coming.
Actually, I might as well wait for any comments you have on v1, before folding that into v2.
}; +static_assert(sizeof(union inany_addr) == sizeof(struct in6_addr));
/** inany_v4 - Extract IPv4 address, if present, from IPv[46] address * @addr: IPv4 or IPv6 address @@ -94,4 +97,15 @@ static inline void inany_from_sockaddr(union inany_addr *aa, in_port_t *port, } }
+/** inany_siphash_feed- Fold IPv[46] address into an in-progress siphash + * @state: siphash state + * @aa: inany to hash + */ +static inline void inany_siphash_feed(struct siphash_state *state, + const union inany_addr *aa) +{ + siphash_feed(state, aa->u64[0]); + siphash_feed(state, aa->u64[1]); +} + #endif /* INANY_H */ diff --git a/siphash.c b/siphash.c deleted file mode 100644 index d2b068c..0000000 --- a/siphash.c +++ /dev/null @@ -1,121 +0,0 @@ -// SPDX-License-Identifier: GPL-2.0-or-later - -/* PASST - Plug A Simple Socket Transport - * for qemu/UNIX domain socket mode - * - * PASTA - Pack A Subtle Tap Abstraction - * for network namespace/tap device mode - * - * siphash.c - SipHash routines - * - * Copyright (c) 2020-2021 Red Hat GmbH - * Author: Stefano Brivio
- */ - -#include -#include - -#include "siphash.h" - -/** - * siphash_8b() - Table index or timestamp offset for TCP over IPv4 (8 bytes in) - * @in: Input data (remote address and two ports, or two addresses) - * @k: Hash function key, 128 bits - * - * Return: the 64-bit hash output - */ -/* NOLINTNEXTLINE(clang-diagnostic-unknown-attributes) */ -__attribute__((optimize("-fno-strict-aliasing"))) /* See csum_16b() */ -/* cppcheck-suppress unusedFunction */ -uint64_t siphash_8b(const uint8_t *in, const uint64_t *k) -{ - struct siphash_state state = SIPHASH_INIT(k); - - siphash_feed(&state, *(uint64_t *)in); - - return siphash_final(&state, 8, 0); -} - -/** - * siphash_12b() - Initial sequence number for TCP over IPv4 (12 bytes in) - * @in: Input data (two addresses, two ports) - * @k: Hash function key, 128 bits - * - * Return: the 64-bit hash output - */ -/* NOLINTNEXTLINE(clang-diagnostic-unknown-attributes) */ -__attribute__((optimize("-fno-strict-aliasing"))) /* See csum_16b() */ -/* cppcheck-suppress unusedFunction */ -uint64_t siphash_12b(const uint8_t *in, const uint64_t *k) -{ - struct siphash_state state = SIPHASH_INIT(k); - uint32_t *in32 = (uint32_t *)in; - - siphash_feed(&state, (uint64_t)(*(in32 + 1)) << 32 | *in32); - - return siphash_final(&state, 12, *(in32 + 2)); -} - -/** - * siphash_20b() - Table index for TCP over IPv6 (20 bytes in) - * @in: Input data (remote address, two ports) - * @k: Hash function key, 128 bits - * - * Return: the 64-bit hash output - */ -/* NOLINTNEXTLINE(clang-diagnostic-unknown-attributes) */ -__attribute__((optimize("-fno-strict-aliasing"))) /* See csum_16b() */ -uint64_t siphash_20b(const uint8_t *in, const uint64_t *k) -{ - struct siphash_state state = SIPHASH_INIT(k); - uint32_t *in32 = (uint32_t *)in; - int i; - - for (i = 0; i < 2; i++, in32 += 2) - siphash_feed(&state, (uint64_t)(*(in32 + 1)) << 32 | *in32); - - return siphash_final(&state, 20, *in32); -} - -/** - * siphash_32b() - Timestamp offset for TCP over IPv6 (32 bytes in) - * @in: Input data (two addresses) - * @k: Hash function key, 128 bits - * - * Return: the 64-bit hash output - */ -/* NOLINTNEXTLINE(clang-diagnostic-unknown-attributes) */ -__attribute__((optimize("-fno-strict-aliasing"))) /* See csum_16b() */ -/* cppcheck-suppress unusedFunction */ -uint64_t siphash_32b(const uint8_t *in, const uint64_t *k) -{ - struct siphash_state state = SIPHASH_INIT(k); - uint64_t *in64 = (uint64_t *)in; - int i; - - for (i = 0; i < 4; i++, in64++) - siphash_feed(&state, *in64); - - return siphash_final(&state, 32, 0); -} - -/** - * siphash_36b() - Initial sequence number for TCP over IPv6 (36 bytes in) - * @in: Input data (two addresses, two ports) - * @k: Hash function key, 128 bits - * - * Return: the 64-bit hash output - */ -/* NOLINTNEXTLINE(clang-diagnostic-unknown-attributes) */ -__attribute__((optimize("-fno-strict-aliasing"))) /* See csum_16b() */ -uint64_t siphash_36b(const uint8_t *in, const uint64_t *k) -{ - struct siphash_state state = SIPHASH_INIT(k); - uint32_t *in32 = (uint32_t *)in; - int i; - - for (i = 0; i < 4; i++, in32 += 2) - siphash_feed(&state, (uint64_t)(*(in32 + 1)) << 32 | *in32); - - return siphash_final(&state, 36, *in32); -} diff --git a/tcp.c b/tcp.c index 9f28020..18ceed1 100644 --- a/tcp.c +++ b/tcp.c @@ -1165,18 +1165,13 @@ static int tcp_hash_match(const struct tcp_tap_conn *conn, static unsigned int tcp_hash(const struct ctx *c, const union inany_addr *faddr, in_port_t eport, in_port_t fport) { - struct { - union inany_addr faddr; - in_port_t eport; - in_port_t fport; - } __attribute__((__packed__)) in = { - *faddr, eport, fport - }; - uint64_t b = 0; + struct siphash_state state = SIPHASH_INIT(c->tcp.hash_secret); + uint64_t hash; - b = siphash_20b((uint8_t *)&in, c->tcp.hash_secret); + inany_siphash_feed(&state, faddr); + hash = siphash_final(&state, 20, (uint64_t)eport << 16 | fport);
- return (unsigned int)(b % TCP_HASH_TABLE_SIZE); + return (unsigned int)(hash % TCP_HASH_TABLE_SIZE); }
/** @@ -1815,17 +1810,8 @@ static void tcp_clamp_window(const struct ctx *c, struct tcp_tap_conn *conn, static void tcp_seq_init(const struct ctx *c, struct tcp_tap_conn *conn, const struct timespec *now) { + struct siphash_state state = SIPHASH_INIT(c->tcp.hash_secret); union inany_addr aany; - struct { - union inany_addr src; - in_port_t srcport; - union inany_addr dst; - in_port_t dstport; - } __attribute__((__packed__)) in = { - .src = conn->faddr, - .srcport = conn->fport, - .dstport = conn->eport, - }; uint64_t hash; uint32_t ns;
@@ -1833,9 +1819,11 @@ static void tcp_seq_init(const struct ctx *c, struct tcp_tap_conn *conn, inany_from_af(&aany, AF_INET, &c->ip4.addr); else inany_from_af(&aany, AF_INET6, &c->ip6.addr); - in.dst = aany;
- hash = siphash_36b((uint8_t *)&in, c->tcp.hash_secret); + inany_siphash_feed(&state, &conn->faddr); + inany_siphash_feed(&state, &aany); + hash = siphash_final(&state, 36, + (uint64_t)conn->fport << 16 | conn->eport);
/* 32ns ticks, overflows 32 bits every 137s */ ns = (now->tv_sec * 1000000000 + now->tv_nsec) >> 5; diff --git a/tcp_splice.c b/tcp_splice.c index 5b36975..3b98260 100644 --- a/tcp_splice.c +++ b/tcp_splice.c @@ -52,6 +52,7 @@ #include "passt.h" #include "log.h" #include "tcp_splice.h" +#include "siphash.h" #include "inany.h"
#include "tcp_conn.h"
-- David Gibson | I'll have my music baroque, and my code david AT gibson.dropbear.id.au | minimalist, thank you. NOT _the_ _other_ | _way_ _around_! http://www.ozlabs.org/~dgibson
On Tue, 26 Sep 2023 17:02:19 +1000
David Gibson
On Tue, Sep 26, 2023 at 04:23:45PM +1000, David Gibson wrote:
On Sat, Sep 23, 2023 at 12:06:30AM +1000, David Gibson wrote:
We have a bunch of variants of the siphash functions for different data sizes. The callers, in tcp.c, need to pack the various values they want to hash into a temporary structure, then call the appropriate version. We can avoid the copy into the temporary by directly using the incremental siphash functions.
The length specific hash functions also have an undocumented constraint that the data pointer they take must, in fact, be aligned to avoid unaligned accesses, which may cause crashes on some architectures.
So, prefer the incremental approach and remove the length-specific functions.
Signed-off-by: David Gibson
--- Makefile | 2 +- inany.h | 16 ++++++- siphash.c | 121 --------------------------------------------------- tcp.c | 32 +++++--------- tcp_splice.c | 1 + 5 files changed, 27 insertions(+), 145 deletions(-) delete mode 100644 siphash.c diff --git a/Makefile b/Makefile index 4435bd6..ec3c3fb 100644 --- a/Makefile +++ b/Makefile @@ -45,7 +45,7 @@ FLAGS += -DDUAL_STACK_SOCKETS=$(DUAL_STACK_SOCKETS)
PASST_SRCS = arch.c arp.c checksum.c conf.c dhcp.c dhcpv6.c icmp.c igmp.c \ isolation.c lineread.c log.c mld.c ndp.c netlink.c packet.c passt.c \ - pasta.c pcap.c siphash.c tap.c tcp.c tcp_splice.c udp.c util.c + pasta.c pcap.c tap.c tcp.c tcp_splice.c udp.c util.c QRAP_SRCS = qrap.c SRCS = $(PASST_SRCS) $(QRAP_SRCS)
diff --git a/inany.h b/inany.h index aadb20b..266d101 100644 --- a/inany.h +++ b/inany.h @@ -14,8 +14,9 @@ * @v4mapped.zero: All zero-bits for an IPv4 address * @v4mapped.one: All one-bits for an IPv4 address * @v4mapped.a4: If @a6 is an IPv4 mapped address, the IPv4 address + * @u64: As an array of u64s (solely for hashing) * - * @v4mapped shouldn't be accessed except via helpers. + * @v4mapped and @u64 shouldn't be accessed except via helpers. */ union inany_addr { struct in6_addr a6; @@ -24,7 +25,9 @@ union inany_addr { uint8_t one[2]; struct in_addr a4; } v4mapped; + uint64_t u64[2];
I realised this change alters the alignment of inany from 4 bytes to 8 bytes, which causes problems for things I have in the works. Revised version coming.
Actually, I might as well wait for any comments you have on v1, before folding that into v2.
Nothing else from my side. -- Stefano
participants (2)
-
David Gibson
-
Stefano Brivio