On 2/1/2018 7:33 AM, Peter Zijlstra wrote:
> On Mon, Jan 29, 2018 at 03:31:02PM -0800, subhra mazumdar wrote:
>> +#ifdef CONFIG_SCHED_SMT
>> +
>> +/*
>> + * From sd_llc downward update the SMT utilization.
>
> Please don't use utilization for this, we already use that word for
> something else.
>
>> + * Skip the lowest level 0.
>> + */
>> +void smt_util(struct rq *rq, int prev_busy, int next_busy)
>> +{
>> + struct sched_domain *sd;
>> + struct sched_group *sg_cpu;
>> + int this_cpu = rq->cpu;
>> + int util;
>> +
>> + if (rq->curr_util == UTIL_UNINITIALIZED)
>> + prev_busy = 0;
>> +
>> + util = next_busy - prev_busy;
>> + rcu_read_lock();
>> + sd = rcu_dereference(per_cpu(sd_llc, this_cpu));
>> + if (util) {
>> + for_each_lower_domain(sd) {
>> + if (sd->level == 0)
>> + break;
>
> afaict you really only need this for the core, and here you're assuming
> everything below the LLC is cores. Would it not be much clearer if you
> introduce sd_core.
>
> As is, for_each_lower_domain includes the starting domain, sd->group
> then is the first core group for this cpu. But then you continue to the
> smt domain (on Intel, on other architectures there could be a cluster
> domain in between) and then you bail using that sd->level == 0 hack
> because otherwise things would go *bang*.
Hi Peter,
The code here and in smt_balance intentionally visits each level between
the llc and smt, including core-cluster on architectures that define it.
smt_balance thus has the chance to randomly pick a better cluster,
and then within that cluster randomly pick a better core. It makes sense,
as resources are shared within a cluster, and choosing a less loaded cluster
should give better performance. As you suggest in a few other places,
it would be nice to see performance results for this case. We have
SPARC processors with core clusters.
> Really rather messy this.
>
> I think you want to go allocate sched_domain_shared for the MC level and
> use that, much like sd_llc_shared.
>
>> + sg_cpu = sd->groups;
>> +
>> + /* atomically add/subtract the util */
>> + if (util > 0)
>> + atomic_inc((atomic_t *)&sg_cpu->utilization);
>> + else
>> + atomic_dec((atomic_t *)&sg_cpu->utilization);
>
> *sigh*, wth do you need that cast? You didn't get the memo that spurious
> casts are where bugs happen and are terrible style at the best of times?
>
>> + }
>> + }
>> +
>> + if (sd)
>> + rq->curr_util = next_busy;
>> + rcu_read_unlock();
>> +}
>
>> + smt_util(rq, 1, 0);
>
>> + smt_util(rq, 0, 1);
>
> That all seems like an overly complex way to write inc/dec. You turned
> what should be a boolean state space (2^1) into something like 2^64.
>
> Also, I think if you count idle instead of busy, you'll do away with the
> need for that whole uninitialized thing.
>
>
>> +#define CPU_PSEUDO_RANDOM(cpu) (cpu_rq(cpu)->rotor++)
>
> That's a bit of a stretch calling that pseudo random..
>
>> +/*
>> + * Find an idle cpu in the core starting search from random index.
>> + */
>> +static int select_idle_smt(struct task_struct *p, struct sched_group *sg)
>> {
>> + int i, rand_index, rand_cpu;
>> + int this_cpu = smp_processor_id();
>>
>> + rand_index = CPU_PSEUDO_RANDOM(this_cpu) % sg->group_weight;
>> + rand_cpu = sg->cp_array[rand_index];
>
> Right, so yuck.. I know why you need that, but that extra array and
> dereference is the reason I never went there.
>
> How much difference does it really make vs the 'normal' wrapping search
> from last CPU ?
>
> This really should be a separate patch with separate performance numbers
> on.
For the benefit of other readers, if we always search and choose starting from
the first CPU in a core, then later searches will often need to traverse the
first
N busy CPU's to find the first idle CPU. Choosing a random starting point
avoids
such bias. It is probably a win for processors with 4 to 8 CPUs per core, and
a slight but hopefully negligible loss for 2 CPUs per core, and I agree we need
to see performance data for this as a separate patch to decide. We have SPARC
systems with 8 CPUs per core.
>> + for_each_cpu_wrap(i, sched_group_span(sg), rand_cpu) {
>> + if (!cpumask_test_cpu(i, &p->cpus_allowed))
>> + continue;
>> + if (idle_cpu(i))
>> + return i;
>> + }
>>
>> + return -1;
>> }
>>
>> /*
>> + * Compare the SMT utilization of the two groups and select the one which
>> + * has more capacity left.
>> */
>> +static int smt_should_migrate(struct sched_group *here,
>> + struct sched_group *there, int self_util)
>> {
>> + int this_cpu = smp_processor_id();
>> + int here_util = here->utilization, there_util = there->utilization;
>>
>> + /* Discount self utilization if it belongs to here or there */
>> + if (self_util > 0) {
>> + if (cpumask_test_cpu(this_cpu, sched_group_span(here)))
>> + here_util -= self_util;
>> + else if (cpumask_test_cpu(this_cpu, sched_group_span(there)))
>> + there_util -= self_util;
>> }
>>
>> + /* Return true if other group has more capacity left */
>> + return (there->group_weight - there_util >
>> + here->group_weight - here_util);
>> }
>
> OK, so this effectively picks the least-busiest/idlest SMT sibling of
> two.
>
>> /*
>> + * SMT balancing works by comparing the target cpu group with a random group
>> + * in llc domain. It calls smt_should_migrate to decide which group has more
>> + * capacity left. The balancing starts top down fom sd_llc to SMT core
>> level.
>> + * Finally idle cpu search is only done in the core.
>> */
>> +static int smt_balance(struct task_struct *p, struct sched_domain *sd, int
>> cpu)
>> {
>> + struct sched_group *sg, *src_sg, *start_sg, *tgt_sg;
>> + struct cpumask *span;
>> + int rand_idx, weight;
>> + int cpu_orig = cpu;
>> + int rand_cpu;
>> + int this_cpu = smp_processor_id();
>> + struct rq *this_rq = cpu_rq(this_cpu);
>> + struct rq *rq = cpu_rq(cpu);
>> + int self_util = 0;
>> + int balanced = 0;
>>
>> + if (p == this_rq->curr)
>> + self_util = rq->curr_util;
>>
>> + for_each_lower_domain(sd) {
>
> Again, I don't think we want to do that. You want to iterate all cores,
> and this is a rather cumbersome way to go about doing that.
>
> Esp. if there's a domain in between. Imagine an ARM bit.little with
> shared L3 growing SMT or something along those lines.
>
>> + if (sd->level == 0)
>> + break;
>>
>> + /* Pick a random group that has cpus where the thread can run */
>> + src_sg = sd->groups;
>> + tgt_sg = NULL;
>> + rand_idx = CPU_PSEUDO_RANDOM(this_cpu) % sd->sg_num;
>> + start_sg = sd->sg_array[rand_idx];
>
>> + sg = start_sg;
>> + do {
>> + span = sched_group_span(sg);
>> + if (sg != src_sg &&
>> + cpumask_intersects(span, &p->cpus_allowed)) {
>> + tgt_sg = sg;
>> + break;
>> + }
>> + sg = sg->next;
>> + } while (sg != start_sg);
>
> OK, so this picks a 'random' group that has CPUs where our task is
> allowed to run (per the above this group could be a cluster, not a
> core).
>
>> + /*
>> + * Compare the target group with random group and select the
>> + * one which has more SMT capacity left. Choose a random CPU in
>> + * the group to spread the load, then find the group's parent sd
>> + * so the group's sd is used on the next main loop iteration.
>> + */
>> + if (tgt_sg && smt_should_migrate(src_sg, tgt_sg, self_util)) {
>> + weight = tgt_sg->group_weight;
>> + rand_idx = CPU_PSEUDO_RANDOM(this_cpu) % weight;
>> + rand_cpu = tgt_sg->cp_array[rand_idx];
>> + for_each_cpu_wrap(cpu, span, rand_cpu) {
>> + if (cpumask_test_cpu(cpu, &p->cpus_allowed))
>> + break;
>> + }
>> + for_each_domain(cpu, sd) {
>> + if (weight < sd->span_weight)
>> + break;
>> + }
>> + balanced = 1;
>> }
>
> I really wonder how much that fake random stuff yields you vs the rest
> of this.
>
> In any case, this will not do for facebook I'm afraid, as is they
> already disable SIS_AVG_CPU and SIS_PROP (iirc) and always take the hit
> of doing a full LLC search.
>
> Yes that is expensive, but they really want to keep that tail latency
> down.
They might be happier with this new patch. In the tests we ran, it improves
CPU utilization and also reduces searching cost. However, I agree we should
keep the option to search all CPUs when SIS_PROP and SIS_AVG_CPU are disabled.
> Also, only ever considering _one_ other core might affect other
> workloads. If you look at those two features above, we should already
> reduce the amount of searching we do when there's not a lot of idle
> time.
It might be interesting to add a tunable for the number of random choices to
make, and clamp it at the max nr computed from avg_cost in select_idle_cpu.
Or, choose a random starting point and then search for nr sequential
candidates; possibly limited by a tunable.
The current (pre-patch) search is biased. select_idle_cpu will not find an
idle CPU hiding behind the first nr candidates.
>> }
>>
>> + /* sd is now lowest level SMT core */
>> + if (sd->parent && (balanced || !idle_cpu(cpu_orig))) {
>> + cpu = select_idle_smt(p, sd->parent->groups);
>> + if (cpu >= 0)
>> return cpu;
>> }
>>
>> + return cpu_orig;
>> }
>>
>
>> @@ -6302,6 +6266,31 @@ static int wake_cap(struct task_struct *p, int cpu,
>> int prev_cpu)
>> return min_cap * 1024 < task_util(p) * capacity_margin;
>> }
>>
>> +static int select_idle_sibling(struct task_struct *p, int prev, int target)
>> +{
>> + struct sched_domain *sd;
>> +
>> + if (idle_cpu(target))
>> + return target;
>> +
>> + /*
>> + * If the previous cpu is cache affine and idle, don't be stupid.
>> + */
>> + if (prev != target && cpus_share_cache(prev, target) && idle_cpu(prev))
>> + return prev;
>> +
>> + sd = rcu_dereference(per_cpu(sd_llc, target));
>> + if (!sd)
>> + return target;
>> +
>> +#ifdef CONFIG_SCHED_SMT
>> + return smt_balance(p, sd, target);
>> +#else
>> +
>> + return select_idle_cpu(p, sd, target);
>> +#endif
>
> And that is just wrong....
>
>> +}
>
> So while there are things in there that _might_ work, I really don't
> want to see this one giant horrible patch again.
Subhra, I suggest roughly this refactoring into multiple patches:
* add sg_array and cp_array
* add curr_util (renamed as peter asks) and the code that updates it.
* select_idle_smt as peter suggests
* add random balancing
- Steve
