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 alûo 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         /// Atomic cache-friendly item counter
 309         /**
 310             Atomic item counter with cache-line padding to avoid false sharing.
 311             Adding cache-line padding before and after atomic counter eliminates the contention
 312             in read path of many containers and can notably improve search operations in sets/maps.
 313         */
 314         class cache_friendly_item_counter
 315         {
 316         public:
 317             typedef atomics::atomic_size_t   atomic_type;   ///< atomic type used
 318             typedef size_t counter_type;                    ///< Integral item counter type (size_t)
 319
 320         private:
 321             //@cond
 322             char            pad1_[cds::c_nCacheLineSize];
 323             atomic_type     m_Counter;   ///< Atomic item counter
 324             char            pad2_[cds::c_nCacheLineSize - sizeof( atomic_type )];
 325             //@endcond
 326
 327         public:
 328             /// Default ctor initializes the counter to zero.
 329             cache_friendly_item_counter()
 330                 : m_Counter(counter_type(0))
 331             {}
 332
 333             /// Returns current value of the counter
 334             counter_type value(atomics::memory_order order = atomics::memory_order_relaxed) const
 335             {
 336                 return m_Counter.load( order );
 337             }
 338
 339             /// Same as \ref value() with relaxed memory ordering
 340             operator counter_type() const
 341             {
 342                 return value();
 343             }
 344
 345             /// Returns underlying atomic interface
 346             atomic_type& getAtomic()
 347             {
 348                 return m_Counter;
 349             }
 350
 351             /// Returns underlying atomic interface (const)
 352             const atomic_type& getAtomic() const
 353             {
 354                 return m_Counter;
 355             }
 356
 357             /// Increments the counter. Semantics: postincrement
 358             counter_type inc(atomics::memory_order order = atomics::memory_order_relaxed )
 359             {
 360                 return m_Counter.fetch_add( 1, order );
 361             }
 362
 363             /// Increments the counter. Semantics: postincrement
 364             counter_type inc( counter_type count, atomics::memory_order order = atomics::memory_order_relaxed )
 365             {
 366                 return m_Counter.fetch_add( count, order );
 367             }
 368
 369             /// Decrements the counter. Semantics: postdecrement
 370             counter_type dec(atomics::memory_order order = atomics::memory_order_relaxed)
 371             {
 372                 return m_Counter.fetch_sub( 1, order );
 373             }
 374
 375             /// Decrements the counter. Semantics: postdecrement
 376             counter_type dec( counter_type count, atomics::memory_order order = atomics::memory_order_relaxed )
 377             {
 378                 return m_Counter.fetch_sub( count, order );
 379             }
 380
 381             /// Preincrement
 382             counter_type operator ++()
 383             {
 384                 return inc() + 1;
 385             }
 386             /// Postincrement
 387             counter_type operator ++(int)
 388             {
 389                 return inc();
 390             }
 391
 392             /// Predecrement
 393             counter_type operator --()
 394             {
 395                 return dec() - 1;
 396             }
 397             /// Postdecrement
 398             counter_type operator --(int)
 399             {
 400                 return dec();
 401             }
 402
 403             /// Increment by \p count
 404             counter_type operator +=( counter_type count )
 405             {
 406                 return inc( count ) + count;
 407             }
 408
 409             /// Decrement by \p count
 410             counter_type operator -=( counter_type count )
 411             {
 412                 return dec( count ) - count;
 413             }
 414
 415             /// Resets count to 0
 416             void reset(atomics::memory_order order = atomics::memory_order_relaxed)
 417             {
 418                 m_Counter.store( 0, order );
 419             }
 420         };
 421
 422
 423         /// Empty item counter
 424         /**
 425             This class may be used instead of \ref item_counter when you do not need full \ref item_counter interface.
 426             All methods of the class is empty and returns 0.
 427
 428             The object of this class should not be used in data structure that behavior significantly depends on item counting
 429             (for example, in many hash map implementation).
 430         */
 431         class empty_item_counter {
 432         public:
 433             typedef size_t counter_type    ;  ///< Counter type
 434         public:
 435             /// Returns 0
 436             static counter_type value(atomics::memory_order /*order*/ = atomics::memory_order_relaxed)
 437             {
 438                 return 0;
 439             }
 440
 441             /// Same as \ref value(), always returns 0.
 442             operator counter_type() const
 443             {
 444                 return value();
 445             }
 446
 447             /// Dummy increment. Always returns 0
 448             static counter_type inc(atomics::memory_order /*order*/ = atomics::memory_order_relaxed)
 449             {
 450                 return 0;
 451             }
 452
 453             /// Dummy increment. Always returns 0
 454             static counter_type inc( counter_type /*count*/, atomics::memory_order /*order*/ = atomics::memory_order_relaxed )
 455             {
 456                 return 0;
 457             }
 458
 459             /// Dummy increment. Always returns 0
 460             static counter_type dec(atomics::memory_order /*order*/ = atomics::memory_order_relaxed)
 461             {
 462                 return 0;
 463             }
 464
 465             /// Dummy increment. Always returns 0
 466             static counter_type dec( counter_type /*count*/, atomics::memory_order /*order*/ = atomics::memory_order_relaxed )
 467             {
 468                 return 0;
 469             }
 470
 471             /// Dummy pre-increment. Always returns 0
 472             counter_type operator ++() const
 473             {
 474                 return 0;
 475             }
 476             /// Dummy post-increment. Always returns 0
 477             counter_type operator ++(int) const
 478             {
 479                 return 0;
 480             }
 481
 482             /// Dummy pre-decrement. Always returns 0
 483             counter_type operator --() const
 484             {
 485                 return 0;
 486             }
 487             /// Dummy post-decrement. Always returns 0
 488             counter_type operator --(int) const
 489             {
 490                 return 0;
 491             }
 492
 493             /// Dummy increment by \p count, always returns 0
 494             counter_type operator +=( counter_type count )
 495             {
 496                 CDS_UNUSED( count );
 497                 return 0;
 498             }
 499
 500             /// Dummy decrement 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 function
 508             static void reset(atomics::memory_order /*order*/ = atomics::memory_order_relaxed)
 509             {}
 510         };
 511     }   // namespace atomicity
 512 }   // namespace cds
 513
 514 #endif // #ifndef CDSLIB_CXX11_ATOMIC_H