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] [day] [month] [year] [list]

Message-ID: <87msiw4j1m.fsf@yhuang6-desk2.ccr.corp.intel.com>
Date: Tue, 22 Oct 2024 16:51:33 +0800
From: "Huang, Ying" <ying.huang@...el.com>
To: Dan Williams <dan.j.williams@...el.com>
Cc: Andrew Morton <akpm@...ux-foundation.org>,  linux-mm@...ck.org,
  linux-kernel@...r.kernel.org,  linux-cxl@...r.kernel.org,  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()

Dan Williams <dan.j.williams@...el.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@...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()?

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@...el.com>

Thanks!

--
Best Regards,
Huang, Ying