linux-kernel - Re: [RFC PATCH 1/6] kernel: implement queue spinlock API

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:	Thu, 7 Feb 2013 16:35:59 -0800
From:	Michel Lespinasse <walken@...gle.com>
To:	paulmck@...ux.vnet.ibm.com
Cc:	Rik van Riel <riel@...hat.com>, Ingo Molnar <mingo@...hat.com>,
	David Howells <dhowells@...hat.com>,
	Thomas Gleixner <tglx@...utronix.de>,
	Eric Dumazet <edumazet@...gle.com>,
	"Eric W. Biederman" <ebiederm@...ssion.com>,
	Manfred Spraul <manfred@...orfullife.com>,
	linux-kernel@...r.kernel.org, john.stultz@...aro.org
Subject: Re: [RFC PATCH 1/6] kernel: implement queue spinlock API

On Thu, Feb 7, 2013 at 2:34 PM, Paul E. McKenney
<paulmck@...ux.vnet.ibm.com> wrote:
> On Tue, Jan 22, 2013 at 03:13:30PM -0800, Michel Lespinasse wrote:
>> Introduce queue spinlocks, to be used in situations where it is desired
>> to have good throughput even under the occasional high-contention situation.
>>
>> This initial implementation is based on the classic MCS spinlock,
>> because I think this represents the nicest API we can hope for in a
>> fast queue spinlock algorithm. The MCS spinlock has known limitations
>> in that it performs very well under high contention, but is not as
>> good as the ticket spinlock under low contention. I will address these
>> limitations in a later patch, which will propose an alternative,
>> higher performance implementation using (mostly) the same API.

While we're talking about MCS spinlocks, I should point out a
potential issue I found about my 'faster queue spinlock' proposed MCS
alternative. It is nice in that it avoids an atomic operation in the
unlock path; however each unlocked lock must have a 'token' allocated
and this token is accessed by the lock function. The issue with this
is that if two threads don't actually block on each other, but they
both access a lock that bounces between them, now the token will have
to bounce between these threads as well, which is going to be more
expansive than the atomic operation that was saved.

-- 
Michel "Walken" Lespinasse
A program is never fully debugged until the last user dies.
--
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/