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