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 *
witness_tsd_tsdn(witness_tsd_t * witness_tsd)125 witness_tsd_tsdn(witness_tsd_t *witness_tsd) {
126 return (witness_tsdn_t *)witness_tsd;
127 }
128
129 JEMALLOC_ALWAYS_INLINE bool
witness_tsdn_null(witness_tsdn_t * witness_tsdn)130 witness_tsdn_null(witness_tsdn_t *witness_tsdn) {
131 return witness_tsdn == NULL;
132 }
133
134 JEMALLOC_ALWAYS_INLINE witness_tsd_t *
witness_tsdn_tsd(witness_tsdn_t * witness_tsdn)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
witness_owner(witness_tsd_t * witness_tsd,const witness_t * witness)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
witness_assert_owner(witness_tsdn_t * witness_tsdn,const witness_t * witness)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
witness_assert_not_owner(witness_tsdn_t * witness_tsdn,const witness_t * witness)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
witness_assert_depth_to_rank(witness_tsdn_t * witness_tsdn,witness_rank_t rank_inclusive,unsigned depth)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
witness_assert_depth(witness_tsdn_t * witness_tsdn,unsigned depth)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
witness_assert_lockless(witness_tsdn_t * witness_tsdn)270 witness_assert_lockless(witness_tsdn_t *witness_tsdn) {
271 witness_assert_depth(witness_tsdn, 0);
272 }
273
274 static inline void
witness_lock(witness_tsdn_t * witness_tsdn,witness_t * witness)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
witness_unlock(witness_tsdn_t * witness_tsdn,witness_t * witness)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