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

[Changwoo Min <changwoo@igalia.com>]

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@igalia.com> 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