From patchwork Mon Feb 24 02:22:39 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Wei Yang X-Patchwork-Id: 13987334 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 4873CC021B2 for ; Mon, 24 Feb 2025 02:24:54 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id A2A026B007B; Sun, 23 Feb 2025 21:24:53 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id 9B3056B0083; Sun, 23 Feb 2025 21:24:53 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 82C446B0085; Sun, 23 Feb 2025 21:24:53 -0500 (EST) 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 637E36B007B for ; Sun, 23 Feb 2025 21:24:53 -0500 (EST) Received: from smtpin24.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay08.hostedemail.com (Postfix) with ESMTP id CD7261406EF for ; Mon, 24 Feb 2025 02:24:52 +0000 (UTC) X-FDA: 83153245224.24.75C9DBB Received: from mail-ej1-f42.google.com (mail-ej1-f42.google.com [209.85.218.42]) by imf26.hostedemail.com (Postfix) with ESMTP id 12C01140007 for ; Mon, 24 Feb 2025 02:24:50 +0000 (UTC) Authentication-Results: imf26.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=dxyPZ14j; spf=pass (imf26.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.218.42 as permitted sender) smtp.mailfrom=richard.weiyang@gmail.com; dmarc=pass (policy=none) header.from=gmail.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1740363891; h=from:from:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:content-type: content-transfer-encoding:in-reply-to:references:dkim-signature; bh=c7Cc1piIg1Zb5LB89HrqbGIXBWyMqUHL/mUcdpVAwyw=; b=oMUcT5CbOqF9zYabpCxUt0R0Zij+idq0Y1qILxD3B6p0Sg8k6onhcME74qFYO81tpR4CsA OA7jY71hUtkMX8b6/cwDMAJyFIKLfoTt8isdUME+FwM7iYauCFKN41brCByxQpNchP8VAX 8BIgMpNmSwGAknZuv2Me0XQvYKBJSow= ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1740363891; a=rsa-sha256; cv=none; b=et/9nMvi0ed2NU11YjRyzb+fFyBmLfh3/Nk+CTIq070/BPS4sQlfj7kqZnpziwUuyUTmYk 3COzFF3sRRdl9R4s+Pzd8IsGY2AL3SUwZhTebEh7FT95mdXFfyGym2qOTgVWUM9hZaUuqJ S4/Hfp0LP5JtGsOSEocFSkNyPfkpkuU= ARC-Authentication-Results: i=1; imf26.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=dxyPZ14j; spf=pass (imf26.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.218.42 as permitted sender) smtp.mailfrom=richard.weiyang@gmail.com; dmarc=pass (policy=none) header.from=gmail.com Received: by mail-ej1-f42.google.com with SMTP id a640c23a62f3a-aaec61d0f65so771438066b.1 for ; Sun, 23 Feb 2025 18:24:50 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1740363889; x=1740968689; darn=kvack.org; h=message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=c7Cc1piIg1Zb5LB89HrqbGIXBWyMqUHL/mUcdpVAwyw=; b=dxyPZ14jAgUfy6SjxPwpaRG/phQAzvmJU7oqsG2H1rGBPVu7tSxaDnxYHfYxEQsYqL VWr6WqjOONLiqaXLnjbsJQZCN3sj4rSDtO6TEzMxqcK9zg4FfmmJCxqVaRSSaMnhAUn7 FaTklaap5iSS5wlW+O+Y04EWVii3jOCVVqpNjhFezIMunHMbyqp0ASrHlAK3906YOF+Q wgEoXCg6hN0kxfWUunzq0xYGUgQP+3KIb1hP13PJFppdRthYMfKg7LB2fI/1Tex3VNfr pYYlBFqL0zHtv1YlDUEFMuiQO2jUyfEZogfMP151K/Raslbshzs+2v+WT8DrXFZzGDv7 wUtQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1740363889; x=1740968689; h=message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=c7Cc1piIg1Zb5LB89HrqbGIXBWyMqUHL/mUcdpVAwyw=; b=r2/h34A62LvDx61+Cv88hBRVyFpmva7rfGZnUpJmHuKdyI7lUT8R1gN/VRBXqrXroz UOY+4vjvOnpHX52UDO7wbWhDF4HJEHLpFUxQX85uai9Zou+h9DYoF7p2pgjZv34ue+u5 OY+bwaiE++Za4N7j6Bmrat9F1QjmVnWtE7h6em4UybPYA6rLUZ1JL7t4pVOycicdQZnk hJ75eL3qfGx7VKfI21exH9wjaU6gz9O5mekbStlIHtw4jUgUfnmE58YypETb5aQDshpC hX8VBQSj76vsYNTEkDspmMzMvhBBEXQR5uBRioLKI/E4JUYPEOIJpt5Bor/VAUpyQVSZ n0/g== X-Gm-Message-State: AOJu0YxJw3CYcYWw3iswLXnUxyWzcwUyJ8X/mUa7lPcibs74f9x1SJTz v7034d1e1A44KuEDxizHmofgB09IpANgoPa7isJWgwnpTPxrf/sX X-Gm-Gg: ASbGnctd23XF4bPBjlEzpsz8tQW3iwTb8mUPTaZZG6SLvI+I0n1y5VwHrQRSeAsAFQU QZcXoppGcultgaHnoAIFbvLL1lU4fsMXOzSUMSkLPbyX4lTk3J0W/SgKbEH5e3Kic6vokqwrhR5 H0yRBqQ0H1UO4lLxizCx5q6huYGWMBQx/HAQz2IM5ld5sWl7IiOdw+vXU4NDTB62s0jj+Ibv97A IxIiguwhKyzYNvVhmXaMWGvi0GYhtYuMDbl/rmaPmLYdS7N1fIMCbUx1D+8gYoF15+REvHJFIJ6 hVbEMMyLtyvE3ouvzyA+NPqKhA== X-Google-Smtp-Source: AGHT+IGprBbhyOx0rh8IZOKPlcrEPy8TUW8qV1gaVPFNluTLZt4IzsasEhyJKaraWOqrShDMUNCaqA== X-Received: by 2002:a17:907:9801:b0:aba:6385:b46d with SMTP id a640c23a62f3a-abc09d37dadmr1075534166b.50.1740363889371; Sun, 23 Feb 2025 18:24:49 -0800 (PST) Received: from localhost ([185.92.221.13]) by smtp.gmail.com with ESMTPSA id a640c23a62f3a-abb82771809sm1670120066b.171.2025.02.23.18.24.48 (version=TLS1_2 cipher=ECDHE-ECDSA-CHACHA20-POLY1305 bits=256/256); Sun, 23 Feb 2025 18:24:48 -0800 (PST) From: Wei Yang To: akpm@linux-foundation.org, michel@lespinasse.org Cc: linux-mm@kvack.org, Wei Yang Subject: [PATCH] lib/interval_tree: skip the check before go to the right subtree Date: Mon, 24 Feb 2025 02:22:39 +0000 Message-Id: <20250224022239.21976-1-richard.weiyang@gmail.com> X-Mailer: git-send-email 2.11.0 X-Rspam-User: X-Rspamd-Queue-Id: 12C01140007 X-Rspamd-Server: rspam07 X-Stat-Signature: dgcfiroxejudy8zsftre9n7fyz17d83k X-HE-Tag: 1740363890-875980 X-HE-Meta: U2FsdGVkX19c/1GhVxVIIk0HcSZOhuJ1BnkuJ9Akm6JiMH8Dlmc5lNoAzTy6DTEHqAJH4cfWHpYEghyUiExe2QbuUMdk15VZNh/CjxMtHyGyzArNkY+6jToYKctpZPwCaIw7/cVjVoPTjCvWJ6R/2oOtrojV9lOwiXZu48iP5g/4nFY0FmJxcOsp+BtbtIBtdlQHUixHEhBbpsVxgctAZxzEksQFZpIUPAyrbNnUnKQ0Xj3bPLfCyksMGC2E8/0Q8qFnBoya6MTz6U2nMSXvgeSyUubIrTOl/055R2n6h7vtJkVGHW+EJaNszceZ5oYdM3ceaXfweJdXd/vdx7yAX1OCcu4WlYAVnAowd4qPtMpo6GSdxwUTG1mrba8DH2j+WZIhCYnbjxOsRsHKb/SvqwLxp9uOxtq0ixwiUyCB6LkMJazgM/q6pecJyOo++aqVJhLYeIkEm9THWsNv2nuX861rGDgmJ2k3f+Q9jETOM4zbIgoIctTkHLUaN8Z/PeeIa9MViFA2mSEtZaLCRSza/6K0eSRUvWKz62AjSRW1Ks9qHynC8rMuBHyWfUFmJ69RzAQC3DqULgv4KbxM/B/hk9XtYW9VpMniWtOBY3ytaCygYEBAcZsTSicaERO85PpAvKUWm2zOzYh5Ky+PA/1dGkMWdems7YrvrrlgjE7BvgA88MTYJ8NLvlCfEhkMm0zYAYAoGBncpYbIYi8n9M7tCQJUqBkvOkEQ8xOn4FCcnYDZpOB+p6aK2lowkIlwreLT6NjiueXXR4LKoGs5xioVaYtUkUwCgOVW1IWdenaA1V/5rMclPuHWJC6A7yACoNyG8KHtR9g6RwC4F5frZUdbLPFGqR/JjFrolAiUGEeC9oG+kMtmG1fD0Rs1pdg6IqiKl54EO9+vfheVlspyYIEW0nikJRxAwHJ81ngm0Hx/9S+GX6tGcb5HjPTEQIgtR3kkRFHydQYmJB4Z2sSSVvp tbgcnWL1 AHYqzJWm/sJxckCv1tbLDd/cKdxgw2BebGzhq+xUNwiKlLq4g0CcDM25YxSYwumKE2peuxaXxoJleIOmSUYhGU5VNTnefKn7ewHQlKlMF+57W/VAsyLumlziy8DNyACff4W08ggn4cZLw4NuHz2XKh5/iEEJfEemorXnZXapKhc92OPI5ChrOLp5C8KXhZv0KbQpStj8vwpaL3K5zbKt1tq0b39e3+OTonLax9DEigLMRHQHKCj1EnoF8iwZVbkfI31SLvGzr+jPhqZIZVUoY1kRsUTAdogvOvSKrlN+G6YCgT9DP/nO2a1q4pZuwXZI6mqvZPSZP+HmcUswgQNbAhVfBCY6MVWW6aqgnixQAV0/Prxj0aMFN0h60TyflaDj7ZaTjx/MKeX+HHOJvrBen37bE7cvlj1P5IoT7YYx2WdvkX8vTdYn/hoIn8x23+9HP8IyA+xg7Lc/1Zbsdxo5tyeIFUyteAKOwJHxdcXCNUNxw7Hya3pr761bYgDoNkB9Pl+MwQ1Dc3++yIfYnwW4f5nDKKOQb3himiHGwpJac9SDmxExuczzOkj+/dw== X-Bogosity: Ham, tests=bogofilter, spamicity=0.001928, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: List-Subscribe: List-Unsubscribe: The interval_tree_subtree_search() holds the loop invariant: start <= node->ITSUBTREE Let's say we have a following tree: node / \ left right So we know node->ITSUBTREE is contributed by one of the following: * left->ITSUBTREE * ITLAST(node) * right->ITSUBTREE When we come to the right node, we are sure the first two don't contribute to node->ITSUBTREE and it must be the right node does the job. So skip the check before go to the right subtree. Signed-off-by: Wei Yang --- include/linux/interval_tree_generic.h | 8 ++------ 1 file changed, 2 insertions(+), 6 deletions(-) diff --git a/include/linux/interval_tree_generic.h b/include/linux/interval_tree_generic.h index aaa8a0767aa3..1b400f26f63d 100644 --- a/include/linux/interval_tree_generic.h +++ b/include/linux/interval_tree_generic.h @@ -104,12 +104,8 @@ ITPREFIX ## _subtree_search(ITSTRUCT *node, ITTYPE start, ITTYPE last) \ if (ITSTART(node) <= last) { /* Cond1 */ \ if (start <= ITLAST(node)) /* Cond2 */ \ return node; /* node is leftmost match */ \ - if (node->ITRB.rb_right) { \ - node = rb_entry(node->ITRB.rb_right, \ - ITSTRUCT, ITRB); \ - if (start <= node->ITSUBTREE) \ - continue; \ - } \ + node = rb_entry(node->ITRB.rb_right, ITSTRUCT, ITRB); \ + continue; \ } \ return NULL; /* No match */ \ } \