linux-kernel - Re: [RFC PATCH v2 3/5] futex: Throughput-optimized (TO) futexes

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:   Thu, 22 Sep 2016 16:08:38 -0400
From:   Waiman Long <waiman.long@....com>
To:     Davidlohr Bueso <dave@...olabs.net>
CC:     Thomas Gleixner <tglx@...utronix.de>,
        Peter Zijlstra <peterz@...radead.org>,
        Mike Galbraith <umgwanakikbuti@...il.com>,
        Ingo Molnar <mingo@...nel.org>,
        Jonathan Corbet <corbet@....net>,
        <linux-kernel@...r.kernel.org>, <linux-doc@...r.kernel.org>,
        Jason Low <jason.low2@....com>,
        Scott J Norton <scott.norton@....com>,
        Douglas Hatch <doug.hatch@....com>
Subject: Re: [RFC PATCH v2 3/5] futex: Throughput-optimized (TO) futexes

On 09/22/2016 11:11 AM, Davidlohr Bueso wrote:
> On Thu, 22 Sep 2016, Thomas Gleixner wrote:
>
>> On Thu, 22 Sep 2016, Davidlohr Bueso wrote:
>>> On Thu, 22 Sep 2016, Thomas Gleixner wrote:
>>> > Also what's the reason that we can't do probabilistic spinning for
>>> > FUTEX_WAIT and have to add yet another specialized variant of 
>>> futexes?
>>>
>>> Where would this leave the respective FUTEX_WAKE? A nop? Probably 
>>> have to
>>> differentiate the fact that the queue was empty, but there was a 
>>> spinning,
>>> instead of straightforward returning 0.
>>
>> Sorry, but I really can't parse this answer.
>>
>> Can you folks please communicate with proper and coherent explanations
>> instead of throwing a few gnawed off bones in my direction?
>
> I actually think that FUTEX_WAIT is the better/nicer approach. But my 
> immediate
> question above was how to handle the FUTEX_WAKE counter-part. If we 
> want to
> maintain current FIFO ordering for wakeups, now with WAIT spinners 
> this will
> create lock stealing scenarios (including if we even guard against 
> starvation).
> Or we could reduce the scope of spinners, due to the restrictions, 
> similar to
> the top-waiter only being able to spin for rtmutexes. This of course 
> will hurt
> the effectiveness of spinning in FUTEX_WAIT in the first place.

Actually, there can be a lot of lock stealing going on with the 
wait-wake futexes. If the critical section is short enough, many of the 
lock waiters can be waiting in the hash bucket spinlock queue and not 
sleeping yet while the futex value changes. As a result, they will exit 
the futex syscall and back to user space with EAGAIN where one of them 
may get the lock. So we can't assume that they will get the lock in the 
FIFO order anyway.

> Another immediate thought was situations where we spinner(s) and the 
> wait queue is
> empty, the WAKE should also have to acknowledge that situation, as 
> just returning 0
> would indicate that there are actually no waiters on the futex.

I would say that adding optimistic spinning to FUTEX_WAIT will be a 
major change and I don't think it will be less complex than adding a new 
futex type like the TO futexes while introducing a fair amount of risk 
of breaking existing applications.

Cheers,
Longman