Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20;
Date:   Tue, 31 May 2022 08:03:12 -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: <20220531150312.GH1790663@paulmck-ThinkPad-P17-Gen-1>
Reply-To: paulmck@kernel.org
References: <YmKE/XgmRnGKrBbB@Pauls-MacBook-Pro.local>
 <20220426203254.GJ4285@paulmck-ThinkPad-P17-Gen-1>
 <YpYAQLi296UFEdTH@ethstick13.dse.in.tum.de>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Disposition: inline
Content-Transfer-Encoding: 8bit
In-Reply-To: <YpYAQLi296UFEdTH@ethstick13.dse.in.tum.de>
Precedence: bulk

On Tue, May 31, 2022 at 01:47:12PM +0200, Paul Heidekrüger wrote:
> On Tue, Apr 26, 2022 at 01:32:54PM -0700, Paul E. McKenney wrote:
> > 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?
> 
> Nope, missing nothing, that was exactly it!
> 
> In ksm_scan_thread(), which calls ksm_do_scan(), which calls
> cmp_and_merge_page(), there is a mutex_lock() / mutex_unlock() pair,
> surrounding the dependency. 

Whew!!!  ;-)

> Still keeping this as a trophy for our dependency checker though ;-)

As well you should!

							Thanx, Paul

> Many thanks,
> Paul
> 
> PS Sorry for the late reply - been distracted ..
> 
> > 
> > 							Thanx, Paul
> > 
> > > Many thanks,
> > > Paul
> > > 
> > > --
> > > [1]: https://lore.kernel.org/all/Yk7%2FT8BJITwz+Og1@Pauls-MacBook-Pro.local/
> > >