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

[Bagas Sanjaya <bagasdotme@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 11104 bytes --]

On Mon, Dec 15, 2025 at 01:22:37PM +0900, Byungchul Park wrote:
> 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@sk.com>
> > > ---
> > >  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@I-love.SAKURA.ne.jp/#t
> >     Link: https://lore.kernel.org/lkml/1674268856-31807-1-git-send-email-byungchul.park@lge.com/
> > @@ -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].

Of course!

-- 
An old man doll... just what I always wanted! - Clara

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 228 bytes --]