Re: [PATCH v6 0/5] MCS Lock: MCS lock code cleanup and optimizations

[Will Deacon <will.deacon@arm.com>]

On Wed, Nov 20, 2013 at 12:50:23PM +0000, Paul E. McKenney wrote:
> On Wed, Nov 20, 2013 at 10:19:57AM +0000, Will Deacon wrote:
> > On Wed, Nov 20, 2013 at 01:37:26AM +0000, Tim Chen wrote:
> > > Will, do you want to take a crack at adding implementation for ARM
> > > with wfe instruction?
> > 
> > Sure, I'll have a go this week. Thanks for keeping that as a consideration!
> > 
> > As an aside: what are you using to test this code, so that I can make sure I
> > don't break it?
> 
> +1 to that!  In fact, it would be nice to have the test code in-tree,
> especially if it can test a wide variety of locks.  (/me needs to look
> at what test code for locks might already be in tree, for that matter...)

Well, in the absence of those tests, I've implemented something that I think
will work for ARM and could be easily extended to arm64.

Tim: I reverted your final patch and went with Paul's suggestion just to
look into the contended case. I'm also not sure about adding
asm/mcs_spinlock.h. This stuff might be better in asm/spinlock.h, which
already exists and contains both spinlocks and rwlocks. Depends on how much
people dislike the Kconfig symbol + conditional #include.

Anyway, patches below. I included the ARM bits for reference, but please
don't include them in your series!

Cheers,

Will

--->8

From 074f4cdf9ddc97454467b9ad9f85128ee67c5604 Mon Sep 17 00:00:00 2001
From: Will Deacon <will.deacon@arm.com>
Date: Wed, 20 Nov 2013 16:14:04 +0000
Subject: [PATCH 1/3] MCS Lock: allow architectures to hook in to contended
 paths

When contended, architectures may be able to reduce the polling overhead
in ways which aren't expressible using a simple relax() primitive.

This patch allows architectures to hook into the mcs_{lock,unlock}
functions for the contended cases only.

Signed-off-by: Will Deacon <will.deacon@arm.com>
---
 kernel/locking/mcs_spinlock.c | 47 +++++++++++++++++++++++++------------------
 1 file changed, 27 insertions(+), 20 deletions(-)

diff --git a/kernel/locking/mcs_spinlock.c b/kernel/locking/mcs_spinlock.c
index 6f2ce8efb006..853070b8a86d 100644
--- a/kernel/locking/mcs_spinlock.c
+++ b/kernel/locking/mcs_spinlock.c
@@ -7,19 +7,34 @@
  * 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/mutex.h>
 #include <linux/export.h>
 
-#ifndef arch_mutex_cpu_relax
-# define arch_mutex_cpu_relax() cpu_relax()
+#ifndef arch_mcs_spin_lock_contended
+/*
+ * Using smp_load_acquire() provides a memory barrier that ensures
+ * subsequent operations happen after the lock is acquired.
+ */
+#define arch_mcs_spin_lock_contended(l)					\
+	while (!(smp_load_acquire(l))) {				\
+		arch_mutex_cpu_relax();					\
+	}
+#endif
+
+#ifndef arch_mcs_spin_unlock_contended
+/*
+ * smp_store_release() provides a memory barrier to ensure all
+ * operations in the critical section has been completed before
+ * unlocking.
+ */
+#define arch_mcs_spin_unlock_contended(l)				\
+	smp_store_release((l), 1)
 #endif
 
 /*
@@ -44,13 +59,9 @@ void mcs_spin_lock(struct mcs_spinlock **lock, struct mcs_spinlock *node)
 		return;
 	}
 	ACCESS_ONCE(prev->next) = node;
-	/*
-	 * Wait until the lock holder passes the lock down.
-	 * Using smp_load_acquire() provides a memory barrier that
-	 * ensures subsequent operations happen after the lock is acquired.
-	 */
-	while (!(smp_load_acquire(&node->locked)))
-		arch_mutex_cpu_relax();
+
+	/* Wait until the lock holder passes the lock down. */
+	arch_mcs_spin_lock_contended(&node->locked);
 }
 EXPORT_SYMBOL_GPL(mcs_spin_lock);
 
@@ -72,12 +83,8 @@ void mcs_spin_unlock(struct mcs_spinlock **lock, struct mcs_spinlock *node)
 		while (!(next = ACCESS_ONCE(node->next)))
 			arch_mutex_cpu_relax();
 	}
-	/*
-	 * Pass lock to next waiter.
-	 * smp_store_release() provides a memory barrier to ensure
-	 * all operations in the critical section has been completed
-	 * before unlocking.
-	 */
-	smp_store_release(&next->locked, 1);
+
+	/* Pass lock to next waiter. */
+	arch_mcs_spin_unlock_contended(&next->locked);
 }
 EXPORT_SYMBOL_GPL(mcs_spin_unlock);
-- 
1.8.2.2


From faa48f77a17cfd99562b1e36de278367aa4d389c Mon Sep 17 00:00:00 2001
From: Will Deacon <will.deacon@arm.com>
Date: Wed, 20 Nov 2013 16:10:57 +0000
Subject: [PATCH 2/3] MCS Lock: add Kconfig entries to allow arch-specific
 hooks

This patch adds Kconfig entries to allow architectures to hook into the
MCS lock/unlock functions in the contended case.

Signed-off-by: Will Deacon <will.deacon@arm.com>
---
 arch/Kconfig                 | 3 +++
 include/linux/mcs_spinlock.h | 8 ++++++++
 2 files changed, 11 insertions(+)

diff --git a/arch/Kconfig b/arch/Kconfig
index f1cf895c040f..ae738f706325 100644
--- a/arch/Kconfig
+++ b/arch/Kconfig
@@ -303,6 +303,9 @@ config HAVE_CMPXCHG_LOCAL
 config HAVE_CMPXCHG_DOUBLE
 	bool
 
+config HAVE_ARCH_MCS_LOCK
+	bool
+
 config ARCH_WANT_IPC_PARSE_VERSION
 	bool
 
diff --git a/include/linux/mcs_spinlock.h b/include/linux/mcs_spinlock.h
index d54bb232a238..d2c02adb0bbd 100644
--- a/include/linux/mcs_spinlock.h
+++ b/include/linux/mcs_spinlock.h
@@ -12,6 +12,14 @@
 #ifndef __LINUX_MCS_SPINLOCK_H
 #define __LINUX_MCS_SPINLOCK_H
 
+/*
+ * An architecture may provide its own lock/unlock functions for the
+ * contended case.
+ */
+#ifdef CONFIG_HAVE_ARCH_MCS_LOCK
+#include <asm/mcs_spinlock.h>
+#endif
+
 struct mcs_spinlock {
 	struct mcs_spinlock *next;
 	int locked; /* 1 if lock acquired */
-- 
1.8.2.2


From 21f047d40002ec4f1b780eee88f16a1870ab00ef Mon Sep 17 00:00:00 2001
From: Will Deacon <will.deacon@arm.com>
Date: Wed, 20 Nov 2013 16:15:31 +0000
Subject: [PATCH 3/3] ARM: mcs lock: implement wfe-based polling for MCS
 locking

This patch introduces a wfe-based polling loop for spinning on contended
MCS locks and waking up corresponding waiters when the lock is released.

Signed-off-by: Will Deacon <will.deacon@arm.com>
---
 arch/arm/Kconfig                    |  1 +
 arch/arm/include/asm/mcs_spinlock.h | 20 ++++++++++++++++++++
 2 files changed, 21 insertions(+)
 create mode 100644 arch/arm/include/asm/mcs_spinlock.h

diff --git a/arch/arm/Kconfig b/arch/arm/Kconfig
index 214b698cefea..ab9fb84599ac 100644
--- a/arch/arm/Kconfig
+++ b/arch/arm/Kconfig
@@ -25,6 +25,7 @@ config ARM
 	select HARDIRQS_SW_RESEND
 	select HAVE_ARCH_JUMP_LABEL if !XIP_KERNEL
 	select HAVE_ARCH_KGDB
+	select HAVE_ARCH_MCS_LOCK
 	select HAVE_ARCH_SECCOMP_FILTER
 	select HAVE_ARCH_TRACEHOOK
 	select HAVE_BPF_JIT
diff --git a/arch/arm/include/asm/mcs_spinlock.h b/arch/arm/include/asm/mcs_spinlock.h
new file mode 100644
index 000000000000..f32f97e81471
--- /dev/null
+++ b/arch/arm/include/asm/mcs_spinlock.h
@@ -0,0 +1,20 @@
+#ifndef __ASM_MCS_LOCK_H
+#define __ASM_MCS_LOCK_H
+
+/* MCS spin-locking. */
+#define arch_mcs_spin_lock_contended(lock)				\
+do {									\
+	/* Ensure prior stores are observed before we enter wfe. */	\
+	smp_mb();							\
+	while (!(smp_load_acquire(lock)))				\
+		wfe();							\
+} while (0)								\
+
+#define arch_mcs_spin_unlock_contended(lock)				\
+do {									\
+	smp_store_release(lock, 1);					\
+	dsb(ishst);							\
+	sev();								\
+} while (0)
+
+#endif	/* __ASM_MCS_LOCK_H */
-- 
1.8.2.2

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