linux-kernel - Re: [RFC] 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: <87zfnb81pi.fsf@yhuang6-desk2.ccr.corp.intel.com>
Date: Fri, 11 Oct 2024 16:48:25 +0800
From: "Huang, Ying" <ying.huang@...el.com>
To: David Hildenbrand <david@...hat.com>
Cc: Andrew Morton <akpm@...ux-foundation.org>,  linux-mm@...ck.org,
  linux-kernel@...r.kernel.org,  linux-cxl@...r.kernel.org,  Dan Williams
 <dan.j.williams@...el.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: [RFC] resource: Avoid unnecessary resource tree walking in
 __region_intersects()

David Hildenbrand <david@...hat.com> writes:

> On 11.10.24 03:06, Huang, Ying wrote:
>> David Hildenbrand <david@...hat.com> writes:
>> 
>>> On 10.10.24 08:55, Huang Ying wrote:
>>>> 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 descent 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
>>>> modified it to return NULL after traversing all descent resources.
>>>> Test shows that this avoids unnecessary resource tree walking in
>>>> __region_intersects().
>>>> It appears even better to revise for_each_resource() to traverse the
>>>> descendant resource tree of "_root" only.  But that will cause "_root"
>>>> to be evaluated twice, which I don't find a good way to eliminate.
>>>
>>> I'm not sure I'm enjoying below code, it makes it harder for me to
>>> understand what's happening.
>>>
>>> I'm also not 100% sure why "p" becomes "root" and "dp" becomes "p" when
>>> calling the function :) Likely this works as intended, but it's confusing
>>> (IOW, bad naming, especially for dp).
>>>
>>>
>>> I think you should just leave next_resource() alone and rather add
>>> a new function that doesn't conditionally consume NULL pointers
>>> (and also no skip_children because you're passing false either way).
>>>
>>> static struct resource *next_resource_XXX(struct resource *root,
>>> 		struct resource *p)
>>> {
>>> 	while (!p->sibling && p->parent) {
>>> 		p = p->parent;
>>> 		if (p == root)
>>> 			return NULL;
>>> 	}
>>> 	return p->sibling;
>>> }
>>>
>>> Maybe even better, add a new for_each_resource() macro that expresses the intended semantics.
>>>
>>> #define for_each_resource_XXX(_root, _p) \
>>> 	for ((_p) = (_root)->child; (_p); (_p) = next_resource_XXX(_root, _p))
>> Yes.  This can improve code readability.
>> A possible issue is that "_root" will be evaluated twice in above
>> macro
>> definition. 
>
> Do you mean that we would process it twice in the loop body, or what
> exactly do you mean with "evaluate" ?

In the macro definition above, _root is used twice.  For example, if
"_root" is a time consuming function call, the function will run twice.
That's not expected.

> And just I understand what we want to achieve: we want to walk the
> subtree below "root" and prevent going to root->sibling or
> root->parent if "root" is not actually the "real root", correct?
>
> X
> |--------|
> A----D   E
> |
> B--C
>
>
> So assume we start walking at A, we want to evaluate A,B,C but not D,E,X.
>
> Does that sum up what we want to achieve?

Yes.

--
Best Regards,
Huang, Ying