From: Boqun Feng <boqun.feng@gmail.com>
To: Andrea Parri <parri.andrea@gmail.com>
Cc: linux-kernel@vger.kernel.org,
Peter Zijlstra <peterz@infradead.org>,
Ingo Molnar <mingo@redhat.com>,
Randy Dunlap <rdunlap@infradead.org>,
Jonathan Corbet <corbet@lwn.net>,
"open list:DOCUMENTATION" <linux-doc@vger.kernel.org>
Subject: Re: [RFC tip/locking/lockdep v5 16/17] lockdep: Documention for recursive read lock detection reasoning
Date: Tue, 27 Feb 2018 10:32:20 +0800 [thread overview]
Message-ID: <20180227023220.ou7764tt56mey3or@tardis> (raw)
In-Reply-To: <20180224225320.GA3027@andrea>
[-- Attachment #1: Type: text/plain, Size: 9410 bytes --]
On Sat, Feb 24, 2018 at 11:53:20PM +0100, Andrea Parri wrote:
> On Thu, Feb 22, 2018 at 03:09:03PM +0800, Boqun Feng wrote:
> > As now we support recursive read lock deadlock detection, add related
> > explanation in the Documentation/lockdep/lockdep-desgin.txt:
> >
> > * Definition of recursive read locks, non-recursive locks, strong
> > dependency path and notions of -(**)->.
> >
> > * Lockdep's assumption.
> >
> > * Informal proof of recursive read lock deadlock detection.
>
> Once again... much appreciated!!, thanks for sharing.
>
np ;-)
>
> >
> > Signed-off-by: Boqun Feng <boqun.feng@gmail.com>
> > Cc: Randy Dunlap <rdunlap@infradead.org>
> > ---
> > Documentation/locking/lockdep-design.txt | 170 +++++++++++++++++++++++++++++++
> > 1 file changed, 170 insertions(+)
> >
> > diff --git a/Documentation/locking/lockdep-design.txt b/Documentation/locking/lockdep-design.txt
> > index 382bc25589c2..fd8a8d97ce58 100644
> > --- a/Documentation/locking/lockdep-design.txt
> > +++ b/Documentation/locking/lockdep-design.txt
> > @@ -284,3 +284,173 @@ Run the command and save the output, then compare against the output from
> > a later run of this command to identify the leakers. This same output
> > can also help you find situations where runtime lock initialization has
> > been omitted.
> > +
> > +Recursive Read Deadlock Detection:
> > +----------------------------------
> > +Lockdep now is equipped with deadlock detection for recursive read locks.
> > +
> > +Recursive read locks, as their name indicates, are the locks able to be
> > +acquired recursively. Unlike non-recursive read locks, recursive read locks
> > +only get blocked by current write lock *holders* other than write lock
> > +*waiters*, for example:
> > +
> > + TASK A: TASK B:
> > +
> > + read_lock(X);
> > +
> > + write_lock(X);
> > +
> > + read_lock(X);
> > +
> > +is not a deadlock for recursive read locks, as while the task B is waiting for
> > +the lock X, the second read_lock() doesn't need to wait because it's a recursive
> > +read lock.
> > +
> > +Note that a lock can be a write lock(exclusive lock), a non-recursive read lock
> > +(non-recursive shared lock) or a recursive read lock(recursive shared lock),
> > +depending on the API used to acquire it(more specifically, the value of the
> > +'read' parameter for lock_acquire(...)). In other words, a single lock instance
> > +has three types of acquisition depending on the acquisition functions:
> > +exclusive, non-recursive read, and recursive read.
> > +
> > +That said, recursive read locks could introduce deadlocks too, considering the
> > +following:
> > +
> > + TASK A: TASK B:
> > +
> > + read_lock(X);
> > + read_lock(Y);
> > + write_lock(Y);
> > + write_lock(X);
> > +
> > +, neither task could get the write locks because the corresponding read locks
> > +are held by each other.
> > +
> > +Lockdep could detect recursive read lock related deadlocks. The dependencies(edges)
> > +in the lockdep graph are classified into four categories:
> > +
> > +1) -(NN)->: non-recursive to non-recursive dependency, non-recursive locks include
> > + non-recursive read locks, write locks and exclusive locks(e.g. spinlock_t).
> > + They are treated equally in deadlock detection. "X -(NN)-> Y" means
> > + X -> Y and both X and Y are non-recursive locks.
> > +
> > +2) -(RN)->: recursive to non-recursive dependency, recursive locks means recursive read
> > + locks. "X -(RN)-> Y" means X -> Y and X is recursive read lock and
> > + Y is non-recursive lock.
> > +
> > +3) -(NR)->: non-recursive to recursive dependency, "X -(NR)-> Y" means X -> Y and X is
> > + non-recursive lock and Y is recursive lock.
> > +
> > +4) -(RR)->: recursive to recursive dependency, "X -(RR)-> Y" means X -> Y and both X
> > + and Y are recursive locks.
> > +
> > +Note that given two locks, they may have multiple dependencies between them, for example:
> > +
> > + TASK A:
> > +
> > + read_lock(X);
> > + write_lock(Y);
> > + ...
> > +
> > + TASK B:
> > +
> > + write_lock(X);
> > + write_lock(Y);
> > +
> > +, we have both X -(RN)-> Y and X -(NN)-> Y in the dependency graph.
> > +
> > +And obviously a non-recursive lock can block the corresponding recursive lock,
> > +and vice versa. Besides a non-recursive lock may block the other non-recursive
> > +lock of the same instance(e.g. a write lock may block a corresponding
> > +non-recursive read lock and vice versa).
> > +
> > +We use -(*N)-> for edges that is either -(RN)-> or -(NN)->, the similar for -(N*)->,
> > +-(*R)-> and -(R*)->
> > +
> > +A "path" is a series of conjunct dependency edges in the graph. And we define a
> > +"strong" path, which indicates the strong dependency throughout each dependency
> > +in the path, as the path that doesn't have two conjunct edges(dependencies) as
> > +-(*R)-> and -(R*)->. IOW, a "strong" path is a path from a lock walking to another
> > +through the lock dependencies, and if X -> Y -> Z in the path(where X, Y, Z are
> > +locks), if the walk from X to Y is through a -(NR)-> or -(RR)-> dependency, the
> > +walk from Y to Z must not be through a -(RN)-> or -(RR)-> dependency, otherwise
> > +it's not a strong path.
> > +
> > +We now prove that if a strong path forms a circle, then we have a potential deadlock.
> > +By "forms a circle", it means for a set of locks A0,A1...An, there is a path from
> > +A0 to An:
> > +
> > + A0 -> A1 -> ... -> An
> > +
> > +and there is also a dependency An->A0. And as the circle is formed by a strong path,
> > +so there are no two conjunct dependency edges as -(*R)-> and -(R*)->.
> > +
> > +
> > +To understand the actual proof, let's look into lockdep's assumption:
> > +
> > +For each lockdep dependency A -> B, there may exist a case where someone is
> > +trying to acquire B with A held, and the existence of such a case is
> > +independent to the existences of cases for other lockdep dependencies.
> > +
> > +For example if we have two functions func1 and func2:
> > +
> > + void func1(...) {
> > + lock(A);
> > + lock(B);
> > + unlock(A);
> > + unlock(B);
> > +
> > + lock(C);
> > + lock(A);
> > + unlock(A);
> > + unlock(C);
> > + }
> > +
> > + void func2(...) {
> > + lock(B);
> > + lock(C);
> > + unlock(C);
> > + unlock(B);
> > + }
> > +
> > +lockdep will generate dependencies: A->B, B->C and C->A, and assume that:
> > +
> > + there may exist a case where someone is trying to acquire B with A held,
> > + there may exist a case where someone is trying to acquire C with B held,
> > + and there may exist a case where someone is trying to acquire A with C held,
> > +
> > +and those three cases exist *independently*, meaning they can happen at the
> > +same time(which requires func1() being called simultaneously by two CPUs or
> > +tasks, which may be impossible due to other constraints in the real life)
> > +
> > +
> > +With this assumption, we can prove that if a strong dependency path forms a circle,
> > +then it indicates a deadlock as far as lockdep is concerned.
>
> As mentioned in a private communication, I would recommend the adoption of
> a "more impersonal" style. Here, for instance, the expression:
>
> "indicates a deadlock as far as lockdep is concerned"
>
> would be replaced with:
>
> "indicates a deadlock as (informally) defined in Sect. ?.?";
>
> similarly (from the proof):
>
> "For a strong dependency [...], lockdep assumes that [...]"
>
> would be replaced with:
>
> "For a strong dependency [...], from assumption/notation ?.?,
> we have/we can conclude [...]".
>
> This could mean that additional text/content would need to be added to the
> present doc./.txt; OTOH, this could help to make this doc. self-contained/
> more accessible to "non-lockdep-experts".
>
Yeah. I will do that in next spin. Thanks!
Regards,
Boqun
> Andrea
>
>
> > +
> > +For a strong dependency circle like:
> > +
> > + A0 -> A1 -> ... -> An
> > + ^ |
> > + | |
> > + +------------------+
> > +, lockdep assumes that
> > +
> > + there may exist a case where someone is trying to acquire A1 with A0 held
> > + there may exist a case where someone is trying to acquire A2 with A1 held
> > + ...
> > + there may exist a case where someone is trying to acquire An with An-1 held
> > + there may exist a case where someone is trying to acquire A0 with An held
> > +
> > +, and because it's a *strong* dependency circle for every Ai (0<=i<=n), Ai is either
> > +held as a non-recursive lock or someone is trying to acquire Ai as a non-recursive lock,
> > +which gives:
> > +
> > +* If Ai is held as a non-recursive lock, then trying to acquire it,
> > + whether as a recursive lock or not, will get blocked.
> > +
> > +* If Ai is held as a recursive lock, then there must be someone is trying to acquire
> > + it as a non-recursive lock, and because recursive locks blocks non-recursive locks,
> > + then it(the "someone") will get blocked.
> > +
> > +So all the holders of A0, A1...An are blocked with A0, A1...An held by each other,
> > +no one can progress, therefore deadlock.
> > --
> > 2.16.1
> >
[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 488 bytes --]
next prev parent reply other threads:[~2018-02-27 2:28 UTC|newest]
Thread overview: 53+ messages / expand[flat|nested] mbox.gz Atom feed top
2018-02-22 7:08 [RFC tip/locking/lockdep v5 00/17] lockdep: Support deadlock detection for recursive read locks Boqun Feng
2018-02-22 7:08 ` [RFC tip/locking/lockdep v5 01/17] lockdep: Demagic the return value of BFS Boqun Feng
2018-02-22 7:08 ` [RFC tip/locking/lockdep v5 02/17] lockdep: Make __bfs() visit every dependency until a match Boqun Feng
2018-02-22 7:08 ` [RFC tip/locking/lockdep v5 03/17] lockdep: Redefine LOCK_*_STATE* bits Boqun Feng
2018-02-22 7:08 ` [RFC tip/locking/lockdep v5 04/17] lockdep: Introduce lock_list::dep Boqun Feng
2018-02-23 11:55 ` Peter Zijlstra
2018-02-23 12:37 ` Boqun Feng
2018-02-24 5:32 ` Boqun Feng
2018-02-24 6:30 ` Boqun Feng
2018-02-24 8:38 ` Peter Zijlstra
2018-02-24 9:00 ` Boqun Feng
2018-02-24 9:26 ` Boqun Feng
2018-02-26 9:00 ` Peter Zijlstra
2018-02-26 10:15 ` Boqun Feng
2018-02-26 10:20 ` Boqun Feng
2018-02-24 7:31 ` Boqun Feng
2018-02-22 7:08 ` [RFC tip/locking/lockdep v5 05/17] lockdep: Extend __bfs() to work with multiple kinds of dependencies Boqun Feng
2018-02-22 14:26 ` Peter Zijlstra
2018-02-22 15:12 ` Boqun Feng
2018-02-22 15:30 ` Peter Zijlstra
2018-02-22 15:51 ` Peter Zijlstra
2018-02-22 16:31 ` Boqun Feng
2018-02-23 5:02 ` Boqun Feng
2018-02-23 11:15 ` Peter Zijlstra
2018-02-22 16:08 ` Peter Zijlstra
2018-02-22 16:34 ` Boqun Feng
2018-02-22 16:32 ` Peter Zijlstra
2018-02-22 7:08 ` [RFC tip/locking/lockdep v5 06/17] lockdep: Support deadlock detection for recursive read in check_noncircular() Boqun Feng
2018-02-22 14:54 ` Peter Zijlstra
2018-02-22 15:16 ` Peter Zijlstra
2018-02-22 15:44 ` Boqun Feng
2018-02-22 7:08 ` [RFC tip/locking/lockdep v5 07/17] lockdep: Adjust check_redundant() for recursive read change Boqun Feng
2018-02-22 17:29 ` Peter Zijlstra
2018-03-16 8:20 ` Boqun Feng
2018-02-22 7:08 ` [RFC tip/locking/lockdep v5 08/17] lockdep: Fix recursive read lock related safe->unsafe detection Boqun Feng
2018-02-22 17:41 ` Peter Zijlstra
2018-02-22 17:46 ` Peter Zijlstra
2018-02-23 8:21 ` Boqun Feng
2018-02-23 8:58 ` Boqun Feng
2018-02-23 11:36 ` Peter Zijlstra
2018-02-22 7:08 ` [RFC tip/locking/lockdep v5 09/17] lockdep: Add recursive read locks into dependency graph Boqun Feng
2018-02-22 7:08 ` [RFC tip/locking/lockdep v5 10/17] lockdep/selftest: Add a R-L/L-W test case specific to chain cache behavior Boqun Feng
2018-02-22 7:08 ` [RFC tip/locking/lockdep v5 11/17] lockdep: Take read/write status in consideration when generate chainkey Boqun Feng
2018-02-22 7:08 ` [RFC tip/locking/lockdep v5 12/17] lockdep/selftest: Unleash irq_read_recursion2 and add more Boqun Feng
2018-02-22 7:09 ` [RFC tip/locking/lockdep v5 13/17] lockdep/selftest: Add more recursive read related test cases Boqun Feng
2018-02-22 7:09 ` [RFC tip/locking/lockdep v5 14/17] Revert "locking/lockdep/selftests: Fix mixed read-write ABBA tests" Boqun Feng
2018-02-22 7:09 ` [RFC tip/locking/lockdep v5 15/17] lockdep: Reduce the size of lock_list Boqun Feng
2018-02-23 11:38 ` Peter Zijlstra
2018-02-23 12:40 ` Boqun Feng
2018-02-22 7:09 ` [RFC tip/locking/lockdep v5 16/17] lockdep: Documention for recursive read lock detection reasoning Boqun Feng
2018-02-24 22:53 ` Andrea Parri
2018-02-27 2:32 ` Boqun Feng [this message]
2018-02-22 7:09 ` [RFC tip/locking/lockdep v5 17/17] MAINTAINERS: Add myself as a LOCKING PRIMITIVES reviewer Boqun Feng
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20180227023220.ou7764tt56mey3or@tardis \
--to=boqun.feng@gmail.com \
--cc=corbet@lwn.net \
--cc=linux-doc@vger.kernel.org \
--cc=linux-kernel@vger.kernel.org \
--cc=mingo@redhat.com \
--cc=parri.andrea@gmail.com \
--cc=peterz@infradead.org \
--cc=rdunlap@infradead.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).