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 A2D0CC7EE24 for ; Fri, 12 May 2023 23:00:34 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S240584AbjELXAc (ORCPT ); Fri, 12 May 2023 19:00:32 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:57860 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S240455AbjELW76 (ORCPT ); Fri, 12 May 2023 18:59:58 -0400 Received: from dfw.source.kernel.org (dfw.source.kernel.org [IPv6:2604:1380:4641:c500::1]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 7D22C6595 for ; Fri, 12 May 2023 15:59:33 -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 4F66065940 for ; Fri, 12 May 2023 22:59:33 +0000 (UTC) Received: by smtp.kernel.org (Postfix) with ESMTPSA id A05FDC433D2; Fri, 12 May 2023 22:59:32 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=linux-foundation.org; s=korg; t=1683932372; bh=7MYL8Hgx/NSI2p8cElo7hU4XoZz+VTYdpIs8I8BgSOo=; h=Date:To:From:Subject:From; b=aOqrUV/+7sSmtgfO2JB2v7CUhn/qrTyVlPePF56Abbh3IEMM4g3z6TGZqM8h4ToNL die6D/gpqlAOzFn8XgCvMzcQMjei3nDeZfywjFOt0J9qW7aa0f4Lipuwqs6TFCNdX3 8BjSlBGud1yua9U+KE1PUIpUKgz9qhfSgsbjV0Zs= Date: Fri, 12 May 2023 15:59:32 -0700 To: mm-commits@vger.kernel.org, zhangpeng.00@bytedance.com, vernon2gm@gmail.com, senozhatsky@chromium.org, richard.weiyang@gmail.com, dcb314@hotmail.com, Liam.Howlett@oracle.com, akpm@linux-foundation.org From: Andrew Morton Subject: + maple_tree-try-harder-to-keep-active-node-after-mas_next.patch added to mm-unstable branch Message-Id: <20230512225932.A05FDC433D2@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: try harder to keep active node after mas_next() has been added to the -mm mm-unstable branch. Its filename is maple_tree-try-harder-to-keep-active-node-after-mas_next.patch This patch will shortly appear at https://git.kernel.org/pub/scm/linux/kernel/git/akpm/25-new.git/tree/patches/maple_tree-try-harder-to-keep-active-node-after-mas_next.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: try harder to keep active node after mas_next() Date: Fri, 12 May 2023 14:20:24 -0400 Clean up the mas_next() call to try and keep a node reference when possible. This will avoid re-walking the tree in most cases. Also clean up the single entry tree handling to ensure index/last are consistent with what one would expect. (returning NULL with limit of 1-oo). Link: https://lkml.kernel.org/r/20230512182036.359030-24-Liam.Howlett@oracle.com Signed-off-by: Liam R. Howlett Cc: David Binderman Cc: Peng Zhang Cc: Sergey Senozhatsky Cc: Vernon Yang Cc: Wei Yang Signed-off-by: Andrew Morton --- lib/maple_tree.c | 89 +++++++++++++++++++++++---------------------- 1 file changed, 47 insertions(+), 42 deletions(-) --- a/lib/maple_tree.c~maple_tree-try-harder-to-keep-active-node-after-mas_next +++ a/lib/maple_tree.c @@ -4727,33 +4727,25 @@ static inline void *mas_next_nentry(stru if (ma_dead_node(node)) return NULL; + mas->last = pivot; if (entry) - goto found; + return entry; if (pivot >= max) return NULL; + if (pivot >= mas->max) + return NULL; + mas->index = pivot + 1; mas->offset++; } - if (mas->index > mas->max) { - mas->index = mas->last; - return NULL; - } - - pivot = mas_safe_pivot(mas, pivots, mas->offset, type); + pivot = mas_logical_pivot(mas, pivots, mas->offset, type); entry = mas_slot(mas, slots, mas->offset); if (ma_dead_node(node)) return NULL; - if (!pivot) - return NULL; - - if (!entry) - return NULL; - -found: mas->last = pivot; return entry; } @@ -4782,21 +4774,15 @@ retry: static inline void *mas_next_entry(struct ma_state *mas, unsigned long limit) { void *entry = NULL; - struct maple_enode *prev_node; struct maple_node *node; - unsigned char offset; unsigned long last; enum maple_type mt; - if (mas->index > limit) { - mas->index = mas->last = limit; - mas_pause(mas); + if (mas->last >= limit) return NULL; - } + last = mas->last; retry: - offset = mas->offset; - prev_node = mas->node; node = mas_mn(mas); mt = mte_node_type(mas->node); mas->offset++; @@ -4815,12 +4801,10 @@ retry: if (likely(entry)) return entry; - if (unlikely((mas->index > limit))) - break; + if (unlikely((mas->last >= limit))) + return NULL; next_node: - prev_node = mas->node; - offset = mas->offset; if (unlikely(mas_next_node(mas, node, limit))) { mas_rewalk(mas, last); goto retry; @@ -4830,9 +4814,6 @@ next_node: mt = mte_node_type(mas->node); } - mas->index = mas->last = limit; - mas->offset = offset; - mas->node = prev_node; return NULL; } @@ -5914,6 +5895,8 @@ EXPORT_SYMBOL_GPL(mas_expected_entries); */ void *mas_next(struct ma_state *mas, unsigned long max) { + bool was_none = mas_is_none(mas); + if (mas_is_none(mas) || mas_is_paused(mas)) mas->node = MAS_START; @@ -5921,16 +5904,16 @@ void *mas_next(struct ma_state *mas, uns mas_walk(mas); /* Retries on dead nodes handled by mas_walk */ if (mas_is_ptr(mas)) { - if (!mas->index) { - mas->index = 1; - mas->last = ULONG_MAX; + if (was_none && mas->index == 0) { + mas->index = mas->last = 0; + return mas_root(mas); } + mas->index = 1; + mas->last = ULONG_MAX; + mas->node = MAS_NONE; return NULL; } - if (mas->last == ULONG_MAX) - return NULL; - /* Retries on dead nodes handled by mas_next_entry */ return mas_next_entry(mas, max); } @@ -6054,17 +6037,25 @@ EXPORT_SYMBOL_GPL(mas_pause); */ void *mas_find(struct ma_state *mas, unsigned long max) { + if (unlikely(mas_is_none(mas))) { + if (unlikely(mas->last >= max)) + return NULL; + + mas->index = mas->last; + mas->node = MAS_START; + } + if (unlikely(mas_is_paused(mas))) { - if (unlikely(mas->last == ULONG_MAX)) { - mas->node = MAS_NONE; + if (unlikely(mas->last >= max)) return NULL; - } + mas->node = MAS_START; mas->index = ++mas->last; } - if (unlikely(mas_is_none(mas))) - mas->node = MAS_START; + + if (unlikely(mas_is_ptr(mas))) + goto ptr_out_of_range; if (unlikely(mas_is_start(mas))) { /* First run or continue */ @@ -6076,13 +6067,27 @@ void *mas_find(struct ma_state *mas, uns entry = mas_walk(mas); if (entry) return entry; + } - if (unlikely(!mas_searchable(mas))) + if (unlikely(!mas_searchable(mas))) { + if (unlikely(mas_is_ptr(mas))) + goto ptr_out_of_range; + + return NULL; + } + + if (mas->index == max) return NULL; /* Retries on dead nodes handled by mas_next_entry */ return mas_next_entry(mas, max); + +ptr_out_of_range: + mas->node = MAS_NONE; + mas->index = 1; + mas->last = ULONG_MAX; + return NULL; } EXPORT_SYMBOL_GPL(mas_find); @@ -6513,7 +6518,7 @@ retry: if (entry) goto unlock; - while (mas_searchable(&mas) && (mas.index < max)) { + while (mas_searchable(&mas) && (mas.last < max)) { entry = mas_next_entry(&mas, max); if (likely(entry && !xa_is_zero(entry))) break; _ 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