[PATCH v2 0/4] sched/fair: Rework task_h_load()

[PATCH v2 0/4] sched/fair: Rework task_h_load()

[Peter Zijlstra]

Rework of task_h_load(), which isn't all that sound atm.

Also in git here:

  git://git.kernel.org/pub/scm/linux/kernel/git/peterz/queue.git sched/task_h_load

Changes since v1:

 - Fixed FAIR_GROUP_SCHED=n build fail
 - Fixed FAIR_GROUP_SCHED runtime fail (Vincent)
 - Rebased on current tree


v1: https://patch.msgid.link/20260828074059.232353141%40infradead.org

[PATCH v2 1/4] sched: Rename/clarify sched_class::task_tick(.queued) argument

[Peter Zijlstra]

For some reason the sched_class::task_tick() argument that indicates it being
an hrtick, is called @queued. I'm sure naming is hard and all, but lets fix
this.

Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
---
 kernel/sched/deadline.c |    4 ++--
 kernel/sched/ext/ext.c  |    2 +-
 kernel/sched/fair.c     |   12 ++++++------
 kernel/sched/idle.c     |    2 +-
 kernel/sched/rt.c       |    2 +-
 kernel/sched/sched.h    |    2 +-
 6 files changed, 12 insertions(+), 12 deletions(-)

--- a/kernel/sched/deadline.c
+++ b/kernel/sched/deadline.c
@@ -2879,7 +2879,7 @@ static void put_prev_task_dl(struct rq *
  * and everything must be accessed through the @rq and @curr passed in
  * parameters.
  */
-static void task_tick_dl(struct rq *rq, struct task_struct *p, int queued)
+static void task_tick_dl(struct rq *rq, struct task_struct *p, int hrtick)
 {
 	update_curr_dl(rq);
 
@@ -2889,7 +2889,7 @@ static void task_tick_dl(struct rq *rq,
 	 * not being the leftmost task anymore. In that case NEED_RESCHED will
 	 * be set and schedule() will start a new hrtick for the next task.
 	 */
-	if (hrtick_enabled_dl(rq) && queued && p->dl.runtime > 0 &&
+	if (hrtick_enabled_dl(rq) && hrtick && p->dl.runtime > 0 &&
 	    is_leftmost(&p->dl, &rq->dl))
 		start_hrtick_dl(rq, &p->dl);
 }
--- a/kernel/sched/ext/ext.c
+++ b/kernel/sched/ext/ext.c
@@ -3809,7 +3809,7 @@ void scx_tick(struct rq *rq)
 	update_other_load_avgs(rq);
 }
 
-static void task_tick_scx(struct rq *rq, struct task_struct *curr, int queued)
+static void task_tick_scx(struct rq *rq, struct task_struct *curr, int hrtick)
 {
 	struct scx_sched *sch = scx_task_sched(curr);
 
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -6772,7 +6772,7 @@ static void put_prev_entity(struct cfs_r
 }
 
 static void
-entity_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr, int queued)
+entity_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr, int hrtick)
 {
 	/*
 	 * Update run-time statistics of the 'current'.
@@ -6787,10 +6787,10 @@ entity_tick(struct cfs_rq *cfs_rq, struc
 
 #ifdef CONFIG_SCHED_HRTICK
 	/*
-	 * queued ticks are scheduled to match the slice, so don't bother
+	 * hrticks are scheduled to match the slice, so don't bother
 	 * validating it and just reschedule.
 	 */
-	if (queued) {
+	if (hrtick) {
 		resched_curr(rq_of(cfs_rq));
 		return;
 	}
@@ -15309,7 +15309,7 @@ static inline void task_tick_core(struct
  * and everything must be accessed through the @rq and @curr passed in
  * parameters.
  */
-static void task_tick_fair(struct rq *rq, struct task_struct *curr, int queued)
+static void task_tick_fair(struct rq *rq, struct task_struct *curr, int hrtick)
 {
 	struct sched_entity *se = &curr->se;
 
@@ -15319,7 +15319,7 @@ static void task_tick_fair(struct rq *rq
 
 		for_each_sched_entity(se) {
 			cfs_rq = cfs_rq_of(se);
-			entity_tick(cfs_rq, se, queued);
+			entity_tick(cfs_rq, se, hrtick);
 
 			weight = __calc_prop_weight(cfs_rq, se, weight);
 		}
@@ -15328,7 +15328,7 @@ static void task_tick_fair(struct rq *rq
 		reweight_eevdf(cfs_rq, se, weight, se->on_rq);
 	}
 
-	if (queued)
+	if (hrtick)
 		return;
 
 	if (static_branch_unlikely(&sched_numa_balancing))
--- a/kernel/sched/idle.c
+++ b/kernel/sched/idle.c
@@ -538,7 +538,7 @@ dequeue_task_idle(struct rq *rq, struct
  * and everything must be accessed through the @rq and @curr passed in
  * parameters.
  */
-static void task_tick_idle(struct rq *rq, struct task_struct *curr, int queued)
+static void task_tick_idle(struct rq *rq, struct task_struct *curr, int hrtick)
 {
 	update_curr_idle(rq);
 }
--- a/kernel/sched/rt.c
+++ b/kernel/sched/rt.c
@@ -2541,7 +2541,7 @@ static inline void watchdog(struct rq *r
  * and everything must be accessed through the @rq and @curr passed in
  * parameters.
  */
-static void task_tick_rt(struct rq *rq, struct task_struct *p, int queued)
+static void task_tick_rt(struct rq *rq, struct task_struct *p, int hrtick)
 {
 	struct sched_rt_entity *rt_se = &p->rt;
 
--- a/kernel/sched/sched.h
+++ b/kernel/sched/sched.h
@@ -2737,7 +2737,7 @@ struct sched_class {
 	 * sched_tick: rq->lock
 	 * sched_tick_remote: rq->lock
 	 */
-	void (*task_tick)(struct rq *rq, struct task_struct *p, int queued);
+	void (*task_tick)(struct rq *rq, struct task_struct *p, int hrtick);
 	/*
 	 * sched_cgroup_fork: p->pi_lock
 	 */

[PATCH v2 2/4] sched/fair: Fold cfs_rq_of(se) into for_each_sched_entity()

[Peter Zijlstra]

Pretty much every for_each_sched_entity() loop does: cfs_rq = cfs_rq_of(se) as
the very first thing. Fold it into the for_each_sched_entity() macro.

This paves the way to have the macro track a backlink transparantly.

Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
---
 kernel/sched/fair.c |   81 +++++++++++++++++++++++-----------------------------
 1 file changed, 37 insertions(+), 44 deletions(-)

--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -318,8 +318,8 @@ const struct sched_class fair_sched_clas
 #ifdef CONFIG_FAIR_GROUP_SCHED
 
 /* Walk up scheduling entities hierarchy */
-#define for_each_sched_entity(se) \
-		for (; se; se = se->parent)
+#define for_each_sched_entity(se, cfs_rq)				\
+	for (; (se) && ((cfs_rq) = cfs_rq_of(se)); (se) = (se)->parent)
 
 static inline bool list_add_leaf_cfs_rq(struct cfs_rq *cfs_rq)
 {
@@ -453,8 +453,8 @@ static int se_is_idle(struct sched_entit
 
 #else /* !CONFIG_FAIR_GROUP_SCHED: */
 
-#define for_each_sched_entity(se) \
-		for (; se; se = NULL)
+#define for_each_sched_entity(se, cfs_rq) \
+	for (; (se) && ((cfs_rq) = cfs_rq_of(se)); (se) = NULL)
 
 static inline bool list_add_leaf_cfs_rq(struct cfs_rq *cfs_rq)
 {
@@ -2277,9 +2277,10 @@ static void update_curr(struct cfs_rq *c
 static void update_curr_fair(struct rq *rq)
 {
 	struct sched_entity *se = &rq->donor->se;
+	struct cfs_rq *cfs_rq;
 
-	for_each_sched_entity(se)
-		update_curr(cfs_rq_of(se));
+	for_each_sched_entity(se, cfs_rq)
+		update_curr(cfs_rq);
 }
 
 static inline void
@@ -5011,18 +5012,19 @@ static void reweight_task_fair(struct rq
 {
 	struct sched_entity *se = &p->se;
 	unsigned long weight = NICE_0_LOAD;
+	struct cfs_rq *cfs_rq = cfs_rq_of(se);
 
 	if (se->on_rq)
 		update_curr_fair(rq);
 
-	reweight_entity(cfs_rq_of(se), se, lw->weight);
+	reweight_entity(cfs_rq, se, lw->weight);
 	se->load.inv_weight = lw->inv_weight;
 
 	if (!se->on_rq)
 		return;
 
-	for_each_sched_entity(se)
-		weight = __calc_prop_weight(cfs_rq_of(se), se, weight);
+	for_each_sched_entity(se, cfs_rq)
+		weight = __calc_prop_weight(cfs_rq, se, weight);
 
 	reweight_eevdf(&rq->cfs, &p->se, weight, p->se.on_rq);
 }
@@ -6593,6 +6595,8 @@ static __always_inline void return_cfs_r
 
 static void set_delayed(struct sched_entity *se)
 {
+	struct cfs_rq *cfs_rq;
+
 	/*
 	 * Delayed se of cfs_rq have no tasks queued on them.
 	 * Do not adjust h_nr_runnable since __dequeue_task()
@@ -6615,15 +6619,14 @@ static void set_delayed(struct sched_ent
 	pref_llc_running_dec(rq_of(cfs_rq_of(se)), task_of(se));
 	se->sched_delayed = 1;
 
-	for_each_sched_entity(se) {
-		struct cfs_rq *cfs_rq = cfs_rq_of(se);
-
+	for_each_sched_entity(se, cfs_rq)
 		cfs_rq->h_nr_runnable--;
-	}
 }
 
 static void clear_delayed(struct sched_entity *se)
 {
+	struct cfs_rq *cfs_rq;
+
 	se->sched_delayed = 0;
 
 	/*
@@ -6642,11 +6645,8 @@ static void clear_delayed(struct sched_e
 	 */
 	pref_llc_running_inc(rq_of(cfs_rq_of(se)), task_of(se));
 
-	for_each_sched_entity(se) {
-		struct cfs_rq *cfs_rq = cfs_rq_of(se);
-
+	for_each_sched_entity(se, cfs_rq)
 		cfs_rq->h_nr_runnable++;
-	}
 }
 
 static void
@@ -7308,14 +7308,16 @@ void unthrottle_cfs_rq(struct cfs_rq *cf
 	walk_tg_tree_from(cfs_rq->tg, tg_nop, tg_unthrottle_up, (void *)rq);
 
 	if (!cfs_rq->load.weight) {
+		struct cfs_rq *cfs_rq_se;
+
 		if (!cfs_rq->on_list)
 			return;
 		/*
 		 * Nothing to run but something to decay (on_list)?
 		 * Complete the branch.
 		 */
-		for_each_sched_entity(se) {
-			if (list_add_leaf_cfs_rq(cfs_rq_of(se)))
+		for_each_sched_entity(se, cfs_rq_se) {
+			if (list_add_leaf_cfs_rq(cfs_rq_se))
 				break;
 		}
 	}
@@ -8161,13 +8163,12 @@ static unsigned long enqueue_hierarchy(s
 	struct sched_entity *se = &p->se;
 	int h_nr_idle = task_has_idle_policy(p);
 	int h_nr_runnable = 1;
+	struct cfs_rq *cfs_rq;
 
 	if (task_new && se->sched_delayed)
 		h_nr_runnable = 0;
 
-	for_each_sched_entity(se) {
-		struct cfs_rq *cfs_rq = cfs_rq_of(se);
-
+	for_each_sched_entity(se, cfs_rq) {
 		update_curr(cfs_rq);
 
 		if (!se->on_rq) {
@@ -8286,16 +8287,15 @@ static void dequeue_hierarchy(struct tas
 	bool task_sleep = flags & DEQUEUE_SLEEP;
 	bool task_delayed = flags & DEQUEUE_DELAYED;
 	bool task_throttled = flags & DEQUEUE_THROTTLE;
-	int h_nr_runnable = 0;
 	int h_nr_idle = task_has_idle_policy(p);
+	int h_nr_runnable = 0;
+	struct cfs_rq *cfs_rq;
 	bool dequeue = true;
 
 	if (task_sleep || task_delayed || !se->sched_delayed)
 		h_nr_runnable = 1;
 
-	for_each_sched_entity(se) {
-		struct cfs_rq *cfs_rq = cfs_rq_of(se);
-
+	for_each_sched_entity(se, cfs_rq) {
 		update_curr(cfs_rq);
 
 		if (dequeue) {
@@ -11557,8 +11557,7 @@ static void update_cfs_rq_h_load(struct
 		return;
 
 	WRITE_ONCE(cfs_rq->h_load_next, NULL);
-	for_each_sched_entity(se) {
-		cfs_rq = cfs_rq_of(se);
+	for_each_sched_entity(se, cfs_rq) {
 		WRITE_ONCE(cfs_rq->h_load_next, se);
 		if (cfs_rq->last_h_load_update == now)
 			break;
@@ -15237,9 +15236,9 @@ static inline void task_tick_core(struct
 static void se_fi_update(const struct sched_entity *se, unsigned int fi_seq,
 			 bool forceidle)
 {
-	for_each_sched_entity(se) {
-		struct cfs_rq *cfs_rq = cfs_rq_of(se);
+	struct cfs_rq *cfs_rq;
 
+	for_each_sched_entity(se, cfs_rq) {
 		if (forceidle) {
 			if (cfs_rq->forceidle_seq == fi_seq)
 				break;
@@ -15317,10 +15316,8 @@ static void task_tick_fair(struct rq *rq
 		unsigned long weight = NICE_0_LOAD;
 		struct cfs_rq *cfs_rq;
 
-		for_each_sched_entity(se) {
-			cfs_rq = cfs_rq_of(se);
+		for_each_sched_entity(se, cfs_rq) {
 			entity_tick(cfs_rq, se, hrtick);
-
 			weight = __calc_prop_weight(cfs_rq, se, weight);
 		}
 
@@ -15402,9 +15399,7 @@ static void propagate_entity_cfs_rq(stru
 	/* Start to propagate at parent */
 	se = se->parent;
 
-	for_each_sched_entity(se) {
-		cfs_rq = cfs_rq_of(se);
-
+	for_each_sched_entity(se, cfs_rq) {
 		update_load_avg(cfs_rq, se, UPDATE_TG);
 
 		if (!cfs_rq_pelt_clock_throttled(cfs_rq))
@@ -15511,9 +15506,7 @@ static void set_next_task_fair(struct rq
 	if (on_rq)
 		__dequeue_entity(cfs_rq, se);
 
-	for_each_sched_entity(se) {
-		cfs_rq = cfs_rq_of(se);
-
+	for_each_sched_entity(se, cfs_rq) {
 		if (!IS_ENABLED(CONFIG_FAIR_GROUP_SCHED) ||
 		    !first || !cfs_rq->h_curr)
 			set_next_entity(cfs_rq, se);
@@ -15720,13 +15713,14 @@ static int __sched_group_set_shares(stru
 	for_each_possible_cpu(i) {
 		struct rq *rq = cpu_rq(i);
 		struct sched_entity *se = tg_se(tg, i);
+		struct cfs_rq *cfs_rq;
 		struct rq_flags rf;
 
 		/* Propagate contribution to hierarchy */
 		rq_lock_irqsave(rq, &rf);
 		update_rq_clock(rq);
-		for_each_sched_entity(se) {
-			update_load_avg(cfs_rq_of(se), se, UPDATE_TG);
+		for_each_sched_entity(se, cfs_rq) {
+			update_load_avg(cfs_rq, se, UPDATE_TG);
 			update_cfs_group(se);
 		}
 		rq_unlock_irqrestore(rq, &rf);
@@ -15773,6 +15767,7 @@ int sched_group_set_idle(struct task_gro
 		struct sched_entity *se = tg_se(tg, i);
 		struct cfs_rq *grp_cfs_rq = tg_cfs_rq(tg, i);
 		bool was_idle = cfs_rq_is_idle(grp_cfs_rq);
+		struct cfs_rq *cfs_rq;
 		long idle_task_delta;
 		struct rq_flags rf;
 
@@ -15787,9 +15782,7 @@ int sched_group_set_idle(struct task_gro
 		if (!cfs_rq_is_idle(grp_cfs_rq))
 			idle_task_delta *= -1;
 
-		for_each_sched_entity(se) {
-			struct cfs_rq *cfs_rq = cfs_rq_of(se);
-
+		for_each_sched_entity(se, cfs_rq) {
 			if (!se->on_rq)
 				break;
 

[PATCH v2 3/4] sched/fair: Extend for_each_sched_entity() with a back-link

[Peter Zijlstra]

Leave a trail of bread crumbs, such that we can find our way back down the
hierarchy. No actual users yet, but split out because its a bit tricky.

Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
---
 kernel/sched/fair.c  |   14 +++++++++++---
 kernel/sched/sched.h |    1 +
 2 files changed, 12 insertions(+), 3 deletions(-)

--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -318,8 +318,13 @@ const struct sched_class fair_sched_clas
 #ifdef CONFIG_FAIR_GROUP_SCHED
 
 /* Walk up scheduling entities hierarchy */
-#define for_each_sched_entity(se, cfs_rq)				\
-	for (; (se) && ((cfs_rq) = cfs_rq_of(se)); (se) = (se)->parent)
+#define for_each_sched_entity(se, cfs_rq)					\
+	for (struct sched_entity *_BL = NULL;					\
+	     (se) && ((cfs_rq) = cfs_rq_of(se), (cfs_rq)->backlink = _BL, true);\
+	     (se) = (se)->parent, _BL = (se))
+
+#define for_each_sched_entity_bl(se, cfs_rq) \
+	for (; ((se) = (cfs_rq)->backlink); (cfs_rq) = group_cfs_rq(se))
 
 static inline bool list_add_leaf_cfs_rq(struct cfs_rq *cfs_rq)
 {
@@ -456,6 +461,9 @@ static int se_is_idle(struct sched_entit
 #define for_each_sched_entity(se, cfs_rq) \
 	for (; (se) && ((cfs_rq) = cfs_rq_of(se)); (se) = NULL)
 
+#define for_each_sched_entity_bl(se, cfs_rq) \
+	for (; ((se) = NULL);)
+
 static inline bool list_add_leaf_cfs_rq(struct cfs_rq *cfs_rq)
 {
 	return true;
@@ -15233,7 +15241,7 @@ static inline void task_tick_core(struct
 /*
  * se_fi_update - Update the cfs_rq->zero_vruntime_fi in a CFS hierarchy if needed.
  */
-static void se_fi_update(const struct sched_entity *se, unsigned int fi_seq,
+static void se_fi_update(struct sched_entity *se, unsigned int fi_seq,
 			 bool forceidle)
 {
 	struct cfs_rq *cfs_rq;
--- a/kernel/sched/sched.h
+++ b/kernel/sched/sched.h
@@ -726,6 +726,7 @@ struct cfs_rq {
 	unsigned long		tg_runnable_avg_contrib;
 	long			propagate;
 	long			prop_runnable_sum;
+	struct sched_entity	*backlink;
 
 	/*
 	 *   h_load = weight * f(tg)

[PATCH v2 4/4] sched/fair: Rework/fix task_h_load()

[Peter Zijlstra]

There are a number of issues with task_h_load():

 - its hierarchy traversal is racy to the point of being broken; where
   originally it was meant to be used under rq->lock, but lacking an assertion
   for that fact, its use spread and violated this. The result is that the
   back-link state is prone to races.

 - it is rate-limited on jiffies, which is HZ, not the underlying PELT decay.

 - since its update is tied to task_h_load() usage, the cfs_rq->h_load numbers are
   not often 'up-to-date', rendering their output in sched/debug near useless.

Rework the whole thing to keep a more up-to-date and less broken cfs_rq->h_load
number.

Move the back-link tracking into for_each_sched_entity(), such that any such
loop sets up a path back. Use this to (optionally) re-compute cfs_rq->h_load on
enqueue, dequeue, set_next and tick, all sites that hold rq->lock.

This ensures that 'active' cgroups have reasonably up-to-date cfs_rq->h_load.
Additionally, have __update_blocked_fair() update cfs_rq->h_load for all
cgroups.

Finally, replace the jiffy rate-limit with one that is tied to the PELT decay.

Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
---
 kernel/sched/fair.c  |  117 +++++++++++++++++++++++++++++++++------------------
 kernel/sched/pelt.h  |    7 +++
 kernel/sched/sched.h |    1 
 3 files changed, 84 insertions(+), 41 deletions(-)

--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -5755,6 +5755,50 @@ static inline bool skip_blocked_update(s
 	return true;
 }
 
+static inline void __update_cfs_rq_h_load(struct cfs_rq *cfs_rq,
+					  struct sched_entity *se,
+					  struct cfs_rq *p_cfs_rq)
+{
+	unsigned long load = cfs_rq->avg.load_avg;
+
+	if (cfs_rq != &cfs_rq->rq->cfs) {
+		/*
+		 * These last two arguments can be NULL when used outside of
+		 * the for_each_sched_entity() hierarchy iteration. Like in
+		 * __update_blocked_fair() where leaf_cfs_rq_list is iterated
+		 * instead.
+		 */
+		if (!se)
+			se = &container_of(cfs_rq, struct cfs_tg_state, cfs_rq)->se;
+		if (!p_cfs_rq)
+			p_cfs_rq = cfs_rq_of(se);
+
+		load = p_cfs_rq->h_load;
+		load = div64_ul(load * se->avg.load_avg,
+				p_cfs_rq->avg.load_avg + 1);
+	}
+
+	WRITE_ONCE(cfs_rq->h_load, load);
+}
+
+static inline bool update_cfs_rq_h_load(struct cfs_rq *cfs_rq,
+					struct sched_entity *se,
+					struct cfs_rq *p_cfs_rq)
+{
+	/*
+	 * Mask out the segment bits, if the remaining bits match, then there
+	 * hasn't been a decay since the last time.
+	 */
+	if ((cfs_rq->last_h_load_update & ~PELT_SEGMENT_MASK) ==
+	    (cfs_rq->avg.last_update_time & ~PELT_SEGMENT_MASK))
+		return false;
+
+	__update_cfs_rq_h_load(cfs_rq, se, p_cfs_rq);
+
+	cfs_rq->last_h_load_update = cfs_rq->avg.last_update_time;
+	return true;
+}
+
 #else /* !CONFIG_FAIR_GROUP_SCHED: */
 
 static inline void update_tg_load_avg(struct cfs_rq *cfs_rq) {}
@@ -5768,6 +5812,10 @@ static inline int propagate_entity_load_
 
 static inline void add_tg_cfs_propagate(struct cfs_rq *cfs_rq, long runnable_sum) {}
 
+static inline bool update_cfs_rq_h_load(struct cfs_rq *cfs_rq,
+					struct sched_entity *se,
+					struct cfs_rq *p_cfs_rq) { return false; }
+
 #endif /* !CONFIG_FAIR_GROUP_SCHED */
 
 #ifdef CONFIG_NO_HZ_COMMON
@@ -8199,6 +8247,9 @@ static unsigned long enqueue_hierarchy(s
 		flags = ENQUEUE_WAKEUP;
 	}
 
+	for_each_sched_entity_bl(se, cfs_rq)
+		update_cfs_rq_h_load(group_cfs_rq(se), se, cfs_rq);
+
 	return weight;
 }
 
@@ -8330,6 +8381,9 @@ static void dequeue_hierarchy(struct tas
 		flags |= DEQUEUE_SLEEP;
 		flags &= ~(DEQUEUE_DELAYED | DEQUEUE_SPECIAL);
 	}
+
+	for_each_sched_entity_bl(se, cfs_rq)
+		update_cfs_rq_h_load(group_cfs_rq(se), se, cfs_rq);
 }
 
 /*
@@ -11547,51 +11601,23 @@ static bool __update_blocked_fair(struct
 			*done = false;
 	}
 
-	return decayed;
-}
-
-/*
- * Compute the hierarchical load factor for cfs_rq and all its ascendants.
- * This needs to be done in a top-down fashion because the load of a child
- * group is a fraction of its parents load.
- */
-static void update_cfs_rq_h_load(struct cfs_rq *cfs_rq)
-{
-	struct sched_entity *se = cfs_rq_se(cfs_rq);
-	unsigned long now = jiffies;
-	unsigned long load;
-
-	if (cfs_rq->last_h_load_update == now)
-		return;
-
-	WRITE_ONCE(cfs_rq->h_load_next, NULL);
-	for_each_sched_entity(se, cfs_rq) {
-		WRITE_ONCE(cfs_rq->h_load_next, se);
-		if (cfs_rq->last_h_load_update == now)
-			break;
-	}
-
-	if (!se) {
-		cfs_rq->h_load = cfs_rq_load_avg(cfs_rq);
-		cfs_rq->last_h_load_update = now;
-	}
+	/*
+	 * The above (forward) leaf_cfs_rq_list traversal will have done
+	 * update_cfs_rq_load_avg() in a bottom-up fashion. Now iterate the
+	 * list backwards, such that we're ensured to have visited every
+	 * parent of the current group to update h_load in a top-down fashion.
+	 */
+	list_for_each_entry_reverse(cfs_rq, &rq->leaf_cfs_rq_list, leaf_cfs_rq_list)
+		update_cfs_rq_h_load(cfs_rq, NULL, NULL);
 
-	while ((se = READ_ONCE(cfs_rq->h_load_next)) != NULL) {
-		load = cfs_rq->h_load;
-		load = div64_ul(load * se->avg.load_avg,
-				cfs_rq_load_avg(cfs_rq) + 1);
-		cfs_rq = group_cfs_rq(se);
-		cfs_rq->h_load = load;
-		cfs_rq->last_h_load_update = now;
-	}
+	return decayed;
 }
 
 static unsigned long task_h_load(struct task_struct *p)
 {
 	struct cfs_rq *cfs_rq = task_cfs_rq(p);
 
-	update_cfs_rq_h_load(cfs_rq);
-	return div64_ul(p->se.avg.load_avg * cfs_rq->h_load,
+	return div64_ul(p->se.avg.load_avg * READ_ONCE(cfs_rq->h_load),
 			cfs_rq_load_avg(cfs_rq) + 1);
 }
 #else /* !CONFIG_FAIR_GROUP_SCHED: */
@@ -15331,6 +15357,11 @@ static void task_tick_fair(struct rq *rq
 
 		se = &curr->se;
 		reweight_eevdf(cfs_rq, se, weight, se->on_rq);
+
+		if (!hrtick) {
+			for_each_sched_entity_bl(se, cfs_rq)
+				update_cfs_rq_h_load(group_cfs_rq(se), se, cfs_rq);
+		}
 	}
 
 	if (hrtick)
@@ -15545,11 +15576,15 @@ static void set_next_task_fair(struct rq
 		 */
 		list_move(&se->group_node, &rq->cfs_tasks);
 	}
-	if (!first)
-		return;
 
 	WARN_ON_ONCE(se->sched_delayed);
 
+	for_each_sched_entity_bl(se, cfs_rq)
+		update_cfs_rq_h_load(group_cfs_rq(se), se, cfs_rq);
+
+	if (!first)
+		return;
+
 	update_misfit_status(p, rq);
 	sched_fair_update_stop_tick(rq, p);
 
@@ -15731,6 +15766,8 @@ static int __sched_group_set_shares(stru
 			update_load_avg(cfs_rq, se, UPDATE_TG);
 			update_cfs_group(se);
 		}
+		for_each_sched_entity_bl(se, cfs_rq)
+			update_cfs_rq_h_load(group_cfs_rq(se), se, cfs_rq);
 		rq_unlock_irqrestore(rq, &rf);
 	}
 
--- a/kernel/sched/pelt.h
+++ b/kernel/sched/pelt.h
@@ -5,6 +5,13 @@
 
 #include "sched-pelt.h"
 
+/*
+ * Pelt uses apprixmate 'us' as ns/1024; and then uses time segments of 1024
+ * 'us'. As a result each segment is in fact '1<<20' ns.
+ */
+#define PELT_SEGMENT_NS		(1<<20)
+#define PELT_SEGMENT_MASK	(PELT_SEGMENT_NS-1)
+
 int __update_load_avg_blocked_se(u64 now, struct sched_entity *se);
 int __update_load_avg_se(u64 now, struct cfs_rq *cfs_rq, struct sched_entity *se);
 int __update_load_avg_cfs_rq(u64 now, struct cfs_rq *cfs_rq);
--- a/kernel/sched/sched.h
+++ b/kernel/sched/sched.h
@@ -736,7 +736,6 @@ struct cfs_rq {
 	 */
 	unsigned long		h_load;
 	u64			last_h_load_update;
-	struct sched_entity	*h_load_next;
 
 	struct rq		*rq;	/* CPU runqueue to which this cfs_rq is attached */
 

Re: [PATCH v2 4/4] sched/fair: Rework/fix task_h_load()

[Kayra Cizmeci]

Hi Peter,

(Fun Stuff):

> @@ -15731,6 +15766,8 @@ static int __sched_group_set_shares(stru
>  			update_load_avg(cfs_rq, se, UPDATE_TG);
>  			update_cfs_group(se);
>  		}
> +		for_each_sched_entity_bl(se, cfs_rq)
> +			update_cfs_rq_h_load(group_cfs_rq(se), se, cfs_rq);
>  		rq_unlock_irqrestore(rq, &rf);
>  	}
>

So, the code is this:
	#define for_each_sched_entity(se, cfs_rq)					\
		for (struct sched_entity *_BL = NULL;					\
		     (se) && ((cfs_rq) = cfs_rq_of(se), (cfs_rq)->backlink = _BL, true);\
		     (se) = (se)->parent, _BL = (se))
	
	#define for_each_sched_entity_bl(se, cfs_rq) \
		for (; ((se) = (cfs_rq)->backlink); (cfs_rq) = group_cfs_rq(se))


(While writing this, a suitcase tried to assassinate me by falling from top of the closet,
what follows after this part may be the symptoms of my brain-damage.)

Let's say we have a *thing* like this:

  +----+    +----+    +------+
  |se_a| -> |rq_a| -> |task_a|
  +----+    +----+    +------+
     |
     |
     |
     V
  +----+    +----+     +------+
  |se_b| -> |rq_b|  -> |task_b|
  +----+    +----+     +------+

When we start as task_b, everything goes well. Both groups are updated.
On task_a too, only se_a is updated. 

But when we start as se_a root's backlink is NULL so we don't update anything.
While on se_b rq_a's backlink is NULL and update se_a but not ourselfes.

I don't think this is that of a problem tho, and
I could be missing something.

(Ultra-Fun Stuff (Maybe)):

Also, I saw you making an Assisted-by joke yesterday so... 

Assisted-by: Fingers (Typing)
Assisted-by: Luck (Born)
Assisted-by: Computer (IDK)
Assisted-by: Knowledge (Knowledge)
Assisted-by: Linux Itself (Kernel)
Assisted-by: EEVDF (I mean...)
Assisted-by: Water
Assisted-by: Energy (I don't have any ;<)
Assisted-by: Sun
Assisted-by: Universe
Assisted-by: Editor
Assisted-by: LKML
Assisted-by: LWN
Assisted-by: Music (Vibes)
Assisted-by: Heart (Broken ;<)
Assisted-by: Brain (Damaged a bit)

There could be more :p

Thanks,
Kayra

Re: [PATCH v2 4/4] sched/fair: Rework/fix task_h_load()

[K Prateek Nayak]

Hello Kayra,

On 9/29/2026 11:16 PM, Kayra Cizmeci wrote:
> Hi Peter,
> 
> (Fun Stuff):
> 
>> @@ -15731,6 +15766,8 @@ static int __sched_group_set_shares(stru
>>  			update_load_avg(cfs_rq, se, UPDATE_TG);
>>  			update_cfs_group(se);
>>  		}
>> +		for_each_sched_entity_bl(se, cfs_rq)
>> +			update_cfs_rq_h_load(group_cfs_rq(se), se, cfs_rq);
>>  		rq_unlock_irqrestore(rq, &rf);
>>  	}
>>
> 
> So, the code is this:
> 	#define for_each_sched_entity(se, cfs_rq)					\
> 		for (struct sched_entity *_BL = NULL;					\
> 		     (se) && ((cfs_rq) = cfs_rq_of(se), (cfs_rq)->backlink = _BL, true);\
> 		     (se) = (se)->parent, _BL = (se))
> 	
> 	#define for_each_sched_entity_bl(se, cfs_rq) \
> 		for (; ((se) = (cfs_rq)->backlink); (cfs_rq) = group_cfs_rq(se))
> 
> 
> (While writing this, a suitcase tried to assassinate me by falling from top of the closet,
> what follows after this part may be the symptoms of my brain-damage.)
> 
> Let's say we have a *thing* like this:
> 
>   +----+    +----+    +------+
>   |se_a| -> |rq_a| -> |task_a|
>   +----+    +----+    +------+
>      |
>      |
>      |
>      V
>   +----+    +----+     +------+
>   |se_b| -> |rq_b|  -> |task_b|
>   +----+    +----+     +------+

I'm having a super hard time understanding this hierarchy.

Is it like:

    root
    /  \
   A    B
   |    |
 task   task

or something like:

  root
   |
   A
   |
   B
   |
  task 

?

> 
> When we start as task_b, everything goes well. Both groups are updated.
> On task_a too, only se_a is updated. 

I'm assuming the hierarchy is like the latter then if traversal from
B updates A.

> 
> But when we start as se_a root's backlink is NULL so we don't update anything.
> While on se_b rq_a's backlink is NULL and update se_a but not ourselfes.

So for that specific section you've highlighted from Peter's patch,
in __sched_group_set_shares(), we first do a:

    for_each_sched_entity(se) {
        update_load_avg(cfs_rq_of(se), se, UPDATE_TG);
        update_cfs_group(se);
    }

That sets up backlink going until se->parent whose group_cfs_rq() is
the cfs_rq of tg_se(B) aka the cfs_rq just above the group whose shares
were altered.

Then we do:

    for_each_sched_entity_bl(se, cfs_rq)
        update_cfs_rq_h_load(group_cfs_rq(se), se, cfs_rq);

Which updates the h_load all the way from the root until the cfs_rq of
the cgroup we altered.

In case of:

  root
   |
   A
   |
   B*

  *shares of cgroup is updated

If we update shares of B (aka tg_se(B)), we update the h_load
until the cfs_rq_of(tg_se(B)) which is till tg_cfs_rq(A).

Now if you have:

   root
    |
    A
   / \
 *B   C
      | \
      D  E

Yes,d you'll still update h_load for only A and you can have stale
h_load for C, D, and E, and for all the tasks queued below them.

Since full propagation is expensive, we do those propagation lazily
when the task is picked, enqueued, or dequeued

Note: We cannot propagate this up further because we have not yet done an
update_load_avg() for the cfa_rq(s) in rest of the hierarchy. Next reweight
will see the correct h_load starting from A and propagate it further when
needed.

Was that the problem you were talking about or did I totally confuse this
with something else?
> I don't think this is that of a problem tho, and
> I could be missing something.

I don't even see the problem. Maybe I need glasses :-)

-- 
Thanks and Regards,
Prateek

Re: [PATCH v2 4/4] sched/fair: Rework/fix task_h_load()

[Kayra Cizmeci]

Hi Prateek,

> I'm having a super hard time understanding this hierarchy.
I'm new to drawing these sorry. Yes, it's like the second one.

> Yes,d you'll still update h_load for only A and you can have stale
> h_load for C, D, and E, and for all the tasks queued below them.

> Since full propagation is expensive, we do those propagation lazily
> when the task is picked, enqueued, or dequeued

> Note: We cannot propagate this up further because we have not yet done an
> update_load_avg() for the cfa_rq(s) in rest of the hierarchy. Next reweight
> will see the correct h_load starting from A and propagate it further when
> needed.

> Was that the problem you were talking about or did I totally confuse this
> with something else?

Yes, I was talking about that. Because there are only one use case
with tg. I'm not sure the NULL is intentional for that case.

But I can't know for sure Peter can say that. Since..
He wrote the series. :>.

> > I don't think this is that of a problem tho, and
> > I could be missing something.

> I don't even see the problem. Maybe I need glasses :-)

Meh. If you need glasses I need an eye surgery or something.

Thanks,
Kayra

Re: [PATCH v2 4/4] sched/fair: Rework/fix task_h_load()

[Peter Zijlstra]

On Wed, Sep 30, 2026 at 06:46:38AM +0530, K Prateek Nayak wrote:
> Hello Kayra,
> 
> On 9/29/2026 11:16 PM, Kayra Cizmeci wrote:
> > Hi Peter,
> > 
> > (Fun Stuff):
> > 
> >> @@ -15731,6 +15766,8 @@ static int __sched_group_set_shares(stru
> >>  			update_load_avg(cfs_rq, se, UPDATE_TG);
> >>  			update_cfs_group(se);
> >>  		}
> >> +		for_each_sched_entity_bl(se, cfs_rq)
> >> +			update_cfs_rq_h_load(group_cfs_rq(se), se, cfs_rq);
> >>  		rq_unlock_irqrestore(rq, &rf);
> >>  	}
> >>
> > 
> > So, the code is this:
> > 	#define for_each_sched_entity(se, cfs_rq)					\
> > 		for (struct sched_entity *_BL = NULL;					\
> > 		     (se) && ((cfs_rq) = cfs_rq_of(se), (cfs_rq)->backlink = _BL, true);\
> > 		     (se) = (se)->parent, _BL = (se))
> > 	
> > 	#define for_each_sched_entity_bl(se, cfs_rq) \
> > 		for (; ((se) = (cfs_rq)->backlink); (cfs_rq) = group_cfs_rq(se))
> > 
> > 
> > (While writing this, a suitcase tried to assassinate me by falling from top of the closet,
> > what follows after this part may be the symptoms of my brain-damage.)

'Expect the unexpected!' :-)

Just to share the pictures I always noodle while doing this...

Given a cgroup hierarchy like:

      Root
      /  \
     A    B
     |    |
     AA   BA
     |    |
     t1   t2

We have:

			 rq->cfs
			 /     \
	    cfs_rq-A - se-A   se-B - cfs_rq-B
	       |                        |
  cfs_rq-AA - se-AA		       se-BA - cfs_rq-BA
     |                                            |
    se-1 - task_1                                se-2 - task_2


Where:

 - cfs_rq_of(se)    - gives the cfs_rq se is enqueued on, iow. up one level
                      example: cfs_rq_of(se-AA) := cfs_rq-A

 - group_cfs_rq(se) - gives the cfs_rq associated with the se, iow. sideways
                      example: group_cfs_rq(se-AA) := cfs_rq-AA

(I normally denote these as little arrows in the graph, but ASCII is a
little more rigid than pencil and paper.)


> > When we start as task_b, everything goes well. Both groups are updated.
> > On task_a too, only se_a is updated. 
> 
> I'm assuming the hierarchy is like the latter then if traversal from
> B updates A.
> 
> > 
> > But when we start as se_a root's backlink is NULL so we don't update anything.
> > While on se_b rq_a's backlink is NULL and update se_a but not ourselfes.
> 
> So for that specific section you've highlighted from Peter's patch,
> in __sched_group_set_shares(), we first do a:
> 
>     for_each_sched_entity(se) {
>         update_load_avg(cfs_rq_of(se), se, UPDATE_TG);
>         update_cfs_group(se);
>     }
> 
> That sets up backlink going until se->parent whose group_cfs_rq() is
> the cfs_rq of tg_se(B) aka the cfs_rq just above the group whose shares
> were altered.
> 
> Then we do:
> 
>     for_each_sched_entity_bl(se, cfs_rq)
>         update_cfs_rq_h_load(group_cfs_rq(se), se, cfs_rq);
> 
> Which updates the h_load all the way from the root until the cfs_rq of
> the cgroup we altered.
> 
> In case of:
> 
>   root
>    |
>    A
>    |
>    B*
> 
>   *shares of cgroup is updated
> 
> If we update shares of B (aka tg_se(B)), we update the h_load
> until the cfs_rq_of(tg_se(B)) which is till tg_cfs_rq(A).
> 
> Now if you have:
> 
>    root
>     |
>     A
>    / \
>  *B   C
>       | \
>       D  E
> 
> Yes,d you'll still update h_load for only A and you can have stale
> h_load for C, D, and E, and for all the tasks queued below them.
> 
> Since full propagation is expensive, we do those propagation lazily
> when the task is picked, enqueued, or dequeued
> 
> Note: We cannot propagate this up further because we have not yet done an
> update_load_avg() for the cfa_rq(s) in rest of the hierarchy. Next reweight
> will see the correct h_load starting from A and propagate it further when
> needed.
> 
> Was that the problem you were talking about or did I totally confuse this
> with something else?

Right, so we only update the groups up from where we start. Ideally we'd
also update the whole affected subtree, but as Prateek says, that might
be expensive, and it will be updated on-demand later.

Re: [PATCH v2 4/4] sched/fair: Rework/fix task_h_load()

[Kayra Cizmeci]

Hi Peter,

I checked everything *again* to make sure;

> -	if (!se) {
> -		cfs_rq->h_load = cfs_rq_load_avg(cfs_rq);
> -		cfs_rq->last_h_load_update = now;
> -	}
> +	/*
> +	 * The above (forward) leaf_cfs_rq_list traversal will have done
> +	 * update_cfs_rq_load_avg() in a bottom-up fashion. Now iterate the
> +	 * list backwards, such that we're ensured to have visited every
> +	 * parent of the current group to update h_load in a top-down fashion.
> +	 */
> +	list_for_each_entry_reverse(cfs_rq, &rq->leaf_cfs_rq_list, leaf_cfs_rq_list)
> +		update_cfs_rq_h_load(cfs_rq, NULL, NULL);


>  static unsigned long task_h_load(struct task_struct *p)
>  {
>  	struct cfs_rq *cfs_rq = task_cfs_rq(p);
>  
> -	update_cfs_rq_h_load(cfs_rq);
> -	return div64_ul(p->se.avg.load_avg * cfs_rq->h_load,
> +	return div64_ul(p->se.avg.load_avg * READ_ONCE(cfs_rq->h_load),
>  			cfs_rq_load_avg(cfs_rq) + 1);
>  }

Is updating the root less often intentional? 
Or am I missing something and we update the root more than the old code?

Also, there's a typo:

> + * Pelt uses apprixmate 'us' as ns/1024; and then uses time segments of 1024
> + * 'us'. As a result each segment is in fact '1<<20' ns.

'apprixmate' :-).

Thanks,
Kayra

Re: [PATCH v2 4/4] sched/fair: Rework/fix task_h_load()

[Peter Zijlstra]

On Wed, Sep 30, 2026 at 01:20:43PM +0300, Kayra Cizmeci wrote:
> Hi Peter,
> 
> I checked everything *again* to make sure;
> 
> > -	if (!se) {
> > -		cfs_rq->h_load = cfs_rq_load_avg(cfs_rq);
> > -		cfs_rq->last_h_load_update = now;
> > -	}
> > +	/*
> > +	 * The above (forward) leaf_cfs_rq_list traversal will have done
> > +	 * update_cfs_rq_load_avg() in a bottom-up fashion. Now iterate the
> > +	 * list backwards, such that we're ensured to have visited every
> > +	 * parent of the current group to update h_load in a top-down fashion.
> > +	 */
> > +	list_for_each_entry_reverse(cfs_rq, &rq->leaf_cfs_rq_list, leaf_cfs_rq_list)
> > +		update_cfs_rq_h_load(cfs_rq, NULL, NULL);
> 
> 
> >  static unsigned long task_h_load(struct task_struct *p)
> >  {
> >  	struct cfs_rq *cfs_rq = task_cfs_rq(p);
> >  
> > -	update_cfs_rq_h_load(cfs_rq);
> > -	return div64_ul(p->se.avg.load_avg * cfs_rq->h_load,
> > +	return div64_ul(p->se.avg.load_avg * READ_ONCE(cfs_rq->h_load),
> >  			cfs_rq_load_avg(cfs_rq) + 1);
> >  }
> 
> Is updating the root less often intentional? 
> Or am I missing something and we update the root more than the old code?

You're referring to the removal of update_cfs_rq_h_load() here? That was
the whole purpose of the patch. The callers of task_h_load() do not (in
general) hold rq->lock, and thus update_cfs_rq_h_load() is unserialized
and broken.

> Also, there's a typo:
> 
> > + * Pelt uses apprixmate 'us' as ns/1024; and then uses time segments of 1024
> > + * 'us'. As a result each segment is in fact '1<<20' ns.
> 
> 'apprixmate' :-).

Some day I might learn to type :-)

Re: [PATCH v2 4/4] sched/fair: Rework/fix task_h_load()

[Kayra Cizmeci]

> > Hi Peter,
> > 
> > I checked everything *again* to make sure;
> > 
> > > -	if (!se) {
> > > -		cfs_rq->h_load = cfs_rq_load_avg(cfs_rq);
> > > -		cfs_rq->last_h_load_update = now;
> > > -	}
> > > +	/*
> > > +	 * The above (forward) leaf_cfs_rq_list traversal will have done
> > > +	 * update_cfs_rq_load_avg() in a bottom-up fashion. Now iterate the
> > > +	 * list backwards, such that we're ensured to have visited every
> > > +	 * parent of the current group to update h_load in a top-down fashion.
> > > +	 */
> > > +	list_for_each_entry_reverse(cfs_rq, &rq->leaf_cfs_rq_list, leaf_cfs_rq_list)
> > > +		update_cfs_rq_h_load(cfs_rq, NULL, NULL);
> > 
> > 
> > >  static unsigned long task_h_load(struct task_struct *p)
> > >  {
> > >  	struct cfs_rq *cfs_rq = task_cfs_rq(p);
> > >  
> > > -	update_cfs_rq_h_load(cfs_rq);
> > > -	return div64_ul(p->se.avg.load_avg * cfs_rq->h_load,
> > > +	return div64_ul(p->se.avg.load_avg * READ_ONCE(cfs_rq->h_load),
> > >  			cfs_rq_load_avg(cfs_rq) + 1);
> > >  }
> > 
> > Is updating the root less often intentional? 
> > Or am I missing something and we update the root more than the old code?

> You're referring to the removal of update_cfs_rq_h_load() here? That was
> the whole purpose of the patch. The callers of task_h_load() do not (in
> general) hold rq->lock, and thus update_cfs_rq_h_load() is unserialized
> and broken.

In the old code we were updating root when we go fully up and if it hadn't been
updated it already.

But now, that block is deleted. update_cfs_rq_h_load() is only called from this
other list_for_each_entry_reverse() block. 

> Also, there's a typo:
> 
> > + * Pelt uses apprixmate 'us' as ns/1024; and then uses time segments of 1024
> > + * 'us'. As a result each segment is in fact '1<<20' ns.
> 
> 'apprixmate' :-).

> Some day I might learn to type :-)

My situation is worse than yours ;-)