[PATCH 0/3] lockdep: liblockdep: Prevent chain_key collisions

[PATCH 0/3] lockdep: liblockdep: Prevent chain_key collisions

[Alfredo Alvarez Fernandez]

This patch series prevents possible collisions in the chain_key
hashing macro iterate_chain_key(key1, key2) that can lead to lockdep 
not detecting very simple deadlocks such as AA or ABBA.

The problem only affects the first allocated lock classes. That could 
explain why it was not seen while running lockdep's test suite, since
by the time the test suite runs there are already registered lock 
classes and the indexes allocated for the lock classes under test are
high enough to avoid collisions.

The patch series also extends the tools/liblockdep test suite with 
tests covering the offending cases.

I came across the problem while testing a simple AA deadlock scenario
in userspace using a pthread_mutex and tools/liblockdep. In that 
context it is fairly easy to have a clean and deterministic initial 
state where the problem can be reproduced.

The proposed solution was tested with the newly introduced tests and
also with lockdep's test suite:
 [    0.000000] Good, all 253 testcases passed! |

Alfredo Alvarez Fernandez (3):
  tools/liblockdep: add userspace version of READ_ONCE
  tools/liblockdep: add tests
  lockdep: prevent chain_key collisions

 kernel/locking/lockdep.c                    | 14 ++++------
 tools/lib/lockdep/tests/AA.c                |  8 +++---
 tools/lib/lockdep/tests/ABA.c               | 13 +++++++++
 tools/lib/lockdep/tests/ABBA_2threads.c     | 43 +++++++++++++++++++++++++++++
 tools/lib/lockdep/uinclude/linux/compiler.h |  1 +
 5 files changed, 67 insertions(+), 12 deletions(-)
 create mode 100644 tools/lib/lockdep/tests/ABA.c
 create mode 100644 tools/lib/lockdep/tests/ABBA_2threads.c

-- 
2.5.0

[PATCH 1/3] tools/liblockdep: add userspace version of READ_ONCE

[Alfredo Alvarez Fernandez]

From: Alfredo Alvarez Fernandez <alfredoalvarezfernandez@gmail.com>

This was added to the kernel code in 1658d35ead5d ("list: Use
READ_ONCE() when testing for empty lists")
There's nothing special we need to do about it in userspace.

Signed-off-by: Alfredo Alvarez Fernandez <alfredoalvarezfernandez@gmail.com>
---
 tools/lib/lockdep/uinclude/linux/compiler.h | 1 +
 1 file changed, 1 insertion(+)

diff --git a/tools/lib/lockdep/uinclude/linux/compiler.h b/tools/lib/lockdep/uinclude/linux/compiler.h
index 6386dc3..fd3e56a 100644
--- a/tools/lib/lockdep/uinclude/linux/compiler.h
+++ b/tools/lib/lockdep/uinclude/linux/compiler.h
@@ -3,6 +3,7 @@
 
 #define __used		__attribute__((__unused__))
 #define unlikely
+#define READ_ONCE(x) (x)
 #define WRITE_ONCE(x, val) x=(val)
 #define RCU_INIT_POINTER(p, v) p=(v)
 
-- 
2.5.0

[PATCH 2/3] tools/liblockdep: add tests

[Alfredo Alvarez Fernandez]

From: Alfredo Alvarez Fernandez <alfredoalvarezfernandez@gmail.com>

Add test for AA and 2 threaded ABBA locking.

Rename AA.c to ABA.c since it was implementing an ABA instead of a pure
AA. Now both cases are covered.

The expected output for AA.c is that the process blocks and lockdep
reports a deadlock.

ABBA_2threads.c differs from ABBA.c in that lockdep keeps separate chains
of held locks per task. This can lead to different behaviour regarding
lock detection. The expected output for this test is that the process
blocks and lockdep reports a circular locking dependency.

Signed-off-by: Alfredo Alvarez Fernandez <alfredoalvarezfernandez@gmail.com>
---
 tools/lib/lockdep/tests/AA.c            |  8 +++---
 tools/lib/lockdep/tests/ABA.c           | 13 ++++++++++
 tools/lib/lockdep/tests/ABBA_2threads.c | 43 +++++++++++++++++++++++++++++++++
 3 files changed, 60 insertions(+), 4 deletions(-)
 create mode 100644 tools/lib/lockdep/tests/ABA.c
 create mode 100644 tools/lib/lockdep/tests/ABBA_2threads.c

diff --git a/tools/lib/lockdep/tests/AA.c b/tools/lib/lockdep/tests/AA.c
index 0f782ff..18211a5 100644
--- a/tools/lib/lockdep/tests/AA.c
+++ b/tools/lib/lockdep/tests/AA.c
@@ -1,13 +1,13 @@
 #include <liblockdep/mutex.h>
 
-void main(void)
+int main(void)
 {
-	pthread_mutex_t a, b;
+	pthread_mutex_t a;
 
 	pthread_mutex_init(&a, NULL);
-	pthread_mutex_init(&b, NULL);
 
 	pthread_mutex_lock(&a);
-	pthread_mutex_lock(&b);
 	pthread_mutex_lock(&a);
+
+	return 0;
 }
diff --git a/tools/lib/lockdep/tests/ABA.c b/tools/lib/lockdep/tests/ABA.c
new file mode 100644
index 0000000..0f782ff
--- /dev/null
+++ b/tools/lib/lockdep/tests/ABA.c
@@ -0,0 +1,13 @@
+#include <liblockdep/mutex.h>
+
+void main(void)
+{
+	pthread_mutex_t a, b;
+
+	pthread_mutex_init(&a, NULL);
+	pthread_mutex_init(&b, NULL);
+
+	pthread_mutex_lock(&a);
+	pthread_mutex_lock(&b);
+	pthread_mutex_lock(&a);
+}
diff --git a/tools/lib/lockdep/tests/ABBA_2threads.c b/tools/lib/lockdep/tests/ABBA_2threads.c
new file mode 100644
index 0000000..62b759c
--- /dev/null
+++ b/tools/lib/lockdep/tests/ABBA_2threads.c
@@ -0,0 +1,43 @@
+#include <stdio.h>
+#include <pthread.h>
+
+pthread_mutex_t a = PTHREAD_MUTEX_INITIALIZER;
+pthread_mutex_t b = PTHREAD_MUTEX_INITIALIZER;
+pthread_barrier_t bar;
+
+void* ba_lock(void *arg) {
+	int ret, i;
+	pthread_mutex_lock(&b);
+
+	if (pthread_barrier_wait(&bar) == PTHREAD_BARRIER_SERIAL_THREAD)
+	    pthread_barrier_destroy(&bar);
+
+	pthread_mutex_lock(&a);
+
+	pthread_mutex_unlock(&a);
+	pthread_mutex_unlock(&b);
+}
+
+int main(void)
+{
+	pthread_t t;
+	pthread_barrier_init(&bar, NULL, 2);
+
+	if (pthread_create(&t, NULL, ba_lock, NULL)) {
+		fprintf(stderr, "pthread_create() failed\n");
+		return 1;
+	}
+	pthread_mutex_lock(&a);
+
+	if (pthread_barrier_wait(&bar) == PTHREAD_BARRIER_SERIAL_THREAD)
+	    pthread_barrier_destroy(&bar);
+
+	pthread_mutex_lock(&b);
+
+	pthread_mutex_unlock(&b);
+	pthread_mutex_unlock(&a);
+
+	pthread_join(t, NULL);
+
+	return 0;
+}
-- 
2.5.0

[PATCH 3/3] lockdep: prevent chain_key collisions

[Alfredo Alvarez Fernandez]

From: Alfredo Alvarez Fernandez <alfredoalvarezfernandez@gmail.com>

The chain_key hashing macro iterate_chain_key(key1, key2) does not
generate a new different value if both key1 and key2 are 0. In that
case the generated value is again 0. This can lead to collisions which
can result in lockdep not detecting deadlocks or circular
dependencies.

Avoid the problem by using class_idx (1-based) instead of class id
(0-based) as an input for the hashing macro 'key2' in
iterate_chain_key(key1, key2).

The use of class id created collisions in cases like the following:

1.- Consider an initial state in which no class has been acquired yet.
Under these circumstances an AA deadlock will not be detected by
lockdep:

  lock  [key1,key2]->new key  (key1=old chain_key, key2=id)
  --------------------------
  A     [0,0]->0
  A     [0,0]->0 (collision)

  The newly generated chain_key collides with the one used before and as
  a result the check for a deadlock is skipped

  A simple test using liblockdep and a pthread mutex confirms the
  problem: (omitting stack traces)

    new class 0xe15038: 0x7ffc64950f20
    acquire class [0xe15038] 0x7ffc64950f20
    acquire class [0xe15038] 0x7ffc64950f20
    hash chain already cached, key: 0000000000000000 tail class:
    [0xe15038] 0x7ffc64950f20

2.- Consider an ABBA in 2 different tasks and no class yet acquired.

  T1 [key1,key2]->new key     T2[key1,key2]->new key
  --                          --
  A [0,0]->0

                              B [0,1]->1

  B [0,1]->1  (collision)

                              A

  In this case the collision prevents lockdep from creating the new
dependency A->B. This in turn results in lockdep not detecting the
circular dependency when T2 acquires A.
---
 kernel/locking/lockdep.c | 14 ++++++--------
 1 file changed, 6 insertions(+), 8 deletions(-)

diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index 60ace56..163657b 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -2168,7 +2168,7 @@ static void check_chain_key(struct task_struct *curr)
 {
 #ifdef CONFIG_DEBUG_LOCKDEP
 	struct held_lock *hlock, *prev_hlock = NULL;
-	unsigned int i, id;
+	unsigned int i;
 	u64 chain_key = 0;
 
 	for (i = 0; i < curr->lockdep_depth; i++) {
@@ -2185,17 +2185,16 @@ static void check_chain_key(struct task_struct *curr)
 				(unsigned long long)hlock->prev_chain_key);
 			return;
 		}
-		id = hlock->class_idx - 1;
 		/*
 		 * Whoops ran out of static storage again?
 		 */
-		if (DEBUG_LOCKS_WARN_ON(id >= MAX_LOCKDEP_KEYS))
+		if (DEBUG_LOCKS_WARN_ON(hlock->class_idx > MAX_LOCKDEP_KEYS))
 			return;
 
 		if (prev_hlock && (prev_hlock->irq_context !=
 							hlock->irq_context))
 			chain_key = 0;
-		chain_key = iterate_chain_key(chain_key, id);
+		chain_key = iterate_chain_key(chain_key, hlock->class_idx);
 		prev_hlock = hlock;
 	}
 	if (chain_key != curr->curr_chain_key) {
@@ -3073,7 +3072,7 @@ static int __lock_acquire(struct lockdep_map *lock, unsigned int subclass,
 	struct task_struct *curr = current;
 	struct lock_class *class = NULL;
 	struct held_lock *hlock;
-	unsigned int depth, id;
+	unsigned int depth;
 	int chain_head = 0;
 	int class_idx;
 	u64 chain_key;
@@ -3176,11 +3175,10 @@ static int __lock_acquire(struct lockdep_map *lock, unsigned int subclass,
 	 * The 'key ID' is what is the most compact key value to drive
 	 * the hash, not class->key.
 	 */
-	id = class - lock_classes;
 	/*
 	 * Whoops, we did it again.. ran straight out of our static allocation.
 	 */
-	if (DEBUG_LOCKS_WARN_ON(id >= MAX_LOCKDEP_KEYS))
+	if (DEBUG_LOCKS_WARN_ON(class_idx > MAX_LOCKDEP_KEYS))
 		return 0;
 
 	chain_key = curr->curr_chain_key;
@@ -3198,7 +3196,7 @@ static int __lock_acquire(struct lockdep_map *lock, unsigned int subclass,
 		chain_key = 0;
 		chain_head = 1;
 	}
-	chain_key = iterate_chain_key(chain_key, id);
+	chain_key = iterate_chain_key(chain_key, class_idx);
 
 	if (nest_lock && !__lock_is_held(nest_lock))
 		return print_lock_nested_lock_not_held(curr, hlock, ip);
-- 
2.5.0

Re: [PATCH 1/3] tools/liblockdep: add userspace version of READ_ONCE

[Peter Zijlstra]

On Thu, Feb 11, 2016 at 12:33:30AM +0100, Alfredo Alvarez Fernandez wrote:
> From: Alfredo Alvarez Fernandez <alfredoalvarezfernandez@gmail.com>
> 
> This was added to the kernel code in 1658d35ead5d ("list: Use
> READ_ONCE() when testing for empty lists")
> There's nothing special we need to do about it in userspace.
> 
> Signed-off-by: Alfredo Alvarez Fernandez <alfredoalvarezfernandez@gmail.com>
> ---
>  tools/lib/lockdep/uinclude/linux/compiler.h | 1 +
>  1 file changed, 1 insertion(+)
> 
> diff --git a/tools/lib/lockdep/uinclude/linux/compiler.h b/tools/lib/lockdep/uinclude/linux/compiler.h
> index 6386dc3..fd3e56a 100644
> --- a/tools/lib/lockdep/uinclude/linux/compiler.h
> +++ b/tools/lib/lockdep/uinclude/linux/compiler.h
> @@ -3,6 +3,7 @@
>  
>  #define __used		__attribute__((__unused__))
>  #define unlikely
> +#define READ_ONCE(x) (x)
>  #define WRITE_ONCE(x, val) x=(val)

I would argue we'd still very much want the volatile cast for both READ
and WRITE_ONCE().

Why do these things have different semantics between user and kernel
space?

Re: [PATCH 1/3] tools/liblockdep: add userspace version of READ_ONCE

[Sasha Levin]

On 02/11/2016 10:16 AM, Peter Zijlstra wrote:
> On Thu, Feb 11, 2016 at 12:33:30AM +0100, Alfredo Alvarez Fernandez wrote:
>> From: Alfredo Alvarez Fernandez <alfredoalvarezfernandez@gmail.com>
>>
>> This was added to the kernel code in 1658d35ead5d ("list: Use
>> READ_ONCE() when testing for empty lists")
>> There's nothing special we need to do about it in userspace.
>>
>> Signed-off-by: Alfredo Alvarez Fernandez <alfredoalvarezfernandez@gmail.com>
>> ---
>>  tools/lib/lockdep/uinclude/linux/compiler.h | 1 +
>>  1 file changed, 1 insertion(+)
>>
>> diff --git a/tools/lib/lockdep/uinclude/linux/compiler.h b/tools/lib/lockdep/uinclude/linux/compiler.h
>> index 6386dc3..fd3e56a 100644
>> --- a/tools/lib/lockdep/uinclude/linux/compiler.h
>> +++ b/tools/lib/lockdep/uinclude/linux/compiler.h
>> @@ -3,6 +3,7 @@
>>  
>>  #define __used		__attribute__((__unused__))
>>  #define unlikely
>> +#define READ_ONCE(x) (x)
>>  #define WRITE_ONCE(x, val) x=(val)
> 
> I would argue we'd still very much want the volatile cast for both READ
> and WRITE_ONCE().
> 
> Why do these things have different semantics between user and kernel
> space?

You're right. I'll send a patch.


Thanks,
Sasha

Re: [PATCH 0/3] lockdep: liblockdep: Prevent chain_key collisions

[Sasha Levin]

On 02/10/2016 06:33 PM, Alfredo Alvarez Fernandez wrote:
> This patch series prevents possible collisions in the chain_key
> hashing macro iterate_chain_key(key1, key2) that can lead to lockdep 
> not detecting very simple deadlocks such as AA or ABBA.
> 
> The problem only affects the first allocated lock classes. That could 
> explain why it was not seen while running lockdep's test suite, since
> by the time the test suite runs there are already registered lock 
> classes and the indexes allocated for the lock classes under test are
> high enough to avoid collisions.
> 
> The patch series also extends the tools/liblockdep test suite with 
> tests covering the offending cases.
> 
> I came across the problem while testing a simple AA deadlock scenario
> in userspace using a pthread_mutex and tools/liblockdep. In that 
> context it is fairly easy to have a clean and deterministic initial 
> state where the problem can be reproduced.
> 
> The proposed solution was tested with the newly introduced tests and
> also with lockdep's test suite:
>  [    0.000000] Good, all 253 testcases passed! |

Thanks Alfredo, I'll grab the first two.

Peter/Ingo, will you take the lockdep one or do you want it to go through
my tree?


Thanks,
Sasha

Re: [PATCH 0/3] lockdep: liblockdep: Prevent chain_key collisions

[Peter Zijlstra]

On Tue, Feb 16, 2016 at 11:38:26AM -0500, Sasha Levin wrote:
> Peter/Ingo, will you take the lockdep one or do you want it to go through
> my tree?

I've got the lockdep one. Thanks!

Re: [PATCH 3/3] lockdep: prevent chain_key collisions

[Ingo Molnar]

* Alfredo Alvarez Fernandez <alfredoalvarezfernandez@gmail.com> wrote:

> From: Alfredo Alvarez Fernandez <alfredoalvarezfernandez@gmail.com>
> 
> The chain_key hashing macro iterate_chain_key(key1, key2) does not
> generate a new different value if both key1 and key2 are 0. In that
> case the generated value is again 0. This can lead to collisions which
> can result in lockdep not detecting deadlocks or circular
> dependencies.
> 
> Avoid the problem by using class_idx (1-based) instead of class id
> (0-based) as an input for the hashing macro 'key2' in
> iterate_chain_key(key1, key2).
> 
> The use of class id created collisions in cases like the following:

Nice find!

> 1.- Consider an initial state in which no class has been acquired yet.
> Under these circumstances an AA deadlock will not be detected by
> lockdep:
> 
>   lock  [key1,key2]->new key  (key1=old chain_key, key2=id)
>   --------------------------
>   A     [0,0]->0
>   A     [0,0]->0 (collision)
> 
>   The newly generated chain_key collides with the one used before and as
>   a result the check for a deadlock is skipped
> 
>   A simple test using liblockdep and a pthread mutex confirms the
>   problem: (omitting stack traces)
> 
>     new class 0xe15038: 0x7ffc64950f20
>     acquire class [0xe15038] 0x7ffc64950f20
>     acquire class [0xe15038] 0x7ffc64950f20
>     hash chain already cached, key: 0000000000000000 tail class:
>     [0xe15038] 0x7ffc64950f20
> 
> 2.- Consider an ABBA in 2 different tasks and no class yet acquired.
> 
>   T1 [key1,key2]->new key     T2[key1,key2]->new key
>   --                          --
>   A [0,0]->0
> 
>                               B [0,1]->1
> 
>   B [0,1]->1  (collision)
> 
>                               A
> 
>   In this case the collision prevents lockdep from creating the new
> dependency A->B. This in turn results in lockdep not detecting the
> circular dependency when T2 acquires A.

So this is pretty fatal result - and it was not found for years!

Could you please also do a follow up fix, to treat hash collisions as hard errors 
and shut up lockdep an report the bug?

Thanks,

	Ingo

[PATCH v2 0/3] lockdep: liblockdep: Prevent chain_key collisions

[Alfredo Alvarez Fernandez]

This patch series prevents possible collisions in the chain_key
hashing macro iterate_chain_key(key1, key2) that can lead to lockdep
not detecting very simple deadlocks such as AA or ABBA.

The problem only affects the first allocated lock classes. That could
explain why it was not seen while running lockdep's test suite, since
by the time the test suite runs there are already registered lock
classes and the indexes allocated for the lock classes under test are
high enough to avoid collisions.

The patch series also extends the tools/liblockdep test suite with
tests covering the offending cases.

I came across the problem while testing a simple AA deadlock scenario
in userspace using a pthread_mutex and tools/liblockdep. In that
context it is fairly easy to have a clean and deterministic initial
state where the problem can be reproduced.

The proposed solution was tested with the newly introduced tests and
also with lockdep's test suite:
 [    0.000000] Good, all 253 testcases passed! |

v2:
  - Add detection for chain_key collisions under CONFIG_DEBUG_LOCKDEP.
    When a collision is detected the problem is reported and all lock
    debugging is turned off.

    Tested using liblockdep and the added tests before and after
    applying the fix, confirming both that the code added for the
    detection correctly reports the problem and that the fix actually
    fixes it.

    Tested tweaking lockdep to generate false collisions and
    verified that the problem is reported and that lock debugging is 
    turned off.

    Also tested with lockdep's test suite after applying the patch:
    [    0.000000] Good, all 253 testcases passed! |

  - Fix code style problems in added liblockdep tests

Alfredo Alvarez Fernandez (3):
  tools/liblockdep: add userspace version of READ_ONCE
  tools/liblockdep: add tests
  lockdep: prevent and detect chain_key collisions

 kernel/locking/lockdep.c                    | 73 ++++++++++++++++++++++-------
 tools/lib/lockdep/tests/AA.c                |  8 ++--
 tools/lib/lockdep/tests/ABA.c               | 13 +++++
 tools/lib/lockdep/tests/ABBA_2threads.c     | 46 ++++++++++++++++++
 tools/lib/lockdep/uinclude/linux/compiler.h |  1 +
 5 files changed, 121 insertions(+), 20 deletions(-)
 create mode 100644 tools/lib/lockdep/tests/ABA.c
 create mode 100644 tools/lib/lockdep/tests/ABBA_2threads.c

-- 
2.5.0

[PATCH v2 1/3] tools/liblockdep: add userspace version of READ_ONCE

[Alfredo Alvarez Fernandez]

From: Alfredo Alvarez Fernandez <alfredoalvarezfernandez@gmail.com>

This was added to the kernel code in <1658d35ead5d> ("list: Use
READ_ONCE() when testing for empty lists")
There's nothing special we need to do about it in userspace.

Signed-off-by: Alfredo Alvarez Fernandez <alfredoalvarezfernandez@gmail.com>
---
 tools/lib/lockdep/uinclude/linux/compiler.h | 1 +
 1 file changed, 1 insertion(+)

diff --git a/tools/lib/lockdep/uinclude/linux/compiler.h b/tools/lib/lockdep/uinclude/linux/compiler.h
index 6386dc3..fd3e56a 100644
--- a/tools/lib/lockdep/uinclude/linux/compiler.h
+++ b/tools/lib/lockdep/uinclude/linux/compiler.h
@@ -3,6 +3,7 @@
 
 #define __used		__attribute__((__unused__))
 #define unlikely
+#define READ_ONCE(x) (x)
 #define WRITE_ONCE(x, val) x=(val)
 #define RCU_INIT_POINTER(p, v) p=(v)
 
-- 
2.5.0

[PATCH v2 2/3] tools/liblockdep: add tests

[Alfredo Alvarez Fernandez]

From: Alfredo Alvarez Fernandez <alfredoalvarezfernandez@gmail.com>

Add test for AA and 2 threaded ABBA locking.

Rename AA.c to ABA.c since it was implementing an ABA instead of a pure
AA. Now both cases are covered.

The expected output for AA.c is that the process blocks and lockdep
reports a deadlock.

ABBA_2threads.c differs from ABBA.c in that lockdep keeps separate chains
of held locks per task. This can lead to different behaviour regarding
lock detection. The expected output for this test is that the process
blocks and lockdep reports a circular locking dependency.

Signed-off-by: Alfredo Alvarez Fernandez <alfredoalvarezfernandez@gmail.com>
---
Changes in v2:
  - Fix style problems in added tests

 tools/lib/lockdep/tests/AA.c            |  8 +++---
 tools/lib/lockdep/tests/ABA.c           | 13 ++++++++++
 tools/lib/lockdep/tests/ABBA_2threads.c | 46 +++++++++++++++++++++++++++++++++
 3 files changed, 63 insertions(+), 4 deletions(-)
 create mode 100644 tools/lib/lockdep/tests/ABA.c
 create mode 100644 tools/lib/lockdep/tests/ABBA_2threads.c

diff --git a/tools/lib/lockdep/tests/AA.c b/tools/lib/lockdep/tests/AA.c
index 0f782ff..18211a5 100644
--- a/tools/lib/lockdep/tests/AA.c
+++ b/tools/lib/lockdep/tests/AA.c
@@ -1,13 +1,13 @@
 #include <liblockdep/mutex.h>
 
-void main(void)
+int main(void)
 {
-	pthread_mutex_t a, b;
+	pthread_mutex_t a;
 
 	pthread_mutex_init(&a, NULL);
-	pthread_mutex_init(&b, NULL);
 
 	pthread_mutex_lock(&a);
-	pthread_mutex_lock(&b);
 	pthread_mutex_lock(&a);
+
+	return 0;
 }
diff --git a/tools/lib/lockdep/tests/ABA.c b/tools/lib/lockdep/tests/ABA.c
new file mode 100644
index 0000000..0f782ff
--- /dev/null
+++ b/tools/lib/lockdep/tests/ABA.c
@@ -0,0 +1,13 @@
+#include <liblockdep/mutex.h>
+
+void main(void)
+{
+	pthread_mutex_t a, b;
+
+	pthread_mutex_init(&a, NULL);
+	pthread_mutex_init(&b, NULL);
+
+	pthread_mutex_lock(&a);
+	pthread_mutex_lock(&b);
+	pthread_mutex_lock(&a);
+}
diff --git a/tools/lib/lockdep/tests/ABBA_2threads.c b/tools/lib/lockdep/tests/ABBA_2threads.c
new file mode 100644
index 0000000..cd807d7
--- /dev/null
+++ b/tools/lib/lockdep/tests/ABBA_2threads.c
@@ -0,0 +1,46 @@
+#include <stdio.h>
+#include <pthread.h>
+
+pthread_mutex_t a = PTHREAD_MUTEX_INITIALIZER;
+pthread_mutex_t b = PTHREAD_MUTEX_INITIALIZER;
+pthread_barrier_t bar;
+
+void *ba_lock(void *arg)
+{
+	int ret, i;
+
+	pthread_mutex_lock(&b);
+
+	if (pthread_barrier_wait(&bar) == PTHREAD_BARRIER_SERIAL_THREAD)
+		pthread_barrier_destroy(&bar);
+
+	pthread_mutex_lock(&a);
+
+	pthread_mutex_unlock(&a);
+	pthread_mutex_unlock(&b);
+}
+
+int main(void)
+{
+	pthread_t t;
+
+	pthread_barrier_init(&bar, NULL, 2);
+
+	if (pthread_create(&t, NULL, ba_lock, NULL)) {
+		fprintf(stderr, "pthread_create() failed\n");
+		return 1;
+	}
+	pthread_mutex_lock(&a);
+
+	if (pthread_barrier_wait(&bar) == PTHREAD_BARRIER_SERIAL_THREAD)
+		pthread_barrier_destroy(&bar);
+
+	pthread_mutex_lock(&b);
+
+	pthread_mutex_unlock(&b);
+	pthread_mutex_unlock(&a);
+
+	pthread_join(t, NULL);
+
+	return 0;
+}
-- 
2.5.0

[PATCH v2 3/3] lockdep: prevent and detect chain_key collisions

[Alfredo Alvarez Fernandez]

From: Alfredo Alvarez Fernandez <alfredoalvarezfernandez@gmail.com>

The chain_key hashing macro iterate_chain_key(key1, key2) does not
generate a new different value if both key1 and key2 are 0. In that
case the generated value is again 0. This can lead to collisions which
can result in lockdep not detecting deadlocks or circular
dependencies.

Avoid the problem by using class_idx (1-based) instead of class id
(0-based) as an input for the hashing macro 'key2' in
iterate_chain_key(key1, key2).

The use of class id created collisions in cases like the following:

1.- Consider an initial state in which no class has been acquired yet.
Under these circumstances an AA deadlock will not be detected by
lockdep:

  lock  [key1,key2]->new key  (key1=old chain_key, key2=id)
  --------------------------
  A     [0,0]->0
  A     [0,0]->0 (collision)

  The newly generated chain_key collides with the one used before and as
  a result the check for a deadlock is skipped

  A simple test using liblockdep and a pthread mutex confirms the
  problem: (omitting stack traces)

    new class 0xe15038: 0x7ffc64950f20
    acquire class [0xe15038] 0x7ffc64950f20
    acquire class [0xe15038] 0x7ffc64950f20
    hash chain already cached, key: 0000000000000000 tail class:
    [0xe15038] 0x7ffc64950f20

2.- Consider an ABBA in 2 different tasks and no class yet acquired.

  T1 [key1,key2]->new key     T2[key1,key2]->new key
  --                          --
  A [0,0]->0

                              B [0,1]->1

  B [0,1]->1  (collision)

                              A

  In this case the collision prevents lockdep from creating the new
dependency A->B. This in turn results in lockdep not detecting the
circular dependency when T2 acquires A.

Add detection for chain_key collision under CONFIG_DEBUG_LOCKDEP.
When a collision is detected the problem is reported and all lock
debugging is turned off.

Signed-off-by: Alfredo Alvarez Fernandez <alfredoalvarezernandez@gmail.com>
---
Changes in v2:
  - Add detection for chain_key collisions under CONFIG_DEBUG_LOCKDEP.
    When a collision is detected the problem is reported and all lock
    debugging is turned off.

    Tested using liblockdep and the added tests before and after
    applying the fix, confirming both that the code added for the
    detection correctly reports the problem and that the fix actually
    fixes it.

    Tested tweaking lockdep to generate false collisions and
    verified that the problem is reported and that lock debugging is 
    turned off.

    Also tested with lockdep's test suite after applying the patch:
    [    0.000000] Good, all 253 testcases passed! |

 kernel/locking/lockdep.c | 73 +++++++++++++++++++++++++++++++++++++-----------
 1 file changed, 57 insertions(+), 16 deletions(-)

diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index 60ace56..2c28298 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -2007,6 +2007,53 @@ struct lock_class *lock_chain_get_class(struct lock_chain *chain, int i)
 }
 
 /*
+ * Returns the index of the first held_lock of the current chain
+ */
+static inline int get_first_held_lock(struct task_struct *curr,
+					struct held_lock *hlock)
+{
+	int i;
+	struct held_lock *hlock_curr;
+
+	for (i = curr->lockdep_depth - 1; i >= 0; i--) {
+		hlock_curr = curr->held_locks + i;
+		if (hlock_curr->irq_context != hlock->irq_context)
+			break;
+
+	}
+
+	return ++i;
+}
+
+/*
+ * Checks whether the chain and the current held locks are consistent
+ * in depth and also in content. If they are not it most likely means
+ * that there was a collision during the calculation of the chain_key.
+ * Returns: 0 not passed, 1 passed
+ */
+static int check_no_collision(struct task_struct *curr,
+			struct held_lock *hlock,
+			struct lock_chain *chain)
+{
+#ifdef CONFIG_DEBUG_LOCKDEP
+	int i, j, id;
+
+	i = get_first_held_lock(curr, hlock);
+
+	if (DEBUG_LOCKS_WARN_ON(chain->depth != curr->lockdep_depth - (i - 1)))
+		return 0;
+
+	for (j = 0; j < chain->depth - 1; j++, i++) {
+		id = curr->held_locks[i].class_idx - 1;
+
+		if (DEBUG_LOCKS_WARN_ON(chain_hlocks[chain->base + j] != id))
+			return 0;
+	}
+#endif
+	return 1;
+}
+
+/*
  * Look up a dependency chain. If the key is not present yet then
  * add it and return 1 - in this case the new dependency chain is
  * validated. If the key is already hashed, return 0.
@@ -2019,7 +2066,6 @@ static inline int lookup_chain_cache(struct task_struct *curr,
 	struct lock_class *class = hlock_class(hlock);
 	struct list_head *hash_head = chainhashentry(chain_key);
 	struct lock_chain *chain;
-	struct held_lock *hlock_curr;
 	int i, j;
 
 	/*
@@ -2037,6 +2083,9 @@ static inline int lookup_chain_cache(struct task_struct *curr,
 		if (chain->chain_key == chain_key) {
 cache_hit:
 			debug_atomic_inc(chain_lookup_hits);
+			if (!check_no_collision(curr, hlock, chain))
+				return 0;
+
 			if (very_verbose(class))
 				printk("\nhash chain already cached, key: "
 					"%016Lx tail class: [%p] %s\n",
@@ -2074,13 +2123,7 @@ cache_hit:
 	chain = lock_chains + nr_lock_chains++;
 	chain->chain_key = chain_key;
 	chain->irq_context = hlock->irq_context;
-	/* Find the first held_lock of current chain */
-	for (i = curr->lockdep_depth - 1; i >= 0; i--) {
-		hlock_curr = curr->held_locks + i;
-		if (hlock_curr->irq_context != hlock->irq_context)
-			break;
-	}
-	i++;
+	i = get_first_held_lock(curr, hlock);
 	chain->depth = curr->lockdep_depth + 1 - i;
 	if (likely(nr_chain_hlocks + chain->depth <= MAX_LOCKDEP_CHAIN_HLOCKS)) {
 		chain->base = nr_chain_hlocks;
@@ -2168,7 +2211,7 @@ static void check_chain_key(struct task_struct *curr)
 {
 #ifdef CONFIG_DEBUG_LOCKDEP
 	struct held_lock *hlock, *prev_hlock = NULL;
-	unsigned int i, id;
+	unsigned int i;
 	u64 chain_key = 0;
 
 	for (i = 0; i < curr->lockdep_depth; i++) {
@@ -2185,17 +2228,16 @@ static void check_chain_key(struct task_struct *curr)
 				(unsigned long long)hlock->prev_chain_key);
 			return;
 		}
-		id = hlock->class_idx - 1;
 		/*
 		 * Whoops ran out of static storage again?
 		 */
-		if (DEBUG_LOCKS_WARN_ON(id >= MAX_LOCKDEP_KEYS))
+		if (DEBUG_LOCKS_WARN_ON(hlock->class_idx > MAX_LOCKDEP_KEYS))
 			return;
 
 		if (prev_hlock && (prev_hlock->irq_context !=
 							hlock->irq_context))
 			chain_key = 0;
-		chain_key = iterate_chain_key(chain_key, id);
+		chain_key = iterate_chain_key(chain_key, hlock->class_idx);
 		prev_hlock = hlock;
 	}
 	if (chain_key != curr->curr_chain_key) {
@@ -3073,7 +3115,7 @@ static int __lock_acquire(struct lockdep_map *lock, unsigned int subclass,
 	struct task_struct *curr = current;
 	struct lock_class *class = NULL;
 	struct held_lock *hlock;
-	unsigned int depth, id;
+	unsigned int depth;
 	int chain_head = 0;
 	int class_idx;
 	u64 chain_key;
@@ -3176,11 +3218,10 @@ static int __lock_acquire(struct lockdep_map *lock, unsigned int subclass,
 	 * The 'key ID' is what is the most compact key value to drive
 	 * the hash, not class->key.
 	 */
-	id = class - lock_classes;
 	/*
 	 * Whoops, we did it again.. ran straight out of our static allocation.
 	 */
-	if (DEBUG_LOCKS_WARN_ON(id >= MAX_LOCKDEP_KEYS))
+	if (DEBUG_LOCKS_WARN_ON(class_idx > MAX_LOCKDEP_KEYS))
 		return 0;
 
 	chain_key = curr->curr_chain_key;
@@ -3198,7 +3239,7 @@ static int __lock_acquire(struct lockdep_map *lock, unsigned int subclass,
 		chain_key = 0;
 		chain_head = 1;
 	}
-	chain_key = iterate_chain_key(chain_key, id);
+	chain_key = iterate_chain_key(chain_key, class_idx);
 
 	if (nest_lock && !__lock_is_held(nest_lock))
 		return print_lock_nested_lock_not_held(curr, hlock, ip);
-- 
2.5.0

[tip:locking/core] tools/lib/lockdep: Add userspace version of READ_ONCE()

[tip-bot for Alfredo Alvarez Fernandez]

Commit-ID:  9d5a23ac8e0ede14a2b23740d231727ba5be483a
Gitweb:     http://git.kernel.org/tip/9d5a23ac8e0ede14a2b23740d231727ba5be483a
Author:     Alfredo Alvarez Fernandez <alfredoalvarezfernandez@gmail.com>
AuthorDate: Fri, 19 Feb 2016 07:48:51 +0100
Committer:  Ingo Molnar <mingo@kernel.org>
CommitDate: Mon, 29 Feb 2016 10:29:27 +0100

tools/lib/lockdep: Add userspace version of READ_ONCE()

This was added to the kernel code in <1658d35ead5d> ("list: Use
READ_ONCE() when testing for empty lists").

There's nothing special we need to do about it in userspace.

Signed-off-by: Alfredo Alvarez Fernandez <alfredoalvarezfernandez@gmail.com>
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: Sasha Levin <sasha.levin@oracle.com>
Cc: Thomas Gleixner <tglx@linutronix.de>
Link: http://lkml.kernel.org/r/1455864533-7536-2-git-send-email-alfredoalvarezernandez@gmail.com
Signed-off-by: Ingo Molnar <mingo@kernel.org>
---
 tools/lib/lockdep/uinclude/linux/compiler.h | 1 +
 1 file changed, 1 insertion(+)

diff --git a/tools/lib/lockdep/uinclude/linux/compiler.h b/tools/lib/lockdep/uinclude/linux/compiler.h
index 6386dc3..fd3e56a 100644
--- a/tools/lib/lockdep/uinclude/linux/compiler.h
+++ b/tools/lib/lockdep/uinclude/linux/compiler.h
@@ -3,6 +3,7 @@
 
 #define __used		__attribute__((__unused__))
 #define unlikely
+#define READ_ONCE(x) (x)
 #define WRITE_ONCE(x, val) x=(val)
 #define RCU_INIT_POINTER(p, v) p=(v)
 

[tip:locking/core] tools/lib/lockdep: Add tests for AA and ABBA locking

[tip-bot for Alfredo Alvarez Fernandez]

Commit-ID:  11a1ac206d0806b0db39712c3292f6006e77a7e8
Gitweb:     http://git.kernel.org/tip/11a1ac206d0806b0db39712c3292f6006e77a7e8
Author:     Alfredo Alvarez Fernandez <alfredoalvarezfernandez@gmail.com>
AuthorDate: Fri, 19 Feb 2016 07:48:52 +0100
Committer:  Ingo Molnar <mingo@kernel.org>
CommitDate: Mon, 29 Feb 2016 10:29:33 +0100

tools/lib/lockdep: Add tests for AA and ABBA locking

Add test for AA and 2 threaded ABBA locking.

Rename AA.c to ABA.c since it was implementing an ABA instead of a pure
AA. Now both cases are covered.

The expected output for AA.c is that the process blocks and lockdep
reports a deadlock.

ABBA_2threads.c differs from ABBA.c in that lockdep keeps separate chains
of held locks per task. This can lead to different behaviour regarding
lock detection. The expected output for this test is that the process
blocks and lockdep reports a circular locking dependency.

These tests found a lockdep bug - fixed by the next commit.

Signed-off-by: Alfredo Alvarez Fernandez <alfredoalvarezfernandez@gmail.com>
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: Sasha Levin <sasha.levin@oracle.com>
Cc: Thomas Gleixner <tglx@linutronix.de>
Link: http://lkml.kernel.org/r/1455864533-7536-3-git-send-email-alfredoalvarezernandez@gmail.com
Signed-off-by: Ingo Molnar <mingo@kernel.org>
---
 tools/lib/lockdep/tests/AA.c            |  8 +++---
 tools/lib/lockdep/tests/{AA.c => ABA.c} |  0
 tools/lib/lockdep/tests/ABBA_2threads.c | 46 +++++++++++++++++++++++++++++++++
 3 files changed, 50 insertions(+), 4 deletions(-)

diff --git a/tools/lib/lockdep/tests/AA.c b/tools/lib/lockdep/tests/AA.c
index 0f782ff..18211a5 100644
--- a/tools/lib/lockdep/tests/AA.c
+++ b/tools/lib/lockdep/tests/AA.c
@@ -1,13 +1,13 @@
 #include <liblockdep/mutex.h>
 
-void main(void)
+int main(void)
 {
-	pthread_mutex_t a, b;
+	pthread_mutex_t a;
 
 	pthread_mutex_init(&a, NULL);
-	pthread_mutex_init(&b, NULL);
 
 	pthread_mutex_lock(&a);
-	pthread_mutex_lock(&b);
 	pthread_mutex_lock(&a);
+
+	return 0;
 }
diff --git a/tools/lib/lockdep/tests/AA.c b/tools/lib/lockdep/tests/ABA.c
similarity index 100%
copy from tools/lib/lockdep/tests/AA.c
copy to tools/lib/lockdep/tests/ABA.c
diff --git a/tools/lib/lockdep/tests/ABBA_2threads.c b/tools/lib/lockdep/tests/ABBA_2threads.c
new file mode 100644
index 0000000..cd807d7
--- /dev/null
+++ b/tools/lib/lockdep/tests/ABBA_2threads.c
@@ -0,0 +1,46 @@
+#include <stdio.h>
+#include <pthread.h>
+
+pthread_mutex_t a = PTHREAD_MUTEX_INITIALIZER;
+pthread_mutex_t b = PTHREAD_MUTEX_INITIALIZER;
+pthread_barrier_t bar;
+
+void *ba_lock(void *arg)
+{
+	int ret, i;
+
+	pthread_mutex_lock(&b);
+
+	if (pthread_barrier_wait(&bar) == PTHREAD_BARRIER_SERIAL_THREAD)
+		pthread_barrier_destroy(&bar);
+
+	pthread_mutex_lock(&a);
+
+	pthread_mutex_unlock(&a);
+	pthread_mutex_unlock(&b);
+}
+
+int main(void)
+{
+	pthread_t t;
+
+	pthread_barrier_init(&bar, NULL, 2);
+
+	if (pthread_create(&t, NULL, ba_lock, NULL)) {
+		fprintf(stderr, "pthread_create() failed\n");
+		return 1;
+	}
+	pthread_mutex_lock(&a);
+
+	if (pthread_barrier_wait(&bar) == PTHREAD_BARRIER_SERIAL_THREAD)
+		pthread_barrier_destroy(&bar);
+
+	pthread_mutex_lock(&b);
+
+	pthread_mutex_unlock(&b);
+	pthread_mutex_unlock(&a);
+
+	pthread_join(t, NULL);
+
+	return 0;
+}

[tip:locking/core] locking/lockdep: Prevent chain_key collisions

[tip-bot for Alfredo Alvarez Fernandez]

Commit-ID:  5f18ab5c6bdba735b31a1e7c2618f48eae6b1b5c
Gitweb:     http://git.kernel.org/tip/5f18ab5c6bdba735b31a1e7c2618f48eae6b1b5c
Author:     Alfredo Alvarez Fernandez <alfredoalvarezfernandez@gmail.com>
AuthorDate: Thu, 11 Feb 2016 00:33:32 +0100
Committer:  Ingo Molnar <mingo@kernel.org>
CommitDate: Mon, 29 Feb 2016 10:32:29 +0100

locking/lockdep: Prevent chain_key collisions

The chain_key hashing macro iterate_chain_key(key1, key2) does not
generate a new different value if both key1 and key2 are 0. In that
case the generated value is again 0. This can lead to collisions which
can result in lockdep not detecting deadlocks or circular
dependencies.

Avoid the problem by using class_idx (1-based) instead of class id
(0-based) as an input for the hashing macro 'key2' in
iterate_chain_key(key1, key2).

The use of class id created collisions in cases like the following:

1.- Consider an initial state in which no class has been acquired yet.
Under these circumstances an AA deadlock will not be detected by
lockdep:

  lock  [key1,key2]->new key  (key1=old chain_key, key2=id)
  --------------------------
  A     [0,0]->0
  A     [0,0]->0 (collision)

  The newly generated chain_key collides with the one used before and as
  a result the check for a deadlock is skipped

  A simple test using liblockdep and a pthread mutex confirms the
  problem: (omitting stack traces)

    new class 0xe15038: 0x7ffc64950f20
    acquire class [0xe15038] 0x7ffc64950f20
    acquire class [0xe15038] 0x7ffc64950f20
    hash chain already cached, key: 0000000000000000 tail class:
    [0xe15038] 0x7ffc64950f20

2.- Consider an ABBA in 2 different tasks and no class yet acquired.

  T1 [key1,key2]->new key     T2[key1,key2]->new key
  --                          --
  A [0,0]->0

                              B [0,1]->1

  B [0,1]->1  (collision)

                              A

In this case the collision prevents lockdep from creating the new
dependency A->B. This in turn results in lockdep not detecting the
circular dependency when T2 acquires A.

Signed-off-by: Alfredo Alvarez Fernandez <alfredoalvarezernandez@gmail.com>
Signed-off-by: Peter 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: sasha.levin@oracle.com
Link: http://lkml.kernel.org/r/1455147212-2389-4-git-send-email-alfredoalvarezernandez@gmail.com
Signed-off-by: Ingo Molnar <mingo@kernel.org>
---
 kernel/locking/lockdep.c | 14 ++++++--------
 1 file changed, 6 insertions(+), 8 deletions(-)

diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index 3261214..6f446eb 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -2143,7 +2143,7 @@ static void check_chain_key(struct task_struct *curr)
 {
 #ifdef CONFIG_DEBUG_LOCKDEP
 	struct held_lock *hlock, *prev_hlock = NULL;
-	unsigned int i, id;
+	unsigned int i;
 	u64 chain_key = 0;
 
 	for (i = 0; i < curr->lockdep_depth; i++) {
@@ -2160,17 +2160,16 @@ static void check_chain_key(struct task_struct *curr)
 				(unsigned long long)hlock->prev_chain_key);
 			return;
 		}
-		id = hlock->class_idx - 1;
 		/*
 		 * Whoops ran out of static storage again?
 		 */
-		if (DEBUG_LOCKS_WARN_ON(id >= MAX_LOCKDEP_KEYS))
+		if (DEBUG_LOCKS_WARN_ON(hlock->class_idx > MAX_LOCKDEP_KEYS))
 			return;
 
 		if (prev_hlock && (prev_hlock->irq_context !=
 							hlock->irq_context))
 			chain_key = 0;
-		chain_key = iterate_chain_key(chain_key, id);
+		chain_key = iterate_chain_key(chain_key, hlock->class_idx);
 		prev_hlock = hlock;
 	}
 	if (chain_key != curr->curr_chain_key) {
@@ -3048,7 +3047,7 @@ static int __lock_acquire(struct lockdep_map *lock, unsigned int subclass,
 	struct task_struct *curr = current;
 	struct lock_class *class = NULL;
 	struct held_lock *hlock;
-	unsigned int depth, id;
+	unsigned int depth;
 	int chain_head = 0;
 	int class_idx;
 	u64 chain_key;
@@ -3151,11 +3150,10 @@ static int __lock_acquire(struct lockdep_map *lock, unsigned int subclass,
 	 * The 'key ID' is what is the most compact key value to drive
 	 * the hash, not class->key.
 	 */
-	id = class - lock_classes;
 	/*
 	 * Whoops, we did it again.. ran straight out of our static allocation.
 	 */
-	if (DEBUG_LOCKS_WARN_ON(id >= MAX_LOCKDEP_KEYS))
+	if (DEBUG_LOCKS_WARN_ON(class_idx > MAX_LOCKDEP_KEYS))
 		return 0;
 
 	chain_key = curr->curr_chain_key;
@@ -3173,7 +3171,7 @@ static int __lock_acquire(struct lockdep_map *lock, unsigned int subclass,
 		chain_key = 0;
 		chain_head = 1;
 	}
-	chain_key = iterate_chain_key(chain_key, id);
+	chain_key = iterate_chain_key(chain_key, class_idx);
 
 	if (nest_lock && !__lock_is_held(nest_lock))
 		return print_lock_nested_lock_not_held(curr, hlock, ip);

[tip:locking/core] locking/lockdep: Detect chain_key collisions

[tip-bot for Ingo Molnar]

Commit-ID:  9e4e7554e755aaad8df0e26268787438735b4b76
Gitweb:     http://git.kernel.org/tip/9e4e7554e755aaad8df0e26268787438735b4b76
Author:     Ingo Molnar <mingo@kernel.org>
AuthorDate: Mon, 29 Feb 2016 10:03:58 +0100
Committer:  Ingo Molnar <mingo@kernel.org>
CommitDate: Mon, 29 Feb 2016 10:32:29 +0100

locking/lockdep: Detect chain_key collisions

Add detection for chain_key collision under CONFIG_DEBUG_LOCKDEP.
When a collision is detected the problem is reported and all lock
debugging is turned off.

Tested using liblockdep and the added tests before and after
applying the fix, confirming both that the code added for the
detection correctly reports the problem and that the fix actually
fixes it.

Tested tweaking lockdep to generate false collisions and
verified that the problem is reported and that lock debugging is
turned off.

Also tested with lockdep's test suite after applying the patch:

    [    0.000000] Good, all 253 testcases passed! |

Signed-off-by: Alfredo Alvarez Fernandez <alfredoalvarezernandez@gmail.com>
Cc: Alfredo Alvarez Fernandez <alfredoalvarezfernandez@gmail.com>
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: sasha.levin@oracle.com
Link: http://lkml.kernel.org/r/1455864533-7536-4-git-send-email-alfredoalvarezernandez@gmail.com
Signed-off-by: Ingo Molnar <mingo@kernel.org>
---
 kernel/locking/lockdep.c | 59 +++++++++++++++++++++++++++++++++++++++++-------
 1 file changed, 51 insertions(+), 8 deletions(-)

diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index 6f446eb..f894a2c 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -1982,6 +1982,53 @@ struct lock_class *lock_chain_get_class(struct lock_chain *chain, int i)
 }
 
 /*
+ * Returns the index of the first held_lock of the current chain
+ */
+static inline int get_first_held_lock(struct task_struct *curr,
+					struct held_lock *hlock)
+{
+	int i;
+	struct held_lock *hlock_curr;
+
+	for (i = curr->lockdep_depth - 1; i >= 0; i--) {
+		hlock_curr = curr->held_locks + i;
+		if (hlock_curr->irq_context != hlock->irq_context)
+			break;
+
+	}
+
+	return ++i;
+}
+
+/*
+ * Checks whether the chain and the current held locks are consistent
+ * in depth and also in content. If they are not it most likely means
+ * that there was a collision during the calculation of the chain_key.
+ * Returns: 0 not passed, 1 passed
+ */
+static int check_no_collision(struct task_struct *curr,
+			struct held_lock *hlock,
+			struct lock_chain *chain)
+{
+#ifdef CONFIG_DEBUG_LOCKDEP
+	int i, j, id;
+
+	i = get_first_held_lock(curr, hlock);
+
+	if (DEBUG_LOCKS_WARN_ON(chain->depth != curr->lockdep_depth - (i - 1)))
+		return 0;
+
+	for (j = 0; j < chain->depth - 1; j++, i++) {
+		id = curr->held_locks[i].class_idx - 1;
+
+		if (DEBUG_LOCKS_WARN_ON(chain_hlocks[chain->base + j] != id))
+			return 0;
+	}
+#endif
+	return 1;
+}
+
+/*
  * Look up a dependency chain. If the key is not present yet then
  * add it and return 1 - in this case the new dependency chain is
  * validated. If the key is already hashed, return 0.
@@ -1994,7 +2041,6 @@ static inline int lookup_chain_cache(struct task_struct *curr,
 	struct lock_class *class = hlock_class(hlock);
 	struct hlist_head *hash_head = chainhashentry(chain_key);
 	struct lock_chain *chain;
-	struct held_lock *hlock_curr;
 	int i, j;
 
 	/*
@@ -2012,6 +2058,9 @@ static inline int lookup_chain_cache(struct task_struct *curr,
 		if (chain->chain_key == chain_key) {
 cache_hit:
 			debug_atomic_inc(chain_lookup_hits);
+			if (!check_no_collision(curr, hlock, chain))
+				return 0;
+
 			if (very_verbose(class))
 				printk("\nhash chain already cached, key: "
 					"%016Lx tail class: [%p] %s\n",
@@ -2049,13 +2098,7 @@ cache_hit:
 	chain = lock_chains + nr_lock_chains++;
 	chain->chain_key = chain_key;
 	chain->irq_context = hlock->irq_context;
-	/* Find the first held_lock of current chain */
-	for (i = curr->lockdep_depth - 1; i >= 0; i--) {
-		hlock_curr = curr->held_locks + i;
-		if (hlock_curr->irq_context != hlock->irq_context)
-			break;
-	}
-	i++;
+	i = get_first_held_lock(curr, hlock);
 	chain->depth = curr->lockdep_depth + 1 - i;
 	if (likely(nr_chain_hlocks + chain->depth <= MAX_LOCKDEP_CHAIN_HLOCKS)) {
 		chain->base = nr_chain_hlocks;