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