Skip to contentSkip to conversation

resource-avoid-unnecessary-resource-tree-walking-in-__region_intersects.patch removed from -mm tree

merged mm-nonmm-stable Andrew Morton 1 participant 1 message Nov 6, 2024

lore
Share & tools
lore

Andrew Morton

author tree notice Applied
#0 lore raw

The quilt patch titled
Subject: resource: avoid unnecessary resource tree walking in __region_intersects()
has been removed from the -mm tree. Its filename was
resource-avoid-unnecessary-resource-tree-walking-in-__region_intersects.patch

This patch was dropped because it was merged into the mm-nonmm-stable branch of git://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm

------------------------------------------------------
From: Huang Ying <[email protected]>
Subject: resource: avoid unnecessary resource tree walking in __region_intersects()
Date: Tue, 29 Oct 2024 20:27: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 using for_each_resource(). However, in current kernel, for_each_resource() 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 revises next_resource() and for_each_resource() and makes for_each_resource() traverse the subtree under the specified subtree root only. 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'.

Thanks David Hildenbrand for providing a good resource tree example.

Cc David Hildenbrand <[email protected]>
Cc Davidlohr Bueso <[email protected]>
Cc Jonathan Cameron <[email protected]>
Cc Alistair Popple <[email protected]>
Cc Andy Shevchenko <[email protected]>
Cc Bjorn Helgaas <[email protected]>
Cc Baoquan He <[email protected]>
Cc Dave Jiang <[email protected]>
Cc Alison Schofield <[email protected]>

---

 kernel/resource.c |   26 ++++++++++++++++++++++----
 1 file changed, 22 insertions(+), 4 deletions(-)
kernel/resource.c renamed from kernel/resource.c~resource-avoid-unnecessary-resource-tree-walking-in-__region_intersects +22 -4
@@ -50,17 +50,35 @@ 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;
 }
 
+/*
+ * Traverse the resource subtree under @_root in pre-order, excluding
+ * @_root itself.
+ *
+ * NOTE: '__p' is introduced to avoid shadowing '_p' outside of loop.
+ * And it is referenced to avoid unused variable warning.
+ */
 #define for_each_resource(_root, _p, _skip_children) \
-	for ((_p) = (_root)->child; (_p); (_p) = next_resource(_p, _skip_children))
+	for (typeof(_root) __root = (_root), __p = _p = __root->child;	\
+	     __p && _p; _p = next_resource(_p, _skip_children, __root))
 
 #ifdef CONFIG_PROC_FS
 
@@ -88,7 +106,7 @@ static void *r_next(struct seq_file *m,
 
 	(*pos)++;
 
-	return (void *)next_resource(p, false);
+	return (void *)next_resource(p, false, NULL);
 }
 
 static void r_stop(struct seq_file *m, void *v)

_

Patches currently in -mm which might be from [email protected] are