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 v4 03/35] maple_tree: Avoid unnecessary ascending
Date:   Thu, 18 May 2023 10:55:12 -0400
Message-Id: <20230518145544.1722059-4-Liam.Howlett@oracle.com>
In-Reply-To: <20230518145544.1722059-1-Liam.Howlett@oracle.com>
References: <20230518145544.1722059-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?/xsxNDx21mQChfAh0TwzV004f+Vwom76rf5ImhFg3YGRn88kpPDTlwRm/KEa?=
 =?us-ascii?Q?aKGjptTx5UoIJIFgx+Uc2erxPqOH2RrUENKoGakQL+2z6O37TG1o5Wu/PO4b?=
 =?us-ascii?Q?YBVSI7qPrlzB7SHzf90dxikfSKTrHPkXH3Oxb+7565hJqya29YoJYJUAmcDd?=
 =?us-ascii?Q?lqbFHI3x2grY3fIfdMs970PlP2KHMy3z2dneqH2Fnu9Llk01rIQLAA+SnIwa?=
 =?us-ascii?Q?eFcroMXsWN466xckahW0W7DO7prPR7rsfwkH0w37wlc+RbpVZybSwye5b52o?=
 =?us-ascii?Q?/0/faDyzjKjLMeESS4HbCUhZLzhNhzjsDV2QfxYvkqZNcaPfSDQz0AbsP+UY?=
 =?us-ascii?Q?lKpUJcQvxC/GWpDlz7Vdmn6uomGanqUNn/VTF99/sqnT9q6y1pY5CRBR65Gn?=
 =?us-ascii?Q?kGW6h0zbe42ljWHNnVIxFSz52mEp8Scgr7Bgw4b7CbFSEJtCJWFLv22EjpC4?=
 =?us-ascii?Q?LsZEJF0U54qC3PRrz5ccASgzuFvVNEd/uQNzuFCw7/2Oog2j67cU7qK9rewm?=
 =?us-ascii?Q?pxFyZMqOTgcS68XVd868HEfuU7cp3dejwFppL3JFHx1xp9trwp4rVym/Y6jJ?=
 =?us-ascii?Q?b6TYJyk55cwQTiQGvlSgA2D/F56G0B+UClcar1fzZP4TuEnsQUJMhB3KIJVo?=
 =?us-ascii?Q?XM1IMgf7RyfCDGWJr//93BdzZ9v38YZYvlTE14WqNLE/ZYIbiljhkZmbpVJz?=
 =?us-ascii?Q?fd3+3UO3OVPkX2fxQwlzACYm+xnDhbHF9++N131aHKGYEh6OGRurhkBwL28g?=
 =?us-ascii?Q?FNTCZvDSENSujKq6SoMDBZTtZYQ8ttHLFxv2mkJ5gqKvJyayHD9vxJ1CNDgJ?=
 =?us-ascii?Q?tlOdpWkxrtfyTfA9gu6XlHSVBNXwrGBmwAGHEIzgrcO8Niv0mhclYATBt7Mp?=
 =?us-ascii?Q?G5Odm7F5OvFGWf2+7rFAQ+iKIhRpJBSCzNdAeEMAao45697QglPT/btdQKqC?=
 =?us-ascii?Q?7O/uzahR7ZDv4svID1pvzI9I5UIpLfoaBm/iFJrSJSUx80D3b6mcmTm/ytoz?=
 =?us-ascii?Q?WO3NpdtAcmIy/UMGpge9cKZScYMjrRyAidYru3aAYav0HGzpllKAOdzyPxlT?=
 =?us-ascii?Q?/t/RjvgllfnLDN/1UQlg1LszNPeaAeeBUsUDW2hXfl8Ax+w/QMRGc5HJZH/e?=
 =?us-ascii?Q?dpZc5E6NyjWnWtRON2rwNfwybSoN7yFjtBOpaU2xWJAmpszCMsPlcziR7nDc?=
 =?us-ascii?Q?GD1pDVZ2BNw5MYSexEBAaLIOMHWFkjCXul0JJcMGPc910yTx3wjgaZB2K3/e?=
 =?us-ascii?Q?8Z+uU7DMJk831tMZpda2M+LsClTyx0UMye/4R0Dd6BAwk4/dxVAu8Il9y8PQ?=
 =?us-ascii?Q?5YoJBvd+UdK82zROwDpzi/IZD/rRxfXZGXvCpa4a2/DP0q7ccI6l0OF4Rvg4?=
 =?us-ascii?Q?ZZDj32c9WMlOe9NMg1TrTo4lHPeqT125AIG/kBTElPFlxD0B0/44AQJnUjEV?=
 =?us-ascii?Q?jXueHk8ify5BZiWXGp0isjtvZjiv3RxRTQawvFJdpfer0FZLl2PwtYcFOT4o?=
 =?us-ascii?Q?OsxYmXhGstOiVCJUmVMzSGx6Bn3jCDYPAC4IR9WzH5yJhDWoa+waj0XfPw6X?=
 =?us-ascii?Q?mCea2ZyyPP2kmueOFZLbk4Wfux2ulkr3orB6t5n/Q7wmwlI4/ZJYaJUZCN2T?=
 =?us-ascii?Q?6A=3D=3D?=
X-MS-Exchange-AntiSpam-ExternalHop-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-ExternalHop-MessageData-0: =?us-ascii?Q?xxJwQYJGZBpIhm7PTUDXVFmF2EY4beea1zuykTTjR8EbnprvUjepjCqWUm4W?=
 =?us-ascii?Q?1j2RgIFBkiQV4e4LdHnV/HoJ4xoE2aPcBCSFMpGSpQUrS3DgOQsitpWZRryr?=
 =?us-ascii?Q?8M402vSHBxgCbGeazY71fV9QvYPHQL+aMW2ok8O+D6CRU3jE2tma3FzWMKl7?=
 =?us-ascii?Q?AA88ANO3qHRVEGaF2FqCim/CDVbZFzUsSQ6rBamlonc9lUsUZ3TlzH90WgMY?=
 =?us-ascii?Q?wDke4YJX0BS+pEpNTL+orfmQrahOLCI3onyvXZ6UnifFePxdRLc+FgPFMd3c?=
 =?us-ascii?Q?sdMDKNuxG2sASfrpj1rh5m8C5I6wYNjvI4GCzis85mB0/tdFVGDtZdwUvoe1?=
 =?us-ascii?Q?LfFE1V1GrcJ3nXBl3Q+81Um3PGBH+NTite9SYW/jSTj7DEUg4lFB7LFGD1zU?=
 =?us-ascii?Q?MOZAKZ3R8R9eluQ03Kj2dobwp/RiVC2j/z2pkOkDUlfUqUfkjyPXblrZzi7C?=
 =?us-ascii?Q?6yCckgJ0UHFAFEiC5Wl0URM+TzHg28fLCijlmic+JuX5cR4xMvVcKp430Z1+?=
 =?us-ascii?Q?eeM4QMzYa+2N5QqHQnMBjapivJG/9m6zXaLZPlOQC7W92vmQCv/zAbLkTSJV?=
 =?us-ascii?Q?uopVGAu+h1Ml24EPeVjETD19EXjOLOET6xR9bCfWFGAb3P6yoQSDUAiZNmVf?=
 =?us-ascii?Q?49Ic0wtsK732sj0Caf8wPF+u/J8aWT1CZxnujWuVQkaDfg98E3cqZfhAM5BK?=
 =?us-ascii?Q?NxQ3BTYM1IH2Pr8l1F7Riln6tFf9VbtKEnPtcF9y1rafTNsrfHNP6St3GQbJ?=
 =?us-ascii?Q?0WDiYmdy1fWntbN0j/amg9dwY4stWLS8BOgBVmm5hIbuxa4nVDH964qfHhvq?=
 =?us-ascii?Q?E+Eysw4ZGQLgccPRPxtjQoUsKEnPJg6AfPXeMy6nfCIYQrjpOy933B4xmk5r?=
 =?us-ascii?Q?YMfm+2+kzQyGCOfQrqs+zQIKzkk9EfLb8DV2J3CKmtEeHB4roHxxQwRVNeie?=
X-OriginatorOrg: oracle.com
X-MS-Exchange-CrossTenant-Network-Message-Id: 1d85856c-561c-4165-7c6c-08db57affc09
X-MS-Exchange-CrossTenant-AuthSource: SN6PR10MB3022.namprd10.prod.outlook.com
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 18 May 2023 14:55:56.4004
 (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: tsE602Tujvc6t/7rMxx0e+yKe8m8P0D3ys/uwcWnvxoQhQ91xLgQeN+CNnukBDBBEtEZOHLlvxRfoV7kYDV5iQ==
X-MS-Exchange-Transport-CrossTenantHeadersStamped: DM6PR10MB4347
X-Proofpoint-Virus-Version: vendor=baseguard
 engine=ICAP:2.0.254,Aquarius:18.0.957,Hydra:6.0.573,FMLib:17.11.170.22
 definitions=2023-05-18_11,2023-05-17_02,2023-02-09_01
X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 suspectscore=0 adultscore=0
 malwarescore=0 bulkscore=0 spamscore=0 phishscore=0 mlxlogscore=999
 mlxscore=0 classifier=spam adjust=0 reason=mlx scancount=1
 engine=8.12.0-2304280000 definitions=main-2305180120
X-Proofpoint-GUID: 6tVROkeCYLwVLJeX6Y0Nc5EfrzMLcO_E
X-Proofpoint-ORIG-GUID: 6tVROkeCYLwVLJeX6Y0Nc5EfrzMLcO_E
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,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 555de3a8343e..5b29d5a916f2 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 9286d3baa12d..75df543e019c 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