cds/sync/pool_monitor.h

   1 /*
   2     This file is a part of libcds - Concurrent Data Structures library
   3
   4     (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
   5
   6     Source code repo: http://github.com/khizmax/libcds/
   7     Download: http://sourceforge.net/projects/libcds/files/
   8
   9     Redistribution and use in source and binary forms, with or without
  10     modification, are permitted provided that the following conditions are met:
  11
  12     * Redistributions of source code must retain the above copyright notice, this
  13       list of conditions and the following disclaimer.
  14
  15     * Redistributions in binary form must reproduce the above copyright notice,
  16       this list of conditions and the following disclaimer in the documentation
  17       and/or other materials provided with the distribution.
  18
  19     THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  20     AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  21     IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  22     DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
  23     FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  24     DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  25     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  26     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  27     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  28     OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29 */
  30
  31 #ifndef CDSLIB_SYNC_POOL_MONITOR_H
  32 #define CDSLIB_SYNC_POOL_MONITOR_H
  33
  34 #include <cds/sync/monitor.h>
  35 #include <cds/algo/atomic.h>
  36 #include <cds/algo/backoff_strategy.h>
  37 #include <cds/opt/options.h> // opt::none
  38
  39 namespace cds { namespace sync {
  40
  41     /// \p pool_monitor traits
  42     struct pool_monitor_traits {
  43
  44         /// Dummy internal statistics if \p Stat template parameter is \p false
  45         struct empty_stat
  46         {
  47             //@cond
  48             void onLock()              const {}
  49             void onUnlock()            const {}
  50             void onLockContention()    const {}
  51             void onUnlockContention()  const {}
  52             void onLockAllocation()    const {}
  53             void onLockDeallocation()  const {}
  54             //@endcond
  55         };
  56
  57         /// Monitor's internal statistics, used if \p Stat template parameter is \p true
  58         template <typename Counter = cds::atomicity::event_counter >
  59         struct stat
  60         {
  61             typedef Counter event_counter; ///< measure type
  62
  63             event_counter m_nLockCount;         ///< Number of monitor \p lock() call
  64             event_counter m_nUnlockCount;       ///< Number of monitor \p unlock() call
  65             event_counter m_nMaxLocked;         ///< Max number of simuntaneously locked mutexes
  66             event_counter m_nLockContention;    ///< Number of \p lock() contenton
  67             event_counter m_nUnlockContention;  ///< Number of \p unlock() contention
  68             event_counter m_nLockAllocation;    ///< Number of the lock allocation from the pool
  69             event_counter m_nLockDeallocation;  ///< Number of the lock deallocation
  70             event_counter m_nMaxAllocated;      ///< Max number of sumultaneously allocated mutexes
  71
  72             //@cond
  73             void onLock()
  74             {
  75                 ++m_nLockCount;
  76                 int nDiff = static_cast<int>( m_nLockCount.get() - m_nUnlockCount.get());
  77                 if ( nDiff > 0 && m_nMaxLocked.get() < static_cast<typename event_counter::value_type>( nDiff ))
  78                     m_nMaxLocked = static_cast<typename event_counter::value_type>( nDiff );
  79             }
  80             void onUnlock()             { ++m_nUnlockCount;     }
  81             void onLockContention()     { ++m_nLockContention;  }
  82             void onUnlockContention()   { ++m_nUnlockContention;}
  83             void onLockAllocation()
  84             {
  85                 ++m_nLockAllocation;
  86                 int nDiff = static_cast<int>( m_nLockAllocation.get() - m_nLockDeallocation.get());
  87                 if ( nDiff > 0 && m_nMaxAllocated.get() < static_cast<typename event_counter::value_type>( nDiff ) )
  88                     m_nMaxAllocated = static_cast<typename event_counter::value_type>( nDiff );
  89             }
  90             void onLockDeallocation()   { ++m_nLockDeallocation;}
  91             //@endcond
  92         };
  93     };
  94
  95
  96     /// @ref cds_sync_monitor "Monitor" that allocates node's lock when needed
  97     /**
  98         The monitor is intended for reducing the number of system mutexes for
  99         huge containers like a tree. The monitor allocates the mutex from the pool \p LockPool
 100         only when container's node should be locked. Lifetime of node's mutex is managed by
 101         reference counter. When the reference counter to node's mutex becomes zero,
 102         the mutex is given back to the pool.
 103
 104         The monitor is blocked: the access to node's mutex is performed under the spin-lock.
 105         However, node locking/unlocking is performed beyond the spin-lock.
 106
 107         Template arguments:
 108         - \p LockPool - the @ref cds_memory_pool "pool type". The pool must maintain
 109             the objects of type \p std::mutex or similar. The access to the pool is not synchronized.
 110         - \p BackOff - back-off strategy for spinning, default is \p cds::backoff::yield
 111         - \p Stat - enable (\p true) or disable (\p false, the default) monitor's internal statistics.
 112
 113         <b>How to use</b>
 114         \code
 115         typedef cds::memory::vyukov_queue_pool< std::mutex > pool_type;
 116         typedef cds::sync::pool_monitor< pool_type > sync_monitor;
 117         \endcode
 118     */
 119     template <class LockPool, typename BackOff = cds::backoff::yield, bool Stat = false >
 120     class pool_monitor
 121     {
 122     public:
 123         typedef LockPool pool_type; ///< Pool type
 124         typedef typename pool_type::value_type lock_type; ///< node lock type
 125         typedef typename std::conditional<
 126             std::is_same< BackOff, cds::opt::none >::value,
 127             cds::backoff::yield,
 128             BackOff
 129         >::type  back_off;  ///< back-off strategy for spinning
 130         typedef uint32_t refspin_type;  ///< Reference counter + spin-lock bit
 131
 132         /// Internal statistics
 133         typedef typename std::conditional<
 134             Stat,
 135             typename pool_monitor_traits::stat<>,
 136             typename pool_monitor_traits::empty_stat
 137         >::type internal_stat;
 138
 139         /// Pool's default capacity
 140         static CDS_CONSTEXPR size_t const c_nDefaultCapacity = 256;
 141
 142     private:
 143         //@cond
 144         static CDS_CONSTEXPR refspin_type const c_nSpinBit = 1;
 145         static CDS_CONSTEXPR refspin_type const c_nRefIncrement = 2;
 146         mutable pool_type      m_Pool;
 147         mutable internal_stat  m_Stat;
 148         //@endcond
 149
 150     public:
 151
 152         /// Node injection
 153         struct node_injection
 154         {
 155             mutable atomics::atomic<refspin_type>   m_RefSpin;  ///< Spin-lock for \p m_pLock (bit 0) + reference counter
 156             mutable lock_type *                     m_pLock;    ///< Node-level lock
 157
 158             //@cond
 159             node_injection()
 160                 : m_RefSpin( 0 )
 161                 , m_pLock( nullptr )
 162             {}
 163
 164             ~node_injection()
 165             {
 166                 assert( m_pLock == nullptr );
 167                 assert( m_RefSpin.load( atomics::memory_order_relaxed ) == 0 );
 168             }
 169
 170             bool check_free() const
 171             {
 172                 return m_pLock == nullptr && m_RefSpin.load( atomics::memory_order_acquire ) == 0;
 173             }
 174             //@endcond
 175         };
 176
 177         /// Initializes the pool of 256 preallocated mutexes
 178         pool_monitor()
 179             : m_Pool( c_nDefaultCapacity )
 180         {}
 181
 182         /// Initializes the pool of \p nPoolCapacity preallocated mutexes
 183         pool_monitor( size_t nPoolCapacity )
 184             : m_Pool( nPoolCapacity ? nPoolCapacity : c_nDefaultCapacity )
 185         {}
 186
 187         /// Makes exclusive access to node \p p
 188         template <typename Node>
 189         void lock( Node const& p ) const
 190         {
 191             lock_type * pLock;
 192
 193             m_Stat.onLock();
 194
 195             // try lock spin and increment reference counter
 196             refspin_type cur = p.m_SyncMonitorInjection.m_RefSpin.load( atomics::memory_order_relaxed ) & ~c_nSpinBit;
 197             if ( !p.m_SyncMonitorInjection.m_RefSpin.compare_exchange_weak( cur, cur + c_nRefIncrement + c_nSpinBit,
 198                 atomics::memory_order_acquire, atomics::memory_order_relaxed ) )
 199             {
 200                 back_off bkoff;
 201                 do {
 202                     m_Stat.onLockContention();
 203                     bkoff();
 204                     cur &= ~c_nSpinBit;
 205                 } while ( !p.m_SyncMonitorInjection.m_RefSpin.compare_exchange_weak( cur, cur + c_nRefIncrement + c_nSpinBit,
 206                     atomics::memory_order_acquire, atomics::memory_order_relaxed ));
 207             }
 208
 209             // spin locked
 210             // If the node has no lock, allocate it from pool
 211             pLock = p.m_SyncMonitorInjection.m_pLock;
 212             if ( !pLock ) {
 213                 assert( cur == 0 );
 214                 pLock = p.m_SyncMonitorInjection.m_pLock = m_Pool.allocate( 1 );
 215                 assert( pLock != nullptr );
 216                 m_Stat.onLockAllocation();
 217             }
 218
 219             // unlock spin
 220             p.m_SyncMonitorInjection.m_RefSpin.store( cur + c_nRefIncrement, atomics::memory_order_release );
 221
 222             // lock the node
 223             pLock->lock();
 224         }
 225
 226         /// Unlocks the node \p p
 227         template <typename Node>
 228         void unlock( Node const& p ) const
 229         {
 230             lock_type * pLock = nullptr;
 231
 232             m_Stat.onUnlock();
 233
 234             assert( p.m_SyncMonitorInjection.m_pLock != nullptr );
 235             p.m_SyncMonitorInjection.m_pLock->unlock();
 236
 237             // try lock spin
 238             refspin_type cur = p.m_SyncMonitorInjection.m_RefSpin.load( atomics::memory_order_relaxed ) & ~c_nSpinBit;
 239             if ( !p.m_SyncMonitorInjection.m_RefSpin.compare_exchange_weak( cur, cur | c_nSpinBit,
 240                 atomics::memory_order_acquire, atomics::memory_order_relaxed ) )
 241             {
 242                 back_off bkoff;
 243                 do {
 244                     m_Stat.onUnlockContention();
 245                     bkoff();
 246                     cur &= ~c_nSpinBit;
 247                 } while ( !p.m_SyncMonitorInjection.m_RefSpin.compare_exchange_weak( cur, cur | c_nSpinBit,
 248                     atomics::memory_order_acquire, atomics::memory_order_relaxed ));
 249             }
 250
 251             // spin locked now
 252
 253             // If we are the unique owner - deallocate lock
 254             if ( cur == c_nRefIncrement ) {
 255                 pLock = p.m_SyncMonitorInjection.m_pLock;
 256                 p.m_SyncMonitorInjection.m_pLock = nullptr;
 257             }
 258
 259             // unlock spin
 260             p.m_SyncMonitorInjection.m_RefSpin.store( cur - c_nRefIncrement, atomics::memory_order_release );
 261
 262             // free pLock
 263             if ( pLock ) {
 264                 m_Pool.deallocate( pLock, 1 );
 265                 m_Stat.onLockDeallocation();
 266             }
 267         }
 268
 269         /// Scoped lock
 270         template <typename Node>
 271         using scoped_lock = monitor_scoped_lock< pool_monitor, Node >;
 272
 273         /// Returns the reference to internal statistics
 274         /**
 275             If class' template argument \p Stat is \p false,
 276             the function returns \ref pool_monitor_traits::empty_stat "dummy statistics".
 277             Otherwise, it returns the reference to monitor's internal statistics
 278             of type \ref pool_monitor_traits::stat.
 279         */
 280         internal_stat const& statistics() const
 281         {
 282             return m_Stat;
 283         }
 284     };
 285
 286 }} // namespace cds::sync
 287
 288 #endif // #ifndef CDSLIB_SYNC_POOL_MONITOR_H
 289