The patch titled
Subject: resource: Avoid unnecessary resource tree walking in __region_intersects()
has been added to the -mm mm-nonmm-unstable branch. Its filename is
resource-avoid-unnecessary-resource-tree-walking-in-__region_intersects.patch
This patch will shortly appear at
https://git.kernel.org/pub/scm/linux/kernel/git/akpm/25-new.git/tree/patches/resource-avoid-unnecessary-resource-tree-walking-in-__region_intersects.patch
This patch will later appear in the mm-nonmm-unstable branch at
git://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm
Before you just go and hit "reply", please:
a) Consider who else should be cc'ed
b) Prefer to cc a suitable mailing list as well
c) Ideally: find the original patch on the mailing list and do a
reply-to-all to that, adding suitable additional cc's
*** Remember to use Documentation/process/submit-checklist.rst when testing your code ***
The -mm tree is included into linux-next via the mm-everything
branch at git://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm
and is updated there every 2-3 working days
------------------------------------------------------
From: Huang Ying <ying.huang@xxxxxxxxx>
Subject: resource: Avoid unnecessary resource tree walking in __region_intersects()
Date: Tue, 22 Oct 2024 13:38:35 +0800
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 descendant 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 makes
it possible to only traverse the subtree under the specified resource.
Test shows that this avoids unnecessary resource tree walking in
__region_intersects().
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.
Link: https://lkml.kernel.org/r/20241022053835.217703-1-ying.huang@xxxxxxxxx
Signed-off-by: "Huang, Ying" <ying.huang@xxxxxxxxx>
Acked-by: Dan Williams <dan.j.williams@xxxxxxxxx>
Cc: David Hildenbrand <david@xxxxxxxxxx>
Cc: Davidlohr Bueso <dave@xxxxxxxxxxxx>
Cc: Jonathan Cameron <jonathan.cameron@xxxxxxxxxx>
Cc: Alistair Popple <apopple@xxxxxxxxxx>
Cc: Andy Shevchenko <andriy.shevchenko@xxxxxxxxxxxxxxx>
Cc: Bjorn Helgaas <bhelgaas@xxxxxxxxxx>
Cc: Baoquan He <bhe@xxxxxxxxxx>
Cc: Dave Jiang <dave.jiang@xxxxxxxxx>
Cc: Alison Schofield <alison.schofield@xxxxxxxxx>
Signed-off-by: Andrew Morton <akpm@xxxxxxxxxxxxxxxxxxxx>
---
kernel/resource.c | 26 +++++++++++++++++++++++---
1 file changed, 23 insertions(+), 3 deletions(-)
--- a/kernel/resource.c~resource-avoid-unnecessary-resource-tree-walking-in-__region_intersects
+++ a/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))
@@ -566,7 +585,8 @@ static int __region_intersects(struct re
* |-- "System RAM" --||-- "CXL Window 0a" --|
*/
covered = false;
- for_each_resource(p, dp, false) {
+ /* Traverse the subtree under 'p'. */
+ for (dp = p->child; dp; dp = __next_resource(dp, false, p)) {
if (!resource_overlaps(dp, &res))
continue;
if (is_type_match(dp, flags, desc)) {
_
Patches currently in -mm which might be from ying.huang@xxxxxxxxx are
resource-remove-dependency-on-sparsemem-from-get_free_region.patch
resource-avoid-unnecessary-resource-tree-walking-in-__region_intersects.patch
