[PATCH v19 25/40] dept: add documents for dept

Add documents describing the concept and APIs of dept.

Signed-off-by: Byungchul Park <[email protected]>
---
 Documentation/dev-tools/dept.rst     | 905 +++++++++++++++++++++++++++
 Documentation/dev-tools/dept_api.rst | 124 ++++
 Documentation/dev-tools/index.rst    |   2 +
 3 files changed, 1031 insertions(+)
 create mode 100644 Documentation/dev-tools/dept.rst
 create mode 100644 Documentation/dev-tools/dept_api.rst

diff --git a/Documentation/dev-tools/dept.rst b/Documentation/dev-tools/dept.rst
new file mode 100644
index 000000000000..c0ed1314a5a7
--- /dev/null
+++ b/Documentation/dev-tools/dept.rst
@@ -0,0 +1,905 @@
+DEPT(DEPendency Tracker)
+========================
+
+Started by Byungchul Park <[email protected]>
+
+How lockdep works
+-----------------
+
+Lockdep detects deadlocks by checking lock acquisition order. For
+example, a graph to track acquisition order built by lockdep might look
+like:
+
+.. code-block::
+
+   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 at
+runtime. For example, 'E -> C' will be added when the two locks have
+been acquired in the order E and then C. The graph will look like:
+
+.. code-block::
+
+       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:
+
+.. code-block::
+
+                -> 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 and stops
+working.
+
+CONCLUSION
+
+Lockdep detects a deadlock by checking if a loop has been created after
+adding a new acquisition order into the graph.
+
+
+Limitation of lockdep
+---------------------
+
+Lockdep deals with deadlocks involving typical locks e.g. spinlock and
+mutex, that are supposed to be released within the acquisition context.
+However, when it comes to a deadlock involving folio lock that is not
+supposed to be released within the acquisition context or other general
+synchronization mechanisms, lockdep doesn't work.
+
+NOTE: In this document, 'context' refers to any type of unique context
+e.g. irq context, normal process context, wq worker context, and so on.
+
+Can lockdep detect the following deadlock?
+
+.. code-block::
+
+   context X	   context Y	   context Z
+
+		   mutex_lock A
+   folio_lock B
+		   folio_lock B <- DEADLOCK
+				   mutex_lock A <- DEADLOCK
+				   folio_unlock B
+		   folio_unlock B
+		   mutex_unlock A
+				   mutex_unlock A
+
+No. What about the following?
+
+.. code-block::
+
+   context X	   context Y
+
+		   mutex_lock A
+   mutex_lock A <- DEADLOCK
+		   wait_for_completion B <- DEADLOCK
+   complete B
+		   mutex_unlock A
+   mutex_unlock A
+
+No.
+
+CONCLUSION
+
+Lockdep cannot detect a deadlock involving folio lock or other general
+synchronization mechanisms.
+
+
+What leads to a deadlock
+------------------------
+
+A deadlock occurs when one or more contexts are waiting for events that
+will never happen. For example:
+
+.. code-block::
+
+   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 this **deadlock**.
+
+If an event occurrence to awaken its wait is a prerequisite to reaching
+another event, we call it **dependency**. In this example:
+
+   * 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.
+
+Dependency graph reflecting this example will look like:
+
+.. code-block::
+
+    -> C -> A -> B -
+   /                \
+   \                /
+    ----------------
+
+   where 'A -> B' means that event A depends on event B.
+
+A circular dependency exists. Such a circular dependency leads to a
+deadlock since no waiters can have desired events triggered.
+
+CONCLUSION
+
+A circular dependency of events leads to a deadlock.
+
+
+Introduce DEPT
+--------------
+
+DEPT(DEPendency Tracker) tracks wait and event instead of lock
+acquisition order so as to recognize the following situation:
+
+.. code-block::
+
+   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 at runtime that is similar to lockdep.
+The graph might look like:
+
+.. code-block::
+
+    -> C -> A -> B -
+   /                \
+   \                /
+    ----------------
+
+   where 'A -> B' means that event A depends on event B.
+
+DEPT keeps adding each new dependency into the graph at runtime. For
+example, 'B -> D' will be added when event D occurrence is a
+prerequisite to reaching event B like:
+
+.. code-block::
+
+   context W
+
+   |
+   v
+   wait for D
+   .
+   event B
+
+After the addition, the graph will look like:
+
+.. code-block::
+
+                     -> 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 potential
+deadlocks.
+
+
+How DEPT works
+--------------
+
+Let's take a look at how DEPT works with the 1st example in the section
+'Limitation of lockdep'.
+
+.. code-block::
+
+   context X	   context Y	   context Z
+
+		   mutex_lock A
+   folio_lock B
+		   folio_lock B <- DEADLOCK
+				   mutex_lock A <- DEADLOCK
+				   folio_unlock B
+		   folio_unlock B
+		   mutex_unlock A
+				   mutex_unlock A
+
+NOTE: In this document, 'event context' refers to a portion within a
+context where an interesting event is triggered in, between a point
+where the context has started progressing toward the event, and the
+event.
+
+Adding comments to describe DEPT's view in detail:
+
+.. code-block::
+
+   context X	   context Y	   context Z
+
+		   mutex_lock A
+		   /* might wait for A */
+		   /* start to take into account event A's context */
+		   /* 1 */
+   folio_lock B
+   /* might wait for B */
+   /* start to take into account event B's context */
+   /* 2 */
+
+		   folio_lock B
+		   /* might wait for B */ <- DEADLOCK
+		   /* start to take into account event B's context */
+		   /* 3 */
+
+				   mutex_lock A
+				   /* might wait for A */ <- DEADLOCK
+				   /* start to take into account
+				      event A's context */
+				   /* 4 */
+
+				   folio_unlock B
+				   /* event B that has been valid since 2 */
+		   folio_unlock B
+		   /* event B that has been valid since 3 */
+
+		   mutex_unlock A
+		   /* event A that has been valid since 1 */
+
+				   mutex_unlock A
+				   /* event A that has been valid since 4 */
+
+Let's build up a dependency graph with this example. Firstly, context X:
+
+.. code-block::
+
+   context X
+
+   folio_lock B
+   /* might wait for B */
+   /* start to take into account event B's context */
+   /* 2 */
+
+There are no events to create dependency. Next, context Y:
+
+.. code-block::
+
+   context Y
+
+   mutex_lock A
+   /* might wait for A */
+   /* start to take into account event A's context */
+   /* 1 */
+
+   folio_lock B
+   /* might wait for B */
+   /* start to take into account event B's context */
+   /* 3 */
+
+   folio_unlock B
+   /* event B that has been valid since 3 */
+
+   mutex_unlock A
+   /* event A that has been valid since 1 */
+
+There are two events, folio_unlock B a.k.a. event B and mutex_unlock A
+a.k.a. event A. For event B, since there are no waits between 3 and the
+event, event B does not create any dependency. For event A, there is a
+wait, folio_lock B a.k.a. wait B, between 1 and the event. Which means
+event A cannot be triggered if wait B cannot be awakened by event B.
+Therefore, we can say event A depends on event B, say, 'A -> B'. The
+graph will look like after adding the dependency:
+
+.. code-block::
+
+   A -> B
+
+   where 'A -> B' means that event A depends on event B.
+
+Lastly, context Z:
+
+.. code-block::
+
+   context Z
+
+   mutex_lock A
+   /* might wait for A */
+   /* start to take into account event A's context */
+   /* 4 */
+
+   folio_unlock B
+   /* event B that has been valid since 2 */
+
+   mutex_unlock A
+   /* event A that has been valid since 4 */
+
+There are also two events, folio_unlock B a.k.a. event B and
+mutex_unlock A a.k.a. event A. For event B, there is a wait, mutex_lock
+A a.k.a. wait A, between 2 and the event. Which means event B cannot be
+triggered if wait A cannot be awakened by event A. Therefore, we can
+say event B depends on event A, say, 'B -> A'. The graph will look like
+after adding the dependency:
+
+.. code-block::
+
+    -> A -> B -
+   /           \
+   \           /
+    -----------
+
+   where 'A -> B' means that event A depends on event B.
+
+A new loop has been created. So DEPT can report it as a deadlock. For
+event A, since there are no waits between 4 and the event, event A does
+not create any dependency. That's it.
+
+Let's take a look at how DEPT works with the 2nd example in the section
+'Limitation of lockdep'.
+
+.. code-block::
+
+   context X	   context Y
+
+		   mutex_lock A
+   mutex_lock A <- DEADLOCK
+		   wait_for_completion B <- DEADLOCK
+   complete B
+		   mutex_unlock A
+   mutex_unlock A
+
+Similarly adding comments to describe DEPT's view in detail:
+
+.. code-block::
+
+   context X	   context Y
+
+		   mutex_lock A
+                   /* might wait for A */
+                   /* start to take into account event A's context */
+                   /* 1 */
+
+                   request_something_and_complete_B
+                   /* request to handle something via e.g. wq, daemon,
+                      or any its own way, and finally do 'complete B'
+                      a.k.a. event B */
+                   /* 2 */
+   /* notice the request from 2 and handle it running toward event B */
+   /* start to take into account event B's context */
+   /* 3 */
+
+   mutex_lock A
+   /* might wait for A */ <- DEADLOCK
+   /* start to take into account event A's context */
+   /* 4 */
+		   wait_for_completion B
+                   /* wait for B */ <- DEADLOCK
+                   /* 5 */
+   complete B
+   /* event B that has been valid since 3 */
+		   mutex_unlock A
+                   /* event A that has been valid since 1 */
+   mutex_unlock A
+   /* event A that has been valid since 4 */
+
+Let's build up a dependency graph with this example. Firstly, context X:
+
+.. code-block::
+
+   context X
+
+   /* notice the request from 2 and handle it running toward event B */
+   /* start to take into account event B's context */
+   /* 3 */
+
+   mutex_lock A
+   /* might wait for A */
+   /* start to take into account event A's context */
+   /* 4 */
+
+   complete B
+   /* event B that has been valid since 3 */
+
+   mutex_unlock A
+   /* event A that has been valid since 4 */
+
+There are two events, complete B a.k.a. event B and mutex_unlock A a.k.a.
+event A. For event A, since there are no waits between between 4 and the
+event, event A does not create any dependency. For event B, there is a
+wait, mutex_lock A a.k.a. wait A, between 3 and the event. Which means
+event B cannot be triggered if wait A cannot be awakened by event A.
+Therefore, we can say event B depends on event A, say, 'B -> A'. The
+graph will look like after adding the dependency:
+
+.. code-block::
+
+   B -> A
+
+   where 'A -> B' means that event A depends on event B.
+
+If context X might notice the request after mutex_lock A, DEPT cannot
+track this dependency, which results in missing a dependency. However,
+that can be improved by adding proper DEPT annotations if needed.
+
+Next, context Y:
+
+.. code-block::
+
+   context Y
+
+   mutex_lock A
+   /* might wait for A */
+   /* start to take into account event A's context */
+   /* 1 */
+
+   request_something_and_complete_B
+   /* request to handle something via e.g. wq, daemon, or any its own
+      way, and finally do 'complete B' a.k.a. event B */
+   /* 2 */
+
+   wait_for_completion B
+   /* wait for B */
+   /* 5 */
+
+   mutex_unlock A
+   /* event A that has been valid since 1 */
+
+There is one event, mutex_unlock A a.k.a. event A. For event A, there is
+a wait, wait_for_completion B a.k.a. wait B, between 1 and the event.
+Which means event A cannot be triggered if wait B cannot be awakened by
+event B. Therefore, we can say event A depends on event B, say, 'A -> B'.
+The graph will look like after adding the dependency:
+
+.. code-block::
+
+    -> B -> A -
+   /           \
+   \           /
+    -----------
+
+   where 'A -> B' means that event A depends on event B.
+
+A new loop has been created. So DEPT can report it as a deadlock.
+
+CONCLUSION
+
+DEPT works well with any general synchronization mechanisms by focusing
+on wait, event and its context.
+
+
+Interpret DEPT report
+---------------------
+
+The following is the same example in the section 'How DEPT works'.
+
+.. code-block::
+
+   context X	   context Y	   context Z
+
+		   mutex_lock A
+		   /* might wait for A */
+		   /* start to take into account event A's context */
+		   /* 1 */
+   folio_lock B
+   /* might wait for B */
+   /* start to take into account event B's context */
+   /* 2 */
+
+		   folio_lock B
+		   /* might wait for B */ <- DEADLOCK
+		   /* start to take into account event B's context */
+		   /* 3 */
+
+				   mutex_lock A
+				   /* might wait for A */ <- DEADLOCK
+				   /* start to take into account
+				      event A's context */
+				   /* 4 */
+
+				   folio_unlock B
+				   /* event B that has been valid since 2 */
+		   folio_unlock B
+		   /* event B that has been valid since 3 */
+
+		   mutex_unlock A
+		   /* event A that has been valid since 1 */
+
+				   mutex_unlock A
+				   /* event A that has been valid since 4 */
+
+We can simplify this by labeling each waiting point with [W], each point
+where its event's context starts with [S] and each event with [E]. This
+example will look like after the labeling:
+
+.. code-block::
+
+   context X	   context Y	   context Z
+
+		   [W][S] mutex_lock A
+   [W][S] folio_lock B
+		   [W][S] folio_lock B <- DEADLOCK
+
+				   [W][S] mutex_lock A <- DEADLOCK
+				   [E] folio_unlock B
+		   [E] folio_unlock B
+		   [E] mutex_unlock A
+				   [E] mutex_unlock A
+
+DEPT uses the symbols [W], [S] and [E] in its report as described above.
+The following is an example reported by DEPT for a real problem in
+practice.
+
+.. code-block::
+
+   Link: https://lore.kernel.org/lkml/[email protected]/#t
+   Link: https://lore.kernel.org/lkml/[email protected]/
+
+   ===================================================
+   DEPT: Circular dependency has been detected.
+   6.2.0-rc1-00025-gb0c20ebf51ac-dirty #28 Not tainted
+   ---------------------------------------------------
+   summary
+   ---------------------------------------------------
+   *** DEADLOCK ***
+
+   context A
+       [S] lock(&ni->ni_lock:0)
+       [W] folio_wait_bit_common(PG_locked_map:0)
+       [E] unlock(&ni->ni_lock:0)
+
+   context B
+       [S] (unknown)(PG_locked_map:0)
+       [W] lock(&ni->ni_lock:0)
+       [E] folio_unlock(PG_locked_map:0)
+
+   [S]: start of the event context
+   [W]: the wait blocked
+   [E]: the event not reachable
+   ---------------------------------------------------
+   context A's detail
+   ---------------------------------------------------
+   context A
+       [S] lock(&ni->ni_lock:0)
+       [W] folio_wait_bit_common(PG_locked_map:0)
+       [E] unlock(&ni->ni_lock:0)
+
+   [S] lock(&ni->ni_lock:0):
+   [<ffffffff82b396fb>] ntfs3_setattr+0x54b/0xd40
+   stacktrace:
+         ntfs3_setattr+0x54b/0xd40
+         notify_change+0xcb3/0x1430
+         do_truncate+0x149/0x210
+         path_openat+0x21a3/0x2a90
+         do_filp_open+0x1ba/0x410
+         do_sys_openat2+0x16d/0x4e0
+         __x64_sys_creat+0xcd/0x120
+         do_syscall_64+0x41/0xc0
+         entry_SYSCALL_64_after_hwframe+0x63/0xcd
+
+   [W] folio_wait_bit_common(PG_locked_map:0):
+   [<ffffffff81b228b0>] truncate_inode_pages_range+0x9b0/0xf20
+   stacktrace:
+         folio_wait_bit_common+0x5e0/0xaf0
+         truncate_inode_pages_range+0x9b0/0xf20
+         truncate_pagecache+0x67/0x90
+         ntfs3_setattr+0x55a/0xd40
+         notify_change+0xcb3/0x1430
+         do_truncate+0x149/0x210
+         path_openat+0x21a3/0x2a90
+         do_filp_open+0x1ba/0x410
+         do_sys_openat2+0x16d/0x4e0
+         __x64_sys_creat+0xcd/0x120
+         do_syscall_64+0x41/0xc0
+         entry_SYSCALL_64_after_hwframe+0x63/0xcd
+
+   [E] unlock(&ni->ni_lock:0):
+   (N/A)
+   ---------------------------------------------------
+   context B's detail
+   ---------------------------------------------------
+   context B
+       [S] (unknown)(PG_locked_map:0)
+       [W] lock(&ni->ni_lock:0)
+       [E] folio_unlock(PG_locked_map:0)
+
+   [S] (unknown)(PG_locked_map:0):
+   (N/A)
+
+   [W] lock(&ni->ni_lock:0):
+   [<ffffffff82b009ec>] attr_data_get_block+0x32c/0x19f0
+   stacktrace:
+         attr_data_get_block+0x32c/0x19f0
+         ntfs_get_block_vbo+0x264/0x1330
+         __block_write_begin_int+0x3bd/0x14b0
+         block_write_begin+0xb9/0x4d0
+         ntfs_write_begin+0x27e/0x480
+         generic_perform_write+0x256/0x570
+         __generic_file_write_iter+0x2ae/0x500
+         ntfs_file_write_iter+0x66d/0x1d70
+         do_iter_readv_writev+0x20b/0x3c0
+         do_iter_write+0x188/0x710
+         vfs_iter_write+0x74/0xa0
+         iter_file_splice_write+0x745/0xc90
+         direct_splice_actor+0x114/0x180
+         splice_direct_to_actor+0x33b/0x8b0
+         do_splice_direct+0x1b7/0x280
+         do_sendfile+0xb49/0x1310
+
+   [E] folio_unlock(PG_locked_map:0):
+   [<ffffffff81f10222>] generic_write_end+0xf2/0x440
+   stacktrace:
+         generic_write_end+0xf2/0x440
+         ntfs_write_end+0x42e/0x980
+         generic_perform_write+0x316/0x570
+         __generic_file_write_iter+0x2ae/0x500
+         ntfs_file_write_iter+0x66d/0x1d70
+         do_iter_readv_writev+0x20b/0x3c0
+         do_iter_write+0x188/0x710
+         vfs_iter_write+0x74/0xa0
+         iter_file_splice_write+0x745/0xc90
+         direct_splice_actor+0x114/0x180
+         splice_direct_to_actor+0x33b/0x8b0
+         do_splice_direct+0x1b7/0x280
+         do_sendfile+0xb49/0x1310
+         __x64_sys_sendfile64+0x1d0/0x210
+         do_syscall_64+0x41/0xc0
+         entry_SYSCALL_64_after_hwframe+0x63/0xcd
+   ---------------------------------------------------
+   information that might be helpful
+   ---------------------------------------------------
+   CPU: 1 PID: 8060 Comm: a.out Not tainted
+	6.2.0-rc1-00025-gb0c20ebf51ac-dirty #28
+   Hardware name: QEMU Standard PC (i440FX + PIIX, 1996),
+	BIOS Bochs 01/01/2011
+   Call Trace:
+    <TASK>
+    dump_stack_lvl+0xf2/0x169
+    print_circle.cold+0xca4/0xd28
+    ? lookup_dep+0x240/0x240
+    ? extend_queue+0x223/0x300
+    cb_check_dl+0x1e7/0x260
+    bfs+0x27b/0x610
+    ? print_circle+0x240/0x240
+    ? llist_add_batch+0x180/0x180
+    ? extend_queue_rev+0x300/0x300
+    ? __add_dep+0x60f/0x810
+    add_dep+0x221/0x5b0
+    ? __add_idep+0x310/0x310
+    ? add_iecxt+0x1bc/0xa60
+    ? add_iecxt+0x1bc/0xa60
+    ? add_iecxt+0x1bc/0xa60
+    ? add_iecxt+0x1bc/0xa60
+    __dept_wait+0x600/0x1490
+    ? add_iecxt+0x1bc/0xa60
+    ? truncate_inode_pages_range+0x9b0/0xf20
+    ? check_new_class+0x790/0x790
+    ? dept_enirq_transition+0x519/0x9c0
+    dept_wait+0x159/0x3b0
+    ? truncate_inode_pages_range+0x9b0/0xf20
+    folio_wait_bit_common+0x5e0/0xaf0
+    ? filemap_get_folios_contig+0xa30/0xa30
+    ? dept_enirq_transition+0x519/0x9c0
+    ? lock_is_held_type+0x10e/0x160
+    ? lock_is_held_type+0x11e/0x160
+    truncate_inode_pages_range+0x9b0/0xf20
+    ? truncate_inode_partial_folio+0xba0/0xba0
+    ? setattr_prepare+0x142/0xc40
+    truncate_pagecache+0x67/0x90
+    ntfs3_setattr+0x55a/0xd40
+    ? ktime_get_coarse_real_ts64+0x1e5/0x2f0
+    ? ntfs_extend+0x5c0/0x5c0
+    ? mode_strip_sgid+0x210/0x210
+    ? ntfs_extend+0x5c0/0x5c0
+    notify_change+0xcb3/0x1430
+    ? do_truncate+0x149/0x210
+    do_truncate+0x149/0x210
+    ? file_open_root+0x430/0x430
+    ? process_measurement+0x18c0/0x18c0
+    ? ntfs_file_release+0x230/0x230
+    path_openat+0x21a3/0x2a90
+    ? path_lookupat+0x840/0x840
+    ? dept_enirq_transition+0x519/0x9c0
+    ? lock_is_held_type+0x10e/0x160
+    do_filp_open+0x1ba/0x410
+    ? may_open_dev+0xf0/0xf0
+    ? find_held_lock+0x2d/0x110
+    ? lock_release+0x43c/0x830
+    ? dept_ecxt_exit+0x31a/0x590
+    ? _raw_spin_unlock+0x3b/0x50
+    ? alloc_fd+0x2de/0x6e0
+    do_sys_openat2+0x16d/0x4e0
+    ? __ia32_sys_get_robust_list+0x3b0/0x3b0
+    ? build_open_flags+0x6f0/0x6f0
+    ? dept_enirq_transition+0x519/0x9c0
+    ? dept_enirq_transition+0x519/0x9c0
+    ? lock_is_held_type+0x4e/0x160
+    ? lock_is_held_type+0x4e/0x160
+    __x64_sys_creat+0xcd/0x120
+    ? __x64_compat_sys_openat+0x1f0/0x1f0
+    do_syscall_64+0x41/0xc0
+    entry_SYSCALL_64_after_hwframe+0x63/0xcd
+   RIP: 0033:0x7f8b9e4e4469
+   Code: 00 f3 c3 66 2e 0f 1f 84 00 00 00 00 00 0f 1f 40 00 48 89 f8 48
+   89 f7 48 89 d6 48 89 ca 4d 89 c2 4d 89 c8 4c 8b 4c 24 08 0f 05 <48>
+   3d 01 f0 ff ff 73 01 c3 48 8b 0d ff 49 2b 00 f7 d8 64 89 01 48
+   RSP: 002b:00007f8b9eea4ef8 EFLAGS: 00000202 ORIG_RAX: 0000000000000055
+   RAX: ffffffffffffffda RBX: 0000000000000000 RCX: 00007f8b9e4e4469
+   RDX: 0000000000737562 RSI: 0000000000000000 RDI: 0000000020000000
+   RBP: 00007f8b9eea4f20 R08: 0000000000000000 R09: 0000000000000000
+   R10: 0000000000000000 R11: 0000000000000202 R12: 00007fffa75511ee
+   R13: 00007fffa75511ef R14: 00007f8b9ee85000 R15: 0000000000000003
+    </TASK>
+
+Let's take a look at the summary that is the most important part.
+
+.. code-block::
+
+   ---------------------------------------------------
+   summary
+   ---------------------------------------------------
+   *** DEADLOCK ***
+
+   context A
+       [S] lock(&ni->ni_lock:0)
+       [W] folio_wait_bit_common(PG_locked_map:0)
+       [E] unlock(&ni->ni_lock:0)
+
+   context B
+       [S] (unknown)(PG_locked_map:0)
+       [W] lock(&ni->ni_lock:0)
+       [E] folio_unlock(PG_locked_map:0)
+
+   [S]: start of the event context
+   [W]: the wait blocked
+   [E]: the event not reachable
+
+The summary shows the following scenario:
+
+.. code-block::
+
+   context A	   context B	   context ?(unknown)
+
+				   [S] folio_lock(&f1)
+   [S] lock(&ni->ni_lock:0)
+   [W] folio_wait_bit_common(PG_locked_map:0)
+
+		   [W] lock(&ni->ni_lock:0)
+		   [E] folio_unlock(&f1)
+
+   [E] unlock(&ni->ni_lock:0)
+
+Adding comments to describe DEPT's view in detail:
+
+.. code-block::
+
+   context A	   context B	   context ?(unknown)
+
+				   [S] folio_lock(&f1)
+				   /* start to take into account context
+				      B heading for folio_unlock(&f1) */
+				   /* 1 */
+   [S] lock(&ni->ni_lock:0)
+   /* start to take into account this context heading for
+      unlock(&ni->ni_lock:0) */
+   /* 2 */
+
+   [W] folio_wait_bit_common(PG_locked_map:0) (= folio_lock(&f1))
+   /* might wait for folio_unlock(&f1) */
+
+		   [W] lock(&ni->ni_lock:0)
+		   /* might wait for unlock(&ni->ni_lock:0) */
+
+		   [E] folio_unlock(&f1)
+		   /* event that has been valid since 1 */
+
+   [E] unlock(&ni->ni_lock:0)
+   /* event that has been valid since 2 */
+
+Let's build up a dependency graph with this report. Firstly, context A:
+
+.. code-block::
+
+   context A
+
+   [S] lock(&ni->ni_lock:0)
+   /* start to take into account this context heading for
+      unlock(&ni->ni_lock:0) */
+   /* 2 */
+
+   [W] folio_wait_bit_common(PG_locked_map:0) (= folio_lock(&f1))
+   /* might wait for folio_unlock(&f1) */
+
+   [E] unlock(&ni->ni_lock:0)
+   /* event that has been valid since 2 */
+
+There is one event, unlock(&ni->ni_lock:0). There is a wait,
+folio_lock(&f1), between 2 and the event. Which means
+unlock(&ni->ni_lock:0) is not reachable if folio_lock(&f1) cannot be
+awakened by the owner's folio_unlock(&f1). Therefore, we can say
+unlock(&ni->ni_lock:0) depends on folio_unlock(&f1), say,
+'unlock(&ni->ni_lock:0) -> folio_unlock(&f1)'.
+
+The graph will look like after adding the dependency:
+
+.. code-block::
+
+   unlock(&ni->ni_lock:0) -> folio_unlock(&f1)
+
+   where 'A -> B' means that event A depends on event B.
+
+Secondly, context B:
+
+.. code-block::
+
+   context B
+
+   [W] lock(&ni->ni_lock:0)
+   /* might wait for unlock(&ni->ni_lock:0) */
+
+   [E] folio_unlock(&f1)
+   /* event that has been valid since 1 */
+
+There is also one event, folio_unlock(&f1). There is a wait,
+lock(&ni->ni_lock:0), between 1 and the event. Which means
+folio_unlock(&f1) is not reachable if lock(&ni->ni_lock:0) cannot be
+awakened by the owner's unlock(&ni->ni_lock:0). Therefore, we can say
+folio_unlock(&f1) depends on unlock(&ni->ni_lock:0), say,
+'folio_unlock(&f1) -> unlock(&ni->ni_lock:0)'.
+
+The graph will look like after adding the dependency:
+
+.. code-block::
+
+    -> unlock(&ni->ni_lock:0) -> folio_unlock(&f1) -
+   /                                                \
+   \                                                /
+    ------------------------------------------------
+
+   where 'A -> B' means that event A depends on event B.
+
+A new loop has been created. So DEPT can report it as a deadlock! Cool!
+
+CONCLUSION
+
+DEPT works awesome!
diff --git a/Documentation/dev-tools/dept_api.rst b/Documentation/dev-tools/dept_api.rst
new file mode 100644
index 000000000000..6706d206f6bf
--- /dev/null
+++ b/Documentation/dev-tools/dept_api.rst
@@ -0,0 +1,124 @@
+DEPT(DEPendency Tracker) APIs
+=============================
+
+Started by Byungchul Park <[email protected]>
+
+SDT(Single-event Dependency Tracker) APIs
+-----------------------------------------
+Use these APIs to annotate either wait or event. These have been already
+applied to the existing synchronization primitives e.g. waitqueue, swait,
+wait_for_completion(), dma fence and so on. The basic APIs of SDT are:
+
+.. code-block:: c
+
+   /*
+    * After defining 'struct dept_map map', initialize the instance.
+    */
+   sdt_map_init(map);
+
+   /*
+    * Place just before the interesting wait.
+    */
+   sdt_wait(map);
+
+   /*
+    * Place just before the interesting event.
+    */
+   sdt_event(map);
+
+The advanced APIs of SDT are:
+
+.. code-block:: c
+
+   /*
+    * After defining 'struct dept_map map', initialize the instance
+    * using an external key.
+    */
+   sdt_map_init_key(map, key);
+
+   /*
+    * Place just before the interesting timeout wait.
+    */
+   sdt_wait_timeout(map, time);
+
+   /*
+    * Use sdt_might_sleep_start() and sdt_might_sleep_end() in pair.
+    * Place at the start of the interesting section that might enter
+    * schedule() or its family that needs to be woken up by
+    * try_to_wake_up().
+    */
+   sdt_might_sleep_start(map);
+
+   /*
+    * Use sdt_might_sleep_start_timeout() and sdt_might_sleep_end() in
+    * pair. Place at the start of the interesting section that might
+    * enter schedule_timeout() or its family that needs to be woken up
+    * by try_to_wake_up().
+    */
+   sdt_might_sleep_start_timeout(map, time);
+
+   /*
+    * Use sdt_might_sleep_start() and sdt_might_sleep_end() in pair.
+    * Place at the end of the interesting section that might enter
+    * schedule(), schedule_timeout() or its family that needs to be
+    * woken up by try_to_wake_up().
+    */
+   sdt_might_sleep_end();
+
+   /*
+    * Use sdt_ecxt_enter() and sdt_ecxt_exit() in pair. Place at the
+    * start of the interesting section where the interesting event might
+    * be triggered.
+    */
+   sdt_ecxt_enter(map);
+
+   /*
+    * Use sdt_ecxt_enter() and sdt_ecxt_exit() in pair. Place at the
+    * end of the interesting section where the interesting event might
+    * be triggered.
+    */
+   sdt_ecxt_exit(map);
+
+
+LDT(Lock Dependency Tracker) APIs
+---------------------------------
+Do not use these APIs directly. These are wrappers for typical locks
+that have been already applied to major locks internally e.g. spin lock,
+mutex, rwlock and so on. The APIs of LDT are:
+
+.. code-block:: c
+
+   ldt_init(map, key, sub, name);
+   ldt_lock(map, sub_local, try, nest, ip);
+   ldt_rlock(map, sub_local, try, nest, ip, queued);
+   ldt_wlock(map, sub_local, try, nest, ip);
+   ldt_unlock(map, ip);
+   ldt_downgrade(map, ip);
+   ldt_set_class(map, name, key, sub_local, ip);
+
+
+Raw APIs
+--------
+Do not use these APIs directly. The raw APIs of dept are:
+
+.. code-block:: c
+
+   dept_free_range(start, size);
+   dept_map_init(map, key, sub, name);
+   dept_map_reinit(map, key, sub, name);
+   dept_ext_wgen_init(ext_wgen);
+   dept_map_copy(map_to, map_from);
+   dept_wait(map, wait_flags, ip, wait_func, sub_local, time);
+   dept_stage_wait(map, key, ip, wait_func, time);
+   dept_request_event_wait_commit();
+   dept_clean_stage();
+   dept_ttwu_stage_wait(task, ip);
+   dept_ecxt_enter(map, evt_flags, ip, ecxt_func, evt_func, sub_local);
+   dept_ecxt_holding(map, evt_flags);
+   dept_request_event(map, ext_wgen);
+   dept_event(map, evt_flags, ip, evt_func, ext_wgen);
+   dept_ecxt_exit(map, evt_flags, ip);
+   dept_ecxt_enter_nokeep(map);
+   dept_key_init(key);
+   dept_key_destroy(key);
+   dept_map_ecxt_modify(map, cur_evt_flags, key, evt_flags, ip, ecxt_func, evt_func, sub_local);
diff --git a/Documentation/dev-tools/index.rst b/Documentation/dev-tools/index.rst
index 59cbb77b33ff..0f37940e4c6e 100644
--- a/Documentation/dev-tools/index.rst
+++ b/Documentation/dev-tools/index.rst
@@ -23,6 +23,8 @@ Documentation/process/debugging/index.rst
    coccinelle
    context-analysis
    sparse
+   dept
+   dept_api
    kcov
    gcov
    kasan
-- 
2.17.1