Re: [PATCH v5 6/8] libstdc++ atomic_futex: Avoid rounding errors in std::future::wait_* [PR91486]

[Jonathan Wakely <jwakely@redhat.com>]

[-- Attachment #1: Type: text/plain, Size: 5354 bytes --]

On 11/09/20 15:41 +0100, Jonathan Wakely wrote:
>On 29/05/20 07:17 +0100, Mike Crowe via Libstdc++ wrote:
>>Convert the specified duration to the target clock's duration type
>>before adding it to the current time in
>>__atomic_futex_unsigned::_M_load_when_equal_for and
>>_M_load_when_equal_until.  This removes the risk of the timeout being
>>rounded down to the current time resulting in there being no wait at
>>all when the duration type lacks sufficient precision to hold the
>>steady_clock current time.
>>
>>Rather than using the style of fix from PR68519, let's expose the C++17
>>std::chrono::ceil function as std::chrono::__detail::ceil so that it can
>>be used in code compiled with earlier standards versions and simplify
>>the fix. This was suggested by John Salmon in
>>https://gcc.gnu.org/bugzilla/show_bug.cgi?id=91486#c5 .
>>
>>This problem has become considerably less likely to trigger since I
>>switched the __atomic__futex_unsigned::__clock_t reference clock from
>>system_clock to steady_clock and added the loop, but the consequences of
>>triggering it have changed too.
>>
>>By my calculations it takes just over 194 days from the epoch for the
>>current time not to be representable in a float. This means that
>>system_clock is always subject to the problem (with the standard 1970
>>epoch) whereas steady_clock with float duration only runs out of
>>resolution machine has been running for that long (assuming the Linux
>>implementation of CLOCK_MONOTONIC.)
>>
>>The recently-added loop in
>>__atomic_futex_unsigned::_M_load_when_equal_until turns this scenario
>>into a busy wait.
>>
>>Unfortunately the combination of both of these things means that it's
>>not possible to write a test case for this occurring in
>>_M_load_when_equal_until as it stands.
>>
>>	* libstdc++-v3/include/std/chrono: (__detail::ceil) Move
>>         implementation of std::chrono::ceil into private namespace so
>>         that it's available to pre-C++17 code.
>>
>>	* libstdc++-v3/include/bits/atomic_futex.h:
>>	  (__atomic_futex_unsigned::_M_load_when_equal_for,
>>	  __atomic_futex_unsigned::_M_load_when_equal_until): Use
>>	  __detail::ceil to convert delta to the reference clock
>>	  duration type to avoid resolution problems
>>
>>	* libstdc++-v3/testsuite/30_threads/async/async.cc: (test_pr91486):
>>         New test for __atomic_futex_unsigned::_M_load_when_equal_for.
>>---
>>libstdc++-v3/include/bits/atomic_futex.h         |  6 +++--
>>libstdc++-v3/include/std/chrono                  | 19 +++++++++++++----
>>libstdc++-v3/testsuite/30_threads/async/async.cc | 15 +++++++++++++-
>>3 files changed, 34 insertions(+), 6 deletions(-)
>>
>>diff --git a/libstdc++-v3/include/bits/atomic_futex.h b/libstdc++-v3/include/bits/atomic_futex.h
>>index 5f95ade..aa137a7 100644
>>--- a/libstdc++-v3/include/bits/atomic_futex.h
>>+++ b/libstdc++-v3/include/bits/atomic_futex.h
>>@@ -219,8 +219,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>>      _M_load_when_equal_for(unsigned __val, memory_order __mo,
>>	  const chrono::duration<_Rep, _Period>& __rtime)
>>      {
>>+	using __dur = typename __clock_t::duration;
>>	return _M_load_when_equal_until(__val, __mo,
>>-					__clock_t::now() + __rtime);
>>+		    __clock_t::now() + chrono::__detail::ceil<__dur>(__rtime));
>>      }
>>
>>    // Returns false iff a timeout occurred.
>>@@ -233,7 +234,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>>	do {
>>	  const __clock_t::time_point __s_entry = __clock_t::now();
>>	  const auto __delta = __atime - __c_entry;
>>-	  const auto __s_atime = __s_entry + __delta;
>>+	  const auto __s_atime = __s_entry +
>>+	      chrono::__detail::ceil<_Duration>(__delta);

I'm testing the attached patch to fix the C++11 constexpr error, but
while re-looking at the uses of __detail::ceil I noticed this is using
_Duration as the target type. Shouldn't that be __clock_t::duration
instead? Why do we care about the duration of the user's time_point
here, rather than the preferred duration of the clock we're about to
wait against?


>>	  if (_M_load_when_equal_until(__val, __mo, __s_atime))
>>	    return true;
>>	  __c_entry = _Clock::now();
>>diff --git a/libstdc++-v3/include/std/chrono b/libstdc++-v3/include/std/chrono
>>index 6d78f32..4257c7c 100644
>>--- a/libstdc++-v3/include/std/chrono
>>+++ b/libstdc++-v3/include/std/chrono
>>@@ -299,6 +299,20 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>>#endif
>>#endif // C++20
>>
>>+    // We want to use ceil even when compiling for earlier standards versions
>>+    namespace __detail
>>+    {
>>+      template<typename _ToDur, typename _Rep, typename _Period>
>>+        constexpr __enable_if_is_duration<_ToDur>
>>+        ceil(const duration<_Rep, _Period>& __d)
>>+        {
>>+	  auto __to = chrono::duration_cast<_ToDur>(__d);
>>+	  if (__to < __d)
>>+	    return __to + _ToDur{1};
>>+	  return __to;
>>+	}
>>+    }
>>+
>>#if __cplusplus >= 201703L
>># define __cpp_lib_chrono 201611
>>
>>@@ -316,10 +330,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>>      constexpr __enable_if_is_duration<_ToDur>
>>      ceil(const duration<_Rep, _Period>& __d)
>>      {
>>-	auto __to = chrono::duration_cast<_ToDur>(__d);
>>-	if (__to < __d)
>>-	  return __to + _ToDur{1};
>>-	return __to;
>>+	return __detail::ceil<_ToDur>(__d);
>
>This isn't valid in C++11, a constexpr function needs to be just a
>return statement. Fix incoming ...




[-- Attachment #2: patch.txt --]
[-- Type: text/x-patch, Size: 3379 bytes --]

commit 2c56e931c694f98ba77c02163b69a62242f23a3b
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Fri Sep 11 18:09:46 2020

    libstdc++: Fix chrono::__detail::ceil to work with C++11
    
    In C++11 constexpr functions can only have a return statement, so we
    need to fix __detail::ceil to make it valid in C++11. This can be done
    by moving the comparison and increment into a new function, __ceil_impl,
    and calling that with the result of the duration_cast.
    
    This would mean the standard C++17 std::chrono::ceil function would make
    two further calls, which would add too much overhead when not inlined.
    For C++17 and later use a using-declaration to add chrono::ceil to
    namespace __detail. For C++11 and C++14 define chrono::__detail::__ceil
    as a C++11-compatible constexpr function template.
    
    libstdc++-v3/ChangeLog:
    
            * include/std/chrono [C++17] (chrono::__detail::ceil): Add
            using declaration to make chrono::ceil available for internal
            use with a consistent name.
            (chrono::__detail::__ceil_impl): New function template.
            (chrono::__detail::ceil): Use __ceil_impl to compare and
            increment the value. Remove SFINAE constraint.

diff --git a/libstdc++-v3/include/std/chrono b/libstdc++-v3/include/std/chrono
index 893d1f6b2c9..2db2b7d0edc 100644
--- a/libstdc++-v3/include/std/chrono
+++ b/libstdc++-v3/include/std/chrono
@@ -329,20 +329,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 #endif
 #endif // C++20
 
-    // We want to use ceil even when compiling for earlier standards versions
-    namespace __detail
-    {
-      template<typename _ToDur, typename _Rep, typename _Period>
-	constexpr __enable_if_is_duration<_ToDur>
-	ceil(const duration<_Rep, _Period>& __d)
-	{
-	  auto __to = chrono::duration_cast<_ToDur>(__d);
-	  if (__to < __d)
-	    return __to + _ToDur{1};
-	  return __to;
-	}
-    }
-
 #if __cplusplus >= 201703L
 # define __cpp_lib_chrono 201611
 
@@ -360,7 +346,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       constexpr __enable_if_is_duration<_ToDur>
       ceil(const duration<_Rep, _Period>& __d)
       {
-	return __detail::ceil<_ToDur>(__d);
+	auto __to = chrono::duration_cast<_ToDur>(__d);
+	if (__to < __d)
+	  return __to - _ToDur{1};
+	return __to;
       }
 
     template <typename _ToDur, typename _Rep, typename _Period>
@@ -394,6 +383,32 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	  return __d;
 	return -__d;
       }
+
+    // Make chrono::ceil<D> also usable as chrono::__detail::ceil<D>.
+    namespace __detail { using chrono::ceil; }
+
+#else // ! C++17
+
+    // We want to use ceil even when compiling for earlier standards versions.
+    // C++11 only allows a single statement in a constexpr function, so we
+    // need to move the comparison into a separate function, __ceil_impl.
+    namespace __detail
+    {
+      template<typename _Tp, typename _Up>
+	constexpr _Tp
+	__ceil_impl(const _Tp& __t, const _Up& __u)
+	{
+	  return (__t < __u) ? (__t + _Tp{1}) : __t;
+	}
+
+      // C++11-friendly version of std::chrono::ceil<D> for internal use.
+      template<typename _ToDur, typename _Rep, typename _Period>
+	constexpr _ToDur
+	ceil(const duration<_Rep, _Period>& __d)
+	{
+	  return __detail::__ceil_impl(chrono::duration_cast<_ToDur>(__d), __d);
+	}
+    }
 #endif // C++17
 
     /// duration_values