From patchwork Thu Oct 24 13:22:16 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Yu Kuai X-Patchwork-Id: 13849011 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 DA537CE8E74 for ; Thu, 24 Oct 2024 13:25:23 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 01B296B009D; Thu, 24 Oct 2024 09:25:19 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id EE3E06B00AB; Thu, 24 Oct 2024 09:25:18 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id CEA686B00AC; Thu, 24 Oct 2024 09:25:18 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0012.hostedemail.com [216.40.44.12]) by kanga.kvack.org (Postfix) with ESMTP id A7E816B009D for ; Thu, 24 Oct 2024 09:25:18 -0400 (EDT) Received: from smtpin23.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay10.hostedemail.com (Postfix) with ESMTP id 727BCC12E6 for ; Thu, 24 Oct 2024 13:24:58 +0000 (UTC) X-FDA: 82708566570.23.FFE9FA4 Received: from dggsgout11.his.huawei.com (dggsgout11.his.huawei.com [45.249.212.51]) by imf08.hostedemail.com (Postfix) with ESMTP id 4643F160030 for ; Thu, 24 Oct 2024 13:25:02 +0000 (UTC) Authentication-Results: imf08.hostedemail.com; dkim=none; spf=pass (imf08.hostedemail.com: domain of yukuai1@huaweicloud.com designates 45.249.212.51 as permitted sender) smtp.mailfrom=yukuai1@huaweicloud.com; dmarc=none ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1729776162; 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:in-reply-to:references:references; bh=h8lKvPZeH9YeU1pVtrmUPXjk9ZaXFZgJF41bfDRO5Z4=; b=NbkZdJLEGnfnjR8HN36hTGMCSenMtoPRL+HRm9jjOTXqNnXLysEG8ds+as5D6WElLCUV5S GrmT7Z+9b4WfYjcaPGQbxlvt3ZN00swTHva2BFhlG8T4YInbKVUi/t5Jvljg78+yfTMZcn 5ZatbqbMRE32Oi7/u/TPG7iKzGYp6P8= ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1729776162; a=rsa-sha256; cv=none; b=gQtY04TX1kypSJhkCbR4ms3iX1D1sj3fmkgGKdwcHBItWQEbM/JMPqXgcsdyyocUD/AWdF iJB0NxZXnSUtfl3j3eWzpxWgfIKniv6b2kejqDiqFCs6pj0cvWuMo24PXFoBAoTdJsLIlj oJVqo/c+3HcGClQB6kJTrgTb+XvMqCo= ARC-Authentication-Results: i=1; imf08.hostedemail.com; dkim=none; spf=pass (imf08.hostedemail.com: domain of yukuai1@huaweicloud.com designates 45.249.212.51 as permitted sender) smtp.mailfrom=yukuai1@huaweicloud.com; dmarc=none Received: from mail.maildlp.com (unknown [172.19.163.216]) by dggsgout11.his.huawei.com (SkyGuard) with ESMTP id 4XZ68j4G25z4f3nbD for ; Thu, 24 Oct 2024 21:24:53 +0800 (CST) Received: from mail02.huawei.com (unknown [10.116.40.128]) by mail.maildlp.com (Postfix) with ESMTP id DAF461A0194 for ; Thu, 24 Oct 2024 21:25:11 +0800 (CST) Received: from huaweicloud.com (unknown [10.175.104.67]) by APP4 (Coremail) with SMTP id gCh0CgD3LMmxShpnmfz6Ew--.42902S7; Thu, 24 Oct 2024 21:25:11 +0800 (CST) From: Yu Kuai To: stable@vger.kernel.org, gregkh@linuxfoundation.org, harry.wentland@amd.com, sunpeng.li@amd.com, Rodrigo.Siqueira@amd.com, alexander.deucher@amd.com, christian.koenig@amd.com, Xinhui.Pan@amd.com, airlied@gmail.com, daniel@ffwll.ch, viro@zeniv.linux.org.uk, brauner@kernel.org, Liam.Howlett@oracle.com, akpm@linux-foundation.org, hughd@google.com, willy@infradead.org, sashal@kernel.org, srinivasan.shanmugam@amd.com, chiahsuan.chung@amd.com, mingo@kernel.org, mgorman@techsingularity.net, yukuai3@huawei.com, chengming.zhou@linux.dev, zhangpeng.00@bytedance.com, chuck.lever@oracle.com Cc: amd-gfx@lists.freedesktop.org, dri-devel@lists.freedesktop.org, linux-kernel@vger.kernel.org, linux-fsdevel@vger.kernel.org, maple-tree@lists.infradead.org, linux-mm@kvack.org, yukuai1@huaweicloud.com, yi.zhang@huawei.com, yangerkun@huawei.com Subject: [PATCH 6.6 19/28] maple_tree: mtree_range_walk() clean up Date: Thu, 24 Oct 2024 21:22:16 +0800 Message-Id: <20241024132225.2271667-4-yukuai1@huaweicloud.com> X-Mailer: git-send-email 2.39.2 In-Reply-To: <20241024132225.2271667-1-yukuai1@huaweicloud.com> References: <20241024132009.2267260-1-yukuai1@huaweicloud.com> <20241024132225.2271667-1-yukuai1@huaweicloud.com> MIME-Version: 1.0 X-CM-TRANSID: gCh0CgD3LMmxShpnmfz6Ew--.42902S7 X-Coremail-Antispam: 1UD129KBjvJXoW7tFW5Kr47Zr1fKFyDCw1rZwb_yoW8KFWfpF nxW345KF9xJF17Crs3Ka1kJrySg3ZxGrWUAa4UGryrZryaywnYg3ZYvryfua98K345A34Y gF43Zw1xW3WIyFJanT9S1TB71UUUUU7qnTZGkaVYY2UrUUUUjbIjqfuFe4nvWSU5nxnvy2 9KBjDU0xBIdaVrnRJUUUmY14x267AKxVWrJVCq3wAFc2x0x2IEx4CE42xK8VAvwI8IcIk0 rVWrJVCq3wAFIxvE14AKwVWUJVWUGwA2048vs2IY020E87I2jVAFwI0_JrWl82xGYIkIc2 x26xkF7I0E14v26ryj6s0DM28lY4IEw2IIxxk0rwA2F7IY1VAKz4vEj48ve4kI8wA2z4x0 Y4vE2Ix0cI8IcVAFwI0_Ar0_tr1l84ACjcxK6xIIjxv20xvEc7CjxVAFwI0_Cr1j6rxdM2 8EF7xvwVC2z280aVAFwI0_GcCE3s1l84ACjcxK6I8E87Iv6xkF7I0E14v26rxl6s0DM2AI xVAIcxkEcVAq07x20xvEncxIr21l5I8CrVACY4xI64kE6c02F40Ex7xfMcIj6xIIjxv20x vE14v26r1Y6r17McIj6I8E87Iv67AKxVWUJVW8JwAm72CE4IkC6x0Yz7v_Jr0_Gr1lF7xv r2IYc2Ij64vIr41lF7I21c0EjII2zVCS5cI20VAGYxC7M4IIrI8v6xkF7I0E8cxan2IY04 v7MxkF7I0En4kS14v26rWY6Fy7MxAIw28IcxkI7VAKI48JMxC20s026xCaFVCjc4AY6r1j 6r4UMI8I3I0E5I8CrVAFwI0_Jr0_Jr4lx2IqxVCjr7xvwVAFwI0_JrI_JrWlx4CE17CEb7 AF67AKxVWrXVW8Jr1lIxkGc2Ij64vIr41lIxAIcVC0I7IYx2IY67AKxVW5JVW7JwCI42IY 6xIIjxv20xvEc7CjxVAFwI0_Cr1j6rxdMIIF0xvE42xK8VAvwI8IcIk0rVWUJVWUCwCI42 IY6I8E87Iv67AKxVW8JVWxJwCI42IY6I8E87Iv6xkF7I0E14v26F4UJVW0obIYCTnIWIev Ja73UjIFyTuYvjTRXID7UUUUU X-CM-SenderInfo: 51xn3trlr6x35dzhxuhorxvhhfrp/ X-Stat-Signature: tfxgco4ebxm6sd47aywfxez15j7rkna9 X-Rspamd-Queue-Id: 4643F160030 X-Rspam-User: X-Rspamd-Server: rspam08 X-HE-Tag: 1729776302-245273 X-HE-Meta: U2FsdGVkX1/dsX8JcK2vNG2IhM3ABsT+LSH03yl1oCD5T5TR8n0hqyJ6gABfwvvn4zKK39SLgafNteWv69F8S2pNZdH6PNy1lax13hfczL07zGVxHw5hlLqvLUyIGhKOBcf0mBY4C86GT5AngCF5VJvIzXfkrVcFWqwQFSVxyxqQ+NASKCo8mbLQEt3kUAwdZpOc02WFcD04J/4fw02BCS6JhWeVfcBB9bHIwwWXxHETdM+WLJ9ykVOoR4qLo86xhXysFJpW3Y0rMtcbVSN8QqwZywid8dDFTzwL1ylfMOHYEAItqvnp4gfHAN+MogM5ohsibyfvqWcX/rHLlam6oadLZi6IeIZ8dEog9/pS5Cc70RU6CJr/HWO5Ebb//k8RfaESBBR85kJ6j/kqKIoekS3n+p95b2AEGFu8R/wtThLnxlNn5yQvfwEpBluVvkJjD9BmjUPnecWtNGk3N5fDB+xGXXYaSK7MJsvFT2T7nNCp85k9p5NYmWffWic0T8tsPEFRMvCMBUYWVV6NBuMBc4aQis7DsdbNddgLRrGsT9rCe73XH4HKgJDyARdVIJqnqr5/0iAeRp1snMuTfP/DJVfC5nYiCtTu2+F+y2riVZIXIr4vGSDXlWcesuZJGpO8PalAiM2DB0Qq8WWKWG5WHrLEBPYYMGp89tmU4LHI3cPZo/mQJuifI+imgU/j8rljQDTYOs3MT5GpaGSTvcOc8mCLkSFofq626fQXiswmNOeP65opbj2iJUb5sRoLwfU3lyBIUZOz9YyYVB8daC2ak1SAol/lIP2dWByFlBaYVOqQ41+3etcNMt5KJGPrfa2YtWJRnfbo+2AihyaLDSwFZQIifTAZssAX4phcv+PwXgO4VRgZFQVIT0Md9bFYRD9ZpZeGOYzSCdfQHhah8uaUOwuZjgGZ/v00VwV7yuSy4rCOiFkGhr+G634/hajlnYknTacjVvYt2OQLbcFaKaU mGB4WJhL p9/773pohzJvEacj5tenTu9hMX482sqYcVqO8sLd5oyLFsG5QbNHZC/QJhQ4KlTcmULr3f90w+s8ysbRemAuoTjP/L1NZA4A3qSXQ9tAu1jcmDNO45FunAdMyPNzU47aWXjZVcZPGAnb2BU3pZEroSzohoH0gMXnkLjCdHn3Ytxo8TvtLNptRRYQ0iq2PR7xDt90gf74MKP2wm+UuEVjRrFxbfpMfiWtUiF4cHE29rgJXbWNuVoiiKBFiprvXp34LpiwjV347ERsoNfHQeavAyM4ZojeSu5uCb1PsWtMEkn0dcjrENGt8Y+IijQ== 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: From: "Liam R. Howlett" commit a3c63c8c5df6406e79490456a1fc41a287676070 upstream. mtree_range_walk() needed to be updated to avoid checking if there was a pivot value. On closer examination, the code could avoid setting min or max in certain scenarios. The commit removes the extra check for pivot[offset] before setting max and only sets max when necessary. It also only sets min if it is necessary by checking offset 0 prior to the loop (as it has always done). The commit also drops a dead node check since the end of the node will return the array size when the last slot is occupied (by a potential reuse in a dead node). The data will be discarded later if the node is marked dead. Benchmarking these changes results in an increase in performance of 5.45% using the BENCH_WALK in the maple tree test code. Link: https://lkml.kernel.org/r/20231101171629.3612299-13-Liam.Howlett@oracle.com Signed-off-by: Liam R. Howlett Cc: Peng Zhang Signed-off-by: Andrew Morton Signed-off-by: Yu Kuai --- lib/maple_tree.c | 27 ++++++++++++--------------- 1 file changed, 12 insertions(+), 15 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index ad8bf3413889..d90f4b7e7511 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -2806,32 +2806,29 @@ static inline void *mtree_range_walk(struct ma_state *mas) min = mas->min; max = mas->max; do { - offset = 0; last = next; node = mte_to_node(next); type = mte_node_type(next); pivots = ma_pivots(node, type); end = ma_data_end(node, type, pivots, max); - if (unlikely(ma_dead_node(node))) - goto dead_node; - - if (pivots[offset] >= mas->index) { - prev_max = max; - prev_min = min; - max = pivots[offset]; + prev_min = min; + prev_max = max; + if (pivots[0] >= mas->index) { + offset = 0; + max = pivots[0]; goto next; } - do { + offset = 1; + while (offset < end) { + if (pivots[offset] >= mas->index) { + max = pivots[offset]; + break; + } offset++; - } while ((offset < end) && (pivots[offset] < mas->index)); + } - prev_min = min; min = pivots[offset - 1] + 1; - prev_max = max; - if (likely(offset < end && pivots[offset])) - max = pivots[offset]; - next: slots = ma_slots(node, type); next = mt_slot(mas->tree, slots, offset);