[PATCH v3 0/6] PCI: allocate space top-down, not bottom-up

[PATCH v3 0/6] PCI: allocate space top-down, not bottom-up

[Bjorn Helgaas]

    This revision is to address two problems found by Horst H. von Brand while
    testing the v2 patches in Fedora:
      https://bugzilla.redhat.com/show_bug.cgi?id=637647 .
    On his machine, we don't use _CRS by default, and the BIOS left some bridge
    windows disabled.

    Problem 1: When we assigned space for the windows, we started at the top
    and allocated [mem 0xffffffffffe00000-0xffffffffffffffff], which is
    obviously useless because the CPU doesn't support physical addresses that
    large.

    Problem 2: Subsequent allocations failed because I made an error in
    find_resource().  We look for available space from [child->end + 1 to
    root->end], and if the last child ends exactly at 0xffffffffffffffff, we
    wrap around and start from zero.

    I made the top-down allocation conditional on ARCH_HAS_TOP_DOWN_ALLOC
    because problem #1 requires per-arch changes to fix.


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 v2 to v3:
    - Updated iomem_resource.end to reflect the end of usable physical address
      space.  Otherwise, we might allocate right up to 0xffffffff_ffffffff,
      which isn't usable.
    - Make allocate_resource() change conditional on ARCH_HAS_TOP_DOWN_ALLOC.
      Without arch-specific changes like the above, it's too dangerous to
      make this change for everybody at once.
    - Fix 64-bit wraparound in find_resource().  If the last child happened
      to end at ~0, we computed the highest available space as [child->end + 1,
      root->end], which makes us think the available space started at 0,
      which makes us return space that may already be allocated.

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 (6):
      resources: ensure alignment callback doesn't allocate below available start
      resources: allocate space within a region from the top down
      PCI: allocate bus resources from the top down
      x86/PCI: allocate space from the end of a region, not the beginning
      x86: update iomem_resource end based on CPU physical address capabilities
      x86: allocate space within a region top-down


 arch/x86/include/asm/io.h |    1 +
 arch/x86/kernel/setup.c   |    1 +
 arch/x86/pci/i386.c       |   18 +++++++---
 drivers/pci/bus.c         |   53 +++++++++++++++++++++++++++---
 kernel/resource.c         |   80 ++++++++++++++++++++++++++++++++++++++++++++-
 5 files changed, 140 insertions(+), 13 deletions(-)

[PATCH v3 1/6] resources: ensure alignment callback doesn't allocate below available start

[Bjorn Helgaas]

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.

Signed-off-by: Bjorn Helgaas <bjorn.helgaas@hp.com>
---

 kernel/resource.c |   10 ++++++++--
 1 files changed, 8 insertions(+), 2 deletions(-)


diff --git a/kernel/resource.c b/kernel/resource.c
index 7b36976..ace2269 100644
--- a/kernel/resource.c
+++ b/kernel/resource.c
@@ -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;

[PATCH v3 2/6] resources: allocate space within a region from the top down

[Bjorn Helgaas]

Allocate space from the top of a region first, then work downward,
if an architecture desires this.

I think it's too dangerous to do this across the board, because
iomem_resource.end is initialized to -1, which is 0xffffffff_ffffffff
on 64-bit architectures, and most machines can't address the entire
64-bit physical address space.  So this patch is only effective if the
architecture defines ARCH_HAS_TOP_DOWN_ALLOC.

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 0xc0000000-0xdfffffff] PCI Bus 0000:02

we attempted to allocate from the [mem 0xbff00000-0xbfffffff] gap first,
then the [mem 0xe0000000-0xf7ffffff] gap.

With this patch, if the architecture defines ARCH_HAS_TOP_DOWN_ALLOC,
we allocate from [mem 0xe0000000-0xf7ffffff] first.

Signed-off-by: Bjorn Helgaas <bjorn.helgaas@hp.com>
---

 kernel/resource.c |   70 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 files changed, 70 insertions(+), 0 deletions(-)


diff --git a/kernel/resource.c b/kernel/resource.c
index ace2269..9218e8e 100644
--- a/kernel/resource.c
+++ b/kernel/resource.c
@@ -357,8 +357,77 @@ int __weak page_is_ram(unsigned long pfn)
 	return walk_system_ram_range(pfn, 1, NULL, __is_ram) == 1;
 }
 
+#ifdef ARCH_HAS_TOP_DOWN_ALLOC
+/*
+ * 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(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 = *new;
+	resource_size_t start;
+
+	tmp.start = root->end;
+	tmp.end = root->end;
+
+	this = find_sibling_prev(root, NULL);
+	for (;;) {
+		if (this && this->end < root->end)
+			tmp.start = this->end + 1;
+		else
+			tmp.start = root->start;
+		if (tmp.start < min)
+			tmp.start = min;
+		if (tmp.end > max)
+			tmp.end = max;
+		tmp.start = ALIGN(tmp.start, 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;
+			return 0;
+		}
+		if (!this || this->start == root->start)
+			break;
+		tmp.end = this->start - 1;
+		this = find_sibling_prev(root, this);
+	}
+	return -EBUSY;
+}
+
+#else
+
+/*
+ * 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,
@@ -411,6 +480,7 @@ static int find_resource(struct resource *root, struct resource *new,
 	}
 	return -EBUSY;
 }
+#endif
 
 /**
  * allocate_resource - allocate empty slot in the resource tree given range & alignment

[PATCH v3 3/6] PCI: allocate bus resources from the top down

[Bjorn Helgaas]

Allocate 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
Reported-by: Brian Bloniarz <phunge0@hotmail.com>
Reported-and-tested-by: Stefan Becker <chemobejk@gmail.com>
Reported-by: Denys Vlasenko <dvlasenk@redhat.com>
Signed-off-by: Bjorn Helgaas <bjorn.helgaas@hp.com>
---

 drivers/pci/bus.c |   53 ++++++++++++++++++++++++++++++++++++++++++++++++-----
 1 files changed, 48 insertions(+), 5 deletions(-)


diff --git a/drivers/pci/bus.c b/drivers/pci/bus.c
index 7f0af0e..172bf26 100644
--- a/drivers/pci/bus.c
+++ b/drivers/pci/bus.c
@@ -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;

[PATCH v3 4/6] x86/PCI: allocate space from the end of a region, not the beginning

[Bjorn Helgaas]

Allocate 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:02

the 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
Signed-off-by: Bjorn Helgaas <bjorn.helgaas@hp.com>
---

 arch/x86/pci/i386.c |   18 ++++++++++++------
 1 files changed, 12 insertions(+), 6 deletions(-)


diff --git a/arch/x86/pci/i386.c b/arch/x86/pci/i386.c
index 5525309..fe866c8 100644
--- a/arch/x86/pci/i386.c
+++ b/arch/x86/pci/i386.c
@@ -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 v3 5/6] x86: update iomem_resource end based on CPU physical address capabilities

[Bjorn Helgaas]

The iomem_resource map reflects the available physical address space.
We statically initialize the end to -1, i.e., 0xffffffff_ffffffff, but
of course we can only use as much as the CPU can address.

This patch updates the end based on the CPU capabilities, so we don't
mistakenly allocate space that isn't usable, as we're likely to do when
allocating from the top-down.

Signed-off-by: Bjorn Helgaas <bjorn.helgaas@hp.com>
---

 arch/x86/kernel/setup.c |    1 +
 1 files changed, 1 insertions(+), 0 deletions(-)


diff --git a/arch/x86/kernel/setup.c b/arch/x86/kernel/setup.c
index c3a4fbb..922b5a1 100644
--- a/arch/x86/kernel/setup.c
+++ b/arch/x86/kernel/setup.c
@@ -788,6 +788,7 @@ void __init setup_arch(char **cmdline_p)
 
 	x86_init.oem.arch_setup();
 
+	iomem_resource.end = (1ULL << boot_cpu_data.x86_phys_bits) - 1;
 	setup_memory_map();
 	parse_setup_data();
 	/* update the e820_saved too */

[PATCH v3 6/6] x86: allocate space within a region top-down

[Bjorn Helgaas]

Request that allocate_resource() use available space from high addresses
first, rather than the default of using low addresses first.

The most common place this makes a difference is when we move or assign
new PCI device resources.  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
Signed-off-by: Bjorn Helgaas <bjorn.helgaas@hp.com>
---

 arch/x86/include/asm/io.h |    1 +
 1 files changed, 1 insertions(+), 0 deletions(-)


diff --git a/arch/x86/include/asm/io.h b/arch/x86/include/asm/io.h
index 30a3e97..6cc02c4 100644
--- a/arch/x86/include/asm/io.h
+++ b/arch/x86/include/asm/io.h
@@ -35,6 +35,7 @@
   */
 
 #define ARCH_HAS_IOREMAP_WC
+#define ARCH_HAS_TOP_DOWN_ALLOC
 
 #include <linux/string.h>
 #include <linux/compiler.h>

Re: [PATCH v3 4/6] x86/PCI: allocate space from the end of a region, not the beginning

[H. Peter Anvin]

On 10/13/2010 09:15 AM, Bjorn Helgaas wrote:
>  
> +#define ALIGN_DOWN(x, a)	((x) & ~(a - 1))
> -	resource_size_t start = res->start;
> +	resource_size_t start = ALIGN_DOWN(res->end - size + 1, align);
>  

Use round_down() here instead of inventing yet another macro?

In all other respects:

Reviewed-by: H. Peter Anvin <hpa@linux.intel.com>

	-hpa

Re: [PATCH v3 4/6] x86/PCI: allocate space from the end of a region, not the beginning

[Bjorn Helgaas]

On Wednesday, October 13, 2010 03:27:58 pm H. Peter Anvin wrote:
> On 10/13/2010 09:15 AM, Bjorn Helgaas wrote:
> >  
> > +#define ALIGN_DOWN(x, a)	((x) & ~(a - 1))
> > -	resource_size_t start = res->start;
> > +	resource_size_t start = ALIGN_DOWN(res->end - size + 1, align);
> >  
> 
> Use round_down() here instead of inventing yet another macro?

Thanks!  I searched for something, but I missed round_down().

Bjorn

Re: [PATCH v3 2/6] resources: allocate space within a region from the top down

[Bjorn Helgaas]

On Wednesday, October 13, 2010 04:19:42 pm Linus Torvalds wrote:
> Hmmm.. Instead of that top-down #define, how about making the allocation
> pattern be a flag in the resource (possibly just the root, but perhaps
> per-resource? )
> 
> That sounds much more flexible, and less ugly than that #ifdef. Perhaps more
> importantly, it would allow us to do the whole allocation order dynamically,
> which would be really good if it turns out to not work on all setups. That
> way we could at least have a kernel command line option that we can ask
> people to test, rather than have them have to recompile the whole kernel.

I like the backout switch idea a lot.  I'm not sure it's worth burning a
bit in the resource flags because I hope we can choose bottom-up vs.
top-down choice once per boot, not per-resource, and treat cases where
we need bottom-up as bugs to be fixed.

Anyway, I'll rework this and you can see what you think.

Bjorn

> On Oct 13, 2010 9:16 AM, "Bjorn Helgaas" <bjorn.helgaas@hp.com> wrote:
> >
> > Allocate space from the top of a region first, then work downward,
> > if an architecture desires this.
> >
> > I think it's too dangerous to do this across the board, because
> > iomem_resource.end is initialized to -1, which is 0xffffffff_ffffffff
> > on 64-bit architectures, and most machines can't address the entire
> > 64-bit physical address space. So this patch is only effective if the
> > architecture defines ARCH_HAS_TOP_DOWN_ALLOC.
> >
> > 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 0xc0000000-0xdfffffff] PCI Bus 0000:02
> >
> > we attempted to allocate from the [mem 0xbff00000-0xbfffffff] gap first,
> > then the [mem 0xe0000000-0xf7ffffff] gap.
> >
> > With this patch, if the architecture defines ARCH_HAS_TOP_DOWN_ALLOC,
> > we allocate from [mem 0xe0000000-0xf7ffffff] first.
> >
> > Signed-off-by: Bjorn Helgaas <bjorn.helgaas@hp.com>
> > ---
> >
> > kernel/resource.c | 70
> +++++++++++++++++++++++++++++++++++++++++++++++++++++
> > 1 files changed, 70 insertions(+), 0 deletions(-)
> >
> >
> > diff --git a/kernel/resource.c b/kernel/resource.c
> > index ace2269..9218e8e 100644
> > --- a/kernel/resource.c
> > +++ b/kernel/resource.c
> > @@ -357,8 +357,77 @@ int __weak page_is_ram(unsigned long pfn)
> > return walk_system_ram_range(pfn, 1, NULL, __is_ram) == 1;
> > }
> >
> > +#ifdef ARCH_HAS_TOP_DOWN_ALLOC
> > +/*
> > + * 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(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 = *new;
> > + resource_size_t start;
> > +
> > + tmp.start = root->end;
> > + tmp.end = root->end;
> > +
> > + this = find_sibling_prev(root, NULL);
> > + for (;;) {
> > + if (this && this->end < root->end)
> > + tmp.start = this->end + 1;
> > + else
> > + tmp.start = root->start;
> > + if (tmp.start < min)
> > + tmp.start = min;
> > + if (tmp.end > max)
> > + tmp.end = max;
> > + tmp.start = ALIGN(tmp.start, 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;
> > + return 0;
> > + }
> > + if (!this || this->start == root->start)
> > + break;
> > + tmp.end = this->start - 1;
> > + this = find_sibling_prev(root, this);
> > + }
> > + return -EBUSY;
> > +}
> > +
> > +#else
> > +
> > +/*
> > + * 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,
> > @@ -411,6 +480,7 @@ static int find_resource(struct resource *root, struct
> resource *new,
> > }
> > return -EBUSY;
> > }
> > +#endif
> >
> > /**
> > * allocate_resource - allocate empty slot in the resource tree given range
> & alignment
> >
>