linux-kernel - Re: [PATCH 13/14] x86/ticketlock: add slowpath logic

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, 19 Jan 2011 10:31:06 -0800
From:	Jeremy Fitzhardinge <jeremy@...p.org>
To:	vatsa@...ux.vnet.ibm.com
CC:	Peter Zijlstra <peterz@...radead.org>,
	Linux Kernel Mailing List <linux-kernel@...r.kernel.org>,
	Nick Piggin <npiggin@...nel.dk>,
	Mathieu Desnoyers <mathieu.desnoyers@...ymtl.ca>,
	Américo Wang <xiyou.wangcong@...il.com>,
	Eric Dumazet <dada1@...mosbay.com>,
	Jan Beulich <JBeulich@...ell.com>, Avi Kivity <avi@...hat.com>,
	Xen-devel <xen-devel@...ts.xensource.com>,
	"H. Peter Anvin" <hpa@...or.com>,
	Linux Virtualization <virtualization@...ts.linux-foundation.org>,
	Jeremy Fitzhardinge <jeremy.fitzhardinge@...rix.com>,
	suzuki@...ibm.com
Subject: Re: [PATCH 13/14] x86/ticketlock: add slowpath logic

On 01/17/2011 07:22 AM, Srivatsa Vaddagiri wrote:
> On Tue, Nov 16, 2010 at 01:08:44PM -0800, Jeremy Fitzhardinge wrote:
>> From: Jeremy Fitzhardinge <jeremy.fitzhardinge@...rix.com>
>>
>> Maintain a flag in both LSBs of the ticket lock which indicates whether
>> anyone is in the lock slowpath and may need kicking when the current
>> holder unlocks.  The flags are set when the first locker enters
>> the slowpath, and cleared when unlocking to an empty queue.
>>
>> In the specific implementation of lock_spinning(), make sure to set
>> the slowpath flags on the lock just before blocking.  We must do
>> this before the last-chance pickup test to prevent a deadlock
>> with the unlocker:
>>
>> Unlocker			Locker
>> 				test for lock pickup
>> 					-> fail
>> test slowpath + unlock
>> 	-> false
>> 				set slowpath flags
>> 				block
>>
>> Whereas this works in any ordering:
>>
>> Unlocker			Locker
>> 				set slowpath flags
>> 				test for lock pickup
>> 					-> fail
>> 				block
>> test slowpath + unlock
>> 	-> true, kick
> I think this is still racy ..
>
> Unlocker				Locker
>
> 				
> test slowpath
> 	-> false
> 		
> 				set slowpath flag
> 				test for lock pickup
> 					-> fail
> 				block
>
>
> unlock
>
> unlock needs to happen first before testing slowpath? I have made that change
> for my KVM guest and it seems to be working well with that change .. Will
> cleanup and post my patches shortly

I think you're probably right; when I last tested this code, it was
hanging in at about the rate this kind of race would cause.  And in my
previous analysis of similar schemes (the current pv spinlock code), it
was always correct to do the "slowpath" test after doing do the unlock.

*But* I haven't yet had the chance to specifically go through and
analyse your patch in detail to make sure there's nothing else going on,
so take this as provisional.

How much testing have you given it?

Thanks,
    J
--
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/