383  * We put the lock dependency chains into a hash-table as well, to cache
409  * The hash key of the lock dependency chains is a hash itself too:
1360  * Add a new dependency to the head of the list:
1369 	 * Lock not present yet - get a new dependency struct and  in add_lock_to_list()
1402  * indicates that adding the <prev> -> <next> lock dependency will
1500  * Return the forward or backward dependency list.
1502  * @lock:   the lock_list to get its class's dependency list
1546  * For dependency @prev -> @next:
1645  * Breadth-First Search to find a strong path in the dependency graph.
1655  * e.g. ER and SN) between two nodes in the dependency graph. But
1656  * only the strong dependency path in the graph is relevant to deadlocks. A
1657  * strong dependency path is a dependency path that doesn't have two adjacent
1662  * for more explanation of the definition of strong dependency paths
1664  * In __bfs(), we only traverse in the strong dependency path:
1666  *     In lock_list::only_xr, we record whether the previous dependency only
1668  *     filter out any -(S*)-> in the current dependency and after that, the
1708 		 * Step 2: check whether prev dependency and this form a strong  in __bfs()
1709 		 *         dependency path.  in __bfs()
1711 		if (lock->parent) { /* Parent exists, check prev dependency */  in __bfs()
1718 			 * dependency.  in __bfs()
1733 		 *         dependency path to this, so check with @match.  in __bfs()
1753 			 * dependency from one (see __bfs_next()), as a result  in __bfs()
1802  * Print a dependency chain entry (this is only done when a deadlock
1867  * When a circular dependency is detected, print the
1882 	pr_warn("WARNING: possible circular locking dependency detected\n");  in print_circular_bug_header()
1893 	pr_warn("\nthe existing dependency chain (in reverse order) is:\n");  in print_circular_bug_header()
1899  * We are about to add A -> B into the dependency graph, and in __bfs() a
1900  * strong dependency path A -> .. -> B is found: hlock_class equals
1907  * dependency graph, as any strong path ..-> A -> B ->.. we can get with
1908  * having dependency A -> B, we could already get a equivalent path ..-> A ->
1934  * We are about to add B -> A into the dependency graph, and in __bfs() a
1935  * strong dependency path A -> .. -> B is found: hlock_class equals
1939  * dependency cycle, that means:
2068  * Check that the dependency graph starting at <src> can lead to
2087  * Prove that the dependency graph starting at <src> can not
2089  * <target> -> <src> dependency.
2125  * Check that the dependency graph starting at <src> can lead to
2126  * <target> or not. If it can, <src> -> <target> dependency is already
2143 	 * To report redundant, we need to find a strong dependency path that  in check_redundant()
2167  * proving that two subgraphs can be connected by a new dependency
2168  * without creating any illegal irq-safe -> irq-unsafe lock dependency.
2172  * 1) We have a strong dependency path A -> ... -> B
2175  *    irq can create a new dependency B -> A (consider the case that a holder
2178  * 3) the dependency circle A -> ... -> B -> A we get from 1) and 2) is a
2195  * There is a strong dependency path in the dependency graph: A -> B, and now
2202  * As above, if only_xr is false, which means A -> B has -(E*)-> dependency
2217  * There is a strong dependency path in the dependency graph: A -> B, and now
2221  * As above, if only_xr is false, which means A -> B has -(*N)-> dependency
2234  * Find a node in the forwards-direction dependency sub-graph starting
2254  * Find a node in the backwards-direction dependency sub-graph starting
2412 	pr_warn("which would create a new lock dependency:\n");  in print_bad_irq_dependency()
2418 	pr_warn("\nbut this new dependency connects a %s-irq-safe lock:\n",  in print_bad_irq_dependency()
2609  * Prove that the new dependency does not connect a hardirq-safe(-read)
2811  * There was a chain-cache miss, and we are about to add a new dependency
2814  *  - would the adding of the <prev> -> <next> dependency create a
2815  *    circular dependency in the graph? [== circular deadlock]
2817  *  - does the new prev->next dependency connect any hardirq-safe lock
2822  *  - does the new prev->next dependency connect any softirq-safe lock
2830  * dependency.
2859 	 * Prove that the new <prev> -> <next> dependency would not  in check_prev_add()
2860 	 * create a circular dependency in the graph. (We do this by  in check_prev_add()
2876 	 * Is the <prev> -> <next> dependency already present?  in check_prev_add()
2881 	 *  L2 added to its dependency list, due to the first chain.)  in check_prev_add()
2890 			 * Also, update the reverse dependency in @next's  in check_prev_add()
2938 	 * to the previous lock's dependency list:  in check_prev_add()
2961  * Add the dependency to all directly-previous locks that are 'relevant'.
3428  * Adds a dependency chain into chain hashtable. And must be called with
3493  * Look up a dependency chain. Must be called with either the graph lock or
3511  * If the key is not present yet in dependency chain cache then
3512  * add it and return 1 - in this case the new dependency chain is
3571 	 * the dependencies only if this is a new dependency chain.  in validate_chain()
3583 		 * And check whether the new lock's dependency graph  in validate_chain()
3587 		 * - across our accumulated lock dependency records  in validate_chain()
3600 		 * Add dependency only if this lock is not the head  in validate_chain()
3602 		 * lock dependency (because we already hold a lock with the  in validate_chain()
3776 	pr_warn("WARNING: possible irq lock inversion dependency detected\n");  in print_irq_inversion_bug()
3978 		 * mark USED_IN has to look forwards -- to ensure no dependency  in mark_lock_irq()
4359 		 * adding of the dependency to 'prev'):  in separate_irq_context()
4680  * We maintain the dependency maps and validate the locking attempt:
4729 	 * dependency checks are done)  in __lock_acquire()
4791 	 * lock keys along the dependency chain. We save the hash value  in __lock_acquire()
4793 	 * after unlock. The chain hash is then used to cache dependency  in __lock_acquire()
6127 	printk("Lock dependency validator: Copyright (c) 2006 Red Hat, Inc., Ingo Molnar\n");  in lockdep_init()
6137 	printk(" memory used by lock dependency info: %zu kB\n",  in lockdep_init()