[2/5] libstdc++ futex: Use FUTEX_CLOCK_REALTIME for wait

Message ID 20180107205532.13138-3-mac@mcrowe.com
State New
Headers show
Series
  • Make std::future::wait_* use std::chrono::steady_clock when required
Related show

Commit Message

Mike Crowe Jan. 7, 2018, 8:55 p.m.
The futex system call supports waiting for an absolute time if
FUTEX_WAIT_BITSET is used rather than FUTEX_WAIT. Doing so provides two
benefits:

1. The call to gettimeofday is not required in order to calculate a
   relative timeout.

2. If someone changes the system clock during the wait then the futex
   timeout will correctly expire earlier or later. Currently that only
   happens if the clock is changed prior to the call to gettimeofday.

According to futex(2), support for FUTEX_CLOCK_REALTIME was added in the
v2.6.28 Linux kernel and FUTEX_WAIT_BITSET was added in v2.6.25. There is
no attempt to detect the kernel version and fall back to the previous
method.
---
 libstdc++-v3/src/c++11/futex.cc | 21 ++++++---------------
 1 file changed, 6 insertions(+), 15 deletions(-)

-- 
2.11.0

Comments

Jonathan Wakely Jan. 9, 2018, 1:50 p.m. | #1
On 07/01/18 20:55 +0000, Mike Crowe wrote:
>The futex system call supports waiting for an absolute time if

>FUTEX_WAIT_BITSET is used rather than FUTEX_WAIT. Doing so provides two

>benefits:

>

>1. The call to gettimeofday is not required in order to calculate a

>   relative timeout.

>

>2. If someone changes the system clock during the wait then the futex

>   timeout will correctly expire earlier or later. Currently that only

>   happens if the clock is changed prior to the call to gettimeofday.

>

>According to futex(2), support for FUTEX_CLOCK_REALTIME was added in the

>v2.6.28 Linux kernel and FUTEX_WAIT_BITSET was added in v2.6.25. There is

>no attempt to detect the kernel version and fall back to the previous

>method.


I don't think we can require a specific kernel version just for this.

What happens if you use those bits on an older kernel, will there be
an ENOSYS error? Because that would allow us to try the new form, and
fallback to the old.

With that I think this change looks good.


>---

> libstdc++-v3/src/c++11/futex.cc | 21 ++++++---------------

> 1 file changed, 6 insertions(+), 15 deletions(-)

>

>diff --git a/libstdc++-v3/src/c++11/futex.cc b/libstdc++-v3/src/c++11/futex.cc

>index f5000aa77b3..40ec7f9b0f7 100644

>--- a/libstdc++-v3/src/c++11/futex.cc

>+++ b/libstdc++-v3/src/c++11/futex.cc

>@@ -35,6 +35,9 @@

>

> // Constants for the wait/wake futex syscall operations

> const unsigned futex_wait_op = 0;

>+const unsigned futex_wait_bitset_op = 9;

>+const unsigned futex_clock_realtime_flag = 256;

>+const unsigned futex_bitset_match_any = ~0;

> const unsigned futex_wake_op = 1;

>

> namespace std _GLIBCXX_VISIBILITY(default)

>@@ -58,22 +61,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION

>       }

>     else

>       {

>-	struct timeval tv;

>-	gettimeofday (&tv, NULL);

>-	// Convert the absolute timeout value to a relative timeout

> 	struct timespec rt;

>-	rt.tv_sec = __s.count() - tv.tv_sec;

>-	rt.tv_nsec = __ns.count() - tv.tv_usec * 1000;

>-	if (rt.tv_nsec < 0)

>-	  {

>-	    rt.tv_nsec += 1000000000;

>-	    --rt.tv_sec;

>-	  }

>-	// Did we already time out?

>-	if (rt.tv_sec < 0)

>-	  return false;

>-

>-	if (syscall (SYS_futex, __addr, futex_wait_op, __val, &rt) == -1)

>+	rt.tv_sec = __s.count();

>+	rt.tv_nsec = __ns.count();

>+	if (syscall (SYS_futex, __addr, futex_wait_bitset_op | futex_clock_realtime_flag, __val, &rt, nullptr, futex_bitset_match_any) == -1)

> 	  {

> 	    _GLIBCXX_DEBUG_ASSERT(errno == EINTR || errno == EAGAIN

> 				  || errno == ETIMEDOUT);

>-- 

>2.11.0

>

>
Mike Crowe Jan. 9, 2018, 5:54 p.m. | #2
On Tuesday 09 January 2018 at 13:50:54 +0000, Jonathan Wakely wrote:
> On 07/01/18 20:55 +0000, Mike Crowe wrote:

> > The futex system call supports waiting for an absolute time if

> > FUTEX_WAIT_BITSET is used rather than FUTEX_WAIT. Doing so provides two

> > benefits:

> > 

> > 1. The call to gettimeofday is not required in order to calculate a

> >   relative timeout.

> > 

> > 2. If someone changes the system clock during the wait then the futex

> >   timeout will correctly expire earlier or later. Currently that only

> >   happens if the clock is changed prior to the call to gettimeofday.

> > 

> > According to futex(2), support for FUTEX_CLOCK_REALTIME was added in the

> > v2.6.28 Linux kernel and FUTEX_WAIT_BITSET was added in v2.6.25. There is

> > no attempt to detect the kernel version and fall back to the previous

> > method.

> 

> I don't think we can require a specific kernel version just for this.


What is the minimum kernel version that libstdc++ requires? Since it's
already relying on NPTL it can't go back earlier than v2.6, but I suppose
that's a while before v2.6.28.

> What happens if you use those bits on an older kernel, will there be

> an ENOSYS error? Because that would allow us to try the new form, and

> fallback to the old.


Glibc's nptl-init.c calls

 futex(.., FUTEX_WAIT_BITSET | FUTEX_CLOCK_REALTIME | FUTEX_PRIVATE_FLAG, ..)

and sets __have_futex_clock_realtime based on whether it gets ENOSYS back
or not so it looks like it is possible to determine whether support is
available.

The only such check I can find in libstdc++ is in filesystem/std-ops.cc
fs::do_copy_file which can try sendfile(2) on each invocation but then
automatically falls back to copying by steam. In that case, the overhead of
the potentially-failing sendfile system call is small compared to copying
the file.

Doing such a check in _M_futex_wait_until means one system call if
FUTEX_CLOCK_REALTIME is supported, but three system calls if it is not
supported. If we found a way to cache the answer in a thread-safe and cheap
manner then this could be avoided.

Do you think it's worth trying to cache whether FUTEX_CLOCK_REALTIME is
available?

Thanks.

Mike.
Torvald Riegel Jan. 12, 2018, 1:18 p.m. | #3
On Tue, 2018-01-09 at 17:54 +0000, Mike Crowe wrote:
> On Tuesday 09 January 2018 at 13:50:54 +0000, Jonathan Wakely wrote:

> > On 07/01/18 20:55 +0000, Mike Crowe wrote:

> > > The futex system call supports waiting for an absolute time if

> > > FUTEX_WAIT_BITSET is used rather than FUTEX_WAIT. Doing so provides two

> > > benefits:

> > > 

> > > 1. The call to gettimeofday is not required in order to calculate a

> > >   relative timeout.

> > > 

> > > 2. If someone changes the system clock during the wait then the futex

> > >   timeout will correctly expire earlier or later. Currently that only

> > >   happens if the clock is changed prior to the call to gettimeofday.

> > > 

> > > According to futex(2), support for FUTEX_CLOCK_REALTIME was added in the

> > > v2.6.28 Linux kernel and FUTEX_WAIT_BITSET was added in v2.6.25. There is

> > > no attempt to detect the kernel version and fall back to the previous

> > > method.

> > 

> > I don't think we can require a specific kernel version just for this.

> 

> What is the minimum kernel version that libstdc++ requires? Since it's

> already relying on NPTL it can't go back earlier than v2.6, but I suppose

> that's a while before v2.6.28.


I'm not aware of any choice regarding this, but Jonathan will know for
sure.

Generally, I think choosing a minium kernel version might be helpful, in
particular if we want to optimize more often specifically for Linux
environments; this may become more worthwhile in the future, for example
when we look at new C++ features such as parallel algorithms, or
upcoming executors.
The gthreads abstraction may is a nice goal, but we can benefit a lot
from knowing what the underlying platform really is.

Another option might be to require a minimum glibc version on Linux, and
build libstdc++ for that.  That would yield a minimum kernel version as
well, and we may can make use of other things in return such as syscall
wrappers.

> > What happens if you use those bits on an older kernel, will there be

> > an ENOSYS error? Because that would allow us to try the new form, and

> > fallback to the old.

> 

> Glibc's nptl-init.c calls

> 

>  futex(.., FUTEX_WAIT_BITSET | FUTEX_CLOCK_REALTIME | FUTEX_PRIVATE_FLAG, ..)

> 

> and sets __have_futex_clock_realtime based on whether it gets ENOSYS back

> or not so it looks like it is possible to determine whether support is

> available.

> 

> The only such check I can find in libstdc++ is in filesystem/std-ops.cc

> fs::do_copy_file which can try sendfile(2) on each invocation but then

> automatically falls back to copying by steam. In that case, the overhead of

> the potentially-failing sendfile system call is small compared to copying

> the file.

> 

> Doing such a check in _M_futex_wait_until means one system call if

> FUTEX_CLOCK_REALTIME is supported, but three system calls if it is not

> supported. If we found a way to cache the answer in a thread-safe and cheap

> manner then this could be avoided.

> 

> Do you think it's worth trying to cache whether FUTEX_CLOCK_REALTIME is

> available?


It may be worth caching that, given how simple this can be:  Just add a
global atomic variable whose initial value means trying the most recent
syscall op, and set that to some other value that indicates an older
kernel.  Then check the value before attempting the syscall.  Can all be
relaxed atomic accesses because it's essentially just a best-effort
optimization.

Performance-wise, the trade-off is between an additional atomic load for
new kernels vs. one additional syscall for older kernels.  Given that we
need the fallback for old kernels anyway unless we select a minimum
version, I guess doing the caching makes sense.  The syscalls are on the
slow paths anyway.
Jonathan Wakely Jan. 12, 2018, 2:49 p.m. | #4
On 12/01/18 14:18 +0100, Torvald Riegel wrote:
>On Tue, 2018-01-09 at 17:54 +0000, Mike Crowe wrote:

>> On Tuesday 09 January 2018 at 13:50:54 +0000, Jonathan Wakely wrote:

>> > On 07/01/18 20:55 +0000, Mike Crowe wrote:

>> > > The futex system call supports waiting for an absolute time if

>> > > FUTEX_WAIT_BITSET is used rather than FUTEX_WAIT. Doing so provides two

>> > > benefits:

>> > >

>> > > 1. The call to gettimeofday is not required in order to calculate a

>> > >   relative timeout.

>> > >

>> > > 2. If someone changes the system clock during the wait then the futex

>> > >   timeout will correctly expire earlier or later. Currently that only

>> > >   happens if the clock is changed prior to the call to gettimeofday.

>> > >

>> > > According to futex(2), support for FUTEX_CLOCK_REALTIME was added in the

>> > > v2.6.28 Linux kernel and FUTEX_WAIT_BITSET was added in v2.6.25. There is

>> > > no attempt to detect the kernel version and fall back to the previous

>> > > method.

>> >

>> > I don't think we can require a specific kernel version just for this.

>>

>> What is the minimum kernel version that libstdc++ requires? Since it's

>> already relying on NPTL it can't go back earlier than v2.6, but I suppose

>> that's a while before v2.6.28.

>

>I'm not aware of any choice regarding this, but Jonathan will know for

>sure.


I don't think we currently have a documented minimum, although there
is an implied one, which I guess is 2.6.0 ... I can't think of
anything else that places requirements on the kernel. Apart from NPTL
we use SYS_futex and SYS_clock_gettime, but there are alternative code
paths for both of those.

>Generally, I think choosing a minium kernel version might be helpful, in

>particular if we want to optimize more often specifically for Linux

>environments; this may become more worthwhile in the future, for example

>when we look at new C++ features such as parallel algorithms, or

>upcoming executors.

>The gthreads abstraction may is a nice goal, but we can benefit a lot

>from knowing what the underlying platform really is.


Agreed. Gthreads is the cause of a few problems for libstdc++.

>Another option might be to require a minimum glibc version on Linux, and

>build libstdc++ for that.  That would yield a minimum kernel version as

>well, and we may can make use of other things in return such as syscall

>wrappers.


We document that we require glibc 2.3, but that is ancient. It's
possible we've unintentionally introduced an implicit requirement on a
newer version.
Joseph Myers Jan. 12, 2018, 5:55 p.m. | #5
On Fri, 12 Jan 2018, Torvald Riegel wrote:

> Another option might be to require a minimum glibc version on Linux, and

> build libstdc++ for that.  That would yield a minimum kernel version as

> well, and we may can make use of other things in return such as syscall

> wrappers.


A minimum glibc version of course only applies when libstdc++ is being 
built with glibc - it can also be built with other C libraries using the 
Linux kernel (and some - at least uClibc - define __GLIBC__ to pretend to 
be some old glibc version).

One thing to note regarding minimum glibc (or kernel) versions is it can 
be useful to use new GCC to build binaries to run on older systems - which 
means building new GCC as a cross compiler with a sysroot with an old 
glibc version in it.  So the relevant question for establishing a minimum 
glibc or kernel version is not what systems people are using to develop 
GCC, but what systems they might want to deploy binaries built with 
current GCC onto.

-- 
Joseph S. Myers
joseph@codesourcery.com

Patch

diff --git a/libstdc++-v3/src/c++11/futex.cc b/libstdc++-v3/src/c++11/futex.cc
index f5000aa77b3..40ec7f9b0f7 100644
--- a/libstdc++-v3/src/c++11/futex.cc
+++ b/libstdc++-v3/src/c++11/futex.cc
@@ -35,6 +35,9 @@ 
 
 // Constants for the wait/wake futex syscall operations
 const unsigned futex_wait_op = 0;
+const unsigned futex_wait_bitset_op = 9;
+const unsigned futex_clock_realtime_flag = 256;
+const unsigned futex_bitset_match_any = ~0;
 const unsigned futex_wake_op = 1;
 
 namespace std _GLIBCXX_VISIBILITY(default)
@@ -58,22 +61,10 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
       }
     else
       {
-	struct timeval tv;
-	gettimeofday (&tv, NULL);
-	// Convert the absolute timeout value to a relative timeout
 	struct timespec rt;
-	rt.tv_sec = __s.count() - tv.tv_sec;
-	rt.tv_nsec = __ns.count() - tv.tv_usec * 1000;
-	if (rt.tv_nsec < 0)
-	  {
-	    rt.tv_nsec += 1000000000;
-	    --rt.tv_sec;
-	  }
-	// Did we already time out?
-	if (rt.tv_sec < 0)
-	  return false;
-
-	if (syscall (SYS_futex, __addr, futex_wait_op, __val, &rt) == -1)
+	rt.tv_sec = __s.count();
+	rt.tv_nsec = __ns.count();
+	if (syscall (SYS_futex, __addr, futex_wait_bitset_op | futex_clock_realtime_flag, __val, &rt, nullptr, futex_bitset_match_any) == -1)
 	  {
 	    _GLIBCXX_DEBUG_ASSERT(errno == EINTR || errno == EAGAIN
 				  || errno == ETIMEDOUT);