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