[PATCH nf 0/4] nftables: Consistently report partial and entire set overlaps

[PATCH nf 0/4] nftables: Consistently report partial and entire set overlaps

[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 -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

[PATCH nf 1/4] nf_tables: Allow set back-ends to report partial overlaps on insertion

[Stefano Brivio]

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

[PATCH nf 2/4] nft_set_pipapo: Separate partial and complete overlap cases on insertion

[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.

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

[PATCH nf 3/4] nft_set_rbtree: Introduce and use nft_rbtree_interval_start()

[Stefano Brivio]

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

[PATCH nf 4/4] nft_set_rbtree: Detect partial overlaps on insertion

[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.

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

Re: [PATCH nf 4/4] nft_set_rbtree: Detect partial overlaps on insertion

[Pablo Neira Ayuso]

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.

Re: [PATCH nf 4/4] nft_set_rbtree: Detect partial overlaps on insertion

[Stefano Brivio]

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