@@ -0,0 +1,314 @@
+// SPDX-License-Identifier: GPL-2.0-only
+/* Tests for the RSS key generated by netdev_rss_key_fill().
+ *
+ * The property under test is that flows differing only in the low order bits
+ * of one hashed header field land on distinct RX queues. It is checked here
+ * from the definition of the Toeplitz hash, independently of the way
+ * netdev_rss_key_init() achieves it.
+ */
+
+#include <kunit/test.h>
+#include <linux/module.h>
+#include <linux/random.h>
+#include <linux/sort.h>
+
+#include "common.h"
+
+MODULE_IMPORT_NS("EXPORTED_FOR_KUNIT_TESTING");
+
+/* Longest hash input exercised here: an IPv6 header, a UDP header, a PSP
+ * header and the inner TCP ports. See rss_key_test_fields[].
+ */
+#define RSS_KEY_TEST_INPUT_LEN 68
+
+#define RSS_KEY_TEST_KEYS 32
+
+/* Number of queue counts exercised end to end by rss_key_spread_test(), which
+ * hashes 2 ** q inputs for each of them. The algebraic check covers all the
+ * queue counts up to NETDEV_RSS_KEY_QMAX.
+ */
+#define RSS_KEY_TEST_SPREAD_QMAX 6
+
+/* Position of the least significant bit of each field, counting from the most
+ * significant bit of the hash input, and the length of that input. These come
+ * from the definition of the hash, not from the key generator.
+ */
+static const struct rss_key_test_field {
+ const char *name;
+ unsigned int lsb;
+ unsigned int nbits;
+} rss_key_test_fields[] = {
+ { "IPv4 saddr", 31, 96 },
+ { "IPv4 daddr", 63, 96 },
+ { "IPv4 sport", 79, 96 },
+ { "IPv4 dport", 95, 96 },
+ { "IPv6 saddr", 127, 288 },
+ { "IPv6 daddr", 255, 288 },
+ { "IPv6 sport", 271, 288 },
+ { "IPv6 dport", 287, 288 },
+ /* Hardware is free to hash an encapsulated header instead, and then
+ * it reads the key far past the 40 bytes an IPv6 4-tuple needs. These
+ * offsets are those of PSP transport mode over UDP over IPv6
+ * (Documentation/networking/psp.rst): 40 bytes of IPv6, 8 of UDP,
+ * PSP_HDR_SIZE of PSP, then the inner TCP ports. Prepending an
+ * Ethernet header, or the 4 extra bytes of an encapsulation tag,
+ * shifts all of this by a whole number of 16-bit units.
+ */
+ { "PSP outer IPv6 saddr", 191, 544 },
+ { "PSP outer IPv6 daddr", 319, 544 },
+ { "PSP inner sport", 527, 544 },
+ { "PSP inner dport", 543, 544 },
+};
+
+static bool rss_key_test_bit(const u8 *buf, unsigned int bit)
+{
+ return buf[bit / BITS_PER_BYTE] & (0x80 >> (bit % BITS_PER_BYTE));
+}
+
+static void rss_key_test_assign_bit(u8 *buf, unsigned int bit, bool value)
+{
+ u8 mask = 0x80 >> (bit % BITS_PER_BYTE);
+
+ if (value)
+ buf[bit / BITS_PER_BYTE] |= mask;
+ else
+ buf[bit / BITS_PER_BYTE] &= ~mask;
+}
+
+/* The 32 key bits starting at @bit, which is what input bit @bit contributes
+ * to the hash.
+ */
+static u32 rss_key_test_window(const u8 *key, unsigned int bit)
+{
+ u32 window = 0;
+ unsigned int i;
+
+ for (i = 0; i < 32; i++)
+ window = (window << 1) | rss_key_test_bit(key, bit + i);
+
+ return window;
+}
+
+static u32 rss_key_test_toeplitz(const u8 *key, const u8 *input,
+ unsigned int nbits)
+{
+ u32 hash = 0;
+ unsigned int i;
+
+ for (i = 0; i < nbits; i++)
+ if (rss_key_test_bit(input, i))
+ hash ^= rss_key_test_window(key, i);
+
+ return hash;
+}
+
+/* Is the map from the q low order bits of the field at @lsb to the q low order
+ * bits of the hash a bijection? Gaussian elimination over GF(2) on the q
+ * windows involved, reduced to their q low order bits.
+ */
+static bool rss_key_test_full_rank(const u8 *key, unsigned int lsb,
+ unsigned int q)
+{
+ u32 basis[NETDEV_RSS_KEY_QMAX] = {};
+ unsigned int j;
+
+ for (j = 0; j < q; j++) {
+ u32 v = rss_key_test_window(key, lsb - j) & (BIT(q) - 1);
+
+ while (v) {
+ unsigned int b = __ffs(v);
+
+ if (!basis[b]) {
+ basis[b] = v;
+ break;
+ }
+ v ^= basis[b];
+ }
+
+ if (!v)
+ return false;
+ }
+
+ return true;
+}
+
+/* Degenerate keys the rank check must reject, so that a check accepting
+ * everything can not make the other tests pass.
+ */
+static void rss_key_checker_test(struct kunit *test)
+{
+ u8 *key = kunit_kzalloc(test, NETDEV_RSS_KEY_LEN, GFP_KERNEL);
+
+ KUNIT_ASSERT_NOT_NULL(test, key);
+
+ /* All the windows are zero. */
+ KUNIT_EXPECT_FALSE(test, rss_key_test_full_rank(key, 31, 1));
+
+ /* All the windows are equal, which is enough for one queue only. */
+ memset(key, 0xff, NETDEV_RSS_KEY_LEN);
+ KUNIT_EXPECT_TRUE(test, rss_key_test_full_rank(key, 31, 1));
+ KUNIT_EXPECT_FALSE(test, rss_key_test_full_rank(key, 31, 2));
+}
+
+static void rss_key_property_test(struct kunit *test)
+{
+ u8 *key = kunit_kzalloc(test, NETDEV_RSS_KEY_LEN, GFP_KERNEL);
+ unsigned int i, j, q;
+
+ KUNIT_ASSERT_NOT_NULL(test, key);
+
+ for (i = 0; i < RSS_KEY_TEST_KEYS; i++) {
+ netdev_rss_key_init(key, NETDEV_RSS_KEY_LEN);
+
+ for (j = 0; j < ARRAY_SIZE(rss_key_test_fields); j++) {
+ const struct rss_key_test_field *f;
+
+ f = &rss_key_test_fields[j];
+
+ for (q = 1; q <= NETDEV_RSS_KEY_QMAX; q++)
+ KUNIT_ASSERT_TRUE_MSG(test,
+ rss_key_test_full_rank(key, f->lsb, q),
+ "%s does not spread over %u queues",
+ f->name, 1U << q);
+ }
+ }
+}
+
+/* rss_key_test_fields[] can only list the layouts somebody thought of, but
+ * the generator does not get to know what the hardware hashes. Sweep the
+ * whole key instead: the property has to hold at every 16-bit aligned
+ * position, which is where a field of any layout can end.
+ */
+static void rss_key_grid_test(struct kunit *test)
+{
+ unsigned int bits = NETDEV_RSS_KEY_LEN * BITS_PER_BYTE;
+ u8 *key = kunit_kzalloc(test, NETDEV_RSS_KEY_LEN, GFP_KERNEL);
+ unsigned int i, lsb, q;
+
+ KUNIT_ASSERT_NOT_NULL(test, key);
+
+ for (i = 0; i < RSS_KEY_TEST_KEYS; i++) {
+ netdev_rss_key_init(key, NETDEV_RSS_KEY_LEN);
+
+ for (lsb = 15; lsb + 32 <= bits; lsb += 16)
+ for (q = 1; q <= NETDEV_RSS_KEY_QMAX; q++)
+ KUNIT_ASSERT_TRUE_MSG(test,
+ rss_key_test_full_rank(key, lsb, q),
+ "field ending at bit %u does not spread over %u queues",
+ lsb, 1U << q);
+ }
+}
+
+static int rss_key_test_cmp(const void *a, const void *b)
+{
+ u32 x = *(const u32 *)a, y = *(const u32 *)b;
+
+ return x < y ? -1 : x > y;
+}
+
+/* Two input bits contributing the same 32-bit window are indistinguishable
+ * to the hash: flipping both of them leaves it unchanged, so the flows of a
+ * burst differing in exactly those two bits all collide. A uniformly random
+ * key has such a pair with probability 2 ** -11, and the generated key must
+ * not do worse.
+ *
+ * netdev_rss_key_init() redraws on a collision at a distance that is a
+ * multiple of 8, which is where the fixup makes one likely, and leaves every
+ * other distance at the odds of a random key. So assert on what it
+ * guarantees: group the windows by their offset modulo 8 and sort each group
+ * on its own. Sorting all of them together instead would be asserting on the
+ * random odds, and would fail about one run in 26 on a correct kernel.
+ */
+static void rss_key_alias_test(struct kunit *test)
+{
+ unsigned int count = NETDEV_RSS_KEY_LEN * BITS_PER_BYTE - 31;
+ u8 *key = kunit_kzalloc(test, NETDEV_RSS_KEY_LEN, GFP_KERNEL);
+ unsigned int i, j, n, r;
+ u32 *windows;
+
+ windows = kunit_kcalloc(test, count, sizeof(*windows), GFP_KERNEL);
+ KUNIT_ASSERT_NOT_NULL(test, key);
+ KUNIT_ASSERT_NOT_NULL(test, windows);
+
+ for (i = 0; i < RSS_KEY_TEST_KEYS; i++) {
+ netdev_rss_key_init(key, NETDEV_RSS_KEY_LEN);
+
+ for (r = 0; r < 8; r++) {
+ n = 0;
+ for (j = r; j < count; j += 8)
+ windows[n++] = rss_key_test_window(key, j);
+
+ sort(windows, n, sizeof(*windows),
+ rss_key_test_cmp, NULL);
+
+ for (j = 1; j < n; j++)
+ KUNIT_ASSERT_NE_MSG(test, windows[j],
+ windows[j - 1],
+ "two input bits a multiple of 8 apart read the same key window %08x",
+ windows[j]);
+ }
+ }
+}
+
+/* Hash the inputs of a burst differing only in the low order bits of one
+ * field, and check that they fill the indirection table evenly.
+ */
+static void rss_key_spread_test(struct kunit *test)
+{
+ u8 *key = kunit_kzalloc(test, NETDEV_RSS_KEY_LEN, GFP_KERNEL);
+ u8 *input = kunit_kzalloc(test, RSS_KEY_TEST_INPUT_LEN, GFP_KERNEL);
+ unsigned int i, j, q;
+
+ KUNIT_ASSERT_NOT_NULL(test, key);
+ KUNIT_ASSERT_NOT_NULL(test, input);
+
+ netdev_rss_key_init(key, NETDEV_RSS_KEY_LEN);
+
+ for (i = 0; i < ARRAY_SIZE(rss_key_test_fields); i++) {
+ const struct rss_key_test_field *f = &rss_key_test_fields[i];
+
+ for (q = 1; q <= RSS_KEY_TEST_SPREAD_QMAX; q++) {
+ u64 seen = 0;
+
+ get_random_bytes(input, RSS_KEY_TEST_INPUT_LEN);
+
+ for (j = 0; j < (1U << q); j++) {
+ unsigned int t, queue;
+ u32 hash;
+
+ for (t = 0; t < q; t++)
+ rss_key_test_assign_bit(input,
+ f->lsb - t,
+ j & BIT(t));
+
+ hash = rss_key_test_toeplitz(key, input,
+ f->nbits);
+ queue = hash & (BIT(q) - 1);
+
+ KUNIT_ASSERT_FALSE_MSG(test, seen & BIT_ULL(queue),
+ "%s hits queue %u twice out of %u",
+ f->name, queue, 1U << q);
+ seen |= BIT_ULL(queue);
+ }
+ }
+ }
+}
+
+static struct kunit_case rss_key_test_cases[] = {
+ KUNIT_CASE(rss_key_checker_test),
+ KUNIT_CASE(rss_key_property_test),
+ KUNIT_CASE(rss_key_grid_test),
+ KUNIT_CASE(rss_key_alias_test),
+ KUNIT_CASE(rss_key_spread_test),
+ {},
+};
+
+static struct kunit_suite rss_key_test_suite = {
+ .name = "ethtool-rss-key",
+ .test_cases = rss_key_test_cases,
+};
+
+kunit_test_suite(rss_key_test_suite);
+
+MODULE_DESCRIPTION("Tests for the RSS key generated by netdev_rss_key_fill()");
+MODULE_LICENSE("GPL");