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]
Date:   Fri, 13 Jan 2023 10:22:20 -0500
From:   Alan Stern <stern@...land.harvard.edu>
To:     Paul Heidekrüger <paul.heidekrueger@....de>
Cc:     "Paul E. McKenney" <paulmck@...nel.org>,
        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, 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.)

Alan Stern

>                                 found = true;
>                                 break;
>                         }
>                 }
> 
> Many thanks,
> Paul