Re: [PATCH nf] netfilter: nft_set_rbtree: bogus lookup/get on consecutive elements in named sets

[Pablo Neira Ayuso <pablo@netfilter.org>]

On Thu, Dec 05, 2019 at 11:04:08PM +0100, Phil Sutter wrote:
> Hi Pablo,
> 
> On Thu, Dec 05, 2019 at 07:07:06PM +0100, Pablo Neira Ayuso wrote:
> > The existing rbtree implementation might store consecutive elements
> > where the closing element and the opening element might overlap, eg.
> > 
> > 	[ a, a+1) [ a+1, a+2)
> > 
> > This patch removes the optimization for non-anonymous sets in the exact
> > matching case, where it is assumed to stop searching in case that the
> > closing element is found. Instead, invalidate candidate interval and
> > keep looking further in the tree.
> > 
> > This patch fixes the lookup and get operations.
> 
> I didn't get what the actual problem is?

The lookup/get results false, while there is an element in the rbtree.
Moreover, the get operation returns true as if a+2 would be in the
tree. This happens with named sets after several set updates, I could
reproduce the issue with several elements mixed with insertion and
deletions in one batch.

I managed to trigger the problem using the test file coming in this
patch: https://patchwork.ozlabs.org/patch/1204779/

I can extend the patch description if you like.

> [...]
> > diff --git a/net/netfilter/nft_set_rbtree.c b/net/netfilter/nft_set_rbtree.c
> > index 57123259452f..510169e28065 100644
> > --- a/net/netfilter/nft_set_rbtree.c
> > +++ b/net/netfilter/nft_set_rbtree.c
> [...]
> > @@ -141,6 +146,8 @@ static bool __nft_rbtree_get(const struct net *net, const struct nft_set *set,
> >  		} else {
> >  			if (!nft_set_elem_active(&rbe->ext, genmask))
> >  				parent = rcu_dereference_raw(parent->rb_left);
> > +				continue;
> > +			}
> >  
> >  			if (!nft_set_ext_exists(&rbe->ext, NFT_SET_EXT_FLAGS) ||
> >  			    (*nft_set_ext_flags(&rbe->ext) & NFT_SET_ELEM_INTERVAL_END) ==
> 
> Are you sure about that chunk? It adds a closing brace without a
> matching opening one. Either this patch ignores whitespace change or
> there's something fishy. :)

Yes, I botched it when squashing my patches before submission. I just
sent a v2.

Thanks.