[PATCH 06/11] resource: make find_resource could return just fit resource

[Yinghai Lu <yinghai@kernel.org>]

Find all suitable empty slots and pick one just fit, so we could spare the big
slot for needed ones later.

Signed-off-by: Yinghai Lu <yinghai@kernel.org>
---
 kernel/resource.c |   60 +++++++++++++++++++++++++++++++++++++++++++++++++---
 1 files changed, 56 insertions(+), 4 deletions(-)

diff --git a/kernel/resource.c b/kernel/resource.c
index 41d7050..45ab24d 100644
--- a/kernel/resource.c
+++ b/kernel/resource.c
@@ -435,7 +435,7 @@ static int __find_resource(struct resource *root, struct resource *old,
 			alloc.end = alloc.start + size - 1;
 			if (resource_contains(&avail, &alloc)) {
 				new->start = alloc.start;
-				new->end = alloc.end;
+				new->end = !old ? avail.end : alloc.end;
 				return 0;
 			}
 		}
@@ -450,14 +450,66 @@ next:		if (!this || this->end == root->end)
 	return -EBUSY;
 }
 
+struct avail_resource {
+	struct list_head list;
+	struct resource res;
+};
 /*
  * Find empty slot in the resource tree given range and alignment.
  */
 static int find_resource(struct resource *root, struct resource *new,
 			resource_size_t size,
-			struct resource_constraint  *constraint)
+			struct resource_constraint *constraint, bool fit)
 {
-	return  __find_resource(root, NULL, new, size, constraint);
+	int ret = -1;
+	LIST_HEAD(head);
+	struct avail_resource *avail, *tmp;
+	resource_size_t avail_start = 0, avail_size = -1ULL;
+
+	if (!fit) {
+		ret = __find_resource(root, NULL, new, size, constraint);
+		if (!ret)
+			new->end = new->start + size - 1;
+		return ret;
+	}
+
+again:
+	/* find all suitable ones */
+	avail = kzalloc(sizeof(*avail), GFP_KERNEL);
+	if (!avail)
+		goto out;
+
+	avail->res.start = new->start;
+	avail->res.end = new->end;
+	avail->res.flags = new->flags;
+	ret = __find_resource(root, NULL, &avail->res, size, constraint);
+	if (ret || __request_resource(root, &avail->res)) {
+		ret = -EBUSY;
+		kfree(avail);
+		goto out;
+	}
+	/* add to the list */
+	list_add(&avail->list, &head);
+	goto again;
+
+out:
+	/* pick up the smallest one and delete the list */
+	list_for_each_entry_safe(avail, tmp, &head, list) {
+		if (resource_size(&avail->res) < avail_size) {
+			avail_size = resource_size(&avail->res);
+			avail_start = avail->res.start;
+			ret = 0;
+		}
+		list_del(&avail->list);
+		__release_resource(&avail->res);
+		kfree(avail);
+	}
+
+	if (!ret) {
+		new->start = avail_start;
+		new->end = new->start + size - 1;
+	}
+	return ret;
 }
 
 /**
@@ -550,7 +602,7 @@ static int __allocate_resource(struct resource *root, struct resource *new,
 
 	if (lock)
 		write_lock(&resource_lock);
-	err = find_resource(root, new, size, &constraint);
+	err = find_resource(root, new, size, &constraint, false);
 	if (err >= 0 && __request_resource(root, new))
 		err = -EBUSY;
 	if (lock)
-- 
1.7.7