From patchwork Tue Oct 29 12:27:35 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Huang, Ying" X-Patchwork-Id: 13854876 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by smtp.lore.kernel.org (Postfix) with ESMTP id 2592FD2AB35 for ; Tue, 29 Oct 2024 12:28:32 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id B1EF26B0098; Tue, 29 Oct 2024 08:28:31 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id ACC746B0099; Tue, 29 Oct 2024 08:28:31 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 995E56B009A; Tue, 29 Oct 2024 08:28:31 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0011.hostedemail.com [216.40.44.11]) by kanga.kvack.org (Postfix) with ESMTP id 7B7376B0098 for ; Tue, 29 Oct 2024 08:28:31 -0400 (EDT) Received: from smtpin06.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay03.hostedemail.com (Postfix) with ESMTP id ED1DAA1130 for ; Tue, 29 Oct 2024 12:28:30 +0000 (UTC) X-FDA: 82726567056.06.AFA533B Received: from mgamail.intel.com (mgamail.intel.com [192.198.163.19]) by imf01.hostedemail.com (Postfix) with ESMTP id E017740013 for ; Tue, 29 Oct 2024 12:28:08 +0000 (UTC) Authentication-Results: imf01.hostedemail.com; dkim=pass header.d=intel.com header.s=Intel header.b=RMFX4OlH; spf=pass (imf01.hostedemail.com: domain of ying.huang@intel.com designates 192.198.163.19 as permitted sender) smtp.mailfrom=ying.huang@intel.com; dmarc=pass (policy=none) header.from=intel.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1730204749; h=from:from:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-transfer-encoding:content-transfer-encoding: in-reply-to:references:dkim-signature; bh=eOsc1reW888cRvwLc6+xiuyn99DCtNIqcY++7xZrpq8=; b=ROcNVsaxfGYvF3nandYLa4WrzT8CHaEVTRkJoodNvExRaC7gWuABqDyz1yxQfkgCf7LSw3 lttsyB+Q5pBvPBKsX1WplL4y2P5tPX/9PizsRnxir7HDhziRYzwEvJ63S0rBAV6WMh34PF xUjJe0rMIRrSAHtgObP94myfGsM0C44= ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1730204749; a=rsa-sha256; cv=none; b=kpo6nEdnStu37B2xWCubKDfHaSQ1SsFaK1guG73qe2WPPq3W4yIZr+6VCpi5LUTzVOsFKd hzefIRuLlsnXjB49NW8NBJHEx/CMa2tj46JqUnkuSpzOmtdqLQ2IZJcfBp9oGuKj0pJwad On/O40aKWIDdcen6MGHhSDGoUAGTdmo= ARC-Authentication-Results: i=1; imf01.hostedemail.com; dkim=pass header.d=intel.com header.s=Intel header.b=RMFX4OlH; spf=pass (imf01.hostedemail.com: domain of ying.huang@intel.com designates 192.198.163.19 as permitted sender) smtp.mailfrom=ying.huang@intel.com; dmarc=pass (policy=none) header.from=intel.com DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=intel.com; i=@intel.com; q=dns/txt; s=Intel; t=1730204909; x=1761740909; h=from:to:cc:subject:date:message-id:mime-version: content-transfer-encoding; bh=qeIQTaQD+DeGbX8uVEsNttO4ZtpK/BOfkldEqvcYYOY=; b=RMFX4OlHSf6z2dKywfBOt9Xooj2Jwi14XifVNouC9uEsiMegfp/SIuFV Pkx7l0Pjq8y4szLA1SNXiq28EinW78zXTXS+1KiZk0+VS0KSMFj+s/dfK 14HWGdM1pOo3tJJyhKUTP1oAlULl5QOOKADNeEam374w3fOyKnwqPVLOt 6GW0PTjgvGlrZvrlnrB2kszsCR9zXEjKE8ExhVcZ/x5fr9ypGlX2o/r46 5B1xojIzLcwonr6a2JASUHlN8KGqm4CDNKbRYPN99b9VgUzFggcUagwCh LqBcVf+Aa2JmLUC6Cw7fnVjfO4BkXdKFHNErxilVp2Nw6cOVwZ6ooPt5B w==; X-CSE-ConnectionGUID: 381SvvW7SCKqt5oAVJZVWQ== X-CSE-MsgGUID: FNtz2OnuRhGTo4QHEuuMnQ== X-IronPort-AV: E=McAfee;i="6700,10204,11240"; a="29297185" X-IronPort-AV: E=Sophos;i="6.11,241,1725346800"; d="scan'208";a="29297185" Received: from fmviesa002.fm.intel.com ([10.60.135.142]) by fmvoesa113.fm.intel.com with ESMTP/TLS/ECDHE-RSA-AES256-GCM-SHA384; 29 Oct 2024 05:28:27 -0700 X-CSE-ConnectionGUID: lq6Ai53iTAqaPsgmbEbZdg== X-CSE-MsgGUID: f9466FP/SUCGsGYxn8021g== X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="6.11,241,1725346800"; d="scan'208";a="105284653" Received: from unknown (HELO yhuang6-mobl2.ccr.corp.intel.com) ([10.245.242.192]) by fmviesa002-auth.fm.intel.com with ESMTP/TLS/ECDHE-RSA-AES256-GCM-SHA384; 29 Oct 2024 05:28:23 -0700 From: Huang Ying To: Andrew Morton Cc: linux-mm@kvack.org, linux-kernel@vger.kernel.org, Huang Ying , Dan Williams , David Hildenbrand , Davidlohr Bueso , Jonathan Cameron , Alistair Popple , Andy Shevchenko , Bjorn Helgaas , Baoquan He , Dave Jiang , Alison Schofield Subject: [PATCH -V2] resource: Avoid unnecessary resource tree walking in __region_intersects() Date: Tue, 29 Oct 2024 20:27:35 +0800 Message-Id: <20241029122735.79164-1-ying.huang@intel.com> X-Mailer: git-send-email 2.39.2 MIME-Version: 1.0 X-Rspam-User: X-Rspamd-Server: rspam04 X-Rspamd-Queue-Id: E017740013 X-Stat-Signature: 9m36a9wj1863ak5bkx84gfnaug1eweci X-HE-Tag: 1730204888-576018 X-HE-Meta: U2FsdGVkX1+OJtYiYt722+4/YZYEnIzZ+wdlNzElQms02W1D5IIkpmUPezBQY+Rn1wCU5qs02Pr0Bs6x4mDu72uCPKSiz1bH8KqkEMdCja0P25qomry68OeS/qFrnB4/5nswbfrrJBk7xXUuqJCo57bpYdXEhQbxh1ZjZJTXTwEUTf1bqfS6gtlc0L1A554NvEdhcnz4VNdINKq07ExNJoc1/2EG9qcpv2vcCkaIznV0B7U0V9dt4CO0SGhVv4WI3GSTOk/lcePtB0cbKQEB24GwqPfuIZhJVnZUjWq9mk8ZECbSs9v+NEpZ8BAnb+C6N9STN1l0CyrMYFVagrXKFNPX6FZxl3a2XrW7OLmY7YcQVBMa1UujaNff0xKp5cv37Ii8CSftvXmHjcl8RBDN/opYExzY1wllnooOD/9DExUZzdOZXNFZ2eVH32jKgwQQ79SlowHZXV5BrJ5E2MYAFSZvso++AgG/M/d9VO05MUXpJGHvCDWXCRf1o8NDz28jCy8vyrUUUvFZ4Jfce1yEDdVyj6CDvswEGS9LNWVf8rIy/ScGIC6lVkk6kvB6KCAcvBGkxrvvfzs4Ii3rD3lYb45+QAmf6FNwRXfbDfwbv7qwb7kgzL46mxr1zNBCnEbDLCXkIGDOElDUQg2jbQ0Y2U3WzmQI3bfOSEjl8keDqlDOMdt8VlcdZgpRGkQRZ/IjvSpydzpfxSBv9U3doBCQeRg2Uarc3I5mmoNSOHkFedtyW1/GYqugTQ65wdGgmklTJgTGs/MtJDFoiR04zBOtP/Hz2oib9p5rkGsZkFlvRGBifgASCd93DgVnOzKPl97bTzl0PT5ovTa9xv7zQCdo+xloLR3OaA6liOlvGF5797ttxSs80ur1GNziApoA7JpbFA4ZPkQESK/FHqaoMYwoi4CW7YYgcEIqgXFCehfAZoDhyN0ha0nnirka/v7j7+OiOSwvw5scBCdq+vjMk6N dMZb0qYY 0AUPaZ6y5QyjL4xjclt+b0JsE7BNVMu/bxFXdSx5Ow1FZC0k2jRugRzsY/BaCblG4FCiEUD93AJgPitJNZI9w3UoW5io7+XvIVfWTsF9bMZX9N+x8J7gV2r6nlMn1tkgOWAeGfPy3qWFCfkUO4zY38ZNR07P7vFb5827WXeFim3zzh/K9zcvK5eFRldEb4TMsr5JIcx6+92vexVRduwDo8/Rec3zh3lv/fpnvk2VpizFGDM5pQv60XfDp+D/dU6Hva908ibHErtk+myBx5K8ETDyRvu3o8vkPRRdn/MZmpaNa8FdFuir+hpuRwZ5k2nKkpZwm8DA3TJtc1Pwn9+vJ2M9QyQF+fOEId0JYNEIyH/JsfBDdJrYkYf4gE0frHUdKTiDV4+1jeu+f2+HVYAZY9OTaZA== X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: List-Subscribe: List-Unsubscribe: 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" Acked-by: Dan Williams Cc: David Hildenbrand Cc: Davidlohr Bueso Cc: Jonathan Cameron Cc: Alistair Popple Cc: Andy Shevchenko Cc: Bjorn Helgaas Cc: Baoquan He Cc: Dave Jiang Cc: Alison Schofield --- 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)