sched_ext: Prevent RB-tree corruption in scx_bpf_task_set_dsq_vtime()
Subsystems (3)
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.
--- kernel/sched/ext.c | 8 +++++++- 1 file changed, 7 insertions(+), 1 deletion(-)
kernel/sched/ext.c +7 -1
@@ -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
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().
Hi Zhao,
Quoted 2 lines · Zhao Mengmeng
Just discuss, if is better to use
WARN_ON_ONCEinstead of failing the scheduler, just like the check in the beginning ofdispatch_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
Tejun Heo
reviewerQuoted 12 lines · Cheng-Yang Chou
scx_bpf_task_set_dsq_vtime()allows modifying a task'sdsq_vtimewithout checking if it is already enqueued onSCX_DSQ_PRIQ. Sincedsq_vtimeis 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_PRIQflag. Disallow vtime modification and triggerscx_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
Andrea Righi
reviewerQuoted 13 lines · Tejun Heo
Quoted 12 lines · Cheng-Yang Chou
scx_bpf_task_set_dsq_vtime()allows modifying a task'sdsq_vtimewithout checking if it is already enqueued onSCX_DSQ_PRIQ. Sincedsq_vtimeis 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_PRIQflag. Disallow vtime modification and triggerscx_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
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'sdsq_vtimewithout checking if it is already enqueued onSCX_DSQ_PRIQ. Sincedsq_vtimeis 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_PRIQflag. Disallow vtime modification and triggerscx_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