Re: [PATCH v18 25/42] dept: add documents for dept

[Byungchul Park]

On Sat, Dec 06, 2025 at 07:25:22AM +0700, Bagas Sanjaya wrote:
> On Fri, Dec 05, 2025 at 04:18:38PM +0900, Byungchul Park wrote:
> > Add documents describing the concept and APIs of dept.
> > 
> > Signed-off-by: Byungchul Park <byungchul@xxxxxx>
> > ---
> >  Documentation/dev-tools/dept.rst     | 778 +++++++++++++++++++++++++++
> >  Documentation/dev-tools/dept_api.rst | 125 +++++
> 
> You forget to add toctree entries:

I'm sorry for late reply.

Thanks a lot!

> ---- >8 ----
> diff --git a/Documentation/dev-tools/index.rst b/Documentation/dev-tools/index.rst
> index 4b8425e348abd1..02c858f5ed1fa2 100644
> --- a/Documentation/dev-tools/index.rst
> +++ b/Documentation/dev-tools/index.rst
> @@ -22,6 +22,8 @@ Documentation/process/debugging/index.rst
>     clang-format
>     coccinelle
>     sparse
> +   dept
> +   dept_api
>     kcov
>     gcov
>     kasan
> 
> > +Lockdep detects a deadlock by checking lock acquisition order.  For
> > +example, a graph to track acquisition order built by lockdep might look
> > +like:
> > +
> > +.. literal::
> > +
> > +   A -> B -
> > +           \
> > +            -> E
> > +           /
> > +   C -> D -
> > +
> > +   where 'A -> B' means that acquisition A is prior to acquisition B
> > +   with A still held.
> 
> Use code-block directive for literal code blocks:

I will.

> ---- >8 ----
> diff --git a/Documentation/dev-tools/dept.rst b/Documentation/dev-tools/dept.rst
> index 333166464543d7..8394c4ea81bc2a 100644
> --- a/Documentation/dev-tools/dept.rst
> +++ b/Documentation/dev-tools/dept.rst
> @@ -10,7 +10,7 @@ Lockdep detects a deadlock by checking lock acquisition order.  For
>  example, a graph to track acquisition order built by lockdep might look
>  like:
>  
> -.. literal::
> +.. code-block::
>  
>     A -> B -
>             \
> @@ -25,7 +25,7 @@ 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:
>  
> -.. literal::
> +.. code-block::
>  
>         A -> B -
>                 \
> @@ -41,7 +41,7 @@ been acquired in the order, E and then C.  The graph will look like:
>  
>  This graph contains a subgraph that demonstrates a loop like:
>  
> -.. literal::
> +.. code-block::
>  
>                  -> E -
>                 /      \
> @@ -76,7 +76,7 @@ e.g. irq context, normal process context, wq worker context, or so on.
>  
>  Can lockdep detect the following deadlock?
>  
> -.. literal::
> +.. code-block::
>  
>     context X	   context Y	   context Z
>  
> @@ -91,7 +91,7 @@ Can lockdep detect the following deadlock?
>  
>  No.  What about the following?
>  
> -.. literal::
> +.. code-block::
>  
>     context X		   context Y
>  
> @@ -116,7 +116,7 @@ What leads a deadlock
>  A deadlock occurs when one or multi contexts are waiting for events that
>  will never happen.  For example:
>  
> -.. literal::
> +.. code-block::
>  
>     context X	   context Y	   context Z
>  
> @@ -148,7 +148,7 @@ In terms of dependency:
>  
>  Dependency graph reflecting this example will look like:
>  
> -.. literal::
> +.. code-block::
>  
>      -> C -> A -> B -
>     /                \
> @@ -171,7 +171,7 @@ Introduce DEPT
>  DEPT(DEPendency Tracker) tracks wait and event instead of lock
>  acquisition order so as to recognize the following situation:
>  
> -.. literal::
> +.. code-block::
>  
>     context X	   context Y	   context Z
>  
> @@ -186,7 +186,7 @@ acquisition order so as to recognize the following situation:
>  and builds up a dependency graph at runtime that is similar to lockdep.
>  The graph might look like:
>  
> -.. literal::
> +.. code-block::
>  
>      -> C -> A -> B -
>     /                \
> @@ -199,7 +199,7 @@ 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:
>  
> -.. literal::
> +.. code-block::
>  
>     context W
>  
> @@ -211,7 +211,7 @@ prerequisite to reaching event B like:
>  
>  After the addition, the graph will look like:
>  
> -.. literal::
> +.. code-block::
>  
>                       -> D
>                      /
> @@ -236,7 +236,7 @@ How DEPT works
>  Let's take a look how DEPT works with the 1st example in the section
>  'Limitation of lockdep'.
>  
> -.. literal::
> +.. code-block::
>  
>     context X	   context Y	   context Z
>  
> @@ -256,7 +256,7 @@ event.
>  
>  Adding comments to describe DEPT's view in detail:
>  
> -.. literal::
> +.. code-block::
>  
>     context X	   context Y	   context Z
>  
> @@ -293,7 +293,7 @@ Adding comments to describe DEPT's view in detail:
>  
>  Let's build up dependency graph with this example.  Firstly, context X:
>  
> -.. literal::
> +.. code-block::
>  
>     context X
>  
> @@ -304,7 +304,7 @@ Let's build up dependency graph with this example.  Firstly, context X:
>  
>  There are no events to create dependency.  Next, context Y:
>  
> -.. literal::
> +.. code-block::
>  
>     context Y
>  
> @@ -332,7 +332,7 @@ 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:
>  
> -.. literal::
> +.. code-block::
>  
>     A -> B
>  
> @@ -340,7 +340,7 @@ graph will look like after adding the dependency:
>  
>  Lastly, context Z:
>  
> -.. literal::
> +.. code-block::
>  
>     context Z
>  
> @@ -362,7 +362,7 @@ 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:
>  
> -.. literal::
> +.. code-block::
>  
>      -> A -> B -
>     /           \
> @@ -386,7 +386,7 @@ Interpret DEPT report
>  
>  The following is the same example in the section 'How DEPT works'.
>  
> -.. literal::
> +.. code-block::
>  
>     context X	   context Y	   context Z
>  
> @@ -425,7 +425,7 @@ 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:
>  
> -.. literal::
> +.. code-block::
>  
>     context X	   context Y	   context Z
>  
> @@ -443,7 +443,7 @@ 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.
>  
> -.. literal::
> +.. code-block::
>  
>     Link: https://lore.kernel.org/lkml/6383cde5-cf4b-facf-6e07-1378a485657d@xxxxxxxxxxxxxxxxxxx/#t
>     Link: https://lore.kernel.org/lkml/1674268856-31807-1-git-send-email-byungchul.park@xxxxxxx/
> @@ -646,7 +646,7 @@ practice.
>  
>  Let's take a look at the summary that is the most important part.
>  
> -.. literal::
> +.. code-block::
>  
>     ---------------------------------------------------
>     summary
> @@ -669,7 +669,7 @@ Let's take a look at the summary that is the most important part.
>  
>  The summary shows the following scenario:
>  
> -.. literal::
> +.. code-block::
>  
>     context A	   context B	   context ?(unknown)
>  
> @@ -684,7 +684,7 @@ The summary shows the following scenario:
>  
>  Adding comments to describe DEPT's view in detail:
>  
> -.. literal::
> +.. code-block::
>  
>     context A	   context B	   context ?(unknown)
>  
> @@ -711,7 +711,7 @@ Adding comments to describe DEPT's view in detail:
>  
>  Let's build up dependency graph with this report. Firstly, context A:
>  
> -.. literal::
> +.. code-block::
>  
>     context A
>  
> @@ -735,7 +735,7 @@ unlock(&ni->ni_lock:0) depends on folio_unlock(&f1), say,
>  
>  The graph will look like after adding the dependency:
>  
> -.. literal::
> +.. code-block::
>  
>     unlock(&ni->ni_lock:0) -> folio_unlock(&f1)
>  
> @@ -743,7 +743,7 @@ The graph will look like after adding the dependency:
>  
>  Secondly, context B:
>  
> -.. literal::
> +.. code-block::
>  
>     context B
>  
> @@ -762,7 +762,7 @@ folio_unlock(&f1) depends on unlock(&ni->ni_lock:0), say,
>  
>  The graph will look like after adding the dependency:
>  
> -.. literal::
> +.. code-block::
>  
>      -> unlock(&ni->ni_lock:0) -> folio_unlock(&f1) -
>     /                                                \
> 
> > +Limitation of lockdep
> > +---------------------
> > +
> > +Lockdep deals with a deadlock by typical lock e.g. spinlock and mutex,
> > +that are supposed to be released within the acquisition context.
> > +However, when it comes to a deadlock by 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, or so on.
> > +
> > +Can lockdep detect the following deadlock?
> > +
> > +.. literal::
> > +
> > +   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?
> > +
> > +.. literal::
> > +
> > +   context X		   context Y
> > +
> > +			   mutex_lock A
> > +   mutex_lock A <- DEADLOCK
> > +			   wait_for_complete B <- DEADLOCK
> > +   complete B
> > +			   mutex_unlock A
> > +   mutex_unlock A
> > +
> > +No.
> 
> One unanswered question from my v17 review [1]: You explain in "How DEPT works"
> section how DEPT detects deadlock in the first example (the former with three
> contexts). Can you do the same on the second example (the latter with two
> contexts)?

Did you mean to update the document with it?  I misunderstood what you
meant but sure I will update it as [1].

[1] https://lore.kernel.org/linux-doc/20251013012855.GB52546@xxxxxxxxxxxxxxxxxxx/

Thanks.

	Byungchul

> Thanks.
> 
> [1]: https://lore.kernel.org/linux-doc/aN84jKyrE1BumpLj@xxxxxxxxx/
> 
> -- 
> An old man doll... just what I always wanted! - Clara