* [PATCH] sched: fix priority leakage in pick_next_highest_task_rt()
@ 2011-05-16 12:55 Hillf Danton
2011-05-17 2:28 ` Yong Zhang
0 siblings, 1 reply; 6+ messages in thread
From: Hillf Danton @ 2011-05-16 12:55 UTC (permalink / raw)
To: LKML; +Cc: Ingo Molnar, Peter Zijlstra, Mike Galbraith, Yong Zhang
When picking the second highest RT task for a given runqueue, if no
task found after scanning the queue of priority == idx, the next idx
should also be checked even in case that next is already existing, or
the window of priority leakage could be opened.
Signed-off-by: Hillf Danton <dhillf@gmail.com>
---
--- a/kernel/sched_rt.c 2011-04-27 11:48:50.000000000 +0800
+++ b/kernel/sched_rt.c 2011-05-16 19:58:42.000000000 +0800
@@ -1166,6 +1166,8 @@ static struct task_struct *pick_next_hig
int idx;
for_each_leaf_rt_rq(rt_rq, rq) {
+ struct task_struct *this;
+
array = &rt_rq->active;
idx = sched_find_first_bit(array->bitmap);
next_idx:
@@ -1173,6 +1175,7 @@ next_idx:
continue;
if (next && next->prio < idx)
continue;
+ this = NULL;
list_for_each_entry(rt_se, array->queue + idx, run_list) {
struct task_struct *p;
@@ -1181,11 +1184,15 @@ next_idx:
p = rt_task_of(rt_se);
if (pick_rt_task(rq, p, cpu)) {
- next = p;
+ this = p;
break;
}
}
- if (!next) {
+ if (this != NULL)
+ next = this;
+ else { /*
+ * we have to check next idx even if next != NULL
+ */
idx = find_next_bit(array->bitmap, MAX_RT_PRIO, idx+1);
goto next_idx;
}
^ permalink raw reply [flat|nested] 6+ messages in thread* Re: [PATCH] sched: fix priority leakage in pick_next_highest_task_rt() 2011-05-16 12:55 [PATCH] sched: fix priority leakage in pick_next_highest_task_rt() Hillf Danton @ 2011-05-17 2:28 ` Yong Zhang 2011-05-17 14:53 ` Hillf Danton 0 siblings, 1 reply; 6+ messages in thread From: Yong Zhang @ 2011-05-17 2:28 UTC (permalink / raw) To: Hillf Danton; +Cc: LKML, Ingo Molnar, Peter Zijlstra, Mike Galbraith [-- Warning: decoded text below may be mangled, UTF-8 assumed --] [-- Attachment #1: Type: text/plain; charset=UTF-8, Size: 2398 bytes --] On Mon, May 16, 2011 at 8:55 PM, Hillf Danton <dhillf@gmail.com> wrote: > When picking the second highest RT task for a given runqueue, if no > task found after scanning the queue of priority == idx, the next idx > should also be checked even in case that next is already existing, or > the window of priority leakage could be opened. I don't see what kind of problem you patch will fix. And mind explaining how priority leakage could happen? Thanks, Yong > > Signed-off-by: Hillf Danton <dhillf@gmail.com> > --- > > --- a/kernel/sched_rt.c 2011-04-27 11:48:50.000000000 +0800 > +++ b/kernel/sched_rt.c 2011-05-16 19:58:42.000000000 +0800 > @@ -1166,6 +1166,8 @@ static struct task_struct *pick_next_hig >     int idx; > >     for_each_leaf_rt_rq(rt_rq, rq) { > +        struct task_struct *this; > + >         array = &rt_rq->active; >         idx = sched_find_first_bit(array->bitmap); >  next_idx: > @@ -1173,6 +1175,7 @@ next_idx: >             continue; >         if (next && next->prio < idx) >             continue; > +        this = NULL; >         list_for_each_entry(rt_se, array->queue + idx, run_list) { >             struct task_struct *p; > > @@ -1181,11 +1184,15 @@ next_idx: > >             p = rt_task_of(rt_se); >             if (pick_rt_task(rq, p, cpu)) { > -                next = p; > +                this = p; >                 break; >             } >         } > -        if (!next) { > +        if (this != NULL) > +            next = this; > +        else {  /* > +             * we have to check next idx even if next != NULL > +             */ >             idx = find_next_bit(array->bitmap, MAX_RT_PRIO, idx+1); >             goto next_idx; >         } > -- Only stand for myself ÿôèº{.nÇ+‰·Ÿ®‰†+%ŠËÿ±éݶ\x17¥Šwÿº{.nÇ+‰·¥Š{±þG«éÿŠ{ayº\x1dʇڙë,j\a¢f£¢·hšïêÿ‘êçz_è®\x03(階ŠÝ¢j"ú\x1a¶^[m§ÿÿ¾\a«þG«éÿ¢¸?™¨èÚ&£ø§~á¶iO•æ¬z·švØ^\x14\x04\x1a¶^[m§ÿÿÃ\fÿ¶ìÿ¢¸?–I¥ ^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH] sched: fix priority leakage in pick_next_highest_task_rt() 2011-05-17 2:28 ` Yong Zhang @ 2011-05-17 14:53 ` Hillf Danton 2011-05-18 1:14 ` Steven Rostedt 2011-05-18 2:07 ` Yong Zhang 0 siblings, 2 replies; 6+ messages in thread From: Hillf Danton @ 2011-05-17 14:53 UTC (permalink / raw) To: Yong Zhang; +Cc: LKML, Ingo Molnar, Peter Zijlstra, Mike Galbraith On Tue, May 17, 2011 at 10:28 AM, Yong Zhang <yong.zhang0@gmail.com> wrote: > On Mon, May 16, 2011 at 8:55 PM, Hillf Danton <dhillf@gmail.com> wrote: >> When picking the second highest RT task for a given runqueue, if no >> task found after scanning the queue of priority == idx, the next idx >> should also be checked even in case that next is already existing, or >> the window of priority leakage could be opened. > > I don't see what kind of problem you patch will fix. > And mind explaining how priority leakage could happen? > Hi Yong If no task is found after scanning the list at array->queue + idx, what should we operate on next? And why is the list scanned? thanks Hillf ^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH] sched: fix priority leakage in pick_next_highest_task_rt() 2011-05-17 14:53 ` Hillf Danton @ 2011-05-18 1:14 ` Steven Rostedt 2011-05-18 2:17 ` Yong Zhang 2011-05-18 2:07 ` Yong Zhang 1 sibling, 1 reply; 6+ messages in thread From: Steven Rostedt @ 2011-05-18 1:14 UTC (permalink / raw) To: Hillf Danton Cc: Yong Zhang, LKML, Ingo Molnar, Peter Zijlstra, Mike Galbraith On Tue, May 17, 2011 at 10:53:22PM +0800, Hillf Danton wrote: > On Tue, May 17, 2011 at 10:28 AM, Yong Zhang <yong.zhang0@gmail.com> wrote: > > On Mon, May 16, 2011 at 8:55 PM, Hillf Danton <dhillf@gmail.com> wrote: > >> When picking the second highest RT task for a given runqueue, if no > >> task found after scanning the queue of priority == idx, the next idx > >> should also be checked even in case that next is already existing, or > >> the window of priority leakage could be opened. > > > > I don't see what kind of problem you patch will fix. > > And mind explaining how priority leakage could happen? > > > Hi Yong > > If no task is found after scanning the list at array->queue + idx, > what should we operate on next? > And why is the list scanned? > The patch looks correct. The code looks like so: for_each_leaf_rt_rq(rt_rq, rq) { array = &rt_rq->active; idx = sched_find_first_bit(array->bitmap); next_idx: if (idx >= MAX_RT_PRIO) continue; if (next && next->prio < idx) continue; list_for_each_entry(rt_se, array->queue + idx, run_list) { struct task_struct *p; if (!rt_entity_is_task(rt_se)) continue; p = rt_task_of(rt_se); if (pick_rt_task(rq, p, cpu)) { next = p; break; } } if (!next) { idx = find_next_bit(array->bitmap, MAX_RT_PRIO, idx+1); goto next_idx; } } What we are doing is looking for the next highest prio task that we can migrate. When we find the next highest priority task that can migrate, we pick it. But the issue comes with the cgroups. If we are looping through the cgroups, and we pick a task in one cgroup, but when we check the next cgroup, if it has a higher priority task, but that task can't migrate, but the next one, also of higher priority, can, that "if (!next)" wont catch it. Although, I don't know the cgroup code very well, and I wonder what it means to pull a task from a run queue onto another run queue that has dropped in priority. But, anyway, for the patch: Acked-by: Steven Rostedt <rostedt@goodmis.org> -- Steve ^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH] sched: fix priority leakage in pick_next_highest_task_rt() 2011-05-18 1:14 ` Steven Rostedt @ 2011-05-18 2:17 ` Yong Zhang 0 siblings, 0 replies; 6+ messages in thread From: Yong Zhang @ 2011-05-18 2:17 UTC (permalink / raw) To: Steven Rostedt Cc: Hillf Danton, LKML, Ingo Molnar, Peter Zijlstra, Mike Galbraith On Wed, May 18, 2011 at 9:14 AM, Steven Rostedt <rostedt@goodmis.org> wrote: > On Tue, May 17, 2011 at 10:53:22PM +0800, Hillf Danton wrote: >> On Tue, May 17, 2011 at 10:28 AM, Yong Zhang <yong.zhang0@gmail.com> wrote: >> > On Mon, May 16, 2011 at 8:55 PM, Hillf Danton <dhillf@gmail.com> wrote: >> >> When picking the second highest RT task for a given runqueue, if no >> >> task found after scanning the queue of priority == idx, the next idx >> >> should also be checked even in case that next is already existing, or >> >> the window of priority leakage could be opened. >> > >> > I don't see what kind of problem you patch will fix. >> > And mind explaining how priority leakage could happen? >> > >> Hi Yong >> >> If no task is found after scanning the list at array->queue + idx, >> what should we operate on next? >> And why is the list scanned? >> > > The patch looks correct. > > The code looks like so: > > for_each_leaf_rt_rq(rt_rq, rq) { > array = &rt_rq->active; > idx = sched_find_first_bit(array->bitmap); > next_idx: > if (idx >= MAX_RT_PRIO) > continue; > if (next && next->prio < idx) > continue; > list_for_each_entry(rt_se, array->queue + idx, run_list) { > struct task_struct *p; > > if (!rt_entity_is_task(rt_se)) > continue; > > p = rt_task_of(rt_se); > if (pick_rt_task(rq, p, cpu)) { > next = p; > break; > } > } > if (!next) { > idx = find_next_bit(array->bitmap, MAX_RT_PRIO, idx+1); > goto next_idx; > } > } > > What we are doing is looking for the next highest prio task that we can > migrate. When we find the next highest priority task that can migrate, > we pick it. But the issue comes with the cgroups. If we are looping > through the cgroups, and we pick a task in one cgroup, but when we check > the next cgroup, if it has a higher priority task, but that task can't > migrate, but the next one, also of higher priority, can, that "if (!next)" > wont catch it. Yup, I misread the patch at the first time. Now I think Hillf's patch is correct. Thanks for your explanation Steven. Thanks, Yong > > Although, I don't know the cgroup code very well, and I wonder what it > means to pull a task from a run queue onto another run queue that has > dropped in priority. > > But, anyway, for the patch: > > Acked-by: Steven Rostedt <rostedt@goodmis.org> > > -- Steve > > -- Only stand for myself ^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH] sched: fix priority leakage in pick_next_highest_task_rt() 2011-05-17 14:53 ` Hillf Danton 2011-05-18 1:14 ` Steven Rostedt @ 2011-05-18 2:07 ` Yong Zhang 1 sibling, 0 replies; 6+ messages in thread From: Yong Zhang @ 2011-05-18 2:07 UTC (permalink / raw) To: Hillf Danton; +Cc: LKML, Ingo Molnar, Peter Zijlstra, Mike Galbraith On Tue, May 17, 2011 at 10:53 PM, Hillf Danton <dhillf@gmail.com> wrote: > On Tue, May 17, 2011 at 10:28 AM, Yong Zhang <yong.zhang0@gmail.com> wrote: >> On Mon, May 16, 2011 at 8:55 PM, Hillf Danton <dhillf@gmail.com> wrote: >>> When picking the second highest RT task for a given runqueue, if no >>> task found after scanning the queue of priority == idx, the next idx >>> should also be checked even in case that next is already existing, or >>> the window of priority leakage could be opened. >> >> I don't see what kind of problem you patch will fix. >> And mind explaining how priority leakage could happen? >> > Hi Yong > > If no task is found after scanning the list at array->queue + idx, > what should we operate on next? > And why is the list scanned? Hmmm, I get your point. Reviewed-by: Yong Zhang <yong.zhang0@gmail.com> Thanks, Yong -- Only stand for myself ^ permalink raw reply [flat|nested] 6+ messages in thread
end of thread, other threads:[~2011-05-18 2:17 UTC | newest] Thread overview: 6+ messages (download: mbox.gz follow: Atom feed -- links below jump to the message on this page -- 2011-05-16 12:55 [PATCH] sched: fix priority leakage in pick_next_highest_task_rt() Hillf Danton 2011-05-17 2:28 ` Yong Zhang 2011-05-17 14:53 ` Hillf Danton 2011-05-18 1:14 ` Steven Rostedt 2011-05-18 2:17 ` Yong Zhang 2011-05-18 2:07 ` Yong Zhang
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for NNTP newsgroup(s).