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