)]}'
{
  "commit": "898d431abd2578281bd3bb7db0970bc2de7a24c5",
  "tree": "5568c3a2a44c6f5c47c6ffdf0da972b73579ca39",
  "parents": [
    "9396e37c4860822fbc354fa438bb18e1437e0c9c"
  ],
  "author": {
    "name": "Eric Dumazet",
    "email": "edumazet@google.com",
    "time": "Tue Sep 22 16:34:56 2026 +0000"
  },
  "committer": {
    "name": "Jakub Kicinski",
    "email": "kuba@kernel.org",
    "time": "Fri Sep 25 16:28:54 2026 -0700"
  },
  "message": "net: ethtool: generate RSS keys that spread flows over all queues\n\nnetdev_rss_key_fill() returns a key made of uniformly random bytes. That\nis not enough, because the Toeplitz hash is linear over GF(2).\n\nWalking the hash input MSB first, each set bit contributes a 32-bit\nsliding window of the key, and hardware indexes the indirection table with\nthe low order bits of the result. Only the tail of each window therefore\nreaches the queue index:\n\n        v(i) \u003d key bits [i + 32 - q .. i + 31]\n\nwith q \u003d log2(number of RX queues). Consecutive input bits give windows\noverlapping in q - 1 positions, so the q vectors belonging to the q lowest\nbits of a header field form a Toeplitz matrix built from 2 * q - 1 key\nbits, rather than q * q independent ones. Over GF(2) a random Toeplitz\nmatrix is singular with probability exactly 1/2, whatever its size.\n\nWhen it is singular, flows differing only in the low order bits of that\nfield cannot reach all the queues. This is not theoretical: a burst of\nconnections draws ephemeral ports from a narrow range, and on one affected\nhost only 4 of the 16 RX queues received any traffic at all, until its key\nwas replaced.\n\nKeep drawing the key at random, since it is a secret that stops a remote\nattacker from steering flows onto a single queue, but force the handful of\nbits that decide this. Writing d[t] for key bit (lsb + 31 - t), where lsb\nis the position of the least significant bit of a field in the hash input,\nthe matrices of all the q values up to 8 are non singular if and only if\n\n        d[2 * i] \u003d 1 ^ d[i] ^ d[i + 1] ^ ... ^ d[2 * i - 1]\n\nThe odd positions stay free, so this is a one pass fixup rather than a\nsearch. It is in fact a bijection from those free positions onto the set\nof the values having the property, so the key stays uniformly distributed\nover that set and the whole cost is 8 bits of entropy per position.\nSearching for such a key by rejection would not have been an option: a\nfreshly drawn one has the property everywhere with probability 2^-1008.\n\nApply this at every 16-bit aligned position of the key, rather than at the\noffsets of the 2-tuple and 4-tuple layouts only. The core does not get to\nknow what a given NIC hashes. Hardware may select the bytes it feeds to\nToeplitz out of a header window with a bitmap, and hash an encapsulated\nheader: for PSP over UDP over IPv6 it can pick the outer addresses and the\ninner TCP ports, which sit 78 bytes into the frame and read key bits well\npast the 40 bytes an IPv6 4-tuple needs. Hashed fields are 16 bits wide at\nthe smallest and are not expected to straddle that grid, so covering the\ngrid covers the layouts that were never written down, at no cost in code.\n\nThis spends 8 bits of entropy per position, 1008 bits out of the 2048 bits\nof netdev_rss_key, leaving 1040 bits. 8 is also the largest usable bound,\nas each q constrains 2 * q - 1 bits and anything larger would make the\nranges of two adjacent positions overlap.\n\nWhat the fixup leaves behind is visible structure: 8 of every 16 bits are\nderived from the 8 others, so a 16-bit aligned word of the key takes only\n2^8 values and about 27 of the 128 words of netdev_rss_key duplicate\nanother one. That much is forced rather than an artefact of this\nimplementation, 1040 bits spread over 128 words being a little over 8 bits\neach, but it has one consequence worth removing. Two 32-bit windows a\nwhole number of words apart now collide with probability 2^-16 instead of\n2^-32, and two input bits reading the same window are indistinguishable to\nthe hash, since flipping both of them leaves it unchanged. Over 500 keys,\n23% of them had such a pair, where a uniformly random key has one with\nprobability 2^-11.\n\nSo draw another key when that happens. Four out of five pass. Which\ndistances to look at follows from where the structure is: covering the\nmultiples of 16 leaves 1.2e-3 expected colliding pairs per key, still 2.6\ntimes the 4.6e-4 of a plain random key, and almost all of that excess sits\nat a distance of 8 modulo 16. Covering every multiple of 8 brings the total\ndown to 4.2e-4, below what a plain random key gives over all distances, and\nwithin a few percent of the 4.0e-4 it gives over the distances that are\nleft.\n\nTwo windows a multiple of 8 bits apart are two windows at the same offset\nmodulo 8, so this is a handful of pairwise sweeps rather than one pass over\nthe key per distance. DO_ONCE() runs the generator under a spinlock with\nhard IRQs disabled, so keep the windows of a class in an array rather than\nrecomputing both sides of every pair: 116 us instead of 254 us for the\nworst case, a 2048-bit key with no collision anywhere, at a cost of 512\nbytes of stack.\n\nThe shared key is fixed up once and every driver prefix inherits both\nproperties. Move netdev_rss_key and netdev_rss_key_fill() from\nnet/ethtool/ioctl.c to net/ethtool/common.c, and move the netdev_rss_key\ndeclaration out of include/linux/netdevice.h into net/core/dev.h.\n\nChecked against an independent Toeplitz implementation: for every 16-bit\naligned position and every q in 1..8, an aligned block of 2^q consecutive\nvalues of a field ending there lands on the 2^q queues exactly once each.\nOver 20 random keys that is 20160 checks, which 50.1% of plain random keys\nfail and none of the generated keys do, for an average of 502 rewritten\nbits out of 2048.\n\nSigned-off-by: Eric Dumazet \u003cedumazet@google.com\u003e\nLink: https://patch.msgid.link/20260922163458.3900996-3-edumazet@google.com\nSigned-off-by: Jakub Kicinski \u003ckuba@kernel.org\u003e\n",
  "tree_diff": [
    {
      "type": "modify",
      "old_id": "6c261eb48845a40516f201233df13694863ee8cd",
      "old_mode": 33188,
      "old_path": "Documentation/networking/scaling.rst",
      "new_id": "6c9836000a8d15c209d52fe78e46d346156893e4",
      "new_mode": 33188,
      "new_path": "Documentation/networking/scaling.rst"
    },
    {
      "type": "modify",
      "old_id": "5d16737167eed1b96bd7e0f03bafb598160d94ba",
      "old_mode": 33188,
      "old_path": "include/linux/netdevice.h",
      "new_id": "d037faff7c44b61c80d8f572c23b49d2a8c1ab8f",
      "new_mode": 33188,
      "new_path": "include/linux/netdevice.h"
    },
    {
      "type": "modify",
      "old_id": "f159a7c7beaa5469990b8b258588980c51b0044a",
      "old_mode": 33188,
      "old_path": "net/core/dev.h",
      "new_id": "51921623fc0a41afec6ea89c53c5789df07bcd3d",
      "new_mode": 33188,
      "new_path": "net/core/dev.h"
    },
    {
      "type": "modify",
      "old_id": "23db40618fed147c4fa3de754b100cda1f98f5cd",
      "old_mode": 33188,
      "old_path": "net/ethtool/common.c",
      "new_id": "b4e766e60d38ae22ea3cb52e74afae24a2b66946",
      "new_mode": 33188,
      "new_path": "net/ethtool/common.c"
    },
    {
      "type": "modify",
      "old_id": "b2820f02ca2790a8a3c13395e20040ee6976006f",
      "old_mode": 33188,
      "old_path": "net/ethtool/ioctl.c",
      "new_id": "2b449d08ddcf30e20caf86e9dd294f3e0819ac2d",
      "new_mode": 33188,
      "new_path": "net/ethtool/ioctl.c"
    }
  ]
}