linux-kernel - Re: [PATCH v2 6/6] sched: create "pushable_tasks" list to limit pushing to one attempt

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:	Fri, 29 Aug 2008 09:24:07 -0400
From:	Gregory Haskins <ghaskins@...ell.com>
To:	mingo@...e.hu
CC:	srostedt@...hat.com, peterz@...radead.org,
	linux-kernel@...r.kernel.org, linux-rt-users@...r.kernel.org,
	npiggin@...e.de, gregory.haskins@...il.com
Subject: Re: [PATCH v2 6/6] sched: create "pushable_tasks" list to limit pushing
 to one attempt

Hi Ingo,

Gregory Haskins wrote:
> The RT scheduler employs a "push/pull" design to actively balance tasks
> within the system (on a per disjoint cpuset basis).  When a task is
> awoken, it is immediately determined if there are any lower priority
> cpus which should be preempted.  This is opposed to the way normal
> SCHED_OTHER tasks behave, which will wait for a periodic rebalancing
> operation to occur before spreading out load.
>
> When a particular RQ has more than 1 active RT task, it is said to
> be in an "overloaded" state.  Once this occurs, the system enters
> the active balancing mode, where it will try to push the task away,
> or persuade a different cpu to pull it over.  The system will stay
> in this state until the system falls back below the <= 1 queued RT
> task per RQ.
>
> However, the current implementation suffers from a limitation in the
> push logic.  Once overloaded, all tasks (other than current) on the
> RQ are analyzed on every push operation, even if it was previously
> unpushable (due to affinity, etc).  Whats more, the operation stops
> at the first task that is unpushable and will not look at items
> lower in the queue.  This causes two problems:
>
> 1) We can have the same tasks analyzed over and over again during each
>    push, which extends out the fast path in the scheduler for no
>    gain.  Consider a RQ that has dozens of tasks that are bound to a
>    core.  Each one of those tasks will be encountered and skipped
>    for each push operation while they are queued.
>
> 2) There may be lower-priority tasks under the unpushable task that
>    could have been successfully pushed, but will never be considered
>    until either the unpushable task is cleared, or a pull operation
>    succeeds.  The net result is a potential latency source for mid
>    priority tasks.
>
> This patch aims to rectify these two conditions by introducing a new
> priority sorted list: "pushable_tasks".  A task is added to the list
> each time a task is activated or preempted.  It is removed from the
> list any time it is deactivated, made current, or fails to push.
>
> This works because a task only needs to be attempted to push once.
> After an initial failure to push, the other cpus will eventually try to
> pull the task when the conditions are proper.  This also solves the
> problem that we don't completely analyze all tasks due to encountering
> an unpushable tasks.  Now every task will have a push attempted (when
> appropriate).
>
> This reduces latency both by shorting the critical section of the
> rq->lock for certain workloads, and by making sure the algorithm
> considers all eligible tasks in the system.
>
> Signed-off-by: Gregory Haskins <ghaskins@...ell.com>
> CC: Steven Rostedt <srostedt@...hat.com>
>   

We have found a crash bug in this patch in our lab caused by this
patch.  So if you had any plans to pull this series in, please skip this
last patch for now (6/6).  I will send out a refresh after I fix the issue.

Thanks,
-Greg



Download attachment "signature.asc" of type "application/pgp-signature" (258 bytes)