Re: [PATCH nf 0/2] nft_set_pipapo: Fix crash due to dangling entries in mapping table

[Stefano Brivio <sbrivio@redhat.com>]

[-- Attachment #1: Type: text/plain, Size: 3748 bytes --]

On Tue, 25 Feb 2020 21:58:47 +0100
Pablo Neira Ayuso <pablo@netfilter.org> wrote:

> On Tue, Feb 25, 2020 at 09:38:15PM +0100, Stefano Brivio wrote:
> > On Tue, 25 Feb 2020 21:21:43 +0100
> > Pablo Neira Ayuso <pablo@netfilter.org> wrote:
> >   
> > > Hi Stefano,
> > > 
> > > On Tue, Feb 25, 2020 at 03:34:35PM +0100, Stefano Brivio wrote:
> > > [...]  
> > > > This is the problem Phil reported:    
> > > [...]  
> > > > Or also simply with:
> > > > 
> > > > # nft add element t s '{ 20-30 . 40 }'
> > > > # nft add element t s '{ 25-35 . 40 }'
> > > > 
> > > > the second element is silently ignored. I'm returning -EEXIST from
> > > > nft_pipapo_insert(), but nft_add_set_elem() clears it because NLM_F_EXCL
> > > > is not set.
> > > > 
> > > > Are you suggesting that this is consistent and therefore not a problem?    
> > > 
> > >                         NLM_F_EXCL      !NLM_F_EXCL
> > >         exact match       EEXIST             0 [*]
> > >         partial match     EEXIST           EEXIST
> > > 
> > > The [*] case would allow for element timeout/expiration updates from
> > > the control plane for exact matches.  
> > 
> > A-ha. I didn't even consider that.
> >   
> > > Note that element updates are not
> > > supported yet, so this check for !NLM_F_EXCL is a stub. I don't think
> > > we should allow for updates on partial matches
> > > 
> > > I think what it is missing is a error to report "partial match" from
> > > pipapo. Then, the core translates this "partial match" error to EEXIST
> > > whether NLM_F_EXCL is set or not.  
> > 
> > Yes, given what you explained, I also think it's the case.
> >   
> > > Would this work for you?  
> > 
> > It would. I need to write a few more lines in nft_pipapo_insert(),
> > because right now I don't have a special case for "entirely
> > overlapping". Something on the lines of:
> > 
> > 	dup = pipapo_get(net, set, start, genmask);
> > 	if (PTR_ERR(dup) == -ENOENT) {
> >   
> > -->		compare start and end key for this entry with  
> > 		start and end key from 'ext'
> > 
> > Let me know if you want me to post a patch with a placeholder for
> > whatever you have in mind, or if I can help implementing this, etc.  
> 
> Please, go ahead with the placeholder, it might be faster. I'll jump
> on it.

Attached, reasonably tested, the placeholder is 'return -ENOTTY':

# nft add table t
# nft add set t s '{ type ipv4_addr . ipv4_addr ; flags interval ; }'
# nft add element t s '{ 1.1.1.1-2.2.2.2 . 3.3.3.3 }'
# nft add element t s '{ 1.1.1.1-2.2.2.3 . 3.3.3.3 }'
Error: Could not process rule: Inappropriate ioctl for device
add element t s { 1.1.1.1-2.2.2.3 . 3.3.3.3 }
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

One detail, unrelated to this patch, that I should probably document in
man pages and Wiki (I forgot, it occurred to me while testing): it is
allowed to insert an entry if a proper subset of it, with no
overlapping bounds, is already inserted. The reverse sequence is not
allowed. This can be used without ambiguity due to strict guarantees
about ordering. That is:

# nft add element t s '{ 1.0.0.20-1.0.0.21 . 3.3.3.3 }'
# nft add element t s '{ 1.0.0.10-1.0.0.100 . 3.3.3.3 }'
# nft list table ip t
table ip t {
	set s {
		type ipv4_addr . ipv4_addr
		flags interval
		elements = { 1.0.0.20/31 . 3.3.3.3,
			     1.0.0.10-1.0.0.100 . 3.3.3.3 }
	}
}

But:

# nft add element t s '{ 1.0.0.10-1.0.0.100 . 3.3.3.3 }'
# nft add element t s '{ 1.0.0.20-1.0.0.21 . 3.3.3.3 }'
Error: Could not process rule: Inappropriate ioctl for device
add element t s { 1.0.0.20-1.0.0.21 . 3.3.3.3 }
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

This is because least generic entries are only allowed to be added
after more generic ones, and match in that order.

-- 
Stefano

[-- Attachment #2: pipapo_overlap_placeholder.patch --]
[-- Type: text/x-patch, Size: 1573 bytes --]

diff --git a/net/netfilter/nft_set_pipapo.c b/net/netfilter/nft_set_pipapo.c
index 4fc0c924ed5d..fc5e347bfeba 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 -ENOTTY;
+	}
+
+	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 -ENOTTY;
 	}
 
 	/* Validate */