From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-pa0-f49.google.com (mail-pa0-f49.google.com [209.85.220.49]) by kanga.kvack.org (Postfix) with ESMTP id 6B1C76B0108 for ; Wed, 6 Nov 2013 16:37:03 -0500 (EST) Received: by mail-pa0-f49.google.com with SMTP id lj1so269624pab.22 for ; Wed, 06 Nov 2013 13:37:03 -0800 (PST) Received: from psmtp.com ([74.125.245.202]) by mx.google.com with SMTP id ws5si478056pab.238.2013.11.06.13.37.01 for ; Wed, 06 Nov 2013 13:37:01 -0800 (PST) Subject: [PATCH v3 0/4] MCS Lock: MCS lock code cleanup and optimizations From: Tim Chen References: Content-Type: text/plain; charset="UTF-8" Date: Wed, 06 Nov 2013 13:36:56 -0800 Message-ID: <1383773816.11046.352.camel@schen9-DESK> Mime-Version: 1.0 Content-Transfer-Encoding: 7bit Sender: owner-linux-mm@kvack.org List-ID: To: Ingo Molnar , Andrew Morton , Thomas Gleixner Cc: linux-kernel@vger.kernel.org, linux-mm , linux-arch@vger.kernel.org, Linus Torvalds , Waiman Long , Andrea Arcangeli , Alex Shi , Andi Kleen , Michel Lespinasse , Davidlohr Bueso , Matthew R Wilcox , Dave Hansen , Peter Zijlstra , Rik van Riel , Peter Hurley , "Paul E.McKenney" , Tim Chen , Raghavendra K T , George Spelvin , "H. Peter Anvin" , Arnd Bergmann , Aswin Chandramouleeswaran , Scott J Norton , Will Deacon , "Figo.zhang" 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 -- 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: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-pa0-f50.google.com (mail-pa0-f50.google.com [209.85.220.50]) by kanga.kvack.org (Postfix) with ESMTP id C9BCE6B010A for ; Wed, 6 Nov 2013 16:37:22 -0500 (EST) Received: by mail-pa0-f50.google.com with SMTP id fb1so265587pad.23 for ; Wed, 06 Nov 2013 13:37:22 -0800 (PST) Received: from psmtp.com ([74.125.245.163]) by mx.google.com with SMTP id ph6si99209pbb.337.2013.11.06.13.37.20 for ; Wed, 06 Nov 2013 13:37:21 -0800 (PST) Subject: [PATCH v3 5/5] MCS Lock: Allow architecture specific memory barrier in lock/unlock From: Tim Chen In-Reply-To: References: Content-Type: text/plain; charset="UTF-8" Date: Wed, 06 Nov 2013 13:37:16 -0800 Message-ID: <1383773836.11046.357.camel@schen9-DESK> Mime-Version: 1.0 Content-Transfer-Encoding: 7bit Sender: owner-linux-mm@kvack.org List-ID: To: Ingo Molnar , Andrew Morton , Thomas Gleixner Cc: linux-kernel@vger.kernel.org, linux-mm , linux-arch@vger.kernel.org, Linus Torvalds , Waiman Long , Andrea Arcangeli , Alex Shi , Andi Kleen , Michel Lespinasse , Davidlohr Bueso , Matthew R Wilcox , Dave Hansen , Peter Zijlstra , Rik van Riel , Peter Hurley , "Paul E.McKenney" , Tim Chen , Raghavendra K T , George Spelvin , "H. Peter Anvin" , Arnd Bergmann , Aswin Chandramouleeswaran , Scott J Norton , Will Deacon , "Figo.zhang" 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 Signed-off-by: Tim Chen --- 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(-) diff --git a/arch/x86/include/asm/barrier.h b/arch/x86/include/asm/barrier.h index c6cd358..6d0172c 100644 --- a/arch/x86/include/asm/barrier.h +++ b/arch/x86/include/asm/barrier.h @@ -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() diff --git a/include/linux/mcs_spinlock.h b/include/linux/mcs_spinlock.h index f2c71e8..d54bb23 100644 --- a/include/linux/mcs_spinlock.h +++ b/include/linux/mcs_spinlock.h @@ -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 -#include -#include -#include - -#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 */ diff --git a/kernel/mcs_spinlock.c b/kernel/mcs_spinlock.c index 3c55626..2dfd207 100644 --- a/kernel/mcs_spinlock.c +++ b/kernel/mcs_spinlock.c @@ -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 +#include +#include +#include #include #include +#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); -- 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: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-pb0-f48.google.com (mail-pb0-f48.google.com [209.85.160.48]) by kanga.kvack.org (Postfix) with ESMTP id B25A96B010C for ; Wed, 6 Nov 2013 16:37:43 -0500 (EST) Received: by mail-pb0-f48.google.com with SMTP id mc8so99688pbc.21 for ; Wed, 06 Nov 2013 13:37:43 -0800 (PST) Received: from psmtp.com ([74.125.245.135]) by mx.google.com with SMTP id ai2si465875pad.291.2013.11.06.13.37.40 for ; Wed, 06 Nov 2013 13:37:42 -0800 (PST) Subject: [PATCH v3 1/5] MCS Lock: Restructure the MCS lock defines and locking code into its own file From: Tim Chen In-Reply-To: References: Content-Type: text/plain; charset="UTF-8" Date: Wed, 06 Nov 2013 13:37:01 -0800 Message-ID: <1383773821.11046.353.camel@schen9-DESK> Mime-Version: 1.0 Content-Transfer-Encoding: 7bit Sender: owner-linux-mm@kvack.org List-ID: To: Ingo Molnar , Andrew Morton , Thomas Gleixner Cc: linux-kernel@vger.kernel.org, linux-mm , linux-arch@vger.kernel.org, Linus Torvalds , Waiman Long , Andrea Arcangeli , Alex Shi , Andi Kleen , Michel Lespinasse , Davidlohr Bueso , Matthew R Wilcox , Dave Hansen , Peter Zijlstra , Rik van Riel , Peter Hurley , "Paul E.McKenney" , Tim Chen , Raghavendra K T , George Spelvin , "H. Peter Anvin" , Arnd Bergmann , Aswin Chandramouleeswaran , Scott J Norton , Will Deacon , "Figo.zhang" 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. Signed-off-by: Tim Chen Signed-off-by: Davidlohr Bueso --- 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 bab49da..32a32e6 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 d24105b..e08b183 100644 --- a/kernel/mutex.c +++ b/kernel/mutex.c @@ -25,6 +25,7 @@ #include #include #include +#include /* * 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 (use_ww_ctx && 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: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-pd0-f181.google.com (mail-pd0-f181.google.com [209.85.192.181]) by kanga.kvack.org (Postfix) with ESMTP id 063C56B010D for ; Wed, 6 Nov 2013 16:37:44 -0500 (EST) Received: by mail-pd0-f181.google.com with SMTP id x10so96503pdj.26 for ; Wed, 06 Nov 2013 13:37:44 -0800 (PST) Received: from psmtp.com ([74.125.245.131]) by mx.google.com with SMTP id hb3si511410pac.94.2013.11.06.13.37.42 for ; Wed, 06 Nov 2013 13:37:43 -0800 (PST) Subject: [PATCH v3 2/5] MCS Lock: optimizations and extra comments From: Tim Chen In-Reply-To: References: Content-Type: text/plain; charset="UTF-8" Date: Wed, 06 Nov 2013 13:37:04 -0800 Message-ID: <1383773824.11046.354.camel@schen9-DESK> Mime-Version: 1.0 Content-Transfer-Encoding: 7bit Sender: owner-linux-mm@kvack.org List-ID: To: Ingo Molnar , Andrew Morton , Thomas Gleixner Cc: linux-kernel@vger.kernel.org, linux-mm , linux-arch@vger.kernel.org, Linus Torvalds , Waiman Long , Andrea Arcangeli , Alex Shi , Andi Kleen , Michel Lespinasse , Davidlohr Bueso , Matthew R Wilcox , Dave Hansen , Peter Zijlstra , Rik van Riel , Peter Hurley , "Paul E.McKenney" , Tim Chen , Raghavendra K T , George Spelvin , "H. Peter Anvin" , Arnd Bergmann , Aswin Chandramouleeswaran , Scott J Norton , Will Deacon , "Figo.zhang" 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 Signed-off-by: Jason Low Signed-off-by: Tim Chen --- 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: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-pd0-f169.google.com (mail-pd0-f169.google.com [209.85.192.169]) by kanga.kvack.org (Postfix) with ESMTP id AC8DA6B010E for ; Wed, 6 Nov 2013 16:37:45 -0500 (EST) Received: by mail-pd0-f169.google.com with SMTP id q10so100802pdj.0 for ; Wed, 06 Nov 2013 13:37:45 -0800 (PST) Received: from psmtp.com ([74.125.245.135]) by mx.google.com with SMTP id ei3si97007pbc.350.2013.11.06.13.37.43 for ; Wed, 06 Nov 2013 13:37:44 -0800 (PST) Subject: [PATCH v3 3/5] MCS Lock: Barrier corrections From: Tim Chen In-Reply-To: References: Content-Type: text/plain; charset="UTF-8" Date: Wed, 06 Nov 2013 13:37:07 -0800 Message-ID: <1383773827.11046.355.camel@schen9-DESK> Mime-Version: 1.0 Content-Transfer-Encoding: 7bit Sender: owner-linux-mm@kvack.org List-ID: To: Ingo Molnar , Andrew Morton , Thomas Gleixner Cc: linux-kernel@vger.kernel.org, linux-mm , linux-arch@vger.kernel.org, Linus Torvalds , Waiman Long , Andrea Arcangeli , Alex Shi , Andi Kleen , Michel Lespinasse , Davidlohr Bueso , Matthew R Wilcox , Dave Hansen , Peter Zijlstra , Rik van Riel , Peter Hurley , "Paul E.McKenney" , Tim Chen , Raghavendra K T , George Spelvin , "H. Peter Anvin" , Arnd Bergmann , Aswin Chandramouleeswaran , Scott J Norton , Will Deacon , "Figo.zhang" 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 Signed-off-by: Jason Low Signed-off-by: Tim Chen --- 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: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-pd0-f173.google.com (mail-pd0-f173.google.com [209.85.192.173]) by kanga.kvack.org (Postfix) with ESMTP id 197D26B0111 for ; Wed, 6 Nov 2013 16:37:50 -0500 (EST) Received: by mail-pd0-f173.google.com with SMTP id r10so100219pdi.4 for ; Wed, 06 Nov 2013 13:37:49 -0800 (PST) Received: from psmtp.com ([74.125.245.163]) by mx.google.com with SMTP id pl10si102500pbc.328.2013.11.06.13.37.47 for ; Wed, 06 Nov 2013 13:37:48 -0800 (PST) Subject: [PATCH v3 4/5] MCS Lock: Make mcs_spinlock.h includable in other files From: Tim Chen In-Reply-To: References: Content-Type: text/plain; charset="UTF-8" Date: Wed, 06 Nov 2013 13:37:12 -0800 Message-ID: <1383773832.11046.356.camel@schen9-DESK> Mime-Version: 1.0 Content-Transfer-Encoding: 7bit Sender: owner-linux-mm@kvack.org List-ID: To: Ingo Molnar , Andrew Morton , Thomas Gleixner Cc: linux-kernel@vger.kernel.org, linux-mm , linux-arch@vger.kernel.org, Linus Torvalds , Waiman Long , Andrea Arcangeli , Alex Shi , Andi Kleen , Michel Lespinasse , Davidlohr Bueso , Matthew R Wilcox , Dave Hansen , Peter Zijlstra , Rik van Riel , Peter Hurley , "Paul E.McKenney" , Tim Chen , Raghavendra K T , George Spelvin , "H. Peter Anvin" , Arnd Bergmann , Aswin Chandramouleeswaran , Scott J Norton , Will Deacon , "Figo.zhang" 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 Signed-off-by: Tim Chen --- 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 +#include +#include +#include + +#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 +#include + +/* + * 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: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-pb0-f44.google.com (mail-pb0-f44.google.com [209.85.160.44]) by kanga.kvack.org (Postfix) with ESMTP id DE24F6B0116 for ; Wed, 6 Nov 2013 16:41:40 -0500 (EST) Received: by mail-pb0-f44.google.com with SMTP id rp8so104827pbb.17 for ; Wed, 06 Nov 2013 13:41:40 -0800 (PST) Received: from psmtp.com ([74.125.245.147]) by mx.google.com with SMTP id ph6si156824pbb.97.2013.11.06.13.41.38 for ; Wed, 06 Nov 2013 13:41:39 -0800 (PST) Subject: Re: [PATCH v3 4/5] MCS Lock: Make mcs_spinlock.h includable in other files From: Tim Chen In-Reply-To: <1383773832.11046.356.camel@schen9-DESK> References: <1383773832.11046.356.camel@schen9-DESK> Content-Type: text/plain; charset="UTF-8" Date: Wed, 06 Nov 2013 13:41:33 -0800 Message-ID: <1383774093.11046.358.camel@schen9-DESK> Mime-Version: 1.0 Content-Transfer-Encoding: 7bit Sender: owner-linux-mm@kvack.org List-ID: To: Ingo Molnar Cc: Andrew Morton , Thomas Gleixner , linux-kernel@vger.kernel.org, linux-mm , linux-arch@vger.kernel.org, Linus Torvalds , Waiman Long , Andrea Arcangeli , Alex Shi , Andi Kleen , Michel Lespinasse , Davidlohr Bueso , Matthew R Wilcox , Dave Hansen , Peter Zijlstra , Rik van Riel , Peter Hurley , "Paul E.McKenney" , Raghavendra K T , George Spelvin , "H. Peter Anvin" , Arnd Bergmann , Aswin Chandramouleeswaran , Scott J Norton , Will Deacon , "Figo.zhang" On Wed, 2013-11-06 at 13:37 -0800, Tim Chen wrote: > 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 > Signed-off-by: Tim Chen Should be Acked-by: Tim Chen > --- > 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 > +#include > +#include > +#include > + > +#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 > +#include > + > +/* > + * 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); -- 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: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-pb0-f53.google.com (mail-pb0-f53.google.com [209.85.160.53]) by kanga.kvack.org (Postfix) with ESMTP id 8D4B86B0117 for ; Wed, 6 Nov 2013 16:42:08 -0500 (EST) Received: by mail-pb0-f53.google.com with SMTP id up7so103548pbc.26 for ; Wed, 06 Nov 2013 13:42:08 -0800 (PST) Received: from psmtp.com ([74.125.245.176]) by mx.google.com with SMTP id bc2si521762pad.100.2013.11.06.13.42.06 for ; Wed, 06 Nov 2013 13:42:06 -0800 (PST) Message-ID: <1383774119.13330.2.camel@buesod1.americas.hpqcorp.net> Subject: Re: [PATCH v3 0/4] MCS Lock: MCS lock code cleanup and optimizations From: Davidlohr Bueso Date: Wed, 06 Nov 2013 13:41:59 -0800 In-Reply-To: <1383773816.11046.352.camel@schen9-DESK> References: <1383773816.11046.352.camel@schen9-DESK> Content-Type: text/plain; charset="UTF-8" Mime-Version: 1.0 Content-Transfer-Encoding: 7bit Sender: owner-linux-mm@kvack.org List-ID: To: Tim Chen Cc: Ingo Molnar , Andrew Morton , Thomas Gleixner , linux-kernel@vger.kernel.org, linux-mm , linux-arch@vger.kernel.org, Linus Torvalds , Waiman Long , Andrea Arcangeli , Alex Shi , Andi Kleen , Michel Lespinasse , Davidlohr Bueso , Matthew R Wilcox , Dave Hansen , Peter Zijlstra , Rik van Riel , Peter Hurley , "Paul E.McKenney" , Raghavendra K T , George Spelvin , "H. Peter Anvin" , Arnd Bergmann , Aswin Chandramouleeswaran , Scott J Norton , Will Deacon , "Figo.zhang" On Wed, 2013-11-06 at 13:36 -0800, Tim Chen 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 > > 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 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 -- 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: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-pd0-f179.google.com (mail-pd0-f179.google.com [209.85.192.179]) by kanga.kvack.org (Postfix) with ESMTP id AF67A6B0119 for ; Wed, 6 Nov 2013 16:42:28 -0500 (EST) Received: by mail-pd0-f179.google.com with SMTP id y10so97847pdj.38 for ; Wed, 06 Nov 2013 13:42:28 -0800 (PST) Received: from psmtp.com ([74.125.245.172]) by mx.google.com with SMTP id j10si540256pac.25.2013.11.06.13.42.26 for ; Wed, 06 Nov 2013 13:42:26 -0800 (PST) Subject: Re: [PATCH v3 5/5] MCS Lock: Allow architecture specific memory barrier in lock/unlock From: Tim Chen In-Reply-To: <1383773836.11046.357.camel@schen9-DESK> References: <1383773836.11046.357.camel@schen9-DESK> Content-Type: text/plain; charset="UTF-8" Date: Wed, 06 Nov 2013 13:42:21 -0800 Message-ID: <1383774141.11046.359.camel@schen9-DESK> Mime-Version: 1.0 Content-Transfer-Encoding: 7bit Sender: owner-linux-mm@kvack.org List-ID: To: Ingo Molnar Cc: Andrew Morton , Thomas Gleixner , linux-kernel@vger.kernel.org, linux-mm , linux-arch@vger.kernel.org, Linus Torvalds , Waiman Long , Andrea Arcangeli , Alex Shi , Andi Kleen , Michel Lespinasse , Davidlohr Bueso , Matthew R Wilcox , Dave Hansen , Peter Zijlstra , Rik van Riel , Peter Hurley , "Paul E.McKenney" , Raghavendra K T , George Spelvin , "H. Peter Anvin" , Arnd Bergmann , Aswin Chandramouleeswaran , Scott J Norton , Will Deacon , "Figo.zhang" On Wed, 2013-11-06 at 13:37 -0800, Tim Chen wrote: > 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 > Signed-off-by: Tim Chen Should be Acked-by: Tim Chen > --- > 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(-) > > diff --git a/arch/x86/include/asm/barrier.h b/arch/x86/include/asm/barrier.h > index c6cd358..6d0172c 100644 > --- a/arch/x86/include/asm/barrier.h > +++ b/arch/x86/include/asm/barrier.h > @@ -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() > diff --git a/include/linux/mcs_spinlock.h b/include/linux/mcs_spinlock.h > index f2c71e8..d54bb23 100644 > --- a/include/linux/mcs_spinlock.h > +++ b/include/linux/mcs_spinlock.h > @@ -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 > -#include > -#include > -#include > - > -#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 */ > diff --git a/kernel/mcs_spinlock.c b/kernel/mcs_spinlock.c > index 3c55626..2dfd207 100644 > --- a/kernel/mcs_spinlock.c > +++ b/kernel/mcs_spinlock.c > @@ -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 > +#include > +#include > +#include > #include > #include > > +#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); -- 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: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-pa0-f46.google.com (mail-pa0-f46.google.com [209.85.220.46]) by kanga.kvack.org (Postfix) with ESMTP id 676426B011B for ; Wed, 6 Nov 2013 16:43:41 -0500 (EST) Received: by mail-pa0-f46.google.com with SMTP id rd3so276198pab.33 for ; Wed, 06 Nov 2013 13:43:41 -0800 (PST) Received: from psmtp.com ([74.125.245.142]) by mx.google.com with SMTP id jp3si114736pbc.336.2013.11.06.13.43.38 for ; Wed, 06 Nov 2013 13:43:39 -0800 (PST) Message-ID: <527AB7CA.4020502@zytor.com> Date: Wed, 06 Nov 2013 13:42:34 -0800 From: "H. Peter Anvin" MIME-Version: 1.0 Subject: Re: [PATCH v3 0/4] MCS Lock: MCS lock code cleanup and optimizations References: <1383773816.11046.352.camel@schen9-DESK> In-Reply-To: <1383773816.11046.352.camel@schen9-DESK> Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 7bit Sender: owner-linux-mm@kvack.org List-ID: To: Tim Chen , Ingo Molnar , Andrew Morton , Thomas Gleixner Cc: linux-kernel@vger.kernel.org, linux-mm , linux-arch@vger.kernel.org, Linus Torvalds , Waiman Long , Andrea Arcangeli , Alex Shi , Andi Kleen , Michel Lespinasse , Davidlohr Bueso , Matthew R Wilcox , Dave Hansen , Peter Zijlstra , Rik van Riel , Peter Hurley , "Paul E.McKenney" , Raghavendra K T , George Spelvin , Arnd Bergmann , Aswin Chandramouleeswaran , Scott J Norton , Will Deacon , "Figo.zhang" On 11/06/2013 01:36 PM, Tim Chen 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 Perhaps I'm missing something here, but what is MCS lock and what is the value? -hpa -- 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: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-pa0-f49.google.com (mail-pa0-f49.google.com [209.85.220.49]) by kanga.kvack.org (Postfix) with ESMTP id C51326B011D for ; Wed, 6 Nov 2013 16:47:38 -0500 (EST) Received: by mail-pa0-f49.google.com with SMTP id lj1so277368pab.8 for ; Wed, 06 Nov 2013 13:47:38 -0800 (PST) Received: from psmtp.com ([74.125.245.176]) by mx.google.com with SMTP id j10si477131pac.344.2013.11.06.13.47.35 for ; Wed, 06 Nov 2013 13:47:36 -0800 (PST) Subject: Re: [PATCH v3 2/5] MCS Lock: optimizations and extra comments From: Tim Chen In-Reply-To: <1383773824.11046.354.camel@schen9-DESK> References: <1383773824.11046.354.camel@schen9-DESK> Content-Type: text/plain; charset="UTF-8" Date: Wed, 06 Nov 2013 13:47:30 -0800 Message-ID: <1383774450.11046.361.camel@schen9-DESK> Mime-Version: 1.0 Content-Transfer-Encoding: 7bit Sender: owner-linux-mm@kvack.org List-ID: To: Ingo Molnar Cc: Andrew Morton , Thomas Gleixner , linux-kernel@vger.kernel.org, linux-mm , linux-arch@vger.kernel.org, Linus Torvalds , Waiman Long , Andrea Arcangeli , Alex Shi