Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1757494AbZGPFWZ (ORCPT ); Thu, 16 Jul 2009 01:22:25 -0400 Received: (majordomo@vger.kernel.org) by vger.kernel.org id S1757422AbZGPFWZ (ORCPT ); Thu, 16 Jul 2009 01:22:25 -0400 Received: from viefep15-int.chello.at ([62.179.121.35]:58846 "EHLO viefep15-int.chello.at" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1757463AbZGPFWY (ORCPT ); Thu, 16 Jul 2009 01:22:24 -0400 X-SourceIP: 213.93.53.227 Subject: Re: [RESEND PATCH 0/11] kernel:lockdep:replace DFS with BFS From: Peter Zijlstra To: Ming Lei Cc: mingo@elte.hu, linux-kernel@vger.kernel.org, akpm@linux-foundation.org, Linus Torvalds , "David S. Miller" , Frederic Weisbecker In-Reply-To: References: <1246201486-7308-1-git-send-email-tom.leiming@gmail.com> <1247476574.7529.55.camel@twins> Content-Type: text/plain Date: Thu, 16 Jul 2009 07:22:33 +0200 Message-Id: <1247721753.15471.2.camel@twins> Mime-Version: 1.0 X-Mailer: Evolution 2.26.1 Content-Transfer-Encoding: 7bit Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Length: 1908 Lines: 48 On Thu, 2009-07-16 at 12:39 +0800, Ming Lei wrote: > 2009/7/13 Peter Zijlstra : > > On Sun, 2009-06-28 at 23:04 +0800, tom.leiming@gmail.com wrote: > >> Hi,Peter > >> > >> Currently lockdep uses recursion DFS(depth-first search) algorithm to > >> search target in checking lock circle(check_noncircular()),irq-safe > >> -> irq-unsafe(check_irq_usage()) and irq inversion when adding a new > >> lock dependency. This patches replace the current DFS with BFS, based on > >> the following consideration: > >> > >> 1,no loss of efficiency, no matter DFS or BFS, the running time > >> are O(V+E) (V is vertex count, and E is edge count of one > >> graph); > > > > I'd still like to get some feedback on the loss of that generation count > > optimization done by DaveM, I haven't had time to analyze the > > ramifications of that. > > > > > > Hi, Ingo and Peter > > As you said, BFS patch-set is valuable(decrease kernel stack consume > largely, and report > the shortest circle). > > It has been pending on lkml silently for several monthes, and I hope > it may be merged to > tip-tree or other tree. I don't know what we should and can do to make > it being accepted by tip-tree. > Anyway, I'd like to do any fixes for it to be merged. > > Any suggestions, ideas or objections? I've asked several times to comment on the removal of that generation count DaveM did. Is that a normal part of DFS, or was that an optimization on top particular to this problem, can something similar be done for BFS, etc. Other than that it does seem to hold up, I've got the patches running on my laptop. Don't worry they're not getting lost. -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/