linux-kernel - Re: [PATCH 3/3] lockdep: prevent chain

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <20160217083852.GC1197@gmail.com>
Date:	Wed, 17 Feb 2016 09:38:52 +0100
From:	Ingo Molnar <mingo@...nel.org>
To:	Alfredo Alvarez Fernandez <alfredoalvarezfernandez@...il.com>
Cc:	mingo@...hat.com, peterz@...radead.org, sasha.levin@...cle.com,
	linux-kernel@...r.kernel.org
Subject: Re: [PATCH 3/3] lockdep: prevent chain_key collisions


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

> From: Alfredo Alvarez Fernandez <alfredoalvarezfernandez@...il.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