Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1331584 > unrolled thread

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

Back to article view | Back to linux.kernel

Contents

  [PATCH 0/3] lockdep: liblockdep: Prevent chain_key collisions Alfredo Alvarez Fernandez <alfredoalvarezfernandez@gmail.com> - 2016-02-11 00:40 +0100
    [PATCH 3/3] lockdep: prevent chain_key collisions Alfredo Alvarez Fernandez <alfredoalvarezfernandez@gmail.com> - 2016-02-11 00:40 +0100
      Re: [PATCH 3/3] lockdep: prevent chain_key collisions Ingo Molnar <mingo@kernel.org> - 2016-02-17 09:40 +0100
        [PATCH v2 2/3] tools/liblockdep: add tests Alfredo Alvarez Fernandez <alfredoalvarezfernandez@gmail.com> - 2016-02-19 07:50 +0100
        [PATCH v2 0/3] lockdep: liblockdep: Prevent chain_key collisions Alfredo Alvarez Fernandez <alfredoalvarezfernandez@gmail.com> - 2016-02-19 07:50 +0100
          [PATCH v2 3/3] lockdep: prevent and detect chain_key collisions Alfredo Alvarez Fernandez <alfredoalvarezfernandez@gmail.com> - 2016-02-19 08:00 +0100
          [PATCH v2 1/3] tools/liblockdep: add userspace version of READ_ONCE Alfredo Alvarez Fernandez <alfredoalvarezfernandez@gmail.com> - 2016-02-19 08:00 +0100
    Re: [PATCH 0/3] lockdep: liblockdep: Prevent chain_key collisions Sasha Levin <sasha.levin@oracle.com> - 2016-02-16 17:40 +0100
      Re: [PATCH 0/3] lockdep: liblockdep: Prevent chain_key collisions Peter Zijlstra <peterz@infradead.org> - 2016-02-16 18:30 +0100

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

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

[toc] | [next] | [standalone]

#1331586 — [PATCH 3/3] lockdep: prevent chain_key collisions

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

[toc] | [prev] | [next] | [standalone]

#1336130 — Re: [PATCH 3/3] lockdep: prevent chain_key collisions

* 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

[toc] | [prev] | [next] | [standalone]

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

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

[toc] | [prev] | [next] | [standalone]

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

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

[toc] | [prev] | [next] | [standalone]

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

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

[toc] | [prev] | [next] | [standalone]

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

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

[toc] | [prev] | [next] | [standalone]

#1335626

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

[toc] | [prev] | [next] | [standalone]

#1335662

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!

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web