* [PATCH nf 0/4] nftables: Consistently report partial and entire set overlaps
@ 2020-03-05 20:33 Stefano Brivio
2020-03-05 20:33 ` [PATCH nf 1/4] nf_tables: Allow set back-ends to report partial overlaps on insertion Stefano Brivio
` (3 more replies)
0 siblings, 4 replies; 7+ messages in thread
From: Stefano Brivio @ 2020-03-05 20:33 UTC (permalink / raw)
To: Pablo Neira Ayuso; +Cc: Phil Sutter, netfilter-devel
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.
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 | 85 ++++++++++++++++++++++++++++++----
3 files changed, 108 insertions(+), 16 deletions(-)
--
2.25.1
^ permalink raw reply [flat|nested] 7+ messages in thread
* [PATCH nf 1/4] nf_tables: Allow set back-ends to report partial overlaps on insertion
2020-03-05 20:33 [PATCH nf 0/4] nftables: Consistently report partial and entire set overlaps Stefano Brivio
@ 2020-03-05 20:33 ` Stefano Brivio
2020-03-05 20:33 ` [PATCH nf 2/4] nft_set_pipapo: Separate partial and complete overlap cases " Stefano Brivio
` (2 subsequent siblings)
3 siblings, 0 replies; 7+ messages in thread
From: Stefano Brivio @ 2020-03-05 20:33 UTC (permalink / raw)
To: Pablo Neira Ayuso; +Cc: Phil Sutter, netfilter-devel
From: Pablo Neira Ayuso <pablo@netfilter.org>
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.
Reported-by: Phil Sutter <phil@nwl.cc>
Signed-off-by: Stefano Brivio <sbrivio@redhat.com>
---
Pablo, I added your From: here as the original patch came from you,
but I'm not sure how to handle this. Please change it as you see fit.
net/netfilter/nf_tables_api.c | 5 +++++
1 file changed, 5 insertions(+)
diff --git a/net/netfilter/nf_tables_api.c b/net/netfilter/nf_tables_api.c
index d1318bdf49ca..51371efe8bf0 100644
--- a/net/netfilter/nf_tables_api.c
+++ b/net/netfilter/nf_tables_api.c
@@ -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;
}
--
2.25.1
^ permalink raw reply related [flat|nested] 7+ messages in thread
* [PATCH nf 2/4] nft_set_pipapo: Separate partial and complete overlap cases on insertion
2020-03-05 20:33 [PATCH nf 0/4] nftables: Consistently report partial and entire set overlaps Stefano Brivio
2020-03-05 20:33 ` [PATCH nf 1/4] nf_tables: Allow set back-ends to report partial overlaps on insertion Stefano Brivio
@ 2020-03-05 20:33 ` Stefano Brivio
2020-03-05 20:33 ` [PATCH nf 3/4] nft_set_rbtree: Introduce and use nft_rbtree_interval_start() Stefano Brivio
2020-03-05 20:33 ` [PATCH nf 4/4] nft_set_rbtree: Detect partial overlaps on insertion Stefano Brivio
3 siblings, 0 replies; 7+ messages in thread
From: Stefano Brivio @ 2020-03-05 20:33 UTC (permalink / raw)
To: Pablo Neira Ayuso; +Cc: Phil Sutter, netfilter-devel
...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.
Reported-by: Phil Sutter <phil@nwl.cc>
Signed-off-by: Stefano Brivio <sbrivio@redhat.com>
---
net/netfilter/nft_set_pipapo.c | 34 +++++++++++++++++++++++++++-------
1 file changed, 27 insertions(+), 7 deletions(-)
diff --git a/net/netfilter/nft_set_pipapo.c b/net/netfilter/nft_set_pipapo.c
index 4fc0c924ed5d..ef7e8ad2e344 100644
--- a/net/netfilter/nft_set_pipapo.c
+++ b/net/netfilter/nft_set_pipapo.c
@@ -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 */
--
2.25.1
^ permalink raw reply related [flat|nested] 7+ messages in thread
* [PATCH nf 3/4] nft_set_rbtree: Introduce and use nft_rbtree_interval_start()
2020-03-05 20:33 [PATCH nf 0/4] nftables: Consistently report partial and entire set overlaps Stefano Brivio
2020-03-05 20:33 ` [PATCH nf 1/4] nf_tables: Allow set back-ends to report partial overlaps on insertion Stefano Brivio
2020-03-05 20:33 ` [PATCH nf 2/4] nft_set_pipapo: Separate partial and complete overlap cases " Stefano Brivio
@ 2020-03-05 20:33 ` Stefano Brivio
2020-03-05 20:33 ` [PATCH nf 4/4] nft_set_rbtree: Detect partial overlaps on insertion Stefano Brivio
3 siblings, 0 replies; 7+ messages in thread
From: Stefano Brivio @ 2020-03-05 20:33 UTC (permalink / raw)
To: Pablo Neira Ayuso; +Cc: Phil Sutter, netfilter-devel
Replace 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 becomes especially useful in the next patch.
Signed-off-by: Stefano Brivio <sbrivio@redhat.com>
---
net/netfilter/nft_set_rbtree.c | 17 +++++++++++------
1 file changed, 11 insertions(+), 6 deletions(-)
diff --git a/net/netfilter/nft_set_rbtree.c b/net/netfilter/nft_set_rbtree.c
index 5000b938ab1e..85572b2a6051 100644
--- a/net/netfilter/nft_set_rbtree.c
+++ b/net/netfilter/nft_set_rbtree.c
@@ -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 *set
if (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 *set
if (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;
--
2.25.1
^ permalink raw reply related [flat|nested] 7+ messages in thread
* [PATCH nf 4/4] nft_set_rbtree: Detect partial overlaps on insertion
2020-03-05 20:33 [PATCH nf 0/4] nftables: Consistently report partial and entire set overlaps Stefano Brivio
` (2 preceding siblings ...)
2020-03-05 20:33 ` [PATCH nf 3/4] nft_set_rbtree: Introduce and use nft_rbtree_interval_start() Stefano Brivio
@ 2020-03-05 20:33 ` Stefano Brivio
2020-03-19 19:32 ` Pablo Neira Ayuso
3 siblings, 1 reply; 7+ messages in thread
From: Stefano Brivio @ 2020-03-05 20:33 UTC (permalink / raw)
To: Pablo Neira Ayuso; +Cc: Phil Sutter, netfilter-devel
...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(-)
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;
--
2.25.1
^ permalink raw reply related [flat|nested] 7+ messages in thread
* Re: [PATCH nf 4/4] nft_set_rbtree: Detect partial overlaps on insertion
2020-03-05 20:33 ` [PATCH nf 4/4] nft_set_rbtree: Detect partial overlaps on insertion Stefano Brivio
@ 2020-03-19 19:32 ` Pablo Neira Ayuso
2020-03-19 20:49 ` Stefano Brivio
0 siblings, 1 reply; 7+ messages in thread
From: Pablo Neira Ayuso @ 2020-03-19 19:32 UTC (permalink / raw)
To: Stefano Brivio; +Cc: Phil Sutter, netfilter-devel
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.
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [PATCH nf 4/4] nft_set_rbtree: Detect partial overlaps on insertion
2020-03-19 19:32 ` Pablo Neira Ayuso
@ 2020-03-19 20:49 ` Stefano Brivio
0 siblings, 0 replies; 7+ messages in thread
From: Stefano Brivio @ 2020-03-19 20:49 UTC (permalink / raw)
To: Pablo Neira Ayuso; +Cc: Phil Sutter, netfilter-devel
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.
--
Stefano
^ permalink raw reply [flat|nested] 7+ messages in thread
end of thread, other threads:[~2020-03-19 20:49 UTC | newest]
Thread overview: 7+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2020-03-05 20:33 [PATCH nf 0/4] nftables: Consistently report partial and entire set overlaps Stefano Brivio
2020-03-05 20:33 ` [PATCH nf 1/4] nf_tables: Allow set back-ends to report partial overlaps on insertion Stefano Brivio
2020-03-05 20:33 ` [PATCH nf 2/4] nft_set_pipapo: Separate partial and complete overlap cases " Stefano Brivio
2020-03-05 20:33 ` [PATCH nf 3/4] nft_set_rbtree: Introduce and use nft_rbtree_interval_start() Stefano Brivio
2020-03-05 20:33 ` [PATCH nf 4/4] nft_set_rbtree: Detect partial overlaps on insertion Stefano Brivio
2020-03-19 19:32 ` Pablo Neira Ayuso
2020-03-19 20:49 ` Stefano Brivio
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).