cds/intrusive/msqueue.h

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