tests: sets: Check rbtree overlap detection after tree rotations

Ticket https://bugzilla.netfilter.org/show_bug.cgi?id=1449 showed
an issue with rbtree overlap detection coming from the fact that,
after tree rotations performed as part of tree rebalancing, caused
by deletions, end elements are not necessarily descendants of their
corresponding start elements.

Add single-sized elements, delete every second one of them, and
re-add them (they will always be full overlaps) in order to check
overlap detection after tree rotations.

Port indices used in the sets are pseudo-random numbers generated
with Marsaglia's Xorshift algorithm with triplet (5, 3, 1), chosen
for k-distribution over 16-bit periods, which gives a good
statistical randomness and forces 201 rebalancing operations out of
250 deletions with the chosen seed (1).

Signed-off-by: Stefano Brivio <sbrivio@redhat.com>
Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>

1 files changed, 36 insertions, 0 deletions

diff --git a/tests/shell/testcases/sets/0044interval_overlap_1 b/tests/shell/testcases/sets/0044interval_overlap_1
new file mode 100755
index 00000000..eeea1943
--- /dev/null
+++ b/tests/shell/testcases/sets/0044interval_overlap_1
@@ -0,0 +1,36 @@
+#!/bin/sh -e
+#
+# 0044interval_overlap_1 - Single-sized intervals can never overlap partially
+#
+# Check that inserting, deleting, and inserting single-sized intervals again
+# never leads to a partial overlap. Specifically trigger rbtree rebalancing in
+# the process, to ensure different tree shapes of equivalent sets don't lead to
+# false positives, by deleting every second inserted item.
+
+xorshift() {
+	# Adaptation of Xorshift algorithm from:
+	#   Marsaglia, G. (2003). Xorshift RNGs.
+	#   Journal of Statistical Software, 8(14), 1 - 6.
+	#   doi:http://dx.doi.org/10.18637/jss.v008.i14
+	# with triplet (5, 3, 1), suitable for 16-bit ranges.
+
+	: $((port ^= port << 5))
+	: $((port ^= port >> 3))
+	: $((port ^= port << 1))
+}
+
+$NFT add table t
+$NFT add set t s '{ type inet_service ; flags interval ; }'
+
+for op in add delete add; do
+	port=1
+	skip=0
+	for i in $(seq 1 500); do
+		xorshift
+		if [ "${op}" = "delete" ]; then
+			[ ${skip} -eq 0 ] && skip=1 && continue
+			skip=0
+		fi
+		$NFT ${op} element t s "{ { $((port % 32768 + 32768)) } }"
+	done
+done