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