1 | /* |
2 | * Copyright 2018-present Facebook, Inc. |
3 | * |
4 | * Licensed under the Apache License, Version 2.0 (the "License"); |
5 | * you may not use this file except in compliance with the License. |
6 | * You may obtain a copy of the License at |
7 | * |
8 | * http://www.apache.org/licenses/LICENSE-2.0 |
9 | * |
10 | * Unless required by applicable law or agreed to in writing, software |
11 | * distributed under the License is distributed on an "AS IS" BASIS, |
12 | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
13 | * See the License for the specific language governing permissions and |
14 | * limitations under the License. |
15 | */ |
16 | #pragma once |
17 | |
18 | #include <folly/synchronization/Hazptr-fwd.h> |
19 | |
20 | #if FOLLY_HAZPTR_THR_LOCAL |
21 | |
22 | #include <folly/synchronization/HazptrObj.h> |
23 | #include <folly/synchronization/HazptrRec.h> |
24 | |
25 | #include <folly/SingletonThreadLocal.h> |
26 | |
27 | #include <glog/logging.h> |
28 | |
29 | #include <atomic> |
30 | |
31 | /** |
32 | * Thread local classes and singletons |
33 | */ |
34 | |
35 | namespace folly { |
36 | |
37 | /** |
38 | * hazptr_tc_entry |
39 | * |
40 | * Thread cache entry. |
41 | */ |
42 | template <template <typename> class Atom> |
43 | class hazptr_tc_entry { |
44 | hazptr_rec<Atom>* hprec_; |
45 | |
46 | template <uint8_t, template <typename> class> |
47 | friend class hazptr_array; |
48 | template <uint8_t, template <typename> class> |
49 | friend class hazptr_local; |
50 | friend class hazptr_tc<Atom>; |
51 | |
52 | FOLLY_ALWAYS_INLINE void fill(hazptr_rec<Atom>* hprec) noexcept { |
53 | hprec_ = hprec; |
54 | } |
55 | |
56 | FOLLY_ALWAYS_INLINE hazptr_rec<Atom>* get() const noexcept { |
57 | return hprec_; |
58 | } |
59 | |
60 | void evict() { |
61 | hprec_->release(); |
62 | } |
63 | }; // hazptr_tc_entry |
64 | |
65 | /** |
66 | * hazptr_tc: |
67 | * |
68 | * Thread cache of hazptr_rec-s that belong to the default domain. |
69 | */ |
70 | template <template <typename> class Atom> |
71 | class hazptr_tc { |
72 | static constexpr uint8_t kCapacity = 9; |
73 | |
74 | hazptr_tc_entry<Atom> entry_[kCapacity]; |
75 | uint8_t count_{0}; |
76 | bool local_{false}; // for debug mode only |
77 | |
78 | public: |
79 | ~hazptr_tc() { |
80 | for (uint8_t i = 0; i < count(); ++i) { |
81 | entry_[i].evict(); |
82 | } |
83 | } |
84 | |
85 | static constexpr uint8_t capacity() noexcept { |
86 | return kCapacity; |
87 | } |
88 | |
89 | private: |
90 | template <uint8_t, template <typename> class> |
91 | friend class hazptr_array; |
92 | friend class hazptr_holder<Atom>; |
93 | template <uint8_t, template <typename> class> |
94 | friend class hazptr_local; |
95 | |
96 | FOLLY_ALWAYS_INLINE |
97 | hazptr_tc_entry<Atom>& operator[](uint8_t i) noexcept { |
98 | DCHECK(i <= capacity()); |
99 | return entry_[i]; |
100 | } |
101 | |
102 | FOLLY_ALWAYS_INLINE hazptr_rec<Atom>* try_get() noexcept { |
103 | if (LIKELY(count_ > 0)) { |
104 | auto hprec = entry_[--count_].get(); |
105 | return hprec; |
106 | } |
107 | return nullptr; |
108 | } |
109 | |
110 | FOLLY_ALWAYS_INLINE bool try_put(hazptr_rec<Atom>* hprec) noexcept { |
111 | if (LIKELY(count_ < capacity())) { |
112 | entry_[count_++].fill(hprec); |
113 | return true; |
114 | } |
115 | return false; |
116 | } |
117 | |
118 | FOLLY_ALWAYS_INLINE uint8_t count() const noexcept { |
119 | return count_; |
120 | } |
121 | |
122 | FOLLY_ALWAYS_INLINE void set_count(uint8_t val) noexcept { |
123 | count_ = val; |
124 | } |
125 | |
126 | FOLLY_NOINLINE void fill(uint8_t num) { |
127 | DCHECK_LE(count_ + num, capacity()); |
128 | auto& domain = default_hazptr_domain<Atom>(); |
129 | for (uint8_t i = 0; i < num; ++i) { |
130 | auto hprec = domain.hprec_acquire(); |
131 | entry_[count_++].fill(hprec); |
132 | } |
133 | } |
134 | |
135 | FOLLY_NOINLINE void evict(uint8_t num) { |
136 | DCHECK_GE(count_, num); |
137 | for (uint8_t i = 0; i < num; ++i) { |
138 | entry_[--count_].evict(); |
139 | } |
140 | } |
141 | |
142 | bool local() const noexcept { // for debugging only |
143 | return local_; |
144 | } |
145 | |
146 | void set_local(bool b) noexcept { // for debugging only |
147 | local_ = b; |
148 | } |
149 | }; // hazptr_tc |
150 | |
151 | /** hazptr_tc_tls */ |
152 | template <template <typename> class Atom> |
153 | FOLLY_ALWAYS_INLINE hazptr_tc<Atom>& hazptr_tc_tls() { |
154 | return folly::SingletonThreadLocal<hazptr_tc<Atom>, void>::get(); |
155 | } |
156 | |
157 | /** |
158 | * hazptr_priv |
159 | * |
160 | * Per-thread list of retired objects to be pushed in bulk to domain. |
161 | */ |
162 | template <template <typename> class Atom> |
163 | class hazptr_priv { |
164 | static constexpr int kThreshold = 20; |
165 | |
166 | Atom<hazptr_obj<Atom>*> head_; |
167 | Atom<hazptr_obj<Atom>*> tail_; |
168 | int rcount_; |
169 | bool in_dtor_; |
170 | |
171 | public: |
172 | hazptr_priv() : head_(nullptr), tail_(nullptr), rcount_(0), in_dtor_(false) {} |
173 | |
174 | ~hazptr_priv() { |
175 | in_dtor_ = true; |
176 | if (!empty()) { |
177 | push_all_to_domain(false); |
178 | } |
179 | } |
180 | |
181 | private: |
182 | friend class hazptr_domain<Atom>; |
183 | friend class hazptr_obj<Atom>; |
184 | |
185 | bool empty() const noexcept { |
186 | return head() == nullptr; |
187 | } |
188 | |
189 | void push(hazptr_obj<Atom>* obj) { |
190 | DCHECK(!in_dtor_); |
191 | push_in_priv_list(obj); |
192 | } |
193 | |
194 | void push_in_priv_list(hazptr_obj<Atom>* obj) { |
195 | while (true) { |
196 | if (tail()) { |
197 | if (push_in_non_empty_list(obj)) { |
198 | break; |
199 | } |
200 | } else { |
201 | if (push_in_empty_list(obj)) { |
202 | break; |
203 | } |
204 | } |
205 | } |
206 | if (++rcount_ >= kThreshold) { |
207 | push_all_to_domain(true); |
208 | } |
209 | } |
210 | |
211 | void push_all_to_domain(bool check_to_reclaim) { |
212 | hazptr_obj<Atom>* h = nullptr; |
213 | hazptr_obj<Atom>* t = nullptr; |
214 | collect(h, t); |
215 | if (h) { |
216 | DCHECK(t); |
217 | hazptr_obj_list<Atom> l(h, t, rcount_); |
218 | hazptr_domain_push_retired<Atom>(l, check_to_reclaim); |
219 | rcount_ = 0; |
220 | } |
221 | } |
222 | |
223 | void collect( |
224 | hazptr_obj<Atom>*& colHead, |
225 | hazptr_obj<Atom>*& colTail) noexcept { |
226 | // This function doesn't change rcount_. |
227 | // The value rcount_ is accurate excluding the effects of calling collect(). |
228 | auto h = exchange_head(); |
229 | if (h) { |
230 | auto t = exchange_tail(); |
231 | DCHECK(t); |
232 | if (colTail) { |
233 | colTail->set_next(h); |
234 | } else { |
235 | colHead = h; |
236 | } |
237 | colTail = t; |
238 | } |
239 | } |
240 | |
241 | hazptr_obj<Atom>* head() const noexcept { |
242 | return head_.load(std::memory_order_acquire); |
243 | } |
244 | |
245 | hazptr_obj<Atom>* tail() const noexcept { |
246 | return tail_.load(std::memory_order_acquire); |
247 | } |
248 | |
249 | void set_head(hazptr_obj<Atom>* obj) noexcept { |
250 | head_.store(obj, std::memory_order_release); |
251 | } |
252 | |
253 | bool cas_head(hazptr_obj<Atom>* expected, hazptr_obj<Atom>* obj) noexcept { |
254 | return head_.compare_exchange_weak( |
255 | expected, obj, std::memory_order_acq_rel, std::memory_order_relaxed); |
256 | } |
257 | |
258 | bool cas_tail(hazptr_obj<Atom>* expected, hazptr_obj<Atom>* obj) noexcept { |
259 | return tail_.compare_exchange_weak( |
260 | expected, obj, std::memory_order_acq_rel, std::memory_order_relaxed); |
261 | } |
262 | |
263 | hazptr_obj<Atom>* exchange_head() noexcept { |
264 | return head_.exchange(nullptr, std::memory_order_acq_rel); |
265 | } |
266 | |
267 | hazptr_obj<Atom>* exchange_tail() noexcept { |
268 | return tail_.exchange(nullptr, std::memory_order_acq_rel); |
269 | } |
270 | |
271 | bool push_in_non_empty_list(hazptr_obj<Atom>* obj) noexcept { |
272 | auto h = head(); |
273 | if (h) { |
274 | obj->set_next(h); |
275 | if (cas_head(h, obj)) { |
276 | return true; |
277 | } |
278 | } |
279 | return false; |
280 | } |
281 | |
282 | bool push_in_empty_list(hazptr_obj<Atom>* obj) noexcept { |
283 | hazptr_obj<Atom>* t = nullptr; |
284 | obj->set_next(nullptr); |
285 | if (cas_tail(t, obj)) { |
286 | set_head(obj); |
287 | return true; |
288 | } |
289 | return false; |
290 | } |
291 | }; // hazptr_priv |
292 | |
293 | /** hazptr_priv_tls */ |
294 | struct HazptrTag {}; |
295 | |
296 | template <template <typename> class Atom> |
297 | using hazptr_priv_singleton = |
298 | folly::SingletonThreadLocal<hazptr_priv<Atom>, HazptrTag>; |
299 | |
300 | template <template <typename> class Atom> |
301 | FOLLY_ALWAYS_INLINE hazptr_priv<Atom>& hazptr_priv_tls() { |
302 | return hazptr_priv_singleton<Atom>::get(); |
303 | } |
304 | |
305 | } // namespace folly |
306 | |
307 | #endif // FOLLY_HAZPTR_THR_LOCAL |
308 | |