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
10enum 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};
79typedef 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
90typedef struct witness_s witness_t;
91typedef ql_head(witness_t) witness_list_t;
92typedef int witness_comp_t (const witness_t *, void *, const witness_t *,
93 void *);
94
95struct 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/******************************************************************************/
122typedef struct witness_tsd_s witness_tsd_t;
123struct 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/******************************************************************************/
134typedef struct witness_tsdn_s witness_tsdn_t;
135struct witness_tsdn_s {
136 witness_tsd_t witness_tsd;
137};
138
139JEMALLOC_ALWAYS_INLINE witness_tsdn_t *
140witness_tsd_tsdn(witness_tsd_t *witness_tsd) {
141 return (witness_tsdn_t *)witness_tsd;
142}
143
144JEMALLOC_ALWAYS_INLINE bool
145witness_tsdn_null(witness_tsdn_t *witness_tsdn) {
146 return witness_tsdn == NULL;
147}
148
149JEMALLOC_ALWAYS_INLINE witness_tsd_t *
150witness_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/******************************************************************************/
158void witness_init(witness_t *witness, const char *name, witness_rank_t rank,
159 witness_comp_t *comp, void *opaque);
160
161typedef void (witness_lock_error_t)(const witness_list_t *, const witness_t *);
162extern witness_lock_error_t *JET_MUTABLE witness_lock_error;
163
164typedef void (witness_owner_error_t)(const witness_t *);
165extern witness_owner_error_t *JET_MUTABLE witness_owner_error;
166
167typedef void (witness_not_owner_error_t)(const witness_t *);
168extern witness_not_owner_error_t *JET_MUTABLE witness_not_owner_error;
169
170typedef void (witness_depth_error_t)(const witness_list_t *,
171 witness_rank_t rank_inclusive, unsigned depth);
172extern witness_depth_error_t *JET_MUTABLE witness_depth_error;
173
174void witnesses_cleanup(witness_tsd_t *witness_tsd);
175void witness_prefork(witness_tsd_t *witness_tsd);
176void witness_postfork_parent(witness_tsd_t *witness_tsd);
177void witness_postfork_child(witness_tsd_t *witness_tsd);
178
179/* Helper, not intended for direct use. */
180static inline bool
181witness_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
197static inline void
198witness_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
219static inline void
220witness_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. */
247static inline unsigned
248witness_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
265static inline void
266witness_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
280static inline void
281witness_assert_depth(witness_tsdn_t *witness_tsdn, unsigned depth) {
282 witness_assert_depth_to_rank(witness_tsdn, WITNESS_RANK_MIN, depth);
283}
284
285static inline void
286witness_assert_lockless(witness_tsdn_t *witness_tsdn) {
287 witness_assert_depth(witness_tsdn, 0);
288}
289
290static inline void
291witness_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
305static inline void
306witness_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
348static inline void
349witness_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