1 files changed, 378 insertions, 0 deletions
diff --git a/deps/jemalloc/include/jemalloc/internal/witness.h b/deps/jemalloc/include/jemalloc/internal/witness.h
new file mode 100644
index 0000000..e81b9a0
--- /dev/null
+++ b/deps/jemalloc/include/jemalloc/internal/witness.h
@@ -0,0 +1,378 @@
+#ifndef JEMALLOC_INTERNAL_WITNESS_H
+#define JEMALLOC_INTERNAL_WITNESS_H
+
+#include "jemalloc/internal/ql.h"
+
+/******************************************************************************/
+/* LOCK RANKS */
+/******************************************************************************/
+
+enum witness_rank_e {
+	/*
+	 * Order matters within this enum listing -- higher valued locks can
+	 * only be acquired after lower-valued ones.  We use the
+	 * auto-incrementing-ness of enum values to enforce this.
+	 */
+
+	/*
+	 * Witnesses with rank WITNESS_RANK_OMIT are completely ignored by the
+	 * witness machinery.
+	 */
+	WITNESS_RANK_OMIT,
+	WITNESS_RANK_MIN,
+	WITNESS_RANK_INIT = WITNESS_RANK_MIN,
+	WITNESS_RANK_CTL,
+	WITNESS_RANK_TCACHES,
+	WITNESS_RANK_ARENAS,
+	WITNESS_RANK_BACKGROUND_THREAD_GLOBAL,
+	WITNESS_RANK_PROF_DUMP,
+	WITNESS_RANK_PROF_BT2GCTX,
+	WITNESS_RANK_PROF_TDATAS,
+	WITNESS_RANK_PROF_TDATA,
+	WITNESS_RANK_PROF_LOG,
+	WITNESS_RANK_PROF_GCTX,
+	WITNESS_RANK_PROF_RECENT_DUMP,
+	WITNESS_RANK_BACKGROUND_THREAD,
+	/*
+	 * Used as an argument to witness_assert_depth_to_rank() in order to
+	 * validate depth excluding non-core locks with lower ranks.  Since the
+	 * rank argument to witness_assert_depth_to_rank() is inclusive rather
+	 * than exclusive, this definition can have the same value as the
+	 * minimally ranked core lock.
+	 */
+	WITNESS_RANK_CORE,
+	WITNESS_RANK_DECAY = WITNESS_RANK_CORE,
+	WITNESS_RANK_TCACHE_QL,
+
+	WITNESS_RANK_SEC_SHARD,
+
+	WITNESS_RANK_EXTENT_GROW,
+	WITNESS_RANK_HPA_SHARD_GROW = WITNESS_RANK_EXTENT_GROW,
+	WITNESS_RANK_SAN_BUMP_ALLOC = WITNESS_RANK_EXTENT_GROW,
+
+	WITNESS_RANK_EXTENTS,
+	WITNESS_RANK_HPA_SHARD = WITNESS_RANK_EXTENTS,
+
+	WITNESS_RANK_HPA_CENTRAL_GROW,
+	WITNESS_RANK_HPA_CENTRAL,
+
+	WITNESS_RANK_EDATA_CACHE,
+
+	WITNESS_RANK_RTREE,
+	WITNESS_RANK_BASE,
+	WITNESS_RANK_ARENA_LARGE,
+	WITNESS_RANK_HOOK,
+
+	WITNESS_RANK_LEAF=0x1000,
+	WITNESS_RANK_BIN = WITNESS_RANK_LEAF,
+	WITNESS_RANK_ARENA_STATS = WITNESS_RANK_LEAF,
+	WITNESS_RANK_COUNTER_ACCUM = WITNESS_RANK_LEAF,
+	WITNESS_RANK_DSS = WITNESS_RANK_LEAF,
+	WITNESS_RANK_PROF_ACTIVE = WITNESS_RANK_LEAF,
+	WITNESS_RANK_PROF_DUMP_FILENAME = WITNESS_RANK_LEAF,
+	WITNESS_RANK_PROF_GDUMP = WITNESS_RANK_LEAF,
+	WITNESS_RANK_PROF_NEXT_THR_UID = WITNESS_RANK_LEAF,
+	WITNESS_RANK_PROF_RECENT_ALLOC = WITNESS_RANK_LEAF,
+	WITNESS_RANK_PROF_STATS = WITNESS_RANK_LEAF,
+	WITNESS_RANK_PROF_THREAD_ACTIVE_INIT = WITNESS_RANK_LEAF,
+};
+typedef enum witness_rank_e witness_rank_t;
+
+/******************************************************************************/
+/* PER-WITNESS DATA */
+/******************************************************************************/
+#if defined(JEMALLOC_DEBUG)
+#  define WITNESS_INITIALIZER(name, rank) {name, rank, NULL, NULL, {NULL, NULL}}
+#else
+#  define WITNESS_INITIALIZER(name, rank)
+#endif
+
+typedef struct witness_s witness_t;
+typedef ql_head(witness_t) witness_list_t;
+typedef int witness_comp_t (const witness_t *, void *, const witness_t *,
+    void *);
+
+struct witness_s {
+	/* Name, used for printing lock order reversal messages. */
+	const char		*name;
+
+	/*
+	 * Witness rank, where 0 is lowest and WITNESS_RANK_LEAF is highest.
+	 * Witnesses must be acquired in order of increasing rank.
+	 */
+	witness_rank_t		rank;
+
+	/*
+	 * If two witnesses are of equal rank and they have the samp comp
+	 * function pointer, it is called as a last attempt to differentiate
+	 * between witnesses of equal rank.
+	 */
+	witness_comp_t		*comp;
+
+	/* Opaque data, passed to comp(). */
+	void			*opaque;
+
+	/* Linkage for thread's currently owned locks. */
+	ql_elm(witness_t)	link;
+};
+
+/******************************************************************************/
+/* PER-THREAD DATA */
+/******************************************************************************/
+typedef struct witness_tsd_s witness_tsd_t;
+struct witness_tsd_s {
+	witness_list_t witnesses;
+	bool forking;
+};
+
+#define WITNESS_TSD_INITIALIZER { ql_head_initializer(witnesses), false }
+#define WITNESS_TSDN_NULL ((witness_tsdn_t *)0)
+
+/******************************************************************************/
+/* (PER-THREAD) NULLABILITY HELPERS */
+/******************************************************************************/
+typedef struct witness_tsdn_s witness_tsdn_t;
+struct witness_tsdn_s {
+	witness_tsd_t witness_tsd;
+};
+
+JEMALLOC_ALWAYS_INLINE witness_tsdn_t *
+witness_tsd_tsdn(witness_tsd_t *witness_tsd) {
+	return (witness_tsdn_t *)witness_tsd;
+}
+
+JEMALLOC_ALWAYS_INLINE bool
+witness_tsdn_null(witness_tsdn_t *witness_tsdn) {
+	return witness_tsdn == NULL;
+}
+
+JEMALLOC_ALWAYS_INLINE witness_tsd_t *
+witness_tsdn_tsd(witness_tsdn_t *witness_tsdn) {
+	assert(!witness_tsdn_null(witness_tsdn));
+	return &witness_tsdn->witness_tsd;
+}
+
+/******************************************************************************/
+/* API */
+/******************************************************************************/
+void witness_init(witness_t *witness, const char *name, witness_rank_t rank,
+    witness_comp_t *comp, void *opaque);
+
+typedef void (witness_lock_error_t)(const witness_list_t *, const witness_t *);
+extern witness_lock_error_t *JET_MUTABLE witness_lock_error;
+
+typedef void (witness_owner_error_t)(const witness_t *);
+extern witness_owner_error_t *JET_MUTABLE witness_owner_error;
+
+typedef void (witness_not_owner_error_t)(const witness_t *);
+extern witness_not_owner_error_t *JET_MUTABLE witness_not_owner_error;
+
+typedef void (witness_depth_error_t)(const witness_list_t *,
+    witness_rank_t rank_inclusive, unsigned depth);
+extern witness_depth_error_t *JET_MUTABLE witness_depth_error;
+
+void witnesses_cleanup(witness_tsd_t *witness_tsd);
+void witness_prefork(witness_tsd_t *witness_tsd);
+void witness_postfork_parent(witness_tsd_t *witness_tsd);
+void witness_postfork_child(witness_tsd_t *witness_tsd);
+
+/* Helper, not intended for direct use. */
+static inline bool
+witness_owner(witness_tsd_t *witness_tsd, const witness_t *witness) {
+	witness_list_t *witnesses;
+	witness_t *w;
+
+	cassert(config_debug);
+
+	witnesses = &witness_tsd->witnesses;
+	ql_foreach(w, witnesses, link) {
+		if (w == witness) {
+			return true;
+		}
+	}
+
+	return false;
+}
+
+static inline void
+witness_assert_owner(witness_tsdn_t *witness_tsdn, const witness_t *witness) {
+	witness_tsd_t *witness_tsd;
+
+	if (!config_debug) {
+		return;
+	}
+
+	if (witness_tsdn_null(witness_tsdn)) {
+		return;
+	}
+	witness_tsd = witness_tsdn_tsd(witness_tsdn);
+	if (witness->rank == WITNESS_RANK_OMIT) {
+		return;
+	}
+
+	if (witness_owner(witness_tsd, witness)) {
+		return;
+	}
+	witness_owner_error(witness);
+}
+
+static inline void
+witness_assert_not_owner(witness_tsdn_t *witness_tsdn,
+    const witness_t *witness) {
+	witness_tsd_t *witness_tsd;
+	witness_list_t *witnesses;
+	witness_t *w;
+
+	if (!config_debug) {
+		return;
+	}
+
+	if (witness_tsdn_null(witness_tsdn)) {
+		return;
+	}
+	witness_tsd = witness_tsdn_tsd(witness_tsdn);
+	if (witness->rank == WITNESS_RANK_OMIT) {
+		return;
+	}
+
+	witnesses = &witness_tsd->witnesses;
+	ql_foreach(w, witnesses, link) {
+		if (w == witness) {
+			witness_not_owner_error(witness);
+		}
+	}
+}
+
+/* Returns depth.  Not intended for direct use. */
+static inline unsigned
+witness_depth_to_rank(witness_list_t *witnesses, witness_rank_t rank_inclusive)
+{
+	unsigned d = 0;
+	witness_t *w = ql_last(witnesses, link);
+
+	if (w != NULL) {
+		ql_reverse_foreach(w, witnesses, link) {
+			if (w->rank < rank_inclusive) {
+				break;
+			}
+			d++;
+		}
+	}
+
+	return d;
+}
+
+static inline void
+witness_assert_depth_to_rank(witness_tsdn_t *witness_tsdn,
+    witness_rank_t rank_inclusive, unsigned depth) {
+	if (!config_debug || witness_tsdn_null(witness_tsdn)) {
+		return;
+	}
+
+	witness_list_t *witnesses = &witness_tsdn_tsd(witness_tsdn)->witnesses;
+	unsigned d = witness_depth_to_rank(witnesses, rank_inclusive);
+
+	if (d != depth) {
+		witness_depth_error(witnesses, rank_inclusive, depth);
+	}
+}
+
+static inline void
+witness_assert_depth(witness_tsdn_t *witness_tsdn, unsigned depth) {
+	witness_assert_depth_to_rank(witness_tsdn, WITNESS_RANK_MIN, depth);
+}
+
+static inline void
+witness_assert_lockless(witness_tsdn_t *witness_tsdn) {
+	witness_assert_depth(witness_tsdn, 0);
+}
+
+static inline void
+witness_assert_positive_depth_to_rank(witness_tsdn_t *witness_tsdn,
+    witness_rank_t rank_inclusive) {
+	if (!config_debug || witness_tsdn_null(witness_tsdn)) {
+		return;
+	}
+
+	witness_list_t *witnesses = &witness_tsdn_tsd(witness_tsdn)->witnesses;
+	unsigned d = witness_depth_to_rank(witnesses, rank_inclusive);
+
+	if (d == 0) {
+		witness_depth_error(witnesses, rank_inclusive, 1);
+	}
+}
+
+static inline void
+witness_lock(witness_tsdn_t *witness_tsdn, witness_t *witness) {
+	witness_tsd_t *witness_tsd;
+	witness_list_t *witnesses;
+	witness_t *w;
+
+	if (!config_debug) {
+		return;
+	}
+
+	if (witness_tsdn_null(witness_tsdn)) {
+		return;
+	}
+	witness_tsd = witness_tsdn_tsd(witness_tsdn);
+	if (witness->rank == WITNESS_RANK_OMIT) {
+		return;
+	}
+
+	witness_assert_not_owner(witness_tsdn, witness);
+
+	witnesses = &witness_tsd->witnesses;
+	w = ql_last(witnesses, link);
+	if (w == NULL) {
+		/* No other locks; do nothing. */
+	} else if (witness_tsd->forking && w->rank <= witness->rank) {
+		/* Forking, and relaxed ranking satisfied. */
+	} else if (w->rank > witness->rank) {
+		/* Not forking, rank order reversal. */
+		witness_lock_error(witnesses, witness);
+	} else if (w->rank == witness->rank && (w->comp == NULL || w->comp !=
+	    witness->comp || w->comp(w, w->opaque, witness, witness->opaque) >
+	    0)) {
+		/*
+		 * Missing/incompatible comparison function, or comparison
+		 * function indicates rank order reversal.
+		 */
+		witness_lock_error(witnesses, witness);
+	}
+
+	ql_elm_new(witness, link);
+	ql_tail_insert(witnesses, witness, link);
+}
+
+static inline void
+witness_unlock(witness_tsdn_t *witness_tsdn, witness_t *witness) {
+	witness_tsd_t *witness_tsd;
+	witness_list_t *witnesses;
+
+	if (!config_debug) {
+		return;
+	}
+
+	if (witness_tsdn_null(witness_tsdn)) {
+		return;
+	}
+	witness_tsd = witness_tsdn_tsd(witness_tsdn);
+	if (witness->rank == WITNESS_RANK_OMIT) {
+		return;
+	}
+
+	/*
+	 * Check whether owner before removal, rather than relying on
+	 * witness_assert_owner() to abort, so that unit tests can test this
+	 * function's failure mode without causing undefined behavior.
+	 */
+	if (witness_owner(witness_tsd, witness)) {
+		witnesses = &witness_tsd->witnesses;
+		ql_remove(witnesses, witness, link);
+	} else {
+		witness_assert_owner(witness_tsdn, witness);
+	}
+}
+
+#endif /* JEMALLOC_INTERNAL_WITNESS_H */