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:     linux-kernel@vger.kernel.org, linux-mm@kvack.org,
        maple-tree@lists.infradead.org,
        "Liam R. Howlett" <Liam.Howlett@oracle.com>
Subject: [PATCH 03/34] maple_tree: Avoid unnecessary ascending
Date:   Tue, 25 Apr 2023 10:09:24 -0400
Message-Id: <20230425140955.3834476-4-Liam.Howlett@oracle.com>
In-Reply-To: <20230425140955.3834476-1-Liam.Howlett@oracle.com>
References: <20230425140955.3834476-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?b91YwAQ5UuSY5cCNYnNGJ25TspR5uZP2C70DZrJXyw12r/10Zw5TVplMg8sF?=
 =?us-ascii?Q?B/o+ctZwDAmme9rqBF8pOZaMCdrM2TfaDmcoXFa9YOGubQib/Kuk61l/rciE?=
 =?us-ascii?Q?JvLQV+zybIjqk1Fkpp9LP3pssEkcldL0CPDuFjJpADf/YeWgO4vGkswk/BWk?=
 =?us-ascii?Q?tSYzxfG2KibT5Kn3uLIJzvVgbUi1wXd11MrnwrczAXQgxuS7ci8jMhYzeEsG?=
 =?us-ascii?Q?JI2rmQTPntxl0NegDR16/IMNdwivPMxW1q3A4V+YAkGlgktPV8weLG844ruE?=
 =?us-ascii?Q?dDhmap2/DucfnonorgMFtD42U7m4sX7Le74n7TSbwU51j7NtJXlrqaops5/P?=
 =?us-ascii?Q?7gC+TCwf+FIr09dwICoukn/+k1q6dygccPKT3cPSedOMZPTAaMMu0Sv9aihZ?=
 =?us-ascii?Q?40xeG+HPloh+mozKECT2CYKUdH36hrkhUzVzn2WIbECRebWAmfn8VV53YM9z?=
 =?us-ascii?Q?YXX8N9btCThVKw3PgI+8BzX4kl78J5C9iXKgvZraj5Lg4/22aLyZ/PkJEtTP?=
 =?us-ascii?Q?cw2POmn4otwyq2ko7mCJlXliKWhIv97TdArhSyF0vzQEScrfqDBY9x3cwnv8?=
 =?us-ascii?Q?ucKe9M9D1JUVTak5yubJCzecTIznS7oJCp9Jkpg04Kloy9qCcslTUzPTIn1p?=
 =?us-ascii?Q?U2UPibeGeiolIQa9LAAbns+KYiY4/zkJbVQd9q/41psjSSL6KHKyG/wYIOH6?=
 =?us-ascii?Q?LhKoaGFz4vW9tSaGVK8LRjpu9qGxEZsrFSakl+P84DiRKEkP9DqKOE3SK9Z6?=
 =?us-ascii?Q?dOa1CUHh40NykY1dHtOAGV5qqPUGxBcdtnav24BFIMocmfFwX+qGJ868K5Ju?=
 =?us-ascii?Q?Geqw+bouW3LxaqTnRsWsv9KGgoICGGUSf3fjidqpJiCypdMemO8222yIz1F4?=
 =?us-ascii?Q?ztuK1rC3bKwS3XkK0h5h83GR0cC2h4oNcwcrALdMhU9o/qsqlGjCpTiVPcnz?=
 =?us-ascii?Q?drAe+nH4NRdF59NxQZiYjK3AmtYm2QsdF4NqTvRCMCQeKBaa6hpeU/ZrF8Yc?=
 =?us-ascii?Q?41l/14ucSl+tRIpIjS3r8erzgbd6LHXpvoG+La9IsBJPhjz07npXhJs7VwSS?=
 =?us-ascii?Q?0fXrWqoK38dHE3fdTCQsEA3KWAfh9WuelAFrst7yCEI27wiIRaiJ3xemLJ9T?=
 =?us-ascii?Q?lcDryefKqmebMAfiu7yKVxj4/Ty7oO0wsQvNJf6FekQRg9o27xe921SI+Vjz?=
 =?us-ascii?Q?7UStleXITk+ygKP6ugdS3Qclx9wo9Ua7KC2xH68ha3xMxMEBQ9kdt5LIRDnl?=
 =?us-ascii?Q?52j8dpiKNh4UDVofAUgx0BxOYOd80pXi77BJmNJmsPmuWI3ANt0Fkqow3zwM?=
 =?us-ascii?Q?J3/ggcfxq0JiMuf9fTaKGZowHvQzX4n1aJvxKOy5gXha/uIowCnE9la4j9GK?=
 =?us-ascii?Q?tIpn4xPqQUAzV5QrDjAwWz2hLflxD4njgNaGzljwPyPKBRvuFtvRNqxeVVif?=
 =?us-ascii?Q?PJQMW/NNN02pMrUKr/o7zvY8ByVAWX5KKoeVftB7svCHlHrE7j4MLGJRuFyH?=
 =?us-ascii?Q?LdoPoCOBaOM4om/isHT9g04lLgUi3eFflE722t56wweRCytbEK4GkJH3M31a?=
 =?us-ascii?Q?eMJ1HOQi6IOkx/mDlpcHP8bZHj/sMjlpnfg1JFFdO2smPMn+TPZBxvAGQ7u9?=
 =?us-ascii?Q?2Q=3D=3D?=
X-MS-Exchange-AntiSpam-ExternalHop-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-ExternalHop-MessageData-0: gIHCGXUnHjmKk/Jb2mlDnzO+CheBkKU57YISaWftZv5UaZS84pjgZVydw/WnRtXP6RR9WgQs8IFNme4YodVKCFYDmkc5GoYAmWskuHqjjccdLrBTtrjtRNn/K7Rcpg9DubJRZlM/PfVZhSJ2UorSQY8B3hRliSGGYun6DwWsZba7nIVuM0KN/lFQKzLwcyQrVPWCt1GSLK30W/LRPl9vDeaKNHGrK/pyfffu6A0Yo9JEJUKsxlRNgC2/JO97t2FaZrmAR+T+Z+TQvv6bEua3xY/L8iNRSaflrx3kkpvHcLgs+pod1MDgYOUJP2ct2+dO8QSXXGjv9IqlytzKeSD8nNRgYFOBzxIIX+Go7kPIECq8K9Gc95QnV8+s2joEwW8cCwKpvUVp9aKZTNrBjM/r+8P76YcAxh6T8GnebDO9vKGjL8zASVepCXCxsu4krMkpQ6vDV7gAi4m+fx0sMTVpHuAMYwbdmpn4q0sSQ5HetKVrJnGXa2bWS6hk+l66A84EUrVA/qeKZqzoVy5GytiwzYp0Nt8FPmQmEQ/hmWz/4ziiyRa/z69Tfxe1KgCjwoCRMCXLrEJpGyUxo3mwOOUJfdjZ12ka7l60FcCDzGNjZWGNirdVqkm+Vx+3rRZ2N7GQpf+p+VuFMT5E1jEdPo2nJtHDVPe21SUTrqtN7tylYZgCXtfe0w4mSMmNnCyS9DtXJA3Aos9aOsvvDphBUIoQPpYOUYSB0iPyJwIORDhPx/PVCmFDs36FDTgfn8VLh43HQIr0cmU5KaLxQbtjdqexv2Tty3YMfr76xysc+n1fDMbBYPGLbGZ8PMF3hJImQuSH1CdzwqNCo5JsGszZB7gX0hHboGJVkQY2ZpKltslBLG/fKr3/DUIE2Po8WVIGtE6hgBv83LvIGwCDNKn63n+pNg==
X-OriginatorOrg: oracle.com
X-MS-Exchange-CrossTenant-Network-Message-Id: a81f3f01-5c29-4e68-75df-08db4596d19e
X-MS-Exchange-CrossTenant-AuthSource: SN6PR10MB3022.namprd10.prod.outlook.com
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 25 Apr 2023 14:10:26.8503
 (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: bJRBxFBekFYI57r1Perx/IMNDMbRE4Hwi2hAAN+fufLhyzINPTp4KpDzU1i26itHvQXPN5TGB8+7yZjx0F+bQg==
X-MS-Exchange-Transport-CrossTenantHeadersStamped: PH7PR10MB6081
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-04-25_06,2023-04-25_01,2023-02-09_01
X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 mlxlogscore=999 suspectscore=0
 malwarescore=0 mlxscore=0 spamscore=0 adultscore=0 phishscore=0
 bulkscore=0 classifier=spam adjust=0 reason=mlx scancount=1
 engine=8.12.0-2303200000 definitions=main-2304250128
X-Proofpoint-GUID: V4HQp_Vg_rE5oW5qzKzDHo32QKjSFKXn
X-Proofpoint-ORIG-GUID: V4HQp_Vg_rE5oW5qzKzDHo32QKjSFKXn
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>
---
 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:
-- 
2.39.2