Re: [PATCH nf-next 0/3] netfilter: nft_set_rbtree: use cloned tree for insertions and removal

[Phil Sutter <phil@nwl.cc>]

Hi,

On Tue, Nov 18, 2025 at 05:07:56PM +0100, Fernando Fernandez Mancera wrote:
> On 11/18/25 12:16 PM, Florian Westphal wrote:
> > This series fixes false negative lookup bug in rbtree set backend that
> > can occur during transaction.
> > 
> > First two patches prepare for actual fix, which is coming in last patch.
> > 
> > All inserts/removals will now occur in a cloned copy, so packetpath can
> > no longer observe the problematic mixed-bag of old, current and new
> > elements.
> > 
> > The live tree will only have reachable elements that are active in the
> > current generation or were active in the previous generation (but are still
> > valid while packetpath holds rcu read lock).  The latter case is only
> > temporary, as new lookups already observe the updated tree).
> > 
> 
> I have been taking a look to the series and testing it with different 
> set sizes. The implementation looks good to me but I noticed that due 
> the new "clone" mechanism there is an impact on performance when 
> modifying an existing rbtree set (inserts or deletions). According to my 
> number the impact would be around 40~%. Usually that isn't problematic 
> but if big sets are used.. then it is a bit more. e.g
> 
> 200K elements ~ avg. time insertion before 510ms after 744ms
> 500K elements ~ avg. time insertion before 5460ms after 7730ms

I wonder if nft_rbtree_maybe_clone() could run a simpler copying
algorithm than properly inserting every element from the old tree into
the new one since the old tree is already correctly organized -
basically leveraging the existing knowledge of every element's correct
position.

Or is there a need to traverse the new tree with each element instead of
copying the whole thing as-is?

Cheers, Phil