cds/intrusive/details/base.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDS_INTRUSIVE_DETAILS_BASE_H
   4 #define __CDS_INTRUSIVE_DETAILS_BASE_H
   5
   6 #include <cds/intrusive/details/node_traits.h>
   7 #include <cds/details/allocator.h>
   8 #include <cds/algo/backoff_strategy.h>
   9
  10 namespace cds {
  11
  12 /// Intrusive containers
  13 /**
  14     @ingroup cds_intrusive_containers
  15     The namespace cds::intrusive contains intrusive lock-free containers.
  16     The idea comes from \p boost::intrusive library, see http://boost.org/doc/ as a good introduction to intrusive approach.
  17     The intrusive containers of libcds library is developed as close to \p boost::intrusive
  18
  19     In terms of lock-free approach, the main advantage of intrusive containers is
  20     that no memory allocation is performed to maintain container items.
  21     However, additional requirements is imposed for types and values that can be stored in intrusive container.
  22     See the container documentation for details.
  23
  24     \anchor cds_intrusive_hook_tag
  25     \par Tags
  26     Many hooks and nodes for intrusive containers contain template argument \p Tag.
  27     This argument serves as a tag, so you can derive from more than one container's node and hence put an object in multiple intrusive containers
  28     at the same time. An incomplete type can serve as a tag. If you specify two hooks, you must specify a different tag for each one.
  29     Example:
  30     \code
  31     struct tag1;
  32     cds::intrusive::treiber_stack::node< cds::gc::HP, tag<tag1> >
  33     \endcode
  34     If no tag is specified the default \p cds::opt::none will be used.
  35
  36     \anchor cds_intrusive_item_creating
  37     \par Inserting items
  38     Many intrusive and non-intrusive (standard-like) containers in the library have the member functions
  39     that take an functor argument to initialize the inserted item after it has been successfully inserted,
  40     for example:
  41     \code
  42     template <typename Q, typename Func>
  43     bool insert( Q& key, Func f );
  44
  45     template <typename Q, typename Func>
  46     std::pair<bool, bool> ensure( Q& key, Func f );
  47     \endcode
  48     The first member function calls \p f functor iif an new item has been inserted. The functor takes two parameter: a reference to inserted item and
  49     \p key.
  50
  51     The second member function, \p ensure, allows to insert a new item to the container if \p key is not found, or to find the item with \p key and
  52     to perform some action with it. The \p f signature is:
  53     \code
  54     void f( bool bNew, item_type& item, Q& key );
  55     \endcode
  56     where \p bNew is a flag to indicate whether \p item is a new created node or not.
  57
  58     Such functions should be used with caution in multi-threaded environment
  59     since they can cause races. The library does not synchronize access
  60     to container's items, so many threads can access to one item simultaneously.
  61     For example, for \p insert member function the following race is possible:
  62     \code
  63         // Suppose, Foo is a complex structure with int key field
  64         SomeContainer<Foo> q;
  65
  66         Thread 1                                  Thread 2
  67
  68         q.insert( Foo(5),                         q.find( 5, []( Foo& item ) {
  69             []( Foo& item ){                         // access to item fields
  70                // complex initialization             ...
  71                item.f1 = ...;                     });
  72                ...
  73             });
  74     \endcode
  75     Execute sequence:
  76     \code
  77         Find 5 in the container.
  78         Key 5 is not found
  79         Create a new item                         Find key 5
  80             with calling Foo(5) ctor
  81         Insert the new item
  82                                                   The key 5 is found -
  83                                                      call the functor     (!)
  84         Perform complex
  85            initialization -
  86            call the functor
  87     \endcode
  88     (!): Thread 2 found the key and call its functor on incomplete initialized item.
  89     Simultaneous access to the item also is possible. In this case Thread 1 is
  90     initializing the item, thread 2 is reading (or writing) the item's fields.
  91     In any case, Thread 2 can read uninitialized or incomplete initialized fields.
  92
  93     \p ensure member function race. Suppose, thread 1 and thread 2 perform
  94     the
  95     following code:
  96     \code
  97         q.ensure( 5, []( bool bNew, Foo& item, int  arg )
  98            {
  99               // bNew: true if the new element has been created
 100               //       false otherwise
 101               if ( bNew ) {
 102                  // initialize item
 103                  item.f1=...;
 104                  //...
 105               }
 106               else {
 107                  // do some work
 108                  if ( !item.f1 )
 109                     item.f1 = ...;
 110                  else {
 111                    //...
 112                  }
 113                  //...
 114               }
 115            }
 116         );
 117     \endcode
 118     Execute sequence:
 119     \code
 120         Thread 1                                  Thread 2
 121         key 5 not found
 122         insert new item Foo(5)                    Find 5
 123                                                   Key 5 found
 124                                                   call the functor with
 125                                                      bNew = false        (!)
 126         call the functor with
 127            bNew = true
 128     \endcode
 129     (!): Thread 2 executes its functor on incomplete initialized item.
 130
 131     To protect your code from such races you can use some item-level synchronization,
 132     for example:
 133     \code
 134     struct Foo {
 135        spinlock lock;       // item-level lock
 136        bool initialized = false;    // initialization flag
 137        // other fields
 138        // ....
 139     };
 140
 141     q.ensure( 5, []( bool bNew, Foo& item, int  arg )
 142         {
 143             // Lock access to the item
 144             std::unique_lock( item.lock );
 145
 146             if ( !item.initialized ) {
 147                 // initialize item
 148                 item.f1=...;
 149                 //...
 150                 item.initialized = true; // mark the item as initialized
 151             }
 152             else {
 153                 // do some work
 154                 if ( !item.f1 )
 155                     item.f1 = ...;
 156                 else {
 157                     //...
 158                 }
 159                 //...
 160             }
 161         }
 162     );
 163     \endcode
 164     If the item-level synchronization is not suitable, you should not use any inserting member function
 165     with post-insert functor argument.
 166
 167     \anchor cds_intrusive_item_destroying
 168     \par Destroying items
 169
 170     It should be very careful when destroying an item removed from intrusive container.
 171     In other threads the references to popped item may exists some time after removing.
 172     To destroy the removed item in thread-safe manner you should call static function \p retire
 173     of garbage collector you use, for example:
 174     \code
 175     struct destroyer  {
 176         void operator ()( my_type * p )
 177         {
 178             delete p;
 179         }
 180     };
 181
 182     typedef cds::intrusive::TreiberStack< cds::gc::HP, my_type, cds::opt::disposer< destroyer > > stack;
 183     stack s;
 184
 185     // ....
 186
 187     my_type * p = s.pop();
 188
 189     if ( p ) {
 190         // It is wrong
 191         // delete p;
 192
 193         // It is correct
 194         cds::gc:HP::retire< destroyer >( p );
 195     }
 196     \endcode
 197     The situation becomes even more complicated when you want store items in different intrusive containers.
 198     In this case the best way is using reference counting:
 199     \code
 200     struct my_type {
 201         ...
 202         std::atomic<unsigned int> nRefCount;
 203
 204         my_type()
 205             : nRefCount(0)
 206         {}
 207     };
 208
 209     struct destroyer  {
 210         void operator ()( my_type * p )
 211         {
 212             if ( --p->nRefCount == 0 )
 213                 delete p    ;   // delete only after no reference pointing to p
 214         }
 215     };
 216
 217     typedef cds::intrusive::TreiberStack< cds::gc::HP, my_type, cds::opt::disposer< destroyer > > stack;
 218     typedef cds::intrusive::MSQueue< cds::gc::HP, my_type, cds::opt::disposer< destroyer > > queue;
 219     stack s;
 220     queue q;
 221
 222     my_type * v = new my_type();
 223
 224     v.nRefCount++   ; // increment counter before pushing the item to the stack
 225     s.push(v);
 226
 227     v.nRefCount++   ; // increment counter before pushing the item to the queue
 228     q.push(v);
 229
 230     // ....
 231
 232     my_type * ps = s.pop();
 233     if ( ps ) {
 234         // It is wrong
 235         // delete ps;
 236
 237         // It is correct
 238         cds::gc:HP::retire< destroyer >( ps );
 239     }
 240
 241     my_type * pq = q.pop();
 242     if ( pq ) {
 243         // It is wrong
 244         // delete pq;
 245
 246         // It is correct
 247         cds::gc:HP::retire< destroyer >( pq );
 248     }
 249     \endcode
 250     Violation of these rules may lead to a crash.
 251
 252     \par Intrusive containers and Hazard Pointer-like garbage collectors
 253
 254     If you develop your intrusive container based on <b>libcds</b> library framework, you should
 255     take in the account the following.
 256     The main idea of garbage collectors (GC) based on Hazard Pointer schema is protecting a shared pointer
 257     by publishing it as a "hazard" one i.e. as a pointer that is changing at the current time and cannot be
 258     deleted at this moment. In intrusive container paradigm, the pointer to the node of the container
 259     and the pointer to the item stored in the container are not equal in the general case.
 260     However, any pointer to the node should be castable to the appropriate pointer to the container's item.
 261     In general, any item can be placed to some different intrusive containers simultaneously,
 262     and each of those container holds a unique pointer to its node that refers to the same item.
 263     When we protect a pointer, we want to protect an <b>item</b> pointer that is the invariant
 264     for any container stored that item. In your intrusive container, instead of protecting by GC's guard a pointer to an node
 265     you should convert it to the pointer to the item and then protect resulting item pointer.
 266     Otherwise an unpredictable result may occur.
 267 */
 268 namespace intrusive {
 269
 270     /// @defgroup cds_intrusive_containers Intrusive containers
 271     /** @defgroup cds_intrusive_helper Helper structs for intrusive containers
 272         @ingroup cds_intrusive_containers
 273     */
 274     /** @defgroup cds_intrusive_stack Stack
 275         @ingroup cds_intrusive_containers
 276     */
 277     /** @defgroup cds_intrusive_queue Queue
 278         @ingroup cds_intrusive_containers
 279     */
 280     /** @defgroup cds_intrusive_priority_queue Priority queue
 281         @ingroup cds_intrusive_containers
 282     */
 283     /** @defgroup cds_intrusive_deque Deque
 284         @ingroup cds_intrusive_containers
 285     */
 286     /** @defgroup cds_intrusive_map Set
 287         @ingroup cds_intrusive_containers
 288     */
 289     /** @defgroup cds_intrusive_tree Tree
 290         @ingroup cds_intrusive_containers
 291     */
 292     /** @defgroup cds_intrusive_list List
 293         @ingroup cds_intrusive_containers
 294     */
 295
 296 }} // namespace cds::intrusuve
 297
 298 #endif  // #ifndef __CDS_INTRUSIVE_DETAILS_BASE_H