NGen
Loading...
Searching...
No Matches
multithreading.hpp
1#ifndef NGEN_MULTITHREADING_HPP
2#define NGEN_MULTITHREADING_HPP
3
4#include <atomic>
5#include <cassert>
6#include <cstddef>
7#include <map>
8#include <memory>
9#include <mutex>
10#include <optional>
11#include <set>
12#include <shared_mutex>
13#include <system_error>
14#include <utility>
15#include <variant>
16#include <vector>
17#include <pthread.h>
18
20{
21 namespace details
22 {
23 // A string usable as a template argument, so that
24 // library_mutex() can be keyed by a library's name
25 template <std::size_t N>
27 constexpr string_literal(const char (&str)[N]) {
28 for (std::size_t i = 0; i < N; ++i)
29 value[i] = str[i];
30 }
31
32 char value[N];
33 };
34
35 // The one mutex in the process for the library named @arg
36 // name, created on first use. Exported, so that it stays one per
37 // process even if ngen is built as shared libraries with hidden
38 // visibility. Call library_mutex() rather than this.
39 [[gnu::visibility("default")]] std::mutex& named_library_mutex(char const* name);
40 }
41
42 // The mutex serializing calls into the library named @arg Name,
43 // which can't be called from more than one thread at a time. Every
44 // call into that library, anywhere in the process, must hold it:
45 //
46 // std::unique_lock netcdf_lock(multithreading::library_mutex<"netcdf">());
47 //
48 // "netcdf" is the NetCDF library, and the HDF5 library beneath it
49 // unless that was built thread-safe, which can't be called from more
50 // than one thread at a time even for different files.
51 //
52 // It's a plain std::mutex, so regions holding it must not nest.
53 //
54 // Each executable or shared library that calls this gets its own
55 // copy of the reference below, but they all refer to the one mutex
56 // that details::named_library_mutex() keeps for Name. A static
57 // mutex here instead would be one per shared library unless
58 // exported, which GCC won't do for a template specialized on a
59 // string_literal.
60 template <details::string_literal Name>
61 std::mutex& library_mutex()
62 {
63 static std::mutex& mutex = details::named_library_mutex(Name.value);
64 return mutex;
65 }
66
67 // What cache_slot::get() returns for a slot whose filler failed
68 struct failed_fill {};
69
70 // Thread-safe holder for one page of cached data. Exactly one
71 // thread fill()s it in; until then the slot is EMPTY, and
72 // other threads calling get() wait for it
73 //
74 // The buffer is a plain shared_ptr published through state_,
75 // rather than a std::atomic<std::shared_ptr>, so that readers
76 // only load state_ and don't contend on the lock that common
77 // implementations of the latter take on every load
78 template <typename T>
79 struct cache_slot {
80 cache_slot() = default;
81
82 cache_slot(cache_slot const&) = delete;
83 cache_slot(cache_slot &&) = delete;
84
85 // Get back a non-nullptr buffer pointer that can safely
86 // be read from. If it's not already set, this may block
87 // on another thread that will call fill() to set said
88 // pointer. Returns failed_fill if that thread called
89 // fail() instead
90 std::variant<std::shared_ptr<T>, failed_fill> get();
91
92 // Fill in this slot with the provided buffer pointer and
93 // safely unblock any threads waiting for it. Must be
94 // called by one thread with a non-null pointer, on a slot
95 // that is EMPTY, or in ERROR to retry a failed fill
96 void fill(std::shared_ptr<T> buffer_ptr, bool immediate_use);
97
98 // Mark this slot's fill as failed, for the thread that would
99 // have filled it to call instead of fill(). Threads waiting in
100 // get(), and later callers, get failed_fill rather than wait
101 // forever
102 void fail();
103
104 private:
105 std::shared_ptr<T> ptr_ = nullptr;
106 // ERROR marks a failed fill, which fill() may retry
107 enum STATE : char { EMPTY=0, FILLED=1, HOT=2, ERROR=3 };
108 std::atomic<int> state_ = STATE::EMPTY;
109 };
110
111 template <typename Key, typename T>
113 // Get back a cache slot matching the @arg key. Exactly
114 // one thread will return 'true' the first time `key` is
115 // passed
116 //
117 // Keys are expected to increase monotonically as the
118 // simulation advances, so a key is not looked up again
119 // after it is evicted. If it is, it is inserted again,
120 // and this returns 'true' again
121 //
122 // If this call inserts a slot and @arg eviction_floor is
123 // set, first evict all slots whose key is below it.
124 // Callers must not pass a floor above the key of any slot
125 // another thread may still be using, which includes the
126 // key being looked up. Eviction is handled here to take
127 // advantage of the locking on the internal structure
128 // necessary for insertion.
129 std::pair<cache_slot<T>&, bool> find_or_insert(Key const& key, std::optional<Key> const& eviction_floor);
130
131 // The keys of all slots currently in the cache
132 std::set<Key> keys() const;
133
134 private:
135 std::map<Key, cache_slot<T>> cache;
136 mutable std::shared_mutex mutex;
137 };
138
139 // Owns a pthread key, so it is deleted even if its owner's
140 // constructor throws after creating it
141 struct thread_key {
142 thread_key();
143 ~thread_key();
144 thread_key(thread_key const&) = delete;
145 thread_key& operator=(thread_key const&) = delete;
146 pthread_key_t key;
147 };
148
149 // One instance of T for each thread that calls get() on this
150 // object, default-constructed on that thread's first call.
151 //
152 // Each thread finds its instance through a pthread key. POSIX gives
153 // a newly created key a null value in every thread, so an object
154 // never sees instances belonging to an earlier one, even if it
155 // reuses that object's address or key. pthread_key_delete() doesn't
156 // destroy the values, so this object owns every instance it
157 // creates, and destroys them when it is destroyed. An instance
158 // whose thread exits stays until then.
159 //
160 // Each object uses one pthread key, so constructing one throws
161 // std::system_error once the process has PTHREAD_KEYS_MAX keys. The
162 // object must not be destroyed while any thread may still call
163 // get() on it or use an instance it returned.
164 template <typename T>
166 public:
167 per_thread() = default;
168 per_thread(per_thread const&) = delete;
169 per_thread& operator=(per_thread const&) = delete;
170
171 // The calling thread's instance, created on first use
172 T& get();
173
174 private:
175 // Declared before instances, so the key outlives them
178 std::vector<std::unique_ptr<T>> instances_;
179 };
180
181 // Remove entries in the passed cache with keys less than
182 // floor_index, and return them, so the caller
183 // controls when they are destroyed. Nodes are spliced, so this
184 // allocates and frees nothing. Returning the named local relies on
185 // NRVO copy elision; where that isn't applied, the map is moved,
186 // which is also constant time.
187 template <typename MapType>
188 MapType evict_stale_values(MapType& cache, typename MapType::key_type const& floor_index)
189 {
190 MapType evicted;
191 auto eviction_iterator = cache.begin();
192 auto end = cache.end();
193 while (eviction_iterator != end && eviction_iterator->first < floor_index) {
194 evicted.insert(evicted.end(), cache.extract(eviction_iterator++));
195 }
196 return evicted;
197 }
198
199 template <typename T>
200 void cache_slot<T>::fill(std::shared_ptr<T> buffer_ptr, bool immediate_use)
201 {
202 assert(buffer_ptr != nullptr);
203 assert(state_.load(std::memory_order_relaxed) == STATE::EMPTY ||
204 state_.load(std::memory_order_relaxed) == STATE::ERROR);
205 ptr_ = std::move(buffer_ptr);
206 // Publish with a release store on state_ itself, rather than a
207 // separate fence, since ThreadSanitizer doesn't model
208 // atomic_thread_fence and would report readers of the buffer
209 // as racing with this thread
210 state_.store(immediate_use ? STATE::HOT : STATE::FILLED, std::memory_order_release);
211 }
212
213 template <typename T>
215 {
216 assert(state_.load(std::memory_order_relaxed) == STATE::EMPTY);
217 state_.store(STATE::ERROR, std::memory_order_release);
218 }
219
220 template <typename T>
221 auto cache_slot<T>::get() -> std::variant<std::shared_ptr<T>, failed_fill>
222 {
223 int state = STATE::EMPTY;
224 while ((state = state_.load(std::memory_order_acquire)) == STATE::EMPTY) {
225 // Just spin on whatever thread is doing the filling
226 #pragma omp taskyield
227 }
228
229 if (state == STATE::ERROR)
230 return failed_fill{};
231
232 // Release, so that readers who see HOT from this store rather
233 // than from fill() synchronize with this thread, and so
234 // transitively happen-after the filling thread's writes
235 if (state == STATE::FILLED)
236 state_.store(STATE::HOT, std::memory_order_release);
237
238 return ptr_;
239 }
240
241 template <typename Key, typename T>
242 auto shared_cache<Key, T>::find_or_insert(Key const& key, std::optional<Key> const& eviction_floor) -> std::pair<cache_slot<T>&, bool>
243 {
244 // Look up the cache slot for key - either cache_iter =
245 // find() gets an extant slot, or this thread commits to
246 // creating and filling a new slot
247 std::shared_lock l(mutex);
248 auto cache_iter = cache.find(key);
249
250 if (cache_iter != cache.end())
251 return {cache_iter->second, false};
252
253 // Upgrade the lock and try to take responsibility for filling this entry in
254 l.unlock();
255 // Declared before the lock, so that evicted entries are destroyed
256 // after it is released, keeping frees of their buffers outside it
257 decltype(cache) evicted;
258 std::unique_lock ul(mutex);
259
260 // Re-check that some other thread didn't get here first
261 cache_iter = cache.find(key);
262
263 if (cache_iter != cache.end())
264 return {cache_iter->second, false};
265
266 if (eviction_floor) {
267 assert(*eviction_floor <= key);
268 // Evict while we hold the writer lock, and are
269 // responsible for modifying the cache anyway. Do it
270 // before the caller fills the new slot, to drop references
271 // to old data before loading new data to limit memory
272 // footprint.
273 evicted = evict_stale_values(cache, *eviction_floor);
274 }
275
276 // This thread really is reponsible for creating it
277 return {cache.try_emplace(key).first->second, true};
278 }
279
280 template <typename T>
282 {
283 if (void* existing = pthread_getspecific(key_.key))
284 return *static_cast<T*>(existing);
285
286 T* created;
287 {
288 std::lock_guard l{instances_mutex_};
289 created = instances_.emplace_back(std::make_unique<T>()).get();
290 }
291 int err = pthread_setspecific(key_.key, created);
292 if (err != 0)
293 throw std::system_error(err, std::generic_category(), "pthread_setspecific");
294 return *created;
295 }
296
297 template <typename Key, typename T>
298 auto shared_cache<Key, T>::keys() const -> std::set<Key>
299 {
300 std::shared_lock l(mutex);
301 std::set<Key> result;
302 for (auto const& entry : cache)
303 result.insert(entry.first);
304 return result;
305 }
306}
307
308#endif // NGEN_MULTITHREADING_HPP
Definition multithreading.hpp:165
per_thread(per_thread const &)=delete
std::vector< std::unique_ptr< T > > instances_
Definition multithreading.hpp:178
thread_key key_
Definition multithreading.hpp:176
T & get()
Definition multithreading.hpp:281
std::mutex instances_mutex_
Definition multithreading.hpp:177
per_thread & operator=(per_thread const &)=delete
std::mutex & named_library_mutex(char const *name)
Definition multithreading.cpp:10
Definition multithreading.hpp:20
MapType evict_stale_values(MapType &cache, typename MapType::key_type const &floor_index)
Definition multithreading.hpp:188
std::mutex & library_mutex()
Definition multithreading.hpp:61
STL namespace.
Definition multithreading.hpp:79
std::variant< std::shared_ptr< T >, failed_fill > get()
Definition multithreading.hpp:221
STATE
Definition multithreading.hpp:107
@ FILLED
Definition multithreading.hpp:107
@ HOT
Definition multithreading.hpp:107
@ EMPTY
Definition multithreading.hpp:107
@ ERROR
Definition multithreading.hpp:107
cache_slot(cache_slot &&)=delete
void fill(std::shared_ptr< T > buffer_ptr, bool immediate_use)
Definition multithreading.hpp:200
cache_slot(cache_slot const &)=delete
std::atomic< int > state_
Definition multithreading.hpp:108
void fail()
Definition multithreading.hpp:214
std::shared_ptr< T > ptr_
Definition multithreading.hpp:105
Definition multithreading.hpp:26
char value[N]
Definition multithreading.hpp:32
constexpr string_literal(const char(&str)[N])
Definition multithreading.hpp:27
Definition multithreading.hpp:68
Definition multithreading.hpp:112
std::pair< cache_slot< T > &, bool > find_or_insert(Key const &key, std::optional< Key > const &eviction_floor)
Definition multithreading.hpp:242
std::set< Key > keys() const
Definition multithreading.hpp:298
std::map< Key, cache_slot< T > > cache
Definition multithreading.hpp:135
std::shared_mutex mutex
Definition multithreading.hpp:136
Definition multithreading.hpp:141
thread_key()
Definition multithreading.cpp:24
thread_key & operator=(thread_key const &)=delete
thread_key(thread_key const &)=delete
~thread_key()
Definition multithreading.cpp:31
pthread_key_t key
Definition multithreading.hpp:146