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 982269c..8d3a43a 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;
 		}
 	}