From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-pb0-f54.google.com (mail-pb0-f54.google.com [209.85.160.54]) by kanga.kvack.org (Postfix) with ESMTP id F3BDA6B013B for ; Wed, 6 Nov 2013 20:39:56 -0500 (EST) Received: by mail-pb0-f54.google.com with SMTP id ro12so339938pbb.13 for ; Wed, 06 Nov 2013 17:39:56 -0800 (PST) Received: from psmtp.com ([74.125.245.124]) by mx.google.com with SMTP id j10si1073978pac.54.2013.11.06.17.39.53 for ; Wed, 06 Nov 2013 17:39:55 -0800 (PST) Received: by mail-vc0-f182.google.com with SMTP id if17so214875vcb.41 for ; Wed, 06 Nov 2013 17:39:52 -0800 (PST) MIME-Version: 1.0 In-Reply-To: <1383773827.11046.355.camel@schen9-DESK> References: <1383773827.11046.355.camel@schen9-DESK> Date: Thu, 7 Nov 2013 10:39:52 +0900 Message-ID: Subject: Re: [PATCH v3 3/5] MCS Lock: Barrier corrections From: Linus Torvalds Content-Type: multipart/alternative; boundary=20cf3079b7fc92942704ea8c57ee Sender: owner-linux-mm@kvack.org List-ID: To: Tim Chen Cc: Arnd Bergmann , "Figo. zhang" , Aswin Chandramouleeswaran , Rik van Riel , Waiman Long , Raghavendra K T , "Paul E.McKenney" , linux-arch@vger.kernel.org, Andi Kleen , Peter Zijlstra , George Spelvin , Michel Lespinasse , Ingo Molnar , Peter Hurley , "H. Peter Anvin" , Andrew Morton , linux-mm , Alex Shi , Andrea Arcangeli , Scott J Norton , linux-kernel@vger.kernel.org, Thomas Gleixner , Dave Hansen , Matthew R Wilcox , Will Deacon , Davidlohr Bueso --20cf3079b7fc92942704ea8c57ee Content-Type: text/plain; charset=UTF-8 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 On Nov 7, 2013 6:37 AM, "Tim Chen" wrote: > 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 > > > > --20cf3079b7fc92942704ea8c57ee Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable

Sorry about the HTML crap, the internet connection is too sl= ow 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. Wri= tes 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 ma= ny others) the smp_rmb will work fine, because writes are never moved earli= er. But on other architectures you really need an acquire to get a lock eff= iciently. No separate barriers. An acquire needs to be on the instruction t= hat 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 *cor= rect* locking will require architecture support.

=C2=A0=C2=A0=C2=A0=C2=A0 Linus

On Nov 7, 2013 6:37 AM, "Tim Chen" <= ;tim.c.chen@linux.intel.com> wrote:
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 <tim= .c.chen@linux.intel.com>
Signed-off-by: Jason Low <jason.low= 2@hp.com>
Signed-off-by: Tim Chen <t= im.c.chen@linux.intel.com>
---
=C2=A0include/linux/mcs_spinlock.h | =C2=A0 13 +++++++++++--
=C2=A01 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 m= cs_spinlock *node)
=C2=A0 =C2=A0 =C2=A0 =C2=A0 node->locked =3D 0;
=C2=A0 =C2=A0 =C2=A0 =C2=A0 node->next =C2=A0 =3D NULL;

+ =C2=A0 =C2=A0 =C2=A0 /* xchg() provides a memory barrier */
=C2=A0 =C2=A0 =C2=A0 =C2=A0 prev =3D xchg(lock, node);
=C2=A0 =C2=A0 =C2=A0 =C2=A0 if (likely(prev =3D=3D NULL)) {
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 /* Lock acquired */=
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 return;
=C2=A0 =C2=A0 =C2=A0 =C2=A0 }
=C2=A0 =C2=A0 =C2=A0 =C2=A0 ACCESS_ONCE(prev->next) =3D node;
- =C2=A0 =C2=A0 =C2=A0 smp_wmb();
=C2=A0 =C2=A0 =C2=A0 =C2=A0 /* Wait until the lock holder passes the lock d= own */
=C2=A0 =C2=A0 =C2=A0 =C2=A0 while (!ACCESS_ONCE(node->locked))
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 arch_mutex_cpu_rela= x();
+
+ =C2=A0 =C2=A0 =C2=A0 /* Make sure subsequent operations happen after the = lock is acquired */
+ =C2=A0 =C2=A0 =C2=A0 smp_rmb();
=C2=A0}

=C2=A0/*
@@ -58,6 +61,7 @@ static void mcs_spin_unlock(struct mcs_spinlock **lock, s= truct mcs_spinlock *nod

=C2=A0 =C2=A0 =C2=A0 =C2=A0 if (likely(!next)) {
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 /*
+ =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0* cmpxchg() provid= es a memory barrier.
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0* Release the= lock by setting it to NULL
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0*/
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 if (likely(cmpxchg(= lock, node, NULL) =3D=3D node))
@@ -65,9 +69,14 @@ static void mcs_spin_unlock(struct mcs_spinlock **lock, = struct mcs_spinlock *nod
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 /* Wait until the n= ext pointer is set */
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 while (!(next =3D A= CCESS_ONCE(node->next)))
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 arch_mutex_cpu_relax();
+ =C2=A0 =C2=A0 =C2=A0 } else {
+ =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 /*
+ =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0* Make sure all op= erations within the critical section
+ =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0* happen before th= e lock is released.
+ =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0*/
+ =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 smp_wmb();
=C2=A0 =C2=A0 =C2=A0 =C2=A0 }
=C2=A0 =C2=A0 =C2=A0 =C2=A0 ACCESS_ONCE(next->locked) =3D 1;
- =C2=A0 =C2=A0 =C2=A0 smp_wmb();
=C2=A0}

=C2=A0#endif /* __LINUX_MCS_SPINLOCK_H */
--
1.7.4.4



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