Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1752992AbZGMICu (ORCPT ); Mon, 13 Jul 2009 04:02:50 -0400 Received: (majordomo@vger.kernel.org) by vger.kernel.org id S1752560AbZGMICt (ORCPT ); Mon, 13 Jul 2009 04:02:49 -0400 Received: from rv-out-0506.google.com ([209.85.198.228]:2099 "EHLO rv-out-0506.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1752523AbZGMICs (ORCPT ); Mon, 13 Jul 2009 04:02:48 -0400 DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=date:from:to:cc:subject:message-id:references:mime-version :content-type:content-disposition:in-reply-to:user-agent; b=LgdsU+P2U10cfcYWRjXdxSwjYSX82kZb79gYgD6GK7EdW9Ysfzxv7iKHQqMuJpjV8p adtkNSzQCM7TGNkR3Flj8n5UYkUV5DnLQvuF523zPWEgUQ+BRJHFGmnQ1UQjpdo83+ve jTxf0RgcId4rv5T9aaIgtnS1JSs/qbuhghOdw= Date: Mon, 13 Jul 2009 16:02:05 +0800 From: Dave Young To: tom.leiming@gmail.com Cc: a.p.zijlstra@chello.nl, linux-kernel@vger.kernel.org, akpm@linux-foundation.org, mingo@elte.hu Subject: Re: [RESEND PATCH 04/11] kernel:lockdep:implement check_noncircular() by BFS Message-ID: <20090713080205.GA2187@darkstar> References: <1246201486-7308-1-git-send-email-tom.leiming@gmail.com> <1246201486-7308-2-git-send-email-tom.leiming@gmail.com> <1246201486-7308-3-git-send-email-tom.leiming@gmail.com> <1246201486-7308-4-git-send-email-tom.leiming@gmail.com> <1246201486-7308-5-git-send-email-tom.leiming@gmail.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <1246201486-7308-5-git-send-email-tom.leiming@gmail.com> User-Agent: Mutt/1.5.19 (2009-01-05) Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Length: 6488 Lines: 194 On Sun, Jun 28, 2009 at 11:04:39PM +0800, tom.leiming@gmail.com wrote: > From: Ming Lei > > This patch uses BFS to implement check_noncircular() and > prints the generated shortest circle if exists. > > Signed-off-by: Ming Lei > --- > kernel/lockdep.c | 89 ++++++++++++++++++++++------------------------------- > 1 files changed, 37 insertions(+), 52 deletions(-) > > diff --git a/kernel/lockdep.c b/kernel/lockdep.c > index ce6d09e..f740088 100644 > --- a/kernel/lockdep.c > +++ b/kernel/lockdep.c > @@ -985,12 +985,7 @@ static inline int __bfs_backward(struct lock_list *src_entry, > * Recursive, forwards-direction lock-dependency checking, used for > * both noncyclic checking and for hardirq-unsafe/softirq-unsafe > * checking. > - * > - * (to keep the stackframe of the recursive functions small we > - * use these global variables, and we also mark various helper > - * functions as noinline.) > */ > -static struct held_lock *check_source, *check_target; > > /* > * Print a dependency chain entry (this is only done when a deadlock > @@ -1014,7 +1009,9 @@ print_circular_bug_entry(struct lock_list *target, unsigned int depth) > * header first: > */ > static noinline int > -print_circular_bug_header(struct lock_list *entry, unsigned int depth) > +print_circular_bug_header(struct lock_list *entry, unsigned int depth, > + struct held_lock *check_src, > + struct held_lock *check_tgt) > { > struct task_struct *curr = current; > > @@ -1027,9 +1024,9 @@ print_circular_bug_header(struct lock_list *entry, unsigned int depth) > printk( "-------------------------------------------------------\n"); > printk("%s/%d is trying to acquire lock:\n", > curr->comm, task_pid_nr(curr)); > - print_lock(check_source); > + print_lock(check_src); > printk("\nbut task is already holding lock:\n"); > - print_lock(check_target); > + print_lock(check_tgt); > printk("\nwhich lock already depends on the new lock.\n\n"); > printk("\nthe existing dependency chain (in reverse order) is:\n"); > > @@ -1043,36 +1040,24 @@ static inline int class_equal(struct lock_list *entry, void *data) > return entry->class == data; > } > > -static noinline int print_circular_bug(void) > +static noinline int print_circular_bug(struct lock_list *this, Shouldn't be 'static noinline int' here? Same question to following ones. > + struct lock_list *target, > + struct held_lock *check_src, > + struct held_lock *check_tgt) > { > struct task_struct *curr = current; > - struct lock_list this; > - struct lock_list *target; > struct lock_list *parent; > - int result; > unsigned long depth; > > if (!debug_locks_off_graph_unlock() || debug_locks_silent) > return 0; > > - this.class = hlock_class(check_source); > - this.parent = NULL; > - if (!save_trace(&this.trace)) > + if (!save_trace(&this->trace)) > return 0; > > - result = __bfs_forward(&this, > - hlock_class(check_target), > - class_equal, > - &target); > - if (result) { > - printk("\n%s:search shortest path failed:%d\n", __func__, > - result); > - return 0; > - } > - > depth = get_lock_depth(target); > > - print_circular_bug_header(target, depth); > + print_circular_bug_header(target, depth, check_src, check_tgt); > > parent = get_lock_parent(target); > > @@ -1090,6 +1075,16 @@ static noinline int print_circular_bug(void) > return 0; > } > > +static int noinline print_bfs_bug(int ret) > +{ > + if (!debug_locks_off_graph_unlock()) > + return 0; > + > + WARN(1, "lockdep bfs error:%d\n", ret); > + > + return 0; > +} > + > #define RECURSION_LIMIT 40 > > static int noinline print_infinite_recursion_bug(void) > @@ -1168,31 +1163,17 @@ unsigned long lockdep_count_backward_deps(struct lock_class *class) > * lead to . Print an error and return 0 if it does. > */ > static noinline int > -check_noncircular(struct lock_class *source, unsigned int depth) > +check_noncircular(struct lock_list *root, struct lock_class *target, > + struct lock_list **target_entry) > { > - struct lock_list *entry; > + int result; > > - if (lockdep_dependency_visit(source, depth)) > - return 1; > + debug_atomic_inc(&nr_cyclic_checks); > > - debug_atomic_inc(&nr_cyclic_check_recursions); > - if (depth > max_recursion_depth) > - max_recursion_depth = depth; > - if (depth >= RECURSION_LIMIT) > - return print_infinite_recursion_bug(); > - /* > - * Check this lock's dependency list: > - */ > - list_for_each_entry(entry, &source->locks_after, entry) { > - if (entry->class == hlock_class(check_target)) > - return 2; > - debug_atomic_inc(&nr_cyclic_checks); > - if (check_noncircular(entry->class, depth+1) == 2) > - return 2; > - } > - return 1; > -} > + result = __bfs_forward(root, target, class_equal, target_entry); > > + return result; > +} > > #if defined(CONFIG_TRACE_IRQFLAGS) && defined(CONFIG_PROVE_LOCKING) > /* > @@ -1586,6 +1567,8 @@ check_prev_add(struct task_struct *curr, struct held_lock *prev, > { > struct lock_list *entry; > int ret; > + struct lock_list this; > + struct lock_list *uninitialized_var(target_entry); > > /* > * Prove that the new -> dependency would not > @@ -1596,11 +1579,13 @@ check_prev_add(struct task_struct *curr, struct held_lock *prev, > * We are using global variables to control the recursion, to > * keep the stackframe size of the recursive functions low: > */ > - check_source = next; > - check_target = prev; > - > - if (check_noncircular(hlock_class(next), 0) == 2) > - return print_circular_bug(); > + this.class = hlock_class(next); > + this.parent = NULL; > + ret = check_noncircular(&this, hlock_class(prev), &target_entry); > + if (unlikely(!ret)) > + return print_circular_bug(&this, target_entry, next, prev); > + else if (unlikely(ret < 0)) > + return print_bfs_bug(ret); > > if (!check_prev_add_irq(curr, prev, next)) > return 0; > -- > 1.6.0.GIT > > -- > 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/ -- 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/