[PATCH] resource: Avoid unnecessary resource tree walking in __region_intersects()

[PATCH] resource: Avoid unnecessary resource tree walking in __region_intersects()

[Huang Ying]

Currently, if __region_intersects() finds any overlapped but unmatched
resource, it walks the descendant resource tree to check for
overlapped and matched descendant resources.  This is achieved using
for_each_resource(), which iterates not only the descendant tree, but
also subsequent sibling trees in certain scenarios.  While this
doesn't introduce bugs, it makes code hard to be understood and
potentially inefficient.

So, the patch renames next_resource() to __next_resource(), and makes
it possible to only traverse the subtree under the specified resource.
Test shows that this avoids unnecessary resource tree walking in
__region_intersects().

For the example resource tree as follows,

  X
  |
  A----D----E
  |
  B--C

if 'A' is the overlapped but unmatched resource, original kernel
iterates 'B', 'C', 'D', 'E' when it walks the descendant tree.  While
the patched kernel iterates only 'B', 'C'.

It appears even better to revise for_each_resource() to traverse the
resource subtree under "_root" only.  But that will cause "_root" to
be evaluated twice, which I don't find a good way to eliminate.

Thanks David Hildenbrand for providing a good resource tree example.

Signed-off-by: "Huang, Ying" <ying.huang@intel.com>
Cc: Dan Williams <dan.j.williams@intel.com>
Cc: David Hildenbrand <david@redhat.com>
Cc: Davidlohr Bueso <dave@stgolabs.net>
Cc: Jonathan Cameron <jonathan.cameron@huawei.com>
Cc: Alistair Popple <apopple@nvidia.com>
Cc: Andy Shevchenko <andriy.shevchenko@linux.intel.com>
Cc: Bjorn Helgaas <bhelgaas@google.com>
Cc: Baoquan He <bhe@redhat.com>
Cc: Dave Jiang <dave.jiang@intel.com>
Cc: Alison Schofield <alison.schofield@intel.com>
---

Changes:

RFC->v1:

- Revised patch description and comments, Thanks David and Andy!

- Link to RFC: https://lore.kernel.org/linux-mm/20241010065558.1347018-1-ying.huang@intel.com/

---
 kernel/resource.c | 26 +++++++++++++++++++++++---
 1 file changed, 23 insertions(+), 3 deletions(-)

diff --git a/kernel/resource.c b/kernel/resource.c
index b730bd28b422..bd217d57fb09 100644
--- a/kernel/resource.c
+++ b/kernel/resource.c
@@ -50,15 +50,34 @@ EXPORT_SYMBOL(iomem_resource);
 
 static DEFINE_RWLOCK(resource_lock);
 
-static struct resource *next_resource(struct resource *p, bool skip_children)
+/*
+ * Return the next node of @p in pre-order tree traversal.  If
+ * @skip_children is true, skip the descendant nodes of @p in
+ * traversal.  If @p is a descendant of @subtree_root, only traverse
+ * the subtree under @subtree_root.
+ */
+static struct resource *__next_resource(struct resource *p, bool skip_children,
+					struct resource *subtree_root)
 {
 	if (!skip_children && p->child)
 		return p->child;
-	while (!p->sibling && p->parent)
+	while (!p->sibling && p->parent) {
 		p = p->parent;
+		if (p == subtree_root)
+			return NULL;
+	}
 	return p->sibling;
 }
 
+static struct resource *next_resource(struct resource *p, bool skip_children)
+{
+	return __next_resource(p, skip_children, NULL);
+}
+
+/*
+ * Traverse the whole resource tree with @_root as root in pre-order.
+ * NOTE: @_root should be the topmost node, that is, @_root->parent == NULL.
+ */
 #define for_each_resource(_root, _p, _skip_children) \
 	for ((_p) = (_root)->child; (_p); (_p) = next_resource(_p, _skip_children))
 
@@ -572,7 +591,8 @@ static int __region_intersects(struct resource *parent, resource_size_t start,
 		covered = false;
 		ostart = max(res.start, p->start);
 		oend = min(res.end, p->end);
-		for_each_resource(p, dp, false) {
+		/* Traverse the subtree under 'p'. */
+		for (dp = p->child; dp; dp = __next_resource(dp, false, p)) {
 			if (!resource_overlaps(dp, &res))
 				continue;
 			is_type = (dp->flags & flags) == flags &&
-- 
2.39.2

Re: [PATCH] resource: Avoid unnecessary resource tree walking in __region_intersects()

[Dan Williams]

Huang Ying wrote:
[..]
> For the example resource tree as follows,
> 
>   X
>   |
>   A----D----E
>   |
>   B--C
> 
> if 'A' is the overlapped but unmatched resource, original kernel
> iterates 'B', 'C', 'D', 'E' when it walks the descendant tree.  While
> the patched kernel iterates only 'B', 'C'.
> 
> It appears even better to revise for_each_resource() to traverse the
> resource subtree under "_root" only.  But that will cause "_root" to
> be evaluated twice, which I don't find a good way to eliminate.
> 
> Thanks David Hildenbrand for providing a good resource tree example.

Should this have a Reported-by: and a Closes: tags for that report?
Seems useful to capture that in the history.

> Signed-off-by: "Huang, Ying" <ying.huang@intel.com>
> Cc: Dan Williams <dan.j.williams@intel.com>
> Cc: David Hildenbrand <david@redhat.com>
> Cc: Davidlohr Bueso <dave@stgolabs.net>
> Cc: Jonathan Cameron <jonathan.cameron@huawei.com>
> Cc: Alistair Popple <apopple@nvidia.com>
> Cc: Andy Shevchenko <andriy.shevchenko@linux.intel.com>
> Cc: Bjorn Helgaas <bhelgaas@google.com>
> Cc: Baoquan He <bhe@redhat.com>
> Cc: Dave Jiang <dave.jiang@intel.com>
> Cc: Alison Schofield <alison.schofield@intel.com>
> ---
> 
> Changes:
> 
> RFC->v1:
> 
> - Revised patch description and comments, Thanks David and Andy!
> 
> - Link to RFC: https://lore.kernel.org/linux-mm/20241010065558.1347018-1-ying.huang@intel.com/
> 
> ---
>  kernel/resource.c | 26 +++++++++++++++++++++++---
>  1 file changed, 23 insertions(+), 3 deletions(-)
> 
> diff --git a/kernel/resource.c b/kernel/resource.c
> index b730bd28b422..bd217d57fb09 100644
> --- a/kernel/resource.c
> +++ b/kernel/resource.c
> @@ -50,15 +50,34 @@ EXPORT_SYMBOL(iomem_resource);
>  
>  static DEFINE_RWLOCK(resource_lock);
>  
> -static struct resource *next_resource(struct resource *p, bool skip_children)
> +/*
> + * Return the next node of @p in pre-order tree traversal.  If
> + * @skip_children is true, skip the descendant nodes of @p in
> + * traversal.  If @p is a descendant of @subtree_root, only traverse
> + * the subtree under @subtree_root.
> + */
> +static struct resource *__next_resource(struct resource *p, bool skip_children,
> +					struct resource *subtree_root)
>  {
>  	if (!skip_children && p->child)
>  		return p->child;
> -	while (!p->sibling && p->parent)
> +	while (!p->sibling && p->parent) {
>  		p = p->parent;
> +		if (p == subtree_root)
> +			return NULL;
> +	}
>  	return p->sibling;
>  }
>  
> +static struct resource *next_resource(struct resource *p, bool skip_children)
> +{
> +	return __next_resource(p, skip_children, NULL);
> +}
> +
> +/*
> + * Traverse the whole resource tree with @_root as root in pre-order.
> + * NOTE: @_root should be the topmost node, that is, @_root->parent == NULL.
> + */
>  #define for_each_resource(_root, _p, _skip_children) \
>  	for ((_p) = (_root)->child; (_p); (_p) = next_resource(_p, _skip_children))
>  
> @@ -572,7 +591,8 @@ static int __region_intersects(struct resource *parent, resource_size_t start,
>  		covered = false;
>  		ostart = max(res.start, p->start);
>  		oend = min(res.end, p->end);
> -		for_each_resource(p, dp, false) {
> +		/* Traverse the subtree under 'p'. */
> +		for (dp = p->child; dp; dp = __next_resource(dp, false, p)) {

Perhaps a new for_each_resource_descendant() to clarify this new
iterator from for_each_resource()?

Otherwise looks good to me:

Acked-by: Dan Williams <dan.j.williams@intel.com>

Re: [PATCH] resource: Avoid unnecessary resource tree walking in __region_intersects()

[Huang, Ying]

Dan Williams <dan.j.williams@intel.com> writes:

> Huang Ying wrote:
> [..]
>> For the example resource tree as follows,
>> 
>>   X
>>   |
>>   A----D----E
>>   |
>>   B--C
>> 
>> if 'A' is the overlapped but unmatched resource, original kernel
>> iterates 'B', 'C', 'D', 'E' when it walks the descendant tree.  While
>> the patched kernel iterates only 'B', 'C'.
>> 
>> It appears even better to revise for_each_resource() to traverse the
>> resource subtree under "_root" only.  But that will cause "_root" to
>> be evaluated twice, which I don't find a good way to eliminate.
>> 
>> Thanks David Hildenbrand for providing a good resource tree example.
>
> Should this have a Reported-by: and a Closes: tags for that report?
> Seems useful to capture that in the history.

IIUC, David didn't reported an issue.  He just provided an example to
explain the different traversal behavior.

>> Signed-off-by: "Huang, Ying" <ying.huang@intel.com>
>> Cc: Dan Williams <dan.j.williams@intel.com>
>> Cc: David Hildenbrand <david@redhat.com>
>> Cc: Davidlohr Bueso <dave@stgolabs.net>
>> Cc: Jonathan Cameron <jonathan.cameron@huawei.com>
>> Cc: Alistair Popple <apopple@nvidia.com>
>> Cc: Andy Shevchenko <andriy.shevchenko@linux.intel.com>
>> Cc: Bjorn Helgaas <bhelgaas@google.com>
>> Cc: Baoquan He <bhe@redhat.com>
>> Cc: Dave Jiang <dave.jiang@intel.com>
>> Cc: Alison Schofield <alison.schofield@intel.com>
>> ---
>> 
>> Changes:
>> 
>> RFC->v1:
>> 
>> - Revised patch description and comments, Thanks David and Andy!
>> 
>> - Link to RFC: https://lore.kernel.org/linux-mm/20241010065558.1347018-1-ying.huang@intel.com/
>> 
>> ---
>>  kernel/resource.c | 26 +++++++++++++++++++++++---
>>  1 file changed, 23 insertions(+), 3 deletions(-)
>> 
>> diff --git a/kernel/resource.c b/kernel/resource.c
>> index b730bd28b422..bd217d57fb09 100644
>> --- a/kernel/resource.c
>> +++ b/kernel/resource.c
>> @@ -50,15 +50,34 @@ EXPORT_SYMBOL(iomem_resource);
>>  
>>  static DEFINE_RWLOCK(resource_lock);
>>  
>> -static struct resource *next_resource(struct resource *p, bool skip_children)
>> +/*
>> + * Return the next node of @p in pre-order tree traversal.  If
>> + * @skip_children is true, skip the descendant nodes of @p in
>> + * traversal.  If @p is a descendant of @subtree_root, only traverse
>> + * the subtree under @subtree_root.
>> + */
>> +static struct resource *__next_resource(struct resource *p, bool skip_children,
>> +					struct resource *subtree_root)
>>  {
>>  	if (!skip_children && p->child)
>>  		return p->child;
>> -	while (!p->sibling && p->parent)
>> +	while (!p->sibling && p->parent) {
>>  		p = p->parent;
>> +		if (p == subtree_root)
>> +			return NULL;
>> +	}
>>  	return p->sibling;
>>  }
>>  
>> +static struct resource *next_resource(struct resource *p, bool skip_children)
>> +{
>> +	return __next_resource(p, skip_children, NULL);
>> +}
>> +
>> +/*
>> + * Traverse the whole resource tree with @_root as root in pre-order.
>> + * NOTE: @_root should be the topmost node, that is, @_root->parent == NULL.
>> + */
>>  #define for_each_resource(_root, _p, _skip_children) \
>>  	for ((_p) = (_root)->child; (_p); (_p) = next_resource(_p, _skip_children))
>>  
>> @@ -572,7 +591,8 @@ static int __region_intersects(struct resource *parent, resource_size_t start,
>>  		covered = false;
>>  		ostart = max(res.start, p->start);
>>  		oend = min(res.end, p->end);
>> -		for_each_resource(p, dp, false) {
>> +		/* Traverse the subtree under 'p'. */
>> +		for (dp = p->child; dp; dp = __next_resource(dp, false, p)) {
>
> Perhaps a new for_each_resource_descendant() to clarify this new
> iterator from for_each_resource()?

Yes.  That's a good idea.  The problem is that it's hard to avoid double
evaluation in an elegant way.  We have discussed this in

https://lore.kernel.org/linux-mm/ZwkCt_ip5VOGWp4u@smile.fi.intel.com/

I have proposed something like,

#define for_each_resource_descendant(_root, _p)                            \
	for (typeof(_root) __root = (_root), __p = (_p) = (__root)->child; \
	     __p && (_p); (_p) = __next_resource(_p, false, __root))

But this doesn't look elegant.

> Otherwise looks good to me:
>
> Acked-by: Dan Williams <dan.j.williams@intel.com>

Thanks!

--
Best Regards,
Huang, Ying