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 | |