xenium
left_right.hpp
1 //
2 // Copyright (c) 2018-2020 Manuel Pöter.
3 // Licensed under the MIT License. See LICENSE file in the project root for full license information.
4 //
5 
6 #ifndef XENIUM_LEFT_RIGHT_HPP
7 #define XENIUM_LEFT_RIGHT_HPP
8 
9 #include <atomic>
10 #include <cassert>
11 #include <mutex>
12 #include <thread>
13 
14 #ifdef _MSC_VER
15 #pragma warning(push)
16 #pragma warning(disable: 4324) // structure was padded due to alignment specifier
17 #endif
18 
19 namespace xenium {
20 
37 template<typename T>
38 struct left_right {
46  left_right(T source) :
47  left(source),
48  right(std::move(source))
49  {}
50 
59  left_right(T left, T right) :
60  left(std::move(left)),
61  right(std::move(right))
62  {}
63 
67  left_right() = default;
68 
82  template<typename Func>
83  auto read(Func&& func) const {
84  read_guard guard(*this);
85  // (1) - this seq-cst-load enforces a total order with the seq-cst-store (2, 3)
86  const T& inst = lr_indicator.load(std::memory_order_seq_cst) == READ_LEFT ? left : right;
87  return func(inst);
88  }
89 
99  template<typename Func>
100  void update(Func&& func) {
101  std::lock_guard<std::mutex> lock(writer_mutex);
102  assert(lr_indicator.load() == version_index.load());
103  if (lr_indicator.load(std::memory_order_relaxed) == READ_LEFT) {
104  func(right);
105  // (2) - this seq-cst-store enforces a total order with the seq-cst-load (1)
106  lr_indicator.store(READ_RIGHT, std::memory_order_seq_cst);
107  toggle_version_and_wait();
108  func(left);
109  } else {
110  func(left);
111  // (3) - this seq-cst-store enforces a total order with the seq-cst-load (1)
112  lr_indicator.store(READ_LEFT, std::memory_order_seq_cst);
113  toggle_version_and_wait();
114  func(right);
115  }
116  }
117 private:
118  struct alignas(64) read_indicator {
119  void arrive(void) {
120  // (4) - this seq-cst-fetch-add enforces a total order with the seq-cst-load (6)
121  counter.fetch_add(1, std::memory_order_seq_cst);
122  }
123  void depart(void) {
124  // (5) - this release-fetch-sub synchronizes-with the seq-cst-load (6)
125  counter.fetch_sub(1, std::memory_order_release);
126  // Note: even though this method is only called by reader threads that (usually)
127  // do not change the underlying data structure, we still have to use release
128  // order here to ensure that the read operations is properly ordered before a
129  // subsequent update operation.
130  }
131  bool empty(void) {
132  // (6) - this seq-cst-load enforces a total order with the seq-cst-fetch-add (4)
133  // and synchronizes-with the release-fetch-add (5)
134  return counter.load(std::memory_order_seq_cst) == 0;
135  }
136  private:
137  std::atomic<uint64_t> counter{0};
138  };
139 
140  struct read_guard {
141  read_guard(const left_right& inst) :
142  indicator(inst.get_read_indicator(inst.version_index.load(std::memory_order_relaxed)))
143  {
144  indicator.arrive();
145  }
146  ~read_guard() { indicator.depart(); }
147  private:
148  read_indicator& indicator;
149  };
150  friend struct read_guard;
151 
152  void toggle_version_and_wait(void) {
153  const int current_version = version_index.load(std::memory_order_relaxed);
154  const int current_idx = current_version & 0x1;
155  const int next_idx = (current_version + 1) & 0x1;
156 
157  wait_for_readers(next_idx);
158  version_index.store(next_idx, std::memory_order_relaxed);
159  wait_for_readers(current_idx);
160  }
161 
162  void wait_for_readers(int idx) {
163  auto& indicator = get_read_indicator(idx);
164  while (!indicator.empty())
165  std::this_thread::yield();
166  }
167 
168  read_indicator& get_read_indicator(int idx) const {
169  assert(idx == 0 || idx == 1);
170  if (idx == 0)
171  return read_indicator1;
172  return read_indicator2;
173  }
174 
175  static constexpr int READ_LEFT = 0;
176  static constexpr int READ_RIGHT = 1;
177 
178  // TODO: make mutex type configurable via policy
179  std::mutex writer_mutex;
180  std::atomic<int> version_index{0} ;
181  std::atomic<int> lr_indicator { READ_LEFT };
182 
183  mutable read_indicator read_indicator1;
184  T left;
185 
186  mutable read_indicator read_indicator2;
187  T right;
188 };
189 }
190 
191 #ifdef _MSC_VER
192 #pragma warning(pop)
193 #endif
194 
195 #endif
xenium::left_right
Generic implementation of the LeftRight algorithm proposed by Ramalhete and Correia [RC15].
Definition: left_right.hpp:38
xenium::left_right::left_right
left_right(T left, T right)
Initializes the two underlying instances withe the specified sources.
Definition: left_right.hpp:59
xenium::left_right::left_right
left_right(T source)
Initialize the two underlying T instances with the specified source.
Definition: left_right.hpp:46
xenium::left_right::read
auto read(Func &&func) const
Performs a read operation on the active instance using the specified functor.
Definition: left_right.hpp:83
xenium::left_right::update
void update(Func &&func)
Performs an update operation on both underlying instances using the specified functor.
Definition: left_right.hpp:100
xenium::left_right::left_right
left_right()=default
Default constructs both underlying instances.