[PATCH] driver core: Extend device_is_dependent()

[PATCH] driver core: Extend device_is_dependent()

[Rafael J. Wysocki]

From: Rafael J. Wysocki <rafael.j.wysocki@intel.com>

When adding a new device link, device_is_dependent() is used to
check whether or not the prospective supplier device does not
depend on the prospective consumer one to avoid adding loops
to the graph of device dependencies.

However, device_is_dependent() does not take the ancestors of
the target device into account, so it may not detect an existing
reverse dependency if, for example, the parent of the target
device depends on the device passed as its first argument.

For this reason, extend device_is_dependent() to also check if
the device passed as its first argument is an ancestor of the
target one and return 1 if that is the case.

Signed-off-by: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
Reported-by: Stephan Gerhold <stephan@gerhold.net> 
---
 drivers/base/core.c |   12 +++++++++++-
 1 file changed, 11 insertions(+), 1 deletion(-)

Index: linux-pm/drivers/base/core.c
===================================================================
--- linux-pm.orig/drivers/base/core.c
+++ linux-pm/drivers/base/core.c
@@ -208,6 +208,16 @@ int device_links_read_lock_held(void)
 #endif
 #endif /* !CONFIG_SRCU */
 
+static bool device_is_ancestor(struct device *dev, struct device *target)
+{
+	while (target->parent) {
+		target = target->parent;
+		if (dev == target)
+			return true;
+	}
+	return false;
+}
+
 /**
  * device_is_dependent - Check if one device depends on another one
  * @dev: Device to check dependencies for.
@@ -221,7 +231,7 @@ int device_is_dependent(struct device *d
 	struct device_link *link;
 	int ret;
 
-	if (dev == target)
+	if (dev == target || device_is_ancestor(dev, target))
 		return 1;
 
 	ret = device_for_each_child(dev, target, device_is_dependent);

Re: [PATCH] driver core: Extend device_is_dependent()

[Saravana Kannan]

On Thu, Jan 14, 2021 at 10:41 AM Rafael J. Wysocki <rjw@rjwysocki.net> wrote:
>
> From: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
>
> When adding a new device link, device_is_dependent() is used to
> check whether or not the prospective supplier device does not
> depend on the prospective consumer one to avoid adding loops
> to the graph of device dependencies.
>
> However, device_is_dependent() does not take the ancestors of
> the target device into account, so it may not detect an existing
> reverse dependency if, for example, the parent of the target
> device depends on the device passed as its first argument.
>
> For this reason, extend device_is_dependent() to also check if
> the device passed as its first argument is an ancestor of the
> target one and return 1 if that is the case.
>
> Signed-off-by: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
> Reported-by: Stephan Gerhold <stephan@gerhold.net>
> ---
>  drivers/base/core.c |   12 +++++++++++-
>  1 file changed, 11 insertions(+), 1 deletion(-)
>
> Index: linux-pm/drivers/base/core.c
> ===================================================================
> --- linux-pm.orig/drivers/base/core.c
> +++ linux-pm/drivers/base/core.c
> @@ -208,6 +208,16 @@ int device_links_read_lock_held(void)
>  #endif
>  #endif /* !CONFIG_SRCU */
>
> +static bool device_is_ancestor(struct device *dev, struct device *target)
> +{
> +       while (target->parent) {
> +               target = target->parent;
> +               if (dev == target)
> +                       return true;
> +       }
> +       return false;
> +}
> +
>  /**
>   * device_is_dependent - Check if one device depends on another one
>   * @dev: Device to check dependencies for.
> @@ -221,7 +231,7 @@ int device_is_dependent(struct device *d
>         struct device_link *link;
>         int ret;
>
> -       if (dev == target)
> +       if (dev == target || device_is_ancestor(dev, target))
>                 return 1;
>
>         ret = device_for_each_child(dev, target, device_is_dependent);
>

The code works, but it's not at all obvious what it's doing. Because,
at first glance, it's easy to mistakenly think that it's trying to
catch this case:
dev <- child1 <- child2 <- target

Maybe it's clearer if we do this check inside the loop? Something like:

                if (link->consumer == target ||
device_is_ancestor(link->consumer, target))
                        return 1;

-Saravana

Re: [PATCH] driver core: Extend device_is_dependent()

[Rafael J. Wysocki]

On Thu, Jan 14, 2021 at 8:32 PM Saravana Kannan <saravanak@google.com> wrote:
>
> On Thu, Jan 14, 2021 at 10:41 AM Rafael J. Wysocki <rjw@rjwysocki.net> wrote:
> >
> > From: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
> >
> > When adding a new device link, device_is_dependent() is used to
> > check whether or not the prospective supplier device does not
> > depend on the prospective consumer one to avoid adding loops
> > to the graph of device dependencies.
> >
> > However, device_is_dependent() does not take the ancestors of
> > the target device into account, so it may not detect an existing
> > reverse dependency if, for example, the parent of the target
> > device depends on the device passed as its first argument.
> >
> > For this reason, extend device_is_dependent() to also check if
> > the device passed as its first argument is an ancestor of the
> > target one and return 1 if that is the case.
> >
> > Signed-off-by: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
> > Reported-by: Stephan Gerhold <stephan@gerhold.net>
> > ---
> >  drivers/base/core.c |   12 +++++++++++-
> >  1 file changed, 11 insertions(+), 1 deletion(-)
> >
> > Index: linux-pm/drivers/base/core.c
> > ===================================================================
> > --- linux-pm.orig/drivers/base/core.c
> > +++ linux-pm/drivers/base/core.c
> > @@ -208,6 +208,16 @@ int device_links_read_lock_held(void)
> >  #endif
> >  #endif /* !CONFIG_SRCU */
> >
> > +static bool device_is_ancestor(struct device *dev, struct device *target)
> > +{
> > +       while (target->parent) {
> > +               target = target->parent;
> > +               if (dev == target)
> > +                       return true;
> > +       }
> > +       return false;
> > +}
> > +
> >  /**
> >   * device_is_dependent - Check if one device depends on another one
> >   * @dev: Device to check dependencies for.
> > @@ -221,7 +231,7 @@ int device_is_dependent(struct device *d
> >         struct device_link *link;
> >         int ret;
> >
> > -       if (dev == target)
> > +       if (dev == target || device_is_ancestor(dev, target))
> >                 return 1;
> >
> >         ret = device_for_each_child(dev, target, device_is_dependent);
> >
>
> The code works, but it's not at all obvious what it's doing. Because,
> at first glance, it's easy to mistakenly think that it's trying to
> catch this case:
> dev <- child1 <- child2 <- target
>
> Maybe it's clearer if we do this check inside the loop?

Which of the loops do you mean?  There are two of them and both need
to do the check in each step AFAICS.

> Something like:
>
>                 if (link->consumer == target ||
> device_is_ancestor(link->consumer, target))
>                         return 1;

So would this be sufficient?

Re: [PATCH] driver core: Extend device_is_dependent()

[Saravana Kannan]

On Thu, Jan 14, 2021 at 11:38 AM Rafael J. Wysocki <rafael@kernel.org> wrote:
>
> On Thu, Jan 14, 2021 at 8:32 PM Saravana Kannan <saravanak@google.com> wrote:
> >
> > On Thu, Jan 14, 2021 at 10:41 AM Rafael J. Wysocki <rjw@rjwysocki.net> wrote:
> > >
> > > From: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
> > >
> > > When adding a new device link, device_is_dependent() is used to
> > > check whether or not the prospective supplier device does not
> > > depend on the prospective consumer one to avoid adding loops
> > > to the graph of device dependencies.
> > >
> > > However, device_is_dependent() does not take the ancestors of
> > > the target device into account, so it may not detect an existing
> > > reverse dependency if, for example, the parent of the target
> > > device depends on the device passed as its first argument.
> > >
> > > For this reason, extend device_is_dependent() to also check if
> > > the device passed as its first argument is an ancestor of the
> > > target one and return 1 if that is the case.
> > >
> > > Signed-off-by: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
> > > Reported-by: Stephan Gerhold <stephan@gerhold.net>
> > > ---
> > >  drivers/base/core.c |   12 +++++++++++-
> > >  1 file changed, 11 insertions(+), 1 deletion(-)
> > >
> > > Index: linux-pm/drivers/base/core.c
> > > ===================================================================
> > > --- linux-pm.orig/drivers/base/core.c
> > > +++ linux-pm/drivers/base/core.c
> > > @@ -208,6 +208,16 @@ int device_links_read_lock_held(void)
> > >  #endif
> > >  #endif /* !CONFIG_SRCU */
> > >
> > > +static bool device_is_ancestor(struct device *dev, struct device *target)
> > > +{
> > > +       while (target->parent) {
> > > +               target = target->parent;
> > > +               if (dev == target)
> > > +                       return true;
> > > +       }
> > > +       return false;
> > > +}
> > > +
> > >  /**
> > >   * device_is_dependent - Check if one device depends on another one
> > >   * @dev: Device to check dependencies for.
> > > @@ -221,7 +231,7 @@ int device_is_dependent(struct device *d
> > >         struct device_link *link;
> > >         int ret;
> > >
> > > -       if (dev == target)
> > > +       if (dev == target || device_is_ancestor(dev, target))
> > >                 return 1;
> > >
> > >         ret = device_for_each_child(dev, target, device_is_dependent);
> > >
> >
> > The code works, but it's not at all obvious what it's doing. Because,
> > at first glance, it's easy to mistakenly think that it's trying to
> > catch this case:
> > dev <- child1 <- child2 <- target
> >
> > Maybe it's clearer if we do this check inside the loop?
>
> Which of the loops do you mean?

Sorry, the list of consumers loop.

> There are two of them and both need
> to do the check in each step AFAICS.

I don't think we need it in the "loop through children" one. Here's why.

We already make sure:
1. The prospective supplier (target) is not a child of the prospective
consumer (dev).
2. The prospective supplier (target) is not a consumer of the
prospective consumer (dev) or any of its children.

To address the problem in the commit, we need to make changes to make sure:
3. The ancestor of prospective supplier (ancestor of target) is not a
child of prospective consumer (dev)
4. The ancestor of prospective supplier (ancestor of target) is not a
consumer of the prospective consumer (dev) or any of its children.

But (3) would be caught automatically when we do (1). Because if (3)
is true, (1) would also be true.
So, what's left is (4), for which my suggestion should be sufficient?

Does it make sense? Or am I missing anything else that needs to be checked?

-Saravana

>
> > Something like:
> >
> >                 if (link->consumer == target ||
> > device_is_ancestor(link->consumer, target))
> >                         return 1;
>
> So would this be sufficient?

Re: [PATCH] driver core: Extend device_is_dependent()

[Rafael J. Wysocki]

On Thu, Jan 14, 2021 at 8:59 PM Saravana Kannan <saravanak@google.com> wrote:
>
> On Thu, Jan 14, 2021 at 11:38 AM Rafael J. Wysocki <rafael@kernel.org> wrote:
> >
> > On Thu, Jan 14, 2021 at 8:32 PM Saravana Kannan <saravanak@google.com> wrote:
> > >
> > > On Thu, Jan 14, 2021 at 10:41 AM Rafael J. Wysocki <rjw@rjwysocki.net> wrote:
> > > >
> > > > From: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
> > > >
> > > > When adding a new device link, device_is_dependent() is used to
> > > > check whether or not the prospective supplier device does not
> > > > depend on the prospective consumer one to avoid adding loops
> > > > to the graph of device dependencies.
> > > >
> > > > However, device_is_dependent() does not take the ancestors of
> > > > the target device into account, so it may not detect an existing
> > > > reverse dependency if, for example, the parent of the target
> > > > device depends on the device passed as its first argument.
> > > >
> > > > For this reason, extend device_is_dependent() to also check if
> > > > the device passed as its first argument is an ancestor of the
> > > > target one and return 1 if that is the case.
> > > >
> > > > Signed-off-by: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
> > > > Reported-by: Stephan Gerhold <stephan@gerhold.net>
> > > > ---
> > > >  drivers/base/core.c |   12 +++++++++++-
> > > >  1 file changed, 11 insertions(+), 1 deletion(-)
> > > >
> > > > Index: linux-pm/drivers/base/core.c
> > > > ===================================================================
> > > > --- linux-pm.orig/drivers/base/core.c
> > > > +++ linux-pm/drivers/base/core.c
> > > > @@ -208,6 +208,16 @@ int device_links_read_lock_held(void)
> > > >  #endif
> > > >  #endif /* !CONFIG_SRCU */
> > > >
> > > > +static bool device_is_ancestor(struct device *dev, struct device *target)
> > > > +{
> > > > +       while (target->parent) {
> > > > +               target = target->parent;
> > > > +               if (dev == target)
> > > > +                       return true;
> > > > +       }
> > > > +       return false;
> > > > +}
> > > > +
> > > >  /**
> > > >   * device_is_dependent - Check if one device depends on another one
> > > >   * @dev: Device to check dependencies for.
> > > > @@ -221,7 +231,7 @@ int device_is_dependent(struct device *d
> > > >         struct device_link *link;
> > > >         int ret;
> > > >
> > > > -       if (dev == target)
> > > > +       if (dev == target || device_is_ancestor(dev, target))
> > > >                 return 1;
> > > >
> > > >         ret = device_for_each_child(dev, target, device_is_dependent);
> > > >
> > >
> > > The code works, but it's not at all obvious what it's doing. Because,
> > > at first glance, it's easy to mistakenly think that it's trying to
> > > catch this case:
> > > dev <- child1 <- child2 <- target
> > >
> > > Maybe it's clearer if we do this check inside the loop?
> >
> > Which of the loops do you mean?
>
> Sorry, the list of consumers loop.
>
> > There are two of them and both need
> > to do the check in each step AFAICS.
>
> I don't think we need it in the "loop through children" one. Here's why.
>
> We already make sure:
> 1. The prospective supplier (target) is not a child of the prospective
> consumer (dev).
> 2. The prospective supplier (target) is not a consumer of the
> prospective consumer (dev) or any of its children.
>
> To address the problem in the commit, we need to make changes to make sure:
> 3. The ancestor of prospective supplier (ancestor of target) is not a
> child of prospective consumer (dev)
> 4. The ancestor of prospective supplier (ancestor of target) is not a
> consumer of the prospective consumer (dev) or any of its children.

This should be taken care of by the recursive device_is_depedent()
invocation in the loop over consumers, but only if (and that's what's
really missing) the supplier has been fully registered.

If the supplier has been initialized, which is specifically checked by
device_link_add(), but not added, it may be missing from its parent's
list of children, but device_is_depedent() only checks those lists.

> But (3) would be caught automatically when we do (1). Because if (3)
> is true, (1) would also be true.
> So, what's left is (4), for which my suggestion should be sufficient?
>
> Does it make sense? Or am I missing anything else that needs to be checked?

AFAICS, the failing case is when the suppliers has been initialized
already, but not fully registered yet, because in that case it is not
sufficient to walk the list of children, it is also necessary to look
at the supplier's parent pointer (and the whole chain of direct
ancestors associated with it).

So the code change in the patch is correct, but the description of it isn't.

Let me respin.

Re: [PATCH] driver core: Extend device_is_dependent()

[Stephan Gerhold]

Hi,

On Thu, Jan 14, 2021 at 11:31:12AM -0800, Saravana Kannan wrote:
> On Thu, Jan 14, 2021 at 10:41 AM Rafael J. Wysocki <rjw@rjwysocki.net> wrote:
> >
> > From: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
> >
> > When adding a new device link, device_is_dependent() is used to
> > check whether or not the prospective supplier device does not
> > depend on the prospective consumer one to avoid adding loops
> > to the graph of device dependencies.
> >
> > However, device_is_dependent() does not take the ancestors of
> > the target device into account, so it may not detect an existing
> > reverse dependency if, for example, the parent of the target
> > device depends on the device passed as its first argument.
> >
> > For this reason, extend device_is_dependent() to also check if
> > the device passed as its first argument is an ancestor of the
> > target one and return 1 if that is the case.
> >
> > Signed-off-by: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
> > Reported-by: Stephan Gerhold <stephan@gerhold.net>
> > ---
> >  drivers/base/core.c |   12 +++++++++++-
> >  1 file changed, 11 insertions(+), 1 deletion(-)
> >
> > Index: linux-pm/drivers/base/core.c
> > ===================================================================
> > --- linux-pm.orig/drivers/base/core.c
> > +++ linux-pm/drivers/base/core.c
> > @@ -208,6 +208,16 @@ int device_links_read_lock_held(void)
> >  #endif
> >  #endif /* !CONFIG_SRCU */
> >
> > +static bool device_is_ancestor(struct device *dev, struct device *target)
> > +{
> > +       while (target->parent) {
> > +               target = target->parent;
> > +               if (dev == target)
> > +                       return true;
> > +       }
> > +       return false;
> > +}
> > +
> >  /**
> >   * device_is_dependent - Check if one device depends on another one
> >   * @dev: Device to check dependencies for.
> > @@ -221,7 +231,7 @@ int device_is_dependent(struct device *d
> >         struct device_link *link;
> >         int ret;
> >
> > -       if (dev == target)
> > +       if (dev == target || device_is_ancestor(dev, target))
> >                 return 1;
> >
> >         ret = device_for_each_child(dev, target, device_is_dependent);
> >
> 

Thanks for the patch, Rafael! I tested it and it seems to avoid the
circular device link (and therefore also the crash). FWIW:

Tested-by: Stephan Gerhold <stephan@gerhold.net>

> The code works, but it's not at all obvious what it's doing. Because,
> at first glance, it's easy to mistakenly think that it's trying to
> catch this case:
> dev <- child1 <- child2 <- target
> 

Isn't this pretty much the case we are trying to catch? I have:

  78d9000.usb <- ci_hdrc.0 <- ci_hdrc.0.ulpi <- phy-ci_hdrc.0.ulpi.0

then something attempts to create a device link with
consumer = 78d9000.usb, supplier = phy-ci_hdrc.0.ulpi.0, and to check if
that is allowed we call device_is_dependent() with dev = 78d9000.usb,
target = phy-ci_hdrc.0.ulpi.0.

Note that this case would normally be covered by the device_for_each_child().
It's not in this case because the klist_children of 78d9000.usb
is updated too late.

> Maybe it's clearer if we do this check inside the loop? Something like:
> 
>                 if (link->consumer == target ||
> device_is_ancestor(link->consumer, target))
>                         return 1;
> 

I tried to test this with the diff below (let me know if I got it wrong).
It does not seem to make any difference though, the circular device link
is still created and without the reorder commit reverted it crashes.

Thanks!
Stephan

diff --git a/drivers/base/core.c b/drivers/base/core.c
index 14f165816742..7af4ef5f89e7 100644
--- a/drivers/base/core.c
+++ b/drivers/base/core.c
@@ -208,6 +208,16 @@ int device_links_read_lock_held(void)
 #endif
 #endif /* !CONFIG_SRCU */
 
+static bool device_is_ancestor(struct device *dev, struct device *target)
+{
+	while (target->parent) {
+		target = target->parent;
+		if (dev == target)
+			return true;
+	}
+	return false;
+}
+
 /**
  * device_is_dependent - Check if one device depends on another one
  * @dev: Device to check dependencies for.
@@ -232,7 +242,7 @@ int device_is_dependent(struct device *dev, void *target)
 		if (link->flags == (DL_FLAG_SYNC_STATE_ONLY | DL_FLAG_MANAGED))
 			continue;
 
-		if (link->consumer == target)
+		if (link->consumer == target || device_is_ancestor(link->consumer, target))
 			return 1;
 
 		ret = device_is_dependent(link->consumer, target);

Re: [PATCH] driver core: Extend device_is_dependent()

[Rafael J. Wysocki]

On Fri, Jan 15, 2021 at 11:03 AM Stephan Gerhold <stephan@gerhold.net> wrote:
>
> Hi,
>
> On Thu, Jan 14, 2021 at 11:31:12AM -0800, Saravana Kannan wrote:
> > On Thu, Jan 14, 2021 at 10:41 AM Rafael J. Wysocki <rjw@rjwysocki.net> wrote:
> > >
> > > From: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
> > >
> > > When adding a new device link, device_is_dependent() is used to
> > > check whether or not the prospective supplier device does not
> > > depend on the prospective consumer one to avoid adding loops
> > > to the graph of device dependencies.
> > >
> > > However, device_is_dependent() does not take the ancestors of
> > > the target device into account, so it may not detect an existing
> > > reverse dependency if, for example, the parent of the target
> > > device depends on the device passed as its first argument.
> > >
> > > For this reason, extend device_is_dependent() to also check if
> > > the device passed as its first argument is an ancestor of the
> > > target one and return 1 if that is the case.
> > >
> > > Signed-off-by: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
> > > Reported-by: Stephan Gerhold <stephan@gerhold.net>
> > > ---
> > >  drivers/base/core.c |   12 +++++++++++-
> > >  1 file changed, 11 insertions(+), 1 deletion(-)
> > >
> > > Index: linux-pm/drivers/base/core.c
> > > ===================================================================
> > > --- linux-pm.orig/drivers/base/core.c
> > > +++ linux-pm/drivers/base/core.c
> > > @@ -208,6 +208,16 @@ int device_links_read_lock_held(void)
> > >  #endif
> > >  #endif /* !CONFIG_SRCU */
> > >
> > > +static bool device_is_ancestor(struct device *dev, struct device *target)
> > > +{
> > > +       while (target->parent) {
> > > +               target = target->parent;
> > > +               if (dev == target)
> > > +                       return true;
> > > +       }
> > > +       return false;
> > > +}
> > > +
> > >  /**
> > >   * device_is_dependent - Check if one device depends on another one
> > >   * @dev: Device to check dependencies for.
> > > @@ -221,7 +231,7 @@ int device_is_dependent(struct device *d
> > >         struct device_link *link;
> > >         int ret;
> > >
> > > -       if (dev == target)
> > > +       if (dev == target || device_is_ancestor(dev, target))
> > >                 return 1;
> > >
> > >         ret = device_for_each_child(dev, target, device_is_dependent);
> > >
> >
>
> Thanks for the patch, Rafael! I tested it and it seems to avoid the
> circular device link (and therefore also the crash). FWIW:
>
> Tested-by: Stephan Gerhold <stephan@gerhold.net>

Thanks!

> > The code works, but it's not at all obvious what it's doing. Because,
> > at first glance, it's easy to mistakenly think that it's trying to
> > catch this case:
> > dev <- child1 <- child2 <- target
> >
>
> Isn't this pretty much the case we are trying to catch? I have:
>
>   78d9000.usb <- ci_hdrc.0 <- ci_hdrc.0.ulpi <- phy-ci_hdrc.0.ulpi.0
>
> then something attempts to create a device link with
> consumer = 78d9000.usb, supplier = phy-ci_hdrc.0.ulpi.0, and to check if
> that is allowed we call device_is_dependent() with dev = 78d9000.usb,
> target = phy-ci_hdrc.0.ulpi.0.
>
> Note that this case would normally be covered by the device_for_each_child().
> It's not in this case because the klist_children of 78d9000.usb
> is updated too late.

Exactly.

The supplier has been initialized, which is why device_is_dependent()
is invoked at all, but it has not been fully registered yet, so
device_for_each_child() cannot be relied on to catch all of the
possible dependencies.

And I say "possible", because the dependency in question is only
partially recorded in the data structures, but IMV device_link_add()
should refuse to create the device link in this case too.

Re: [PATCH] driver core: Extend device_is_dependent()

[Saravana Kannan]

On Fri, Jan 15, 2021 at 5:03 AM Rafael J. Wysocki <rafael@kernel.org> wrote:
>
> On Fri, Jan 15, 2021 at 11:03 AM Stephan Gerhold <stephan@gerhold.net> wrote:
> >
> > Hi,
> >
> > On Thu, Jan 14, 2021 at 11:31:12AM -0800, Saravana Kannan wrote:
> > > On Thu, Jan 14, 2021 at 10:41 AM Rafael J. Wysocki <rjw@rjwysocki.net> wrote:
> > > >
> > > > From: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
> > > >
> > > > When adding a new device link, device_is_dependent() is used to
> > > > check whether or not the prospective supplier device does not
> > > > depend on the prospective consumer one to avoid adding loops
> > > > to the graph of device dependencies.
> > > >
> > > > However, device_is_dependent() does not take the ancestors of
> > > > the target device into account, so it may not detect an existing
> > > > reverse dependency if, for example, the parent of the target
> > > > device depends on the device passed as its first argument.
> > > >
> > > > For this reason, extend device_is_dependent() to also check if
> > > > the device passed as its first argument is an ancestor of the
> > > > target one and return 1 if that is the case.
> > > >
> > > > Signed-off-by: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
> > > > Reported-by: Stephan Gerhold <stephan@gerhold.net>
> > > > ---
> > > >  drivers/base/core.c |   12 +++++++++++-
> > > >  1 file changed, 11 insertions(+), 1 deletion(-)
> > > >
> > > > Index: linux-pm/drivers/base/core.c
> > > > ===================================================================
> > > > --- linux-pm.orig/drivers/base/core.c
> > > > +++ linux-pm/drivers/base/core.c
> > > > @@ -208,6 +208,16 @@ int device_links_read_lock_held(void)
> > > >  #endif
> > > >  #endif /* !CONFIG_SRCU */
> > > >
> > > > +static bool device_is_ancestor(struct device *dev, struct device *target)
> > > > +{
> > > > +       while (target->parent) {
> > > > +               target = target->parent;
> > > > +               if (dev == target)
> > > > +                       return true;
> > > > +       }
> > > > +       return false;
> > > > +}
> > > > +
> > > >  /**
> > > >   * device_is_dependent - Check if one device depends on another one
> > > >   * @dev: Device to check dependencies for.
> > > > @@ -221,7 +231,7 @@ int device_is_dependent(struct device *d
> > > >         struct device_link *link;
> > > >         int ret;
> > > >
> > > > -       if (dev == target)
> > > > +       if (dev == target || device_is_ancestor(dev, target))
> > > >                 return 1;
> > > >
> > > >         ret = device_for_each_child(dev, target, device_is_dependent);
> > > >
> > >
> >
> > Thanks for the patch, Rafael! I tested it and it seems to avoid the
> > circular device link (and therefore also the crash). FWIW:
> >
> > Tested-by: Stephan Gerhold <stephan@gerhold.net>
>
> Thanks!
>
> > > The code works, but it's not at all obvious what it's doing. Because,
> > > at first glance, it's easy to mistakenly think that it's trying to
> > > catch this case:
> > > dev <- child1 <- child2 <- target
> > >
> >
> > Isn't this pretty much the case we are trying to catch? I have:
> >
> >   78d9000.usb <- ci_hdrc.0 <- ci_hdrc.0.ulpi <- phy-ci_hdrc.0.ulpi.0
> >
> > then something attempts to create a device link with
> > consumer = 78d9000.usb, supplier = phy-ci_hdrc.0.ulpi.0, and to check if
> > that is allowed we call device_is_dependent() with dev = 78d9000.usb,
> > target = phy-ci_hdrc.0.ulpi.0.
> >
> > Note that this case would normally be covered by the device_for_each_child().
> > It's not in this case because the klist_children of 78d9000.usb
> > is updated too late.
>
> Exactly.

Stephan,

What device/driver is this? Is this a dwc3 device/driver? That driver
does some weird/incorrect stuff the last time I checked.

>
> The supplier has been initialized, which is why device_is_dependent()
> is invoked at all, but it has not been fully registered yet, so
> device_for_each_child() cannot be relied on to catch all of the
> possible dependencies.

Rafael,

Ok, I understand this additional case now.

What functions does one call to get the device to this state? AFAIR,
device_add() does both the "initialization" and adding to the
parent's children list.

I'm okay with this, but I want to make sure the driver isn't doing weird stuff.

-Saravana

Re: [PATCH] driver core: Extend device_is_dependent()

[Rafael J. Wysocki]

On Fri, Jan 15, 2021 at 6:21 PM Saravana Kannan <saravanak@google.com> wrote:
>
> On Fri, Jan 15, 2021 at 5:03 AM Rafael J. Wysocki <rafael@kernel.org> wrote:
> >
> > On Fri, Jan 15, 2021 at 11:03 AM Stephan Gerhold <stephan@gerhold.net> wrote:
> > >
> > > Hi,
> > >
> > > On Thu, Jan 14, 2021 at 11:31:12AM -0800, Saravana Kannan wrote:
> > > > On Thu, Jan 14, 2021 at 10:41 AM Rafael J. Wysocki <rjw@rjwysocki.net> wrote:
> > > > >
> > > > > From: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
> > > > >
> > > > > When adding a new device link, device_is_dependent() is used to
> > > > > check whether or not the prospective supplier device does not
> > > > > depend on the prospective consumer one to avoid adding loops
> > > > > to the graph of device dependencies.
> > > > >
> > > > > However, device_is_dependent() does not take the ancestors of
> > > > > the target device into account, so it may not detect an existing
> > > > > reverse dependency if, for example, the parent of the target
> > > > > device depends on the device passed as its first argument.
> > > > >
> > > > > For this reason, extend device_is_dependent() to also check if
> > > > > the device passed as its first argument is an ancestor of the
> > > > > target one and return 1 if that is the case.
> > > > >
> > > > > Signed-off-by: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
> > > > > Reported-by: Stephan Gerhold <stephan@gerhold.net>
> > > > > ---
> > > > >  drivers/base/core.c |   12 +++++++++++-
> > > > >  1 file changed, 11 insertions(+), 1 deletion(-)
> > > > >
> > > > > Index: linux-pm/drivers/base/core.c
> > > > > ===================================================================
> > > > > --- linux-pm.orig/drivers/base/core.c
> > > > > +++ linux-pm/drivers/base/core.c
> > > > > @@ -208,6 +208,16 @@ int device_links_read_lock_held(void)
> > > > >  #endif
> > > > >  #endif /* !CONFIG_SRCU */
> > > > >
> > > > > +static bool device_is_ancestor(struct device *dev, struct device *target)
> > > > > +{
> > > > > +       while (target->parent) {
> > > > > +               target = target->parent;
> > > > > +               if (dev == target)
> > > > > +                       return true;
> > > > > +       }
> > > > > +       return false;
> > > > > +}
> > > > > +
> > > > >  /**
> > > > >   * device_is_dependent - Check if one device depends on another one
> > > > >   * @dev: Device to check dependencies for.
> > > > > @@ -221,7 +231,7 @@ int device_is_dependent(struct device *d
> > > > >         struct device_link *link;
> > > > >         int ret;
> > > > >
> > > > > -       if (dev == target)
> > > > > +       if (dev == target || device_is_ancestor(dev, target))
> > > > >                 return 1;
> > > > >
> > > > >         ret = device_for_each_child(dev, target, device_is_dependent);
> > > > >
> > > >
> > >
> > > Thanks for the patch, Rafael! I tested it and it seems to avoid the
> > > circular device link (and therefore also the crash). FWIW:
> > >
> > > Tested-by: Stephan Gerhold <stephan@gerhold.net>
> >
> > Thanks!
> >
> > > > The code works, but it's not at all obvious what it's doing. Because,
> > > > at first glance, it's easy to mistakenly think that it's trying to
> > > > catch this case:
> > > > dev <- child1 <- child2 <- target
> > > >
> > >
> > > Isn't this pretty much the case we are trying to catch? I have:
> > >
> > >   78d9000.usb <- ci_hdrc.0 <- ci_hdrc.0.ulpi <- phy-ci_hdrc.0.ulpi.0
> > >
> > > then something attempts to create a device link with
> > > consumer = 78d9000.usb, supplier = phy-ci_hdrc.0.ulpi.0, and to check if
> > > that is allowed we call device_is_dependent() with dev = 78d9000.usb,
> > > target = phy-ci_hdrc.0.ulpi.0.
> > >
> > > Note that this case would normally be covered by the device_for_each_child().
> > > It's not in this case because the klist_children of 78d9000.usb
> > > is updated too late.
> >
> > Exactly.
>
> Stephan,
>
> What device/driver is this? Is this a dwc3 device/driver? That driver
> does some weird/incorrect stuff the last time I checked.
>
> >
> > The supplier has been initialized, which is why device_is_dependent()
> > is invoked at all, but it has not been fully registered yet, so
> > device_for_each_child() cannot be relied on to catch all of the
> > possible dependencies.
>
> Rafael,
>
> Ok, I understand this additional case now.
>
> What functions does one call to get the device to this state?

device_initialize() followed by device_link_add() (with the device
passed as the supplier) and device_add().

> AFAIR, device_add() does both the "initialization" and adding to the
> parent's children list.

device_register() does that.

>
> I'm okay with this, but I want to make sure the driver isn't doing weird stuff.

So the purpose of the change is to make device_link_add() catch that. :-)

Re: [PATCH] driver core: Extend device_is_dependent()

[Stephan Gerhold]

On Fri, Jan 15, 2021 at 09:20:54AM -0800, Saravana Kannan wrote:
> On Fri, Jan 15, 2021 at 5:03 AM Rafael J. Wysocki <rafael@kernel.org> wrote:
> > On Fri, Jan 15, 2021 at 11:03 AM Stephan Gerhold <stephan@gerhold.net> wrote:
> > > On Thu, Jan 14, 2021 at 11:31:12AM -0800, Saravana Kannan wrote:
> > > > On Thu, Jan 14, 2021 at 10:41 AM Rafael J. Wysocki <rjw@rjwysocki.net> wrote:
> > > > >
> > > > > From: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
> > > > >
> > > > > When adding a new device link, device_is_dependent() is used to
> > > > > check whether or not the prospective supplier device does not
> > > > > depend on the prospective consumer one to avoid adding loops
> > > > > to the graph of device dependencies.
> > > > >
> > > > > However, device_is_dependent() does not take the ancestors of
> > > > > the target device into account, so it may not detect an existing
> > > > > reverse dependency if, for example, the parent of the target
> > > > > device depends on the device passed as its first argument.
> > > > >
> > > > > For this reason, extend device_is_dependent() to also check if
> > > > > the device passed as its first argument is an ancestor of the
> > > > > target one and return 1 if that is the case.
> > > > >
> > > > > Signed-off-by: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
> > > > > Reported-by: Stephan Gerhold <stephan@gerhold.net>
> > > > > ---
> > > > >  drivers/base/core.c |   12 +++++++++++-
> > > > >  1 file changed, 11 insertions(+), 1 deletion(-)
> > > > >
> > > > > Index: linux-pm/drivers/base/core.c
> > > > > ===================================================================
> > > > > --- linux-pm.orig/drivers/base/core.c
> > > > > +++ linux-pm/drivers/base/core.c
> > > > > @@ -208,6 +208,16 @@ int device_links_read_lock_held(void)
> > > > >  #endif
> > > > >  #endif /* !CONFIG_SRCU */
> > > > >
> > > > > +static bool device_is_ancestor(struct device *dev, struct device *target)
> > > > > +{
> > > > > +       while (target->parent) {
> > > > > +               target = target->parent;
> > > > > +               if (dev == target)
> > > > > +                       return true;
> > > > > +       }
> > > > > +       return false;
> > > > > +}
> > > > > +
> > > > >  /**
> > > > >   * device_is_dependent - Check if one device depends on another one
> > > > >   * @dev: Device to check dependencies for.
> > > > > @@ -221,7 +231,7 @@ int device_is_dependent(struct device *d
> > > > >         struct device_link *link;
> > > > >         int ret;
> > > > >
> > > > > -       if (dev == target)
> > > > > +       if (dev == target || device_is_ancestor(dev, target))
> > > > >                 return 1;
> > > > >
> > > > >         ret = device_for_each_child(dev, target, device_is_dependent);
> > > > >
> > > >
> > > > The code works, but it's not at all obvious what it's doing. Because,
> > > > at first glance, it's easy to mistakenly think that it's trying to
> > > > catch this case:
> > > > dev <- child1 <- child2 <- target
> > > >
> > >
> > > Isn't this pretty much the case we are trying to catch? I have:
> > >
> > >   78d9000.usb <- ci_hdrc.0 <- ci_hdrc.0.ulpi <- phy-ci_hdrc.0.ulpi.0
> > >
> > > then something attempts to create a device link with
> > > consumer = 78d9000.usb, supplier = phy-ci_hdrc.0.ulpi.0, and to check if
> > > that is allowed we call device_is_dependent() with dev = 78d9000.usb,
> > > target = phy-ci_hdrc.0.ulpi.0.
> > >
> > > Note that this case would normally be covered by the device_for_each_child().
> > > It's not in this case because the klist_children of 78d9000.usb
> > > is updated too late.
> >
> > Exactly.
> 
> Stephan,
> 
> What device/driver is this? Is this a dwc3 device/driver? That driver
> does some weird/incorrect stuff the last time I checked.
> 

I described my situation in this mail thread:
https://lore.kernel.org/lkml/X%2FycQpu7NIGI969v@gerhold.net/

It's USB, but chipidea on apq8016-sbc in this case. The situation is
definitely kind of weird, but not sure if it is wrong per-se.

Thanks,
Stephan