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
35namespace folly {
36
37/**
38 * hazptr_tc_entry
39 *
40 * Thread cache entry.
41 */
42template <template <typename> class Atom>
43class 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 */
70template <template <typename> class Atom>
71class 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 */
152template <template <typename> class Atom>
153FOLLY_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 */
162template <template <typename> class Atom>
163class 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 */
294struct HazptrTag {};
295
296template <template <typename> class Atom>
297using hazptr_priv_singleton =
298 folly::SingletonThreadLocal<hazptr_priv<Atom>, HazptrTag>;
299
300template <template <typename> class Atom>
301FOLLY_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