[PATCH] sched_ext: make DSQ iterator stay drained after NULL

[PATCH] sched_ext: make DSQ iterator stay drained after NULL

[Kang Chen]

nldsq_cursor_next_task() unlinks the iteration cursor when it reaches the
end of the DSQ.  A later call sees list_empty(&cursor->node), starts
from the DSQ head again, and returns the first task of the same
iteration.

The verifier relies on the iterator contract that once next() returns
NULL it keeps returning NULL: process_iter_next_call() marks the
iterator DRAINED and treats the result of later next() calls as the
constant zero.  A restarted DSQ iteration therefore hands the BPF
program a task pointer while the verifier believes R0 == 0.

Remember the drained state in the cursor flags and return NULL on every
later next() call.  The cursor has spare flag bits and the BPF-visible
iterator layout is unchanged.

Fixes: 650ba21b131e ("sched_ext: Implement DSQ iterator")
Signed-off-by: Kang Chen <k.chen@smail.nju.edu.cn>
---
 kernel/sched/ext/ext.c | 17 +++++++++++++++--
 1 file changed, 15 insertions(+), 2 deletions(-)

diff --git a/kernel/sched/ext/ext.c b/kernel/sched/ext/ext.c
index 9bae826d69f9..03e0fbf17011 100644
--- a/kernel/sched/ext/ext.c
+++ b/kernel/sched/ext/ext.c
@@ -555,12 +555,14 @@ enum scx_dsq_iter_flags {
 	/* iterate in the reverse dispatch order */
 	SCX_DSQ_ITER_REV		= 1U << 16,
 
+	__SCX_DSQ_ITER_DRAINED		= 1U << 28,
 	__SCX_DSQ_ITER_HAS_REENQ	= 1U << 29,
 	__SCX_DSQ_ITER_HAS_SLICE	= 1U << 30,
 	__SCX_DSQ_ITER_HAS_VTIME	= 1U << 31,
 
 	__SCX_DSQ_ITER_USER_FLAGS	= SCX_DSQ_ITER_REV,
 	__SCX_DSQ_ITER_ALL_FLAGS	= __SCX_DSQ_ITER_USER_FLAGS |
+					  __SCX_DSQ_ITER_DRAINED |
 					  __SCX_DSQ_ITER_HAS_REENQ |
 					  __SCX_DSQ_ITER_HAS_SLICE |
 					  __SCX_DSQ_ITER_HAS_VTIME,
@@ -10615,13 +10617,24 @@ __bpf_kfunc int bpf_iter_scx_dsq_new(struct bpf_iter_scx_dsq *it, u64 dsq_id,
 __bpf_kfunc struct task_struct *bpf_iter_scx_dsq_next(struct bpf_iter_scx_dsq *it)
 {
 	struct bpf_iter_scx_dsq_kern *kit = (void *)it;
+	struct task_struct *p;
 
-	if (!kit->dsq)
+	if (!kit->dsq || (kit->cursor.flags & __SCX_DSQ_ITER_DRAINED))
 		return NULL;
 
 	guard(raw_spinlock_irqsave)(&kit->dsq->lock);
 
-	return nldsq_cursor_next_task(&kit->cursor, kit->dsq);
+	p = nldsq_cursor_next_task(&kit->cursor, kit->dsq);
+	/*
+	 * nldsq_cursor_next_task() unlinks the cursor and starts from the DSQ
+	 * head when it is called again.  The verifier relies on an iterator
+	 * which returned NULL to keep returning NULL (see
+	 * process_iter_next_call()), so remember the drained state.
+	 */
+	if (!p)
+		kit->cursor.flags |= __SCX_DSQ_ITER_DRAINED;
+
+	return p;
 }
 
 /**
-- 
2.34.1

Re: [PATCH] sched_ext: make DSQ iterator stay drained after NULL

[sashiko-bot]

Thank you for your contribution! Sashiko AI review found no new issues
in this patch, but noticed 1 related pre-existing issue it does not
introduce:
- [High] sched_ext: recursive dsq->lock deadlock via
  bpf_iter_scx_dsq_next() in tracing [1]
--

commit 892356944fb79fb9f40ab2f24779b6976bd4ec25
Author: Kang Chen <k.chen@smail.nju.edu.cn>

sched_ext: make DSQ iterator stay drained after NULL

This commit records a drained flag in the DSQ iterator cursor once
nldsq_cursor_next_task() returns NULL so subsequent calls to
bpf_iter_scx_dsq_next() continue returning NULL.

> diff --git a/kernel/sched/ext/ext.c b/kernel/sched/ext/ext.c
> index ebdf7b91f9d37..f2bfd43d75526 100644
> --- a/kernel/sched/ext/ext.c
> +++ b/kernel/sched/ext/ext.c

[ ... ]

> @@ -11028,13 +11030,24 @@ __bpf_kfunc int bpf_iter_scx_dsq_new(struct bpf_iter_scx_dsq *it, u64 dsq_id,
>  __bpf_kfunc struct task_struct *bpf_iter_scx_dsq_next(struct bpf_iter_scx_dsq *it)
>  {
>  	struct bpf_iter_scx_dsq_kern *kit = (void *)it;
> +	struct task_struct *p;
>  
> -	if (!kit->dsq)
> +	if (!kit->dsq || (kit->cursor.flags & __SCX_DSQ_ITER_DRAINED))
>  		return NULL;
>  
>  	guard(raw_spinlock_irqsave)(&kit->dsq->lock);

[Severity: High]
This problem wasn't introduced by this patch, but can bpf_iter_scx_dsq_next()
and bpf_iter_scx_dsq_destroy() deadlock [1] on kit->dsq->lock when
called from a BPF tracing program?

The DSQ iterator kfuncs are registered in scx_kfunc_ids_any and are not
listed in scx_kfunc_ids_no_tracing, so scx_kfunc_context_filter() allows
BPF_PROG_TYPE_TRACING programs to call them.  If a tracing program runs
while the current CPU already holds the same user DSQ's lock, iterating that
DSQ attempts to acquire kit->dsq->lock recursively on the same CPU:

scx_dispatch_enqueue()
  raw_spin_lock(&dsq->lock)
  ...
  scx_error()
    trace_sched_ext_exit()
      <BPF tracing prog>
        bpf_iter_scx_dsq_next()
          raw_spin_lock_irqsave(&kit->dsq->lock)  <-- spins forever

Adding the DSQ iterator kfuncs to scx_kfunc_ids_no_tracing would prevent
tracing programs from calling them.

[1] https://sashiko.dev/#/bug/linux-243627bf-8f5e-401e-a2af-0b6c5d9b3088

-- 
Sashiko AI review · https://sashiko.dev/#/patchset/20261110125113.2935742-1-k.chen@smail.nju.edu.cn?part=1

Re: [PATCH] sched_ext: make DSQ iterator stay drained after NULL

[Tejun Heo]

Applied to sched_ext/for-7.4-fixes.

Thanks.

--
tejun