From patchwork Tue Oct 22 05:38: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: 13845116 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 A74B2D1CDA1 for ; Tue, 22 Oct 2024 05:38:57 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id E85886B0083; Tue, 22 Oct 2024 01:38:56 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id E0D9E6B0085; Tue, 22 Oct 2024 01:38:56 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id CAE126B0088; Tue, 22 Oct 2024 01:38:56 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0010.hostedemail.com [216.40.44.10]) by kanga.kvack.org (Postfix) with ESMTP id A9D536B0083 for ; Tue, 22 Oct 2024 01:38:56 -0400 (EDT) Received: from smtpin09.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay08.hostedemail.com (Postfix) with ESMTP id 391601406B3 for ; Tue, 22 Oct 2024 05:38:39 +0000 (UTC) X-FDA: 82700133432.09.1FFA04C Received: from mgamail.intel.com (mgamail.intel.com [192.198.163.12]) by imf05.hostedemail.com (Postfix) with ESMTP id 92693100004 for ; Tue, 22 Oct 2024 05:38:23 +0000 (UTC) Authentication-Results: imf05.hostedemail.com; dkim=pass header.d=intel.com header.s=Intel header.b=e5oZkv8A; dmarc=pass (policy=none) header.from=intel.com; spf=pass (imf05.hostedemail.com: domain of ying.huang@intel.com designates 192.198.163.12 as permitted sender) smtp.mailfrom=ying.huang@intel.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1729575411; a=rsa-sha256; cv=none; b=m1R60kJPSInBInm36pV6igbeT2t4j6V13fyxgwiK3OYorM5jg/2eVUvTuaen1wqF9xnPhI SNjtioDIG4mIkpATE9RySsqgFR0JNQVym3bixn9vXXBaQqFJ4dyMUHsz8KgJdGtIrniJWd ErBocdfj3IlViokOrojjWDAqVlnwOoc= ARC-Authentication-Results: i=1; imf05.hostedemail.com; dkim=pass header.d=intel.com header.s=Intel header.b=e5oZkv8A; dmarc=pass (policy=none) header.from=intel.com; spf=pass (imf05.hostedemail.com: domain of ying.huang@intel.com designates 192.198.163.12 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=1729575411; 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=EWyjmILgGrFcr1G5SVbXprVy7uYqAH9ZiKyXUnmMJjk=; b=LsfF57jCcCtW3CD049oySVY6wHWGyq5sbHUomypKqo39jaO3cg4tEDlutFzdiYiSfDNi5B 1D2Xqu3Y1RYv5xDsBbrrjN8sSResbOSe+l5gJDESy7XDCZpFIEs1Ivom/hk7j4wfOtz4Db ODdzKgeejnEhkg0Xt48pN8DOyjIoQd8= DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=intel.com; i=@intel.com; q=dns/txt; s=Intel; t=1729575533; x=1761111533; h=from:to:cc:subject:date:message-id:mime-version: content-transfer-encoding; bh=GwTFeNoIIXjKi/aSaoQJJGcSm97Xf5Ku6yRmwVLP3O4=; b=e5oZkv8Aukujk8aN2AgdYG39lyK6gEd4HN923x4zO7NGUaiWbOZskFDT 5IEh+I8vI4vu4UhZq6ENZ0Zp7Aqo1aqCBefPs55LEtdM/zuxsrjsJKFMJ yJe2FLJnmRvDm8NgOgqyo5iczB6yaSO/gl5SIkD6YiVFOfJL5Adb/+TC1 9N6CHiyMhTKF10SDWgLJv9fAB8IC50Kqo+XiMvhk+fYdYx+3/uhnChpaY br2syduXcF7YhUuGElcdHAp/mX2+F46WYKB4cvvqx+6ynS9lna9rB1zlt VDx4UxABvKCwzE2/052yv48oQ4ZXxnWksyNwE0r1rwH0qUfQMbcX6eJ/F g==; X-CSE-ConnectionGUID: DwMQO62ZTwmgJDkVUMuBgg== X-CSE-MsgGUID: SLxGHGeMQ2Wnmbu9CV6Pfg== X-IronPort-AV: E=McAfee;i="6700,10204,11232"; a="33015500" X-IronPort-AV: E=Sophos;i="6.11,222,1725346800"; d="scan'208";a="33015500" Received: from orviesa003.jf.intel.com ([10.64.159.143]) by fmvoesa106.fm.intel.com with ESMTP/TLS/ECDHE-RSA-AES256-GCM-SHA384; 21 Oct 2024 22:38:52 -0700 X-CSE-ConnectionGUID: Az2Rjbx7TMykrTgOQjxVxg== X-CSE-MsgGUID: u7bsE4q1S5GTrbYWt4vuzg== X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="6.11,199,1725346800"; d="scan'208";a="84557733" Received: from yhuang6-mobl2.sh.intel.com ([10.238.3.32]) by ORVIESA003-auth.jf.intel.com with ESMTP/TLS/ECDHE-RSA-AES256-GCM-SHA384; 21 Oct 2024 22:38:48 -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: [PATCH] resource: Avoid unnecessary resource tree walking in __region_intersects() Date: Tue, 22 Oct 2024 13:38:35 +0800 Message-Id: <20241022053835.217703-1-ying.huang@intel.com> X-Mailer: git-send-email 2.39.2 MIME-Version: 1.0 X-Rspamd-Server: rspam12 X-Rspamd-Queue-Id: 92693100004 X-Stat-Signature: whmc48hg465wc857tg6yrorph1qax9mw X-Rspam-User: X-HE-Tag: 1729575503-175159 X-HE-Meta: U2FsdGVkX19/YXQuCgL9rncBHCGtpaFJAuE+3J0KRhSlfLgRZUbixcmfVamHkHwXpMnhzT0J1KL7/g6EAQBRdFAvB0xNT342gLsU2b6y8u6t5EHcZr00Fh59+DjN9knIn9WpGYhMPauZCA+Hu1UoIanhvqRL1eFmjd5hwg2LHdyJSU/hQ04ANniC6KjyOjvhPLG9etwChE9FtkVtJ7yKL1K1hQnqHfYXEzTQf3NNcJjwH++0ycIBlmEsu0MEYkHjhyTay771bj2Cs2iKGR6mm2sj2d308ZaLvFGHNGdSoZl259rwD4VqIswvfv8izsFyU1rlEk0ICf9w0+fFALy4QopWzpI+oGpn9vAlETF79c8AqW2qOQSP8aJfVv6wHbJLegkVqDu4G1X6PiufAyZKGRcd5L0//+jc5B+F5Q7DVIeqY3MZCvJZpHuL4Sy3I1WOesct9pe8LM5bD86QLm+WbS7akK2G4xvuchDrTVuv39zjtF0gx292lCGRWBEJUK91c/6K+D+5WIcO53YExKFgSACLj6OchOWwpOe+fXuCwxpqvCd48cRi0Zq1lV94ywQ1JrWej+VsOtdmGO1FV8cKIp5zctU6PmX/kSXj/G1Z0yQwBZ4blS5iHYunR28f/YTwtALxA3aCeGTpxjr1lafF3baZannNlmbsVq5kEPnlRABLQEdTU/XwMyUYt2bWk9HvPM5lOSAG6ZKTn0zUu2tbexG78/x7qE96LFMSWEzlT1WPEqvjID05YOL18umDaMBoFTb8a/hjOmu3wBbYz/oUdSJtAJp2b+Li+4FiWL59qkS8pGUN5mmufKywPWqB4jCtOTiIzsJZ9uo59i4nZdk+k0QmHwxC6EQcmnN2KaOQZKQhgkZ6/c9I9bfLoVvDmzYgkDCNbeRBiLhzRAEp6jhPEtsYCBYe7AIrCEA7eB8gRYcyuujxqz8sdTq6R962ec61LWzHnOfdiocCLm8mF0P v7gDB7Ox d77e1s6UCrDAQORW3zTNwGMWYcg0cu1Yq3u85cj2J6YGTKm7R2nJ3H9NwZHXGTgZqmYOmIU6YhmoaLz9mQMxtW2/VKdB6EFH+i3bm1J2NQPeIB4nk7wwHOTvpLoJj5R4Vxg/N78wB9zcywPWEb8KywrbD29v9EjdcKEII7DDcK+7KB/BMgatl2Sgxlm4he+i/QSEGvPWEyLiPBekDvG/H/5xM6QCHntMiQwfFYrKc3QXFj1DI9MA/akX1Y3/7wjn24G1peCdi9VzUzEfLBbmSEZ3i3wXXdHSDCEkB1e/TN3MefvsLLVu9B9gchdls8u87tGMiJ6aMvPnvH1yNa0vvdYv9ASrthOnjtO581uxQYhOX0Riawlk/k8BTcLy/KGRDSIeSVb8Lrl5DUWCEMPx5tvqEHw== 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 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. 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 Acked-by: Dan Williams --- Changes: 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, 23 insertions(+), 3 deletions(-) diff --git a/kernel/resource.c b/kernel/resource.c index b730bd28b422..bd217d57fb09 100644 --- a/kernel/resource.c +++ b/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)) @@ -572,7 +591,8 @@ 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) { + /* Traverse the subtree under 'p'. */ + for (dp = p->child; dp; dp = __next_resource(dp, false, p)) { if (!resource_overlaps(dp, &res)) continue; is_type = (dp->flags & flags) == flags &&