* [RESEND PATCH v11 0/2] Make find_later_rq() choose a closer cpu in topology
@ 2018-01-08 6:14 Byungchul Park
2018-01-08 6:14 ` [RESEND PATCH v11 1/2] sched/deadline: Add support for SD_PREFER_SIBLING on find_later_rq() Byungchul Park
2018-01-08 6:14 ` [RESEND PATCH v11 2/2] sched/rt: Add support for SD_PREFER_SIBLING on find_lowest_rq() Byungchul Park
0 siblings, 2 replies; 11+ messages in thread
From: Byungchul Park @ 2018-01-08 6:14 UTC (permalink / raw)
To: peterz, mingo, rostedt
Cc: tglx, raistlin, linux-kernel, juri.lelli, bristot, kernel-team
Change from v10
-. modify a comment a bit as Steven suggested
Change from v9
-. modify a comment a bit so to be more clear as Juri suggested
Change from v8
-. add suggested-by Peterz
-. add several comments
Change from v7
-. fix a trivial typo
-. modify commit messages to explain what it does more clearly
-. simplify code with an existing macro
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 | 82 ++++++++++++++++++++++++++++++++++++++++++++-----
kernel/sched/rt.c | 80 +++++++++++++++++++++++++++++++++++++++++++++--
2 files changed, 152 insertions(+), 10 deletions(-)
--
1.9.1
^ permalink raw reply [flat|nested] 11+ messages in thread
* [RESEND PATCH v11 1/2] sched/deadline: Add support for SD_PREFER_SIBLING on find_later_rq()
2018-01-08 6:14 [RESEND PATCH v11 0/2] Make find_later_rq() choose a closer cpu in topology Byungchul Park
@ 2018-01-08 6:14 ` Byungchul Park
2018-01-10 17:22 ` kbuild test robot
2018-01-08 6:14 ` [RESEND PATCH v11 2/2] sched/rt: Add support for SD_PREFER_SIBLING on find_lowest_rq() Byungchul Park
1 sibling, 1 reply; 11+ messages in thread
From: Byungchul Park @ 2018-01-08 6:14 UTC (permalink / raw)
To: peterz, mingo, rostedt
Cc: tglx, raistlin, linux-kernel, juri.lelli, bristot, kernel-team
It would be better to try to check other siblings first if
SD_PREFER_SIBLING is flaged when pushing tasks - migration.
Suggested-by: Peter Zijlstra <peterz@infradead.org>
Signed-off-by: Byungchul Park <byungchul.park@lge.com>
Acked-by: Juri Lelli <juri.lelli@arm.com>
---
kernel/sched/deadline.c | 82 ++++++++++++++++++++++++++++++++++++++++++++-----
1 file changed, 75 insertions(+), 7 deletions(-)
diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
index 0223694..d619c07 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;
+
+ for_each_cpu(cpu, mask) {
+ 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,15 +1399,37 @@ 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 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 a cpu exists that is in the later_mask and
+ * the current sd span, but not in the prefer sd
+ * span, then that becomes our choice.
+ *
+ * Of course, the latest possible cpu is already
+ * under consideration through later_mask.
*/
+ best_cpu = find_cpu(later_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;
}
@@ -1393,6 +1438,29 @@ 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.
+ *
+ * XXX: Consider the following example, 4 cores SMT2 system:
+ *
+ * LLC [0 - 7]
+ * SMT [0 1][2 3][4 5][6 7]
+ * o x o x x x x x
+ *
+ * where 'o': occupied and 'x': empty.
+ *
+ * A wakeup on cpu0 will exclude cpu1 and choose cpu3, since
+ * cpu1 is in a SD_PREFER_SIBLING sd and cpu3 is not. However,
+ * in this case, cpu4 would have been a better choice, since
+ * cpu3 is a (SMT) thread of an already loaded core.
+ *
+ * Doing it 'right' is difficult and expensive. The current
+ * solution is an acceptable approximation.
+ */
+ 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
^ permalink raw reply related [flat|nested] 11+ messages in thread
* Re: [RESEND PATCH v11 1/2] sched/deadline: Add support for SD_PREFER_SIBLING on find_later_rq()
2018-01-08 6:14 ` [RESEND PATCH v11 1/2] sched/deadline: Add support for SD_PREFER_SIBLING on find_later_rq() Byungchul Park
@ 2018-01-10 17:22 ` kbuild test robot
2018-01-11 7:48 ` Byungchul Park
0 siblings, 1 reply; 11+ messages in thread
From: kbuild test robot @ 2018-01-10 17:22 UTC (permalink / raw)
To: Byungchul Park
Cc: kbuild-all, peterz, mingo, rostedt, tglx, raistlin, linux-kernel,
juri.lelli, bristot, kernel-team
Hi Byungchul,
Thank you for the patch! Perhaps something to improve:
[auto build test WARNING on tip/sched/core]
[also build test WARNING on v4.15-rc7 next-20180110]
[if your patch is applied to the wrong git tree, please drop us a note to help improve the system]
url: https://github.com/0day-ci/linux/commits/Byungchul-Park/sched-deadline-Add-support-for-SD_PREFER_SIBLING-on-find_later_rq/20180110-225946
reproduce:
# apt-get install sparse
make ARCH=x86_64 allmodconfig
make C=1 CF=-D__CHECK_ENDIAN__
sparse warnings: (new ones prefixed by >>)
kernel/sched/sched.h:2104:16: sparse: incompatible types in comparison expression (different address spaces)
kernel/sched/sched.h:2104:16: sparse: incompatible types in comparison expression (different address spaces)
kernel/sched/sched.h:2104:16: sparse: incompatible types in comparison expression (different address spaces)
kernel/sched/sched.h:2104:16: sparse: incompatible types in comparison expression (different address spaces)
kernel/sched/sched.h:2104:16: sparse: incompatible types in comparison expression (different address spaces)
kernel/sched/sched.h:2104:16: sparse: incompatible types in comparison expression (different address spaces)
kernel/sched/sched.h:2104:16: sparse: incompatible types in comparison expression (different address spaces)
kernel/sched/sched.h:2104:16: sparse: incompatible types in comparison expression (different address spaces)
kernel/sched/deadline.c:1124:5: sparse: symbol 'grub_reclaim' was not declared. Should it be
kernel/sched/sched.h:2104:16: sparse: incompatible types in comparison expression (different address spaces)
kernel/sched/sched.h:2104:16: sparse: incompatible types in comparison expression (different address spaces)
kernel/sched/sched.h:2104:16: sparse: incompatible types in comparison expression (different address spaces)
kernel/sched/deadline.c:1916:9: sparse: incompatible types in comparison expression (different address spaces)
kernel/sched/sched.h:2104:16: sparse: incompatible types in comparison expression (different address spaces)
>> kernel/sched/deadline.c:1857:55: sparse: incorrect type in argument 1 (different modifiers) @@ expected struct sched_domain @@ got structstruct sched_domain @@
kernel/sched/deadline.c:1857:55: expected struct sched_domain
kernel/sched/deadline.c:1857:55: got struct sched_domain const
kernel/sched/deadline.c:1858:64: sparse: incorrect type in argument 1 (different modifiers) @@ expected struct sched_domain @@ got structstruct sched_domain @@
kernel/sched/deadline.c:1858:64: expected struct sched_domain
kernel/sched/deadline.c:1858:64: got struct sched_domain const
kernel/sched/deadline.c:563:9: sparse: context imbalance in 'dl_task_offline_migration' - unexpected unlock
kernel/sched/deadline.c:2060:9: sparse: context imbalance in 'find_lock_later_rq' - different lock contexts for basic block
kernel/sched/deadline.c:2155:23: sparse: context imbalance in 'push_dl_task' - unexpected unlock
kernel/sched/sched.h:1856:17: sparse: context imbalance in 'pull_dl_task' - unexpected unlock
kernel/sched/deadline.c: In function 'find_cpu':
kernel/sched/deadline.c:1857:48: warning: passing argument 1 of 'sched_domain_span' discards 'const' qualifier from pointer target type
const struct cpumask = sched_domain_span(sd);
^~
In file included from kernel/sched/sched.h:6:0,
from kernel/sched/deadline.c:18:
include/linux/sched/topology.h:160:31: note: expected 'struct sched_domain but argument is of type 'const struct sched_domain
static inline struct cpumask sched_domain
^~~~~~~~~~~~~~~~~
kernel/sched/deadline.c:1858:57: warning: passing argument 1 of 'sched_domain_span' discards 'const' qualifier from pointer target type
const struct cpumask = prefer sched_domain_span(prefer) : NULL;
^~~~~~
In file included from kernel/sched/sched.h:6:0,
from kernel/sched/deadline.c:18:
include/linux/sched/topology.h:160:31: note: expected 'struct sched_domain but argument is of type 'const struct sched_domain
static inline struct cpumask sched_domain
^~~~~~~~~~~~~~~~~
vim +1857 kernel/sched/deadline.c
1849
1850 /*
1851 * Find the first cpu in: mask & sd & ~prefer
1852 */
1853 static int find_cpu(const struct cpumask *mask,
1854 const struct sched_domain *sd,
1855 const struct sched_domain *prefer)
1856 {
> 1857 const struct cpumask *sds = sched_domain_span(sd);
1858 const struct cpumask *ps = prefer ? sched_domain_span(prefer) : NULL;
1859 int cpu;
1860
1861 for_each_cpu(cpu, mask) {
1862 if (!cpumask_test_cpu(cpu, sds))
1863 continue;
1864 if (ps && cpumask_test_cpu(cpu, ps))
1865 continue;
1866 break;
1867 }
1868
1869 return cpu;
1870 }
1871
---
0-DAY kernel test infrastructure Open Source Technology Center
https://lists.01.org/pipermail/kbuild-all Intel Corporation
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [RESEND PATCH v11 1/2] sched/deadline: Add support for SD_PREFER_SIBLING on find_later_rq()
2018-01-10 17:22 ` kbuild test robot
@ 2018-01-11 7:48 ` Byungchul Park
0 siblings, 0 replies; 11+ messages in thread
From: Byungchul Park @ 2018-01-11 7:48 UTC (permalink / raw)
To: kbuild test robot
Cc: kbuild-all, peterz, mingo, rostedt, tglx, raistlin, linux-kernel,
juri.lelli, bristot, kernel-team
On 1/11/2018 2:22 AM, kbuild test robot wrote:
> Hi Byungchul,
>
> Thank you for the patch! Perhaps something to improve:
>
> [auto build test WARNING on tip/sched/core]
> [also build test WARNING on v4.15-rc7 next-20180110]
> [if your patch is applied to the wrong git tree, please drop us a note to help improve the system]
>
> url: https://github.com/0day-ci/linux/commits/Byungchul-Park/sched-deadline-Add-support-for-SD_PREFER_SIBLING-on-find_later_rq/20180110-225946
> reproduce:
> # apt-get install sparse
> make ARCH=x86_64 allmodconfig
> make C=1 CF=-D__CHECK_ENDIAN__
>
>
> sparse warnings: (new ones prefixed by >>)
>
> kernel/sched/sched.h:2104:16: sparse: incompatible types in comparison expression (different address spaces)
> kernel/sched/sched.h:2104:16: sparse: incompatible types in comparison expression (different address spaces)
> kernel/sched/sched.h:2104:16: sparse: incompatible types in comparison expression (different address spaces)
> kernel/sched/sched.h:2104:16: sparse: incompatible types in comparison expression (different address spaces)
> kernel/sched/sched.h:2104:16: sparse: incompatible types in comparison expression (different address spaces)
> kernel/sched/sched.h:2104:16: sparse: incompatible types in comparison expression (different address spaces)
> kernel/sched/sched.h:2104:16: sparse: incompatible types in comparison expression (different address spaces)
> kernel/sched/sched.h:2104:16: sparse: incompatible types in comparison expression (different address spaces)
> kernel/sched/deadline.c:1124:5: sparse: symbol 'grub_reclaim' was not declared. Should it be
> kernel/sched/sched.h:2104:16: sparse: incompatible types in comparison expression (different address spaces)
> kernel/sched/sched.h:2104:16: sparse: incompatible types in comparison expression (different address spaces)
> kernel/sched/sched.h:2104:16: sparse: incompatible types in comparison expression (different address spaces)
> kernel/sched/deadline.c:1916:9: sparse: incompatible types in comparison expression (different address spaces)
> kernel/sched/sched.h:2104:16: sparse: incompatible types in comparison expression (different address spaces)
>>> kernel/sched/deadline.c:1857:55: sparse: incorrect type in argument 1 (different modifiers) @@ expected struct sched_domain @@ got structstruct sched_domain @@
> kernel/sched/deadline.c:1857:55: expected struct sched_domain
> kernel/sched/deadline.c:1857:55: got struct sched_domain const
> kernel/sched/deadline.c:1858:64: sparse: incorrect type in argument 1 (different modifiers) @@ expected struct sched_domain @@ got structstruct sched_domain @@
> kernel/sched/deadline.c:1858:64: expected struct sched_domain
> kernel/sched/deadline.c:1858:64: got struct sched_domain const
> kernel/sched/deadline.c:563:9: sparse: context imbalance in 'dl_task_offline_migration' - unexpected unlock
> kernel/sched/deadline.c:2060:9: sparse: context imbalance in 'find_lock_later_rq' - different lock contexts for basic block
> kernel/sched/deadline.c:2155:23: sparse: context imbalance in 'push_dl_task' - unexpected unlock
> kernel/sched/sched.h:1856:17: sparse: context imbalance in 'pull_dl_task' - unexpected unlock
> kernel/sched/deadline.c: In function 'find_cpu':
> kernel/sched/deadline.c:1857:48: warning: passing argument 1 of 'sched_domain_span' discards 'const' qualifier from pointer target type
> const struct cpumask = sched_domain_span(sd);
> ^~
> In file included from kernel/sched/sched.h:6:0,
> from kernel/sched/deadline.c:18:
> include/linux/sched/topology.h:160:31: note: expected 'struct sched_domain but argument is of type 'const struct sched_domain
> static inline struct cpumask sched_domain
> ^~~~~~~~~~~~~~~~~
> kernel/sched/deadline.c:1858:57: warning: passing argument 1 of 'sched_domain_span' discards 'const' qualifier from pointer target type
> const struct cpumask = prefer sched_domain_span(prefer) : NULL;
> ^~~~~~
> In file included from kernel/sched/sched.h:6:0,
> from kernel/sched/deadline.c:18:
> include/linux/sched/topology.h:160:31: note: expected 'struct sched_domain but argument is of type 'const struct sched_domain
> static inline struct cpumask sched_domain
> ^~~~~~~~~~~~~~~~~
>
> vim +1857 kernel/sched/deadline.c
>
> 1849
> 1850 /*
> 1851 * Find the first cpu in: mask & sd & ~prefer
> 1852 */
> 1853 static int find_cpu(const struct cpumask *mask,
> 1854 const struct sched_domain *sd,
> 1855 const struct sched_domain *prefer)
> 1856 {
>> 1857 const struct cpumask *sds = sched_domain_span(sd);
Thanks a lot.
I will fix and respin it.
I'm gonna change prototype of sched_domain_span() rather than
find_cpu() to avoid the warning. Is it ok to fix it that way?
> 1858 const struct cpumask *ps = prefer ? sched_domain_span(prefer) : NULL;
> 1859 int cpu;
> 1860
> 1861 for_each_cpu(cpu, mask) {
> 1862 if (!cpumask_test_cpu(cpu, sds))
> 1863 continue;
> 1864 if (ps && cpumask_test_cpu(cpu, ps))
> 1865 continue;
> 1866 break;
> 1867 }
> 1868
> 1869 return cpu;
> 1870 }
> 1871
>
> ---
> 0-DAY kernel test infrastructure Open Source Technology Center
> https://lists.01.org/pipermail/kbuild-all Intel Corporation
>
--
Thanks,
Byungchul
^ permalink raw reply [flat|nested] 11+ messages in thread
* [RESEND PATCH v11 2/2] sched/rt: Add support for SD_PREFER_SIBLING on find_lowest_rq()
2018-01-08 6:14 [RESEND PATCH v11 0/2] Make find_later_rq() choose a closer cpu in topology Byungchul Park
2018-01-08 6:14 ` [RESEND PATCH v11 1/2] sched/deadline: Add support for SD_PREFER_SIBLING on find_later_rq() Byungchul Park
@ 2018-01-08 6:14 ` Byungchul Park
2018-01-10 17:45 ` kbuild test robot
1 sibling, 1 reply; 11+ messages in thread
From: Byungchul Park @ 2018-01-08 6:14 UTC (permalink / raw)
To: peterz, mingo, rostedt
Cc: tglx, raistlin, linux-kernel, juri.lelli, bristot, kernel-team
It would be better to try to check other siblings first if
SD_PREFER_SIBLING is flaged when pushing tasks - migration.
Suggested-by: Peter Zijlstra <peterz@infradead.org>
Signed-off-by: Byungchul Park <byungchul.park@lge.com>
Reviewed-by: Steven Rostedt (VMware) <rostedt@goodmis.org>
---
kernel/sched/rt.c | 80 ++++++++++++++++++++++++++++++++++++++++++++++++++++---
1 file changed, 77 insertions(+), 3 deletions(-)
diff --git a/kernel/sched/rt.c b/kernel/sched/rt.c
index 979b734..a32e36d 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;
+
+ for_each_cpu(cpu, mask) {
+ 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,37 @@ static int find_lowest_rq(struct task_struct *task)
return this_cpu;
}
- best_cpu = cpumask_first_and(lowest_mask,
- sched_domain_span(sd));
+ /*
+ * If a cpu exists that is in the lowest_mask and
+ * the current sd span, but not in the prefer sd
+ * span, then that becomes our choice.
+ *
+ * Of course, the lowest possible cpu is already
+ * under consideration through lowest_mask.
+ */
+ 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 +1730,29 @@ static int find_lowest_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.
+ *
+ * XXX: Consider the following example, 4 cores SMT2 system:
+ *
+ * LLC [0 - 7]
+ * SMT [0 1][2 3][4 5][6 7]
+ * o x o x x x x x
+ *
+ * where 'o': occupied and 'x': empty.
+ *
+ * A wakeup on cpu0 will exclude cpu1 and choose cpu3, since
+ * cpu1 is in a SD_PREFER_SIBLING sd and cpu3 is not. However,
+ * in this case, cpu4 would have been a better choice, since
+ * cpu3 is a (SMT) thread of an already loaded core.
+ *
+ * Doing it 'right' is difficult and expensive. The current
+ * solution is an acceptable approximation.
+ */
+ 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
^ permalink raw reply related [flat|nested] 11+ messages in thread
* Re: [RESEND PATCH v11 2/2] sched/rt: Add support for SD_PREFER_SIBLING on find_lowest_rq()
2018-01-08 6:14 ` [RESEND PATCH v11 2/2] sched/rt: Add support for SD_PREFER_SIBLING on find_lowest_rq() Byungchul Park
@ 2018-01-10 17:45 ` kbuild test robot
0 siblings, 0 replies; 11+ messages in thread
From: kbuild test robot @ 2018-01-10 17:45 UTC (permalink / raw)
To: Byungchul Park
Cc: kbuild-all, peterz, mingo, rostedt, tglx, raistlin, linux-kernel,
juri.lelli, bristot, kernel-team
Hi Byungchul,
Thank you for the patch! Perhaps something to improve:
[auto build test WARNING on tip/sched/core]
[also build test WARNING on v4.15-rc7 next-20180110]
[if your patch is applied to the wrong git tree, please drop us a note to help improve the system]
url: https://github.com/0day-ci/linux/commits/Byungchul-Park/sched-deadline-Add-support-for-SD_PREFER_SIBLING-on-find_later_rq/20180110-225946
reproduce:
# apt-get install sparse
make ARCH=x86_64 allmodconfig
make C=1 CF=-D__CHECK_ENDIAN__
sparse warnings: (new ones prefixed by >>)
kernel/sched/sched.h:2104:16: sparse: incompatible types in comparison expression (different address spaces)
kernel/sched/rt.c:1681:9: sparse: incompatible types in comparison expression (different address spaces)
>> kernel/sched/rt.c:1629:55: sparse: incorrect type in argument 1 (different modifiers) @@ expected struct sched_domain @@ got structstruct sched_domain @@
kernel/sched/rt.c:1629:55: expected struct sched_domain
kernel/sched/rt.c:1629:55: got struct sched_domain const
kernel/sched/rt.c:1630:64: sparse: incorrect type in argument 1 (different modifiers) @@ expected struct sched_domain @@ got structstruct sched_domain @@
kernel/sched/rt.c:1630:64: expected struct sched_domain
kernel/sched/rt.c:1630:64: got struct sched_domain const
kernel/sched/rt.c:1824:9: sparse: context imbalance in 'find_lock_lowest_rq' - different lock contexts for basic block
kernel/sched/rt.c:1919:9: sparse: context imbalance in 'push_rt_task' - unexpected unlock
kernel/sched/rt.c: In function 'find_cpu':
kernel/sched/rt.c:1629:48: warning: passing argument 1 of 'sched_domain_span' discards 'const' qualifier from pointer target type
const struct cpumask = sched_domain_span(sd);
^~
In file included from kernel/sched/sched.h:6:0,
from kernel/sched/rt.c:7:
include/linux/sched/topology.h:160:31: note: expected 'struct sched_domain but argument is of type 'const struct sched_domain
static inline struct cpumask sched_domain
^~~~~~~~~~~~~~~~~
kernel/sched/rt.c:1630:57: warning: passing argument 1 of 'sched_domain_span' discards 'const' qualifier from pointer target type
const struct cpumask = prefer sched_domain_span(prefer) : NULL;
^~~~~~
In file included from kernel/sched/sched.h:6:0,
from kernel/sched/rt.c:7:
include/linux/sched/topology.h:160:31: note: expected 'struct sched_domain but argument is of type 'const struct sched_domain
static inline struct cpumask sched_domain
^~~~~~~~~~~~~~~~~
vim +1629 kernel/sched/rt.c
1621
1622 /*
1623 * Find the first cpu in: mask & sd & ~prefer
1624 */
1625 static int find_cpu(const struct cpumask *mask,
1626 const struct sched_domain *sd,
1627 const struct sched_domain *prefer)
1628 {
> 1629 const struct cpumask *sds = sched_domain_span(sd);
1630 const struct cpumask *ps = prefer ? sched_domain_span(prefer) : NULL;
1631 int cpu;
1632
1633 for_each_cpu(cpu, mask) {
1634 if (!cpumask_test_cpu(cpu, sds))
1635 continue;
1636 if (ps && cpumask_test_cpu(cpu, ps))
1637 continue;
1638 break;
1639 }
1640
1641 return cpu;
1642 }
1643
---
0-DAY kernel test infrastructure Open Source Technology Center
https://lists.01.org/pipermail/kbuild-all Intel Corporation
^ permalink raw reply [flat|nested] 11+ messages in thread
* [RESEND PATCH v11 0/2] Make find_later_rq() choose a closer cpu in topology
@ 2018-05-09 6:44 Byungchul Park
2018-05-09 6:44 ` [RESEND PATCH v11 2/2] sched/rt: Add support for SD_PREFER_SIBLING on find_lowest_rq() Byungchul Park
0 siblings, 1 reply; 11+ messages in thread
From: Byungchul Park @ 2018-05-09 6:44 UTC (permalink / raw)
To: peterz, mingo, rostedt
Cc: tglx, raistlin, linux-kernel, juri.lelli, bristot, kernel-team
Change from v10
-. modify a comment a bit as Steven suggested
Change from v9
-. modify a comment a bit so to be more clear as Juri suggested
Change from v8
-. add suggested-by Peterz
-. add several comments
Change from v7
-. fix a trivial typo
-. modify commit messages to explain what it does more clearly
-. simplify code with an existing macro
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 | 82 ++++++++++++++++++++++++++++++++++++++++++++-----
kernel/sched/rt.c | 80 +++++++++++++++++++++++++++++++++++++++++++++--
2 files changed, 152 insertions(+), 10 deletions(-)
--
1.9.1
^ permalink raw reply [flat|nested] 11+ messages in thread
* [RESEND PATCH v11 2/2] sched/rt: Add support for SD_PREFER_SIBLING on find_lowest_rq()
2018-05-09 6:44 [RESEND PATCH v11 0/2] Make find_later_rq() choose a closer cpu in topology Byungchul Park
@ 2018-05-09 6:44 ` Byungchul Park
0 siblings, 0 replies; 11+ messages in thread
From: Byungchul Park @ 2018-05-09 6:44 UTC (permalink / raw)
To: peterz, mingo, rostedt
Cc: tglx, raistlin, linux-kernel, juri.lelli, bristot, kernel-team
It would be better to try to check other siblings first if
SD_PREFER_SIBLING is flaged when pushing tasks - migration.
Suggested-by: Peter Zijlstra <peterz@infradead.org>
Signed-off-by: Byungchul Park <byungchul.park@lge.com>
Reviewed-by: Steven Rostedt (VMware) <rostedt@goodmis.org>
---
kernel/sched/rt.c | 80 ++++++++++++++++++++++++++++++++++++++++++++++++++++---
1 file changed, 77 insertions(+), 3 deletions(-)
diff --git a/kernel/sched/rt.c b/kernel/sched/rt.c
index 979b734..a32e36d 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;
+
+ for_each_cpu(cpu, mask) {
+ 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,37 @@ static int find_lowest_rq(struct task_struct *task)
return this_cpu;
}
- best_cpu = cpumask_first_and(lowest_mask,
- sched_domain_span(sd));
+ /*
+ * If a cpu exists that is in the lowest_mask and
+ * the current sd span, but not in the prefer sd
+ * span, then that becomes our choice.
+ *
+ * Of course, the lowest possible cpu is already
+ * under consideration through lowest_mask.
+ */
+ 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 +1730,29 @@ static int find_lowest_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.
+ *
+ * XXX: Consider the following example, 4 cores SMT2 system:
+ *
+ * LLC [0 - 7]
+ * SMT [0 1][2 3][4 5][6 7]
+ * o x o x x x x x
+ *
+ * where 'o': occupied and 'x': empty.
+ *
+ * A wakeup on cpu0 will exclude cpu1 and choose cpu3, since
+ * cpu1 is in a SD_PREFER_SIBLING sd and cpu3 is not. However,
+ * in this case, cpu4 would have been a better choice, since
+ * cpu3 is a (SMT) thread of an already loaded core.
+ *
+ * Doing it 'right' is difficult and expensive. The current
+ * solution is an acceptable approximation.
+ */
+ 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
^ permalink raw reply related [flat|nested] 11+ messages in thread
* [RESEND PATCH v11 0/2] Make find_later_rq() choose a closer cpu in topology
@ 2017-12-28 23:32 Byungchul Park
2017-12-28 23:32 ` [RESEND PATCH v11 2/2] sched/rt: Add support for SD_PREFER_SIBLING on find_lowest_rq() Byungchul Park
0 siblings, 1 reply; 11+ messages in thread
From: Byungchul Park @ 2017-12-28 23:32 UTC (permalink / raw)
To: peterz, mingo, rostedt
Cc: tglx, raistlin, linux-kernel, juri.lelli, bristot, kernel-team
Change from v10
-. modify a comment a bit as Steven suggested
Change from v9
-. modify a comment a bit so to be more clear as Juri suggested
Change from v8
-. add suggested-by Peterz
-. add several comments
Change from v7
-. fix a trivial typo
-. modify commit messages to explain what it does more clearly
-. simplify code with an existing macro
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 | 82 ++++++++++++++++++++++++++++++++++++++++++++-----
kernel/sched/rt.c | 80 +++++++++++++++++++++++++++++++++++++++++++++--
2 files changed, 152 insertions(+), 10 deletions(-)
--
1.9.1
^ permalink raw reply [flat|nested] 11+ messages in thread
* [RESEND PATCH v11 2/2] sched/rt: Add support for SD_PREFER_SIBLING on find_lowest_rq()
2017-12-28 23:32 [RESEND PATCH v11 0/2] Make find_later_rq() choose a closer cpu in topology Byungchul Park
@ 2017-12-28 23:32 ` Byungchul Park
0 siblings, 0 replies; 11+ messages in thread
From: Byungchul Park @ 2017-12-28 23:32 UTC (permalink / raw)
To: peterz, mingo, rostedt
Cc: tglx, raistlin, linux-kernel, juri.lelli, bristot, kernel-team
It would be better to try to check other siblings first if
SD_PREFER_SIBLING is flaged when pushing tasks - migration.
Suggested-by: Peter Zijlstra <peterz@infradead.org>
Signed-off-by: Byungchul Park <byungchul.park@lge.com>
Reviewed-by: Steven Rostedt (VMware) <rostedt@goodmis.org>
---
kernel/sched/rt.c | 80 ++++++++++++++++++++++++++++++++++++++++++++++++++++---
1 file changed, 77 insertions(+), 3 deletions(-)
diff --git a/kernel/sched/rt.c b/kernel/sched/rt.c
index 979b734..a32e36d 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;
+
+ for_each_cpu(cpu, mask) {
+ 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,37 @@ static int find_lowest_rq(struct task_struct *task)
return this_cpu;
}
- best_cpu = cpumask_first_and(lowest_mask,
- sched_domain_span(sd));
+ /*
+ * If a cpu exists that is in the lowest_mask and
+ * the current sd span, but not in the prefer sd
+ * span, then that becomes our choice.
+ *
+ * Of course, the lowest possible cpu is already
+ * under consideration through lowest_mask.
+ */
+ 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 +1730,29 @@ static int find_lowest_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.
+ *
+ * XXX: Consider the following example, 4 cores SMT2 system:
+ *
+ * LLC [0 - 7]
+ * SMT [0 1][2 3][4 5][6 7]
+ * o x o x x x x x
+ *
+ * where 'o': occupied and 'x': empty.
+ *
+ * A wakeup on cpu0 will exclude cpu1 and choose cpu3, since
+ * cpu1 is in a SD_PREFER_SIBLING sd and cpu3 is not. However,
+ * in this case, cpu4 would have been a better choice, since
+ * cpu3 is a (SMT) thread of an already loaded core.
+ *
+ * Doing it 'right' is difficult and expensive. The current
+ * solution is an acceptable approximation.
+ */
+ 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
^ permalink raw reply related [flat|nested] 11+ messages in thread
* [RESEND PATCH v11 0/2] Make find_later_rq() choose a closer cpu in topology
@ 2017-12-19 1:20 Byungchul Park
2017-12-19 1:20 ` [RESEND PATCH v11 2/2] sched/rt: Add support for SD_PREFER_SIBLING on find_lowest_rq() Byungchul Park
0 siblings, 1 reply; 11+ messages in thread
From: Byungchul Park @ 2017-12-19 1:20 UTC (permalink / raw)
To: peterz, mingo, rostedt
Cc: tglx, raistlin, linux-kernel, juri.lelli, bristot, kernel-team
Change from v10
-. modify a comment a bit as Steven suggested
Change from v9
-. modify a comment a bit so to be more clear as Juri suggested
Change from v8
-. add suggested-by Peterz
-. add several comments
Change from v7
-. fix a trivial typo
-. modify commit messages to explain what it does more clearly
-. simplify code with an existing macro
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 | 82 ++++++++++++++++++++++++++++++++++++++++++++-----
kernel/sched/rt.c | 80 +++++++++++++++++++++++++++++++++++++++++++++--
2 files changed, 152 insertions(+), 10 deletions(-)
--
1.9.1
^ permalink raw reply [flat|nested] 11+ messages in thread
* [RESEND PATCH v11 2/2] sched/rt: Add support for SD_PREFER_SIBLING on find_lowest_rq()
2017-12-19 1:20 [RESEND PATCH v11 0/2] Make find_later_rq() choose a closer cpu in topology Byungchul Park
@ 2017-12-19 1:20 ` Byungchul Park
0 siblings, 0 replies; 11+ messages in thread
From: Byungchul Park @ 2017-12-19 1:20 UTC (permalink / raw)
To: peterz, mingo, rostedt
Cc: tglx, raistlin, linux-kernel, juri.lelli, bristot, kernel-team
It would be better to try to check other siblings first if
SD_PREFER_SIBLING is flaged when pushing tasks - migration.
Suggested-by: Peter Zijlstra <peterz@infradead.org>
Signed-off-by: Byungchul Park <byungchul.park@lge.com>
Reviewed-by: Steven Rostedt (VMware) <rostedt@goodmis.org>
---
kernel/sched/rt.c | 80 ++++++++++++++++++++++++++++++++++++++++++++++++++++---
1 file changed, 77 insertions(+), 3 deletions(-)
diff --git a/kernel/sched/rt.c b/kernel/sched/rt.c
index 979b734..a32e36d 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;
+
+ for_each_cpu(cpu, mask) {
+ 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,37 @@ static int find_lowest_rq(struct task_struct *task)
return this_cpu;
}
- best_cpu = cpumask_first_and(lowest_mask,
- sched_domain_span(sd));
+ /*
+ * If a cpu exists that is in the lowest_mask and
+ * the current sd span, but not in the prefer sd
+ * span, then that becomes our choice.
+ *
+ * Of course, the lowest possible cpu is already
+ * under consideration through lowest_mask.
+ */
+ 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 +1730,29 @@ static int find_lowest_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.
+ *
+ * XXX: Consider the following example, 4 cores SMT2 system:
+ *
+ * LLC [0 - 7]
+ * SMT [0 1][2 3][4 5][6 7]
+ * o x o x x x x x
+ *
+ * where 'o': occupied and 'x': empty.
+ *
+ * A wakeup on cpu0 will exclude cpu1 and choose cpu3, since
+ * cpu1 is in a SD_PREFER_SIBLING sd and cpu3 is not. However,
+ * in this case, cpu4 would have been a better choice, since
+ * cpu3 is a (SMT) thread of an already loaded core.
+ *
+ * Doing it 'right' is difficult and expensive. The current
+ * solution is an acceptable approximation.
+ */
+ 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
^ permalink raw reply related [flat|nested] 11+ messages in thread
* [RESEND PATCH v11 0/2] Make find_later_rq() choose a closer cpu in topology
@ 2017-11-02 1:25 Byungchul Park
2017-11-02 1:25 ` [RESEND PATCH v11 2/2] sched/rt: Add support for SD_PREFER_SIBLING on find_lowest_rq() Byungchul Park
0 siblings, 1 reply; 11+ messages in thread
From: Byungchul Park @ 2017-11-02 1:25 UTC (permalink / raw)
To: peterz, mingo, rostedt
Cc: tglx, raistlin, linux-kernel, juri.lelli, kernel-team
Change from v10
-. modify a comment a bit as Steven suggested
Change from v9
-. modify a comment a bit so to be more clear as Juri suggested
Change from v8
-. add suggested-by Peterz
-. add several comments
Change from v7
-. fix a trivial typo
-. modify commit messages to explain what it does more clearly
-. simplify code with an existing macro
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 | 82 ++++++++++++++++++++++++++++++++++++++++++++-----
kernel/sched/rt.c | 80 +++++++++++++++++++++++++++++++++++++++++++++--
2 files changed, 152 insertions(+), 10 deletions(-)
--
1.9.1
^ permalink raw reply [flat|nested] 11+ messages in thread
* [RESEND PATCH v11 2/2] sched/rt: Add support for SD_PREFER_SIBLING on find_lowest_rq()
2017-11-02 1:25 [RESEND PATCH v11 0/2] Make find_later_rq() choose a closer cpu in topology Byungchul Park
@ 2017-11-02 1:25 ` Byungchul Park
0 siblings, 0 replies; 11+ messages in thread
From: Byungchul Park @ 2017-11-02 1:25 UTC (permalink / raw)
To: peterz, mingo, rostedt
Cc: tglx, raistlin, linux-kernel, juri.lelli, kernel-team
It would be better to try to check other siblings first if
SD_PREFER_SIBLING is flaged when pushing tasks - migration.
Suggested-by: Peter Zijlstra <peterz@infradead.org>
Signed-off-by: Byungchul Park <byungchul.park@lge.com>
Reviewed-by: Steven Rostedt (VMware) <rostedt@goodmis.org>
---
kernel/sched/rt.c | 80 ++++++++++++++++++++++++++++++++++++++++++++++++++++---
1 file changed, 77 insertions(+), 3 deletions(-)
diff --git a/kernel/sched/rt.c b/kernel/sched/rt.c
index 979b734..a32e36d 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;
+
+ for_each_cpu(cpu, mask) {
+ 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,37 @@ static int find_lowest_rq(struct task_struct *task)
return this_cpu;
}
- best_cpu = cpumask_first_and(lowest_mask,
- sched_domain_span(sd));
+ /*
+ * If a cpu exists that is in the lowest_mask and
+ * the current sd span, but not in the prefer sd
+ * span, then that becomes our choice.
+ *
+ * Of course, the lowest possible cpu is already
+ * under consideration through lowest_mask.
+ */
+ 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 +1730,29 @@ static int find_lowest_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.
+ *
+ * XXX: Consider the following example, 4 cores SMT2 system:
+ *
+ * LLC [0 - 7]
+ * SMT [0 1][2 3][4 5][6 7]
+ * o x o x x x x x
+ *
+ * where 'o': occupied and 'x': empty.
+ *
+ * A wakeup on cpu0 will exclude cpu1 and choose cpu3, since
+ * cpu1 is in a SD_PREFER_SIBLING sd and cpu3 is not. However,
+ * in this case, cpu4 would have been a better choice, since
+ * cpu3 is a (SMT) thread of an already loaded core.
+ *
+ * Doing it 'right' is difficult and expensive. The current
+ * solution is an acceptable approximation.
+ */
+ 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
^ permalink raw reply related [flat|nested] 11+ messages in thread
* [RESEND PATCH v11 0/2] Make find_later_rq() choose a closer cpu in topology
@ 2017-10-10 6:37 Byungchul Park
2017-10-10 6:37 ` [RESEND PATCH v11 2/2] sched/rt: Add support for SD_PREFER_SIBLING on find_lowest_rq() Byungchul Park
0 siblings, 1 reply; 11+ messages in thread
From: Byungchul Park @ 2017-10-10 6:37 UTC (permalink / raw)
To: peterz, mingo, rostedt; +Cc: linux-kernel, juri.lelli, kernel-team
Change from v10
-. modify a comment a bit as Steven suggested
Change from v9
-. modify a comment a bit so to be more clear as Juri suggested
Change from v8
-. add suggested-by Peterz
-. add several comments
Change from v7
-. fix a trivial typo
-. modify commit messages to explain what it does more clearly
-. simplify code with an existing macro
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 | 82 ++++++++++++++++++++++++++++++++++++++++++++-----
kernel/sched/rt.c | 80 +++++++++++++++++++++++++++++++++++++++++++++--
2 files changed, 152 insertions(+), 10 deletions(-)
--
1.9.1
^ permalink raw reply [flat|nested] 11+ messages in thread
* [RESEND PATCH v11 2/2] sched/rt: Add support for SD_PREFER_SIBLING on find_lowest_rq()
2017-10-10 6:37 [RESEND PATCH v11 0/2] Make find_later_rq() choose a closer cpu in topology Byungchul Park
@ 2017-10-10 6:37 ` Byungchul Park
0 siblings, 0 replies; 11+ messages in thread
From: Byungchul Park @ 2017-10-10 6:37 UTC (permalink / raw)
To: peterz, mingo, rostedt; +Cc: linux-kernel, juri.lelli, kernel-team
It would be better to try to check other siblings first if
SD_PREFER_SIBLING is flaged when pushing tasks - migration.
Suggested-by: Peter Zijlstra <peterz@infradead.org>
Signed-off-by: Byungchul Park <byungchul.park@lge.com>
Reviewed-by: Steven Rostedt (VMware) <rostedt@goodmis.org>
---
kernel/sched/rt.c | 80 ++++++++++++++++++++++++++++++++++++++++++++++++++++---
1 file changed, 77 insertions(+), 3 deletions(-)
diff --git a/kernel/sched/rt.c b/kernel/sched/rt.c
index 979b734..a32e36d 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;
+
+ for_each_cpu(cpu, mask) {
+ 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,37 @@ static int find_lowest_rq(struct task_struct *task)
return this_cpu;
}
- best_cpu = cpumask_first_and(lowest_mask,
- sched_domain_span(sd));
+ /*
+ * If a cpu exists that is in the lowest_mask and
+ * the current sd span, but not in the prefer sd
+ * span, then that becomes our choice.
+ *
+ * Of course, the lowest possible cpu is already
+ * under consideration through lowest_mask.
+ */
+ 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 +1730,29 @@ static int find_lowest_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.
+ *
+ * XXX: Consider the following example, 4 cores SMT2 system:
+ *
+ * LLC [0 - 7]
+ * SMT [0 1][2 3][4 5][6 7]
+ * o x o x x x x x
+ *
+ * where 'o': occupied and 'x': empty.
+ *
+ * A wakeup on cpu0 will exclude cpu1 and choose cpu3, since
+ * cpu1 is in a SD_PREFER_SIBLING sd and cpu3 is not. However,
+ * in this case, cpu4 would have been a better choice, since
+ * cpu3 is a (SMT) thread of an already loaded core.
+ *
+ * Doing it 'right' is difficult and expensive. The current
+ * solution is an acceptable approximation.
+ */
+ 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
^ permalink raw reply related [flat|nested] 11+ messages in thread
end of thread, other threads:[~2018-05-09 6:45 UTC | newest]
Thread overview: 11+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2018-01-08 6:14 [RESEND PATCH v11 0/2] Make find_later_rq() choose a closer cpu in topology Byungchul Park
2018-01-08 6:14 ` [RESEND PATCH v11 1/2] sched/deadline: Add support for SD_PREFER_SIBLING on find_later_rq() Byungchul Park
2018-01-10 17:22 ` kbuild test robot
2018-01-11 7:48 ` Byungchul Park
2018-01-08 6:14 ` [RESEND PATCH v11 2/2] sched/rt: Add support for SD_PREFER_SIBLING on find_lowest_rq() Byungchul Park
2018-01-10 17:45 ` kbuild test robot
-- strict thread matches above, loose matches on Subject: below --
2018-05-09 6:44 [RESEND PATCH v11 0/2] Make find_later_rq() choose a closer cpu in topology Byungchul Park
2018-05-09 6:44 ` [RESEND PATCH v11 2/2] sched/rt: Add support for SD_PREFER_SIBLING on find_lowest_rq() Byungchul Park
2017-12-28 23:32 [RESEND PATCH v11 0/2] Make find_later_rq() choose a closer cpu in topology Byungchul Park
2017-12-28 23:32 ` [RESEND PATCH v11 2/2] sched/rt: Add support for SD_PREFER_SIBLING on find_lowest_rq() Byungchul Park
2017-12-19 1:20 [RESEND PATCH v11 0/2] Make find_later_rq() choose a closer cpu in topology Byungchul Park
2017-12-19 1:20 ` [RESEND PATCH v11 2/2] sched/rt: Add support for SD_PREFER_SIBLING on find_lowest_rq() Byungchul Park
2017-11-02 1:25 [RESEND PATCH v11 0/2] Make find_later_rq() choose a closer cpu in topology Byungchul Park
2017-11-02 1:25 ` [RESEND PATCH v11 2/2] sched/rt: Add support for SD_PREFER_SIBLING on find_lowest_rq() Byungchul Park
2017-10-10 6:37 [RESEND PATCH v11 0/2] Make find_later_rq() choose a closer cpu in topology Byungchul Park
2017-10-10 6:37 ` [RESEND PATCH v11 2/2] sched/rt: Add support for SD_PREFER_SIBLING on find_lowest_rq() Byungchul Park
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.