cds/intrusive/moir_queue.h

   1 /*
   2     This file is a part of libcds - Concurrent Data Structures library
   3
   4     (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
   5
   6     Source code repo: http://github.com/khizmax/libcds/
   7     Download: http://sourceforge.net/projects/libcds/files/
   8
   9     Redistribution and use in source and binary forms, with or without
  10     modification, are permitted provided that the following conditions are met:
  11
  12     * Redistributions of source code must retain the above copyright notice, this
  13       list of conditions and the following disclaimer.
  14
  15     * Redistributions in binary form must reproduce the above copyright notice,
  16       this list of conditions and the following disclaimer in the documentation
  17       and/or other materials provided with the distribution.
  18
  19     THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  20     AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  21     IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  22     DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
  23     FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  24     DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  25     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  26     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  27     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  28     OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29 */
  30
  31 #ifndef CDSLIB_INTRUSIVE_MOIR_QUEUE_H
  32 #define CDSLIB_INTRUSIVE_MOIR_QUEUE_H
  33
  34 #include <cds/intrusive/msqueue.h>
  35
  36 namespace cds { namespace intrusive {
  37
  38     /// A variation of Michael & Scott's lock-free queue (intrusive variant)
  39     /** @ingroup cds_intrusive_queue
  40         This is slightly optimized Michael & Scott's queue algorithm that overloads \ref dequeue function.
  41
  42         Source:
  43             - [2000] Simon Doherty, Lindsay Groves, Victor Luchangco, Mark Moir
  44                 "Formal Verification of a practical lock-free queue algorithm"
  45
  46         Cite from this work about difference from Michael & Scott algo:
  47         "Our algorithm differs from Michael and Scott's [MS98] in that we test whether \p Tail points to the header
  48         node only <b>after</b> \p Head has been updated, so a dequeuing process reads \p Tail only once. The dequeue in
  49         [MS98] performs this test before checking whether the next pointer in the dummy node is null, which
  50         means that it reads \p Tail every time a dequeuing process loops. Under high load, when operations retry
  51         frequently, our modification will reduce the number of accesses to global memory. This modification, however,
  52         introduces the possibility of \p Head and \p Tail 'crossing'."
  53
  54         Explanation of template arguments see \p intrusive::MSQueue.
  55
  56         \par Examples
  57         \code
  58         #include <cds/intrusive/moir_queue.h>
  59         #include <cds/gc/hp.h>
  60
  61         namespace ci = cds::inrtusive;
  62         typedef cds::gc::HP hp_gc;
  63
  64         // MoirQueue with Hazard Pointer garbage collector, base hook + item disposer:
  65         struct Foo: public ci::msqueue::node< hp_gc >
  66         {
  67             // Your data
  68             ...
  69         };
  70
  71         // Disposer for Foo struct just deletes the object passed in
  72         struct fooDisposer {
  73             void operator()( Foo * p )
  74             {
  75                 delete p;
  76             }
  77         };
  78
  79         typedef ci::MoirQueue<
  80             hp_gc
  81             ,Foo
  82             typename ci::msqueue::make_traits<
  83                 ,ci::opt::hook<
  84                     ci::msqueue::base_hook< ci::opt::gc<hp_gc> >
  85                 >
  86                 ,ci::opt::disposer< fooDisposer >
  87             >::type
  88         > fooQueue;
  89
  90         // MoirQueue with Hazard Pointer garbage collector,
  91         // member hook + item disposer + item counter,
  92         // without padding of internal queue data:
  93         struct Bar
  94         {
  95             // Your data
  96             ...
  97             ci::msqueue::node< hp_gc > hMember;
  98         };
  99
 100         struct barQueueTraits: public ci::msqueue::traits
 101         {
 102             typedef ci::msqueue::member_hook< offsetof(Bar, hMember), ,ci::opt::gc<hp_gc> > hook;
 103             typedef fooDisposer disposer;
 104             typedef cds::atomicity::item_counter item_counter;
 105             enum { padding = cds::opt::no_special_padding };
 106         };
 107         typedef ci::MoirQueue< hp_gc, Bar, barQueueTraits > barQueue;
 108         \endcode
 109     */
 110     template <typename GC, typename T, typename Traits = cds::intrusive::msqueue::traits>
 111     class MoirQueue: public MSQueue< GC, T, Traits >
 112     {
 113         //@cond
 114         typedef MSQueue< GC, T, Traits > base_class;
 115         typedef typename base_class::node_type node_type;
 116         //@endcond
 117
 118     public:
 119         //@cond
 120         typedef typename base_class::value_type value_type;
 121         typedef typename base_class::back_off   back_off;
 122         typedef typename base_class::gc         gc;
 123         typedef typename base_class::node_traits node_traits;
 124         typedef typename base_class::memory_model   memory_model;
 125         //@endcond
 126
 127         /// Rebind template arguments
 128         template < typename GC2, typename T2, typename Traits2 >
 129         struct rebind {
 130             typedef MoirQueue< GC2, T2, Traits2> other   ;   ///< Rebinding result
 131         };
 132
 133     protected:
 134         //@cond
 135         typedef typename base_class::dequeue_result dequeue_result;
 136
 137         bool do_dequeue( dequeue_result& res )
 138         {
 139             back_off bkoff;
 140
 141             node_type * pNext;
 142             node_type * h;
 143             while ( true ) {
 144                 h = res.guards.protect( 0, base_class::m_pHead, []( node_type * p ) -> value_type * { return node_traits::to_value_ptr( p );});
 145                 pNext = res.guards.protect( 1, h->m_pNext, []( node_type * p ) -> value_type * { return node_traits::to_value_ptr( p );});
 146
 147                 if ( pNext == nullptr ) {
 148                     base_class::m_Stat.onEmptyDequeue();
 149                     return false;    // queue is empty
 150                 }
 151
 152                 if ( base_class::m_pHead.compare_exchange_strong( h, pNext, memory_model::memory_order_release, atomics::memory_order_relaxed )) {
 153                     node_type * t = base_class::m_pTail.load(memory_model::memory_order_acquire);
 154                     if ( h == t )
 155                         base_class::m_pTail.compare_exchange_strong( t, pNext, memory_model::memory_order_release, atomics::memory_order_relaxed );
 156                     break;
 157                 }
 158
 159                 base_class::m_Stat.onDequeueRace();
 160                 bkoff();
 161             }
 162
 163             --base_class::m_ItemCounter;
 164             base_class::m_Stat.onDequeue();
 165
 166             res.pHead = h;
 167             res.pNext = pNext;
 168             return true;
 169         }
 170         //@endcond
 171
 172     public:
 173         /// Dequeues a value from the queue
 174         /** @anchor cds_intrusive_MoirQueue_dequeue
 175             See warning about item disposing in \p MSQueue::dequeue.
 176         */
 177         value_type * dequeue()
 178         {
 179             dequeue_result res;
 180             if ( do_dequeue( res )) {
 181                 base_class::dispose_result( res );
 182                 return node_traits::to_value_ptr( *res.pNext );
 183             }
 184             return nullptr;
 185         }
 186
 187         /// Synonym for \ref cds_intrusive_MoirQueue_dequeue "dequeue" function
 188         value_type * pop()
 189         {
 190             return dequeue();
 191         }
 192     };
 193
 194 }} // namespace cds::intrusive
 195
 196 #endif // #ifndef CDSLIB_INTRUSIVE_MOIR_QUEUE_H