lockdep: Support deadlock detection for recursive read locks in check_noncircular()

Currently, lockdep only has limit support for deadlock detection for
recursive read locks.

The basic idea of the detection is:

Firstly we add recursive read lock into the graph, so now we have four
types of dependency: 1) non-recursive to recursive(NR), 2) non-recursive
to non-recursive(NN), 3) recursive to non-recursive(RN) and 4) recursive
to recursive(RR).

And further in __bfs() we now allow switch the lock read/write status in
the traverse, in other words, if the __bfs() went from A to B through
write_lock(A) --> read_lock(B), we would allow __bfs() to go from B to C
through write_lock(B) --> read_lock(C).

However, we limit the traverse reflect the real dependencies, and the
rule is simple: the bfs traverse can go through A to B and then to C iff
we can find dependency A --> B and B --> C where B is not a recursive
read lock in at least one of dependencies(A --> B and B-->C). In other
words, a lock cannot be the transfer station if it only has *->R
dependencies with previous locks and R->* dependencies with following
locks.

If we could still find a circle under this rule, a deadlock is reported.

Signed-off-by: Boqun Feng <boqun.feng@gmail.com>
2 files changed