• David Miller's avatar
    lockdep: fix combinatorial explosion in lock subgraph traversal · 419ca3f1
    David Miller authored
    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: default avatarDavid S. Miller <davem@davemloft.net>
    Acked-by: default avatarPeter Zijlstra <a.p.zijlstra@chello.nl>
    Signed-off-by: default avatarIngo Molnar <mingo@elte.hu>
    419ca3f1
lockdep.h 12.4 KB