Line data    Source code

       1            0 : // Distributed under the MIT License.
       2              : // See LICENSE.txt for details.
       3              : 
       4              : #pragma once
       5              : 
       6              : #include <atomic>
       7              : #include <limits>
       8              : #include <new>  // for hardware_destructive_interference_size
       9              : 
      10              : namespace Parallel {
      11              : /*!
      12              :  * \brief A two-state spinlock that allows multiple readers of a shared resource
      13              :  * to acquire the lock simultaneously.
      14              :  *
      15              :  * A spinlock (i.e. a non-yielding lock) that can be used to guard a resource
      16              :  * where multiple threads can safely perform some types of operations
      17              :  * (e.g. reader entries from a container), while only one thread can safely
      18              :  * perform other types of operations (e.g. modifying the container).
      19              :  *
      20              :  * ### Implementation
      21              :  * We lock by using a `std::atomic<std::int64_t>` (a signed integer). The lock
      22              :  * is not locked if the integer is `0`. It is read-locked if it is positive
      23              :  * and write-locked if it is negative. To read-lock we first check that the
      24              :  * integer is non-negative and then `fetch_add(1, std::memory_order_acq_rel)`,
      25              :  * then check that the number _before_ the increment is non-negative. The
      26              :  * reason for the second check is that between checking that the lock is not
      27              :  * write-locked and the `fetch_add()` operation, it could be write-locked by
      28              :  * another thread. To write-lock, we check that the integer is `0` and if so
      29              :  * we set it to `std::numeric_limits<std::int64_t>::lowest()` (i.e. `-2^{63}`).
      30              :  * We achieve this by using a `compare_exchange_strong()` with failure memory
      31              :  * order `relaxed` and success memory order `acq_rel`. This guarantees that
      32              :  * different threads synchronize using the lock.
      33              :  *
      34              :  * A thread read-unlocks the lock using a
      35              :  * `fetch_sub(1, std::memory_order_acq_rel)` operation.
      36              :  *
      37              :  * A thread write-unlocks the lock using a `store(0, std::memory_order_release)`
      38              :  * operation.
      39              :  */
      40            1 : class MultiReaderSpinlock {
      41              :  public:
      42            0 :   MultiReaderSpinlock() = default;
      43            0 :   MultiReaderSpinlock(const MultiReaderSpinlock&) = delete;
      44            0 :   MultiReaderSpinlock& operator=(const MultiReaderSpinlock&) = delete;
      45            0 :   MultiReaderSpinlock(MultiReaderSpinlock&&) = delete;
      46            0 :   MultiReaderSpinlock& operator=(MultiReaderSpinlock&&) = delete;
      47            0 :   ~MultiReaderSpinlock() = default;
      48              : 
      49              :   /// \brief Acquire the lock in a reader state.
      50              :   ///
      51              :   /// \note Multiple threads can acquire a reader state simultaneously.
      52            1 :   void read_lock() noexcept {
      53              :     for (;;) {
      54              :       while (lock_.load(std::memory_order_relaxed) < 0) {
      55              :       }
      56              : 
      57              :       if (lock_.fetch_add(1, std::memory_order_acquire) > -1) {
      58              :         return;
      59              :       }
      60              :     }
      61              :   }
      62              : 
      63              :   /// \brief Release the lock from a reader state.
      64              :   ///
      65              :   /// \note Since multiple threads can simultaneously acquire a reader state,
      66              :   /// unlock from a single reader does not guarantee a writer can acquire the
      67              :   /// lock in a write state.
      68            1 :   void read_unlock() noexcept { lock_.fetch_sub(1, std::memory_order_release); }
      69              : 
      70              :   /// \brief Acquire the lock in a writer state.
      71              :   ///
      72              :   /// Once acquired, no other thread can acquire the lock in either a read or
      73              :   /// a write state until this thread unlocks it.
      74            1 :   void write_lock() noexcept {
      75              :     for (;;) {
      76              :       std::int64_t current_value{0};
      77              :       if (lock_.compare_exchange_strong(
      78              :               current_value, std::numeric_limits<std::int64_t>::lowest(),
      79              :               std::memory_order_acq_rel, std::memory_order_relaxed)) {
      80              :         return;
      81              :       }
      82              : 
      83              :       while (lock_.load(std::memory_order_relaxed) != 0) {
      84              :       }
      85              :     }
      86              :   }
      87              : 
      88              :   /// \brief Release the lock from a reader state.
      89            1 :   void write_unlock() noexcept { lock_.store(0, std::memory_order_release); }
      90              : 
      91              :  private:
      92              : #ifdef __cpp_lib_hardware_interference_size
      93              :   static constexpr size_t cache_line_size_ =
      94              :       std::hardware_destructive_interference_size;
      95              : #else
      96            0 :   static constexpr size_t cache_line_size_ = 64;
      97              : #endif
      98              : 
      99            0 :   alignas(cache_line_size_) std::atomic<std::int64_t> lock_{0};
     100              :   // Ensure we pad the end to avoid false sharing. Unlikely to happen because
     101              :   // of the layout, but better to be safe.
     102              : #if defined(__clang__)
     103              : #pragma GCC diagnostic push
     104              : #pragma GCC diagnostic ignored "-Wunused-private-field"
     105              : #endif
     106              :   // NOLINTNEXTLINE(modernize-avoid-c-arrays)
     107            0 :   char padding_[cache_line_size_ - sizeof(std::atomic<std::int64_t>)] = {};
     108              : #if defined(__clang__)
     109              : #pragma GCC diagnostic pop
     110              : #endif
     111              : };
     112              : }  // namespace Parallel