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@xxxxxxxxxx> --- .../testcases/sets/0044interval_overlap_1 | 36 +++++++++++++++++++ 1 file changed, 36 insertions(+) create mode 100755 tests/shell/testcases/sets/0044interval_overlap_1 diff --git a/tests/shell/testcases/sets/0044interval_overlap_1 b/tests/shell/testcases/sets/0044interval_overlap_1 new file mode 100755 index 000000000000..eeea1943ee55 --- /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 -- 2.28.0
