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,
        Suren Baghdasaryan <surenb@google.com>,
        "Liam R. Howlett" <Liam.Howlett@oracle.com>
Subject: [PATCH v3 13/15] maple_tree: Refine mas_preallocate() node calculations
Date:   Mon, 24 Jul 2023 14:31:55 -0400
Message-Id: <20230724183157.3939892-14-Liam.Howlett@oracle.com>
In-Reply-To: <20230724183157.3939892-1-Liam.Howlett@oracle.com>
References: <20230724183157.3939892-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?T90gBg4639CFy8dOg565EdLbt4QJdPYxDmJM6b14IpurJ2VHej9TE1qkgUk7?=
 =?us-ascii?Q?OrDQselZ5SjbTWKekLbU50zSL2qc8soZ3FTdTgGX1W0PxhZjxiFtfqljKC8n?=
 =?us-ascii?Q?gQqwgvbxuPPame3IRLdHRPG2ClWgU7negzSMys9kxZ+77KTFe2EX0Rpd6mNU?=
 =?us-ascii?Q?SGNka8fGEtSx+JZyFwBhqOZcI74SlwKebQoQghUxB7yRIziAPH2LtPBK3fKT?=
 =?us-ascii?Q?dyS6L2ca5Z2YRCcFX4JN+QQHiprOzSnQ2QQ4SpXMMVMtftEpUy8Qdg0BoFl7?=
 =?us-ascii?Q?ZJpLBd4ZKgnICEI2lKoe7thV8tUCB9LgI0J0fhCoHJ4U9/CLYs3ld5JhnKvz?=
 =?us-ascii?Q?clb0SF9Mlqbz5kTahz3diSw6uBAgGiaYITaTuUAEFFXhwujGMg488o4yhf15?=
 =?us-ascii?Q?R7oGe7IB8cTpNA2aYF6/+YJiR7dK2NOnTRmJvoX4VPMmRkiFjL/UwA+32MsX?=
 =?us-ascii?Q?d4XF5NI7XpR9hgmmfRLcRt3/DbRSzgv8M9CPbyg6rFRKsduNrfrClK/Ls6pp?=
 =?us-ascii?Q?SzMpxwsl+SPzu4zHS268EUtYGN4j9f/Gq/6Xtn8vTyLlHtSdw+vXd+ENfQDx?=
 =?us-ascii?Q?NN+U9XshGWaXkeVhYi7PE8DBN/chjogeE8Ke5hB6EhLcu0Ussua6qEWk71cO?=
 =?us-ascii?Q?zGDrNqDuXRet6HkFwfn1Br0OIYSnT9GKtHftWzIP7V57PFUGq0UCzD9mJ8D6?=
 =?us-ascii?Q?7zA756BmLytwb6R+APXrK4FC3BEytmOMkefqvOlijrQk42XJflan6Tu8blm9?=
 =?us-ascii?Q?+QPnAbB7CzVCGe4as8THOHENsn2VXIgmR0zDX9P0lpsyi9Dqs5UJ1RWyK7i7?=
 =?us-ascii?Q?Bi1u7U48doSY5Cfq2Apl3FNhLvnyYqdW/KurBGDIOJ90MJ0GL/g3GFFMSYx2?=
 =?us-ascii?Q?czWIhIvCh0LFVODyK/fMm3WMXNIu47EE8/yFWYKIee0yX5p5rIJwNpD44uPe?=
 =?us-ascii?Q?nHJ4+SPZ4Tkl4oPnt45yOLpldeIdG7XoXKGuqCXgAxzlAuUFHNP6d1YlawMz?=
 =?us-ascii?Q?4P7tFNWtpEKo4zQMVfuPI4Btpr2YqQ9g6ZlkTDKARSsfAT1fLa9d4MV92Jvm?=
 =?us-ascii?Q?ynJvI4GRSR2w15boqQ/0qViqq4lm4KA0a2pHGNDcEabexDFMwyU9S56Ec6Vg?=
 =?us-ascii?Q?HfjnL+ZQ0QwKCk+KMOrblMdoT6EFmKV45bWs0luo4E9+yFRjirZj50etCn/9?=
 =?us-ascii?Q?ST8RmaM1TyOqpd1FxP7hXX0lR0eb6DtzZP4Qkebeybqheqi8zOBddVNMp+Kl?=
 =?us-ascii?Q?8mF+4yZluXegiYSHfEvSsrT05YYM12eEGAGbKMDWjzG0sN3J0mdEYakx4YGw?=
 =?us-ascii?Q?dw9R9ZuSEqeSorOhMgaR+IqVKJQm2Z80VBdyCzCs6//2Vm8LkO2fxEJ/6iI/?=
 =?us-ascii?Q?kkVjUV1FtGzKuKmSUMvyEXTo5K4xmuYJigXuN2wbV2u2Cf6GALIDaDrIuXlj?=
 =?us-ascii?Q?4asXVsNXxS+sUzAcfHvSmzuH+l2GgJNOAHaBAl4tyPZ0yuRlk5dO+SqtDAOX?=
 =?us-ascii?Q?UaxB34II8TKBi4RWuzG/ukxBv3hLXEa6Hi5L1LZbXELoGDoEMZLJXwLtJX5L?=
 =?us-ascii?Q?mcvWgW+FetqpRFBVfnqmccwKwbFBuQCGp/mqc+cKQP887RwH5zuFSYTs+85Q?=
 =?us-ascii?Q?fQ=3D=3D?=
X-MS-Exchange-AntiSpam-ExternalHop-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-ExternalHop-MessageData-0: LBaiUyY7DyuI50smHmVmkd+1njtyvSdkvyU/rbqO0Yv0YYa4aavOboekteKXgRnb+cT7e1Da0v//5vSr+e7Tj2qEXMEWZJmO6BT5ye/DgR/ckD0wnpyWXja8z7uBfapTPLI3wEWOtS7En8Z4EoleUlfpgX7P30NXNXAK2rBvIR70XJmxpelvzmhfXJ/DxwIIJ0j3IPlpMZ2kXI+1WCKYrftDg0asAZW/mdNRm0dUiOTAPjMdjSo+PQ6nzB5+P4XyIkwI9m9LJ0NKvqEexhKYa5n8eSRhQEVsrXxBw/JJERD05ZjTv6MzN+b7es5cLaQqyy6KPPVyaZDqOjH4xROFaO+dOS5kFgsIeKIz4PuEl4idqYZt2KGFWnPP4H6tGhL+xc+yDoZnPfJPCIe5M3lbtVoQYd/P0BXp5PLVh8izJQBIXFMCc/cgU4BewtcpOGkXtfxrF9EwdHcDweY2KhE5U5Mex3CLVNK2lqcPwn7d4D78npK5VVRiRu7VhgxmF9+lNVf5hsipyxhN9elzTUs+D9pV2szkTur8+UgDgH0DF2FrXUyBkVs2Jj/BZxuQmWVYt4QyeZNYZp+tIvJARjNyoj4r1LWI7JveA5VX31zdTeSUey1kC/c3KCAlDcqfilLCHrHLuSOvnFh+2T+60QYJ/jKXxPn8GjwEUoxuA+9b93L/RDR7I3avWYfl7kQDYwR9SDVaEUeSM+vTORhiXpaMvSGZDexoIS7TskM0e36hXr0wNFwtKRKggopSvITNL5HZ5bQu4/Yg4AQBE4YjC/pHZUEdGudgZRgZRklza7KLc6SyFbXAxbLnFeLKISsOT01kRVg9FzIu1TynU0fOblb8k7NdQWzKaLzxtKnOS+Zmm4TlwN+8lyaF+dj26zqVfyUrtXeU5EDAJA+H162X2YSMxOmk0nnH+phJTi+sFVPGkUs=
X-OriginatorOrg: oracle.com
X-MS-Exchange-CrossTenant-Network-Message-Id: 83c48392-5c3f-4534-96ca-08db8c7461a5
X-MS-Exchange-CrossTenant-AuthSource: SN6PR10MB3022.namprd10.prod.outlook.com
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 24 Jul 2023 18:32:48.6321
 (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: Odkz+ZAw2fnZIWuEYO1U5ivq1xuW1tSx3oWCtE0pmaCx0V0Cg13H2kIP4ceP8kPKkbkcZ9cTm5lF3W9xB1DgXw==
X-MS-Exchange-Transport-CrossTenantHeadersStamped: CY8PR10MB6609
X-Proofpoint-Virus-Version: vendor=baseguard
 engine=ICAP:2.0.254,Aquarius:18.0.957,Hydra:6.0.591,FMLib:17.11.176.26
 definitions=2023-07-24_14,2023-07-24_01,2023-05-22_02
X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 bulkscore=0 spamscore=0 adultscore=0
 phishscore=0 mlxlogscore=999 malwarescore=0 mlxscore=0 suspectscore=0
 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2306200000
 definitions=main-2307240164
X-Proofpoint-ORIG-GUID: q5ki6t7Cy2K0A7iGgJZ1e6mhapWSMt34
X-Proofpoint-GUID: q5ki6t7Cy2K0A7iGgJZ1e6mhapWSMt34
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

Calculate the number of nodes based on the pending write action instead
of assuming the worst case.

This addresses a performance regression introduced in platforms that
have longer allocation timing.

Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>
---
 lib/maple_tree.c | 44 +++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 43 insertions(+), 1 deletion(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index db61cdd8a649..4a111785360f 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -5535,9 +5535,51 @@ EXPORT_SYMBOL_GPL(mas_store_prealloc);
  */
 int mas_preallocate(struct ma_state *mas, void *entry, gfp_t gfp)
 {
+	MA_WR_STATE(wr_mas, mas, entry);
+	unsigned char node_size;
+	int request = 1;
 	int ret;
 
-	mas_node_count_gfp(mas, 1 + mas_mt_height(mas) * 3, gfp);
+
+	if (unlikely(!mas->index && mas->last == ULONG_MAX))
+		goto ask_now;
+
+	mas_wr_store_setup(&wr_mas);
+	wr_mas.content = mas_start(mas);
+	/* Root expand */
+	if (unlikely(mas_is_none(mas) || mas_is_ptr(mas)))
+		goto ask_now;
+
+	if (unlikely(!mas_wr_walk(&wr_mas))) {
+		/* Spanning store, use worst case for now */
+		request = 1 + mas_mt_height(mas) * 3;
+		goto ask_now;
+	}
+
+	/* At this point, we are at the leaf node that needs to be altered. */
+	/* Exact fit, no nodes needed. */
+	if (wr_mas.r_min == mas->index && wr_mas.r_max == mas->last)
+		return 0;
+
+	mas_wr_end_piv(&wr_mas);
+	node_size = mas_wr_new_end(&wr_mas);
+	if (node_size >= mt_slots[wr_mas.type]) {
+		/* Split, worst case for now. */
+		request = 1 + mas_mt_height(mas) * 2;
+		goto ask_now;
+	}
+
+	/* New root needs a singe node */
+	if (unlikely(mte_is_root(mas->node)))
+		goto ask_now;
+
+	/* Potential spanning rebalance collapsing a node, use worst-case */
+	if (node_size  - 1 <= mt_min_slots[wr_mas.type])
+		request = mas_mt_height(mas) * 2 - 1;
+
+	/* node store, slot store needs one node */
+ask_now:
+	mas_node_count_gfp(mas, request, gfp);
 	mas->mas_flags |= MA_STATE_PREALLOC;
 	if (likely(!mas_is_err(mas)))
 		return 0;
-- 
2.39.2