[PATCH AUTOSEL 5.5 27/35] netfilter: nf_tables: Allow set back-ends to report partial overlaps on insertion

[PATCH AUTOSEL 5.5 27/35] netfilter: nf_tables: Allow set back-ends to report partial overlaps on insertion

[Sasha Levin]

From: Pablo Neira Ayuso <pablo@netfilter.org>

[ Upstream commit 8c2d45b2b65ca1f215244be1c600236e83f9815f ]

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>
Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
Signed-off-by: Sasha Levin <sashal@kernel.org>
---
 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 11a2a7b5312ee..a9f6bace16245 100644
--- a/net/netfilter/nf_tables_api.c
+++ b/net/netfilter/nf_tables_api.c
@@ -4957,6 +4957,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 err5;
 	}
-- 
2.20.1

Re: [PATCH AUTOSEL 5.5 27/35] netfilter: nf_tables: Allow set back-ends to report partial overlaps on insertion

[Stefano Brivio]

Hi Sasha,

On Mon,  6 Apr 2020 20:00:49 -0400
Sasha Levin <sashal@kernel.org> wrote:

> From: Pablo Neira Ayuso <pablo@netfilter.org>
> 
> [ Upstream commit 8c2d45b2b65ca1f215244be1c600236e83f9815f ]

This patch, together with 28/35 and 29/35 in this series, and all the
equivalent patches for 5.4 and 4.19, that is:
	[PATCH AUTOSEL 5.5 27/35] netfilter: nf_tables: Allow set back-ends to report partial overlaps on insertion
	[PATCH AUTOSEL 5.5 28/35] netfilter: nft_set_rbtree: Introduce and use nft_rbtree_interval_start()
	[PATCH AUTOSEL 5.5 29/35] netfilter: nft_set_rbtree: Detect partial overlaps on insertion
	[PATCH AUTOSEL 5.4 24/32] netfilter: nf_tables: Allow set back-ends to report partial overlaps on insertion
	[PATCH AUTOSEL 5.4 25/32] netfilter: nft_set_rbtree: Introduce and use nft_rbtree_interval_start()
	[PATCH AUTOSEL 5.4 26/32] netfilter: nft_set_rbtree: Detect partial overlaps on insertion
	[PATCH AUTOSEL 4.19 08/13] netfilter: nf_tables: Allow set back-ends to report partial overlaps on insertion
	[PATCH AUTOSEL 4.19 09/13] netfilter: nft_set_rbtree: Introduce and use nft_rbtree_interval_start()
	[PATCH AUTOSEL 4.19 10/13] netfilter: nft_set_rbtree: Detect partial overlaps on insertion

should only be backported together with nf.git commit
	72239f2795fa ("netfilter: nft_set_rbtree: Drop spurious condition for overlap detection on insertion")

as they would otherwise introduce a regression. In general, those changes
are not really relevant before 5.6, as nft_set_pipapo wasn't there and the
main purpose here is to make the nft_set_rbtree back-end consistent with it:
they also prevent a malfunction in nft_set_rbtree itself, but nothing that
would be triggered using 'nft' alone, and no memory badnesses or critical
issues whatsoever. So it's also safe to drop them, in my opinion.

Also patches for 4.14 and 4.9:
	[PATCH AUTOSEL 4.14 6/9] netfilter: nf_tables: Allow set back-ends to report partial overlaps on insertion
	[PATCH AUTOSEL 4.9 3/5] netfilter: nf_tables: Allow set back-ends to report partial overlaps on insertion

can safely be dropped, because there are no set back-ends there, without
the following patches, that use this way of reporting a partial overlap.

I'm used to not Cc: stable on networking patches (Dave's net.git),
but I guess I should instead if they go through nf.git (Pablo's tree),
right?

-- 
Stefano

Re: [PATCH AUTOSEL 5.5 27/35] netfilter: nf_tables: Allow set back-ends to report partial overlaps on insertion

[Sasha Levin]

On Tue, Apr 07, 2020 at 02:18:48AM +0200, Stefano Brivio wrote:
>Hi Sasha,
>
>On Mon,  6 Apr 2020 20:00:49 -0400
>Sasha Levin <sashal@kernel.org> wrote:
>
>> From: Pablo Neira Ayuso <pablo@netfilter.org>
>>
>> [ Upstream commit 8c2d45b2b65ca1f215244be1c600236e83f9815f ]
>
>This patch, together with 28/35 and 29/35 in this series, and all the
>equivalent patches for 5.4 and 4.19, that is:
>	[PATCH AUTOSEL 5.5 27/35] netfilter: nf_tables: Allow set back-ends to report partial overlaps on insertion
>	[PATCH AUTOSEL 5.5 28/35] netfilter: nft_set_rbtree: Introduce and use nft_rbtree_interval_start()
>	[PATCH AUTOSEL 5.5 29/35] netfilter: nft_set_rbtree: Detect partial overlaps on insertion
>	[PATCH AUTOSEL 5.4 24/32] netfilter: nf_tables: Allow set back-ends to report partial overlaps on insertion
>	[PATCH AUTOSEL 5.4 25/32] netfilter: nft_set_rbtree: Introduce and use nft_rbtree_interval_start()
>	[PATCH AUTOSEL 5.4 26/32] netfilter: nft_set_rbtree: Detect partial overlaps on insertion
>	[PATCH AUTOSEL 4.19 08/13] netfilter: nf_tables: Allow set back-ends to report partial overlaps on insertion
>	[PATCH AUTOSEL 4.19 09/13] netfilter: nft_set_rbtree: Introduce and use nft_rbtree_interval_start()
>	[PATCH AUTOSEL 4.19 10/13] netfilter: nft_set_rbtree: Detect partial overlaps on insertion
>
>should only be backported together with nf.git commit
>	72239f2795fa ("netfilter: nft_set_rbtree: Drop spurious condition for overlap detection on insertion")
>
>as they would otherwise introduce a regression. In general, those changes
>are not really relevant before 5.6, as nft_set_pipapo wasn't there and the
>main purpose here is to make the nft_set_rbtree back-end consistent with it:
>they also prevent a malfunction in nft_set_rbtree itself, but nothing that
>would be triggered using 'nft' alone, and no memory badnesses or critical
>issues whatsoever. So it's also safe to drop them, in my opinion.
>
>Also patches for 4.14 and 4.9:
>	[PATCH AUTOSEL 4.14 6/9] netfilter: nf_tables: Allow set back-ends to report partial overlaps on insertion
>	[PATCH AUTOSEL 4.9 3/5] netfilter: nf_tables: Allow set back-ends to report partial overlaps on insertion
>
>can safely be dropped, because there are no set back-ends there, without
>the following patches, that use this way of reporting a partial overlap.

I've just dropped them all as 72239f2795fa ("netfilter: nft_set_rbtree:
Drop spurious condition for overlap detection on insertion") didn't make
it into Linus's tree yet.

>I'm used to not Cc: stable on networking patches (Dave's net.git),
>but I guess I should instead if they go through nf.git (Pablo's tree),
>right?

Yup, this confusion has caused for quite a few netfilter fixes to not
land in -stable. If it goes through Pablo's tree (and unless he intructs
otherwise), you should Cc stable.

-- 
Thanks,
Sasha

Re: [PATCH AUTOSEL 5.5 27/35] netfilter: nf_tables: Allow set back-ends to report partial overlaps on insertion

[Stefano Brivio]

On Mon, 13 Apr 2020 12:39:00 -0400
Sasha Levin <sashal@kernel.org> wrote:

> On Tue, Apr 07, 2020 at 02:18:48AM +0200, Stefano Brivio wrote:
>
> >I'm used to not Cc: stable on networking patches (Dave's net.git),
> >but I guess I should instead if they go through nf.git (Pablo's tree),
> >right?  
> 
> Yup, this confusion has caused for quite a few netfilter fixes to not
> land in -stable. If it goes through Pablo's tree (and unless he intructs
> otherwise), you should Cc stable.

Hah, thanks for clarifying.

What do you think I should do specifically with 72239f2795fa
("netfilter: nft_set_rbtree: Drop spurious condition for overlap detection
on insertion")?

I haven't Cc'ed stable on that one. Can I expect AUTOSEL to pick it up
anyway?

-- 
Stefano

Re: [PATCH AUTOSEL 5.5 27/35] netfilter: nf_tables: Allow set back-ends to report partial overlaps on insertion

[Sasha Levin]

On Mon, Apr 13, 2020 at 10:38:58PM +0200, Stefano Brivio wrote:
>On Mon, 13 Apr 2020 12:39:00 -0400
>Sasha Levin <sashal@kernel.org> wrote:
>
>> On Tue, Apr 07, 2020 at 02:18:48AM +0200, Stefano Brivio wrote:
>>
>> >I'm used to not Cc: stable on networking patches (Dave's net.git),
>> >but I guess I should instead if they go through nf.git (Pablo's tree),
>> >right?
>>
>> Yup, this confusion has caused for quite a few netfilter fixes to not
>> land in -stable. If it goes through Pablo's tree (and unless he intructs
>> otherwise), you should Cc stable.
>
>Hah, thanks for clarifying.
>
>What do you think I should do specifically with 72239f2795fa
>("netfilter: nft_set_rbtree: Drop spurious condition for overlap detection
>on insertion")?
>
>I haven't Cc'ed stable on that one. Can I expect AUTOSEL to pick it up
>anyway?

I'll make sure it gets queued up when it hits Linus's tree :)

-- 
Thanks,
Sasha

Re: [PATCH AUTOSEL 5.5 27/35] netfilter: nf_tables: Allow set back-ends to report partial overlaps on insertion

[Pablo Neira Ayuso]

Hi Sasha,

On Tue, Apr 14, 2020 at 11:08:40AM -0400, Sasha Levin wrote:
> On Mon, Apr 13, 2020 at 10:38:58PM +0200, Stefano Brivio wrote:
> > On Mon, 13 Apr 2020 12:39:00 -0400
> > Sasha Levin <sashal@kernel.org> wrote:
> > 
> > > On Tue, Apr 07, 2020 at 02:18:48AM +0200, Stefano Brivio wrote:
> > > 
> > > >I'm used to not Cc: stable on networking patches (Dave's net.git),
> > > >but I guess I should instead if they go through nf.git (Pablo's tree),
> > > >right?
> > > 
> > > Yup, this confusion has caused for quite a few netfilter fixes to not
> > > land in -stable. If it goes through Pablo's tree (and unless he intructs
> > > otherwise), you should Cc stable.
> > 
> > Hah, thanks for clarifying.
> > 
> > What do you think I should do specifically with 72239f2795fa
> > ("netfilter: nft_set_rbtree: Drop spurious condition for overlap detection
> > on insertion")?
> > 
> > I haven't Cc'ed stable on that one. Can I expect AUTOSEL to pick it up
> > anyway?
> 
> I'll make sure it gets queued up when it hits Linus's tree :)

5.6.6 is out and this fix is still not included...

Would you please enqueue...

commit 72239f2795fab9a58633bd0399698ff7581534a3
Author: Stefano Brivio <sbrivio@redhat.com>
Date:   Wed Apr 1 17:14:38 2020 +0200

    netfilter: nft_set_rbtree: Drop spurious condition for overlap detection on insertion

for 5.6.x -stable ?

Thank you very much.

Re: [PATCH AUTOSEL 5.5 27/35] netfilter: nf_tables: Allow set back-ends to report partial overlaps on insertion

[Greg KH]

On Tue, Apr 21, 2020 at 01:32:21PM +0200, Pablo Neira Ayuso wrote:
> Hi Sasha,
> 
> On Tue, Apr 14, 2020 at 11:08:40AM -0400, Sasha Levin wrote:
> > On Mon, Apr 13, 2020 at 10:38:58PM +0200, Stefano Brivio wrote:
> > > On Mon, 13 Apr 2020 12:39:00 -0400
> > > Sasha Levin <sashal@kernel.org> wrote:
> > > 
> > > > On Tue, Apr 07, 2020 at 02:18:48AM +0200, Stefano Brivio wrote:
> > > > 
> > > > >I'm used to not Cc: stable on networking patches (Dave's net.git),
> > > > >but I guess I should instead if they go through nf.git (Pablo's tree),
> > > > >right?
> > > > 
> > > > Yup, this confusion has caused for quite a few netfilter fixes to not
> > > > land in -stable. If it goes through Pablo's tree (and unless he intructs
> > > > otherwise), you should Cc stable.
> > > 
> > > Hah, thanks for clarifying.
> > > 
> > > What do you think I should do specifically with 72239f2795fa
> > > ("netfilter: nft_set_rbtree: Drop spurious condition for overlap detection
> > > on insertion")?
> > > 
> > > I haven't Cc'ed stable on that one. Can I expect AUTOSEL to pick it up
> > > anyway?
> > 
> > I'll make sure it gets queued up when it hits Linus's tree :)
> 
> 5.6.6 is out and this fix is still not included...
> 
> Would you please enqueue...
> 
> commit 72239f2795fab9a58633bd0399698ff7581534a3
> Author: Stefano Brivio <sbrivio@redhat.com>
> Date:   Wed Apr 1 17:14:38 2020 +0200
> 
>     netfilter: nft_set_rbtree: Drop spurious condition for overlap detection on insertion
> 
> for 5.6.x -stable ?

Now queued up, thanks.

greg k-h

[PATCH AUTOSEL 5.5 28/35] netfilter: nft_set_rbtree: Introduce and use nft_rbtree_interval_start()

[Sasha Levin]

From: Stefano Brivio <sbrivio@redhat.com>

[ Upstream commit 6f7c9caf017be8ab0fe3b99509580d0793bf0833 ]

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>
Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
Signed-off-by: Sasha Levin <sashal@kernel.org>
---
 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 a9f804f7a04ac..95fcba34bfd35 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.20.1

[PATCH AUTOSEL 5.5 29/35] netfilter: nft_set_rbtree: Detect partial overlaps on insertion

[Sasha Levin]

From: Stefano Brivio <sbrivio@redhat.com>

[ Upstream commit 7c84d41416d836ef7e533bd4d64ccbdf40c5ac70 ]

...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>
Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
Signed-off-by: Sasha Levin <sashal@kernel.org>
---
 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 95fcba34bfd35..996fd9dc6160c 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.20.1