Re: [PATCH 2/2] mutex: Apply adaptive spinning on mutex_trylock()

From: Andrey Kuzmin
Date: Fri Mar 25 2011 - 07:13:42 EST


On Fri, Mar 25, 2011 at 6:39 AM, Steven Rostedt <rostedt@xxxxxxxxxxx> wrote:
> On Thu, Mar 24, 2011 at 10:41:51AM +0100, Tejun Heo wrote:
>> Adaptive owner spinning used to be applied only to mutex_lock(). ÂThis
>> patch applies it also to mutex_trylock().
>>
>> btrfs has developed custom locking to avoid excessive context switches
>> in its btree implementation. ÂGenerally, doing away with the custom
>> implementation and just using the mutex shows better behavior;
>> however, there's an interesting distinction in the custom implemention
>> of trylock. ÂIt distinguishes between simple trylock and tryspin,
>> where the former just tries once and then fail while the latter does
>> some spinning before giving up.
>>
>> Currently, mutex_trylock() doesn't use adaptive spinning. ÂIt tries
>> just once. ÂI got curious whether using adaptive spinning on
>> mutex_trylock() would be beneficial and it seems so, for btrfs anyway.
>>
>> The following results are from "dbench 50" run on an opteron two
>> socket eight core machine with 4GiB of memory and an OCZ vertex SSD.
>> During the run, disk stays mostly idle and all CPUs are fully occupied
>> and the difference in locking performance becomes quite visible.
>>
>> SIMPLE is with the locking simplification patch[1] applied. Âi.e. it
>> basically just uses mutex. ÂSPIN is with this patch applied on top -
>> mutex_trylock() uses adaptive spinning.
>>
>> Â Â Â Â USER Â SYSTEM Â SIRQ Â ÂCXTSW ÂTHROUGHPUT
>> ÂSIMPLE 61107 Â354977 Â Â217 Â8099529 Â845.100 MB/sec
>> ÂSPIN Â 63140 Â364888 Â Â214 Â6840527 Â879.077 MB/sec
>>
>> On various runs, the adaptive spinning trylock consistently posts
>> higher throughput. ÂThe amount of difference varies but it outperforms
>> consistently.
>>
>> In general, using adaptive spinning on trylock makes sense as trylock
>> failure usually leads to costly unlock-relock sequence.
>>
>> [1] http://article.gmane.org/gmane.comp.file-systems.btrfs/9658
>>
>> Signed-off-by: Tejun Heo <tj@xxxxxxxxxx>
>
> I'm curious about the effects that this has on those places that do:
>
> again:
> Â Â Â Âmutex_lock(A);
> Â Â Â Âif (mutex_trylock(B)) {
> Â Â Â Â Â Â Â Âmutex_unlock(A);
> Â Â Â Â Â Â Â Âgoto again;
>
>
> Where the normal locking order is:
> ÂB -> A
>
> If another location does:
>
> Â Â Â Âmutex_lock(B);
> Â Â Â Â[...]
> Â Â Â Âmutex_lock(A);
>
> But another process has A already, and is running, it may spin waiting
> for A as A's owner is still running.
>
> But now, mutex_trylock(B) becomes a spinner too, and since the B's owner
> is running (spinning on A) it will spin as well waiting for A's owner to
> release it. Unfortunately, A's owner is also spinning waiting for B to
> release it.
>
> If both A and B's owners are real time tasks, then boom! deadlock.

Turning try_lock into indefinitely spinning one breaks its semantics,
so deadlock is to be expected. But what's wrong in this scenario if
try_lock spins a bit before giving up?

Regards,
Andrey

>
> -- Steve
>
> --
> To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in
> the body of a message to majordomo@xxxxxxxxxxxxxxx
> More majordomo info at Âhttp://vger.kernel.org/majordomo-info.html
>
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/