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%2FT8BJITwz+Og1@Pauls-MacBook-Pro.local/
> >
