[Linaro-mm-sig] Re: [PATCH v17 28/47] dept: add documentation for dept

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 byungchul@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-1378a485657d@I-love.SAK... Link: https://lore.kernel.org/lkml/1674268856-31807-1-git-send-email-byungchul.par...

@@ -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...