[v8,01/10] ACPI: scan: Remove the second DSDT traversal

Collect the devices with _DEP into a list and continue processing them
after a full traversal, instead of doing a full second traversal of the
tree.

This makes the second DSDT traversal pass unnecessary as we already have
the nodes we're interested in in a linked list.

Signed-off-by: Sakari Ailus <sakari.ailus@linux.intel.com>
---
 drivers/acpi/scan.c | 125 ++++++++++++++++++++++++++++++++------------
 1 file changed, 92 insertions(+), 33 deletions(-)

On Wed, Mar 29, 2023 at 12:10 PM Sakari Ailus
<sakari.ailus@linux.intel.com> wrote:
>
> Collect the devices with _DEP into a list and continue processing them
> after a full traversal, instead of doing a full second traversal of the
> tree.
>
> This makes the second DSDT traversal pass unnecessary as we already have
> the nodes we're interested in in a linked list.

The second traversal of the ACPI namespace (it may not be just the
DSDT at that point to be precise) is not really about _DEP handling.
In fact, the latter has been added on top of it.

It is about the PCI enumeration.  Namely, when acpi_pci_root_add()
runs for the PCI host bridge object in the ACPI namespace, the entire
device hierarchy below it is walked and all of the ACPI device objects
corresponding to the PCI devices on the bus are assumed to be present.
This means that all of the ACPI device objects need to be created in
the first walk, without binding any ACPI drivers or scan handlers to
them, and the second walk is to find out what is actually represented
by those objects.

It cannot be eliminated in any simple way.

> Signed-off-by: Sakari Ailus <sakari.ailus@linux.intel.com>
> ---
>  drivers/acpi/scan.c | 125 ++++++++++++++++++++++++++++++++------------
>  1 file changed, 92 insertions(+), 33 deletions(-)
>
> diff --git a/drivers/acpi/scan.c b/drivers/acpi/scan.c
> index 0c6f06abe3f4..280d12e0aa2f 100644
> --- a/drivers/acpi/scan.c
> +++ b/drivers/acpi/scan.c
> @@ -2029,10 +2029,52 @@ static u32 acpi_scan_check_dep(acpi_handle handle, bool check_dep)
>         return count;
>  }
>
> -static bool acpi_bus_scan_second_pass;
> +/**
> + * struct acpi_postponed_handle - A postponed ACPI handle
> + * @list: Entry in a postponed list
> + * @handle: The postponed handle
> + *
> + * One such entry represents an ACPI handle the scanning of which has been
> + * postponed.
> + */
> +struct acpi_postponed_handle {
> +       struct list_head list;
> +       acpi_handle handle;
> +};
> +
> +/**
> + * struct acpi_scan_context - Context for scanning ACPI devices
> + * @postponed_head: The list head of the postponed ACPI handles
> + * @device: The first encountered device, typically the root of the scanned tree
> + */
> +struct acpi_scan_context {
> +       struct list_head postponed_head;
> +       struct acpi_device *device;
> +};
> +
> +/**
> + * acpi_bus_handle_postpone - Add an ACPI handle to a given postponed list
> + * @handle: The ACPI handle
> + * @head: Postponed list head
> + *
> + * Add a given ACPI handle to a list of ACPI objects for which the creation
> + * of the device objects is to be postponed.
> + */
> +static void acpi_bus_handle_postpone(acpi_handle handle,
> +                                    struct list_head *head)
> +{
> +       struct acpi_postponed_handle *ph;
> +
> +       ph = kzalloc(sizeof(*ph), GFP_KERNEL);
> +       if (!ph)
> +               return;
> +
> +       ph->handle = handle;
> +       list_add(&ph->list, head);
> +}
>
>  static acpi_status acpi_bus_check_add(acpi_handle handle, bool check_dep,
> -                                     struct acpi_device **adev_p)
> +                                     struct acpi_scan_context *ctx)
>  {
>         struct acpi_device *device = acpi_fetch_acpi_dev(handle);
>         acpi_object_type acpi_type;
> @@ -2051,7 +2093,7 @@ static acpi_status acpi_bus_check_add(acpi_handle handle, bool check_dep,
>
>                 /* Bail out if there are dependencies. */
>                 if (acpi_scan_check_dep(handle, check_dep) > 0) {
> -                       acpi_bus_scan_second_pass = true;
> +                       acpi_bus_handle_postpone(handle, &ctx->postponed_head);
>                         return AE_CTRL_DEPTH;
>                 }
>
> @@ -2086,22 +2128,22 @@ static acpi_status acpi_bus_check_add(acpi_handle handle, bool check_dep,
>         acpi_scan_init_hotplug(device);
>
>  out:
> -       if (!*adev_p)
> -               *adev_p = device;
> +       if (!ctx->device)
> +               ctx->device = device;
>
>         return AE_OK;
>  }
>
>  static acpi_status acpi_bus_check_add_1(acpi_handle handle, u32 lvl_not_used,
> -                                       void *not_used, void **ret_p)
> +                                       void *ctx, void **unused)
>  {
> -       return acpi_bus_check_add(handle, true, (struct acpi_device **)ret_p);
> +       return acpi_bus_check_add(handle, true, (struct acpi_scan_context *)ctx);
>  }
>
>  static acpi_status acpi_bus_check_add_2(acpi_handle handle, u32 lvl_not_used,
> -                                       void *not_used, void **ret_p)
> +                                       void *ctx, void **device)
>  {
> -       return acpi_bus_check_add(handle, false, (struct acpi_device **)ret_p);
> +       return acpi_bus_check_add(handle, false, (struct acpi_scan_context *)ctx);
>  }
>
>  static void acpi_default_enumeration(struct acpi_device *device)
> @@ -2422,37 +2464,54 @@ EXPORT_SYMBOL_GPL(acpi_dev_get_next_consumer_dev);
>   */
>  int acpi_bus_scan(acpi_handle handle)
>  {
> -       struct acpi_device *device = NULL;
> -
> -       acpi_bus_scan_second_pass = false;
> -
> -       /* Pass 1: Avoid enumerating devices with missing dependencies. */
> +       struct acpi_scan_context ctx = {
> +               .postponed_head = LIST_HEAD_INIT(ctx.postponed_head),
> +       };
> +       struct acpi_postponed_handle *ph, *tmp_ph;
> +       int ret = 0;
>
> -       if (ACPI_SUCCESS(acpi_bus_check_add(handle, true, &device)))
> +       if (ACPI_SUCCESS(acpi_bus_check_add(handle, true, &ctx)))
>                 acpi_walk_namespace(ACPI_TYPE_ANY, handle, ACPI_UINT32_MAX,
> -                                   acpi_bus_check_add_1, NULL, NULL,
> -                                   (void **)&device);
> -
> -       if (!device)
> -               return -ENODEV;
> -
> -       acpi_bus_attach(device, (void *)true);
> +                                   acpi_bus_check_add_1, NULL, (void *)&ctx,
> +                                   NULL);
>
> -       if (!acpi_bus_scan_second_pass)
> -               return 0;
> -
> -       /* Pass 2: Enumerate all of the remaining devices. */
> +       if (!ctx.device) {
> +               ret = -ENODEV;
> +               goto out_release;
> +       }
>
> -       device = NULL;
> +       acpi_bus_attach(ctx.device, (void *)true);
>
> -       if (ACPI_SUCCESS(acpi_bus_check_add(handle, false, &device)))
> -               acpi_walk_namespace(ACPI_TYPE_ANY, handle, ACPI_UINT32_MAX,
> -                                   acpi_bus_check_add_2, NULL, NULL,
> -                                   (void **)&device);
> +       /*
> +        * Proceed to register ACPI devices that were postponed due to _DEP
> +        * objects during the namespace walk.
> +        */
> +       list_for_each_entry_safe(ph, tmp_ph, &ctx.postponed_head, list) {
> +               list_del(&ph->list);
> +               /* Set device NULL here to obtain the root for this sub-tree. */
> +               ctx.device = NULL;
> +               /*
> +                * Do this manually, as the namespace walk will only include
> +                * sub-nodes, not the node itself. ctx.device is set to the
> +                * ACPI device corresponding ph->handle.
> +                */
> +               acpi_bus_check_add_2(ph->handle, 0, &ctx, NULL);
> +               /* Walk the rest of the sub-namespace. */
> +               acpi_walk_namespace(ACPI_TYPE_ANY, ph->handle, ACPI_UINT32_MAX,
> +                                   acpi_bus_check_add_2, NULL, (void *)&ctx,
> +                                   NULL);
> +               if (ctx.device)
> +                       acpi_bus_attach(ctx.device, NULL);
> +               kfree(ph);
> +       }
>
> -       acpi_bus_attach(device, NULL);
> +out_release:
> +       list_for_each_entry_safe(ph, tmp_ph, &ctx.postponed_head, list) {
> +               list_del(&ph->list);
> +               kfree(ph);
> +       }
>
> -       return 0;
> +       return ret;
>  }
>  EXPORT_SYMBOL(acpi_bus_scan);
>
> --
> 2.30.2
>

Hi Rafael,

Thank you for the review.

On Tue, May 09, 2023 at 08:06:28PM +0200, Rafael J. Wysocki wrote:
> On Wed, Mar 29, 2023 at 12:10 PM Sakari Ailus
> <sakari.ailus@linux.intel.com> wrote:
> >
> > Collect the devices with _DEP into a list and continue processing them
> > after a full traversal, instead of doing a full second traversal of the
> > tree.
> >
> > This makes the second DSDT traversal pass unnecessary as we already have
> > the nodes we're interested in in a linked list.
> 
> The second traversal of the ACPI namespace (it may not be just the
> DSDT at that point to be precise) is not really about _DEP handling.
> In fact, the latter has been added on top of it.
> 
> It is about the PCI enumeration.  Namely, when acpi_pci_root_add()
> runs for the PCI host bridge object in the ACPI namespace, the entire
> device hierarchy below it is walked and all of the ACPI device objects
> corresponding to the PCI devices on the bus are assumed to be present.
> This means that all of the ACPI device objects need to be created in
> the first walk, without binding any ACPI drivers or scan handlers to
> them, and the second walk is to find out what is actually represented
> by those objects.
> 
> It cannot be eliminated in any simple way.

My understanding still remains that this patch does not (or other patches
in this set) change the above. It is just how those nodes are reached:
instead of traversing the entire tree and ignoring the devices that have
already an acpi_device created for them, a linked list of devices of
interest is traversed.

Of course it is possible that I have missed something. The codebase isn't
entirely trivial.

On Tuesday, May 9, 2023 10:49:21 PM CEST Sakari Ailus wrote:
> Hi Rafael,
> 
> Thank you for the review.
> 
> On Tue, May 09, 2023 at 08:06:28PM +0200, Rafael J. Wysocki wrote:
> > On Wed, Mar 29, 2023 at 12:10 PM Sakari Ailus
> > <sakari.ailus@linux.intel.com> wrote:
> > >
> > > Collect the devices with _DEP into a list and continue processing them
> > > after a full traversal, instead of doing a full second traversal of the
> > > tree.
> > >
> > > This makes the second DSDT traversal pass unnecessary as we already have
> > > the nodes we're interested in in a linked list.
> > 
> > The second traversal of the ACPI namespace (it may not be just the
> > DSDT at that point to be precise) is not really about _DEP handling.
> > In fact, the latter has been added on top of it.
> > 
> > It is about the PCI enumeration.  Namely, when acpi_pci_root_add()
> > runs for the PCI host bridge object in the ACPI namespace, the entire
> > device hierarchy below it is walked and all of the ACPI device objects
> > corresponding to the PCI devices on the bus are assumed to be present.
> > This means that all of the ACPI device objects need to be created in
> > the first walk, without binding any ACPI drivers or scan handlers to
> > them, and the second walk is to find out what is actually represented
> > by those objects.
> > 
> > It cannot be eliminated in any simple way.
> 
> My understanding still remains that this patch does not (or other patches
> in this set) change the above. It is just how those nodes are reached:
> instead of traversing the entire tree and ignoring the devices that have
> already an acpi_device created for them, a linked list of devices of
> interest is traversed.
> 
> Of course it is possible that I have missed something. The codebase isn't
> entirely trivial.

You are right and I see what it is about now.

However, the implementation is rather fragile and the list added by the
$subject patch is redundant AFAICS, because all of the objects in it
are also present in acpi_dep_list as consumers (adding an object to
acpi_dep_list as a consumer is necessary for that object to be added to the
new list too).  Of course, there may be multiple acpi_dep_list for the same
consumer object, but it is not a fundamental problem.

So overall I'd prefer to do something like the appended (untested) patch
instead.

---
From: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
Subject: [PATCH] ACPI: scan: Reduce overhead related to devices with dependencies

Notice that all of the objects for which the acpi_scan_check_dep()
return value is greater than 0 are present in acpi_dep_list as consumers
(there may be multiple entries for one object, but that is not a
problem), so after carrying out the initial ACPI namespace walk in which
devices with dependencies are skipped, acpi_bus_scan() can simply walk
acpi_dep_list and enumerate all of the unique consumer objects from
there and their descendants instead of walking the entire target branch
of the ACPI namespace and looking for device objects that have not been
enumerated yet in it.

Because walking acpi_dep_list is generally less overhead than walking
the entire ACPI namespace, use the observation above to reduce the
system initialization overhead related to ACPI, which is particularly
important on large systems.

Signed-off-by: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
---
 drivers/acpi/scan.c     |   71 ++++++++++++++++++++++++++++++++++--------------
 include/acpi/acpi_bus.h |    2 +
 2 files changed, 53 insertions(+), 20 deletions(-)

Index: linux-pm/include/acpi/acpi_bus.h
===================================================================
--- linux-pm.orig/include/acpi/acpi_bus.h
+++ linux-pm/include/acpi/acpi_bus.h
@@ -289,6 +289,8 @@ struct acpi_dep_data {
 	acpi_handle supplier;
 	acpi_handle consumer;
 	bool honor_dep;
+	bool met;
+	bool free_when_met;
 };
 
 /* Performance Management */
Index: linux-pm/drivers/acpi/scan.c
===================================================================
--- linux-pm.orig/drivers/acpi/scan.c
+++ linux-pm/drivers/acpi/scan.c
@@ -2029,8 +2029,6 @@ static u32 acpi_scan_check_dep(acpi_hand
 	return count;
 }
 
-static bool acpi_bus_scan_second_pass;
-
 static acpi_status acpi_bus_check_add(acpi_handle handle, bool check_dep,
 				      struct acpi_device **adev_p)
 {
@@ -2050,10 +2048,8 @@ static acpi_status acpi_bus_check_add(ac
 			return AE_OK;
 
 		/* Bail out if there are dependencies. */
-		if (acpi_scan_check_dep(handle, check_dep) > 0) {
-			acpi_bus_scan_second_pass = true;
+		if (acpi_scan_check_dep(handle, check_dep) > 0)
 			return AE_CTRL_DEPTH;
-		}
 
 		fallthrough;
 	case ACPI_TYPE_ANY:	/* for ACPI_ROOT_OBJECT */
@@ -2311,8 +2307,12 @@ static int acpi_scan_clear_dep(struct ac
 			acpi_dev_put(adev);
 	}
 
-	list_del(&dep->node);
-	kfree(dep);
+	if (dep->free_when_met) {
+		list_del(&dep->node);
+		kfree(dep);
+	} else {
+		dep->met = true;
+	}
 
 	return 0;
 }
@@ -2406,6 +2406,49 @@ struct acpi_device *acpi_dev_get_next_co
 }
 EXPORT_SYMBOL_GPL(acpi_dev_get_next_consumer_dev);
 
+static void acpi_scan_postponed(acpi_handle handle)
+{
+	struct acpi_device *adev = NULL;
+	struct acpi_dep_data *dep, *tmp;
+
+	mutex_lock(&acpi_dep_list_lock);
+
+	list_for_each_entry_safe(dep, tmp, &acpi_dep_list, node) {
+		acpi_handle handle = dep->consumer;
+
+		/*
+		 * Even though the lock is released here, tmp is guaranteed to
+		 * be valid, because none of the list entries following dep is
+		 * marked as "free when met" and so they cannot be deleted.
+		 */
+		mutex_unlock(&acpi_dep_list_lock);
+
+		/*
+		 * In case there are multiple acpi_dep_list entries with the
+		 * same consumer, skip the current entry if the consumer device
+		 * object corresponding to it is present already.
+		 */
+		if (!acpi_fetch_acpi_dev(handle) &&
+		    ACPI_SUCCESS(acpi_bus_check_add(handle, false, &adev))) {
+			acpi_walk_namespace(ACPI_TYPE_ANY, handle, ACPI_UINT32_MAX,
+					    acpi_bus_check_add_2, NULL, NULL,
+					    (void **)&adev);
+			acpi_bus_attach(adev, NULL);
+		}
+
+		mutex_lock(&acpi_dep_list_lock);
+
+		if (dep->met) {
+			list_del(&dep->node);
+			kfree(dep);
+		} else {
+			dep->free_when_met = true;
+		}
+	}
+
+	mutex_unlock(&acpi_dep_list_lock);
+}
+
 /**
  * acpi_bus_scan - Add ACPI device node objects in a given namespace scope.
  * @handle: Root of the namespace scope to scan.
@@ -2424,8 +2467,6 @@ int acpi_bus_scan(acpi_handle handle)
 {
 	struct acpi_device *device = NULL;
 
-	acpi_bus_scan_second_pass = false;
-
 	/* Pass 1: Avoid enumerating devices with missing dependencies. */
 
 	if (ACPI_SUCCESS(acpi_bus_check_add(handle, true, &device)))
@@ -2438,19 +2479,9 @@ int acpi_bus_scan(acpi_handle handle)
 
 	acpi_bus_attach(device, (void *)true);
 
-	if (!acpi_bus_scan_second_pass)
-		return 0;
-
 	/* Pass 2: Enumerate all of the remaining devices. */
 
-	device = NULL;
-
-	if (ACPI_SUCCESS(acpi_bus_check_add(handle, false, &device)))
-		acpi_walk_namespace(ACPI_TYPE_ANY, handle, ACPI_UINT32_MAX,
-				    acpi_bus_check_add_2, NULL, NULL,
-				    (void **)&device);
-
-	acpi_bus_attach(device, NULL);
+	acpi_scan_postponed(handle);
 
 	return 0;
 }