| /* |
| |
| Copyright (c) 2017, NVIDIA Corporation |
| All rights reserved. |
| |
| Redistribution and use in source and binary forms, with or without modification, |
| are permitted provided that the following conditions are met: |
| |
| 1. Redistributions of source code must retain the above copyright notice, this |
| list of conditions and the following disclaimer. |
| |
| 2. Redistributions in binary form must reproduce the above copyright notice, |
| this list of conditions and the following disclaimer in the documentation |
| and/or other materials provided with the distribution. |
| |
| THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND |
| ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED |
| WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. |
| IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, |
| INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, |
| BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
| DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF |
| LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE |
| OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED |
| OF THE POSSIBILITY OF SUCH DAMAGE. |
| |
| */ |
| |
| #ifndef __semaphore__ |
| #define __semaphore__ |
| |
| #include "details/config.hpp" |
| |
| #ifdef __semaphore_cuda |
| namespace cuda |
| { |
| #else |
| namespace std |
| { |
| #endif |
| namespace experimental |
| { |
| inline namespace v1 |
| { |
| |
| // 32.10, semaphore type and operations |
| enum semaphore_notify |
| { |
| semaphore_notify_all, |
| semaphore_notify_one, |
| semaphore_notify_none |
| }; |
| struct binary_semaphore; |
| struct counting_semaphore; |
| struct synchronic; |
| |
| // 32.10.2, initialization |
| #define ATOMIC_SEM_INIT 0 //see below |
| |
| // 32.10.3, atomic free functions for waiting |
| template <class T> |
| __semaphore_abi void atomic_signal_explicit(const atomic<T> *, semaphore_notify); |
| template <class T> |
| __semaphore_abi void atomic_signal(const atomic<T> *); |
| template <class T, class V> |
| __semaphore_abi void atomic_wait_explicit(const atomic<T> *, V, std::memory_order); |
| template <class T, class V> |
| __semaphore_abi void atomic_wait(const atomic<T> *, V); |
| template <class T, class V> |
| __semaphore_abi bool atomic_try_wait_explicit(const atomic<T> *, V, std::memory_order); |
| template <class T, class V> |
| __semaphore_abi bool atomic_try_wait(const atomic<T> *,V); |
| |
| struct binary_semaphore |
| { |
| using count_type = uint32_t; |
| |
| static constexpr count_type max = 1; |
| |
| __semaphore_abi inline void release() noexcept |
| { |
| if(__stolen) |
| __stolen = false; |
| else |
| #ifdef __semaphore_cuda |
| __tocket.fetch_add(1, std::memory_order_relaxed); |
| #else |
| __tocket.store(__tocket.load(std::memory_order_relaxed)+1, std::memory_order_relaxed); |
| #endif |
| #ifdef __semaphore_fast_path |
| count_type old = __valubit; |
| if (__semaphore_expect(!__atom.compare_exchange_strong(old, 0, std::memory_order_acquire, std::memory_order_relaxed), 0)) |
| __release_slow(old); |
| #else |
| __atom.fetch_and(~__valubit, std::memory_order_acquire); |
| #endif |
| } |
| __semaphore_abi inline bool try_acquire() noexcept |
| { |
| count_type old = 0; |
| for (int i = 0;i < 64; ++i) { |
| if(__semaphore_expect(__atom.compare_exchange_strong(old = 0, __valubit, std::memory_order_acquire, std::memory_order_relaxed),1)) |
| return __stolen = true; |
| for(; old != 0 && i < 64; ++i) { |
| details::__semaphore_yield(); |
| old = __atom.load(std::memory_order_relaxed); |
| } |
| } |
| return false; |
| } |
| __semaphore_abi inline void acquire() noexcept |
| { |
| if (__semaphore_expect(try_acquire(), 1)) |
| return; |
| __acquire_slow(); |
| } |
| template <class Clock, class Duration> |
| __semaphore_abi bool try_acquire_until(const std::chrono::time_point<Clock, Duration>& abs_time) |
| { |
| if (__semaphore_expect(try_acquire(), 1)) |
| return true; |
| return __acquire_slow_timed(abs_time); |
| } |
| template <class Rep, class Period> |
| __semaphore_abi bool try_acquire_for(const std::chrono::duration<Rep, Period>& rel_time) |
| { |
| if (__semaphore_expect(try_acquire(), 1)) |
| return true; |
| return __acquire_slow_timed(details::__semaphore_clock::now() + rel_time); |
| } |
| |
| __semaphore_abi constexpr binary_semaphore(count_type desired) noexcept : __atom(desired ? 0 : 1), __ticket(0), __tocket(0), __stolen(false) |
| { |
| } |
| |
| binary_semaphore(const binary_semaphore&) = delete; |
| binary_semaphore &operator=(const binary_semaphore&) = delete; |
| |
| static constexpr count_type __valubit = 1; |
| static constexpr count_type __lockbit = 2; |
| static constexpr count_type __slowbit = 4; |
| static constexpr count_type __contbit = 8; |
| |
| #ifdef __semaphore_fast_path |
| __semaphore_abi void __release_slow(count_type old) noexcept; |
| #endif |
| |
| __semaphore_abi void __acquire_slow() noexcept; |
| |
| bool __acquire_slow_timed(std::chrono::time_point<details::__semaphore_clock, details::__semaphore_duration> const &) noexcept; |
| |
| atomic<count_type> __atom; |
| atomic<count_type> __ticket; |
| atomic<count_type> __tocket; |
| bool __stolen; |
| }; |
| |
| #ifndef __semaphore_sem |
| |
| struct counting_semaphore |
| { |
| using count_type = int32_t; |
| |
| private: |
| #ifdef __semaphore_fast_path |
| static constexpr count_type __valumask = ~3, |
| __contmask = 2, |
| __lockmask = 1, |
| __shift = 2; |
| #else |
| static constexpr count_type __valumask = ~0, |
| __contmask = 0, |
| __lockmask = 0, |
| __shift = 0; |
| #endif |
| public: |
| static constexpr count_type max = (__valumask >> (__shift ? __shift : 1)); |
| |
| __semaphore_abi inline void release(std::memory_order order = std::memory_order_seq_cst) noexcept |
| { |
| release(1, semaphore_notify_all, order); |
| } |
| __semaphore_abi inline void release(count_type term, std::memory_order order = std::memory_order_seq_cst) noexcept |
| { |
| release(term, semaphore_notify_all, order); |
| } |
| __semaphore_abi inline void release(count_type term, semaphore_notify notify, std::memory_order order = std::memory_order_seq_cst) noexcept |
| { |
| |
| #ifdef __semaphore_fast_path |
| count_type old = 0, set = term << __shift; |
| bool success = atom.compare_exchange_weak(old, set, order, std::memory_order_relaxed); |
| while (__semaphore_expect(!success && !(old & (__contmask | __lockmask)), 0)) |
| { |
| set = old + (term << __shift); |
| success = atom.compare_exchange_weak(old, set, order, std::memory_order_relaxed); |
| } |
| if (__semaphore_expect(!success, 0)) |
| __fetch_add_slow(term, old, order, notify); |
| #else |
| count_type old = atom.fetch_add(term, order); |
| #endif |
| } |
| |
| __semaphore_abi inline void acquire(std::memory_order order = std::memory_order_seq_cst) noexcept |
| { |
| |
| while (__semaphore_expect(!__fetch_sub_if(order), 0)) |
| { |
| bool const success = __acquire_fast(order); |
| if (__semaphore_expect(!success, 0)) |
| __acquire_slow(order); |
| } |
| } |
| __semaphore_abi inline bool try_acquire(std::memory_order order = std::memory_order_seq_cst) noexcept |
| { |
| |
| return __fetch_sub_if(order); |
| } |
| template <class Clock, class Duration> |
| __semaphore_abi bool try_acquire_until(std::chrono::time_point<Clock, Duration> const &abs_time, std::memory_order order = std::memory_order_seq_cst) |
| { |
| |
| while (__semaphore_expect(!__fetch_sub_if(order), 0)) |
| { |
| bool success = __acquire_fast(order); |
| if (__semaphore_expect(!success, 0)) |
| success = __acquire_slow_timed(abs_time, order); |
| if (__semaphore_expect(!success, 0)) |
| return false; |
| } |
| return true; |
| } |
| template <class Rep, class Period> |
| __semaphore_abi bool try_acquire_for(std::chrono::duration<Rep, Period> const &rel_time, std::memory_order order = std::memory_order_seq_cst) |
| { |
| |
| if (__semaphore_expect(__fetch_sub_if(order), 1)) |
| return true; |
| else |
| return try_acquire_until(details::__semaphore_clock::now() + std::chrono::duration_cast<std::chrono::nanoseconds>(rel_time), order); |
| } |
| |
| __semaphore_abi constexpr counting_semaphore(count_type desired) noexcept : atom(desired << __shift) |
| { |
| } |
| counting_semaphore(const counting_semaphore &) = delete; |
| counting_semaphore &operator=(const counting_semaphore &) = delete; |
| |
| private: |
| __semaphore_abi bool __fetch_sub_if_slow(count_type old, std::memory_order order) noexcept; |
| |
| __semaphore_abi bool __fetch_sub_if(std::memory_order order) noexcept |
| { |
| |
| count_type old = 1 << __shift, set = 0; |
| bool retcode = atom.compare_exchange_weak(old, set, order, std::memory_order_relaxed); |
| if (__semaphore_expect(!retcode && (old >> __shift) >= 1, 0)) |
| { |
| old &= __valumask; |
| set = old - (1 << __shift); |
| retcode = atom.compare_exchange_weak(old, set, order, std::memory_order_relaxed); |
| } |
| if (__semaphore_expect(!retcode && (old >> __shift) >= 1, 0)) |
| retcode = __fetch_sub_if_slow(old, order); |
| return retcode; |
| } |
| |
| #ifdef __semaphore_fast_path |
| __semaphore_abi void __fetch_add_slow(count_type term, count_type old, std::memory_order order, semaphore_notify notify) noexcept; |
| #endif |
| |
| __semaphore_abi bool __acquire_slow_timed(std::chrono::time_point<details::__semaphore_clock, details::__semaphore_duration> const &abs_time, std::memory_order order) noexcept; |
| |
| __semaphore_abi void __acquire_slow(std::memory_order order) noexcept; |
| |
| __semaphore_abi inline bool __acquire_fast(std::memory_order order) noexcept |
| { |
| |
| auto value = (atom.load(order) >> __shift); |
| if (__semaphore_expect(value >= 1, 1)) |
| return true; |
| for (int i = 0; i < 32; ++i) |
| { |
| details::__semaphore_yield(); |
| value = (atom.load(order) >> __shift); |
| if (__semaphore_expect(value >= 1, 1)) |
| return true; |
| } |
| return false; |
| } |
| |
| atomic<count_type> atom; |
| |
| friend struct synchronic; |
| }; |
| |
| #else |
| |
| struct counting_semaphore |
| { |
| using count_type = int32_t; |
| |
| static constexpr count_type max = (numeric_limits<count_type>::max)() >> 1; |
| |
| __semaphore_abi inline void release(std::memory_order order = std::memory_order_seq_cst) noexcept |
| { |
| release(1, semaphore_notify_all, order); |
| } |
| __semaphore_abi inline void release(count_type term, std::memory_order order = std::memory_order_seq_cst) noexcept |
| { |
| release(term, semaphore_notify_all, order); |
| } |
| __semaphore_abi inline void release(count_type term, semaphore_notify, std::memory_order order = std::memory_order_seq_cst) noexcept |
| { |
| count_type old = __frontbuffer.load(std::memory_order_relaxed); |
| while (1) |
| { |
| old &= ~1; |
| if (__frontbuffer.compare_exchange_weak(old, old + (term << 1) + 1, order, std::memory_order_relaxed)) |
| break; |
| } |
| if (old >> 1 < 0) |
| { // was it depleted? |
| count_type inc = (min)(-(old >> 1), term); |
| #ifdef __semaphore_back_buffered |
| __backbuffer.fetch_add(inc - 1); |
| inc = 1; |
| #endif |
| count_type const result = details::__semaphore_sem_post(__semaphore, inc); |
| #ifdef WIN32 |
| if (!result) |
| { |
| auto d = GetLastError(); |
| assert(d == ERROR_SUCCESS); |
| } |
| #endif |
| assert(result); |
| } |
| __frontbuffer.fetch_sub(1); |
| } |
| |
| inline void acquire(std::memory_order order = std::memory_order_seq_cst) noexcept |
| { |
| __acquire_fast(); |
| __acquire_slow(order); |
| } |
| |
| template <class Rep, class Period> |
| bool try_acquire_for(std::chrono::duration<Rep, Period> const &rel_time, std::memory_order order = std::memory_order_seq_cst) |
| { |
| |
| __acquire_fast(); |
| if (__frontbuffer.fetch_sub(2, order) >> 1 > 0) |
| return true; |
| auto const result = details::__semaphore_sem_wait_timed(__semaphore, rel_time); |
| if (result) |
| __backfill(); |
| return result; |
| } |
| template <class Clock, class Duration> |
| bool try_acquire_until(std::chrono::time_point<Clock, Duration> const &abs_time, std::memory_order order = std::memory_order_seq_cst) |
| { |
| |
| return try_acquire_for(abs_time - Clock::now(), order); |
| } |
| inline bool try_acquire(std::memory_order order = std::memory_order_seq_cst) noexcept |
| { |
| |
| __acquire_fast(); |
| if (__frontbuffer.fetch_sub(2, order) >> 1 > 0) |
| return true; |
| return try_acquire_for(std::chrono::nanoseconds(0), order); |
| } |
| counting_semaphore(count_type desired) noexcept |
| : __frontbuffer { desired << 1 } |
| #ifdef __semaphore_back_buffered |
| , __backbuffer{ 0 } |
| #endif |
| { |
| auto const result = details::__semaphore_sem_init(__semaphore, desired); |
| #ifdef WIN32 |
| if (!result) |
| { |
| auto d = GetLastError(); |
| assert(d == ERROR_SUCCESS); |
| } |
| #endif |
| assert(result); |
| } |
| ~counting_semaphore() |
| { |
| |
| while (__frontbuffer.load(std::memory_order_acquire) & 1) |
| ; |
| auto const result = details::__semaphore_sem_destroy(__semaphore); |
| assert(result); |
| } |
| counting_semaphore(const counting_semaphore &) = delete; |
| counting_semaphore &operator=(const counting_semaphore &) = delete; |
| |
| private: |
| inline void __acquire_fast() noexcept |
| { |
| |
| if (__semaphore_expect(__frontbuffer.load(std::memory_order_relaxed) > 1, 1)) |
| return; |
| for (int i = 0; i < 32; ++i) |
| { |
| details::__semaphore_yield(); |
| if (__semaphore_expect(__frontbuffer.load(std::memory_order_relaxed) > 1, 1)) |
| return; |
| } |
| } |
| |
| inline void __acquire_slow(std::memory_order order) noexcept { |
| if (__frontbuffer.fetch_sub(2, order) >> 1 > 0) |
| return; |
| count_type const result = details::__semaphore_sem_wait(__semaphore); |
| #ifdef WIN32 |
| if (!result) |
| { |
| auto d = GetLastError(); |
| assert(d == ERROR_SUCCESS); |
| } |
| #endif |
| assert(result); |
| __backfill(); |
| } |
| |
| inline void __backfill() |
| { |
| #ifdef __semaphore_back_buffered |
| if (__semaphore_expect(__backbuffer.load(std::memory_order_relaxed) == 0, 1)) |
| return; |
| if (__semaphore_expect(__backbuffer.fetch_sub(1, std::memory_order_relaxed) == 0, 0)) |
| { |
| __backbuffer.fetch_add(1, std::memory_order_relaxed); // put back |
| return; |
| } |
| auto const result = details::__semaphore_sem_post(__semaphore, 1); |
| assert(result); |
| #endif |
| } |
| |
| details::__semaphore_sem_t __semaphore; |
| atomic<count_type> __frontbuffer; |
| #ifdef __semaphore_back_buffered |
| atomic<count_type> __backbuffer; |
| #endif |
| |
| friend struct synchronic; |
| }; |
| |
| #endif |
| |
| #ifndef __semaphore_cuda |
| #define __semaphore_abi_a __semaphore_abi |
| #else |
| #define __semaphore_abi_a __semaphore_abi static |
| #endif |
| |
| struct synchronic { |
| |
| template <class T> |
| __semaphore_abi_a void signal(const atomic<T>*, semaphore_notify notify = semaphore_notify_all) noexcept |
| { |
| #ifndef __semaphore_cuda |
| if (__semaphore_expect(!__reversebuffer.load(std::memory_order_relaxed), 1)) |
| return; |
| (atomic_thread_fence)(std::memory_order_seq_cst); |
| int const waiting = __reversebuffer.exchange(0, std::memory_order_relaxed); |
| if (__semaphore_expect(waiting, 0)) |
| __sem.release(waiting, notify, std::memory_order_release); |
| #endif |
| } |
| |
| template <class T, class V> |
| __semaphore_abi_a void wait_cas(atomic<T>* a, V oldval, V newval, std::memory_order order = std::memory_order_seq_cst) noexcept |
| { |
| for (int i = 0; i < 16; ++i, details::__semaphore_yield()) { |
| auto old = oldval; |
| if (__semaphore_expect(a->compare_exchange_weak(old, newval, order), 1)) |
| return; |
| } |
| details::__semaphore_exponential_backoff b; |
| while (1) |
| { |
| b.sleep(); |
| auto old = oldval; |
| if (__semaphore_expect(a->compare_exchange_weak(old, newval, order), 1)) |
| return; |
| } |
| } |
| |
| template <class T, class V> |
| __semaphore_abi_a void wait(atomic<T> const *a, V oldval, std::memory_order order = std::memory_order_seq_cst) noexcept |
| { |
| for (int i = 0; i < 16; ++i, details::__semaphore_yield()) |
| if (__semaphore_expect(a->load(order) != oldval, 1)) |
| return; |
| details::__semaphore_exponential_backoff b; |
| do |
| { |
| #ifndef __semaphore_cuda |
| __reversebuffer.fetch_add(1, std::memory_order_relaxed); |
| (atomic_thread_fence)(std::memory_order_seq_cst); |
| if (__semaphore_expect(a->load(order) != oldval, 0)) |
| { |
| auto const waiting = __reversebuffer.exchange(0, std::memory_order_relaxed); |
| switch (waiting) |
| { |
| case 0: |
| __sem.acquire(std::memory_order_relaxed); // uuuuuuuuhhhh, this is really weird for for/until |
| case 1: |
| break; |
| default: |
| __sem.release(waiting - 1, semaphore_notify_all, std::memory_order_relaxed); break; |
| } |
| break; |
| } |
| __sem.__acquire_slow(std::memory_order_relaxed); |
| #else |
| b.sleep(); |
| #endif |
| } while (a->load(order) == oldval); |
| } |
| |
| template <class T, class V> |
| __semaphore_abi_a bool try_wait(atomic<T> const *a, V oldval, std::memory_order order = std::memory_order_seq_cst) noexcept |
| { |
| |
| for (int i = 0; i < 128; ++i, details::__semaphore_yield()) |
| if (__semaphore_expect(a->load(order) != oldval, 1)) |
| return true; |
| return false; |
| } |
| |
| __semaphore_abi inline synchronic(counting_semaphore::count_type desired) noexcept |
| #ifndef __semaphore_cuda |
| : __sem(desired), __reversebuffer{0} |
| #endif |
| { |
| } |
| synchronic(const synchronic &) = delete; |
| synchronic &operator=(const synchronic &) = delete; |
| |
| #ifndef __semaphore_cuda |
| counting_semaphore __sem; |
| atomic<counting_semaphore::count_type> __reversebuffer{ 0 }; |
| #endif |
| }; |
| |
| #ifndef __semaphore_cuda |
| extern __semaphore_abi synchronic *__atomic_wait_get_semaphore(void const *ptr); |
| #endif |
| |
| template <class T> |
| __semaphore_abi void atomic_signal_explicit(const atomic<T>*a, semaphore_notify notify) |
| { |
| #ifndef __semaphore_cuda |
| __atomic_wait_get_semaphore(a)-> |
| #else |
| synchronic:: |
| #endif |
| signal(a, notify); |
| } |
| template <class T> |
| __semaphore_abi void atomic_signal(const atomic<T>* a) |
| { |
| #ifndef __semaphore_cuda |
| __atomic_wait_get_semaphore(a)-> |
| #else |
| synchronic:: |
| #endif |
| signal(a); |
| } |
| template <class T, class V> |
| __semaphore_abi void atomic_wait_cas_explicit(atomic<T>* a, V oldval, V newval, std::memory_order order) |
| { |
| #ifndef __semaphore_cuda |
| __atomic_wait_get_semaphore(a)-> |
| #else |
| synchronic:: |
| #endif |
| wait_cas(a, oldval, newval, order); |
| } |
| template <class T, class V> |
| __semaphore_abi void atomic_wait_cas(atomic<T>* a, V oldval, V newval) |
| { |
| #ifndef __semaphore_cuda |
| __atomic_wait_get_semaphore(a)-> |
| #else |
| synchronic:: |
| #endif |
| wait_cas(a, oldval, newval); |
| } |
| template <class T, class V> |
| __semaphore_abi void atomic_wait_explicit(const atomic<T>* a, V oldval, std::memory_order order) |
| { |
| #ifndef __semaphore_cuda |
| __atomic_wait_get_semaphore(a)-> |
| #else |
| synchronic:: |
| #endif |
| wait(a, oldval, order); |
| } |
| template <class T, class V> |
| __semaphore_abi void atomic_wait(const atomic<T>* a, V oldval) |
| { |
| #ifndef __semaphore_cuda |
| __atomic_wait_get_semaphore(a)-> |
| #else |
| synchronic:: |
| #endif |
| wait(a, oldval); |
| } |
| template <class T, class V> |
| __semaphore_abi void atomic_try_wait_explicit(const atomic<T>* a, V oldval, std::memory_order order) |
| { |
| #ifndef __semaphore_cuda |
| __atomic_wait_get_semaphore(a)-> |
| #else |
| synchronic:: |
| #endif |
| try_wait(a, oldval, order); |
| } |
| template <class T, class V> |
| __semaphore_abi void atomic_try_wait(const atomic<T>* a, V oldval) |
| { |
| #ifndef __semaphore_cuda |
| __atomic_wait_get_semaphore(a)-> |
| #else |
| synchronic:: |
| #endif |
| try_wait(a, oldval); |
| } |
| |
| } |
| } // namespace experimental |
| } |
| |
| #endif //__semaphore__ |
