[RFC tip 0/5] lockdep: Support deadlock detection for recursive read locks

[Boqun Feng <boqun.feng@gmail.com>]

Hi Ingo and Peter,

As Peter pointed out:

	https://marc.info/?l=linux-kernel&m=150349072023540

The lockdep current has a limit support for recursive read locks, the
deadlock case as follow could not be detected:

	read_lock(A);
				lock(B);
	lock(B);
				write_lock(A);

I got some inspiration from Gautham R Shenoy:

	https://lwn.net/Articles/332801/

, and came up with this series.

The basic idea is:

*	Add recursive read locks into the graph

*	Classify dependencies into R->R, N->R, R->N, N->N, where R
	stands for recursive read lock, N stands for other locks.

*	Extend __bfs() to go through all kinds of dependencies and the
	read/write status could be changed in the traverse(i.e. with
	dependency N(A)->R(B) and N(B)->R(C), BFS could go from A to B
	and then to C).

*	But don't allow use a lock B as a transfer station if B only has
	*->R dependencies to the previous lock and R->* dependencies to
	the next lock. This is because if a BFS traverse has such a B as
	a transfer station, the following exists:

		CPU0		CPU1		CPU2		CPU3
		lock(X);
		lock(Y);   	lock(Y);
				rlock(B);	rlock(B);
						lock(P);   	lock(P);
								lock(Q);
	
	The lock dependency breaks between CPU1 and CPU2, no deadlock.
		
In this way, we can reflect the real dependencies while taking recursive
read locks into considerations.

This is readlly an RFC, as I'm 100% sure I cover all the cases related
to read recursive locks, but I do add two sets of self testcases, and
they did pass ;-)

This series consists of 5 patches:

Patch #1 introduces a new test case to test chain cache behavior on the
recursive read deadlock detection.

Patch #2 introduces more complex cases for recursive read deadlock
detection.

Patch #3 does a little bit clean-up on the return value of __bfs() and
its friends.

Patch #4 adds recursive locks into dependency graph and extends BFS to
allow deadlock detection for recursive read locks.

Patch #5 fixes the problem that lock chains and chainkeys don't treat
read/write locks differently, which could miss the chance to detect a
deadlock because a lock chain cache hit.

I plan to write more tests and play about this in next weeks, just send
out for suggestions and comments.

Reviews and tests are welcome!

Regards,
Boqun