2022-04-22 20:22:49

by Paul Heidekrüger

[permalink] [raw]
Subject: Broken Address Dependency in mm/ksm.c::cmp_and_merge_page()

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%[email protected]/


2022-04-27 10:28:22

by Paul E. McKenney

[permalink] [raw]
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%[email protected]/
>

2022-06-01 06:11:46

by Paul Heidekrüger

[permalink] [raw]
Subject: Re: Broken Address Dependency in mm/ksm.c::cmp_and_merge_page()

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.

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

Many thanks,
Paul

PS Sorry for the late reply - been distracted ..

>
> Thanx, Paul
>
> > Many thanks,
> > Paul
> >
> > --
> > [1]: https://lore.kernel.org/all/Yk7%[email protected]/
> >

2022-06-01 14:13:32

by Paul E. McKenney

[permalink] [raw]
Subject: Re: Broken Address Dependency in mm/ksm.c::cmp_and_merge_page()

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%[email protected]/
> > >

2023-01-13 11:55:14

by Paul Heidekrüger

[permalink] [raw]
Subject: Re: Broken Address Dependency in mm/ksm.c::cmp_and_merge_page()

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?

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);

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);
found = true;
break;
}
}

Many thanks,
Paul

2023-01-13 16:09:28

by Alan Stern

[permalink] [raw]
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

2023-01-18 12:06:29

by Paul Heidekrüger

[permalink] [raw]
Subject: Re: Broken Address Dependency in mm/ksm.c::cmp_and_merge_page()

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


Attachments:
smime.p7s (4.25 kB)
S/MIME digital signature

2023-01-18 18:39:06

by Paul E. McKenney

[permalink] [raw]
Subject: Re: Broken Address Dependency in mm/ksm.c::cmp_and_merge_page()

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?

Up to the maintainers, but if any of the code that I maintain was relying
on a control dependency, I would want that code commented. But in this
case, lockdep_unregister_key() isn't called very often, correct? If so,
and if this control dependency really is relied on, perhaps some stronger
and less fragile ordering should be used.

But again, maintainers' choice!

Thanx, Paul

2023-01-25 20:41:03

by Boqun Feng

[permalink] [raw]
Subject: Re: Broken Address Dependency in mm/ksm.c::cmp_and_merge_page()

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



2023-02-01 09:05:02

by Paul Heidekrüger

[permalink] [raw]
Subject: Re: Broken Address Dependency in mm/ksm.c::cmp_and_merge_page()

Hi Boqun,

On 25 Jan 2023, at 21:39, Boqun Feng wrote:

> Hi,
>
> [Cc Rust-for-Linux folks]
>
> No hurries but is your tool avaiable somewhere so that we can have a
> try.

Not ready just yet, but very much on it! Hope to be have something to share very
soon :-)

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

Sure!

Paul


Attachments:
smime.p7s (4.25 kB)
S/MIME digital signature