Re: [PATCH nf 1/2] netfilter: nft_set_rbtree: move sync GC from insert path to set->ops->commit

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

On Mon, Oct 02, 2023 at 04:23:12PM +0200, Florian Westphal wrote:
> Pablo Neira Ayuso <pablo@netfilter.org> wrote:
> > According to 2ee52ae94baa ("netfilter: nft_set_rbtree: skip sync GC for
> > new elements in this transaction"), new elements in this transaction
> > might expire before such transaction ends. Skip sync GC is needed for
> > such elements otherwise commit path might walk over an already released
> > object.
> > 
> > However, Florian found that while iterating the tree from the insert
> > path for sync GC, it is possible that stale references could still
> > happen for elements in the less-equal and great-than boundaries to
> > narrow down the tree descend to speed up overlap detection, this
> > triggers bogus overlap errors.
> > 
> > This patch skips expired elements in the overlap detection routine which
> > iterates on the reversed ordered list of elements that represent the
> > intervals. Since end elements provide no expiration extension, check for
> > the next non-end element in this interval, hence, skip both elements in
> > the iteration if the interval has expired.
> 
> 10.1.2.3 - 10.1.2.30  (expired!)
> 
> transaction wants to add:
> 10.1.2.2 - 10.1.2.29
> 
> AFAICS, this is now mismerged into:
> 
> 10.1.2.2 - 10.1.2.30, because walking back to
> next end element from expired 10.1.2.3 will
> find 10.1.2.29 as first preceeding end element, no?

Yes, this corner case is currently possible.

> and the "commit" operation comes after genid bump, so we can't
> restrict that to "not active in next gen" or similar :-/
> 
> Can you use dead-bit instead?

Yes, on-demand GC remains in place from insert path and it uses the
dead bit.

> Element has expired -> Mark element and the end-pair as dead,
> then reap all expired and dead nodes from commit callback.
>
> Problem is what to do after reset-inerval support is added,
> because the newly-marked-dead elements could have a timeout
> refresh already pending, and I don't see how this can be handled.

You mean:

transaction
set element E is refreshed
set element E expires
set element E is marked as dead by on-demand GC (when walking down for different element E2)
end transaction

This can probably be addressed by using a curren time snapshot at the
beginning of the transaction to check for the expiration, instead of
checking for the current real time which is a moving target.

Let's consolidate this discussion in one single email thread, all
these issues are interrelated :)