linux-kernel - Re: [PATCH V2 0/6][RFC] futex: FUTEX_LOCK with optional adaptive spinning

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:	Tue, 06 Apr 2010 16:30:35 +0300
From:	Avi Kivity <avi@...hat.com>
To:	Darren Hart <dvhltc@...ibm.com>
CC:	linux-kernel@...r.kernel.org, Thomas Gleixner <tglx@...utronix.de>,
	Peter Zijlstra <peterz@...radead.org>,
	Ingo Molnar <mingo@...e.hu>,
	Eric Dumazet <eric.dumazet@...il.com>,
	"Peter W. Morreale" <pmorreale@...ell.com>,
	Rik van Riel <riel@...hat.com>,
	Steven Rostedt <rostedt@...dmis.org>,
	Gregory Haskins <ghaskins@...ell.com>,
	Sven-Thorsten Dietrich <sdietrich@...ell.com>,
	Chris Mason <chris.mason@...cle.com>,
	John Cooper <john.cooper@...rd-harmonic.com>,
	Chris Wright <chrisw@...s-sol.org>
Subject: Re: [PATCH V2 0/6][RFC] futex: FUTEX_LOCK with optional adaptive
 spinning

On 04/06/2010 02:15 AM, Darren Hart wrote:
> Avi Kivity wrote:
>
>>>> An interesting (but perhaps difficult to achieve) optimization 
>>>> would be to spin in userspace.
>>>
>>> I couldn't think of a lightweight way to determine when the owner 
>>> has been scheduled out in userspace. Kernel assistance is required. 
>>> You could do this on the schedule() side of things, but I figured 
>>> I'd get some strong pushback if I tried to add a hook into 
>>> descheduling that flipped a bit in the futex value stating the owner 
>>> was about to deschedule(). Still, that might be something to explore.
>>
>> In the futex value it's hopeless (since a thread can hold many locks), 
>
> It can, but there is a futex value per lock. If the task_struct had a 
> list of held futex locks (as it does for pi futex locks) the 
> deschedule() path could walk that and mark the FUTEX_OWNER_SLEEPING bit.
>

You don't want the context switch path to walk a list whose length is 
user controlled.

>> but I don't think it's unreasonable to set a bit in the thread local 
>> storage area.  The futex format would then need to be extended to 
>> contain a pointer to this bit.
>
> This appears to be 1 bit per task instead of 1 bit per lock. 

Yes.  O(1) on context switch instead of O(n).

> Also, the value is thread-specific... so how would a potential waiter 
> be able to determine if the owner of a particular lock was running or 
> not with this method?  ... maybe I'm missing some core bit about 
> TLS... are you talking about pthread_key_create() and 
> pthread_getspecific() ?

The lock would need to contain a pointer to the owning task.  Could be 
set with cmpxchg{8,16}b on x86.

-- 
error compiling committee.c: too many arguments to function

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