From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from bombadil.infradead.org (bombadil.infradead.org [198.137.202.133]) (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 1973E47D952 for ; Tue, 30 Jun 2026 19:09:21 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=198.137.202.133 ARC-Seal:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1782846563; cv=none; b=beTmCG8Y7ihyuwEdgzzHo9L1Zp//eoePDUf2/aveJzeddHh+VOE7XzW+kqG71G7pPWqz0S2bxiUYNhDArhIzaal5kA1rutRtHnwyZ3lVbznZpQeSitrMSlEDlf9di0q1m47vRovpfBzP9vhQKuPuaZ0OJMLaXxXovKIQDlmf8A0= ARC-Message-Signature:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1782846563; c=relaxed/simple; bh=TvOdnb7Tg8WFp5b/MCaFDdCkxqW5IHnNsyykp0SJwFg=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=tjgWd+Xer4zNk7ycfF9cmaeHpOYZjbvI87XdBq1X85j97S79LEU8X18SSIKTQgB0H7Cm3WG1ipM2xuXhu6FlH9U2MmW/Gn//k5ovMmiHeHO43EAWacVFYgqay36kZ0CHEvFhFoHNprouL4/tokP+tZNBlNCvWXrr+cm97huqDw8= ARC-Authentication-Results:i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=infradead.org; spf=pass smtp.mailfrom=infradead.org; dkim=pass (2048-bit key) header.d=infradead.org header.i=@infradead.org header.b=axnD4nib; arc=none smtp.client-ip=198.137.202.133 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=infradead.org Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=infradead.org Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=infradead.org header.i=@infradead.org header.b="axnD4nib" DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=infradead.org; s=bombadil.20210309; h=Content-Transfer-Encoding: MIME-Version:References:In-Reply-To:Message-ID:Date:Subject:Cc:To:From:Sender :Reply-To:Content-Type:Content-ID:Content-Description; bh=xzlYIsdi92YMwmj1hZksyU4NuPw53o+SNfTZpxZAXJ4=; b=axnD4nibPwHejwd22BJ0u2lexi uAOchXXE2BSp6T1bEnxHPXtuB4f6FlbtZIwzxE6jsfyJh4JFn62GtISAnfX4VlwRS7M7p3kOQEyrz nN8smyb163+dRemFBe+GNfVSziuPksVIN5uGpMZSwfRZH8FAmaeJrR4QUqe0IGqrY6DtcQg4XDt8t +Rhet2HgAe9CWtpZgCwQjh9OFtMi/zmbYLwaKHILrxGGPXAUFF0NyAcxt2pZQW0GjbT1N9mvXkbPn aoxz2o8i21YgRcM31+NpOoB9Tdy4eE/h0VljlQNzpx7j/YoWy8D5GvidOwrPYdLFDGzeHcd0gP/mR LKNCzw6A==; Received: from [38.23.173.23] (helo=localhost) by bombadil.infradead.org with esmtpsa (Exim 4.99.1 #2 (Red Hat Linux)) id 1wedpf-0000000063S-1UYM; Tue, 30 Jun 2026 19:09:20 +0000 From: "Liam R. Howlett (Oracle)" To: Andrew Morton Cc: linux-mm@kvack.org, linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org, "Liam R. Howlett (Oracle)" Subject: [PATCH v2 18/19] maple_tree: Avoid extra gap calculation Date: Tue, 30 Jun 2026 15:08:42 -0400 Message-ID: <20260630190843.3563858-19-liam@infradead.org> X-Mailer: git-send-email 2.47.3 In-Reply-To: <20260630190843.3563858-1-liam@infradead.org> References: <20260630190843.3563858-1-liam@infradead.org> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: 8bit 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. Signed-off-by: Liam R. Howlett (Oracle) --- lib/maple_tree.c | 28 +++++++++++++++++----------- 1 file changed, 17 insertions(+), 11 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index afe65ff0f8a6f..4336a98763984 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -1565,14 +1565,26 @@ static inline void mas_parent_gap(struct ma_state *mas, unsigned char offset, 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)) @@ -1582,13 +1594,7 @@ static inline void mas_update_gap(struct ma_state *mas) 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); } /* @@ -2136,8 +2142,8 @@ static inline void mas_wmb_replace(struct ma_state *mas, struct maple_copy *cp) 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); } -- 2.47.3