driver core: fw_devlink: Add support for batching fwnode parsing

The amount of time spent parsing fwnodes of devices can become really
high if the devices are added in an non-ideal order. Worst case can be
O(N^2) when N devices are added. But this can be optimized to O(N) by
adding all the devices and then parsing all their fwnodes in one batch.

This commit adds fw_devlink_pause() and fw_devlink_resume() to allow
doing this.

Signed-off-by: Saravana Kannan <saravanak@google.com>
Link: https://lore.kernel.org/r/20200515053500.215929-4-saravanak@google.com
Signed-off-by: Greg Kroah-Hartman <gregkh@linuxfoundation.org>

diff --git a/drivers/base/base.h b/drivers/base/base.h
index 40fb069..95c22c0 100644 (file)
--- a/drivers/base/base.h
+++ b/drivers/base/base.h
@@ -153,6 +153,7 @@ extern char *make_class_name(const char *name, struct kobject *kobj);
 extern int devres_release_all(struct device *dev);
 extern void device_block_probing(void);
 extern void device_unblock_probing(void);
+extern void driver_deferred_probe_force_trigger(void);
 
 /* /sys/devices directory */
 extern struct kset *devices_kset;

diff --git a/drivers/base/core.c b/drivers/base/core.c
index f585d92..84c5697 100644 (file)
--- a/drivers/base/core.c
+++ b/drivers/base/core.c
@@ -49,6 +49,9 @@ static LIST_HEAD(wait_for_suppliers);
 static DEFINE_MUTEX(wfs_lock);
 static LIST_HEAD(deferred_sync);
 static unsigned int defer_sync_state_count = 1;
+static unsigned int defer_fw_devlink_count;
+static DEFINE_MUTEX(defer_fw_devlink_lock);
+static bool fw_devlink_is_permissive(void);
 
 #ifdef CONFIG_SRCU
 static DEFINE_MUTEX(device_links_lock);
@@ -527,7 +530,7 @@ static void device_link_add_missing_supplier_links(void)
                int ret = fwnode_call_int_op(dev->fwnode, add_links, dev);
                if (!ret)
                        list_del_init(&dev->links.needs_suppliers);
-               else if (ret != -ENODEV)
+               else if (ret != -ENODEV || fw_devlink_is_permissive())
                        dev->links.need_for_probe = false;
        }
        mutex_unlock(&wfs_lock);
@@ -1177,17 +1180,116 @@ static void fw_devlink_link_device(struct device *dev)
 {
        int fw_ret;
 
-       device_link_add_missing_supplier_links();
+       if (!fw_devlink_flags)
+               return;
+
+       mutex_lock(&defer_fw_devlink_lock);
+       if (!defer_fw_devlink_count)
+               device_link_add_missing_supplier_links();
+
+       /*
+        * The device's fwnode not having add_links() doesn't affect if other
+        * consumers can find this device as a supplier.  So, this check is
+        * intentionally placed after device_link_add_missing_supplier_links().
+        */
+       if (!fwnode_has_op(dev->fwnode, add_links))
+               goto out;
 
-       if (fw_devlink_flags && fwnode_has_op(dev->fwnode, add_links)) {
+       /*
+        * If fw_devlink is being deferred, assume all devices have mandatory
+        * suppliers they need to link to later. Then, when the fw_devlink is
+        * resumed, all these devices will get a chance to try and link to any
+        * suppliers they have.
+        */
+       if (!defer_fw_devlink_count) {
                fw_ret = fwnode_call_int_op(dev->fwnode, add_links, dev);
-               if (fw_ret == -ENODEV && !fw_devlink_is_permissive())
-                       device_link_wait_for_mandatory_supplier(dev);
-               else if (fw_ret)
-                       device_link_wait_for_optional_supplier(dev);
+               if (fw_ret == -ENODEV && fw_devlink_is_permissive())
+                       fw_ret = -EAGAIN;
+       } else {
+               fw_ret = -ENODEV;
        }
+
+       if (fw_ret == -ENODEV)
+               device_link_wait_for_mandatory_supplier(dev);
+       else if (fw_ret)
+               device_link_wait_for_optional_supplier(dev);
+
+out:
+       mutex_unlock(&defer_fw_devlink_lock);
 }
 
+/**
+ * fw_devlink_pause - Pause parsing of fwnode to create device links
+ *
+ * Calling this function defers any fwnode parsing to create device links until
+ * fw_devlink_resume() is called. Both these functions are ref counted and the
+ * caller needs to match the calls.
+ *
+ * While fw_devlink is paused:
+ * - Any device that is added won't have its fwnode parsed to create device
+ *   links.
+ * - The probe of the device will also be deferred during this period.
+ * - Any devices that were already added, but waiting for suppliers won't be
+ *   able to link to newly added devices.
+ *
+ * Once fw_devlink_resume():
+ * - All the fwnodes that was not parsed will be parsed.
+ * - All the devices that were deferred probing will be reattempted if they
+ *   aren't waiting for any more suppliers.
+ *
+ * This pair of functions, is mainly meant to optimize the parsing of fwnodes
+ * when a lot of devices that need to link to each other are added in a short
+ * interval of time. For example, adding all the top level devices in a system.
+ *
+ * For example, if N devices are added and:
+ * - All the consumers are added before their suppliers
+ * - All the suppliers of the N devices are part of the N devices
+ *
+ * Then:
+ *
+ * - With the use of fw_devlink_pause() and fw_devlink_resume(), each device
+ *   will only need one parsing of its fwnode because it is guaranteed to find
+ *   all the supplier devices already registered and ready to link to. It won't
+ *   have to do another pass later to find one or more suppliers it couldn't
+ *   find in the first parse of the fwnode. So, we'll only need O(N) fwnode
+ *   parses.
+ *
+ * - Without the use of fw_devlink_pause() and fw_devlink_resume(), we would
+ *   end up doing O(N^2) parses of fwnodes because every device that's added is
+ *   guaranteed to trigger a parse of the fwnode of every device added before
+ *   it. This O(N^2) parse is made worse by the fact that when a fwnode of a
+ *   device is parsed, all it descendant devices might need to have their
+ *   fwnodes parsed too (even if the devices themselves aren't added).
+ */
+void fw_devlink_pause(void)
+{
+       mutex_lock(&defer_fw_devlink_lock);
+       defer_fw_devlink_count++;
+       mutex_unlock(&defer_fw_devlink_lock);
+}
+
+/** fw_devlink_resume - Resume parsing of fwnode to create device links
+ *
+ * This function is used in conjunction with fw_devlink_pause() and is ref
+ * counted. See documentation for fw_devlink_pause() for more details.
+ */
+void fw_devlink_resume(void)
+{
+       mutex_lock(&defer_fw_devlink_lock);
+       if (!defer_fw_devlink_count) {
+               WARN(true, "Unmatched fw_devlink pause/resume!");
+               goto out;
+       }
+
+       defer_fw_devlink_count--;
+       if (defer_fw_devlink_count)
+               goto out;
+
+       device_link_add_missing_supplier_links();
+       driver_deferred_probe_force_trigger();
+out:
+       mutex_unlock(&defer_fw_devlink_lock);
+}
 /* Device links support end. */
 
 int (*platform_notify)(struct device *dev) = NULL;

diff --git a/drivers/base/dd.c b/drivers/base/dd.c
index 48ca81c..63991d9 100644 (file)
--- a/drivers/base/dd.c
+++ b/drivers/base/dd.c
@@ -160,6 +160,14 @@ static bool driver_deferred_probe_enable = false;
  * again.
  */
 static void driver_deferred_probe_trigger(void)
+{
+       if (!driver_deferred_probe_enable)
+               return;
+
+       driver_deferred_probe_force_trigger();
+}
+
+void driver_deferred_probe_force_trigger(void)
 {
        if (!driver_deferred_probe_enable)
                return;

diff --git a/include/linux/fwnode.h b/include/linux/fwnode.h
index e0abafb..9506f8e 100644 (file)
--- a/include/linux/fwnode.h
+++ b/include/linux/fwnode.h
@@ -171,5 +171,7 @@ struct fwnode_operations {
 #define get_dev_from_fwnode(fwnode)    get_device((fwnode)->dev)
 
 extern u32 fw_devlink_get_flags(void);
+void fw_devlink_pause(void);
+void fw_devlink_resume(void);
 
 #endif