384  * We put the lock dependency chains into a hash-table as well, to cache
410  * The hash key of the lock dependency chains is a hash itself too:
1365  * Add a new dependency to the head of the list:
1374 	 * Lock not present yet - get a new dependency struct and  in add_lock_to_list()
1407  * indicates that adding the <prev> -> <next> lock dependency will
1505  * Return the forward or backward dependency list.
1507  * @lock:   the lock_list to get its class's dependency list
1551  * For dependency @prev -> @next:
1650  * Breadth-First Search to find a strong path in the dependency graph.
1660  * e.g. ER and SN) between two nodes in the dependency graph. But
1661  * only the strong dependency path in the graph is relevant to deadlocks. A
1662  * strong dependency path is a dependency path that doesn't have two adjacent
1667  * for more explanation of the definition of strong dependency paths
1669  * In __bfs(), we only traverse in the strong dependency path:
1671  *     In lock_list::only_xr, we record whether the previous dependency only
1673  *     filter out any -(S*)-> in the current dependency and after that, the
1714 		 * Step 2: check whether prev dependency and this form a strong  in __bfs()
1715 		 *         dependency path.  in __bfs()
1717 		if (lock->parent) { /* Parent exists, check prev dependency */  in __bfs()
1724 			 * dependency.  in __bfs()
1739 		 *         dependency path to this, so check with @match.  in __bfs()
1764 			 * dependency from one (see __bfs_next()), as a result  in __bfs()
1815  * Print a dependency chain entry (this is only done when a deadlock
1880  * When a circular dependency is detected, print the
1895 	pr_warn("WARNING: possible circular locking dependency detected\n");  in print_circular_bug_header()
1906 	pr_warn("\nthe existing dependency chain (in reverse order) is:\n");  in print_circular_bug_header()
1912  * We are about to add A -> B into the dependency graph, and in __bfs() a
1913  * strong dependency path A -> .. -> B is found: hlock_class equals
1920  * dependency graph, as any strong path ..-> A -> B ->.. we can get with
1921  * having dependency A -> B, we could already get a equivalent path ..-> A ->
1947  * We are about to add B -> A into the dependency graph, and in __bfs() a
1948  * strong dependency path A -> .. -> B is found: hlock_class equals
1952  * dependency cycle, that means:
2081  * Check that the dependency graph starting at <src> can lead to
2101  * Prove that the dependency graph starting at <src> can not
2103  * <target> -> <src> dependency.
2141  * proving that two subgraphs can be connected by a new dependency
2142  * without creating any illegal irq-safe -> irq-unsafe lock dependency.
2146  * 1) We have a strong dependency path A -> ... -> B
2149  *    irq can create a new dependency B -> A (consider the case that a holder
2152  * 3) the dependency circle A -> ... -> B -> A we get from 1) and 2) is a
2169  * There is a strong dependency path in the dependency graph: A -> B, and now
2176  * As above, if only_xr is false, which means A -> B has -(E*)-> dependency
2191  * There is a strong dependency path in the dependency graph: A -> B, and now
2195  * As above, if only_xr is false, which means A -> B has -(*N)-> dependency
2213 	 * dependency.  in usage_skip()
2222 	 * where lock(B) cannot sleep, and we have a dependency B -> ... -> A.  in usage_skip()
2224 	 * Now we prove local_lock() cannot exist in that dependency. First we  in usage_skip()
2230 	 * way the local_lock() exists in the dependency B -> ... -> A.  in usage_skip()
2246  * Find a node in the forwards-direction dependency sub-graph starting
2266  * Find a node in the backwards-direction dependency sub-graph starting
2309  * Dependency path printing:
2311  * After BFS we get a lock dependency path (linked via ->parent of lock_list),
2312  * printing out each lock in the dependency path will help on understanding how
2313  * the deadlock could happen. Here are some details about dependency path
2316  * 1)	A lock_list can be either forwards or backwards for a lock dependency,
2317  * 	for a lock dependency A -> B, there are two lock_lists:
2331  * 	represent a certain lock dependency, it only provides an initial entry
2348  * We have a lock dependency path as follow:
2389  * We have a lock dependency path (from a backwards search) as follow:
2399  * dependency path L1 -> L2 -> .. -> Ln in the non-reverse order.
2403  * trace of L1 in the dependency path, which is alright, because most of the
2528 	pr_warn("which would create a new lock dependency:\n");  in print_bad_irq_dependency()
2534 	pr_warn("\nbut this new dependency connects a %s-irq-safe lock:\n",  in print_bad_irq_dependency()
2722  * Prove that the new dependency does not connect a hardirq-safe(-read)
2830  * Check that the dependency graph starting at <src> can lead to
2831  * <target> or not. If it can, <src> -> <target> dependency is already
2848 	 * To report redundant, we need to find a strong dependency path that  in check_redundant()
2994  * There was a chain-cache miss, and we are about to add a new dependency
2997  *  - would the adding of the <prev> -> <next> dependency create a
2998  *    circular dependency in the graph? [== circular deadlock]
3000  *  - does the new prev->next dependency connect any hardirq-safe lock
3005  *  - does the new prev->next dependency connect any softirq-safe lock
3013  * dependency.
3042 	 * Prove that the new <prev> -> <next> dependency would not  in check_prev_add()
3043 	 * create a circular dependency in the graph. (We do this by  in check_prev_add()
3059 	 * Is the <prev> -> <next> dependency already present?  in check_prev_add()
3064 	 *  L2 added to its dependency list, due to the first chain.)  in check_prev_add()
3073 			 * Also, update the reverse dependency in @next's  in check_prev_add()
3119 	 * to the previous lock's dependency list:  in check_prev_add()
3142  * Add the dependency to all directly-previous locks that are 'relevant'.
3609  * Adds a dependency chain into chain hashtable. And must be called with
3674  * Look up a dependency chain. Must be called with either the graph lock or
3692  * If the key is not present yet in dependency chain cache then
3693  * add it and return 1 - in this case the new dependency chain is
3752 	 * the dependencies only if this is a new dependency chain.  in validate_chain()
3764 		 * And check whether the new lock's dependency graph  in validate_chain()
3768 		 * - across our accumulated lock dependency records  in validate_chain()
3781 		 * Add dependency only if this lock is not the head  in validate_chain()
3783 		 * lock dependency (because we already hold a lock with the  in validate_chain()
3958 	pr_warn("WARNING: possible irq lock inversion dependency detected\n");  in print_irq_inversion_bug()
4160 		 * mark USED_IN has to look forwards -- to ensure no dependency  in mark_lock_irq()
4541 		 * adding of the dependency to 'prev'):  in separate_irq_context()
4863  * We maintain the dependency maps and validate the locking attempt:
4912 	 * dependency checks are done)  in __lock_acquire()
4974 	 * lock keys along the dependency chain. We save the hash value  in __lock_acquire()
4976 	 * after unlock. The chain hash is then used to cache dependency  in __lock_acquire()
6319 	printk("Lock dependency validator: Copyright (c) 2006 Red Hat, Inc., Ingo Molnar\n");  in lockdep_init()
6329 	printk(" memory used by lock dependency info: %zu kB\n",  in lockdep_init()