linux-kernel - Re: Broken Address Dependency in mm/ksm.c::cmp_and_merge

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

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <20220426203254.GJ4285@paulmck-ThinkPad-P17-Gen-1>
Date:   Tue, 26 Apr 2022 13:32:54 -0700
From:   "Paul E. McKenney" <paulmck@...nel.org>
To:     Paul Heidekrüger <paul.heidekrueger@...tum.de>
Cc:     Alan Stern <stern@...land.harvard.edu>,
        Andrea Parri <parri.andrea@...il.com>,
        Will Deacon <will@...nel.org>,
        Peter Zijlstra <peterz@...radead.org>,
        Boqun Feng <boqun.feng@...il.com>,
        Nicholas Piggin <npiggin@...il.com>,
        David Howells <dhowells@...hat.com>,
        Jade Alglave <j.alglave@....ac.uk>,
        Luc Maranget <luc.maranget@...ia.fr>,
        Akira Yokosawa <akiyks@...il.com>,
        Daniel Lustig <dlustig@...dia.com>,
        Joel Fernandes <joel@...lfernandes.org>,
        linux-kernel@...r.kernel.org, linux-arch@...r.kernel.org,
        llvm@...ts.linux.dev, Marco Elver <elver@...gle.com>,
        Charalampos Mainas <charalampos.mainas@...il.com>,
        Pramod Bhatotia <pramod.bhatotia@...tum.de>,
        Soham Shakraborty <s.s.chakraborty@...elft.nl>,
        Martin Fink <martin.fink@...tum.de>
Subject: Re: Broken Address Dependency in mm/ksm.c::cmp_and_merge_page()

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