aboutsummaryrefslogtreecommitdiffstats
path: root/kernel/lockdep_internals.h
diff options
context:
space:
mode:
authorDavid Miller <davem@davemloft.net>2008-07-30 00:45:03 -0400
committerIngo Molnar <mingo@elte.hu>2008-07-31 12:38:28 -0400
commit419ca3f13532793b81aff09f80c60af3eacbb43d (patch)
treeeb2d82e52917ebccff269a51e90868ce229336b2 /kernel/lockdep_internals.h
parent6e86841d05f371b5b9b86ce76c02aaee83352298 (diff)
lockdep: fix combinatorial explosion in lock subgraph traversal
When we traverse the graph, either forwards or backwards, we are interested in whether a certain property exists somewhere in a node reachable in the graph. Therefore it is never necessary to traverse through a node more than once to get a correct answer to the given query. Take advantage of this property using a global ID counter so that we need not clear all the markers in all the lock_class entries before doing a traversal. A new ID is choosen when we start to traverse, and we continue through a lock_class only if it's ID hasn't been marked with the new value yet. This short-circuiting is essential especially for high CPU count systems. The scheduler has a runqueue per cpu, and needs to take two runqueue locks at a time, which leads to long chains of backwards and forwards subgraphs from these runqueue lock nodes. Without the short-circuit implemented here, a graph traversal on a runqueue lock can take up to (1 << (N - 1)) checks on a system with N cpus. For anything more than 16 cpus or so, lockdep will eventually bring the machine to a complete standstill. Signed-off-by: David S. Miller <davem@davemloft.net> Acked-by: Peter Zijlstra <a.p.zijlstra@chello.nl> Signed-off-by: Ingo Molnar <mingo@elte.hu>
Diffstat (limited to 'kernel/lockdep_internals.h')
-rw-r--r--kernel/lockdep_internals.h3
1 files changed, 3 insertions, 0 deletions
diff --git a/kernel/lockdep_internals.h b/kernel/lockdep_internals.h
index c3600a091a28..68d44ec77ab5 100644
--- a/kernel/lockdep_internals.h
+++ b/kernel/lockdep_internals.h
@@ -53,6 +53,9 @@ extern unsigned int nr_process_chains;
53extern unsigned int max_lockdep_depth; 53extern unsigned int max_lockdep_depth;
54extern unsigned int max_recursion_depth; 54extern unsigned int max_recursion_depth;
55 55
56extern unsigned long lockdep_count_forward_deps(struct lock_class *);
57extern unsigned long lockdep_count_backward_deps(struct lock_class *);
58
56#ifdef CONFIG_DEBUG_LOCKDEP 59#ifdef CONFIG_DEBUG_LOCKDEP
57/* 60/*
58 * Various lockdep statistics: 61 * Various lockdep statistics: