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

From: Yinghai Lu <yinghai@kernel.org>
To: Bjorn Helgaas <bhelgaas@google.com>,
	Benjamin Herrenschmidt <benh@kernel.crashing.org>,
	Tony Luck <tony.luck@intel.com>,
	David Miller <davem@davemloft.net>, x86 <x86@kernel.org>,
	Linus Torvalds <torvalds@linux-foundation.org>
Cc: Dominik Brodowski <linux@dominikbrodowski.net>,
	Andrew Morton <akpm@linux-foundation.org>,
	Greg Kroah-Hartman <gregkh@linuxfoundation.org>,
	linux-pci@vger.kernel.org, linux-kernel@vger.kernel.org,
	linux-arch@vger.kernel.org, Yinghai Lu <yinghai@kernel.org>
Subject: Re: [PATCH -v12 02/15] resources: Add probe_resource()
Date: Tue, 28 Aug 2012 09:09:48 -0700	[thread overview]
Message-ID: <CAE9FiQUXTngUZp2c2dLVRZjFxhXD9e+XYW6Pn0zaHvMt0fB+eA@mail.gmail.com> (raw)
In-Reply-To: <CAE9FiQVrUbEzopKfeoQZFNdNszLN96brC+rYuGXQCfZvpi_ETQ@mail.gmail.com>

[-- 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
  */
