MCS Lock: MCS lock code cleanup and optimizations

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

v3:
1. modified memory barriers to support non x86 architectures that have weak memory ordering.

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

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 (2):
MCS Lock: Make mcs_spinlock.h includable in other files MCS Lock: Allow architecture specific memory barrier in lock/unlock

 arch/x86/include/asm/barrier.h |    6 +++
 include/linux/mcs_spinlock.h   |   25 ++++++++++
 include/linux/mutex.h          |    5 +-
 kernel/Makefile                |    6 +-
 kernel/mcs_spinlock.c          |   96 ++++++++++++++++++++++++++++++++++++++++
 kernel/mutex.c                 |   60 +++----------------------
 6 files changed, 140 insertions(+), 58 deletions(-)
 create mode 100644 include/linux/mcs_spinlock.h
 create mode 100644 kernel/mcs_spinlock.c

Quoted 36 lines · 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

v3:
1. modified memory barriers to support non x86 architectures that have weak memory ordering.

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

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 (2):
MCS Lock: Make mcs_spinlock.h includable in other files MCS Lock: Allow architecture specific memory barrier in lock/unlock

Quoted 9 lines

 arch/x86/include/asm/barrier.h |    6 +++
 include/linux/mcs_spinlock.h   |   25 ++++++++++
 include/linux/mutex.h          |    5 +-
 kernel/Makefile                |    6 +-
 kernel/mcs_spinlock.c          |   96 ++++++++++++++++++++++++++++++++++++++++
 kernel/mutex.c                 |   60 +++----------------------
 6 files changed, 140 insertions(+), 58 deletions(-)
 create mode 100644 include/linux/mcs_spinlock.h
 create mode 100644 kernel/mcs_spinlock.c

Hmm I noticed that Peter's patchset to move locking mechanisms into a unique directory is now in -tip, ie:

http://marc.info/?l=linux-kernel&m=138373682928585

So we'll have problems applying this patchset, it would probably be best to rebase on top.

Thanks,
Davidlohr

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

Perhaps I'm missing something here, but what is MCS lock and what is the value?

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 Tim Chen <[email protected]>

Signed-off-by Jason Low <[email protected]>

Signed-off-by Tim Chen <[email protected]>

---
 include/linux/mcs_spinlock.h |   13 +++++++++++--
 1 files changed, 11 insertions(+), 2 deletions(-)

include/linux/mcs_spinlock.h +11 -2

index b5de3b0..96f14299 100644
@@ -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)))

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 Tim Chen <[email protected]>

Signed-off-by Jason Low <[email protected]>

Signed-off-by Tim Chen <[email protected]>

---
 include/linux/mcs_spinlock.h |   13 +++++++++++--
 1 files changed, 11 insertions(+), 2 deletions(-)

include/linux/mcs_spinlock.h +3 -1

index 96f14299..93d445d 100644
@@ -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 */

include/linux/mcs_spinlock.h +1 -0

+       smp_rmb();
 }
 
 /*

@@ -58,6 +61,7 @@ static void mcs_spin_unlock(struct mcs_spinlock **lock,

struct mcs_spinlock *nod

        if (likely(!next)) {
                /*

include/linux/mcs_spinlock.h +1 -0

+                * 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();

include/linux/mcs_spinlock.h +6 -2

+       } 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

Sorry about the HTML crap, the internet connection is too slow for my normal email habits, so I'm using my phone.

I think the barriers are still totally wrong for the locking functions.

Adding an smp_rmb after waiting for the lock is pure BS. Writes in the locked region could percolate out of the locked region.

The thing is, you cannot do the memory ordering for locks in any same generic way. Not using our current barrier system. On x86 (and many others) the smp_rmb will work fine, because writes are never moved earlier. But on other architectures you really need an acquire to get a lock efficiently. No separate barriers. An acquire needs to be on the instruction that does the lock.

Same goes for unlock. On x86 any store is a fine unlock, but on other architectures you need a store with a release marker.

So no amount of barriers will ever do this correctly. Sure, you can add full memory barriers and it will be "correct" but it will be unbearably slow, and add totally unnecessary serialization. So *correct* locking will require architecture support.

Linus,

A more general maintenance question: do you agree with the whole idea to factor out the MCS logic from mutex.c to make it reusable?

This optimization patch makes me think it's a useful thing to do:

[PATCH v3 2/5] MCS Lock: optimizations and extra comments

as that kicks back optimizations to the mutex code as well. It also brought some spotlight on mutex code that it would not have gotten otherwise.

That advantage is also its disadvantage: additional coupling between rwsem and mutex logic internals. But not like it's overly hard to undo this change, so I'm in general in favor of this direction ...

So unless you object to this direction, I planned to apply this preparatory series to the locking tree once we are all happy with all the fine details.

Thanks,

Ingo

I don't necessarily mind the factoring out, I just think it needs to be really solid and clear if - and *before* - we do this. [...]

[...] We do *not* want to factor out some half-arsed implementation and then have later patches to fix up the crud. Nor when multiple different locks then use that common code.

So I think it needs to be *clearly* great code before it gets factored out. Because before it is great code, it should not be shared with anything else.

Sorry about the HTML crap, the internet connection is too slow for my normal email habits, so I'm using my phone.

I think the barriers are still totally wrong for the locking functions.

Adding an smp_rmb after waiting for the lock is pure BS. Writes in the locked region could percolate out of the locked region.

The thing is, you cannot do the memory ordering for locks in any same generic way. Not using our current barrier system. On x86 (and many others) the smp_rmb will work fine, because writes are never moved earlier. But on other architectures you really need an acquire to get a lock efficiently. No separate barriers. An acquire needs to be on the instruction that does the lock.

Same goes for unlock. On x86 any store is a fine unlock, but on other architectures you need a store with a release marker.

So no amount of barriers will ever do this correctly. Sure, you can add full memory barriers and it will be "correct" but it will be unbearably slow, and add totally unnecessary serialization. So *correct* locking will require architecture support.

Rather than writing arch-specific locking code, would you agree to introduce acquire and release memory operations ?

Quoted 3 lines · Michel Lespinasse

Rather than writing arch-specific locking code, would you agree to introduce acquire and release memory operations ?

Yes, that's probably the right thing to do. What ops do we need? Store with release, cmpxchg and load with acquire? Anything else?

Quoted 8 lines · Linus Torvalds

Quoted 3 lines · Michel Lespinasse

Rather than writing arch-specific locking code, would you agree to introduce acquire and release memory operations ?

Yes, that's probably the right thing to do. What ops do we need? Store with release, cmpxchg and load with acquire? Anything else?

Depends on what lock types we want to implement on top; for MCS we would need:
- xchg acquire (common case) and load acquire (for spinning on our locker's wait word)
- cmpxchg release (when there is no next locker) and store release (when writing to the next locker's wait word)

One downside of the proposal is that using a load acquire for spinning puts the memory barrier within the spin loop. So this model is very intuitive and does not add unnecessary barriers on x86, but it my place the barriers in a suboptimal place for architectures that need them.

Quoted 17 lines · Michel Lespinasse

Quoted 8 lines · Linus Torvalds

Quoted 3 lines · Michel Lespinasse

Rather than writing arch-specific locking code, would you agree to introduce acquire and release memory operations ?

Yes, that's probably the right thing to do. What ops do we need? Store with release, cmpxchg and load with acquire? Anything else?

Depends on what lock types we want to implement on top; for MCS we would need:
- xchg acquire (common case) and load acquire (for spinning on our locker's wait word)
- cmpxchg release (when there is no next locker) and store release (when writing to the next locker's wait word)

Quoted 5 lines

One downside of the proposal is that using a load acquire for spinning puts the memory barrier within the spin loop. So this model is very intuitive and does not add unnecessary barriers on x86, but it my place the barriers in a suboptimal place for architectures that need them.

OK, I will bite... Why is a barrier in the spinloop suboptimal?

Can't say that I have tried measuring it, but the barrier should not normally result in interconnect traffic. Given that the barrier is required anyway, it should not affect lock-acquisition latency.

So what am I missing here?

Quoted 24 lines · Paul E. McKenney

Quoted 22 lines · Michel Lespinasse

Quoted 8 lines · Linus Torvalds

Quoted 3 lines · Michel Lespinasse

Rather than writing arch-specific locking code, would you agree to introduce acquire and release memory operations ?

Yes, that's probably the right thing to do. What ops do we need? Store with release, cmpxchg and load with acquire? Anything else?

Depends on what lock types we want to implement on top; for MCS we would need:
- xchg acquire (common case) and load acquire (for spinning on our locker's wait word)
- cmpxchg release (when there is no next locker) and store release (when writing to the next locker's wait word)

One downside of the proposal is that using a load acquire for spinning puts the memory barrier within the spin loop. So this model is very intuitive and does not add unnecessary barriers on x86, but it my place the barriers in a suboptimal place for architectures that need them.

Quoted 1 line

OK, I will bite... Why is a barrier in the spinloop suboptimal?

It's probably not a big deal - all I meant to say is that if you were manually placing barriers, you would probably put one after the loop instead. I don't deal much with architectures where such barriers are needed, so I don't know for sure if the difference means much.

Quoted 4 lines

Can't say that I have tried measuring it, but the barrier should not normally result in interconnect traffic. Given that the barrier is required anyway, it should not affect lock-acquisition latency.

Agree

Quoted 1 line

So what am I missing here?

I think you read my second email as me trying to shoot down a proposal
- I wasn't, as I really like the acquire/release model and find it easy to program with, which is why I'm proposing it in the first place. I just wanted to be upfront about all potential downsides, so we can consider them and see if they are significant - I don't think they are, but I'm not the best person to judge that as I mostly just deal with x86 stuff.

Michel, are you planning to do an implementation of load-acquire/store-release functions of various architectures?

Quoted 2 lines · Tim Chen

Michel, are you planning to do an implementation of load-acquire/store-release functions of various architectures?

A little something like this:
http://marc.info/?l=linux-arch&m=138386254111507

It so happens we were working on that the past week or so due to another issue ;-)

Quoted 4 lines

Or is the approach of arch specific memory barrier for MCS an acceptable one before load-acquire and store-release
are available? Are there any technical issues remaining with the patchset after including including Waiman's arch specific barrier?

Quoted 9 lines · Peter Zijlstra

Quoted 2 lines · Tim Chen

Michel, are you planning to do an implementation of load-acquire/store-release functions of various architectures?

A little something like this:
http://marc.info/?l=linux-arch&m=138386254111507

It so happens we were working on that the past week or so due to another issue ;-)

Haha, awesome, I wasn't aware of this effort.

Tim: my approach would be to provide the acquire/release operations in arch-specific include files, and have a default implementation using barriers for arches who don't provide these new ops. That way you make it work on all arches at once (using the default implementation) and make it fast on any arch that cares.

Quoted 4 lines

Quoted 4 lines

Or is the approach of arch specific memory barrier for MCS an acceptable one before load-acquire and store-release
are available? Are there any technical issues remaining with the patchset after including including Waiman's arch specific barrier?

I don't want to stand in the way of Waiman's change, and I had actually taken the same approach with arch-specific barriers when proposing some queue spinlocks in the past; however I do feel that this comes back regularly enough that having acquire/release primitives available would help, hence my proposal.

That said, earlier in the thread Linus said we should probably get all our ducks in a row before going forward with this, so...

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 <[email protected]>

Signed-off-by Tim Chen <[email protected]>

---
 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

include/linux/mcs_spinlock.h +22 -5

index 93d445d..f2c71e8 100644
@@ -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);
 

kernel/Makefile +3 -3

index 1ce4755..2ad8454 100644
@@ -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

kernel/mcs_spinlock.c new file +11 -0

new file mode 100644
index 0000000..3c55626
@@ -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>

This patch moves the decision of what kind of memory barriers to be used in the MCS lock and unlock functions to the architecture specific layer. It also moves the actual lock/unlock code to mcs_spinlock.c file.

A full memory barrier will be used if the following macros are not defined:
1) smp_mb__before_critical_section()
2) smp_mb__after_critical_section()

For the x86 architecture, only compiler barrier will be needed.

Signed-off-by Waiman Long <[email protected]>

Signed-off-by Tim Chen <[email protected]>

---
 arch/x86/include/asm/barrier.h |    6 +++
 include/linux/mcs_spinlock.h   |   78 +-------------------------------------
 kernel/mcs_spinlock.c          |   81 ++++++++++++++++++++++++++++++++++++++-
 3 files changed, 86 insertions(+), 79 deletions(-)

arch/x86/include/asm/barrier.h +6 -0

index c6cd358..6d0172c 100644
@@ -92,6 +92,12 @@
 #endif
 #define smp_read_barrier_depends()	read_barrier_depends()
 #define set_mb(var, value) do { (void)xchg(&var, value); } while (0)
+
+#if !defined(CONFIG_X86_PPRO_FENCE) && !defined(CONFIG_X86_OOSTORE)
+# define smp_mb__before_critical_section()	barrier()
+# define smp_mb__after_critical_section()	barrier()
+#endif
+
 #else
 #define smp_mb()	barrier()
 #define smp_rmb()	barrier()

include/linux/mcs_spinlock.h +2 -76

index f2c71e8..d54bb23 100644
@@ -12,19 +12,6 @@
 #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 */

@@ -32,68 +19,7 @@ struct mcs_spinlock {
 
 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.
- * 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().
- *
- * The _raw_mcs_spin_lock() function should not be called directly. Instead,
- * users should call mcs_spin_lock().
- */
-static inline
-void _raw_mcs_spin_lock(struct mcs_spinlock **lock, struct mcs_spinlock *node)
-{
-	struct mcs_spinlock *prev;
-
-	/* Init 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;
-	/* 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();
-}
-
-/*
- * Releases the lock. The caller should pass in the corresponding node that
- * was used to acquire the lock.
- */
-static inline
-void mcs_spin_unlock(struct mcs_spinlock **lock, struct mcs_spinlock *node)
-{
-	struct mcs_spinlock *next = ACCESS_ONCE(node->next);
-
-	if (likely(!next)) {
-		/*
-		 * cmpxchg() provides a memory barrier.
-		 * Release the lock by setting it to NULL
-		 */
-		if (likely(cmpxchg(lock, node, NULL) == node))
-			return;
-		/* 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;
-}
+extern
+void mcs_spin_unlock(struct mcs_spinlock **lock, struct mcs_spinlock *node);
 
 #endif /* __LINUX_MCS_SPINLOCK_H */

kernel/mcs_spinlock.c +78 -3

index 3c55626..2dfd207 100644
@@ -7,15 +7,90 @@
  * It avoids expensive cache bouncings that common test-and-set spin-lock
  * implementations incur.
  */
+/*
+ * 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>
 #include <linux/mcs_spinlock.h>
 #include <linux/export.h>
 
+#ifndef arch_mutex_cpu_relax
+# define arch_mutex_cpu_relax() cpu_relax()
+#endif
+
 /*
- * We don't inline mcs_spin_lock() so that perf can correctly account for the
- * time spent in this lock function.
+ * Fall back to use full memory barrier if those macros are not defined
+ * in a architecture specific header file.
+ */
+#ifndef smp_mb__before_critical_section
+#define	smp_mb__before_critical_section()	smp_mb()
+#endif
+
+#ifndef smp_mb__after_critical_section
+#define	smp_mb__after_critical_section()	smp_mb()
+#endif
+
+
+/*
+ * 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().
  */
 void mcs_spin_lock(struct mcs_spinlock **lock, struct mcs_spinlock *node)
 {
-	_raw_mcs_spin_lock(lock, node);
+	struct mcs_spinlock *prev;
+
+	/* Init 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;
+	/* 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_mb__before_critical_section();
 }
 EXPORT_SYMBOL_GPL(mcs_spin_lock);
+
+/*
+ * Releases the lock. The caller should pass in the corresponding node that
+ * was used to acquire the lock.
+ */
+void mcs_spin_unlock(struct mcs_spinlock **lock, struct mcs_spinlock *node)
+{
+	struct mcs_spinlock *next = ACCESS_ONCE(node->next);
+
+	if (likely(!next)) {
+		/*
+		 * cmpxchg() provides a memory barrier.
+		 * Release the lock by setting it to NULL
+		 */
+		if (likely(cmpxchg(lock, node, NULL) == node))
+			return;
+		/* 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_mb__after_critical_section();
+	}
+	ACCESS_ONCE(next->locked) = 1;
+}
+EXPORT_SYMBOL_GPL(mcs_spin_unlock);