linux-kernel - Re: [RFC][PATCH]: sched/fair: search a task from the tail of the queue

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: <20170824174615.pcgw5mylr67nyigi@hirez.programming.kicks-ass.net>
Date:   Thu, 24 Aug 2017 19:46:15 +0200
From:   Peter Zijlstra <peterz@...radead.org>
To:     "Uladzislau Rezki (Sony)" <urezki@...il.com>
Cc:     LKML <linux-kernel@...r.kernel.org>,
        Ingo Molnar <mingo@...hat.com>, Mike Galbraith <efault@....de>,
        Oleksiy Avramchenko <oleksiy.avramchenko@...ymobile.com>,
        Paul Turner <pjt@...gle.com>, Oleg Nesterov <oleg@...hat.com>,
        Steven Rostedt <rostedt@...dmis.org>,
        Mike Galbraith <umgwanakikbuti@...il.com>,
        Kirill Tkhai <tkhai@...dex.ru>,
        Tim Chen <tim.c.chen@...ux.intel.com>,
        Nicolas Pitre <nicolas.pitre@...aro.org>
Subject: Re: [RFC][PATCH]: sched/fair: search a task from the tail of the
 queue

On Thu, Aug 24, 2017 at 12:44:45PM +0200, Uladzislau Rezki (Sony) wrote:
> From: Uladzislau Rezki <urezki@...il.com>
> 
> When a task is enqueued back from a physical CPU to the running
> list it is placed in the beginning of the queue. Thus, the cfs_tasks
> list is more or less sorted (except woken tasks) starting from recently
> given CPU time tasks toward tasks with max wait time in a run-queue.

Hurm... that is only true for short running tasks, the moment you get
things like involuntary preemption that's completely off.

Imagine starting 3 busy-spinning tasks, lets call then A, B and C.

So our cfs_tasks list is ordered: C B A, since C is the last task we
started.

At this point, C might also be the leftmost task, since it has ran
least. But the moment we let A run its full quantum it will become the
rightmost and we'll pick C. Let C run its full quantum and that becomes
the rightmost.

So now we have, in our tree: B A C, while our list is still C B A. No
relation left what so ever.

How, hackbench will be very short running tasks, so the list tends to be
better ordered vs the tree.

That said, functionally it really doesn't matter what way around the
list we iterate for migration, so if this is a win for some, that's
nice. But it would be nice to get more benchmarks ran to see if there is
cases where it hurts.

Another thing you could play with is making pick_next_task_fair() move
the selected task to the front of the list. That way the list becomes a
MRU and picking from the tail always makes sense.