[PATCH 0/5] Make std::future::wait_* use std::chrono::steady_clock when required

[PATCH 0/5] Make std::future::wait_* use std::chrono::steady_clock when required

[Mike Crowe]

This patch series was originally submitted back in September at
https://gcc.gnu.org/ml/libstdc++/2017-09/msg00083.html which ended up
as https://patchwork.ozlabs.org/cover/817379/ . The patches received
no comments at all, which may mean that they are perfect or that they
are so bad that no-one knew where to start with criticising them. It
would be good to know which. :)

The patches are unchanged from last time, but I have corrected a typo
in one of the commit messages. The original cover message follows.

This is a first attempt to make std::future::wait_until and
std::future::wait_for make correct use of
std::chrono::steady_clock/CLOCK_MONOTONIC. It also makes
std::future::wait_until react to changes to CLOCK_REALTIME during the
wait, but only when passed a std::chrono::system_clock time point.

Prior to these patches, the situation is similar to that described at
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=41861 for
std::condition_variable, but with the benefit that this time the bug can be
fixed entirely within libstdc++.

(I've omitted the ChangeLog entries for now, since I don't believe that
this is ready to be accepted in its current form.)

Mike Crowe (5): Improve libstdc++-v3 async test libstdc++ futex: Use
  FUTEX_CLOCK_REALTIME for wait libstdc++ futex: Support waiting on
  std::chrono::steady_clock directly libstdc++ atomic_futex: Use
  std::chrono::steady_clock as reference clock Extra async tests, not
  for merging

 libstdc++-v3/include/bits/atomic_futex.h         |  74 ++++++++++++++-
 libstdc++-v3/src/c++11/futex.cc                  |  48 +++++++---
 libstdc++-v3/testsuite/30_threads/async/async.cc | 112 +++++++++++++++++++++++
 3 files changed, 217 insertions(+), 17 deletions(-)

-- 
2.11.0

[PATCH 5/5] Extra async tests, not for merging

[Mike Crowe]

These tests show that changing the system clock has an effect on
std::future::wait_until when using std::chrono::system_clock but not when
using std::chrono::steady_clock. Unfortunately these tests have a number of
downsides:

1. Nothing that is attempting to keep the clock set correctly (ntpd,
   systemd-timesyncd) can be running at the same time.

2. The test process requires the CAP_SYS_TIME capability.

3. Other processes running concurrently may misbehave when the clock darts
   back and forth.

4. They are slow to run.

As such, I don't think they are suitable for merging. I include them here
because I wanted to document how I had tested the changes in the previous
commits.
---
 libstdc++-v3/testsuite/30_threads/async/async.cc | 76 ++++++++++++++++++++++++
 1 file changed, 76 insertions(+)

diff --git a/libstdc++-v3/testsuite/30_threads/async/async.cc b/libstdc++-v3/testsuite/30_threads/async/async.cc
index 7326c5f7cd6..5bd7e999401 100644
--- a/libstdc++-v3/testsuite/30_threads/async/async.cc
+++ b/libstdc++-v3/testsuite/30_threads/async/async.cc
@@ -25,6 +25,7 @@
 
 #include <future>
 #include <testsuite_hooks.h>
+#include <sys/time.h>
 
 using namespace std;
 
@@ -94,11 +95,86 @@ void test03()
   VERIFY( elapsed < std::chrono::seconds(20) );
 }
 
+void perturb_system_clock(const std::chrono::seconds &seconds)
+{
+  struct timeval tv;
+  if (gettimeofday(&tv, NULL))
+    abort();
+
+  tv.tv_sec += seconds.count();
+  if (settimeofday(&tv, NULL))
+    abort();
+}
+
+void work04()
+{
+  std::this_thread::sleep_for(std::chrono::seconds(10));
+}
+
+// Ensure that advancing CLOCK_REALTIME doesn't make any difference
+// when we're waiting on std::chrono::steady_clock.
+void test04()
+{
+  auto const start = chrono::steady_clock::now();
+  future<void> f1 = async(launch::async, &work04);
+
+  perturb_system_clock(chrono::seconds(20));
+
+  std::future_status status;
+  status = f1.wait_for(std::chrono::seconds(4));
+  VERIFY( status == std::future_status::timeout );
+
+  status = f1.wait_until(start + std::chrono::seconds(6));
+  VERIFY( status == std::future_status::timeout );
+
+  status = f1.wait_until(start + std::chrono::seconds(12));
+  VERIFY( status == std::future_status::ready );
+
+  auto const elapsed = chrono::steady_clock::now() - start;
+  VERIFY( elapsed >= std::chrono::seconds(10) );
+  VERIFY( elapsed < std::chrono::seconds(15) );
+
+  perturb_system_clock(chrono::seconds(-20));
+}
+
+void work05()
+{
+  std::this_thread::sleep_for(std::chrono::seconds(5));
+  perturb_system_clock(chrono::seconds(60));
+  std::this_thread::sleep_for(std::chrono::seconds(5));
+}
+
+// Ensure that advancing CLOCK_REALTIME does make a difference when
+// we're waiting on std::chrono::system_clock.
+void test05()
+{
+  auto const start = chrono::system_clock::now();
+  auto const start_steady = chrono::steady_clock::now();
+
+  future<void> f1 = async(launch::async, &work05);
+  future_status status;
+  status = f1.wait_until(start + std::chrono::seconds(60));
+  VERIFY( status == std::future_status::timeout );
+
+  auto const elapsed_steady = chrono::steady_clock::now() - start_steady;
+  VERIFY( elapsed_steady >= std::chrono::seconds(5) );
+  VERIFY( elapsed_steady < std::chrono::seconds(10) );
+
+  status = f1.wait_until(start + std::chrono::seconds(75));
+  VERIFY( status == std::future_status::ready );
+
+  perturb_system_clock(chrono::seconds(-60));
+}
+
 int main()
 {
   test01();
   test02();
   test03<std::chrono::system_clock>();
   test03<std::chrono::steady_clock>();
+  if (geteuid() == 0) {
+    test04();
+    test05();
+  }
   return 0;
 }
-- 
2.11.0

[PATCH 4/5] libstdc++ atomic_futex: Use std::chrono::steady_clock as reference clock

[Mike Crowe]

The user-visible effect of this change is that std::future::wait_for now
uses std::chrono::steady_clock to determine the timeout. This makes it
immune to changes made to the system clock. It also means that anyone using
their own clock types with std::future::wait_until will have the timeout
converted to std::chrono::steady_clock rather than
std::chrono::system_clock.

Now that use of both std::chrono::steady_clock and
std::chrono::system_clock are correctly supported for the wait timeout, I
believe that std::chrono::steady_clock is a better choice for the reference
clock that all other clocks are converted to since it is guaranteed to
advance steadily. The previous behaviour of converting to
std::chrono::system_clock risks timeouts changing dramatically when the
system clock is changed.
---
 libstdc++-v3/include/bits/atomic_futex.h | 7 +++----
 1 file changed, 3 insertions(+), 4 deletions(-)

diff --git a/libstdc++-v3/include/bits/atomic_futex.h b/libstdc++-v3/include/bits/atomic_futex.h
index 78f39fb4048..7dff848d8ad 100644
--- a/libstdc++-v3/include/bits/atomic_futex.h
+++ b/libstdc++-v3/include/bits/atomic_futex.h
@@ -71,7 +71,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
   template <unsigned _Waiter_bit = 0x80000000>
   class __atomic_futex_unsigned : __atomic_futex_unsigned_base
   {
-    typedef chrono::system_clock __clock_t;
+    typedef chrono::steady_clock __clock_t;
 
     // This must be lock-free and at offset 0.
     atomic<unsigned> _M_data;
@@ -169,7 +169,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     unsigned
     _M_load_and_test_until_impl(unsigned __assumed, unsigned __operand,
 	bool __equal, memory_order __mo,
-	const chrono::time_point<__clock_t, _Dur>& __atime)
+	const chrono::time_point<std::chrono::system_clock, _Dur>& __atime)
     {
       auto __s = chrono::time_point_cast<chrono::seconds>(__atime);
       auto __ns = chrono::duration_cast<chrono::nanoseconds>(__atime - __s);
@@ -229,7 +229,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       _M_load_when_equal_until(unsigned __val, memory_order __mo,
 	  const chrono::time_point<_Clock, _Duration>& __atime)
       {
-	// DR 887 - Sync unknown clock to known clock.
 	const typename _Clock::time_point __c_entry = _Clock::now();
 	const __clock_t::time_point __s_entry = __clock_t::now();
 	const auto __delta = __atime - __c_entry;
@@ -241,7 +240,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     template<typename _Duration>
     _GLIBCXX_ALWAYS_INLINE bool
     _M_load_when_equal_until(unsigned __val, memory_order __mo,
-	const chrono::time_point<__clock_t, _Duration>& __atime)
+	const chrono::time_point<std::chrono::system_clock, _Duration>& __atime)
     {
       unsigned __i = _M_load(__mo);
       if ((__i & ~_Waiter_bit) == __val)
-- 
2.11.0

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

[Mike Crowe]

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(-)

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

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

[Jonathan Wakely]

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
>
>

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

[Mike Crowe]

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.

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

[Torvald Riegel]

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.

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

[Jonathan Wakely]

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.

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

[Joseph Myers]

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 1/5] Improve libstdc++-v3 async test

[Mike Crowe]

Add tests for waiting for the future using both std::chrono::steady_clock
and std::chrono::system_clock in preparation for dealing with those clocks
properly in futex.cc.
---
 libstdc++-v3/testsuite/30_threads/async/async.cc | 36 ++++++++++++++++++++++++
 1 file changed, 36 insertions(+)

diff --git a/libstdc++-v3/testsuite/30_threads/async/async.cc b/libstdc++-v3/testsuite/30_threads/async/async.cc
index 8071cb133fc..7326c5f7cd6 100644
--- a/libstdc++-v3/testsuite/30_threads/async/async.cc
+++ b/libstdc++-v3/testsuite/30_threads/async/async.cc
@@ -52,17 +52,53 @@ void test02()
   VERIFY( status == std::future_status::timeout );
   status = f1.wait_until(std::chrono::system_clock::now());
   VERIFY( status == std::future_status::timeout );
+  status = f1.wait_until(std::chrono::steady_clock::now());
+  VERIFY( status == std::future_status::timeout );
   l.unlock();  // allow async thread to proceed
   f1.wait();   // wait for it to finish
   status = f1.wait_for(std::chrono::milliseconds(0));
   VERIFY( status == std::future_status::ready );
   status = f1.wait_until(std::chrono::system_clock::now());
   VERIFY( status == std::future_status::ready );
+  status = f1.wait_until(std::chrono::steady_clock::now());
+  VERIFY( status == std::future_status::ready );
+}
+
+void work03()
+{
+    std::this_thread::sleep_for(std::chrono::seconds(15));
+}
+
+// This test is slow in order to try and avoid failing on a loaded
+// machine. Nevertheless, it could still fail if the kernel decides
+// not to schedule us for several seconds. It also assumes that no-one
+// will change CLOCK_REALTIME whilst the test is running.
+template<typename CLOCK>
+void test03()
+{
+  auto const start = CLOCK::now();
+  future<void> f1 = async(launch::async, &work03);
+  std::future_status status;
+
+  status = f1.wait_for(std::chrono::seconds(5));
+  VERIFY( status == std::future_status::timeout );
+
+  status = f1.wait_until(start + std::chrono::seconds(10));
+  VERIFY( status == std::future_status::timeout );
+
+  status = f1.wait_until(start + std::chrono::seconds(25));
+  VERIFY( status == std::future_status::ready );
+
+  auto const elapsed = CLOCK::now() - start;
+  VERIFY( elapsed >= std::chrono::seconds(15) );
+  VERIFY( elapsed < std::chrono::seconds(20) );
 }
 
 int main()
 {
   test01();
   test02();
+  test03<std::chrono::system_clock>();
+  test03<std::chrono::steady_clock>();
   return 0;
 }
-- 
2.11.0

Re: [PATCH 1/5] Improve libstdc++-v3 async test

[Jonathan Wakely]

On 07/01/18 20:55 +0000, Mike Crowe wrote:
>Add tests for waiting for the future using both std::chrono::steady_clock
>and std::chrono::system_clock in preparation for dealing with those clocks
>properly in futex.cc.
>---
> libstdc++-v3/testsuite/30_threads/async/async.cc | 36 ++++++++++++++++++++++++
> 1 file changed, 36 insertions(+)
>
>diff --git a/libstdc++-v3/testsuite/30_threads/async/async.cc b/libstdc++-v3/testsuite/30_threads/async/async.cc
>index 8071cb133fc..7326c5f7cd6 100644
>--- a/libstdc++-v3/testsuite/30_threads/async/async.cc
>+++ b/libstdc++-v3/testsuite/30_threads/async/async.cc
>@@ -52,17 +52,53 @@ void test02()
>   VERIFY( status == std::future_status::timeout );
>   status = f1.wait_until(std::chrono::system_clock::now());
>   VERIFY( status == std::future_status::timeout );
>+  status = f1.wait_until(std::chrono::steady_clock::now());
>+  VERIFY( status == std::future_status::timeout );
>   l.unlock();  // allow async thread to proceed
>   f1.wait();   // wait for it to finish
>   status = f1.wait_for(std::chrono::milliseconds(0));
>   VERIFY( status == std::future_status::ready );
>   status = f1.wait_until(std::chrono::system_clock::now());
>   VERIFY( status == std::future_status::ready );
>+  status = f1.wait_until(std::chrono::steady_clock::now());
>+  VERIFY( status == std::future_status::ready );
>+}
>+
>+void work03()
>+{
>+    std::this_thread::sleep_for(std::chrono::seconds(15));

I don't think we want 15s - 20s pauses in the testsuite.

Could the sleep_for be 5s, with waits of 500ms, 1s, and then 10s, so
the expected wait is only 5s?

I don't think it's the end of the world if the test occasionally
fails on very loaded machines.


>+}
>+
>+// This test is slow in order to try and avoid failing on a loaded
>+// machine. Nevertheless, it could still fail if the kernel decides
>+// not to schedule us for several seconds. It also assumes that no-one
>+// will change CLOCK_REALTIME whilst the test is running.
>+template<typename CLOCK>
>+void test03()
>+{
>+  auto const start = CLOCK::now();
>+  future<void> f1 = async(launch::async, &work03);
>+  std::future_status status;
>+
>+  status = f1.wait_for(std::chrono::seconds(5));
>+  VERIFY( status == std::future_status::timeout );
>+
>+  status = f1.wait_until(start + std::chrono::seconds(10));
>+  VERIFY( status == std::future_status::timeout );
>+
>+  status = f1.wait_until(start + std::chrono::seconds(25));
>+  VERIFY( status == std::future_status::ready );
>+
>+  auto const elapsed = CLOCK::now() - start;
>+  VERIFY( elapsed >= std::chrono::seconds(15) );
>+  VERIFY( elapsed < std::chrono::seconds(20) );
> }
>
> int main()
> {
>   test01();
>   test02();
>+  test03<std::chrono::system_clock>();
>+  test03<std::chrono::steady_clock>();
>   return 0;
> }
>-- 
>2.11.0
>
>

[PATCH 3/5] libstdc++ futex: Support waiting on std::chrono::steady_clock directly

[Mike Crowe]

The user-visible effect of this change is for std::future::wait_until to
use CLOCK_MONOTONIC when passed a timeout of std::chrono::steady_clock
type. This makes it immune to any changes made to the system clock
CLOCK_REALTIME.

Add an overload of __atomic_futex_unsigned::_M_load_and_text_until_impl
that accepts a std::chrono::steady_clock, and correctly passes this through
to __atomic_futex_unsigned_base::_M_futex_wait_until_steady which uses
CLOCK_MONOTONIC for the timeout within the futex system call. These
functions are mostly just copies of the std::chrono::system_clock versions
with small tweaks.

Prior to this commit, a std::chrono::steady timeout would be converted via
std::chrono::system_clock which risks reducing or increasing the timeout if
someone changes CLOCK_REALTIME whilst the wait is happening. (The commit
immediately prior to this one increases the window of opportunity for that
from a short period during the calculation of a relative timeout, to the
entire duration of the wait.)

I believe that I've added this functionality in a way that it doesn't break
ABI compatibility, but that has made it more verbose and less type safe. I
believe that it would be better to maintain the timeout as an instance of
the correct clock type all the way down to a single _M_futex_wait_until
function with an overload for each clock. The current scheme of separating
out the seconds and nanoseconds early risks accidentally calling the wait
function for the wrong clock. Unfortunately, doing this would break code
that compiled against the old header.
---
 libstdc++-v3/include/bits/atomic_futex.h | 67 +++++++++++++++++++++++++++++++-
 libstdc++-v3/src/c++11/futex.cc          | 33 ++++++++++++++++
 2 files changed, 99 insertions(+), 1 deletion(-)

diff --git a/libstdc++-v3/include/bits/atomic_futex.h b/libstdc++-v3/include/bits/atomic_futex.h
index ad9437da4e2..78f39fb4048 100644
--- a/libstdc++-v3/include/bits/atomic_futex.h
+++ b/libstdc++-v3/include/bits/atomic_futex.h
@@ -52,11 +52,18 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 #if defined(_GLIBCXX_HAVE_LINUX_FUTEX) && ATOMIC_INT_LOCK_FREE > 1
   struct __atomic_futex_unsigned_base
   {
-    // Returns false iff a timeout occurred.
+    // __s and __ns are measured against CLOCK_REALTIME. Returns false
+    // iff a timeout occurred.
     bool
     _M_futex_wait_until(unsigned *__addr, unsigned __val, bool __has_timeout,
 	chrono::seconds __s, chrono::nanoseconds __ns);
 
+    // __s and __ns are measured against CLOCK_MONOTONIC. Returns
+    // false iff a timeout occurred.
+    bool
+    _M_futex_wait_until_steady(unsigned *__addr, unsigned __val, bool __has_timeout,
+	chrono::seconds __s, chrono::nanoseconds __ns);
+
     // This can be executed after the object has been destroyed.
     static void _M_futex_notify_all(unsigned* __addr);
   };
@@ -86,6 +93,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     // value if equal is false.
     // The assumed value is the caller's assumption about the current value
     // when making the call.
+    // __s and __ns are measured against CLOCK_REALTIME.
     unsigned
     _M_load_and_test_until(unsigned __assumed, unsigned __operand,
 	bool __equal, memory_order __mo, bool __has_timeout,
@@ -110,6 +118,36 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	}
     }
 
+    // If a timeout occurs, returns a current value after the timeout;
+    // otherwise, returns the operand's value if equal is true or a different
+    // value if equal is false.
+    // The assumed value is the caller's assumption about the current value
+    // when making the call.
+    // __s and __ns are measured against CLOCK_MONOTONIC.
+    unsigned
+    _M_load_and_test_until_steady(unsigned __assumed, unsigned __operand,
+	bool __equal, memory_order __mo, bool __has_timeout,
+	chrono::seconds __s, chrono::nanoseconds __ns)
+    {
+      for (;;)
+	{
+	  // Don't bother checking the value again because we expect the caller
+	  // to have done it recently.
+	  // memory_order_relaxed is sufficient because we can rely on just the
+	  // modification order (store_notify uses an atomic RMW operation too),
+	  // and the futex syscalls synchronize between themselves.
+	  _M_data.fetch_or(_Waiter_bit, memory_order_relaxed);
+	  bool __ret = _M_futex_wait_until_steady((unsigned*)(void*)&_M_data,
+					   __assumed | _Waiter_bit,
+					   __has_timeout, __s, __ns);
+	  // Fetch the current value after waiting (clears _Waiter_bit).
+	  __assumed = _M_load(__mo);
+	  if (!__ret || ((__operand == __assumed) == __equal))
+	    return __assumed;
+	  // TODO adapt wait time
+	}
+    }
+
     // Returns the operand's value if equal is true or a different value if
     // equal is false.
     // The assumed value is the caller's assumption about the current value
@@ -140,6 +178,19 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	  true, __s.time_since_epoch(), __ns);
     }
 
+    template<typename _Dur>
+    unsigned
+    _M_load_and_test_until_impl(unsigned __assumed, unsigned __operand,
+	bool __equal, memory_order __mo,
+	const chrono::time_point<std::chrono::steady_clock, _Dur>& __atime)
+    {
+      auto __s = chrono::time_point_cast<chrono::seconds>(__atime);
+      auto __ns = chrono::duration_cast<chrono::nanoseconds>(__atime - __s);
+      // XXX correct?
+      return _M_load_and_test_until_steady(__assumed, __operand, __equal, __mo,
+	  true, __s.time_since_epoch(), __ns);
+    }
+
   public:
 
     _GLIBCXX_ALWAYS_INLINE unsigned
@@ -200,6 +251,20 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       return (__i & ~_Waiter_bit) == __val;
     }
 
+    // Returns false iff a timeout occurred.
+    template<typename _Duration>
+    _GLIBCXX_ALWAYS_INLINE bool
+    _M_load_when_equal_until(unsigned __val, memory_order __mo,
+	const chrono::time_point<std::chrono::steady_clock, _Duration>& __atime)
+    {
+      unsigned __i = _M_load(__mo);
+      if ((__i & ~_Waiter_bit) == __val)
+	return true;
+      // TODO Spin-wait first.  Ignore effect on timeout.
+      __i = _M_load_and_test_until_impl(__i, __val, true, __mo, __atime);
+      return (__i & ~_Waiter_bit) == __val;
+    }
+
     _GLIBCXX_ALWAYS_INLINE void
     _M_store_notify_all(unsigned __val, memory_order __mo)
     {
diff --git a/libstdc++-v3/src/c++11/futex.cc b/libstdc++-v3/src/c++11/futex.cc
index 40ec7f9b0f7..8ade1fffefe 100644
--- a/libstdc++-v3/src/c++11/futex.cc
+++ b/libstdc++-v3/src/c++11/futex.cc
@@ -36,6 +36,7 @@
 // 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_monotonic_flag = 0;
 const unsigned futex_clock_realtime_flag = 256;
 const unsigned futex_bitset_match_any = ~0;
 const unsigned futex_wake_op = 1;
@@ -75,6 +76,38 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       }
   }
 
+  bool
+  __atomic_futex_unsigned_base::_M_futex_wait_until_steady(unsigned *__addr,
+      unsigned __val,
+      bool __has_timeout, chrono::seconds __s, chrono::nanoseconds __ns)
+  {
+    if (!__has_timeout)
+      {
+	// Ignore whether we actually succeeded to block because at worst,
+	// we will fall back to spin-waiting.  The only thing we could do
+	// here on errors is abort.
+	int ret __attribute__((unused));
+	ret = syscall (SYS_futex, __addr, futex_wait_op, __val, nullptr);
+	_GLIBCXX_DEBUG_ASSERT(ret == 0 || errno == EINTR || errno == EAGAIN);
+	return true;
+      }
+    else
+      {
+	struct timespec rt;
+	rt.tv_sec = __s.count();
+	rt.tv_nsec = __ns.count();
+
+	if (syscall (SYS_futex, __addr, futex_wait_bitset_op | futex_clock_monotonic_flag, __val, &rt, nullptr, futex_bitset_match_any) == -1)
+	  {
+	    _GLIBCXX_DEBUG_ASSERT(errno == EINTR || errno == EAGAIN
+				  || errno == ETIMEDOUT);
+	    if (errno == ETIMEDOUT)
+	      return false;
+	  }
+	return true;
+      }
+  }
+
   void
   __atomic_futex_unsigned_base::_M_futex_notify_all(unsigned* __addr)
   {
-- 
2.11.0

Re: [PATCH 0/5] Make std::future::wait_* use std::chrono::steady_clock when required

[Jonathan Wakely]

On 07/01/18 20:55 +0000, Mike Crowe wrote:
>This patch series was originally submitted back in September at
>https://gcc.gnu.org/ml/libstdc++/2017-09/msg00083.html which ended up
>as https://patchwork.ozlabs.org/cover/817379/ . The patches received
>no comments at all, which may mean that they are perfect or that they
>are so bad that no-one knew where to start with criticising them. It
>would be good to know which. :)

Sorry for the lack of review. Although not perfect I think the patches
look good, but I didn't feel entirely confident reviewing them at the
time, and let them slip through the cracks (we could do with more
reviewers for libstdc++ patches).

I'm taking another look now, and have asked the original author of the
__atomic_futex_unsigned code to look too, so thanks for the ping.

Re: [PATCH 0/5] Make std::future::wait_* use std::chrono::steady_clock when required

[Torvald Riegel]

On Sun, 2018-01-07 at 20:55 +0000, Mike Crowe wrote:
> This patch series was originally submitted back in September at
> https://gcc.gnu.org/ml/libstdc++/2017-09/msg00083.html which ended up
> as https://patchwork.ozlabs.org/cover/817379/ . The patches received
> no comments at all, which may mean that they are perfect or that they
> are so bad that no-one knew where to start with criticising them. It
> would be good to know which. :)
> 
> The patches are unchanged from last time, but I have corrected a typo
> in one of the commit messages. The original cover message follows.
> 
> This is a first attempt to make std::future::wait_until and
> std::future::wait_for make correct use of
> std::chrono::steady_clock/CLOCK_MONOTONIC. It also makes
> std::future::wait_until react to changes to CLOCK_REALTIME during the
> wait, but only when passed a std::chrono::system_clock time point.

I have comments on the design.

First, I don't think we should not change
__atomic_futex_unsigned_base::_M_futex_wait_until, as there's a risk
that we'll change behavior of existing applications that work as
expected.
Instead, ISTM we should additionally expose the two options we have at
the level of futexes:
* Relative timeout using CLOCK_MONOTONIC
* Absolute timeout using CLOCK_REALTIME (which will fall back to the
former on old kernels, which is fine I think).

Then we do the following translations from functions that programs would
call to the new futex functions:

1) wait_for is a loop in which we load the current time from the steady
clock, then call the relative futex wait, and if that returns for a
spurious reason (ie, neither timeout nor is the expected value present),
we reduce the prior relative amount by the difference between the time
before the futex wait and the current time.

2) wait_until using the steady clock is a loop similar to wait_for, just
that we additionally compute the initial relative timeout.

3) wait_until using the system clock is a loop that uses
absolute-timeout futex wait.

4) For wait_until using an unknown clock, I'd say that synching to the
system clock is the right approach.  Using wait_until indicates that the
programmer wanted to have a point in time, not a duration.

Does this work for you?

If so, could you provide a revised patch that uses this approach and
includes this approach in the documentation?
(Sorry for the lack of comments in the current code).

Re: [PATCH 0/5] Make std::future::wait_* use std::chrono::steady_clock when required

[Mike Crowe]

Hi Torvald,

Thanks for reviewing this change.

On Saturday 13 January 2018 at 16:29:57 +0100, Torvald Riegel wrote:
> On Sun, 2018-01-07 at 20:55 +0000, Mike Crowe wrote:
> > This is a first attempt to make std::future::wait_until and
> > std::future::wait_for make correct use of
> > std::chrono::steady_clock/CLOCK_MONOTONIC. It also makes
> > std::future::wait_until react to changes to CLOCK_REALTIME during the
> > wait, but only when passed a std::chrono::system_clock time point.
> 
> I have comments on the design.
> 
> First, I don't think we should not change
> __atomic_futex_unsigned_base::_M_futex_wait_until, as there's a risk
> that we'll change behavior of existing applications that work as
> expected.

I assume you mean "I don't think we should change" or "I think we should
not change"... :-)

The only way I can see that behaviour will change for existing programs is
when the system clock changes (i.e. when someone calls settimeofday.) In
the existing code, the maximum wait time is fixed once gettimeofday is
called to calculate the relative timeout. When using FUTEX_CLOCK_REALTIME,
the maximum wait can change based on changes to the system clock after that
point. It appears that glibc made this transition successfully and
currently uses FUTEX_CLOCK_REALTIME. I think that the new behaviour is
better than the old behaviour.

Or perhaps I've missed another possibility. Did you have another risk in
mind?

> Instead, ISTM we should additionally expose the two options we have at
> the level of futexes:
> * Relative timeout using CLOCK_MONOTONIC
> * Absolute timeout using CLOCK_REALTIME (which will fall back to the
> former on old kernels, which is fine I think).
> 
> Then we do the following translations from functions that programs would
> call to the new futex functions:
> 
> 1) wait_for is a loop in which we load the current time from the steady
> clock, then call the relative futex wait, and if that returns for a
> spurious reason (ie, neither timeout nor is the expected value present),
> we reduce the prior relative amount by the difference between the time
> before the futex wait and the current time.

If we're going to loop on a relative timeout it sounds safer to convert it
to an absolute (steady clock) timeout. That way we won't risk increasing
the timeout if the scheduler decides not to run us at an inopportune moment
between waits. _M_load_when_equal_for already does this.

_M_load_and_test_until already has a loop for spurious wakeup. I think that
it makes sense to only loop at one level. That loop relies on the timeout
being absolute, which is why my _M_load_and_test_until_steady also uses an
absolute timeout.

> 2) wait_until using the steady clock is a loop similar to wait_for, just
> that we additionally compute the initial relative timeout.

Clearly an absolute wait can be implemented in terms of a relative one and
vice-versa, but at least in my attempts to write them I find the code
easier to understand (and therefore get right) if the fundamental wait is
the absolute one and the relative one is implemented on top of it.

> 3) wait_until using the system clock is a loop that uses
> absolute-timeout futex wait.
> 
> 4) For wait_until using an unknown clock, I'd say that synching to the
> system clock is the right approach.  Using wait_until indicates that the
> programmer wanted to have a point in time, not a duration.

For my embedded and desktop point of view, the system clock should not be
trusted, can suddenly change in any direction and doesn't necessarily help
identify a point in real time. If we assume that the non-standard clock is
advancing steadily too, then steady_clock is a better match than
system_clock.

If you have a machine that has its system clock locked with PTP to an
atomic clock then you might think the opposite. However, even in that
situation you're reliant on steady_clock being reliable enough for short
periods of time anyway, because that shares the same local clock as
system_time.

> Does this work for you?

Not yet, but maybe there's parts that I don't fully understand the
reasoning behind.

> If so, could you provide a revised patch that uses this approach and
> includes this approach in the documentation?
> (Sorry for the lack of comments in the current code).

I'm definitely willing to improve the current code rather than just add to
it.

Mike.

Re: [PATCH 0/5] Make std::future::wait_* use std::chrono::steady_clock when required

[Mike Crowe]

On Sunday 14 January 2018 at 16:08:09 +0000, Mike Crowe wrote:
> Hi Torvald,
> 
> Thanks for reviewing this change.
> 
> On Saturday 13 January 2018 at 16:29:57 +0100, Torvald Riegel wrote:
> > On Sun, 2018-01-07 at 20:55 +0000, Mike Crowe wrote:
> > > This is a first attempt to make std::future::wait_until and
> > > std::future::wait_for make correct use of
> > > std::chrono::steady_clock/CLOCK_MONOTONIC. It also makes
> > > std::future::wait_until react to changes to CLOCK_REALTIME during the
> > > wait, but only when passed a std::chrono::system_clock time point.
> > 
> > I have comments on the design.
> > 
> > First, I don't think we should not change
> > __atomic_futex_unsigned_base::_M_futex_wait_until, as there's a risk
> > that we'll change behavior of existing applications that work as
> > expected.
> 
> I assume you mean "I don't think we should change" or "I think we should
> not change"... :-)
> 
> The only way I can see that behaviour will change for existing programs is
> when the system clock changes (i.e. when someone calls settimeofday.) In
> the existing code, the maximum wait time is fixed once gettimeofday is
> called to calculate the relative timeout. When using FUTEX_CLOCK_REALTIME,
> the maximum wait can change based on changes to the system clock after that
> point. It appears that glibc made this transition successfully and
> currently uses FUTEX_CLOCK_REALTIME. I think that the new behaviour is
> better than the old behaviour.
> 
> Or perhaps I've missed another possibility. Did you have another risk in
> mind?
> 
> > Instead, ISTM we should additionally expose the two options we have at
> > the level of futexes:
> > * Relative timeout using CLOCK_MONOTONIC
> > * Absolute timeout using CLOCK_REALTIME (which will fall back to the
> > former on old kernels, which is fine I think).
> > 
> > Then we do the following translations from functions that programs would
> > call to the new futex functions:
> > 
> > 1) wait_for is a loop in which we load the current time from the steady
> > clock, then call the relative futex wait, and if that returns for a
> > spurious reason (ie, neither timeout nor is the expected value present),
> > we reduce the prior relative amount by the difference between the time
> > before the futex wait and the current time.
> 
> If we're going to loop on a relative timeout it sounds safer to convert it
> to an absolute (steady clock) timeout. That way we won't risk increasing
> the timeout if the scheduler decides not to run us at an inopportune moment
> between waits. _M_load_when_equal_for already does this.
> 
> _M_load_and_test_until already has a loop for spurious wakeup. I think that
> it makes sense to only loop at one level. That loop relies on the timeout
> being absolute, which is why my _M_load_and_test_until_steady also uses an
> absolute timeout.
> 
> > 2) wait_until using the steady clock is a loop similar to wait_for, just
> > that we additionally compute the initial relative timeout.
> 
> Clearly an absolute wait can be implemented in terms of a relative one and
> vice-versa, but at least in my attempts to write them I find the code
> easier to understand (and therefore get right) if the fundamental wait is
> the absolute one and the relative one is implemented on top of it.

I had a quick go at implementing at least the first part of your design, as
I understood it. (I've kept the loops inside atomic_futex_unsigned - and I
think that you wanted to move them out to the client code.) I've not tested
it much.

I think that this implementation of _M_load_and_test_for is rather more
error-prone than my previous _M_load_and_test_until_steady. That's probably
partly because the type-safe duration has already been separated into seconds
and nanoseconds. It would be nice to push this separation as deeply as
possible in the code, but I'm afraid that would break ABI compatibility.

Thanks.

Mike.

--8<--

diff --git a/libstdc++-v3/include/bits/atomic_futex.h b/libstdc++-v3/include/bits/atomic_futex.h
index ad9437da4e2..fa4a4382c79 100644
--- a/libstdc++-v3/include/bits/atomic_futex.h
+++ b/libstdc++-v3/include/bits/atomic_futex.h
@@ -57,6 +57,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     _M_futex_wait_until(unsigned *__addr, unsigned __val, bool __has_timeout,
 	chrono::seconds __s, chrono::nanoseconds __ns);

+    // Returns false iff a timeout occurred.
+    bool
+    _M_futex_wait_for(unsigned *__addr, unsigned __val, bool __has_timeout,
+	chrono::seconds __s, chrono::nanoseconds __ns);
+
     // This can be executed after the object has been destroyed.
     static void _M_futex_notify_all(unsigned* __addr);
   };
@@ -110,6 +115,40 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	}
     }

+    // If a timeout occurs, returns a current value after the timeout;
+    // otherwise, returns the operand's value if equal is true or a different
+    // value if equal is false.
+    // The assumed value is the caller's assumption about the current value
+    // when making the call.
+    unsigned
+    _M_load_and_test_for(unsigned __assumed, unsigned __operand,
+	bool __equal, memory_order __mo, bool __has_timeout,
+	chrono::seconds __s, chrono::nanoseconds __ns)
+    {
+      auto __end_time = chrono::steady_clock::now() + chrono::seconds(__s) + chrono::nanoseconds(__ns);
+      for(;;)
+	{
+	  // Don't bother checking the value again because we expect the caller
+	  // to have done it recently.
+	  // memory_order_relaxed is sufficient because we can rely on just the
+	  // modification order (store_notify uses an atomic RMW operation too),
+	  // and the futex syscalls synchronize between themselves.
+	  _M_data.fetch_or(_Waiter_bit, memory_order_relaxed);
+	  bool __ret = _M_futex_wait_for((unsigned*)(void*)&_M_data,
+					   __assumed | _Waiter_bit,
+					   __has_timeout, __s, __ns);
+	  // Fetch the current value after waiting (clears _Waiter_bit).
+	  __assumed = _M_load(__mo);
+	  if (!__ret || ((__operand == __assumed) == __equal))
+	    return __assumed;
+
+	  const auto __remaining = __end_time - chrono::steady_clock::now();
+	  __s = chrono::duration_cast<chrono::seconds>(__remaining);
+	  __ns = chrono::duration_cast<chrono::nanoseconds>(__remaining - __s);
+	}
+      return __assumed;
+    }
+
     // Returns the operand's value if equal is true or a different value if
     // equal is false.
     // The assumed value is the caller's assumption about the current value
@@ -168,8 +207,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       _M_load_when_equal_for(unsigned __val, memory_order __mo,
 	  const chrono::duration<_Rep, _Period>& __rtime)
       {
-	return _M_load_when_equal_until(__val, __mo,
-					__clock_t::now() + __rtime);
+	unsigned __i = _M_load(__mo);
+	if ((__i & ~_Waiter_bit) == __val)
+	  return true;
+	auto __s = chrono::duration_cast<chrono::seconds>(__rtime);
+	auto __ns = chrono::duration_cast<chrono::nanoseconds>(__rtime - __s);
+	__i = _M_load_and_test_for(__i, __val, true, __mo, true, __s, __ns);
+	return (__i & ~_Waiter_bit) == __val;
       }

     // Returns false iff a timeout occurred.
diff --git a/libstdc++-v3/src/c++11/futex.cc b/libstdc++-v3/src/c++11/futex.cc
index f5000aa77b3..1b5fe480209 100644
--- a/libstdc++-v3/src/c++11/futex.cc
+++ b/libstdc++-v3/src/c++11/futex.cc
@@ -84,6 +84,38 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       }
   }

+  bool
+  __atomic_futex_unsigned_base::_M_futex_wait_for(unsigned *__addr,
+      unsigned __val,
+      bool __has_timeout, chrono::seconds __s, chrono::nanoseconds __ns)
+  {
+    if (!__has_timeout)
+      {
+	// Ignore whether we actually succeeded to block because at worst,
+	// we will fall back to spin-waiting.  The only thing we could do
+	// here on errors is abort.
+	int ret __attribute__((unused));
+	ret = syscall (SYS_futex, __addr, futex_wait_op, __val, nullptr);
+	_GLIBCXX_DEBUG_ASSERT(ret == 0 || errno == EINTR || errno == EAGAIN);
+	return true;
+      }
+    else
+      {
+	struct timespec rt;
+	rt.tv_sec = __s.count();
+	rt.tv_nsec = __ns.count();
+
+	if (syscall (SYS_futex, __addr, futex_wait_op, __val, &rt) == -1)
+	  {
+	    _GLIBCXX_DEBUG_ASSERT(errno == EINTR || errno == EAGAIN
+				  || errno == ETIMEDOUT);
+	    if (errno == ETIMEDOUT)
+	      return false;
+	  }
+	return true;
+      }
+  }
+
   void
   __atomic_futex_unsigned_base::_M_futex_notify_all(unsigned* __addr)
   {
--
2.11.0

Re: [PATCH 0/5] Make std::future::wait_* use std::chrono::steady_clock when required

[Mike Crowe]

On Sunday 14 January 2018 at 20:44:10 +0000, Mike Crowe wrote:
> On Sunday 14 January 2018 at 16:08:09 +0000, Mike Crowe wrote:
> > Hi Torvald,
> > 
> > Thanks for reviewing this change.
> > 
> > On Saturday 13 January 2018 at 16:29:57 +0100, Torvald Riegel wrote:
> > > On Sun, 2018-01-07 at 20:55 +0000, Mike Crowe wrote:
> > > > This is a first attempt to make std::future::wait_until and
> > > > std::future::wait_for make correct use of
> > > > std::chrono::steady_clock/CLOCK_MONOTONIC. It also makes
> > > > std::future::wait_until react to changes to CLOCK_REALTIME during the
> > > > wait, but only when passed a std::chrono::system_clock time point.
> > > 
> > > I have comments on the design.
> > > 
> > > First, I don't think we should not change
> > > __atomic_futex_unsigned_base::_M_futex_wait_until, as there's a risk
> > > that we'll change behavior of existing applications that work as
> > > expected.
> > 
> > I assume you mean "I don't think we should change" or "I think we should
> > not change"... :-)
> > 
> > The only way I can see that behaviour will change for existing programs is
> > when the system clock changes (i.e. when someone calls settimeofday.) In
> > the existing code, the maximum wait time is fixed once gettimeofday is
> > called to calculate the relative timeout. When using FUTEX_CLOCK_REALTIME,
> > the maximum wait can change based on changes to the system clock after that
> > point. It appears that glibc made this transition successfully and
> > currently uses FUTEX_CLOCK_REALTIME. I think that the new behaviour is
> > better than the old behaviour.
> > 
> > Or perhaps I've missed another possibility. Did you have another risk in
> > mind?
> > 
> > > Instead, ISTM we should additionally expose the two options we have at
> > > the level of futexes:
> > > * Relative timeout using CLOCK_MONOTONIC
> > > * Absolute timeout using CLOCK_REALTIME (which will fall back to the
> > > former on old kernels, which is fine I think).
> > > 
> > > Then we do the following translations from functions that programs would
> > > call to the new futex functions:
> > > 
> > > 1) wait_for is a loop in which we load the current time from the steady
> > > clock, then call the relative futex wait, and if that returns for a
> > > spurious reason (ie, neither timeout nor is the expected value present),
> > > we reduce the prior relative amount by the difference between the time
> > > before the futex wait and the current time.
> > 
> > If we're going to loop on a relative timeout it sounds safer to convert it
> > to an absolute (steady clock) timeout. That way we won't risk increasing
> > the timeout if the scheduler decides not to run us at an inopportune moment
> > between waits. _M_load_when_equal_for already does this.
> > 
> > _M_load_and_test_until already has a loop for spurious wakeup. I think that
> > it makes sense to only loop at one level. That loop relies on the timeout
> > being absolute, which is why my _M_load_and_test_until_steady also uses an
> > absolute timeout.
> > 
> > > 2) wait_until using the steady clock is a loop similar to wait_for, just
> > > that we additionally compute the initial relative timeout.
> > 
> > Clearly an absolute wait can be implemented in terms of a relative one and
> > vice-versa, but at least in my attempts to write them I find the code
> > easier to understand (and therefore get right) if the fundamental wait is
> > the absolute one and the relative one is implemented on top of it.
> 
> I had a quick go at implementing at least the first part of your design, as
> I understood it. (I've kept the loops inside atomic_futex_unsigned - and I
> think that you wanted to move them out to the client code.) I've not tested
> it much.
> 
> I think that this implementation of _M_load_and_test_for is rather more
> error-prone than my previous _M_load_and_test_until_steady. That's probably
> partly because the type-safe duration has already been separated into seconds
> and nanoseconds. It would be nice to push this separation as deeply as
> possible in the code, but I'm afraid that would break ABI compatibility.
> 
> Thanks.
> 
> Mike.
> 
> --8<--
> 
> diff --git a/libstdc++-v3/include/bits/atomic_futex.h b/libstdc++-v3/include/bits/atomic_futex.h
> index ad9437da4e2..fa4a4382c79 100644
> --- a/libstdc++-v3/include/bits/atomic_futex.h
> +++ b/libstdc++-v3/include/bits/atomic_futex.h
> @@ -57,6 +57,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>      _M_futex_wait_until(unsigned *__addr, unsigned __val, bool __has_timeout,
>  	chrono::seconds __s, chrono::nanoseconds __ns);
> 
> +    // Returns false iff a timeout occurred.
> +    bool
> +    _M_futex_wait_for(unsigned *__addr, unsigned __val, bool __has_timeout,
> +	chrono::seconds __s, chrono::nanoseconds __ns);
> +
>      // This can be executed after the object has been destroyed.
>      static void _M_futex_notify_all(unsigned* __addr);
>    };
> @@ -110,6 +115,40 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>  	}
>      }
> 
> +    // If a timeout occurs, returns a current value after the timeout;
> +    // otherwise, returns the operand's value if equal is true or a different
> +    // value if equal is false.
> +    // The assumed value is the caller's assumption about the current value
> +    // when making the call.
> +    unsigned
> +    _M_load_and_test_for(unsigned __assumed, unsigned __operand,
> +	bool __equal, memory_order __mo, bool __has_timeout,
> +	chrono::seconds __s, chrono::nanoseconds __ns)
> +    {
> +      auto __end_time = chrono::steady_clock::now() + chrono::seconds(__s) + chrono::nanoseconds(__ns);
> +      for(;;)
> +	{
> +	  // Don't bother checking the value again because we expect the caller
> +	  // to have done it recently.
> +	  // memory_order_relaxed is sufficient because we can rely on just the
> +	  // modification order (store_notify uses an atomic RMW operation too),
> +	  // and the futex syscalls synchronize between themselves.
> +	  _M_data.fetch_or(_Waiter_bit, memory_order_relaxed);
> +	  bool __ret = _M_futex_wait_for((unsigned*)(void*)&_M_data,
> +					   __assumed | _Waiter_bit,
> +					   __has_timeout, __s, __ns);
> +	  // Fetch the current value after waiting (clears _Waiter_bit).
> +	  __assumed = _M_load(__mo);
> +	  if (!__ret || ((__operand == __assumed) == __equal))
> +	    return __assumed;
> +
> +	  const auto __remaining = __end_time - chrono::steady_clock::now();
> +	  __s = chrono::duration_cast<chrono::seconds>(__remaining);
> +	  __ns = chrono::duration_cast<chrono::nanoseconds>(__remaining - __s);
> +	}
> +      return __assumed;
> +    }
> +
>      // Returns the operand's value if equal is true or a different value if
>      // equal is false.
>      // The assumed value is the caller's assumption about the current value
> @@ -168,8 +207,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>        _M_load_when_equal_for(unsigned __val, memory_order __mo,
>  	  const chrono::duration<_Rep, _Period>& __rtime)
>        {
> -	return _M_load_when_equal_until(__val, __mo,
> -					__clock_t::now() + __rtime);
> +	unsigned __i = _M_load(__mo);
> +	if ((__i & ~_Waiter_bit) == __val)
> +	  return true;
> +	auto __s = chrono::duration_cast<chrono::seconds>(__rtime);
> +	auto __ns = chrono::duration_cast<chrono::nanoseconds>(__rtime - __s);
> +	__i = _M_load_and_test_for(__i, __val, true, __mo, true, __s, __ns);
> +	return (__i & ~_Waiter_bit) == __val;
>        }
> 
>      // Returns false iff a timeout occurred.
> diff --git a/libstdc++-v3/src/c++11/futex.cc b/libstdc++-v3/src/c++11/futex.cc
> index f5000aa77b3..1b5fe480209 100644
> --- a/libstdc++-v3/src/c++11/futex.cc
> +++ b/libstdc++-v3/src/c++11/futex.cc
> @@ -84,6 +84,38 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>        }
>    }
> 
> +  bool
> +  __atomic_futex_unsigned_base::_M_futex_wait_for(unsigned *__addr,
> +      unsigned __val,
> +      bool __has_timeout, chrono::seconds __s, chrono::nanoseconds __ns)
> +  {
> +    if (!__has_timeout)
> +      {
> +	// Ignore whether we actually succeeded to block because at worst,
> +	// we will fall back to spin-waiting.  The only thing we could do
> +	// here on errors is abort.
> +	int ret __attribute__((unused));
> +	ret = syscall (SYS_futex, __addr, futex_wait_op, __val, nullptr);
> +	_GLIBCXX_DEBUG_ASSERT(ret == 0 || errno == EINTR || errno == EAGAIN);
> +	return true;
> +      }
> +    else
> +      {
> +	struct timespec rt;
> +	rt.tv_sec = __s.count();
> +	rt.tv_nsec = __ns.count();
> +
> +	if (syscall (SYS_futex, __addr, futex_wait_op, __val, &rt) == -1)
> +	  {
> +	    _GLIBCXX_DEBUG_ASSERT(errno == EINTR || errno == EAGAIN
> +				  || errno == ETIMEDOUT);
> +	    if (errno == ETIMEDOUT)
> +	      return false;
> +	  }
> +	return true;
> +      }
> +  }
> +
>    void
>    __atomic_futex_unsigned_base::_M_futex_notify_all(unsigned* __addr)
>    {
> --
> 2.11.0
> 

Hi Torvald and Jonathan,

Do you have any comments on my replies?

Thanks.

Mike.