Lines Matching full:dependency
418 * We put the lock dependency chains into a hash-table as well, to cache
444 * The hash key of the lock dependency chains is a hash itself too:
1423 * Add a new dependency to the head of the list:
1432 * Lock not present yet - get a new dependency struct and
1465 * indicates that adding the <prev> -> <next> lock dependency will
1563 * Return the forward or backward dependency list.
1565 * @lock: the lock_list to get its class's dependency list
1609 * For dependency @prev -> @next:
1708 * Breadth-First Search to find a strong path in the dependency graph.
1718 * e.g. ER and SN) between two nodes in the dependency graph. But
1719 * only the strong dependency path in the graph is relevant to deadlocks. A
1720 * strong dependency path is a dependency path that doesn't have two adjacent
1725 * for more explanation of the definition of strong dependency paths
1727 * In __bfs(), we only traverse in the strong dependency path:
1729 * In lock_list::only_xr, we record whether the previous dependency only
1731 * filter out any -(S*)-> in the current dependency and after that, the
1772 * Step 2: check whether prev dependency and this form a strong
1773 * dependency path.
1775 if (lock->parent) { /* Parent exists, check prev dependency */
1782 * dependency.
1797 * dependency path to this, so check with @match.
1822 * dependency from one (see __bfs_next()), as a result
1873 * Print a dependency chain entry (this is only done when a deadlock
1948 * When a circular dependency is detected, print the
1963 pr_warn("WARNING: possible circular locking dependency detected\n");
1974 pr_warn("\nthe existing dependency chain (in reverse order) is:\n");
1980 * We are about to add A -> B into the dependency graph, and in __bfs() a
1981 * strong dependency path A -> .. -> B is found: hlock_class equals
1988 * dependency graph, as any strong path ..-> A -> B ->.. we can get with
1989 * having dependency A -> B, we could already get a equivalent path ..-> A ->
2015 * We are about to add B -> A into the dependency graph, and in __bfs() a
2016 * strong dependency path A -> .. -> B is found: hlock_class equals
2020 * dependency cycle, that means:
2156 * Check that the dependency graph starting at <src> can lead to
2178 * Prove that the dependency graph starting at <src> can not
2180 * <target> -> <src> dependency.
2221 * proving that two subgraphs can be connected by a new dependency
2222 * without creating any illegal irq-safe -> irq-unsafe lock dependency.
2226 * 1) We have a strong dependency path A -> ... -> B
2229 * irq can create a new dependency B -> A (consider the case that a holder
2232 * 3) the dependency circle A -> ... -> B -> A we get from 1) and 2) is a
2249 * There is a strong dependency path in the dependency graph: A -> B, and now
2256 * As above, if only_xr is false, which means A -> B has -(E*)-> dependency
2271 * There is a strong dependency path in the dependency graph: A -> B, and now
2275 * As above, if only_xr is false, which means A -> B has -(*N)-> dependency
2296 * dependency.
2305 * where lock(B) cannot sleep, and we have a dependency B -> ... -> A.
2307 * Now we prove local_lock() cannot exist in that dependency. First we
2313 * way the local_lock() exists in the dependency B -> ... -> A.
2331 * Find a node in the forwards-direction dependency sub-graph starting
2351 * Find a node in the backwards-direction dependency sub-graph starting
2394 * Dependency path printing:
2396 * After BFS we get a lock dependency path (linked via ->parent of lock_list),
2397 * printing out each lock in the dependency path will help on understanding how
2398 * the deadlock could happen. Here are some details about dependency path
2401 * 1) A lock_list can be either forwards or backwards for a lock dependency,
2402 * for a lock dependency A -> B, there are two lock_lists:
2416 * represent a certain lock dependency, it only provides an initial entry
2433 * We have a lock dependency path as follow:
2474 * We have a lock dependency path (from a backwards search) as follow:
2484 * dependency path L1 -> L2 -> .. -> Ln in the non-reverse order.
2488 * trace of L1 in the dependency path, which is alright, because most of the
2615 pr_warn("which would create a new lock dependency:\n");
2621 pr_warn("\nbut this new dependency connects a %s-irq-safe lock:\n",
2811 * Prove that the new dependency does not connect a hardirq-safe(-read)
2919 * Check that the dependency graph starting at <src> can lead to
2920 * <target> or not. If it can, <src> -> <target> dependency is already
2937 * To report redundant, we need to find a strong dependency path that
3101 * There was a chain-cache miss, and we are about to add a new dependency
3104 * - would the adding of the <prev> -> <next> dependency create a
3105 * circular dependency in the graph? [== circular deadlock]
3107 * - does the new prev->next dependency connect any hardirq-safe lock
3112 * - does the new prev->next dependency connect any softirq-safe lock
3120 * dependency.
3157 * Prove that the new <prev> -> <next> dependency would not
3158 * create a circular dependency in the graph. (We do this by
3174 * Is the <prev> -> <next> dependency already present?
3179 * L2 added to its dependency list, due to the first chain.)
3188 * Also, update the reverse dependency in @next's
3234 * to the previous lock's dependency list:
3253 * Add the dependency to all directly-previous locks that are 'relevant'.
3725 * Adds a dependency chain into chain hashtable. And must be called with
3794 * Look up a dependency chain. Must be called with either the graph lock or
3812 * If the key is not present yet in dependency chain cache then
3813 * add it and return 1 - in this case the new dependency chain is
3872 * the dependencies only if this is a new dependency chain.
3884 * And check whether the new lock's dependency graph
3888 * - across our accumulated lock dependency records
3901 * Add dependency only if this lock is not the head
3903 * lock dependency (because we already hold a lock with the
4084 pr_warn("WARNING: possible irq lock inversion dependency detected\n");
4292 * mark USED_IN has to look forwards -- to ensure no dependency
4650 * creates no critical section and no extra dependency can be introduced
4702 * adding of the dependency to 'prev'):
5072 * We maintain the dependency maps and validate the locking attempt:
5130 * dependency checks are done)
5194 * lock keys along the dependency chain. We save the hash value
5196 * after unlock. The chain hash is then used to cache dependency
6620 pr_info("Lock dependency validator: Copyright (c) 2006 Red Hat, Inc., Ingo Molnar\n");
6630 pr_info(" memory used by lock dependency info: %zu kB\n",