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>
Subject: [PATCH 02/14] maple_tree: Add benchmarking for mas_prev()
Date:   Wed, 31 May 2023 22:15:53 -0400
Message-Id: <20230601021605.2823123-3-Liam.Howlett@oracle.com>
In-Reply-To: <20230601021605.2823123-1-Liam.Howlett@oracle.com>
References: <20230601021605.2823123-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?sIK3dSqnxTcUzFKrJWYu5+gRCteGE8JwrlHJpFqUWZciw9bkavpZ+4EVv56f?=
 =?us-ascii?Q?5PYNX47dYnUpops+/mthf6D4UvGxVzucUaF0VHJVjsEt9VHdkxCiAvA9KuFA?=
 =?us-ascii?Q?Mx/Txz4VyEO6q9KAOjHI5hnQ4z5cvbR+B4d4DfYEoHcm+Fj4O8LF6uA4PTnl?=
 =?us-ascii?Q?I1lomJ+IuN5E60wV0lXOwjiLogPCTBz1/C0XTFsHtbrRUDpPqqbENjY1umsM?=
 =?us-ascii?Q?wmAKCs2w+vWK0hyLH7eP3ofhNxjqirlMElGKBgXxIzD4WzImLRBY/3C/1KP6?=
 =?us-ascii?Q?dKOLSIXbC5UXpSx4b+g82eBJ1YJ07T4/xuxnHZiIvVBwqvZIlP+2E73K8wma?=
 =?us-ascii?Q?eaeWKOu5MH8dcBAS9pLoB7dWZoZCnDImrcpUUN3Iahi26mQmcJ4ll7J85WCC?=
 =?us-ascii?Q?//v450TBU20ANgzixPqLsZtNH273smLTIoN+FmdlTLuLwLul4LLPAiDp8SFY?=
 =?us-ascii?Q?dHT7NX/+SrSKNmQ048VOMHoFGxnXeWYwQXpSU+/pkFegIFrg9Ocqu8PExWxv?=
 =?us-ascii?Q?g8psPbg5ozMGST0aiMYIpWhixeTkcse+7NdfwJbx1MWpXSQqDd0AbLMC/XWZ?=
 =?us-ascii?Q?CBCDiK9sr+FpKXc7UV6DsD+WD1NXj5V8milzyxOoml0dx93ZPao7FT8652qe?=
 =?us-ascii?Q?IN/0AXINKKDoDnAPYnx1voEuswEAzeWAKApeK05CO0W0vEY+7r2UwK2dujEv?=
 =?us-ascii?Q?D/qhN/38Ac3vuGZW1CjTEp/d2cWWzHikuKj7LzhNutNsGP8ingi466KkmAjL?=
 =?us-ascii?Q?kMTOTioWwI41kTAAndHEzsypdUyWIwgSk778mJU2R2U9MCsz2S4JlglE11RI?=
 =?us-ascii?Q?Pt//AkphHiv3ITVHevHGNYHujIJ9Ukc8AXYVtG+j+bneDb0fxsQ2OEMXp0PI?=
 =?us-ascii?Q?yHLRKGgKEmd8EoBgON4kyxh1NZ6mRsIdsDOM3htJ/gfY33N3iY59wJBq8H7Z?=
 =?us-ascii?Q?2Siq028AY1kF/twWLS8YZ8t4BCa/+YvtdXJIKe2Gp+VY6YvT3OhOLxr8BYws?=
 =?us-ascii?Q?UW0ZUuo73qZaQAc32/WM2W6n16m4X0p24IboZbutanBoyYCCupZtT7RdyBj8?=
 =?us-ascii?Q?b8Bkz3aDLkyEOngNENES5KjEGvm7QDdmhI81Luq0/X0wmS+hJdLpTNXCw1Z6?=
 =?us-ascii?Q?2HBxVzwARJwE0UEIaMt2aUoNNtuQUxr1wiwQoA6FhYRCTa/fOylr8fDGB37Z?=
 =?us-ascii?Q?rBjuqVPsuQYKH8xspCIJKlLGWy5todikuUfCdwHaLrAFq9IK0ZJPV/prF8Ke?=
 =?us-ascii?Q?EbMqGUuKhniapPmxB25jWKJE7/KPTfVF+2zr+NrPO4H34pUvfMsm3zjClowD?=
 =?us-ascii?Q?bsyUGXHVuNynhb5XZNHMCL9v4Q5x4oD0jINtQ9lDsFYWqPEgsnnyukEDFBoc?=
 =?us-ascii?Q?M+t4sVWlUa8rimLTL4Ck8tWJrju832KhvbGgJpvcBxNc8FqAWreY5Cl8TCcu?=
 =?us-ascii?Q?Gl0B4JzKT8EQUbVP+ttq5oLIpHhILOQnjZRCoWT8PHoUjtIVR/cdzvg2Y5sq?=
 =?us-ascii?Q?P4W6EBU3qmcBtg/QXtD5K50iT+HRdpIAHxcJunGto0/+oguUj4OnpDWwWRZw?=
 =?us-ascii?Q?mqRttRKU45eKmNSdi0rHved6N4yZ792Z1Xr1G986pDKvEW6H72T6bRJ+QiNV?=
 =?us-ascii?Q?yA=3D=3D?=
X-MS-Exchange-AntiSpam-ExternalHop-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-ExternalHop-MessageData-0: BXqogGFQIO3UbyPLgbjQfwyzUWmYk2XMtefLFbrh1RqUVFTeviJx4lp8287qiTeNZIBD+TjSaYAD6TPfyPasWNHanoqRrdxQ4B2qBdzomCLX5c3XY41sGVs7O8IUSidO8a/Wb0jW1hiWmc2OwuI7EZP70mH5JGEjJvlfBrT3u44zze2FThJqNCTw/3L4yiwk0np7QkUTHR+d99KkO/RiQ4uZ/eLllJRX4K4a2NhpMXgDV0OhM/q9i+OrFD0itbvlUThxyd9GPNUEY3whEw7WWoxZY/HSyDf/Y4C3dP/SG5cD5DSHnIrwvXLUJTwvRhdQpSZRD5+nqgwrlvaJBguJ0kiDjwA+O2g/Tw7lOMgZrGFChEgi3RwV1DuU8cXnanYjAJKv8/lSaUSVcGiQJNz/8XYLBv4RUEn/o4pUy75v31Y/3ruxJiAq63neTg5he88j9jG7bmi203wEh4kM+7JMFBMfocBWni0I0RWRk7RL0+sg9cNr2LtWKdMk5naSM1QsX8NgYCq8Jh1vZTb5FPUNZSHlz5ZfiHGOWRhgIIIKspM5MZbEnZp9IQHEdw7ekIn4fW1UgjhakSSewAMVl0x+c3KtXwkQKF6/J0TABPjS4fu4dsyCuSz+/wQRuCO3TQYRCzDT+8I1ZetslWHnB25uKCouFbzsBvybivl9e/w9lVuR1GOhdK7TdeV5gTpJDp0bUXSfHu3l5K0vUP3MkaRg2RlnpTfzvl5GnA7739KT7QX0ruZqKhwuWCGCEbyqR/LW4rt0KoqrbZekyyn3kDGzv5s/QeJ5f4PIdDD0sVQ4aaxuOz8k/qc/8ApGhBnffrWZKzifkUrW622rp3Hb9feNFzJB0c6ko+EeTqcdxsS1wQG983ELxRKMJ63FBH4fneiYwNM4QYm5EK1Tm6pnfvuSEA==
X-OriginatorOrg: oracle.com
X-MS-Exchange-CrossTenant-Network-Message-Id: b81ed707-260f-44b9-42f7-08db62463106
X-MS-Exchange-CrossTenant-AuthSource: SN6PR10MB3022.namprd10.prod.outlook.com
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 01 Jun 2023 02:16:21.4090
 (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: 7BFVPNrLG8CzLS9nul12DZJNoG2iYcCQ9SE7n86r2D2lCdT52GiMSUMq+0rzJnFgKIRcXnJhcejxshBaIilbaw==
X-MS-Exchange-Transport-CrossTenantHeadersStamped: SJ0PR10MB4687
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-05-31_18,2023-05-31_03,2023-05-22_02
X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 suspectscore=0 adultscore=0 spamscore=0
 phishscore=0 malwarescore=0 mlxlogscore=999 mlxscore=0 bulkscore=0
 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2304280000
 definitions=main-2306010016
X-Proofpoint-GUID: aDNZbnOv52S6_uTnPGkmds4wTCBOHyi9
X-Proofpoint-ORIG-GUID: aDNZbnOv52S6_uTnPGkmds4wTCBOHyi9
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