PCI: allocate space top-down, not bottom-up
v2 cover PCI: allocate space top-down, not bottom-up
When we move PCI devices, we currently allocate space bottom-up, i.e., we look at PCI bus resources in the order we found them, we look at gaps between child resources bottom-up, and we align the new space at the bottom of an available region.
On x86, we move PCI devices more than we used to because we now pay attention to the PCI host bridge windows from ACPI. For example, when we find a device that's outside all the known host bridge windows, we try to move it into a window, and we look for space starting at the bottom.
Windows does similar device moves, but it looks for space top-down rather than bottom-up. Since most machines are better-tested with Windows than Linux, this difference means that Linux is more likely to trip over BIOS bugs in the PCI host bridge window descriptions than Windows is.
We've had several reports of Dell machines where the BIOS leaves the AHCI controller outside the host bridge windows (BIOS bug #1), *and* the lowest host bridge window includes an area that doesn't actually reach PCI (BIOS bug #2). The result is that Windows (which moves AHCI to the top of a window) works fine, while Linux (which moves AHCI to the bottom, buggy, area) doesn't work.
These patches change Linux to allocate space more like Windows does:
1) The x86 pcibios_align_resource() will choose space from the end of an available area, not the beginning.
2) In the generic allocate_resource() path, we'll look for space between existing children from the top, not from the bottom.
3) When pci_bus_alloc_resource() looks for available space, it will start from the highest window, not the first one we found.
This series fixes a 2.6.34 regression that prevents many Dell Precision workstations from booting:
https://bugzilla.kernel.org/show_bug.cgi?id=16228
Changes from v1 to v2:
- Moved check for allocating before the available area from pcibios_align_resource() to find_resource(). Better to do it after the alignment callback is done, and make it generic.
- Fixed pcibios_align_resource() alignment. If we start from the end of the available area, we must align *downward*, not upward.
- Fixed pcibios_align_resource() ISA alias avoidance. Again, since the starting point is the end of the area, we must align downward when we avoid aliased areas.
---
Bjorn Helgaas (4):
resources: ensure alignment callback doesn't allocate below available start x86/PCI: allocate space from the end of a region, not the beginning
resources: allocate space within a region from the top down
PCI: allocate bus resources from the top down
arch/x86/pci/i386.c | 18 ++++++++++++----- drivers/pci/bus.c | 53 ++++++++++++++++++++++++++++++++++++++++++++++----- kernel/resource.c | 50 +++++++++++++++++++++++++++++++----------------- 3 files changed, 92 insertions(+), 29 deletions(-)
PATCH v2 1/4 resources: ensure alignment callback doesn't allocate below available start
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 a location above the available area.
This patch adds a check to make sure the callback doesn't return something *below* the available area, as may happen if the callback tries to allocate top-down.
---
kernel/resource.c | 10 ++++++++-- 1 files changed, 8 insertions(+), 2 deletions(-)
kernel/resource.c +8 -2
@@ -371,6 +371,7 @@ static int find_resource(struct resource *root, struct resource *new, {struct resource *this = root->child;struct resource tmp = *new; +resource_size_t start; tmp.start = root->start;/*
@@ -391,8 +392,13 @@ 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); +if (alignf) { + start =alignf (alignf_data, &tmp, size, align); +if (tmp.start <= start && start <= tmp.end) + tmp.start = start; +else + tmp.start = tmp.end; + }if (tmp.start < tmp.end && tmp.end - tmp.start >= size -1 ) { new->start = tmp.start; new->end = tmp.start + size -1 ;
Re: [PATCH v2 1/4] resources: ensure alignment callback doesn't allocate below available start
Quoted 6 lines · On Fri, 17 Sep 2010 16:32:12 -0600 Bjorn Helgaas <[email protected]> wrote:
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 a location above the available area.
Quoted 6 lines
This patch adds a check to make sure the callback doesn't return something *below* the available area, as may happen if the callback tries to allocate top-down.
Signed-off-by Bjorn Helgaas <[email protected]>---
Applied this series. It's way bigger than I'd like at this point, but it does fix some regressions, so I'll give Linus the option of pulling it in my next pull request. If he declines, we'll put it into -next and tag it for inclusion into the stable series.
Signature · 1 line
Jesse Barnes, Intel Open Source Technology Center
Re: [PATCH v2 1/4] resources: ensure alignment callback doesn't allocate below available start
Quoted 5 lines · Jesse Barnes
Applied this series. It's way bigger than I'd like at this point, but it does fix some regressions, so I'll give Linus the option of pulling it in my next pull request. If he declines, we'll put it into -next and tag it for inclusion into the stable series.
I definitely am not going to pull this series for 2.6.36.
I could possibly take this first one that only prepares for the real change and doesn't actually change anything in itself, but switching around the order of allocations after -rc5 would be crazy. Yes, it may help some people, but we have absolutely no idea who it could hurt. So the whole thing is definitely something for the merge window (and preferably pretty early there too)
Linus
Re: [PATCH v2 1/4] resources: ensure alignment callback doesn't allocate below available start
Quoted 7 lines · On Fri, 24 Sep 2010 11:15:54 -0700 Linus Torvalds…
Quoted 5 lines · Jesse Barnes
Applied this series. It's way bigger than I'd like at this point, but it does fix some regressions, so I'll give Linus the option of pulling it in my next pull request. If he declines, we'll put it into -next and tag it for inclusion into the stable series.
Quoted 8 lines
I definitely am not going to pull this series for 2.6.36.
I could possibly take this first one that only prepares for the real change and doesn't actually change anything in itself, but switching around the order of allocations after -rc5 would be crazy. Yes, it may help some people, but we have absolutely no idea who it could hurt. So the whole thing is definitely something for the merge window (and preferably pretty early there too)
Ok that's settled then (though I was secretly hoping you'd pull & then release 2.6.36 without even compile testing).
It's all ready and queued up, I'll send you a pull request early on so we can get some good test coverage.
Thanks,
Signature · 1 line
Jesse Barnes, Intel Open Source Technology Center
PATCH v2 2/4 x86/PCI: allocate space from the end of a region, not the beginning
In reply to Bjorn HelgaasAllocate from the end of a region, not the beginning.
For example, if we need to allocate 0x800 bytes for a device on bus 0000:00 given these resources:
[mem 0xbff00000-0xdfffffff] PCI Bus 0000:00
[mem 0xc0000000-0xdfffffff] PCI Bus 0000:02the available space at [mem 0xbff00000-0xbfffffff] is passed to the alignment callback (pcibios_align_resource()). Prior to this patch, we would put the new 0x800 byte resource at the beginning of that available space, i.e., at [mem 0xbff00000-0xbff007ff].
With this patch, we put it at the end, at [mem 0xbffff800-0xbfffffff].
Reference: https://bugzilla.kernel.org/show_bug.cgi?id=16228#c41
---
arch/x86/pci/i386.c | 18 ++++++++++++------ 1 files changed, 12 insertions(+), 6 deletions(-)
arch/x86/pci/i386.c +12 -6
@@ -37,6 +37,7 @@#include <asm/pci_x86.h> #include <asm/io_apic.h> +#define ALIGN_DOWN (x, a) ((x) & ~(a - 1))static int skip_isa_ioresource_align (struct pci_dev *dev) {
@@ -65,16 +66,21 @@ pcibios_align_resource(void *data, const struct resource *res, resource_size_t size, resource_size_t align) {struct pci_dev *dev = data; -resource_size_t start = res->start; +resource_size_t start =ALIGN_DOWN (res->end - size +1 , align);if (res->flags &IORESOURCE_IO ) { -if (skip_isa_ioresource_align (dev)) -return start; -if (start &0x300 ) - start = (start +0x3ff ) & ~0x3ff ; + +/* +* If we're avoiding ISA aliases, the largest contiguous I/O +* port space is 256 bytes. Clearing bits 9 and 10 preserves +* all 256-byte and smaller alignments, so the result will +* still be correctly aligned. +*/ +if (!skip_isa_ioresource_align (dev)) + start &= ~0x300 ; }else if (res->flags &IORESOURCE_MEM ) {if (start <BIOS_END ) - start =BIOS_END ; + start = res->end;/* fail; no space */ }return start; }
PATCH v2 3/4 resources: allocate space within a region from the top down
In reply to Bjorn HelgaasAllocate space from the top of a region first, then work downward.
When we allocate space from a resource, we look for gaps between children of the resource. Previously, we looked at gaps from the bottom up. For example, given this:
[mem 0xbff00000-0xf7ffffff] PCI Bus 0000:00
[mem 0xc0000000-0xdfffffff] PCI Bus 0000:02we attempted to allocate from the [mem 0xbff00000-0xbfffffff] gap first, then the [mem 0xe0000000-0xf7ffffff] gap.
With this patch, we allocate from [mem 0xe0000000-0xf7ffffff] first.
Low addresses are generally scarce, so it's better to use high addresses when possible. This follows Windows practice for PCI allocation.
Reference: https://bugzilla.kernel.org/show_bug.cgi?id=16228#c42
---
kernel/resource.c | 40 ++++++++++++++++++++++++---------------- 1 files changed, 24 insertions(+), 16 deletions(-)
kernel/resource.c +24 -16
@@ -358,6 +358,20 @@ int __weak page_is_ram(unsigned long pfn) }/* +* 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. */ static int find_resource(struct resource *root, struct resource *new,
@@ -369,24 +383,18 @@ static int find_resource(struct resource *root, struct resource *new, resource_size_t), void *alignf_data) { -struct resource *this = root->child; +struct resource *this;struct resource tmp = *new;resource_size_t start; - 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. -*/ -if (this && this->start ==0 ) { - tmp.start = this->end +1 ; - this = this->sibling; - } -for (;;) { + tmp.end = root->end; + + this =find_sibling_prev (root,NULL ); +for (;;) {if (this) - tmp.end = this->start -1 ; + tmp.start = this->end +1 ;else - tmp.end = root->end; + tmp.start = root->start;if (tmp.start < min) tmp.start = min;if (tmp.end > max)
@@ -404,10 +412,10 @@ static int find_resource(struct resource *root, struct resource *new, new->end = tmp.start + size -1 ;return 0 ; } -if (!this) +if (!this || this->start == root->start)break ; - tmp.start = this->end +1 ; - this = this->sibling; + tmp.end = this->start -1 ; + this =find_sibling_prev (root, this); }return -EBUSY ; }
PATCH v2 4/4 PCI: allocate bus resources from the top down
In reply to Bjorn HelgaasAllocate space from the highest-address PCI bus resource first, then work downward.
Previously, we looked for space in PCI host bridge windows in the order we discovered the windows. For example, given the following windows (discovered via an ACPI _CRS method):
pci_root PNP0A03:00: host bridge window [mem 0x000a0000-0x000bffff]
pci_root PNP0A03:00: host bridge window [mem 0x000c0000-0x000effff]
pci_root PNP0A03:00: host bridge window [mem 0x000f0000-0x000fffff]
pci_root PNP0A03:00: host bridge window [mem 0xbff00000-0xf7ffffff]
pci_root PNP0A03:00: host bridge window [mem 0xff980000-0xff980fff]
pci_root PNP0A03:00: host bridge window [mem 0xff97c000-0xff97ffff]
pci_root PNP0A03:00: host bridge window [mem 0xfed20000-0xfed9ffff]we attempted to allocate from [mem 0x000a0000-0x000bffff] first, then [mem 0x000c0000-0x000effff], and so on.
With this patch, we allocate from [mem 0xff980000-0xff980fff] first, then [mem 0xff97c000-0xff97ffff], [mem 0xfed20000-0xfed9ffff], etc.
Allocating top-down follows Windows practice, so we're less likely to trip over BIOS defects in the _CRS description.
On the machine above (a Dell T3500), the [mem 0xbff00000-0xbfffffff] region doesn't actually work and is likely a BIOS defect. The symptom is that we move the AHCI controller to 0xbff00000, which leads to "Boot has failed, sleeping forever," a BUG in ahci_stop_engine(), or some other boot failure.
Reference: https://bugzilla.kernel.org/show_bug.cgi?id=16228#c43
Reference: https://bugzilla.redhat.com/show_bug.cgi?id=620313
Reference: https://bugzilla.redhat.com/show_bug.cgi?id=629933
---
drivers/pci/bus.c | 53 ++++++++++++++++++++++++++++++++++++++++++++++++----- 1 files changed, 48 insertions(+), 5 deletions(-)
drivers/pci/bus.c +48 -5
@@ -64,6 +64,49 @@ void pci_bus_remove_resources(struct pci_bus *bus) } } +/* +* Find the highest-address bus resource below the cursor "res". If the +* cursor is NULL, return the highest resource. +*/ +static struct resource *pci_bus_find_resource_prev (struct pci_bus *bus, +unsigned int type, +struct resource *res) +{ +struct resource *r, *prev =NULL ; +int i; + +pci_bus_for_each_resource (bus, r, i) { +if (!r) +continue ; + +if ((r->flags &IORESOURCE_TYPE_BITS ) != type) +continue ; + +/* If this resource is at or past the cursor, skip it */ +if (res) { +if (r == res) +continue ; +if (r->end > res->end) +continue ; +if (r->end == res->end && r->start > res->start) +continue ; + } + +if (!prev) + prev = r; + +/* +* A small resource is higher than a large one that ends at +* the same address. +*/ +if (r->end > prev->end || + (r->end == prev->end && r->start > prev->start)) + prev = r; + } + +return prev; +} +/** * pci_bus_alloc_resource - allocate a resource from a parent bus * @bus: PCI bus
@@ -89,9 +132,10 @@ pci_bus_alloc_resource(struct pci_bus *bus, struct resource *res, resource_size_t), void *alignf_data) { -int i, ret = -ENOMEM ; +int ret = -ENOMEM ;struct resource *r;resource_size_t max =-1 ; +unsigned int type = res->flags &IORESOURCE_TYPE_BITS ; type_mask |=IORESOURCE_IO |IORESOURCE_MEM ;
@@ -99,10 +143,9 @@ pci_bus_alloc_resource(struct pci_bus *bus, struct resource *res,if (!(res->flags &IORESOURCE_MEM_64 )) max =PCIBIOS_MAX_MEM_32 ; -pci_bus_for_each_resource (bus, r, i) { -if (!r) -continue ; - +/* Look for space at highest addresses first */ + r =pci_bus_find_resource_prev (bus, type,NULL ); +for ( ; r; r =pci_bus_find_resource_prev (bus, type, r)) {/* type_mask must match */ if ((res->flags ^ r->flags) & type_mask)continue ;
... for the whole series. However, I definitely want to see the issue of using reserved regions for resource allocation addressed.
-hpa
Added cc: [email protected]
See:
https://patchwork.kernel.org/patch/189182/
https://patchwork.kernel.org/patch/189232/
https://patchwork.kernel.org/patch/189242/
https://patchwork.kernel.org/patch/189252/
Quoted 62 lines · Bjorn Helgaas
When we move PCI devices, we currently allocate space bottom-up, i.e., we look at PCI bus resources in the order we found them, we look at gaps between child resources bottom-up, and we align the new space at the bottom of an available region.
On x86, we move PCI devices more than we used to because we now pay attention to the PCI host bridge windows from ACPI. For example, when we find a device that's outside all the known host bridge windows, we try to move it into a window, and we look for space starting at the bottom.
Windows does similar device moves, but it looks for space top-down rather than bottom-up. Since most machines are better-tested with Windows than Linux, this difference means that Linux is more likely to trip over BIOS bugs in the PCI host bridge window descriptions than Windows is.
We've had several reports of Dell machines where the BIOS leaves the AHCI controller outside the host bridge windows (BIOS bug #1), *and* the lowest host bridge window includes an area that doesn't actually reach PCI (BIOS bug #2). The result is that Windows (which moves AHCI to the top of a window) works fine, while Linux (which moves AHCI to the bottom, buggy, area) doesn't work.
These patches change Linux to allocate space more like Windows does:
1) The x86
pcibios_align_resource()will choose space from the end of an available area, not the beginning.2) In the generic
allocate_resource()path, we'll look for space between existing children from the top, not from the bottom.3) When
pci_bus_alloc_resource()looks for available space, it will start from the highest window, not the first one we found.This series fixes a 2.6.34 regression that prevents many Dell Precision workstations from booting:
https://bugzilla.kernel.org/show_bug.cgi?id=16228Changes from v1 to v2:
- Moved check for allocating before the available area frompcibios_align_resource()tofind_resource(). Better to do it after the alignment callback is done, and make it generic.
- Fixedpcibios_align_resource()alignment. If we start from the end of the available area, we must align *downward*, not upward.
- Fixedpcibios_align_resource()ISA alias avoidance. Again, since the starting point is the end of the area, we must align downward when we avoid aliased areas.---
Bjorn Helgaas (4):
resources: ensure alignment callback doesn't allocate below available start x86/PCI: allocate space from the end of a region, not the beginning
resources: allocate space within a region from the top down
PCI: allocate bus resources from the top downarch/x86/pci/i386.c | 18 ++++++++++++----- drivers/pci/bus.c | 53 ++++++++++++++++++++++++++++++++++++++++++++++----- kernel/resource.c | 50 +++++++++++++++++++++++++++++++----------------- 3 files changed, 92 insertions(+), 29 deletions(-)
Quoted 6 lines · Bjorn Helgaas
Added cc: [email protected]
See:
https://patchwork.kernel.org/patch/189182/
https://patchwork.kernel.org/patch/189232/
https://patchwork.kernel.org/patch/189242/
https://patchwork.kernel.org/patch/189252/
Um, why would -stable want them if they aren't in Linus's tree yet? Please, when they are in his tree, _AND_ have gotten a lot of testing, then email the git commit ids of what you want added to the stable tree to [email protected].
Doing it beforehand like this is a sure way to cause me a lot of work and the patches to be lost.
thanks,
greg k-h
Quoted 8 lines · On Fri, 24 Sep 2010 16:40:20 -0700 Greg KH <[email protected]> wrote:
Quoted 6 lines · Bjorn Helgaas
Added cc: [email protected]
See:
https://patchwork.kernel.org/patch/189182/
https://patchwork.kernel.org/patch/189232/
https://patchwork.kernel.org/patch/189242/
https://patchwork.kernel.org/patch/189252/
Quoted 7 lines
Um, why would -stable want them if they aren't in Linus's tree yet? Please, when they are in his tree, _AND_ have gotten a lot of testing, then email the git commit ids of what you want added to the stable tree to [email protected].
Doing it beforehand like this is a sure way to cause me a lot of work and the patches to be lost.
Yeah sorry. They're queued up in a special branch atm, but will be part of my initial 2.6.37 merge request pull. They're not going into 2.6.36 because they're a bit too invasive for this late in the process.
I don't *think* they'll cause problems (ultimately they should make us behave a bit more like Windows as far as resource allocation goes) so hopefully a merge into stable sometime after the 2.6.37 merge window closes won't be a problem, but you probably don't have a nice way of automating that...
Thanks,
Signature · 1 line
Jesse Barnes, Intel Open Source Technology Center
Quoted 8 lines · Greg KH
Quoted 6 lines · Bjorn Helgaas
Added cc: [email protected]
See:
https://patchwork.kernel.org/patch/189182/
https://patchwork.kernel.org/patch/189232/
https://patchwork.kernel.org/patch/189242/
https://patchwork.kernel.org/patch/189252/
Quoted 7 lines
Um, why would -stable want them if they aren't in Linus's tree yet? Please, when they are in his tree, _AND_ have gotten a lot of testing, then email the git commit ids of what you want added to the stable tree to [email protected].
Doing it beforehand like this is a sure way to cause me a lot of work and the patches to be lost.
Oops, sorry, I'm inexperienced in the ways of -stable. Akpm reminded me tocc:
stable, and I thought he meant now, but he probably meant later. I'll put it on my list for later.
Bjorn
Quoted 14 lines · Bjorn Helgaas
Quoted 13 lines · Greg KH
Quoted 6 lines · Bjorn Helgaas
Added cc: [email protected]
See:
https://patchwork.kernel.org/patch/189182/
https://patchwork.kernel.org/patch/189232/
https://patchwork.kernel.org/patch/189242/
https://patchwork.kernel.org/patch/189252/Um, why would -stable want them if they aren't in Linus's tree yet? Please, when they are in his tree, _AND_ have gotten a lot of testing, then email the git commit ids of what you want added to the stable tree to [email protected].
Quoted 6 lines
Quoted 2 lines
Doing it beforehand like this is a sure way to cause me a lot of work and the patches to be lost.
Oops, sorry, I'm inexperienced in the ways of -stable. Akpm reminded me tocc:
stable, and I thought he meant now, but he probably meant later. I'll put it on my list for later.
Please read the file, Documentation/stable_kernel_rules.txt for how to get stuff into the stable tree.
thanks,
greg k-h