From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1030214AbcBQIi6 (ORCPT ); Wed, 17 Feb 2016 03:38:58 -0500 Received: from mail-wm0-f48.google.com ([74.125.82.48]:33189 "EHLO mail-wm0-f48.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1756641AbcBQIi4 (ORCPT ); Wed, 17 Feb 2016 03:38:56 -0500 Date: Wed, 17 Feb 2016 09:38:52 +0100 From: Ingo Molnar To: Alfredo Alvarez Fernandez Cc: mingo@redhat.com, peterz@infradead.org, sasha.levin@oracle.com, linux-kernel@vger.kernel.org Subject: Re: [PATCH 3/3] lockdep: prevent chain_key collisions Message-ID: <20160217083852.GC1197@gmail.com> References: <1455147212-2389-1-git-send-email-alfredoalvarezernandez@gmail.com> <1455147212-2389-4-git-send-email-alfredoalvarezernandez@gmail.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <1455147212-2389-4-git-send-email-alfredoalvarezernandez@gmail.com> User-Agent: Mutt/1.5.23 (2014-03-12) Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org * Alfredo Alvarez Fernandez wrote: > From: Alfredo Alvarez Fernandez > > 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