[lkml]   [2009]   [Jul]   [11]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
SubjectRe: [RESEND PATCH 01/11] kernel:lockdep:print the shortest dependency chain if finding a circle
2009/7/12 Frederic Weisbecker <>:
> On Sun, Jun 28, 2009 at 11:04:36PM +0800, wrote:
>> From: Ming Lei <>
>> 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

 \ /
  Last update: 2009-07-12 04:45    [W:0.137 / U:2.520 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site