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

From: Dan Williams
Date: Tue Oct 22 2024 - 04:19:33 EST


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>