From patchwork Thu Oct 10 06:55:58 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Huang, Ying" X-Patchwork-Id: 13829591 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 7AB09CF07B5 for ; Thu, 10 Oct 2024 06:56:23 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 0BF026B0088; Thu, 10 Oct 2024 02:56:23 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 06F646B0089; Thu, 10 Oct 2024 02:56:23 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id E54976B008A; Thu, 10 Oct 2024 02:56:22 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0014.hostedemail.com [216.40.44.14]) by kanga.kvack.org (Postfix) with ESMTP id CA5A26B0088 for ; Thu, 10 Oct 2024 02:56:22 -0400 (EDT) Received: from smtpin14.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay01.hostedemail.com (Postfix) with ESMTP id 2F6991C76B3 for ; Thu, 10 Oct 2024 06:56:19 +0000 (UTC) X-FDA: 82656783804.14.D7998B7 Received: from mgamail.intel.com (mgamail.intel.com [192.198.163.15]) by imf29.hostedemail.com (Postfix) with ESMTP id D0745120005 for ; Thu, 10 Oct 2024 06:56:18 +0000 (UTC) Authentication-Results: imf29.hostedemail.com; dkim=pass header.d=intel.com header.s=Intel header.b=npWsMbWy; dmarc=pass (policy=none) header.from=intel.com; spf=pass (imf29.hostedemail.com: domain of ying.huang@intel.com designates 192.198.163.15 as permitted sender) smtp.mailfrom=ying.huang@intel.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1728543279; a=rsa-sha256; cv=none; b=snPRsOrQfTxkgp05WHxiZ0ryhEbQIHy2ZwUS1WO9itykBo2QEMqSu9olEdBBDA58OATmqP /dpQVouKqJFkQq1oerlVe1skWBpr7ViS3XWqP8Sg1b5SgFaLJVvKqFIliejDbfmVrO9cL9 oiIhIQy6gLUBsVCiYISob832/GHSZE8= ARC-Authentication-Results: i=1; imf29.hostedemail.com; dkim=pass header.d=intel.com header.s=Intel header.b=npWsMbWy; dmarc=pass (policy=none) header.from=intel.com; spf=pass (imf29.hostedemail.com: domain of ying.huang@intel.com designates 192.198.163.15 as permitted sender) smtp.mailfrom=ying.huang@intel.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1728543279; 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=I5E6hlYT87I4xLnv1an2qbvaXk9AOrRa38Yaav1zUww=; b=eqNFjWwse6XtkH5+LYfSNbMfMZCwUp0hQ9Q7MaN9cVYi2Njr37peKmRjrFFQDPW2o+91HY zLAYIH5LE9GEtPguLIhSGcJhz4Jwb3B4Gxw034sJxc4X4geN4xeWoQTKy4DRleOPMZNwMa p+DdK7tB+DgmfSi7cex4fhi5xFMhQaQ= DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=intel.com; i=@intel.com; q=dns/txt; s=Intel; t=1728543380; x=1760079380; h=from:to:cc:subject:date:message-id:mime-version: content-transfer-encoding; bh=2Df5FXqi+/E58OjQ101ZrWiq5+1tVdsdX+lRyBQgnRE=; b=npWsMbWyynVRskq1G1Dzc8wi6uMcuqmrRHp+N0wsNkGU82jEDrBkTSdk 0ZSaHDcjbABoSBu1plvJGM4birKvpjRAb5qKLf02KzGry/q2+3Xdc3V+p tSBKxiAKDlKbrzYcSggghZilcKFVBwntKo0mnxOsRDHjUO7qVfpRZf6Vl wnzCrS0iLvVTQPoV0JbTGjPHDG+d5ZM7gFbjBw/ehAftr4PII7Lb/Pku8 aFg5ZMHet9lIJkryx+Nm3ymfS38C73E6Y9uTim2HJsWbDZiRZkadZiEpZ qkt3eMKm2wVVvIP87/nr249dREEesK1OrTEK0FiYYVL9AMqTsNLiCe0dC w==; X-CSE-ConnectionGUID: 4gGq/K2gQ7uAsQFZtxNwvw== X-CSE-MsgGUID: 1DB4xhcCRfiFcPG3li/W1A== X-IronPort-AV: E=McAfee;i="6700,10204,11220"; a="28013092" X-IronPort-AV: E=Sophos;i="6.11,192,1725346800"; d="scan'208";a="28013092" Received: from orviesa004.jf.intel.com ([10.64.159.144]) by fmvoesa109.fm.intel.com with ESMTP/TLS/ECDHE-RSA-AES256-GCM-SHA384; 09 Oct 2024 23:56:18 -0700 X-CSE-ConnectionGUID: 1aAYwmSHSemda/dLtUrbhQ== X-CSE-MsgGUID: yz/iyDIDSySv1bSXMR8fdg== X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="6.11,192,1725346800"; d="scan'208";a="81504475" Received: from unknown (HELO yhuang6-mobl2.ccr.corp.intel.com) ([10.245.243.193]) by orviesa004-auth.jf.intel.com with ESMTP/TLS/ECDHE-RSA-AES256-GCM-SHA384; 09 Oct 2024 23:56:15 -0700 From: Huang Ying To: Andrew Morton Cc: linux-mm@kvack.org, linux-kernel@vger.kernel.org, linux-cxl@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: [RFC] resource: Avoid unnecessary resource tree walking in __region_intersects() Date: Thu, 10 Oct 2024 14:55:58 +0800 Message-Id: <20241010065558.1347018-1-ying.huang@intel.com> X-Mailer: git-send-email 2.39.2 MIME-Version: 1.0 X-Rspamd-Queue-Id: D0745120005 X-Rspam-User: X-Rspamd-Server: rspam05 X-Stat-Signature: eq49f7u637htm8g4j7ucjf9wwx1a4cuy X-HE-Tag: 1728543378-152261 X-HE-Meta: U2FsdGVkX1/rLLMlvOHx1HSVgoxp7iCIvaYzMe+VNvPMREZ7mg1BNPfV8jWlTYRTLmTKUVtCoSF8RmuWRT3p+J3Q+2fXa8i+yhd1z/bjRovPMYGZZYBN30t5r327OF2C41XsZixmsvssXiaQRU7OGi6X2l9E9YV4OY9FUGogSlpdJqyB+czTYVzC5iYoViR9qBj9ExP7NqcG08fP3PZcLow+Q6D8qOo5sY5lrrRqY15GPxeqT626D9lXK/Z7xOHWRKOwjyDAj6OfZ2kU0eteiXXA/Wtj0/IYE7oUYOvJqqJtFkdT9NIKxnx7vH+1UvztwMA6ma8CaoFa0eG6ciGwTFx7Kf+mkFCgp5i+/1/KdBVr9EIR8KBmh5+khpAFyx81JQZHUskmY3He+2Rc3+uuJ10V9bMgQ2Mc5Yp6RrIoEB0uJJmdUSVtzYewYnFljQzSq2v7E+XS+fDfCYQ37OZjzHfWFGykycozOWpnPGc3F4xFOY3IZOUz9zVUHF3eyQ1MS43e/2jk8/nFcFLu+a2kAPewUWQ3rVfEQ5SHPse81i0vWQ07r+17bHBIdaIWf+3ZszyiOj0UY2gIrE0TY0ohVWfbM98E5r4F5R7cJYdG8PhPl4zx9i3Hb7vsqbMAIzKA7Xpp1xEEHzL6Lu0ko2q+HQSoJqr/ia5iQBRLaF5pyYgxwZ6+vrOD80Rld9Ko3T4INkVkpBxhoJaoQbRqtzrnEugaQaTs1YFD/++7Lv9nqTG5HEQDuEWNb2uupOrQS2aItzudjYcJQXwDJ9ulNauPOAAPexUYyhose0MwownRV4Ux6X3ztiBP/iI25E+jjRmd0zVxirA50jFKahYh11HjvthbdXNtG/OC4eM7tam07ze4fRi55Z/U0CAt1+ngzaD5cNK5G1SJPfiDiXWybrbGvLDC2+zzCrKWpniYi7sQIRp4ch//HBMZCCVWYVZYZfrLg4wFWMCpP0qs9fafnK0 jUUGOsh+ hUtmYEj5S/hmk4fmPDmq2TqwwRNlt4858sx7j5ZQyv5kHPR3pgns7PeTmMBLg9oMnJeioxtZVV+mc0jmJlilXeOWb+uN2pGD9lJAnvBqCzD6FZ9bM476r39ZfZVE+kzMdg07wCmOL2oRbsJw9BVVKMaVquarhcBJAHx8p3ED4eUD98AUtIGkuMWMwR5zWRNrsKHtiwBXz3TFPOOSnvQCu+8lb/++h1WiLqeeN5ig+bSXcO3IiIwV2og2eutMhzLEpChftVA+Ga4wbtz7+rHWx7Zosz5m6I2dXODzak2FIJv6ZsqelLrHsn/Bxu8XImoiqOoP/0GIwyIqNmGCoVZHo2AnPnCm+OdeGcngiip6Qv15Gi1aJcYuu4dSe3U1P0VnuqyeR 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. 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. Signed-off-by: "Huang, Ying" Cc: 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 --- kernel/resource.c | 19 ++++++++++++++++--- 1 file changed, 16 insertions(+), 3 deletions(-) diff --git a/kernel/resource.c b/kernel/resource.c index b730bd28b422..3ded4c5d4418 100644 --- a/kernel/resource.c +++ b/kernel/resource.c @@ -50,15 +50,28 @@ EXPORT_SYMBOL(iomem_resource); static DEFINE_RWLOCK(resource_lock); -static struct resource *next_resource(struct resource *p, bool skip_children) +static struct resource *__next_resource(struct resource *root, struct resource *p, + bool skip_children) { if (!skip_children && p->child) return p->child; - while (!p->sibling && p->parent) + while (!p->sibling && p->parent) { p = p->parent; + if (p == root) + return NULL; + } return p->sibling; } +static struct resource *next_resource(struct resource *p, bool skip_children) +{ + return __next_resource(NULL, p, skip_children); +} + +/* + * Traverse the whole resource tree (NOTE: not descendant tree under + * _root) from _root->child on. + */ #define for_each_resource(_root, _p, _skip_children) \ for ((_p) = (_root)->child; (_p); (_p) = next_resource(_p, _skip_children)) @@ -572,7 +585,7 @@ static int __region_intersects(struct resource *parent, resource_size_t start, covered = false; ostart = max(res.start, p->start); oend = min(res.end, p->end); - for_each_resource(p, dp, false) { + for (dp = p->child; dp; dp = __next_resource(p, dp, false)) { if (!resource_overlaps(dp, &res)) continue; is_type = (dp->flags & flags) == flags &&