Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20;
From:   "Liam R. Howlett" <Liam.Howlett@oracle.com>
To:     Andrew Morton <akpm@linux-foundation.org>
Cc:     maple-tree@lists.infradead.org, linux-mm@kvack.org,
        linux-kernel@vger.kernel.org,
        "Liam R. Howlett" <Liam.Howlett@oracle.com>,
        Peng Zhang <zhangpeng.00@bytedance.com>
Subject: [PATCH v2 03/36] maple_tree: Avoid unnecessary ascending
Date:   Fri,  5 May 2023 13:41:31 -0400
Message-Id: <20230505174204.2665599-4-Liam.Howlett@oracle.com>
In-Reply-To: <20230505174204.2665599-1-Liam.Howlett@oracle.com>
References: <20230505174204.2665599-1-Liam.Howlett@oracle.com>
Content-Transfer-Encoding: 8bit
Content-Type: text/plain
MIME-Version: 1.0
X-MS-Exchange-AntiSpam-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-MessageData-0: =?us-ascii?Q?9NaWmodjH5uXy9D5DX3qYr7BKEOE48IHHEmnl2ME3U6gvXEcZFxjU2Ni1yTW?=
 =?us-ascii?Q?LYD+iYfDn04v/ZlmjREJPrV/WNdUGjDdYjWru/3dR+kUjv1LHaWCfr0JQfqt?=
 =?us-ascii?Q?ap9r9cbbfEzg36sRgfZlyF2npXWajJYnYzC/H/EGxPYviavnPHDySXvkGzZN?=
 =?us-ascii?Q?2xRHE7+erOoYlD9jEYxjjTKCGtGs1acsvbCEP0IZbbCbSRzjefuY04GlPbtc?=
 =?us-ascii?Q?uUiyGVjnp4LWJBAWGRTLbhCJS/9yXoUISDPXvGQSyL9aBOIZjNe1hT06EHhh?=
 =?us-ascii?Q?bu/RYLdwBLUUPmzELklLFsOZXqURjoHr6hZdfWxgz39AZ+oHASW76hNj+ou0?=
 =?us-ascii?Q?PWfITJ/TI7Ris1b3qw2Cjl3Z/ON53QhLgGqWosloRKiSNsJUiDfRKZz5JhSI?=
 =?us-ascii?Q?B9Do75PlOYIQa067ogMuGhEhBSRGPZZWLDMWE4WGOr03LcqySXwzsI0/8NV3?=
 =?us-ascii?Q?JcaVvW9ZJpZgUHkBQPEoGrM7ZeSkDb5KnDbhvi+1H5GJNPikoxpunpIPaDfA?=
 =?us-ascii?Q?nzDIH8UbU12qpNnGymQJwGxFlT2i6CX173drD0hiyvlyHdhCLelkmOaYH8RL?=
 =?us-ascii?Q?Rpa9obB4vQowClQa2QXOiGwhaUUiNf0DPZuzTHPz1Q2MLrcJyuuFmAbQr5zH?=
 =?us-ascii?Q?7Z0MHEBlS+11WBtLnP5DPFdDlDxx9AxYRS2rjbtqqGKLHF4p+JIVd+HHKNtl?=
 =?us-ascii?Q?Wd2qbFv16oQ25PxSzNyyHHmIO/Cyk+hsB/Afeq9xrfT71VQszj0L8KydVGUQ?=
 =?us-ascii?Q?5jFCKfB0wAPbJwNCzEjs3PxSm6OPV9BEpV4QEnl8XbLwYo76fCUSEFfXVr2j?=
 =?us-ascii?Q?USuynBfXgudWIM5aNk7VCYFHAnKq9EKdIFY/JxISfC3qPpBJMCrhOvRwVSob?=
 =?us-ascii?Q?jxxoCN538FUnhYM0Xlz5SHQBQfJXUi/bAzp4ptHRpbItD6TmBCaM55IQZJqm?=
 =?us-ascii?Q?QhaT+qd25LkPWYm4YIQy2csiOgqU40rgfqDw4ttKa8eDfgBL9auFosnvOMiu?=
 =?us-ascii?Q?Pbm/F5tb2j53ANeNwVvfEQs/N6D0cq3bD7ybCL5Gu3nHsb4CxuNZ0/7G6tWM?=
 =?us-ascii?Q?w7QX06/jnMGeyCvGLRV++r2UoXQ2Q7P07G8iLD90h78YcKgcjifykvqZxKfi?=
 =?us-ascii?Q?TxrKBQz7wV/g2rp4ev5FAFd5k9Uz+h37b2S1l8f6+vN73igrd5QrEIBX+OXH?=
 =?us-ascii?Q?xtAE9wZi2OUpH1bJV+L8FsSSAhi+wrFrRYOk6t3UQ5OjrubZi9d+VJasWUJ9?=
 =?us-ascii?Q?2QYYbKV2BcyyP1/6UzGW8m0ZEn74qM1m+2SvuNGl2bQYxsnPTgn4q304xMF1?=
 =?us-ascii?Q?5QotT3ZF3Sze6BBql2JeeUeSMTvM/wKK3odKR80r+KXPrG8YNasYyCCOChCW?=
 =?us-ascii?Q?qNEW3VM8e3+bWu2HaiZKgBLeeTdGudxDqRogrcddhe5TuXXNsUYUwNuI+Xo6?=
 =?us-ascii?Q?8vHA04c8UXImSS1USQyOABQjxWg7OqVSWJGlzFtKX5DxLrs/6jFjt9EEXG6f?=
 =?us-ascii?Q?DKDGccny8G3u3lDGxIl/1u1fw+5j9tBB7WrP1PfOfZORSVL3FYrAVbPEUbDx?=
 =?us-ascii?Q?Zo0d58h4wZNV3hNwTdLo6V5YWCmN1/wUlcdtNh46OyVGx354ufWHGWWj1qdL?=
 =?us-ascii?Q?AQ=3D=3D?=
X-MS-Exchange-AntiSpam-ExternalHop-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-ExternalHop-MessageData-0: =?us-ascii?Q?ywQK4fOtA7I5hYHVQdc2rQdnfcsFatnmRb3NooBRWA/Cplq4DPj4hc6FKep+?=
 =?us-ascii?Q?hUNDvcMgwx82lTecEJWRWZJG1UaJ6a2oUzw20JOWajhAS3fn8zN+/QDLTCQs?=
 =?us-ascii?Q?Pf0CjBO6rdvaiB/fDzuSGQdr/CYvfym77L/uRE0B5k3w7w1LO5ypSKOew5Aa?=
 =?us-ascii?Q?DoP585hmzsAvE3tAIaZxLJ3wz3jPLQEiYs8N8Vhrmg/1fU55noQ3NzIz96c8?=
 =?us-ascii?Q?klpHCJkAvTydhYLhyWlSQjnoT9a8THp5/8doRkUif3hc9wtVzG+LKd2TcZEm?=
 =?us-ascii?Q?7rBpwvW0eXwVy/YcE82UKHr/OqApCR7Ulh+pmlJ3AS7vQiwkvpzw3qU++QDk?=
 =?us-ascii?Q?h+4V6HNCwbui6u0MY5SpMPzxoVLCcmuGPb2KTuDhLl2+yR+j/yQqLpp7s9fv?=
 =?us-ascii?Q?xpKLGdxzAk40mth1XqPWMU37zQ/giX3WGDCeeb5QaxTFSHVCCQPtS3AYctwd?=
 =?us-ascii?Q?u/+rtqfWKFNrwL6PYw95MRV0p9hd1EpBbBpacMhsMjqK4t6IFhoT3Zua4Op/?=
 =?us-ascii?Q?f1vzFB3SNCynO/m0HMNWJfwUeDc/FeEbk8MXUqSHT297piKs1XgFXGPUKucs?=
 =?us-ascii?Q?29tjEjR3/w/pKtc4UA/0mQ/g7z8XXMJ1LI0XDMqNw1afDAlzRclL3gVtLKsr?=
 =?us-ascii?Q?Ahos/3Peuj9vbv64X/U3ovTSdIABvbrgwpy+mPPk2ykzP97qcyeo8QZMnGJZ?=
 =?us-ascii?Q?8+UdXicY02TfsI6Aed7qXJdjys0BvwazusHzra4P6iGDrN5stHLxQSVZzwqf?=
 =?us-ascii?Q?pdhnDvJB3CVH5ZEnyrkuT1sorA7i9CxxhNtrDzQrIayskX6vDeZ6qqnWYQaP?=
 =?us-ascii?Q?Me8QFG0if4VpcZ3zndHhRbq3QxuxXYSYv1/mGZhoSZgwpFY2ZNtg9SpaBx7r?=
 =?us-ascii?Q?m/sjXXlZihB8BelQeSwF/KLsDId7Nxrz/f8AYJwTURcG0fFtg8B8OblLX/yW?=
X-OriginatorOrg: oracle.com
X-MS-Exchange-CrossTenant-Network-Message-Id: a48b9924-86f7-4e8b-26c1-08db4d9047ea
X-MS-Exchange-CrossTenant-AuthSource: SN6PR10MB3022.namprd10.prod.outlook.com
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 05 May 2023 17:43:48.1355
 (UTC)
X-MS-Exchange-CrossTenant-FromEntityHeader: Hosted
X-MS-Exchange-CrossTenant-Id: 4e2c6054-71cb-48f1-bd6c-3a9705aca71b
X-MS-Exchange-CrossTenant-MailboxType: HOSTED
X-MS-Exchange-CrossTenant-UserPrincipalName: ru2Q0H7+/poI4+jlfCi7XpFv1yVxGMoZPYz+J+dfAh57ubmjfZOuBsL1o36FQ6LRvGVZegJIakeMV3VTu563vQ==
X-MS-Exchange-Transport-CrossTenantHeadersStamped: BL3PR10MB6089
X-Proofpoint-Virus-Version: vendor=baseguard
 engine=ICAP:2.0.254,Aquarius:18.0.942,Hydra:6.0.573,FMLib:17.11.170.22
 definitions=2023-05-05_24,2023-05-05_01,2023-02-09_01
X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 bulkscore=0 mlxscore=0 spamscore=0
 mlxlogscore=999 phishscore=0 malwarescore=0 adultscore=0 suspectscore=0
 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2303200000
 definitions=main-2305050146
X-Proofpoint-GUID: J0hXzc_hJzr1QCEJs9xYqcCFlyOvRn-j
X-Proofpoint-ORIG-GUID: J0hXzc_hJzr1QCEJs9xYqcCFlyOvRn-j
X-Spam-Status: No, score=-2.8 required=5.0 tests=BAYES_00,DKIM_SIGNED,
        DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,RCVD_IN_DNSWL_LOW,
        RCVD_IN_MSPIKE_H2,SPF_HELO_NONE,SPF_NONE,T_SCC_BODY_TEXT_LINE
        autolearn=ham autolearn_force=no version=3.4.6
X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on
        lindbergh.monkeyblade.net
Precedence: bulk
List-ID: <linux-kernel.vger.kernel.org>
X-Mailing-List: linux-kernel@vger.kernel.org

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 <Liam.Howlett@oracle.com>
Reviewed-by: Peng Zhang <zhangpeng.00@bytedance.com>
---
 lib/maple_tree.c                 | 11 ++++++++---
 tools/testing/radix-tree/maple.c |  4 ++++
 2 files changed, 12 insertions(+), 3 deletions(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 555de3a8343e1..5b29d5a916f2c 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -1103,7 +1103,6 @@ static int mas_ascend(struct ma_state *mas)
 	enum maple_type a_type;
 	unsigned long min, max;
 	unsigned long *pivots;
-	unsigned char offset;
 	bool set_max = false, set_min = false;
 
 	a_node = mas_mn(mas);
@@ -1115,8 +1114,9 @@ static int mas_ascend(struct ma_state *mas)
 	p_node = mte_parent(mas->node);
 	if (unlikely(a_node == p_node))
 		return 1;
+
 	a_type = mas_parent_type(mas, mas->node);
-	offset = mte_parent_slot(mas->node);
+	mas->offset = mte_parent_slot(mas->node);
 	a_enode = mt_mk_node(p_node, a_type);
 
 	/* Check to make sure all parent information is still accurate */
@@ -1124,7 +1124,6 @@ static int mas_ascend(struct ma_state *mas)
 		return 1;
 
 	mas->node = a_enode;
-	mas->offset = offset;
 
 	if (mte_is_root(a_enode)) {
 		mas->max = ULONG_MAX;
@@ -1132,6 +1131,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:
-- 
2.39.2