413  * We put the lock dependency chains into a hash-table as well, to cache
439  * The hash key of the lock dependency chains is a hash itself too:
1406  * Add a new dependency to the head of the list:
1415 	 * Lock not present yet - get a new dependency struct and  in add_lock_to_list()
1448  * indicates that adding the <prev> -> <next> lock dependency will
1546  * Return the forward or backward dependency list.
1548  * @lock:   the lock_list to get its class's dependency list
1592  * For dependency @prev -> @next:
1691  * Breadth-First Search to find a strong path in the dependency graph.
1701  * e.g. ER and SN) between two nodes in the dependency graph. But
1702  * only the strong dependency path in the graph is relevant to deadlocks. A
1703  * strong dependency path is a dependency path that doesn't have two adjacent
1708  * for more explanation of the definition of strong dependency paths
1710  * In __bfs(), we only traverse in the strong dependency path:
1712  *     In lock_list::only_xr, we record whether the previous dependency only
1714  *     filter out any -(S*)-> in the current dependency and after that, the
1755 		 * Step 2: check whether prev dependency and this form a strong  in __bfs()
1756 		 *         dependency path.  in __bfs()
1758 		if (lock->parent) { /* Parent exists, check prev dependency */  in __bfs()
1765 			 * dependency.  in __bfs()
1780 		 *         dependency path to this, so check with @match.  in __bfs()
1805 			 * dependency from one (see __bfs_next()), as a result  in __bfs()
1856  * Print a dependency chain entry (this is only done when a deadlock
1931  * When a circular dependency is detected, print the
1946 	pr_warn("WARNING: possible circular locking dependency detected\n");  in print_circular_bug_header()
1957 	pr_warn("\nthe existing dependency chain (in reverse order) is:\n");  in print_circular_bug_header()
1963  * We are about to add A -> B into the dependency graph, and in __bfs() a
1964  * strong dependency path A -> .. -> B is found: hlock_class equals
1971  * dependency graph, as any strong path ..-> A -> B ->.. we can get with
1972  * having dependency A -> B, we could already get a equivalent path ..-> A ->
1998  * We are about to add B -> A into the dependency graph, and in __bfs() a
1999  * strong dependency path A -> .. -> B is found: hlock_class equals
2003  * dependency cycle, that means:
2132  * Check that the dependency graph starting at <src> can lead to
2154  * Prove that the dependency graph starting at <src> can not
2156  * <target> -> <src> dependency.
2197  * proving that two subgraphs can be connected by a new dependency
2198  * without creating any illegal irq-safe -> irq-unsafe lock dependency.
2202  * 1) We have a strong dependency path A -> ... -> B
2205  *    irq can create a new dependency B -> A (consider the case that a holder
2208  * 3) the dependency circle A -> ... -> B -> A we get from 1) and 2) is a
2225  * There is a strong dependency path in the dependency graph: A -> B, and now
2232  * As above, if only_xr is false, which means A -> B has -(E*)-> dependency
2247  * There is a strong dependency path in the dependency graph: A -> B, and now
2251  * As above, if only_xr is false, which means A -> B has -(*N)-> dependency
2272 	 * dependency.  in usage_skip()
2281 	 * where lock(B) cannot sleep, and we have a dependency B -> ... -> A.  in usage_skip()
2283 	 * Now we prove local_lock() cannot exist in that dependency. First we  in usage_skip()
2289 	 * way the local_lock() exists in the dependency B -> ... -> A.  in usage_skip()
2307  * Find a node in the forwards-direction dependency sub-graph starting
2327  * Find a node in the backwards-direction dependency sub-graph starting
2370  * Dependency path printing:
2372  * After BFS we get a lock dependency path (linked via ->parent of lock_list),
2373  * printing out each lock in the dependency path will help on understanding how
2374  * the deadlock could happen. Here are some details about dependency path
2377  * 1)	A lock_list can be either forwards or backwards for a lock dependency,
2378  * 	for a lock dependency A -> B, there are two lock_lists:
2392  * 	represent a certain lock dependency, it only provides an initial entry
2409  * We have a lock dependency path as follow:
2450  * We have a lock dependency path (from a backwards search) as follow:
2460  * dependency path L1 -> L2 -> .. -> Ln in the non-reverse order.
2464  * trace of L1 in the dependency path, which is alright, because most of the
2589 	pr_warn("which would create a new lock dependency:\n");  in print_bad_irq_dependency()
2595 	pr_warn("\nbut this new dependency connects a %s-irq-safe lock:\n",  in print_bad_irq_dependency()
2783  * Prove that the new dependency does not connect a hardirq-safe(-read)
2891  * Check that the dependency graph starting at <src> can lead to
2892  * <target> or not. If it can, <src> -> <target> dependency is already
2909 	 * To report redundant, we need to find a strong dependency path that  in check_redundant()
3069  * There was a chain-cache miss, and we are about to add a new dependency
3072  *  - would the adding of the <prev> -> <next> dependency create a
3073  *    circular dependency in the graph? [== circular deadlock]
3075  *  - does the new prev->next dependency connect any hardirq-safe lock
3080  *  - does the new prev->next dependency connect any softirq-safe lock
3088  * dependency.
3125 	 * Prove that the new <prev> -> <next> dependency would not  in check_prev_add()
3126 	 * create a circular dependency in the graph. (We do this by  in check_prev_add()
3142 	 * Is the <prev> -> <next> dependency already present?  in check_prev_add()
3147 	 *  L2 added to its dependency list, due to the first chain.)  in check_prev_add()
3156 			 * Also, update the reverse dependency in @next's  in check_prev_add()
3202 	 * to the previous lock's dependency list:  in check_prev_add()
3221  * Add the dependency to all directly-previous locks that are 'relevant'.
3688  * Adds a dependency chain into chain hashtable. And must be called with
3753  * Look up a dependency chain. Must be called with either the graph lock or
3771  * If the key is not present yet in dependency chain cache then
3772  * add it and return 1 - in this case the new dependency chain is
3831 	 * the dependencies only if this is a new dependency chain.  in validate_chain()
3843 		 * And check whether the new lock's dependency graph  in validate_chain()
3847 		 * - across our accumulated lock dependency records  in validate_chain()
3860 		 * Add dependency only if this lock is not the head  in validate_chain()
3862 		 * lock dependency (because we already hold a lock with the  in validate_chain()
4037 	pr_warn("WARNING: possible irq lock inversion dependency detected\n");  in print_irq_inversion_bug()
4239 		 * mark USED_IN has to look forwards -- to ensure no dependency  in mark_lock_irq()
4573 	 * creates no critical section and no extra dependency can be introduced  in mark_usage()
4625 		 * adding of the dependency to 'prev'):  in separate_irq_context()
4982  * We maintain the dependency maps and validate the locking attempt:
5031 	 * dependency checks are done)  in __lock_acquire()
5095 	 * lock keys along the dependency chain. We save the hash value  in __lock_acquire()
5097 	 * after unlock. The chain hash is then used to cache dependency  in __lock_acquire()
6480 	printk("Lock dependency validator: Copyright (c) 2006 Red Hat, Inc., Ingo Molnar\n");  in lockdep_init()
6490 	printk(" memory used by lock dependency info: %zu kB\n",  in lockdep_init()