Provide the smallest possible cycle in deadlock detector reports

[GoogleCodeExporter]

When a lock-order inversion occurs (usually detected through DFS) we should 
provide the smallest possible cycle (to ease the burden of debugging it).

It's possible to have a lock orders established: A->B->C, A->C. If this order 
is then broken by locking C->A, then a DFS could provide C->A->B->C, even 
though C->A->C would be sufficient and easier to parse/debug.

Original issue reported on code.google.com by pbos@google.com on 5 Mar 2014 at 4:04

[GoogleCodeExporter]

Do you have a test that shows that we don't do it? 
(It's a bit messy, we have two detector engines now, but the one based on 
bitvectors certainly finds the shortest path),
see e.g. ShortestPath test in sanitizer_common/tests/sanitizer_bvgraph_test.cc

Original comment by konstant...@gmail.com on 11 Mar 2014 at 1:37

[GoogleCodeExporter]

I don't, when talking with dvyukov@ it sounded like he hadn't thought of it, so 
I put this down so it wouldn't be forgotten. Might still be relevant for the 
non-bitvector one.

Original comment by pbos@google.com on 11 Mar 2014 at 1:41

[GoogleCodeExporter]

yes, as per offline discussion, it's an issue only for the "second" 
implementation
let this be open for now as a reminder

Original comment by dvyu...@google.com on 11 Mar 2014 at 1:50

[GoogleCodeExporter]

Original comment by dvyu...@google.com on 25 Apr 2014 at 10:18

• Added labels: DeadlockDetector

[GoogleCodeExporter]

Original comment by dvyu...@google.com on 19 May 2014 at 11:59

[GoogleCodeExporter]

This is relevant only for deadlock detector v2, and we have not decided which 
one wins. So this is postponed for now.

Original comment by dvyu...@google.com on 19 May 2014 at 12:01