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
161  * These flags go in the witness relationship matrix and describe the
162  * relationship between any two struct witness objects.
192  * it is held by witness.  For example, a lock instance will hold the
220  * The main witness structure. One of these per named lock type in the system
223 struct witness {
227 	STAILQ_ENTRY(witness) 	w_list;		/* List of all witnesses. */
228 	STAILQ_ENTRY(witness) 	w_typelist;	/* Witnesses of a type. */
229 	struct witness		*w_hash_next; /* Linked list in hash buckets. */
242 STAILQ_HEAD(witness_list, witness);
245  * The witness hash table. Keys are witness names (const char *), elements are
246  * witness objects (struct witness *).
249 	struct witness	*wh_array[WITNESS_HASH_SIZE];
269  * The witness lock order data hash table. Keys are witness index tuples
299 witness_lock_type_equal(struct witness *w1, struct witness *w2)
314 static int	_isitmyx(struct witness *w1, struct witness *w2, int rmask,
316 static void	adopt(struct witness *parent, struct witness *child);
317 static int	blessed(struct witness *, struct witness *);
318 static void	depart(struct witness *w);
319 static struct witness	*enroll(const char *description,
323 static int	isitmychild(struct witness *parent, struct witness *child);
324 static int	isitmydescendant(struct witness *parent, struct witness *child);
325 static void	itismychild(struct witness *parent, struct witness *child);
330 static void	witness_add_fullgraph(struct sbuf *sb, struct witness *parent);
335 		    struct witness *, int indent);
338 static void	witness_ddb_level_descendants(struct witness *parent, int l);
343 static void	witness_free(struct witness *m);
344 static struct witness	*witness_get(void);
346 static struct witness	*witness_hash_get(const char *key);
347 static void	witness_hash_put(struct witness *w);
352 static int	witness_lock_order_add(struct witness *parent,
353 		    struct witness *child);
354 static int	witness_lock_order_check(struct witness *parent,
355 		    struct witness *child);
357 					    struct witness *parent,
358 					    struct witness *child);
367 FEATURE(witness, "kernel has witness(9) support");
369 static SYSCTL_NODE(_debug, OID_AUTO, witness, CTLFLAG_RW | CTLFLAG_MPSAFE, NULL,
374  * witness is completely disabled.  Otherwise witness performs full
376  * may be toggled.  However, witness cannot be reenabled once it is
383     "witness is watching lock operations");
425  * Output channel for witness messages.  By default we print to the console.
448  * Call this to print out the witness faulty stacks.
453     "Show bad witness stacks");
476 static struct witness *w_data;
479 static struct witness_hash w_hash;	/* The witness hash table. */
748  * This global is set to 0 once it becomes safe to use the witness code.
771  * Calculate the size of early witness structures.
778 	sz = sizeof(struct witness) * witness_count;
787  * The WITNESS-enabled diagnostic code.  Note that the witness code does
796 	struct witness *w, *w1;
802 	p += sizeof(struct witness) * witness_count;
814 	 * We have to release Giant before initializing its witness
820 	CTR1(KTR_WITNESS, "%s: initializing witness", __func__);
821 	mtx_init(&w_mtx, "witness lock", NULL, MTX_SPIN | MTX_QUIET |
830 	    ("%s: Invalid list of free witness objects", __func__));
862 	/* Iterate through all locks and add them to witness. */
872 	/* Mark the witness code as being ready for use. */
923 	struct witness *w;
949 	struct witness *w;
961 		/* If the witness has ancestors (is not a root), skip it. */
969 witness_ddb_level_descendants(struct witness *w, int l)
987     struct witness *w, int indent)
1021 	struct witness *w;
1037 	struct witness *w;
1085 	/* Require locks that witness knows about. */
1118 	struct witness *w, *w1;
1295 			 * If this lock doesn't undergo witness checking,
1301 				    ("lock missing witness structure"));
1414 			 * witness w in our list.
1439 				struct witness *w2 = lock2->li_lock->lo_witness;
1510 	struct witness *w;
1537 	/* Update per-witness last file and line acquire. */
1746 	 * free witness pool (and subsequent locking) is avoided.
1873 	struct witness *w;
1884 	struct witness *w;
1892 static struct witness *
1895 	struct witness *w;
1929 	/* Insert new witness into the hash */
1948 depart(struct witness *w)
1966 adopt(struct witness *parent, struct witness *child)
2038 				printf("witness rmatrix paradox! [%d][%d]=%d "
2047 				printf("witness rmatrix paradox! [%d][%d]=%d "
2059 itismychild(struct witness *parent, struct witness *child)
2090 _isitmyx(struct witness *w1, struct witness *w2, int rmask, const char *fname)
2124 isitmychild(struct witness *parent, struct witness *child)
2134 isitmydescendant(struct witness *ancestor, struct witness *descendant)
2142 blessed(struct witness *w1, struct witness *w2)
2161 static struct witness *
2164 	struct witness *w;
2177 		printf("WITNESS: unable to allocate a new witness object\n");
2194 witness_free(struct witness *w)
2213 		printf("%s: witness exhausted\n", __func__);
2611 DB_SHOW_COMMAND(witness, db_witness_display)
2622 	struct witness *tmp_w1, *tmp_w2, *w1, *w2;
2631 	tmp_w1 = malloc(sizeof(struct witness), M_TEMP, M_WAITOK | M_ZERO);
2632 	tmp_w2 = malloc(sizeof(struct witness), M_TEMP, M_WAITOK | M_ZERO);
2839 	struct witness *w;
2899 witness_add_fullgraph(struct sbuf *sb, struct witness *w)
2941  * Initializes the two witness hash tables. Called exactly once from
2971 static struct witness *
2974 	struct witness *w;
2993 witness_hash_put(struct witness *w)
3013 witness_lock_order_get(struct witness *parent, struct witness *child)
3047 witness_lock_order_check(struct witness *parent, struct witness *child)
3060 witness_lock_order_add(struct witness *parent, struct witness *child)
3091 /* Call this whenever the structure of the witness graph changes. */