Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:18 as permitted sender) client-ip=2620:137:e000::1:18;
Date:   Tue, 26 Apr 2022 13:32:54 -0700
From:   "Paul E. McKenney" <paulmck@kernel.org>
To:     Paul =?iso-8859-1?Q?Heidekr=FCger?= <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()
Message-ID: <20220426203254.GJ4285@paulmck-ThinkPad-P17-Gen-1>
Reply-To: paulmck@kernel.org
References: <YmKE/XgmRnGKrBbB@Pauls-MacBook-Pro.local>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Disposition: inline
Content-Transfer-Encoding: 8bit
In-Reply-To: <YmKE/XgmRnGKrBbB@Pauls-MacBook-Pro.local>
Precedence: bulk

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/
>