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

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <d82e647a0907111929u72ebe4b5t7cf638568e195adc@mail.gmail.com>
Date:	Sun, 12 Jul 2009 10:29:11 +0800
From:	Ming Lei <tom.leiming@...il.com>
To:	Frederic Weisbecker <fweisbec@...il.com>
Cc:	a.p.zijlstra@...llo.nl, linux-kernel@...r.kernel.org,
	akpm@...ux-foundation.org, mingo@...e.hu
Subject: Re: [RESEND PATCH 0/11] kernel:lockdep:replace DFS with BFS

2009/7/12 Frederic Weisbecker <fweisbec@...il.com>:
> On Sat, Jul 11, 2009 at 11:25:29AM +0800, Ming Lei wrote:
>> 2009/7/11 Frederic Weisbecker <fweisbec@...il.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
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/