linux-kernel - Re: [PATCH] locking/qrwlock: Fix ordering in queued_write_lock

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <20210415164525.GC26594@willie-the-truck>
Date:   Thu, 15 Apr 2021 17:45:25 +0100
From:   Will Deacon <will@...nel.org>
To:     Ali Saidi <alisaidi@...zon.com>
Cc:     benh@...nel.crashing.org, boqun.feng@...il.com,
        catalin.marinas@....com, linux-kernel@...r.kernel.org,
        longman@...hat.com, mingo@...hat.com, peterz@...radead.org,
        stable@...r.kernel.org, steve.capper@....com
Subject: Re: [PATCH] locking/qrwlock: Fix ordering in
 queued_write_lock_slowpath

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