| Message ID | e6f84fe980f55dde272f7c17e2423390a03e942d.1583438771.git.sbrivio@redhat.com |
|---|---|
| State | Changes Requested |
| Delegated to: | Pablo Neira |
| Headers | show |
| Series | nftables: Consistently report partial and entire set overlaps | expand |
Hi Stefano, Sorry for the late response to this one. On Thu, Mar 05, 2020 at 09:33:05PM +0100, Stefano Brivio wrote: > @@ -223,17 +258,40 @@ static int __nft_rbtree_insert(const struct net *net, const struct nft_set *set, > d = memcmp(nft_set_ext_key(&rbe->ext), > nft_set_ext_key(&new->ext), > set->klen); > - if (d < 0) > + if (d < 0) { > p = &parent->rb_left; > - else if (d > 0) > + > + if (nft_rbtree_interval_start(new)) { > + overlap = nft_rbtree_interval_start(rbe) && > + nft_set_elem_active(&rbe->ext, > + genmask); > + } else { > + overlap = nft_rbtree_interval_end(rbe) && > + nft_set_elem_active(&rbe->ext, > + genmask); > + } > + } else if (d > 0) { > p = &parent->rb_right; > - else { > + > + if (nft_rbtree_interval_end(new)) { > + overlap = nft_rbtree_interval_end(rbe) && > + nft_set_elem_active(&rbe->ext, > + genmask); > + } else if (nft_rbtree_interval_end(rbe) && > + nft_set_elem_active(&rbe->ext, genmask)) { > + overlap = true; > + } > + } else { > if (nft_rbtree_interval_end(rbe) && > nft_rbtree_interval_start(new)) { > p = &parent->rb_left; > + Instead of this inconditional reset of 'overlap': > + overlap = false; I think this should be: if (nft_set_elem_active(&rbe->ext, genmask)) overlap = false; if the existing rbe is active, then reset 'overlap' to false.
On Thu, 19 Mar 2020 20:32:11 +0100 Pablo Neira Ayuso <pablo@netfilter.org> wrote: > Hi Stefano, > > Sorry for the late response to this one. > > On Thu, Mar 05, 2020 at 09:33:05PM +0100, Stefano Brivio wrote: > > @@ -223,17 +258,40 @@ static int __nft_rbtree_insert(const struct net *net, const struct nft_set *set, > > d = memcmp(nft_set_ext_key(&rbe->ext), > > nft_set_ext_key(&new->ext), > > set->klen); > > - if (d < 0) > > + if (d < 0) { > > p = &parent->rb_left; > > - else if (d > 0) > > + > > + if (nft_rbtree_interval_start(new)) { > > + overlap = nft_rbtree_interval_start(rbe) && > > + nft_set_elem_active(&rbe->ext, > > + genmask); > > + } else { > > + overlap = nft_rbtree_interval_end(rbe) && > > + nft_set_elem_active(&rbe->ext, > > + genmask); > > + } > > + } else if (d > 0) { > > p = &parent->rb_right; > > - else { > > + > > + if (nft_rbtree_interval_end(new)) { > > + overlap = nft_rbtree_interval_end(rbe) && > > + nft_set_elem_active(&rbe->ext, > > + genmask); > > + } else if (nft_rbtree_interval_end(rbe) && > > + nft_set_elem_active(&rbe->ext, genmask)) { > > + overlap = true; > > + } > > + } else { > > if (nft_rbtree_interval_end(rbe) && > > nft_rbtree_interval_start(new)) { > > p = &parent->rb_left; > > + > > Instead of this inconditional reset of 'overlap': > > > + overlap = false; > > I think this should be: > > if (nft_set_elem_active(&rbe->ext, genmask)) > overlap = false; > > if the existing rbe is active, then reset 'overlap' to false. I think you're right (also for the case just below this), and, if you're not, then a comment on why I'm not checking it is clearly needed, because I have a vague memory about the fact we could *perhaps* skip it in this particular case, and I can't remember that myself :) I'll fix either problem in v2.
diff --git a/net/netfilter/nft_set_rbtree.c b/net/netfilter/nft_set_rbtree.c index 85572b2a6051..c97c493cd867 100644 --- a/net/netfilter/nft_set_rbtree.c +++ b/net/netfilter/nft_set_rbtree.c @@ -213,8 +213,43 @@ static int __nft_rbtree_insert(const struct net *net, const struct nft_set *set, u8 genmask = nft_genmask_next(net); struct nft_rbtree_elem *rbe; struct rb_node *parent, **p; + bool overlap = false; int d; + /* 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) + * + * 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) + * + * Case a4. resolves to b1.: + * - 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., + * in that order. + * + * The flag is also cleared in two special cases: + * + * b4. |__ _ _!|<_ _ _ (insert start right before existing end) + * b5. |__ _ >|!__ _ _ (insert end right after existing start) + * + * which always happen as last step and imply that no further + * overlapping is possible. + */ + parent = NULL; p = &priv->root.rb_node; while (*p != NULL) { @@ -223,17 +258,40 @@ static int __nft_rbtree_insert(const struct net *net, const struct nft_set *set, d = memcmp(nft_set_ext_key(&rbe->ext), nft_set_ext_key(&new->ext), set->klen); - if (d < 0) + if (d < 0) { p = &parent->rb_left; - else if (d > 0) + + if (nft_rbtree_interval_start(new)) { + overlap = nft_rbtree_interval_start(rbe) && + nft_set_elem_active(&rbe->ext, + genmask); + } else { + overlap = nft_rbtree_interval_end(rbe) && + nft_set_elem_active(&rbe->ext, + genmask); + } + } else if (d > 0) { p = &parent->rb_right; - else { + + if (nft_rbtree_interval_end(new)) { + overlap = nft_rbtree_interval_end(rbe) && + nft_set_elem_active(&rbe->ext, + genmask); + } else if (nft_rbtree_interval_end(rbe) && + nft_set_elem_active(&rbe->ext, genmask)) { + overlap = true; + } + } else { if (nft_rbtree_interval_end(rbe) && nft_rbtree_interval_start(new)) { p = &parent->rb_left; + + overlap = false; } else if (nft_rbtree_interval_start(rbe) && nft_rbtree_interval_end(new)) { p = &parent->rb_right; + + overlap = false; } else if (nft_set_elem_active(&rbe->ext, genmask)) { *ext = &rbe->ext; return -EEXIST; @@ -242,6 +300,10 @@ static int __nft_rbtree_insert(const struct net *net, const struct nft_set *set, } } } + + if (overlap) + return -ENOTEMPTY; + rb_link_node_rcu(&new->node, parent, p); rb_insert_color(&new->node, &priv->root); return 0;
...and return -ENOTEMPTY to the front-end in this case, instead of proceeding. Currently, nft takes care of checking for these cases and not sending them to the kernel, but if we drop the set_overlap() call in nft we can end up in situations like: # nft add table t # nft add set t s '{ type inet_service ; flags interval ; }' # nft add element t s '{ 1 - 5 }' # nft add element t s '{ 6 - 10 }' # nft add element t s '{ 4 - 7 }' # nft list set t s table ip t { set s { type inet_service flags interval elements = { 1-3, 4-5, 6-7 } } } This change has the primary purpose of making the behaviour consistent with nft_set_pipapo, but is also functional to avoid inconsistent behaviour if userspace sends overlapping elements for any reason. Signed-off-by: Stefano Brivio <sbrivio@redhat.com> --- net/netfilter/nft_set_rbtree.c | 68 ++++++++++++++++++++++++++++++++-- 1 file changed, 65 insertions(+), 3 deletions(-)