From mboxrd@z Thu Jan 1 00:00:00 1970 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 AADD6D1CDBD for ; Tue, 22 Oct 2024 08:55:19 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id E85946B007B; Tue, 22 Oct 2024 04:55:18 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id E0A206B0082; Tue, 22 Oct 2024 04:55:18 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id CAAA16B0083; Tue, 22 Oct 2024 04:55:18 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0013.hostedemail.com [216.40.44.13]) by kanga.kvack.org (Postfix) with ESMTP id A76126B007B for ; Tue, 22 Oct 2024 04:55:18 -0400 (EDT) Received: from smtpin07.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay05.hostedemail.com (Postfix) with ESMTP id 4045A41C68 for ; Tue, 22 Oct 2024 08:55:09 +0000 (UTC) X-FDA: 82700628360.07.570E87F Received: from mgamail.intel.com (mgamail.intel.com [198.175.65.12]) by imf26.hostedemail.com (Postfix) with ESMTP id A6DEA14001B for ; Tue, 22 Oct 2024 08:55:03 +0000 (UTC) Authentication-Results: imf26.hostedemail.com; dkim=pass header.d=intel.com header.s=Intel header.b="Ow2ce3z/"; spf=pass (imf26.hostedemail.com: domain of ying.huang@intel.com designates 198.175.65.12 as permitted sender) smtp.mailfrom=ying.huang@intel.com; dmarc=pass (policy=none) header.from=intel.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1729587239; a=rsa-sha256; cv=none; b=3XYFIJAWhfKXL9cByFiqhyP9axU6vOyJ84/0PArsWG8Fr+15myFhYgl0ugx4IgeEDs2aaM W4/RPD+KCYaCyllyPWb+57SvPSoJhlu8b5IeEwBsFqVmcyVn5Izy0oCl2T/H8OVg6UPdO8 KagQU+CmwYih4SLc65smSZAaOvoQhVI= ARC-Authentication-Results: i=1; imf26.hostedemail.com; dkim=pass header.d=intel.com header.s=Intel header.b="Ow2ce3z/"; spf=pass (imf26.hostedemail.com: domain of ying.huang@intel.com designates 198.175.65.12 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=1729587239; 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-type:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=c5P1Ay13T9NFWAIwvMbV7kApDegbxYEQC0Ikf1bU7bE=; b=UQQbcKjUO8yPNv/sf9vHC3qTNBBNcOyicZgfEdYpIdccZzR0T5SpMheb/GpKgIC1a85teZ 0NuPS9yk6Rhf3ZDXJe6HI8fdXt4/CkWAwv/ji86Wrd+GhOYhu8Kj8zpqkPHNITIJpPKLu6 DJsQknDFLFrAJ80p1+rpExPq1V47lCA= DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=intel.com; i=@intel.com; q=dns/txt; s=Intel; t=1729587315; x=1761123315; h=from:to:cc:subject:in-reply-to:references:date: message-id:mime-version; bh=GtdwHkMu5Vu+ITk+uiwWQIn/+rp0fZ195H106kR+b9E=; b=Ow2ce3z/sMjbn8Y6NIzdlbdGXw0/qd/wzs/9xSfZML6q/5sMIyWZk5A1 4ev0dzsA3kV9JhW75Ej5Mfc+Y2oCUp7dGuNFeoWWEDSi1zYm8haxzJswV 1vSaQEWCnyof3tqewi76ncR1P97/PZCvVeLyae6imO7hUxfiRptOOuMQ4 S3OwUQQokxfwzLLq1U+mK+Ma8dlhgckICjK8EMG8qkbnEtpXXWndT270Y OIT7qVs3LRgaxmfEU41DsOFY1lnTaCVzo5UCRGJybkECVpJLirZ/jJk1d 7/kqnz8uaykOf1R84/RqmHI4yFGFqptmYVUKbxKkR1KSocVDXg2Oo+0De Q==; X-CSE-ConnectionGUID: BMq0VRyMTrmkpujAFyAsxQ== X-CSE-MsgGUID: 0Lci5RPFTQqG6F1gqZRJnA== X-IronPort-AV: E=McAfee;i="6700,10204,11232"; a="40493966" X-IronPort-AV: E=Sophos;i="6.11,222,1725346800"; d="scan'208";a="40493966" Received: from fmviesa010.fm.intel.com ([10.60.135.150]) by orvoesa104.jf.intel.com with ESMTP/TLS/ECDHE-RSA-AES256-GCM-SHA384; 22 Oct 2024 01:55:09 -0700 X-CSE-ConnectionGUID: PP3K5ywuSq2E1stjpXA46w== X-CSE-MsgGUID: jQKWzKU/ScOdfm5tdnWGFA== X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="6.11,222,1725346800"; d="scan'208";a="80154060" Received: from yhuang6-desk2.sh.intel.com (HELO yhuang6-desk2.ccr.corp.intel.com) ([10.238.208.55]) by fmviesa010-auth.fm.intel.com with ESMTP/TLS/ECDHE-RSA-AES256-GCM-SHA384; 22 Oct 2024 01:55:06 -0700 From: "Huang, Ying" To: Dan Williams Cc: Andrew Morton , linux-mm@kvack.org, linux-kernel@vger.kernel.org, linux-cxl@vger.kernel.org, David Hildenbrand , Davidlohr Bueso , Jonathan Cameron , Alistair Popple , Andy Shevchenko , Bjorn Helgaas , Baoquan He , Dave Jiang , Alison Schofield Subject: Re: [PATCH] resource: Avoid unnecessary resource tree walking in __region_intersects() In-Reply-To: <6717600289c1e_2312294ab@dwillia2-xfh.jf.intel.com.notmuch> (Dan Williams's message of "Tue, 22 Oct 2024 01:19:14 -0700") References: <20241022053835.217703-1-ying.huang@intel.com> <6717600289c1e_2312294ab@dwillia2-xfh.jf.intel.com.notmuch> Date: Tue, 22 Oct 2024 16:51:33 +0800 Message-ID: <87msiw4j1m.fsf@yhuang6-desk2.ccr.corp.intel.com> User-Agent: Gnus/5.13 (Gnus v5.13) MIME-Version: 1.0 Content-Type: text/plain; charset=ascii X-Stat-Signature: 33gzo7d7bjgjd1g3zd8435d6cb77io55 X-Rspamd-Queue-Id: A6DEA14001B X-Rspam-User: X-Rspamd-Server: rspam10 X-HE-Tag: 1729587303-752889 X-HE-Meta: U2FsdGVkX1+5GCqluL5DuIUcEtpLjsn/WWi73BITtctPEf2ehbeE7VlUHZJna369rQx4sSlUZ34HaE41v/btqjGpcaLbiijkFOfMlvrJVywZkiCK7V+hz0NcR7cdSe6efI930DOZgHvLfJ9Kj88HQdfCcKasDnm5L4Wdxlodf2P8fBwEOWFN87N3s3IkY0+qclQk4YMySQ+S8xwWFwOadt0e0RpSxQKg3wrGyQWmADQ/fP+vkoijZ/bwGkFVZz7aW3sLVrrCOeRFlP5mdPjPro6M3QxVplx6jzfL4vK11WnSjeK3N4R37YbKjSOdWG3hUEknIQrsm/xR4Cu52En1aUKhFqjibwZKkkUBP/CersmCGfl8/1zRRU/I7dNskHaUUl+PYSuPROW/O7qPFV0PZac71dM+6mFEuofogUjf2Niwfbnt+0ps/NOB5PNgCKbUda69+z0uM2hNecBYeHak2QjPJ7tlZyBHNhTtWkC8Zv+tuCwg2cGkRIsSRsjyapigF2RVpsTFkkNjZzOAxD4RNuRtJ//FnnPmqKQDsS1ehl+A7ENy5nAy9fpzfN01VKVt0DpUb3Lg4dK9arJycjdA1PuGcn2cfPNirOD7b5e3ujUtimDj5eF+c+Z0HWYfprymERCIThCNioI1lx7rXBbh7og0F0SMzOXaZUI0rGssqsDX4XtGKj/0SXEF8purXG4BRDMqgKb2BzPDTfawtsMr2WXe+f41JbLJY1TLJAozyt//2bYNoyPXEyXj2L1IzUqfl03jgMv0PfU2kEF8l0374CMN6rAPH0eLPxywQXf6jwDj+sRNgIrsPiyKbbbHYxQtm+7BuUNtDUKe1Sdmb5mNxF+jBhb0xyKB2oAdBfw3PiP6C/l2SlXgrjXqppfj1tMHJgp8Z1swiGHqmd1pmJmPSdnQUoutXk+a1VIDo4Edwh/k53dJaZLypfWVaURupgSNxEwO+MSBJx4yqrTMW12 0/EaXDQI XsGHn0C8jrnwQ4jgZ8VvJD7tcq1iOJjnKMZ4p84g6mOqESGjHKhnSktrhL/+KyLj8kHWaWjgbI24gUruLR7oUyfaBbTFiflW6RgGpDNiP0i+d5qx3rXwxqFn4+JlmYZ+qpEHTRtV6nPS13Cep5XgIOuf+TuIPmxwCPnL2rODDKrcdRo9UP7PI+mfIMOy3TrzUxE8NU2IYPyS/kF2obwmnPc1+r2aU6t2D3m6O6peJoS1dlV9O4Ixu+Oq7VMKbW7TE5YbJTg5BWywyQDXSKxHr8VMOw2evHvSRsa1Pkswwv+ccgzcxb0VXErNZX98I/QxcWg3oYUWHTbj07COaKfa29MuSJXa9NLpbjxrCe6JCqaU1lmCBv0dD7g8TKQdS3tjEf3Dczm5xiOnlg8iqGVQBaPtwFrI/8GdCik0d 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: Dan Williams writes: > Huang Ying wrote: > [..] >> 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. > > Should this have a Reported-by: and a Closes: tags for that report? > Seems useful to capture that in the history. IIUC, David didn't reported an issue. He just provided an example to explain the different traversal behavior. >> 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 >> --- >> >> 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)) { > > Perhaps a new for_each_resource_descendant() to clarify this new > iterator from for_each_resource()? Yes. That's a good idea. The problem is that it's hard to avoid double evaluation in an elegant way. We have discussed this in https://lore.kernel.org/linux-mm/ZwkCt_ip5VOGWp4u@smile.fi.intel.com/ I have proposed something like, #define for_each_resource_descendant(_root, _p) \ for (typeof(_root) __root = (_root), __p = (_p) = (__root)->child; \ __p && (_p); (_p) = __next_resource(_p, false, __root)) But this doesn't look elegant. > Otherwise looks good to me: > > Acked-by: Dan Williams Thanks! -- Best Regards, Huang, Ying