cds/intrusive/striped_set/striping_policy.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDS_INTRUSIVE_STRIPED_SET_STRIPING_POLICY_H
   4 #define __CDS_INTRUSIVE_STRIPED_SET_STRIPING_POLICY_H
   5
   6 #include <memory>
   7 #include <mutex>
   8 #include <cds/lock/array.h>
   9 #include <cds/os/thread.h>
  10 #include <cds/lock/spinlock.h>
  11
  12 namespace cds { namespace intrusive { namespace striped_set {
  13
  14     /// Lock striping concurrent access policy
  15     /**
  16         This is one of available opt::mutex_policy option type for StripedSet
  17
  18         Lock striping is very simple technique.
  19         The set consists of the bucket table and the array of locks.
  20         Initially, the capacity of lock array and bucket table is the same.
  21         When set is resized, bucket table capacity will be doubled but lock array will not.
  22         The lock \p i protects each bucket \p j, where <tt> j = i mod L </tt>,
  23         where \p L - the size of lock array.
  24
  25         The policy contains an internal array of \p Lock locks.
  26
  27         Template arguments:
  28         - \p Lock - the type of mutex. The default is \p std::mutex. The mutex type should be default-constructible.
  29             Note that a spin-lock is not so good suitable for lock striping for performance reason.
  30         - \p Alloc - allocator type used for lock array memory allocation. Default is \p CDS_DEFAULT_ALLOCATOR.
  31     */
  32     template <class Lock = std::mutex, class Alloc = CDS_DEFAULT_ALLOCATOR >
  33     class striping
  34     {
  35     public:
  36         typedef Lock    lock_type       ;   ///< lock type
  37         typedef Alloc   allocator_type  ;   ///< allocator type
  38
  39         typedef cds::lock::array< lock_type, cds::lock::pow2_select_policy, allocator_type >    lock_array_type ;   ///< lock array type
  40
  41     protected:
  42         //@cond
  43         lock_array_type m_Locks;
  44         //@endcond
  45
  46     public:
  47         //@cond
  48         class scoped_cell_lock {
  49             cds::lock::scoped_lock< lock_array_type >   m_guard;
  50
  51         public:
  52             scoped_cell_lock( striping& policy, size_t nHash )
  53                 : m_guard( policy.m_Locks, nHash )
  54             {}
  55         };
  56
  57         class scoped_full_lock {
  58             cds::lock::scoped_lock< lock_array_type >   m_guard;
  59         public:
  60             scoped_full_lock( striping& policy )
  61                 : m_guard( policy.m_Locks )
  62             {}
  63         };
  64
  65         class scoped_resize_lock: public scoped_full_lock {
  66         public:
  67             scoped_resize_lock( striping& policy )
  68                 : scoped_full_lock( policy )
  69             {}
  70
  71             bool success() const
  72             {
  73                 return true;
  74             }
  75         };
  76         //@endcond
  77
  78     public:
  79         /// Constructor
  80         striping(
  81             size_t nLockCount   ///< The size of lock array. Must be power of two.
  82         )
  83             : m_Locks( nLockCount, cds::lock::pow2_select_policy( nLockCount ))
  84         {}
  85
  86         /// Returns lock array size
  87         /**
  88             Lock array size is unchanged during \p striped object lifetime
  89         */
  90         size_t lock_count() const
  91         {
  92             return m_Locks.size();
  93         }
  94
  95         //@cond
  96         void resize( size_t /*nNewCapacity*/ )
  97         {}
  98         //@endcond
  99     };
 100
 101
 102     /// Refinable concurrent access policy
 103     /**
 104         This is one of available opt::mutex_policy option type for StripedSet
 105
 106         Refining is like a striping technique (see striped_set::striping)
 107         but it allows growing the size of lock array when resizing the hash table.
 108         So, the sizes of hash table and lock array are equal.
 109
 110         Template arguments:
 111         - \p RecursiveLock - the type of mutex. Reentrant (recursive) mutex is required.
 112             The default is \p std::recursive_mutex. The mutex type should be default-constructible.
 113         - \p BackOff - back-off strategy. Default is cds::backoff::yield
 114         - \p Alloc - allocator type used for lock array memory allocation. Default is \p CDS_DEFAULT_ALLOCATOR.
 115     */
 116     template <
 117         class RecursiveLock = std::recursive_mutex,
 118         typename BackOff = cds::backoff::yield,
 119         class Alloc = CDS_DEFAULT_ALLOCATOR>
 120     class refinable
 121     {
 122     public:
 123         typedef RecursiveLock   lock_type   ;   ///< lock type
 124         typedef BackOff         back_off    ;   ///< back-off strategy used
 125         typedef Alloc           allocator_type; ///< allocator type
 126
 127     protected:
 128         //@cond
 129         typedef cds::lock::trivial_select_policy  lock_selection_policy;
 130
 131         class lock_array_type
 132             : public cds::lock::array< lock_type, lock_selection_policy, allocator_type >
 133             , public std::enable_shared_from_this< lock_array_type >
 134         {
 135             typedef cds::lock::array< lock_type, lock_selection_policy, allocator_type >    lock_array_base;
 136         public:
 137             lock_array_type( size_t nCapacity )
 138                 : lock_array_base( nCapacity )
 139             {}
 140         };
 141         typedef std::shared_ptr< lock_array_type >  lock_array_ptr;
 142         typedef cds::details::Allocator< lock_array_type, allocator_type >  lock_array_allocator;
 143
 144         typedef unsigned long long  owner_t;
 145         typedef std::thread::id     threadId_t;
 146
 147         typedef cds::lock::Spin     spinlock_type;
 148         typedef cds::lock::scoped_lock< spinlock_type > scoped_spinlock;
 149         //@endcond
 150
 151     protected:
 152         //@cond
 153         static owner_t const c_nOwnerMask = (((owner_t) 1) << (sizeof(owner_t) * 8 - 1)) - 1;
 154
 155         lock_array_ptr                  m_arrLocks  ;   ///< Lock array. The capacity of array is specified in constructor.
 156         CDS_ATOMIC::atomic< owner_t >   m_Owner     ;   ///< owner mark (thread id + boolean flag)
 157         CDS_ATOMIC::atomic<size_t>      m_nCapacity ;   ///< Lock array capacity
 158         spinlock_type                   m_access    ;   ///< access to m_arrLocks
 159         //@endcond
 160
 161     protected:
 162         //@cond
 163         struct lock_array_disposer {
 164             void operator()( lock_array_type * pArr )
 165             {
 166                 lock_array_allocator().Delete( pArr );
 167             }
 168         };
 169
 170         lock_array_ptr create_lock_array( size_t nCapacity )
 171         {
 172             m_nCapacity.store( nCapacity, CDS_ATOMIC::memory_order_relaxed );
 173             return lock_array_ptr( lock_array_allocator().New( nCapacity ), lock_array_disposer() );
 174         }
 175
 176         lock_type& acquire( size_t nHash )
 177         {
 178             owner_t me = (owner_t) std::this_thread::get_id();
 179             owner_t who;
 180
 181             back_off bkoff;
 182             while ( true ) {
 183                 // wait while resizing
 184                 while ( true ) {
 185                     who = m_Owner.load( CDS_ATOMIC::memory_order_acquire );
 186                     if ( !( who & 1 ) || (who >> 1) == (me & c_nOwnerMask) )
 187                         break;
 188                     bkoff();
 189                 }
 190
 191                 lock_array_ptr pLocks;
 192                 {
 193                     scoped_spinlock sl(m_access);
 194                     pLocks = m_arrLocks;
 195                 }
 196
 197                 lock_type& lock = pLocks->at( nHash & (pLocks->size() - 1));
 198                 lock.lock();
 199
 200                 who = m_Owner.load( CDS_ATOMIC::memory_order_acquire );
 201                 if ( ( !(who & 1) || (who >> 1) == (me & c_nOwnerMask) ) && m_arrLocks == pLocks )
 202                     return lock;
 203                 lock.unlock();
 204             }
 205         }
 206
 207         lock_array_ptr acquire_all()
 208         {
 209             owner_t me = (owner_t)std::this_thread::get_id();
 210             owner_t who;
 211
 212             back_off bkoff;
 213             while ( true ) {
 214                 // wait while resizing
 215                 while ( true ) {
 216                     who = m_Owner.load( CDS_ATOMIC::memory_order_acquire );
 217                     if ( !( who & 1 ) || (who >> 1) == (me & c_nOwnerMask) )
 218                         break;
 219                     bkoff();
 220                 }
 221
 222                 lock_array_ptr pLocks;
 223                 {
 224                     scoped_spinlock sl(m_access);
 225                     pLocks = m_arrLocks;
 226                 }
 227
 228                 pLocks->lock_all();
 229
 230                 who = m_Owner.load( CDS_ATOMIC::memory_order_acquire );
 231                 if ( ( !(who & 1) || (who >> 1) == (me & c_nOwnerMask) ) && m_arrLocks == pLocks )
 232                     return pLocks;
 233
 234                 pLocks->unlock_all();
 235             }
 236         }
 237
 238         void release_all( lock_array_ptr p )
 239         {
 240             p->unlock_all();
 241         }
 242
 243         bool acquire_resize()
 244         {
 245             owner_t me = (owner_t)std::this_thread::get_id();
 246
 247             back_off bkoff;
 248             for (unsigned int nAttempts = 0; nAttempts < 32; ++nAttempts ) {
 249                 owner_t ownNull = 0;
 250                 if ( m_Owner.compare_exchange_strong( ownNull, (me << 1) | 1, CDS_ATOMIC::memory_order_acquire, CDS_ATOMIC::memory_order_relaxed )) {
 251                     lock_array_ptr pOldLocks = m_arrLocks;
 252                     size_t const nLockCount = pOldLocks->size();
 253                     for ( size_t i = 0; i < nLockCount; ++i ) {
 254                         typename lock_array_type::lock_type& lock = pOldLocks->at(i);
 255                         bkoff.reset();
 256                         while ( !lock.try_lock() )
 257                             bkoff();
 258                         lock.unlock();
 259                     }
 260                     return true;
 261                 }
 262                 else
 263                     bkoff();
 264             }
 265             return false;
 266         }
 267
 268         void release_resize()
 269         {
 270             m_Owner.store( 0, CDS_ATOMIC::memory_order_release );
 271         }
 272         //@endcond
 273     public:
 274         //@cond
 275         class scoped_cell_lock {
 276             cds::lock::scoped_lock< lock_type >   m_guard;
 277
 278         public:
 279             scoped_cell_lock( refinable& policy, size_t nHash )
 280                 : m_guard( policy.acquire( nHash ), true )
 281             {}
 282         };
 283
 284         class scoped_full_lock {
 285             refinable&      m_Policy;
 286             lock_array_ptr  m_Locks;
 287         public:
 288             scoped_full_lock( refinable& policy )
 289                 : m_Policy( policy )
 290             {
 291                 m_Locks = policy.acquire_all();
 292             }
 293             ~scoped_full_lock()
 294             {
 295                 m_Policy.release_all( m_Locks );
 296             }
 297         };
 298
 299         class scoped_resize_lock {
 300             refinable&      m_Policy;
 301             bool            m_bSucceess;
 302
 303         public:
 304             scoped_resize_lock( refinable& policy )
 305                 : m_Policy( policy )
 306             {
 307                 m_bSucceess = policy.acquire_resize();
 308             }
 309
 310             ~scoped_resize_lock()
 311             {
 312                 if ( m_bSucceess )
 313                     m_Policy.release_resize();
 314             }
 315
 316             bool success() const
 317             {
 318                 return m_bSucceess;
 319             }
 320         };
 321         //@endcond
 322
 323     public:
 324         /// Constructor
 325         refinable(
 326             size_t nLockCount   ///< Initial size of lock array. Must be power of two.
 327         )
 328         : m_Owner(0)
 329         , m_nCapacity( nLockCount )
 330         {
 331             assert( cds::beans::is_power2( nLockCount ));
 332             m_arrLocks = create_lock_array( nLockCount );
 333         }
 334
 335         /// Returns lock array size
 336         /**
 337             Lock array size is not a constant for \p refinable policy and can be changed when the set is resized.
 338         */
 339         size_t lock_count() const
 340         {
 341             return m_nCapacity.load( CDS_ATOMIC::memory_order_relaxed );
 342         }
 343
 344         /// Resize for new capacity
 345         void resize( size_t nNewCapacity )
 346         {
 347             // Expect the access is locked by scoped_resize_lock!!!
 348             lock_array_ptr pNewArr = create_lock_array( nNewCapacity );
 349             scoped_spinlock sl(m_access);
 350             m_arrLocks.swap( pNewArr );
 351         }
 352     };
 353
 354 }}} // namespace cds::intrusive::striped_set
 355
 356 #endif