Skip to contentSkip to conversation

sched_ext: Fix scx_bpf_reenqueue_local()

PATCH Applied Tejun Heo 2 participants 6 messages Jul 9, 2024 Scheduler

lore
Share & tools
lore

Tejun Heo

author
#0 lore raw

PATCH 1/1 sched_ext: Fix scx_bpf_reenqueue_local()

Fix scx_bpf_reenqueue_local()'s misbehaviors in two cases:

- when SCX_ENQ_HEAD is used to dispatch a re-enqueued task back to the same local DSQ.

- when the CPU is being preempted by stop_task for task migration.

This patchset contains the following two patches:

0001-sched_ext-Reimplement-scx_bpf_reenqueue_local.patch 0002-sched_ext-Make-scx_bpf_reenqueue_local-skip-tasks-th.patch

and is also available in the following git branch:

git://git.kernel.org/pub/scm/linux/kernel/git/tj/sched_ext.git scx-fix-reenqueue_local

diffstat follows. Thanks.

 kernel/sched/ext.c |   40 +++++++++++++++++++++++++++-------------
 1 file changed, 27 insertions(+), 13 deletions(-)

--
tejun

author
#1 lore raw

PATCH 1/2 sched_ext: Reimplement scx_bpf_reenqueue_local()

scx_bpf_reenqueue_local() is used to re-enqueue tasks on the local DSQ from ops.cpu_release(). Because the BPF scheduler may dispatch tasks to the same local DSQ, to avoid processing the same tasks repeatedly, it first takes the number of queued tasks and processes the task at the head of the queue that number of times.

This is incorrect as a task can be dispatched to the same local DSQ with SCX_ENQ_HEAD. Such a task will be processed repeatedly until the count is exhausted and the succeeding tasks won't be processed at all.

Fix it by first moving all candidate tasks to a private list and then processing that list. While at it, remove the WARNs. They're rather superflous as later steps will check them anyway.

Fixes 245254f7081d ("sched_ext: Implement sched_ext_ops.cpu_acquire/release()")
Cc David Vernet <[email protected]>
---
 kernel/sched/ext.c | 28 ++++++++++++++--------------
 1 file changed, 14 insertions(+), 14 deletions(-)
kernel/sched/ext.c +14 -14
index f16d72d72635..0fabfe19327c 100644
@@ -5628,8 +5628,10 @@ __bpf_kfunc_start_defs();
  */
 __bpf_kfunc u32 scx_bpf_reenqueue_local(void)
 {
-	u32 nr_enqueued, i;
+	LIST_HEAD(tasks);
+	u32 nr_enqueued = 0;
 	struct rq *rq;
+	struct task_struct *p, *n;
 
 	if (!scx_kf_allowed(SCX_KF_CPU_RELEASE))
 		return 0;
@@ -5638,22 +5640,20 @@ __bpf_kfunc u32 scx_bpf_reenqueue_local(void)
 	lockdep_assert_rq_held(rq);
 
 	/*
-	 * Get the number of tasks on the local DSQ before iterating over it to
-	 * pull off tasks. The enqueue callback below can signal that it wants
-	 * the task to stay on the local DSQ, and we want to prevent the BPF
-	 * scheduler from causing us to loop indefinitely.
+	 * The BPF scheduler may choose to dispatch tasks back to
+	 * @rq->scx.local_dsq. Move all candidate tasks off to a private list
+	 * first to avoid processing the same tasks repeatedly.
 	 */
-	nr_enqueued = rq->scx.local_dsq.nr;
-	for (i = 0; i < nr_enqueued; i++) {
-		struct task_struct *p;
-
-		p = first_local_task(rq);
-		WARN_ON_ONCE(atomic_long_read(&p->scx.ops_state) !=
-			     SCX_OPSS_NONE);
-		WARN_ON_ONCE(!(p->scx.flags & SCX_TASK_QUEUED));
-		WARN_ON_ONCE(p->scx.holding_cpu != -1);
+	list_for_each_entry_safe(p, n, &rq->scx.local_dsq.list,
+				 scx.dsq_list.node) {
 		dispatch_dequeue(rq, p);
+		list_add_tail(&p->scx.dsq_list.node, &tasks);
+	}
+
+	list_for_each_entry_safe(p, n, &tasks, scx.dsq_list.node) {
+		list_del_init(&p->scx.dsq_list.node);
 		do_enqueue_task(rq, p, SCX_ENQ_REENQ, -1);
+		nr_enqueued++;
 	}
 
 	return nr_enqueued;
Signature · 1 line
2.45.2
Acked-by on v1 1/2
#2 lore raw

Re: [PATCH 1/2] sched_ext: Reimplement scx_bpf_reenqueue_local()

Quoted 10 lines · Tejun Heo

scx_bpf_reenqueue_local() is used to re-enqueue tasks on the local DSQ from ops.cpu_release(). Because the BPF scheduler may dispatch tasks to the same local DSQ, to avoid processing the same tasks repeatedly, it first takes the number of queued tasks and processes the task at the head of the queue that number of times.

This is incorrect as a task can be dispatched to the same local DSQ with SCX_ENQ_HEAD. Such a task will be processed repeatedly until the count is exhausted and the succeeding tasks won't be processed at all.

Quoted 7 lines

Fix it by first moving all candidate tasks to a private list and then processing that list. While at it, remove the WARNs. They're rather superflous as later steps will check them anyway.

Fixes 245254f7081d ("sched_ext: Implement sched_ext_ops.cpu_acquire/release()")
Cc David Vernet <[email protected]>
author
#3 lore raw

PATCH 2/2 sched_ext: Make scx_bpf_reenqueue_local() skip tasks that are being migrated

In reply to Tejun Heo

When a running task is migrated to another CPU, the stop_task is used to preempt the running task and migrate it. This, expectedly, invokes ops.cpu_release(). If the BPF scheduler then calls scx_bpf_reenqueue_local(), it re-enqueues all tasks on the local DSQ including the task which is being migrated.

This creates an unnecessary re-enqueue of a task which is about to be deactivated and re-activated for migration anyway. It can also cause confusion for the BPF scheduler as scx_bpf_task_cpu() of the task and its allowed CPUs may not agree while migration is pending.

Fixes 245254f7081d ("sched_ext: Implement sched_ext_ops.cpu_acquire/release()")
Cc David Vernet <[email protected]>
---
 kernel/sched/ext.c | 14 ++++++++++++++
 1 file changed, 14 insertions(+)
kernel/sched/ext.c +14 -0
index 0fabfe19327c..f4a7abcec793 100644
@@ -5646,6 +5646,20 @@ __bpf_kfunc u32 scx_bpf_reenqueue_local(void)
 	 */
 	list_for_each_entry_safe(p, n, &rq->scx.local_dsq.list,
 				 scx.dsq_list.node) {
+		/*
+		 * If @p is being migrated, @p's current CPU may not agree with
+		 * its allowed CPUs and the migration_cpu_stop is about to
+		 * deactivate and re-activate @p anyway. Skip re-enqueueing.
+		 *
+		 * While racing sched property changes may also dequeue and
+		 * re-enqueue a migrating task while its current CPU and allowed
+		 * CPUs disagree, they use %ENQUEUE_RESTORE which is bypassed to
+		 * the current local DSQ for running tasks and thus are not
+		 * visible to the BPF scheduler.
+		 */
+		if (p->migration_pending)
+			continue;
+
 		dispatch_dequeue(rq, p);
 		list_add_tail(&p->scx.dsq_list.node, &tasks);
 	}
Signature · 1 line
2.45.2
Acked-by on v1 2/2
#4 lore raw

Re: [PATCH 2/2] sched_ext: Make scx_bpf_reenqueue_local() skip tasks that are being migrated

Quoted 6 lines · Tejun Heo

When a running task is migrated to another CPU, the stop_task is used to preempt the running task and migrate it. This, expectedly, invokes ops.cpu_release(). If the BPF scheduler then calls scx_bpf_reenqueue_local(), it re-enqueues all tasks on the local DSQ including the task which is being migrated.

Quoted 8 lines

This creates an unnecessary re-enqueue of a task which is about to be deactivated and re-activated for migration anyway. It can also cause confusion for the BPF scheduler as scx_bpf_task_cpu() of the task and its allowed CPUs may not agree while migration is pending.

Fixes 245254f7081d ("sched_ext: Implement sched_ext_ops.cpu_acquire/release()")
Cc David Vernet <[email protected]>
author Applied
#5 lore raw
In reply to Tejun Heo
Quoted 11 lines · Tejun Heo

Fix scx_bpf_reenqueue_local()'s misbehaviors in two cases:

- when SCX_ENQ_HEAD is used to dispatch a re-enqueued task back to the same local DSQ.

- when the CPU is being preempted by stop_task for task migration.

This patchset contains the following two patches:

0001-sched_ext-Reimplement-scx_bpf_reenqueue_local.patch 0002-sched_ext-Make-scx_bpf_reenqueue_local-skip-tasks-th.patch

Applied to sched_ext/for-6.11.

Thanks.

Signature · 1 line
tejun