[PATCH v2 0/2] sched/fair: optimize and simplify rq leaf_cfs_rq_list

[PATCH v2 0/2] sched/fair: optimize and simplify rq leaf_cfs_rq_list

[Chengming Zhou]

Hi,

This v2 is based on [1], which try to not put cfs_rqs in throttled_hierarchy
on the rq leaf_cfs_rq_list, simplify the leaf_cfs_rq_list maintenance and
optimize the periodic load decay.

Vincent suggested moving throttled_hierarchy() outside list_add_leaf_cfs_rq()
because the task will not be added in this case which is quite misleading.

When do that moving in propagate_entity_cfs_rq(), I found it has problem
with propagation upwards. So add the fix in the first patch to be easier
to backport, please see the details in its commit message.

[1] https://lore.kernel.org/all/20220427160544.40309-1-zhouchengming@bytedance.com/

Chengming Zhou (2):
  sched/fair: fix propagate during synchronous attach/detach
  sched/fair: optimize and simplify rq leaf_cfs_rq_list

 kernel/sched/fair.c | 83 +++++++++++----------------------------------
 1 file changed, 20 insertions(+), 63 deletions(-)

-- 
2.36.1

[PATCH v2 1/2] sched/fair: fix propagate during synchronous attach/detach

[Chengming Zhou]

When a task moves from/to a cfs_rq, we first detach/attach the load_avg
of se from/to that cfs_rq, then propagate the changes across the tg tree
to make it visible to the root, which did in update_load_avg().

But the current code will break when encountering a on_list cfs_rq,
can't propagate up to the root cfs_rq, that also mismatch with the
comment of propagate_entity_cfs_rq(), which says "Propagate the changes
of the sched_entity across the tg tree to make it visible to the root".

The second problem is that it won't update_load_avg() for throttled
cfs_rq, cause the load changes can't be propagated upwards.

    A
    |
    B  --> throttled cfs_rq
   /
  C

The prop_runnable_sum of C won't be propagated to B, so won't be
propagated to A.

Fixes: 0258bdfaff5b ("sched/fair: Fix unfairness caused by missing load decay")
Signed-off-by: Chengming Zhou <zhouchengming@bytedance.com>
---
 kernel/sched/fair.c | 10 ++--------
 1 file changed, 2 insertions(+), 8 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 523e548c8fdd..5276d05692e0 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -11303,14 +11303,8 @@ static void propagate_entity_cfs_rq(struct sched_entity *se)
 	for_each_sched_entity(se) {
 		cfs_rq = cfs_rq_of(se);
 
-		if (!cfs_rq_throttled(cfs_rq)){
-			update_load_avg(cfs_rq, se, UPDATE_TG);
-			list_add_leaf_cfs_rq(cfs_rq);
-			continue;
-		}
-
-		if (list_add_leaf_cfs_rq(cfs_rq))
-			break;
+		update_load_avg(cfs_rq, se, UPDATE_TG);
+		list_add_leaf_cfs_rq(cfs_rq);
 	}
 }
 #else
-- 
2.36.1

[PATCH v2 2/2] sched/fair: optimize and simplify rq leaf_cfs_rq_list

[Chengming Zhou]

We notice the rq leaf_cfs_rq_list has two problems when do bugfix
backports and some test profiling.

1. cfs_rqs under throttled subtree could be added to the list, and
   make their fully decayed ancestors on the list, even though not needed.

2. #1 also make the leaf_cfs_rq_list management complex and error prone,
   this is the list of related bugfix so far:

   commit 31bc6aeaab1d ("sched/fair: Optimize update_blocked_averages()")
   commit fe61468b2cbc ("sched/fair: Fix enqueue_task_fair warning")
   commit b34cb07dde7c ("sched/fair: Fix enqueue_task_fair() warning some more")
   commit 39f23ce07b93 ("sched/fair: Fix unthrottle_cfs_rq() for leaf_cfs_rq list")
   commit 0258bdfaff5b ("sched/fair: Fix unfairness caused by missing load decay")
   commit a7b359fc6a37 ("sched/fair: Correctly insert cfs_rq's to list on unthrottle")
   commit fdaba61ef8a2 ("sched/fair: Ensure that the CFS parent is added after unthrottling")
   commit 2630cde26711 ("sched/fair: Add ancestors of unthrottled undecayed cfs_rq")

commit 31bc6aeaab1d ("sched/fair: Optimize update_blocked_averages()")
delete every cfs_rq under throttled subtree from rq->leaf_cfs_rq_list,
and delete the throttled_hierarchy() test in update_blocked_averages(),
which optimized update_blocked_averages().

But those later bugfix add cfs_rqs under throttled subtree back to
rq->leaf_cfs_rq_list again, with their fully decayed ancestors, for
the integrity of rq->leaf_cfs_rq_list.

This patch takes another method, skip all cfs_rqs under throttled
hierarchy when list_add_leaf_cfs_rq(), to completely make cfs_rqs
under throttled subtree off the leaf_cfs_rq_list.

So we don't need to consider throttled related things in
enqueue_entity(), unthrottle_cfs_rq() and enqueue_task_fair(),
which simplify the code a lot. Also optimize update_blocked_averages()
since cfs_rqs under throttled hierarchy and their ancestors
won't be on the leaf_cfs_rq_list.

Signed-off-by: Chengming Zhou <zhouchengming@bytedance.com>
---
v2:
 - move throttled_hierarchy() outside list_add_leaf_cfs_rq(),
   suggested by Vincent.
---
 kernel/sched/fair.c | 77 ++++++++++++---------------------------------
 1 file changed, 20 insertions(+), 57 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 5276d05692e0..7438c1865109 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -4374,16 +4374,11 @@ enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
 		__enqueue_entity(cfs_rq, se);
 	se->on_rq = 1;
 
-	/*
-	 * When bandwidth control is enabled, cfs might have been removed
-	 * because of a parent been throttled but cfs->nr_running > 1. Try to
-	 * add it unconditionally.
-	 */
-	if (cfs_rq->nr_running == 1 || cfs_bandwidth_used())
-		list_add_leaf_cfs_rq(cfs_rq);
-
-	if (cfs_rq->nr_running == 1)
+	if (cfs_rq->nr_running == 1) {
 		check_enqueue_throttle(cfs_rq);
+		if (!throttled_hierarchy(cfs_rq))
+			list_add_leaf_cfs_rq(cfs_rq);
+	}
 }
 
 static void __clear_buddies_last(struct sched_entity *se)
@@ -4998,11 +4993,18 @@ void unthrottle_cfs_rq(struct cfs_rq *cfs_rq)
 	/* update hierarchical throttle state */
 	walk_tg_tree_from(cfs_rq->tg, tg_nop, tg_unthrottle_up, (void *)rq);
 
-	/* Nothing to run but something to decay (on_list)? Complete the branch */
 	if (!cfs_rq->load.weight) {
-		if (cfs_rq->on_list)
-			goto unthrottle_throttle;
-		return;
+		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)))
+				break;
+		}
+		goto unthrottle_throttle;
 	}
 
 	task_delta = cfs_rq->h_nr_running;
@@ -5040,31 +5042,12 @@ void unthrottle_cfs_rq(struct cfs_rq *cfs_rq)
 		/* end evaluation on encountering a throttled cfs_rq */
 		if (cfs_rq_throttled(qcfs_rq))
 			goto unthrottle_throttle;
-
-		/*
-		 * One parent has been throttled and cfs_rq removed from the
-		 * list. Add it back to not break the leaf list.
-		 */
-		if (throttled_hierarchy(qcfs_rq))
-			list_add_leaf_cfs_rq(qcfs_rq);
 	}
 
 	/* At this point se is NULL and we are at root level*/
 	add_nr_running(rq, task_delta);
 
 unthrottle_throttle:
-	/*
-	 * The cfs_rq_throttled() breaks in the above iteration can result in
-	 * incomplete leaf list maintenance, resulting in triggering the
-	 * assertion below.
-	 */
-	for_each_sched_entity(se) {
-		struct cfs_rq *qcfs_rq = cfs_rq_of(se);
-
-		if (list_add_leaf_cfs_rq(qcfs_rq))
-			break;
-	}
-
 	assert_list_leaf_cfs_rq(rq);
 
 	/* Determine whether we need to wake up potentially idle CPU: */
@@ -5719,13 +5702,6 @@ enqueue_task_fair(struct rq *rq, struct task_struct *p, int flags)
 		/* end evaluation on encountering a throttled cfs_rq */
 		if (cfs_rq_throttled(cfs_rq))
 			goto enqueue_throttle;
-
-               /*
-                * One parent has been throttled and cfs_rq removed from the
-                * list. Add it back to not break the leaf list.
-                */
-               if (throttled_hierarchy(cfs_rq))
-                       list_add_leaf_cfs_rq(cfs_rq);
 	}
 
 	/* At this point se is NULL and we are at root level*/
@@ -5749,21 +5725,6 @@ enqueue_task_fair(struct rq *rq, struct task_struct *p, int flags)
 		update_overutilized_status(rq);
 
 enqueue_throttle:
-	if (cfs_bandwidth_used()) {
-		/*
-		 * When bandwidth control is enabled; the cfs_rq_throttled()
-		 * breaks in the above iteration can result in incomplete
-		 * leaf list maintenance, resulting in triggering the assertion
-		 * below.
-		 */
-		for_each_sched_entity(se) {
-			cfs_rq = cfs_rq_of(se);
-
-			if (list_add_leaf_cfs_rq(cfs_rq))
-				break;
-		}
-	}
-
 	assert_list_leaf_cfs_rq(rq);
 
 	hrtick_update(rq);
@@ -11293,9 +11254,10 @@ static inline bool vruntime_normalized(struct task_struct *p)
  */
 static void propagate_entity_cfs_rq(struct sched_entity *se)
 {
-	struct cfs_rq *cfs_rq;
+	struct cfs_rq *cfs_rq = cfs_rq_of(se);
 
-	list_add_leaf_cfs_rq(cfs_rq_of(se));
+	if (!throttled_hierarchy(cfs_rq))
+		list_add_leaf_cfs_rq(cfs_rq);
 
 	/* Start to propagate at parent */
 	se = se->parent;
@@ -11304,7 +11266,8 @@ static void propagate_entity_cfs_rq(struct sched_entity *se)
 		cfs_rq = cfs_rq_of(se);
 
 		update_load_avg(cfs_rq, se, UPDATE_TG);
-		list_add_leaf_cfs_rq(cfs_rq);
+		if (!throttled_hierarchy(cfs_rq))
+			list_add_leaf_cfs_rq(cfs_rq);
 	}
 }
 #else
-- 
2.36.1

Re: [PATCH v2 2/2] sched/fair: optimize and simplify rq leaf_cfs_rq_list

[kernel test robot]

Hi Chengming,

Thank you for the patch! Yet something to improve:

[auto build test ERROR on tip/sched/core]
[also build test ERROR on tip/master linus/master v5.18 next-20220525]
[If your patch is applied to the wrong git tree, kindly drop us a note.
And when submitting patch, we suggest to use '--base' as documented in
https://git-scm.com/docs/git-format-patch]

url:    https://github.com/intel-lab-lkp/linux/commits/Chengming-Zhou/sched-fair-optimize-and-simplify-rq-leaf_cfs_rq_list/20220526-151850
base:   https://git.kernel.org/pub/scm/linux/kernel/git/tip/tip.git 991d8d8142cad94f9c5c05db25e67fa83d6f772a
config: powerpc-allnoconfig (https://download.01.org/0day-ci/archive/20220526/202205261617.YUT1ixQ8-lkp@intel.com/config)
compiler: powerpc-linux-gcc (GCC) 11.3.0
reproduce (this is a W=1 build):
        wget https://raw.githubusercontent.com/intel/lkp-tests/master/sbin/make.cross -O ~/bin/make.cross
        chmod +x ~/bin/make.cross
        # https://github.com/intel-lab-lkp/linux/commit/cb2b1810aeb3f8f290a932f3e625ab9df1110054
        git remote add linux-review https://github.com/intel-lab-lkp/linux
        git fetch --no-tags linux-review Chengming-Zhou/sched-fair-optimize-and-simplify-rq-leaf_cfs_rq_list/20220526-151850
        git checkout cb2b1810aeb3f8f290a932f3e625ab9df1110054
        # save the config file
        mkdir build_dir && cp config build_dir/.config
        COMPILER_INSTALL_PATH=$HOME/0day COMPILER=gcc-11.3.0 make.cross W=1 O=build_dir ARCH=powerpc SHELL=/bin/bash kernel/sched/

If you fix the issue, kindly add following tag where applicable
Reported-by: kernel test robot <lkp@intel.com>

All errors (new ones prefixed by >>):

   kernel/sched/fair.c:645:5: warning: no previous prototype for 'sched_update_scaling' [-Wmissing-prototypes]
     645 | int sched_update_scaling(void)
         |     ^~~~~~~~~~~~~~~~~~~~
   kernel/sched/fair.c: In function 'enqueue_entity':
>> kernel/sched/fair.c:4343:22: error: implicit declaration of function 'throttled_hierarchy' [-Werror=implicit-function-declaration]
    4343 |                 if (!throttled_hierarchy(cfs_rq))
         |                      ^~~~~~~~~~~~~~~~~~~
   kernel/sched/fair.c: At top level:
>> kernel/sched/fair.c:5484:19: error: static declaration of 'throttled_hierarchy' follows non-static declaration
    5484 | static inline int throttled_hierarchy(struct cfs_rq *cfs_rq)
         |                   ^~~~~~~~~~~~~~~~~~~
   kernel/sched/fair.c:4343:22: note: previous implicit declaration of 'throttled_hierarchy' with type 'int()'
    4343 |                 if (!throttled_hierarchy(cfs_rq))
         |                      ^~~~~~~~~~~~~~~~~~~
   kernel/sched/fair.c:5495:6: warning: no previous prototype for 'init_cfs_bandwidth' [-Wmissing-prototypes]
    5495 | void init_cfs_bandwidth(struct cfs_bandwidth *cfs_b) {}
         |      ^~~~~~~~~~~~~~~~~~
   kernel/sched/fair.c:11654:6: warning: no previous prototype for 'free_fair_sched_group' [-Wmissing-prototypes]
   11654 | void free_fair_sched_group(struct task_group *tg) { }
         |      ^~~~~~~~~~~~~~~~~~~~~
   kernel/sched/fair.c:11656:5: warning: no previous prototype for 'alloc_fair_sched_group' [-Wmissing-prototypes]
   11656 | int alloc_fair_sched_group(struct task_group *tg, struct task_group *parent)
         |     ^~~~~~~~~~~~~~~~~~~~~~
   kernel/sched/fair.c:11661:6: warning: no previous prototype for 'online_fair_sched_group' [-Wmissing-prototypes]
   11661 | void online_fair_sched_group(struct task_group *tg) { }
         |      ^~~~~~~~~~~~~~~~~~~~~~~
   kernel/sched/fair.c:11663:6: warning: no previous prototype for 'unregister_fair_sched_group' [-Wmissing-prototypes]
   11663 | void unregister_fair_sched_group(struct task_group *tg) { }
         |      ^~~~~~~~~~~~~~~~~~~~~~~~~~~
   cc1: some warnings being treated as errors


vim +/throttled_hierarchy +4343 kernel/sched/fair.c

  4263	
  4264	/*
  4265	 * MIGRATION
  4266	 *
  4267	 *	dequeue
  4268	 *	  update_curr()
  4269	 *	    update_min_vruntime()
  4270	 *	  vruntime -= min_vruntime
  4271	 *
  4272	 *	enqueue
  4273	 *	  update_curr()
  4274	 *	    update_min_vruntime()
  4275	 *	  vruntime += min_vruntime
  4276	 *
  4277	 * this way the vruntime transition between RQs is done when both
  4278	 * min_vruntime are up-to-date.
  4279	 *
  4280	 * WAKEUP (remote)
  4281	 *
  4282	 *	->migrate_task_rq_fair() (p->state == TASK_WAKING)
  4283	 *	  vruntime -= min_vruntime
  4284	 *
  4285	 *	enqueue
  4286	 *	  update_curr()
  4287	 *	    update_min_vruntime()
  4288	 *	  vruntime += min_vruntime
  4289	 *
  4290	 * this way we don't have the most up-to-date min_vruntime on the originating
  4291	 * CPU and an up-to-date min_vruntime on the destination CPU.
  4292	 */
  4293	
  4294	static void
  4295	enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
  4296	{
  4297		bool renorm = !(flags & ENQUEUE_WAKEUP) || (flags & ENQUEUE_MIGRATED);
  4298		bool curr = cfs_rq->curr == se;
  4299	
  4300		/*
  4301		 * If we're the current task, we must renormalise before calling
  4302		 * update_curr().
  4303		 */
  4304		if (renorm && curr)
  4305			se->vruntime += cfs_rq->min_vruntime;
  4306	
  4307		update_curr(cfs_rq);
  4308	
  4309		/*
  4310		 * Otherwise, renormalise after, such that we're placed at the current
  4311		 * moment in time, instead of some random moment in the past. Being
  4312		 * placed in the past could significantly boost this task to the
  4313		 * fairness detriment of existing tasks.
  4314		 */
  4315		if (renorm && !curr)
  4316			se->vruntime += cfs_rq->min_vruntime;
  4317	
  4318		/*
  4319		 * When enqueuing a sched_entity, we must:
  4320		 *   - Update loads to have both entity and cfs_rq synced with now.
  4321		 *   - Add its load to cfs_rq->runnable_avg
  4322		 *   - For group_entity, update its weight to reflect the new share of
  4323		 *     its group cfs_rq
  4324		 *   - Add its new weight to cfs_rq->load.weight
  4325		 */
  4326		update_load_avg(cfs_rq, se, UPDATE_TG | DO_ATTACH);
  4327		se_update_runnable(se);
  4328		update_cfs_group(se);
  4329		account_entity_enqueue(cfs_rq, se);
  4330	
  4331		if (flags & ENQUEUE_WAKEUP)
  4332			place_entity(cfs_rq, se, 0);
  4333	
  4334		check_schedstat_required();
  4335		update_stats_enqueue_fair(cfs_rq, se, flags);
  4336		check_spread(cfs_rq, se);
  4337		if (!curr)
  4338			__enqueue_entity(cfs_rq, se);
  4339		se->on_rq = 1;
  4340	
  4341		if (cfs_rq->nr_running == 1) {
  4342			check_enqueue_throttle(cfs_rq);
> 4343			if (!throttled_hierarchy(cfs_rq))
  4344				list_add_leaf_cfs_rq(cfs_rq);
  4345		}
  4346	}
  4347	

-- 
0-DAY CI Kernel Test Service
https://01.org/lkp

Re: [External] Re: [PATCH v2 2/2] sched/fair: optimize and simplify rq leaf_cfs_rq_list

[Chengming Zhou]

On 2022/5/26 16:53, kernel test robot wrote:
> Hi Chengming,
> 
> Thank you for the patch! Yet something to improve:
> 
> [auto build test ERROR on tip/sched/core]
> [also build test ERROR on tip/master linus/master v5.18 next-20220525]
> [If your patch is applied to the wrong git tree, kindly drop us a note.
> And when submitting patch, we suggest to use '--base' as documented in
> https://git-scm.com/docs/git-format-patch]
> 
> url:    https://github.com/intel-lab-lkp/linux/commits/Chengming-Zhou/sched-fair-optimize-and-simplify-rq-leaf_cfs_rq_list/20220526-151850
> base:   https://git.kernel.org/pub/scm/linux/kernel/git/tip/tip.git 991d8d8142cad94f9c5c05db25e67fa83d6f772a
> config: powerpc-allnoconfig (https://download.01.org/0day-ci/archive/20220526/202205261617.YUT1ixQ8-lkp@intel.com/config)
> compiler: powerpc-linux-gcc (GCC) 11.3.0
> reproduce (this is a W=1 build):
>         wget https://raw.githubusercontent.com/intel/lkp-tests/master/sbin/make.cross -O ~/bin/make.cross
>         chmod +x ~/bin/make.cross
>         # https://github.com/intel-lab-lkp/linux/commit/cb2b1810aeb3f8f290a932f3e625ab9df1110054
>         git remote add linux-review https://github.com/intel-lab-lkp/linux
>         git fetch --no-tags linux-review Chengming-Zhou/sched-fair-optimize-and-simplify-rq-leaf_cfs_rq_list/20220526-151850
>         git checkout cb2b1810aeb3f8f290a932f3e625ab9df1110054
>         # save the config file
>         mkdir build_dir && cp config build_dir/.config
>         COMPILER_INSTALL_PATH=$HOME/0day COMPILER=gcc-11.3.0 make.cross W=1 O=build_dir ARCH=powerpc SHELL=/bin/bash kernel/sched/
> 
> If you fix the issue, kindly add following tag where applicable
> Reported-by: kernel test robot <lkp@intel.com>

Thanks, will fix !CONFIG_FAIR_GROUP_SCHED build next version.

> 
> All errors (new ones prefixed by >>):
> 
>    kernel/sched/fair.c:645:5: warning: no previous prototype for 'sched_update_scaling' [-Wmissing-prototypes]
>      645 | int sched_update_scaling(void)
>          |     ^~~~~~~~~~~~~~~~~~~~
>    kernel/sched/fair.c: In function 'enqueue_entity':
>>> kernel/sched/fair.c:4343:22: error: implicit declaration of function 'throttled_hierarchy' [-Werror=implicit-function-declaration]
>     4343 |                 if (!throttled_hierarchy(cfs_rq))
>          |                      ^~~~~~~~~~~~~~~~~~~
>    kernel/sched/fair.c: At top level:
>>> kernel/sched/fair.c:5484:19: error: static declaration of 'throttled_hierarchy' follows non-static declaration
>     5484 | static inline int throttled_hierarchy(struct cfs_rq *cfs_rq)
>          |                   ^~~~~~~~~~~~~~~~~~~
>    kernel/sched/fair.c:4343:22: note: previous implicit declaration of 'throttled_hierarchy' with type 'int()'
>     4343 |                 if (!throttled_hierarchy(cfs_rq))
>          |                      ^~~~~~~~~~~~~~~~~~~
>    kernel/sched/fair.c:5495:6: warning: no previous prototype for 'init_cfs_bandwidth' [-Wmissing-prototypes]
>     5495 | void init_cfs_bandwidth(struct cfs_bandwidth *cfs_b) {}
>          |      ^~~~~~~~~~~~~~~~~~
>    kernel/sched/fair.c:11654:6: warning: no previous prototype for 'free_fair_sched_group' [-Wmissing-prototypes]
>    11654 | void free_fair_sched_group(struct task_group *tg) { }
>          |      ^~~~~~~~~~~~~~~~~~~~~
>    kernel/sched/fair.c:11656:5: warning: no previous prototype for 'alloc_fair_sched_group' [-Wmissing-prototypes]
>    11656 | int alloc_fair_sched_group(struct task_group *tg, struct task_group *parent)
>          |     ^~~~~~~~~~~~~~~~~~~~~~
>    kernel/sched/fair.c:11661:6: warning: no previous prototype for 'online_fair_sched_group' [-Wmissing-prototypes]
>    11661 | void online_fair_sched_group(struct task_group *tg) { }
>          |      ^~~~~~~~~~~~~~~~~~~~~~~
>    kernel/sched/fair.c:11663:6: warning: no previous prototype for 'unregister_fair_sched_group' [-Wmissing-prototypes]
>    11663 | void unregister_fair_sched_group(struct task_group *tg) { }
>          |      ^~~~~~~~~~~~~~~~~~~~~~~~~~~
>    cc1: some warnings being treated as errors
> 
> 
> vim +/throttled_hierarchy +4343 kernel/sched/fair.c
> 
>   4263	
>   4264	/*
>   4265	 * MIGRATION
>   4266	 *
>   4267	 *	dequeue
>   4268	 *	  update_curr()
>   4269	 *	    update_min_vruntime()
>   4270	 *	  vruntime -= min_vruntime
>   4271	 *
>   4272	 *	enqueue
>   4273	 *	  update_curr()
>   4274	 *	    update_min_vruntime()
>   4275	 *	  vruntime += min_vruntime
>   4276	 *
>   4277	 * this way the vruntime transition between RQs is done when both
>   4278	 * min_vruntime are up-to-date.
>   4279	 *
>   4280	 * WAKEUP (remote)
>   4281	 *
>   4282	 *	->migrate_task_rq_fair() (p->state == TASK_WAKING)
>   4283	 *	  vruntime -= min_vruntime
>   4284	 *
>   4285	 *	enqueue
>   4286	 *	  update_curr()
>   4287	 *	    update_min_vruntime()
>   4288	 *	  vruntime += min_vruntime
>   4289	 *
>   4290	 * this way we don't have the most up-to-date min_vruntime on the originating
>   4291	 * CPU and an up-to-date min_vruntime on the destination CPU.
>   4292	 */
>   4293	
>   4294	static void
>   4295	enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
>   4296	{
>   4297		bool renorm = !(flags & ENQUEUE_WAKEUP) || (flags & ENQUEUE_MIGRATED);
>   4298		bool curr = cfs_rq->curr == se;
>   4299	
>   4300		/*
>   4301		 * If we're the current task, we must renormalise before calling
>   4302		 * update_curr().
>   4303		 */
>   4304		if (renorm && curr)
>   4305			se->vruntime += cfs_rq->min_vruntime;
>   4306	
>   4307		update_curr(cfs_rq);
>   4308	
>   4309		/*
>   4310		 * Otherwise, renormalise after, such that we're placed at the current
>   4311		 * moment in time, instead of some random moment in the past. Being
>   4312		 * placed in the past could significantly boost this task to the
>   4313		 * fairness detriment of existing tasks.
>   4314		 */
>   4315		if (renorm && !curr)
>   4316			se->vruntime += cfs_rq->min_vruntime;
>   4317	
>   4318		/*
>   4319		 * When enqueuing a sched_entity, we must:
>   4320		 *   - Update loads to have both entity and cfs_rq synced with now.
>   4321		 *   - Add its load to cfs_rq->runnable_avg
>   4322		 *   - For group_entity, update its weight to reflect the new share of
>   4323		 *     its group cfs_rq
>   4324		 *   - Add its new weight to cfs_rq->load.weight
>   4325		 */
>   4326		update_load_avg(cfs_rq, se, UPDATE_TG | DO_ATTACH);
>   4327		se_update_runnable(se);
>   4328		update_cfs_group(se);
>   4329		account_entity_enqueue(cfs_rq, se);
>   4330	
>   4331		if (flags & ENQUEUE_WAKEUP)
>   4332			place_entity(cfs_rq, se, 0);
>   4333	
>   4334		check_schedstat_required();
>   4335		update_stats_enqueue_fair(cfs_rq, se, flags);
>   4336		check_spread(cfs_rq, se);
>   4337		if (!curr)
>   4338			__enqueue_entity(cfs_rq, se);
>   4339		se->on_rq = 1;
>   4340	
>   4341		if (cfs_rq->nr_running == 1) {
>   4342			check_enqueue_throttle(cfs_rq);
>> 4343			if (!throttled_hierarchy(cfs_rq))
>   4344				list_add_leaf_cfs_rq(cfs_rq);
>   4345		}
>   4346	}
>   4347	
> 

Re: [External] Re: [PATCH v2 2/2] sched/fair: optimize and simplify rq leaf_cfs_rq_list

[Chengming Zhou]

[-- Attachment #1: Type: text/plain, Size: 7215 bytes --]

On 2022/5/26 16:53, kernel test robot wrote:
> Hi Chengming,
> 
> Thank you for the patch! Yet something to improve:
> 
> [auto build test ERROR on tip/sched/core]
> [also build test ERROR on tip/master linus/master v5.18 next-20220525]
> [If your patch is applied to the wrong git tree, kindly drop us a note.
> And when submitting patch, we suggest to use '--base' as documented in
> https://git-scm.com/docs/git-format-patch]
> 
> url:    https://github.com/intel-lab-lkp/linux/commits/Chengming-Zhou/sched-fair-optimize-and-simplify-rq-leaf_cfs_rq_list/20220526-151850
> base:   https://git.kernel.org/pub/scm/linux/kernel/git/tip/tip.git 991d8d8142cad94f9c5c05db25e67fa83d6f772a
> config: powerpc-allnoconfig (https://download.01.org/0day-ci/archive/20220526/202205261617.YUT1ixQ8-lkp(a)intel.com/config)
> compiler: powerpc-linux-gcc (GCC) 11.3.0
> reproduce (this is a W=1 build):
>         wget https://raw.githubusercontent.com/intel/lkp-tests/master/sbin/make.cross -O ~/bin/make.cross
>         chmod +x ~/bin/make.cross
>         # https://github.com/intel-lab-lkp/linux/commit/cb2b1810aeb3f8f290a932f3e625ab9df1110054
>         git remote add linux-review https://github.com/intel-lab-lkp/linux
>         git fetch --no-tags linux-review Chengming-Zhou/sched-fair-optimize-and-simplify-rq-leaf_cfs_rq_list/20220526-151850
>         git checkout cb2b1810aeb3f8f290a932f3e625ab9df1110054
>         # save the config file
>         mkdir build_dir && cp config build_dir/.config
>         COMPILER_INSTALL_PATH=$HOME/0day COMPILER=gcc-11.3.0 make.cross W=1 O=build_dir ARCH=powerpc SHELL=/bin/bash kernel/sched/
> 
> If you fix the issue, kindly add following tag where applicable
> Reported-by: kernel test robot <lkp@intel.com>

Thanks, will fix !CONFIG_FAIR_GROUP_SCHED build next version.

> 
> All errors (new ones prefixed by >>):
> 
>    kernel/sched/fair.c:645:5: warning: no previous prototype for 'sched_update_scaling' [-Wmissing-prototypes]
>      645 | int sched_update_scaling(void)
>          |     ^~~~~~~~~~~~~~~~~~~~
>    kernel/sched/fair.c: In function 'enqueue_entity':
>>> kernel/sched/fair.c:4343:22: error: implicit declaration of function 'throttled_hierarchy' [-Werror=implicit-function-declaration]
>     4343 |                 if (!throttled_hierarchy(cfs_rq))
>          |                      ^~~~~~~~~~~~~~~~~~~
>    kernel/sched/fair.c: At top level:
>>> kernel/sched/fair.c:5484:19: error: static declaration of 'throttled_hierarchy' follows non-static declaration
>     5484 | static inline int throttled_hierarchy(struct cfs_rq *cfs_rq)
>          |                   ^~~~~~~~~~~~~~~~~~~
>    kernel/sched/fair.c:4343:22: note: previous implicit declaration of 'throttled_hierarchy' with type 'int()'
>     4343 |                 if (!throttled_hierarchy(cfs_rq))
>          |                      ^~~~~~~~~~~~~~~~~~~
>    kernel/sched/fair.c:5495:6: warning: no previous prototype for 'init_cfs_bandwidth' [-Wmissing-prototypes]
>     5495 | void init_cfs_bandwidth(struct cfs_bandwidth *cfs_b) {}
>          |      ^~~~~~~~~~~~~~~~~~
>    kernel/sched/fair.c:11654:6: warning: no previous prototype for 'free_fair_sched_group' [-Wmissing-prototypes]
>    11654 | void free_fair_sched_group(struct task_group *tg) { }
>          |      ^~~~~~~~~~~~~~~~~~~~~
>    kernel/sched/fair.c:11656:5: warning: no previous prototype for 'alloc_fair_sched_group' [-Wmissing-prototypes]
>    11656 | int alloc_fair_sched_group(struct task_group *tg, struct task_group *parent)
>          |     ^~~~~~~~~~~~~~~~~~~~~~
>    kernel/sched/fair.c:11661:6: warning: no previous prototype for 'online_fair_sched_group' [-Wmissing-prototypes]
>    11661 | void online_fair_sched_group(struct task_group *tg) { }
>          |      ^~~~~~~~~~~~~~~~~~~~~~~
>    kernel/sched/fair.c:11663:6: warning: no previous prototype for 'unregister_fair_sched_group' [-Wmissing-prototypes]
>    11663 | void unregister_fair_sched_group(struct task_group *tg) { }
>          |      ^~~~~~~~~~~~~~~~~~~~~~~~~~~
>    cc1: some warnings being treated as errors
> 
> 
> vim +/throttled_hierarchy +4343 kernel/sched/fair.c
> 
>   4263	
>   4264	/*
>   4265	 * MIGRATION
>   4266	 *
>   4267	 *	dequeue
>   4268	 *	  update_curr()
>   4269	 *	    update_min_vruntime()
>   4270	 *	  vruntime -= min_vruntime
>   4271	 *
>   4272	 *	enqueue
>   4273	 *	  update_curr()
>   4274	 *	    update_min_vruntime()
>   4275	 *	  vruntime += min_vruntime
>   4276	 *
>   4277	 * this way the vruntime transition between RQs is done when both
>   4278	 * min_vruntime are up-to-date.
>   4279	 *
>   4280	 * WAKEUP (remote)
>   4281	 *
>   4282	 *	->migrate_task_rq_fair() (p->state == TASK_WAKING)
>   4283	 *	  vruntime -= min_vruntime
>   4284	 *
>   4285	 *	enqueue
>   4286	 *	  update_curr()
>   4287	 *	    update_min_vruntime()
>   4288	 *	  vruntime += min_vruntime
>   4289	 *
>   4290	 * this way we don't have the most up-to-date min_vruntime on the originating
>   4291	 * CPU and an up-to-date min_vruntime on the destination CPU.
>   4292	 */
>   4293	
>   4294	static void
>   4295	enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
>   4296	{
>   4297		bool renorm = !(flags & ENQUEUE_WAKEUP) || (flags & ENQUEUE_MIGRATED);
>   4298		bool curr = cfs_rq->curr == se;
>   4299	
>   4300		/*
>   4301		 * If we're the current task, we must renormalise before calling
>   4302		 * update_curr().
>   4303		 */
>   4304		if (renorm && curr)
>   4305			se->vruntime += cfs_rq->min_vruntime;
>   4306	
>   4307		update_curr(cfs_rq);
>   4308	
>   4309		/*
>   4310		 * Otherwise, renormalise after, such that we're placed at the current
>   4311		 * moment in time, instead of some random moment in the past. Being
>   4312		 * placed in the past could significantly boost this task to the
>   4313		 * fairness detriment of existing tasks.
>   4314		 */
>   4315		if (renorm && !curr)
>   4316			se->vruntime += cfs_rq->min_vruntime;
>   4317	
>   4318		/*
>   4319		 * When enqueuing a sched_entity, we must:
>   4320		 *   - Update loads to have both entity and cfs_rq synced with now.
>   4321		 *   - Add its load to cfs_rq->runnable_avg
>   4322		 *   - For group_entity, update its weight to reflect the new share of
>   4323		 *     its group cfs_rq
>   4324		 *   - Add its new weight to cfs_rq->load.weight
>   4325		 */
>   4326		update_load_avg(cfs_rq, se, UPDATE_TG | DO_ATTACH);
>   4327		se_update_runnable(se);
>   4328		update_cfs_group(se);
>   4329		account_entity_enqueue(cfs_rq, se);
>   4330	
>   4331		if (flags & ENQUEUE_WAKEUP)
>   4332			place_entity(cfs_rq, se, 0);
>   4333	
>   4334		check_schedstat_required();
>   4335		update_stats_enqueue_fair(cfs_rq, se, flags);
>   4336		check_spread(cfs_rq, se);
>   4337		if (!curr)
>   4338			__enqueue_entity(cfs_rq, se);
>   4339		se->on_rq = 1;
>   4340	
>   4341		if (cfs_rq->nr_running == 1) {
>   4342			check_enqueue_throttle(cfs_rq);
>> 4343			if (!throttled_hierarchy(cfs_rq))
>   4344				list_add_leaf_cfs_rq(cfs_rq);
>   4345		}
>   4346	}
>   4347	
> 

Re: [PATCH v2 2/2] sched/fair: optimize and simplify rq leaf_cfs_rq_list

[kernel test robot]

Hi Chengming,

Thank you for the patch! Yet something to improve:

[auto build test ERROR on tip/sched/core]
[also build test ERROR on tip/master linus/master v5.18 next-20220526]
[If your patch is applied to the wrong git tree, kindly drop us a note.
And when submitting patch, we suggest to use '--base' as documented in
https://git-scm.com/docs/git-format-patch]

url:    https://github.com/intel-lab-lkp/linux/commits/Chengming-Zhou/sched-fair-optimize-and-simplify-rq-leaf_cfs_rq_list/20220526-151850
base:   https://git.kernel.org/pub/scm/linux/kernel/git/tip/tip.git 991d8d8142cad94f9c5c05db25e67fa83d6f772a
config: arm-randconfig-r014-20220524 (https://download.01.org/0day-ci/archive/20220526/202205261834.2QOwksAg-lkp@intel.com/config)
compiler: clang version 15.0.0 (https://github.com/llvm/llvm-project 3d546191ad9d7d2ad2c7928204b9de51deafa675)
reproduce (this is a W=1 build):
        wget https://raw.githubusercontent.com/intel/lkp-tests/master/sbin/make.cross -O ~/bin/make.cross
        chmod +x ~/bin/make.cross
        # install arm cross compiling tool for clang build
        # apt-get install binutils-arm-linux-gnueabi
        # https://github.com/intel-lab-lkp/linux/commit/cb2b1810aeb3f8f290a932f3e625ab9df1110054
        git remote add linux-review https://github.com/intel-lab-lkp/linux
        git fetch --no-tags linux-review Chengming-Zhou/sched-fair-optimize-and-simplify-rq-leaf_cfs_rq_list/20220526-151850
        git checkout cb2b1810aeb3f8f290a932f3e625ab9df1110054
        # save the config file
        mkdir build_dir && cp config build_dir/.config
        COMPILER_INSTALL_PATH=$HOME/0day COMPILER=clang make.cross W=1 O=build_dir ARCH=arm SHELL=/bin/bash

If you fix the issue, kindly add following tag where applicable
Reported-by: kernel test robot <lkp@intel.com>

All errors (new ones prefixed by >>):

   kernel/sched/fair.c:645:5: warning: no previous prototype for function 'sched_update_scaling' [-Wmissing-prototypes]
   int sched_update_scaling(void)
       ^
   kernel/sched/fair.c:645:1: note: declare 'static' if the function is not intended to be used outside of this translation unit
   int sched_update_scaling(void)
   ^
   static 
>> kernel/sched/fair.c:4343:8: error: call to undeclared function 'throttled_hierarchy'; ISO C99 and later do not support implicit function declarations [-Wimplicit-function-declaration]
                   if (!throttled_hierarchy(cfs_rq))
                        ^
   kernel/sched/fair.c:5484:19: error: static declaration of 'throttled_hierarchy' follows non-static declaration
   static inline int throttled_hierarchy(struct cfs_rq *cfs_rq)
                     ^
   kernel/sched/fair.c:4343:8: note: previous implicit declaration is here
                   if (!throttled_hierarchy(cfs_rq))
                        ^
   kernel/sched/fair.c:5495:6: warning: no previous prototype for function 'init_cfs_bandwidth' [-Wmissing-prototypes]
   void init_cfs_bandwidth(struct cfs_bandwidth *cfs_b) {}
        ^
   kernel/sched/fair.c:5495:1: note: declare 'static' if the function is not intended to be used outside of this translation unit
   void init_cfs_bandwidth(struct cfs_bandwidth *cfs_b) {}
   ^
   static 
   kernel/sched/fair.c:11654:6: warning: no previous prototype for function 'free_fair_sched_group' [-Wmissing-prototypes]
   void free_fair_sched_group(struct task_group *tg) { }
        ^
   kernel/sched/fair.c:11654:1: note: declare 'static' if the function is not intended to be used outside of this translation unit
   void free_fair_sched_group(struct task_group *tg) { }
   ^
   static 
   kernel/sched/fair.c:11656:5: warning: no previous prototype for function 'alloc_fair_sched_group' [-Wmissing-prototypes]
   int alloc_fair_sched_group(struct task_group *tg, struct task_group *parent)
       ^
   kernel/sched/fair.c:11656:1: note: declare 'static' if the function is not intended to be used outside of this translation unit
   int alloc_fair_sched_group(struct task_group *tg, struct task_group *parent)
   ^
   static 
   kernel/sched/fair.c:11661:6: warning: no previous prototype for function 'online_fair_sched_group' [-Wmissing-prototypes]
   void online_fair_sched_group(struct task_group *tg) { }
        ^
   kernel/sched/fair.c:11661:1: note: declare 'static' if the function is not intended to be used outside of this translation unit
   void online_fair_sched_group(struct task_group *tg) { }
   ^
   static 
   kernel/sched/fair.c:11663:6: warning: no previous prototype for function 'unregister_fair_sched_group' [-Wmissing-prototypes]
   void unregister_fair_sched_group(struct task_group *tg) { }
        ^
   kernel/sched/fair.c:11663:1: note: declare 'static' if the function is not intended to be used outside of this translation unit
   void unregister_fair_sched_group(struct task_group *tg) { }
   ^
   static 
   6 warnings and 2 errors generated.

Kconfig warnings: (for reference only)
   WARNING: unmet direct dependencies detected for DRM_GEM_SHMEM_HELPER
   Depends on HAS_IOMEM && DRM && MMU
   Selected by
   - DRM_SSD130X && HAS_IOMEM && DRM


vim +/throttled_hierarchy +4343 kernel/sched/fair.c

  4263	
  4264	/*
  4265	 * MIGRATION
  4266	 *
  4267	 *	dequeue
  4268	 *	  update_curr()
  4269	 *	    update_min_vruntime()
  4270	 *	  vruntime -= min_vruntime
  4271	 *
  4272	 *	enqueue
  4273	 *	  update_curr()
  4274	 *	    update_min_vruntime()
  4275	 *	  vruntime += min_vruntime
  4276	 *
  4277	 * this way the vruntime transition between RQs is done when both
  4278	 * min_vruntime are up-to-date.
  4279	 *
  4280	 * WAKEUP (remote)
  4281	 *
  4282	 *	->migrate_task_rq_fair() (p->state == TASK_WAKING)
  4283	 *	  vruntime -= min_vruntime
  4284	 *
  4285	 *	enqueue
  4286	 *	  update_curr()
  4287	 *	    update_min_vruntime()
  4288	 *	  vruntime += min_vruntime
  4289	 *
  4290	 * this way we don't have the most up-to-date min_vruntime on the originating
  4291	 * CPU and an up-to-date min_vruntime on the destination CPU.
  4292	 */
  4293	
  4294	static void
  4295	enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
  4296	{
  4297		bool renorm = !(flags & ENQUEUE_WAKEUP) || (flags & ENQUEUE_MIGRATED);
  4298		bool curr = cfs_rq->curr == se;
  4299	
  4300		/*
  4301		 * If we're the current task, we must renormalise before calling
  4302		 * update_curr().
  4303		 */
  4304		if (renorm && curr)
  4305			se->vruntime += cfs_rq->min_vruntime;
  4306	
  4307		update_curr(cfs_rq);
  4308	
  4309		/*
  4310		 * Otherwise, renormalise after, such that we're placed at the current
  4311		 * moment in time, instead of some random moment in the past. Being
  4312		 * placed in the past could significantly boost this task to the
  4313		 * fairness detriment of existing tasks.
  4314		 */
  4315		if (renorm && !curr)
  4316			se->vruntime += cfs_rq->min_vruntime;
  4317	
  4318		/*
  4319		 * When enqueuing a sched_entity, we must:
  4320		 *   - Update loads to have both entity and cfs_rq synced with now.
  4321		 *   - Add its load to cfs_rq->runnable_avg
  4322		 *   - For group_entity, update its weight to reflect the new share of
  4323		 *     its group cfs_rq
  4324		 *   - Add its new weight to cfs_rq->load.weight
  4325		 */
  4326		update_load_avg(cfs_rq, se, UPDATE_TG | DO_ATTACH);
  4327		se_update_runnable(se);
  4328		update_cfs_group(se);
  4329		account_entity_enqueue(cfs_rq, se);
  4330	
  4331		if (flags & ENQUEUE_WAKEUP)
  4332			place_entity(cfs_rq, se, 0);
  4333	
  4334		check_schedstat_required();
  4335		update_stats_enqueue_fair(cfs_rq, se, flags);
  4336		check_spread(cfs_rq, se);
  4337		if (!curr)
  4338			__enqueue_entity(cfs_rq, se);
  4339		se->on_rq = 1;
  4340	
  4341		if (cfs_rq->nr_running == 1) {
  4342			check_enqueue_throttle(cfs_rq);
> 4343			if (!throttled_hierarchy(cfs_rq))
  4344				list_add_leaf_cfs_rq(cfs_rq);
  4345		}
  4346	}
  4347	

-- 
0-DAY CI Kernel Test Service
https://01.org/lkp