Messages in this thread Patch in this message | | | Date | Mon, 8 Jun 2009 23:50:43 +0800 | From | Ming Lei <> | Subject | Re: [PATCH 0/8] kernel:lockdep:replace DFS with BFS |
| |
On Mon, 08 Jun 2009 14:22:07 +0200 Peter Zijlstra <a.p.zijlstra@chello.nl> wrote:
> On Sun, 2009-05-31 at 22:49 +0800, tom.leiming@gmail.com wrote: > > Hi, > > 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); > > > > 2,BFS may be easily implemented by circular queue and consumes > > much less kernel stack space than DFS for DFS is implemented by > > recursion. > > > > 3, The shortest path can be obtained by BFS if the target is > > found, but can't be got by DFS. By the shortest path, we can > > shorten the lock dependency chain and help to troubleshoot lock > > problem easier than before. > > > > OK, so I applied the patches and the cleanup below. > > mostly little style nits and moving the circular queue into lockdep.c > (nobody else uses it, so why share it?). > > One thing though, macros with return statements?! that's seriously bad > style, don't do that. > > One thing that worries me a little is that we loose DaveM's > lockdep_dependency_visit() optimization. My brain seems unwilling to > co-operate on determining if BFS would make that redundant, so a > little word on that would be appreciated. > > Then I booted it and all hell broke loose, so either I wrecked > something or you did :-), would you terribly mind poking at that a > little?
I have fixed the bug, which is introduced in your patch: lockdep: clean up after BFS patches.
Please apply and verify the patch,thanks.
I'll go to bed,:-)
From e99ce7b2b4985032e9f54b08a7790f3df2783286 Mon Sep 17 00:00:00 2001 From: Ming Lei <tom.leiming@gmail.com> Date: Mon, 8 Jun 2009 23:38:59 +0800 Subject: [PATCH] kernel:lockdep:fix return value of check_usage*()
Return zero if BFS find the target, so fix return value of callers of BFS.
The patch fixes the boot failure introduced by the patch: lockdep: clean up after BFS patches .
Signed-off-by: Ming Lei <tom.leiming@gmail.com> --- kernel/lockdep.c | 20 ++++++++++++-------- 1 files changed, 12 insertions(+), 8 deletions(-)
diff --git a/kernel/lockdep.c b/kernel/lockdep.c index 09a141f..48c3364 100644 --- a/kernel/lockdep.c +++ b/kernel/lockdep.c @@ -1250,8 +1250,6 @@ find_usage_forwards(struct lock_list *root, enum lock_usage_bit bit, debug_atomic_inc(&nr_find_usage_forwards_checks); result = __bfs_forwards(root, (void *)bit, usage_match, target_entry); - if (result < 0) - return print_bfs_bug(result); return result; } @@ -1275,8 +1273,6 @@ find_usage_backwards(struct lock_list *root, enum lock_usage_bit bit, debug_atomic_inc(&nr_find_usage_backwards_checks); result = __bfs_backwards(root, (void *)bit, usage_match, target_entry); - if (result < 0) - return print_bfs_bug(result); return result; } @@ -1397,13 +1393,17 @@ check_usage(struct task_struct *curr, struct held_lock *prev, this.class = hlock_class(prev); ret = find_usage_backwards(&this, bit_backwards, &target_entry); - if (!ret || ret == 1) + if (ret < 0) + return print_bfs_bug(ret); + if (ret == 1) return ret; that.parent = NULL; that.class = hlock_class(next); ret = find_usage_forwards(&that, bit_forwards, &target_entry1); - if (!ret || ret == 1) + if (ret < 0) + return print_bfs_bug(ret); + if (ret == 1) return ret; return print_bad_irq_dependency(curr, &this, &that, @@ -2088,7 +2088,9 @@ check_usage_forwards(struct task_struct *curr, struct held_lock *this, root.parent = NULL; root.class = hlock_class(this); ret = find_usage_forwards(&root, bit, &target_entry); - if (!ret || ret == 1) + if (ret < 0) + return print_bfs_bug(ret); + if (ret == 1) return ret; return print_irq_inversion_bug(curr, &root, target_entry, @@ -2110,7 +2112,9 @@ check_usage_backwards(struct task_struct *curr, struct held_lock *this, root.parent = NULL; root.class = hlock_class(this); ret = find_usage_backwards(&root, bit, &target_entry); - if (!ret || ret == 1) + if (ret < 0) + return print_bfs_bug(ret); + if (ret == 1) return ret; return print_irq_inversion_bug(curr, &root, target_entry, -- 1.6.0.GIT
-- Lei Ming
| |