[PATCH] sched: fix priority leakage in pick_next_highest_task_rt()

[PATCH] sched: fix priority leakage in pick_next_highest_task_rt()

[Hillf Danton]

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;
 		}

Re: [PATCH] sched: fix priority leakage in pick_next_highest_task_rt()

[Yong Zhang]

[-- 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¥

Re: [PATCH] sched: fix priority leakage in pick_next_highest_task_rt()

[Hillf Danton]

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

Re: [PATCH] sched: fix priority leakage in pick_next_highest_task_rt()

[Steven Rostedt]

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

Re: [PATCH] sched: fix priority leakage in pick_next_highest_task_rt()

[Yong Zhang]

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

Re: [PATCH] sched: fix priority leakage in pick_next_highest_task_rt()

[Yong Zhang]

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