Received-SPF: pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) client-ip=209.132.180.67;
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, linux-kernel@vger.kernel.org,
        longman@redhat.com, paulmck@linux.vnet.ibm.com,
        boqun.feng@gmail.com, Yuyang Du <duyuyang@gmail.com>
Subject: [PATCH v4 24/30] locking/lockdep: Define the two task model for lockdep checks formally
Date:   Thu, 29 Aug 2019 16:31:26 +0800
Message-Id: <20190829083132.22394-25-duyuyang@gmail.com>
In-Reply-To: <20190829083132.22394-1-duyuyang@gmail.com>
References: <20190829083132.22394-1-duyuyang@gmail.com>
MIME-Version: 1.0
Content-Transfer-Encoding: 8bit
Sender: linux-kernel-owner@vger.kernel.org
Precedence: bulk

Lockdep effectively uses a two-task model to track workload's locking
behavior and then do the checking to find inversion deadlock scenarios
based on such model. Lets explain it in detail.

When there is a new lock dependency L1 -> L2 (i.e., the current task
attempts to acquire L2 while holding L1), which is from a new lock
chain's latest two locks, lockdep's view of the world is composed of two
virtual tasks:

 - Task1: the entire previous locking behavior depicted by the forward
   lock dependency graph.

 - Task2: the current task's new locking behavior, i.e., the L1 -> L2 dependency.

Whenever a Task2 comes, lockdep tries to find in Task1 whether there exists
the inverse locking order of L1 -> L2, namely L2 -> L1. If this inverse
locking order exists, then lockdep has found the typical inversion deadlock
scenario, a.k.a, ABBA deadlock. And if not, Task2 will be merged into Task1
to become a new bigger Task1 with a bigger graph. Then this track and check
cycle goes on and on.

There is some nuances between this two-task model and the real workload
locking behavior. Some examples:

(The following Tx denotes concrete tasks)

    T1
    --

    L1
    L2

    (L1 and L2 released)

    L2
    L3

    T2
    --

    L1
    L2
    L3

T1 and T2 will produce the same Task1 from the perspective of lockdep's
two-task model. However, this model does not actually reflect the reality in
full length. In T1, L1 -> L3 actually has no "real" dependency while in T2
it is "real" (a real X -> Y lock dependency is defined as a task is
attempting to acquire Y while holding X). This may result in false positive
deadlock scenarios. For example:

Case #1.1:

    T1        T2
    --        --

    L1
    L2        L3
    L3        L1   [Deadlock]

Case #1.2 (T1 is a singular task):

    T1        T2
    --        --

    L1
    L2

    (L1 L2 released)

    L2        L3
    L3        L1   [No deadlock]

Case #1.3:

    T1a       T1b       T2
    ---       ---       --

    L1        L1
    L2        L2

    (L1 L2 released
     in T1a and T1b)

    L2        L2        L3
    L3        L3        L1   [Deadlock]

From Case #1.2 (no deadlock) to Case #1.3 (deadlock), we can see that
lockdep is also assuming there can be multiple Task1's on top of the
two-task model, and from pragmatic point of view, this assumption is not
unrealistic to make.

However, with read locks that can be fully concurrent with read locks
and not be blocked by write locks (such as the rwlock). Lockdep's such
model is flawed. For example (the following read locks, denoted as RR,
and write locks are of type rwlock):

Case #2.1:

    T1        T2
    --        --

    W1
    RR2       W3
    W3        W1   [Deadlock]

Case #2.2:

    T1a       T1b       T2
    ---       ---       --

    W1        RR2       W3
    RR2       W3        W1   [No deadlock]

Case #2.3:

    T1a       T1b       T2
    ---       ---       --

    W1        W1
    RR2       RR2

    (W1 RR2 released
     in T1a and T1b)

    RR2       RR2       W3
    W3        W3        W1   [No deadlock]

Lockdep cannot differentiate Case #2.1 from Case #2.2 and Case #2.3 or
vice versa. This is because when modeling Task1, it cannot tell whether
two neighboring direct dependencies in the graph are in the same real
task and hence create a "real" dependency.

To make up for this, the two-task model needs to be strengthened. We
previously mapped lock chains to lock dependency graph and added
read-write lock types into dependencies. This patch finally modifies the
graph traversing algorithm (__bfs()) to stop when two neighboring direct
dependencies are not in the same lock chain and the middle lock is a
recursive-read lock (rwlock).

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

diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index 3ad97bc..05c70be 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -1617,6 +1617,71 @@ static inline void set_lock_type2(struct lock_list *lock, int read)
 }
 
 /*
+ * A lock stopper in the dependency graph is a read lock that stops the
+ * graph traversal passing through it even if the two dependencies are
+ * linked in a path. A stopper sits in such two lock dependencies:
+ *
+ *     X -> RR (stopper) -> X (where RR is recursive-read lock)
+ *
+ * and these two dependencies are NOT from one lock chain.
+ */
+static inline bool
+read_lock_stopper(struct lock_list *parent, struct lock_list *child, int forward)
+{
+	struct lock_chain *chain1, *chain2;
+	struct lock_list *list[2] = { child, parent };
+	u64 key1, key2;
+	int distance, other = 1 - forward;
+
+	/* This is the source entry */
+	if (!get_lock_parent(parent))
+		return false;
+
+	if (!(get_lock_type1(list[other]) == LOCK_TYPE_RECURSIVE &&
+	      get_lock_type2(list[forward]) == LOCK_TYPE_RECURSIVE))
+		return false;
+
+	distance = list[forward]->distance;
+
+	list_for_each_entry_rcu(chain1, &list[forward]->chains, chain_entry) {
+		key1 = chain1->chain_key;
+
+		list_for_each_entry_rcu(chain2, &list[other]->chains, chain_entry) {
+			/*
+			 * If the two chains are in the same task lock stack,
+			 * we should be able to calculate key2 from key1 if
+			 * distance is 1, or calculate key1 from key2 if
+			 * distance is larger than 1.
+			 */
+			if (distance == 1) {
+				int class_idx = fw_dep_class(list[other]) - lock_classes;
+				key1 = iterate_chain_key(key1, class_idx,
+							 get_lock_type2(list[other]));
+				key2 = chain2->chain_key;
+
+				if (key1 == key2)
+					return false;
+			}
+			else {
+				int i = chain1->base, j = chain2->base;
+
+				if (chain1->depth != chain2->depth - distance)
+					continue;
+
+				for (; i < chain1->depth - 1; i++, j++)
+					if (chain_hlocks[i] != chain_hlocks[j] ||
+					    chain_hlocks_type[i] != chain_hlocks_type[i])
+						continue;
+
+				return false;
+			}
+		}
+	}
+
+	return true;
+}
+
+/*
  * Forward- or backward-dependency search, used for both circular dependency
  * checking and hardirq-unsafe/softirq-unsafe checking.
  */
@@ -1656,6 +1721,9 @@ static int __bfs(struct lock_list *source_entry,
 			if (!lock_accessed(entry, forward)) {
 				unsigned int cq_depth;
 
+				if (read_lock_stopper(lock, entry, forward))
+					continue;
+
 				mark_lock_accessed(entry, lock, forward);
 
 				if (__cq_enqueue(cq, entry)) {
-- 
1.8.3.1