lkml.org 
[lkml]   [2009]   [Jun]   [8]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
Patch in this message
/
Date
From
SubjectRe: [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


\
 
 \ /
  Last update: 2009-06-08 17:53    [W:0.071 / U:3.424 seconds]
©2003-2017 Jasper Spaans. hosted at Digital OceanAdvertise on this site