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

[Alexei Starovoitov]

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.

> +	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().

Patch 1 looks good.

pw-bot: cr