| lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
|
Open Source and information security mailing list archives
| ||
|
Message-ID: <20260115193647.1695937-2-Liam.Howlett@oracle.com>
Date: Thu, 15 Jan 2026 14:36:20 -0500
From: "Liam R. Howlett" <Liam.Howlett@...cle.com>
To: Andrew Morton <akpm@...ux-foundation.org>
Cc: maple-tree@...ts.infradead.org, linux-mm@...ck.org,
linux-kernel@...r.kernel.org, Suren Baghdasaryan <surenb@...gle.com>,
Matthew Wilcox <willy@...radead.org>,
Sidhartha Kumar <sidhartha.kumar@...cle.com>,
Vlastimil Babka <vbabka@...e.cz>, Alice Ryhl <aliceryhl@...gle.com>,
Kuninori Morimoto <kuninori.morimoto.gx@...esas.com>,
Geert Uytterhoeven <geert@...ux-m68k.org>,
Arnd Bergmann <arnd@...db.de>, Christian Kujau <lists@...dbynature.de>,
"Liam R. Howlett" <Liam.Howlett@...cle.com>
Subject: [PATCH 01/28] maple_tree: Move mas_spanning_rebalance loop to function
Move the loop over the tree levels to its own function.
No intended functional changes.
Signed-off-by: Liam R. Howlett <Liam.Howlett@...cle.com>
---
lib/maple_tree.c | 108 +++++++++++++++++++++++++----------------------
1 file changed, 58 insertions(+), 50 deletions(-)
diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 5aa4c95000188..5c85964b36c58 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -2595,49 +2595,16 @@ static inline void *mtree_range_walk(struct ma_state *mas)
return NULL;
}
-/*
- * mas_spanning_rebalance() - Rebalance across two nodes which may not be peers.
- * @mas: The starting maple state
- * @mast: The maple_subtree_state, keeps track of 4 maple states.
- * @count: The estimated count of iterations needed.
- *
- * Follow the tree upwards from @l_mas and @r_mas for @count, or until the root
- * is hit. First @b_node is split into two entries which are inserted into the
- * next iteration of the loop. @b_node is returned populated with the final
- * iteration. @mas is used to obtain allocations. orig_l_mas keeps track of the
- * nodes that will remain active by using orig_l_mas->index and orig_l_mas->last
- * to account of what has been copied into the new sub-tree. The update of
- * orig_l_mas->last is used in mas_consume to find the slots that will need to
- * be either freed or destroyed. orig_l_mas->depth keeps track of the height of
- * the new sub-tree in case the sub-tree becomes the full tree.
- */
-static void mas_spanning_rebalance(struct ma_state *mas,
+static void mas_spanning_rebalance_loop(struct ma_state *mas,
struct maple_subtree_state *mast, unsigned char count)
{
+
unsigned char split, mid_split;
unsigned char slot = 0;
unsigned char new_height = 0; /* used if node is a new root */
struct maple_enode *left = NULL, *middle = NULL, *right = NULL;
struct maple_enode *old_enode;
- MA_STATE(l_mas, mas->tree, mas->index, mas->index);
- MA_STATE(r_mas, mas->tree, mas->index, mas->last);
- MA_STATE(m_mas, mas->tree, mas->index, mas->index);
-
- /*
- * The tree needs to be rebalanced and leaves need to be kept at the same level.
- * Rebalancing is done by use of the ``struct maple_topiary``.
- */
- mast->l = &l_mas;
- mast->m = &m_mas;
- mast->r = &r_mas;
- l_mas.status = r_mas.status = m_mas.status = ma_none;
-
- /* Check if this is not root and has sufficient data. */
- if (((mast->orig_l->min != 0) || (mast->orig_r->max != ULONG_MAX)) &&
- unlikely(mast->bn->b_end <= mt_min_slots[mast->bn->type]))
- mast_spanning_rebalance(mast);
-
/*
* Each level of the tree is examined and balanced, pushing data to the left or
* right, or rebalancing against left or right nodes is employed to avoid
@@ -2672,10 +2639,10 @@ static void mas_spanning_rebalance(struct ma_state *mas,
mast_ascend(mast);
mast_combine_cp_left(mast);
- l_mas.offset = mast->bn->b_end;
- mab_set_b_end(mast->bn, &l_mas, left);
- mab_set_b_end(mast->bn, &m_mas, middle);
- mab_set_b_end(mast->bn, &r_mas, right);
+ mast->l->offset = mast->bn->b_end;
+ mab_set_b_end(mast->bn, mast->l, left);
+ mab_set_b_end(mast->bn, mast->m, middle);
+ mab_set_b_end(mast->bn, mast->r, right);
/* Copy anything necessary out of the right node. */
mast_combine_cp_right(mast);
@@ -2708,17 +2675,17 @@ static void mas_spanning_rebalance(struct ma_state *mas,
count++;
}
- l_mas.node = mt_mk_node(ma_mnode_ptr(mas_pop_node(mas)),
+ mast->l->node = mt_mk_node(ma_mnode_ptr(mas_pop_node(mas)),
mte_node_type(mast->orig_l->node));
- mab_mas_cp(mast->bn, 0, mt_slots[mast->bn->type] - 1, &l_mas, true);
+ mab_mas_cp(mast->bn, 0, mt_slots[mast->bn->type] - 1, mast->l, true);
new_height++;
- mas_set_parent(mas, left, l_mas.node, slot);
+ mas_set_parent(mas, left, mast->l->node, slot);
if (middle)
- mas_set_parent(mas, middle, l_mas.node, ++slot);
+ mas_set_parent(mas, middle, mast->l->node, ++slot);
if (right)
- mas_set_parent(mas, right, l_mas.node, ++slot);
+ mas_set_parent(mas, right, mast->l->node, ++slot);
if (mas_is_root_limits(mast->l)) {
new_root:
@@ -2726,20 +2693,61 @@ static void mas_spanning_rebalance(struct ma_state *mas,
while (!mte_is_root(mast->orig_l->node))
mast_ascend(mast);
} else {
- mas_mn(&l_mas)->parent = mas_mn(mast->orig_l)->parent;
+ mas_mn(mast->l)->parent = mas_mn(mast->orig_l)->parent;
}
old_enode = mast->orig_l->node;
- mas->depth = l_mas.depth;
- mas->node = l_mas.node;
- mas->min = l_mas.min;
- mas->max = l_mas.max;
- mas->offset = l_mas.offset;
+ mas->depth = mast->l->depth;
+ mas->node = mast->l->node;
+ mas->min = mast->l->min;
+ mas->max = mast->l->max;
+ mas->offset = mast->l->offset;
mas_wmb_replace(mas, old_enode, new_height);
mtree_range_walk(mas);
return;
}
+/*
+ * mas_spanning_rebalance() - Rebalance across two nodes which may not be peers.
+ * @mas: The starting maple state
+ * @mast: The maple_subtree_state, keeps track of 4 maple states.
+ * @count: The estimated count of iterations needed.
+ *
+ * Follow the tree upwards from @l_mas and @r_mas for @count, or until the root
+ * is hit. First @b_node is split into two entries which are inserted into the
+ * next iteration of the loop. @b_node is returned populated with the final
+ * iteration. @mas is used to obtain allocations. orig_l_mas keeps track of the
+ * nodes that will remain active by using orig_l_mas->index and orig_l_mas->last
+ * to account of what has been copied into the new sub-tree. The update of
+ * orig_l_mas->last is used in mas_consume to find the slots that will need to
+ * be either freed or destroyed. orig_l_mas->depth keeps track of the height of
+ * the new sub-tree in case the sub-tree becomes the full tree.
+ */
+static void mas_spanning_rebalance(struct ma_state *mas,
+ struct maple_subtree_state *mast, unsigned char count)
+{
+
+ MA_STATE(l_mas, mas->tree, mas->index, mas->index);
+ MA_STATE(r_mas, mas->tree, mas->index, mas->last);
+ MA_STATE(m_mas, mas->tree, mas->index, mas->index);
+
+ /*
+ * The tree needs to be rebalanced and leaves need to be kept at the same level.
+ * Rebalancing is done by use of the ``struct maple_topiary``.
+ */
+ mast->l = &l_mas;
+ mast->m = &m_mas;
+ mast->r = &r_mas;
+ l_mas.status = r_mas.status = m_mas.status = ma_none;
+
+ /* Check if this is not root and has sufficient data. */
+ if (((mast->orig_l->min != 0) || (mast->orig_r->max != ULONG_MAX)) &&
+ unlikely(mast->bn->b_end <= mt_min_slots[mast->bn->type]))
+ mast_spanning_rebalance(mast);
+
+ mas_spanning_rebalance_loop(mas, mast, count);
+}
+
/*
* mas_rebalance() - Rebalance a given node.
* @mas: The maple state
--
2.47.3
Powered by blists - more mailing lists