linux-kernel - Re: [patch 6/8] pull RT tasks

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]

Message-Id: <1193061338.1912.17.camel@localhost.localdomain>
Date:	Mon, 22 Oct 2007 09:55:38 -0400
From:	Steven Rostedt <rostedt@...dmis.org>
To:	Dmitry Adamushko <dmitry.adamushko@...il.com>
Cc:	LKML <linux-kernel@...r.kernel.org>,
	RT <linux-rt-users@...r.kernel.org>,
	Linus Torvalds <torvalds@...ux-foundation.org>,
	Andrew Morton <akpm@...ux-foundation.org>,
	Ingo Molnar <mingo@...e.hu>,
	Thomas Gleixner <tglx@...utronix.de>,
	Gregory Haskins <ghaskins@...ell.com>,
	Peter Zijlstra <a.p.zijlstra@...llo.nl>
Subject: Re: [patch 6/8] pull RT tasks

Hi Dmitry,

On Sun, 2007-10-21 at 11:35 +0200, Dmitry Adamushko wrote:
> Hi Steven,
> 
> > When a pull RT is initiated, all overloaded runqueues are examined for
> > a RT task that is higher in prio than the highest prio task queued on the
> > target runqueue. If another runqueue holds a RT task that is of higher
> > prio than the highest prio task on the target runqueue is found it is pulled
> > to the target runqueue.
> 
> I think, 2 things should be accomplished here :
> 
> (1) be sure to pull the _highest_ prio task ;
> 
> i.e. the _highest_ prio task amongst all runnable (but not running) RT
> tasks across all the run-queues which is capable of running on
> this_cpu ;
> 
> (2) don't pull more than 1 task at once.

I've thought about this, and played a little. The problem we have is
that we don't take locks when searching each run queue. So by the time
you got the "highest rq" to pull from, it may no longer be the highest.
So what do we do in that case? search again?

If we are lucky and pull the highest first, then we will not pull
another one. Since we are not comparing the rq prio to current, but to
the highest task on the current rq.  So once we pull a high prio task,
we only pull another one if we find a even higher prio task.

Yes, it's a little inefficient, and can cause shuffling of task around.
But these tasks haven't actually run yet, so it isn't too much harm. But
the benefit is that when we finish, we have the highest task that can
run on the runqueue.

> 
> that said, just pull the highest prio task and run it.
> 
> ---
> 
> why (2)? Just to avoid situations when tasks are being pulled/pushed
> back and forth between run-queues.
> 
> Let's say we have 4 cpu system:
> 
> 0:  task(10) , task(92)
> 1:  task(10), task(91)
> 2:  task(10), task(90)
> 3:  task(10)
> 
> when task(10) on cpu#3 is inactive, we pull task(92), task(91),
> task(90) and then run task(90)... in the mean time, some of cpu[0..2]
> becomes inactive and pull task(91) and task(92) back and run them...
> that may repeat again and again depending on when/how long task(10)
> run on their corresponding cpus...

I'm not sure that's too much of an issue, since we are just switch tasks
on lists. As long has they haven't run yet, then it shouldn't be too
much harm. We do have a little bit of cache hits in the queues
themselves, but alternatives to fix this would probably cause the same
effects.

> 
> so it seems to me that the more optimal behavior would be "don't pull
> more than you can run at the moment -- that's 1".
> 
> to this goal, something like find_lock_highest_rq() would be necessary.

The problem is that we have too many races to find the highest rq at the
moment. But by pulling the highest at the time, we should end up with
what we want.

> 
> and I guess, {get,put}_task_struct() should be used in pull_rt_task()
> for the 'next' in a similar way as it's done in push_rt_task() .

No, we don't need to do the get task on pull. With push, we start with a
task and we want to push it somewhere. On the double_lock_balance, we
might lose our rq lock. Which means that next could have been put on
another run queue, run to completion, and then exited destroying the
task. We still reference that task after the double_lock_balance, and if
it is not active anymore, we finish the push.

With the pull, we are focusing on the run queue. If we had to release
the rq lock on double_lock_balance, we just pick the highest "next" on
the current run queue (which could have changed) and take the current
task on the src rq, which also could have changed. If the current task
on the src rq is higher in priority we move it over to the dst rq. So no
get/put_task_struct is needed.

-- Steve

-
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/