]>
Commit | Line | Data |
---|---|---|
b32b8144 FG |
1 | |
2 | // Copyright Oliver Kowalke 2016. | |
3 | // Distributed under the Boost Software License, Version 1.0. | |
4 | // (See accompanying file LICENSE_1_0.txt or copy at | |
5 | // http://www.boost.org/LICENSE_1_0.txt) | |
6 | ||
7 | #ifndef BOOST_FIBERS_SPINLOCK_TTAS_ADAPTIVE_FUTEX_H | |
8 | #define BOOST_FIBERS_SPINLOCK_TTAS_ADAPTIVE_FUTEX_H | |
9 | ||
20effc67 | 10 | #include <algorithm> |
b32b8144 FG |
11 | #include <atomic> |
12 | #include <cmath> | |
13 | #include <random> | |
14 | #include <thread> | |
15 | ||
16 | #include <boost/fiber/detail/config.hpp> | |
17 | #include <boost/fiber/detail/cpu_relax.hpp> | |
18 | #include <boost/fiber/detail/futex.hpp> | |
19 | ||
20 | // based on informations from: | |
21 | // https://software.intel.com/en-us/articles/benefitting-power-and-performance-sleep-loops | |
22 | // https://software.intel.com/en-us/articles/long-duration-spin-wait-loops-on-hyper-threading-technology-enabled-intel-processors | |
23 | ||
24 | namespace boost { | |
25 | namespace fibers { | |
26 | namespace detail { | |
27 | ||
28 | class spinlock_ttas_adaptive_futex { | |
29 | private: | |
30 | template< typename FBSplk > | |
31 | friend class spinlock_rtm; | |
32 | ||
33 | std::atomic< std::int32_t > value_{ 0 }; | |
34 | std::atomic< std::int32_t > retries_{ 0 }; | |
35 | ||
36 | public: | |
37 | spinlock_ttas_adaptive_futex() = default; | |
38 | ||
39 | spinlock_ttas_adaptive_futex( spinlock_ttas_adaptive_futex const&) = delete; | |
40 | spinlock_ttas_adaptive_futex & operator=( spinlock_ttas_adaptive_futex const&) = delete; | |
41 | ||
42 | void lock() noexcept { | |
43 | static thread_local std::minstd_rand generator{ std::random_device{}() }; | |
44 | std::int32_t collisions = 0, retries = 0, expected = 0; | |
45 | const std::int32_t prev_retries = retries_.load( std::memory_order_relaxed); | |
46 | const std::int32_t max_relax_retries = (std::min)( | |
47 | static_cast< std::int32_t >( BOOST_FIBERS_SPIN_BEFORE_SLEEP0), 2 * prev_retries + 10); | |
48 | const std::int32_t max_sleep_retries = (std::min)( | |
49 | static_cast< std::int32_t >( BOOST_FIBERS_SPIN_BEFORE_YIELD), 2 * prev_retries + 10); | |
50 | // after max. spins or collisions suspend via futex | |
51 | while ( retries++ < BOOST_FIBERS_RETRY_THRESHOLD) { | |
52 | // avoid using multiple pause instructions for a delay of a specific cycle count | |
53 | // the delay of cpu_relax() (pause on Intel) depends on the processor family | |
54 | // the cycle count can not guaranteed from one system to the next | |
55 | // -> check the shared variable 'value_' in between each cpu_relax() to prevent | |
56 | // unnecessarily long delays on some systems | |
57 | // test shared variable 'status_' | |
58 | // first access to 'value_' -> chache miss | |
59 | // sucessive acccess to 'value_' -> cache hit | |
60 | // if 'value_' was released by other fiber | |
61 | // cached 'value_' is invalidated -> cache miss | |
62 | if ( 0 != ( expected = value_.load( std::memory_order_relaxed) ) ) { | |
63 | #if !defined(BOOST_FIBERS_SPIN_SINGLE_CORE) | |
64 | if ( max_relax_retries > retries) { | |
65 | // give CPU a hint that this thread is in a "spin-wait" loop | |
66 | // delays the next instruction's execution for a finite period of time (depends on processor family) | |
67 | // the CPU is not under demand, parts of the pipeline are no longer being used | |
68 | // -> reduces the power consumed by the CPU | |
69 | // -> prevent pipeline stalls | |
70 | cpu_relax(); | |
71 | } else if ( max_sleep_retries > retries) { | |
72 | // std::this_thread::sleep_for( 0us) has a fairly long instruction path length, | |
73 | // combined with an expensive ring3 to ring 0 transition costing about 1000 cycles | |
74 | // std::this_thread::sleep_for( 0us) lets give up this_thread the remaining part of its time slice | |
75 | // if and only if a thread of equal or greater priority is ready to run | |
76 | static constexpr std::chrono::microseconds us0{ 0 }; | |
77 | std::this_thread::sleep_for( us0); | |
78 | } else { | |
79 | // std::this_thread::yield() allows this_thread to give up the remaining part of its time slice, | |
80 | // but only to another thread on the same processor | |
81 | // instead of constant checking, a thread only checks if no other useful work is pending | |
82 | std::this_thread::yield(); | |
83 | } | |
84 | #else | |
85 | // std::this_thread::yield() allows this_thread to give up the remaining part of its time slice, | |
86 | // but only to another thread on the same processor | |
87 | // instead of constant checking, a thread only checks if no other useful work is pending | |
88 | std::this_thread::yield(); | |
89 | #endif | |
90 | } else if ( ! value_.compare_exchange_strong( expected, 1, std::memory_order_acquire) ) { | |
91 | // spinlock now contended | |
92 | // utilize 'Binary Exponential Backoff' algorithm | |
93 | // linear_congruential_engine is a random number engine based on Linear congruential generator (LCG) | |
94 | std::uniform_int_distribution< std::int32_t > distribution{ | |
95 | 0, static_cast< std::int32_t >( 1) << (std::min)(collisions, static_cast< std::int32_t >( BOOST_FIBERS_CONTENTION_WINDOW_THRESHOLD)) }; | |
96 | const std::int32_t z = distribution( generator); | |
97 | ++collisions; | |
98 | for ( std::int32_t i = 0; i < z; ++i) { | |
99 | // -> reduces the power consumed by the CPU | |
100 | // -> prevent pipeline stalls | |
101 | cpu_relax(); | |
102 | } | |
103 | } else { | |
104 | // success, lock acquired | |
105 | retries_.store( prev_retries + (retries - prev_retries) / 8, std::memory_order_relaxed); | |
106 | return; | |
107 | } | |
108 | } | |
109 | // failure, lock not acquired | |
110 | // pause via futex | |
111 | if ( 2 != expected) { | |
112 | expected = value_.exchange( 2, std::memory_order_acquire); | |
113 | } | |
114 | while ( 0 != expected) { | |
115 | futex_wait( & value_, 2); | |
116 | expected = value_.exchange( 2, std::memory_order_acquire); | |
117 | } | |
118 | // success, lock acquired | |
119 | retries_.store( prev_retries + (retries - prev_retries) / 8, std::memory_order_relaxed); | |
120 | } | |
121 | ||
122 | bool try_lock() noexcept { | |
123 | std::int32_t expected = 0; | |
124 | return value_.compare_exchange_strong( expected, 1, std::memory_order_acquire); | |
125 | } | |
126 | ||
127 | void unlock() noexcept { | |
128 | if ( 1 != value_.fetch_sub( 1, std::memory_order_acquire) ) { | |
129 | value_.store( 0, std::memory_order_release); | |
130 | futex_wake( & value_); | |
131 | } | |
132 | } | |
133 | }; | |
134 | ||
135 | }}} | |
136 | ||
137 | #endif // BOOST_FIBERS_SPINLOCK_TTAS_ADAPTIVE_FUTEX_H |