| lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
|
Open Source and information security mailing list archives
| ||
|
Message-ID: <aTN38kJjBftxnjm9@archie.me>
Date: Sat, 6 Dec 2025 07:25:22 +0700
From: Bagas Sanjaya <bagasdotme@...il.com>
To: Byungchul Park <byungchul@...com>, linux-kernel@...r.kernel.org
Cc: 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 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:
---- >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:
---- >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)?
Thanks.
[1]: https://lore.kernel.org/linux-doc/aN84jKyrE1BumpLj@archie.me/
--
An old man doll... just what I always wanted! - Clara
Download attachment "signature.asc" of type "application/pgp-signature" (229 bytes)
Powered by blists - more mailing lists