Re: [RESEND PATCH 0/11] kernel:lockdep:replace DFS with BFS

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

2009/7/12 Frederic Weisbecker <fweisbec@gmail.com>:
> On Sat, Jul 11, 2009 at 11:25:29AM +0800, Ming Lei wrote:
>> 2009/7/11 Frederic Weisbecker <fweisbec@gmail.com>:

>> >>     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.
>> >
>> >
>> > But there I don't understand your argument.
>> > The shortest path finding doesn't seem to me a need.
>> > Example:
>> >
>> > Task 1 acquires: A B C
>> > And Later:
>> > Task 2 acquires: C B A
>> >
>> > DFS will probably report a circular lock dependency
>> > with A and C.
>> > BFS will probably report a circular lock dependency
>> > with B and C.
>> >
>> > Which one is the most important? Both dependencies must be fixed
>> > anyway. Once the developer will fix one of those, the remaining one
>> > will be reported and so on...
>> >
>> > Or am I missing something else?
>>
>> Yes, you are right.  By BFS, we can always find the shortest circle, but we
>> find a random circle by DFS.   No one can say which circle is the most
>> important from the point of deadlock.
>>
>> But it is easier to start troubleshooting from the shortest circle
>> than a random circle , then from the next shortest circle if other
>> circle still exists .
>>
>> Right?
>
>
> I don't have a strong opinion on this. I just don't think the shortest path is
> the most important if there are many many paths.
> Whatever AB-BA is encountered, all of them must be fixed.
> What might give a degree of importance for such bad circle is the window
> in which it triggers.

The shortest path is just a characteristic of BFS, and we do not need
to pay extra
work for it.  So finding the shortest circle have not any bad effect at least.

IMHO, troubleshooting from the shortest circle is easier than from other circle.

-- 
Lei Ming