linux-kernel - Re: [PATCH 2/2] mutex: Apply adaptive spinning on mutex

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]

Message-ID: <AANLkTimO3b3D+SofYFLyh8Txk+e4Ke4ToKrBiatdFghr@mail.gmail.com>
Date:	Fri, 25 Mar 2011 14:13:14 +0300
From:	Andrey Kuzmin <andrey.v.kuzmin@...il.com>
To:	Steven Rostedt <rostedt@...dmis.org>
Cc:	Tejun Heo <tj@...nel.org>, Peter Zijlstra <peterz@...radead.org>,
	Ingo Molnar <mingo@...hat.com>,
	Linus Torvalds <torvalds@...ux-foundation.org>,
	Andrew Morton <akpm@...ux-foundation.org>,
	Chris Mason <chris.mason@...cle.com>,
	linux-kernel@...r.kernel.org, linux-btrfs@...r.kernel.org
Subject: Re: [PATCH 2/2] mutex: Apply adaptive spinning on mutex_trylock()

On Fri, Mar 25, 2011 at 6:39 AM, Steven Rostedt <rostedt@...dmis.org> 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@...nel.org>
>
> 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@...r.kernel.org
> 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@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/