From a9cea017411c95ec789092971f9baaef1f826883 Mon Sep 17 00:00:00 2001 From: Bjorn Helgaas Date: Tue, 26 Oct 2010 15:41:13 -0600 Subject: resources: add a default alignf to simplify find_resource() This removes a test from find_resource(), which is getting cluttered. No functional change. Signed-off-by: Bjorn Helgaas Signed-off-by: Jesse Barnes --- kernel/resource.c | 15 +++++++++++++-- 1 file changed, 13 insertions(+), 2 deletions(-) (limited to 'kernel/resource.c') diff --git a/kernel/resource.c b/kernel/resource.c index 7b36976..7dc8ad2 100644 --- a/kernel/resource.c +++ b/kernel/resource.c @@ -357,6 +357,14 @@ int __weak page_is_ram(unsigned long pfn) return walk_system_ram_range(pfn, 1, NULL, __is_ram) == 1; } +static resource_size_t simple_align_resource(void *data, + const struct resource *avail, + resource_size_t size, + resource_size_t align) +{ + return avail->start; +} + /* * Find empty slot in the resource tree given range and alignment. */ @@ -391,8 +399,8 @@ static int find_resource(struct resource *root, struct resource *new, if (tmp.end > max) tmp.end = max; tmp.start = ALIGN(tmp.start, align); - if (alignf) - tmp.start = alignf(alignf_data, &tmp, size, align); + + tmp.start = alignf(alignf_data, &tmp, size, align); if (tmp.start < tmp.end && tmp.end - tmp.start >= size - 1) { new->start = tmp.start; new->end = tmp.start + size - 1; @@ -428,6 +436,9 @@ int allocate_resource(struct resource *root, struct resource *new, { int err; + if (!alignf) + alignf = simple_align_resource; + write_lock(&resource_lock); err = find_resource(root, new, size, min, max, align, alignf, alignf_data); if (err >= 0 && __request_resource(root, new)) -- cgit v1.1 From 5d6b1fa301b13cc651ee717a9b518124dea2f814 Mon Sep 17 00:00:00 2001 From: Bjorn Helgaas Date: Tue, 26 Oct 2010 15:41:18 -0600 Subject: resources: factor out resource_clip() to simplify find_resource() This factors out the min/max clipping to simplify find_resource(). No functional change. Signed-off-by: Bjorn Helgaas Signed-off-by: Jesse Barnes --- kernel/resource.c | 15 +++++++++++---- 1 file changed, 11 insertions(+), 4 deletions(-) (limited to 'kernel/resource.c') diff --git a/kernel/resource.c b/kernel/resource.c index 7dc8ad2..26e9f25 100644 --- a/kernel/resource.c +++ b/kernel/resource.c @@ -365,6 +365,15 @@ static resource_size_t simple_align_resource(void *data, return avail->start; } +static void resource_clip(struct resource *res, resource_size_t min, + resource_size_t max) +{ + if (res->start < min) + res->start = min; + if (res->end > max) + res->end = max; +} + /* * Find empty slot in the resource tree given range and alignment. */ @@ -394,10 +403,8 @@ static int find_resource(struct resource *root, struct resource *new, tmp.end = this->start - 1; else tmp.end = root->end; - if (tmp.start < min) - tmp.start = min; - if (tmp.end > max) - tmp.end = max; + + resource_clip(&tmp, min, max); tmp.start = ALIGN(tmp.start, align); tmp.start = alignf(alignf_data, &tmp, size, align); -- cgit v1.1 From 6909ba14c25b4db6be2ff89f4fa0fac2d70151a0 Mon Sep 17 00:00:00 2001 From: Bjorn Helgaas Date: Tue, 26 Oct 2010 15:41:23 -0600 Subject: resources: ensure callback doesn't allocate outside available space The alignment callback returns a proposed location, which may have been adjusted to avoid ISA aliases or for other architecture-specific reasons. We already had a check ("tmp.start < tmp.end") to make sure the callback doesn't return an area that extends past the available area. This patch reworks the check to make sure it doesn't return an area that extends either below or above the available area. Signed-off-by: Bjorn Helgaas Signed-off-by: Jesse Barnes --- kernel/resource.c | 16 +++++++++++----- 1 file changed, 11 insertions(+), 5 deletions(-) (limited to 'kernel/resource.c') diff --git a/kernel/resource.c b/kernel/resource.c index 26e9f25..89d5041 100644 --- a/kernel/resource.c +++ b/kernel/resource.c @@ -374,6 +374,11 @@ static void resource_clip(struct resource *res, resource_size_t min, res->end = max; } +static bool resource_contains(struct resource *res1, struct resource *res2) +{ + return res1->start <= res2->start && res1->end >= res2->end; +} + /* * Find empty slot in the resource tree given range and alignment. */ @@ -387,7 +392,7 @@ static int find_resource(struct resource *root, struct resource *new, void *alignf_data) { struct resource *this = root->child; - struct resource tmp = *new; + struct resource tmp = *new, alloc; tmp.start = root->start; /* @@ -407,10 +412,11 @@ static int find_resource(struct resource *root, struct resource *new, resource_clip(&tmp, min, max); tmp.start = ALIGN(tmp.start, align); - tmp.start = alignf(alignf_data, &tmp, size, align); - if (tmp.start < tmp.end && tmp.end - tmp.start >= size - 1) { - new->start = tmp.start; - new->end = tmp.start + size - 1; + alloc.start = alignf(alignf_data, &tmp, size, align); + alloc.end = alloc.start + size - 1; + if (resource_contains(&tmp, &alloc)) { + new->start = alloc.start; + new->end = alloc.end; return 0; } if (!this) -- cgit v1.1 From a1862e31079149a52b6223776228c3aee493d4a7 Mon Sep 17 00:00:00 2001 From: Bjorn Helgaas Date: Tue, 26 Oct 2010 15:41:28 -0600 Subject: resources: handle overflow when aligning start of available area If tmp.start is near ~0, ALIGN(tmp.start) may overflow, which would make us think there's more available space than there really is. We would likely return something that conflicts with a previous resource, which would cause a failure when allocate_resource() requests the newly- allocated region. Reference: https://bugzilla.redhat.com/show_bug.cgi?id=646027 Reported-by: Fabrice Bellet Signed-off-by: Bjorn Helgaas Signed-off-by: Jesse Barnes --- kernel/resource.c | 21 +++++++++++++-------- 1 file changed, 13 insertions(+), 8 deletions(-) (limited to 'kernel/resource.c') diff --git a/kernel/resource.c b/kernel/resource.c index 89d5041..e15b922 100644 --- a/kernel/resource.c +++ b/kernel/resource.c @@ -392,7 +392,7 @@ static int find_resource(struct resource *root, struct resource *new, void *alignf_data) { struct resource *this = root->child; - struct resource tmp = *new, alloc; + struct resource tmp = *new, avail, alloc; tmp.start = root->start; /* @@ -410,14 +410,19 @@ static int find_resource(struct resource *root, struct resource *new, tmp.end = root->end; resource_clip(&tmp, min, max); - tmp.start = ALIGN(tmp.start, align); - alloc.start = alignf(alignf_data, &tmp, size, align); - alloc.end = alloc.start + size - 1; - if (resource_contains(&tmp, &alloc)) { - new->start = alloc.start; - new->end = alloc.end; - return 0; + /* Check for overflow after ALIGN() */ + avail = *new; + avail.start = ALIGN(tmp.start, align); + avail.end = tmp.end; + if (avail.start >= tmp.start) { + alloc.start = alignf(alignf_data, &avail, size, align); + alloc.end = alloc.start + size - 1; + if (resource_contains(&avail, &alloc)) { + new->start = alloc.start; + new->end = alloc.end; + return 0; + } } if (!this) break; -- cgit v1.1 From e7f8567db9a7f6b3151b0b275e245c1cef0d9c70 Mon Sep 17 00:00:00 2001 From: Bjorn Helgaas Date: Tue, 26 Oct 2010 15:41:33 -0600 Subject: resources: support allocating space within a region from the top down Allocate space from the top of a region first, then work downward, if an architecture desires this. When we allocate space from a resource, we look for gaps between children of the resource. Previously, we always looked at gaps from the bottom up. For example, given this: [mem 0xbff00000-0xf7ffffff] PCI Bus 0000:00 [mem 0xbff00000-0xbfffffff] gap -- available [mem 0xc0000000-0xdfffffff] PCI Bus 0000:02 [mem 0xe0000000-0xf7ffffff] gap -- available we attempted to allocate from the [mem 0xbff00000-0xbfffffff] gap first, then the [mem 0xe0000000-0xf7ffffff] gap. With this patch an architecture can choose to allocate from the top gap [mem 0xe0000000-0xf7ffffff] first. We can't do this across the board because iomem_resource.end is initialized to 0xffffffff_ffffffff on 64-bit architectures, and most machines can't address the entire 64-bit physical address space. Therefore, we only allocate top-down if the arch requests it by clearing "resource_alloc_from_bottom". Signed-off-by: Bjorn Helgaas Signed-off-by: Jesse Barnes --- kernel/resource.c | 98 ++++++++++++++++++++++++++++++++++++++++++++++++++++--- 1 file changed, 94 insertions(+), 4 deletions(-) (limited to 'kernel/resource.c') diff --git a/kernel/resource.c b/kernel/resource.c index e15b922..716b680 100644 --- a/kernel/resource.c +++ b/kernel/resource.c @@ -40,6 +40,23 @@ EXPORT_SYMBOL(iomem_resource); static DEFINE_RWLOCK(resource_lock); +/* + * By default, we allocate free space bottom-up. The architecture can request + * top-down by clearing this flag. The user can override the architecture's + * choice with the "resource_alloc_from_bottom" kernel boot option, but that + * should only be a debugging tool. + */ +int resource_alloc_from_bottom = 1; + +static __init int setup_alloc_from_bottom(char *s) +{ + printk(KERN_INFO + "resource: allocating from bottom-up; please report a bug\n"); + resource_alloc_from_bottom = 1; + return 0; +} +early_param("resource_alloc_from_bottom", setup_alloc_from_bottom); + static void *r_next(struct seq_file *m, void *v, loff_t *pos) { struct resource *p = v; @@ -380,7 +397,74 @@ static bool resource_contains(struct resource *res1, struct resource *res2) } /* + * Find the resource before "child" in the sibling list of "root" children. + */ +static struct resource *find_sibling_prev(struct resource *root, struct resource *child) +{ + struct resource *this; + + for (this = root->child; this; this = this->sibling) + if (this->sibling == child) + return this; + + return NULL; +} + +/* + * Find empty slot in the resource tree given range and alignment. + * This version allocates from the end of the root resource first. + */ +static int find_resource_from_top(struct resource *root, struct resource *new, + resource_size_t size, resource_size_t min, + resource_size_t max, resource_size_t align, + resource_size_t (*alignf)(void *, + const struct resource *, + resource_size_t, + resource_size_t), + void *alignf_data) +{ + struct resource *this; + struct resource tmp, avail, alloc; + + tmp.start = root->end; + tmp.end = root->end; + + this = find_sibling_prev(root, NULL); + for (;;) { + if (this) { + if (this->end < root->end) + tmp.start = this->end + 1; + } else + tmp.start = root->start; + + resource_clip(&tmp, min, max); + + /* Check for overflow after ALIGN() */ + avail = *new; + avail.start = ALIGN(tmp.start, align); + avail.end = tmp.end; + if (avail.start >= tmp.start) { + alloc.start = alignf(alignf_data, &avail, size, align); + alloc.end = alloc.start + size - 1; + if (resource_contains(&avail, &alloc)) { + new->start = alloc.start; + new->end = alloc.end; + return 0; + } + } + + if (!this || this->start == root->start) + break; + + tmp.end = this->start - 1; + this = find_sibling_prev(root, this); + } + return -EBUSY; +} + +/* * Find empty slot in the resource tree given range and alignment. + * This version allocates from the beginning of the root resource first. */ static int find_resource(struct resource *root, struct resource *new, resource_size_t size, resource_size_t min, @@ -396,14 +480,15 @@ static int find_resource(struct resource *root, struct resource *new, tmp.start = root->start; /* - * Skip past an allocated resource that starts at 0, since the assignment - * of this->start - 1 to tmp->end below would cause an underflow. + * Skip past an allocated resource that starts at 0, since the + * assignment of this->start - 1 to tmp->end below would cause an + * underflow. */ if (this && this->start == 0) { tmp.start = this->end + 1; this = this->sibling; } - for(;;) { + for (;;) { if (this) tmp.end = this->start - 1; else @@ -424,8 +509,10 @@ static int find_resource(struct resource *root, struct resource *new, return 0; } } + if (!this) break; + tmp.start = this->end + 1; this = this->sibling; } @@ -458,7 +545,10 @@ int allocate_resource(struct resource *root, struct resource *new, alignf = simple_align_resource; write_lock(&resource_lock); - err = find_resource(root, new, size, min, max, align, alignf, alignf_data); + if (resource_alloc_from_bottom) + err = find_resource(root, new, size, min, max, align, alignf, alignf_data); + else + err = find_resource_from_top(root, new, size, min, max, align, alignf, alignf_data); if (err >= 0 && __request_resource(root, new)) err = -EBUSY; write_unlock(&resource_lock); -- cgit v1.1