Skip to contentSkip to conversation

nft_set_pipapo: fix incorrect avx2 match of 5th field octet

PATCH Superseded Florian Westphal 2 participants 6 messages Apr 4, 2025

Subsystems (3)

v2 of 3 Superseded Latest is v3 →

lore
Share & tools
lore

Florian Westphal

author maintainer
#0 lore raw

v2 cover nft_set_pipapo: fix incorrect avx2 match of 5th field octet

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           | 220 ++++++++++++++++--
 .../net/netfilter/nft_concat_range.sh         |  39 +++-
 2 files changed, 243 insertions(+), 16 deletions(-)
Signature · 1 line
2.49.0
author maintainer
#1 lore raw

PATCH v2 1/3 nft_set_pipapo: add avx register usage tracking for NET_DEBUG builds

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)

mem and tmp are mutually exclusive.

Warn if
a) register store happens while register has 'mem' bit set but 'and' unset.
This detects clobbering of a register with new packet data before the previous load has been processed.
b) register is read but wasn't written to before This detects operations happening on undefined register content, such as AND or GOTOs.
c) register is saved to memory, but it doesn't hold result of an AND operation.
This detects erroneous stores to the memory scratch map.
d) register is used for goto, but it doesn't contain result of earlier AND operation.

This is disabled for NET_DEBUG=n builds.

v2: Improve kdoc (Stefano Brivio)
Use u16 (Stefano Brivio)
Reduce macro usage in favor of inline helpers warn if we store register to memory but its not holding result of AND operation

---
v2: major changes as per Stefano

Stores to memory or GOTOs now cause a splat unless the register result of AND operation.
This triggers in 1 case but I think code is fine, I added nft_pipapo_avx2_force_tmp() helper and use it in the relevant spot.

 net/netfilter/nft_set_pipapo_avx2.c | 217 ++++++++++++++++++++++++++--
 1 file changed, 203 insertions(+), 14 deletions(-)
net/netfilter/nft_set_pipapo_avx2.c +203 -14
index b8d3c3213efe..334d16096d00 100644
@@ -26,6 +26,160 @@
 
 #define NFT_PIPAPO_LONGS_PER_M256	(XSAVE_YMM_SIZE / BITS_PER_LONG)
 
+/**
+ * struct nft_pipapo_debug_regmap - Bitmaps representing sets of YMM registers
+ *
+ * @mem: n-th bit set if YMM<n> contains packet data loaded from memory
+ * @and: n-th bit set if YMM<n> was folded (AND operation done)
+ * @tmp: n-th bit set if YMM<n> contains folded data (result of AND operation)
+ */
+struct nft_pipapo_debug_regmap {
+#ifdef CONFIG_DEBUG_NET
+	u16 mem;
+	u16 and;
+	u16 tmp;
+#endif
+};
+
+#ifdef CONFIG_DEBUG_NET
+/* 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 = {        \
+		.tmp = BIT(15),                                         \
+	}
+
+#define NFT_PIPAPO_WARN(cond, reg, rmap, line, message)	({			\
+	const struct nft_pipapo_debug_regmap *rm__ = (rmap);			\
+	DEBUG_NET_WARN_ONCE((cond), "reg %d line %u %s, mem %04x, and %04x tmp %04x",\
+		  (reg), (line), (message), rm__->mem, rm__->and, rm__->tmp);	\
+})
+#else /* !CONFIG_DEBUG_NET */
+#define NFT_PIPAPO_AVX2_DEBUG_MAP                                       \
+	struct nft_pipapo_debug_regmap __pipapo_debug_regmap
+#endif
+
+/**
+ * nft_pipapo_avx2_load_packet() - Check and record packet data store
+ *
+ * @reg: Index of register being written to
+ * @r: Current bitmap of registers for debugging purposes
+ * @line: __LINE__ number filled via AVX2 macro
+ *
+ * Mark reg as holding packet data.
+ * Check reg is unused or had an AND operation performed on it.
+ */
+static inline void nft_pipapo_avx2_load_packet(unsigned int reg,
+					       struct nft_pipapo_debug_regmap *r,
+					       unsigned int line)
+{
+#ifdef CONFIG_DEBUG_NET
+	bool used = BIT(reg) & (r->mem | r->tmp);
+	bool anded = BIT(reg) & r->and;
+
+	r->and &= ~BIT(reg);
+	r->tmp &= ~BIT(reg);
+	r->mem |= BIT(reg);
+
+	if (used)
+		NFT_PIPAPO_WARN(!anded, reg, r, line, "busy");
+#endif
+}
+
+/**
+ * nft_pipapo_avx2_force_tmp() - Mark @reg as holding result of AND operation
+ * @reg: Index of register
+ * @r: Current bitmap of registers for debugging purposes
+ *
+ * Mark reg as holding temporary data, no checks are performed.
+ */
+static inline void nft_pipapo_avx2_force_tmp(unsigned int reg,
+					   struct nft_pipapo_debug_regmap *r)
+{
+#ifdef CONFIG_DEBUG_NET
+	r->tmp |= BIT(reg);
+	r->mem &= ~BIT(reg);
+#endif
+}
+
+/**
+ * nft_pipapo_avx2_load_tmp() - Check and record scratchmap restore
+ *
+ * @reg: Index of register being written to
+ * @r: Current bitmap of registers for debugging purposes
+ * @line: __LINE__ number filled via AVX2 macro
+ *
+ * Mark reg as holding temporary data.
+ * Check reg is unused or had an AND operation performed on it.
+ */
+static inline void nft_pipapo_avx2_load_tmp(unsigned int reg,
+					    struct nft_pipapo_debug_regmap *r,
+					    unsigned int line)
+{
+#ifdef CONFIG_DEBUG_NET
+	bool used = BIT(reg) & (r->mem | r->tmp);
+	bool anded = BIT(reg) & r->and;
+
+	r->and &= ~BIT(reg);
+
+	nft_pipapo_avx2_force_tmp(reg, r);
+
+	if (used)
+		NFT_PIPAPO_WARN(!anded, reg, r, line, "busy");
+#endif
+}
+
+/**
+ * nft_pipapo_avx2_debug_and() - Mark registers as being ANDed
+ *
+ * @a: Index of register being written to
+ * @b: Index of first register being ANDed
+ * @c: Index of second register being ANDed
+ * @r: Current bitmap of registers for debugging purposes
+ * @line: __LINE__ number filled via AVX2 macro
+ *
+ * Tags @reg2 and @reg3 as ANDed register
+ * Tags @reg1 as containing AND result
+ */
+static inline void nft_pipapo_avx2_debug_and(unsigned int a, unsigned int b,
+					     unsigned int c,
+					     struct nft_pipapo_debug_regmap *r,
+					     unsigned int line)
+{
+#ifdef CONFIG_DEBUG_NET
+	bool b_and = BIT(b) & r->and;
+	bool c_and = BIT(c) & r->and;
+	bool b_tmp = BIT(b) & r->tmp;
+	bool c_tmp = BIT(c) & r->tmp;
+	bool b_mem = BIT(b) & r->mem;
+	bool c_mem = BIT(c) & r->mem;
+
+	r->and |= BIT(b);
+	r->and |= BIT(c);
+
+	nft_pipapo_avx2_force_tmp(a, r);
+
+	NFT_PIPAPO_WARN((!b_mem && !b_and && !b_tmp), b, r, line, "unused");
+	NFT_PIPAPO_WARN((!c_mem && !c_and && !c_tmp), c, r, line, "unused");
+#endif
+}
+
+/**
+ * nft_pipapo_avx2_reg_tmp() - Check that @reg holds result of AND operation
+ * @reg: Index of register
+ * @r: Current bitmap of registers for debugging purposes
+ * @line: __LINE__ number filled via AVX2 macro
+ */
+static inline void nft_pipapo_avx2_reg_tmp(unsigned int reg,
+					   const struct nft_pipapo_debug_regmap *r,
+					   unsigned int line)
+{
+#ifdef CONFIG_DEBUG_NET
+	bool holds_and_result = BIT(reg) & r->tmp;
+
+        NFT_PIPAPO_WARN(!holds_and_result, reg, r, line, "unused");
+#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:
@@ -36,36 +190,60 @@
  * - loading the result bitmap from the previous field, as it's never used
  *   again
  */
-#define NFT_PIPAPO_AVX2_LOAD(reg, loc)					\
-	asm volatile("vmovntdqa %0, %%ymm" #reg : : "m" (loc))
+#define __NFT_PIPAPO_AVX2_LOAD(reg, loc)				\
+	asm volatile("vmovntdqa %0, %%ymm" #reg : : "m" (loc));		\
+
+#define NFT_PIPAPO_AVX2_LOAD(reg, loc) do {				\
+	nft_pipapo_avx2_load_tmp(reg,					\
+				 &__pipapo_debug_regmap, __LINE__);	\
+	__NFT_PIPAPO_AVX2_LOAD(reg, loc);				\
+} while (0)
 
 /* Stream a single lookup table bucket into YMM register given lookup table,
  * group index, value of packet bits, bucket size.
  */
-#define NFT_PIPAPO_AVX2_BUCKET_LOAD4(reg, lt, group, v, bsize)		\
-	NFT_PIPAPO_AVX2_LOAD(reg,					\
-			     lt[((group) * NFT_PIPAPO_BUCKETS(4) +	\
-				 (v)) * (bsize)])
-#define NFT_PIPAPO_AVX2_BUCKET_LOAD8(reg, lt, group, v, bsize)		\
-	NFT_PIPAPO_AVX2_LOAD(reg,					\
-			     lt[((group) * NFT_PIPAPO_BUCKETS(8) +	\
-				 (v)) * (bsize)])
+#define NFT_PIPAPO_AVX2_BUCKET_LOAD4(reg, lt, group, v, bsize) do {	\
+	nft_pipapo_avx2_load_packet(reg,				\
+				    &__pipapo_debug_regmap, __LINE__);	\
+	__NFT_PIPAPO_AVX2_LOAD(reg,					\
+			       lt[((group) * NFT_PIPAPO_BUCKETS(4) +	\
+			       (v)) * (bsize)]);			\
+} while (0)
+
+#define NFT_PIPAPO_AVX2_BUCKET_LOAD8(reg, lt, group, v, bsize) do {	\
+	nft_pipapo_avx2_load_packet(reg,				\
+				    &__pipapo_debug_regmap, __LINE__);	\
+	__NFT_PIPAPO_AVX2_LOAD(reg,					\
+			       lt[((group) * NFT_PIPAPO_BUCKETS(8) +	\
+			       (v)) * (bsize)])				\
+} while (0)
 
 /* 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_debug_and(dst, a, b,				\
+				  &__pipapo_debug_regmap, __LINE__);	\
+} 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_reg_tmp(reg, &__pipapo_debug_regmap, __LINE__);	\
+	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_reg_tmp(reg, &__pipapo_debug_regmap, __LINE__);	\
+	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 +397,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 +461,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 +541,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 +639,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 +735,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 +863,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) {
@@ -687,6 +871,7 @@ static int nft_pipapo_avx2_lookup_8b_1(unsigned long *map, unsigned long *fill,
 
 		if (first) {
 			NFT_PIPAPO_AVX2_BUCKET_LOAD8(2, lt, 0, pkt[0], bsize);
+			nft_pipapo_avx2_force_tmp(2, &__pipapo_debug_regmap);
 		} else {
 			NFT_PIPAPO_AVX2_BUCKET_LOAD8(0, lt, 0, pkt[0], bsize);
 			NFT_PIPAPO_AVX2_LOAD(1, map[i_ul]);
@@ -738,6 +923,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 +989,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 +1066,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 +1153,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) {
Signature · 1 line
2.49.0
Reviewed-by on v2 1/3
#2 lore raw

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

Quoted 25 lines · On Fri, 4 Apr 2025 15:32:24 +0200 Florian Westphal <[email protected]> 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)

mem and tmp are mutually exclusive.

Warn if
a) register store happens while register has 'mem' bit set but 'and' unset.
This detects clobbering of a register with new packet data before the previous load has been processed.
b) register is read but wasn't written to before This detects operations happening on undefined register content, such as AND or GOTOs.
c) register is saved to memory, but it doesn't hold result of an AND operation.
This detects erroneous stores to the memory scratch map.
d) register is used for goto, but it doesn't contain result of earlier AND operation.

This is disabled for NET_DEBUG=n builds.

Quoted 7 lines

v2: Improve kdoc (Stefano Brivio)
Use u16 (Stefano Brivio)
Reduce macro usage in favor of inline helpers warn if we store register to memory but its not holding result of AND operation

Thanks, it looks much clearer (at least to me) now. Just some exceedingly minor nits below. Other than that,

Quoted 5 lines

---
v2: major changes as per Stefano

Stores to memory or GOTOs now cause a splat unless the register result of AND operation.

Ah, oops, I thought that was the intention in v1 too! :)

Quoted 2 lines

This triggers in 1 case but I think code is fine, I added nft_pipapo_avx2_force_tmp() helper and use it in the relevant spot.

It makes sense to me, details below.

Quoted 19 lines
 net/netfilter/nft_set_pipapo_avx2.c | 217 ++++++++++++++++++++++++++--
 1 file changed, 203 insertions(+), 14 deletions(-)
net/netfilter/nft_set_pipapo_avx2.c +7 -0
index b8d3c3213efe..334d16096d00 100644
@@ -26,6 +26,160 @@
 
 #define NFT_PIPAPO_LONGS_PER_M256	(XSAVE_YMM_SIZE / BITS_PER_LONG)
 
+/**
+ * struct nft_pipapo_debug_regmap - Bitmaps representing sets of YMM registers
+ *
+ * @mem: n-th bit set if YMM<n> contains packet data loaded from memory
+ * @and: n-th bit set if YMM<n> was folded (AND operation done)
+ * @tmp: n-th bit set if YMM<n> contains folded data (result of AND operation)
+ */

net/netfilter/nft_set_pipapo_avx2.c line 45

Quoted 10 lines
net/netfilter/nft_set_pipapo_avx2.c +10 -0
+struct nft_pipapo_debug_regmap {
+#ifdef CONFIG_DEBUG_NET
+	u16 mem;
+	u16 and;
+	u16 tmp;
+#endif
+};
+
+#ifdef CONFIG_DEBUG_NET
+/* YYM15 is used as an always-0-register, see nft_pipapo_avx2_prepare */

It's really YMM (or ymm), with two m's and one y. :) That's what I was referring to in my previous comment.

net/netfilter/nft_set_pipapo_avx2.c line 49

Quoted 4 lines
net/netfilter/nft_set_pipapo_avx2.c +4 -0
+#define NFT_PIPAPO_AVX2_DEBUG_MAP                                       \
+	struct nft_pipapo_debug_regmap __pipapo_debug_regmap = {        \
+		.tmp = BIT(15),                                         \
+	}

This mixes spaces and tabs (I guess from copy and paste).

Quoted 120 lines
net/netfilter/nft_set_pipapo_avx2.c +120 -0
+
+#define NFT_PIPAPO_WARN(cond, reg, rmap, line, message)	({			\
+	const struct nft_pipapo_debug_regmap *rm__ = (rmap);			\
+	DEBUG_NET_WARN_ONCE((cond), "reg %d line %u %s, mem %04x, and %04x tmp %04x",\
+		  (reg), (line), (message), rm__->mem, rm__->and, rm__->tmp);	\
+})
+#else /* !CONFIG_DEBUG_NET */
+#define NFT_PIPAPO_AVX2_DEBUG_MAP                                       \
+	struct nft_pipapo_debug_regmap __pipapo_debug_regmap
+#endif
+
+/**
+ * nft_pipapo_avx2_load_packet() - Check and record packet data store
+ *
+ * @reg: Index of register being written to
+ * @r: Current bitmap of registers for debugging purposes
+ * @line: __LINE__ number filled via AVX2 macro
+ *
+ * Mark reg as holding packet data.
+ * Check reg is unused or had an AND operation performed on it.
+ */
+static inline void nft_pipapo_avx2_load_packet(unsigned int reg,
+					       struct nft_pipapo_debug_regmap *r,
+					       unsigned int line)
+{
+#ifdef CONFIG_DEBUG_NET
+	bool used = BIT(reg) & (r->mem | r->tmp);
+	bool anded = BIT(reg) & r->and;
+
+	r->and &= ~BIT(reg);
+	r->tmp &= ~BIT(reg);
+	r->mem |= BIT(reg);
+
+	if (used)
+		NFT_PIPAPO_WARN(!anded, reg, r, line, "busy");
+#endif
+}
+
+/**
+ * nft_pipapo_avx2_force_tmp() - Mark @reg as holding result of AND operation
+ * @reg: Index of register
+ * @r: Current bitmap of registers for debugging purposes
+ *
+ * Mark reg as holding temporary data, no checks are performed.
+ */
+static inline void nft_pipapo_avx2_force_tmp(unsigned int reg,
+					   struct nft_pipapo_debug_regmap *r)
+{
+#ifdef CONFIG_DEBUG_NET
+	r->tmp |= BIT(reg);
+	r->mem &= ~BIT(reg);
+#endif
+}
+
+/**
+ * nft_pipapo_avx2_load_tmp() - Check and record scratchmap restore
+ *
+ * @reg: Index of register being written to
+ * @r: Current bitmap of registers for debugging purposes
+ * @line: __LINE__ number filled via AVX2 macro
+ *
+ * Mark reg as holding temporary data.
+ * Check reg is unused or had an AND operation performed on it.
+ */
+static inline void nft_pipapo_avx2_load_tmp(unsigned int reg,
+					    struct nft_pipapo_debug_regmap *r,
+					    unsigned int line)
+{
+#ifdef CONFIG_DEBUG_NET
+	bool used = BIT(reg) & (r->mem | r->tmp);
+	bool anded = BIT(reg) & r->and;
+
+	r->and &= ~BIT(reg);
+
+	nft_pipapo_avx2_force_tmp(reg, r);
+
+	if (used)
+		NFT_PIPAPO_WARN(!anded, reg, r, line, "busy");
+#endif
+}
+
+/**
+ * nft_pipapo_avx2_debug_and() - Mark registers as being ANDed
+ *
+ * @a: Index of register being written to
+ * @b: Index of first register being ANDed
+ * @c: Index of second register being ANDed
+ * @r: Current bitmap of registers for debugging purposes
+ * @line: __LINE__ number filled via AVX2 macro
+ *
+ * Tags @reg2 and @reg3 as ANDed register
+ * Tags @reg1 as containing AND result
+ */
+static inline void nft_pipapo_avx2_debug_and(unsigned int a, unsigned int b,
+					     unsigned int c,
+					     struct nft_pipapo_debug_regmap *r,
+					     unsigned int line)
+{
+#ifdef CONFIG_DEBUG_NET
+	bool b_and = BIT(b) & r->and;
+	bool c_and = BIT(c) & r->and;
+	bool b_tmp = BIT(b) & r->tmp;
+	bool c_tmp = BIT(c) & r->tmp;
+	bool b_mem = BIT(b) & r->mem;
+	bool c_mem = BIT(c) & r->mem;
+
+	r->and |= BIT(b);
+	r->and |= BIT(c);
+
+	nft_pipapo_avx2_force_tmp(a, r);
+
+	NFT_PIPAPO_WARN((!b_mem && !b_and && !b_tmp), b, r, line, "unused");
+	NFT_PIPAPO_WARN((!c_mem && !c_and && !c_tmp), c, r, line, "unused");
+#endif
+}
+
+/**
+ * nft_pipapo_avx2_reg_tmp() - Check that @reg holds result of AND operation
+ * @reg: Index of register
+ * @r: Current bitmap of registers for debugging purposes

net/netfilter/nft_set_pipapo_avx2.c line 179

Quoted 10 lines
net/netfilter/nft_set_pipapo_avx2.c +10 -0
+ * @line: __LINE__ number filled via AVX2 macro
+ */
+static inline void nft_pipapo_avx2_reg_tmp(unsigned int reg,
+					   const struct nft_pipapo_debug_regmap *r,
+					   unsigned int line)
+{
+#ifdef CONFIG_DEBUG_NET
+	bool holds_and_result = BIT(reg) & r->tmp;
+
+        NFT_PIPAPO_WARN(!holds_and_result, reg, r, line, "unused");

This is indented with spaces.

Quoted 130 lines
net/netfilter/nft_set_pipapo_avx2.c +47 -14
+#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:
@@ -36,36 +190,60 @@
  * - loading the result bitmap from the previous field, as it's never used
  *   again
  */
-#define NFT_PIPAPO_AVX2_LOAD(reg, loc)					\
-	asm volatile("vmovntdqa %0, %%ymm" #reg : : "m" (loc))
+#define __NFT_PIPAPO_AVX2_LOAD(reg, loc)				\
+	asm volatile("vmovntdqa %0, %%ymm" #reg : : "m" (loc));		\
+
+#define NFT_PIPAPO_AVX2_LOAD(reg, loc) do {				\
+	nft_pipapo_avx2_load_tmp(reg,					\
+				 &__pipapo_debug_regmap, __LINE__);	\
+	__NFT_PIPAPO_AVX2_LOAD(reg, loc);				\
+} while (0)
 
 /* Stream a single lookup table bucket into YMM register given lookup table,
  * group index, value of packet bits, bucket size.
  */
-#define NFT_PIPAPO_AVX2_BUCKET_LOAD4(reg, lt, group, v, bsize)		\
-	NFT_PIPAPO_AVX2_LOAD(reg,					\
-			     lt[((group) * NFT_PIPAPO_BUCKETS(4) +	\
-				 (v)) * (bsize)])
-#define NFT_PIPAPO_AVX2_BUCKET_LOAD8(reg, lt, group, v, bsize)		\
-	NFT_PIPAPO_AVX2_LOAD(reg,					\
-			     lt[((group) * NFT_PIPAPO_BUCKETS(8) +	\
-				 (v)) * (bsize)])
+#define NFT_PIPAPO_AVX2_BUCKET_LOAD4(reg, lt, group, v, bsize) do {	\
+	nft_pipapo_avx2_load_packet(reg,				\
+				    &__pipapo_debug_regmap, __LINE__);	\
+	__NFT_PIPAPO_AVX2_LOAD(reg,					\
+			       lt[((group) * NFT_PIPAPO_BUCKETS(4) +	\
+			       (v)) * (bsize)]);			\
+} while (0)
+
+#define NFT_PIPAPO_AVX2_BUCKET_LOAD8(reg, lt, group, v, bsize) do {	\
+	nft_pipapo_avx2_load_packet(reg,				\
+				    &__pipapo_debug_regmap, __LINE__);	\
+	__NFT_PIPAPO_AVX2_LOAD(reg,					\
+			       lt[((group) * NFT_PIPAPO_BUCKETS(8) +	\
+			       (v)) * (bsize)])				\
+} while (0)
 
 /* 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_debug_and(dst, a, b,				\
+				  &__pipapo_debug_regmap, __LINE__);	\
+} 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_reg_tmp(reg, &__pipapo_debug_regmap, __LINE__);	\
+	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_reg_tmp(reg, &__pipapo_debug_regmap, __LINE__);	\
+	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 +397,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 +461,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 +541,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 +639,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 +735,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 +863,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) {

net/netfilter/nft_set_pipapo_avx2.c static int nft_pipapo_avx2_lookup_8b_1(unsigned long *map, unsigned long *fill, · line 874

Quoted 4 lines
net/netfilter/nft_set_pipapo_avx2.c +1 -0
@@ -687,6 +871,7 @@ static int nft_pipapo_avx2_lookup_8b_1(unsigned long *map, unsigned long *fill,
 
 		if (first) {
 			NFT_PIPAPO_AVX2_BUCKET_LOAD8(2, lt, 0, pkt[0], bsize);
+			nft_pipapo_avx2_force_tmp(2, &__pipapo_debug_regmap);

Right, that's because we have an 8-bit bucket and we're comparing 8 bits, so in this case we don't need to AND any value in the first iteration.

Quoted 35 lines
net/netfilter/nft_set_pipapo_avx2.c +4 -0
 		} else {
 			NFT_PIPAPO_AVX2_BUCKET_LOAD8(0, lt, 0, pkt[0], bsize);
 			NFT_PIPAPO_AVX2_LOAD(1, map[i_ul]);
@@ -738,6 +923,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 +989,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 +1066,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 +1153,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) {
Signature · 1 line
Stefano
author maintainer
#3 lore raw

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

Quoted 5 lines · Stefano Brivio

Review

Quoted 2 lines
(quoted diff) +2 -0
+#ifdef CONFIG_DEBUG_NET
+/* YYM15 is used as an always-0-register, see nft_pipapo_avx2_prepare */

It's really YMM (or ymm), with two m's and one y. :) That's what I was referring to in my previous comment.

Grr, my brain autocorrects this for some reason :-/

I'll fix it in v3 on Monday.

Quoted 6 lines

net/netfilter/nft_set_pipapo_avx2.c line 49

Quoted 4 lines
net/netfilter/nft_set_pipapo_avx2.c +4 -0
+#define NFT_PIPAPO_AVX2_DEBUG_MAP                                       \
+	struct nft_pipapo_debug_regmap __pipapo_debug_regmap = {        \
+		.tmp = BIT(15),                                         \
+	}

This mixes spaces and tabs (I guess from copy and paste).

Thanks, will fix it too.

Quoted 6 lines

net/netfilter/nft_set_pipapo_avx2.c line 179

Quoted 4 lines
net/netfilter/nft_set_pipapo_avx2.c +4 -0
+#ifdef CONFIG_DEBUG_NET
+	bool holds_and_result = BIT(reg) & r->tmp;
+
+        NFT_PIPAPO_WARN(!holds_and_result, reg, r, line, "unused");

This is indented with spaces.

Indeed, will fix.

Quoted 9 lines

net/netfilter/nft_set_pipapo_avx2.c static int nft_pipapo_avx2_lookup_8b_1(unsigned long *map, unsigned long *fill, · line 874

Quoted 5 lines
net/netfilter/nft_set_pipapo_avx2.c +1 -0
@@ -687,6 +871,7 @@ static int nft_pipapo_avx2_lookup_8b_1(unsigned long *map, unsigned long *fill,
 
 		if (first) {
 			NFT_PIPAPO_AVX2_BUCKET_LOAD8(2, lt, 0, pkt[0], bsize);
+			nft_pipapo_avx2_force_tmp(2, &__pipapo_debug_regmap);

Right, that's because we have an 8-bit bucket and we're comparing 8 bits, so in this case we don't need to AND any value in the first iteration.

Thanks for confirming.

author maintainer
#4 lore raw

PATCH v2 2/3 nft_set_pipapo: fix incorrect avx2 match of 5th field octet

In reply to 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.

Fixes 7400b063969b ("nft_set_pipapo: Introduce AVX2-based lookup implementation")

---
v2: no changes.

 net/netfilter/nft_set_pipapo_avx2.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)
net/netfilter/nft_set_pipapo_avx2.c +2 -1
index 334d16096d00..7792625b8100 100644
@@ -1183,8 +1183,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);
Signature · 1 line
2.49.0
author maintainer
#5 lore raw

PATCH v2 3/3 selftests: netfilter: add test case for recent mismatch bug

In reply to 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.

---
v2: no changes.

 .../net/netfilter/nft_concat_range.sh         | 39 ++++++++++++++++++-
 1 file changed, 38 insertions(+), 1 deletion(-)
tools/testing/selftests/net/netfilter/nft_concat_range.sh +38 -1
index 47088b005390..1f5979c1510c 100755
@@ -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}"
 }
Signature · 1 line
2.49.0