futex: FUTEX_LOCK with optional adaptive spinning
in [Kernel]
|
From: Avi Kivity on 6 Apr 2010 09:40 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(a)vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
From: Peter Zijlstra on 6 Apr 2010 09:40 On Tue, 2010-04-06 at 16:28 +0300, Avi Kivity wrote: > > Yes, but that's the best case for spinning. You could simply use a > userspace spinlock in this case. Userspace spinlocks are evil.. they should _never_ be used. -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo(a)vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
From: Alan Cox on 6 Apr 2010 09:50 On Tue, 06 Apr 2010 15:35:31 +0200 Peter Zijlstra <peterz(a)infradead.org> wrote: > On Tue, 2010-04-06 at 16:28 +0300, Avi Kivity wrote: > > > > Yes, but that's the best case for spinning. You could simply use a > > userspace spinlock in this case. > > Userspace spinlocks are evil.. they should _never_ be used. Thats a gross and inaccurate simplification. For the case Avi is talking about spinning in userspace makes sense in a lot of environments. Once you've got one thread pinned per cpu (or gang scheduling >-) ) there are various environments where it makes complete and utter sense. -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo(a)vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
From: Avi Kivity on 6 Apr 2010 09:50 On 04/06/2010 04:35 PM, Peter Zijlstra wrote: > On Tue, 2010-04-06 at 16:28 +0300, Avi Kivity wrote: > >> Yes, but that's the best case for spinning. You could simply use a >> userspace spinlock in this case. >> > Userspace spinlocks are evil.. they should _never_ be used. > But in this case they're fastest. If we don't provide a non-evil alternative, people will use them. -- 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(a)vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
From: Peter Zijlstra on 6 Apr 2010 10:10
On Tue, 2010-04-06 at 16:41 +0300, Avi Kivity wrote: > On 04/06/2010 04:35 PM, Peter Zijlstra wrote: > > On Tue, 2010-04-06 at 16:28 +0300, Avi Kivity wrote: > > > >> Yes, but that's the best case for spinning. You could simply use a > >> userspace spinlock in this case. > >> > > Userspace spinlocks are evil.. they should _never_ be used. > > > > But in this case they're fastest. If we don't provide a non-evil > alternative, people will use them. > That's what FUTEX_LOCK is about. -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo(a)vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/ |