On Tue, 2013-11-19 at 11:10 -0800, Paul E. McKenney wrote:
> On Fri, Nov 08, 2013 at 11:51:52AM -0800, Tim Chen wrote:
> > We will need the MCS lock code for doing optimistic spinning for rwsem
> > and queue rwlock. Extracting the MCS code from mutex.c and put into
> > its own file allow us to reuse this code easily.
> >
> > Signed-off-by: Tim Chen <tim.c.chen@xxxxxxxxxxxxxxx>
> > Signed-off-by: Davidlohr Bueso <davidlohr@xxxxxx>
>
> Please see comments below.
>
Thanks for reviewing the code.
> Thanx, Paul
>
> > ---
> > include/linux/mcs_spinlock.h | 64 ++++++++++++++++++++++++++++++++++++++++++
> > include/linux/mutex.h | 5 ++-
> > kernel/locking/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);
>
> OK, the full memory barriers implied by xchg() ensure that *node will be
> initialized before the "ACCESS_ONCE(prev->next) = node" below puts the
> node into the list. This rules out the misordering scenario that Tim
> Chen called out in message-id <1380322005.3467.186.camel@schen9-DESK>
> on September 27th.
>
> Assuming of course a corresponding barrier on the lock handoff side.
>
> > + if (likely(prev == NULL)) {
> > + /* Lock acquired */
> > + node->locked = 1;
> > + return;
> > + }
> > + ACCESS_ONCE(prev->next) = node;
> > + smp_wmb();
>
> I don't see what the above memory barrier does. Here are some things
> that it cannot be doing:
>
> o Ordering the insertion into the list above with the polling
> below. First, smp_wmb() does not order prior writes against
> later reads, and second misordering is harmless. If we start
> polling before the insertion is complete, all that happens
> is that the first few polls have no chance of seeing a lock
> grant.
>
> o Ordering the polling against the initialization -- the above
> xchg() is already doing that for us.
>
> So what is its purpose?
Agree that the smp_wmb is not needed. It is in the existing mcs code
residing in mutex.c and we're re-factoring the code only here and hasn't
corrected the memory barrier.
The particular smp_wmb() is removed in Patch 4/4 that corrects the
memory barriers.
>
> > + /* Wait until the lock holder passes the lock down */
> > + while (!ACCESS_ONCE(node->locked))
> > + arch_mutex_cpu_relax();
>
> On the other hand, I don't see how we get away without a barrier here.
> As written, what prevents the caller's load from ->owner from being
> reordered with the above load from ->locked? (Perhaps you can argue
> that such reordering is only a performance problem, but if so we need
> that argument recorded in comments.)
>
> Of course, if anyone ever tries to use mcs_spin_lock() as a full lock,
> they will need a memory barrier here to prevent the critical section
> from leaking out.
Agree too. The appropriate memory barrier is added in Patch 4/4.
>
> > +}
> > +
> > +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();
> > + }
>
> We need a memory barrier somewhere before here in this function,
> otherwise the critical section can leak out. I do not believe that
> we can rely on the prohibition against speculative stores that Peter
> Zijlstra and I have been discussing because that does not provide the
> transitivity required by locking primitives. I believe that we -could-
> make the access below be an smp_store_release(), though.
>
> Placing the barrier here (or at least not preceding the initial
> fetch from node->next) has the advantage of allowing it to pair with
> the xchg() in mcs_spin_lock(), though given the dependency only an
> smp_read_barrier_depends() is required for that purpose.
>
> > + ACCESS_ONCE(next->locked) = 1;
> > + smp_wmb();
>
> I don't see what this barrier does for us. It is ordering the unlock
> store with what, exactly?
>
> If it really is doing something, we need a big fat comment stating what
> that is, and checkpatch.pl will be happy to inform you. ;-)
>
> > +}
> > +
> > +#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/locking/mutex.c b/kernel/locking/mutex.c
> > index d24105b..e08b183 100644
> > --- a/kernel/locking/mutex.c
> > +++ b/kernel/locking/mutex.c
> > @@ -25,6 +25,7 @@
> > #include <linux/spinlock.h>
> > #include <linux/interrupt.h>
> > #include <linux/debug_locks.h>
> > +#include <linux/mcs_spinlock.h>
> >
> > /*
> > * In the DEBUG case we are using the "NULL fastpath" for mutexes,
> > @@ -52,7 +53,7 @@ __mutex_init(struct mutex *lock, const char *name, struct lock_class_key *key)
> > INIT_LIST_HEAD(&lock->wait_list);
> > mutex_clear_owner(lock);
> > #ifdef CONFIG_MUTEX_SPIN_ON_OWNER
> > - lock->spin_mlock = NULL;
> > + lock->mcs_lock = NULL;
> > #endif
> >
> > debug_mutex_init(lock, name, key);
> > @@ -111,54 +112,7 @@ EXPORT_SYMBOL(mutex_lock);
> > * more or less simultaneously, the spinners need to acquire a MCS lock
> > * first before spinning on the owner field.
> > *
> > - * We don't inline mspin_lock() so that perf can correctly account for the
> > - * time spent in this lock function.
> > */
> > -struct mspin_node {
> > - struct mspin_node *next ;
> > - int locked; /* 1 if lock acquired */
> > -};
> > -#define MLOCK(mutex) ((struct mspin_node **)&((mutex)->spin_mlock))
> > -
> > -static noinline
> > -void mspin_lock(struct mspin_node **lock, struct mspin_node *node)
> > -{
> > - struct mspin_node *prev;
> > -
> > - /* Init node */
> > - node->locked = 0;
> > - node->next = NULL;
> > -
> > - prev = xchg(lock, node);
> > - if (likely(prev == NULL)) {
> > - /* Lock acquired */
> > - node->locked = 1;
> > - return;
> > - }
> > - ACCESS_ONCE(prev->next) = node;
> > - smp_wmb();
> > - /* Wait until the lock holder passes the lock down */
> > - while (!ACCESS_ONCE(node->locked))
> > - arch_mutex_cpu_relax();
> > -}
> > -
> > -static void mspin_unlock(struct mspin_node **lock, struct mspin_node *node)
> > -{
> > - struct mspin_node *next = ACCESS_ONCE(node->next);
> > -
> > - if (likely(!next)) {
> > - /*
> > - * Release the lock by setting it to NULL
> > - */
> > - if (cmpxchg(lock, node, NULL) == node)
> > - return;
> > - /* Wait until the next pointer is set */
> > - while (!(next = ACCESS_ONCE(node->next)))
> > - arch_mutex_cpu_relax();
> > - }
> > - ACCESS_ONCE(next->locked) = 1;
> > - smp_wmb();
> > -}
> >
> > /*
> > * Mutex spinning code migrated from kernel/sched/core.c
> > @@ -448,7 +402,7 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass,
> >
> > for (;;) {
> > struct task_struct *owner;
> > - struct mspin_node node;
> > + struct mcs_spinlock node;
> >
> > if (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 from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to majordomo@xxxxxxxxxxxxxxx
> More majordomo info at http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at http://www.tux.org/lkml/
--
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>