Message-ID: <20251215042237.GA49936@system.software.com>
Date: Mon, 15 Dec 2025 13:22:37 +0900
From: Byungchul Park <byungchul@...com>
To: Bagas Sanjaya <bagasdotme@...il.com>
Cc: linux-kernel@...r.kernel.org, kernel_team@...ynix.com,
	torvalds@...ux-foundation.org, damien.lemoal@...nsource.wdc.com,
	linux-ide@...r.kernel.org, adilger.kernel@...ger.ca,
	linux-ext4@...r.kernel.org, mingo@...hat.com, peterz@...radead.org,
	will@...nel.org, tglx@...utronix.de, rostedt@...dmis.org,
	joel@...lfernandes.org, sashal@...nel.org, daniel.vetter@...ll.ch,
	duyuyang@...il.com, johannes.berg@...el.com, tj@...nel.org,
	tytso@....edu, willy@...radead.org, david@...morbit.com,
	amir73il@...il.com, gregkh@...uxfoundation.org, kernel-team@....com,
	linux-mm@...ck.org, akpm@...ux-foundation.org, mhocko@...nel.org,
	minchan@...nel.org, hannes@...xchg.org, vdavydov.dev@...il.com,
	sj@...nel.org, jglisse@...hat.com, dennis@...nel.org, cl@...ux.com,
	penberg@...nel.org, rientjes@...gle.com, vbabka@...e.cz,
	ngupta@...are.org, linux-block@...r.kernel.org,
	josef@...icpanda.com, linux-fsdevel@...r.kernel.org, jack@...e.cz,
	jlayton@...nel.org, dan.j.williams@...el.com, hch@...radead.org,
	djwong@...nel.org, dri-devel@...ts.freedesktop.org,
	rodrigosiqueiramelo@...il.com, melissa.srw@...il.com,
	hamohammed.sa@...il.com, harry.yoo@...cle.com,
	chris.p.wilson@...el.com, gwan-gyeong.mun@...el.com,
	max.byungchul.park@...il.com, boqun.feng@...il.com,
	longman@...hat.com, yunseong.kim@...csson.com, ysk@...lloc.com,
	yeoreum.yun@....com, netdev@...r.kernel.org,
	matthew.brost@...el.com, her0gyugyu@...il.com, corbet@....net,
	catalin.marinas@....com, bp@...en8.de, x86@...nel.org,
	hpa@...or.com, luto@...nel.org, sumit.semwal@...aro.org,
	gustavo@...ovan.org, christian.koenig@....com,
	andi.shyti@...nel.org, arnd@...db.de, lorenzo.stoakes@...cle.com,
	Liam.Howlett@...cle.com, rppt@...nel.org, surenb@...gle.com,
	mcgrof@...nel.org, petr.pavlu@...e.com, da.gomez@...nel.org,
	samitolvanen@...gle.com, paulmck@...nel.org, frederic@...nel.org,
	neeraj.upadhyay@...nel.org, joelagnelf@...dia.com,
	josh@...htriplett.org, urezki@...il.com,
	mathieu.desnoyers@...icios.com, jiangshanlai@...il.com,
	qiang.zhang@...ux.dev, juri.lelli@...hat.com,
	vincent.guittot@...aro.org, dietmar.eggemann@....com,
	bsegall@...gle.com, mgorman@...e.de, vschneid@...hat.com,
	chuck.lever@...cle.com, neil@...wn.name, okorniev@...hat.com,
	Dai.Ngo@...cle.com, tom@...pey.com, trondmy@...nel.org,
	anna@...nel.org, kees@...nel.org, bigeasy@...utronix.de,
	clrkwllms@...nel.org, mark.rutland@....com, ada.coupriediaz@....com,
	kristina.martsenko@....com, wangkefeng.wang@...wei.com,
	broonie@...nel.org, kevin.brodsky@....com, dwmw@...zon.co.uk,
	shakeel.butt@...ux.dev, ast@...nel.org, ziy@...dia.com,
	yuzhao@...gle.com, baolin.wang@...ux.alibaba.com,
	usamaarif642@...il.com, joel.granados@...nel.org,
	richard.weiyang@...il.com, geert+renesas@...der.be,
	tim.c.chen@...ux.intel.com, linux@...blig.org,
	alexander.shishkin@...ux.intel.com, lillian@...r-ark.net,
	chenhuacai@...nel.org, francesco@...la.it,
	guoweikang.kernel@...il.com, link@...o.com, jpoimboe@...nel.org,
	masahiroy@...nel.org, brauner@...nel.org,
	thomas.weissschuh@...utronix.de, oleg@...hat.com, mjguzik@...il.com,
	andrii@...nel.org, wangfushuai@...du.com, linux-doc@...r.kernel.org,
	linux-arm-kernel@...ts.infradead.org, linux-media@...r.kernel.org,
	linaro-mm-sig@...ts.linaro.org, linux-i2c@...r.kernel.org,
	linux-arch@...r.kernel.org, linux-modules@...r.kernel.org,
	rcu@...r.kernel.org, linux-nfs@...r.kernel.org,
	linux-rt-devel@...ts.linux.dev, 2407018371@...com, dakr@...nel.org,
	miguel.ojeda.sandonis@...il.com, neilb@...mail.net,
	wsa+renesas@...g-engineering.com, dave.hansen@...el.com,
	geert@...ux-m68k.org, ojeda@...nel.org, alex.gaynor@...il.com,
	gary@...yguo.net, bjorn3_gh@...tonmail.com, lossin@...nel.org,
	a.hindborg@...nel.org, aliceryhl@...gle.com, tmgross@...ch.edu,
	rust-for-linux@...r.kernel.org
Subject: Re: [PATCH v18 25/42] dept: add documents for dept

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

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

Thanks.

	Byungchul

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

Powered by blists - more mailing lists