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,
        Peng Zhang <zhangpeng.00@bytedance.com>,
        "Liam R. Howlett" <Liam.Howlett@oracle.com>
Subject: [PATCH v2 02/16] maple_tree: Add benchmarking for mas_prev()
Date:   Mon, 12 Jun 2023 16:39:39 -0400
Message-Id: <20230612203953.2093911-3-Liam.Howlett@oracle.com>
In-Reply-To: <20230612203953.2093911-1-Liam.Howlett@oracle.com>
References: <20230612203953.2093911-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?3RCgeonaRw7dDX9wxKXkrg7iWIv1Zc3E36aAdfzFuGzUvEbXGql+DW/AD8mN?=
 =?us-ascii?Q?n57yB8S8SRWrTdjNOjPOUvle/PKRiel4g0VvD0kN5tx1nUA5FuV37RuAl9On?=
 =?us-ascii?Q?ajnz23WIzsNFCD1k61zTxbuQ/gmvqvRNRjjQqIXO68Bes9XyvGiPBknHEF1x?=
 =?us-ascii?Q?sUXbpaI1x+9LYpc+mylPZ0wFdRg5KPhpbDr2Tp3sVeQ9qTsz+J5UCAzYliF8?=
 =?us-ascii?Q?8kBTauLdiIMprSzz9SA2gU9nFtLTYbKWcPm3l68sNB8HYB9cjuD79xs8Tg/P?=
 =?us-ascii?Q?+DKiqQueSHZwKJV+ZqeFd8nDI8PW02dPhFgug7ypEjT4Zh9/VADeFpkzKkHv?=
 =?us-ascii?Q?igOcblR3o4snYbIemv0xfw7Rsgf5LtT83uYl22Gva3Hy5h5Y9h1NhpdQFlOx?=
 =?us-ascii?Q?4HRzspdq71M5NUU3z1jOsmjMxVaMQ7mWj2cDhOS7OAI3rc24kO88eHHxvHGI?=
 =?us-ascii?Q?qm8OIszV4I3VcR/1Q8qbbl9wxjQSvXQej71KuKCG9nAZXahVSfFQdPvQGIq8?=
 =?us-ascii?Q?KzYub7v1NnYq2kjWUPyt1+YeYlBOodL2oC+lMBage+Tskl86oMgZL3JAo6ZO?=
 =?us-ascii?Q?eEQwpM2t2WRQoEeRPDHGFIBVO5hY9jUOi9yXYiluglsJbiTET+NEckbK3ncp?=
 =?us-ascii?Q?nJ377TfNep1vWVtqMFLUWBKqw6DtIql8gJWuGJbJogdiqS8AD9q+EuJodnDI?=
 =?us-ascii?Q?Hn0Axz6vqrtTIw5AuCdPmoRDRqoXgDcMAuzyg02bZRnDGnQNlhFg94Cr1ukB?=
 =?us-ascii?Q?MgWXFifjNwcv1FLMqPVFums1ua58LwzITYsPSRLpzuvC15OMGpcGlq0xzgtE?=
 =?us-ascii?Q?JdhdGC5tcBbCLw8b4brp2UBkIvRyQdzZIGR+AgLgufcomvqh3MagmbNFQHSW?=
 =?us-ascii?Q?07FYP9Zf5vlmageXtl9V+HCq0CtoB7vKDg1xmatdwZanRe+xaxmTBXTMPT1d?=
 =?us-ascii?Q?mXDlYNml7ZwYGW5sn8Qra0RhLSZGnAXlVnWDuS/nvV3e617ns0zejYBQZDQ6?=
 =?us-ascii?Q?DtpwXhHSXAzppNkbIaaYhRHThy1uPkY1WjYw1HHB0ZnkzoNBEp8iFqp8cIwy?=
 =?us-ascii?Q?10mmwbe8xflW8k2N0rIaSyafJsQ7CCUtj0XBsPVT2uQs5Ks0jIH77wACz7sC?=
 =?us-ascii?Q?cf85fQ5fSpSdnUvc4RsKwMo7kkncY5dPLzFfTrXJOr81z1VdwN+moEdBt+WK?=
 =?us-ascii?Q?hsGAp6O0T45Sd8a78n4Ynly31rnVC2WBSp2uFSExrzqqi0DeV7dXs89qw0Pb?=
 =?us-ascii?Q?c6gLNL2Z1EDo/G4cogbDGpoqkEsNtl+rise+9aGszO57EpWTDGEYOlSPnA1h?=
 =?us-ascii?Q?LdWJJ8bM+QhzjG2JCOEiY/516BJr7JfuxFTICqxDkYrnLeSeHQOAdDZHYLWU?=
 =?us-ascii?Q?fnpP9kLS7T/uZPosPl83dp04rnbAJXRzUbewrL38a3IdL+yWryN+H+EZi9F5?=
 =?us-ascii?Q?+ox3PxHB2BvxZfP5eSATZ9PvZ95dIR6rQ4AHvkPIoCx7g+bcABtyzqfx7UaP?=
 =?us-ascii?Q?BDi5OXuhxEm1UwEbvHCokZpxLCiw9XysHsV6xvBKTTZ3PlmEr2QrsIwHTKes?=
 =?us-ascii?Q?wT5CDHpkKLIUlBEfxRdICBYNiMGmW5NHVfj3CQjX1cdUBZyBsY2ij3tfT6DJ?=
 =?us-ascii?Q?gw=3D=3D?=
X-MS-Exchange-AntiSpam-ExternalHop-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-ExternalHop-MessageData-0: =?us-ascii?Q?QRLEXBfGB0vhOyawo92OI2bwTlVWwibfh1Tzyxn5yaob77UF/9eCZqNW9H64?=
 =?us-ascii?Q?mmsmPz6kaXuP0YuFmzYgqEnpTFQDO57hXT8opJYcLJU1rngemRO7wIqMri1u?=
 =?us-ascii?Q?DsXnwQpRaHInRQ++OMZv8EsQ2H5q8SrZbKn4mCmkSEXReyGDulYNMnta5USK?=
 =?us-ascii?Q?7454xVDxLBpWcGpUwEhe6HSHbZgLkGUDxgH+q+MPHfnKyCMaBuvfJD1buHL1?=
 =?us-ascii?Q?qbmwchoUjcthXrBp1sC2kiI4/q7IJb+BkQkydF/OpRqxuuVg2dLTYeulBEpA?=
 =?us-ascii?Q?02UVujjc5cCarfz4sT4LPS7vSZnMT7gcnrmkfYTpWtYQyxdI3aznZujoN/AG?=
 =?us-ascii?Q?yxdaY8s2O2DYfy/Y43szbebkx3cGVbcfgK8zznQEyMXd3BQy0exTmYIbv7Pe?=
 =?us-ascii?Q?0yTznWbmCf8eWCg4P6kFh/DaA0IzP20Dj27E9Btc/ighpNgIsDDLmqAaGpan?=
 =?us-ascii?Q?GBrqw59xcjJ31TeIQn8xjdERQi/MZFGAdGtZd6tO+0i+XgS5Gnl78qiC8SZy?=
 =?us-ascii?Q?+Sb81F7iFfHWZyx3zSkO49abKtl1Jok/b/J9OSLGLB/DiiSOYX6UvYHl+Tom?=
 =?us-ascii?Q?hMURJPrHz2h7KD1FaNNMjNua4h1izxynbuPStJtvhVHwBLiz4Jllrm6rFsry?=
 =?us-ascii?Q?10iOoR8hjq3rVBq6B+mTcECVIjxaWs6JGec6LWmtOm6YpbnXQpPwyef1rrza?=
 =?us-ascii?Q?VkclPo0s1dcVxYyvNUjVXVug8V5NZRUW3XhnpMvy7+bxT7L4/SFy+V/mSals?=
 =?us-ascii?Q?UzwTKq7s4psykA5PhLg9K6w40L1doI8TfAJc6Qo8WvMglFGJkApMsmGGnZ65?=
 =?us-ascii?Q?prq+jTuFwpC3TK+AkqZsIkFVbY9dMWv0LHpvAMk1BFg8Ve1q5appqCtttHq7?=
 =?us-ascii?Q?X7UdlKiD+xL5tCyCkHsLAV+LEEQ+o32PQyn9u3ylXmPrGwgUzfpEWwhYjium?=
X-OriginatorOrg: oracle.com
X-MS-Exchange-CrossTenant-Network-Message-Id: 4ae038b1-4ff5-4c42-b3f1-08db6b853321
X-MS-Exchange-CrossTenant-AuthSource: SN6PR10MB3022.namprd10.prod.outlook.com
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 12 Jun 2023 20:40:03.8925
 (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: ox+Q0+Zdm2QO/pUZgOImBn6dBfEYyBoNwYBDyGHFE1+cYjV+OhKfvUV/d/g/qD4iuaWdAVdnmmMhtp2+Ui/UUw==
X-MS-Exchange-Transport-CrossTenantHeadersStamped: SA0PR10MB6425
X-Proofpoint-Virus-Version: vendor=baseguard
 engine=ICAP:2.0.254,Aquarius:18.0.957,Hydra:6.0.573,FMLib:17.11.176.26
 definitions=2023-06-12_16,2023-06-12_02,2023-05-22_02
X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 mlxlogscore=999 bulkscore=0 mlxscore=0
 spamscore=0 malwarescore=0 adultscore=0 phishscore=0 suspectscore=0
 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2305260000
 definitions=main-2306120176
X-Proofpoint-ORIG-GUID: s6Lb2icNYkDxG4qP6CNl4pjZmHmfNJlK
X-Proofpoint-GUID: s6Lb2icNYkDxG4qP6CNl4pjZmHmfNJlK
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_H5,RCVD_IN_MSPIKE_WL,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

Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>
---
 lib/test_maple_tree.c | 36 ++++++++++++++++++++++++++++++++++++
 1 file changed, 36 insertions(+)

diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c
index 3dbf99c3f2b1..15d7b7bce7d6 100644
--- a/lib/test_maple_tree.c
+++ b/lib/test_maple_tree.c
@@ -45,6 +45,7 @@ atomic_t maple_tree_tests_passed;
 /* #define BENCH_MT_FOR_EACH */
 /* #define BENCH_FORK */
 /* #define BENCH_MAS_FOR_EACH */
+/* #define BENCH_MAS_PREV */
 
 #ifdef __KERNEL__
 #define mt_set_non_kernel(x)		do {} while (0)
@@ -1735,7 +1736,35 @@ static noinline void __init bench_mas_for_each(struct maple_tree *mt)
 
 }
 #endif
+#if defined(BENCH_MAS_PREV)
+static noinline void __init bench_mas_prev(struct maple_tree *mt)
+{
+	int i, count = 1000000;
+	unsigned long max = 2500;
+	void *entry;
+	MA_STATE(mas, mt, 0, 0);
+
+	for (i = 0; i < max; i += 5) {
+		int gap = 4;
+		if (i % 30 == 0)
+			gap = 3;
+		mtree_store_range(mt, i, i + gap, xa_mk_value(i), GFP_KERNEL);
+	}
 
+	rcu_read_lock();
+	for (i = 0; i < count; i++) {
+		unsigned long j = 2495;
+
+		mas_set(&mas, ULONG_MAX);
+		while ((entry = mas_prev(&mas, 0)) != NULL) {
+			MT_BUG_ON(mt, entry != xa_mk_value(j));
+			j -= 5;
+		}
+	}
+	rcu_read_unlock();
+
+}
+#endif
 /* check_forking - simulate the kernel forking sequence with the tree. */
 static noinline void __init check_forking(struct maple_tree *mt)
 {
@@ -3468,6 +3497,13 @@ static int __init maple_tree_seed(void)
 	mtree_destroy(&tree);
 	goto skip;
 #endif
+#if defined(BENCH_MAS_PREV)
+#define BENCH
+	mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
+	bench_mas_prev(&tree);
+	mtree_destroy(&tree);
+	goto skip;
+#endif
 
 	mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
 	check_iteration(&tree);
-- 
2.39.2