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             /// Alignment for internal queue data. Default is \p opt::cache_line_alignment
 175             enum { alignment = opt::cache_line_alignment };
 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::alignment - the alignment for internal queue data. Default is \p opt::cache_line_alignment
 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 alignment 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::alignment< cds::opt::no_special_alignment >
 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 opt::details::alignment_setter< typename node_type::atomic_node_ptr, traits::alignment >::type aligned_node_ptr;
 349         typedef typename opt::details::alignment_setter< node_type, traits::alignment >::type dummy_node_type;
 350
 351         aligned_node_ptr    m_pHead ;           ///< Queue's head pointer
 352         aligned_node_ptr    m_pTail ;           ///< Queue's tail pointer
 353         dummy_node_type     m_Dummy ;           ///< dummy node
 354         item_counter        m_ItemCounter   ;   ///< Item counter
 355         stat                m_Stat  ;           ///< Internal statistics
 356         //@endcond
 357
 358         //@cond
 359         struct dequeue_result {
 360             typename gc::template GuardArray<2>  guards;
 361
 362             node_type * pHead;
 363             node_type * pNext;
 364         };
 365
 366         bool do_dequeue( dequeue_result& res )
 367         {
 368             node_type * pNext;
 369             back_off bkoff;
 370
 371             node_type * h;
 372             while ( true ) {
 373                 h = res.guards.protect( 0, m_pHead, []( node_type * p ) -> value_type * { return node_traits::to_value_ptr( p );});
 374                 pNext = res.guards.protect( 1, h->m_pNext, []( node_type * p ) -> value_type * { return node_traits::to_value_ptr( p );});
 375                 if ( m_pHead.load(memory_model::memory_order_acquire) != h )
 376                     continue;
 377
 378                 if ( pNext == nullptr ) {
 379                     m_Stat.onEmptyDequeue();
 380                     return false;    // empty queue
 381                 }
 382
 383                 node_type * t = m_pTail.load(memory_model::memory_order_acquire);
 384                 if ( h == t ) {
 385                     // It is needed to help enqueue
 386                     m_pTail.compare_exchange_strong( t, pNext, memory_model::memory_order_release, atomics::memory_order_relaxed );
 387                     m_Stat.onBadTail();
 388                     continue;
 389                 }
 390
 391                 if ( m_pHead.compare_exchange_strong( h, pNext, memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
 392                     break;
 393
 394                 m_Stat.onDequeueRace();
 395                 bkoff();
 396             }
 397
 398             --m_ItemCounter;
 399             m_Stat.onDequeue();
 400
 401             res.pHead = h;
 402             res.pNext = pNext;
 403             return true;
 404         }
 405
 406         static void clear_links( node_type * pNode )
 407         {
 408             pNode->m_pNext.store( nullptr, memory_model::memory_order_release );
 409         }
 410
 411         void dispose_result( dequeue_result& res )
 412         {
 413             dispose_node( res.pHead );
 414         }
 415
 416         void dispose_node( node_type * p )
 417         {
 418             // Note about the dummy node:
 419             // We cannot clear m_Dummy here since it leads to ABA.
 420             // On the other hand, we cannot use deferred clear_links( &m_Dummy ) call via
 421             // HP retiring cycle since m_Dummy is member of MSQueue and may be destroyed
 422             // before HP retiring cycle invocation.
 423             // So, we will never clear m_Dummy
 424
 425             struct disposer_thunk {
 426                 void operator()( value_type * p ) const
 427                 {
 428                     assert( p != nullptr );
 429                     MSQueue::clear_links( node_traits::to_node_ptr( p ) );
 430                     disposer()(p);
 431                 }
 432             };
 433
 434             if ( p != &m_Dummy )
 435                 gc::template retire<disposer_thunk>( node_traits::to_value_ptr( p ) );
 436         }
 437         //@endcond
 438
 439     public:
 440         /// Initializes empty queue
 441         MSQueue()
 442             : m_pHead( &m_Dummy )
 443             , m_pTail( &m_Dummy )
 444         {}
 445
 446         /// Destructor clears the queue
 447         /**
 448             Since the Michael & Scott queue contains at least one item even
 449             if the queue is empty, the destructor may call item disposer.
 450         */
 451         ~MSQueue()
 452         {
 453             clear();
 454
 455             node_type * pHead = m_pHead.load(memory_model::memory_order_relaxed);
 456
 457             assert( pHead != nullptr );
 458             assert( pHead == m_pTail.load(memory_model::memory_order_relaxed) );
 459
 460             m_pHead.store( nullptr, memory_model::memory_order_relaxed );
 461             m_pTail.store( nullptr, memory_model::memory_order_relaxed );
 462
 463             dispose_node( pHead );
 464         }
 465
 466         /// Enqueues \p val value into the queue.
 467         /** @anchor cds_intrusive_MSQueue_enqueue
 468             The function always returns \p true.
 469         */
 470         bool enqueue( value_type& val )
 471         {
 472             node_type * pNew = node_traits::to_node_ptr( val );
 473             link_checker::is_empty( pNew );
 474
 475             typename gc::Guard guard;
 476             back_off bkoff;
 477
 478             node_type * t;
 479             while ( true ) {
 480                 t = guard.protect( m_pTail, []( node_type * p ) -> value_type * { return node_traits::to_value_ptr( p );});
 481
 482                 node_type * pNext = t->m_pNext.load(memory_model::memory_order_acquire);
 483                 if ( pNext != nullptr ) {
 484                     // Tail is misplaced, advance it
 485                     m_pTail.compare_exchange_weak( t, pNext, memory_model::memory_order_release, atomics::memory_order_relaxed );
 486                     m_Stat.onBadTail();
 487                     continue;
 488                 }
 489
 490                 node_type * tmp = nullptr;
 491                 if ( t->m_pNext.compare_exchange_strong( tmp, pNew, memory_model::memory_order_release, atomics::memory_order_relaxed ))
 492                     break;
 493
 494                 m_Stat.onEnqueueRace();
 495                 bkoff();
 496             }
 497             ++m_ItemCounter;
 498             m_Stat.onEnqueue();
 499
 500             if ( !m_pTail.compare_exchange_strong( t, pNew, memory_model::memory_order_release, atomics::memory_order_relaxed ))
 501                 m_Stat.onAdvanceTailFailed();
 502             return true;
 503         }
 504
 505         /// Dequeues a value from the queue
 506         /** @anchor cds_intrusive_MSQueue_dequeue
 507             If the queue is empty the function returns \p nullptr.
 508
 509             \par Warning
 510             The queue algorithm has following feature: when \p %dequeue() is called,
 511             the item returning is still queue's top, and previous top is disposed:
 512
 513             \code
 514             before dequeuing         Dequeue               after dequeuing
 515             +------------------+                           +------------------+
 516       Top ->|      Item 1      |  -> Dispose Item 1        |      Item 2      | <- Top
 517             +------------------+                           +------------------+
 518             |      Item 2      |  -> Return Item 2         |       ...        |
 519             +------------------+
 520             |       ...        |
 521             \endcode
 522
 523             \p %dequeue() function returns Item 2, that becomes new top of queue, and calls
 524             the disposer for Item 1, that was queue's top on function entry.
 525             Thus, you cannot manually delete item returned because it is still included in
 526             item sequence and it has valuable link field that must not be zeroed.
 527             The item should be deleted only in garbage collector retire cycle using the disposer.
 528         */
 529         value_type * dequeue()
 530         {
 531             dequeue_result res;
 532
 533             if ( do_dequeue( res )) {
 534                 dispose_result( res );
 535
 536                 return node_traits::to_value_ptr( *res.pNext );
 537             }
 538             return nullptr;
 539         }
 540
 541         /// Synonym for \ref cds_intrusive_MSQueue_enqueue "enqueue()" function
 542         bool push( value_type& val )
 543         {
 544             return enqueue( val );
 545         }
 546
 547         /// Synonym for \ref cds_intrusive_MSQueue_dequeue "dequeue()" function
 548         value_type * pop()
 549         {
 550             return dequeue();
 551         }
 552
 553         /// Checks if the queue is empty
 554         bool empty() const
 555         {
 556             typename gc::Guard guard;
 557             return guard.protect( m_pHead, []( node_type * p ) -> value_type * { return node_traits::to_value_ptr( p );})
 558                 ->m_pNext.load( memory_model::memory_order_relaxed ) == nullptr;
 559         }
 560
 561         /// Clear the queue
 562         /**
 563             The function repeatedly calls \p dequeue() until it returns \p nullptr.
 564             The disposer defined in template \p Traits is called for each item
 565             that can be safely disposed.
 566         */
 567         void clear()
 568         {
 569             while ( dequeue() );
 570         }
 571
 572         /// Returns queue's item count
 573         /**
 574             The value returned depends on \p msqueue::traits::item_counter. For \p atomicity::empty_item_counter,
 575             this function always returns 0.
 576
 577             @note Even if you use real item counter and it returns 0, this fact is not mean that the queue
 578             is empty. To check queue emptyness use \p empty() method.
 579         */
 580         size_t size() const
 581         {
 582             return m_ItemCounter.value();
 583         }
 584
 585         /// Returns reference to internal statistics
 586         stat const& statistics() const
 587         {
 588             return m_Stat;
 589         }
 590     };
 591
 592 }} // namespace cds::intrusive
 593
 594 #endif // #ifndef CDSLIB_INTRUSIVE_MSQUEUE_H