[PATCH 1/4] PCI: optimize pci_bus_get_depth() by enumerating on pci bus hierachy

[Wei Yang <weiyang@linux.vnet.ibm.com>]

Normally, on one pci bus there would be more devices than pci buses. When
calculating the depth of pci bus, it would be more time efficient by
enumerating through the child buses instead of the child devices.

Also by doing so, the code seems more self explaining. Previously, it go
through the pci devices and check whether a bridge introduce a child bus or
not, which needs more background knowledge to understand it.

This patch caculating the depth by enumerating on pci bus hierachy in an
iterative way.

Signed-off-by: Wei Yang <weiyang@linux.vnet.ibm.com>
Reviewed-by: Gavin Shan <shangw@linux.vnet.ibm.com>
Reviewed-by: Ram Pai <linuxram@us.ibm.com>
Reviewed-by: Xiao Guangrong <xiaoguangrong@linux.vnet.ibm.com>
Reviewed-by: Mike Qiu <qiudayu@linux.vnet.ibm.com>
---
 drivers/pci/setup-bus.c |   43 ++++++++++++++++++++++++++++++++-----------
 1 files changed, 32 insertions(+), 11 deletions(-)

diff --git a/drivers/pci/setup-bus.c b/drivers/pci/setup-bus.c
index 16abaaa..b333f73 100644
--- a/drivers/pci/setup-bus.c
+++ b/drivers/pci/setup-bus.c
@@ -1299,22 +1299,43 @@ static void pci_bus_dump_resources(struct pci_bus *bus)
 
 static int __init pci_bus_get_depth(struct pci_bus *bus)
 {
-	int depth = 0;
-	struct pci_dev *dev;
+	int max_depth, depth;
+	struct pci_bus *parent, *curr;
+	struct list_head *node;
 
-	list_for_each_entry(dev, &bus->devices, bus_list) {
-		int ret;
-		struct pci_bus *b = dev->subordinate;
-		if (!b)
-			continue;
+	/* no child? */
+	if (list_empty(&bus->children))
+		return 0;
 
-		ret = pci_bus_get_depth(b);
-		if (ret + 1 > depth)
-			depth = ret + 1;
+	node = bus->children.next;
+	parent = bus;
+	max_depth = depth = 1;
+
+	while (parent) {
+		/* hit the head, go back to parent level */
+		if (node == &parent->children) {
+			node = parent->node.next;
+			parent = parent->parent;
+			depth--;
+			continue;
+		}
+		curr = list_entry(node, struct pci_bus, node);
+		/* depth first */
+		if (!list_empty(&curr->children)) {
+			node = curr->children.next;
+			parent = curr;
+			depth++;
+			if (max_depth < depth)
+				max_depth = depth;
+		}
+		/* no child, go to the sibling */
+		else
+			node = curr->node.next;
 	}
 
-	return depth;
+	return max_depth;
 }
+
 static int __init pci_get_max_depth(void)
 {
 	int depth = 0;
-- 
1.7.5.4