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 * 125 witness_tsd_tsdn(witness_tsd_t *witness_tsd) { 126 return (witness_tsdn_t *)witness_tsd; 127 } 128 129 JEMALLOC_ALWAYS_INLINE bool 130 witness_tsdn_null(witness_tsdn_t *witness_tsdn) { 131 return witness_tsdn == NULL; 132 } 133 134 JEMALLOC_ALWAYS_INLINE witness_tsd_t * 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 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 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 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 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 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 270 witness_assert_lockless(witness_tsdn_t *witness_tsdn) { 271 witness_assert_depth(witness_tsdn, 0); 272 } 273 274 static inline void 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 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