Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.18 as permitted sender) client-ip=23.128.96.18;
From:   Boqun Feng <boqun.feng@gmail.com>
To:     linux-kernel@vger.kernel.org, linux-doc@vger.kernel.org
Cc:     Peter Zijlstra <peterz@infradead.org>,
        Ingo Molnar <mingo@redhat.com>, Will Deacon <will@kernel.org>,
        Jonathan Corbet <corbet@lwn.net>,
        Waiman Long <longman@redhat.com>,
        Boqun Feng <boqun.feng@gmail.com>
Subject: [RFC v7 00/19] lockdep: Support deadlock detection for recursive read locks
Date:   Fri,  7 Aug 2020 15:42:19 +0800
Message-Id: <20200807074238.1632519-1-boqun.feng@gmail.com>
MIME-Version: 1.0
Content-Transfer-Encoding: 8bit
Sender: linux-kernel-owner@vger.kernel.org
Precedence: bulk

Hi Peter and Waiman,

As promised, this is the updated version of my previous lockdep patchset
for recursive read lock support. It's based on v5.8. Previous versions
can be found at:

V1: https://marc.info/?l=linux-kernel&m=150393341825453
V2: https://marc.info/?l=linux-kernel&m=150468649417950
V3: https://marc.info/?l=linux-kernel&m=150637795424969
V4: https://marc.info/?l=linux-kernel&m=151550860121565
V5: https://marc.info/?l=linux-kernel&m=151928315529363
V6: https://lore.kernel.org/lkml/20180411135110.9217-1-boqun.feng@gmail.com/

Changes since last version:

*	I change the detection algorithm which I present in 2018
	plumbers [1], you can find the explanation of the detection
	method in patch #2.

*	Adjust the irq safe->unsafe changes from Frederic Weisbecker

*	Add more tests.


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 -(SR)->, -(ER)->, -(SN)->,
	-(EN)->, where R stands for recursive read lock, N stands for
	other locks(i.e. non-recursive read locks and write locks), S
	stands for shared locks (read locks, no matter recursive or
	not), and E stands for exclusive locks (i.e. write locks)

*	Define strong dependency paths as the paths of dependencies
	don't have two adjacent dependencies as -(*R)-> and -(S*)->.

*	Extend __bfs() to only traverse on strong dependency paths.

*	If __bfs() finds a strong dependency circle, then a deadlock is
	reported.

The whole series consists of 19 patches:

1.	Add documentation for recursive read lock deadlock detection
	reasoning

2.	Annotate read_lock() correctly (with queued_read_lock()
	semantics into consideration)

3.	Do a clean up on the return value of __bfs() and its friends.

4.	Make __bfs() able to visit every dependency until a match is
	found. The old version of __bfs() could only visit each lock
	class once, and this is insufficient if we are going to add
	recursive read locks into the dependency graph.

5.	Reduce the size of lock_list::distance.

6-7	Extend __bfs() to be able to traverse the stong dependency
	patchs after recursive read locks added into the graph.

8.	Make __bfs(.math) return bool.

9-11	Adjust check_redundant(), check_noncircular() and
	check_irq_usage() with recursive read locks into consideration.

12.	Finally add recursive read locks into the dependency graph.

13-14	Adjust lock cache chain key generation with recursive read locks
	into consideration, and provide a test case.

15-16	Add more test cases.

17.	Revert commit d82fed752942 ("locking/lockdep/selftests: Fix
	mixed read-write ABBA tests"),

18-19	Add more test cases (including tests that are specific for
	queued_read_lock())

This series passed all the lockdep selftest cases (including those I
introduce).

Test and comments are welcome!

Regards,
Boqun