On Thu, Oct 02, 2025 at 05:12:28PM +0900, Byungchul Park wrote:
> This document describes the concept and APIs of dept.
>
> Signed-off-by: Byungchul Park <byungc...@sk.com>
> ---
> Documentation/dependency/dept.txt | 735 ++++++++++++++++++++++++++
> Documentation/dependency/dept_api.txt | 117 ++++
> 2 files changed, 852 insertions(+)
> create mode 100644 Documentation/dependency/dept.txt
> create mode 100644 Documentation/dependency/dept_api.txt
What about writing dept docs in reST (like the rest of kernel documentation)?
---- >8 ----
diff --git a/Documentation/dependency/dept.txt b/Documentation/locking/dept.rst
similarity index 92%
rename from Documentation/dependency/dept.txt
rename to Documentation/locking/dept.rst
index 5dd358b96734e6..7b90a0d95f0876 100644
--- a/Documentation/dependency/dept.txt
+++ b/Documentation/locking/dept.rst
@@ -8,7 +8,7 @@ How lockdep works
Lockdep detects a deadlock by checking lock acquisition order. For
example, a graph to track acquisition order built by lockdep might look
-like:
+like::
A -> B -
\
@@ -16,12 +16,12 @@ like:
/
C -> D -
- where 'A -> B' means that acquisition A is prior to acquisition B
- with A still held.
+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 the two locks have
-been acquired in the order, E and then C. The graph will look like:
+been acquired in the order, E and then C. The graph will look like::
A -> B -
\
@@ -32,10 +32,10 @@ been acquired in the order, E and then C. The graph will
look like:
\ /
------------------
- where 'A -> B' means that acquisition A is prior to acquisition B
- with A still held.
+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:
+This graph contains a subgraph that demonstrates a loop like::
-> E -
/ \
@@ -67,6 +67,8 @@ mechanisms, lockdep doesn't work.
Can lockdep detect the following deadlock?
+::
+
context X context Y context Z
mutex_lock A
@@ -80,6 +82,8 @@ Can lockdep detect the following deadlock?
No. What about the following?
+::
+
context X context Y
mutex_lock A
@@ -101,7 +105,7 @@ What leads a deadlock
---------------------
A deadlock occurs when one or multi contexts are waiting for events that
-will never happen. For example:
+will never happen. For example::
context X context Y context Z
@@ -121,24 +125,24 @@ We call this *deadlock*.
If an event occurrence 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.
+ * 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.
+ * 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:
+Dependency graph reflecting this example will look like::
-> C -> A -> B -
/ \
\ /
----------------
- where 'A -> B' means that event A depends on event 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.
@@ -152,7 +156,7 @@ Introduce DEPT
--------------
DEPT(DEPendency Tracker) tracks wait and event instead of lock
-acquisition order so as to recognize the following situation:
+acquisition order so as to recognize the following situation::
context X context Y context Z
@@ -165,18 +169,18 @@ acquisition order so as to recognize the following
situation:
event A
and builds up a dependency graph in runtime that is similar to lockdep.
-The graph might look like:
+The graph might look like::
-> C -> A -> B -
/ \
\ /
----------------
- where 'A -> B' means that event A depends on event 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 event D occurrence is a
-prerequisite to reaching event B like:
+prerequisite to reaching event B like::
|
v
@@ -184,7 +188,7 @@ prerequisite to reaching event B like:
.
event B
-After the addition, the graph will look like:
+After the addition, the graph will look like::
-> D
/
@@ -209,6 +213,8 @@ How DEPT works
Let's take a look how DEPT works with the 1st example in the section
'Limitation of lockdep'.
+::
+
context X context Y context Z
mutex_lock A
@@ -220,7 +226,7 @@ Let's take a look how DEPT works with the 1st example in
the section
mutex_unlock A
mutex_unlock A
-Adding comments to describe DEPT's view in terms of wait and event:
+Adding comments to describe DEPT's view in terms of wait and event::
context X context Y context Z
@@ -248,7 +254,7 @@ Adding comments to describe DEPT's view in terms of wait
and event:
mutex_unlock A
/* event A */
-Adding more supplementary comments to describe DEPT's view in detail:
+Adding more supplementary comments to describe DEPT's view in detail::
context X context Y context Z
@@ -283,7 +289,7 @@ Adding more supplementary comments to describe DEPT's view
in detail:
mutex_unlock A
/* event A that's been valid since 4 */
-Let's build up dependency graph with this example. Firstly, context X:
+Let's build up dependency graph with this example. Firstly, context X::
context X
@@ -292,7 +298,7 @@ Let's build up dependency graph with this example. Firstly,
context X:
/* start to take into account event B's context */
/* 2 */
-There are no events to create dependency. Next, context Y:
+There are no events to create dependency. Next, context Y::
context Y
@@ -317,13 +323,13 @@ waits between 3 and the event, event B does not create
dependency. For
event A, there is a wait, folio_lock B, between 1 and the event. Which
means event A cannot be triggered if event B does not wake up the wait.
Therefore, we can say event A depends on event B, say, 'A -> B'. The
-graph will look like after adding the dependency:
+graph will look like after adding the dependency::
A -> B
- where 'A -> B' means that event A depends on event B.
+where 'A -> B' means that event A depends on event B.
-Lastly, context Z:
+Lastly, context Z::
context Z
@@ -343,7 +349,7 @@ wait, mutex_lock A, between 2 and the event - remind 2 is
at a very
start and before the wait in timeline. Which means event B cannot be
triggered if event A does not wake up the wait. Therefore, we can say
event B depends on event A, say, 'B -> A'. The graph will look like
-after adding the dependency:
+after adding the dependency::
-> A -> B -
/ \
@@ -367,6 +373,8 @@ Interpret DEPT report
The following is the example in the section 'How DEPT works'.
+::
+
context X context Y context Z
mutex_lock A
@@ -402,7 +410,7 @@ The following is the example in the section 'How DEPT
works'.
We can Simplify this by replacing 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 replacement:
+This example will look like after the replacement::
context X context Y context Z
@@ -419,6 +427,8 @@ This example will look like after the replacement:
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.
+::
+
Link:
https://lore.kernel.org/lkml/6383cde5-cf4b-facf-6e07-1378a4856...@i-love.sakura.ne.jp/#t
Link:
https://lore.kernel.org/lkml/1674268856-31807-1-git-send-email-byungchul.p...@lge.com/
@@ -620,6 +630,8 @@ The following is an example reported by DEPT for a real
problem.
Let's take a look at the summary that is the most important part.
+::
+
---------------------------------------------------
summary
---------------------------------------------------
@@ -639,7 +651,7 @@ Let's take a look at the summary that is the most important
part.
[W]: the wait blocked
[E]: the event not reachable
-The summary shows the following scenario:
+The summary shows the following scenario::
context A context B context ?(unknown)
@@ -652,7 +664,7 @@ The summary shows the following scenario:
[E] unlock(&ni->ni_lock:0)
-Adding supplementary comments to describe DEPT's view in detail:
+Adding supplementary comments to describe DEPT's view in detail::
context A context B context ?(unknown)
@@ -677,7 +689,7 @@ Adding supplementary comments to describe DEPT's view in
detail:
[E] unlock(&ni->ni_lock:0)
/* event that's been valid since 2 */
-Let's build up dependency graph with this report. Firstly, context A:
+Let's build up dependency graph with this report. Firstly, context A::
context A
@@ -697,13 +709,13 @@ wait, folio_lock(&f1), between 2 and the event. Which
means
unlock(&ni->ni_lock:0) is not reachable if folio_unlock(&f1) does not
wake up the wait. 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:
+The graph will look like after adding the dependency::
unlock(&ni->ni_lock:0) -> folio_unlock(&f1)
- where 'A -> B' means that event A depends on event B.
+where 'A -> B' means that event A depends on event B.
-Secondly, context B:
+Secondly, context B::
context B
@@ -719,14 +731,14 @@ very start and before the wait in timeline. Which means
folio_unlock(&f1)
is not reachable if unlock(&ni->ni_lock:0) does not wake up the wait.
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:
+like after adding the dependency::
-> unlock(&ni->ni_lock:0) -> folio_unlock(&f1) -
/ \
\ /
------------------------------------------------
- where 'A -> B' means that event A depends on event 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! Cool!
diff --git a/Documentation/dependency/dept_api.txt
b/Documentation/locking/dept_api.rst
similarity index 97%
rename from Documentation/dependency/dept_api.txt
rename to Documentation/locking/dept_api.rst
index 8e0d5a118a460e..96c4d65f4a9a2d 100644
--- a/Documentation/dependency/dept_api.txt
+++ b/Documentation/locking/dept_api.rst
@@ -10,6 +10,8 @@ already applied into 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.
*/
@@ -27,6 +29,8 @@ APIs of SDT are:
The advanced APIs of SDT are:
+.. code-block:: c
+
/*
* After defining 'struct dept_map map', initialize the instance
* using an external key.
@@ -83,6 +87,8 @@ Do not use these APIs directly. These are the wrappers for
typical
locks, that have been already applied into 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);
@@ -96,6 +102,8 @@ 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);
diff --git a/Documentation/locking/index.rst b/Documentation/locking/index.rst
index 6a9ea96c8bcb70..7ec3dce7fee425 100644
--- a/Documentation/locking/index.rst
+++ b/Documentation/locking/index.rst
@@ -24,6 +24,8 @@ Locking
percpu-rw-semaphore
robust-futexes
robust-futex-ABI
+ dept
+ dept_api
.. only:: subproject and html
> +Can lockdep detect the following deadlock?
> +
> + 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?
> +
> + context X context Y
> +
> + mutex_lock A
> + mutex_lock A <- DEADLOCK
> + wait_for_complete B <- DEADLOCK
> + complete B
> + mutex_unlock A
> + mutex_unlock A
Can you explain how DEPT detects deadlock on the second example above (like
the first one being described in "How DEPT works" section)?
Confused...
--
An old man doll... just what I always wanted! - Clara
