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 A1E9DC7EE2E for ; Thu, 1 Jun 2023 22:46:06 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S230492AbjFAWqF (ORCPT ); Thu, 1 Jun 2023 18:46:05 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:52394 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S232102AbjFAWp7 (ORCPT ); Thu, 1 Jun 2023 18:45:59 -0400 Received: from dfw.source.kernel.org (dfw.source.kernel.org [139.178.84.217]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 76C0019B for ; Thu, 1 Jun 2023 15:45:57 -0700 (PDT) Received: from smtp.kernel.org (relay.kernel.org [52.25.139.140]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by dfw.source.kernel.org (Postfix) with ESMTPS id 555E7649EB for ; Thu, 1 Jun 2023 22:45:57 +0000 (UTC) Received: by smtp.kernel.org (Postfix) with ESMTPSA id AE6A0C433EF; Thu, 1 Jun 2023 22:45:56 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=linux-foundation.org; s=korg; t=1685659556; bh=q8BnlX1KXnGG0csdsjHN9Acp2BurOeTOr0udWA3wg6E=; h=Date:To:From:Subject:From; b=gmEew9HmpxcurgsLMGL5XDxl4j9m/JfNe2+F8JQWokqR/B1AQNGBtxLxPhPn2pV7Y iyBuMnGf5DGxwfuaeT4jM3ypKbeVye1CzJ8MHjnNSgtRbCNjpsX+xKeIXpIh8RpKoQ XNlML5k+rshcz2/7HbnLRNYWN216VTyFwIaWYz7I= Date: Thu, 01 Jun 2023 15:45:56 -0700 To: mm-commits@vger.kernel.org, Liam.Howlett@oracle.com, akpm@linux-foundation.org From: Andrew Morton Subject: + maple_tree-refine-mas_preallocate-node-calculations.patch added to mm-unstable branch Message-Id: <20230601224556.AE6A0C433EF@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: refine mas_preallocate() node calculations has been added to the -mm mm-unstable branch. Its filename is maple_tree-refine-mas_preallocate-node-calculations.patch This patch will shortly appear at https://git.kernel.org/pub/scm/linux/kernel/git/akpm/25-new.git/tree/patches/maple_tree-refine-mas_preallocate-node-calculations.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: "Liam R. Howlett" Subject: maple_tree: refine mas_preallocate() node calculations Date: Wed, 31 May 2023 22:16:04 -0400 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. Link: https://lkml.kernel.org/r/20230601021605.2823123-14-Liam.Howlett@oracle.com Signed-off-by: Liam R. Howlett Signed-off-by: Andrew Morton --- lib/maple_tree.c | 44 +++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 43 insertions(+), 1 deletion(-) --- a/lib/maple_tree.c~maple_tree-refine-mas_preallocate-node-calculations +++ a/lib/maple_tree.c @@ -5541,9 +5541,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; _ Patches currently in -mm which might be from Liam.Howlett@oracle.com are maple_tree-fix-static-analyser-cppcheck-issue.patch maple_tree-avoid-unnecessary-ascending.patch maple_tree-clean-up-mas_dfs_postorder.patch maple_tree-add-debug-bug_on-and-warn_on-variants.patch maple_tree-use-mas_bug_on-when-setting-a-leaf-node-as-a-parent.patch maple_tree-use-mas_bug_on-in-mas_set_height.patch maple_tree-use-mas_bug_on-from-mas_topiary_range.patch maple_tree-use-mas_wr_bug_on-in-mas_store_prealloc.patch maple_tree-use-mas_bug_on-prior-to-calling-mas_meta_gap.patch maple_tree-return-error-on-mte_pivots-out-of-range.patch maple_tree-make-test-code-work-without-debug-enabled.patch mm-update-validate_mm-to-use-vma-iterator.patch mm-update-vma_iter_store-to-use-mas_warn_on.patch maple_tree-add-__init-and-__exit-to-test-module.patch maple_tree-remove-unnecessary-check-from-mas_destroy.patch maple_tree-mas_start-reset-depth-on-dead-node.patch mm-mmap-change-do_vmi_align_munmap-for-maple-tree-iterator-changes.patch maple_tree-try-harder-to-keep-active-node-after-mas_next.patch maple_tree-try-harder-to-keep-active-node-with-mas_prev.patch maple_tree-revise-limit-checks-in-mas_empty_area_rev.patch maple_tree-fix-testing-mas_empty_area.patch maple_tree-introduce-mas_next_slot-interface.patch maple_tree-add-mas_next_range-and-mas_find_range-interfaces.patch maple_tree-relocate-mas_rewalk-and-mas_rewalk_if_dead.patch maple_tree-introduce-mas_prev_slot-interface.patch maple_tree-add-mas_prev_range-and-mas_find_range_rev-interface.patch maple_tree-clear-up-index-and-last-setting-in-single-entry-tree.patch maple_tree-update-testing-code-for-mas_nextprevwalk.patch mm-add-vma_iter_nextprev_range-to-vma-iterator.patch mm-avoid-rewalk-in-mmap_region.patch maple_tree-add-benchmarking-for-mas_for_each.patch maple_tree-add-benchmarking-for-mas_prev.patch mm-move-unmap_vmas-declaration-to-internal-header.patch mm-change-do_vmi_align_munmap-side-tree-index.patch mm-remove-prev-check-from-do_vmi_align_munmap.patch maple_tree-introduce-__mas_set_range.patch mm-remove-re-walk-from-mmap_region.patch maple_tree-re-introduce-entry-to-mas_preallocate-arguments.patch mm-use-vma_iter_clear_gfp-in-nommu.patch mm-set-up-vma-iterator-for-vma_iter_prealloc-calls.patch maple_tree-move-mas_wr_end_piv-below-mas_wr_extend_null.patch maple_tree-update-mas_preallocate-testing.patch maple_tree-refine-mas_preallocate-node-calculations.patch mm-mmap-change-vma-iteration-order-in-do_vmi_align_munmap.patch userfaultfd-fix-regression-in-userfaultfd_unmap_prep.patch