linux-kernel - [PATCH -V2] 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>] [day] [month] [year] [list]

Message-Id: <20241029122735.79164-1-ying.huang@intel.com>
Date: Tue, 29 Oct 2024 20:27:35 +0800
From: Huang Ying <ying.huang@...el.com>
To: Andrew Morton <akpm@...ux-foundation.org>
Cc: linux-mm@...ck.org,
	linux-kernel@...r.kernel.org,
	Huang Ying <ying.huang@...el.com>,
	Dan Williams <dan.j.williams@...el.com>,
	David Hildenbrand <david@...hat.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: [PATCH -V2] resource: Avoid unnecessary resource tree walking in __region_intersects()

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.

Signed-off-by: "Huang, Ying" <ying.huang@...el.com>
Acked-by: Dan Williams <dan.j.williams@...el.com>
Cc: David Hildenbrand <david@...hat.com>
Cc: Davidlohr Bueso <dave@...olabs.net>
Cc: Jonathan Cameron <jonathan.cameron@...wei.com>
Cc: Alistair Popple <apopple@...dia.com>
Cc: Andy Shevchenko <andriy.shevchenko@...ux.intel.com>
Cc: Bjorn Helgaas <bhelgaas@...gle.com>
Cc: Baoquan He <bhe@...hat.com>
Cc: Dave Jiang <dave.jiang@...el.com>
Cc: Alison Schofield <alison.schofield@...el.com>
---
Changes:

v2:

- Revise for_each_resource() to traverse only descendant resource tree.  Thanks Dan and Andy.

- Collected Acked-by.

- Link to v1: https://lore.kernel.org/linux-mm/20241022053835.217703-1-ying.huang@intel.com/

RFC->v1:

- Revised patch description and comments, Thanks David and Andy!

- Link to RFC: https://lore.kernel.org/linux-mm/20241010065558.1347018-1-ying.huang@intel.com/

---
 kernel/resource.c | 26 ++++++++++++++++++++++----
 1 file changed, 22 insertions(+), 4 deletions(-)

diff --git a/kernel/resource.c b/kernel/resource.c
index b730bd28b422..b6a890c78507 100644
--- a/kernel/resource.c
+++ b/kernel/resource.c
@@ -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, void *v, loff_t *pos)
 
 	(*pos)++;
 
-	return (void *)next_resource(p, false);
+	return (void *)next_resource(p, false, NULL);
 }
 
 static void r_stop(struct seq_file *m, void *v)
-- 
2.39.2