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