Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1404141 > unrolled thread

sem_lock() vs qspinlocks

Back to article view | Back to linux.kernel

Contents

  sem_lock() vs qspinlocks Davidlohr Bueso <dave@stgolabs.net> - 2016-05-20 07:40 +0200
    Re: sem_lock() vs qspinlocks Peter Zijlstra <peterz@infradead.org> - 2016-05-20 10:00 +0200
      Re: sem_lock() vs qspinlocks Davidlohr Bueso <dave@stgolabs.net> - 2016-05-20 17:10 +0200
        Re: sem_lock() vs qspinlocks Peter Zijlstra <peterz@infradead.org> - 2016-05-20 17:10 +0200
          Re: sem_lock() vs qspinlocks Davidlohr Bueso <dave@stgolabs.net> - 2016-05-20 17:30 +0200
          Re: sem_lock() vs qspinlocks Peter Zijlstra <peterz@infradead.org> - 2016-05-20 17:30 +0200
        Re: sem_lock() vs qspinlocks Waiman Long <waiman.long@hpe.com> - 2016-05-20 22:50 +0200
          Re: sem_lock() vs qspinlocks Peter Zijlstra <peterz@infradead.org> - 2016-05-20 23:00 +0200
            Re: sem_lock() vs qspinlocks Davidlohr Bueso <dave@stgolabs.net> - 2016-05-21 03:00 +0200
              Re: sem_lock() vs qspinlocks Waiman Long <waiman.long@hpe.com> - 2016-05-21 06:10 +0200
                Re: sem_lock() vs qspinlocks Peter Zijlstra <peterz@infradead.org> - 2016-05-21 09:50 +0200
    Re: sem_lock() vs qspinlocks Peter Zijlstra <peterz@infradead.org> - 2016-05-20 10:00 +0200
    Re: sem_lock() vs qspinlocks Peter Zijlstra <peterz@infradead.org> - 2016-05-20 10:20 +0200
      Re: sem_lock() vs qspinlocks Peter Zijlstra <peterz@infradead.org> - 2016-05-20 10:20 +0200
        Re: sem_lock() vs qspinlocks Peter Zijlstra <peterz@infradead.org> - 2016-05-20 11:40 +0200
    Re: sem_lock() vs qspinlocks Peter Zijlstra <peterz@infradead.org> - 2016-05-20 10:40 +0200
      Re: sem_lock() vs qspinlocks Peter Zijlstra <peterz@infradead.org> - 2016-05-20 11:10 +0200
        Re: sem_lock() vs qspinlocks Ingo Molnar <mingo@kernel.org> - 2016-05-20 12:10 +0200
          Re: sem_lock() vs qspinlocks Mel Gorman <mgorman@techsingularity.net> - 2016-05-20 12:50 +0200
    Re: sem_lock() vs qspinlocks Peter Zijlstra <peterz@infradead.org> - 2016-05-20 14:00 +0200
      Re: sem_lock() vs qspinlocks Boqun Feng <boqun.feng@gmail.com> - 2016-05-20 16:10 +0200
        Re: sem_lock() vs qspinlocks Peter Zijlstra <peterz@infradead.org> - 2016-05-20 17:30 +0200
          Re: sem_lock() vs qspinlocks Peter Zijlstra <peterz@infradead.org> - 2016-05-20 18:10 +0200
            Re: sem_lock() vs qspinlocks Linus Torvalds <torvalds@linux-foundation.org> - 2016-05-20 19:10 +0200
              Re: sem_lock() vs qspinlocks Peter Zijlstra <peterz@infradead.org> - 2016-05-20 23:10 +0200
                Re: sem_lock() vs qspinlocks Linus Torvalds <torvalds@linux-foundation.org> - 2016-05-20 23:50 +0200
                  Re: sem_lock() vs qspinlocks Davidlohr Bueso <dave@stgolabs.net> - 2016-05-21 02:50 +0200
                    Re: sem_lock() vs qspinlocks Linus Torvalds <torvalds@linux-foundation.org> - 2016-05-21 04:40 +0200
                    Re: sem_lock() vs qspinlocks Peter Zijlstra <peterz@infradead.org> - 2016-05-21 09:40 +0200
                      Re: sem_lock() vs qspinlocks Manfred Spraul <manfred@colorfullife.com> - 2016-05-21 15:50 +0200
                        Re: sem_lock() vs qspinlocks Peter Zijlstra <peterz@infradead.org> - 2016-05-24 13:00 +0200
                      Re: sem_lock() vs qspinlocks Davidlohr Bueso <dave@stgolabs.net> - 2016-05-21 19:20 +0200
              Re: sem_lock() vs qspinlocks Peter Zijlstra <peterz@infradead.org> - 2016-05-23 14:30 +0200
                Re: sem_lock() vs qspinlocks Linus Torvalds <torvalds@linux-foundation.org> - 2016-05-23 20:00 +0200
                  Re: sem_lock() vs qspinlocks Boqun Feng <boqun.feng@gmail.com> - 2016-05-25 08:40 +0200
            Re: sem_lock() vs qspinlocks Manfred Spraul <manfred@colorfullife.com> - 2016-05-22 10:50 +0200
              Re: sem_lock() vs qspinlocks Peter Zijlstra <peterz@infradead.org> - 2016-05-22 11:40 +0200
      Re: sem_lock() vs qspinlocks Davidlohr Bueso <dave@stgolabs.net> - 2016-05-20 18:30 +0200
      Re: sem_lock() vs qspinlocks Waiman Long <waiman.long@hpe.com> - 2016-05-20 22:50 +0200
        Re: sem_lock() vs qspinlocks Peter Zijlstra <peterz@infradead.org> - 2016-05-20 23:00 +0200

Page 2 of 2 — ← Prev page 1 [2]

#1404474

[Multipart message — attachments visible in raw view] — view raw

Hi Peter,

On Fri, May 20, 2016 at 01:58:19PM +0200, Peter Zijlstra wrote:
> On Thu, May 19, 2016 at 10:39:26PM -0700, Davidlohr Bueso wrote:
> > As such, the following restores the behavior of the ticket locks and 'fixes'
> > (or hides?) the bug in sems. Naturally incorrect approach:
> > 
> > @@ -290,7 +290,8 @@ static void sem_wait_array(struct sem_array *sma)
> > 
> > 	for (i = 0; i < sma->sem_nsems; i++) {
> > 		sem = sma->sem_base + i;
> > -               spin_unlock_wait(&sem->lock);
> > +               while (atomic_read(&sem->lock))
> > +                       cpu_relax();
> > 	}
> > 	ipc_smp_acquire__after_spin_is_unlocked();
> > }
> 
> The actual bug is clear_pending_set_locked() not having acquire
> semantics. And the above 'fixes' things because it will observe the old
> pending bit or the locked bit, so it doesn't matter if the store
> flipping them is delayed.
> 
> The comment in queued_spin_lock_slowpath() above the smp_cond_acquire()
> states that that acquire is sufficient, but this is incorrect in the
> face of spin_is_locked()/spin_unlock_wait() usage only looking at the
> lock byte.
> 
> The problem is that the clear_pending_set_locked() is an unordered
> store, therefore this store can be delayed until no later than
> spin_unlock() (which orders against it due to the address dependency).
> 
> This opens numerous races; for example:
> 
> 	ipc_lock_object(&sma->sem_perm);
> 	sem_wait_array(sma);
> 
> 				false   ->	spin_is_locked(&sma->sem_perm.lock)
> 
> is entirely possible, because sem_wait_array() consists of pure reads,
> so the store can pass all that, even on x86.
> 
> The below 'hack' seems to solve the problem.
> 
> _However_ this also means the atomic_cmpxchg_relaxed() in the locked:
> branch is equally wrong -- although not visible on x86. And note that
> atomic_cmpxchg_acquire() would not in fact be sufficient either, since
> the acquire is on the LOAD not the STORE of the LL/SC.
> 
> I need a break of sorts, because after twisting my head around the sem
> code and then the qspinlock code I'm wrecked. I'll try and make a proper
> patch if people can indeed confirm my thinking here.
> 

I think your analysis is right, however, the problem only exists if we
have the following use pattern, right?

	CPU 0			CPU 1
	====================	==================
	spin_lock(A);		spin_lock(B);
	spin_unlock_wait(B);	spin_unlock_wait(A);
	do_something();		do_something();

, which ends up CPU 0 and 1 both running do_something(). And actually
this can be simply fixed by add smp_mb() between spin_lock() and
spin_unlock_wait() on both CPU, or add an smp_mb() in spin_unlock_wait()
as PPC does in 51d7d5205d338 "powerpc: Add smp_mb() to arch_spin_is_locked()".

So if relaxed/acquire atomics and clear_pending_set_locked() work fine
in other situations, a proper fix would be fixing the
spin_is_locked()/spin_unlock_wait() or their users?

Regards,
Boqun

> ---
>  kernel/locking/qspinlock.c | 1 +
>  1 file changed, 1 insertion(+)
> 
> diff --git a/kernel/locking/qspinlock.c b/kernel/locking/qspinlock.c
> index ce2f75e32ae1..348e172e774f 100644
> --- a/kernel/locking/qspinlock.c
> +++ b/kernel/locking/qspinlock.c
> @@ -366,6 +366,7 @@ void queued_spin_lock_slowpath(struct qspinlock *lock, u32 val)
>  	 * *,1,0 -> *,0,1
>  	 */
>  	clear_pending_set_locked(lock);
> +	smp_mb();
>  	return;
>  
>  	/*

[toc] | [prev] | [next] | [standalone]

#1404541

On Fri, May 20, 2016 at 10:05:33PM +0800, Boqun Feng wrote:
> On Fri, May 20, 2016 at 01:58:19PM +0200, Peter Zijlstra wrote:
> > On Thu, May 19, 2016 at 10:39:26PM -0700, Davidlohr Bueso wrote:
> > > As such, the following restores the behavior of the ticket locks and 'fixes'
> > > (or hides?) the bug in sems. Naturally incorrect approach:
> > > 
> > > @@ -290,7 +290,8 @@ static void sem_wait_array(struct sem_array *sma)
> > > 
> > > 	for (i = 0; i < sma->sem_nsems; i++) {
> > > 		sem = sma->sem_base + i;
> > > -               spin_unlock_wait(&sem->lock);
> > > +               while (atomic_read(&sem->lock))
> > > +                       cpu_relax();
> > > 	}
> > > 	ipc_smp_acquire__after_spin_is_unlocked();
> > > }
> > 
> > The actual bug is clear_pending_set_locked() not having acquire
> > semantics. And the above 'fixes' things because it will observe the old
> > pending bit or the locked bit, so it doesn't matter if the store
> > flipping them is delayed.
> > 
> > The comment in queued_spin_lock_slowpath() above the smp_cond_acquire()
> > states that that acquire is sufficient, but this is incorrect in the
> > face of spin_is_locked()/spin_unlock_wait() usage only looking at the
> > lock byte.
> > 
> > The problem is that the clear_pending_set_locked() is an unordered
> > store, therefore this store can be delayed until no later than
> > spin_unlock() (which orders against it due to the address dependency).
> > 
> > This opens numerous races; for example:
> > 
> > 	ipc_lock_object(&sma->sem_perm);
> > 	sem_wait_array(sma);
> > 
> > 				false   ->	spin_is_locked(&sma->sem_perm.lock)
> > 
> > is entirely possible, because sem_wait_array() consists of pure reads,
> > so the store can pass all that, even on x86.
> > 
> > The below 'hack' seems to solve the problem.
> > 
> > _However_ this also means the atomic_cmpxchg_relaxed() in the locked:
> > branch is equally wrong -- although not visible on x86. And note that
> > atomic_cmpxchg_acquire() would not in fact be sufficient either, since
> > the acquire is on the LOAD not the STORE of the LL/SC.
> > 
> > I need a break of sorts, because after twisting my head around the sem
> > code and then the qspinlock code I'm wrecked. I'll try and make a proper
> > patch if people can indeed confirm my thinking here.
> > 
> 
> I think your analysis is right, however, the problem only exists if we
> have the following use pattern, right?
> 
> 	CPU 0			CPU 1
> 	====================	==================
> 	spin_lock(A);		spin_lock(B);
> 	spin_unlock_wait(B);	spin_unlock_wait(A);
> 	do_something();		do_something();

More or less yes. The semaphore code is like:

	spin_lock(A)		spin_lock(B)
	spin_unlock_wait(B)	spin_is_locked(A)

which shows that both spin_is_locked() and spin_unlock_wait() are in the
same class.

> , which ends up CPU 0 and 1 both running do_something(). And actually
> this can be simply fixed by add smp_mb() between spin_lock() and
> spin_unlock_wait() on both CPU, or add an smp_mb() in spin_unlock_wait()
> as PPC does in 51d7d5205d338 "powerpc: Add smp_mb() to arch_spin_is_locked()".

Right and arm64 does in d86b8da04dfa. Curiously you only fixed
spin_is_locked() and Will only fixed spin_unlock_wait, while AFAIU we
need to have _BOTH_ fixed.

Now looking at the PPC code, spin_unlock_wait() as per
arch/powerpc/lib/locks.c actually does included the extra smp_mb().

> So if relaxed/acquire atomics and clear_pending_set_locked() work fine
> in other situations, a proper fix would be fixing the
> spin_is_locked()/spin_unlock_wait() or their users?

Right; the relaxed stores work fine for the 'regular' mutual exclusive
critical section usage of locks. And yes, I think only the case you
outlined can care about it.

Let me write a patch..

[toc] | [prev] | [next] | [standalone]

#1404569

On Fri, May 20, 2016 at 05:21:49PM +0200, Peter Zijlstra wrote:

> Let me write a patch..

OK, something like the below then.. lemme go build that and verify that
too fixes things.

---
Subject: locking,qspinlock: Fix spin_is_locked() and spin_unlock_wait()

Similar to commits:

  51d7d5205d33 ("powerpc: Add smp_mb() to arch_spin_is_locked()")
  d86b8da04dfa ("arm64: spinlock: serialise spin_unlock_wait against concurrent lockers")

qspinlock suffers from the fact that the _Q_LOCKED_VAL store is
unordered inside the ACQUIRE of the lock.

And while this is not a problem for the regular mutual exclusive
critical section usage of spinlocks, it breaks creative locking like:

	spin_lock(A)			spin_lock(B)
	spin_unlock_wait(B)		if (!spin_is_locked(A))
	do_something()			  do_something()

In that both CPUs can end up running do_something at the same time,
because our _Q_LOCKED_VAL store can drop past the spin_unlock_wait()
spin_is_locked() loads (even on x86!!).

To avoid making the normal case slower, add smp_mb()s to the less used
spin_unlock_wait() / spin_is_locked() side of things to avoid this
problem.

Reported-by: Davidlohr Bueso <dave@stgolabs.net>
Reported-by: Giovanni Gherdovich <ggherdovich@suse.com>
Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
---
 include/asm-generic/qspinlock.h | 27 ++++++++++++++++++++++++++-
 1 file changed, 26 insertions(+), 1 deletion(-)

diff --git a/include/asm-generic/qspinlock.h b/include/asm-generic/qspinlock.h
index 35a52a880b2f..6bd05700d8c9 100644
--- a/include/asm-generic/qspinlock.h
+++ b/include/asm-generic/qspinlock.h
@@ -28,7 +28,30 @@
  */
 static __always_inline int queued_spin_is_locked(struct qspinlock *lock)
 {
-	return atomic_read(&lock->val);
+	/*
+	 * queued_spin_lock_slowpath() can ACQUIRE the lock before
+	 * issuing the unordered store that sets _Q_LOCKED_VAL.
+	 *
+	 * See both smp_cond_acquire() sites for more detail.
+	 *
+	 * This however means that in code like:
+	 *
+	 *   spin_lock(A)		spin_lock(B)
+	 *   spin_unlock_wait(B)	spin_is_locked(A)
+	 *   do_something()		do_something()
+	 *
+	 * Both CPUs can end up running do_something() because the store
+	 * setting _Q_LOCKED_VAL will pass through the loads in
+	 * spin_unlock_wait() and/or spin_is_locked().
+	 *
+	 * Avoid this by issuing a full memory barrier between the spin_lock()
+	 * and the loads in spin_unlock_wait() and spin_is_locked().
+	 *
+	 * Note that regular mutual exclusion doesn't care about this
+	 * delayed store.
+	 */
+	smp_mb();
+	return atomic_read(&lock->val) & _Q_LOCKED_MASK;
 }
 
 /**
@@ -108,6 +131,8 @@ static __always_inline void queued_spin_unlock(struct qspinlock *lock)
  */
 static inline void queued_spin_unlock_wait(struct qspinlock *lock)
 {
+	/* See queued_spin_is_locked() */
+	smp_mb();
 	while (atomic_read(&lock->val) & _Q_LOCKED_MASK)
 		cpu_relax();
 }

[toc] | [prev] | [next] | [standalone]

#1404619

On Fri, May 20, 2016 at 9:04 AM, Peter Zijlstra <peterz@infradead.org> wrote:
> +        * queued_spin_lock_slowpath() can ACQUIRE the lock before
> +        * issuing the unordered store that sets _Q_LOCKED_VAL.

Ugh. This was my least favorite part of the queued locks, and I really
liked the completely unambiguous semantics of the x86 atomics-based
versions we used to have.

But I guess we're stuck with it.

That said, it strikes me that almost all of the users of
"spin_is_locked()" are using it for verification purposes (not locking
correctness), and that the people who are playing games with locking
correctness are few and already have to play *other* games anyway.

See for example "ipc_smp_acquire__after_spin_is_unlocked()", which has
a big comment atop of it that now becomes nonsensical with this patch.

So I do wonder if we should make that smp_mb() be something the
*caller* has to do, and document rules for it. IOW, introduce a new
spinlock primitive called "spin_lock_synchronize()", and then spinlock
implementations that have this non-atomic behavior with an unordered
store would do something like

    static inline void queued_spin_lock_synchronize(struct qspinlock
*a, struct qspinlock *b)
    {
        smp_mb();
    }

and then we'd document that *if* yuou need ordering guarantees between

   spin_lock(a);
   .. spin_is_locked/spin_wait_lock(b) ..

you have to have a

    spin_lock_synchronize(a, b);

in between.

A spin-lock implementation with the old x86 atomic semantics would
make it a no-op.

We should also introduce something like that
"splin_lock_acquire_after_unlock()" so that the ipc/sem.c behavior
would be documented too. Partly because some spinlock implementations
might have stronger unlock ordering and that could be a no-op for
them), but mostly for documentation of the rules.

Now, I'd take Peter's patch as-is, because I don't think any of this
matters from a *performance* standpoint, and Peter's patch is much
smaller and simpler.

But the reason I think it might be a good thing to introduce those
spin_lock_synchronize() and splin_lock_acquire_after_unlock() concepts
would be to make it very very clear what those subtle implementations
in mutexes and the multi-level locks in the ipc layer are doing and
what they rely on.

Comments? There are arguments for Peter's simple approach too ("robust
and simpler interface" vs "make our requirements explicit").

               Linus

[toc] | [prev] | [next] | [standalone]

#1404720

On Fri, May 20, 2016 at 10:00:45AM -0700, Linus Torvalds wrote:
> On Fri, May 20, 2016 at 9:04 AM, Peter Zijlstra <peterz@infradead.org> wrote:
> > +        * queued_spin_lock_slowpath() can ACQUIRE the lock before
> > +        * issuing the unordered store that sets _Q_LOCKED_VAL.
> 
> Ugh. This was my least favorite part of the queued locks, and I really
> liked the completely unambiguous semantics of the x86 atomics-based
> versions we used to have.
> 
> But I guess we're stuck with it.

Yeah, I wasn't too happy either when I realized it today. We _could_
make these atomic ops, but then we're just making things slower for this
one weird case :/

> That said, it strikes me that almost all of the users of
> "spin_is_locked()" are using it for verification purposes (not locking
> correctness),

Right; although I feel those people should be using
lockdep_assert_held() for this instead. That not only compiles out when
!LOCKDEP but also asserts the current task/cpu is the lock owner, not
someone else.

> and that the people who are playing games with locking
> correctness are few and already have to play *other* games anyway.
> 
> See for example "ipc_smp_acquire__after_spin_is_unlocked()", which has
> a big comment atop of it that now becomes nonsensical with this patch.

Not quite; we still need that I think.

We now have:

	spin_lock(A);
	smp_mb();
	while (!spin_is_locked(B))
		cpu_relax();
	smp_rmb();

And that control dependency together with the rmb form a load-acquire on
the unlocked B, which matches the release of the spin_unlock(B) and
ensures we observe the whole previous critical section we waited for.

The new smp_mb() doesn't help with that.

> Now, I'd take Peter's patch as-is, because I don't think any of this
> matters from a *performance* standpoint, and Peter's patch is much
> smaller and simpler.

I would suggest you do this and also mark it for stable v4.2 and later.

> But the reason I think it might be a good thing to introduce those
> spin_lock_synchronize() and splin_lock_acquire_after_unlock() concepts
> would be to make it very very clear what those subtle implementations
> in mutexes and the multi-level locks in the ipc layer are doing and
> what they rely on.

We can always do the fancy stuff on top, but that isn't going to need
backporting to all stable trees, this is.

I'll think a little more on the explicit document vs simple thing.

[toc] | [prev] | [next] | [standalone]

#1404739

On Fri, May 20, 2016 at 2:06 PM, Peter Zijlstra <peterz@infradead.org> wrote:
>>
>> See for example "ipc_smp_acquire__after_spin_is_unlocked()", which has
>> a big comment atop of it that now becomes nonsensical with this patch.
>
> Not quite; we still need that I think.

I think so too, but it's the *comment* that is nonsensical.

The comment says that "spin_unlock_wait() and !spin_is_locked() are
not memory barriers", and clearly now those instructions *are* memory
barriers with your patch.

However, the semaphore code wants a memory barrier after the _read_ in
the spin_unlocked_wait(), which it doesn't get.

So that is part of why I don't like the "hide memory barriers inside
the implementation".

Because once the operations aren't atomic (exactly like the spinlock
is now no longer atomic on x86: it's a separate read-with-acquire
followed by an unordered store for the queued case), the barrier
semantics within such an operation get very screwy.  There may be
barriers, but they aren't barriers to *everything*, they are just
barriers to part of the non-atomic operation.

If we were to make the synchronization explicit, we'd still have to
deal with all the subtle semantics, but now the subtle semantics would
at least be *explicit*. And it would make it much easier to explain
the barriers in that ipc semaphore code.

>> Now, I'd take Peter's patch as-is, because I don't think any of this
>> matters from a *performance* standpoint, and Peter's patch is much
>> smaller and simpler.
>
> I would suggest you do this and also mark it for stable v4.2 and later.

Oh, I definitely agree on the stable part, and yes, the "splt things
up" model should come later if people agree that it's a good thing.

Should I take the patch as-is, or should I just wait for a pull
request from the locking tree? Either is ok by me.

              Linus

[toc] | [prev] | [next] | [standalone]

#1404781

On Fri, 20 May 2016, Linus Torvalds wrote:


>Oh, I definitely agree on the stable part, and yes, the "splt things
>up" model should come later if people agree that it's a good thing.

The backporting part is quite nice, yes, but ultimately I think I prefer
Linus' suggestion making things explicit, as opposed to consulting the spinlock
implying barriers. I also hate to have an smp_mb() (particularly for spin_is_locked)
given that we are not optimizing for the common case (regular mutual excl).

As opposed to spin_is_locked(), spin_unlock_wait() is perhaps more tempting
to use for locking correctness. For example, taking a look at nf_conntrack_all_lock(),
it too likes to get smart with spin_unlock_wait() -- also for finer graining purposes.
While not identical to sems, it goes like:

nf_conntrack_all_lock():	nf_conntrack_lock():
spin_lock(B);			spin_lock(A);

				if (bar) { // false
bar = 1;			   ...
				}
[loop ctrl-barrier]				
  spin_unlock_wait(A);
foo();				foo();

If the spin_unlock_wait() doesn't yet see the store that makes A visibly locked,
we could end up with both threads in foo(), no?. (Although I'm unsure about that
ctrl barrier and archs could fall into it. The point was to see in-tree examples
of creative thinking with locking).

>Should I take the patch as-is, or should I just wait for a pull
>request from the locking tree? Either is ok by me.

I can verify that this patch fixes the issue.

Thanks,
Davidlohr

[toc] | [prev] | [next] | [standalone]

#1404790

On Fri, May 20, 2016 at 5:48 PM, Davidlohr Bueso <dave@stgolabs.net> wrote:
>
> I can verify that this patch fixes the issue.

Ok, I've applied it to my tree.

         Linus

[toc] | [prev] | [next] | [standalone]

#1404820

On Fri, May 20, 2016 at 05:48:39PM -0700, Davidlohr Bueso wrote:
> On Fri, 20 May 2016, Linus Torvalds wrote:
> 
> 
> >Oh, I definitely agree on the stable part, and yes, the "splt things
> >up" model should come later if people agree that it's a good thing.
> 
> The backporting part is quite nice, yes, but ultimately I think I prefer
> Linus' suggestion making things explicit, as opposed to consulting the spinlock
> implying barriers. I also hate to have an smp_mb() (particularly for spin_is_locked)
> given that we are not optimizing for the common case (regular mutual excl).

I'm confused; we _are_ optimizing for the common case. spin_is_locked()
is very unlikely to be used. And arguably should be used less in favour
of lockdep_assert_held().

> As opposed to spin_is_locked(), spin_unlock_wait() is perhaps more tempting
> to use for locking correctness. For example, taking a look at nf_conntrack_all_lock(),
> it too likes to get smart with spin_unlock_wait() -- also for finer graining purposes.
> While not identical to sems, it goes like:
> 
> nf_conntrack_all_lock():	nf_conntrack_lock():
> spin_lock(B);			spin_lock(A);
> 
> 				if (bar) { // false
> bar = 1;			   ...
> 				}
> [loop ctrl-barrier]				
>  spin_unlock_wait(A);
> foo();				foo();
> 
> If the spin_unlock_wait() doesn't yet see the store that makes A visibly locked,
> we could end up with both threads in foo(), no?. (Although I'm unsure about that
> ctrl barrier and archs could fall into it. The point was to see in-tree examples
> of creative thinking with locking).

I'm tempted to put that trailing smp_rmb() in spin_unlock_wait() too;
because I suspect the netfilter code is broken without it.

And it seems intuitive to assume that if we return from unlock_wait() we
can indeed observe the critical section we waited on.

Something a little like so; but then for _all_ implementations.

---
 include/asm-generic/qspinlock.h |  6 ++++++
 include/linux/compiler.h        | 13 ++++++++-----
 2 files changed, 14 insertions(+), 5 deletions(-)

diff --git a/include/asm-generic/qspinlock.h b/include/asm-generic/qspinlock.h
index 6bd05700d8c9..2f2eddd3e1f9 100644
--- a/include/asm-generic/qspinlock.h
+++ b/include/asm-generic/qspinlock.h
@@ -135,6 +135,12 @@ static inline void queued_spin_unlock_wait(struct qspinlock *lock)
 	smp_mb();
 	while (atomic_read(&lock->val) & _Q_LOCKED_MASK)
 		cpu_relax();
+
+	/*
+	 * Match the RELEASE of the spin_unlock() we just observed. Thereby
+	 * ensuring we observe the whole critical section that ended.
+	 */
+	smp_acquire__after_ctrl_dep();
 }
 
 #ifndef virt_spin_lock
diff --git a/include/linux/compiler.h b/include/linux/compiler.h
index 793c0829e3a3..3c4bc8160947 100644
--- a/include/linux/compiler.h
+++ b/include/linux/compiler.h
@@ -304,21 +304,24 @@ static __always_inline void __write_once_size(volatile void *p, void *res, int s
 	__u.__val;					\
 })
 
+/*
+ * A control dependency provides a LOAD->STORE order, the additional RMB
+ * provides LOAD->LOAD order, together they provide LOAD->{LOAD,STORE} order,
+ * aka. ACQUIRE.
+ */
+#define smp_acquire__after_ctrl_dep()	smp_rmb()
+
 /**
  * smp_cond_acquire() - Spin wait for cond with ACQUIRE ordering
  * @cond: boolean expression to wait for
  *
  * Equivalent to using smp_load_acquire() on the condition variable but employs
  * the control dependency of the wait to reduce the barrier on many platforms.
- *
- * The control dependency provides a LOAD->STORE order, the additional RMB
- * provides LOAD->LOAD order, together they provide LOAD->{LOAD,STORE} order,
- * aka. ACQUIRE.
  */
 #define smp_cond_acquire(cond)	do {		\
 	while (!(cond))				\
 		cpu_relax();			\
-	smp_rmb(); /* ctrl + rmb := acquire */	\
+	smp_acquire__after_ctrl_dep();		\
 } while (0)
 
 #endif /* __KERNEL__ */

[toc] | [prev] | [next] | [standalone]

#1404846

On 05/21/2016 09:37 AM, Peter Zijlstra wrote:
> On Fri, May 20, 2016 at 05:48:39PM -0700, Davidlohr Bueso wrote:
>> As opposed to spin_is_locked(), spin_unlock_wait() is perhaps more tempting
>> to use for locking correctness. For example, taking a look at nf_conntrack_all_lock(),
>> it too likes to get smart with spin_unlock_wait() -- also for finer graining purposes.
>> While not identical to sems, it goes like:
>>
>> nf_conntrack_all_lock():	nf_conntrack_lock():
>> spin_lock(B);			spin_lock(A);
>>
>> 				if (bar) { // false
>> bar = 1;			   ...
>> 				}
>> [loop ctrl-barrier]				
>>   spin_unlock_wait(A);
>> foo();				foo();
>>
>> If the spin_unlock_wait() doesn't yet see the store that makes A visibly locked,
>> we could end up with both threads in foo(), no?. (Although I'm unsure about that
>> ctrl barrier and archs could fall into it. The point was to see in-tree examples
>> of creative thinking with locking).
> I'm tempted to put that trailing smp_rmb() in spin_unlock_wait() too;
> because I suspect the netfilter code is broken without it.
>
> And it seems intuitive to assume that if we return from unlock_wait() we
> can indeed observe the critical section we waited on.
Then !spin_is_locked() and spin_unlock_wait() would be different with 
regards to memory barriers.
Would that really help?

My old plan was to document the rules, and define a generic 
smp_acquire__after_spin_is_unlocked.
https://lkml.org/lkml/2015/3/1/153

Noone supported it, so it ended up as 
ipc_smp_acquire__after_spin_is_unlocked().
Should we move it to linux/spinlock.h?

Who needs it?
- ipc/sem.c (but please start from the version from linux-next as 
reference, it is far less convoluted compared to the current code)
https://git.kernel.org/cgit/linux/kernel/git/next/linux-next.git/tree/ipc/sem.c

- nf_conntrack

- task_rq_lock() perhaps needs smp_acquire__after_ctrl_dep
(I didn't figure out yet what happened to the proposed patch)
https://lkml.org/lkml/2015/2/17/129

--
     Manfred

[toc] | [prev] | [next] | [standalone]

#1406055

On Sat, May 21, 2016 at 03:49:20PM +0200, Manfred Spraul wrote:

> >I'm tempted to put that trailing smp_rmb() in spin_unlock_wait() too;
> >because I suspect the netfilter code is broken without it.
> >
> >And it seems intuitive to assume that if we return from unlock_wait() we
> >can indeed observe the critical section we waited on.

> Then !spin_is_locked() and spin_unlock_wait() would be different with
> regards to memory barriers.
> Would that really help?

We could fix that I think; something horrible like:

static __always_inline int queued_spin_is_locked(struct qspinlock *lock)
{
	int locked;
	smp_mb();
	locked = atomic_read(&lock->val) & _Q_LOCKED_MASK;
	smp_acquire__after_ctrl_dep();
	return locked;
}

Which if used in a conditional like:

	spin_lock(A);
	if (spin_is_locked(B)) {
		spin_unlock(A);
		spin_lock(B);
		...
	}

would still provide the ACQUIRE semantics required. The only difference
is that it would provide it to _both_ branches, which might be a little
more expensive.

> My old plan was to document the rules, and define a generic
> smp_acquire__after_spin_is_unlocked.
> https://lkml.org/lkml/2015/3/1/153

Yeah; I more or less forgot all that.

Now, I too think having the thing documented is good; _however_ I also
think having primitives that actually do what you assume them to is a
good thing.

spin_unlock_wait() not actually serializing against the spin_unlock() is
really surprising and subtle.

[toc] | [prev] | [next] | [standalone]

#1404874

On Sat, 21 May 2016, Peter Zijlstra wrote:

>On Fri, May 20, 2016 at 05:48:39PM -0700, Davidlohr Bueso wrote:
>> On Fri, 20 May 2016, Linus Torvalds wrote:
>>
>>
>> >Oh, I definitely agree on the stable part, and yes, the "splt things
>> >up" model should come later if people agree that it's a good thing.
>>
>> The backporting part is quite nice, yes, but ultimately I think I prefer
>> Linus' suggestion making things explicit, as opposed to consulting the spinlock
>> implying barriers. I also hate to have an smp_mb() (particularly for spin_is_locked)
>> given that we are not optimizing for the common case (regular mutual excl).
>
>I'm confused; we _are_ optimizing for the common case. spin_is_locked()
>is very unlikely to be used. And arguably should be used less in favour
>of lockdep_assert_held().

Indeed we are.

But by 'common case' I was really thinking about spin_is_locked() vs spin_wait_unlock().
The former being the more common of the two, and the one which mostly will _not_ be used
for lock correctness purposes, hence it doesn't need that new smp_mb. Hence allowing users
to explicitly set the ordering needs (ie spin_lock_synchronize()) seems like the better
long term alternative. otoh, with your approach all such bugs are automatically fixed :)

Thanks,
Davidlohr

[toc] | [prev] | [next] | [standalone]

#1405315

On Fri, May 20, 2016 at 10:00:45AM -0700, Linus Torvalds wrote:

> So I do wonder if we should make that smp_mb() be something the
> *caller* has to do, and document rules for it. IOW, introduce a new
> spinlock primitive called "spin_lock_synchronize()", and then spinlock
> implementations that have this non-atomic behavior with an unordered
> store would do something like
> 
>     static inline void queued_spin_lock_synchronize(struct qspinlock
> *a, struct qspinlock *b)
>     {
>         smp_mb();
>     }
> 
> and then we'd document that *if* yuou need ordering guarantees between
> 
>    spin_lock(a);
>    .. spin_is_locked/spin_wait_lock(b) ..
> 
> you have to have a
> 
>     spin_lock_synchronize(a, b);
> 
> in between.

So I think I favour the explicit barrier. But my 'problem' is that we
now have _two_ different scenarios in which we need to order two
different spinlocks.

The first is the RCpc vs RCsc spinlock situation (currently only on
PowerPC). Where the spin_unlock() spin_lock() 'barier' is not
transitive.

And the second is this 'new' situation, where the store is unordered and
is not observable until a release, which is fundamentally so on PPC and
ARM64 but also possible due to lock implementation choices like with our
qspinlock, which makes it manifest even on x86.

Now, ideally we'd be able to use one barrier construct for both; but
given that, while there is overlap, they're not the same. And I'd be
somewhat reluctant to issue superfluous smp_mb()s just because; it is an
expensive instruction.

Paul has smp_mb__after_unlock_lock() for the RCpc 'upgrade'. How about
something like:

	smp_mb__after_lock()

?


OTOH; even if we document this, it is something that is easy to forget
or miss. It is not like Documentation/memory-barriers.txt is in want of
more complexity.

[toc] | [prev] | [next] | [standalone]

#1405550

On Mon, May 23, 2016 at 5:25 AM, Peter Zijlstra <peterz@infradead.org> wrote:
>
> Paul has smp_mb__after_unlock_lock() for the RCpc 'upgrade'. How about
> something like:
>
>         smp_mb__after_lock()

I'd much rather make the naming be higher level. It's not necessarily
going to be a "mb", and while the problem is about smp, the primitives
it is synchronizing aren't actually smp-specific (ie you're
synchronizing a lock that is relevant on UP too).

So I'd just call it something like

        spin_lock_sync_after_lock();

because different locks might have different levels of serialization
(ie maybe a spinlock needs one thing, and a mutex needs another - if
we start worrying about ordering between spin_lock and
mutex_is_locked(), for example, or between mutex_lock() and
spin_is_locked()).

Hmm?

                     Linus

[toc] | [prev] | [next] | [standalone]

#1406676

[Multipart message — attachments visible in raw view] — view raw

On Mon, May 23, 2016 at 10:52:09AM -0700, Linus Torvalds wrote:
> On Mon, May 23, 2016 at 5:25 AM, Peter Zijlstra <peterz@infradead.org> wrote:
> >
> > Paul has smp_mb__after_unlock_lock() for the RCpc 'upgrade'. How about
> > something like:
> >
> >         smp_mb__after_lock()
> 
> I'd much rather make the naming be higher level. It's not necessarily

Speak of higher level, I realize that problem here is similar to the
problem we discussed last year:

http://lkml.kernel.org/r/20151112070915.GC6314@fixme-laptop.cn.ibm.com

the problem here is about synchronization between two spinlocks and that
problem is about synchronization between a spinlock and ordinary
variables.

(One result of this similarity is that qspinlock on x86 may be also
broken in the do_exit() code as spinlocks on AARCH64 and PPC. Because
a variable LOAD inside a qspinlock critical section could be reordered
before the STORE part of a qspinlock acquisition.)


For the problem we found last year, the current solution for AARCH64 and
PPC is to have a little heavy weight spin_unlock_wait() to pair with
spin_lock():

AARCH64: http://lkml.kernel.org/r/1448624646-15863-1-git-send-email-will.deacon@arm.com
PPC: http://lkml.kernel.org/r/1461130033-70898-1-git-send-email-boqun.feng@gmail.com (not merged yet)

Another solution works on PPC is what Paul Mckenney suggested, using
smp_mb__after_unlock_lock():

http://lkml.kernel.org/r/20151112144004.GU3972@linux.vnet.ibm.com

, which is petty much the same as the spinlock synchronization
primitive we are discussing about here.


So I'm thinking, if we are going to introduce some primitives for
synchronizing two spinlocks (or even a spinlock and a mutex) anyway,
could we be a little more higher level, to reuse/invent primitives to
solve the synchronzing problem we have between
spinlocks(spin_unlock_wait()) and normal variables?

One benefit of this is that we could drop the complex implementations of
spin_unlock_wait() on AARCH64 and PPC.

Thoughts?

Regards,
Boqun

> going to be a "mb", and while the problem is about smp, the primitives
> it is synchronizing aren't actually smp-specific (ie you're
> synchronizing a lock that is relevant on UP too).
> 
> So I'd just call it something like
> 
>         spin_lock_sync_after_lock();
> 
> because different locks might have different levels of serialization
> (ie maybe a spinlock needs one thing, and a mutex needs another - if
> we start worrying about ordering between spin_lock and
> mutex_is_locked(), for example, or between mutex_lock() and
> spin_is_locked()).
> 
> Hmm?
> 
>                      Linus

[toc] | [prev] | [next] | [standalone]

#1404923

Hi Peter,


On 05/20/2016 06:04 PM, Peter Zijlstra wrote:
> On Fri, May 20, 2016 at 05:21:49PM +0200, Peter Zijlstra wrote:
>
>> Let me write a patch..
> OK, something like the below then.. lemme go build that and verify that
> too fixes things.
>
> ---
> Subject: locking,qspinlock: Fix spin_is_locked() and spin_unlock_wait()
>
> Similar to commits:
>
>    51d7d5205d33 ("powerpc: Add smp_mb() to arch_spin_is_locked()")
>    d86b8da04dfa ("arm64: spinlock: serialise spin_unlock_wait against concurrent lockers")
>
> qspinlock suffers from the fact that the _Q_LOCKED_VAL store is
> unordered inside the ACQUIRE of the lock.
>
> And while this is not a problem for the regular mutual exclusive
> critical section usage of spinlocks, it breaks creative locking like:
>
> 	spin_lock(A)			spin_lock(B)
> 	spin_unlock_wait(B)		if (!spin_is_locked(A))
> 	do_something()			  do_something()
>
> In that both CPUs can end up running do_something at the same time,
> because our _Q_LOCKED_VAL store can drop past the spin_unlock_wait()
> spin_is_locked() loads (even on x86!!).
How would we handle mixed spin_lock()/mutex_lock() code?
For the IPC code, I would like to replace the outer lock with a mutex.
The code only uses spinlocks, because at the time it was written, the 
mutex code didn't contain a busy wait.
With a mutex, the code would become simpler (all the 
lock/unlock/kmalloc/relock parts could be removed).

The result would be something like:

	mutex_lock(A)			spin_lock(B)
	spin_unlock_wait(B)		if (!mutex_is_locked(A))
	do_something()			  do_something()

--
     Manfred

[toc] | [prev] | [next] | [standalone]

#1404987

On Sun, May 22, 2016 at 10:43:08AM +0200, Manfred Spraul wrote:
> How would we handle mixed spin_lock()/mutex_lock() code?
> For the IPC code, I would like to replace the outer lock with a mutex.
> The code only uses spinlocks, because at the time it was written, the mutex
> code didn't contain a busy wait.
> With a mutex, the code would become simpler (all the
> lock/unlock/kmalloc/relock parts could be removed).
> 
> The result would be something like:
> 
> 	mutex_lock(A)			spin_lock(B)
> 	spin_unlock_wait(B)		if (!mutex_is_locked(A))
> 	do_something()			  do_something()
> 

Should work similarly, but we'll have to audit mutex for these same
issues. I'll put it on todo.

[toc] | [prev] | [next] | [standalone]

#1404581

On Fri, 20 May 2016, Peter Zijlstra wrote:

>The problem is that the clear_pending_set_locked() is an unordered
>store, therefore this store can be delayed until no later than
>spin_unlock() (which orders against it due to the address dependency).
>
>This opens numerous races; for example:
>
>	ipc_lock_object(&sma->sem_perm);
>	sem_wait_array(sma);
>
>				false   ->	spin_is_locked(&sma->sem_perm.lock)
>
>is entirely possible, because sem_wait_array() consists of pure reads,
>so the store can pass all that, even on x86.

I had pondered at the unordered stores in clear_pending_set_locked() for arm,
for example, but I _certainly_ missed this for x86 inside the ACQUIRE region.

Thanks,
Davidlohr

[toc] | [prev] | [next] | [standalone]

#1404714

On 05/20/2016 07:58 AM, Peter Zijlstra wrote:
> On Thu, May 19, 2016 at 10:39:26PM -0700, Davidlohr Bueso wrote:
>> As such, the following restores the behavior of the ticket locks and 'fixes'
>> (or hides?) the bug in sems. Naturally incorrect approach:
>>
>> @@ -290,7 +290,8 @@ static void sem_wait_array(struct sem_array *sma)
>>
>> 	for (i = 0; i<  sma->sem_nsems; i++) {
>> 		sem = sma->sem_base + i;
>> -               spin_unlock_wait(&sem->lock);
>> +               while (atomic_read(&sem->lock))
>> +                       cpu_relax();
>> 	}
>> 	ipc_smp_acquire__after_spin_is_unlocked();
>> }
> The actual bug is clear_pending_set_locked() not having acquire
> semantics. And the above 'fixes' things because it will observe the old
> pending bit or the locked bit, so it doesn't matter if the store
> flipping them is delayed.

The clear_pending_set_locked() is not the only place where the lock is 
set. If there are more than one waiter, the queuing patch will be used 
instead. The set_locked(), which is also an unordered store, will then 
be used to set the lock.

Cheers,
Longman

[toc] | [prev] | [next] | [standalone]

#1404718

On Fri, May 20, 2016 at 04:44:19PM -0400, Waiman Long wrote:
> On 05/20/2016 07:58 AM, Peter Zijlstra wrote:
> >On Thu, May 19, 2016 at 10:39:26PM -0700, Davidlohr Bueso wrote:
> >>As such, the following restores the behavior of the ticket locks and 'fixes'
> >>(or hides?) the bug in sems. Naturally incorrect approach:
> >>
> >>@@ -290,7 +290,8 @@ static void sem_wait_array(struct sem_array *sma)
> >>
> >>	for (i = 0; i<  sma->sem_nsems; i++) {
> >>		sem = sma->sem_base + i;
> >>-               spin_unlock_wait(&sem->lock);
> >>+               while (atomic_read(&sem->lock))
> >>+                       cpu_relax();
> >>	}
> >>	ipc_smp_acquire__after_spin_is_unlocked();
> >>}
> >The actual bug is clear_pending_set_locked() not having acquire
> >semantics. And the above 'fixes' things because it will observe the old
> >pending bit or the locked bit, so it doesn't matter if the store
> >flipping them is delayed.
> 
> The clear_pending_set_locked() is not the only place where the lock is set.
> If there are more than one waiter, the queuing patch will be used instead.
> The set_locked(), which is also an unordered store, will then be used to set
> the lock.

Ah yes. I didn't get that far. One case was enough :-)

[toc] | [prev] | [standalone]

Page 2 of 2 — ← Prev page 1 [2]

Back to top | Article view | linux.kernel

csiph-web