1 files changed, 183 insertions, 84 deletions

diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index 91c6b89f04df..27b992fe8cec 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -501,11 +501,11 @@ static char get_usage_char(struct lock_class *class, enum lock_usage_bit bit)
 {
         char c = '.';
 
-        if (class->usage_mask & lock_flag(bit + 2))
+        if (class->usage_mask & lock_flag(bit + LOCK_USAGE_DIR_MASK))
                 c = '+';
         if (class->usage_mask & lock_flag(bit)) {
                 c = '-';
-                if (class->usage_mask & lock_flag(bit + 2))
+                if (class->usage_mask & lock_flag(bit + LOCK_USAGE_DIR_MASK))
                         c = '?';
         }
 
@@ -1666,19 +1666,25 @@ check_redundant(struct lock_list *root, struct lock_class *target,
 }
 
 #if defined(CONFIG_TRACE_IRQFLAGS) && defined(CONFIG_PROVE_LOCKING)
+
+static inline int usage_accumulate(struct lock_list *entry, void *mask)
+{
+        *(unsigned long *)mask |= entry->class->usage_mask;
+
+        return 0;
+}
+
 /*
  * Forwards and backwards subgraph searching, for the purposes of
  * proving that two subgraphs can be connected by a new dependency
  * without creating any illegal irq-safe -> irq-unsafe lock dependency.
  */
 
-static inline int usage_match(struct lock_list *entry, void *bit)
+static inline int usage_match(struct lock_list *entry, void *mask)
 {
-        return entry->class->usage_mask & (1 << (enum lock_usage_bit)bit);
+        return entry->class->usage_mask & *(unsigned long *)mask;
 }
 
-
-
 /*
  * Find a node in the forwards-direction dependency sub-graph starting
  * at @root->class that matches @bit.
@@ -1690,14 +1696,14 @@ static inline int usage_match(struct lock_list *entry, void *bit)
  * Return <0 on error.
  */
 static int
-find_usage_forwards(struct lock_list *root, enum lock_usage_bit bit,
+find_usage_forwards(struct lock_list *root, unsigned long usage_mask,
                         struct lock_list **target_entry)
 {
         int result;
 
         debug_atomic_inc(nr_find_usage_forwards_checks);
 
-        result = __bfs_forwards(root, (void *)bit, usage_match, target_entry);
+        result = __bfs_forwards(root, &usage_mask, usage_match, target_entry);
 
         return result;
 }
@@ -1713,14 +1719,14 @@ find_usage_forwards(struct lock_list *root, enum lock_usage_bit bit,
  * Return <0 on error.
  */
 static int
-find_usage_backwards(struct lock_list *root, enum lock_usage_bit bit,
+find_usage_backwards(struct lock_list *root, unsigned long usage_mask,
                         struct lock_list **target_entry)
 {
         int result;
 
         debug_atomic_inc(nr_find_usage_backwards_checks);
 
-        result = __bfs_backwards(root, (void *)bit, usage_match, target_entry);
+        result = __bfs_backwards(root, &usage_mask, usage_match, target_entry);
 
         return result;
 }
@@ -1912,39 +1918,6 @@ print_bad_irq_dependency(struct task_struct *curr,
         return 0;
 }
 
-static int
-check_usage(struct task_struct *curr, struct held_lock *prev,
-            struct held_lock *next, enum lock_usage_bit bit_backwards,
-            enum lock_usage_bit bit_forwards, const char *irqclass)
-{
-        int ret;
-        struct lock_list this, that;
-        struct lock_list *uninitialized_var(target_entry);
-        struct lock_list *uninitialized_var(target_entry1);
-
-        this.parent = NULL;
-
-        this.class = hlock_class(prev);
-        ret = find_usage_backwards(&this, bit_backwards, &target_entry);
-        if (ret < 0)
-                return print_bfs_bug(ret);
-        if (ret == 1)
-                return ret;
-
-        that.parent = NULL;
-        that.class = hlock_class(next);
-        ret = find_usage_forwards(&that, bit_forwards, &target_entry1);
-        if (ret < 0)
-                return print_bfs_bug(ret);
-        if (ret == 1)
-                return ret;
-
-        return print_bad_irq_dependency(curr, &this, &that,
-                        target_entry, target_entry1,
-                        prev, next,
-                        bit_backwards, bit_forwards, irqclass);
-}
-
 static const char *state_names[] = {
 #define LOCKDEP_STATE(__STATE) \
         __stringify(__STATE),
@@ -1961,9 +1934,19 @@ static const char *state_rnames[] = {
 
 static inline const char *state_name(enum lock_usage_bit bit)
 {
-        return (bit & LOCK_USAGE_READ_MASK) ? state_rnames[bit >> 2] : state_names[bit >> 2];
+        if (bit & LOCK_USAGE_READ_MASK)
+                return state_rnames[bit >> LOCK_USAGE_DIR_MASK];
+        else
+                return state_names[bit >> LOCK_USAGE_DIR_MASK];
 }
 
+/*
+ * The bit number is encoded like:
+ *
+ *  bit0: 0 exclusive, 1 read lock
+ *  bit1: 0 used in irq, 1 irq enabled
+ *  bit2-n: state
+ */
 static int exclusive_bit(int new_bit)
 {
         int state = new_bit & LOCK_USAGE_STATE_MASK;
@@ -1975,45 +1958,160 @@ static int exclusive_bit(int new_bit)
         return state | (dir ^ LOCK_USAGE_DIR_MASK);
 }
 
+/*
+ * Observe that when given a bitmask where each bitnr is encoded as above, a
+ * right shift of the mask transforms the individual bitnrs as -1 and
+ * conversely, a left shift transforms into +1 for the individual bitnrs.
+ *
+ * So for all bits whose number have LOCK_ENABLED_* set (bitnr1 == 1), we can
+ * create the mask with those bit numbers using LOCK_USED_IN_* (bitnr1 == 0)
+ * instead by subtracting the bit number by 2, or shifting the mask right by 2.
+ *
+ * Similarly, bitnr1 == 0 becomes bitnr1 == 1 by adding 2, or shifting left 2.
+ *
+ * So split the mask (note that LOCKF_ENABLED_IRQ_ALL|LOCKF_USED_IN_IRQ_ALL is
+ * all bits set) and recompose with bitnr1 flipped.
+ */
+static unsigned long invert_dir_mask(unsigned long mask)
+{
+        unsigned long excl = 0;
+
+        /* Invert dir */
+        excl |= (mask & LOCKF_ENABLED_IRQ_ALL) >> LOCK_USAGE_DIR_MASK;
+        excl |= (mask & LOCKF_USED_IN_IRQ_ALL) << LOCK_USAGE_DIR_MASK;
+
+        return excl;
+}
+
+/*
+ * As above, we clear bitnr0 (LOCK_*_READ off) with bitmask ops. First, for all
+ * bits with bitnr0 set (LOCK_*_READ), add those with bitnr0 cleared (LOCK_*).
+ * And then mask out all bitnr0.
+ */
+static unsigned long exclusive_mask(unsigned long mask)
+{
+        unsigned long excl = invert_dir_mask(mask);
+
+        /* Strip read */
+        excl |= (excl & LOCKF_IRQ_READ) >> LOCK_USAGE_READ_MASK;
+        excl &= ~LOCKF_IRQ_READ;
+
+        return excl;
+}
+
+/*
+ * Retrieve the _possible_ original mask to which @mask is
+ * exclusive. Ie: this is the opposite of exclusive_mask().
+ * Note that 2 possible original bits can match an exclusive
+ * bit: one has LOCK_USAGE_READ_MASK set, the other has it
+ * cleared. So both are returned for each exclusive bit.
+ */
+static unsigned long original_mask(unsigned long mask)
+{
+        unsigned long excl = invert_dir_mask(mask);
+
+        /* Include read in existing usages */
+        excl |= (excl & LOCKF_IRQ) << LOCK_USAGE_READ_MASK;
+
+        return excl;
+}
+
+/*
+ * Find the first pair of bit match between an original
+ * usage mask and an exclusive usage mask.
+ */
+static int find_exclusive_match(unsigned long mask,
+                                unsigned long excl_mask,
+                                enum lock_usage_bit *bitp,
+                                enum lock_usage_bit *excl_bitp)
+{
+        int bit, excl;
+
+        for_each_set_bit(bit, &mask, LOCK_USED) {
+                excl = exclusive_bit(bit);
+                if (excl_mask & lock_flag(excl)) {
+                        *bitp = bit;
+                        *excl_bitp = excl;
+                        return 0;
+                }
+        }
+        return -1;
+}
+
+/*
+ * Prove that the new dependency does not connect a hardirq-safe(-read)
+ * lock with a hardirq-unsafe lock - to achieve this we search
+ * the backwards-subgraph starting at <prev>, and the
+ * forwards-subgraph starting at <next>:
+ */
 static int check_irq_usage(struct task_struct *curr, struct held_lock *prev,
-                           struct held_lock *next, enum lock_usage_bit bit)
+                           struct held_lock *next)
 {
+        unsigned long usage_mask = 0, forward_mask, backward_mask;
+        enum lock_usage_bit forward_bit = 0, backward_bit = 0;
+        struct lock_list *uninitialized_var(target_entry1);
+        struct lock_list *uninitialized_var(target_entry);
+        struct lock_list this, that;
+        int ret;
+
         /*
-         * Prove that the new dependency does not connect a hardirq-safe
-         * lock with a hardirq-unsafe lock - to achieve this we search
-         * the backwards-subgraph starting at <prev>, and the
-         * forwards-subgraph starting at <next>:
+         * Step 1: gather all hard/soft IRQs usages backward in an
+         * accumulated usage mask.
          */
-        if (!check_usage(curr, prev, next, bit,
-                           exclusive_bit(bit), state_name(bit)))
-                return 0;
+        this.parent = NULL;
+        this.class = hlock_class(prev);
+
+        ret = __bfs_backwards(&this, &usage_mask, usage_accumulate, NULL);
+        if (ret < 0)
+                return print_bfs_bug(ret);
 
-        bit++; /* _READ */
+        usage_mask &= LOCKF_USED_IN_IRQ_ALL;
+        if (!usage_mask)
+                return 1;
 
         /*
-         * Prove that the new dependency does not connect a hardirq-safe-read
-         * lock with a hardirq-unsafe lock - to achieve this we search
-         * the backwards-subgraph starting at <prev>, and the
-         * forwards-subgraph starting at <next>:
+         * Step 2: find exclusive uses forward that match the previous
+         * backward accumulated mask.
          */
-        if (!check_usage(curr, prev, next, bit,
-                           exclusive_bit(bit), state_name(bit)))
-                return 0;
+        forward_mask = exclusive_mask(usage_mask);
 
-        return 1;
-}
+        that.parent = NULL;
+        that.class = hlock_class(next);
 
-static int
-check_prev_add_irq(struct task_struct *curr, struct held_lock *prev,
-                struct held_lock *next)
-{
-#define LOCKDEP_STATE(__STATE)                                          \
-        if (!check_irq_usage(curr, prev, next, LOCK_USED_IN_##__STATE)) \
-                return 0;
-#include "lockdep_states.h"
-#undef LOCKDEP_STATE
+        ret = find_usage_forwards(&that, forward_mask, &target_entry1);
+        if (ret < 0)
+                return print_bfs_bug(ret);
+        if (ret == 1)
+                return ret;
 
-        return 1;
+        /*
+         * Step 3: we found a bad match! Now retrieve a lock from the backward
+         * list whose usage mask matches the exclusive usage mask from the
+         * lock found on the forward list.
+         */
+        backward_mask = original_mask(target_entry1->class->usage_mask);
+
+        ret = find_usage_backwards(&this, backward_mask, &target_entry);
+        if (ret < 0)
+                return print_bfs_bug(ret);
+        if (DEBUG_LOCKS_WARN_ON(ret == 1))
+                return 1;
+
+        /*
+         * Step 4: narrow down to a pair of incompatible usage bits
+         * and report it.
+         */
+        ret = find_exclusive_match(target_entry->class->usage_mask,
+                                   target_entry1->class->usage_mask,
+                                   &backward_bit, &forward_bit);
+        if (DEBUG_LOCKS_WARN_ON(ret == -1))
+                return 1;
+
+        return print_bad_irq_dependency(curr, &this, &that,
+                        target_entry, target_entry1,
+                        prev, next,
+                        backward_bit, forward_bit,
+                        state_name(backward_bit));
 }
 
 static void inc_chains(void)
@@ -2030,9 +2128,8 @@ static void inc_chains(void)
 
 #else
 
-static inline int
-check_prev_add_irq(struct task_struct *curr, struct held_lock *prev,
-                struct held_lock *next)
+static inline int check_irq_usage(struct task_struct *curr,
+                                  struct held_lock *prev, struct held_lock *next)
 {
         return 1;
 }
@@ -2211,7 +2308,7 @@ check_prev_add(struct task_struct *curr, struct held_lock *prev,
         else if (unlikely(ret < 0))
                 return print_bfs_bug(ret);
 
-        if (!check_prev_add_irq(curr, prev, next))
+        if (!check_irq_usage(curr, prev, next))
                 return 0;
 
         /*
@@ -2773,6 +2870,12 @@ static void check_chain_key(struct task_struct *curr)
 #endif
 }
 
+static int mark_lock(struct task_struct *curr, struct held_lock *this,
+                     enum lock_usage_bit new_bit);
+
+#if defined(CONFIG_TRACE_IRQFLAGS) && defined(CONFIG_PROVE_LOCKING)
+
+
 static void
 print_usage_bug_scenario(struct held_lock *lock)
 {
@@ -2842,10 +2945,6 @@ valid_state(struct task_struct *curr, struct held_lock *this,
         return 1;
 }
 
-static int mark_lock(struct task_struct *curr, struct held_lock *this,
-                     enum lock_usage_bit new_bit);
-
-#if defined(CONFIG_TRACE_IRQFLAGS) && defined(CONFIG_PROVE_LOCKING)
 
 /*
  * print irq inversion bug:
@@ -2925,7 +3024,7 @@ check_usage_forwards(struct task_struct *curr, struct held_lock *this,
 
         root.parent = NULL;
         root.class = hlock_class(this);
-        ret = find_usage_forwards(&root, bit, &target_entry);
+        ret = find_usage_forwards(&root, lock_flag(bit), &target_entry);
         if (ret < 0)
                 return print_bfs_bug(ret);
         if (ret == 1)
@@ -2949,7 +3048,7 @@ check_usage_backwards(struct task_struct *curr, struct held_lock *this,
 
         root.parent = NULL;
         root.class = hlock_class(this);
-        ret = find_usage_backwards(&root, bit, &target_entry);
+        ret = find_usage_backwards(&root, lock_flag(bit), &target_entry);
         if (ret < 0)
                 return print_bfs_bug(ret);
         if (ret == 1)
@@ -3004,7 +3103,7 @@ static int (*state_verbose_f[])(struct lock_class *class) = {
 static inline int state_verbose(enum lock_usage_bit bit,
                                 struct lock_class *class)
 {
-        return state_verbose_f[bit >> 2](class);
+        return state_verbose_f[bit >> LOCK_USAGE_DIR_MASK](class);
 }
 
 typedef int (*check_usage_f)(struct task_struct *, struct held_lock *,
@@ -3146,7 +3245,7 @@ void lockdep_hardirqs_on(unsigned long ip)
         /*
          * See the fine text that goes along with this variable definition.
          */
-        if (DEBUG_LOCKS_WARN_ON(unlikely(early_boot_irqs_disabled)))
+        if (DEBUG_LOCKS_WARN_ON(early_boot_irqs_disabled))
                 return;
 
         /*