]> git.ipfire.org Git - thirdparty/nftables.git/commit
tests: sets: Check rbtree overlap detection after tree rotations
authorStefano Brivio <sbrivio@redhat.com>
Wed, 19 Aug 2020 22:00:18 +0000 (00:00 +0200)
committerPablo Neira Ayuso <pablo@netfilter.org>
Wed, 26 Aug 2020 16:52:28 +0000 (18:52 +0200)
commitcf456cdf82b9ee64c53a23cc64cf231d58bce452
treeee90b0e705037c8134c6cc9de935e8934b829971
parentca2e6e0db0b970e56a3c48c73e39c0367f464410
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>
tests/shell/testcases/sets/0044interval_overlap_1 [new file with mode: 0755]