From mboxrd@z Thu Jan 1 00:00:00 1970 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 vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 80F83EB64DA for ; Sun, 2 Jul 2023 22:33:45 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S229954AbjGBWdo (ORCPT ); Sun, 2 Jul 2023 18:33:44 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:55540 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S229791AbjGBWdo (ORCPT ); Sun, 2 Jul 2023 18:33:44 -0400 Received: from dfw.source.kernel.org (dfw.source.kernel.org [139.178.84.217]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 9798AE50 for ; Sun, 2 Jul 2023 15:33:36 -0700 (PDT) Received: from smtp.kernel.org (relay.kernel.org [52.25.139.140]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits)) (No client certificate requested) by dfw.source.kernel.org (Postfix) with ESMTPS id 36C7160CF7 for ; Sun, 2 Jul 2023 22:33:36 +0000 (UTC) Received: by smtp.kernel.org (Postfix) with ESMTPSA id 8D149C433C7; Sun, 2 Jul 2023 22:33:35 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=linux-foundation.org; s=korg; t=1688337215; bh=nIGchBGUKCeFokE0jEkJ8bA1b3BfgvYTgYtfaWJGMFs=; h=Date:To:From:Subject:From; b=UNT0zclbGO/sLAO0nQQ+sKMdUuKIUGY5vGDTKoWFKCsIuYw5aykhYGw118TSI6K1v HU/GmtyNEEtA//LROa6dIPFuuamZPzSe3WiLiCvpEnaknQEz9qgGacFdweJxJM1hGe y6Ek3N80jRZK5ydwm1ZfEub8BX2o2UogkJDdqsD4= Date: Sun, 02 Jul 2023 15:33:35 -0700 To: mm-commits@vger.kernel.org, Liam.Howlett@oracle.com, zhangpeng.00@bytedance.com, akpm@linux-foundation.org From: Andrew Morton Subject: + maple_tree-optimize-mas_wr_append-also-improve-duplicating-vmas.patch added to mm-unstable branch Message-Id: <20230702223335.8D149C433C7@smtp.kernel.org> Precedence: bulk Reply-To: linux-kernel@vger.kernel.org List-ID: X-Mailing-List: mm-commits@vger.kernel.org The patch titled Subject: maple_tree: optimize mas_wr_append(), also improve duplicating VMAs has been added to the -mm mm-unstable branch. Its filename is maple_tree-optimize-mas_wr_append-also-improve-duplicating-vmas.patch This patch will shortly appear at https://git.kernel.org/pub/scm/linux/kernel/git/akpm/25-new.git/tree/patches/maple_tree-optimize-mas_wr_append-also-improve-duplicating-vmas.patch This patch will later appear in the mm-unstable branch at git://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm Before you just go and hit "reply", please: a) Consider who else should be cc'ed b) Prefer to cc a suitable mailing list as well c) Ideally: find the original patch on the mailing list and do a reply-to-all to that, adding suitable additional cc's *** Remember to use Documentation/process/submit-checklist.rst when testing your code *** The -mm tree is included into linux-next via the mm-everything branch at git://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm and is updated there every 2-3 working days ------------------------------------------------------ From: Peng Zhang Subject: maple_tree: optimize mas_wr_append(), also improve duplicating VMAs Date: Wed, 28 Jun 2023 15:36:56 +0800 When the new range can be completely covered by the original last range without touching the boundaries on both sides, two new entries can be appended to the end as a fast path. We update the original last pivot at the end, and the newly appended two entries will not be accessed before this, so it is also safe in RCU mode. This is useful for sequential insertion, which is what we do in dup_mmap(). Enabling BENCH_FORK in test_maple_tree and just running bench_forking() gives the following time-consuming numbers: before: after: 17,874.83 msec 15,738.38 msec It shows about a 12% performance improvement for duplicating VMAs. Link: https://lkml.kernel.org/r/20230628073657.75314-4-zhangpeng.00@bytedance.com Signed-off-by: Peng Zhang Reviewed-by: Liam R. Howlett Signed-off-by: Andrew Morton --- lib/maple_tree.c | 33 ++++++++++++++++++++++----------- 1 file changed, 22 insertions(+), 11 deletions(-) --- a/lib/maple_tree.c~maple_tree-optimize-mas_wr_append-also-improve-duplicating-vmas +++ a/lib/maple_tree.c @@ -4266,10 +4266,10 @@ static inline unsigned char mas_wr_new_e * * Return: True if appended, false otherwise */ -static inline bool mas_wr_append(struct ma_wr_state *wr_mas) +static inline bool mas_wr_append(struct ma_wr_state *wr_mas, + unsigned char new_end) { unsigned char end = wr_mas->node_end; - unsigned char new_end = end + 1; struct ma_state *mas = wr_mas->mas; unsigned char node_pivots = mt_pivots[wr_mas->type]; @@ -4281,16 +4281,27 @@ static inline bool mas_wr_append(struct ma_set_meta(wr_mas->node, maple_leaf_64, 0, new_end); } - if (mas->last == wr_mas->r_max) { - /* Append to end of range */ - rcu_assign_pointer(wr_mas->slots[new_end], wr_mas->entry); - wr_mas->pivots[end] = mas->index - 1; - mas->offset = new_end; + if (new_end == wr_mas->node_end + 1) { + if (mas->last == wr_mas->r_max) { + /* Append to end of range */ + rcu_assign_pointer(wr_mas->slots[new_end], + wr_mas->entry); + wr_mas->pivots[end] = mas->index - 1; + mas->offset = new_end; + } else { + /* Append to start of range */ + rcu_assign_pointer(wr_mas->slots[new_end], + wr_mas->content); + wr_mas->pivots[end] = mas->last; + rcu_assign_pointer(wr_mas->slots[end], wr_mas->entry); + } } else { - /* Append to start of range */ + /* Append to the range without touching any boundaries. */ rcu_assign_pointer(wr_mas->slots[new_end], wr_mas->content); - wr_mas->pivots[end] = mas->last; - rcu_assign_pointer(wr_mas->slots[end], wr_mas->entry); + wr_mas->pivots[end + 1] = mas->last; + rcu_assign_pointer(wr_mas->slots[end + 1], wr_mas->entry); + wr_mas->pivots[end] = mas->index - 1; + mas->offset = end + 1; } if (!wr_mas->content || !wr_mas->entry) @@ -4337,7 +4348,7 @@ static inline void mas_wr_modify(struct goto slow_path; /* Attempt to append */ - if (new_end == wr_mas->node_end + 1 && mas_wr_append(wr_mas)) + if (mas_wr_append(wr_mas, new_end)) return; if (new_end == wr_mas->node_end && mas_wr_slot_store(wr_mas)) _ Patches currently in -mm which might be from zhangpeng.00@bytedance.com are maple_tree-add-test-for-mas_wr_modify-fast-path.patch maple_tree-add-test-for-expanding-range-in-rcu-mode.patch maple_tree-optimize-mas_wr_append-also-improve-duplicating-vmas.patch maple_tree-add-a-fast-path-case-in-mas_wr_slot_store.patch