Received-SPF: pass (google.com: domain of linux-kernel+bounces-206626-linux.lists.archive=gmail.com@vger.kernel.org designates 139.178.88.99 as permitted sender) client-ip=139.178.88.99;
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 09/16] maple_tree: use store type in mas_wr_store_entry()
Date: Fri,  7 Jun 2024 11:52:50 -0700
Message-ID: <20240607185257.963768-10-sidhartha.kumar@oracle.com>
In-Reply-To: <20240607185257.963768-1-sidhartha.kumar@oracle.com>
References: <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?RBH6gLPWmishdK9gBpk9s0jWJkpqwagLssRkdcKt/N5Ipin6B8NmWchAaDdX?=
 =?us-ascii?Q?H66nEnEUCYORdyvUXZqZTto44J6Lkxyx0cugUlk4AB3uOAYc874/Y5GuRIjJ?=
 =?us-ascii?Q?t3HxkmYU3AbkU3LumKIGV4+kgvIVRK6ircmJuXTah/cwwaacMkl1xsz3QKpv?=
 =?us-ascii?Q?x1wvf0uCuPwLrudl/cDRatxlxzRDO2qIGVRN1OAD7uT68zCBcCxzl14ARsxt?=
 =?us-ascii?Q?rjncORxTn3ZKyJEGPl3sdDzvS0Vr0mlT7oBnV26qpdKxumukbU4uYtoNg0I0?=
 =?us-ascii?Q?2nahCXY39sgGxLIFDws7aav5DWQou2j+4YjhsJJWyheHWLmTAKme4mVQatLJ?=
 =?us-ascii?Q?WfY3WjhtVCfORTN+W53Fe4VBLCtglch7xTBzbjQvZztP/EIAO2JKraR13qFX?=
 =?us-ascii?Q?OMs9IUFD+Zbo3A202Z9kH75CjAG+qxxkY31Lz2r7lIIS2XPzDOjHEY+Afjyn?=
 =?us-ascii?Q?ArmBBqgk5REyQEmr1bzQHCpPj+e8/JvnZgcilxo90tToLps7SfloYyEi6uyQ?=
 =?us-ascii?Q?lERFs9PWNSCqaWBOOvG7zQzf56IF2wTI4jNWHOfngXXGx6Seoe5h1KeERQt/?=
 =?us-ascii?Q?hXZDaQ69mBY4hYwvbHMNxcb8wPpGQCSzGzevTccF7LghZ+2Xl50dstHZKUlk?=
 =?us-ascii?Q?kmRbqzQBmhj3LuZfyB32jKGhjpXtJJeQyfhdnSpQgSmox+HFTTQEUBM3xFnk?=
 =?us-ascii?Q?yLyxElGAGYhE/vnCGdaniQtoaciPRTNmrl4JIhmz3nktiPNVTjKaA+MZ5uLF?=
 =?us-ascii?Q?Gy6W7iJRDwIeRzAmPX7GAKeZsLs2fOfUHof5p/NFmQqbqBGiXSV2CeZXezrV?=
 =?us-ascii?Q?RuJpCmxcEawBtb/XfUeQvPbqpBC0KjNW6IZEuvmiaLEr+gCHe1316YHA2Y/G?=
 =?us-ascii?Q?P36tkDO0/8KGHQQIqgdIySBjQCXydfKpcyELLKYnedjVF+ZmH+KjXOqqQVPK?=
 =?us-ascii?Q?t03WR+a4kyh3YpVbbD0nHvL7D29SK9EgxHuqB071gNHK5afA+hseNd2qKnXe?=
 =?us-ascii?Q?MC324/XojmzWog0+kiAjjHm5gp6pez6cm3EZFgwn4yfiXB3kawDfYEeySAvD?=
 =?us-ascii?Q?JAwIr1fiRq7+puJCHbNjLfsYTHX1UPuRHlUOqrjQPJUGie5PpLBoZ8u94WYv?=
 =?us-ascii?Q?7hrmLQNjT0qNAT0HdFYe02+KHikbd8TgquznUMH6z4aE2gld+LbLM9RbagVG?=
 =?us-ascii?Q?rSAT8gl3xNSf/PXm/JsPCrhaqAiZByf7EVdBn8OXCgSpcyTrg9xSlu5Yu4+Q?=
 =?us-ascii?Q?b1gr3pvcv/ncPYiBKxSHf+uvfQ9cNCLEFdNXIDYkO4NYPjK/P5c39+CQ/bRS?=
 =?us-ascii?Q?iEgMUym41E4WJcU6vBBAtN0yPkJjqVTO8zbO0YFyIPYmWoHNH5O8cDP+khzg?=
 =?us-ascii?Q?dxA4cRodPskBhSGtaf3ciR1X365y56TvQ+um6ZKYE45PyPqUH/Rv8S/xwIme?=
 =?us-ascii?Q?tVNDapEpqGua+TADxWN6oRBH/615ZxqvxO2VfdgaSHcxaBdFjxPi6wpL0BwZ?=
 =?us-ascii?Q?EryaoL6aAB8f5nI/pRq5+BKXpZPPslkTqcPzGByqVbPYS787kx1aQ5c6sAeq?=
 =?us-ascii?Q?pb2F+WOCVQgCIQEL6ciJwNpAuGlDM5qY72rGESbWtmFQKuW2Cht4h0ZpzZJe?=
 =?us-ascii?Q?S5CclhGpCG6XASawt9JcCgs=3D?=
X-MS-Exchange-AntiSpam-ExternalHop-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-ExternalHop-MessageData-0: 
	0ARf6/I/EUltTOs/J1BNkkDQJSfkHJcw3i8AC/ZpKcGK4Gtnn27RIOZE1HV7h5i9yU7PSZDOVYrRhv0eAH6zJ8oL6MBBqFwtZQAfsnP3GRmQQl+epiGrFR9uUKkgoPVD4psMxlpyAIfQwIBVnrZ7pHwSDRY1AJdinkLAMCLH+kd/7QDKLhdbng5MIpg8ngiAWpFk3Gff7QsyKWtSc2N8joNzB1bW/VdtQoDWJF9C8JO+IV7t4UDjEUKvZhoE/F+roGWn/WDgCQF0cgw6e4FRI0fa1qrAbt89Pg4Zk+ayeuCSAizbtIwfDE0IRTt/9czgREFaDpmYVt5oMJeCs/uOb/ZKCzz3nhY8vQwuC+rW25czSCgc03WK96aUus4joYtnwYpEburWcq/hM9law6/R1nT9nmD6H0T6w/GxOGnWReSBbYuQV1Cn/RTxnrKiEf80qoFoawdFRyYVsktNabzAtlpQVMiFRtp37uxEwzFUt1mZF6Awdm+yFh1dzAgupFtxILcziw/9+oqWXAeNcmCJL+mqCMnYfb06DO7jM+Od6U31bFrB6qdZ8ZXIoFLIan5IuWLe9Dt42xEVlMhj35U4pmcVowaHgg7cPbilRMeM/2Q=
X-OriginatorOrg: oracle.com
X-MS-Exchange-CrossTenant-Network-Message-Id: cfb1a767-1a42-49b5-b21f-08dc87231c75
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:25.1942
 (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: 51HFLJJBeNcuU66D0H5AVBF6mC0NA9xyhsw8lrlAV1otaidoPFCvNp5RZuNyl1Nskd88T/1DdLWZ9WG81Vj4ZD6Zv+kundTB/du+8cnells=
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 malwarescore=0 adultscore=0
 phishscore=0 suspectscore=0 bulkscore=0 spamscore=0 mlxlogscore=999
 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2405010000
 definitions=main-2406070138
X-Proofpoint-GUID: 8nkelKO-z_5mcRZ6sUp_6VQLTK08V6ol
X-Proofpoint-ORIG-GUID: 8nkelKO-z_5mcRZ6sUp_6VQLTK08V6ol

When storing an entry, we can read the store type that was set from a
previous partial walk of the tree. Now that the type of store is known,
select the correct write helper function to use to complete the store.

Also noinline mas_wr_spanning_store() to limit stack frame usage in
mas_wr_store_entry() as it allocates a maple_big_node on the stack.

Signed-off-by: Sidhartha Kumar <sidhartha.kumar@oracle.com>
---
 lib/maple_tree.c | 55 +++++++++++++++++++++++++++++++-----------------
 1 file changed, 36 insertions(+), 19 deletions(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 91b18eef81e1..2c42e99c400c 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -3780,7 +3780,7 @@ static inline int mas_new_root(struct ma_state *mas, void *entry)
  *
  * Return: 0 on error, positive on success.
  */
-static inline int mas_wr_spanning_store(struct ma_wr_state *wr_mas)
+static noinline int mas_wr_spanning_store(struct ma_wr_state *wr_mas)
 {
 	struct maple_subtree_state mast;
 	struct maple_big_node b_node;
@@ -4206,27 +4206,42 @@ static inline void mas_wr_modify(struct ma_wr_state *wr_mas)
 static inline void *mas_wr_store_entry(struct ma_wr_state *wr_mas)
 {
 	struct ma_state *mas = wr_mas->mas;
+	unsigned char new_end = mas_wr_new_end(wr_mas);
 
-	wr_mas->content = mas_start(mas);
-	if (mas_is_none(mas) || mas_is_ptr(mas)) {
+	switch (mas->store_type) {
+	case wr_invalid:
+		MT_BUG_ON(mas->tree, 1);
+		return NULL;
+	case wr_new_root:
+		mas_new_root(mas, wr_mas->entry);
+		break;
+	case wr_store_root:
 		mas_store_root(mas, wr_mas->entry);
-		return wr_mas->content;
-	}
-
-	if (unlikely(!mas_wr_walk(wr_mas))) {
+		break;
+	case wr_exact_fit:
+		rcu_assign_pointer(wr_mas->slots[mas->offset], wr_mas->entry);
+		if (!!wr_mas->entry ^ !!wr_mas->content)
+			mas_update_gap(mas);
+		break;
+	case wr_append:
+		mas_wr_append(wr_mas, new_end);
+		break;
+	case wr_slot_store:
+		mas_wr_slot_store(wr_mas);
+		break;
+	case wr_node_store:
+		mas_wr_node_store(wr_mas, new_end);
+		break;
+	case wr_spanning_store:
 		mas_wr_spanning_store(wr_mas);
-		return wr_mas->content;
-	}
-
-	/* At this point, we are at the leaf node that needs to be altered. */
-	mas_wr_end_piv(wr_mas);
-	/* New root for a single pointer */
-	if (unlikely(!mas->index && mas->last == ULONG_MAX)) {
-		mas_new_root(mas, wr_mas->entry);
-		return wr_mas->content;
+		break;
+	case wr_split_store:
+	case wr_rebalance:
+	case wr_bnode:
+		mas_wr_bnode(wr_mas);
+		break;
 	}
 
-	mas_wr_modify(wr_mas);
 	return wr_mas->content;
 }
 
@@ -5590,7 +5605,8 @@ void *mas_store(struct ma_state *mas, void *entry)
 	 * want to examine what happens if a single store operation was to
 	 * overwrite multiple entries within a self-balancing B-Tree.
 	 */
-	mas_wr_store_setup(&wr_mas);
+	mas_wr_prealloc_setup(&wr_mas);
+	mas_wr_store_type(&wr_mas);
 	mas_wr_store_entry(&wr_mas);
 	return wr_mas.content;
 }
@@ -5639,7 +5655,8 @@ void mas_store_prealloc(struct ma_state *mas, void *entry)
 {
 	MA_WR_STATE(wr_mas, mas, entry);
 
-	mas_wr_store_setup(&wr_mas);
+	mas_wr_prealloc_setup(&wr_mas);
+	mas_wr_store_type(&wr_mas);
 	trace_ma_write(__func__, mas, 0, entry);
 	mas_wr_store_entry(&wr_mas);
 	MAS_WR_BUG_ON(&wr_mas, mas_is_err(mas));
-- 
2.45.2