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 v3 03/35] maple_tree: Avoid unnecessary ascending
Date:   Fri, 12 May 2023 14:20:04 -0400
Message-Id: <20230512182036.359030-4-Liam.Howlett@oracle.com>
In-Reply-To: <20230512182036.359030-1-Liam.Howlett@oracle.com>
References: <20230512182036.359030-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?UZBlhnd8arDdovFB+d9K0n2y0hSt3PXVsr9rQLemogc9HAWiMCTtlz2IPHr4?=
 =?us-ascii?Q?neLQ9aZ6FHcUBW4AdqDmCf0WHAsud3Sg9vqlBbiRruZq9ascvSjyap214ULV?=
 =?us-ascii?Q?MIUp10Fc265VWV08lsZhmdixxWl6Uq8yXQ4PnDMQD8O6hhnIOgoRQmdo9exj?=
 =?us-ascii?Q?ffLzXfAKqR9sKYGkW1I1BM9Sr4j/XbmUCvX5JXxC+gJMedfAJYYBCYd2w/qS?=
 =?us-ascii?Q?FTreBAS1xf9Tt0vSKLURsoZ17EpdUJdJGFyRGnJYOAtODM5T+iTsOtGrUtm0?=
 =?us-ascii?Q?Hb/KE6gfW7e/kCGfC16H6UkxeJ9RsfjHKHFgEtrcqCTfTlXa8O7lwDPpFR4M?=
 =?us-ascii?Q?6Q1ImibYFxj1njpr0Gzl2vW6jsyCNGpDsM4EwmaUgw+2WR6LWEwsk3enJhb7?=
 =?us-ascii?Q?zSUgiif7cZhuexaPZlYs+d26bOv2dvlF0+GREBb0Ydha+oCR7KI2pkW2LatH?=
 =?us-ascii?Q?fHlsLu4GSH6vbNCdI+8P0l7nQ/4xyLRED1DpANLaMDOS64DwJaCT1N12VYBW?=
 =?us-ascii?Q?BLbS1Siompy4TKvmMYvyNUgMYeWbM09gvpN80ze56zzZIak/e4BwwPAvscLr?=
 =?us-ascii?Q?JiWApCQThfw0bQHh4a7tFAMvro0anMgM62wY+9lW1rVlWJdqgFBz+UjaFx+e?=
 =?us-ascii?Q?qsN2DPfJh6mdc7wu03sCumPUGgXiLrhvI569unDzs93RONjV+XZWlLVWV7G1?=
 =?us-ascii?Q?qcDTq+nRcy+jJz9m9ojj+E1vvtdq+LpAYHVPMMUgcRsOKHo1ly5Nu5qMBi9w?=
 =?us-ascii?Q?GVeBwP+V5OCqRX6/cULV4KROKePrEnUu0+R39VUxWfOnbEUdBTo31FlyjGl+?=
 =?us-ascii?Q?kY+udr3Wz0T5N8DMMLLP3TSB6c8pFBi/3pbBb2JylwbRNAxzeHVhVvQ0d+e1?=
 =?us-ascii?Q?6aX+nkLfKSNPzYrq4Hkusepdf1JkMqY75U0RAqtGWQeVlZaHAyUIO4TQYdhV?=
 =?us-ascii?Q?gAFxbwkdgNUm1ctd+ZxQCJ6E8SBGkWead6DqAUi8X5ROD+HsPVadvOyB2Hb2?=
 =?us-ascii?Q?har9BHYfCT6/Z5AcLjRyBzK4C2BI6KzphehLR67JNigivn9zY04r6MQJHzJ5?=
 =?us-ascii?Q?OvPCZnsWM6m4ruID4IbWy9+v/LeiUkbgvJVbVN/TQiUX1RGe7TwXk2j9N4If?=
 =?us-ascii?Q?otCL8hjqsMlzAd4fzgfVs0kpnlvDJHk+3fJAOPC3esI/rHwE9pJWj/HI0kCe?=
 =?us-ascii?Q?hzfSs8toccx3q2pSVcNWdI2R53d7R0w5oZLYXhWHVDU7kNULg4hWckPQvCT3?=
 =?us-ascii?Q?XOgbiMbd4+dJLfAExD7UilBNTbNd3WZUUP+k1U75cQaF03dlcPeNhVnvAya8?=
 =?us-ascii?Q?yVa0xTiz1RewwCjky5aQ2ciKqqTWuUDhc1PGznuU2UG7R1C4V1Z6C4BccC9W?=
 =?us-ascii?Q?4z58ZAyKRvaSH+TN4BjGoVhPS+hw704doygsARZobrhXY7wLfuggEll52l9Q?=
 =?us-ascii?Q?X7zA5mW6/mbky4sqfFmWIld1SCpVgP9EOgCCSqi2sh9ul6p7s4doUpid72Ej?=
 =?us-ascii?Q?I9g/rrIsv9nzwdU1Tvz4cUtnEY1HJavPRGyQ5ad6sgFU+W7Nzslc7Ei+Ghh7?=
 =?us-ascii?Q?HTPm+/CmF3Afal9rK18HJAQUNfZLqzQmy8MoE9XXFB2lzZLlPY6sgzwJUSH4?=
 =?us-ascii?Q?yw=3D=3D?=
X-MS-Exchange-AntiSpam-ExternalHop-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-ExternalHop-MessageData-0: =?us-ascii?Q?GRW9Ah87ZBh+AYbTwUkz79/R3bVwWiyIDreHswVcUlUCpJAf08UC9LL3mToS?=
 =?us-ascii?Q?mKNSZB8vf6Fpitq0Tcv4mAn+Bp3n53vxtmFjdshY5FDwIoGwaxbzsupTxs+Y?=
 =?us-ascii?Q?jsoaj5bMYb48AVsLnv1d0KifWzXTgLyMhEbBIfUOQqQ1ZmVOHtytbhAPyml8?=
 =?us-ascii?Q?vCB9cKVVvcZkFP936tXBYEOWOgokYof5JzddHbV6RNUT0u8nl2eE7zstlnS8?=
 =?us-ascii?Q?rPLM55Uexnw01G/kBFpXWwHoXlc+0uP8Czb5zR3qKQWQSB+P9MCOEyjW/3d6?=
 =?us-ascii?Q?lGO97AvOXlN8jhcpHqIhnIHxTPpHG30CpkAhCdcpILippjYWi7U5rVaac9ed?=
 =?us-ascii?Q?cU1keVuIlZir1jY4s/CNsFRfiWeB8mOfcGTcf2ruJ701LAfOcRKpWsieHoEG?=
 =?us-ascii?Q?x7bvXSqpoyE88BYKKMbxh1YOb+/98+LhSDcxWMLgmexVyAGy9DEKpgKCNVif?=
 =?us-ascii?Q?ikPWf7egsme5Rmu0wvDLd65ADe5VUA8SkWlUmGGspCUFSvPcq5YSlBI7cJOe?=
 =?us-ascii?Q?OF20l3saiYjqbZqPJ/S7rQNASkN9eCbbvVHvlUebvBbVHdziiLlrkv8sF4Rr?=
 =?us-ascii?Q?ZEnbrb0I1TN32OtlmMH1lGo19s08Blc59HmTmh2Wj2PeAQ4O38IcU3q9WEOs?=
 =?us-ascii?Q?2Z0djJX3EVFOI2gnqFrOvYyisjLUBRd1n4RnM2z4dIccmGHORzrsRh0sG/6n?=
 =?us-ascii?Q?hxj/7vKEZ8Ioc0HOMeFTthszPPLuoH8L2g9hzQ10ODt5+xZeC6+L5qHhYF2a?=
 =?us-ascii?Q?wWcg47tYNXFttSFKNG8bbwsF68i4WrCelqtQa/6Hj6fFU8TvpxRLrh+/7lJZ?=
 =?us-ascii?Q?5rW181ueuPtahtWBOZXUc9NGvzy7eYqShjMsZOH7YgKKOrCurBwqLZ9T/w6+?=
 =?us-ascii?Q?E042t1+ivOYMQ7CKgr0x0HY3BhC1uX11x3dEkjvRtfpY/ZtNSJ5nINstEwHL?=
X-OriginatorOrg: oracle.com
X-MS-Exchange-CrossTenant-Network-Message-Id: ae32d136-aa02-440a-b54a-08db5315a193
X-MS-Exchange-CrossTenant-AuthSource: SN6PR10MB3022.namprd10.prod.outlook.com
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 12 May 2023 18:20:57.4613
 (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: Icv4zmrDEMOWwPAvndTXDVeACceBINChEQE2/oaSm7gdNWqQUnqy8gk2N+1LIeUgZxJo7jKS4FcQK43UhW+KRw==
X-MS-Exchange-Transport-CrossTenantHeadersStamped: CY5PR10MB6143
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-12_11,2023-05-05_01,2023-02-09_01
X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 mlxlogscore=999 phishscore=0
 adultscore=0 spamscore=0 suspectscore=0 malwarescore=0 bulkscore=0
 mlxscore=0 classifier=spam adjust=0 reason=mlx scancount=1
 engine=8.12.0-2304280000 definitions=main-2305120153
X-Proofpoint-GUID: 3HHVyC-czsEa0bkoVtRRgqWx7I2_SGFv
X-Proofpoint-ORIG-GUID: 3HHVyC-czsEa0bkoVtRRgqWx7I2_SGFv
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