introduce sys_membarrier(): process-wide memory barrier

Here is an implementation of a new system call, sys_membarrier(), which executes a memory barrier on all threads of the current process.

It aims at greatly simplifying and enhancing the current signal-based liburcu userspace RCU synchronize_rcu() implementation. (found at http://lttng.org/urcu)

Both the signal-based and the sys_membarrier userspace RCU schemes permit us to remove the memory barrier from the userspace RCU rcu_read_lock() and rcu_read_unlock() primitives, thus significantly accelerating them. These memory barriers are replaced by compiler barriers on the read-side, and all matching memory barriers on the write-side are turned into an invokation of a memory barrier on all active threads in the process. By letting the kernel perform this synchronization rather than dumbly sending a signal to every process threads (as we currently do), we diminish the number of unnecessary wake ups and only issue the memory barriers on active threads. Non-running threads do not need to execute such barrier anyway, because these are implied by the scheduler context switches.

To explain the benefit of this scheme, let's introduce two example threads:

Thread A (non-frequent, e.g. executing liburcu synchronize_rcu()) Thread B (frequent, e.g. executing liburcu rcu_read_lock()/rcu_read_unlock())

In a scheme where all smp_mb() in thread A synchronize_rcu() are ordering memory accesses with respect to smp_mb() present in rcu_read_lock/unlock(), we can change all smp_mb() from synchronize_rcu() into calls to sys_membarrier() and all smp_mb() from rcu_read_lock/unlock() into compiler barriers "barrier()".

Before the change, we had, for each smp_mb() pairs:

Thread A                    Thread B
prev mem accesses           prev mem accesses
smp_mb()                    smp_mb()
follow mem accesses         follow mem accesses

After the change, these pairs become:

Thread A                    Thread B
prev mem accesses           prev mem accesses
sys_membarrier()            barrier()
follow mem accesses         follow mem accesses

As we can see, there are two possible scenarios: either Thread B memory accesses do not happen concurrently with Thread A accesses (1), or they do (2).

1) Non-concurrent Thread A vs Thread B accesses:

Thread A Thread B
prev mem accesses
sys_membarrier()
follow mem accesses
prev mem accesses
barrier()
follow mem accesses

In this case, thread B accesses will be weakly ordered. This is OK, because at that point, thread A is not particularly interested in ordering them with respect to its own accesses.

2) Concurrent Thread A vs Thread B accesses

Thread A                    Thread B
prev mem accesses           prev mem accesses
sys_membarrier()            barrier()
follow mem accesses         follow mem accesses

In this case, thread B accesses, which are ensured to be in program order thanks to the compiler barrier, will be "upgraded" to full smp_mb() thanks to the IPIs executing memory barriers on each active system threads. Each non-running process threads are intrinsically serialized by the scheduler.

The current implementation simply executes a memory barrier in an IPI handler on each active cpu. Going through the hassle of taking run queue locks and checking if the thread running on each online CPU belongs to the current thread seems more heavyweight than the cost of the IPI itself (not measured though).

The system call number is only assigned for x86_64 in this RFC patch.

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

CC "Paul E. McKenney" <[email protected]>

CC [email protected]

CC [email protected]

CC [email protected]

CC [email protected]

CC [email protected]

CC [email protected]

CC [email protected]

CC [email protected]

CC [email protected]

CC [email protected]

CC [email protected]

CC [email protected]

---
 arch/x86/include/asm/unistd_64.h |    2 ++
 kernel/sched.c                   |   30 ++++++++++++++++++++++++++++++
 2 files changed, 32 insertions(+)

Index: linux-2.6-lttng/arch/x86/include/asm/unistd_64.h
===================================================================

arch/x86/include/asm/unistd_64.h +2 -0

@@ -661,6 +661,8 @@ __SYSCALL(__NR_pwritev, sys_pwritev)
 __SYSCALL(__NR_rt_tgsigqueueinfo, sys_rt_tgsigqueueinfo)
 #define __NR_perf_event_open			298
 __SYSCALL(__NR_perf_event_open, sys_perf_event_open)
+#define __NR_membarrier				299
+__SYSCALL(__NR_membarrier, sys_membarrier)
 
 #ifndef __NO_STUBS
 #define __ARCH_WANT_OLD_READDIR

Index: linux-2.6-lttng/kernel/sched.c
===================================================================

kernel/sched.c +30 -0

@@ -10822,6 +10822,36 @@ struct cgroup_subsys cpuacct_subsys = {
 };
 #endif	/* CONFIG_CGROUP_CPUACCT */
 
+/*
+ * Execute a memory barrier on all CPUs on SMP systems.
+ * Do not rely on implicit barriers in smp_call_function(), just in case they
+ * are ever relaxed in the future.
+ */
+static void membarrier_ipi(void *unused)
+{
+	smp_mb();
+}
+
+/*
+ * sys_membarrier - issue memory barrier on current process running threads
+ *
+ * Execute a memory barrier on all running threads of the current process.
+ * Upon completion, the caller thread is ensured that all process threads
+ * have passed through a state where memory accesses match program order.
+ * (non-running threads are de facto in such a state)
+ *
+ * The current implementation simply executes a memory barrier in an IPI handler
+ * on each active cpu. Going through the hassle of taking run queue locks and
+ * checking if the thread running on each online CPU belongs to the current
+ * thread seems more heavyweight than the cost of the IPI itself.
+ */
+SYSCALL_DEFINE0(membarrier)
+{
+	on_each_cpu(membarrier_ipi, NULL, 1);
+
+	return 0;
+}
+
 #ifndef CONFIG_SMP
 
 int rcu_expedited_torture_stats(char *page)

Signature · 3 lines

-- 
Mathieu Desnoyers
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68

Quoted 82 lines · Mathieu Desnoyers

Here is an implementation of a new system call, sys_membarrier(), which executes a memory barrier on all threads of the current process.

It aims at greatly simplifying and enhancing the current signal-based liburcu userspace RCU synchronize_rcu() implementation. (found at http://lttng.org/urcu)

Both the signal-based and the sys_membarrier userspace RCU schemes permit us to remove the memory barrier from the userspace RCU rcu_read_lock() and rcu_read_unlock() primitives, thus significantly accelerating them. These memory barriers are replaced by compiler barriers on the read-side, and all matching memory barriers on the write-side are turned into an invokation of a memory barrier on all active threads in the process. By letting the kernel perform this synchronization rather than dumbly sending a signal to every process threads (as we currently do), we diminish the number of unnecessary wake ups and only issue the memory barriers on active threads. Non-running threads do not need to execute such barrier anyway, because these are implied by the scheduler context switches.

To explain the benefit of this scheme, let's introduce two example threads:

Thread A (non-frequent, e.g. executing liburcu synchronize_rcu()) Thread B (frequent, e.g. executing liburcu rcu_read_lock()/rcu_read_unlock())

In a scheme where all smp_mb() in thread A synchronize_rcu() are ordering memory accesses with respect to smp_mb() present in rcu_read_lock/unlock(), we can change all smp_mb() from synchronize_rcu() into calls to sys_membarrier() and all smp_mb() from rcu_read_lock/unlock() into compiler barriers "barrier()".

Before the change, we had, for each smp_mb() pairs:

Thread A                    Thread B
prev mem accesses           prev mem accesses
smp_mb()                    smp_mb()
follow mem accesses         follow mem accesses

After the change, these pairs become:

Thread A                    Thread B
prev mem accesses           prev mem accesses
sys_membarrier()            barrier()
follow mem accesses         follow mem accesses

As we can see, there are two possible scenarios: either Thread B memory accesses do not happen concurrently with Thread A accesses (1), or they do (2).

1) Non-concurrent Thread A vs Thread B accesses:

Thread A Thread B
prev mem accesses
sys_membarrier()
follow mem accesses
prev mem accesses
barrier()
follow mem accesses

In this case, thread B accesses will be weakly ordered. This is OK, because at that point, thread A is not particularly interested in ordering them with respect to its own accesses.

2) Concurrent Thread A vs Thread B accesses

Thread A                    Thread B
prev mem accesses           prev mem accesses
sys_membarrier()            barrier()
follow mem accesses         follow mem accesses

In this case, thread B accesses, which are ensured to be in program order thanks to the compiler barrier, will be "upgraded" to full smp_mb() thanks to the IPIs executing memory barriers on each active system threads. Each non-running process threads are intrinsically serialized by the scheduler.

The current implementation simply executes a memory barrier in an IPI handler on each active cpu. Going through the hassle of taking run queue locks and checking if the thread running on each online CPU belongs to the current thread seems more heavyweight than the cost of the IPI itself (not measured though).

Quoted 1 line

The system call number is only assigned for x86_64 in this RFC patch.

Beats the heck out of user-mode signal handlers!!! And it is hard to imagine groveling through runqueues ever being a win, even on very large systems. The only reasonable optimization I can imagine is to turn this into a no-op for a single-threaded process, but there are other ways to do that optimization.

Reviewed-by "Paul E. McKenney" <[email protected]>

Quoted 77 lines

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

CC "Paul E. McKenney" <[email protected]>

CC [email protected]

CC [email protected]

CC [email protected]

CC [email protected]

CC [email protected]

CC [email protected]

CC [email protected]

CC [email protected]

CC [email protected]

CC [email protected]

CC [email protected]

CC [email protected]

---
 arch/x86/include/asm/unistd_64.h |    2 ++
 kernel/sched.c                   |   30 ++++++++++++++++++++++++++++++
 2 files changed, 32 insertions(+)

Index: linux-2.6-lttng/arch/x86/include/asm/unistd_64.h
===================================================================

arch/x86/include/asm/unistd_64.h +2 -0

@@ -661,6 +661,8 @@ __SYSCALL(__NR_pwritev, sys_pwritev)
 __SYSCALL(__NR_rt_tgsigqueueinfo, sys_rt_tgsigqueueinfo)
 #define __NR_perf_event_open			298
 __SYSCALL(__NR_perf_event_open, sys_perf_event_open)
+#define __NR_membarrier				299
+__SYSCALL(__NR_membarrier, sys_membarrier)
 
 #ifndef __NO_STUBS
 #define __ARCH_WANT_OLD_READDIR

Index: linux-2.6-lttng/kernel/sched.c
===================================================================

kernel/sched.c +30 -0

@@ -10822,6 +10822,36 @@ struct cgroup_subsys cpuacct_subsys = {
 };
 #endif	/* CONFIG_CGROUP_CPUACCT */
 
+/*
+ * Execute a memory barrier on all CPUs on SMP systems.
+ * Do not rely on implicit barriers in smp_call_function(), just in case they
+ * are ever relaxed in the future.
+ */
+static void membarrier_ipi(void *unused)
+{
+	smp_mb();
+}
+
+/*
+ * sys_membarrier - issue memory barrier on current process running threads
+ *
+ * Execute a memory barrier on all running threads of the current process.
+ * Upon completion, the caller thread is ensured that all process threads
+ * have passed through a state where memory accesses match program order.
+ * (non-running threads are de facto in such a state)
+ *
+ * The current implementation simply executes a memory barrier in an IPI handler
+ * on each active cpu. Going through the hassle of taking run queue locks and
+ * checking if the thread running on each online CPU belongs to the current
+ * thread seems more heavyweight than the cost of the IPI itself.
+ */
+SYSCALL_DEFINE0(membarrier)
+{
+	on_each_cpu(membarrier_ipi, NULL, 1);
+
+	return 0;
+}
+
 #ifndef CONFIG_SMP
 
 int rcu_expedited_torture_stats(char *page)

Signature · 3 lines

-- 
Mathieu Desnoyers
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68

Here is an implementation of a new system call, sys_membarrier(), which executes a memory barrier on all threads of the current process.

It aims at greatly simplifying and enhancing the current signal-based liburcu userspace RCU synchronize_rcu() implementation. (found at http://lttng.org/urcu)

Both the signal-based and the sys_membarrier userspace RCU schemes permit us to remove the memory barrier from the userspace RCU rcu_read_lock() and rcu_read_unlock() primitives, thus significantly accelerating them. These memory barriers are replaced by compiler barriers on the read-side, and all matching memory barriers on the write-side are turned into an invokation of a memory barrier on all active threads in the process. By letting the kernel perform this synchronization rather than dumbly sending a signal to every process threads (as we currently do), we diminish the number of unnecessary wake ups and only issue the memory barriers on active threads. Non-running threads do not need to execute such barrier anyway, because these are implied by the scheduler context switches.

To explain the benefit of this scheme, let's introduce two example threads:

Thread A (non-frequent, e.g. executing liburcu synchronize_rcu()) Thread B (frequent, e.g. executing liburcu rcu_read_lock()/rcu_read_unlock())

In a scheme where all smp_mb() in thread A synchronize_rcu() are ordering memory accesses with respect to smp_mb() present in rcu_read_lock/unlock(), we can change all smp_mb() from synchronize_rcu() into calls to sys_membarrier() and all smp_mb() from rcu_read_lock/unlock() into compiler barriers "barrier()".

Before the change, we had, for each smp_mb() pairs:

Thread A                    Thread B
prev mem accesses           prev mem accesses
smp_mb()                    smp_mb()
follow mem accesses         follow mem accesses

After the change, these pairs become:

Thread A                    Thread B
prev mem accesses           prev mem accesses
sys_membarrier()            barrier()
follow mem accesses         follow mem accesses

As we can see, there are two possible scenarios: either Thread B memory accesses do not happen concurrently with Thread A accesses (1), or they do (2).

1) Non-concurrent Thread A vs Thread B accesses:

Thread A Thread B
prev mem accesses
sys_membarrier()
follow mem accesses
prev mem accesses
barrier()
follow mem accesses

In this case, thread B accesses will be weakly ordered. This is OK, because at that point, thread A is not particularly interested in ordering them with respect to its own accesses.

2) Concurrent Thread A vs Thread B accesses

Thread A                    Thread B
prev mem accesses           prev mem accesses
sys_membarrier()            barrier()
follow mem accesses         follow mem accesses

In this case, thread B accesses, which are ensured to be in program order thanks to the compiler barrier, will be "upgraded" to full smp_mb() thanks to the IPIs executing memory barriers on each active system threads. Each non-running process threads are intrinsically serialized by the scheduler.

The current implementation simply executes a memory barrier in an IPI handler on each active cpu. Going through the hassle of taking run queue locks and checking if the thread running on each online CPU belongs to the current thread seems more heavyweight than the cost of the IPI itself (not measured though).

The system call number is only assigned for x86_64 in this RFC patch.

Quoted 19 lines · Mathieu Desnoyers

Here is an implementation of a new system call, sys_membarrier(), which executes a memory barrier on all threads of the current process.

It aims at greatly simplifying and enhancing the current signal-based liburcu userspace RCU synchronize_rcu() implementation. (found at http://lttng.org/urcu)

Both the signal-based and the sys_membarrier userspace RCU schemes permit us to remove the memory barrier from the userspace RCU rcu_read_lock() and rcu_read_unlock() primitives, thus significantly accelerating them. These memory barriers are replaced by compiler barriers on the read-side, and all matching memory barriers on the write-side are turned into an invokation of a memory barrier on all active threads in the process. By letting the kernel perform this synchronization rather than dumbly sending a signal to every process threads (as we currently do), we diminish the number of unnecessary wake ups and only issue the memory barriers on active threads. Non-running threads do not need to execute such barrier anyway, because these are implied by the scheduler context switches.

[...]

Quoted 32 lines

The current implementation simply executes a memory barrier in an IPI handler on each active cpu. Going through the hassle of taking run queue locks and checking if the thread running on each online CPU belongs to the current thread seems more heavyweight than the cost of the IPI itself (not measured though).

kernel/sched.c +20 -0

@@ -10822,6 +10822,36 @@ struct cgroup_subsys cpuacct_subsys = {
 };
 #endif	/* CONFIG_CGROUP_CPUACCT */
 
+/*
+ * Execute a memory barrier on all CPUs on SMP systems.
+ * Do not rely on implicit barriers in smp_call_function(), just in case they
+ * are ever relaxed in the future.
+ */
+static void membarrier_ipi(void *unused)
+{
+	smp_mb();
+}
+
+/*
+ * sys_membarrier - issue memory barrier on current process running threads
+ *
+ * Execute a memory barrier on all running threads of the current process.
+ * Upon completion, the caller thread is ensured that all process threads
+ * have passed through a state where memory accesses match program order.
+ * (non-running threads are de facto in such a state)
+ *
+ * The current implementation simply executes a memory barrier in an IPI handler
+ * on each active cpu. Going through the hassle of taking run queue locks and

kernel/sched.c struct cgroup_subsys cpuacct_subsys = { · line 10854

Quoted 10 lines

kernel/sched.c +10 -0

+ * checking if the thread running on each online CPU belongs to the current
+ * thread seems more heavyweight than the cost of the IPI itself.
+ */
+SYSCALL_DEFINE0(membarrier)
+{
+	on_each_cpu(membarrier_ipi, NULL, 1);
+
+	return 0;
+}
+

Nice idea. A few things come immediately to mind:

- If !CONFIG_SMP, this syscall should become (more of) a no-op. Ideally even if CONFIG_SMP but running with one CPU. (If you really wanted to go nuts, you could make it a vsyscall that did nothing with 1 CPU, to avoid the syscall overhead, but that seems like entirely too much trouble.)

- Have you tested what happens if a process does "while(1) membarrier();"? By running on every CPU, including those not owned by the current process, this has the potential to make DoS easier, particularly on systems with many CPUs. That gets even worse if a process forks multiple threads running that same loop. Also consider that executing an IPI will do work even on a CPU currently running a real-time task.

- Rather than groveling through runqueues, could you somehow remotely check the value of current? In theory, a race in doing so wouldn't matter; finding something other than the current process should mean you don't need to do a barrier, and finding the current process means you might need to do a barrier.

- Part of me thinks this ought to become slightly more general, and just deliver a signal that the receiving thread could handle as it likes. However, that would certainly prove more expensive than this, and I don't know that the generality would buy anything.

- Could you somehow register reader threads with the kernel, in a way that makes them easy to detect remotely?

- Josh Triplett

Here is an implementation of a new system call, sys_membarrier(), which executes a memory barrier on all threads of the current process.

It aims at greatly simplifying and enhancing the current signal-based liburcu userspace RCU synchronize_rcu() implementation. (found at http://lttng.org/urcu)

Both the signal-based and the sys_membarrier userspace RCU schemes permit us to remove the memory barrier from the userspace RCU rcu_read_lock() and rcu_read_unlock() primitives, thus significantly accelerating them. These memory barriers are replaced by compiler barriers on the read-side, and all matching memory barriers on the write-side are turned into an invokation of a memory barrier on all active threads in the process. By letting the kernel perform this synchronization rather than dumbly sending a signal to every process threads (as we currently do), we diminish the number of unnecessary wake ups and only issue the memory barriers on active threads. Non-running threads do not need to execute such barrier anyway, because these are implied by the scheduler context switches.

The current implementation simply executes a memory barrier in an IPI handler on each active cpu. Going through the hassle of taking run queue locks and checking if the thread running on each online CPU belongs to the current thread seems more heavyweight than the cost of the IPI itself (not measured though).

kernel/sched.c +20 -0

@@ -10822,6 +10822,36 @@ struct cgroup_subsys cpuacct_subsys = {
 };
 #endif	/* CONFIG_CGROUP_CPUACCT */
 
+/*
+ * Execute a memory barrier on all CPUs on SMP systems.
+ * Do not rely on implicit barriers in smp_call_function(), just in case they
+ * are ever relaxed in the future.
+ */
+static void membarrier_ipi(void *unused)
+{
+	smp_mb();
+}
+
+/*
+ * sys_membarrier - issue memory barrier on current process running threads
+ *
+ * Execute a memory barrier on all running threads of the current process.
+ * Upon completion, the caller thread is ensured that all process threads
+ * have passed through a state where memory accesses match program order.
+ * (non-running threads are de facto in such a state)
+ *
+ * The current implementation simply executes a memory barrier in an IPI handler
+ * on each active cpu. Going through the hassle of taking run queue locks and

Quoted 7 lines · Mathieu Desnoyers

Here is an implementation of a new system call, sys_membarrier(), which executes a memory barrier on all threads of the current process.

It aims at greatly simplifying and enhancing the current signal-based liburcu userspace RCU synchronize_rcu() implementation. (found at http://lttng.org/urcu)

Nice.

Quoted 69 lines

Both the signal-based and the sys_membarrier userspace RCU schemes permit us to remove the memory barrier from the userspace RCU rcu_read_lock() and rcu_read_unlock() primitives, thus significantly accelerating them. These memory barriers are replaced by compiler barriers on the read-side, and all matching memory barriers on the write-side are turned into an invokation of a memory barrier on all active threads in the process. By letting the kernel perform this synchronization rather than dumbly sending a signal to every process threads (as we currently do), we diminish the number of unnecessary wake ups and only issue the memory barriers on active threads. Non-running threads do not need to execute such barrier anyway, because these are implied by the scheduler context switches.

To explain the benefit of this scheme, let's introduce two example threads:

Thread A (non-frequent, e.g. executing liburcu synchronize_rcu()) Thread B (frequent, e.g. executing liburcu rcu_read_lock()/rcu_read_unlock())

In a scheme where all smp_mb() in thread A synchronize_rcu() are ordering memory accesses with respect to smp_mb() present in rcu_read_lock/unlock(), we can change all smp_mb() from synchronize_rcu() into calls to sys_membarrier() and all smp_mb() from rcu_read_lock/unlock() into compiler barriers "barrier()".

Before the change, we had, for each smp_mb() pairs:

Thread A                    Thread B
prev mem accesses           prev mem accesses
smp_mb()                    smp_mb()
follow mem accesses         follow mem accesses

After the change, these pairs become:

Thread A                    Thread B
prev mem accesses           prev mem accesses
sys_membarrier()            barrier()
follow mem accesses         follow mem accesses

As we can see, there are two possible scenarios: either Thread B memory accesses do not happen concurrently with Thread A accesses (1), or they do (2).

1) Non-concurrent Thread A vs Thread B accesses:

Thread A Thread B
prev mem accesses
sys_membarrier()
follow mem accesses
prev mem accesses
barrier()
follow mem accesses

In this case, thread B accesses will be weakly ordered. This is OK, because at that point, thread A is not particularly interested in ordering them with respect to its own accesses.

2) Concurrent Thread A vs Thread B accesses

Thread A                    Thread B
prev mem accesses           prev mem accesses
sys_membarrier()            barrier()
follow mem accesses         follow mem accesses

In this case, thread B accesses, which are ensured to be in program order thanks to the compiler barrier, will be "upgraded" to full smp_mb() thanks to the IPIs executing memory barriers on each active system threads. Each non-running process threads are intrinsically serialized by the scheduler.

Quoted 6 lines

The current implementation simply executes a memory barrier in an IPI handler on each active cpu. Going through the hassle of taking run queue locks and checking if the thread running on each online CPU belongs to the current thread seems more heavyweight than the cost of the IPI itself (not measured though).

I don't think you need to grab any locks. Doing an rcu_read_lock() should prevent tasks from disappearing (since destruction of tasks use RCU). You may still need to grab the tasklist_lock under read_lock().

So what you could do, is find each task that is a thread of the calling task, and then just check task_rq(task)->curr != task. Just send the IPI's to those tasks that pass the test.

If the task->rq changes, or the task->rq->curr changes, and makes the condition fail (or even pass), the events that cause those changes are probably good enough than needing to call smp_mb();

-- Steve

Quoted 1 line

The system call number is only assigned for x86_64 in this RFC patch.

Quoted 66 lines · * Josh Triplett ([email protected]) wrote:

Quoted 19 lines · Mathieu Desnoyers

Here is an implementation of a new system call, sys_membarrier(), which executes a memory barrier on all threads of the current process.

It aims at greatly simplifying and enhancing the current signal-based liburcu userspace RCU synchronize_rcu() implementation. (found at http://lttng.org/urcu)

Both the signal-based and the sys_membarrier userspace RCU schemes permit us to remove the memory barrier from the userspace RCU rcu_read_lock() and rcu_read_unlock() primitives, thus significantly accelerating them. These memory barriers are replaced by compiler barriers on the read-side, and all matching memory barriers on the write-side are turned into an invokation of a memory barrier on all active threads in the process. By letting the kernel perform this synchronization rather than dumbly sending a signal to every process threads (as we currently do), we diminish the number of unnecessary wake ups and only issue the memory barriers on active threads. Non-running threads do not need to execute such barrier anyway, because these are implied by the scheduler context switches.

[...]

Quoted 32 lines

The current implementation simply executes a memory barrier in an IPI handler on each active cpu. Going through the hassle of taking run queue locks and checking if the thread running on each online CPU belongs to the current thread seems more heavyweight than the cost of the IPI itself (not measured though).

kernel/sched.c +20 -0

@@ -10822,6 +10822,36 @@ struct cgroup_subsys cpuacct_subsys = {
 };
 #endif	/* CONFIG_CGROUP_CPUACCT */
 
+/*
+ * Execute a memory barrier on all CPUs on SMP systems.
+ * Do not rely on implicit barriers in smp_call_function(), just in case they
+ * are ever relaxed in the future.
+ */
+static void membarrier_ipi(void *unused)
+{
+	smp_mb();
+}
+
+/*
+ * sys_membarrier - issue memory barrier on current process running threads
+ *
+ * Execute a memory barrier on all running threads of the current process.
+ * Upon completion, the caller thread is ensured that all process threads
+ * have passed through a state where memory accesses match program order.
+ * (non-running threads are de facto in such a state)
+ *
+ * The current implementation simply executes a memory barrier in an IPI handler
+ * on each active cpu. Going through the hassle of taking run queue locks and

kernel/sched.c struct cgroup_subsys cpuacct_subsys = { · line 10854

Quoted 10 lines

kernel/sched.c +10 -0

+ * checking if the thread running on each online CPU belongs to the current
+ * thread seems more heavyweight than the cost of the IPI itself.
+ */
+SYSCALL_DEFINE0(membarrier)
+{
+	on_each_cpu(membarrier_ipi, NULL, 1);
+
+	return 0;
+}
+

Nice idea. A few things come immediately to mind:

Quoted 6 lines

- If !CONFIG_SMP, this syscall should become (more of) a no-op. Ideally even if CONFIG_SMP but running with one CPU. (If you really wanted to go nuts, you could make it a vsyscall that did nothing with 1 CPU, to avoid the syscall overhead, but that seems like entirely too much trouble.)

Sure, will do.

Quoted 7 lines

- Have you tested what happens if a process does "while(1) membarrier();"? By running on every CPU, including those not owned by the current process, this has the potential to make DoS easier, particularly on systems with many CPUs. That gets even worse if a process forks multiple threads running that same loop. Also consider that executing an IPI will do work even on a CPU currently running a real-time task.

Just tried it with a 10,000,000 iterations loop.

The thread doing the system call loop takes 2.0% of user time, 98% of system time. All other cpus are nearly 100.0% idle. Just to give a bit more info about my test setup, I also have a thread sitting on a CPU busy-waiting for the loop to complete. This thread takes 97.7% user time (but it really is just there to make sure we are indeed doing the IPIs, not skipping it through the thread_group_empty(current) test). If I remove this thread, the execution time of the test program shrinks from 32 seconds down to 1.9 seconds. So yes, the IPI is actually executed in the first place, because removing the extra thread accelerates the loop tremendously. I used a 8-core Xeon to test.

Quoted 5 lines

- Rather than groveling through runqueues, could you somehow remotely check the value of current? In theory, a race in doing so wouldn't matter; finding something other than the current process should mean you don't need to do a barrier, and finding the current process means you might need to do a barrier.

Well, the thing is that sending an IPI to all processors can be done very efficiently on a lot of architectures because it uses an IPI broadcast. If we have to select a few processors to which we send the signal individually, I fear that the solution will scale poorly on systems where cpus are densely used by threads belonging to the current process.

So if we go down the route of sending an IPI broadcast as I did, then the performance improvement of skipping the smp_mb() for some CPU seems insignificant compared to the IPI. In addition, it would require to add some preparation code and exchange cache-lines (containing the process ID), which would actually slow down the non-parallel portion of the system call (to accelerate the parallelizable portion on only some of the CPUs).

Quoted 4 lines

- Part of me thinks this ought to become slightly more general, and just deliver a signal that the receiving thread could handle as it likes. However, that would certainly prove more expensive than this, and I don't know that the generality would buy anything.

A general scheme would have to call every threads, even those which are not running. In the case of this system call, this is a particular case where we can forget about non-running threads, because the memory barrier is implied by the scheduler activity that brought them offline. So I really don't see how we can use this IPI scheme for other things that this kind of synchronization.

Quoted 2 lines

- Could you somehow register reader threads with the kernel, in a way that makes them easy to detect remotely?

There are two ways I figure out we could do this. One would imply adding extra shared data between kernel and userspace (which I'd like to avoid, to keep coupling low). The other alternative would be to add per task_struct information about this, and new system calls. The added per task_struct information would use up cache lines (which are very important, especially in the task_struct) and the added system call at rcu_read_lock/unlock() would simply kill performance.

Quoted 88 lines · * Steven Rostedt ([email protected]) wrote:

Quoted 7 lines · Mathieu Desnoyers

Here is an implementation of a new system call, sys_membarrier(), which executes a memory barrier on all threads of the current process.

It aims at greatly simplifying and enhancing the current signal-based liburcu userspace RCU synchronize_rcu() implementation. (found at http://lttng.org/urcu)

Nice.

Quoted 69 lines

Both the signal-based and the sys_membarrier userspace RCU schemes permit us to remove the memory barrier from the userspace RCU rcu_read_lock() and rcu_read_unlock() primitives, thus significantly accelerating them. These memory barriers are replaced by compiler barriers on the read-side, and all matching memory barriers on the write-side are turned into an invokation of a memory barrier on all active threads in the process. By letting the kernel perform this synchronization rather than dumbly sending a signal to every process threads (as we currently do), we diminish the number of unnecessary wake ups and only issue the memory barriers on active threads. Non-running threads do not need to execute such barrier anyway, because these are implied by the scheduler context switches.

To explain the benefit of this scheme, let's introduce two example threads:

Thread A (non-frequent, e.g. executing liburcu synchronize_rcu()) Thread B (frequent, e.g. executing liburcu rcu_read_lock()/rcu_read_unlock())

In a scheme where all smp_mb() in thread A synchronize_rcu() are ordering memory accesses with respect to smp_mb() present in rcu_read_lock/unlock(), we can change all smp_mb() from synchronize_rcu() into calls to sys_membarrier() and all smp_mb() from rcu_read_lock/unlock() into compiler barriers "barrier()".

Before the change, we had, for each smp_mb() pairs:

Thread A                    Thread B
prev mem accesses           prev mem accesses
smp_mb()                    smp_mb()
follow mem accesses         follow mem accesses

After the change, these pairs become:

Thread A                    Thread B
prev mem accesses           prev mem accesses
sys_membarrier()            barrier()
follow mem accesses         follow mem accesses

As we can see, there are two possible scenarios: either Thread B memory accesses do not happen concurrently with Thread A accesses (1), or they do (2).

1) Non-concurrent Thread A vs Thread B accesses:

Thread A Thread B
prev mem accesses
sys_membarrier()
follow mem accesses
prev mem accesses
barrier()
follow mem accesses

In this case, thread B accesses will be weakly ordered. This is OK, because at that point, thread A is not particularly interested in ordering them with respect to its own accesses.

2) Concurrent Thread A vs Thread B accesses

Thread A                    Thread B
prev mem accesses           prev mem accesses
sys_membarrier()            barrier()
follow mem accesses         follow mem accesses

In this case, thread B accesses, which are ensured to be in program order thanks to the compiler barrier, will be "upgraded" to full smp_mb() thanks to the IPIs executing memory barriers on each active system threads. Each non-running process threads are intrinsically serialized by the scheduler.

Quoted 6 lines

The current implementation simply executes a memory barrier in an IPI handler on each active cpu. Going through the hassle of taking run queue locks and checking if the thread running on each online CPU belongs to the current thread seems more heavyweight than the cost of the IPI itself (not measured though).

Quoted 7 lines

I don't think you need to grab any locks. Doing an rcu_read_lock() should prevent tasks from disappearing (since destruction of tasks use RCU). You may still need to grab the tasklist_lock under read_lock().

So what you could do, is find each task that is a thread of the calling task, and then just check task_rq(task)->curr != task. Just send the IPI's to those tasks that pass the test.

I guess you mean

"then just check task_rq(task)->curr == task" ... ?

Quoted 4 lines

If the task->rq changes, or the task->rq->curr changes, and makes the condition fail (or even pass), the events that cause those changes are probably good enough than needing to call smp_mb();

I see your point.

This would probably be good for machines with very large number of cpus and without IPI broadcast support, running processes with only few threads.

I really start to think that we should have some way to compare the number of threads belonging to a process and choose between the broadcast IPI and the per-cpu IPI depending if we are over or under an arbitrary threshold.

Index: linux-2.6-lttng/kernel/sched.c
===================================================================

kernel/sched.c +23 -0

@@ -10822,6 +10822,36 @@ struct cgroup_subsys cpuacct_subsys = {
 };
 #endif	/* CONFIG_CGROUP_CPUACCT */
 
+/*
+ * Execute a memory barrier on all CPUs on SMP systems.
+ * Do not rely on implicit barriers in smp_call_function(), just in case they
+ * are ever relaxed in the future.
+ */
+static void membarrier_ipi(void *unused)
+{
+	smp_mb();
+}
+
+/*
+ * sys_membarrier - issue memory barrier on current process running threads
+ *
+ * Execute a memory barrier on all running threads of the current process.
+ * Upon completion, the caller thread is ensured that all process threads
+ * have passed through a state where memory accesses match program order.
+ * (non-running threads are de facto in such a state)
+ *
+ * The current implementation simply executes a memory barrier in an IPI handler
+ * on each active cpu. Going through the hassle of taking run queue locks and
+ * checking if the thread running on each online CPU belongs to the current
+ * thread seems more heavyweight than the cost of the IPI itself.
+ */

Beats the heck out of user-mode signal handlers!!! And it is hard to imagine groveling through runqueues ever being a win, even on very large systems. The only reasonable optimization I can imagine is to turn this into a no-op for a single-threaded process, but there are other ways to do that optimization.

Reviewed-by "Paul E. McKenney" <[email protected]>

The number of threads doesn't matter nearly as much as the number of threads typically running at a time compared to the number of processors. Of course, we can't measure that as easily, but I don't know that your proposed heuristic would approximate it well.

Both the signal-based and the sys_membarrier userspace RCU schemes permit us to remove the memory barrier from the userspace RCU rcu_read_lock() and rcu_read_unlock() primitives, thus significantly accelerating them. These memory barriers are replaced by compiler

barriers on the read-side, and all matching memory barriers on the write-side are turned into an invokation of a memory barrier on all active threads in the process. By letting the kernel perform this synchronization rather than dumbly sending a signal to every process threads (as we currently do), we diminish the number of unnecessary wake ups and only issue the memory barriers on active threads. Non-running threads do not need to execute such barrier anyway, because these are implied by the scheduler context switches.

The current implementation simply executes a memory barrier in an IPI handler on each active cpu. Going through the hassle of taking run queue locks and checking if the thread running on each online CPU belongs to the current thread seems more heavyweight than the cost of the IPI itself (not measured though).

A simple:

  for_each_cpu(cpu, current->mm->cpu_vm_mask) {
     if (cpu_curr(cpu)->mm == current->mm)
        smp_call_function_single(cpu, func, NULL, 1);
  }

I see your point.

This would probably be good for machines with very large number of cpus and without IPI broadcast support, running processes with only few threads. I really start to think that we should have some way to compare the number of threads belonging to a process and choose between the broadcast IPI and the per-cpu IPI depending if we are over or under an arbitrary threshold.

Quoted 5 lines · Josh Triplett

The number of threads doesn't matter nearly as much as the number of threads typically running at a time compared to the number of processors. Of course, we can't measure that as easily, but I don't know that your proposed heuristic would approximate it well.

Quite agreed, and not disturbing RT tasks is even more important.

A simple:

  for_each_cpu(cpu, current->mm->cpu_vm_mask) {
     if (cpu_curr(cpu)->mm == current->mm)
        smp_call_function_single(cpu, func, NULL, 1);
  }

seems far preferable over anything else, if you really want you can use a cpumask to copy cpu_vm_mask in and unset bits and use the mask with smp_call_function_any(), but that includes having to allocate the cpumask, which might or might not be too expensive for Mathieu.

Quoted 1 line · Mathieu Desnoyers

I see your point.

Actually you are missing the point ;-)

Quoted 7 lines

This would probably be good for machines with very large number of cpus and without IPI broadcast support, running processes with only few threads. I really start to think that we should have some way to compare the number of threads belonging to a process and choose between the broadcast IPI and the per-cpu IPI depending if we are over or under an arbitrary threshold.

This has nothing to do with performance. It has to do with a thread should not interfere with a thread belonging to another process. We really don't care how long the sys_membarrier() takes (it's the slow path anyway). We do care that a critical RT task is being interrupted by some java thread sending thousands of IPIs.

-- Steve

Quoted 4 lines · Mathieu Desnoyers

Both the signal-based and the sys_membarrier userspace RCU schemes permit us to remove the memory barrier from the userspace RCU rcu_read_lock() and rcu_read_unlock() primitives, thus significantly accelerating them. These memory barriers are replaced by compiler

Quoted 8 lines

barriers on the read-side, and all matching memory barriers on the write-side are turned into an invokation of a memory barrier on all active threads in the process. By letting the kernel perform this synchronization rather than dumbly sending a signal to every process threads (as we currently do), we diminish the number of unnecessary wake ups and only issue the memory barriers on active threads. Non-running threads do not need to execute such barrier anyway, because these are implied by the scheduler context switches.

I'm not sure all this effort is really needed on architectures with strong memory ordering.

kernel/sched.c struct cgroup_subsys cpuacct_subsys = { · line 10850

Quoted 9 lines

+ * The current implementation simply executes a memory barrier in an IPI handler
+ * on each active cpu. Going through the hassle of taking run queue locks and
+ * checking if the thread running on each online CPU belongs to the current
+ * thread seems more heavyweight than the cost of the IPI itself.
+ */

kernel/sched.c +3 -0

+SYSCALL_DEFINE0(membarrier)
+{
+	on_each_cpu(membarrier_ipi, NULL, 1);

Can't you use mm->cpu_vm_mask?

-Andi

Quoted 5 lines · Mathieu Desnoyers

The current implementation simply executes a memory barrier in an IPI handler on each active cpu. Going through the hassle of taking run queue locks and checking if the thread running on each online CPU belongs to the current thread seems more heavyweight than the cost of the IPI itself (not measured though).

There's another way to do this:

(1) For each threads you want to execute a memory barrier, mark in its task_struct that you want it to do a memory barrier and set TIF_NOTIFY_RESUME.

(2) Interrupt all CPUs. The interrupt handler doesn't have to do anything.

(3) When any of the threads marked in (1) gain CPU time, do_notify_resume() will be executed, and the do-memory-barrier flag can be tested and if it was set, the flag can be cleared and a memory barrier can be interpolated.

The current thread will also pass through stage (3) on its way out, if it's marked in stage (1).

David

Quoted 7 lines · Paul E. McKenney

Beats the heck out of user-mode signal handlers!!! And it is hard to imagine groveling through runqueues ever being a win, even on very large systems. The only reasonable optimization I can imagine is to turn this into a no-op for a single-threaded process, but there are other ways to do that optimization.

Quoted 1 line

Reviewed-by "Paul E. McKenney" <[email protected]>

Then imagine someone doing:

while (1)
sys_membarrier();

on your multi node machine, see how happy you are then.

Quoted 1 line · * Josh Triplett ([email protected]) wrote:

On Wed, Jan 06, 2010 at 11:40:07PM -0500, Mathieu Desnoyers wrote:

Quoted 7 lines

- Have you tested what happens if a process does "while(1) membarrier();"? By running on every CPU, including those not owned by the current process, this has the potential to make DoS easier, particularly on systems with many CPUs. That gets even worse if a process forks multiple threads running that same loop. Also consider that executing an IPI will do work even on a CPU currently running a real-time task.

Just tried it with a 10,000,000 iterations loop.

The thread doing the system call loop takes 2.0% of user time, 98% of system time. All other cpus are nearly 100.0% idle. Just to give a bit more info about my test setup, I also have a thread sitting on a CPU busy-waiting for the loop to complete. This thread takes 97.7% user time (but it really is just there to make sure we are indeed doing the IPIs, not skipping it through the thread_group_empty(current) test). If I remove this thread, the execution time of the test program shrinks from 32 seconds down to 1.9 seconds. So yes, the IPI is actually executed in the first place, because removing the extra thread accelerates the loop tremendously. I used a 8-core Xeon to test.

Quoted 5 lines

- Rather than groveling through runqueues, could you somehow remotely check the value of current? In theory, a race in doing so wouldn't matter; finding something other than the current process should mean you don't need to do a barrier, and finding the current process means you might need to do a barrier.

Well, the thing is that sending an IPI to all processors can be done very efficiently on a lot of architectures because it uses an IPI broadcast. If we have to select a few processors to which we send the signal individually, I fear that the solution will scale poorly on systems where cpus are densely used by threads belonging to the current process.

So if we go down the route of sending an IPI broadcast as I did, then the performance improvement of skipping the smp_mb() for some CPU seems insignificant compared to the IPI. In addition, it would require to add some preparation code and exchange cache-lines (containing the process ID), which would actually slow down the non-parallel portion of the system call (to accelerate the parallelizable portion on only some of the CPUs).

So I don't think this would buy us anything. However, if we would have a per-process count of the number of threads in the thread group, then we could switch to a per-cpu IPI rather than broadcast if we detect that we have much fewer threads than CPUs.

Quoted 4 lines

- Part of me thinks this ought to become slightly more general, and just deliver a signal that the receiving thread could handle as it likes. However, that would certainly prove more expensive than this, and I don't know that the generality would buy anything.

A general scheme would have to call every threads, even those which are not running. In the case of this system call, this is a particular case where we can forget about non-running threads, because the memory barrier is implied by the scheduler activity that brought them offline. So I really don't see how we can use this IPI scheme for other things that this kind of synchronization.

Quoted 2 lines

- Could you somehow register reader threads with the kernel, in a way that makes them easy to detect remotely?

There are two ways I figure out we could do this. One would imply adding extra shared data between kernel and userspace (which I'd like to avoid, to keep coupling low). The other alternative would be to add per task_struct information about this, and new system calls. The added per task_struct information would use up cache lines (which are very important, especially in the task_struct) and the added system call at rcu_read_lock/unlock() would simply kill performance.

Thanks,

Mathieu

Quoted 3 lines

- Josh Triplett

Signature · 2 lines

Mathieu Desnoyers
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68

Or am I missing your point entirely ?

Quoted 7 lines · Mathieu Desnoyers

Here is an implementation of a new system call, sys_membarrier(), which executes a memory barrier on all threads of the current process.

It aims at greatly simplifying and enhancing the current signal-based liburcu userspace RCU synchronize_rcu() implementation. (found at http://lttng.org/urcu)

Nice.

Quoted 69 lines

Both the signal-based and the sys_membarrier userspace RCU schemes permit us to remove the memory barrier from the userspace RCU rcu_read_lock() and rcu_read_unlock() primitives, thus significantly accelerating them. These memory barriers are replaced by compiler barriers on the read-side, and all matching memory barriers on the write-side are turned into an invokation of a memory barrier on all active threads in the process. By letting the kernel perform this synchronization rather than dumbly sending a signal to every process threads (as we currently do), we diminish the number of unnecessary wake ups and only issue the memory barriers on active threads. Non-running threads do not need to execute such barrier anyway, because these are implied by the scheduler context switches.

To explain the benefit of this scheme, let's introduce two example threads:

Thread A (non-frequent, e.g. executing liburcu synchronize_rcu()) Thread B (frequent, e.g. executing liburcu rcu_read_lock()/rcu_read_unlock())

In a scheme where all smp_mb() in thread A synchronize_rcu() are ordering memory accesses with respect to smp_mb() present in rcu_read_lock/unlock(), we can change all smp_mb() from synchronize_rcu() into calls to sys_membarrier() and all smp_mb() from rcu_read_lock/unlock() into compiler barriers "barrier()".

Before the change, we had, for each smp_mb() pairs:

Thread A                    Thread B
prev mem accesses           prev mem accesses
smp_mb()                    smp_mb()
follow mem accesses         follow mem accesses

After the change, these pairs become:

Thread A                    Thread B
prev mem accesses           prev mem accesses
sys_membarrier()            barrier()
follow mem accesses         follow mem accesses

As we can see, there are two possible scenarios: either Thread B memory accesses do not happen concurrently with Thread A accesses (1), or they do (2).

1) Non-concurrent Thread A vs Thread B accesses:

Thread A Thread B
prev mem accesses
sys_membarrier()
follow mem accesses
prev mem accesses
barrier()
follow mem accesses

In this case, thread B accesses will be weakly ordered. This is OK, because at that point, thread A is not particularly interested in ordering them with respect to its own accesses.

2) Concurrent Thread A vs Thread B accesses

Thread A                    Thread B
prev mem accesses           prev mem accesses
sys_membarrier()            barrier()
follow mem accesses         follow mem accesses

In this case, thread B accesses, which are ensured to be in program order thanks to the compiler barrier, will be "upgraded" to full smp_mb() thanks to the IPIs executing memory barriers on each active system threads. Each non-running process threads are intrinsically serialized by the scheduler.

Quoted 6 lines

The current implementation simply executes a memory barrier in an IPI handler on each active cpu. Going through the hassle of taking run queue locks and checking if the thread running on each online CPU belongs to the current thread seems more heavyweight than the cost of the IPI itself (not measured though).

I don't think you need to grab any locks. Doing an rcu_read_lock() should prevent tasks from disappearing (since destruction of tasks use RCU). You may still need to grab the tasklist_lock under read_lock().

So what you could do, is find each task that is a thread of the calling task, and then just check task_rq(task)->curr != task. Just send the IPI's to those tasks that pass the test.

If the task->rq changes, or the task->rq->curr changes, and makes the condition fail (or even pass), the events that cause those changes are probably good enough than needing to call smp_mb();

Quoted 5 lines · Josh Triplett

The number of threads doesn't matter nearly as much as the number of threads typically running at a time compared to the number of processors. Of course, we can't measure that as easily, but I don't know that your proposed heuristic would approximate it well.

Quite agreed, and not disturbing RT tasks is even more important.

A simple:

  for_each_cpu(cpu, current->mm->cpu_vm_mask) {
     if (cpu_curr(cpu)->mm == current->mm)
        smp_call_function_single(cpu, func, NULL, 1);
  }

seems far preferable over anything else, if you really want you can use a cpumask to copy cpu_vm_mask in and unset bits and use the mask with smp_call_function_any(), but that includes having to allocate the cpumask, which might or might not be too expensive for Mathieu.

Quoted 4 lines · Mathieu Desnoyers

Both the signal-based and the sys_membarrier userspace RCU schemes permit us to remove the memory barrier from the userspace RCU rcu_read_lock() and rcu_read_unlock() primitives, thus significantly accelerating them. These memory barriers are replaced by compiler

Quoted 8 lines

barriers on the read-side, and all matching memory barriers on the write-side are turned into an invokation of a memory barrier on all active threads in the process. By letting the kernel perform this synchronization rather than dumbly sending a signal to every process threads (as we currently do), we diminish the number of unnecessary wake ups and only issue the memory barriers on active threads. Non-running threads do not need to execute such barrier anyway, because these are implied by the scheduler context switches.

I'm not sure all this effort is really needed on architectures with strong memory ordering.

kernel/sched.c struct cgroup_subsys cpuacct_subsys = { · line 10850

Quoted 8 lines

+ * The current implementation simply executes a memory barrier in an IPI handler
+ * on each active cpu. Going through the hassle of taking run queue locks and
+ * checking if the thread running on each online CPU belongs to the current
+ * thread seems more heavyweight than the cost of the IPI itself.
+ */

kernel/sched.c +3 -0

+SYSCALL_DEFINE0(membarrier)
+{
+	on_each_cpu(membarrier_ipi, NULL, 1);

Can't you use mm->cpu_vm_mask?

Quoted 3 lines

If the task->rq changes, or the task->rq->curr changes, and makes the condition fail (or even pass), the events that cause those changes are probably good enough than needing to call smp_mb();

This narrows the fatal window, but does not eliminate it. :-(

The CPU doing the sys_membarrier() might see an old value of ->curr, and the other CPU might see an old value of whatever pointer we are trying to recycle. This combination is fatal.

Quoted 8 lines · Peter Zijlstra

Quoted 5 lines · Josh Triplett

The number of threads doesn't matter nearly as much as the number of threads typically running at a time compared to the number of processors. Of course, we can't measure that as easily, but I don't know that your proposed heuristic would approximate it well.

Quite agreed, and not disturbing RT tasks is even more important.

OK, so I stand un-Reviewed-by twice in one morning. ;-)

Quoted 7 lines

A simple:

  for_each_cpu(cpu, current->mm->cpu_vm_mask) {
     if (cpu_curr(cpu)->mm == current->mm)
        smp_call_function_single(cpu, func, NULL, 1);
  }

Quoted 4 lines

seems far preferable over anything else, if you really want you can use a cpumask to copy cpu_vm_mask in and unset bits and use the mask with smp_call_function_any(), but that includes having to allocate the cpumask, which might or might not be too expensive for Mathieu.

This would be vulnerable to the sys_membarrier() CPU seeing an old value of cpu_curr(cpu)->mm, and that other task seeing the old value of the pointer we are trying to RCU-destroy, right?

Quoted 19 lines · Paul E. McKenney

Quoted 8 lines · Peter Zijlstra

Quoted 5 lines · Josh Triplett

The number of threads doesn't matter nearly as much as the number of threads typically running at a time compared to the number of processors. Of course, we can't measure that as easily, but I don't know that your proposed heuristic would approximate it well.

Quite agreed, and not disturbing RT tasks is even more important.

OK, so I stand un-Reviewed-by twice in one morning. ;-)

Quoted 7 lines

A simple:

  for_each_cpu(cpu, current->mm->cpu_vm_mask) {
     if (cpu_curr(cpu)->mm == current->mm)
        smp_call_function_single(cpu, func, NULL, 1);
  }

Quoted 8 lines

Quoted 4 lines

seems far preferable over anything else, if you really want you can use a cpumask to copy cpu_vm_mask in and unset bits and use the mask with smp_call_function_any(), but that includes having to allocate the cpumask, which might or might not be too expensive for Mathieu.

This would be vulnerable to the sys_membarrier() CPU seeing an old value of cpu_curr(cpu)->mm, and that other task seeing the old value of the pointer we are trying to RCU-destroy, right?

Right, so I was thinking that since you want a mb to be executed when calling sys_membarrier(). If you observe a matching ->mm but the cpu has since scheduled, we're good since it scheduled (but we'll still send the IPI anyway), if we do not observe it because the task gets scheduled in after we do the iteration we're still good because it scheduled.

As to needing to keep rcu_read_lock() around the iteration, for sure we need that to ensure the remote task_struct reference we take is valid.

Quoted 19 lines · Paul E. McKenney

Quoted 8 lines · Peter Zijlstra

Quoted 5 lines · Josh Triplett

The number of threads doesn't matter nearly as much as the number of threads typically running at a time compared to the number of processors. Of course, we can't measure that as easily, but I don't know that your proposed heuristic would approximate it well.

Quite agreed, and not disturbing RT tasks is even more important.

OK, so I stand un-Reviewed-by twice in one morning. ;-)

Quoted 7 lines

A simple:

  for_each_cpu(cpu, current->mm->cpu_vm_mask) {
     if (cpu_curr(cpu)->mm == current->mm)
        smp_call_function_single(cpu, func, NULL, 1);
  }

Quoted 8 lines

Quoted 4 lines

seems far preferable over anything else, if you really want you can use a cpumask to copy cpu_vm_mask in and unset bits and use the mask with smp_call_function_any(), but that includes having to allocate the cpumask, which might or might not be too expensive for Mathieu.

This would be vulnerable to the sys_membarrier() CPU seeing an old value of cpu_curr(cpu)->mm, and that other task seeing the old value of the pointer we are trying to RCU-destroy, right?

Right, so I was thinking that since you want a mb to be executed when calling sys_membarrier(). If you observe a matching ->mm but the cpu has since scheduled, we're good since it scheduled (but we'll still send the IPI anyway), if we do not observe it because the task gets scheduled in after we do the iteration we're still good because it scheduled.

As to needing to keep rcu_read_lock() around the iteration, for sure we need that to ensure the remote task_struct reference we take is valid.

Quoted 29 lines · Peter Zijlstra

Quoted 19 lines · Paul E. McKenney

Quoted 8 lines · Peter Zijlstra

Quoted 5 lines · Josh Triplett

The number of threads doesn't matter nearly as much as the number of threads typically running at a time compared to the number of processors. Of course, we can't measure that as easily, but I don't know that your proposed heuristic would approximate it well.

Quite agreed, and not disturbing RT tasks is even more important.

OK, so I stand un-Reviewed-by twice in one morning. ;-)

Quoted 7 lines

A simple:

  for_each_cpu(cpu, current->mm->cpu_vm_mask) {
     if (cpu_curr(cpu)->mm == current->mm)
        smp_call_function_single(cpu, func, NULL, 1);
  }

Quoted 8 lines

Quoted 4 lines

seems far preferable over anything else, if you really want you can use a cpumask to copy cpu_vm_mask in and unset bits and use the mask with smp_call_function_any(), but that includes having to allocate the cpumask, which might or might not be too expensive for Mathieu.

This would be vulnerable to the sys_membarrier() CPU seeing an old value of cpu_curr(cpu)->mm, and that other task seeing the old value of the pointer we are trying to RCU-destroy, right?

Quoted 5 lines

Right, so I was thinking that since you want a mb to be executed when calling sys_membarrier(). If you observe a matching ->mm but the cpu has since scheduled, we're good since it scheduled (but we'll still send the IPI anyway), if we do not observe it because the task gets scheduled in after we do the iteration we're still good because it scheduled.

Something like the following for sys_membarrier(), then?

  smp_mb();

  for_each_cpu(cpu, current->mm->cpu_vm_mask) {
     if (cpu_curr(cpu)->mm == current->mm)
        smp_call_function_single(cpu, func, NULL, 1);
  }

Then the code changing ->mm on the other CPU also needs to have a full smp_mb() somewhere after the change to ->mm, but before starting user-space execution. Which it might well just due to overhead, but we need to make sure that someone doesn't optimize us out of existence.

Thanx, Paul

Quoted 3 lines

As to needing to keep rcu_read_lock() around the iteration, for sure we need that to ensure the remote task_struct reference we take is valid.

Something like the following for sys_membarrier(), then?

  smp_mb();
  for_each_cpu(cpu, current->mm->cpu_vm_mask) {
     if (cpu_curr(cpu)->mm == current->mm)
        smp_call_function_single(cpu, func, NULL, 1);
  }

Then the code changing ->mm on the other CPU also needs to have a full smp_mb() somewhere after the change to ->mm, but before starting user-space execution. Which it might well just due to overhead, but we need to make sure that someone doesn't optimize us out of existence.

On Thu, Jan 07, 2010 at 01:04:39AM -0500, Mathieu Desnoyers wrote:

Quoted 12 lines

Just tried it with a 10,000,000 iterations loop.

The thread doing the system call loop takes 2.0% of user time, 98% of system time. All other cpus are nearly 100.0% idle. Just to give a bit more info about my test setup, I also have a thread sitting on a CPU busy-waiting for the loop to complete. This thread takes 97.7% user time (but it really is just there to make sure we are indeed doing the IPIs, not skipping it through the thread_group_empty(current) test). If I remove this thread, the execution time of the test program shrinks from 32 seconds down to 1.9 seconds. So yes, the IPI is actually executed in the first place, because removing the extra thread accelerates the loop tremendously. I used a 8-core Xeon to test.

Do you know if the kernel properly measures the overhead of IPIs? The CPUs might have only looked idle. What about running some kind of CPU-bound benchmark on the other CPUs and testing the completion time with and without the process running the membarrier loop?

Quoted 6 lines

Quoted 5 lines

- Part of me thinks this ought to become slightly more general, and just deliver a signal that the receiving thread could handle as it likes. However, that would certainly prove more expensive than this, and I don't know that the generality would buy anything.

Quoted 6 lines

A general scheme would have to call every threads, even those which are not running. In the case of this system call, this is a particular case where we can forget about non-running threads, because the memory barrier is implied by the scheduler activity that brought them offline. So I really don't see how we can use this IPI scheme for other things that this kind of synchronization.

No, I don't mean non-running threads. If you wanted that, you could do what urcu currently does, and send a signal to all threads. I meant something like "signal all *running* threads from my process".

Quoted 11 lines

Quoted 3 lines

- Could you somehow register reader threads with the kernel, in a way that makes them easy to detect remotely?

There are two ways I figure out we could do this. One would imply adding extra shared data between kernel and userspace (which I'd like to avoid, to keep coupling low). The other alternative would be to add per task_struct information about this, and new system calls. The added per task_struct information would use up cache lines (which are very important, especially in the task_struct) and the added system call at rcu_read_lock/unlock() would simply kill performance.

No, I didn't mean that you would do a syscall in rcu_read_{lock,unlock}. I meant that you would do a system call when the reader threads start, saying "hey, reader thread here".

- Josh Triplett

Quoted 36 lines · * Paul E. McKenney ([email protected]) wrote:

Quoted 34 lines · Peter Zijlstra

Quoted 19 lines · Paul E. McKenney

Quoted 8 lines · Peter Zijlstra

Quoted 5 lines · Josh Triplett

The number of threads doesn't matter nearly as much as the number of threads typically running at a time compared to the number of processors. Of course, we can't measure that as easily, but I don't know that your proposed heuristic would approximate it well.

Quite agreed, and not disturbing RT tasks is even more important.

OK, so I stand un-Reviewed-by twice in one morning. ;-)

Quoted 7 lines

A simple:

  for_each_cpu(cpu, current->mm->cpu_vm_mask) {
     if (cpu_curr(cpu)->mm == current->mm)
        smp_call_function_single(cpu, func, NULL, 1);
  }

Quoted 8 lines

Quoted 4 lines

seems far preferable over anything else, if you really want you can use a cpumask to copy cpu_vm_mask in and unset bits and use the mask with smp_call_function_any(), but that includes having to allocate the cpumask, which might or might not be too expensive for Mathieu.

This would be vulnerable to the sys_membarrier() CPU seeing an old value of cpu_curr(cpu)->mm, and that other task seeing the old value of the pointer we are trying to RCU-destroy, right?

Right, so I was thinking that since you want a mb to be executed when calling sys_membarrier(). If you observe a matching ->mm but the cpu has since scheduled, we're good since it scheduled (but we'll still send the IPI anyway), if we do not observe it because the task gets scheduled in after we do the iteration we're still good because it scheduled.

Quoted 3 lines

Something like the following for sys_membarrier(), then?

  smp_mb();

This smp_mb() is redundant, as we issue it through the for_each_cpu loop on the local CPU already.

Quoted 5 lines

  for_each_cpu(cpu, current->mm->cpu_vm_mask) {
     if (cpu_curr(cpu)->mm == current->mm)
        smp_call_function_single(cpu, func, NULL, 1);
  }

Quoted 4 lines

Then the code changing ->mm on the other CPU also needs to have a full smp_mb() somewhere after the change to ->mm, but before starting user-space execution. Which it might well just due to overhead, but we need to make sure that someone doesn't optimize us out of existence.

I believe we also need one between execution of the userspace task and change to ->mm. If we have these guarantees I think we are fine.

Mathieu

Quoted 6 lines

Thanx, Paul

Quoted 3 lines

As to needing to keep rcu_read_lock() around the iteration, for sure we need that to ensure the remote task_struct reference we take is valid.

Signature · 7 lines

Mathieu Desnoyers
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to [email protected]
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Quoted 8 lines · Paul E. McKenney

Something like the following for sys_membarrier(), then?

  smp_mb();
  for_each_cpu(cpu, current->mm->cpu_vm_mask) {
     if (cpu_curr(cpu)->mm == current->mm)
        smp_call_function_single(cpu, func, NULL, 1);
  }

Quoted 4 lines

Then the code changing ->mm on the other CPU also needs to have a full smp_mb() somewhere after the change to ->mm, but before starting user-space execution. Which it might well just due to overhead, but we need to make sure that someone doesn't optimize us out of existence.

To change the mm requires things like flushing the TLB. I'd be surprised if the change of the mm does not already do a smp_mb() somewhere.

Quoted 15 lines · Steven Rostedt

Quoted 12 lines · Paul E. McKenney

Something like the following for sys_membarrier(), then?

  smp_mb();
  for_each_cpu(cpu, current->mm->cpu_vm_mask) {
     if (cpu_curr(cpu)->mm == current->mm)
        smp_call_function_single(cpu, func, NULL, 1);
  }

Then the code changing ->mm on the other CPU also needs to have a full smp_mb() somewhere after the change to ->mm, but before starting user-space execution. Which it might well just due to overhead, but we need to make sure that someone doesn't optimize us out of existence.

Quoted 2 lines

To change the mm requires things like flushing the TLB. I'd be surprised if the change of the mm does not already do a smp_mb() somewhere.

Agreed, but "somewhere" does not fill me with warm fuzzies. ;-)

On Wed, 2010-01-06 at 23:40 -0500, Mathieu Desnoyers wrote:

http://marc.info/?t=126283939400002

Quoted 8 lines

Index: linux-2.6-lttng/kernel/sched.c
===================================================================

kernel/sched.c +0 -0

@@ -10822,6 +10822,36 @@ struct cgroup_subsys cpuacct_subsys = {
 };
 #endif	/* CONFIG_CGROUP_CPUACCT */
 

kernel/sched.c struct cgroup_subsys cpuacct_subsys = { · line 10834

Quoted 10 lines

kernel/sched.c +10 -0

+/*
+ * Execute a memory barrier on all CPUs on SMP systems.
+ * Do not rely on implicit barriers in smp_call_function(), just in case they
+ * are ever relaxed in the future.
+ */
+static void membarrier_ipi(void *unused)
+{
+	smp_mb();
+}
+

Also, there was some talk a while ago about IPIs implying memory barriers. Which I of course forgot all details about,.. at least sending one implies a wmb and receiving one an rmb, but it could be stronger, Oleg?

Quoted 13 lines · Peter Zijlstra

On Wed, 2010-01-06 at 23:40 -0500, Mathieu Desnoyers wrote:

http://marc.info/?t=126283939400002

Quoted 8 lines

Index: linux-2.6-lttng/kernel/sched.c
===================================================================

kernel/sched.c +0 -0

@@ -10822,6 +10822,36 @@ struct cgroup_subsys cpuacct_subsys = {
 };
 #endif	/* CONFIG_CGROUP_CPUACCT */
 

Quoted 15 lines

kernel/sched.c struct cgroup_subsys cpuacct_subsys = { · line 10834

Quoted 10 lines

kernel/sched.c +10 -0

+/*
+ * Execute a memory barrier on all CPUs on SMP systems.
+ * Do not rely on implicit barriers in smp_call_function(), just in case they
+ * are ever relaxed in the future.
+ */
+static void membarrier_ipi(void *unused)
+{
+	smp_mb();
+}
+

Also, there was some talk a while ago about IPIs implying memory barriers. Which I of course forgot all details about,.. at least sending one implies a wmb and receiving one an rmb, but it could be stronger, Oleg?

IIRC, it was decided that IPIs must imply mb(), but I am not sure this is true on any arch/

However, even if IPI didn't imply mb(), I don't understand why it is needed... After the quick reading of the original changelog in
http://marc.info/?l=linux-kernel&m=126283923115068

	Thread A                    Thread B
	prev mem accesses           prev mem accesses
	sys_membarrier()            barrier()
	follow mem accesses         follow mem accesses

sys_membarrier() should "insert" mb() on behalf of B "instead" of barrier(), right? But, if we send IPI, B enters kernel mode and returns to user-mode. Should this imply mb() in any case?

Quoted 16 lines · Paul E. McKenney

Quoted 15 lines · Steven Rostedt

Quoted 12 lines · Paul E. McKenney

Something like the following for sys_membarrier(), then?

  smp_mb();
  for_each_cpu(cpu, current->mm->cpu_vm_mask) {
     if (cpu_curr(cpu)->mm == current->mm)
        smp_call_function_single(cpu, func, NULL, 1);
  }

Then the code changing ->mm on the other CPU also needs to have a full smp_mb() somewhere after the change to ->mm, but before starting user-space execution. Which it might well just due to overhead, but we need to make sure that someone doesn't optimize us out of existence.

Quoted 4 lines

Quoted 2 lines

To change the mm requires things like flushing the TLB. I'd be surprised if the change of the mm does not already do a smp_mb() somewhere.

Agreed, but "somewhere" does not fill me with warm fuzzies. ;-)

Another question would be, does flushing the TLB imply a mb()?

Quoted 3 lines

sys_membarrier() should "insert" mb() on behalf of B "instead" of barrier(), right? But, if we send IPI, B enters kernel mode and returns to user-mode. Should this imply mb() in any case?

Hello, Oleg,

The issue is with some suggested optimizations that would avoid sending the IPI to CPUs that are not running threads in the same process as the thread executing the sys_membarrier(). Some forms of these optimizations sample ->mm without locking, and the question is whether this is safe.

Quoted 10 lines · Paul E. McKenney

Quoted 3 lines

sys_membarrier() should "insert" mb() on behalf of B "instead" of barrier(), right? But, if we send IPI, B enters kernel mode and returns to user-mode. Should this imply mb() in any case?

Hello, Oleg,

The issue is with some suggested optimizations that would avoid sending the IPI to CPUs that are not running threads in the same process as the thread executing the sys_membarrier(). Some forms of these optimizations sample ->mm without locking, and the question is whether this is safe.

Note, we are not suggesting optimizations. It has nothing to do with performance of the syscall. We just can't allow one process to be DoSing another process on another cpu by it sending out millions of IPIs. Mathieu already showed that you could cause a 2x slowdown to the unrelated tasks.

Quoted 5 lines

Note, we are not suggesting optimizations. It has nothing to do with performance of the syscall. We just can't allow one process to be DoSing another process on another cpu by it sending out millions of IPIs. Mathieu already showed that you could cause a 2x slowdown to the unrelated tasks.

I would have said that we are trying to optimize our way out of a DoS situation, but point taken. Whatever we choose to call it, the discussion is on the suggested modifications, not strictly on the original patch. ;-)

Quoted 9 lines · Paul E. McKenney

Quoted 5 lines

Note, we are not suggesting optimizations. It has nothing to do with performance of the syscall. We just can't allow one process to be DoSing another process on another cpu by it sending out millions of IPIs. Mathieu already showed that you could cause a 2x slowdown to the unrelated tasks.

I would have said that we are trying to optimize our way out of a DoS situation, but point taken. Whatever we choose to call it, the discussion is on the suggested modifications, not strictly on the original patch. ;-)

OK, I just want to get a better understanding of what can go wrong. A sys_membarrier() is used as follows, correct? (using a list example)

	<user space>

	list_del(obj);

	synchronize_rcu();  -> calls sys_membarrier();

	free(obj);

And we need to protect against:

	<user space>

	read_rcu_lock();

	obj = list->next;

	use_object(obj);

	read_rcu_unlock();

where we want to make sure that the synchronize_rcu() makes sure that we have passed the grace period of all takers of read_rcu_lock(). Now I have not looked at the code that implements userspace rcu, so I'm making a lot of assumptions here. But the problem that we need to avoid is:

	CPU 1				CPU 2
     -----------                    -------------

	<user space>			<user space>

					rcu_read_lock();

					obj = list->next

	list_del(obj)

					< Interrupt >
					< kernel space>
					<schedule>

					<kernel_thread>

					<schedule>

					< back to original task >

	sys_membarrier();
	< kernel space >

	if (task_rq(task)->curr != task)
	< but still sees kernel thread >

	< user space >

	< misses that we are still in rcu section >

	free(obj);

					< user space >

					use_object(obj); <=== crash!

I guess what I'm trying to do here is to understand what can go wrong, and then when we understand the issues, we can find a solution.

I believe that I am worried about a different scenario. I do not believe that the scenario you lay out above can actually happen. The pair of schedules on CPU 2 have to act as a full memory barrier, otherwise, it would not be safe to resume a task on some other CPU.

If the pair
of schedules act as a full memory barrier, then the code in synchronize_rcu() that looks at the RCU read-side state would see that CPU 2 is in an RCU read-side critical section.

The scenario that I am (perhaps wrongly) concerned about is enabled by the fact that URCU's rcu_read_lock() has a load, some checks, and a store. It has compiler constraints, but no hardware memory barriers. This means that CPUs (even x86) can execute an rcu_dereference() before the rcu_read_lock()'s store has executed.

Hacking your example above, keeping mind that x86 can reorder subsequent loads to precede prior stores:

	CPU 1				CPU 2
     -----------                    -------------

	<user space>			<kernel space, switching to task>

					->curr updated

					<long code path, maybe mb?>

					<user space>

					rcu_read_lock(); [load only]

					obj = list->next

	list_del(obj)

	sys_membarrier();
	< kernel space >

	if (task_rq(task)->curr != task)
	< but load to obj reordered before store to ->curr >

	< user space >

	< misses that CPU 2 is in rcu section >

	[CPU 2's ->curr update now visible]

	[CPU 2's rcu_read_lock() store now visible]

	free(obj);

					use_object(obj); <=== crash!

If the "long code path" happens to include a full memory barrier, or if it happens to be long enough to overflow CPU 2's store buffer, then the above scenario cannot happen. Until such time as someone applies some unforeseen optimization to the context-switch path.

And, yes, the context-switch path has to have a full memory barrier somewhere, but that somewhere could just as easily come before the update of ->curr.

The same scenario applies when using ->cpu_vm_mask instead of ->curr.

Now, I could easily believe that the current context-switch code has sufficient atomic operations, memory barriers, and instructions to prevent this scenario from occurring, but it is feeling a lot like an accident waiting to happen. Hence my strident complaints. ;-)

Quoted 4 lines · Paul E. McKenney

I believe that I am worried about a different scenario. I do not believe that the scenario you lay out above can actually happen. The pair of schedules on CPU 2 have to act as a full memory barrier, otherwise, it would not be safe to resume a task on some other CPU.

I'm not so sure about that. The update of ->curr happens inside a spinlock, which is a rmb() ... wmb() pair. Must be, because a spin_lock must be an rmb otherwise the loads could move outside the lock, and the spin_unlock must be a wmb() otherwise what was written could move outside the lock.

Quoted 30 lines

If the pair
of schedules act as a full memory barrier, then the code in synchronize_rcu() that looks at the RCU read-side state would see that CPU 2 is in an RCU read-side critical section.

The scenario that I am (perhaps wrongly) concerned about is enabled by the fact that URCU's rcu_read_lock() has a load, some checks, and a store. It has compiler constraints, but no hardware memory barriers. This means that CPUs (even x86) can execute an rcu_dereference() before the rcu_read_lock()'s store has executed.

Hacking your example above, keeping mind that x86 can reorder subsequent loads to precede prior stores:

	CPU 1				CPU 2
     -----------                    -------------

	<user space>			<kernel space, switching to task>

					->curr updated

					<long code path, maybe mb?>

					<user space>

					rcu_read_lock(); [load only]

					obj = list->next

Quoted 4 lines

	list_del(obj)

	sys_membarrier();
	< kernel space >

Well, if we just grab the task_rq(task)->lock here, then we should be OK? We would guarantee that curr is either the task we want or not.

Quoted 22 lines

	if (task_rq(task)->curr != task)
	< but load to obj reordered before store to ->curr >

	< user space >

	< misses that CPU 2 is in rcu section >

	[CPU 2's ->curr update now visible]

	[CPU 2's rcu_read_lock() store now visible]

	free(obj);

					use_object(obj); <=== crash!

If the "long code path" happens to include a full memory barrier, or if it happens to be long enough to overflow CPU 2's store buffer, then the above scenario cannot happen. Until such time as someone applies some unforeseen optimization to the context-switch path.

Quoted 3 lines

And, yes, the context-switch path has to have a full memory barrier somewhere, but that somewhere could just as easily come before the update of ->curr.

Hmm, since ->curr is updated before sched_mm() I'm thinking it would have to be after the update of curr.

Quoted 6 lines

The same scenario applies when using ->cpu_vm_mask instead of ->curr.

Now, I could easily believe that the current context-switch code has sufficient atomic operations, memory barriers, and instructions to prevent this scenario from occurring, but it is feeling a lot like an accident waiting to happen. Hence my strident complaints. ;-)

I'm totally with you on this. I really want a good understanding of what can go wrong, and show that we have the necessary infrastructure to prevent it.

Quoted 4 lines · Paul E. McKenney

I believe that I am worried about a different scenario. I do not believe that the scenario you lay out above can actually happen. The pair of schedules on CPU 2 have to act as a full memory barrier, otherwise, it would not be safe to resume a task on some other CPU.

I'm not so sure about that. The update of ->curr happens inside a spinlock, which is a rmb() ... wmb() pair. Must be, because a spin_lock must be an rmb otherwise the loads could move outside the lock, and the spin_unlock must be a wmb() otherwise what was written could move outside the lock.

Quoted 32 lines

If the pair
of schedules act as a full memory barrier, then the code in synchronize_rcu() that looks at the RCU read-side state would see that CPU 2 is in an RCU read-side critical section.

The scenario that I am (perhaps wrongly) concerned about is enabled by the fact that URCU's rcu_read_lock() has a load, some checks, and a store. It has compiler constraints, but no hardware memory barriers. This means that CPUs (even x86) can execute an rcu_dereference() before the rcu_read_lock()'s store has executed.

Hacking your example above, keeping mind that x86 can reorder subsequent loads to precede prior stores:

	CPU 1				CPU 2
     -----------                    -------------

	<user space>			<kernel space, switching to task>

					->curr updated

					<long code path, maybe mb?>

					<user space>

					rcu_read_lock(); [load only]

					obj = list->next

Quoted 4 lines

	list_del(obj)

	sys_membarrier();
	< kernel space >

Well, if we just grab the task_rq(task)->lock here, then we should be OK? We would guarantee that curr is either the task we want or not.

Well, if we just grab the task_rq(task)->lock here, then we should be OK? We would guarantee that curr is either the task we want or not.

Quoted 2 lines · * Steven Rostedt ([email protected]) wrote:

Well, if we just grab the task_rq(task)->lock here, then we should be OK? We would guarantee that curr is either the task we want or not.

Hrm, I just tested it, and there seems to be a significant performance penality involved with taking these locks for each CPU, even with just 8 cores. So if we can do without the locks, that would be preferred.

Quoted 7 lines · Mathieu Desnoyers

Quoted 2 lines · * Steven Rostedt ([email protected]) wrote:

Well, if we just grab the task_rq(task)->lock here, then we should be OK? We would guarantee that curr is either the task we want or not.

Hrm, I just tested it, and there seems to be a significant performance penality involved with taking these locks for each CPU, even with just 8 cores. So if we can do without the locks, that would be preferred.

How significant? Factor of two? Two orders of magnitude?

Quoted 11 lines · * Paul E. McKenney ([email protected]) wrote:

Quoted 7 lines · Mathieu Desnoyers

Quoted 2 lines · * Steven Rostedt ([email protected]) wrote:

Well, if we just grab the task_rq(task)->lock here, then we should be OK? We would guarantee that curr is either the task we want or not.

Hrm, I just tested it, and there seems to be a significant performance penality involved with taking these locks for each CPU, even with just 8 cores. So if we can do without the locks, that would be preferred.

How significant? Factor of two? Two orders of magnitude?

On a 8-core Intel Xeon (T is the number of threads receiving the IPIs):

Without runqueue locks:

T=1: 0m13.911s
T=2: 0m20.730s
T=3: 0m21.474s
T=4: 0m27.952s
T=5: 0m26.286s
T=6: 0m27.855s
T=7: 0m29.695s

With runqueue locks:

T=1: 0m15.802s
T=2: 0m22.484s
T=3: 0m24.751s
T=4: 0m29.134s
T=5: 0m30.094s
T=6: 0m33.090s
T=7: 0m33.897s

So on 8 cores, taking spinlocks for each of the 8 runqueues adds about 15% overhead when doing an IPI to 1 thread. Therefore, that won't be pretty on 128+-core machines.

Quoted 35 lines · Mathieu Desnoyers

Quoted 11 lines · * Paul E. McKenney ([email protected]) wrote:

Quoted 7 lines · Mathieu Desnoyers

Quoted 2 lines · * Steven Rostedt ([email protected]) wrote:

Well, if we just grab the task_rq(task)->lock here, then we should be OK? We would guarantee that curr is either the task we want or not.

Hrm, I just tested it, and there seems to be a significant performance penality involved with taking these locks for each CPU, even with just 8 cores. So if we can do without the locks, that would be preferred.

How significant? Factor of two? Two orders of magnitude?

On a 8-core Intel Xeon (T is the number of threads receiving the IPIs):

Without runqueue locks:

T=1: 0m13.911s
T=2: 0m20.730s
T=3: 0m21.474s
T=4: 0m27.952s
T=5: 0m26.286s
T=6: 0m27.855s
T=7: 0m29.695s

With runqueue locks:

T=1: 0m15.802s
T=2: 0m22.484s
T=3: 0m24.751s
T=4: 0m29.134s
T=5: 0m30.094s
T=6: 0m33.090s
T=7: 0m33.897s

Quoted 3 lines

So on 8 cores, taking spinlocks for each of the 8 runqueues adds about 15% overhead when doing an IPI to 1 thread. Therefore, that won't be pretty on 128+-core machines.

But isn't the bulk of the overhead the IPIs rather than the runqueue locks?

     W/out RQ       W/RQ   % degradation
T=1:    13.91      15.8    1.14
T=2:    20.73      22.48   1.08
T=3:    21.47      24.75   1.15
T=4:    27.95      29.13   1.04
T=5:    26.29      30.09   1.14
T=6:    27.86      33.09   1.19
T=7:    29.7       33.9    1.14

So if we had lots of CPUs, we might want to fan the IPIs out through intermediate CPUs in a tree fashion, but the runqueue locks are not causing excessive pain.

How does this compare to use of POSIX signals? Never mind, POSIX signals are arbitrarily bad if you have way more threads than are actually running at the time...

Thanx, Paul

Quoted 35 lines · Mathieu Desnoyers

Quoted 11 lines · * Paul E. McKenney ([email protected]) wrote:

Quoted 7 lines · Mathieu Desnoyers

Quoted 2 lines · * Steven Rostedt ([email protected]) wrote:

Well, if we just grab the task_rq(task)->lock here, then we should be OK? We would guarantee that curr is either the task we want or not.

Hrm, I just tested it, and there seems to be a significant performance penality involved with taking these locks for each CPU, even with just 8 cores. So if we can do without the locks, that would be preferred.

How significant? Factor of two? Two orders of magnitude?

On a 8-core Intel Xeon (T is the number of threads receiving the IPIs):

Without runqueue locks:

T=1: 0m13.911s
T=2: 0m20.730s
T=3: 0m21.474s
T=4: 0m27.952s
T=5: 0m26.286s
T=6: 0m27.855s
T=7: 0m29.695s

With runqueue locks:

T=1: 0m15.802s
T=2: 0m22.484s
T=3: 0m24.751s
T=4: 0m29.134s
T=5: 0m30.094s
T=6: 0m33.090s
T=7: 0m33.897s

Quoted 3 lines

So on 8 cores, taking spinlocks for each of the 8 runqueues adds about 15% overhead when doing an IPI to 1 thread. Therefore, that won't be pretty on 128+-core machines.

But isn't the bulk of the overhead the IPIs rather than the runqueue locks?

W/out RQ W/RQ % degradation

So if we had lots of CPUs, we might want to fan the IPIs out through intermediate CPUs in a tree fashion, but the runqueue locks are not causing excessive pain.

How does this compare to use of POSIX signals? Never mind, POSIX signals are arbitrarily bad if you have way more threads than are actually running at the time...

Thanx, Paul

Quoted 36 lines · * Paul E. McKenney ([email protected]) wrote:

Quoted 35 lines · Mathieu Desnoyers

Quoted 11 lines · * Paul E. McKenney ([email protected]) wrote:

Quoted 7 lines · Mathieu Desnoyers

Quoted 2 lines · * Steven Rostedt ([email protected]) wrote:

Well, if we just grab the task_rq(task)->lock here, then we should be OK? We would guarantee that curr is either the task we want or not.

Hrm, I just tested it, and there seems to be a significant performance penality involved with taking these locks for each CPU, even with just 8 cores. So if we can do without the locks, that would be preferred.

How significant? Factor of two? Two orders of magnitude?

On a 8-core Intel Xeon (T is the number of threads receiving the IPIs):

Without runqueue locks:

T=1: 0m13.911s
T=2: 0m20.730s
T=3: 0m21.474s
T=4: 0m27.952s
T=5: 0m26.286s
T=6: 0m27.855s
T=7: 0m29.695s

With runqueue locks:

T=1: 0m15.802s
T=2: 0m22.484s
T=3: 0m24.751s
T=4: 0m29.134s
T=5: 0m30.094s
T=6: 0m33.090s
T=7: 0m33.897s

Quoted 8 lines

Quoted 3 lines

So on 8 cores, taking spinlocks for each of the 8 runqueues adds about 15% overhead when doing an IPI to 1 thread. Therefore, that won't be pretty on 128+-core machines.

But isn't the bulk of the overhead the IPIs rather than the runqueue locks?

W/out RQ W/RQ % degradation

fix:

       W/out RQ       W/RQ   ratio
> T=1:    13.91      15.8    1.14
> T=2:    20.73      22.48   1.08
> T=3:    21.47      24.75   1.15
> T=4:    27.95      29.13   1.04
> T=5:    26.29      30.09   1.14
> T=6:    27.86      33.09   1.19
> T=7:    29.7       33.9    1.14

These numbers tell you that the degradation is roughly constant as we add more threads (let's consider 1 thread per core, 1 IPI per thread, with active threads). It is all run on a 8-core system will all cpus active. As we increase the number of IPIs (e.g. T=2 -> T=7) we add 9s, for 1.8s/IPI (always for 10,000,000 sys_membarrier() calls), for an added 180 ns/core per call. (note: T=1 is a special-case, as I do not allocate any cpumask.)

Using the spinlocks adds about 3s for 10,000,000 sys_membarrier() calls or a 8-core system, for an added 300 ns/core per call.

So the overhead of taking the task lock is about twice higher, per core, than the overhead of the IPIs. This is understandable if the architecture does an IPI broadcast: the scalability problem then boils down to exchange cache-lines to inform the ipi sender that the other cpus have completed. An atomic operation exchanging a cache-line would be expected to be within the irqoff+spinlock+spinunlock+irqon overhead.

Quoted 3 lines

So if we had lots of CPUs, we might want to fan the IPIs out through intermediate CPUs in a tree fashion, but the runqueue locks are not causing excessive pain.

A tree hierarchy may not be useful for sending the IPIs (as, hopefully, they can be broadcasted pretty efficiciently), but however could be useful when waiting for the IPIs to complete efficiently.

Quoted 3 lines

How does this compare to use of POSIX signals? Never mind, POSIX signals are arbitrarily bad if you have way more threads than are actually running at the time...

POSIX signals to all threads are terrible in that they require to wake up all those threads. I have not even thought it useful to compare these two approaches with benchmarks yet (I'll do that when the sys_membarrier() support is implemented in liburcu).

Quoted 66 lines · Mathieu Desnoyers

Quoted 36 lines · * Paul E. McKenney ([email protected]) wrote:

Quoted 35 lines · Mathieu Desnoyers

Quoted 11 lines · * Paul E. McKenney ([email protected]) wrote:

Quoted 7 lines · Mathieu Desnoyers

Quoted 2 lines · * Steven Rostedt ([email protected]) wrote:

Well, if we just grab the task_rq(task)->lock here, then we should be OK? We would guarantee that curr is either the task we want or not.

Hrm, I just tested it, and there seems to be a significant performance penality involved with taking these locks for each CPU, even with just 8 cores. So if we can do without the locks, that would be preferred.

How significant? Factor of two? Two orders of magnitude?

On a 8-core Intel Xeon (T is the number of threads receiving the IPIs):

Without runqueue locks:

T=1: 0m13.911s
T=2: 0m20.730s
T=3: 0m21.474s
T=4: 0m27.952s
T=5: 0m26.286s
T=6: 0m27.855s
T=7: 0m29.695s

With runqueue locks:

T=1: 0m15.802s
T=2: 0m22.484s
T=3: 0m24.751s
T=4: 0m29.134s
T=5: 0m30.094s
T=6: 0m33.090s
T=7: 0m33.897s

Quoted 8 lines

Quoted 3 lines

So on 8 cores, taking spinlocks for each of the 8 runqueues adds about 15% overhead when doing an IPI to 1 thread. Therefore, that won't be pretty on 128+-core machines.

But isn't the bulk of the overhead the IPIs rather than the runqueue locks?

W/out RQ W/RQ % degradation

fix:

       W/out RQ       W/RQ   ratio
> T=1:    13.91      15.8    1.14
> T=2:    20.73      22.48   1.08
> T=3:    21.47      24.75   1.15
> T=4:    27.95      29.13   1.04
> T=5:    26.29      30.09   1.14
> T=6:    27.86      33.09   1.19
> T=7:    29.7       33.9    1.14

These numbers tell you that the degradation is roughly constant as we add more threads (let's consider 1 thread per core, 1 IPI per thread, with active threads). It is all run on a 8-core system will all cpus active. As we increase the number of IPIs (e.g. T=2 -> T=7) we add 9s, for 1.8s/IPI (always for 10,000,000 sys_membarrier() calls), for an added 180 ns/core per call. (note: T=1 is a special-case, as I do not allocate any cpumask.)

Using the spinlocks adds about 3s for 10,000,000 sys_membarrier() calls or a 8-core system, for an added 300 ns/core per call.

Quoted 6 lines

So the overhead of taking the task lock is about twice higher, per core, than the overhead of the IPIs. This is understandable if the architecture does an IPI broadcast: the scalability problem then boils down to exchange cache-lines to inform the ipi sender that the other cpus have completed. An atomic operation exchanging a cache-line would be expected to be within the irqoff+spinlock+spinunlock+irqon overhead.

Let me rephrase the question... Isn't the vast bulk of the overhead something other than the runqueue spinlocks?

Quoted 8 lines

Quoted 4 lines

So if we had lots of CPUs, we might want to fan the IPIs out through intermediate CPUs in a tree fashion, but the runqueue locks are not causing excessive pain.

A tree hierarchy may not be useful for sending the IPIs (as, hopefully, they can be broadcasted pretty efficiciently), but however could be useful when waiting for the IPIs to complete efficiently.

OK, given that you precompute the CPU mask, you might be able to take advantage of hardware broadcast, on architectures having it.

Quoted 4 lines

Quoted 3 lines

How does this compare to use of POSIX signals? Never mind, POSIX signals are arbitrarily bad if you have way more threads than are actually running at the time...

Quoted 4 lines

POSIX signals to all threads are terrible in that they require to wake up all those threads. I have not even thought it useful to compare these two approaches with benchmarks yet (I'll do that when the sys_membarrier() support is implemented in liburcu).

It would be of some interest. I bet that the runqueue spinlock overhead is -way- down in the noise by comparison to POSIX signals, even when all the threads are running. ;-)

Quoted 10 lines

Quoted 9 lines

Using the spinlocks adds about 3s for 10,000,000 sys_membarrier() calls or a 8-core system, for an added 300 ns/core per call.

So the overhead of taking the task lock is about twice higher, per core, than the overhead of the IPIs. This is understandable if the architecture does an IPI broadcast: the scalability problem then boils down to exchange cache-lines to inform the ipi sender that the other cpus have completed. An atomic operation exchanging a cache-line would be expected to be within the irqoff+spinlock+spinunlock+irqon overhead.

Quoted 2 lines

Let me rephrase the question... Isn't the vast bulk of the overhead something other than the runqueue spinlocks?

I don't think so. What we have here is:

O(1)
- a system call
- cpumask allocation
- IPI broadcast

O(nr cpus)

- wait for IPI handlers to complete
- runqueue spinlocks

Then we should have O(tasks) for spinlocks taken, and O(min(tasks, CPUS)) for IPIs.

cpumask = 0;
foreach task {

	spin_lock(task_rq(task)->rq->lock);
	if (task_rq(task)->curr == task)
		cpu_set(task_cpu(task), cpumask);
	spin_unlock(task_rq(task)->rq->lock);
}

send_ipi(cpumask);

Quoted 74 lines · * Paul E. McKenney ([email protected]) wrote:

Quoted 66 lines · Mathieu Desnoyers

Quoted 36 lines · * Paul E. McKenney ([email protected]) wrote:

Quoted 35 lines · Mathieu Desnoyers

Quoted 11 lines · * Paul E. McKenney ([email protected]) wrote:

Quoted 7 lines · Mathieu Desnoyers

Quoted 2 lines · * Steven Rostedt ([email protected]) wrote:

Well, if we just grab the task_rq(task)->lock here, then we should be OK? We would guarantee that curr is either the task we want or not.

Hrm, I just tested it, and there seems to be a significant performance penality involved with taking these locks for each CPU, even with just 8 cores. So if we can do without the locks, that would be preferred.

How significant? Factor of two? Two orders of magnitude?

On a 8-core Intel Xeon (T is the number of threads receiving the IPIs):

Without runqueue locks:

T=1: 0m13.911s
T=2: 0m20.730s
T=3: 0m21.474s
T=4: 0m27.952s
T=5: 0m26.286s
T=6: 0m27.855s
T=7: 0m29.695s

With runqueue locks:

T=1: 0m15.802s
T=2: 0m22.484s
T=3: 0m24.751s
T=4: 0m29.134s
T=5: 0m30.094s
T=6: 0m33.090s
T=7: 0m33.897s

Quoted 8 lines

Quoted 3 lines

So on 8 cores, taking spinlocks for each of the 8 runqueues adds about 15% overhead when doing an IPI to 1 thread. Therefore, that won't be pretty on 128+-core machines.

But isn't the bulk of the overhead the IPIs rather than the runqueue locks?

W/out RQ W/RQ % degradation

fix:

       W/out RQ       W/RQ   ratio
> T=1:    13.91      15.8    1.14
> T=2:    20.73      22.48   1.08
> T=3:    21.47      24.75   1.15
> T=4:    27.95      29.13   1.04
> T=5:    26.29      30.09   1.14
> T=6:    27.86      33.09   1.19
> T=7:    29.7       33.9    1.14

These numbers tell you that the degradation is roughly constant as we add more threads (let's consider 1 thread per core, 1 IPI per thread, with active threads). It is all run on a 8-core system will all cpus active. As we increase the number of IPIs (e.g. T=2 -> T=7) we add 9s, for 1.8s/IPI (always for 10,000,000 sys_membarrier() calls), for an added 180 ns/core per call. (note: T=1 is a special-case, as I do not allocate any cpumask.)

Using the spinlocks adds about 3s for 10,000,000 sys_membarrier() calls or a 8-core system, for an added 300 ns/core per call.

Quoted 6 lines

So the overhead of taking the task lock is about twice higher, per core, than the overhead of the IPIs. This is understandable if the architecture does an IPI broadcast: the scalability problem then boils down to exchange cache-lines to inform the ipi sender that the other cpus have completed. An atomic operation exchanging a cache-line would be expected to be within the irqoff+spinlock+spinunlock+irqon overhead.

Quoted 2 lines

Let me rephrase the question... Isn't the vast bulk of the overhead something other than the runqueue spinlocks?

I don't think so. What we have here is:

O(1)
- a system call
- cpumask allocation
- IPI broadcast

O(nr cpus)
- wait for IPI handlers to complete
- runqueue spinlocks

The O(1) operations seems to be about 5x slower than the combined O(nr cpus) wait and spinlock operations, but this only means that as soon as we have 8 cores, then the bulk of the overhead sits in the runqueue spinlock (if we have to take them).

If we don't take spinlocks, then we can go up to 16 cores before the bulk of the overhead starts to be the "wait for IPI handlers to complete" phase. As you pointed out, we could turn this wait phase into a tree hierarchy. However, we cannot do this with the spinlocks, as they have to be taken for the initial cpumask iteration.

Therefore, if we don't have to take those spinlocks, we can have a very significant gain over this system call overhead, especially on large systems. Not taking spinlocks here allows us to use a tree hierarchy to turn the bulk of the scalability overhead (waiting for IPI handlers to complete) into a O(log(nb cpus)) complexity order, which is quite interesting.

Quoted 20 lines

Quoted 7 lines

Quoted 3 lines

So if we had lots of CPUs, we might want to fan the IPIs out through intermediate CPUs in a tree fashion, but the runqueue locks are not causing excessive pain.

A tree hierarchy may not be useful for sending the IPIs (as, hopefully, they can be broadcasted pretty efficiciently), but however could be useful when waiting for the IPIs to complete efficiently.

OK, given that you precompute the CPU mask, you might be able to take advantage of hardware broadcast, on architectures having it.

Quoted 8 lines

Quoted 3 lines

How does this compare to use of POSIX signals? Never mind, POSIX signals are arbitrarily bad if you have way more threads than are actually running at the time...

POSIX signals to all threads are terrible in that they require to wake up all those threads. I have not even thought it useful to compare these two approaches with benchmarks yet (I'll do that when the sys_membarrier() support is implemented in liburcu).

Quoted 3 lines

It would be of some interest. I bet that the runqueue spinlock overhead is -way- down in the noise by comparison to POSIX signals, even when all the threads are running. ;-)

For 1,000,000 iterations, sending signals to execute a remote mb and waiting for it to complete:

                             W/out RQ       W/RQ   ratio
T=1: 0m3.107s           T=1:    13.91      15.8    1.14
T=2: 0m5.772s           T=2:    20.73      22.48   1.08
T=3: 0m8.662s           T=3:    21.47      24.75   1.15
T=4: 0m12.239s          T=4:    27.95      29.13   1.04
T=5: 0m16.213s          T=5:    26.29      30.09   1.14
T=6: 0m19.482s          T=6:    27.86      33.09   1.19
T=7: 0m23.227s          T=7:    29.7       33.9    1.14

So, per iteration:

T=1: 3107 ns
T=2: 5772 ns
T=3: 8662 ns
T=4: 12239 ns
T=5: 16213 ns
T=6: 19482 ns
T=7: 23227 ns

For an added 3000 ns per extra thread. So, yes, the added 300 ns/core for spinlocks is almost lost in the noise compared to the signal-based solution, but it's not because the old solution was behaving so poorly that we can rely on it to say what is noise vs not in the current implementation. Looking at what the scalability bottlenecks are, and looking at what is noise within the current implementation seems like a more appropriate way to design an efficient system call.

So all in all, we can expect around 6.25-fold improvement because we diminish the per-core overhead if we use the spinlocks (480 ns/core vs 3000 ns/core), but if we don't take the runqueue spinlocks (180 ns/core), then we are contemplating a 16.7-fold improvement. And this is without considering a tree-hierarchy for waiting for IPIs to complete, which would additionally change the order of the scalability overhead from O(n) to O(log(n)).

Quoted 2 lines · Steven Rostedt

Then we should have O(tasks) for spinlocks taken, and O(min(tasks, CPUS)) for IPIs.

And for nr tasks >> CPUS, this may help too:

Quoted 2 lines

cpumask = 0;
foreach task {

	if (cpumask == online_cpus)
		break;

Quoted 6 lines

	spin_lock(task_rq(task)->rq->lock);
	if (task_rq(task)->curr == task)
		cpu_set(task_cpu(task), cpumask);
	spin_unlock(task_rq(task)->rq->lock);
}

send_ipi(cpumask);

Quoted 5 lines · Steven Rostedt

Quoted 2 lines · Steven Rostedt

Then we should have O(tasks) for spinlocks taken, and O(min(tasks, CPUS)) for IPIs.

Quoted 14 lines

And for nr tasks >> CPUS, this may help too:

Quoted 2 lines

cpumask = 0;
foreach task {

	if (cpumask == online_cpus)
		break;

Quoted 6 lines

	spin_lock(task_rq(task)->rq->lock);
	if (task_rq(task)->curr == task)
		cpu_set(task_cpu(task), cpumask);
	spin_unlock(task_rq(task)->rq->lock);
}

send_ipi(cpumask);

Good point, erring on the side of sending too many IPIs is safe. One might even be able to just send the full set if enough of the CPUs were running the current process and none of the remainder were running real-time threads. And yes, it would then be necessary to throttle calls to sys_membarrier().

Quoted 15 lines · Mathieu Desnoyers

Quoted 10 lines

Quoted 9 lines

Using the spinlocks adds about 3s for 10,000,000 sys_membarrier() calls or a 8-core system, for an added 300 ns/core per call.

So the overhead of taking the task lock is about twice higher, per core, than the overhead of the IPIs. This is understandable if the architecture does an IPI broadcast: the scalability problem then boils down to exchange cache-lines to inform the ipi sender that the other cpus have completed. An atomic operation exchanging a cache-line would be expected to be within the irqoff+spinlock+spinunlock+irqon overhead.

Quoted 2 lines

Let me rephrase the question... Isn't the vast bulk of the overhead something other than the runqueue spinlocks?

I don't think so. What we have here is:

Quoted 6 lines

O(1)
- a system call
- cpumask allocation
- IPI broadcast

O(nr cpus)

Isn't this really O(tasks) ?

Don't you do the spinlock(task_rq(task)->rq->lock)?

So the scale is not with large boxes, but the number of tasks that must be checked. Still, if you have 1000 threads, a rcu writer is bound to take a bit of overhead. But the advantage is the readers are still fast.

RCU is known to be slow for writing. A user must be aware of this.

Then we should have O(tasks) for spinlocks taken, and O(min(tasks, CPUS)) for IPIs.

cpumask = 0;

foreach task {
	spin_lock(task_rq(task)->rq->lock);
	if (task_rq(task)->curr == task)
		cpu_set(task_cpu(task), cpumask);
	spin_unlock(task_rq(task)->rq->lock);
}

send_ipi(cpumask);

-- Steve

Quoted 2 lines

- wait for IPI handlers to complete
- runqueue spinlocks

Quoted 3 lines · Steven Rostedt

Then we should have O(tasks) for spinlocks taken, and O(min(tasks, CPUS)) for IPIs.

And for nr tasks >> CPUS, this may help too:

Quoted 2 lines

cpumask = 0;
foreach task {

	if (cpumask == online_cpus)
		break;

Quoted 8 lines

	spin_lock(task_rq(task)->rq->lock);
	if (task_rq(task)->curr == task)
		cpu_set(task_cpu(task), cpumask);
	spin_unlock(task_rq(task)->rq->lock);
}

send_ipi(cpumask);

-- Steve

Quoted 100 lines · Mathieu Desnoyers

Quoted 74 lines · * Paul E. McKenney ([email protected]) wrote:

Quoted 66 lines · Mathieu Desnoyers

Quoted 36 lines · * Paul E. McKenney ([email protected]) wrote:

Quoted 35 lines · Mathieu Desnoyers

Quoted 11 lines · * Paul E. McKenney ([email protected]) wrote:

Quoted 7 lines · Mathieu Desnoyers

Quoted 2 lines · * Steven Rostedt ([email protected]) wrote:

Well, if we just grab the task_rq(task)->lock here, then we should be OK? We would guarantee that curr is either the task we want or not.

Hrm, I just tested it, and there seems to be a significant performance penality involved with taking these locks for each CPU, even with just 8 cores. So if we can do without the locks, that would be preferred.

How significant? Factor of two? Two orders of magnitude?

On a 8-core Intel Xeon (T is the number of threads receiving the IPIs):

Without runqueue locks:

T=1: 0m13.911s
T=2: 0m20.730s
T=3: 0m21.474s
T=4: 0m27.952s
T=5: 0m26.286s
T=6: 0m27.855s
T=7: 0m29.695s

With runqueue locks:

T=1: 0m15.802s
T=2: 0m22.484s
T=3: 0m24.751s
T=4: 0m29.134s
T=5: 0m30.094s
T=6: 0m33.090s
T=7: 0m33.897s

Quoted 8 lines

Quoted 3 lines

So on 8 cores, taking spinlocks for each of the 8 runqueues adds about 15% overhead when doing an IPI to 1 thread. Therefore, that won't be pretty on 128+-core machines.

But isn't the bulk of the overhead the IPIs rather than the runqueue locks?

W/out RQ W/RQ % degradation

fix:

       W/out RQ       W/RQ   ratio
> T=1:    13.91      15.8    1.14
> T=2:    20.73      22.48   1.08
> T=3:    21.47      24.75   1.15
> T=4:    27.95      29.13   1.04
> T=5:    26.29      30.09   1.14
> T=6:    27.86      33.09   1.19
> T=7:    29.7       33.9    1.14

These numbers tell you that the degradation is roughly constant as we add more threads (let's consider 1 thread per core, 1 IPI per thread, with active threads). It is all run on a 8-core system will all cpus active. As we increase the number of IPIs (e.g. T=2 -> T=7) we add 9s, for 1.8s/IPI (always for 10,000,000 sys_membarrier() calls), for an added 180 ns/core per call. (note: T=1 is a special-case, as I do not allocate any cpumask.)

Using the spinlocks adds about 3s for 10,000,000 sys_membarrier() calls or a 8-core system, for an added 300 ns/core per call.

Quoted 6 lines

So the overhead of taking the task lock is about twice higher, per core, than the overhead of the IPIs. This is understandable if the architecture does an IPI broadcast: the scalability problem then boils down to exchange cache-lines to inform the ipi sender that the other cpus have completed. An atomic operation exchanging a cache-line would be expected to be within the irqoff+spinlock+spinunlock+irqon overhead.

Quoted 2 lines

Let me rephrase the question... Isn't the vast bulk of the overhead something other than the runqueue spinlocks?

I don't think so. What we have here is:

O(1)
- a system call
- cpumask allocation
- IPI broadcast

O(nr cpus)
- wait for IPI handlers to complete
- runqueue spinlocks

The O(1) operations seems to be about 5x slower than the combined O(nr cpus) wait and spinlock operations, but this only means that as soon as we have 8 cores, then the bulk of the overhead sits in the runqueue spinlock (if we have to take them).

If we don't take spinlocks, then we can go up to 16 cores before the bulk of the overhead starts to be the "wait for IPI handlers to complete" phase. As you pointed out, we could turn this wait phase into a tree hierarchy. However, we cannot do this with the spinlocks, as they have to be taken for the initial cpumask iteration.

Quoted 6 lines

Therefore, if we don't have to take those spinlocks, we can have a very significant gain over this system call overhead, especially on large systems. Not taking spinlocks here allows us to use a tree hierarchy to turn the bulk of the scalability overhead (waiting for IPI handlers to complete) into a O(log(nb cpus)) complexity order, which is quite interesting.

All this would sound plausible if it weren't for the ratio of overheads for runqueue-lock and non-runqueue-lock versions not varying much from one to seven CPUs. ;-)

And please keep in mind that this operations happens on the URCU slowpath. Further, there may be opportunities for much larger savings by batching grace-period requests, given that a single grace period can serve an arbitrarily large number of synchronize_rcu() requests.

Quoted 21 lines

Quoted 21 lines

Quoted 8 lines

Quoted 4 lines

So if we had lots of CPUs, we might want to fan the IPIs out through intermediate CPUs in a tree fashion, but the runqueue locks are not causing excessive pain.

A tree hierarchy may not be useful for sending the IPIs (as, hopefully, they can be broadcasted pretty efficiciently), but however could be useful when waiting for the IPIs to complete efficiently.

OK, given that you precompute the CPU mask, you might be able to take advantage of hardware broadcast, on architectures having it.

Quoted 8 lines

Quoted 3 lines

How does this compare to use of POSIX signals? Never mind, POSIX signals are arbitrarily bad if you have way more threads than are actually running at the time...

POSIX signals to all threads are terrible in that they require to wake up all those threads. I have not even thought it useful to compare these two approaches with benchmarks yet (I'll do that when the sys_membarrier() support is implemented in liburcu).

Quoted 6 lines

Quoted 3 lines

It would be of some interest. I bet that the runqueue spinlock overhead is -way- down in the noise by comparison to POSIX signals, even when all the threads are running. ;-)

For 1,000,000 iterations, sending signals to execute a remote mb and waiting for it to complete:

Adding the previous results for comparison, and please keep in mind the need to multiply the left-hand column by ten before comparing to the right-hand column:

Quoted 8 lines

                             W/out RQ       W/RQ   ratio
T=1: 0m3.107s           T=1:    13.91      15.8    1.14
T=2: 0m5.772s           T=2:    20.73      22.48   1.08
T=3: 0m8.662s           T=3:    21.47      24.75   1.15
T=4: 0m12.239s          T=4:    27.95      29.13   1.04
T=5: 0m16.213s          T=5:    26.29      30.09   1.14
T=6: 0m19.482s          T=6:    27.86      33.09   1.19
T=7: 0m23.227s          T=7:    29.7       33.9    1.14

So sys_membarrier() is roughly a factor of two better than POSIX signals for a single thread, rising to not quite a factor of eight for seven threads. And this data -does- support the notion that POSIX signals get increasingly worse with increasing numbers of threads, as one would expect.

Quoted 11 lines

So, per iteration:

T=1: 3107 ns
T=2: 5772 ns
T=3: 8662 ns
T=4: 12239 ns
T=5: 16213 ns
T=6: 19482 ns
T=7: 23227 ns

Quoted 7 lines

For an added 3000 ns per extra thread. So, yes, the added 300 ns/core for spinlocks is almost lost in the noise compared to the signal-based solution, but it's not because the old solution was behaving so poorly that we can rely on it to say what is noise vs not in the current implementation. Looking at what the scalability bottlenecks are, and looking at what is noise within the current implementation seems like a more appropriate way to design an efficient system call.

I agree that your measurements show a marked improvement compared to POSIX signals that increases with increasing numbers of threads, again, as expected.

Quoted 8 lines

So all in all, we can expect around 6.25-fold improvement because we diminish the per-core overhead if we use the spinlocks (480 ns/core vs 3000 ns/core), but if we don't take the runqueue spinlocks (180 ns/core), then we are contemplating a 16.7-fold improvement. And this is without considering a tree-hierarchy for waiting for IPIs to complete, which would additionally change the order of the scalability overhead from O(n) to O(log(n)).

Eh? You should be able to use the locks to accumulate a cpumask, then use whatever you want, including a tree hierarchy, to both send and wait for the IPIs, right?

Keep in mind that the runqueue locks just force memory ordering on the sampling. It should not be necessary to hold them while sending the IPIs. Or am I missing something?

Thanx, Paul

Quoted 5 lines · Steven Rostedt

Quoted 2 lines · Steven Rostedt

Then we should have O(tasks) for spinlocks taken, and O(min(tasks, CPUS)) for IPIs.

Quoted 14 lines

And for nr tasks >> CPUS, this may help too:

Quoted 2 lines

cpumask = 0;
foreach task {

	if (cpumask == online_cpus)
		break;

Quoted 6 lines

	spin_lock(task_rq(task)->rq->lock);
	if (task_rq(task)->curr == task)
		cpu_set(task_cpu(task), cpumask);
	spin_unlock(task_rq(task)->rq->lock);
}

send_ipi(cpumask);

Good point, erring on the side of sending too many IPIs is safe. One might even be able to just send the full set if enough of the CPUs were running the current process and none of the remainder were running real-time threads. And yes, it would then be necessary to throttle calls to sys_membarrier().

Quickly hiding behind a suitable boulder... ;-)

Thanx, Paul

Quoted 21 lines · Paul E. McKenney

Quoted 5 lines · Steven Rostedt

Quoted 2 lines · Steven Rostedt

Then we should have O(tasks) for spinlocks taken, and O(min(tasks, CPUS)) for IPIs.

Quoted 14 lines

And for nr tasks >> CPUS, this may help too:

Quoted 2 lines

cpumask = 0;
foreach task {

	if (cpumask == online_cpus)
		break;

Quoted 6 lines

	spin_lock(task_rq(task)->rq->lock);
	if (task_rq(task)->curr == task)
		cpu_set(task_cpu(task), cpumask);
	spin_unlock(task_rq(task)->rq->lock);
}

send_ipi(cpumask);

Quoted 6 lines

Good point, erring on the side of sending too many IPIs is safe. One might even be able to just send the full set if enough of the CPUs were running the current process and none of the remainder were running real-time threads. And yes, it would then be necessary to throttle calls to sys_membarrier().

If you need to throttle calls to sys_membarrier(), than why bother optimizing it? Again, this is like calling synchronize_sched() in the kernel, which is a very heavy operation, and should only be called by those that are not performance critical.

Why are we struggling so much with optimizing the slow path?

Here's how I take it. This method is much better that sending signals to all threads. The advantage the sys_membarrier gives us, is also a way to keep user rcu_read_locks barrier free, which means that rcu_read_locks are quick and scale well.

So what if we have a linear decrease in performance with the number of threads on the write side?

-- Steve

Quoted 21 lines · Paul E. McKenney

Quoted 5 lines · Steven Rostedt

Quoted 2 lines · Steven Rostedt

Then we should have O(tasks) for spinlocks taken, and O(min(tasks, CPUS)) for IPIs.

Quoted 14 lines

And for nr tasks >> CPUS, this may help too:

Quoted 2 lines

cpumask = 0;
foreach task {

	if (cpumask == online_cpus)
		break;

Quoted 6 lines

	spin_lock(task_rq(task)->rq->lock);
	if (task_rq(task)->curr == task)
		cpu_set(task_cpu(task), cpumask);
	spin_unlock(task_rq(task)->rq->lock);
}

send_ipi(cpumask);

Quoted 6 lines

Good point, erring on the side of sending too many IPIs is safe. One might even be able to just send the full set if enough of the CPUs were running the current process and none of the remainder were running real-time threads. And yes, it would then be necessary to throttle calls to sys_membarrier().

If you need to throttle calls to sys_membarrier(), than why bother optimizing it? Again, this is like calling synchronize_sched() in the kernel, which is a very heavy operation, and should only be called by those that are not performance critical.

Why are we struggling so much with optimizing the slow path?

Here's how I take it. This method is much better that sending signals to all threads. The advantage the sys_membarrier gives us, is also a way to keep user rcu_read_locks barrier free, which means that rcu_read_locks are quick and scale well.

So what if we have a linear decrease in performance with the number of threads on the write side?

-- Steve

Quoted 2 lines

So what if we have a linear decrease in performance with the number of threads on the write side?

Hrm, looking at arch/x86/include/asm/mmu_context.h

switch_mm(), which is basically called each time the scheduler needs to change the current task, does a

cpumask_clear_cpu(cpu, mm_cpumask(prev));

and

cpumask_set_cpu(cpu, mm_cpumask(next));

which precise goal is to stop the flush ipis for the previous mm. The 100$ question is : why do we have to confirm that the thread is indeed on the runqueue (taking locks and everything) when we could simply just bluntly use the mm_cpumask for our own IPIs ?

cpumask_clear_cpu and cpumask_set_cpu translate into clear_bit/set_bit. cpumask_next does a find_next_bit on the cpumask.

clear_bit/set_bit are atomic and not reordered on x86. PowerPC also uses ll/sc loops in bitops.h, so I think it should be pretty safe to assume that mm_cpumask is, by design, made to be used as cpumask to send a broadcast IPI to all CPUs which run threads belonging to a given process.

So, how about just using mm_cpumask(current) for the broadcast ? Then we don't even need to allocate our own cpumask neither.

Or am I missing something ? I just sounds too simple.

        CPU 1                           CPU 2
     -----------                    -------------

        <user space>                    <kernel space, switching to task>

                                        ->curr updated

                                        <long code path, maybe mb?>

                                        <user space>

                                        rcu_read_lock(); [load only]

                                        obj = list->next

        list_del(obj)

        sys_membarrier();

        < kernel space >

        if (task_rq(task)->curr != task)
        < but load to obj reordered before store to ->curr >

        < user space >

        < misses that CPU 2 is in rcu section >

        [CPU 2's ->curr update now visible]

        [CPU 2's rcu_read_lock() store now visible]

        free(obj);

                                        use_object(obj); <=== crash!

Quoted 36 lines · * Steven Rostedt ([email protected]) wrote:

Quoted 21 lines · Paul E. McKenney

Quoted 5 lines · Steven Rostedt

Quoted 2 lines · Steven Rostedt

Then we should have O(tasks) for spinlocks taken, and O(min(tasks, CPUS)) for IPIs.

Quoted 14 lines

And for nr tasks >> CPUS, this may help too:

Quoted 2 lines

cpumask = 0;
foreach task {

	if (cpumask == online_cpus)
		break;

Quoted 6 lines

	spin_lock(task_rq(task)->rq->lock);
	if (task_rq(task)->curr == task)
		cpu_set(task_cpu(task), cpumask);
	spin_unlock(task_rq(task)->rq->lock);
}

send_ipi(cpumask);

Quoted 6 lines

Good point, erring on the side of sending too many IPIs is safe. One might even be able to just send the full set if enough of the CPUs were running the current process and none of the remainder were running real-time threads. And yes, it would then be necessary to throttle calls to sys_membarrier().

If you need to throttle calls to sys_membarrier(), than why bother optimizing it? Again, this is like calling synchronize_sched() in the kernel, which is a very heavy operation, and should only be called by those that are not performance critical.

Why are we struggling so much with optimizing the slow path?

Quoted 7 lines

Here's how I take it. This method is much better that sending signals to all threads. The advantage the sys_membarrier gives us, is also a way to keep user rcu_read_locks barrier free, which means that rcu_read_locks are quick and scale well.

So what if we have a linear decrease in performance with the number of threads on the write side?

Hrm, looking at arch/x86/include/asm/mmu_context.h

switch_mm(), which is basically called each time the scheduler needs to change the current task, does a

cpumask_clear_cpu(cpu, mm_cpumask(prev));

and

cpumask_set_cpu(cpu, mm_cpumask(next));

which precise goal is to stop the flush ipis for the previous mm. The 100$ question is : why do we have to confirm that the thread is indeed on the runqueue (taking locks and everything) when we could simply just bluntly use the mm_cpumask for our own IPIs ?

cpumask_clear_cpu and cpumask_set_cpu translate into clear_bit/set_bit. cpumask_next does a find_next_bit on the cpumask.

clear_bit/set_bit are atomic and not reordered on x86. PowerPC also uses ll/sc loops in bitops.h, so I think it should be pretty safe to assume that mm_cpumask is, by design, made to be used as cpumask to send a broadcast IPI to all CPUs which run threads belonging to a given process.

So, how about just using mm_cpumask(current) for the broadcast ? Then we don't even need to allocate our own cpumask neither.

Or am I missing something ? I just sounds too simple.

Quoted 27 lines · * Paul E. McKenney ([email protected]) wrote:

Quoted 5 lines · Steven Rostedt

Quoted 2 lines · Steven Rostedt

Then we should have O(tasks) for spinlocks taken, and O(min(tasks, CPUS)) for IPIs.

Quoted 14 lines

And for nr tasks >> CPUS, this may help too:

Quoted 2 lines

cpumask = 0;
foreach task {

	if (cpumask == online_cpus)
		break;

Quoted 6 lines

	spin_lock(task_rq(task)->rq->lock);
	if (task_rq(task)->curr == task)
		cpu_set(task_cpu(task), cpumask);
	spin_unlock(task_rq(task)->rq->lock);
}

send_ipi(cpumask);

Good point, erring on the side of sending too many IPIs is safe. One might even be able to just send the full set if enough of the CPUs were running the current process and none of the remainder were running real-time threads. And yes, it would then be necessary to throttle calls to sys_membarrier().

Quoted 1 line

Quickly hiding behind a suitable boulder... ;-)

:)

One quick counter-argument against IPI-to-all: that will wake up all CPUs, including those which are asleep. Not really good for energy-saving.

Quoted 10 lines · Mathieu Desnoyers

Quoted 2 lines

So what if we have a linear decrease in performance with the number of threads on the write side?

Hrm, looking at arch/x86/include/asm/mmu_context.h

switch_mm(), which is basically called each time the scheduler needs to change the current task, does a

cpumask_clear_cpu(cpu, mm_cpumask(prev));

Quoted 8 lines

and

cpumask_set_cpu(cpu, mm_cpumask(next));

which precise goal is to stop the flush ipis for the previous mm. The 100$ question is : why do we have to confirm that the thread is indeed on the runqueue (taking locks and everything) when we could simply just bluntly use the mm_cpumask for our own IPIs ?

I was just looking at that code, and was thinking the same thing ;-)

Quoted 9 lines

cpumask_clear_cpu and cpumask_set_cpu translate into clear_bit/set_bit. cpumask_next does a find_next_bit on the cpumask.

clear_bit/set_bit are atomic and not reordered on x86. PowerPC also uses ll/sc loops in bitops.h, so I think it should be pretty safe to assume that mm_cpumask is, by design, made to be used as cpumask to send a broadcast IPI to all CPUs which run threads belonging to a given process.

Quoted 4 lines

So, how about just using mm_cpumask(current) for the broadcast ? Then we don't even need to allocate our own cpumask neither.

Or am I missing something ? I just sounds too simple.

I think we can use it. If for some reason it does not satisfy what you need then I also think the TLB flushing is also broken.

IIRC, (Paul help me out on this), what Paul said earlier, we are trying to protect against this scenario:

(from Paul's email:)

Quoted 24 lines

        CPU 1                           CPU 2
     -----------                    -------------

        <user space>                    <kernel space, switching to task>

                                        ->curr updated

                                        <long code path, maybe mb?>

                                        <user space>

                                        rcu_read_lock(); [load only]

                                        obj = list->next

        list_del(obj)

        sys_membarrier();
        < kernel space >

        if (task_rq(task)->curr != task)
        < but load to obj reordered before store to ->curr >

Quoted 3 lines

< user space >

< misses that CPU 2 is in rcu section >

If the TLB flush misses that CPU 2 has a threaded task, and does not flush CPU 2s TLB, it can also risk the same type of crash.

Quoted 8 lines

        [CPU 2's ->curr update now visible]

        [CPU 2's rcu_read_lock() store now visible]

        free(obj);

                                        use_object(obj); <=== crash!

Think about it. If you change a process mmap, say you updated a mmap of a file by flushing out one page and replacing it with another. If the above missed sending to CPU 2, then CPU 2 may still be accessing the old page of the file, and not the new one.

I think this may be the safe bet.

Quoted 7 lines · Steven Rostedt

Quoted 3 lines

< user space >

< misses that CPU 2 is in rcu section >

If the TLB flush misses that CPU 2 has a threaded task, and does not flush CPU 2s TLB, it can also risk the same type of crash.

But isn't the VM's locking helping us out in that case?

Quoted 14 lines

Quoted 8 lines

        [CPU 2's ->curr update now visible]

        [CPU 2's rcu_read_lock() store now visible]

        free(obj);

                                        use_object(obj); <=== crash!

Think about it. If you change a process mmap, say you updated a mmap of a file by flushing out one page and replacing it with another. If the above missed sending to CPU 2, then CPU 2 may still be accessing the old page of the file, and not the new one.

Quoted 1 line

I think this may be the safe bet.

You might well be correct that we can access that bitmap locklessly, but there are additional things (like the loading of the arch-specific page-table register) that are likely to be helping in the VM case, but not necessarily helping in this case.

Quoted 28 lines · Paul E. McKenney

Quoted 7 lines · Steven Rostedt

Quoted 3 lines

< user space >

< misses that CPU 2 is in rcu section >

If the TLB flush misses that CPU 2 has a threaded task, and does not flush CPU 2s TLB, it can also risk the same type of crash.

But isn't the VM's locking helping us out in that case?

Quoted 15 lines

Quoted 8 lines

        [CPU 2's ->curr update now visible]

        [CPU 2's rcu_read_lock() store now visible]

        free(obj);

                                        use_object(obj); <=== crash!

Think about it. If you change a process mmap, say you updated a mmap of a file by flushing out one page and replacing it with another. If the above missed sending to CPU 2, then CPU 2 may still be accessing the old page of the file, and not the new one.

I think this may be the safe bet.

Quoted 4 lines

You might well be correct that we can access that bitmap locklessly, but there are additional things (like the loading of the arch-specific page-table register) that are likely to be helping in the VM case, but not necessarily helping in this case.

Then perhaps the sys_membarrier() should just do a flush_tlb()? That should guarantee the synchronization, right?

* Steven Rostedt ([email protected]) wrote:

The way I see it, TLB can be seen as read-only elements (a local read-only cache) on the processors. Therefore, we don't care if they are in a stale state while performing the cpumask update, because the fact that we are executing switch_mm() means that these TLB entries are not being used locally anyway and will be dropped shortly. So we have the equivalent of a full memory barrier (load_cr3()) _after_ the cpumask updates.

However, in sys_membarrier(), we also need to flush the write buffers present on each processor running threads which belong to our current process. Therefore, we would need, in addition, a smp_mb() before the mm cpumask modification. For x86, cpumask_clear_cpu/cpumask_set_cpu implies a LOCK-prefixed operation, and hence does not need any added barrier, but this could be different for other architectures.

So, AFAIK, doing a flush_tlb() would not guarantee the kind of synchronization we are looking for because an uncommitted write buffer could still sit on the remote CPU when we return from sys_membarrier().

Quoted 17 lines · Mathieu Desnoyers

* Steven Rostedt ([email protected]) wrote:

The way I see it, TLB can be seen as read-only elements (a local read-only cache) on the processors. Therefore, we don't care if they are in a stale state while performing the cpumask update, because the fact that we are executing switch_mm() means that these TLB entries are not being used locally anyway and will be dropped shortly. So we have the equivalent of a full memory barrier (load_cr3()) _after_ the cpumask updates.

However, in sys_membarrier(), we also need to flush the write buffers present on each processor running threads which belong to our current process. Therefore, we would need, in addition, a smp_mb() before the mm cpumask modification. For x86, cpumask_clear_cpu/cpumask_set_cpu implies a LOCK-prefixed operation, and hence does not need any added barrier, but this could be different for other architectures.

Quoted 3 lines

So, AFAIK, doing a flush_tlb() would not guarantee the kind of synchronization we are looking for because an uncommitted write buffer could still sit on the remote CPU when we return from sys_membarrier().

Ah, so you are saying we can have this:

	CPU 0			CPU 1
     ----------		    --------------
	obj = list->obj;
				<user space>
				rcu_read_lock();
				obj = rcu_dereference(list->obj);
				obj->foo = bar;

				<preempt>
				<kernel space>

				schedule();
				cpumask_clear(mm_cpumask, cpu);

	sys_membarrier();
	free(obj);

				<store to obj->foo goes to memory>  <- corruption

So, if there's no smp_wmb() between the <preempt> and cpumask_clear() then we have an issue?

-- Steve

Quoted 28 lines · Paul E. McKenney

Quoted 7 lines · Steven Rostedt

Quoted 3 lines

< user space >

< misses that CPU 2 is in rcu section >

If the TLB flush misses that CPU 2 has a threaded task, and does not flush CPU 2s TLB, it can also risk the same type of crash.

But isn't the VM's locking helping us out in that case?

Quoted 15 lines

Quoted 8 lines

        [CPU 2's ->curr update now visible]

        [CPU 2's rcu_read_lock() store now visible]

        free(obj);

                                        use_object(obj); <=== crash!

Think about it. If you change a process mmap, say you updated a mmap of a file by flushing out one page and replacing it with another. If the above missed sending to CPU 2, then CPU 2 may still be accessing the old page of the file, and not the new one.

I think this may be the safe bet.

Quoted 4 lines

You might well be correct that we can access that bitmap locklessly, but there are additional things (like the loading of the arch-specific page-table register) that are likely to be helping in the VM case, but not necessarily helping in this case.

Then perhaps the sys_membarrier() should just do a flush_tlb()? That should guarantee the synchronization, right?

Quoted 34 lines · Steven Rostedt

Quoted 32 lines · Paul E. McKenney

Quoted 7 lines · Steven Rostedt

Quoted 3 lines

< user space >

< misses that CPU 2 is in rcu section >

If the TLB flush misses that CPU 2 has a threaded task, and does not flush CPU 2s TLB, it can also risk the same type of crash.

But isn't the VM's locking helping us out in that case?

Quoted 9 lines

Quoted 8 lines

        [CPU 2's ->curr update now visible]

        [CPU 2's rcu_read_lock() store now visible]

        free(obj);

                                        use_object(obj); <=== crash!

Quoted 6 lines

Think about it. If you change a process mmap, say you updated a mmap of a file by flushing out one page and replacing it with another. If the above missed sending to CPU 2, then CPU 2 may still be accessing the old page of the file, and not the new one.

I think this may be the safe bet.

You might well be correct that we can access that bitmap locklessly, but there are additional things (like the loading of the arch-specific page-table register) that are likely to be helping in the VM case, but not necessarily helping in this case.

Quoted 2 lines

Then perhaps the sys_membarrier() should just do a flush_tlb()? That should guarantee the synchronization, right?

Isn't just grabbing the runqueue locks a bit more straightforward and more clearly correct? Again, this is the URCU slowpath, so it is hard to get too excited about a 15% performance penalty.

Quoted 18 lines

	CPU 0			CPU 1
     ----------		    --------------
	obj = list->obj;
				<user space>
				rcu_read_lock();
				obj = rcu_dereference(list->obj);
				obj->foo = bar;

				<preempt>
				<kernel space>

				schedule();
				cpumask_clear(mm_cpumask, cpu);

	sys_membarrier();
	free(obj);

Quoted 2 lines

				<store to obj->foo goes to memory>  <- corruption

Hrm, having a writer like this in a rcu read-side would be a bit weird. We have to look at the actual rcu_read_lock() implementation in urcu to see why load/stores are important on the rcu read-side.

(note: _STORE_SHARED is simply a volatile store)

(Thread-local variable, shared with the thread doing synchronize_rcu()) struct urcu_reader __thread urcu_reader;

static inline void _rcu_read_lock(void)

{
        long tmp;

        tmp = urcu_reader.ctr;
        if (likely(!(tmp & RCU_GP_CTR_NEST_MASK))) {
                _STORE_SHARED(urcu_reader.ctr, _LOAD_SHARED(urcu_gp_ctr));
                /*
                 * Set active readers count for outermost nesting level before
                 * accessing the pointer. See force_mb_all_threads().
                 */
                barrier();
        } else {
                _STORE_SHARED(urcu_reader.ctr, tmp + RCU_GP_COUNT);
        }
}

So as you see here, we have to ensure that the store to urcu_reader.ctr is globally visible before entering the critical section (previous stores must complete before following loads). For rcu_read_unlock, it's the opposite:

static inline void _rcu_read_unlock(void)

{
        long tmp;

        tmp = urcu_reader.ctr;
        /*
         * Finish using rcu before decrementing the pointer.
         * See force_mb_all_threads().
         */
        if (likely((tmp & RCU_GP_CTR_NEST_MASK) == RCU_GP_COUNT)) {
                barrier();
                _STORE_SHARED(urcu_reader.ctr, urcu_reader.ctr - RCU_GP_COUNT);
        } else {
                _STORE_SHARED(urcu_reader.ctr, urcu_reader.ctr - RCU_GP_COUNT);
        }
}

We need to ensure that previous loads complete before following stores.

Therefore, the race with unlock showing that we need to order loads before stores:

	CPU 0			CPU 1
        --------------          --------------
                                <user space> (already in read-side C.S.)
                                obj = rcu_dereference(list->next);
                                  -> load list->next
                                copy = obj->foo;
                                rcu_read_unlock();
                                  -> store to urcu_reader.ctr
                                <urcu_reader.ctr store is globally visible>
        list_del(obj);
                                <preempt>
                                <kernel space>

                                schedule();
                                cpumask_clear(mm_cpumask, cpu);

        sys_membarrier();
        set global g.p. (urcu_gp_ctr) phase to 1
        wait for all urcu_reader.ctr in phase 0
        set global g.p. (urcu_gp_ctr) phase to 0
        wait for all urcu_reader.ctr in phase 1
        sys_membarrier();
        free(obj);
                                <list->next load hits memory>
                                <obj->foo load hits memory> <- corruption

Quoted 4 lines

So, if there's no smp_wmb() between the <preempt> and cpumask_clear() then we have an issue?

Considering the scenario above, we would need a full smp_mb() (or equivalent) rather than just smp_wmb() to be strictly correct.

Quoted 21 lines · Mathieu Desnoyers

Quoted 20 lines

	CPU 0			CPU 1
     ----------		    --------------
	obj = list->obj;
				<user space>
				rcu_read_lock();
				obj = rcu_dereference(list->obj);
				obj->foo = bar;

				<preempt>
				<kernel space>

				schedule();
				cpumask_clear(mm_cpumask, cpu);

	sys_membarrier();
	free(obj);

				<store to obj->foo goes to memory>  <- corruption

Quoted 4 lines

Hrm, having a writer like this in a rcu read-side would be a bit weird. We have to look at the actual rcu_read_lock() implementation in urcu to see why load/stores are important on the rcu read-side.

No it is not weird, it is common. The read is on the link list that we can access. Yes a write should be protected by other locks, so maybe that is the weird part.

Quoted 29 lines

(note: _STORE_SHARED is simply a volatile store)

(Thread-local variable, shared with the thread doing synchronize_rcu()) struct urcu_reader __thread urcu_reader;

static inline void _rcu_read_lock(void)

{
        long tmp;

        tmp = urcu_reader.ctr;
        if (likely(!(tmp & RCU_GP_CTR_NEST_MASK))) {
                _STORE_SHARED(urcu_reader.ctr, _LOAD_SHARED(urcu_gp_ctr));
                /*
                 * Set active readers count for outermost nesting level before
                 * accessing the pointer. See force_mb_all_threads().
                 */
                barrier();
        } else {
                _STORE_SHARED(urcu_reader.ctr, tmp + RCU_GP_COUNT);
        }
}

So as you see here, we have to ensure that the store to urcu_reader.ctr is globally visible before entering the critical section (previous stores must complete before following loads). For rcu_read_unlock, it's the opposite:

static inline void _rcu_read_unlock(void)

Quoted 15 lines

{
        long tmp;

        tmp = urcu_reader.ctr;
        /*
         * Finish using rcu before decrementing the pointer.
         * See force_mb_all_threads().
         */
        if (likely((tmp & RCU_GP_CTR_NEST_MASK) == RCU_GP_COUNT)) {
                barrier();
                _STORE_SHARED(urcu_reader.ctr, urcu_reader.ctr - RCU_GP_COUNT);
        } else {
                _STORE_SHARED(urcu_reader.ctr, urcu_reader.ctr - RCU_GP_COUNT);
        }
}

Thanks for the insight of the code. I need to get around and look at your userspace implementation ;-)

Quoted 19 lines

We need to ensure that previous loads complete before following stores.

Therefore, the race with unlock showing that we need to order loads before stores:

	CPU 0			CPU 1
        --------------          --------------
                                <user space> (already in read-side C.S.)
                                obj = rcu_dereference(list->next);
                                  -> load list->next
                                copy = obj->foo;
                                rcu_read_unlock();
                                  -> store to urcu_reader.ctr
                                <urcu_reader.ctr store is globally visible>
        list_del(obj);
                                <preempt>
                                <kernel space>

Quoted 2 lines

                                schedule();
                                cpumask_clear(mm_cpumask, cpu);

but here we are switching to a new task.

Quoted 11 lines

        sys_membarrier();
        set global g.p. (urcu_gp_ctr) phase to 1
        wait for all urcu_reader.ctr in phase 0
        set global g.p. (urcu_gp_ctr) phase to 0
        wait for all urcu_reader.ctr in phase 1
        sys_membarrier();
        free(obj);
                                <list->next load hits memory>
                                <obj->foo load hits memory> <- corruption

load of obj->foo is really load foo(obj) into some register. And for the above to fail, that means that this load happened even after we switched to kernel space, and that load of foo(obj) is still pending to get into the thread stack that saved that register.

But I'm sure Paul will point me to some arch that does this ;-)

Quoted 5 lines

Quoted 4 lines

So, if there's no smp_wmb() between the <preempt> and cpumask_clear() then we have an issue?

Quoted 2 lines

Considering the scenario above, we would need a full smp_mb() (or equivalent) rather than just smp_wmb() to be strictly correct.

I agree with Paul, we should just punt and grab the rq locks. That seems to be the safest way without resorting to funny tricks to save 15% on a slow path.

-- Steve

Quoted 38 lines · * Paul E. McKenney ([email protected]) wrote:

Quoted 36 lines · Steven Rostedt

Quoted 26 lines · Paul E. McKenney

Quoted 7 lines · Steven Rostedt

Quoted 3 lines

< user space >

< misses that CPU 2 is in rcu section >

If the TLB flush misses that CPU 2 has a threaded task, and does not flush CPU 2s TLB, it can also risk the same type of crash.

But isn't the VM's locking helping us out in that case?

Quoted 14 lines

Quoted 8 lines

        [CPU 2's ->curr update now visible]

        [CPU 2's rcu_read_lock() store now visible]

        free(obj);

                                        use_object(obj); <=== crash!

Think about it. If you change a process mmap, say you updated a mmap of a file by flushing out one page and replacing it with another. If the above missed sending to CPU 2, then CPU 2 may still be accessing the old page of the file, and not the new one.

Quoted 6 lines

Quoted 1 line

I think this may be the safe bet.

You might well be correct that we can access that bitmap locklessly, but there are additional things (like the loading of the arch-specific page-table register) that are likely to be helping in the VM case, but not necessarily helping in this case.

Then perhaps the sys_membarrier() should just do a flush_tlb()? That should guarantee the synchronization, right?

Quoted 3 lines

Isn't just grabbing the runqueue locks a bit more straightforward and more clearly correct? Again, this is the URCU slowpath, so it is hard to get too excited about a 15% performance penalty.

Even when taking the spinlocks, efficient iteration on active threads is done with for_each_cpu(cpu, mm_cpumask(current->mm)), which depends on the same cpumask, and thus requires the same memory barriers around the updates.

We could switch to an inefficient iteration on all online CPUs instead, and check read runqueue ->mm with the spinlock held. Is that what you propose ? This will cause reading of large amounts of runqueue information, especially on large systems running few threads. The other way around is to iterate on all the process threads: in this case, small systems running many threads will have to read information about many inactive threads, which is not much better.

Quoted 21 lines · Mathieu Desnoyers

Quoted 20 lines

	CPU 0			CPU 1
     ----------		    --------------
	obj = list->obj;
				<user space>
				rcu_read_lock();
				obj = rcu_dereference(list->obj);
				obj->foo = bar;

				<preempt>
				<kernel space>

				schedule();
				cpumask_clear(mm_cpumask, cpu);

	sys_membarrier();
	free(obj);

				<store to obj->foo goes to memory>  <- corruption

Quoted 3 lines

Hrm, having a writer like this in a rcu read-side would be a bit weird. We have to look at the actual rcu_read_lock() implementation in urcu to see why load/stores are important on the rcu read-side.

No it is not weird, it is common. The read is on the link list that we can access. Yes a write should be protected by other locks, so maybe that is the weird part.

Quoted 28 lines

(note: _STORE_SHARED is simply a volatile store)

(Thread-local variable, shared with the thread doing synchronize_rcu()) struct urcu_reader __thread urcu_reader;

static inline void _rcu_read_lock(void)

{
        long tmp;

        tmp = urcu_reader.ctr;
        if (likely(!(tmp & RCU_GP_CTR_NEST_MASK))) {
                _STORE_SHARED(urcu_reader.ctr, _LOAD_SHARED(urcu_gp_ctr));
                /*
                 * Set active readers count for outermost nesting level before
                 * accessing the pointer. See force_mb_all_threads().
                 */
                barrier();
        } else {
                _STORE_SHARED(urcu_reader.ctr, tmp + RCU_GP_COUNT);
        }
}

So as you see here, we have to ensure that the store to urcu_reader.ctr is globally visible before entering the critical section (previous stores must complete before following loads). For rcu_read_unlock, it's the opposite:

static inline void _rcu_read_unlock(void)

Quoted 15 lines

{
        long tmp;

        tmp = urcu_reader.ctr;
        /*
         * Finish using rcu before decrementing the pointer.
         * See force_mb_all_threads().
         */
        if (likely((tmp & RCU_GP_CTR_NEST_MASK) == RCU_GP_COUNT)) {
                barrier();
                _STORE_SHARED(urcu_reader.ctr, urcu_reader.ctr - RCU_GP_COUNT);
        } else {
                _STORE_SHARED(urcu_reader.ctr, urcu_reader.ctr - RCU_GP_COUNT);
        }
}

Thanks for the insight of the code. I need to get around and look at your userspace implementation ;-)

Quoted 6 lines

We need to ensure that previous loads complete before following stores.

Therefore, the race with unlock showing that we need to order loads before stores:

Quoted 15 lines

	CPU 0			CPU 1
        --------------          --------------
                                <user space> (already in read-side C.S.)
                                obj = rcu_dereference(list->next);
                                  -> load list->next
                                copy = obj->foo;
                                rcu_read_unlock();
                                  -> store to urcu_reader.ctr
                                <urcu_reader.ctr store is globally visible>
        list_del(obj);
                                <preempt>
                                <kernel space>

                                schedule();
                                cpumask_clear(mm_cpumask, cpu);

but here we are switching to a new task.

Quoted 10 lines

        sys_membarrier();
        set global g.p. (urcu_gp_ctr) phase to 1
        wait for all urcu_reader.ctr in phase 0
        set global g.p. (urcu_gp_ctr) phase to 0
        wait for all urcu_reader.ctr in phase 1
        sys_membarrier();
        free(obj);
                                <list->next load hits memory>
                                <obj->foo load hits memory> <- corruption

load of obj->foo is really load foo(obj) into some register. And for the above to fail, that means that this load happened even after we switched to kernel space, and that load of foo(obj) is still pending to get into the thread stack that saved that register.

But I'm sure Paul will point me to some arch that does this ;-)

Quoted 5 lines

Quoted 2 lines

So, if there's no smp_wmb() between the <preempt> and cpumask_clear() then we have an issue?

Considering the scenario above, we would need a full smp_mb() (or equivalent) rather than just smp_wmb() to be strictly correct.

I agree with Paul, we should just punt and grab the rq locks. That seems to be the safest way without resorting to funny tricks to save 15% on a slow path.

-- Steve

Quoted 4 lines

Even when taking the spinlocks, efficient iteration on active threads is done with for_each_cpu(cpu, mm_cpumask(current->mm)), which depends on the same cpumask, and thus requires the same memory barriers around the updates.

Ouch!!! Good point and good catch!!!

Quoted 7 lines

We could switch to an inefficient iteration on all online CPUs instead, and check read runqueue ->mm with the spinlock held. Is that what you propose ? This will cause reading of large amounts of runqueue information, especially on large systems running few threads. The other way around is to iterate on all the process threads: in this case, small systems running many threads will have to read information about many inactive threads, which is not much better.

I am not all that worried about exactly what we do as long as it is pretty obviously correct. We can then improve performance when and as the need arises. We might need to use any of the strategies you propose, or perhaps even choose among them depending on the number of threads in the process, the number of CPUs, and so forth. (I hope not, but...)

My guess is that an obviously correct approach would work well for a slowpath. If someone later runs into performance problems, we can fix them with the added knowledge of what they are trying to do.

* Paul E. McKenney ([email protected]) wrote:
[...]

Quoted 22 lines

Quoted 4 lines

Even when taking the spinlocks, efficient iteration on active threads is done with for_each_cpu(cpu, mm_cpumask(current->mm)), which depends on the same cpumask, and thus requires the same memory barriers around the updates.

Ouch!!! Good point and good catch!!!

Quoted 7 lines

We could switch to an inefficient iteration on all online CPUs instead, and check read runqueue ->mm with the spinlock held. Is that what you propose ? This will cause reading of large amounts of runqueue information, especially on large systems running few threads. The other way around is to iterate on all the process threads: in this case, small systems running many threads will have to read information about many inactive threads, which is not much better.

I am not all that worried about exactly what we do as long as it is pretty obviously correct. We can then improve performance when and as the need arises. We might need to use any of the strategies you propose, or perhaps even choose among them depending on the number of threads in the process, the number of CPUs, and so forth. (I hope not, but...)

Quoted 4 lines

My guess is that an obviously correct approach would work well for a slowpath. If someone later runs into performance problems, we can fix them with the added knowledge of what they are trying to do.

OK, here is what I propose. Let's choose between two implementations (v3a and v3b), which implement two "obviously correct" approaches. In summary:

* baseline (based on 2.6.32.2)
text data bss dec hex filename
76887 8782 2044 87713 156a1 kernel/sched.o

* v3a: ipi to many using mm_cpumask

- adds smp_mb__before_clear_bit()/smp_mb__after_clear_bit() before and after mm_cpumask stores in context_switch(). They are only executed when oldmm and mm are different. (it's my turn to hide behind an appropriately-sized boulder for touching the scheduler). ;) Note that it's not that bad, as these barriers turn into simple compiler barrier() on:
avr32, blackfin, cris, frb, h8300, m32r, m68k, mn10300, score, sh, sparc, x86 and xtensa.
The less lucky architectures gaining two smp_mb() are:
alpha, arm, ia64, mips, parisc, powerpc and s390.
ia64 is gaining only one smp_mb() thanks to its acquire semantic.
- size
text data bss dec hex filename
77239 8782 2044 88065 15801 kernel/sched.o
-> adds 352 bytes of text
- Number of lines (system call source code, w/o comments) : 18

* v3b: iteration on min(num_online_cpus(), nr threads in the process), taking runqueue spinlocks, allocating a cpumask, ipi to many to the cpumask. Does not allocate the cpumask if only a single IPI is needed.

- only adds sys_membarrier() and related functions.
- size
text data bss dec hex filename
78047 8782 2044 88873 15b29 kernel/sched.o
-> adds 1160 bytes of text
- Number of lines (system call source code, w/o comments) : 163

I'll reply to this email with the two implementations. Comments are welcome.

Here is an implementation of a new system call, sys_membarrier(), which executes a memory barrier on all threads of the current process.

It aims at greatly simplifying and enhancing the current signal-based liburcu userspace RCU synchronize_rcu() implementation. (found at http://lttng.org/urcu)

Changelog since v1:

- Only perform the IPI in CONFIG_SMP.
- Only perform the IPI if the process has more than one thread.
- Only send IPIs to CPUs involved with threads belonging to our process.
- Adaptative IPI scheme (single vs many IPI with threshold).
- Issue smp_mb() at the beginning and end of the system call.

Changelog since v2:
- simply send-to-many to the mm_cpumask. It contains the list of processors we have to IPI to (which use the mm), and this mask is updated atomically.

Both the signal-based and the sys_membarrier userspace RCU schemes permit us to remove the memory barrier from the userspace RCU rcu_read_lock() and rcu_read_unlock() primitives, thus significantly accelerating them. These memory barriers are replaced by compiler barriers on the read-side, and all matching memory barriers on the write-side are turned into an invokation of a memory barrier on all active threads in the process. By letting the kernel perform this synchronization rather than dumbly sending a signal to every process threads (as we currently do), we diminish the number of unnecessary wake ups and only issue the memory barriers on active threads. Non-running threads do not need to execute such barrier anyway, because these are implied by the scheduler context switches.

To explain the benefit of this scheme, let's introduce two example threads:

Thread A (non-frequent, e.g. executing liburcu synchronize_rcu()) Thread B (frequent, e.g. executing liburcu rcu_read_lock()/rcu_read_unlock())

In a scheme where all smp_mb() in thread A synchronize_rcu() are ordering memory accesses with respect to smp_mb() present in rcu_read_lock/unlock(), we can change all smp_mb() from synchronize_rcu() into calls to sys_membarrier() and all smp_mb() from rcu_read_lock/unlock() into compiler barriers "barrier()".

Before the change, we had, for each smp_mb() pairs:

Thread A                    Thread B
prev mem accesses           prev mem accesses
smp_mb()                    smp_mb()
follow mem accesses         follow mem accesses

After the change, these pairs become:

Thread A                    Thread B
prev mem accesses           prev mem accesses
sys_membarrier()            barrier()
follow mem accesses         follow mem accesses

As we can see, there are two possible scenarios: either Thread B memory accesses do not happen concurrently with Thread A accesses (1), or they do (2).

1) Non-concurrent Thread A vs Thread B accesses:

Thread A Thread B
prev mem accesses
sys_membarrier()
follow mem accesses
prev mem accesses
barrier()
follow mem accesses

In this case, thread B accesses will be weakly ordered. This is OK, because at that point, thread A is not particularly interested in ordering them with respect to its own accesses.

2) Concurrent Thread A vs Thread B accesses

Thread A                    Thread B
prev mem accesses           prev mem accesses
sys_membarrier()            barrier()
follow mem accesses         follow mem accesses

In this case, thread B accesses, which are ensured to be in program order thanks to the compiler barrier, will be "upgraded" to full smp_mb() thanks to the IPIs executing memory barriers on each active system threads. Each non-running process threads are intrinsically serialized by the scheduler.

For my Intel Xeon E5405 (new set of results, disabled kernel debugging)

T=1: 0m18.921s
T=2: 0m19.457s
T=3: 0m21.619s
T=4: 0m21.641s
T=5: 0m23.426s
T=6: 0m26.450s
T=7: 0m27.731s

The expected top pattern, when using 1 CPU for a thread doing sys_membarrier() in a loop and other threads busy-waiting in user-space on a variable shows that the thread doing sys_membarrier is doing mostly system calls, and other threads are mostly running in user-space. Side-note, in this test, it's important to check that individual threads are not always fully at 100% user-space time (they range between ~95% and 100%), because when some thread in the test is always at 100% on the same CPU, this means it does not get the IPI at all. (I actually found out about a bug in my own code while developing it with this test.)

Cpu0  :100.0%us,  0.0%sy,  0.0%ni,  0.0%id,  0.0%wa,  0.0%hi,  0.0%si,  0.0%st
Cpu1  : 99.7%us,  0.0%sy,  0.0%ni,  0.0%id,  0.0%wa,  0.3%hi,  0.0%si,  0.0%st
Cpu2  : 99.3%us,  0.0%sy,  0.0%ni,  0.0%id,  0.0%wa,  0.7%hi,  0.0%si,  0.0%st
Cpu3  :100.0%us,  0.0%sy,  0.0%ni,  0.0%id,  0.0%wa,  0.0%hi,  0.0%si,  0.0%st
Cpu4  :100.0%us,  0.0%sy,  0.0%ni,  0.0%id,  0.0%wa,  0.0%hi,  0.0%si,  0.0%st
Cpu5  : 96.0%us,  1.3%sy,  0.0%ni,  0.0%id,  0.0%wa,  0.0%hi,  2.6%si,  0.0%st
Cpu6  :  1.3%us, 98.7%sy,  0.0%ni,  0.0%id,  0.0%wa,  0.0%hi,  0.0%si,  0.0%st
Cpu7  : 96.1%us,  3.3%sy,  0.0%ni,  0.0%id,  0.0%wa,  0.3%hi,  0.3%si,  0.0%st

Results in liburcu:

Operations in 10s, 6 readers, 2 writers:

(what we previously had)
memory barriers in reader: 973494744 reads, 892368 writes
signal-based scheme: 6289946025 reads, 1251 writes

(what we have now, with dynamic sys_membarrier check) memory barriers in reader: 907693804 reads, 817793 writes
sys_membarrier scheme: 4061976535 reads, 526807 writes

So the dynamic sys_membarrier availability check adds some overhead to the read-side, but besides that, we can see that we are close to the read-side performance of the signal-based scheme and also close (5/8) to the performance of the memory-barrier write-side. We have a write-side speedup of 421:1 over the signal-based scheme by using the sys_membarrier system call. This allows a 4.5:1 read-side speedup over the memory barrier scheme.

The system call number is only assigned for x86_64 in this RFC patch.

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

CC "Paul E. McKenney" <[email protected]>

CC [email protected]

CC [email protected]

CC [email protected]

CC [email protected]

CC [email protected]

CC [email protected]

CC [email protected]

CC [email protected]

CC [email protected]

CC [email protected]

CC [email protected]

CC [email protected]

---
 arch/x86/include/asm/unistd_64.h |    2 +
 kernel/sched.c                   |   59 ++++++++++++++++++++++++++++++++++++++-
 2 files changed, 60 insertions(+), 1 deletion(-)

Index: linux-2.6-lttng/arch/x86/include/asm/unistd_64.h
===================================================================

arch/x86/include/asm/unistd_64.h +2 -0

@@ -661,6 +661,8 @@ __SYSCALL(__NR_pwritev, sys_pwritev)
 __SYSCALL(__NR_rt_tgsigqueueinfo, sys_rt_tgsigqueueinfo)
 #define __NR_perf_event_open			298
 __SYSCALL(__NR_perf_event_open, sys_perf_event_open)
+#define __NR_membarrier				299
+__SYSCALL(__NR_membarrier, sys_membarrier)
 
 #ifndef __NO_STUBS
 #define __ARCH_WANT_OLD_READDIR

Index: linux-2.6-lttng/kernel/sched.c
===================================================================

kernel/sched.c +58 -1

@@ -2861,12 +2861,26 @@ context_switch(struct rq *rq, struct tas
 	 */
 	arch_start_context_switch(prev);
 
+	/*
+	 * sys_membarrier IPI-mb scheme requires a memory barrier between
+	 * user-space thread execution and update to mm_cpumask.
+	 */
+	if (likely(oldmm) && likely(oldmm != mm))
+		smp_mb__before_clear_bit();
+
 	if (unlikely(!mm)) {
 		next->active_mm = oldmm;
 		atomic_inc(&oldmm->mm_count);
 		enter_lazy_tlb(oldmm, next);
-	} else
+	} else {
 		switch_mm(oldmm, mm, next);
+		/*
+		 * sys_membarrier IPI-mb scheme requires a memory barrier
+		 * between update to mm_cpumask and user-space thread execution.
+		 */
+		if (likely(oldmm != mm))
+			smp_mb__after_clear_bit();
+	}
 
 	if (unlikely(!prev->mm)) {
 		prev->active_mm = NULL;

@@ -10822,6 +10836,49 @@ struct cgroup_subsys cpuacct_subsys = {
 };
 #endif	/* CONFIG_CGROUP_CPUACCT */
 
+/*
+ * Execute a memory barrier on all active threads from the current process
+ * on SMP systems. Do not rely on implicit barriers in
+ * smp_call_function_many(), just in case they are ever relaxed in the future.
+ */
+static void membarrier_ipi(void *unused)
+{
+	smp_mb();
+}
+
+/*
+ * sys_membarrier - issue memory barrier on current process running threads
+ *
+ * Execute a memory barrier on all running threads of the current process.
+ * Upon completion, the caller thread is ensured that all process threads
+ * have passed through a state where memory accesses match program order.
+ * (non-running threads are de facto in such a state)
+ */
+SYSCALL_DEFINE0(membarrier)
+{
+#ifdef CONFIG_SMP
+	if (unlikely(thread_group_empty(current)))
+		return 0;
+	/*
+	 * Memory barrier on the caller thread _before_ sending first
+	 * IPI. Matches memory barriers around mm_cpumask modification in
+	 * context_switch().
+	 */
+	smp_mb();
+	preempt_disable();
+	smp_call_function_many(mm_cpumask(current->mm), membarrier_ipi,
+			       NULL, 1);
+	preempt_enable();
+	/*
+	 * Memory barrier on the caller thread _after_ we finished
+	 * waiting for the last IPI. Matches memory barriers around mm_cpumask
+	 * modification in context_switch().
+	 */
+	smp_mb();
+#endif	/* #ifdef CONFIG_SMP */
+	return 0;
+}
+
 #ifndef CONFIG_SMP
 
 int rcu_expedited_torture_stats(char *page)

Signature · 2 lines

Mathieu Desnoyers
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68

Quoted 6 lines · Mathieu Desnoyers

Here is an implementation of a new system call, sys_membarrier(), which executes a memory barrier on all threads of the current process.

It aims at greatly simplifying and enhancing the current signal-based liburcu userspace RCU synchronize_rcu() implementation. (found at http://lttng.org/urcu)

Given that this has the memory barrier both before and after the assignment to ->mm, looks good to me from a memory-ordering viewpoint. I must defer to others on the effect on context-switch overhead.

Thanx, Paul

Quoted 247 lines

Changelog since v1:

- Only perform the IPI in CONFIG_SMP.
- Only perform the IPI if the process has more than one thread.
- Only send IPIs to CPUs involved with threads belonging to our process.
- Adaptative IPI scheme (single vs many IPI with threshold).
- Issue smp_mb() at the beginning and end of the system call.

Changelog since v2:
- simply send-to-many to the mm_cpumask. It contains the list of processors we have to IPI to (which use the mm), and this mask is updated atomically.

Both the signal-based and the sys_membarrier userspace RCU schemes permit us to remove the memory barrier from the userspace RCU rcu_read_lock() and rcu_read_unlock() primitives, thus significantly accelerating them. These memory barriers are replaced by compiler barriers on the read-side, and all matching memory barriers on the write-side are turned into an invokation of a memory barrier on all active threads in the process. By letting the kernel perform this synchronization rather than dumbly sending a signal to every process threads (as we currently do), we diminish the number of unnecessary wake ups and only issue the memory barriers on active threads. Non-running threads do not need to execute such barrier anyway, because these are implied by the scheduler context switches.

To explain the benefit of this scheme, let's introduce two example threads:

Thread A (non-frequent, e.g. executing liburcu synchronize_rcu()) Thread B (frequent, e.g. executing liburcu rcu_read_lock()/rcu_read_unlock())

In a scheme where all smp_mb() in thread A synchronize_rcu() are ordering memory accesses with respect to smp_mb() present in rcu_read_lock/unlock(), we can change all smp_mb() from synchronize_rcu() into calls to sys_membarrier() and all smp_mb() from rcu_read_lock/unlock() into compiler barriers "barrier()".

Before the change, we had, for each smp_mb() pairs:

Thread A                    Thread B
prev mem accesses           prev mem accesses
smp_mb()                    smp_mb()
follow mem accesses         follow mem accesses

After the change, these pairs become:

Thread A                    Thread B
prev mem accesses           prev mem accesses
sys_membarrier()            barrier()
follow mem accesses         follow mem accesses

As we can see, there are two possible scenarios: either Thread B memory accesses do not happen concurrently with Thread A accesses (1), or they do (2).

1) Non-concurrent Thread A vs Thread B accesses:

Thread A Thread B
prev mem accesses
sys_membarrier()
follow mem accesses
prev mem accesses
barrier()
follow mem accesses

In this case, thread B accesses will be weakly ordered. This is OK, because at that point, thread A is not particularly interested in ordering them with respect to its own accesses.

2) Concurrent Thread A vs Thread B accesses

Thread A                    Thread B
prev mem accesses           prev mem accesses
sys_membarrier()            barrier()
follow mem accesses         follow mem accesses

In this case, thread B accesses, which are ensured to be in program order thanks to the compiler barrier, will be "upgraded" to full smp_mb() thanks to the IPIs executing memory barriers on each active system threads. Each non-running process threads are intrinsically serialized by the scheduler.

For my Intel Xeon E5405 (new set of results, disabled kernel debugging)

T=1: 0m18.921s
T=2: 0m19.457s
T=3: 0m21.619s
T=4: 0m21.641s
T=5: 0m23.426s
T=6: 0m26.450s
T=7: 0m27.731s

The expected top pattern, when using 1 CPU for a thread doing sys_membarrier() in a loop and other threads busy-waiting in user-space on a variable shows that the thread doing sys_membarrier is doing mostly system calls, and other threads are mostly running in user-space. Side-note, in this test, it's important to check that individual threads are not always fully at 100% user-space time (they range between ~95% and 100%), because when some thread in the test is always at 100% on the same CPU, this means it does not get the IPI at all. (I actually found out about a bug in my own code while developing it with this test.)

Cpu0  :100.0%us,  0.0%sy,  0.0%ni,  0.0%id,  0.0%wa,  0.0%hi,  0.0%si,  0.0%st
Cpu1  : 99.7%us,  0.0%sy,  0.0%ni,  0.0%id,  0.0%wa,  0.3%hi,  0.0%si,  0.0%st
Cpu2  : 99.3%us,  0.0%sy,  0.0%ni,  0.0%id,  0.0%wa,  0.7%hi,  0.0%si,  0.0%st
Cpu3  :100.0%us,  0.0%sy,  0.0%ni,  0.0%id,  0.0%wa,  0.0%hi,  0.0%si,  0.0%st
Cpu4  :100.0%us,  0.0%sy,  0.0%ni,  0.0%id,  0.0%wa,  0.0%hi,  0.0%si,  0.0%st
Cpu5  : 96.0%us,  1.3%sy,  0.0%ni,  0.0%id,  0.0%wa,  0.0%hi,  2.6%si,  0.0%st
Cpu6  :  1.3%us, 98.7%sy,  0.0%ni,  0.0%id,  0.0%wa,  0.0%hi,  0.0%si,  0.0%st
Cpu7  : 96.1%us,  3.3%sy,  0.0%ni,  0.0%id,  0.0%wa,  0.3%hi,  0.3%si,  0.0%st

Results in liburcu:

Operations in 10s, 6 readers, 2 writers:

(what we previously had)
memory barriers in reader: 973494744 reads, 892368 writes
signal-based scheme: 6289946025 reads, 1251 writes

(what we have now, with dynamic sys_membarrier check) memory barriers in reader: 907693804 reads, 817793 writes
sys_membarrier scheme: 4061976535 reads, 526807 writes

So the dynamic sys_membarrier availability check adds some overhead to the read-side, but besides that, we can see that we are close to the read-side performance of the signal-based scheme and also close (5/8) to the performance of the memory-barrier write-side. We have a write-side speedup of 421:1 over the signal-based scheme by using the sys_membarrier system call. This allows a 4.5:1 read-side speedup over the memory barrier scheme.

The system call number is only assigned for x86_64 in this RFC patch.

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

CC "Paul E. McKenney" <[email protected]>

CC [email protected]

CC [email protected]

CC [email protected]

CC [email protected]

CC [email protected]

CC [email protected]

CC [email protected]

CC [email protected]

CC [email protected]

CC [email protected]

CC [email protected]

CC [email protected]

---
 arch/x86/include/asm/unistd_64.h |    2 +
 kernel/sched.c                   |   59 ++++++++++++++++++++++++++++++++++++++-
 2 files changed, 60 insertions(+), 1 deletion(-)

Index: linux-2.6-lttng/arch/x86/include/asm/unistd_64.h
===================================================================

arch/x86/include/asm/unistd_64.h +2 -0

@@ -661,6 +661,8 @@ __SYSCALL(__NR_pwritev, sys_pwritev)
 __SYSCALL(__NR_rt_tgsigqueueinfo, sys_rt_tgsigqueueinfo)
 #define __NR_perf_event_open			298
 __SYSCALL(__NR_perf_event_open, sys_perf_event_open)
+#define __NR_membarrier				299
+__SYSCALL(__NR_membarrier, sys_membarrier)
 
 #ifndef __NO_STUBS
 #define __ARCH_WANT_OLD_READDIR

Index: linux-2.6-lttng/kernel/sched.c
===================================================================

kernel/sched.c +58 -1

@@ -2861,12 +2861,26 @@ context_switch(struct rq *rq, struct tas
 	 */
 	arch_start_context_switch(prev);
 
+	/*
+	 * sys_membarrier IPI-mb scheme requires a memory barrier between
+	 * user-space thread execution and update to mm_cpumask.
+	 */
+	if (likely(oldmm) && likely(oldmm != mm))
+		smp_mb__before_clear_bit();
+
 	if (unlikely(!mm)) {
 		next->active_mm = oldmm;
 		atomic_inc(&oldmm->mm_count);
 		enter_lazy_tlb(oldmm, next);
-	} else
+	} else {
 		switch_mm(oldmm, mm, next);
+		/*
+		 * sys_membarrier IPI-mb scheme requires a memory barrier
+		 * between update to mm_cpumask and user-space thread execution.
+		 */
+		if (likely(oldmm != mm))
+			smp_mb__after_clear_bit();
+	}
 
 	if (unlikely(!prev->mm)) {
 		prev->active_mm = NULL;

@@ -10822,6 +10836,49 @@ struct cgroup_subsys cpuacct_subsys = {
 };
 #endif	/* CONFIG_CGROUP_CPUACCT */
 
+/*
+ * Execute a memory barrier on all active threads from the current process
+ * on SMP systems. Do not rely on implicit barriers in
+ * smp_call_function_many(), just in case they are ever relaxed in the future.
+ */
+static void membarrier_ipi(void *unused)
+{
+	smp_mb();
+}
+
+/*
+ * sys_membarrier - issue memory barrier on current process running threads
+ *
+ * Execute a memory barrier on all running threads of the current process.
+ * Upon completion, the caller thread is ensured that all process threads
+ * have passed through a state where memory accesses match program order.
+ * (non-running threads are de facto in such a state)
+ */
+SYSCALL_DEFINE0(membarrier)
+{
+#ifdef CONFIG_SMP
+	if (unlikely(thread_group_empty(current)))
+		return 0;
+	/*
+	 * Memory barrier on the caller thread _before_ sending first
+	 * IPI. Matches memory barriers around mm_cpumask modification in
+	 * context_switch().
+	 */
+	smp_mb();
+	preempt_disable();
+	smp_call_function_many(mm_cpumask(current->mm), membarrier_ipi,
+			       NULL, 1);
+	preempt_enable();
+	/*
+	 * Memory barrier on the caller thread _after_ we finished
+	 * waiting for the last IPI. Matches memory barriers around mm_cpumask
+	 * modification in context_switch().
+	 */
+	smp_mb();
+#endif	/* #ifdef CONFIG_SMP */
+	return 0;
+}
+
 #ifndef CONFIG_SMP
 
 int rcu_expedited_torture_stats(char *page)

Signature · 2 lines

Mathieu Desnoyers
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68

Here is an implementation of a new system call, sys_membarrier(), which executes a memory barrier on all threads of the current process.

Index: linux-2.6-lttng/arch/x86/include/asm/unistd_64.h
===================================================================

arch/x86/include/asm/unistd_64.h +2 -0

@@ -661,6 +661,8 @@ __SYSCALL(__NR_pwritev, sys_pwritev)
 __SYSCALL(__NR_rt_tgsigqueueinfo, sys_rt_tgsigqueueinfo)
 #define __NR_perf_event_open			298
 __SYSCALL(__NR_perf_event_open, sys_perf_event_open)
+#define __NR_membarrier				299
+__SYSCALL(__NR_membarrier, sys_membarrier)
 
 #ifndef __NO_STUBS
 #define __ARCH_WANT_OLD_READDIR

Index: linux-2.6-lttng/kernel/sched.c
===================================================================

kernel/sched.c +51 -1

@@ -2861,12 +2861,26 @@ context_switch(struct rq *rq, struct tas
 	 */
 	arch_start_context_switch(prev);
 
+	/*
+	 * sys_membarrier IPI-mb scheme requires a memory barrier between
+	 * user-space thread execution and update to mm_cpumask.
+	 */
+	if (likely(oldmm) && likely(oldmm != mm))
+		smp_mb__before_clear_bit();
+
 	if (unlikely(!mm)) {
 		next->active_mm = oldmm;
 		atomic_inc(&oldmm->mm_count);
 		enter_lazy_tlb(oldmm, next);
-	} else
+	} else {
 		switch_mm(oldmm, mm, next);
+		/*
+		 * sys_membarrier IPI-mb scheme requires a memory barrier
+		 * between update to mm_cpumask and user-space thread execution.
+		 */
+		if (likely(oldmm != mm))
+			smp_mb__after_clear_bit();
+	}
 
 	if (unlikely(!prev->mm)) {
 		prev->active_mm = NULL;

@@ -10822,6 +10836,49 @@ struct cgroup_subsys cpuacct_subsys = {
 };
 #endif	/* CONFIG_CGROUP_CPUACCT */
 
+/*
+ * Execute a memory barrier on all active threads from the current process
+ * on SMP systems. Do not rely on implicit barriers in
+ * smp_call_function_many(), just in case they are ever relaxed in the future.
+ */
+static void membarrier_ipi(void *unused)
+{
+	smp_mb();
+}
+
+/*
+ * sys_membarrier - issue memory barrier on current process running threads
+ *
+ * Execute a memory barrier on all running threads of the current process.
+ * Upon completion, the caller thread is ensured that all process threads
+ * have passed through a state where memory accesses match program order.
+ * (non-running threads are de facto in such a state)
+ */
+SYSCALL_DEFINE0(membarrier)
+{
+#ifdef CONFIG_SMP
+	if (unlikely(thread_group_empty(current)))
+		return 0;
+	/*
+	 * Memory barrier on the caller thread _before_ sending first
+	 * IPI. Matches memory barriers around mm_cpumask modification in
+	 * context_switch().
+	 */
+	smp_mb();
+	preempt_disable();
+	smp_call_function_many(mm_cpumask(current->mm), membarrier_ipi,
+			       NULL, 1);
+	preempt_enable();
+	/*
+	 * Memory barrier on the caller thread _after_ we finished
+	 * waiting for the last IPI. Matches memory barriers around mm_cpumask

Quoted 67 lines · Mathieu Desnoyers

* Paul E. McKenney ([email protected]) wrote:
[...]

Quoted 22 lines

Quoted 4 lines

Even when taking the spinlocks, efficient iteration on active threads is done with for_each_cpu(cpu, mm_cpumask(current->mm)), which depends on the same cpumask, and thus requires the same memory barriers around the updates.

Ouch!!! Good point and good catch!!!

Quoted 7 lines

We could switch to an inefficient iteration on all online CPUs instead, and check read runqueue ->mm with the spinlock held. Is that what you propose ? This will cause reading of large amounts of runqueue information, especially on large systems running few threads. The other way around is to iterate on all the process threads: in this case, small systems running many threads will have to read information about many inactive threads, which is not much better.

I am not all that worried about exactly what we do as long as it is pretty obviously correct. We can then improve performance when and as the need arises. We might need to use any of the strategies you propose, or perhaps even choose among them depending on the number of threads in the process, the number of CPUs, and so forth. (I hope not, but...)

Quoted 4 lines

My guess is that an obviously correct approach would work well for a slowpath. If someone later runs into performance problems, we can fix them with the added knowledge of what they are trying to do.

OK, here is what I propose. Let's choose between two implementations (v3a and v3b), which implement two "obviously correct" approaches. In summary:

* baseline (based on 2.6.32.2)
text data bss dec hex filename
76887 8782 2044 87713 156a1 kernel/sched.o

* v3a: ipi to many using mm_cpumask

- adds smp_mb__before_clear_bit()/smp_mb__after_clear_bit() before and after mm_cpumask stores in context_switch(). They are only executed when oldmm and mm are different. (it's my turn to hide behind an appropriately-sized boulder for touching the scheduler). ;) Note that it's not that bad, as these barriers turn into simple compiler barrier() on:
avr32, blackfin, cris, frb, h8300, m32r, m68k, mn10300, score, sh, sparc, x86 and xtensa.
The less lucky architectures gaining two smp_mb() are:
alpha, arm, ia64, mips, parisc, powerpc and s390.
ia64 is gaining only one smp_mb() thanks to its acquire semantic.
- size
text data bss dec hex filename
77239 8782 2044 88065 15801 kernel/sched.o
-> adds 352 bytes of text
- Number of lines (system call source code, w/o comments) : 18

* v3b: iteration on min(num_online_cpus(), nr threads in the process), taking runqueue spinlocks, allocating a cpumask, ipi to many to the cpumask. Does not allocate the cpumask if only a single IPI is needed.

- only adds sys_membarrier() and related functions.
- size
text data bss dec hex filename
78047 8782 2044 88873 15b29 kernel/sched.o
-> adds 1160 bytes of text
- Number of lines (system call source code, w/o comments) : 163

Quoted 2 lines

I'll reply to this email with the two implementations. Comments are welcome.

Cool!!! Just for completeness, I point out the following trivial implementation:

/*
* sys_membarrier - issue memory barrier on current process running threads *
* Execute a memory barrier on all running threads of the current process.
* Upon completion, the caller thread is ensured that all process threads
* have passed through a state where memory accesses match program order.
* (non-running threads are de facto in such a state)
*
* Note that synchronize_sched() has the side-effect of doing a memory
* barrier on each CPU.
*/
SYSCALL_DEFINE0(membarrier)

{
	synchronize_sched();
}

This does unnecessarily hit all CPUs in the system, but has the same minimal impact that in-kernel RCU already has. It has long latency, (milliseconds) which might well disqualify it from consideration for some applications. On the other hand, it automatically batches multiple concurrent calls to sys_membarrier().

Thanx, Paul

Quoted 2 lines · Mathieu Desnoyers

Here is an implementation of a new system call, sys_membarrier(), which executes a memory barrier on all threads of the current process.

Please start a new thread for new versions, I really didn't find this until I started reading in date order instead of thread order.

Quoted 96 lines

Index: linux-2.6-lttng/arch/x86/include/asm/unistd_64.h
===================================================================

arch/x86/include/asm/unistd_64.h +2 -0

@@ -661,6 +661,8 @@ __SYSCALL(__NR_pwritev, sys_pwritev)
 __SYSCALL(__NR_rt_tgsigqueueinfo, sys_rt_tgsigqueueinfo)
 #define __NR_perf_event_open			298
 __SYSCALL(__NR_perf_event_open, sys_perf_event_open)
+#define __NR_membarrier				299
+__SYSCALL(__NR_membarrier, sys_membarrier)
 
 #ifndef __NO_STUBS
 #define __ARCH_WANT_OLD_READDIR

Index: linux-2.6-lttng/kernel/sched.c
===================================================================

kernel/sched.c +58 -1

@@ -2861,12 +2861,26 @@ context_switch(struct rq *rq, struct tas
 	 */
 	arch_start_context_switch(prev);
 
+	/*
+	 * sys_membarrier IPI-mb scheme requires a memory barrier between
+	 * user-space thread execution and update to mm_cpumask.
+	 */
+	if (likely(oldmm) && likely(oldmm != mm))
+		smp_mb__before_clear_bit();
+
 	if (unlikely(!mm)) {
 		next->active_mm = oldmm;
 		atomic_inc(&oldmm->mm_count);
 		enter_lazy_tlb(oldmm, next);
-	} else
+	} else {
 		switch_mm(oldmm, mm, next);
+		/*
+		 * sys_membarrier IPI-mb scheme requires a memory barrier
+		 * between update to mm_cpumask and user-space thread execution.
+		 */
+		if (likely(oldmm != mm))
+			smp_mb__after_clear_bit();
+	}
 
 	if (unlikely(!prev->mm)) {
 		prev->active_mm = NULL;

@@ -10822,6 +10836,49 @@ struct cgroup_subsys cpuacct_subsys = {
 };
 #endif	/* CONFIG_CGROUP_CPUACCT */
 
+/*
+ * Execute a memory barrier on all active threads from the current process
+ * on SMP systems. Do not rely on implicit barriers in
+ * smp_call_function_many(), just in case they are ever relaxed in the future.
+ */
+static void membarrier_ipi(void *unused)
+{
+	smp_mb();
+}
+
+/*
+ * sys_membarrier - issue memory barrier on current process running threads
+ *
+ * Execute a memory barrier on all running threads of the current process.
+ * Upon completion, the caller thread is ensured that all process threads
+ * have passed through a state where memory accesses match program order.
+ * (non-running threads are de facto in such a state)
+ */
+SYSCALL_DEFINE0(membarrier)
+{
+#ifdef CONFIG_SMP
+	if (unlikely(thread_group_empty(current)))
+		return 0;
+	/*
+	 * Memory barrier on the caller thread _before_ sending first
+	 * IPI. Matches memory barriers around mm_cpumask modification in
+	 * context_switch().
+	 */
+	smp_mb();
+	preempt_disable();
+	smp_call_function_many(mm_cpumask(current->mm), membarrier_ipi,
+			       NULL, 1);
+	preempt_enable();
+	/*
+	 * Memory barrier on the caller thread _after_ we finished
+	 * waiting for the last IPI. Matches memory barriers around mm_cpumask
+	 * modification in context_switch().
+	 */
+	smp_mb();
+#endif	/* #ifdef CONFIG_SMP */
+	return 0;
+}
+
 #ifndef CONFIG_SMP