linux-kernel - Re: [PATCH 00/10] steal tasks to improve CPU utilization

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: <a43db228-ddd0-c30f-6ba0-8d54f17f57c7@arm.com>
Date:   Wed, 24 Oct 2018 16:34:34 +0100
From:   Valentin Schneider <valentin.schneider@....com>
To:     Steven Sistare <steven.sistare@...cle.com>,
        Peter Zijlstra <peterz@...radead.org>
Cc:     mingo@...hat.com, subhra.mazumdar@...cle.com,
        dhaval.giani@...cle.com, daniel.m.jordan@...cle.com,
        pavel.tatashin@...rosoft.com, matt@...eblueprint.co.uk,
        umgwanakikbuti@...il.com, riel@...hat.com, jbacik@...com,
        juri.lelli@...hat.com, linux-kernel@...r.kernel.org
Subject: Re: [PATCH 00/10] steal tasks to improve CPU utilization

Hi,

On 22/10/2018 20:07, Steven Sistare wrote:
> On 10/22/2018 1:04 PM, Peter Zijlstra wrote:
[...]
> 
> We could delete idle_balance() and use stealing exclusively for handling
> new idle.  For each sd level, stealing would look for an overloaded CPU
> in the overloaded bitmap(s) that overlap that level.  I played with that
> a little but it is not ready for prime time, and I did not want to hold
> the patch series for it.  Also, I would like folks to get some production
> experience with stealing on a variety of architectures before considering
> a radical step like replacing idle_balance().
> 

I think this could work fine for standard symmetrical systems, but I have
some concerns for asymmetric systems (Arm big.LITTLE & co). One thing that
should show up in 4.20-rc1 is the misfit logic, which caters to those
asymmetric systems.

If you look at 757ffdd705ee ("sched/fair: Set rq->rd->overload when
misfit") on Linus' tree, we can set rq->rd->overload even if
(rq->nr_running == 1). This is because we do want to do an idle_balance()
when we have misfit tasks, which should lead to active balancing one of
those CPU-hungry tasks to move it to a more powerful CPU.

With a pure try_steal() approach, we won't do any active balancing - we
could steal some task from a cfs_overload_cpu but that's not what the
load balancer would have done. The load balancer would only do such a thing
if the imbalance type is group_overloaded, which means:

  sum_nr_running > group_weight &&
  group_util * sd->imbalance_pct > group_capacity * 100

(IOW the number of tasks running on the CPU is not the sole deciding
factor)

Otherwise, misfit tasks (group_misfit_task imbalance type) would have
priority.

Perhaps we could decorate the cfs_overload_cpus with some more information
(e.g. misfit task presence), but then we'd have to add some logic to decide
when to steal what.

We'd also lose the NOHZ update done in idle_balance(), though I think it's
not such a big deal - were were piggy-backing this on idle_balance() just
because it happened to be convenient, and we still have NOHZ_STATS_KICK
anyway.

Another thing - in your test cases, what is the most prevalent cause of
failure to pull a task in idle_balance()? Is it the load_balance() itself
that fails to find a task (e.g. because the imbalance is not deemed big
enough), or is it the idle migration cost logic that prevents
load_balance() from running to completion?

In the first case, try_steal() makes perfect sense to me. In the second
case, I'm not sure if we really want to pull something if we know (well,
we *think*) we're about to resume the execution of some other task.

> We could merge the stealing code into the idle_balance() code to get a
> union of the two, but IMO that would be less readable.
> 
> We could remove the core and socket levels from idle_balance()

I understand that as only doing load_balance() at DIE level in
idle_balance(), as that is what makes most sense to me (with big.LITTLE
those misfit migrations are done at DIE level), is that correct?

Also, with DynamIQ (next gen big.LITTLE) we could have asymmetry at MC
level, which could cause issues there.

> and let
> stealing handle those levels.  I think that makes sense after stealing
> performance is validated on more architectures, but we would still have
> two different mechanisms.
> 
> - Steve
> 

I'll try out those patches on top of the misfit series to see how the
whole thing behaves.