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 2E74846AF21 for ; Tue, 30 Jun 2026 19:09:06 +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=1782846547; cv=none; b=sng2zuwRrQIW6Ymq5DcOi28bUyROOOnBiQ2hNrqiBkcYTCGaZEs5J9412W4J43T77m/cdWH060pH4D4PLo+WFCYkHNUuiU6sKYLLJaiygKOg/INcXDZN1Uq1AHASbKiz25Tf0K9XiJbJFGGCvHKSGo/8Teq5Pb+D56c9FnuDOU4= ARC-Message-Signature:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1782846547; c=relaxed/simple; bh=BZBgqWpVVZQSdhOgtNYPVzq7MpYeDOB6f0imZAFYRkw=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=l+Qkd7ZOhM8WB7NMYcJ1p8fsG/oyL5C/m32BvYUw8v8J3DTxYH5znhiCeB36bxdvfsXbpJ2NHhLqqy93ghTjtehQA0N4aEZGsqwwzZdAJvnV5TRvxBKsT/6Y6D44PG1+pu8Wjtjgbk2C0MWUXeGUkAoZhR0zn7aTYgy/moAu76Q= 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=0ugGImTA; 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="0ugGImTA" 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=RehuvfOSezc9zOkXVOdYQDokSzzkxVMF+i6Xa+KVxvU=; b=0ugGImTA4qN1dYQoeT8DvwkmMK HR6OclU65y7VwqohEjvFaHTQkkwCpIiti8Aa+vp5Bu+iZDA/71GsjCNw65rvzT6X8UaFgg0RBeN2R Fs2xQkR7oVhKBCtm40TLANcTx3P9aXMCKVBAZmblK9ioBXFHVXHmgJtt2z/F3sWMl3ZksGmfcgTd1 s9WZzmTvwb2uFpeXv5h5Zong6/vtpQXgIv9Lx6J3H3t7L5A531XBdRz8QGhZWf6YcDYOQ4FqrR5+Z HiUkE70OkCa5hyYHDtYVdNOHpds/xeHGduT5j6LdExCP+RMku+Fize4zEZTIIQ+44Vr95TXZ4M6PK wrAozD/A==; Received: from [38.23.173.23] (helo=localhost) by bombadil.infradead.org with esmtpsa (Exim 4.99.1 #2 (Red Hat Linux)) id 1wedpR-000000005wg-2WpM; Tue, 30 Jun 2026 19:09:05 +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 11/19] maple_tree: Add bulk parent set helper Date: Tue, 30 Jun 2026 15:08:35 -0400 Message-ID: <20260630190843.3563858-12-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 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. Drop the mas_set_parent() function since the last user has been removed. 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 | 97 +++++++++++++++++++++--------------------------- 1 file changed, 42 insertions(+), 55 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 999a1d095e369..768193406c3db 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -455,46 +455,6 @@ enum maple_type mas_parent_type(struct ma_state *mas, struct maple_enode *enode) return 0; } -/* - * mas_set_parent() - Set the parent node and encode the slot - * @mas: The maple state - * @enode: The encoded maple node. - * @parent: The encoded maple node that is the parent of @enode. - * @slot: The slot that @enode resides in @parent. - * - * Slot number is encoded in the enode->parent bit 3-6 or 2-6, depending on the - * parent type. - */ -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 shift; - unsigned long type; - enum maple_type p_type = mte_node_type(parent); - - MAS_BUG_ON(mas, p_type == maple_dense); - MAS_BUG_ON(mas, p_type == maple_leaf_64); - - switch (p_type) { - case maple_range_64: - case maple_arange_64: - shift = MAPLE_PARENT_SLOT_SHIFT; - type = MAPLE_PARENT_RANGE64; - break; - default: - case maple_dense: - case maple_leaf_64: - shift = type = 0; - break; - } - - val &= ~MAPLE_NODE_MASK; /* Clear all node metadata in parent */ - val |= (slot << shift) | type; - mte_to_node(enode)->parent = ma_parent_ptr(val); -} - /* * mte_parent_slot() - get the parent slot of @enode. * @enode: The encoded maple node. @@ -876,6 +836,42 @@ static inline void ma_set_meta_gap(struct maple_node *mn, enum maple_type mt, meta->gap = offset; } +/* + * 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; + + child = mt_slot_locked(mas->tree, slots, i); + mte_to_node(child)->parent = ma_parent_ptr(pval); + } +} + /* * mat_add() - Add a @dead_enode to the ma_topiary of a list of dead nodes. * @mat: the ma_topiary, a linked list of dead nodes. @@ -1608,14 +1604,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); } /* @@ -1997,15 +1989,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