[PATCH] Recurse when searching for empty slots in resources trees

[Andrew Patterson <andrew.patterson@hp.com>]

Recurse when searching for empty slots in resources trees

The function pci_assign_resource() is called to allocate address
ranges for PCI device BARs in the parent bridges resource tree during
hot add operations (such as during physical hot-plug, logical
hot-plug, or PCI error recovery) of a PCI device.  This function in
turn calls find_resource() to see if resources are available, and then
allocate_resource() to insert the resource into the tree. Both of
these functions only check the immediate children and its siblings of
the root resource passed to them.  This algorithm can fail in certain
topologies where a resource is only available further down the
resource tree.

This patch changes find_resources() and allocate_resources() so that
they recursively descend the resource tree instead of just checking the
immediate child and its siblings.

Descendents are checked after the immediate child and its siblings to
maintain as much as possible the existing tree resource layout.

Signed-off-by: Andrew Patterson <andrew.patterson@hp.com>
---

diff --git a/kernel/resource.c b/kernel/resource.c
index ac5f3a3..636c3b0 100644
--- a/kernel/resource.c
+++ b/kernel/resource.c
@@ -301,19 +301,28 @@ static int find_resource(struct resource *root, struct resource *new,
 	struct resource *this = root->child;
 
 	new->start = root->start;
+
 	/*
-	 * Skip past an allocated resource that starts at 0, since the assignment
-	 * of this->start - 1 to new->end below would cause an underflow.
+	 * See if there is room before, after, or in between child
+	 * and/or its siblings.
 	 */
-	if (this && this->start == 0) {
-		new->start = this->end + 1;
-		this = this->sibling;
-	}
 	for(;;) {
-		if (this)
-			new->end = this->start - 1;
-		else
+		if (this) {
 			new->end = root->end;
+			if (new->start + size - 1 < this->start)
+				new->end = new->start + size - 1;
+			else {
+				if (this->sibling) {
+					if (this->sibling->start - this->end >= size - 1) {
+						new->start = this->end + 1;
+						new->end = this->sibling->start - 1;
+					} else
+						goto next;
+				} else
+					new->start = this->end + 1;
+			}
+		}
+
 		if (new->start < min)
 			new->start = min;
 		if (new->end > max)
@@ -327,9 +336,22 @@ static int find_resource(struct resource *root, struct resource *new,
 		}
 		if (!this)
 			break;
+next:
 		new->start = this->end + 1;
 		this = this->sibling;
 	}
+
+	/* See if there is room inside the child or its siblings. */
+	if (root->child) {
+		for (this = root->child; this; this = this->sibling) {
+			if (find_resource(this, new,
+					  size, min, max, align,
+					  alignf, alignf_data) == 0) {
+				return 0;
+			}
+		}
+	}
+
 	return -EBUSY;
 }
 
@@ -352,11 +374,21 @@ int allocate_resource(struct resource *root, struct resource *new,
 		      void *alignf_data)
 {
 	int err;
+	struct resource *parent, *first;
 
 	write_lock(&resource_lock);
 	err = find_resource(root, new, size, min, max, align, alignf, alignf_data);
-	if (err >= 0 && __request_resource(root, new))
-		err = -EBUSY;
+	if (err >= 0) {
+		for (parent = root;; parent = first) {
+			first = __request_resource(parent, new);
+			if (!first)
+				break;
+			if (first == parent) {
+				err = -EBUSY;
+				break;
+			}
+		}
+	}
 	write_unlock(&resource_lock);
 	return err;
 }
@@ -627,6 +659,11 @@ struct resource * __request_region(struct resource *parent,
 			parent = conflict;
 			if (!(conflict->flags & IORESOURCE_BUSY))
 				continue;
+			/* May have a duplicate that is not busy */
+			if (conflict->child) {
+				parent = conflict->child;
+				continue;
+			}
 		}
 
 		/* Uhhuh, that didn't work out.. */