Skip to contentSkip to conversation

hsr: Implement more robust duplicate discard algorithm

RFC In review Felix Maurer 3 participants 11 messages Dec 22, 2025 – Jan 8

Subsystems (4)
lore
Share & tools
lore
#0 lore raw

cover hsr: Implement more robust duplicate discard algorithm

The PRP duplicate discard algorithm does not work reliably with certain link faults. Especially with packet loss on one link, the duplicate discard algorithm drops valid packets. For a more thorough description see patch 5.

My suggestion is to replace the current, drop window-based algorithm with a new one that tracks the received sequence numbers individually (description again in patch 5). I am sending this as an RFC to gather feedback mainly on two points:

1. Is the design generally acceptable? Of course, this change leads to higher memory usage and more work to do for each packet. But I argue that this is an acceptable trade-off to make for a more robust PRP behavior with faulty links. After all, PRP is to be used in environments where redundancy is needed and people are ready to maintain two duplicate networks to achieve it.
2. As the tests added in patch 6 show, HSR is subject to similar problems. I do not see a reason not to use a very similar algorithm for HSR as well (with a bitmap for each port). Any objections to doing that (in a later patch series)? This will make the trade-off with memory usage more pronounced, as the hsr_seq_block will grow by three more bitmaps, at least for each HSR node (of which we do not expect too many, as an HSR ring can not be infinitely large).

Most of the patches in this series are for the selftests. This is mainly to demonstrate the problems with the current duplicate discard algorithms, not so much about gathering feedback. Especially patch 1 and 2 are rather preparatory cleanups that do not have much to do with the actual problems the new algorithm tries to solve.

A few points I know not yet addressed are:
- HSR duplicate discard (see above).
- The KUnit test is not updated for the new algorithm. I will work on that before actual patch submission.
- Merging the sequence number blocks when two entries in the node table are merged because they belong to the same node.

Thank you for your feedback already!

---

Felix Maurer (6):
selftests: hsr: Add ping test for PRP
selftests: hsr: Check duplicates on HSR with VLAN
selftests: hsr: Add tests for faulty links
selftests: hsr: Add tests for more link faults with PRP
hsr: Implement more robust duplicate discard for PRP
selftests: hsr: Add more link fault tests for HSR

 net/hsr/hsr_framereg.c                        | 181 ++++++---
 net/hsr/hsr_framereg.h                        |  24 +-
 tools/testing/selftests/net/hsr/Makefile      |   2 +
 tools/testing/selftests/net/hsr/hsr_ping.sh   | 198 +++------
 .../testing/selftests/net/hsr/link_faults.sh  | 376 ++++++++++++++++++
 tools/testing/selftests/net/hsr/prp_ping.sh   | 141 +++++++
 tools/testing/selftests/net/hsr/settings      |   2 +-
 7 files changed, 714 insertions(+), 210 deletions(-)
 create mode 100755 tools/testing/selftests/net/hsr/link_faults.sh
 create mode 100755 tools/testing/selftests/net/hsr/prp_ping.sh

--
2.52.0

#1 lore raw

RFC 1/6 selftests: hsr: Add ping test for PRP

Add a selftest for PRP that performs a basic ping test on IPv4 and IPv6, over the plain PRP interface and a VLAN interface, similar to the existing ping test for HSR. The test first checks reachability of of the other node, then checks for no loss and no duplicates.

---
 tools/testing/selftests/net/hsr/Makefile    |   1 +
 tools/testing/selftests/net/hsr/prp_ping.sh | 141 ++++++++++++++++++++
 2 files changed, 142 insertions(+)
 create mode 100755 tools/testing/selftests/net/hsr/prp_ping.sh
tools/testing/selftests/net/hsr/Makefile +1 -0
index 4b6afc0fe9f8..1886f345897a 100644
@@ -5,6 +5,7 @@ top_srcdir = ../../../../..
 TEST_PROGS := \
 	hsr_ping.sh \
 	hsr_redbox.sh \
+	prp_ping.sh \
 # end of TEST_PROGS
 
 TEST_FILES += hsr_common.sh
tools/testing/selftests/net/hsr/prp_ping.sh new file +141 -0

141 lines not on this page · raw message

Signature · 1 line
2.52.0
#2 lore raw

RFC 2/6 selftests: hsr: Check duplicates on HSR with VLAN

In reply to Felix Maurer

Previously the hsr_ping test only checked that all nodes in a VLAN are reachable (using do_ping). Update the test to also check that there is no packet loss and no duplicate packets by running the same tests for VLANs as without VLANs (including using do_ping_long). This also adds tests for IPv6 over VLAN. To unify the test code, the topology without VLANs now uses IP addresses from dead:beef:0::/64 to align with the 100.64.0.0/24 range for IPv4. Error messages are updated across the board to make it easier to find what actually failed.

Also update the VLAN test to only run in VLAN 2, as there is no need to check if ping really works with VLAN IDs 2, 3, 4, and 5. This lowers the number of long ping tests on VLANs to keep the overall test runtime in bounds.

It's still necessary to bump the test timeout a bit, though: a ping long tests takes 1sec, do_ping_tests performs 12 of them, do_link_problem_tests 6, and the VLAN tests again 12. With some buffer for setup and waiting and for two protocol versions, 90sec timeout seems reasonable.

---
 tools/testing/selftests/net/hsr/hsr_ping.sh | 179 +++++++-------------
 tools/testing/selftests/net/hsr/settings    |   2 +-
 2 files changed, 64 insertions(+), 117 deletions(-)
tools/testing/selftests/net/hsr/hsr_ping.sh +63 -116
index 5a65f4f836be..b162ea07b5c1 100755
@@ -27,31 +27,34 @@ while getopts "$optstring" option;do
 esac
 done
 
-do_complete_ping_test()
+do_ping_tests()
 {
-	echo "INFO: Initial validation ping."
-	# Each node has to be able each one.
-	do_ping "$ns1" 100.64.0.2
-	do_ping "$ns2" 100.64.0.1
-	do_ping "$ns3" 100.64.0.1
-	stop_if_error "Initial validation failed."
-
-	do_ping "$ns1" 100.64.0.3
-	do_ping "$ns2" 100.64.0.3
-	do_ping "$ns3" 100.64.0.2
+	local netid="$1"
 
-	do_ping "$ns1" dead:beef:1::2
-	do_ping "$ns1" dead:beef:1::3
-	do_ping "$ns2" dead:beef:1::1
-	do_ping "$ns2" dead:beef:1::2
-	do_ping "$ns3" dead:beef:1::1
-	do_ping "$ns3" dead:beef:1::2
+	echo "INFO: Running ping tests."
 
-	stop_if_error "Initial validation failed."
+	echo "INFO: Initial validation ping."
+	# Each node has to be able to reach each one.
+	do_ping "$ns1" 100.64.$netid.2
+	do_ping "$ns1" 100.64.$netid.3
+	do_ping "$ns2" 100.64.$netid.1
+	do_ping "$ns2" 100.64.$netid.3
+	do_ping "$ns3" 100.64.$netid.1
+	do_ping "$ns3" 100.64.$netid.2
+	stop_if_error "Initial validation failed on IPv4."
+
+	do_ping "$ns1" dead:beef:$netid::2
+	do_ping "$ns1" dead:beef:$netid::3
+	do_ping "$ns2" dead:beef:$netid::1
+	do_ping "$ns2" dead:beef:$netid::2
+	do_ping "$ns3" dead:beef:$netid::1
+	do_ping "$ns3" dead:beef:$netid::2
+	stop_if_error "Initial validation failed on IPv6."
 
 # Wait until supervisor all supervision frames have been processed and the node
 # entries have been merged. Otherwise duplicate frames will be observed which is
 # valid at this stage.
+	echo "INFO: Wait for node table entries to be merged."
 	WAIT=5
 	while [ ${WAIT} -gt 0 ]
 	do
@@ -68,24 +71,28 @@ do_complete_ping_test()
 	sleep 1
 
 	echo "INFO: Longer ping test."
-	do_ping_long "$ns1" 100.64.0.2
-	do_ping_long "$ns1" dead:beef:1::2
-	do_ping_long "$ns1" 100.64.0.3
-	do_ping_long "$ns1" dead:beef:1::3
-
-	stop_if_error "Longer ping test failed."
-
-	do_ping_long "$ns2" 100.64.0.1
-	do_ping_long "$ns2" dead:beef:1::1
-	do_ping_long "$ns2" 100.64.0.3
-	do_ping_long "$ns2" dead:beef:1::2
-	stop_if_error "Longer ping test failed."
+	do_ping_long "$ns1" 100.64.$netid.2
+	do_ping_long "$ns1" dead:beef:$netid::2
+	do_ping_long "$ns1" 100.64.$netid.3
+	do_ping_long "$ns1" dead:beef:$netid::3
+	stop_if_error "Longer ping test failed (ns1)."
+
+	do_ping_long "$ns2" 100.64.$netid.1
+	do_ping_long "$ns2" dead:beef:$netid::1
+	do_ping_long "$ns2" 100.64.$netid.3
+	do_ping_long "$ns2" dead:beef:$netid::3
+	stop_if_error "Longer ping test failed (ns2)."
+
+	do_ping_long "$ns3" 100.64.$netid.1
+	do_ping_long "$ns3" dead:beef:$netid::1
+	do_ping_long "$ns3" 100.64.$netid.2
+	do_ping_long "$ns3" dead:beef:$netid::2
+	stop_if_error "Longer ping test failed (ns3)."
+}
 
-	do_ping_long "$ns3" 100.64.0.1
-	do_ping_long "$ns3" dead:beef:1::1
-	do_ping_long "$ns3" 100.64.0.2
-	do_ping_long "$ns3" dead:beef:1::2
-	stop_if_error "Longer ping test failed."
+do_link_problem_tests()
+{
+	echo "INFO: Running link problem tests."
 
 	echo "INFO: Cutting one link."
 	do_ping_long "$ns1" 100.64.0.3 &
@@ -104,26 +111,22 @@ do_complete_ping_test()
 
 	do_ping_long "$ns1" 100.64.0.2
 	do_ping_long "$ns1" 100.64.0.3
-
-	stop_if_error "Failed with delay and packetloss."
+	stop_if_error "Failed with delay and packetloss (ns1)."
 
 	do_ping_long "$ns2" 100.64.0.1
 	do_ping_long "$ns2" 100.64.0.3
-
-	stop_if_error "Failed with delay and packetloss."
+	stop_if_error "Failed with delay and packetloss (ns2)."
 
 	do_ping_long "$ns3" 100.64.0.1
 	do_ping_long "$ns3" 100.64.0.2
-	stop_if_error "Failed with delay and packetloss."
-
-	echo "INFO: All good."
+	stop_if_error "Failed with delay and packetloss (ns3)."
 }
 
 setup_hsr_interfaces()
 {
 	local HSRv="$1"
 
-	echo "INFO: preparing interfaces for HSRv${HSRv}."
+	echo "INFO: Preparing interfaces for HSRv${HSRv}."
 # Three HSR nodes. Each node has one link to each of its neighbour, two links in total.
 #
 #    ns1eth1 ----- ns2eth1
@@ -146,11 +149,11 @@ setup_hsr_interfaces()
 
 	# IP for HSR
 	ip -net "$ns1" addr add 100.64.0.1/24 dev hsr1
-	ip -net "$ns1" addr add dead:beef:1::1/64 dev hsr1 nodad
+	ip -net "$ns1" addr add dead:beef:0::1/64 dev hsr1 nodad
 	ip -net "$ns2" addr add 100.64.0.2/24 dev hsr2
-	ip -net "$ns2" addr add dead:beef:1::2/64 dev hsr2 nodad
+	ip -net "$ns2" addr add dead:beef:0::2/64 dev hsr2 nodad
 	ip -net "$ns3" addr add 100.64.0.3/24 dev hsr3
-	ip -net "$ns3" addr add dead:beef:1::3/64 dev hsr3 nodad
+	ip -net "$ns3" addr add dead:beef:0::3/64 dev hsr3 nodad
 
 	ip -net "$ns1" link set address 00:11:22:00:01:01 dev ns1eth1
 	ip -net "$ns1" link set address 00:11:22:00:01:02 dev ns1eth2
@@ -177,85 +180,33 @@ setup_hsr_interfaces()
 
 setup_vlan_interfaces() {
 	ip -net "$ns1" link add link hsr1 name hsr1.2 type vlan id 2
-	ip -net "$ns1" link add link hsr1 name hsr1.3 type vlan id 3
-	ip -net "$ns1" link add link hsr1 name hsr1.4 type vlan id 4
-	ip -net "$ns1" link add link hsr1 name hsr1.5 type vlan id 5
-
 	ip -net "$ns2" link add link hsr2 name hsr2.2 type vlan id 2
-	ip -net "$ns2" link add link hsr2 name hsr2.3 type vlan id 3
-	ip -net "$ns2" link add link hsr2 name hsr2.4 type vlan id 4
-	ip -net "$ns2" link add link hsr2 name hsr2.5 type vlan id 5
-
 	ip -net "$ns3" link add link hsr3 name hsr3.2 type vlan id 2
-	ip -net "$ns3" link add link hsr3 name hsr3.3 type vlan id 3
-	ip -net "$ns3" link add link hsr3 name hsr3.4 type vlan id 4
-	ip -net "$ns3" link add link hsr3 name hsr3.5 type vlan id 5
 
 	ip -net "$ns1" addr add 100.64.2.1/24 dev hsr1.2
-	ip -net "$ns1" addr add 100.64.3.1/24 dev hsr1.3
-	ip -net "$ns1" addr add 100.64.4.1/24 dev hsr1.4
-	ip -net "$ns1" addr add 100.64.5.1/24 dev hsr1.5
+	ip -net "$ns1" addr add dead:beef:2::1/64 dev hsr1.2 nodad
 
 	ip -net "$ns2" addr add 100.64.2.2/24 dev hsr2.2
-	ip -net "$ns2" addr add 100.64.3.2/24 dev hsr2.3
-	ip -net "$ns2" addr add 100.64.4.2/24 dev hsr2.4
-	ip -net "$ns2" addr add 100.64.5.2/24 dev hsr2.5
+	ip -net "$ns2" addr add dead:beef:2::2/64 dev hsr2.2 nodad
 
 	ip -net "$ns3" addr add 100.64.2.3/24 dev hsr3.2
-	ip -net "$ns3" addr add 100.64.3.3/24 dev hsr3.3
-	ip -net "$ns3" addr add 100.64.4.3/24 dev hsr3.4
-	ip -net "$ns3" addr add 100.64.5.3/24 dev hsr3.5
+	ip -net "$ns3" addr add dead:beef:2::3/64 dev hsr3.2 nodad
 
 	ip -net "$ns1" link set dev hsr1.2 up
-	ip -net "$ns1" link set dev hsr1.3 up
-	ip -net "$ns1" link set dev hsr1.4 up
-	ip -net "$ns1" link set dev hsr1.5 up
-
 	ip -net "$ns2" link set dev hsr2.2 up
-	ip -net "$ns2" link set dev hsr2.3 up
-	ip -net "$ns2" link set dev hsr2.4 up
-	ip -net "$ns2" link set dev hsr2.5 up
-
 	ip -net "$ns3" link set dev hsr3.2 up
-	ip -net "$ns3" link set dev hsr3.3 up
-	ip -net "$ns3" link set dev hsr3.4 up
-	ip -net "$ns3" link set dev hsr3.5 up
 
 }
 
-hsr_vlan_ping() {
-	do_ping "$ns1" 100.64.2.2
-	do_ping "$ns1" 100.64.3.2
-	do_ping "$ns1" 100.64.4.2
-	do_ping "$ns1" 100.64.5.2
-
-	do_ping "$ns1" 100.64.2.3
-	do_ping "$ns1" 100.64.3.3
-	do_ping "$ns1" 100.64.4.3
-	do_ping "$ns1" 100.64.5.3
-
-	do_ping "$ns2" 100.64.2.1
-	do_ping "$ns2" 100.64.3.1
-	do_ping "$ns2" 100.64.4.1
-	do_ping "$ns2" 100.64.5.1
-
-	do_ping "$ns2" 100.64.2.3
-	do_ping "$ns2" 100.64.3.3
-	do_ping "$ns2" 100.64.4.3
-	do_ping "$ns2" 100.64.5.3
-
-	do_ping "$ns3" 100.64.2.1
-	do_ping "$ns3" 100.64.3.1
-	do_ping "$ns3" 100.64.4.1
-	do_ping "$ns3" 100.64.5.1
-
-	do_ping "$ns3" 100.64.2.2
-	do_ping "$ns3" 100.64.3.2
-	do_ping "$ns3" 100.64.4.2
-	do_ping "$ns3" 100.64.5.2
+run_complete_ping_tests()
+{
+	echo "INFO: Running complete ping tests."
+	do_ping_tests 0
+	do_link_problem_tests
 }
 
-run_vlan_tests() {
+run_vlan_tests()
+{
 	vlan_challenged_hsr1=$(ip net exec "$ns1" ethtool -k hsr1 | grep "vlan-challenged" | awk '{print $2}')
 	vlan_challenged_hsr2=$(ip net exec "$ns2" ethtool -k hsr2 | grep "vlan-challenged" | awk '{print $2}')
 	vlan_challenged_hsr3=$(ip net exec "$ns3" ethtool -k hsr3 | grep "vlan-challenged" | awk '{print $2}')
@@ -263,27 +214,23 @@ run_vlan_tests() {
 	if [[ "$vlan_challenged_hsr1" = "off" || "$vlan_challenged_hsr2" = "off" || "$vlan_challenged_hsr3" = "off" ]]; then
 		echo "INFO: Running VLAN tests"
 		setup_vlan_interfaces
-		hsr_vlan_ping
+		do_ping_tests 2
 	else
 		echo "INFO: Not Running VLAN tests as the device does not support VLAN"
 	fi
 }
 
 check_prerequisites
-setup_ns ns1 ns2 ns3
-
 trap cleanup_all_ns EXIT
 
+setup_ns ns1 ns2 ns3
 setup_hsr_interfaces 0
-do_complete_ping_test
-
+run_complete_ping_tests
 run_vlan_tests
 
 setup_ns ns1 ns2 ns3
-
 setup_hsr_interfaces 1
-do_complete_ping_test
-
+run_complete_ping_tests
 run_vlan_tests
 
 exit $ret
tools/testing/selftests/net/hsr/settings +1 -1
index 0fbc037f2aa8..ba4d85f74cd6 100644
@@ -1 +1 @@
-timeout=50
+timeout=90

--
2.52.0

#3 lore raw

RFC 3/6 selftests: hsr: Add tests for faulty links

In reply to Felix Maurer

Add a test case that can support different types of faulty links for all protocol versions (HSRv0, HSRv1, PRPv1). It starts with a baseline with fully functional links. The first faulty case is one link being cut during the ping. This test uses a different function for ping that sends more packets in shorter intervals to stress the duplicate detection algorithms a bit more and allow for future tests with other link faults (packet loss, reordering, etc.).

As the link fault tests now cover the cut link for HSR and PRP, it can be removed from the hsr_ping test. Note that the removed cut link test did not really test the fault because do_ping_long takes about 1sec while the link is only cut after a 3sec sleep.

---
 tools/testing/selftests/net/hsr/Makefile      |   1 +
 tools/testing/selftests/net/hsr/hsr_ping.sh   |  11 -
 .../testing/selftests/net/hsr/link_faults.sh  | 269 ++++++++++++++++++
 3 files changed, 270 insertions(+), 11 deletions(-)
 create mode 100755 tools/testing/selftests/net/hsr/link_faults.sh
tools/testing/selftests/net/hsr/Makefile +1 -0
index 1886f345897a..31fb9326cf53 100644
@@ -5,6 +5,7 @@ top_srcdir = ../../../../..
 TEST_PROGS := \
 	hsr_ping.sh \
 	hsr_redbox.sh \
+	link_faults.sh \
 	prp_ping.sh \
 # end of TEST_PROGS
 
tools/testing/selftests/net/hsr/hsr_ping.sh +0 -11
index b162ea07b5c1..7cb752c25ff2 100755
@@ -94,17 +94,6 @@ do_link_problem_tests()
 {
 	echo "INFO: Running link problem tests."
 
-	echo "INFO: Cutting one link."
-	do_ping_long "$ns1" 100.64.0.3 &
-
-	sleep 3
-	ip -net "$ns3" link set ns3eth1 down
-	wait
-
-	ip -net "$ns3" link set ns3eth1 up
-
-	stop_if_error "Failed with one link down."
-
 	echo "INFO: Delay the link and drop a few packages."
 	tc -net "$ns3" qdisc add dev ns3eth1 root netem delay 50ms
 	tc -net "$ns2" qdisc add dev ns2eth1 root netem delay 5ms loss 25%
tools/testing/selftests/net/hsr/link_faults.sh new file +269 -0

269 lines not on this page · raw message

Signature · 1 line
2.52.0
#4 lore raw

RFC 4/6 selftests: hsr: Add tests for more link faults with PRP

In reply to Felix Maurer

Add tests where one link has different rates of packet loss or reorders packets. PRP should still be able to recover from these link faults and show no packet loss. However, it is acceptable to receive some level of duplicate packets. This matches the current specification (IEC 62439-3:2021) of the duplicate discard algorithm that requires it to be "designed such that it never rejects a legitimate frame, while occasional acceptance of a duplicate can be tolerated." The rate of acceptable duplicates in this test is intentionally high (10%) to make the test stable, the values I observed in the worst test cases (20% loss) are around 5% duplicates.

---
 .../testing/selftests/net/hsr/link_faults.sh  | 79 +++++++++++++++++--
 1 file changed, 74 insertions(+), 5 deletions(-)
tools/testing/selftests/net/hsr/link_faults.sh +74 -5
index b00fdba62f17..11a55ba5cd7d 100755
@@ -10,10 +10,16 @@ ALL_TESTS="
 	test_cut_link_hsrv1
 	test_clean_prp
 	test_cut_link_prp
+	test_packet_loss_prp
+	test_high_packet_loss_prp
+	test_reordering_prp
 "
 
-# The tests are running ping for 5sec with a relatively short interval with a
-# cut link, which should be recoverable by HSR/PRP.
+# The tests are running ping for 5sec with a relatively short interval in
+# different scenarios with faulty links (cut links, packet loss, delay,
+# reordering) that should be recoverable by HSR/PRP. The ping interval (10ms)
+# is short enough that the base delay (50ms) leads to a queue in the netem
+# qdiscs which is needed for reordering.
 
 setup_hsr_topo()
 {
@@ -152,6 +158,7 @@ check_ping()
 {
 	local node="$1"
 	local dst="$2"
+	local accepted_dups="$3"
 	local ping_args="-q -i 0.01 -c 400"
 
 	log_info "Running ping $node -> $dst"
@@ -176,7 +183,9 @@ check_ping()
 		loss="${BASH_REMATCH[1]}"
 	fi
 
-	check_err "$dups" "Unexpected duplicate packets (${dups})"
+	if [ "$dups" -gt "$accepted_dups" ]; then
+		check_err 1 "Unexpected duplicate packets (${dups})"
+	fi
 	if [ "$loss" != "0%" ]; then
 		check_err 1 "Unexpected packet loss (${loss})"
 	fi
@@ -195,7 +204,7 @@ test_clean()
 		return
 	fi
 
-	check_ping "$node1" "100.64.0.2"
+	check_ping "$node1" "100.64.0.2" 0
 
 	log_test "${tname}"
 }
@@ -235,7 +244,7 @@ test_cut_link()
 		log_info "Cutting link"
 		ip -net "$node1" link set vethB down
 	) &
-	check_ping "$node1" "100.64.0.2"
+	check_ping "$node1" "100.64.0.2" 0
 
 	wait
 	log_test "${tname}"
@@ -257,6 +266,66 @@ test_cut_link_prp()
 	test_cut_link "PRP"
 }
 
+test_packet_loss()
+{
+	local proto="$1"
+	local loss="$2"
+
+	RET=0
+	tname="${FUNCNAME} - ${proto}, ${loss}"
+
+	setup_topo "$proto"
+	if ((RET != ksft_pass)); then
+		log_test "${tname} setup"
+		return
+	fi
+
+	# Packet loss with lower delay makes sure the packets on the lossy link
+	# arrive first.
+	tc -net "$node1" qdisc add dev vethA root netem delay 50ms
+	tc -net "$node1" qdisc add dev vethB root netem delay 20ms loss "$loss"
+
+	check_ping "$node1" "100.64.0.2" 40
+
+	log_test "${tname}"
+}
+
+test_packet_loss_prp()
+{
+	test_packet_loss "PRP" "20%"
+}
+
+test_high_packet_loss_prp()
+{
+	test_packet_loss "PRP" "80%"
+}
+
+test_reordering()
+{
+	local proto="$1"
+
+	RET=0
+	tname="${FUNCNAME} - ${proto}"
+
+	setup_topo "$proto"
+	if ((RET != ksft_pass)); then
+		log_test "${tname} setup"
+		return
+	fi
+
+	tc -net "$node1" qdisc add dev vethA root netem delay 50ms
+	tc -net "$node1" qdisc add dev vethB root netem delay 50ms reorder 20%
+
+	check_ping "$node1" "100.64.0.2" 40
+
+	log_test "${tname}"
+}
+
+test_reordering_prp()
+{
+	test_reordering "PRP"
+}
+
 cleanup()
 {
 	cleanup_all_ns
Signature · 1 line
2.52.0
#5 lore raw

RFC 5/6 hsr: Implement more robust duplicate discard for PRP

In reply to Felix Maurer

The PRP duplicate discard algorithm does not work reliably with certain link faults. Especially with packet loss on one link, the duplicate discard algorithm drops valid packets which leads to packet loss on the PRP interface where the link fault should in theory be perfectly recoverable by PRP. This happens because the algorithm opens the drop window on the lossy link, covering received and lost sequence numbers. If the other, non-lossy link receives the duplicate for a lost frame, it is within the drop window of the lossy link and therefore dropped.

Since IEC 62439-3:2012, a node has one sequence number counter for frames it sends, instead of one sequence number counter for each destination. Therefore, a node can not expect to receive contiguous sequence numbers from a sender. A missing sequence number can be totally normal (if the sender intermittently communicates with another node) or mean a frame was lost.

The algorithm, as previously implemented in commit 05fd00e5e7b1 ("net: hsr:
Fix PRP duplicate detection"), was part of IEC 62439-3:2010 (HSRv0/PRPv0) but was removed with IEC 62439-3:2012 (HSRv1/PRPv1). Since that, no algorithm is specified but up to implementers. It should be "designed such that it never rejects a legitimate frame, while occasional acceptance of a duplicate can be tolerated" (IEC 62439-3:2021).

For the duplicate discard algorithm, this means that 1) we need to track the sequence numbers individually to account for non-contiguous sequence numbers, and 2) we should always err on the side of accepting a duplicate than dropping a valid frame.

The idea of the new algorithm is to store the seen sequence numbers in a bitmap. To keep the size of the bitmap in control, we store it as a "sparse bitmap" where the bitmap is split into blocks and not all blocks exist at the same time. The sparse bitmap is implemented using an xarray that keeps the references to the individual blocks and a backing ring buffer that stores the actual blocks. New blocks are initialized in the buffer and added to the xarray as needed when new frames arrive. Existing blocks are removed in two conditions:
1. The block found for an arriving sequence number is old and therefore not relevant to the duplicate discard algorithm anymore, i.e., it has been added more than than the entry forget time ago. In this case, the block is removed from the xarray and marked as forgotten (by setting its timestamp to 0).
2. Space is needed in the ring buffer for a new block. In this case, the block is removed from the xarray, if it hasn't already been forgotten (by 1.). Afterwards, the new block is initialized in its place.

All of this still happens under seq_out_lock, to prevent concurrent access to the blocks.

Fixes 05fd00e5e7b1 ("net: hsr: Fix PRP duplicate detection")
---
 net/hsr/hsr_framereg.c | 181 ++++++++++++++++++++++++++---------------
 net/hsr/hsr_framereg.h |  24 +++++-
 2 files changed, 138 insertions(+), 67 deletions(-)
net/hsr/hsr_framereg.c +117 -64
index 3a2a2fa7a0a3..c6e9d3a2648a 100644
@@ -126,13 +126,28 @@ void hsr_del_self_node(struct hsr_priv *hsr)
 		kfree_rcu(old, rcu_head);
 }
 
+static void hsr_free_node(struct hsr_node *node)
+{
+	xa_destroy(&node->seq_blocks);
+	kfree(node->block_buf);
+	kfree(node);
+}
+
+static void hsr_free_node_rcu(struct rcu_head *rn)
+{
+	struct hsr_node *node = container_of(rn, struct hsr_node, rcu_head);
+	hsr_free_node(node);
+}
+
 void hsr_del_nodes(struct list_head *node_db)
 {
 	struct hsr_node *node;
 	struct hsr_node *tmp;
 
-	list_for_each_entry_safe(node, tmp, node_db, mac_list)
-		kfree(node);
+	list_for_each_entry_safe(node, tmp, node_db, mac_list) {
+		list_del(&node->mac_list);
+		hsr_free_node(node);
+	}
 }
 
 void prp_handle_san_frame(bool san, enum hsr_port_type port,
@@ -176,11 +191,7 @@ static struct hsr_node *hsr_add_node(struct hsr_priv *hsr,
 	for (i = 0; i < HSR_PT_PORTS; i++) {
 		new_node->time_in[i] = now;
 		new_node->time_out[i] = now;
-	}
-	for (i = 0; i < HSR_PT_PORTS; i++) {
 		new_node->seq_out[i] = seq_out;
-		new_node->seq_expected[i] = seq_out + 1;
-		new_node->seq_start[i] = seq_out + 1;
 	}
 
 	if (san && hsr->proto_ops->handle_san_frame)
@@ -194,11 +205,20 @@ static struct hsr_node *hsr_add_node(struct hsr_priv *hsr,
 		if (ether_addr_equal(node->macaddress_B, addr))
 			goto out;
 	}
+
+	new_node->block_buf = kcalloc(HSR_MAX_SEQ_BLOCKS,
+				      sizeof(struct hsr_seq_block),
+				      GFP_ATOMIC);
+	if (!new_node->block_buf)
+		goto out;
+
+	xa_init(&new_node->seq_blocks);
 	list_add_tail_rcu(&new_node->mac_list, node_db);
 	spin_unlock_bh(&hsr->list_lock);
 	return new_node;
 out:
 	spin_unlock_bh(&hsr->list_lock);
+	kfree(new_node->block_buf);
 	kfree(new_node);
 	return node;
 }
@@ -283,6 +303,9 @@ struct hsr_node *hsr_get_node(struct hsr_port *port, struct list_head *node_db,
 /* Use the Supervision frame's info about an eventual macaddress_B for merging
  * nodes that has previously had their macaddress_B registered as a separate
  * node.
+ * TODO Merging PRP nodes currently looses the info on received sequence numbers
+ * from one node. This may lead to some duplicates being received but does no
+ * harm otherwise.
  */
 void hsr_handle_sup_frame(struct hsr_frame_info *frame)
 {
@@ -398,7 +421,7 @@ void hsr_handle_sup_frame(struct hsr_frame_info *frame)
 	if (!node_curr->removed) {
 		list_del_rcu(&node_curr->mac_list);
 		node_curr->removed = true;
-		kfree_rcu(node_curr, rcu_head);
+		call_rcu(&node_curr->rcu_head, hsr_free_node_rcu);
 	}
 	spin_unlock_bh(&hsr->list_lock);
 
@@ -505,17 +528,66 @@ int hsr_register_frame_out(struct hsr_port *port, struct hsr_frame_info *frame)
 	return 0;
 }
 
-/* Adaptation of the PRP duplicate discard algorithm described in wireshark
- * wiki (https://wiki.wireshark.org/PRP)
- *
- * A drop window is maintained for both LANs with start sequence set to the
- * first sequence accepted on the LAN that has not been seen on the other LAN,
- * and expected sequence set to the latest received sequence number plus one.
- *
- * When a frame is received on either LAN it is compared against the received
- * frames on the other LAN. If it is outside the drop window of the other LAN
- * the frame is accepted and the drop window is updated.
- * The drop window for the other LAN is reset.
+static bool hsr_seq_block_is_old(struct hsr_seq_block *block)
+{
+	unsigned long expiry = msecs_to_jiffies(HSR_ENTRY_FORGET_TIME);
+
+	return time_is_before_jiffies(block->time + expiry);
+}
+
+static void hsr_forget_seq_block(struct hsr_node *node,
+				 struct hsr_seq_block *block)
+{
+	if (block->time)
+		xa_erase(&node->seq_blocks, block->block_idx);
+	block->time = 0;
+}
+
+/* Get the currently active sequence number block. If there is no block yet, or
+ * the existing one is expired, a new block is created. The idea is to maintain
+ * a "sparse bitmap" where a bitmap for the whole sequence number space is
+ * split into blocks and not all blocks exist all the time. The blocks can
+ * expire after time (in low traffic situations) or when they are replaced in
+ * the backing fixed size buffer (in high traffic situations).
+ */
+static struct hsr_seq_block *hsr_get_active_seq_block(struct hsr_node *node, u16 seq_nr)
+{
+	struct hsr_seq_block *block, *res;
+	u16 block_idx;
+
+	block_idx = seq_nr >> HSR_SEQ_BLOCK_SHIFT;
+	block = xa_load(&node->seq_blocks, block_idx);
+
+	if (block && hsr_seq_block_is_old(block)) {
+		hsr_forget_seq_block(node, block);
+		block = NULL;
+	}
+
+	if (!block) {
+		block = &node->block_buf[node->next_block];
+		hsr_forget_seq_block(node, block);
+
+		memset(block, 0, sizeof(*block));
+		block->time = jiffies;
+		block->block_idx = block_idx;
+
+		res = xa_store(&node->seq_blocks, block_idx, block, GFP_ATOMIC);
+		if (xa_is_err(res))
+			return NULL;
+
+		node->next_block = (node->next_block + 1) & (HSR_MAX_SEQ_BLOCKS - 1);
+	}
+
+	return block;
+}
+
+/* PRP duplicate discard algorithm: we maintain a bitmap where we set a bit for
+ * every seen sequence number. The bitmap is split into blocks and the block
+ * management is detailed in hsr_get_active_seq_block(). In any case, we err on
+ * the side of accepting a packet, as the specification requires the algorithm
+ * to be "designed such that it never rejects a legitimate frame, while
+ * occasional acceptance of a duplicate can be tolerated." (IEC 62439-3:2021,
+ * 4.1.10.3).
  *
  * 'port' is the outgoing interface
  * 'frame' is the frame to be sent
@@ -526,18 +598,21 @@ int hsr_register_frame_out(struct hsr_port *port, struct hsr_frame_info *frame)
  */
 int prp_register_frame_out(struct hsr_port *port, struct hsr_frame_info *frame)
 {
-	enum hsr_port_type other_port;
-	enum hsr_port_type rcv_port;
+	struct hsr_seq_block *block;
+	u16 sequence_nr, seq_bit;
 	struct hsr_node *node;
-	u16 sequence_diff;
-	u16 sequence_exp;
-	u16 sequence_nr;
 
-	/* out-going frames are always in order
-	 * and can be checked the same way as for HSR
-	 */
-	if (frame->port_rcv->type == HSR_PT_MASTER)
-		return hsr_register_frame_out(port, frame);
+	node = frame->node_src;
+	sequence_nr = frame->sequence_nr;
+
+	// out-going frames are always in order
+	if (frame->port_rcv->type == HSR_PT_MASTER) {
+		spin_lock_bh(&node->seq_out_lock);
+		node->time_out[port->type] = jiffies;
+		node->seq_out[port->type] = sequence_nr;
+		spin_unlock_bh(&node->seq_out_lock);
+		return 0;
+	}
 
 	/* for PRP we should only forward frames from the slave ports
 	 * to the master port
@@ -545,47 +620,25 @@ int prp_register_frame_out(struct hsr_port *port, struct hsr_frame_info *frame)
 	if (port->type != HSR_PT_MASTER)
 		return 1;
 
-	node = frame->node_src;
-	sequence_nr = frame->sequence_nr;
-	sequence_exp = sequence_nr + 1;
-	rcv_port = frame->port_rcv->type;
-	other_port = rcv_port == HSR_PT_SLAVE_A ? HSR_PT_SLAVE_B :
-				 HSR_PT_SLAVE_A;
-
 	spin_lock_bh(&node->seq_out_lock);
-	if (time_is_before_jiffies(node->time_out[port->type] +
-	    msecs_to_jiffies(HSR_ENTRY_FORGET_TIME)) ||
-	    (node->seq_start[rcv_port] == node->seq_expected[rcv_port] &&
-	     node->seq_start[other_port] == node->seq_expected[other_port])) {
-		/* the node hasn't been sending for a while
-		 * or both drop windows are empty, forward the frame
-		 */
-		node->seq_start[rcv_port] = sequence_nr;
-	} else if (seq_nr_before(sequence_nr, node->seq_expected[other_port]) &&
-		   seq_nr_before_or_eq(node->seq_start[other_port], sequence_nr)) {
-		/* drop the frame, update the drop window for the other port
-		 * and reset our drop window
-		 */
-		node->seq_start[other_port] = sequence_exp;
-		node->seq_expected[rcv_port] = sequence_exp;
-		node->seq_start[rcv_port] = node->seq_expected[rcv_port];
-		spin_unlock_bh(&node->seq_out_lock);
-		return 1;
-	}
 
-	/* update the drop window for the port where this frame was received
-	 * and clear the drop window for the other port
-	 */
-	node->seq_start[other_port] = node->seq_expected[other_port];
-	node->seq_expected[rcv_port] = sequence_exp;
-	sequence_diff = sequence_exp - node->seq_start[rcv_port];
-	if (sequence_diff > PRP_DROP_WINDOW_LEN)
-		node->seq_start[rcv_port] = sequence_exp - PRP_DROP_WINDOW_LEN;
+	block = hsr_get_active_seq_block(node, sequence_nr);
+	if (WARN_ON_ONCE(!block))
+		goto out_new;
+
+	seq_bit = sequence_nr & HSR_SEQ_BLOCK_MASK;
+	if (test_and_set_bit(seq_bit, block->seq_nrs))
+		goto out_seen;
 
 	node->time_out[port->type] = jiffies;
 	node->seq_out[port->type] = sequence_nr;
+out_new:
 	spin_unlock_bh(&node->seq_out_lock);
 	return 0;
+
+out_seen:
+	spin_unlock_bh(&node->seq_out_lock);
+	return 1;
 }
 
 #if IS_MODULE(CONFIG_PRP_DUP_DISCARD_KUNIT_TEST)
@@ -672,7 +725,7 @@ void hsr_prune_nodes(struct timer_list *t)
 				list_del_rcu(&node->mac_list);
 				node->removed = true;
 				/* Note that we need to free this entry later: */
-				kfree_rcu(node, rcu_head);
+				call_rcu(&node->rcu_head, hsr_free_node_rcu);
 			}
 		}
 	}
@@ -706,7 +759,7 @@ void hsr_prune_proxy_nodes(struct timer_list *t)
 				list_del_rcu(&node->mac_list);
 				node->removed = true;
 				/* Note that we need to free this entry later: */
-				kfree_rcu(node, rcu_head);
+				call_rcu(&node->rcu_head, hsr_free_node_rcu);
 			}
 		}
 	}
net/hsr/hsr_framereg.h +21 -3
index b04948659d84..804543d5191c 100644
@@ -74,9 +74,26 @@ bool hsr_is_node_in_db(struct list_head *node_db,
 
 int prp_register_frame_out(struct hsr_port *port, struct hsr_frame_info *frame);
 
+
+#define HSR_SEQ_BLOCK_SHIFT 7 /* 128 bits */
+#define HSR_SEQ_BLOCK_SIZE (1 << HSR_SEQ_BLOCK_SHIFT)
+#define HSR_SEQ_BLOCK_MASK (HSR_SEQ_BLOCK_SIZE - 1)
+#define HSR_MAX_SEQ_BLOCKS 64
+
+struct hsr_seq_block {
+	unsigned long		time;
+	u16			block_idx;
+	DECLARE_BITMAP(seq_nrs, HSR_SEQ_BLOCK_SIZE);
+};
+
+struct hsr_block_buf {
+	struct hsr_seq_block	*buf;
+	int			next;
+};
+
 struct hsr_node {
 	struct list_head	mac_list;
-	/* Protect R/W access to seq_out */
+	/* Protect R/W access to seq_out and seq_blocks */
 	spinlock_t		seq_out_lock;
 	unsigned char		macaddress_A[ETH_ALEN];
 	unsigned char		macaddress_B[ETH_ALEN];
@@ -91,8 +108,9 @@ struct hsr_node {
 	u16			seq_out[HSR_PT_PORTS];
 	bool			removed;
 	/* PRP specific duplicate handling */
-	u16			seq_expected[HSR_PT_PORTS];
-	u16			seq_start[HSR_PT_PORTS];
+	struct xarray		seq_blocks;
+	struct hsr_seq_block	*block_buf;
+	int			next_block;
 	struct rcu_head		rcu_head;
 };
 
Signature · 1 line
2.52.0
#8 lore raw

RFC 6/6 selftests: hsr: Add more link fault tests for HSR

In reply to Felix Maurer

Run the packet loss and reordering tests also for both HSR versions. Now they can be removed from the hsr_ping tests completly. Note that the tests currently fail because the HSR duplicate discard algorithm does not sufficiently take faulty links into account.

The timeout needs to be increased because there are 15 link fault test cases now, with each of them taking 5-6sec for the test and at most 5sec for the HSR node tables to get merged and we also want some room to make the test runs stable.

---
 tools/testing/selftests/net/hsr/hsr_ping.sh   | 32 +++-------------
 .../testing/selftests/net/hsr/link_faults.sh  | 38 +++++++++++++++++++
 tools/testing/selftests/net/hsr/settings      |  2 +-
 3 files changed, 44 insertions(+), 28 deletions(-)
tools/testing/selftests/net/hsr/hsr_ping.sh +5 -27
index 7cb752c25ff2..1ff074dcf93e 100755
@@ -90,27 +90,6 @@ do_ping_tests()
 	stop_if_error "Longer ping test failed (ns3)."
 }
 
-do_link_problem_tests()
-{
-	echo "INFO: Running link problem tests."
-
-	echo "INFO: Delay the link and drop a few packages."
-	tc -net "$ns3" qdisc add dev ns3eth1 root netem delay 50ms
-	tc -net "$ns2" qdisc add dev ns2eth1 root netem delay 5ms loss 25%
-
-	do_ping_long "$ns1" 100.64.0.2
-	do_ping_long "$ns1" 100.64.0.3
-	stop_if_error "Failed with delay and packetloss (ns1)."
-
-	do_ping_long "$ns2" 100.64.0.1
-	do_ping_long "$ns2" 100.64.0.3
-	stop_if_error "Failed with delay and packetloss (ns2)."
-
-	do_ping_long "$ns3" 100.64.0.1
-	do_ping_long "$ns3" 100.64.0.2
-	stop_if_error "Failed with delay and packetloss (ns3)."
-}
-
 setup_hsr_interfaces()
 {
 	local HSRv="$1"
@@ -187,11 +166,10 @@ setup_vlan_interfaces() {
 
 }
 
-run_complete_ping_tests()
+run_ping_tests()
 {
-	echo "INFO: Running complete ping tests."
+	echo "INFO: Running ping tests."
 	do_ping_tests 0
-	do_link_problem_tests
 }
 
 run_vlan_tests()
@@ -201,7 +179,7 @@ run_vlan_tests()
 	vlan_challenged_hsr3=$(ip net exec "$ns3" ethtool -k hsr3 | grep "vlan-challenged" | awk '{print $2}')
 
 	if [[ "$vlan_challenged_hsr1" = "off" || "$vlan_challenged_hsr2" = "off" || "$vlan_challenged_hsr3" = "off" ]]; then
-		echo "INFO: Running VLAN tests"
+		echo "INFO: Running VLAN ping tests"
 		setup_vlan_interfaces
 		do_ping_tests 2
 	else
@@ -214,12 +192,12 @@ trap cleanup_all_ns EXIT
 
 setup_ns ns1 ns2 ns3
 setup_hsr_interfaces 0
-run_complete_ping_tests
+run_ping_tests
 run_vlan_tests
 
 setup_ns ns1 ns2 ns3
 setup_hsr_interfaces 1
-run_complete_ping_tests
+run_ping_tests
 run_vlan_tests
 
 exit $ret
tools/testing/selftests/net/hsr/link_faults.sh +38 -0
index 11a55ba5cd7d..e246a38abb7c 100755
@@ -6,8 +6,16 @@ source ../lib.sh
 ALL_TESTS="
 	test_clean_hsrv0
 	test_cut_link_hsrv0
+	test_packet_loss_hsrv0
+	test_high_packet_loss_hsrv0
+	test_reordering_hsrv0
+
 	test_clean_hsrv1
 	test_cut_link_hsrv1
+	test_packet_loss_hsrv1
+	test_high_packet_loss_hsrv1
+	test_reordering_hsrv1
+
 	test_clean_prp
 	test_cut_link_prp
 	test_packet_loss_prp
@@ -290,11 +298,31 @@ test_packet_loss()
 	log_test "${tname}"
 }
 
+test_packet_loss_hsrv0()
+{
+	test_packet_loss "HSRv0" "20%"
+}
+
+test_packet_loss_hsrv1()
+{
+	test_packet_loss "HSRv1" "20%"
+}
+
 test_packet_loss_prp()
 {
 	test_packet_loss "PRP" "20%"
 }
 
+test_high_packet_loss_hsrv0()
+{
+	test_packet_loss "HSRv0" "80%"
+}
+
+test_high_packet_loss_hsrv1()
+{
+	test_packet_loss "HSRv1" "80%"
+}
+
 test_high_packet_loss_prp()
 {
 	test_packet_loss "PRP" "80%"
@@ -321,6 +349,16 @@ test_reordering()
 	log_test "${tname}"
 }
 
+test_reordering_hsrv0()
+{
+	test_reordering "HSRv0"
+}
+
+test_reordering_hsrv1()
+{
+	test_reordering "HSRv1"
+}
+
 test_reordering_prp()
 {
 	test_reordering "PRP"
tools/testing/selftests/net/hsr/settings +1 -1
index ba4d85f74cd6..a953c96aa16e 100644
@@ -1 +1 @@
-timeout=90
+timeout=180
Signature · 1 line
2.52.0
#6 lore raw

Re: [RFC net 5/6] hsr: Implement more robust duplicate discard for PRP

In reply to Felix Maurer
kernel test robot noticed the following build errors:

Hi Felix,

[This is a private test report for your RFC patch.] kernel test robot noticed the following build errors:

[auto build test ERROR on net/main]

url:    https://github.com/intel-lab-lkp/linux/commits/Felix-Maurer/selftests-hsr-Add-ping-test-for-PRP/20251223-050252
base:   net/main
patch link:    https://lore.kernel.org/r/af4bd23b0a4b417b9ce26d77c1d153cfaf78ec64.1766433800.git.fmaurer%40redhat.com
patch subject: [RFC net 5/6] hsr: Implement more robust duplicate discard for PRP
config: csky-randconfig-r072-20251225 (https://download.01.org/0day-ci/archive/20251225/[email protected]/config)
compiler: csky-linux-gcc (GCC) 12.5.0
reproduce (this is a W=1 build): (https://download.01.org/0day-ci/archive/20251225/[email protected]/reproduce)

If you fix the issue in a separate patch/commit (i.e. not just a new version of the same patch/commit), kindly add following tags
| Reported-by: kernel test robot <[email protected]>
| Closes: https://lore.kernel.org/oe-kbuild-all/[email protected]/

All errors (new ones prefixed by >>):

net/hsr/prp_dup_discard_test.c: In function 'build_prp_test_data':

>> net/hsr/prp_dup_discard_test.c:23:19: error: 'struct hsr_node' has no member named 'seq_start'
      23 |         data->node.seq_start[HSR_PT_SLAVE_A] = 1;
         |                   ^
>> net/hsr/prp_dup_discard_test.c:24:19: error: 'struct hsr_node' has no member named 'seq_expected'
      24 |         data->node.seq_expected[HSR_PT_SLAVE_A] = 1;
         |                   ^
   net/hsr/prp_dup_discard_test.c:25:19: error: 'struct hsr_node' has no member named 'seq_start'
      25 |         data->node.seq_start[HSR_PT_SLAVE_B] = 1;
         |                   ^
   net/hsr/prp_dup_discard_test.c:26:19: error: 'struct hsr_node' has no member named 'seq_expected'
      26 |         data->node.seq_expected[HSR_PT_SLAVE_B] = 1;
         |                   ^
   In file included from net/hsr/prp_dup_discard_test.c:2:
   net/hsr/prp_dup_discard_test.c: In function 'check_prp_counters':
   net/hsr/prp_dup_discard_test.c:39:41: error: 'struct hsr_node' has no member named 'seq_start'
      39 |         KUNIT_EXPECT_EQ(test, data->node.seq_start[HSR_PT_SLAVE_A],
         |                                         ^
   include/kunit/test.h:839:22: note: in definition of macro 'KUNIT_BASE_BINARY_ASSERTION'
     839 |         const typeof(left) __left = (left);                                    \
         |                      ^~~~
   include/kunit/test.h:1035:9: note: in expansion of macro 'KUNIT_BINARY_INT_ASSERTION'
    1035 |         KUNIT_BINARY_INT_ASSERTION(test,                                       \
         |         ^~~~~~~~~~~~~~~~~~~~~~~~~~
   include/kunit/test.h:1032:9: note: in expansion of macro 'KUNIT_EXPECT_EQ_MSG'
    1032 |         KUNIT_EXPECT_EQ_MSG(test, left, right, NULL)
         |         ^~~~~~~~~~~~~~~~~~~
   net/hsr/prp_dup_discard_test.c:39:9: note: in expansion of macro 'KUNIT_EXPECT_EQ'
      39 |         KUNIT_EXPECT_EQ(test, data->node.seq_start[HSR_PT_SLAVE_A],
         |         ^~~~~~~~~~~~~~~
   net/hsr/prp_dup_discard_test.c:39:41: error: 'struct hsr_node' has no member named 'seq_start'
      39 |         KUNIT_EXPECT_EQ(test, data->node.seq_start[HSR_PT_SLAVE_A],
         |                                         ^
   include/kunit/test.h:839:38: note: in definition of macro 'KUNIT_BASE_BINARY_ASSERTION'
     839 |         const typeof(left) __left = (left);                                    \
         |                                      ^~~~
   include/kunit/test.h:1035:9: note: in expansion of macro 'KUNIT_BINARY_INT_ASSERTION'
    1035 |         KUNIT_BINARY_INT_ASSERTION(test,                                       \
         |         ^~~~~~~~~~~~~~~~~~~~~~~~~~
   include/kunit/test.h:1032:9: note: in expansion of macro 'KUNIT_EXPECT_EQ_MSG'
    1032 |         KUNIT_EXPECT_EQ_MSG(test, left, right, NULL)
         |         ^~~~~~~~~~~~~~~~~~~
   net/hsr/prp_dup_discard_test.c:39:9: note: in expansion of macro 'KUNIT_EXPECT_EQ'
      39 |         KUNIT_EXPECT_EQ(test, data->node.seq_start[HSR_PT_SLAVE_A],
         |         ^~~~~~~~~~~~~~~
   net/hsr/prp_dup_discard_test.c:41:41: error: 'struct hsr_node' has no member named 'seq_start'
      41 |         KUNIT_EXPECT_EQ(test, data->node.seq_start[HSR_PT_SLAVE_B],
         |                                         ^
   include/kunit/test.h:839:22: note: in definition of macro 'KUNIT_BASE_BINARY_ASSERTION'
     839 |         const typeof(left) __left = (left);                                    \
         |                      ^~~~
   include/kunit/test.h:1035:9: note: in expansion of macro 'KUNIT_BINARY_INT_ASSERTION'
    1035 |         KUNIT_BINARY_INT_ASSERTION(test,                                       \
         |         ^~~~~~~~~~~~~~~~~~~~~~~~~~
   include/kunit/test.h:1032:9: note: in expansion of macro 'KUNIT_EXPECT_EQ_MSG'
    1032 |         KUNIT_EXPECT_EQ_MSG(test, left, right, NULL)
         |         ^~~~~~~~~~~~~~~~~~~
   net/hsr/prp_dup_discard_test.c:41:9: note: in expansion of macro 'KUNIT_EXPECT_EQ'
      41 |         KUNIT_EXPECT_EQ(test, data->node.seq_start[HSR_PT_SLAVE_B],
         |         ^~~~~~~~~~~~~~~
   net/hsr/prp_dup_discard_test.c:41:41: error: 'struct hsr_node' has no member named 'seq_start'
      41 |         KUNIT_EXPECT_EQ(test, data->node.seq_start[HSR_PT_SLAVE_B],
         |                                         ^
   include/kunit/test.h:839:38: note: in definition of macro 'KUNIT_BASE_BINARY_ASSERTION'
     839 |         const typeof(left) __left = (left);                                    \
         |                                      ^~~~
   include/kunit/test.h:1035:9: note: in expansion of macro 'KUNIT_BINARY_INT_ASSERTION'
    1035 |         KUNIT_BINARY_INT_ASSERTION(test,                                       \
         |         ^~~~~~~~~~~~~~~~~~~~~~~~~~
   include/kunit/test.h:1032:9: note: in expansion of macro 'KUNIT_EXPECT_EQ_MSG'
    1032 |         KUNIT_EXPECT_EQ_MSG(test, left, right, NULL)
         |         ^~~~~~~~~~~~~~~~~~~
   net/hsr/prp_dup_discard_test.c:41:9: note: in expansion of macro 'KUNIT_EXPECT_EQ'
      41 |         KUNIT_EXPECT_EQ(test, data->node.seq_start[HSR_PT_SLAVE_B],
         |         ^~~~~~~~~~~~~~~
   net/hsr/prp_dup_discard_test.c:43:41: error: 'struct hsr_node' has no member named 'seq_expected'
      43 |         KUNIT_EXPECT_EQ(test, data->node.seq_expected[HSR_PT_SLAVE_A],
         |                                         ^
   include/kunit/test.h:839:22: note: in definition of macro 'KUNIT_BASE_BINARY_ASSERTION'
     839 |         const typeof(left) __left = (left);                                    \
         |                      ^~~~
   include/kunit/test.h:1035:9: note: in expansion of macro 'KUNIT_BINARY_INT_ASSERTION'
    1035 |         KUNIT_BINARY_INT_ASSERTION(test,                                       \
         |         ^~~~~~~~~~~~~~~~~~~~~~~~~~
   include/kunit/test.h:1032:9: note: in expansion of macro 'KUNIT_EXPECT_EQ_MSG'
    1032 |         KUNIT_EXPECT_EQ_MSG(test, left, right, NULL)
         |         ^~~~~~~~~~~~~~~~~~~
   net/hsr/prp_dup_discard_test.c:43:9: note: in expansion of macro 'KUNIT_EXPECT_EQ'
      43 |         KUNIT_EXPECT_EQ(test, data->node.seq_expected[HSR_PT_SLAVE_A],
         |         ^~~~~~~~~~~~~~~
   net/hsr/prp_dup_discard_test.c:43:41: error: 'struct hsr_node' has no member named 'seq_expected'
      43 |         KUNIT_EXPECT_EQ(test, data->node.seq_expected[HSR_PT_SLAVE_A],
         |                                         ^
   include/kunit/test.h:839:38: note: in definition of macro 'KUNIT_BASE_BINARY_ASSERTION'
     839 |         const typeof(left) __left = (left);                                    \
         |                                      ^~~~
   include/kunit/test.h:1035:9: note: in expansion of macro 'KUNIT_BINARY_INT_ASSERTION'
    1035 |         KUNIT_BINARY_INT_ASSERTION(test,                                       \
         |         ^~~~~~~~~~~~~~~~~~~~~~~~~~
   include/kunit/test.h:1032:9: note: in expansion of macro 'KUNIT_EXPECT_EQ_MSG'
    1032 |         KUNIT_EXPECT_EQ_MSG(test, left, right, NULL)
         |         ^~~~~~~~~~~~~~~~~~~
   net/hsr/prp_dup_discard_test.c:43:9: note: in expansion of macro 'KUNIT_EXPECT_EQ'
      43 |         KUNIT_EXPECT_EQ(test, data->node.seq_expected[HSR_PT_SLAVE_A],
         |         ^~~~~~~~~~~~~~~

vim +23 net/hsr/prp_dup_discard_test.c

814dbf4b6c955c Jaakko Karrenpalo 2025-03-07  13  
814dbf4b6c955c Jaakko Karrenpalo 2025-03-07  14  static struct prp_test_data *build_prp_test_data(struct kunit *test)
814dbf4b6c955c Jaakko Karrenpalo 2025-03-07  15  {
814dbf4b6c955c Jaakko Karrenpalo 2025-03-07  16  	struct prp_test_data *data = kunit_kzalloc(test,
814dbf4b6c955c Jaakko Karrenpalo 2025-03-07  17  		sizeof(struct prp_test_data), GFP_USER);
814dbf4b6c955c Jaakko Karrenpalo 2025-03-07  18  	KUNIT_EXPECT_NOT_ERR_OR_NULL(test, data);
814dbf4b6c955c Jaakko Karrenpalo 2025-03-07  19  
814dbf4b6c955c Jaakko Karrenpalo 2025-03-07  20  	data->frame.node_src = &data->node;
814dbf4b6c955c Jaakko Karrenpalo 2025-03-07  21  	data->frame.port_rcv = &data->port_rcv;
814dbf4b6c955c Jaakko Karrenpalo 2025-03-07  22  	data->port_rcv.type = HSR_PT_SLAVE_A;
814dbf4b6c955c Jaakko Karrenpalo 2025-03-07 @23  	data->node.seq_start[HSR_PT_SLAVE_A] = 1;
814dbf4b6c955c Jaakko Karrenpalo 2025-03-07 @24  	data->node.seq_expected[HSR_PT_SLAVE_A] = 1;
814dbf4b6c955c Jaakko Karrenpalo 2025-03-07  25  	data->node.seq_start[HSR_PT_SLAVE_B] = 1;
814dbf4b6c955c Jaakko Karrenpalo 2025-03-07  26  	data->node.seq_expected[HSR_PT_SLAVE_B] = 1;
814dbf4b6c955c Jaakko Karrenpalo 2025-03-07  27  	data->node.seq_out[HSR_PT_MASTER] = 0;
814dbf4b6c955c Jaakko Karrenpalo 2025-03-07  28  	data->node.time_out[HSR_PT_MASTER] = jiffies;
814dbf4b6c955c Jaakko Karrenpalo 2025-03-07  29  	data->port.type = HSR_PT_MASTER;
814dbf4b6c955c Jaakko Karrenpalo 2025-03-07  30  
814dbf4b6c955c Jaakko Karrenpalo 2025-03-07  31  	return data;
814dbf4b6c955c Jaakko Karrenpalo 2025-03-07  32  }
814dbf4b6c955c Jaakko Karrenpalo 2025-03-07  33  
Signature · 2 lines
0-DAY CI Kernel Test Service
https://github.com/intel/lkp-tests/wiki
#7 lore raw

Re: [RFC net 5/6] hsr: Implement more robust duplicate discard for PRP

In reply to Felix Maurer
kernel test robot noticed the following build errors:

Hi Felix,

[This is a private test report for your RFC patch.] kernel test robot noticed the following build errors:

[auto build test ERROR on net/main]

url:    https://github.com/intel-lab-lkp/linux/commits/Felix-Maurer/selftests-hsr-Add-ping-test-for-PRP/20251223-050252
base:   net/main
patch link:    https://lore.kernel.org/r/af4bd23b0a4b417b9ce26d77c1d153cfaf78ec64.1766433800.git.fmaurer%40redhat.com
patch subject: [RFC net 5/6] hsr: Implement more robust duplicate discard for PRP
config: arm64-randconfig-001-20251225 (https://download.01.org/0day-ci/archive/20251225/[email protected]/config)
compiler: clang version 18.1.8 (https://github.com/llvm/llvm-project 3b5b5c1ec4a3095ab096dd780e84d7ab81f3d7ff)
reproduce (this is a W=1 build): (https://download.01.org/0day-ci/archive/20251225/[email protected]/reproduce)

If you fix the issue in a separate patch/commit (i.e. not just a new version of the same patch/commit), kindly add following tags
| Reported-by: kernel test robot <[email protected]>
| Closes: https://lore.kernel.org/oe-kbuild-all/[email protected]/

All errors (new ones prefixed by >>):

>> net/hsr/prp_dup_discard_test.c:23:13: error: no member named 'seq_start' in 'struct hsr_node'
      23 |         data->node.seq_start[HSR_PT_SLAVE_A] = 1;
         |         ~~~~~~~~~~ ^
>> net/hsr/prp_dup_discard_test.c:24:13: error: no member named 'seq_expected' in 'struct hsr_node'
      24 |         data->node.seq_expected[HSR_PT_SLAVE_A] = 1;
         |         ~~~~~~~~~~ ^
   net/hsr/prp_dup_discard_test.c:25:13: error: no member named 'seq_start' in 'struct hsr_node'
      25 |         data->node.seq_start[HSR_PT_SLAVE_B] = 1;
         |         ~~~~~~~~~~ ^
   net/hsr/prp_dup_discard_test.c:26:13: error: no member named 'seq_expected' in 'struct hsr_node'
      26 |         data->node.seq_expected[HSR_PT_SLAVE_B] = 1;
         |         ~~~~~~~~~~ ^
   net/hsr/prp_dup_discard_test.c:39:35: error: no member named 'seq_start' in 'struct hsr_node'
      39 |         KUNIT_EXPECT_EQ(test, data->node.seq_start[HSR_PT_SLAVE_A],
         |                               ~~~~~~~~~~ ^
   include/kunit/test.h:1032:28: note: expanded from macro 'KUNIT_EXPECT_EQ'
    1032 |         KUNIT_EXPECT_EQ_MSG(test, left, right, NULL)
         |                                   ^~~~
   include/kunit/test.h:1037:8: note: expanded from macro 'KUNIT_EXPECT_EQ_MSG'
    1037 |                                    left, ==, right,                            \
         |                                    ^~~~
   include/kunit/test.h:873:9: note: expanded from macro 'KUNIT_BINARY_INT_ASSERTION'
     873 |                                     left, op, right,                           \
         |                                     ^~~~
   include/kunit/test.h:839:15: note: expanded from macro 'KUNIT_BASE_BINARY_ASSERTION'
     839 |         const typeof(left) __left = (left);                                    \
         |                      ^~~~
   net/hsr/prp_dup_discard_test.c:39:35: error: no member named 'seq_start' in 'struct hsr_node'
      39 |         KUNIT_EXPECT_EQ(test, data->node.seq_start[HSR_PT_SLAVE_A],
         |                               ~~~~~~~~~~ ^
   include/kunit/test.h:1032:28: note: expanded from macro 'KUNIT_EXPECT_EQ'
    1032 |         KUNIT_EXPECT_EQ_MSG(test, left, right, NULL)
         |                                   ^~~~
   include/kunit/test.h:1037:8: note: expanded from macro 'KUNIT_EXPECT_EQ_MSG'
    1037 |                                    left, ==, right,                            \
         |                                    ^~~~
   include/kunit/test.h:873:9: note: expanded from macro 'KUNIT_BINARY_INT_ASSERTION'
     873 |                                     left, op, right,                           \
         |                                     ^~~~
   include/kunit/test.h:839:31: note: expanded from macro 'KUNIT_BASE_BINARY_ASSERTION'
     839 |         const typeof(left) __left = (left);                                    \
         |                                      ^~~~
   net/hsr/prp_dup_discard_test.c:41:35: error: no member named 'seq_start' in 'struct hsr_node'
      41 |         KUNIT_EXPECT_EQ(test, data->node.seq_start[HSR_PT_SLAVE_B],
         |                               ~~~~~~~~~~ ^
   include/kunit/test.h:1032:28: note: expanded from macro 'KUNIT_EXPECT_EQ'
    1032 |         KUNIT_EXPECT_EQ_MSG(test, left, right, NULL)
         |                                   ^~~~
   include/kunit/test.h:1037:8: note: expanded from macro 'KUNIT_EXPECT_EQ_MSG'
    1037 |                                    left, ==, right,                            \
         |                                    ^~~~
   include/kunit/test.h:873:9: note: expanded from macro 'KUNIT_BINARY_INT_ASSERTION'
     873 |                                     left, op, right,                           \
         |                                     ^~~~
   include/kunit/test.h:839:15: note: expanded from macro 'KUNIT_BASE_BINARY_ASSERTION'
     839 |         const typeof(left) __left = (left);                                    \
         |                      ^~~~
   net/hsr/prp_dup_discard_test.c:41:35: error: no member named 'seq_start' in 'struct hsr_node'
      41 |         KUNIT_EXPECT_EQ(test, data->node.seq_start[HSR_PT_SLAVE_B],
         |                               ~~~~~~~~~~ ^
   include/kunit/test.h:1032:28: note: expanded from macro 'KUNIT_EXPECT_EQ'
    1032 |         KUNIT_EXPECT_EQ_MSG(test, left, right, NULL)
         |                                   ^~~~
   include/kunit/test.h:1037:8: note: expanded from macro 'KUNIT_EXPECT_EQ_MSG'
    1037 |                                    left, ==, right,                            \
         |                                    ^~~~
   include/kunit/test.h:873:9: note: expanded from macro 'KUNIT_BINARY_INT_ASSERTION'
     873 |                                     left, op, right,                           \
         |                                     ^~~~
   include/kunit/test.h:839:31: note: expanded from macro 'KUNIT_BASE_BINARY_ASSERTION'
     839 |         const typeof(left) __left = (left);                                    \
         |                                      ^~~~
   net/hsr/prp_dup_discard_test.c:43:35: error: no member named 'seq_expected' in 'struct hsr_node'
      43 |         KUNIT_EXPECT_EQ(test, data->node.seq_expected[HSR_PT_SLAVE_A],
         |                               ~~~~~~~~~~ ^
   include/kunit/test.h:1032:28: note: expanded from macro 'KUNIT_EXPECT_EQ'
    1032 |         KUNIT_EXPECT_EQ_MSG(test, left, right, NULL)
         |                                   ^~~~
   include/kunit/test.h:1037:8: note: expanded from macro 'KUNIT_EXPECT_EQ_MSG'
    1037 |                                    left, ==, right,                            \
         |                                    ^~~~
   include/kunit/test.h:873:9: note: expanded from macro 'KUNIT_BINARY_INT_ASSERTION'
     873 |                                     left, op, right,                           \
         |                                     ^~~~
   include/kunit/test.h:839:15: note: expanded from macro 'KUNIT_BASE_BINARY_ASSERTION'
     839 |         const typeof(left) __left = (left);                                    \
         |                      ^~~~
   net/hsr/prp_dup_discard_test.c:43:35: error: no member named 'seq_expected' in 'struct hsr_node'
      43 |         KUNIT_EXPECT_EQ(test, data->node.seq_expected[HSR_PT_SLAVE_A],
         |                               ~~~~~~~~~~ ^
   include/kunit/test.h:1032:28: note: expanded from macro 'KUNIT_EXPECT_EQ'
    1032 |         KUNIT_EXPECT_EQ_MSG(test, left, right, NULL)
         |                                   ^~~~
   include/kunit/test.h:1037:8: note: expanded from macro 'KUNIT_EXPECT_EQ_MSG'
    1037 |                                    left, ==, right,                            \
         |                                    ^~~~
   include/kunit/test.h:873:9: note: expanded from macro 'KUNIT_BINARY_INT_ASSERTION'
     873 |                                     left, op, right,                           \
         |                                     ^~~~
   include/kunit/test.h:839:31: note: expanded from macro 'KUNIT_BASE_BINARY_ASSERTION'
     839 |         const typeof(left) __left = (left);                                    \
         |                                      ^~~~
   net/hsr/prp_dup_discard_test.c:45:35: error: no member named 'seq_expected' in 'struct hsr_node'
      45 |         KUNIT_EXPECT_EQ(test, data->node.seq_expected[HSR_PT_SLAVE_B],

vim +23 net/hsr/prp_dup_discard_test.c

814dbf4b6c955c Jaakko Karrenpalo 2025-03-07  13  
814dbf4b6c955c Jaakko Karrenpalo 2025-03-07  14  static struct prp_test_data *build_prp_test_data(struct kunit *test)
814dbf4b6c955c Jaakko Karrenpalo 2025-03-07  15  {
814dbf4b6c955c Jaakko Karrenpalo 2025-03-07  16  	struct prp_test_data *data = kunit_kzalloc(test,
814dbf4b6c955c Jaakko Karrenpalo 2025-03-07  17  		sizeof(struct prp_test_data), GFP_USER);
814dbf4b6c955c Jaakko Karrenpalo 2025-03-07  18  	KUNIT_EXPECT_NOT_ERR_OR_NULL(test, data);
814dbf4b6c955c Jaakko Karrenpalo 2025-03-07  19  
814dbf4b6c955c Jaakko Karrenpalo 2025-03-07  20  	data->frame.node_src = &data->node;
814dbf4b6c955c Jaakko Karrenpalo 2025-03-07  21  	data->frame.port_rcv = &data->port_rcv;
814dbf4b6c955c Jaakko Karrenpalo 2025-03-07  22  	data->port_rcv.type = HSR_PT_SLAVE_A;
814dbf4b6c955c Jaakko Karrenpalo 2025-03-07 @23  	data->node.seq_start[HSR_PT_SLAVE_A] = 1;
814dbf4b6c955c Jaakko Karrenpalo 2025-03-07 @24  	data->node.seq_expected[HSR_PT_SLAVE_A] = 1;
814dbf4b6c955c Jaakko Karrenpalo 2025-03-07  25  	data->node.seq_start[HSR_PT_SLAVE_B] = 1;
814dbf4b6c955c Jaakko Karrenpalo 2025-03-07  26  	data->node.seq_expected[HSR_PT_SLAVE_B] = 1;
814dbf4b6c955c Jaakko Karrenpalo 2025-03-07  27  	data->node.seq_out[HSR_PT_MASTER] = 0;
814dbf4b6c955c Jaakko Karrenpalo 2025-03-07  28  	data->node.time_out[HSR_PT_MASTER] = jiffies;
814dbf4b6c955c Jaakko Karrenpalo 2025-03-07  29  	data->port.type = HSR_PT_MASTER;
814dbf4b6c955c Jaakko Karrenpalo 2025-03-07  30  
814dbf4b6c955c Jaakko Karrenpalo 2025-03-07  31  	return data;
814dbf4b6c955c Jaakko Karrenpalo 2025-03-07  32  }
814dbf4b6c955c Jaakko Karrenpalo 2025-03-07  33  
Signature · 2 lines
0-DAY CI Kernel Test Service
https://github.com/intel/lkp-tests/wiki
reviewer
#9 lore raw
In reply to Felix Maurer
Quoted 10 lines · Felix Maurer

The PRP duplicate discard algorithm does not work reliably with certain link faults. Especially with packet loss on one link, the duplicate discard algorithm drops valid packets. For a more thorough description see patch 5.

My suggestion is to replace the current, drop window-based algorithm with a new one that tracks the received sequence numbers individually (description again in patch 5). I am sending this as an RFC to gather feedback mainly on two points:

Quoted 13 lines

1. Is the design generally acceptable? Of course, this change leads to higher memory usage and more work to do for each packet. But I argue that this is an acceptable trade-off to make for a more robust PRP behavior with faulty links. After all, PRP is to be used in environments where redundancy is needed and people are ready to maintain two duplicate networks to achieve it.
2. As the tests added in patch 6 show, HSR is subject to similar problems. I do not see a reason not to use a very similar algorithm for HSR as well (with a bitmap for each port). Any objections to doing that (in a later patch series)? This will make the trade-off with memory usage more pronounced, as the hsr_seq_block will grow by three more bitmaps, at least for each HSR node (of which we do not expect too many, as an HSR ring can not be infinitely large).

Hi Felix,

Happy New Year!

We have spoken about this offline before and I agree that the situation should be improved.

IMHO the trade-offs you are making here seem reasonable. And I wonder if it helps to think in terms of the expected usage of this code: Is it expected to scale to a point where the memory and CPU overhead becomes unreasonable; or do, as I think you imply above, we expect deployments to be on systems where the trade-offs are acceptable?

Quoted 11 lines

Most of the patches in this series are for the selftests. This is mainly to demonstrate the problems with the current duplicate discard algorithms, not so much about gathering feedback. Especially patch 1 and 2 are rather preparatory cleanups that do not have much to do with the actual problems the new algorithm tries to solve.

A few points I know not yet addressed are:
- HSR duplicate discard (see above).
- The KUnit test is not updated for the new algorithm. I will work on that before actual patch submission.

FTR, the KUnit tests no longer compiles. But probably you already knew that.

Quoted 4 lines

- Merging the sequence number blocks when two entries in the node table are merged because they belong to the same node.

Thank you for your feedback already!

Some slightly more specific feedback:

* These patches are probably for net-next rather than net

* Please run checkpatch.pl --max-line-length=80 --codespell (on each patch)
- And fix the line lengths where it doesn't reduce readability. E.g. don't split strings

* Please also run shellcheck on the selftests
- As much as is reasonable please address the warnings
- In general new .sh files should be shellcheck-clean
- To aid this, use "# shellcheck disable=CASE", for cases that don't match the way selftests are written , e.g. SC2154 and SC2034

* I was curious to see LANG=C in at least one of the selftests. And I do see limited precedence for that. I'm just mentioning that I was surprised as I'd always thought it was an implied requirement.

#10 lore raw
Quoted 29 lines · Simon Horman
Quoted 10 lines · Felix Maurer

The PRP duplicate discard algorithm does not work reliably with certain link faults. Especially with packet loss on one link, the duplicate discard algorithm drops valid packets. For a more thorough description see patch 5.

My suggestion is to replace the current, drop window-based algorithm with a new one that tracks the received sequence numbers individually (description again in patch 5). I am sending this as an RFC to gather feedback mainly on two points:

Quoted 13 lines

1. Is the design generally acceptable? Of course, this change leads to higher memory usage and more work to do for each packet. But I argue that this is an acceptable trade-off to make for a more robust PRP behavior with faulty links. After all, PRP is to be used in environments where redundancy is needed and people are ready to maintain two duplicate networks to achieve it.
2. As the tests added in patch 6 show, HSR is subject to similar problems. I do not see a reason not to use a very similar algorithm for HSR as well (with a bitmap for each port). Any objections to doing that (in a later patch series)? This will make the trade-off with memory usage more pronounced, as the hsr_seq_block will grow by three more bitmaps, at least for each HSR node (of which we do not expect too many, as an HSR ring can not be infinitely large).

Hi Felix,

Happy New Year!

Quoted 8 lines

We have spoken about this offline before and I agree that the situation should be improved.

IMHO the trade-offs you are making here seem reasonable. And I wonder if it helps to think in terms of the expected usage of this code: Is it expected to scale to a point where the memory and CPU overhead becomes unreasonable; or do, as I think you imply above, we expect deployments to be on systems where the trade-offs are acceptable?

Happy new year to you as well!

As for the expected scale, there are two dimensions: the number of nodes in the network and the data rate with which they send.

The number of nodes in the network affect the memory usage because each node now has the block buffer. For PRP that's 64 blocks * 32 byte = 2kbyte for each node in the node table. A PRP network doesn't have an explicit limit for the number of nodes. However, the whole network is a single layer-2 segment which shouldn't grow too large anyways. Even if one really tries to put 1000 nodes into the PRP network, the memory overhead (2Mbyte) is acceptable in my opinion.

For HSR, the blocks would be larger because we need to track the sequence numbers per port. I expect 64 blocks * 80 byte = 5kbyte per node in the node table. There is no explicit limit for the size of an HSR ring either. But I expect them to be of limited size because the forwarding delays add up throughout the ring. I've seen vendors limiting the ring size to 50 nodes with 100Mbit/s links and 300 with 1Gbit/s links. In both cases I consider the memory overhead acceptable.

The data rates are harder to reason about. In general, the data rates for HSR and PRP are limited because too high packet rates would lead to very fast re-use of the 16bit sequence numbers. The IEC 62439-3:2021 mentions 100Mbit/s links and 1Gbit/s links. I don't expect HSR or PRP networks to scale out to, e.g., 10Gbit/s links with the current specification as this would mean that sequence numbers could repeat as often as every ~4ms. The default constants in the IEC standard, which we also use, are oriented at a 100Mbit/s network.

In my tests with veth pairs, the CPU overhead didn't lead to significantly lower data rates. The main factor limiting the data rate at the moment, I assume, is the per-node spinlock that is taken for each received packet. IMHO, there is a lot more to gain in terms of CPU overhead from making this lock smaller or getting rid of it, than we loose with the more accurate duplicate discard algorithm in this patchset.

The CPU overhead of the algorithm benefits from the fact that in high packet rate scenarios (where it really matters) many packets will have sequence numbers in already initialized blocks. These packets just have
additionally: one xarray lookup, one comparison, and one bit setting. If a block needs to be initialized (once every 128 packets plus their 128 duplicates if all sequence numbers are seen), we will have: one xa_erase, a bunch of memory writes, and one xa_store.

In theory, all packets could end up in the slow path if a node sends every 128th packet to us. If this is sent from a well behaving node, the packet rate wouldn't be an issue anymore, though.

Quoted 13 lines
Quoted 10 lines

Most of the patches in this series are for the selftests. This is mainly to demonstrate the problems with the current duplicate discard algorithms, not so much about gathering feedback. Especially patch 1 and 2 are rather preparatory cleanups that do not have much to do with the actual problems the new algorithm tries to solve.

A few points I know not yet addressed are:
- HSR duplicate discard (see above).
- The KUnit test is not updated for the new algorithm. I will work on that before actual patch submission.

FTR, the KUnit tests no longer compiles. But probably you already knew that.

Quoted 8 lines
Quoted 4 lines

- Merging the sequence number blocks when two entries in the node table are merged because they belong to the same node.

Thank you for your feedback already!

Some slightly more specific feedback:

* These patches are probably for net-next rather than net

They are, that was just a mistake when I sent them.

Quoted 10 lines

* Please run checkpatch.pl --max-line-length=80 --codespell (on each patch)
- And fix the line lengths where it doesn't reduce readability. E.g. don't split strings

* Please also run shellcheck on the selftests
- As much as is reasonable please address the warnings
- In general new .sh files should be shellcheck-clean
- To aid this, use "# shellcheck disable=CASE", for cases that don't match the way selftests are written , e.g. SC2154 and SC2034

Quoted 3 lines

* I was curious to see LANG=C in at least one of the selftests. And I do see limited precedence for that. I'm just mentioning that I was surprised as I'd always thought it was an implied requirement.

Thanks for the feedback, I'll work on it for the next submission. The LANG=C was in another hsr selftest, it can probably be removed. I agree that probably a lot of selftests fail with any other LANG.

Thanks,
Felix