Re: [PATCH bpf-next 2/3] selftests/bpf: libarena: Cache the rbtree's leftmost node and count

[Changwoo Min]

Hi Alexei,

Thanks for the review.

On 11/1/26 10:03 AM, Alexei Starovoitov wrote:
> On Tue, Oct 27, 2026 at 11:00 PM Changwoo Min <changwoo@xxxxxxxxxx> wrote:
> >   struct rbtree {
> > +	/* Writer fields, on a cache line of their own. */
> >   	struct rbnode __arena *root;
> >   	enum rbtree_alloc alloc;
> >   	enum rbtree_insert_mode insert;
> > +
> > +	/*
> > +	 * The leftmost node and the node count on their own cache line.
> > +	 * The writer keeps them current, and readers may read them without
> > +	 * the writer's lock (see rb_first() and friends).
> > +	 */
> > +	struct {
> > +		struct rbnode __arena *first;
> > +		uint64_t nr;
> > +	} __attribute__((aligned(RB_CACHELINE_SIZE)));
> >   };
>
> That's 16 -> 128 bytes.
> Without perf numbers it's a premature optimization.

You are right. I ran a scheduler-side task queue built on this rbtree
(based on scx_lavd replacing its DSQs) on a 2-socket, 192-CPU EPYC
machine (no hyperthreading) to compare the aligned vs. unaligned
versions. The following are the results of the 10 runs.

                                    aligned        unaligned
  perf bench sched messaging (s)    0.51 +- 0.01   0.50 +- 0.01
  perf bench sched pipe (us/op)     3.18 +- 0.04   3.19 +- 0.04
  schbench full, wakeup p99 (us)    78.3 +- 5.7    79.5 +- 3.6
  schbench full, RPS                44941 +- 124   44954 +- 86
  schbench 2x over, RPS             45146 +- 101   45133 +- 141

There are no statistically meaningful differences so I will drop the
alignment in v2.

> > +	ret = rbnode_remove(rbtree, node);
> > +	if (ret)
> > +		return ret;
> > +
> > +	if (was_first)
> > +		rb_set_first(rbtree, next);
>
> In an RB_ALLOC tree rbnode_remove() frees the node and then rebalances
> the tree. first points to the freed node all that time:
>
>    CPU 0, holds the lock            CPU 1, no lock
>    rb_pop()
>      rb_node_remove()
>        rbnode_remove()
>          rb_node_free(node)
>                                     rb_first_key()
>                                       first = rbtree->first
>                                       first->key    <- use after free
>          rebalance
>        rb_set_first(next)
>
> buddy_free() poisons the node. A prog built with ASAN gets a report from
> rb_first_key().
>
> rb_erase_cached() moves rb_leftmost before rb_erase().
> Should it be the same here?
> Move rb_next() from patch 3 in front of this patch. Then at the top of
> rb_node_remove():
>
>    if (rbtree->first == node)
>            rb_set_first(rbtree, rb_next(node));
>    WRITE_ONCE(rbtree->nr, rbtree->nr - 1);
>
> and no need for the wrapper, was_first and the rename to rbnode_remove().

Sure, I will move rb_next() before this patch and update first and
nr at the top of rb_node_remove() in v2, as you suggested.

Regards,
Changwoo Min

> Patch 1 looks good.
>
> pw-bot: cr