[PATCH nf 0/3] nft_set_pipapo: fix incorrect avx2 match of 5th field octet

[PATCH nf 0/3] nft_set_pipapo: fix incorrect avx2 match of 5th field octet

[Florian Westphal]

Sontu Mazumdar reports incorrect matching in the pipapo set type.

First patch adds debug infrastructure (conditional for CONFIG_DEBUG_NET)
to add rudimentary avx register tracking.

Second patch is the actual fix.

Third patch adds a test case.

I checked that selftest passes with all three patches applied,
that the new selftest fails without the fix and that the
register tracking added in patch 1 also produces a WARN splat.

Florian Westphal (3):
  nft_set_pipapo: add avx register usage tracking for NET_DEBUG builds
  nft_set_pipapo: fix incorrect avx2 match of 5th field octet
  selftests: netfilter: add test case for recent mismatch bug

 net/netfilter/nft_set_pipapo_avx2.c           | 139 +++++++++++++++++-
 .../net/netfilter/nft_concat_range.sh         |  39 ++++-
 2 files changed, 171 insertions(+), 7 deletions(-)

-- 
2.49.0

[PATCH nf 1/3] nft_set_pipapo: add avx register usage tracking for NET_DEBUG builds

[Florian Westphal]

Add rudimentary register tracking for avx2 helpers.

A register can have following states:
- mem (contains packet data)
- and (was consumed, value folded into other register)
- tmp (holds result of folding operation)

Warn if
a) register store happens while register has 'mem' bit set
   but 'and' unset
b) register is examined but wasn't written to
c) register is folded into another register but wasn't written to

This is off unless NET_DEBUG=y is set.

Signed-off-by: Florian Westphal <fw@strlen.de>
---
 net/netfilter/nft_set_pipapo_avx2.c | 136 +++++++++++++++++++++++++++-
 1 file changed, 131 insertions(+), 5 deletions(-)

diff --git a/net/netfilter/nft_set_pipapo_avx2.c b/net/netfilter/nft_set_pipapo_avx2.c
index b8d3c3213efe..8ce7154b678a 100644
--- a/net/netfilter/nft_set_pipapo_avx2.c
+++ b/net/netfilter/nft_set_pipapo_avx2.c
@@ -26,6 +26,109 @@
 
 #define NFT_PIPAPO_LONGS_PER_M256	(XSAVE_YMM_SIZE / BITS_PER_LONG)
 
+#if defined(CONFIG_DEBUG_NET)
+struct nft_pipapo_debug_regmap {
+	unsigned long mem;			/* register store: reg := mem (packet data) */
+	unsigned long and;			/* register used as and operator */
+	unsigned long tmp;			/* register used as and destination */
+};
+
+/* yym15 is used as an always-0-register, see nft_pipapo_avx2_prepare */
+#define	NFT_PIPAPO_AVX2_DEBUG_MAP	struct nft_pipapo_debug_regmap __pipapo_debug_regmap = { .mem = 1 << 15 }
+
+#define NFT_PIPAPO_WARN(cond, reg, message)						\
+	DEBUG_NET_WARN_ONCE((cond), "reg %d %s, mem %08lx, and %08lx tmp %08lx",	\
+		  (reg), (message), __pipapo_debug_regmap.mem, __pipapo_debug_regmap.and, __pipapo_debug_regmap.tmp)
+
+/**
+ * nft_pipapo_avx2_debug_load() - record a store to reg
+ *
+ * @reg: the register being written to
+ *
+ * Return: true if splat needs to be triggered
+ */
+static inline bool nft_pipapo_avx2_debug_load(unsigned int reg,
+					      struct nft_pipapo_debug_regmap *r)
+{
+	bool anded, used, tmp;
+
+	anded = test_bit(reg, &r->and);
+	used = test_bit(reg, &r->mem);
+	tmp = test_bit(reg, &r->tmp);
+
+	anded = test_and_clear_bit(reg, &r->and);
+	tmp = test_and_clear_bit(reg, &r->tmp);
+	used = test_and_set_bit(reg, &r->mem);
+
+	if (!used) /* Not used -> ok, no warning needs to be emitted. */
+		return false;
+
+	/* Register is clobbered, Warning needs to be emitted if it wasn't AND'ed */
+	return !anded;
+}
+
+/**
+ * nft_pipapo_avx2_debug_and() - mark registers as being ANDed
+ *
+ * @reg1: the register being written to
+ * @reg2: the first register being anded
+ * @reg3: the second register being anded
+ *
+ * Tags @reg2 and @reg3 as ANDed register
+ * Tags @reg1 as containing AND result
+ *
+ * Return: true if splat needs to be triggered
+ */
+static inline bool nft_pipapo_avx2_debug_and(unsigned int reg1, unsigned int reg2,
+					     unsigned int reg3,
+					     struct nft_pipapo_debug_regmap *r)
+{
+	bool r2_and = test_and_set_bit(reg2, &r->and);
+	bool r3_and = test_and_set_bit(reg3, &r->and);
+	bool r2_tmp = test_and_set_bit(reg2, &r->tmp);
+	bool r3_tmp = test_and_set_bit(reg3, &r->tmp);
+	bool r2_mem = test_bit(reg2, &r->mem);
+	bool r3_mem = test_bit(reg3, &r->mem);
+
+	clear_bit(reg1, &r->mem);
+	set_bit(reg1, &r->tmp);
+
+	return (!r2_mem && !r2_and && !r2_tmp) || (!r3_mem && !r3_and && !r3_tmp);
+}
+
+/* saw a load, ok if register hasn't been used (mem bit not set)
+ * or if the register was anded to another register (mem_and is set).
+ */
+#define	NFT_PIPAPO_AVX2_SAW_LOAD(reg)	({	\
+	unsigned int r__ = (reg);		\
+	NFT_PIPAPO_WARN(nft_pipapo_avx2_debug_load(r__, &__pipapo_debug_regmap), r__, "busy");\
+})
+
+static inline bool nft_pipapo_avx2_debug_usable(unsigned int reg,
+						const struct nft_pipapo_debug_regmap *r)
+{
+	unsigned long u = r->mem | r->and | r->tmp;
+
+	return !test_bit(reg, &u);
+}
+
+#define NFT_PIPAPO_AVX2_USABLE(reg) ({			\
+	unsigned int r__ = (reg);			\
+	NFT_PIPAPO_WARN(nft_pipapo_avx2_debug_usable(r__, &__pipapo_debug_regmap), r__, "undef");\
+})
+
+#define NFT_PIPAPO_AVX2_AND_DEBUG(dst, a, b) ({		\
+	unsigned int r__ = (dst);			\
+	NFT_PIPAPO_WARN(nft_pipapo_avx2_debug_and(r__, (a), (b), &__pipapo_debug_regmap), r__, "invalid sreg");\
+})
+
+#else
+#define	NFT_PIPAPO_AVX2_SAW_LOAD(reg)		BUILD_BUG_ON_INVALID(reg)
+#define	NFT_PIPAPO_AVX2_USABLE(reg)		BUILD_BUG_ON_INVALID(reg)
+#define NFT_PIPAPO_AVX2_AND_DEBUG(dst, a, b)	BUILD_BUG_ON_INVALID((dst) | (a) | (b))
+#define	NFT_PIPAPO_AVX2_DEBUG_MAP		do { } while (0)
+#endif
+
 /* Load from memory into YMM register with non-temporal hint ("stream load"),
  * that is, don't fetch lines from memory into the cache. This avoids pushing
  * precious packet data out of the cache hierarchy, and is appropriate when:
@@ -37,7 +140,10 @@
  *   again
  */
 #define NFT_PIPAPO_AVX2_LOAD(reg, loc)					\
-	asm volatile("vmovntdqa %0, %%ymm" #reg : : "m" (loc))
+do {									\
+	asm volatile("vmovntdqa %0, %%ymm" #reg : : "m" (loc));		\
+	NFT_PIPAPO_AVX2_SAW_LOAD(reg);					\
+} while (0)
 
 /* Stream a single lookup table bucket into YMM register given lookup table,
  * group index, value of packet bits, bucket size.
@@ -53,19 +159,29 @@
 
 /* Bitwise AND: the staple operation of this algorithm */
 #define NFT_PIPAPO_AVX2_AND(dst, a, b)					\
-	asm volatile("vpand %ymm" #a ", %ymm" #b ", %ymm" #dst)
+do {									\
+	BUILD_BUG_ON(a == b);						\
+	asm volatile("vpand %ymm" #a ", %ymm" #b ", %ymm" #dst);	\
+	NFT_PIPAPO_AVX2_AND_DEBUG(dst, a, b);				\
+} while (0)
 
 /* Jump to label if @reg is zero */
 #define NFT_PIPAPO_AVX2_NOMATCH_GOTO(reg, label)			\
-	asm goto("vptest %%ymm" #reg ", %%ymm" #reg ";"	\
-			  "je %l[" #label "]" : : : : label)
+do {									\
+	NFT_PIPAPO_AVX2_USABLE(reg);					\
+	asm goto("vptest %%ymm" #reg ", %%ymm" #reg ";"			\
+			  "je %l[" #label "]" : : : : label);		\
+} while (0)
 
 /* Store 256 bits from YMM register into memory. Contrary to bucket load
  * operation, we don't bypass the cache here, as stored matching results
  * are always used shortly after.
  */
 #define NFT_PIPAPO_AVX2_STORE(loc, reg)					\
-	asm volatile("vmovdqa %%ymm" #reg ", %0" : "=m" (loc))
+do {									\
+	NFT_PIPAPO_AVX2_USABLE(reg);					\
+	asm volatile("vmovdqa %%ymm" #reg ", %0" : "=m" (loc));		\
+} while (0)
 
 /* Zero out a complete YMM register, @reg */
 #define NFT_PIPAPO_AVX2_ZERO(reg)					\
@@ -219,6 +335,7 @@ static int nft_pipapo_avx2_lookup_4b_2(unsigned long *map, unsigned long *fill,
 	int i, ret = -1, m256_size = f->bsize / NFT_PIPAPO_LONGS_PER_M256, b;
 	u8 pg[2] = { pkt[0] >> 4, pkt[0] & 0xf };
 	unsigned long *lt = f->lt, bsize = f->bsize;
+	NFT_PIPAPO_AVX2_DEBUG_MAP;
 
 	lt += offset * NFT_PIPAPO_LONGS_PER_M256;
 	for (i = offset; i < m256_size; i++, lt += NFT_PIPAPO_LONGS_PER_M256) {
@@ -282,6 +399,7 @@ static int nft_pipapo_avx2_lookup_4b_4(unsigned long *map, unsigned long *fill,
 	int i, ret = -1, m256_size = f->bsize / NFT_PIPAPO_LONGS_PER_M256, b;
 	u8 pg[4] = { pkt[0] >> 4, pkt[0] & 0xf, pkt[1] >> 4, pkt[1] & 0xf };
 	unsigned long *lt = f->lt, bsize = f->bsize;
+	NFT_PIPAPO_AVX2_DEBUG_MAP;
 
 	lt += offset * NFT_PIPAPO_LONGS_PER_M256;
 	for (i = offset; i < m256_size; i++, lt += NFT_PIPAPO_LONGS_PER_M256) {
@@ -361,6 +479,7 @@ static int nft_pipapo_avx2_lookup_4b_8(unsigned long *map, unsigned long *fill,
 		   };
 	int i, ret = -1, m256_size = f->bsize / NFT_PIPAPO_LONGS_PER_M256, b;
 	unsigned long *lt = f->lt, bsize = f->bsize;
+	NFT_PIPAPO_AVX2_DEBUG_MAP;
 
 	lt += offset * NFT_PIPAPO_LONGS_PER_M256;
 	for (i = offset; i < m256_size; i++, lt += NFT_PIPAPO_LONGS_PER_M256) {
@@ -458,6 +577,7 @@ static int nft_pipapo_avx2_lookup_4b_12(unsigned long *map, unsigned long *fill,
 		    };
 	int i, ret = -1, m256_size = f->bsize / NFT_PIPAPO_LONGS_PER_M256, b;
 	unsigned long *lt = f->lt, bsize = f->bsize;
+	NFT_PIPAPO_AVX2_DEBUG_MAP;
 
 	lt += offset * NFT_PIPAPO_LONGS_PER_M256;
 	for (i = offset; i < m256_size; i++, lt += NFT_PIPAPO_LONGS_PER_M256) {
@@ -553,6 +673,7 @@ static int nft_pipapo_avx2_lookup_4b_32(unsigned long *map, unsigned long *fill,
 		    };
 	int i, ret = -1, m256_size = f->bsize / NFT_PIPAPO_LONGS_PER_M256, b;
 	unsigned long *lt = f->lt, bsize = f->bsize;
+	NFT_PIPAPO_AVX2_DEBUG_MAP;
 
 	lt += offset * NFT_PIPAPO_LONGS_PER_M256;
 	for (i = offset; i < m256_size; i++, lt += NFT_PIPAPO_LONGS_PER_M256) {
@@ -680,6 +801,7 @@ static int nft_pipapo_avx2_lookup_8b_1(unsigned long *map, unsigned long *fill,
 {
 	int i, ret = -1, m256_size = f->bsize / NFT_PIPAPO_LONGS_PER_M256, b;
 	unsigned long *lt = f->lt, bsize = f->bsize;
+	NFT_PIPAPO_AVX2_DEBUG_MAP;
 
 	lt += offset * NFT_PIPAPO_LONGS_PER_M256;
 	for (i = offset; i < m256_size; i++, lt += NFT_PIPAPO_LONGS_PER_M256) {
@@ -738,6 +860,7 @@ static int nft_pipapo_avx2_lookup_8b_2(unsigned long *map, unsigned long *fill,
 {
 	int i, ret = -1, m256_size = f->bsize / NFT_PIPAPO_LONGS_PER_M256, b;
 	unsigned long *lt = f->lt, bsize = f->bsize;
+	NFT_PIPAPO_AVX2_DEBUG_MAP;
 
 	lt += offset * NFT_PIPAPO_LONGS_PER_M256;
 	for (i = offset; i < m256_size; i++, lt += NFT_PIPAPO_LONGS_PER_M256) {
@@ -803,6 +926,7 @@ static int nft_pipapo_avx2_lookup_8b_4(unsigned long *map, unsigned long *fill,
 {
 	int i, ret = -1, m256_size = f->bsize / NFT_PIPAPO_LONGS_PER_M256, b;
 	unsigned long *lt = f->lt, bsize = f->bsize;
+	NFT_PIPAPO_AVX2_DEBUG_MAP;
 
 	lt += offset * NFT_PIPAPO_LONGS_PER_M256;
 	for (i = offset; i < m256_size; i++, lt += NFT_PIPAPO_LONGS_PER_M256) {
@@ -879,6 +1003,7 @@ static int nft_pipapo_avx2_lookup_8b_6(unsigned long *map, unsigned long *fill,
 {
 	int i, ret = -1, m256_size = f->bsize / NFT_PIPAPO_LONGS_PER_M256, b;
 	unsigned long *lt = f->lt, bsize = f->bsize;
+	NFT_PIPAPO_AVX2_DEBUG_MAP;
 
 	lt += offset * NFT_PIPAPO_LONGS_PER_M256;
 	for (i = offset; i < m256_size; i++, lt += NFT_PIPAPO_LONGS_PER_M256) {
@@ -965,6 +1090,7 @@ static int nft_pipapo_avx2_lookup_8b_16(unsigned long *map, unsigned long *fill,
 {
 	int i, ret = -1, m256_size = f->bsize / NFT_PIPAPO_LONGS_PER_M256, b;
 	unsigned long *lt = f->lt, bsize = f->bsize;
+	NFT_PIPAPO_AVX2_DEBUG_MAP;
 
 	lt += offset * NFT_PIPAPO_LONGS_PER_M256;
 	for (i = offset; i < m256_size; i++, lt += NFT_PIPAPO_LONGS_PER_M256) {
-- 
2.49.0

Re: [PATCH nf 1/3] nft_set_pipapo: add avx register usage tracking for NET_DEBUG builds

[Stefano Brivio]

Mostly nits:

On Fri,  4 Apr 2025 08:20:52 +0200
Florian Westphal <fw@strlen.de> wrote:

> Add rudimentary register tracking for avx2 helpers.
> 
> A register can have following states:
> - mem (contains packet data)
> - and (was consumed, value folded into other register)
> - tmp (holds result of folding operation)
> 
> Warn if
> a) register store happens while register has 'mem' bit set
>    but 'and' unset
> b) register is examined but wasn't written to
> c) register is folded into another register but wasn't written to

Thanks, this looks very useful... especially in hindsight. :)

> This is off unless NET_DEBUG=y is set.
> 
> Signed-off-by: Florian Westphal <fw@strlen.de>
> ---
>  net/netfilter/nft_set_pipapo_avx2.c | 136 +++++++++++++++++++++++++++-
>  1 file changed, 131 insertions(+), 5 deletions(-)
> 
> diff --git a/net/netfilter/nft_set_pipapo_avx2.c b/net/netfilter/nft_set_pipapo_avx2.c
> index b8d3c3213efe..8ce7154b678a 100644
> --- a/net/netfilter/nft_set_pipapo_avx2.c
> +++ b/net/netfilter/nft_set_pipapo_avx2.c
> @@ -26,6 +26,109 @@
>  
>  #define NFT_PIPAPO_LONGS_PER_M256	(XSAVE_YMM_SIZE / BITS_PER_LONG)
>  
> +#if defined(CONFIG_DEBUG_NET)

This made me wonder if there's any specific reason why we would need
#if defined(x) here instead of a common #ifdef x. It looks like there
isn't a reason, so maybe #ifdef CONFIG_DEBUG_NET is more... expected.

> +struct nft_pipapo_debug_regmap {

It would be nice to have those comments in kerneldoc style for
consistency with everything else:

/**
 * struct nft_pipapo_debug_regmap - Bitmaps representing sets of YMM registers

> +	unsigned long mem;			/* register store: reg := mem (packet data) */

...and here it took me a while to understand that, if the bit is set,
the register was *already used* for a store, perhaps:

 * @mem:	n-th bit set if YMM<n> was loaded from memory (packet data)

> +	unsigned long and;			/* register used as and operator */
> +	unsigned long tmp;			/* register used as and destination */

Capitalising "and" would make this more readable I think, say:

 * @and:	YMM<n> already used as AND operand

Perhaps those could all be uint16_t to reflect that it's YMM registers,
and nft_pipapo_avx2_debug_usable() could simply promote them to
unsigned long as needed by test_bit().

They could even be uint32_t to represent ZMM registers (or extended
YMM) if we want to make this AVX512-ready, I'm not sure.

> +};
> +
> +/* yym15 is used as an always-0-register, see nft_pipapo_avx2_prepare */

That's ymm15 or YMM15. nft_pipapo_avx2_prepare().

> +#define	NFT_PIPAPO_AVX2_DEBUG_MAP	struct nft_pipapo_debug_regmap __pipapo_debug_regmap = { .mem = 1 << 15 }

I guess it would be nice to have all this wrapped to 80 columns unless
it particularly bothers you. If it doesn't:

#define NFT_PIPAPO_AVX2_DEBUG_MAP					\
	struct nft_pipapo_debug_regmap __pipapo_debug_regmap = {	\
		.mem = BIT(15),						\
	}

> +
> +#define NFT_PIPAPO_WARN(cond, reg, message)						\
> +	DEBUG_NET_WARN_ONCE((cond), "reg %d %s, mem %08lx, and %08lx tmp %08lx",	\
> +		  (reg), (message), __pipapo_debug_regmap.mem, __pipapo_debug_regmap.and, __pipapo_debug_regmap.tmp)
> +
> +/**
> + * nft_pipapo_avx2_debug_load() - record a store to reg

I would say it does more than that, say,

 * nft_pipapo_avx2_debug_load() - Record a store to register, check its validity

?

> + *
> + * @reg: the register being written to

 * @r: Current bitmap of registers for debugging purposes

> + *
> + * Return: true if splat needs to be triggered
> + */
> +static inline bool nft_pipapo_avx2_debug_load(unsigned int reg,
> +					      struct nft_pipapo_debug_regmap *r)
> +{
> +	bool anded, used, tmp;
> +
> +	anded = test_bit(reg, &r->and);
> +	used = test_bit(reg, &r->mem);
> +	tmp = test_bit(reg, &r->tmp);

These shouldn't touch the bitmaps, so...

> +	anded = test_and_clear_bit(reg, &r->and);
> +	tmp = test_and_clear_bit(reg, &r->tmp);
> +	used = test_and_set_bit(reg, &r->mem);

it looks like the test_bit() checks above are a left-over without
effect, unless I'm missing something.

Shouldn't we warn if tmp is true, and, in nft_pipapo_avx2_debug_and(),
clear the bit once the destination/temporary register was in turn ANDed?

Otherwise we could clobber a valid temporary register, I guess.

> +
> +	if (!used) /* Not used -> ok, no warning needs to be emitted. */
> +		return false;
> +
> +	/* Register is clobbered, Warning needs to be emitted if it wasn't AND'ed */

warning

> +	return !anded;
> +}
> +
> +/**
> + * nft_pipapo_avx2_debug_and() - mark registers as being ANDed
> + *
> + * @reg1: the register being written to
> + * @reg2: the first register being anded
> + * @reg3: the second register being anded

NFT_PIPAPO_AVX2_AND() uses @dst, @a, @b. We could use the same here for
consistency.

> + *
> + * Tags @reg2 and @reg3 as ANDed register
> + * Tags @reg1 as containing AND result
> + *
> + * Return: true if splat needs to be triggered
> + */
> +static inline bool nft_pipapo_avx2_debug_and(unsigned int reg1, unsigned int reg2,
> +					     unsigned int reg3,
> +					     struct nft_pipapo_debug_regmap *r)
> +{
> +	bool r2_and = test_and_set_bit(reg2, &r->and);
> +	bool r3_and = test_and_set_bit(reg3, &r->and);
> +	bool r2_tmp = test_and_set_bit(reg2, &r->tmp);
> +	bool r3_tmp = test_and_set_bit(reg3, &r->tmp);

I thought you would just set BIT(reg1) in r->tmp as a result: r2 and r3
are not used as destination/temporary. Or maybe I misunderstood the
description of 'tmp'.

> +	bool r2_mem = test_bit(reg2, &r->mem);
> +	bool r3_mem = test_bit(reg3, &r->mem);
> +
> +	clear_bit(reg1, &r->mem);
> +	set_bit(reg1, &r->tmp);
> +
> +	return (!r2_mem && !r2_and && !r2_tmp) || (!r3_mem && !r3_and && !r3_tmp);
> +}
> +
> +/* saw a load, ok if register hasn't been used (mem bit not set)
> + * or if the register was anded to another register (mem_and is set).
> + */
> +#define	NFT_PIPAPO_AVX2_SAW_LOAD(reg)	({	\
> +	unsigned int r__ = (reg);		\
> +	NFT_PIPAPO_WARN(nft_pipapo_avx2_debug_load(r__, &__pipapo_debug_regmap), r__, "busy");\

Same here, I would wrap at 80 columns if doable and not annoying.

> +})
> +

/**
 * nft_pipapo_avx2_debug_usable() - @reg usable as temporary or for memory load?
 * @reg:	Index of register
 * Return: true if register is free for usage
 */

> +static inline bool nft_pipapo_avx2_debug_usable(unsigned int reg,
> +						const struct nft_pipapo_debug_regmap *r)
> +{
> +	unsigned long u = r->mem | r->and | r->tmp;
> +
> +	return !test_bit(reg, &u);
> +}
> +
> +#define NFT_PIPAPO_AVX2_USABLE(reg) ({			\
> +	unsigned int r__ = (reg);			\
> +	NFT_PIPAPO_WARN(nft_pipapo_avx2_debug_usable(r__, &__pipapo_debug_regmap), r__, "undef");\
> +})
> +
> +#define NFT_PIPAPO_AVX2_AND_DEBUG(dst, a, b) ({		\
> +	unsigned int r__ = (dst);			\
> +	NFT_PIPAPO_WARN(nft_pipapo_avx2_debug_and(r__, (a), (b), &__pipapo_debug_regmap), r__, "invalid sreg");\
> +})
> +
> +#else

I guess it would be practical to mark this as /* !CONFIG_DEBUG_NET */

> +#define	NFT_PIPAPO_AVX2_SAW_LOAD(reg)		BUILD_BUG_ON_INVALID(reg)
> +#define	NFT_PIPAPO_AVX2_USABLE(reg)		BUILD_BUG_ON_INVALID(reg)

I'm not sure if there's much value in indenting those with an extra tab.

> +#define NFT_PIPAPO_AVX2_AND_DEBUG(dst, a, b)	BUILD_BUG_ON_INVALID((dst) | (a) | (b))
> +#define	NFT_PIPAPO_AVX2_DEBUG_MAP		do { } while (0)
> +#endif
> +
>  /* Load from memory into YMM register with non-temporal hint ("stream load"),
>   * that is, don't fetch lines from memory into the cache. This avoids pushing
>   * precious packet data out of the cache hierarchy, and is appropriate when:
> @@ -37,7 +140,10 @@
>   *   again
>   */
>  #define NFT_PIPAPO_AVX2_LOAD(reg, loc)					\
> -	asm volatile("vmovntdqa %0, %%ymm" #reg : : "m" (loc))
> +do {									\
> +	asm volatile("vmovntdqa %0, %%ymm" #reg : : "m" (loc));		\
> +	NFT_PIPAPO_AVX2_SAW_LOAD(reg);					\
> +} while (0)
>  
>  /* Stream a single lookup table bucket into YMM register given lookup table,
>   * group index, value of packet bits, bucket size.
> @@ -53,19 +159,29 @@
>  
>  /* Bitwise AND: the staple operation of this algorithm */
>  #define NFT_PIPAPO_AVX2_AND(dst, a, b)					\
> -	asm volatile("vpand %ymm" #a ", %ymm" #b ", %ymm" #dst)
> +do {									\
> +	BUILD_BUG_ON(a == b);						\
> +	asm volatile("vpand %ymm" #a ", %ymm" #b ", %ymm" #dst);	\
> +	NFT_PIPAPO_AVX2_AND_DEBUG(dst, a, b);				\
> +} while (0)
>  
>  /* Jump to label if @reg is zero */
>  #define NFT_PIPAPO_AVX2_NOMATCH_GOTO(reg, label)			\
> -	asm goto("vptest %%ymm" #reg ", %%ymm" #reg ";"	\
> -			  "je %l[" #label "]" : : : : label)
> +do {									\
> +	NFT_PIPAPO_AVX2_USABLE(reg);					\

Here, I'm definitely missing something, because this works but I'm not
sure why.

I thought that nft_pipapo_avx2_debug_usable() would return true iff the
register is _free_.

But it must be a valid temporary (in 'tmp', right?) if we use vptest on
it. So it should *not* be "usable" (as destination), right? Or maybe I
misunderstood the role of 'tmp' altogether.

> +	asm goto("vptest %%ymm" #reg ", %%ymm" #reg ";"			\
> +			  "je %l[" #label "]" : : : : label);		\
> +} while (0)
>  
>  /* Store 256 bits from YMM register into memory. Contrary to bucket load
>   * operation, we don't bypass the cache here, as stored matching results
>   * are always used shortly after.
>   */
>  #define NFT_PIPAPO_AVX2_STORE(loc, reg)					\
> -	asm volatile("vmovdqa %%ymm" #reg ", %0" : "=m" (loc))
> +do {									\
> +	NFT_PIPAPO_AVX2_USABLE(reg);					\
> +	asm volatile("vmovdqa %%ymm" #reg ", %0" : "=m" (loc));		\
> +} while (0)
>  
>  /* Zero out a complete YMM register, @reg */
>  #define NFT_PIPAPO_AVX2_ZERO(reg)					\
> @@ -219,6 +335,7 @@ static int nft_pipapo_avx2_lookup_4b_2(unsigned long *map, unsigned long *fill,
>  	int i, ret = -1, m256_size = f->bsize / NFT_PIPAPO_LONGS_PER_M256, b;
>  	u8 pg[2] = { pkt[0] >> 4, pkt[0] & 0xf };
>  	unsigned long *lt = f->lt, bsize = f->bsize;
> +	NFT_PIPAPO_AVX2_DEBUG_MAP;
>  
>  	lt += offset * NFT_PIPAPO_LONGS_PER_M256;
>  	for (i = offset; i < m256_size; i++, lt += NFT_PIPAPO_LONGS_PER_M256) {
> @@ -282,6 +399,7 @@ static int nft_pipapo_avx2_lookup_4b_4(unsigned long *map, unsigned long *fill,
>  	int i, ret = -1, m256_size = f->bsize / NFT_PIPAPO_LONGS_PER_M256, b;
>  	u8 pg[4] = { pkt[0] >> 4, pkt[0] & 0xf, pkt[1] >> 4, pkt[1] & 0xf };
>  	unsigned long *lt = f->lt, bsize = f->bsize;
> +	NFT_PIPAPO_AVX2_DEBUG_MAP;
>  
>  	lt += offset * NFT_PIPAPO_LONGS_PER_M256;
>  	for (i = offset; i < m256_size; i++, lt += NFT_PIPAPO_LONGS_PER_M256) {
> @@ -361,6 +479,7 @@ static int nft_pipapo_avx2_lookup_4b_8(unsigned long *map, unsigned long *fill,
>  		   };
>  	int i, ret = -1, m256_size = f->bsize / NFT_PIPAPO_LONGS_PER_M256, b;
>  	unsigned long *lt = f->lt, bsize = f->bsize;
> +	NFT_PIPAPO_AVX2_DEBUG_MAP;
>  
>  	lt += offset * NFT_PIPAPO_LONGS_PER_M256;
>  	for (i = offset; i < m256_size; i++, lt += NFT_PIPAPO_LONGS_PER_M256) {
> @@ -458,6 +577,7 @@ static int nft_pipapo_avx2_lookup_4b_12(unsigned long *map, unsigned long *fill,
>  		    };
>  	int i, ret = -1, m256_size = f->bsize / NFT_PIPAPO_LONGS_PER_M256, b;
>  	unsigned long *lt = f->lt, bsize = f->bsize;
> +	NFT_PIPAPO_AVX2_DEBUG_MAP;
>  
>  	lt += offset * NFT_PIPAPO_LONGS_PER_M256;
>  	for (i = offset; i < m256_size; i++, lt += NFT_PIPAPO_LONGS_PER_M256) {
> @@ -553,6 +673,7 @@ static int nft_pipapo_avx2_lookup_4b_32(unsigned long *map, unsigned long *fill,
>  		    };
>  	int i, ret = -1, m256_size = f->bsize / NFT_PIPAPO_LONGS_PER_M256, b;
>  	unsigned long *lt = f->lt, bsize = f->bsize;
> +	NFT_PIPAPO_AVX2_DEBUG_MAP;
>  
>  	lt += offset * NFT_PIPAPO_LONGS_PER_M256;
>  	for (i = offset; i < m256_size; i++, lt += NFT_PIPAPO_LONGS_PER_M256) {
> @@ -680,6 +801,7 @@ static int nft_pipapo_avx2_lookup_8b_1(unsigned long *map, unsigned long *fill,
>  {
>  	int i, ret = -1, m256_size = f->bsize / NFT_PIPAPO_LONGS_PER_M256, b;
>  	unsigned long *lt = f->lt, bsize = f->bsize;
> +	NFT_PIPAPO_AVX2_DEBUG_MAP;
>  
>  	lt += offset * NFT_PIPAPO_LONGS_PER_M256;
>  	for (i = offset; i < m256_size; i++, lt += NFT_PIPAPO_LONGS_PER_M256) {
> @@ -738,6 +860,7 @@ static int nft_pipapo_avx2_lookup_8b_2(unsigned long *map, unsigned long *fill,
>  {
>  	int i, ret = -1, m256_size = f->bsize / NFT_PIPAPO_LONGS_PER_M256, b;
>  	unsigned long *lt = f->lt, bsize = f->bsize;
> +	NFT_PIPAPO_AVX2_DEBUG_MAP;
>  
>  	lt += offset * NFT_PIPAPO_LONGS_PER_M256;
>  	for (i = offset; i < m256_size; i++, lt += NFT_PIPAPO_LONGS_PER_M256) {
> @@ -803,6 +926,7 @@ static int nft_pipapo_avx2_lookup_8b_4(unsigned long *map, unsigned long *fill,
>  {
>  	int i, ret = -1, m256_size = f->bsize / NFT_PIPAPO_LONGS_PER_M256, b;
>  	unsigned long *lt = f->lt, bsize = f->bsize;
> +	NFT_PIPAPO_AVX2_DEBUG_MAP;
>  
>  	lt += offset * NFT_PIPAPO_LONGS_PER_M256;
>  	for (i = offset; i < m256_size; i++, lt += NFT_PIPAPO_LONGS_PER_M256) {
> @@ -879,6 +1003,7 @@ static int nft_pipapo_avx2_lookup_8b_6(unsigned long *map, unsigned long *fill,
>  {
>  	int i, ret = -1, m256_size = f->bsize / NFT_PIPAPO_LONGS_PER_M256, b;
>  	unsigned long *lt = f->lt, bsize = f->bsize;
> +	NFT_PIPAPO_AVX2_DEBUG_MAP;
>  
>  	lt += offset * NFT_PIPAPO_LONGS_PER_M256;
>  	for (i = offset; i < m256_size; i++, lt += NFT_PIPAPO_LONGS_PER_M256) {
> @@ -965,6 +1090,7 @@ static int nft_pipapo_avx2_lookup_8b_16(unsigned long *map, unsigned long *fill,
>  {
>  	int i, ret = -1, m256_size = f->bsize / NFT_PIPAPO_LONGS_PER_M256, b;
>  	unsigned long *lt = f->lt, bsize = f->bsize;
> +	NFT_PIPAPO_AVX2_DEBUG_MAP;
>  
>  	lt += offset * NFT_PIPAPO_LONGS_PER_M256;
>  	for (i = offset; i < m256_size; i++, lt += NFT_PIPAPO_LONGS_PER_M256) {

-- 
Stefano

Re: [PATCH nf 1/3] nft_set_pipapo: add avx register usage tracking for NET_DEBUG builds

[Florian Westphal]

Stefano Brivio <sbrivio@redhat.com> wrote:
> This made me wonder if there's any specific reason why we would need
> #if defined(x) here instead of a common #ifdef x. It looks like there
> isn't a reason, so maybe #ifdef CONFIG_DEBUG_NET is more... expected.

Ok, I'll change it and will also update the rest as per your comments.

Not sure I will be able to spin v2 before next week though.

> Perhaps those could all be uint16_t to reflect that it's YMM registers,
> and nft_pipapo_avx2_debug_usable() could simply promote them to
> unsigned long as needed by test_bit().

I'll swich to u16 and will ditch test_bit in favor of BIT(a) & r->.

> They could even be uint32_t to represent ZMM registers (or extended
> YMM) if we want to make this AVX512-ready, I'm not sure.

Can be done later.

[PATCH nf 2/3] nft_set_pipapo: fix incorrect avx2 match of 5th field octet

[Florian Westphal]

Given a set element like:

	icmpv6 . dead:beef:00ff::1

The value of 'ff' is irrelevant, any address will be matched
as long as the other octets are the same.

This is because of too-early register clobbering:
ymm7 is reloaded with new packet data (pkt[9])  but it still holds data
of an earlier load that wasn't processed yet.

The existing tests in nft_concat_range.sh selftests do exercise this code
path, but do not trigger incorrect matching due to the network prefix
limitation.

Cc: Stefano Brivio <sbrivio@redhat.com>
Reported-by: sontu mazumdar <sontu21@gmail.com>
Closes: https://marc.info/?l=netfilter&m=174369594208899&w=2
Fixes: 7400b063969b ("nft_set_pipapo: Introduce AVX2-based lookup implementation")
Signed-off-by: Florian Westphal <fw@strlen.de>
---
 net/netfilter/nft_set_pipapo_avx2.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

diff --git a/net/netfilter/nft_set_pipapo_avx2.c b/net/netfilter/nft_set_pipapo_avx2.c
index 8ce7154b678a..87cb0183cd79 100644
--- a/net/netfilter/nft_set_pipapo_avx2.c
+++ b/net/netfilter/nft_set_pipapo_avx2.c
@@ -1120,8 +1120,9 @@ static int nft_pipapo_avx2_lookup_8b_16(unsigned long *map, unsigned long *fill,
 		NFT_PIPAPO_AVX2_BUCKET_LOAD8(5, lt,  8,  pkt[8], bsize);
 
 		NFT_PIPAPO_AVX2_AND(6, 2, 3);
+		NFT_PIPAPO_AVX2_AND(3, 4, 7);
 		NFT_PIPAPO_AVX2_BUCKET_LOAD8(7, lt,  9,  pkt[9], bsize);
-		NFT_PIPAPO_AVX2_AND(0, 4, 5);
+		NFT_PIPAPO_AVX2_AND(0, 3, 5);
 		NFT_PIPAPO_AVX2_BUCKET_LOAD8(1, lt, 10, pkt[10], bsize);
 		NFT_PIPAPO_AVX2_AND(2, 6, 7);
 		NFT_PIPAPO_AVX2_BUCKET_LOAD8(3, lt, 11, pkt[11], bsize);
-- 
2.49.0

Re: [PATCH nf 2/3] nft_set_pipapo: fix incorrect avx2 match of 5th field octet

[Stefano Brivio]

On Fri,  4 Apr 2025 08:20:53 +0200
Florian Westphal <fw@strlen.de> wrote:

> Given a set element like:
> 
> 	icmpv6 . dead:beef:00ff::1
> 
> The value of 'ff' is irrelevant, any address will be matched
> as long as the other octets are the same.
> 
> This is because of too-early register clobbering:
> ymm7 is reloaded with new packet data (pkt[9])  but it still holds data
> of an earlier load that wasn't processed yet.
> 
> The existing tests in nft_concat_range.sh selftests do exercise this code
> path, but do not trigger incorrect matching due to the network prefix
> limitation.
> 
> Cc: Stefano Brivio <sbrivio@redhat.com>
> Reported-by: sontu mazumdar <sontu21@gmail.com>
> Closes: https://marc.info/?l=netfilter&m=174369594208899&w=2
> Fixes: 7400b063969b ("nft_set_pipapo: Introduce AVX2-based lookup implementation")
> Signed-off-by: Florian Westphal <fw@strlen.de>
> ---
>  net/netfilter/nft_set_pipapo_avx2.c | 3 ++-
>  1 file changed, 2 insertions(+), 1 deletion(-)
> 
> diff --git a/net/netfilter/nft_set_pipapo_avx2.c b/net/netfilter/nft_set_pipapo_avx2.c
> index 8ce7154b678a..87cb0183cd79 100644
> --- a/net/netfilter/nft_set_pipapo_avx2.c
> +++ b/net/netfilter/nft_set_pipapo_avx2.c
> @@ -1120,8 +1120,9 @@ static int nft_pipapo_avx2_lookup_8b_16(unsigned long *map, unsigned long *fill,
>  		NFT_PIPAPO_AVX2_BUCKET_LOAD8(5, lt,  8,  pkt[8], bsize);
>  
>  		NFT_PIPAPO_AVX2_AND(6, 2, 3);
> +		NFT_PIPAPO_AVX2_AND(3, 4, 7);
>  		NFT_PIPAPO_AVX2_BUCKET_LOAD8(7, lt,  9,  pkt[9], bsize);
> -		NFT_PIPAPO_AVX2_AND(0, 4, 5);
> +		NFT_PIPAPO_AVX2_AND(0, 3, 5);

Ouch, this is embarrassing, so it's great to see 1/3 and the fact that
it doesn't trigger other splats is a big relief.

Thanks Florian for fixing this and thanks Sontu for the detailed
report. I'm still reviewing patches 1/3 and 3/3.

If it matters, for now, for this one,

Reviewed-by: Stefano Brivio <sbrivio@redhat.com>

-- 
Stefano

[PATCH nf 3/3] selftests: netfilter: add test case for recent mismatch bug

[Florian Westphal]

Without 'nft_set_pipapo: fix incorrect avx2 match of 5th field octet"
this fails:

TEST: reported issues
  Add two elements, flush, re-add       1s                              [ OK ]
  net,mac with reload                   0s                              [ OK ]
  net,port,proto                        3s                              [ OK ]
  avx2 false match                      0s                              [FAIL]
False match for fe80:dead:01fe:0a02:0b03:6007:8009:a001

Other tests do not detect the kernel bug as they only alter parts in
the /64 netmask.

Signed-off-by: Florian Westphal <fw@strlen.de>
---
 .../net/netfilter/nft_concat_range.sh         | 39 ++++++++++++++++++-
 1 file changed, 38 insertions(+), 1 deletion(-)

diff --git a/tools/testing/selftests/net/netfilter/nft_concat_range.sh b/tools/testing/selftests/net/netfilter/nft_concat_range.sh
index 47088b005390..1f5979c1510c 100755
--- a/tools/testing/selftests/net/netfilter/nft_concat_range.sh
+++ b/tools/testing/selftests/net/netfilter/nft_concat_range.sh
@@ -27,7 +27,7 @@ TYPES="net_port port_net net6_port port_proto net6_port_mac net6_port_mac_proto
        net6_port_net6_port net_port_mac_proto_net"
 
 # Reported bugs, also described by TYPE_ variables below
-BUGS="flush_remove_add reload net_port_proto_match"
+BUGS="flush_remove_add reload net_port_proto_match avx2_mismatch"
 
 # List of possible paths to pktgen script from kernel tree for performance tests
 PKTGEN_SCRIPT_PATHS="
@@ -387,6 +387,25 @@ race_repeat	0
 
 perf_duration	0
 "
+
+TYPE_avx2_mismatch="
+display		avx2 false match
+type_spec	inet_proto . ipv6_addr
+chain_spec	meta l4proto . ip6 daddr
+dst		proto addr6
+src
+start		1
+count		1
+src_delta	1
+tools		ping
+proto		icmp6
+
+race_repeat	0
+
+perf_duration	0
+"
+
+
 # Set template for all tests, types and rules are filled in depending on test
 set_template='
 flush ruleset
@@ -1629,6 +1648,24 @@ test_bug_net_port_proto_match() {
 	nft flush ruleset
 }
 
+test_bug_avx2_mismatch()
+{
+	setup veth send_"${proto}" set || return ${ksft_skip}
+
+	local a1="fe80:dead:01ff:0a02:0b03:6007:8009:a001"
+	local a2="fe80:dead:01fe:0a02:0b03:6007:8009:a001"
+
+	nft "add element inet filter test { icmpv6 . $a1 }"
+
+	dst_addr6="$a2"
+	send_icmp6
+
+	if [ "$(count_packets)" -gt "0" ]; then
+		err "False match for $a2"
+		return 1
+	fi
+}
+
 test_reported_issues() {
 	eval test_bug_"${subtest}"
 }
-- 
2.49.0

Re: [PATCH nf 3/3] selftests: netfilter: add test case for recent mismatch bug

[Stefano Brivio]

On Fri,  4 Apr 2025 08:20:54 +0200
Florian Westphal <fw@strlen.de> wrote:

> Without 'nft_set_pipapo: fix incorrect avx2 match of 5th field octet"
> this fails:
> 
> TEST: reported issues
>   Add two elements, flush, re-add       1s                              [ OK ]
>   net,mac with reload                   0s                              [ OK ]
>   net,port,proto                        3s                              [ OK ]
>   avx2 false match                      0s                              [FAIL]
> False match for fe80:dead:01fe:0a02:0b03:6007:8009:a001
> 
> Other tests do not detect the kernel bug as they only alter parts in
> the /64 netmask.
> 
> Signed-off-by: Florian Westphal <fw@strlen.de>

Reviewed-by: Stefano Brivio <sbrivio@redhat.com>

-- 
Stefano

Re: [PATCH nf 3/3] selftests: netfilter: add test case for recent mismatch bug

[sontu mazumdar]

Florian, do we have the same test for every bit in the ipv6 address
both matching/unmatching ? If not, would it be possible to add this to
confirm that we are matching all the bits in the ipv6 address.

Also, a general question, where is this netfilter code maintained ? I
found this github where the code is present "GitHub - torvalds/linux:
Linux kernel source tree" but couldn't see this fix in Pull request.

Regards,
Sontu

On Fri, Apr 4, 2025 at 5:21 PM Stefano Brivio <sbrivio@redhat.com> wrote:
>
> On Fri,  4 Apr 2025 08:20:54 +0200
> Florian Westphal <fw@strlen.de> wrote:
>
> > Without 'nft_set_pipapo: fix incorrect avx2 match of 5th field octet"
> > this fails:
> >
> > TEST: reported issues
> >   Add two elements, flush, re-add       1s                              [ OK ]
> >   net,mac with reload                   0s                              [ OK ]
> >   net,port,proto                        3s                              [ OK ]
> >   avx2 false match                      0s                              [FAIL]
> > False match for fe80:dead:01fe:0a02:0b03:6007:8009:a001
> >
> > Other tests do not detect the kernel bug as they only alter parts in
> > the /64 netmask.
> >
> > Signed-off-by: Florian Westphal <fw@strlen.de>
>
> Reviewed-by: Stefano Brivio <sbrivio@redhat.com>
>
> --
> Stefano
>

Re: [PATCH nf 3/3] selftests: netfilter: add test case for recent mismatch bug

[Stefano Brivio]

On Wed, 9 Apr 2025 15:21:33 +0530
sontu mazumdar <sontu21@gmail.com> wrote:

> Florian, do we have the same test for every bit in the ipv6 address
> both matching/unmatching ? If not, would it be possible to add this to
> confirm that we are matching all the bits in the ipv6 address.

The equivalent testing, in more detail than that, is implemented by the
patch (under review) at:

  https://lore.kernel.org/all/20250407174048.21272-4-fw@strlen.de/

You can add more tests on top on the new one in nft_concat_range.sh,
but it's not doable to test every single bit, because there are 2 ^ 128
possible IPv6 addresses. I guess you could add a test looping on bytes
or groups of 16 bits.

> Also, a general question, where is this netfilter code maintained ? I
> found this github where the code is present "GitHub - torvalds/linux:
> Linux kernel source tree" but couldn't see this fix in Pull request.

netfilter doesn't use GitHub. See:

  https://www.netfilter.org/projects/nftables/index.html#git

-- 
Stefano