Re: [PATCH 17/24] sched/fair: Implement delayed dequeue

Re: [PATCH 17/24] sched/fair: Implement delayed dequeue

[Bert Karwatzki]

Since linux next-20240820 the following messages appears when booting:

[    T1] smp: Bringing up secondary CPUs ...
[    T1] smpboot: x86: Booting SMP configuration:
[    T1] .... node  #0, CPUs:        #2  #4  #6  #8 #10 #12 #14  #1
This is the line I'm concerend about:
[    T1] psi: inconsistent task state! task=61:cpuhp/3 cpu=0 psi_flags=4 clear=0 set=4
[    T1]   #3  #5  #7  #9 #11 #13 #15
[    T1] Spectre V2 : Update user space SMT mitigation: STIBP always-on
[    T1] smp: Brought up 1 node, 16 CPUs
[    T1] smpboot: Total of 16 processors activated (102216.16 BogoMIPS)

I bisected this to commit 152e11f6df29 ("sched/fair: Implement delayed dequeue").
Is this normal or is this something I should worry about?

Bert Karwatzki

[REGRESSION] Re: [PATCH 17/24] sched/fair: Implement delayed dequeue

[Chris Bainbridge]

On Fri, Aug 30, 2024 at 02:34:56PM +0200, Bert Karwatzki wrote:
> Since linux next-20240820 the following messages appears when booting:
> 
> [    T1] smp: Bringing up secondary CPUs ...
> [    T1] smpboot: x86: Booting SMP configuration:
> [    T1] .... node  #0, CPUs:        #2  #4  #6  #8 #10 #12 #14  #1
> This is the line I'm concerend about:
> [    T1] psi: inconsistent task state! task=61:cpuhp/3 cpu=0 psi_flags=4 clear=0 set=4
> [    T1]   #3  #5  #7  #9 #11 #13 #15
> [    T1] Spectre V2 : Update user space SMT mitigation: STIBP always-on
> [    T1] smp: Brought up 1 node, 16 CPUs
> [    T1] smpboot: Total of 16 processors activated (102216.16 BogoMIPS)
> 
> I bisected this to commit 152e11f6df29 ("sched/fair: Implement delayed dequeue").
> Is this normal or is this something I should worry about?
> 
> Bert Karwatzki

I am also getting a similar error on boot, and bisected it to the same commit:

[    0.342931] psi: inconsistent task state! task=15:rcu_tasks_trace cpu=0 psi_flags=4 clear=0 set=4

#regzbot introduced: 152e11f6df293e816a6a37c69757033cdc72667d

Re: [REGRESSION] Re: [PATCH 17/24] sched/fair: Implement delayed dequeue

[Linux regression tracking (Thorsten Leemhuis)]

On 22.09.24 17:45, Chris Bainbridge wrote:
> On Fri, Aug 30, 2024 at 02:34:56PM +0200, Bert Karwatzki wrote:
>> Since linux next-20240820 the following messages appears when booting:
>>
>> [    T1] smp: Bringing up secondary CPUs ...
>> [    T1] smpboot: x86: Booting SMP configuration:
>> [    T1] .... node  #0, CPUs:        #2  #4  #6  #8 #10 #12 #14  #1
>> This is the line I'm concerend about:
>> [    T1] psi: inconsistent task state! task=61:cpuhp/3 cpu=0 psi_flags=4 clear=0 set=4
>> [    T1]   #3  #5  #7  #9 #11 #13 #15
>> [    T1] Spectre V2 : Update user space SMT mitigation: STIBP always-on
>> [    T1] smp: Brought up 1 node, 16 CPUs
>> [    T1] smpboot: Total of 16 processors activated (102216.16 BogoMIPS)
>>
>> I bisected this to commit 152e11f6df29 ("sched/fair: Implement delayed dequeue").
>> Is this normal or is this something I should worry about?
>>
> I am also getting a similar error on boot, and bisected it to the same commit:
> 
> [    0.342931] psi: inconsistent task state! task=15:rcu_tasks_trace cpu=0 psi_flags=4 clear=0 set=4
> 
> #regzbot introduced: 152e11f6df293e816a6a37c69757033cdc72667d

thx for CCing the regressions list.

Paul also reported this earlier today:

https://lore.kernel.org/all/cd67fbcd-d659-4822-bb90-7e8fbb40a856@molgen.mpg.de/

Hannes [CCed] replied there and has some idea what might be wrong:

https://lore.kernel.org/all/20240922102047.GA437832@cmpxchg.org/

Ciao, Thorsten (wearing his 'the Linux kernel's regression tracker' hat)
--
Everything you wanna know about Linux kernel regression tracking:
https://linux-regtracking.leemhuis.info/about/#tldr
If I did something stupid, please tell me, as explained on that page.

P.S.:

#regzbot dup:
https://lore.kernel.org/all/cd67fbcd-d659-4822-bb90-7e8fbb40a856@molgen.mpg.de/

#regzbot report:
https://lore.kernel.org/all/cd67fbcd-d659-4822-bb90-7e8fbb40a856@molgen.mpg.de/
#regzbot introduced: 152e11f6df293e816a6a37c69757033cdc72667d

Re: [REGRESSION] Re: [PATCH 17/24] sched/fair: Implement delayed dequeue

[Klaus Kudielka]

On Sun, 2024-09-22 at 16:45 +0100, Chris Bainbridge wrote:
> On Fri, Aug 30, 2024 at 02:34:56PM +0200, Bert Karwatzki wrote:
> > Since linux next-20240820 the following messages appears when booting:
> > 
> > [    T1] smp: Bringing up secondary CPUs ...
> > [    T1] smpboot: x86: Booting SMP configuration:
> > [    T1] .... node  #0, CPUs:        #2  #4  #6  #8 #10 #12 #14  #1
> > This is the line I'm concerend about:
> > [    T1] psi: inconsistent task state! task=61:cpuhp/3 cpu=0 psi_flags=4 clear=0 set=4
> > [    T1]   #3  #5  #7  #9 #11 #13 #15
> > [    T1] Spectre V2 : Update user space SMT mitigation: STIBP always-on
> > [    T1] smp: Brought up 1 node, 16 CPUs
> > [    T1] smpboot: Total of 16 processors activated (102216.16 BogoMIPS)
> > 
> > I bisected this to commit 152e11f6df29 ("sched/fair: Implement delayed dequeue").
> > Is this normal or is this something I should worry about?
> > 
> > Bert Karwatzki
> 
> I am also getting a similar error on boot, and bisected it to the same commit:
> 
> [    0.342931] psi: inconsistent task state! task=15:rcu_tasks_trace cpu=0 psi_flags=4 clear=0 set=4
> 
> #regzbot introduced: 152e11f6df293e816a6a37c69757033cdc72667d

Just another data point, while booting 6.12-rc1 on a Turris Omnia:

[    0.000000] Linux version 6.12.0-rc1 (XXX) (arm-linux-gnueabihf-gcc (Debian 14.2.0-1) 14.2.0, GNU ld (GNU Binutils for Debian) 2.43.1) #1 SMP Thu Oct  3 06:59:25 CEST 2024
[    0.000000] CPU: ARMv7 Processor [414fc091] revision 1 (ARMv7), cr=10c5387d
[    0.000000] CPU: PIPT / VIPT nonaliasing data cache, VIPT aliasing instruction cache
[    0.000000] OF: fdt: Machine model: Turris Omnia
...
[    0.000867] CPU0: thread -1, cpu 0, socket 0, mpidr 80000000
[    0.000876] psi: inconsistent task state! task=2:kthreadd cpu=0 psi_flags=4 clear=0 set=4

Re: [REGRESSION] Re: [PATCH 17/24] sched/fair: Implement delayed dequeue

[K Prateek Nayak]

Hello folks,

On 10/3/2024 11:01 AM, Klaus Kudielka wrote:
> On Sun, 2024-09-22 at 16:45 +0100, Chris Bainbridge wrote:
>> On Fri, Aug 30, 2024 at 02:34:56PM +0200, Bert Karwatzki wrote:
>>> Since linux next-20240820 the following messages appears when booting:
>>>
>>> [    T1] smp: Bringing up secondary CPUs ...
>>> [    T1] smpboot: x86: Booting SMP configuration:
>>> [    T1] .... node  #0, CPUs:        #2  #4  #6  #8 #10 #12 #14  #1
>>> This is the line I'm concerend about:
>>> [    T1] psi: inconsistent task state! task=61:cpuhp/3 cpu=0 psi_flags=4 clear=0 set=4
>>> [    T1]   #3  #5  #7  #9 #11 #13 #15
>>> [    T1] Spectre V2 : Update user space SMT mitigation: STIBP always-on
>>> [    T1] smp: Brought up 1 node, 16 CPUs
>>> [    T1] smpboot: Total of 16 processors activated (102216.16 BogoMIPS)
>>>
>>> I bisected this to commit 152e11f6df29 ("sched/fair: Implement delayed dequeue").
>>> Is this normal or is this something I should worry about?
>>>
>>> Bert Karwatzki
>>
>> I am also getting a similar error on boot, and bisected it to the same commit:
>>
>> [    0.342931] psi: inconsistent task state! task=15:rcu_tasks_trace cpu=0 psi_flags=4 clear=0 set=4
>>
>> #regzbot introduced: 152e11f6df293e816a6a37c69757033cdc72667d
> 
> Just another data point, while booting 6.12-rc1 on a Turris Omnia:
> 
> [    0.000000] Linux version 6.12.0-rc1 (XXX) (arm-linux-gnueabihf-gcc (Debian 14.2.0-1) 14.2.0, GNU ld (GNU Binutils for Debian) 2.43.1) #1 SMP Thu Oct  3 06:59:25 CEST 2024
> [    0.000000] CPU: ARMv7 Processor [414fc091] revision 1 (ARMv7), cr=10c5387d
> [    0.000000] CPU: PIPT / VIPT nonaliasing data cache, VIPT aliasing instruction cache
> [    0.000000] OF: fdt: Machine model: Turris Omnia
> ...
> [    0.000867] CPU0: thread -1, cpu 0, socket 0, mpidr 80000000
> [    0.000876] psi: inconsistent task state! task=2:kthreadd cpu=0 psi_flags=4 clear=0 set=4
> 

Not sure if someone took a stab at this but I haven't seen the "psi:
inconsistent task state" warning with the below diff. I'm not sure if my
approach is right which if why I'm pasting the diff before sending out
an official series. Any comments or testing is greatly appreciated.

The diff is based on:

     git.kernel.org/pub/scm/linux/kernel/git/peterz/queue.git sched/urgent

at commit d4ac164bde7a ("sched/eevdf: Fix wakeup-preempt by checking
cfs_rq->nr_running")

My approach was as follows:

o psi_dequeue() relied on psi_sched_switch() to set the PSI flags
   appropriately for a dequeued task. However, psi_sched_switch() used
   "!task_on_rq_queued(prev)" to judge if the prev task is blocked which
   is now untrue with DELAYED_DEQUEUE. Fix it by checking
   "p->se.sched_delayed" as well. I also added a matching check for
   ENQUEUE_DELAYED for psi_enqueue().

o With the above, the warning was put off for a few more seconds but it
   still appeared. I dumped all PSI flag transition along with
   "tsk->se.sched_delayed" to see what trips it and I saw the following
   state changes for the task that finally tripped it:

     psi: task state: task=18:rcu_preempt cpu=0 psi_flags=0 clear=0 set=0 delayed=1
     psi: task state: task=18:rcu_preempt cpu=128 psi_flags=0 clear=0 set=4 delayed=1
     psi: task state: task=18:rcu_preempt cpu=128 psi_flags=4 clear=0 set=4 delayed=0
     psi: inconsistent task state! task=18:rcu_preempt cpu=128 psi_flags=4 clear=0 set=4 delayed=0

   Note that cpu switched with "tsk->se.sched_delayed" still set which
   got me looking at the task migration path. The warning added below
   in "deactivate_task()" tripped without fail, just before the PSI
   warning was logged.

   To prevent migration of a delayed entity (XXX: Is it a good idea?)
   we do a "account_task_dequeue()" in the delayed dequeue case to
   remove the task from the "rq->cfs_list", thus removing it from the
   purview of the load balancer.

o With the above change, I only managed to trip the deactivate_task()
   WARN_ON() and immediately the PSI warning in the NUMA balancing path

     ------------[ cut here ]------------
     p->se.sched_delayed
     WARNING: CPU: 75 PID: 473 at kernel/sched/core.c:2075 deactivate_task+0xa6/0xc0
     Modules linked in: ...
     CPU: 75 UID: 0 PID: 473 Comm: migration/75 Not tainted 6.12.0-rc1-peterz-sched-urgent-psi-fix+ #32
     Hardware name: Dell Inc. PowerEdge R6525/024PW1, BIOS 2.7.3 03/30/2022
     Stopper: multi_cpu_stop+0x0/0x110 <- migrate_swap+0xd7/0x150
     RIP: 0010:deactivate_task+0xa6/0xc0
     Code: ...
     RSP: 0018:ffff9f210e12fdc0 EFLAGS: 00010086
     RAX: 0000000000000000 RBX: 0000000000000000 RCX: 0000000000000027
     RDX: ffff90116ffa18c8 RSI: 0000000000000001 RDI: ffff90116ffa18c0
     RBP: ffff8fd2d8559ac0 R08: 0000000000000003 R09: 0000000000000000
     R10: 64656863732e6573 R11: 646579616c65645f R12: ffff90116ffb6500
     R13: ffff90116ffb6500 R14: 0000000000000004 R15: ffff8fd2f28f433c
     FS:  0000000000000000(0000) GS:ffff90116ff80000(0000) knlGS:0000000000000000
     CS:  0010 DS: 0000 ES: 0000 CR0: 0000000080050033
     CR2: 000055748a34e000 CR3: 000000807974e004 CR4: 0000000000f70ef0
     PKRU: 55555554
     Call Trace:
      <TASK>
      ? __warn+0x88/0x130
      ? deactivate_task+0xa6/0xc0
      ? report_bug+0x18e/0x1a0
      ? prb_read_valid+0x1b/0x30
      ? handle_bug+0x5b/0xa0
      ? exc_invalid_op+0x18/0x70
      ? asm_exc_invalid_op+0x1a/0x20
      ? deactivate_task+0xa6/0xc0
      __migrate_swap_task.part.0+0xbe/0x180
      migrate_swap_stop+0x1b6/0x1f0
      multi_cpu_stop+0x6e/0x110
      ? __pfx_multi_cpu_stop+0x10/0x10
      cpu_stopper_thread+0x97/0x160
      ? __pfx_smpboot_thread_fn+0x10/0x10
      smpboot_thread_fn+0xdd/0x1d0
      kthread+0xd3/0x100
      ? __pfx_kthread+0x10/0x10
      ret_from_fork+0x34/0x50
      ? __pfx_kthread+0x10/0x10
      ret_from_fork_asm+0x1a/0x30
      </TASK>
     ---[ end trace 0000000000000000 ]---

   From some logging, I can say the "dst_task" is the one that is
   delayed but I could not go up the stack to find out how it is
   chosen for the swap. For this RFC, I just block the delayed
   entity in "__migrate_swap_task()" and set the "p->wake_cpu"
   to redirect the next wakeup to the appropriate NUMA node.

I haven't encountered any warnings with my machine going for a while now
but I haven't tested any fancy cgroups scenarios yet either; Mileage may
vary :)

diff --git a/kernel/sched/core.c b/kernel/sched/core.c
index 43e453ab7e20..b55b52b081ba 100644
--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -2014,7 +2014,9 @@ void enqueue_task(struct rq *rq, struct task_struct *p, int flags)
  
  	if (!(flags & ENQUEUE_RESTORE)) {
  		sched_info_enqueue(rq, p);
-		psi_enqueue(p, (flags & ENQUEUE_WAKEUP) && !(flags & ENQUEUE_MIGRATED));
+		/* Delayed tasks are considered dequeued by PSI tracking */
+		psi_enqueue(p, ((flags & ENQUEUE_WAKEUP) && !(flags & ENQUEUE_MIGRATED)) ||
+			       (flags & ENQUEUE_DELAYED));
  	}
  
  	p->sched_class->enqueue_task(rq, p, flags);
@@ -2069,6 +2071,9 @@ void deactivate_task(struct rq *rq, struct task_struct *p, int flags)
  {
  	SCHED_WARN_ON(flags & DEQUEUE_SLEEP);
  
+	/* Delayed tasks should not be migrated */
+	SCHED_WARN_ON(p->se.sched_delayed);
+
  	WRITE_ONCE(p->on_rq, TASK_ON_RQ_MIGRATING);
  	ASSERT_EXCLUSIVE_WRITER(p->on_rq);
  
@@ -3298,9 +3303,21 @@ static void __migrate_swap_task(struct task_struct *p, int cpu)
  		struct rq_flags srf, drf;
  
  		src_rq = task_rq(p);
-		dst_rq = cpu_rq(cpu);
-
  		rq_pin_lock(src_rq, &srf);
+
+		if (p->se.sched_delayed) {
+			block_task(src_rq, p, DEQUEUE_DELAYED);
+			rq_unpin_lock(src_rq, &srf);
+
+			/*
+			 * Make it appear we last ran on the preferred
+			 * node. See the comment below.
+			 */
+			p->wake_cpu = cpu;
+			return;
+		}
+
+		dst_rq = cpu_rq(cpu);
  		rq_pin_lock(dst_rq, &drf);
  
  		deactivate_task(src_rq, p, 0);
@@ -6667,7 +6684,14 @@ static void __sched notrace __schedule(int sched_mode)
  
  		migrate_disable_switch(rq, prev);
  		psi_account_irqtime(rq, prev, next);
-		psi_sched_switch(prev, next, !task_on_rq_queued(prev));
+
+		/*
+		 * psi_task_switch() is responsible for clearing TSK_RUNNING
+		 * and TSK_IOWAIT which psi_dequeue() skips for a task going
+		 * to sleep (see comment there). Consider a delayed entity
+		 * as one that has gone to sleep for PSI accounting.
+		 */
+		psi_sched_switch(prev, next, !task_on_rq_queued(prev) || prev->se.sched_delayed);
  
  		trace_sched_switch(preempt, prev, next, prev_state);
  
diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index ab497fafa7be..cf02d202ab0c 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -3661,18 +3661,40 @@ static inline void update_scan_period(struct task_struct *p, int new_cpu)
  
  #endif /* CONFIG_NUMA_BALANCING */
  
+#ifdef CONFIG_SMP
+
+static void
+account_task_enqueue(struct cfs_rq *cfs_rq, struct sched_entity *se)
+{
+	struct rq *rq = rq_of(cfs_rq);
+
+	account_numa_enqueue(rq, task_of(se));
+	list_add(&se->group_node, &rq->cfs_tasks);
+}
+
+static void
+account_task_dequeue(struct cfs_rq *cfs_rq, struct sched_entity *se)
+{
+	account_numa_dequeue(rq_of(cfs_rq), task_of(se));
+	list_del_init(&se->group_node);
+}
+
+#else
+
+static void
+account_task_enqueue(struct cfs_rq *cfs_rq, struct sched_entity *se) { }
+static void
+account_task_dequeue(struct cfs_rq *cfs_rq, struct sched_entity *se) { }
+
+#endif
+
  static void
  account_entity_enqueue(struct cfs_rq *cfs_rq, struct sched_entity *se)
  {
  	update_load_add(&cfs_rq->load, se->load.weight);
-#ifdef CONFIG_SMP
-	if (entity_is_task(se)) {
-		struct rq *rq = rq_of(cfs_rq);
+	if (entity_is_task(se) && !se->sched_delayed)
+		account_task_enqueue(cfs_rq, se);
  
-		account_numa_enqueue(rq, task_of(se));
-		list_add(&se->group_node, &rq->cfs_tasks);
-	}
-#endif
  	cfs_rq->nr_running++;
  	if (se_is_idle(se))
  		cfs_rq->idle_nr_running++;
@@ -3682,12 +3704,11 @@ static void
  account_entity_dequeue(struct cfs_rq *cfs_rq, struct sched_entity *se)
  {
  	update_load_sub(&cfs_rq->load, se->load.weight);
-#ifdef CONFIG_SMP
-	if (entity_is_task(se)) {
-		account_numa_dequeue(rq_of(cfs_rq), task_of(se));
-		list_del_init(&se->group_node);
-	}
-#endif
+
+	/* Delayed tasks are already dequeued the first time */
+	if (entity_is_task(se) && !se->sched_delayed)
+		account_task_dequeue(cfs_rq, se);
+
  	cfs_rq->nr_running--;
  	if (se_is_idle(se))
  		cfs_rq->idle_nr_running--;
@@ -6943,6 +6964,10 @@ requeue_delayed_entity(struct sched_entity *se)
  
  	update_load_avg(cfs_rq, se, 0);
  	se->sched_delayed = 0;
+
+	if (entity_is_task(se))
+		account_task_enqueue(cfs_rq, se);
+
  }
  
  /*
@@ -7190,10 +7215,18 @@ static int dequeue_entities(struct rq *rq, struct sched_entity *se, int flags)
   */
  static bool dequeue_task_fair(struct rq *rq, struct task_struct *p, int flags)
  {
-	if (!(p->se.sched_delayed && (task_on_rq_migrating(p) || (flags & DEQUEUE_SAVE))))
+	struct sched_entity *se = &p->se;
+
+	if (!(se->sched_delayed && (task_on_rq_migrating(p) || (flags & DEQUEUE_SAVE))))
  		util_est_dequeue(&rq->cfs, p);
  
-	if (dequeue_entities(rq, &p->se, flags) < 0) {
+	if (dequeue_entities(rq, se, flags) < 0) {
+		/*
+		 * Remove delayed entity from rq->cfs_tasks list
+		 * to prevent load balancer from migrating it
+		 * away.
+		 */
+		account_task_dequeue(cfs_rq_of(se), se);
  		util_est_update(&rq->cfs, p, DEQUEUE_SLEEP);
  		return false;
  	}
--

The above changes were arrived at by experimenting. If there are no
obvious objections, I'll send a clean series after some more testing.
Any and all comments are highly appreciated.
-- 
Thanks and Regards,
Prateek

Re: [REGRESSION] Re: [PATCH 17/24] sched/fair: Implement delayed dequeue

[Peter Zijlstra]

On Fri, Oct 04, 2024 at 04:40:08PM +0530, K Prateek Nayak wrote:
> Hello folks,
> 
> On 10/3/2024 11:01 AM, Klaus Kudielka wrote:
> > On Sun, 2024-09-22 at 16:45 +0100, Chris Bainbridge wrote:
> > > On Fri, Aug 30, 2024 at 02:34:56PM +0200, Bert Karwatzki wrote:
> > > > Since linux next-20240820 the following messages appears when booting:
> > > > 
> > > > [    T1] smp: Bringing up secondary CPUs ...
> > > > [    T1] smpboot: x86: Booting SMP configuration:
> > > > [    T1] .... node  #0, CPUs:        #2  #4  #6  #8 #10 #12 #14  #1
> > > > This is the line I'm concerend about:
> > > > [    T1] psi: inconsistent task state! task=61:cpuhp/3 cpu=0 psi_flags=4 clear=0 set=4
> > > > [    T1]   #3  #5  #7  #9 #11 #13 #15
> > > > [    T1] Spectre V2 : Update user space SMT mitigation: STIBP always-on
> > > > [    T1] smp: Brought up 1 node, 16 CPUs
> > > > [    T1] smpboot: Total of 16 processors activated (102216.16 BogoMIPS)
> > > > 
> > > > I bisected this to commit 152e11f6df29 ("sched/fair: Implement delayed dequeue").
> > > > Is this normal or is this something I should worry about?
> > > > 
> > > > Bert Karwatzki
> > > 
> > > I am also getting a similar error on boot, and bisected it to the same commit:
> > > 
> > > [    0.342931] psi: inconsistent task state! task=15:rcu_tasks_trace cpu=0 psi_flags=4 clear=0 set=4
> > > 
> > > #regzbot introduced: 152e11f6df293e816a6a37c69757033cdc72667d
> > 
> > Just another data point, while booting 6.12-rc1 on a Turris Omnia:
> > 
> > [    0.000000] Linux version 6.12.0-rc1 (XXX) (arm-linux-gnueabihf-gcc (Debian 14.2.0-1) 14.2.0, GNU ld (GNU Binutils for Debian) 2.43.1) #1 SMP Thu Oct  3 06:59:25 CEST 2024
> > [    0.000000] CPU: ARMv7 Processor [414fc091] revision 1 (ARMv7), cr=10c5387d
> > [    0.000000] CPU: PIPT / VIPT nonaliasing data cache, VIPT aliasing instruction cache
> > [    0.000000] OF: fdt: Machine model: Turris Omnia
> > ...
> > [    0.000867] CPU0: thread -1, cpu 0, socket 0, mpidr 80000000
> > [    0.000876] psi: inconsistent task state! task=2:kthreadd cpu=0 psi_flags=4 clear=0 set=4
> > 
> 
> Not sure if someone took a stab at this but I haven't seen the "psi:

I'm aware of the issue, but since it's just statistics and not
anything 'important', I've been spending my time on those crashing bugs.

> inconsistent task state" warning with the below diff. I'm not sure if my
> approach is right which if why I'm pasting the diff before sending out
> an official series. Any comments or testing is greatly appreciated.
> 
> The diff is based on:
> 
>     git.kernel.org/pub/scm/linux/kernel/git/peterz/queue.git sched/urgent
> 
> at commit d4ac164bde7a ("sched/eevdf: Fix wakeup-preempt by checking
> cfs_rq->nr_running")

Thanks, I just pushed all that out to tip/sched/urgent.

> My approach was as follows:
> 
> o psi_dequeue() relied on psi_sched_switch() to set the PSI flags
>   appropriately for a dequeued task. However, psi_sched_switch() used
>   "!task_on_rq_queued(prev)" to judge if the prev task is blocked which
>   is now untrue with DELAYED_DEQUEUE. Fix it by checking
>   "p->se.sched_delayed" as well. I also added a matching check for
>   ENQUEUE_DELAYED for psi_enqueue().

We already determine the whole sleep state earlier, the whole having
called block_task() is a clue, perhaps we should propagate that state
instead of trying to divinate it again.

> o With the above, the warning was put off for a few more seconds but it
>   still appeared. I dumped all PSI flag transition along with
>   "tsk->se.sched_delayed" to see what trips it and I saw the following
>   state changes for the task that finally tripped it:
> 
>     psi: task state: task=18:rcu_preempt cpu=0 psi_flags=0 clear=0 set=0 delayed=1
>     psi: task state: task=18:rcu_preempt cpu=128 psi_flags=0 clear=0 set=4 delayed=1
>     psi: task state: task=18:rcu_preempt cpu=128 psi_flags=4 clear=0 set=4 delayed=0
>     psi: inconsistent task state! task=18:rcu_preempt cpu=128 psi_flags=4 clear=0 set=4 delayed=0
> 
>   Note that cpu switched with "tsk->se.sched_delayed" still set which
>   got me looking at the task migration path. The warning added below
>   in "deactivate_task()" tripped without fail, just before the PSI
>   warning was logged.
> 
>   To prevent migration of a delayed entity (XXX: Is it a good idea?)

It is not. By migrating the entities they can get picked sooner and the
delayed thing gets removed sooner. Less 'hidden' weight.

>   we do a "account_task_dequeue()" in the delayed dequeue case to
>   remove the task from the "rq->cfs_list", thus removing it from the
>   purview of the load balancer.

Anyway, assuming PSI wants to preserve current semantics, does something
like the below work?

---
diff --git a/kernel/sched/core.c b/kernel/sched/core.c
index 43e453ab7e20..0d766fb9fbc4 100644
--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -2012,7 +2012,7 @@ void enqueue_task(struct rq *rq, struct task_struct *p, int flags)
 	if (!(flags & ENQUEUE_NOCLOCK))
 		update_rq_clock(rq);
 
-	if (!(flags & ENQUEUE_RESTORE)) {
+	if (!(flags & ENQUEUE_RESTORE) && !p->se.sched_delayed) {
 		sched_info_enqueue(rq, p);
 		psi_enqueue(p, (flags & ENQUEUE_WAKEUP) && !(flags & ENQUEUE_MIGRATED));
 	}
@@ -2039,7 +2039,7 @@ inline bool dequeue_task(struct rq *rq, struct task_struct *p, int flags)
 	if (!(flags & DEQUEUE_NOCLOCK))
 		update_rq_clock(rq);
 
-	if (!(flags & DEQUEUE_SAVE)) {
+	if (!(flags & DEQUEUE_SAVE) && !p->se.sched_delayed) {
 		sched_info_dequeue(rq, p);
 		psi_dequeue(p, flags & DEQUEUE_SLEEP);
 	}
@@ -6537,6 +6537,7 @@ static void __sched notrace __schedule(int sched_mode)
 	 * as a preemption by schedule_debug() and RCU.
 	 */
 	bool preempt = sched_mode > SM_NONE;
+	bool block = false;
 	unsigned long *switch_count;
 	unsigned long prev_state;
 	struct rq_flags rf;
@@ -6622,6 +6623,7 @@ static void __sched notrace __schedule(int sched_mode)
 			 * After this, schedule() must not care about p->state any more.
 			 */
 			block_task(rq, prev, flags);
+			block = true;
 		}
 		switch_count = &prev->nvcsw;
 	}
@@ -6667,7 +6669,7 @@ static void __sched notrace __schedule(int sched_mode)
 
 		migrate_disable_switch(rq, prev);
 		psi_account_irqtime(rq, prev, next);
-		psi_sched_switch(prev, next, !task_on_rq_queued(prev));
+		psi_sched_switch(prev, next, block);
 
 		trace_sched_switch(preempt, prev, next, prev_state);
 

Re: [REGRESSION] Re: [PATCH 17/24] sched/fair: Implement delayed dequeue

[Johannes Weiner]

On Fri, Oct 04, 2024 at 02:35:06PM +0200, Peter Zijlstra wrote:
> On Fri, Oct 04, 2024 at 04:40:08PM +0530, K Prateek Nayak wrote:
> > Hello folks,
> > 
> > On 10/3/2024 11:01 AM, Klaus Kudielka wrote:
> > > On Sun, 2024-09-22 at 16:45 +0100, Chris Bainbridge wrote:
> > > > On Fri, Aug 30, 2024 at 02:34:56PM +0200, Bert Karwatzki wrote:
> > > > > Since linux next-20240820 the following messages appears when booting:
> > > > > 
> > > > > [    T1] smp: Bringing up secondary CPUs ...
> > > > > [    T1] smpboot: x86: Booting SMP configuration:
> > > > > [    T1] .... node  #0, CPUs:        #2  #4  #6  #8 #10 #12 #14  #1
> > > > > This is the line I'm concerend about:
> > > > > [    T1] psi: inconsistent task state! task=61:cpuhp/3 cpu=0 psi_flags=4 clear=0 set=4
> > > > > [    T1]   #3  #5  #7  #9 #11 #13 #15
> > > > > [    T1] Spectre V2 : Update user space SMT mitigation: STIBP always-on
> > > > > [    T1] smp: Brought up 1 node, 16 CPUs
> > > > > [    T1] smpboot: Total of 16 processors activated (102216.16 BogoMIPS)
> > > > > 
> > > > > I bisected this to commit 152e11f6df29 ("sched/fair: Implement delayed dequeue").
> > > > > Is this normal or is this something I should worry about?
> > > > > 
> > > > > Bert Karwatzki
> > > > 
> > > > I am also getting a similar error on boot, and bisected it to the same commit:
> > > > 
> > > > [    0.342931] psi: inconsistent task state! task=15:rcu_tasks_trace cpu=0 psi_flags=4 clear=0 set=4
> > > > 
> > > > #regzbot introduced: 152e11f6df293e816a6a37c69757033cdc72667d
> > > 
> > > Just another data point, while booting 6.12-rc1 on a Turris Omnia:
> > > 
> > > [    0.000000] Linux version 6.12.0-rc1 (XXX) (arm-linux-gnueabihf-gcc (Debian 14.2.0-1) 14.2.0, GNU ld (GNU Binutils for Debian) 2.43.1) #1 SMP Thu Oct  3 06:59:25 CEST 2024
> > > [    0.000000] CPU: ARMv7 Processor [414fc091] revision 1 (ARMv7), cr=10c5387d
> > > [    0.000000] CPU: PIPT / VIPT nonaliasing data cache, VIPT aliasing instruction cache
> > > [    0.000000] OF: fdt: Machine model: Turris Omnia
> > > ...
> > > [    0.000867] CPU0: thread -1, cpu 0, socket 0, mpidr 80000000
> > > [    0.000876] psi: inconsistent task state! task=2:kthreadd cpu=0 psi_flags=4 clear=0 set=4
> > > 
> > 
> > Not sure if someone took a stab at this but I haven't seen the "psi:
> 
> I'm aware of the issue, but since it's just statistics and not
> anything 'important', I've been spending my time on those crashing bugs.
> 
> > inconsistent task state" warning with the below diff. I'm not sure if my
> > approach is right which if why I'm pasting the diff before sending out
> > an official series. Any comments or testing is greatly appreciated.

This fixes the bug for me.

> Anyway, assuming PSI wants to preserve current semantics, does something
> like the below work?

This doesn't. But it's a different corruption now:

[    2.298408] psi: inconsistent task state! task=24:cpuhp/1 cpu=1 psi_flags=10 clear=14 set=0

It's psi_sched_switch(.sleep=true) trying to clear the running state
and the queued state, but finds only the running state set.

I don't think it's an erroneous dequeue. __schedule() has that
block_task() dequeue before the switch, but the DEQUEUE_SLEEP makes it
a no-op and leaves the combined update to psi_sched_switch().

It looks instead it's missing an enqueue callback. This triggers:

diff --git a/kernel/sched/psi.c b/kernel/sched/psi.c
index 020d58967d4e..09a251e3986d 100644
--- a/kernel/sched/psi.c
+++ b/kernel/sched/psi.c
@@ -922,6 +922,8 @@ void psi_task_switch(struct task_struct *prev, struct task_struct *next,
 	u64 now = cpu_clock(cpu);
 
 	if (next->pid) {
+		WARN_ON_ONCE(!(next->psi_flags & TSK_RUNNING));
+
 		psi_flags_change(next, 0, TSK_ONCPU);
 		/*
 		 * Set TSK_ONCPU on @next's cgroups. If @next shares any

> ---
> diff --git a/kernel/sched/core.c b/kernel/sched/core.c
> index 43e453ab7e20..0d766fb9fbc4 100644
> --- a/kernel/sched/core.c
> +++ b/kernel/sched/core.c
> @@ -2012,7 +2012,7 @@ void enqueue_task(struct rq *rq, struct task_struct *p, int flags)
>  	if (!(flags & ENQUEUE_NOCLOCK))
>  		update_rq_clock(rq);
>  
> -	if (!(flags & ENQUEUE_RESTORE)) {
> +	if (!(flags & ENQUEUE_RESTORE) && !p->se.sched_delayed) {
>  		sched_info_enqueue(rq, p);
>  		psi_enqueue(p, (flags & ENQUEUE_WAKEUP) && !(flags & ENQUEUE_MIGRATED));
>  	}

... we must be skipping here when we shouldn't.

I tried moving it past ->enqueue_task(), like we did for uclamp, to
get the enqueue when sched_delayed is cleared by the callback and task
is considered properly queued again. However, that results in yet
another problem:

[    4.624776] psi: inconsistent task state! task=161:systemd-ssh-gen cpu=1 psi_flags=15 clear=14 set=1

This is a psi_sched_switch() trying to clear running|queued and set
iowait. Task is already running|queued|iowait. It looks like we had a
genuine wakeup that was signaled with psi_enqueue(.wakeup=false) (so
it didn't clear the iowait).

> @@ -2039,7 +2039,7 @@ inline bool dequeue_task(struct rq *rq, struct task_struct *p, int flags)
>  	if (!(flags & DEQUEUE_NOCLOCK))
>  		update_rq_clock(rq);
>  
> -	if (!(flags & DEQUEUE_SAVE)) {
> +	if (!(flags & DEQUEUE_SAVE) && !p->se.sched_delayed) {
>  		sched_info_dequeue(rq, p);
>  		psi_dequeue(p, flags & DEQUEUE_SLEEP);
>  	}
> @@ -6537,6 +6537,7 @@ static void __sched notrace __schedule(int sched_mode)
>  	 * as a preemption by schedule_debug() and RCU.
>  	 */
>  	bool preempt = sched_mode > SM_NONE;
> +	bool block = false;
>  	unsigned long *switch_count;
>  	unsigned long prev_state;
>  	struct rq_flags rf;
> @@ -6622,6 +6623,7 @@ static void __sched notrace __schedule(int sched_mode)
>  			 * After this, schedule() must not care about p->state any more.
>  			 */
>  			block_task(rq, prev, flags);
> +			block = true;
>  		}
>  		switch_count = &prev->nvcsw;
>  	}
> @@ -6667,7 +6669,7 @@ static void __sched notrace __schedule(int sched_mode)
>  
>  		migrate_disable_switch(rq, prev);
>  		psi_account_irqtime(rq, prev, next);
> -		psi_sched_switch(prev, next, !task_on_rq_queued(prev));
> +		psi_sched_switch(prev, next, block);
>  
>  		trace_sched_switch(preempt, prev, next, prev_state);

Re: [REGRESSION] Re: [PATCH 17/24] sched/fair: Implement delayed dequeue

[K Prateek Nayak]

Hello Johannes, Peter,

On 10/4/2024 7:27 PM, Johannes Weiner wrote:
> On Fri, Oct 04, 2024 at 02:35:06PM +0200, Peter Zijlstra wrote:
>> On Fri, Oct 04, 2024 at 04:40:08PM +0530, K Prateek Nayak wrote:
>>> Hello folks,
>>>
>>> On 10/3/2024 11:01 AM, Klaus Kudielka wrote:
>>>> On Sun, 2024-09-22 at 16:45 +0100, Chris Bainbridge wrote:
>>>>> On Fri, Aug 30, 2024 at 02:34:56PM +0200, Bert Karwatzki wrote:
>>>>>> Since linux next-20240820 the following messages appears when booting:
>>>>>>
>>>>>> [    T1] smp: Bringing up secondary CPUs ...
>>>>>> [    T1] smpboot: x86: Booting SMP configuration:
>>>>>> [    T1] .... node  #0, CPUs:        #2  #4  #6  #8 #10 #12 #14  #1
>>>>>> This is the line I'm concerend about:
>>>>>> [    T1] psi: inconsistent task state! task=61:cpuhp/3 cpu=0 psi_flags=4 clear=0 set=4
>>>>>> [    T1]   #3  #5  #7  #9 #11 #13 #15
>>>>>> [    T1] Spectre V2 : Update user space SMT mitigation: STIBP always-on
>>>>>> [    T1] smp: Brought up 1 node, 16 CPUs
>>>>>> [    T1] smpboot: Total of 16 processors activated (102216.16 BogoMIPS)
>>>>>>
>>>>>> I bisected this to commit 152e11f6df29 ("sched/fair: Implement delayed dequeue").
>>>>>> Is this normal or is this something I should worry about?
>>>>>>
>>>>>> Bert Karwatzki
>>>>>
>>>>> I am also getting a similar error on boot, and bisected it to the same commit:
>>>>>
>>>>> [    0.342931] psi: inconsistent task state! task=15:rcu_tasks_trace cpu=0 psi_flags=4 clear=0 set=4
>>>>>
>>>>> #regzbot introduced: 152e11f6df293e816a6a37c69757033cdc72667d
>>>>
>>>> Just another data point, while booting 6.12-rc1 on a Turris Omnia:
>>>>
>>>> [    0.000000] Linux version 6.12.0-rc1 (XXX) (arm-linux-gnueabihf-gcc (Debian 14.2.0-1) 14.2.0, GNU ld (GNU Binutils for Debian) 2.43.1) #1 SMP Thu Oct  3 06:59:25 CEST 2024
>>>> [    0.000000] CPU: ARMv7 Processor [414fc091] revision 1 (ARMv7), cr=10c5387d
>>>> [    0.000000] CPU: PIPT / VIPT nonaliasing data cache, VIPT aliasing instruction cache
>>>> [    0.000000] OF: fdt: Machine model: Turris Omnia
>>>> ...
>>>> [    0.000867] CPU0: thread -1, cpu 0, socket 0, mpidr 80000000
>>>> [    0.000876] psi: inconsistent task state! task=2:kthreadd cpu=0 psi_flags=4 clear=0 set=4
>>>>
>>>
>>> Not sure if someone took a stab at this but I haven't seen the "psi:
>>
>> I'm aware of the issue, but since it's just statistics and not
>> anything 'important', I've been spending my time on those crashing bugs.
>>
>>> inconsistent task state" warning with the below diff. I'm not sure if my
>>> approach is right which if why I'm pasting the diff before sending out
>>> an official series. Any comments or testing is greatly appreciated.
> 
> This fixes the bug for me.

Thank you for testing :)

> 
>> Anyway, assuming PSI wants to preserve current semantics, does something
>> like the below work?
> 
> This doesn't. But it's a different corruption now:
> 
> [    2.298408] psi: inconsistent task state! task=24:cpuhp/1 cpu=1 psi_flags=10 clear=14 set=0

I hit the same log (clear 14, set 0) and I tried the below changes on
top of Peter's diff:

diff --git a/kernel/sched/core.c b/kernel/sched/core.c
index 0d766fb9fbc4..9cf3d4359994 100644
--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -2012,9 +2012,10 @@ void enqueue_task(struct rq *rq, struct task_struct *p, int flags)
  	if (!(flags & ENQUEUE_NOCLOCK))
  		update_rq_clock(rq);
  
-	if (!(flags & ENQUEUE_RESTORE) && !p->se.sched_delayed) {
+	if (!(flags & ENQUEUE_RESTORE) && (!p->se.sched_delayed || (flags & ENQUEUE_DELAYED))) {
  		sched_info_enqueue(rq, p);
-		psi_enqueue(p, (flags & ENQUEUE_WAKEUP) && !(flags & ENQUEUE_MIGRATED));
+		psi_enqueue(p, ((flags & ENQUEUE_WAKEUP) && !(flags & ENQUEUE_MIGRATED)) ||
+			       (flags & ENQUEUE_DELAYED));
  	}
  
  	p->sched_class->enqueue_task(rq, p, flags);
--

... but it just changes the warning to:

     psi: task underflow! cpu=65 t=0 tasks=[0 0 0 0] clear=1 set=4
     psi: task underflow! cpu=31 t=0 tasks=[0 0 1 0] clear=1 set=0

Doing a dump_stack(), I see it come from psi_enqueue() and
psi_ttwu_dequeue() and I see "clear=1" as the common theme. I've
stared at it for a while but I'm at a loss currently. If something
jumps out, I'll update here.

Thank you again both for taking a look.

-- 
Thanks and Regards,
Prateek

> 
> It's psi_sched_switch(.sleep=true) trying to clear the running state
> and the queued state, but finds only the running state set.
> 
> I don't think it's an erroneous dequeue. __schedule() has that
> block_task() dequeue before the switch, but the DEQUEUE_SLEEP makes it
> a no-op and leaves the combined update to psi_sched_switch().
> 
> It looks instead it's missing an enqueue callback. This triggers:
> 
> diff --git a/kernel/sched/psi.c b/kernel/sched/psi.c
> index 020d58967d4e..09a251e3986d 100644
> --- a/kernel/sched/psi.c
> +++ b/kernel/sched/psi.c
> @@ -922,6 +922,8 @@ void psi_task_switch(struct task_struct *prev, struct task_struct *next,
>   	u64 now = cpu_clock(cpu);
>   
>   	if (next->pid) {
> +		WARN_ON_ONCE(!(next->psi_flags & TSK_RUNNING));
> +
>   		psi_flags_change(next, 0, TSK_ONCPU);
>   		/*
>   		 * Set TSK_ONCPU on @next's cgroups. If @next shares any
> 
>> ---
>> diff --git a/kernel/sched/core.c b/kernel/sched/core.c
>> index 43e453ab7e20..0d766fb9fbc4 100644
>> --- a/kernel/sched/core.c
>> +++ b/kernel/sched/core.c
>> @@ -2012,7 +2012,7 @@ void enqueue_task(struct rq *rq, struct task_struct *p, int flags)
>>   	if (!(flags & ENQUEUE_NOCLOCK))
>>   		update_rq_clock(rq);
>>   
>> -	if (!(flags & ENQUEUE_RESTORE)) {
>> +	if (!(flags & ENQUEUE_RESTORE) && !p->se.sched_delayed) {
>>   		sched_info_enqueue(rq, p);
>>   		psi_enqueue(p, (flags & ENQUEUE_WAKEUP) && !(flags & ENQUEUE_MIGRATED));
>>   	}
> 
> ... we must be skipping here when we shouldn't.
> 
> I tried moving it past ->enqueue_task(), like we did for uclamp, to
> get the enqueue when sched_delayed is cleared by the callback and task
> is considered properly queued again. However, that results in yet
> another problem:
> 
> [    4.624776] psi: inconsistent task state! task=161:systemd-ssh-gen cpu=1 psi_flags=15 clear=14 set=1
> 
> This is a psi_sched_switch() trying to clear running|queued and set
> iowait. Task is already running|queued|iowait. It looks like we had a
> genuine wakeup that was signaled with psi_enqueue(.wakeup=false) (so
> it didn't clear the iowait).
> 
>> @@ -2039,7 +2039,7 @@ inline bool dequeue_task(struct rq *rq, struct task_struct *p, int flags)
>>   	if (!(flags & DEQUEUE_NOCLOCK))
>>   		update_rq_clock(rq);
>>   
>> -	if (!(flags & DEQUEUE_SAVE)) {
>> +	if (!(flags & DEQUEUE_SAVE) && !p->se.sched_delayed) {
>>   		sched_info_dequeue(rq, p);
>>   		psi_dequeue(p, flags & DEQUEUE_SLEEP);
>>   	}
>> @@ -6537,6 +6537,7 @@ static void __sched notrace __schedule(int sched_mode)
>>   	 * as a preemption by schedule_debug() and RCU.
>>   	 */
>>   	bool preempt = sched_mode > SM_NONE;
>> +	bool block = false;
>>   	unsigned long *switch_count;
>>   	unsigned long prev_state;
>>   	struct rq_flags rf;
>> @@ -6622,6 +6623,7 @@ static void __sched notrace __schedule(int sched_mode)
>>   			 * After this, schedule() must not care about p->state any more.
>>   			 */
>>   			block_task(rq, prev, flags);
>> +			block = true;
>>   		}
>>   		switch_count = &prev->nvcsw;
>>   	}
>> @@ -6667,7 +6669,7 @@ static void __sched notrace __schedule(int sched_mode)
>>   
>>   		migrate_disable_switch(rq, prev);
>>   		psi_account_irqtime(rq, prev, next);
>> -		psi_sched_switch(prev, next, !task_on_rq_queued(prev));
>> +		psi_sched_switch(prev, next, block);
>>   
>>   		trace_sched_switch(preempt, prev, next, prev_state);

Re: [REGRESSION] Re: [PATCH 17/24] sched/fair: Implement delayed dequeue

[K Prateek Nayak]

Hello Peter,

On 10/4/2024 6:05 PM, Peter Zijlstra wrote:
> On Fri, Oct 04, 2024 at 04:40:08PM +0530, K Prateek Nayak wrote:
>> Hello folks,
>>
>> On 10/3/2024 11:01 AM, Klaus Kudielka wrote:
>>> On Sun, 2024-09-22 at 16:45 +0100, Chris Bainbridge wrote:
>>>> On Fri, Aug 30, 2024 at 02:34:56PM +0200, Bert Karwatzki wrote:
>>>>> Since linux next-20240820 the following messages appears when booting:
>>>>>
>>>>> [    T1] smp: Bringing up secondary CPUs ...
>>>>> [    T1] smpboot: x86: Booting SMP configuration:
>>>>> [    T1] .... node  #0, CPUs:        #2  #4  #6  #8 #10 #12 #14  #1
>>>>> This is the line I'm concerend about:
>>>>> [    T1] psi: inconsistent task state! task=61:cpuhp/3 cpu=0 psi_flags=4 clear=0 set=4
>>>>> [    T1]   #3  #5  #7  #9 #11 #13 #15
>>>>> [    T1] Spectre V2 : Update user space SMT mitigation: STIBP always-on
>>>>> [    T1] smp: Brought up 1 node, 16 CPUs
>>>>> [    T1] smpboot: Total of 16 processors activated (102216.16 BogoMIPS)
>>>>>
>>>>> I bisected this to commit 152e11f6df29 ("sched/fair: Implement delayed dequeue").
>>>>> Is this normal or is this something I should worry about?
>>>>>
>>>>> Bert Karwatzki
>>>>
>>>> I am also getting a similar error on boot, and bisected it to the same commit:
>>>>
>>>> [    0.342931] psi: inconsistent task state! task=15:rcu_tasks_trace cpu=0 psi_flags=4 clear=0 set=4
>>>>
>>>> #regzbot introduced: 152e11f6df293e816a6a37c69757033cdc72667d
>>>
>>> Just another data point, while booting 6.12-rc1 on a Turris Omnia:
>>>
>>> [    0.000000] Linux version 6.12.0-rc1 (XXX) (arm-linux-gnueabihf-gcc (Debian 14.2.0-1) 14.2.0, GNU ld (GNU Binutils for Debian) 2.43.1) #1 SMP Thu Oct  3 06:59:25 CEST 2024
>>> [    0.000000] CPU: ARMv7 Processor [414fc091] revision 1 (ARMv7), cr=10c5387d
>>> [    0.000000] CPU: PIPT / VIPT nonaliasing data cache, VIPT aliasing instruction cache
>>> [    0.000000] OF: fdt: Machine model: Turris Omnia
>>> ...
>>> [    0.000867] CPU0: thread -1, cpu 0, socket 0, mpidr 80000000
>>> [    0.000876] psi: inconsistent task state! task=2:kthreadd cpu=0 psi_flags=4 clear=0 set=4
>>>
>>
>> Not sure if someone took a stab at this but I haven't seen the "psi:
> 
> I'm aware of the issue, but since it's just statistics and not
> anything 'important', I've been spending my time on those crashing bugs.
> 
>> inconsistent task state" warning with the below diff. I'm not sure if my
>> approach is right which if why I'm pasting the diff before sending out
>> an official series. Any comments or testing is greatly appreciated.
>>
>> The diff is based on:
>>
>>      git.kernel.org/pub/scm/linux/kernel/git/peterz/queue.git sched/urgent
>>
>> at commit d4ac164bde7a ("sched/eevdf: Fix wakeup-preempt by checking
>> cfs_rq->nr_running")
> 
> Thanks, I just pushed all that out to tip/sched/urgent.
> 
>> My approach was as follows:
>>
>> o psi_dequeue() relied on psi_sched_switch() to set the PSI flags
>>    appropriately for a dequeued task. However, psi_sched_switch() used
>>    "!task_on_rq_queued(prev)" to judge if the prev task is blocked which
>>    is now untrue with DELAYED_DEQUEUE. Fix it by checking
>>    "p->se.sched_delayed" as well. I also added a matching check for
>>    ENQUEUE_DELAYED for psi_enqueue().
> 
> We already determine the whole sleep state earlier, the whole having
> called block_task() is a clue, perhaps we should propagate that state
> instead of trying to divinate it again.

Yup that makes sense!

> 
>> o With the above, the warning was put off for a few more seconds but it
>>    still appeared. I dumped all PSI flag transition along with
>>    "tsk->se.sched_delayed" to see what trips it and I saw the following
>>    state changes for the task that finally tripped it:
>>
>>      psi: task state: task=18:rcu_preempt cpu=0 psi_flags=0 clear=0 set=0 delayed=1
>>      psi: task state: task=18:rcu_preempt cpu=128 psi_flags=0 clear=0 set=4 delayed=1
>>      psi: task state: task=18:rcu_preempt cpu=128 psi_flags=4 clear=0 set=4 delayed=0
>>      psi: inconsistent task state! task=18:rcu_preempt cpu=128 psi_flags=4 clear=0 set=4 delayed=0
>>
>>    Note that cpu switched with "tsk->se.sched_delayed" still set which
>>    got me looking at the task migration path. The warning added below
>>    in "deactivate_task()" tripped without fail, just before the PSI
>>    warning was logged.
>>
>>    To prevent migration of a delayed entity (XXX: Is it a good idea?)
> 
> It is not. By migrating the entities they can get picked sooner and the
> delayed thing gets removed sooner. Less 'hidden' weight.

True that! I was thinking moving queued load could also potentially help
delayed entities being picked faster on the rq where they were delayed.
Both seem to help in one way or the other but I don't have any solid
data to conclusively say which might be better.

> 
>>    we do a "account_task_dequeue()" in the delayed dequeue case to
>>    remove the task from the "rq->cfs_list", thus removing it from the
>>    purview of the load balancer.
> 
> Anyway, assuming PSI wants to preserve current semantics, does something
> like the below work?

I've updated the details from my testing on the parallel thread by
Johannes.

tl;dr I still see PSI warnings, some more tinkering on top of your
changes altered the warning to "psi: task underflow!". So far, no
luck figuring out how that comes about.

Thank you for taking a look and for the quick patch!

-- 
Thanks and Regards,
Prateek

> 
> ---
> diff --git a/kernel/sched/core.c b/kernel/sched/core.c
> index 43e453ab7e20..0d766fb9fbc4 100644
> --- a/kernel/sched/core.c
> +++ b/kernel/sched/core.c
> @@ -2012,7 +2012,7 @@ void enqueue_task(struct rq *rq, struct task_struct *p, int flags)
>   	if (!(flags & ENQUEUE_NOCLOCK))
>   		update_rq_clock(rq);
>   
> -	if (!(flags & ENQUEUE_RESTORE)) {
> +	if (!(flags & ENQUEUE_RESTORE) && !p->se.sched_delayed) {
>   		sched_info_enqueue(rq, p);
>   		psi_enqueue(p, (flags & ENQUEUE_WAKEUP) && !(flags & ENQUEUE_MIGRATED));
>   	}
> @@ -2039,7 +2039,7 @@ inline bool dequeue_task(struct rq *rq, struct task_struct *p, int flags)
>   	if (!(flags & DEQUEUE_NOCLOCK))
>   		update_rq_clock(rq);
>   
> -	if (!(flags & DEQUEUE_SAVE)) {
> +	if (!(flags & DEQUEUE_SAVE) && !p->se.sched_delayed) {
>   		sched_info_dequeue(rq, p);
>   		psi_dequeue(p, flags & DEQUEUE_SLEEP);
>   	}
> @@ -6537,6 +6537,7 @@ static void __sched notrace __schedule(int sched_mode)
>   	 * as a preemption by schedule_debug() and RCU.
>   	 */
>   	bool preempt = sched_mode > SM_NONE;
> +	bool block = false;
>   	unsigned long *switch_count;
>   	unsigned long prev_state;
>   	struct rq_flags rf;
> @@ -6622,6 +6623,7 @@ static void __sched notrace __schedule(int sched_mode)
>   			 * After this, schedule() must not care about p->state any more.
>   			 */
>   			block_task(rq, prev, flags);
> +			block = true;
>   		}
>   		switch_count = &prev->nvcsw;
>   	}
> @@ -6667,7 +6669,7 @@ static void __sched notrace __schedule(int sched_mode)
>   
>   		migrate_disable_switch(rq, prev);
>   		psi_account_irqtime(rq, prev, next);
> -		psi_sched_switch(prev, next, !task_on_rq_queued(prev));
> +		psi_sched_switch(prev, next, block);
>   
>   		trace_sched_switch(preempt, prev, next, prev_state);
>   

Re: [REGRESSION] Re: [PATCH 17/24] sched/fair: Implement delayed dequeue

[K Prateek Nayak]

Hello Johannes, Peter,

On 10/4/2024 10:13 PM, K Prateek Nayak wrote:
> [..snip..]
>>> Anyway, assuming PSI wants to preserve current semantics, does something
>>> like the below work?
>>
>> This doesn't. But it's a different corruption now:
>>
>> [    2.298408] psi: inconsistent task state! task=24:cpuhp/1 cpu=1 psi_flags=10 clear=14 set=0
> 
> I hit the same log (clear 14, set 0) and I tried the below changes on
> top of Peter's diff:
> 
> diff --git a/kernel/sched/core.c b/kernel/sched/core.c
> index 0d766fb9fbc4..9cf3d4359994 100644
> --- a/kernel/sched/core.c
> +++ b/kernel/sched/core.c
> @@ -2012,9 +2012,10 @@ void enqueue_task(struct rq *rq, struct task_struct *p, int flags)
>       if (!(flags & ENQUEUE_NOCLOCK))
>           update_rq_clock(rq);
> 
> -    if (!(flags & ENQUEUE_RESTORE) && !p->se.sched_delayed) {
> +    if (!(flags & ENQUEUE_RESTORE) && (!p->se.sched_delayed || (flags & ENQUEUE_DELAYED))) {
>           sched_info_enqueue(rq, p);
> -        psi_enqueue(p, (flags & ENQUEUE_WAKEUP) && !(flags & ENQUEUE_MIGRATED));
> +        psi_enqueue(p, ((flags & ENQUEUE_WAKEUP) && !(flags & ENQUEUE_MIGRATED)) ||
> +                   (flags & ENQUEUE_DELAYED));
>       }
> 
>       p->sched_class->enqueue_task(rq, p, flags);
> -- 
> 
> ... but it just changes the warning to:
> 
>      psi: task underflow! cpu=65 t=0 tasks=[0 0 0 0] clear=1 set=4
>      psi: task underflow! cpu=31 t=0 tasks=[0 0 1 0] clear=1 set=0
> 
> Doing a dump_stack(), I see it come from psi_enqueue() and
> psi_ttwu_dequeue() and I see "clear=1" as the common theme. I've
> stared at it for a while but I'm at a loss currently. If something
> jumps out, I'll update here.

I could narrow down the crux of the matter to the fact that when a task
is delayed, and the delayed task is then migrated, the wakeup context
may not have any idea that the task was moved from its previous
runqueue. This is the same reason psi_enqueue() considers only ...

     (flags & ENQUEUE_WAKEUP) && !(flags & ENQUEUE_MIGRATED)

... as a wakeup. In case of a wakeup with migration, PSI forgoes
clearing the TSK_IOWAIT flag which seems to be the issue I encountered
in my splat previously.

With that said, the below diff, based on Peter's original approach
currently seems to work for me in the sense that I have not seen the
inconsistent state warning for a while now with my stress test.

Two key points of the approach are:

o It uses "p->migration_flags" to indicate a delayed entity has
   migrated to another runqueue and convey the same during psi_enqueue().

o It adds ENQUEUE_WAKEUP flag alongside ENQUEUE_DELAYED for
   enqueue_task() in ttwu_runnable() since psi_enqueue() needs to know of
   a wakeup without migration to clear the TSK_IOWAIT flag it would have
   set during psi_task_switch() for blocking task and going down the
   stack for enqueue_task_fair(), there seem to be no other observer of
   the ENQUEUE_WAKEUP flag other than psi_enqueue() in the requeue path.

If there are no obvious objections, I'll send a clean patch soon.
In the meantime, here is the diff:

diff --git a/kernel/sched/core.c b/kernel/sched/core.c
index 43e453ab7e20..885801432e9a 100644
--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -2009,12 +2009,19 @@ unsigned long get_wchan(struct task_struct *p)
  
  void enqueue_task(struct rq *rq, struct task_struct *p, int flags)
  {
+	bool wakee_not_migrated = (flags & ENQUEUE_WAKEUP) && !(flags & ENQUEUE_MIGRATED);
+
  	if (!(flags & ENQUEUE_NOCLOCK))
  		update_rq_clock(rq);
  
  	if (!(flags & ENQUEUE_RESTORE)) {
  		sched_info_enqueue(rq, p);
-		psi_enqueue(p, (flags & ENQUEUE_WAKEUP) && !(flags & ENQUEUE_MIGRATED));
+
+		/* Notify PSI that the task was migrated in a delayed state before wakeup. */
+		if ((p->migration_flags & DELAYED_MIGRATED) && !task_on_rq_migrating(p)) {
+			wakee_not_migrated = false;
+			p->migration_flags &= ~DELAYED_MIGRATED;
+		}
  	}
  
  	p->sched_class->enqueue_task(rq, p, flags);
@@ -2023,6 +2030,8 @@ void enqueue_task(struct rq *rq, struct task_struct *p, int flags)
  	 * ->sched_delayed.
  	 */
  	uclamp_rq_inc(rq, p);
+	if (!(flags & ENQUEUE_RESTORE))
+		psi_enqueue(p, wakee_not_migrated);
  
  	if (sched_core_enabled(rq))
  		sched_core_enqueue(rq, p);
@@ -2042,6 +2051,9 @@ inline bool dequeue_task(struct rq *rq, struct task_struct *p, int flags)
  	if (!(flags & DEQUEUE_SAVE)) {
  		sched_info_dequeue(rq, p);
  		psi_dequeue(p, flags & DEQUEUE_SLEEP);
+
+		if (p->se.sched_delayed && task_on_rq_migrating(p))
+			p->migration_flags |= DELAYED_MIGRATED;
  	}
  
  	/*
@@ -3733,7 +3745,7 @@ static int ttwu_runnable(struct task_struct *p, int wake_flags)
  	if (task_on_rq_queued(p)) {
  		update_rq_clock(rq);
  		if (p->se.sched_delayed)
-			enqueue_task(rq, p, ENQUEUE_NOCLOCK | ENQUEUE_DELAYED);
+			enqueue_task(rq, p, ENQUEUE_NOCLOCK | ENQUEUE_WAKEUP | ENQUEUE_DELAYED);
  		if (!task_on_cpu(rq, p)) {
  			/*
  			 * When on_rq && !on_cpu the task is preempted, see if
@@ -6537,6 +6549,7 @@ static void __sched notrace __schedule(int sched_mode)
  	 * as a preemption by schedule_debug() and RCU.
  	 */
  	bool preempt = sched_mode > SM_NONE;
+	bool block = false;
  	unsigned long *switch_count;
  	unsigned long prev_state;
  	struct rq_flags rf;
@@ -6622,6 +6635,7 @@ static void __sched notrace __schedule(int sched_mode)
  			 * After this, schedule() must not care about p->state any more.
  			 */
  			block_task(rq, prev, flags);
+			block = true;
  		}
  		switch_count = &prev->nvcsw;
  	}
@@ -6667,7 +6681,7 @@ static void __sched notrace __schedule(int sched_mode)
  
  		migrate_disable_switch(rq, prev);
  		psi_account_irqtime(rq, prev, next);
-		psi_sched_switch(prev, next, !task_on_rq_queued(prev));
+		psi_sched_switch(prev, next, block);
  
  		trace_sched_switch(preempt, prev, next, prev_state);
  
diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
index b1c3588a8f00..2dc2c4cb4f5f 100644
--- a/kernel/sched/sched.h
+++ b/kernel/sched/sched.h
@@ -1326,6 +1326,7 @@ static inline int cpu_of(struct rq *rq)
  }
  
  #define MDF_PUSH		0x01
+#define DELAYED_MIGRATED	0x02 /* Task was migrated when in DELAYED_DEQUEUE state */
  
  static inline bool is_migration_disabled(struct task_struct *p)
  {
diff --git a/kernel/sched/stats.h b/kernel/sched/stats.h
index 237780aa3c53..06a2c6d3ec1e 100644
--- a/kernel/sched/stats.h
+++ b/kernel/sched/stats.h
@@ -129,6 +129,13 @@ static inline void psi_enqueue(struct task_struct *p, bool wakeup)
  	if (static_branch_likely(&psi_disabled))
  		return;
  
+	/*
+	 * Delayed task is not ready to run yet!
+	 * Wait for a requeue before accounting.
+	 */
+	if (p->se.sched_delayed)
+		return;
+
  	if (p->in_memstall)
  		set |= TSK_MEMSTALL_RUNNING;
  
@@ -148,6 +155,9 @@ static inline void psi_dequeue(struct task_struct *p, bool sleep)
  	if (static_branch_likely(&psi_disabled))
  		return;
  
+	/* Delayed task can only be dequeued for migration. */
+	WARN_ON_ONCE(p->se.sched_delayed && sleep);
+
  	/*
  	 * A voluntary sleep is a dequeue followed by a task switch. To
  	 * avoid walking all ancestors twice, psi_task_switch() handles
--

Any and all suggestions are highly appreciated.

> 
> Thank you again both for taking a look.
> 

-- 
Thanks and Regards,
Prateek

Re: [REGRESSION] Re: [PATCH 17/24] sched/fair: Implement delayed dequeue

[K Prateek Nayak]

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

Hello folks,

On 10/8/2024 9:08 PM, K Prateek Nayak wrote:
> Hello Johannes, Peter,
> 
> On 10/4/2024 10:13 PM, K Prateek Nayak wrote:
>> [..snip..]
>>>> Anyway, assuming PSI wants to preserve current semantics, does something
>>>> like the below work?
>>>
>>> This doesn't. But it's a different corruption now:
>>>
>>> [    2.298408] psi: inconsistent task state! task=24:cpuhp/1 cpu=1 psi_flags=10 clear=14 set=0
>>
>> I hit the same log (clear 14, set 0) and I tried the below changes on
>> top of Peter's diff:
>>
>> diff --git a/kernel/sched/core.c b/kernel/sched/core.c
>> index 0d766fb9fbc4..9cf3d4359994 100644
>> --- a/kernel/sched/core.c
>> +++ b/kernel/sched/core.c
>> @@ -2012,9 +2012,10 @@ void enqueue_task(struct rq *rq, struct task_struct *p, int flags)
>>       if (!(flags & ENQUEUE_NOCLOCK))
>>           update_rq_clock(rq);
>>
>> -    if (!(flags & ENQUEUE_RESTORE) && !p->se.sched_delayed) {
>> +    if (!(flags & ENQUEUE_RESTORE) && (!p->se.sched_delayed || (flags & ENQUEUE_DELAYED))) {
>>           sched_info_enqueue(rq, p);
>> -        psi_enqueue(p, (flags & ENQUEUE_WAKEUP) && !(flags & ENQUEUE_MIGRATED));
>> +        psi_enqueue(p, ((flags & ENQUEUE_WAKEUP) && !(flags & ENQUEUE_MIGRATED)) ||
>> +                   (flags & ENQUEUE_DELAYED));
>>       }
>>
>>       p->sched_class->enqueue_task(rq, p, flags);
>> -- 
>>
>> ... but it just changes the warning to:
>>
>>      psi: task underflow! cpu=65 t=0 tasks=[0 0 0 0] clear=1 set=4
>>      psi: task underflow! cpu=31 t=0 tasks=[0 0 1 0] clear=1 set=0
>>
>> Doing a dump_stack(), I see it come from psi_enqueue() and
>> psi_ttwu_dequeue() and I see "clear=1" as the common theme. I've
>> stared at it for a while but I'm at a loss currently. If something
>> jumps out, I'll update here.
> 
> I could narrow down the crux of the matter to the fact that when a task
> is delayed, and the delayed task is then migrated, the wakeup context
> may not have any idea that the task was moved from its previous
> runqueue. This is the same reason psi_enqueue() considers only ...
> 
>      (flags & ENQUEUE_WAKEUP) && !(flags & ENQUEUE_MIGRATED)
> 
> ... as a wakeup. In case of a wakeup with migration, PSI forgoes
> clearing the TSK_IOWAIT flag which seems to be the issue I encountered
> in my splat previously.
> 
> With that said, the below diff, based on Peter's original approach
> currently seems to work for me in the sense that I have not seen the
> inconsistent state warning for a while now with my stress test.
> 
> Two key points of the approach are:
> 
> o It uses "p->migration_flags" to indicate a delayed entity has
>    migrated to another runqueue and convey the same during psi_enqueue().
> 
> o It adds ENQUEUE_WAKEUP flag alongside ENQUEUE_DELAYED for
>    enqueue_task() in ttwu_runnable() since psi_enqueue() needs to know of
>    a wakeup without migration to clear the TSK_IOWAIT flag it would have
>    set during psi_task_switch() for blocking task and going down the
>    stack for enqueue_task_fair(), there seem to be no other observer of
>    the ENQUEUE_WAKEUP flag other than psi_enqueue() in the requeue path.
> 
> If there are no obvious objections, I'll send a clean patch soon.
> In the meantime, here is the diff:
> [..snip..]

That last diff was malformed! Sorry for the noise. Here is the corrected
diff:

diff --git a/kernel/sched/core.c b/kernel/sched/core.c
index 43e453ab7e20..885801432e9a 100644
--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -2009,12 +2009,19 @@ unsigned long get_wchan(struct task_struct *p)
  
  void enqueue_task(struct rq *rq, struct task_struct *p, int flags)
  {
+	bool wakee_not_migrated = (flags & ENQUEUE_WAKEUP) && !(flags & ENQUEUE_MIGRATED);
+
  	if (!(flags & ENQUEUE_NOCLOCK))
  		update_rq_clock(rq);
  
  	if (!(flags & ENQUEUE_RESTORE)) {
  		sched_info_enqueue(rq, p);
-		psi_enqueue(p, (flags & ENQUEUE_WAKEUP) && !(flags & ENQUEUE_MIGRATED));
+
+		/* Notify PSI that the task was migrated in a delayed state before wakeup. */
+		if ((p->migration_flags & DELAYED_MIGRATED) && !task_on_rq_migrating(p)) {
+			wakee_not_migrated = false;
+			p->migration_flags &= ~DELAYED_MIGRATED;
+		}
  	}
  
  	p->sched_class->enqueue_task(rq, p, flags);
@@ -2023,6 +2030,8 @@ void enqueue_task(struct rq *rq, struct task_struct *p, int flags)
  	 * ->sched_delayed.
  	 */
  	uclamp_rq_inc(rq, p);
+	if (!(flags & ENQUEUE_RESTORE))
+		psi_enqueue(p, wakee_not_migrated);
  
  	if (sched_core_enabled(rq))
  		sched_core_enqueue(rq, p);
@@ -2042,6 +2051,9 @@ inline bool dequeue_task(struct rq *rq, struct task_struct *p, int flags)
  	if (!(flags & DEQUEUE_SAVE)) {
  		sched_info_dequeue(rq, p);
  		psi_dequeue(p, flags & DEQUEUE_SLEEP);
+
+		if (p->se.sched_delayed && task_on_rq_migrating(p))
+			p->migration_flags |= DELAYED_MIGRATED;
  	}
  
  	/*
@@ -3733,7 +3745,7 @@ static int ttwu_runnable(struct task_struct *p, int wake_flags)
  	if (task_on_rq_queued(p)) {
  		update_rq_clock(rq);
  		if (p->se.sched_delayed)
-			enqueue_task(rq, p, ENQUEUE_NOCLOCK | ENQUEUE_DELAYED);
+			enqueue_task(rq, p, ENQUEUE_NOCLOCK | ENQUEUE_WAKEUP | ENQUEUE_DELAYED);
  		if (!task_on_cpu(rq, p)) {
  			/*
  			 * When on_rq && !on_cpu the task is preempted, see if
@@ -6537,6 +6549,7 @@ static void __sched notrace __schedule(int sched_mode)
  	 * as a preemption by schedule_debug() and RCU.
  	 */
  	bool preempt = sched_mode > SM_NONE;
+	bool block = false;
  	unsigned long *switch_count;
  	unsigned long prev_state;
  	struct rq_flags rf;
@@ -6622,6 +6635,7 @@ static void __sched notrace __schedule(int sched_mode)
  			 * After this, schedule() must not care about p->state any more.
  			 */
  			block_task(rq, prev, flags);
+			block = true;
  		}
  		switch_count = &prev->nvcsw;
  	}
@@ -6667,7 +6681,7 @@ static void __sched notrace __schedule(int sched_mode)
  
  		migrate_disable_switch(rq, prev);
  		psi_account_irqtime(rq, prev, next);
-		psi_sched_switch(prev, next, !task_on_rq_queued(prev));
+		psi_sched_switch(prev, next, block);
  
  		trace_sched_switch(preempt, prev, next, prev_state);
  
diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
index b1c3588a8f00..2dc2c4cb4f5f 100644
--- a/kernel/sched/sched.h
+++ b/kernel/sched/sched.h
@@ -1326,6 +1326,7 @@ static inline int cpu_of(struct rq *rq)
  }
  
  #define MDF_PUSH		0x01
+#define DELAYED_MIGRATED	0x02 /* Task was migrated when in DELAYED_DEQUEUE state */
  
  static inline bool is_migration_disabled(struct task_struct *p)
  {
diff --git a/kernel/sched/stats.h b/kernel/sched/stats.h
index 237780aa3c53..06a2c6d3ec1e 100644
--- a/kernel/sched/stats.h
+++ b/kernel/sched/stats.h
@@ -129,6 +129,13 @@ static inline void psi_enqueue(struct task_struct *p, bool wakeup)
  	if (static_branch_likely(&psi_disabled))
  		return;
  
+	/*
+	 * Delayed task is not ready to run yet!
+	 * Wait for a requeue before accounting.
+	 */
+	if (p->se.sched_delayed)
+		return;
+
  	if (p->in_memstall)
  		set |= TSK_MEMSTALL_RUNNING;
  
@@ -148,6 +155,9 @@ static inline void psi_dequeue(struct task_struct *p, bool sleep)
  	if (static_branch_likely(&psi_disabled))
  		return;
  
+	/* Delayed task can only be dequeued for migration. */
+	WARN_ON_ONCE(p->se.sched_delayed && sleep);
+
  	/*
  	 * A voluntary sleep is a dequeue followed by a task switch. To
  	 * avoid walking all ancestors twice, psi_task_switch() handles
--

Attaching an RFC patch in case I messed this up as well!

> -- 
> 
> Any and all suggestions are highly appreciated.
> 
>>
>> Thank you again both for taking a look.
>>
> 

-- 
Thanks and Regards,
Prateek

[-- Attachment #2: 0001-sched-psi-Fixup-PSI-accounting-with-DELAY_DEQUEUE.patch --]
[-- Type: text/plain, Size: 5869 bytes --]

From 2e15180e18b51e9a2bc0d7050e915a70d2673a06 Mon Sep 17 00:00:00 2001
From: K Prateek Nayak <kprateek.nayak@amd.com>
Date: Fri, 4 Oct 2024 15:24:35 +0000
Subject: [RFC PATCH] sched/psi: Fixup PSI accounting with DELAY_DEQUEUE

After the merge of DELAY_DEQUEUE, "psi: inconsistent task state: warning
were seen early into the boot. The crux of the matter is the fact that
when a task is delayed, and the delayed task is then migrated, the
wakeup context may not have any idea that the task was moved from its
previous runqueue. This is the same reason psi_enqueue() considers
only ...

     (flags & ENQUEUE_WAKEUP) && !(flags & ENQUEUE_MIGRATED)

... as a wakeup. In case of a wakeup with migration, PSI forgoes
clearing the TSK_IOWAIT flag which seems to be the issue I encountered
in my splat previously.

With that said, the below diff, based on Peter's original approach
currently seems to work for me in the sense that I have not seen the
inconsistent state warning for a while now with my stress test.

Two key points of the approach are:

o It uses "p->migration_flags" to indicate a delayed entity has
   migrated to another runqueue and convey the same during psi_enqueue().

o It adds ENQUEUE_WAKEUP flag alongside ENQUEUE_DELAYED for
   enqueue_task() in ttwu_runnable() since psi_enqueue() needs to know of
   a wakeup without migration to clear the TSK_IOWAIT flag it would have
   set during psi_task_switch() for blocking task and going down the
   stack for enqueue_task_fair(), there seem to be no other observer of
   the ENQUEUE_WAKEUP flag other than psi_enqueue() in the requeue path.

Suggested-by: Peter Zijlstra <peterz@infradead.org>
Signed-off-by: K Prateek Nayak <kprateek.nayak@amd.com>
---
 kernel/sched/core.c  | 20 +++++++++++++++++---
 kernel/sched/sched.h |  1 +
 kernel/sched/stats.h | 10 ++++++++++
 3 files changed, 28 insertions(+), 3 deletions(-)

diff --git a/kernel/sched/core.c b/kernel/sched/core.c
index 43e453ab7e20..885801432e9a 100644
--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -2009,12 +2009,19 @@ unsigned long get_wchan(struct task_struct *p)
 
 void enqueue_task(struct rq *rq, struct task_struct *p, int flags)
 {
+	bool wakee_not_migrated = (flags & ENQUEUE_WAKEUP) && !(flags & ENQUEUE_MIGRATED);
+
 	if (!(flags & ENQUEUE_NOCLOCK))
 		update_rq_clock(rq);
 
 	if (!(flags & ENQUEUE_RESTORE)) {
 		sched_info_enqueue(rq, p);
-		psi_enqueue(p, (flags & ENQUEUE_WAKEUP) && !(flags & ENQUEUE_MIGRATED));
+
+		/* Notify PSI that the task was migrated in a delayed state before wakeup. */
+		if ((p->migration_flags & DELAYED_MIGRATED) && !task_on_rq_migrating(p)) {
+			wakee_not_migrated = false;
+			p->migration_flags &= ~DELAYED_MIGRATED;
+		}
 	}
 
 	p->sched_class->enqueue_task(rq, p, flags);
@@ -2023,6 +2030,8 @@ void enqueue_task(struct rq *rq, struct task_struct *p, int flags)
 	 * ->sched_delayed.
 	 */
 	uclamp_rq_inc(rq, p);
+	if (!(flags & ENQUEUE_RESTORE))
+		psi_enqueue(p, wakee_not_migrated);
 
 	if (sched_core_enabled(rq))
 		sched_core_enqueue(rq, p);
@@ -2042,6 +2051,9 @@ inline bool dequeue_task(struct rq *rq, struct task_struct *p, int flags)
 	if (!(flags & DEQUEUE_SAVE)) {
 		sched_info_dequeue(rq, p);
 		psi_dequeue(p, flags & DEQUEUE_SLEEP);
+
+		if (p->se.sched_delayed && task_on_rq_migrating(p))
+			p->migration_flags |= DELAYED_MIGRATED;
 	}
 
 	/*
@@ -3733,7 +3745,7 @@ static int ttwu_runnable(struct task_struct *p, int wake_flags)
 	if (task_on_rq_queued(p)) {
 		update_rq_clock(rq);
 		if (p->se.sched_delayed)
-			enqueue_task(rq, p, ENQUEUE_NOCLOCK | ENQUEUE_DELAYED);
+			enqueue_task(rq, p, ENQUEUE_NOCLOCK | ENQUEUE_WAKEUP | ENQUEUE_DELAYED);
 		if (!task_on_cpu(rq, p)) {
 			/*
 			 * When on_rq && !on_cpu the task is preempted, see if
@@ -6537,6 +6549,7 @@ static void __sched notrace __schedule(int sched_mode)
 	 * as a preemption by schedule_debug() and RCU.
 	 */
 	bool preempt = sched_mode > SM_NONE;
+	bool block = false;
 	unsigned long *switch_count;
 	unsigned long prev_state;
 	struct rq_flags rf;
@@ -6622,6 +6635,7 @@ static void __sched notrace __schedule(int sched_mode)
 			 * After this, schedule() must not care about p->state any more.
 			 */
 			block_task(rq, prev, flags);
+			block = true;
 		}
 		switch_count = &prev->nvcsw;
 	}
@@ -6667,7 +6681,7 @@ static void __sched notrace __schedule(int sched_mode)
 
 		migrate_disable_switch(rq, prev);
 		psi_account_irqtime(rq, prev, next);
-		psi_sched_switch(prev, next, !task_on_rq_queued(prev));
+		psi_sched_switch(prev, next, block);
 
 		trace_sched_switch(preempt, prev, next, prev_state);
 
diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
index b1c3588a8f00..2dc2c4cb4f5f 100644
--- a/kernel/sched/sched.h
+++ b/kernel/sched/sched.h
@@ -1326,6 +1326,7 @@ static inline int cpu_of(struct rq *rq)
 }
 
 #define MDF_PUSH		0x01
+#define DELAYED_MIGRATED	0x02 /* Task was migrated when in DELAYED_DEQUEUE state */
 
 static inline bool is_migration_disabled(struct task_struct *p)
 {
diff --git a/kernel/sched/stats.h b/kernel/sched/stats.h
index 237780aa3c53..06a2c6d3ec1e 100644
--- a/kernel/sched/stats.h
+++ b/kernel/sched/stats.h
@@ -129,6 +129,13 @@ static inline void psi_enqueue(struct task_struct *p, bool wakeup)
 	if (static_branch_likely(&psi_disabled))
 		return;
 
+	/*
+	 * Delayed task is not ready to run yet!
+	 * Wait for a requeue before accounting.
+	 */
+	if (p->se.sched_delayed)
+		return;
+
 	if (p->in_memstall)
 		set |= TSK_MEMSTALL_RUNNING;
 
@@ -148,6 +155,9 @@ static inline void psi_dequeue(struct task_struct *p, bool sleep)
 	if (static_branch_likely(&psi_disabled))
 		return;
 
+	/* Delayed task can only be dequeued for migration. */
+	WARN_ON_ONCE(p->se.sched_delayed && sleep);
+
 	/*
 	 * A voluntary sleep is a dequeue followed by a task switch. To
 	 * avoid walking all ancestors twice, psi_task_switch() handles
-- 
2.34.1

Re: [REGRESSION] Re: [PATCH 17/24] sched/fair: Implement delayed dequeue

[Johannes Weiner]

On Tue, Oct 08, 2024 at 09:54:52PM +0530, K Prateek Nayak wrote:
> From 2e15180e18b51e9a2bc0d7050e915a70d2673a06 Mon Sep 17 00:00:00 2001
> From: K Prateek Nayak <kprateek.nayak@amd.com>
> Date: Fri, 4 Oct 2024 15:24:35 +0000
> Subject: [RFC PATCH] sched/psi: Fixup PSI accounting with DELAY_DEQUEUE
> 
> After the merge of DELAY_DEQUEUE, "psi: inconsistent task state: warning
> were seen early into the boot. The crux of the matter is the fact that
> when a task is delayed, and the delayed task is then migrated, the
> wakeup context may not have any idea that the task was moved from its
> previous runqueue. This is the same reason psi_enqueue() considers
> only ...
> 
>      (flags & ENQUEUE_WAKEUP) && !(flags & ENQUEUE_MIGRATED)
> 
> ... as a wakeup. In case of a wakeup with migration, PSI forgoes
> clearing the TSK_IOWAIT flag which seems to be the issue I encountered
> in my splat previously.
> 
> With that said, the below diff, based on Peter's original approach
> currently seems to work for me in the sense that I have not seen the
> inconsistent state warning for a while now with my stress test.
> 
> Two key points of the approach are:
> 
> o It uses "p->migration_flags" to indicate a delayed entity has
>    migrated to another runqueue and convey the same during psi_enqueue().
> 
> o It adds ENQUEUE_WAKEUP flag alongside ENQUEUE_DELAYED for
>    enqueue_task() in ttwu_runnable() since psi_enqueue() needs to know of
>    a wakeup without migration to clear the TSK_IOWAIT flag it would have
>    set during psi_task_switch() for blocking task and going down the
>    stack for enqueue_task_fair(), there seem to be no other observer of
>    the ENQUEUE_WAKEUP flag other than psi_enqueue() in the requeue path.
> 
> Suggested-by: Peter Zijlstra <peterz@infradead.org>
> Signed-off-by: K Prateek Nayak <kprateek.nayak@amd.com>

Tested-by: Johannes Weiner <hannes@cmpxchg.org>

It fixes the warning and bogus pressure values after stressing it for
an hour or so with tons of cpu contention and cgroup movements.

Re: [REGRESSION] Re: [PATCH 17/24] sched/fair: Implement delayed dequeue

[K Prateek Nayak]

Hello Johannes,

On 10/9/2024 11:37 PM, Johannes Weiner wrote:
> On Tue, Oct 08, 2024 at 09:54:52PM +0530, K Prateek Nayak wrote:
>>  From 2e15180e18b51e9a2bc0d7050e915a70d2673a06 Mon Sep 17 00:00:00 2001
>> From: K Prateek Nayak <kprateek.nayak@amd.com>
>> Date: Fri, 4 Oct 2024 15:24:35 +0000
>> Subject: [RFC PATCH] sched/psi: Fixup PSI accounting with DELAY_DEQUEUE
>>
>> After the merge of DELAY_DEQUEUE, "psi: inconsistent task state: warning
>> were seen early into the boot. The crux of the matter is the fact that
>> when a task is delayed, and the delayed task is then migrated, the
>> wakeup context may not have any idea that the task was moved from its
>> previous runqueue. This is the same reason psi_enqueue() considers
>> only ...
>>
>>       (flags & ENQUEUE_WAKEUP) && !(flags & ENQUEUE_MIGRATED)
>>
>> ... as a wakeup. In case of a wakeup with migration, PSI forgoes
>> clearing the TSK_IOWAIT flag which seems to be the issue I encountered
>> in my splat previously.
>>
>> With that said, the below diff, based on Peter's original approach
>> currently seems to work for me in the sense that I have not seen the
>> inconsistent state warning for a while now with my stress test.
>>
>> Two key points of the approach are:
>>
>> o It uses "p->migration_flags" to indicate a delayed entity has
>>     migrated to another runqueue and convey the same during psi_enqueue().
>>
>> o It adds ENQUEUE_WAKEUP flag alongside ENQUEUE_DELAYED for
>>     enqueue_task() in ttwu_runnable() since psi_enqueue() needs to know of
>>     a wakeup without migration to clear the TSK_IOWAIT flag it would have
>>     set during psi_task_switch() for blocking task and going down the
>>     stack for enqueue_task_fair(), there seem to be no other observer of
>>     the ENQUEUE_WAKEUP flag other than psi_enqueue() in the requeue path.
>>
>> Suggested-by: Peter Zijlstra <peterz@infradead.org>
>> Signed-off-by: K Prateek Nayak <kprateek.nayak@amd.com>
> 
> Tested-by: Johannes Weiner <hannes@cmpxchg.org>
> 
> It fixes the warning and bogus pressure values after stressing it for
> an hour or so with tons of cpu contention and cgroup movements.

Thanks a ton for testing. I'll send a proper series soon for folks to
review.
-- 
Thanks and Regards,
Prateek

Re: [PATCH 17/24] sched/fair: Implement delayed dequeue

[Dietmar Eggemann]

On 08/11/2024 19:16, Phil Auld wrote:
> On Fri, Nov 08, 2024 at 03:53:26PM +0100 Dietmar Eggemann wrote:
>> On 04/11/2024 13:50, Phil Auld wrote:
>>>
>>> Hi Dietmar,
>>>
>>> On Mon, Nov 04, 2024 at 10:28:37AM +0100 Dietmar Eggemann wrote:
>>>> Hi Phil,
>>>>
>>>> On 01/11/2024 13:47, Phil Auld wrote:

[...]

>> One reason I don't see the difference between DELAY_DEQUEUE and
>> NO_DELAY_DEQUEUE could be because of the affinity of the related
>> nvme interrupts: 
>>
>> $ cat /proc/interrupts
>>
>>      CPU0 CPU1    CPU2 CPU3 CPU4    CPU5 CPU6 CPU7    CPU8 ...
>> 132:   0    0  1523653    0   0        0   0    0       0  ... IR-PCI-MSIX-0000:01:00.0 1-edge nvme0q1
>> 133:   0    0        0    0   0  1338451   0    0       0  ... IR-PCI-MSIX-0000:01:00.0 2-edge nvme0q2
>> 134:   0    0        0    0   0        0   0    0  2252297 ... IR-PCI-MSIX-0000:01:00.0 3-edge nvme0q3
>>
>> $ cat /proc/irq/132/smp_affinity_list 
>> 0-2
>> cat /proc/irq/133/smp_affinity_list 
>> 3-5
>> cat /proc/irq/134/smp_affinity_list 
>> 6-8
>>
>> So the 8 fio tasks from: 
>>
>> # fio --cpus_allowed 1,2,3,4,5,6,7,8 --rw randwrite --bs 4k
>>   --runtime 8s --iodepth 32 --direct 1 --ioengine libaio
>>   --numjobs 8 --size 30g --name default --time_based
>>   --group_reporting --cpus_allowed_policy shared
>>   --directory /testfs
>>
>> don't have to fight with per-CPU kworkers on each CPU.
>>
>> e.g. 'nvme0q3 interrupt -> queue on workqueue dio/nvme0n1p2 -> 
>>       run iomap_dio_complete_work() in kworker/8:x'
>>
>> In case I trace the 'task_on_rq_queued(p) && p->se.sched_delayed &&
>> rq->nr_running > 1) condition in ttwu_runnable() condition i only see
>> the per-CPU kworker in there, so p->nr_cpus_allowed == 1.
>>
>> So the patch shouldn't make a difference for this scenario?
>>
> 
> If the kworker is waking up an fio task it could.  I don't think
> they are bound to a single cpu.
> 
> But yes if your trace is only showing the kworker there then it would
> not help.  Are you actually able to reproduce the difference?

No, with my setup I don't see any difference running your fio test. But
the traces also show me that there are no scenarios in which this patch
can make a difference in the scores.

>> But maybe your VDO or thinpool setup creates waker/wakee pairs with
>> wakee->nr_cpus_allowed > 1? 
>>
> 
> That's certainly possible but I don't know for sure. There are well more
> dio kworkers on the box than cpus though if I recall. I don't know
> if they all have singel cpu affinities. 

Yeah there must be more tasks (inc. kworkers) w/ 'p->nr_cpus_allowed >
1' involved.

>> Does your machine has single CPU smp_affinity masks for these nvme
>> interrupts?
>>
> 
> I don't know. I had to give the machine back.

Ah, too late then ;-)

Re: [PATCH 17/24] sched/fair: Implement delayed dequeue

[Phil Auld]

On Fri, Nov 08, 2024 at 03:53:26PM +0100 Dietmar Eggemann wrote:
> On 04/11/2024 13:50, Phil Auld wrote:
> > 
> > Hi Dietmar,
> > 
> > On Mon, Nov 04, 2024 at 10:28:37AM +0100 Dietmar Eggemann wrote:
> >> Hi Phil,
> >>
> >> On 01/11/2024 13:47, Phil Auld wrote:
> >>>
> >>> Hi Peterm
> 
> [...]
> 
> >> I'm not seeing this on my i7-13700K running tip sched/core (1a6151017ee5
> >> - sched: psi: pass enqueue/dequeue flags to psi callbacks directly
> >> (2024-10-26 Johannes Weiner)) (6.12.0-rc4 - based)
> >>
> >> Using 'taskset 0xaaaaa' avoiding SMT and running only on P-cores.
> >>
> >> vanilla features: 990MB/s (mean out of 5 runs, σ:  9.38)
> >> NO_DELAY_DEQUEUE: 992MB/s (mean out of 5 runs, σ: 10.61)
> >>
> >> # sudo lshw -class disk -class storage
> >>   *-nvme                    
> >>        description: NVMe device
> >>        product: GIGABYTE GP-ASM2NE6500GTTD
> >>        vendor: Phison Electronics Corporation
> >>        physical id: 0
> >>        bus info: pci@0000:01:00.0
> >>        logical name: /dev/nvme0
> >>        version: EGFM13.2
> >>        ...
> >>        capabilities: nvme pciexpress msix msi pm nvm_express bus_master cap_list
> >>        configuration: driver=nvme latency=0 nqn=nqn.2014.08.org.nvmexpress:19871987SN215108954872 GIGABYTE GP-ASM2NE6500GTTD state=live
> >>        resources: irq:16 memory:70800000-70803fff
> >>
> >> # mount | grep ^/dev/nvme0
> >> /dev/nvme0n1p2 on / type ext4 (rw,relatime,errors=remount-ro)
> >>
> >> Which disk device you're using?
> > 
> > Most of the reports are on various NVME drives (samsung mostly I think).
> > 
> > 
> > One thing I should add is that it's all on LVM: 
> > 
> > 
> > vgcreate vg /dev/nvme0n1 -y
> > lvcreate -n thinMeta -L 3GB vg -y
> > lvcreate -n thinPool -l 99%FREE vg -y
> > lvconvert --thinpool /dev/mapper/vg-thinPool --poolmetadata /dev/mapper/vg-thinMeta -Zn -y
> > lvcreate -n testLV -V 1300G --thinpool thinPool vg
> > wipefs -a /dev/mapper/vg-testLV
> > mkfs.ext4 /dev/mapper/vg-testLV -E lazy_itable_init=0,lazy_journal_init=0 -F
> > mount /dev/mapper/vg-testLV /testfs 
> > 
> > 
> > With VDO or thinpool (as above) it shows on both ext4 and xfs. With fs on
> > drive directly it's a little more variable. Some it shows on xfs, some it show
> > on ext4 and not vice-versa, seems to depend on the drive or hw raid. But when
> > it shows it's 100% reproducible on that setup. 
> > 
> > It's always the randwrite numbers. The rest look fine.
> > 
> > Also, as yet I'm not personally doing this testing, just looking into it and
> > passing on the information I have. 
> 
> One reason I don't see the difference between DELAY_DEQUEUE and
> NO_DELAY_DEQUEUE could be because of the affinity of the related
> nvme interrupts: 
> 
> $ cat /proc/interrupts
> 
>      CPU0 CPU1    CPU2 CPU3 CPU4    CPU5 CPU6 CPU7    CPU8 ...
> 132:   0    0  1523653    0   0        0   0    0       0  ... IR-PCI-MSIX-0000:01:00.0 1-edge nvme0q1
> 133:   0    0        0    0   0  1338451   0    0       0  ... IR-PCI-MSIX-0000:01:00.0 2-edge nvme0q2
> 134:   0    0        0    0   0        0   0    0  2252297 ... IR-PCI-MSIX-0000:01:00.0 3-edge nvme0q3
> 
> $ cat /proc/irq/132/smp_affinity_list 
> 0-2
> cat /proc/irq/133/smp_affinity_list 
> 3-5
> cat /proc/irq/134/smp_affinity_list 
> 6-8
> 
> So the 8 fio tasks from: 
> 
> # fio --cpus_allowed 1,2,3,4,5,6,7,8 --rw randwrite --bs 4k
>   --runtime 8s --iodepth 32 --direct 1 --ioengine libaio
>   --numjobs 8 --size 30g --name default --time_based
>   --group_reporting --cpus_allowed_policy shared
>   --directory /testfs
> 
> don't have to fight with per-CPU kworkers on each CPU.
> 
> e.g. 'nvme0q3 interrupt -> queue on workqueue dio/nvme0n1p2 -> 
>       run iomap_dio_complete_work() in kworker/8:x'
> 
> In case I trace the 'task_on_rq_queued(p) && p->se.sched_delayed &&
> rq->nr_running > 1) condition in ttwu_runnable() condition i only see
> the per-CPU kworker in there, so p->nr_cpus_allowed == 1.
> 
> So the patch shouldn't make a difference for this scenario?
>

If the kworker is waking up an fio task it could.  I don't think
they are bound to a single cpu.

But yes if your trace is only showing the kworker there then it would
not help.  Are you actually able to reproduce the difference?


> But maybe your VDO or thinpool setup creates waker/wakee pairs with
> wakee->nr_cpus_allowed > 1? 
>

That's certainly possible but I don't know for sure. There are well more
dio kworkers on the box than cpus though if I recall. I don't know
if they all have singel cpu affinities. 


> Does your machine has single CPU smp_affinity masks for these nvme
> interrupts?
>

I don't know. I had to give the machine back. 



Cheers,
Phil


> [...]
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 

-- 

Re: [PATCH 17/24] sched/fair: Implement delayed dequeue

[Dietmar Eggemann]

On 04/11/2024 13:50, Phil Auld wrote:
> 
> Hi Dietmar,
> 
> On Mon, Nov 04, 2024 at 10:28:37AM +0100 Dietmar Eggemann wrote:
>> Hi Phil,
>>
>> On 01/11/2024 13:47, Phil Auld wrote:
>>>
>>> Hi Peterm

[...]

>> I'm not seeing this on my i7-13700K running tip sched/core (1a6151017ee5
>> - sched: psi: pass enqueue/dequeue flags to psi callbacks directly
>> (2024-10-26 Johannes Weiner)) (6.12.0-rc4 - based)
>>
>> Using 'taskset 0xaaaaa' avoiding SMT and running only on P-cores.
>>
>> vanilla features: 990MB/s (mean out of 5 runs, σ:  9.38)
>> NO_DELAY_DEQUEUE: 992MB/s (mean out of 5 runs, σ: 10.61)
>>
>> # sudo lshw -class disk -class storage
>>   *-nvme                    
>>        description: NVMe device
>>        product: GIGABYTE GP-ASM2NE6500GTTD
>>        vendor: Phison Electronics Corporation
>>        physical id: 0
>>        bus info: pci@0000:01:00.0
>>        logical name: /dev/nvme0
>>        version: EGFM13.2
>>        ...
>>        capabilities: nvme pciexpress msix msi pm nvm_express bus_master cap_list
>>        configuration: driver=nvme latency=0 nqn=nqn.2014.08.org.nvmexpress:19871987SN215108954872 GIGABYTE GP-ASM2NE6500GTTD state=live
>>        resources: irq:16 memory:70800000-70803fff
>>
>> # mount | grep ^/dev/nvme0
>> /dev/nvme0n1p2 on / type ext4 (rw,relatime,errors=remount-ro)
>>
>> Which disk device you're using?
> 
> Most of the reports are on various NVME drives (samsung mostly I think).
> 
> 
> One thing I should add is that it's all on LVM: 
> 
> 
> vgcreate vg /dev/nvme0n1 -y
> lvcreate -n thinMeta -L 3GB vg -y
> lvcreate -n thinPool -l 99%FREE vg -y
> lvconvert --thinpool /dev/mapper/vg-thinPool --poolmetadata /dev/mapper/vg-thinMeta -Zn -y
> lvcreate -n testLV -V 1300G --thinpool thinPool vg
> wipefs -a /dev/mapper/vg-testLV
> mkfs.ext4 /dev/mapper/vg-testLV -E lazy_itable_init=0,lazy_journal_init=0 -F
> mount /dev/mapper/vg-testLV /testfs 
> 
> 
> With VDO or thinpool (as above) it shows on both ext4 and xfs. With fs on
> drive directly it's a little more variable. Some it shows on xfs, some it show
> on ext4 and not vice-versa, seems to depend on the drive or hw raid. But when
> it shows it's 100% reproducible on that setup. 
> 
> It's always the randwrite numbers. The rest look fine.
> 
> Also, as yet I'm not personally doing this testing, just looking into it and
> passing on the information I have. 

One reason I don't see the difference between DELAY_DEQUEUE and
NO_DELAY_DEQUEUE could be because of the affinity of the related
nvme interrupts: 

$ cat /proc/interrupts

     CPU0 CPU1    CPU2 CPU3 CPU4    CPU5 CPU6 CPU7    CPU8 ...
132:   0    0  1523653    0   0        0   0    0       0  ... IR-PCI-MSIX-0000:01:00.0 1-edge nvme0q1
133:   0    0        0    0   0  1338451   0    0       0  ... IR-PCI-MSIX-0000:01:00.0 2-edge nvme0q2
134:   0    0        0    0   0        0   0    0  2252297 ... IR-PCI-MSIX-0000:01:00.0 3-edge nvme0q3

$ cat /proc/irq/132/smp_affinity_list 
0-2
cat /proc/irq/133/smp_affinity_list 
3-5
cat /proc/irq/134/smp_affinity_list 
6-8

So the 8 fio tasks from: 

# fio --cpus_allowed 1,2,3,4,5,6,7,8 --rw randwrite --bs 4k
  --runtime 8s --iodepth 32 --direct 1 --ioengine libaio
  --numjobs 8 --size 30g --name default --time_based
  --group_reporting --cpus_allowed_policy shared
  --directory /testfs

don't have to fight with per-CPU kworkers on each CPU.

e.g. 'nvme0q3 interrupt -> queue on workqueue dio/nvme0n1p2 -> 
      run iomap_dio_complete_work() in kworker/8:x'

In case I trace the 'task_on_rq_queued(p) && p->se.sched_delayed &&
rq->nr_running > 1) condition in ttwu_runnable() condition i only see
the per-CPU kworker in there, so p->nr_cpus_allowed == 1.

So the patch shouldn't make a difference for this scenario?

But maybe your VDO or thinpool setup creates waker/wakee pairs with
wakee->nr_cpus_allowed > 1? 

Does your machine has single CPU smp_affinity masks for these nvme
interrupts?

[...]

Re: [PATCH 17/24] sched/fair: Implement delayed dequeue

[Peter Zijlstra]

On Thu, Nov 07, 2024 at 03:02:36PM +0100, Mike Galbraith wrote:
> On Thu, 2024-11-07 at 10:46 +0100, Mike Galbraith wrote:
> > On Thu, 2024-11-07 at 05:03 +0100, Mike Galbraith wrote:
> > >
> > > I built that patch out of curiosity, and yeah, set_next_task_fair()
> > > finding a cfs_rq->curr ends play time pretty quickly.
> >
> > The below improved uptime, and trace_printk() says it's doing the
> > intended, so I suppose I'll add a feature and see what falls out.
> 
> From netperf, I got.. number tabulation practice.  Three runs of each
> test with and without produced nothing but variance/noise.

Make it go away then.

If you could write a Changelog for you inspired bit and stick my cleaned
up version under it, I'd be much obliged.

Re: [PATCH 17/24] sched/fair: Implement delayed dequeue

[Mike Galbraith]

On Thu, 2024-11-07 at 10:46 +0100, Mike Galbraith wrote:
> On Thu, 2024-11-07 at 05:03 +0100, Mike Galbraith wrote:
> >
> > I built that patch out of curiosity, and yeah, set_next_task_fair()
> > finding a cfs_rq->curr ends play time pretty quickly.
>
> The below improved uptime, and trace_printk() says it's doing the
> intended, so I suppose I'll add a feature and see what falls out.

From netperf, I got.. number tabulation practice.  Three runs of each
test with and without produced nothing but variance/noise.

	-Mike

Re: [PATCH 17/24] sched/fair: Implement delayed dequeue

[Mike Galbraith]

On Thu, 2024-11-07 at 05:03 +0100, Mike Galbraith wrote:
>
> I built that patch out of curiosity, and yeah, set_next_task_fair()
> finding a cfs_rq->curr ends play time pretty quickly.

The below improved uptime, and trace_printk() says it's doing the
intended, so I suppose I'll add a feature and see what falls out.

---
 kernel/sched/core.c |    4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -3794,7 +3794,7 @@ static int ttwu_runnable(struct task_str
 		int queue_flags = DEQUEUE_NOCLOCK;

 		if (p->se.sched_delayed)
-			queue_flags |= DEQUEUE_DELAYED;
+			queue_flags |= (DEQUEUE_DELAYED | DEQUEUE_SLEEP);

 		/*
 		 * Since we're not current anywhere *AND* hold pi_lock, dequeue
@@ -3802,7 +3802,7 @@ static int ttwu_runnable(struct task_str
 		 * case further along the ttwu() path.
 		 */
 		if (rq->nr_running > 1 && p->nr_cpus_allowed > 1) {
-			dequeue_task(rq, p, DEQUEUE_SLEEP | queue_flags);
+			dequeue_task(rq, p, queue_flags);
 			return 0;
 		}

Re: [PATCH 17/24] sched/fair: Implement delayed dequeue

[Mike Galbraith]

On Wed, 2024-11-06 at 16:22 +0100, Mike Galbraith wrote:
>
> Hm, if we try to bounce a preempted task and fail, the wakeup_preempt()
> call won't happen.

Zzzt, wrong, falling through still leads to the bottom of a wakeup with
its preempt check...

> Bouncing preempted tasks is double edged sword..

..but that bit is pretty intriguing.  From the service latency and
utilization perspective only at decision time (prime mission), it's an
obvious win to migrate to an idle CPU.

It's also a clear win for communication latency when buddies are NOT
popular but misused end to end latency measurement tools ala TCP_RR
with only microscopic concurrency. For the other netperf modes of
operation, there's no shortage of concurrency to salvage *and get out
of the communication stream*, and I think that applies to wide swaths
of the real world.  What makes it intriguing is the cross-over point
where "stacking is the stupidest idea ever" becomes "stacking may put
my and my buddy's wide butts directly in our own communication stream,
but that's less pain than what unrelated wide butts inflict on top of
higher LLC vs L2 latency".

For UDP_STREAM (async to the bone), there is no such a point, it would
seemingly prefer its buddy call from orbit, but for its more reasonable
TCP brother and ilk, there is.

Sample numbers (talk), interference is 8 unbound 88% compute instances,
box is crusty ole 8 rq i7-4790.

UDP_STREAM-1    unbound    Avg:  47135  Sum:    47135
UDP_STREAM-1    stacked    Avg:  39602  Sum:    39602
UDP_STREAM-1    cross-smt  Avg:  61599  Sum:    61599
UDP_STREAM-1    cross-core Avg:  67680  Sum:    67680

(distancia muy bueno!)

TCP_STREAM-1    unbound    Avg:  26299  Sum:    26299
TCP_STREAM-1    stacked    Avg:  27893  Sum:    27893
TCP_STREAM-1    cross-smt  Avg:  16728  Sum:    16728
TCP_STREAM-1    cross-core Avg:  13877  Sum:    13877

(idiota, distancia NO bueno, castillo inflable muy bueno!)

Service latency dominates.. not quite always, and bouncing tasks about
is simultaneously the only sane thing to do and pure evil... like
everything else in sched land, making it a hard game to win :)

I built that patch out of curiosity, and yeah, set_next_task_fair()
finding a cfs_rq->curr ends play time pretty quickly.  Too bad my
service latency is a bit dinged up, bouncing preempted wakees about
promises to be interesting.

	-Mike

Re: [PATCH 17/24] sched/fair: Implement delayed dequeue

[Mike Galbraith]

On Wed, 2024-11-06 at 15:14 +0100, Peter Zijlstra wrote:
> On Wed, Nov 06, 2024 at 02:53:46PM +0100, Peter Zijlstra wrote:
> 
> > diff --git a/kernel/sched/core.c b/kernel/sched/core.c
> > index 54d82c21fc8e..b083c6385e88 100644
> > --- a/kernel/sched/core.c
> > +++ b/kernel/sched/core.c
> > @@ -3774,28 +3774,38 @@ ttwu_do_activate(struct rq *rq, struct task_struct *p, int wake_flags,
> >   */
> >  static int ttwu_runnable(struct task_struct *p, int wake_flags)
> >  {
> > +       CLASS(__task_rq_lock, rq_guard)(p);
> > +       struct rq *rq = rq_guard.rq;
> >  
> > +       if (!task_on_rq_queued(p))
> > +               return 0;
> > +
> > +       update_rq_clock(rq);
> > +       if (p->se.sched_delayed) {
> > +               int queue_flags = ENQUEUE_DELAYED | ENQUEUE_NOCLOCK;
> > +
> > +               /*
> > +                * Since sched_delayed means we cannot be current anywhere,
> > +                * dequeue it here and have it fall through to the
> > +                * select_task_rq() case further along the ttwu() path.
> > +                */
> > +               if (rq->nr_running > 1 && p->nr_cpus_allowed > 1) {
> > +                       dequeue_task(rq, p, DEQUEUE_SLEEP | queue_flags);
> > +                       return 0;
> >                 }
> > +
> > +               enqueue_task(rq, p, queue_flags);
> 
> And then I wondered... this means that !task_on_cpu() is true for
> sched_delayed, and thus we can move this in the below branch.
> 
> But also, we can probably dequeue every such task, not only
> sched_delayed ones.
> 
> >         }
> > +       if (!task_on_cpu(rq, p)) {
> > +               /*
> > +                * When on_rq && !on_cpu the task is preempted, see if
> > +                * it should preempt the task that is current now.
> > +                */
> > +               wakeup_preempt(rq, p, wake_flags);
> > +       }
> > +       ttwu_do_wakeup(p);
> >  
> > +       return 1;
> >  }
> 
> 
> Yielding something like this on top... which boots. But since I forgot
> to make it a feature, I can't actually tell at this point.. *sigh*
> 
> Anyway, more toys to poke at I suppose.
> 
> 
> diff --git a/kernel/sched/core.c b/kernel/sched/core.c
> index b083c6385e88..69b19ba77598 100644
> --- a/kernel/sched/core.c
> +++ b/kernel/sched/core.c
> @@ -3781,28 +3781,32 @@ static int ttwu_runnable(struct task_struct *p, int wake_flags)
>                 return 0;
>  
>         update_rq_clock(rq);
> -       if (p->se.sched_delayed) {
> -               int queue_flags = ENQUEUE_DELAYED | ENQUEUE_NOCLOCK;
> +       if (!task_on_cpu(rq, p)) {
> +               int queue_flags = DEQUEUE_NOCLOCK;
> +
> +               if (p->se.sched_delayed)
> +                       queue_flags |= DEQUEUE_DELAYED;
>  
>                 /*
> -                * Since sched_delayed means we cannot be current anywhere,
> -                * dequeue it here and have it fall through to the
> -                * select_task_rq() case further along the ttwu() path.
> +                * Since we're not current anywhere *AND* hold pi_lock, dequeue
> +                * it here and have it fall through to the select_task_rq()
> +                * case further along the ttwu() path.
>                  */
>                 if (rq->nr_running > 1 && p->nr_cpus_allowed > 1) {
>                         dequeue_task(rq, p, DEQUEUE_SLEEP | queue_flags);
>                         return 0;
>                 }

Hm, if we try to bounce a preempted task and fail, the wakeup_preempt()
call won't happen.

Bouncing preempted tasks is double edged sword.. on the one hand, it's
a huge win if bounce works for communicating tasks who will otherwise
be talking around the not-my-buddy man-in-the-middle who did the
preempting, but on the other, when PELT has its white hat on (also has
a black one) and has buddies pairing up nicely in an approaching
saturation scenario, bounces disturb it, add chaos.  Dunno.

>  
> -               enqueue_task(rq, p, queue_flags);
> -       }
> -       if (!task_on_cpu(rq, p)) {
> +               if (p->se.sched_delayed)
> +                       enqueue_task(rq, p, queue_flags);
> +
>                 /*
>                  * When on_rq && !on_cpu the task is preempted, see if
>                  * it should preempt the task that is current now.
>                  */
>                 wakeup_preempt(rq, p, wake_flags);
>         }
> +       SCHED_WARN_ON(p->se.sched_delayed);
>         ttwu_do_wakeup(p);
>  
>         return 1;

Re: [PATCH 17/24] sched/fair: Implement delayed dequeue

[Peter Zijlstra]

On Wed, Nov 06, 2024 at 03:14:20PM +0100, Peter Zijlstra wrote:
> On Wed, Nov 06, 2024 at 02:53:46PM +0100, Peter Zijlstra wrote:
> 
> > diff --git a/kernel/sched/core.c b/kernel/sched/core.c
> > index 54d82c21fc8e..b083c6385e88 100644
> > --- a/kernel/sched/core.c
> > +++ b/kernel/sched/core.c
> > @@ -3774,28 +3774,38 @@ ttwu_do_activate(struct rq *rq, struct task_struct *p, int wake_flags,
> >   */
> >  static int ttwu_runnable(struct task_struct *p, int wake_flags)
> >  {
> > +	CLASS(__task_rq_lock, rq_guard)(p);
> > +	struct rq *rq = rq_guard.rq;
> >  
> > +	if (!task_on_rq_queued(p))
> > +		return 0;
> > +
> > +	update_rq_clock(rq);
> > +	if (p->se.sched_delayed) {
> > +		int queue_flags = ENQUEUE_DELAYED | ENQUEUE_NOCLOCK;
> > +
> > +		/*
> > +		 * Since sched_delayed means we cannot be current anywhere,
> > +		 * dequeue it here and have it fall through to the
> > +		 * select_task_rq() case further along the ttwu() path.
> > +		 */
> > +		if (rq->nr_running > 1 && p->nr_cpus_allowed > 1) {
> > +			dequeue_task(rq, p, DEQUEUE_SLEEP | queue_flags);
> > +			return 0;
> >  		}
> > +
> > +		enqueue_task(rq, p, queue_flags);
> 
> And then I wondered... this means that !task_on_cpu() is true for
> sched_delayed, and thus we can move this in the below branch.
> 
> But also, we can probably dequeue every such task, not only
> sched_delayed ones.
> 
> >  	}
> > +	if (!task_on_cpu(rq, p)) {
> > +		/*
> > +		 * When on_rq && !on_cpu the task is preempted, see if
> > +		 * it should preempt the task that is current now.
> > +		 */
> > +		wakeup_preempt(rq, p, wake_flags);
> > +	}
> > +	ttwu_do_wakeup(p);
> >  
> > +	return 1;
> >  }
> 
> 
> Yielding something like this on top... which boots. But since I forgot
> to make it a feature, I can't actually tell at this point.. *sigh*

It dies real fast, so clearly I'm missing something. Oh well.

Re: [PATCH 17/24] sched/fair: Implement delayed dequeue

[Peter Zijlstra]

On Wed, Nov 06, 2024 at 03:14:58PM +0100, Mike Galbraith wrote:
> On Wed, 2024-11-06 at 14:53 +0100, Peter Zijlstra wrote:
> > 
> > So... I was trying to make that prettier and ended up with something
> > like this:
> 
> Passing ENQUEUE_DELAYED to dequeue_task() looks funky until you check
> the value, but otherwise yeah, when applied that looks better to me.

Yeah, it does look funneh, but we've been doing that for a long long
while.

Still, perhaps I should rename the shared ones to QUEUE_foo and only
have the specific ones be {EN,DE}QUEUE_foo.

Re: [PATCH 17/24] sched/fair: Implement delayed dequeue

[Mike Galbraith]

On Wed, 2024-11-06 at 14:53 +0100, Peter Zijlstra wrote:
> 
> So... I was trying to make that prettier and ended up with something
> like this:

Passing ENQUEUE_DELAYED to dequeue_task() looks funky until you check
the value, but otherwise yeah, when applied that looks better to me.

> 
> ---
>  kernel/sched/core.c  | 46 ++++++++++++++++++++++++++++------------------
>  kernel/sched/sched.h |  5 +++++
>  2 files changed, 33 insertions(+), 18 deletions(-)
> 
> diff --git a/kernel/sched/core.c b/kernel/sched/core.c
> index 54d82c21fc8e..b083c6385e88 100644
> --- a/kernel/sched/core.c
> +++ b/kernel/sched/core.c
> @@ -3774,28 +3774,38 @@ ttwu_do_activate(struct rq *rq, struct task_struct *p, int wake_flags,
>   */
>  static int ttwu_runnable(struct task_struct *p, int wake_flags)
>  {
> -       struct rq_flags rf;
> -       struct rq *rq;
> -       int ret = 0;
> +       CLASS(__task_rq_lock, rq_guard)(p);
> +       struct rq *rq = rq_guard.rq;
>  
> -       rq = __task_rq_lock(p, &rf);
> -       if (task_on_rq_queued(p)) {
> -               update_rq_clock(rq);
> -               if (p->se.sched_delayed)
> -                       enqueue_task(rq, p, ENQUEUE_NOCLOCK | ENQUEUE_DELAYED);
> -               if (!task_on_cpu(rq, p)) {
> -                       /*
> -                        * When on_rq && !on_cpu the task is preempted, see if
> -                        * it should preempt the task that is current now.
> -                        */
> -                       wakeup_preempt(rq, p, wake_flags);
> +       if (!task_on_rq_queued(p))
> +               return 0;
> +
> +       update_rq_clock(rq);
> +       if (p->se.sched_delayed) {
> +               int queue_flags = ENQUEUE_DELAYED | ENQUEUE_NOCLOCK;
> +
> +               /*
> +                * Since sched_delayed means we cannot be current anywhere,
> +                * dequeue it here and have it fall through to the
> +                * select_task_rq() case further along the ttwu() path.
> +                */
> +               if (rq->nr_running > 1 && p->nr_cpus_allowed > 1) {
> +                       dequeue_task(rq, p, DEQUEUE_SLEEP | queue_flags);
> +                       return 0;
>                 }
> -               ttwu_do_wakeup(p);
> -               ret = 1;
> +
> +               enqueue_task(rq, p, queue_flags);
>         }
> -       __task_rq_unlock(rq, &rf);
> +       if (!task_on_cpu(rq, p)) {
> +               /*
> +                * When on_rq && !on_cpu the task is preempted, see if
> +                * it should preempt the task that is current now.
> +                */
> +               wakeup_preempt(rq, p, wake_flags);
> +       }
> +       ttwu_do_wakeup(p);
>  
> -       return ret;
> +       return 1;
>  }
>  
>  #ifdef CONFIG_SMP
> diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
> index 21b1780c6695..1714ac38500f 100644
> --- a/kernel/sched/sched.h
> +++ b/kernel/sched/sched.h
> @@ -1787,6 +1787,11 @@ task_rq_unlock(struct rq *rq, struct task_struct *p, struct rq_flags *rf)
>         raw_spin_unlock_irqrestore(&p->pi_lock, rf->flags);
>  }
>  
> +DEFINE_LOCK_GUARD_1(__task_rq_lock, struct task_struct,
> +                   _T->rq = __task_rq_lock(_T->lock, &_T->rf),
> +                   __task_rq_unlock(_T->rq, &_T->rf),
> +                   struct rq *rq; struct rq_flags rf)
> +
>  DEFINE_LOCK_GUARD_1(task_rq_lock, struct task_struct,
>                     _T->rq = task_rq_lock(_T->lock, &_T->rf),
>                     task_rq_unlock(_T->rq, _T->lock, &_T->rf),

Re: [PATCH 17/24] sched/fair: Implement delayed dequeue

[Peter Zijlstra]

On Wed, Nov 06, 2024 at 02:53:46PM +0100, Peter Zijlstra wrote:

> diff --git a/kernel/sched/core.c b/kernel/sched/core.c
> index 54d82c21fc8e..b083c6385e88 100644
> --- a/kernel/sched/core.c
> +++ b/kernel/sched/core.c
> @@ -3774,28 +3774,38 @@ ttwu_do_activate(struct rq *rq, struct task_struct *p, int wake_flags,
>   */
>  static int ttwu_runnable(struct task_struct *p, int wake_flags)
>  {
> +	CLASS(__task_rq_lock, rq_guard)(p);
> +	struct rq *rq = rq_guard.rq;
>  
> +	if (!task_on_rq_queued(p))
> +		return 0;
> +
> +	update_rq_clock(rq);
> +	if (p->se.sched_delayed) {
> +		int queue_flags = ENQUEUE_DELAYED | ENQUEUE_NOCLOCK;
> +
> +		/*
> +		 * Since sched_delayed means we cannot be current anywhere,
> +		 * dequeue it here and have it fall through to the
> +		 * select_task_rq() case further along the ttwu() path.
> +		 */
> +		if (rq->nr_running > 1 && p->nr_cpus_allowed > 1) {
> +			dequeue_task(rq, p, DEQUEUE_SLEEP | queue_flags);
> +			return 0;
>  		}
> +
> +		enqueue_task(rq, p, queue_flags);

And then I wondered... this means that !task_on_cpu() is true for
sched_delayed, and thus we can move this in the below branch.

But also, we can probably dequeue every such task, not only
sched_delayed ones.

>  	}
> +	if (!task_on_cpu(rq, p)) {
> +		/*
> +		 * When on_rq && !on_cpu the task is preempted, see if
> +		 * it should preempt the task that is current now.
> +		 */
> +		wakeup_preempt(rq, p, wake_flags);
> +	}
> +	ttwu_do_wakeup(p);
>  
> +	return 1;
>  }


Yielding something like this on top... which boots. But since I forgot
to make it a feature, I can't actually tell at this point.. *sigh*

Anyway, more toys to poke at I suppose.


diff --git a/kernel/sched/core.c b/kernel/sched/core.c
index b083c6385e88..69b19ba77598 100644
--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -3781,28 +3781,32 @@ static int ttwu_runnable(struct task_struct *p, int wake_flags)
 		return 0;
 
 	update_rq_clock(rq);
-	if (p->se.sched_delayed) {
-		int queue_flags = ENQUEUE_DELAYED | ENQUEUE_NOCLOCK;
+	if (!task_on_cpu(rq, p)) {
+		int queue_flags = DEQUEUE_NOCLOCK;
+
+		if (p->se.sched_delayed)
+			queue_flags |= DEQUEUE_DELAYED;
 
 		/*
-		 * Since sched_delayed means we cannot be current anywhere,
-		 * dequeue it here and have it fall through to the
-		 * select_task_rq() case further along the ttwu() path.
+		 * Since we're not current anywhere *AND* hold pi_lock, dequeue
+		 * it here and have it fall through to the select_task_rq()
+		 * case further along the ttwu() path.
 		 */
 		if (rq->nr_running > 1 && p->nr_cpus_allowed > 1) {
 			dequeue_task(rq, p, DEQUEUE_SLEEP | queue_flags);
 			return 0;
 		}
 
-		enqueue_task(rq, p, queue_flags);
-	}
-	if (!task_on_cpu(rq, p)) {
+		if (p->se.sched_delayed)
+			enqueue_task(rq, p, queue_flags);
+
 		/*
 		 * When on_rq && !on_cpu the task is preempted, see if
 		 * it should preempt the task that is current now.
 		 */
 		wakeup_preempt(rq, p, wake_flags);
 	}
+	SCHED_WARN_ON(p->se.sched_delayed);
 	ttwu_do_wakeup(p);
 
 	return 1;

Re: [PATCH 17/24] sched/fair: Implement delayed dequeue

[Peter Zijlstra]

On Tue, Nov 05, 2024 at 05:05:12AM +0100, Mike Galbraith wrote:

> After one minute of lightly loaded box browsing, trace_printk() said:
> 
>   645   - racy peek says there is a room available
>    11   - cool, reserved room is free
>   206   - no vacancy or wakee pinned
> 38807   - SIS accommodates room seeker
> 
> The below should improve the odds, but high return seems unlikely.
> 
> ---
>  kernel/sched/core.c |    9 ++++++++-
>  1 file changed, 8 insertions(+), 1 deletion(-)
> 
> --- a/kernel/sched/core.c
> +++ b/kernel/sched/core.c
> @@ -3790,7 +3790,13 @@ static int ttwu_runnable(struct task_str
>  	rq = __task_rq_lock(p, &rf);
>  	if (task_on_rq_queued(p)) {
>  		update_rq_clock(rq);
> -		if (p->se.sched_delayed)
> +		/*
> +		 * If wakee is mobile and the room it reserved is occupied, let it try to migrate.
> +		 */
> +		if (p->se.sched_delayed && rq->nr_running > 1 && cpumask_weight(p->cpus_ptr) > 1) {
> +			dequeue_task(rq, p, DEQUEUE_SLEEP | DEQUEUE_DELAYED | DEQUEUE_NOCLOCK);
> +			goto out_unlock;
> +		} else if (p->se.sched_delayed)
>  			enqueue_task(rq, p, ENQUEUE_NOCLOCK | ENQUEUE_DELAYED);
>  		if (!task_on_cpu(rq, p)) {
>  			/*
> @@ -3802,6 +3808,7 @@ static int ttwu_runnable(struct task_str
>  		ttwu_do_wakeup(p);
>  		ret = 1;
>  	}
> +out_unlock:
>  	__task_rq_unlock(rq, &rf);
> 
>  	return ret;

So... I was trying to make that prettier and ended up with something
like this:

---
 kernel/sched/core.c  | 46 ++++++++++++++++++++++++++++------------------
 kernel/sched/sched.h |  5 +++++
 2 files changed, 33 insertions(+), 18 deletions(-)

diff --git a/kernel/sched/core.c b/kernel/sched/core.c
index 54d82c21fc8e..b083c6385e88 100644
--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -3774,28 +3774,38 @@ ttwu_do_activate(struct rq *rq, struct task_struct *p, int wake_flags,
  */
 static int ttwu_runnable(struct task_struct *p, int wake_flags)
 {
-	struct rq_flags rf;
-	struct rq *rq;
-	int ret = 0;
+	CLASS(__task_rq_lock, rq_guard)(p);
+	struct rq *rq = rq_guard.rq;
 
-	rq = __task_rq_lock(p, &rf);
-	if (task_on_rq_queued(p)) {
-		update_rq_clock(rq);
-		if (p->se.sched_delayed)
-			enqueue_task(rq, p, ENQUEUE_NOCLOCK | ENQUEUE_DELAYED);
-		if (!task_on_cpu(rq, p)) {
-			/*
-			 * When on_rq && !on_cpu the task is preempted, see if
-			 * it should preempt the task that is current now.
-			 */
-			wakeup_preempt(rq, p, wake_flags);
+	if (!task_on_rq_queued(p))
+		return 0;
+
+	update_rq_clock(rq);
+	if (p->se.sched_delayed) {
+		int queue_flags = ENQUEUE_DELAYED | ENQUEUE_NOCLOCK;
+
+		/*
+		 * Since sched_delayed means we cannot be current anywhere,
+		 * dequeue it here and have it fall through to the
+		 * select_task_rq() case further along the ttwu() path.
+		 */
+		if (rq->nr_running > 1 && p->nr_cpus_allowed > 1) {
+			dequeue_task(rq, p, DEQUEUE_SLEEP | queue_flags);
+			return 0;
 		}
-		ttwu_do_wakeup(p);
-		ret = 1;
+
+		enqueue_task(rq, p, queue_flags);
 	}
-	__task_rq_unlock(rq, &rf);
+	if (!task_on_cpu(rq, p)) {
+		/*
+		 * When on_rq && !on_cpu the task is preempted, see if
+		 * it should preempt the task that is current now.
+		 */
+		wakeup_preempt(rq, p, wake_flags);
+	}
+	ttwu_do_wakeup(p);
 
-	return ret;
+	return 1;
 }
 
 #ifdef CONFIG_SMP
diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
index 21b1780c6695..1714ac38500f 100644
--- a/kernel/sched/sched.h
+++ b/kernel/sched/sched.h
@@ -1787,6 +1787,11 @@ task_rq_unlock(struct rq *rq, struct task_struct *p, struct rq_flags *rf)
 	raw_spin_unlock_irqrestore(&p->pi_lock, rf->flags);
 }
 
+DEFINE_LOCK_GUARD_1(__task_rq_lock, struct task_struct,
+		    _T->rq = __task_rq_lock(_T->lock, &_T->rf),
+		    __task_rq_unlock(_T->rq, &_T->rf),
+		    struct rq *rq; struct rq_flags rf)
+
 DEFINE_LOCK_GUARD_1(task_rq_lock, struct task_struct,
 		    _T->rq = task_rq_lock(_T->lock, &_T->rf),
 		    task_rq_unlock(_T->rq, _T->lock, &_T->rf),

Re: [PATCH 17/24] sched/fair: Implement delayed dequeue

[K Prateek Nayak]

Hello Mike,

On 11/5/2024 12:16 PM, Mike Galbraith wrote:
> On Tue, 2024-11-05 at 09:52 +0530, K Prateek Nayak wrote:
>> Hello Mike,
> 
> Greetings,
> 
>> Would checking "p->nr_cpus_allowed > 1" be enough instead of doing a
>> "cpumask_weight(p->cpus_ptr) > 1"?
> 
> Yeah (thwap).
> 
>> I was thinking, since the task is indeed delayed, there has to be more
>> than one task on the runqueue right since a single task by itself cannot
>> be ineligible and be marked for delayed dequeue?
> 
> But they migrate via LB, and idle balance unlocks the rq.
> trace_printk() just verified that they do still both land with
> sched_delayed intact and with nr_running = 1.

Ah! You are right! thank you for clarifying. Since the sharp stick seems
to be working, let me go thrown a bunch of workloads at it and report
back :)

-- 
Thanks and Regards,
Prateek

> 
>> The only time we
>> encounter a delayed task with "rq->nr_running == 1" is if the other
>> tasks have been fully dequeued and pick_next_task() is in the process of
>> picking off all the delayed task, but since that is done with the rq
>> lock held in schedule(), it is even possible for the
>> "rq->nr_running > 1" to be false here?
> 
> I don't see how, the rq being looked at is locked.
> 
> 	-Mike

Re: [PATCH 17/24] sched/fair: Implement delayed dequeue

[Mike Galbraith]

On Tue, 2024-11-05 at 14:05 -0500, Phil Auld wrote:
>
> Well that worked pretty well. It actually makes DELAY_DEQUEUE a litte better
> than NO_DELAY_DEQUEUE
>
> DELAY_DEQUEUE     ~595MB/s
> NO_DELAY_DEQUEUE  ~581MB/s

Hrmph, not the expected result, but sharp stick's mission was to
confirm/deny that delta's relevance, so job well done.. kindling.

	-Mike

Re: [PATCH 17/24] sched/fair: Implement delayed dequeue

[Phil Auld]

On Tue, Nov 05, 2024 at 10:20:10AM -0500 Phil Auld wrote:
> On Tue, Nov 05, 2024 at 05:05:12AM +0100 Mike Galbraith wrote:
> > On Mon, 2024-11-04 at 08:05 -0500, Phil Auld wrote:
> > > On Sat, Nov 02, 2024 at 05:32:14AM +0100 Mike Galbraith wrote:
> > >
> > > >
> > > > The buddy being preempted certainly won't be wakeup migrated...
> > >
> > > Not the waker who gets preempted but the wakee may be a bit more
> > > sticky on his current cpu and thus stack more since he's still
> > > in that runqueue.
> > 
> > Ah, indeed, if wakees don't get scraped off before being awakened, they
> > can and do miss chances at an idle CPU according to trace_printk().
> > 
> > I'm undecided if overall it's boon, bane or even matters, as there is
> > still an ample supply of wakeup migration, but seems it can indeed
> > inject wakeup latency needlessly, so <sharpens stick>...
> > 
> > My box booted and neither become exceptionally noisy nor inexplicably
> > silent in.. oh, minutes now, so surely yours will be perfectly fine.
> > 
> > After one minute of lightly loaded box browsing, trace_printk() said:
> > 
> >   645   - racy peek says there is a room available
> >    11   - cool, reserved room is free
> >   206   - no vacancy or wakee pinned
> > 38807   - SIS accommodates room seeker
> > 
> > The below should improve the odds, but high return seems unlikely.
> >
> 
> Thanks, I'll give it a spin with the nr_cpus_allowed bit.
>

Well that worked pretty well. It actually makes DELAY_DEQUEUE a litte better
than NO_DELAY_DEQUEUE

DELAY_DEQUEUE     ~595MB/s
NO_DELAY_DEQUEUE  ~581MB/s

I left the cpumask_weight becaude vim isn't happy with my terminal to that machine
for some reason I have not found yet. So I couldn't actually edit the darn thing.
This is not my normal build setup. But I'll spin up a real build with this patch
and throw it over the wall to the perf team to have them do their full battery
of tests on it.

Probably "Paul" will be cranky now. 


Thanks,
Phil


> 
> Cheers,
> Phil
> 
> 
> 
> > ---
> >  kernel/sched/core.c |    9 ++++++++-
> >  1 file changed, 8 insertions(+), 1 deletion(-)
> > 
> > --- a/kernel/sched/core.c
> > +++ b/kernel/sched/core.c
> > @@ -3790,7 +3790,13 @@ static int ttwu_runnable(struct task_str
> >  	rq = __task_rq_lock(p, &rf);
> >  	if (task_on_rq_queued(p)) {
> >  		update_rq_clock(rq);
> > -		if (p->se.sched_delayed)
> > +		/*
> > +		 * If wakee is mobile and the room it reserved is occupied, let it try to migrate.
> > +		 */
> > +		if (p->se.sched_delayed && rq->nr_running > 1 && cpumask_weight(p->cpus_ptr) > 1) {
> > +			dequeue_task(rq, p, DEQUEUE_SLEEP | DEQUEUE_DELAYED | DEQUEUE_NOCLOCK);
> > +			goto out_unlock;
> > +		} else if (p->se.sched_delayed)
> >  			enqueue_task(rq, p, ENQUEUE_NOCLOCK | ENQUEUE_DELAYED);
> >  		if (!task_on_cpu(rq, p)) {
> >  			/*
> > @@ -3802,6 +3808,7 @@ static int ttwu_runnable(struct task_str
> >  		ttwu_do_wakeup(p);
> >  		ret = 1;
> >  	}
> > +out_unlock:
> >  	__task_rq_unlock(rq, &rf);
> > 
> >  	return ret;
> > 
> > 
> 
> -- 
> 
> 

-- 

Re: [PATCH 17/24] sched/fair: Implement delayed dequeue

[Phil Auld]

Hi Christian,

On Tue, Nov 05, 2024 at 09:53:49AM +0000 Christian Loehle wrote:
> On 11/4/24 12:50, Phil Auld wrote:
> > 
> > Hi Dietmar,
> > 
> > On Mon, Nov 04, 2024 at 10:28:37AM +0100 Dietmar Eggemann wrote:
> >> Hi Phil,
> >>
> >> On 01/11/2024 13:47, Phil Auld wrote:
> >>>
> >>> Hi Peterm
> >>>
> >>> On Sat, Jul 27, 2024 at 12:27:49PM +0200 Peter Zijlstra wrote:
> >>>> Extend / fix 86bfbb7ce4f6 ("sched/fair: Add lag based placement") by
> >>>> noting that lag is fundamentally a temporal measure. It should not be
> >>>> carried around indefinitely.
> >>>>
> >>>> OTOH it should also not be instantly discarded, doing so will allow a
> >>>> task to game the system by purposefully (micro) sleeping at the end of
> >>>> its time quantum.
> >>>>
> >>>> Since lag is intimately tied to the virtual time base, a wall-time
> >>>> based decay is also insufficient, notably competition is required for
> >>>> any of this to make sense.
> >>>>
> >>>> Instead, delay the dequeue and keep the 'tasks' on the runqueue,
> >>>> competing until they are eligible.
> >>>>
> >>>> Strictly speaking, we only care about keeping them until the 0-lag
> >>>> point, but that is a difficult proposition, instead carry them around
> >>>> until they get picked again, and dequeue them at that point.
> >>>
> >>> This one is causing a 10-20% performance hit on our filesystem tests.
> >>>
> >>> On 6.12-rc5 (so with the latest follow ons) we get:
> >>>
> >>> with DELAY_DEQUEUE the bandwidth is 510 MB/s
> >>> with NO_DELAY_DEQUEUE the bandwidth is 590 MB/s
> >>>
> >>> The test is fio, something like this:
> >>>
> >>> taskset -c 1,2,3,4,5,6,7,8 fio --rw randwrite --bs 4k --runtime 1m --fsync 0 --iodepth 32 --direct 1 --ioengine libaio --numjobs 8 --size 30g --nrfiles 1 --loops 1 --name default --randrepeat 1 --time_based --group_reporting --directory /testfs
> >>
> >> I'm not seeing this on my i7-13700K running tip sched/core (1a6151017ee5
> >> - sched: psi: pass enqueue/dequeue flags to psi callbacks directly
> >> (2024-10-26 Johannes Weiner)) (6.12.0-rc4 - based)
> >>
> >> Using 'taskset 0xaaaaa' avoiding SMT and running only on P-cores.
> >>
> >> vanilla features: 990MB/s (mean out of 5 runs, σ:  9.38)
> >> NO_DELAY_DEQUEUE: 992MB/s (mean out of 5 runs, σ: 10.61)
> >>
> >> # sudo lshw -class disk -class storage
> >>   *-nvme                    
> >>        description: NVMe device
> >>        product: GIGABYTE GP-ASM2NE6500GTTD
> >>        vendor: Phison Electronics Corporation
> >>        physical id: 0
> >>        bus info: pci@0000:01:00.0
> >>        logical name: /dev/nvme0
> >>        version: EGFM13.2
> >>        ...
> >>        capabilities: nvme pciexpress msix msi pm nvm_express bus_master cap_list
> >>        configuration: driver=nvme latency=0 nqn=nqn.2014.08.org.nvmexpress:19871987SN215108954872 GIGABYTE GP-ASM2NE6500GTTD state=live
> >>        resources: irq:16 memory:70800000-70803fff 
> >>
> >> # mount | grep ^/dev/nvme0
> >> /dev/nvme0n1p2 on / type ext4 (rw,relatime,errors=remount-ro)
> >>
> >> Which disk device you're using?
> > 
> > Most of the reports are on various NVME drives (samsung mostly I think).
> > 
> > 
> > One thing I should add is that it's all on LVM: 
> > 
> > 
> > vgcreate vg /dev/nvme0n1 -y
> > lvcreate -n thinMeta -L 3GB vg -y
> > lvcreate -n thinPool -l 99%FREE vg -y
> > lvconvert --thinpool /dev/mapper/vg-thinPool --poolmetadata /dev/mapper/vg-thinMeta -Zn -y
> > lvcreate -n testLV -V 1300G --thinpool thinPool vg
> > wipefs -a /dev/mapper/vg-testLV
> > mkfs.ext4 /dev/mapper/vg-testLV -E lazy_itable_init=0,lazy_journal_init=0 -F
> > mount /dev/mapper/vg-testLV /testfs 
> > 
> > 
> > With VDO or thinpool (as above) it shows on both ext4 and xfs. With fs on
> > drive directly it's a little more variable. Some it shows on xfs, some it show
> > on ext4 and not vice-versa, seems to depend on the drive or hw raid. But when
> > it shows it's 100% reproducible on that setup. 
> > 
> > It's always the randwrite numbers. The rest look fine.
> 
> Hi Phil,
> 
> Thanks for the detailed instructions. Unfortunately even with your LVM setup on
> the platforms I've tried I don't see a regression so far, all the numbers are
> about equal for DELAY_DEQUEUE and NO_DELAY_DEQUEUE.
>

Yeah, that's odd.

Fwiw:

Architecture:             x86_64
  CPU op-mode(s):         32-bit, 64-bit
  Address sizes:          48 bits physical, 48 bits virtual
  Byte Order:             Little Endian
CPU(s):                   32
  On-line CPU(s) list:    0-31
Vendor ID:                AuthenticAMD
  BIOS Vendor ID:         Advanced Micro Devices, Inc.
  Model name:             AMD EPYC 7313P 16-Core Processor
    BIOS Model name:      AMD EPYC 7313P 16-Core Processor                Unknown CPU @ 3.0GHz
    BIOS CPU family:      107
    CPU family:           25
    ...

16 SMT2 cores (siblings are 16-31)


#lsblk -N
NAME    TYPE MODEL                      SERIAL              REV TRAN   RQ-SIZE  MQ
nvme3n1 disk SAMSUNG MZQL21T9HCJR-00A07 S64GNJ0T605178 GDC5602Q nvme      1023  32
nvme2n1 disk SAMSUNG MZQL21T9HCJR-00A07 S64GNJ0T605128 GDC5602Q nvme      1023  32
nvme0n1 disk SAMSUNG MZQL21T9HCJR-00A07 S64GNJ0T605125 GDC5602Q nvme      1023  32
nvme1n1 disk SAMSUNG MZQL21T9HCJR-00A07 S64GNJ0T605127 GDC5602Q nvme      1023  32

Where nvme0n1 is the one I'm actually using.

I'm on 6.12.0-0.rc5.44.eln143.x86_64  which is v6.12-rc5 with RHEL .config.  This
should have little to no franken-kernel bits but now that I have the machine
I'll build from upstream (with the RHEL .config still) to make sure.

We did see it on all the RCs so far. 


> Anyway I have some follow-ups, first let me trim the fio command for readability:
> fio --rw randwrite --bs 4k --runtime 1m --fsync 0 --iodepth 32 --direct 1 --ioengine libaio --numjobs 8 --size 30g --nrfiles 1 --loops 1 --name default --randrepeat 1 --time_based --group_reporting --directory /testfs
> 
> dropping defaults nr_files, loops, fsync, randrepeat
> fio --rw randwrite --bs 4k --runtime 1m --iodepth 32 --direct 1 --ioengine libaio --numjobs 8 --size 30g --name default --time_based --group_reporting --directory /testfs
> 
> Adding the CPU affinities directly:
> fio --cpus_allowed 1-8 --rw randwrite --bs 4k --runtime 1m --iodepth 32 --direct 1 --ioengine libaio --numjobs 8 --size 30g --name default --time_based --group_reporting --directory /testfs
>

Fair enough.  It should work the same with taskset I suppose except the below bit. I've
been given this from our perforance team. They have a framework that produces nice html
pages with red and green results and graphs and whatnot.  Right now it's in the form of
a script that pulls the KB/s number of out the json output which is nice and keeps me
from going crosseyed looking at the full fio run output.

> Now I was wondering about the following:
> Is it actually the kworker (not another fio) being preempted? (I'm pretty sure it is)
> To test: --cpus_allowed_policy split (each fio process gets it's own CPU).

with  --cpus-allowed and --cpus_allowed_policy split the results with DELAY_DEQUEUE are
better (540MB/s) but with NO_DELAY_DEQUEUE they are also better (640 MB/s). It was
510MB/s and 590MB/s before. 

> 
> You wrote:
> >I was thinking maybe the preemption was preventing some batching of IO completions or
> >initiations. But that was wrong it seems.
> 
> So while it doesn't reproduce for me, the only thing being preempted regularly is
> the kworker (running iomap_dio_complete_work). I don't quite follow the "that was
> wrong it seems" part then. Could you elaborate?
>

I was thinking that the fio batch test along with the disabling WAKEUP_PREEMPTION
was telling me that it wasn't the over preemption issue, but that also I could be
wrong about...


> Could you also post the other benchmark numbers? Does any of them score higher in IOPS?
> Is --rw write the same issue if you set --bs 4k (assuming you set a larger bs for seqwrite).
>

I don't have numbers for all of the other flavors but I ran --rw write --bs 4k:

DELAY_DEQUEUE     ~590MB/s
NO_DELAY_DEQUEUE  ~840MB/s

Those results are not good for DELAY_DEQUEUE either.

> Can you set the kworkers handling completions to SCHED_BATCH too? Just to confirm.

I think I did the wrong kworkes the first time. So I'll try again to figure out which
kworkers to twiddle (or I'll just do all 227 of them...).



Thanks,
Phil


> 
> Regards,
> Christian
> 

-- 

Re: [PATCH 17/24] sched/fair: Implement delayed dequeue

[Phil Auld]

On Tue, Nov 05, 2024 at 05:05:12AM +0100 Mike Galbraith wrote:
> On Mon, 2024-11-04 at 08:05 -0500, Phil Auld wrote:
> > On Sat, Nov 02, 2024 at 05:32:14AM +0100 Mike Galbraith wrote:
> >
> > >
> > > The buddy being preempted certainly won't be wakeup migrated...
> >
> > Not the waker who gets preempted but the wakee may be a bit more
> > sticky on his current cpu and thus stack more since he's still
> > in that runqueue.
> 
> Ah, indeed, if wakees don't get scraped off before being awakened, they
> can and do miss chances at an idle CPU according to trace_printk().
> 
> I'm undecided if overall it's boon, bane or even matters, as there is
> still an ample supply of wakeup migration, but seems it can indeed
> inject wakeup latency needlessly, so <sharpens stick>...
> 
> My box booted and neither become exceptionally noisy nor inexplicably
> silent in.. oh, minutes now, so surely yours will be perfectly fine.
> 
> After one minute of lightly loaded box browsing, trace_printk() said:
> 
>   645   - racy peek says there is a room available
>    11   - cool, reserved room is free
>   206   - no vacancy or wakee pinned
> 38807   - SIS accommodates room seeker
> 
> The below should improve the odds, but high return seems unlikely.
>

Thanks, I'll give it a spin with the nr_cpus_allowed bit.


Cheers,
Phil



> ---
>  kernel/sched/core.c |    9 ++++++++-
>  1 file changed, 8 insertions(+), 1 deletion(-)
> 
> --- a/kernel/sched/core.c
> +++ b/kernel/sched/core.c
> @@ -3790,7 +3790,13 @@ static int ttwu_runnable(struct task_str
>  	rq = __task_rq_lock(p, &rf);
>  	if (task_on_rq_queued(p)) {
>  		update_rq_clock(rq);
> -		if (p->se.sched_delayed)
> +		/*
> +		 * If wakee is mobile and the room it reserved is occupied, let it try to migrate.
> +		 */
> +		if (p->se.sched_delayed && rq->nr_running > 1 && cpumask_weight(p->cpus_ptr) > 1) {
> +			dequeue_task(rq, p, DEQUEUE_SLEEP | DEQUEUE_DELAYED | DEQUEUE_NOCLOCK);
> +			goto out_unlock;
> +		} else if (p->se.sched_delayed)
>  			enqueue_task(rq, p, ENQUEUE_NOCLOCK | ENQUEUE_DELAYED);
>  		if (!task_on_cpu(rq, p)) {
>  			/*
> @@ -3802,6 +3808,7 @@ static int ttwu_runnable(struct task_str
>  		ttwu_do_wakeup(p);
>  		ret = 1;
>  	}
> +out_unlock:
>  	__task_rq_unlock(rq, &rf);
> 
>  	return ret;
> 
> 

-- 

Re: [PATCH 17/24] sched/fair: Implement delayed dequeue

[Christian Loehle]

On 11/4/24 12:50, Phil Auld wrote:
> 
> Hi Dietmar,
> 
> On Mon, Nov 04, 2024 at 10:28:37AM +0100 Dietmar Eggemann wrote:
>> Hi Phil,
>>
>> On 01/11/2024 13:47, Phil Auld wrote:
>>>
>>> Hi Peterm
>>>
>>> On Sat, Jul 27, 2024 at 12:27:49PM +0200 Peter Zijlstra wrote:
>>>> Extend / fix 86bfbb7ce4f6 ("sched/fair: Add lag based placement") by
>>>> noting that lag is fundamentally a temporal measure. It should not be
>>>> carried around indefinitely.
>>>>
>>>> OTOH it should also not be instantly discarded, doing so will allow a
>>>> task to game the system by purposefully (micro) sleeping at the end of
>>>> its time quantum.
>>>>
>>>> Since lag is intimately tied to the virtual time base, a wall-time
>>>> based decay is also insufficient, notably competition is required for
>>>> any of this to make sense.
>>>>
>>>> Instead, delay the dequeue and keep the 'tasks' on the runqueue,
>>>> competing until they are eligible.
>>>>
>>>> Strictly speaking, we only care about keeping them until the 0-lag
>>>> point, but that is a difficult proposition, instead carry them around
>>>> until they get picked again, and dequeue them at that point.
>>>
>>> This one is causing a 10-20% performance hit on our filesystem tests.
>>>
>>> On 6.12-rc5 (so with the latest follow ons) we get:
>>>
>>> with DELAY_DEQUEUE the bandwidth is 510 MB/s
>>> with NO_DELAY_DEQUEUE the bandwidth is 590 MB/s
>>>
>>> The test is fio, something like this:
>>>
>>> taskset -c 1,2,3,4,5,6,7,8 fio --rw randwrite --bs 4k --runtime 1m --fsync 0 --iodepth 32 --direct 1 --ioengine libaio --numjobs 8 --size 30g --nrfiles 1 --loops 1 --name default --randrepeat 1 --time_based --group_reporting --directory /testfs
>>
>> I'm not seeing this on my i7-13700K running tip sched/core (1a6151017ee5
>> - sched: psi: pass enqueue/dequeue flags to psi callbacks directly
>> (2024-10-26 Johannes Weiner)) (6.12.0-rc4 - based)
>>
>> Using 'taskset 0xaaaaa' avoiding SMT and running only on P-cores.
>>
>> vanilla features: 990MB/s (mean out of 5 runs, σ:  9.38)
>> NO_DELAY_DEQUEUE: 992MB/s (mean out of 5 runs, σ: 10.61)
>>
>> # sudo lshw -class disk -class storage
>>   *-nvme                    
>>        description: NVMe device
>>        product: GIGABYTE GP-ASM2NE6500GTTD
>>        vendor: Phison Electronics Corporation
>>        physical id: 0
>>        bus info: pci@0000:01:00.0
>>        logical name: /dev/nvme0
>>        version: EGFM13.2
>>        ...
>>        capabilities: nvme pciexpress msix msi pm nvm_express bus_master cap_list
>>        configuration: driver=nvme latency=0 nqn=nqn.2014.08.org.nvmexpress:19871987SN215108954872 GIGABYTE GP-ASM2NE6500GTTD state=live
>>        resources: irq:16 memory:70800000-70803fff 
>>
>> # mount | grep ^/dev/nvme0
>> /dev/nvme0n1p2 on / type ext4 (rw,relatime,errors=remount-ro)
>>
>> Which disk device you're using?
> 
> Most of the reports are on various NVME drives (samsung mostly I think).
> 
> 
> One thing I should add is that it's all on LVM: 
> 
> 
> vgcreate vg /dev/nvme0n1 -y
> lvcreate -n thinMeta -L 3GB vg -y
> lvcreate -n thinPool -l 99%FREE vg -y
> lvconvert --thinpool /dev/mapper/vg-thinPool --poolmetadata /dev/mapper/vg-thinMeta -Zn -y
> lvcreate -n testLV -V 1300G --thinpool thinPool vg
> wipefs -a /dev/mapper/vg-testLV
> mkfs.ext4 /dev/mapper/vg-testLV -E lazy_itable_init=0,lazy_journal_init=0 -F
> mount /dev/mapper/vg-testLV /testfs 
> 
> 
> With VDO or thinpool (as above) it shows on both ext4 and xfs. With fs on
> drive directly it's a little more variable. Some it shows on xfs, some it show
> on ext4 and not vice-versa, seems to depend on the drive or hw raid. But when
> it shows it's 100% reproducible on that setup. 
> 
> It's always the randwrite numbers. The rest look fine.

Hi Phil,

Thanks for the detailed instructions. Unfortunately even with your LVM setup on
the platforms I've tried I don't see a regression so far, all the numbers are
about equal for DELAY_DEQUEUE and NO_DELAY_DEQUEUE.

Anyway I have some follow-ups, first let me trim the fio command for readability:
fio --rw randwrite --bs 4k --runtime 1m --fsync 0 --iodepth 32 --direct 1 --ioengine libaio --numjobs 8 --size 30g --nrfiles 1 --loops 1 --name default --randrepeat 1 --time_based --group_reporting --directory /testfs

dropping defaults nr_files, loops, fsync, randrepeat
fio --rw randwrite --bs 4k --runtime 1m --iodepth 32 --direct 1 --ioengine libaio --numjobs 8 --size 30g --name default --time_based --group_reporting --directory /testfs

Adding the CPU affinities directly:
fio --cpus_allowed 1-8 --rw randwrite --bs 4k --runtime 1m --iodepth 32 --direct 1 --ioengine libaio --numjobs 8 --size 30g --name default --time_based --group_reporting --directory /testfs

Now I was wondering about the following:
Is it actually the kworker (not another fio) being preempted? (I'm pretty sure it is)
To test: --cpus_allowed_policy split (each fio process gets it's own CPU).

You wrote:
>I was thinking maybe the preemption was preventing some batching of IO completions or
>initiations. But that was wrong it seems.

So while it doesn't reproduce for me, the only thing being preempted regularly is
the kworker (running iomap_dio_complete_work). I don't quite follow the "that was
wrong it seems" part then. Could you elaborate?

Could you also post the other benchmark numbers? Does any of them score higher in IOPS?
Is --rw write the same issue if you set --bs 4k (assuming you set a larger bs for seqwrite).

Can you set the kworkers handling completions to SCHED_BATCH too? Just to confirm.

Regards,
Christian

Re: [PATCH 17/24] sched/fair: Implement delayed dequeue

[Mike Galbraith]

On Tue, 2024-11-05 at 09:52 +0530, K Prateek Nayak wrote:
> Hello Mike,

Greetings,

> Would checking "p->nr_cpus_allowed > 1" be enough instead of doing a
> "cpumask_weight(p->cpus_ptr) > 1"?

Yeah (thwap).

> I was thinking, since the task is indeed delayed, there has to be more
> than one task on the runqueue right since a single task by itself cannot
> be ineligible and be marked for delayed dequeue?

But they migrate via LB, and idle balance unlocks the rq.
trace_printk() just verified that they do still both land with
sched_delayed intact and with nr_running = 1.

> The only time we
> encounter a delayed task with "rq->nr_running == 1" is if the other
> tasks have been fully dequeued and pick_next_task() is in the process of
> picking off all the delayed task, but since that is done with the rq
> lock held in schedule(), it is even possible for the
> "rq->nr_running > 1" to be false here?

I don't see how, the rq being looked at is locked.

	-Mike

Re: [PATCH 17/24] sched/fair: Implement delayed dequeue

[K Prateek Nayak]

Hello Mike,

On 11/5/2024 9:35 AM, Mike Galbraith wrote:
> On Mon, 2024-11-04 at 08:05 -0500, Phil Auld wrote:
>> On Sat, Nov 02, 2024 at 05:32:14AM +0100 Mike Galbraith wrote:
>>
>>>
>>> The buddy being preempted certainly won't be wakeup migrated...
>>
>> Not the waker who gets preempted but the wakee may be a bit more
>> sticky on his current cpu and thus stack more since he's still
>> in that runqueue.
> 
> Ah, indeed, if wakees don't get scraped off before being awakened, they
> can and do miss chances at an idle CPU according to trace_printk().
> 
> I'm undecided if overall it's boon, bane or even matters, as there is
> still an ample supply of wakeup migration, but seems it can indeed
> inject wakeup latency needlessly, so <sharpens stick>...

I had tried this out a while back but I was indiscriminately doing a
DEQUEUE_DELAYED and letting delayed tasks go through a full ttwu cycle
which did not yield any improvements on hackbench. Your approach to
selectively do it might indeed be better (more thoughts below)

> 
> My box booted and neither become exceptionally noisy nor inexplicably
> silent in.. oh, minutes now, so surely yours will be perfectly fine.
> 
> After one minute of lightly loaded box browsing, trace_printk() said:
> 
>    645   - racy peek says there is a room available
>     11   - cool, reserved room is free
>    206   - no vacancy or wakee pinned
> 38807   - SIS accommodates room seeker
> 
> The below should improve the odds, but high return seems unlikely.
> 
> ---
>   kernel/sched/core.c |    9 ++++++++-
>   1 file changed, 8 insertions(+), 1 deletion(-)
> 
> --- a/kernel/sched/core.c
> +++ b/kernel/sched/core.c
> @@ -3790,7 +3790,13 @@ static int ttwu_runnable(struct task_str
>   	rq = __task_rq_lock(p, &rf);
>   	if (task_on_rq_queued(p)) {
>   		update_rq_clock(rq);
> -		if (p->se.sched_delayed)
> +		/*
> +		 * If wakee is mobile and the room it reserved is occupied, let it try to migrate.
> +		 */
> +		if (p->se.sched_delayed && rq->nr_running > 1 && cpumask_weight(p->cpus_ptr) > 1) {

Would checking "p->nr_cpus_allowed > 1" be enough instead of doing a
"cpumask_weight(p->cpus_ptr) > 1"?

I was thinking, since the task is indeed delayed, there has to be more
than one task on the runqueue right since a single task by itself cannot
be ineligible and be marked for delayed dequeue? The only time we
encounter a delayed task with "rq->nr_running == 1" is if the other
tasks have been fully dequeued and pick_next_task() is in the process of
picking off all the delayed task, but since that is done with the rq
lock held in schedule(), it is even possible for the
"rq->nr_running > 1" to be false here?

> +			dequeue_task(rq, p, DEQUEUE_SLEEP | DEQUEUE_DELAYED | DEQUEUE_NOCLOCK);
> +			goto out_unlock;
> +		} else if (p->se.sched_delayed)
>   			enqueue_task(rq, p, ENQUEUE_NOCLOCK | ENQUEUE_DELAYED);
>   		if (!task_on_cpu(rq, p)) {
>   			/*
> @@ -3802,6 +3808,7 @@ static int ttwu_runnable(struct task_str
>   		ttwu_do_wakeup(p);
>   		ret = 1;
>   	}
> +out_unlock:
>   	__task_rq_unlock(rq, &rf);
> 
>   	return ret;
> 
> 

-- 
Thanks and Regards,
Prateek

Re: [PATCH 17/24] sched/fair: Implement delayed dequeue

[Mike Galbraith]

On Mon, 2024-11-04 at 08:05 -0500, Phil Auld wrote:
> On Sat, Nov 02, 2024 at 05:32:14AM +0100 Mike Galbraith wrote:
>
> >
> > The buddy being preempted certainly won't be wakeup migrated...
>
> Not the waker who gets preempted but the wakee may be a bit more
> sticky on his current cpu and thus stack more since he's still
> in that runqueue.

Ah, indeed, if wakees don't get scraped off before being awakened, they
can and do miss chances at an idle CPU according to trace_printk().

I'm undecided if overall it's boon, bane or even matters, as there is
still an ample supply of wakeup migration, but seems it can indeed
inject wakeup latency needlessly, so <sharpens stick>...

My box booted and neither become exceptionally noisy nor inexplicably
silent in.. oh, minutes now, so surely yours will be perfectly fine.

After one minute of lightly loaded box browsing, trace_printk() said:

  645   - racy peek says there is a room available
   11   - cool, reserved room is free
  206   - no vacancy or wakee pinned
38807   - SIS accommodates room seeker

The below should improve the odds, but high return seems unlikely.

---
 kernel/sched/core.c |    9 ++++++++-
 1 file changed, 8 insertions(+), 1 deletion(-)

--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -3790,7 +3790,13 @@ static int ttwu_runnable(struct task_str
 	rq = __task_rq_lock(p, &rf);
 	if (task_on_rq_queued(p)) {
 		update_rq_clock(rq);
-		if (p->se.sched_delayed)
+		/*
+		 * If wakee is mobile and the room it reserved is occupied, let it try to migrate.
+		 */
+		if (p->se.sched_delayed && rq->nr_running > 1 && cpumask_weight(p->cpus_ptr) > 1) {
+			dequeue_task(rq, p, DEQUEUE_SLEEP | DEQUEUE_DELAYED | DEQUEUE_NOCLOCK);
+			goto out_unlock;
+		} else if (p->se.sched_delayed)
 			enqueue_task(rq, p, ENQUEUE_NOCLOCK | ENQUEUE_DELAYED);
 		if (!task_on_cpu(rq, p)) {
 			/*
@@ -3802,6 +3808,7 @@ static int ttwu_runnable(struct task_str
 		ttwu_do_wakeup(p);
 		ret = 1;
 	}
+out_unlock:
 	__task_rq_unlock(rq, &rf);

 	return ret;

Re: [PATCH 17/24] sched/fair: Implement delayed dequeue

[Phil Auld]

On Sat, Nov 02, 2024 at 05:32:14AM +0100 Mike Galbraith wrote:
> On Fri, 2024-11-01 at 16:07 -0400, Phil Auld wrote:
> 
> 
> > Thanks for jumping in.  My jargon decoder ring seems to be failing me
> > so I'm not completely sure what you are saying below :)
> >
> > "buddies" you mean tasks that waking each other up and sleeping.
> > And one runs for longer than the other, right?
> 
> Yeah, buddies are related waker/wakee 1:1 1:N or M:N, excluding tasks
> happening to be sitting on a CPU where, say a timer fires, an IRQ leads
> to a wakeup of lord knows what, lock wakeups etc etc etc. I think Peter
> coined the term buddy to mean that (less typing), and it stuck.
>

Thanks!

> > > 1 tbench buddy pair scheduled cross core.
> > >
> > >   PID USER      PR  NI    VIRT    RES    SHR S  %CPU  %MEM     TIME+ P COMMAND
> > > 13770 root      20   0   21424   1920   1792 S 60.13 0.012   0:33.81 3 tbench
> > > 13771 root      20   0    4720    896    768 S 46.84 0.006   0:26.10 2 tbench_srv
> >  
> > > Note 60/47 utilization, now pinned/stacked.
> > >
> > > 6.1.114-cfs
> > >   PID USER      PR  NI    VIRT    RES    SHR S  %CPU  %MEM     TIME+ P COMMAND
> > >  4407 root      20   0   21424   1980   1772 R 50.00 0.012   0:29.20 3 tbench
> > >  4408 root      20   0    4720    124      0 R 50.00 0.001   0:28.76 3 tbench_srv
> >
> > What is the difference between these first two?  The first is on
> > separate cores so they don't interfere with each other? And the second is
> > pinned to the same core?
> 
> Yeah, see 'P'. Given CPU headroom, a tbench pair can consume ~107%.
> They're not fully synchronous.. wouldn't be relevant here/now if they
> were :)
> 
> > > Note what happens to the lighter tbench_srv. Consuming red hot L2 data,
> > > it can utilize a full 50%, but it must first preempt wide bottom buddy.
> > >
> >
> > We've got "light" and "wide" here which is a bit mixed metaphorically
> > :)
> 
> Wide, skinny, feather-weight or lard-ball, they all work for me.
> 
> > So here CFS is letting the wakee preempt the waker and providing pretty
> > equal fairness. And hot l2 caching is masking the assymmetry.
> 
> No, it's way simpler: preemption slices through the only thing it can
> slice through, the post wakeup concurrent bits.. that otherwise sits
> directly in the communication stream as a lump of latency in a latency
> bound operation.
> 
> >
> > With wakeup preemption off it doesn't help in my case. I was thinking
> > maybe the preemption was preventing some batching of IO completions
> > or
> > initiations. But that was wrong it seems.
> 
> Dunno.
> 
> > Does it also possibly make wakeup migration less likely and thus increase
> > stacking?
> 
> The buddy being preempted certainly won't be wakeup migrated, because
> it won't sleep. Two very sleepy tasks when bw constrained becomes one
> 100% hog and one 99.99% hog when CPU constrained.
>

Not the waker who gets preempted but the wakee may be a bit more
sticky on his current cpu and thus stack more since he's still
in that runqueue. But that's just a mental excercise trying to
find things that are directly related to delay dequeue. No observation
other than the over all perf hit. 


> > > Bottom line, box full of 1:1 buddies pairing up and stacking in L2.
> > >
> > > tbench 8
> > > 6.1.114-cfs      3674.37 MB/sec
> > > 6.1.114-eevdf    3505.25 MB/sec -delay_dequeue
> > >                  3701.66 MB/sec +delay_dequeue
> > >
> > > For tbench, preemption = shorter turnaround = higher throughput.
> >
> > So here you have a benchmark that gets a ~5% boost from
> > delayed_dequeue.
> >
> > But I've got one that get's a 20% penalty so I'm not exactly sure what
> > to make of that. Clearly FIO does not have the same pattern as tbench.
> 
> There are basically two options in sched-land, shave fastpath cycles,
> or some variant of Rob Peter to pay Paul ;-)
>

That Peter is cranky :)

Cheers,
Phil


> 	-Mike
> 

-- 

Re: [PATCH 17/24] sched/fair: Implement delayed dequeue

[Phil Auld]

Hi Dietmar,

On Mon, Nov 04, 2024 at 10:28:37AM +0100 Dietmar Eggemann wrote:
> Hi Phil,
> 
> On 01/11/2024 13:47, Phil Auld wrote:
> > 
> > Hi Peterm
> > 
> > On Sat, Jul 27, 2024 at 12:27:49PM +0200 Peter Zijlstra wrote:
> >> Extend / fix 86bfbb7ce4f6 ("sched/fair: Add lag based placement") by
> >> noting that lag is fundamentally a temporal measure. It should not be
> >> carried around indefinitely.
> >>
> >> OTOH it should also not be instantly discarded, doing so will allow a
> >> task to game the system by purposefully (micro) sleeping at the end of
> >> its time quantum.
> >>
> >> Since lag is intimately tied to the virtual time base, a wall-time
> >> based decay is also insufficient, notably competition is required for
> >> any of this to make sense.
> >>
> >> Instead, delay the dequeue and keep the 'tasks' on the runqueue,
> >> competing until they are eligible.
> >>
> >> Strictly speaking, we only care about keeping them until the 0-lag
> >> point, but that is a difficult proposition, instead carry them around
> >> until they get picked again, and dequeue them at that point.
> > 
> > This one is causing a 10-20% performance hit on our filesystem tests.
> > 
> > On 6.12-rc5 (so with the latest follow ons) we get:
> > 
> > with DELAY_DEQUEUE the bandwidth is 510 MB/s
> > with NO_DELAY_DEQUEUE the bandwidth is 590 MB/s
> > 
> > The test is fio, something like this:
> > 
> > taskset -c 1,2,3,4,5,6,7,8 fio --rw randwrite --bs 4k --runtime 1m --fsync 0 --iodepth 32 --direct 1 --ioengine libaio --numjobs 8 --size 30g --nrfiles 1 --loops 1 --name default --randrepeat 1 --time_based --group_reporting --directory /testfs
> 
> I'm not seeing this on my i7-13700K running tip sched/core (1a6151017ee5
> - sched: psi: pass enqueue/dequeue flags to psi callbacks directly
> (2024-10-26 Johannes Weiner)) (6.12.0-rc4 - based)
> 
> Using 'taskset 0xaaaaa' avoiding SMT and running only on P-cores.
> 
> vanilla features: 990MB/s (mean out of 5 runs, σ:  9.38)
> NO_DELAY_DEQUEUE: 992MB/s (mean out of 5 runs, σ: 10.61)
> 
> # sudo lshw -class disk -class storage
>   *-nvme                    
>        description: NVMe device
>        product: GIGABYTE GP-ASM2NE6500GTTD
>        vendor: Phison Electronics Corporation
>        physical id: 0
>        bus info: pci@0000:01:00.0
>        logical name: /dev/nvme0
>        version: EGFM13.2
>        ...
>        capabilities: nvme pciexpress msix msi pm nvm_express bus_master cap_list
>        configuration: driver=nvme latency=0 nqn=nqn.2014.08.org.nvmexpress:19871987SN215108954872 GIGABYTE GP-ASM2NE6500GTTD state=live
>        resources: irq:16 memory:70800000-70803fff
> 
> # mount | grep ^/dev/nvme0
> /dev/nvme0n1p2 on / type ext4 (rw,relatime,errors=remount-ro)
> 
> Which disk device you're using?

Most of the reports are on various NVME drives (samsung mostly I think).


One thing I should add is that it's all on LVM: 


vgcreate vg /dev/nvme0n1 -y
lvcreate -n thinMeta -L 3GB vg -y
lvcreate -n thinPool -l 99%FREE vg -y
lvconvert --thinpool /dev/mapper/vg-thinPool --poolmetadata /dev/mapper/vg-thinMeta -Zn -y
lvcreate -n testLV -V 1300G --thinpool thinPool vg
wipefs -a /dev/mapper/vg-testLV
mkfs.ext4 /dev/mapper/vg-testLV -E lazy_itable_init=0,lazy_journal_init=0 -F
mount /dev/mapper/vg-testLV /testfs 


With VDO or thinpool (as above) it shows on both ext4 and xfs. With fs on
drive directly it's a little more variable. Some it shows on xfs, some it show
on ext4 and not vice-versa, seems to depend on the drive or hw raid. But when
it shows it's 100% reproducible on that setup. 

It's always the randwrite numbers. The rest look fine.

Also, as yet I'm not personally doing this testing, just looking into it and
passing on the information I have. 


Thanks for taking a look. 

Cheers,
Phil

> 
> > 
> > In this case it's ext4, but I'm not sure it will be FS specific.
> > 
> > I should have the machine and setup next week to poke further but I wanted
> > to mention it now just in case any one has an "aha" moment.
> > 
> > It seems to only effect these FS loads. Other perf tests are not showing any
> > issues that I am aware of.
> 
> [...]
> 

-- 

Re: [PATCH 17/24] sched/fair: Implement delayed dequeue

[Dietmar Eggemann]

+cc Christian Loehle <christian.loehle@arm.com>

On 04/11/2024 10:28, Dietmar Eggemann wrote:
> Hi Phil,
> 
> On 01/11/2024 13:47, Phil Auld wrote:
>>
>> Hi Peterm
>>
>> On Sat, Jul 27, 2024 at 12:27:49PM +0200 Peter Zijlstra wrote:
>>> Extend / fix 86bfbb7ce4f6 ("sched/fair: Add lag based placement") by
>>> noting that lag is fundamentally a temporal measure. It should not be
>>> carried around indefinitely.
>>>
>>> OTOH it should also not be instantly discarded, doing so will allow a
>>> task to game the system by purposefully (micro) sleeping at the end of
>>> its time quantum.
>>>
>>> Since lag is intimately tied to the virtual time base, a wall-time
>>> based decay is also insufficient, notably competition is required for
>>> any of this to make sense.
>>>
>>> Instead, delay the dequeue and keep the 'tasks' on the runqueue,
>>> competing until they are eligible.
>>>
>>> Strictly speaking, we only care about keeping them until the 0-lag
>>> point, but that is a difficult proposition, instead carry them around
>>> until they get picked again, and dequeue them at that point.
>>
>> This one is causing a 10-20% performance hit on our filesystem tests.
>>
>> On 6.12-rc5 (so with the latest follow ons) we get:
>>
>> with DELAY_DEQUEUE the bandwidth is 510 MB/s
>> with NO_DELAY_DEQUEUE the bandwidth is 590 MB/s
>>
>> The test is fio, something like this:
>>
>> taskset -c 1,2,3,4,5,6,7,8 fio --rw randwrite --bs 4k --runtime 1m --fsync 0 --iodepth 32 --direct 1 --ioengine libaio --numjobs 8 --size 30g --nrfiles 1 --loops 1 --name default --randrepeat 1 --time_based --group_reporting --directory /testfs
> 
> I'm not seeing this on my i7-13700K running tip sched/core (1a6151017ee5
> - sched: psi: pass enqueue/dequeue flags to psi callbacks directly
> (2024-10-26 Johannes Weiner)) (6.12.0-rc4 - based)
> 
> Using 'taskset 0xaaaaa' avoiding SMT and running only on P-cores.
                 ^^^^^^^
> 
> vanilla features: 990MB/s (mean out of 5 runs, σ:  9.38)
> NO_DELAY_DEQUEUE: 992MB/s (mean out of 5 runs, σ: 10.61)

Christian Loehle just told me that my cpumask looks odd. Should be
0xaaaa instead.

Retested:

vanilla features: 954MB/s (mean out of 5 runs, σ: 30.83)
NO_DELAY_DEQUEUE: 932MB/s (mean out of 5 runs, σ: 28.10)

Now there are only 8 CPUs (instead of 10) for the 8 (+2) fio tasks. σ
went up probably because of more wakeup/preemption latency.

> 
> # sudo lshw -class disk -class storage
>   *-nvme                    
>        description: NVMe device
>        product: GIGABYTE GP-ASM2NE6500GTTD
>        vendor: Phison Electronics Corporation
>        physical id: 0
>        bus info: pci@0000:01:00.0
>        logical name: /dev/nvme0
>        version: EGFM13.2
>        ...
>        capabilities: nvme pciexpress msix msi pm nvm_express bus_master cap_list
>        configuration: driver=nvme latency=0 nqn=nqn.2014.08.org.nvmexpress:19871987SN215108954872 GIGABYTE GP-ASM2NE6500GTTD state=live
>        resources: irq:16 memory:70800000-70803fff
> 
> # mount | grep ^/dev/nvme0
> /dev/nvme0n1p2 on / type ext4 (rw,relatime,errors=remount-ro)
> 
> Which disk device you're using?
> 
>>
>> In this case it's ext4, but I'm not sure it will be FS specific.
>>
>> I should have the machine and setup next week to poke further but I wanted
>> to mention it now just in case any one has an "aha" moment.
>>
>> It seems to only effect these FS loads. Other perf tests are not showing any
>> issues that I am aware of.
> 
> [...]
> 
> 

Re: [PATCH 17/24] sched/fair: Implement delayed dequeue

[Dietmar Eggemann]

Hi Phil,

On 01/11/2024 13:47, Phil Auld wrote:
> 
> Hi Peterm
> 
> On Sat, Jul 27, 2024 at 12:27:49PM +0200 Peter Zijlstra wrote:
>> Extend / fix 86bfbb7ce4f6 ("sched/fair: Add lag based placement") by
>> noting that lag is fundamentally a temporal measure. It should not be
>> carried around indefinitely.
>>
>> OTOH it should also not be instantly discarded, doing so will allow a
>> task to game the system by purposefully (micro) sleeping at the end of
>> its time quantum.
>>
>> Since lag is intimately tied to the virtual time base, a wall-time
>> based decay is also insufficient, notably competition is required for
>> any of this to make sense.
>>
>> Instead, delay the dequeue and keep the 'tasks' on the runqueue,
>> competing until they are eligible.
>>
>> Strictly speaking, we only care about keeping them until the 0-lag
>> point, but that is a difficult proposition, instead carry them around
>> until they get picked again, and dequeue them at that point.
> 
> This one is causing a 10-20% performance hit on our filesystem tests.
> 
> On 6.12-rc5 (so with the latest follow ons) we get:
> 
> with DELAY_DEQUEUE the bandwidth is 510 MB/s
> with NO_DELAY_DEQUEUE the bandwidth is 590 MB/s
> 
> The test is fio, something like this:
> 
> taskset -c 1,2,3,4,5,6,7,8 fio --rw randwrite --bs 4k --runtime 1m --fsync 0 --iodepth 32 --direct 1 --ioengine libaio --numjobs 8 --size 30g --nrfiles 1 --loops 1 --name default --randrepeat 1 --time_based --group_reporting --directory /testfs

I'm not seeing this on my i7-13700K running tip sched/core (1a6151017ee5
- sched: psi: pass enqueue/dequeue flags to psi callbacks directly
(2024-10-26 Johannes Weiner)) (6.12.0-rc4 - based)

Using 'taskset 0xaaaaa' avoiding SMT and running only on P-cores.

vanilla features: 990MB/s (mean out of 5 runs, σ:  9.38)
NO_DELAY_DEQUEUE: 992MB/s (mean out of 5 runs, σ: 10.61)

# sudo lshw -class disk -class storage
  *-nvme                    
       description: NVMe device
       product: GIGABYTE GP-ASM2NE6500GTTD
       vendor: Phison Electronics Corporation
       physical id: 0
       bus info: pci@0000:01:00.0
       logical name: /dev/nvme0
       version: EGFM13.2
       ...
       capabilities: nvme pciexpress msix msi pm nvm_express bus_master cap_list
       configuration: driver=nvme latency=0 nqn=nqn.2014.08.org.nvmexpress:19871987SN215108954872 GIGABYTE GP-ASM2NE6500GTTD state=live
       resources: irq:16 memory:70800000-70803fff

# mount | grep ^/dev/nvme0
/dev/nvme0n1p2 on / type ext4 (rw,relatime,errors=remount-ro)

Which disk device you're using?

> 
> In this case it's ext4, but I'm not sure it will be FS specific.
> 
> I should have the machine and setup next week to poke further but I wanted
> to mention it now just in case any one has an "aha" moment.
> 
> It seems to only effect these FS loads. Other perf tests are not showing any
> issues that I am aware of.

[...]

Re: [PATCH 17/24] sched/fair: Implement delayed dequeue

[Mike Galbraith]

On Fri, 2024-11-01 at 16:07 -0400, Phil Auld wrote:


> Thanks for jumping in.  My jargon decoder ring seems to be failing me
> so I'm not completely sure what you are saying below :)
>
> "buddies" you mean tasks that waking each other up and sleeping.
> And one runs for longer than the other, right?

Yeah, buddies are related waker/wakee 1:1 1:N or M:N, excluding tasks
happening to be sitting on a CPU where, say a timer fires, an IRQ leads
to a wakeup of lord knows what, lock wakeups etc etc etc. I think Peter
coined the term buddy to mean that (less typing), and it stuck.

> > 1 tbench buddy pair scheduled cross core.
> >
> >   PID USER      PR  NI    VIRT    RES    SHR S  %CPU  %MEM     TIME+ P COMMAND
> > 13770 root      20   0   21424   1920   1792 S 60.13 0.012   0:33.81 3 tbench
> > 13771 root      20   0    4720    896    768 S 46.84 0.006   0:26.10 2 tbench_srv
>  
> > Note 60/47 utilization, now pinned/stacked.
> >
> > 6.1.114-cfs
> >   PID USER      PR  NI    VIRT    RES    SHR S  %CPU  %MEM     TIME+ P COMMAND
> >  4407 root      20   0   21424   1980   1772 R 50.00 0.012   0:29.20 3 tbench
> >  4408 root      20   0    4720    124      0 R 50.00 0.001   0:28.76 3 tbench_srv
>
> What is the difference between these first two?  The first is on
> separate cores so they don't interfere with each other? And the second is
> pinned to the same core?

Yeah, see 'P'. Given CPU headroom, a tbench pair can consume ~107%.
They're not fully synchronous.. wouldn't be relevant here/now if they
were :)

> > Note what happens to the lighter tbench_srv. Consuming red hot L2 data,
> > it can utilize a full 50%, but it must first preempt wide bottom buddy.
> >
>
> We've got "light" and "wide" here which is a bit mixed metaphorically
> :)

Wide, skinny, feather-weight or lard-ball, they all work for me.

> So here CFS is letting the wakee preempt the waker and providing pretty
> equal fairness. And hot l2 caching is masking the assymmetry.

No, it's way simpler: preemption slices through the only thing it can
slice through, the post wakeup concurrent bits.. that otherwise sits
directly in the communication stream as a lump of latency in a latency
bound operation.

>
> With wakeup preemption off it doesn't help in my case. I was thinking
> maybe the preemption was preventing some batching of IO completions
> or
> initiations. But that was wrong it seems.

Dunno.

> Does it also possibly make wakeup migration less likely and thus increase
> stacking?

The buddy being preempted certainly won't be wakeup migrated, because
it won't sleep. Two very sleepy tasks when bw constrained becomes one
100% hog and one 99.99% hog when CPU constrained.

> > Bottom line, box full of 1:1 buddies pairing up and stacking in L2.
> >
> > tbench 8
> > 6.1.114-cfs      3674.37 MB/sec
> > 6.1.114-eevdf    3505.25 MB/sec -delay_dequeue
> >                  3701.66 MB/sec +delay_dequeue
> >
> > For tbench, preemption = shorter turnaround = higher throughput.
>
> So here you have a benchmark that gets a ~5% boost from
> delayed_dequeue.
>
> But I've got one that get's a 20% penalty so I'm not exactly sure what
> to make of that. Clearly FIO does not have the same pattern as tbench.

There are basically two options in sched-land, shave fastpath cycles,
or some variant of Rob Peter to pay Paul ;-)

	-Mike

Re: [PATCH 17/24] sched/fair: Implement delayed dequeue

[Phil Auld]

Hi Mike,

On Fri, Nov 01, 2024 at 07:08:31PM +0100 Mike Galbraith wrote:
> On Fri, 2024-11-01 at 10:42 -0400, Phil Auld wrote:
> > On Fri, Nov 01, 2024 at 03:26:49PM +0100 Peter Zijlstra wrote:
> > > On Fri, Nov 01, 2024 at 09:38:22AM -0400, Phil Auld wrote:
> > >
> > > > How is delay dequeue causing more preemption?
> > >
> > > The thing delay dequeue does is it keeps !eligible tasks on the runqueue
> > > until they're picked again. Them getting picked means they're eligible.
> > > If at that point they're still not runnable, they're dequeued.
> > >
> > > By keeping them around like this, they can earn back their lag.
> > >
> > > The result is that the moment they get woken up again, they're going to
> > > be eligible and are considered for preemption.
> > >
> > >
> > > The whole thinking behind this is that while 'lag' measures the
> > > mount of service difference from the ideal (positive lag will have less
> > > service, while negative lag will have had too much service), this is
> > > only true for the (constantly) competing task.
> > >
> > > The moment a task leaves, will it still have had too much service? And
> > > after a few seconds of inactivity?
> > >
> > > So by keeping the deactivated tasks (artificially) in the competition
> > > until they're at least at the equal service point, lets them burn off
> > > some of that debt.
> > >
> > > It is not dissimilar to how CFS had sleeper bonus, except that was
> > > walltime based, while this is competition based.
> > >
> > >
> > > Notably, this makes a significant difference for interactive tasks that
> > > only run periodically. If they're not eligible at the point of wakeup,
> > > they'll incur undue latency.
> > >
> > >
> > > Now, I imagine FIO to have tasks blocking on IO, and while they're
> > > blocked, they'll be earning their eligibility, such that when they're
> > > woken they're good to go, preempting whatever.
> > >
> > > Whatever doesn't seem to enjoy this.
> > >
> > >
> > > Given BATCH makes such a terrible mess of things, I'm thinking FIO as a
> > > whole does like preemption -- so now it's a question of figuring out
> > > what exactly it does and doesn't like. Which is never trivial :/
> > >
> >
> > Thanks for that detailed explanation.
> >
> > I can confirm that FIO does like the preemption
> >
> > NO_WAKEUP_P and DELAY    - 427 MB/s
> > NO_WAKEUP_P and NO_DELAY - 498 MB/s
> > WAKEUP_P and DELAY       - 519 MB/s
> > WAKEUP_P and NO_DELAY    - 590 MB/s
> >
> > Something in the delay itself
> > (extra tasks in the queue? not migrating the delayed task? ...)
> 
> I think it's all about short term fairness and asymmetric buddies.

Thanks for jumping in.  My jargon decoder ring seems to be failing me
so I'm not completely sure what you are saying below :)

"buddies" you mean tasks that waking each other up and sleeping.
And one runs for longer than the other, right?

> 
> tbench comparison eevdf vs cfs, 100% apple to apple.
> 
> 1 tbench buddy pair scheduled cross core.
> 
>   PID USER      PR  NI    VIRT    RES    SHR S  %CPU  %MEM     TIME+ P COMMAND
> 13770 root      20   0   21424   1920   1792 S 60.13 0.012   0:33.81 3 tbench
> 13771 root      20   0    4720    896    768 S 46.84 0.006   0:26.10 2 tbench_srv
 
> Note 60/47 utilization, now pinned/stacked.
> 
> 6.1.114-cfs
>   PID USER      PR  NI    VIRT    RES    SHR S  %CPU  %MEM     TIME+ P COMMAND
>  4407 root      20   0   21424   1980   1772 R 50.00 0.012   0:29.20 3 tbench
>  4408 root      20   0    4720    124      0 R 50.00 0.001   0:28.76 3 tbench_srv

What is the difference between these first two?  The first is on
separate cores so they don't interfere with each other? And the second is
pinned to the same core?

>
> Note what happens to the lighter tbench_srv. Consuming red hot L2 data,
> it can utilize a full 50%, but it must first preempt wide bottom buddy.
>

We've got "light" and "wide" here which is a bit mixed metaphorically :) 
So here CFS is letting the wakee preempt the waker and providing pretty
equal fairness. And hot l2 caching is masking the assymmetry. 

> Now eevdf.  (zero source deltas other than eevdf)
> 6.1.114-eevdf -delay_dequeue
>   PID USER      PR  NI    VIRT    RES    SHR S  %CPU  %MEM     TIME+ P COMMAND
>  4988 root      20   0   21424   1948   1736 R 56.44 0.012   0:32.92 3 tbench
>  4989 root      20   0    4720    128      0 R 44.55 0.001   0:25.49 3 tbench_srv
> 6.1.114-eevdf +delay_dequeue
>   PID USER      PR  NI    VIRT    RES    SHR S  %CPU  %MEM     TIME+ P COMMAND
>  4934 root      20   0   21424   1952   1736 R 52.00 0.012   0:30.09 3 tbench
>  4935 root      20   0    4720    124      0 R 49.00 0.001   0:28.15 3 tbench_srv
> 
> As Peter noted, delay_dequeue levels the sleeper playing field.  Both
> of these guys are 1:1 sleepers, but they're asymmetric in width.

With wakeup preemption off it doesn't help in my case. I was thinking
maybe the preemption was preventing some batching of IO completions or
initiations. But that was wrong it seems. 

Does it also possibly make wakeup migration less likely and thus increase
stacking?  

> Bottom line, box full of 1:1 buddies pairing up and stacking in L2.
> 
> tbench 8
> 6.1.114-cfs      3674.37 MB/sec
> 6.1.114-eevdf    3505.25 MB/sec -delay_dequeue
>                  3701.66 MB/sec +delay_dequeue
> 
> For tbench, preemption = shorter turnaround = higher throughput.

So here you have a benchmark that gets a ~5% boost from delayed_dequeue.

But I've got one that get's a 20% penalty so I'm not exactly sure what
to make of that. Clearly FIO does not have the same pattern as tbench. 

It's not a special case though, this is one that our perf team runs
regularly to look for regressions. 

I'll be able to poke at it more next week so hopefully I can see what it's
doing. 


Cheers,
Phil


> 
> 	-Mike
> 

-- 

Re: [PATCH 17/24] sched/fair: Implement delayed dequeue

[Mike Galbraith]

On Fri, 2024-11-01 at 10:42 -0400, Phil Auld wrote:
> On Fri, Nov 01, 2024 at 03:26:49PM +0100 Peter Zijlstra wrote:
> > On Fri, Nov 01, 2024 at 09:38:22AM -0400, Phil Auld wrote:
> >
> > > How is delay dequeue causing more preemption?
> >
> > The thing delay dequeue does is it keeps !eligible tasks on the runqueue
> > until they're picked again. Them getting picked means they're eligible.
> > If at that point they're still not runnable, they're dequeued.
> >
> > By keeping them around like this, they can earn back their lag.
> >
> > The result is that the moment they get woken up again, they're going to
> > be eligible and are considered for preemption.
> >
> >
> > The whole thinking behind this is that while 'lag' measures the
> > mount of service difference from the ideal (positive lag will have less
> > service, while negative lag will have had too much service), this is
> > only true for the (constantly) competing task.
> >
> > The moment a task leaves, will it still have had too much service? And
> > after a few seconds of inactivity?
> >
> > So by keeping the deactivated tasks (artificially) in the competition
> > until they're at least at the equal service point, lets them burn off
> > some of that debt.
> >
> > It is not dissimilar to how CFS had sleeper bonus, except that was
> > walltime based, while this is competition based.
> >
> >
> > Notably, this makes a significant difference for interactive tasks that
> > only run periodically. If they're not eligible at the point of wakeup,
> > they'll incur undue latency.
> >
> >
> > Now, I imagine FIO to have tasks blocking on IO, and while they're
> > blocked, they'll be earning their eligibility, such that when they're
> > woken they're good to go, preempting whatever.
> >
> > Whatever doesn't seem to enjoy this.
> >
> >
> > Given BATCH makes such a terrible mess of things, I'm thinking FIO as a
> > whole does like preemption -- so now it's a question of figuring out
> > what exactly it does and doesn't like. Which is never trivial :/
> >
>
> Thanks for that detailed explanation.
>
> I can confirm that FIO does like the preemption
>
> NO_WAKEUP_P and DELAY    - 427 MB/s
> NO_WAKEUP_P and NO_DELAY - 498 MB/s
> WAKEUP_P and DELAY       - 519 MB/s
> WAKEUP_P and NO_DELAY    - 590 MB/s
>
> Something in the delay itself
> (extra tasks in the queue? not migrating the delayed task? ...)

I think it's all about short term fairness and asymmetric buddies.

tbench comparison eevdf vs cfs, 100% apple to apple.

1 tbench buddy pair scheduled cross core.

  PID USER      PR  NI    VIRT    RES    SHR S  %CPU  %MEM     TIME+ P COMMAND
13770 root      20   0   21424   1920   1792 S 60.13 0.012   0:33.81 3 tbench
13771 root      20   0    4720    896    768 S 46.84 0.006   0:26.10 2 tbench_srv

Note 60/47 utilization, now pinned/stacked.

6.1.114-cfs
  PID USER      PR  NI    VIRT    RES    SHR S  %CPU  %MEM     TIME+ P COMMAND
 4407 root      20   0   21424   1980   1772 R 50.00 0.012   0:29.20 3 tbench
 4408 root      20   0    4720    124      0 R 50.00 0.001   0:28.76 3 tbench_srv

Note what happens to the lighter tbench_srv. Consuming red hot L2 data,
it can utilize a full 50%, but it must first preempt wide bottom buddy.

Now eevdf.  (zero source deltas other than eevdf)
6.1.114-eevdf -delay_dequeue
  PID USER      PR  NI    VIRT    RES    SHR S  %CPU  %MEM     TIME+ P COMMAND
 4988 root      20   0   21424   1948   1736 R 56.44 0.012   0:32.92 3 tbench
 4989 root      20   0    4720    128      0 R 44.55 0.001   0:25.49 3 tbench_srv
6.1.114-eevdf +delay_dequeue
  PID USER      PR  NI    VIRT    RES    SHR S  %CPU  %MEM     TIME+ P COMMAND
 4934 root      20   0   21424   1952   1736 R 52.00 0.012   0:30.09 3 tbench
 4935 root      20   0    4720    124      0 R 49.00 0.001   0:28.15 3 tbench_srv

As Peter noted, delay_dequeue levels the sleeper playing field.  Both
of these guys are 1:1 sleepers, but they're asymmetric in width.

Bottom line, box full of 1:1 buddies pairing up and stacking in L2.

tbench 8
6.1.114-cfs      3674.37 MB/sec
6.1.114-eevdf    3505.25 MB/sec -delay_dequeue
                 3701.66 MB/sec +delay_dequeue

For tbench, preemption = shorter turnaround = higher throughput.

	-Mike

Re: [PATCH 17/24] sched/fair: Implement delayed dequeue

[Phil Auld]

On Fri, Nov 01, 2024 at 03:26:49PM +0100 Peter Zijlstra wrote:
> On Fri, Nov 01, 2024 at 09:38:22AM -0400, Phil Auld wrote:
> 
> > How is delay dequeue causing more preemption? 
> 
> The thing delay dequeue does is it keeps !eligible tasks on the runqueue
> until they're picked again. Them getting picked means they're eligible.
> If at that point they're still not runnable, they're dequeued.
> 
> By keeping them around like this, they can earn back their lag.
> 
> The result is that the moment they get woken up again, they're going to
> be eligible and are considered for preemption.
> 
> 
> The whole thinking behind this is that while 'lag' measures the
> mount of service difference from the ideal (positive lag will have less
> service, while negative lag will have had too much service), this is
> only true for the (constantly) competing task.
> 
> The moment a task leaves, will it still have had too much service? And
> after a few seconds of inactivity?
> 
> So by keeping the deactivated tasks (artificially) in the competition
> until they're at least at the equal service point, lets them burn off
> some of that debt.
> 
> It is not dissimilar to how CFS had sleeper bonus, except that was
> walltime based, while this is competition based.
> 
> 
> Notably, this makes a significant difference for interactive tasks that
> only run periodically. If they're not eligible at the point of wakeup,
> they'll incur undue latency.
> 
> 
> Now, I imagine FIO to have tasks blocking on IO, and while they're
> blocked, they'll be earning their eligibility, such that when they're
> woken they're good to go, preempting whatever.
> 
> Whatever doesn't seem to enjoy this.
> 
> 
> Given BATCH makes such a terrible mess of things, I'm thinking FIO as a
> whole does like preemption -- so now it's a question of figuring out
> what exactly it does and doesn't like. Which is never trivial :/
> 

Thanks for that detailed explanation.

I can confirm that FIO does like the preemption

NO_WAKEUP_P and DELAY    - 427 MB/s
NO_WAKEUP_P and NO_DELAY - 498 MB/s
WAKEUP_P and DELAY       - 519 MB/s
WAKEUP_P and NO_DELAY    - 590 MB/s

Something in the delay itself
(extra tasks in the queue? not migrating the delayed task? ...) 

I'll start looking at tracing next week.


Thanks,
Phil


-- 

Re: [PATCH 17/24] sched/fair: Implement delayed dequeue

[Peter Zijlstra]

On Fri, Nov 01, 2024 at 09:38:22AM -0400, Phil Auld wrote:

> How is delay dequeue causing more preemption? 

The thing delay dequeue does is it keeps !eligible tasks on the runqueue
until they're picked again. Them getting picked means they're eligible.
If at that point they're still not runnable, they're dequeued.

By keeping them around like this, they can earn back their lag.

The result is that the moment they get woken up again, they're going to
be eligible and are considered for preemption.


The whole thinking behind this is that while 'lag' measures the
mount of service difference from the ideal (positive lag will have less
service, while negative lag will have had too much service), this is
only true for the (constantly) competing task.

The moment a task leaves, will it still have had too much service? And
after a few seconds of inactivity?

So by keeping the deactivated tasks (artificially) in the competition
until they're at least at the equal service point, lets them burn off
some of that debt.

It is not dissimilar to how CFS had sleeper bonus, except that was
walltime based, while this is competition based.


Notably, this makes a significant difference for interactive tasks that
only run periodically. If they're not eligible at the point of wakeup,
they'll incur undue latency.


Now, I imagine FIO to have tasks blocking on IO, and while they're
blocked, they'll be earning their eligibility, such that when they're
woken they're good to go, preempting whatever.

Whatever doesn't seem to enjoy this.


Given BATCH makes such a terrible mess of things, I'm thinking FIO as a
whole does like preemption -- so now it's a question of figuring out
what exactly it does and doesn't like. Which is never trivial :/

Re: [PATCH 17/24] sched/fair: Implement delayed dequeue

[Phil Auld]

On Fri, Nov 01, 2024 at 01:56:59PM +0100 Peter Zijlstra wrote:
> On Fri, Nov 01, 2024 at 08:47:15AM -0400, Phil Auld wrote:
> 
> > This one is causing a 10-20% performance hit on our filesystem tests.
> > 
> > On 6.12-rc5 (so with the latest follow ons) we get:
> > 
> > with DELAY_DEQUEUE the bandwidth is 510 MB/s
> > with NO_DELAY_DEQUEUE the bandwidth is 590 MB/s
> > 
> > The test is fio, something like this:
> > 
> > taskset -c 1,2,3,4,5,6,7,8 fio --rw randwrite --bs 4k --runtime 1m --fsync 0 --iodepth 32 --direct 1 --ioengine libaio --numjobs 8 --size 30g --nrfiles 1 --loops 1 --name default --randrepeat 1 --time_based --group_reporting --directory /testfs
> > 
> > In this case it's ext4, but I'm not sure it will be FS specific.
> > 
> > I should have the machine and setup next week to poke further but I wanted
> > to mention it now just in case any one has an "aha" moment.
> > 
> > It seems to only effect these FS loads. Other perf tests are not showing any
> > issues that I am aware of.
> 
> There's a number of reports -- mostly it seems to be a case of excessive
> preemption hurting things.
> 
> What happens if you use:
> 
>   schedtool -B -a 1-8 -e fio ....
> 
>

Thanks for taking a look. 

That makes the overall performance way worse:

DELAY_DEQUEUE - 146 MB/s
NO_DELAY_DEQUEUE - 156 MB/s

I guess that does make the difference between delay and nodelay
about half. 

How is delay dequeue causing more preemption? Or is that more
for eevdf in general?  We aren't seeing any issues there except
for the delay dequeue thing.



Cheers,
Phil

-- 

Re: [PATCH 17/24] sched/fair: Implement delayed dequeue

[Peter Zijlstra]

On Fri, Nov 01, 2024 at 08:47:15AM -0400, Phil Auld wrote:

> This one is causing a 10-20% performance hit on our filesystem tests.
> 
> On 6.12-rc5 (so with the latest follow ons) we get:
> 
> with DELAY_DEQUEUE the bandwidth is 510 MB/s
> with NO_DELAY_DEQUEUE the bandwidth is 590 MB/s
> 
> The test is fio, something like this:
> 
> taskset -c 1,2,3,4,5,6,7,8 fio --rw randwrite --bs 4k --runtime 1m --fsync 0 --iodepth 32 --direct 1 --ioengine libaio --numjobs 8 --size 30g --nrfiles 1 --loops 1 --name default --randrepeat 1 --time_based --group_reporting --directory /testfs
> 
> In this case it's ext4, but I'm not sure it will be FS specific.
> 
> I should have the machine and setup next week to poke further but I wanted
> to mention it now just in case any one has an "aha" moment.
> 
> It seems to only effect these FS loads. Other perf tests are not showing any
> issues that I am aware of.

There's a number of reports -- mostly it seems to be a case of excessive
preemption hurting things.

What happens if you use:

  schedtool -B -a 1-8 -e fio ....

Re: [PATCH 17/24] sched/fair: Implement delayed dequeue

[Phil Auld]

Hi Peterm

On Sat, Jul 27, 2024 at 12:27:49PM +0200 Peter Zijlstra wrote:
> Extend / fix 86bfbb7ce4f6 ("sched/fair: Add lag based placement") by
> noting that lag is fundamentally a temporal measure. It should not be
> carried around indefinitely.
> 
> OTOH it should also not be instantly discarded, doing so will allow a
> task to game the system by purposefully (micro) sleeping at the end of
> its time quantum.
> 
> Since lag is intimately tied to the virtual time base, a wall-time
> based decay is also insufficient, notably competition is required for
> any of this to make sense.
> 
> Instead, delay the dequeue and keep the 'tasks' on the runqueue,
> competing until they are eligible.
> 
> Strictly speaking, we only care about keeping them until the 0-lag
> point, but that is a difficult proposition, instead carry them around
> until they get picked again, and dequeue them at that point.

This one is causing a 10-20% performance hit on our filesystem tests.

On 6.12-rc5 (so with the latest follow ons) we get:

with DELAY_DEQUEUE the bandwidth is 510 MB/s
with NO_DELAY_DEQUEUE the bandwidth is 590 MB/s

The test is fio, something like this:

taskset -c 1,2,3,4,5,6,7,8 fio --rw randwrite --bs 4k --runtime 1m --fsync 0 --iodepth 32 --direct 1 --ioengine libaio --numjobs 8 --size 30g --nrfiles 1 --loops 1 --name default --randrepeat 1 --time_based --group_reporting --directory /testfs

In this case it's ext4, but I'm not sure it will be FS specific.

I should have the machine and setup next week to poke further but I wanted
to mention it now just in case any one has an "aha" moment.

It seems to only effect these FS loads. Other perf tests are not showing any
issues that I am aware of.



Thanks,
Phil



> 
> Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
> ---
>  kernel/sched/deadline.c |    1 
>  kernel/sched/fair.c     |   82 ++++++++++++++++++++++++++++++++++++++++++------
>  kernel/sched/features.h |    9 +++++
>  3 files changed, 81 insertions(+), 11 deletions(-)
> 
> --- a/kernel/sched/deadline.c
> +++ b/kernel/sched/deadline.c
> @@ -2428,7 +2428,6 @@ static struct task_struct *__pick_next_t
>  		else
>  			p = dl_se->server_pick_next(dl_se);
>  		if (!p) {
> -			WARN_ON_ONCE(1);
>  			dl_se->dl_yielded = 1;
>  			update_curr_dl_se(rq, dl_se, 0);
>  			goto again;
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -5379,20 +5379,44 @@ static void clear_buddies(struct cfs_rq
>  
>  static __always_inline void return_cfs_rq_runtime(struct cfs_rq *cfs_rq);
>  
> -static void
> +static bool
>  dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
>  {
> -	int action = UPDATE_TG;
> +	if (flags & DEQUEUE_DELAYED) {
> +		/*
> +		 * DEQUEUE_DELAYED is typically called from pick_next_entity()
> +		 * at which point we've already done update_curr() and do not
> +		 * want to do so again.
> +		 */
> +		SCHED_WARN_ON(!se->sched_delayed);
> +		se->sched_delayed = 0;
> +	} else {
> +		bool sleep = flags & DEQUEUE_SLEEP;
> +
> +		/*
> +		 * DELAY_DEQUEUE relies on spurious wakeups, special task
> +		 * states must not suffer spurious wakeups, excempt them.
> +		 */
> +		if (flags & DEQUEUE_SPECIAL)
> +			sleep = false;
> +
> +		SCHED_WARN_ON(sleep && se->sched_delayed);
> +		update_curr(cfs_rq);
>  
> +		if (sched_feat(DELAY_DEQUEUE) && sleep &&
> +		    !entity_eligible(cfs_rq, se)) {
> +			if (cfs_rq->next == se)
> +				cfs_rq->next = NULL;
> +			se->sched_delayed = 1;
> +			return false;
> +		}
> +	}
> +
> +	int action = UPDATE_TG;
>  	if (entity_is_task(se) && task_on_rq_migrating(task_of(se)))
>  		action |= DO_DETACH;
>  
>  	/*
> -	 * Update run-time statistics of the 'current'.
> -	 */
> -	update_curr(cfs_rq);
> -
> -	/*
>  	 * When dequeuing a sched_entity, we must:
>  	 *   - Update loads to have both entity and cfs_rq synced with now.
>  	 *   - For group_entity, update its runnable_weight to reflect the new
> @@ -5430,6 +5454,8 @@ dequeue_entity(struct cfs_rq *cfs_rq, st
>  
>  	if (cfs_rq->nr_running == 0)
>  		update_idle_cfs_rq_clock_pelt(cfs_rq);
> +
> +	return true;
>  }
>  
>  static void
> @@ -5828,11 +5854,21 @@ static bool throttle_cfs_rq(struct cfs_r
>  	idle_task_delta = cfs_rq->idle_h_nr_running;
>  	for_each_sched_entity(se) {
>  		struct cfs_rq *qcfs_rq = cfs_rq_of(se);
> +		int flags;
> +
>  		/* throttled entity or throttle-on-deactivate */
>  		if (!se->on_rq)
>  			goto done;
>  
> -		dequeue_entity(qcfs_rq, se, DEQUEUE_SLEEP);
> +		/*
> +		 * Abuse SPECIAL to avoid delayed dequeue in this instance.
> +		 * This avoids teaching dequeue_entities() about throttled
> +		 * entities and keeps things relatively simple.
> +		 */
> +		flags = DEQUEUE_SLEEP | DEQUEUE_SPECIAL;
> +		if (se->sched_delayed)
> +			flags |= DEQUEUE_DELAYED;
> +		dequeue_entity(qcfs_rq, se, flags);
>  
>  		if (cfs_rq_is_idle(group_cfs_rq(se)))
>  			idle_task_delta = cfs_rq->h_nr_running;
> @@ -6918,6 +6954,7 @@ static int dequeue_entities(struct rq *r
>  	bool was_sched_idle = sched_idle_rq(rq);
>  	int rq_h_nr_running = rq->cfs.h_nr_running;
>  	bool task_sleep = flags & DEQUEUE_SLEEP;
> +	bool task_delayed = flags & DEQUEUE_DELAYED;
>  	struct task_struct *p = NULL;
>  	int idle_h_nr_running = 0;
>  	int h_nr_running = 0;
> @@ -6931,7 +6968,13 @@ static int dequeue_entities(struct rq *r
>  
>  	for_each_sched_entity(se) {
>  		cfs_rq = cfs_rq_of(se);
> -		dequeue_entity(cfs_rq, se, flags);
> +
> +		if (!dequeue_entity(cfs_rq, se, flags)) {
> +			if (p && &p->se == se)
> +				return -1;
> +
> +			break;
> +		}
>  
>  		cfs_rq->h_nr_running -= h_nr_running;
>  		cfs_rq->idle_h_nr_running -= idle_h_nr_running;
> @@ -6956,6 +6999,7 @@ static int dequeue_entities(struct rq *r
>  			break;
>  		}
>  		flags |= DEQUEUE_SLEEP;
> +		flags &= ~(DEQUEUE_DELAYED | DEQUEUE_SPECIAL);
>  	}
>  
>  	for_each_sched_entity(se) {
> @@ -6985,6 +7029,17 @@ static int dequeue_entities(struct rq *r
>  	if (unlikely(!was_sched_idle && sched_idle_rq(rq)))
>  		rq->next_balance = jiffies;
>  
> +	if (p && task_delayed) {
> +		SCHED_WARN_ON(!task_sleep);
> +		SCHED_WARN_ON(p->on_rq != 1);
> +
> +		/* Fix-up what dequeue_task_fair() skipped */
> +		hrtick_update(rq);
> +
> +		/* Fix-up what block_task() skipped. */
> +		__block_task(rq, p);
> +	}
> +
>  	return 1;
>  }
>  /*
> @@ -6996,8 +7051,10 @@ static bool dequeue_task_fair(struct rq
>  {
>  	util_est_dequeue(&rq->cfs, p);
>  
> -	if (dequeue_entities(rq, &p->se, flags) < 0)
> +	if (dequeue_entities(rq, &p->se, flags) < 0) {
> +		util_est_update(&rq->cfs, p, DEQUEUE_SLEEP);
>  		return false;
> +	}
>  
>  	util_est_update(&rq->cfs, p, flags & DEQUEUE_SLEEP);
>  	hrtick_update(rq);
> @@ -12973,6 +13030,11 @@ static void set_next_task_fair(struct rq
>  		/* ensure bandwidth has been allocated on our new cfs_rq */
>  		account_cfs_rq_runtime(cfs_rq, 0);
>  	}
> +
> +	if (!first)
> +		return;
> +
> +	SCHED_WARN_ON(se->sched_delayed);
>  }
>  
>  void init_cfs_rq(struct cfs_rq *cfs_rq)
> --- a/kernel/sched/features.h
> +++ b/kernel/sched/features.h
> @@ -29,6 +29,15 @@ SCHED_FEAT(NEXT_BUDDY, false)
>  SCHED_FEAT(CACHE_HOT_BUDDY, true)
>  
>  /*
> + * Delay dequeueing tasks until they get selected or woken.
> + *
> + * By delaying the dequeue for non-eligible tasks, they remain in the
> + * competition and can burn off their negative lag. When they get selected
> + * they'll have positive lag by definition.
> + */
> +SCHED_FEAT(DELAY_DEQUEUE, true)
> +
> +/*
>   * Allow wakeup-time preemption of the current task:
>   */
>  SCHED_FEAT(WAKEUP_PREEMPTION, true)
> 
> 

-- 

Re: [PATCH 17/24] sched/fair: Implement delayed dequeue

[Sean Christopherson]

On Thu, Oct 10, 2024, Peter Zijlstra wrote:
> On Thu, Oct 10, 2024 at 10:19:40AM +0200, Peter Zijlstra wrote:
> > On Wed, Oct 09, 2024 at 07:49:54PM -0700, Sean Christopherson wrote:
> > 
> > > TL;DR: Code that checks task_struct.on_rq may be broken by this commit.
> > 
> > Correct, and while I did look at quite a few, I did miss KVM used it,
> > damn.
> > 
> > > Peter,
> > > 
> > > Any thoughts on how best to handle this?  The below hack-a-fix resolves the issue,
> > > but it's obviously not appropriate.  KVM uses vcpu->preempted for more than just
> > > posted interrupts, so KVM needs equivalent functionality to current->on-rq as it
> > > was before this commit.
> > > 
> > > @@ -6387,7 +6390,7 @@ static void kvm_sched_out(struct preempt_notifier *pn,
> > >  
> > >         WRITE_ONCE(vcpu->scheduled_out, true);
> > >  
> > > -       if (current->on_rq && vcpu->wants_to_run) {
> > > +       if (se_runnable(&current->se) && vcpu->wants_to_run) {
> > >                 WRITE_ONCE(vcpu->preempted, true);
> > >                 WRITE_ONCE(vcpu->ready, true);
> > >         }
> > 
> > se_runnable() isn't quite right, but yes, a helper along those lines is
> > probably best. Let me try and grep more to see if there's others I
> > missed as well :/
> 
> How's the below? I remember looking at the freezer thing before and
> deciding it isn't a correctness thing, but given I added the helper, I
> changed it anyway. I've added a bunch of comments and the perf thing is
> similar to KVM, it wants to know about preemptions so that had to change
> too.

Fixes KVM's woes!  Thanks!

Re: [PATCH 17/24] sched/fair: Implement delayed dequeue

[Mike Galbraith]

On Thu, 2024-10-10 at 09:18 -0700, Sean Christopherson wrote:
> On Thu, Oct 10, 2024, Mike Galbraith wrote:
> > On Wed, 2024-10-09 at 19:49 -0700, Sean Christopherson wrote:
> > >
> > > Any thoughts on how best to handle this?  The below hack-a-fix resolves the issue,
> > > but it's obviously not appropriate.  KVM uses vcpu->preempted for more than just
> > > posted interrupts, so KVM needs equivalent functionality to current->on-rq as it
> > > was before this commit.
> > >
> > > @@ -6387,7 +6390,7 @@ static void kvm_sched_out(struct preempt_notifier *pn,
> > >  
> > >         WRITE_ONCE(vcpu->scheduled_out, true);
> > >  
> > > -       if (current->on_rq && vcpu->wants_to_run) {
> > > +       if (se_runnable(&current->se) && vcpu->wants_to_run) {
> > >                 WRITE_ONCE(vcpu->preempted, true);
> > >                 WRITE_ONCE(vcpu->ready, true);
> > >         }
> >
> > Why is that deemed "obviously not appropriate"?  ->on_rq in and of
> > itself meaning only "on rq" doesn't seem like a bad thing.
>
> Doh, my wording was unclear.  I didn't mean the logic was inappropriate, I meant
> that KVM shouldn't be poking into an internal sched/ helper.

Ah, confusion all better.  (yeah, swiping other's toys is naughty)

	-Mike

Re: [PATCH 17/24] sched/fair: Implement delayed dequeue

[Sean Christopherson]

On Thu, Oct 10, 2024, Mike Galbraith wrote:
> On Wed, 2024-10-09 at 19:49 -0700, Sean Christopherson wrote:
> >
> > Any thoughts on how best to handle this?  The below hack-a-fix resolves the issue,
> > but it's obviously not appropriate.  KVM uses vcpu->preempted for more than just
> > posted interrupts, so KVM needs equivalent functionality to current->on-rq as it
> > was before this commit.
> >
> > @@ -6387,7 +6390,7 @@ static void kvm_sched_out(struct preempt_notifier *pn,
> >  
> >         WRITE_ONCE(vcpu->scheduled_out, true);
> >  
> > -       if (current->on_rq && vcpu->wants_to_run) {
> > +       if (se_runnable(&current->se) && vcpu->wants_to_run) {
> >                 WRITE_ONCE(vcpu->preempted, true);
> >                 WRITE_ONCE(vcpu->ready, true);
> >         }
> 
> Why is that deemed "obviously not appropriate"?  ->on_rq in and of
> itself meaning only "on rq" doesn't seem like a bad thing.

Doh, my wording was unclear.  I didn't mean the logic was inappropriate, I meant
that KVM shouldn't be poking into an internal sched/ helper.

Re: [PATCH 17/24] sched/fair: Implement delayed dequeue

[Peter Zijlstra]

On Thu, Oct 10, 2024 at 10:19:40AM +0200, Peter Zijlstra wrote:
> On Wed, Oct 09, 2024 at 07:49:54PM -0700, Sean Christopherson wrote:
> 
> > TL;DR: Code that checks task_struct.on_rq may be broken by this commit.
> 
> Correct, and while I did look at quite a few, I did miss KVM used it,
> damn.
> 
> > Peter,
> > 
> > Any thoughts on how best to handle this?  The below hack-a-fix resolves the issue,
> > but it's obviously not appropriate.  KVM uses vcpu->preempted for more than just
> > posted interrupts, so KVM needs equivalent functionality to current->on-rq as it
> > was before this commit.
> > 
> > @@ -6387,7 +6390,7 @@ static void kvm_sched_out(struct preempt_notifier *pn,
> >  
> >         WRITE_ONCE(vcpu->scheduled_out, true);
> >  
> > -       if (current->on_rq && vcpu->wants_to_run) {
> > +       if (se_runnable(&current->se) && vcpu->wants_to_run) {
> >                 WRITE_ONCE(vcpu->preempted, true);
> >                 WRITE_ONCE(vcpu->ready, true);
> >         }
> 
> se_runnable() isn't quite right, but yes, a helper along those lines is
> probably best. Let me try and grep more to see if there's others I
> missed as well :/

How's the below? I remember looking at the freezer thing before and
deciding it isn't a correctness thing, but given I added the helper, I
changed it anyway. I've added a bunch of comments and the perf thing is
similar to KVM, it wants to know about preemptions so that had to change
too.

---
 include/linux/sched.h         |  5 +++++
 kernel/events/core.c          |  2 +-
 kernel/freezer.c              |  7 ++++++-
 kernel/rcu/tasks.h            |  9 +++++++++
 kernel/sched/core.c           | 12 +++++++++---
 kernel/time/tick-sched.c      |  5 +++++
 kernel/trace/trace_selftest.c |  2 +-
 virt/kvm/kvm_main.c           |  2 +-
 8 files changed, 37 insertions(+), 7 deletions(-)

diff --git a/include/linux/sched.h b/include/linux/sched.h
index 0053f0664847..2b1f454e4575 100644
--- a/include/linux/sched.h
+++ b/include/linux/sched.h
@@ -2134,6 +2134,11 @@ static inline void set_task_cpu(struct task_struct *p, unsigned int cpu)
 
 #endif /* CONFIG_SMP */
 
+static inline bool task_is_runnable(struct task_struct *p)
+{
+	return p->on_rq && !p->se.sched_delayed;
+}
+
 extern bool sched_task_on_rq(struct task_struct *p);
 extern unsigned long get_wchan(struct task_struct *p);
 extern struct task_struct *cpu_curr_snapshot(int cpu);
diff --git a/kernel/events/core.c b/kernel/events/core.c
index e3589c4287cb..cdd09769e6c5 100644
--- a/kernel/events/core.c
+++ b/kernel/events/core.c
@@ -9251,7 +9251,7 @@ static void perf_event_switch(struct task_struct *task,
 		},
 	};
 
-	if (!sched_in && task->on_rq) {
+	if (!sched_in && task_is_runnable(task)) {
 		switch_event.event_id.header.misc |=
 				PERF_RECORD_MISC_SWITCH_OUT_PREEMPT;
 	}
diff --git a/kernel/freezer.c b/kernel/freezer.c
index 44bbd7dbd2c8..8d530d0949ff 100644
--- a/kernel/freezer.c
+++ b/kernel/freezer.c
@@ -109,7 +109,12 @@ static int __set_task_frozen(struct task_struct *p, void *arg)
 {
 	unsigned int state = READ_ONCE(p->__state);
 
-	if (p->on_rq)
+	/*
+	 * Allow freezing the sched_delayed tasks; they will not execute until
+	 * ttwu() fixes them up, so it is safe to swap their state now, instead
+	 * of waiting for them to get fully dequeued.
+	 */
+	if (task_is_runnable(p))
 		return 0;
 
 	if (p != current && task_curr(p))
diff --git a/kernel/rcu/tasks.h b/kernel/rcu/tasks.h
index 6333f4ccf024..4d7ee95df06e 100644
--- a/kernel/rcu/tasks.h
+++ b/kernel/rcu/tasks.h
@@ -985,6 +985,15 @@ static bool rcu_tasks_is_holdout(struct task_struct *t)
 	if (!READ_ONCE(t->on_rq))
 		return false;
 
+	/*
+	 * t->on_rq && !t->se.sched_delayed *could* be considered sleeping but
+	 * since it is a spurious state (it will transition into the
+	 * traditional blocked state or get woken up without outside
+	 * dependencies), not considering it such should only affect timing.
+	 *
+	 * Be conservative for now and not include it.
+	 */
+
 	/*
 	 * Idle tasks (or idle injection) within the idle loop are RCU-tasks
 	 * quiescent states. But CPU boot code performed by the idle task
diff --git a/kernel/sched/core.c b/kernel/sched/core.c
index 0bacc5cd3693..be5c04eb5ba0 100644
--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -548,6 +548,11 @@ sched_core_dequeue(struct rq *rq, struct task_struct *p, int flags) { }
  *   ON_RQ_MIGRATING state is used for migration without holding both
  *   rq->locks. It indicates task_cpu() is not stable, see task_rq_lock().
  *
+ *   Additionally it is possible to be ->on_rq but still be considered not
+ *   runnable when p->se.sched_delayed is true. These tasks are on the runqueue
+ *   but will be dequeued as soon as they get picked again. See the
+ *   task_is_runnable() helper.
+ *
  * p->on_cpu <- { 0, 1 }:
  *
  *   is set by prepare_task() and cleared by finish_task() such that it will be
@@ -4358,9 +4363,10 @@ static bool __task_needs_rq_lock(struct task_struct *p)
  * @arg: Argument to function.
  *
  * Fix the task in it's current state by avoiding wakeups and or rq operations
- * and call @func(@arg) on it.  This function can use ->on_rq and task_curr()
- * to work out what the state is, if required.  Given that @func can be invoked
- * with a runqueue lock held, it had better be quite lightweight.
+ * and call @func(@arg) on it.  This function can use task_is_runnable() and
+ * task_curr() to work out what the state is, if required.  Given that @func
+ * can be invoked with a runqueue lock held, it had better be quite
+ * lightweight.
  *
  * Returns:
  *   Whatever @func returns
diff --git a/kernel/time/tick-sched.c b/kernel/time/tick-sched.c
index 753a184c7090..59efa14ce185 100644
--- a/kernel/time/tick-sched.c
+++ b/kernel/time/tick-sched.c
@@ -435,6 +435,11 @@ static void tick_nohz_kick_task(struct task_struct *tsk)
 	 *   tick_nohz_task_switch()
 	 *     LOAD p->tick_dep_mask
 	 */
+	// XXX given a task picks up the dependency on schedule(), should we
+	// only care about tasks that are currently on the CPU instead of all
+	// that are on the runqueue?
+	//
+	// That is, does this want to be: task_on_cpu() / task_curr()?
 	if (!sched_task_on_rq(tsk))
 		return;
 
diff --git a/kernel/trace/trace_selftest.c b/kernel/trace/trace_selftest.c
index c4ad7cd7e778..1469dd8075fa 100644
--- a/kernel/trace/trace_selftest.c
+++ b/kernel/trace/trace_selftest.c
@@ -1485,7 +1485,7 @@ trace_selftest_startup_wakeup(struct tracer *trace, struct trace_array *tr)
 	/* reset the max latency */
 	tr->max_latency = 0;
 
-	while (p->on_rq) {
+	while (task_is_runnable(p)) {
 		/*
 		 * Sleep to make sure the -deadline thread is asleep too.
 		 * On virtual machines we can't rely on timings,
diff --git a/virt/kvm/kvm_main.c b/virt/kvm/kvm_main.c
index 05cbb2548d99..0c666f1870af 100644
--- a/virt/kvm/kvm_main.c
+++ b/virt/kvm/kvm_main.c
@@ -6387,7 +6387,7 @@ static void kvm_sched_out(struct preempt_notifier *pn,
 
 	WRITE_ONCE(vcpu->scheduled_out, true);
 
-	if (current->on_rq && vcpu->wants_to_run) {
+	if (task_is_runnable(current) && vcpu->wants_to_run) {
 		WRITE_ONCE(vcpu->preempted, true);
 		WRITE_ONCE(vcpu->ready, true);
 	}

Re: [PATCH 17/24] sched/fair: Implement delayed dequeue

[Peter Zijlstra]

On Wed, Oct 09, 2024 at 07:49:54PM -0700, Sean Christopherson wrote:

> TL;DR: Code that checks task_struct.on_rq may be broken by this commit.

Correct, and while I did look at quite a few, I did miss KVM used it,
damn.

> Peter,
> 
> Any thoughts on how best to handle this?  The below hack-a-fix resolves the issue,
> but it's obviously not appropriate.  KVM uses vcpu->preempted for more than just
> posted interrupts, so KVM needs equivalent functionality to current->on-rq as it
> was before this commit.
> 
> @@ -6387,7 +6390,7 @@ static void kvm_sched_out(struct preempt_notifier *pn,
>  
>         WRITE_ONCE(vcpu->scheduled_out, true);
>  
> -       if (current->on_rq && vcpu->wants_to_run) {
> +       if (se_runnable(&current->se) && vcpu->wants_to_run) {
>                 WRITE_ONCE(vcpu->preempted, true);
>                 WRITE_ONCE(vcpu->ready, true);
>         }

se_runnable() isn't quite right, but yes, a helper along those lines is
probably best. Let me try and grep more to see if there's others I
missed as well :/

Re: [PATCH 17/24] sched/fair: Implement delayed dequeue

[Mike Galbraith]

On Wed, 2024-10-09 at 19:49 -0700, Sean Christopherson wrote:
>
> Any thoughts on how best to handle this?  The below hack-a-fix resolves the issue,
> but it's obviously not appropriate.  KVM uses vcpu->preempted for more than just
> posted interrupts, so KVM needs equivalent functionality to current->on-rq as it
> was before this commit.
>
> @@ -6387,7 +6390,7 @@ static void kvm_sched_out(struct preempt_notifier *pn,
>  
>         WRITE_ONCE(vcpu->scheduled_out, true);
>  
> -       if (current->on_rq && vcpu->wants_to_run) {
> +       if (se_runnable(&current->se) && vcpu->wants_to_run) {
>                 WRITE_ONCE(vcpu->preempted, true);
>                 WRITE_ONCE(vcpu->ready, true);
>         }

Why is that deemed "obviously not appropriate"?  ->on_rq in and of
itself meaning only "on rq" doesn't seem like a bad thing.

	-Mike

Re: [PATCH 17/24] sched/fair: Implement delayed dequeue

[Sean Christopherson]

+KVM

On Thu, Aug 29, 2024, Marek Szyprowski wrote:
> On 27.07.2024 12:27, Peter Zijlstra wrote:
> > Extend / fix 86bfbb7ce4f6 ("sched/fair: Add lag based placement") by
> > noting that lag is fundamentally a temporal measure. It should not be
> > carried around indefinitely.
> >
> > OTOH it should also not be instantly discarded, doing so will allow a
> > task to game the system by purposefully (micro) sleeping at the end of
> > its time quantum.
> >
> > Since lag is intimately tied to the virtual time base, a wall-time
> > based decay is also insufficient, notably competition is required for
> > any of this to make sense.
> >
> > Instead, delay the dequeue and keep the 'tasks' on the runqueue,
> > competing until they are eligible.
> >
> > Strictly speaking, we only care about keeping them until the 0-lag
> > point, but that is a difficult proposition, instead carry them around
> > until they get picked again, and dequeue them at that point.
> >
> > Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
> 
> This patch landed recently in linux-next as commit 152e11f6df29 
> ("sched/fair: Implement delayed dequeue"). In my tests on some of the 
> ARM 32bit boards it causes a regression in rtcwake tool behavior - from 
> time to time this simple call never ends:
> 
> # time rtcwake -s 10 -m on
> 
> Reverting this commit (together with its compile dependencies) on top of 
> linux-next fixes this issue. Let me know how can I help debugging this 
> issue.

This commit broke KVM's posted interrupt handling (and other things), and the root
cause may be the same underlying issue.

TL;DR: Code that checks task_struct.on_rq may be broken by this commit.

KVM's breakage boils down to the preempt notifiers, i.e. kvm_sched_out(), being
invoked with current->on_rq "true" after KVM has explicitly called schedule().
kvm_sched_out() uses current->on_rq to determine if the vCPU is being preempted
(voluntarily or not, doesn't matter), and so waiting until some later point in
time to call __block_task() causes KVM to think the task was preempted, when in
reality it was not.

  static void kvm_sched_out(struct preempt_notifier *pn,
 			  struct task_struct *next)
  {
	struct kvm_vcpu *vcpu = preempt_notifier_to_vcpu(pn);

	WRITE_ONCE(vcpu->scheduled_out, true);

	if (current->on_rq && vcpu->wants_to_run) {  <================
		WRITE_ONCE(vcpu->preempted, true);
		WRITE_ONCE(vcpu->ready, true);
	}
	kvm_arch_vcpu_put(vcpu);
	__this_cpu_write(kvm_running_vcpu, NULL);
  }

KVM uses vcpu->preempted for a variety of things, but the most visibly problematic
is waking a vCPU from (virtual) HLT via posted interrupt wakeup.  When a vCPU
HLTs, KVM ultimate calls schedule() to schedule out the vCPU until it receives
a wake event.

When a device or another vCPU can post an interrupt as a wake event, KVM mucks
with the blocking vCPU's posted interrupt descriptor so that posted interrupts
that should be wake events get delivered on a dedicated host IRQ vector, so that
KVM can kick and wake the target vCPU.

But when vcpu->preempted is true, KVM suppresses posted interrupt notifications,
knowing that the vCPU will be scheduled back in.  Because a vCPU (task) can be
preempted while KVM is emulating HLT, KVM keys off vcpu->preempted to set PID.SN,
and doesn't exempt the blocking case.  In short, KVM uses vcpu->preempted, i.e.
current->on_rq, to differentiate between the vCPU getting preempted and KVM
executing schedule().

As a result, the false positive for vcpu->preempted causes KVM to suppress posted
interrupt notifications and the target vCPU never gets its wake event.


Peter,

Any thoughts on how best to handle this?  The below hack-a-fix resolves the issue,
but it's obviously not appropriate.  KVM uses vcpu->preempted for more than just
posted interrupts, so KVM needs equivalent functionality to current->on-rq as it
was before this commit.

@@ -6387,7 +6390,7 @@ static void kvm_sched_out(struct preempt_notifier *pn,
 
        WRITE_ONCE(vcpu->scheduled_out, true);
 
-       if (current->on_rq && vcpu->wants_to_run) {
+       if (se_runnable(&current->se) && vcpu->wants_to_run) {
                WRITE_ONCE(vcpu->preempted, true);
                WRITE_ONCE(vcpu->ready, true);
        }

Re: [PATCH 17/24] sched/fair: Implement delayed dequeue

[Marek Szyprowski]

On 27.07.2024 12:27, Peter Zijlstra wrote:
> Extend / fix 86bfbb7ce4f6 ("sched/fair: Add lag based placement") by
> noting that lag is fundamentally a temporal measure. It should not be
> carried around indefinitely.
>
> OTOH it should also not be instantly discarded, doing so will allow a
> task to game the system by purposefully (micro) sleeping at the end of
> its time quantum.
>
> Since lag is intimately tied to the virtual time base, a wall-time
> based decay is also insufficient, notably competition is required for
> any of this to make sense.
>
> Instead, delay the dequeue and keep the 'tasks' on the runqueue,
> competing until they are eligible.
>
> Strictly speaking, we only care about keeping them until the 0-lag
> point, but that is a difficult proposition, instead carry them around
> until they get picked again, and dequeue them at that point.
>
> Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>

This patch landed recently in linux-next as commit 152e11f6df29 
("sched/fair: Implement delayed dequeue"). In my tests on some of the 
ARM 32bit boards it causes a regression in rtcwake tool behavior - from 
time to time this simple call never ends:

# time rtcwake -s 10 -m on

Reverting this commit (together with its compile dependencies) on top of 
linux-next fixes this issue. Let me know how can I help debugging this 
issue.

> ---
>   kernel/sched/deadline.c |    1
>   kernel/sched/fair.c     |   82 ++++++++++++++++++++++++++++++++++++++++++------
>   kernel/sched/features.h |    9 +++++
>   3 files changed, 81 insertions(+), 11 deletions(-)
>
> --- a/kernel/sched/deadline.c
> +++ b/kernel/sched/deadline.c
> @@ -2428,7 +2428,6 @@ static struct task_struct *__pick_next_t
>   		else
>   			p = dl_se->server_pick_next(dl_se);
>   		if (!p) {
> -			WARN_ON_ONCE(1);
>   			dl_se->dl_yielded = 1;
>   			update_curr_dl_se(rq, dl_se, 0);
>   			goto again;
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -5379,20 +5379,44 @@ static void clear_buddies(struct cfs_rq
>   
>   static __always_inline void return_cfs_rq_runtime(struct cfs_rq *cfs_rq);
>   
> -static void
> +static bool
>   dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
>   {
> -	int action = UPDATE_TG;
> +	if (flags & DEQUEUE_DELAYED) {
> +		/*
> +		 * DEQUEUE_DELAYED is typically called from pick_next_entity()
> +		 * at which point we've already done update_curr() and do not
> +		 * want to do so again.
> +		 */
> +		SCHED_WARN_ON(!se->sched_delayed);
> +		se->sched_delayed = 0;
> +	} else {
> +		bool sleep = flags & DEQUEUE_SLEEP;
> +
> +		/*
> +		 * DELAY_DEQUEUE relies on spurious wakeups, special task
> +		 * states must not suffer spurious wakeups, excempt them.
> +		 */
> +		if (flags & DEQUEUE_SPECIAL)
> +			sleep = false;
> +
> +		SCHED_WARN_ON(sleep && se->sched_delayed);
> +		update_curr(cfs_rq);
>   
> +		if (sched_feat(DELAY_DEQUEUE) && sleep &&
> +		    !entity_eligible(cfs_rq, se)) {
> +			if (cfs_rq->next == se)
> +				cfs_rq->next = NULL;
> +			se->sched_delayed = 1;
> +			return false;
> +		}
> +	}
> +
> +	int action = UPDATE_TG;
>   	if (entity_is_task(se) && task_on_rq_migrating(task_of(se)))
>   		action |= DO_DETACH;
>   
>   	/*
> -	 * Update run-time statistics of the 'current'.
> -	 */
> -	update_curr(cfs_rq);
> -
> -	/*
>   	 * When dequeuing a sched_entity, we must:
>   	 *   - Update loads to have both entity and cfs_rq synced with now.
>   	 *   - For group_entity, update its runnable_weight to reflect the new
> @@ -5430,6 +5454,8 @@ dequeue_entity(struct cfs_rq *cfs_rq, st
>   
>   	if (cfs_rq->nr_running == 0)
>   		update_idle_cfs_rq_clock_pelt(cfs_rq);
> +
> +	return true;
>   }
>   
>   static void
> @@ -5828,11 +5854,21 @@ static bool throttle_cfs_rq(struct cfs_r
>   	idle_task_delta = cfs_rq->idle_h_nr_running;
>   	for_each_sched_entity(se) {
>   		struct cfs_rq *qcfs_rq = cfs_rq_of(se);
> +		int flags;
> +
>   		/* throttled entity or throttle-on-deactivate */
>   		if (!se->on_rq)
>   			goto done;
>   
> -		dequeue_entity(qcfs_rq, se, DEQUEUE_SLEEP);
> +		/*
> +		 * Abuse SPECIAL to avoid delayed dequeue in this instance.
> +		 * This avoids teaching dequeue_entities() about throttled
> +		 * entities and keeps things relatively simple.
> +		 */
> +		flags = DEQUEUE_SLEEP | DEQUEUE_SPECIAL;
> +		if (se->sched_delayed)
> +			flags |= DEQUEUE_DELAYED;
> +		dequeue_entity(qcfs_rq, se, flags);
>   
>   		if (cfs_rq_is_idle(group_cfs_rq(se)))
>   			idle_task_delta = cfs_rq->h_nr_running;
> @@ -6918,6 +6954,7 @@ static int dequeue_entities(struct rq *r
>   	bool was_sched_idle = sched_idle_rq(rq);
>   	int rq_h_nr_running = rq->cfs.h_nr_running;
>   	bool task_sleep = flags & DEQUEUE_SLEEP;
> +	bool task_delayed = flags & DEQUEUE_DELAYED;
>   	struct task_struct *p = NULL;
>   	int idle_h_nr_running = 0;
>   	int h_nr_running = 0;
> @@ -6931,7 +6968,13 @@ static int dequeue_entities(struct rq *r
>   
>   	for_each_sched_entity(se) {
>   		cfs_rq = cfs_rq_of(se);
> -		dequeue_entity(cfs_rq, se, flags);
> +
> +		if (!dequeue_entity(cfs_rq, se, flags)) {
> +			if (p && &p->se == se)
> +				return -1;
> +
> +			break;
> +		}
>   
>   		cfs_rq->h_nr_running -= h_nr_running;
>   		cfs_rq->idle_h_nr_running -= idle_h_nr_running;
> @@ -6956,6 +6999,7 @@ static int dequeue_entities(struct rq *r
>   			break;
>   		}
>   		flags |= DEQUEUE_SLEEP;
> +		flags &= ~(DEQUEUE_DELAYED | DEQUEUE_SPECIAL);
>   	}
>   
>   	for_each_sched_entity(se) {
> @@ -6985,6 +7029,17 @@ static int dequeue_entities(struct rq *r
>   	if (unlikely(!was_sched_idle && sched_idle_rq(rq)))
>   		rq->next_balance = jiffies;
>   
> +	if (p && task_delayed) {
> +		SCHED_WARN_ON(!task_sleep);
> +		SCHED_WARN_ON(p->on_rq != 1);
> +
> +		/* Fix-up what dequeue_task_fair() skipped */
> +		hrtick_update(rq);
> +
> +		/* Fix-up what block_task() skipped. */
> +		__block_task(rq, p);
> +	}
> +
>   	return 1;
>   }
>   /*
> @@ -6996,8 +7051,10 @@ static bool dequeue_task_fair(struct rq
>   {
>   	util_est_dequeue(&rq->cfs, p);
>   
> -	if (dequeue_entities(rq, &p->se, flags) < 0)
> +	if (dequeue_entities(rq, &p->se, flags) < 0) {
> +		util_est_update(&rq->cfs, p, DEQUEUE_SLEEP);
>   		return false;
> +	}
>   
>   	util_est_update(&rq->cfs, p, flags & DEQUEUE_SLEEP);
>   	hrtick_update(rq);
> @@ -12973,6 +13030,11 @@ static void set_next_task_fair(struct rq
>   		/* ensure bandwidth has been allocated on our new cfs_rq */
>   		account_cfs_rq_runtime(cfs_rq, 0);
>   	}
> +
> +	if (!first)
> +		return;
> +
> +	SCHED_WARN_ON(se->sched_delayed);
>   }
>   
>   void init_cfs_rq(struct cfs_rq *cfs_rq)
> --- a/kernel/sched/features.h
> +++ b/kernel/sched/features.h
> @@ -29,6 +29,15 @@ SCHED_FEAT(NEXT_BUDDY, false)
>   SCHED_FEAT(CACHE_HOT_BUDDY, true)
>   
>   /*
> + * Delay dequeueing tasks until they get selected or woken.
> + *
> + * By delaying the dequeue for non-eligible tasks, they remain in the
> + * competition and can burn off their negative lag. When they get selected
> + * they'll have positive lag by definition.
> + */
> +SCHED_FEAT(DELAY_DEQUEUE, true)
> +
> +/*
>    * Allow wakeup-time preemption of the current task:
>    */
>   SCHED_FEAT(WAKEUP_PREEMPTION, true)
>
>
>
Best regards
-- 
Marek Szyprowski, PhD
Samsung R&D Institute Poland

Re: [PATCH 17/24] sched/fair: Implement delayed dequeue

[Luis Machado]

Hi Peter,

On 7/27/24 11:27, Peter Zijlstra wrote:
> Extend / fix 86bfbb7ce4f6 ("sched/fair: Add lag based placement") by
> noting that lag is fundamentally a temporal measure. It should not be
> carried around indefinitely.
> 
> OTOH it should also not be instantly discarded, doing so will allow a
> task to game the system by purposefully (micro) sleeping at the end of
> its time quantum.
> 
> Since lag is intimately tied to the virtual time base, a wall-time
> based decay is also insufficient, notably competition is required for
> any of this to make sense.
> 
> Instead, delay the dequeue and keep the 'tasks' on the runqueue,
> competing until they are eligible.
> 
> Strictly speaking, we only care about keeping them until the 0-lag
> point, but that is a difficult proposition, instead carry them around
> until they get picked again, and dequeue them at that point.
> 
> Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
> ---
>  kernel/sched/deadline.c |    1 
>  kernel/sched/fair.c     |   82 ++++++++++++++++++++++++++++++++++++++++++------
>  kernel/sched/features.h |    9 +++++
>  3 files changed, 81 insertions(+), 11 deletions(-)
> 
> --- a/kernel/sched/deadline.c
> +++ b/kernel/sched/deadline.c
> @@ -2428,7 +2428,6 @@ static struct task_struct *__pick_next_t
>  		else
>  			p = dl_se->server_pick_next(dl_se);
>  		if (!p) {
> -			WARN_ON_ONCE(1);
>  			dl_se->dl_yielded = 1;
>  			update_curr_dl_se(rq, dl_se, 0);
>  			goto again;
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -5379,20 +5379,44 @@ static void clear_buddies(struct cfs_rq
>  
>  static __always_inline void return_cfs_rq_runtime(struct cfs_rq *cfs_rq);
>  
> -static void
> +static bool
>  dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
>  {
> -	int action = UPDATE_TG;
> +	if (flags & DEQUEUE_DELAYED) {
> +		/*
> +		 * DEQUEUE_DELAYED is typically called from pick_next_entity()
> +		 * at which point we've already done update_curr() and do not
> +		 * want to do so again.
> +		 */
> +		SCHED_WARN_ON(!se->sched_delayed);
> +		se->sched_delayed = 0;
> +	} else {
> +		bool sleep = flags & DEQUEUE_SLEEP;
> +
> +		/*
> +		 * DELAY_DEQUEUE relies on spurious wakeups, special task
> +		 * states must not suffer spurious wakeups, excempt them.
> +		 */
> +		if (flags & DEQUEUE_SPECIAL)
> +			sleep = false;
> +
> +		SCHED_WARN_ON(sleep && se->sched_delayed);
> +		update_curr(cfs_rq);
>  
> +		if (sched_feat(DELAY_DEQUEUE) && sleep &&
> +		    !entity_eligible(cfs_rq, se)) {
> +			if (cfs_rq->next == se)
> +				cfs_rq->next = NULL;
> +			se->sched_delayed = 1;
> +			return false;
> +		}
> +	}
> +
> +	int action = UPDATE_TG;
>  	if (entity_is_task(se) && task_on_rq_migrating(task_of(se)))
>  		action |= DO_DETACH;
>  
>  	/*
> -	 * Update run-time statistics of the 'current'.
> -	 */
> -	update_curr(cfs_rq);
> -
> -	/*
>  	 * When dequeuing a sched_entity, we must:
>  	 *   - Update loads to have both entity and cfs_rq synced with now.
>  	 *   - For group_entity, update its runnable_weight to reflect the new
> @@ -5430,6 +5454,8 @@ dequeue_entity(struct cfs_rq *cfs_rq, st
>  
>  	if (cfs_rq->nr_running == 0)
>  		update_idle_cfs_rq_clock_pelt(cfs_rq);
> +
> +	return true;
>  }
>  
>  static void
> @@ -5828,11 +5854,21 @@ static bool throttle_cfs_rq(struct cfs_r
>  	idle_task_delta = cfs_rq->idle_h_nr_running;
>  	for_each_sched_entity(se) {
>  		struct cfs_rq *qcfs_rq = cfs_rq_of(se);
> +		int flags;
> +
>  		/* throttled entity or throttle-on-deactivate */
>  		if (!se->on_rq)
>  			goto done;
>  
> -		dequeue_entity(qcfs_rq, se, DEQUEUE_SLEEP);
> +		/*
> +		 * Abuse SPECIAL to avoid delayed dequeue in this instance.
> +		 * This avoids teaching dequeue_entities() about throttled
> +		 * entities and keeps things relatively simple.
> +		 */
> +		flags = DEQUEUE_SLEEP | DEQUEUE_SPECIAL;
> +		if (se->sched_delayed)
> +			flags |= DEQUEUE_DELAYED;
> +		dequeue_entity(qcfs_rq, se, flags);
>  
>  		if (cfs_rq_is_idle(group_cfs_rq(se)))
>  			idle_task_delta = cfs_rq->h_nr_running;
> @@ -6918,6 +6954,7 @@ static int dequeue_entities(struct rq *r
>  	bool was_sched_idle = sched_idle_rq(rq);
>  	int rq_h_nr_running = rq->cfs.h_nr_running;
>  	bool task_sleep = flags & DEQUEUE_SLEEP;
> +	bool task_delayed = flags & DEQUEUE_DELAYED;
>  	struct task_struct *p = NULL;
>  	int idle_h_nr_running = 0;
>  	int h_nr_running = 0;
> @@ -6931,7 +6968,13 @@ static int dequeue_entities(struct rq *r
>  
>  	for_each_sched_entity(se) {
>  		cfs_rq = cfs_rq_of(se);
> -		dequeue_entity(cfs_rq, se, flags);
> +
> +		if (!dequeue_entity(cfs_rq, se, flags)) {
> +			if (p && &p->se == se)
> +				return -1;
> +
> +			break;
> +		}
>  
>  		cfs_rq->h_nr_running -= h_nr_running;
>  		cfs_rq->idle_h_nr_running -= idle_h_nr_running;
> @@ -6956,6 +6999,7 @@ static int dequeue_entities(struct rq *r
>  			break;
>  		}
>  		flags |= DEQUEUE_SLEEP;
> +		flags &= ~(DEQUEUE_DELAYED | DEQUEUE_SPECIAL);
>  	}
>  
>  	for_each_sched_entity(se) {
> @@ -6985,6 +7029,17 @@ static int dequeue_entities(struct rq *r
>  	if (unlikely(!was_sched_idle && sched_idle_rq(rq)))
>  		rq->next_balance = jiffies;
>  
> +	if (p && task_delayed) {
> +		SCHED_WARN_ON(!task_sleep);
> +		SCHED_WARN_ON(p->on_rq != 1);
> +
> +		/* Fix-up what dequeue_task_fair() skipped */
> +		hrtick_update(rq);
> +
> +		/* Fix-up what block_task() skipped. */
> +		__block_task(rq, p);
> +	}
> +
>  	return 1;
>  }
>  /*
> @@ -6996,8 +7051,10 @@ static bool dequeue_task_fair(struct rq
>  {
>  	util_est_dequeue(&rq->cfs, p);
>  
> -	if (dequeue_entities(rq, &p->se, flags) < 0)
> +	if (dequeue_entities(rq, &p->se, flags) < 0) {
> +		util_est_update(&rq->cfs, p, DEQUEUE_SLEEP);
>  		return false;
> +	}
>  
>  	util_est_update(&rq->cfs, p, flags & DEQUEUE_SLEEP);
>  	hrtick_update(rq);
> @@ -12973,6 +13030,11 @@ static void set_next_task_fair(struct rq
>  		/* ensure bandwidth has been allocated on our new cfs_rq */
>  		account_cfs_rq_runtime(cfs_rq, 0);
>  	}
> +
> +	if (!first)
> +		return;
> +
> +	SCHED_WARN_ON(se->sched_delayed);
>  }
>  
>  void init_cfs_rq(struct cfs_rq *cfs_rq)
> --- a/kernel/sched/features.h
> +++ b/kernel/sched/features.h
> @@ -29,6 +29,15 @@ SCHED_FEAT(NEXT_BUDDY, false)
>  SCHED_FEAT(CACHE_HOT_BUDDY, true)
>  
>  /*
> + * Delay dequeueing tasks until they get selected or woken.
> + *
> + * By delaying the dequeue for non-eligible tasks, they remain in the
> + * competition and can burn off their negative lag. When they get selected
> + * they'll have positive lag by definition.
> + */
> +SCHED_FEAT(DELAY_DEQUEUE, true)
> +
> +/*
>   * Allow wakeup-time preemption of the current task:
>   */
>  SCHED_FEAT(WAKEUP_PREEMPTION, true)
> 
> 
> 

Just a heads-up I'm chasing some odd behavior on the big.little/pixel 6 platform, where
sometimes I see runs with spikes of higher frequencies for extended amounts of time (multiple
seconds), in particular for little cores, which leads to higher energy use.

I'm still trying to understand why that happens, but looks like the utilization values are
sometimes stuck at high values. I just want to make sure the delayed dequeue changes aren't
interfering with the util calculations.

Unfortunately the benchmark is Android-specific, so hard to provide a reasonable
reproducer for Linux.

Re: [PATCH 17/24] sched/fair: Implement delayed dequeue

[Valentin Schneider]

On 02/08/24 16:59, Peter Zijlstra wrote:
> On Fri, Aug 02, 2024 at 04:39:08PM +0200, Valentin Schneider wrote:
>>
>> On 27/07/24 12:27, Peter Zijlstra wrote:
>> > Extend / fix 86bfbb7ce4f6 ("sched/fair: Add lag based placement") by
>> > noting that lag is fundamentally a temporal measure. It should not be
>> > carried around indefinitely.
>> >
>> > OTOH it should also not be instantly discarded, doing so will allow a
>> > task to game the system by purposefully (micro) sleeping at the end of
>> > its time quantum.
>> >
>> > Since lag is intimately tied to the virtual time base, a wall-time
>> > based decay is also insufficient, notably competition is required for
>> > any of this to make sense.
>> >
>> > Instead, delay the dequeue and keep the 'tasks' on the runqueue,
>> > competing until they are eligible.
>> >
>> > Strictly speaking, we only care about keeping them until the 0-lag
>> > point, but that is a difficult proposition, instead carry them around
>> > until they get picked again, and dequeue them at that point.
>> >
>>
>> Question from a lazy student who just caught up to the current state of
>> EEVDF...
>>
>> IIUC this makes it so time spent sleeping increases an entity's lag, rather
>> than it being frozen & restored via the place_entity() magic.
>>
>> So entities with negative lag get closer to their 0-lag point, after which
>> they can get picked & dequeued if still not runnable.
>
> Right.
>
>> However, don't entities with positive lag get *further* away from their
>> 0-lag point?
>
> Which is why we only delay de dequeue when !eligible, IOW when lag is
> negative.
>
> The next patch additionally truncates lag to 0 (for delayed entities),
> so they can never earn extra time.

Gotcha, thanks for pointing that out, I think I'm (slowly) getting it :D

Re: [PATCH 17/24] sched/fair: Implement delayed dequeue

[Peter Zijlstra]

On Fri, Aug 02, 2024 at 04:39:08PM +0200, Valentin Schneider wrote:
> 
> On 27/07/24 12:27, Peter Zijlstra wrote:
> > Extend / fix 86bfbb7ce4f6 ("sched/fair: Add lag based placement") by
> > noting that lag is fundamentally a temporal measure. It should not be
> > carried around indefinitely.
> >
> > OTOH it should also not be instantly discarded, doing so will allow a
> > task to game the system by purposefully (micro) sleeping at the end of
> > its time quantum.
> >
> > Since lag is intimately tied to the virtual time base, a wall-time
> > based decay is also insufficient, notably competition is required for
> > any of this to make sense.
> >
> > Instead, delay the dequeue and keep the 'tasks' on the runqueue,
> > competing until they are eligible.
> >
> > Strictly speaking, we only care about keeping them until the 0-lag
> > point, but that is a difficult proposition, instead carry them around
> > until they get picked again, and dequeue them at that point.
> >
> 
> Question from a lazy student who just caught up to the current state of
> EEVDF...
> 
> IIUC this makes it so time spent sleeping increases an entity's lag, rather
> than it being frozen & restored via the place_entity() magic.
> 
> So entities with negative lag get closer to their 0-lag point, after which
> they can get picked & dequeued if still not runnable.

Right.

> However, don't entities with positive lag get *further* away from their
> 0-lag point?

Which is why we only delay de dequeue when !eligible, IOW when lag is
negative.

The next patch additionally truncates lag to 0 (for delayed entities),
so they can never earn extra time.

Re: [PATCH 17/24] sched/fair: Implement delayed dequeue

[Valentin Schneider]

On 27/07/24 12:27, Peter Zijlstra wrote:
> Extend / fix 86bfbb7ce4f6 ("sched/fair: Add lag based placement") by
> noting that lag is fundamentally a temporal measure. It should not be
> carried around indefinitely.
>
> OTOH it should also not be instantly discarded, doing so will allow a
> task to game the system by purposefully (micro) sleeping at the end of
> its time quantum.
>
> Since lag is intimately tied to the virtual time base, a wall-time
> based decay is also insufficient, notably competition is required for
> any of this to make sense.
>
> Instead, delay the dequeue and keep the 'tasks' on the runqueue,
> competing until they are eligible.
>
> Strictly speaking, we only care about keeping them until the 0-lag
> point, but that is a difficult proposition, instead carry them around
> until they get picked again, and dequeue them at that point.
>

Question from a lazy student who just caught up to the current state of
EEVDF...

IIUC this makes it so time spent sleeping increases an entity's lag, rather
than it being frozen & restored via the place_entity() magic.

So entities with negative lag get closer to their 0-lag point, after which
they can get picked & dequeued if still not runnable.

However, don't entities with positive lag get *further* away from their
0-lag point?

[PATCH 17/24] sched/fair: Implement delayed dequeue

[Peter Zijlstra]

Extend / fix 86bfbb7ce4f6 ("sched/fair: Add lag based placement") by
noting that lag is fundamentally a temporal measure. It should not be
carried around indefinitely.

OTOH it should also not be instantly discarded, doing so will allow a
task to game the system by purposefully (micro) sleeping at the end of
its time quantum.

Since lag is intimately tied to the virtual time base, a wall-time
based decay is also insufficient, notably competition is required for
any of this to make sense.

Instead, delay the dequeue and keep the 'tasks' on the runqueue,
competing until they are eligible.

Strictly speaking, we only care about keeping them until the 0-lag
point, but that is a difficult proposition, instead carry them around
until they get picked again, and dequeue them at that point.

Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
---
 kernel/sched/deadline.c |    1 
 kernel/sched/fair.c     |   82 ++++++++++++++++++++++++++++++++++++++++++------
 kernel/sched/features.h |    9 +++++
 3 files changed, 81 insertions(+), 11 deletions(-)

--- a/kernel/sched/deadline.c
+++ b/kernel/sched/deadline.c
@@ -2428,7 +2428,6 @@ static struct task_struct *__pick_next_t
 		else
 			p = dl_se->server_pick_next(dl_se);
 		if (!p) {
-			WARN_ON_ONCE(1);
 			dl_se->dl_yielded = 1;
 			update_curr_dl_se(rq, dl_se, 0);
 			goto again;
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -5379,20 +5379,44 @@ static void clear_buddies(struct cfs_rq
 
 static __always_inline void return_cfs_rq_runtime(struct cfs_rq *cfs_rq);
 
-static void
+static bool
 dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
 {
-	int action = UPDATE_TG;
+	if (flags & DEQUEUE_DELAYED) {
+		/*
+		 * DEQUEUE_DELAYED is typically called from pick_next_entity()
+		 * at which point we've already done update_curr() and do not
+		 * want to do so again.
+		 */
+		SCHED_WARN_ON(!se->sched_delayed);
+		se->sched_delayed = 0;
+	} else {
+		bool sleep = flags & DEQUEUE_SLEEP;
+
+		/*
+		 * DELAY_DEQUEUE relies on spurious wakeups, special task
+		 * states must not suffer spurious wakeups, excempt them.
+		 */
+		if (flags & DEQUEUE_SPECIAL)
+			sleep = false;
+
+		SCHED_WARN_ON(sleep && se->sched_delayed);
+		update_curr(cfs_rq);
 
+		if (sched_feat(DELAY_DEQUEUE) && sleep &&
+		    !entity_eligible(cfs_rq, se)) {
+			if (cfs_rq->next == se)
+				cfs_rq->next = NULL;
+			se->sched_delayed = 1;
+			return false;
+		}
+	}
+
+	int action = UPDATE_TG;
 	if (entity_is_task(se) && task_on_rq_migrating(task_of(se)))
 		action |= DO_DETACH;
 
 	/*
-	 * Update run-time statistics of the 'current'.
-	 */
-	update_curr(cfs_rq);
-
-	/*
 	 * When dequeuing a sched_entity, we must:
 	 *   - Update loads to have both entity and cfs_rq synced with now.
 	 *   - For group_entity, update its runnable_weight to reflect the new
@@ -5430,6 +5454,8 @@ dequeue_entity(struct cfs_rq *cfs_rq, st
 
 	if (cfs_rq->nr_running == 0)
 		update_idle_cfs_rq_clock_pelt(cfs_rq);
+
+	return true;
 }
 
 static void
@@ -5828,11 +5854,21 @@ static bool throttle_cfs_rq(struct cfs_r
 	idle_task_delta = cfs_rq->idle_h_nr_running;
 	for_each_sched_entity(se) {
 		struct cfs_rq *qcfs_rq = cfs_rq_of(se);
+		int flags;
+
 		/* throttled entity or throttle-on-deactivate */
 		if (!se->on_rq)
 			goto done;
 
-		dequeue_entity(qcfs_rq, se, DEQUEUE_SLEEP);
+		/*
+		 * Abuse SPECIAL to avoid delayed dequeue in this instance.
+		 * This avoids teaching dequeue_entities() about throttled
+		 * entities and keeps things relatively simple.
+		 */
+		flags = DEQUEUE_SLEEP | DEQUEUE_SPECIAL;
+		if (se->sched_delayed)
+			flags |= DEQUEUE_DELAYED;
+		dequeue_entity(qcfs_rq, se, flags);
 
 		if (cfs_rq_is_idle(group_cfs_rq(se)))
 			idle_task_delta = cfs_rq->h_nr_running;
@@ -6918,6 +6954,7 @@ static int dequeue_entities(struct rq *r
 	bool was_sched_idle = sched_idle_rq(rq);
 	int rq_h_nr_running = rq->cfs.h_nr_running;
 	bool task_sleep = flags & DEQUEUE_SLEEP;
+	bool task_delayed = flags & DEQUEUE_DELAYED;
 	struct task_struct *p = NULL;
 	int idle_h_nr_running = 0;
 	int h_nr_running = 0;
@@ -6931,7 +6968,13 @@ static int dequeue_entities(struct rq *r
 
 	for_each_sched_entity(se) {
 		cfs_rq = cfs_rq_of(se);
-		dequeue_entity(cfs_rq, se, flags);
+
+		if (!dequeue_entity(cfs_rq, se, flags)) {
+			if (p && &p->se == se)
+				return -1;
+
+			break;
+		}
 
 		cfs_rq->h_nr_running -= h_nr_running;
 		cfs_rq->idle_h_nr_running -= idle_h_nr_running;
@@ -6956,6 +6999,7 @@ static int dequeue_entities(struct rq *r
 			break;
 		}
 		flags |= DEQUEUE_SLEEP;
+		flags &= ~(DEQUEUE_DELAYED | DEQUEUE_SPECIAL);
 	}
 
 	for_each_sched_entity(se) {
@@ -6985,6 +7029,17 @@ static int dequeue_entities(struct rq *r
 	if (unlikely(!was_sched_idle && sched_idle_rq(rq)))
 		rq->next_balance = jiffies;
 
+	if (p && task_delayed) {
+		SCHED_WARN_ON(!task_sleep);
+		SCHED_WARN_ON(p->on_rq != 1);
+
+		/* Fix-up what dequeue_task_fair() skipped */
+		hrtick_update(rq);
+
+		/* Fix-up what block_task() skipped. */
+		__block_task(rq, p);
+	}
+
 	return 1;
 }
 /*
@@ -6996,8 +7051,10 @@ static bool dequeue_task_fair(struct rq
 {
 	util_est_dequeue(&rq->cfs, p);
 
-	if (dequeue_entities(rq, &p->se, flags) < 0)
+	if (dequeue_entities(rq, &p->se, flags) < 0) {
+		util_est_update(&rq->cfs, p, DEQUEUE_SLEEP);
 		return false;
+	}
 
 	util_est_update(&rq->cfs, p, flags & DEQUEUE_SLEEP);
 	hrtick_update(rq);
@@ -12973,6 +13030,11 @@ static void set_next_task_fair(struct rq
 		/* ensure bandwidth has been allocated on our new cfs_rq */
 		account_cfs_rq_runtime(cfs_rq, 0);
 	}
+
+	if (!first)
+		return;
+
+	SCHED_WARN_ON(se->sched_delayed);
 }
 
 void init_cfs_rq(struct cfs_rq *cfs_rq)
--- a/kernel/sched/features.h
+++ b/kernel/sched/features.h
@@ -29,6 +29,15 @@ SCHED_FEAT(NEXT_BUDDY, false)
 SCHED_FEAT(CACHE_HOT_BUDDY, true)
 
 /*
+ * Delay dequeueing tasks until they get selected or woken.
+ *
+ * By delaying the dequeue for non-eligible tasks, they remain in the
+ * competition and can burn off their negative lag. When they get selected
+ * they'll have positive lag by definition.
+ */
+SCHED_FEAT(DELAY_DEQUEUE, true)
+
+/*
  * Allow wakeup-time preemption of the current task:
  */
 SCHED_FEAT(WAKEUP_PREEMPTION, true)