415  * We put the lock dependency chains into a hash-table as well, to cache
441  * The hash key of the lock dependency chains is a hash itself too:
1420  * Add a new dependency to the head of the list:
1429 	 * Lock not present yet - get a new dependency struct and  in add_lock_to_list()
1462  * indicates that adding the <prev> -> <next> lock dependency will
1560  * Return the forward or backward dependency list.
1562  * @lock:   the lock_list to get its class's dependency list
1606  * For dependency @prev -> @next:
1705  * Breadth-First Search to find a strong path in the dependency graph.
1715  * e.g. ER and SN) between two nodes in the dependency graph. But
1716  * only the strong dependency path in the graph is relevant to deadlocks. A
1717  * strong dependency path is a dependency path that doesn't have two adjacent
1722  * for more explanation of the definition of strong dependency paths
1724  * In __bfs(), we only traverse in the strong dependency path:
1726  *     In lock_list::only_xr, we record whether the previous dependency only
1728  *     filter out any -(S*)-> in the current dependency and after that, the
1769 		 * Step 2: check whether prev dependency and this form a strong  in __bfs()
1770 		 *         dependency path.  in __bfs()
1772 		if (lock->parent) { /* Parent exists, check prev dependency */  in __bfs()
1779 			 * dependency.  in __bfs()
1794 		 *         dependency path to this, so check with @match.  in __bfs()
1819 			 * dependency from one (see __bfs_next()), as a result  in __bfs()
1870  * Print a dependency chain entry (this is only done when a deadlock
1945  * When a circular dependency is detected, print the
1960 	pr_warn("WARNING: possible circular locking dependency detected\n");  in print_circular_bug_header()
1971 	pr_warn("\nthe existing dependency chain (in reverse order) is:\n");  in print_circular_bug_header()
1977  * We are about to add A -> B into the dependency graph, and in __bfs() a
1978  * strong dependency path A -> .. -> B is found: hlock_class equals
1985  * dependency graph, as any strong path ..-> A -> B ->.. we can get with
1986  * having dependency A -> B, we could already get a equivalent path ..-> A ->
2012  * We are about to add B -> A into the dependency graph, and in __bfs() a
2013  * strong dependency path A -> .. -> B is found: hlock_class equals
2017  * dependency cycle, that means:
2153  * Check that the dependency graph starting at <src> can lead to
2175  * Prove that the dependency graph starting at <src> can not
2177  * <target> -> <src> dependency.
2218  * proving that two subgraphs can be connected by a new dependency
2219  * without creating any illegal irq-safe -> irq-unsafe lock dependency.
2223  * 1) We have a strong dependency path A -> ... -> B
2226  *    irq can create a new dependency B -> A (consider the case that a holder
2229  * 3) the dependency circle A -> ... -> B -> A we get from 1) and 2) is a
2246  * There is a strong dependency path in the dependency graph: A -> B, and now
2253  * As above, if only_xr is false, which means A -> B has -(E*)-> dependency
2268  * There is a strong dependency path in the dependency graph: A -> B, and now
2272  * As above, if only_xr is false, which means A -> B has -(*N)-> dependency
2293 	 * dependency.  in usage_skip()
2302 	 * where lock(B) cannot sleep, and we have a dependency B -> ... -> A.  in usage_skip()
2304 	 * Now we prove local_lock() cannot exist in that dependency. First we  in usage_skip()
2310 	 * way the local_lock() exists in the dependency B -> ... -> A.  in usage_skip()
2328  * Find a node in the forwards-direction dependency sub-graph starting
2348  * Find a node in the backwards-direction dependency sub-graph starting
2391  * Dependency path printing:
2393  * After BFS we get a lock dependency path (linked via ->parent of lock_list),
2394  * printing out each lock in the dependency path will help on understanding how
2395  * the deadlock could happen. Here are some details about dependency path
2398  * 1)	A lock_list can be either forwards or backwards for a lock dependency,
2399  * 	for a lock dependency A -> B, there are two lock_lists:
2413  * 	represent a certain lock dependency, it only provides an initial entry
2430  * We have a lock dependency path as follow:
2471  * We have a lock dependency path (from a backwards search) as follow:
2481  * dependency path L1 -> L2 -> .. -> Ln in the non-reverse order.
2485  * trace of L1 in the dependency path, which is alright, because most of the
2612 	pr_warn("which would create a new lock dependency:\n");  in print_bad_irq_dependency()
2618 	pr_warn("\nbut this new dependency connects a %s-irq-safe lock:\n",  in print_bad_irq_dependency()
2808  * Prove that the new dependency does not connect a hardirq-safe(-read)
2916  * Check that the dependency graph starting at <src> can lead to
2917  * <target> or not. If it can, <src> -> <target> dependency is already
2934 	 * To report redundant, we need to find a strong dependency path that  in check_redundant()
3098  * There was a chain-cache miss, and we are about to add a new dependency
3101  *  - would the adding of the <prev> -> <next> dependency create a
3102  *    circular dependency in the graph? [== circular deadlock]
3104  *  - does the new prev->next dependency connect any hardirq-safe lock
3109  *  - does the new prev->next dependency connect any softirq-safe lock
3117  * dependency.
3154 	 * Prove that the new <prev> -> <next> dependency would not  in check_prev_add()
3155 	 * create a circular dependency in the graph. (We do this by  in check_prev_add()
3171 	 * Is the <prev> -> <next> dependency already present?  in check_prev_add()
3176 	 *  L2 added to its dependency list, due to the first chain.)  in check_prev_add()
3185 			 * Also, update the reverse dependency in @next's  in check_prev_add()
3231 	 * to the previous lock's dependency list:  in check_prev_add()
3250  * Add the dependency to all directly-previous locks that are 'relevant'.
3722  * Adds a dependency chain into chain hashtable. And must be called with
3791  * Look up a dependency chain. Must be called with either the graph lock or
3809  * If the key is not present yet in dependency chain cache then
3810  * add it and return 1 - in this case the new dependency chain is
3869 	 * the dependencies only if this is a new dependency chain.  in validate_chain()
3881 		 * And check whether the new lock's dependency graph  in validate_chain()
3885 		 * - across our accumulated lock dependency records  in validate_chain()
3898 		 * Add dependency only if this lock is not the head  in validate_chain()
3900 		 * lock dependency (because we already hold a lock with the  in validate_chain()
4081 	pr_warn("WARNING: possible irq lock inversion dependency detected\n");  in print_irq_inversion_bug()
4289 		 * mark USED_IN has to look forwards -- to ensure no dependency  in mark_lock_irq()
4647 	 * creates no critical section and no extra dependency can be introduced  in mark_usage()
4699 		 * adding of the dependency to 'prev'):  in separate_irq_context()
5069  * We maintain the dependency maps and validate the locking attempt:
5123 	 * dependency checks are done)  in __lock_acquire()
5187 	 * lock keys along the dependency chain. We save the hash value  in __lock_acquire()
5189 	 * after unlock. The chain hash is then used to cache dependency  in __lock_acquire()
6608 	pr_info("Lock dependency validator: Copyright (c) 2006 Red Hat, Inc., Ingo Molnar\n");  in lockdep_init()
6618 	pr_info(" memory used by lock dependency info: %zu kB\n",  in lockdep_init()