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

Groups > linux.kernel > #1336130

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

Show all headers | View raw

* 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

Back to linux.kernel | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

[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

csiph-web