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@xxxxxxxxx>
> Cc: Dan Williams <dan.j.williams@xxxxxxxxx>
> Cc: David Hildenbrand <david@xxxxxxxxxx>
> Cc: Davidlohr Bueso <dave@xxxxxxxxxxxx>
> Cc: Jonathan Cameron <jonathan.cameron@xxxxxxxxxx>
> Cc: Alistair Popple <apopple@xxxxxxxxxx>
> Cc: Andy Shevchenko <andriy.shevchenko@xxxxxxxxxxxxxxx>
> Cc: Bjorn Helgaas <bhelgaas@xxxxxxxxxx>
> Cc: Baoquan He <bhe@xxxxxxxxxx>
> Cc: Dave Jiang <dave.jiang@xxxxxxxxx>
> Cc: Alison Schofield <alison.schofield@xxxxxxxxx>
> ---
> 
> 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@xxxxxxxxx/
> 
> ---
>  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@xxxxxxxxx>