Index: libcxx/include/CMakeLists.txt =================================================================== --- libcxx/include/CMakeLists.txt +++ libcxx/include/CMakeLists.txt @@ -25,6 +25,7 @@ any array atomic + barrier bit bitset cassert @@ -103,6 +104,7 @@ iostream istream iterator + latch limits limits.h list @@ -122,6 +124,7 @@ ratio regex scoped_allocator + semaphore set setjmp.h shared_mutex Index: libcxx/include/__threading_support =================================================================== --- libcxx/include/__threading_support +++ libcxx/include/__threading_support @@ -14,6 +14,13 @@ #include #include #include +#include + +#if defined(__linux__) +# include +# include +# include +#endif #ifndef _LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER #pragma GCC system_header @@ -26,6 +33,10 @@ #if defined(_LIBCPP_HAS_THREAD_API_PTHREAD) # include # include +# include +# if defined(__APPLE__) +# include +# endif #endif #if defined(_LIBCPP_HAS_THREAD_LIBRARY_EXTERNAL) || \ @@ -63,6 +74,15 @@ typedef pthread_cond_t __libcpp_condvar_t; #define _LIBCPP_CONDVAR_INITIALIZER PTHREAD_COND_INITIALIZER +// Semaphore +#if defined(__APPLE__) +typedef dispatch_semaphore_t __libcpp_semaphore_t; +# define _LIBCPP_SEMAPHORE_MAX numeric_limits::max() +#else +typedef sem_t __libcpp_semaphore_t; +# define _LIBCPP_SEMAPHORE_MAX SEM_VALUE_MAX +#endif + // Execute once typedef pthread_once_t __libcpp_exec_once_flag; #define _LIBCPP_EXEC_ONCE_INITIALIZER PTHREAD_ONCE_INIT @@ -115,7 +135,14 @@ #endif // !defined(_LIBCPP_HAS_THREAD_API_PTHREAD) && !defined(_LIBCPP_HAS_THREAD_API_EXTERNAL) #if !defined(_LIBCPP_HAS_THREAD_API_EXTERNAL) + +_LIBCPP_THREAD_ABI_VISIBILITY +__libcpp_timespec_t __libcpp_to_timespec(chrono::nanoseconds __ns, bool __absolute); + // Mutex +_LIBCPP_THREAD_ABI_VISIBILITY +int __libcpp_mutex_init(__libcpp_mutex_t *__m); + _LIBCPP_THREAD_ABI_VISIBILITY int __libcpp_recursive_mutex_init(__libcpp_recursive_mutex_t *__m); @@ -144,6 +171,9 @@ int __libcpp_mutex_destroy(__libcpp_mutex_t *__m); // Condition variable +_LIBCPP_THREAD_ABI_VISIBILITY +int __libcpp_condvar_init(__libcpp_condvar_t* __cv); + _LIBCPP_THREAD_ABI_VISIBILITY int __libcpp_condvar_signal(__libcpp_condvar_t* __cv); @@ -160,6 +190,22 @@ _LIBCPP_THREAD_ABI_VISIBILITY int __libcpp_condvar_destroy(__libcpp_condvar_t* __cv); +// Semaphore +_LIBCPP_THREAD_ABI_VISIBILITY +bool __libcpp_semaphore_init(__libcpp_semaphore_t* __sem, int __init); + +_LIBCPP_THREAD_ABI_VISIBILITY +bool __libcpp_semaphore_destroy(__libcpp_semaphore_t* __sem); + +_LIBCPP_THREAD_ABI_VISIBILITY +bool __libcpp_semaphore_post(__libcpp_semaphore_t* __sem); + +_LIBCPP_THREAD_ABI_VISIBILITY +bool __libcpp_semaphore_wait(__libcpp_semaphore_t* __sem); + +_LIBCPP_THREAD_ABI_VISIBILITY +bool __libcpp_semaphore_wait_timed(__libcpp_semaphore_t* __sem, chrono::nanoseconds __ns); + // Execute once _LIBCPP_THREAD_ABI_VISIBILITY int __libcpp_execute_once(__libcpp_exec_once_flag *flag, @@ -195,9 +241,16 @@ _LIBCPP_THREAD_ABI_VISIBILITY void __libcpp_thread_yield(); +_LIBCPP_THREAD_ABI_VISIBILITY +void __libcpp_thread_yield_processor(); + _LIBCPP_THREAD_ABI_VISIBILITY void __libcpp_thread_sleep_for(const chrono::nanoseconds& __ns); +template +_LIBCPP_THREAD_ABI_VISIBILITY +bool __libcpp_thread_poll_with_backoff(_Fn && __f, chrono::nanoseconds __max = chrono::nanoseconds::zero()); + // Thread local storage _LIBCPP_THREAD_ABI_VISIBILITY int __libcpp_tls_create(__libcpp_tls_key* __key, @@ -215,6 +268,34 @@ defined(_LIBCPP_BUILDING_THREAD_LIBRARY_EXTERNAL)) && \ defined(_LIBCPP_HAS_THREAD_API_PTHREAD) +__libcpp_timespec_t __libcpp_to_timespec(chrono::nanoseconds __ns, bool __absolute) { + + using namespace chrono; + if(__absolute) + __ns += chrono::system_clock::now().time_since_epoch(); + seconds __s = duration_cast(__ns); + __libcpp_timespec_t __ts; + typedef decltype(__ts.tv_sec) ts_sec; + _LIBCPP_CONSTEXPR ts_sec __ts_sec_max = numeric_limits::max(); + + if (__s.count() < __ts_sec_max) + { + __ts.tv_sec = static_cast(__s.count()); + __ts.tv_nsec = static_cast((__ns - __s).count()); + } + else + { + __ts.tv_sec = __ts_sec_max; + __ts.tv_nsec = 999999999; // (10^9 - 1) + } + return __ts; +} + +int __libcpp_mutex_init(__libcpp_mutex_t *__m) +{ + return pthread_mutex_init(__m, NULL); +} + int __libcpp_recursive_mutex_init(__libcpp_recursive_mutex_t *__m) { pthread_mutexattr_t attr; @@ -280,6 +361,11 @@ } // Condition Variable +int __libcpp_condvar_init(__libcpp_condvar_t* __cv) +{ + return pthread_cond_init(__cv, NULL); +} + int __libcpp_condvar_signal(__libcpp_condvar_t *__cv) { return pthread_cond_signal(__cv); @@ -306,6 +392,66 @@ return pthread_cond_destroy(__cv); } +// Semaphore +#if defined(__APPLE__) + +bool __libcpp_semaphore_init(__libcpp_semaphore_t* __sem, int __init) +{ + return (*__sem = dispatch_semaphore_create(__init)) != NULL; +} + +bool __libcpp_semaphore_destroy(__libcpp_semaphore_t* __sem) +{ + dispatch_release(*__sem); + return true; +} + +bool __libcpp_semaphore_post(__libcpp_semaphore_t* __sem) +{ + dispatch_semaphore_signal(*__sem); + return true; +} + +bool __libcpp_semaphore_wait(__libcpp_semaphore_t* __sem) +{ + return dispatch_semaphore_wait(*__sem, DISPATCH_TIME_FOREVER) == 0; +} + +bool __libcpp_semaphore_wait_timed(__libcpp_semaphore_t* __sem, chrono::nanoseconds __ns) +{ + return dispatch_semaphore_wait(*__sem, dispatch_time(DISPATCH_TIME_NOW, __ns.count())) == 0; +} + +#else + +bool __libcpp_semaphore_init(__libcpp_semaphore_t* __sem, int __init) +{ + return sem_init(__sem, 0, __init) == 0; +} + +bool __libcpp_semaphore_destroy(__libcpp_semaphore_t* __sem) +{ + return sem_destroy(__sem) == 0; +} + +bool __libcpp_semaphore_post(__libcpp_semaphore_t* __sem) +{ + return sem_post(__sem) == 0; +} + +bool __libcpp_semaphore_wait(__libcpp_semaphore_t* __sem) +{ + return sem_wait(__sem) == 0; +} + +bool __libcpp_semaphore_wait_timed(__libcpp_semaphore_t* __sem, chrono::nanoseconds __ns) +{ + __libcpp_timespec_t __ts = __libcpp_to_timespec(__ns, true); + return sem_timedwait(__sem, &__ts) == 0; +} + +#endif //__APPLE__ + // Execute once int __libcpp_execute_once(__libcpp_exec_once_flag *flag, void (*init_routine)()) { @@ -361,26 +507,52 @@ sched_yield(); } +void __libcpp_thread_yield_processor() +{ +#if defined(__aarch64__) + asm volatile ("yield" :::); +#elif defined(__x86_64__) + asm volatile ("pause" :::); +#elif defined (__powerpc__) + asm volatile ("or 27,27,27":::); +#else + ; +#endif +} + void __libcpp_thread_sleep_for(const chrono::nanoseconds& __ns) { - using namespace chrono; - seconds __s = duration_cast(__ns); - __libcpp_timespec_t __ts; - typedef decltype(__ts.tv_sec) ts_sec; - _LIBCPP_CONSTEXPR ts_sec __ts_sec_max = numeric_limits::max(); + __libcpp_timespec_t __ts = __libcpp_to_timespec(__ns, false); + while (nanosleep(&__ts, &__ts) == -1 && errno == EINTR); +} - if (__s.count() < __ts_sec_max) - { - __ts.tv_sec = static_cast(__s.count()); - __ts.tv_nsec = static_cast((__ns - __s).count()); - } - else - { - __ts.tv_sec = __ts_sec_max; - __ts.tv_nsec = 999999999; // (10^9 - 1) - } +#define _LIBCPP_POLLING_COUNT 16 - while (nanosleep(&__ts, &__ts) == -1 && errno == EINTR); +template +bool __libcpp_thread_poll_with_backoff(_Fn && __f, chrono::nanoseconds __max) +{ + chrono::high_resolution_clock::time_point const __start = chrono::high_resolution_clock::now(); + for(int __count = 0;;) { + if(__f()) + return true; + if(__count < _LIBCPP_POLLING_COUNT) { + if(__count > (_LIBCPP_POLLING_COUNT >> 1)) + __libcpp_thread_yield_processor(); + __count += 1; + continue; + } + chrono::high_resolution_clock::duration const __elapsed = chrono::high_resolution_clock::now() - __start; + if(__max != chrono::nanoseconds::zero() && + __max < __elapsed) + return false; + chrono::nanoseconds const __step = __elapsed / 4; + if(__step >= chrono::milliseconds(1)) + __libcpp_thread_sleep_for(chrono::milliseconds(1)); + else if(__step >= chrono::microseconds(10)) + __libcpp_thread_sleep_for(__step); + else + __libcpp_thread_yield(); + } } // Thread local storage @@ -401,6 +573,45 @@ #endif // !_LIBCPP_HAS_THREAD_LIBRARY_EXTERNAL || _LIBCPP_BUILDING_THREAD_LIBRARY_EXTERNAL +#ifndef _LIBCPP_HAS_NO_PLATFORM_WAIT + +#ifndef _LIBCPP_HAS_NO_PLATFORM_WAIT_STATE +# ifdef __linux__ +# define _LIBCPP_HAS_PLATFORM_WAIT_STATE +# define _LIBCPP_PLATFORM_WAIT_STATE_SIZE 4 +typedef uint32_t __libcpp_platform_contention_t; +# endif // __linux__ +# ifdef __APPLE__ +# define _LIBCPP_HAS_PLATFORM_WAIT_STATE +# define _LIBCPP_PLATFORM_WAIT_STATE_SIZE 8 +typedef uint64_t __libcpp_platform_contention_t; +# endif +#endif //_LIBCPP_HAS_NO_PLATFORM_WAIT_STATE + +#define _LIBCPP_HAS_PLATFORM_WAIT + +_LIBCPP_FUNC_VIS +void __libcpp_platform_contention_notify( + void const volatile* __location, + void* __contention_state, // in: __cxx_atomic_impl<__libcpp_platform_contention_t>* or nullptr + bool __notify_one +); +_LIBCPP_FUNC_VIS +void __libcpp_platform_contention_monitor_for_wait( + void const volatile* __location, + void* __contention_state, // in: __cxx_atomic_impl<__libcpp_platform_contention_t>* or nullptr + void* __old_value // out: __libcpp_platform_contention_t* or nullptr +); +_LIBCPP_FUNC_VIS +void __libcpp_platform_contention_wait_and_cleanup( + void const volatile* __location, + bool __do_wait, + void* __contention_state, // in: __cxx_atomic_impl<__libcpp_platform_contention_t>* or nullptr + void const* __old_value // in: __libcpp_platform_contention_t* or nullptr +); + +#endif // _LIBCPP_HAS_NO_PLATFORM_WAIT + class _LIBCPP_TYPE_VIS thread; class _LIBCPP_TYPE_VIS __thread_id; @@ -453,7 +664,7 @@ _LIBCPP_INLINE_VISIBILITY void __reset() { __id_ = 0; } - + template friend _LIBCPP_INLINE_VISIBILITY Index: libcxx/include/atomic =================================================================== --- libcxx/include/atomic +++ libcxx/include/atomic @@ -547,8 +547,10 @@ */ #include <__config> +#include <__threading_support> #include #include +#include #include #include @@ -629,11 +631,16 @@ #endif // _LIBCPP_STD_VER > 17 +template _LIBCPP_INLINE_VISIBILITY +bool __cxx_nonatomic_compare_equal(_Tp const& __lhs, _Tp const& __rhs) { + return memcmp(&__lhs, &__rhs, sizeof(_Tp)) == 0; +} + static_assert((is_same::type, __memory_order_underlying_t>::value), "unexpected underlying type for std::memory_order"); #if defined(_LIBCPP_HAS_GCC_ATOMIC_IMP) || \ - defined(_LIBCPP_ATOMIC_ONLY_USE_BUILTINS) + defined(_LIBCPP_ATOMIC_ONLY_USE_BUILTINS) // [atomics.types.generic]p1 guarantees _Tp is trivially copyable. Because // the default operator= in an object is not volatile, a byte-by-byte copy @@ -1079,7 +1086,7 @@ return __c11_atomic_fetch_xor(&__a->__a_value, __pattern, static_cast<__memory_order_underlying_t>(__order)); } -#endif // _LIBCPP_HAS_GCC_ATOMIC_IMP, _LIBCPP_HAS_C_ATOMIC_IMP +#endif // _LIBCPP_HAS_GCC_ATOMIC_IMP, _LIBCPP_HAS_C_ATOMIC_IMP template _LIBCPP_INLINE_VISIBILITY @@ -1218,9 +1225,9 @@ bool __cxx_atomic_compare_exchange_strong(volatile __cxx_atomic_lock_impl<_Tp>* __a, _Tp* __expected, _Tp __value, memory_order, memory_order) { __a->__lock(); - _Tp temp; - __cxx_atomic_assign_volatile(temp, __a->__a_value); - bool __ret = temp == *__expected; + _Tp __temp; + __cxx_atomic_assign_volatile(__temp, __a->__a_value); + bool __ret = __temp == *__expected; if(__ret) __cxx_atomic_assign_volatile(__a->__a_value, __value); else @@ -1247,9 +1254,9 @@ bool __cxx_atomic_compare_exchange_weak(volatile __cxx_atomic_lock_impl<_Tp>* __a, _Tp* __expected, _Tp __value, memory_order, memory_order) { __a->__lock(); - _Tp temp; - __cxx_atomic_assign_volatile(temp, __a->__a_value); - bool __ret = temp == *__expected; + _Tp __temp; + __cxx_atomic_assign_volatile(__temp, __a->__a_value); + bool __ret = __temp == *__expected; if(__ret) __cxx_atomic_assign_volatile(__a->__a_value, __value); else @@ -1307,7 +1314,7 @@ template _LIBCPP_INLINE_VISIBILITY _Tp* __cxx_atomic_fetch_add(__cxx_atomic_lock_impl<_Tp*>* __a, - ptrdiff_t __delta, memory_order) { + ptrdiff_t __delta, memory_order) { __a->__lock(); _Tp* __old = __a->__a_value; __a->__a_value += __delta; @@ -1448,10 +1455,194 @@ #endif _LIBCPP_INLINE_VISIBILITY __cxx_atomic_impl() _NOEXCEPT _LIBCPP_DEFAULT - _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR explicit __cxx_atomic_impl(_Tp value) _NOEXCEPT + _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR __cxx_atomic_impl(_Tp value) _NOEXCEPT : _Base(value) {} }; +#ifdef _LIBCPP_HAS_PLATFORM_WAIT + +template +_LIBCPP_INLINE_VISIBILITY bool __cxx_atomic_wait_fast(__cxx_atomic_impl<_Tp> const volatile* __a, _Tp const __val, memory_order __order) +{ + for(int __i = 0; __i < _LIBCPP_POLLING_COUNT; ++__i) { + if(!__cxx_nonatomic_compare_equal(__cxx_atomic_load(__a, __order), __val)) + return true; + if(__i < 12) + __libcpp_thread_yield_processor(); + else + __libcpp_thread_yield(); + } + return false; +} + +#ifdef _LIBCPP_HAS_PLATFORM_WAIT_STATE + +template +_LIBCPP_INLINE_VISIBILITY void __cxx_atomic_notify_all(__cxx_atomic_impl<_Tp> const volatile* __a, + __cxx_atomic_impl<__libcpp_platform_contention_t>* __s = nullptr) +{ + __libcpp_platform_contention_notify(__a, __s, true); +} +template +_LIBCPP_INLINE_VISIBILITY void __cxx_atomic_notify_one(__cxx_atomic_impl<_Tp> const volatile* __a, + __cxx_atomic_impl<__libcpp_platform_contention_t>* __s = nullptr) +{ + __libcpp_platform_contention_notify(__a, __s, false); +} +template +_LIBCPP_INLINE_VISIBILITY void __cxx_atomic_wait(__cxx_atomic_impl<_Tp> const volatile* __a, _Tp const __val, memory_order __order, + __cxx_atomic_impl<__libcpp_platform_contention_t>* __s = nullptr) +{ + if(__cxx_atomic_wait_fast(__a, __val, __order)) + return; + while(1) + { + __libcpp_platform_contention_t __old; + __libcpp_platform_contention_monitor_for_wait(__a, __s, &__old); + auto const __cond = __cxx_nonatomic_compare_equal(__cxx_atomic_load(__a, __order), __val); + __libcpp_platform_contention_wait_and_cleanup(__a, __cond, __s, &__old); + if(!__cond) + return; + } +} + +#else // _LIBCPP_HAS_PLATFORM_WAIT_STATE + +template +_LIBCPP_INLINE_VISIBILITY void __cxx_atomic_notify_all(__cxx_atomic_impl<_Tp> const volatile* __a) +{ + __libcpp_platform_contention_notify(__a, /* ignored-> */ nullptr, true); +} +template +_LIBCPP_INLINE_VISIBILITY void __cxx_atomic_notify_one(__cxx_atomic_impl<_Tp> const volatile* __a) +{ + __libcpp_platform_contention_notify(__a, /* ignored-> */ nullptr, false); +} +template +_LIBCPP_INLINE_VISIBILITY void __cxx_atomic_wait(__cxx_atomic_impl<_Tp> const volatile* __a, _Tp const __val, memory_order __order) +{ + if(__cxx_atomic_wait_fast(__a, __val, __order)) + return; + while(1) + { + __libcpp_platform_contention_monitor_for_wait(__a, /* ignored-> */ nullptr, nullptr); + auto const __cond = __cxx_nonatomic_compare_equal(__cxx_atomic_load(__a, __order), __val); + __libcpp_platform_contention_wait_and_cleanup(__a, __cond, /* ignored-> */ nullptr, nullptr); + if(!__cond) + return; + } +} + +#endif // _LIBCPP_HAS_PLATFORM_WAIT_STATE + +#else // _LIBCPP_HAS_PLATFORM_WAIT + +template +_LIBCPP_INLINE_VISIBILITY void __cxx_atomic_notify_all(__cxx_atomic_impl<_Tp> const volatile* __a) +{ +} +template +_LIBCPP_INLINE_VISIBILITY void __cxx_atomic_notify_one(__cxx_atomic_impl<_Tp> const volatile* __a) +{ +} +template +_LIBCPP_INLINE_VISIBILITY void __cxx_atomic_wait(__cxx_atomic_impl<_Tp> const volatile* __a, _Tp const __val, memory_order __order) +{ + __libcpp_thread_poll_with_backoff([=]() -> bool { + return !__cxx_nonatomic_compare_equal(__cxx_atomic_load(__a, __order), __val); + }); +} + +#endif // _LIBCPP_HAS_PLATFORM_WAIT + +class __atomic_positive_ptrdiff_t +{ +#if defined(_LIBCPP_HAS_PLATFORM_WAIT_STATE) && (_LIBCPP_PLATFORM_WAIT_STATE_SIZE > 4) + inline _LIBCPP_INLINE_VISIBILITY + static int __count_bit_zero() { return 1; } + using __value_type = __libcpp_platform_contention_t; + mutable __cxx_atomic_impl<__libcpp_platform_contention_t> __count; + inline _LIBCPP_INLINE_VISIBILITY __cxx_atomic_impl<__libcpp_platform_contention_t>* __this_contention() const { return &__count; } +#else + inline _LIBCPP_INLINE_VISIBILITY + static int __count_bit_zero() { return 0; } + using __value_type = ptrdiff_t; + __cxx_atomic_impl __count; +#ifdef _LIBCPP_HAS_PLATFORM_WAIT_STATE + mutable __cxx_atomic_impl<__libcpp_platform_contention_t> __contention; + inline _LIBCPP_INLINE_VISIBILITY __cxx_atomic_impl<__libcpp_platform_contention_t>* __this_contention() const { return &__contention; } +#endif +#endif + inline _LIBCPP_INLINE_VISIBILITY + static int __non_count_mask() { return (1 << __count_bit_zero()) - 1; } +public: + inline _LIBCPP_INLINE_VISIBILITY + __atomic_positive_ptrdiff_t(ptrdiff_t __count) : __count(__count << __count_bit_zero()) +#if defined(_LIBCPP_HAS_PLATFORM_WAIT_STATE) && (_LIBCPP_PLATFORM_WAIT_STATE_SIZE <= 4) + , __contention(0) +#endif + { + } + inline _LIBCPP_INLINE_VISIBILITY + ptrdiff_t __contended_load(memory_order __order) const { + return (ptrdiff_t)__cxx_atomic_load(&__count, __order) >> __count_bit_zero(); } + inline _LIBCPP_INLINE_VISIBILITY + ptrdiff_t __contended_fetch_add(ptrdiff_t __update, memory_order __order) { + return (ptrdiff_t)__cxx_atomic_fetch_add(&__count, (__value_type)__update << __count_bit_zero(), __order) >> __count_bit_zero(); } + inline _LIBCPP_INLINE_VISIBILITY + ptrdiff_t __contended_fetch_sub(ptrdiff_t __update, memory_order __order) { + return (ptrdiff_t)__cxx_atomic_fetch_sub(&__count, (__value_type)__update << __count_bit_zero(), __order) >> __count_bit_zero(); } + inline _LIBCPP_INLINE_VISIBILITY + bool __contended_compare_exchange(ptrdiff_t& __expected, ptrdiff_t __desired, + memory_order __success, memory_order __failure) + { + __value_type __current = __expected << __count_bit_zero(); + while(1) + { + __value_type const __lo = (__current & __non_count_mask()); + if(__cxx_atomic_compare_exchange_weak(&__count, &__current, __lo + (__desired << __count_bit_zero()), __success, __failure)) + return true; + ptrdiff_t const __hi = (ptrdiff_t)__current >> __count_bit_zero(); + if(__hi != __expected) { + __expected = __hi; + return false; + } + } + } + inline _LIBCPP_INLINE_VISIBILITY + void __contended_notify_all() const + { +#ifdef _LIBCPP_HAS_PLATFORM_WAIT_STATE + __cxx_atomic_notify_all(&__count, __this_contention()); +#else + __cxx_atomic_notify_all(&__count); +#endif + } + inline _LIBCPP_INLINE_VISIBILITY + void __contended_notify_one() const + { +#ifdef _LIBCPP_HAS_PLATFORM_WAIT_STATE + __cxx_atomic_notify_one(&__count, __this_contention()); +#else + __cxx_atomic_notify_one(&__count); +#endif + } + inline _LIBCPP_INLINE_VISIBILITY + void __contended_wait(ptrdiff_t __old, memory_order __order) const + { + __value_type __current = __cxx_atomic_load(&__count, __order); + ptrdiff_t const __hi = (ptrdiff_t)__current >> __count_bit_zero(); + if(__hi != __old) + return; + __value_type const __lo = (__current & __non_count_mask()); +#ifdef _LIBCPP_HAS_PLATFORM_WAIT_STATE + __cxx_atomic_wait(&__count, __lo + (__old << __count_bit_zero()), __order, __this_contention()); +#else + __cxx_atomic_wait(&__count, __lo + (__old << __count_bit_zero()), __order); +#endif + } +}; + // general atomic template ::value && !is_same<_Tp, bool>::value> @@ -1532,6 +1723,19 @@ memory_order __m = memory_order_seq_cst) _NOEXCEPT {return __cxx_atomic_compare_exchange_strong(&__a_, &__e, __d, __m, __m);} + _LIBCPP_INLINE_VISIBILITY void wait(_Tp __v, memory_order __m = memory_order_seq_cst) const volatile _NOEXCEPT + {__cxx_atomic_wait(&__a_, __v, __m);} + _LIBCPP_INLINE_VISIBILITY void wait(_Tp __v, memory_order __m = memory_order_seq_cst) const _NOEXCEPT + {__cxx_atomic_wait(&__a_, __v, __m);} + _LIBCPP_INLINE_VISIBILITY void notify_one() volatile _NOEXCEPT + {__cxx_atomic_notify_one(&__a_);} + _LIBCPP_INLINE_VISIBILITY void notify_one() _NOEXCEPT + {__cxx_atomic_notify_one(&__a_);} + _LIBCPP_INLINE_VISIBILITY void notify_all() volatile _NOEXCEPT + {__cxx_atomic_notify_all(&__a_);} + _LIBCPP_INLINE_VISIBILITY void notify_all() _NOEXCEPT + {__cxx_atomic_notify_all(&__a_);} + _LIBCPP_INLINE_VISIBILITY __atomic_base() _NOEXCEPT _LIBCPP_DEFAULT @@ -1643,6 +1847,7 @@ : public __atomic_base<_Tp> { typedef __atomic_base<_Tp> __base; + using value_type = _Tp; _LIBCPP_INLINE_VISIBILITY atomic() _NOEXCEPT _LIBCPP_DEFAULT _LIBCPP_INLINE_VISIBILITY @@ -1663,6 +1868,7 @@ : public __atomic_base<_Tp*> { typedef __atomic_base<_Tp*> __base; + using value_type = _Tp*; _LIBCPP_INLINE_VISIBILITY atomic() _NOEXCEPT _LIBCPP_DEFAULT _LIBCPP_INLINE_VISIBILITY @@ -1947,6 +2153,76 @@ return __o->compare_exchange_strong(*__e, __d, __s, __f); } +// atomic_wait + +template +_LIBCPP_INLINE_VISIBILITY +void atomic_wait(const volatile atomic<_Tp>* __o, + typename atomic<_Tp>::value_type __v) _NOEXCEPT +{ + return __o->wait(__v); +} + +template +_LIBCPP_INLINE_VISIBILITY +void atomic_wait(const atomic<_Tp>* __o, + typename atomic<_Tp>::value_type __v) _NOEXCEPT +{ + return __o->wait(__v); +} + +// atomic_wait_explicit + +template +_LIBCPP_INLINE_VISIBILITY +void atomic_wait_explicit(const volatile atomic<_Tp>* __o, + typename atomic<_Tp>::value_type __v, + memory_order __m) _NOEXCEPT + _LIBCPP_CHECK_LOAD_MEMORY_ORDER(__m) +{ + return __o->wait(__v, __m); +} + +template +_LIBCPP_INLINE_VISIBILITY +void atomic_wait_explicit(const atomic<_Tp>* __o, + typename atomic<_Tp>::value_type __v, + memory_order __m) _NOEXCEPT + _LIBCPP_CHECK_LOAD_MEMORY_ORDER(__m) +{ + return __o->wait(__v, __m); +} + +// atomic_notify_one + +template +_LIBCPP_INLINE_VISIBILITY +void atomic_notify_one(volatile atomic<_Tp>* __o) _NOEXCEPT +{ + __o->notify_one(); +} +template +_LIBCPP_INLINE_VISIBILITY +void atomic_notify_one(atomic<_Tp>* __o) _NOEXCEPT +{ + __o->notify_one(); +} + +// atomic_notify_one + +template +_LIBCPP_INLINE_VISIBILITY +void atomic_notify_all(volatile atomic<_Tp>* __o) _NOEXCEPT +{ + __o->notify_all(); +} +template +_LIBCPP_INLINE_VISIBILITY +void atomic_notify_all(atomic<_Tp>* __o) _NOEXCEPT +{ + __o->notify_all(); +} + // atomic_fetch_add template @@ -2279,6 +2555,13 @@ { __cxx_atomic_impl<_LIBCPP_ATOMIC_FLAG_TYPE> __a_; + _LIBCPP_INLINE_VISIBILITY + bool test(memory_order __m = memory_order_seq_cst) const volatile _NOEXCEPT + {return _LIBCPP_ATOMIC_FLAG_TYPE(true)==__cxx_atomic_load(&__a_, __m);} + _LIBCPP_INLINE_VISIBILITY + bool test(memory_order __m = memory_order_seq_cst) const _NOEXCEPT + {return _LIBCPP_ATOMIC_FLAG_TYPE(true)==__cxx_atomic_load(&__a_, __m);} + _LIBCPP_INLINE_VISIBILITY bool test_and_set(memory_order __m = memory_order_seq_cst) volatile _NOEXCEPT {return __cxx_atomic_exchange(&__a_, _LIBCPP_ATOMIC_FLAG_TYPE(true), __m);} @@ -2292,6 +2575,25 @@ void clear(memory_order __m = memory_order_seq_cst) _NOEXCEPT {__cxx_atomic_store(&__a_, _LIBCPP_ATOMIC_FLAG_TYPE(false), __m);} + _LIBCPP_INLINE_VISIBILITY + void wait(bool __v, memory_order __m = memory_order_seq_cst) const volatile _NOEXCEPT + {__cxx_atomic_wait(&__a_, _LIBCPP_ATOMIC_FLAG_TYPE(__v), __m);} + _LIBCPP_INLINE_VISIBILITY + void wait(bool __v, memory_order __m = memory_order_seq_cst) const _NOEXCEPT + {__cxx_atomic_wait(&__a_, _LIBCPP_ATOMIC_FLAG_TYPE(__v), __m);} + _LIBCPP_INLINE_VISIBILITY + void notify_one() volatile _NOEXCEPT + {__cxx_atomic_notify_one(&__a_);} + _LIBCPP_INLINE_VISIBILITY + void notify_one() _NOEXCEPT + {__cxx_atomic_notify_one(&__a_);} + _LIBCPP_INLINE_VISIBILITY + void notify_all() volatile _NOEXCEPT + {__cxx_atomic_notify_all(&__a_);} + _LIBCPP_INLINE_VISIBILITY + void notify_all() _NOEXCEPT + {__cxx_atomic_notify_all(&__a_);} + _LIBCPP_INLINE_VISIBILITY atomic_flag() _NOEXCEPT _LIBCPP_DEFAULT @@ -2310,6 +2612,35 @@ #endif } atomic_flag; + +inline _LIBCPP_INLINE_VISIBILITY +bool +atomic_flag_test(const volatile atomic_flag* __o) _NOEXCEPT +{ + return __o->test(); +} + +inline _LIBCPP_INLINE_VISIBILITY +bool +atomic_flag_test(const atomic_flag* __o) _NOEXCEPT +{ + return __o->test(); +} + +inline _LIBCPP_INLINE_VISIBILITY +bool +atomic_flag_test_explicit(const volatile atomic_flag* __o, memory_order __m) _NOEXCEPT +{ + return __o->test(__m); +} + +inline _LIBCPP_INLINE_VISIBILITY +bool +atomic_flag_test_explicit(const atomic_flag* __o, memory_order __m) _NOEXCEPT +{ + return __o->test(__m); +} + inline _LIBCPP_INLINE_VISIBILITY bool atomic_flag_test_and_set(volatile atomic_flag* __o) _NOEXCEPT @@ -2366,6 +2697,65 @@ __o->clear(__m); } + +inline _LIBCPP_INLINE_VISIBILITY +void +atomic_flag_wait(const volatile atomic_flag* __o, bool __v) _NOEXCEPT +{ + __o->wait(__v); +} + +inline _LIBCPP_INLINE_VISIBILITY +void +atomic_flag_wait(const atomic_flag* __o, bool __v) _NOEXCEPT +{ + __o->wait(__v); +} + +inline _LIBCPP_INLINE_VISIBILITY +void +atomic_flag_wait_explicit(const volatile atomic_flag* __o, + bool __v, memory_order __m) _NOEXCEPT +{ + __o->wait(__v, __m); +} + +inline _LIBCPP_INLINE_VISIBILITY +void +atomic_flag_wait_explicit(const atomic_flag* __o, + bool __v, memory_order __m) _NOEXCEPT +{ + __o->wait(__v, __m); +} + +inline _LIBCPP_INLINE_VISIBILITY +void +atomic_flag_notify_one(volatile atomic_flag* __o) _NOEXCEPT +{ + __o->notify_one(); +} + +inline _LIBCPP_INLINE_VISIBILITY +void +atomic_flag_notify_one(atomic_flag* __o) _NOEXCEPT +{ + __o->notify_one(); +} + +inline _LIBCPP_INLINE_VISIBILITY +void +atomic_flag_notify_all(volatile atomic_flag* __o) _NOEXCEPT +{ + __o->notify_all(); +} + +inline _LIBCPP_INLINE_VISIBILITY +void +atomic_flag_notify_all(atomic_flag* __o) _NOEXCEPT +{ + __o->notify_all(); +} + // fences inline _LIBCPP_INLINE_VISIBILITY @@ -2434,6 +2824,11 @@ typedef atomic atomic_intmax_t; typedef atomic atomic_uintmax_t; +static_assert(ATOMIC_INT_LOCK_FREE, "This library assumes atomic is lock-free."); + +typedef atomic atomic_signed_lock_free; +typedef atomic atomic_unsigned_lock_free; + #define ATOMIC_FLAG_INIT {false} #define ATOMIC_VAR_INIT(__v) {__v} Index: libcxx/include/barrier =================================================================== --- /dev/null +++ libcxx/include/barrier @@ -0,0 +1,307 @@ +// -*- C++ -*- +//===--------------------------- barrier ----------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP_BARRIER +#define _LIBCPP_BARRIER + +/* + barrier synopsis + +namespace std +{ + + template + class barrier + { + public: + using arrival_token = see below; + + constexpr explicit barrier(ptrdiff_t phase_count, + CompletionFunction f = CompletionFunction()); + ~barrier(); + + barrier(const barrier&) = delete; + barrier& operator=(const barrier&) = delete; + + [[nodiscard]] arrival_token arrive(ptrdiff_t update = 1); + void wait(arrival_token&& arrival) const; + + void arrive_and_wait(); + void arrive_and_drop(); + + private: + CompletionFunction completion; // exposition only + }; + +} + +*/ + +#include <__config> +#include <__threading_support> +#include +# ifndef _LIBCPP_HAS_NO_TREE_BARRIER +# include +# endif + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +#pragma GCC system_header +#endif + +#ifdef _LIBCPP_HAS_NO_THREADS +# error is not supported on this single threaded system +#endif + +#if _LIBCPP_STD_VER < 11 +# error is requires C++11 or later +#endif + +_LIBCPP_BEGIN_NAMESPACE_STD + +struct __empty_completion +{ + inline _LIBCPP_INLINE_VISIBILITY + void operator()() noexcept + { + } +}; + +#ifndef _LIBCPP_HAS_NO_TREE_BARRIER + +/* + +The default implementation of __barrier_base is a classic tree barrier. + +It looks different from literature pseudocode for two main reasons: + 1. Threads that call into std::barrier functions do not provide indices, + so a numbering step is added before the actual barrier algorithm, + appearing as an N+1 round to the N rounds of the tree barrier. + 2. A great deal of attention has been paid to avoid cache line thrashing + by flattening the tree structure into cache-line sized arrays, that + are indexed in an efficient way. + +*/ + +class __barrier_algorithm_base { +public: + using __phase_t = uint8_t; + + struct alignas(64) __state_t + { + struct { + __atomic_base<__phase_t> __phase = ATOMIC_VAR_INIT(0); + } __tickets[64]; + }; + + ptrdiff_t __expected; + unique_ptr<__state_t[]> __state; + + _LIBCPP_EXPORTED_FROM_ABI + __barrier_algorithm_base(ptrdiff_t __expected); + _LIBCPP_EXPORTED_FROM_ABI + bool __arrive(__phase_t const __old_phase); +}; + +template +class __barrier_base : public __barrier_algorithm_base { + + __atomic_base __expected_adjustment; + _CompletionF __completion; + __atomic_base<__phase_t> __phase; + +public: + using arrival_token = __phase_t; + + _LIBCPP_INLINE_VISIBILITY + __barrier_base(ptrdiff_t __expected, _CompletionF __completion = _CompletionF()) + : __barrier_algorithm_base(__expected), __expected_adjustment(0), + __completion(std::move(__completion)), __phase(0) + { + } + [[nodiscard]] _LIBCPP_INLINE_VISIBILITY + arrival_token arrive(ptrdiff_t update) + { + auto __old_phase = __phase.load(memory_order_relaxed); + for(; update; --update) + if(__arrive(__old_phase)) { + __completion(); + __expected += __expected_adjustment.load(memory_order_relaxed); + __expected_adjustment.store(0, memory_order_relaxed); + __phase.store(__old_phase + 2, memory_order_release); + } + return __old_phase; + } + _LIBCPP_INLINE_VISIBILITY + void wait(arrival_token&& __old_phase) const + { + __libcpp_thread_poll_with_backoff([=]() -> bool { + return __phase.load(memory_order_acquire) != __old_phase; + }); + } + _LIBCPP_INLINE_VISIBILITY + void arrive_and_drop() + { + __expected_adjustment.fetch_sub(1, memory_order_relaxed); + (void)arrive(1); + } +}; + +#else + +/* + +The alternative implementation of __barrier_base is a central barrier. + +Two versions of this algorithm are provided: + 1. A fairly straightforward implementation of the litterature for the + general case where the completion function is not empty. + 2. An optimized implementation that exploits 2's complement arithmetic + and well-defined overflow in atomic arithmetic, to handle the phase + roll-over for free. + +*/ + +template +class __barrier_base { + + __atomic_base __expected; + __atomic_base __arrived; + _CompletionF __completion; + __atomic_base __phase; +public: + using arrival_token = bool; + + _LIBCPP_INLINE_VISIBILITY + __barrier_base(ptrdiff_t __expected, _CompletionF __completion = _CompletionF()) + : __expected(__expected), __arrived(__expected), __completion(__completion), __phase(false) + { + } + [[nodiscard]] _LIBCPP_INLINE_VISIBILITY + arrival_token arrive(ptrdiff_t update) + { + auto const __old_phase = __phase.load(memory_order_relaxed); + auto const __result = __arrived.fetch_sub(update, memory_order_acq_rel) - update; + auto const new_expected = __expected.load(memory_order_relaxed); + if(0 == __result) { + __completion(); + __arrived.store(new_expected, memory_order_relaxed); + __phase.store(!__old_phase, memory_order_release); + atomic_notify_all(&__phase); + } + return __old_phase; + } + _LIBCPP_INLINE_VISIBILITY + void wait(arrival_token&& __old_phase) const + { + __phase.wait(__old_phase, memory_order_acquire); + } + _LIBCPP_INLINE_VISIBILITY + void arrive_and_drop() + { + __expected.fetch_sub(1, memory_order_relaxed); + (void)arrive(1); + } +}; + +template<> +class __barrier_base<__empty_completion> { + + static constexpr uint64_t __expected_unit = 1ull; + static constexpr uint64_t __arrived_unit = 1ull << 32; + static constexpr uint64_t __expected_mask = __arrived_unit - 1; + static constexpr uint64_t __phase_bit = 1ull << 63; + static constexpr uint64_t __arrived_mask = (__phase_bit - 1) & ~__expected_mask; + + __atomic_base __phase_arrived_expected; + + static _LIBCPP_INLINE_VISIBILITY + constexpr uint64_t __init(ptrdiff_t __count) _NOEXCEPT + { + return ((uint64_t(1u << 31) - __count) << 32) + | (uint64_t(1u << 31) - __count); + } + +public: + using arrival_token = uint64_t; + + _LIBCPP_INLINE_VISIBILITY + explicit inline __barrier_base(ptrdiff_t __count, __empty_completion = __empty_completion()) + : __phase_arrived_expected(__init(__count)) + { + } + [[nodiscard]] inline _LIBCPP_INLINE_VISIBILITY + arrival_token arrive(ptrdiff_t update) + { + auto const __inc = __arrived_unit * update; + auto const __old = __phase_arrived_expected.fetch_add(__inc, memory_order_acq_rel); + if((__old ^ (__old + __inc)) & __phase_bit) { + __phase_arrived_expected.fetch_add((__old & __expected_mask) << 32, memory_order_relaxed); + __phase_arrived_expected.notify_all(); + } + return __old & __phase_bit; + } + inline _LIBCPP_INLINE_VISIBILITY + void wait(arrival_token&& __phase) const + { + __libcpp_thread_poll_with_backoff([=]() -> bool + { + uint64_t const __current = __phase_arrived_expected.load(memory_order_acquire); + return ((__current & __phase_bit) != __phase); + }); + } + inline _LIBCPP_INLINE_VISIBILITY + void arrive_and_drop() + { + __phase_arrived_expected.fetch_add(__expected_unit, memory_order_relaxed); + (void)arrive(1); + } +}; + +#endif //_LIBCPP_HAS_NO_TREE_BARRIER + +template +class barrier { + + __barrier_base<_CompletionF> __b; +public: + using arrival_token = typename __barrier_base<_CompletionF>::arrival_token; + + _LIBCPP_INLINE_VISIBILITY + barrier(ptrdiff_t __count, _CompletionF __completion = _CompletionF()) + : __b(__count, std::move(__completion)) { + } + + barrier(barrier const&) = delete; + barrier& operator=(barrier const&) = delete; + + [[nodiscard]] _LIBCPP_INLINE_VISIBILITY + arrival_token arrive(ptrdiff_t update = 1) + { + return __b.arrive(update); + } + _LIBCPP_INLINE_VISIBILITY + void wait(arrival_token&& __phase) const + { + __b.wait(std::move(__phase)); + } + _LIBCPP_INLINE_VISIBILITY + void arrive_and_wait() + { + wait(arrive()); + } + _LIBCPP_INLINE_VISIBILITY + void arrive_and_drop() + { + __b.arrive_and_drop(); + } +}; + +_LIBCPP_END_NAMESPACE_STD + +#endif //_LIBCPP_BARRIER Index: libcxx/include/chrono =================================================================== --- libcxx/include/chrono +++ libcxx/include/chrono @@ -1568,6 +1568,8 @@ /////////////////////// clocks /////////////////////////// ////////////////////////////////////////////////////////// +#ifndef _LIBCPP_HAS_CLOCK_API_EXTERNAL + class _LIBCPP_TYPE_VIS system_clock { public: @@ -1600,7 +1602,12 @@ typedef system_clock high_resolution_clock; #endif +#endif // _LIBCPP_HAS_CLOCK_API_EXTERNAL + #if _LIBCPP_STD_VER > 17 + +#ifndef _LIBCPP_HAS_CLOCK_API_EXTERNAL + // [time.clock.file], type file_clock using file_clock = _VSTD_FS::_FilesystemClock; @@ -1619,6 +1626,7 @@ using local_seconds = local_time; using local_days = local_time; +#endif // _LIBCPP_HAS_CLOCK_API_EXTERNAL struct last_spec { explicit last_spec() = default; }; Index: libcxx/include/cstddef =================================================================== --- libcxx/include/cstddef +++ libcxx/include/cstddef @@ -60,8 +60,12 @@ _LIBCPP_END_NAMESPACE_STD #if _LIBCPP_STD_VER > 14 +#ifdef _LIBCPP_BEGIN_NAMESPACE_STD_NOVERSION +_LIBCPP_BEGIN_NAMESPACE_STD_NOVERSION +#else namespace std // purposefully not versioned { +#endif //_LIBCPP_BEGIN_NAMESPACE_STD_NOVERSION enum class byte : unsigned char {}; constexpr byte operator| (byte __lhs, byte __rhs) noexcept @@ -105,7 +109,11 @@ )); } +#ifdef _LIBCPP_END_NAMESPACE_STD_NOVERSION +_LIBCPP_END_NAMESPACE_STD_NOVERSION +#else } +#endif //_LIBCPP_END_NAMESPACE_STD_NOVERSION #include // rest of byte #endif Index: libcxx/include/latch =================================================================== --- /dev/null +++ libcxx/include/latch @@ -0,0 +1,110 @@ +// -*- C++ -*- +//===--------------------------- latch -----------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP_LATCH +#define _LIBCPP_LATCH + +/* + latch synopsis + +namespace std +{ + + class latch + { + public: + constexpr explicit latch(ptrdiff_t expected); + ~latch(); + + latch(const latch&) = delete; + latch& operator=(const latch&) = delete; + + void count_down(ptrdiff_t update = 1); + bool try_wait() const noexcept; + void wait() const; + void arrive_and_wait(ptrdiff_t update = 1); + + private: + ptrdiff_t counter; // exposition only + }; + +} + +*/ + +#include <__config> +#include <__threading_support> +#include + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +#pragma GCC system_header +#endif + +#ifdef _LIBCPP_HAS_NO_THREADS +# error is not supported on this single threaded system +#endif + +#if _LIBCPP_STD_VER < 11 +# error is requires C++11 or later +#endif + +_LIBCPP_BEGIN_NAMESPACE_STD + +class __latch_base : public __atomic_positive_ptrdiff_t +{ +public: + _LIBCPP_INLINE_VISIBILITY + constexpr explicit __latch_base(ptrdiff_t __expected) + : __atomic_positive_ptrdiff_t(__expected) { } + + ~__latch_base() = default; + __latch_base(const __latch_base&) = delete; + __latch_base& operator=(const __latch_base&) = delete; + + inline _LIBCPP_INLINE_VISIBILITY + void count_down(ptrdiff_t __update = 1) + { + ptrdiff_t const __old = __contended_fetch_sub(__update, memory_order_release); + if(__old == __update) + __contended_notify_all(); + } + inline _LIBCPP_INLINE_VISIBILITY + bool try_wait() const noexcept + { + return __contended_load(memory_order_acquire) == 0; + } + inline _LIBCPP_INLINE_VISIBILITY + void wait() const + { + while(1) { + ptrdiff_t const __current = __contended_load(memory_order_acquire); + if(__current == 0) + return; + __contended_wait(__current, memory_order_relaxed); + } + } + inline _LIBCPP_INLINE_VISIBILITY + void arrive_and_wait(ptrdiff_t __update = 1) + { + count_down(__update); + wait(); + } +}; + +class latch : public __latch_base { +public: + _LIBCPP_INLINE_VISIBILITY + constexpr explicit latch(ptrdiff_t __expected) + : __latch_base(__expected) { } + +}; + +_LIBCPP_END_NAMESPACE_STD + +#endif //_LIBCPP_LATCH Index: libcxx/include/module.modulemap =================================================================== --- libcxx/include/module.modulemap +++ libcxx/include/module.modulemap @@ -231,6 +231,10 @@ header "atomic" export * } + module barrier { + header "barrier" + export * + } module bit { header "bit" export * @@ -334,6 +338,10 @@ header "iterator" export * } + module latch { + header "latch" + export * + } module limits { header "limits" export * @@ -400,6 +408,10 @@ header "scoped_allocator" export * } + module semaphore { + header "semaphore" + export * + } module set { header "set" export initializer_list Index: libcxx/include/semaphore =================================================================== --- /dev/null +++ libcxx/include/semaphore @@ -0,0 +1,315 @@ +// -*- C++ -*- +//===--------------------------- semaphore --------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP_SEMAPHORE +#define _LIBCPP_SEMAPHORE + +/* + semaphore synopsis + +namespace std { + +template +class counting_semaphore +{ +public: +static constexpr ptrdiff_t max() noexcept; + +constexpr explicit counting_semaphore(ptrdiff_t desired); +~counting_semaphore(); + +counting_semaphore(const counting_semaphore&) = delete; +counting_semaphore& operator=(const counting_semaphore&) = delete; + +void release(ptrdiff_t update = 1); +void acquire(); +bool try_acquire() noexcept; +template + bool try_acquire_for(const chrono::duration& rel_time); +template + bool try_acquire_until(const chrono::time_point& abs_time); + +private: +ptrdiff_t counter; // exposition only +}; + +using binary_semaphore = counting_semaphore<1>; + +} + +*/ + +#include <__config> +#include <__threading_support> +#include +#include + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +#pragma GCC system_header +#endif + +#ifdef _LIBCPP_HAS_NO_THREADS +# error is not supported on this single threaded system +#endif + +#if _LIBCPP_STD_VER < 11 +# error is requires C++11 or later +#endif + +#if defined(__APPLE__) && !defined(_LIBCPP_HAS_NO_SEMAPHORES) && !defined(_LIBCPP_HAS_SEMAPHORES) +# define _LIBCPP_HAS_NO_SEMAPHORES +#endif + +#if defined(__linux__) && !defined(_LIBCPP_HAS_NO_SEMAPHORE_FRONT_BUFFER) && !defined(_LIBCPP_HAS_SEMAPHORE_FRONT_BUFFER) +# define _LIBCPP_HAS_NO_SEMAPHORE_FRONT_BUFFER +#endif + +_LIBCPP_BEGIN_NAMESPACE_STD + +/* + +__atomic_semaphore_base is the general-case implementation, to be used for +user-requested least-max values that exceed the OS implementation support +(incl. when the OS has no support of its own) and for binary semaphores. + +It is a typical Dijsktra semaphore algorithm over atomics, wait and notify +functions. It avoids contention against users' own use of those facilities. + +*/ + +class __atomic_semaphore_base : public __atomic_positive_ptrdiff_t +{ +public: + _LIBCPP_INLINE_VISIBILITY + __atomic_semaphore_base(ptrdiff_t __count) : __atomic_positive_ptrdiff_t(__count) { } + ~__atomic_semaphore_base() = default; + __atomic_semaphore_base(__atomic_semaphore_base const&) = delete; + __atomic_semaphore_base& operator=(__atomic_semaphore_base const&) = delete; + + _LIBCPP_INLINE_VISIBILITY + void release(ptrdiff_t __update = 1) + { + if(0 < __contended_fetch_add(__update, memory_order_release)) + ; + else if(__update > 1) + __contended_notify_all(); + else + __contended_notify_one(); + } + _LIBCPP_INLINE_VISIBILITY + void acquire() + { + ptrdiff_t __old = __contended_load(memory_order_relaxed); + while (1) { + if(__old == 0) { + __contended_wait(__old, memory_order_relaxed); + __old = __contended_load(memory_order_relaxed); + continue; + } + if(__contended_compare_exchange(__old, __old - 1, memory_order_acquire, memory_order_relaxed)) + break; + } + } + template + _LIBCPP_INLINE_VISIBILITY + bool try_acquire_for(chrono::duration const& __rel_time) + { + return __libcpp_thread_poll_with_backoff([=]() { + ptrdiff_t __old = __contended_load(memory_order_acquire); + if (__old == 0) + return false; + return __contended_compare_exchange(__old, __old - 1, memory_order_acquire, memory_order_relaxed); + }, __rel_time); + } +}; + +#ifndef _LIBCPP_HAS_NO_SEMAPHORES + +/* + +__sem_semaphore_basic_base a simple wrapper for the OS semaphore type. That +is, every call is routed to the OS in the most direct manner possible. + +On __APPLE__, the OS produces a fault if uses of 'wait' and 'signal' aren't +balanced, so this implementation balances them at destruction time (that's safe). + +*/ + +class __sem_semaphore_basic_base { + +#ifdef __APPLE__ + atomic __balance = {0}; +#endif + __libcpp_semaphore_t __semaphore; + +public: + + _LIBCPP_EXPORTED_FROM_ABI + __sem_semaphore_basic_base(ptrdiff_t __count); + _LIBCPP_EXPORTED_FROM_ABI + ~__sem_semaphore_basic_base(); + _LIBCPP_EXPORTED_FROM_ABI + void release(ptrdiff_t __update); + _LIBCPP_EXPORTED_FROM_ABI + void acquire(); + _LIBCPP_EXPORTED_FROM_ABI + bool try_acquire_for(chrono::nanoseconds __rel_time); +}; + +#ifndef _LIBCPP_HAS_NO_SEMAPHORE_BACK_BUFFER + +/* + +__sem_semaphore_back_buffered_base optimizes the case of release with an +operand greater than 1, as a wrapper around __sem_semaphore_basic_base. + +None of the target OSes support 'post' or 'signal' with a count greater +than 1, so the basic semaphore calls the OS in a loop in that case. That +puts a large burden on the caller of release (O(N) syscalls). This wrapper +distributes the releases as a binary tree among the releaser and the threads +unblocked as a result of any of the releases. + +*/ + +class __sem_semaphore_back_buffered_base { + + _LIBCPP_INLINE_VISIBILITY + void __backfill(); + + __sem_semaphore_basic_base __semaphore; + atomic __backbuffer; + +public: + _LIBCPP_EXPORTED_FROM_ABI + __sem_semaphore_back_buffered_base(ptrdiff_t __count); + _LIBCPP_EXPORTED_FROM_ABI + ~__sem_semaphore_back_buffered_base(); + _LIBCPP_EXPORTED_FROM_ABI + void release(ptrdiff_t __update); + _LIBCPP_EXPORTED_FROM_ABI + void acquire(); + _LIBCPP_EXPORTED_FROM_ABI + bool try_acquire_for(chrono::nanoseconds __rel_time); +}; + +#endif //_LIBCPP_HAS_NO_SEMAPHORE_BACK_BUFFER + +#ifndef _LIBCPP_HAS_NO_SEMAPHORE_FRONT_BUFFER + +/* + +__sem_semaphore_front_buffered_base optimizes the case of acquires on an +semaphore that has no blocked waiters, as a wrapper around (if available) +__sem_semaphore_back_buffered_base or __sem_semaphore_basic_base. + +On most OSes, semaphore calls go through a syscall that is (by itself) an +order-of-magnitude more expensive than the cost of acquiring the semaphore. +This wrapper tracks whether there are any suspended waiters and handles the +exchange of semaphore counts in user-space, so long as there are none. + +*/ + +class __sem_semaphore_front_buffered_base { + +#ifndef _LIBCPP_HAS_NO_SEMAPHORE_BACK_BUFFER + __sem_semaphore_back_buffered_base __semaphore; +#else + __sem_semaphore_basic_base __semaphore; +#endif + atomic __frontbuffer; + +public: + _LIBCPP_EXPORTED_FROM_ABI + __sem_semaphore_front_buffered_base(ptrdiff_t __count); + _LIBCPP_EXPORTED_FROM_ABI + ~__sem_semaphore_front_buffered_base(); + _LIBCPP_EXPORTED_FROM_ABI + void release(ptrdiff_t __update); + _LIBCPP_EXPORTED_FROM_ABI + void acquire(); + _LIBCPP_EXPORTED_FROM_ABI + bool try_acquire_for(chrono::nanoseconds __rel_time); +}; + +#endif //_LIBCPP_HAS_NO_SEMAPHORE_FRONT_BUFFER + +#endif //_LIBCPP_HAS_NO_SEMAPHORES + +#if defined(_LIBCPP_HAS_NO_SEMAPHORES) + template + using __semaphore_base = __atomic_semaphore_base; +#else +# if !defined(_LIBCPP_HAS_NO_SEMAPHORE_FRONT_BUFFER) + using __sem_semaphore_base = __sem_semaphore_front_buffered_base; +# elif !defined(_LIBCPP_HAS_NO_SEMAPHORE_BACK_BUFFER) + using __sem_semaphore_base = __sem_semaphore_back_buffered_base; +# else + using __sem_semaphore_base = __sem_semaphore_basic_base; +# endif + template + using __semaphore_base = + typename conditional<(__least_max_value > 1 && __least_max_value <= _LIBCPP_SEMAPHORE_MAX), + __sem_semaphore_base, + __atomic_semaphore_base>::type; +#endif + +template +class counting_semaphore +{ + __semaphore_base<__least_max_value> __semaphore; +public: + static constexpr ptrdiff_t max() noexcept { + return __least_max_value; + } + + _LIBCPP_INLINE_VISIBILITY + counting_semaphore(ptrdiff_t __count = 0) : __semaphore(__count) { } + ~counting_semaphore() = default; + + counting_semaphore(const counting_semaphore&) = delete; + counting_semaphore& operator=(const counting_semaphore&) = delete; + + _LIBCPP_INLINE_VISIBILITY + void release(ptrdiff_t __update = 1) + { + __semaphore.release(__update); + } + _LIBCPP_INLINE_VISIBILITY + void acquire() + { + __semaphore.acquire(); + } + template + _LIBCPP_INLINE_VISIBILITY + bool try_acquire_for(chrono::duration const& __rel_time) + { + return __semaphore.try_acquire_for(chrono::duration_cast(__rel_time)); + } + _LIBCPP_INLINE_VISIBILITY + bool try_acquire() + { + return try_acquire_for(chrono::nanoseconds::zero()); + } + template + _LIBCPP_INLINE_VISIBILITY + bool try_acquire_until(chrono::time_point const& __abs_time) + { + auto const current = Clock::now(); + if(current >= __abs_time) + return try_acquire(); + else + return try_acquire_for(__abs_time - current); + } +}; + +using binary_semaphore = counting_semaphore<1>; + +_LIBCPP_END_NAMESPACE_STD + +#endif //_LIBCPP_SEMAPHORE Index: libcxx/include/stdexcept =================================================================== --- libcxx/include/stdexcept +++ libcxx/include/stdexcept @@ -72,8 +72,12 @@ _LIBCPP_END_NAMESPACE_STD -namespace std // purposefully not using versioning namespace +#ifdef _LIBCPP_BEGIN_NAMESPACE_STD_NOVERSION +_LIBCPP_BEGIN_NAMESPACE_STD_NOVERSION +#else +namespace std // purposefully not versioned { +#endif //_LIBCPP_BEGIN_NAMESPACE_STD_NOVERSION class _LIBCPP_EXCEPTION_ABI logic_error : public exception @@ -204,7 +208,11 @@ #endif }; -} // std +#ifdef _LIBCPP_END_NAMESPACE_STD_NOVERSION +_LIBCPP_END_NAMESPACE_STD_NOVERSION +#else +} +#endif //_LIBCPP_END_NAMESPACE_STD_NOVERSION _LIBCPP_BEGIN_NAMESPACE_STD Index: libcxx/include/type_traits =================================================================== --- libcxx/include/type_traits +++ libcxx/include/type_traits @@ -4028,8 +4028,12 @@ #if _LIBCPP_STD_VER > 14 // std::byte +#ifdef _LIBCPP_BEGIN_NAMESPACE_STD_NOVERSION +_LIBCPP_BEGIN_NAMESPACE_STD_NOVERSION +#else namespace std // purposefully not versioned { +#endif //_LIBCPP_BEGIN_NAMESPACE_STD_NOVERSION template constexpr typename enable_if, byte>::type & operator<<=(byte& __lhs, _Integer __shift) noexcept @@ -4054,7 +4058,11 @@ constexpr typename enable_if, _Integer>::type to_integer(byte __b) noexcept { return static_cast<_Integer>(__b); } +#ifdef _LIBCPP_END_NAMESPACE_STD_NOVERSION +_LIBCPP_END_NAMESPACE_STD_NOVERSION +#else } +#endif //_LIBCPP_END_NAMESPACE_STD_NOVERSION #endif #endif // _LIBCPP_TYPE_TRAITS Index: libcxx/src/CMakeLists.txt =================================================================== --- libcxx/src/CMakeLists.txt +++ libcxx/src/CMakeLists.txt @@ -4,6 +4,8 @@ set(LIBCXX_SOURCES algorithm.cpp any.cpp + atomic.cpp + barrier.cpp bind.cpp charconv.cpp chrono.cpp @@ -28,6 +30,7 @@ optional.cpp random.cpp regex.cpp + semaphore.cpp shared_mutex.cpp stdexcept.cpp string.cpp Index: libcxx/src/atomic.cpp =================================================================== --- /dev/null +++ libcxx/src/atomic.cpp @@ -0,0 +1,171 @@ +//===------------------------- atomic.cpp ---------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "__config" + +#ifndef _LIBCPP_HAS_NO_THREADS + +#include "atomic" + +_LIBCPP_BEGIN_NAMESPACE_STD + +#ifdef _LIBCPP_HAS_PLATFORM_WAIT + +#if defined(__APPLE__) && defined(_LIBCPP_HAS_PLATFORM_WAIT_STATE) +# undef _LIBCPP_HAS_PLATFORM_WAIT_STATE +# warning "Need to define the Apple wait state in src/atomic.cpp" +#endif + +#ifndef _LIBCPP_HAS_NO_PLATFORM_WAIT_TABLE + +#ifdef _LIBCPP_HAS_PLATFORM_WAIT_STATE + +struct alignas(64) __libcpp_contention_t +{ + static constexpr __libcpp_platform_contention_t __wait_bit = 1; + static constexpr __libcpp_platform_contention_t __count_bit = 2; + __cxx_atomic_impl<__libcpp_platform_contention_t> __s = ATOMIC_VAR_INIT(0); +}; + +#else //_LIBCPP_HAS_PLATFORM_WAIT_STATE + +struct alignas(64) __libcpp_contention_t +{ + __cxx_atomic_impl __waiters = ATOMIC_VAR_INIT(0); + __libcpp_mutex_t __mutex = _LIBCPP_MUTEX_INITIALIZER; + __libcpp_condvar_t __condvar = _LIBCPP_CONDVAR_INITIALIZER; +}; + +#endif // _LIBCPP_HAS_PLATFORM_WAIT_STATE + +static constexpr size_t __libcpp_contention_state_size = (1 << 8); /* < there's no magic in this number */ +__libcpp_contention_t __libcpp_contention_state_[ __libcpp_contention_state_size ]; +__libcpp_contention_t* __libcpp_contention_state(void const volatile * p) +{ + return &__libcpp_contention_state_[(std::uintptr_t)p & (__libcpp_contention_state_size - 1)]; +} + +#endif // _LIBCPP_HAS_NO_PLATFORM_WAIT_TABLE + +#if !defined(_LIBCPP_HAS_PLATFORM_WAIT_STATE) && !defined(_LIBCPP_HAS_NO_PLATFORM_WAIT_TABLE) + +_LIBCPP_FUNC_VIS +void __libcpp_platform_contention_notify(void const volatile* __location, + void* /*off-target, do not use*/, + bool /*off-target, do not use*/) +{ + auto const __c = __libcpp_contention_state(__location); + __cxx_atomic_thread_fence(memory_order_seq_cst); + if(0 == __cxx_atomic_load(&__c->__waiters, memory_order_relaxed)) + return; + if(0 != __cxx_atomic_exchange(&__c->__waiters, ptrdiff_t(0), memory_order_relaxed)) { + __libcpp_mutex_lock(&__c->__mutex); + __libcpp_mutex_unlock(&__c->__mutex); + __libcpp_condvar_broadcast(&__c->__condvar); + } +} +_LIBCPP_FUNC_VIS +void __libcpp_platform_contention_monitor_for_wait(void const volatile* __location, + void* /*off-target, do not use*/, + void* /*off-target, do not use*/) +{ + auto const __c = __libcpp_contention_state(__location); + __libcpp_mutex_lock(&__c->__mutex); + __cxx_atomic_store(&__c->__waiters, ptrdiff_t(1), memory_order_relaxed); + __cxx_atomic_thread_fence(memory_order_seq_cst); +} +_LIBCPP_FUNC_VIS +void __libcpp_platform_contention_wait_and_cleanup(void const volatile* __location, + bool __do_wait, + void* /*off-target, do not use*/, + void const* /*off-target, do not use*/) +{ + auto const __c = __libcpp_contention_state(__location); + if(__do_wait) + __libcpp_condvar_wait(&__c->__condvar, &__c->__mutex); + __libcpp_mutex_unlock(&__c->__mutex); +} + +#endif // !defined(_LIBCPP_HAS_PLATFORM_WAIT_STATE) && !defined(_LIBCPP_HAS_NO_PLATFORM_WAIT_TABLE) + +#ifdef _LIBCPP_HAS_PLATFORM_WAIT_STATE + +#ifdef __linux__ +inline _LIBCPP_INLINE_VISIBILITY +void __libcpp_platform_wait(void const volatile* ptr, __libcpp_platform_contention_t val, void const* timeout) +{ + syscall(SYS_futex, ptr, FUTEX_WAIT_PRIVATE, val, timeout, 0, 0); +} +inline _LIBCPP_INLINE_VISIBILITY +void __libcpp_platform_wake(void const volatile* ptr, bool all) +{ + syscall(SYS_futex, ptr, FUTEX_WAKE_PRIVATE, all ? INT_MAX : 1, 0, 0, 0); +} +#else +#error "Fill me in for this platform." +#endif // __linux__ + +_LIBCPP_FUNC_VIS +void __libcpp_platform_contention_notify(void const volatile* __location, + void* __contention_state, + bool __all) +{ + auto* __s = (__cxx_atomic_impl<__libcpp_platform_contention_t>*)__contention_state; +#ifndef _LIBCPP_HAS_NO_PLATFORM_WAIT_TABLE + if(nullptr == __s) { + __s = &__libcpp_contention_state(__location)->__s; + __all = true; + } +#endif + if(__location != __s) + __cxx_atomic_fetch_add(__s, __libcpp_contention_t::__count_bit, memory_order_release); + __cxx_atomic_thread_fence(memory_order_seq_cst); + auto const __wait_bit = __libcpp_contention_t::__wait_bit; + if(__wait_bit & __cxx_atomic_fetch_and(__s, ~__wait_bit, memory_order_relaxed)) + __libcpp_platform_wake(__s, __all); +} +_LIBCPP_FUNC_VIS +void __libcpp_platform_contention_monitor_for_wait(void const volatile* __location, + void* __contention_state, + void* __old_value) +{ + auto* __s = (__cxx_atomic_impl<__libcpp_platform_contention_t>*)__contention_state; + auto* const __ret = (__libcpp_platform_contention_t*)__old_value; +#ifndef _LIBCPP_HAS_NO_PLATFORM_WAIT_TABLE + if(nullptr == __s) + __s = &__libcpp_contention_state(__location)->__s; +#endif + __cxx_atomic_fetch_or(__s, __libcpp_contention_t::__wait_bit, memory_order_relaxed); + __cxx_atomic_thread_fence(memory_order_seq_cst); + *__ret = __cxx_atomic_load(__s, memory_order_acquire); +} +_LIBCPP_FUNC_VIS +void __libcpp_platform_contention_wait_and_cleanup(void const volatile* __location, + bool __cond, + void* __contention_state, + void const* __old_value) +{ + auto const* __s = (__cxx_atomic_impl<__libcpp_platform_contention_t>*)__contention_state; + auto const* const __old = (__libcpp_platform_contention_t*)__old_value; + if(!__cond) + return; +#ifndef _LIBCPP_HAS_NO_PLATFORM_WAIT_TABLE + if(nullptr == __s) + __s = &__libcpp_contention_state(__location)->__s; +#endif + static constexpr timespec __timeout = { 2, 0 }; + __libcpp_platform_wait(__s, *__old, sizeof(__libcpp_platform_contention_t) > 4 ? nullptr : &__timeout); +} + +#endif // _LIBCPP_HAS_PLATFORM_WAIT_STATE + +#endif // _LIBCPP_HAS_PLATFORM_WAIT + +_LIBCPP_END_NAMESPACE_STD + +#endif //_LIBCPP_HAS_NO_THREADS Index: libcxx/src/barrier.cpp =================================================================== --- /dev/null +++ libcxx/src/barrier.cpp @@ -0,0 +1,76 @@ +//===------------------------- barrier.cpp ---------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "__config" + +#ifndef _LIBCPP_HAS_NO_THREADS + +#include "barrier" + +_LIBCPP_BEGIN_NAMESPACE_STD + +#if !defined(_LIBCPP_HAS_NO_TREE_BARRIER) && !defined(_LIBCPP_HAS_NO_THREAD_FAVORITE_BARRIER_INDEX) && (_LIBCPP_STD_VER >= 11) + +_LIBCPP_EXPORTED_FROM_ABI +thread_local ptrdiff_t __libcpp_thread_favorite_barrier_index = 0; + +_LIBCPP_EXPORTED_FROM_ABI +__barrier_algorithm_base::__barrier_algorithm_base(ptrdiff_t __expected) + : __expected(__expected), __state(new __barrier_algorithm_base::__state_t[(__expected+1) >> 1]) +{ +} + +_LIBCPP_EXPORTED_FROM_ABI +bool __barrier_algorithm_base::__arrive(__phase_t const __old_phase) +{ + __phase_t const __half_step = __old_phase + 1, __full_step = __old_phase + 2; +#ifndef _LIBCPP_HAS_NO_THREAD_FAVORITE_BARRIER_INDEX + ptrdiff_t __current = __libcpp_thread_favorite_barrier_index, +#else + ptrdiff_t __current = 0, +#endif + __current_expected = __expected, + __last_node = (__current_expected >> 1); + for(size_t __round = 0;; ++__round) { + if(__current_expected == 1) + return true; + for(;;++__current) { +#ifndef _LIBCPP_HAS_NO_THREAD_FAVORITE_BARRIER_INDEX + if(0 == __round) { + if(__current >= __current_expected) + __current = 0; + __libcpp_thread_favorite_barrier_index = __current; + } +#endif + __phase_t expect = __old_phase; + if(__current == __last_node && (__current_expected & 1)) + { + if(__state[__current].__tickets[__round].__phase.compare_exchange_strong(expect, __full_step, memory_order_acq_rel)) + break; // I'm 1 in 1, go to next __round + } + else if(__state[__current].__tickets[__round].__phase.compare_exchange_strong(expect, __half_step, memory_order_acq_rel)) + { + return false; // I'm 1 in 2, done with arrival + } + else if(expect == __half_step) + { + if(__state[__current].__tickets[__round].__phase.compare_exchange_strong(expect, __full_step, memory_order_acq_rel)) + break; // I'm 2 in 2, go to next __round + } + } + __current_expected = (__current_expected >> 1) + (__current_expected & 1); + __current &= ~( 1 << __round ); + __last_node &= ~( 1 << __round ); + } +} + +#endif + +_LIBCPP_END_NAMESPACE_STD + +#endif //_LIBCPP_HAS_NO_THREADS Index: libcxx/src/semaphore.cpp =================================================================== --- /dev/null +++ libcxx/src/semaphore.cpp @@ -0,0 +1,179 @@ +//===------------------------ semaphore.cpp -------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "__config" + +#ifndef _LIBCPP_HAS_NO_THREADS + +#include "semaphore" + +_LIBCPP_BEGIN_NAMESPACE_STD + +#if !defined(_LIBCPP_HAS_NO_SEMAPHORES) + +_LIBCPP_EXPORTED_FROM_ABI +__sem_semaphore_basic_base::__sem_semaphore_basic_base(ptrdiff_t __count) : + __semaphore() +{ + __libcpp_semaphore_init(&__semaphore, __count); +} +_LIBCPP_EXPORTED_FROM_ABI +__sem_semaphore_basic_base::~__sem_semaphore_basic_base() { +#ifdef __APPLE__ + auto __b = __balance.load(memory_order_relaxed); + for(; __b > 0; --__b) __libcpp_semaphore_wait(&__semaphore); + for(; __b < 0; ++__b) __libcpp_semaphore_post(&__semaphore); +#endif + __libcpp_semaphore_destroy(&__semaphore); +} +_LIBCPP_EXPORTED_FROM_ABI +void __sem_semaphore_basic_base::release(ptrdiff_t __update) +{ +#ifdef __APPLE__ + __balance.fetch_add(__update, memory_order_relaxed); +#endif + for(; __update; --__update) + __libcpp_semaphore_post(&__semaphore); +} +_LIBCPP_EXPORTED_FROM_ABI +void __sem_semaphore_basic_base::acquire() +{ + __libcpp_semaphore_wait(&__semaphore); +#ifdef __APPLE__ + __balance.fetch_sub(1, memory_order_relaxed); +#endif +} +_LIBCPP_EXPORTED_FROM_ABI +bool __sem_semaphore_basic_base::try_acquire_for(chrono::nanoseconds __rel_time) +{ + auto const __success = __libcpp_semaphore_wait_timed(&__semaphore, __rel_time); +#ifdef __APPLE__ + __balance.fetch_sub(1, memory_order_relaxed); +#endif + return __success; +} + +#ifndef _LIBCPP_HAS_NO_SEMAPHORE_BACK_BUFFER + +_LIBCPP_INLINE_VISIBILITY +void __sem_semaphore_back_buffered_base::__backfill() +{ + ptrdiff_t __expect = 2; + while(__expect != 0) + { + ptrdiff_t const __sub = __expect > 1 ? 2 : 1; + if(!__backbuffer.compare_exchange_weak(__expect, __expect - __sub, memory_order_acquire, memory_order_relaxed)) + continue; + if(__sub > 1) + __semaphore.release(1); + __semaphore.release(1); + break; + } +} +_LIBCPP_EXPORTED_FROM_ABI +__sem_semaphore_back_buffered_base::__sem_semaphore_back_buffered_base(ptrdiff_t __count) : + __semaphore(__count), __backbuffer(0) +{ +} +_LIBCPP_EXPORTED_FROM_ABI +__sem_semaphore_back_buffered_base::~__sem_semaphore_back_buffered_base() +{ +} +_LIBCPP_EXPORTED_FROM_ABI +void __sem_semaphore_back_buffered_base::release(ptrdiff_t __update) +{ + if(__update > 2) + __backbuffer.fetch_add(__update - 2, memory_order_acq_rel); + if(__update > 1) + __semaphore.release(1); + __semaphore.release(1); +} +_LIBCPP_EXPORTED_FROM_ABI +void __sem_semaphore_back_buffered_base::acquire() +{ + __semaphore.acquire(); + __backfill(); +} +_LIBCPP_EXPORTED_FROM_ABI +bool __sem_semaphore_back_buffered_base::try_acquire_for(chrono::nanoseconds __rel_time) +{ + if(!__semaphore.try_acquire_for(__rel_time)) + return false; + __backfill(); + return true; +} + +#endif //_LIBCPP_HAS_NO_SEMAPHORE_BACK_BUFFER + +#ifndef _LIBCPP_HAS_NO_SEMAPHORE_FRONT_BUFFER + +template +_LIBCPP_INLINE_VISIBILITY +static bool __sem_semaphore_front_buffered_base_acquire(atomic& __frontbuffer, _Function && __f) +{ + uint64_t __old; + __libcpp_thread_poll_with_backoff([&]() { + __old = __frontbuffer.load(memory_order_relaxed); + return 0 != (__old >> 32); + }, chrono::microseconds(50)); + while(1) { + if(0 != (__old >> 32)) { + if(__frontbuffer.compare_exchange_weak(__old, __old - (1ll << 32), memory_order_acquire)) + return true; + } + else + { + if(__frontbuffer.compare_exchange_weak(__old, __old + 1ll, memory_order_acquire)) { + bool const __ret = __f(); + __frontbuffer.fetch_sub(1ll, memory_order_release); + return __ret; + } + } + } +} +_LIBCPP_EXPORTED_FROM_ABI +__sem_semaphore_front_buffered_base::__sem_semaphore_front_buffered_base(ptrdiff_t __count) : + __semaphore(0), __frontbuffer(uint64_t(__count) << 32) +{ +} +_LIBCPP_EXPORTED_FROM_ABI +__sem_semaphore_front_buffered_base::~__sem_semaphore_front_buffered_base() +{ +} +_LIBCPP_EXPORTED_FROM_ABI +void __sem_semaphore_front_buffered_base::release(ptrdiff_t __update) +{ + uint64_t __old = 0; + while(0 == (__old & ~0ul)) + if(__frontbuffer.compare_exchange_weak(__old, __old + (uint64_t(__update) << 32), memory_order_acq_rel)) + return; + __semaphore.release(__update); +} +_LIBCPP_EXPORTED_FROM_ABI +void __sem_semaphore_front_buffered_base::acquire() +{ + __sem_semaphore_front_buffered_base_acquire(__frontbuffer, [=]() -> bool { + __semaphore.acquire(); + return true; + }); +} +_LIBCPP_EXPORTED_FROM_ABI +bool __sem_semaphore_front_buffered_base::try_acquire_for(chrono::nanoseconds __rel_time) +{ + return __sem_semaphore_front_buffered_base_acquire(__frontbuffer, [=]() -> bool { + return __semaphore.try_acquire_for(__rel_time); + }); +} + +#endif //_LIBCPP_HAS_NO_SEMAPHORE_FRONT_BUFFER + +#endif + +_LIBCPP_END_NAMESPACE_STD + +#endif //_LIBCPP_HAS_NO_THREADS Index: libcxx/test/libcxx/double_include.sh.cpp =================================================================== --- libcxx/test/libcxx/double_include.sh.cpp +++ libcxx/test/libcxx/double_include.sh.cpp @@ -25,6 +25,9 @@ #include #ifndef _LIBCPP_HAS_NO_THREADS #include +#include +#include +#include #endif #include #include Index: libcxx/test/std/atomics/atomics.types.operations/atomics.types.operations.wait/atomic_wait.pass.cpp =================================================================== --- /dev/null +++ libcxx/test/std/atomics/atomics.types.operations/atomics.types.operations.wait/atomic_wait.pass.cpp @@ -0,0 +1,56 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// UNSUPPORTED: libcpp-has-no-threads +// XFAIL: c++98, c++03 + +// + +#include +#include +#include +#include + +#include "test_macros.h" +#include "../atomics.types.operations.req/atomic_helpers.h" + +template +struct TestFn { + void operator()() const { + typedef std::atomic A; + + A t; + std::atomic_init(&t, T(1)); + assert(std::atomic_load(&t) == T(1)); + std::atomic_wait(&t, T(0)); + std::thread t_([&](){ + std::atomic_store(&t, T(3)); + std::atomic_notify_one(&t); + }); + std::atomic_wait(&t, T(1)); + t_.join(); + + volatile A vt; + std::atomic_init(&vt, T(2)); + assert(std::atomic_load(&vt) == T(2)); + std::atomic_wait(&vt, T(1)); + std::thread t2_([&](){ + std::atomic_store(&vt, T(4)); + std::atomic_notify_one(&vt); + }); + std::atomic_wait(&vt, T(2)); + t2_.join(); + } +}; + +int main(int, char**) +{ + TestEachAtomicType()(); + + return 0; +} Index: libcxx/test/std/thread/thread.barrier/arrive.pass.cpp =================================================================== --- /dev/null +++ libcxx/test/std/thread/thread.barrier/arrive.pass.cpp @@ -0,0 +1,32 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// UNSUPPORTED: libcpp-has-no-threads + +// + +#include +#include + +#include "test_macros.h" + +int main(int, char**) +{ + std::barrier<> b(2); + + auto tok = b.arrive(); + std::thread t([&](){ + (void)b.arrive(); + }); + b.wait(std::move(tok)); + t.join(); + + auto tok2 = b.arrive(2); + b.wait(std::move(tok2)); + return 0; +} Index: libcxx/test/std/thread/thread.barrier/arrive_and_drop.pass.cpp =================================================================== --- /dev/null +++ libcxx/test/std/thread/thread.barrier/arrive_and_drop.pass.cpp @@ -0,0 +1,30 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// UNSUPPORTED: libcpp-has-no-threads + +// + +#include +#include + +#include "test_macros.h" + +int main(int, char**) +{ + std::barrier<> b(2); + + std::thread t([&](){ + b.arrive_and_drop(); + }); + + b.arrive_and_wait(); + b.arrive_and_wait(); + t.join(); + return 0; +} Index: libcxx/test/std/thread/thread.barrier/arrive_and_wait.pass.cpp =================================================================== --- /dev/null +++ libcxx/test/std/thread/thread.barrier/arrive_and_wait.pass.cpp @@ -0,0 +1,31 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// UNSUPPORTED: libcpp-has-no-threads + +// + +#include +#include + +#include "test_macros.h" + +int main(int, char**) +{ + std::barrier<> b(2); + + std::thread t([&](){ + for(int i = 0; i < 10; ++i) + b.arrive_and_wait(); + }); + for(int i = 0; i < 10; ++i) + b.arrive_and_wait(); + t.join(); + + return 0; +} Index: libcxx/test/std/thread/thread.barrier/completion.pass.cpp =================================================================== --- /dev/null +++ libcxx/test/std/thread/thread.barrier/completion.pass.cpp @@ -0,0 +1,36 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// UNSUPPORTED: libcpp-has-no-threads + +// + +#include +#include +#include + +#include "test_macros.h" + +int main(int, char**) +{ + int x = 0; + auto comp = [&]() { x += 1; }; + std::barrier b(2, comp); + + std::thread t([&](){ + for(int i = 0; i < 10; ++i) + b.arrive_and_wait(); + }); + + for(int i = 0; i < 10; ++i) + b.arrive_and_wait(); + + assert(x == 10); + t.join(); + return 0; +} Index: libcxx/test/std/thread/thread.barrier/version.pass.cpp =================================================================== --- /dev/null +++ libcxx/test/std/thread/thread.barrier/version.pass.cpp @@ -0,0 +1,24 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// UNSUPPORTED: libcpp-has-no-threads + +// + +#include + +#include "test_macros.h" + +#ifndef _LIBCPP_VERSION +#error _LIBCPP_VERSION not defined +#endif + +int main(int, char**) +{ + return 0; +} Index: libcxx/test/std/thread/thread.latch/arrive_and_wait.pass.cpp =================================================================== --- /dev/null +++ libcxx/test/std/thread/thread.latch/arrive_and_wait.pass.cpp @@ -0,0 +1,29 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// UNSUPPORTED: libcpp-has-no-threads + +// + +#include +#include + +#include "test_macros.h" + +int main(int, char**) +{ + std::latch l(2); + + std::thread t([&](){ + l.arrive_and_wait(); + }); + l.arrive_and_wait(); + t.join(); + + return 0; +} Index: libcxx/test/std/thread/thread.latch/count_down.pass.cpp =================================================================== --- /dev/null +++ libcxx/test/std/thread/thread.latch/count_down.pass.cpp @@ -0,0 +1,30 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// UNSUPPORTED: libcpp-has-no-threads + +// + +#include +#include + +#include "test_macros.h" + +int main(int, char**) +{ + std::latch l(2); + + l.count_down(); + std::thread t([&](){ + l.count_down(); + }); + l.wait(); + t.join(); + + return 0; +} Index: libcxx/test/std/thread/thread.latch/try_wait.pass.cpp =================================================================== --- /dev/null +++ libcxx/test/std/thread/thread.latch/try_wait.pass.cpp @@ -0,0 +1,27 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// UNSUPPORTED: libcpp-has-no-threads + +// + +#include +#include + +#include "test_macros.h" + +int main(int, char**) +{ + std::latch l(1); + + l.count_down(); + bool const b = l.try_wait(); + assert(b); + + return 0; +} Index: libcxx/test/std/thread/thread.latch/version.pass.cpp =================================================================== --- /dev/null +++ libcxx/test/std/thread/thread.latch/version.pass.cpp @@ -0,0 +1,24 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// UNSUPPORTED: libcpp-has-no-threads + +// + +#include + +#include "test_macros.h" + +#ifndef _LIBCPP_VERSION +#error _LIBCPP_VERSION not defined +#endif + +int main(int, char**) +{ + return 0; +} Index: libcxx/test/std/thread/thread.semaphore/acquire.pass.cpp =================================================================== --- /dev/null +++ libcxx/test/std/thread/thread.semaphore/acquire.pass.cpp @@ -0,0 +1,30 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// UNSUPPORTED: libcpp-has-no-threads + +// + +#include +#include + +#include "test_macros.h" + +int main(int, char**) +{ + std::counting_semaphore<> s(2); + + std::thread t([&](){ + s.acquire(); + }); + t.join(); + + s.acquire(); + + return 0; +} Index: libcxx/test/std/thread/thread.semaphore/binary.pass.cpp =================================================================== --- /dev/null +++ libcxx/test/std/thread/thread.semaphore/binary.pass.cpp @@ -0,0 +1,37 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// UNSUPPORTED: libcpp-has-no-threads + +// + +#include +#include +#include + +#include "test_macros.h" + +int main(int, char**) +{ + std::binary_semaphore s(1); + + auto l = [&](){ + for(int i = 0; i < 1024; ++i) { + s.acquire(); + std::this_thread::sleep_for(std::chrono::microseconds(1)); + s.release(); + } + }; + + std::thread t(l); + l(); + + t.join(); + + return 0; +} Index: libcxx/test/std/thread/thread.semaphore/max.pass.cpp =================================================================== --- /dev/null +++ libcxx/test/std/thread/thread.semaphore/max.pass.cpp @@ -0,0 +1,27 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// UNSUPPORTED: libcpp-has-no-threads + +// + +#include +#include + +#include "test_macros.h" + +int main(int, char**) +{ + static_assert(std::counting_semaphore<>::max() > 0); + static_assert(std::counting_semaphore<1>::max() >= 1); + static_assert(std::counting_semaphore::max()>::max() >= 1); + static_assert(std::counting_semaphore::max()>::max() >= 1); + static_assert(std::counting_semaphore::max()>::max() >= 1); + static_assert(std::counting_semaphore<1>::max() == std::binary_semaphore::max()); + return 0; +} Index: libcxx/test/std/thread/thread.semaphore/release.pass.cpp =================================================================== --- /dev/null +++ libcxx/test/std/thread/thread.semaphore/release.pass.cpp @@ -0,0 +1,33 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// UNSUPPORTED: libcpp-has-no-threads + +// + +#include +#include + +#include "test_macros.h" + +int main(int, char**) +{ + std::counting_semaphore<> s(0); + + s.release(); + s.acquire(); + + std::thread t([&](){ + s.acquire(); + }); + s.release(2); + t.join(); + s.acquire(); + + return 0; +} Index: libcxx/test/std/thread/thread.semaphore/timed.pass.cpp =================================================================== --- /dev/null +++ libcxx/test/std/thread/thread.semaphore/timed.pass.cpp @@ -0,0 +1,43 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// UNSUPPORTED: libcpp-has-no-threads + +// + +#include +#include +#include + +#include "test_macros.h" + +int main(int, char**) +{ + auto const start = std::chrono::steady_clock::now(); + + std::counting_semaphore<> s(0); + + assert(!s.try_acquire_until(start + std::chrono::milliseconds(250))); + assert(!s.try_acquire_for(std::chrono::milliseconds(250))); + + std::thread t([&](){ + std::this_thread::sleep_for(std::chrono::milliseconds(250)); + s.release(); + std::this_thread::sleep_for(std::chrono::milliseconds(250)); + s.release(); + }); + + assert(s.try_acquire_until(start + std::chrono::seconds(2))); + assert(s.try_acquire_for(std::chrono::seconds(2))); + t.join(); + + auto const end = std::chrono::steady_clock::now(); + assert(end - start < std::chrono::seconds(10)); + + return 0; +} Index: libcxx/test/std/thread/thread.semaphore/try_acquire.pass.cpp =================================================================== --- /dev/null +++ libcxx/test/std/thread/thread.semaphore/try_acquire.pass.cpp @@ -0,0 +1,33 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// UNSUPPORTED: libcpp-has-no-threads + +// + +#include +#include + +#include "test_macros.h" + +int main(int, char**) +{ + std::counting_semaphore<> s(1); + + assert(s.try_acquire()); + s.release(); + assert(s.try_acquire()); + s.release(2); + std::thread t([&](){ + assert(s.try_acquire()); + }); + t.join(); + assert(s.try_acquire()); + + return 0; +} Index: libcxx/test/std/thread/thread.semaphore/version.pass.cpp =================================================================== --- /dev/null +++ libcxx/test/std/thread/thread.semaphore/version.pass.cpp @@ -0,0 +1,24 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// UNSUPPORTED: libcpp-has-no-threads + +// + +#include + +#include "test_macros.h" + +#ifndef _LIBCPP_VERSION +#error _LIBCPP_VERSION not defined +#endif + +int main(int, char**) +{ + return 0; +}