[PATCH v5 0/4] Make find_later_rq() choose a closer cpu in topology

[PATCH v5 0/4] 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 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 (4):
  sched/deadline: Make find_later_rq() choose a closer cpu in topology
  sched/deadline: Change return value of cpudl_find()
  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/cpudeadline.c | 26 ++++++++++++-------------
 kernel/sched/deadline.c    | 48 +++++++++++++++++++++++++++++++---------------
 kernel/sched/rt.c          | 17 ++++++++++++++++
 3 files changed, 63 insertions(+), 28 deletions(-)

-- 
1.9.1

[PATCH v5 1/4] sched/deadline: 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.

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

diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
index a2ce590..9d997d9 100644
--- a/kernel/sched/deadline.c
+++ b/kernel/sched/deadline.c
@@ -1324,7 +1324,7 @@ static int find_later_rq(struct task_struct *task)
 	struct sched_domain *sd;
 	struct cpumask *later_mask = this_cpu_cpumask_var_ptr(local_cpu_mask_dl);
 	int this_cpu = smp_processor_id();
-	int best_cpu, cpu = task_cpu(task);
+	int cpu = task_cpu(task);
 
 	/* Make sure the mask is initialized first */
 	if (unlikely(!later_mask))
@@ -1337,17 +1337,14 @@ static int find_later_rq(struct task_struct *task)
 	 * We have to consider system topology and task affinity
 	 * first, then we can look for a suitable cpu.
 	 */
-	best_cpu = cpudl_find(&task_rq(task)->rd->cpudl,
-			task, later_mask);
-	if (best_cpu == -1)
+	if (cpudl_find(&task_rq(task)->rd->cpudl, task, later_mask) == -1)
 		return -1;
 
 	/*
-	 * If we are here, some target has been found,
-	 * the most suitable of which is cached in best_cpu.
-	 * This is, among the runqueues where the current tasks
-	 * have later deadlines than the task's one, the rq
-	 * with the latest possible one.
+	 * If we are here, some targets have been found, including
+	 * the most suitable which is, among the runqueues where the
+	 * current tasks have later deadlines than the task's one, the
+	 * rq with the latest possible one.
 	 *
 	 * Now we check how well this matches with task's
 	 * affinity and system topology.
@@ -1367,6 +1364,7 @@ static int find_later_rq(struct task_struct *task)
 	rcu_read_lock();
 	for_each_domain(cpu, sd) {
 		if (sd->flags & SD_WAKE_AFFINE) {
+			int best_cpu;
 
 			/*
 			 * If possible, preempting this_cpu is
@@ -1378,12 +1376,15 @@ static int find_later_rq(struct task_struct *task)
 				return this_cpu;
 			}
 
+			best_cpu = cpumask_first_and(later_mask,
+							sched_domain_span(sd));
 			/*
-			 * Last chance: if best_cpu is valid and is
-			 * in the mask, that becomes our choice.
+			 * Last chance: if a cpu being in both later_mask
+			 * and current sd span is valid, that becomes our
+			 * choice. Of course, the latest possible cpu is
+			 * already under consideration through later_mask.
 			 */
-			if (best_cpu < nr_cpu_ids &&
-			    cpumask_test_cpu(best_cpu, sched_domain_span(sd))) {
+			if (best_cpu < nr_cpu_ids) {
 				rcu_read_unlock();
 				return best_cpu;
 			}
-- 
1.9.1

Re: [PATCH v5 1/4] sched/deadline: Make find_later_rq() choose a closer cpu in topology

[Juri Lelli]

Hi,

On 23/05/17 11:00, Byungchul Park wrote:
> 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.
> 
> Signed-off-by: Byungchul Park <byungchul.park@lge.com>

The patch looks essentially all right to me: makes sense and it aligns
behavior with RT.

However...

> ---
>  kernel/sched/deadline.c | 27 ++++++++++++++-------------
>  1 file changed, 14 insertions(+), 13 deletions(-)
> 
> diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
> index a2ce590..9d997d9 100644
> --- a/kernel/sched/deadline.c
> +++ b/kernel/sched/deadline.c
> @@ -1324,7 +1324,7 @@ static int find_later_rq(struct task_struct *task)
>  	struct sched_domain *sd;
>  	struct cpumask *later_mask = this_cpu_cpumask_var_ptr(local_cpu_mask_dl);
>  	int this_cpu = smp_processor_id();
> -	int best_cpu, cpu = task_cpu(task);
> +	int cpu = task_cpu(task);
>  
>  	/* Make sure the mask is initialized first */
>  	if (unlikely(!later_mask))
> @@ -1337,17 +1337,14 @@ static int find_later_rq(struct task_struct *task)
>  	 * We have to consider system topology and task affinity
>  	 * first, then we can look for a suitable cpu.
>  	 */
> -	best_cpu = cpudl_find(&task_rq(task)->rd->cpudl,
> -			task, later_mask);
> -	if (best_cpu == -1)
> +	if (cpudl_find(&task_rq(task)->rd->cpudl, task, later_mask) == -1)
>  		return -1;
>  
>  	/*
> -	 * If we are here, some target has been found,
> -	 * the most suitable of which is cached in best_cpu.
> -	 * This is, among the runqueues where the current tasks
> -	 * have later deadlines than the task's one, the rq
> -	 * with the latest possible one.
> +	 * If we are here, some targets have been found, including
> +	 * the most suitable which is, among the runqueues where the
> +	 * current tasks have later deadlines than the task's one, the
> +	 * rq with the latest possible one.
>  	 *
>  	 * Now we check how well this matches with task's
>  	 * affinity and system topology.
> @@ -1367,6 +1364,7 @@ static int find_later_rq(struct task_struct *task)
>  	rcu_read_lock();
>  	for_each_domain(cpu, sd) {
>  		if (sd->flags & SD_WAKE_AFFINE) {

This is orthogonal to the proposed change, but I'm wondering if it make
sense to do the following only for SD_WAKE_AFFINE domains. The
consideration applies to RT as well, actually. Also, find_later_rq gets
called when trying to push tasks away as well and in that case checking
for this flag seems inappropriate? Peter, Steve?

Thanks,

- Juri

Re: [PATCH v5 1/4] sched/deadline: Make find_later_rq() choose a closer cpu in topology

[Byungchul Park]

On Wed, Jul 12, 2017 at 02:13:36PM +0100, Juri Lelli wrote:
> > @@ -1367,6 +1364,7 @@ static int find_later_rq(struct task_struct *task)
> >  	rcu_read_lock();
> >  	for_each_domain(cpu, sd) {
> >  		if (sd->flags & SD_WAKE_AFFINE) {

Hi,

> This is orthogonal to the proposed change, but I'm wondering if it make
> sense to do the following only for SD_WAKE_AFFINE domains. The

Actually I also wonder it..

> consideration applies to RT as well, actually. Also, find_later_rq gets
> called when trying to push tasks away as well and in that case checking
> for this flag seems inappropriate? Peter, Steve?
> 
> Thanks,
> 
> - Juri

[tip:sched/core] sched/deadline: Make find_later_rq() choose a closer CPU in topology

[tip-bot for Byungchul Park]

Commit-ID:  b18c3ca11c20caa4a397baa9b893ebc4aaa4fe9f
Gitweb:     http://git.kernel.org/tip/b18c3ca11c20caa4a397baa9b893ebc4aaa4fe9f
Author:     Byungchul Park <byungchul.park@lge.com>
AuthorDate: Tue, 23 May 2017 11:00:56 +0900
Committer:  Ingo Molnar <mingo@kernel.org>
CommitDate: Thu, 10 Aug 2017 12:18:17 +0200

sched/deadline: Make find_later_rq() choose a closer CPU in topology

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 selects 0 (best_cpu)
even though that's just any among free_cpus. Fix it.

This (re)aligns the deadline behaviour with the rt behaviour.

Signed-off-by: Byungchul Park <byungchul.park@lge.com>
Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
Cc: <bristot@redhat.com>
Cc: <juri.lelli@gmail.com>
Cc: <kernel-team@lge.com>
Cc: <rostedt@goodmis.org>
Cc: Linus Torvalds <torvalds@linux-foundation.org>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Thomas Gleixner <tglx@linutronix.de>
Link: http://lkml.kernel.org/r/1495504859-10960-2-git-send-email-byungchul.park@lge.com
Signed-off-by: Ingo Molnar <mingo@kernel.org>
---
 kernel/sched/deadline.c | 27 ++++++++++++++-------------
 1 file changed, 14 insertions(+), 13 deletions(-)

diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
index a205ac7..ac07d7c 100644
--- a/kernel/sched/deadline.c
+++ b/kernel/sched/deadline.c
@@ -1798,7 +1798,7 @@ static int find_later_rq(struct task_struct *task)
 	struct sched_domain *sd;
 	struct cpumask *later_mask = this_cpu_cpumask_var_ptr(local_cpu_mask_dl);
 	int this_cpu = smp_processor_id();
-	int best_cpu, cpu = task_cpu(task);
+	int cpu = task_cpu(task);
 
 	/* Make sure the mask is initialized first */
 	if (unlikely(!later_mask))
@@ -1811,17 +1811,14 @@ static int find_later_rq(struct task_struct *task)
 	 * We have to consider system topology and task affinity
 	 * first, then we can look for a suitable cpu.
 	 */
-	best_cpu = cpudl_find(&task_rq(task)->rd->cpudl,
-			task, later_mask);
-	if (best_cpu == -1)
+	if (cpudl_find(&task_rq(task)->rd->cpudl, task, later_mask) == -1)
 		return -1;
 
 	/*
-	 * If we are here, some target has been found,
-	 * the most suitable of which is cached in best_cpu.
-	 * This is, among the runqueues where the current tasks
-	 * have later deadlines than the task's one, the rq
-	 * with the latest possible one.
+	 * If we are here, some targets have been found, including
+	 * the most suitable which is, among the runqueues where the
+	 * current tasks have later deadlines than the task's one, the
+	 * rq with the latest possible one.
 	 *
 	 * Now we check how well this matches with task's
 	 * affinity and system topology.
@@ -1841,6 +1838,7 @@ static int find_later_rq(struct task_struct *task)
 	rcu_read_lock();
 	for_each_domain(cpu, sd) {
 		if (sd->flags & SD_WAKE_AFFINE) {
+			int best_cpu;
 
 			/*
 			 * If possible, preempting this_cpu is
@@ -1852,12 +1850,15 @@ static int find_later_rq(struct task_struct *task)
 				return this_cpu;
 			}
 
+			best_cpu = cpumask_first_and(later_mask,
+							sched_domain_span(sd));
 			/*
-			 * Last chance: if best_cpu is valid and is
-			 * in the mask, that becomes our choice.
+			 * Last chance: if a cpu being in both later_mask
+			 * and current sd span is valid, that becomes our
+			 * choice. Of course, the latest possible cpu is
+			 * already under consideration through later_mask.
 			 */
-			if (best_cpu < nr_cpu_ids &&
-			    cpumask_test_cpu(best_cpu, sched_domain_span(sd))) {
+			if (best_cpu < nr_cpu_ids) {
 				rcu_read_unlock();
 				return best_cpu;
 			}

[PATCH v5 2/4] sched/deadline: Change return value of cpudl_find()

[Byungchul Park]

Currently cpudl_find() returns the best cpu that means it has the
maximum dl, however, the value is already kept in later_mask and the
return value is not referred directly any more.

Now, it's enough to return whether CPUs were found or not, like rt.

Signed-off-by: Byungchul Park <byungchul.park@lge.com>
---
 kernel/sched/cpudeadline.c | 26 +++++++++++++-------------
 kernel/sched/deadline.c    |  6 +++---
 2 files changed, 16 insertions(+), 16 deletions(-)

diff --git a/kernel/sched/cpudeadline.c b/kernel/sched/cpudeadline.c
index fba235c..7408cbe 100644
--- a/kernel/sched/cpudeadline.c
+++ b/kernel/sched/cpudeadline.c
@@ -119,29 +119,29 @@ static inline int cpudl_maximum(struct cpudl *cp)
  * @p: the task
  * @later_mask: a mask to fill in with the selected CPUs (or NULL)
  *
- * Returns: int - best CPU (heap maximum if suitable)
+ * Returns: (int)bool - CPUs were found
  */
 int cpudl_find(struct cpudl *cp, struct task_struct *p,
 	       struct cpumask *later_mask)
 {
-	int best_cpu = -1;
 	const struct sched_dl_entity *dl_se = &p->dl;
 
 	if (later_mask &&
 	    cpumask_and(later_mask, cp->free_cpus, &p->cpus_allowed)) {
-		best_cpu = cpumask_any(later_mask);
-		goto out;
-	} else if (cpumask_test_cpu(cpudl_maximum(cp), &p->cpus_allowed) &&
-			dl_time_before(dl_se->deadline, cp->elements[0].dl)) {
-		best_cpu = cpudl_maximum(cp);
-		if (later_mask)
-			cpumask_set_cpu(best_cpu, later_mask);
-	}
+		return 1;
+	} else {
+		int best_cpu = cpudl_maximum(cp);
+		WARN_ON(best_cpu != -1 && !cpu_present(best_cpu));
 
-out:
-	WARN_ON(best_cpu != -1 && !cpu_present(best_cpu));
+		if (cpumask_test_cpu(best_cpu, &p->cpus_allowed) &&
+		    dl_time_before(dl_se->deadline, cp->elements[0].dl)) {
+			if (later_mask)
+				cpumask_set_cpu(best_cpu, later_mask);
 
-	return best_cpu;
+			return 1;
+		}
+	}
+	return 0;
 }
 
 /*
diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
index 9d997d9..0223694 100644
--- a/kernel/sched/deadline.c
+++ b/kernel/sched/deadline.c
@@ -1107,7 +1107,7 @@ static void check_preempt_equal_dl(struct rq *rq, struct task_struct *p)
 	 * let's hope p can move out.
 	 */
 	if (rq->curr->nr_cpus_allowed == 1 ||
-	    cpudl_find(&rq->rd->cpudl, rq->curr, NULL) == -1)
+	    !cpudl_find(&rq->rd->cpudl, rq->curr, NULL))
 		return;
 
 	/*
@@ -1115,7 +1115,7 @@ static void check_preempt_equal_dl(struct rq *rq, struct task_struct *p)
 	 * see if it is pushed or pulled somewhere else.
 	 */
 	if (p->nr_cpus_allowed != 1 &&
-	    cpudl_find(&rq->rd->cpudl, p, NULL) != -1)
+	    cpudl_find(&rq->rd->cpudl, p, NULL))
 		return;
 
 	resched_curr(rq);
@@ -1337,7 +1337,7 @@ static int find_later_rq(struct task_struct *task)
 	 * We have to consider system topology and task affinity
 	 * first, then we can look for a suitable cpu.
 	 */
-	if (cpudl_find(&task_rq(task)->rd->cpudl, task, later_mask) == -1)
+	if (!cpudl_find(&task_rq(task)->rd->cpudl, task, later_mask))
 		return -1;
 
 	/*
-- 
1.9.1

Re: [PATCH v5 2/4] sched/deadline: Change return value of cpudl_find()

[Juri Lelli]

Hi,

On 23/05/17 11:00, Byungchul Park wrote:
> Currently cpudl_find() returns the best cpu that means it has the
> maximum dl, however, the value is already kept in later_mask and the
> return value is not referred directly any more.
> 
> Now, it's enough to return whether CPUs were found or not, like rt.
> 

I'd reword as

cpudl_find() users are only interested in knowing if suitable CPU(s)
were found or not (and then they look at later_mask to know which).

Change cpudl_find() return type accordingly.

> Signed-off-by: Byungchul Park <byungchul.park@lge.com>
> ---
>  kernel/sched/cpudeadline.c | 26 +++++++++++++-------------
>  kernel/sched/deadline.c    |  6 +++---
>  2 files changed, 16 insertions(+), 16 deletions(-)
> 
> diff --git a/kernel/sched/cpudeadline.c b/kernel/sched/cpudeadline.c
> index fba235c..7408cbe 100644
> --- a/kernel/sched/cpudeadline.c
> +++ b/kernel/sched/cpudeadline.c
> @@ -119,29 +119,29 @@ static inline int cpudl_maximum(struct cpudl *cp)
>   * @p: the task
>   * @later_mask: a mask to fill in with the selected CPUs (or NULL)
>   *
> - * Returns: int - best CPU (heap maximum if suitable)
> + * Returns: (int)bool - CPUs were found

Why not simply bool?

Thanks,

- Juri

Re: [PATCH v5 2/4] sched/deadline: Change return value of cpudl_find()

[Byungchul Park]

On Wed, Jul 12, 2017 at 02:22:32PM +0100, Juri Lelli wrote:
> Hi,
> 
> On 23/05/17 11:00, Byungchul Park wrote:
> > Currently cpudl_find() returns the best cpu that means it has the
> > maximum dl, however, the value is already kept in later_mask and the
> > return value is not referred directly any more.
> > 
> > Now, it's enough to return whether CPUs were found or not, like rt.
> > 
> 
> I'd reword as
> 
> cpudl_find() users are only interested in knowing if suitable CPU(s)
> were found or not (and then they look at later_mask to know which).
> 
> Change cpudl_find() return type accordingly.

Hi,

Much better. Thank you very much. I will change it.

> 
> > Signed-off-by: Byungchul Park <byungchul.park@lge.com>
> > ---
> >  kernel/sched/cpudeadline.c | 26 +++++++++++++-------------
> >  kernel/sched/deadline.c    |  6 +++---
> >  2 files changed, 16 insertions(+), 16 deletions(-)
> > 
> > diff --git a/kernel/sched/cpudeadline.c b/kernel/sched/cpudeadline.c
> > index fba235c..7408cbe 100644
> > --- a/kernel/sched/cpudeadline.c
> > +++ b/kernel/sched/cpudeadline.c
> > @@ -119,29 +119,29 @@ static inline int cpudl_maximum(struct cpudl *cp)
> >   * @p: the task
> >   * @later_mask: a mask to fill in with the selected CPUs (or NULL)
> >   *
> > - * Returns: int - best CPU (heap maximum if suitable)
> > + * Returns: (int)bool - CPUs were found
> 
> Why not simply bool?

I just did it same as rt.

> Thanks,
> 
> - Juri

[tip:sched/core] sched/deadline: Change return value of cpudl_find()

[tip-bot for Byungchul Park]

Commit-ID:  3261ed0b25098f92d36d5ad14524254d8c7fba54
Gitweb:     http://git.kernel.org/tip/3261ed0b25098f92d36d5ad14524254d8c7fba54
Author:     Byungchul Park <byungchul.park@lge.com>
AuthorDate: Tue, 23 May 2017 11:00:57 +0900
Committer:  Ingo Molnar <mingo@kernel.org>
CommitDate: Thu, 10 Aug 2017 12:18:17 +0200

sched/deadline: Change return value of cpudl_find()

cpudl_find() users are only interested in knowing if suitable CPU(s)
were found or not (and then they look at later_mask to know which).

Change cpudl_find() return type accordingly. Aligns with rt code.

Signed-off-by: Byungchul Park <byungchul.park@lge.com>
Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
Cc: <bristot@redhat.com>
Cc: <juri.lelli@gmail.com>
Cc: <kernel-team@lge.com>
Cc: <rostedt@goodmis.org>
Cc: Linus Torvalds <torvalds@linux-foundation.org>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Thomas Gleixner <tglx@linutronix.de>
Link: http://lkml.kernel.org/r/1495504859-10960-3-git-send-email-byungchul.park@lge.com
Signed-off-by: Ingo Molnar <mingo@kernel.org>
---
 kernel/sched/cpudeadline.c | 26 +++++++++++++-------------
 kernel/sched/deadline.c    |  6 +++---
 2 files changed, 16 insertions(+), 16 deletions(-)

diff --git a/kernel/sched/cpudeadline.c b/kernel/sched/cpudeadline.c
index bdf448b..8d9562d 100644
--- a/kernel/sched/cpudeadline.c
+++ b/kernel/sched/cpudeadline.c
@@ -119,29 +119,29 @@ static inline int cpudl_maximum(struct cpudl *cp)
  * @p: the task
  * @later_mask: a mask to fill in with the selected CPUs (or NULL)
  *
- * Returns: int - best CPU (heap maximum if suitable)
+ * Returns: int - CPUs were found
  */
 int cpudl_find(struct cpudl *cp, struct task_struct *p,
 	       struct cpumask *later_mask)
 {
-	int best_cpu = -1;
 	const struct sched_dl_entity *dl_se = &p->dl;
 
 	if (later_mask &&
 	    cpumask_and(later_mask, cp->free_cpus, &p->cpus_allowed)) {
-		best_cpu = cpumask_any(later_mask);
-		goto out;
-	} else if (cpumask_test_cpu(cpudl_maximum(cp), &p->cpus_allowed) &&
-			dl_time_before(dl_se->deadline, cp->elements[0].dl)) {
-		best_cpu = cpudl_maximum(cp);
-		if (later_mask)
-			cpumask_set_cpu(best_cpu, later_mask);
-	}
+		return 1;
+	} else {
+		int best_cpu = cpudl_maximum(cp);
+		WARN_ON(best_cpu != -1 && !cpu_present(best_cpu));
 
-out:
-	WARN_ON(best_cpu != -1 && !cpu_present(best_cpu));
+		if (cpumask_test_cpu(best_cpu, &p->cpus_allowed) &&
+		    dl_time_before(dl_se->deadline, cp->elements[0].dl)) {
+			if (later_mask)
+				cpumask_set_cpu(best_cpu, later_mask);
 
-	return best_cpu;
+			return 1;
+		}
+	}
+	return 0;
 }
 
 /*
diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
index ac07d7c..d05bd94 100644
--- a/kernel/sched/deadline.c
+++ b/kernel/sched/deadline.c
@@ -1594,7 +1594,7 @@ static void check_preempt_equal_dl(struct rq *rq, struct task_struct *p)
 	 * let's hope p can move out.
 	 */
 	if (rq->curr->nr_cpus_allowed == 1 ||
-	    cpudl_find(&rq->rd->cpudl, rq->curr, NULL) == -1)
+	    !cpudl_find(&rq->rd->cpudl, rq->curr, NULL))
 		return;
 
 	/*
@@ -1602,7 +1602,7 @@ static void check_preempt_equal_dl(struct rq *rq, struct task_struct *p)
 	 * see if it is pushed or pulled somewhere else.
 	 */
 	if (p->nr_cpus_allowed != 1 &&
-	    cpudl_find(&rq->rd->cpudl, p, NULL) != -1)
+	    cpudl_find(&rq->rd->cpudl, p, NULL))
 		return;
 
 	resched_curr(rq);
@@ -1811,7 +1811,7 @@ static int find_later_rq(struct task_struct *task)
 	 * We have to consider system topology and task affinity
 	 * first, then we can look for a suitable cpu.
 	 */
-	if (cpudl_find(&task_rq(task)->rd->cpudl, task, later_mask) == -1)
+	if (!cpudl_find(&task_rq(task)->rd->cpudl, task, later_mask))
 		return -1;
 
 	/*

[PATCH v5 3/4] 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 | 17 +++++++++++++++++
 1 file changed, 17 insertions(+)

diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
index 0223694..ada264c 100644
--- a/kernel/sched/deadline.c
+++ b/kernel/sched/deadline.c
@@ -1325,6 +1325,7 @@ static int find_later_rq(struct task_struct *task)
 	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))
@@ -1385,6 +1386,15 @@ 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 get more chances to
+				 * check other siblings.
+				 */
+				if (sd->flags & SD_PREFER_SIBLING) {
+					fallback_cpu = best_cpu;
+					continue;
+				}
 				rcu_read_unlock();
 				return best_cpu;
 			}
@@ -1393,6 +1403,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

Re: [PATCH v5 3/4] sched/deadline: Add support for SD_PREFER_SIBLING on find_later_rq()

[Peter Zijlstra]

I picked up the first 2 with edits to the Changelog as suggested
by Juri.

On Tue, May 23, 2017 at 11:00:58AM +0900, Byungchul Park wrote:

> diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
> index 0223694..ada264c 100644
> --- a/kernel/sched/deadline.c
> +++ b/kernel/sched/deadline.c
> @@ -1325,6 +1325,7 @@ static int find_later_rq(struct task_struct *task)
>  	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))
> @@ -1385,6 +1386,15 @@ 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 get more chances to
> +				 * check other siblings.
> +				 */
> +				if (sd->flags & SD_PREFER_SIBLING) {
> +					fallback_cpu = best_cpu;
> +					continue;
> +				}
>  				rcu_read_unlock();
>  				return best_cpu;
>  			}
> @@ -1393,6 +1403,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.
>  	 */


This one I'm not sure on..  at the very least we should exclude all of
the prefer sibling domain when we do the next domain, and if there are
multiple prefer sibling levels, we should only pick the first
fallback_cpu -- there is no point is overriding it with a possible CPU
further away.

I implemented that below -- although the find_cpu() function is really
rather horrible.

But still this isn't quite right, because when we consider this for SMT
(as was the intent here) we'll happily occupy a full sibling core over
finding an empty one.

Now, the problem is that actually doing the right thing quickly ends up
very expensive, we'd have to scan the entire cache domain at least once,
so maybe this is good enough.. no idea :/


---
--- a/kernel/sched/deadline.c
+++ b/kernel/sched/deadline.c
@@ -1793,12 +1793,35 @@ static struct task_struct *pick_earliest
 
 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))
@@ -1850,8 +1873,7 @@ static int find_later_rq(struct task_str
 				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
@@ -1859,6 +1881,17 @@ static int find_later_rq(struct task_str
 			 * already under consideration through later_mask.
 			 */
 			if (best_cpu < nr_cpu_ids) {
+				/*
+				 * If current domain is SD_PREFER_SIBLING
+				 * flaged, we have to get more chances to
+				 * check other siblings.
+				 */
+				if (sd->flags & SD_PREFER_SIBLING) {
+					prefer = sd;
+					if (fallback_cpu == -1)
+						fallback_cpu = best_cpu;
+					continue;
+				}
 				rcu_read_unlock();
 				return best_cpu;
 			}
@@ -1867,6 +1900,13 @@ static int find_later_rq(struct task_str
 	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.
 	 */

Re: [PATCH v5 3/4] sched/deadline: Add support for SD_PREFER_SIBLING on find_later_rq()

[Byungchul Park]

On Thu, Aug 03, 2017 at 02:03:34PM +0200, Peter Zijlstra wrote:
> This one I'm not sure on..  at the very least we should exclude all of
> the prefer sibling domain when we do the next domain, and if there are
> multiple prefer sibling levels, we should only pick the first
> fallback_cpu -- there is no point is overriding it with a possible CPU
> further away.

I agree.

> I implemented that below -- although the find_cpu() function is really
> rather horrible.
> 
> But still this isn't quite right, because when we consider this for SMT
> (as was the intent here) we'll happily occupy a full sibling core over
> finding an empty one.
> 
> Now, the problem is that actually doing the right thing quickly ends up
> very expensive, we'd have to scan the entire cache domain at least once,
> so maybe this is good enough.. no idea :/
> 
> 
> ---
> --- a/kernel/sched/deadline.c
> +++ b/kernel/sched/deadline.c
> @@ -1793,12 +1793,35 @@ static struct task_struct *pick_earliest
>  
>  static DEFINE_PER_CPU(cpumask_var_t, local_cpu_mask_dl);
>  
> +/*
> + * Find the first cpu in: mask & sd & ~prefer
                                          ^
                                Yes, I missed it.

> + */
> +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))
> @@ -1850,8 +1873,7 @@ static int find_later_rq(struct task_str
>  				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
> @@ -1859,6 +1881,17 @@ static int find_later_rq(struct task_str
>  			 * already under consideration through later_mask.
>  			 */
>  			if (best_cpu < nr_cpu_ids) {
> +				/*
> +				 * If current domain is SD_PREFER_SIBLING
> +				 * flaged, we have to get more chances to
> +				 * check other siblings.
> +				 */
> +				if (sd->flags & SD_PREFER_SIBLING) {
> +					prefer = sd;
> +					if (fallback_cpu == -1)
                                        ^
                                     I like the 'if' statement.
                                     I should have done this.

> +						fallback_cpu = best_cpu;
> +					continue;
> +				}
>  				rcu_read_unlock();
>  				return best_cpu;
>  			}

Thank you.

[PATCH v5 4/4] 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 | 17 +++++++++++++++++
 1 file changed, 17 insertions(+)

diff --git a/kernel/sched/rt.c b/kernel/sched/rt.c
index 979b734..6332b2ad 100644
--- a/kernel/sched/rt.c
+++ b/kernel/sched/rt.c
@@ -1624,6 +1624,7 @@ static int find_lowest_rq(struct task_struct *task)
 	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))
@@ -1671,6 +1672,15 @@ static int find_lowest_rq(struct task_struct *task)
 			best_cpu = cpumask_first_and(lowest_mask,
 						     sched_domain_span(sd));
 			if (best_cpu < nr_cpu_ids) {
+				/*
+				 * If current domain is SD_PREFER_SIBLING
+				 * flaged, we have to get more chances to
+				 * check other siblings.
+				 */
+				if (sd->flags & SD_PREFER_SIBLING) {
+					fallback_cpu = best_cpu;
+					continue;
+				}
 				rcu_read_unlock();
 				return best_cpu;
 			}
@@ -1679,6 +1689,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 v5 0/4] Make find_later_rq() choose a closer cpu in topology

[Byungchul Park]

On Tue, May 23, 2017 at 11:00:55AM +0900, Byungchul Park wrote:
> 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.

Hi, Peterz,

I wonder if you remember what I answered your question about applying
this approach into rt policy. Rt *already* works as expected.

And I implemented what you suggested, SD_PREFER_SIBLING. It would be
appriciated to check if I works correctly.

Thank you,
Byungchul

> 
> 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 (4):
>   sched/deadline: Make find_later_rq() choose a closer cpu in topology
>   sched/deadline: Change return value of cpudl_find()
>   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/cpudeadline.c | 26 ++++++++++++-------------
>  kernel/sched/deadline.c    | 48 +++++++++++++++++++++++++++++++---------------
>  kernel/sched/rt.c          | 17 ++++++++++++++++
>  3 files changed, 63 insertions(+), 28 deletions(-)
> 
> -- 
> 1.9.1

Re: [PATCH v5 0/4] Make find_later_rq() choose a closer cpu in topology

[Byungchul Park]

Could you check this patchset considering cpu topology on cpu selection?

On Tue, May 23, 2017 at 11:00:55AM +0900, Byungchul Park wrote:
> 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 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 (4):
>   sched/deadline: Make find_later_rq() choose a closer cpu in topology
>   sched/deadline: Change return value of cpudl_find()
>   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/cpudeadline.c | 26 ++++++++++++-------------
>  kernel/sched/deadline.c    | 48 +++++++++++++++++++++++++++++++---------------
>  kernel/sched/rt.c          | 17 ++++++++++++++++
>  3 files changed, 63 insertions(+), 28 deletions(-)
> 
> -- 
> 1.9.1