sched/cpuset: distribute tasks within affinity masks
Subsystems (4)
PATCH v2 1/1 sched/cpuset: distribute tasks within affinity masks
From: Paul Turner <[email protected]>
Currently, when updating the affinity of tasks via either cpusets.cpus, or, sched_setaffinity(); tasks not currently running within the newly specified mask will be arbitrarily assigned to the first CPU within the mask.
This (particularly in the case that we are restricting masks) can result in many tasks being assigned to the first CPUs of their new masks.
This:
1) Can induce scheduling delays while the load-balancer has a chance to spread them between their new CPUs.
2) Can antogonize a poor load-balancer behavior where it has a difficult time recognizing that a cross-socket imbalance has been forced by an affinity mask.
This change adds a new cpumask interface to allow iterated calls to distribute within the intersection of the provided masks.
The cases that this mainly affects are:
- modifying cpuset.cpus
- when tasks join a cpuset
- when modifying a task's affinity via sched_setaffinity(2)
---
v2:
- Moved the "distribute" implementation to a new cpumask_any_and_distribute() function
- No longer move a task if it is already running on an allowed cpu
include/linux/cpumask.h | 7 +++++++ kernel/sched/core.c | 7 ++++++- lib/cpumask.c | 29 +++++++++++++++++++++++++++++ 3 files changed, 42 insertions(+), 1 deletion(-)
include/linux/cpumask.h +7 -0
@@ -194,6 +194,11 @@ static inline unsigned int cpumask_local_spread(unsigned int i, int node)return 0 ; } +static inline int cpumask_any_and_distribute (const struct cpumask *src1p, +const struct cpumask *src2p) { +return cpumask_next_and (-1 , src1p, src2p); +} +#define for_each_cpu (cpu, mask) \ for ((cpu) = 0; (cpu) < 1; (cpu)++, (void)mask)#define for_each_cpu_not (cpu, mask) \
@@ -245,6 +250,8 @@ static inline unsigned int cpumask_next_zero(int n, const struct cpumask *srcp)int cpumask_next_and (int n,const struct cpumask *,const struct cpumask *);int cpumask_any_but (const struct cpumask *mask,unsigned int cpu);unsigned int cpumask_local_spread (unsigned int i,int node); +int cpumask_any_and_distribute (const struct cpumask *src1p, +const struct cpumask *src2p);/** * for_each_cpu - iterate over every cpu in a mask
kernel/sched/core.c +6 -1
@@ -1652,7 +1652,12 @@ static int __set_cpus_allowed_ptr(struct task_struct *p,if (cpumask_equal (p->cpus_ptr, new_mask)) goto out; - dest_cpu =cpumask_any_and (cpu_valid_mask, new_mask); +/* +* Picking a ~random cpu helps in cases where we are changing affinity +* for groups of tasks (ie. cpuset), so that load balancing is not +* immediately required to distribute the tasks within their new mask. +*/ + dest_cpu =cpumask_any_and_distribute (cpu_valid_mask, new_mask);if (dest_cpu >= nr_cpu_ids) { ret = -EINVAL ; goto out;
lib/cpumask.c +29 -0
@@ -232,3 +232,32 @@ unsigned int cpumask_local_spread(unsigned int i, int node)BUG (); }EXPORT_SYMBOL (cpumask_local_spread); + +static DEFINE_PER_CPU(int, distribute_cpu_mask_prev); + +/** +* Returns an arbitrary cpu within srcp1 & srcp2. +* +* Iterated calls using the same srcp1 and srcp2 will be distributed within +* their intersection. +* +* Returns >= nr_cpu_ids if the intersection is empty. +*/ +int cpumask_any_and_distribute (const struct cpumask *src1p, +const struct cpumask *src2p) +{ +int next, prev; + +/* NOTE: our first selection will skip 0. */ + prev =__this_cpu_read (distribute_cpu_mask_prev); + + next =cpumask_next_and (prev, src1p, src2p); +if (next >= nr_cpu_ids) + next =cpumask_first_and (src1p, src2p); + +if (next < nr_cpu_ids) +__this_cpu_write (distribute_cpu_mask_prev, next); + +return next; +} +EXPORT_SYMBOL (cpumask_any_and_distribute);
Signature · 1 line
2.25.1.481.gfbce0eb801-goog
Quoted 21 lines · Josh Don
From: Paul Turner <[email protected]>
Currently, when updating the affinity of tasks via either cpusets.cpus, or,
sched_setaffinity(); tasks not currently running within the newly specified mask will be arbitrarily assigned to the first CPU within the mask.This (particularly in the case that we are restricting masks) can result in many tasks being assigned to the first CPUs of their new masks.
This:
1) Can induce scheduling delays while the load-balancer has a chance to spread them between their new CPUs.
2) Can antogonize a poor load-balancer behavior where it has a difficult time recognizing that a cross-socket imbalance has been forced by an affinity mask.This change adds a new cpumask interface to allow iterated calls to distribute within the intersection of the provided masks.
Quoted 8 lines
The cases that this mainly affects are:
- modifying cpuset.cpus
- when tasks join a cpuset
- when modifying a task's affinity viasched_setaffinity(2)Co-developed-by Josh Don <[email protected]>Signed-off-by Josh Don <[email protected]>Signed-off-by Paul Turner <[email protected]>
This actually helps me fix a similar problem I faced in RT [1]. If multiple RT tasks wakeup at the same time we get a 'thundering herd' issue where they all end up going to the same CPU, just to be pushed out again.
Beside this will help fix another problem for RT tasks fitness, which is a manifestation of the problem above. If two tasks wake up at the same time and they happen to run on a little cpu (but request to run on a big one), one of them will end up being migrated because find_lowest_rq() will return the first cpu in the mask for both tasks.
I tested the API (not the change in sched/core.c) and it looks good to me.
Quoted 16 lines
---
v2:
- Moved the "distribute" implementation to a newcpumask_any_and_distribute()function
- No longer move a task if it is already running on an allowed cpuinclude/linux/cpumask.h | 7 +++++++ kernel/sched/core.c | 7 ++++++- lib/cpumask.c | 29 +++++++++++++++++++++++++++++ 3 files changed, 42 insertions(+), 1 deletion(-)include/linux/cpumask.h +0
-0
include/linux/cpumask.h static inline unsigned int cpumask_local_spread(unsigned int i, int node) · line 200
Quoted 7 lines
include/linux/cpumask.h +4
-0@@ -194,6 +194,11 @@ static inline unsigned int cpumask_local_spread(unsigned int i, int node)return 0 ; } +static inline int cpumask_any_and_distribute (const struct cpumask *src1p, +const struct cpumask *src2p) { +return cpumask_next_and (-1 , src1p, src2p); +}
nit: cpumask_first_and() is better here?
It might be a good idea to split the API from the user too.
Anyway, for the API.
Thanks
--
Qais Yousef
[1] https://lore.kernel.org/lkml/20200219140243.wfljmupcrwm2jelo@e107158-lin/
Quoted 71 lines
include/linux/cpumask.h +3
-0+#define for_each_cpu (cpu, mask) \ for ((cpu) = 0; (cpu) < 1; (cpu)++, (void)mask)#define for_each_cpu_not (cpu, mask) \@@ -245,6 +250,8 @@ static inline unsigned int cpumask_next_zero(int n, const struct cpumask *srcp)int cpumask_next_and (int n,const struct cpumask *,const struct cpumask *);int cpumask_any_but (const struct cpumask *mask,unsigned int cpu);unsigned int cpumask_local_spread (unsigned int i,int node); +int cpumask_any_and_distribute (const struct cpumask *src1p, +const struct cpumask *src2p);/** * for_each_cpu - iterate over every cpu in a mask kernel/sched/core.c +6
-1@@ -1652,7 +1652,12 @@ static int __set_cpus_allowed_ptr(struct task_struct *p,if (cpumask_equal (p->cpus_ptr, new_mask)) goto out; - dest_cpu =cpumask_any_and (cpu_valid_mask, new_mask); +/* +* Picking a ~random cpu helps in cases where we are changing affinity +* for groups of tasks (ie. cpuset), so that load balancing is not +* immediately required to distribute the tasks within their new mask. +*/ + dest_cpu =cpumask_any_and_distribute (cpu_valid_mask, new_mask);if (dest_cpu >= nr_cpu_ids) { ret = -EINVAL ; goto out;lib/cpumask.c +29
-0@@ -232,3 +232,32 @@ unsigned int cpumask_local_spread(unsigned int i, int node)BUG (); }EXPORT_SYMBOL (cpumask_local_spread); + +static DEFINE_PER_CPU(int, distribute_cpu_mask_prev); + +/** +* Returns an arbitrary cpu within srcp1 & srcp2. +* +* Iterated calls using the same srcp1 and srcp2 will be distributed within +* their intersection. +* +* Returns >= nr_cpu_ids if the intersection is empty. +*/ +int cpumask_any_and_distribute (const struct cpumask *src1p, +const struct cpumask *src2p) +{ +int next, prev; + +/* NOTE: our first selection will skip 0. */ + prev =__this_cpu_read (distribute_cpu_mask_prev); + + next =cpumask_next_and (prev, src1p, src2p); +if (next >= nr_cpu_ids) + next =cpumask_first_and (src1p, src2p); + +if (next < nr_cpu_ids) +__this_cpu_write (distribute_cpu_mask_prev, next); + +return next; +} +EXPORT_SYMBOL (cpumask_any_and_distribute);Signature · 1 line
2.25.1.481.gfbce0eb801-goog
Peter Zijlstra
maintainerQuoted 27 lines · Qais Yousef
Quoted 26 lines · Josh Don
From: Paul Turner <[email protected]>
Currently, when updating the affinity of tasks via either cpusets.cpus, or,
sched_setaffinity(); tasks not currently running within the newly specified mask will be arbitrarily assigned to the first CPU within the mask.This (particularly in the case that we are restricting masks) can result in many tasks being assigned to the first CPUs of their new masks.
This:
1) Can induce scheduling delays while the load-balancer has a chance to spread them between their new CPUs.
2) Can antogonize a poor load-balancer behavior where it has a difficult time recognizing that a cross-socket imbalance has been forced by an affinity mask.This change adds a new cpumask interface to allow iterated calls to distribute within the intersection of the provided masks.
The cases that this mainly affects are:
- modifying cpuset.cpus
- when tasks join a cpuset
- when modifying a task's affinity viasched_setaffinity(2)
Quoted 8 lines
Quoted 3 lines
Co-developed-by Josh Don <[email protected]>Signed-off-by Josh Don <[email protected]>Signed-off-by Paul Turner <[email protected]>Anyway, for the API.
Reviewed-by Qais Yousef <[email protected]>Tested-by Qais Yousef <[email protected]>
Thanks guys!
Quoted 5 lines · Qais Yousef
This actually helps me fix a similar problem I faced in RT [1]. If multiple RT tasks wakeup at the same time we get a 'thundering herd' issue where they all end up going to the same CPU, just to be pushed out again.
Quoted 7 lines
Beside this will help fix another problem for RT tasks fitness, which is a manifestation of the problem above. If two tasks wake up at the same time and they happen to run on a little cpu (but request to run on a big one), one of them will end up being migrated because
find_lowest_rq()will return the first cpu in the mask for both tasks.I tested the API (not the change in
sched/core.c) and it looks good to me.
Nice, glad that the API already has another use case. Thanks for taking a look.
Quoted 1 line
nit:
cpumask_first_and()is better here?
Yea, I would also prefer to use it, but the definition of cpumask_first_and() follows this section, as it itself uses cpumask_next_and().
Quoted 1 line
It might be a good idea to split the API from the user too.
Not sure what you mean by this, could you clarify?
Quoted 7 lines · Peter Zijlstra
Quoted 5 lines
Anyway, for the API.
Reviewed-by Qais Yousef <[email protected]>Tested-by Qais Yousef <[email protected]>Thanks guys!
Thanks Peter, any other comments or are you happy with merging this patch as-is?
Quoted 18 lines · Josh Don
Quoted 5 lines · Qais Yousef
This actually helps me fix a similar problem I faced in RT [1]. If multiple RT tasks wakeup at the same time we get a 'thundering herd' issue where they all end up going to the same CPU, just to be pushed out again.
Quoted 7 lines
Beside this will help fix another problem for RT tasks fitness, which is a manifestation of the problem above. If two tasks wake up at the same time and they happen to run on a little cpu (but request to run on a big one), one of them will end up being migrated because
find_lowest_rq()will return the first cpu in the mask for both tasks.I tested the API (not the change in
sched/core.c) and it looks good to me.Nice, glad that the API already has another use case. Thanks for taking a look.
Quoted 1 line
nit:
cpumask_first_and()is better here?
Quoted 7 lines
Yea, I would also prefer to use it, but the definition of
cpumask_first_and()follows this section, as it itself usescpumask_next_and().Quoted 1 line
It might be a good idea to split the API from the user too.
Not sure what you mean by this, could you clarify?
I meant it'd be a good idea to split the cpumask API into its own patch and have a separate patch for the user in sched/core.c. But that was a small nit. If the user (in sched/core.c) somehow introduces a regression, reverting it separately should be trivial.
Thanks
--
Qais Yousef
Quoted 11 lines · Peter Zijlstra
Quoted 7 lines
Quoted 5 lines
Anyway, for the API.
Reviewed-by Qais Yousef <[email protected]>Tested-by Qais Yousef <[email protected]>Thanks guys!
Thanks Peter, any other comments or are you happy with merging this patch as-is?
Quoted 6 lines · Qais Yousef
Quoted 4 lines · Josh Don
Quoted 2 lines · Qais Yousef
It might be a good idea to split the API from the user too.
Quoted 8 lines
Quoted 1 line
Not sure what you mean by this, could you clarify?
I meant it'd be a good idea to split the cpumask API into its own patch and have a separate patch for the user in
sched/core.c. But that was a small nit. If the user (insched/core.c) somehow introduces a regression, reverting it separately should be trivial.Thanks
Ah, yes I agree that sounds like a good idea, I can do that.
Peter, any other nit before I re-send?
Quoted 14 lines · Josh Don
Quoted 13 lines · Qais Yousef
Quoted 5 lines · Josh Don
Quoted 2 lines · Qais Yousef
It might be a good idea to split the API from the user too.
Not sure what you mean by this, could you clarify?
I meant it'd be a good idea to split the cpumask API into its own patch and have a separate patch for the user in
sched/core.c. But that was a small nit. If the user (insched/core.c) somehow introduces a regression, reverting it separately should be trivial.
Quoted 5 lines
Quoted 1 line
Thanks
Ah, yes I agree that sounds like a good idea, I can do that.
Peter, any other nit before I re-send?
AFAICT it was already picked up, so no need to resend to fix the nits from my side.
[tip: sched/core] sched/core: Distribute tasks within affinity masks
In reply to Josh DonThe following commit has been merged into the sched/core branch of tip:
The following commit has been merged into the sched/core branch of tip:
Commit-ID: 46a87b3851f0d6eb05e6d83d5c5a30df0eca8f76 Gitweb: https://git.kernel.org/tip/46a87b3851f0d6eb05e6d83d5c5a30df0eca8f76 Author: Paul Turner <[email protected]> AuthorDate: Tue, 10 Mar 2020 18:01:13 -07:00 Committer: Peter Zijlstra <[email protected]> CommitterDate: Fri, 20 Mar 2020 13:06:18 +01:00
sched/core: Distribute tasks within affinity masks
Currently, when updating the affinity of tasks via either cpusets.cpus, or, sched_setaffinity(); tasks not currently running within the newly specified mask will be arbitrarily assigned to the first CPU within the mask.
This (particularly in the case that we are restricting masks) can result in many tasks being assigned to the first CPUs of their new masks.
This:
1) Can induce scheduling delays while the load-balancer has a chance to spread them between their new CPUs.
2) Can antogonize a poor load-balancer behavior where it has a difficult time recognizing that a cross-socket imbalance has been forced by an affinity mask.
This change adds a new cpumask interface to allow iterated calls to distribute within the intersection of the provided masks.
The cases that this mainly affects are:
- modifying cpuset.cpus
- when tasks join a cpuset
- when modifying a task's affinity via sched_setaffinity(2)
--- include/linux/cpumask.h | 7 +++++++ kernel/sched/core.c | 7 ++++++- lib/cpumask.c | 29 +++++++++++++++++++++++++++++ 3 files changed, 42 insertions(+), 1 deletion(-)
include/linux/cpumask.h +7 -0
@@ -194,6 +194,11 @@ static inline unsigned int cpumask_local_spread(unsigned int i, int node)return 0 ; } +static inline int cpumask_any_and_distribute (const struct cpumask *src1p, +const struct cpumask *src2p) { +return cpumask_next_and (-1 , src1p, src2p); +} +#define for_each_cpu (cpu, mask) \ for ((cpu) = 0; (cpu) < 1; (cpu)++, (void)mask)#define for_each_cpu_not (cpu, mask) \
@@ -245,6 +250,8 @@ static inline unsigned int cpumask_next_zero(int n, const struct cpumask *srcp)int cpumask_next_and (int n,const struct cpumask *,const struct cpumask *);int cpumask_any_but (const struct cpumask *mask,unsigned int cpu);unsigned int cpumask_local_spread (unsigned int i,int node); +int cpumask_any_and_distribute (const struct cpumask *src1p, +const struct cpumask *src2p);/** * for_each_cpu - iterate over every cpu in a mask
kernel/sched/core.c +6 -1
@@ -1650,7 +1650,12 @@ static int __set_cpus_allowed_ptr(struct task_struct *p,if (cpumask_equal (p->cpus_ptr, new_mask)) goto out; - dest_cpu =cpumask_any_and (cpu_valid_mask, new_mask); +/* +* Picking a ~random cpu helps in cases where we are changing affinity +* for groups of tasks (ie. cpuset), so that load balancing is not +* immediately required to distribute the tasks within their new mask. +*/ + dest_cpu =cpumask_any_and_distribute (cpu_valid_mask, new_mask);if (dest_cpu >= nr_cpu_ids) { ret = -EINVAL ; goto out;
lib/cpumask.c +29 -0
@@ -232,3 +232,32 @@ unsigned int cpumask_local_spread(unsigned int i, int node)BUG (); }EXPORT_SYMBOL (cpumask_local_spread); + +static DEFINE_PER_CPU(int, distribute_cpu_mask_prev); + +/** +* Returns an arbitrary cpu within srcp1 & srcp2. +* +* Iterated calls using the same srcp1 and srcp2 will be distributed within +* their intersection. +* +* Returns >= nr_cpu_ids if the intersection is empty. +*/ +int cpumask_any_and_distribute (const struct cpumask *src1p, +const struct cpumask *src2p) +{ +int next, prev; + +/* NOTE: our first selection will skip 0. */ + prev =__this_cpu_read (distribute_cpu_mask_prev); + + next =cpumask_next_and (prev, src1p, src2p); +if (next >= nr_cpu_ids) + next =cpumask_first_and (src1p, src2p); + +if (next < nr_cpu_ids) +__this_cpu_write (distribute_cpu_mask_prev, next); + +return next; +} +EXPORT_SYMBOL (cpumask_any_and_distribute);