Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::3:4 as permitted sender) client-ip=2620:137:e000::3:4;
From:   Sidhartha Kumar <sidhartha.kumar@oracle.com>
To:     linux-kernel@vger.kernel.org, linux-mm@kvack.org,
        maple-tree@lists.infradead.org
Cc:     akpm@linux-foundation.org, willy@infradead.org,
        liam.howlett@oracle.com, zhangpeng.00@bytedance.com,
        Sidhartha Kumar <sidhartha.kumar@oracle.com>
Subject: [PATCH] maple_tree: do not preallocate nodes for slot stores
Date:   Tue, 12 Dec 2023 11:46:40 -0800
Message-ID: <20231212194640.217966-1-sidhartha.kumar@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?ESkBIl8cLygxlCLquC3SzKqc2FRvQXu0wN4l4v2gZc72byYgeapKvQXBHnfg?=
 =?us-ascii?Q?U1Ve0W6HJZAEOHDj1xww6cVfvTlTPQzDyrwwGRalN7WG4C9o0/6gu0B3nh9o?=
 =?us-ascii?Q?w8wXkJmnOPUFa6DB5UtMNc2e7pS1iz7EQi5FpBIDkTAPvrofx4QYOBUuvD5s?=
 =?us-ascii?Q?EMZjzNu6tDhsPeJLJNKsqEDbW09QFz+679TtlxSemXrylhw+WxZl2Notv0fR?=
 =?us-ascii?Q?h21mFixIMkgGOdh7IU5AOjxDPiMLM6NwEN/mWCw0eR4ujxn/I6m3dcIP2AbF?=
 =?us-ascii?Q?CldE16925gPzzuoZIAOOgpS2CtYePdKspyAFGzX9zzMHH3cyNe33iR2jDQxX?=
 =?us-ascii?Q?f5ai/2HfDgLS27pPcENasfUq++dv+w6XD4Zp/Gek+Scf2SmvSWhY6dfBlbYn?=
 =?us-ascii?Q?9RQK2JiNnys2HjuO+cLYqqhLKkTf2NeCUYUbAFOGB2h8qVNnZpRz3kfhymVf?=
 =?us-ascii?Q?iRraW3gN76gKN8DJ1FJ1Rz2ntOaVdeReDe2OkRQkQzrEq54UTVbDlPF3hF4z?=
 =?us-ascii?Q?ewcBaw08YTnlze7tYzjNB8NOndxCAZjdhB0Mz5ibrpBE9tzLOvcpU5TAg8XY?=
 =?us-ascii?Q?Xtq2VKi6SX2HeNMmdQpKR03d4LWq+qrDTs+OFCTQ7mQC9fG6lcU2EqqSbD99?=
 =?us-ascii?Q?DSkGQrqSjjaFd/2k4QBJ0izFKOtmEZILwL7HxsPNkyDd3nEdtOjphSbiXKVd?=
 =?us-ascii?Q?svAA+Xbx1T9JaWknbL0NFolBsZgFJr2FT9ZWMRvOch7gE1gqRG/6MDqpEtJu?=
 =?us-ascii?Q?MmIFj55daCQHw2DwfK3s2KYmBAfl0JCt4gjxRh0vtGp5K1NpEnBp2sdWhE/O?=
 =?us-ascii?Q?zZc+d17l7pnAvw6iIQgQ34EhgGZ7DH6Xh6uE6cvaRSuBcLltn9P6X9AaM6Qb?=
 =?us-ascii?Q?2zB3NSAup4JAepHLOmbk7pG4BauqXef6eQ0rq9LG5yRP6uv36sgEKTl2tvQv?=
 =?us-ascii?Q?YnVved7BIVrc3+9mjHjC1+FQ1MsK57yHadWwB5s32BnpcpJOGkOuiNaGyUf/?=
 =?us-ascii?Q?E1rFCslRKXkFTLDpiIq+94V3bWvLEKTlPbH+29lWFqg3ADF8XZFv88bEHALk?=
 =?us-ascii?Q?kqnbKalauT6K1NGPKcnlFCabCKFuFOIsVb3Di4S4nH1jBuT9nxLOtFOQPQvo?=
 =?us-ascii?Q?h50f/IaH7Yu5QOpVm4qaPOukR7Vv7nYOgIRgkjygFZgKPmnwrh2apojmEqBd?=
 =?us-ascii?Q?ivf/Pff+E6QzCWRRMEOSaLFsR2GW+p94ob8+HkEyr4+wnaMqozh/F5ua3xq4?=
 =?us-ascii?Q?g4ewABobJWsEiI37XFnHyKMVHjyc485eeIotaf3v+sjbE5YfMOTTkgBgd2Z/?=
 =?us-ascii?Q?YXNiJyLZTfkaeVTleUi67FEL003HQojrwIny2OHG3+VAOZjrxKG3mbInXdoL?=
 =?us-ascii?Q?3ptPYriznA+Ln7NJSLaLBdJA5VBfKBtu3xrwPtm78RhAw+Kkb8P3Es3yj2Xd?=
 =?us-ascii?Q?x2Zy3cVjh2X3xPfSZ6Hjay3HSr7AU7qDKz1jYnL/p7JfzyEfKnOaAtYj0jrD?=
 =?us-ascii?Q?UgGvtHqL9kJhkT9z4B0C9XOmk9U2bOmwivNgHICvn5eEpq40PliE5nWjJzNH?=
 =?us-ascii?Q?fydm6zzWeOb46FT4dCvEu4Yp7aIjLQXOHGE+WrKPngTLHQPWAB/5i11VriHk?=
 =?us-ascii?Q?P9N4UuxNAb2QVeo3Yr2x/c4=3D?=
X-MS-Exchange-AntiSpam-ExternalHop-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-ExternalHop-MessageData-0: =?us-ascii?Q?5rJcYFIa+4WB1FTSkL2lzb07pJJlx6gdnhxNMneehU9nCNIaeoxrzWr3KJL5?=
 =?us-ascii?Q?E1aMyjIauC+0jYwTivHio4h7MjGKVcPLHdFAyMv05NY9KTQi7oWQcDmuW4wt?=
 =?us-ascii?Q?+MSVn1vnncHNiApkDaQKCtK6OIdf4XenMwXYQHxWfwJimAI+Bj08WsXQC5Zt?=
 =?us-ascii?Q?2Qo8ivSJ57xceTJdX2efEYsyOqemT1JboLy5fNlMZOCP+xL9RUg3dviNDtw/?=
 =?us-ascii?Q?4gQRRCSLhsOEjNZVX8yIruAvyYvJ7QwglAUi6mgbxgIenWRnxCcf5dGXYu9l?=
 =?us-ascii?Q?z3278kEfXffNtAjiUuzwkHCdVQVAAcojmU8HyX9GN+uYoPiZcxgcVdwin6y7?=
 =?us-ascii?Q?I9/XtQdOwE16RbbJtRPOpxzoPatY67xag7OsOw2aASR7qkGCKFd2e6iD1V+U?=
 =?us-ascii?Q?3Nhg9yQZM+ZXumTy964UiKIZJ+ZlZ0x4lQSyglUu0gtQt4ZTx0rd7WjyUbOW?=
 =?us-ascii?Q?Ww0XtH9UQ0kgKYb24P3WAXpvUtzbxx8q3sqDkvDC1RtkHfkcxak4g/cgLiiv?=
 =?us-ascii?Q?9c5Knjeh+CiYOexzX6ian7e1oGSHRG3yqGHeI57AU53Qqe4ihvNlmUq6fHQ5?=
 =?us-ascii?Q?IVos4czponF9E7gH0MQRLgWO1MjTE7wVBHWN2q1eqt3aNVIlCBLQ3aqno1M7?=
 =?us-ascii?Q?ba0OfiafIc7Kx9pKs0zO9dYzImPqSBuuNDgzOhO7xyrB83i/Velq4npYwcEG?=
 =?us-ascii?Q?gGooHGb7hCdy7b/5AqxeAVUtf9Gl8YOujWVm6l99T14EDsJGbGtRhMAtKOSO?=
 =?us-ascii?Q?XpacJNBLwEvibeLR2UgZXXwpXdsT9hAKAuOW757C+mp4TNqWn4keKL8S9yuH?=
 =?us-ascii?Q?4B7P4RYVH9MP+oQ37bb7r+NIeKswXWR1snWRsJ4SmTgpQwbtn4ab1M5zer4C?=
 =?us-ascii?Q?h4p+2S8pJYZL6+pNt7QCSqL5RmMtY+wQDT9OO/Hsf5pZmDOIBha3iuAD9Cqt?=
 =?us-ascii?Q?5c5mfJ6XtgiQsOD0eH8CGGgIhE19CEuhnTw3PsbzZGg=3D?=
X-OriginatorOrg: oracle.com
X-MS-Exchange-CrossTenant-Network-Message-Id: 8772db88-e214-4dc9-1260-08dbfb4b1275
X-MS-Exchange-CrossTenant-AuthSource: CH0PR10MB5113.namprd10.prod.outlook.com
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 12 Dec 2023 19:46:45.5313
 (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: MhorIutPTZxous8q/jxxKrVAvLx2mq44fnA8OrFwj2WbanrvXkROkpoSt9eu+IGG3OKoJzEXkWHQtlWfKc9rAcnM+4kuSOys/y2Exz+byXY=
X-MS-Exchange-Transport-CrossTenantHeadersStamped: DS7PR10MB5309
X-Proofpoint-Virus-Version: vendor=baseguard
 engine=ICAP:2.0.272,Aquarius:18.0.997,Hydra:6.0.619,FMLib:17.11.176.26
 definitions=2023-12-12_12,2023-12-12_01,2023-05-22_02
X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 bulkscore=0 malwarescore=0
 mlxlogscore=999 adultscore=0 phishscore=0 suspectscore=0 mlxscore=0
 spamscore=0 classifier=spam adjust=0 reason=mlx scancount=1
 engine=8.12.0-2311290000 definitions=main-2312120151
X-Proofpoint-ORIG-GUID: B8C3UP6f2e5iCrE8-g9P5UWkhwi00Z7q
X-Proofpoint-GUID: B8C3UP6f2e5iCrE8-g9P5UWkhwi00Z7q
X-Spam-Status: No, score=-0.9 required=5.0 tests=DKIM_SIGNED,DKIM_VALID,
	DKIM_VALID_AU,HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI,
	SPF_HELO_NONE,SPF_PASS,T_SCC_BODY_TEXT_LINE autolearn=unavailable
	autolearn_force=no version=3.4.6
X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on howler.vger.email
Precedence: bulk
List-ID: <linux-kernel.vger.kernel.org>
X-Mailing-List: linux-kernel@vger.kernel.org
X-Greylist: Sender passed SPF test, not delayed by milter-greylist-4.6.4 (howler.vger.email [0.0.0.0]); Tue, 12 Dec 2023 11:47:27 -0800 (PST)

mas_preallocate() defaults to requesting 1 node for preallocation and then
,depending on the type of store, will update the request variable. There
isn't a check for a slot store type, so slot stores are preallocating the
default 1 node. Slot stores do not require any additional nodes, so add a
check for the slot store case that will bypass node_count_gfp(). Update
the tests to reflect that slot stores do not require allocations.

User visible effects of this bug include increased memory usage from the
unneeded node that was allocated.

Fixes: 0b8bb544b1a7 ("maple_tree: update mas_preallocate() testing")
Signed-off-by: Sidhartha Kumar <sidhartha.kumar@oracle.com>
---
This patch passes the maple tree test suite. A seperate patch will be sent
for a 6.6 stable backport as the node_end field was moved from the
ma_wr_state to the ma_state in a recent patch which is not in 6.6.


 lib/maple_tree.c                 | 6 ++++++
 tools/testing/radix-tree/maple.c | 2 +-
 2 files changed, 7 insertions(+), 1 deletion(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index e6954fa75eb5..e4a39beb1018 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -5475,6 +5475,12 @@ int mas_preallocate(struct ma_state *mas, void *entry, gfp_t gfp)
 
 	mas_wr_end_piv(&wr_mas);
 	node_size = mas_wr_new_end(&wr_mas);
+
+	/* Slot store, does not require additional nodes */
+	if ((node_size == mas->end) && ((!mt_in_rcu(mas->tree))
+		|| (wr_mas.offset_end - mas->offset == 1)))
+		return 0;
+
 	if (node_size >= mt_slots[wr_mas.type]) {
 		/* Split, worst case for now. */
 		request = 1 + mas_mt_height(mas) * 2;
diff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/maple.c
index 687886cebd9d..f1caf4bcf937 100644
--- a/tools/testing/radix-tree/maple.c
+++ b/tools/testing/radix-tree/maple.c
@@ -35545,7 +35545,7 @@ static noinline void __init check_prealloc(struct maple_tree *mt)
 	MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0);
 	allocated = mas_allocated(&mas);
 	height = mas_mt_height(&mas);
-	MT_BUG_ON(mt, allocated != 1);
+	MT_BUG_ON(mt, allocated != 0);
 	mas_store_prealloc(&mas, ptr);
 	MT_BUG_ON(mt, mas_allocated(&mas) != 0);
 
-- 
2.42.0