mirror of https://lore.kernel.org/lkml/
 help / color / mirror / Atom feed
From: "Paul E. McKenney" <paulmck@kernel.org>
To: "Paul Heidekrüger" <paul.heidekrueger@in.tum.de>
Cc: Alan Stern <stern@rowland.harvard.edu>,
	Andrea Parri <parri.andrea@gmail.com>,
	Will Deacon <will@kernel.org>,
	Peter Zijlstra <peterz@infradead.org>,
	Boqun Feng <boqun.feng@gmail.com>,
	Nicholas Piggin <npiggin@gmail.com>,
	David Howells <dhowells@redhat.com>,
	Jade Alglave <j.alglave@ucl.ac.uk>,
	Luc Maranget <luc.maranget@inria.fr>,
	Akira Yokosawa <akiyks@gmail.com>,
	Daniel Lustig <dlustig@nvidia.com>,
	Joel Fernandes <joel@joelfernandes.org>,
	linux-kernel@vger.kernel.org, linux-arch@vger.kernel.org,
	llvm@lists.linux.dev, Marco Elver <elver@google.com>,
	Charalampos Mainas <charalampos.mainas@gmail.com>,
	Pramod Bhatotia <pramod.bhatotia@in.tum.de>,
	Soham Shakraborty <s.s.chakraborty@tudelft.nl>,
	Martin Fink <martin.fink@in.tum.de>
Subject: Re: Broken Address Dependency in mm/ksm.c::cmp_and_merge_page()
Date: Tue, 26 Apr 2022 13:32:54 -0700	[thread overview]
Message-ID: <20220426203254.GJ4285@paulmck-ThinkPad-P17-Gen-1> (raw)
In-Reply-To: <YmKE/XgmRnGKrBbB@Pauls-MacBook-Pro.local>

On Fri, Apr 22, 2022 at 12:35:41PM +0200, Paul Heidekrüger wrote:
> Hi all, 
> 
> My dependency checker is flagging yet another broken dependency. For
> context, see [1].
> 
> Thankfully, it is fairly straight-forward to explain this time.
> 
> > stable_node = page_stable_node(page);
> 
> Line 2032 in mm/ksm.c::cmp_and_merge_page() sees the return value of a
> call to "page_stable_node()", which can depend on a "READ_ONCE()", being
> assigned to "stable_node".
> 
> > if (stable_node) {
> >         if (stable_node->head != &migrate_nodes &&
> >             get_kpfn_nid(READ_ONCE(stable_node->kpfn)) != 
> >             NUMA(stable_node->nid)) {
> >                 stable_node_dup_del(stable_node); ‣dup: stable_node
> >                 stable_node->head = &migrate_nodes;
> >                 list_add(&stable_node->list, stable_node->head);
> 
> The dependency chain then runs into the two following if's, through an
> assignment of "migrate_nodes" to "stable_node->head" (line 2038) and
> finally reaches a call to "list_add()" (line 2039) where
> "stable_node->head" gets passed as the second function argument. 

Huh.

But migrate_nodes is nothing more or less than a list_head structure.
So one would expect that some other mechanism is protecting its ->prev
and ->next pointers.

> >         }
> > }
> > 
> > static inline void list_add(struct list_head *new, struct list_head *head)
> > {
> >         __list_add(new, head, head->next);
> > }
> > 
> > static inline void __list_add(struct list_head *new,
> >                               struct list_head *prev,
> >                               struct list_head *next)
> > {
> >         if (!__list_add_valid(new, prev, next))
> >                 return;
> > 
> >         next->prev = new;
> >         new->next = next;
> >         new->prev = prev;
> >         WRITE_ONCE(prev->next, new);
> > }
> 
> By being passed into "list_add()" via "stable_node->head", the
> dependency chain eventually reaches a "WRITE_ONCE()" in "__list_add()"
> whose destination address, "stable_node->head->next", is part of the
> dependency chain and therefore carries an address dependency. 
> 
> However, as a result of the assignment in line 2038, Clang knows that
> "stable_node->head" is "migrate_nodes" and replaces it, thereby breaking
> the dependency chain. 
> 
> What do you think?

Given that this is a non-atomic update, there had better be something
protecting it.  This something might be a lock, a decremented-to-zero
reference count, a rule about only one kthread being permitted to update
that list, and so on.  In all such cases, the code would not be relying
on the dependency, but rather on whatever was protecting that operation.

Or am I missing something here?

							Thanx, Paul

> Many thanks,
> Paul
> 
> --
> [1]: https://lore.kernel.org/all/Yk7%2FT8BJITwz+Og1@Pauls-MacBook-Pro.local/
> 

  reply	other threads:[~2022-04-26 20:33 UTC|newest]

Thread overview: 10+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2022-04-22 10:35 Paul Heidekrüger
2022-04-26 20:32 ` Paul E. McKenney [this message]
2022-05-31 11:47   ` Paul Heidekrüger
2022-05-31 15:03     ` Paul E. McKenney
2023-01-13 11:11       ` Paul Heidekrüger
2023-01-13 15:22         ` Alan Stern
2023-01-18 10:42           ` Paul Heidekrüger
2023-01-18 18:09             ` Paul E. McKenney
2023-01-25 20:39             ` Boqun Feng
2023-02-01  9:04               ` Paul Heidekrüger

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20220426203254.GJ4285@paulmck-ThinkPad-P17-Gen-1 \
    --to=paulmck@kernel.org \
    --cc=akiyks@gmail.com \
    --cc=boqun.feng@gmail.com \
    --cc=charalampos.mainas@gmail.com \
    --cc=dhowells@redhat.com \
    --cc=dlustig@nvidia.com \
    --cc=elver@google.com \
    --cc=j.alglave@ucl.ac.uk \
    --cc=joel@joelfernandes.org \
    --cc=linux-arch@vger.kernel.org \
    --cc=linux-kernel@vger.kernel.org \
    --cc=llvm@lists.linux.dev \
    --cc=luc.maranget@inria.fr \
    --cc=martin.fink@in.tum.de \
    --cc=npiggin@gmail.com \
    --cc=parri.andrea@gmail.com \
    --cc=paul.heidekrueger@in.tum.de \
    --cc=peterz@infradead.org \
    --cc=pramod.bhatotia@in.tum.de \
    --cc=s.s.chakraborty@tudelft.nl \
    --cc=stern@rowland.harvard.edu \
    --cc=will@kernel.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox

all inboxes | Powered by JetHome®