Hi Pablo,
On Mon, 27 Jun 2022 18:59:06 +0200
Pablo Neira Ayuso <pablo@xxxxxxxxxxxxx> wrote:
> Hi Stefano,
>
> On Tue, Jun 14, 2022 at 03:07:04AM +0200, Stefano Brivio wrote:
> > ...instead of a tree descent, which became overly complicated in an
> > attempt to cover cases where expired or inactive elements would
> > affect comparisons with the new element being inserted.
> >
> > Further, it turned out that it's probably impossible to cover all
> > those cases, as inactive nodes might entirely hide subtrees
> > consisting of a complete interval plus a node that makes the current
> > insertion not overlap.
> >
> > For the insertion operation itself, this essentially reverts back to
> > the implementation before commit 7c84d41416d8
> > ("netfilter: nft_set_rbtree: Detect partial overlaps on insertion"),
> > except that cases of complete overlap are already handled in the
> > overlap detection phase itself, which slightly simplifies the loop to
> > find the insertion point.
> >
> > Reported-by: Pablo Neira Ayuso <pablo@xxxxxxxxxxxxx>
> > Fixes: 7c84d41416d8 ("netfilter: nft_set_rbtree: Detect partial overlaps on insertion")
> > Signed-off-by: Stefano Brivio <sbrivio@xxxxxxxxxx>
> > ---
> > net/netfilter/nft_set_rbtree.c | 194 ++++++++++-----------------------
> > 1 file changed, 58 insertions(+), 136 deletions(-)
>
> When running tests this is increasing the time to detect overlaps in
> my testbed, because of the linear list walk for each element.
>
> So I have been looking at an alternative approach (see attached patch) to
> address your comments. The idea is to move out the overlapping nodes
> from the element in the tree, instead keep them in a list.
>
> root
> / \
> elem elem -> update -> update
> / \
> elem elem
>
> Each rbtree element in the tree .has pending_list which stores the
> element that supersede the existing (inactive) element. There is also a
> .list which is used to add the element to the .pending_list. Elements
> in the tree might have a .pending_list with one or more elements.
>
> The .deactivate path looks for the last (possibly) active element. The
> .remove path depends on the element state: a) element is singleton (no
> pending elements), then erase from tree, b) element has a pending
> list, then replace the first element in the pending_list by this node,
> and splice pending_list (there might be more elements), c) this
> element is in the pending_list, the just remove it. This handles both
> commit (walks through the list of transaction forward direction) and
> abort path (walks through the list of transactions in backward
> direction).
I think that's brilliant, give me a couple of days to have a thorough
look at it.
--
Stefano
