sys/kern/subr_witness.c

38  * Implementation of the `witness' lock verifier.  Originally implemented for
44  *	Main Entry: witness
48  *	    testimony, witness, from 2wit
58  *	      religious faith or conviction <the heroic witness to divine
160  * These flags go in the witness relationship matrix and describe the
161  * relationship between any two struct witness objects.
191  * it is held by witness.  For example, a lock instance will hold the
219  * The main witness structure. One of these per named lock type in the system
222 struct witness {
226 	STAILQ_ENTRY(witness) 	w_list;		/* List of all witnesses. */
227 	STAILQ_ENTRY(witness) 	w_typelist;	/* Witnesses of a type. */
228 	struct witness		*w_hash_next; /* Linked list in hash buckets. */
241 STAILQ_HEAD(witness_list, witness);
244  * The witness hash table. Keys are witness names (const char *), elements are
245  * witness objects (struct witness *).
248 	struct witness	*wh_array[WITNESS_HASH_SIZE];
268  * The witness lock order data hash table. Keys are witness index tuples
298 witness_lock_type_equal(struct witness *w1, struct witness *w2)
313 static int	_isitmyx(struct witness *w1, struct witness *w2, int rmask,
315 static void	adopt(struct witness *parent, struct witness *child);
316 static int	blessed(struct witness *, struct witness *);
317 static void	depart(struct witness *w);
318 static struct witness	*enroll(const char *description,
322 static int	isitmychild(struct witness *parent, struct witness *child);
323 static int	isitmydescendant(struct witness *parent, struct witness *child);
324 static void	itismychild(struct witness *parent, struct witness *child);
329 static void	witness_add_fullgraph(struct sbuf *sb, struct witness *parent);
334 		    struct witness *, int indent);
337 static void	witness_ddb_level_descendants(struct witness *parent, int l);
341 static void	witness_free(struct witness *m);
342 static struct witness	*witness_get(void);
344 static struct witness	*witness_hash_get(const char *key);
345 static void	witness_hash_put(struct witness *w);
350 static int	witness_lock_order_add(struct witness *parent,
351 		    struct witness *child);
352 static int	witness_lock_order_check(struct witness *parent,
353 		    struct witness *child);
355 					    struct witness *parent,
356 					    struct witness *child);
363 static SYSCTL_NODE(_debug, OID_AUTO, witness, CTLFLAG_RW, NULL,
368  * witness is completely disabled.  Otherwise witness performs full
370  * may be toggled.  However, witness cannot be reenabled once it is
375     sysctl_debug_witness_watch, "I", "witness is watching lock operations");
417  * Output channel for witness messages.  By default we print to the console.
437  * Call this to print out the witness faulty stacks.
440     NULL, 0, sysctl_debug_witness_badstacks, "A", "Show bad witness stacks");
463 static struct witness *w_data;
466 static struct witness_hash w_hash;	/* The witness hash table. */
745  * This global is set to 0 once it becomes safe to use the witness code.
768  * Calculate the size of early witness structures.
775 	sz = sizeof(struct witness) * witness_count;
784  * The WITNESS-enabled diagnostic code.  Note that the witness code does
793 	struct witness *w, *w1;
799 	p += sizeof(struct witness) * witness_count;
811 	 * We have to release Giant before initializing its witness
817 	CTR1(KTR_WITNESS, "%s: initializing witness", __func__);
818 	mtx_init(&w_mtx, "witness lock", NULL, MTX_SPIN | MTX_QUIET |
827 	    ("%s: Invalid list of free witness objects", __func__));
859 	/* Iterate through all locks and add them to witness. */
869 	/* Mark the witness code as being ready for use. */
920 	struct witness *w;
946 	struct witness *w;
959 		/* If the witness has ancestors (is not a root), skip it. */
967 witness_ddb_level_descendants(struct witness *w, int l)
985     struct witness *w, int indent)
1019 	struct witness *w;
1035 	struct witness *w;
1083 	/* Require locks that witness knows about. */
1116 	struct witness *w, *w1;
1293 			 * If this lock doesn't undergo witness checking,
1299 				    ("lock missing witness structure"));
1396 			 * witness w in our list.
1459 	struct witness *w;
1486 	/* Update per-witness last file and line acquire. */
1694 	 * free witness pool (and subsequent locking) is avoided.
1821 	struct witness *w;
1832 	struct witness *w;
1840 static struct witness *
1843 	struct witness *w;
1877 	/* Insert new witness into the hash */
1896 depart(struct witness *w)
1915 adopt(struct witness *parent, struct witness *child)
1988 				printf("witness rmatrix paradox! [%d][%d]=%d "
1997 				printf("witness rmatrix paradox! [%d][%d]=%d "
2009 itismychild(struct witness *parent, struct witness *child)
2040 _isitmyx(struct witness *w1, struct witness *w2, int rmask, const char *fname)
2074 isitmychild(struct witness *parent, struct witness *child)
2084 isitmydescendant(struct witness *ancestor, struct witness *descendant)
2092 blessed(struct witness *w1, struct witness *w2)
2111 static struct witness *
2114 	struct witness *w;
2127 		printf("WITNESS: unable to allocate a new witness object\n");
2144 witness_free(struct witness *w)
2163 		printf("%s: witness exhausted\n", __func__);
2562 DB_SHOW_COMMAND(witness, db_witness_display)
2573 	struct witness *tmp_w1, *tmp_w2, *w1, *w2;
2582 	tmp_w1 = malloc(sizeof(struct witness), M_TEMP, M_WAITOK | M_ZERO);
2583 	tmp_w2 = malloc(sizeof(struct witness), M_TEMP, M_WAITOK | M_ZERO);
2790 	struct witness *w;
2850 witness_add_fullgraph(struct sbuf *sb, struct witness *w)
2893  * Initializes the two witness hash tables. Called exactly once from
2923 static struct witness *
2926 	struct witness *w;
2945 witness_hash_put(struct witness *w)
2966 witness_lock_order_get(struct witness *parent, struct witness *child)
3000 witness_lock_order_check(struct witness *parent, struct witness *child)
3013 witness_lock_order_add(struct witness *parent, struct witness *child)
3044 /* Call this whenever the structure of the witness graph changes. */