LKML Archive on lore.kernel.org
help / color / mirror / Atom feed
From: Yuyang Du <duyuyang@gmail.com>
To: peterz@infradead.org, will.deacon@arm.com, mingo@kernel.org
Cc: bvanassche@acm.org, ming.lei@redhat.com, frederic@kernel.org,
	tglx@linutronix.de, boqun.feng@gmail.com,
	linux-kernel@vger.kernel.org, Yuyang Du <duyuyang@gmail.com>
Subject: [PATCH 14/17] locking/lockdep: Support recursive read locks
Date: Mon, 13 May 2019 17:12:00 +0800	[thread overview]
Message-ID: <20190513091203.7299-15-duyuyang@gmail.com> (raw)
In-Reply-To: <20190513091203.7299-1-duyuyang@gmail.com>

Now we are good to finally support recursive read locks.

This is done simply by adding the dependency that has recursive locks to the
graph, which previously is skipped.

The reason is plainly simple:

  (a). Recursive read lock differs from read lock only inside a task.
  (b). check_deadlock_current() already handles recursive-read lock pretty
       well.

Now that the bulk of the implementation of the read-write lock deadlock
detection algorithm is done, the lockdep internal performance statistics can
be collected (the workload used as usual is: make clean; reboot; make vmlinux -j8):

Before
------
 direct dependencies:                  8980 [max: 32768]
 indirect dependencies:               41065
 all direct dependencies:            211016
 dependency chains:                   11592 [max: 65536]
 dependency chain hlocks:             42869 [max: 327680]
 in-hardirq chains:                      85
 in-softirq chains:                     385
 in-process chains:                   10250
 stack-trace entries:                123121 [max: 524288]
 combined max dependencies:       340292196
 max bfs queue depth:                   244
 chain lookup misses:                 12703
 chain lookup hits:               666620822
 cyclic checks:                       11392
 redundant checks:                        0

After
-----

 direct dependencies:                  9624 [max: 32768]
 indirect dependencies:               43759
 all direct dependencies:            216024
 dependency chains:                   12119 [max: 65536]
 dependency chain hlocks:             44654 [max: 327680]
 in-hardirq chains:                      88
 in-softirq chains:                     383
 in-process chains:                   10544
 stack-trace entries:                132362 [max: 524288]
 combined max dependencies:       360385920
 max bfs queue depth:                   250
 chain lookup misses:                 13528
 chain lookup hits:               664721852
 cyclic checks:                       12053
 redundant checks:                        0

Most noticeably, we have slightly more dependencies, chains, and chain
lookup misses, but none of them raises concerns.

Signed-off-by: Yuyang Du <duyuyang@gmail.com>
---
 kernel/locking/lockdep.c | 47 +++++++++++++++++++++++++++--------------------
 1 file changed, 27 insertions(+), 20 deletions(-)

diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index 417b23d..69d6bd6 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -1805,6 +1805,9 @@ static inline void set_lock_type2(struct lock_list *lock, int read)
 		.parent = NULL,
 	};
 
+	if (DEBUG_LOCKS_WARN_ON(hlock_class(src) == hlock_class(target)))
+		return 0;
+
 	debug_atomic_inc(nr_cyclic_checks);
 
 	while (true) {
@@ -1861,9 +1864,17 @@ static inline void set_lock_type2(struct lock_list *lock, int read)
 					break;
 
 				/*
+				 * This previous lock has the same class as
+				 * the src (the next lock to acquire); this
+				 * must be a recursive read case. Skip.
+				 */
+				if (hlock_class(prev) == hlock_class(src))
+					continue;
+
+				/*
 				 * Since the src lock (the next lock to
-				 * acquire) is neither recursive nor nested
-				 * lock, so this prev class cannot be src
+				 * acquire) is not nested lock, so up to
+				 * now this prev class cannot be the src
 				 * class, then does the path have this
 				 * previous lock?
 				 *
@@ -2609,6 +2620,17 @@ static inline void inc_chains(void)
 	}
 
 	/*
+	 * Filter out the direct dependency with the same lock class, which
+	 * is legitimate only if both the locks have the recursive read
+	 * type, otherwise we should not have been here in the first place.
+	 */
+	if (hlock_class(prev) == hlock_class(next)) {
+		WARN_ON_ONCE(next->read != LOCK_TYPE_RECURSIVE);
+		WARN_ON_ONCE(prev->read != LOCK_TYPE_RECURSIVE);
+		return 2;
+	}
+
+	/*
 	 * Prove that the new <prev> -> <next> dependency would not
 	 * create a deadlock scenario in the graph. (We do this by
 	 * a breadth-first search into the graph starting at <next>,
@@ -2626,16 +2648,6 @@ static inline void inc_chains(void)
 		return 0;
 
 	/*
-	 * For recursive read-locks we do all the dependency checks,
-	 * but we dont store read-triggered dependencies (only
-	 * write-triggered dependencies). This ensures that only the
-	 * write-side dependencies matter, and that if for example a
-	 * write-lock never takes any other locks, then the reads are
-	 * equivalent to a NOP.
-	 */
-	if (next->read == LOCK_TYPE_RECURSIVE || prev->read == LOCK_TYPE_RECURSIVE)
-		return 1;
-	/*
 	 * Is the <prev> -> <next> dependency already present?
 	 *
 	 * (this may occur even though this is a new chain: consider
@@ -2734,11 +2746,7 @@ static inline void inc_chains(void)
 		int distance = curr->lockdep_depth - depth + 1;
 		hlock = curr->held_locks + depth - 1;
 
-		/*
-		 * Only non-recursive-read entries get new dependencies
-		 * added:
-		 */
-		if (hlock->read != LOCK_TYPE_RECURSIVE && hlock->check) {
+		if (hlock->check) {
 			int ret = check_prev_add(curr, hlock, next, distance,
 						 &trace);
 			if (!ret)
@@ -3131,10 +3139,9 @@ static int validate_chain(struct task_struct *curr,
 
 		/*
 		 * Add dependency only if this lock is not the head
-		 * of the chain, and if it's not a secondary read-lock:
+		 * of the chain, and if it's not a nest lock:
 		 */
-		if (!chain_head && ret != LOCK_TYPE_RECURSIVE &&
-		    ret != LOCK_TYPE_NEST) {
+		if (!chain_head && ret != LOCK_TYPE_NEST) {
 			if (!check_prevs_add(curr, hlock))
 				return 0;
 		}
-- 
1.8.3.1


  parent reply	other threads:[~2019-05-13  9:14 UTC|newest]

Thread overview: 22+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2019-05-13  9:11 [PATCH 00/17] Support for read-write lock deadlock detection Yuyang Du
2019-05-13  9:11 ` [PATCH 01/17] locking/lockdep: Add lock type enum to explicitly specify read or write locks Yuyang Du
2019-05-13 11:45   ` Peter Zijlstra
2019-05-14  1:31     ` Yuyang Du
2019-05-14 12:04       ` Peter Zijlstra
2019-05-13  9:11 ` [PATCH 02/17] locking/lockdep: Add read-write type for dependency Yuyang Du
2019-05-13  9:11 ` [PATCH 03/17] locking/lockdep: Add helper functions to operate on the searched path Yuyang Du
2019-05-13  9:11 ` [PATCH 04/17] locking/lockdep: Update direct dependency's read-write type if it exists Yuyang Du
2019-05-13  9:11 ` [PATCH 05/17] locking/lockdep: Rename deadlock check functions Yuyang Du
2019-05-13  9:11 ` [PATCH 06/17] locking/lockdep: Adjust BFS algorithm to support multiple matches Yuyang Du
2019-05-13  9:11 ` [PATCH 07/17] locking/lockdep: Introduce mark_lock_unaccessed() Yuyang Du
2019-05-13  9:11 ` [PATCH 08/17] locking/lockdep: Introduce chain_hlocks_type for held lock's read-write type Yuyang Du
2019-05-13  9:11 ` [PATCH 09/17] locking/lockdep: Hash held lock's read-write type into chain key Yuyang Du
2019-05-13  9:11 ` [PATCH 10/17] locking/lockdep: Support read-write lock's deadlock detection Yuyang Du
2019-05-13  9:11 ` [PATCH 11/17] locking/lockdep: Adjust lockdep selftest cases Yuyang Du
2019-05-13  9:11 ` [PATCH 12/17] locking/lockdep: Remove useless lock type assignment Yuyang Du
2019-05-13  9:11 ` [PATCH 13/17] locking/lockdep: Add nest lock type Yuyang Du
2019-05-13  9:12 ` Yuyang Du [this message]
2019-05-13  9:12 ` [PATCH 15/17] locking/lockdep: Adjust selftest case for recursive read lock Yuyang Du
2019-05-13  9:12 ` [PATCH 16/17] locking/lockdep: Add more lockdep selftest cases Yuyang Du
2019-05-13  9:12 ` [PATCH 17/17] locking/lockdep: Remove irq-safe to irq-unsafe read check Yuyang Du
2019-05-13  9:17 ` [PATCH 00/17] Support for read-write lock deadlock detection Yuyang Du

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=20190513091203.7299-15-duyuyang@gmail.com \
    --to=duyuyang@gmail.com \
    --cc=boqun.feng@gmail.com \
    --cc=bvanassche@acm.org \
    --cc=frederic@kernel.org \
    --cc=linux-kernel@vger.kernel.org \
    --cc=ming.lei@redhat.com \
    --cc=mingo@kernel.org \
    --cc=peterz@infradead.org \
    --cc=tglx@linutronix.de \
    --cc=will.deacon@arm.com \
    --subject='Re: [PATCH 14/17] locking/lockdep: Support recursive read locks' \
    /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

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).