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