sched: Restructure task_mm_cid_work for predictability

From: Mathieu Desnoyers <[email protected]>

When a process reduces its number of threads or clears bits in its CPU affinity mask, the mm_cid allocation should eventually converge towards smaller values.

However, the change introduced by:

commit 7e019dcc470f ("sched: Improve cache locality of RSEQ concurrency IDs for intermittent workloads")

adds a per-mm/CPU recent_cid which is never unset unless a thread migrates.

This is a tradeoff between:

A) Preserving cache locality after a transition from many threads to few threads, or after reducing the hamming weight of the allowed CPU mask.

B) Making the mm_cid upper bounds wrt nr threads and allowed CPU mask easy to document and understand.

C) Allowing applications to eventually react to mm_cid compaction after reduction of the nr threads or allowed CPU mask, making the tracking of mm_cid compaction easier by shrinking it back towards 0 or not.

D) Making sure applications that periodically reduce and then increase again the nr threads or allowed CPU mask still benefit from good cache locality with mm_cid.

Introduce the following changes:

* After shrinking the number of threads or reducing the number of allowed CPUs, reduce the value of max_nr_cid so expansion of CID allocation will preserve cache locality if the number of threads or allowed CPUs increase again.

* Only re-use a recent_cid if it is within the max_nr_cid upper bound, else find the first available CID.

Fixes 7e019dcc470f ("sched: Improve cache locality of RSEQ concurrency IDs for intermittent workloads")

Cc Peter Zijlstra (Intel) <[email protected]>

Cc Marco Elver <[email protected]>

Cc Ingo Molnar <[email protected]>

Tested-by Gabriele Monaco <[email protected]>

Signed-off-by Mathieu Desnoyers <[email protected]>

Signed-off-by Gabriele Monaco <[email protected]>

---
  include/linux/mm_types.h |  7 ++++---
  kernel/sched/sched.h     | 25 ++++++++++++++++++++++---
  2 files changed, 26 insertions(+), 6 deletions(-)

include/linux/mm_types.h +4 -3

index 6b27db7f94963..0234f14f2aa6b 100644
@@ -875,10 +875,11 @@ struct mm_struct {
  		 */
  		unsigned int nr_cpus_allowed;
  		/**
-		 * @max_nr_cid: Maximum number of concurrency IDs allocated.
+		 * @max_nr_cid: Maximum number of allowed concurrency
+		 *              IDs allocated.
  		 *
-		 * Track the highest number of concurrency IDs allocated for the
-		 * mm.
+		 * Track the highest number of allowed concurrency IDs
+		 * allocated for the mm.
  		 */
  		atomic_t max_nr_cid;
  		/**

kernel/sched/sched.h +22 -3

index 38e0e323dda26..606c96b74ebfa 100644
@@ -3698,10 +3698,28 @@ static inline int __mm_cid_try_get(struct task_struct *t, struct mm_struct *mm)
  {
  	struct cpumask *cidmask = mm_cidmask(mm);
  	struct mm_cid __percpu *pcpu_cid = mm->pcpu_cid;
-	int cid = __this_cpu_read(pcpu_cid->recent_cid);
+	int cid, max_nr_cid, allowed_max_nr_cid;
 
+	/*
+	 * After shrinking the number of threads or reducing the number
+	 * of allowed cpus, reduce the value of max_nr_cid so expansion
+	 * of cid allocation will preserve cache locality if the number
+	 * of threads or allowed cpus increase again.
+	 */
+	max_nr_cid = atomic_read(&mm->max_nr_cid);
+	while ((allowed_max_nr_cid = min_t(int, READ_ONCE(mm->nr_cpus_allowed),
+					   atomic_read(&mm->mm_users))),
+	       max_nr_cid > allowed_max_nr_cid) {
+		/* atomic_try_cmpxchg loads previous mm->max_nr_cid into max_nr_cid. */
+		if (atomic_try_cmpxchg(&mm->max_nr_cid, &max_nr_cid, allowed_max_nr_cid)) {
+			max_nr_cid = allowed_max_nr_cid;
+			break;
+		}
+	}
  	/* Try to re-use recent cid. This improves cache locality. */
-	if (!mm_cid_is_unset(cid) && !cpumask_test_and_set_cpu(cid, cidmask))
+	cid = __this_cpu_read(pcpu_cid->recent_cid);
+	if (!mm_cid_is_unset(cid) && cid < max_nr_cid &&
+	    !cpumask_test_and_set_cpu(cid, cidmask))
  		return cid;
  	/*
  	 * Expand cid allocation if the maximum number of concurrency

@@ -3709,8 +3727,9 @@ static inline int __mm_cid_try_get(struct task_struct *t, struct mm_struct *mm)
  	 * and number of threads. Expanding cid allocation as much as
  	 * possible improves cache locality.
  	 */
-	cid = atomic_read(&mm->max_nr_cid);
+	cid = max_nr_cid;
  	while (cid < READ_ONCE(mm->nr_cpus_allowed) && cid < atomic_read(&mm->mm_users)) {
+		/* atomic_try_cmpxchg loads previous mm->max_nr_cid into cid. */
  		if (!atomic_try_cmpxchg(&mm->max_nr_cid, &cid, cid + 1))
  			continue;
  		if (!cpumask_test_and_set_cpu(cid, cidmask))

Quoted 2 lines · Gabriele Monaco

From: Mathieu Desnoyers <[email protected]>

Peter, Ingo, this patch has been ready for inclusion for a while. The rest of this series does not seem to be quite ready yet, but can we at least merge this patch into tip ?

kernel test robot noticed "WARNING:at_kernel/workqueue.c:#__queue_delayed_work" on:

[    2.640924][    T0] ------------[ cut here ]------------

[ 2.641646][ T0] WARNING: CPU: 0 PID: 0 at kernel/workqueue.c:2495

__queue_delayed_work (kernel/workqueue.c:2495 (discriminator 9)) [    2.642874][    T0] Modules linked in:
[    2.643381][    T0] CPU: 0 UID: 0 PID: 0 Comm: swapper Not tainted 6.14.0-rc2-00002-g287adf9e9c1f #1
[    2.644582][    T0] Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS 1.16.2-debian-1.16.2-1 04/01/2014

[ 2.645943][ T0] RIP: 0010:__queue_delayed_work

(kernel/workqueue.c:2495 (discriminator 9))

Quoted 5 lines · kernel test robot

kernel test robot noticed "WARNING:at_kernel/workqueue.c:#__queue_delayed_work" on:

[    2.640924][    T0] ------------[ cut here ]------------

[ 2.641646][ T0] WARNING: CPU: 0 PID: 0 at kernel/workqueue.c:2495

Quoted 8 lines

__queue_delayed_work (kernel/workqueue.c:2495 (discriminator 9)) [    2.642874][    T0] Modules linked in:
[    2.643381][    T0] CPU: 0 UID: 0 PID: 0 Comm: swapper Not tainted 6.14.0-rc2-00002-g287adf9e9c1f #1
[    2.644582][    T0] Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS 1.16.2-debian-1.16.2-1 04/01/2014

[ 2.645943][ T0] RIP: 0010:__queue_delayed_work

(kernel/workqueue.c:2495 (discriminator 9))

There seem to be major problems with this configuration, I'm trying to understand what's wrong but, for the time being, this patchset is not ready for inclusion.

Quoted 17 lines · Gabriele Monaco

Quoted 13 lines · kernel test robot

kernel test robot noticed "WARNING:at_kernel/workqueue.c:#__queue_delayed_work" on:

[    2.640924][    T0] ------------[ cut here ]------------

[ 2.641646][ T0] WARNING: CPU: 0 PID: 0 at

kernel/workqueue.c:2495
__queue_delayed_work (kernel/workqueue.c:2495 (discriminator 9)) [    2.642874][    T0] Modules linked in:
[    2.643381][    T0] CPU: 0 UID: 0 PID: 0 Comm: swapper Not tainted
6.14.0-rc2-00002-g287adf9e9c1f #1
[    2.644582][    T0] Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS 1.16.2-debian-1.16.2-1 04/01/2014

Quoted 2 lines

[ 2.645943][ T0] RIP: 0010:__queue_delayed_work

(kernel/workqueue.c:2495 (discriminator 9))

Quoted 5 lines

There seem to be major problems with this configuration, I'm trying to
understand what's wrong but, for the time being, this patchset is not
ready for inclusion.

I think there is an issue with the order of init functions at boot.

poking_init() calls mm_alloc(), which ends up calling mm_init().

The WARN_ON() is about a NULL wq pointer, which I suspect happens if poking_init() is called before workqueue_init_early(), which allocates system_wq.

Indeed, in start_kernel(), poking_init() is called before workqueue_init_early().

I'm not sure what are the init order dependencies across subsystems here.
There is the following order in start_kernel():

[...]
         mm_core_init();
         poking_init();
         ftrace_init();

         /* trace_printk can be enabled here */
         early_trace_init();

         /*
          * Set up the scheduler prior starting any interrupts (such as the
          * timer interrupt). Full topology setup happens at smp_init()
          * time - but meanwhile we still have a functioning scheduler.
          */
         sched_init();

         if (WARN(!irqs_disabled(),
                  "Interrupts were enabled *very* early, fixing it\n"))
                 local_irq_disable(); radix_tree_init();
         maple_tree_init();

         /*
          * Set up housekeeping before setting up workqueues to allow the unbound
          * workqueue to take non-housekeeping into account. */
         housekeeping_init();

         /*
          * Allow workqueue creation and work item queueing/cancelling
          * early.  Work item execution depends on kthreads and starts after
          * workqueue_init().
          */
         workqueue_init_early();
[...]

So either we find a way to reorder this, or we make sure poking_init()
does not require the workqueue.

Thanks,

Mathieu

Quoted 5 lines · kernel test robot

kernel test robot noticed "WARNING:at_kernel/workqueue.c:#__queue_delayed_work" on:

[    2.640924][    T0] ------------[ cut here ]------------

[ 2.641646][ T0] WARNING: CPU: 0 PID: 0 at kernel/workqueue.c:2495

Quoted 8 lines

__queue_delayed_work (kernel/workqueue.c:2495 (discriminator 9)) [    2.642874][    T0] Modules linked in:
[    2.643381][    T0] CPU: 0 UID: 0 PID: 0 Comm: swapper Not tainted 6.14.0-rc2-00002-g287adf9e9c1f #1
[    2.644582][    T0] Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS 1.16.2-debian-1.16.2-1 04/01/2014

[ 2.645943][ T0] RIP: 0010:__queue_delayed_work

(kernel/workqueue.c:2495 (discriminator 9))

There seem to be major problems with this configuration, I'm trying to understand what's wrong but, for the time being, this patchset is not ready for inclusion.

Gabriele

Quoted 17 lines · Gabriele Monaco

Quoted 13 lines · kernel test robot

kernel test robot noticed "WARNING:at_kernel/workqueue.c:#__queue_delayed_work" on:

[    2.640924][    T0] ------------[ cut here ]------------

[ 2.641646][ T0] WARNING: CPU: 0 PID: 0 at

kernel/workqueue.c:2495
__queue_delayed_work (kernel/workqueue.c:2495 (discriminator 9)) [    2.642874][    T0] Modules linked in:
[    2.643381][    T0] CPU: 0 UID: 0 PID: 0 Comm: swapper Not tainted
6.14.0-rc2-00002-g287adf9e9c1f #1
[    2.644582][    T0] Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS 1.16.2-debian-1.16.2-1 04/01/2014

Quoted 2 lines

[ 2.645943][ T0] RIP: 0010:__queue_delayed_work

(kernel/workqueue.c:2495 (discriminator 9))

Quoted 5 lines

There seem to be major problems with this configuration, I'm trying to
understand what's wrong but, for the time being, this patchset is not
ready for inclusion.

Patch 1/3 has been ready for a while though. Can we post it separately
for inclusion ?

Quoted 5 lines · kernel test robot

kernel test robot noticed "WARNING:at_kernel/workqueue.c:#__queue_delayed_work" on:

[    2.640924][    T0] ------------[ cut here ]------------

[ 2.641646][ T0] WARNING: CPU: 0 PID: 0 at kernel/workqueue.c:2495

Quoted 8 lines

__queue_delayed_work (kernel/workqueue.c:2495 (discriminator 9)) [    2.642874][    T0] Modules linked in:
[    2.643381][    T0] CPU: 0 UID: 0 PID: 0 Comm: swapper Not tainted 6.14.0-rc2-00002-g287adf9e9c1f #1
[    2.644582][    T0] Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS 1.16.2-debian-1.16.2-1 04/01/2014

[ 2.645943][ T0] RIP: 0010:__queue_delayed_work

(kernel/workqueue.c:2495 (discriminator 9))

There seem to be major problems with this configuration, I'm trying to understand what's wrong but, for the time being, this patchset is not ready for inclusion.

Quoted 17 lines · Gabriele Monaco

Quoted 13 lines · kernel test robot

kernel test robot noticed "WARNING:at_kernel/workqueue.c:#__queue_delayed_work" on:

[    2.640924][    T0] ------------[ cut here ]------------

[ 2.641646][ T0] WARNING: CPU: 0 PID: 0 at

kernel/workqueue.c:2495
__queue_delayed_work (kernel/workqueue.c:2495 (discriminator 9)) [    2.642874][    T0] Modules linked in:
[    2.643381][    T0] CPU: 0 UID: 0 PID: 0 Comm: swapper Not tainted
6.14.0-rc2-00002-g287adf9e9c1f #1
[    2.644582][    T0] Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS 1.16.2-debian-1.16.2-1 04/01/2014

Quoted 2 lines

[ 2.645943][ T0] RIP: 0010:__queue_delayed_work

(kernel/workqueue.c:2495 (discriminator 9))

Quoted 5 lines

There seem to be major problems with this configuration, I'm trying to
understand what's wrong but, for the time being, this patchset is not
ready for inclusion.

I'm staring at this now, and I'm thinking we could do a simpler change
that would solve your RT issues without having to introduce a dependency
on workqueue.c.

So if the culprit is that task_mm_cid_work() runs for too long on large
many-cpus systems, why not break it up into smaller iterations ?

So rather than iterating on "for_each_possible_cpu", we could simply break this down into iteration on at most N cpus, so:

tick #1: iteration on CPUs 0 ..   N - 1
tick #2: iteration on CPUs N .. 2*N - 1
...
circling back to 0 when it reaches the number of possible cpus.

This N value could be configurable, e.g. CONFIG_RSEQ_CID_SCAN_BATCH, with a sane default. An RT system could decide to make that value lower.

Then all we need to do is remember which was that last observed cpu number in the mm struct, so the next tick picks up from there.

The main downside of this approach compared to scheduling delayed work in a workqueue is that it depends on having the mm be current when
the scheduler tick happens. But perhaps this is something we could fix
in a different way that does not add a dependency on workqueue. I'm not
sure how though.

Thoughts ?

This patchset moves the task_mm_cid_work to a preemptible and migratable context. This reduces the impact of this task to the scheduling latency of real time tasks.
The change makes the recurrence of the task a bit more predictable. We also add optimisation and fixes to make sure the task_mm_cid_work works as intended.

The behaviour causing latency was introduced in commit 223baf9d17f2 ("sched: Fix performance regression introduced by mm_cid") which introduced a task work tied to the scheduler tick.
That approach presents two possible issues:
* the task work runs before returning to user and causes, in fact, a scheduling latency (with order of magnitude significant in PREEMPT_RT)
* periodic tasks with short runtime are less likely to run during the tick, hence they might not run the task work at all

Patch 1 allows the mm_cids to be actually compacted when a process reduces its number of threads, which was not the case since the same mm_cids were reused to improve cache locality, more details in [4].

Patch 2 contains the main changes, removing the task_work on the scheduler tick and using a delayed_work instead. Additionally, we terminate the call immediately if we see that no mm_cid is actually active, which could happen on processes sleeping for long time or which exited but whose mm has not been freed yet.

Patch 3 adds a selftest to validate the functionality of the task_mm_cid_work (i.e. to compact the mm_cids). The test fails if patch 1 is not applied and is flaky without patch 2. We expect it to always pass with the entire patchset applied.

Changes since V5:
* Punctuation

Changes since V4 [1]:
* Fixes on the selftest
* Polished memory allocation and cleanup
* Handle the test failure in main

Changes since V3 [2]:
* Fixes on the selftest
* Minor style issues in comments and indentation
* Use of perror where possible
* Add a barrier to align threads execution
* Improve test failure and error handling

Changes since V2 [3]:
* Change the order of the patches
* Merge patches changing the main delayed_work logic
* Improved self-test to spawn 1 less thread and use the main one instead

Changes since V1 [4]:
* Re-arm the delayed_work at each invocation
* Cancel the work synchronously at mmdrop
* Remove next scan fields and completely rely on the delayed_work
* Shrink mm_cid allocation with nr thread/affinity (Mathieu Desnoyers)
* Add self test

Overhead comparison in [4]

[1] - https://lore.kernel.org/lkml/[email protected]
[2] - https://lore.kernel.org/lkml/[email protected]
[3] - https://lore.kernel.org/lkml/[email protected]
[4] - https://lore.kernel.org/lkml/[email protected]

To: Mathieu Desnoyers <[email protected]>
To: Peter Zijlstra <[email protected]>
To: Ingo Molnar <[email protected]>
To: Paul E. McKenney <[email protected]>
To: Shuah Khan <[email protected]>

Gabriele Monaco (2):
sched: Move task_mm_cid_work to mm delayed work rseq/selftests: Add test for mm_cid compaction

Mathieu Desnoyers (1):
sched: Compact RSEQ concurrency IDs with reduced threads and affinity

  include/linux/mm_types.h                      |  23 +-
  include/linux/sched.h                         |   1 -
  kernel/sched/core.c                           |  66 +-----
  kernel/sched/sched.h                          |  32 ++-
  tools/testing/selftests/rseq/.gitignore       |   1 +
  tools/testing/selftests/rseq/Makefile         |   2 +-
  .../selftests/rseq/mm_cid_compaction_test.c   | 200 ++++++++++++++++++
  7 files changed, 246 insertions(+), 79 deletions(-)

create mode 100644 tools/testing/selftests/rseq/mm_cid_compaction_test.c

base-commit: a64dcfb451e254085a7daee5fe51bf22959d52d3