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 316ABC77B60 for ; Wed, 26 Apr 2023 05:28:07 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 98C6E6B0078; Wed, 26 Apr 2023 01:28:06 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 93CDB6B007B; Wed, 26 Apr 2023 01:28:06 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 804606B007D; Wed, 26 Apr 2023 01:28:06 -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 7059E6B0078 for ; Wed, 26 Apr 2023 01:28:06 -0400 (EDT) Received: from smtpin03.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay05.hostedemail.com (Postfix) with ESMTP id 2BEA140165 for ; Wed, 26 Apr 2023 05:28:06 +0000 (UTC) X-FDA: 80722410972.03.AE10DD8 Received: from mail-pf1-f173.google.com (mail-pf1-f173.google.com [209.85.210.173]) by imf19.hostedemail.com (Postfix) with ESMTP id BB4861A000B for ; Wed, 26 Apr 2023 05:28:03 +0000 (UTC) Authentication-Results: imf19.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=fDYawT5v; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf19.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.173 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1682486884; 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:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=CxdQSe72d3sjq+Prr4mwyPnfSSkLPwhzfDnldlQ4qk4=; b=ftsY97rUGeuc8Bb9z19MktbaDUOqwjmwuTQi4yj7TlehDNMcubZf1lxIxRc4+fLVjAfrio pvwe9yCAQaBI89YYPymqyLQUMAUBiGM50jxcFetmOah3Zlf8lkEZWTIzNIXGiGufwoVYtp BhHxKe6gUkjQKqf7Qd5itfM1B2sd+4o= ARC-Authentication-Results: i=1; imf19.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=fDYawT5v; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf19.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.173 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1682486884; a=rsa-sha256; cv=none; b=dlR8NK+CsC3rYiEB/0tU3x9rMMn++taGg/RtzvQ4Yc0VJaawywJlPZEvnXrToYgWCpg2S7 ldaRDjbgJifKSL9RjBThlxSJ9AAMYtEXq39lCsQ3jcCFkXa+ZIQvIqrl/w7sCj/Y7MWGCy 4XOcH8gF1oi+ffS76/9E5fEwy3B6yDs= Received: by mail-pf1-f173.google.com with SMTP id d2e1a72fcca58-63b4bf2d74aso5279834b3a.2 for ; Tue, 25 Apr 2023 22:28:03 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1682486882; x=1685078882; h=content-transfer-encoding:in-reply-to:from:references:cc:to:subject :user-agent:mime-version:date:message-id:from:to:cc:subject:date :message-id:reply-to; bh=CxdQSe72d3sjq+Prr4mwyPnfSSkLPwhzfDnldlQ4qk4=; b=fDYawT5vqUlOtaRh1EOPfxUV9+CjQfLaHmQT3OZlTb2X+Diy2M+p+l4YVuPj57dXs7 BkM3anEZkn7XVQZZW9enjlZXWrr9+CR7ajfSVVyQ+wNWHAa9vy7lfOonyQARdinKv+yB cMXKuqJ9wX9bnDFiIyDRVT8bls7XQ5LxzT7KpqZn+Wn5VNIiuUJsmJULlL9Vowd6jxiE A/fMun+XkJmK0xbL4I2TJ1J3/SGIDwNMxYWEQzmrhsT+7SOcqvlf/YBjil6uGaG7JSCP Ivv8PIYRvU6iFXLhzHJn82CpRYnTyIuvjp3FxM1uCthYqZoY2k1Q0lZjsnkWoKU37xK0 F2KQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1682486882; x=1685078882; h=content-transfer-encoding:in-reply-to:from:references:cc:to:subject :user-agent:mime-version:date:message-id:x-gm-message-state:from:to :cc:subject:date:message-id:reply-to; bh=CxdQSe72d3sjq+Prr4mwyPnfSSkLPwhzfDnldlQ4qk4=; b=f0T6OuizkdgV+W1Os9nWESPL2wvI7a1jloN5611xQUYTZkCwCGq4EtmVNl9f1pN+CJ 8Zl54HNQc2SAhGHcrWOkK4LB2hxgt5cYikzjyvJFQn8ENw1yEIdqEQfMzuj+li/5UJCi CX+ZYCFOV77PPvF4uqLXKkD/Xg/49tC40KUKtRyb7SugDl54lFAxnkX6B+q1ofVaEcuI SGYZe6ISzaoqQ4uFLseMtJtR8eSg6YYEdQhkZuubLFDgghI3vEFzRUJ3VSDIuPcKKMNQ s09L4aF12Q2e1Mg3Jp0PGhFi2z7F2WJ6GGldLVcJWeeI5/1xdmJ+xD5A2+LCzBGZgsZX Cbzg== X-Gm-Message-State: AAQBX9dP3iZvjuRH1mb0wV1lZ6DYO/BR6oiQSHT6vY8gIym7IW/NOOeY QnH7afWBkYBajC39gtBFPm/D3A== X-Google-Smtp-Source: AKy350ZMLKluC5EfzL5S2N9tE1EkG8ZgnFTB4pb6O7Vf48KbS830aXZAy9Css9lqbTdXUeWlxDg/jA== X-Received: by 2002:a05:6a00:194c:b0:63d:2680:94dd with SMTP id s12-20020a056a00194c00b0063d268094ddmr24783165pfk.6.1682486882290; Tue, 25 Apr 2023 22:28:02 -0700 (PDT) Received: from [10.200.11.252] ([139.177.225.236]) by smtp.gmail.com with ESMTPSA id u26-20020a056a00099a00b0062e0c39977csm10260586pfg.139.2023.04.25.22.28.00 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Tue, 25 Apr 2023 22:28:02 -0700 (PDT) Message-ID: <25ea9d02-a941-3ab6-8ffb-e6394e2bc027@bytedance.com> Date: Wed, 26 Apr 2023 13:27:57 +0800 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:102.0) Gecko/20100101 Thunderbird/102.10.1 Subject: Re: [PATCH 03/34] maple_tree: Avoid unnecessary ascending To: "Liam R. Howlett" Cc: linux-kernel@vger.kernel.org, linux-mm@kvack.org, maple-tree@lists.infradead.org, Andrew Morton References: <20230425140955.3834476-1-Liam.Howlett@oracle.com> <20230425140955.3834476-4-Liam.Howlett@oracle.com> From: Peng Zhang In-Reply-To: <20230425140955.3834476-4-Liam.Howlett@oracle.com> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit X-Rspam-User: X-Rspamd-Server: rspam02 X-Rspamd-Queue-Id: BB4861A000B X-Stat-Signature: qzwkwa3hrb77rme9n1erh1uhxm1r8hsd X-HE-Tag: 1682486883-601470 X-HE-Meta: U2FsdGVkX1+8hBNzjAtgl7Ld0zlbYOLxpQq1AvPtvhhLv/tyM5d0glwKP3VakHBiwsO2HFGYOd/PNWGFSQUqCr102GJqmbI2HqYFTvgNqMsOeT+Yy9zHsCpoP+M6njFoupJV6Ste8hyuMsW28NM1uBPS9xTOO1mwQ4gncwgB9dr7hi7BW+dBRjvhm0JahkZKcZ1xbeS/y2UeqAVSpIm3kQ5zPVPzJBWlOA4p+RB4PqhGoB43mOIXLyHs3Hx2rmhKz4pISgTdAGdSWJeU1nQYw+bqOx7bT9GrqpOFbbgZ7owHEFcqcuhPDkVM9+z4CYcAlH1obgXS5iOcDA+85D6G4m8RUI1tQS/IL2NNu/MkgiPu6BYX9WDHbfWq5U9RgjaJgabJddZamPf1CW+RveKV3cJBPbh6fsmzoJdQxAmpaxwL07W2biCt3/cDuXrQOE8v4PsKI2cjMQuHw5f1ZmAyGeRDN3Q7LfTaSv2Ncily77UEC9HOJJqr+B/0BRESYOHBtONxh4YtWb99fuzj34EtPGrGDVCiG3LDTIokqD8xTKeLWLc7FBoSM0cFekJjQ5mIw8r4zHrzaWwNOC66j0EO0UsXYnlNy6iWnOAfT6rZVflSlIfdB8gJWvG6UkNvjljCkNIzpRXc0ZamZEI6Nyc63mmcYcbuX75/+mTRgd0t+nW62L/wq05M33h/0i22z5ut3rM84eQii2WKeIKK0FUXvhV4eFobWlFOiRmAImARHMuhDLtfIinlyj73Yc4DIYk2U+OUdwMyCVD1McGBlupKN7XoqqtxNMn38JtSgsHjdrl73TLFpdxesNHlj9RxaivbgbLHFgX6EMp+kETZD7YSHnIoj2x/MAq0rhqZg/XLqgOIXYXGKYEoF6Srfd4lbjMvFeq9kzTfHNHahEYdgK10xeSUv5SuGf9JWqxLicYRRGAF6C2Q3kCm6e48SZYg0VjlUtv5CtOi0mXAVKDEkTn j8KwxYcV 46xilpCV6pXSYMQM4dJSNucjO7g1tWlQeBiHv6xBLgy91ojxhgHvIzn8ZzDkfTguy7jRIJIQdNJ6Ka8lN6a9f3L2UnS1BKfTFcLXlbnKWJJa0R75QY3uFXZZTG2cKhppFyS9PlHYDwKfFZoZ0WbpoYYPGDw6etIRYNdjq0Y38iZzxmUCvxDNAxaby5PsbuzHHs6J+2UyaJyW/wBNeqA45iSErHbV9GrDYmE0FwTeK+qu0lWd7mphi0U/2IqJq+7IzfkHyX4m+pzvHKOpiyyrcwJlED73YNexe3nI3DuFZXWOr9m2K2+8uPIjogJgHhs0XL6TsZKvszx9hVtZ0B8R/Qmkwkj2wIFbj7TGAViLaymKjt1hfNdq+7mqzOPAdjntXKTqYxeqqbGUjz2IUSvtlz2iUxEEpIvwsBhvILzWQC0bElcHp4dDQYpkNTD6L5lEVLVVpuN0QvCK6MyqtSq63200YgYbO/iHI3OGavI1bPQNb2Dw= 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: 在 2023/4/25 22:09, Liam R. Howlett 写道: > The maple tree node limits are implied by the parent. When walking up > the tree, the limit may not be known until a slot that does not have > implied limits are encountered. However, if the node is the left-most > or right-most node, the walking up to find that limit can be skipped. > > This commit also fixes the debug/testing code that was not setting the > limit on walking down the tree as that optimization is not compatible > with this change. > > Signed-off-by: Liam R. Howlett Reviewed-by: Peng Zhang > --- > lib/maple_tree.c | 6 ++++++ > tools/testing/radix-tree/maple.c | 4 ++++ > 2 files changed, 10 insertions(+) > > diff --git a/lib/maple_tree.c b/lib/maple_tree.c > index ac0245dd88dad..60bae5be008a6 100644 > --- a/lib/maple_tree.c > +++ b/lib/maple_tree.c > @@ -1132,6 +1132,12 @@ static int mas_ascend(struct ma_state *mas) > return 0; > } > > + if (!mas->min) > + set_min = true; > + > + if (mas->max == ULONG_MAX) > + set_max = true; > + > min = 0; > max = ULONG_MAX; > do { > diff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/maple.c > index 9286d3baa12d6..75df543e019c9 100644 > --- a/tools/testing/radix-tree/maple.c > +++ b/tools/testing/radix-tree/maple.c > @@ -35259,6 +35259,7 @@ static void mas_dfs_preorder(struct ma_state *mas) > > struct maple_enode *prev; > unsigned char end, slot = 0; > + unsigned long *pivots; > > if (mas->node == MAS_START) { > mas_start(mas); > @@ -35291,6 +35292,9 @@ static void mas_dfs_preorder(struct ma_state *mas) > mas_ascend(mas); > goto walk_up; > } > + pivots = ma_pivots(mte_to_node(prev), mte_node_type(prev)); > + mas->max = mas_safe_pivot(mas, pivots, slot, mte_node_type(prev)); > + mas->min = mas_safe_min(mas, pivots, slot); > > return; > done: