[PATCH 00/10] siphash: cleanups and fixes

newer
[PATCH v2 00/10] siphash: cleanups...

older
[PATCH v2 0/2] Some static checker...

David Gibson

22 Sep 2023 22 Sep '23

4:06 p.m.

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

Show replies by date

David Gibson

22 Sep 22 Sep

4:06 p.m.

New subject: [PATCH 01/10] siphash: Make siphash functions consistently return 64-bit results

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 --- siphash.c | 17 +++++++---------- siphash.h | 6 +++--- tcp.c | 7 ++++--- 3 files changed, 14 insertions(+), 16 deletions(-) diff --git a/siphash.c b/siphash.c index e266e15..20009fe 100644 --- a/siphash.c +++ b/siphash.c @@ -61,7 +61,6 @@ uint64_t v[4] = { 0x736f6d6570736575ULL, 0x646f72616e646f6dULL, \ 0x6c7967656e657261ULL, 0x7465646279746573ULL }; \ uint64_t b = (uint64_t)(len) << 56; \ - uint32_t ret; \ int __i; \ \ do { \ @@ -93,8 +92,6 @@ v[2] ^= 0xff; \ SIPROUND(4); \ b = (v[0] ^ v[1]) ^ (v[2] ^ v[3]); \ - ret = (uint32_t)(b >> 32) ^ (uint32_t)b; \ - (void)ret; \ } while (0) /** @@ -132,12 +129,12 @@ uint64_t siphash_8b(const uint8_t *in, const uint64_t *k) * @in: Input data (two addresses, two ports) * @k: Hash function key, 128 bits * - * Return: 32 bits obtained by XORing the two halves of the 64-bit hash output + * Return: the 64-bit hash output */ /* NOLINTNEXTLINE(clang-diagnostic-unknown-attributes) */ __attribute__((optimize("-fno-strict-aliasing"))) /* See siphash_8b() */ /* cppcheck-suppress unusedFunction */ -uint32_t siphash_12b(const uint8_t *in, const uint64_t *k) +uint64_t siphash_12b(const uint8_t *in, const uint64_t *k) { uint32_t *in32 = (uint32_t *)in; uint64_t combined; @@ -151,7 +148,7 @@ uint32_t siphash_12b(const uint8_t *in, const uint64_t *k) b |= *(in32 + 2); POSTAMBLE; - return ret; + return b; } /** @@ -194,7 +191,7 @@ uint64_t siphash_20b(const uint8_t *in, const uint64_t *k) /* NOLINTNEXTLINE(clang-diagnostic-unknown-attributes) */ __attribute__((optimize("-fno-strict-aliasing"))) /* See siphash_8b() */ /* cppcheck-suppress unusedFunction */ -uint32_t siphash_32b(const uint8_t *in, const uint64_t *k) +uint64_t siphash_32b(const uint8_t *in, const uint64_t *k) { uint64_t *in64 = (uint64_t *)in; int i; @@ -217,11 +214,11 @@ uint32_t siphash_32b(const uint8_t *in, const uint64_t *k) * @in: Input data (two addresses, two ports) * @k: Hash function key, 128 bits * - * Return: 32 bits obtained by XORing the two halves of the 64-bit hash output + * Return: the 64-bit hash output */ /* NOLINTNEXTLINE(clang-diagnostic-unknown-attributes) */ __attribute__((optimize("-fno-strict-aliasing"))) /* See siphash_8b() */ -uint32_t siphash_36b(const uint8_t *in, const uint64_t *k) +uint64_t siphash_36b(const uint8_t *in, const uint64_t *k) { uint32_t *in32 = (uint32_t *)in; int i; @@ -239,5 +236,5 @@ uint32_t siphash_36b(const uint8_t *in, const uint64_t *k) b |= *in32; POSTAMBLE; - return ret; + return b; } diff --git a/siphash.h b/siphash.h index 5b0d0c3..de04c56 100644 --- a/siphash.h +++ b/siphash.h @@ -7,9 +7,9 @@ #define SIPHASH_H uint64_t siphash_8b(const uint8_t *in, const uint64_t *k); -uint32_t siphash_12b(const uint8_t *in, const uint64_t *k); +uint64_t siphash_12b(const uint8_t *in, const uint64_t *k); uint64_t siphash_20b(const uint8_t *in, const uint64_t *k); -uint32_t siphash_32b(const uint8_t *in, const uint64_t *k); -uint32_t siphash_36b(const uint8_t *in, const uint64_t *k); +uint64_t siphash_32b(const uint8_t *in, const uint64_t *k); +uint64_t siphash_36b(const uint8_t *in, const uint64_t *k); #endif /* SIPHASH_H */ diff --git a/tcp.c b/tcp.c index dd3142d..9f28020 100644 --- a/tcp.c +++ b/tcp.c @@ -1826,7 +1826,8 @@ static void tcp_seq_init(const struct ctx *c, struct tcp_tap_conn *conn, .srcport = conn->fport, .dstport = conn->eport, }; - uint32_t ns, seq = 0; + uint64_t hash; + uint32_t ns; if (CONN_V4(conn)) inany_from_af(&aany, AF_INET, &c->ip4.addr); @@ -1834,12 +1835,12 @@ static void tcp_seq_init(const struct ctx *c, struct tcp_tap_conn *conn, inany_from_af(&aany, AF_INET6, &c->ip6.addr); in.dst = aany; - seq = siphash_36b((uint8_t *)&in, c->tcp.hash_secret); + hash = siphash_36b((uint8_t *)&in, c->tcp.hash_secret); /* 32ns ticks, overflows 32 bits every 137s */ ns = (now->tv_sec * 1000000000 + now->tv_nsec) >> 5; - conn->seq_to_tap = seq + ns; + conn->seq_to_tap = ((uint32_t)(hash >> 32) ^ (uint32_t)hash) + ns; } /** -- 2.41.0

David Gibson

4:06 p.m.

New subject: [PATCH 02/10] siphash: Make sip round calculations an inline function rather than macro

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 --- siphash.c | 51 +++++++++++++++++++++++++++++---------------------- 1 file changed, 29 insertions(+), 22 deletions(-) diff --git a/siphash.c b/siphash.c index 20009fe..e1fcf18 100644 --- a/siphash.c +++ b/siphash.c @@ -68,29 +68,36 @@ v[__i] = k[__i % 2]; \ } while (0) -#define SIPROUND(n) \ - do { \ - for (__i = 0; __i < (n); __i++) { \ - v[0] += v[1]; \ - v[1] = ROTL(v[1], 13) ^ v[0]; \ - v[0] = ROTL(v[0], 32); \ - v[2] += v[3]; \ - v[3] = ROTL(v[3], 16) ^ v[2]; \ - v[0] += v[3]; \ - v[3] = ROTL(v[3], 21) ^ v[0]; \ - v[2] += v[1]; \ - v[1] = ROTL(v[1], 17) ^ v[2]; \ - v[2] = ROTL(v[2], 32); \ - } \ - } while (0) +/** + * sipround() - Perform rounds of SipHash scrambling + * @v: siphash state (4 x 64-bit integers) + * @n: Number of rounds to apply + */ +static inline void sipround(uint64_t *v, int n) +{ + int i; + + for (i = 0; i < n; i++) { + v[0] += v[1]; + v[1] = ROTL(v[1], 13) ^ v[0]; + v[0] = ROTL(v[0], 32); + v[2] += v[3]; + v[3] = ROTL(v[3], 16) ^ v[2]; + v[0] += v[3]; + v[3] = ROTL(v[3], 21) ^ v[0]; + v[2] += v[1]; + v[1] = ROTL(v[1], 17) ^ v[2]; + v[2] = ROTL(v[2], 32); + } +} #define POSTAMBLE \ do { \ v[3] ^= b; \ - SIPROUND(2); \ + sipround(v, 2); \ v[0] ^= b; \ v[2] ^= 0xff; \ - SIPROUND(4); \ + sipround(v, 4); \ b = (v[0] ^ v[1]) ^ (v[2] ^ v[3]); \ } while (0) @@ -117,7 +124,7 @@ uint64_t siphash_8b(const uint8_t *in, const uint64_t *k) { PREAMBLE(8); v[3] ^= *(uint64_t *)in; - SIPROUND(2); + sipround(v, 2); v[0] ^= *(uint64_t *)in; POSTAMBLE; @@ -143,7 +150,7 @@ uint64_t siphash_12b(const uint8_t *in, const uint64_t *k) PREAMBLE(12); v[3] ^= combined; - SIPROUND(2); + sipround(v, 2); v[0] ^= combined; b |= *(in32 + 2); POSTAMBLE; @@ -171,7 +178,7 @@ uint64_t siphash_20b(const uint8_t *in, const uint64_t *k) uint64_t combined = (uint64_t)(*(in32 + 1)) << 32 | *in32; v[3] ^= combined; - SIPROUND(2); + sipround(v, 2); v[0] ^= combined; } @@ -200,7 +207,7 @@ uint64_t siphash_32b(const uint8_t *in, const uint64_t *k) for (i = 0; i < 4; i++, in64++) { v[3] ^= *in64; - SIPROUND(2); + sipround(v, 2); v[0] ^= *in64; } @@ -229,7 +236,7 @@ uint64_t siphash_36b(const uint8_t *in, const uint64_t *k) uint64_t combined = (uint64_t)(*(in32 + 1)) << 32 | *in32; v[3] ^= combined; - SIPROUND(2); + sipround(v, 2); v[0] ^= combined; } -- 2.41.0

David Gibson

4:06 p.m.

New subject: [PATCH 03/10] siphash: Add siphash_feed() helper

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 --- siphash.c | 52 +++++++++++++++++++++------------------------------- 1 file changed, 21 insertions(+), 31 deletions(-) diff --git a/siphash.c b/siphash.c index e1fcf18..716ab62 100644 --- a/siphash.c +++ b/siphash.c @@ -91,11 +91,21 @@ static inline void sipround(uint64_t *v, int n) } } +/** + * siphash_feed() - Fold 64-bits of data into the hash state + * @v: siphash state (4 x 64-bit integers) + * @in: New value to fold into hash + */ +static inline void siphash_feed(uint64_t *v, uint64_t in) +{ + v[3] ^= in; + sipround(v, 2); + v[0] ^= in; +} + #define POSTAMBLE \ do { \ - v[3] ^= b; \ - sipround(v, 2); \ - v[0] ^= b; \ + siphash_feed(v, b); \ v[2] ^= 0xff; \ sipround(v, 4); \ b = (v[0] ^ v[1]) ^ (v[2] ^ v[3]); \ @@ -123,9 +133,7 @@ __attribute__((optimize("-fno-strict-aliasing"))) uint64_t siphash_8b(const uint8_t *in, const uint64_t *k) { PREAMBLE(8); - v[3] ^= *(uint64_t *)in; - sipround(v, 2); - v[0] ^= *(uint64_t *)in; + siphash_feed(v, *(uint64_t *)in); POSTAMBLE; return b; @@ -144,14 +152,9 @@ __attribute__((optimize("-fno-strict-aliasing"))) /* See siphash_8b() */ uint64_t siphash_12b(const uint8_t *in, const uint64_t *k) { uint32_t *in32 = (uint32_t *)in; - uint64_t combined; - - combined = (uint64_t)(*(in32 + 1)) << 32 | *in32; PREAMBLE(12); - v[3] ^= combined; - sipround(v, 2); - v[0] ^= combined; + siphash_feed(v, (uint64_t)(*(in32 + 1)) << 32 | *in32); b |= *(in32 + 2); POSTAMBLE; @@ -174,13 +177,8 @@ uint64_t siphash_20b(const uint8_t *in, const uint64_t *k) PREAMBLE(20); - for (i = 0; i < 2; i++, in32 += 2) { - uint64_t combined = (uint64_t)(*(in32 + 1)) << 32 | *in32; - - v[3] ^= combined; - sipround(v, 2); - v[0] ^= combined; - } + for (i = 0; i < 2; i++, in32 += 2) + siphash_feed(v, (uint64_t)(*(in32 + 1)) << 32 | *in32); b |= *in32; POSTAMBLE; @@ -205,11 +203,8 @@ uint64_t siphash_32b(const uint8_t *in, const uint64_t *k) PREAMBLE(32); - for (i = 0; i < 4; i++, in64++) { - v[3] ^= *in64; - sipround(v, 2); - v[0] ^= *in64; - } + for (i = 0; i < 4; i++, in64++) + siphash_feed(v, *in64); POSTAMBLE; @@ -232,13 +227,8 @@ uint64_t siphash_36b(const uint8_t *in, const uint64_t *k) PREAMBLE(36); - for (i = 0; i < 4; i++, in32 += 2) { - uint64_t combined = (uint64_t)(*(in32 + 1)) << 32 | *in32; - - v[3] ^= combined; - sipround(v, 2); - v[0] ^= combined; - } + for (i = 0; i < 4; i++, in32 += 2) + siphash_feed(v, (uint64_t)(*(in32 + 1)) << 32 | *in32); b |= *in32; POSTAMBLE; -- 2.41.0

David Gibson

4:06 p.m.

New subject: [PATCH 04/10] siphash: Clean up hash finalisation with posthash_final() function

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 --- siphash.c | 58 +++++++++++++++++++++++++++---------------------------- 1 file changed, 28 insertions(+), 30 deletions(-) diff --git a/siphash.c b/siphash.c index 716ab62..ec39793 100644 --- a/siphash.c +++ b/siphash.c @@ -51,16 +51,16 @@ * */ +#include #include #include "siphash.h" #define ROTL(x, b) (uint64_t)(((x) << (b)) | ((x) >> (64 - (b)))) -#define PREAMBLE(len) \ +#define PREAMBLE \ uint64_t v[4] = { 0x736f6d6570736575ULL, 0x646f72616e646f6dULL, \ 0x6c7967656e657261ULL, 0x7465646279746573ULL }; \ - uint64_t b = (uint64_t)(len) << 56; \ int __i; \ \ do { \ @@ -103,13 +103,21 @@ static inline void siphash_feed(uint64_t *v, uint64_t in) v[0] ^= in; } -#define POSTAMBLE \ - do { \ - siphash_feed(v, b); \ - v[2] ^= 0xff; \ - sipround(v, 4); \ - b = (v[0] ^ v[1]) ^ (v[2] ^ v[3]); \ - } while (0) +/** + * siphash_final - Finalize SipHash calculations + * @v: siphash state (4 x 64-bit integers) + * @len: Total length of input data + * @tail: Final data for the hash (<= 7 bytes) + */ +static inline uint64_t siphash_final(uint64_t *v, size_t len, uint64_t tail) +{ + uint64_t b = (uint64_t)(len) << 56 | tail; + + siphash_feed(v, b); + v[2] ^= 0xff; + sipround(v, 4); + return v[0] ^ v[1] ^ v[2] ^ v[3]; +} /** * siphash_8b() - Table index or timestamp offset for TCP over IPv4 (8 bytes in) @@ -132,11 +140,11 @@ __attribute__((optimize("-fno-strict-aliasing"))) /* cppcheck-suppress unusedFunction */ uint64_t siphash_8b(const uint8_t *in, const uint64_t *k) { - PREAMBLE(8); + PREAMBLE; siphash_feed(v, *(uint64_t *)in); - POSTAMBLE; - return b; + + return siphash_final(v, 8, 0); } /** @@ -153,12 +161,10 @@ uint64_t siphash_12b(const uint8_t *in, const uint64_t *k) { uint32_t *in32 = (uint32_t *)in; - PREAMBLE(12); + PREAMBLE; siphash_feed(v, (uint64_t)(*(in32 + 1)) << 32 | *in32); - b |= *(in32 + 2); - POSTAMBLE; - return b; + return siphash_final(v, 12, *(in32 + 2)); } /** @@ -175,15 +181,12 @@ uint64_t siphash_20b(const uint8_t *in, const uint64_t *k) uint32_t *in32 = (uint32_t *)in; int i; - PREAMBLE(20); + PREAMBLE; for (i = 0; i < 2; i++, in32 += 2) siphash_feed(v, (uint64_t)(*(in32 + 1)) << 32 | *in32); - b |= *in32; - POSTAMBLE; - - return b; + return siphash_final(v, 20, *in32); } /** @@ -201,14 +204,12 @@ uint64_t siphash_32b(const uint8_t *in, const uint64_t *k) uint64_t *in64 = (uint64_t *)in; int i; - PREAMBLE(32); + PREAMBLE; for (i = 0; i < 4; i++, in64++) siphash_feed(v, *in64); - POSTAMBLE; - - return b; + return siphash_final(v, 32, 0); } /** @@ -225,13 +226,10 @@ uint64_t siphash_36b(const uint8_t *in, const uint64_t *k) uint32_t *in32 = (uint32_t *)in; int i; - PREAMBLE(36); + PREAMBLE; for (i = 0; i < 4; i++, in32 += 2) siphash_feed(v, (uint64_t)(*(in32 + 1)) << 32 | *in32); - b |= *in32; - POSTAMBLE; - - return b; + return siphash_final(v, 36, *in32); } -- 2.41.0

David Gibson

4:06 p.m.

New subject: [PATCH 05/10] siphash: Fix bug in state initialisation

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 --- siphash.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/siphash.c b/siphash.c index ec39793..6932da2 100644 --- a/siphash.c +++ b/siphash.c @@ -65,7 +65,7 @@ \ do { \ for (__i = sizeof(v) / sizeof(v[0]) - 1; __i >= 0; __i--) \ - v[__i] = k[__i % 2]; \ + v[__i] ^= k[__i % 2]; \ } while (0) /** -- 2.41.0

David Gibson

4:06 p.m.

New subject: [PATCH 06/10] siphash: Use more hygienic state initialiser

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] \ + } /** * sipround() - Perform rounds of SipHash scrambling @@ -140,7 +137,8 @@ __attribute__((optimize("-fno-strict-aliasing"))) /* cppcheck-suppress unusedFunction */ uint64_t siphash_8b(const uint8_t *in, const uint64_t *k) { - PREAMBLE; + uint64_t v[4] = SIPHASH_INIT(k); + siphash_feed(v, *(uint64_t *)in); @@ -160,8 +158,8 @@ __attribute__((optimize("-fno-strict-aliasing"))) /* See siphash_8b() */ uint64_t siphash_12b(const uint8_t *in, const uint64_t *k) { uint32_t *in32 = (uint32_t *)in; + uint64_t v[4] = SIPHASH_INIT(k); - PREAMBLE; siphash_feed(v, (uint64_t)(*(in32 + 1)) << 32 | *in32); return siphash_final(v, 12, *(in32 + 2)); @@ -179,10 +177,9 @@ __attribute__((optimize("-fno-strict-aliasing"))) /* See siphash_8b() */ uint64_t siphash_20b(const uint8_t *in, const uint64_t *k) { uint32_t *in32 = (uint32_t *)in; + uint64_t v[4] = SIPHASH_INIT(k); int i; - PREAMBLE; - for (i = 0; i < 2; i++, in32 += 2) siphash_feed(v, (uint64_t)(*(in32 + 1)) << 32 | *in32); @@ -202,10 +199,9 @@ __attribute__((optimize("-fno-strict-aliasing"))) /* See siphash_8b() */ uint64_t siphash_32b(const uint8_t *in, const uint64_t *k) { uint64_t *in64 = (uint64_t *)in; + uint64_t v[4] = SIPHASH_INIT(k); int i; - PREAMBLE; - for (i = 0; i < 4; i++, in64++) siphash_feed(v, *in64); @@ -224,10 +220,9 @@ __attribute__((optimize("-fno-strict-aliasing"))) /* See siphash_8b() */ uint64_t siphash_36b(const uint8_t *in, const uint64_t *k) { uint32_t *in32 = (uint32_t *)in; + uint64_t v[4] = SIPHASH_INIT(k); int i; - PREAMBLE; - for (i = 0; i < 4; i++, in32 += 2) siphash_feed(v, (uint64_t)(*(in32 + 1)) << 32 | *in32); -- 2.41.0

Stefano Brivio

27 Sep 27 Sep

7:04 p.m.

New subject: [PATCH 06/10] siphash: Use more hygienic state initialiser

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] 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

David Gibson

28 Sep 28 Sep

3:20 a.m.

New subject: [PATCH 06/10] siphash: Use more hygienic state initialiser

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

Stefano Brivio

29 Sep 29 Sep

5:19 p.m.

New subject: [PATCH 06/10] siphash: Use more hygienic state initialiser

On Thu, 28 Sep 2023 11:20:21 +1000 David Gibson wrote:

...

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

David Gibson

22 Sep 22 Sep

4:06 p.m.

New subject: [PATCH 07/10] siphash: Use specific structure for internal state

To improve type safety, encapsulate the internal state of the SipHash algorithm into a dedicated structure type. Signed-off-by: David Gibson --- siphash.c | 80 +++++++++++++++++++++++++++++-------------------------- 1 file changed, 42 insertions(+), 38 deletions(-) diff --git a/siphash.c b/siphash.c index 21c560d..66174c7 100644 --- a/siphash.c +++ b/siphash.c @@ -58,33 +58,37 @@ #define ROTL(x, b) (uint64_t)(((x) << (b)) | ((x) >> (64 - (b)))) -#define SIPHASH_INIT(k) { \ +struct siphash_state { + uint64_t v[4]; +}; + +#define SIPHASH_INIT(k) { { \ 0x736f6d6570736575ULL ^ (k)[0], \ 0x646f72616e646f6dULL ^ (k)[1], \ 0x6c7967656e657261ULL ^ (k)[0], \ 0x7465646279746573ULL ^ (k)[1] \ - } + } } /** * sipround() - Perform rounds of SipHash scrambling * @v: siphash state (4 x 64-bit integers) * @n: Number of rounds to apply */ -static inline void sipround(uint64_t *v, int n) +static inline void sipround(struct siphash_state *state, int n) { int i; for (i = 0; i < n; i++) { - v[0] += v[1]; - v[1] = ROTL(v[1], 13) ^ v[0]; - v[0] = ROTL(v[0], 32); - v[2] += v[3]; - v[3] = ROTL(v[3], 16) ^ v[2]; - v[0] += v[3]; - v[3] = ROTL(v[3], 21) ^ v[0]; - v[2] += v[1]; - v[1] = ROTL(v[1], 17) ^ v[2]; - v[2] = ROTL(v[2], 32); + state->v[0] += state->v[1]; + state->v[1] = ROTL(state->v[1], 13) ^ state->v[0]; + state->v[0] = ROTL(state->v[0], 32); + state->v[2] += state->v[3]; + state->v[3] = ROTL(state->v[3], 16) ^ state->v[2]; + state->v[0] += state->v[3]; + state->v[3] = ROTL(state->v[3], 21) ^ state->v[0]; + state->v[2] += state->v[1]; + state->v[1] = ROTL(state->v[1], 17) ^ state->v[2]; + state->v[2] = ROTL(state->v[2], 32); } } @@ -93,11 +97,11 @@ static inline void sipround(uint64_t *v, int n) * @v: siphash state (4 x 64-bit integers) * @in: New value to fold into hash */ -static inline void siphash_feed(uint64_t *v, uint64_t in) +static inline void siphash_feed(struct siphash_state *state, uint64_t in) { - v[3] ^= in; - sipround(v, 2); - v[0] ^= in; + state->v[3] ^= in; + sipround(state, 2); + state->v[0] ^= in; } /** @@ -106,14 +110,15 @@ static inline void siphash_feed(uint64_t *v, uint64_t in) * @len: Total length of input data * @tail: Final data for the hash (<= 7 bytes) */ -static inline uint64_t siphash_final(uint64_t *v, size_t len, uint64_t tail) +static inline uint64_t siphash_final(struct siphash_state *state, + size_t len, uint64_t tail) { uint64_t b = (uint64_t)(len) << 56 | tail; - siphash_feed(v, b); - v[2] ^= 0xff; - sipround(v, 4); - return v[0] ^ v[1] ^ v[2] ^ v[3]; + siphash_feed(state, b); + state->v[2] ^= 0xff; + sipround(state, 4); + return state->v[0] ^ state->v[1] ^ state->v[2] ^ state->v[3]; } /** @@ -137,12 +142,11 @@ __attribute__((optimize("-fno-strict-aliasing"))) /* cppcheck-suppress unusedFunction */ uint64_t siphash_8b(const uint8_t *in, const uint64_t *k) { - uint64_t v[4] = SIPHASH_INIT(k); - - siphash_feed(v, *(uint64_t *)in); + struct siphash_state state = SIPHASH_INIT(k); + siphash_feed(&state, *(uint64_t *)in); - return siphash_final(v, 8, 0); + return siphash_final(&state, 8, 0); } /** @@ -157,12 +161,12 @@ __attribute__((optimize("-fno-strict-aliasing"))) /* See siphash_8b() */ /* 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; - uint64_t v[4] = SIPHASH_INIT(k); - siphash_feed(v, (uint64_t)(*(in32 + 1)) << 32 | *in32); + siphash_feed(&state, (uint64_t)(*(in32 + 1)) << 32 | *in32); - return siphash_final(v, 12, *(in32 + 2)); + return siphash_final(&state, 12, *(in32 + 2)); } /** @@ -176,14 +180,14 @@ uint64_t siphash_12b(const uint8_t *in, const uint64_t *k) __attribute__((optimize("-fno-strict-aliasing"))) /* See siphash_8b() */ 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; - uint64_t v[4] = SIPHASH_INIT(k); int i; for (i = 0; i < 2; i++, in32 += 2) - siphash_feed(v, (uint64_t)(*(in32 + 1)) << 32 | *in32); + siphash_feed(&state, (uint64_t)(*(in32 + 1)) << 32 | *in32); - return siphash_final(v, 20, *in32); + return siphash_final(&state, 20, *in32); } /** @@ -198,14 +202,14 @@ __attribute__((optimize("-fno-strict-aliasing"))) /* See siphash_8b() */ /* 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; - uint64_t v[4] = SIPHASH_INIT(k); int i; for (i = 0; i < 4; i++, in64++) - siphash_feed(v, *in64); + siphash_feed(&state, *in64); - return siphash_final(v, 32, 0); + return siphash_final(&state, 32, 0); } /** @@ -219,12 +223,12 @@ uint64_t siphash_32b(const uint8_t *in, const uint64_t *k) __attribute__((optimize("-fno-strict-aliasing"))) /* See siphash_8b() */ 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; - uint64_t v[4] = SIPHASH_INIT(k); int i; for (i = 0; i < 4; i++, in32 += 2) - siphash_feed(v, (uint64_t)(*(in32 + 1)) << 32 | *in32); + siphash_feed(&state, (uint64_t)(*(in32 + 1)) << 32 | *in32); - return siphash_final(v, 36, *in32); + return siphash_final(&state, 36, *in32); } -- 2.41.0

David Gibson

4:06 p.m.

New subject: [PATCH 08/10] siphash: Make internal helpers public

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 --- siphash.c | 104 ------------------------------------------------- siphash.h | 113 +++++++++++++++++++++++++++++++++++++++++++++++++++++- 2 files changed, 111 insertions(+), 106 deletions(-) diff --git a/siphash.c b/siphash.c index 66174c7..91bcc5d 100644 --- a/siphash.c +++ b/siphash.c @@ -10,45 +10,6 @@ * * Copyright (c) 2020-2021 Red Hat GmbH * Author: Stefano Brivio - * - * This is an implementation of the SipHash-2-4-64 functions needed for TCP - * initial sequence numbers and socket lookup table hash for IPv4 and IPv6, see: - * - * Aumasson, J.P. and Bernstein, D.J., 2012, December. SipHash: a fast - * short-input PRF. In International Conference on Cryptology in India - * (pp. 489-508). Springer, Berlin, Heidelberg. - * - * http://cr.yp.to/siphash/siphash-20120918.pdf - * - * This includes code from the reference SipHash implementation at - * https://github.com/veorq/SipHash/ originally licensed as follows: - * - * -- - * SipHash reference C implementation - * - * Copyright (c) 2012-2021 Jean-Philippe Aumasson - * - * Copyright (c) 2012-2014 Daniel J. Bernstein - * - * To the extent possible under law, the author(s) have dedicated all copyright - * and related and neighboring rights to this software to the public domain - * worldwide. This software is distributed without any warranty. - * - * You should have received a copy of the CC0 Public Domain Dedication along - * with - * this software. If not, see - * http://creativecommons.org/publicdomain/zero/1.0/. - * -- - * - * and from the Linux kernel implementation (lib/siphash.c), originally licensed - * as follows: - * - * -- - * Copyright (C) 2016 Jason A. Donenfeld . All Rights Reserved. - * - * This file is provided under a dual BSD/GPLv2 license. - * -- - * */ #include @@ -56,71 +17,6 @@ #include "siphash.h" -#define ROTL(x, b) (uint64_t)(((x) << (b)) | ((x) >> (64 - (b)))) - -struct siphash_state { - uint64_t v[4]; -}; - -#define SIPHASH_INIT(k) { { \ - 0x736f6d6570736575ULL ^ (k)[0], \ - 0x646f72616e646f6dULL ^ (k)[1], \ - 0x6c7967656e657261ULL ^ (k)[0], \ - 0x7465646279746573ULL ^ (k)[1] \ - } } - -/** - * sipround() - Perform rounds of SipHash scrambling - * @v: siphash state (4 x 64-bit integers) - * @n: Number of rounds to apply - */ -static inline void sipround(struct siphash_state *state, int n) -{ - int i; - - for (i = 0; i < n; i++) { - state->v[0] += state->v[1]; - state->v[1] = ROTL(state->v[1], 13) ^ state->v[0]; - state->v[0] = ROTL(state->v[0], 32); - state->v[2] += state->v[3]; - state->v[3] = ROTL(state->v[3], 16) ^ state->v[2]; - state->v[0] += state->v[3]; - state->v[3] = ROTL(state->v[3], 21) ^ state->v[0]; - state->v[2] += state->v[1]; - state->v[1] = ROTL(state->v[1], 17) ^ state->v[2]; - state->v[2] = ROTL(state->v[2], 32); - } -} - -/** - * siphash_feed() - Fold 64-bits of data into the hash state - * @v: siphash state (4 x 64-bit integers) - * @in: New value to fold into hash - */ -static inline void siphash_feed(struct siphash_state *state, uint64_t in) -{ - state->v[3] ^= in; - sipround(state, 2); - state->v[0] ^= in; -} - -/** - * siphash_final - Finalize SipHash calculations - * @v: siphash state (4 x 64-bit integers) - * @len: Total length of input data - * @tail: Final data for the hash (<= 7 bytes) - */ -static inline uint64_t siphash_final(struct siphash_state *state, - size_t len, uint64_t tail) -{ - uint64_t b = (uint64_t)(len) << 56 | tail; - - siphash_feed(state, b); - state->v[2] ^= 0xff; - sipround(state, 4); - return state->v[0] ^ state->v[1] ^ state->v[2] ^ state->v[3]; -} - /** * 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) diff --git a/siphash.h b/siphash.h index de04c56..f966cdb 100644 --- a/siphash.h +++ b/siphash.h @@ -1,11 +1,120 @@ /* SPDX-License-Identifier: GPL-2.0-or-later - * Copyright (c) 2021 Red Hat GmbH + * Copyright Red Hat * Author: Stefano Brivio - */ + * Author: David Gibson + * + * This is an implementation of the SipHash-2-4-64 functions needed for TCP + * initial sequence numbers and socket lookup table hash for IPv4 and IPv6, see: + * + * Aumasson, J.P. and Bernstein, D.J., 2012, December. SipHash: a fast + * short-input PRF. In International Conference on Cryptology in India + * (pp. 489-508). Springer, Berlin, Heidelberg. + * + * http://cr.yp.to/siphash/siphash-20120918.pdf + * + * This includes code from the reference SipHash implementation at + * https://github.com/veorq/SipHash/ originally licensed as follows: + * + * -- + * SipHash reference C implementation + * + * Copyright (c) 2012-2021 Jean-Philippe Aumasson + * Copyright (c) 2012-2014 Daniel J. Bernstein + * + * To the extent possible under law, the author(s) have dedicated all copyright + * and related and neighboring rights to this software to the public domain + * worldwide. This software is distributed without any warranty. + * + * You should have received a copy of the CC0 Public Domain Dedication along + * with this software. If not, see + * http://creativecommons.org/publicdomain/zero/1.0/. + * -- + * + * and from the Linux kernel implementation (lib/siphash.c), originally licensed + * as follows: + * + * -- + * Copyright (C) 2016 Jason A. Donenfeld . All Rights Reserved. + * + * This file is provided under a dual BSD/GPLv2 license. + * -- + * +*/ #ifndef SIPHASH_H #define SIPHASH_H +/** + * struct siphash_state - Internal state of siphash calculation + */ +struct siphash_state { + uint64_t v[4]; +}; + +#define SIPHASH_INIT(k) { { \ + 0x736f6d6570736575ULL ^ (k)[0], \ + 0x646f72616e646f6dULL ^ (k)[1], \ + 0x6c7967656e657261ULL ^ (k)[0], \ + 0x7465646279746573ULL ^ (k)[1] \ + } } + +/** + * sipround() - Perform rounds of SipHash scrambling + * @v: siphash state (4 x 64-bit integers) + * @n: Number of rounds to apply + */ +static inline void sipround(struct siphash_state *state, int n) +{ + int i; + +#define ROTL(x, b) (uint64_t)(((x) << (b)) | ((x) >> (64 - (b)))) + + for (i = 0; i < n; i++) { + + state->v[0] += state->v[1]; + state->v[1] = ROTL(state->v[1], 13) ^ state->v[0]; + state->v[0] = ROTL(state->v[0], 32); + state->v[2] += state->v[3]; + state->v[3] = ROTL(state->v[3], 16) ^ state->v[2]; + state->v[0] += state->v[3]; + state->v[3] = ROTL(state->v[3], 21) ^ state->v[0]; + state->v[2] += state->v[1]; + state->v[1] = ROTL(state->v[1], 17) ^ state->v[2]; + state->v[2] = ROTL(state->v[2], 32); + } + +#undef ROTL +} + +/** + * siphash_feed() - Fold 64-bits of data into the hash state + * @v: siphash state (4 x 64-bit integers) + * @in: New value to fold into hash + */ +static inline void siphash_feed(struct siphash_state *state, uint64_t in) +{ + state->v[3] ^= in; + sipround(state, 2); + state->v[0] ^= in; +} + +/** + * siphash_final - Finalize SipHash calculations + * @v: siphash state (4 x 64-bit integers) + * @len: Total length of input data + * @tail: Final data for the hash (<= 7 bytes) + */ +static inline uint64_t siphash_final(struct siphash_state *state, + size_t len, uint64_t tail) +{ + uint64_t b = (uint64_t)(len) << 56 | tail; + + siphash_feed(state, b); + state->v[2] ^= 0xff; + sipround(state, 4); + return state->v[0] ^ state->v[1] ^ state->v[2] ^ state->v[3]; +} + uint64_t siphash_8b(const uint8_t *in, const uint64_t *k); uint64_t siphash_12b(const uint8_t *in, const uint64_t *k); uint64_t siphash_20b(const uint8_t *in, const uint64_t *k); -- 2.41.0

David Gibson

4:06 p.m.

New subject: [PATCH 09/10] siphash, checksum: Move TBAA explanation to checksum.c

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 --- checksum.c | 19 ++++++++++++++----- siphash.c | 19 +++++-------------- 2 files changed, 19 insertions(+), 19 deletions(-) diff --git a/checksum.c b/checksum.c index f2b82a4..03b8a7c 100644 --- a/checksum.c +++ b/checksum.c @@ -69,8 +69,17 @@ * * Return: 32-bit sum of 16-bit words */ +/* Type-Based Alias Analysis (TBAA) optimisation in gcc 11 and 12 (-flto -O2) + * makes these functions essentially useless by allowing reordering of stores of + * input data across function calls. Not even declaring @in as char pointer is + * enough: disable gcc's interpretation of strict aliasing altogether. See also: + * + * https://gcc.gnu.org/bugzilla/show_bug.cgi?id=106706 + * https://stackoverflow.com/questions/2958633/gcc-strict-aliasing-and-horror-s... + * https://lore.kernel.org/all/alpine.LFD.2.00.0901121128080.6528__33422.532809... + */ /* NOLINTNEXTLINE(clang-diagnostic-unknown-attributes) */ -__attribute__((optimize("-fno-strict-aliasing"))) /* See siphash_8b() */ +__attribute__((optimize("-fno-strict-aliasing"))) uint32_t sum_16b(const void *buf, size_t len) { const uint16_t *p = buf; @@ -110,7 +119,7 @@ uint16_t csum_fold(uint32_t sum) * Return: 16-bit IPv4-style checksum */ /* NOLINTNEXTLINE(clang-diagnostic-unknown-attributes) */ -__attribute__((optimize("-fno-strict-aliasing"))) /* See siphash_8b() */ +__attribute__((optimize("-fno-strict-aliasing"))) /* See csum_16b() */ uint16_t csum_unaligned(const void *buf, size_t len, uint32_t init) { return (uint16_t)~csum_fold(sum_16b(buf, len) + init); @@ -247,7 +256,7 @@ void csum_icmp6(struct icmp6hdr *icmp6hr, * - coding style adaptation */ /* NOLINTNEXTLINE(clang-diagnostic-unknown-attributes) */ -__attribute__((optimize("-fno-strict-aliasing"))) /* See siphash_8b() */ +__attribute__((optimize("-fno-strict-aliasing"))) /* See csum_16b() */ static uint32_t csum_avx2(const void *buf, size_t len, uint32_t init) { __m256i a, b, sum256, sum_a_hi, sum_a_lo, sum_b_hi, sum_b_lo, c, d; @@ -395,7 +404,7 @@ less_than_128_bytes: * Return: 16-bit folded, complemented checksum sum */ /* NOLINTNEXTLINE(clang-diagnostic-unknown-attributes) */ -__attribute__((optimize("-fno-strict-aliasing"))) /* See siphash_8b() */ +__attribute__((optimize("-fno-strict-aliasing"))) /* See csum_16b() */ uint16_t csum(const void *buf, size_t len, uint32_t init) { return (uint16_t)~csum_fold(csum_avx2(buf, len, init)); @@ -412,7 +421,7 @@ uint16_t csum(const void *buf, size_t len, uint32_t init) * Return: 16-bit folded, complemented checksum */ /* NOLINTNEXTLINE(clang-diagnostic-unknown-attributes) */ -__attribute__((optimize("-fno-strict-aliasing"))) /* See siphash_8b() */ +__attribute__((optimize("-fno-strict-aliasing"))) /* See csum_16b() */ uint16_t csum(const void *buf, size_t len, uint32_t init) { return csum_unaligned(buf, len, init); diff --git a/siphash.c b/siphash.c index 91bcc5d..d2b068c 100644 --- a/siphash.c +++ b/siphash.c @@ -24,17 +24,8 @@ * * Return: the 64-bit hash output */ -/* Type-Based Alias Analysis (TBAA) optimisation in gcc 11 and 12 (-flto -O2) - * makes these functions essentially useless by allowing reordering of stores of - * input data across function calls. Not even declaring @in as char pointer is - * enough: disable gcc's interpretation of strict aliasing altogether. See also: - * - * https://gcc.gnu.org/bugzilla/show_bug.cgi?id=106706 - * https://stackoverflow.com/questions/2958633/gcc-strict-aliasing-and-horror-s... - * https://lore.kernel.org/all/alpine.LFD.2.00.0901121128080.6528__33422.532809... - */ /* NOLINTNEXTLINE(clang-diagnostic-unknown-attributes) */ -__attribute__((optimize("-fno-strict-aliasing"))) +__attribute__((optimize("-fno-strict-aliasing"))) /* See csum_16b() */ /* cppcheck-suppress unusedFunction */ uint64_t siphash_8b(const uint8_t *in, const uint64_t *k) { @@ -53,7 +44,7 @@ uint64_t siphash_8b(const uint8_t *in, const uint64_t *k) * Return: the 64-bit hash output */ /* NOLINTNEXTLINE(clang-diagnostic-unknown-attributes) */ -__attribute__((optimize("-fno-strict-aliasing"))) /* See siphash_8b() */ +__attribute__((optimize("-fno-strict-aliasing"))) /* See csum_16b() */ /* cppcheck-suppress unusedFunction */ uint64_t siphash_12b(const uint8_t *in, const uint64_t *k) { @@ -73,7 +64,7 @@ uint64_t siphash_12b(const uint8_t *in, const uint64_t *k) * Return: the 64-bit hash output */ /* NOLINTNEXTLINE(clang-diagnostic-unknown-attributes) */ -__attribute__((optimize("-fno-strict-aliasing"))) /* See siphash_8b() */ +__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); @@ -94,7 +85,7 @@ uint64_t siphash_20b(const uint8_t *in, const uint64_t *k) * Return: the 64-bit hash output */ /* NOLINTNEXTLINE(clang-diagnostic-unknown-attributes) */ -__attribute__((optimize("-fno-strict-aliasing"))) /* See siphash_8b() */ +__attribute__((optimize("-fno-strict-aliasing"))) /* See csum_16b() */ /* cppcheck-suppress unusedFunction */ uint64_t siphash_32b(const uint8_t *in, const uint64_t *k) { @@ -116,7 +107,7 @@ uint64_t siphash_32b(const uint8_t *in, const uint64_t *k) * Return: the 64-bit hash output */ /* NOLINTNEXTLINE(clang-diagnostic-unknown-attributes) */ -__attribute__((optimize("-fno-strict-aliasing"))) /* See siphash_8b() */ +__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); -- 2.41.0

David Gibson

4:06 p.m.

New subject: [PATCH 10/10] siphash: Use incremental rather than all-at-once siphash functions

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]; }; +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" -- 2.41.0

David Gibson

26 Sep 26 Sep

8:23 a.m.

New subject: [PATCH 10/10] siphash: Use incremental rather than all-at-once siphash functions

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

David Gibson

9:02 a.m.

New subject: [PATCH 10/10] siphash: Use incremental rather than all-at-once siphash functions

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

Stefano Brivio

27 Sep 27 Sep

7:05 p.m.

New subject: [PATCH 10/10] siphash: Use incremental rather than all-at-once siphash functions

On Tue, 26 Sep 2023 17:02:19 +1000 David Gibson wrote:

...

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

640

Age (days ago)

647

Last active (days ago)

List overview

Download

16 comments

2 participants

participants (2)

David Gibson
Stefano Brivio

[PATCH 00/10] siphash: cleanups and fixes

tags

participants (2)