From patchwork Wed Aug 14 16:19:27 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Sidhartha Kumar X-Patchwork-Id: 13763701 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by smtp.lore.kernel.org (Postfix) with ESMTP id 0DB5FC3DA4A for ; Wed, 14 Aug 2024 16:20:23 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 1AEA66B009F; Wed, 14 Aug 2024 12:20:09 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 0E4966B009D; Wed, 14 Aug 2024 12:20:09 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id E52346B00A0; Wed, 14 Aug 2024 12:20:08 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0017.hostedemail.com [216.40.44.17]) by kanga.kvack.org (Postfix) with ESMTP id C12F16B009D for ; Wed, 14 Aug 2024 12:20:08 -0400 (EDT) Received: from smtpin27.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay01.hostedemail.com (Postfix) with ESMTP id A9F701C41DA for ; Wed, 14 Aug 2024 16:20:07 +0000 (UTC) X-FDA: 82451362854.27.A958103 Received: from mx0a-00069f02.pphosted.com (mx0a-00069f02.pphosted.com [205.220.165.32]) by imf14.hostedemail.com (Postfix) with ESMTP id 9B4EC100022 for ; Wed, 14 Aug 2024 16:20:05 +0000 (UTC) Authentication-Results: imf14.hostedemail.com; dkim=pass header.d=oracle.com header.s=corp-2023-11-20 header.b=XkjyJ1iV; spf=pass (imf14.hostedemail.com: domain of sidhartha.kumar@oracle.com designates 205.220.165.32 as permitted sender) smtp.mailfrom=sidhartha.kumar@oracle.com; dmarc=pass (policy=reject) header.from=oracle.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1723652370; h=from:from:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-transfer-encoding:content-transfer-encoding: in-reply-to:references:dkim-signature; bh=SK/Nu26uetx5TSG6GlCyrLf0Bo09xblzpAwAokPxC9A=; b=rV525lsZC8p5MWU4wrBmIEKnqKwkQydKfuP4xfaxLjthHzFTtfUjbrJ9f6tDkwKvZkqL2y 8OrMWcKmdYM5Mj5aVcq+7Mb/AY7dWrQ1+Ikf15/lo/dgNFYVxCJ8HsERllDSLu/lg4VgmO laZ4YNAC8Zl9l+Rr/TLh3XVT1TstTVk= ARC-Authentication-Results: i=1; imf14.hostedemail.com; dkim=pass header.d=oracle.com header.s=corp-2023-11-20 header.b=XkjyJ1iV; spf=pass (imf14.hostedemail.com: domain of sidhartha.kumar@oracle.com designates 205.220.165.32 as permitted sender) smtp.mailfrom=sidhartha.kumar@oracle.com; dmarc=pass (policy=reject) header.from=oracle.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1723652370; a=rsa-sha256; cv=none; b=EQloTZhjYvYVIsInBxMaGie2nC3aCdWrGKhYcZicKQd8tyFcfuSVSr/OiHlUE7pj4OVEcz Zah566M2qGQqpmodHgeJkvDd2nX23Mm6EiIF+yY4oQgpbuufv+51ypX94Pt2qUK6puKv8G mr8TA7IK7TphZiV8Nz4HbNk16xosXdM= Received: from pps.filterd (m0246627.ppops.net [127.0.0.1]) by mx0b-00069f02.pphosted.com (8.18.1.2/8.18.1.2) with ESMTP id 47EBtc3E028372; Wed, 14 Aug 2024 16:19:50 GMT DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=oracle.com; h= from:to:cc:subject:date:message-id:mime-version :content-transfer-encoding; s=corp-2023-11-20; bh=SK/Nu26uetx5TS G6GlCyrLf0Bo09xblzpAwAokPxC9A=; b=XkjyJ1iVoTYnhh5654FaMbuCSSsGNG 7EodH+8YMnAHT+3agpNxBUE2jv1pGq//CY7U3cmRpq3axkc1EBjAbKrj1ilwpL3p 85jsLQ1R46IwKdqYgrPonvVo6gqXmmJMBw+2ncFL6YuXsZieVXzE3vWHORcy8wpd /DHPMJZ/jVXmV+uvQLaAXEhobFS/vaosAcgVNGraQBA8O82hFJZWIMJNzJ1E4j4m fWPItB7EYHTr0pQjLIlyzmrvegjO9WXXf6nZYI5QMZf4wHx7bBSXNurZt4Wjhwks ytZ51vhdSFj8hcQ3GnH3jbaAFrerZOawaDRSip0Xj9NxoABAF9uw8EEw== Received: from iadpaimrmta02.imrmtpd1.prodappiadaev1.oraclevcn.com (iadpaimrmta02.appoci.oracle.com [147.154.18.20]) by mx0b-00069f02.pphosted.com (PPS) with ESMTPS id 40wxt10sht-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Wed, 14 Aug 2024 16:19:49 +0000 (GMT) Received: from pps.filterd (iadpaimrmta02.imrmtpd1.prodappiadaev1.oraclevcn.com [127.0.0.1]) by iadpaimrmta02.imrmtpd1.prodappiadaev1.oraclevcn.com (8.17.1.19/8.17.1.19) with ESMTP id 47EEuMDk021125; Wed, 14 Aug 2024 16:19:48 GMT Received: from pps.reinject (localhost [127.0.0.1]) by iadpaimrmta02.imrmtpd1.prodappiadaev1.oraclevcn.com (PPS) with ESMTPS id 40wxngn7hm-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Wed, 14 Aug 2024 16:19:48 +0000 Received: from iadpaimrmta02.imrmtpd1.prodappiadaev1.oraclevcn.com (iadpaimrmta02.imrmtpd1.prodappiadaev1.oraclevcn.com [127.0.0.1]) by pps.reinject (8.17.1.5/8.17.1.5) with ESMTP id 47EGIvBu035951; Wed, 14 Aug 2024 16:19:48 GMT Received: from sidkumar-mac.us.oracle.com (dhcp-10-65-174-212.vpn.oracle.com [10.65.174.212]) by iadpaimrmta02.imrmtpd1.prodappiadaev1.oraclevcn.com (PPS) with ESMTP id 40wxngn7gt-1; Wed, 14 Aug 2024 16:19:47 +0000 From: Sidhartha Kumar To: linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org Cc: linux-mm@kvack.org, akpm@linux-foundation.org, liam.howlett@oracle.com, willy@infradead.org, surenb@google.com, Sidhartha Kumar Subject: [PATCH v4 00/17] Introduce a store type enum for the Maple tree Date: Wed, 14 Aug 2024 12:19:27 -0400 Message-ID: <20240814161944.55347-1-sidhartha.kumar@oracle.com> X-Mailer: git-send-email 2.46.0 MIME-Version: 1.0 X-Proofpoint-Virus-Version: vendor=baseguard engine=ICAP:2.0.293,Aquarius:18.0.1039,Hydra:6.0.680,FMLib:17.12.28.16 definitions=2024-08-14_12,2024-08-13_02,2024-05-17_01 X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 adultscore=0 mlxscore=0 bulkscore=1 phishscore=0 malwarescore=0 suspectscore=0 spamscore=0 mlxlogscore=999 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2407110000 definitions=main-2408140111 X-Proofpoint-GUID: 24WpDigPHcUZeefFkLGA3z4tHfQ12KSL X-Proofpoint-ORIG-GUID: 24WpDigPHcUZeefFkLGA3z4tHfQ12KSL X-Rspamd-Server: rspam03 X-Rspam-User: X-Rspamd-Queue-Id: 9B4EC100022 X-Stat-Signature: x68h3uzxfam8j5wdnzjnix11rmbrinhf X-HE-Tag: 1723652405-775947 X-HE-Meta: U2FsdGVkX19jBMt52ra4Y9/NhJBveu8HzZ6Rka0adq/xbOL2WuWce6i0ntDogFYrG7yx/NSgVY76LH4ovhPSzfIUH+Xp2YiTx/wQBzUL7gXjUFJ2AtM7Cgy07QPv71pL/y8ToZAMqQXR/eGABdVi9j6cDoOYlWgI2uD0Iy8XHiKm1+LPNfU2IeGUwhUImHZYKkhYPDWRTAxyIaryZ3aFSaG6Yu+YZCiVVYNKDJtHEL+iUxXvQzcmPMt15Fhh9+2ZODlHK37xAoNp6OYxEHZorP0x8AzhiszeYaRcSIku9Q3q84fO++cBkDZ+I9Dq4p9cvAJj6uFRdn/vksrlT7KN2tstl3hNk6MCHRA8wbCgF8xlIEevtGdGlYKaU5MjRFhc9IoGjZSUluTE/EtNEXLaDi13szlogWT69nmtIzEaNVTJlu3vgWZK91ikUTecG7rGO+s6946HrvBZULlhk5IjmjGEEj8ezdMhQBJYl6SdAVy8C0TMDli1mCCKNs58VUinTM8NWESjdbiMxH5DFYzseOCv1rYgKO2uBsQUoxZGdaU+bvXguoj28swly3aTIHU8Uv7Gc+mVGqeqsBsDExjbTU0zx84ZakKiSxBHZQufb1ktKNlpf4VQNp/WDbZ0xuXIr5ZVvi0uAGdWAs/QovYM2vW4rQkhsFaYD0TZ7uf9irPlWnVqkBQBl6xp37VV7rCPZ6cBtrpE7J4rrj4zfjZHZL/dKEKIFAYw8S31oVBdlWH8oYEN8cXtLx05V15M7kUsQ1xH1ddNAzzqIKpsslF9skcvzrlvBaVFSN5uEE3xhtvO2PSBtyIcKEgEMzI2ILiNecLLn478L12c3GkUI8VU+wH59G+bGwbeFQq+yUdMcPdWqI8zhTwjSnHsW/fkdEjS7NSaz+0pVU/A1DyTpogY+vekLO9nbgUbC8sf68eVrqYclE0xlEmicCHfA+gni9+2ReizGlRdttgh3rIO9T3 DUCPDybe s8akpMK/88/jmfPFSel30KqSpddb8WCAs7Ao25isOW1ArcC+W67u0nPoUCcFxswKHV4PgL8HCkDxsMf/7BFnsEvIrfke5kylZ/YwuXyvWCJGbhaFNop3lnXjWUzyX+x5HAm2Ok9bfYoDc5ngHK27pbHXo2h2O/RUWxodfhGs7x+2Pk/QG05kXqf2K7FkgC3z2+HMuibuK+f3HU156sPPf9dO7xOt7pfX8OpeuMvwi62u4DIncuQ7H0b/tha9peCbcbCwQLLjQ92F2Co0bNYd0vfXHqLtqqurben9a6Uy5MJUymXQSGRxQ31HJR4CXKWyaIwKRRp9Z8XpC+gjFBKh0DY0KmznD+zUpQJtz X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: List-Subscribe: List-Unsubscribe: v3[1] -> v4: - move up mas->node = null in mas_start() so mas->node is cleared in all cases. - don't pass gfp into mas_wr_preallocate().This fixes the libfs error reported in v3[2]. - change condition of node store so more writes can be eligible node stores. - more cleanup of mas_commit_b_node() as most of the function becomes dead code. - remove wr_bnode as a store type as it is no longer needed. - add a patch to change many write helper functions to be void. ================================ OVERVIEW ================================ This series implements two work items[3]: "aligning mas_store_gfp() with mas_preallocate()" and "enum for store type". mas_store_gfp() is modified to preallocate nodes. This simplies many of the write helper functions by allowing them to use mas_store_gfp() rather than open coding node allocation and error handling. The enum defines the following store types: enum store_type { wr_invalid, wr_new_root, wr_store_root, wr_exact_fit, wr_spanning_store, wr_split_store, wr_rebalance, wr_append, wr_node_store, wr_slot_store, }; In the current maple tree code, a walk down the tree is done in mas_preallocate() to determine the number of nodes needed for this write. After node allocation, mas_wr_store_entry() will perform another walk to determine which write helper function to use to complete the write. Rather than performing the second walk, we can store the type of write in the maple write state during node allocation and read this field to complete the write. Patches 1-16 implement this store type feature. Patch 17 is a cleanup patch to change functions that have unused return types to be void. ================================ RESULTS ================================= Phoronix t-test-1 (Seconds < Lower Is Better) v6.10-rc6 Threads: 1 33.15 Threads: 2 10.81 v6.10-rc6 + this series Threads: 1 32.69 Threads: 2 10.45 Stress-ng mmap 6.10_base store_type_v4 Duration User 2744.65 2769.40 Duration System 10862.69 10817.59 Duration Elapsed 1477.58 1478.35 ================================ TESTING ================================= Testing was done with the maple tree test suite. A new test case is also added to validate the order in which we test for and assign the store type. [1]: https://lore.kernel.org/linux-mm/80926b22-a8d2-9992-eb5e-27e2c99cf460@google.com/T/#m81044feb66765265f8ca7f21e4b4b3725b18780a [2]: https://lore.kernel.org/linux-mm/80926b22-a8d2-9992-eb5e-27e2c99cf460@google.com/T/#mb36c6526486638e82518c0f37a428fb279c84d8a [3]: https://lists.infradead.org/pipermail/maple-tree/2023-December/003098.html Sidhartha Kumar (17): maple_tree: introduce store_type enum maple_tree: introduce mas_wr_prealloc_setup() maple_tree: move up mas_wr_store_setup() and mas_wr_prealloc_setup() maple_tree: introduce mas_wr_store_type() maple_tree: remove mas_destroy() from mas_nomem() maple_tree: preallocate nodes in mas_erase() maple_tree: use mas_store_gfp() in mtree_store_range() maple_tree: print store type in mas_dump() maple_tree: use store type in mas_wr_store_entry() maple_tree: convert mas_insert() to preallocate nodes maple_tree: simplify mas_commit_b_node() maple_tree: remove mas_wr_modify() maple_tree: have mas_store() allocate nodes if needed maple_tree: remove node allocations from various write helper functions maple_tree: remove repeated sanity checks from write helper functions maple_tree: remove unneeded mas_wr_walk() in mas_store_prealloc() maple_tree: make write helper functions void include/linux/maple_tree.h | 14 + lib/maple_tree.c | 653 ++++++++++++++++--------------- tools/testing/radix-tree/maple.c | 46 ++- 3 files changed, 400 insertions(+), 313 deletions(-)