linux-kernel - Re: [RFC][PATCH 3/3] locking/qspinlock: Optimize for x86

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: Windows password security audit tool. GUI, reports in PDF.

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

Message-ID: <20181002123152.GA10055@andrea>
Date:   Tue, 2 Oct 2018 14:31:52 +0200
From:   Andrea Parri <andrea.parri@...rulasolutions.com>
To:     Will Deacon <will.deacon@....com>
Cc:     Peter Zijlstra <peterz@...radead.org>, mingo@...nel.org,
        linux-kernel@...r.kernel.org, longman@...hat.com,
        tglx@...utronix.de
Subject: Re: [RFC][PATCH 3/3] locking/qspinlock: Optimize for x86

> consider this scenario with your patch:
> 
> 1. CPU0 sees a locked val, and is about to do your xchg_relaxed() to set
>    pending.
> 
> 2. CPU1 comes in and sets pending, spins on locked
> 
> 3. CPU2 sees a pending and locked val, and is about to enter the head of
>    the waitqueue (i.e. it's right before xchg_tail()).
> 
> 4. The locked holder unlock()s, CPU1 takes the lock() and then unlock()s
>    it, so pending and locked are now 0.
> 
> 5. CPU0 sets pending and reads back zeroes for the other fields
> 
> 6. CPU0 clears pending and sets locked -- it now has the lock
> 
> 7. CPU2 updates tail, sees it's at the head of the waitqueue and spins
>    for locked and pending to go clear. However, it reads a stale value
>    from step (4) and attempts the atomic_try_cmpxchg() to take the lock.
> 
> 8. CPU2 will fail the cmpxchg(), but then go ahead and set locked. At this
>    point we're hosed, because both CPU2 and CPU0 have the lock.

Thanks for pointing this out.   I am wondering: can't we have a similar
scenario with the current code (i.e., w/o these patches): what prevents
the scenario reported below, following Peter's diagram, from happening?

  Andrea


  CPU0		CPU1		CPU2		CPU3

0)						lock
						  trylock -> (0,0,1)
1)lock
    trylock /* fail */

2)		lock
		  trylock /* fail */
		  fetch_or_acquire -> (0,1,1)
		  wait-locked

3)				lock
				  trylock /* fail */
				  goto queue

4)						unlock -> (0,1,0)
		  clr_pnd_set_lck -> (0,0,1)
		  unlock -> (0,0,0)

5)  fetch_or_acquire -> (0,1,0)
6)  clr_pnd_set_lck -> (0,0,1)
7)				  xchg_tail -> (n,0,1)
				  load_acquire <- (n,0,0) (from-4)
8)				  cmpxchg /* fail */
				  set_locked()