introduce sys_membarrier(): process-wide memory barrier (v5)

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

kernel/sched.c +27 -0

@@ -10822,6 +10822,117 @@ struct cgroup_subsys cpuacct_subsys = {
 };
 #endif	/* CONFIG_CGROUP_CPUACCT */
 
+#ifdef CONFIG_SMP
+
+/*
+ * Execute a memory barrier on all active threads from the current process
+ * on SMP systems. Do not rely on implicit barriers in IPI handler execution,
+ * because batched IPI lists are synchronized with spinlocks rather than full
+ * memory barriers. This is not the bulk of the overhead anyway, so let's stay
+ * on the safe side.
+ */
+static void membarrier_ipi(void *unused)
+{
+	smp_mb();
+}
+
+/*
+ * Handle out-of-mem by sending per-cpu IPIs instead.
+ */
+static void membarrier_retry(void)
+{
+	struct mm_struct *mm;
+	int cpu;
+
+	for_each_cpu(cpu, mm_cpumask(current->mm)) {
+		spin_lock_irq(&cpu_rq(cpu)->lock);
+		mm = cpu_curr(cpu)->mm;
+		spin_unlock_irq(&cpu_rq(cpu)->lock);
+		if (current->mm == mm)

kernel/sched.c +27 -0

+ *
+ * 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)
+ *
+ * mm_cpumask is used as an approximation. It is a superset of the cpumask to
+ * which we must send IPIs, mainly due to lazy TLB shootdown. Therefore,
+ * we check each runqueue to make sure our ->mm is indeed running on them. This
+ * reduces the risk of disturbing a RT task by sending unnecessary IPIs. There
+ * is still a slight chance to disturb an unrelated task, because we do not lock
+ * the runqueues while sending IPIs, but the real-time effect of this heavy
+ * locking would be worse than the comparatively small disruption of an IPI.
+ *
+ * RED PEN: before assinging a system call number for sys_membarrier() to an
+ * architecture, we must ensure that switch_mm issues full memory barriers (or a
+ * synchronizing instruction having the same effect) between:
+ * - user-space code execution and clear mm_cpumask.
+ * - set mm_cpumask and user-space code execution.
+ * In some case adding a comment to this effect will suffice, in others we will
+ * need to add smp_mb__before_clear_bit()/smp_mb__after_clear_bit() or simply
+ * smp_mb(). These barriers are required to ensure we do not _miss_ a CPU that
+ * need to receive an IPI, which would be a bug.
+ *
+ * On uniprocessor systems, this system call simply returns 0 without doing
+ * anything, so user-space knows it is implemented.
+ */

kernel/sched.c +23 -0

+	cpumask_copy(tmpmask, mm_cpumask(current->mm));
+	preempt_disable();
+	cpumask_clear_cpu(smp_processor_id(), tmpmask);
+	for_each_cpu(cpu, tmpmask) {
+		spin_lock_irq(&cpu_rq(cpu)->lock);
+		mm = cpu_curr(cpu)->mm;
+		spin_unlock_irq(&cpu_rq(cpu)->lock);
+		if (current->mm != mm)
+			cpumask_clear_cpu(cpu, tmpmask);
+	}
+	smp_call_function_many(tmpmask, membarrier_ipi, NULL, 1);
+	preempt_enable();
+	free_cpumask_var(tmpmask);
+unlock:
+	/*
+	 * Memory barrier on the caller thread _after_ we finished
+	 * waiting for the last IPI. Matches memory barriers around mm_cpumask
+	 * modification in switch_mm().
+	 */
+	smp_mb();
+#endif /* #ifdef CONFIG_SMP */
+	return 0;
+}

Hi

Interesting patch :)

I have few comments.

Quoted 40 lines

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

kernel/sched.c +32 -0

@@ -10822,6 +10822,117 @@ struct cgroup_subsys cpuacct_subsys = {
 };
 #endif	/* CONFIG_CGROUP_CPUACCT */
 
+#ifdef CONFIG_SMP
+
+/*
+ * Execute a memory barrier on all active threads from the current process
+ * on SMP systems. Do not rely on implicit barriers in IPI handler execution,
+ * because batched IPI lists are synchronized with spinlocks rather than full
+ * memory barriers. This is not the bulk of the overhead anyway, so let's stay
+ * on the safe side.
+ */
+static void membarrier_ipi(void *unused)
+{
+	smp_mb();
+}
+
+/*
+ * Handle out-of-mem by sending per-cpu IPIs instead.
+ */
+static void membarrier_retry(void)
+{
+	struct mm_struct *mm;
+	int cpu;
+
+	for_each_cpu(cpu, mm_cpumask(current->mm)) {
+		spin_lock_irq(&cpu_rq(cpu)->lock);
+		mm = cpu_curr(cpu)->mm;
+		spin_unlock_irq(&cpu_rq(cpu)->lock);
+		if (current->mm == mm)
+			smp_call_function_single(cpu, membarrier_ipi, NULL, 1);
+	}
+}
+
+#endif /* #ifdef CONFIG_SMP */

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

Quoted 5 lines

kernel/sched.c +5 -0

+
+/*
+ * sys_membarrier - issue memory barrier on current process running threads
+ * @expedited: (0) Lowest overhead. Few milliseconds latency.
+ *             (1) Few microseconds latency.

Why do we need both expedited and non-expedited mode? at least, this documentation is bad. it suggest "you have to use non-expedited mode always!".

Quoted 33 lines

kernel/sched.c +31 -0

+ *
+ * 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)
+ *
+ * mm_cpumask is used as an approximation. It is a superset of the cpumask to
+ * which we must send IPIs, mainly due to lazy TLB shootdown. Therefore,
+ * we check each runqueue to make sure our ->mm is indeed running on them. This
+ * reduces the risk of disturbing a RT task by sending unnecessary IPIs. There
+ * is still a slight chance to disturb an unrelated task, because we do not lock
+ * the runqueues while sending IPIs, but the real-time effect of this heavy
+ * locking would be worse than the comparatively small disruption of an IPI.
+ *
+ * RED PEN: before assinging a system call number for sys_membarrier() to an
+ * architecture, we must ensure that switch_mm issues full memory barriers (or a
+ * synchronizing instruction having the same effect) between:
+ * - user-space code execution and clear mm_cpumask.
+ * - set mm_cpumask and user-space code execution.
+ * In some case adding a comment to this effect will suffice, in others we will
+ * need to add smp_mb__before_clear_bit()/smp_mb__after_clear_bit() or simply
+ * smp_mb(). These barriers are required to ensure we do not _miss_ a CPU that
+ * need to receive an IPI, which would be a bug.
+ *
+ * On uniprocessor systems, this system call simply returns 0 without doing
+ * anything, so user-space knows it is implemented.
+ */
+SYSCALL_DEFINE1(membarrier, int, expedited)
+{
+#ifdef CONFIG_SMP
+	cpumask_var_t tmpmask;

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

Quoted 6 lines

kernel/sched.c +6 -0

+	struct mm_struct *mm;
+	int cpu;
+
+	if (unlikely(thread_group_empty(current) || (num_online_cpus() == 1)))
+		return 0;
+	if (!unlikely(expedited)) {

unlikely(!expedited)?

Quoted 5 lines

kernel/sched.c +3 -0

+		synchronize_sched();
+		return 0;
+	}

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

Quoted 10 lines

kernel/sched.c +10 -0

+	/*
+	 * Memory barrier on the caller thread _before_ sending first
+	 * IPI. Matches memory barriers around mm_cpumask modification in
+	 * switch_mm().
+	 */
+	smp_mb();
+	if (!alloc_cpumask_var(&tmpmask, GFP_KERNEL)) {
+		membarrier_retry();
+		goto unlock;
+	}

if CONFIG_CPUMASK_OFFSTACK=1, alloc_cpumask_var call kmalloc. FWIW, kmalloc calling seems destory the worth of this patch.

#ifdef CONFIG_CPUMASK_OFFSTACK
	membarrier_retry();
	goto unlock;

#endif

is better? I'm not sure.

Quoted 25 lines

kernel/sched.c +23 -0

+	cpumask_copy(tmpmask, mm_cpumask(current->mm));
+	preempt_disable();
+	cpumask_clear_cpu(smp_processor_id(), tmpmask);
+	for_each_cpu(cpu, tmpmask) {
+		spin_lock_irq(&cpu_rq(cpu)->lock);
+		mm = cpu_curr(cpu)->mm;
+		spin_unlock_irq(&cpu_rq(cpu)->lock);
+		if (current->mm != mm)
+			cpumask_clear_cpu(cpu, tmpmask);
+	}
+	smp_call_function_many(tmpmask, membarrier_ipi, NULL, 1);
+	preempt_enable();
+	free_cpumask_var(tmpmask);
+unlock:
+	/*
+	 * Memory barrier on the caller thread _after_ we finished
+	 * waiting for the last IPI. Matches memory barriers around mm_cpumask
+	 * modification in switch_mm().
+	 */
+	smp_mb();
+#endif /* #ifdef CONFIG_SMP */
+	return 0;
+}

Quoted 46 lines

Hi

Interesting patch :)

I have few comments.

Quoted 40 lines

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

kernel/sched.c +32 -0

@@ -10822,6 +10822,117 @@ struct cgroup_subsys cpuacct_subsys = {
 };
 #endif	/* CONFIG_CGROUP_CPUACCT */
 
+#ifdef CONFIG_SMP
+
+/*
+ * Execute a memory barrier on all active threads from the current process
+ * on SMP systems. Do not rely on implicit barriers in IPI handler execution,
+ * because batched IPI lists are synchronized with spinlocks rather than full
+ * memory barriers. This is not the bulk of the overhead anyway, so let's stay
+ * on the safe side.
+ */
+static void membarrier_ipi(void *unused)
+{
+	smp_mb();
+}
+
+/*
+ * Handle out-of-mem by sending per-cpu IPIs instead.
+ */
+static void membarrier_retry(void)
+{
+	struct mm_struct *mm;
+	int cpu;
+
+	for_each_cpu(cpu, mm_cpumask(current->mm)) {
+		spin_lock_irq(&cpu_rq(cpu)->lock);
+		mm = cpu_curr(cpu)->mm;
+		spin_unlock_irq(&cpu_rq(cpu)->lock);
+		if (current->mm == mm)
+			smp_call_function_single(cpu, membarrier_ipi, NULL, 1);
+	}
+}
+
+#endif /* #ifdef CONFIG_SMP */

Quoted 8 lines

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

Quoted 5 lines

kernel/sched.c +5 -0

+
+/*
+ * sys_membarrier - issue memory barrier on current process running threads
+ * @expedited: (0) Lowest overhead. Few milliseconds latency.
+ *             (1) Few microseconds latency.

Why do we need both expedited and non-expedited mode? at least, this documentation is bad. it suggest "you have to use non-expedited mode always!".

Right. Maybe I should rather write:

+ * @expedited: (0) Low overhead, but slow execution (few milliseconds)
+ * (1) Slightly higher overhead, fast execution (few microseconds)

And I could probably go as far as adding a few paragraphs:

Using the non-expedited mode is recommended for applications which can afford leaving the caller thread waiting for a few milliseconds. A good example would be a thread dedicated to execute RCU callbacks, which waits for callbacks to enqueue most of the time anyway.

The expedited mode is recommended whenever the application needs to have control returning to the caller thread as quickly as possible. An example of such application would be one which uses the same thread to perform data structure updates and issue the RCU synchronization.

It is perfectly safe to call both expedited and non-expedited sys_membarriers in a process.

Does that help ?

Quoted 4 lines

Quoted 4 lines

kernel/sched.c +4 -0

+	 * Memory barrier on the caller thread _before_ sending first
+	 * IPI. Matches memory barriers around mm_cpumask modification in
+	 * switch_mm().
+	 */

Quoted 8 lines

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

Quoted 5 lines

kernel/sched.c +5 -0

+	smp_mb();
+	if (!alloc_cpumask_var(&tmpmask, GFP_KERNEL)) {
+		membarrier_retry();
+		goto unlock;
+	}

if CONFIG_CPUMASK_OFFSTACK=1, alloc_cpumask_var call kmalloc. FWIW, kmalloc calling seems destory the worth of this patch.

Why ? I'm not sure I understand your point. Even if we call kmalloc to allocate the cpumask, this is a constant overhead. The benefit of smp_call_function_many() over smp_call_function_single() is that it scales better by allowing to broadcast IPIs when the architecture supports it. Or maybe I'm missing something ?

Quoted 7 lines

#ifdef CONFIG_CPUMASK_OFFSTACK
	membarrier_retry();
	goto unlock;

#endif

is better? I'm not sure.

Thanks for the comments !

Mathieu

Quoted 77 lines · * KOSAKI Motohiro ([email protected]) wrote:

Quoted 46 lines

Hi

Interesting patch :)

I have few comments.

Quoted 40 lines

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

kernel/sched.c +32 -0

@@ -10822,6 +10822,117 @@ struct cgroup_subsys cpuacct_subsys = {
 };
 #endif	/* CONFIG_CGROUP_CPUACCT */
 
+#ifdef CONFIG_SMP
+
+/*
+ * Execute a memory barrier on all active threads from the current process
+ * on SMP systems. Do not rely on implicit barriers in IPI handler execution,
+ * because batched IPI lists are synchronized with spinlocks rather than full
+ * memory barriers. This is not the bulk of the overhead anyway, so let's stay
+ * on the safe side.
+ */
+static void membarrier_ipi(void *unused)
+{
+	smp_mb();
+}
+
+/*
+ * Handle out-of-mem by sending per-cpu IPIs instead.
+ */
+static void membarrier_retry(void)
+{
+	struct mm_struct *mm;
+	int cpu;
+
+	for_each_cpu(cpu, mm_cpumask(current->mm)) {
+		spin_lock_irq(&cpu_rq(cpu)->lock);
+		mm = cpu_curr(cpu)->mm;
+		spin_unlock_irq(&cpu_rq(cpu)->lock);
+		if (current->mm == mm)
+			smp_call_function_single(cpu, membarrier_ipi, NULL, 1);
+	}
+}
+
+#endif /* #ifdef CONFIG_SMP */

Quoted 8 lines

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

Quoted 5 lines

kernel/sched.c +5 -0

+
+/*
+ * sys_membarrier - issue memory barrier on current process running threads
+ * @expedited: (0) Lowest overhead. Few milliseconds latency.
+ *             (1) Few microseconds latency.

Why do we need both expedited and non-expedited mode? at least, this documentation is bad. it suggest "you have to use non-expedited mode always!".

Right. Maybe I should rather write:

+ * @expedited: (0) Low overhead, but slow execution (few milliseconds)
+ * (1) Slightly higher overhead, fast execution (few microseconds)

And I could probably go as far as adding a few paragraphs:

Using the non-expedited mode is recommended for applications which can afford leaving the caller thread waiting for a few milliseconds. A good example would be a thread dedicated to execute RCU callbacks, which waits for callbacks to enqueue most of the time anyway.

The expedited mode is recommended whenever the application needs to have control returning to the caller thread as quickly as possible. An example of such application would be one which uses the same thread to perform data structure updates and issue the RCU synchronization.

It is perfectly safe to call both expedited and non-expedited sys_membarriers in a process.

Quoted 1 line

Does that help ?

Do librcu need both? I bet average programmer don't understand this explanation. please recall, syscall interface are used by non kernel developers too. If librcu only use either (0) or (1), I hope remove another one.

But if librcu really need both, the above explanation is enough good. I think.

Quoted 13 lines

Quoted 4 lines

Quoted 4 lines

kernel/sched.c +4 -0

+	 * Memory barrier on the caller thread _before_ sending first
+	 * IPI. Matches memory barriers around mm_cpumask modification in
+	 * switch_mm().
+	 */

Quoted 8 lines

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

Quoted 5 lines

kernel/sched.c +5 -0

+	smp_mb();
+	if (!alloc_cpumask_var(&tmpmask, GFP_KERNEL)) {
+		membarrier_retry();
+		goto unlock;
+	}

if CONFIG_CPUMASK_OFFSTACK=1, alloc_cpumask_var call kmalloc. FWIW, kmalloc calling seems destory the worth of this patch.

Quoted 5 lines

Why ? I'm not sure I understand your point. Even if we call kmalloc to allocate the cpumask, this is a constant overhead. The benefit of smp_call_function_many() over smp_call_function_single() is that it scales better by allowing to broadcast IPIs when the architecture supports it. Or maybe I'm missing something ?

It depend on what mean "constant overhead". kmalloc might cause page reclaim and undeterministic delay. I'm not sure (1) How much membarrier_retry() slower than smp_call_function_many and (2) Which do you think important average or worst performance. Only I note I don't think GFP_KERNEL is constant overhead.

hmm...
Do you intend to GFP_ATOMIC?

Quoted 12 lines

Quoted 7 lines

#ifdef CONFIG_CPUMASK_OFFSTACK
	membarrier_retry();
	goto unlock;

#endif

is better? I'm not sure.

Thanks for the comments !

Mathieu

Quoted 1 line · * KOSAKI Motohiro ([email protected]) wrote:

Quoted 20 lines

Quoted 2 lines

Why do we need both expedited and non-expedited mode? at least, this documentation is bad. it suggest "you have to use non-expedited mode always!".

Right. Maybe I should rather write:

+ * @expedited: (0) Low overhead, but slow execution (few milliseconds)
+ * (1) Slightly higher overhead, fast execution (few microseconds)

And I could probably go as far as adding a few paragraphs:

Using the non-expedited mode is recommended for applications which can afford leaving the caller thread waiting for a few milliseconds. A good example would be a thread dedicated to execute RCU callbacks, which waits for callbacks to enqueue most of the time anyway.

The expedited mode is recommended whenever the application needs to have control returning to the caller thread as quickly as possible. An example of such application would be one which uses the same thread to perform data structure updates and issue the RCU synchronization.

Quoted 5 lines

It is perfectly safe to call both expedited and non-expedited sys_membarriers in a process.

Does that help ?

Do librcu need both? I bet average programmer don't understand this explanation. please recall, syscall interface are used by non kernel developers too. If librcu only use either (0) or (1), I hope remove another one.

But if librcu really need both, the above explanation is enough good. I think.

Quoted 15 lines

Quoted 14 lines

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

Quoted 11 lines

kernel/sched.c +9 -0

+	 * Memory barrier on the caller thread _before_ sending first
+	 * IPI. Matches memory barriers around mm_cpumask modification in
+	 * switch_mm().
+	 */
+	smp_mb();
+	if (!alloc_cpumask_var(&tmpmask, GFP_KERNEL)) {
+		membarrier_retry();
+		goto unlock;
+	}

if CONFIG_CPUMASK_OFFSTACK=1, alloc_cpumask_var call kmalloc. FWIW, kmalloc calling seems destory the worth of this patch.

Quoted 5 lines

Why ? I'm not sure I understand your point. Even if we call kmalloc to allocate the cpumask, this is a constant overhead. The benefit of smp_call_function_many() over smp_call_function_single() is that it scales better by allowing to broadcast IPIs when the architecture supports it. Or maybe I'm missing something ?

It depend on what mean "constant overhead". kmalloc might cause page reclaim and undeterministic delay. I'm not sure (1) How much membarrier_retry() slower than smp_call_function_many and (2) Which do you think important average or worst performance. Only I note I don't think GFP_KERNEL is constant overhead.

hmm...
Do you intend to GFP_ATOMIC?

Quoted 1 line

Quoted 1 line · * KOSAKI Motohiro ([email protected]) wrote:

[...]

Quoted 31 lines

Quoted 20 lines

Quoted 2 lines

Why do we need both expedited and non-expedited mode? at least, this documentation is bad. it suggest "you have to use non-expedited mode always!".

Right. Maybe I should rather write:

+ * @expedited: (0) Low overhead, but slow execution (few milliseconds)
+ * (1) Slightly higher overhead, fast execution (few microseconds)

And I could probably go as far as adding a few paragraphs:

Using the non-expedited mode is recommended for applications which can afford leaving the caller thread waiting for a few milliseconds. A good example would be a thread dedicated to execute RCU callbacks, which waits for callbacks to enqueue most of the time anyway.

The expedited mode is recommended whenever the application needs to have control returning to the caller thread as quickly as possible. An example of such application would be one which uses the same thread to perform data structure updates and issue the RCU synchronization.

Quoted 5 lines

It is perfectly safe to call both expedited and non-expedited sys_membarriers in a process.

Does that help ?

Do librcu need both? I bet average programmer don't understand this explanation. please recall, syscall interface are used by non kernel developers too. If librcu only use either (0) or (1), I hope remove another one.

Quoted 2 lines

But if librcu really need both, the above explanation is enough good. I think.

As Paul said, we need both in liburcu. These usage scenarios are explained in the system call documentation.

Quoted 19 lines

Quoted 13 lines

Quoted 4 lines

Quoted 4 lines

kernel/sched.c +4 -0

+	 * Memory barrier on the caller thread _before_ sending first
+	 * IPI. Matches memory barriers around mm_cpumask modification in
+	 * switch_mm().
+	 */

Quoted 8 lines

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

Quoted 5 lines

kernel/sched.c +5 -0

+	smp_mb();
+	if (!alloc_cpumask_var(&tmpmask, GFP_KERNEL)) {
+		membarrier_retry();
+		goto unlock;
+	}

if CONFIG_CPUMASK_OFFSTACK=1, alloc_cpumask_var call kmalloc. FWIW, kmalloc calling seems destory the worth of this patch.

Quoted 5 lines

Why ? I'm not sure I understand your point. Even if we call kmalloc to allocate the cpumask, this is a constant overhead. The benefit of smp_call_function_many() over smp_call_function_single() is that it scales better by allowing to broadcast IPIs when the architecture supports it. Or maybe I'm missing something ?

Quoted 5 lines

It depend on what mean "constant overhead". kmalloc might cause page reclaim and undeterministic delay. I'm not sure (1) How much membarrier_retry() slower than smp_call_function_many and (2) Which do you think important average or worst performance. Only I note I don't think GFP_KERNEL is constant overhead.

10,000,000 sys_membarrier calls (varying the number of threads to which we send IPIs), IPI-to-many, 8-core system:

T=1: 0m20.173s
T=2: 0m20.506s
T=3: 0m22.632s
T=4: 0m24.759s
T=5: 0m26.633s
T=6: 0m29.654s
T=7: 0m30.669s

Just doing local mb()+single IPI to T other threads:

T=1: 0m18.801s
T=2: 0m29.086s
T=3: 0m46.841s
T=4: 0m53.758s
T=5: 1m10.856s
T=6: 1m21.142s
T=7: 1m38.362s

So sending single IPIs adds about 1.5 microseconds per extra core. With the IPI-to-many scheme, we add about 0.2 microseconds per extra core. So we have a factor 10 gain in scalability. The initial cost of the cpumask allocation (which seems to be allocated on the stack in my config) is just about 1.4 microseconds. So here, we only have a small gain for the 1 IPI case, which does not justify the added complexity of dealing with it differently.

Also... it's pretty much a slow path anyway compared to the RCU read-side. I just don't want this slow path to scale badly.

Quoted 3 lines

hmm...
Do you intend to GFP_ATOMIC?

Would it help to lower the allocation overhead ?

Quoted 1 line · * KOSAKI Motohiro ([email protected]) wrote:

Quoted 27 lines

Quoted 5 lines

It depend on what mean "constant overhead". kmalloc might cause page reclaim and undeterministic delay. I'm not sure (1) How much membarrier_retry() slower than smp_call_function_many and (2) Which do you think important average or worst performance. Only I note I don't think GFP_KERNEL is constant overhead.

10,000,000 sys_membarrier calls (varying the number of threads to which we send IPIs), IPI-to-many, 8-core system:

T=1: 0m20.173s
T=2: 0m20.506s
T=3: 0m22.632s
T=4: 0m24.759s
T=5: 0m26.633s
T=6: 0m29.654s
T=7: 0m30.669s

Just doing local mb()+single IPI to T other threads:

T=1: 0m18.801s
T=2: 0m29.086s
T=3: 0m46.841s
T=4: 0m53.758s
T=5: 1m10.856s
T=6: 1m21.142s
T=7: 1m38.362s

Quoted 7 lines

So sending single IPIs adds about 1.5 microseconds per extra core. With the IPI-to-many scheme, we add about 0.2 microseconds per extra core. So we have a factor 10 gain in scalability. The initial cost of the cpumask allocation (which seems to be allocated on the stack in my config) is just about 1.4 microseconds. So here, we only have a small gain for the 1 IPI case, which does not justify the added complexity of dealing with it differently.

I'd like to discuss to separate CONFIG_CPUMASK_OFFSTACK=1 and CONFIG_CPUMASK_OFFSTACK=0.

CONFIG_CPUMASK_OFFSTACK=0 (your config)
- cpumask is allocated on stask
- alloc_cpumask_var() is nop (yes, nop is constant overhead ;)
- alloc_cpumask_var() always return 1, then membarrier_retry() is never called.
- alloc_cpumask_var() ignore GFP_KERNEL parameter

CONFIG_CPUMASK_OFFSTACK=1 and use GFP_KERNEL
- cpumask is allocated on heap
- alloc_cpumask_var() is the wrapper of kmalloc()
- GFP_KERNEL parameter is passed kmalloc
- GFP_KERNEL mean alloc_cpumask_var() always return 1, except oom-killer case. IOW, membarrier_retry() is still never called on typical use case.
- kmalloc(GFP_KERNEL) might invoke page reclaim and it can spent few seconds (not microseconds).

CONFIG_CPUMASK_OFFSTACK=1 and use GFP_ATOMIC
- cpumask is allocated on heap
- alloc_cpumask_var() is the wrapper of kmalloc()
- GFP_ATOMIC mean kmalloc never invoke page reclaim. IOW, kmalloc() cost is nearly constant. (few or lots microseconds)
- OTOH, alloc_cpumask_var() might fail, at that time membarrier_retry() is called.

So, My last mail talked about CONFIG_CPUMASK_OFFSTACK=1, but you mesured CONFIG_CPUMASK_OFFSTACK=0. That's the reason why our conclusion is different.

Quoted 6 lines

Also... it's pretty much a slow path anyway compared to the RCU read-side. I just don't want this slow path to scale badly.

Quoted 1 line

Quoted 4 lines

Quoted 2 lines

hmm...
Do you intend to GFP_ATOMIC?

Would it help to lower the allocation overhead ?

No. If the system have lots free memory, GFP_ATOMIC and GFP_KERNEL don't have any difference. but if the system have no free memory, GFP_KERNEL might cause big latency.

Perhaps, It is no big issue. If the system have no free memory, another syscall will invoke page reclaim soon although sys_membarrier avoid it. I'm not sure. It depend on librcu latency policy.

Another alternative plan is,

	if (!alloc_cpumask_var(&tmpmask, GFP_KERNEL)) {
		err = -ENOMEM;
		goto unlock;
	}

and kill membarrier_retry(). because CONFIG_CPUMASK_OFFSTACK=1 is only used for SGI big hpc machine, it mean nobody can test membarrier_retry(). Never called function doesn't have lots worth.

Thought?

Quoted 1 line

Quoted 1 line · * KOSAKI Motohiro ([email protected]) wrote:

[...]

Quoted 61 lines

Quoted 27 lines

Quoted 5 lines

It depend on what mean "constant overhead". kmalloc might cause page reclaim and undeterministic delay. I'm not sure (1) How much membarrier_retry() slower than smp_call_function_many and (2) Which do you think important average or worst performance. Only I note I don't think GFP_KERNEL is constant overhead.

10,000,000 sys_membarrier calls (varying the number of threads to which we send IPIs), IPI-to-many, 8-core system:

T=1: 0m20.173s
T=2: 0m20.506s
T=3: 0m22.632s
T=4: 0m24.759s
T=5: 0m26.633s
T=6: 0m29.654s
T=7: 0m30.669s

Just doing local mb()+single IPI to T other threads:

T=1: 0m18.801s
T=2: 0m29.086s
T=3: 0m46.841s
T=4: 0m53.758s
T=5: 1m10.856s
T=6: 1m21.142s
T=7: 1m38.362s

Quoted 7 lines

So sending single IPIs adds about 1.5 microseconds per extra core. With the IPI-to-many scheme, we add about 0.2 microseconds per extra core. So we have a factor 10 gain in scalability. The initial cost of the cpumask allocation (which seems to be allocated on the stack in my config) is just about 1.4 microseconds. So here, we only have a small gain for the 1 IPI case, which does not justify the added complexity of dealing with it differently.

I'd like to discuss to separate CONFIG_CPUMASK_OFFSTACK=1 and CONFIG_CPUMASK_OFFSTACK=0.

CONFIG_CPUMASK_OFFSTACK=0 (your config)
- cpumask is allocated on stask
- alloc_cpumask_var() is nop (yes, nop is constant overhead ;)
- alloc_cpumask_var() always return 1, then membarrier_retry() is never called.
- alloc_cpumask_var() ignore GFP_KERNEL parameter

CONFIG_CPUMASK_OFFSTACK=1 and use GFP_KERNEL
- cpumask is allocated on heap
- alloc_cpumask_var() is the wrapper of kmalloc()
- GFP_KERNEL parameter is passed kmalloc
- GFP_KERNEL mean alloc_cpumask_var() always return 1, except oom-killer case. IOW, membarrier_retry() is still never called on typical use case.
- kmalloc(GFP_KERNEL) might invoke page reclaim and it can spent few seconds (not microseconds).

CONFIG_CPUMASK_OFFSTACK=1 and use GFP_ATOMIC
- cpumask is allocated on heap
- alloc_cpumask_var() is the wrapper of kmalloc()
- GFP_ATOMIC mean kmalloc never invoke page reclaim. IOW, kmalloc() cost is nearly constant. (few or lots microseconds)
- OTOH, alloc_cpumask_var() might fail, at that time membarrier_retry() is called.

Quoted 2 lines

So, My last mail talked about CONFIG_CPUMASK_OFFSTACK=1, but you mesured CONFIG_CPUMASK_OFFSTACK=0. That's the reason why our conclusion is different.

I would have to put my system in OOM condition anyway to measure the page reclaim overhead. Given that sys_membarrier is not exactly a fast path, I don't think it matters _that much_.

Hrm. Well, given the "expedited" nature of the system call, it might come as a surprise to have to wait for page reclaim, and surprises are not good. OTOH, I don't want to allow users to easily consume all the GFP_ATOMIC pool. But I think it's unlikely, as we are bounded by the number of processors which can concurrently run sys_membarrier().

+ * sys_membarrier - issue memory barrier on current process running threads
+ * @expedited: (0) Lowest overhead. Few milliseconds latency.
+ * (1) Few microseconds latency.
+ *

Quoted 4 lines · Mathieu Desnoyers

+ * sys_membarrier - issue memory barrier on current process running threads
+ * @expedited: (0) Lowest overhead. Few milliseconds latency.
+ * (1) Few microseconds latency.
+ *

Alternate ABI proposal, keeping the possibility of future expansion in mind:

/*
Mandatory flags to the membarrier system call that the kernel must understand are in the high 16 bits.
*/
#define MEMBARRIER_MANDATORY_MASK 0xFFFF0000

/*
Optional hints that the kernel can ignore are in the low 16 bits. */
#define MEMBARRIER_OPTIONAL_MASK 0x0000FFFF

#define MEMBARRIER_EXPEDITED 1

extern int membarrier(unsigned int flags);

And then add to the system call itself:

if ((flags & MEMBARRIER_MANDATORY_MASK) != 0)

	return -EINVAL;

Why is it OK to ignore the developer's request for an expedited membarrer()? The guy who expected the syscall to complete in a few microseconds might not be so happy to have it take many milliseconds. By the same token, the guy who specified non-expedited so as to minimally disturb other threads in the system might not be so happy to see them all be IPIed for no good reason. ;-)

Thanx, Paul

Quoted 7 lines · Paul E. McKenney

Why is it OK to ignore the developer's request for an expedited membarrer()? The guy who expected the syscall to complete in a few microseconds might not be so happy to have it take many milliseconds. By the same token, the guy who specified non-expedited so as to minimally disturb other threads in the system might not be so happy to see them all be IPIed for no good reason. ;-)

Quoted 1 line

Thanx, Paul

Because the behavior is still correct, even if it is slower than you'd expect. It doesn't really matter where the expedited flag goes, though, because every future kernel will understand it.

Signature · 2 lines

-- 
Nicholas Miell <[email protected]>

Quoted 8 lines · * Nicholas Miell ([email protected]) wrote:

Quoted 7 lines · Paul E. McKenney

Why is it OK to ignore the developer's request for an expedited membarrer()? The guy who expected the syscall to complete in a few microseconds might not be so happy to have it take many milliseconds. By the same token, the guy who specified non-expedited so as to minimally disturb other threads in the system might not be so happy to see them all be IPIed for no good reason. ;-)

Quoted 5 lines

Quoted 1 line

Thanx, Paul

Because the behavior is still correct, even if it is slower than you'd expect. It doesn't really matter where the expedited flag goes, though, because every future kernel will understand it.

16ms vs few µs is such a huge performance difference that it's barely adequate to say that the behavior is still correct, but we definitely cannot say it is unchanged. It can really render some applications unusable.

If, for some reason, the expedited version of the system call happens to be unimplemented, we should return -EINVAL, so the application can deal with it in the approproate way (which could be, for instance, to use a fall-back doing memory barriers on the RCU read-side).

But I don't see any reason for not implementing the expedited version properly in the first place.

Quoted 20 lines · Mathieu Desnoyers

Quoted 8 lines · * Nicholas Miell ([email protected]) wrote:

Quoted 7 lines · Paul E. McKenney

Why is it OK to ignore the developer's request for an expedited membarrer()? The guy who expected the syscall to complete in a few microseconds might not be so happy to have it take many milliseconds. By the same token, the guy who specified non-expedited so as to minimally disturb other threads in the system might not be so happy to see them all be IPIed for no good reason. ;-)

Quoted 5 lines

Quoted 1 line

Thanx, Paul

Because the behavior is still correct, even if it is slower than you'd expect. It doesn't really matter where the expedited flag goes, though, because every future kernel will understand it.

16ms vs few µs is such a huge performance difference that it's barely adequate to say that the behavior is still correct, but we definitely cannot say it is unchanged. It can really render some applications unusable.

Quoted 8 lines

If, for some reason, the expedited version of the system call happens to be unimplemented, we should return -EINVAL, so the application can deal with it in the approproate way (which could be, for instance, to use a fall-back doing memory barriers on the RCU read-side).

But I don't see any reason for not implementing the expedited version properly in the first place.

You're focusing on the least important detail of the proposal. It doesn't matter whether the expedited flag is compat flag or an incompat flag, because every version of kernel that ever has the membarrier system call will know what it means, and even if for some reason it doesn't implement expedited membarriers, it will still be able to recognize the flag and return an error.

The whole point of compat and incompat flags is that it allows new applications to run on old kernels and either work or fail as appropriate, depending on whether the new features they're using must be implemented or can be silently ignored.

Signature · 2 lines

-- 
Nicholas Miell <[email protected]>

Quoted 4 lines · * Nicholas Miell ([email protected]) wrote:

The whole point of compat and incompat flags is that it allows new applications to run on old kernels and either work or fail as appropriate, depending on whether the new features they're using must be implemented or can be silently ignored.

I see. Thanks for the explanation. Then the expedited flag should clearly be part of the mandatory flags.

Can you point me to other system calls that are doing this ?

Thanks,

Mathieu

Quoted 10 lines · Mathieu Desnoyers

Quoted 4 lines · * Nicholas Miell ([email protected]) wrote:

The whole point of compat and incompat flags is that it allows new applications to run on old kernels and either work or fail as appropriate, depending on whether the new features they're using must be implemented or can be silently ignored.

I see. Thanks for the explanation. Then the expedited flag should clearly be part of the mandatory flags.

Quoted 5 lines

Can you point me to other system calls that are doing this ?

Thanks,

Mathieu

Not off the top of my head, but I did steal the idea from the ext2/3/4 disk format.

Quoted 15 lines · * Nicholas Miell ([email protected]) wrote:

Quoted 14 lines · Mathieu Desnoyers

Quoted 4 lines · * Nicholas Miell ([email protected]) wrote:

The whole point of compat and incompat flags is that it allows new applications to run on old kernels and either work or fail as appropriate, depending on whether the new features they're using must be implemented or can be silently ignored.

I see. Thanks for the explanation. Then the expedited flag should clearly be part of the mandatory flags.

Can you point me to other system calls that are doing this ?

Thanks,

Mathieu

Quoted 2 lines

Not off the top of my head, but I did steal the idea from the ext2/3/4 disk format.

Sounds a bit over-engineered to me for system calls, but who knows if we eventually have to extend sys_membarrier(). This involves that, right now, I'd have to add a header to include/linux to define these flags. Also, "int expedited" is a bit clearer, but less flexible, than "int flags". Anyone else have comments about this ?

Quoted 16 lines · Mathieu Desnoyers

Quoted 15 lines · * Nicholas Miell ([email protected]) wrote:

Quoted 14 lines · Mathieu Desnoyers

Quoted 4 lines · * Nicholas Miell ([email protected]) wrote:

The whole point of compat and incompat flags is that it allows new applications to run on old kernels and either work or fail as appropriate, depending on whether the new features they're using must be implemented or can be silently ignored.

I see. Thanks for the explanation. Then the expedited flag should clearly be part of the mandatory flags.

Can you point me to other system calls that are doing this ?

Thanks,

Mathieu

Quoted 9 lines

Quoted 2 lines

Not off the top of my head, but I did steal the idea from the ext2/3/4 disk format.

Sounds a bit over-engineered to me for system calls, but who knows if we eventually have to extend sys_membarrier(). This involves that, right now, I'd have to add a header to include/linux to define these flags. Also, "int expedited" is a bit clearer, but less flexible, than "int flags". Anyone else have comments about this ?

It doesn't bother me that you have to do extra work to add the flag definitions to a header file. :-)

As I understand it, the proposal is to have the option to extend the ABI based on as yet undefined flag bits. This doesn't seem like a bad thing.

The runtime overhead of testing a single bit vs. non-zero in the parameter shouldn't be an issue.

Quoted 27 lines · David Daney

Quoted 25 lines · Mathieu Desnoyers

Quoted 10 lines · * Nicholas Miell ([email protected]) wrote:

Quoted 9 lines · Mathieu Desnoyers

Quoted 4 lines · * Nicholas Miell ([email protected]) wrote:

The whole point of compat and incompat flags is that it allows new applications to run on old kernels and either work or fail as appropriate, depending on whether the new features they're using must be implemented or can be silently ignored.

I see. Thanks for the explanation. Then the expedited flag should clearly be part of the mandatory flags.

Quoted 7 lines

Quoted 5 lines

Can you point me to other system calls that are doing this ?

Thanks,

Mathieu

Not off the top of my head, but I did steal the idea from the ext2/3/4 disk format.

Sounds a bit over-engineered to me for system calls, but who knows if we eventually have to extend sys_membarrier(). This involves that, right now, I'd have to add a header to include/linux to define these flags. Also, "int expedited" is a bit clearer, but less flexible, than "int flags". Anyone else have comments about this ?

Quoted 3 lines

It doesn't bother me that you have to do extra work to add the flag definitions to a header file. :-)

Quoted 6 lines

As I understand it, the proposal is to have the option to extend the ABI based on as yet undefined flag bits. This doesn't seem like a bad thing.

The runtime overhead of testing a single bit vs. non-zero in the parameter shouldn't be an issue.

The recent introduction of accept4(), signalfd4(), eventfd2(), epoll_create1(), dup3(), pipe2(), and inotify_init1() suggest that this is the kind of thing you want to plan for, because you're probably going to end up doing it anyway.

Signature · 2 lines

-- 
Nicholas Miell <[email protected]>

Quoted 7 lines · Paul E. McKenney

Why is it OK to ignore the developer's request for an expedited membarrer()? The guy who expected the syscall to complete in a few microseconds might not be so happy to have it take many milliseconds. By the same token, the guy who specified non-expedited so as to minimally disturb other threads in the system might not be so happy to see them all be IPIed for no good reason. ;-)

Quoted 1 line

Thanx, Paul

Because the behavior is still correct, even if it is slower than you'd expect. It doesn't really matter where the expedited flag goes, though, because every future kernel will understand it.

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

Quoted 12 lines · Mathieu Desnoyers

kernel/sched.c +12 -0

+static void membarrier_retry(void)
+{
+	struct mm_struct *mm;
+	int cpu;
+
+	for_each_cpu(cpu, mm_cpumask(current->mm)) {
+		spin_lock_irq(&cpu_rq(cpu)->lock);
+		mm = cpu_curr(cpu)->mm;
+		spin_unlock_irq(&cpu_rq(cpu)->lock);
+		if (current->mm == mm)
+			smp_call_function_single(cpu, membarrier_ipi, NULL, 1);
+	}

You would need to disable cpu unplug operations while doing this or you might end up sending IPIs to offline cpus.

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

Quoted 7 lines

kernel/sched.c +6 -0

+	cpumask_copy(tmpmask, mm_cpumask(current->mm));
+	preempt_disable();
+	cpumask_clear_cpu(smp_processor_id(), tmpmask);
+	for_each_cpu(cpu, tmpmask) {
+		spin_lock_irq(&cpu_rq(cpu)->lock);
+		mm = cpu_curr(cpu)->mm;

This might access the rq of an offline cpu. But maybe it's intended since offline cpus "run" idle?

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

Quoted 7 lines · Mathieu Desnoyers

kernel/sched.c +7 -0

+       for_each_cpu(cpu, tmpmask) {
+               spin_lock_irq(&cpu_rq(cpu)->lock);
+               mm = cpu_curr(cpu)->mm;
+               spin_unlock_irq(&cpu_rq(cpu)->lock);
+               if (current->mm != mm)
+                       cpumask_clear_cpu(cpu, tmpmask);
+       } 

Why not:

  rcu_read_lock();
  if (current->mm != cpu_curr(cpu)->mm)
    cpumask_clear_cpu(cpu, tmpmask);
  rcu_read_unlock();

the RCU read lock ensures the task_struct obtained remains valid, and it avoids taking the rq->lock.

Quoted 11 lines · * Peter Zijlstra ([email protected]) wrote:

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

Quoted 7 lines · Mathieu Desnoyers

kernel/sched.c +7 -0

+       for_each_cpu(cpu, tmpmask) {
+               spin_lock_irq(&cpu_rq(cpu)->lock);
+               mm = cpu_curr(cpu)->mm;
+               spin_unlock_irq(&cpu_rq(cpu)->lock);
+               if (current->mm != mm)
+                       cpumask_clear_cpu(cpu, tmpmask);
+       } 

Why not:

Quoted 8 lines

  rcu_read_lock();
  if (current->mm != cpu_curr(cpu)->mm)
    cpumask_clear_cpu(cpu, tmpmask);
  rcu_read_unlock();

the RCU read lock ensures the task_struct obtained remains valid, and it avoids taking the rq->lock.

If we go for a simple rcu_read_lock, I think that we need a smp_mb() after switch_to() updates the current task on the remote CPU, before it returns to user-space. Do we have this guarantee for all architectures ?

So what I'm looking for, overall, is:

schedule()
...
switch_mm()

    smp_mb()
    clear mm_cpumask
    set mm_cpumask

switch_to()
update current task
smp_mb()

If we have that, then the rcu_read_lock should work.

What the rq lock currently gives us is the guarantee that if the current thread changes on a remote CPU while we are not holding this lock, then a full scheduler execution is performed, which implies a memory barrier if we change the current thread (it does, right ?).

Quoted 37 lines · Mathieu Desnoyers

Quoted 11 lines · * Peter Zijlstra ([email protected]) wrote:

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

Quoted 7 lines · Mathieu Desnoyers

kernel/sched.c +7 -0

+       for_each_cpu(cpu, tmpmask) {
+               spin_lock_irq(&cpu_rq(cpu)->lock);
+               mm = cpu_curr(cpu)->mm;
+               spin_unlock_irq(&cpu_rq(cpu)->lock);
+               if (current->mm != mm)
+                       cpumask_clear_cpu(cpu, tmpmask);
+       } 

Why not:

Quoted 8 lines

  rcu_read_lock();
  if (current->mm != cpu_curr(cpu)->mm)
    cpumask_clear_cpu(cpu, tmpmask);
  rcu_read_unlock();

the RCU read lock ensures the task_struct obtained remains valid, and it avoids taking the rq->lock.

If we go for a simple rcu_read_lock, I think that we need a smp_mb() after switch_to() updates the current task on the remote CPU, before it returns to user-space. Do we have this guarantee for all architectures ?

So what I'm looking for, overall, is:

schedule()
...
switch_mm()

    smp_mb()
    clear mm_cpumask
    set mm_cpumask

switch_to()
update current task
smp_mb()

Quoted 6 lines

If we have that, then the rcu_read_lock should work.

What the rq lock currently gives us is the guarantee that if the current thread changes on a remote CPU while we are not holding this lock, then a full scheduler execution is performed, which implies a memory barrier if we change the current thread (it does, right ?).

I'm not quite seeing it, we have 4 possibilities, switches between threads with:

a) our mm, another mm

- if we observe the former, we'll send an IPI (redundant)
- if we observe the latter, the switch_mm will have issued an mb

b) another mm, our mm

- if we observe the former, we're good because the cpu didn't run our thread when we called sys_membarrier()
- if we observe the latter, we'll send an IPI (redundant)

c) our mm, our mm

- no matter which task we observe, we'll match and send an IPI

d) another mm, another mm

- no matter which task we observe, we'll not match and not send an IPI.

Or am I missing something?

It's this scenario that is causing problem. Let's consider this execution:

       CPU 0 (membarrier)                  CPU 1 (another mm -> our mm)
       <kernel-space>                      <kernel-space>
                                           switch_mm()
                                             smp_mb()
                                             clear_mm_cpumask()
                                             set_mm_cpumask()
                                             smp_mb() (by load_cr3() on x86)
                                           switch_to()
       mm_cpumask includes CPU 1
       rcu_read_lock()
       if (CPU 1 mm != our mm)
         skip CPU 1.
       rcu_read_unlock()
                                             current = next (1)
                                           <switch back to user-space>
                                           read-lock()
                                             read gp, store local gp
                                             barrier()
                                             access critical section (2)

So if we don't have any memory barrier between (1) and (2), the memory operations can be reordered in such a way that CPU 0 will not send IPI to a CPU that would need to have it's barrier() promoted into a smp_mb().

Quoted 3 lines · Mathieu Desnoyers

It's this scenario that is causing problem. Let's consider this execution:

I'm still not getting it, sure we don't send an IPI, but it will have done an mb() in switch_mm() to become our mm, so even without the IPI it will have executed that mb we were after.

Quoted 5 lines · * Peter Zijlstra ([email protected]) wrote:

Quoted 3 lines · Mathieu Desnoyers

It's this scenario that is causing problem. Let's consider this execution:

(slightly augmented)

CPU 0 (membarrier) CPU 1 (another mm -> our mm)
<user-space>
<kernel-space> switch_mm()
smp_mb() clear_mm_cpumask() set_mm_cpumask() smp_mb() (by load_cr3() on x86)
switch_to()
memory access before membarrier
<call sys_membarrier()>
smp_mb()
mm_cpumask includes CPU 1
rcu_read_lock()
if (CPU 1 mm != our mm)
skip CPU 1.
rcu_read_unlock()
smp_mb()
<return to user-space>
current = next (1)
<switch back to user-space> urcu read lock()
read gp
store local gp (2) barrier()
access critical section data (3)
memory access after membarrier

So if we don't have any memory barrier between (1) and (3), the memory operations can be reordered in such a way that CPU 0 will not send IPI to a CPU that would need to have it's barrier() promoted into a smp_mb().

Quoted 1 line

Quoted 3 lines

I'm still not getting it, sure we don't send an IPI, but it will have done an mb() in switch_mm() to become our mm, so even without the IPI it will have executed that mb we were after.

The augmented race window above shows that it would be possible for (2) and (3) to be reordered across the barrier(), and therefore the critical section access could spill over a rcu-unlocked state.

To make this painfully clear, I'll reorder the accesses to match that of the CPU to memory:

CPU 0 (membarrier) CPU 1 (another mm -our mm)
<user-space>
<kernel-space> switch_mm()
smp_mb() clear_mm_cpumask() set_mm_cpumask() smp_mb() (by load_cr3() on x86)
switch_to()
<buffered current = next>
<switch back to user-space> urcu read lock()

access critical section data (3)
memory access before membarrier
<call sys_membarrier()>
smp_mb()
mm_cpumask includes CPU 1
rcu_read_lock()
if (CPU 1 mm != our mm)
skip CPU 1.

rcu_read_unlock()
smp_mb()
<return to user-space>
memory access after membarrier
current = next (1) (buffer flush) read gp
store local gp (2)

This should make the problem a bit more evident. Access (3) is done outside of the read-side C.S. as far as the userspace synchronize_rcu() is concerned.

Thanks,

Mathieu

Quoted 15 lines · Mathieu Desnoyers

To make this painfully clear, I'll reorder the accesses to match that of the CPU to memory:

CPU 0 (membarrier) CPU 1 (another mm -our mm)
<user-space>
<kernel-space> switch_mm()
smp_mb() clear_mm_cpumask() set_mm_cpumask() smp_mb() (by load_cr3() on x86)
switch_to()
<buffered current = next>
<switch back to user-space> urcu read lock()

Quoted 8 lines

access critical section data (3)
memory access before membarrier
<call sys_membarrier()>
smp_mb()
mm_cpumask includes CPU 1
rcu_read_lock()
if (CPU 1 mm != our mm)
skip CPU 1.

I still don't see how the above conditional fails?

-- Steve

Quoted 17 lines

rcu_read_unlock()
smp_mb()
<return to user-space>
memory access after membarrier
current = next (1) (buffer flush) read gp
store local gp (2)

This should make the problem a bit more evident. Access (3) is done outside of the read-side C.S. as far as the userspace synchronize_rcu() is concerned.

Thanks,

Mathieu

It's a case where CPU 1 switches from our mm to another mm:

CPU 0 (membarrier) CPU 1 (another mm -our mm)
<user-space> <user-space>
<buffered access C.S. data> urcu read unlock()
barrier() store local gp
<kernel-space> rq->curr = next (1)
memory access before membarrier
<call sys_membarrier()>
smp_mb()
mm_cpumask includes CPU 1
rcu_read_lock()
if (cpu_curr(1)->mm != our mm)
skip CPU 1 -> here, rq->curr new version is already visible

rcu_read_unlock()
smp_mb()
<return to user-space>
memory access after membarrier
-> this is where we allow freeing
the old structure although the
buffered access C.S. data is
still in flight.

User-space access C.S. data (2)
(buffer flush)
switch_mm()
smp_mb() clear_mm_cpumask() set_mm_cpumask() smp_mb() (by load_cr3() on x86)
switch_to()
<buffered current = next>
<switch back to user-space>
current = next (1) (buffer flush)
access critical section data (3)

As we can see, the reordering of (1) and (2) is problematic, as it lets the check skip over a CPU that have global side-effects not committed to memory yet.

It's a case where CPU 1 switches from our mm to another mm:

CPU 0 (membarrier) CPU 1 (another mm -our mm)
<user-space> <user-space>
<buffered access C.S. data> urcu read unlock()
barrier() store local gp
<kernel-space>

rq->curr = next (1)
memory access before membarrier
<call sys_membarrier()>
smp_mb()
mm_cpumask includes CPU 1
rcu_read_lock()
if (cpu_curr(1)->mm != our mm)
skip CPU 1 -> here, rq->curr new version is already visible
rcu_read_unlock()
smp_mb()
<return to user-space>
memory access after membarrier
-> this is where we allow freeing
the old structure although the
buffered access C.S. data is
still in flight.
User-space access C.S. data (2)
(buffer flush)
switch_mm()
smp_mb() clear_mm_cpumask() set_mm_cpumask() smp_mb() (by load_cr3() on x86)
switch_to()
<buffered current = next>
<switch back to user-space>
current = next (1) (buffer flush)
access critical section data (3)

As we can see, the reordering of (1) and (2) is problematic, as it lets the check skip over a CPU that have global side-effects not committed to memory yet.

Quoted 9 lines · Mathieu Desnoyers

It's a case where CPU 1 switches from our mm to another mm:

CPU 0 (membarrier) CPU 1 (another mm -our mm)
<user-space> <user-space>
<buffered access C.S. data> urcu read unlock()
barrier() store local gp
<kernel-space>

OK, so the question is how we end up here, if its though interrupt preemption I think the interrupt delivery will imply an mb,

if its a
blocking syscall, the set_task_state() mb [*] should be there.

Then we also do:

clear_tsk_need_resched()

which is an atomic bitop (although does not imply a full barrier per-se).

Quoted 1 line

                                           rq->curr = next (1)

Quoted 11 lines · Peter Zijlstra

Quoted 9 lines · Mathieu Desnoyers

It's a case where CPU 1 switches from our mm to another mm:

CPU 0 (membarrier) CPU 1 (another mm -our mm)
<user-space> <user-space>
<buffered access C.S. data> urcu read unlock()
barrier() store local gp
<kernel-space>

Quoted 2 lines

OK, so the question is how we end up here, if its though interrupt preemption I think the interrupt delivery will imply an mb,

I keep thinking that, but I think we actually refuted that in an earlier discussion on this patch.

Quoted 8 lines

if its a
blocking syscall, the set_task_state() mb [*] should be there.

Then we also do:

clear_tsk_need_resched()

Quoted 4 lines

which is an atomic bitop (although does not imply a full barrier per-se).

Quoted 1 line

                                           rq->curr = next (1)

We could possibly look at placing that assignment in context_switch() between switch_mm() and switch_to(), which should provide a mb before and after I think, Ingo?

Quoted 12 lines · * Peter Zijlstra ([email protected]) wrote:

Quoted 11 lines · Peter Zijlstra

Quoted 9 lines · Mathieu Desnoyers

It's a case where CPU 1 switches from our mm to another mm:

CPU 0 (membarrier) CPU 1 (another mm -our mm)
<user-space> <user-space>
<buffered access C.S. data> urcu read unlock()
barrier() store local gp
<kernel-space>

Quoted 5 lines

Quoted 2 lines

OK, so the question is how we end up here, if its though interrupt preemption I think the interrupt delivery will imply an mb,

I keep thinking that, but I think we actually refuted that in an earlier discussion on this patch.

Intel Architecture Software Developer's Manual Vol. 3: System Programming
7.4 Serializing Instructions

"MOV to control reg, MOV to debug reg, WRMSR, INVD, INVLPG, WBINDV, LGDT, LLDT, LIDT, LTR, CPUID, IRET, RSM"

So, this list does _not_ include: INT, SYSENTER, SYSEXIT.

Only IRET is included. So I don't think it is safe to assume that x86 has serializing instructions when entering/leaving the kernel.

Quoted 8 lines

Quoted 8 lines

if its a
blocking syscall, the set_task_state() mb [*] should be there.

Then we also do:

clear_tsk_need_resched()

Quoted 8 lines

Quoted 4 lines

which is an atomic bitop (although does not imply a full barrier per-se).

Quoted 1 line

                                           rq->curr = next (1)

We could possibly look at placing that assignment in context_switch() between switch_mm() and switch_to(), which should provide a mb before and after I think, Ingo?

That's an interesting idea. It would indeed fix the problem of the missing barrier before the assignment, but would lack the appropriate barrier after the assignment. If the rq->curr = next; assignment is made after load_cr3, then we lack a memory barrier between the assignment and execution of following user-space code after returning with SYSEXIT (and we lack the appropriate barrier for other architectures too).

We could possibly look at placing that assignment in context_switch() between switch_mm() and switch_to(), which should provide a mb before and after I think, Ingo?

Quoted 4 lines · Peter Zijlstra

We could possibly look at placing that assignment in context_switch() between switch_mm() and switch_to(), which should provide a mb before and after I think, Ingo?

Right, just found out why we cannot do that, the first thing context_switch() does is prepare_context_switch() which includes prepare_lock_switch() which on __ARCH_WANT_UNLOCKED_CTXSW machines drops the rq->lock, and we have to have rq->curr assigned by then.

* Peter Zijlstra ([email protected]) wrote:

We can even create a generic fallback with the following kind of code in the meantime:

static inline void spin_lock_mb(spinlock_t *lock)

{
	spin_lock(&lock);

	smp_mb();
}

static inline void spin_unlock_mb(spinlock_t *lock)

{
	smp_mb();
	spin_unlock(&lock);

}

How does that sound ?

Quoted 8 lines · Mathieu Desnoyers

* Peter Zijlstra ([email protected]) wrote:

We can even create a generic fallback with the following kind of code in the meantime:

static inline void spin_lock_mb(spinlock_t *lock)

{
	spin_lock(&lock);

That would be spin_lock(lock);

Quoted 3 lines

	smp_mb();
}

Quoted 4 lines

static inline void spin_unlock_mb(spinlock_t *lock)

{
	smp_mb();
	spin_unlock(&lock);

and spin_unlock(lock);

;-)

Quoted 4 lines

}

How does that sound ?

You may also need spin_lock_irqsave, et al. variants too.

-- Steve

Quoted 1 line · * Steven Rostedt ([email protected]) wrote:

You may also need spin_lock_irqsave, et al. variants too.

Yep, or we simply use the local_irq_save/restore separately. That could be a good idea given that only few specialized sites are affected.

Quoted 6 lines · Mathieu Desnoyers

Quoted 1 line · * Steven Rostedt ([email protected]) wrote:

You may also need spin_lock_irqsave, et al. variants too.

Yep, or we simply use the local_irq_save/restore separately. That could be a good idea given that only few specialized sites are affected.

If it gets used more often, then we need to consider RT. RT modifies spin_lock_irqsave into a standard mutex that does not disable interrupts. But if something does:

	local_irq_save(flags);
	spin_lock_mb(&lock);
	[...]

Then it will break RT (if lock is to be converted).

-- Steve

One efficient way to fit the requirement of sys_membarrier() would be to create spin_lock_mb()/spin_unlock_mb(), which would have full memory barriers rather than the acquire/release semantic. These could be used within schedule() execution. On UP, they would turn into preempt off/on and a compiler barrier, just like normal spin locks.

On architectures like x86, the atomic instructions already imply a full memory barrier, so we have a direct mapping and no overhead. On architecture where the spin lock only provides acquire semantic (e.g. powerpc using lwsync and isync), then we would have to create an alternate implementation with "sync".

Quoted 7 lines · Mathieu Desnoyers

One efficient way to fit the requirement of sys_membarrier() would be to create spin_lock_mb()/spin_unlock_mb(), which would have full memory barriers rather than the acquire/release semantic. These could be used within schedule() execution. On UP, they would turn into preempt off/on and a compiler barrier, just like normal spin locks.

Quoted 5 lines

On architectures like x86, the atomic instructions already imply a full memory barrier, so we have a direct mapping and no overhead. On architecture where the spin lock only provides acquire semantic (e.g. powerpc using lwsync and isync), then we would have to create an alternate implementation with "sync".

There's also clear_tsk_need_resched() which is an atomic op.

The thing I'm worrying about is not making schedule() more expensive for a relatively rare operation like sys_membarrier(), while at the same time trying to not make while (1) sys_membarrier() ruin your system.

On x86 there is plenty that implies a full mb before rq->curr = next, the thing to figure out is what is generally the cheapest place to force one for other architectures.

Not sure where that leaves us, since I'm not too familiar with !x86.

So about that [*], Oleg, kernel/signal.c:SYSCALL_DEFINE0(pause) does:

SYSCALL_DEFINE0(pause)

{
        current->state = TASK_INTERRUPTIBLE;
        schedule();
        return -ERESTARTNOHAND;
}

Isn't that ->state assignment buggy? If so, there appear to be quite a few such sites, which worries me.

Quoted 5 lines · * Peter Zijlstra ([email protected]) wrote:

Quoted 3 lines · Mathieu Desnoyers

It's this scenario that is causing problem. Let's consider this execution:

(slightly augmented)

       CPU 0 (membarrier)                  CPU 1 (another mm -> our mm)
       <user-space>
                                           <kernel-space>
                                           switch_mm()
                                             smp_mb()
                                             clear_mm_cpumask()
                                             set_mm_cpumask()
                                             smp_mb() (by load_cr3() on x86)
                                           switch_to()
       memory access before membarrier
       <call sys_membarrier()>
       smp_mb()
       mm_cpumask includes CPU 1
       rcu_read_lock()
       if (CPU 1 mm != our mm)

skip CPU 1.
rcu_read_unlock()
smp_mb()
<return to user-space>
current = next (1)
<switch back to user-space> urcu read lock()
read gp
store local gp (2) barrier()
access critical section data (3)
memory access after membarrier

Quoted 50 lines · * Peter Zijlstra ([email protected]) wrote:

Quoted 37 lines · Mathieu Desnoyers

Quoted 11 lines · * Peter Zijlstra ([email protected]) wrote:

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

Quoted 7 lines · Mathieu Desnoyers

kernel/sched.c +7 -0

+       for_each_cpu(cpu, tmpmask) {
+               spin_lock_irq(&cpu_rq(cpu)->lock);
+               mm = cpu_curr(cpu)->mm;
+               spin_unlock_irq(&cpu_rq(cpu)->lock);
+               if (current->mm != mm)
+                       cpumask_clear_cpu(cpu, tmpmask);
+       } 

Why not:

Quoted 8 lines

  rcu_read_lock();
  if (current->mm != cpu_curr(cpu)->mm)
    cpumask_clear_cpu(cpu, tmpmask);
  rcu_read_unlock();

the RCU read lock ensures the task_struct obtained remains valid, and it avoids taking the rq->lock.

If we go for a simple rcu_read_lock, I think that we need a smp_mb() after switch_to() updates the current task on the remote CPU, before it returns to user-space. Do we have this guarantee for all architectures ?

So what I'm looking for, overall, is:

schedule()
...
switch_mm()

    smp_mb()
    clear mm_cpumask
    set mm_cpumask

switch_to()
update current task
smp_mb()

Quoted 6 lines

If we have that, then the rcu_read_lock should work.

What the rq lock currently gives us is the guarantee that if the current thread changes on a remote CPU while we are not holding this lock, then a full scheduler execution is performed, which implies a memory barrier if we change the current thread (it does, right ?).

I'm not quite seeing it, we have 4 possibilities, switches between threads with:

a) our mm, another mm

Quoted 8 lines

- if we observe the former, we'll send an IPI (redundant)
- if we observe the latter, the switch_mm will have issued an mb

b) another mm, our mm

- if we observe the former, we're good because the cpu didn't run our thread when we called sys_membarrier()
- if we observe the latter, we'll send an IPI (redundant)

It's this scenario that is causing problem. Let's consider this execution:

       CPU 0 (membarrier)                  CPU 1 (another mm -> our mm)
       <kernel-space>                      <kernel-space>
                                           switch_mm()
                                             smp_mb()
                                             clear_mm_cpumask()
                                             set_mm_cpumask()
                                             smp_mb() (by load_cr3() on x86)
                                           switch_to()
       mm_cpumask includes CPU 1
       rcu_read_lock()
       if (CPU 1 mm != our mm)
         skip CPU 1.
       rcu_read_unlock()
                                             current = next (1)

<switch back to user-space> read-lock()
read gp, store local gp barrier() access critical section (2)

So if we don't have any memory barrier between (1) and (2), the memory operations can be reordered in such a way that CPU 0 will not send IPI to a CPU that would need to have it's barrier() promoted into a smp_mb().

Replacing these kernel rcu_read_lock/unlock() by rq locks ensures that when the scheduler runs concurrently on another CPU, _all_ the scheduling code is executed atomically wrt the spin lock taken on cpu 0.

When x86 uses iret to return to user-space, then we have a serializing instruction. But if it uses sysexit, or if we are on a different architecture, are we sure that a memory barrier is issued before returning to user-space ?

Quoted 17 lines

It's this scenario that is causing problem. Let's consider this execution:

       CPU 0 (membarrier)                  CPU 1 (another mm -> our mm)
       <kernel-space>                      <kernel-space>
                                           switch_mm()
                                             smp_mb()
                                             clear_mm_cpumask()
                                             set_mm_cpumask()
                                             smp_mb() (by load_cr3() on x86)
                                           switch_to()
       mm_cpumask includes CPU 1
       rcu_read_lock()
       if (CPU 1 mm != our mm)
         skip CPU 1.
       rcu_read_unlock()
                                             current = next (1)

OK, so on x86 current uses esp and will be flipped somewhere in the switch_to() magic, cpu_curr(cpu) as used by CPU 0 uses rq->curr, which will be set before context_switch() and that always implies a mb() for non matching ->mm's [*]

Quoted 11 lines

<switch back to user-space> read-lock()
read gp, store local gp barrier() access critical section (2)

So if we don't have any memory barrier between (1) and (2), the memory operations can be reordered in such a way that CPU 0 will not send IPI to a CPU that would need to have it's barrier() promoted into a smp_mb().

OK, so I'm utterly failing to make sense of the above, do you need more than the 2 cpus discussed to make it go boom?

Quoted 3 lines

Replacing these kernel rcu_read_lock/unlock() by rq locks ensures that when the scheduler runs concurrently on another CPU, _all_ the scheduling code is executed atomically wrt the spin lock taken on cpu 0.

Sure, but taking the rq->lock is fairly heavy handed.

Quoted 4 lines

When x86 uses iret to return to user-space, then we have a serializing instruction. But if it uses sysexit, or if we are on a different architecture, are we sure that a memory barrier is issued before returning to user-space ?

[*] and possibly also for matching ->mm's, because:

OK, so I had a quick look at the switch_to() magic, and from what I can make of it it implies an mb, if only because poking at the segment registers implies LOCK semantics.

Quoted 17 lines · Mathieu Desnoyers

It's this scenario that is causing problem. Let's consider this execution:

       CPU 0 (membarrier)                  CPU 1 (another mm -> our mm)
       <kernel-space>                      <kernel-space>
                                           switch_mm()
                                             smp_mb()
                                             clear_mm_cpumask()
                                             set_mm_cpumask()
                                             smp_mb() (by load_cr3() on x86)
                                           switch_to()
       mm_cpumask includes CPU 1
       rcu_read_lock()
       if (CPU 1 mm != our mm)
         skip CPU 1.
       rcu_read_unlock()
                                             current = next (1)

OK, so on x86 current uses esp and will be flipped somewhere in the switch_to() magic, cpu_curr(cpu) as used by CPU 0 uses rq->curr, which will be set before context_switch() and that always implies a mb() for non matching ->mm's [*]

Quoted 7 lines

<switch back to user-space> read-lock()
read gp, store local gp barrier() access critical section (2)

Quoted 4 lines

So if we don't have any memory barrier between (1) and (2), the memory operations can be reordered in such a way that CPU 0 will not send IPI to a CPU that would need to have it's barrier() promoted into a smp_mb().

OK, so I'm utterly failing to make sense of the above, do you need more than the 2 cpus discussed to make it go boom?

Quoted 4 lines

Replacing these kernel rcu_read_lock/unlock() by rq locks ensures that when the scheduler runs concurrently on another CPU, _all_ the scheduling code is executed atomically wrt the spin lock taken on cpu 0.

Sure, but taking the rq->lock is fairly heavy handed.

Quoted 5 lines

When x86 uses iret to return to user-space, then we have a serializing instruction. But if it uses sysexit, or if we are on a different architecture, are we sure that a memory barrier is issued before returning to user-space ?

[*] and possibly also for matching ->mm's, because:

OK, so I had a quick look at the switch_to() magic, and from what I can make of it it implies an mb, if only because poking at the segment registers implies LOCK semantics.