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 3FC53425CE5 for ; Mon, 29 Jun 2026 14:42:50 +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=1782744171; cv=none; b=YIiaO644sbiys23nilDYe1/re1EEkutt9oAMz0WQ5kjYnXu2Fhum9ntVvT87MlBB8RXbgrxYQO3eZ9kKZCFMOfhI8YTDtFGe1LbftwU4RBH0eWGVG1ZmXk9Udp93nxKULn+GnLarmqlgZ/vxMd23wCguQtCPDitf/QZZ4P7zj2s= ARC-Message-Signature:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1782744171; c=relaxed/simple; bh=LPoLFbckkLWFDeiDGCKZD/dHj3xcIa0cUj6Iby9FJmg=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=lhCJngct+JThVUu+4kumbQBz0FuqXbr1IX0pgC6cWc8m1s+L20ASguQ9Y1bYBrMBCmDeCzu2qxLF0HvNnrbiqqjVX7sXgiTzYZGzS27CPN7Dl/ycjdwkzdb/8+uyGiSDgUZ9EW8Kpk7+dF2N9i2SFtKJTNRC8jeCAkHTc5YgiXQ= 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=OYjRcMVT; 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="OYjRcMVT" 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=SDtINFsEXgJAYq83PFKVlhRpnIRfNfxztGiIGve8N6Y=; b=OYjRcMVTO52rjDgaELicVF/KGw w1xNsFR62AWXMxz+Bs6C4YXCzXiYuqEcd0I/DfywbfZH9Xffy6Xx3dMtDz9LCSIILXA6C6Q/RFQHc 1cQ4HVPSkcKwT9IvsbpeTk1Ix+kwCk+ugukSmMefpkSKPwgInnBxhPXUWl9l/gPZ4rLSDKL63vsLV V5UaRibJVQtbfLNLK2dvFiRzF1xKsHceP3kSbk10c4/9dSrpC2Nnnmfu2HQXRcBFM3ucAC9qepP7d /StE6i07N6JVfJ7yAydKYQQXeTSKl6wnecZG5wRqdNI7MSvAVdtzPlLl5uL3tNz0XmoYwEdLHHw2e /FpFaKLQ==; Received: from [38.23.173.23] (helo=localhost) by bombadil.infradead.org with esmtpsa (Exim 4.99.1 #2 (Red Hat Linux)) id 1weDCD-0000000Euch-39QC; Mon, 29 Jun 2026 14:42:49 +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 11/18] maple_tree: Add bulk parent set helper Date: Mon, 29 Jun 2026 10:41:38 -0400 Message-ID: <20260629144145.1572283-12-liam@infradead.org> X-Mailer: git-send-email 2.47.3 In-Reply-To: <20260629144145.1572283-1-liam@infradead.org> References: <20260629144145.1572283-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 Instead of calculating the parent pointer each time for a child, cache the majority of the parent pointer and only change the slot per child. Testing on a tree containing 2048 entries of height 4 had an increased gain of 3.51% on nodes tracking gaps. Signed-off-by: Liam R. Howlett (Oracle) --- lib/maple_tree.c | 59 +++++++++++++++++++++++++++++++++++------------- 1 file changed, 43 insertions(+), 16 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index dd679ba2b8bfa..6531a2af338cd 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -469,7 +469,7 @@ static inline void mas_set_parent(struct ma_state *mas, struct maple_enode *enode, const struct maple_enode *parent, unsigned char slot) { - unsigned long val = (unsigned long)parent; + unsigned long val; unsigned long shift; unsigned long type; enum maple_type p_type = mte_node_type(parent); @@ -490,11 +490,47 @@ void mas_set_parent(struct ma_state *mas, struct maple_enode *enode, break; } + val = (unsigned long)parent; val &= ~MAPLE_NODE_MASK; /* Clear all node metadata in parent */ val |= (slot << shift) | type; mte_to_node(enode)->parent = ma_parent_ptr(val); } +/* + * mas_set_parent_slots() - Bulk operation to set many slot parent pointers + * @mas: The maple state + * @parent: The encoded maple node that is the parent of @enode. + * @slot: The slot that of the @enode. + * @start_slot: The offset into @slot + * @count: The number of slots to set (eg: exclusive) + */ +static inline +void mas_set_parent_slots(struct ma_state *mas, struct maple_enode *parent, + void __rcu **slots, unsigned char start_slot, unsigned char count) +{ + unsigned long val; + unsigned long shift; + unsigned long type; + enum maple_type p_type = mte_node_type(parent); + unsigned char i; + + MAS_BUG_ON(mas, p_type != maple_range_64 && + p_type != maple_arange_64); + + shift = MAPLE_PARENT_SLOT_SHIFT; + type = MAPLE_PARENT_RANGE64; + + val = (unsigned long)parent; + val &= ~MAPLE_NODE_MASK; + + for (i = 0; i < count; i++) { + unsigned long pval = val | ((start_slot + i) << shift) | type; + struct maple_enode *child = (struct maple_enode *)slots[i]; + + mte_to_node(child)->parent = ma_parent_ptr(pval); + } +} + /* * mte_parent_slot() - get the parent slot of @enode. * @enode: The encoded maple node. @@ -1605,14 +1641,10 @@ static inline void mas_adopt_children(struct ma_state *mas, struct maple_node *node = mte_to_node(parent); void __rcu **slots = ma_slots(node, type); unsigned long *pivots = ma_pivots(node, type); - struct maple_enode *child; - unsigned char offset; + unsigned char end; - offset = ma_data_end(node, type, pivots, mas->max); - do { - child = mas_slot_locked(mas, slots, offset); - mas_set_parent(mas, child, parent, offset); - } while (offset--); + end = ma_data_end(node, type, pivots, mas->max); + mas_set_parent_slots(mas, parent, slots, 0, end + 1); } /* @@ -1994,15 +2026,10 @@ unsigned long node_copy(struct ma_state *mas, struct maple_node *src, s_slots = ma_slots(src, s_mt) + start; s_pivots = ma_pivots(src, s_mt) + start; memcpy(d_slots, s_slots, size * sizeof(void __rcu *)); - if (!ma_is_leaf(d_mt) && s_mt == maple_copy) { - struct maple_enode *edst = mt_mk_node(dst, d_mt); - - for (int i = 0; i < size; i++) - mas_set_parent(mas, - mt_slot_locked(mas->tree, d_slots, i), - edst, d_start + i); - } + if (!ma_is_leaf(d_mt) && s_mt == maple_copy) + mas_set_parent_slots(mas, mt_mk_node(dst, d_mt), + d_slots, d_start, size); d_gaps = ma_gaps(dst, d_mt); if (d_gaps) { -- 2.47.3