Re: [PATCH 2/3] rbtree: update augmented data on the way down in rb_add_augmented_cached()

[Peter Zijlstra]

On Tue, Sep 29, 2026 at 01:24:46PM +0800, Yiwei Lin wrote:
> On 2026/09/29 05:37, Peter Zijlstra wrote:
> > This builds and boot, so it must be perfect, right ;-)
> >
> > Assisted-by: Brain
> > Signed-off-by: Peter Zijlstra (Intel) <peterz@xxxxxxxxxxxxx>
> 
> Right, thanks.
> 
> If you're fine with me carrying it, I can take it into v2 with and
> derive ->merge() from the same RB_AUG() list, so
> rb_add_augmented_cached() folds the new node into its ancestors in
> the one pass down instead of the ->propagate() round trip.
> 
> One thing I am aware here:  RB_AUG()'s cmp only
> expresses "pick one of the two", so min/max style aggregates; a sum or
> a count (subtree size, total weight) can't be written, where the old
> RBCOMPUTE could do anything.  Nobody in-tree needs that today, so it might
> be acceptable as is, but it's a regression in generality for the same
> price:
> 
>         RB_AUG(val, aug, fold)  /* _val = fold(_val, child->aug) */
> 
> keeps the register-local recompute exactly as it is, drops RB_MIN /
> RB_MAX in favour of the existing min()/max(), and a sum is just
> "a + b".  For sched that's min, max and a wrapping-safe min for
> min_vruntime. Do you think this can be accepted as is, or should I try
> to make it more general?

The fold() thing is indeed an excellent suggestion. Make it so ;-)

Thanks!