Feedback-ID: iad51458e:Fastmail
Date:   Wed, 25 Jan 2023 12:39:29 -0800
From:   Boqun Feng <boqun.feng@gmail.com>
To:     Paul =?iso-8859-1?Q?Heidekr=FCger?= <paul.heidekrueger@tum.de>
Cc:     Alan Stern <stern@rowland.harvard.edu>,
        "Paul E. McKenney" <paulmck@kernel.org>,
        Andrea Parri <parri.andrea@gmail.com>,
        Will Deacon <will@kernel.org>,
        Peter Zijlstra <peterz@infradead.org>,
        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>,
        Miguel Ojeda <ojeda@kernel.org>,
        Alex Gaynor <alex.gaynor@gmail.com>,
        Wedson Almeida Filho <wedsonaf@gmail.com>,
        Gary Guo <gary@garyguo.net>,
        =?iso-8859-1?Q?Bj=F6rn?= Roy Baron <bjorn3_gh@protonmail.com>
Subject: Re: Broken Address Dependency in mm/ksm.c::cmp_and_merge_page()
Message-ID: <Y9GTgdMnGu6OxUZC@boqun-archlinux>
References: <YmKE/XgmRnGKrBbB@Pauls-MacBook-Pro.local>
 <20220426203254.GJ4285@paulmck-ThinkPad-P17-Gen-1>
 <YpYAQLi296UFEdTH@ethstick13.dse.in.tum.de>
 <20220531150312.GH1790663@paulmck-ThinkPad-P17-Gen-1>
 <0EC00B0E-554A-4BF3-B012-ED1E36B12FD1@tum.de>
 <Y8F3LMlTnT5ZtVTq@rowland.harvard.edu>
 <9E7A62DD-D5DC-4B9C-A592-1A626482563B@tum.de>
MIME-Version: 1.0
Content-Type: text/plain; charset=iso-8859-1
Content-Disposition: inline
Content-Transfer-Encoding: 8bit
In-Reply-To: <9E7A62DD-D5DC-4B9C-A592-1A626482563B@tum.de>
Precedence: bulk

Hi,

[Cc Rust-for-Linux folks]

No hurries but is your tool avaiable somewhere so that we can have a
try.

Although Rust doesn't support dependencies ordering, but it's good to
know which dependency is reserved after optimization. 

Regards,
Boqun

On Wed, Jan 18, 2023 at 11:42:23AM +0100, Paul Heidekr?ger wrote:
> On 13 Jan 2023, at 16:22, Alan Stern wrote:
> 
> > On Fri, Jan 13, 2023 at 12:11:25PM +0100, Paul Heidekr?ger wrote:
> >> Hi all,
> >>
> >> FWIW, here are two more broken address dependencies, both very similar to the
> >> one discussed in this thread. From what I can tell, both are protected by a
> >> lock, so, again, nothing to worry about right now? Would you agree?
> >
> > FWIW, my opinion is that in both cases the broken dependency can be
> > removed entirely.
> >
> >> Comments marked with "AD:" were added by me for readability.
> >>
> >> 1. drivers/hwtracing/stm/core.c::1050 - 1085
> >>
> >>         /**
> >>          * __stm_source_link_drop() - detach stm_source from an stm device
> >>          * @src:	stm_source device
> >>          * @stm:	stm device
> >>          *
> >>          * If @stm is @src::link, disconnect them from one another and put the
> >>          * reference on the @stm device.
> >>          *
> >>          * Caller must hold stm::link_mutex.
> >>          */
> >>         static int __stm_source_link_drop(struct stm_source_device *src,
> >>                                           struct stm_device *stm)
> >>         {
> >>                 struct stm_device *link;
> >>                 int ret = 0;
> >>
> >>                 lockdep_assert_held(&stm->link_mutex);
> >>
> >>                 /* for stm::link_list modification, we hold both mutex and spinlock */
> >>                 spin_lock(&stm->link_lock);
> >>                 spin_lock(&src->link_lock);
> >>
> >>                 /* AD: Beginning of the address dependency. */
> >>                 link = srcu_dereference_check(src->link, &stm_source_srcu, 1);
> >>
> >>                 /*
> >>                  * The linked device may have changed since we last looked, because
> >>                  * we weren't holding the src::link_lock back then; if this is the
> >>                  * case, tell the caller to retry.
> >>                  */
> >>                 if (link != stm) {
> >>                         ret = -EAGAIN;
> >>                         goto unlock;
> >>                 }
> >>
> >>                 /* AD: Compiler deduces that "link" and "stm" are exchangeable at this point. */
> >>                 stm_output_free(link, &src->output); list_del_init(&src->link_entry);
> >>
> >>                 /* AD: Leads to WRITE_ONCE() to (&link->dev)->power.last_busy. */
> >>                 pm_runtime_mark_last_busy(&link->dev);
> >
> > In both of these statements, link can safely be replaced by stm.
> >
> > (There's also a control dependency which the LKMM isn't aware of.  This
> > makes it all the more safe.)
> >
> >> 2. kernel/locking/lockdep.c::6319 - 6348
> >>
> >>         /*
> >>          * Unregister a dynamically allocated key.
> >>          *
> >>          * Unlike lockdep_register_key(), a search is always done to find a matching
> >>          * key irrespective of debug_locks to avoid potential invalid access to freed
> >>          * memory in lock_class entry.
> >>          */
> >>         void lockdep_unregister_key(struct lock_class_key *key)
> >>         {
> >>                 struct hlist_head *hash_head = keyhashentry(key);
> >>                 struct lock_class_key *k;
> >>                 struct pending_free *pf;
> >>                 unsigned long flags;
> >>                 bool found = false;
> >>
> >>                 might_sleep();
> >>
> >>                 if (WARN_ON_ONCE(static_obj(key)))
> >>                         return;
> >>
> >>                 raw_local_irq_save(flags);
> >>                 lockdep_lock();
> >>
> >>                 /* AD: Address dependency begins here with an rcu_dereference_raw() into k. */
> >>                 hlist_for_each_entry_rcu(k, hash_head, hash_entry) {
> >>                         /* AD: Compiler deduces that k and key are exchangable iff the if condition evaluates to true.
> >>                         if (k == key) {
> >>                                 /* AD: Leads to WRITE_ONCE() to (&k->hash_entry)->pprev. */
> >>                                 hlist_del_rcu(&k->hash_entry);
> >
> > And here k could safely be replaced with key.  (And again there is a
> > control dependency, but this is one that the LKMM would detect.)
> 
> Ha, I didn't even notice the control dependencies - of course! In that case,
> this doesn't warrant a patch though, given that nothing is really breaking?
> 
> Many thanks,
> Paul