From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from smtp.kernel.org (aws-us-west-2-korg-mail-alma10-1.taild15c8.ts.net [100.103.45.18]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id CB1A73D969B for ; Fri, 21 Aug 2026 22:44:10 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=100.103.45.18 ARC-Seal:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1787352252; cv=none; b=MfHtYhUxYfxzMEaJgbWdrDgsS7dJ5M3CnAm7HBGhsNae2Nj2uhilEXu26A1wUEGJ/1tznwQoPN7J2Kcn2new1LaXXjVVNOhbvE/P5y11lOl+8h7VLJxpydxEgKnTGa8IPkMdcRMhpRgt/FMYPrfatTTCS8UjO+CRwtYznO5Li1c= ARC-Message-Signature:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1787352252; c=relaxed/simple; bh=RgEZR9F/EokASCvzHPJz4pwkxrgG7+CfEapGo/dxyW8=; h=Date:To:From:Subject:Message-Id; b=UMfux7g1Txu6lYNSFb3l03f8Cd+u0WbawtGTtpO5G0nJ8Z8BzxnceudiEPif0UuhLlEIBVXN3KxaXEJFf1cPaShm6AZdofQIQXSsSNxuQHR9UhbDqE1yCil229mmE+AZU2MYqEKvzr/WLthK2OMoOXEVqSUz+TJmw6AE4ENNktI= ARC-Authentication-Results:i=1; smtp.subspace.kernel.org; dkim=pass (1024-bit key) header.d=linux-foundation.org header.i=@linux-foundation.org header.b=YPjbqtqv; arc=none smtp.client-ip=100.103.45.18 Authentication-Results: smtp.subspace.kernel.org; dkim=pass (1024-bit key) header.d=linux-foundation.org header.i=@linux-foundation.org header.b="YPjbqtqv" Received: by smtp.kernel.org (Postfix) with ESMTPSA id A1C3B1F000E9; Fri, 21 Aug 2026 22:44:10 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linux-foundation.org; s=korg; t=1787352250; bh=KmaRJ9TLyqA1fxX1Zc4+uZzcOwtQNAybqIqZ22oQlrs=; h=Date:To:From:Subject; b=YPjbqtqv+RiA514oftFA+FUoS0TvtydgDFBwTSOhHsDXpAEbHu9h5GCNLtmobHAp7 LZBHFZIgSpuKcI+0DvP950Y/sWdWLWHQCMWroJmiZ9xlqsyyJsogTW0v48reDzkYl+ hPkDiujPJ0ZiPPtgSlytdRsFS3GavgGRxyh7Iou0= Date: Fri, 21 Aug 2026 15:44:10 -0700 To: mm-commits@vger.kernel.org,liam@infradead.org,akpm@linux-foundation.org From: Andrew Morton Subject: + maple_tree-avoid-extra-gap-calculation.patch added to mm-unstable branch Message-Id: <20260821224410.A1C3B1F000E9@smtp.kernel.org> Precedence: bulk X-Mailing-List: mm-commits@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: The patch titled Subject: maple_tree: avoid extra gap calculation has been added to the -mm mm-unstable branch. Its filename is maple_tree-avoid-extra-gap-calculation.patch This patch will shortly appear at https://git.kernel.org/pub/scm/linux/kernel/git/akpm/25-new.git/tree/patches/maple_tree-avoid-extra-gap-calculation.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 various branches at git://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm and is updated there most days ------------------------------------------------------ From: "Liam R. Howlett (Oracle)" Subject: maple_tree: avoid extra gap calculation Date: Fri, 21 Aug 2026 15:26:26 -0400 Prior to ending the ascension loop of larger operations like split, rebalance, and spanning store the gap in the node had been calculated. Once the node is inserted into the tree, the gap is recalculated in mas_update_gap(). This can be avoided by creating a helper for mas_update_gap() that accepts the known gap value, which reduces the operations required for gap updating path. Link: https://lore.kernel.org/20260821192627.4085470-19-liam@infradead.org Signed-off-by: Liam R. Howlett (Oracle) Cc: Boqun Feng Cc: Breno Leitao Cc: Chris Mason Cc: Chuck Lever Cc: Ingo Molnar Cc: Jason Gunthorpe Cc: Joe Perches Cc: Peter Zijlstra Cc: Rik van Riel Cc: Waiman Long Cc: Will Deacon Signed-off-by: Andrew Morton --- lib/maple_tree.c | 28 +++++++++++++++++----------- 1 file changed, 17 insertions(+), 11 deletions(-) --- a/lib/maple_tree.c~maple_tree-avoid-extra-gap-calculation +++ a/lib/maple_tree.c @@ -1566,14 +1566,26 @@ ascend: goto ascend; } +static __always_inline void mas_update_gap_known(struct ma_state *mas, + unsigned long gap) +{ + unsigned char pslot; + unsigned long p_gap; + + pslot = mte_parent_slot(mas->node); + p_gap = ma_gaps(mte_parent(mas->node), + mas_parent_type(mas, mas->node))[pslot]; + + if (p_gap != gap) + mas_parent_gap(mas, pslot, gap); +} + /* * mas_update_gap() - Update a nodes gaps and propagate up if necessary. * @mas: the maple state. */ static inline void mas_update_gap(struct ma_state *mas) { - unsigned char pslot; - unsigned long p_gap; unsigned long max_gap; if (!mt_is_alloc(mas->tree)) @@ -1583,13 +1595,7 @@ static inline void mas_update_gap(struct return; max_gap = mas_max_gap(mas); - - pslot = mte_parent_slot(mas->node); - p_gap = ma_gaps(mte_parent(mas->node), - mas_parent_type(mas, mas->node))[pslot]; - - if (p_gap != max_gap) - mas_parent_gap(mas, pslot, max_gap); + mas_update_gap_known(mas, max_gap); } /* @@ -2137,8 +2143,8 @@ static inline void mas_wmb_replace(struc mas->node = mt_slot_locked(mas->tree, cp->slot, 0); /* Insert the new data in the tree */ mas_topiary_replace(mas, old_enode, cp->height); - if (!mte_is_leaf(mas->node)) - mas_update_gap(mas); + if (mt_is_alloc(mas->tree) && !mte_is_root(mas->node)) + mas_update_gap_known(mas, cp->gap[0]); mtree_range_walk(mas); } _ Patches currently in -mm which might be from liam@infradead.org are maple_tree-add-rcu-locking-check-when-lockdep-is-enabled.patch locking-lockdep-add-sequence-counter-to-held_lock.patch maple_tree-add-write-lock-checking-with-lockdep-sequence-numbers.patch maple_tree-documentation-fix.patch maple_tree-drop-dead-code-from-mas_extend_spanning_null.patch maple_tree-drop-maple_alloc_slots.patch maple_tree-clarify-comments-on-mas_nomem.patch maple_tree-use-prefetched-value-in-mas_wr_store_type.patch maple_tree-optimise-mas_wr_node_store-when-not-in-rcu-mode.patch maple_tree-micro-optimisation-of-mas_wr_store_type.patch maple_tree-add-bulk-parent-set-helper.patch maple_tree-catch-race-in-mas_alloc_cyclic.patch maple_tree-document-that-erase-may-use-gfp_kernel-for-allocations.patch maple_tree-avoid-mas_erase-and-mtree_erase-failures.patch maple_tree-document-erase-and-allocations-better.patch maple_tree-change-two-gfp-flags-in-tests.patch maple_tree-fix-argument-name-in-header.patch maple_tree-avoid-extra-gap-calculation.patch maple_tree-add-helper-mas_make_walkable.patch