With the consolidation of put_prev_task/set_next_task(), see
commit 436f3eed5c69 ("sched: Combine the last put_prev_task() and the
first set_next_task()"), we are now skipping the transition between
these two functions when the previous and the next tasks are the same.

As a result, ops.update_idle() is now called only once when the CPU
transitions to the idle class. If the CPU stays active (e.g., through a
call to scx_bpf_kick_cpu()), ops.update_idle() will not be triggered
again since the task remains unchanged (rq->idle).

While this behavior seems generally correct, it can cause issues in
certain sched_ext scenarios.

For example, a BPF scheduler might use logic like the following to keep
the CPU active under specific conditions:

void BPF_STRUCT_OPS(sched_update_idle, s32 cpu, bool idle)
{
	if (!idle)
		return;
	if (condition)
		scx_bpf_kick_cpu(cpu, 0);
}

A call to scx_bpf_kick_cpu() wakes up the CPU, so in theory,
ops.update_idle() should be triggered again until the condition becomes
false. However, this doesn't happen, and scx_bpf_kick_cpu() doesn't
produce the expected effect.

In practice, this change badly impacts performance in user-space
schedulers that rely on ops.update_idle() to activate user-space
components.

For instance, in the case of scx_rustland, performance drops
significantly (e.g., gaming benchmarks fall from ~60fps to ~10fps).

To address this, trigger ops.update_idle() also from pick_task_idle()
when the idle task keeps running on the CPU. This restores the correct
behavior of ops.update_idle() and it allows to fix the performance
regression in scx_rustland.

Fixes: 7c65ae81ea86 ("sched_ext: Don't call put_prev_task_scx() before picking the next task")
Signed-off-by: Andrea Righi <andrea.righi@linux.dev>
---
 kernel/sched/idle.c | 14 ++++++++++++++
 1 file changed, 14 insertions(+)

ChangeLog v3 -> v4:
  - handle the core-sched case that may ignore the result of
    pick_task(), triggering spurious ops.update_idle() events

ChangeLog v2 -> v3:
  - add a comment to clarify why we need to update the scx idle state in
    pick_task()

ChangeLog v1 -> v2:
  - move the logic from put_prev_set_next_task() to scx_update_idle()

diff --git a/kernel/sched/idle.c b/kernel/sched/idle.c
index d2f096bb274c..3e76b11237a9 100644
--- a/kernel/sched/idle.c
+++ b/kernel/sched/idle.c
@@ -466,6 +466,20 @@ static void set_next_task_idle(struct rq *rq, struct task_struct *next, bool fir
 
 struct task_struct *pick_task_idle(struct rq *rq)
 {
+	/*
+	 * When switching from a non-idle to the idle class, .set_next_task()
+	 * is called only once during the transition.
+	 *
+	 * However, the CPU may remain active for multiple rounds running the
+	 * idle task (e.g., by calling scx_bpf_kick_cpu() from the
+	 * ops.update_idle() callback).
+	 *
+	 * In such cases, we need to keep updating the scx idle state to
+	 * properly re-trigger the ops.update_idle() callback and ensure
+	 * correct handling of scx idle state transitions.
+	 */
+	if (rq->curr == rq->idle)
+		scx_update_idle(rq, true);
 	return rq->idle;
 }
 
-- 
2.47.0

Hi Andrea,

kernel test robot noticed the following build warnings:

[auto build test WARNING on tip/sched/core]
[also build test WARNING on linus/master v6.12-rc3 next-20241016]
[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#_base_tree_information]

url:    https://github.com/intel-lab-lkp/linux/commits/Andrea-Righi/sched_ext-Trigger-ops-update_idle-from-pick_task_idle/20241015-191701
base:   tip/sched/core
patch link:    https://lore.kernel.org/r/20241015111539.12136-1-andrea.righi%40linux.dev
patch subject: [PATCH v4] sched_ext: Trigger ops.update_idle() from pick_task_idle()
config: x86_64-randconfig-122-20241016 (https://download.01.org/0day-ci/archive/20241016/202410161955.CsmEsAy8-lkp@intel.com/config)
compiler: gcc-12 (Debian 12.2.0-14) 12.2.0
reproduce (this is a W=1 build): (https://download.01.org/0day-ci/archive/20241016/202410161955.CsmEsAy8-lkp@intel.com/reproduce)

If you fix the issue in a separate patch/commit (i.e. not just a new version of
the same patch/commit), kindly add following tags
| Reported-by: kernel test robot <lkp@intel.com>
| Closes: https://lore.kernel.org/oe-kbuild-all/202410161955.CsmEsAy8-lkp@intel.com/

sparse warnings: (new ones prefixed by >>)
   kernel/sched/build_policy.c: note: in included file:
>> kernel/sched/idle.c:481:22: sparse: sparse: incompatible types in comparison expression (different address spaces):
   kernel/sched/idle.c:481:22: sparse:    struct task_struct [noderef] __rcu *
   kernel/sched/idle.c:481:22: sparse:    struct task_struct *
   kernel/sched/build_policy.c: note: in included file:
   kernel/sched/rt.c:991:38: sparse: sparse: incorrect type in initializer (different address spaces) @@     expected struct task_struct *curr @@     got struct task_struct [noderef] __rcu *curr @@
   kernel/sched/rt.c:991:38: sparse:     expected struct task_struct *curr
   kernel/sched/rt.c:991:38: sparse:     got struct task_struct [noderef] __rcu *curr
   kernel/sched/rt.c:1529:31: sparse: sparse: incorrect type in argument 2 (different address spaces) @@     expected struct task_struct *p @@     got struct task_struct [noderef] __rcu *curr @@
   kernel/sched/rt.c:1529:31: sparse:     expected struct task_struct *p
   kernel/sched/rt.c:1529:31: sparse:     got struct task_struct [noderef] __rcu *curr
   kernel/sched/build_policy.c: note: in included file:
   kernel/sched/deadline.c:2341:42: sparse: sparse: incorrect type in argument 2 (different address spaces) @@     expected struct sched_dl_entity const *b @@     got struct sched_dl_entity [noderef] __rcu * @@
   kernel/sched/deadline.c:2341:42: sparse:     expected struct sched_dl_entity const *b
   kernel/sched/deadline.c:2341:42: sparse:     got struct sched_dl_entity [noderef] __rcu *
   kernel/sched/deadline.c:1242:39: sparse: sparse: incorrect type in argument 1 (different address spaces) @@     expected struct task_struct *p @@     got struct task_struct [noderef] __rcu *curr @@
   kernel/sched/deadline.c:1242:39: sparse:     expected struct task_struct *p
   kernel/sched/deadline.c:1242:39: sparse:     got struct task_struct [noderef] __rcu *curr
   kernel/sched/deadline.c:1242:85: sparse: sparse: incorrect type in argument 2 (different address spaces) @@     expected struct sched_dl_entity const *b @@     got struct sched_dl_entity [noderef] __rcu * @@
   kernel/sched/deadline.c:1242:85: sparse:     expected struct sched_dl_entity const *b
   kernel/sched/deadline.c:1242:85: sparse:     got struct sched_dl_entity [noderef] __rcu *
   kernel/sched/deadline.c:1342:23: sparse: sparse: incorrect type in argument 1 (different address spaces) @@     expected struct task_struct *p @@     got struct task_struct [noderef] __rcu *curr @@
   kernel/sched/deadline.c:1342:23: sparse:     expected struct task_struct *p
   kernel/sched/deadline.c:1342:23: sparse:     got struct task_struct [noderef] __rcu *curr
   kernel/sched/deadline.c:1651:31: sparse: sparse: incorrect type in argument 1 (different address spaces) @@     expected struct task_struct *p @@     got struct task_struct [noderef] __rcu *curr @@
   kernel/sched/deadline.c:1651:31: sparse:     expected struct task_struct *p
   kernel/sched/deadline.c:1651:31: sparse:     got struct task_struct [noderef] __rcu *curr
   kernel/sched/deadline.c:1651:70: sparse: sparse: incorrect type in argument 2 (different address spaces) @@     expected struct sched_dl_entity const *b @@     got struct sched_dl_entity [noderef] __rcu * @@
   kernel/sched/deadline.c:1651:70: sparse:     expected struct sched_dl_entity const *b
   kernel/sched/deadline.c:1651:70: sparse:     got struct sched_dl_entity [noderef] __rcu *
   kernel/sched/deadline.c:1739:38: sparse: sparse: incorrect type in initializer (different address spaces) @@     expected struct task_struct *curr @@     got struct task_struct [noderef] __rcu *curr @@
   kernel/sched/deadline.c:1739:38: sparse:     expected struct task_struct *curr
   kernel/sched/deadline.c:1739:38: sparse:     got struct task_struct [noderef] __rcu *curr
   kernel/sched/deadline.c:3054:22: sparse: sparse: incompatible types in comparison expression (different address spaces):
   kernel/sched/deadline.c:3054:22: sparse:    struct task_struct [noderef] __rcu *
   kernel/sched/deadline.c:3054:22: sparse:    struct task_struct *
   kernel/sched/build_policy.c: note: in included file:
   kernel/sched/syscalls.c:206:22: sparse: sparse: incompatible types in comparison expression (different address spaces):
   kernel/sched/syscalls.c:206:22: sparse:    struct task_struct [noderef] __rcu *
   kernel/sched/syscalls.c:206:22: sparse:    struct task_struct *
   kernel/sched/build_policy.c: note: in included file (through include/linux/smp.h, include/linux/sched/clock.h):
   include/linux/list.h:83:21: sparse: sparse: self-comparison always evaluates to true
   include/linux/list.h:83:21: sparse: sparse: self-comparison always evaluates to true
   kernel/sched/build_policy.c: note: in included file:
   kernel/sched/sched.h:2265:25: sparse: sparse: incompatible types in comparison expression (different address spaces):
   kernel/sched/sched.h:2265:25: sparse:    struct task_struct [noderef] __rcu *
   kernel/sched/sched.h:2265:25: sparse:    struct task_struct *
   kernel/sched/sched.h:2265:25: sparse: sparse: incompatible types in comparison expression (different address spaces):
   kernel/sched/sched.h:2265:25: sparse:    struct task_struct [noderef] __rcu *
   kernel/sched/sched.h:2265:25: sparse:    struct task_struct *
   kernel/sched/sched.h:2265:25: sparse: sparse: incompatible types in comparison expression (different address spaces):
   kernel/sched/sched.h:2265:25: sparse:    struct task_struct [noderef] __rcu *
   kernel/sched/sched.h:2265:25: sparse:    struct task_struct *
   kernel/sched/sched.h:2265:25: sparse: sparse: incompatible types in comparison expression (different address spaces):
   kernel/sched/sched.h:2265:25: sparse:    struct task_struct [noderef] __rcu *
   kernel/sched/sched.h:2265:25: sparse:    struct task_struct *
   kernel/sched/sched.h:2265:25: sparse: sparse: incompatible types in comparison expression (different address spaces):
   kernel/sched/sched.h:2265:25: sparse:    struct task_struct [noderef] __rcu *
   kernel/sched/sched.h:2265:25: sparse:    struct task_struct *
   kernel/sched/sched.h:2451:9: sparse: sparse: incompatible types in comparison expression (different address spaces):
   kernel/sched/sched.h:2451:9: sparse:    struct task_struct [noderef] __rcu *
   kernel/sched/sched.h:2451:9: sparse:    struct task_struct *
   kernel/sched/sched.h:2265:25: sparse: sparse: incompatible types in comparison expression (different address spaces):
   kernel/sched/sched.h:2265:25: sparse:    struct task_struct [noderef] __rcu *
   kernel/sched/sched.h:2265:25: sparse:    struct task_struct *
   kernel/sched/sched.h:2451:9: sparse: sparse: incompatible types in comparison expression (different address spaces):
   kernel/sched/sched.h:2451:9: sparse:    struct task_struct [noderef] __rcu *
   kernel/sched/sched.h:2451:9: sparse:    struct task_struct *
   kernel/sched/build_policy.c: note: in included file:
   kernel/sched/syscalls.c:1331:6: sparse: sparse: context imbalance in 'sched_getaffinity' - different lock contexts for basic block
   kernel/sched/build_policy.c: note: in included file:
   kernel/sched/sched.h:2265:25: sparse: sparse: incompatible types in comparison expression (different address spaces):
   kernel/sched/sched.h:2265:25: sparse:    struct task_struct [noderef] __rcu *
   kernel/sched/sched.h:2265:25: sparse:    struct task_struct *

vim +481 kernel/sched/idle.c

   466	
   467	struct task_struct *pick_task_idle(struct rq *rq)
   468	{
   469		/*
   470		 * When switching from a non-idle to the idle class, .set_next_task()
   471		 * is called only once during the transition.
   472		 *
   473		 * However, the CPU may remain active for multiple rounds running the
   474		 * idle task (e.g., by calling scx_bpf_kick_cpu() from the
   475		 * ops.update_idle() callback).
   476		 *
   477		 * In such cases, we need to keep updating the scx idle state to
   478		 * properly re-trigger the ops.update_idle() callback and ensure
   479		 * correct handling of scx idle state transitions.
   480		 */
 > 481		if (rq->curr == rq->idle)
   482			scx_update_idle(rq, true);
   483		return rq->idle;
   484	}
   485	

-- 
0-DAY CI Kernel Test Service
https://github.com/intel/lkp-tests/wiki

Hello, Andrea.

On Tue, Oct 15, 2024 at 01:15:39PM +0200, Andrea Righi wrote:
...
> For example, a BPF scheduler might use logic like the following to keep
> the CPU active under specific conditions:
> 
> void BPF_STRUCT_OPS(sched_update_idle, s32 cpu, bool idle)
> {
> 	if (!idle)
> 		return;
> 	if (condition)
> 		scx_bpf_kick_cpu(cpu, 0);
> }
> 
> A call to scx_bpf_kick_cpu() wakes up the CPU, so in theory,
> ops.update_idle() should be triggered again until the condition becomes
> false. However, this doesn't happen, and scx_bpf_kick_cpu() doesn't
> produce the expected effect.

I thought more about this scenario and I'm not sure anymore whether we want
to guarantee that scx_bpf_kick_cpu() is followed by update_idle(cpu, true).
Here are a couple considerations:

- As implemented, the transtions aren't balanced. ie. When the above
  happens, update_idle(cpu, true) will be generated multiple times without
  intervening update_idle(cpu, false). We can insert artificial false
  transtions but that's cumbersome and...

- For the purpose of determining whether a CPU is idle for e.g. task
  placement from ops.select_cpu(). The CPU *should* be considered idle in
  this polling state.

Overall, it feels a bit contrived to generate update_idle() events
consecutively for this. If a scheduler wants to poll in idle state, can't it
do something like the following?

- Trigger kick from update_idle(cpu, true) and remember that the CPU is in
  the polling state.

- Keep kicking from ops.dispatch() until polling state is cleared.

As what kick() guarnatees is at least one dispatch event after kicking, this
is guaranteed to be correct and the control flow, while a bit more
complicated, makes sense - it triggers dispatch on idle transition and keeps
dispatching in the idle state.

What do you think?

Thanks.

-- 
tejun

On Tue, Oct 15, 2024 at 04:41:26AM -1000, Tejun Heo wrote:
> Hello, Andrea.
> 
> On Tue, Oct 15, 2024 at 01:15:39PM +0200, Andrea Righi wrote:
> ...
> > For example, a BPF scheduler might use logic like the following to keep
> > the CPU active under specific conditions:
> > 
> > void BPF_STRUCT_OPS(sched_update_idle, s32 cpu, bool idle)
> > {
> > 	if (!idle)
> > 		return;
> > 	if (condition)
> > 		scx_bpf_kick_cpu(cpu, 0);
> > }
> > 
> > A call to scx_bpf_kick_cpu() wakes up the CPU, so in theory,
> > ops.update_idle() should be triggered again until the condition becomes
> > false. However, this doesn't happen, and scx_bpf_kick_cpu() doesn't
> > produce the expected effect.
> 
> I thought more about this scenario and I'm not sure anymore whether we want
> to guarantee that scx_bpf_kick_cpu() is followed by update_idle(cpu, true).
> Here are a couple considerations:
> 
> - As implemented, the transtions aren't balanced. ie. When the above
>   happens, update_idle(cpu, true) will be generated multiple times without
>   intervening update_idle(cpu, false). We can insert artificial false
>   transtions but that's cumbersome and...

Agreed, I wouldn't suggest adding artificial false events.

> 
> - For the purpose of determining whether a CPU is idle for e.g. task
>   placement from ops.select_cpu(). The CPU *should* be considered idle in
>   this polling state.
> 
> Overall, it feels a bit contrived to generate update_idle() events
> consecutively for this. If a scheduler wants to poll in idle state, can't it
> do something like the following?
> 
> - Trigger kick from update_idle(cpu, true) and remember that the CPU is in
>   the polling state.
> 
> - Keep kicking from ops.dispatch() until polling state is cleared.
> 
> As what kick() guarnatees is at least one dispatch event after kicking, this
> is guaranteed to be correct and the control flow, while a bit more
> complicated, makes sense - it triggers dispatch on idle transition and keeps
> dispatching in the idle state.
> 
> What do you think?

That seems to work in theory, I'll run some tests to confirm that it
also works in practice. :)

It looks definitely nicer than triggering multiple ops.update_idle()
from the kernel and we can maintain the proper semantic of triggering
update_idle() only on actual idle state changes.

Thanks,
-Andrea

On Tue, Oct 15, 2024 at 05:31:09PM +0200, Andrea Righi wrote:
...
> > - For the purpose of determining whether a CPU is idle for e.g. task
> >   placement from ops.select_cpu(). The CPU *should* be considered idle in
> >   this polling state.
> > 
> > Overall, it feels a bit contrived to generate update_idle() events
> > consecutively for this. If a scheduler wants to poll in idle state, can't it
> > do something like the following?
> > 
> > - Trigger kick from update_idle(cpu, true) and remember that the CPU is in
> >   the polling state.
> > 
> > - Keep kicking from ops.dispatch() until polling state is cleared.
> > 
> > As what kick() guarnatees is at least one dispatch event after kicking, this
> > is guaranteed to be correct and the control flow, while a bit more
> > complicated, makes sense - it triggers dispatch on idle transition and keeps
> > dispatching in the idle state.
> > 
> > What do you think?
> 
> That seems to work in theory, I'll run some tests to confirm that it
> also works in practice. :)
> 
> It looks definitely nicer than triggering multiple ops.update_idle()
> from the kernel and we can maintain the proper semantic of triggering
> update_idle() only on actual idle state changes.

For the record, this seems to be working for now. Here is the
implementation of the idea proposed by Tejun:
https://github.com/sched-ext/scx/commit/40ccca8cbef8fc73e16bfb789c7565326b3cca62

Therefore, we can ignore the kernel patch.

Thanks for the help on this!
-Andrea