Skip to contentSkip to conversation

sched/cpuset: distribute tasks within affinity masks

PATCH Applied Josh Don 4 participants 8 messages Mar 11, 2020 – Mar 20, 2020

Subsystems (4)
lore
Share & tools
lore

Josh Don

author
#0 lore raw

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
index d5cc88514aee..f0d895d6ac39 100644
@@ -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
index 1a9983da4408..fc6f2bec7d44 100644
@@ -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
index 0cb672eb107c..fb22fb266f93 100644
@@ -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
Reviewed-by Tested-by on v2 1/1
#1 lore raw
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 via sched_setaffinity(2)

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 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 +0 -0
index d5cc88514aee..f0d895d6ac39 100644

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
index 1a9983da4408..fc6f2bec7d44 100644
@@ -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
index 0cb672eb107c..fb22fb266f93 100644
@@ -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
maintainer
#2 lore raw
Quoted 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 via sched_setaffinity(2)

Quoted 8 lines
Quoted 3 lines

Anyway, for the API.

Thanks guys!

author
#3 lore raw
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.

Thanks guys!

Thanks Peter, any other comments or are you happy with merging this patch as-is?

#4 lore raw
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 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?

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.

Thanks guys!

Thanks Peter, any other comments or are you happy with merging this patch as-is?

author
#5 lore raw
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 (in sched/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?

#6 lore raw
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 (in sched/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.

merge bot Applied
#7 lore raw

[tip: sched/core] sched/core: Distribute tasks within affinity masks

In reply to Josh Don
The 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
index d5cc885..f0d895d 100644
@@ -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
index 978bf6f..014d4f7 100644
@@ -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
index 0cb672e..fb22fb2 100644
@@ -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);