Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1751336AbZGPHMj (ORCPT ); Thu, 16 Jul 2009 03:12:39 -0400 Received: (majordomo@vger.kernel.org) by vger.kernel.org id S1751241AbZGPHMi (ORCPT ); Thu, 16 Jul 2009 03:12:38 -0400 Received: from mail-pz0-f196.google.com ([209.85.222.196]:41331 "EHLO mail-pz0-f196.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751164AbZGPHMh (ORCPT ); Thu, 16 Jul 2009 03:12:37 -0400 DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type:content-transfer-encoding; b=W6uf16LNXEAESLXJ+Z4rbINo6lqStb0dL9ECyV8GeA87R5miw2KSGidHcWlgEl0OWC GKZJw8bu5qDYhSTxzOTfJyiKnwwz/Vn86bKszXUFKzhWytW22jk83mHTGYjuLIfVo/ku pC4HolviMGcTILpZCYe31ripoZ6P5chTk76ZA= MIME-Version: 1.0 In-Reply-To: <1247721753.15471.2.camel@twins> References: <1246201486-7308-1-git-send-email-tom.leiming@gmail.com> <1247476574.7529.55.camel@twins> <1247721753.15471.2.camel@twins> Date: Thu, 16 Jul 2009 15:12:37 +0800 Message-ID: Subject: Re: [RESEND PATCH 0/11] kernel:lockdep:replace DFS with BFS From: Ming Lei To: Peter Zijlstra Cc: mingo@elte.hu, linux-kernel@vger.kernel.org, akpm@linux-foundation.org, Linus Torvalds , "David S. Miller" , Frederic Weisbecker Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Length: 1084 Lines: 33 2009/7/16 Peter Zijlstra : > > 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. DFS uses generation count DaveM did to decide if a class is visted, and BFS uses bitmap to mark a class is visted or not and the extra efficiency loss is bitmap_zero(bfs_accessed, MAX_LOCKDEP_ENTRIES); before staring each BFS. On most of ARCH, bimap_zero can be optimizied to only consume very few instructions, can't it? It seems bitmap is more easily used in BFS than generation count. > > 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. Great. -- Lei Ming -- 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/