• Frederic Weisbecker's avatar
    locking/lockdep: Test all incompatible scenarios at once in check_irq_usage() · 948f8376
    Frederic Weisbecker authored
    check_prev_add_irq() tests all incompatible scenarios one after the
    other while adding a lock (@next) to a tree dependency (@prev):
    
    	LOCK_USED_IN_HARDIRQ          vs         LOCK_ENABLED_HARDIRQ
    	LOCK_USED_IN_HARDIRQ_READ     vs         LOCK_ENABLED_HARDIRQ
    	LOCK_USED_IN_SOFTIRQ          vs         LOCK_ENABLED_SOFTIRQ
    	LOCK_USED_IN_SOFTIRQ_READ     vs         LOCK_ENABLED_SOFTIRQ
    
    Also for these four scenarios, we must at least iterate the @prev
    backward dependency. Then if it matches the relevant LOCK_USED_* bit,
    we must also iterate the @next forward dependency.
    
    Therefore in the best case we iterate 4 times, in the worst case 8 times.
    
    A different approach can let us divide the number of branch iterations
    by 4:
    
    1) Iterate through @prev backward dependencies and accumulate all the IRQ
       uses in a single mask. In the best case where the current lock hasn't
       been used in IRQ, we stop here.
    
    2) Iterate through @next forward dependencies and try to find a lock
       whose usage is exclusive to the accumulated usages gathered in the
       previous step. If we find one (call it @lockA), we have found an
       incompatible use, otherwise we stop here. Only bad locking scenario
       go further. So a sane verification stop here.
    
    3) Iterate again through @prev backward dependency and find the lock
       whose usage matches @lockA in term of incompatibility. Call that
       lock @lockB.
    
    4) Report the incompatible usages of @lockA and @lockB
    
    If no incompatible use is found, the verification never goes beyond
    step 2 which means at most two iterations.
    
    The following compares the execution measurements of the function
    check_prev_add_irq():
    
                Number of  calls   | Avg (ns)  | Stdev (ns) | Total time (ns)
      ------------------------------------------------------------------------
      Mainline         8452        |  2652     |    11962   |    22415143
      This patch       8452        |  1518     |     7090   |    12835602
    Signed-off-by: default avatarFrederic Weisbecker <frederic@kernel.org>
    Signed-off-by: default avatarPeter Zijlstra (Intel) <peterz@infradead.org>
    Cc: Andrew Morton <akpm@linux-foundation.org>
    Cc: Linus Torvalds <torvalds@linux-foundation.org>
    Cc: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
    Cc: Peter Zijlstra <peterz@infradead.org>
    Cc: Thomas Gleixner <tglx@linutronix.de>
    Cc: Will Deacon <will.deacon@arm.com>
    Link: https://lkml.kernel.org/r/20190402160244.32434-5-frederic@kernel.orgSigned-off-by: default avatarIngo Molnar <mingo@kernel.org>
    948f8376
lockdep_internals.h 6.42 KB