Implement the standard for timeouts for std::condition_variable

[tomcherry]

Summary

The C++ standard calls for wait_for() to use steady clock and
wait_until() to use the clock that is provided as an argument. This
is not currently done in libc++ and is not possible with the pthreads
API, however it is possible with the underlying futex system call.

This change re-implements std::condition_variable with a tweaked
version of the implementation of pthread_cond_* from Android bionic to
support the correct semantics.

Bug: 35756266

[tomcherry]

This is mostly an RFC. The underlying issue is that we cannot use timed waits based on CLOCK_REALTIME on Android. In trying to fix that, I figured I might as well try implementing the standard as described, though I understand that there'd be resistance to such a re-implementation.

[tomcherry]

See https://reviews.llvm.org/D65339

include/__mutex_base

 // -*- C++ -*-
 //===----------------------------------------------------------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is dual licensed under the MIT and the University of Illinois Open
 // Source Licenses. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef _LIBCPP___MUTEX_BASE
 #define _LIBCPP___MUTEX_BASE
 
+#include <atomic>
 #include <__config>
 #include <chrono>
 #include <system_error>
 #include <__threading_support>
 
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
_LIBCPP_DECLARE_STRONG_ENUM(cv_status)
     no_timeout,
     timeout
 };
 _LIBCPP_DECLARE_STRONG_ENUM_EPILOG(cv_status)
 
 class _LIBCPP_TYPE_VIS condition_variable
 {
 #ifndef _LIBCPP_CXX03_LANG
-    __libcpp_condvar_t __cv_ = _LIBCPP_CONDVAR_INITIALIZER;
+    atomic_uint __state{0};
 #else
-    __libcpp_condvar_t __cv_;
+    atomic_uint __state;
 #endif
-
 public:
     _LIBCPP_INLINE_VISIBILITY
 #ifndef _LIBCPP_CXX03_LANG
     constexpr condition_variable() _NOEXCEPT = default;
 #else
-    condition_variable() _NOEXCEPT {__cv_ = (__libcpp_condvar_t)_LIBCPP_CONDVAR_INITIALIZER;}
+    condition_variable() _NOEXCEPT {atomic_init(&__state, (unsigned int)0);}
 #endif
     ~condition_variable();
 
 private:
     condition_variable(const condition_variable&); // = delete;
     condition_variable& operator=(const condition_variable&); // = delete;
 
 public:
     void notify_one() _NOEXCEPT;
     void notify_all() _NOEXCEPT;
 
     void wait(unique_lock<mutex>& __lk) _NOEXCEPT;
     template <class _Predicate>
         _LIBCPP_METHOD_TEMPLATE_IMPLICIT_INSTANTIATION_VIS
         void wait(unique_lock<mutex>& __lk, _Predicate __pred);
 
+    template <class _Duration>
+        _LIBCPP_METHOD_TEMPLATE_IMPLICIT_INSTANTIATION_VIS
+        cv_status
+        wait_until(unique_lock<mutex>& __lk,
+                   const chrono::time_point<chrono::system_clock, _Duration>& __t);
+
+    template <class _Duration>
+        _LIBCPP_METHOD_TEMPLATE_IMPLICIT_INSTANTIATION_VIS
+        cv_status
+        wait_until(unique_lock<mutex>& __lk,
+                   const chrono::time_point<chrono::steady_clock, _Duration>& __t);
+
     template <class _Clock, class _Duration>
         _LIBCPP_METHOD_TEMPLATE_IMPLICIT_INSTANTIATION_VIS
          cv_status
          wait_until(unique_lock<mutex>& __lk,
                     const chrono::time_point<_Clock, _Duration>& __t);
 
     template <class _Clock, class _Duration, class _Predicate>
         _LIBCPP_METHOD_TEMPLATE_IMPLICIT_INSTANTIATION_VIS
         bool
         wait_until(unique_lock<mutex>& __lk,
                    const chrono::time_point<_Clock, _Duration>& __t,
                    _Predicate __pred);
 
     template <class _Rep, class _Period>
         _LIBCPP_METHOD_TEMPLATE_IMPLICIT_INSTANTIATION_VIS
         cv_status
         wait_for(unique_lock<mutex>& __lk,
                  const chrono::duration<_Rep, _Period>& __d);
 
     template <class _Rep, class _Period, class _Predicate>
         bool
         _LIBCPP_INLINE_VISIBILITY
         wait_for(unique_lock<mutex>& __lk,
                  const chrono::duration<_Rep, _Period>& __d,
                  _Predicate __pred);
 
-    typedef __libcpp_condvar_t* native_handle_type;
-    _LIBCPP_INLINE_VISIBILITY native_handle_type native_handle() {return &__cv_;}
+    typedef atomic_uint* native_handle_type;
+    _LIBCPP_INLINE_VISIBILITY native_handle_type native_handle() {
+        return reinterpret_cast<native_handle_type>(&__state);
+    }
 
 private:
-    void __do_timed_wait(unique_lock<mutex>& __lk,
-       chrono::time_point<chrono::system_clock, chrono::nanoseconds>) _NOEXCEPT;
+    int __wait(unique_lock<mutex>& __lk, chrono::nanoseconds __t,
+               bool __rel_timeout, bool __realtime) _NOEXCEPT;
+    void __pulse(int thread_count) _NOEXCEPT;
+    int __futex(volatile void* ftx, int op, int value,
+                const struct timespec* timeout, int bitset) _NOEXCEPT;
 };
 #endif // !_LIBCPP_HAS_NO_THREADS
 
-template <class _To, class _Rep, class _Period>
-inline _LIBCPP_INLINE_VISIBILITY
-typename enable_if
-<
-    chrono::__is_duration<_To>::value,
-    _To
->::type
-__ceil(chrono::duration<_Rep, _Period> __d)
-{
-    using namespace chrono;
-    _To __r = duration_cast<_To>(__d);
-    if (__r < __d)
-        ++__r;
-    return __r;
-}
-
 #ifndef _LIBCPP_HAS_NO_THREADS
 template <class _Predicate>
 void
 condition_variable::wait(unique_lock<mutex>& __lk, _Predicate __pred)
 {
     while (!__pred())
         wait(__lk);
 }
 
+template <class _Duration>
+cv_status
+condition_variable::wait_until(unique_lock<mutex>& __lk,
+                               const chrono::time_point<chrono::system_clock, _Duration>& __t)
+{
+    auto __tp = chrono::time_point_cast<chrono::nanoseconds>(__t);
+    auto duration = __tp.time_since_epoch();
+    return __wait(__lk, duration, false, true) == -ETIMEDOUT ?
+        cv_status::timeout : cv_status::no_timeout;
+}
+
+template <class _Duration>
+cv_status
+condition_variable::wait_until(unique_lock<mutex>& __lk,
+                               const chrono::time_point<chrono::steady_clock, _Duration>& __t)
+{
+    auto __tp = chrono::time_point_cast<chrono::nanoseconds>(__t);
+    auto duration = __tp.time_since_epoch();
+    return __wait(__lk, duration, false, false) == -ETIMEDOUT ?
+        cv_status::timeout : cv_status::no_timeout;
+}
+
 template <class _Clock, class _Duration>
 cv_status
 condition_variable::wait_until(unique_lock<mutex>& __lk,
                                const chrono::time_point<_Clock, _Duration>& __t)
 {
     using namespace chrono;
     wait_for(__lk, __t - _Clock::now());
     return _Clock::now() < __t ? cv_status::no_timeout : cv_status::timeout;
condition_variable::wait_until(unique_lock<mutex>& __lk,
     return true;
 }
 
 template <class _Rep, class _Period>
 cv_status
 condition_variable::wait_for(unique_lock<mutex>& __lk,
                              const chrono::duration<_Rep, _Period>& __d)
 {
-    using namespace chrono;
     if (__d <= __d.zero())
         return cv_status::timeout;
-    typedef time_point<system_clock, duration<long double, nano> > __sys_tpf;
-    typedef time_point<system_clock, nanoseconds> __sys_tpi;
-    __sys_tpf _Max = __sys_tpi::max();
-    steady_clock::time_point __c_now = steady_clock::now();
-    system_clock::time_point __s_now = system_clock::now();
-    if (_Max - __d > __s_now)
-        __do_timed_wait(__lk, __s_now + __ceil<nanoseconds>(__d));
-    else
-        __do_timed_wait(__lk, __sys_tpi::max());
-    return steady_clock::now() - __c_now < __d ? cv_status::no_timeout :
-                                                 cv_status::timeout;
+
+    auto duration_ns = chrono::duration_cast<chrono::nanoseconds>(__d);
+    if (duration_ns < __d) duration_ns++;
+
+    return __wait(__lk, duration_ns, true, false)  == -ETIMEDOUT ?
+        cv_status::timeout : cv_status::no_timeout;
 }
 
 template <class _Rep, class _Period, class _Predicate>
 inline
 bool
 condition_variable::wait_for(unique_lock<mutex>& __lk,
                              const chrono::duration<_Rep, _Period>& __d,
                              _Predicate __pred)

src/condition_variable.cpp

 //===-------------------- condition_variable.cpp --------------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is dual licensed under the MIT and the University of Illinois Open
 // Source Licenses. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "__config"
 
 #ifndef _LIBCPP_HAS_NO_THREADS
 
+#include <linux/futex.h>
+#include <sys/syscall.h>
+#include <unistd.h>
+
 #include "condition_variable"
 #include "thread"
 #include "system_error"
 #include "__undef_macros"
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 condition_variable::~condition_variable()
 {
-    __libcpp_condvar_destroy(&__cv_);
+    atomic_store_explicit(&__state, 0xdeadc04d, memory_order_relaxed);
+}
+
+void
+condition_variable::__pulse(int thread_count) _NOEXCEPT
+{
+    _LIBCPP_CONSTEXPR unsigned int kCondCounterStep = 0x0004;
+    atomic_fetch_add_explicit(&__state, kCondCounterStep, memory_order_relaxed);
+    __futex(&__state, FUTEX_WAKE_PRIVATE, thread_count, nullptr, 0);
 }
 
 void
 condition_variable::notify_one() _NOEXCEPT
 {
-    __libcpp_condvar_signal(&__cv_);
+    __pulse(1);
 }
 
 void
 condition_variable::notify_all() _NOEXCEPT
 {
-    __libcpp_condvar_broadcast(&__cv_);
+    __pulse(numeric_limits<int>::max());
 }
 
 void
 condition_variable::wait(unique_lock<mutex>& lk) _NOEXCEPT
 {
-    if (!lk.owns_lock())
-        __throw_system_error(EPERM,
-                                  "condition_variable::wait: mutex not locked");
-    int ec = __libcpp_condvar_wait(&__cv_, lk.mutex()->native_handle());
-    if (ec)
-        __throw_system_error(ec, "condition_variable wait failed");
+    __wait(lk, chrono::nanoseconds(0), false, false);
+}
+
+int
+condition_variable::__wait(unique_lock<mutex>& __lk, chrono::nanoseconds __t,
+                           bool __rel_timeout, bool __realtime) _NOEXCEPT
+{
+    int op;
+    int val3;
+
+    if (__t.count() == 0 || __rel_timeout) {
+        op = FUTEX_WAIT_PRIVATE;
+        val3 = 0;
+    } else if (__realtime) {
+        op = FUTEX_WAIT_BITSET_PRIVATE | FUTEX_CLOCK_REALTIME;
+        val3 = FUTEX_BITSET_MATCH_ANY;
+    } else {
+        op = FUTEX_WAIT_BITSET_PRIVATE;
+        val3 = FUTEX_BITSET_MATCH_ANY;
     }
 
-void
-condition_variable::__do_timed_wait(unique_lock<mutex>& lk,
-     chrono::time_point<chrono::system_clock, chrono::nanoseconds> tp) _NOEXCEPT
-{
     using namespace chrono;
-    if (!lk.owns_lock())
-        __throw_system_error(EPERM,
-                            "condition_variable::timed wait: mutex not locked");
-    nanoseconds d = tp.time_since_epoch();
-    if (d > nanoseconds(0x59682F000000E941))
-        d = nanoseconds(0x59682F000000E941);
+    if (__t > nanoseconds(0x59682F000000E941))
+        __t = nanoseconds(0x59682F000000E941);
     timespec ts;
-    seconds s = duration_cast<seconds>(d);
+    timespec* pts = nullptr;
+
+    if (__t.count() > 0) {
+        seconds s = duration_cast<seconds>(__t);
         typedef decltype(ts.tv_sec) ts_sec;
         _LIBCPP_CONSTEXPR ts_sec ts_sec_max = numeric_limits<ts_sec>::max();
         if (s.count() < ts_sec_max)
         {
             ts.tv_sec = static_cast<ts_sec>(s.count());
-        ts.tv_nsec = static_cast<decltype(ts.tv_nsec)>((d - s).count());
+            ts.tv_nsec = static_cast<decltype(ts.tv_nsec)>((__t - s).count());
         }
         else
         {
             ts.tv_sec = ts_sec_max;
             ts.tv_nsec = giga::num - 1;
         }
-    int ec = __libcpp_condvar_timedwait(&__cv_, lk.mutex()->native_handle(), &ts);
-    if (ec != 0 && ec != ETIMEDOUT)
-        __throw_system_error(ec, "condition_variable timed_wait failed");
+        pts = &ts;
+    }
+
+    unsigned int old_state = atomic_load_explicit(&__state, memory_order_relaxed);
+    __lk.unlock();
+    int ec = __futex(&__state, op, old_state, pts, val3);
+    __lk.lock();
+
+    return ec;
+}
+
+int condition_variable::__futex(volatile void* ftx, int op, int value,
+                                const struct timespec* timeout,
+                                int bitset) _NOEXCEPT {
+    // Our generated syscall assembler sets errno, but our callers don't want to.
+    int saved_errno = errno;
+    int result = syscall(__NR_futex, ftx, op, value, timeout, NULL, bitset);
+    if (result == -1) {
+        result = -errno;
+        errno = saved_errno;
+    }
+    return result;
 }
 
 void
 notify_all_at_thread_exit(condition_variable& cond, unique_lock<mutex> lk)
 {
     auto& tl_ptr = __thread_local_data();
     // If this thread was not created using std::thread then it will not have
     // previously allocated.