linux-kernel - Re: [RFC] Implement Batched (group) ticket 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]

Date:	Wed, 28 May 2014 15:19:49 -0700
From:	Linus Torvalds <torvalds@...ux-foundation.org>
To:	Rik van Riel <riel@...hat.com>
Cc:	Raghavendra K T <raghavendra.kt@...ux.vnet.ibm.com>,
	Thomas Gleixner <tglx@...utronix.de>,
	Ingo Molnar <mingo@...hat.com>, Peter Anvin <hpa@...or.com>,
	Konrad Rzeszutek Wilk <konrad.wilk@...cle.com>,
	Paolo Bonzini <pbonzini@...hat.com>,
	Gleb Natapov <gleb@...hat.com>,
	Peter Zijlstra <peterz@...radead.org>,
	Paul McKenney <paulmck@...ux.vnet.ibm.com>,
	Waiman Long <waiman.long@...com>,
	Dave Jones <davej@...hat.com>, Oleg Nesterov <oleg@...hat.com>,
	"the arch/x86 maintainers" <x86@...nel.org>,
	Jeremy Fitzhardinge <jeremy@...p.org>,
	Paul Gortmaker <paul.gortmaker@...driver.com>,
	Andi Kleen <ak@...ux.intel.com>,
	Jason Wang <jasowang@...hat.com>, fernando_b1@....ntt.co.jp,
	Linux Kernel Mailing List <linux-kernel@...r.kernel.org>,
	KVM list <kvm@...r.kernel.org>,
	virtualization <virtualization@...ts.linux-foundation.org>,
	xen-devel@...ts.xenproject.org,
	Marcelo Tosatti <mtosatti@...hat.com>,
	"Vinod, Chegu" <chegu_vinod@...com>
Subject: Re: [RFC] Implement Batched (group) ticket lock

On Wed, May 28, 2014 at 2:55 PM, Rik van Riel <riel@...hat.com> wrote:
>
> Or maybe cmpxchg is cheap once you already own the cache line
> exclusively?

A locked cmpxchg ends up being anything between ~15-50 cycles
depending on microarchitecture if things are already exclusively in
the cache (with the P4 being an outlier, and all locked instructions
tend to take ~100+ cycles, but I can't say I can really find it in
myself to even care about netburst any more).

The most noticeable downside we've seen has been when we've used
"read-op-cmpxchg" as a _replacement_ for something like "lock [x]add",
when that "read+cmpxchg" has caused two cacheline ops (cacheline first
loaded shared by the read, then exclusive by the cmpxchg). That's bad.

But if preceded by a write (or, in this case, an xadd), that doesn't
happen. Still, those roughly 15-50 cycles can certainly be noticeable
(especially at the high end), but you need to have some load that
doesn't bounce the lock, and largely fit in the caches to see it. And
you probably want to test one of the older CPU's, I think Haswell is
the lower end (ie in the ~20 cycle range).

If somebody has a P4 still, that's likely the worst case by far.

              Linus
--
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/