linux-kernel - Re: [PATCH] sched: avoid overpull when pulling RT task

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:	Mon, 16 May 2011 21:14:56 +0800
From:	Hillf Danton <dhillf@...il.com>
To:	Mike Galbraith <efault@....de>
Cc:	LKML <linux-kernel@...r.kernel.org>, Ingo Molnar <mingo@...e.hu>,
	Peter Zijlstra <peterz@...radead.org>,
	Yong Zhang <yong.zhang0@...il.com>,
	Thomas Gleixner <tglx@...utronix.de>
Subject: Re: [PATCH] sched: avoid overpull when pulling RT task

On Sun, May 15, 2011 at 2:35 PM, Mike Galbraith <efault@....de> wrote:
> On Sun, 2011-05-15 at 12:35 +0800, Hillf Danton wrote:
>> When pulling RT task for a given runqueue, pulling is continued even
>> after certain RT tasks get pulled, in case there are still higher
>> priority tasks on other runqueues, though it is low likelihood as the
>> comment says. The load of of this runqueue, on other hand, should also
>> be concerned. If it is overloaded, the low likelihood should be
>> abandoned to avoid overpull.
>>
>> Signed-off-by: Hillf Danton <dhillf@...il.com>
>> ---
>>  kernel/sched_rt.c |    5 +++++
>>  1 files changed, 5 insertions(+), 0 deletions(-)
>>
>> diff --git a/kernel/sched_rt.c b/kernel/sched_rt.c
>> index 14c764b..b425ca1 100644
>> --- a/kernel/sched_rt.c
>> +++ b/kernel/sched_rt.c
>> @@ -1508,6 +1508,11 @@ static int pull_rt_task(struct rq *this_rq)
>>               }
>>  skip:
>>               double_unlock_balance(this_rq, src_rq);
>> +
>> +             /* if pulled we have to also avoid overpull */
>> +             if (ret == 1)
>> +                     if (likely(rt_overloaded(this_rq)))
>> +                             break;
>>       }
>>
>>       return ret;
>
> Hm.
>
> It looks to me like you should remove the rt_overloaded() test (and
> function) entirely instead.  If you look at pull usage, the intent is
> that system wide, higher priority tasks run before lower.
>
> I don't think it matters much if we pull too much, since what we pull
> while traversing is ever increasing in priority _and waiting_ anyway.
> We may do a bit more work than strictly necessary on the way to the
> highest priority runnable task, but what matters most is that highest
> priority gets to the CPU first, which testing for overload can stymie.
>
> (seems pulling more than one could turn out either good or bad for any
> but the highest priority task though, lacking crystal ball)
>
Hi Mike

To win the crystal ball, I take another try.

In the following patch, pulling is played in two rounds. In the first round,
the highest priority task is determined with no pull operation. Pulling is
carried out in the second round, and if the highest priority task is pulled,
pulling could be stopped when overload detected, to relieve overpull.

Please review again, thanks.

Hillf
---

--- a/kernel/sched_rt.c	2011-04-27 11:48:50.000000000 +0800
+++ b/kernel/sched_rt.c	2011-05-16 20:42:18.000000000 +0800
@@ -1425,10 +1425,11 @@ static int pull_rt_task(struct rq *this_
 	int this_cpu = this_rq->cpu, ret = 0, cpu;
 	struct task_struct *p;
 	struct rq *src_rq;
+	int highest_prio = MAX_RT_PRIO;
+	int highest_pulled = 0;
+	int first_round = 1;

-	if (likely(!rt_overloaded(this_rq)))
-		return 0;
-
+again:
 	for_each_cpu(cpu, this_rq->rd->rto_mask) {
 		if (this_cpu == cpu)
 			continue;
@@ -1480,6 +1481,18 @@ static int pull_rt_task(struct rq *this_
 			if (p->prio < src_rq->curr->prio)
 				goto skip;

+			/*
+			 * To avoid overpull, we play pulling in two rounds,and
+			 * the highest task is determined in the first round.
+			 */
+			if (first_round) {
+				if (p->prio < highest_prio)
+					highest_prio = p->prio;
+				goto skip;
+			}
+			if (p->prio <= highest_prio)
+				highest_pulled = 1;
+
 			ret = 1;

 			deactivate_task(src_rq, p, 0);
@@ -1494,6 +1507,15 @@ static int pull_rt_task(struct rq *this_
 		}
 skip:
 		double_unlock_balance(this_rq, src_rq);
+
+		if (highest_pulled && rt_overloaded(this_rq))
+			break;
+	}
+
+	if (first_round && highest_prio != MAX_RT_PRIO) {
+		/* try to pull higher tasks on other RQs */
+		first_round = 0;
+		goto again;
 	}

 	return ret;
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/