Re: [RESEND PATCH 01/11] kernel:lockdep:print the shortest dependency chain if finding a circle

[Ming Lei <tom.leiming@gmail.com>]

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