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#include <folly/synchronization/HazptrDomain.h>
20#include <folly/synchronization/HazptrHolder.h>
21#include <folly/synchronization/HazptrObj.h>
22#include <folly/synchronization/HazptrObjLinked.h>
23#include <folly/synchronization/HazptrRec.h>
24#include <folly/synchronization/HazptrThrLocal.h>
25
26/// Hazard pointers is a safe reclamation method. It protects objects
27/// from being reclaimed while being accessed by one or more threads, but
28/// allows objects to be removed concurrently while being accessed.
29///
30/// What is a Hazard Pointer?
31/// -------------------------
32/// A hazard pointer is a single-writer multi-reader pointer that can
33/// be owned by at most one thread at a time. To protect an object A
34/// from being reclaimed while in use, a thread X sets one of its
35/// owned hazard pointers, P, to the address of A. If P is set to &A
36/// before A is removed (i.e., it becomes unreachable) then A will not be
37/// reclaimed as long as P continues to hold the value &A.
38///
39/// Why use hazard pointers?
40/// ------------------------
41/// - Speed and scalability.
42/// - Can be used while blocking.
43///
44/// When not to use hazard pointers?
45/// --------------------------------
46/// - When thread local data is not supported efficiently.
47///
48/// Basic Interface
49/// ---------------
50/// - In the hazptr library, raw hazard pointers are not exposed to
51/// users. Instead, each instance of the class hazptr_holder owns
52/// and manages at most one hazard pointer.
53/// - Typically classes of objects protected by hazard pointers are
54/// derived from a class template hazptr_obj_base that provides a
55/// member function retire(). When an object A is removed,
56/// A.retire() is called to pass responsibility for reclaiming A to
57/// the hazptr library. A will be reclaimed only after it is not
58/// protected by hazard pointers.
59/// - The essential components of the hazptr API are:
60/// o hazptr_holder: Class that owns and manages a hazard pointer.
61/// o get_protected: Mmember function of hazptr_holder. Protects
62/// an object pointed to by an atomic source (if not null).
63/// T* get_protected(const atomic<T*>& src);
64/// o hazptr_obj_base<T>: Base class for protected objects.
65/// o retire: Member function of hazptr_obj_base that automatically
66/// reclaims the object when safe.
67/// void retire();
68///
69/// Default Domain and Default Deleters
70/// -----------------------------------
71/// - Most uses do not need to specify custom domains and custom
72/// deleters, and by default use the default domain and default
73/// deleters.
74///
75/// Simple usage example
76/// --------------------
77/// class Config : public hazptr_obj_base<Config> {
78/// /* ... details ... */
79/// U get_config(V v);
80/// };
81///
82/// std::atomic<Config*> config_;
83///
84/// // Called frequently
85/// U get_config(V v) {
86/// hazptr_holder h; /* h owns a hazard pointer */
87/// Config* ptr = h.get_protected(config_);
88/// /* safe to access *ptr as long as it is protected by h */
89/// return ptr->get_config(v);
90/// /* h dtor resets and releases the owned hazard pointer,
91/// *ptr will be no longer protected by this hazard pointer */
92/// }
93///
94/// // called rarely
95/// void update_config(Config* new_config) {
96/// Config* ptr = config_.exchange(new_config);
97/// ptr->retire() // Member function of hazptr_obj_base<Config>
98/// }
99///
100/// Optimized Holders
101/// -----------------
102/// - The template hazptr_array<M> provides most of the functionality
103/// of M hazptr_holder-s but with faster construction/destruction
104/// (for M > 1), at the cost of restrictions (on move and swap).
105/// - The template hazptr_local<M> provides greater speed even when
106/// M=1 (~2 ns vs ~5 ns for construction/destruction) but it is
107/// unsafe for the current thread to construct any other holder-type
108/// objects (hazptr_holder, hazptr_array and other hazptr_local)
109/// while the current instance exists.
110/// - In the above example, if Config::get_config() and all of its
111/// descendants are guaranteed not to use hazard pointers, then it
112/// can be faster (by ~3 ns.) to use
113/// hazptr_local<1> h;
114/// Config* ptr = h[0].get_protected(config_);
115/// than
116/// hazptr_holder h;
117/// Config* ptr = h.get_protected(config_);
118///
119/// Memory Usage
120/// ------------
121/// - The size of the metadata for the hazptr library is linear in the
122/// number of threads using hazard pointers, assuming a constant
123/// number of hazard pointers per thread, which is typical.
124/// - The typical number of reclaimable but not yet reclaimed of
125/// objects is linear in the number of hazard pointers, which
126/// typically is linear in the number of threads using hazard
127/// pointers.
128///
129/// Protecting Linked Structures and Automatic Retirement
130/// -----------------------------------------------------
131/// Hazard pointers provide link counting API to protect linked
132/// structures. It is capable of automatic retirement of objects even
133/// when the removal of objects is uncertain. It also supports
134/// optimizations when links are known to be immutable. All the link
135/// counting features incur no extra overhead for readers.
136/// See HazptrObjLinked.h for more details.
137///
138/// Alternative Safe Reclamation Methods
139/// ------------------------------------
140/// - Locking (exclusive or shared):
141/// o Pros: simple to reason about.
142/// o Cons: serialization, high reader overhead, high contention, deadlock.
143/// o When to use: When speed and contention are not critical, and
144/// when deadlock avoidance is simple.
145/// - Reference counting (atomic shared_ptr):
146/// o Pros: automatic reclamation, thread-anonymous, independent of
147/// support for thread local data, immune to deadlock.
148/// o Cons: high reader (and writer) overhead, high reader (and
149/// writer) contention.
150/// o When to use: When thread local support is lacking and deadlock
151/// can be a problem, or automatic reclamation is needed.
152/// - Read-copy-update (RCU):
153/// o Pros: simple, fast, scalable.
154/// o Cons: sensitive to blocking
155/// o When to use: When speed and scalability are important and
156/// objects do not need to be protected while blocking.
157///
158/// Hazard Pointers vs RCU
159/// ----------------------
160/// - The differences between hazard pointers and RCU boil down to
161/// that hazard pointers protect specific objects, whereas RCU
162/// sections protect all protectable objects.
163/// - Both have comparably low overheads for protection (i.e. reading
164/// or traversal) in the order of low nanoseconds.
165/// - Both support effectively perfect scalability of object
166/// protection by read-only operations (barring other factors).
167/// - Both rely on thread local data for performance.
168/// - Hazard pointers can protect objects while blocking
169/// indefinitely. Hazard pointers only prevent the reclamation of
170/// the objects they are protecting.
171/// - RCU sections do not allow indefinite blocking, because RCU
172/// prevents the reclamation of all protectable objects, which
173/// otherwise would lead to deadlock and/or running out of memory.
174/// - Hazard pointers can support end-to-end lock-free operations,
175/// including updates (provided lock-free allocator), regardless of
176/// thread delays and scheduling constraints.
177/// - RCU can support wait-free read operations, but reclamation of
178/// unbounded objects can be delayed for as long as a single thread
179/// is delayed.
180/// - The number of unreclaimed objects is bounded when protected by
181/// hazard pointers, but is unbounded when protected by RCU.
182/// - RCU is simpler to use than hazard pointers (except for the
183/// blocking and deadlock issues mentioned above). Hazard pointers
184/// need to identify protected objects, whereas RCU does not need to
185/// because it protects all protectable objects.
186/// - Both can protect linked structures. Hazard pointers needs
187/// additional link counting with low or moderate overhead for
188/// update operations, and no overhead for readers. RCU protects
189/// protects linked structures automatically, because it protects
190/// everything.
191///
192/// Differences from the Standard Proposal
193/// --------------------------------------
194/// - The latest standard proposal is in wg21.link/p0566.
195/// - This library's API differs from the standard proposal because:
196/// (a) the standard proposal is changing based on committee
197/// feedback, and (b) this library provides additional
198/// fast-evolving features based on usage experience that do not
199/// have corressponding proposed standard wording.
200/// - The main differences are:
201/// o This library uses an extra atomic template parameter for
202/// testing and debugging.
203/// o This library does not support a custom polymorphic allocator
204/// (C++17) parameter for the hazptr_domain constructor, until
205/// such support becomes widely available.
206/// o The construction of empty and non-empty hazptr_holder-s are
207/// reversed. This library will conform eventually.
208/// o hazptr_holder member functions get_protected and reset are
209/// called protect and reset_protected, respectively, in the
210/// latest proposal. Will conform eventually.
211/// o hazptr_array and hazptr_local are not part of the standard
212/// proposal.
213/// o Link counting support and protection of linked structures is
214/// not part of the current standard proposal.
215