[PATCH v12 27/27] dept: Add 'Dept' documentation

[Byungchul Park]

This document describes the concept of Dept.

Signed-off-by: Byungchul Park <byungchul@xxxxxx>
---
 Documentation/dependency/dept.txt | 283 ++++++++++++++++++++++++++++++
 1 file changed, 283 insertions(+)
 create mode 100644 Documentation/dependency/dept.txt

diff --git a/Documentation/dependency/dept.txt b/Documentation/dependency/dept.txt
new file mode 100644
index 000000000000..7efe3bc59b2d
--- /dev/null
+++ b/Documentation/dependency/dept.txt
@@ -0,0 +1,283 @@
+DEPT(DEPendency Tracker)
+========================
+
+Started by Byungchul Park <max.byungchul.park@xxxxxx>
+
+How lockdep works
+-----------------
+
+Lockdep tries to detect a deadlock by checking lock acquisition order.
+For example, consider a graph built by lockdep like:
+
+   A -> B -
+           \
+            -> E
+           /
+   C -> D -
+
+   where 'A -> B' means that acquisition A is prior to acquisition B
+   with A still held.
+
+Lockdep keeps adding each new acquisition order into the graph in
+runtime. For example, 'E -> C' will be added when it's recognized that
+the two locks have been acquired in that order like:
+
+       A -> B -
+               \
+                -> E -
+               /      \
+    -> C -> D -        \
+   /                   /
+   \                  /
+    ------------------
+
+   where 'A -> B' means that acquisition A is prior to acquisition B
+   with A still held.
+
+This graph contains a subgraph that demonstrates a loop like:
+
+                -> E -
+               /      \
+    -> C -> D -        \
+   /                   /
+   \                  /
+    ------------------
+
+   where 'A -> B' means that acquisition A is prior to acquisition B
+   with A still held.
+
+Lockdep reports it as a deadlock on detection of a loop.
+
+CONCLUSION
+
+Lockdep detects a deadlock by checking if a loop has been created after
+expanding the graph.
+
+
+Limitation of lockdep
+---------------------
+
+Lockdep works on typical lock e.g. spinlock and mutex, that are supposed
+to be released within the acquisition context. However, a deadlock by
+folio lock or other synchronization mechanisms cannot be detected by
+lockdep that basically tracks lock acquisition order.
+
+Can we detect the following deadlock?
+
+   CONTEXT X	   CONTEXT Y	   CONTEXT Z
+
+		   mutex_lock A
+   folio_lock B
+		   folio_lock B
+				   mutex_lock A /* DEADLOCK */
+				   folio_unlock B
+		   folio_unlock B
+		   mutex_unlock A
+				   mutex_unlock A
+
+No, we can't. What about the following?
+
+   CONTEXT X		   CONTEXT Y
+
+			   mutex_lock A
+   mutex_lock A
+			   wait_for_complete B /* DEADLOCK */
+   complete B
+			   mutex_unlock A
+   mutex_unlock A
+
+No, we can't.
+
+CONCLUSION
+
+Given the limitation, lockdep cannot detect a deadlock by folio lock or
+other synchronization mechanisms.
+
+
+What leads a deadlock
+---------------------
+
+A deadlock occurs when one or multi contexts are waiting for events that
+will never happen. For example:
+
+   CONTEXT X	   CONTEXT Y	   CONTEXT Z
+
+   |		   |		   |
+   v		   |		   |
+   (1) wait for A  v		   |
+   .		   (2) wait for C  v
+   event C	   .		   (3) wait for B
+		   event B	   .
+				   event A
+
+Event C cannot be triggered because context X is stuck at (1), event B
+cannot be triggered because context Y is stuck at (2), and event A
+cannot be triggered because context Z is stuck at (3). All the contexts
+are stuck. We call the situation a *deadlock*.
+
+If an event occurrence is a prerequisite to reaching another event, we
+call it *dependency*. In the example above:
+
+   Event A occurrence is a prerequisite to reaching event C.
+   Event C occurrence is a prerequisite to reaching event B.
+   Event B occurrence is a prerequisite to reaching event A.
+
+In terms of dependency:
+
+   Event C depends on event A.
+   Event B depends on event C.
+   Event A depends on event B.
+
+Dependencies in a graph look like:
+
+    -> C -> A -> B -
+   /                \
+   \                /
+    ----------------
+
+   where 'A -> B' means that event A depends on event B.
+
+A circular dependency exists. Such a circular dependency leads a
+deadlock since no waiters can have desired events triggered.
+
+CONCLUSION
+
+A circular dependency leads a deadlock.
+
+
+Introduce DEPT
+--------------
+
+DEPT(DEPendency Tracker) tracks wait and event instead of lock
+acquisition order so as to recognize the following situation:
+
+   CONTEXT X	   CONTEXT Y	   CONTEXT Z
+
+   |		   |		   |
+   v		   |		   |
+   wait for A	   v		   |
+   .		   wait for C	   v
+   event C	   .		   wait for B
+		   event B	   .
+				   event A
+
+and builds up a dependency graph in runtime, similar to lockdep. The
+graph would look like:
+
+    -> C -> A -> B -
+   /                \
+   \                /
+    ----------------
+
+   where 'A -> B' means that event A depends on event B.
+
+DEPT keeps adding each new dependency into the graph in runtime. For
+example, 'B -> D' will be added when it's recognized that event D
+occurrence is a prerequisite to reaching event B, in other words, event
+B depends on event D like:
+
+   |
+   v
+   wait for D
+   .
+   event B
+
+After adding 'B -> D' dependency into the graph, the graph would look
+like:
+
+                     -> D
+                    /
+    -> C -> A -> B -
+   /                \
+   \                /
+    ----------------
+
+   where 'A -> B' means that event A depends on event B.
+
+DEPT is going to report a deadlock on detection of a new loop.
+
+CONCLUSION
+
+DEPT works on wait and event so as to theoretically detect all the
+potential deadlocks.
+
+
+How DEPT works
+--------------
+
+Let's take a look how DEPT works with an example that was mentioned in
+the section 'Limitation of lockdep'.
+
+   CONTEXT X	   CONTEXT Y	   CONTEXT Z
+
+		   mutex_lock A
+   folio_lock B
+		   folio_lock B
+				   mutex_lock A /* DEADLOCK */
+				   folio_unlock B
+		   folio_unlock B
+		   mutex_unlock A
+				   mutex_unlock A
+
+Add comments to describe DEPT's view using terms of wait and event.
+
+   CONTEXT X	   CONTEXT Y	   CONTEXT Z
+
+		   mutex_lock A
+		   /* start to take into account event A context */
+   folio_lock B
+   /* start to take into account event B context */
+
+		   folio_lock B
+		   /* wait for B */
+		   (1)
+				   mutex_lock A /* DEADLOCK */
+				   /* wait for A */
+				   (2)
+
+				   folio_unlock B
+				   /* event B */
+		   folio_unlock B
+		   /* not interest until reaching (1) */
+
+		   mutex_unlock A
+		   /* event A */
+				   mutex_unlock A
+				   /* not interest until reaching (2) */
+
+Focusing on wait and event, the example can be simplified like:
+
+   CONTEXT X	   CONTEXT Y	   CONTEXT Z
+
+		   |		   |
+		   |		   |
+		   v		   |
+		   wait for B	   v
+		   .		   wait for A
+		   .		   .
+		   .		   event B
+		   event A
+
+Event A occurrence is a prerequisite to reaching event B, and event B
+occurrence is a prerequisite to reaching event A.
+
+In terms of dependency:
+
+   Event B depends on event A.
+   Event A depends on event B.
+
+Dependencies in the dependency graph look like:
+
+    -> A -> B -
+   /           \
+   \           /
+    -----------
+
+   where 'A -> B' means that event A depends on event B.
+
+A loop has been created. So DEPT can report it as a deadlock.
+
+CONCLUSION
+
+DEPT works well with any synchronization mechanisms by focusing on wait
+and event.
-- 
2.17.1