@@ -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)
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(-)