[PATCH v3 23/30] locking/lockdep: Define the two task model for lockdep checks formally

[Yuyang Du]

Lockdep effectively uses a two-task model to track workload's locking
behavior and 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 new locking behavior, the L1 -> L2 dependency.

For these two tasks, lockdep tries to find whether there exists the
inverse locking order of L1 -> L2, namely L2 -> L1. If this inverse
locking order exists, then lockdep finds 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 in terms of equivalency which affects lockdep finding
true (not false positive) deadlock scenarios. Some examples:

(The following Tx denotes concrete tasks)

    T1
    --

    L1
    L2

    (L1 and L2 released)

    L2
    L3

    T2
    --

    L1
    L2
    L3

Both 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@xxxxxxxxx>
---
 kernel/locking/lockdep.c | 68 ++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 68 insertions(+)

diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index 7d02b94..444eb62 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -1545,6 +1545,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.
  */
@@ -1584,6 +1649,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