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