[PATCH v7 0/2] Make find_later_rq() choose a closer cpu in topology

[PATCH v7 0/2] Make find_later_rq() choose a closer cpu in topology

[Byungchul Park]

When cpudl_find() returns any among free_cpus, the cpu might not be
closer than others, considering sched domain. For example:

   this_cpu: 15
   free_cpus: 0, 1,..., 14 (== later_mask)
   best_cpu: 0

   topology:

   0 --+
       +--+
   1 --+  |
          +-- ... --+
   2 --+  |         |
       +--+         |
   3 --+            |

   ...             ...

   12 --+           |
        +--+        |
   13 --+  |        |
           +-- ... -+
   14 --+  |
        +--+
   15 --+

In this case, it would be best to select 14 since it's a free cpu and
closest to 15(this_cpu). However, currently the code select 0(best_cpu)
even though that's just any among free_cpus. Fix it.

Change from v6
   -. add a comment about selection of fallback_cpu incase more than one exist
   -. modify a comment explaining what we do wrt PREFER_SIBLING

Change from v5
   -. exclude two patches already picked up by peterz
      (sched/deadline: Make find_later_rq() choose a closer cpu in topology)
      (sched/deadline: Change return value of cpudl_find())
   -. apply what peterz fixed for 'prefer sibling', into deadline and rt

Change from v4
   -. remove a patch that might cause huge lock contention
      (by spin lock(&cpudl.lock) in a hot path of scheduler)

Change from v3
   -. rename closest_cpu to best_cpu so that it align with rt
   -. protect referring cpudl.elements with cpudl.lock
   -. change return value of cpudl_find() to bool

Change from v2
   -. add support for SD_PREFER_SIBLING

Change from v1
   -. clean up the patch

Byungchul Park (2):
  sched/deadline: Add support for SD_PREFER_SIBLING on find_later_rq()
  sched/rt: Add support for SD_PREFER_SIBLING on find_lowest_rq()

 kernel/sched/deadline.c | 55 +++++++++++++++++++++++++++++++++++++++++++++---
 kernel/sched/rt.c       | 56 ++++++++++++++++++++++++++++++++++++++++++++++---
 2 files changed, 105 insertions(+), 6 deletions(-)

-- 
1.9.1

[PATCH v7 1/2] sched/deadline: Add support for SD_PREFER_SIBLING on find_later_rq()

[Byungchul Park]

It would be better to avoid pushing tasks to other cpu within
a SD_PREFER_SIBLING domain, instead, get more chances to check other
siblings.

Signed-off-by: Byungchul Park <byungchul.park@lge.com>
---
 kernel/sched/deadline.c | 55 ++++++++++++++++++++++++++++++++++++++++++++++---
 1 file changed, 52 insertions(+), 3 deletions(-)

diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
index 0223694..8f69a37 100644
--- a/kernel/sched/deadline.c
+++ b/kernel/sched/deadline.c
@@ -1319,12 +1319,35 @@ static struct task_struct *pick_earliest_pushable_dl_task(struct rq *rq, int cpu
 
 static DEFINE_PER_CPU(cpumask_var_t, local_cpu_mask_dl);
 
+/*
+ * Find the first cpu in: mask & sd & ~prefer
+ */
+static int find_cpu(const struct cpumask *mask,
+		    const struct sched_domain *sd,
+		    const struct sched_domain *prefer)
+{
+	const struct cpumask *sds = sched_domain_span(sd);
+	const struct cpumask *ps  = prefer ? sched_domain_span(prefer) : NULL;
+	int cpu = -1;
+
+	while ((cpu = cpumask_next(cpu, mask)) < nr_cpu_ids) {
+		if (!cpumask_test_cpu(cpu, sds))
+			continue;
+		if (ps && cpumask_test_cpu(cpu, ps))
+			continue;
+		break;
+	}
+
+	return cpu;
+}
+
 static int find_later_rq(struct task_struct *task)
 {
-	struct sched_domain *sd;
+	struct sched_domain *sd, *prefer = NULL;
 	struct cpumask *later_mask = this_cpu_cpumask_var_ptr(local_cpu_mask_dl);
 	int this_cpu = smp_processor_id();
 	int cpu = task_cpu(task);
+	int fallback_cpu = -1;
 
 	/* Make sure the mask is initialized first */
 	if (unlikely(!later_mask))
@@ -1376,8 +1399,7 @@ static int find_later_rq(struct task_struct *task)
 				return this_cpu;
 			}
 
-			best_cpu = cpumask_first_and(later_mask,
-							sched_domain_span(sd));
+			best_cpu = find_cpu(later_mask, sd, prefer);
 			/*
 			 * Last chance: if a cpu being in both later_mask
 			 * and current sd span is valid, that becomes our
@@ -1385,6 +1407,26 @@ static int find_later_rq(struct task_struct *task)
 			 * already under consideration through later_mask.
 			 */
 			if (best_cpu < nr_cpu_ids) {
+				/*
+				 * If current domain is SD_PREFER_SIBLING
+				 * flaged, we have to try to check other
+				 * siblings first.
+				 */
+				if (sd->flags & SD_PREFER_SIBLING) {
+					prefer = sd;
+
+					/*
+					 * fallback_cpu should be one
+					 * in the closest domain among
+					 * SD_PREFER_SIBLING domains,
+					 * in case that more than one
+					 * SD_PREFER_SIBLING domains
+					 * exist in the hierachy.
+					 */
+					if (fallback_cpu == -1)
+						fallback_cpu = best_cpu;
+					continue;
+				}
 				rcu_read_unlock();
 				return best_cpu;
 			}
@@ -1393,6 +1435,13 @@ static int find_later_rq(struct task_struct *task)
 	rcu_read_unlock();
 
 	/*
+	 * If fallback_cpu is valid, all our guesses failed *except* for
+	 * SD_PREFER_SIBLING domain. Now, we can return the fallback cpu.
+	 */
+	if (fallback_cpu != -1)
+		return fallback_cpu;
+
+	/*
 	 * At this point, all our guesses failed, we just return
 	 * 'something', and let the caller sort the things out.
 	 */
-- 
1.9.1

[PATCH v7 2/2] sched/rt: Add support for SD_PREFER_SIBLING on find_lowest_rq()

[Byungchul Park]

It would be better to avoid pushing tasks to other cpu within
a SD_PREFER_SIBLING domain, instead, get more chances to check other
siblings.

Signed-off-by: Byungchul Park <byungchul.park@lge.com>
---
 kernel/sched/rt.c | 56 ++++++++++++++++++++++++++++++++++++++++++++++++++++---
 1 file changed, 53 insertions(+), 3 deletions(-)

diff --git a/kernel/sched/rt.c b/kernel/sched/rt.c
index 979b734..f185690 100644
--- a/kernel/sched/rt.c
+++ b/kernel/sched/rt.c
@@ -1618,12 +1618,35 @@ static struct task_struct *pick_highest_pushable_task(struct rq *rq, int cpu)
 
 static DEFINE_PER_CPU(cpumask_var_t, local_cpu_mask);
 
+/*
+ * Find the first cpu in: mask & sd & ~prefer
+ */
+static int find_cpu(const struct cpumask *mask,
+		    const struct sched_domain *sd,
+		    const struct sched_domain *prefer)
+{
+	const struct cpumask *sds = sched_domain_span(sd);
+	const struct cpumask *ps  = prefer ? sched_domain_span(prefer) : NULL;
+	int cpu = -1;
+
+	while ((cpu = cpumask_next(cpu, mask)) < nr_cpu_ids) {
+		if (!cpumask_test_cpu(cpu, sds))
+			continue;
+		if (ps && cpumask_test_cpu(cpu, ps))
+			continue;
+		break;
+	}
+
+	return cpu;
+}
+
 static int find_lowest_rq(struct task_struct *task)
 {
-	struct sched_domain *sd;
+	struct sched_domain *sd, *prefer = NULL;
 	struct cpumask *lowest_mask = this_cpu_cpumask_var_ptr(local_cpu_mask);
 	int this_cpu = smp_processor_id();
 	int cpu      = task_cpu(task);
+	int fallback_cpu = -1;
 
 	/* Make sure the mask is initialized first */
 	if (unlikely(!lowest_mask))
@@ -1668,9 +1691,29 @@ static int find_lowest_rq(struct task_struct *task)
 				return this_cpu;
 			}
 
-			best_cpu = cpumask_first_and(lowest_mask,
-						     sched_domain_span(sd));
+			best_cpu = find_cpu(lowest_mask, sd, prefer);
+
 			if (best_cpu < nr_cpu_ids) {
+				/*
+				 * If current domain is SD_PREFER_SIBLING
+				 * flaged, we have to try to check other
+				 * siblings first.
+				 */
+				if (sd->flags & SD_PREFER_SIBLING) {
+					prefer = sd;
+
+					/*
+					 * fallback_cpu should be one
+					 * in the closest domain among
+					 * SD_PREFER_SIBLING domains,
+					 * in case that more than one
+					 * SD_PREFER_SIBLING domains
+					 * exist in the hierachy.
+					 */
+					if (fallback_cpu == -1)
+						fallback_cpu = best_cpu;
+					continue;
+				}
 				rcu_read_unlock();
 				return best_cpu;
 			}
@@ -1679,6 +1722,13 @@ static int find_lowest_rq(struct task_struct *task)
 	rcu_read_unlock();
 
 	/*
+	 * If fallback_cpu is valid, all our quesses failed *except* for
+	 * SD_PREFER_SIBLING domain. Now, we can return the fallback cpu.
+	 */
+	if (fallback_cpu != -1)
+		return fallback_cpu;
+
+	/*
 	 * And finally, if there were no matches within the domains
 	 * just give the caller *something* to work with from the compatible
 	 * locations.
-- 
1.9.1

RE: [PATCH v7 0/2] Make find_later_rq() choose a closer cpu in topology

[Byungchul Park]

From: Byungchul Park [mailto:byungchul.park@lge.com]
> Change from v6
>    -. add a comment about selection of fallback_cpu incase more than one
> exist
>    -. modify a comment explaining what we do wrt PREFER_SIBLING

I could add supplementary comments, thank to Steven and Joel.

Thank you very much.

Re: [PATCH v7 1/2] sched/deadline: Add support for SD_PREFER_SIBLING on find_later_rq()

[Joel Fernandes (Google)]

Hi Byungchul,

On Thu, Aug 17, 2017 at 11:05 PM, Byungchul Park <byungchul.park@lge.com> wrote:
> It would be better to avoid pushing tasks to other cpu within
> a SD_PREFER_SIBLING domain, instead, get more chances to check other
> siblings.
>
> Signed-off-by: Byungchul Park <byungchul.park@lge.com>
> ---
>  kernel/sched/deadline.c | 55 ++++++++++++++++++++++++++++++++++++++++++++++---
>  1 file changed, 52 insertions(+), 3 deletions(-)
>
> diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
> index 0223694..8f69a37 100644
> --- a/kernel/sched/deadline.c
> +++ b/kernel/sched/deadline.c
> @@ -1319,12 +1319,35 @@ static struct task_struct *pick_earliest_pushable_dl_task(struct rq *rq, int cpu
>
>  static DEFINE_PER_CPU(cpumask_var_t, local_cpu_mask_dl);
>
> +/*
> + * Find the first cpu in: mask & sd & ~prefer
> + */
> +static int find_cpu(const struct cpumask *mask,
> +                   const struct sched_domain *sd,
> +                   const struct sched_domain *prefer)
> +{
> +       const struct cpumask *sds = sched_domain_span(sd);
> +       const struct cpumask *ps  = prefer ? sched_domain_span(prefer) : NULL;
> +       int cpu = -1;
> +
> +       while ((cpu = cpumask_next(cpu, mask)) < nr_cpu_ids) {

This can be simplified to for_each_cpu(cpu, mask) ?


thanks,

-Joel

Re: [PATCH v7 1/2] sched/deadline: Add support for SD_PREFER_SIBLING on find_later_rq()

[Byungchul Park]

On Fri, Aug 18, 2017 at 12:21:46AM -0700, Joel Fernandes (Google) wrote:
> Hi Byungchul,
> 
> On Thu, Aug 17, 2017 at 11:05 PM, Byungchul Park <byungchul.park@lge.com> wrote:
> > It would be better to avoid pushing tasks to other cpu within
> > a SD_PREFER_SIBLING domain, instead, get more chances to check other
> > siblings.
> >
> > Signed-off-by: Byungchul Park <byungchul.park@lge.com>
> > ---
> >  kernel/sched/deadline.c | 55 ++++++++++++++++++++++++++++++++++++++++++++++---
> >  1 file changed, 52 insertions(+), 3 deletions(-)
> >
> > diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
> > index 0223694..8f69a37 100644
> > --- a/kernel/sched/deadline.c
> > +++ b/kernel/sched/deadline.c
> > @@ -1319,12 +1319,35 @@ static struct task_struct *pick_earliest_pushable_dl_task(struct rq *rq, int cpu
> >
> >  static DEFINE_PER_CPU(cpumask_var_t, local_cpu_mask_dl);
> >
> > +/*
> > + * Find the first cpu in: mask & sd & ~prefer
> > + */
> > +static int find_cpu(const struct cpumask *mask,
> > +                   const struct sched_domain *sd,
> > +                   const struct sched_domain *prefer)
> > +{
> > +       const struct cpumask *sds = sched_domain_span(sd);
> > +       const struct cpumask *ps  = prefer ? sched_domain_span(prefer) : NULL;
> > +       int cpu = -1;
> > +
> > +       while ((cpu = cpumask_next(cpu, mask)) < nr_cpu_ids) {
> 
> This can be simplified to for_each_cpu(cpu, mask) ?

Indeed, exactly.

I will use that, thank you.

Re: [PATCH v7 2/2] sched/rt: Add support for SD_PREFER_SIBLING on find_lowest_rq()

[Steven Rostedt]

On Fri, 18 Aug 2017 15:05:13 +0900
Byungchul Park <byungchul.park@lge.com> wrote:

> It would be better to avoid pushing tasks to other cpu within
> a SD_PREFER_SIBLING domain, instead, get more chances to check other
> siblings.
> 
> Signed-off-by: Byungchul Park <byungchul.park@lge.com>

Reviewed-by: Steven Rostedt (VMware) <rostedt@goodmis.org>

Note, we really should consolidate the rt.c and deadline.c find lowest
rqs code, especially since they should be aware of each other (rt and
deadline tasks should take notice of other rt and deadline tasks, not
just their own kind).

-- Steve