1 | #ifndef JEMALLOC_INTERNAL_WITNESS_H |
2 | #define JEMALLOC_INTERNAL_WITNESS_H |
3 | |
4 | #include "jemalloc/internal/ql.h" |
5 | |
6 | /******************************************************************************/ |
7 | /* LOCK RANKS */ |
8 | /******************************************************************************/ |
9 | |
10 | /* |
11 | * Witnesses with rank WITNESS_RANK_OMIT are completely ignored by the witness |
12 | * machinery. |
13 | */ |
14 | |
15 | #define WITNESS_RANK_OMIT 0U |
16 | |
17 | #define WITNESS_RANK_MIN 1U |
18 | |
19 | #define WITNESS_RANK_INIT 1U |
20 | #define WITNESS_RANK_CTL 1U |
21 | #define WITNESS_RANK_TCACHES 2U |
22 | #define WITNESS_RANK_ARENAS 3U |
23 | |
24 | #define WITNESS_RANK_BACKGROUND_THREAD_GLOBAL 4U |
25 | |
26 | #define WITNESS_RANK_PROF_DUMP 5U |
27 | #define WITNESS_RANK_PROF_BT2GCTX 6U |
28 | #define WITNESS_RANK_PROF_TDATAS 7U |
29 | #define WITNESS_RANK_PROF_TDATA 8U |
30 | #define WITNESS_RANK_PROF_LOG 9U |
31 | #define WITNESS_RANK_PROF_GCTX 10U |
32 | #define WITNESS_RANK_BACKGROUND_THREAD 11U |
33 | |
34 | /* |
35 | * Used as an argument to witness_assert_depth_to_rank() in order to validate |
36 | * depth excluding non-core locks with lower ranks. Since the rank argument to |
37 | * witness_assert_depth_to_rank() is inclusive rather than exclusive, this |
38 | * definition can have the same value as the minimally ranked core lock. |
39 | */ |
40 | #define WITNESS_RANK_CORE 12U |
41 | |
42 | #define WITNESS_RANK_DECAY 12U |
43 | #define WITNESS_RANK_TCACHE_QL 13U |
44 | #define WITNESS_RANK_EXTENT_GROW 14U |
45 | #define WITNESS_RANK_EXTENTS 15U |
46 | #define WITNESS_RANK_EXTENT_AVAIL 16U |
47 | |
48 | #define WITNESS_RANK_EXTENT_POOL 17U |
49 | #define WITNESS_RANK_RTREE 18U |
50 | #define WITNESS_RANK_BASE 19U |
51 | #define WITNESS_RANK_ARENA_LARGE 20U |
52 | #define WITNESS_RANK_HOOK 21U |
53 | |
54 | #define WITNESS_RANK_LEAF 0xffffffffU |
55 | #define WITNESS_RANK_BIN WITNESS_RANK_LEAF |
56 | #define WITNESS_RANK_ARENA_STATS WITNESS_RANK_LEAF |
57 | #define WITNESS_RANK_DSS WITNESS_RANK_LEAF |
58 | #define WITNESS_RANK_PROF_ACTIVE WITNESS_RANK_LEAF |
59 | #define WITNESS_RANK_PROF_ACCUM WITNESS_RANK_LEAF |
60 | #define WITNESS_RANK_PROF_DUMP_SEQ WITNESS_RANK_LEAF |
61 | #define WITNESS_RANK_PROF_GDUMP WITNESS_RANK_LEAF |
62 | #define WITNESS_RANK_PROF_NEXT_THR_UID WITNESS_RANK_LEAF |
63 | #define WITNESS_RANK_PROF_THREAD_ACTIVE_INIT WITNESS_RANK_LEAF |
64 | |
65 | /******************************************************************************/ |
66 | /* PER-WITNESS DATA */ |
67 | /******************************************************************************/ |
68 | #if defined(JEMALLOC_DEBUG) |
69 | # define WITNESS_INITIALIZER(name, rank) {name, rank, NULL, NULL, {NULL, NULL}} |
70 | #else |
71 | # define WITNESS_INITIALIZER(name, rank) |
72 | #endif |
73 | |
74 | typedef struct witness_s witness_t; |
75 | typedef unsigned witness_rank_t; |
76 | typedef ql_head(witness_t) witness_list_t; |
77 | typedef int witness_comp_t (const witness_t *, void *, const witness_t *, |
78 | void *); |
79 | |
80 | struct witness_s { |
81 | /* Name, used for printing lock order reversal messages. */ |
82 | const char *name; |
83 | |
84 | /* |
85 | * Witness rank, where 0 is lowest and UINT_MAX is highest. Witnesses |
86 | * must be acquired in order of increasing rank. |
87 | */ |
88 | witness_rank_t rank; |
89 | |
90 | /* |
91 | * If two witnesses are of equal rank and they have the samp comp |
92 | * function pointer, it is called as a last attempt to differentiate |
93 | * between witnesses of equal rank. |
94 | */ |
95 | witness_comp_t *comp; |
96 | |
97 | /* Opaque data, passed to comp(). */ |
98 | void *opaque; |
99 | |
100 | /* Linkage for thread's currently owned locks. */ |
101 | ql_elm(witness_t) link; |
102 | }; |
103 | |
104 | /******************************************************************************/ |
105 | /* PER-THREAD DATA */ |
106 | /******************************************************************************/ |
107 | typedef struct witness_tsd_s witness_tsd_t; |
108 | struct witness_tsd_s { |
109 | witness_list_t witnesses; |
110 | bool forking; |
111 | }; |
112 | |
113 | #define WITNESS_TSD_INITIALIZER { ql_head_initializer(witnesses), false } |
114 | #define WITNESS_TSDN_NULL ((witness_tsdn_t *)0) |
115 | |
116 | /******************************************************************************/ |
117 | /* (PER-THREAD) NULLABILITY HELPERS */ |
118 | /******************************************************************************/ |
119 | typedef struct witness_tsdn_s witness_tsdn_t; |
120 | struct witness_tsdn_s { |
121 | witness_tsd_t witness_tsd; |
122 | }; |
123 | |
124 | JEMALLOC_ALWAYS_INLINE witness_tsdn_t * |
125 | witness_tsd_tsdn(witness_tsd_t *witness_tsd) { |
126 | return (witness_tsdn_t *)witness_tsd; |
127 | } |
128 | |
129 | JEMALLOC_ALWAYS_INLINE bool |
130 | witness_tsdn_null(witness_tsdn_t *witness_tsdn) { |
131 | return witness_tsdn == NULL; |
132 | } |
133 | |
134 | JEMALLOC_ALWAYS_INLINE witness_tsd_t * |
135 | witness_tsdn_tsd(witness_tsdn_t *witness_tsdn) { |
136 | assert(!witness_tsdn_null(witness_tsdn)); |
137 | return &witness_tsdn->witness_tsd; |
138 | } |
139 | |
140 | /******************************************************************************/ |
141 | /* API */ |
142 | /******************************************************************************/ |
143 | void witness_init(witness_t *witness, const char *name, witness_rank_t rank, |
144 | witness_comp_t *comp, void *opaque); |
145 | |
146 | typedef void (witness_lock_error_t)(const witness_list_t *, const witness_t *); |
147 | extern witness_lock_error_t *JET_MUTABLE witness_lock_error; |
148 | |
149 | typedef void (witness_owner_error_t)(const witness_t *); |
150 | extern witness_owner_error_t *JET_MUTABLE witness_owner_error; |
151 | |
152 | typedef void (witness_not_owner_error_t)(const witness_t *); |
153 | extern witness_not_owner_error_t *JET_MUTABLE witness_not_owner_error; |
154 | |
155 | typedef void (witness_depth_error_t)(const witness_list_t *, |
156 | witness_rank_t rank_inclusive, unsigned depth); |
157 | extern witness_depth_error_t *JET_MUTABLE witness_depth_error; |
158 | |
159 | void witnesses_cleanup(witness_tsd_t *witness_tsd); |
160 | void witness_prefork(witness_tsd_t *witness_tsd); |
161 | void witness_postfork_parent(witness_tsd_t *witness_tsd); |
162 | void witness_postfork_child(witness_tsd_t *witness_tsd); |
163 | |
164 | /* Helper, not intended for direct use. */ |
165 | static inline bool |
166 | witness_owner(witness_tsd_t *witness_tsd, const witness_t *witness) { |
167 | witness_list_t *witnesses; |
168 | witness_t *w; |
169 | |
170 | cassert(config_debug); |
171 | |
172 | witnesses = &witness_tsd->witnesses; |
173 | ql_foreach(w, witnesses, link) { |
174 | if (w == witness) { |
175 | return true; |
176 | } |
177 | } |
178 | |
179 | return false; |
180 | } |
181 | |
182 | static inline void |
183 | witness_assert_owner(witness_tsdn_t *witness_tsdn, const witness_t *witness) { |
184 | witness_tsd_t *witness_tsd; |
185 | |
186 | if (!config_debug) { |
187 | return; |
188 | } |
189 | |
190 | if (witness_tsdn_null(witness_tsdn)) { |
191 | return; |
192 | } |
193 | witness_tsd = witness_tsdn_tsd(witness_tsdn); |
194 | if (witness->rank == WITNESS_RANK_OMIT) { |
195 | return; |
196 | } |
197 | |
198 | if (witness_owner(witness_tsd, witness)) { |
199 | return; |
200 | } |
201 | witness_owner_error(witness); |
202 | } |
203 | |
204 | static inline void |
205 | witness_assert_not_owner(witness_tsdn_t *witness_tsdn, |
206 | const witness_t *witness) { |
207 | witness_tsd_t *witness_tsd; |
208 | witness_list_t *witnesses; |
209 | witness_t *w; |
210 | |
211 | if (!config_debug) { |
212 | return; |
213 | } |
214 | |
215 | if (witness_tsdn_null(witness_tsdn)) { |
216 | return; |
217 | } |
218 | witness_tsd = witness_tsdn_tsd(witness_tsdn); |
219 | if (witness->rank == WITNESS_RANK_OMIT) { |
220 | return; |
221 | } |
222 | |
223 | witnesses = &witness_tsd->witnesses; |
224 | ql_foreach(w, witnesses, link) { |
225 | if (w == witness) { |
226 | witness_not_owner_error(witness); |
227 | } |
228 | } |
229 | } |
230 | |
231 | static inline void |
232 | witness_assert_depth_to_rank(witness_tsdn_t *witness_tsdn, |
233 | witness_rank_t rank_inclusive, unsigned depth) { |
234 | witness_tsd_t *witness_tsd; |
235 | unsigned d; |
236 | witness_list_t *witnesses; |
237 | witness_t *w; |
238 | |
239 | if (!config_debug) { |
240 | return; |
241 | } |
242 | |
243 | if (witness_tsdn_null(witness_tsdn)) { |
244 | return; |
245 | } |
246 | witness_tsd = witness_tsdn_tsd(witness_tsdn); |
247 | |
248 | d = 0; |
249 | witnesses = &witness_tsd->witnesses; |
250 | w = ql_last(witnesses, link); |
251 | if (w != NULL) { |
252 | ql_reverse_foreach(w, witnesses, link) { |
253 | if (w->rank < rank_inclusive) { |
254 | break; |
255 | } |
256 | d++; |
257 | } |
258 | } |
259 | if (d != depth) { |
260 | witness_depth_error(witnesses, rank_inclusive, depth); |
261 | } |
262 | } |
263 | |
264 | static inline void |
265 | witness_assert_depth(witness_tsdn_t *witness_tsdn, unsigned depth) { |
266 | witness_assert_depth_to_rank(witness_tsdn, WITNESS_RANK_MIN, depth); |
267 | } |
268 | |
269 | static inline void |
270 | witness_assert_lockless(witness_tsdn_t *witness_tsdn) { |
271 | witness_assert_depth(witness_tsdn, 0); |
272 | } |
273 | |
274 | static inline void |
275 | witness_lock(witness_tsdn_t *witness_tsdn, witness_t *witness) { |
276 | witness_tsd_t *witness_tsd; |
277 | witness_list_t *witnesses; |
278 | witness_t *w; |
279 | |
280 | if (!config_debug) { |
281 | return; |
282 | } |
283 | |
284 | if (witness_tsdn_null(witness_tsdn)) { |
285 | return; |
286 | } |
287 | witness_tsd = witness_tsdn_tsd(witness_tsdn); |
288 | if (witness->rank == WITNESS_RANK_OMIT) { |
289 | return; |
290 | } |
291 | |
292 | witness_assert_not_owner(witness_tsdn, witness); |
293 | |
294 | witnesses = &witness_tsd->witnesses; |
295 | w = ql_last(witnesses, link); |
296 | if (w == NULL) { |
297 | /* No other locks; do nothing. */ |
298 | } else if (witness_tsd->forking && w->rank <= witness->rank) { |
299 | /* Forking, and relaxed ranking satisfied. */ |
300 | } else if (w->rank > witness->rank) { |
301 | /* Not forking, rank order reversal. */ |
302 | witness_lock_error(witnesses, witness); |
303 | } else if (w->rank == witness->rank && (w->comp == NULL || w->comp != |
304 | witness->comp || w->comp(w, w->opaque, witness, witness->opaque) > |
305 | 0)) { |
306 | /* |
307 | * Missing/incompatible comparison function, or comparison |
308 | * function indicates rank order reversal. |
309 | */ |
310 | witness_lock_error(witnesses, witness); |
311 | } |
312 | |
313 | ql_elm_new(witness, link); |
314 | ql_tail_insert(witnesses, witness, link); |
315 | } |
316 | |
317 | static inline void |
318 | witness_unlock(witness_tsdn_t *witness_tsdn, witness_t *witness) { |
319 | witness_tsd_t *witness_tsd; |
320 | witness_list_t *witnesses; |
321 | |
322 | if (!config_debug) { |
323 | return; |
324 | } |
325 | |
326 | if (witness_tsdn_null(witness_tsdn)) { |
327 | return; |
328 | } |
329 | witness_tsd = witness_tsdn_tsd(witness_tsdn); |
330 | if (witness->rank == WITNESS_RANK_OMIT) { |
331 | return; |
332 | } |
333 | |
334 | /* |
335 | * Check whether owner before removal, rather than relying on |
336 | * witness_assert_owner() to abort, so that unit tests can test this |
337 | * function's failure mode without causing undefined behavior. |
338 | */ |
339 | if (witness_owner(witness_tsd, witness)) { |
340 | witnesses = &witness_tsd->witnesses; |
341 | ql_remove(witnesses, witness, link); |
342 | } else { |
343 | witness_assert_owner(witness_tsdn, witness); |
344 | } |
345 | } |
346 | |
347 | #endif /* JEMALLOC_INTERNAL_WITNESS_H */ |
348 | |