Messages in this thread | | | Date | Sun, 12 Jul 2009 10:42:42 +0800 | Subject | Re: [RESEND PATCH 01/11] kernel:lockdep:print the shortest dependency chain if finding a circle | From | Ming Lei <> |
| |
2009/7/12 Frederic Weisbecker <fweisbec@gmail.com>: > On Sun, Jun 28, 2009 at 11:04:36PM +0800, tom.leiming@gmail.com wrote: >> From: Ming Lei <tom.leiming@gmail.com> >> >> Currently lockdep will print the 1st circle detected if it exists when >> acquiring a new (next) lock. >> >> This patch prints the shortest path from the next lock to be acquired to >> the previous held lock if a circle is found. >> >> The patch still uses the current method to check circle, and once the >> circle is found, breadth-first search algorithem is used to compute the >> shortest path from the next lock to the previous lock in the forward >> lock dependency graph. >> >> Printing the shortest path will shorten the dependency chain, and make >> troubleshooting for possible circular locking easier. > > > > Oh! That looks fairly different from what I was thinking about...
If you continue to review the following patches, you will find it is the same from what you are thinking about.
The patch is a middle patch and just a start point. It is this patch that checking circle by BFS comes to my mind.
Maybe I should rearrange the patch set, I really want to get more suggestions and comments to do it.
Thanks for your review.
> > If I understand well, lets imagine the following: > > Task 1 acquires: A B F > Task 2 acquires: A B C D E F > Task 3 acquires: F B > > Before your patch, DFS would report the BF - FB wicked dependency > by reporting the Task 2 dependency snapshot, which is cluttered by > the other locks C, D and E (that would be reported in the dependency chain > if I'm not wrong) whereas BFS would be smarter by finding the shortest > snapshot found in Task 3: just F B. > > Correct me if I misunderstand this patch.
You are correct, BFS will always find the shortest circle if there is circle.
> > I suggest you to provide an example along this patch, that would make > it easier to demonstrate its importance.
No, as you said, the shortest circle is not very important, and it is just a byproduct and we have no reason to reject it.
-- Lei Ming
| |