Received-SPF: softfail (google.com: domain of transitioning linux-kernel-owner@vger.kernel.org does not designate 23.128.96.19 as permitted sender) client-ip=23.128.96.19;
Date:   Fri, 22 Apr 2022 12:35:41 +0200
From:   Paul =?iso-8859-1?Q?Heidekr=FCger?= <paul.heidekrueger@in.tum.de>
To:     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>,
        "Paul E. McKenney" <paulmck@kernel.org>,
        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
Cc:     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: Broken Address Dependency in mm/ksm.c::cmp_and_merge_page()
Message-ID: <YmKE/XgmRnGKrBbB@Pauls-MacBook-Pro.local>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Disposition: inline
Content-Transfer-Encoding: 8bit
Precedence: bulk

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. 

>         }
> }
> 
> 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?

Many thanks,
Paul

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