[PATCH] locking/qrwlock: Fix ordering in queued_write_lock_slowpath

[PATCH] locking/qrwlock: Fix ordering in queued_write_lock_slowpath

[Ali Saidi]

While this code is executed with the wait_lock held, a reader can
acquire the lock without holding wait_lock.  The writer side loops
checking the value with the atomic_cond_read_acquire(), but only truly
acquires the lock when the compare-and-exchange is completed
successfully which isn’t ordered. The other atomic operations from this
point are release-ordered and thus reads after the lock acquisition can
be completed before the lock is truly acquired which violates the
guarantees the lock should be making.

Fixes: b519b56e378ee ("locking/qrwlock: Use atomic_cond_read_acquire() when spinning in qrwloc")
Signed-off-by: Ali Saidi <alisaidi@amazon.com>
Cc: stable@vger.kernel.org
---
 kernel/locking/qrwlock.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/kernel/locking/qrwlock.c b/kernel/locking/qrwlock.c
index 4786dd271b45..10770f6ac4d9 100644
--- a/kernel/locking/qrwlock.c
+++ b/kernel/locking/qrwlock.c
@@ -73,8 +73,8 @@ void queued_write_lock_slowpath(struct qrwlock *lock)
 
 	/* When no more readers or writers, set the locked flag */
 	do {
-		atomic_cond_read_acquire(&lock->cnts, VAL == _QW_WAITING);
-	} while (atomic_cmpxchg_relaxed(&lock->cnts, _QW_WAITING,
+		atomic_cond_read_relaxed(&lock->cnts, VAL == _QW_WAITING);
+	} while (atomic_cmpxchg_acquire(&lock->cnts, _QW_WAITING,
 					_QW_LOCKED) != _QW_WAITING);
 unlock:
 	arch_spin_unlock(&lock->wait_lock);
-- 
2.24.4.AMZN

Re: [PATCH] locking/qrwlock: Fix ordering in queued_write_lock_slowpath

[Will Deacon]

On Thu, Apr 15, 2021 at 02:25:52PM +0000, Ali Saidi wrote:
> While this code is executed with the wait_lock held, a reader can
> acquire the lock without holding wait_lock.  The writer side loops
> checking the value with the atomic_cond_read_acquire(), but only truly
> acquires the lock when the compare-and-exchange is completed
> successfully which isn’t ordered. The other atomic operations from this
> point are release-ordered and thus reads after the lock acquisition can
> be completed before the lock is truly acquired which violates the
> guarantees the lock should be making.

I think it would be worth spelling this out with an example. The issue
appears to be a concurrent reader in interrupt context taking and releasing
the lock in the window where the writer has returned from the
atomic_cond_read_acquire() but has not yet performed the cmpxchg(). Loads
can be speculated during this time, but the A-B-A of the lock word
from _QW_WAITING to (_QW_WAITING | _QR_BIAS) and back to _QW_WAITING allows
the atomic_cmpxchg_relaxed() to succeed. Is that right?

With that in mind, it would probably be a good idea to eyeball the qspinlock
slowpath as well, as that uses both atomic_cond_read_acquire() and
atomic_try_cmpxchg_relaxed().

> Fixes: b519b56e378ee ("locking/qrwlock: Use atomic_cond_read_acquire() when spinning in qrwloc")

Typo in the quoted subject ('qrwloc').

> Signed-off-by: Ali Saidi <alisaidi@amazon.com>
> Cc: stable@vger.kernel.org
> ---
>  kernel/locking/qrwlock.c | 4 ++--
>  1 file changed, 2 insertions(+), 2 deletions(-)
> 
> diff --git a/kernel/locking/qrwlock.c b/kernel/locking/qrwlock.c
> index 4786dd271b45..10770f6ac4d9 100644
> --- a/kernel/locking/qrwlock.c
> +++ b/kernel/locking/qrwlock.c
> @@ -73,8 +73,8 @@ void queued_write_lock_slowpath(struct qrwlock *lock)
>  
>  	/* When no more readers or writers, set the locked flag */
>  	do {
> -		atomic_cond_read_acquire(&lock->cnts, VAL == _QW_WAITING);
> -	} while (atomic_cmpxchg_relaxed(&lock->cnts, _QW_WAITING,
> +		atomic_cond_read_relaxed(&lock->cnts, VAL == _QW_WAITING);
> +	} while (atomic_cmpxchg_acquire(&lock->cnts, _QW_WAITING,
>  					_QW_LOCKED) != _QW_WAITING);

Patch looks good, so with an updated message:

Acked-by: Will Deacon <will@kernel.org>

Will

Re: [PATCH] locking/qrwlock: Fix ordering in queued_write_lock_slowpath

[Peter Zijlstra]

On Thu, Apr 15, 2021 at 02:25:52PM +0000, Ali Saidi wrote:
> While this code is executed with the wait_lock held, a reader can
> acquire the lock without holding wait_lock.  The writer side loops
> checking the value with the atomic_cond_read_acquire(), but only truly
> acquires the lock when the compare-and-exchange is completed
> successfully which isn’t ordered. The other atomic operations from this
> point are release-ordered and thus reads after the lock acquisition can
> be completed before the lock is truly acquired which violates the
> guarantees the lock should be making.

Should be per who? We explicitly do not order the lock acquire store.
qspinlock has the exact same issue.

If you look in the git history surrounding spin_is_locked(), you'll find
'lovely' things.

Basically, if you're doing crazy things with spin_is_locked() you get to
keep the pieces.

> Fixes: b519b56e378ee ("locking/qrwlock: Use atomic_cond_read_acquire() when spinning in qrwloc")
> Signed-off-by: Ali Saidi <alisaidi@amazon.com>
> Cc: stable@vger.kernel.org
> ---
>  kernel/locking/qrwlock.c | 4 ++--
>  1 file changed, 2 insertions(+), 2 deletions(-)
> 
> diff --git a/kernel/locking/qrwlock.c b/kernel/locking/qrwlock.c
> index 4786dd271b45..10770f6ac4d9 100644
> --- a/kernel/locking/qrwlock.c
> +++ b/kernel/locking/qrwlock.c
> @@ -73,8 +73,8 @@ void queued_write_lock_slowpath(struct qrwlock *lock)
>  
>  	/* When no more readers or writers, set the locked flag */
>  	do {
> -		atomic_cond_read_acquire(&lock->cnts, VAL == _QW_WAITING);
> -	} while (atomic_cmpxchg_relaxed(&lock->cnts, _QW_WAITING,
> +		atomic_cond_read_relaxed(&lock->cnts, VAL == _QW_WAITING);
> +	} while (atomic_cmpxchg_acquire(&lock->cnts, _QW_WAITING,
>  					_QW_LOCKED) != _QW_WAITING);
>  unlock:
>  	arch_spin_unlock(&lock->wait_lock);

This doesn't make sense, there is no such thing as a store-acquire. What
you're doing here is moving the acquire from one load to the next. A
load we know will load the exact same value.

Also see Documentation/atomic_t.txt:

  {}_acquire: the R of the RMW (or atomic_read) is an ACQUIRE


If anything this code wants to be written like so.

---

diff --git a/kernel/locking/qrwlock.c b/kernel/locking/qrwlock.c
index 4786dd271b45..22aeccc363ca 100644
--- a/kernel/locking/qrwlock.c
+++ b/kernel/locking/qrwlock.c
@@ -60,6 +60,8 @@ EXPORT_SYMBOL(queued_read_lock_slowpath);
  */
 void queued_write_lock_slowpath(struct qrwlock *lock)
 {
+	u32 cnt;
+
 	/* Put the writer into the wait queue */
 	arch_spin_lock(&lock->wait_lock);
 
@@ -73,9 +75,8 @@ void queued_write_lock_slowpath(struct qrwlock *lock)
 
 	/* When no more readers or writers, set the locked flag */
 	do {
-		atomic_cond_read_acquire(&lock->cnts, VAL == _QW_WAITING);
-	} while (atomic_cmpxchg_relaxed(&lock->cnts, _QW_WAITING,
-					_QW_LOCKED) != _QW_WAITING);
+		cnt = atomic_cond_read_acquire(&lock->cnts, VAL == _QW_WAITING);
+	} while (!atomic_try_cmpxchg_relaxed(&lock->cnts, &cnt, _QW_LOCKED));
 unlock:
 	arch_spin_unlock(&lock->wait_lock);
 }

Re: [PATCH] locking/qrwlock: Fix ordering in queued_write_lock_slowpath

[Waiman Long]

On 4/15/21 10:25 AM, Ali Saidi wrote:
> While this code is executed with the wait_lock held, a reader can
> acquire the lock without holding wait_lock.  The writer side loops
> checking the value with the atomic_cond_read_acquire(), but only truly
> acquires the lock when the compare-and-exchange is completed
> successfully which isn’t ordered. The other atomic operations from this
> point are release-ordered and thus reads after the lock acquisition can
> be completed before the lock is truly acquired which violates the
> guarantees the lock should be making.
>
> Fixes: b519b56e378ee ("locking/qrwlock: Use atomic_cond_read_acquire() when spinning in qrwloc")
> Signed-off-by: Ali Saidi <alisaidi@amazon.com>
> Cc: stable@vger.kernel.org
> ---
>   kernel/locking/qrwlock.c | 4 ++--
>   1 file changed, 2 insertions(+), 2 deletions(-)
>
> diff --git a/kernel/locking/qrwlock.c b/kernel/locking/qrwlock.c
> index 4786dd271b45..10770f6ac4d9 100644
> --- a/kernel/locking/qrwlock.c
> +++ b/kernel/locking/qrwlock.c
> @@ -73,8 +73,8 @@ void queued_write_lock_slowpath(struct qrwlock *lock)
>   
>   	/* When no more readers or writers, set the locked flag */
>   	do {
> -		atomic_cond_read_acquire(&lock->cnts, VAL == _QW_WAITING);
> -	} while (atomic_cmpxchg_relaxed(&lock->cnts, _QW_WAITING,
> +		atomic_cond_read_relaxed(&lock->cnts, VAL == _QW_WAITING);
> +	} while (atomic_cmpxchg_acquire(&lock->cnts, _QW_WAITING,
>   					_QW_LOCKED) != _QW_WAITING);
>   unlock:
>   	arch_spin_unlock(&lock->wait_lock);

I think the original code isn't wrong. The read_acquire provides the 
acquire barrier for cmpxchg. Because of conditional dependency, the 
wait_lock unlock won't happen until the cmpxchg succeeds. Without doing 
a read_acquire, there may be a higher likelihood that the cmpxchg may fail.

Anyway, I will let Will or Peter chime in on this as I am not as 
proficient as them on this topic.

Cheers,
Longman

Re: [PATCH] locking/qrwlock: Fix ordering in queued_write_lock_slowpath

[Will Deacon]

On Thu, Apr 15, 2021 at 05:03:58PM +0200, Peter Zijlstra wrote:
> On Thu, Apr 15, 2021 at 02:25:52PM +0000, Ali Saidi wrote:
> > While this code is executed with the wait_lock held, a reader can
> > acquire the lock without holding wait_lock.  The writer side loops
> > checking the value with the atomic_cond_read_acquire(), but only truly
> > acquires the lock when the compare-and-exchange is completed
> > successfully which isn’t ordered. The other atomic operations from this
> > point are release-ordered and thus reads after the lock acquisition can
> > be completed before the lock is truly acquired which violates the
> > guarantees the lock should be making.
> 
> Should be per who? We explicitly do not order the lock acquire store.
> qspinlock has the exact same issue.
> 
> If you look in the git history surrounding spin_is_locked(), you'll find
> 'lovely' things.
> 
> Basically, if you're doing crazy things with spin_is_locked() you get to
> keep the pieces.
> 
> > Fixes: b519b56e378ee ("locking/qrwlock: Use atomic_cond_read_acquire() when spinning in qrwloc")
> > Signed-off-by: Ali Saidi <alisaidi@amazon.com>
> > Cc: stable@vger.kernel.org
> > ---
> >  kernel/locking/qrwlock.c | 4 ++--
> >  1 file changed, 2 insertions(+), 2 deletions(-)
> > 
> > diff --git a/kernel/locking/qrwlock.c b/kernel/locking/qrwlock.c
> > index 4786dd271b45..10770f6ac4d9 100644
> > --- a/kernel/locking/qrwlock.c
> > +++ b/kernel/locking/qrwlock.c
> > @@ -73,8 +73,8 @@ void queued_write_lock_slowpath(struct qrwlock *lock)
> >  
> >  	/* When no more readers or writers, set the locked flag */
> >  	do {
> > -		atomic_cond_read_acquire(&lock->cnts, VAL == _QW_WAITING);
> > -	} while (atomic_cmpxchg_relaxed(&lock->cnts, _QW_WAITING,
> > +		atomic_cond_read_relaxed(&lock->cnts, VAL == _QW_WAITING);
> > +	} while (atomic_cmpxchg_acquire(&lock->cnts, _QW_WAITING,
> >  					_QW_LOCKED) != _QW_WAITING);
> >  unlock:
> >  	arch_spin_unlock(&lock->wait_lock);
> 
> This doesn't make sense, there is no such thing as a store-acquire. What
> you're doing here is moving the acquire from one load to the next. A
> load we know will load the exact same value.
> 
> Also see Documentation/atomic_t.txt:
> 
>   {}_acquire: the R of the RMW (or atomic_read) is an ACQUIRE
> 
> 
> If anything this code wants to be written like so.
> 
> ---
> 
> diff --git a/kernel/locking/qrwlock.c b/kernel/locking/qrwlock.c
> index 4786dd271b45..22aeccc363ca 100644
> --- a/kernel/locking/qrwlock.c
> +++ b/kernel/locking/qrwlock.c
> @@ -60,6 +60,8 @@ EXPORT_SYMBOL(queued_read_lock_slowpath);
>   */
>  void queued_write_lock_slowpath(struct qrwlock *lock)
>  {
> +	u32 cnt;
> +
>  	/* Put the writer into the wait queue */
>  	arch_spin_lock(&lock->wait_lock);
>  
> @@ -73,9 +75,8 @@ void queued_write_lock_slowpath(struct qrwlock *lock)
>  
>  	/* When no more readers or writers, set the locked flag */
>  	do {
> -		atomic_cond_read_acquire(&lock->cnts, VAL == _QW_WAITING);
> -	} while (atomic_cmpxchg_relaxed(&lock->cnts, _QW_WAITING,
> -					_QW_LOCKED) != _QW_WAITING);
> +		cnt = atomic_cond_read_acquire(&lock->cnts, VAL == _QW_WAITING);

I think the issue is that >here< a concurrent reader in interrupt context
can take the lock and release it again, but we could speculate reads from
the critical section up over the later release and up before the control
dependency here...

> +	} while (!atomic_try_cmpxchg_relaxed(&lock->cnts, &cnt, _QW_LOCKED));

... and then this cmpxchg() will succeed, so our speculated stale reads
could be used.

*HOWEVER*

Speculating a read should be fine in the face of a concurrent _reader_,
so for this to be an issue it implies that the reader is also doing some
(atomic?) updates.

Ali?

Will

Re: [PATCH] locking/qrwlock: Fix ordering in queued_write_lock_slowpath

[Catalin Marinas]

On Thu, Apr 15, 2021 at 04:28:21PM +0100, Will Deacon wrote:
> On Thu, Apr 15, 2021 at 05:03:58PM +0200, Peter Zijlstra wrote:
> > On Thu, Apr 15, 2021 at 02:25:52PM +0000, Ali Saidi wrote:
> > > While this code is executed with the wait_lock held, a reader can
> > > acquire the lock without holding wait_lock.  The writer side loops
> > > checking the value with the atomic_cond_read_acquire(), but only truly
> > > acquires the lock when the compare-and-exchange is completed
> > > successfully which isn’t ordered. The other atomic operations from this
> > > point are release-ordered and thus reads after the lock acquisition can
> > > be completed before the lock is truly acquired which violates the
> > > guarantees the lock should be making.
[...]
> > > Fixes: b519b56e378ee ("locking/qrwlock: Use atomic_cond_read_acquire() when spinning in qrwloc")
> > > Signed-off-by: Ali Saidi <alisaidi@amazon.com>
> > > Cc: stable@vger.kernel.org
> > > ---
> > >  kernel/locking/qrwlock.c | 4 ++--
> > >  1 file changed, 2 insertions(+), 2 deletions(-)
> > > 
> > > diff --git a/kernel/locking/qrwlock.c b/kernel/locking/qrwlock.c
> > > index 4786dd271b45..10770f6ac4d9 100644
> > > --- a/kernel/locking/qrwlock.c
> > > +++ b/kernel/locking/qrwlock.c
> > > @@ -73,8 +73,8 @@ void queued_write_lock_slowpath(struct qrwlock *lock)
> > >  
> > >  	/* When no more readers or writers, set the locked flag */
> > >  	do {
> > > -		atomic_cond_read_acquire(&lock->cnts, VAL == _QW_WAITING);
> > > -	} while (atomic_cmpxchg_relaxed(&lock->cnts, _QW_WAITING,
> > > +		atomic_cond_read_relaxed(&lock->cnts, VAL == _QW_WAITING);
> > > +	} while (atomic_cmpxchg_acquire(&lock->cnts, _QW_WAITING,
> > >  					_QW_LOCKED) != _QW_WAITING);
> > >  unlock:
> > >  	arch_spin_unlock(&lock->wait_lock);
> > 
> > This doesn't make sense, there is no such thing as a store-acquire. What
> > you're doing here is moving the acquire from one load to the next. A
> > load we know will load the exact same value.
> > 
> > Also see Documentation/atomic_t.txt:
> > 
> >   {}_acquire: the R of the RMW (or atomic_read) is an ACQUIRE
> > 
> > 
> > If anything this code wants to be written like so.
> > 
> > ---
> > 
> > diff --git a/kernel/locking/qrwlock.c b/kernel/locking/qrwlock.c
> > index 4786dd271b45..22aeccc363ca 100644
> > --- a/kernel/locking/qrwlock.c
> > +++ b/kernel/locking/qrwlock.c
> > @@ -60,6 +60,8 @@ EXPORT_SYMBOL(queued_read_lock_slowpath);
> >   */
> >  void queued_write_lock_slowpath(struct qrwlock *lock)
> >  {
> > +	u32 cnt;
> > +
> >  	/* Put the writer into the wait queue */
> >  	arch_spin_lock(&lock->wait_lock);
> >  
> > @@ -73,9 +75,8 @@ void queued_write_lock_slowpath(struct qrwlock *lock)
> >  
> >  	/* When no more readers or writers, set the locked flag */
> >  	do {
> > -		atomic_cond_read_acquire(&lock->cnts, VAL == _QW_WAITING);
> > -	} while (atomic_cmpxchg_relaxed(&lock->cnts, _QW_WAITING,
> > -					_QW_LOCKED) != _QW_WAITING);
> > +		cnt = atomic_cond_read_acquire(&lock->cnts, VAL == _QW_WAITING);
> 
> I think the issue is that >here< a concurrent reader in interrupt context
> can take the lock and release it again, but we could speculate reads from
> the critical section up over the later release and up before the control
> dependency here...
> 
> > +	} while (!atomic_try_cmpxchg_relaxed(&lock->cnts, &cnt, _QW_LOCKED));
> 
> ... and then this cmpxchg() will succeed, so our speculated stale reads
> could be used.
> 
> *HOWEVER*
> 
> Speculating a read should be fine in the face of a concurrent _reader_,
> so for this to be an issue it implies that the reader is also doing some
> (atomic?) updates.

There's at least one such case: see chain_epi_lockless() updating
epi->next, called from ep_poll_callback() with a read_lock held. This
races with ep_done_scan() which has the write_lock held.

I think the authors of the above code interpreted the read_lock as
something that multiple threads can own disregarding the _read_ part.

-- 
Catalin

Re: [PATCH] locking/qrwlock: Fix ordering in queued_write_lock_slowpath

[Will Deacon]

On Thu, Apr 15, 2021 at 04:37:58PM +0100, Catalin Marinas wrote:
> On Thu, Apr 15, 2021 at 04:28:21PM +0100, Will Deacon wrote:
> > On Thu, Apr 15, 2021 at 05:03:58PM +0200, Peter Zijlstra wrote:
> > > diff --git a/kernel/locking/qrwlock.c b/kernel/locking/qrwlock.c
> > > index 4786dd271b45..22aeccc363ca 100644
> > > --- a/kernel/locking/qrwlock.c
> > > +++ b/kernel/locking/qrwlock.c
> > > @@ -60,6 +60,8 @@ EXPORT_SYMBOL(queued_read_lock_slowpath);
> > >   */
> > >  void queued_write_lock_slowpath(struct qrwlock *lock)
> > >  {
> > > +	u32 cnt;
> > > +
> > >  	/* Put the writer into the wait queue */
> > >  	arch_spin_lock(&lock->wait_lock);
> > >  
> > > @@ -73,9 +75,8 @@ void queued_write_lock_slowpath(struct qrwlock *lock)
> > >  
> > >  	/* When no more readers or writers, set the locked flag */
> > >  	do {
> > > -		atomic_cond_read_acquire(&lock->cnts, VAL == _QW_WAITING);
> > > -	} while (atomic_cmpxchg_relaxed(&lock->cnts, _QW_WAITING,
> > > -					_QW_LOCKED) != _QW_WAITING);
> > > +		cnt = atomic_cond_read_acquire(&lock->cnts, VAL == _QW_WAITING);
> > 
> > I think the issue is that >here< a concurrent reader in interrupt context
> > can take the lock and release it again, but we could speculate reads from
> > the critical section up over the later release and up before the control
> > dependency here...
> > 
> > > +	} while (!atomic_try_cmpxchg_relaxed(&lock->cnts, &cnt, _QW_LOCKED));
> > 
> > ... and then this cmpxchg() will succeed, so our speculated stale reads
> > could be used.
> > 
> > *HOWEVER*
> > 
> > Speculating a read should be fine in the face of a concurrent _reader_,
> > so for this to be an issue it implies that the reader is also doing some
> > (atomic?) updates.
> 
> There's at least one such case: see chain_epi_lockless() updating
> epi->next, called from ep_poll_callback() with a read_lock held. This
> races with ep_done_scan() which has the write_lock held.

Do you know if that's the code which triggered this patch? If so, it would
be great to have this information in the changelog!

> I think the authors of the above code interpreted the read_lock as
> something that multiple threads can own disregarding the _read_ part.

Using RmW atomics should be fine for that; it's no worse than some of the
tricks pulled in RCU read context in the dentry cache (but then again, what
is? ;)

Will

Re: [PATCH] locking/qrwlock: Fix ordering in queued_write_lock_slowpath

[Peter Zijlstra]

On Thu, Apr 15, 2021 at 04:28:21PM +0100, Will Deacon wrote:
> On Thu, Apr 15, 2021 at 05:03:58PM +0200, Peter Zijlstra wrote:
> > @@ -73,9 +75,8 @@ void queued_write_lock_slowpath(struct qrwlock *lock)
> >  
> >  	/* When no more readers or writers, set the locked flag */
> >  	do {
> > -		atomic_cond_read_acquire(&lock->cnts, VAL == _QW_WAITING);
> > -	} while (atomic_cmpxchg_relaxed(&lock->cnts, _QW_WAITING,
> > -					_QW_LOCKED) != _QW_WAITING);
> > +		cnt = atomic_cond_read_acquire(&lock->cnts, VAL == _QW_WAITING);
> 
> I think the issue is that >here< a concurrent reader in interrupt context
> can take the lock and release it again, but we could speculate reads from
> the critical section up over the later release and up before the control
> dependency here...

OK, so that was totally not clear from the original changelog.

> > +	} while (!atomic_try_cmpxchg_relaxed(&lock->cnts, &cnt, _QW_LOCKED));
> 
> ... and then this cmpxchg() will succeed, so our speculated stale reads
> could be used.
> 
> *HOWEVER*
> 
> Speculating a read should be fine in the face of a concurrent _reader_,
> so for this to be an issue it implies that the reader is also doing some
> (atomic?) updates.

So we're having something like:

	CPU0				CPU1

	queue_write_lock_slowpath()
	  atomic_cond_read_acquire() == _QW_WAITING

					queued_read_lock_slowpath()
					  atomic_cond_read_acquire()
					  return;
   ,--> (before X's store)
   |					X = y;
   |
   |					queued_read_unlock()
   |					  (void)atomic_sub_return_release()
   |
   |	  atomic_cmpxchg_relaxed(.old = _QW_WAITING)
   |
    `--	r = X;


Which as Will said is a cmpxchg ABA, however for it to be ABA, we have
to observe that unlock-store, and won't we then also have to observe the
whole critical section?

Ah, the issue is yet another load inside our own (CPU0)'s critical
section. which isn't ordered against the cmpxchg_relaxed() and can be
issued before.

So yes, then making the cmpxchg an acquire, will force all our own loads
to happen later.

Re: [PATCH] locking/qrwlock: Fix ordering in queued_write_lock_slowpath

[Ali Saidi]

On Thu, 15 Apr 2021 16:02:29 +0100, Will Deacon wrote:
> On Thu, Apr 15, 2021 at 02:25:52PM +0000, Ali Saidi wrote:
> > While this code is executed with the wait_lock held, a reader can
> > acquire the lock without holding wait_lock.  The writer side loops
> > checking the value with the atomic_cond_read_acquire(), but only truly
> > acquires the lock when the compare-and-exchange is completed
> > successfully which isn’t ordered. The other atomic operations from this
> > point are release-ordered and thus reads after the lock acquisition can
> > be completed before the lock is truly acquired which violates the
> > guarantees the lock should be making.
> 
> I think it would be worth spelling this out with an example. The issue
> appears to be a concurrent reader in interrupt context taking and releasing
> the lock in the window where the writer has returned from the
> atomic_cond_read_acquire() but has not yet performed the cmpxchg(). Loads
> can be speculated during this time, but the A-B-A of the lock word
> from _QW_WAITING to (_QW_WAITING | _QR_BIAS) and back to _QW_WAITING allows
> the atomic_cmpxchg_relaxed() to succeed. Is that right?

You're right. What we're seeing is an A-B-A problem that can allow 
atomic_cond_read_acquire() to succeed and before the cmpxchg succeeds a reader
performs an A-B-A on the lock which allows the core to observe a read that
follows the cmpxchg ahead of the cmpxchg succeeding. 

We've seen a problem in epoll where the reader does a xchg while
holding the read lock, but the writer can see a value change out from under it. 

Writer                               | Reader 2
--------------------------------------------------------------------------------
ep_scan_ready_list()                 |
|- write_lock_irq()                  |
    |- queued_write_lock_slowpath()  |
      |- atomic_cond_read_acquire()  |
                                     | read_lock_irqsave(&ep->lock, flags);
                                     | chain_epi_lockless()
                                     |    epi->next = xchg(&ep->ovflist, epi);
                                     | read_unlock_irqrestore(&ep->lock, flags);
                                     |       
         atomic_cmpxchg_relaxed()    |
  READ_ONCE(ep->ovflist);    

> 
> With that in mind, it would probably be a good idea to eyeball the qspinlock
> slowpath as well, as that uses both atomic_cond_read_acquire() and
> atomic_try_cmpxchg_relaxed().

It seems plausible that the same thing could occur here in qspinlock:
          if ((val & _Q_TAIL_MASK) == tail) {
                  if (atomic_try_cmpxchg_relaxed(&lock->val, &val, _Q_LOCKED_VAL))
                          goto release; /* No contention */
          }

> 
> > Fixes: b519b56e378ee ("locking/qrwlock: Use atomic_cond_read_acquire() when spinning in qrwloc")

Ack, will fix. 

> Typo in the quoted subject ('qrwloc').
> 
> > Signed-off-by: Ali Saidi <alisaidi@amazon.com>
> > Cc: stable@vger.kernel.org
> > ---
> >  kernel/locking/qrwlock.c | 4 ++--
> >  1 file changed, 2 insertions(+), 2 deletions(-)
> > 
> > diff --git a/kernel/locking/qrwlock.c b/kernel/locking/qrwlock.c
> > index 4786dd271b45..10770f6ac4d9 100644
> > --- a/kernel/locking/qrwlock.c
> > +++ b/kernel/locking/qrwlock.c
> > @@ -73,8 +73,8 @@ void queued_write_lock_slowpath(struct qrwlock *lock)
> >  
> >  	/* When no more readers or writers, set the locked flag */
> >  	do {
> > -		atomic_cond_read_acquire(&lock->cnts, VAL == _QW_WAITING);
> > -	} while (atomic_cmpxchg_relaxed(&lock->cnts, _QW_WAITING,
> > +		atomic_cond_read_relaxed(&lock->cnts, VAL == _QW_WAITING);
> > +	} while (atomic_cmpxchg_acquire(&lock->cnts, _QW_WAITING,
> >  					_QW_LOCKED) != _QW_WAITING);
> 
> Patch looks good, so with an updated message:
> 
> Acked-by: Will Deacon <will@kernel.org>
> 
> Will

Re: [PATCH] locking/qrwlock: Fix ordering in queued_write_lock_slowpath

[Will Deacon]

On Thu, Apr 15, 2021 at 04:26:46PM +0000, Ali Saidi wrote:
> 
> On Thu, 15 Apr 2021 16:02:29 +0100, Will Deacon wrote:
> > On Thu, Apr 15, 2021 at 02:25:52PM +0000, Ali Saidi wrote:
> > > While this code is executed with the wait_lock held, a reader can
> > > acquire the lock without holding wait_lock.  The writer side loops
> > > checking the value with the atomic_cond_read_acquire(), but only truly
> > > acquires the lock when the compare-and-exchange is completed
> > > successfully which isn’t ordered. The other atomic operations from this
> > > point are release-ordered and thus reads after the lock acquisition can
> > > be completed before the lock is truly acquired which violates the
> > > guarantees the lock should be making.
> > 
> > I think it would be worth spelling this out with an example. The issue
> > appears to be a concurrent reader in interrupt context taking and releasing
> > the lock in the window where the writer has returned from the
> > atomic_cond_read_acquire() but has not yet performed the cmpxchg(). Loads
> > can be speculated during this time, but the A-B-A of the lock word
> > from _QW_WAITING to (_QW_WAITING | _QR_BIAS) and back to _QW_WAITING allows
> > the atomic_cmpxchg_relaxed() to succeed. Is that right?
> 
> You're right. What we're seeing is an A-B-A problem that can allow 
> atomic_cond_read_acquire() to succeed and before the cmpxchg succeeds a reader
> performs an A-B-A on the lock which allows the core to observe a read that
> follows the cmpxchg ahead of the cmpxchg succeeding. 
> 
> We've seen a problem in epoll where the reader does a xchg while
> holding the read lock, but the writer can see a value change out from under it. 
> 
> Writer                               | Reader 2
> --------------------------------------------------------------------------------
> ep_scan_ready_list()                 |
> |- write_lock_irq()                  |
>     |- queued_write_lock_slowpath()  |
>       |- atomic_cond_read_acquire()  |
>                                      | read_lock_irqsave(&ep->lock, flags);
>                                      | chain_epi_lockless()
>                                      |    epi->next = xchg(&ep->ovflist, epi);
>                                      | read_unlock_irqrestore(&ep->lock, flags);
>                                      |       
>          atomic_cmpxchg_relaxed()    |
>   READ_ONCE(ep->ovflist);    


Please stick this in the commit message, preferably annotated a bit like
Peter's example to show the READ_ONCE() being speculated.

> > With that in mind, it would probably be a good idea to eyeball the qspinlock
> > slowpath as well, as that uses both atomic_cond_read_acquire() and
> > atomic_try_cmpxchg_relaxed().
> 
> It seems plausible that the same thing could occur here in qspinlock:
>           if ((val & _Q_TAIL_MASK) == tail) {
>                   if (atomic_try_cmpxchg_relaxed(&lock->val, &val, _Q_LOCKED_VAL))
>                           goto release; /* No contention */
>           }

Just been thinking about this, but I don't see an issue here because
everybody is queuing the same way (i.e. we don't have a mechanism to jump
the queue like we do for qrwlock) and the tail portion of the lock word
isn't susceptible to ABA. That is, once we're at the head of the queue
and we've seen the lock become unlocked via atomic_cond_read_acquire(),
then we know we hold it.

So qspinlock looks fine to me, but I'd obviously value anybody else's
opinion on that.

Will

Re: [PATCH] locking/qrwlock: Fix ordering in queued_write_lock_slowpath

[Waiman Long]

On 4/15/21 12:45 PM, Will Deacon wrote:
>
>>> With that in mind, it would probably be a good idea to eyeball the qspinlock
>>> slowpath as well, as that uses both atomic_cond_read_acquire() and
>>> atomic_try_cmpxchg_relaxed().
>> It seems plausible that the same thing could occur here in qspinlock:
>>            if ((val & _Q_TAIL_MASK) == tail) {
>>                    if (atomic_try_cmpxchg_relaxed(&lock->val, &val, _Q_LOCKED_VAL))
>>                            goto release; /* No contention */
>>            }
> Just been thinking about this, but I don't see an issue here because
> everybody is queuing the same way (i.e. we don't have a mechanism to jump
> the queue like we do for qrwlock) and the tail portion of the lock word
> isn't susceptible to ABA. That is, once we're at the head of the queue
> and we've seen the lock become unlocked via atomic_cond_read_acquire(),
> then we know we hold it.
>
> So qspinlock looks fine to me, but I'd obviously value anybody else's
> opinion on that.

I agree with your assessment of qspinlock. I think qspinlock is fine.

Cheers,
Longman

Re: [PATCH] locking/qrwlock: Fix ordering in queued_write_lock_slowpath

[Steve Capper]

Hiya,

On 15/04/2021 17:45, Will Deacon wrote:
> On Thu, Apr 15, 2021 at 04:26:46PM +0000, Ali Saidi wrote:
>>
>> On Thu, 15 Apr 2021 16:02:29 +0100, Will Deacon wrote:
>>> On Thu, Apr 15, 2021 at 02:25:52PM +0000, Ali Saidi wrote:
>>>> While this code is executed with the wait_lock held, a reader can
>>>> acquire the lock without holding wait_lock.  The writer side loops
>>>> checking the value with the atomic_cond_read_acquire(), but only truly
>>>> acquires the lock when the compare-and-exchange is completed
>>>> successfully which isn’t ordered. The other atomic operations from this
>>>> point are release-ordered and thus reads after the lock acquisition can
>>>> be completed before the lock is truly acquired which violates the
>>>> guarantees the lock should be making.
>>>
>>> I think it would be worth spelling this out with an example. The issue
>>> appears to be a concurrent reader in interrupt context taking and releasing
>>> the lock in the window where the writer has returned from the
>>> atomic_cond_read_acquire() but has not yet performed the cmpxchg(). Loads
>>> can be speculated during this time, but the A-B-A of the lock word
>>> from _QW_WAITING to (_QW_WAITING | _QR_BIAS) and back to _QW_WAITING allows
>>> the atomic_cmpxchg_relaxed() to succeed. Is that right?
>>
>> You're right. What we're seeing is an A-B-A problem that can allow
>> atomic_cond_read_acquire() to succeed and before the cmpxchg succeeds a reader
>> performs an A-B-A on the lock which allows the core to observe a read that
>> follows the cmpxchg ahead of the cmpxchg succeeding.
>>
>> We've seen a problem in epoll where the reader does a xchg while
>> holding the read lock, but the writer can see a value change out from under it.
>>
>> Writer                               | Reader 2
>> --------------------------------------------------------------------------------
>> ep_scan_ready_list()                 |
>> |- write_lock_irq()                  |
>>      |- queued_write_lock_slowpath()  |
>>        |- atomic_cond_read_acquire()  |
>>                                       | read_lock_irqsave(&ep->lock, flags);
>>                                       | chain_epi_lockless()
>>                                       |    epi->next = xchg(&ep->ovflist, epi);
>>                                       | read_unlock_irqrestore(&ep->lock, flags);
>>                                       |
>>           atomic_cmpxchg_relaxed()    |
>>    READ_ONCE(ep->ovflist);
> 
> 
> Please stick this in the commit message, preferably annotated a bit like
> Peter's example to show the READ_ONCE() being speculated.
> 

I can confirm that this patch fixes a problem observed in
ep_scan_ready_list(.) whereby ovflist appeared to change when the write
lock was held.

So please feel free to add:
Tested-by: Steve Capper <steve.capper@arm.com>

Also, I have spent a decent chunk of time looking at the above issue and
went through qrwlock, so FWIW, please feel free to add:
Reviewed-by: Steve Capper <steve.capper@arm.com>

Cheers,
-- 
Steve