linux-kernel - Re: [PATCH] resource: Avoid unnecessary resource tree walking in __region

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <6717600289c1e_2312294ab@dwillia2-xfh.jf.intel.com.notmuch>
Date: Tue, 22 Oct 2024 01:19:14 -0700
From: Dan Williams <dan.j.williams@...el.com>
To: Huang Ying <ying.huang@...el.com>, Andrew Morton
	<akpm@...ux-foundation.org>
CC: <linux-mm@...ck.org>, <linux-kernel@...r.kernel.org>,
	<linux-cxl@...r.kernel.org>, Huang Ying <ying.huang@...el.com>, Dan Williams
	<dan.j.williams@...el.com>, David Hildenbrand <david@...hat.com>, "Davidlohr
 Bueso" <dave@...olabs.net>, Jonathan Cameron <jonathan.cameron@...wei.com>,
	Alistair Popple <apopple@...dia.com>, Andy Shevchenko
	<andriy.shevchenko@...ux.intel.com>, Bjorn Helgaas <bhelgaas@...gle.com>,
	Baoquan He <bhe@...hat.com>, Dave Jiang <dave.jiang@...el.com>, "Alison
 Schofield" <alison.schofield@...el.com>
Subject: Re: [PATCH] resource: Avoid unnecessary resource tree walking in
 __region_intersects()

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@...el.com>
> Cc: Dan Williams <dan.j.williams@...el.com>
> Cc: David Hildenbrand <david@...hat.com>
> Cc: Davidlohr Bueso <dave@...olabs.net>
> Cc: Jonathan Cameron <jonathan.cameron@...wei.com>
> Cc: Alistair Popple <apopple@...dia.com>
> Cc: Andy Shevchenko <andriy.shevchenko@...ux.intel.com>
> Cc: Bjorn Helgaas <bhelgaas@...gle.com>
> Cc: Baoquan He <bhe@...hat.com>
> Cc: Dave Jiang <dave.jiang@...el.com>
> Cc: Alison Schofield <alison.schofield@...el.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@...el.com>