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

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: <d82e647a0907111942o1cf22batb204c38bfbd43c03@mail.gmail.com>
Date:	Sun, 12 Jul 2009 10:42:42 +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 01/11] kernel:lockdep:print the shortest dependency 
	chain if finding a circle

2009/7/12 Frederic Weisbecker <fweisbec@...il.com>:
> On Sun, Jun 28, 2009 at 11:04:36PM +0800, tom.leiming@...il.com wrote:
>> From: Ming Lei <tom.leiming@...il.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
--
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/