cds/container/segmented_queue.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDS_CONTAINER_SEGMENTED_QUEUE_H
   4 #define __CDS_CONTAINER_SEGMENTED_QUEUE_H
   5
   6 #include <memory>
   7 #include <functional>   // ref
   8 #include <cds/intrusive/segmented_queue.h>
   9 #include <cds/details/trivial_assign.h>
  10
  11 namespace cds { namespace container {
  12
  13     /// SegmentedQueue -related declarations
  14     namespace segmented_queue {
  15
  16 #   ifdef CDS_DOXYGEN_INVOKED
  17         /// SegmentedQueue internal statistics
  18         typedef cds::intrusive::segmented_queue::stat stat;
  19 #   else
  20         using cds::intrusive::segmented_queue::stat;
  21 #   endif
  22
  23         /// SegmentedQueue empty internal statistics (no overhead)
  24         typedef cds::intrusive::segmented_queue::empty_stat empty_stat;
  25
  26         /// SegmentedQueue default type traits
  27         struct traits {
  28
  29             /// Item allocator. Default is \ref CDS_DEFAULT_ALLOCATOR
  30             typedef CDS_DEFAULT_ALLOCATOR   node_allocator;
  31
  32             /// Item counter, default is atomicity::item_counter
  33             /**
  34                 The item counting is an essential part of segmented queue algorithm.
  35                 The \p empty() member function is based on checking <tt>size() == 0</tt>.
  36                 Therefore, dummy item counter like atomicity::empty_item_counter is not the proper counter.
  37             */
  38             typedef atomicity::item_counter item_counter;
  39
  40             /// Internal statistics, possible predefined types are \ref stat, \ref empty_stat (the default)
  41             typedef segmented_queue::empty_stat        stat;
  42
  43             /// Memory model, default is opt::v::relaxed_ordering. See cds::opt::memory_model for the full list of possible types
  44             typedef opt::v::relaxed_ordering  memory_model;
  45
  46             /// Alignment of critical data, default is cache line alignment. See cds::opt::alignment option specification
  47             enum { alignment = opt::cache_line_alignment };
  48
  49             /// Padding of segment data, default is no special padding
  50             /** @copydetails cds::intrusive::segmented_queue::traits::padding
  51             */
  52             enum { padding = cds::intrusive::segmented_queue::traits::padding };
  53
  54             /// Segment allocator. Default is \ref CDS_DEFAULT_ALLOCATOR
  55             typedef CDS_DEFAULT_ALLOCATOR allocator;
  56
  57             /// Lock type used to maintain an internal list of allocated segments
  58             typedef cds::lock::Spin lock_type;
  59
  60             /// Random \ref cds::opt::permutation_generator "permutation generator" for sequence [0, quasi_factor)
  61             typedef cds::opt::v::random2_permutation<int>    permutation_generator;
  62         };
  63
  64          /// Metafunction converting option list to traits for SegmentedQueue
  65         /**
  66             The metafunction can be useful if a few fields in \p segmented_queue::traits should be changed.
  67             For example:
  68             \code
  69             typedef cds::container::segmented_queue::make_traits<
  70                 cds::opt::item_counter< cds::atomicity::item_counter >
  71             >::type my_segmented_queue_traits;
  72             \endcode
  73             This code creates \p %SegmentedQueue type traits with item counting feature,
  74             all other \p segmented_queue::traits members left unchanged.
  75
  76             \p Options are:
  77             - \p opt::node_allocator - node allocator.
  78             - \p opt::stat - internal statistics, possible type: \p segmented_queue::stat, \p segmented_queue::empty_stat (the default)
  79             - \p opt::item_counter - item counting feature. Note that \p atomicity::empty_item_counetr is not suitable
  80                 for segmented queue.
  81             - \p opt::memory_model - memory model, default is \p opt::v::relaxed_ordering.
  82                 See option description for the full list of possible models
  83             - \p opt::alignment - the alignment of critical data, see option description for explanation
  84             - \p opt::padding - the padding of segment data, default no special padding.
  85                 See \p traits::padding for explanation.
  86             - \p opt::allocator - the allocator used to maintain segments.
  87             - \p opt::lock_type - a mutual exclusion lock type used to maintain internal list of allocated
  88                 segments. Default is \p cds::opt::Spin, \p std::mutex is also suitable.
  89             - \p opt::permutation_generator - a random permutation generator for sequence [0, quasi_factor),
  90                 default is \p cds::opt::v::random2_permutation<int>
  91         */
  92         template <typename... Options>
  93         struct make_traits {
  94 #   ifdef CDS_DOXYGEN_INVOKED
  95             typedef implementation_defined type ;   ///< Metafunction result
  96 #   else
  97             typedef typename cds::opt::make_options<
  98                 typename cds::opt::find_type_traits< traits, Options... >::type
  99                 ,Options...
 100             >::type   type;
 101 #   endif
 102         };
 103
 104     } // namespace segmented_queue
 105
 106     //@cond
 107     namespace details {
 108
 109         template <typename GC, typename T, typename Traits>
 110         struct make_segmented_queue
 111         {
 112             typedef GC      gc;
 113             typedef T       value_type;
 114             typedef Traits  original_type_traits;
 115
 116             typedef cds::details::Allocator< T, typename original_type_traits::node_allocator > cxx_node_allocator;
 117             struct node_disposer {
 118                 void operator()( T * p )
 119                 {
 120                     cxx_node_allocator().Delete( p );
 121                 }
 122             };
 123
 124             struct intrusive_type_traits: public original_type_traits
 125             {
 126                 typedef node_disposer   disposer;
 127             };
 128
 129             typedef cds::intrusive::SegmentedQueue< gc, value_type, intrusive_type_traits > type;
 130         };
 131
 132     } // namespace details
 133     //@endcond
 134
 135     /// Segmented queue
 136     /** @ingroup cds_nonintrusive_queue
 137
 138         The queue is based on work
 139         - [2010] Afek, Korland, Yanovsky "Quasi-Linearizability: relaxed consistency for improved concurrency"
 140
 141         In this paper the authors offer a relaxed version of linearizability, so-called quasi-linearizability,
 142         that preserves some of the intuition, provides a flexible way to control the level of relaxation
 143         and supports th implementation of more concurrent and scalable data structure.
 144         Intuitively, the linearizability requires each run to be equivalent in some sense to a serial run
 145         of the algorithm. This equivalence to some serial run imposes strong synchronization requirements
 146         that in many cases results in limited scalability and synchronization bottleneck.
 147
 148         The general idea is that the queue maintains a linked list of segments, each segment is an array of
 149         nodes in the size of the quasi factor, and each node has a deleted boolean marker, which states
 150         if it has been dequeued. Each producer iterates over last segment in the linked list in some random
 151         permutation order. Whet it finds an empty cell it performs a CAS operation attempting to enqueue its
 152         new element. In case the entire segment has been scanned and no available cell is found (implying
 153         that the segment is full), then it attempts to add a new segment to the list.
 154
 155         The dequeue operation is similar: the consumer iterates over the first segment in the linked list
 156         in some random permutation order. When it finds an item which has not yet been dequeued, it performs
 157         CAS on its deleted marker in order to "delete" it, if succeeded this item is considered dequeued.
 158         In case the entire segment was scanned and all the nodes have already been dequeued (implying that
 159         the segment is empty), then it attempts to remove this segment from the linked list and starts
 160         the same process on the next segment. If there is no next segment, the queue is considered empty.
 161
 162         Based on the fact that most of the time threads do not add or remove segments, most of the work
 163         is done in parallel on different cells in the segments. This ensures a controlled contention
 164         depending on the segment size, which is quasi factor.
 165
 166         The segmented queue is an <i>unfair</i> queue since it violates the strong FIFO order but no more than
 167         quasi factor. It means that the consumer dequeues any item from the current first segment.
 168
 169         Template parameters:
 170         - \p GC - a garbage collector, possible types are cds::gc::HP, cds::gc::PTB
 171         - \p T - the type of values stored in the queue
 172         - \p Traits - queue type traits, default is \p segmented_queue::type_traits.
 173             \p segmented_queue::make_traits metafunction can be used to construct your
 174             type traits.
 175     */
 176     template <class GC, typename T, typename Traits = segmented_queue::traits >
 177     class SegmentedQueue:
 178 #ifdef CDS_DOXYGEN_INVOKED
 179         public cds::intrusive::SegmentedQueue< GC, T, Traits >
 180 #else
 181         public details::make_segmented_queue< GC, T, Traits >::type
 182 #endif
 183     {
 184         //@cond
 185         typedef details::make_segmented_queue< GC, T, Traits > maker;
 186         typedef typename maker::type base_class;
 187         //@endcond
 188     public:
 189         typedef GC  gc;         ///< Garbage collector
 190         typedef T   value_type; ///< type of the value stored in the queue
 191         typedef Traits traits;  ///< Queue traits
 192
 193         typedef typename traits::node_allocator node_allocator;   ///< Node allocator
 194         typedef typename base_class::memory_model  memory_model;   ///< Memory ordering. See cds::opt::memory_model option
 195         typedef typename base_class::item_counter  item_counter;   ///< Item counting policy, see cds::opt::item_counter option setter
 196         typedef typename base_class::stat          stat        ;   ///< Internal statistics policy
 197         typedef typename base_class::lock_type     lock_type   ;   ///< Type of mutex for maintaining an internal list of allocated segments.
 198         typedef typename base_class::permutation_generator permutation_generator; ///< Random permutation generator for sequence [0, quasi-factor)
 199
 200         static const size_t m_nHazardPtrCount = base_class::m_nHazardPtrCount ; ///< Count of hazard pointer required for the algorithm
 201
 202     protected:
 203         //@cond
 204         typedef typename maker::cxx_node_allocator  cxx_node_allocator;
 205         typedef std::unique_ptr< value_type, typename maker::node_disposer >  scoped_node_ptr;
 206
 207         static value_type * alloc_node( value_type const& v )
 208         {
 209             return cxx_node_allocator().New( v );
 210         }
 211
 212         static value_type * alloc_node()
 213         {
 214             return cxx_node_allocator().New();
 215         }
 216
 217         template <typename... Args>
 218         static value_type * alloc_node_move( Args&&... args )
 219         {
 220             return cxx_node_allocator().MoveNew( std::forward<Args>( args )... );
 221         }
 222         //@endcond
 223
 224     public:
 225         /// Initializes the empty queue
 226         SegmentedQueue(
 227             size_t nQuasiFactor     ///< Quasi factor. If it is not a power of 2 it is rounded up to nearest power of 2. Minimum is 2.
 228             )
 229             : base_class( nQuasiFactor )
 230         {}
 231
 232         /// Clears the queue and deletes all internal data
 233         ~SegmentedQueue()
 234         {}
 235
 236         /// Inserts a new element at last segment of the queue
 237         /**
 238             The function makes queue node in dynamic memory calling copy constructor for \p val
 239             and then it calls intrusive::SEgmentedQueue::enqueue.
 240             Returns \p true if success, \p false otherwise.
 241         */
 242         bool enqueue( value_type const& val )
 243         {
 244             scoped_node_ptr p( alloc_node(val) );
 245             if ( base_class::enqueue( *p ) ) {
 246                 p.release();
 247                 return true;
 248             }
 249             return false;
 250         }
 251
 252         /// Enqueues data to the queue using a functor
 253         /**
 254             \p Func is a functor called to create node.
 255             The functor \p f takes one argument - a reference to a new node of type \ref value_type :
 256             \code
 257             cds::container::SegmentedQueue< cds::gc::HP, Foo > myQueue;
 258             Bar bar;
 259             myQueue.enqueue_with( [&bar]( Foo& dest ) { dest = bar; } );
 260             \endcode
 261         */
 262         template <typename Func>
 263         bool enqueue_with( Func f )
 264         {
 265             scoped_node_ptr p( alloc_node() );
 266             f( *p );
 267             if ( base_class::enqueue( *p ) ) {
 268                 p.release();
 269                 return true;
 270             }
 271             return false;
 272         }
 273
 274
 275         /// Synonym for \p enqueue() member function
 276         bool push( value_type const& val )
 277         {
 278             return enqueue( val );
 279         }
 280
 281         /// Synonym for \p enqueue_with() member function
 282         template <typename Func>
 283         bool push_with( Func f )
 284         {
 285             return enqueue_with( f );
 286         }
 287
 288         /// Enqueues data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
 289         template <typename... Args>
 290         bool emplace( Args&&... args )
 291         {
 292             scoped_node_ptr p( alloc_node_move( std::forward<Args>(args)... ) );
 293             if ( base_class::enqueue( *p )) {
 294                 p.release();
 295                 return true;
 296             }
 297             return false;
 298         }
 299
 300         /// Dequeues a value from the queue
 301         /**
 302             If queue is not empty, the function returns \p true, \p dest contains copy of
 303             dequeued value. The assignment operator for type \ref value_type is invoked.
 304             If queue is empty, the function returns \p false, \p dest is unchanged.
 305         */
 306         bool dequeue( value_type& dest )
 307         {
 308             return dequeue_with( [&dest]( value_type& src ) { dest = src; });
 309         }
 310
 311         /// Dequeues a value using a functor
 312         /**
 313             \p Func is a functor called to copy dequeued value.
 314             The functor takes one argument - a reference to removed node:
 315             \code
 316             cds:container::MSQueue< cds::gc::HP, Foo > myQueue;
 317             Bar bar;
 318             myQueue.dequeue_with( [&bar]( Foo& src ) { bar = std::move( src );});
 319             \endcode
 320             The functor is called only if the queue is not empty.
 321         */
 322         template <typename Func>
 323         bool dequeue_with( Func f )
 324         {
 325             value_type * p = base_class::dequeue();
 326             if ( p ) {
 327                 f( *p );
 328                 gc::template retire< typename maker::node_disposer >( p );
 329                 return true;
 330             }
 331             return false;
 332         }
 333
 334         /// Synonym for \p dequeue_with() function
 335         template <typename Func>
 336         bool pop_with( Func f )
 337         {
 338             return dequeue_with( f );
 339         }
 340
 341         /// Synonym for \p dequeue() function
 342         bool pop( value_type& dest )
 343         {
 344             return dequeue( dest );
 345         }
 346
 347         /// Checks if the queue is empty
 348         /**
 349             The original segmented queue algorithm does not allow to check emptiness accurately
 350             because \p empty() is unlinearizable.
 351             This function tests queue's emptiness checking <tt>size() == 0</tt>,
 352             so, the item counting feature is an essential part of queue's algorithm.
 353         */
 354         bool empty() const
 355         {
 356             return base_class::empty();
 357         }
 358
 359         /// Clear the queue
 360         /**
 361             The function repeatedly calls \ref dequeue until it returns \p nullptr.
 362             The disposer specified in \p Traits template argument is called for each removed item.
 363         */
 364         void clear()
 365         {
 366             base_class::clear();
 367         }
 368
 369         /// Returns queue's item count
 370         size_t size() const
 371         {
 372             return base_class::size();
 373         }
 374
 375         /// Returns reference to internal statistics
 376         /**
 377             The type of internal statistics is specified by \p Traits template argument.
 378         */
 379         const stat& statistics() const
 380         {
 381             return base_class::statistics();
 382         }
 383
 384         /// Returns quasi factor, a power-of-two number
 385         size_t quasi_factor() const
 386         {
 387             return base_class::quasi_factor();
 388         }
 389     };
 390
 391 }} // namespace cds::container
 392
 393 #endif // #ifndef __CDS_CONTAINER_SEGMENTED_QUEUE_H