412  * We put the lock dependency chains into a hash-table as well, to cache
438  * The hash key of the lock dependency chains is a hash itself too:
1411  * Add a new dependency to the head of the list:
1420 	 * Lock not present yet - get a new dependency struct and  in add_lock_to_list()
1453  * indicates that adding the <prev> -> <next> lock dependency will
1551  * Return the forward or backward dependency list.
1553  * @lock:   the lock_list to get its class's dependency list
1597  * For dependency @prev -> @next:
1696  * Breadth-First Search to find a strong path in the dependency graph.
1706  * e.g. ER and SN) between two nodes in the dependency graph. But
1707  * only the strong dependency path in the graph is relevant to deadlocks. A
1708  * strong dependency path is a dependency path that doesn't have two adjacent
1713  * for more explanation of the definition of strong dependency paths
1715  * In __bfs(), we only traverse in the strong dependency path:
1717  *     In lock_list::only_xr, we record whether the previous dependency only
1719  *     filter out any -(S*)-> in the current dependency and after that, the
1760 		 * Step 2: check whether prev dependency and this form a strong  in __bfs()
1761 		 *         dependency path.  in __bfs()
1763 		if (lock->parent) { /* Parent exists, check prev dependency */  in __bfs()
1770 			 * dependency.  in __bfs()
1785 		 *         dependency path to this, so check with @match.  in __bfs()
1810 			 * dependency from one (see __bfs_next()), as a result  in __bfs()
1861  * Print a dependency chain entry (this is only done when a deadlock
1926  * When a circular dependency is detected, print the
1941 	pr_warn("WARNING: possible circular locking dependency detected\n");  in print_circular_bug_header()
1952 	pr_warn("\nthe existing dependency chain (in reverse order) is:\n");  in print_circular_bug_header()
1958  * We are about to add A -> B into the dependency graph, and in __bfs() a
1959  * strong dependency path A -> .. -> B is found: hlock_class equals
1966  * dependency graph, as any strong path ..-> A -> B ->.. we can get with
1967  * having dependency A -> B, we could already get a equivalent path ..-> A ->
1993  * We are about to add B -> A into the dependency graph, and in __bfs() a
1994  * strong dependency path A -> .. -> B is found: hlock_class equals
1998  * dependency cycle, that means:
2127  * Check that the dependency graph starting at <src> can lead to
2147  * Prove that the dependency graph starting at <src> can not
2149  * <target> -> <src> dependency.
2187  * proving that two subgraphs can be connected by a new dependency
2188  * without creating any illegal irq-safe -> irq-unsafe lock dependency.
2192  * 1) We have a strong dependency path A -> ... -> B
2195  *    irq can create a new dependency B -> A (consider the case that a holder
2198  * 3) the dependency circle A -> ... -> B -> A we get from 1) and 2) is a
2215  * There is a strong dependency path in the dependency graph: A -> B, and now
2222  * As above, if only_xr is false, which means A -> B has -(E*)-> dependency
2237  * There is a strong dependency path in the dependency graph: A -> B, and now
2241  * As above, if only_xr is false, which means A -> B has -(*N)-> dependency
2259 	 * dependency.  in usage_skip()
2268 	 * where lock(B) cannot sleep, and we have a dependency B -> ... -> A.  in usage_skip()
2270 	 * Now we prove local_lock() cannot exist in that dependency. First we  in usage_skip()
2276 	 * way the local_lock() exists in the dependency B -> ... -> A.  in usage_skip()
2292  * Find a node in the forwards-direction dependency sub-graph starting
2312  * Find a node in the backwards-direction dependency sub-graph starting
2355  * Dependency path printing:
2357  * After BFS we get a lock dependency path (linked via ->parent of lock_list),
2358  * printing out each lock in the dependency path will help on understanding how
2359  * the deadlock could happen. Here are some details about dependency path
2362  * 1)	A lock_list can be either forwards or backwards for a lock dependency,
2363  * 	for a lock dependency A -> B, there are two lock_lists:
2377  * 	represent a certain lock dependency, it only provides an initial entry
2394  * We have a lock dependency path as follow:
2435  * We have a lock dependency path (from a backwards search) as follow:
2445  * dependency path L1 -> L2 -> .. -> Ln in the non-reverse order.
2449  * trace of L1 in the dependency path, which is alright, because most of the
2574 	pr_warn("which would create a new lock dependency:\n");  in print_bad_irq_dependency()
2580 	pr_warn("\nbut this new dependency connects a %s-irq-safe lock:\n",  in print_bad_irq_dependency()
2768  * Prove that the new dependency does not connect a hardirq-safe(-read)
2876  * Check that the dependency graph starting at <src> can lead to
2877  * <target> or not. If it can, <src> -> <target> dependency is already
2894 	 * To report redundant, we need to find a strong dependency path that  in check_redundant()
3040  * There was a chain-cache miss, and we are about to add a new dependency
3043  *  - would the adding of the <prev> -> <next> dependency create a
3044  *    circular dependency in the graph? [== circular deadlock]
3046  *  - does the new prev->next dependency connect any hardirq-safe lock
3051  *  - does the new prev->next dependency connect any softirq-safe lock
3059  * dependency.
3088 	 * Prove that the new <prev> -> <next> dependency would not  in check_prev_add()
3089 	 * create a circular dependency in the graph. (We do this by  in check_prev_add()
3105 	 * Is the <prev> -> <next> dependency already present?  in check_prev_add()
3110 	 *  L2 added to its dependency list, due to the first chain.)  in check_prev_add()
3119 			 * Also, update the reverse dependency in @next's  in check_prev_add()
3165 	 * to the previous lock's dependency list:  in check_prev_add()
3184  * Add the dependency to all directly-previous locks that are 'relevant'.
3651  * Adds a dependency chain into chain hashtable. And must be called with
3716  * Look up a dependency chain. Must be called with either the graph lock or
3734  * If the key is not present yet in dependency chain cache then
3735  * add it and return 1 - in this case the new dependency chain is
3794 	 * the dependencies only if this is a new dependency chain.  in validate_chain()
3806 		 * And check whether the new lock's dependency graph  in validate_chain()
3810 		 * - across our accumulated lock dependency records  in validate_chain()
3823 		 * Add dependency only if this lock is not the head  in validate_chain()
3825 		 * lock dependency (because we already hold a lock with the  in validate_chain()
4000 	pr_warn("WARNING: possible irq lock inversion dependency detected\n");  in print_irq_inversion_bug()
4202 		 * mark USED_IN has to look forwards -- to ensure no dependency  in mark_lock_irq()
4582 		 * adding of the dependency to 'prev'):  in separate_irq_context()
4903  * We maintain the dependency maps and validate the locking attempt:
4952 	 * dependency checks are done)  in __lock_acquire()
5014 	 * lock keys along the dependency chain. We save the hash value  in __lock_acquire()
5016 	 * after unlock. The chain hash is then used to cache dependency  in __lock_acquire()
6367 	printk("Lock dependency validator: Copyright (c) 2006 Red Hat, Inc., Ingo Molnar\n");  in lockdep_init()
6377 	printk(" memory used by lock dependency info: %zu kB\n",  in lockdep_init()