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