Received-SPF: pass (google.com: domain of linux-kernel+bounces-206617-linux.lists.archive=gmail.com@vger.kernel.org designates 2604:1380:40f1:3f00::1 as permitted sender) client-ip=2604:1380:40f1:3f00::1;
From: Sidhartha Kumar <sidhartha.kumar@oracle.com>
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, Sidhartha Kumar <sidhartha.kumar@oracle.com>
Subject: [PATCH v2 00/16] Introduce a store type enum for the Maple tree
Date: Fri,  7 Jun 2024 11:52:41 -0700
Message-ID: <20240607185257.963768-1-sidhartha.kumar@oracle.com>
Content-Transfer-Encoding: 8bit
Content-Type: text/plain
Precedence: bulk
MIME-Version: 1.0
X-MS-Exchange-AntiSpam-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-MessageData-0: 
	=?us-ascii?Q?ee5jLYKxSY/Ha3t6I2pu+cvwxAWmTZg19XkZIpI1/nsZsuI6gzA86+rbOerU?=
 =?us-ascii?Q?sdjzoUkNP+8e+Mf80ewSUDrz/c++NvvjJaZzbxLUtKIRGZm612TSXVLy5CFi?=
 =?us-ascii?Q?FdTUJ7CV8TqQFBug2h/CQyWKjCfIWBVSutC4vduSM6s0mVR4NgWhmjNUlfcU?=
 =?us-ascii?Q?Ak57AEEtw4oOxRGuE1mTSyk/ZFNEGKfXzovlDL/0OhMkmI4/Qmi6dU6bLzQJ?=
 =?us-ascii?Q?oBLhuMIxLHRZzOYPhvboTmDi7CfWt9yFkxNOGpRuKb2Woy7OyTsGbx8vpmeq?=
 =?us-ascii?Q?9XNO2+0Xaeu+aS//xmAfob/X/yiEsUxJ90zSuzP6HE984ufAmGfCHf22USOQ?=
 =?us-ascii?Q?o6U7ftyNizI9sltowNmgIgu+fFe8mNc2FCps+whEOxwn6vvHf4KjDZ8w/ICM?=
 =?us-ascii?Q?tHVjT9V0q9VfI9p7HmycejbEBVpNw6Wj5RTDSSATQ05rXMZKH5tmKv7jK3XQ?=
 =?us-ascii?Q?BuQ5aXb3nNAvE3yoraubbur4jfxI4mhahFpP/OxmHbIENmOF6Osr6bxcVCQa?=
 =?us-ascii?Q?rYgKAF4wEMWmKHtn4y8owvudLlrGpM7Tff6issDTH0HPqg05Y9Q3++zad/qy?=
 =?us-ascii?Q?EY0kJlQU1ZTrAxXUx0hkoEWhsWijDvXBOVvyuOUuvhHtdI/OWpb65HcDwCyh?=
 =?us-ascii?Q?RlqoD4nidBucECl2bxrQ2vump2E2fBhdpln5A78Li1dK9klz+8xNlTWTzauh?=
 =?us-ascii?Q?1hzZsCmaPGGj1/YLyr0wxr0J5v7REIFag6nKrbd2h/g6nE4hu3HG25qWr/nc?=
 =?us-ascii?Q?aIdVba2Ce8MWrtFLA5dWlvmFaGa8Ys93IE+kVVoTVNxn3EmUfVYZfopsbSJX?=
 =?us-ascii?Q?sfapbKuC4n/cF/YfYRpbu4W7qBMqEgAf0yK8HPYUDzLk47lZGta24u0NmCIn?=
 =?us-ascii?Q?vZ2iboXxlJk4HKn8jyUXsYydhF/nxJXtZZvAx2u55JhTCuBlIQCwTsoLRWkp?=
 =?us-ascii?Q?f1eyKlMjxC9G6aNniMTVz3P3bKPymJFBna5dCry9wNtg3aJXIb1jFpWsErjK?=
 =?us-ascii?Q?dn729Yq5PjeeBIKy3UvukKbgPa/1YOJzFQBFkEAvZYj7sy2xwrJB4FmTdE2X?=
 =?us-ascii?Q?4TW4Iw25fRyIFdP02z4hoi2VZeHp3oMqwC98RQMsHelXc3eYlcMbaAZrm4vL?=
 =?us-ascii?Q?yqd4ak005GFKEejnRyxsIeGQyH/M+icfvQ6b0/fXYwckZskjPPEuGhm23unk?=
 =?us-ascii?Q?MFa/FMbcd3rioHE05SjgQqg/y+QI1C4EiiIsnZRsJQhGkZF5QBauS58D5oVV?=
 =?us-ascii?Q?yB3ZyyKYL7/mTz13YChj9463ftqX3XY3+MBHAK+mTq99ef7AXEn2+9at0mtm?=
 =?us-ascii?Q?T7wuOkUdsy9G65swhPYs4NrCHh+Qjx/L+ejN2uOSd/HeWy65JGPqrUgbCGOU?=
 =?us-ascii?Q?+q1zfrRr5kZYgPPSISwirUzRcbEryLPrRS81MSUCMWfpabNfpWkTwP2DpEoL?=
 =?us-ascii?Q?qp/ke98HGc1OPr+CmIxAZ2Qar+0wwpk+aJA0BSpfJgLOr3MS2DghF62ByUgV?=
 =?us-ascii?Q?rgPPqJHH18L+oCfCbYOmrApYmgjlAZWL7YzaapdVDmV9p0MWSzLBYvh0EN0L?=
 =?us-ascii?Q?0tSJhjh5NB6CfNnFbN83qk3wLkvA2zfusntqkZR+IOVGoJdsoLuJud3VDcPY?=
 =?us-ascii?Q?NQPQfEWghuc/5cgj50gItDA=3D?=
X-MS-Exchange-AntiSpam-ExternalHop-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-ExternalHop-MessageData-0: 
	HOgCqxBFECKJgJXizh+obu6YlbRdvw32wpwJH/JdFIPFCNIOeGu769WFbOlUejwoOftHQ8+M1Kq9R/iUfrIPdYZfHFzwE0UZJBku39AMSs1UIEm7SVq2idhYVCh1EopTKfnvby6iCY29Ofr2A9Jhqd9RA0ksrV+su29qaQN2co4QJJe/8OKIfbl9nd6yCO2JQWXpqcrSH3hz81cXw35yh2mbtrInzrpkGDNT+h2xIqLgwNid8F7Nnj3hzpDK3Dg3R4HFdB+IQznas+TdMI9+ym4pDfsjgbl3fylxLurVWKXox24ZbjIgpezKD3rlX8ezatcE3VLRwqflL6z5eyqeKr+k9momNKG2BaCuCwj3qHXmMng9riPvch778zuTCFXOgTlYqpy4dQgjz4TE9Uf/IKXQOs2O21iNSIJMKxDBAn9lCglsa4XdH37aOt2hQlcMLl8iCGXooj9ocPakUiHgUw1bnx6JNOi7kR4dwU4yLwK/V6MEV2/HE6KbCsb1JXPZFdhR4v9wMoaUy5ddAnrQKUGR3JkThlXBjt5w02+EXh8Ow9uEJxNTTs28bW1V9V8qBrq/UKvP/Z+/hTnbReO9/8QL2ZRBnG7scyxZCGWSquc=
X-OriginatorOrg: oracle.com
X-MS-Exchange-CrossTenant-Network-Message-Id: 2b76629a-342b-4a33-73d5-08dc87230f52
X-MS-Exchange-CrossTenant-AuthSource: CH0PR10MB5113.namprd10.prod.outlook.com
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 07 Jun 2024 18:53:03.1927
 (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: bA93iCrnpHb72JWjwjT7wW6h06eu1Sa7FEsdor2eenBacB6UQMRQ1g7mmj6887Uhope64wQp5FRG5GQZ5EUddaPClhg1iL1nV5cpE54utbY=
X-MS-Exchange-Transport-CrossTenantHeadersStamped: SJ0PR10MB5629
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-06-07_11,2024-06-06_02,2024-05-17_01
X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 mlxscore=0 phishscore=0 bulkscore=1
 adultscore=0 spamscore=0 mlxlogscore=999 suspectscore=0 malwarescore=0
 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2405010000
 definitions=main-2406070137
X-Proofpoint-ORIG-GUID: iBY1OArsR8U9P5neFHn9gDL9TsIW8Iom
X-Proofpoint-GUID: iBY1OArsR8U9P5neFHn9gDL9TsIW8Iom

v1[1] -> v2:
  - previous results were noisy, replaced with stress-ng-mmap config of
    mmtests
  
  - document function parameter 'entry'in 'mas_prealloc_calc per Intel
    Test Robot
  
  - explain why mas_reset() was dropeed in patch 4

  - add locking and mas_destroy() to testcase in patch 4
  
  - squash "set write store type" vs "set store type" into the
    mas_wr_store_entry() modification

  - only set ret to xa_err() in the err case in mas_store_gfp()

  - move MT_BUG_ON() inside lock in patch 7

  - noinline mas_wr_spanning store to reduce stack usage in
    mas_wr_store_type() in patch 11 per Intel Test Robot

  - document function parameter gfp in mas_insert() per Intel
    test robot.

  - further simplify the local variables in patch 11


================================ OVERVIEW ================================

This series implements two work items[2]: "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,
	wr_bnode
};

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.

================================ RESULTS =================================

                  v6.10_mmap     v6.10_mmap_store_type
Duration User           9.80        8.69
Duration System      2295.94     2243.85
Duration Elapsed     1010.50     1009.44

================================ 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/20240604174145.563900-1-sidhartha.kumar@oracle.com/
[2]: https://lists.infradead.org/pipermail/maple-tree/2023-December/003098.html


Sidhartha Kumar (16):
  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: use mas_store_gfp() 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 mas_wr_append()
  maple_tree: remove unneeded mas_wr_walk() in mas_store_prealloc()

 include/linux/maple_tree.h       |  15 +
 lib/maple_tree.c                 | 579 ++++++++++++++++++-------------
 tools/testing/radix-tree/maple.c |  48 ++-
 3 files changed, 401 insertions(+), 241 deletions(-)

-- 
2.45.2