linux-kernel - Re: [PATCH 2/2] locking/qspinlock: Limit # of spins in _Q_PENDING

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]

Date:   Wed, 11 Apr 2018 16:22:12 +0100
From:   Catalin Marinas <catalin.marinas@....com>
To:     Waiman Long <longman@...hat.com>
Cc:     Ingo Molnar <mingo@...hat.com>,
        Peter Zijlstra <peterz@...radead.org>,
        linux-kernel@...r.kernel.org, Will Deacon <will.deacon@....com>,
        boqun.feng@...il.com,
        "Paul E. McKenney" <paulmck@...ux.vnet.ibm.com>
Subject: Re: [PATCH 2/2] locking/qspinlock: Limit # of spins in
 _Q_PENDING_VAL wait loop

Hi Waiman,

On Mon, Apr 09, 2018 at 02:08:52PM -0400, Waiman Long wrote:
> @@ -311,13 +320,19 @@ void queued_spin_lock_slowpath(struct qspinlock *lock, u32 val)
>  		return;
>  
>  	/*
> -	 * wait for in-progress pending->locked hand-overs
> +	 * wait for in-progress pending->locked hand-overs with a
> +	 * limited number of spins.
>  	 *
>  	 * 0,1,0 -> 0,0,1
>  	 */
>  	if (val == _Q_PENDING_VAL) {
> -		while ((val = atomic_read(&lock->val)) == _Q_PENDING_VAL)
> +		int cnt = _Q_PENDING_LOOP;
> +
> +		while ((val = atomic_read(&lock->val)) == _Q_PENDING_VAL) {
> +			if (!--cnt)
> +				goto queue;
>  			cpu_relax();
> +		}
>  	}

In my model, the pathological case is not this loop but the following
one (trylock || pending):

P0:					P1:
queued_spin_lock() fails		queued_spin_lock() succeeds
queued_spin_lock_slowpath()
	val == _Q_LOCKED_VAL
	new = _Q_LOCKED_VAL |
		_Q_PENDING_VAL
					queued_spin_unlock()
						lock->val == 0
	cmpxchg(&lock->val, val, new)
		fails
	val = old (0)
	repeat for (;;) loop:
	new = _Q_LOCKED_VAL
					queued_spin_lock() succeeds
						lock->val == _Q_LOCKED_VAL
	cmpxchg(&lock->val, val, new)
		fails
	val = old (_Q_LOCKED_VAL)
	repeat for (;;) loop:

	... and we are back to the P0 state above when it first entered
	the loop, hence no progress. P1 never enters slowpath.

I think the pending bounded loop in your patch is needed for a three CPU
scenario where two of them can hand over _Q_PENDING_VAL while the third
doesn't make progress. I tried modeling 3 CPUs to see but the tool still
hits the for (;;) loop case rather than pending wait loop. Maybe a
combination of Will's changes to the (trylock || pending) loop with your
bounded pending hand-over?

-- 
Catalin