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?
> 
> 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?
> 
> Element has expired -> Mark element and the end-pair as dead,
> then reap all expired and dead nodes from commit callback.

This makes sense.

> 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.

Yes, refresh set element timeout semantics depends on what the timeout
says in the preparation phase. The same problem that is being
discussed in the other two emails in different thread.

We could annotate the current time at the beginning of the
transaction and use it to check if the element has expired, so set
element expiration stops being a moving target.