linux-kernel - Re: [PATCH v3 1/2] qspinlock: Introducing a 4-byte queue spinlock implementation

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] [day] [month] [year] [list]

Message-ID: <20140207181737.GS4250@linux.vnet.ibm.com>
Date:	Fri, 7 Feb 2014 10:17:37 -0800
From:	"Paul E. McKenney" <paulmck@...ux.vnet.ibm.com>
To:	Waiman Long <waiman.long@...com>
Cc:	Peter Zijlstra <peterz@...radead.org>,
	Thomas Gleixner <tglx@...utronix.de>,
	Ingo Molnar <mingo@...hat.com>,
	"H. Peter Anvin" <hpa@...or.com>, Arnd Bergmann <arnd@...db.de>,
	linux-arch@...r.kernel.org, x86@...nel.org,
	linux-kernel@...r.kernel.org, Steven Rostedt <rostedt@...dmis.org>,
	Andrew Morton <akpm@...ux-foundation.org>,
	Michel Lespinasse <walken@...gle.com>,
	Andi Kleen <andi@...stfloor.org>,
	Rik van Riel <riel@...hat.com>,
	Linus Torvalds <torvalds@...ux-foundation.org>,
	Raghavendra K T <raghavendra.kt@...ux.vnet.ibm.com>,
	George Spelvin <linux@...izon.com>,
	Tim Chen <tim.c.chen@...ux.intel.com>,
	Daniel J Blueman <daniel@...ascale.com>,
	Alexander Fyodorov <halcy@...dex.ru>,
	Aswin Chandramouleeswaran <aswin@...com>,
	Scott J Norton <scott.norton@...com>,
	Thavatchai Makphaibulchoke <thavatchai.makpahibulchoke@...com>
Subject: Re: [PATCH v3 1/2] qspinlock: Introducing a 4-byte queue spinlock
 implementation

On Wed, Feb 05, 2014 at 10:10:34PM -0500, Waiman Long wrote:
> On 02/03/2014 06:40 AM, Peter Zijlstra wrote:
> >On Fri, Jan 31, 2014 at 02:24:33PM -0500, Waiman Long wrote:
> >>Light contention is the only case where the qspinlock may not perform as
> >>good as the ticket spinlock. I know this is the most common case. However, I
> >>would argue that the slowdown, if any, will not be really noticeable. This
> >>is what I will try to find out.
> >Please also explain why things are slower/faster. Thomas tried to get
> >you to do so a few months back, but you kept deflecting.
> 
> It is not easy to have a test case to test light contention. I am
> trying to create custom test case to get that data.

Here are some ways of doing that:

1.	Provide (say) a thousand locks for each thread, so that you
	have all of these locks in one big array of locks.  Have each
	thread loop, where each pass through the loop acquires
	and releases a randomly selected lock.	Then measure the
	acquisition/release throughput.

2.	As #1 above, but vary the number of locks per thread in order to
	vary the level of contention in a controlled manner.  Note that
	the cache-miss probability is (N-1)/N, where where N is the
	number of threads, at least assuming each thread gets its own CPU.

3.	Provide each thread with its own lock and have each thread
	loop, where each pass through the loop acquires and releases
	the thread's lock.  This eliminates both contention and
	cache misses.

4.	As #1 above, but randomly acquire some other thread's lock with
	controlled probability to introduce controlled levels of both
	contention and cache misses.

5.	As #4 above, but provide each thread with multiple locks
	randomly selected to allow cache miss rate to be increased
	independently of contention.

All approaches require extremely efficient random-number generators,
for example, independent per-thread generators.

							Thanx, Paul

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