driver core: Extend device_is_dependent()

From: Rafael J. Wysocki <[email protected]>

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

Reported-by Stephan Gerhold <[email protected]>

---
 drivers/base/core.c |   12 +++++++++++-
 1 file changed, 11 insertions(+), 1 deletion(-)

Index: linux-pm/drivers/base/core.c
===================================================================

drivers/base/core.c +10 -0

@@ -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.

Quoted 46 lines · Rafael J. Wysocki

From: Rafael J. Wysocki <[email protected]>

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

Reported-by Stephan Gerhold <[email protected]>

---
 drivers/base/core.c |   12 +++++++++++-
 1 file changed, 11 insertions(+), 1 deletion(-)

Index: linux-pm/drivers/base/core.c
===================================================================

drivers/base/core.c +10 -0

@@ -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.

drivers/base/core.c int device_is_dependent(struct device *d · line 237

Quoted 8 lines

drivers/base/core.c +1 -1

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

Quoted 62 lines · Saravana Kannan

Quoted 46 lines · Rafael J. Wysocki

From: Rafael J. Wysocki <[email protected]>

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

Reported-by Stephan Gerhold <[email protected]>

---
 drivers/base/core.c |   12 +++++++++++-
 1 file changed, 11 insertions(+), 1 deletion(-)

Index: linux-pm/drivers/base/core.c
===================================================================

drivers/base/core.c +10 -0

@@ -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.

drivers/base/core.c int device_is_dependent(struct device *d · line 237

Quoted 8 lines

drivers/base/core.c +1 -1

@@ -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

Quoted 1 line

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.

Quoted 6 lines

Something like:

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

So would this be sufficient?

Quoted 64 lines · Rafael J. Wysocki

Quoted 62 lines · Saravana Kannan

Quoted 46 lines · Rafael J. Wysocki

From: Rafael J. Wysocki <[email protected]>

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

Reported-by Stephan Gerhold <[email protected]>

---
 drivers/base/core.c |   12 +++++++++++-
 1 file changed, 11 insertions(+), 1 deletion(-)

Index: linux-pm/drivers/base/core.c
===================================================================

drivers/base/core.c +10 -0

@@ -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.

drivers/base/core.c int device_is_dependent(struct device *d · line 237

Quoted 8 lines

drivers/base/core.c +1 -1

@@ -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

Quoted 3 lines

Quoted 1 line

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.

Quoted 2 lines

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?

Quoted 48 lines · Rafael J. Wysocki

From: Rafael J. Wysocki <[email protected]>

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

Reported-by Stephan Gerhold <[email protected]>

---
 drivers/base/core.c |   12 +++++++++++-
 1 file changed, 11 insertions(+), 1 deletion(-)

Index: linux-pm/drivers/base/core.c
===================================================================

drivers/base/core.c +10 -0

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

drivers/base/core.c int device_is_dependent(struct device *d · line 237

Quoted 6 lines

drivers/base/core.c +1 -1

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

Hi,

Quoted 53 lines · Saravana Kannan

Quoted 52 lines · Rafael J. Wysocki

From: Rafael J. Wysocki <[email protected]>

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

Reported-by Stephan Gerhold <[email protected]>

---
 drivers/base/core.c |   12 +++++++++++-
 1 file changed, 11 insertions(+), 1 deletion(-)

Index: linux-pm/drivers/base/core.c
===================================================================

drivers/base/core.c +11 -1

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

Quoted 3 lines

drivers/base/core.c int device_is_dependent(struct device *d · line 237

Quoted 2 lines

drivers/base/core.c +0 -0

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

Quoted 5 lines

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.

Quoted 57 lines · Stephan Gerhold

Hi,

Quoted 53 lines · Saravana Kannan

Quoted 52 lines · Rafael J. Wysocki

From: Rafael J. Wysocki <[email protected]>

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

Reported-by Stephan Gerhold <[email protected]>

---
 drivers/base/core.c |   12 +++++++++++-
 1 file changed, 11 insertions(+), 1 deletion(-)

Index: linux-pm/drivers/base/core.c
===================================================================

drivers/base/core.c +11 -1

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

Quoted 8 lines

Quoted 3 lines

drivers/base/core.c int device_is_dependent(struct device *d · line 237

Quoted 2 lines

drivers/base/core.c +0 -0

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

Thanks!

Quoted 15 lines

Quoted 5 lines

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.

Quoted 3 lines

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.

Quoted 85 lines · Rafael J. Wysocki

Quoted 57 lines · Stephan Gerhold

Hi,

Quoted 53 lines · Saravana Kannan

Quoted 52 lines · Rafael J. Wysocki

From: Rafael J. Wysocki <[email protected]>

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

Reported-by Stephan Gerhold <[email protected]>

---
 drivers/base/core.c |   12 +++++++++++-
 1 file changed, 11 insertions(+), 1 deletion(-)

Index: linux-pm/drivers/base/core.c
===================================================================

drivers/base/core.c +11 -1

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

Quoted 8 lines

Quoted 3 lines

drivers/base/core.c int device_is_dependent(struct device *d · line 237

Quoted 2 lines

drivers/base/core.c +0 -0

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

Thanks!

Quoted 15 lines

Quoted 5 lines

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.

Quoted 5 lines

Quoted 3 lines

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.

Quoted 5 lines

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.

Quoted 77 lines · Rafael J. Wysocki

Quoted 75 lines · Stephan Gerhold

Quoted 53 lines · Saravana Kannan

Quoted 52 lines · Rafael J. Wysocki

From: Rafael J. Wysocki <[email protected]>

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

Reported-by Stephan Gerhold <[email protected]>

---
 drivers/base/core.c |   12 +++++++++++-
 1 file changed, 11 insertions(+), 1 deletion(-)

Index: linux-pm/drivers/base/core.c
===================================================================

drivers/base/core.c +11 -1

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

Quoted 8 lines

drivers/base/core.c int device_is_dependent(struct device *d · line 237

Quoted 2 lines

drivers/base/core.c +0 -0

        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.

Quoted 1 line

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.