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

[Florian Westphal <fw@strlen.de>]

Phil Sutter <phil@nwl.cc> wrote:

Thanks for doing this but I'm not sold on this.
This also traverses the entire tree, which is afaics not avoidable
and also the expensive part.

I don't get much better results with this version
(10 inserts into 800k tree: mainline: ~3m, patchset, 3m47m, your
version 3m47s).

> +static void nft_rbtree_copy(const struct nft_set *set, struct rb_node *parent,
> +			    struct rb_node **pos, struct nft_rbtree_elem *elem)
> +{
> +	struct nft_rbtree *priv = nft_set_priv(set);
> +	u8 genbit = nft_rbtree_genbit_copy(priv);
> +
> +	rb_link_node_rcu(&elem->node[genbit], parent, pos);
> +	rb_set_parent_color(&elem->node[genbit], parent,
> +			    rb_color(&elem->node[!genbit]));
> +
> +	if (elem->node[!genbit].rb_left)
> +		nft_rbtree_copy(set, &elem->node[genbit],
> +				&elem->node[genbit].rb_left,
> +				rb_entry(elem->node[!genbit].rb_left,
> +					 struct nft_rbtree_elem,
> +					 node[!genbit]));

... and that makes recursive calls, i am reluctant here.

It should be fine given its limited by tree height, but it makes
me uneasy to have this.