ceph/src/boost/libs/interprocess/include/boost/interprocess/sync/detail/condition_algorithm_8a.hpp

   1 //////////////////////////////////////////////////////////////////////////////
   2 //
   3 // (C) Copyright Ion Gaztanaga 2005-2012. Distributed under the Boost
   4 // Software License, Version 1.0. (See accompanying file
   5 // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
   6 //
   7 // See http://www.boost.org/libs/interprocess for documentation.
   8 //
   9 //////////////////////////////////////////////////////////////////////////////
  10
  11 #ifndef BOOST_INTERPROCESS_DETAIL_CONDITION_ALGORITHM_8A_HPP
  12 #define BOOST_INTERPROCESS_DETAIL_CONDITION_ALGORITHM_8A_HPP
  13
  14 #ifndef BOOST_CONFIG_HPP
  15 #  include <boost/config.hpp>
  16 #endif
  17 #
  18 #if defined(BOOST_HAS_PRAGMA_ONCE)
  19 #  pragma once
  20 #endif
  21
  22 #include <boost/interprocess/detail/config_begin.hpp>
  23 #include <boost/interprocess/detail/workaround.hpp>
  24 #include <boost/interprocess/sync/scoped_lock.hpp>
  25 #include <boost/interprocess/sync/detail/locks.hpp>
  26 #include <limits>
  27
  28 namespace boost {
  29 namespace interprocess {
  30 namespace ipcdetail {
  31
  32 ////////////////////////////////////////////////////////////////////////
  33 ////////////////////////////////////////////////////////////////////////
  34 ////////////////////////////////////////////////////////////////////////
  35 //
  36 // Condition variable algorithm taken from pthreads-win32 discussion.
  37 //
  38 // The algorithm was developed by Alexander Terekhov in colaboration with
  39 // Louis Thomas.
  40 //
  41 //     Algorithm 8a / IMPL_SEM,UNBLOCK_STRATEGY == UNBLOCK_ALL
  42 //
  43 // semBlockLock - bin.semaphore
  44 // semBlockQueue - semaphore
  45 // mtxExternal - mutex or CS
  46 // mtxUnblockLock - mutex or CS
  47 // nWaitersGone - int
  48 // nWaitersBlocked - int
  49 // nWaitersToUnblock - int
  50 //
  51 // wait( timeout ) {
  52 //
  53 //   [auto: register int result          ]     // error checking omitted
  54 //   [auto: register int nSignalsWasLeft ]
  55 //   [auto: register int nWaitersWasGone ]
  56 //
  57 //   sem_wait( semBlockLock );
  58 //   nWaitersBlocked++;
  59 //   sem_post( semBlockLock );
  60 //
  61 //   unlock( mtxExternal );
  62 //   bTimedOut = sem_wait( semBlockQueue,timeout );
  63 //
  64 //   lock( mtxUnblockLock );
  65 //   if ( 0 != (nSignalsWasLeft = nWaitersToUnblock) ) {
  66 //     if ( bTimedOut ) {                       // timeout (or canceled)
  67 //       if ( 0 != nWaitersBlocked ) {
  68 //         nWaitersBlocked--;
  69 //       }
  70 //       else {
  71 //         nWaitersGone++;                     // count spurious wakeups.
  72 //       }
  73 //     }
  74 //     if ( 0 == --nWaitersToUnblock ) {
  75 //       if ( 0 != nWaitersBlocked ) {
  76 //         sem_post( semBlockLock );           // open the gate.
  77 //         nSignalsWasLeft = 0;                // do not open the gate
  78 //                                             // below again.
  79 //       }
  80 //       else if ( 0 != (nWaitersWasGone = nWaitersGone) ) {
  81 //         nWaitersGone = 0;
  82 //       }
  83 //     }
  84 //   }
  85 //   else if ( INT_MAX/2 == ++nWaitersGone ) { // timeout/canceled or
  86 //                                             // spurious semaphore :-)
  87 //     sem_wait( semBlockLock );
  88 //     nWaitersBlocked -= nWaitersGone;     // something is going on here
  89 //                                          //  - test of timeouts? :-)
  90 //     sem_post( semBlockLock );
  91 //     nWaitersGone = 0;
  92 //   }
  93 //   unlock( mtxUnblockLock );
  94 //
  95 //   if ( 1 == nSignalsWasLeft ) {
  96 //     if ( 0 != nWaitersWasGone ) {
  97 //       // sem_adjust( semBlockQueue,-nWaitersWasGone );
  98 //       while ( nWaitersWasGone-- ) {
  99 //         sem_wait( semBlockQueue );       // better now than spurious later
 100 //       }
 101 //     } sem_post( semBlockLock );          // open the gate
 102 //   }
 103 //
 104 //   lock( mtxExternal );
 105 //
 106 //   return ( bTimedOut ) ? ETIMEOUT : 0;
 107 // }
 108 //
 109 // signal(bAll) {
 110 //
 111 //   [auto: register int result         ]
 112 //   [auto: register int nSignalsToIssue]
 113 //
 114 //   lock( mtxUnblockLock );
 115 //
 116 //   if ( 0 != nWaitersToUnblock ) {        // the gate is closed!!!
 117 //     if ( 0 == nWaitersBlocked ) {        // NO-OP
 118 //       return unlock( mtxUnblockLock );
 119 //     }
 120 //     if (bAll) {
 121 //       nWaitersToUnblock += nSignalsToIssue=nWaitersBlocked;
 122 //       nWaitersBlocked = 0;
 123 //     }
 124 //     else {
 125 //       nSignalsToIssue = 1;
 126 //       nWaitersToUnblock++;
 127 //       nWaitersBlocked--;
 128 //     }
 129 //   }
 130 //   else if ( nWaitersBlocked > nWaitersGone ) { // HARMLESS RACE CONDITION!
 131 //     sem_wait( semBlockLock );                  // close the gate
 132 //     if ( 0 != nWaitersGone ) {
 133 //       nWaitersBlocked -= nWaitersGone;
 134 //       nWaitersGone = 0;
 135 //     }
 136 //     if (bAll) {
 137 //       nSignalsToIssue = nWaitersToUnblock = nWaitersBlocked;
 138 //       nWaitersBlocked = 0;
 139 //     }
 140 //     else {
 141 //       nSignalsToIssue = nWaitersToUnblock = 1;
 142 //       nWaitersBlocked--;
 143 //     }
 144 //   }
 145 //   else { // NO-OP
 146 //     return unlock( mtxUnblockLock );
 147 //   }
 148 //
 149 //   unlock( mtxUnblockLock );
 150 //   sem_post( semBlockQueue,nSignalsToIssue );
 151 //   return result;
 152 // }
 153 ////////////////////////////////////////////////////////////////////////
 154 ////////////////////////////////////////////////////////////////////////
 155 ////////////////////////////////////////////////////////////////////////
 156
 157
 158 // Required interface for ConditionMembers
 159 // class ConditionMembers
 160 // {
 161 //    typedef implementation_defined semaphore_type;
 162 //    typedef implementation_defined mutex_type;
 163 //    typedef implementation_defined integer_type;
 164 //
 165 //    integer_type    &get_nwaiters_blocked()
 166 //    integer_type    &get_nwaiters_gone()
 167 //    integer_type    &get_nwaiters_to_unblock()
 168 //    semaphore_type  &get_sem_block_queue()
 169 //    semaphore_type  &get_sem_block_lock()
 170 //    mutex_type      &get_mtx_unblock_lock()
 171 // };
 172 //
 173 // Must be initialized as following
 174 //
 175 //    get_nwaiters_blocked() == 0
 176 //    get_nwaiters_gone() == 0
 177 //    get_nwaiters_to_unblock() == 0
 178 //    get_sem_block_queue() == initial count 0
 179 //    get_sem_block_lock() == initial count 1
 180 //    get_mtx_unblock_lock() (unlocked)
 181 //
 182 template<class ConditionMembers>
 183 class condition_algorithm_8a
 184 {
 185    private:
 186    condition_algorithm_8a();
 187    ~condition_algorithm_8a();
 188    condition_algorithm_8a(const condition_algorithm_8a &);
 189    condition_algorithm_8a &operator=(const condition_algorithm_8a &);
 190
 191    typedef typename ConditionMembers::semaphore_type  semaphore_type;
 192    typedef typename ConditionMembers::mutex_type      mutex_type;
 193    typedef typename ConditionMembers::integer_type    integer_type;
 194
 195    public:
 196    template<class Lock>
 197    static bool wait  ( ConditionMembers &data, Lock &lock
 198                      , bool timeout_enabled, const boost::posix_time::ptime &abs_time);
 199    static void signal(ConditionMembers &data, bool broadcast);
 200 };
 201
 202 template<class ConditionMembers>
 203 inline void condition_algorithm_8a<ConditionMembers>::signal(ConditionMembers &data, bool broadcast)
 204 {
 205    integer_type nsignals_to_issue;
 206
 207    {
 208       scoped_lock<mutex_type> locker(data.get_mtx_unblock_lock());
 209
 210       if ( 0 != data.get_nwaiters_to_unblock() ) {        // the gate is closed!!!
 211          if ( 0 == data.get_nwaiters_blocked() ) {        // NO-OP
 212             //locker's destructor triggers data.get_mtx_unblock_lock().unlock()
 213             return;
 214          }
 215          if (broadcast) {
 216             data.get_nwaiters_to_unblock() += nsignals_to_issue = data.get_nwaiters_blocked();
 217             data.get_nwaiters_blocked() = 0;
 218          }
 219          else {
 220             nsignals_to_issue = 1;
 221             data.get_nwaiters_to_unblock()++;
 222             data.get_nwaiters_blocked()--;
 223          }
 224       }
 225       else if ( data.get_nwaiters_blocked() > data.get_nwaiters_gone() ) { // HARMLESS RACE CONDITION!
 226          data.get_sem_block_lock().wait();                      // close the gate
 227          if ( 0 != data.get_nwaiters_gone() ) {
 228             data.get_nwaiters_blocked() -= data.get_nwaiters_gone();
 229             data.get_nwaiters_gone() = 0;
 230          }
 231          if (broadcast) {
 232             nsignals_to_issue = data.get_nwaiters_to_unblock() = data.get_nwaiters_blocked();
 233             data.get_nwaiters_blocked() = 0;
 234          }
 235          else {
 236             nsignals_to_issue = data.get_nwaiters_to_unblock() = 1;
 237             data.get_nwaiters_blocked()--;
 238          }
 239       }
 240       else { // NO-OP
 241          //locker's destructor triggers data.get_mtx_unblock_lock().unlock()
 242          return;
 243       }
 244       //locker's destructor triggers data.get_mtx_unblock_lock().unlock()
 245    }
 246    data.get_sem_block_queue().post(nsignals_to_issue);
 247 }
 248
 249 template<class ConditionMembers>
 250 template<class Lock>
 251 inline bool condition_algorithm_8a<ConditionMembers>::wait
 252    ( ConditionMembers &data
 253    , Lock &lock
 254    , bool tout_enabled
 255    , const boost::posix_time::ptime &abs_time
 256    )
 257 {
 258    //Initialize to avoid warnings
 259    integer_type nsignals_was_left = 0;
 260    integer_type nwaiters_was_gone = 0;
 261
 262    data.get_sem_block_lock().wait();
 263    ++data.get_nwaiters_blocked();
 264    data.get_sem_block_lock().post();
 265
 266    //Unlock external lock and program for relock
 267    lock_inverter<Lock> inverted_lock(lock);
 268    scoped_lock<lock_inverter<Lock> >   external_unlock(inverted_lock);
 269
 270    bool bTimedOut = tout_enabled
 271       ? !data.get_sem_block_queue().timed_wait(abs_time)
 272       : (data.get_sem_block_queue().wait(), false);
 273
 274    {
 275       scoped_lock<mutex_type> locker(data.get_mtx_unblock_lock());
 276       if ( 0 != (nsignals_was_left = data.get_nwaiters_to_unblock()) ) {
 277          if ( bTimedOut ) {                       // timeout (or canceled)
 278             if ( 0 != data.get_nwaiters_blocked() ) {
 279                data.get_nwaiters_blocked()--;
 280             }
 281             else {
 282                data.get_nwaiters_gone()++;                     // count spurious wakeups.
 283             }
 284          }
 285          if ( 0 == --data.get_nwaiters_to_unblock() ) {
 286             if ( 0 != data.get_nwaiters_blocked() ) {
 287                data.get_sem_block_lock().post();          // open the gate.
 288                nsignals_was_left = 0;          // do not open the gate below again.
 289             }
 290             else if ( 0 != (nwaiters_was_gone = data.get_nwaiters_gone()) ) {
 291                data.get_nwaiters_gone() = 0;
 292             }
 293          }
 294       }
 295       else if ( (std::numeric_limits<integer_type>::max)()/2
 296                 == ++data.get_nwaiters_gone() ) { // timeout/canceled or spurious semaphore :-)
 297          data.get_sem_block_lock().wait();
 298          data.get_nwaiters_blocked() -= data.get_nwaiters_gone();       // something is going on here - test of timeouts? :-)
 299          data.get_sem_block_lock().post();
 300          data.get_nwaiters_gone() = 0;
 301       }
 302       //locker's destructor triggers data.get_mtx_unblock_lock().unlock()
 303    }
 304
 305    if ( 1 == nsignals_was_left ) {
 306       if ( 0 != nwaiters_was_gone ) {
 307          // sem_adjust( data.get_sem_block_queue(),-nwaiters_was_gone );
 308          while ( nwaiters_was_gone-- ) {
 309             data.get_sem_block_queue().wait();       // better now than spurious later
 310          }
 311       }
 312       data.get_sem_block_lock().post(); // open the gate
 313    }
 314
 315    //lock.lock(); called from unlocker destructor
 316
 317    return ( bTimedOut ) ? false : true;
 318 }
 319
 320
 321 template<class ConditionMembers>
 322 class condition_8a_wrapper
 323 {
 324    //Non-copyable
 325    condition_8a_wrapper(const condition_8a_wrapper &);
 326    condition_8a_wrapper &operator=(const condition_8a_wrapper &);
 327
 328    ConditionMembers m_data;
 329    typedef ipcdetail::condition_algorithm_8a<ConditionMembers> algo_type;
 330
 331    public:
 332
 333    condition_8a_wrapper(){}
 334
 335    //Compiler-generated destructor is OK
 336    //~condition_8a_wrapper(){}
 337
 338    ConditionMembers & get_members()
 339    {  return m_data; }
 340
 341    const ConditionMembers & get_members() const
 342    {  return m_data; }
 343
 344    void notify_one()
 345    {  algo_type::signal(m_data, false);  }
 346
 347    void notify_all()
 348    {  algo_type::signal(m_data, true);  }
 349
 350    template <typename L>
 351    void wait(L& lock)
 352    {
 353       if (!lock)
 354          throw lock_exception();
 355       algo_type::wait(m_data, lock, false, boost::posix_time::ptime());
 356    }
 357
 358    template <typename L, typename Pr>
 359    void wait(L& lock, Pr pred)
 360    {
 361       if (!lock)
 362          throw lock_exception();
 363
 364       while (!pred())
 365          algo_type::wait(m_data, lock, false, boost::posix_time::ptime());
 366    }
 367
 368    template <typename L>
 369    bool timed_wait(L& lock, const boost::posix_time::ptime &abs_time)
 370    {
 371       if (!lock)
 372          throw lock_exception();
 373       return algo_type::wait(m_data, lock, true, abs_time);
 374    }
 375
 376    template <typename L, typename Pr>
 377    bool timed_wait(L& lock, const boost::posix_time::ptime &abs_time, Pr pred)
 378    {
 379       if (!lock)
 380             throw lock_exception();
 381       while (!pred()){
 382          if (!algo_type::wait(m_data, lock, true, abs_time))
 383             return pred();
 384       }
 385       return true;
 386    }
 387 };
 388
 389 }  //namespace ipcdetail
 390 }  //namespace interprocess
 391 }  //namespace boost
 392
 393 #include <boost/interprocess/detail/config_end.hpp>
 394
 395 #endif   //BOOST_INTERPROCESS_DETAIL_CONDITION_ALGORITHM_8A_HPP