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

[Huang, Ying]

David Hildenbrand <david@xxxxxxxxxx> 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.  IMO, this should be avoided.  Do you have some idea about
how to do that?  Something like below?

#define for_each_resource_XXX(_root, _p)                                \
	for (typeof(_root) __root = (_root), __p = (_p) = (__root)->child; \
	     __p && (_p); (_p) = next_resource_XXX(__root, _p))

> XXX TBD
>
> Or do you think this should not only be "improved" for the __region_intersects() use case
> but for all for_each_resource() users? I cannot tell easily.

I prefer to make for_each_resource() to traverse only descendant
resource tree of "_root".  This helps code reusing and make the
interface easier to be understood.  The difficulty lies in twice
evaluation as above.

--
Best Regards,
Huang, Ying