nftables: Consistently report partial and entire set overlaps
Subsystems (2)
v2 cover nftables: Consistently report partial and entire set overlaps
Phil reports that inserting an element, that includes a concatenated range colliding with an existing one, fails silently.
This is because so far set back-ends have no way to tell apart cases of identical elements being inserted from clashing elements. On insertion, the front-end would strip -EEXIST if NLM_F_EXCL is not passed, so we return success to userspace while an error in fact occurred.
As suggested by Pablo, allow back-ends to return -ENOTEMPTY in case of partial overlaps, with patch 1/4. Then, with patches 2/4 to 4/4, update nft_set_pipapo and nft_set_rbtree to report partial overlaps using the new error code.
v2: Only consider active elements for rbtree overlap detection in
patch 4/4 (Pablo Neira Ayuso)
Stefano Brivio (4):
nf_tables: Allow set back-ends to report partial overlaps on insertion
nft_set_pipapo: Separate partial and complete overlap cases on
insertion
nft_set_rbtree: Introduce and use nft_rbtree_interval_start()
nft_set_rbtree: Detect partial overlaps on insertion
net/netfilter/nf_tables_api.c | 5 ++ net/netfilter/nft_set_pipapo.c | 34 ++++++++++--- net/netfilter/nft_set_rbtree.c | 87 ++++++++++++++++++++++++++++++---- 3 files changed, 110 insertions(+), 16 deletions(-)
Signature · 1 line
2.25.1
PATCH v2 1/4 nf_tables: Allow set back-ends to report partial overlaps on insertion
From: Pablo Neira Ayuso <[email protected]>
Currently, the -EEXIST return code of ->insert() callbacks is ambiguous: it might indicate that a given element (including intervals) already exists as such, or that the new element would clash with existing ones.
If identical elements already exist, the front-end is ignoring this without returning error, in case NLM_F_EXCL is not set. However, if the new element can't be inserted due an overlap, we should report this to the user.
To this purpose, allow set back-ends to return -ENOTEMPTY on collision with existing elements, translate that to -EEXIST, and return that to userspace, no matter if NLM_F_EXCL was set.
---
v2: No changes
net/netfilter/nf_tables_api.c | 5 +++++ 1 file changed, 5 insertions(+)
net/netfilter/nf_tables_api.c +5 -0
@@ -5077,6 +5077,11 @@ static int nft_add_set_elem(struct nft_ctx *ctx, struct nft_set *set, err = -EBUSY ; else if (!(nlmsg_flags & NLM_F_EXCL)) err =0 ; + }else if (err == -ENOTEMPTY ) { +/* ENOTEMPTY reports overlapping between this element +* and an existing one. +*/ + err = -EEXIST ; } goto err_element_clash; }
Signature · 1 line
2.25.1
PATCH v2 2/4 nft_set_pipapo: Separate partial and complete overlap cases on insertion
In reply to Stefano Brivio...and return -ENOTEMPTY to the front-end on collision, -EEXIST if an identical element already exists. Together with the previous patch, element collision will now be returned to the user as -EEXIST.
---
v2: No changes
net/netfilter/nft_set_pipapo.c | 34 +++++++++++++++++++++++++++------- 1 file changed, 27 insertions(+), 7 deletions(-)
net/netfilter/nft_set_pipapo.c +27 -7
@@ -1098,21 +1098,41 @@ static int nft_pipapo_insert(const struct net *net, const struct nft_set *set,struct nft_pipapo_field *f;int i, bsize_max, err =0 ; +if (nft_set_ext_exists (ext,NFT_SET_EXT_KEY_END )) + end = (const u8 *)nft_set_ext_key_end (ext)->data; +else + end = start; + dup =pipapo_get (net, set, start, genmask); -if (PTR_ERR (dup) == -ENOENT ) { -if (nft_set_ext_exists (ext,NFT_SET_EXT_KEY_END )) { - end = (const u8 *)nft_set_ext_key_end (ext)->data; - dup =pipapo_get (net, set, end,nft_genmask_next (net)); - }else { - end = start; +if (!IS_ERR (dup)) { +/* Check if we already have the same exact entry */ +const struct nft_data *dup_key, *dup_end; + + dup_key =nft_set_ext_key (&dup->ext); +if (nft_set_ext_exists (&dup->ext,NFT_SET_EXT_KEY_END )) + dup_end =nft_set_ext_key_end (&dup->ext); +else + dup_end = dup_key; + +if (!memcmp (start, dup_key->data,sizeof (*dup_key->data)) && + !memcmp (end, dup_end->data,sizeof (*dup_end->data))) { + *ext2 = &dup->ext; +return -EEXIST ; } + +return -ENOTEMPTY ; + } + +if (PTR_ERR (dup) == -ENOENT ) { +/* Look for partially overlapping entries */ + dup =pipapo_get (net, set, end,nft_genmask_next (net)); }if (PTR_ERR (dup) != -ENOENT ) {if (IS_ERR (dup))return PTR_ERR (dup); *ext2 = &dup->ext; -return -EEXIST ; +return -ENOTEMPTY ; }/* Validate */
Signature · 1 line
2.25.1
PATCH v2 3/4 nft_set_rbtree: Introduce and use nft_rbtree_interval_start()
In reply to Stefano BrivioReplace negations of nft_rbtree_interval_end() with a new helper, nft_rbtree_interval_start(), wherever this helps to visualise the problem at hand, that is, for all the occurrences except for the comparison against given flags in __nft_rbtree_get().
This gets especially useful in the next patch.
---
v2: No changes
net/netfilter/nft_set_rbtree.c | 17 +++++++++++------ 1 file changed, 11 insertions(+), 6 deletions(-)
net/netfilter/nft_set_rbtree.c +11 -6
@@ -33,6 +33,11 @@ static bool nft_rbtree_interval_end(const struct nft_rbtree_elem *rbe) (*nft_set_ext_flags (&rbe->ext) &NFT_SET_ELEM_INTERVAL_END ); } +static bool nft_rbtree_interval_start (const struct nft_rbtree_elem *rbe) +{ +return !nft_rbtree_interval_end (rbe); +} +static bool nft_rbtree_equal (const struct nft_set *set,const void *this,const struct nft_rbtree_elem *interval) {
@@ -64,7 +69,7 @@ static bool __nft_rbtree_lookup(const struct net *net, const struct nft_set *setif (interval &&nft_rbtree_equal (set, this, interval) &&nft_rbtree_interval_end (rbe) && - !nft_rbtree_interval_end (interval)) +nft_rbtree_interval_start (interval))continue ; interval = rbe; }else if (d >0 )
@@ -89,7 +94,7 @@ static bool __nft_rbtree_lookup(const struct net *net, const struct nft_set *setif (set->flags &NFT_SET_INTERVAL && interval !=NULL &&nft_set_elem_active (&interval->ext, genmask) && - !nft_rbtree_interval_end (interval)) { +nft_rbtree_interval_start (interval)) { *ext = &interval->ext;return true; }
@@ -224,9 +229,9 @@ static int __nft_rbtree_insert(const struct net *net, const struct nft_set *set, p = &parent->rb_right; else {if (nft_rbtree_interval_end (rbe) && - !nft_rbtree_interval_end (new)) { +nft_rbtree_interval_start (new)) { p = &parent->rb_left; - }else if (!nft_rbtree_interval_end (rbe) && + }else if (nft_rbtree_interval_start (rbe) &&nft_rbtree_interval_end (new)) { p = &parent->rb_right; }else if (nft_set_elem_active (&rbe->ext, genmask)) {
@@ -317,10 +322,10 @@ static void *nft_rbtree_deactivate(const struct net *net, parent = parent->rb_right; else {if (nft_rbtree_interval_end (rbe) && - !nft_rbtree_interval_end (this)) { +nft_rbtree_interval_start (this)) { parent = parent->rb_left;continue ; - }else if (!nft_rbtree_interval_end (rbe) && + }else if (nft_rbtree_interval_start (rbe) &&nft_rbtree_interval_end (this)) { parent = parent->rb_right;continue ;
Signature · 1 line
2.25.1
PATCH v2 4/4 nft_set_rbtree: Detect partial overlaps on insertion
In reply to Stefano Brivio...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.
v2: When we meet the same key data in the tree, as start element while
inserting an end element, or as end element while inserting a start element, actually check that the existing element is active, before resetting the overlap flag (Pablo Neira Ayuso)
--- net/netfilter/nft_set_rbtree.c | 70 ++++++++++++++++++++++++++++++++-- 1 file changed, 67 insertions(+), 3 deletions(-)
net/netfilter/nft_set_rbtree.c +67 -3
@@ -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,42 @@ 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; + +if (nft_set_elem_active (&rbe->ext, genmask)) + overlap = false; }else if (nft_rbtree_interval_start (rbe) &&nft_rbtree_interval_end (new)) { p = &parent->rb_right; + +if (nft_set_elem_active (&rbe->ext, genmask)) + overlap = false; }else if (nft_set_elem_active (&rbe->ext, genmask)) { *ext = &rbe->ext;return -EEXIST ;
@@ -242,6 +302,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 ;
Signature · 1 line
2.25.1
Pablo Neira Ayuso
maintainerRe: [PATCH nf v2 4/4] nft_set_rbtree: Detect partial overlaps on insertion
Hi Stefano,
Quoted 19 lines · Stefano Brivio
...and return
-ENOTEMPTYto 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 theset_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 {(quoted diff) +0
-0set s { type inet_service flags interval elements = { 1-3, 4-5, 6-7 } } }
Quoted 4 lines
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.
nftables/tests/py is reporting a regression that is related to this patch. If I locally revert this patch here, tests/py works fine here.
Thanks.
Re: [PATCH nf v2 4/4] nft_set_rbtree: Detect partial overlaps on insertion
Quoted 22 lines · On Tue, 31 Mar 2020 22:12:27 +0200 Pablo Neira Ayuso <[email protected]>…
Hi Stefano,
Quoted 19 lines · Stefano Brivio
...and return
-ENOTEMPTYto 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 theset_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 {(quoted diff) +0
-0set s { type inet_service flags interval elements = { 1-3, 4-5, 6-7 } } }
Quoted 7 lines
Quoted 4 lines
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.nftables/tests/py is reporting a regression that is related to this patch. If I locally revert this patch here, tests/py works fine here.
Grrr, did I really run tests/shell only after this... :(
Sorry, I'm on it.
Signature · 1 line
Stefano
Quoted 9 lines · Stefano Brivio
Phil reports that inserting an element, that includes a concatenated range colliding with an existing one, fails silently.
This is because so far set back-ends have no way to tell apart cases of identical elements being inserted from clashing elements. On insertion, the front-end would strip
-EEXISTifNLM_F_EXCLis not passed, so we return success to userspace while an error in fact occurred.
Quoted 4 lines
As suggested by Pablo, allow back-ends to return
-ENOTEMPTYin case of partial overlaps, with patch 1/4. Then, with patches 2/4 to 4/4, updatenft_set_pipapoandnft_set_rbtreeto report partial overlaps using the new error code.
Applied, thanks.