Udpated sys_membarrier() speedup patch, FYI

Hello!
But my main question is whether the throttling shown below is acceptable for your use cases, namely only one expedited sys_membarrier() permitted per scheduling-clock period (1 millisecond on many platforms), with any excess being silently converted to non-expedited form.

Quoted 5 lines · Paul E. McKenney

Hello!
But my main question is whether the throttling shown below is acceptable for your use cases, namely only one expedited sys_membarrier() permitted per scheduling-clock period (1 millisecond on many platforms), with any excess being silently converted to non-expedited form.

Google doesn't use sys_membarrier (that I know of...), but we do use RSEQ fences, which implements membarrier + a little extra to interrupt RSEQ critical sections (via IPI--smp_call_function_many.) One important optimization here is that we only throw IPIs to cpus running the same mm as current (or a subset if requested by userspace), as this is sufficient for the API guarantees we provide. I suspect a similar optimization would largely mitigate DOS concerns, no? I don't know if there are use cases not covered. To answer your question:
throttling these (or our equivalents) would be fine in terms of userspace throughput. We haven't noticed performance problems requiring such an intervention, however.

Furthermore: I wince a bit at the silent downgrade; I'd almost prefer -EAGAIN or -EBUSY. In particular, again for RSEQ fence, the downgrade simply wouldn't work; rcu_sched_qs() gets called at many points that aren't sufficiently quiescent for RSEQ (in particular, when userspace code is running!) This is solvable, but worth thinking about.

IPIin only those CPUs running threads in the same process as the thread invoking membarrier() would be very nice! There is some LKML discussion on this topic, which is currently circling around making this determination reliable on all CPU families. ARM and x86 are thought to be OK, PowerPC is thought to require a smallish patch, MIPS is a big question mark, and so on.

But I am surprised when you say that the downgrade would not work, at least if you are not running with nohz_full CPUs. The rcu_sched_qs() function simply sets a per-CPU quiescent-state flag. The needed strong ordering is instead supplied by the combination of the code starting the grace period, reporting the setting of the quiescent-state flag to core RCU, and the code completing the grace period. Each non-idle CPU will execute full memory barriers either in RCU_SOFTIRQ context, on entry to idle, on exit from idle, or within the grace-period kthread. In particular, a CPU running the same usermode thread for the entire grace period will execute the needed memory barriers in RCU_SOFTIRQ context shortly after taking a scheduling-clock interrupt.

Quoted 6 lines · Paul E. McKenney

IPIin only those CPUs running threads in the same process as the thread invoking membarrier() would be very nice! There is some LKML discussion on this topic, which is currently circling around making this determination reliable on all CPU families. ARM and x86 are thought to be OK, PowerPC is thought to require a smallish patch, MIPS is a big question mark, and so on.

I'm not sure what you mean by the determination or how this is arch specific?

Quoted 11 lines

But I am surprised when you say that the downgrade would not work, at least if you are not running with nohz_full CPUs. The rcu_sched_qs() function simply sets a per-CPU quiescent-state flag. The needed strong ordering is instead supplied by the combination of the code starting the grace period, reporting the setting of the quiescent-state flag to core RCU, and the code completing the grace period. Each non-idle CPU will execute full memory barriers either in RCU_SOFTIRQ context, on entry to idle, on exit from idle, or within the grace-period kthread. In particular, a CPU running the same usermode thread for the entire grace period will execute the needed memory barriers in RCU_SOFTIRQ context shortly after taking a scheduling-clock interrupt.

Recall that I need more than just a memory barrier--also to interrupt RSEQ critical sections in progress on those CPUs. I know this isn't general purpose, I'm just saying a trivial downgrade wouldn't work for me. :) It would probably be sufficient to set NOTIFY_RESUME on all cpus running my code (which is what my IPI function does anyway...)

Hello!

Please see below for a prototype sys_membarrier() speedup patch. Please note that there is some controversy on this subject, so the final version will probably be quite a bit different than this prototype.

But my main question is whether the throttling shown below is acceptable for your use cases, namely only one expedited sys_membarrier() permitted per scheduling-clock period (1 millisecond on many platforms), with any excess being silently converted to non-expedited form. The reason for the throttling is concerns about DoS attacks based on user code with a tight loop invoking this system call.

Thoughts?

Thanx, Paul

------------------------------------------------------------------------

commit 4cd5253094b6d7f9501e21e13aa4e2e78e8a70cd

Author: Paul E. McKenney <[email protected]>
Date:   Tue Jul 18 13:53:32 2017 -0700

sys_membarrier: Add expedited option

The sys_membarrier() system call has proven too slow for some use cases, which has prompted users to instead rely on TLB shootdown. Although TLB shootdown is much faster, it has the slight disadvantage of not working at all on arm and arm64 and also of being vulnerable to reasonable optimizations that might skip some IPIs. However, the Linux kernel does not currrently provide a reasonable alternative, so it is hard to criticize these users from doing what works for them on a given piece of hardware at a given time.

This commit therefore adds an expedited option to the sys_membarrier() system call, thus providing a faster mechanism that is portable and is not subject to death by optimization. Note that if more than one MEMBARRIER_CMD_SHARED_EXPEDITED sys_membarrier() call happens within the same jiffy, all but the first will use synchronize_sched() instead of synchronize_sched_expedited().

Signed-off-by Paul E. McKenney <[email protected]>

[ paulmck: Fix code style issue pointed out by Boqun Feng. ]

Tested-by Avi Kivity <[email protected]>

Cc Maged Michael <[email protected]>

Cc Andrew Hunter <[email protected]>

Cc Geoffrey Romer <[email protected]>

include/uapi/linux/membarrier.h +11 -0

index e0b108bd2624..5720386d0904 100644
@@ -40,6 +40,16 @@
   *                          (non-running threads are de facto in such a
   *                          state). This covers threads from all processes
   *                          running on the system. This command returns 0.
+ * @MEMBARRIER_CMD_SHARED_EXPEDITED:  Execute a memory barrier on all
+ *			    running threads, but in an expedited fashion.
+ *                          Upon return from system call, the caller thread
+ *                          is ensured that all running threads have passed
+ *                          through a state where all memory accesses to
+ *                          user-space addresses match program order between
+ *                          entry to and return from the system call
+ *                          (non-running threads are de facto in such a
+ *                          state). This covers threads from all processes
+ *                          running on the system. This command returns 0.
   *
   * Command to be passed to the membarrier system call. The commands need to
   * be a single bit each, except for MEMBARRIER_CMD_QUERY which is assigned to

@@ -48,6 +58,7 @@
  enum membarrier_cmd {
  	MEMBARRIER_CMD_QUERY = 0,
  	MEMBARRIER_CMD_SHARED = (1 << 0),
+	MEMBARRIER_CMD_SHARED_EXPEDITED = (1 << 1),
  };
 
  #endif /* _UAPI_LINUX_MEMBARRIER_H */

kernel/membarrier.c +16 -1

index 9f9284f37f8d..587e3bbfae7e 100644
@@ -22,7 +22,8 @@
   * Bitmask made from a "or" of all commands within enum membarrier_cmd,
   * except MEMBARRIER_CMD_QUERY.
   */
-#define MEMBARRIER_CMD_BITMASK	(MEMBARRIER_CMD_SHARED)
+#define MEMBARRIER_CMD_BITMASK	(MEMBARRIER_CMD_SHARED |		\
+				 MEMBARRIER_CMD_SHARED_EXPEDITED)
 
  /**
   * sys_membarrier - issue memory barriers on a set of threads

@@ -64,6 +65,20 @@ SYSCALL_DEFINE2(membarrier, int, cmd, int, flags)
  		if (num_online_cpus() > 1)
  			synchronize_sched();
  		return 0;
+	case MEMBARRIER_CMD_SHARED_EXPEDITED:
+		if (num_online_cpus() > 1) {
+			static unsigned long lastexp;
+			unsigned long j;
+
+			j = jiffies;
+			if (READ_ONCE(lastexp) == j) {
+				synchronize_sched();
+				WRITE_ONCE(lastexp, j);
+			} else {
+				synchronize_sched_expedited();
+			}
+		}
+		return 0;
  	default:
  		return -EINVAL;
  	}

Quoted 6 lines · Paul E. McKenney

Hello!

Please see below for a prototype sys_membarrier() speedup patch. Please note that there is some controversy on this subject, so the final version will probably be quite a bit different than this prototype.

Quoted 8 lines

But my main question is whether the throttling shown below is acceptable for your use cases, namely only one expedited sys_membarrier() permitted per scheduling-clock period (1 millisecond on many platforms), with any excess being silently converted to non-expedited form. The reason for the throttling is concerns about DoS attacks based on user code with a tight loop invoking this system call.

Thoughts?

Silent throttling would render it useless for me. -EAGAIN is a little better, but I'd be forced to spin until either I get kicked out of my loop, or it succeeds.

IPIing only running threads of my process would be perfect. In fact I might even be able to make use of "membarrier these threads please" to reduce IPIs, when I change the topology from fully connected to something more sparse, on larger machines.

My previous implementations were a signal (but that's horrible on large machines) and trylock + mprotect (but that doesn't work on ARM).

Quoted 24 lines · Avi Kivity

Quoted 6 lines · Paul E. McKenney

Hello!

Please see below for a prototype sys_membarrier() speedup patch. Please note that there is some controversy on this subject, so the final version will probably be quite a bit different than this prototype.

Quoted 8 lines

But my main question is whether the throttling shown below is acceptable for your use cases, namely only one expedited sys_membarrier() permitted per scheduling-clock period (1 millisecond on many platforms), with any excess being silently converted to non-expedited form. The reason for the throttling is concerns about DoS attacks based on user code with a tight loop invoking this system call.

Thoughts?

Silent throttling would render it useless for me. -EAGAIN is a little better, but I'd be forced to spin until either I get kicked out of my loop, or it succeeds.

IPIing only running threads of my process would be perfect. In fact I might even be able to make use of "membarrier these threads please" to reduce IPIs, when I change the topology from fully connected to something more sparse, on larger machines.

Quoted 3 lines

My previous implementations were a signal (but that's horrible on large machines) and trylock + mprotect (but that doesn't work on ARM).

OK, how about the following patch, which IPIs only the running threads of the process doing the sys_membarrier()?

Thanx, Paul

------------------------------------------------------------------------

From: Mathieu Desnoyers <[email protected]>
To: Peter Zijlstra <[email protected]>
Cc: [email protected], Mathieu Desnoyers
<[email protected]>,
"Paul E . McKenney" <[email protected]>, Boqun Feng <[email protected]>
Subject: [RFC PATCH] membarrier: expedited private command
Date: Thu, 27 Jul 2017 14:59:43 -0400
Message-Id: <[email protected]>

Implement MEMBARRIER_CMD_PRIVATE_EXPEDITED with IPIs using cpumask built from all runqueues for which current thread's mm is the same as our own.

Scheduler-wise, it requires that we add a memory barrier after context switching between processes (which have different mm).

It would be interesting to benchmark the overhead of this added barrier on the performance of context switching between processes. If the preexisting overhead of switching between mm is high enough, the overhead of adding this extra barrier may be insignificant.

[ Compile-tested only! ]

CC Peter Zijlstra <[email protected]>

CC Paul E. McKenney <[email protected]>

CC Boqun Feng <[email protected]>

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

---
  include/uapi/linux/membarrier.h |  8 +++--
  kernel/membarrier.c             | 76 ++++++++++++++++++++++++++++++++++++++++-
  kernel/sched/core.c             | 21 ++++++++++++
  3 files changed, 102 insertions(+), 3 deletions(-)

include/uapi/linux/membarrier.h +6 -2

index e0b108bd2624..6a33c5852f6b 100644
@@ -40,14 +40,18 @@
   *                          (non-running threads are de facto in such a
   *                          state). This covers threads from all processes
   *                          running on the system. This command returns 0.
+ * TODO: documentation.
   *
   * Command to be passed to the membarrier system call. The commands need to
   * be a single bit each, except for MEMBARRIER_CMD_QUERY which is assigned to
   * the value 0.
   */
  enum membarrier_cmd {
-	MEMBARRIER_CMD_QUERY = 0,
-	MEMBARRIER_CMD_SHARED = (1 << 0),
+	MEMBARRIER_CMD_QUERY			= 0,
+	MEMBARRIER_CMD_SHARED			= (1 << 0),
+	/* reserved for MEMBARRIER_CMD_SHARED_EXPEDITED (1 << 1) */
+	/* reserved for MEMBARRIER_CMD_PRIVATE (1 << 2) */
+	MEMBARRIER_CMD_PRIVATE_EXPEDITED	= (1 << 3),
  };
 
  #endif /* _UAPI_LINUX_MEMBARRIER_H */

kernel/membarrier.c +33 -1

index 9f9284f37f8d..8c6c0f96f617 100644
@@ -19,10 +19,81 @@
  #include <linux/tick.h>
 
  /*
+ * XXX For cpu_rq(). Should we rather move
+ * membarrier_private_expedited() to sched/core.c or create
+ * sched/membarrier.c ?
+ */
+#include "sched/sched.h"
+
+/*
   * Bitmask made from a "or" of all commands within enum membarrier_cmd,
   * except MEMBARRIER_CMD_QUERY.
   */
-#define MEMBARRIER_CMD_BITMASK	(MEMBARRIER_CMD_SHARED)
+#define MEMBARRIER_CMD_BITMASK	\
+	(MEMBARRIER_CMD_SHARED | MEMBARRIER_CMD_PRIVATE_EXPEDITED)
+
 
 	rcu_read_unlock();
+	}
+}
+
+static void membarrier_private_expedited(void)
+{
+	int cpu, this_cpu;
+	cpumask_var_t tmpmask;
+
+	if (num_online_cpus() == 1)
+		return;
+
+	/*
+	 * Matches memory barriers around rq->curr modification in
+	 * scheduler.
+	 */
+	smp_mb();	/* system call entry is not a mb. */
+
+	if (!alloc_cpumask_var(&tmpmask, GFP_NOWAIT)) {
+		/* Fallback for OOM. */
+		membarrier_private_expedited_ipi_each();
+		goto end;
+	}
+

kernel/membarrier.c +15 -0

+		rcu_read_unlock();
+	}
+	smp_call_function_many(tmpmask, ipi_mb, NULL, 1);
+	free_cpumask_var(tmpmask);
+end:
+	/*
+	* Memory barrier on the caller thread _after_ we finished
+	* waiting for the last IPI. Matches memory barriers around
+	* rq->curr modification in scheduler.
+	*/
+	smp_mb();	/* exit from system call is not a mb */
+}
 
  /**
   * sys_membarrier - issue memory barriers on a set of threads

@@ -64,6 +135,9 @@ SYSCALL_DEFINE2(membarrier, int, cmd, int, flags)
  		if (num_online_cpus() > 1)
  			synchronize_sched();
  		return 0;
+	case MEMBARRIER_CMD_PRIVATE_EXPEDITED:
+		membarrier_private_expedited();
+		return 0;
  	default:
  		return -EINVAL;
  	}

kernel/sched/core.c +3 -0

index 17c667b427b4..f171d2aaaf82 100644
@@ -2724,6 +2724,26 @@ asmlinkage __visible void schedule_tail(struct task_struct *prev)
  		put_user(task_pid_vnr(current), current->set_child_tid);
  }
 
+#ifdef CONFIG_MEMBARRIER
+static void membarrier_expedited_mb_after_set_current(struct mm_struct *mm,
+		struct mm_struct *oldmm)

kernel/sched/core.c +8 -0

+#else /* #ifdef CONFIG_MEMBARRIER */
+static void membarrier_expedited_mb_after_set_current(struct mm_struct *mm,
+		struct mm_struct *oldmm)
+{
+}
+#endif /* #else #ifdef CONFIG_MEMBARRIER */
+
  /*
   * context_switch - switch to the new MM and the new thread's register state.
   */

@@ -2737,6 +2757,7 @@ context_switch(struct rq *rq, struct task_struct *prev,
 
  	mm = next->mm;
  	oldmm = prev->active_mm;
+	membarrier_expedited_mb_after_set_current(mm, oldmm);
  	/*
  	 * For paravirt, this is coupled with an exit in switch_to to
  	 * combine the page table reload and the switch backend into

Quoted 25 lines · Paul E. McKenney

Quoted 24 lines · Avi Kivity

Quoted 6 lines · Paul E. McKenney

Hello!

Please see below for a prototype sys_membarrier() speedup patch. Please note that there is some controversy on this subject, so the final version will probably be quite a bit different than this prototype.

Quoted 8 lines

But my main question is whether the throttling shown below is acceptable for your use cases, namely only one expedited sys_membarrier() permitted per scheduling-clock period (1 millisecond on many platforms), with any excess being silently converted to non-expedited form. The reason for the throttling is concerns about DoS attacks based on user code with a tight loop invoking this system call.

Thoughts?

Silent throttling would render it useless for me. -EAGAIN is a little better, but I'd be forced to spin until either I get kicked out of my loop, or it succeeds.

IPIing only running threads of my process would be perfect. In fact I might even be able to make use of "membarrier these threads please" to reduce IPIs, when I change the topology from fully connected to something more sparse, on larger machines.

Quoted 5 lines

Quoted 3 lines

My previous implementations were a signal (but that's horrible on large machines) and trylock + mprotect (but that doesn't work on ARM).

OK, how about the following patch, which IPIs only the running threads of the process doing the sys_membarrier()?

Works for me.

Quoted 111 lines

------------------------------------------------------------------------

From: Mathieu Desnoyers <[email protected]>
To: Peter Zijlstra <[email protected]>
Cc: [email protected], Mathieu Desnoyers
<[email protected]>,
"Paul E . McKenney" <[email protected]>, Boqun Feng <[email protected]>
Subject: [RFC PATCH] membarrier: expedited private command
Date: Thu, 27 Jul 2017 14:59:43 -0400
Message-Id: <[email protected]>

Implement MEMBARRIER_CMD_PRIVATE_EXPEDITED with IPIs using cpumask built from all runqueues for which current thread's mm is the same as our own.

Scheduler-wise, it requires that we add a memory barrier after context switching between processes (which have different mm).

It would be interesting to benchmark the overhead of this added barrier on the performance of context switching between processes. If the preexisting overhead of switching between mm is high enough, the overhead of adding this extra barrier may be insignificant.

[ Compile-tested only! ]

CC Peter Zijlstra <[email protected]>

CC Paul E. McKenney <[email protected]>

CC Boqun Feng <[email protected]>

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

---
 include/uapi/linux/membarrier.h |  8 +++--
 kernel/membarrier.c             | 76 ++++++++++++++++++++++++++++++++++++++++-
 kernel/sched/core.c             | 21 ++++++++++++
 3 files changed, 102 insertions(+), 3 deletions(-)

include/uapi/linux/membarrier.h +6 -2

index e0b108bd2624..6a33c5852f6b 100644
@@ -40,14 +40,18 @@
  *                          (non-running threads are de facto in such a
  *                          state). This covers threads from all processes
  *                          running on the system. This command returns 0.
+ * TODO: documentation.
  *
  * Command to be passed to the membarrier system call. The commands need to
  * be a single bit each, except for MEMBARRIER_CMD_QUERY which is assigned to
  * the value 0.
  */
 enum membarrier_cmd {
-	MEMBARRIER_CMD_QUERY = 0,
-	MEMBARRIER_CMD_SHARED = (1 << 0),
+	MEMBARRIER_CMD_QUERY			= 0,
+	MEMBARRIER_CMD_SHARED			= (1 << 0),
+	/* reserved for MEMBARRIER_CMD_SHARED_EXPEDITED (1 << 1) */
+	/* reserved for MEMBARRIER_CMD_PRIVATE (1 << 2) */
+	MEMBARRIER_CMD_PRIVATE_EXPEDITED	= (1 << 3),
 };
 
 #endif /* _UAPI_LINUX_MEMBARRIER_H */

kernel/membarrier.c +38 -1

index 9f9284f37f8d..8c6c0f96f617 100644
@@ -19,10 +19,81 @@
 #include <linux/tick.h>
 
 /*
+ * XXX For cpu_rq(). Should we rather move
+ * membarrier_private_expedited() to sched/core.c or create
+ * sched/membarrier.c ?
+ */
+#include "sched/sched.h"
+
+/*
  * Bitmask made from a "or" of all commands within enum membarrier_cmd,
  * except MEMBARRIER_CMD_QUERY.
  */
-#define MEMBARRIER_CMD_BITMASK	(MEMBARRIER_CMD_SHARED)
+#define MEMBARRIER_CMD_BITMASK	\
+	(MEMBARRIER_CMD_SHARED | MEMBARRIER_CMD_PRIVATE_EXPEDITED)
+
 
 	rcu_read_unlock();
+	}
+}
+
+static void membarrier_private_expedited(void)
+{
+	int cpu, this_cpu;
+	cpumask_var_t tmpmask;
+
+	if (num_online_cpus() == 1)
+		return;
+
+	/*
+	 * Matches memory barriers around rq->curr modification in
+	 * scheduler.
+	 */
+	smp_mb();	/* system call entry is not a mb. */
+
+	if (!alloc_cpumask_var(&tmpmask, GFP_NOWAIT)) {
+		/* Fallback for OOM. */
+		membarrier_private_expedited_ipi_each();
+		goto end;
+	}
+
+	this_cpu = raw_smp_processor_id();
+	for_each_online_cpu(cpu) {
+		struct task_struct *p;
+
+		if (cpu == this_cpu)

kernel/membarrier.c line 84

Quoted 5 lines

kernel/membarrier.c +5 -0

+			continue;
+		rcu_read_lock();
+		p = task_rcu_dereference(&cpu_rq(cpu)->curr);
+		if (p && p->mm == current->mm)
+			__cpumask_set_cpu(cpu, tmpmask);

This gets you some false positives, if the CPU idled then mm will not have changed.

Quoted 33 lines

kernel/membarrier.c +15 -0

+		rcu_read_unlock();
+	}
+	smp_call_function_many(tmpmask, ipi_mb, NULL, 1);
+	free_cpumask_var(tmpmask);
+end:
+	/*
+	* Memory barrier on the caller thread _after_ we finished
+	* waiting for the last IPI. Matches memory barriers around
+	* rq->curr modification in scheduler.
+	*/
+	smp_mb();	/* exit from system call is not a mb */
+}
 
 /**
  * sys_membarrier - issue memory barriers on a set of threads

@@ -64,6 +135,9 @@ SYSCALL_DEFINE2(membarrier, int, cmd, int, flags)
 		if (num_online_cpus() > 1)
 			synchronize_sched();
 		return 0;
+	case MEMBARRIER_CMD_PRIVATE_EXPEDITED:
+		membarrier_private_expedited();
+		return 0;
 	default:
 		return -EINVAL;
 	}

kernel/sched/core.c +0 -0

index 17c667b427b4..f171d2aaaf82 100644
@@ -2724,6 +2724,26 @@ asmlinkage __visible void schedule_tail(struct task_struct *prev)
 		put_user(task_pid_vnr(current), current->set_child_tid);
 }
 

kernel/sched/core.c asmlinkage __visible void schedule_tail(struct task_struct *prev) · line 2739

Quoted 13 lines

kernel/sched/core.c +13 -0

+#ifdef CONFIG_MEMBARRIER
+static void membarrier_expedited_mb_after_set_current(struct mm_struct *mm,
+		struct mm_struct *oldmm)
+{
+	if (likely(mm == oldmm))
+		return;		/* Thread context switch, same mm. */
+	/*
+	 * When switching between processes, membarrier expedited
+	 * private requires a memory barrier after we set the current
+	 * task.
+	 */
+	smp_mb();
+}

Won't the actual page table switch generate a barrier, at least on many archs? It sure will on x86.

It's also unneeded if kernel entry or exit involve a barrier (not true for x86, so probably not for anything else either).

Quoted 18 lines

kernel/sched/core.c +8 -0

+#else /* #ifdef CONFIG_MEMBARRIER */
+static void membarrier_expedited_mb_after_set_current(struct mm_struct *mm,
+		struct mm_struct *oldmm)
+{
+}
+#endif /* #else #ifdef CONFIG_MEMBARRIER */
+
 /*
  * context_switch - switch to the new MM and the new thread's register state.
  */

@@ -2737,6 +2757,7 @@ context_switch(struct rq *rq, struct task_struct *prev,
 
 	mm = next->mm;
 	oldmm = prev->active_mm;
+	membarrier_expedited_mb_after_set_current(mm, oldmm);
 	/*
 	 * For paravirt, this is coupled with an exit in switch_to to
 	 * combine the page table reload and the switch backend into

Quoted 29 lines · Avi Kivity

Quoted 28 lines · Paul E. McKenney

Quoted 27 lines · Avi Kivity

Quoted 6 lines · Paul E. McKenney

Hello!

Please see below for a prototype sys_membarrier() speedup patch. Please note that there is some controversy on this subject, so the final version will probably be quite a bit different than this prototype.

Quoted 8 lines

But my main question is whether the throttling shown below is acceptable for your use cases, namely only one expedited sys_membarrier() permitted per scheduling-clock period (1 millisecond on many platforms), with any excess being silently converted to non-expedited form. The reason for the throttling is concerns about DoS attacks based on user code with a tight loop invoking this system call.

Thoughts?

Silent throttling would render it useless for me. -EAGAIN is a little better, but I'd be forced to spin until either I get kicked out of my loop, or it succeeds.

IPIing only running threads of my process would be perfect. In fact I might even be able to make use of "membarrier these threads please" to reduce IPIs, when I change the topology from fully connected to something more sparse, on larger machines.

My previous implementations were a signal (but that's horrible on large machines) and trylock + mprotect (but that doesn't work on ARM).

Quoted 4 lines

Quoted 2 lines

OK, how about the following patch, which IPIs only the running threads of the process doing the sys_membarrier()?

Works for me.

Thank you for testing! I expect that Mathieu will have a v2 soon, hopefully CCing you guys. (If not, I will forward it.)

Mathieu, please note Avi's feedback below.

Thanx, Paul

Quoted 112 lines

Quoted 112 lines

------------------------------------------------------------------------

From: Mathieu Desnoyers <[email protected]>
To: Peter Zijlstra <[email protected]>
Cc: [email protected], Mathieu Desnoyers
<[email protected]>,
"Paul E . McKenney" <[email protected]>, Boqun Feng <[email protected]>
Subject: [RFC PATCH] membarrier: expedited private command
Date: Thu, 27 Jul 2017 14:59:43 -0400
Message-Id: <[email protected]>

Implement MEMBARRIER_CMD_PRIVATE_EXPEDITED with IPIs using cpumask built from all runqueues for which current thread's mm is the same as our own.

Scheduler-wise, it requires that we add a memory barrier after context switching between processes (which have different mm).

It would be interesting to benchmark the overhead of this added barrier on the performance of context switching between processes. If the preexisting overhead of switching between mm is high enough, the overhead of adding this extra barrier may be insignificant.

[ Compile-tested only! ]

CC Peter Zijlstra <[email protected]>

CC Paul E. McKenney <[email protected]>

CC Boqun Feng <[email protected]>

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

---
 include/uapi/linux/membarrier.h |  8 +++--
 kernel/membarrier.c             | 76 ++++++++++++++++++++++++++++++++++++++++-
 kernel/sched/core.c             | 21 ++++++++++++
 3 files changed, 102 insertions(+), 3 deletions(-)

include/uapi/linux/membarrier.h +6 -2

index e0b108bd2624..6a33c5852f6b 100644
@@ -40,14 +40,18 @@
  *                          (non-running threads are de facto in such a
  *                          state). This covers threads from all processes
  *                          running on the system. This command returns 0.
+ * TODO: documentation.
  *
  * Command to be passed to the membarrier system call. The commands need to
  * be a single bit each, except for MEMBARRIER_CMD_QUERY which is assigned to
  * the value 0.
  */
 enum membarrier_cmd {
-	MEMBARRIER_CMD_QUERY = 0,
-	MEMBARRIER_CMD_SHARED = (1 << 0),
+	MEMBARRIER_CMD_QUERY			= 0,
+	MEMBARRIER_CMD_SHARED			= (1 << 0),
+	/* reserved for MEMBARRIER_CMD_SHARED_EXPEDITED (1 << 1) */
+	/* reserved for MEMBARRIER_CMD_PRIVATE (1 << 2) */
+	MEMBARRIER_CMD_PRIVATE_EXPEDITED	= (1 << 3),
 };
 
 #endif /* _UAPI_LINUX_MEMBARRIER_H */

kernel/membarrier.c +38 -1

index 9f9284f37f8d..8c6c0f96f617 100644
@@ -19,10 +19,81 @@
 #include <linux/tick.h>
 
 /*
+ * XXX For cpu_rq(). Should we rather move
+ * membarrier_private_expedited() to sched/core.c or create
+ * sched/membarrier.c ?
+ */
+#include "sched/sched.h"
+
+/*
  * Bitmask made from a "or" of all commands within enum membarrier_cmd,
  * except MEMBARRIER_CMD_QUERY.
  */
-#define MEMBARRIER_CMD_BITMASK	(MEMBARRIER_CMD_SHARED)
+#define MEMBARRIER_CMD_BITMASK	\
+	(MEMBARRIER_CMD_SHARED | MEMBARRIER_CMD_PRIVATE_EXPEDITED)
+
 
 	rcu_read_unlock();
+	}
+}
+
+static void membarrier_private_expedited(void)
+{
+	int cpu, this_cpu;
+	cpumask_var_t tmpmask;
+
+	if (num_online_cpus() == 1)
+		return;
+
+	/*
+	 * Matches memory barriers around rq->curr modification in
+	 * scheduler.
+	 */
+	smp_mb();	/* system call entry is not a mb. */
+
+	if (!alloc_cpumask_var(&tmpmask, GFP_NOWAIT)) {
+		/* Fallback for OOM. */
+		membarrier_private_expedited_ipi_each();
+		goto end;
+	}
+
+	this_cpu = raw_smp_processor_id();
+	for_each_online_cpu(cpu) {
+		struct task_struct *p;
+
+		if (cpu == this_cpu)

Quoted 8 lines

kernel/membarrier.c line 84

Quoted 5 lines

kernel/membarrier.c +5 -0

+			continue;
+		rcu_read_lock();
+		p = task_rcu_dereference(&cpu_rq(cpu)->curr);
+		if (p && p->mm == current->mm)
+			__cpumask_set_cpu(cpu, tmpmask);

This gets you some false positives, if the CPU idled then mm will not have changed.

Good point! The battery-powered embedded guys would probably prefer we not needlessly IPI idle CPUs. We cannot rely on RCU's dyntick-idle state in nohz_full cases. Not sure if is_idle_task() can be used safely, given things like play_idle().

----- On Jul 27, 2017, at 4:37 PM, Paul E. McKenney [email protected]

Quoted 1 line · wrote:

On Thu, Jul 27, 2017 at 11:04:13PM +0300, Avi Kivity wrote:

Quoted 15 lines

Quoted 6 lines

Quoted 6 lines

kernel/membarrier.c +6 -0

+
+	this_cpu = raw_smp_processor_id();
+	for_each_online_cpu(cpu) {
+		struct task_struct *p;
+
+		if (cpu == this_cpu)

Quoted 8 lines

kernel/membarrier.c line 84

Quoted 5 lines

kernel/membarrier.c +5 -0

+			continue;
+		rcu_read_lock();
+		p = task_rcu_dereference(&cpu_rq(cpu)->curr);
+		if (p && p->mm == current->mm)
+			__cpumask_set_cpu(cpu, tmpmask);

This gets you some false positives, if the CPU idled then mm will not have changed.

Quoted 4 lines

Good point! The battery-powered embedded guys would probably prefer we not needlessly IPI idle CPUs. We cannot rely on RCU's dyntick-idle state in nohz_full cases. Not sure if is_idle_task() can be used safely, given things like play_idle().

Would changing the check in this loop to:

if (p && !is_idle_task(p) && p->mm == current->mm) {

work for you ?

Thanks,

Mathieu

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

Quoted 4 lines · ----- On Jul 27, 2017, at 4:58 PM, Mathieu Desnoyers…

----- On Jul 27, 2017, at 4:37 PM, Paul E. McKenney [email protected]

Quoted 1 line · wrote:

On Thu, Jul 27, 2017 at 11:04:13PM +0300, Avi Kivity wrote:

[...]

Quoted 19 lines

Quoted 13 lines

Quoted 5 lines

Quoted 5 lines

kernel/membarrier.c +5 -0

+
+	this_cpu = raw_smp_processor_id();
+	for_each_online_cpu(cpu) {
+		struct task_struct *p;
+

Quoted 8 lines

kernel/membarrier.c line 84

Quoted 6 lines

kernel/membarrier.c +6 -0

+		if (cpu == this_cpu)
+			continue;
+		rcu_read_lock();
+		p = task_rcu_dereference(&cpu_rq(cpu)->curr);
+		if (p && p->mm == current->mm)
+			__cpumask_set_cpu(cpu, tmpmask);

This gets you some false positives, if the CPU idled then mm will not have changed.

Quoted 4 lines

Good point! The battery-powered embedded guys would probably prefer we not needlessly IPI idle CPUs. We cannot rely on RCU's dyntick-idle state in nohz_full cases. Not sure if is_idle_task() can be used safely, given things like play_idle().

Would changing the check in this loop to:

Quoted 3 lines

if (p && !is_idle_task(p) && p->mm == current->mm) {

work for you ?

Avi, is there an optimization that allows current->mm to be non-null when the idle task is scheduled that I am missing ?

I would have expected current->mm to be always NULL for idle tasks.

I remembered that current->mm does not change when switching to a kernel task, but my Kernlish is very rusty, or maybe it has changed.

Quoted 2 lines · Avi Kivity

I remembered that current->mm does not change when switching to a kernel task, but my Kernlish is very rusty, or maybe it has changed.

kernel threads do indeed preserve the mm of the old userspace task, but we track that in ->active_mm. Their ->mm will be NULL.

Quoted 5 lines · Avi Kivity

IPIing only running threads of my process would be perfect. In fact I might even be able to make use of "membarrier these threads please" to reduce IPIs, when I change the topology from fully connected to something more sparse, on larger machines.

kernel/membarrier.c +5 -0

+static void membarrier_private_expedited_ipi_each(void)
+{
+       int cpu;
+
+       for_each_online_cpu(cpu) {

Quoted 6 lines · Paul E. McKenney

Quoted 5 lines · Avi Kivity

IPIing only running threads of my process would be perfect. In fact I might even be able to make use of "membarrier these threads please" to reduce IPIs, when I change the topology from fully connected to something more sparse, on larger machines.

We do this as well--sometimes we only need RSEQ fences against specific CPU(s), and thus pass a subset.

Quoted 5 lines

kernel/membarrier.c +5 -0

+static void membarrier_private_expedited_ipi_each(void)
+{
+       int cpu;
+
+       for_each_online_cpu(cpu) {

kernel/membarrier.c line 54

Quoted 10 lines

kernel/membarrier.c +10 -0

+               struct task_struct *p;
+
+               rcu_read_lock();
+               p = task_rcu_dereference(&cpu_rq(cpu)->curr);
+               if (p && p->mm == current->mm)
+                       smp_call_function_single(cpu, ipi_mb, NULL, 1);
+               rcu_read_unlock();
+       }
+}
+

We have the (simpler imho)

const struct cpumask *mask = mm_cpumask(mm);
/* possibly AND it with a user requested mask */
smp_call_function_many(mask, ipi_func, ....);

which I think will be faster on some archs (that support broadcast) and have fewer problems with out of sync values (though we do have to check in our IPI function that we haven't context switched out.

Am I missing why this won't work?

Quoted 5 lines · Paul E. McKenney

Quoted 4 lines · Avi Kivity

IPIing only running threads of my process would be perfect. In fact I might even be able to make use of "membarrier these threads please" to reduce IPIs, when I change the topology from fully connected to something more sparse, on larger machines.

We do this as well--sometimes we only need RSEQ fences against specific CPU(s), and thus pass a subset.

Quoted 5 lines

kernel/membarrier.c +5 -0

+static void membarrier_private_expedited_ipi_each(void)
+{
+       int cpu;
+
+       for_each_online_cpu(cpu) {

kernel/membarrier.c line 54

Quoted 10 lines

kernel/membarrier.c +10 -0

+               struct task_struct *p;
+
+               rcu_read_lock();
+               p = task_rcu_dereference(&cpu_rq(cpu)->curr);
+               if (p && p->mm == current->mm)
+                       smp_call_function_single(cpu, ipi_mb, NULL, 1);
+               rcu_read_unlock();
+       }
+}
+

We have the (simpler imho)

const struct cpumask *mask = mm_cpumask(mm);
/* possibly AND it with a user requested mask */
smp_call_function_many(mask, ipi_func, ....);

which I think will be faster on some archs (that support broadcast) and have fewer problems with out of sync values (though we do have to check in our IPI function that we haven't context switched out.

Am I missing why this won't work?

Quoted 10 lines · Andrew Hunter

Quoted 5 lines · Paul E. McKenney

Quoted 4 lines · Avi Kivity

IPIing only running threads of my process would be perfect. In fact I might even be able to make use of "membarrier these threads please" to reduce IPIs, when I change the topology from fully connected to something more sparse, on larger machines.

We do this as well--sometimes we only need RSEQ fences against specific CPU(s), and thus pass a subset.

Sounds like a good future enhancement, probably requiring a new syscall to accommodate the cpumask.

Quoted 26 lines

Quoted 5 lines

kernel/membarrier.c +5 -0

+static void membarrier_private_expedited_ipi_each(void)
+{
+       int cpu;
+
+       for_each_online_cpu(cpu) {

kernel/membarrier.c line 54

Quoted 10 lines

kernel/membarrier.c +10 -0

+               struct task_struct *p;
+
+               rcu_read_lock();
+               p = task_rcu_dereference(&cpu_rq(cpu)->curr);
+               if (p && p->mm == current->mm)
+                       smp_call_function_single(cpu, ipi_mb, NULL, 1);
+               rcu_read_unlock();
+       }
+}
+

We have the (simpler imho)

const struct cpumask *mask = mm_cpumask(mm);
/* possibly AND it with a user requested mask */
smp_call_function_many(mask, ipi_func, ....);

which I think will be faster on some archs (that support broadcast) and have fewer problems with out of sync values (though we do have to check in our IPI function that we haven't context switched out.

Quoted 1 line

Am I missing why this won't work?

My impression is that some architectures don't provide the needed ordering in this case, and also that some architectures support ASIDs and would thus IPI CPUs that weren't actually running threads in the process at the current time.

Mathieu, anything I am missing?

Hello!

But my main question is whether the throttling shown below is acceptable for your use cases, namely only one expedited sys_membarrier() permitted per scheduling-clock period (1 millisecond on many platforms), with any excess being silently converted to non-expedited form. The reason for the throttling is concerns about DoS attacks based on user code with a tight loop invoking this system call.

kernel/membarrier.c +5 -0

+			} else {
+				synchronize_sched_expedited();
+			}
+		}
+		return 0;

Hi Paul,

Thanks for looking at this again!

Quoted 8 lines · Paul E. McKenney

Hello!

But my main question is whether the throttling shown below is acceptable for your use cases, namely only one expedited sys_membarrier() permitted per scheduling-clock period (1 millisecond on many platforms), with any excess being silently converted to non-expedited form. The reason for the throttling is concerns about DoS attacks based on user code with a tight loop invoking this system call.

We've been using sys_membarrier for the last year or so in a handful of places with no issues. Recently we made it an option in our hazard pointers implementation, giving us something with performance between hazard pointers and RCU:

https://github.com/facebook/folly/blob/master/folly/experimental/hazptr/hazptr-impl.h#L555

Currently hazard pointers tries to free retired memory the same thread that did the retire(), so the latency spiked for workloads that were
retire() heavy. For the moment we dropped back to using mprotect
hacks.

I've tested Mathieu's v4 patch, it works great. We currently don't have any cases where we need SHARED.

I also tested the rate-limited version, while better than the current non-EXPEDITED SHARED version, we still hit the slow path pretty often. I agree with other commenters that returning an error code instead of silently slowing down might be better.

kernel/membarrier.c SYSCALL_DEFINE2(membarrier, int, cmd, int, flags) · line 76

Quoted 9 lines

kernel/membarrier.c +9 -0

+	case MEMBARRIER_CMD_SHARED_EXPEDITED:
+		if (num_online_cpus() > 1) {
+			static unsigned long lastexp;
+			unsigned long j;
+
+			j = jiffies;
+			if (READ_ONCE(lastexp) == j) {
+				synchronize_sched();
+				WRITE_ONCE(lastexp, j);

It looks like this update of lastexp should be in the other branch?

Quoted 5 lines

kernel/membarrier.c +5 -0

+			} else {
+				synchronize_sched_expedited();
+			}
+		}
+		return 0;