cds/sync/pool_monitor.h

   1 //$$CDS-header$$
   2
   3 #ifndef CDSLIB_SYNC_POOL_MONITOR_H
   4 #define CDSLIB_SYNC_POOL_MONITOR_H
   5
   6 #include <cds/sync/monitor.h>
   7 #include <cds/algo/atomic.h>
   8 #include <cds/algo/backoff_strategy.h>
   9
  10 namespace cds { namespace sync {
  11
  12     /// @ref cds_sync_monitor "Monitor" that allocates node's lock when needed
  13     /**
  14         The monitor is intended for reducing the number of system mutexes for
  15         huge containers like a tree. The monitor allocates the mutex from the pool \p LockPool
  16         only when container's node should be locked. Lifetime of node's mutex is managed by
  17         reference counter. When the reference counter to node's mutex becomes zero,
  18         the mutex is given back to the pool.
  19
  20         The monitor is blocked: the access to node's mutex is performed under the spin-lock.
  21         However, node locking/unlocking is performed beyond the spin-lock.
  22
  23         Template arguments:
  24         - \p LockPool - the @ref cds_memory_pool "pool type". The pool must maintain
  25             the objects of type \p std::mutex or similar. The access to the pool is not synchronized.
  26         - \p BackOff - back-off strategy for spinning, default is \p cds::backoff::LockDefault
  27
  28         <b>How to use</b>
  29         \code
  30         typedef cds::memory::vyukov_queue_pool< std::mutex > pool_type;
  31         typedef cds::sync::pool_monitor< pool_type > sync_monitor;
  32         \endcode
  33     */
  34     template <class LockPool, typename BackOff = cds::backoff::LockDefault >
  35     class pool_monitor
  36     {
  37     public:
  38         typedef LockPool pool_type; ///< Pool type
  39         typedef typename pool_type::value_type lock_type; ///< node lock type
  40         typedef BackOff  back_off;  ///< back-off strategy for spinning
  41
  42     private:
  43         //@cond
  44         pool_type   m_Pool;
  45         //@endcond
  46
  47     public:
  48         /// Monitor injection into \p Node
  49         template <typename Node>
  50         class node_injection : public Node
  51         {
  52             //@cond
  53             typedef unsigned int refspin_type;
  54             static CDS_CONSTEXPR refspin_type const c_nSpinBit = 1;
  55             static CDS_CONSTEXPR refspin_type const c_nRefIncrement = 2;
  56
  57             struct injection
  58             {
  59                 atomics::atomic<refspin_type>   m_RefSpin;  ///< Spin-lock for \p m_pLock (bit 0) + reference counter
  60                 lock_type *                     m_pLock;    ///< Node-level lock
  61
  62                 injection()
  63                     : m_Access( 0 )
  64                     , m_pLock( nullptr )
  65                 {}
  66
  67                 ~injection()
  68                 {
  69                     assert( m_pLock == nullptr );
  70                     assert( m_RefSpin.load( atomics::memory_order_relaxed ) == 0 );
  71                 }
  72             };
  73             //@endcond
  74
  75         public:
  76             mutable injection   m_Access;   ///< injected data
  77
  78 #       ifdef CDS_CXX11_INHERITING_CTOR
  79             using Node::Node;
  80 #       else
  81             // Inheriting ctor emulation
  82             template <typename... Args>
  83             node_injection( Args&&... args )
  84                 : Node( std::forward<Args>( args )... )
  85             {}
  86 #       endif
  87         };
  88
  89         /// Initializes the pool of 256 preallocated mutexes
  90         pool_monitor()
  91             : m_Pool( 256 )
  92         {}
  93
  94         /// Initializes the pool of \p nPoolCapacity preallocated mutexes
  95         pool_monitor( size_t nPoolCapacity )
  96             : m_Pool( nPoolCapacity)
  97         {}
  98
  99         /// Makes exclusive access to node \p p
 100         template <typename Node>
 101         void lock( Node const& p ) const
 102         {
 103             lock_type * pLock;
 104
 105             // try lock spin and increment reference counter
 106             refspin_type cur = p.m_Access.m_RefSpin.load( atomics::memory_order_relaxed ) & ~c_nSpinBit;
 107             if ( !p.m_Access.m_RefSpin.compare_exchange_weak( cur, cur + c_nRefIncrement + c_nSpinBit,
 108                 atomics::memory_order_acquire, atomics::memory_order_relaxed ) )
 109             {
 110                 back_off bkoff;
 111                 do {
 112                     bkoff();
 113                     cur &= ~c_nSpinBit;
 114                 } while ( !p.m_Access.m_RefSpin.compare_exchange_weak( cur, cur + c_nRefIncrement + c_nSpinBit,
 115                     atomics::memory_order_acquire, atomics::memory_order_relaxed );
 116             }
 117
 118             // spin locked
 119             // If the node has no lock, allocate it from pool
 120             pLock = p.m_Access.m_pLock;
 121             if ( !pLock )
 122                 pLock = p.m_Access.m_pLock = m_Pool.allocate( 1 );
 123
 124             // unlock spin
 125             p.m_Access.m_RefSpin.store( cur + c_nRefIncrement, atomics::memory_order_release );
 126
 127             // lock the node
 128             pLock->lock();
 129         }
 130
 131         /// Unlocks the node \p p
 132         template <typename Node>
 133         void unlock( Node const& p ) const
 134         {
 135             lock_type * pLock = nullptr;
 136
 137             assert( p.m_Access.m_pLock != nullptr );
 138             p.m_Access.m_pLock->unlock();
 139
 140             // try lock spin
 141             refspin_type cur = p.m_Access.m_RefSpin.load( atomics::memory_order_relaxed ) & ~c_nSpinBit;
 142             if ( !p.m_Access.m_RefSpin.compare_exchange_weak( cur, cur + c_nSpinBit,
 143                 atomics::memory_order_acquire, atomics::memory_order_relaxed ) )
 144             {
 145                 back_off bkoff;
 146                 do {
 147                     bkoff();
 148                     cur &= ~c_nSpinBit;
 149                 } while ( !p.m_Access.m_RefSpin.compare_exchange_weak( cur, cur + c_nSpinBit,
 150                     atomics::memory_order_acquire, atomics::memory_order_relaxed );
 151             }
 152
 153             // spin locked now
 154
 155             // If we are the unique owner - deallocate lock
 156             if ( cur == c_nRefIncrement ) {
 157                 pLock = p.m_Access.m_pLock;
 158                 p.m_Access.m_pLock = nullptr;
 159             }
 160
 161             // unlock spin
 162             p.m_Access.m_RefSpin.store( cur - c_nRefIncrement, atomics::memory_order_release );
 163
 164             // free pLock
 165             if ( pLock )
 166                 m_Pool.deallocate( pLock, 1 );
 167         }
 168
 169         /// Scoped lock
 170         template <typename Node>
 171         using scoped_lock = monitor_scoped_lock< pool_monitor, Node >;
 172     };
 173
 174 }} // namespace cds::sync
 175
 176 #endif // #ifndef CDSLIB_SYNC_POOL_MONITOR_H
 177