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