linux-kernel.vger.kernel.org archive mirror
 help / color / mirror / Atom feed
From: Steven Sistare <steven.sistare@oracle.com>
To: Valentin Schneider <valentin.schneider@arm.com>,
	mingo@redhat.com, peterz@infradead.org
Cc: subhra.mazumdar@oracle.com, dhaval.giani@oracle.com,
	daniel.m.jordan@oracle.com, pavel.tatashin@microsoft.com,
	matt@codeblueprint.co.uk, umgwanakikbuti@gmail.com,
	riel@redhat.com, jbacik@fb.com, juri.lelli@redhat.com,
	vincent.guittot@linaro.org, quentin.perret@arm.com,
	linux-kernel@vger.kernel.org
Subject: Re: [PATCH v3 03/10] sched/topology: Provide cfs_overload_cpus bitmap
Date: Mon, 19 Nov 2018 12:33:45 -0500	[thread overview]
Message-ID: <0857925d-a24e-90ea-e28c-90d69b2f66dd@oracle.com> (raw)
In-Reply-To: <de2d2824-d66e-8852-d67a-d58b478b74c1@arm.com>

On 11/12/2018 11:42 AM, Valentin Schneider wrote:
> Hi Steve,
> 
> On 09/11/2018 12:50, Steve Sistare wrote:
>> From: Steve Sistare <steve.sistare@oracle.com>
>>
>> Define and initialize a sparse bitmap of overloaded CPUs, per
>> last-level-cache scheduling domain, for use by the CFS scheduling class.
>> Save a pointer to cfs_overload_cpus in the rq for efficient access.
>>
>> Signed-off-by: Steve Sistare <steven.sistare@oracle.com>
>> ---
>>  include/linux/sched/topology.h |  1 +
>>  kernel/sched/sched.h           |  2 ++
>>  kernel/sched/topology.c        | 21 +++++++++++++++++++--
>>  3 files changed, 22 insertions(+), 2 deletions(-)
>>
>> diff --git a/include/linux/sched/topology.h b/include/linux/sched/topology.h
>> index 6b99761..b173a77 100644
>> --- a/include/linux/sched/topology.h
>> +++ b/include/linux/sched/topology.h
>> @@ -72,6 +72,7 @@ struct sched_domain_shared {
>>  	atomic_t	ref;
>>  	atomic_t	nr_busy_cpus;
>>  	int		has_idle_cores;
>> +	struct sparsemask *cfs_overload_cpus;
> 
> Thinking about misfit stealing, we can't use the sd_llc_shared's because
> on big.LITTLE misfit migrations happen across LLC domains.
> 
> I was thinking of adding a misfit sparsemask to the root_domain, but
> then I thought we could do the same thing for cfs_overload_cpus.
> 
> By doing so we'd have a single source of information for overloaded CPUs,
> and we could filter that down during idle balance - you mentioned earlier
> wanting to try stealing at each SD level. This would also let you get
> rid of [PATCH 02].
> 
> The main part of try_steal() could then be written down as something like
> this:
> 
> ----->8-----
> 
> for_each_domain(this_cpu, sd) {
> 	span = sched_domain_span(sd)
> 		
> 	for_each_sparse_wrap(src_cpu, overload_cpus) {
> 		if (cpumask_test_cpu(src_cpu, span) &&
> 		    steal_from(dts_rq, dst_rf, &locked, src_cpu)) {
> 			stolen = 1;
> 			goto out;
> 		}
> 	}
> }
> 
> ------8<-----
> 
> We could limit the stealing to stop at the highest SD_SHARE_PKG_RESOURCES
> domain for now so there would be no behavioural change - but we'd
> factorize the #ifdef SCHED_SMT bit. Furthermore, the door would be open
> to further stealing.
> 
> What do you think?

That is not efficient for a multi-level search because at each domain level we 
would (re) iterate over overloaded candidates that do not belong in that level.
To extend stealing across LLC, I would like to keep the per-LLC sparsemask, 
but add to each SD a list of sparsemask pointers.  The list nodes would be
private, but the sparsemask structs would be shared.  Each list would include
the masks that overlap the SD's members.  The list would be a singleton at the
core and LLC levels (same as the socket level for most processors), and would 
have multiple elements at the NUMA level.

- Steve


  reply	other threads:[~2018-11-19 17:34 UTC|newest]

Thread overview: 30+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2018-11-09 12:50 [PATCH v3 00/10] steal tasks to improve CPU utilization Steve Sistare
2018-11-09 12:50 ` [PATCH v3 01/10] sched: Provide sparsemask, a reduced contention bitmap Steve Sistare
2018-11-27 15:16   ` Steven Sistare
2018-11-28  1:19     ` Omar Sandoval
2018-12-06 16:07       ` Steven Sistare
2018-12-06 18:19         ` Omar Sandoval
2018-11-09 12:50 ` [PATCH v3 02/10] sched/topology: Provide hooks to allocate data shared per LLC Steve Sistare
2018-11-09 12:50 ` [PATCH v3 03/10] sched/topology: Provide cfs_overload_cpus bitmap Steve Sistare
2018-11-09 17:38   ` Valentin Schneider
2018-11-19 17:32     ` Steven Sistare
2018-11-20 12:52       ` Valentin Schneider
2018-11-12 16:42   ` Valentin Schneider
2018-11-19 17:33     ` Steven Sistare [this message]
2018-11-20 12:42       ` Valentin Schneider
2018-11-26 19:06         ` Steven Sistare
2018-12-03 16:56           ` Valentin Schneider
2018-12-06 16:40             ` Steven Sistare
2018-12-06 17:28               ` Valentin Schneider
2018-11-09 12:50 ` [PATCH v3 04/10] sched/fair: Dynamically update cfs_overload_cpus Steve Sistare
2018-11-09 12:50 ` [PATCH v3 05/10] sched/fair: Hoist idle_stamp up from idle_balance Steve Sistare
2018-11-09 19:07   ` Valentin Schneider
2018-11-19 17:31     ` Steven Sistare
2018-11-20 10:24       ` Valentin Schneider
2018-11-09 12:50 ` [PATCH v3 06/10] sched/fair: Generalize the detach_task interface Steve Sistare
2018-11-09 12:50 ` [PATCH v3 07/10] sched/fair: Provide can_migrate_task_llc Steve Sistare
2018-11-09 12:50 ` [PATCH v3 08/10] sched/fair: Steal work from an overloaded CPU when CPU goes idle Steve Sistare
2018-11-09 12:50 ` [PATCH v3 09/10] sched/fair: disable stealing if too many NUMA nodes Steve Sistare
2018-11-09 12:50 ` [PATCH v3 10/10] sched/fair: Provide idle search schedstats Steve Sistare
2018-11-10 17:08   ` kbuild test robot
2018-11-09 15:02 ` hackbench run scripts Steven Sistare

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=0857925d-a24e-90ea-e28c-90d69b2f66dd@oracle.com \
    --to=steven.sistare@oracle.com \
    --cc=daniel.m.jordan@oracle.com \
    --cc=dhaval.giani@oracle.com \
    --cc=jbacik@fb.com \
    --cc=juri.lelli@redhat.com \
    --cc=linux-kernel@vger.kernel.org \
    --cc=matt@codeblueprint.co.uk \
    --cc=mingo@redhat.com \
    --cc=pavel.tatashin@microsoft.com \
    --cc=peterz@infradead.org \
    --cc=quentin.perret@arm.com \
    --cc=riel@redhat.com \
    --cc=subhra.mazumdar@oracle.com \
    --cc=umgwanakikbuti@gmail.com \
    --cc=valentin.schneider@arm.com \
    --cc=vincent.guittot@linaro.org \
    --subject='Re: [PATCH v3 03/10] sched/topology: Provide cfs_overload_cpus bitmap' \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).