[RFC] pthread support for FUTEX_WAIT_MULTIPLE

Hello,

I started putting together a patch to expose the new Linux futex 
functionality that recently got proposed for upstream inclusion. [1]

I pushed the patch to a repository [2] and am also including it in this 
email for early comments and feedback.

Since I'm so unfamiliar with the generally accepted practice, I've held 
on finishing it until I could get some feedback on a variety of points 
I'm unsure about.

The gist of it is that it adds a new function, 
pthread_mutex_timedlock_any(), that can take a list of mutexes. It 
returns when one of the mutex has been locked (and tells you which one), 
or if the timeout is met. We would use this to reduce unnecessary 
wakeups and spinning in our thread pool synchronization code, compared 
to the current eventfd hack we rely on.

All mutexes passed to the list need to have matching types/kinds, as the 
kernel interface can only accept one PRIVATE flag for the whole operation.

Here are a grab bag of my questions, please bear with me:

  - I assume whichever name it might end up as should end with _np? Is 
there any specific process to follow for this sort of non-standard 
inclusion, other than just writing the code and documentation?

  - What is the standard way for an application to discover whether it 
can use an entrypoint dependent on a certain Linux kernel version? With 
our proposed use, we'd be fine running the function once at startup to 
pick which path to chose, eg. pthread_mutex_lock_any( NULL, 0, NULL, 
NULL ). If it returns 0, we'd enable the new path, otherwise we'd fall 
back to eventfd(). I have a TODO in the code where we could do that, but 
it's probably not the right way to do things.

  - I assume the way I'm exposing it as a 2.2.5-versioned symbol for 
local testing is wrong; what is the right way to do this?

  - I was planning on implementing the various different mutex types 
with branches, and possibly try to have a couple of callsites to a 
version that takes flags and rely on compiler inlining possibly doing 
the right thing. I see other implementations of similar functions opt 
for much more explicit inlining based on the mutex type. Would a version 
with branches be acceptable initially? We could further work on 
inlining/tuning if we found hotspots in the future.

  - In my tree I have a placeholder test application that should be 
replaced by a new mutex test. However, it would also be a good idea to 
leverage other mutex tests to test this new thing, since it's a superset 
of many other mutex calls. Could we make the normal mutex test suite run 
a second time, with a macro wrapping the normal pthread_lock with this 
implementation instead?

Thanks,

  - Pierre-Loup

[1] https://lkml.org/lkml/2019/7/30/1399

[2] 
https://github.com/Plagman/glibc/commit/3b01145fa25987f2f93e7eda7f3e7d0f2f77b290

 From 3b01145fa25987f2f93e7eda7f3e7d0f2f77b290 Mon Sep 17 00:00:00 2001
From: "Pierre-Loup A. Griffais" <pgriffais@valvesoftware.com>
Date: Wed, 10 Jul 2019 19:47:52 -0700
Subject: [PATCH 1/2] Implement pthread_mutex_lock_any() and
  pthread_mutex_timedlock_any().

On newer Linux kernels, futex supports a WAIT_MULTIPLE operation that can be
used to implement new locking functionality that allows a given application
thread to sleep while waiting for one of multiple given locks to become
available.
---
  nptl/Makefile                                 |   1 +
  nptl/Versions                                 |   2 +
  nptl/pthreadP.h                               |   5 +
  nptl/pthread_mutex_lock_any.c                 |  37 ++++
  nptl/pthread_mutex_timedlock_any.c            | 193 ++++++++++++++++++
  sysdeps/nptl/pthread.h                        |  10 +
  sysdeps/unix/sysv/linux/lowlevellock-futex.h  |  15 ++
  .../sysv/linux/x86_64/64/libpthread.abilist   |   1 +
  8 files changed, 264 insertions(+)
  create mode 100644 nptl/pthread_mutex_lock_any.c
  create mode 100644 nptl/pthread_mutex_timedlock_any.c

* Pierre-Loup A. Griffais:

> The gist of it is that it adds a new function,
> pthread_mutex_timedlock_any(), that can take a list of mutexes. It
> returns when one of the mutex has been locked (and tells you which
> one), or if the timeout is met. We would use this to reduce
> unnecessary wakeups and spinning in our thread pool synchronization
> code, compared to the current eventfd hack we rely on.

This explains why the mutexes have to be contiguous in memory.  For
other applications, this looks like an unnecessary restriction.

>  - I assume whichever name it might end up as should end with _np? Is
> there any specific process to follow for this sort of non-standard
> inclusion, other than just writing the code and documentation?

It seems unlikely that this is ever going to be standardized, so I think
we'd need the _np suffix, yes.

>  - What is the standard way for an application to discover whether it
> can use an entrypoint dependent on a certain Linux kernel version?
> With our proposed use, we'd be fine running the function once at
> startup to pick which path to chose, eg. pthread_mutex_lock_any( NULL,
> 0, NULL, NULL ). If it returns 0, we'd enable the new path, otherwise
> we'd fall back to eventfd(). I have a TODO in the code where we could
> do that, but it's probably not the right way to do things.

I think you would have to probe on first use inside
pthread_mutex_lock_any, using a dummy call.

>  - I assume the way I'm exposing it as a 2.2.5-versioned symbol for
> local testing is wrong; what is the right way to do this?

This patch could be targeted at glibc 2.31, then you would have to use
GLIBC_2.31.

>  - In my tree I have a placeholder test application that should be
> replaced by a new mutex test. However, it would also be a good idea to
> leverage other mutex tests to test this new thing, since it's a
> superset of many other mutex calls. Could we make the normal mutex
> test suite run a second time, with a macro wrapping the normal
> pthread_lock with this implementation instead?

Due to the new ENOMEM error, the new function is not a strict superset.

I'm wondering if the current design is really the right one,
particularly for thread pools.  The implementation performs multiple
scans of the mutex lists, which look rather costly for large pools.
That's probably unavoidable if the list is dynamic and potentially
different for every call, but given the array-based interface, I don't
think this is the intended use.  Something that use pre-registration of
the participating futexes could avoid that.  I also find it difficult to
believe that this approach beats something that involves queues, where a
worker thread that becomes available identifies itself directly to a
submitter thread, or can directly consume the submitted work item.

Thanks,
Florian

On 31/07/2019 01:07, Pierre-Loup A. Griffais wrote:
> I started putting together a patch to expose the new Linux futex functionality that recently got proposed for upstream inclusion. [1]
...
> 
> [1] https://lkml.org/lkml/2019/7/30/1399

i don't see that patch on the linux-api list where
userspace api related patches are discussed.

syscalls that have time argument need extra care now
that 32bit targets will get a new 64bit time_t abi.

the futex syscall is multiplexed and intricately
related to the pthread implementation so there are
many reasons why such patch should not be accepted
into linux before agreement with userspace.

On 31/07/2019 05:14, Florian Weimer wrote:
> * Pierre-Loup A. Griffais:
> 
>> The gist of it is that it adds a new function,
>> pthread_mutex_timedlock_any(), that can take a list of mutexes. It
>> returns when one of the mutex has been locked (and tells you which
>> one), or if the timeout is met. We would use this to reduce
>> unnecessary wakeups and spinning in our thread pool synchronization
>> code, compared to the current eventfd hack we rely on.
> 
> This explains why the mutexes have to be contiguous in memory.  For
> other applications, this looks like an unnecessary restriction.
> 
>>  - I assume whichever name it might end up as should end with _np? Is
>> there any specific process to follow for this sort of non-standard
>> inclusion, other than just writing the code and documentation?
> 
> It seems unlikely that this is ever going to be standardized, so I think
> we'd need the _np suffix, yes.
> 
>>  - What is the standard way for an application to discover whether it
>> can use an entrypoint dependent on a certain Linux kernel version?
>> With our proposed use, we'd be fine running the function once at
>> startup to pick which path to chose, eg. pthread_mutex_lock_any( NULL,
>> 0, NULL, NULL ). If it returns 0, we'd enable the new path, otherwise
>> we'd fall back to eventfd(). I have a TODO in the code where we could
>> do that, but it's probably not the right way to do things.
> 
> I think you would have to probe on first use inside
> pthread_mutex_lock_any, using a dummy call.
> 
>>  - I assume the way I'm exposing it as a 2.2.5-versioned symbol for
>> local testing is wrong; what is the right way to do this?
> 
> This patch could be targeted at glibc 2.31, then you would have to use
> GLIBC_2.31.
> 
>>  - In my tree I have a placeholder test application that should be
>> replaced by a new mutex test. However, it would also be a good idea to
>> leverage other mutex tests to test this new thing, since it's a
>> superset of many other mutex calls. Could we make the normal mutex
>> test suite run a second time, with a macro wrapping the normal
>> pthread_lock with this implementation instead?
> 
> Due to the new ENOMEM error, the new function is not a strict superset.
> 
> I'm wondering if the current design is really the right one,
> particularly for thread pools.  The implementation performs multiple
> scans of the mutex lists, which look rather costly for large pools.
> That's probably unavoidable if the list is dynamic and potentially
> different for every call, but given the array-based interface, I don't
> think this is the intended use.  Something that use pre-registration of
> the participating futexes could avoid that.  I also find it difficult to
> believe that this approach beats something that involves queues, where a
> worker thread that becomes available identifies itself directly to a
> submitter thread, or can directly consume the submitted work item.

Also, I am trying to understand exactly what the new futex operation tries
to optimize.  The kernel patch adds some information about a wine specific
implementation, but it not clear what exactly was tested on "Wine fsync 
implementation and executing multi-threaded applications" neither by
"example code that exercises the FUTEX_WAIT_MULTIPLE path on a
multi-threaded".

Could you provide some actual source code for your 'thread pool synchronization 
code' or at least point to the wine code that you are aiming to optimize?

[replying to both inline below, let me know if just branching the thread
is generally preferable in the future]

On 7/31/19 1:14 AM, Florian Weimer wrote:> * Pierre-Loup A. Griffais:
> 
>> The gist of it is that it adds a new function, 
>> pthread_mutex_timedlock_any(), that can take a list of mutexes. It 
>> returns when one of the mutex has been locked (and tells you which 
>> one), or if the timeout is met. We would use this to reduce 
>> unnecessary wakeups and spinning in our thread pool
>> synchronization code, compared to the current eventfd hack we rely
>> on.
> 
> This explains why the mutexes have to be contiguous in memory.  For 
> other applications, this looks like an unnecessary restriction.

Agreed. Will switch the first argument to an array of pointers instead.

> 
>> - I assume whichever name it might end up as should end with _np?
>> Is there any specific process to follow for this sort of
>> non-standard inclusion, other than just writing the code and
>> documentation?
> 
> It seems unlikely that this is ever going to be standardized, so I
> think we'd need the _np suffix, yes.

Thanks for clarifying.

> 
>> - What is the standard way for an application to discover whether
>> it can use an entrypoint dependent on a certain Linux kernel
>> version? With our proposed use, we'd be fine running the function
>> once at startup to pick which path to chose, eg.
>> pthread_mutex_lock_any( NULL, 0, NULL, NULL ). If it returns 0,
>> we'd enable the new path, otherwise we'd fall back to eventfd(). I
>> have a TODO in the code where we could do that, but it's probably
>> not the right way to do things.
> 
> I think you would have to probe on first use inside 
> pthread_mutex_lock_any, using a dummy call.

OK, that was my original plan, I can finish writing that up.

> 
>> - I assume the way I'm exposing it as a 2.2.5-versioned symbol for 
>> local testing is wrong; what is the right way to do this?
> 
> This patch could be targeted at glibc 2.31, then you would have to
> use GLIBC_2.31.
> 
>> - In my tree I have a placeholder test application that should be 
>> replaced by a new mutex test. However, it would also be a good idea
>> to leverage other mutex tests to test this new thing, since it's a 
>> superset of many other mutex calls. Could we make the normal mutex 
>> test suite run a second time, with a macro wrapping the normal 
>> pthread_lock with this implementation instead?
> 
> Due to the new ENOMEM error, the new function is not a strict
> superset.

True, thanks for pointing that out. Any sort of attempted wrapping would
have to account for that somehow.

> 
> I'm wondering if the current design is really the right one, 
> particularly for thread pools.  The implementation performs multiple 
> scans of the mutex lists, which look rather costly for large pools. 
> That's probably unavoidable if the list is dynamic and potentially 
> different for every call, but given the array-based interface, I
> don't think this is the intended use.  Something that use
> pre-registration of the participating futexes could avoid that.  I
> also find it difficult to believe that this approach beats something
> that involves queues, where a worker thread that becomes available
> identifies itself directly to a submitter thread, or can directly
> consume the submitted work item.

That might be interesting if walking the lists turns out to be a
hotspot. I think the mutex count per operation would typically not be 
thousands, and probably not hundreds either.

I would think there's still a queue somewhere to acquire jobs, this 
would be used before and after. For instance, job threads want to sleep 
until work has been queued, or another system event occurs that might 
require them to wake up, like app shutdown or scene transition. 
Similarly, after firing off N jobs, the job manager will want to sleep 
until one of the jobs is complete to perform some accounting and publish 
the results to other systems. For both of these usecases, using eventfd 
to wait for multiple events seems to result in more CPU spinning than 
the futex-based solution, both in userspace and the kernel.

> 
> Thanks, Florian
> 

On 7/31/19 3:01 AM, Szabolcs Nagy wrote:
> On 31/07/2019 01:07, Pierre-Loup A. Griffais wrote:
>> I started putting together a patch to expose the new Linux futex
>> functionality that recently got proposed for upstream inclusion.
>> [1]
> ...
>> 
>> [1] https://lkml.org/lkml/2019/7/30/1399
> 
> i don't see that patch on the linux-api list where userspace api
> related patches are discussed.
> 
> syscalls that have time argument need extra care now that 32bit
> targets will get a new 64bit time_t abi.

Thanks, looks like there were compat concerns raised on the kernel side 
as well; we can copy linux-api for the next patch iteration.

> 
> the futex syscall is multiplexed and intricately related to the
> pthread implementation so there are many reasons why such patch
> should not be accepted into linux before agreement with userspace.

What does that process typically look like, other than raising it on 
both ends like we did?

Thanks for all the feedback!
  - Pierre-Loup

>

On 31/07/2019 22:58, Pierre-Loup A. Griffais wrote:
> On 7/31/19 3:01 AM, Szabolcs Nagy wrote:
>> the futex syscall is multiplexed and intricately related to the
>> pthread implementation so there are many reasons why such patch
>> should not be accepted into linux before agreement with userspace.
> 
> What does that process typically look like, other than raising it on both ends like we did?

such kernel patch has to be visible to ppl who care about
the linux userspace api, i think the linux-api list is the
closest and if the patch needs eyes from glibc developers
then cc libc-alpha too (e.g. a patch documenting new syscall
behaviour on the kernel side should ideally be reviewed on
libc-alpha too to ensure the semantics is ok from a libc pov)

* Pierre-Loup A. Griffais:

> I would think there's still a queue somewhere to acquire jobs, this
> would be used before and after. For instance, job threads want to
> sleep until work has been queued, or another system event occurs that
> might require them to wake up, like app shutdown or scene
> transition. Similarly, after firing off N jobs, the job manager will
> want to sleep until one of the jobs is complete to perform some
> accounting and publish the results to other systems. For both of these
> usecases, using eventfd to wait for multiple events seems to result in
> more CPU spinning than the futex-based solution, both in userspace and
> the kernel.

Why do you consider eventfd the only viable alternative?  If you want a
futex-based solution today, you can use condition variables.  It won't
give you the theoretical minimum of context switches, but neither does
FUTEX_WAIT_MULTIPLE, as far as I can tell.

Thanks,
Florian

On 8/1/19 2:39 AM, Florian Weimer wrote:
> * Pierre-Loup A. Griffais:
> 
>> I would think there's still a queue somewhere to acquire jobs, this
>> would be used before and after. For instance, job threads want to
>> sleep until work has been queued, or another system event occurs that
>> might require them to wake up, like app shutdown or scene
>> transition. Similarly, after firing off N jobs, the job manager will
>> want to sleep until one of the jobs is complete to perform some
>> accounting and publish the results to other systems. For both of these
>> usecases, using eventfd to wait for multiple events seems to result in
>> more CPU spinning than the futex-based solution, both in userspace and
>> the kernel.
> 
> Why do you consider eventfd the only viable alternative?  If you want a
> futex-based solution today, you can use condition variables.  It won't
> give you the theoretical minimum of context switches, but neither does
> FUTEX_WAIT_MULTIPLE, as far as I can tell.

I think there's two main aspects to this, one is purely technical and I 
can try to speak to it a bit below:

Unless I'm missing something, in the scenario where I have N (where N is 
probably close to the CPU count on the machine) job threads processing 
work and needing to report back to a job system, then promptly get back 
to work, wouldn't trying to implement this with condition variables 
introduce unwanted contention between the job threads at reporting that 
wouldn't exist otherwise? Or, unwanted spinning on the job manager side.

So I do think it would give us quite a bit more potential context 
switches and overhead, which we're trying to reduce. Spinning more for 
the same latency is not desirable for gaming, as power usage also 
factors in.

When you say the proposed futex approach is still not necessarily 
optimal, do you mean compared to a complete lockless design on the app 
side? Do you agree it would still be more efficient than using cond 
vars? (and that would require some redesign work on the app side as well)

The other aspect is that we're dealing with a bunch of applications that 
have their threading model already defined by the time they target 
Linux. They can use WaitForMultiple() on Windows and kqueue on macOS; 
they typically opt for lower-performance "emulation" of the desired 
behavior using multiple mutexes, condition variables, or eventfd. I 
think this new primitive would let them quickly port to something that 
is equally as efficient, or more efficient, than their starting point.

Thanks,
  - Pierre-Loup

> 
> Thanks,
> Florian
>

* Pierre-Loup A. Griffais:

> On 8/1/19 2:39 AM, Florian Weimer wrote:
>> * Pierre-Loup A. Griffais:
>>
>>> I would think there's still a queue somewhere to acquire jobs, this
>>> would be used before and after. For instance, job threads want to
>>> sleep until work has been queued, or another system event occurs that
>>> might require them to wake up, like app shutdown or scene
>>> transition. Similarly, after firing off N jobs, the job manager will
>>> want to sleep until one of the jobs is complete to perform some
>>> accounting and publish the results to other systems. For both of these
>>> usecases, using eventfd to wait for multiple events seems to result in
>>> more CPU spinning than the futex-based solution, both in userspace and
>>> the kernel.
>>
>> Why do you consider eventfd the only viable alternative?  If you want a
>> futex-based solution today, you can use condition variables.  It won't
>> give you the theoretical minimum of context switches, but neither does
>> FUTEX_WAIT_MULTIPLE, as far as I can tell.
>
> I think there's two main aspects to this, one is purely technical and
> I can try to speak to it a bit below:
>
> Unless I'm missing something, in the scenario where I have N (where N
> is probably close to the CPU count on the machine) job threads
> processing work and needing to report back to a job system, then
> promptly get back to work, wouldn't trying to implement this with
> condition variables introduce unwanted contention between the job
> threads at reporting that wouldn't exist otherwise? Or, unwanted
> spinning on the job manager side.

I don't really see how FUTEX_WAIT_MULTIPLE supports this nicely.  Since
the mutex you get back is arbitrary, you cannot unconditionally enqueue
a job on that worker thread because you might always get back the same
worker thread, leading to unbounded queue growth.  So the submitting
needs to synchronize with the chosen worker thread anyway.

And the contention is there with FUTEX_WAIT_MULTIPLE as well, except
that you don't have one very hot cache line, but several cache lines
bouncing around between CPUs.

I guess the architecture just isn't clear to me.

> The other aspect is that we're dealing with a bunch of applications
> that have their threading model already defined by the time they
> target Linux. They can use WaitForMultiple() on Windows and kqueue on
> macOS; they typically opt for lower-performance "emulation" of the
> desired behavior using multiple mutexes, condition variables, or
> eventfd. I think this new primitive would let them quickly port to
> something that is equally as efficient, or more efficient, than their
> starting point.

I really doubt that a futex-based WaitForMultipleObjects implementation
can have equally efficient performance, unless the Windows
implementation is really, really bad.  It's hard to optimize
WaitForMultipleObjects (just as it is hard to optimize select/poll), but
I think it's impossible if all you have is an array of concrete futexes
with fixed semantics.

Thanks,
Florian