]> err.no Git - linux-2.6/commit
lockdep: fix combinatorial explosion in lock subgraph traversal
authorDavid Miller <davem@davemloft.net>
Wed, 30 Jul 2008 04:45:03 +0000 (21:45 -0700)
committerIngo Molnar <mingo@elte.hu>
Thu, 31 Jul 2008 16:38:28 +0000 (18:38 +0200)
commit419ca3f13532793b81aff09f80c60af3eacbb43d
treeeb2d82e52917ebccff269a51e90868ce229336b2
parent6e86841d05f371b5b9b86ce76c02aaee83352298
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>
include/linux/lockdep.h
kernel/lockdep.c
kernel/lockdep_internals.h
kernel/lockdep_proc.c