[PATCH nf-next 0/3] netfilter: nf_set_pipapo_avx2: fix initial map fill

[PATCH nf-next 0/3] netfilter: nf_set_pipapo_avx2: fix initial map fill

[Florian Westphal]

The avx2 implementation suffers from the same bug fixed in the C
implementation with 791a615b7ad2
("netfilter: nf_set_pipapo: fix initial map fill").

If the first field isn't the largest one, there will be mismatches, i.e.
a wrong match will be returned.

First patch fixes this bug.

Because the selftest data path test does:
   .... @test counter name ...

.. and then checks if the counter has been incremented, the selftest
first needs to be reworked to use per-element counters.

Otherwise, we can only differentiate between 'no entry matches' and
'some entry matches', but its imperative we can also validate that
the lookup did return the correct element.

The second patch does reworks the selftest accordingly.

Last patch adds extends the existing regression test for this
bug class by also validating the datapath, rather than just the
control plane.

Florian Westphal (3):
  netfilter: nf_set_pipapo_avx2: fix initial map fill
  selftests: netfilter: nft_concat_range.sh: prefer per element counters
    for testing
  selftests: netfilter: nft_concat_range.sh: add datapath check for map
    fill bug

 net/netfilter/nft_set_pipapo_avx2.c           |  21 +++-
 .../net/netfilter/nft_concat_range.sh         | 102 +++++++++++++++---
 2 files changed, 108 insertions(+), 15 deletions(-)

-- 
2.49.0

[PATCH nf-next 1/3] netfilter: nf_set_pipapo_avx2: fix initial map fill

[Florian Westphal]

If the first field doesn't cover the entire start map, then we must zero
out the remainder, else we leak those bits into the next match round map.

The earlie fix was incomplete and did only fix up the generic C
implementation.

A followup patch adds a test case to nft_concat_range.sh.

Fixes: 791a615b7ad2 ("netfilter: nf_set_pipapo: fix initial map fill")
Signed-off-by: Florian Westphal <fw@strlen.de>
---
 net/netfilter/nft_set_pipapo_avx2.c | 21 ++++++++++++++++++++-
 1 file changed, 20 insertions(+), 1 deletion(-)

diff --git a/net/netfilter/nft_set_pipapo_avx2.c b/net/netfilter/nft_set_pipapo_avx2.c
index c15db28c5ebc..be7c16c79f71 100644
--- a/net/netfilter/nft_set_pipapo_avx2.c
+++ b/net/netfilter/nft_set_pipapo_avx2.c
@@ -1113,6 +1113,25 @@ bool nft_pipapo_avx2_estimate(const struct nft_set_desc *desc, u32 features,
 	return true;
 }
 
+/**
+ * pipapo_resmap_init_avx2() - Initialise result map before first use
+ * @m:		Matching data, including mapping table
+ * @res_map:	Result map
+ *
+ * Like pipapo_resmap_init() but do not set start map bits covered by the first field.
+ */
+static inline void pipapo_resmap_init_avx2(const struct nft_pipapo_match *m, unsigned long *res_map)
+{
+	const struct nft_pipapo_field *f = m->f;
+	int i;
+
+	/* Starting map doesn't need to be set to all-ones for this implementation,
+	 * but we do need to zero the remaining bits, if any.
+	 */
+	for (i = f->bsize; i < m->bsize_max; i++)
+		res_map[i] = 0ul;
+}
+
 /**
  * nft_pipapo_avx2_lookup() - Lookup function for AVX2 implementation
  * @net:	Network namespace
@@ -1171,7 +1190,7 @@ bool nft_pipapo_avx2_lookup(const struct net *net, const struct nft_set *set,
 	res  = scratch->map + (map_index ? m->bsize_max : 0);
 	fill = scratch->map + (map_index ? 0 : m->bsize_max);
 
-	/* Starting map doesn't need to be set for this implementation */
+	pipapo_resmap_init_avx2(m, res);
 
 	nft_pipapo_avx2_prepare();
 
-- 
2.49.0

Re: [PATCH nf-next 1/3] netfilter: nf_set_pipapo_avx2: fix initial map fill

[Pablo Neira Ayuso]

Hi Florian, Stefano,

On Fri, May 23, 2025 at 02:20:44PM +0200, Florian Westphal wrote:
> If the first field doesn't cover the entire start map, then we must zero
> out the remainder, else we leak those bits into the next match round map.
> 
> The earlie fix was incomplete and did only fix up the generic C
> implementation.
> 
> A followup patch adds a test case to nft_concat_range.sh.
> 
> Fixes: 791a615b7ad2 ("netfilter: nf_set_pipapo: fix initial map fill")
> Signed-off-by: Florian Westphal <fw@strlen.de>
> ---
>  net/netfilter/nft_set_pipapo_avx2.c | 21 ++++++++++++++++++++-
>  1 file changed, 20 insertions(+), 1 deletion(-)
> 
> diff --git a/net/netfilter/nft_set_pipapo_avx2.c b/net/netfilter/nft_set_pipapo_avx2.c
> index c15db28c5ebc..be7c16c79f71 100644
> --- a/net/netfilter/nft_set_pipapo_avx2.c
> +++ b/net/netfilter/nft_set_pipapo_avx2.c
> @@ -1113,6 +1113,25 @@ bool nft_pipapo_avx2_estimate(const struct nft_set_desc *desc, u32 features,
>  	return true;
>  }
>  
> +/**
> + * pipapo_resmap_init_avx2() - Initialise result map before first use
> + * @m:		Matching data, including mapping table
> + * @res_map:	Result map
> + *
> + * Like pipapo_resmap_init() but do not set start map bits covered by the first field.
> + */
> +static inline void pipapo_resmap_init_avx2(const struct nft_pipapo_match *m, unsigned long *res_map)
> +{
> +	const struct nft_pipapo_field *f = m->f;
> +	int i;
> +
> +	/* Starting map doesn't need to be set to all-ones for this implementation,
> +	 * but we do need to zero the remaining bits, if any.
> +	 */
> +	for (i = f->bsize; i < m->bsize_max; i++)
> +		res_map[i] = 0ul;
> +}
> +
>  /**
>   * nft_pipapo_avx2_lookup() - Lookup function for AVX2 implementation
>   * @net:	Network namespace
> @@ -1171,7 +1190,7 @@ bool nft_pipapo_avx2_lookup(const struct net *net, const struct nft_set *set,
>  	res  = scratch->map + (map_index ? m->bsize_max : 0);
>  	fill = scratch->map + (map_index ? 0 : m->bsize_max);
>  
> -	/* Starting map doesn't need to be set for this implementation */
> +	pipapo_resmap_init_avx2(m, res);

nitpick:

nft_pipapo_avx2_lookup_slow() calls pipapo_resmap_init() for
non-optimized fields, eg. 8 bytes, which is unlikely to be seen.
IIUC this resets it again.

Maybe revisit this in nf-next? Would be worth to cover this avx2 path
with 8 bytes in tests?

Thanks.

>  
>  	nft_pipapo_avx2_prepare();
>  
> -- 
> 2.49.0
> 
> 

Re: [PATCH nf-next 1/3] netfilter: nf_set_pipapo_avx2: fix initial map fill

[Florian Westphal]

Pablo Neira Ayuso <pablo@netfilter.org> wrote:
> > +	/* Starting map doesn't need to be set to all-ones for this implementation,
> > +	 * but we do need to zero the remaining bits, if any.
> > +	 */
> > +	for (i = f->bsize; i < m->bsize_max; i++)
> > +		res_map[i] = 0ul;
> > +}
> > +
> >  /**
> >   * nft_pipapo_avx2_lookup() - Lookup function for AVX2 implementation
> >   * @net:	Network namespace
> > @@ -1171,7 +1190,7 @@ bool nft_pipapo_avx2_lookup(const struct net *net, const struct nft_set *set,
> >  	res  = scratch->map + (map_index ? m->bsize_max : 0);
> >  	fill = scratch->map + (map_index ? 0 : m->bsize_max);
> >  
> > -	/* Starting map doesn't need to be set for this implementation */
> > +	pipapo_resmap_init_avx2(m, res);
> 
> nitpick:
> 
> nft_pipapo_avx2_lookup_slow() calls pipapo_resmap_init() for
> non-optimized fields, eg. 8 bytes, which is unlikely to be seen.
> IIUC this resets it again.

Yes.  We have no test case for this function.
Can you come up with an example that would exercise this function?
It would be good to cover it in selftests.

> Maybe revisit this in nf-next? Would be worth to cover this avx2 path
> with 8 bytes in tests?

Not sure its worth it.  pipapo_resmap_init_avx2(), in most cases, is
a no-op as usually m->bsize_max is the same as f->bsize.

But yes, we could add yet another version of pipapo_resmap_init()
that only has the one-fill part.

[PATCH nf-next 2/3] selftests: netfilter: nft_concat_range.sh: prefer per element counters for testing

[Florian Westphal]

The selftest uses following rule:
  ... @test counter name "test"

Then sends a packet, then checks if the named counter did increment or
not.

This is fine for the 'no-match' test case: If anything matches the
counter increments and the test fails as expected.

But for the 'should match' test cases this isn't optimal.
Consider buggy matching, where the packet matches entry x, but it
should have matched entry y.

In that case the test would erronously pass.

Rework the selftest to use per-element counters to avoid this.

After sending packet that should have matched entry x, query the
relevant element via 'nft reset element' and check that its counter
had incremented.

The 'nomatch' case isn't altered, no entry should match so the named
counter must be 0, changing it to the per-element counter would then
pass if another entry matches.

The downside of this change is a slight increase in test run-time by
a few seconds.

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

diff --git a/tools/testing/selftests/net/netfilter/nft_concat_range.sh b/tools/testing/selftests/net/netfilter/nft_concat_range.sh
index efea93cf23d4..86b8ce742700 100755
--- a/tools/testing/selftests/net/netfilter/nft_concat_range.sh
+++ b/tools/testing/selftests/net/netfilter/nft_concat_range.sh
@@ -419,6 +419,7 @@ table inet filter {
 
 	set test {
 		type ${type_spec}
+		counter
 		flags interval,timeout
 	}
 
@@ -1158,8 +1159,17 @@ del() {
 	fi
 }
 
-# Return packet count from 'test' counter in 'inet filter' table
+# Return packet count for elem $1 from 'test' counter in 'inet filter' table
 count_packets() {
+	found=0
+	for token in $(nft reset element inet filter test "${1}" ); do
+		[ ${found} -eq 1 ] && echo "${token}" && return
+		[ "${token}" = "packets" ] && found=1
+	done
+}
+
+# Return packet count from 'test' counter in 'inet filter' table
+count_packets_nomatch() {
 	found=0
 	for token in $(nft list counter inet filter test); do
 		[ ${found} -eq 1 ] && echo "${token}" && return
@@ -1206,6 +1216,10 @@ perf() {
 
 # Set MAC addresses, send single packet, check that it matches, reset counter
 send_match() {
+	local elem="$1"
+
+	shift
+
 	ip link set veth_a address "$(format_mac "${1}")"
 	ip -n B link set veth_b address "$(format_mac "${2}")"
 
@@ -1216,7 +1230,7 @@ send_match() {
 		eval src_"$f"=\$\(format_\$f "${2}"\)
 	done
 	eval send_\$proto
-	if [ "$(count_packets)" != "1" ]; then
+	if [ "$(count_packets "$elem")" != "1" ]; then
 		err "${proto} packet to:"
 		err "  $(for f in ${dst}; do
 			 eval format_\$f "${1}"; printf ' '; done)"
@@ -1242,7 +1256,7 @@ send_nomatch() {
 		eval src_"$f"=\$\(format_\$f "${2}"\)
 	done
 	eval send_\$proto
-	if [ "$(count_packets)" != "0" ]; then
+	if [ "$(count_packets_nomatch)" != "0" ]; then
 		err "${proto} packet to:"
 		err "  $(for f in ${dst}; do
 			 eval format_\$f "${1}"; printf ' '; done)"
@@ -1262,6 +1276,8 @@ send_nomatch() {
 test_correctness_main() {
 	range_size=1
 	for i in $(seq "${start}" $((start + count))); do
+		local elem=""
+
 		end=$((start + range_size))
 
 		# Avoid negative or zero-sized port ranges
@@ -1272,15 +1288,16 @@ test_correctness_main() {
 		srcstart=$((start + src_delta))
 		srcend=$((end + src_delta))
 
-		add "$(format)" || return 1
+		elem="$(format)"
+		add "$elem" || return 1
 		for j in $(seq "$start" $((range_size / 2 + 1)) ${end}); do
-			send_match "${j}" $((j + src_delta)) || return 1
+			send_match "$elem" "${j}" $((j + src_delta)) || return 1
 		done
 		send_nomatch $((end + 1)) $((end + 1 + src_delta)) || return 1
 
 		# Delete elements now and then
 		if [ $((i % 3)) -eq 0 ]; then
-			del "$(format)" || return 1
+			del "$elem" || return 1
 			for j in $(seq "$start" \
 				   $((range_size / 2 + 1)) ${end}); do
 				send_nomatch "${j}" $((j + src_delta)) \
@@ -1572,14 +1589,17 @@ test_timeout() {
 
 	range_size=1
 	for i in $(seq "$start" $((start + count))); do
+		local elem=""
+
 		end=$((start + range_size))
 		srcstart=$((start + src_delta))
 		srcend=$((end + src_delta))
 
-		add "$(format)" || return 1
+		elem="$(format)"
+		add "$elem" || return 1
 
 		for j in $(seq "$start" $((range_size / 2 + 1)) ${end}); do
-			send_match "${j}" $((j + src_delta)) || return 1
+			send_match "$elem" "${j}" $((j + src_delta)) || return 1
 		done
 
 		range_size=$((range_size + 1))
@@ -1737,7 +1757,7 @@ test_bug_reload() {
 		srcend=$((end + src_delta))
 
 		for j in $(seq "$start" $((range_size / 2 + 1)) ${end}); do
-			send_match "${j}" $((j + src_delta)) || return 1
+			send_match "$(format)" "${j}" $((j + src_delta)) || return 1
 		done
 
 		range_size=$((range_size + 1))
@@ -1817,7 +1837,7 @@ test_bug_avx2_mismatch()
 	dst_addr6="$a2"
 	send_icmp6
 
-	if [ "$(count_packets)" -gt "0" ]; then
+	if [ "$(count_packets "{ icmpv6 . $a1 }")" -gt "0" ]; then
 		err "False match for $a2"
 		return 1
 	fi
-- 
2.49.0

[PATCH nf-next 3/3] selftests: netfilter: nft_concat_range.sh: add datapath check for map fill bug

[Florian Westphal]

commit 0935ee6032df ("selftests: netfilter: add test case for recent mismatch bug")
added a regression check for incorrect initial fill of the result map
that was fixed with 791a615b7ad2 ("netfilter: nf_set_pipapo: fix initial map fill").

The test used 'nft get element', i.e., control plane checks for
match/nomatch results.

The control plane however doesn't use avx2 version, so we need to
send+match packets.

As the additional packet match/nomatch is slow, don't do this for
every element added/removed: add and use maybe_send_(no)match
helpers and use them.

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

diff --git a/tools/testing/selftests/net/netfilter/nft_concat_range.sh b/tools/testing/selftests/net/netfilter/nft_concat_range.sh
index 86b8ce742700..cd12b8b5ac0e 100755
--- a/tools/testing/selftests/net/netfilter/nft_concat_range.sh
+++ b/tools/testing/selftests/net/netfilter/nft_concat_range.sh
@@ -378,7 +378,7 @@ display		net,port,proto
 type_spec	ipv4_addr . inet_service . inet_proto
 chain_spec	ip daddr . udp dport . meta l4proto
 dst		addr4 port proto
-src
+src		 
 start		1
 count		9
 src_delta	9
@@ -1269,6 +1269,42 @@ send_nomatch() {
 	fi
 }
 
+maybe_send_nomatch() {
+	local elem="$1"
+	local what="$4"
+
+	[ $((RANDOM%20)) -gt 0 ] && return
+
+	dst_addr4="$2"
+	dst_port="$3"
+	send_udp
+
+	if [ "$(count_packets_nomatch)" != "0" ]; then
+		err "Packet to $dst_addr4:$dst_port did match $what"
+		err "$(nft -a list ruleset)"
+		return 1
+	fi
+}
+
+maybe_send_match() {
+	local elem="$1"
+	local what="$4"
+
+	[ $((RANDOM%20)) -gt 0 ] && return
+
+	dst_addr4="$2"
+	dst_port="$3"
+	send_udp
+
+	if [ "$(count_packets "{ $elem }")" != "1" ]; then
+		err "Packet to $dst_addr4:$dst_port did not match $what"
+		err "$(nft -a list ruleset)"
+		return 1
+	fi
+	nft reset counter inet filter test >/dev/null
+	nft reset element inet filter test "{ $elem }" >/dev/null
+}
+
 # Correctness test template:
 # - add ranged element, check that packets match it
 # - check that packets outside range don't match it
@@ -1776,22 +1812,34 @@ test_bug_net_port_proto_match() {
 	range_size=1
 	for i in $(seq 1 10); do
 		for j in $(seq 1 20) ; do
-			elem=$(printf "10.%d.%d.0/24 . %d1-%d0 . 6-17 " ${i} ${j} ${i} "$((i+1))")
+			local dport=$j
+
+			elem=$(printf "10.%d.%d.0/24 . %d-%d0 . 6-17 " ${i} ${j} ${dport} "$((dport+1))")
+
+			# too slow, do not test all addresses
+			maybe_send_nomatch "$elem" $(printf "10.%d.%d.1" $i $j) $(printf "%d1" $((dport+1))) "before add" || return 1
 
 			nft "add element inet filter test { $elem }" || return 1
+
+			maybe_send_match "$elem" $(printf "10.%d.%d.1" $i $j) $(printf "%d" $dport) "after add" || return 1
+
 			nft "get element inet filter test { $elem }" | grep -q "$elem"
 			if [ $? -ne 0 ];then
 				local got=$(nft "get element inet filter test { $elem }")
 				err "post-add: should have returned $elem but got $got"
 				return 1
 			fi
+
+			maybe_send_nomatch "$elem" $(printf "10.%d.%d.1" $i $j) $(printf "%d1" $((dport+1))) "out-of-range" || return 1
 		done
 	done
 
 	# recheck after set was filled
 	for i in $(seq 1 10); do
 		for j in $(seq 1 20) ; do
-			elem=$(printf "10.%d.%d.0/24 . %d1-%d0 . 6-17 " ${i} ${j} ${i} "$((i+1))")
+			local dport=$j
+
+			elem=$(printf "10.%d.%d.0/24 . %d-%d0 . 6-17 " ${i} ${j} ${dport} "$((dport+1))")
 
 			nft "get element inet filter test { $elem }" | grep -q "$elem"
 			if [ $? -ne 0 ];then
@@ -1799,6 +1847,9 @@ test_bug_net_port_proto_match() {
 				err "post-fill: should have returned $elem but got $got"
 				return 1
 			fi
+
+			maybe_send_match "$elem" $(printf "10.%d.%d.1" $i $j) $(printf "%d" $dport) "recheck" || return 1
+			maybe_send_nomatch "$elem" $(printf "10.%d.%d.1" $i $j) $(printf "%d1" $((dport+1))) "recheck out-of-range" || return 1
 		done
 	done
 
@@ -1806,9 +1857,10 @@ test_bug_net_port_proto_match() {
 	for i in $(seq 1 10); do
 		for j in $(seq 1 20) ; do
 			local rnd=$((RANDOM%10))
+			local dport=$j
 			local got=""
 
-			elem=$(printf "10.%d.%d.0/24 . %d1-%d0 . 6-17 " ${i} ${j} ${i} "$((i+1))")
+			elem=$(printf "10.%d.%d.0/24 . %d-%d0 . 6-17 " ${i} ${j} ${dport} "$((dport+1))")
 			if [ $rnd -gt 0 ];then
 				continue
 			fi
@@ -1819,6 +1871,8 @@ test_bug_net_port_proto_match() {
 				err "post-delete: query for $elem returned $got instead of error."
 				return 1
 			fi
+
+			maybe_send_nomatch "$elem" $(printf "10.%d.%d.1" $i $j) $(printf "%d" $dport) "match after deletion" || return 1
 		done
 	done
 
-- 
2.49.0

Re: [PATCH nf-next 0/3] netfilter: nf_set_pipapo_avx2: fix initial map fill

[Stefano Brivio]

On Fri, 23 May 2025 14:20:43 +0200
Florian Westphal <fw@strlen.de> wrote:

> The avx2 implementation suffers from the same bug fixed in the C
> implementation with 791a615b7ad2
> ("netfilter: nf_set_pipapo: fix initial map fill").
> 
> If the first field isn't the largest one, there will be mismatches, i.e.
> a wrong match will be returned.

...weird that we didn't catch this together with the issue described
by 791a615b7ad2, I guess it wasn't found on x86.

> First patch fixes this bug.
> 
> Because the selftest data path test does:
>    .... @test counter name ...
> 
> .. and then checks if the counter has been incremented, the selftest
> first needs to be reworked to use per-element counters.

That makes sense indeed, I didn't even know they existed. Actually, I
just learnt about 'nft reset element', that's quite neat.

> Otherwise, we can only differentiate between 'no entry matches' and
> 'some entry matches', but its imperative we can also validate that
> the lookup did return the correct element.
> 
> The second patch does reworks the selftest accordingly.
> 
> Last patch adds extends the existing regression test for this
> bug class by also validating the datapath, rather than just the
> control plane.
> 
> Florian Westphal (3):
>   netfilter: nf_set_pipapo_avx2: fix initial map fill
>   selftests: netfilter: nft_concat_range.sh: prefer per element counters
>     for testing
>   selftests: netfilter: nft_concat_range.sh: add datapath check for map
>     fill bug

For the series,

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

-- 
Stefano

Re: [PATCH nf-next 0/3] netfilter: nf_set_pipapo_avx2: fix initial map fill

[Florian Westphal]

Stefano Brivio <sbrivio@redhat.com> wrote:
> > Because the selftest data path test does:
> >    .... @test counter name ...
> > 
> > .. and then checks if the counter has been incremented, the selftest
> > first needs to be reworked to use per-element counters.
> 
> That makes sense indeed, I didn't even know they existed. Actually, I
> just learnt about 'nft reset element', that's quite neat.

Pipapo predates the per element counters so no wonder you did
not use them in the original selftest :-)

Thanks for reviewing!