net: ethtool: generate RSS keys that spread flows over all queues

netdev_rss_key_fill() returns a key made of uniformly random bytes. That
is not enough, because the Toeplitz hash is linear over GF(2).

Walking the hash input MSB first, each set bit contributes a 32-bit
sliding window of the key, and hardware indexes the indirection table with
the low order bits of the result. Only the tail of each window therefore
reaches the queue index:

        v(i) = key bits [i + 32 - q .. i + 31]

with q = log2(number of RX queues). Consecutive input bits give windows
overlapping in q - 1 positions, so the q vectors belonging to the q lowest
bits of a header field form a Toeplitz matrix built from 2 * q - 1 key
bits, rather than q * q independent ones. Over GF(2) a random Toeplitz
matrix is singular with probability exactly 1/2, whatever its size.

When it is singular, flows differing only in the low order bits of that
field cannot reach all the queues. This is not theoretical: a burst of
connections draws ephemeral ports from a narrow range, and on one affected
host only 4 of the 16 RX queues received any traffic at all, until its key
was replaced.

Keep drawing the key at random, since it is a secret that stops a remote
attacker from steering flows onto a single queue, but force the handful of
bits that decide this. Writing d[t] for key bit (lsb + 31 - t), where lsb
is the position of the least significant bit of a field in the hash input,
the matrices of all the q values up to 8 are non singular if and only if

        d[2 * i] = 1 ^ d[i] ^ d[i + 1] ^ ... ^ d[2 * i - 1]

The odd positions stay free, so this is a one pass fixup rather than a
search. It is in fact a bijection from those free positions onto the set
of the values having the property, so the key stays uniformly distributed
over that set and the whole cost is 8 bits of entropy per position.
Searching for such a key by rejection would not have been an option: a
freshly drawn one has the property everywhere with probability 2^-1008.

Apply this at every 16-bit aligned position of the key, rather than at the
offsets of the 2-tuple and 4-tuple layouts only. The core does not get to
know what a given NIC hashes. Hardware may select the bytes it feeds to
Toeplitz out of a header window with a bitmap, and hash an encapsulated
header: for PSP over UDP over IPv6 it can pick the outer addresses and the
inner TCP ports, which sit 78 bytes into the frame and read key bits well
past the 40 bytes an IPv6 4-tuple needs. Hashed fields are 16 bits wide at
the smallest and are not expected to straddle that grid, so covering the
grid covers the layouts that were never written down, at no cost in code.

This spends 8 bits of entropy per position, 1008 bits out of the 2048 bits
of netdev_rss_key, leaving 1040 bits. 8 is also the largest usable bound,
as each q constrains 2 * q - 1 bits and anything larger would make the
ranges of two adjacent positions overlap.

What the fixup leaves behind is visible structure: 8 of every 16 bits are
derived from the 8 others, so a 16-bit aligned word of the key takes only
2^8 values and about 27 of the 128 words of netdev_rss_key duplicate
another one. That much is forced rather than an artefact of this
implementation, 1040 bits spread over 128 words being a little over 8 bits
each, but it has one consequence worth removing. Two 32-bit windows a
whole number of words apart now collide with probability 2^-16 instead of
2^-32, and two input bits reading the same window are indistinguishable to
the hash, since flipping both of them leaves it unchanged. Over 500 keys,
23% of them had such a pair, where a uniformly random key has one with
probability 2^-11.

So draw another key when that happens. Four out of five pass. Which
distances to look at follows from where the structure is: covering the
multiples of 16 leaves 1.2e-3 expected colliding pairs per key, still 2.6
times the 4.6e-4 of a plain random key, and almost all of that excess sits
at a distance of 8 modulo 16. Covering every multiple of 8 brings the total
down to 4.2e-4, below what a plain random key gives over all distances, and
within a few percent of the 4.0e-4 it gives over the distances that are
left.

Two windows a multiple of 8 bits apart are two windows at the same offset
modulo 8, so this is a handful of pairwise sweeps rather than one pass over
the key per distance. DO_ONCE() runs the generator under a spinlock with
hard IRQs disabled, so keep the windows of a class in an array rather than
recomputing both sides of every pair: 116 us instead of 254 us for the
worst case, a 2048-bit key with no collision anywhere, at a cost of 512
bytes of stack.

The shared key is fixed up once and every driver prefix inherits both
properties. Move netdev_rss_key and netdev_rss_key_fill() from
net/ethtool/ioctl.c to net/ethtool/common.c, and move the netdev_rss_key
declaration out of include/linux/netdevice.h into net/core/dev.h.

Checked against an independent Toeplitz implementation: for every 16-bit
aligned position and every q in 1..8, an aligned block of 2^q consecutive
values of a field ending there lands on the 2^q queues exactly once each.
Over 20 random keys that is 20160 checks, which 50.1% of plain random keys
fail and none of the generated keys do, for an average of 502 rewritten
bits out of 2048.

Signed-off-by: Eric Dumazet <edumazet@google.com>
Link: https://patch.msgid.link/20260922163458.3900996-3-edumazet@google.com
Signed-off-by: Jakub Kicinski <kuba@kernel.org>

1 files changed, 0 insertions, 1 deletions

diff --git a/include/linux/netdevice.h b/include/linux/netdevice.h
index 5d16737167ee..d037faff7c44 100644
--- a/include/linux/netdevice.h
+++ b/include/linux/netdevice.h
@@ -5323,7 +5323,6 @@ void netdev_lower_state_changed(struct net_device *lower_dev,
 				void *lower_state_info);
 
 #define NETDEV_RSS_KEY_LEN 256
-extern u8 netdev_rss_key[NETDEV_RSS_KEY_LEN] __read_mostly;
 void netdev_rss_key_fill(void *buffer, size_t len);
 
 int skb_checksum_help(struct sk_buff *skb);