cds/algo/atomic.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-2017
   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_CXX11_ATOMIC_H
  32 #define CDSLIB_CXX11_ATOMIC_H
  33
  34 #include <cds/details/defs.h>
  35 #include <cds/user_setup/cache_line.h>
  36
  37 namespace cds {
  38
  39 /// C++11 Atomic library support
  40 /** @anchor cds_cxx11_atomic
  41     \p libcds can use the following implementations of the atomics:
  42     - STL \p &lt;atomic&gt;. This is used by default
  43     - \p boost.atomic for boost 1.54 and above. To use it you should define \p CDS_USE_BOOST_ATOMIC for
  44       your compiler invocation, for example, for gcc specify \p -DCDS_USE_BOOST_ATOMIC
  45       in command line
  46     - \p libcds implementation of atomic operation according to C++11 standard as
  47       specified in <a href="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2011/n3242.pdf">N3242, p.29</a>.
  48       \p libcds implementation is not the full standard compliant, it provides only C++ part of standard,
  49       for example, \p libcds has no static initialization of the atomic variables and some other C features.
  50       However, that imlementation is enough for the library purposes. Supported architecture: x86, amd64,
  51       ia64 (Itanium) 64bit, 64bit Sparc. To use \p libcds atomic you should define \p CDS_USE_LIBCDS_ATOMIC
  52       in the compiler command line (\p -DCDS_USE_LIBCDS_ATOMIC for gcc/clang).
  53
  54       @note For Clang compiler \p libcds doesn't use native \p libc++ \p &lt;atomic&gt; due some problems.
  55       Instead, \p libcds atomic is used by default, or you can try to use \p boost.atomic.
  56
  57       The library defines \p atomics alias for atomic namespace:
  58       - <tt>namespace atomics = std</tt> for STL
  59       - <tt>namespace atomics = boost</tt> for \p boost.atomic
  60       - <tt>namespace atomics = cds::cxx11_atomic</tt> for library-provided atomic implementation
  61 */
  62 namespace cxx11_atomic {
  63 }} // namespace cds::cxx11_atomic
  64
  65 //@cond
  66 #if defined(CDS_USE_BOOST_ATOMIC)
  67     // boost atomic
  68 #   include <boost/version.hpp>
  69 #   if BOOST_VERSION >= 105400
  70 #       include <boost/atomic.hpp>
  71         namespace atomics = boost;
  72 #       define CDS_CXX11_ATOMIC_BEGIN_NAMESPACE namespace boost {
  73 #       define CDS_CXX11_ATOMIC_END_NAMESPACE }
  74 #   else
  75 #       error "Boost version 1.54 or above is needed for boost.atomic"
  76 #   endif
  77 #elif defined(CDS_USE_LIBCDS_ATOMIC)
  78     // libcds atomic
  79 #   include <cds/compiler/cxx11_atomic.h>
  80     namespace atomics = cds::cxx11_atomic;
  81 #   define CDS_CXX11_ATOMIC_BEGIN_NAMESPACE namespace cds { namespace cxx11_atomic {
  82 #   define CDS_CXX11_ATOMIC_END_NAMESPACE }}
  83 #else
  84     // Compiler provided C++11 atomic
  85 #   include <atomic>
  86     namespace atomics = std;
  87 #   define CDS_CXX11_ATOMIC_BEGIN_NAMESPACE namespace std {
  88 #   define CDS_CXX11_ATOMIC_END_NAMESPACE }
  89 #endif
  90 //@endcond
  91
  92 namespace cds {
  93
  94     /// Atomic primitives
  95     /**
  96         This namespace contains useful primitives derived from <tt>std::atomic</tt>.
  97     */
  98     namespace atomicity {
  99
 100         /// Atomic event counter.
 101         /**
 102             This class is based on <tt>std::atomic_size_t</tt>.
 103             It uses relaxed memory ordering \p memory_order_relaxed and may be used as a statistic counter.
 104         */
 105         class event_counter
 106         {
 107             //@cond
 108             atomics::atomic_size_t   m_counter;
 109             //@endcond
 110
 111         public:
 112             typedef size_t      value_type  ;       ///< Type of counter
 113
 114         public:
 115             // Initializes event counter with zero
 116             event_counter() CDS_NOEXCEPT
 117                 : m_counter(size_t(0))
 118             {}
 119
 120             /// Assign operator
 121             /**
 122                 Returns \p n.
 123             */
 124             value_type operator =(
 125                 value_type n    ///< new value of the counter
 126             ) CDS_NOEXCEPT
 127             {
 128                 m_counter.exchange( n, atomics::memory_order_relaxed );
 129                 return n;
 130             }
 131
 132             /// Addition
 133             /**
 134                 Returns new value of the atomic counter.
 135             */
 136             size_t operator +=(
 137                 size_t n    ///< addendum
 138             ) CDS_NOEXCEPT
 139             {
 140                 return m_counter.fetch_add( n, atomics::memory_order_relaxed ) + n;
 141             }
 142
 143             /// Substraction
 144             /**
 145                 Returns new value of the atomic counter.
 146             */
 147             size_t operator -=(
 148                 size_t n    ///< subtrahend
 149             ) CDS_NOEXCEPT
 150             {
 151                 return m_counter.fetch_sub( n, atomics::memory_order_relaxed ) - n;
 152             }
 153
 154             /// Get current value of the counter
 155             operator size_t () const CDS_NOEXCEPT
 156             {
 157                 return m_counter.load( atomics::memory_order_relaxed );
 158             }
 159
 160             /// Preincrement
 161             size_t operator ++() CDS_NOEXCEPT
 162             {
 163                 return m_counter.fetch_add( 1, atomics::memory_order_relaxed ) + 1;
 164             }
 165             /// Postincrement
 166             size_t operator ++(int) CDS_NOEXCEPT
 167             {
 168                 return m_counter.fetch_add( 1, atomics::memory_order_relaxed );
 169             }
 170
 171             /// Predecrement
 172             size_t operator --() CDS_NOEXCEPT
 173             {
 174                 return m_counter.fetch_sub( 1, atomics::memory_order_relaxed ) - 1;
 175             }
 176             /// Postdecrement
 177             size_t operator --(int) CDS_NOEXCEPT
 178             {
 179                 return m_counter.fetch_sub( 1, atomics::memory_order_relaxed );
 180             }
 181
 182             /// Get current value of the counter
 183             size_t get() const CDS_NOEXCEPT
 184             {
 185                 return m_counter.load( atomics::memory_order_relaxed );
 186             }
 187
 188             /// Resets the counter to 0
 189             void reset() CDS_NOEXCEPT
 190             {
 191                 m_counter.store( 0, atomics::memory_order_release );
 192             }
 193         };
 194
 195         /// Atomic item counter
 196         /**
 197             This class is simplified interface around \p std::atomic_size_t.
 198             The class supports getting current value of the counter and increment/decrement its value.
 199
 200             See also: improved version that eliminates false sharing - \p cache_friendly_item_counter.
 201         */
 202         class item_counter
 203         {
 204         public:
 205             typedef atomics::atomic_size_t   atomic_type;   ///< atomic type used
 206             typedef size_t counter_type;                    ///< Integral item counter type (size_t)
 207
 208         private:
 209             //@cond
 210             atomic_type     m_Counter;   ///< Atomic item counter
 211             //@endcond
 212
 213         public:
 214             /// Default ctor initializes the counter to zero.
 215             item_counter()
 216                 : m_Counter(counter_type(0))
 217             {}
 218
 219             /// Returns current value of the counter
 220             counter_type value(atomics::memory_order order = atomics::memory_order_relaxed) const
 221             {
 222                 return m_Counter.load( order );
 223             }
 224
 225             /// Same as \ref value() with relaxed memory ordering
 226             operator counter_type() const
 227             {
 228                 return value();
 229             }
 230
 231             /// Returns underlying atomic interface
 232             atomic_type& getAtomic()
 233             {
 234                 return m_Counter;
 235             }
 236
 237             /// Returns underlying atomic interface (const)
 238             const atomic_type& getAtomic() const
 239             {
 240                 return m_Counter;
 241             }
 242
 243             /// Increments the counter. Semantics: postincrement
 244             counter_type inc(atomics::memory_order order = atomics::memory_order_relaxed )
 245             {
 246                 return m_Counter.fetch_add( 1, order );
 247             }
 248
 249             /// Increments the counter. Semantics: postincrement
 250             counter_type inc( counter_type count, atomics::memory_order order = atomics::memory_order_relaxed )
 251             {
 252                 return m_Counter.fetch_add( count, order );
 253             }
 254
 255             /// Decrements the counter. Semantics: postdecrement
 256             counter_type dec(atomics::memory_order order = atomics::memory_order_relaxed)
 257             {
 258                 return m_Counter.fetch_sub( 1, order );
 259             }
 260
 261             /// Decrements the counter. Semantics: postdecrement
 262             counter_type dec( counter_type count, atomics::memory_order order = atomics::memory_order_relaxed )
 263             {
 264                 return m_Counter.fetch_sub( count, order );
 265             }
 266
 267             /// Preincrement
 268             counter_type operator ++()
 269             {
 270                 return inc() + 1;
 271             }
 272             /// Postincrement
 273             counter_type operator ++(int)
 274             {
 275                 return inc();
 276             }
 277
 278             /// Predecrement
 279             counter_type operator --()
 280             {
 281                 return dec() - 1;
 282             }
 283             /// Postdecrement
 284             counter_type operator --(int)
 285             {
 286                 return dec();
 287             }
 288
 289             /// Increment by \p count
 290             counter_type operator +=( counter_type count )
 291             {
 292                 return inc( count ) + count;
 293             }
 294
 295             /// Decrement by \p count
 296             counter_type operator -=( counter_type count )
 297             {
 298                 return dec( count ) - count;
 299             }
 300
 301             /// Resets count to 0
 302             void reset(atomics::memory_order order = atomics::memory_order_relaxed)
 303             {
 304                 m_Counter.store( 0, order );
 305             }
 306         };
 307
 308 #if CDS_COMPILER == CDS_COMPILER_CLANG
 309     // CLang unhappy: pad1_ and pad2_ - unused private field warning
 310 #   pragma GCC diagnostic push
 311 #   pragma GCC diagnostic ignored "-Wunused-private-field"
 312 #endif
 313         /// Atomic cache-friendly item counter
 314         /**
 315             Atomic item counter with cache-line padding to avoid false sharing.
 316             Adding cache-line padding before and after atomic counter eliminates the contention
 317             in read path of many containers and can notably improve search operations in sets/maps.
 318         */
 319         class cache_friendly_item_counter
 320         {
 321         public:
 322             typedef atomics::atomic_size_t   atomic_type;   ///< atomic type used
 323             typedef size_t counter_type;                    ///< Integral item counter type (size_t)
 324
 325         private:
 326             //@cond
 327             char            pad1_[cds::c_nCacheLineSize];
 328             atomic_type     m_Counter;   ///< Atomic item counter
 329             char            pad2_[cds::c_nCacheLineSize - sizeof( atomic_type )];
 330             //@endcond
 331
 332         public:
 333             /// Default ctor initializes the counter to zero.
 334             cache_friendly_item_counter()
 335                 : m_Counter(counter_type(0))
 336             {}
 337
 338             /// Returns current value of the counter
 339             counter_type value(atomics::memory_order order = atomics::memory_order_relaxed) const
 340             {
 341                 return m_Counter.load( order );
 342             }
 343
 344             /// Same as \ref value() with relaxed memory ordering
 345             operator counter_type() const
 346             {
 347                 return value();
 348             }
 349
 350             /// Returns underlying atomic interface
 351             atomic_type& getAtomic()
 352             {
 353                 return m_Counter;
 354             }
 355
 356             /// Returns underlying atomic interface (const)
 357             const atomic_type& getAtomic() const
 358             {
 359                 return m_Counter;
 360             }
 361
 362             /// Increments the counter. Semantics: postincrement
 363             counter_type inc(atomics::memory_order order = atomics::memory_order_relaxed )
 364             {
 365                 return m_Counter.fetch_add( 1, order );
 366             }
 367
 368             /// Increments the counter. Semantics: postincrement
 369             counter_type inc( counter_type count, atomics::memory_order order = atomics::memory_order_relaxed )
 370             {
 371                 return m_Counter.fetch_add( count, order );
 372             }
 373
 374             /// Decrements the counter. Semantics: postdecrement
 375             counter_type dec(atomics::memory_order order = atomics::memory_order_relaxed)
 376             {
 377                 return m_Counter.fetch_sub( 1, order );
 378             }
 379
 380             /// Decrements the counter. Semantics: postdecrement
 381             counter_type dec( counter_type count, atomics::memory_order order = atomics::memory_order_relaxed )
 382             {
 383                 return m_Counter.fetch_sub( count, order );
 384             }
 385
 386             /// Preincrement
 387             counter_type operator ++()
 388             {
 389                 return inc() + 1;
 390             }
 391             /// Postincrement
 392             counter_type operator ++(int)
 393             {
 394                 return inc();
 395             }
 396
 397             /// Predecrement
 398             counter_type operator --()
 399             {
 400                 return dec() - 1;
 401             }
 402             /// Postdecrement
 403             counter_type operator --(int)
 404             {
 405                 return dec();
 406             }
 407
 408             /// Increment by \p count
 409             counter_type operator +=( counter_type count )
 410             {
 411                 return inc( count ) + count;
 412             }
 413
 414             /// Decrement by \p count
 415             counter_type operator -=( counter_type count )
 416             {
 417                 return dec( count ) - count;
 418             }
 419
 420             /// Resets count to 0
 421             void reset(atomics::memory_order order = atomics::memory_order_relaxed)
 422             {
 423                 m_Counter.store( 0, order );
 424             }
 425         };
 426 #if CDS_COMPILER == CDS_COMPILER_CLANG
 427 #   pragma GCC diagnostic pop
 428 #endif
 429
 430         /// Empty item counter
 431         /**
 432             This class may be used instead of \ref item_counter when you do not need full \ref item_counter interface.
 433             All methods of the class is empty and returns 0.
 434
 435             The object of this class should not be used in data structure that behavior significantly depends on item counting
 436             (for example, in many hash map implementation).
 437         */
 438         class empty_item_counter {
 439         public:
 440             typedef size_t counter_type    ;  ///< Counter type
 441         public:
 442             /// Returns 0
 443             static counter_type value(atomics::memory_order /*order*/ = atomics::memory_order_relaxed)
 444             {
 445                 return 0;
 446             }
 447
 448             /// Same as \ref value(), always returns 0.
 449             operator counter_type() const
 450             {
 451                 return value();
 452             }
 453
 454             /// Dummy increment. Always returns 0
 455             static counter_type inc(atomics::memory_order /*order*/ = atomics::memory_order_relaxed)
 456             {
 457                 return 0;
 458             }
 459
 460             /// Dummy increment. Always returns 0
 461             static counter_type inc( counter_type /*count*/, atomics::memory_order /*order*/ = atomics::memory_order_relaxed )
 462             {
 463                 return 0;
 464             }
 465
 466             /// Dummy increment. Always returns 0
 467             static counter_type dec(atomics::memory_order /*order*/ = atomics::memory_order_relaxed)
 468             {
 469                 return 0;
 470             }
 471
 472             /// Dummy increment. Always returns 0
 473             static counter_type dec( counter_type /*count*/, atomics::memory_order /*order*/ = atomics::memory_order_relaxed )
 474             {
 475                 return 0;
 476             }
 477
 478             /// Dummy pre-increment. Always returns 0
 479             counter_type operator ++() const
 480             {
 481                 return 0;
 482             }
 483             /// Dummy post-increment. Always returns 0
 484             counter_type operator ++(int) const
 485             {
 486                 return 0;
 487             }
 488
 489             /// Dummy pre-decrement. Always returns 0
 490             counter_type operator --() const
 491             {
 492                 return 0;
 493             }
 494             /// Dummy post-decrement. Always returns 0
 495             counter_type operator --(int) const
 496             {
 497                 return 0;
 498             }
 499
 500             /// Dummy increment by \p count, always returns 0
 501             counter_type operator +=( counter_type count )
 502             {
 503                 CDS_UNUSED( count );
 504                 return 0;
 505             }
 506
 507             /// Dummy decrement by \p count, always returns 0
 508             counter_type operator -=( counter_type count )
 509             {
 510                 CDS_UNUSED( count );
 511                 return 0;
 512             }
 513
 514             /// Dummy function
 515             static void reset(atomics::memory_order /*order*/ = atomics::memory_order_relaxed)
 516             {}
 517         };
 518     }   // namespace atomicity
 519 }   // namespace cds
 520
 521 #endif // #ifndef CDSLIB_CXX11_ATOMIC_H