On Fri, Dec 06, 2019 at 08:26:47PM +0100, Pablo Neira Ayuso wrote: > 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. To extend the problem description: The issue is that the existing lookup optimization (that only works for the anonymous sets) might not reach the opening [ a+1, ... element if the closing ... , a+1) is found in first place when walking over the rbtree. Hence, walking the full tree in that case is needed. > 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. > >
