linux-kernel - Re: [PATCH 01/11] qspinlock: A simple generic 4-byte queue spinlock

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: <20140623161200.GG19860@laptop.programming.kicks-ass.net>
Date:	Mon, 23 Jun 2014 18:12:00 +0200
From:	Peter Zijlstra <peterz@...radead.org>
To:	Konrad Rzeszutek Wilk <konrad.wilk@...cle.com>
Cc:	Waiman.Long@...com, tglx@...utronix.de, mingo@...nel.org,
	linux-arch@...r.kernel.org, linux-kernel@...r.kernel.org,
	virtualization@...ts.linux-foundation.org,
	xen-devel@...ts.xenproject.org, kvm@...r.kernel.org,
	paolo.bonzini@...il.com, boris.ostrovsky@...cle.com,
	paulmck@...ux.vnet.ibm.com, riel@...hat.com,
	torvalds@...ux-foundation.org, raghavendra.kt@...ux.vnet.ibm.com,
	david.vrabel@...rix.com, oleg@...hat.com, gleb@...hat.com,
	scott.norton@...com, chegu_vinod@...com
Subject: Re: [PATCH 01/11] qspinlock: A simple generic 4-byte queue spinlock

On Tue, Jun 17, 2014 at 04:03:29PM -0400, Konrad Rzeszutek Wilk wrote:
> > > +			new = tail | (val & _Q_LOCKED_MASK);
> > > +
> > > +		old = atomic_cmpxchg(&lock->val, val, new);
> > > +		if (old == val)
> > > +			break;
> > > +
> > > +		val = old;
> > > +	}
> > > +
> > > +	/*
> > > +	 * we won the trylock; forget about queueing.
> > > +	 */
> > > +	if (new == _Q_LOCKED_VAL)
> > > +		goto release;
> > > +
> > > +	/*
> > > +	 * if there was a previous node; link it and wait.
> > > +	 */
> > > +	if (old & ~_Q_LOCKED_MASK) {
> > > +		prev = decode_tail(old);
> > > +		ACCESS_ONCE(prev->next) = node;
> > > +
> > > +		arch_mcs_spin_lock_contended(&node->locked);
> 
> Could you add a comment here:
> 
> /* We are spinning forever until the previous node updates locked - which
> it does once the it has updated lock->val with our tail number. */

That's incorrect -- or at least, I understand that to be incorrect. The
previous node will not have changed the tail to point to us. You always
change to tail to point to yourself, seeing how you add yourself to the
tail.

Is the existing comment any better if I s/wait./wait for it to release
us./ ?

> > > +	/*
> > > +	 * claim the lock:
> > > +	 *
> > > +	 * n,0 -> 0,1 : lock, uncontended
> > > +	 * *,0 -> *,1 : lock, contended
> > > +	 */
> > > +	for (;;) {
> > > +		new = _Q_LOCKED_VAL;
> > > +		if (val != tail)
> > > +			new |= val;
> > 
> ..snip..
> > 
> > Could you help a bit in explaining it in English please?
> 
> After looking at the assembler code I finally figured out how
> we can get here. And the 'contended' part threw me off. Somehow
> I imagined there are two more more CPUs stampeding here and 
> trying to update the lock->val. But in reality the other CPUs
> are stuck in the arch_mcs_spin_lock_contended spinning on their
> local value.

Well, the lock as a whole is contended (there's >1 waiters), and the
point of MCS style locks it to make sure they're not actually pounding
on the same cacheline. So the whole thing is consistent.

> Perhaps you could add this comment.
> 
> /* Once queue_spin_unlock is called (which _subtracts_ _Q_LOCKED_VAL from
> the lock->val and still preserving the tail data), the winner gets to
> claim the ticket. 

There's no tickets :/

> Since we still need the other CPUs to continue and
> preserve the strict ordering in which they setup node->next, we:
>  1) update lock->val to the tail value (so tail CPU and its index) with
>     _Q_LOCKED_VAL.

We don't, we preserve the tail value, unless we're the tail, in which
case we clear the tail.

>  2). Once we are done, we poke the other CPU (the one that linked to
>     us) by writting to node->locked (below) so they can make progress and
>     loop on lock->val changing from _Q_LOCKED_MASK to zero).

_If_ there was another cpu, ie. the tail didn't point to us.

---

I don't do well with natural language comments like that; they tend to
confuse me more than anything.

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/