cds/intrusive/msqueue.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDS_INTRUSIVE_MSQUEUE_H
   4 #define __CDS_INTRUSIVE_MSQUEUE_H
   5
   6 #include <type_traits>
   7 #include <cds/intrusive/details/single_link_struct.h>
   8 #include <cds/cxx11_atomic.h>
   9
  10 namespace cds { namespace intrusive {
  11
  12     /// MSQueue related definitions
  13     /** @ingroup cds_intrusive_helper
  14     */
  15     namespace msqueue {
  16
  17         /// Queue node
  18         /**
  19             Template parameters:
  20             - GC - garbage collector used
  21             - Tag - a \ref cds_intrusive_hook_tag "tag"
  22         */
  23         template <class GC, typename Tag = opt::none >
  24         using node = cds::intrusive::single_link::node< GC, Tag > ;
  25
  26         /// Base hook
  27         /**
  28             \p Options are:
  29             - opt::gc - garbage collector used.
  30             - opt::tag - a \ref cds_intrusive_hook_tag "tag"
  31         */
  32         template < typename... Options >
  33         using base_hook = cds::intrusive::single_link::base_hook< Options...>;
  34
  35         /// Member hook
  36         /**
  37             \p MemberOffset specifies offset in bytes of \ref node member into your structure.
  38             Use \p offsetof macro to define \p MemberOffset
  39
  40             \p Options are:
  41             - opt::gc - garbage collector used.
  42             - opt::tag - a \ref cds_intrusive_hook_tag "tag"
  43         */
  44         template < size_t MemberOffset, typename... Options >
  45         using member_hook = cds::intrusive::single_link::member_hook< MemberOffset, Options... >;
  46
  47         /// Traits hook
  48         /**
  49             \p NodeTraits defines type traits for node.
  50             See \ref node_traits for \p NodeTraits interface description
  51
  52             \p Options are:
  53             - opt::gc - garbage collector used.
  54             - opt::tag - a \ref cds_intrusive_hook_tag "tag"
  55         */
  56         template <typename NodeTraits, typename... Options >
  57         using traits_hook = cds::intrusive::single_link::traits_hook< NodeTraits, Options... >;
  58
  59         /// Queue internal statistics. May be used for debugging or profiling
  60         /**
  61             Template argument \p Counter defines type of counter.
  62             Default is \p cds::atomicity::event_counter, that is weak, i.e. it is not guaranteed
  63             strict event counting.
  64             You may use stronger type of counter like as \p cds::atomicity::item_counter,
  65             or even integral type, for example, \p int.
  66         */
  67         template <typename Counter = cds::atomicity::event_counter >
  68         struct stat
  69         {
  70             typedef Counter     counter_type;   ///< Counter type
  71
  72             counter_type m_EnqueueCount      ;  ///< Enqueue call count
  73             counter_type m_DequeueCount      ;  ///< Dequeue call count
  74             counter_type m_EnqueueRace       ;  ///< Count of enqueue race conditions encountered
  75             counter_type m_DequeueRace       ;  ///< Count of dequeue race conditions encountered
  76             counter_type m_AdvanceTailError  ;  ///< Count of "advance tail failed" events
  77             counter_type m_BadTail           ;  ///< Count of events "Tail is not pointed to the last item in the queue"
  78
  79             /// Register enqueue call
  80             void onEnqueue()                { ++m_EnqueueCount; }
  81             /// Register dequeue call
  82             void onDequeue()                { ++m_DequeueCount; }
  83             /// Register enqueue race event
  84             void onEnqueueRace()            { ++m_EnqueueRace; }
  85             /// Register dequeue race event
  86             void onDequeueRace()            { ++m_DequeueRace; }
  87             /// Register "advance tail failed" event
  88             void onAdvanceTailFailed()      { ++m_AdvanceTailError; }
  89             /// Register event "Tail is not pointed to last item in the queue"
  90             void onBadTail()                { ++m_BadTail; }
  91
  92             //@cond
  93             void reset()
  94             {
  95                 m_EnqueueCount.reset();
  96                 m_DequeueCount.reset();
  97                 m_EnqueueRace.reset();
  98                 m_DequeueRace.reset();
  99                 m_AdvanceTailError.reset();
 100                 m_BadTail.reset();
 101             }
 102
 103             stat& operator +=( stat const& s )
 104             {
 105                 m_EnqueueCount += s.m_EnqueueCount.get();
 106                 m_DequeueCount += s.m_DequeueCount.get();
 107                 m_EnqueueRace += s.m_EnqueueRace.get();
 108                 m_DequeueRace += s.m_DequeueRace.get();
 109                 m_AdvanceTailError += s.m_AdvanceTailError.get();
 110                 m_BadTail += s.m_BadTail.get();
 111
 112                 return *this;
 113             }
 114             //@endcond
 115         };
 116
 117         /// Dummy queue statistics - no counting is performed, no overhead. Support interface like \p msqueue::stat
 118         struct empty_stat
 119         {
 120             //@cond
 121             void onEnqueue()                {}
 122             void onDequeue()                {}
 123             void onEnqueueRace()            {}
 124             void onDequeueRace()            {}
 125             void onAdvanceTailFailed()      {}
 126             void onBadTail()                {}
 127
 128             void reset() {}
 129             empty_stat& operator +=( empty_stat const& s )
 130             {
 131                 return *this;
 132             }
 133             //@endcond
 134         };
 135
 136         /// MSQueue default type traits
 137         struct traits
 138         {
 139             /// Back-off strategy
 140             typedef cds::backoff::empty         back_off;
 141
 142             /// Hook, possible types are \p msqueue::base_hook, \p msqueue::member_hook, \p msqueue::traits_hook
 143             typedef msqueue::base_hook<>        hook;
 144
 145             /// The functor used for dispose removed items. Default is \p opt::v::empty_disposer. This option is used for dequeuing
 146             typedef opt::v::empty_disposer      disposer;
 147
 148             /// Item counting feature; by default, disabled. Use \p cds::atomicity::item_counter to enable item counting
 149             typedef atomicity::empty_item_counter   item_counter;
 150
 151             /// Internal statistics (by default, disabled)
 152             /**
 153                 Possible option value are: \p msqueue::stat, \p msqueue::empty_stat (the default),
 154                 user-provided class that supports \p %msqueue::stat interface.
 155             */
 156             typedef msqueue::empty_stat         stat;
 157
 158             /// C++ memory ordering model
 159             /**
 160                 Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
 161                 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
 162             */
 163             typedef opt::v::relaxed_ordering    memory_model;
 164
 165             /// Link checking, see \p cds::opt::link_checker
 166             static CDS_CONSTEXPR const opt::link_check_type link_checker = opt::debug_check_link;
 167
 168             /// Alignment for internal queue data. Default is \p opt::cache_line_alignment
 169             enum { alignment = opt::cache_line_alignment };
 170         };
 171
 172         /// Metafunction converting option list to \p msqueue::traits
 173         /**
 174             This is a wrapper for <tt> cds::opt::make_options< type_traits, Options...> </tt>
 175             Supported \p Options are:
 176
 177             - opt::hook - hook used. Possible hooks are: \p msqueue::base_hook, \p msqueue::member_hook, \p msqueue::traits_hook.
 178                 If the option is not specified, \p %msqueue::base_hook<> is used.
 179             - opt::back_off - back-off strategy used, default is \p cds::backoff::empty.
 180             - opt::disposer - the functor used for dispose removed items. Default is \p opt::v::empty_disposer. This option is used
 181                 when dequeuing.
 182             - opt::link_checker - the type of node's link fields checking. Default is \p opt::debug_check_link
 183             - opt::item_counter - the type of item counting feature. Default is \p cds::atomicity::empty_item_counter (item counting disabled)
 184                 To enable item counting use \p cds::atomicity::item_counter
 185             - opt::stat - the type to gather internal statistics.
 186                 Possible statistics types are: \p msqueue::stat, \p msqueue::empty_stat, user-provided class that supports \p %msqueue::stat interface.
 187                 Default is \p %msqueue::empty_stat (internal statistics disabled).
 188             - opt::alignment - the alignment for internal queue data. Default is \p opt::cache_line_alignment
 189             - opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
 190                 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
 191
 192             Example: declare \p %MSQueue with item counting and internal statistics
 193             \code
 194             typedef cds::intrusive::MSQueue< cds::gc::HP, Foo,
 195                 typename cds::intrusive::msqueue::make_traits<
 196                     cds::intrusive::opt:hook< cds::intrusive::msqueue::base_hook< cds::opt::gc<cds:gc::HP> >>,
 197                     cds::opt::item_counte< cds::atomicity::item_counter >,
 198                     cds::opt::stat< cds::intrusive::msqueue::stat<> >
 199                 >::type
 200             > myQueue;
 201             \endcode
 202         */
 203         template <typename... Options>
 204         struct make_traits {
 205 #   ifdef CDS_DOXYGEN_INVOKED
 206             typedef implementation_defined type;   ///< Metafunction result
 207 #   else
 208             typedef typename cds::opt::make_options<
 209                 typename cds::opt::find_type_traits< traits, Options... >::type
 210                 , Options...
 211             >::type type;
 212 #   endif
 213         };
 214
 215
 216     } // namespace msqueue
 217
 218     /// Michael & Scott's intrusive lock-free queue
 219     /** @ingroup cds_intrusive_queue
 220         Implementation of well-known Michael & Scott's queue algorithm:
 221         - [1998] Maged Michael, Michael Scott "Simple, fast, and practical non-blocking and blocking concurrent queue algorithms"
 222
 223         Template arguments:
 224         - \p GC - garbage collector type: \p gc::HP, \p gc::DHP
 225         - \p T - type of value to be stored in the queue. A value of type \p T must be derived from \p msqueue::node for \p msqueue::base_hook,
 226             or it should have a member of type \p %msqueue::node for \p msqueue::member_hook,
 227             or it should be convertible to \p %msqueue::node for \p msqueue::traits_hook.
 228         - \p Traits - queue traits, default is \p msqueue::traits. You can use \p msqueue::make_traits
 229             metafunction to make your traits or just derive your traits from \p %msqueue::traits:
 230             \code
 231             struct myTraits: public cds::intrusive::msqueue::traits {
 232                 typedef cds::intrusive::msqueue::stat<> stat;
 233                 typedef cds::atomicity::item_counter    item_counter;
 234             };
 235             typedef cds::intrusive::MSQueue< cds::gc::HP, Foo, myTraits > myQueue;
 236
 237             // Equivalent make_traits example:
 238             typedef cds::intrusive::MSQueue< cds::gc::HP, Foo,
 239                 typename cds::intrusive::msqueue::make_traits<
 240                     cds::opt::stat< cds::intrusive::msqueue::stat<> >,
 241                     cds::opt::item_counter< cds::atomicity::item_counter >
 242                 >::type
 243             > myQueue;
 244             \endcode
 245
 246         \par About item disposing
 247         The Michael & Scott's queue algo has a key feature: even if the queue is empty it contains one item that is "dummy" one from
 248         the standpoint of the algo. See \p dequeue() function for explanation.
 249
 250         \par Examples
 251         \code
 252         #include <cds/intrusive/msqueue.h>
 253         #include <cds/gc/hp.h>
 254
 255         namespace ci = cds::inrtusive;
 256         typedef cds::gc::HP hp_gc;
 257
 258         // MSQueue with Hazard Pointer garbage collector, base hook + item disposer:
 259         struct Foo: public ci::msqueue::node< hp_gc >
 260         {
 261             // Your data
 262             ...
 263         };
 264
 265         // Disposer for Foo struct just deletes the object passed in
 266         struct fooDisposer {
 267             void operator()( Foo * p )
 268             {
 269                 delete p;
 270             }
 271         };
 272
 273         // Declare traits for the queue
 274         struct myTraits: public ci::msqueue::traits {
 275             ,ci::opt::hook<
 276                 ci::msqueue::base_hook< ci::opt::gc<hp_gc> >
 277             >
 278             ,ci::opt::disposer< fooDisposer >
 279         };
 280
 281         // At least, declare the queue type
 282         typedef ci::MSQueue< hp_gc, Foo, myTraits > fooQueue;
 283
 284         // Example 2:
 285         //  MSQueue with Hazard Pointer garbage collector,
 286         //  member hook + item disposer + item counter,
 287         //  without alignment of internal queue data
 288         //  Use msqueue::make_traits
 289         struct Bar
 290         {
 291             // Your data
 292             ...
 293             ci::msqueue::node< hp_gc > hMember;
 294         };
 295
 296         typedef ci::MSQueue< hp_gc,
 297             Foo,
 298             typename ci::msqueue::make_traits<
 299                 ci::opt::hook<
 300                     ci::msqueue::member_hook<
 301                         offsetof(Bar, hMember)
 302                         ,ci::opt::gc<hp_gc>
 303                     >
 304                 >
 305                 ,ci::opt::disposer< fooDisposer >
 306                 ,cds::opt::item_counter< cds::atomicity::item_counter >
 307                 ,cds::opt::alignment< cds::opt::no_special_alignment >
 308             >::type
 309         > barQueue;
 310         \endcode
 311     */
 312     template <typename GC, typename T, typename Traits>
 313     class MSQueue
 314     {
 315     public:
 316         typedef GC gc;          ///< Garbage collector
 317         typedef T  value_type;  ///< type of value stored in the queue
 318         typedef Traits traits;  ///< Queue traits
 319
 320         typedef typename traits::hook       hook;       ///< hook type
 321         typedef typename hook::node_type    node_type;  ///< node type
 322         typedef typename traits::disposer   disposer;   ///< disposer used
 323         typedef typename get_node_traits< value_type, node_type, hook>::type node_traits;   ///< node traits
 324         typedef typename single_link::get_link_checker< node_type, traits::link_checker >::type link_checker;   ///< link checker
 325
 326         typedef typename traits::back_off   back_off;       ///< back-off strategy
 327         typedef typename traits::item_counter item_counter; ///< Item counter class
 328         typedef typename traits::stat       stat;           ///< Internal statistics
 329         typedef typename traits::memory_model memory_model; ///< Memory ordering. See \p cds::opt::memory_model option
 330
 331         /// Rebind template arguments
 332         template <typename GC2, typename T2, typename Traits2>
 333         struct rebind {
 334             typedef MSQueue< GC2, T2, Traits2 > other;   ///< Rebinding result
 335         };
 336
 337         static CDS_CONSTEXPR const size_t m_nHazardPtrCount = 2; ///< Count of hazard pointer required for the algorithm
 338
 339     protected:
 340         //@cond
 341
 342         // GC and node_type::gc must be the same
 343         static_assert((std::is_same<gc, typename node_type::gc>::value), "GC and node_type::gc must be the same");
 344
 345         typedef intrusive::node_to_value<MSQueue> node_to_value;
 346         typedef typename opt::details::alignment_setter< typename node_type::atomic_node_ptr, traits::alignment >::type aligned_node_ptr;
 347         typedef typename opt::details::alignment_setter< node_type, traits::alignment >::type dummy_node_type;
 348
 349         aligned_node_ptr    m_pHead ;           ///< Queue's head pointer
 350         aligned_node_ptr    m_pTail ;           ///< Queue's tail pointer
 351         dummy_node_type     m_Dummy ;           ///< dummy node
 352         item_counter        m_ItemCounter   ;   ///< Item counter
 353         stat                m_Stat  ;           ///< Internal statistics
 354         //@endcond
 355
 356         //@cond
 357         struct dequeue_result {
 358             typename gc::template GuardArray<2>  guards;
 359
 360             node_type * pHead;
 361             node_type * pNext;
 362         };
 363
 364         bool do_dequeue( dequeue_result& res )
 365         {
 366             node_type * pNext;
 367             back_off bkoff;
 368
 369             node_type * h;
 370             while ( true ) {
 371                 h = res.guards.protect( 0, m_pHead, node_to_value() );
 372                 pNext = h->m_pNext.load( memory_model::memory_order_relaxed );
 373                 res.guards.assign( 1, node_to_value()( pNext ));
 374                 if ( m_pHead.load(memory_model::memory_order_acquire) != h )
 375                     continue;
 376
 377                 if ( pNext == nullptr )
 378                     return false ;    // empty queue
 379
 380                 node_type * t = m_pTail.load(memory_model::memory_order_acquire);
 381                 if ( h == t ) {
 382                     // It is needed to help enqueue
 383                     m_pTail.compare_exchange_strong( t, pNext, memory_model::memory_order_release, atomics::memory_order_relaxed );
 384                     m_Stat.onBadTail();
 385                     continue;
 386                 }
 387
 388                 if ( m_pHead.compare_exchange_strong( h, pNext, memory_model::memory_order_release, atomics::memory_order_relaxed ))
 389                     break;
 390
 391                 m_Stat.onDequeueRace();
 392                 bkoff();
 393             }
 394
 395             --m_ItemCounter;
 396             m_Stat.onDequeue();
 397
 398             res.pHead = h;
 399             res.pNext = pNext;
 400             return true;
 401         }
 402
 403         static void clear_links( node_type * pNode )
 404         {
 405             pNode->m_pNext.store( nullptr, memory_model::memory_order_release );
 406         }
 407
 408         void dispose_result( dequeue_result& res )
 409         {
 410             dispose_node( res.pHead );
 411         }
 412
 413         void dispose_node( node_type * p )
 414         {
 415             // Note about the dummy node:
 416             // We cannot clear m_Dummy here since it leads to ABA.
 417             // On the other hand, we cannot use deferred clear_links( &m_Dummy ) call via
 418             // HP retiring cycle since m_Dummy is member of MSQueue and may be destroyed
 419             // before HP retiring cycle invocation.
 420             // So, we will never clear m_Dummy
 421
 422             struct disposer_thunk {
 423                 void operator()( value_type * p ) const
 424                 {
 425                     assert( p != nullptr );
 426                     MSQueue::clear_links( node_traits::to_node_ptr( p ) );
 427                     disposer()(p);
 428                 }
 429             };
 430
 431             if ( p != &m_Dummy )
 432                 gc::template retire<disposer_thunk>( node_traits::to_value_ptr( p ) );
 433         }
 434         //@endcond
 435
 436     public:
 437         /// Initializes empty queue
 438         MSQueue()
 439             : m_pHead( &m_Dummy )
 440             , m_pTail( &m_Dummy )
 441         {}
 442
 443         /// Destructor clears the queue
 444         /**
 445             Since the Michael & Scott queue contains at least one item even
 446             if the queue is empty, the destructor may call item disposer.
 447         */
 448         ~MSQueue()
 449         {
 450             clear();
 451
 452             node_type * pHead = m_pHead.load(memory_model::memory_order_relaxed);
 453
 454             assert( pHead != nullptr );
 455             assert( pHead == m_pTail.load(memory_model::memory_order_relaxed) );
 456
 457             m_pHead.store( nullptr, memory_model::memory_order_relaxed );
 458             m_pTail.store( nullptr, memory_model::memory_order_relaxed );
 459
 460             dispose_node( pHead );
 461         }
 462
 463         /// Enqueues \p val value into the queue.
 464         /** @anchor cds_intrusive_MSQueue_enqueue
 465             The function always returns \p true.
 466         */
 467         bool enqueue( value_type& val )
 468         {
 469             node_type * pNew = node_traits::to_node_ptr( val );
 470             link_checker::is_empty( pNew );
 471
 472             typename gc::Guard guard;
 473             back_off bkoff;
 474
 475             node_type * t;
 476             while ( true ) {
 477                 t = guard.protect( m_pTail, node_to_value() );
 478
 479                 node_type * pNext = t->m_pNext.load(memory_model::memory_order_acquire);
 480                 if ( pNext != nullptr ) {
 481                     // Tail is misplaced, advance it
 482                     m_pTail.compare_exchange_weak( t, pNext, memory_model::memory_order_release, atomics::memory_order_relaxed );
 483                     m_Stat.onBadTail();
 484                     continue;
 485                 }
 486
 487                 node_type * tmp = nullptr;
 488                 if ( t->m_pNext.compare_exchange_strong( tmp, pNew, memory_model::memory_order_release, atomics::memory_order_relaxed ))
 489                     break;
 490
 491                 m_Stat.onEnqueueRace();
 492                 bkoff();
 493             }
 494             ++m_ItemCounter;
 495             m_Stat.onEnqueue();
 496
 497             if ( !m_pTail.compare_exchange_strong( t, pNew, memory_model::memory_order_acq_rel, atomics::memory_order_relaxed ))
 498                 m_Stat.onAdvanceTailFailed();
 499             return true;
 500         }
 501
 502         /// Dequeues a value from the queue
 503         /** @anchor cds_intrusive_MSQueue_dequeue
 504             If the queue is empty the function returns \p nullptr.
 505
 506             \par Warning
 507             The queue algorithm has following feature: when \p %dequeue() is called,
 508             the item returning is still queue's top, and previous top is disposed:
 509
 510             \code
 511             before dequeuing         Dequeue               after dequeuing
 512             +------------------+                           +------------------+
 513       Top ->|      Item 1      |  -> Dispose Item 1        |      Item 2      | <- Top
 514             +------------------+                           +------------------+
 515             |      Item 2      |  -> Return Item 2         |       ...        |
 516             +------------------+
 517             |       ...        |
 518             \endcode
 519
 520             \p %dequeue() function returns Item 2, that becomes new top of queue, and calls
 521             the disposer for Item 1, that was queue's top on function entry.
 522             Thus, you cannot manually delete item returned because it is still included in
 523             item sequence and it has valuable link field that must not be zeroed.
 524             The item should be deleted only in garbage collector retire cycle using the disposer.
 525         */
 526         value_type * dequeue()
 527         {
 528             dequeue_result res;
 529
 530             if ( do_dequeue( res )) {
 531                 dispose_result( res );
 532
 533                 return node_traits::to_value_ptr( *res.pNext );
 534             }
 535             return nullptr;
 536         }
 537
 538         /// Synonym for \ref cds_intrusive_MSQueue_enqueue "enqueue()" function
 539         bool push( value_type& val )
 540         {
 541             return enqueue( val );
 542         }
 543
 544         /// Synonym for \ref cds_intrusive_MSQueue_dequeue "dequeue()" function
 545         value_type * pop()
 546         {
 547             return dequeue();
 548         }
 549
 550         /// Checks if the queue is empty
 551         bool empty() const
 552         {
 553             typename gc::Guard guard;
 554             return guard.protect( m_pHead, node_to_value() )->m_pNext.load( memory_model::memory_order_relaxed ) == nullptr;
 555         }
 556
 557         /// Clear the queue
 558         /**
 559             The function repeatedly calls \p dequeue() until it returns \p nullptr.
 560             The disposer defined in template \p Traits is called for each item
 561             that can be safely disposed.
 562         */
 563         void clear()
 564         {
 565             while ( dequeue() );
 566         }
 567
 568         /// Returns queue's item count
 569         /**
 570             The value returned depends on \p msqueue::traits::item_counter. For \p atomicity::empty_item_counter,
 571             this function always returns 0.
 572
 573             @note Even if you use real item counter and it returns 0, this fact is not mean that the queue
 574             is empty. To check queue emptyness use \p empty() method.
 575         */
 576         size_t size() const
 577         {
 578             return m_ItemCounter.value();
 579         }
 580
 581         /// Returns reference to internal statistics
 582         stat const& statistics() const
 583         {
 584             return m_Stat;
 585         }
 586     };
 587
 588 }} // namespace cds::intrusive
 589
 590 #endif // #ifndef __CDS_INTRUSIVE_MSQUEUE_H