On 09/25/2017 07:51 PM, joelaf wrote:

Hi Rohit,

Just some comments:

Hi Joel,

Thanks for the comments

On 09/25/2017 05:02 PM, Rohit Jain wrote:

...

While looking for idle CPUs for a waking task, we should also account for the delays caused due to the bandwidth reduction by RT/IRQ tasks.

This patch does that by trying to find a higher capacity CPU with minimum wake up latency.

Signed-off-by: Rohit Jain rohit.k.jain@oracle.com

kernel/sched/fair.c | 27 ++++++++++++++++++++++++--- 1 file changed, 24 insertions(+), 3 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c index eca6a57..afb701f 100644 --- a/kernel/sched/fair.c +++ b/kernel/sched/fair.c @@ -5590,6 +5590,11 @@ static unsigned long capacity_orig_of(int cpu) return cpu_rq(cpu)->cpu_capacity_orig; }

+static inline bool full_capacity(int cpu) +{

• return (capacity_of(cpu) >= (capacity_orig_of(cpu)*819 >> 10));

Wouldn't 768 be better for multiplication? gcc converts the expression to shifts and adds then.

While 768 is easier to convert to shifts and adds, 819/1024 gets you very close to 80% which is what I was trying to achieve.

...

+}

• static unsigned long cpu_avg_load_per_task(int cpu) { struct rq *rq = cpu_rq(cpu);

@@ -5916,8 +5921,10 @@ find_idlest_cpu(struct sched_group *group, struct task_struct *p, int this_cpu) unsigned long load, min_load = ULONG_MAX; unsigned int min_exit_latency = UINT_MAX; u64 latest_idle_timestamp = 0;

• unsigned int backup_cap = 0; int least_loaded_cpu = this_cpu; int shallowest_idle_cpu = -1;

• int shallowest_idle_cpu_backup = -1; int i;

  /* Check if we have any choice: */

@@ -5937,7 +5944,12 @@ find_idlest_cpu(struct sched_group *group, struct task_struct *p, int this_cpu) */ min_exit_latency = idle->exit_latency; latest_idle_timestamp = rq->idle_stamp;

• 		shallowest_idle_cpu = i;
  

• 		if (full_capacity(i)) {
  

• 			shallowest_idle_cpu = i;
  

• 		} else if (capacity_of(i) > backup_cap) {
  

• 			shallowest_idle_cpu_backup = i;
  

• 			backup_cap = capacity_of(i);
  

• 		}
  

I'm a bit skeptical about this - if the CPU is idle, then is it likely that the capacity of the CPU is reduced due to RT pressure?

What has idleness got to do with RT pressure?

This is an instantaneous view where the scheduler is looking to place threads. In this case, if we know historically the capacity of the CPU is reduced (due to RT/IRQ/Thermal Throttling or whatever it may be) we should avoid that CPU if we have a choice.

I can see that it can matter, but I am wondering if you have any data for your usecase to show that it does (that is if you didn't consider RT pressure for idle CPUs, are you still seeing a big enough performance improvement to warrant the change?

I tested this with OLTP which has a mix of both IRQ and RT threads. Also, I tested with micro-benchmarks which have IRQ and fair threads. I haven't seen what happens just with RT alone. This would come back to the question: "Why reduce capacities when RT thread is running?", frankly I don't know the answer, however from a capacity stand point that is taken into account.

It makes sense to me however I don't know the reasoning.

...

	} else if ((!idle || idle->exit_latency == min_exit_latency) &&
		   rq->idle_stamp > latest_idle_timestamp) {
		/*

@@ -5946,7 +5958,12 @@ find_idlest_cpu(struct sched_group *group, struct task_struct *p, int this_cpu) * a warmer cache. */ latest_idle_timestamp = rq->idle_stamp;

• 		shallowest_idle_cpu = i;
  

• 		if (full_capacity(i)) {
  

• 			shallowest_idle_cpu = i;
  

• 		} else if (capacity_of(i) > backup_cap) {
  

• 			shallowest_idle_cpu_backup = i;
  

• 			backup_cap = capacity_of(i);
  

• 		}
  }
  

  } else if (shallowest_idle_cpu == -1) { load = weighted_cpuload(cpu_rq(i));

@@ -5957,7 +5974,11 @@ find_idlest_cpu(struct sched_group *group, struct task_struct *p, int this_cpu) } }

• return shallowest_idle_cpu != -1 ? shallowest_idle_cpu : least_loaded_cpu;

• if (shallowest_idle_cpu != -1)

• return shallowest_idle_cpu;
  

• return (shallowest_idle_cpu_backup != -1 ?

• shallowest_idle_cpu_backup : least_loaded_cpu);
  

  }

  #ifdef CONFIG_SCHED_SMT

I see code duplication here which can be reduced by 7 lines compared to your original patch:

This does look better and I will try to incorporate this.

Thanks, Rohit

---

kernel/sched/fair.c | 20 +++++++++++++++++--- 1 file changed, 17 insertions(+), 3 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c index c95880e216f6..72fc8d18b251 100644 --- a/kernel/sched/fair.c +++ b/kernel/sched/fair.c @@ -5528,6 +5528,7 @@ find_idlest_cpu(struct sched_group *group, struct task_struct *p, int this_cpu) /* Traverse only the allowed CPUs */ for_each_cpu_and(i, sched_group_span(group), &p->cpus_allowed) { if (idle_cpu(i)) {

• 	int idle_candidate = -1;
  struct rq *rq = cpu_rq(i);
  struct cpuidle_state *idle = idle_get_state(rq);
  if (idle && idle->exit_latency < min_exit_latency) {
  

@@ -5538,7 +5539,7 @@ find_idlest_cpu(struct sched_group *group, struct task_struct *p, int this_cpu) */ min_exit_latency = idle->exit_latency; latest_idle_timestamp = rq->idle_stamp;

• 		shallowest_idle_cpu = i;
  

• 		idle_candidate = i;
  } else if ((!idle || idle->exit_latency == min_exit_latency) &&
  	   rq->idle_stamp > latest_idle_timestamp) {
  	/*
  

@@ -5547,7 +5548,16 @@ find_idlest_cpu(struct sched_group *group, struct task_struct *p, int this_cpu) * a warmer cache. */ latest_idle_timestamp = rq->idle_stamp;

• 		shallowest_idle_cpu = i;
  

• 		idle_candidate = i;
  

• 	}
  

• 	if (idle_candidate != -1) {
  

• 		if (full_capacity(idle_candidate)) {
  

• 			shallowest_idle_cpu = idle_candidate;
  

• 		} else if (capacity_of(idle_candidate) > backup_cap) {
  

• 			shallowest_idle_cpu_backup = idle_candidate;
  

• 			backup_cap = capacity_of(idle_candidate);
  

• 		}
  }
  

  } else if (shallowest_idle_cpu == -1) { load = weighted_cpuload(i);

@@ -5558,7 +5568,11 @@ find_idlest_cpu(struct sched_group *group, struct task_struct *p, int this_cpu) } }

• return shallowest_idle_cpu != -1 ? shallowest_idle_cpu : least_loaded_cpu;

• if (shallowest_idle_cpu != -1)

• return shallowest_idle_cpu;
  

• return (shallowest_idle_cpu_backup != -1 ?

• 	shallowest_idle_cpu_backup : least_loaded_cpu);
  

  }

  #ifdef CONFIG_SCHED_SMT

On 09/25/2017 11:53 PM, Joel Fernandes wrote:

Hi Rohit,

Just some comments:

Hi Joel,

Thanks for the comments.

On Mon, Sep 25, 2017 at 5:02 PM, Rohit Jain rohit.k.jain@oracle.com wrote:

...

While looking for CPUs to place running tasks on, the scheduler completely ignores the capacity stolen away by RT/IRQ tasks.

This patch fixes that.

Signed-off-by: Rohit Jain rohit.k.jain@oracle.com

kernel/sched/fair.c | 54 ++++++++++++++++++++++++++++++++++++++++++----------- 1 file changed, 43 insertions(+), 11 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c index afb701f..19ff2c3 100644 --- a/kernel/sched/fair.c +++ b/kernel/sched/fair.c @@ -6040,7 +6040,10 @@ void __update_idle_core(struct rq *rq) static int select_idle_core(struct task_struct *p, struct sched_domain *sd, int target) { struct cpumask *cpus = this_cpu_cpumask_var_ptr(select_idle_mask);

•   int core, cpu;
  

•   int core, cpu, rcpu, rcpu_backup;
  

I would call rcpu_backup as backup_cpu.

OK

...

•   unsigned int backup_cap = 0;
  

•   rcpu = rcpu_backup = -1;
  
     if (!static_branch_likely(&sched_smt_present))
             return -1;
  

@@ -6057,10 +6060,20 @@ static int select_idle_core(struct task_struct *p, struct sched_domain *sd, int cpumask_clear_cpu(cpu, cpus); if (!idle_cpu(cpu)) idle = false;

•                   if (full_capacity(cpu)) {
  

•                           rcpu = cpu;
  

•                   } else if ((rcpu == -1) && (capacity_of(cpu) > backup_cap)) {
  

•                           backup_cap = capacity_of(cpu);
  

•                           rcpu_backup = cpu;
  

•                   }
  

Here you comparing capacity of different SMT threads.

...

             }

•           if (idle)
  

•                   return core;
  

•           if (idle) {
  

•                   if (rcpu == -1)
  

•                           return (rcpu_backup != -1 ? rcpu_backup : core);
  

•                   return rcpu;
  

•           }
  

This didn't make much sense to me, here you are returning either an SMT thread or a core. That doesn't make much of a difference because SMT threads share the same capacity (SD_SHARE_CPUCAPACITY). I think what you want to do is find out the capacity of a 'core', not an SMT thread, and compare the capacity of different cores and consider the one which has least RT/IRQ interference.

IIUC the capacities of each strand is scaled by IRQ and 'rt_avg' for that 'rq'. Now if the strand is idle now and gets an interrupt in the future, the 'core' would look like:

+----+----+    | I  |    |    | T  |    |    +----+----+

(I -> Interrupt, T-> Thread we are trying to schedule).

whereas if the other strand on the core was taking interrupt the core would look like:

+----+----+    | I  | T  |    |    |    |    +----+----+

With this case, because we know from the past avg, one of the strands is running low on capacity, I am trying to return a better strand for the thread to start on.

...

     }

     /*

@@ -6076,7 +6089,8 @@ static int select_idle_core(struct task_struct *p, struct sched_domain *sd, int */ static int select_idle_smt(struct task_struct *p, struct sched_domain *sd, int target) {

•   int cpu;
  

•   int cpu, backup_cpu = -1;
  

•   unsigned int backup_cap = 0;
  
     if (!static_branch_likely(&sched_smt_present))
             return -1;
  

@@ -6084,11 +6098,17 @@ static int select_idle_smt(struct task_struct *p, struct sched_domain *sd, int t for_each_cpu(cpu, cpu_smt_mask(target)) { if (!cpumask_test_cpu(cpu, &p->cpus_allowed)) continue;

•           if (idle_cpu(cpu))
  

•                   return cpu;
  

•           if (idle_cpu(cpu)) {
  

•                   if (full_capacity(cpu))
  

•                           return cpu;
  

•                   if (capacity_of(cpu) > backup_cap) {
  

•                           backup_cap = capacity_of(cpu);
  

•                           backup_cpu = cpu;
  

•                   }
  

•           }
  

Same thing here, since SMT threads share the same underlying capacity, is there any point in comparing the capacities of each SMT thread?

See above

Thanks, Rohit

thanks,

• Joel

[...]

Hi Joel,

On 09/28/2017 05:53 AM, joelaf wrote:

Hi Rohit,

On Tue, Sep 26, 2017 at 12:48 PM, Rohit Jain rohit.k.jain@oracle.com wrote: [...]

<snip>

...

...

...

              }

•           if (idle)
  

•                   return core;
  

•           if (idle) {
  

•                   if (rcpu == -1)
  

•                           return (rcpu_backup != -1 ? rcpu_backup :
  

core);

•                   return rcpu;
  

•           }
  

This didn't make much sense to me, here you are returning either an SMT thread or a core. That doesn't make much of a difference because SMT threads share the same capacity (SD_SHARE_CPUCAPACITY). I think what you want to do is find out the capacity of a 'core', not an SMT thread, and compare the capacity of different cores and consider the one which has least RT/IRQ interference.

IIUC the capacities of each strand is scaled by IRQ and 'rt_avg' for that 'rq'. Now if the strand is idle now and gets an interrupt in the future, the 'core' would look like:

+----+----+
| I  |    |
| T  |    |
+----+----+

(I -> Interrupt, T-> Thread we are trying to schedule).

whereas if the other strand on the core was taking interrupt the core would look like:

+----+----+
| I  | T  |
|    |    |
+----+----+

With this case, because we know from the past avg, one of the strands is running low on capacity, I am trying to return a better strand for the thread to start on.

I know what you're trying to do but they way you've retrofitted it into the core looks weird (to me) and makes the code unreadable and ugly IMO.

Why not do something simpler like skip the core if any SMT thread has been running at lesser capacity? I'm not sure if this works great or if the maintainers will prefer your or my below approach, but I find the below diff much cleaner for the select_idle_core bit. It also makes more sense since resources are shared at SMT level so makes sense to me to skip the core altogether for this:

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c index 6ee7242dbe0a..f324a84e29f1 100644 --- a/kernel/sched/fair.c +++ b/kernel/sched/fair.c @@ -5738,14 +5738,17 @@ static int select_idle_core(struct task_struct *p, struct sched_domain *sd, int

for_each_cpu_wrap(core, cpus, target) { bool idle = true;

• bool full_cap = true;
  
  

  for_each_cpu(cpu, cpu_smt_mask(core)) { cpumask_clear_cpu(cpu, cpus); if (!idle_cpu(cpu)) idle = false;

• 	if (!full_capacity(cpu))
  

• 		full_cap = false;
  

  }

• if (idle)
  

• if (idle && full_cap)
  return core;
  

  }

Well, with your changes you will skip over fully idle cores which is not an ideal thing either. I see that you were advocating for select idle+lowest capacity core, whereas I was stopping at the first idlecore.

Since the whole philosophy till now in this patch is "Don't spare an idle CPU", I think the following diff might look better to you. Please note this is only for discussion sakes, I haven't fully tested it yet.

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c index ec15e5f..c2933eb 100644 --- a/kernel/sched/fair.c +++ b/kernel/sched/fair.c @@ -6040,7 +6040,9 @@ void __update_idle_core(struct rq *rq)  static int select_idle_core(struct task_struct *p, struct sched_domain *sd, int target)  {      struct cpumask *cpus = this_cpu_cpumask_var_ptr(select_idle_mask); -    int core, cpu; +    int core, cpu, rcpu, backup_core; + +    rcpu = backup_core = -1;

if (!static_branch_likely(&sched_smt_present))          return -1; @@ -6052,15 +6054,34 @@ static int select_idle_core(struct task_struct *p, struct sched_domain *sd, int

for_each_cpu_wrap(core, cpus, target) {          bool idle = true; +        bool full_cap = true;

for_each_cpu(cpu, cpu_smt_mask(core)) {              cpumask_clear_cpu(cpu, cpus);              if (!idle_cpu(cpu))                  idle = false; + +            if (!full_capacity(cpu)) { +                full_cap = false; +            }          }

-        if (idle) +        if (idle && full_cap)              return core; +        else if (idle && backup_core == -1) +            backup_core = core; +    } + +    if (backup_core != -1) { +        for_each_cpu(cpu, cpu_smt_mask(backup_core)) { +            if (full_capacity(cpu)) +                return cpu; +            else if ((rcpu == -1) || +                 (capacity_of(cpu) > capacity_of(rcpu))) +                rcpu = cpu; +        } + +        return rcpu;      }

Do let me know what you think.

Thanks, Rohit

thanks,

• Joel

Hi Joel,

On 10/02/2017 09:52 PM, Joel Fernandes wrote:

Hi Rohit,

On Thu, Sep 28, 2017 at 8:09 AM, Rohit Jain rohit.k.jain@oracle.com wrote: [..]

...

...

...

With this case, because we know from the past avg, one of the strands is running low on capacity, I am trying to return a better strand for the thread to start on.

I know what you're trying to do but they way you've retrofitted it into the core looks weird (to me) and makes the code unreadable and ugly IMO.

Why not do something simpler like skip the core if any SMT thread has been running at lesser capacity? I'm not sure if this works great or if the maintainers will prefer your or my below approach, but I find the below diff much cleaner for the select_idle_core bit. It also makes more sense since resources are shared at SMT level so makes sense to me to skip the core altogether for this:

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c index 6ee7242dbe0a..f324a84e29f1 100644 --- a/kernel/sched/fair.c +++ b/kernel/sched/fair.c @@ -5738,14 +5738,17 @@ static int select_idle_core(struct task_struct *p, struct sched_domain *sd, int for_each_cpu_wrap(core, cpus, target) { bool idle = true;

•           bool full_cap = true;
             for_each_cpu(cpu, cpu_smt_mask(core)) {
                     cpumask_clear_cpu(cpu, cpus);
                     if (!idle_cpu(cpu))
                             idle = false;
  

•                   if (!full_capacity(cpu))
  

•                           full_cap = false;
             }
  

  •         if (idle)
    

•           if (idle && full_cap)
                     return core;
     }
  
  

Well, with your changes you will skip over fully idle cores which is not an ideal thing either. I see that you were advocating for select idle+lowest capacity core, whereas I was stopping at the first idlecore.

Since the whole philosophy till now in this patch is "Don't spare an idle CPU", I think the following diff might look better to you. Please note this is only for discussion sakes, I haven't fully tested it yet.

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c index ec15e5f..c2933eb 100644 --- a/kernel/sched/fair.c +++ b/kernel/sched/fair.c @@ -6040,7 +6040,9 @@ void __update_idle_core(struct rq *rq) static int select_idle_core(struct task_struct *p, struct sched_domain *sd, int target) { struct cpumask *cpus = this_cpu_cpumask_var_ptr(select_idle_mask);

• int core, cpu;

• int core, cpu, rcpu, backup_core;

• rcpu = backup_core = -1;

  if (!static_branch_likely(&sched_smt_present)) return -1;

@@ -6052,15 +6054,34 @@ static int select_idle_core(struct task_struct *p, struct sched_domain *sd, int

  for_each_cpu_wrap(core, cpus, target) {
      bool idle = true;

•    bool full_cap = true;
  
      for_each_cpu(cpu, cpu_smt_mask(core)) {
          cpumask_clear_cpu(cpu, cpus);
          if (!idle_cpu(cpu))
              idle = false;
  

•        if (!full_capacity(cpu)) {
  

•            full_cap = false;
  

•        }
      }
  
  

•    if (idle)
  

•    if (idle && full_cap)
          return core;
  

•    else if (idle && backup_core == -1)
  

•        backup_core = core;
  

• }
• if (backup_core != -1) {

•    for_each_cpu(cpu, cpu_smt_mask(backup_core)) {
  

•        if (full_capacity(cpu))
  

•            return cpu;
  

•        else if ((rcpu == -1) ||
  

•             (capacity_of(cpu) > capacity_of(rcpu)))
  

•            rcpu = cpu;
  

•    }
  

•    return rcpu;
  }
  
  
  

Do let me know what you think.

I think that if there isn't a benefit in your tests in doing the above vs the simpler approach, then I prefer the simpler approach especially since there's no point/benefit in complicating the code for select_idle_core.

Fair enough!

If there are no more concerns in this version, then I will go ahead and try out all that is discussed in this version and send an updated version. Please let me know if there are any other concerns/feedback.

Thanks, Rohit

thanks,

• Joel