[PATCH -v12 00/15] PCI: allocate pci bus num range for unassigned bridge busn

[PATCH -v12 00/15] PCI: allocate pci bus num range for unassigned bridge busn

[Yinghai Lu]

busn_res already in next. and this patchset will
will try to allocate busn range from the tree

could be found at:
        git://git.kernel.org/pub/scm/linux/kernel/git/yinghai/linux-yinghai.git for-pci-busn-alloc

-v2: according to Jesse, split to more small patches.
-v3: address some request from Bjorn. like make use %pR for busn_res debug print
        out, and move the comment change with code change.
-v4: fixes the problem about rescan that Bjorn found.
-v5: add /proc/iobusn that is requested by Bjorn.
     remove old workaround from pciehp.
     add rescan_bridge for pci bridge in /sys
-v6: remove global iobusn_resource, and every root bus's busn_res will be root
     of children buses' busn_res.
     pc cardbus change is tested by pcmcia maintainter.
-v7: remove pci_scan_root_bus_max requested by Bjorn and Jesse.
-v8: rebase on top other patches with arch/x86/pci/bus_numa.c changes
     also only include busn_res related changes.
-v9: Add busn into pci_root_info, and add it to resources list and pass it
     to pci_create_root_bus.
-v11: convert busn_res probe to generic probe_resource with resource lock holding
     add more strict checking about not scaned peer bridges.
-v12: updated after busn_resource changes.

Yinghai Lu (15):
  resources: Split out __allocate_resource()
  resources: Add probe_resource()
  resources: Replace registered resource in tree.
  PCI: Add pci_bus_extend/shrink_top()
  PCI: Probe safe range that we can use for unassigned bridge.
  PCI: Add pci_bus_replace_busn_res()
  PCI: Allocate bus range instead of use max blindly
  PCI: Strict checking of valid range for bridge
  PCI: Kill pci_fixup_parent_subordinate_busnr()
  PCI: Seperate child bus scanning to two passes overall
  pcmcia: Remove workaround for fixing pci parent bus subordinate
  PCI: Double checking setting for bus register and bus struct.
  PCI, pciehp: Remove not needed bus number range checking
  PCI: More strict checking of valid range for bridge
  PCI: Don't shrink too much for hotplug bridge

 drivers/pci/hotplug-pci.c     |   12 +--
 drivers/pci/probe.c           |  351 +++++++++++++++++++++++++++++++----------
 drivers/pcmcia/yenta_socket.c |   75 ---------
 include/linux/ioport.h        |    8 +
 kernel/resource.c             |  200 +++++++++++++++++++++++-
 5 files changed, 472 insertions(+), 174 deletions(-)

-- 
1.7.7

[PATCH -v12 01/15] resources: Split out __allocate_resource()

[Yinghai Lu]

It will take bool lock, so we could use it in other functions that
hold the resource lock already.

Signed-off-by: Yinghai Lu <yinghai@kernel.org>
Cc: Andrew Morton <akpm@linux-foundation.org>
---
 kernel/resource.c |   26 +++++++++++++++++++++-----
 1 files changed, 21 insertions(+), 5 deletions(-)

diff --git a/kernel/resource.c b/kernel/resource.c
index dc8b477..3f6e522 100644
--- a/kernel/resource.c
+++ b/kernel/resource.c
@@ -521,14 +521,14 @@ out:
  * @alignf: alignment function, optional, called if not NULL
  * @alignf_data: arbitrary data to pass to the @alignf function
  */
-int allocate_resource(struct resource *root, struct resource *new,
+static int __allocate_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)
+		      void *alignf_data, bool lock)
 {
 	int err;
 	struct resource_constraint constraint;
@@ -542,19 +542,35 @@ int allocate_resource(struct resource *root, struct resource *new,
 	constraint.alignf = alignf;
 	constraint.alignf_data = alignf_data;
 
-	if ( new->parent ) {
+	if (new->parent && lock) {
 		/* resource is already allocated, try reallocating with
 		   the new constraints */
 		return reallocate_resource(root, new, size, &constraint);
 	}
 
-	write_lock(&resource_lock);
+	if (lock)
+		write_lock(&resource_lock);
 	err = find_resource(root, new, size, &constraint);
 	if (err >= 0 && __request_resource(root, new))
 		err = -EBUSY;
-	write_unlock(&resource_lock);
+	if (lock)
+		write_unlock(&resource_lock);
 	return err;
 }
+int allocate_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)
+{
+	bool lock = true;
+
+	return __allocate_resource(root, new, size, min, max, align,
+				   alignf, alignf_data, lock);
+}
 
 EXPORT_SYMBOL(allocate_resource);
 
-- 
1.7.7

[PATCH -v12 02/15] resources: Add probe_resource()

[Yinghai Lu]

It is changed from busn_res only version, because Bjorn found that version
was not holding resource_lock.
Even it may be ok for busn_res not holding resource_lock.
It would be better to have it to be generic and use lock and we may
use it for other resources.

probe_resource() will try to find specified size or more in parent bus.
If can not find current parent resource, and it will try to expand parents
top.
If still can not find that specified on top, it will try to reduce target size
until find one.

It will return 0, if it find any resource that could be used.

Returned resource is registered in the tree.
So caller may need to use replace_resource to put real resource in tree.

-v3: remove two parameters that is for debug purpose.
-v4: fix stop_flags checking.
-v5: adjust stop_flags checking position to avoid not needed calling
	into allocate_resource().

Signed-off-by: Yinghai Lu <yinghai@kernel.org>
Cc: Andrew Morton <akpm@linux-foundation.org>
---
 include/linux/ioport.h |    7 ++
 kernel/resource.c      |  149 ++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 156 insertions(+), 0 deletions(-)

diff --git a/include/linux/ioport.h b/include/linux/ioport.h
index 589e0e7..8292e8b 100644
--- a/include/linux/ioport.h
+++ b/include/linux/ioport.h
@@ -156,6 +156,13 @@ extern int allocate_resource(struct resource *root, struct resource *new,
 						       resource_size_t,
 						       resource_size_t),
 			     void *alignf_data);
+void resource_shrink_parents_top(struct resource *b_res,
+				 long size, struct resource *parent_res);
+struct device;
+int probe_resource(struct resource *b_res,
+			struct resource *busn_res,
+			resource_size_t needed_size, struct resource **p,
+			int skip_nr, int limit, int flags);
 struct resource *lookup_resource(struct resource *root, resource_size_t start);
 int adjust_resource(struct resource *res, resource_size_t start,
 		    resource_size_t size);
diff --git a/kernel/resource.c b/kernel/resource.c
index 3f6e522..d5d9aef 100644
--- a/kernel/resource.c
+++ b/kernel/resource.c
@@ -980,6 +980,155 @@ void __release_region(struct resource *parent, resource_size_t start,
 }
 EXPORT_SYMBOL(__release_region);
 
+static void __resource_extend_parents_top(struct resource *b_res,
+		 long size, struct resource *parent_res)
+{
+	struct resource *res = b_res;
+
+	if (!size)
+		return;
+
+	while (res && res != parent_res) {
+		res->end += size;
+		res = res->parent;
+	}
+}
+
+void resource_shrink_parents_top(struct resource *b_res,
+		 long size, struct resource *parent_res)
+{
+	write_lock(&resource_lock);
+	__resource_extend_parents_top(b_res, -size, parent_res);
+	write_unlock(&resource_lock);
+}
+
+static resource_size_t __find_res_top_free_size(struct resource *res,
+						 int skip_nr)
+{
+	resource_size_t n_size;
+	struct resource tmp_res;
+
+	/*
+	 *   find out free number below res->end that we can use.
+	 *	res->start to res->start + skip_nr - 1 can not be used.
+	 */
+	n_size = resource_size(res);
+	if (n_size <= skip_nr)
+		return 0;
+
+	n_size -= skip_nr;
+	memset(&tmp_res, 0, sizeof(struct resource));
+	while (n_size > 0) {
+		int ret;
+
+		ret = __allocate_resource(res, &tmp_res, n_size,
+			res->end - n_size + skip_nr, res->end,
+			1, NULL, NULL, false, false);
+		if (ret == 0) {
+			__release_resource(&tmp_res);
+			break;
+		}
+		n_size--;
+	}
+
+	return n_size;
+}
+
+/**
+ * probe_resource - Probe resource in parent resource.
+ * @b_res: parent resource descriptor
+ * @busn_res: return probed resource
+ * @needed_size: target size
+ * @p: pointer to farest parent that we extend the top
+ * @skip_nr: number in b_res start that we need to skip.
+ * @limit: local boundary
+ * @stop_flags: flags for stopping extend parent res
+ *
+ * will try to allocate resource in b_res, if can not find the range
+ *  will try to extend parent resources' top.
+ * if still can not make it, will reduce needed_size.
+ */
+int probe_resource(struct resource *b_res,
+			 struct resource *busn_res,
+			 resource_size_t needed_size, struct resource **p,
+			 int skip_nr, int limit, int stop_flags)
+{
+	int ret = -ENOMEM;
+	resource_size_t n_size;
+	struct resource *parent_res = NULL;
+	resource_size_t tmp = b_res->end + 1;
+
+again:
+	/*
+	 * We first try to allocate biggest range in b_res that
+	 *  we can use in b_res directly.
+	 *  we also need to skip skip_nr from start of b_res.
+	 */
+	n_size = resource_size(b_res);
+	if (n_size > skip_nr)
+		n_size -= skip_nr;
+	else
+		n_size = 0;
+	memset(busn_res, 0, sizeof(struct resource));
+	while (n_size >= needed_size) {
+		ret = allocate_resource(b_res, busn_res, n_size,
+				b_res->start + skip_nr, b_res->end,
+				1, NULL, NULL);
+		if (!ret)
+			return ret;
+		n_size--;
+	}
+
+	/* Try to extend the top of parent resources to meet needed_size */
+	write_lock(&resource_lock);
+
+	/* b_res could be root bus resource and can not be extended */
+	if (b_res->flags & stop_flags)
+		goto reduce_needed_size;
+
+	/* find out free range under top at first */
+	n_size = __find_res_top_free_size(b_res, skip_nr);
+	/* can not extend cross local boundary */
+	if ((limit - b_res->end) < (needed_size - n_size))
+		goto reduce_needed_size;
+
+	/* Probe extended range above top */
+	memset(busn_res, 0, sizeof(struct resource));
+	parent_res = b_res->parent;
+	while (parent_res && !(parent_res->flags & stop_flags)) {
+		ret = __allocate_resource(parent_res, busn_res,
+			 needed_size - n_size,
+			 tmp, tmp + needed_size - n_size - 1,
+			 1, NULL, NULL, false, false);
+		if (!ret) {
+			/* save parent_res, we need it as stopper later */
+			*p = parent_res;
+
+			/* prepare busn_res for return */
+			__release_resource(busn_res);
+			busn_res->start -= n_size;
+
+			/* extend parent resources top */
+			__resource_extend_parents_top(b_res,
+					 needed_size - n_size, parent_res);
+			__request_resource(b_res, busn_res);
+
+			write_unlock(&resource_lock);
+			return ret;
+		}
+		parent_res = parent_res->parent;
+	}
+
+reduce_needed_size:
+	write_unlock(&resource_lock);
+	/* ret must not be 0 here */
+	needed_size--;
+	if (needed_size)
+		goto again;
+
+	return ret;
+}
+
 /*
  * Managed region resource
  */
-- 
1.7.7

[PATCH -v12 03/15] resources: Replace registered resource in tree.

[Yinghai Lu]

We could have one resource inserted in tree at first during probing.

Later we need to put real resource into the tree.

So try to hold the lock to swap them.

-v2: make it more generic to handle old one with children or no parent.

Signed-off-by: Yinghai Lu <yinghai@kernel.org>
Cc: Andrew Morton <akpm@linux-foundation.org>
---
 include/linux/ioport.h |    1 +
 kernel/resource.c      |   25 +++++++++++++++++++++++++
 2 files changed, 26 insertions(+), 0 deletions(-)

diff --git a/include/linux/ioport.h b/include/linux/ioport.h
index 8292e8b..cbf3480 100644
--- a/include/linux/ioport.h
+++ b/include/linux/ioport.h
@@ -163,6 +163,7 @@ int probe_resource(struct resource *b_res,
 			struct resource *busn_res,
 			resource_size_t needed_size, struct resource **p,
 			int skip_nr, int limit, int flags);
+void replace_resource(struct resource *old_res, struct resource *new_res);
 struct resource *lookup_resource(struct resource *root, resource_size_t start);
 int adjust_resource(struct resource *res, resource_size_t start,
 		    resource_size_t size);
diff --git a/kernel/resource.c b/kernel/resource.c
index d5d9aef..8da0e76 100644
--- a/kernel/resource.c
+++ b/kernel/resource.c
@@ -1129,6 +1129,31 @@ reduce_needed_size:
 	return ret;
 }
 
+/* replace old with new in the resource tree */
+void replace_resource(struct resource *old, struct resource *new)
+{
+	struct resource *parent, *tmp, *p;
+
+	write_lock(&resource_lock);
+	new->start = old->start;
+	new->end = old->end;
+	new->flags = old->flags;
+
+	p = old->child;
+	while (p) {
+		tmp = p;
+		p = p->sibling;
+		__release_resource(tmp);
+		__request_resource(new, tmp);
+	}
+	parent = old->parent;
+	if (parent) {
+		__release_resource(old);
+		__request_resource(parent, new);
+	}
+	write_unlock(&resource_lock);
+}
+
 /*
  * Managed region resource
  */
-- 
1.7.7

[PATCH -v12 04/15] PCI: Add pci_bus_extend/shrink_top()

[Yinghai Lu]

Extend or shrink bus and parent buses top (subordinate)

Extended range is verified safe range, and stop at recorded parent_res.

-v2: Remove busn_res change, it is updated in other function.

Signed-off-by: Yinghai Lu <yinghai@kernel.org>
---
 drivers/pci/probe.c |   28 ++++++++++++++++++++++++++++
 1 files changed, 28 insertions(+), 0 deletions(-)

diff --git a/drivers/pci/probe.c b/drivers/pci/probe.c
index cd06c84..44c42ae 100644
--- a/drivers/pci/probe.c
+++ b/drivers/pci/probe.c
@@ -689,6 +689,34 @@ static void pci_fixup_parent_subordinate_busnr(struct pci_bus *child, int max)
 	}
 }
 
+static void __devinit pci_bus_extend_top(struct pci_bus *parent,
+		 long size, struct resource *parent_res)
+{
+	struct resource *res;
+
+	if (!size)
+		return;
+
+	while (parent) {
+		res = &parent->busn_res;
+		if (res == parent_res)
+			break;
+		pci_write_config_byte(parent->self, PCI_SUBORDINATE_BUS,
+					 parent->busn_res.end);
+		dev_printk(KERN_DEBUG, &parent->dev,
+				"busn_res: %s %02lx to %pR\n",
+				(size > 0) ? "extended" : "shrunk",
+				abs(size), res);
+		parent = parent->parent;
+	}
+}
+
+static void __devinit pci_bus_shrink_top(struct pci_bus *parent,
+		 long size, struct resource *parent_res)
+{
+	pci_bus_extend_top(parent, -size, parent_res);
+}
+
 /*
  * If it's a bridge, configure it and scan the bus behind it.
  * For CardBus bridges, we don't scan behind as the devices will
-- 
1.7.7

[PATCH -v12 05/15] PCI: Probe safe range that we can use for unassigned bridge.

[Yinghai Lu]

Try to allocate from parent bus busn_res. If we can not find any big enough,
will try to extend parent bus top. even the extending is through allocating,
after allocating will pad the range to parent buses top.

When extending happens, We will record the parent_res, so could use it as
stopper for really extend/shrink top later.

-v4: Use generic probe_resource()

Signed-off-by: Yinghai Lu <yinghai@kernel.org>
---
 drivers/pci/probe.c |   28 ++++++++++++++++++++++++++++
 1 files changed, 28 insertions(+), 0 deletions(-)

diff --git a/drivers/pci/probe.c b/drivers/pci/probe.c
index 44c42ae..75bca6f 100644
--- a/drivers/pci/probe.c
+++ b/drivers/pci/probe.c
@@ -717,6 +717,34 @@ static void __devinit pci_bus_shrink_top(struct pci_bus *parent,
 	pci_bus_extend_top(parent, -size, parent_res);
 }
 
+static int __devinit pci_bridge_probe_busn_res(struct pci_bus *bus,
+			 struct pci_dev *dev, struct resource *busn_res,
+			 resource_size_t needed_size, struct resource **p)
+{
+	int ret;
+	int old_size = resource_size(&bus->busn_res);
+	int skip_nr = 1;
+	int domain_limit = 0xff;
+	int stop_flags = IORESOURCE_PCI_FIXED;
+
+	ret = probe_resource(&bus->busn_res, busn_res, needed_size,
+			p, skip_nr, domain_limit, stop_flags);
+
+	if (ret)
+		return ret;
+
+	busn_res->flags = IORESOURCE_BUS;
+
+	if (*p) {
+		/* extend parent bus top*/
+		int new_size = resource_size(&bus->busn_res);
+
+		pci_bus_extend_top(bus, new_size - old_size, *p);
+	}
+
+	return ret;
+}
+
 /*
  * If it's a bridge, configure it and scan the bus behind it.
  * For CardBus bridges, we don't scan behind as the devices will
-- 
1.7.7

[PATCH -v12 06/15] PCI: Add pci_bus_replace_busn_res()

[Yinghai Lu]

It will use replace_resource to put bus's busn_res in the resource tree.

Signed-off-by: Yinghai Lu <yinghai@kernel.org>
---
 drivers/pci/probe.c |   15 +++++++++++++++
 1 files changed, 15 insertions(+), 0 deletions(-)

diff --git a/drivers/pci/probe.c b/drivers/pci/probe.c
index 75bca6f..7498502 100644
--- a/drivers/pci/probe.c
+++ b/drivers/pci/probe.c
@@ -660,6 +660,21 @@ static struct pci_bus *pci_alloc_child_bus(struct pci_bus *parent,
 	return child;
 }
 
+static void pci_bus_replace_busn_res(struct pci_bus *b,
+					 struct resource *busn_res)
+{
+	struct resource *res = &b->busn_res;
+
+	/* busn_res must be registered already*/
+	if (!busn_res->parent)
+		return;
+
+	replace_resource(busn_res, res);
+
+	dev_printk(KERN_DEBUG, &b->dev, "busn_res: %pR is updated under %pR\n",
+			res, res->parent);
+}
+
 struct pci_bus *__ref pci_add_new_bus(struct pci_bus *parent, struct pci_dev *dev, int busnr)
 {
 	struct pci_bus *child;
-- 
1.7.7

[PATCH -v12 07/15] PCI: Allocate bus range instead of use max blindly

[Yinghai Lu]

Every bus have extra busn_res, and linked them together under root bus busn_res

When need to find usable bus number range, try probe it.

To avoid falling to small hole in the middle, we try from 8 spare bus.
If can not find 8 or more in the middle, will try to append 8 on top later.
then if can not append, will try to find 7 from the middle, then will try to append 7 on top.
then if can not append, will try to find 6 from the middle...

For cardbus will only find 4 spare.

If extend from top, at last will shrink back to really needed range...

-v4: fix checking with pci rescan. Found by Bjorn.
-v5: Use update bridge probe busn_res function and replace_resource

Signed-off-by: Yinghai Lu <yinghai@kernel.org>
---
 drivers/pci/probe.c |  100 ++++++++++++++++++++++++++++-----------------------
 1 files changed, 55 insertions(+), 45 deletions(-)

diff --git a/drivers/pci/probe.c b/drivers/pci/probe.c
index 7498502..1cae8fe 100644
--- a/drivers/pci/probe.c
+++ b/drivers/pci/probe.c
@@ -638,9 +638,8 @@ static struct pci_bus *pci_alloc_child_bus(struct pci_bus *parent,
 	 * Set up the primary, secondary and subordinate
 	 * bus numbers.
 	 */
-	child->number = child->busn_res.start = busnr;
+	child->number = busnr;
 	child->primary = parent->busn_res.start;
-	child->busn_res.end = 0xff;
 
 	if (!bridge)
 		return child;
@@ -774,10 +773,11 @@ int __devinit pci_scan_bridge(struct pci_bus *bus, struct pci_dev *dev, int max,
 {
 	struct pci_bus *child;
 	int is_cardbus = (dev->hdr_type == PCI_HEADER_TYPE_CARDBUS);
-	u32 buses, i, j = 0;
+	u32 buses;
 	u16 bctl;
 	u8 primary, secondary, subordinate;
 	int broken = 0;
+	struct resource *parent_res = NULL;
 
 	pci_read_config_dword(dev, PCI_PRIMARY_BUS, &buses);
 	primary = buses & 0xFF;
@@ -794,10 +794,11 @@ int __devinit pci_scan_bridge(struct pci_bus *bus, struct pci_dev *dev, int max,
 
 	/* Check if setup is sensible at all */
 	if (!pass &&
-	    (primary != bus->number || secondary <= bus->number)) {
-		dev_dbg(&dev->dev, "bus configuration invalid, reconfiguring\n");
+	    (primary != bus->number || secondary <= bus->number))
 		broken = 1;
-	}
+
+	if (broken)
+		dev_dbg(&dev->dev, "bus configuration invalid, reconfiguring\n");
 
 	/* Disable MasterAbortMode during probing to avoid reporting
 	   of bus errors (in some architectures) */ 
@@ -842,6 +843,11 @@ int __devinit pci_scan_bridge(struct pci_bus *bus, struct pci_dev *dev, int max,
 		 * We need to assign a number to this bus which we always
 		 * do in the second pass.
 		 */
+		long shrink_size;
+		struct resource busn_res;
+		int ret = -ENOMEM;
+		int old_max = max;
+
 		if (!pass) {
 			if (pcibios_assign_all_busses() || broken)
 				/* Temporarily disable forwarding of the
@@ -858,21 +864,42 @@ int __devinit pci_scan_bridge(struct pci_bus *bus, struct pci_dev *dev, int max,
 		/* Clear errors */
 		pci_write_config_word(dev, PCI_STATUS, 0xffff);
 
-		/* Prevent assigning a bus number that already exists.
-		 * This can happen when a bridge is hot-plugged, so in
-		 * this case we only re-scan this bus. */
-		child = pci_find_bus(pci_domain_nr(bus), max+1);
-		if (!child) {
-			child = pci_add_new_bus(bus, dev, ++max);
-			if (!child)
-				goto out;
-			pci_bus_insert_busn_res(child, max, 0xff);
+		if (dev->subordinate) {
+			/* We get here only for cardbus */
+			child = dev->subordinate;
+			if  (!is_cardbus)
+				dev_warn(&dev->dev,
+				 "rescan scaned bridge as broken one again ?");
+
+			goto out;
 		}
+		/*
+		 * For CardBus bridges, we leave 4 bus numbers
+		 * as cards with a PCI-to-PCI bridge can be
+		 * inserted later.
+		 * other just allocate 8 bus to avoid we fall into
+		 *  small hole in the middle.
+		 */
+		ret = pci_bridge_probe_busn_res(bus, dev, &busn_res,
+				is_cardbus ? (CARDBUS_RESERVE_BUSNR + 1) : 8,
+				&parent_res);
+
+		if (ret != 0)
+			goto out;
+
+		child = pci_add_new_bus(bus, dev, busn_res.start);
+		if (!child)
+			goto out;
+
+		pci_bus_replace_busn_res(child, &busn_res);
+
 		buses = (buses & 0xff000000)
 		      | ((unsigned int)(child->primary)     <<  0)
 		      | ((unsigned int)(child->busn_res.start)   <<  8)
 		      | ((unsigned int)(child->busn_res.end) << 16);
 
+		max = child->busn_res.end;
+
 		/*
 		 * yenta.c forces a secondary latency timer of 176.
 		 * Copy that behaviour here.
@@ -903,43 +930,26 @@ int __devinit pci_scan_bridge(struct pci_bus *bus, struct pci_dev *dev, int max,
 			 * the real value of max.
 			 */
 			pci_fixup_parent_subordinate_busnr(child, max);
+
 		} else {
-			/*
-			 * For CardBus bridges, we leave 4 bus numbers
-			 * as cards with a PCI-to-PCI bridge can be
-			 * inserted later.
-			 */
-			for (i=0; i<CARDBUS_RESERVE_BUSNR; i++) {
-				struct pci_bus *parent = bus;
-				if (pci_find_bus(pci_domain_nr(bus),
-							max+i+1))
-					break;
-				while (parent->parent) {
-					if ((!pcibios_assign_all_busses()) &&
-					    (parent->busn_res.end > max) &&
-					    (parent->busn_res.end <= max+i)) {
-						j = 1;
-					}
-					parent = parent->parent;
-				}
-				if (j) {
-					/*
-					 * Often, there are two cardbus bridges
-					 * -- try to leave one valid bus number
-					 * for each one.
-					 */
-					i /= 2;
-					break;
-				}
-			}
-			max += i;
 			pci_fixup_parent_subordinate_busnr(child, max);
 		}
 		/*
 		 * Set the subordinate bus number to its real value.
 		 */
-		pci_bus_update_busn_res_end(child, max);
+		shrink_size = (int)child->busn_res.end - max;
 		pci_write_config_byte(dev, PCI_SUBORDINATE_BUS, max);
+		pci_bus_update_busn_res_end(child, max);
+
+		/* shrink some back, if we extend top before */
+		if (!is_cardbus && (shrink_size > 0) && parent_res) {
+			resource_shrink_parents_top(&bus->busn_res, shrink_size,
+						 parent_res);
+			pci_bus_shrink_top(bus, shrink_size, parent_res);
+		}
+
+		if (old_max > max)
+			max = old_max;
 	}
 
 	sprintf(child->name,
-- 
1.7.7

[PATCH -v12 08/15] PCI: Strict checking of valid range for bridge

[Yinghai Lu]

Children bridges busn range should be allocated from parent bus range.

So we could avoid overlapping between sibling bridges on same bus.

Signed-off-by: Yinghai Lu <yinghai@kernel.org>
---
 drivers/pci/probe.c |   27 +++++++++++++++++++++++++++
 1 files changed, 27 insertions(+), 0 deletions(-)

diff --git a/drivers/pci/probe.c b/drivers/pci/probe.c
index 1cae8fe..98a9911 100644
--- a/drivers/pci/probe.c
+++ b/drivers/pci/probe.c
@@ -759,6 +759,28 @@ static int __devinit pci_bridge_probe_busn_res(struct pci_bus *bus,
 	return ret;
 }
 
+static int __devinit pci_bridge_check_busn_broken(struct pci_bus *bus,
+				struct pci_dev *dev,
+				int secondary, int subordinate)
+{
+	int ret;
+	struct resource busn_res;
+
+	memset(&busn_res, 0, sizeof(struct resource));
+	dev_printk(KERN_DEBUG, &dev->dev,
+		 "check if busn %02x-%02x is in busn_res: %pR\n",
+		 secondary, subordinate, &bus->busn_res);
+	ret = allocate_resource(&bus->busn_res, &busn_res,
+			 (subordinate - secondary + 1),
+			 secondary, subordinate,
+			 1, NULL, NULL);
+	if (ret)
+		return 1;
+
+	release_resource(&busn_res);
+
+	return 0;
+}
 /*
  * If it's a bridge, configure it and scan the bus behind it.
  * For CardBus bridges, we don't scan behind as the devices will
@@ -797,6 +819,11 @@ int __devinit pci_scan_bridge(struct pci_bus *bus, struct pci_dev *dev, int max,
 	    (primary != bus->number || secondary <= bus->number))
 		broken = 1;
 
+	/* more strict checking */
+	if (!pass && !broken && !dev->subordinate)
+		broken = pci_bridge_check_busn_broken(bus, dev,
+						   secondary, subordinate);
+
 	if (broken)
 		dev_dbg(&dev->dev, "bus configuration invalid, reconfiguring\n");
 
-- 
1.7.7

[PATCH -v12 09/15] PCI: Kill pci_fixup_parent_subordinate_busnr()

[Yinghai Lu]

Now we can safely extend parent top and shrink them by probing them.

Don't need that anymore.

Signed-off-by: Yinghai Lu <yinghai@kernel.org>
---
 drivers/pci/probe.c |   32 --------------------------------
 1 files changed, 0 insertions(+), 32 deletions(-)

diff --git a/drivers/pci/probe.c b/drivers/pci/probe.c
index 98a9911..d558316 100644
--- a/drivers/pci/probe.c
+++ b/drivers/pci/probe.c
@@ -687,22 +687,6 @@ struct pci_bus *__ref pci_add_new_bus(struct pci_bus *parent, struct pci_dev *de
 	return child;
 }
 
-static void pci_fixup_parent_subordinate_busnr(struct pci_bus *child, int max)
-{
-	struct pci_bus *parent = child->parent;
-
-	/* Attempts to fix that up are really dangerous unless
-	   we're going to re-assign all bus numbers. */
-	if (!pcibios_assign_all_busses())
-		return;
-
-	while (parent->parent && parent->busn_res.end < max) {
-		parent->busn_res.end = max;
-		pci_write_config_byte(parent->self, PCI_SUBORDINATE_BUS, max);
-		parent = parent->parent;
-	}
-}
-
 static void __devinit pci_bus_extend_top(struct pci_bus *parent,
 		 long size, struct resource *parent_res)
 {
@@ -943,23 +927,7 @@ int __devinit pci_scan_bridge(struct pci_bus *bus, struct pci_dev *dev, int max,
 
 		if (!is_cardbus) {
 			child->bridge_ctl = bctl;
-			/*
-			 * Adjust subordinate busnr in parent buses.
-			 * We do this before scanning for children because
-			 * some devices may not be detected if the bios
-			 * was lazy.
-			 */
-			pci_fixup_parent_subordinate_busnr(child, max);
-			/* Now we can scan all subordinate buses... */
 			max = pci_scan_child_bus(child);
-			/*
-			 * now fix it up again since we have found
-			 * the real value of max.
-			 */
-			pci_fixup_parent_subordinate_busnr(child, max);
-
-		} else {
-			pci_fixup_parent_subordinate_busnr(child, max);
 		}
 		/*
 		 * Set the subordinate bus number to its real value.
-- 
1.7.7

[PATCH -v12 10/15] PCI: Seperate child bus scanning to two passes overall

[Yinghai Lu]

In extreme case: Two bridges are properly setup.
       bridge A
               bridge AA
               bridge AB
       bridge B
	       bridge BA
	       bridge BB
   but AA, AB are not setup properly.
   bridge A has small range, and bridge AB could need more, when do the
       first pass0 for bridge A, it will do pass0 and pass1 for AA and AB,
	during that process, it will extend range of A for AB blindly.
	because bridge B is not registered yet.
       that could overlap range that is used by bridge B.

Right way should be:
       do pass0 for all good bridges at first.
So we could do pass0 for bridge B before pass1 for bridge AB.

Signed-off-by: Yinghai Lu <yinghai@kernel.org>
---
 drivers/pci/probe.c |   50 ++++++++++++++++++++++++++++++++++----------------
 1 files changed, 34 insertions(+), 16 deletions(-)

diff --git a/drivers/pci/probe.c b/drivers/pci/probe.c
index d558316..e77f58d 100644
--- a/drivers/pci/probe.c
+++ b/drivers/pci/probe.c
@@ -765,6 +765,9 @@ static int __devinit pci_bridge_check_busn_broken(struct pci_bus *bus,
 
 	return 0;
 }
+
+static unsigned int __devinit __pci_scan_child_bus(struct pci_bus *bus,
+						 int pass);
 /*
  * If it's a bridge, configure it and scan the bus behind it.
  * For CardBus bridges, we don't scan behind as the devices will
@@ -821,11 +824,10 @@ int __devinit pci_scan_bridge(struct pci_bus *bus, struct pci_dev *dev, int max,
 	    !is_cardbus && !broken) {
 		unsigned int cmax;
 		/*
-		 * Bus already configured by firmware, process it in the first
-		 * pass and just note the configuration.
+		 * Bus already configured by firmware, still process it in two
+		 * passes in extreme case like two adjaced bridges have children
+		 * bridges that are not setup properly.
 		 */
-		if (pass)
-			goto out;
 
 		/*
 		 * If we already got to this bus through a different bridge,
@@ -844,7 +846,7 @@ int __devinit pci_scan_bridge(struct pci_bus *bus, struct pci_dev *dev, int max,
 			child->bridge_ctl = bctl;
 		}
 
-		cmax = pci_scan_child_bus(child);
+		cmax = __pci_scan_child_bus(child, pass);
 		if (cmax > max)
 			max = cmax;
 		if (child->busn_res.end > max)
@@ -1662,12 +1664,13 @@ void pcie_bus_configure_settings(struct pci_bus *bus, u8 mpss)
 }
 EXPORT_SYMBOL_GPL(pcie_bus_configure_settings);
 
-unsigned int __devinit pci_scan_child_bus(struct pci_bus *bus)
+static unsigned int __devinit __pci_scan_child_bus(struct pci_bus *bus,
+						 int pass)
 {
-	unsigned int devfn, pass, max = bus->busn_res.start;
+	unsigned int devfn, max = bus->busn_res.start;
 	struct pci_dev *dev;
 
-	dev_dbg(&bus->dev, "scanning bus\n");
+	dev_dbg(&bus->dev, "scanning bus pass %d\n", pass);
 
 	/* Go find them, Rover! */
 	for (devfn = 0; devfn < 0x100; devfn += 8)
@@ -1681,18 +1684,16 @@ unsigned int __devinit pci_scan_child_bus(struct pci_bus *bus)
 	 * all PCI-to-PCI bridges on this bus.
 	 */
 	if (!bus->is_added) {
-		dev_dbg(&bus->dev, "fixups for bus\n");
+		dev_dbg(&bus->dev, "fixups for bus pass %d\n", pass);
 		pcibios_fixup_bus(bus);
 		if (pci_is_root_bus(bus))
 			bus->is_added = 1;
 	}
 
-	for (pass=0; pass < 2; pass++)
-		list_for_each_entry(dev, &bus->devices, bus_list) {
-			if (dev->hdr_type == PCI_HEADER_TYPE_BRIDGE ||
-			    dev->hdr_type == PCI_HEADER_TYPE_CARDBUS)
-				max = pci_scan_bridge(bus, dev, max, pass);
-		}
+	list_for_each_entry(dev, &bus->devices, bus_list)
+		if (dev->hdr_type == PCI_HEADER_TYPE_BRIDGE ||
+		    dev->hdr_type == PCI_HEADER_TYPE_CARDBUS)
+			max = pci_scan_bridge(bus, dev, max, pass);
 
 	/*
 	 * We've scanned the bus and so we know all about what's on
@@ -1701,7 +1702,24 @@ unsigned int __devinit pci_scan_child_bus(struct pci_bus *bus)
 	 *
 	 * Return how far we've got finding sub-buses.
 	 */
-	dev_dbg(&bus->dev, "bus scan returning with max=%02x\n", max);
+	dev_dbg(&bus->dev, "bus scan returning with max=%02x pass %d\n",
+			max, pass);
+
+	return max;
+}
+
+unsigned int __devinit pci_scan_child_bus(struct pci_bus *bus)
+{
+	int pass;
+	unsigned int max = 0, tmp;
+
+	for (pass = 0; pass < 2;  pass++) {
+		tmp = __pci_scan_child_bus(bus, pass);
+
+		if (tmp > max)
+			max = tmp;
+	}
+
 	return max;
 }
 
-- 
1.7.7

[PATCH -v12 11/15] pcmcia: Remove workaround for fixing pci parent bus subordinate

[Yinghai Lu]

Now pci busn allocation code is there, and it will preallocate bus number and it
will make sure parent buses subordinate is right.

So remove workaround here.

Signed-off-by: Yinghai Lu <yinghai@kernel.org>
Tested-by: Dominik Brodowski <linux@dominikbrodowski.net>
Cc: Rusty Russell <rusty@rustcorp.com.au>
Cc: Mauro Carvalho Chehab <mchehab@redhat.com>
Cc: linux-pcmcia@lists.infradead.org
---
 drivers/pcmcia/yenta_socket.c |   75 -----------------------------------------
 1 files changed, 0 insertions(+), 75 deletions(-)

diff --git a/drivers/pcmcia/yenta_socket.c b/drivers/pcmcia/yenta_socket.c
index 667678d..7e42bb4 100644
--- a/drivers/pcmcia/yenta_socket.c
+++ b/drivers/pcmcia/yenta_socket.c
@@ -1064,79 +1064,6 @@ static void yenta_config_init(struct yenta_socket *socket)
 	config_writew(socket, CB_BRIDGE_CONTROL, bridge);
 }
 
-/**
- * yenta_fixup_parent_bridge - Fix subordinate bus# of the parent bridge
- * @cardbus_bridge: The PCI bus which the CardBus bridge bridges to
- *
- * Checks if devices on the bus which the CardBus bridge bridges to would be
- * invisible during PCI scans because of a misconfigured subordinate number
- * of the parent brige - some BIOSes seem to be too lazy to set it right.
- * Does the fixup carefully by checking how far it can go without conflicts.
- * See http://bugzilla.kernel.org/show_bug.cgi?id=2944 for more information.
- */
-static void yenta_fixup_parent_bridge(struct pci_bus *cardbus_bridge)
-{
-	struct list_head *tmp;
-	unsigned char upper_limit;
-	/*
-	 * We only check and fix the parent bridge: All systems which need
-	 * this fixup that have been reviewed are laptops and the only bridge
-	 * which needed fixing was the parent bridge of the CardBus bridge:
-	 */
-	struct pci_bus *bridge_to_fix = cardbus_bridge->parent;
-
-	/* Check bus numbers are already set up correctly: */
-	if (bridge_to_fix->busn_res.end >= cardbus_bridge->busn_res.end)
-		return; /* The subordinate number is ok, nothing to do */
-
-	if (!bridge_to_fix->parent)
-		return; /* Root bridges are ok */
-
-	/* stay within the limits of the bus range of the parent: */
-	upper_limit = bridge_to_fix->parent->busn_res.end;
-
-	/* check the bus ranges of all silbling bridges to prevent overlap */
-	list_for_each(tmp, &bridge_to_fix->parent->children) {
-		struct pci_bus *silbling = pci_bus_b(tmp);
-		/*
-		 * If the silbling has a higher secondary bus number
-		 * and it's secondary is equal or smaller than our
-		 * current upper limit, set the new upper limit to
-		 * the bus number below the silbling's range:
-		 */
-		if (silbling->busn_res.start > bridge_to_fix->busn_res.end
-		    && silbling->busn_res.start <= upper_limit)
-			upper_limit = silbling->busn_res.start - 1;
-	}
-
-	/* Show that the wanted subordinate number is not possible: */
-	if (cardbus_bridge->busn_res.end > upper_limit)
-		dev_printk(KERN_WARNING, &cardbus_bridge->dev,
-			   "Upper limit for fixing this "
-			   "bridge's parent bridge: #%02x\n", upper_limit);
-
-	/* If we have room to increase the bridge's subordinate number, */
-	if (bridge_to_fix->busn_res.end < upper_limit) {
-
-		/* use the highest number of the hidden bus, within limits */
-		unsigned char subordinate_to_assign =
-			min_t(int, cardbus_bridge->busn_res.end, upper_limit);
-
-		dev_printk(KERN_INFO, &bridge_to_fix->dev,
-			   "Raising subordinate bus# of parent "
-			   "bus (#%02x) from #%02x to #%02x\n",
-			   bridge_to_fix->number,
-			   (int)bridge_to_fix->busn_res.end, subordinate_to_assign);
-
-		/* Save the new subordinate in the bus struct of the bridge */
-		bridge_to_fix->busn_res.end = subordinate_to_assign;
-
-		/* and update the PCI config space with the new subordinate */
-		pci_write_config_byte(bridge_to_fix->self,
-			PCI_SUBORDINATE_BUS, bridge_to_fix->busn_res.end);
-	}
-}
-
 /*
  * Initialize a cardbus controller. Make sure we have a usable
  * interrupt, and that we can map the cardbus area. Fill in the
@@ -1257,8 +1184,6 @@ static int __devinit yenta_probe(struct pci_dev *dev, const struct pci_device_id
 	dev_printk(KERN_INFO, &dev->dev,
 		   "Socket status: %08x\n", cb_readl(socket, CB_SOCKET_STATE));
 
-	yenta_fixup_parent_bridge(dev->subordinate);
-
 	/* Register it with the pcmcia layer.. */
 	ret = pcmcia_register_socket(&socket->socket);
 	if (ret == 0) {
-- 
1.7.7

[PATCH -v12 12/15] PCI: Double checking setting for bus register and bus struct.

[Yinghai Lu]

User could use setpci change bridge's bus register. that could make value of register
and struct is out of sync.
User later will use rescan to see the devices is moving.

In the rescaning, we need to double check the range and remove the old struct at first.

to make thing working user may need have script to remove children devices under bridge
at first, and then use setpci update bus register and then rescan.

Signed-off-by: Yinghai Lu <yinghai@kernel.org>
---
 drivers/pci/probe.c |   42 ++++++++++++++++++++++++++++++++++++++++++
 1 files changed, 42 insertions(+), 0 deletions(-)

diff --git a/drivers/pci/probe.c b/drivers/pci/probe.c
index e77f58d..93b61b8 100644
--- a/drivers/pci/probe.c
+++ b/drivers/pci/probe.c
@@ -806,6 +806,48 @@ int __devinit pci_scan_bridge(struct pci_bus *bus, struct pci_dev *dev, int max,
 	    (primary != bus->number || secondary <= bus->number))
 		broken = 1;
 
+	if (!pass && dev->subordinate) {
+		child = dev->subordinate;
+		/*
+		 * User could change bus register in bridge manually with
+		 * setpci and rescan. So double check the setting, and remove
+		 * old structs.  Don't set broken yet, let following check
+		 * to see if the new setting good.
+		 */
+		if (primary != child->primary ||
+		    secondary != child->busn_res.start ||
+		    subordinate != child->busn_res.end) {
+			dev_info(&dev->dev,
+				"someone changed bus register from pri:%02x, sec:%02x, sub:%02x to pri:%02x, sec:%02x, sub:%02x\n",
+				child->primary, (int)child->busn_res.start,
+				(int)child->busn_res.end,
+				primary, secondary, subordinate);
+			if (!list_empty(&dev->subordinate->devices)) {
+				u32 old_buses;
+
+				dev_info(&dev->dev,
+				 "but children devices are not removed manually before that.\n");
+				/*
+				 * Try best to remove left children devices
+				 * but we need to set bus register back,
+				 * otherwise we can not access children device
+				 * and stop them.
+				 */
+				old_buses = (buses & 0xff000000)
+				   | ((unsigned int)(child->primary) << 0)
+				   | ((unsigned int)(child->busn_res.start) << 8)
+				   | ((unsigned int)(child->busn_res.end) << 16);
+				pci_write_config_dword(dev, PCI_PRIMARY_BUS,
+							 old_buses);
+				pci_stop_and_remove_behind_bridge(dev);
+				pci_write_config_dword(dev, PCI_PRIMARY_BUS,
+							 buses);
+			}
+			pci_remove_bus(dev->subordinate);
+			dev->subordinate = NULL;
+		}
+	}
+
 	/* more strict checking */
 	if (!pass && !broken && !dev->subordinate)
 		broken = pci_bridge_check_busn_broken(bus, dev,
-- 
1.7.7

[PATCH -v12 13/15] PCI, pciehp: Remove not needed bus number range checking

[Yinghai Lu]

Found hotplug adding one EM with bridge fail, bios only leave one bus range
 for slot.

[ 1169.621444] pciehp: No bus number available for hot-added bridge 0000:55:00.0
[ 1169.633277] pcieport 0000:40:03.0: PCI bridge to [bus 55-55]

With busn_res tracking and allocating, we don't need that checking anymore.

Parent bridges' bus number will be extended safely.

Signed-off-by: Yinghai Lu <yinghai@kernel.org>
---
 drivers/pci/hotplug-pci.c |   12 +-----------
 1 files changed, 1 insertions(+), 11 deletions(-)

diff --git a/drivers/pci/hotplug-pci.c b/drivers/pci/hotplug-pci.c
index 6258dc2..2221a27 100644
--- a/drivers/pci/hotplug-pci.c
+++ b/drivers/pci/hotplug-pci.c
@@ -7,18 +7,8 @@
 int __ref pci_hp_add_bridge(struct pci_dev *dev)
 {
 	struct pci_bus *parent = dev->bus;
-	int pass, busnr, start = parent->busn_res.start;
-	int end = parent->busn_res.end;
+	int pass, busnr = parent->busn_res.start;
 
-	for (busnr = start; busnr <= end; busnr++) {
-		if (!pci_find_bus(pci_domain_nr(parent), busnr))
-			break;
-	}
-	if (busnr-- > end) {
-		printk(KERN_ERR "No bus number available for hot-added bridge %s\n",
-				pci_name(dev));
-		return -1;
-	}
 	for (pass = 0; pass < 2; pass++)
 		busnr = pci_scan_bridge(parent, dev, busnr, pass);
 	if (!dev->subordinate)
-- 
1.7.7

[PATCH -v12 14/15] PCI: More strict checking of valid range for bridge

[Yinghai Lu]

Found one sick system with two sibling bridge have overlaping range from BIOS.
00:02.1 bus range is 0x30-0x30
00:02.2 bus range is 0x30-0x3f, and it have two children under it.

RHEL 6.2 kernel, will just 00:02.1 have child bus 0x30, and bridge 00:02.2 will
not have.

before this patch, this patchset will have 00:02.1 to have bus 0x30,
and 00:02.2 will have reallocate range bus 01.
but 00:02.1 will have scaned at first, so later it will have two fake devices.

To fix the problem, We need to check with unscaned sibling bridge about range
overlapping.
If there is overlapping found, will mark both sides to be broken.
So we could prevent one side take too big range.

Signed-off-by: Yinghai Lu <yinghai@kernel.org>
---
 drivers/pci/probe.c |   45 ++++++++++++++++++++++++++++++++++++++++++++-
 1 files changed, 44 insertions(+), 1 deletions(-)

diff --git a/drivers/pci/probe.c b/drivers/pci/probe.c
index 93b61b8..118fe5b 100644
--- a/drivers/pci/probe.c
+++ b/drivers/pci/probe.c
@@ -743,6 +743,48 @@ static int __devinit pci_bridge_probe_busn_res(struct pci_bus *bus,
 	return ret;
 }
 
+static int __devinit pci_bridge_check_busn_broken_with_unscaned(
+				struct pci_bus *bus,
+				struct pci_dev *dev,
+				int secondary, int subordinate)
+{
+	u32 buses2;
+	int broken = 0;
+	struct pci_dev *dev2;
+	int secondary2, subordinate2;
+	int common_start, common_end;
+
+	/* need to check with not scaned sibling bridges */
+	list_for_each_entry(dev2, &bus->devices, bus_list) {
+		if (dev2->hdr_type != PCI_HEADER_TYPE_BRIDGE &&
+		    dev2->hdr_type != PCI_HEADER_TYPE_CARDBUS)
+			continue;
+		if (dev2->subordinate)
+			continue;
+		if (dev2 == dev)
+			continue;
+
+		pci_read_config_dword(dev2, PCI_PRIMARY_BUS, &buses2);
+		secondary2 = (buses2 >> 8) & 0xFF;
+		subordinate2 = (buses2 >> 16) & 0xFF;
+
+		/* overlapping between them ? */
+		common_start = max(secondary, secondary2);
+		common_end = min(subordinate, subordinate2);
+		if (common_start <= common_end) {
+			/*
+			 * Temporarily disable forwarding of the
+			 * configuration cycles on this sibling bridge
+			 */
+			pci_write_config_dword(dev2, PCI_PRIMARY_BUS,
+					       buses2 & ~0xffffff);
+			broken = 1;
+		}
+	}
+
+	return broken;
+}
+
 static int __devinit pci_bridge_check_busn_broken(struct pci_bus *bus,
 				struct pci_dev *dev,
 				int secondary, int subordinate)
@@ -763,7 +805,8 @@ static int __devinit pci_bridge_check_busn_broken(struct pci_bus *bus,
 
 	release_resource(&busn_res);
 
-	return 0;
+	return pci_bridge_check_busn_broken_with_unscaned(bus, dev,
+					secondary, subordinate);
 }
 
 static unsigned int __devinit __pci_scan_child_bus(struct pci_bus *bus,
-- 
1.7.7

[PATCH -v12 15/15] PCI: Don't shrink too much for hotplug bridge

[Yinghai Lu]

Otherwise may have problem later if we plug pcie cards with bridges.

Signed-off-by: Yinghai Lu <yinghai@kernel.org>
---
 drivers/pci/probe.c |    6 ++++++
 1 files changed, 6 insertions(+), 0 deletions(-)

diff --git a/drivers/pci/probe.c b/drivers/pci/probe.c
index 118fe5b..f66f1b1 100644
--- a/drivers/pci/probe.c
+++ b/drivers/pci/probe.c
@@ -811,6 +811,7 @@ static int __devinit pci_bridge_check_busn_broken(struct pci_bus *bus,
 
 static unsigned int __devinit __pci_scan_child_bus(struct pci_bus *bus,
 						 int pass);
+#define HOTPLUG_BRIDGE_RESERVE_BUSNR 8
 /*
  * If it's a bridge, configure it and scan the bus behind it.
  * For CardBus bridges, we don't scan behind as the devices will
@@ -1019,6 +1020,11 @@ int __devinit pci_scan_bridge(struct pci_bus *bus, struct pci_dev *dev, int max,
 		/*
 		 * Set the subordinate bus number to its real value.
 		 */
+		if (dev->is_hotplug_bridge && child->busn_res.end > max &&
+		   (max - child->busn_res.start) < HOTPLUG_BRIDGE_RESERVE_BUSNR)
+			max = min_t(int, child->busn_res.start +
+					 HOTPLUG_BRIDGE_RESERVE_BUSNR,
+				    child->busn_res.end);
 		shrink_size = (int)child->busn_res.end - max;
 		pci_write_config_byte(dev, PCI_SUBORDINATE_BUS, max);
 		pci_bus_update_busn_res_end(child, max);
-- 
1.7.7

Re: [PATCH -v12 01/15] resources: Split out __allocate_resource()

[Linus Torvalds]

On Tue, Jun 26, 2012 at 11:53 AM, Yinghai Lu <yinghai@kernel.org> wrote:
> It will take bool lock, so we could use it in other functions that
> hold the resource lock already.

This is too damn ugly.

These kinds of "conditionally take lock" things are always just bugs
waiting to happen. Don't do it.

Just make the rule be that the caller of the __allocate_resource
helper has to hold the lock. Sure, that means that you need to then
use split reallocate_resource() into a helper function (ie a static
__reallocate_resource() that needs to have the lock taken by the
caller too), but dammit, that's definitely the right thing to do
anyway.

These kinds of "bool lock" crap things have to die. They are *wrong*.
They are a sign of bad locking rules.

                  Linus

Re: [PATCH -v12 01/15] resources: Split out __allocate_resource()

[Yinghai Lu]

[-- Attachment #1: Type: text/plain, Size: 928 bytes --]

On Tue, Jun 26, 2012 at 12:01 PM, Linus Torvalds
<torvalds@linux-foundation.org> wrote:
> On Tue, Jun 26, 2012 at 11:53 AM, Yinghai Lu <yinghai@kernel.org> wrote:
>> It will take bool lock, so we could use it in other functions that
>> hold the resource lock already.
>
> This is too damn ugly.
>
> These kinds of "conditionally take lock" things are always just bugs
> waiting to happen. Don't do it.
>
> Just make the rule be that the caller of the __allocate_resource
> helper has to hold the lock. Sure, that means that you need to then
> use split reallocate_resource() into a helper function (ie a static
> __reallocate_resource() that needs to have the lock taken by the
> caller too), but dammit, that's definitely the right thing to do
> anyway.
>
> These kinds of "bool lock" crap things have to die. They are *wrong*.
> They are a sign of bad locking rules.

You are right, please check updated one.

Thanks

Yinghai

[-- Attachment #2: probe_resource_1.patch --]
[-- Type: application/octet-stream, Size: 3516 bytes --]

Subject: [PATCH] resources: Split out __allocate_resource()

It will out hold lock, so we could use it in other functions that
hold the resource lock already.

-v2: according to Linus, using "bool lock" as parameter
     aka "conditionally take lock" is *wrong*.

Signed-off-by: Yinghai Lu <yinghai@kernel.org>
Cc: Andrew Morton <akpm@linux-foundation.org>

---
 kernel/resource.c |   41 +++++++++++++++++++++++++++++++++--------
 1 file changed, 33 insertions(+), 8 deletions(-)

Index: linux-2.6/kernel/resource.c
===================================================================
--- linux-2.6.orig/kernel/resource.c
+++ linux-2.6/kernel/resource.c
@@ -470,7 +470,7 @@ static int find_resource(struct resource
  * @newsize: new size of the resource descriptor
  * @constraint: the size and alignment constraints to be met.
  */
-int reallocate_resource(struct resource *root, struct resource *old,
+static int __reallocate_resource(struct resource *root, struct resource *old,
 			resource_size_t newsize,
 			struct resource_constraint  *constraint)
 {
@@ -478,7 +478,6 @@ int reallocate_resource(struct resource
 	struct resource new = *old;
 	struct resource *conflict;
 
-	write_lock(&resource_lock);
 
 	if ((err = __find_resource(root, old, &new, newsize, constraint)))
 		goto out;
@@ -504,11 +503,20 @@ int reallocate_resource(struct resource
 		BUG_ON(conflict);
 	}
 out:
-	write_unlock(&resource_lock);
 	return err;
 }
+int reallocate_resource(struct resource *root, struct resource *old,
+			resource_size_t newsize,
+			struct resource_constraint  *constraint)
+{
+	int ret;
 
+	write_lock(&resource_lock);
+	ret = __reallocate_resource(root, old, newsize, constraint);
+	write_unlock(&resource_lock);
 
+	return ret;
+}
 /**
  * allocate_resource - allocate empty slot in the resource tree given range & alignment.
  * 	The resource will be reallocated with a new size if it was already allocated
@@ -521,7 +529,7 @@ out:
  * @alignf: alignment function, optional, called if not NULL
  * @alignf_data: arbitrary data to pass to the @alignf function
  */
-int allocate_resource(struct resource *root, struct resource *new,
+static int __allocate_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 *,
@@ -542,19 +550,36 @@ int allocate_resource(struct resource *r
 	constraint.alignf = alignf;
 	constraint.alignf_data = alignf_data;
 
-	if ( new->parent ) {
+	if (new->parent) {
 		/* resource is already allocated, try reallocating with
 		   the new constraints */
-		return reallocate_resource(root, new, size, &constraint);
+		return __reallocate_resource(root, new, size, &constraint);
 	}
 
-	write_lock(&resource_lock);
 	err = find_resource(root, new, size, &constraint);
 	if (err >= 0 && __request_resource(root, new))
 		err = -EBUSY;
-	write_unlock(&resource_lock);
+
 	return err;
 }
+int allocate_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)
+{
+	int ret;
+
+	write_lock(&resource_lock);
+	ret = __allocate_resource(root, new, size, min, max, align,
+				   alignf, alignf_data);
+	write_unlock(&resource_lock);
+
+	return ret;
+}
 
 EXPORT_SYMBOL(allocate_resource);
 

Re: [PATCH -v12 01/15] resources: Split out __allocate_resource()

[Linus Torvalds]

On Tue, Jun 26, 2012 at 1:33 PM, Yinghai Lu <yinghai@kernel.org> wrote:
>
> You are right, please check updated one.

I think you can now also remove the "goto out" and in
__reallocate_resource() and replace it with a "return err;" instead.

But yeah, this looks fine.

             Linus

Re: [PATCH -v12 02/15] resources: Add probe_resource()

[Yinghai Lu]

[-- Attachment #1: Type: text/plain, Size: 1284 bytes --]

On Tue, Jun 26, 2012 at 11:53 AM, Yinghai Lu <yinghai@kernel.org> wrote:
> It is changed from busn_res only version, because Bjorn found that version
> was not holding resource_lock.
> Even it may be ok for busn_res not holding resource_lock.
> It would be better to have it to be generic and use lock and we may
> use it for other resources.
>
> probe_resource() will try to find specified size or more in parent bus.
> If can not find current parent resource, and it will try to expand parents
> top.
> If still can not find that specified on top, it will try to reduce target size
> until find one.
>
> It will return 0, if it find any resource that could be used.
>
> Returned resource is registered in the tree.
> So caller may need to use replace_resource to put real resource in tree.
>
> -v3: remove two parameters that is for debug purpose.
> -v4: fix stop_flags checking.
> -v5: adjust stop_flags checking position to avoid not needed calling
>        into allocate_resource().

please check attached one that is updated after first patch with
__allocate_resource changes.
except this one and first one are changed. left ones are not needed to
be updated.
So i'm not going to resend them.

the git branch does get updated.

Thanks

Yinghai

[-- Attachment #2: probe_resource_2.patch --]
[-- Type: application/octet-stream, Size: 6261 bytes --]

Subject: [PATCH] resources: Add probe_resource()

It is changed from busn_res only version, because Bjorn found that version
was not holding resource_lock.
Even it may be ok for busn_res not holding resource_lock.
It would be better to have it to be generic and use lock and we may
use it for other resources.

probe_resource() will try to find specified size or more in parent bus.
If can not find current parent resource, and it will try to expand parents
top.
If still can not find that specified on top, it will try to reduce target size
until find one.

It will return 0, if it find any resource that could be used.

Returned resource is registered in the tree.
So caller may need to use replace_resource to put real resource in tree.

-v3: remove two parameters that is for debug purpose.
-v4: fix stop_flags checking.
-v5: adjust stop_flags checking position to avoid not needed calling
	into allocate_resource().
-v6: use updated __allocate_resource.

Signed-off-by: Yinghai Lu <yinghai@kernel.org>
Cc: Andrew Morton <akpm@linux-foundation.org>

---
 include/linux/ioport.h |    7 ++
 kernel/resource.c      |  149 +++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 156 insertions(+)

Index: linux-2.6/include/linux/ioport.h
===================================================================
--- linux-2.6.orig/include/linux/ioport.h
+++ linux-2.6/include/linux/ioport.h
@@ -156,6 +156,13 @@ extern int allocate_resource(struct reso
 						       resource_size_t,
 						       resource_size_t),
 			     void *alignf_data);
+void resource_shrink_parents_top(struct resource *b_res,
+				 long size, struct resource *parent_res);
+struct device;
+int probe_resource(struct resource *b_res,
+			struct resource *busn_res,
+			resource_size_t needed_size, struct resource **p,
+			int skip_nr, int limit, int flags);
 struct resource *lookup_resource(struct resource *root, resource_size_t start);
 int adjust_resource(struct resource *res, resource_size_t start,
 		    resource_size_t size);
Index: linux-2.6/kernel/resource.c
===================================================================
--- linux-2.6.orig/kernel/resource.c
+++ linux-2.6/kernel/resource.c
@@ -989,6 +989,155 @@ void __release_region(struct resource *p
 }
 EXPORT_SYMBOL(__release_region);
 
+static void __resource_extend_parents_top(struct resource *b_res,
+		 long size, struct resource *parent_res)
+{
+	struct resource *res = b_res;
+
+	if (!size)
+		return;
+
+	while (res && res != parent_res) {
+		res->end += size;
+		res = res->parent;
+	}
+}
+
+void resource_shrink_parents_top(struct resource *b_res,
+		 long size, struct resource *parent_res)
+{
+	write_lock(&resource_lock);
+	__resource_extend_parents_top(b_res, -size, parent_res);
+	write_unlock(&resource_lock);
+}
+
+static resource_size_t __find_res_top_free_size(struct resource *res,
+						 int skip_nr)
+{
+	resource_size_t n_size;
+	struct resource tmp_res;
+
+	/*
+	 *   find out free number below res->end that we can use.
+	 *	res->start to res->start + skip_nr - 1 can not be used.
+	 */
+	n_size = resource_size(res);
+	if (n_size <= skip_nr)
+		return 0;
+
+	n_size -= skip_nr;
+	memset(&tmp_res, 0, sizeof(struct resource));
+	while (n_size > 0) {
+		int ret;
+
+		ret = __allocate_resource(res, &tmp_res, n_size,
+			res->end - n_size + skip_nr, res->end,
+			1, NULL, NULL);
+		if (ret == 0) {
+			__release_resource(&tmp_res);
+			break;
+		}
+		n_size--;
+	}
+
+	return n_size;
+}
+
+/**
+ * probe_resource - Probe resource in parent resource.
+ * @b_res: parent resource descriptor
+ * @busn_res: return probed resource
+ * @needed_size: target size
+ * @p: pointer to farest parent that we extend the top
+ * @skip_nr: number in b_res start that we need to skip.
+ * @limit: local boundary
+ * @stop_flags: flags for stopping extend parent res
+ *
+ * will try to allocate resource in b_res, if can not find the range
+ *  will try to extend parent resources' top.
+ * if still can not make it, will reduce needed_size.
+ */
+int probe_resource(struct resource *b_res,
+			 struct resource *busn_res,
+			 resource_size_t needed_size, struct resource **p,
+			 int skip_nr, int limit, int stop_flags)
+{
+	int ret = -ENOMEM;
+	resource_size_t n_size;
+	struct resource *parent_res = NULL;
+	resource_size_t tmp = b_res->end + 1;
+
+again:
+	/*
+	 * We first try to allocate biggest range in b_res that
+	 *  we can use in b_res directly.
+	 *  we also need to skip skip_nr from start of b_res.
+	 */
+	n_size = resource_size(b_res);
+	if (n_size > skip_nr)
+		n_size -= skip_nr;
+	else
+		n_size = 0;
+	memset(busn_res, 0, sizeof(struct resource));
+	while (n_size >= needed_size) {
+		ret = allocate_resource(b_res, busn_res, n_size,
+				b_res->start + skip_nr, b_res->end,
+				1, NULL, NULL);
+		if (!ret)
+			return ret;
+		n_size--;
+	}
+
+	/* Try to extend the top of parent resources to meet needed_size */
+	write_lock(&resource_lock);
+
+	/* b_res could be root bus resource and can not be extended */
+	if (b_res->flags & stop_flags)
+		goto reduce_needed_size;
+
+	/* find out free range under top at first */
+	n_size = __find_res_top_free_size(b_res, skip_nr);
+	/* can not extend cross local boundary */
+	if ((limit - b_res->end) < (needed_size - n_size))
+		goto reduce_needed_size;
+
+	/* Probe extended range above top */
+	memset(busn_res, 0, sizeof(struct resource));
+	parent_res = b_res->parent;
+	while (parent_res && !(parent_res->flags & stop_flags)) {
+		ret = __allocate_resource(parent_res, busn_res,
+			 needed_size - n_size,
+			 tmp, tmp + needed_size - n_size - 1,
+			 1, NULL, NULL);
+		if (!ret) {
+			/* save parent_res, we need it as stopper later */
+			*p = parent_res;
+
+			/* prepare busn_res for return */
+			__release_resource(busn_res);
+			busn_res->start -= n_size;
+
+			/* extend parent resources top */
+			__resource_extend_parents_top(b_res,
+					 needed_size - n_size, parent_res);
+			__request_resource(b_res, busn_res);
+
+			write_unlock(&resource_lock);
+			return ret;
+		}
+		parent_res = parent_res->parent;
+	}
+
+reduce_needed_size:
+	write_unlock(&resource_lock);
+	/* ret must not be 0 here */
+	needed_size--;
+	if (needed_size)
+		goto again;
+
+	return ret;
+}
+
 /*
  * Managed region resource
  */

Re: [PATCH -v12 02/15] resources: Add probe_resource()

[Yinghai Lu]

[-- Attachment #1: Type: text/plain, Size: 1352 bytes --]

On Tue, Jun 26, 2012 at 3:07 PM, Yinghai Lu <yinghai@kernel.org> wrote:
> On Tue, Jun 26, 2012 at 11:53 AM, Yinghai Lu <yinghai@kernel.org> wrote:
>> It is changed from busn_res only version, because Bjorn found that version
>> was not holding resource_lock.
>> Even it may be ok for busn_res not holding resource_lock.
>> It would be better to have it to be generic and use lock and we may
>> use it for other resources.
>>
>> probe_resource() will try to find specified size or more in parent bus.
>> If can not find current parent resource, and it will try to expand parents
>> top.
>> If still can not find that specified on top, it will try to reduce target size
>> until find one.
>>
>> It will return 0, if it find any resource that could be used.
>>
>> Returned resource is registered in the tree.
>> So caller may need to use replace_resource to put real resource in tree.
>>
>> -v3: remove two parameters that is for debug purpose.
>> -v4: fix stop_flags checking.
>> -v5: adjust stop_flags checking position to avoid not needed calling
>>        into allocate_resource().
>
> please check attached one that is updated after first patch with
> __allocate_resource changes.
> except this one and first one are changed. left ones are not needed to
> be updated.
> So i'm not going to resend them.

please check update one. -v7

Thanks

Yinghai

[-- Attachment #2: probe_resource_2.patch --]
[-- Type: application/octet-stream, Size: 8073 bytes --]

Subject: [PATCH] resources: Add probe_resource()

It is changed from busn_res only version, because Bjorn found that version
was not holding resource_lock.
Even it may be ok for busn_res not holding resource_lock.
It would be better to have it to be generic and use lock and we may
use it for other resources.

probe_resource() will try to find specified size or more in parent bus.
If can not find current parent resource, and it will try to expand parents
top.
If still can not find that specified on top, it will try to reduce target size
until find one.

It will return 0, if it find any resource that could be used.

Returned resource is registered in the tree.
So caller may need to use replace_resource to put real resource in tree.

-v3: remove two parameters that is for debug purpose.
-v4: fix stop_flags checking.
-v5: adjust stop_flags checking position to avoid not needed calling
	into allocate_resource().
-v6: use updated __allocate_resource.
-v7: Linus said: "resource_extend_parents()" thing is too dangerous as it
        is. It can corrupt the resource list by making the resource end
        overlap with the next resource (for extension) or not cover all the
        child resources (for shrinking).
     Try to fold in resource_extend_parents_top, and have updated one
	resource_shrink_parent_top() with adjust_resource that will
	checking parent and children covering.

Signed-off-by: Yinghai Lu <yinghai@kernel.org>
Cc: Andrew Morton <akpm@linux-foundation.org>

---
 include/linux/ioport.h |    6 +
 kernel/resource.c      |  188 +++++++++++++++++++++++++++++++++++++++++++++++--
 2 files changed, 190 insertions(+), 4 deletions(-)

Index: linux-2.6/include/linux/ioport.h
===================================================================
--- linux-2.6.orig/include/linux/ioport.h
+++ linux-2.6/include/linux/ioport.h
@@ -156,6 +156,12 @@ extern int allocate_resource(struct reso
 						       resource_size_t,
 						       resource_size_t),
 			     void *alignf_data);
+int resource_shrink_parents_top(struct resource *b_res,
+				 long size, struct resource *parent_res);
+int probe_resource(struct resource *b_res,
+			struct resource *busn_res,
+			resource_size_t needed_size, struct resource **p,
+			int skip_nr, int limit, int flags);
 struct resource *lookup_resource(struct resource *root, resource_size_t start);
 int adjust_resource(struct resource *res, resource_size_t start,
 		    resource_size_t size);
Index: linux-2.6/kernel/resource.c
===================================================================
--- linux-2.6.orig/kernel/resource.c
+++ linux-2.6/kernel/resource.c
@@ -741,14 +741,13 @@ void insert_resource_expand_to_fit(struc
  * arguments.  Returns 0 on success, -EBUSY if it can't fit.
  * Existing children of the resource are assumed to be immutable.
  */
-int adjust_resource(struct resource *res, resource_size_t start, resource_size_t size)
+static int __adjust_resource(struct resource *res, resource_size_t start,
+			     resource_size_t size)
 {
 	struct resource *tmp, *parent = res->parent;
 	resource_size_t end = start + size - 1;
 	int result = -EBUSY;
 
-	write_lock(&resource_lock);
-
 	if (!parent)
 		goto skip;
 
@@ -776,9 +775,19 @@ skip:
 	result = 0;
 
  out:
-	write_unlock(&resource_lock);
 	return result;
 }
+int adjust_resource(struct resource *res, resource_size_t start,
+		    resource_size_t size)
+{
+	int ret;
+
+	write_lock(&resource_lock);
+	ret = __adjust_resource(res, start, size);
+	write_unlock(&resource_lock);
+
+	return ret;
+}
 EXPORT_SYMBOL(adjust_resource);
 
 static void __init __reserve_region_with_split(struct resource *root,
@@ -1011,6 +1020,177 @@ void __release_region(struct resource *p
 }
 EXPORT_SYMBOL(__release_region);
 
+static int __resource_shrink_parents_top(struct resource *b_res,
+		 long size, struct resource *parent_res)
+{
+	struct resource *res = b_res;
+
+	if (size <= 0)
+		return 0;
+
+	while (res && res != parent_res) {
+		if (__adjust_resource(res, res->start,
+			 resource_size(res) - size)) {
+			struct resource *tmp = b_res;
+
+			while (tmp != res) {
+				__adjust_resource(tmp, tmp->start,
+					resource_size(tmp) + size);
+				tmp = tmp->parent;
+			}
+
+			return -EBUSY;
+
+		}
+		res = res->parent;
+	}
+
+	return 0;
+}
+
+int resource_shrink_parents_top(struct resource *b_res,
+		 long size, struct resource *parent_res)
+{
+	int ret;
+
+	write_lock(&resource_lock);
+	ret = __resource_shrink_parents_top(b_res, size, parent_res);
+	write_unlock(&resource_lock);
+
+	return ret;
+}
+
+static resource_size_t __find_res_top_free_size(struct resource *res,
+						 int skip_nr)
+{
+	resource_size_t n_size;
+	struct resource tmp_res;
+
+	/*
+	 *   find out free number below res->end that we can use.
+	 *	res->start to res->start + skip_nr - 1 can not be used.
+	 */
+	n_size = resource_size(res);
+	if (n_size <= skip_nr)
+		return 0;
+
+	n_size -= skip_nr;
+	memset(&tmp_res, 0, sizeof(struct resource));
+	while (n_size > 0) {
+		int ret;
+
+		ret = __allocate_resource(res, &tmp_res, n_size,
+			res->end - n_size + skip_nr, res->end,
+			1, NULL, NULL);
+		if (ret == 0) {
+			__release_resource(&tmp_res);
+			break;
+		}
+		n_size--;
+	}
+
+	return n_size;
+}
+
+/**
+ * probe_resource - Probe resource in parent resource.
+ * @b_res: parent resource descriptor
+ * @busn_res: return probed resource
+ * @needed_size: target size
+ * @p: pointer to farest parent that we extend the top
+ * @skip_nr: number in b_res start that we need to skip.
+ * @limit: local boundary
+ * @stop_flags: flags for stopping extend parent res
+ *
+ * will try to allocate resource in b_res, if can not find the range
+ *  will try to extend parent resources' top.
+ * if still can not make it, will reduce needed_size.
+ */
+int probe_resource(struct resource *b_res,
+			 struct resource *busn_res,
+			 resource_size_t needed_size, struct resource **p,
+			 int skip_nr, int limit, int stop_flags)
+{
+	int ret = -ENOMEM;
+	resource_size_t n_size;
+	struct resource *parent_res = NULL;
+	resource_size_t tmp = b_res->end + 1;
+
+again:
+	/*
+	 * We first try to allocate biggest range in b_res that
+	 *  we can use in b_res directly.
+	 *  we also need to skip skip_nr from start of b_res.
+	 */
+	n_size = resource_size(b_res);
+	if (n_size > skip_nr)
+		n_size -= skip_nr;
+	else
+		n_size = 0;
+	memset(busn_res, 0, sizeof(struct resource));
+	while (n_size >= needed_size) {
+		ret = allocate_resource(b_res, busn_res, n_size,
+				b_res->start + skip_nr, b_res->end,
+				1, NULL, NULL);
+		if (!ret)
+			return ret;
+		n_size--;
+	}
+
+	/* Try to extend the top of parent resources to meet needed_size */
+	write_lock(&resource_lock);
+
+	/* b_res could be root bus resource and can not be extended */
+	if (b_res->flags & stop_flags)
+		goto reduce_needed_size;
+
+	/* find out free range under top at first */
+	n_size = __find_res_top_free_size(b_res, skip_nr);
+	/* can not extend cross local boundary */
+	if ((limit - b_res->end) < (needed_size - n_size))
+		goto reduce_needed_size;
+
+	/* Probe extended range above top */
+	memset(busn_res, 0, sizeof(struct resource));
+	parent_res = b_res->parent;
+	while (parent_res && !(parent_res->flags & stop_flags)) {
+		ret = __allocate_resource(parent_res, busn_res,
+			 needed_size - n_size,
+			 tmp, tmp + needed_size - n_size - 1,
+			 1, NULL, NULL);
+		if (!ret) {
+			struct resource *res = b_res;
+
+			/* save parent_res, we need it as stopper later */
+			*p = parent_res;
+
+			/* prepare busn_res for return */
+			__release_resource(busn_res);
+			busn_res->start -= n_size;
+
+			/* extend parent resources top */
+			while (res && res != parent_res) {
+				res->end += needed_size - n_size;
+				res = res->parent;
+			}
+			__request_resource(b_res, busn_res);
+
+			write_unlock(&resource_lock);
+			return ret;
+		}
+		parent_res = parent_res->parent;
+	}
+
+reduce_needed_size:
+	write_unlock(&resource_lock);
+	/* ret must not be 0 here */
+	needed_size--;
+	if (needed_size)
+		goto again;
+
+	return ret;
+}
+
 /*
  * Managed region resource
  */

Re: [PATCH -v12 02/15] resources: Add probe_resource()

[Linus Torvalds]

On Tue, Aug 28, 2012 at 9:09 AM, Yinghai Lu <yinghai@kernel.org> wrote:
>
> please check update one. -v7

Ugh. Ok, looking closer at this, I think I agree with Bjorn. This is too ugly.

The whole "reduce size/needed_size by 1" double loop is O(n**2). And
it does ugly "insert fake resource to check, and then remove it". Ugh.

Maybe this works in practice for the special case of some PCI bus
numbers that are small integers, but the code is nasty nasty horrible
and not a generic resource allocation thing.

                Linus

Re: [PATCH -v12 02/15] resources: Add probe_resource()

[Linus Torvalds]

[-- Attachment #1: Type: text/plain, Size: 1950 bytes --]

On Tue, Aug 28, 2012 at 10:05 AM, Linus Torvalds
<torvalds@linux-foundation.org> wrote:
>
> Ugh. Ok, looking closer at this,

Btw, looking at that code, I also found what looks like a potential
locking bug in allocate_resource().

The code does

    if (new->parent)
       .. reallocate ..

to check whether a resource was already allocated. HOWEVER, it does so
without actually holding the resource lock. Which means that
"new->parent" might in theory change.

I don't really know if we care. Anybody who does a
"allocate_resource()" on an existing resource that might already be in
the resource tree hopefully does *not* do that in parallel with
another user trying to change the resource allocation, so maybe the
right thing to do is to just say "whatever, if there is a race with
two threads reallocating the same resource at the same time, the bug
is a much more serious one at a higher level".

So this may well be a non-issue. It was introduced some time ago, in
commit 23c570a67448e ("resource: ability to resize an allocated
resource"), since before that we never even allowed re-allocation of
an already allocated resource in the first place, and everything
happened under the lock.

I dunno. Here's a (UNTESTED!) patch that should fix it. Because it's
extremely doubtful whether this is a real problem, I'm certainly not
going to commit it now, much less mark it for stable. But I'm throwing
it out as an RFC. Technically, if people rely on any races being
handled by the resource subsystem, this *could* trigger. But I'm
hoping that the PCI layer has some higher-level locking for
"reallocate the resources of this PCI device". I did *not* check the
callers.

Btw, reallocate_resource() isn't actually used anywhere in the tree
that I can see, so maybe we should remove it and the export, and just
have the __reallocate_resource() that is static to resource.c and is
to be called only with the lock held.

                         Linus

[-- Attachment #2: patch.diff --]
[-- Type: application/octet-stream, Size: 3383 bytes --]

 kernel/resource.c | 75 +++++++++++++++++++++++++++++++------------------------
 1 file changed, 42 insertions(+), 33 deletions(-)

diff --git a/kernel/resource.c b/kernel/resource.c
index 34d45886ee84..829443690497 100644
--- a/kernel/resource.c
+++ b/kernel/resource.c
@@ -462,50 +462,59 @@ static int find_resource(struct resource *root, struct resource *new,
 	return  __find_resource(root, NULL, new, size, constraint);
 }
 
-/**
- * reallocate_resource - allocate a slot in the resource tree given range & alignment.
- *	The resource will be relocated if the new size cannot be reallocated in the
- *	current location.
- *
- * @root: root resource descriptor
- * @old:  resource descriptor desired by caller
- * @newsize: new size of the resource descriptor
- * @constraint: the size and alignment constraints to be met.
- */
-int reallocate_resource(struct resource *root, struct resource *old,
+
+static int __reallocate_resource(struct resource *root, struct resource *old,
 			resource_size_t newsize,
 			struct resource_constraint  *constraint)
 {
-	int err=0;
+	int err;
 	struct resource new = *old;
 	struct resource *conflict;
 
-	write_lock(&resource_lock);
-
-	if ((err = __find_resource(root, old, &new, newsize, constraint)))
-		goto out;
+	err = __find_resource(root, old, &new, newsize, constraint);
+	if (err)
+		return err;
 
 	if (resource_contains(&new, old)) {
 		old->start = new.start;
 		old->end = new.end;
-		goto out;
+		return 0;
 	}
 
-	if (old->child) {
-		err = -EBUSY;
-		goto out;
-	}
+	if (old->child)
+		return -EBUSY;
 
 	if (resource_contains(old, &new)) {
 		old->start = new.start;
 		old->end = new.end;
-	} else {
-		__release_resource(old);
-		*old = new;
-		conflict = __request_resource(root, old);
-		BUG_ON(conflict);
+		return 0;
 	}
-out:
+
+	__release_resource(old);
+	*old = new;
+	conflict = __request_resource(root, old);
+	BUG_ON(conflict);
+	return 0;
+}
+
+/**
+ * reallocate_resource - allocate a slot in the resource tree given range & alignment.
+ *	The resource will be relocated if the new size cannot be reallocated in the
+ *	current location.
+ *
+ * @root: root resource descriptor
+ * @old:  resource descriptor desired by caller
+ * @newsize: new size of the resource descriptor
+ * @constraint: the size and alignment constraints to be met.
+ */
+int reallocate_resource(struct resource *root, struct resource *old,
+			resource_size_t newsize,
+			struct resource_constraint  *constraint)
+{
+	int err;
+
+	write_lock(&resource_lock);
+	err = __reallocate_resource(root, old, newsize, constraint);
 	write_unlock(&resource_lock);
 	return err;
 }
@@ -544,16 +553,16 @@ int allocate_resource(struct resource *root, struct resource *new,
 	constraint.alignf = alignf;
 	constraint.alignf_data = alignf_data;
 
+	write_lock(&resource_lock);
 	if ( new->parent ) {
 		/* resource is already allocated, try reallocating with
 		   the new constraints */
-		return reallocate_resource(root, new, size, &constraint);
+		err = __reallocate_resource(root, new, size, &constraint);
+	} else {
+		err = find_resource(root, new, size, &constraint);
+		if (err >= 0 && __request_resource(root, new))
+			err = -EBUSY;
 	}
-
-	write_lock(&resource_lock);
-	err = find_resource(root, new, size, &constraint);
-	if (err >= 0 && __request_resource(root, new))
-		err = -EBUSY;
 	write_unlock(&resource_lock);
 	return err;
 }

Re: [PATCH -v12 02/15] resources: Add probe_resource()

[Ram Pai]

On Tue, Aug 28, 2012 at 05:10:43PM -0700, Linus Torvalds wrote:
> On Tue, Aug 28, 2012 at 10:05 AM, Linus Torvalds
> <torvalds@linux-foundation.org> wrote:
> >
> > Ugh. Ok, looking closer at this,
> 
> Btw, looking at that code, I also found what looks like a potential
> locking bug in allocate_resource().
> 
> The code does
> 
>     if (new->parent)
>        .. reallocate ..
> 
> to check whether a resource was already allocated. HOWEVER, it does so
> without actually holding the resource lock. Which means that
> "new->parent" might in theory change.
> 

:( it was my mistake.

BTW: adjust_resource() also has the same problem. It is also
accessing res->parent without holding the lock.

The following patch enhances your patch to fix that potential race too.


kernel/resource.c |   81 +++++++++++++++++++++++++++++++++----------------------------
  1 file changed, 45 insertions(+), 36 deletions(-)

diff --git a/kernel/resource.c b/kernel/resource.c
index 34d4588..427ed48 100644
--- a/kernel/resource.c
+++ b/kernel/resource.c
@@ -462,50 +462,59 @@ static int find_resource(struct resource *root, struct resource *new,
 	return  __find_resource(root, NULL, new, size, constraint);
 }
 
-/**
- * reallocate_resource - allocate a slot in the resource tree given range & alignment.
- *	The resource will be relocated if the new size cannot be reallocated in the
- *	current location.
- *
- * @root: root resource descriptor
- * @old:  resource descriptor desired by caller
- * @newsize: new size of the resource descriptor
- * @constraint: the size and alignment constraints to be met.
- */
-int reallocate_resource(struct resource *root, struct resource *old,
+
+static int __reallocate_resource(struct resource *root, struct resource *old,
 			resource_size_t newsize,
 			struct resource_constraint  *constraint)
 {
-	int err=0;
+	int err;
 	struct resource new = *old;
 	struct resource *conflict;
 
-	write_lock(&resource_lock);
-
-	if ((err = __find_resource(root, old, &new, newsize, constraint)))
-		goto out;
+	err = __find_resource(root, old, &new, newsize, constraint);
+	if (err)
+		return err;
 
 	if (resource_contains(&new, old)) {
 		old->start = new.start;
 		old->end = new.end;
-		goto out;
+		return 0;
 	}
 
-	if (old->child) {
-		err = -EBUSY;
-		goto out;
-	}
+	if (old->child)
+		return -EBUSY;
 
 	if (resource_contains(old, &new)) {
 		old->start = new.start;
 		old->end = new.end;
-	} else {
-		__release_resource(old);
-		*old = new;
-		conflict = __request_resource(root, old);
-		BUG_ON(conflict);
+		return 0;
 	}
-out:
+
+	__release_resource(old);
+	*old = new;
+	conflict = __request_resource(root, old);
+	BUG_ON(conflict);
+	return 0;
+}
+
+/**
+ * reallocate_resource - allocate a slot in the resource tree given range
+ * & alignment. The resource will be relocated if the new size cannot be
+ * reallocated in the current location.
+ *
+ * @root: root resource descriptor
+ * @old:  resource descriptor desired by caller
+ * @newsize: new size of the resource descriptor
+ * @constraint: the size and alignment constraints to be met.
+ */
+int reallocate_resource(struct resource *root, struct resource *old,
+			resource_size_t newsize,
+			struct resource_constraint  *constraint)
+{
+	int err;
+
+	write_lock(&resource_lock);
+	err = __reallocate_resource(root, old, newsize, constraint);
 	write_unlock(&resource_lock);
 	return err;
 }
@@ -544,16 +553,16 @@ int allocate_resource(struct resource *root, struct resource *new,
 	constraint.alignf = alignf;
 	constraint.alignf_data = alignf_data;
 
-	if ( new->parent ) {
+	write_lock(&resource_lock);
+	if (new->parent) {
 		/* resource is already allocated, try reallocating with
 		   the new constraints */
-		return reallocate_resource(root, new, size, &constraint);
+		err = __reallocate_resource(root, new, size, &constraint);
+	} else {
+		err = find_resource(root, new, size, &constraint);
+		if (err >= 0 && __request_resource(root, new))
+			err = -EBUSY;
 	}
-
-	write_lock(&resource_lock);
-	err = find_resource(root, new, size, &constraint);
-	if (err >= 0 && __request_resource(root, new))
-		err = -EBUSY;
 	write_unlock(&resource_lock);
 	return err;
 }
@@ -718,12 +727,12 @@ void insert_resource_expand_to_fit(struct resource *root, struct resource *new)
  */
 int adjust_resource(struct resource *res, resource_size_t start, resource_size_t size)
 {
-	struct resource *tmp, *parent = res->parent;
+	struct resource *tmp, *parent;
 	resource_size_t end = start + size - 1;
 	int result = -EBUSY;
 
 	write_lock(&resource_lock);
-
+	parent = res->parent;
 	if (!parent)
 		goto skip;
 

Re: [PATCH -v12 02/15] resources: Add probe_resource()

[Yinghai Lu]

[-- Attachment #1: Type: text/plain, Size: 1388 bytes --]

On Tue, Aug 28, 2012 at 5:10 PM, Linus Torvalds
<torvalds@linux-foundation.org> wrote:
> On Tue, Aug 28, 2012 at 10:05 AM, Linus Torvalds
> <torvalds@linux-foundation.org> wrote:
>>
>> Ugh. Ok, looking closer at this,
>
> Btw, looking at that code, I also found what looks like a potential
> locking bug in allocate_resource().
>
> The code does
>
>     if (new->parent)
>        .. reallocate ..
>
> to check whether a resource was already allocated. HOWEVER, it does so
> without actually holding the resource lock. Which means that
> "new->parent" might in theory change.
>
> I don't really know if we care. Anybody who does a
> "allocate_resource()" on an existing resource that might already be in
> the resource tree hopefully does *not* do that in parallel with
> another user trying to change the resource allocation, so maybe the
> right thing to do is to just say "whatever, if there is a race with
> two threads reallocating the same resource at the same time, the bug
> is a much more serious one at a higher level".

yes, another patch that that split __allocate_resource out have the similar fix.

http://git.kernel.org/?p=linux/kernel/git/yinghai/linux-yinghai.git;a=commitdiff;h=5d52b21303b7271ba4c5302b387766628f074ae2

but the changelog does not that mention the reason.

also have another version for probe_resource, please check attached version -v8.

Thanks

Yinghai

[-- Attachment #2: probe_resource_2.patch --]
[-- Type: application/octet-stream, Size: 7896 bytes --]

Subject: [PATCH] resources: Add probe_resource()

It is changed from busn_res only version, because Bjorn found that version
was not holding resource_lock.
Even it may be ok for busn_res not holding resource_lock.
It would be better to have it to be generic and use lock and we may
use it for other resources.

probe_resource() will try to find specified size or more in parent bus.
If can not find current parent resource, and it will try to expand parents
top.
If still can not find that specified on top, it will try to reduce target size
until find one.

It will return 0, if it find any resource that could be used.

Returned resource is registered in the tree.
So caller may need to use replace_resource to put real resource in tree.

-v3: remove two parameters that is for debug purpose.
-v4: fix stop_flags checking.
-v5: adjust stop_flags checking position to avoid not needed calling
	into allocate_resource().
-v6: use updated __allocate_resource.
-v7: Linus said: "resource_extend_parents()" thing is too dangerous as it
        is. It can corrupt the resource list by making the resource end
        overlap with the next resource (for extension) or not cover all the
        child resources (for shrinking).
     Try to fold in resource_extend_parents_top, and have updated one
	resource_shrink_parent_top() with adjust_resource that will
	checking parent and children covering.
-v8: Linus said: allocation/return is not right, and -1 step tricks make it
	not work as generic resource probe.
     So try to remove the needed_size tricks, and also use __adjust_resource
	for probing instead.

Signed-off-by: Yinghai Lu <yinghai@kernel.org>
Cc: Andrew Morton <akpm@linux-foundation.org>

---
 include/linux/ioport.h |    6 +
 kernel/resource.c      |  168 +++++++++++++++++++++++++++++++++++++++++++++++--
 2 files changed, 170 insertions(+), 4 deletions(-)

Index: linux-2.6/include/linux/ioport.h
===================================================================
--- linux-2.6.orig/include/linux/ioport.h
+++ linux-2.6/include/linux/ioport.h
@@ -156,6 +156,12 @@ extern int allocate_resource(struct reso
 						       resource_size_t,
 						       resource_size_t),
 			     void *alignf_data);
+int resource_shrink_parents_top(struct resource *b_res,
+				 long size, struct resource *parent_res);
+int probe_resource(struct resource *b_res,
+			struct resource *busn_res,
+			resource_size_t needed_size, struct resource **p,
+			int skip_nr, int limit, int flags);
 struct resource *lookup_resource(struct resource *root, resource_size_t start);
 int adjust_resource(struct resource *res, resource_size_t start,
 		    resource_size_t size);
Index: linux-2.6/kernel/resource.c
===================================================================
--- linux-2.6.orig/kernel/resource.c
+++ linux-2.6/kernel/resource.c
@@ -741,14 +741,13 @@ void insert_resource_expand_to_fit(struc
  * arguments.  Returns 0 on success, -EBUSY if it can't fit.
  * Existing children of the resource are assumed to be immutable.
  */
-int adjust_resource(struct resource *res, resource_size_t start, resource_size_t size)
+static int __adjust_resource(struct resource *res, resource_size_t start,
+			     resource_size_t size)
 {
 	struct resource *tmp, *parent = res->parent;
 	resource_size_t end = start + size - 1;
 	int result = -EBUSY;
 
-	write_lock(&resource_lock);
-
 	if (!parent)
 		goto skip;
 
@@ -776,9 +775,19 @@ skip:
 	result = 0;
 
  out:
-	write_unlock(&resource_lock);
 	return result;
 }
+int adjust_resource(struct resource *res, resource_size_t start,
+		    resource_size_t size)
+{
+	int ret;
+
+	write_lock(&resource_lock);
+	ret = __adjust_resource(res, start, size);
+	write_unlock(&resource_lock);
+
+	return ret;
+}
 EXPORT_SYMBOL(adjust_resource);
 
 static void __init __reserve_region_with_split(struct resource *root,
@@ -1011,6 +1020,157 @@ void __release_region(struct resource *p
 }
 EXPORT_SYMBOL(__release_region);
 
+static int __resource_shrink_parents_top(struct resource *b_res,
+		 long size, struct resource *parent_res)
+{
+	struct resource *res = b_res;
+
+	if (size <= 0)
+		return 0;
+
+	while (res && res != parent_res) {
+		if (__adjust_resource(res, res->start,
+			 resource_size(res) - size)) {
+			struct resource *tmp = b_res;
+
+			while (tmp != res) {
+				__adjust_resource(tmp, tmp->start,
+					resource_size(tmp) + size);
+				tmp = tmp->parent;
+			}
+
+			return -EBUSY;
+
+		}
+		res = res->parent;
+	}
+
+	return 0;
+}
+
+int resource_shrink_parents_top(struct resource *b_res,
+		 long size, struct resource *parent_res)
+{
+	int ret;
+
+	write_lock(&resource_lock);
+	ret = __resource_shrink_parents_top(b_res, size, parent_res);
+	write_unlock(&resource_lock);
+
+	return ret;
+}
+
+static resource_size_t __find_res_top_free_size(struct resource *res,
+						 int skip_nr)
+{
+	resource_size_t n_size;
+
+	/*
+	 *   find out free number below res->end that we can use.
+	 *	res->start to res->start + skip_nr - 1 can not be used.
+	 */
+	if (res->child) {
+		struct resource *child = res->child;
+
+		while (child->sibling)
+			child = child->sibling;
+
+		/* check if children cover skip_nr */
+		if (child->end - res->start + 1 >= skip_nr)
+			return res->end - child->end;
+	}
+
+	n_size = resource_size(res);
+	if (n_size <= skip_nr)
+		return 0;
+	return n_size - skip_nr;
+}
+
+/**
+ * probe_resource - Probe resource in parent resource.
+ * @b_res: parent resource descriptor
+ * @busn_res: return probed resource
+ * @needed_size: target size
+ * @p: pointer to farest parent that we extend the top
+ * @skip_nr: number in b_res start that we need to skip.
+ * @limit: local boundary
+ * @stop_flags: flags for stopping extend parent res
+ *
+ * will try to allocate resource in b_res, if can not find the range
+ *  will try to extend parent resources' top.
+ */
+int probe_resource(struct resource *b_res,
+			 struct resource *busn_res,
+			 resource_size_t needed_size, struct resource **p,
+			 int skip_nr, int limit, int stop_flags)
+{
+	int ret = -ENOMEM;
+	resource_size_t n_size;
+	struct resource *parent_res;
+
+	/*
+	 * We first try to allocate range in b_res that
+	 *  we can use in b_res directly.
+	 *  we also need to skip skip_nr from start of b_res.
+	 */
+	memset(busn_res, 0, sizeof(struct resource));
+	ret = allocate_resource(b_res, busn_res, needed_size,
+				b_res->start + skip_nr, b_res->end,
+				1, NULL, NULL);
+	if (!ret)
+		return ret;
+
+	/* Try to extend the top of parent resources to meet needed_size */
+	write_lock(&resource_lock);
+
+	/* b_res could be root bus resource and can not be extended */
+	if (b_res->flags & stop_flags)
+		goto out;
+
+	/* find out free range under top at first */
+	n_size = __find_res_top_free_size(b_res, skip_nr);
+	/* can not extend cross local boundary */
+	if ((limit - b_res->end) < (needed_size - n_size))
+		goto out;
+
+	/* Probe extended range above top */
+	memset(busn_res, 0, sizeof(struct resource));
+	parent_res = b_res->parent;
+	while (parent_res && !(parent_res->flags & stop_flags)) {
+		ret = __adjust_resource(parent_res, parent_res->start,
+			resource_size(parent_res) + (needed_size - n_size));
+		if (!ret) {
+			struct resource *res = b_res;
+
+			/* save parent_res, we need it as stopper later */
+			*p = parent_res;
+
+			/* prepare busn_res for return */
+			__release_resource(busn_res);
+			busn_res->start -= n_size;
+
+			/* extend parent resources top */
+			while (res && res != parent_res) {
+				res->end += needed_size - n_size;
+				res = res->parent;
+			}
+			ret = __allocate_resource(b_res, busn_res, needed_size,
+					b_res->start + skip_nr, b_res->end,
+					1, NULL, NULL);
+
+			write_unlock(&resource_lock);
+			return ret;
+		}
+		parent_res = parent_res->parent;
+	}
+
+out:
+	write_unlock(&resource_lock);
+	/* ret must not be 0 here */
+
+	return ret;
+}
+
 /*
  * Managed region resource
  */

Re: [PATCH -v12 02/15] resources: Add probe_resource()

[Yinghai Lu]

On Wed, Aug 29, 2012 at 3:14 AM, Ram Pai <linuxram@us.ibm.com> wrote:
> @@ -718,12 +727,12 @@ void insert_resource_expand_to_fit(struct resource *root, struct resource *new)
>   */
>  int adjust_resource(struct resource *res, resource_size_t start, resource_size_t size)
>  {
> -       struct resource *tmp, *parent = res->parent;
> +       struct resource *tmp, *parent;
>         resource_size_t end = start + size - 1;
>         int result = -EBUSY;
>
>         write_lock(&resource_lock);
> -
> +       parent = res->parent;
>         if (!parent)
>                 goto skip;

yes, in the v7 of probe_resource() patch that  I sent before,
introduced _adjust_resource solved the problem.


@@ -741,14 +741,13 @@ void insert_resource_expand_to_fit(struc
  * arguments.  Returns 0 on success, -EBUSY if it can't fit.
  * Existing children of the resource are assumed to be immutable.
  */
-int adjust_resource(struct resource *res, resource_size_t start,
resource_size_t size)
+static int __adjust_resource(struct resource *res, resource_size_t start,
+                            resource_size_t size)
 {
        struct resource *tmp, *parent = res->parent;
        resource_size_t end = start + size - 1;
        int result = -EBUSY;

-       write_lock(&resource_lock);
-
        if (!parent)
                goto skip;

@@ -776,9 +775,19 @@ skip:
        result = 0;

  out:
-       write_unlock(&resource_lock);
        return result;
 }
+int adjust_resource(struct resource *res, resource_size_t start,
+                   resource_size_t size)
+{
+       int ret;
+
+       write_lock(&resource_lock);
+       ret = __adjust_resource(res, start, size);
+       write_unlock(&resource_lock);
+
+       return ret;
+}
 EXPORT_SYMBOL(adjust_resource);

 static void __init __reserve_region_with_split(struct resource *root,

Re: [PATCH -v12 02/15] resources: Add probe_resource()

[Yinghai Lu]

[-- Attachment #1: Type: text/plain, Size: 542 bytes --]

On Wed, Aug 29, 2012 at 8:57 AM, Yinghai Lu <yinghai@kernel.org> wrote:
> also have another version for probe_resource, please check attached version -v8.
>

sorry, v8 forget removing two lines.

please -v9 instead.

-v8: Linus said: allocation/return is not right, and -1 step tricks make it
	not work as generic resource probe.
     So try to remove the needed_size tricks, and also use __adjust_resource
	for probing instead.
-v9: remove two lines that is supposed to be removed after converting to use
	__adjust_resource

Thanks

Yinghai

[-- Attachment #2: probe_resource_2.patch --]
[-- Type: application/octet-stream, Size: 7858 bytes --]

Subject: [PATCH] resources: Add probe_resource()

It is changed from busn_res only version, because Bjorn found that version
was not holding resource_lock.
Even it may be ok for busn_res not holding resource_lock.
It would be better to have it to be generic and use lock and we may
use it for other resources.

probe_resource() will try to find specified size or more in parent bus.
If can not find current parent resource, and it will try to expand parents
top.
If still can not find that specified on top, it will try to reduce target size
until find one.

It will return 0, if it find any resource that could be used.

Returned resource is registered in the tree.
So caller may need to use replace_resource to put real resource in tree.

-v3: remove two parameters that is for debug purpose.
-v4: fix stop_flags checking.
-v5: adjust stop_flags checking position to avoid not needed calling
	into allocate_resource().
-v6: use updated __allocate_resource.
-v7: Linus said: "resource_extend_parents()" thing is too dangerous as it
        is. It can corrupt the resource list by making the resource end
        overlap with the next resource (for extension) or not cover all the
        child resources (for shrinking).
     Try to fold in resource_extend_parents_top, and have updated one
	resource_shrink_parent_top() with adjust_resource that will
	checking parent and children covering.
-v8: Linus said: allocation/return is not right, and -1 step tricks make it
	not work as generic resource probe.
     So try to remove the needed_size tricks, and also use __adjust_resource
	for probing instead.
-v9: remove two lines that is supposed to be removed after converting to use
	__adjust_resource

Signed-off-by: Yinghai Lu <yinghai@kernel.org>
Cc: Andrew Morton <akpm@linux-foundation.org>

---
 include/linux/ioport.h |    6 +
 kernel/resource.c      |  165 +++++++++++++++++++++++++++++++++++++++++++++++--
 2 files changed, 167 insertions(+), 4 deletions(-)

Index: linux-2.6/include/linux/ioport.h
===================================================================
--- linux-2.6.orig/include/linux/ioport.h
+++ linux-2.6/include/linux/ioport.h
@@ -156,6 +156,12 @@ extern int allocate_resource(struct reso
 						       resource_size_t,
 						       resource_size_t),
 			     void *alignf_data);
+int resource_shrink_parents_top(struct resource *b_res,
+				 long size, struct resource *parent_res);
+int probe_resource(struct resource *b_res,
+			struct resource *busn_res,
+			resource_size_t needed_size, struct resource **p,
+			int skip_nr, int limit, int flags);
 struct resource *lookup_resource(struct resource *root, resource_size_t start);
 int adjust_resource(struct resource *res, resource_size_t start,
 		    resource_size_t size);
Index: linux-2.6/kernel/resource.c
===================================================================
--- linux-2.6.orig/kernel/resource.c
+++ linux-2.6/kernel/resource.c
@@ -741,14 +741,13 @@ void insert_resource_expand_to_fit(struc
  * arguments.  Returns 0 on success, -EBUSY if it can't fit.
  * Existing children of the resource are assumed to be immutable.
  */
-int adjust_resource(struct resource *res, resource_size_t start, resource_size_t size)
+static int __adjust_resource(struct resource *res, resource_size_t start,
+			     resource_size_t size)
 {
 	struct resource *tmp, *parent = res->parent;
 	resource_size_t end = start + size - 1;
 	int result = -EBUSY;
 
-	write_lock(&resource_lock);
-
 	if (!parent)
 		goto skip;
 
@@ -776,9 +775,19 @@ skip:
 	result = 0;
 
  out:
-	write_unlock(&resource_lock);
 	return result;
 }
+int adjust_resource(struct resource *res, resource_size_t start,
+		    resource_size_t size)
+{
+	int ret;
+
+	write_lock(&resource_lock);
+	ret = __adjust_resource(res, start, size);
+	write_unlock(&resource_lock);
+
+	return ret;
+}
 EXPORT_SYMBOL(adjust_resource);
 
 static void __init __reserve_region_with_split(struct resource *root,
@@ -1011,6 +1020,154 @@ void __release_region(struct resource *p
 }
 EXPORT_SYMBOL(__release_region);
 
+static int __resource_shrink_parents_top(struct resource *b_res,
+		 long size, struct resource *parent_res)
+{
+	struct resource *res = b_res;
+
+	if (size <= 0)
+		return 0;
+
+	while (res && res != parent_res) {
+		if (__adjust_resource(res, res->start,
+			 resource_size(res) - size)) {
+			struct resource *tmp = b_res;
+
+			while (tmp != res) {
+				__adjust_resource(tmp, tmp->start,
+					resource_size(tmp) + size);
+				tmp = tmp->parent;
+			}
+
+			return -EBUSY;
+
+		}
+		res = res->parent;
+	}
+
+	return 0;
+}
+
+int resource_shrink_parents_top(struct resource *b_res,
+		 long size, struct resource *parent_res)
+{
+	int ret;
+
+	write_lock(&resource_lock);
+	ret = __resource_shrink_parents_top(b_res, size, parent_res);
+	write_unlock(&resource_lock);
+
+	return ret;
+}
+
+static resource_size_t __find_res_top_free_size(struct resource *res,
+						 int skip_nr)
+{
+	resource_size_t n_size;
+
+	/*
+	 *   find out free number below res->end that we can use.
+	 *	res->start to res->start + skip_nr - 1 can not be used.
+	 */
+	if (res->child) {
+		struct resource *child = res->child;
+
+		while (child->sibling)
+			child = child->sibling;
+
+		/* check if children cover skip_nr */
+		if (child->end - res->start + 1 >= skip_nr)
+			return res->end - child->end;
+	}
+
+	n_size = resource_size(res);
+	if (n_size <= skip_nr)
+		return 0;
+	return n_size - skip_nr;
+}
+
+/**
+ * probe_resource - Probe resource in parent resource.
+ * @b_res: parent resource descriptor
+ * @busn_res: return probed resource
+ * @needed_size: target size
+ * @p: pointer to farest parent that we extend the top
+ * @skip_nr: number in b_res start that we need to skip.
+ * @limit: local boundary
+ * @stop_flags: flags for stopping extend parent res
+ *
+ * will try to allocate resource in b_res, if can not find the range
+ *  will try to extend parent resources' top.
+ */
+int probe_resource(struct resource *b_res,
+			 struct resource *busn_res,
+			 resource_size_t needed_size, struct resource **p,
+			 int skip_nr, int limit, int stop_flags)
+{
+	int ret;
+	resource_size_t n_size;
+	struct resource *parent_res;
+
+	write_lock(&resource_lock);
+	/*
+	 * We first try to allocate range in b_res that
+	 *  we can use in b_res directly.
+	 *  we also need to skip skip_nr from start of b_res.
+	 */
+	memset(busn_res, 0, sizeof(struct resource));
+	ret = __allocate_resource(b_res, busn_res, needed_size,
+				b_res->start + skip_nr, b_res->end,
+				1, NULL, NULL);
+	if (!ret) {
+		*p = NULL;
+		goto out;
+	}
+
+	/* Try to extend the top of parent resources to meet needed_size */
+
+	/* b_res could be root bus resource and can not be extended */
+	if (b_res->flags & stop_flags)
+		goto out;
+
+	/* find out free range under top at first */
+	n_size = __find_res_top_free_size(b_res, skip_nr);
+	/* can not extend cross local boundary */
+	if ((limit - b_res->end) < (needed_size - n_size))
+		goto out;
+
+	/* Probe extended range above top */
+	memset(busn_res, 0, sizeof(struct resource));
+	parent_res = b_res->parent;
+	while (parent_res && !(parent_res->flags & stop_flags)) {
+		ret = __adjust_resource(parent_res, parent_res->start,
+			resource_size(parent_res) + (needed_size - n_size));
+		if (!ret) {
+			struct resource *res = b_res;
+
+			/* save parent_res, we need it as stopper later */
+			*p = parent_res;
+
+			/* extend parent resources top */
+			while (res && res != parent_res) {
+				res->end += needed_size - n_size;
+				res = res->parent;
+			}
+
+			ret = __allocate_resource(b_res, busn_res, needed_size,
+					b_res->start + skip_nr, b_res->end,
+					1, NULL, NULL);
+			/* ret must be 0 here*/
+			goto out:
+		}
+		parent_res = parent_res->parent;
+	}
+
+out:
+	write_unlock(&resource_lock);
+
+	return ret;
+}
+
 /*
  * Managed region resource
  */

Re: [PATCH -v12 02/15] resources: Add probe_resource()

[Bjorn Helgaas]

On Wed, Aug 29, 2012 at 10:36 AM, Yinghai Lu <yinghai@kernel.org> wrote:
> On Wed, Aug 29, 2012 at 8:57 AM, Yinghai Lu <yinghai@kernel.org> wrote:
>> also have another version for probe_resource, please check attached version -v8.
>>
>
> sorry, v8 forget removing two lines.
>
> please -v9 instead.
>
> -v8: Linus said: allocation/return is not right, and -1 step tricks make it
>         not work as generic resource probe.
>      So try to remove the needed_size tricks, and also use __adjust_resource
>         for probing instead.
> -v9: remove two lines that is supposed to be removed after converting to use
>         __adjust_resource

These tweaks might be slight improvements, but they completely miss
the point of my objection.  I just don't think the probe_resource()
interface is a reasonable addition to kernel/resource.c.  I think it's
too hard to describe what it does, and it seems like it's too specific
to what PCI needs in this particular case.  We should be able to look
at the prototype and get a pretty good idea of what the function does,
but I can't do that with this:

+int probe_resource(struct resource *b_res,
+			 struct resource *busn_res,
+			 resource_size_t needed_size, struct resource **p,
+			 int skip_nr, int limit, int stop_flags)

We already have adjust_resource(), which grows or shrinks a resource
while maintaining the invariants that the adjusted resource (1)
doesn't overlap any of its siblings and (2) still contains all its
children.

adjust_resource() seems like a fairly generic, generally useful
interface.  What you're trying to do with probe_resource() is quite
similar, except that probe_resource() adds the idea of walking up the
tree.

I think you should consider something like an "expand_resource()" that
just balloons a resource at both ends until it abuts its siblings,
i.e., it grows the resource as much as possible.  Then you know the
largest possible size, and you can use adjust_resource() to shrink it
again if you don't need that much.  You can walk up the tree in the
caller when you need to.

Bjorn