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