* [PATCH nf v2 0/4] nftables: Consistently report partial and entire set overlaps
@ 2020-03-22 2:21 Stefano Brivio
2020-03-22 2:21 ` [PATCH nf v2 1/4] nf_tables: Allow set back-ends to report partial overlaps on insertion Stefano Brivio
` (4 more replies)
0 siblings, 5 replies; 8+ messages in thread
From: Stefano Brivio @ 2020-03-22 2:21 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.
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(-)
--
2.25.1
^ permalink raw reply [flat|nested] 8+ messages in thread
* [PATCH nf v2 1/4] nf_tables: Allow set back-ends to report partial overlaps on insertion
2020-03-22 2:21 [PATCH nf v2 0/4] nftables: Consistently report partial and entire set overlaps Stefano Brivio
@ 2020-03-22 2:21 ` Stefano Brivio
2020-03-22 2:21 ` [PATCH nf v2 2/4] nft_set_pipapo: Separate partial and complete overlap cases " Stefano Brivio
` (3 subsequent siblings)
4 siblings, 0 replies; 8+ messages in thread
From: Stefano Brivio @ 2020-03-22 2:21 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>
---
v2: No changes
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] 8+ messages in thread
* [PATCH nf v2 2/4] nft_set_pipapo: Separate partial and complete overlap cases on insertion
2020-03-22 2:21 [PATCH nf v2 0/4] nftables: Consistently report partial and entire set overlaps Stefano Brivio
2020-03-22 2:21 ` [PATCH nf v2 1/4] nf_tables: Allow set back-ends to report partial overlaps on insertion Stefano Brivio
@ 2020-03-22 2:21 ` Stefano Brivio
2020-03-22 2:22 ` [PATCH nf v2 3/4] nft_set_rbtree: Introduce and use nft_rbtree_interval_start() Stefano Brivio
` (2 subsequent siblings)
4 siblings, 0 replies; 8+ messages in thread
From: Stefano Brivio @ 2020-03-22 2:21 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>
---
v2: No changes
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] 8+ messages in thread
* [PATCH nf v2 3/4] nft_set_rbtree: Introduce and use nft_rbtree_interval_start()
2020-03-22 2:21 [PATCH nf v2 0/4] nftables: Consistently report partial and entire set overlaps Stefano Brivio
2020-03-22 2:21 ` [PATCH nf v2 1/4] nf_tables: Allow set back-ends to report partial overlaps on insertion Stefano Brivio
2020-03-22 2:21 ` [PATCH nf v2 2/4] nft_set_pipapo: Separate partial and complete overlap cases " Stefano Brivio
@ 2020-03-22 2:22 ` Stefano Brivio
2020-03-22 2:22 ` [PATCH nf v2 4/4] nft_set_rbtree: Detect partial overlaps on insertion Stefano Brivio
2020-03-24 19:01 ` [PATCH nf v2 0/4] nftables: Consistently report partial and entire set overlaps Pablo Neira Ayuso
4 siblings, 0 replies; 8+ messages in thread
From: Stefano Brivio @ 2020-03-22 2:22 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 gets especially useful in the next patch.
Signed-off-by: Stefano Brivio <sbrivio@redhat.com>
---
v2: No changes
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] 8+ messages in thread
* [PATCH nf v2 4/4] nft_set_rbtree: Detect partial overlaps on insertion
2020-03-22 2:21 [PATCH nf v2 0/4] nftables: Consistently report partial and entire set overlaps Stefano Brivio
` (2 preceding siblings ...)
2020-03-22 2:22 ` [PATCH nf v2 3/4] nft_set_rbtree: Introduce and use nft_rbtree_interval_start() Stefano Brivio
@ 2020-03-22 2:22 ` Stefano Brivio
2020-03-31 20:12 ` Pablo Neira Ayuso
2020-03-24 19:01 ` [PATCH nf v2 0/4] nftables: Consistently report partial and entire set overlaps Pablo Neira Ayuso
4 siblings, 1 reply; 8+ messages in thread
From: Stefano Brivio @ 2020-03-22 2:22 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.
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)
Signed-off-by: Stefano Brivio <sbrivio@redhat.com>
---
net/netfilter/nft_set_rbtree.c | 70 ++++++++++++++++++++++++++++++++--
1 file changed, 67 insertions(+), 3 deletions(-)
diff --git a/net/netfilter/nft_set_rbtree.c b/net/netfilter/nft_set_rbtree.c
index 85572b2a6051..8617fc16a1ed 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,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;
--
2.25.1
^ permalink raw reply related [flat|nested] 8+ messages in thread
* Re: [PATCH nf v2 0/4] nftables: Consistently report partial and entire set overlaps
2020-03-22 2:21 [PATCH nf v2 0/4] nftables: Consistently report partial and entire set overlaps Stefano Brivio
` (3 preceding siblings ...)
2020-03-22 2:22 ` [PATCH nf v2 4/4] nft_set_rbtree: Detect partial overlaps on insertion Stefano Brivio
@ 2020-03-24 19:01 ` Pablo Neira Ayuso
4 siblings, 0 replies; 8+ messages in thread
From: Pablo Neira Ayuso @ 2020-03-24 19:01 UTC (permalink / raw)
To: Stefano Brivio; +Cc: Phil Sutter, netfilter-devel
On Sun, Mar 22, 2020 at 03:21:57AM +0100, Stefano Brivio wrote:
> 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.
Applied, thanks.
^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [PATCH nf v2 4/4] nft_set_rbtree: Detect partial overlaps on insertion
2020-03-22 2:22 ` [PATCH nf v2 4/4] nft_set_rbtree: Detect partial overlaps on insertion Stefano Brivio
@ 2020-03-31 20:12 ` Pablo Neira Ayuso
2020-03-31 20:33 ` Stefano Brivio
0 siblings, 1 reply; 8+ messages in thread
From: Pablo Neira Ayuso @ 2020-03-31 20:12 UTC (permalink / raw)
To: Stefano Brivio; +Cc: Phil Sutter, netfilter-devel
Hi Stefano,
On Sun, Mar 22, 2020 at 03:22:01AM +0100, Stefano Brivio wrote:
> ...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.
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.
^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [PATCH nf v2 4/4] nft_set_rbtree: Detect partial overlaps on insertion
2020-03-31 20:12 ` Pablo Neira Ayuso
@ 2020-03-31 20:33 ` Stefano Brivio
0 siblings, 0 replies; 8+ messages in thread
From: Stefano Brivio @ 2020-03-31 20:33 UTC (permalink / raw)
To: Pablo Neira Ayuso; +Cc: Phil Sutter, netfilter-devel
On Tue, 31 Mar 2020 22:12:27 +0200
Pablo Neira Ayuso <pablo@netfilter.org> wrote:
> Hi Stefano,
>
> On Sun, Mar 22, 2020 at 03:22:01AM +0100, Stefano Brivio wrote:
> > ...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.
>
> 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.
--
Stefano
^ permalink raw reply [flat|nested] 8+ messages in thread
end of thread, other threads:[~2020-03-31 20:33 UTC | newest]
Thread overview: 8+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2020-03-22 2:21 [PATCH nf v2 0/4] nftables: Consistently report partial and entire set overlaps Stefano Brivio
2020-03-22 2:21 ` [PATCH nf v2 1/4] nf_tables: Allow set back-ends to report partial overlaps on insertion Stefano Brivio
2020-03-22 2:21 ` [PATCH nf v2 2/4] nft_set_pipapo: Separate partial and complete overlap cases " Stefano Brivio
2020-03-22 2:22 ` [PATCH nf v2 3/4] nft_set_rbtree: Introduce and use nft_rbtree_interval_start() Stefano Brivio
2020-03-22 2:22 ` [PATCH nf v2 4/4] nft_set_rbtree: Detect partial overlaps on insertion Stefano Brivio
2020-03-31 20:12 ` Pablo Neira Ayuso
2020-03-31 20:33 ` Stefano Brivio
2020-03-24 19:01 ` [PATCH nf v2 0/4] nftables: Consistently report partial and entire set overlaps Pablo Neira Ayuso
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).