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

[David Hildenbrand]

On 11.10.24 03:06, Huang, Ying wrote:
> 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. 

Do you mean that we would process it twice in the loop body, or what 
exactly do you mean with "evaluate" ?


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?

--
Cheers,

David / dhildenb