contrib/jemalloc/include/jemalloc/internal/witness.h

   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 */