From 999195d24ed8e5f6aa10b6c3f79e9b058f1c359a Mon Sep 17 00:00:00 2001 From: Greg Kroah-Hartman Date: Tue, 21 Apr 2020 15:15:17 +0200 Subject: [PATCH] 5.6-stable patches added patches: netfilter-nft_set_rbtree-drop-spurious-condition-for-overlap-detection-on-insertion.patch --- ...n-for-overlap-detection-on-insertion.patch | 93 +++++++++++++++++++ queue-5.6/series | 1 + 2 files changed, 94 insertions(+) create mode 100644 queue-5.6/netfilter-nft_set_rbtree-drop-spurious-condition-for-overlap-detection-on-insertion.patch create mode 100644 queue-5.6/series diff --git a/queue-5.6/netfilter-nft_set_rbtree-drop-spurious-condition-for-overlap-detection-on-insertion.patch b/queue-5.6/netfilter-nft_set_rbtree-drop-spurious-condition-for-overlap-detection-on-insertion.patch new file mode 100644 index 00000000000..fc72a69b91a --- /dev/null +++ b/queue-5.6/netfilter-nft_set_rbtree-drop-spurious-condition-for-overlap-detection-on-insertion.patch @@ -0,0 +1,93 @@ +From 72239f2795fab9a58633bd0399698ff7581534a3 Mon Sep 17 00:00:00 2001 +From: Stefano Brivio +Date: Wed, 1 Apr 2020 17:14:38 +0200 +Subject: netfilter: nft_set_rbtree: Drop spurious condition for overlap detection on insertion + +From: Stefano Brivio + +commit 72239f2795fab9a58633bd0399698ff7581534a3 upstream. + +Case a1. for overlap detection in __nft_rbtree_insert() is not a valid +one: start-after-start is not needed to detect any type of interval +overlap and it actually results in a false positive if, while +descending the tree, this is the only step we hit after starting from +the root. + +This introduced a regression, as reported by Pablo, in Python tests +cases ip/ip.t and ip/numgen.t: + + ip/ip.t: ERROR: line 124: add rule ip test-ip4 input ip hdrlength vmap { 0-4 : drop, 5 : accept, 6 : continue } counter: This rule should not have failed. + ip/numgen.t: ERROR: line 7: add rule ip test-ip4 pre dnat to numgen inc mod 10 map { 0-5 : 192.168.10.100, 6-9 : 192.168.20.200}: This rule should not have failed. + +Drop case a1. and renumber others, so that they are a bit clearer. In +order for these diagrams to be readily understandable, a bigger rework +is probably needed, such as an ASCII art of the actual rbtree (instead +of a flattened version). + +Shell script test sets/0044interval_overlap_0 should cover all +possible cases for false negatives, so I consider that test case still +sufficient after this change. + +v2: Fix comments for cases a3. and b3. + +Reported-by: Pablo Neira Ayuso +Fixes: 7c84d41416d8 ("netfilter: nft_set_rbtree: Detect partial overlaps on insertion") +Signed-off-by: Stefano Brivio +Signed-off-by: Pablo Neira Ayuso +Signed-off-by: Greg Kroah-Hartman + +--- + net/netfilter/nft_set_rbtree.c | 23 +++++++++++------------ + 1 file changed, 11 insertions(+), 12 deletions(-) + +--- a/net/netfilter/nft_set_rbtree.c ++++ b/net/netfilter/nft_set_rbtree.c +@@ -218,27 +218,26 @@ static int __nft_rbtree_insert(const str + + /* Detect overlaps as we descend the tree. Set the flag in these cases: + * +- * a1. |__ _ _? >|__ _ _ (insert start after existing start) +- * a2. _ _ __>| ?_ _ __| (insert end before existing end) +- * a3. _ _ ___| ?_ _ _>| (insert end after existing end) +- * a4. >|__ _ _ _ _ __| (insert start before existing end) ++ * a1. _ _ __>| ?_ _ __| (insert end before existing end) ++ * a2. _ _ ___| ?_ _ _>| (insert end after existing end) ++ * a3. _ _ ___? >|_ _ __| (insert start before existing end) + * + * and clear it later on, as we eventually reach the points indicated by + * '?' above, in the cases described below. We'll always meet these + * later, locally, due to tree ordering, and overlaps for the intervals + * that are the closest together are always evaluated last. + * +- * b1. |__ _ _! >|__ _ _ (insert start after existing end) +- * b2. _ _ __>| !_ _ __| (insert end before existing start) +- * b3. !_____>| (insert end after existing start) ++ * b1. _ _ __>| !_ _ __| (insert end before existing start) ++ * b2. _ _ ___| !_ _ _>| (insert end after existing start) ++ * b3. _ _ ___! >|_ _ __| (insert start after existing end) + * +- * Case a4. resolves to b1.: ++ * Case a3. resolves to b3.: + * - if the inserted start element is the leftmost, because the '0' + * element in the tree serves as end element + * - otherwise, if an existing end is found. Note that end elements are + * always inserted after corresponding start elements. + * +- * For a new, rightmost pair of elements, we'll hit cases b1. and b3., ++ * For a new, rightmost pair of elements, we'll hit cases b3. and b2., + * in that order. + * + * The flag is also cleared in two special cases: +@@ -262,9 +261,9 @@ static int __nft_rbtree_insert(const str + p = &parent->rb_left; + + if (nft_rbtree_interval_start(new)) { +- overlap = nft_rbtree_interval_start(rbe) && +- nft_set_elem_active(&rbe->ext, +- genmask); ++ if (nft_rbtree_interval_end(rbe) && ++ nft_set_elem_active(&rbe->ext, genmask)) ++ overlap = false; + } else { + overlap = nft_rbtree_interval_end(rbe) && + nft_set_elem_active(&rbe->ext, diff --git a/queue-5.6/series b/queue-5.6/series new file mode 100644 index 00000000000..6d772c887fd --- /dev/null +++ b/queue-5.6/series @@ -0,0 +1 @@ +netfilter-nft_set_rbtree-drop-spurious-condition-for-overlap-detection-on-insertion.patch -- 2.47.3