Eigen  5.0.1-dev+master
 
Loading...
Searching...
No Matches
ThreadLocal.h
1// This file is part of Eigen, a lightweight C++ template library
2// for linear algebra.
3//
4// Copyright (C) 2016 Benoit Steiner <benoit.steiner.goog@gmail.com>
5//
6// This Source Code Form is subject to the terms of the Mozilla
7// Public License v. 2.0. If a copy of the MPL was not distributed
8// with this file, You can obtain one at http://mozilla.org/MPL/2.0/.
9// SPDX-License-Identifier: MPL-2.0
10
11#ifndef EIGEN_THREADPOOL_THREAD_LOCAL_H
12#define EIGEN_THREADPOOL_THREAD_LOCAL_H
13
14#include <forward_list>
15
16#ifdef EIGEN_AVOID_THREAD_LOCAL
17
18#ifdef EIGEN_THREAD_LOCAL
19#undef EIGEN_THREAD_LOCAL
20#endif
21
22#else
23
24#define EIGEN_THREAD_LOCAL static thread_local
25
26// Disable TLS for Apple builds with deployment targets that do not support it.
27#if defined(__APPLE__)
28// Included for TARGET_OS_IPHONE, __IPHONE_OS_VERSION_MIN_REQUIRED,
29// __IPHONE_9_0.
30#include <Availability.h>
31#include <TargetConditionals.h>
32#endif
33// Checks whether the `thread_local` storage duration specifier is supported.
34#if EIGEN_COMP_CLANGAPPLE && TARGET_OS_IPHONE && __IPHONE_OS_VERSION_MIN_REQUIRED < __IPHONE_9_0
35// Notes: `thread_local` is not supported when targeting iOS versions before 9.0.
36#undef EIGEN_THREAD_LOCAL
37#endif
38
39#endif // EIGEN_AVOID_THREAD_LOCAL
40
41// IWYU pragma: private
42#include "./InternalHeaderCheck.h"
43
44namespace Eigen {
45
46namespace internal {
47template <typename T>
48struct ThreadLocalNoOpInitialize {
49 void operator()(T&) const {}
50};
51
52template <typename T>
53struct ThreadLocalNoOpRelease {
54 void operator()(T&) const {}
55};
56
57} // namespace internal
58
59// Thread local container for elements of type T, that does not use thread local
60// storage. As long as the number of unique threads accessing this storage
61// is smaller than `capacity_`, it is lock-free and wait-free. Otherwise it will
62// use a mutex for synchronization.
63//
64// Type `T` has to be default constructible, and by default each thread will get
65// a default constructed value. It is possible to specify custom `initialize`
66// callable, that will be called lazily from each thread accessing this object,
67// and will be passed a default initialized object of type `T`. Also it's
68// possible to pass a custom `release` callable, that will be invoked before
69// calling ~T().
70//
71// Example:
72//
73// struct Counter {
74// int value = 0;
75// }
76//
77// Eigen::ThreadLocal<Counter> counter(10);
78//
79// // Each thread will have access to its own counter object.
80// Counter& cnt = counter.local();
81// cnt++;
82//
83// WARNING: Eigen::ThreadLocal uses the OS-specific value returned by
84// std::this_thread::get_id() to identify threads. This value is not guaranteed
85// to be unique except for the life of the thread. A newly created thread may
86// get an OS-specific ID equal to that of an already destroyed thread.
87//
88// Somewhat similar to TBB thread local storage, with similar restrictions:
89// https://www.threadingbuildingblocks.org/docs/help/reference/thread_local_storage/enumerable_thread_specific_cls.html
90//
91template <typename T, typename Initialize = internal::ThreadLocalNoOpInitialize<T>,
92 typename Release = internal::ThreadLocalNoOpRelease<T>>
93class ThreadLocal {
94 // We preallocate default constructed elements in MaxSizedVector.
95 static_assert(std::is_default_constructible<T>::value, "ThreadLocal data type must be default constructible");
96
97 public:
98 explicit ThreadLocal(int capacity)
99 : ThreadLocal(capacity, internal::ThreadLocalNoOpInitialize<T>(), internal::ThreadLocalNoOpRelease<T>()) {}
100
101 ThreadLocal(int capacity, Initialize initialize)
102 : ThreadLocal(capacity, std::move(initialize), internal::ThreadLocalNoOpRelease<T>()) {}
103
104 ThreadLocal(int capacity, Initialize initialize, Release release)
105 : initialize_(std::move(initialize)),
106 release_(std::move(release)),
107 capacity_(capacity),
108 data_(capacity_),
109 ptr_(capacity_),
110 filled_records_(0) {
111 eigen_assert(capacity_ >= 0);
112 data_.resize(capacity_);
113 for (int i = 0; i < capacity_; ++i) {
114 ptr_.emplace_back(nullptr);
115 }
116 }
117
118 T& local() {
119 std::thread::id this_thread = std::this_thread::get_id();
120 if (capacity_ == 0) return InsertOrSpill(this_thread, 0);
121
122 std::size_t h = std::hash<std::thread::id>()(this_thread);
123 const int start_idx = h % capacity_;
124
125 // NOTE: From the definition of `std::this_thread::get_id()` it is
126 // guaranteed that we never can have concurrent insertions with the same key
127 // to our hash-map like data structure. If we didn't find an element during
128 // the initial traversal, it's guaranteed that no one else could have
129 // inserted it while we are in this function. This allows to massively
130 // simplify our lock-free insert-only hash map.
131
132 // Check if we already have an element for `this_thread`.
133 int idx = start_idx;
134 while (ThreadIdAndValue* record = ptr_[idx].load()) {
135 if (record->thread_id == this_thread) return record->value;
136
137 idx += 1;
138 if (idx >= capacity_) idx -= capacity_;
139 if (idx == start_idx) break;
140 }
141
142 return InsertOrSpill(this_thread, idx);
143 }
144
145 // WARN: It's not thread safe to call it concurrently with `local()`.
146 void ForEach(std::function<void(std::thread::id, T&)> f) {
147 // Reading directly from `data_` is unsafe, because only CAS to the
148 // record in `ptr_` makes all changes visible to other threads.
149 for (auto& ptr : ptr_) {
150 ThreadIdAndValue* record = ptr.load();
151 if (record == nullptr) continue;
152 f(record->thread_id, record->value);
153 }
154
155 // We did not spill into the list based storage.
156 if (filled_records_.load(std::memory_order_relaxed) < capacity_) return;
157
158 // Adds a happens before edge from the last call to InsertOrSpill().
159 EIGEN_MUTEX_LOCK lock(mu_);
160 for (auto& record : spilled_) {
161 f(record.thread_id, record.value);
162 }
163 }
164
165 // WARN: It's not thread safe to call it concurrently with `local()`.
166 ~ThreadLocal() {
167 // Reading directly from `data_` is unsafe, because only CAS to the record
168 // in `ptr_` makes all changes visible to other threads.
169 for (auto& ptr : ptr_) {
170 ThreadIdAndValue* record = ptr.load();
171 if (record == nullptr) continue;
172 release_(record->value);
173 }
174
175 // We did not spill into the list based storage.
176 if (filled_records_.load(std::memory_order_relaxed) < capacity_) return;
177
178 // Adds a happens before edge from the last call to InsertOrSpill().
179 EIGEN_MUTEX_LOCK lock(mu_);
180 for (auto& record : spilled_) {
181 release_(record.value);
182 }
183 }
184
185 private:
186 struct ThreadIdAndValue {
187 std::thread::id thread_id;
188 T value;
189 };
190
191 EIGEN_DONT_INLINE T& InsertOrSpill(std::thread::id this_thread, int idx) {
192 // If we are here, it means that `capacity_ == 0`, we found an insertion
193 // point in lookup table at `idx`, or we did a full traversal and table is
194 // full.
195
196 // If lock-free storage still has space, double check via atomic increment;
197 // if old value in `filled_records_` is at least `capacity_`, some other
198 // thread added an element while we were traversing lookup table, so we
199 // fallback on mutex below.
200 if (filled_records_.load() < capacity_) {
201 int insertion_index = filled_records_.fetch_add(1, std::memory_order_relaxed);
202 if (insertion_index < capacity_) {
203 // At this point it's guaranteed that we can access to
204 // data_[insertion_index] without a data race.
205 data_[insertion_index].thread_id = this_thread;
206 initialize_(data_[insertion_index].value);
207
208 // That's the pointer we'll put into the lookup table.
209 ThreadIdAndValue* inserted = &data_[insertion_index];
210
211 // Now we have to find an insertion point into the lookup table. We
212 // start from the `idx` that was identified as an insertion point above,
213 // it's guaranteed that we will have an empty record somewhere in a
214 // lookup table (because we created a record in the `data_`).
215 const int insertion_idx = idx;
216 ThreadIdAndValue* empty;
217
218 do {
219 // Always start search from the original insertion candidate.
220 idx = insertion_idx;
221 while (ptr_[idx].load() != nullptr) {
222 idx += 1;
223 if (idx >= capacity_) idx -= capacity_;
224 // If we did a full loop, it means that we don't have any free
225 // entries in the lookup table, and this means that something is
226 // terribly wrong.
227 eigen_assert(idx != insertion_idx);
228 }
229 // We'll use nullptr pointer to ThreadIdAndValue in a compare-and-swap
230 // loop.
231 empty = nullptr;
232 // Atomic CAS of the pointer guarantees that any other thread, that
233 // will follow this pointer will see all the mutations in the `data_`.
234 } while (!ptr_[idx].compare_exchange_weak(empty, inserted));
235
236 return inserted->value;
237 }
238 }
239
240 // Use list guarded by a mutex when lock-free storage is full.
241 EIGEN_MUTEX_LOCK lock(mu_);
242 for (auto& record : spilled_) {
243 if (record.thread_id == this_thread) return record.value;
244 }
245 spilled_.emplace_front();
246 ThreadIdAndValue& inserted = spilled_.front();
247 inserted.thread_id = this_thread;
248 initialize_(inserted.value);
249 return inserted.value;
250 }
251
252 Initialize initialize_;
253 Release release_;
254 const int capacity_;
255
256 // Storage that backs lock-free lookup table `ptr_`. Records stored in this
257 // storage contiguously starting from index 0.
258 MaxSizeVector<ThreadIdAndValue> data_;
259
260 // Atomic pointers to the data stored in `data_`. Used as a lookup table for
261 // linear probing hash map (https://en.wikipedia.org/wiki/Linear_probing).
262 MaxSizeVector<std::atomic<ThreadIdAndValue*>> ptr_;
263
264 // Number of records stored in the `data_`.
265 std::atomic<int> filled_records_;
266
267 // We fallback on per thread list if lock-free storage is full. In practice
268 // this should never happen, if `capacity_` is a reasonable estimate of the
269 // number of threads running in a system.
270 EIGEN_MUTEX mu_; // Protects spilled_.
271 std::forward_list<ThreadIdAndValue> spilled_;
272};
273
274} // namespace Eigen
275
276#endif // EIGEN_THREADPOOL_THREAD_LOCAL_H