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