ACPICA: Performance enhancement for namespace search and access

This change enhances the performance of namespace searches and
walks by adding a backpointer to the parent in each namespace
node. On large namespaces, this change can improve overall ACPI
performance by up to 9X.  Adding a pointer to each namespace node
increases the overall size of the internal namespace by about 5%,
since each namespace entry usually consists of both a namespace
node and an ACPI operand object.

Signed-off-by: Alexey Starikovskiy <astarikovskiy@suse.de>
Signed-off-by: Bob Moore <robert.moore@intel.com>
Signed-off-by: Lin Ming <ming.m.lin@intel.com>
Signed-off-by: Len Brown <len.brown@intel.com>

1 files changed, 25 insertions, 49 deletions

diff --git a/drivers/acpi/acpica/nsalloc.c b/drivers/acpi/acpica/nsalloc.c
index 982269c1fa48..8d3a43a061ab 100644
--- a/drivers/acpi/acpica/nsalloc.c
+++ b/drivers/acpi/acpica/nsalloc.c
@@ -159,7 +159,7 @@ void acpi_ns_remove_node(struct acpi_namespace_node *node)
 
         ACPI_FUNCTION_TRACE_PTR(ns_remove_node, node);
 
-        parent_node = acpi_ns_get_parent_node(node);
+        parent_node = node->parent;
 
         prev_node = NULL;
         next_node = parent_node->child;
@@ -168,29 +168,20 @@ void acpi_ns_remove_node(struct acpi_namespace_node *node)
 
         while (next_node != node) {
                 prev_node = next_node;
-                next_node = prev_node->peer;
+                next_node = next_node->peer;
         }
 
         if (prev_node) {
 
                 /* Node is not first child, unlink it */
 
-                prev_node->peer = next_node->peer;
-                if (next_node->flags & ANOBJ_END_OF_PEER_LIST) {
-                        prev_node->flags |= ANOBJ_END_OF_PEER_LIST;
-                }
+                prev_node->peer = node->peer;
         } else {
-                /* Node is first child (has no previous peer) */
-
-                if (next_node->flags & ANOBJ_END_OF_PEER_LIST) {
-
-                        /* No peers at all */
-
-                        parent_node->child = NULL;
-                } else {        /* Link peer list to parent */
-
-                        parent_node->child = next_node->peer;
-                }
+                /*
+                 * Node is first child (has no previous peer).
+                 * Link peer list to parent
+                 */
+                parent_node->child = node->peer;
         }
 
         /* Delete the node and any attached objects */
@@ -238,23 +229,20 @@ void acpi_ns_install_node(struct acpi_walk_state *walk_state, struct acpi_namesp
 
         /* Link the new entry into the parent and existing children */
 
+        node->peer = NULL;
+        node->parent = parent_node;
         child_node = parent_node->child;
+
         if (!child_node) {
                 parent_node->child = node;
-                node->flags |= ANOBJ_END_OF_PEER_LIST;
-                node->peer = parent_node;
         } else {
-                while (!(child_node->flags & ANOBJ_END_OF_PEER_LIST)) {
+                /* Add node to the end of the peer list */
+
+                while (child_node->peer) {
                         child_node = child_node->peer;
                 }
 
                 child_node->peer = node;
-
-                /* Clear end-of-list flag */
-
-                child_node->flags &= ~ANOBJ_END_OF_PEER_LIST;
-                node->flags |= ANOBJ_END_OF_PEER_LIST;
-                node->peer = parent_node;
         }
 
         /* Init the new entry */
@@ -288,9 +276,8 @@ void acpi_ns_install_node(struct acpi_walk_state *walk_state, struct acpi_namesp
 
 void acpi_ns_delete_children(struct acpi_namespace_node *parent_node)
 {
-        struct acpi_namespace_node *child_node;
         struct acpi_namespace_node *next_node;
-        u8 flags;
+        struct acpi_namespace_node *node_to_delete;
 
         ACPI_FUNCTION_TRACE_PTR(ns_delete_children, parent_node);
 
@@ -298,37 +285,26 @@ void acpi_ns_delete_children(struct acpi_namespace_node *parent_node)
                 return_VOID;
         }
 
-        /* If no children, all done! */
-
-        child_node = parent_node->child;
-        if (!child_node) {
-                return_VOID;
-        }
-
         /* Deallocate all children at this level */
 
-        do {
-
-                /* Get the things we need */
-
-                next_node = child_node->peer;
-                flags = child_node->flags;
+        next_node = parent_node->child;
+        while (next_node) {
 
                 /* Grandchildren should have all been deleted already */
 
-                if (child_node->child) {
+                if (next_node->child) {
                         ACPI_ERROR((AE_INFO, "Found a grandchild! P=%p C=%p",
-                                    parent_node, child_node));
+                                    parent_node, next_node));
                 }
 
                 /*
                  * Delete this child node and move on to the next child in the list.
                  * No need to unlink the node since we are deleting the entire branch.
                  */
-                acpi_ns_delete_node(child_node);
-                child_node = next_node;
-
-        } while (!(flags & ANOBJ_END_OF_PEER_LIST));
+                node_to_delete = next_node;
+                next_node = next_node->peer;
+                acpi_ns_delete_node(node_to_delete);
+        };
 
         /* Clear the parent's child pointer */
 
@@ -405,7 +381,7 @@ void acpi_ns_delete_namespace_subtree(struct acpi_namespace_node *parent_node)
 
                         /* Move up the tree to the grandparent */
 
-                        parent_node = acpi_ns_get_parent_node(parent_node);
+                        parent_node = parent_node->parent;
                 }
         }
 
@@ -510,7 +486,7 @@ void acpi_ns_delete_namespace_by_owner(acpi_owner_id owner_id)
 
                         /* Move up the tree to the grandparent */
 
-                        parent_node = acpi_ns_get_parent_node(parent_node);
+                        parent_node = parent_node->parent;
                 }
         }