[PATCH v2 0/4] MCS Lock: MCS lock code cleanup and optimizations

[PATCH v2 0/4] MCS Lock: MCS lock code cleanup and optimizations

[Tim Chen]

In this patch series, we separated out the MCS lock code which was
previously embedded in the mutex.c.  This allows for easier reuse of
MCS lock in other places like rwsem and qrwlock.  We also did some micro
optimizations and barrier cleanup.

This patches were previously part of the rwsem optimization patch series
but now we spearate them out.

Tim Chen

v2:
1. change export mcs_spin_lock as a GPL export symbol
2. corrected mcs_spin_lock to references


Jason Low (2):
  MCS Lock: optimizations and extra comments
  MCS Lock: Barrier corrections

Tim Chen (1):
  MCS Lock: Restructure the MCS lock defines and locking code into its
    own file

Waiman Long (1):
  MCS Lock: Make mcs_spinlock.h includable in other files

 include/linux/mcs_spinlock.h |   99 ++++++++++++++++++++++++++++++++++++++++++
 include/linux/mutex.h        |    5 +-
 kernel/Makefile              |    6 +-
 kernel/mcs_spinlock.c        |   21 +++++++++
 kernel/mutex.c               |   60 +++----------------------
 5 files changed, 133 insertions(+), 58 deletions(-)
 create mode 100644 include/linux/mcs_spinlock.h
 create mode 100644 kernel/mcs_spinlock.c

-- 
1.7.4.4


--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [PATCH v2 0/4] MCS Lock: MCS lock code cleanup and optimizations

[Michel Lespinasse]

On Tue, Nov 5, 2013 at 9:42 AM, Tim Chen <tim.c.chen@linux.intel.com> wrote:
> In this patch series, we separated out the MCS lock code which was
> previously embedded in the mutex.c.  This allows for easier reuse of
> MCS lock in other places like rwsem and qrwlock.  We also did some micro
> optimizations and barrier cleanup.
>
> This patches were previously part of the rwsem optimization patch series
> but now we spearate them out.
>
> Tim Chen
>
> v2:
> 1. change export mcs_spin_lock as a GPL export symbol
> 2. corrected mcs_spin_lock to references
>
> Jason Low (2):
>   MCS Lock: optimizations and extra comments
>   MCS Lock: Barrier corrections
>
> Tim Chen (1):
>   MCS Lock: Restructure the MCS lock defines and locking code into its
>     own file
>
> Waiman Long (1):
>   MCS Lock: Make mcs_spinlock.h includable in other files
>
>  include/linux/mcs_spinlock.h |   99 ++++++++++++++++++++++++++++++++++++++++++
>  include/linux/mutex.h        |    5 +-
>  kernel/Makefile              |    6 +-
>  kernel/mcs_spinlock.c        |   21 +++++++++
>  kernel/mutex.c               |   60 +++----------------------
>  5 files changed, 133 insertions(+), 58 deletions(-)
>  create mode 100644 include/linux/mcs_spinlock.h
>  create mode 100644 kernel/mcs_spinlock.c

What base kernel does this apply over ?

-- 
Michel "Walken" Lespinasse
A program is never fully debugged until the last user dies.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [PATCH v2 0/4] MCS Lock: MCS lock code cleanup and optimizations

[Tim Chen]

On Tue, 2013-11-05 at 13:14 -0800, Michel Lespinasse wrote:
> On Tue, Nov 5, 2013 at 9:42 AM, Tim Chen <tim.c.chen@linux.intel.com> wrote:
> > In this patch series, we separated out the MCS lock code which was
> > previously embedded in the mutex.c.  This allows for easier reuse of
> > MCS lock in other places like rwsem and qrwlock.  We also did some micro
> > optimizations and barrier cleanup.
> >
> > This patches were previously part of the rwsem optimization patch series
> > but now we spearate them out.
> >
> > Tim Chen
> >
> > v2:
> > 1. change export mcs_spin_lock as a GPL export symbol
> > 2. corrected mcs_spin_lock to references
> >
> > Jason Low (2):
> >   MCS Lock: optimizations and extra comments
> >   MCS Lock: Barrier corrections
> >
> > Tim Chen (1):
> >   MCS Lock: Restructure the MCS lock defines and locking code into its
> >     own file
> >
> > Waiman Long (1):
> >   MCS Lock: Make mcs_spinlock.h includable in other files
> >
> >  include/linux/mcs_spinlock.h |   99 ++++++++++++++++++++++++++++++++++++++++++
> >  include/linux/mutex.h        |    5 +-
> >  kernel/Makefile              |    6 +-
> >  kernel/mcs_spinlock.c        |   21 +++++++++
> >  kernel/mutex.c               |   60 +++----------------------
> >  5 files changed, 133 insertions(+), 58 deletions(-)
> >  create mode 100644 include/linux/mcs_spinlock.h
> >  create mode 100644 kernel/mcs_spinlock.c
> 
> What base kernel does this apply over ?
> 

Should be applicable on latest v3.12-rc7.

Tim

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

[PATCH v2 1/4] MCS Lock: Restructure the MCS lock defines and locking code into its own file

[Tim Chen]

We will need the MCS lock code for doing optimistic spinning for rwsem.
Extracting the MCS code from mutex.c and put into its own file allow us
to reuse this code easily for rwsem.

Reviewed-by: Ingo Molnar <mingo@elte.hu>
Reviewed-by: Peter Zijlstra <peterz@infradead.org>
Signed-off-by: Tim Chen <tim.c.chen@linux.intel.com>
Signed-off-by: Davidlohr Bueso <davidlohr@hp.com>
---
 include/linux/mcs_spinlock.h |   64 ++++++++++++++++++++++++++++++++++++++++++
 include/linux/mutex.h        |    5 ++-
 kernel/mutex.c               |   60 ++++----------------------------------
 3 files changed, 74 insertions(+), 55 deletions(-)
 create mode 100644 include/linux/mcs_spinlock.h

diff --git a/include/linux/mcs_spinlock.h b/include/linux/mcs_spinlock.h
new file mode 100644
index 0000000..b5de3b0
--- /dev/null
+++ b/include/linux/mcs_spinlock.h
@@ -0,0 +1,64 @@
+/*
+ * MCS lock defines
+ *
+ * This file contains the main data structure and API definitions of MCS lock.
+ *
+ * The MCS lock (proposed by Mellor-Crummey and Scott) is a simple spin-lock
+ * with the desirable properties of being fair, and with each cpu trying
+ * to acquire the lock spinning on a local variable.
+ * It avoids expensive cache bouncings that common test-and-set spin-lock
+ * implementations incur.
+ */
+#ifndef __LINUX_MCS_SPINLOCK_H
+#define __LINUX_MCS_SPINLOCK_H
+
+struct mcs_spinlock {
+	struct mcs_spinlock *next;
+	int locked; /* 1 if lock acquired */
+};
+
+/*
+ * We don't inline mcs_spin_lock() so that perf can correctly account for the
+ * time spent in this lock function.
+ */
+static noinline
+void mcs_spin_lock(struct mcs_spinlock **lock, struct mcs_spinlock *node)
+{
+	struct mcs_spinlock *prev;
+
+	/* Init node */
+	node->locked = 0;
+	node->next   = NULL;
+
+	prev = xchg(lock, node);
+	if (likely(prev == NULL)) {
+		/* Lock acquired */
+		node->locked = 1;
+		return;
+	}
+	ACCESS_ONCE(prev->next) = node;
+	smp_wmb();
+	/* Wait until the lock holder passes the lock down */
+	while (!ACCESS_ONCE(node->locked))
+		arch_mutex_cpu_relax();
+}
+
+static void mcs_spin_unlock(struct mcs_spinlock **lock, struct mcs_spinlock *node)
+{
+	struct mcs_spinlock *next = ACCESS_ONCE(node->next);
+
+	if (likely(!next)) {
+		/*
+		 * Release the lock by setting it to NULL
+		 */
+		if (cmpxchg(lock, node, NULL) == node)
+			return;
+		/* Wait until the next pointer is set */
+		while (!(next = ACCESS_ONCE(node->next)))
+			arch_mutex_cpu_relax();
+	}
+	ACCESS_ONCE(next->locked) = 1;
+	smp_wmb();
+}
+
+#endif /* __LINUX_MCS_SPINLOCK_H */
diff --git a/include/linux/mutex.h b/include/linux/mutex.h
index ccd4260..e6eaeea 100644
--- a/include/linux/mutex.h
+++ b/include/linux/mutex.h
@@ -46,6 +46,7 @@
  * - detects multi-task circular deadlocks and prints out all affected
  *   locks and tasks (and only those tasks)
  */
+struct mcs_spinlock;
 struct mutex {
 	/* 1: unlocked, 0: locked, negative: locked, possible waiters */
 	atomic_t		count;
@@ -55,7 +56,7 @@ struct mutex {
 	struct task_struct	*owner;
 #endif
 #ifdef CONFIG_MUTEX_SPIN_ON_OWNER
-	void			*spin_mlock;	/* Spinner MCS lock */
+	struct mcs_spinlock	*mcs_lock;	/* Spinner MCS lock */
 #endif
 #ifdef CONFIG_DEBUG_MUTEXES
 	const char 		*name;
@@ -179,4 +180,4 @@ extern int atomic_dec_and_mutex_lock(atomic_t *cnt, struct mutex *lock);
 #define arch_mutex_cpu_relax()	cpu_relax()
 #endif
 
-#endif
+#endif /* __LINUX_MUTEX_H */
diff --git a/kernel/mutex.c b/kernel/mutex.c
index 6d647ae..4640731 100644
--- a/kernel/mutex.c
+++ b/kernel/mutex.c
@@ -25,6 +25,7 @@
 #include <linux/spinlock.h>
 #include <linux/interrupt.h>
 #include <linux/debug_locks.h>
+#include <linux/mcs_spinlock.h>
 
 /*
  * In the DEBUG case we are using the "NULL fastpath" for mutexes,
@@ -52,7 +53,7 @@ __mutex_init(struct mutex *lock, const char *name, struct lock_class_key *key)
 	INIT_LIST_HEAD(&lock->wait_list);
 	mutex_clear_owner(lock);
 #ifdef CONFIG_MUTEX_SPIN_ON_OWNER
-	lock->spin_mlock = NULL;
+	lock->mcs_lock = NULL;
 #endif
 
 	debug_mutex_init(lock, name, key);
@@ -111,54 +112,7 @@ EXPORT_SYMBOL(mutex_lock);
  * more or less simultaneously, the spinners need to acquire a MCS lock
  * first before spinning on the owner field.
  *
- * We don't inline mspin_lock() so that perf can correctly account for the
- * time spent in this lock function.
  */
-struct mspin_node {
-	struct mspin_node *next ;
-	int		  locked;	/* 1 if lock acquired */
-};
-#define	MLOCK(mutex)	((struct mspin_node **)&((mutex)->spin_mlock))
-
-static noinline
-void mspin_lock(struct mspin_node **lock, struct mspin_node *node)
-{
-	struct mspin_node *prev;
-
-	/* Init node */
-	node->locked = 0;
-	node->next   = NULL;
-
-	prev = xchg(lock, node);
-	if (likely(prev == NULL)) {
-		/* Lock acquired */
-		node->locked = 1;
-		return;
-	}
-	ACCESS_ONCE(prev->next) = node;
-	smp_wmb();
-	/* Wait until the lock holder passes the lock down */
-	while (!ACCESS_ONCE(node->locked))
-		arch_mutex_cpu_relax();
-}
-
-static void mspin_unlock(struct mspin_node **lock, struct mspin_node *node)
-{
-	struct mspin_node *next = ACCESS_ONCE(node->next);
-
-	if (likely(!next)) {
-		/*
-		 * Release the lock by setting it to NULL
-		 */
-		if (cmpxchg(lock, node, NULL) == node)
-			return;
-		/* Wait until the next pointer is set */
-		while (!(next = ACCESS_ONCE(node->next)))
-			arch_mutex_cpu_relax();
-	}
-	ACCESS_ONCE(next->locked) = 1;
-	smp_wmb();
-}
 
 /*
  * Mutex spinning code migrated from kernel/sched/core.c
@@ -448,7 +402,7 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass,
 
 	for (;;) {
 		struct task_struct *owner;
-		struct mspin_node  node;
+		struct mcs_spinlock  node;
 
 		if (!__builtin_constant_p(ww_ctx == NULL) && ww_ctx->acquired > 0) {
 			struct ww_mutex *ww;
@@ -470,10 +424,10 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass,
 		 * If there's an owner, wait for it to either
 		 * release the lock or go to sleep.
 		 */
-		mspin_lock(MLOCK(lock), &node);
+		mcs_spin_lock(&lock->mcs_lock, &node);
 		owner = ACCESS_ONCE(lock->owner);
 		if (owner && !mutex_spin_on_owner(lock, owner)) {
-			mspin_unlock(MLOCK(lock), &node);
+			mcs_spin_unlock(&lock->mcs_lock, &node);
 			goto slowpath;
 		}
 
@@ -488,11 +442,11 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass,
 			}
 
 			mutex_set_owner(lock);
-			mspin_unlock(MLOCK(lock), &node);
+			mcs_spin_unlock(&lock->mcs_lock, &node);
 			preempt_enable();
 			return 0;
 		}
-		mspin_unlock(MLOCK(lock), &node);
+		mcs_spin_unlock(&lock->mcs_lock, &node);
 
 		/*
 		 * When there's no owner, we might have preempted between the
-- 
1.7.4.4



--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

[PATCH v2 2/4] MCS Lock: optimizations and extra comments

[Tim Chen]

Remove unnecessary operation and make the cmpxchg(lock, node, NULL) == node
check in mcs_spin_unlock() likely() as it is likely that a race did not occur
most of the time.

Also add in more comments describing how the local node is used in MCS locks.

Reviewed-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
Reviewed-by: Tim Chen <tim.c.chen@linux.intel.com>
Signed-off-by: Jason Low <jason.low2@hp.com>
---
 include/linux/mcs_spinlock.h |   13 +++++++++++--
 1 files changed, 11 insertions(+), 2 deletions(-)

diff --git a/include/linux/mcs_spinlock.h b/include/linux/mcs_spinlock.h
index b5de3b0..96f14299 100644
--- a/include/linux/mcs_spinlock.h
+++ b/include/linux/mcs_spinlock.h
@@ -18,6 +18,12 @@ struct mcs_spinlock {
 };
 
 /*
+ * In order to acquire the lock, the caller should declare a local node and
+ * pass a reference of the node to this function in addition to the lock.
+ * If the lock has already been acquired, then this will proceed to spin
+ * on this node->locked until the previous lock holder sets the node->locked
+ * in mcs_spin_unlock().
+ *
  * We don't inline mcs_spin_lock() so that perf can correctly account for the
  * time spent in this lock function.
  */
@@ -33,7 +39,6 @@ void mcs_spin_lock(struct mcs_spinlock **lock, struct mcs_spinlock *node)
 	prev = xchg(lock, node);
 	if (likely(prev == NULL)) {
 		/* Lock acquired */
-		node->locked = 1;
 		return;
 	}
 	ACCESS_ONCE(prev->next) = node;
@@ -43,6 +48,10 @@ void mcs_spin_lock(struct mcs_spinlock **lock, struct mcs_spinlock *node)
 		arch_mutex_cpu_relax();
 }
 
+/*
+ * Releases the lock. The caller should pass in the corresponding node that
+ * was used to acquire the lock.
+ */
 static void mcs_spin_unlock(struct mcs_spinlock **lock, struct mcs_spinlock *node)
 {
 	struct mcs_spinlock *next = ACCESS_ONCE(node->next);
@@ -51,7 +60,7 @@ static void mcs_spin_unlock(struct mcs_spinlock **lock, struct mcs_spinlock *nod
 		/*
 		 * Release the lock by setting it to NULL
 		 */
-		if (cmpxchg(lock, node, NULL) == node)
+		if (likely(cmpxchg(lock, node, NULL) == node))
 			return;
 		/* Wait until the next pointer is set */
 		while (!(next = ACCESS_ONCE(node->next)))
-- 
1.7.4.4



--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

[PATCH v2 3/4] MCS Lock: Barrier corrections

[Tim Chen]

This patch corrects the way memory barriers are used in the MCS lock
and removes ones that are not needed. Also add comments on all barriers.

Reviewed-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
Reviewed-by: Tim Chen <tim.c.chen@linux.intel.com>
Signed-off-by: Jason Low <jason.low2@hp.com>
---
 include/linux/mcs_spinlock.h |   13 +++++++++++--
 1 files changed, 11 insertions(+), 2 deletions(-)

diff --git a/include/linux/mcs_spinlock.h b/include/linux/mcs_spinlock.h
index 96f14299..93d445d 100644
--- a/include/linux/mcs_spinlock.h
+++ b/include/linux/mcs_spinlock.h
@@ -36,16 +36,19 @@ void mcs_spin_lock(struct mcs_spinlock **lock, struct mcs_spinlock *node)
 	node->locked = 0;
 	node->next   = NULL;
 
+	/* xchg() provides a memory barrier */
 	prev = xchg(lock, node);
 	if (likely(prev == NULL)) {
 		/* Lock acquired */
 		return;
 	}
 	ACCESS_ONCE(prev->next) = node;
-	smp_wmb();
 	/* Wait until the lock holder passes the lock down */
 	while (!ACCESS_ONCE(node->locked))
 		arch_mutex_cpu_relax();
+
+	/* Make sure subsequent operations happen after the lock is acquired */
+	smp_rmb();
 }
 
 /*
@@ -58,6 +61,7 @@ static void mcs_spin_unlock(struct mcs_spinlock **lock, struct mcs_spinlock *nod
 
 	if (likely(!next)) {
 		/*
+		 * cmpxchg() provides a memory barrier.
 		 * Release the lock by setting it to NULL
 		 */
 		if (likely(cmpxchg(lock, node, NULL) == node))
@@ -65,9 +69,14 @@ static void mcs_spin_unlock(struct mcs_spinlock **lock, struct mcs_spinlock *nod
 		/* Wait until the next pointer is set */
 		while (!(next = ACCESS_ONCE(node->next)))
 			arch_mutex_cpu_relax();
+	} else {
+		/*
+		 * Make sure all operations within the critical section
+		 * happen before the lock is released.
+		 */
+		smp_wmb();
 	}
 	ACCESS_ONCE(next->locked) = 1;
-	smp_wmb();
 }
 
 #endif /* __LINUX_MCS_SPINLOCK_H */
-- 
1.7.4.4



--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [PATCH v2 3/4] MCS Lock: Barrier corrections

[Will Deacon]

On Tue, Nov 05, 2013 at 05:42:36PM +0000, Tim Chen wrote:
> This patch corrects the way memory barriers are used in the MCS lock
> and removes ones that are not needed. Also add comments on all barriers.

Hmm, I see that you're fixing up the barriers, but I still don't completely
understand how what you have is correct. Hopefully you can help me out :)

> Reviewed-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
> Reviewed-by: Tim Chen <tim.c.chen@linux.intel.com>
> Signed-off-by: Jason Low <jason.low2@hp.com>
> ---
>  include/linux/mcs_spinlock.h |   13 +++++++++++--
>  1 files changed, 11 insertions(+), 2 deletions(-)
> 
> diff --git a/include/linux/mcs_spinlock.h b/include/linux/mcs_spinlock.h
> index 96f14299..93d445d 100644
> --- a/include/linux/mcs_spinlock.h
> +++ b/include/linux/mcs_spinlock.h
> @@ -36,16 +36,19 @@ void mcs_spin_lock(struct mcs_spinlock **lock, struct mcs_spinlock *node)
>  	node->locked = 0;
>  	node->next   = NULL;
>  
> +	/* xchg() provides a memory barrier */
>  	prev = xchg(lock, node);
>  	if (likely(prev == NULL)) {
>  		/* Lock acquired */
>  		return;
>  	}
>  	ACCESS_ONCE(prev->next) = node;
> -	smp_wmb();
>  	/* Wait until the lock holder passes the lock down */
>  	while (!ACCESS_ONCE(node->locked))
>  		arch_mutex_cpu_relax();
> +
> +	/* Make sure subsequent operations happen after the lock is acquired */
> +	smp_rmb();

Ok, so this is an smp_rmb() because we assume that stores aren't speculated,
right? (i.e. the control dependency above is enough for stores to be ordered
with respect to taking the lock)...

>  }
>  
>  /*
> @@ -58,6 +61,7 @@ static void mcs_spin_unlock(struct mcs_spinlock **lock, struct mcs_spinlock *nod
>  
>  	if (likely(!next)) {
>  		/*
> +		 * cmpxchg() provides a memory barrier.
>  		 * Release the lock by setting it to NULL
>  		 */
>  		if (likely(cmpxchg(lock, node, NULL) == node))
> @@ -65,9 +69,14 @@ static void mcs_spin_unlock(struct mcs_spinlock **lock, struct mcs_spinlock *nod
>  		/* Wait until the next pointer is set */
>  		while (!(next = ACCESS_ONCE(node->next)))
>  			arch_mutex_cpu_relax();
> +	} else {
> +		/*
> +		 * Make sure all operations within the critical section
> +		 * happen before the lock is released.
> +		 */
> +		smp_wmb();

...but I don't see what prevents reads inside the critical section from
moving across the smp_wmb() here.

What am I missing?

Will

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [PATCH v2 3/4] MCS Lock: Barrier corrections

[Tim Chen]

On Tue, 2013-11-05 at 18:37 +0000, Will Deacon wrote:
> On Tue, Nov 05, 2013 at 05:42:36PM +0000, Tim Chen wrote:
> > This patch corrects the way memory barriers are used in the MCS lock
> > and removes ones that are not needed. Also add comments on all barriers.
> 
> Hmm, I see that you're fixing up the barriers, but I still don't completely
> understand how what you have is correct. Hopefully you can help me out :)
> 
> > Reviewed-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
> > Reviewed-by: Tim Chen <tim.c.chen@linux.intel.com>
> > Signed-off-by: Jason Low <jason.low2@hp.com>
> > ---
> >  include/linux/mcs_spinlock.h |   13 +++++++++++--
> >  1 files changed, 11 insertions(+), 2 deletions(-)
> > 
> > diff --git a/include/linux/mcs_spinlock.h b/include/linux/mcs_spinlock.h
> > index 96f14299..93d445d 100644
> > --- a/include/linux/mcs_spinlock.h
> > +++ b/include/linux/mcs_spinlock.h
> > @@ -36,16 +36,19 @@ void mcs_spin_lock(struct mcs_spinlock **lock, struct mcs_spinlock *node)
> >  	node->locked = 0;
> >  	node->next   = NULL;
> >  
> > +	/* xchg() provides a memory barrier */
> >  	prev = xchg(lock, node);
> >  	if (likely(prev == NULL)) {
> >  		/* Lock acquired */
> >  		return;
> >  	}
> >  	ACCESS_ONCE(prev->next) = node;
> > -	smp_wmb();
> >  	/* Wait until the lock holder passes the lock down */
> >  	while (!ACCESS_ONCE(node->locked))
> >  		arch_mutex_cpu_relax();
> > +
> > +	/* Make sure subsequent operations happen after the lock is acquired */
> > +	smp_rmb();
> 
> Ok, so this is an smp_rmb() because we assume that stores aren't speculated,
> right? (i.e. the control dependency above is enough for stores to be ordered
> with respect to taking the lock)...
> 
> >  }
> >  
> >  /*
> > @@ -58,6 +61,7 @@ static void mcs_spin_unlock(struct mcs_spinlock **lock, struct mcs_spinlock *nod
> >  
> >  	if (likely(!next)) {
> >  		/*
> > +		 * cmpxchg() provides a memory barrier.
> >  		 * Release the lock by setting it to NULL
> >  		 */
> >  		if (likely(cmpxchg(lock, node, NULL) == node))
> > @@ -65,9 +69,14 @@ static void mcs_spin_unlock(struct mcs_spinlock **lock, struct mcs_spinlock *nod
> >  		/* Wait until the next pointer is set */
> >  		while (!(next = ACCESS_ONCE(node->next)))
> >  			arch_mutex_cpu_relax();
> > +	} else {
> > +		/*
> > +		 * Make sure all operations within the critical section
> > +		 * happen before the lock is released.
> > +		 */
> > +		smp_wmb();
> 
> ...but I don't see what prevents reads inside the critical section from
> moving across the smp_wmb() here.

This is to prevent any read in next critical section from
creeping up before write in the previous critical section
has completed

e.g.
CPU 1 execute
        mcs_lock
        x = 1;
        ...
        x = 2;
        mcs_unlock

and CPU 2 execute

        mcs_lock
        y = x;
        ...
        mcs_unlock

We expect y to be 2 after the "y = x" assignment. Without the proper 
rmb in lock and wmb in unlock, y could be 1 for CPU 2 with 
speculative read (i.e. before the x=2 assignment is completed).

Tim

> 
> What am I missing?
> 
> Will


--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [PATCH v2 3/4] MCS Lock: Barrier corrections

[Peter Zijlstra]

On Tue, Nov 05, 2013 at 11:21:57AM -0800, Tim Chen wrote:
> On Tue, 2013-11-05 at 18:37 +0000, Will Deacon wrote:
> > On Tue, Nov 05, 2013 at 05:42:36PM +0000, Tim Chen wrote:
> > > This patch corrects the way memory barriers are used in the MCS lock
> > > and removes ones that are not needed. Also add comments on all barriers.
> > 
> > Hmm, I see that you're fixing up the barriers, but I still don't completely
> > understand how what you have is correct. Hopefully you can help me out :)
> > 
> > > Reviewed-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
> > > Reviewed-by: Tim Chen <tim.c.chen@linux.intel.com>
> > > Signed-off-by: Jason Low <jason.low2@hp.com>
> > > ---
> > >  include/linux/mcs_spinlock.h |   13 +++++++++++--
> > >  1 files changed, 11 insertions(+), 2 deletions(-)
> > > 
> > > diff --git a/include/linux/mcs_spinlock.h b/include/linux/mcs_spinlock.h
> > > index 96f14299..93d445d 100644
> > > --- a/include/linux/mcs_spinlock.h
> > > +++ b/include/linux/mcs_spinlock.h
> > > @@ -36,16 +36,19 @@ void mcs_spin_lock(struct mcs_spinlock **lock, struct mcs_spinlock *node)
> > >  	node->locked = 0;
> > >  	node->next   = NULL;
> > >  
> > > +	/* xchg() provides a memory barrier */
> > >  	prev = xchg(lock, node);
> > >  	if (likely(prev == NULL)) {
> > >  		/* Lock acquired */
> > >  		return;
> > >  	}
> > >  	ACCESS_ONCE(prev->next) = node;
> > > -	smp_wmb();
> > >  	/* Wait until the lock holder passes the lock down */
> > >  	while (!ACCESS_ONCE(node->locked))
> > >  		arch_mutex_cpu_relax();
> > > +
> > > +	/* Make sure subsequent operations happen after the lock is acquired */
> > > +	smp_rmb();
> > 
> > Ok, so this is an smp_rmb() because we assume that stores aren't speculated,
> > right? (i.e. the control dependency above is enough for stores to be ordered
> > with respect to taking the lock)...

PaulMck completely confused me a few days ago with control dependencies
etc.. Pretty much saying that C/C++ doesn't do those.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [PATCH v2 3/4] MCS Lock: Barrier corrections

[Tim Chen]

On Tue, 2013-11-05 at 22:18 +0100, Peter Zijlstra wrote:
> On Tue, Nov 05, 2013 at 11:21:57AM -0800, Tim Chen wrote:
> > On Tue, 2013-11-05 at 18:37 +0000, Will Deacon wrote:
> > > On Tue, Nov 05, 2013 at 05:42:36PM +0000, Tim Chen wrote:
> > > > This patch corrects the way memory barriers are used in the MCS lock
> > > > and removes ones that are not needed. Also add comments on all barriers.
> > > 
> > > Hmm, I see that you're fixing up the barriers, but I still don't completely
> > > understand how what you have is correct. Hopefully you can help me out :)
> > > 
> > > > Reviewed-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
> > > > Reviewed-by: Tim Chen <tim.c.chen@linux.intel.com>
> > > > Signed-off-by: Jason Low <jason.low2@hp.com>
> > > > ---
> > > >  include/linux/mcs_spinlock.h |   13 +++++++++++--
> > > >  1 files changed, 11 insertions(+), 2 deletions(-)
> > > > 
> > > > diff --git a/include/linux/mcs_spinlock.h b/include/linux/mcs_spinlock.h
> > > > index 96f14299..93d445d 100644
> > > > --- a/include/linux/mcs_spinlock.h
> > > > +++ b/include/linux/mcs_spinlock.h
> > > > @@ -36,16 +36,19 @@ void mcs_spin_lock(struct mcs_spinlock **lock, struct mcs_spinlock *node)
> > > >  	node->locked = 0;
> > > >  	node->next   = NULL;
> > > >  
> > > > +	/* xchg() provides a memory barrier */
> > > >  	prev = xchg(lock, node);
> > > >  	if (likely(prev == NULL)) {
> > > >  		/* Lock acquired */
> > > >  		return;
> > > >  	}
> > > >  	ACCESS_ONCE(prev->next) = node;
> > > > -	smp_wmb();
> > > >  	/* Wait until the lock holder passes the lock down */
> > > >  	while (!ACCESS_ONCE(node->locked))
> > > >  		arch_mutex_cpu_relax();
> > > > +
> > > > +	/* Make sure subsequent operations happen after the lock is acquired */
> > > > +	smp_rmb();
> > > 
> > > Ok, so this is an smp_rmb() because we assume that stores aren't speculated,
> > > right? (i.e. the control dependency above is enough for stores to be ordered
> > > with respect to taking the lock)...
> 

The smp_rmb was put in to make sure that the lock
is indeed set before we start doing speculative reads in next critical
section.

Wonder if your concern is about the possibility of write in next 
critical section bleeding into read in previous critical section?

If reads and writes are re-ordered in previous critical section before mcs_spin_unlock, 
it may be possible that the previous critical section is still
reading when it set the lock for the next mcs in mcs_spin_unlock.  
This allows the next critical section to start writing prematurely, before 
previous critical section finished all reads.  

If this concern is valid, we should change the smp_wmb() to smp_mb()
in the unlock function, to make sure previous critical section has
completed all operations before next section starts.


> PaulMck completely confused me a few days ago with control dependencies
> etc.. Pretty much saying that C/C++ doesn't do those.

Will appreciate feedback getting the barriers right.

Thanks.

Tim

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [PATCH v2 3/4] MCS Lock: Barrier corrections

[Will Deacon]

On Wed, Nov 06, 2013 at 01:25:53AM +0000, Tim Chen wrote:
> On Tue, 2013-11-05 at 22:18 +0100, Peter Zijlstra wrote:
> > On Tue, Nov 05, 2013 at 11:21:57AM -0800, Tim Chen wrote:
> > > On Tue, 2013-11-05 at 18:37 +0000, Will Deacon wrote:
> > > > On Tue, Nov 05, 2013 at 05:42:36PM +0000, Tim Chen wrote:
> > > > > This patch corrects the way memory barriers are used in the MCS lock
> > > > > and removes ones that are not needed. Also add comments on all barriers.
> > > > 
> > > > Hmm, I see that you're fixing up the barriers, but I still don't completely
> > > > understand how what you have is correct. Hopefully you can help me out :)
> > > > 
> > > > > Reviewed-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
> > > > > Reviewed-by: Tim Chen <tim.c.chen@linux.intel.com>
> > > > > Signed-off-by: Jason Low <jason.low2@hp.com>
> > > > > ---
> > > > >  include/linux/mcs_spinlock.h |   13 +++++++++++--
> > > > >  1 files changed, 11 insertions(+), 2 deletions(-)
> > > > > 
> > > > > diff --git a/include/linux/mcs_spinlock.h b/include/linux/mcs_spinlock.h
> > > > > index 96f14299..93d445d 100644
> > > > > --- a/include/linux/mcs_spinlock.h
> > > > > +++ b/include/linux/mcs_spinlock.h
> > > > > @@ -36,16 +36,19 @@ void mcs_spin_lock(struct mcs_spinlock **lock, struct mcs_spinlock *node)
> > > > >  	node->locked = 0;
> > > > >  	node->next   = NULL;
> > > > >  
> > > > > +	/* xchg() provides a memory barrier */
> > > > >  	prev = xchg(lock, node);
> > > > >  	if (likely(prev == NULL)) {
> > > > >  		/* Lock acquired */
> > > > >  		return;
> > > > >  	}
> > > > >  	ACCESS_ONCE(prev->next) = node;
> > > > > -	smp_wmb();
> > > > >  	/* Wait until the lock holder passes the lock down */
> > > > >  	while (!ACCESS_ONCE(node->locked))
> > > > >  		arch_mutex_cpu_relax();
> > > > > +
> > > > > +	/* Make sure subsequent operations happen after the lock is acquired */
> > > > > +	smp_rmb();
> > > > 
> > > > Ok, so this is an smp_rmb() because we assume that stores aren't speculated,
> > > > right? (i.e. the control dependency above is enough for stores to be ordered
> > > > with respect to taking the lock)...
> > 
> 
> The smp_rmb was put in to make sure that the lock
> is indeed set before we start doing speculative reads in next critical
> section.
> 
> Wonder if your concern is about the possibility of write in next 
> critical section bleeding into read in previous critical section?

Correct. You want to ensure that all accesses (reads and writes) that occur in
program order after taking the lock occur inside the critical section.

> If reads and writes are re-ordered in previous critical section before mcs_spin_unlock, 
> it may be possible that the previous critical section is still
> reading when it set the lock for the next mcs in mcs_spin_unlock.  
> This allows the next critical section to start writing prematurely, before 
> previous critical section finished all reads.  
> 
> If this concern is valid, we should change the smp_wmb() to smp_mb()
> in the unlock function, to make sure previous critical section has
> completed all operations before next section starts.

smp_rmb() is defined only to order reads against reads, so relying on the
control dependency feels fragile. (On arm64, an smp_rmb() actually orders
reads against reads/writes).

> > PaulMck completely confused me a few days ago with control dependencies
> > etc.. Pretty much saying that C/C++ doesn't do those.
> 
> Will appreciate feedback getting the barriers right.

I'm not up to speed with C11, but an smp_mb() is certainly clearer to me,
especially if you change the smb_wmb() in the unlock code into an smp_mb
too.

Will

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [PATCH v2 3/4] MCS Lock: Barrier corrections

[Paul E. McKenney]

On Tue, Nov 05, 2013 at 10:18:03PM +0100, Peter Zijlstra wrote:
> On Tue, Nov 05, 2013 at 11:21:57AM -0800, Tim Chen wrote:
> > On Tue, 2013-11-05 at 18:37 +0000, Will Deacon wrote:
> > > On Tue, Nov 05, 2013 at 05:42:36PM +0000, Tim Chen wrote:
> > > > This patch corrects the way memory barriers are used in the MCS lock
> > > > and removes ones that are not needed. Also add comments on all barriers.
> > > 
> > > Hmm, I see that you're fixing up the barriers, but I still don't completely
> > > understand how what you have is correct. Hopefully you can help me out :)
> > > 
> > > > Reviewed-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
> > > > Reviewed-by: Tim Chen <tim.c.chen@linux.intel.com>
> > > > Signed-off-by: Jason Low <jason.low2@hp.com>
> > > > ---
> > > >  include/linux/mcs_spinlock.h |   13 +++++++++++--
> > > >  1 files changed, 11 insertions(+), 2 deletions(-)
> > > > 
> > > > diff --git a/include/linux/mcs_spinlock.h b/include/linux/mcs_spinlock.h
> > > > index 96f14299..93d445d 100644
> > > > --- a/include/linux/mcs_spinlock.h
> > > > +++ b/include/linux/mcs_spinlock.h
> > > > @@ -36,16 +36,19 @@ void mcs_spin_lock(struct mcs_spinlock **lock, struct mcs_spinlock *node)
> > > >  	node->locked = 0;
> > > >  	node->next   = NULL;
> > > >  
> > > > +	/* xchg() provides a memory barrier */
> > > >  	prev = xchg(lock, node);
> > > >  	if (likely(prev == NULL)) {
> > > >  		/* Lock acquired */
> > > >  		return;
> > > >  	}
> > > >  	ACCESS_ONCE(prev->next) = node;
> > > > -	smp_wmb();
> > > >  	/* Wait until the lock holder passes the lock down */
> > > >  	while (!ACCESS_ONCE(node->locked))
> > > >  		arch_mutex_cpu_relax();
> > > > +
> > > > +	/* Make sure subsequent operations happen after the lock is acquired */
> > > > +	smp_rmb();
> > > 
> > > Ok, so this is an smp_rmb() because we assume that stores aren't speculated,
> > > right? (i.e. the control dependency above is enough for stores to be ordered
> > > with respect to taking the lock)...
> 
> PaulMck completely confused me a few days ago with control dependencies
> etc.. Pretty much saying that C/C++ doesn't do those.

I remember that there was a subtlety here, but don't remember what it was...

And while I do remember reviewing this code, I don't find any evidence
that I gave my "Reviewed-by".  Tim/Jason, if I fat-fingered this, please
forward that email back to me.

							Thanx, Paul

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [PATCH v2 3/4] MCS Lock: Barrier corrections

[Tim Chen]

On Wed, 2013-11-06 at 06:45 -0800, Paul E. McKenney wrote:
> On Tue, Nov 05, 2013 at 10:18:03PM +0100, Peter Zijlstra wrote:
> > On Tue, Nov 05, 2013 at 11:21:57AM -0800, Tim Chen wrote:
> > > On Tue, 2013-11-05 at 18:37 +0000, Will Deacon wrote:
> > > > On Tue, Nov 05, 2013 at 05:42:36PM +0000, Tim Chen wrote:
> > > > > This patch corrects the way memory barriers are used in the MCS lock
> > > > > and removes ones that are not needed. Also add comments on all barriers.
> > > > 
> > > > Hmm, I see that you're fixing up the barriers, but I still don't completely
> > > > understand how what you have is correct. Hopefully you can help me out :)
> > > > 
> > > > > Reviewed-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
> > > > > Reviewed-by: Tim Chen <tim.c.chen@linux.intel.com>
> > > > > Signed-off-by: Jason Low <jason.low2@hp.com>
> > > > > ---
> > > > >  include/linux/mcs_spinlock.h |   13 +++++++++++--
> > > > >  1 files changed, 11 insertions(+), 2 deletions(-)
> > > > > 
> > > > > diff --git a/include/linux/mcs_spinlock.h b/include/linux/mcs_spinlock.h
> > > > > index 96f14299..93d445d 100644
> > > > > --- a/include/linux/mcs_spinlock.h
> > > > > +++ b/include/linux/mcs_spinlock.h
> > > > > @@ -36,16 +36,19 @@ void mcs_spin_lock(struct mcs_spinlock **lock, struct mcs_spinlock *node)
> > > > >  	node->locked = 0;
> > > > >  	node->next   = NULL;
> > > > >  
> > > > > +	/* xchg() provides a memory barrier */
> > > > >  	prev = xchg(lock, node);
> > > > >  	if (likely(prev == NULL)) {
> > > > >  		/* Lock acquired */
> > > > >  		return;
> > > > >  	}
> > > > >  	ACCESS_ONCE(prev->next) = node;
> > > > > -	smp_wmb();
> > > > >  	/* Wait until the lock holder passes the lock down */
> > > > >  	while (!ACCESS_ONCE(node->locked))
> > > > >  		arch_mutex_cpu_relax();
> > > > > +
> > > > > +	/* Make sure subsequent operations happen after the lock is acquired */
> > > > > +	smp_rmb();
> > > > 
> > > > Ok, so this is an smp_rmb() because we assume that stores aren't speculated,
> > > > right? (i.e. the control dependency above is enough for stores to be ordered
> > > > with respect to taking the lock)...
> > 
> > PaulMck completely confused me a few days ago with control dependencies
> > etc.. Pretty much saying that C/C++ doesn't do those.
> 
> I remember that there was a subtlety here, but don't remember what it was...
> 
> And while I do remember reviewing this code, I don't find any evidence
> that I gave my "Reviewed-by".  Tim/Jason, if I fat-fingered this, please
> forward that email back to me.

Yes Paul, you didn't explicitly gave the Reviewed-by. 
I put it in there because you have given valuable
comments on the potential critical section bleeding when 
reviewing initial version of the code.

I'll take it out now till you have explicitly given it.
Appreciate if you can provide your feedback on the current
version of code.

Thanks.

Tim

> 
> 							Thanx, Paul
> 


--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [PATCH v2 3/4] MCS Lock: Barrier corrections

[Waiman Long]

Tim,

I have just sent out a patch as an addendum to your patch series. 
Hopefully that will address the memory barrier issue.

-Longman

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [PATCH v2 3/4] MCS Lock: Barrier corrections

[Figo.zhang]

[-- Attachment #1: Type: text/plain, Size: 3894 bytes --]

2013/11/6 Tim Chen <tim.c.chen@linux.intel.com>

> On Tue, 2013-11-05 at 18:37 +0000, Will Deacon wrote:
> > On Tue, Nov 05, 2013 at 05:42:36PM +0000, Tim Chen wrote:
> > > This patch corrects the way memory barriers are used in the MCS lock
> > > and removes ones that are not needed. Also add comments on all
> barriers.
> >
> > Hmm, I see that you're fixing up the barriers, but I still don't
> completely
> > understand how what you have is correct. Hopefully you can help me out :)
> >
> > > Reviewed-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
> > > Reviewed-by: Tim Chen <tim.c.chen@linux.intel.com>
> > > Signed-off-by: Jason Low <jason.low2@hp.com>
> > > ---
> > >  include/linux/mcs_spinlock.h |   13 +++++++++++--
> > >  1 files changed, 11 insertions(+), 2 deletions(-)
> > >
> > > diff --git a/include/linux/mcs_spinlock.h
> b/include/linux/mcs_spinlock.h
> > > index 96f14299..93d445d 100644
> > > --- a/include/linux/mcs_spinlock.h
> > > +++ b/include/linux/mcs_spinlock.h
> > > @@ -36,16 +36,19 @@ void mcs_spin_lock(struct mcs_spinlock **lock,
> struct mcs_spinlock *node)
> > >     node->locked = 0;
> > >     node->next   = NULL;
> > >
> > > +   /* xchg() provides a memory barrier */
> > >     prev = xchg(lock, node);
> > >     if (likely(prev == NULL)) {
> > >             /* Lock acquired */
> > >             return;
> > >     }
> > >     ACCESS_ONCE(prev->next) = node;
> > > -   smp_wmb();
> > >     /* Wait until the lock holder passes the lock down */
> > >     while (!ACCESS_ONCE(node->locked))
> > >             arch_mutex_cpu_relax();
> > > +
> > > +   /* Make sure subsequent operations happen after the lock is
> acquired */
> > > +   smp_rmb();
> >
> > Ok, so this is an smp_rmb() because we assume that stores aren't
> speculated,
> > right? (i.e. the control dependency above is enough for stores to be
> ordered
> > with respect to taking the lock)...
> >
> > >  }
> > >
> > >  /*
> > > @@ -58,6 +61,7 @@ static void mcs_spin_unlock(struct mcs_spinlock
> **lock, struct mcs_spinlock *nod
> > >
> > >     if (likely(!next)) {
> > >             /*
> > > +            * cmpxchg() provides a memory barrier.
> > >              * Release the lock by setting it to NULL
> > >              */
> > >             if (likely(cmpxchg(lock, node, NULL) == node))
> > > @@ -65,9 +69,14 @@ static void mcs_spin_unlock(struct mcs_spinlock
> **lock, struct mcs_spinlock *nod
> > >             /* Wait until the next pointer is set */
> > >             while (!(next = ACCESS_ONCE(node->next)))
> > >                     arch_mutex_cpu_relax();
> > > +   } else {
> > > +           /*
> > > +            * Make sure all operations within the critical section
> > > +            * happen before the lock is released.
> > > +            */
> > > +           smp_wmb();
> >
> > ...but I don't see what prevents reads inside the critical section from
> > moving across the smp_wmb() here.
>
> This is to prevent any read in next critical section from
> creeping up before write in the previous critical section
> has completed
>
> e.g.
> CPU 1 execute
>         mcs_lock
>         x = 1;
>         ...
>         x = 2;
>         mcs_unlock
>
> and CPU 2 execute
>
>         mcs_lock
>         y = x;
>         ...
>         mcs_unlock
>
> We expect y to be 2 after the "y = x" assignment. Without the proper
> rmb in lock and wmb in unlock, y could be 1 for CPU 2 with
> speculative read (i.e. before the x=2 assignment is completed).
>

is it not a good example ?
why CPU2 will be waited  the "x" set to "2" ?  Maybe "y=x" assignment will
be executed firstly than CPU1 in pipeline
because of out-of-reorder.

e.g.
CPU 1 execute
        mcs_lock
        x = 1;
        ...
        x = 2;
        flags = true;
        mcs_unlock

and CPU 2 execute

       while (flags) {
              mcs_lock
               y = x;
                ...
              mcs_unlock
       }

[-- Attachment #2: Type: text/html, Size: 5288 bytes --]

Re: [PATCH v2 3/4] MCS Lock: Barrier corrections

[Will Deacon]

On Wed, Nov 06, 2013 at 05:44:42AM +0000, Figo.zhang wrote:
> 2013/11/6 Tim Chen <tim.c.chen@linux.intel.com<mailto:tim.c.chen@linux.intel.com>>
> On Tue, 2013-11-05 at 18:37 +0000, Will Deacon wrote:
> > On Tue, Nov 05, 2013 at 05:42:36PM +0000, Tim Chen wrote:
> > > diff --git a/include/linux/mcs_spinlock.h b/include/linux/mcs_spinlock.h
> > > index 96f14299..93d445d 100644
> > > --- a/include/linux/mcs_spinlock.h
> > > +++ b/include/linux/mcs_spinlock.h
> > > @@ -36,16 +36,19 @@ void mcs_spin_lock(struct mcs_spinlock **lock, struct mcs_spinlock *node)
> > >     node->locked = 0;
> > >     node->next   = NULL;
> > >
> > > +   /* xchg() provides a memory barrier */
> > >     prev = xchg(lock, node);
> > >     if (likely(prev == NULL)) {
> > >             /* Lock acquired */
> > >             return;
> > >     }
> > >     ACCESS_ONCE(prev->next) = node;
> > > -   smp_wmb();
> > >     /* Wait until the lock holder passes the lock down */
> > >     while (!ACCESS_ONCE(node->locked))
> > >             arch_mutex_cpu_relax();
> > > +
> > > +   /* Make sure subsequent operations happen after the lock is acquired */
> > > +   smp_rmb();
> >
> > Ok, so this is an smp_rmb() because we assume that stores aren't speculated,
> > right? (i.e. the control dependency above is enough for stores to be ordered
> > with respect to taking the lock)...
> >
> > >  }
> > >
> > >  /*
> > > @@ -58,6 +61,7 @@ static void mcs_spin_unlock(struct mcs_spinlock **lock, struct mcs_spinlock *nod
> > >
> > >     if (likely(!next)) {
> > >             /*
> > > +            * cmpxchg() provides a memory barrier.
> > >              * Release the lock by setting it to NULL
> > >              */
> > >             if (likely(cmpxchg(lock, node, NULL) == node))
> > > @@ -65,9 +69,14 @@ static void mcs_spin_unlock(struct mcs_spinlock **lock, struct mcs_spinlock *nod
> > >             /* Wait until the next pointer is set */
> > >             while (!(next = ACCESS_ONCE(node->next)))
> > >                     arch_mutex_cpu_relax();
> > > +   } else {
> > > +           /*
> > > +            * Make sure all operations within the critical section
> > > +            * happen before the lock is released.
> > > +            */
> > > +           smp_wmb();
> >
> > ...but I don't see what prevents reads inside the critical section from
> > moving across the smp_wmb() here.
> 
> This is to prevent any read in next critical section from
> creeping up before write in the previous critical section
> has completed

Understood, but an smp_wmb() doesn't provide any ordering guarantees with
respect to reads, hence why I think you need an smp_mb() here.

> e.g.
> CPU 1 execute
>         mcs_lock
>         x = 1;
>         ...
>         x = 2;
>         mcs_unlock
> 
> and CPU 2 execute
> 
>         mcs_lock
>         y = x;
>         ...
>         mcs_unlock
> 
> We expect y to be 2 after the "y = x" assignment. Without the proper
> rmb in lock and wmb in unlock, y could be 1 for CPU 2 with
> speculative read (i.e. before the x=2 assignment is completed).
> 
> is it not a good example ?

I think you need reads and writes by both CPUs to show the problem:

	// x, y are zero-initialised memory locations
	// a, b are registers

CPU 1:
	mcs_lock
	a = x
	y = 1
	mcs_unlock

CPU 2:
	mcs_lock
	b = y
	x = 1
	mcs_unlock

In this case, you would hope that you can't observe a = b = 1.

However, given the current barriers, I think you could end up with something
equivalent to:

CPU 1:
	y = 1		// Moved over read-barrier
	mcs_lock	// smp_rmb
	mcs_unlock	// smp_wmb
	a = x		// Moved over write-barrier

CPU 2:
	x = 1		// Moved over read-barrier
	mcs_lock	// smp_rmb
	mcs_unlock	// smp_wmb
	b = y		// Moved over write-barrier

which would permit a = b = 1, as well as other orderings.

Will

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [PATCH v2 3/4] MCS Lock: Barrier corrections

[Waiman Long]

On 11/06/2013 07:20 AM, Will Deacon wrote:
> On Wed, Nov 06, 2013 at 05:44:42AM +0000, Figo.zhang wrote:
>> 2013/11/6 Tim Chen<tim.c.chen@linux.intel.com<mailto:tim.c.chen@linux.intel.com>>
>> On Tue, 2013-11-05 at 18:37 +0000, Will Deacon wrote:
>>> On Tue, Nov 05, 2013 at 05:42:36PM +0000, Tim Chen wrote:
>>>> diff --git a/include/linux/mcs_spinlock.h b/include/linux/mcs_spinlock.h
>>>> index 96f14299..93d445d 100644
>>>> --- a/include/linux/mcs_spinlock.h
>>>> +++ b/include/linux/mcs_spinlock.h
>>>> @@ -36,16 +36,19 @@ void mcs_spin_lock(struct mcs_spinlock **lock, struct mcs_spinlock *node)
>>>>      node->locked = 0;
>>>>      node->next   = NULL;
>>>>
>>>> +   /* xchg() provides a memory barrier */
>>>>      prev = xchg(lock, node);
>>>>      if (likely(prev == NULL)) {
>>>>              /* Lock acquired */
>>>>              return;
>>>>      }
>>>>      ACCESS_ONCE(prev->next) = node;
>>>> -   smp_wmb();
>>>>      /* Wait until the lock holder passes the lock down */
>>>>      while (!ACCESS_ONCE(node->locked))
>>>>              arch_mutex_cpu_relax();
>>>> +
>>>> +   /* Make sure subsequent operations happen after the lock is acquired */
>>>> +   smp_rmb();
>>> Ok, so this is an smp_rmb() because we assume that stores aren't speculated,
>>> right? (i.e. the control dependency above is enough for stores to be ordered
>>> with respect to taking the lock)...
>>>
>>>>   }
>>>>
>>>>   /*
>>>> @@ -58,6 +61,7 @@ static void mcs_spin_unlock(struct mcs_spinlock **lock, struct mcs_spinlock *nod
>>>>
>>>>      if (likely(!next)) {
>>>>              /*
>>>> +            * cmpxchg() provides a memory barrier.
>>>>               * Release the lock by setting it to NULL
>>>>               */
>>>>              if (likely(cmpxchg(lock, node, NULL) == node))
>>>> @@ -65,9 +69,14 @@ static void mcs_spin_unlock(struct mcs_spinlock **lock, struct mcs_spinlock *nod
>>>>              /* Wait until the next pointer is set */
>>>>              while (!(next = ACCESS_ONCE(node->next)))
>>>>                      arch_mutex_cpu_relax();
>>>> +   } else {
>>>> +           /*
>>>> +            * Make sure all operations within the critical section
>>>> +            * happen before the lock is released.
>>>> +            */
>>>> +           smp_wmb();
>>> ...but I don't see what prevents reads inside the critical section from
>>> moving across the smp_wmb() here.
>> This is to prevent any read in next critical section from
>> creeping up before write in the previous critical section
>> has completed
> Understood, but an smp_wmb() doesn't provide any ordering guarantees with
> respect to reads, hence why I think you need an smp_mb() here.

A major reason for the current design is to avoid overhead of a full 
memory barrier in x86 which doesn't need that. I do agree that the 
current code may not be enough for other architectures. I would like to 
propose that the following changes:

1) Move the lock/unlock functions to mcs_spinlock.c.
2) Define a set of primitives - smp_mb__before_critical_section(), 
smp_mb_after_critical_section() that will fall back to smp_mb() if they 
are not defined in asm/processor.h, for example.
3) Use the new primitives instead of the current smp_rmb() and smp_wmb() 
memory barrier.

That will allow each architecture to tailor what sort of memory barrier 
do they want to use.

Regards,
Longman

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

[PATCH v2 4/4] MCS Lock: Make mcs_spinlock.h includable in other files

[Tim Chen]

The following changes are made to enable mcs_spinlock.h file to be
widely included in other files without causing problem:

1) Include a number of prerequisite header files and define
   arch_mutex_cpu_relax(), if not previously defined.
2) Make mcs_spin_unlock() an inlined function and
   rename mcs_spin_lock() to _raw_mcs_spin_lock() which is also an
   inlined function.
3) Create a new mcs_spinlock.c file to contain the non-inlined
   mcs_spin_lock() function.

Signed-off-by: Waiman Long <Waiman.Long@hp.com>
---
 include/linux/mcs_spinlock.h |   27 ++++++++++++++++++++++-----
 kernel/Makefile              |    6 +++---
 kernel/mcs_spinlock.c        |   21 +++++++++++++++++++++
 3 files changed, 46 insertions(+), 8 deletions(-)
 create mode 100644 kernel/mcs_spinlock.c

diff --git a/include/linux/mcs_spinlock.h b/include/linux/mcs_spinlock.h
index 93d445d..f2c71e8 100644
--- a/include/linux/mcs_spinlock.h
+++ b/include/linux/mcs_spinlock.h
@@ -12,11 +12,27 @@
 #ifndef __LINUX_MCS_SPINLOCK_H
 #define __LINUX_MCS_SPINLOCK_H
 
+/*
+ * asm/processor.h may define arch_mutex_cpu_relax().
+ * If it is not defined, cpu_relax() will be used.
+ */
+#include <asm/barrier.h>
+#include <asm/cmpxchg.h>
+#include <asm/processor.h>
+#include <linux/compiler.h>
+
+#ifndef arch_mutex_cpu_relax
+# define arch_mutex_cpu_relax() cpu_relax()
+#endif
+
 struct mcs_spinlock {
 	struct mcs_spinlock *next;
 	int locked; /* 1 if lock acquired */
 };
 
+extern
+void mcs_spin_lock(struct mcs_spinlock **lock, struct mcs_spinlock *node);
+
 /*
  * In order to acquire the lock, the caller should declare a local node and
  * pass a reference of the node to this function in addition to the lock.
@@ -24,11 +40,11 @@ struct mcs_spinlock {
  * on this node->locked until the previous lock holder sets the node->locked
  * in mcs_spin_unlock().
  *
- * We don't inline mcs_spin_lock() so that perf can correctly account for the
- * time spent in this lock function.
+ * The _raw_mcs_spin_lock() function should not be called directly. Instead,
+ * users should call mcs_spin_lock().
  */
-static noinline
-void mcs_spin_lock(struct mcs_spinlock **lock, struct mcs_spinlock *node)
+static inline
+void _raw_mcs_spin_lock(struct mcs_spinlock **lock, struct mcs_spinlock *node)
 {
 	struct mcs_spinlock *prev;
 
@@ -55,7 +71,8 @@ void mcs_spin_lock(struct mcs_spinlock **lock, struct mcs_spinlock *node)
  * Releases the lock. The caller should pass in the corresponding node that
  * was used to acquire the lock.
  */
-static void mcs_spin_unlock(struct mcs_spinlock **lock, struct mcs_spinlock *node)
+static inline
+void mcs_spin_unlock(struct mcs_spinlock **lock, struct mcs_spinlock *node)
 {
 	struct mcs_spinlock *next = ACCESS_ONCE(node->next);
 
diff --git a/kernel/Makefile b/kernel/Makefile
index 1ce4755..2ad8454 100644
--- a/kernel/Makefile
+++ b/kernel/Makefile
@@ -50,9 +50,9 @@ obj-$(CONFIG_SMP) += smp.o
 ifneq ($(CONFIG_SMP),y)
 obj-y += up.o
 endif
-obj-$(CONFIG_SMP) += spinlock.o
-obj-$(CONFIG_DEBUG_SPINLOCK) += spinlock.o
-obj-$(CONFIG_PROVE_LOCKING) += spinlock.o
+obj-$(CONFIG_SMP) += spinlock.o mcs_spinlock.o
+obj-$(CONFIG_DEBUG_SPINLOCK) += spinlock.o mcs_spinlock.o
+obj-$(CONFIG_PROVE_LOCKING) += spinlock.o mcs_spinlock.o
 obj-$(CONFIG_UID16) += uid16.o
 obj-$(CONFIG_MODULES) += module.o
 obj-$(CONFIG_MODULE_SIG) += module_signing.o modsign_pubkey.o modsign_certificate.o
diff --git a/kernel/mcs_spinlock.c b/kernel/mcs_spinlock.c
new file mode 100644
index 0000000..3c55626
--- /dev/null
+++ b/kernel/mcs_spinlock.c
@@ -0,0 +1,21 @@
+/*
+ * MCS lock
+ *
+ * The MCS lock (proposed by Mellor-Crummey and Scott) is a simple spin-lock
+ * with the desirable properties of being fair, and with each cpu trying
+ * to acquire the lock spinning on a local variable.
+ * It avoids expensive cache bouncings that common test-and-set spin-lock
+ * implementations incur.
+ */
+#include <linux/mcs_spinlock.h>
+#include <linux/export.h>
+
+/*
+ * We don't inline mcs_spin_lock() so that perf can correctly account for the
+ * time spent in this lock function.
+ */
+void mcs_spin_lock(struct mcs_spinlock **lock, struct mcs_spinlock *node)
+{
+	_raw_mcs_spin_lock(lock, node);
+}
+EXPORT_SYMBOL_GPL(mcs_spin_lock);
-- 
1.7.4.4


--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [PATCH v2 4/4] MCS Lock: Make mcs_spinlock.h includable in other files

[Peter Zijlstra]

On Tue, Nov 05, 2013 at 09:42:39AM -0800, Tim Chen wrote:
> + * The _raw_mcs_spin_lock() function should not be called directly. Instead,
> + * users should call mcs_spin_lock().
>   */
> -static noinline
> -void mcs_spin_lock(struct mcs_spinlock **lock, struct mcs_spinlock *node)
> +static inline
> +void _raw_mcs_spin_lock(struct mcs_spinlock **lock, struct mcs_spinlock *node)
>  {
>  	struct mcs_spinlock *prev;
>  

So why keep it in the header at all?

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [PATCH v2 4/4] MCS Lock: Make mcs_spinlock.h includable in other files

[Tim Chen]

On Tue, 2013-11-05 at 19:57 +0100, Peter Zijlstra wrote:
> On Tue, Nov 05, 2013 at 09:42:39AM -0800, Tim Chen wrote:
> > + * The _raw_mcs_spin_lock() function should not be called directly. Instead,
> > + * users should call mcs_spin_lock().
> >   */
> > -static noinline
> > -void mcs_spin_lock(struct mcs_spinlock **lock, struct mcs_spinlock *node)
> > +static inline
> > +void _raw_mcs_spin_lock(struct mcs_spinlock **lock, struct mcs_spinlock *node)
> >  {
> >  	struct mcs_spinlock *prev;
> >  
> 
> So why keep it in the header at all?

I also made the suggestion originally of keeping both lock and unlock in
mcs_spinlock.c.  Wonder if Waiman decides to keep them in header 
because in-lining the unlock function makes execution a bit faster?

Tim

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [PATCH v2 4/4] MCS Lock: Make mcs_spinlock.h includable in other files

[Waiman Long]

On 11/05/2013 02:30 PM, Tim Chen wrote:
> On Tue, 2013-11-05 at 19:57 +0100, Peter Zijlstra wrote:
>> On Tue, Nov 05, 2013 at 09:42:39AM -0800, Tim Chen wrote:
>>> + * The _raw_mcs_spin_lock() function should not be called directly. Instead,
>>> + * users should call mcs_spin_lock().
>>>    */
>>> -static noinline
>>> -void mcs_spin_lock(struct mcs_spinlock **lock, struct mcs_spinlock *node)
>>> +static inline
>>> +void _raw_mcs_spin_lock(struct mcs_spinlock **lock, struct mcs_spinlock *node)
>>>   {
>>>   	struct mcs_spinlock *prev;
>>>
>> So why keep it in the header at all?
> I also made the suggestion originally of keeping both lock and unlock in
> mcs_spinlock.c.  Wonder if Waiman decides to keep them in header
> because in-lining the unlock function makes execution a bit faster?
>
> Tim
>

I was following the example of the spinlock code where the lock function 
is not inlined, but the unlock function is. I have no objection to make 
them both as non-inlined functions, if you think that is the right move.

Regards,
Longman

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [PATCH v2 4/4] MCS Lock: Make mcs_spinlock.h includable in other files

[Peter Zijlstra]

On Wed, Nov 06, 2013 at 10:31:47AM -0500, Waiman Long wrote:
> On 11/05/2013 02:30 PM, Tim Chen wrote:
> >On Tue, 2013-11-05 at 19:57 +0100, Peter Zijlstra wrote:
> >>On Tue, Nov 05, 2013 at 09:42:39AM -0800, Tim Chen wrote:
> >>>+ * The _raw_mcs_spin_lock() function should not be called directly. Instead,
> >>>+ * users should call mcs_spin_lock().
> >>>   */
> >>>-static noinline
> >>>-void mcs_spin_lock(struct mcs_spinlock **lock, struct mcs_spinlock *node)
> >>>+static inline
> >>>+void _raw_mcs_spin_lock(struct mcs_spinlock **lock, struct mcs_spinlock *node)
> >>>  {
> >>>  	struct mcs_spinlock *prev;
> >>>
> >>So why keep it in the header at all?
> >I also made the suggestion originally of keeping both lock and unlock in
> >mcs_spinlock.c.  Wonder if Waiman decides to keep them in header
> >because in-lining the unlock function makes execution a bit faster?
> >
> >Tim
> >
> 
> I was following the example of the spinlock code where the lock function is
> not inlined, but the unlock function is. I have no objection to make them
> both as non-inlined functions, if you think that is the right move.

I don't care, what I do find odd is the existence of
_raw_mcs_spin_lock(). If you want to out-of-line it, just move the
entire thing into a .c file already.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>