Skip to contentSkip to conversation

sched_ext: Prevent RB-tree corruption in scx_bpf_task_set_dsq_vtime()

PATCH In review Cheng-Yang Chou 4 participants 6 messages Apr 15 – Apr 16

Subsystems (3)
lore
Share & tools
lore
#0 lore raw

PATCH 1/1 sched_ext: Prevent RB-tree corruption in scx_bpf_task_set_dsq_vtime()

scx_bpf_task_set_dsq_vtime() allows modifying a task's dsq_vtime without checking if it is already enqueued on SCX_DSQ_PRIQ. Since dsq_vtime is the rb-tree sorting key, mutating it in-place violates the BST invariant and corrupts the tree structure.

In ops.dispatch():

	p = scx_bpf_dsq_peek(PRIO_DSQ); // Get a task already in the DSQ
	if (p) {
		// This illegally returns %true
		scx_bpf_task_set_dsq_vtime(p, 0xFFFFFFFFFFFFFFFF);
	}

Fix this by adding a check for the SCX_TASK_DSQ_ON_PRIQ flag. Disallow vtime modification and trigger scx_error() if the task is already queued on a priority DSQ.

Fixes 3035addfaf28 ("sched_ext: Add scx_bpf_task_set_slice() and scx_bpf_task_set_dsq_vtime()")
Cc [email protected] # v6.19+
---
 kernel/sched/ext.c | 8 +++++++-
 1 file changed, 7 insertions(+), 1 deletion(-)
kernel/sched/ext.c +7 -1
index 012ca8bd70fb..7a54f9bc5e7a 100644
@@ -8540,7 +8540,8 @@ __bpf_kfunc bool scx_bpf_task_set_slice(struct task_struct *p, u64 slice,
  * @aux: implicit BPF argument to access bpf_prog_aux hidden from BPF progs
  *
  * Set @p's virtual time to @vtime. Returns %true on success, %false if the
- * calling scheduler doesn't have authority over @p.
+ * calling scheduler doesn't have authority over @p. If @p is already enqueued
+ * on a priority DSQ, scx_error() is triggered and %false is returned.
  */
 __bpf_kfunc bool scx_bpf_task_set_dsq_vtime(struct task_struct *p, u64 vtime,
 					    const struct bpf_prog_aux *aux)
@@ -8552,6 +8553,11 @@ __bpf_kfunc bool scx_bpf_task_set_dsq_vtime(struct task_struct *p, u64 vtime,
 	if (unlikely(!scx_task_on_sched(sch, p)))
 		return false;
 
+	if (unlikely(READ_ONCE(p->scx.dsq_flags) & SCX_TASK_DSQ_ON_PRIQ)) {
+		scx_error(sch, "vtime modification disallowed while on a priority DSQ");
+		return false;
+	}
+
 	p->scx.dsq_vtime = vtime;
 	return true;
 }
Signature · 1 line
2.48.1
#1 lore raw

Just discuss, if is better to use WARN_ON_ONCE instead of failing the scheduler, just like the check in the beginning of dispatch_enqueue().

#2 lore raw

Hi Zhao,

Quoted 2 lines · Zhao Mengmeng

Just discuss, if is better to use WARN_ON_ONCE instead of failing the scheduler, just like the check in the beginning of dispatch_enqueue().

I think this is more like a misused scheduler API. dispatch_enqueue() uses scx_error() for the same category of errors:
- scx_error(sch, "attempting to dispatch to a destroyed dsq")
- scx_error(sch, "cannot use vtime ordering for built-in DSQs")

That said, I don't have a strong opinion on this. :-)

Signature · 2 lines
Thanks,
Cheng-Yang
reviewer
#3 lore raw
In reply to Cheng-Yang Chou
Quoted 12 lines · Cheng-Yang Chou

scx_bpf_task_set_dsq_vtime() allows modifying a task's dsq_vtime without checking if it is already enqueued on SCX_DSQ_PRIQ. Since dsq_vtime is the rb-tree sorting key, mutating it in-place violates the BST invariant and corrupts the tree structure.

In ops.dispatch():

	p = scx_bpf_dsq_peek(PRIO_DSQ); // Get a task already in the DSQ
	if (p) {
		// This illegally returns %true
		scx_bpf_task_set_dsq_vtime(p, 0xFFFFFFFFFFFFFFFF);
	}
Quoted 3 lines

Fix this by adding a check for the SCX_TASK_DSQ_ON_PRIQ flag. Disallow vtime modification and trigger scx_error() if the task is already queued on a priority DSQ.

If the user updates the vtime after inserting, the tree looks wrong but it won't cause crashes or anything. Later insertions might get confused in terms of ordering but it's a rather obvious user-shotting-their-own-foot, so I'm more inclined to leave it as-is.

Thanks.

Signature · 1 line
tejun
reviewer
#4 lore raw
Quoted 13 lines · Tejun Heo
Quoted 12 lines · Cheng-Yang Chou

scx_bpf_task_set_dsq_vtime() allows modifying a task's dsq_vtime without checking if it is already enqueued on SCX_DSQ_PRIQ. Since dsq_vtime is the rb-tree sorting key, mutating it in-place violates the BST invariant and corrupts the tree structure.

In ops.dispatch():

	p = scx_bpf_dsq_peek(PRIO_DSQ); // Get a task already in the DSQ
	if (p) {
		// This illegally returns %true
		scx_bpf_task_set_dsq_vtime(p, 0xFFFFFFFFFFFFFFFF);
	}
Quoted 8 lines
Quoted 3 lines

Fix this by adding a check for the SCX_TASK_DSQ_ON_PRIQ flag. Disallow vtime modification and trigger scx_error() if the task is already queued on a priority DSQ.

If the user updates the vtime after inserting, the tree looks wrong but it won't cause crashes or anything. Later insertions might get confused in terms of ordering but it's a rather obvious user-shotting-their-own-foot, so I'm more inclined to leave it as-is.

I agree. This looks like intentionally breaking the tree. If users do so, they can keep the pieces. :)

Thanks,
-Andrea

#5 lore raw

Hi Tejun, Andrea,

Quoted 18 lines · Andrea Righi
Quoted 17 lines · Tejun Heo
Quoted 15 lines · Cheng-Yang Chou

scx_bpf_task_set_dsq_vtime() allows modifying a task's dsq_vtime without checking if it is already enqueued on SCX_DSQ_PRIQ. Since dsq_vtime is the rb-tree sorting key, mutating it in-place violates the BST invariant and corrupts the tree structure.

In ops.dispatch():

	p = scx_bpf_dsq_peek(PRIO_DSQ); // Get a task already in the DSQ
	if (p) {
		// This illegally returns %true
		scx_bpf_task_set_dsq_vtime(p, 0xFFFFFFFFFFFFFFFF);
	}

Fix this by adding a check for the SCX_TASK_DSQ_ON_PRIQ flag. Disallow vtime modification and trigger scx_error() if the task is already queued on a priority DSQ.

Quoted 7 lines
Quoted 4 lines

If the user updates the vtime after inserting, the tree looks wrong but it won't cause crashes or anything. Later insertions might get confused in terms of ordering but it's a rather obvious user-shotting-their-own-foot, so I'm more inclined to leave it as-is.

I agree. This looks like intentionally breaking the tree. If users do so, they can keep the pieces. :)

Ah, I see. I was just experimenting with some scheduler API combinations. Indeed, users shouldn't do this if they want their scheduler to work correctly.

Thanks for the explanation!

Signature · 2 lines
Thanks,
Cheng-Yang