[PATCH] sched/eevdf: fix rb augmented with multi fields

[PATCH] sched/eevdf: fix rb augmented with multi fields

[Vincent Guittot]

The eevdf rb tree maintains 3 augmented fields but only one is currently
copied when balancing the tree.

Add a more generic define that can be used when there are several augmented
fields. In this case, we provide a function that takes care of copying all
fields.

Fixes: aef6987d8954 ("sched/eevdf: Propagate min_slice up the cgroup hierarchy")
Signed-off-by: Vincent Guittot <vincent.guittot@linaro.org>
---
 include/linux/rbtree_augmented.h | 35 +++++++++++++++++++++++++-------
 kernel/sched/fair.c              | 15 ++++++++++++--
 2 files changed, 41 insertions(+), 9 deletions(-)

diff --git a/include/linux/rbtree_augmented.h b/include/linux/rbtree_augmented.h
index 6dbc5a1bf6a8..d2fa1c41bfd2 100644
--- a/include/linux/rbtree_augmented.h
+++ b/include/linux/rbtree_augmented.h
@@ -87,18 +87,18 @@ rb_add_augmented_cached(struct rb_node *node, struct rb_root_cached *tree,
 }
 
 /*
- * Template for declaring augmented rbtree callbacks (generic case)
+ * Template for declaring augmented rbtree callbacks (generic multi fields)
  *
  * RBSTATIC:    'static' or empty
  * RBNAME:      name of the rb_augment_callbacks structure
  * RBSTRUCT:    struct type of the tree nodes
  * RBFIELD:     name of struct rb_node field within RBSTRUCT
- * RBAUGMENTED: name of field within RBSTRUCT holding data for subtree
- * RBCOMPUTE:   name of function that recomputes the RBAUGMENTED data
+ * RBCOPY:	name of function that copies the RBAUGMENTED datas
+ * RBCOMPUTE:   name of function that recomputes the RBAUGMENTED datas
  */
 
-#define RB_DECLARE_CALLBACKS(RBSTATIC, RBNAME,				\
-			     RBSTRUCT, RBFIELD, RBAUGMENTED, RBCOMPUTE)	\
+#define RB_DECLARE_CALLBACKS_MULTI(RBSTATIC, RBNAME,			\
+			     RBSTRUCT, RBFIELD, RBCOPY, RBCOMPUTE)	\
 static inline void							\
 RBNAME ## _propagate(struct rb_node *rb, struct rb_node *stop)		\
 {									\
@@ -114,14 +114,14 @@ RBNAME ## _copy(struct rb_node *rb_old, struct rb_node *rb_new)		\
 {									\
 	RBSTRUCT *old = rb_entry(rb_old, RBSTRUCT, RBFIELD);		\
 	RBSTRUCT *new = rb_entry(rb_new, RBSTRUCT, RBFIELD);		\
-	new->RBAUGMENTED = old->RBAUGMENTED;				\
+	RBCOPY(new, old);						\
 }									\
 static void								\
 RBNAME ## _rotate(struct rb_node *rb_old, struct rb_node *rb_new)	\
 {									\
 	RBSTRUCT *old = rb_entry(rb_old, RBSTRUCT, RBFIELD);		\
 	RBSTRUCT *new = rb_entry(rb_new, RBSTRUCT, RBFIELD);		\
-	new->RBAUGMENTED = old->RBAUGMENTED;				\
+	RBCOPY(new, old);						\
 	RBCOMPUTE(old, false);						\
 }									\
 RBSTATIC const struct rb_augment_callbacks RBNAME = {			\
@@ -130,6 +130,27 @@ RBSTATIC const struct rb_augment_callbacks RBNAME = {			\
 	.rotate = RBNAME ## _rotate					\
 };
 
+/*
+ * Template for declaring augmented rbtree callbacks (generic single field)
+ *
+ * RBSTATIC:    'static' or empty
+ * RBNAME:      name of the rb_augment_callbacks structure
+ * RBSTRUCT:    struct type of the tree nodes
+ * RBFIELD:     name of struct rb_node field within RBSTRUCT
+ * RBAUGMENTED: name of field within RBSTRUCT holding data for subtree
+ * RBCOMPUTE:   name of function that recomputes the RBAUGMENTED data
+ */
+
+#define RB_DECLARE_CALLBACKS(RBSTATIC, RBNAME,				\
+			     RBSTRUCT, RBFIELD, RBAUGMENTED, RBCOMPUTE)	\
+static inline void							\
+RBNAME ## _copy_single(RBSTRUCT *new, RBSTRUCT *old)			\
+{									\
+	new->RBAUGMENTED = old->RBAUGMENTED;				\
+}									\
+RB_DECLARE_CALLBACKS_MULTI(RBSTATIC, RBNAME,				\
+		     RBSTRUCT, RBFIELD, RBNAME ## _copy_single, RBCOMPUTE)
+
 /*
  * Template for declaring augmented rbtree callbacks,
  * computing RBAUGMENTED scalar as max(RBCOMPUTE(node)) for all subtree nodes.
diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index db5937d7e46e..019812c4fe32 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -1037,6 +1037,16 @@ static inline void __max_slice_update(struct sched_entity *se, struct rb_node *n
 	}
 }
 
+/*
+ * se->min_vruntime = min(se->vruntime, {left,right}->min_vruntime)
+ */
+static inline void min_vruntime_copy(struct sched_entity *new, struct sched_entity *old)
+{
+	new->min_vruntime = old->min_vruntime;
+	new->min_slice = old->min_slice;
+	new->max_slice = old->max_slice;
+}
+
 /*
  * se->min_vruntime = min(se->vruntime, {left,right}->min_vruntime)
  */
@@ -1064,8 +1074,9 @@ static inline bool min_vruntime_update(struct sched_entity *se, bool exit)
 	       se->max_slice == old_max_slice;
 }
 
-RB_DECLARE_CALLBACKS(static, min_vruntime_cb, struct sched_entity,
-		     run_node, min_vruntime, min_vruntime_update);
+
+RB_DECLARE_CALLBACKS_MULTI(static, min_vruntime_cb, struct sched_entity,
+		     run_node, min_vruntime_copy, min_vruntime_update);
 
 /*
  * Enqueue an entity into the rb-tree:
-- 
2.53.0

Re: [PATCH] sched/eevdf: fix rb augmented with multi fields

[K Prateek Nayak]

Hello Vincent,

On 9/8/2026 7:25 PM, Vincent Guittot wrote:
> The eevdf rb tree maintains 3 augmented fields but only one is currently
> copied when balancing the tree.
> 
> Add a more generic define that can be used when there are several augmented
> fields. In this case, we provide a function that takes care of copying all
> fields.
> 
> Fixes: aef6987d8954 ("sched/eevdf: Propagate min_slice up the cgroup hierarchy")
> Signed-off-by: Vincent Guittot <vincent.guittot@linaro.org>

I remember stumbling on this in
https://lore.kernel.org/lkml/20250220093257.9380-22-kprateek.nayak@amd.com/
but working around the problem in the scheduler layer instead.

Generic rb-tree layer extension makes more sense. Feel free to include:

Reviewed-by: K Prateek Nayak <kprateek.nayak@amd.com>
Tested-by: K Prateek Nayak <kprateek.nayak@amd.com>

[..snip.]
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index db5937d7e46e..019812c4fe32 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -1037,6 +1037,16 @@ static inline void __max_slice_update(struct sched_entity *se, struct rb_node *n
>  	}
>  }
>  
> +/*
> + * se->min_vruntime = min(se->vruntime, {left,right}->min_vruntime)
> + */

nit. Do we need this comment? It doesn't really describe the copy
callback.

> +static inline void min_vruntime_copy(struct sched_entity *new, struct sched_entity *old)
> +{
> +	new->min_vruntime = old->min_vruntime;
> +	new->min_slice = old->min_slice;
> +	new->max_slice = old->max_slice;
> +}
> +
>  /*
>   * se->min_vruntime = min(se->vruntime, {left,right}->min_vruntime)
>   */

The one over here above min_vruntime_update() makes sense and should
suffice IMO.

> @@ -1064,8 +1074,9 @@ static inline bool min_vruntime_update(struct sched_entity *se, bool exit)
>  	       se->max_slice == old_max_slice;
>  }
>  
> -RB_DECLARE_CALLBACKS(static, min_vruntime_cb, struct sched_entity,
> -		     run_node, min_vruntime, min_vruntime_update);
> +
> +RB_DECLARE_CALLBACKS_MULTI(static, min_vruntime_cb, struct sched_entity,
> +		     run_node, min_vruntime_copy, min_vruntime_update);
>  
>  /*
>   * Enqueue an entity into the rb-tree:

-- 
Thanks and Regards,
Prateek

Re: [PATCH] sched/eevdf: fix rb augmented with multi fields

[Vincent Guittot]

On Tue, 8 Sept 2026 at 22:37, K Prateek Nayak <kprateek.nayak@amd.com> wrote:
>
> Hello Vincent,
>
> On 9/8/2026 7:25 PM, Vincent Guittot wrote:
> > The eevdf rb tree maintains 3 augmented fields but only one is currently
> > copied when balancing the tree.
> >
> > Add a more generic define that can be used when there are several augmented
> > fields. In this case, we provide a function that takes care of copying all
> > fields.
> >
> > Fixes: aef6987d8954 ("sched/eevdf: Propagate min_slice up the cgroup hierarchy")
> > Signed-off-by: Vincent Guittot <vincent.guittot@linaro.org>
>
> I remember stumbling on this in
> https://lore.kernel.org/lkml/20250220093257.9380-22-kprateek.nayak@amd.com/
> but working around the problem in the scheduler layer instead.
>
> Generic rb-tree layer extension makes more sense. Feel free to include:
>
> Reviewed-by: K Prateek Nayak <kprateek.nayak@amd.com>
> Tested-by: K Prateek Nayak <kprateek.nayak@amd.com>

Thanks

>
> [..snip.]
> > diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> > index db5937d7e46e..019812c4fe32 100644
> > --- a/kernel/sched/fair.c
> > +++ b/kernel/sched/fair.c
> > @@ -1037,6 +1037,16 @@ static inline void __max_slice_update(struct sched_entity *se, struct rb_node *n
> >       }
> >  }
> >
> > +/*
> > + * se->min_vruntime = min(se->vruntime, {left,right}->min_vruntime)
> > + */
>
> nit. Do we need this comment? It doesn't really describe the copy
> callback.

No, it was just the result of a copy/paste

>
> > +static inline void min_vruntime_copy(struct sched_entity *new, struct sched_entity *old)
> > +{
> > +     new->min_vruntime = old->min_vruntime;
> > +     new->min_slice = old->min_slice;
> > +     new->max_slice = old->max_slice;
> > +}
> > +
> >  /*
> >   * se->min_vruntime = min(se->vruntime, {left,right}->min_vruntime)
> >   */
>
> The one over here above min_vruntime_update() makes sense and should
> suffice IMO.
>
> > @@ -1064,8 +1074,9 @@ static inline bool min_vruntime_update(struct sched_entity *se, bool exit)
> >              se->max_slice == old_max_slice;
> >  }
> >
> > -RB_DECLARE_CALLBACKS(static, min_vruntime_cb, struct sched_entity,
> > -                  run_node, min_vruntime, min_vruntime_update);
> > +
> > +RB_DECLARE_CALLBACKS_MULTI(static, min_vruntime_cb, struct sched_entity,
> > +                  run_node, min_vruntime_copy, min_vruntime_update);
> >
> >  /*
> >   * Enqueue an entity into the rb-tree:
>
> --
> Thanks and Regards,
> Prateek
>

Re: [PATCH] sched/eevdf: fix rb augmented with multi fields

[Kayra Cizmeci]

Hello Vincent,

> The eevdf rb tree maintains 3 augmented fields but only one is currently
> copied when balancing the tree.

> Add a more generic define that can be used when there are several augmented
> fields. In this case, we provide a function that takes care of copying all
> fields.

So the problem is we need to copy 3 things and we copy 1 thing currently? (simplified)
Also, I read Prateek's review too, so I'll not go on the same things on this one.

And I thought that 2 separate reviews are better than one, so... :>

> /*
> - * Template for declaring augmented rbtree callbacks (generic case)
> + * Template for declaring augmented rbtree callbacks (generic multi fields)
>   *
>   * RBSTATIC:    'static' or empty
>   * RBNAME:      name of the rb_augment_callbacks structure
>   * RBSTRUCT:    struct type of the tree nodes
>   * RBFIELD:     name of struct rb_node field within RBSTRUCT
> - * RBAUGMENTED: name of field within RBSTRUCT holding data for subtree
> - * RBCOMPUTE:   name of function that recomputes the RBAUGMENTED data
> + * RBCOPY:	name of function that copies the RBAUGMENTED datas
> + * RBCOMPUTE:   name of function that recomputes the RBAUGMENTED datas
>  */

nit. 'datas' is wrong in english. I would use it like that too. Maybe 'fields' but
I think using 'fields' in one of them and 'data' in the others would look bad. 
Ah. English is annoying.

> @@ -114,14 +114,14 @@ RBNAME ## _copy(struct rb_node *rb_old, struct rb_node *rb_new)		\
>  {									\
>  	RBSTRUCT *old = rb_entry(rb_old, RBSTRUCT, RBFIELD);		\
>  	RBSTRUCT *new = rb_entry(rb_new, RBSTRUCT, RBFIELD);		\
> -	new->RBAUGMENTED = old->RBAUGMENTED;				\
> +	RBCOPY(new, old);						\
>  }									\
>  static void								\
>  RBNAME ## _rotate(struct rb_node *rb_old, struct rb_node *rb_new)	\
>  {									\
>  	RBSTRUCT *old = rb_entry(rb_old, RBSTRUCT, RBFIELD);		\
>  	RBSTRUCT *new = rb_entry(rb_new, RBSTRUCT, RBFIELD);		\
> -	new->RBAUGMENTED = old->RBAUGMENTED;				\
> +	RBCOPY(new, old);						\
>  	RBCOMPUTE(old, false);						\
>  }

The bool exit on min_vruntime_update() parameter appears to be unused when I grep or search for
any use case. Could we remove it?

The other things aside these is good for me. It looks really weird to copy only
min_vruntime while not copying others at the first place. And I think the
solution is good. 

I was thinking to do a boot test, but I did not thought it would add something
to the patch. So I did not. I can if it's going to add something tho.

Include if you want to :-):

Reviewed-by: Kayra Cizmeci <kayracizmeci@gmail.com>

Re: [PATCH] sched/eevdf: fix rb augmented with multi fields

[Peter Zijlstra]

On Wed, Sep 09, 2026 at 09:58:27PM +0300, Kayra Cizmeci wrote:

> The bool exit on min_vruntime_update() parameter appears to be unused
> when I grep or search for any use case. Could we remove it?

grep for RBCOMPUTE, you'll find it used in RBNAME ## _propagate().

Re: [PATCH] sched/eevdf: fix rb augmented with multi fields

[Kayra Cizmeci]

>> The bool exit on min_vruntime_update() parameter appears to be unused
>> when I grep or search for any use case. Could we remove it?

> grep for RBCOMPUTE, you'll find it used in RBNAME ## _propagate().

I knew that it is used there. But it's not really used in min_vruntime_update().

Reading some code, the parameter is here because there are 2 different functions for RBCOMPUTE
and one of them uses the parameter while the other not uses it. 

So it's better if we remove it, but there is no clean way that I can see using to remove it.