| 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: <aT_PlFHyQB6HyZXG@archie.me>
Date: Mon, 15 Dec 2025 16:06:28 +0700
From: Bagas Sanjaya <bagasdotme@...il.com>
To: Byungchul Park <byungchul@...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 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@...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
Download attachment "signature.asc" of type "application/pgp-signature" (229 bytes)
Powered by blists - more mailing lists