[PATCH 0/2] sched: Run task_mm_cid_work in batches to lower latency

[PATCH 0/2] sched: Run task_mm_cid_work in batches to lower latency

[Gabriele Monaco]

This patchset is a continuation of [1] but using a simpler approach.
The task_mm_cid_work runs as a task_work returning to userspace and
causes a non-negligible scheduling latency, mostly due to its iterations
over all cores.

Split the work into several batches, each call to task_mm_cid_work will
not run for all cpus but just for a configurable number of cpus. Next
runs will pick up where the previous left off.
The mechanism that avoids running too frequently (100ms) is enforced
only when we finish all cpus, that is when we start from 0.

Patch 1 implements the logic behind the change

Patch 2 implements a test to validate mm_cids are compacted, since this
patchset doesn't address the fact processes running in bursts are less
likely to run the task_work, we add a busy loop in the test to make sure
the mm_cid runs during the test duration (not necessary in [1]). The
test would of course fail if the mm_cid compaction mechanism is broken.

This patchset is based on 1/3 of [1] ("sched: Compact RSEQ concurrency
IDs with reduced threads and affinity"), which will be merged separately,
lacking that commit might have the test in patch 2 fail.

[1] - https://lore.kernel.org/lkml/20250210153253.460471-1-gmonaco@redhat.com/

To: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
To: Peter Zijlstra <peterz@infradead.org>
To: Ingo Molnar <mingo@kernel.org>
To: Paul E. McKenney <paulmck@kernel.org>
Cc: Shuah Khan <shuah@kernel.org>

Gabriele Monaco (2):
  sched: Compact RSEQ concurrency IDs in batches
  rseq/selftests: Add test for mm_cid compaction

 include/linux/mm_types.h                      |   8 +
 init/Kconfig                                  |  12 +
 kernel/sched/core.c                           |  27 ++-
 tools/testing/selftests/rseq/.gitignore       |   1 +
 tools/testing/selftests/rseq/Makefile         |   2 +-
 .../selftests/rseq/mm_cid_compaction_test.c   | 208 ++++++++++++++++++
 6 files changed, 254 insertions(+), 4 deletions(-)
 create mode 100644 tools/testing/selftests/rseq/mm_cid_compaction_test.c

-- 
2.48.1

[PATCH 1/2] sched: Compact RSEQ concurrency IDs in batches

[Gabriele Monaco]

Currently, the task_mm_cid_work function is called in a task work
triggered by a scheduler tick to frequently compact the mm_cids of each
process for each core. This can delay the execution of the corresponding
thread for the entire duration of the function, negatively affecting the
response in case of real time tasks. In practice, we observe
task_mm_cid_work increasing the latency of 30-35us on a 128 cores
system, this order of magnitude is meaningful under PREEMPT_RT.

Run the task_mm_cid_work in batches of up to CONFIG_RSEQ_CID_SCAN_BATCH
cpus, this contains the duration of the delay for each scan.
Also improve the duration by iterating for all present cpus and not for
all possible.

The task_mm_cid_work already contains a mechanism to avoid running more
frequently than every 100ms, considering the function runs at every
tick, assuming ticks every 1ms (HZ=1000 is common on distros) and
assuming an unfavorable scenario of 1/10 ticks during task T runtime, we
can compact the CIDs for task T in about 130ms by setting
CONFIG_RSEQ_CID_SCAN_BATCH to 10 on a 128 cores machine.
This value also drastically reduces the task work duration and is a more
acceptable latency for the aforementioned machine.

Fixes: 223baf9d17f2 ("sched: Fix performance regression introduced by mm_cid")
Signed-off-by: Gabriele Monaco <gmonaco@redhat.com>
---
 include/linux/mm_types.h |  8 ++++++++
 init/Kconfig             | 12 ++++++++++++
 kernel/sched/core.c      | 27 ++++++++++++++++++++++++---
 3 files changed, 44 insertions(+), 3 deletions(-)

diff --git a/include/linux/mm_types.h b/include/linux/mm_types.h
index 0234f14f2aa6b..1e0e491d2c5c2 100644
--- a/include/linux/mm_types.h
+++ b/include/linux/mm_types.h
@@ -867,6 +867,13 @@ struct mm_struct {
 		 * When the next mm_cid scan is due (in jiffies).
 		 */
 		unsigned long mm_cid_next_scan;
+		/*
+		 * @mm_cid_scan_cpu: Which cpu to start from in the next scan
+		 *
+		 * Scan in batches of CONFIG_RSEQ_CID_SCAN_BATCH after each scan
+		 * save the next cpu index here (or 0 if we are done)
+		 */
+		unsigned int mm_cid_scan_cpu;
 		/**
 		 * @nr_cpus_allowed: Number of CPUs allowed for mm.
 		 *
@@ -1249,6 +1256,7 @@ static inline void mm_init_cid(struct mm_struct *mm, struct task_struct *p)
 	raw_spin_lock_init(&mm->cpus_allowed_lock);
 	cpumask_copy(mm_cpus_allowed(mm), &p->cpus_mask);
 	cpumask_clear(mm_cidmask(mm));
+	mm->mm_cid_scan_cpu = 0;
 }
 
 static inline int mm_alloc_cid_noprof(struct mm_struct *mm, struct task_struct *p)
diff --git a/init/Kconfig b/init/Kconfig
index d0d021b3fa3b3..39f1d4c7980c0 100644
--- a/init/Kconfig
+++ b/init/Kconfig
@@ -1813,6 +1813,18 @@ config DEBUG_RSEQ
 
 	  If unsure, say N.
 
+config RSEQ_CID_SCAN_BATCH
+	int "Number of CPUs to scan every time we attempt mm_cid compaction"
+	range 1 NR_CPUS
+	default 10
+	depends on SCHED_MM_CID
+	help
+	  CPUs are scanned pseudo-periodically to compact the CID of each task,
+	  this operation can take a longer amount of time on systems with many
+	  CPUs, resulting in higher scheduling latency for the current task.
+	  A higher value means the CID is compacted faster, but results in
+	  higher scheduling latency.
+
 config CACHESTAT_SYSCALL
 	bool "Enable cachestat() system call" if EXPERT
 	default y
diff --git a/kernel/sched/core.c b/kernel/sched/core.c
index 9aecd914ac691..8d1cce4ed62c6 100644
--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -10536,7 +10536,7 @@ static void task_mm_cid_work(struct callback_head *work)
 	struct task_struct *t = current;
 	struct cpumask *cidmask;
 	struct mm_struct *mm;
-	int weight, cpu;
+	int weight, cpu, from_cpu, to_cpu;
 
 	SCHED_WARN_ON(t != container_of(work, struct task_struct, cid_work));
 
@@ -10546,6 +10546,15 @@ static void task_mm_cid_work(struct callback_head *work)
 	mm = t->mm;
 	if (!mm)
 		return;
+	cpu = from_cpu = READ_ONCE(mm->mm_cid_scan_cpu);
+	to_cpu = from_cpu + CONFIG_RSEQ_CID_SCAN_BATCH;
+	if (from_cpu > cpumask_last(cpu_present_mask)) {
+		from_cpu = 0;
+		to_cpu = CONFIG_RSEQ_CID_SCAN_BATCH;
+	}
+	if (from_cpu != 0)
+		/* Delay scan only if we are done with all cpus. */
+		goto cid_compact;
 	old_scan = READ_ONCE(mm->mm_cid_next_scan);
 	next_scan = now + msecs_to_jiffies(MM_CID_SCAN_DELAY);
 	if (!old_scan) {
@@ -10561,17 +10570,29 @@ static void task_mm_cid_work(struct callback_head *work)
 		return;
 	if (!try_cmpxchg(&mm->mm_cid_next_scan, &old_scan, next_scan))
 		return;
+
+cid_compact:
+	if (!try_cmpxchg(&mm->mm_cid_scan_cpu, &cpu, to_cpu))
+		return;
 	cidmask = mm_cidmask(mm);
 	/* Clear cids that were not recently used. */
-	for_each_possible_cpu(cpu)
+	cpu = from_cpu;
+	for_each_cpu_from(cpu, cpu_present_mask) {
+		if (cpu == to_cpu)
+			break;
 		sched_mm_cid_remote_clear_old(mm, cpu);
+	}
 	weight = cpumask_weight(cidmask);
 	/*
 	 * Clear cids that are greater or equal to the cidmask weight to
 	 * recompact it.
 	 */
-	for_each_possible_cpu(cpu)
+	cpu = from_cpu;
+	for_each_cpu_from(cpu, cpu_present_mask) {
+		if (cpu == to_cpu)
+			break;
 		sched_mm_cid_remote_clear_weight(mm, cpu, weight);
+	}
 }
 
 void init_sched_mm_cid(struct task_struct *t)
-- 
2.48.1

[PATCH 2/2] rseq/selftests: Add test for mm_cid compaction

[Gabriele Monaco]

A task in the kernel (task_mm_cid_work) runs somewhat periodically to
compact the mm_cid for each process. Add a test to validate that it runs
correctly and timely.

The test spawns 1 thread pinned to each CPU, then each thread, including
the main one, runs in short bursts for some time. During this period, the
mm_cids should be spanning all numbers between 0 and nproc.

At the end of this phase, a thread with high enough mm_cid (>= nproc/2)
is selected to be the new leader, all other threads terminate.

After some time, the only running thread should see 0 as mm_cid, if that
doesn't happen, the compaction mechanism didn't work and the test fails.

Since mm_cid compaction is less likely for tasks running in short
bursts, we increase the likelihood by just running a busy loop at every
iteration. This compaction is a best effort work and this behaviour is
currently acceptable.

The test never fails if only 1 core is available, in which case, we
cannot test anything as the only available mm_cid is 0.

Reviewed-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Signed-off-by: Gabriele Monaco <gmonaco@redhat.com>
---
 tools/testing/selftests/rseq/.gitignore       |   1 +
 tools/testing/selftests/rseq/Makefile         |   2 +-
 .../selftests/rseq/mm_cid_compaction_test.c   | 208 ++++++++++++++++++
 3 files changed, 210 insertions(+), 1 deletion(-)
 create mode 100644 tools/testing/selftests/rseq/mm_cid_compaction_test.c

diff --git a/tools/testing/selftests/rseq/.gitignore b/tools/testing/selftests/rseq/.gitignore
index 16496de5f6ce4..2c89f97e4f737 100644
--- a/tools/testing/selftests/rseq/.gitignore
+++ b/tools/testing/selftests/rseq/.gitignore
@@ -3,6 +3,7 @@ basic_percpu_ops_test
 basic_percpu_ops_mm_cid_test
 basic_test
 basic_rseq_op_test
+mm_cid_compaction_test
 param_test
 param_test_benchmark
 param_test_compare_twice
diff --git a/tools/testing/selftests/rseq/Makefile b/tools/testing/selftests/rseq/Makefile
index 5a3432fceb586..ce1b38f46a355 100644
--- a/tools/testing/selftests/rseq/Makefile
+++ b/tools/testing/selftests/rseq/Makefile
@@ -16,7 +16,7 @@ OVERRIDE_TARGETS = 1
 
 TEST_GEN_PROGS = basic_test basic_percpu_ops_test basic_percpu_ops_mm_cid_test param_test \
 		param_test_benchmark param_test_compare_twice param_test_mm_cid \
-		param_test_mm_cid_benchmark param_test_mm_cid_compare_twice
+		param_test_mm_cid_benchmark param_test_mm_cid_compare_twice mm_cid_compaction_test
 
 TEST_GEN_PROGS_EXTENDED = librseq.so
 
diff --git a/tools/testing/selftests/rseq/mm_cid_compaction_test.c b/tools/testing/selftests/rseq/mm_cid_compaction_test.c
new file mode 100644
index 0000000000000..8808500466d02
--- /dev/null
+++ b/tools/testing/selftests/rseq/mm_cid_compaction_test.c
@@ -0,0 +1,208 @@
+// SPDX-License-Identifier: LGPL-2.1
+#define _GNU_SOURCE
+#include <assert.h>
+#include <pthread.h>
+#include <sched.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <stddef.h>
+
+#include "../kselftest.h"
+#include "rseq.h"
+
+#define VERBOSE 0
+#define printf_verbose(fmt, ...)                    \
+	do {                                        \
+		if (VERBOSE)                        \
+			printf(fmt, ##__VA_ARGS__); \
+	} while (0)
+
+/* 0.5 s */
+#define RUNNER_PERIOD 500000
+/* Number of runs before we terminate or get the token */
+#define THREAD_RUNS 5
+
+/*
+ * Number of times we check that the mm_cid were compacted.
+ * Checks are repeated every RUNNER_PERIOD.
+ */
+#define MM_CID_COMPACT_TIMEOUT 10
+
+struct thread_args {
+	int cpu;
+	int num_cpus;
+	pthread_mutex_t *token;
+	pthread_barrier_t *barrier;
+	pthread_t *tinfo;
+	struct thread_args *args_head;
+};
+
+static void __noreturn *thread_runner(void *arg)
+{
+	struct thread_args *args = arg;
+	int i, ret, curr_mm_cid;
+	cpu_set_t cpumask;
+
+	CPU_ZERO(&cpumask);
+	CPU_SET(args->cpu, &cpumask);
+	ret = pthread_setaffinity_np(pthread_self(), sizeof(cpumask), &cpumask);
+	if (ret) {
+		errno = ret;
+		perror("Error: failed to set affinity");
+		abort();
+	}
+	pthread_barrier_wait(args->barrier);
+
+	for (i = 0; i < THREAD_RUNS; i++)
+		usleep(RUNNER_PERIOD);
+	curr_mm_cid = rseq_current_mm_cid();
+	/*
+	 * We select one thread with high enough mm_cid to be the new leader.
+	 * All other threads (including the main thread) will terminate.
+	 * After some time, the mm_cid of the only remaining thread should
+	 * converge to 0, if not, the test fails.
+	 */
+	if (curr_mm_cid >= args->num_cpus / 2 &&
+	    !pthread_mutex_trylock(args->token)) {
+		printf_verbose(
+			"cpu%d has mm_cid=%d and will be the new leader.\n",
+			sched_getcpu(), curr_mm_cid);
+		for (i = 0; i < args->num_cpus; i++) {
+			if (args->tinfo[i] == pthread_self())
+				continue;
+			ret = pthread_join(args->tinfo[i], NULL);
+			if (ret) {
+				errno = ret;
+				perror("Error: failed to join thread");
+				abort();
+			}
+		}
+		pthread_barrier_destroy(args->barrier);
+		free(args->tinfo);
+		free(args->token);
+		free(args->barrier);
+		free(args->args_head);
+
+		for (i = 0; i < MM_CID_COMPACT_TIMEOUT; i++) {
+			curr_mm_cid = rseq_current_mm_cid();
+			printf_verbose("run %d: mm_cid=%d on cpu%d.\n", i,
+				       curr_mm_cid, sched_getcpu());
+			if (curr_mm_cid == 0)
+				exit(EXIT_SUCCESS);
+			/*
+			 * Currently mm_cid compaction is less likely for tasks
+			 * running in short bursts: increase likelihood by just
+			 * running for some time doing nothing.
+			 */
+			for (int j = 0; j < 0xffff; j++)
+				for (int k = 0; k < 0xffff; k++)
+					asm("");
+			usleep(RUNNER_PERIOD);
+		}
+		exit(EXIT_FAILURE);
+	}
+	printf_verbose("cpu%d has mm_cid=%d and is going to terminate.\n",
+		       sched_getcpu(), curr_mm_cid);
+	pthread_exit(NULL);
+}
+
+int test_mm_cid_compaction(void)
+{
+	cpu_set_t affinity;
+	int i, j, ret = 0, num_threads;
+	pthread_t *tinfo;
+	pthread_mutex_t *token;
+	pthread_barrier_t *barrier;
+	struct thread_args *args;
+
+	sched_getaffinity(0, sizeof(affinity), &affinity);
+	num_threads = CPU_COUNT(&affinity);
+	tinfo = calloc(num_threads, sizeof(*tinfo));
+	if (!tinfo) {
+		perror("Error: failed to allocate tinfo");
+		return -1;
+	}
+	args = calloc(num_threads, sizeof(*args));
+	if (!args) {
+		perror("Error: failed to allocate args");
+		ret = -1;
+		goto out_free_tinfo;
+	}
+	token = malloc(sizeof(*token));
+	if (!token) {
+		perror("Error: failed to allocate token");
+		ret = -1;
+		goto out_free_args;
+	}
+	barrier = malloc(sizeof(*barrier));
+	if (!barrier) {
+		perror("Error: failed to allocate barrier");
+		ret = -1;
+		goto out_free_token;
+	}
+	if (num_threads == 1) {
+		fprintf(stderr, "Cannot test on a single cpu. "
+				"Skipping mm_cid_compaction test.\n");
+		/* only skipping the test, this is not a failure */
+		goto out_free_barrier;
+	}
+	pthread_mutex_init(token, NULL);
+	ret = pthread_barrier_init(barrier, NULL, num_threads);
+	if (ret) {
+		errno = ret;
+		perror("Error: failed to initialise barrier");
+		goto out_free_barrier;
+	}
+	for (i = 0, j = 0; i < CPU_SETSIZE && j < num_threads; i++) {
+		if (!CPU_ISSET(i, &affinity))
+			continue;
+		args[j].num_cpus = num_threads;
+		args[j].tinfo = tinfo;
+		args[j].token = token;
+		args[j].barrier = barrier;
+		args[j].cpu = i;
+		args[j].args_head = args;
+		if (!j) {
+			/* The first thread is the main one */
+			tinfo[0] = pthread_self();
+			++j;
+			continue;
+		}
+		ret = pthread_create(&tinfo[j], NULL, thread_runner, &args[j]);
+		if (ret) {
+			errno = ret;
+			perror("Error: failed to create thread");
+			abort();
+		}
+		++j;
+	}
+	printf_verbose("Started %d threads.\n", num_threads);
+
+	/* Also main thread will terminate if it is not selected as leader */
+	thread_runner(&args[0]);
+
+	/* only reached in case of errors */
+out_free_barrier:
+	free(barrier);
+out_free_token:
+	free(token);
+out_free_args:
+	free(args);
+out_free_tinfo:
+	free(tinfo);
+
+	return ret;
+}
+
+int main(int argc, char **argv)
+{
+	if (!rseq_mm_cid_available()) {
+		fprintf(stderr, "Error: rseq_mm_cid unavailable\n");
+		return -1;
+	}
+	if (test_mm_cid_compaction())
+		return -1;
+	return 0;
+}
-- 
2.48.1

Re: [PATCH 1/2] sched: Compact RSEQ concurrency IDs in batches

[Mathieu Desnoyers]

On 2025-02-17 06:23, Gabriele Monaco wrote:
> Currently, the task_mm_cid_work function is called in a task work
> triggered by a scheduler tick to frequently compact the mm_cids of each
> process for each core. This can delay the execution of the corresponding
> thread for the entire duration of the function, negatively affecting the
> response in case of real time tasks. In practice, we observe
> task_mm_cid_work increasing the latency of 30-35us on a 128 cores
> system, this order of magnitude is meaningful under PREEMPT_RT.
> 
> Run the task_mm_cid_work in batches of up to CONFIG_RSEQ_CID_SCAN_BATCH
> cpus, this contains the duration of the delay for each scan.
> Also improve the duration by iterating for all present cpus and not for
> all possible.

Iterating only on present cpus is not enough on CONFIG_HOTPLUG=y,
because ACPI can dynamically add/remove CPUs from the set. If we end
up iterating only on present cpus, then we need to add a cpu hotplug
callback to handle the removal case, and I'm not sure the added
complexity is worth it here.

> 
> The task_mm_cid_work already contains a mechanism to avoid running more
> frequently than every 100ms, considering the function runs at every
> tick, assuming ticks every 1ms (HZ=1000 is common on distros) and
> assuming an unfavorable scenario of 1/10 ticks during task T runtime, we
> can compact the CIDs for task T in about 130ms by setting
> CONFIG_RSEQ_CID_SCAN_BATCH to 10 on a 128 cores machine.
> This value also drastically reduces the task work duration and is a more
> acceptable latency for the aforementioned machine.
> 
> Fixes: 223baf9d17f2 ("sched: Fix performance regression introduced by mm_cid")
> Signed-off-by: Gabriele Monaco <gmonaco@redhat.com>
> ---
>   include/linux/mm_types.h |  8 ++++++++
>   init/Kconfig             | 12 ++++++++++++
>   kernel/sched/core.c      | 27 ++++++++++++++++++++++++---
>   3 files changed, 44 insertions(+), 3 deletions(-)
> 
> diff --git a/include/linux/mm_types.h b/include/linux/mm_types.h
> index 0234f14f2aa6b..1e0e491d2c5c2 100644
> --- a/include/linux/mm_types.h
> +++ b/include/linux/mm_types.h
> @@ -867,6 +867,13 @@ struct mm_struct {
>   		 * When the next mm_cid scan is due (in jiffies).
>   		 */
>   		unsigned long mm_cid_next_scan;
> +		/*
> +		 * @mm_cid_scan_cpu: Which cpu to start from in the next scan

Other similar comments have a "." at end of line.

> +		 *
> +		 * Scan in batches of CONFIG_RSEQ_CID_SCAN_BATCH after each scan
> +		 * save the next cpu index here (or 0 if we are done)

Suggested rewording:

Scan in batches of CONFIG_RSEQ_CID_SCAN_BATCH. This field holds
the next cpu index after each scan, or 0 if all batches are
done.


> +		 */
> +		unsigned int mm_cid_scan_cpu;
>   		/**
>   		 * @nr_cpus_allowed: Number of CPUs allowed for mm.
>   		 *
> @@ -1249,6 +1256,7 @@ static inline void mm_init_cid(struct mm_struct *mm, struct task_struct *p)
>   	raw_spin_lock_init(&mm->cpus_allowed_lock);
>   	cpumask_copy(mm_cpus_allowed(mm), &p->cpus_mask);
>   	cpumask_clear(mm_cidmask(mm));
> +	mm->mm_cid_scan_cpu = 0;
>   }
>   
>   static inline int mm_alloc_cid_noprof(struct mm_struct *mm, struct task_struct *p)
> diff --git a/init/Kconfig b/init/Kconfig
> index d0d021b3fa3b3..39f1d4c7980c0 100644
> --- a/init/Kconfig
> +++ b/init/Kconfig
> @@ -1813,6 +1813,18 @@ config DEBUG_RSEQ
>   
>   	  If unsure, say N.
>   
> +config RSEQ_CID_SCAN_BATCH
> +	int "Number of CPUs to scan every time we attempt mm_cid compaction"

Reword without "we".

> +	range 1 NR_CPUS
> +	default 10
> +	depends on SCHED_MM_CID
> +	help
> +	  CPUs are scanned pseudo-periodically to compact the CID of each task,
> +	  this operation can take a longer amount of time on systems with many
> +	  CPUs, resulting in higher scheduling latency for the current task.
> +	  A higher value means the CID is compacted faster, but results in
> +	  higher scheduling latency.
> +
>   config CACHESTAT_SYSCALL
>   	bool "Enable cachestat() system call" if EXPERT
>   	default y
> diff --git a/kernel/sched/core.c b/kernel/sched/core.c
> index 9aecd914ac691..8d1cce4ed62c6 100644
> --- a/kernel/sched/core.c
> +++ b/kernel/sched/core.c
> @@ -10536,7 +10536,7 @@ static void task_mm_cid_work(struct callback_head *work)
>   	struct task_struct *t = current;
>   	struct cpumask *cidmask;
>   	struct mm_struct *mm;
> -	int weight, cpu;
> +	int weight, cpu, from_cpu, to_cpu;
>   
>   	SCHED_WARN_ON(t != container_of(work, struct task_struct, cid_work));
>   
> @@ -10546,6 +10546,15 @@ static void task_mm_cid_work(struct callback_head *work)
>   	mm = t->mm;
>   	if (!mm)
>   		return;
> +	cpu = from_cpu = READ_ONCE(mm->mm_cid_scan_cpu);
> +	to_cpu = from_cpu + CONFIG_RSEQ_CID_SCAN_BATCH;
> +	if (from_cpu > cpumask_last(cpu_present_mask)) {

See explanation about using possible rather than present.

> +		from_cpu = 0;
> +		to_cpu = CONFIG_RSEQ_CID_SCAN_BATCH;

If the cpu_possible_mask is sparsely populated, this will end
up doing batches that hit very few cpus. Instead, we should
count how many cpus are handled within each
for_each_cpu_from(cpu, cpu_possible_mask) loops below and break
when reaching CONFIG_RSEQ_CID_SCAN_BATCH.

> +	}
> +	if (from_cpu != 0)
> +		/* Delay scan only if we are done with all cpus. */
> +		goto cid_compact;
>   	old_scan = READ_ONCE(mm->mm_cid_next_scan);
>   	next_scan = now + msecs_to_jiffies(MM_CID_SCAN_DELAY);
>   	if (!old_scan) {
> @@ -10561,17 +10570,29 @@ static void task_mm_cid_work(struct callback_head *work)
>   		return;
>   	if (!try_cmpxchg(&mm->mm_cid_next_scan, &old_scan, next_scan))
>   		return;
> +
> +cid_compact:
> +	if (!try_cmpxchg(&mm->mm_cid_scan_cpu, &cpu, to_cpu))
> +		return;
>   	cidmask = mm_cidmask(mm);
>   	/* Clear cids that were not recently used. */
> -	for_each_possible_cpu(cpu)
> +	cpu = from_cpu;
> +	for_each_cpu_from(cpu, cpu_present_mask) {
> +		if (cpu == to_cpu)
> +			break;
>   		sched_mm_cid_remote_clear_old(mm, cpu);
> +	}
>   	weight = cpumask_weight(cidmask);
>   	/*
>   	 * Clear cids that are greater or equal to the cidmask weight to
>   	 * recompact it.
>   	 */
> -	for_each_possible_cpu(cpu)
> +	cpu = from_cpu;
> +	for_each_cpu_from(cpu, cpu_present_mask) {
> +		if (cpu == to_cpu)
> +			break;
>   		sched_mm_cid_remote_clear_weight(mm, cpu, weight);
> +	}

Here set mm->mm_cid_scan_cpu to the new next position which is
the result from the "for each" loop.

Thanks,

Mathieu

>   }
>   
>   void init_sched_mm_cid(struct task_struct *t)


-- 
Mathieu Desnoyers
EfficiOS Inc.
https://www.efficios.com

Re: [PATCH 2/2] rseq/selftests: Add test for mm_cid compaction

[Mathieu Desnoyers]

On 2025-02-17 06:23, Gabriele Monaco wrote:
> A task in the kernel (task_mm_cid_work) runs somewhat periodically to
> compact the mm_cid for each process. Add a test to validate that it runs
> correctly and timely.
> 
> The test spawns 1 thread pinned to each CPU, then each thread, including
> the main one, runs in short bursts for some time. During this period, the
> mm_cids should be spanning all numbers between 0 and nproc.
> 
> At the end of this phase, a thread with high enough mm_cid (>= nproc/2)
> is selected to be the new leader, all other threads terminate.
> 
> After some time, the only running thread should see 0 as mm_cid, if that
> doesn't happen, the compaction mechanism didn't work and the test fails.
> 
> Since mm_cid compaction is less likely for tasks running in short
> bursts, we increase the likelihood by just running a busy loop at every
> iteration. This compaction is a best effort work and this behaviour is
> currently acceptable.

I'm wondering what we can do to make this compaction scheme more
predictable.

The situation here is caused by the fact that the CID compaction
only happens on scheduler tick. If the workload is periodic and
runs in short bursts, chances are that the scheduler tick never
issue task_tick_mm_cid() for a given process, so no compaction.

So task_tick_mm_cid() basically does:

void task_tick_mm_cid(struct rq *rq, struct task_struct *curr)
{
         struct callback_head *work = &curr->cid_work;
         unsigned long now = jiffies;

         if (!curr->mm || (curr->flags & (PF_EXITING | PF_KTHREAD)) ||
             work->next != work)
                 return;
         if (time_before(now, READ_ONCE(curr->mm->mm_cid_next_scan)))
                 return;

         /* No page allocation under rq lock */
         task_work_add(curr, work, TWA_RESUME | TWAF_NO_ALLOC);
}

So typically we have a "time_before()" check that is hit and
paces the execution of this task_work every 100ms or so.

If we have periodic tasks, that means those tasks are necessarily
preempted so they are not current when the tick happens. If the
task cares about compaction of mm_cid, it means it has returned
to userspace after that preemption.

Sooo, we happen to have code in kernel/rseq.c called exactly at
that point:

__rseq_handle_notify_resume()

I wonder if we could perhaps just call task_tick_mm_cid() (or a version
of it renamed to something more meaningful) from
__rseq_handle_notify_resume() ? By combining time_before() checks from
the scheduler tick and at return to userspace after preemption, AFAIU
we'd be handling the periodic workload correctly, and therefore this
test for mm_cid compaction could check for more robust guarantees.

Thoughts ?

Thanks,

Mathieu

> 
> The test never fails if only 1 core is available, in which case, we
> cannot test anything as the only available mm_cid is 0.
> 
> Reviewed-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
> Signed-off-by: Gabriele Monaco <gmonaco@redhat.com>
> ---
>   tools/testing/selftests/rseq/.gitignore       |   1 +
>   tools/testing/selftests/rseq/Makefile         |   2 +-
>   .../selftests/rseq/mm_cid_compaction_test.c   | 208 ++++++++++++++++++
>   3 files changed, 210 insertions(+), 1 deletion(-)
>   create mode 100644 tools/testing/selftests/rseq/mm_cid_compaction_test.c
> 
> diff --git a/tools/testing/selftests/rseq/.gitignore b/tools/testing/selftests/rseq/.gitignore
> index 16496de5f6ce4..2c89f97e4f737 100644
> --- a/tools/testing/selftests/rseq/.gitignore
> +++ b/tools/testing/selftests/rseq/.gitignore
> @@ -3,6 +3,7 @@ basic_percpu_ops_test
>   basic_percpu_ops_mm_cid_test
>   basic_test
>   basic_rseq_op_test
> +mm_cid_compaction_test
>   param_test
>   param_test_benchmark
>   param_test_compare_twice
> diff --git a/tools/testing/selftests/rseq/Makefile b/tools/testing/selftests/rseq/Makefile
> index 5a3432fceb586..ce1b38f46a355 100644
> --- a/tools/testing/selftests/rseq/Makefile
> +++ b/tools/testing/selftests/rseq/Makefile
> @@ -16,7 +16,7 @@ OVERRIDE_TARGETS = 1
>   
>   TEST_GEN_PROGS = basic_test basic_percpu_ops_test basic_percpu_ops_mm_cid_test param_test \
>   		param_test_benchmark param_test_compare_twice param_test_mm_cid \
> -		param_test_mm_cid_benchmark param_test_mm_cid_compare_twice
> +		param_test_mm_cid_benchmark param_test_mm_cid_compare_twice mm_cid_compaction_test
>   
>   TEST_GEN_PROGS_EXTENDED = librseq.so
>   
> diff --git a/tools/testing/selftests/rseq/mm_cid_compaction_test.c b/tools/testing/selftests/rseq/mm_cid_compaction_test.c
> new file mode 100644
> index 0000000000000..8808500466d02
> --- /dev/null
> +++ b/tools/testing/selftests/rseq/mm_cid_compaction_test.c
> @@ -0,0 +1,208 @@
> +// SPDX-License-Identifier: LGPL-2.1
> +#define _GNU_SOURCE
> +#include <assert.h>
> +#include <pthread.h>
> +#include <sched.h>
> +#include <stdint.h>
> +#include <stdio.h>
> +#include <stdlib.h>
> +#include <string.h>
> +#include <stddef.h>
> +
> +#include "../kselftest.h"
> +#include "rseq.h"
> +
> +#define VERBOSE 0
> +#define printf_verbose(fmt, ...)                    \
> +	do {                                        \
> +		if (VERBOSE)                        \
> +			printf(fmt, ##__VA_ARGS__); \
> +	} while (0)
> +
> +/* 0.5 s */
> +#define RUNNER_PERIOD 500000
> +/* Number of runs before we terminate or get the token */
> +#define THREAD_RUNS 5
> +
> +/*
> + * Number of times we check that the mm_cid were compacted.
> + * Checks are repeated every RUNNER_PERIOD.
> + */
> +#define MM_CID_COMPACT_TIMEOUT 10
> +
> +struct thread_args {
> +	int cpu;
> +	int num_cpus;
> +	pthread_mutex_t *token;
> +	pthread_barrier_t *barrier;
> +	pthread_t *tinfo;
> +	struct thread_args *args_head;
> +};
> +
> +static void __noreturn *thread_runner(void *arg)
> +{
> +	struct thread_args *args = arg;
> +	int i, ret, curr_mm_cid;
> +	cpu_set_t cpumask;
> +
> +	CPU_ZERO(&cpumask);
> +	CPU_SET(args->cpu, &cpumask);
> +	ret = pthread_setaffinity_np(pthread_self(), sizeof(cpumask), &cpumask);
> +	if (ret) {
> +		errno = ret;
> +		perror("Error: failed to set affinity");
> +		abort();
> +	}
> +	pthread_barrier_wait(args->barrier);
> +
> +	for (i = 0; i < THREAD_RUNS; i++)
> +		usleep(RUNNER_PERIOD);
> +	curr_mm_cid = rseq_current_mm_cid();
> +	/*
> +	 * We select one thread with high enough mm_cid to be the new leader.
> +	 * All other threads (including the main thread) will terminate.
> +	 * After some time, the mm_cid of the only remaining thread should
> +	 * converge to 0, if not, the test fails.
> +	 */
> +	if (curr_mm_cid >= args->num_cpus / 2 &&
> +	    !pthread_mutex_trylock(args->token)) {
> +		printf_verbose(
> +			"cpu%d has mm_cid=%d and will be the new leader.\n",
> +			sched_getcpu(), curr_mm_cid);
> +		for (i = 0; i < args->num_cpus; i++) {
> +			if (args->tinfo[i] == pthread_self())
> +				continue;
> +			ret = pthread_join(args->tinfo[i], NULL);
> +			if (ret) {
> +				errno = ret;
> +				perror("Error: failed to join thread");
> +				abort();
> +			}
> +		}
> +		pthread_barrier_destroy(args->barrier);
> +		free(args->tinfo);
> +		free(args->token);
> +		free(args->barrier);
> +		free(args->args_head);
> +
> +		for (i = 0; i < MM_CID_COMPACT_TIMEOUT; i++) {
> +			curr_mm_cid = rseq_current_mm_cid();
> +			printf_verbose("run %d: mm_cid=%d on cpu%d.\n", i,
> +				       curr_mm_cid, sched_getcpu());
> +			if (curr_mm_cid == 0)
> +				exit(EXIT_SUCCESS);
> +			/*
> +			 * Currently mm_cid compaction is less likely for tasks
> +			 * running in short bursts: increase likelihood by just
> +			 * running for some time doing nothing.
> +			 */
> +			for (int j = 0; j < 0xffff; j++)
> +				for (int k = 0; k < 0xffff; k++)
> +					asm("");
> +			usleep(RUNNER_PERIOD);
> +		}
> +		exit(EXIT_FAILURE);
> +	}
> +	printf_verbose("cpu%d has mm_cid=%d and is going to terminate.\n",
> +		       sched_getcpu(), curr_mm_cid);
> +	pthread_exit(NULL);
> +}
> +
> +int test_mm_cid_compaction(void)
> +{
> +	cpu_set_t affinity;
> +	int i, j, ret = 0, num_threads;
> +	pthread_t *tinfo;
> +	pthread_mutex_t *token;
> +	pthread_barrier_t *barrier;
> +	struct thread_args *args;
> +
> +	sched_getaffinity(0, sizeof(affinity), &affinity);
> +	num_threads = CPU_COUNT(&affinity);
> +	tinfo = calloc(num_threads, sizeof(*tinfo));
> +	if (!tinfo) {
> +		perror("Error: failed to allocate tinfo");
> +		return -1;
> +	}
> +	args = calloc(num_threads, sizeof(*args));
> +	if (!args) {
> +		perror("Error: failed to allocate args");
> +		ret = -1;
> +		goto out_free_tinfo;
> +	}
> +	token = malloc(sizeof(*token));
> +	if (!token) {
> +		perror("Error: failed to allocate token");
> +		ret = -1;
> +		goto out_free_args;
> +	}
> +	barrier = malloc(sizeof(*barrier));
> +	if (!barrier) {
> +		perror("Error: failed to allocate barrier");
> +		ret = -1;
> +		goto out_free_token;
> +	}
> +	if (num_threads == 1) {
> +		fprintf(stderr, "Cannot test on a single cpu. "
> +				"Skipping mm_cid_compaction test.\n");
> +		/* only skipping the test, this is not a failure */
> +		goto out_free_barrier;
> +	}
> +	pthread_mutex_init(token, NULL);
> +	ret = pthread_barrier_init(barrier, NULL, num_threads);
> +	if (ret) {
> +		errno = ret;
> +		perror("Error: failed to initialise barrier");
> +		goto out_free_barrier;
> +	}
> +	for (i = 0, j = 0; i < CPU_SETSIZE && j < num_threads; i++) {
> +		if (!CPU_ISSET(i, &affinity))
> +			continue;
> +		args[j].num_cpus = num_threads;
> +		args[j].tinfo = tinfo;
> +		args[j].token = token;
> +		args[j].barrier = barrier;
> +		args[j].cpu = i;
> +		args[j].args_head = args;
> +		if (!j) {
> +			/* The first thread is the main one */
> +			tinfo[0] = pthread_self();
> +			++j;
> +			continue;
> +		}
> +		ret = pthread_create(&tinfo[j], NULL, thread_runner, &args[j]);
> +		if (ret) {
> +			errno = ret;
> +			perror("Error: failed to create thread");
> +			abort();
> +		}
> +		++j;
> +	}
> +	printf_verbose("Started %d threads.\n", num_threads);
> +
> +	/* Also main thread will terminate if it is not selected as leader */
> +	thread_runner(&args[0]);
> +
> +	/* only reached in case of errors */
> +out_free_barrier:
> +	free(barrier);
> +out_free_token:
> +	free(token);
> +out_free_args:
> +	free(args);
> +out_free_tinfo:
> +	free(tinfo);
> +
> +	return ret;
> +}
> +
> +int main(int argc, char **argv)
> +{
> +	if (!rseq_mm_cid_available()) {
> +		fprintf(stderr, "Error: rseq_mm_cid unavailable\n");
> +		return -1;
> +	}
> +	if (test_mm_cid_compaction())
> +		return -1;
> +	return 0;
> +}


-- 
Mathieu Desnoyers
EfficiOS Inc.
https://www.efficios.com

Re: [PATCH 2/2] rseq/selftests: Add test for mm_cid compaction

[Gabriele Monaco]

On Mon, 2025-02-17 at 14:59 -0500, Mathieu Desnoyers wrote:
> On 2025-02-17 06:23, Gabriele Monaco wrote:
> > A task in the kernel (task_mm_cid_work) runs somewhat periodically
> > to
> > compact the mm_cid for each process. Add a test to validate that it
> > runs
> > correctly and timely.
> > 
> > The test spawns 1 thread pinned to each CPU, then each thread,
> > including
> > the main one, runs in short bursts for some time. During this
> > period, the
> > mm_cids should be spanning all numbers between 0 and nproc.
> > 
> > At the end of this phase, a thread with high enough mm_cid (>=
> > nproc/2)
> > is selected to be the new leader, all other threads terminate.
> > 
> > After some time, the only running thread should see 0 as mm_cid, if
> > that
> > doesn't happen, the compaction mechanism didn't work and the test
> > fails.
> > 
> > Since mm_cid compaction is less likely for tasks running in short
> > bursts, we increase the likelihood by just running a busy loop at
> > every
> > iteration. This compaction is a best effort work and this behaviour
> > is
> > currently acceptable.
> 
> I'm wondering what we can do to make this compaction scheme more
> predictable.
> 
> The situation here is caused by the fact that the CID compaction
> only happens on scheduler tick. If the workload is periodic and
> runs in short bursts, chances are that the scheduler tick never
> issue task_tick_mm_cid() for a given process, so no compaction.
> 
> So task_tick_mm_cid() basically does:
> 
> void task_tick_mm_cid(struct rq *rq, struct task_struct *curr)
> {
>          struct callback_head *work = &curr->cid_work;
>          unsigned long now = jiffies;
> 
>          if (!curr->mm || (curr->flags & (PF_EXITING | PF_KTHREAD))
> ||
>              work->next != work)
>                  return;
>          if (time_before(now, READ_ONCE(curr->mm->mm_cid_next_scan)))
>                  return;
> 
>          /* No page allocation under rq lock */
>          task_work_add(curr, work, TWA_RESUME | TWAF_NO_ALLOC);
> }
> 
> So typically we have a "time_before()" check that is hit and
> paces the execution of this task_work every 100ms or so.
> 
> If we have periodic tasks, that means those tasks are necessarily
> preempted so they are not current when the tick happens. If the
> task cares about compaction of mm_cid, it means it has returned
> to userspace after that preemption.
> 
> Sooo, we happen to have code in kernel/rseq.c called exactly at
> that point:
> 
> __rseq_handle_notify_resume()
> 
> I wonder if we could perhaps just call task_tick_mm_cid() (or a
> version
> of it renamed to something more meaningful) from
> __rseq_handle_notify_resume() ? By combining time_before() checks
> from
> the scheduler tick and at return to userspace after preemption, AFAIU
> we'd be handling the periodic workload correctly, and therefore this
> test for mm_cid compaction could check for more robust guarantees.
> 
> Thoughts ?

Alright, that seems better, since the task work already runs there
(resume_user_mode_work), it's only set as pending once we get the tick,
I agree that seems a bit redundant.

In this case I'd see calling the task_mm_cid_work where
rseq_handle_notify_resume is called and not the task_tick_mm_cid.

The way I see it, rseq_handle_notify_resume is behaving essentially
like a task_work with TWA_RESUME (setting TIF_NOTIFY_RESUME on its own
at syscalls, task switches and migrations). task_mm_cid_work, instead
sets TIF_NOTIFY_RESUME on ticks (via the task_work API). This last bit
could change, conceptually I mean, we probably don't want to use
task_work at all in such contexts.

Does this make sense to you?


However, I'm still not particularly fond of running stuff there at all.
If a periodic task needs to run now, it preempts everything else and
should be on its way as soon as possible. A task work is always going
to delay this, although by a tiny bit.

Again, for now I cannot think of a better way without bringing
workqueues into the picture, and in this specific case we have a valid
workaround to reduce the latency.

Thanks,
Gabriele

Re: [PATCH 1/2] sched: Compact RSEQ concurrency IDs in batches

[Gabriele Monaco]

On Mon, 2025-02-17 at 14:46 -0500, Mathieu Desnoyers wrote:
> On 2025-02-17 06:23, Gabriele Monaco wrote:
> > Currently, the task_mm_cid_work function is called in a task work
> > triggered by a scheduler tick to frequently compact the mm_cids of
> > each
> > process for each core. This can delay the execution of the
> > corresponding
> > thread for the entire duration of the function, negatively
> > affecting the
> > response in case of real time tasks. In practice, we observe
> > task_mm_cid_work increasing the latency of 30-35us on a 128 cores
> > system, this order of magnitude is meaningful under PREEMPT_RT.
> > 
> > Run the task_mm_cid_work in batches of up to
> > CONFIG_RSEQ_CID_SCAN_BATCH
> > cpus, this contains the duration of the delay for each scan.
> > Also improve the duration by iterating for all present cpus and not
> > for
> > all possible.
> 
> Iterating only on present cpus is not enough on CONFIG_HOTPLUG=y,
> because ACPI can dynamically add/remove CPUs from the set. If we end
> up iterating only on present cpus, then we need to add a cpu hotplug
> callback to handle the removal case, and I'm not sure the added
> complexity is worth it here.
> 

Got it, didn't think of that..

> > 
> > The task_mm_cid_work already contains a mechanism to avoid running
> > more
> > frequently than every 100ms, considering the function runs at every
> > tick, assuming ticks every 1ms (HZ=1000 is common on distros) and
> > assuming an unfavorable scenario of 1/10 ticks during task T
> > runtime, we
> > can compact the CIDs for task T in about 130ms by setting
> > CONFIG_RSEQ_CID_SCAN_BATCH to 10 on a 128 cores machine.
> > This value also drastically reduces the task work duration and is a
> > more
> > acceptable latency for the aforementioned machine.
> > 
> > Fixes: 223baf9d17f2 ("sched: Fix performance regression introduced
> > by mm_cid")
> > Signed-off-by: Gabriele Monaco <gmonaco@redhat.com>
> > ---
> >   include/linux/mm_types.h |  8 ++++++++
> >   init/Kconfig             | 12 ++++++++++++
> >   kernel/sched/core.c      | 27 ++++++++++++++++++++++++---
> >   3 files changed, 44 insertions(+), 3 deletions(-)
> >   
> > @@ -10546,6 +10546,15 @@ static void task_mm_cid_work(struct
> > callback_head *work)
> >   	mm = t->mm;
> >   	if (!mm)
> >   		return;
> > +	cpu = from_cpu = READ_ONCE(mm->mm_cid_scan_cpu);
> > +	to_cpu = from_cpu + CONFIG_RSEQ_CID_SCAN_BATCH;
> > +	if (from_cpu > cpumask_last(cpu_present_mask)) {
> 
> See explanation about using possible rather than present.
> 
> > +		from_cpu = 0;
> > +		to_cpu = CONFIG_RSEQ_CID_SCAN_BATCH;
> 
> If the cpu_possible_mask is sparsely populated, this will end
> up doing batches that hit very few cpus. Instead, we should
> count how many cpus are handled within each
> for_each_cpu_from(cpu, cpu_possible_mask) loops below and break
> when reaching CONFIG_RSEQ_CID_SCAN_BATCH.
> 
> > +	}
> > [...]
> > +	for_each_cpu_from(cpu, cpu_present_mask) {
> > +		if (cpu == to_cpu)
> > +			break;
> >   		sched_mm_cid_remote_clear_weight(mm, cpu, weight);
> > +	}
> 
> Here set mm->mm_cid_scan_cpu to the new next position which is
> the result from the "for each" loop.
> 

Mmh, good point, I wonder though if we need to care for multiple
threads scanning the same mm concurrently. In my patch it shouldn't
happen (threads /book/ up to to_cpu writing it before scanning).
To do so, I'd probably need to create a map with N elements starting
from from_cpu and use that, or have a dry loop before actually
scanning.

Thanks,
Gabriele

Re: [PATCH 2/2] rseq/selftests: Add test for mm_cid compaction

[Gabriele Monaco]

On Tue, 2025-02-18 at 09:13 +0100, Gabriele Monaco wrote:
> 
> However, I'm still not particularly fond of running stuff there at
> all.
> If a periodic task needs to run now, it preempts everything else and
> should be on its way as soon as possible. A task work is always going
> to delay this, although by a tiny bit.
> 
> Again, for now I cannot think of a better way without bringing
> workqueues into the picture, and in this specific case we have a
> valid
> workaround to reduce the latency.
> 

Been thinking about this for a while, what about getting the best from
both worlds?
MMs already have a dependency on workqueues (async_put_work) they
simply don't wildly schedule them like I was doing, essentially, the
whole periodic delayed_work thing was the issue.
Substituting what is currently a task_work with a plain work_struct (on
the mm) doesn't look too bad to me.

We still keep the mechanism to trigger and regulate its frequency and,
instead of doing it from a tick, we do it from
__rseq_handle_notify_resume.
This way we won't have it scheduled for sleeping, never running or
whatever exotic threads (which was a potential issue with the
delayed_work) but we also keep it in a preemptible context with
frequency comparable to the task_work.

Running it in a work_struct would probably make the batch scan
superfluous, since we are talking about some 30us which can run
perfectly fine in a kworker.

What do you think?

Thanks,
Gabriele