ceph/src/boost/boost/fiber/detail/spinlock_ttas_futex.hpp

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