e287aecc91c45d1d00d92bdac29b3f75f2532a64
[folly.git] / folly / experimental / hazptr / hazptr-impl.h
1 /*
2  * Copyright 2017 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
17 /* override-include-guard */
18 #ifndef HAZPTR_H
19 #error "This should only be included by hazptr.h"
20 #endif
21
22 /* quality of implementation switches */
23
24 // NOTE: The #ifndef pattern is prone to ODR violation. Its use for
25 // quality of implementation options is temporary. Eventually these
26 // options should be added to the API in future API extensions.
27
28 #ifndef HAZPTR_AMB
29 #define HAZPTR_AMB true
30 #endif
31
32 #ifndef HAZPTR_TC
33 #define HAZPTR_TC true
34 #endif
35
36 #ifndef HAZPTR_TC_SIZE
37 #define HAZPTR_TC_SIZE 10
38 #endif
39
40 #ifndef HAZPTR_PRIV
41 #define HAZPTR_PRIV true
42 #endif
43
44 #ifndef HAZPTR_ONE_DOMAIN
45 #define HAZPTR_ONE_DOMAIN false
46 #endif
47
48 #ifndef HAZPTR_SCAN_MULT
49 #define HAZPTR_SCAN_MULT 2
50 #endif
51
52 #ifndef HAZPTR_SCAN_THRESHOLD
53 #define HAZPTR_SCAN_THRESHOLD 1000
54 #endif
55
56 /* stats switch */
57 #ifndef HAZPTR_STATS
58 #define HAZPTR_STATS false
59 #endif
60
61 #include <folly/concurrency/CacheLocality.h>
62 #include <folly/experimental/hazptr/debug.h>
63 #include <folly/synchronization/AsymmetricMemoryBarrier.h>
64
65 #include <mutex> // for thread caching
66 #include <unordered_set> // for hash set in bulk reclamation
67
68 namespace folly {
69 namespace hazptr {
70
71 /**
72  *  Helper classes and functions
73  */
74
75 /** hazptr_stats */
76
77 class hazptr_stats;
78
79 #if HAZPTR_STATS
80 #define INC_HAZPTR_STATS(x) hazptr_stats_.x()
81 #else
82 #define INC_HAZPTR_STATS(x)
83 #endif
84
85 /** hazptr_mb */
86
87 class hazptr_mb {
88  public:
89   static void light();
90   static void heavy();
91 };
92
93 /**
94  *  TLS structures
95  */
96
97 /** TLS life state */
98
99 enum hazptr_tls_state { TLS_ALIVE, TLS_UNINITIALIZED, TLS_DESTROYED };
100
101 /** hazptr_tc structures
102  *  Thread caching of hazptr_rec-s that belong to the default domain.
103  */
104
105 struct hazptr_tc_entry {
106   hazptr_rec* hprec_;
107
108   void fill(hazptr_rec* hprec);
109   hazptr_rec* get();
110   void evict();
111 };
112
113 static_assert(
114     std::is_trivial<hazptr_tc_entry>::value,
115     "hazptr_tc_entry must be trivial"
116     " to avoid a branch to check initialization");
117
118 struct hazptr_tc {
119   hazptr_tc_entry entry_[HAZPTR_TC_SIZE];
120   size_t count_;
121   bool local_; // for debug mode only
122
123  public:
124   hazptr_tc_entry& operator[](size_t i);
125   hazptr_rec* get();
126   bool put(hazptr_rec* hprec);
127   size_t count();
128 };
129
130 static_assert(
131     std::is_trivial<hazptr_tc>::value,
132     "hazptr_tc must be trivial to avoid a branch to check initialization");
133
134 hazptr_tc* hazptr_tc_tls();
135 void hazptr_tc_init();
136 void hazptr_tc_shutdown();
137 hazptr_rec* hazptr_tc_try_get();
138 bool hazptr_tc_try_put(hazptr_rec* hprec);
139
140 /** hazptr_priv structures
141  *  Thread private lists of retired objects that belong to the default domain.
142  */
143
144 struct hazptr_priv {
145   hazptr_obj* head_;
146   hazptr_obj* tail_;
147   int rcount_;
148   bool active_;
149
150   void push(hazptr_obj* obj);
151   void pushAllToDomain();
152 };
153
154 static_assert(
155     std::is_trivial<hazptr_priv>::value,
156     "hazptr_priv must be trivial to avoid a branch to check initialization");
157
158 void hazptr_priv_init();
159 void hazptr_priv_shutdown();
160 bool hazptr_priv_try_retire(hazptr_obj* obj);
161
162 /** hazptr_tls_life */
163
164 struct hazptr_tls_life {
165   hazptr_tls_life();
166   ~hazptr_tls_life();
167 };
168
169 void tls_life_odr_use();
170
171 /** tls globals */
172
173 extern thread_local hazptr_tls_state tls_state_;
174 extern thread_local hazptr_tc tls_tc_data_;
175 extern thread_local hazptr_priv tls_priv_data_;
176 extern thread_local hazptr_tls_life tls_life_; // last
177
178 /**
179  *  hazptr_domain
180  */
181
182 inline constexpr hazptr_domain::hazptr_domain(memory_resource* mr) noexcept
183     : mr_(mr) {}
184
185 /**
186  *  hazptr_obj_base
187  */
188
189 template <typename T, typename D>
190 inline void hazptr_obj_base<T, D>::retire(hazptr_domain& domain, D deleter) {
191   DEBUG_PRINT(this << " " << &domain);
192   deleter_ = std::move(deleter);
193   reclaim_ = [](hazptr_obj* p) {
194     auto hobp = static_cast<hazptr_obj_base*>(p);
195     auto obj = static_cast<T*>(hobp);
196     hobp->deleter_(obj);
197   };
198   if (HAZPTR_PRIV &&
199       (HAZPTR_ONE_DOMAIN || (&domain == &default_hazptr_domain()))) {
200     if (hazptr_priv_try_retire(this)) {
201       return;
202     }
203   }
204   domain.objRetire(this);
205 }
206
207 /**
208  *  hazptr_obj_base_refcounted
209  */
210
211 template <typename T, typename D>
212 inline void hazptr_obj_base_refcounted<T, D>::retire(
213     hazptr_domain& domain,
214     D deleter) {
215   DEBUG_PRINT(this << " " << &domain);
216   deleter_ = std::move(deleter);
217   reclaim_ = [](hazptr_obj* p) {
218     auto hrobp = static_cast<hazptr_obj_base_refcounted*>(p);
219     if (hrobp->release_ref()) {
220       auto obj = static_cast<T*>(hrobp);
221       hrobp->deleter_(obj);
222     }
223   };
224   if (HAZPTR_PRIV &&
225       (HAZPTR_ONE_DOMAIN || (&domain == &default_hazptr_domain()))) {
226     if (hazptr_priv_try_retire(this)) {
227       return;
228     }
229   }
230   domain.objRetire(this);
231 }
232
233 template <typename T, typename D>
234 inline void hazptr_obj_base_refcounted<T, D>::acquire_ref() {
235   DEBUG_PRINT(this);
236   auto oldval = refcount_.fetch_add(1);
237   DCHECK(oldval >= 0);
238 }
239
240 template <typename T, typename D>
241 inline void hazptr_obj_base_refcounted<T, D>::acquire_ref_safe() {
242   DEBUG_PRINT(this);
243   auto oldval = refcount_.load(std::memory_order_acquire);
244   DCHECK(oldval >= 0);
245   refcount_.store(oldval + 1, std::memory_order_release);
246 }
247
248 template <typename T, typename D>
249 inline bool hazptr_obj_base_refcounted<T, D>::release_ref() {
250   DEBUG_PRINT(this);
251   auto oldval = refcount_.load(std::memory_order_acquire);
252   if (oldval > 0) {
253     oldval = refcount_.fetch_sub(1);
254   } else {
255     if (kIsDebug) {
256       refcount_.store(-1);
257     }
258   }
259   DEBUG_PRINT(this << " " << oldval);
260   DCHECK(oldval >= 0);
261   return oldval == 0;
262 }
263
264 /**
265  *  hazptr_rec
266  */
267
268 class hazptr_rec {
269   friend class hazptr_domain;
270   friend class hazptr_holder;
271   friend struct hazptr_tc_entry;
272
273   FOLLY_ALIGN_TO_AVOID_FALSE_SHARING
274   std::atomic<const void*> hazptr_{nullptr};
275   hazptr_rec* next_{nullptr};
276   std::atomic<bool> active_{false};
277
278   void set(const void* p) noexcept;
279   const void* get() const noexcept;
280   void clear() noexcept;
281   bool isActive() noexcept;
282   bool tryAcquire() noexcept;
283   void release() noexcept;
284 };
285
286 /**
287  *  hazptr_holder
288  */
289
290 FOLLY_ALWAYS_INLINE hazptr_holder::hazptr_holder(hazptr_domain& domain) {
291   domain_ = &domain;
292   if (LIKELY(
293           HAZPTR_TC &&
294           (HAZPTR_ONE_DOMAIN || &domain == &default_hazptr_domain()))) {
295     auto hprec = hazptr_tc_try_get();
296     if (LIKELY(hprec != nullptr)) {
297       hazptr_ = hprec;
298       DEBUG_PRINT(this << " " << domain_ << " " << hazptr_);
299       return;
300     }
301   }
302   hazptr_ = domain_->hazptrAcquire();
303   DEBUG_PRINT(this << " " << domain_ << " " << hazptr_);
304   if (hazptr_ == nullptr) { std::bad_alloc e; throw e; }
305 }
306
307 FOLLY_ALWAYS_INLINE hazptr_holder::hazptr_holder(std::nullptr_t) noexcept {
308   domain_ = nullptr;
309   hazptr_ = nullptr;
310   DEBUG_PRINT(this << " " << domain_ << " " << hazptr_);
311 }
312
313 FOLLY_ALWAYS_INLINE hazptr_holder::~hazptr_holder() {
314   DEBUG_PRINT(this);
315   if (LIKELY(hazptr_ != nullptr)) {
316     hazptr_->clear();
317     if (LIKELY(
318             HAZPTR_TC &&
319             (HAZPTR_ONE_DOMAIN || domain_ == &default_hazptr_domain()))) {
320       if (LIKELY(hazptr_tc_try_put(hazptr_))) {
321         return;
322       }
323     }
324     domain_->hazptrRelease(hazptr_);
325   }
326 }
327
328 FOLLY_ALWAYS_INLINE hazptr_holder::hazptr_holder(hazptr_holder&& rhs) noexcept {
329   domain_ = rhs.domain_;
330   hazptr_ = rhs.hazptr_;
331   rhs.domain_ = nullptr;
332   rhs.hazptr_ = nullptr;
333 }
334
335 FOLLY_ALWAYS_INLINE
336 hazptr_holder& hazptr_holder::operator=(hazptr_holder&& rhs) noexcept {
337   /* Self-move is a no-op.  */
338   if (LIKELY(this != &rhs)) {
339     this->~hazptr_holder();
340     new (this) hazptr_holder(std::move(rhs));
341   }
342   return *this;
343 }
344
345 template <typename T>
346 FOLLY_ALWAYS_INLINE bool hazptr_holder::try_protect(
347     T*& ptr,
348     const std::atomic<T*>& src) noexcept {
349   return try_protect(ptr, src, [](T* t) { return t; });
350 }
351
352 template <typename T, typename Func>
353 FOLLY_ALWAYS_INLINE bool hazptr_holder::try_protect(
354     T*& ptr,
355     const std::atomic<T*>& src,
356     Func f) noexcept {
357   DEBUG_PRINT(this << " " << ptr << " " << &src);
358   reset(f(ptr));
359   /*** Full fence ***/ hazptr_mb::light();
360   T* p = src.load(std::memory_order_acquire);
361   if (UNLIKELY(p != ptr)) {
362     ptr = p;
363     reset();
364     return false;
365   }
366   return true;
367 }
368
369 template <typename T>
370 FOLLY_ALWAYS_INLINE T* hazptr_holder::get_protected(
371     const std::atomic<T*>& src) noexcept {
372   return get_protected(src, [](T* t) { return t; });
373 }
374
375 template <typename T, typename Func>
376 FOLLY_ALWAYS_INLINE T* hazptr_holder::get_protected(
377     const std::atomic<T*>& src,
378     Func f) noexcept {
379   T* p = src.load(std::memory_order_relaxed);
380   while (!try_protect(p, src, f)) {
381   }
382   DEBUG_PRINT(this << " " << p << " " << &src);
383   return p;
384 }
385
386 template <typename T>
387 FOLLY_ALWAYS_INLINE void hazptr_holder::reset(const T* ptr) noexcept {
388   auto p = static_cast<hazptr_obj*>(const_cast<T*>(ptr));
389   DEBUG_PRINT(this << " " << ptr << " p:" << p);
390   DCHECK(hazptr_); // UB if *this is empty
391   hazptr_->set(p);
392 }
393
394 FOLLY_ALWAYS_INLINE void hazptr_holder::reset(std::nullptr_t) noexcept {
395   DEBUG_PRINT(this);
396   DCHECK(hazptr_); // UB if *this is empty
397   hazptr_->clear();
398 }
399
400 FOLLY_ALWAYS_INLINE void hazptr_holder::swap(hazptr_holder& rhs) noexcept {
401   DEBUG_PRINT(
402     this << " " <<  this->hazptr_ << " " << this->domain_ << " -- "
403     << &rhs << " " << rhs.hazptr_ << " " << rhs.domain_);
404   if (!HAZPTR_ONE_DOMAIN) {
405     std::swap(this->domain_, rhs.domain_);
406   }
407   std::swap(this->hazptr_, rhs.hazptr_);
408 }
409
410 FOLLY_ALWAYS_INLINE void swap(hazptr_holder& lhs, hazptr_holder& rhs) noexcept {
411   lhs.swap(rhs);
412 }
413
414 /**
415  *  hazptr_array
416  */
417
418 template <size_t M>
419 FOLLY_ALWAYS_INLINE hazptr_array<M>::hazptr_array() {
420   auto h = reinterpret_cast<hazptr_holder*>(&raw_);
421   if (HAZPTR_TC) {
422     auto ptc = hazptr_tc_tls();
423     if (LIKELY(ptc != nullptr)) {
424       auto& tc = *ptc;
425       auto count = tc.count();
426       if (M <= count) {
427         size_t offset = count - M;
428         for (size_t i = 0; i < M; ++i) {
429           auto hprec = tc[offset + i].hprec_;
430           DCHECK(hprec != nullptr);
431           DEBUG_PRINT(i << " " << &h[i]);
432           new (&h[i]) hazptr_holder(nullptr);
433           h[i].hazptr_ = hprec;
434           DEBUG_PRINT(
435               i << " " << &h[i] << " " << h[i].domain_ << " " << h[i].hazptr_);
436         }
437         tc.count_ = offset;
438         return;
439       }
440     }
441   }
442   // slow path
443   for (size_t i = 0; i < M; ++i) {
444     new (&h[i]) hazptr_holder;
445     DEBUG_PRINT(
446         i << " " << &h[i] << " " << h[i].domain_ << " " << h[i].hazptr_);
447   }
448 }
449
450 template <size_t M>
451 FOLLY_ALWAYS_INLINE hazptr_array<M>::hazptr_array(
452     hazptr_array&& other) noexcept {
453   DEBUG_PRINT(this << " " << M << " " << &other);
454   auto h = reinterpret_cast<hazptr_holder*>(&raw_);
455   for (size_t i = 0; i < M; ++i) {
456     new (&h[i]) hazptr_holder(std::move(other.h_[i]));
457     DEBUG_PRINT(i << " " << &h[i] << " " << &other.h_[i]);
458   }
459   empty_ = other.empty_;
460   other.empty_ = true;
461 }
462
463 template <size_t M>
464 FOLLY_ALWAYS_INLINE hazptr_array<M>::hazptr_array(std::nullptr_t) noexcept {
465   DEBUG_PRINT(this << " " << M);
466   auto h = reinterpret_cast<hazptr_holder*>(&raw_);
467   for (size_t i = 0; i < M; ++i) {
468     new (&h[i]) hazptr_holder(nullptr);
469     DEBUG_PRINT(i << " " << &h[i]);
470   }
471   empty_ = true;
472 }
473
474 template <size_t M>
475 FOLLY_ALWAYS_INLINE hazptr_array<M>::~hazptr_array() {
476   if (empty_) {
477     return;
478   }
479   auto h = reinterpret_cast<hazptr_holder*>(&raw_);
480   if (HAZPTR_TC) {
481     auto ptc = hazptr_tc_tls();
482     if (LIKELY(ptc != nullptr)) {
483       auto& tc = *ptc;
484       auto count = tc.count();
485       if ((M <= HAZPTR_TC_SIZE) && (count + M <= HAZPTR_TC_SIZE)) {
486         for (size_t i = 0; i < M; ++i) {
487           tc[count + i].hprec_ = h[i].hazptr_;
488           DEBUG_PRINT(i << " " << &h[i]);
489           new (&h[i]) hazptr_holder(nullptr);
490           DEBUG_PRINT(
491               i << " " << &h[i] << " " << h[i].domain_ << " " << h[i].hazptr_);
492         }
493         tc.count_ = count + M;
494         return;
495       }
496     }
497   }
498   // slow path
499   for (size_t i = 0; i < M; ++i) {
500     h[i].~hazptr_holder();
501   }
502 }
503
504 template <size_t M>
505 FOLLY_ALWAYS_INLINE hazptr_array<M>& hazptr_array<M>::operator=(
506     hazptr_array&& other) noexcept {
507   DEBUG_PRINT(this << " " << M << " " << &other);
508   auto h = reinterpret_cast<hazptr_holder*>(&raw_);
509   for (size_t i = 0; i < M; ++i) {
510     h[i] = std::move(other[i]);
511     DEBUG_PRINT(i << " " << &h[i] << " " << &other[i]);
512   }
513   empty_ = other.empty_;
514   other.empty_ = true;
515   return *this;
516 }
517
518 template <size_t M>
519 FOLLY_ALWAYS_INLINE hazptr_holder& hazptr_array<M>::operator[](
520     size_t i) noexcept {
521   auto h = reinterpret_cast<hazptr_holder*>(&raw_);
522   DCHECK(i < M);
523   return h[i];
524 }
525
526 /**
527  *  hazptr_local
528  */
529
530 template <size_t M>
531 FOLLY_ALWAYS_INLINE hazptr_local<M>::hazptr_local() {
532   auto h = reinterpret_cast<hazptr_holder*>(&raw_);
533   if (HAZPTR_TC) {
534     auto ptc = hazptr_tc_tls();
535     if (LIKELY(ptc != nullptr)) {
536       auto& tc = *ptc;
537       auto count = tc.count();
538       if (M <= count) {
539         if (kIsDebug) {
540           DCHECK(!tc.local_);
541           tc.local_ = true;
542         }
543         // Fast path
544         for (size_t i = 0; i < M; ++i) {
545           auto hprec = tc[i].hprec_;
546           DCHECK(hprec != nullptr);
547           DEBUG_PRINT(i << " " << &h[i]);
548           new (&h[i]) hazptr_holder(nullptr);
549           h[i].hazptr_ = hprec;
550           DEBUG_PRINT(
551               i << " " << &h[i] << " " << h[i].domain_ << " " << h[i].hazptr_);
552         }
553         return;
554       }
555     }
556   }
557   // Slow path
558   need_destruct_ = true;
559   for (size_t i = 0; i < M; ++i) {
560     new (&h[i]) hazptr_holder;
561     DEBUG_PRINT(
562         i << " " << &h[i] << " " << h[i].domain_ << " " << h[i].hazptr_);
563   }
564 }
565
566 template <size_t M>
567 FOLLY_ALWAYS_INLINE hazptr_local<M>::~hazptr_local() {
568   if (LIKELY(!need_destruct_)) {
569     if (kIsDebug) {
570       auto ptc = hazptr_tc_tls();
571       DCHECK(ptc != nullptr);
572       auto& tc = *ptc;
573       DCHECK(tc.local_);
574       tc.local_ = false;
575     }
576     return;
577   }
578   // Slow path
579   auto h = reinterpret_cast<hazptr_holder*>(&raw_);
580   for (size_t i = 0; i < M; ++i) {
581     h[i].~hazptr_holder();
582   }
583 }
584
585 template <size_t M>
586 FOLLY_ALWAYS_INLINE hazptr_holder& hazptr_local<M>::operator[](
587     size_t i) noexcept {
588   auto h = reinterpret_cast<hazptr_holder*>(&raw_);
589   DCHECK(i < M);
590   return h[i];
591 }
592
593 ////////////////////////////////////////////////////////////////////////////////
594 // [TODO]:
595 // - Control of reclamation (when and by whom)
596 // - End-to-end lock-free implementation
597
598 /** Definition of default_hazptr_domain() */
599
600 FOLLY_ALWAYS_INLINE hazptr_domain& default_hazptr_domain() {
601   DEBUG_PRINT(&default_domain_);
602   return default_domain_;
603 }
604
605 /** hazptr_rec */
606
607 FOLLY_ALWAYS_INLINE void hazptr_rec::set(const void* p) noexcept {
608   DEBUG_PRINT(this << " " << p);
609   hazptr_.store(p, std::memory_order_release);
610 }
611
612 inline const void* hazptr_rec::get() const noexcept {
613   auto p = hazptr_.load(std::memory_order_acquire);
614   DEBUG_PRINT(this << " " << p);
615   return p;
616 }
617
618 FOLLY_ALWAYS_INLINE void hazptr_rec::clear() noexcept {
619   DEBUG_PRINT(this);
620   hazptr_.store(nullptr, std::memory_order_release);
621 }
622
623 inline bool hazptr_rec::isActive() noexcept {
624   return active_.load(std::memory_order_acquire);
625 }
626
627 inline bool hazptr_rec::tryAcquire() noexcept {
628   bool active = isActive();
629   if (!active &&
630       active_.compare_exchange_strong(
631           active, true, std::memory_order_release, std::memory_order_relaxed)) {
632     DEBUG_PRINT(this);
633     return true;
634   }
635   return false;
636 }
637
638 inline void hazptr_rec::release() noexcept {
639   DEBUG_PRINT(this);
640   active_.store(false, std::memory_order_release);
641 }
642
643 /** hazptr_obj */
644
645 inline const void* hazptr_obj::getObjPtr() const {
646   DEBUG_PRINT(this);
647   return this;
648 }
649
650 /** hazptr_domain */
651
652 inline hazptr_domain::~hazptr_domain() {
653   DEBUG_PRINT(this);
654   { /* reclaim all remaining retired objects */
655     hazptr_obj* next;
656     auto retired = retired_.exchange(nullptr);
657     while (retired) {
658       for (auto p = retired; p; p = next) {
659         next = p->next_;
660         DEBUG_PRINT(this << " " << p << " " << p->reclaim_);
661         (*(p->reclaim_))(p);
662       }
663       retired = retired_.exchange(nullptr);
664     }
665   }
666   /* Leak the data for the default domain to avoid destruction order
667    * issues with thread caches.
668    */
669   if (this != &default_hazptr_domain()) {
670     /* free all hazptr_rec-s */
671     hazptr_rec* next;
672     for (auto p = hazptrs_.load(std::memory_order_acquire); p; p = next) {
673       next = p->next_;
674       DCHECK(!p->isActive());
675       mr_->deallocate(static_cast<void*>(p), sizeof(hazptr_rec));
676     }
677   }
678 }
679
680 inline hazptr_rec* hazptr_domain::hazptrAcquire() {
681   hazptr_rec* p;
682   hazptr_rec* next;
683   for (p = hazptrs_.load(std::memory_order_acquire); p; p = next) {
684     next = p->next_;
685     if (p->tryAcquire()) {
686       return p;
687     }
688   }
689   p = static_cast<hazptr_rec*>(mr_->allocate(sizeof(hazptr_rec)));
690   DEBUG_PRINT(this << " " << p << " " << sizeof(hazptr_rec));
691   if (p == nullptr) {
692     return nullptr;
693   }
694   p->active_.store(true, std::memory_order_relaxed);
695   p->next_ = hazptrs_.load(std::memory_order_acquire);
696   while (!hazptrs_.compare_exchange_weak(
697       p->next_, p, std::memory_order_release, std::memory_order_acquire)) {
698     /* keep trying */;
699   }
700   auto hcount = hcount_.fetch_add(1);
701   DEBUG_PRINT(this << " " << p << " " << sizeof(hazptr_rec) << " " << hcount);
702   return p;
703 }
704
705 inline void hazptr_domain::hazptrRelease(hazptr_rec* p) noexcept {
706   DEBUG_PRINT(this << " " << p);
707   p->release();
708 }
709
710 inline int
711 hazptr_domain::pushRetired(hazptr_obj* head, hazptr_obj* tail, int count) {
712   /*** Full fence ***/ hazptr_mb::light();
713   tail->next_ = retired_.load(std::memory_order_acquire);
714   while (!retired_.compare_exchange_weak(
715       tail->next_,
716       head,
717       std::memory_order_release,
718       std::memory_order_acquire)) {
719   }
720   return rcount_.fetch_add(count) + count;
721 }
722
723 inline bool hazptr_domain::reachedThreshold(int rcount) {
724   return (
725       rcount >= HAZPTR_SCAN_THRESHOLD &&
726       rcount >= HAZPTR_SCAN_MULT * hcount_.load(std::memory_order_acquire));
727 }
728
729 inline void hazptr_domain::objRetire(hazptr_obj* p) {
730   auto rcount = pushRetired(p, p, 1);
731   if (reachedThreshold(rcount)) {
732     tryBulkReclaim();
733   }
734 }
735
736 inline void hazptr_domain::tryBulkReclaim() {
737   DEBUG_PRINT(this);
738   do {
739     auto hcount = hcount_.load(std::memory_order_acquire);
740     auto rcount = rcount_.load(std::memory_order_acquire);
741     if (rcount < HAZPTR_SCAN_THRESHOLD || rcount < HAZPTR_SCAN_MULT * hcount) {
742       return;
743     }
744     if (rcount_.compare_exchange_weak(
745             rcount, 0, std::memory_order_release, std::memory_order_relaxed)) {
746       break;
747     }
748   } while (true);
749   bulkReclaim();
750 }
751
752 inline void hazptr_domain::bulkReclaim() {
753   DEBUG_PRINT(this);
754   /*** Full fence ***/ hazptr_mb::heavy();
755   auto p = retired_.exchange(nullptr, std::memory_order_acquire);
756   auto h = hazptrs_.load(std::memory_order_acquire);
757   std::unordered_set<const void*> hs; // TODO lock-free alternative
758   for (; h; h = h->next_) {
759     hs.insert(h->get());
760   }
761   int rcount = 0;
762   hazptr_obj* retired = nullptr;
763   hazptr_obj* tail = nullptr;
764   hazptr_obj* next;
765   for (; p; p = next) {
766     next = p->next_;
767     if (hs.count(p->getObjPtr()) == 0) {
768       DEBUG_PRINT(this << " " << p << " " << p->reclaim_);
769       (*(p->reclaim_))(p);
770     } else {
771       p->next_ = retired;
772       retired = p;
773       if (tail == nullptr) {
774         tail = p;
775       }
776       ++rcount;
777     }
778   }
779   if (tail) {
780     pushRetired(retired, tail, rcount);
781   }
782 }
783
784 /** hazptr_stats */
785
786 class hazptr_stats {
787  public:
788   ~hazptr_stats();
789   void light();
790   void heavy();
791   void seq_cst();
792
793  private:
794   std::atomic<uint64_t> light_{0};
795   std::atomic<uint64_t> heavy_{0};
796   std::atomic<uint64_t> seq_cst_{0};
797 };
798
799 extern hazptr_stats hazptr_stats_;
800
801 inline hazptr_stats::~hazptr_stats() {
802   DEBUG_PRINT(this << " light " << light_.load());
803   DEBUG_PRINT(this << " heavy " << heavy_.load());
804   DEBUG_PRINT(this << " seq_cst " << seq_cst_.load());
805 }
806
807 FOLLY_ALWAYS_INLINE void hazptr_stats::light() {
808   if (HAZPTR_STATS) {
809     /* atomic */ ++light_;
810   }
811 }
812
813 inline void hazptr_stats::heavy() {
814   if (HAZPTR_STATS) {
815     /* atomic */ ++heavy_;
816   }
817 }
818
819 inline void hazptr_stats::seq_cst() {
820   if (HAZPTR_STATS) {
821     /* atomic */ ++seq_cst_;
822   }
823 }
824
825 /** hazptr_mb */
826
827 FOLLY_ALWAYS_INLINE void hazptr_mb::light() {
828   DEBUG_PRINT("");
829   if (HAZPTR_AMB) {
830     folly::asymmetricLightBarrier();
831     INC_HAZPTR_STATS(light);
832   } else {
833     atomic_thread_fence(std::memory_order_seq_cst);
834     INC_HAZPTR_STATS(seq_cst);
835   }
836 }
837
838 inline void hazptr_mb::heavy() {
839   DEBUG_PRINT("");
840   if (HAZPTR_AMB) {
841     folly::asymmetricHeavyBarrier(AMBFlags::EXPEDITED);
842     INC_HAZPTR_STATS(heavy);
843   } else {
844     atomic_thread_fence(std::memory_order_seq_cst);
845     INC_HAZPTR_STATS(seq_cst);
846   }
847 }
848
849 /**
850  *  TLS structures
851  */
852
853 /**
854  *  hazptr_tc structures
855  */
856
857 /** hazptr_tc_entry */
858
859 FOLLY_ALWAYS_INLINE void hazptr_tc_entry::fill(hazptr_rec* hprec) {
860   hprec_ = hprec;
861   DEBUG_PRINT(this << " " << hprec);
862 }
863
864 FOLLY_ALWAYS_INLINE hazptr_rec* hazptr_tc_entry::get() {
865   auto hprec = hprec_;
866   DEBUG_PRINT(this << " " << hprec);
867   return hprec;
868 }
869
870 inline void hazptr_tc_entry::evict() {
871   auto hprec = hprec_;
872   hprec->release();
873   DEBUG_PRINT(this << " " << hprec);
874 }
875
876 /** hazptr_tc */
877
878 FOLLY_ALWAYS_INLINE hazptr_tc_entry& hazptr_tc::operator[](size_t i) {
879   DCHECK(i <= HAZPTR_TC_SIZE);
880   return entry_[i];
881 }
882
883 FOLLY_ALWAYS_INLINE hazptr_rec* hazptr_tc::get() {
884   if (LIKELY(count_ != 0)) {
885     auto hprec = entry_[--count_].get();
886     DEBUG_PRINT(this << " " << hprec);
887     return hprec;
888   }
889   DEBUG_PRINT(this << " nullptr");
890   return nullptr;
891 }
892
893 FOLLY_ALWAYS_INLINE bool hazptr_tc::put(hazptr_rec* hprec) {
894   if (LIKELY(count_ < HAZPTR_TC_SIZE)) {
895     entry_[count_++].fill(hprec);
896     DEBUG_PRINT(this << " " << count_ - 1);
897     return true;
898   }
899   return false;
900 }
901
902 FOLLY_ALWAYS_INLINE size_t hazptr_tc::count() {
903   return count_;
904 }
905
906 /** hazptr_tc free functions */
907
908 FOLLY_ALWAYS_INLINE hazptr_tc* hazptr_tc_tls() {
909   DEBUG_PRINT(tls_state_);
910   if (LIKELY(tls_state_ == TLS_ALIVE)) {
911     DEBUG_PRINT(tls_state_);
912     return &tls_tc_data_;
913   } else if (tls_state_ == TLS_UNINITIALIZED) {
914     tls_life_odr_use();
915     return &tls_tc_data_;
916   }
917   return nullptr;
918 }
919
920 inline void hazptr_tc_init() {
921   DEBUG_PRINT("");
922   auto& tc = tls_tc_data_;
923   DEBUG_PRINT(&tc);
924   tc.count_ = 0;
925   if (kIsDebug) {
926     tc.local_ = false;
927   }
928 }
929
930 inline void hazptr_tc_shutdown() {
931   auto& tc = tls_tc_data_;
932   DEBUG_PRINT(&tc);
933   for (size_t i = 0; i < tc.count_; ++i) {
934     tc.entry_[i].evict();
935   }
936 }
937
938 FOLLY_ALWAYS_INLINE hazptr_rec* hazptr_tc_try_get() {
939   DEBUG_PRINT(TLS_UNINITIALIZED << TLS_ALIVE << TLS_DESTROYED);
940   DEBUG_PRINT(tls_state_);
941   if (LIKELY(tls_state_ == TLS_ALIVE)) {
942     DEBUG_PRINT(tls_state_);
943     return tls_tc_data_.get();
944   } else if (tls_state_ == TLS_UNINITIALIZED) {
945     tls_life_odr_use();
946     return tls_tc_data_.get();
947   }
948   return nullptr;
949 }
950
951 FOLLY_ALWAYS_INLINE bool hazptr_tc_try_put(hazptr_rec* hprec) {
952   DEBUG_PRINT(tls_state_);
953   if (LIKELY(tls_state_ == TLS_ALIVE)) {
954     DEBUG_PRINT(tls_state_);
955     return tls_tc_data_.put(hprec);
956   }
957   return false;
958 }
959
960 /**
961  *  hazptr_priv
962  */
963
964 inline void hazptr_priv::push(hazptr_obj* obj) {
965   auto& domain = default_hazptr_domain();
966   obj->next_ = nullptr;
967   if (tail_) {
968     tail_->next_ = obj;
969   } else {
970     if (!active_) {
971       domain.objRetire(obj);
972       return;
973     }
974     head_ = obj;
975   }
976   tail_ = obj;
977   ++rcount_;
978   if (domain.reachedThreshold(rcount_)) {
979     pushAllToDomain();
980   }
981 }
982
983 inline void hazptr_priv::pushAllToDomain() {
984   auto& domain = default_hazptr_domain();
985   domain.pushRetired(head_, tail_, rcount_);
986   head_ = nullptr;
987   tail_ = nullptr;
988   rcount_ = 0;
989   domain.tryBulkReclaim();
990 }
991
992 inline void hazptr_priv_init() {
993   auto& priv = tls_priv_data_;
994   DEBUG_PRINT(&priv);
995   priv.head_ = nullptr;
996   priv.tail_ = nullptr;
997   priv.rcount_ = 0;
998   priv.active_ = true;
999 }
1000
1001 inline void hazptr_priv_shutdown() {
1002   auto& priv = tls_priv_data_;
1003   DEBUG_PRINT(&priv);
1004   DCHECK(priv.active_);
1005   priv.active_ = false;
1006   if (priv.tail_) {
1007     priv.pushAllToDomain();
1008   }
1009 }
1010
1011 inline bool hazptr_priv_try_retire(hazptr_obj* obj) {
1012   DEBUG_PRINT(tls_state_);
1013   if (tls_state_ == TLS_ALIVE) {
1014     DEBUG_PRINT(tls_state_);
1015     tls_priv_data_.push(obj);
1016     return true;
1017   } else if (tls_state_ == TLS_UNINITIALIZED) {
1018     DEBUG_PRINT(tls_state_);
1019     tls_life_odr_use();
1020     tls_priv_data_.push(obj);
1021     return true;
1022   }
1023   return false;
1024 }
1025
1026 /** hazptr_tls_life */
1027
1028 inline void tls_life_odr_use() {
1029   DEBUG_PRINT(tls_state_);
1030   CHECK(tls_state_ == TLS_UNINITIALIZED);
1031   auto volatile tlsOdrUse = &tls_life_;
1032   CHECK(tlsOdrUse != nullptr);
1033   DEBUG_PRINT(tlsOdrUse);
1034 }
1035
1036 inline hazptr_tls_life::hazptr_tls_life() {
1037   DEBUG_PRINT(this);
1038   CHECK(tls_state_ == TLS_UNINITIALIZED);
1039   hazptr_tc_init();
1040   hazptr_priv_init();
1041   tls_state_ = TLS_ALIVE;
1042 }
1043
1044 inline hazptr_tls_life::~hazptr_tls_life() {
1045   DEBUG_PRINT(this);
1046   CHECK(tls_state_ == TLS_ALIVE);
1047   hazptr_tc_shutdown();
1048   hazptr_priv_shutdown();
1049   tls_state_ = TLS_DESTROYED;
1050 }
1051
1052 } // namespace hazptr
1053 } // namespace folly