On Wed, Nov 20, 2013 at 05:00:17PM +0000, Will Deacon wrote:
> 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!
This approach does look way better than replicating the entire MCS-lock
implementation on a bunch of architectures! ;-)
Thanx, Paul
> Cheers,
>
> Will
>
> --->8
>
> >From 074f4cdf9ddc97454467b9ad9f85128ee67c5604 Mon Sep 17 00:00:00 2001
> From: Will Deacon <will.deacon@xxxxxxx>
> 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@xxxxxxx>
> ---
> 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@xxxxxxx>
> 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@xxxxxxx>
> ---
> 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@xxxxxxx>
> 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@xxxxxxx>
> ---
> 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@xxxxxxxxx. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@xxxxxxxxx";> email@xxxxxxxxx </a>