From 6884832472730e286d476b64882a5f6856625320 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Fri, 30 Jan 2026 15:59:06 -0500 Subject: maple_tree: fix mas_dup_alloc() sparse warning Patch series "maple_tree: Replace big node with maple copy", v3. The big node struct was created for simplicity of splitting, rebalancing, and spanning store operations by using a copy buffer to create the data necessary prior to breaking it up into 256B nodes. Certain operations were rather tricky due to the restriction of keeping NULL entries together and never at the end of a node (except the right-most node). The big node struct is incompatible with future features that are currently in development. Specifically different node types and different data type sizes for pivots. The big node struct was also a stack variable, which caused issues with certain configurations of kernel build. This series removes big node by introducing another node type which will never be written to the tree: maple_copy. The maple copy node operates more like a scatter/gather operation with a number of sources and destinations of allocated nodes. The sources are copied to the destinations, in turn, until the sources are exhausted. The destination is changed if it is filled or the split location is reached prior to the source data end. New data is inserted by using the maple copy node itself as a source with up to 3 slots and pivots. The data in the maple copy node is the data being written to the tree along with any fragment of the range(s) being overwritten. As with all nodes, the maple copy node is of size 256B. Using a node type allows for the copy operation to treat the new data stored in the maple copy node the same as any other source node. Analysis of the runtime shows no regression or benefit of removing the larger stack structure. The motivation is the ground work to use new node types and to help those with odd configurations that have had issues. The change was tested by myself using mm_tests on amd64 and by Suren on android (arm64). Limited testing on s390 qemu was also performed using stress-ng on the virtual memory, which should cover many corner cases. This patch (of 30): Use RCU_INIT_POINTER to initialize an rcu pointer to an initial value since there are no readers within the tree being created during duplication. There is no risk of readers seeing the initialized or uninitialized value until after the synchronization call in mas_dup_buld(). Link: https://lkml.kernel.org/r/20260130205935.2559335-1-Liam.Howlett@oracle.com Link: https://lkml.kernel.org/r/20260130205935.2559335-2-Liam.Howlett@oracle.com Signed-off-by: Liam R. Howlett Cc: Alice Ryhl Cc: Andrew Ballance Cc: Arnd Bergmann Cc: Christian Kujau Cc: Geert Uytterhoeven Cc: Kuninori Morimoto Cc: Matthew Wilcox (Oracle) Cc: SeongJae Park Cc: Sidhartha Kumar Cc: Suren Baghdasaryan Cc: Vlastimil Babka Signed-off-by: Andrew Morton --- lib/maple_tree.c | 11 +++++++++-- 1 file changed, 9 insertions(+), 2 deletions(-) (limited to 'lib') diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 5aa4c9500018..0e0158ee7ba5 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -6260,8 +6260,15 @@ static inline void mas_dup_alloc(struct ma_state *mas, struct ma_state *new_mas, for (i = 0; i < count; i++) { val = (unsigned long)mt_slot_locked(mas->tree, slots, i); val &= MAPLE_NODE_MASK; - new_slots[i] = ma_mnode_ptr((unsigned long)mas_pop_node(mas) | - val); + /* + * Warning, see rcu_assign_pointer() documentation. Since this + * is a duplication of a tree, there are no readers walking the + * tree until after the rcu_assign_pointer() call in + * mas_dup_build(). + */ + RCU_INIT_POINTER(new_slots[i], + ma_mnode_ptr((unsigned long)mas_pop_node(mas) | + val)); } } -- cgit From 3e302560b9b49f76d97f431d7b9de6829344ba87 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Fri, 30 Jan 2026 15:59:07 -0500 Subject: maple_tree: move mas_spanning_rebalance loop to function Move the loop over the tree levels to its own function. No intended functional changes. Link: https://lkml.kernel.org/r/20260130205935.2559335-3-Liam.Howlett@oracle.com Signed-off-by: Liam R. Howlett Cc: Alice Ryhl Cc: Andrew Ballance Cc: Arnd Bergmann Cc: Christian Kujau Cc: Geert Uytterhoeven Cc: Kuninori Morimoto Cc: Matthew Wilcox (Oracle) Cc: SeongJae Park Cc: Sidhartha Kumar Cc: Suren Baghdasaryan Cc: Vlastimil Babka Signed-off-by: Andrew Morton --- lib/maple_tree.c | 108 +++++++++++++++++++++++++++++-------------------------- 1 file changed, 58 insertions(+), 50 deletions(-) (limited to 'lib') diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 0e0158ee7ba5..70ad474e6ed1 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -2595,49 +2595,16 @@ dead_node: 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 @@ new_root: 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 -- cgit From df11f9ee8f5dbe4d8a0a61c70eb5a5d37d77c8a6 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Fri, 30 Jan 2026 15:59:08 -0500 Subject: maple_tree: extract use of big node from mas_wr_spanning_store() Isolate big node to use in its own function. No functional changes intended. Link: https://lkml.kernel.org/r/20260130205935.2559335-4-Liam.Howlett@oracle.com Signed-off-by: Liam R. Howlett Cc: Alice Ryhl Cc: Andrew Ballance Cc: Arnd Bergmann Cc: Christian Kujau Cc: Geert Uytterhoeven Cc: Kuninori Morimoto Cc: Matthew Wilcox (Oracle) Cc: SeongJae Park Cc: Sidhartha Kumar Cc: Suren Baghdasaryan Cc: Vlastimil Babka Signed-off-by: Andrew Morton --- lib/maple_tree.c | 44 ++++++++++++++++++++++++++------------------ 1 file changed, 26 insertions(+), 18 deletions(-) (limited to 'lib') diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 70ad474e6ed1..9ab42821ee2d 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -2748,6 +2748,30 @@ static void mas_spanning_rebalance(struct ma_state *mas, mas_spanning_rebalance_loop(mas, mast, count); } + +static noinline void mas_wr_spanning_rebalance(struct ma_state *mas, + struct maple_subtree_state *mast, unsigned char height, + struct ma_wr_state *l_wr_mas) +{ + struct maple_big_node b_node; + + memset(&b_node, 0, sizeof(struct maple_big_node)); + /* Copy l_mas and store the value in b_node. */ + mas_store_b_node(l_wr_mas, &b_node, mast->orig_l->end); + /* Copy r_mas into b_node if there is anything to copy. */ + if (mast->orig_r->max > mast->orig_r->last) + mas_mab_cp(mast->orig_r, mast->orig_r->offset, + mast->orig_r->end, &b_node, b_node.b_end + 1); + else + b_node.b_end++; + + /* Stop spanning searches by searching for just index. */ + mast->orig_l->index = mast->orig_l->last = mas->index; + + mast->bn = &b_node; + /* Combine l_mas and r_mas and split them up evenly again. */ + return mas_spanning_rebalance(mas, mast, height); +} /* * mas_rebalance() - Rebalance a given node. * @mas: The maple state @@ -3400,10 +3424,9 @@ done: * span. * @wr_mas: The maple write state */ -static noinline void mas_wr_spanning_store(struct ma_wr_state *wr_mas) +static void mas_wr_spanning_store(struct ma_wr_state *wr_mas) { struct maple_subtree_state mast; - struct maple_big_node b_node; struct ma_state *mas; unsigned char height; @@ -3467,24 +3490,9 @@ static noinline void mas_wr_spanning_store(struct ma_wr_state *wr_mas) return mas_new_root(mas, wr_mas->entry); } - memset(&b_node, 0, sizeof(struct maple_big_node)); - /* Copy l_mas and store the value in b_node. */ - mas_store_b_node(&l_wr_mas, &b_node, l_mas.end); - /* Copy r_mas into b_node if there is anything to copy. */ - if (r_mas.max > r_mas.last) - mas_mab_cp(&r_mas, r_mas.offset, r_mas.end, - &b_node, b_node.b_end + 1); - else - b_node.b_end++; - - /* Stop spanning searches by searching for just index. */ - l_mas.index = l_mas.last = mas->index; - - mast.bn = &b_node; mast.orig_l = &l_mas; mast.orig_r = &r_mas; - /* Combine l_mas and r_mas and split them up evenly again. */ - return mas_spanning_rebalance(mas, &mast, height + 1); + mas_wr_spanning_rebalance(mas, &mast, height + 1, &l_wr_mas); } /* -- cgit From a2ac9935d3305a558cd16f7fb1521146fe86fe74 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Fri, 30 Jan 2026 15:59:09 -0500 Subject: maple_tree: remove unnecessary assignment of orig_l index The index value is already a copy of the maple state so there is no need to set it again. Link: https://lkml.kernel.org/r/20260130205935.2559335-5-Liam.Howlett@oracle.com Signed-off-by: Liam R. Howlett Cc: Alice Ryhl Cc: Andrew Ballance Cc: Arnd Bergmann Cc: Christian Kujau Cc: Geert Uytterhoeven Cc: Kuninori Morimoto Cc: Matthew Wilcox (Oracle) Cc: SeongJae Park Cc: Sidhartha Kumar Cc: Suren Baghdasaryan Cc: Vlastimil Babka Signed-off-by: Andrew Morton --- lib/maple_tree.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'lib') diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 9ab42821ee2d..1e780427c04a 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -2766,7 +2766,7 @@ static noinline void mas_wr_spanning_rebalance(struct ma_state *mas, b_node.b_end++; /* Stop spanning searches by searching for just index. */ - mast->orig_l->index = mast->orig_l->last = mas->index; + mast->orig_l->last = mas->index; mast->bn = &b_node; /* Combine l_mas and r_mas and split them up evenly again. */ -- cgit From 6f2e522186cbd06fef61921a55375dfeb7885f2a Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Fri, 30 Jan 2026 15:59:10 -0500 Subject: maple_tree: inline mas_spanning_rebalance() into mas_wr_spanning_rebalance() Copy the contents of mas_spanning_rebalance() into mas_wr_spanning_rebalance(), in preparation of removing initial big node use. No functional changes intended. Link: https://lkml.kernel.org/r/20260130205935.2559335-6-Liam.Howlett@oracle.com Signed-off-by: Liam R. Howlett Cc: Alice Ryhl Cc: Andrew Ballance Cc: Arnd Bergmann Cc: Christian Kujau Cc: Geert Uytterhoeven Cc: Kuninori Morimoto Cc: Matthew Wilcox (Oracle) Cc: SeongJae Park Cc: Sidhartha Kumar Cc: Suren Baghdasaryan Cc: Vlastimil Babka Signed-off-by: Andrew Morton --- lib/maple_tree.c | 20 +++++++++++++++++++- 1 file changed, 19 insertions(+), 1 deletion(-) (limited to 'lib') diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 1e780427c04a..fb14ce4a49c3 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -2754,6 +2754,9 @@ static noinline void mas_wr_spanning_rebalance(struct ma_state *mas, struct ma_wr_state *l_wr_mas) { struct maple_big_node b_node; + 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); memset(&b_node, 0, sizeof(struct maple_big_node)); /* Copy l_mas and store the value in b_node. */ @@ -2770,7 +2773,22 @@ static noinline void mas_wr_spanning_rebalance(struct ma_state *mas, mast->bn = &b_node; /* Combine l_mas and r_mas and split them up evenly again. */ - return mas_spanning_rebalance(mas, mast, height); + + /* + * 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, height); } /* * mas_rebalance() - Rebalance a given node. -- cgit From 3dd3dbaac179e36861ca065cbbd7b89860ef883a Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Fri, 30 Jan 2026 15:59:11 -0500 Subject: maple_tree: make ma_wr_states reliable for reuse in spanning store mas_extend_spanning_null() was not modifying the range min and range max of the resulting store operation. The result was that the maple write state no longer matched what the write was doing. This was not an issue as the values were previously not used, but to make the ma_wr_state usable in future changes, the range min/max stored in the ma_wr_state for left and right need to be consistent with the operation. Link: https://lkml.kernel.org/r/20260130205935.2559335-7-Liam.Howlett@oracle.com Signed-off-by: Liam R. Howlett Cc: Alice Ryhl Cc: Andrew Ballance Cc: Arnd Bergmann Cc: Christian Kujau Cc: Geert Uytterhoeven Cc: Kuninori Morimoto Cc: Matthew Wilcox (Oracle) Cc: SeongJae Park Cc: Sidhartha Kumar Cc: Suren Baghdasaryan Cc: Vlastimil Babka Signed-off-by: Andrew Morton --- lib/maple_tree.c | 2 ++ 1 file changed, 2 insertions(+) (limited to 'lib') diff --git a/lib/maple_tree.c b/lib/maple_tree.c index fb14ce4a49c3..ab14876bebf7 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -3319,6 +3319,7 @@ static inline void mas_extend_spanning_null(struct ma_wr_state *l_wr_mas, l_mas->index = l_mas->min; l_mas->offset = l_slot - 1; + l_wr_mas->r_min = l_mas->index; } if (!r_wr_mas->content) { @@ -3331,6 +3332,7 @@ static inline void mas_extend_spanning_null(struct ma_wr_state *l_wr_mas, r_mas->last = mas_safe_pivot(r_mas, r_wr_mas->pivots, r_wr_mas->type, r_mas->offset + 1); r_mas->offset++; + r_wr_mas->r_max = r_mas->last; } } -- cgit From 41bcc348f23feacb2b6c16dd0b7aa7d024ce93cc Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Fri, 30 Jan 2026 15:59:12 -0500 Subject: maple_tree: remove l_wr_mas from mas_wr_spanning_rebalance Use the wr_mas instead of creating another variable on the stack. Take the opportunity to remove l_mas from being used anywhere but in the maple_subtree_state. Link: https://lkml.kernel.org/r/20260130205935.2559335-8-Liam.Howlett@oracle.com Signed-off-by: Liam R. Howlett Cc: Alice Ryhl Cc: Andrew Ballance Cc: Arnd Bergmann Cc: Christian Kujau Cc: Geert Uytterhoeven Cc: Kuninori Morimoto Cc: Matthew Wilcox (Oracle) Cc: SeongJae Park Cc: Sidhartha Kumar Cc: Suren Baghdasaryan Cc: Vlastimil Babka Signed-off-by: Andrew Morton --- lib/maple_tree.c | 19 ++++++++----------- 1 file changed, 8 insertions(+), 11 deletions(-) (limited to 'lib') diff --git a/lib/maple_tree.c b/lib/maple_tree.c index ab14876bebf7..afa39bbd687c 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -2751,7 +2751,7 @@ static void mas_spanning_rebalance(struct ma_state *mas, static noinline void mas_wr_spanning_rebalance(struct ma_state *mas, struct maple_subtree_state *mast, unsigned char height, - struct ma_wr_state *l_wr_mas) + struct ma_wr_state *wr_mas) { struct maple_big_node b_node; MA_STATE(l_mas, mas->tree, mas->index, mas->index); @@ -2760,7 +2760,7 @@ static noinline void mas_wr_spanning_rebalance(struct ma_state *mas, memset(&b_node, 0, sizeof(struct maple_big_node)); /* Copy l_mas and store the value in b_node. */ - mas_store_b_node(l_wr_mas, &b_node, mast->orig_l->end); + mas_store_b_node(wr_mas, &b_node, mast->orig_l->end); /* Copy r_mas into b_node if there is anything to copy. */ if (mast->orig_r->max > mast->orig_r->last) mas_mab_cp(mast->orig_r, mast->orig_r->offset, @@ -3454,7 +3454,6 @@ static void mas_wr_spanning_store(struct ma_wr_state *wr_mas) MA_STATE(l_mas, NULL, 0, 0); MA_STATE(r_mas, NULL, 0, 0); MA_WR_STATE(r_wr_mas, &r_mas, wr_mas->entry); - MA_WR_STATE(l_wr_mas, &l_mas, wr_mas->entry); /* * A store operation that spans multiple nodes is called a spanning @@ -3494,25 +3493,23 @@ static void mas_wr_spanning_store(struct ma_wr_state *wr_mas) r_mas.last = r_mas.index = mas->last; /* Set up left side. */ - l_mas = *mas; - mas_wr_walk_index(&l_wr_mas); + mas_wr_walk_index(wr_mas); if (!wr_mas->entry) { - mas_extend_spanning_null(&l_wr_mas, &r_wr_mas); - mas->offset = l_mas.offset; - mas->index = l_mas.index; - mas->last = l_mas.last = r_mas.last; + mas_extend_spanning_null(wr_mas, &r_wr_mas); + mas->last = r_mas.last; } /* expanding NULLs may make this cover the entire range */ - if (!l_mas.index && r_mas.last == ULONG_MAX) { + if (!mas->index && r_mas.last == ULONG_MAX) { mas_set_range(mas, 0, ULONG_MAX); return mas_new_root(mas, wr_mas->entry); } + l_mas = *mas; mast.orig_l = &l_mas; mast.orig_r = &r_mas; - mas_wr_spanning_rebalance(mas, &mast, height + 1, &l_wr_mas); + mas_wr_spanning_rebalance(mas, &mast, height + 1, wr_mas); } /* -- cgit From 368015952767753abdf13e62b31e58b8107fc916 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Fri, 30 Jan 2026 15:59:13 -0500 Subject: maple_tree: don't pass through height in mas_wr_spanning_store Height is not used locally in the function, so call the height argument closer to where it is passed in the next level. Link: https://lkml.kernel.org/r/20260130205935.2559335-9-Liam.Howlett@oracle.com Signed-off-by: Liam R. Howlett Cc: Alice Ryhl Cc: Andrew Ballance Cc: Arnd Bergmann Cc: Christian Kujau Cc: Geert Uytterhoeven Cc: Kuninori Morimoto Cc: Matthew Wilcox (Oracle) Cc: SeongJae Park Cc: Sidhartha Kumar Cc: Suren Baghdasaryan Cc: Vlastimil Babka Signed-off-by: Andrew Morton --- lib/maple_tree.c | 9 ++++----- 1 file changed, 4 insertions(+), 5 deletions(-) (limited to 'lib') diff --git a/lib/maple_tree.c b/lib/maple_tree.c index afa39bbd687c..91d3fb7ac39c 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -2750,10 +2750,10 @@ static void mas_spanning_rebalance(struct ma_state *mas, static noinline void mas_wr_spanning_rebalance(struct ma_state *mas, - struct maple_subtree_state *mast, unsigned char height, - struct ma_wr_state *wr_mas) + struct maple_subtree_state *mast, struct ma_wr_state *wr_mas) { struct maple_big_node b_node; + unsigned char height; 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); @@ -2788,6 +2788,7 @@ static noinline void mas_wr_spanning_rebalance(struct ma_state *mas, unlikely(mast->bn->b_end <= mt_min_slots[mast->bn->type])) mast_spanning_rebalance(mast); + height = mas_mt_height(mas) + 1; mas_spanning_rebalance_loop(mas, mast, height); } /* @@ -3448,7 +3449,6 @@ static void mas_wr_spanning_store(struct ma_wr_state *wr_mas) { struct maple_subtree_state mast; struct ma_state *mas; - unsigned char height; /* Left and Right side of spanning store */ MA_STATE(l_mas, NULL, 0, 0); @@ -3476,7 +3476,6 @@ static void mas_wr_spanning_store(struct ma_wr_state *wr_mas) * Node rebalancing may occur due to this store, so there may be three new * entries per level plus a new root. */ - height = mas_mt_height(mas); /* * Set up right side. Need to get to the next offset after the spanning @@ -3509,7 +3508,7 @@ static void mas_wr_spanning_store(struct ma_wr_state *wr_mas) l_mas = *mas; mast.orig_l = &l_mas; mast.orig_r = &r_mas; - mas_wr_spanning_rebalance(mas, &mast, height + 1, wr_mas); + mas_wr_spanning_rebalance(mas, &mast, wr_mas); } /* -- cgit From 2fce1c3c47caa73ceb0c97d2a3c4c9f470ad736c Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Fri, 30 Jan 2026 15:59:14 -0500 Subject: maple_tree: move maple_subtree_state from mas_wr_spanning_store to mas_wr_spanning_rebalance Moving the maple_subtree_state is necessary for future cleanups and is only set up in mas_wr_spanning_rebalance() but never used. Link: https://lkml.kernel.org/r/20260130205935.2559335-10-Liam.Howlett@oracle.com Signed-off-by: Liam R. Howlett Cc: Alice Ryhl Cc: Andrew Ballance Cc: Arnd Bergmann Cc: Christian Kujau Cc: Geert Uytterhoeven Cc: Kuninori Morimoto Cc: Matthew Wilcox (Oracle) Cc: SeongJae Park Cc: Sidhartha Kumar Cc: Suren Baghdasaryan Cc: Vlastimil Babka Signed-off-by: Andrew Morton --- lib/maple_tree.c | 41 +++++++++++++++++++++-------------------- 1 file changed, 21 insertions(+), 20 deletions(-) (limited to 'lib') diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 91d3fb7ac39c..c5bb341da5e9 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -2750,46 +2750,52 @@ static void mas_spanning_rebalance(struct ma_state *mas, static noinline void mas_wr_spanning_rebalance(struct ma_state *mas, - struct maple_subtree_state *mast, struct ma_wr_state *wr_mas) + struct ma_wr_state *wr_mas, struct ma_wr_state *r_wr_mas) { + struct maple_subtree_state mast; struct maple_big_node b_node; unsigned char height; 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); + MA_STATE(mast_l_mas, NULL, 0, 0); + + mast_l_mas = *mas; + mast.orig_l = &mast_l_mas; + mast.orig_r = r_wr_mas->mas; memset(&b_node, 0, sizeof(struct maple_big_node)); /* Copy l_mas and store the value in b_node. */ - mas_store_b_node(wr_mas, &b_node, mast->orig_l->end); + mas_store_b_node(wr_mas, &b_node, mast.orig_l->end); /* Copy r_mas into b_node if there is anything to copy. */ - if (mast->orig_r->max > mast->orig_r->last) - mas_mab_cp(mast->orig_r, mast->orig_r->offset, - mast->orig_r->end, &b_node, b_node.b_end + 1); + if (mast.orig_r->max > mast.orig_r->last) + mas_mab_cp(mast.orig_r, mast.orig_r->offset, + mast.orig_r->end, &b_node, b_node.b_end + 1); else b_node.b_end++; /* Stop spanning searches by searching for just index. */ - mast->orig_l->last = mas->index; + mast.orig_l->last = mas->index; - mast->bn = &b_node; + mast.bn = &b_node; /* Combine l_mas and r_mas and split them up evenly again. */ /* * 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; + 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); + 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); height = mas_mt_height(mas) + 1; - mas_spanning_rebalance_loop(mas, mast, height); + mas_spanning_rebalance_loop(mas, &mast, height); } /* * mas_rebalance() - Rebalance a given node. @@ -3447,11 +3453,9 @@ done: */ static void mas_wr_spanning_store(struct ma_wr_state *wr_mas) { - struct maple_subtree_state mast; struct ma_state *mas; /* Left and Right side of spanning store */ - MA_STATE(l_mas, NULL, 0, 0); MA_STATE(r_mas, NULL, 0, 0); MA_WR_STATE(r_wr_mas, &r_mas, wr_mas->entry); @@ -3505,10 +3509,7 @@ static void mas_wr_spanning_store(struct ma_wr_state *wr_mas) return mas_new_root(mas, wr_mas->entry); } - l_mas = *mas; - mast.orig_l = &l_mas; - mast.orig_r = &r_mas; - mas_wr_spanning_rebalance(mas, &mast, wr_mas); + mas_wr_spanning_rebalance(mas, wr_mas, &r_wr_mas); } /* -- cgit From 6b74d44b6297de89284cec8a83fce223106c159a Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Fri, 30 Jan 2026 15:59:15 -0500 Subject: maple_tree: correct right ma_wr_state end pivot in mas_wr_spanning_store() The end_piv will be needed in the next patch set and has not been set correctly in this code path. Correct the oversight before using it. Link: https://lkml.kernel.org/r/20260130205935.2559335-11-Liam.Howlett@oracle.com Signed-off-by: Liam R. Howlett Cc: Alice Ryhl Cc: Andrew Ballance Cc: Arnd Bergmann Cc: Christian Kujau Cc: Geert Uytterhoeven Cc: Kuninori Morimoto Cc: Matthew Wilcox (Oracle) Cc: SeongJae Park Cc: Sidhartha Kumar Cc: Suren Baghdasaryan Cc: Vlastimil Babka Signed-off-by: Andrew Morton --- lib/maple_tree.c | 1 + 1 file changed, 1 insertion(+) (limited to 'lib') diff --git a/lib/maple_tree.c b/lib/maple_tree.c index c5bb341da5e9..caac936bd8d4 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -3494,6 +3494,7 @@ static void mas_wr_spanning_store(struct ma_wr_state *wr_mas) r_mas.index = r_mas.last; mas_wr_walk_index(&r_wr_mas); r_mas.last = r_mas.index = mas->last; + r_wr_mas.end_piv = r_wr_mas.r_max; /* Set up left side. */ mas_wr_walk_index(wr_mas); -- cgit From 9ec1e972c3de3106140c18d2a1c7c74795d85a69 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Fri, 30 Jan 2026 15:59:16 -0500 Subject: maple_tree: introduce maple_copy node and use it in mas_spanning_rebalance() Introduce an internal-memory only node type called maple_copy to facilitate internal copy operations. Use it in mas_spanning_rebalance() for just the leaf nodes. Initially, the maple_copy node is used to configure the source nodes and copy the data into the big_node. The maple_copy contains a list of source entries with start and end offsets. One of the maple_copy entries can be itself with an offset of 0 to 2, representing the data where the store partially overwrites entries, or fully overwrites the entry. The side effect is that the source nodes no longer have to worry about partially copying the existing offset if it is not fully overwritten. This is in preparation of removal of the maple big_node, but for the time being the data is copied to the big node to limit the change size. Link: https://lkml.kernel.org/r/20260130205935.2559335-12-Liam.Howlett@oracle.com Signed-off-by: Liam R. Howlett Cc: Alice Ryhl Cc: Andrew Ballance Cc: Arnd Bergmann Cc: Christian Kujau Cc: Geert Uytterhoeven Cc: Kuninori Morimoto Cc: Matthew Wilcox (Oracle) Cc: SeongJae Park Cc: Sidhartha Kumar Cc: Suren Baghdasaryan Cc: Vlastimil Babka Signed-off-by: Andrew Morton --- include/linux/maple_tree.h | 26 +++++++++ lib/maple_tree.c | 140 ++++++++++++++++++++++++++++++++++++++++++--- 2 files changed, 157 insertions(+), 9 deletions(-) (limited to 'lib') diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h index 7b8aad47121e..9bc7fa89bc2e 100644 --- a/include/linux/maple_tree.h +++ b/include/linux/maple_tree.h @@ -139,6 +139,7 @@ enum maple_type { maple_leaf_64, maple_range_64, maple_arange_64, + maple_copy, }; enum store_type { @@ -154,6 +155,30 @@ enum store_type { wr_slot_store, }; +struct maple_copy { + struct { + struct maple_node *node; + unsigned long max; + unsigned char start; + unsigned char end; + enum maple_type mt; + } src[4]; + /* Simulated node */ + void __rcu *slot[3]; + unsigned long min; + union { + unsigned long pivot[3]; + struct { + void *_pad[2]; + unsigned long max; + }; + }; + unsigned char end; + + /*Avoid passing these around */ + unsigned char s_count; +}; + /** * DOC: Maple tree flags * @@ -299,6 +324,7 @@ struct maple_node { }; struct maple_range_64 mr64; struct maple_arange_64 ma64; + struct maple_copy cp; }; }; diff --git a/lib/maple_tree.c b/lib/maple_tree.c index caac936bd8d4..554fdffd6c5b 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -605,6 +605,8 @@ static inline unsigned long *ma_pivots(struct maple_node *node, case maple_range_64: case maple_leaf_64: return node->mr64.pivot; + case maple_copy: + return node->cp.pivot; case maple_dense: return NULL; } @@ -624,6 +626,7 @@ static inline unsigned long *ma_gaps(struct maple_node *node, switch (type) { case maple_arange_64: return node->ma64.gap; + case maple_copy: case maple_range_64: case maple_leaf_64: case maple_dense: @@ -690,6 +693,7 @@ static inline void mte_set_pivot(struct maple_enode *mn, unsigned char piv, case maple_arange_64: node->ma64.pivot[piv] = val; break; + case maple_copy: case maple_dense: break; } @@ -711,6 +715,8 @@ static inline void __rcu **ma_slots(struct maple_node *mn, enum maple_type mt) case maple_range_64: case maple_leaf_64: return mn->mr64.slot; + case maple_copy: + return mn->cp.slot; case maple_dense: return mn->slot; } @@ -2595,6 +2601,110 @@ dead_node: return NULL; } +/* + * cp_leaf_init() - Initialize a maple_copy node for the leaf level of a + * spanning store + * @cp: The maple copy node + * @mas: The maple state + * @l_wr_mas: The left write state of the spanning store + * @r_wr_mas: The right write state of the spanning store + */ +static inline void cp_leaf_init(struct maple_copy *cp, + struct ma_state *mas, struct ma_wr_state *l_wr_mas, + struct ma_wr_state *r_wr_mas) +{ + unsigned char end = 0; + + /* + * WARNING: The use of RCU_INIT_POINTER() makes it extremely important + * to not expose the maple_copy node to any readers. Exposure may + * result in buggy code when a compiler reorders the instructions. + */ + + /* Create entries to insert including split entries to left and right */ + if (l_wr_mas->r_min < mas->index) { + end++; + RCU_INIT_POINTER(cp->slot[0], l_wr_mas->content); + cp->pivot[0] = mas->index - 1; + } + RCU_INIT_POINTER(cp->slot[end], l_wr_mas->entry); + cp->pivot[end] = mas->last; + + if (r_wr_mas->end_piv > mas->last) { + end++; + RCU_INIT_POINTER(cp->slot[end], + r_wr_mas->slots[r_wr_mas->offset_end]); + cp->pivot[end] = r_wr_mas->end_piv; + } + + cp->min = l_wr_mas->r_min; + cp->max = cp->pivot[end]; + cp->end = end; +} + +static inline void append_wr_mas_cp(struct maple_copy *cp, + struct ma_wr_state *wr_mas, unsigned char start, unsigned char end) +{ + unsigned char count; + + count = cp->s_count; + cp->src[count].node = wr_mas->node; + cp->src[count].mt = wr_mas->type; + if (wr_mas->mas->end <= end) + cp->src[count].max = wr_mas->mas->max; + else + cp->src[count].max = wr_mas->pivots[end]; + + cp->src[count].start = start; + cp->src[count].end = end; + cp->s_count++; +} + +static inline void init_cp_src(struct maple_copy *cp) +{ + cp->src[cp->s_count].node = ma_mnode_ptr(cp); + cp->src[cp->s_count].mt = maple_copy; + cp->src[cp->s_count].max = cp->max; + cp->src[cp->s_count].start = 0; + cp->src[cp->s_count].end = cp->end; + cp->s_count++; +} + +static inline +void cp_data_write(struct maple_copy *cp, struct maple_big_node *b_node) +{ + struct maple_node *src; + unsigned char s; + unsigned char src_end, s_offset; + unsigned long *b_pivots, *cp_pivots; + void __rcu **b_slots, **cp_slots; + enum maple_type s_mt; + + b_node->b_end = 0; + + s = 0; + b_pivots = b_node->pivot; + b_slots = (void __rcu **)b_node->slot; + do { + unsigned char size; + + src = cp->src[s].node; + s_mt = cp->src[s].mt; + s_offset = cp->src[s].start; + src_end = cp->src[s].end; + size = src_end - s_offset + 1; + cp_pivots = ma_pivots(src, s_mt) + s_offset; + cp_slots = ma_slots(src, s_mt) + s_offset; + memcpy(b_slots, cp_slots, size * sizeof(void __rcu *)); + if (size > 1) + memcpy(b_pivots, cp_pivots, (size - 1) * sizeof(unsigned long)); + b_pivots[size - 1] = cp->src[s].max; + b_pivots += size; + b_slots += size; + b_node->b_end += size; + } while (++s < cp->s_count); +} + static void mas_spanning_rebalance_loop(struct ma_state *mas, struct maple_subtree_state *mast, unsigned char count) { @@ -2750,10 +2860,11 @@ static void mas_spanning_rebalance(struct ma_state *mas, static noinline void mas_wr_spanning_rebalance(struct ma_state *mas, - struct ma_wr_state *wr_mas, struct ma_wr_state *r_wr_mas) + struct ma_wr_state *l_wr_mas, struct ma_wr_state *r_wr_mas) { struct maple_subtree_state mast; struct maple_big_node b_node; + struct maple_copy cp; unsigned char height; MA_STATE(l_mas, mas->tree, mas->index, mas->index); MA_STATE(r_mas, mas->tree, mas->index, mas->last); @@ -2765,15 +2876,26 @@ static noinline void mas_wr_spanning_rebalance(struct ma_state *mas, mast.orig_l = &mast_l_mas; mast.orig_r = r_wr_mas->mas; memset(&b_node, 0, sizeof(struct maple_big_node)); - /* Copy l_mas and store the value in b_node. */ - mas_store_b_node(wr_mas, &b_node, mast.orig_l->end); - /* Copy r_mas into b_node if there is anything to copy. */ - if (mast.orig_r->max > mast.orig_r->last) - mas_mab_cp(mast.orig_r, mast.orig_r->offset, - mast.orig_r->end, &b_node, b_node.b_end + 1); - else - b_node.b_end++; + cp.s_count = 0; + cp_leaf_init(&cp, mas, l_wr_mas, r_wr_mas); + /* Copy left 0 - offset */ + if (l_wr_mas->mas->offset) { + unsigned char off = l_wr_mas->mas->offset - 1; + + append_wr_mas_cp(&cp, l_wr_mas, 0, off); + cp.src[cp.s_count - 1].max = cp.min - 1; + } + + init_cp_src(&cp); + + /* Copy right from offset_end + 1 to end */ + if (r_wr_mas->mas->end != r_wr_mas->offset_end) + append_wr_mas_cp(&cp, r_wr_mas, r_wr_mas->offset_end + 1, + r_wr_mas->mas->end); + + b_node.type = l_wr_mas->type; + cp_data_write(&cp, &b_node); /* Stop spanning searches by searching for just index. */ mast.orig_l->last = mas->index; -- cgit From f141d5664388db2ec155f61c9ce36b9b4dc307bc Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Fri, 30 Jan 2026 15:59:18 -0500 Subject: maple_tree: inline mas_spanning_rebalance_loop() into mas_wr_spanning_rebalance() Just copy the code and replace count with height. This is done to avoid affecting other code paths into mas_spanning_rebalance_loop() for the next change. No functional change intended. Link: https://lkml.kernel.org/r/20260130205935.2559335-14-Liam.Howlett@oracle.com Signed-off-by: Liam R. Howlett Cc: Alice Ryhl Cc: Andrew Ballance Cc: Arnd Bergmann Cc: Christian Kujau Cc: Geert Uytterhoeven Cc: Kuninori Morimoto Cc: Matthew Wilcox (Oracle) Cc: SeongJae Park Cc: Sidhartha Kumar Cc: Suren Baghdasaryan Cc: Vlastimil Babka Signed-off-by: Andrew Morton --- lib/maple_tree.c | 108 ++++++++++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 107 insertions(+), 1 deletion(-) (limited to 'lib') diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 554fdffd6c5b..a9b7e398c7db 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -2862,6 +2862,13 @@ static void mas_spanning_rebalance(struct ma_state *mas, static noinline void mas_wr_spanning_rebalance(struct ma_state *mas, struct ma_wr_state *l_wr_mas, struct ma_wr_state *r_wr_mas) { + + 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; + struct maple_subtree_state mast; struct maple_big_node b_node; struct maple_copy cp; @@ -2917,7 +2924,106 @@ static noinline void mas_wr_spanning_rebalance(struct ma_state *mas, mast_spanning_rebalance(&mast); height = mas_mt_height(mas) + 1; - mas_spanning_rebalance_loop(mas, &mast, height); + + /* + * 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 + * rippling up the tree to limit the amount of churn. Once a new sub-section of + * the tree is created, there may be a mix of new and old nodes. The old nodes + * will have the incorrect parent pointers and currently be in two trees: the + * original tree and the partially new tree. To remedy the parent pointers in + * the old tree, the new data is swapped into the active tree and a walk down + * the tree is performed and the parent pointers are updated. + * See mas_topiary_replace() for more information. + */ + while (height--) { + mast.bn->b_end--; + mast.bn->type = mte_node_type(mast.orig_l->node); + split = mas_mab_to_node(mas, mast.bn, &left, &right, &middle, + &mid_split); + mast_set_split_parents(&mast, left, middle, right, split, + mid_split); + mast_cp_to_nodes(&mast, left, middle, right, split, mid_split); + new_height++; + + /* + * Copy data from next level in the tree to mast.bn from next + * iteration + */ + memset(mast.bn, 0, sizeof(struct maple_big_node)); + mast.bn->type = mte_node_type(left); + + /* Root already stored in l->node. */ + if (mas_is_root_limits(mast.l)) + goto new_root; + + mast_ascend(&mast); + mast_combine_cp_left(&mast); + 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); + mast.orig_l->last = mast.orig_l->max; + + if (mast_sufficient(&mast)) { + if (mast_overflow(&mast)) + continue; + + if (mast.orig_l->node == mast.orig_r->node) { + /* + * The data in b_node should be stored in one + * node and in the tree + */ + slot = mast.l->offset; + break; + } + + continue; + } + + /* May be a new root stored in mast.bn */ + if (mas_is_root_limits(mast.orig_l)) + break; + + mast_spanning_rebalance(&mast); + + /* rebalancing from other nodes may require another loop. */ + if (!height) + height++; + } + + 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, mast.l, true); + new_height++; + mas_set_parent(mas, left, mast.l->node, slot); + if (middle) + mas_set_parent(mas, middle, mast.l->node, ++slot); + + if (right) + mas_set_parent(mas, right, mast.l->node, ++slot); + + if (mas_is_root_limits(mast.l)) { +new_root: + mas_mn(mast.l)->parent = ma_parent_ptr(mas_tree_parent(mas)); + while (!mte_is_root(mast.orig_l->node)) + mast_ascend(&mast); + } else { + mas_mn(mast.l)->parent = mas_mn(mast.orig_l)->parent; + } + + old_enode = mast.orig_l->node; + 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); } /* * mas_rebalance() - Rebalance a given node. -- cgit From 6953038cab845f3720ec8d83915f4f083861e195 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Fri, 30 Jan 2026 15:59:19 -0500 Subject: maple_tree: change initial big node setup in mas_wr_spanning_rebalance() Instead of copying the data into the big node and finding out that the data may need to be moved or appended to, calculate the data space up front (in the maple copy node) and set up another source for the copy. The additional copy source is tracked in the maple state sib (short for sibling), and is put into the maple write states for future operations after the data is in the big node. To facilitate the newly moved node, some initial setup of the maple subtree state are relocated after the potential shift caused by the new way of rebalancing against a sibling. Link: https://lkml.kernel.org/r/20260130205935.2559335-15-Liam.Howlett@oracle.com Signed-off-by: Liam R. Howlett Cc: Alice Ryhl Cc: Andrew Ballance Cc: Arnd Bergmann Cc: Christian Kujau Cc: Geert Uytterhoeven Cc: Kuninori Morimoto Cc: Matthew Wilcox (Oracle) Cc: SeongJae Park Cc: Sidhartha Kumar Cc: Suren Baghdasaryan Cc: Vlastimil Babka Signed-off-by: Andrew Morton --- include/linux/maple_tree.h | 1 + lib/maple_tree.c | 175 +++++++++++++++++++++++++++++++++++++++------ 2 files changed, 153 insertions(+), 23 deletions(-) (limited to 'lib') diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h index 9bc7fa89bc2e..e99e16ac1c6d 100644 --- a/include/linux/maple_tree.h +++ b/include/linux/maple_tree.h @@ -177,6 +177,7 @@ struct maple_copy { /*Avoid passing these around */ unsigned char s_count; + unsigned char data; }; /** diff --git a/lib/maple_tree.c b/lib/maple_tree.c index a9b7e398c7db..0d6f810a4a1f 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -1304,6 +1304,18 @@ static inline unsigned char mas_data_end(struct ma_state *mas) return mt_pivots[type]; } +static inline +void wr_mas_setup(struct ma_wr_state *wr_mas, struct ma_state *mas) +{ + wr_mas->node = mas_mn(mas); + wr_mas->type = mte_node_type(mas->node); + wr_mas->pivots = ma_pivots(wr_mas->node, wr_mas->type); + wr_mas->slots = ma_slots(wr_mas->node, wr_mas->type); + wr_mas->r_min = mas_safe_min(mas, wr_mas->pivots, mas->offset); + wr_mas->r_max = mas_safe_pivot(mas, wr_mas->pivots, mas->offset, + wr_mas->type); +} + /* * mas_leaf_max_gap() - Returns the largest gap in a leaf node * @mas: the maple state @@ -2258,6 +2270,44 @@ static inline void mte_mid_split_check(struct maple_enode **l, *split = mid_split; } +static inline +void spanning_sib(struct ma_wr_state *l_wr_mas, + struct ma_wr_state *r_wr_mas, struct ma_state *nneighbour) +{ + struct ma_state l_tmp = *l_wr_mas->mas; + struct ma_state r_tmp = *r_wr_mas->mas; + unsigned char depth = 0; + + do { + mas_ascend(&r_tmp); + mas_ascend(&l_tmp); + depth++; + if (r_tmp.offset < mas_data_end(&r_tmp)) { + r_tmp.offset++; + mas_descend(&r_tmp); + r_tmp.offset = 0; + while (--depth) + mas_descend(&r_tmp); + + r_tmp.end = mas_data_end(&r_tmp); + *nneighbour = r_tmp; + return; + } else if (l_tmp.offset) { + l_tmp.offset--; + do { + mas_descend(&l_tmp); + l_tmp.offset = mas_data_end(&l_tmp); + } while (--depth); + + l_tmp.end = l_tmp.offset; + *nneighbour = l_tmp; + return; + } + } while (!mte_is_root(r_tmp.node)); + + WARN_ON_ONCE(1); +} + /* * mast_set_split_parents() - Helper function to set three nodes parents. Slot * is taken from @mast->l. @@ -2642,6 +2692,49 @@ static inline void cp_leaf_init(struct maple_copy *cp, cp->end = end; } +/* + * cp_data_calc() - Calculate the size of the data (1 indexed). + * @cp: The maple copy struct with the new data populated. + * @l_wr_mas: The maple write state containing the data to the left of the write + * @r_wr_mas: The maple write state containing the data to the right of the + * write + * + * cp->data is a size (not indexed by 0). + */ +static inline void cp_data_calc(struct maple_copy *cp, + struct ma_wr_state *l_wr_mas, struct ma_wr_state *r_wr_mas) +{ + + /* Add 1 every time for the 0th element */ + cp->data = l_wr_mas->mas->offset; + /* Add the new data and any partial overwrites */ + cp->data += cp->end + 1; + /* Data from right (offset + 1 to end), +1 for zero */ + cp->data += r_wr_mas->mas->end - r_wr_mas->offset_end; +} + +static inline void append_mas_cp(struct maple_copy *cp, + struct ma_state *mas, unsigned char start, unsigned char end) +{ + struct maple_node *node; + enum maple_type mt; + unsigned char count; + + count = cp->s_count; + node = mas_mn(mas); + mt = mte_node_type(mas->node); + cp->src[count].node = node; + cp->src[count].mt = mt; + if (mas->end <= end) + cp->src[count].max = mas->max; + else + cp->src[count].max = ma_pivots(node, mt)[end]; + + cp->src[count].start = start; + cp->src[count].end = end; + cp->s_count++; +} + static inline void append_wr_mas_cp(struct maple_copy *cp, struct ma_wr_state *wr_mas, unsigned char start, unsigned char end) { @@ -2670,6 +2763,42 @@ static inline void init_cp_src(struct maple_copy *cp) cp->s_count++; } +/* + * multi_src_setup() - Set the @cp node up with multiple sources to copy from. + * @cp: The maple copy node + * @l_wr_mas: The left write maple state + * @r_wr_mas: The right write maple state + * @sib: The sibling maple state + * + * Note: @sib->end == 0 indicates no sibling will be used. + */ +static inline +void multi_src_setup(struct maple_copy *cp, struct ma_wr_state *l_wr_mas, + struct ma_wr_state *r_wr_mas, struct ma_state *sib) +{ + cp->s_count = 0; + if (sib->end && sib->max < l_wr_mas->mas->min) + append_mas_cp(cp, sib, 0, sib->end); + + /* Copy left 0 - offset */ + if (l_wr_mas->mas->offset) { + unsigned char off = l_wr_mas->mas->offset - 1; + + append_wr_mas_cp(cp, l_wr_mas, 0, off); + cp->src[cp->s_count - 1].max = cp->min - 1; + } + + init_cp_src(cp); + + /* Copy right either from offset or offset + 1 pending on r_max */ + if (r_wr_mas->mas->end != r_wr_mas->offset_end) + append_wr_mas_cp(cp, r_wr_mas, r_wr_mas->offset_end + 1, + r_wr_mas->mas->end); + + if (sib->end && sib->min > r_wr_mas->mas->max) + append_mas_cp(cp, sib, 0, sib->end); +} + static inline void cp_data_write(struct maple_copy *cp, struct maple_big_node *b_node) { @@ -2873,36 +3002,42 @@ static noinline void mas_wr_spanning_rebalance(struct ma_state *mas, struct maple_big_node b_node; struct maple_copy cp; unsigned char height; + struct ma_state sib; 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); MA_STATE(mast_l_mas, NULL, 0, 0); - mast_l_mas = *mas; - mast.orig_l = &mast_l_mas; - mast.orig_r = r_wr_mas->mas; memset(&b_node, 0, sizeof(struct maple_big_node)); + mast_l_mas = *mas; cp.s_count = 0; cp_leaf_init(&cp, mas, l_wr_mas, r_wr_mas); - /* Copy left 0 - offset */ - if (l_wr_mas->mas->offset) { - unsigned char off = l_wr_mas->mas->offset - 1; - - append_wr_mas_cp(&cp, l_wr_mas, 0, off); - cp.src[cp.s_count - 1].max = cp.min - 1; + cp_data_calc(&cp, l_wr_mas, r_wr_mas); + if (((l_wr_mas->mas->min != 0) || (r_wr_mas->mas->max != ULONG_MAX)) && + (cp.data <= mt_min_slots[l_wr_mas->type])) { + spanning_sib(l_wr_mas, r_wr_mas, &sib); + cp.data += sib.end + 1; + } else { + sib.end = 0; } - init_cp_src(&cp); - - /* Copy right from offset_end + 1 to end */ - if (r_wr_mas->mas->end != r_wr_mas->offset_end) - append_wr_mas_cp(&cp, r_wr_mas, r_wr_mas->offset_end + 1, - r_wr_mas->mas->end); - - + multi_src_setup(&cp, l_wr_mas, r_wr_mas, &sib); b_node.type = l_wr_mas->type; cp_data_write(&cp, &b_node); + if (sib.end) { + if (sib.max < l_wr_mas->mas->min) { + *l_wr_mas->mas = sib; + wr_mas_setup(l_wr_mas, &sib); + mast_l_mas = sib; + } else { + *r_wr_mas->mas = sib; + wr_mas_setup(r_wr_mas, &sib); + } + } + + mast.orig_l = &mast_l_mas; + mast.orig_r = r_wr_mas->mas; /* Stop spanning searches by searching for just index. */ mast.orig_l->last = mas->index; @@ -2917,12 +3052,6 @@ static noinline void mas_wr_spanning_rebalance(struct ma_state *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); - height = mas_mt_height(mas) + 1; /* -- cgit From de7f3ed37c1a433b7e1d5514e9a86a6c354e83d7 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Fri, 30 Jan 2026 15:59:20 -0500 Subject: maple_tree: introduce ma_leaf_max_gap() This is the same as mas_leaf_max_gap(), but the information necessary is known without a maple state in future code. Adding this function now simplifies the review for a subsequent patch. Link: https://lkml.kernel.org/r/20260130205935.2559335-16-Liam.Howlett@oracle.com Signed-off-by: Liam R. Howlett Cc: Alice Ryhl Cc: Andrew Ballance Cc: Arnd Bergmann Cc: Christian Kujau Cc: Geert Uytterhoeven Cc: Kuninori Morimoto Cc: Matthew Wilcox (Oracle) Cc: SeongJae Park Cc: Sidhartha Kumar Cc: Suren Baghdasaryan Cc: Vlastimil Babka Signed-off-by: Andrew Morton --- lib/maple_tree.c | 48 ++++++++++++++++++++++++++++-------------------- 1 file changed, 28 insertions(+), 20 deletions(-) (limited to 'lib') diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 0d6f810a4a1f..499cae720251 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -1315,26 +1315,14 @@ void wr_mas_setup(struct ma_wr_state *wr_mas, struct ma_state *mas) wr_mas->r_max = mas_safe_pivot(mas, wr_mas->pivots, mas->offset, wr_mas->type); } - -/* - * mas_leaf_max_gap() - Returns the largest gap in a leaf node - * @mas: the maple state - * - * Return: The maximum gap in the leaf. - */ -static unsigned long mas_leaf_max_gap(struct ma_state *mas) +static inline unsigned long ma_leaf_max_gap(struct maple_node *mn, + enum maple_type mt, unsigned long min, unsigned long max, + unsigned long *pivots, void __rcu **slots) { - enum maple_type mt; unsigned long pstart, gap, max_gap; - struct maple_node *mn; - unsigned long *pivots; - void __rcu **slots; unsigned char i; unsigned char max_piv; - mt = mte_node_type(mas->node); - mn = mas_mn(mas); - slots = ma_slots(mn, mt); max_gap = 0; if (unlikely(ma_is_dense(mt))) { gap = 0; @@ -1356,26 +1344,25 @@ static unsigned long mas_leaf_max_gap(struct ma_state *mas) * Check the first implied pivot optimizes the loop below and slot 1 may * be skipped if there is a gap in slot 0. */ - pivots = ma_pivots(mn, mt); if (likely(!slots[0])) { - max_gap = pivots[0] - mas->min + 1; + max_gap = pivots[0] - min + 1; i = 2; } else { i = 1; } /* reduce max_piv as the special case is checked before the loop */ - max_piv = ma_data_end(mn, mt, pivots, mas->max) - 1; + max_piv = ma_data_end(mn, mt, pivots, max) - 1; /* * Check end implied pivot which can only be a gap on the right most * node. */ - if (unlikely(mas->max == ULONG_MAX) && !slots[max_piv + 1]) { + if (unlikely(max == ULONG_MAX) && !slots[max_piv + 1]) { gap = ULONG_MAX - pivots[max_piv]; if (gap > max_gap) max_gap = gap; - if (max_gap > pivots[max_piv] - mas->min) + if (max_gap > pivots[max_piv] - min) return max_gap; } @@ -1395,6 +1382,27 @@ static unsigned long mas_leaf_max_gap(struct ma_state *mas) return max_gap; } +/* + * mas_leaf_max_gap() - Returns the largest gap in a leaf node + * @mas: the maple state + * + * Return: The maximum gap in the leaf. + */ +static inline unsigned long mas_leaf_max_gap(struct ma_state *mas) +{ + enum maple_type mt; + struct maple_node *mn; + unsigned long *pivots; + void __rcu **slots; + + mn = mas_mn(mas); + mt = mte_node_type(mas->node); + slots = ma_slots(mn, mt); + pivots = ma_pivots(mn, mt); + + return ma_leaf_max_gap(mn, mt, mas->min, mas->max, pivots, slots); +} + /* * ma_max_gap() - Get the maximum gap in a maple node (non-leaf) * @node: The maple node -- cgit From 20b20162e1f3b7e60cf0e79116fb2f3bdef3dc5e Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Fri, 30 Jan 2026 15:59:21 -0500 Subject: maple_tree: add gap support, slot and pivot sizes for maple copy Add plumbing work for using maple copy as a normal node for a source of copy operations. This is needed later. Link: https://lkml.kernel.org/r/20260130205935.2559335-17-Liam.Howlett@oracle.com Signed-off-by: Liam R. Howlett Cc: Alice Ryhl Cc: Andrew Ballance Cc: Arnd Bergmann Cc: Christian Kujau Cc: Geert Uytterhoeven Cc: Kuninori Morimoto Cc: Matthew Wilcox (Oracle) Cc: SeongJae Park Cc: Sidhartha Kumar Cc: Suren Baghdasaryan Cc: Vlastimil Babka Signed-off-by: Andrew Morton --- include/linux/maple_tree.h | 1 + lib/maple_tree.c | 5 +++++ 2 files changed, 6 insertions(+) (limited to 'lib') diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h index e99e16ac1c6d..db6a02788902 100644 --- a/include/linux/maple_tree.h +++ b/include/linux/maple_tree.h @@ -165,6 +165,7 @@ struct maple_copy { } src[4]; /* Simulated node */ void __rcu *slot[3]; + unsigned long gap[3]; unsigned long min; union { unsigned long pivot[3]; diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 499cae720251..9c701ee7412c 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -101,6 +101,7 @@ static const unsigned long mt_max[] = { [maple_leaf_64] = ULONG_MAX, [maple_range_64] = ULONG_MAX, [maple_arange_64] = ULONG_MAX, + [maple_copy] = ULONG_MAX, }; #define mt_node_max(x) mt_max[mte_node_type(x)] #endif @@ -110,6 +111,7 @@ static const unsigned char mt_slots[] = { [maple_leaf_64] = MAPLE_RANGE64_SLOTS, [maple_range_64] = MAPLE_RANGE64_SLOTS, [maple_arange_64] = MAPLE_ARANGE64_SLOTS, + [maple_copy] = 3, }; #define mt_slot_count(x) mt_slots[mte_node_type(x)] @@ -118,6 +120,7 @@ static const unsigned char mt_pivots[] = { [maple_leaf_64] = MAPLE_RANGE64_SLOTS - 1, [maple_range_64] = MAPLE_RANGE64_SLOTS - 1, [maple_arange_64] = MAPLE_ARANGE64_SLOTS - 1, + [maple_copy] = 3, }; #define mt_pivot_count(x) mt_pivots[mte_node_type(x)] @@ -126,6 +129,7 @@ static const unsigned char mt_min_slots[] = { [maple_leaf_64] = (MAPLE_RANGE64_SLOTS / 2) - 2, [maple_range_64] = (MAPLE_RANGE64_SLOTS / 2) - 2, [maple_arange_64] = (MAPLE_ARANGE64_SLOTS / 2) - 1, + [maple_copy] = 1, /* Should never be used */ }; #define mt_min_slot_count(x) mt_min_slots[mte_node_type(x)] @@ -627,6 +631,7 @@ static inline unsigned long *ma_gaps(struct maple_node *node, case maple_arange_64: return node->ma64.gap; case maple_copy: + return node->cp.gap; case maple_range_64: case maple_leaf_64: case maple_dense: -- cgit From a9c6716e088a1d4badd4fa6797469506bb99ec8b Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Fri, 30 Jan 2026 15:59:22 -0500 Subject: maple_tree: start using maple copy node for destination Stop using the maple subtree state and big node in favour of using three destinations in the maple copy node. That is, expand the way leaves were handled to all levels of the tree and use the maple copy node to track the new nodes. Extract out the sibling init into the data calculation since this is where the insufficient data can be detected. The remainder of the sibling code to shift the next iteration is moved to the spanning_ascend() function, since it is not always needed. Next introduce the dst_setup() function which will decide how many nodes are needed to contain the data at this level. Using the destination count, populate the copy node's dst array with the new nodes and set d_count to the correct value. Note that this can be tricky in the case of a leaf node with exactly enough room because of the rule against NULLs at the end of leaves. Once the destinations are ready, copy the data by altering the cp_data_write() function to copy from the sources to the destinations directly. This eliminates the use of the big node in this code path. On node completion, node_finalise() will zero out the remaining area and set the metadata, if necessary. spanning_ascend() is used to decide if the operation is complete. It may create a new root, converge into one destination, or continue upwards by ascending the left and right write maple states. One test case setup needed to be tweaked so that the targeted node was surrounded by full nodes. [akpm@linux-foundation.org: coding-style cleanups] Link: https://lkml.kernel.org/r/20260130205935.2559335-18-Liam.Howlett@oracle.com Signed-off-by: Liam R. Howlett Cc: Alice Ryhl Cc: Andrew Ballance Cc: Arnd Bergmann Cc: Christian Kujau Cc: Geert Uytterhoeven Cc: Kuninori Morimoto Cc: Matthew Wilcox (Oracle) Cc: SeongJae Park Cc: Sidhartha Kumar Cc: Suren Baghdasaryan Cc: Vlastimil Babka Signed-off-by: Andrew Morton --- include/linux/maple_tree.h | 14 + lib/maple_tree.c | 624 +++++++++++++++++++++++++++------------ tools/testing/radix-tree/maple.c | 2 +- 3 files changed, 458 insertions(+), 182 deletions(-) (limited to 'lib') diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h index db6a02788902..0c464eade1d6 100644 --- a/include/linux/maple_tree.h +++ b/include/linux/maple_tree.h @@ -156,6 +156,17 @@ enum store_type { }; struct maple_copy { + /* + * min, max, and pivots are values + * start, end, split are indexes into arrays + * data is a size + */ + + struct { + struct maple_node *node; + unsigned long max; + enum maple_type mt; + } dst[3]; struct { struct maple_node *node; unsigned long max; @@ -178,7 +189,10 @@ struct maple_copy { /*Avoid passing these around */ unsigned char s_count; + unsigned char d_count; + unsigned char split; unsigned char data; + unsigned char height; }; /** diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 9c701ee7412c..4d9e7f00f5c8 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -353,6 +353,13 @@ static inline struct maple_enode *mt_mk_node(const struct maple_node *node, (type << MAPLE_ENODE_TYPE_SHIFT) | MAPLE_ENODE_NULL); } +static inline void ma_init_slot(void __rcu **slot, const struct maple_node *mn, + const enum maple_type mt) +{ + /* WARNING: this is unsafe if the slot is exposed to readers. */ + RCU_INIT_POINTER(*slot, (void *)mt_mk_node(mn, mt)); +} + static inline void *mte_mk_root(const struct maple_enode *node) { return (void *)((unsigned long)node | MAPLE_ROOT_NODE); @@ -1320,6 +1327,21 @@ void wr_mas_setup(struct ma_wr_state *wr_mas, struct ma_state *mas) wr_mas->r_max = mas_safe_pivot(mas, wr_mas->pivots, mas->offset, wr_mas->type); } + +static inline +void wr_mas_ascend(struct ma_wr_state *wr_mas) +{ + struct ma_state *mas = wr_mas->mas; + + mas_ascend(mas); + wr_mas_setup(wr_mas, mas); + mas->end = ma_data_end(wr_mas->node, wr_mas->type, wr_mas->pivots, + mas->max); + /* Careful, this may be wrong.. */ + wr_mas->end_piv = wr_mas->r_max; + wr_mas->offset_end = mas->offset; +} + static inline unsigned long ma_leaf_max_gap(struct maple_node *mn, enum maple_type mt, unsigned long min, unsigned long max, unsigned long *pivots, void __rcu **slots) @@ -2507,6 +2529,112 @@ static inline void mas_wmb_replace(struct ma_state *mas, mas_update_gap(mas); } +/* + * node_copy() - Copy from one node to another. + * + * @mas: The maple state + * @src: The source node + * @start: The offset into the src to start copying + * @size: The size to copy (non-zero) + * @s_max: The source node max + * @s_mt: The source maple node type + * @dst: The destination + * @d_start: The start location in the destination node + * @d_mt: The destination maple node type + */ +static inline +unsigned long node_copy(struct ma_state *mas, struct maple_node *src, + unsigned char start, unsigned char size, unsigned long s_max, + enum maple_type s_mt, struct maple_node *dst, unsigned char d_start, + enum maple_type d_mt) +{ + unsigned long *s_pivots, *d_pivots; + void __rcu **s_slots, **d_slots; + unsigned long *s_gaps, *d_gaps; + unsigned long d_max; + + d_slots = ma_slots(dst, d_mt) + d_start; + d_pivots = ma_pivots(dst, d_mt) + d_start; + 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); + } + + d_gaps = ma_gaps(dst, d_mt); + if (d_gaps) { + s_gaps = ma_gaps(src, s_mt) + start; + d_gaps += d_start; + memcpy(d_gaps, s_gaps, size * sizeof(unsigned long)); + } + + if (start + size - 1 < mt_pivots[s_mt]) + d_max = s_pivots[size - 1]; + else + d_max = s_max; + + if (d_start + size <= mt_pivots[d_mt]) + d_pivots[size - 1] = d_max; + + size--; + if (size) + memcpy(d_pivots, s_pivots, size * sizeof(unsigned long)); + + return d_max; +} + +/* + * node_finalise() - Zero out unused area and populate metadata + * @node: The maple node + * @mt: The maple node type + * @end: The end of the used area + */ +static inline +void node_finalise(struct maple_node *node, enum maple_type mt, + unsigned char end) +{ + unsigned char max_end = mt_slots[mt]; + unsigned char size; + unsigned long *gaps; + unsigned char gap_slot; + + gaps = ma_gaps(node, mt); + if (end < max_end - 1) { + size = max_end - end; + memset(ma_slots(node, mt) + end, 0, size * sizeof(void *)); + + if (gaps) + memset(gaps + end, 0, size * sizeof(unsigned long)); + + if (--size) + memset(ma_pivots(node, mt) + end, 0, size * sizeof(unsigned long)); + } + + gap_slot = 0; + if (gaps && !ma_is_leaf(mt)) { + unsigned long max_gap; + + max_gap = 0; + for (int i = 0; i <= end; i++) + if (gaps[i] > max_gap) { + gap_slot = i; + max_gap = gaps[i]; + } + } + + if (mt == maple_arange_64) + ma_set_meta(node, mt, gap_slot, end - 1); + else if (end <= max_end - 1) + ma_set_meta(node, mt, gap_slot, end - 1); +} + /* * mast_cp_to_nodes() - Copy data out to nodes. * @mast: The maple subtree state @@ -2684,6 +2812,7 @@ static inline void cp_leaf_init(struct maple_copy *cp, * result in buggy code when a compiler reorders the instructions. */ + cp->height = 1; /* Create entries to insert including split entries to left and right */ if (l_wr_mas->r_min < mas->index) { end++; @@ -2726,6 +2855,100 @@ static inline void cp_data_calc(struct maple_copy *cp, cp->data += r_wr_mas->mas->end - r_wr_mas->offset_end; } +/* + * spanning_data() - Calculate the @cp data and populate @sib if insufficient + * @cp: The maple copy node + * @l_wr_mas: The left write maple state + * @r_wr_mas: The right write maple state + * @sib: The maple state of the sibling. + * + * Note: @cp->data is a size and not indexed by 0. @sib->end may be set to 0 to + * indicate it will not be used. + */ +static inline void spanning_data(struct maple_copy *cp, + struct ma_wr_state *l_wr_mas, struct ma_wr_state *r_wr_mas, + struct ma_state *sib) +{ + cp_data_calc(cp, l_wr_mas, r_wr_mas); + if (((l_wr_mas->mas->min != 0) || (r_wr_mas->mas->max != ULONG_MAX)) && + (cp->data <= mt_min_slots[l_wr_mas->type])) { + spanning_sib(l_wr_mas, r_wr_mas, sib); + cp->data += sib->end + 1; + } else { + sib->end = 0; + } +} + +/* + * dst_setup() - Set up one or more destinations for the new data. + * @cp: The maple copy node + * @mas: The maple state + * @mt: The source node type + */ +static inline +void dst_setup(struct maple_copy *cp, struct ma_state *mas, enum maple_type mt) +{ + /* Data is 1 indexed, every src has +1 added. */ + + if (cp->data <= mt_slots[mt]) { + cp->split = cp->data - 1; + cp->d_count = 1; + goto node_setup; + } + + cp->split = (cp->data - 1) / 2; + cp->d_count = 2; + if (cp->data < mt_slots[mt] * 2) + goto node_setup; + + if (cp->data == mt_slots[mt] * 2) { + unsigned char off; + unsigned char s; + + if (!ma_is_leaf(mt)) + goto node_setup; + + /* + * Leaf nodes are a bit tricky because we cannot assume the data + * can fit due to the NULL limitation on node ends. + */ + off = cp->split; + for (s = 0; s < cp->s_count; s++) { + unsigned char s_off; + + s_off = cp->src[s].end - cp->src[s].start; + if (s_off >= off) + break; + + s_off++; + off -= s_off; + } + + off += cp->src[s].start; + if (ma_slots(cp->src[s].node, cp->src[s].mt)[off]) + goto node_setup; + + cp->split++; + if (cp->split < mt_slots[mt]) + goto node_setup; + + cp->split -= 2; + if (cp->data - 2 - cp->split < mt_slots[mt]) + goto node_setup; + + } + + /* No other choice but to 3-way split the data */ + cp->split = (cp->data + 2) / 3; + cp->d_count = 3; + +node_setup: + for (int i = 0; i < cp->d_count; i++) { + cp->dst[i].mt = mt; + cp->dst[i].node = ma_mnode_ptr(mas_pop_node(mas)); + } +} + static inline void append_mas_cp(struct maple_copy *cp, struct ma_state *mas, unsigned char start, unsigned char end) { @@ -2813,38 +3036,153 @@ void multi_src_setup(struct maple_copy *cp, struct ma_wr_state *l_wr_mas, } static inline -void cp_data_write(struct maple_copy *cp, struct maple_big_node *b_node) +void cp_data_write(struct maple_copy *cp, struct ma_state *mas) { - struct maple_node *src; - unsigned char s; + struct maple_node *dst, *src; + unsigned char s, d; + unsigned char dst_offset; + unsigned char data_offset; unsigned char src_end, s_offset; - unsigned long *b_pivots, *cp_pivots; - void __rcu **b_slots, **cp_slots; - enum maple_type s_mt; + unsigned char split; + unsigned long s_max, d_max; + unsigned char dst_size; + enum maple_type s_mt, d_mt; + + data_offset = 0; + s = d = 0; + /* Readability help */ + src = cp->src[s].node; + dst = cp->dst[d].node; + s_offset = cp->src[s].start; + src_end = cp->src[s].end; + split = cp->split; + s_max = cp->src[s].max; + s_mt = cp->src[s].mt; + d_mt = cp->dst[d].mt; + do { + dst_offset = 0; + d_max = 0; + dst = cp->dst[d].node; + d_mt = cp->dst[d].mt; + dst_size = split + 1; - b_node->b_end = 0; + while (dst_size) { + unsigned char size; - s = 0; - b_pivots = b_node->pivot; - b_slots = (void __rcu **)b_node->slot; - do { - unsigned char size; - - src = cp->src[s].node; - s_mt = cp->src[s].mt; - s_offset = cp->src[s].start; - src_end = cp->src[s].end; - size = src_end - s_offset + 1; - cp_pivots = ma_pivots(src, s_mt) + s_offset; - cp_slots = ma_slots(src, s_mt) + s_offset; - memcpy(b_slots, cp_slots, size * sizeof(void __rcu *)); - if (size > 1) - memcpy(b_pivots, cp_pivots, (size - 1) * sizeof(unsigned long)); - b_pivots[size - 1] = cp->src[s].max; - b_pivots += size; - b_slots += size; - b_node->b_end += size; - } while (++s < cp->s_count); + if (src_end - s_offset + 1 < dst_size) + size = src_end - s_offset + 1; + else + size = dst_size; + + d_max = node_copy(mas, src, s_offset, size, s_max, s_mt, + dst, dst_offset, d_mt); + + dst_offset += size; + s_offset += size; + if (s_offset > src_end) { + /* This source is exhausted */ + s++; + if (s >= cp->s_count) { + cp->dst[d].max = d_max; + node_finalise(dst, d_mt, dst_offset); + return; + } + /* Reset local src */ + src = cp->src[s].node; + s_offset = cp->src[s].start; + src_end = cp->src[s].end; + s_max = cp->src[s].max; + s_mt = cp->src[s].mt; + } + + dst_size -= size; + data_offset += size; + } + + split = cp->split; + cp->dst[d].max = d_max; + /* Handle null entries */ + if (cp->dst[d].max != ULONG_MAX && + !ma_slots(dst, d_mt)[dst_offset - 1]) { + if (s_offset == cp->src[s].start) { + s--; + src = cp->src[s].node; + src_end = cp->src[s].end; + s_max = cp->src[s].max; + s_mt = cp->src[s].mt; + s_offset = src_end; + } else { + s_offset--; + } + /* Set dst max and clear pivot */ + split++; + data_offset--; + dst_offset--; + cp->dst[d].max = ma_pivots(dst, d_mt)[dst_offset - 1]; + } + + node_finalise(dst, d_mt, dst_offset); + ++d; /* Next destination */ + if (d == cp->d_count - 1) + split = cp->data - data_offset; + + if (d >= cp->d_count) { + WARN_ON(data_offset < cp->data); + return; + } + + } while (data_offset <= cp->data); +} + +/* + * cp_dst_to_slots() - Migrate the maple copy destination to the maple copy + * slots + * @cp: The maple copy node + * @min: The minimal value represented + * @max: The maximum value represented + * @mas: The maple state + */ +static inline void cp_dst_to_slots(struct maple_copy *cp, unsigned long min, + unsigned long max, struct ma_state *mas) +{ + unsigned char d; + unsigned long slot_min = min; + + for (d = 0; d < cp->d_count; d++) { + struct maple_node *mn = cp->dst[d].node; + enum maple_type mt = cp->dst[d].mt; + unsigned long slot_max = cp->dst[d].max; + + /* + * Warning, see cp_leaf_init() comment and rcu_assign_pointer() + * documentation. Since these are new nodes, there are no + * read-side operations that can view them until they are + * inserted into the tree after an rcu_assign_pointer() call. + */ + ma_init_slot(&cp->slot[d], mn, mt); + cp->pivot[d] = slot_max; + if (mt_is_alloc(mas->tree)) { + if (ma_is_leaf(mt)) { + cp->gap[d] = ma_leaf_max_gap(mn, mt, slot_min, + slot_max, ma_pivots(mn, mt), + ma_slots(mn, mt)); + } else { + unsigned long *gaps = ma_gaps(mn, mt); + + if (gaps) { + unsigned char gap_slot; + + gap_slot = ma_meta_gap(mn); + cp->gap[d] = gaps[gap_slot]; + } + } + } + slot_min = slot_max + 1; + } + + cp->end = cp->d_count - 1; + cp->min = min; + cp->max = max; } static void mas_spanning_rebalance_loop(struct ma_state *mas, @@ -3000,173 +3338,97 @@ static void mas_spanning_rebalance(struct ma_state *mas, mas_spanning_rebalance_loop(mas, mast, count); } - -static noinline void mas_wr_spanning_rebalance(struct ma_state *mas, - struct ma_wr_state *l_wr_mas, struct ma_wr_state *r_wr_mas) +/* + * spanning_ascend() - See if a spanning store operation has to keep walking up + * the tree + * @cp: The maple_copy node + * @l_wr_mas: The left maple write state + * @r_wr_mas: The right maple write state + * @sib: the maple state of the sibling + * + * Returns: True if another iteration is necessary. + */ +static bool spanning_ascend(struct maple_copy *cp, struct ma_state *mas, + struct ma_wr_state *l_wr_mas, struct ma_wr_state *r_wr_mas, + struct ma_state *sib) { - - 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; - - struct maple_subtree_state mast; - struct maple_big_node b_node; - struct maple_copy cp; - unsigned char height; - struct ma_state sib; - 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); - MA_STATE(mast_l_mas, NULL, 0, 0); - - - memset(&b_node, 0, sizeof(struct maple_big_node)); - mast_l_mas = *mas; - cp.s_count = 0; - cp_leaf_init(&cp, mas, l_wr_mas, r_wr_mas); - cp_data_calc(&cp, l_wr_mas, r_wr_mas); - if (((l_wr_mas->mas->min != 0) || (r_wr_mas->mas->max != ULONG_MAX)) && - (cp.data <= mt_min_slots[l_wr_mas->type])) { - spanning_sib(l_wr_mas, r_wr_mas, &sib); - cp.data += sib.end + 1; - } else { - sib.end = 0; - } - - multi_src_setup(&cp, l_wr_mas, r_wr_mas, &sib); - b_node.type = l_wr_mas->type; - cp_data_write(&cp, &b_node); - if (sib.end) { - if (sib.max < l_wr_mas->mas->min) { - *l_wr_mas->mas = sib; - wr_mas_setup(l_wr_mas, &sib); - mast_l_mas = sib; - } else { - *r_wr_mas->mas = sib; - wr_mas_setup(r_wr_mas, &sib); - } + if (sib->end) { + if (sib->max < l_wr_mas->mas->min) + *l_wr_mas->mas = *sib; + else + *r_wr_mas->mas = *sib; } - mast.orig_l = &mast_l_mas; - mast.orig_r = r_wr_mas->mas; - /* Stop spanning searches by searching for just index. */ - mast.orig_l->last = mas->index; + cp_dst_to_slots(cp, l_wr_mas->mas->min, r_wr_mas->mas->max, mas); + if (!cp->min && cp->max == ULONG_MAX) { + /* New root */ + if (cp->d_count != 1) { + enum maple_type mt = maple_arange_64; - mast.bn = &b_node; - /* Combine l_mas and r_mas and split them up evenly again. */ + if (!mt_is_alloc(mas->tree)) + mt = maple_range_64; - /* - * 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; - height = mas_mt_height(mas) + 1; - - /* - * 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 - * rippling up the tree to limit the amount of churn. Once a new sub-section of - * the tree is created, there may be a mix of new and old nodes. The old nodes - * will have the incorrect parent pointers and currently be in two trees: the - * original tree and the partially new tree. To remedy the parent pointers in - * the old tree, the new data is swapped into the active tree and a walk down - * the tree is performed and the parent pointers are updated. - * See mas_topiary_replace() for more information. - */ - while (height--) { - mast.bn->b_end--; - mast.bn->type = mte_node_type(mast.orig_l->node); - split = mas_mab_to_node(mas, mast.bn, &left, &right, &middle, - &mid_split); - mast_set_split_parents(&mast, left, middle, right, split, - mid_split); - mast_cp_to_nodes(&mast, left, middle, right, split, mid_split); - new_height++; - - /* - * Copy data from next level in the tree to mast.bn from next - * iteration - */ - memset(mast.bn, 0, sizeof(struct maple_big_node)); - mast.bn->type = mte_node_type(left); - - /* Root already stored in l->node. */ - if (mas_is_root_limits(mast.l)) - goto new_root; - - mast_ascend(&mast); - mast_combine_cp_left(&mast); - 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); - mast.orig_l->last = mast.orig_l->max; - - if (mast_sufficient(&mast)) { - if (mast_overflow(&mast)) - continue; - - if (mast.orig_l->node == mast.orig_r->node) { - /* - * The data in b_node should be stored in one - * node and in the tree - */ - slot = mast.l->offset; - break; - } - - continue; + cp->data = cp->d_count; + cp->s_count = 0; + dst_setup(cp, mas, mt); + init_cp_src(cp); + node_copy(mas, cp->src[0].node, 0, cp->data, cp->max, maple_copy, + cp->dst[0].node, 0, mt); + node_finalise(cp->dst[0].node, mt, cp->end + 1); + /* + * Warning, see cp_leaf_init() comment and rcu_assign_pointer() + * documentation. Since this is a new root, there are no + * read-side operations that can view it until it is insert into + * the tree after an rcu_assign_pointer() call. + */ + ma_init_slot(&cp->slot[0], cp->dst[0].node, mt); + cp->height++; } - - /* May be a new root stored in mast.bn */ - if (mas_is_root_limits(mast.orig_l)) - break; - - mast_spanning_rebalance(&mast); - - /* rebalancing from other nodes may require another loop. */ - if (!height) - height++; + WARN_ON_ONCE(cp->dst[0].node != mte_to_node( + mt_slot_locked(mas->tree, cp->slot, 0))); + cp->dst[0].node->parent = ma_parent_ptr(mas_tree_parent(mas)); + mas->min = 0; + mas->max = ULONG_MAX; + mas->depth = 0; + mas->node = mas_root_locked(mas); + return false; } - mast.l->node = mt_mk_node(ma_mnode_ptr(mas_pop_node(mas)), - mte_node_type(mast.orig_l->node)); + /* Converged and has a single destination */ + if ((cp->d_count == 1) && + (l_wr_mas->mas->node == r_wr_mas->mas->node)) { + cp->dst[0].node->parent = ma_parent_ptr(mas_mn(mas)->parent); + return false; + } - mab_mas_cp(mast.bn, 0, mt_slots[mast.bn->type] - 1, mast.l, true); - new_height++; - mas_set_parent(mas, left, mast.l->node, slot); - if (middle) - mas_set_parent(mas, middle, mast.l->node, ++slot); + cp->height++; + wr_mas_ascend(l_wr_mas); + wr_mas_ascend(r_wr_mas); + return true; +} - if (right) - mas_set_parent(mas, right, mast.l->node, ++slot); +static noinline void mas_wr_spanning_rebalance(struct ma_state *mas, + struct ma_wr_state *l_wr_mas, struct ma_wr_state *r_wr_mas) +{ - if (mas_is_root_limits(mast.l)) { -new_root: - mas_mn(mast.l)->parent = ma_parent_ptr(mas_tree_parent(mas)); - while (!mte_is_root(mast.orig_l->node)) - mast_ascend(&mast); - } else { - mas_mn(mast.l)->parent = mas_mn(mast.orig_l)->parent; - } + struct maple_enode *old_enode; + struct maple_copy cp; + struct ma_state sib; - old_enode = mast.orig_l->node; - 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); + cp_leaf_init(&cp, mas, l_wr_mas, r_wr_mas); + do { + spanning_data(&cp, l_wr_mas, r_wr_mas, &sib); + multi_src_setup(&cp, l_wr_mas, r_wr_mas, &sib); + dst_setup(&cp, mas, l_wr_mas->type); + cp_data_write(&cp, mas); + } while (spanning_ascend(&cp, mas, l_wr_mas, r_wr_mas, &sib)); + + old_enode = mas->node; + mas->node = mt_slot_locked(mas->tree, cp.slot, 0); + mas_wmb_replace(mas, old_enode, cp.height); mtree_range_walk(mas); } + /* * mas_rebalance() - Rebalance a given node. * @mas: The maple state diff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/maple.c index 85fb5616c133..dfd7099f0d8e 100644 --- a/tools/testing/radix-tree/maple.c +++ b/tools/testing/radix-tree/maple.c @@ -35508,7 +35508,7 @@ static noinline void __init check_spanning_write(struct maple_tree *mt) /* Store a value across a node boundary that causes a 3 way split */ if (MAPLE_32BIT) - i = 49590; /* 0xc1b6 */ + i = 49430; /* 0xc116 */ else i = 49670; /* 0xC206 */ -- cgit From 3578d61c1c4305ef4e24adda97266bc4d1ebc962 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Fri, 30 Jan 2026 15:59:23 -0500 Subject: maple_tree: inline mas_wr_spanning_rebalance() Now that the spanning rebalance is small, fully inline it in mas_wr_spanning_store(). No functional change. Link: https://lkml.kernel.org/r/20260130205935.2559335-19-Liam.Howlett@oracle.com Signed-off-by: Liam R. Howlett Cc: Alice Ryhl Cc: Andrew Ballance Cc: Arnd Bergmann Cc: Christian Kujau Cc: Geert Uytterhoeven Cc: Kuninori Morimoto Cc: Matthew Wilcox (Oracle) Cc: SeongJae Park Cc: Sidhartha Kumar Cc: Suren Baghdasaryan Cc: Vlastimil Babka Signed-off-by: Andrew Morton --- lib/maple_tree.c | 38 +++++++++++++++----------------------- 1 file changed, 15 insertions(+), 23 deletions(-) (limited to 'lib') diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 4d9e7f00f5c8..22e929826402 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -3407,28 +3407,6 @@ static bool spanning_ascend(struct maple_copy *cp, struct ma_state *mas, return true; } -static noinline void mas_wr_spanning_rebalance(struct ma_state *mas, - struct ma_wr_state *l_wr_mas, struct ma_wr_state *r_wr_mas) -{ - - struct maple_enode *old_enode; - struct maple_copy cp; - struct ma_state sib; - - cp_leaf_init(&cp, mas, l_wr_mas, r_wr_mas); - do { - spanning_data(&cp, l_wr_mas, r_wr_mas, &sib); - multi_src_setup(&cp, l_wr_mas, r_wr_mas, &sib); - dst_setup(&cp, mas, l_wr_mas->type); - cp_data_write(&cp, mas); - } while (spanning_ascend(&cp, mas, l_wr_mas, r_wr_mas, &sib)); - - old_enode = mas->node; - mas->node = mt_slot_locked(mas->tree, cp.slot, 0); - mas_wmb_replace(mas, old_enode, cp.height); - mtree_range_walk(mas); -} - /* * mas_rebalance() - Rebalance a given node. * @mas: The maple state @@ -4085,7 +4063,10 @@ done: */ static void mas_wr_spanning_store(struct ma_wr_state *wr_mas) { + struct maple_enode *old_enode; + struct maple_copy cp; struct ma_state *mas; + struct ma_state sib; /* Left and Right side of spanning store */ MA_STATE(r_mas, NULL, 0, 0); @@ -4142,7 +4123,18 @@ static void mas_wr_spanning_store(struct ma_wr_state *wr_mas) return mas_new_root(mas, wr_mas->entry); } - mas_wr_spanning_rebalance(mas, wr_mas, &r_wr_mas); + cp_leaf_init(&cp, mas, wr_mas, &r_wr_mas); + do { + spanning_data(&cp, wr_mas, &r_wr_mas, &sib); + multi_src_setup(&cp, wr_mas, &r_wr_mas, &sib); + dst_setup(&cp, mas, wr_mas->type); + cp_data_write(&cp, mas); + } while (spanning_ascend(&cp, mas, wr_mas, &r_wr_mas, &sib)); + + old_enode = mas->node; + mas->node = mt_slot_locked(mas->tree, cp.slot, 0); + mas_wmb_replace(mas, old_enode, cp.height); + mtree_range_walk(mas); } /* -- cgit From 448ec8c0a424b89b22acb641481088af1e43f5c2 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Fri, 30 Jan 2026 15:59:24 -0500 Subject: maple_tree: remove unnecessary return statements Functions do not need to state return at the end, unless skipping unwind. These can safely be dropped. Link: https://lkml.kernel.org/r/20260130205935.2559335-20-Liam.Howlett@oracle.com Signed-off-by: Liam R. Howlett Cc: Alice Ryhl Cc: Andrew Ballance Cc: Arnd Bergmann Cc: Christian Kujau Cc: Geert Uytterhoeven Cc: Kuninori Morimoto Cc: Matthew Wilcox (Oracle) Cc: SeongJae Park Cc: Sidhartha Kumar Cc: Suren Baghdasaryan Cc: Vlastimil Babka Signed-off-by: Andrew Morton --- lib/maple_tree.c | 11 ----------- 1 file changed, 11 deletions(-) (limited to 'lib') diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 22e929826402..87bbc5492305 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -3294,7 +3294,6 @@ new_root: mas->offset = mast->l->offset; mas_wmb_replace(mas, old_enode, new_height); mtree_range_walk(mas); - return; } /* @@ -3718,7 +3717,6 @@ static void mas_split(struct ma_state *mas, struct maple_big_node *b_node) mas->node = l_mas.node; mas_wmb_replace(mas, old, height); mtree_range_walk(mas); - return; } /* @@ -3779,7 +3777,6 @@ static inline void mas_root_expand(struct ma_state *mas, void *entry) ma_set_meta(node, maple_leaf_64, 0, slot); /* swap the new root into the tree */ rcu_assign_pointer(mas->tree->ma_root, mte_mk_root(mas->node)); - return; } /* @@ -4051,8 +4048,6 @@ static inline void mas_new_root(struct ma_state *mas, void *entry) done: if (xa_is_node(root)) mte_destroy_walk(root, mas->tree); - - return; } /* * mas_wr_spanning_store() - Create a subtree with the store operation completed @@ -4215,7 +4210,6 @@ done: trace_ma_write(TP_FCT, mas, 0, wr_mas->entry); mas_update_gap(mas); mas->end = new_end; - return; } /* @@ -4263,8 +4257,6 @@ static inline void mas_wr_slot_store(struct ma_wr_state *wr_mas) */ if (!wr_mas->entry || gap) mas_update_gap(mas); - - return; } static inline void mas_wr_extend_null(struct ma_wr_state *wr_mas) @@ -4378,7 +4370,6 @@ static inline void mas_wr_append(struct ma_wr_state *wr_mas, mas->end = new_end; trace_ma_write(TP_FCT, mas, new_end, wr_mas->entry); - return; } /* @@ -4437,8 +4428,6 @@ static inline void mas_wr_store_entry(struct ma_wr_state *wr_mas) case wr_invalid: MT_BUG_ON(mas->tree, 1); } - - return; } static inline void mas_wr_prealloc_setup(struct ma_wr_state *wr_mas) -- cgit From 62e9d349afce279944a22295515c18af335722c0 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Fri, 30 Jan 2026 15:59:25 -0500 Subject: maple_tree: separate wr_split_store and wr_rebalance store type code path The split and rebalance store types both go through the same function that uses the big node. Separate the code paths so that each can be updated independently. No functional change intended Link: https://lkml.kernel.org/r/20260130205935.2559335-21-Liam.Howlett@oracle.com Signed-off-by: Liam R. Howlett Cc: Alice Ryhl Cc: Andrew Ballance Cc: Arnd Bergmann Cc: Christian Kujau Cc: Geert Uytterhoeven Cc: Kuninori Morimoto Cc: Matthew Wilcox (Oracle) Cc: SeongJae Park Cc: Sidhartha Kumar Cc: Suren Baghdasaryan Cc: Vlastimil Babka Signed-off-by: Andrew Morton --- lib/maple_tree.c | 47 +++++++++++++++++++++++------------------------ 1 file changed, 23 insertions(+), 24 deletions(-) (limited to 'lib') diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 87bbc5492305..2383c97f684b 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -3719,24 +3719,6 @@ static void mas_split(struct ma_state *mas, struct maple_big_node *b_node) mtree_range_walk(mas); } -/* - * mas_commit_b_node() - Commit the big node into the tree. - * @wr_mas: The maple write state - * @b_node: The maple big node - */ -static noinline_for_kasan void mas_commit_b_node(struct ma_wr_state *wr_mas, - struct maple_big_node *b_node) -{ - enum store_type type = wr_mas->mas->store_type; - - WARN_ON_ONCE(type != wr_rebalance && type != wr_split_store); - - if (type == wr_rebalance) - return mas_rebalance(wr_mas->mas, b_node); - - return mas_split(wr_mas->mas, b_node); -} - /* * mas_root_expand() - Expand a root to a node * @mas: The maple state @@ -4373,19 +4355,34 @@ static inline void mas_wr_append(struct ma_wr_state *wr_mas, } /* - * mas_wr_bnode() - Slow path for a modification. + * mas_wr_split() - Expand one node into two * @wr_mas: The write maple state - * - * This is where split, rebalance end up. */ -static void mas_wr_bnode(struct ma_wr_state *wr_mas) +static noinline_for_kasan void mas_wr_split(struct ma_wr_state *wr_mas) { struct maple_big_node b_node; trace_ma_write(TP_FCT, wr_mas->mas, 0, wr_mas->entry); memset(&b_node, 0, sizeof(struct maple_big_node)); mas_store_b_node(wr_mas, &b_node, wr_mas->offset_end); - mas_commit_b_node(wr_mas, &b_node); + WARN_ON_ONCE(wr_mas->mas->store_type != wr_split_store); + return mas_split(wr_mas->mas, &b_node); +} + +/* + * mas_wr_rebalance() - Insufficient data in one node needs to either get data + * from a sibling or absorb a sibling all together. + * @wr_mas: The write maple state + */ +static noinline_for_kasan void mas_wr_rebalance(struct ma_wr_state *wr_mas) +{ + struct maple_big_node b_node; + + trace_ma_write(__func__, wr_mas->mas, 0, wr_mas->entry); + memset(&b_node, 0, sizeof(struct maple_big_node)); + mas_store_b_node(wr_mas, &b_node, wr_mas->offset_end); + WARN_ON_ONCE(wr_mas->mas->store_type != wr_rebalance); + return mas_rebalance(wr_mas->mas, &b_node); } /* @@ -4416,8 +4413,10 @@ static inline void mas_wr_store_entry(struct ma_wr_state *wr_mas) mas_wr_spanning_store(wr_mas); break; case wr_split_store: + mas_wr_split(wr_mas); + break; case wr_rebalance: - mas_wr_bnode(wr_mas); + mas_wr_rebalance(wr_mas); break; case wr_new_root: mas_new_root(mas, wr_mas->entry); -- cgit From b00a1804e69297489a88d4cbdffba6a6f21795e3 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Fri, 30 Jan 2026 15:59:26 -0500 Subject: maple_tree: add cp_is_new_root() helper Add a helper to do what is needed when the maple copy node contains a new root node. This is useful for future commits and is self-documenting code. [Liam.Howlett@oracle.com: remove warnings on older compilers] Link: https://lkml.kernel.org/r/malwmirqnpuxqkqrobcmzfkmmxipoyzwfs2nwc5fbpxlt2r2ej@wchmjtaljvw3 [akpm@linux-foundation.org: s/cp->slot[0]/&cp->slot[0]/, per Liam] Link: https://lkml.kernel.org/r/20260130205935.2559335-22-Liam.Howlett@oracle.com Signed-off-by: Liam R. Howlett Cc: Alice Ryhl Cc: Andrew Ballance Cc: Arnd Bergmann Cc: Christian Kujau Cc: Geert Uytterhoeven Cc: Kuninori Morimoto Cc: Matthew Wilcox (Oracle) Cc: SeongJae Park Cc: Sidhartha Kumar Cc: Suren Baghdasaryan Cc: Vlastimil Babka Signed-off-by: Andrew Morton --- lib/maple_tree.c | 70 ++++++++++++++++++++++++++++++-------------------------- 1 file changed, 38 insertions(+), 32 deletions(-) (limited to 'lib') diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 2383c97f684b..6a8f75dac6c9 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -3337,6 +3337,43 @@ static void mas_spanning_rebalance(struct ma_state *mas, mas_spanning_rebalance_loop(mas, mast, count); } +static inline bool cp_is_new_root(struct maple_copy *cp, struct ma_state *mas) +{ + if (cp->min || cp->max != ULONG_MAX) + return false; + + if (cp->d_count != 1) { + enum maple_type mt = maple_arange_64; + + if (!mt_is_alloc(mas->tree)) + mt = maple_range_64; + + cp->data = cp->d_count; + cp->s_count = 0; + dst_setup(cp, mas, mt); + init_cp_src(cp); + node_copy(mas, cp->src[0].node, 0, cp->data, cp->max, maple_copy, + cp->dst[0].node, 0, mt); + node_finalise(cp->dst[0].node, mt, cp->end + 1); + /* + * Warning, see cp_leaf_init() comment and rcu_assign_pointer() + * documentation. Since this is a new root, there are no + * read-side operations that can view it until it is insert into + * the tree after an rcu_assign_pointer() call. + */ + ma_init_slot(&cp->slot[0], cp->dst[0].node, mt); + cp->height++; + } + WARN_ON_ONCE(cp->dst[0].node != mte_to_node( + mt_slot_locked(mas->tree, cp->slot, 0))); + cp->dst[0].node->parent = ma_parent_ptr(mas_tree_parent(mas)); + mas->min = 0; + mas->max = ULONG_MAX; + mas->depth = 0; + mas->node = mas_root_locked(mas); + return true; +} + /* * spanning_ascend() - See if a spanning store operation has to keep walking up * the tree @@ -3359,39 +3396,8 @@ static bool spanning_ascend(struct maple_copy *cp, struct ma_state *mas, } cp_dst_to_slots(cp, l_wr_mas->mas->min, r_wr_mas->mas->max, mas); - if (!cp->min && cp->max == ULONG_MAX) { - /* New root */ - if (cp->d_count != 1) { - enum maple_type mt = maple_arange_64; - - if (!mt_is_alloc(mas->tree)) - mt = maple_range_64; - - cp->data = cp->d_count; - cp->s_count = 0; - dst_setup(cp, mas, mt); - init_cp_src(cp); - node_copy(mas, cp->src[0].node, 0, cp->data, cp->max, maple_copy, - cp->dst[0].node, 0, mt); - node_finalise(cp->dst[0].node, mt, cp->end + 1); - /* - * Warning, see cp_leaf_init() comment and rcu_assign_pointer() - * documentation. Since this is a new root, there are no - * read-side operations that can view it until it is insert into - * the tree after an rcu_assign_pointer() call. - */ - ma_init_slot(&cp->slot[0], cp->dst[0].node, mt); - cp->height++; - } - WARN_ON_ONCE(cp->dst[0].node != mte_to_node( - mt_slot_locked(mas->tree, cp->slot, 0))); - cp->dst[0].node->parent = ma_parent_ptr(mas_tree_parent(mas)); - mas->min = 0; - mas->max = ULONG_MAX; - mas->depth = 0; - mas->node = mas_root_locked(mas); + if (cp_is_new_root(cp, mas)) return false; - } /* Converged and has a single destination */ if ((cp->d_count == 1) && -- cgit From 971f0db15977582a811712bba042191721715c19 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Fri, 30 Jan 2026 15:59:27 -0500 Subject: maple_tree: use maple copy node for mas_wr_rebalance() operation Stop using the maple big node for rebalance operations by changing to more align with spanning store. The rebalance operation needs its own data calculation in rebalance_data(). In the event of too much data, the rebalance tries to push the data using push_data_sib(). If there is insufficient data, the rebalance operation will rebalance against a sibling (found with rebalance_sib()). The rebalance starts at the leaf and works its way upward in the tree using rebalance_ascend(). Most of the code is shared with spanning store such as the copy node having a new root, but is fundamentally different in that the data must come from a sibling. A parent maple state is used to track the parent location to avoid multiple mas_ascend() calls. The maple state tree location is copied from the parent to the mas (child) in the ascend step. Ascending itself is done in the main loop. Link: https://lkml.kernel.org/r/20260130205935.2559335-23-Liam.Howlett@oracle.com Signed-off-by: Liam R. Howlett Cc: Alice Ryhl Cc: Andrew Ballance Cc: Arnd Bergmann Cc: Christian Kujau Cc: Geert Uytterhoeven Cc: Kuninori Morimoto Cc: Matthew Wilcox (Oracle) Cc: SeongJae Park Cc: Sidhartha Kumar Cc: Suren Baghdasaryan Cc: Vlastimil Babka Signed-off-by: Andrew Morton --- lib/maple_tree.c | 213 +++++++++++++++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 206 insertions(+), 7 deletions(-) (limited to 'lib') diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 6a8f75dac6c9..7ce7c0a33943 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -2305,6 +2305,19 @@ static inline void mte_mid_split_check(struct maple_enode **l, *split = mid_split; } +static inline void rebalance_sib(struct ma_state *parent, struct ma_state *sib) +{ + *sib = *parent; + /* Prioritize move right to pull data left */ + if (sib->offset < sib->end) + sib->offset++; + else + sib->offset--; + + mas_descend(sib); + sib->end = mas_data_end(sib); +} + static inline void spanning_sib(struct ma_wr_state *l_wr_mas, struct ma_wr_state *r_wr_mas, struct ma_state *nneighbour) @@ -2855,6 +2868,112 @@ static inline void cp_data_calc(struct maple_copy *cp, cp->data += r_wr_mas->mas->end - r_wr_mas->offset_end; } +static bool data_fits(struct ma_state *sib, struct ma_state *mas, + struct maple_copy *cp) +{ + unsigned char new_data; + enum maple_type type; + unsigned char space; + unsigned char end; + + type = mte_node_type(mas->node); + space = 2 * mt_slots[type]; + end = sib->end; + + new_data = end + 1 + cp->data; + if (new_data > space) + return false; + + /* + * This is off by one by design. The extra space is left to reduce + * jitter in operations that add then remove two entries. + * + * end is an index while new space and data are both sizes. Adding one + * to end to convert the index to a size means that the below + * calculation should be <=, but we want to keep an extra space in nodes + * to reduce jitter. + * + * Note that it is still possible to get a full node on the left by the + * NULL landing exactly on the split. The NULL ending of a node happens + * in the dst_setup() function, where we will either increase the split + * by one or decrease it by one, if possible. In the case of split + * (this case), it is always possible to shift the spilt by one - again + * because there is at least one slot free by the below checking. + */ + if (new_data < space) + return true; + + return false; +} + +static inline void push_data_sib(struct maple_copy *cp, struct ma_state *mas, + struct ma_state *sib, struct ma_state *parent) +{ + + if (mte_is_root(mas->node)) + goto no_push; + + + *sib = *parent; + if (sib->offset) { + sib->offset--; + mas_descend(sib); + sib->end = mas_data_end(sib); + if (data_fits(sib, mas, cp)) /* Push left */ + return; + + *sib = *parent; + } + + if (sib->offset >= sib->end) + goto no_push; + + sib->offset++; + mas_descend(sib); + sib->end = mas_data_end(sib); + if (data_fits(sib, mas, cp)) /* Push right*/ + return; + +no_push: + sib->end = 0; +} + +/* + * rebalance_data() - Calculate the @cp data, populate @sib if insufficient or + * if the data can be pushed into a sibling. + * @cp: The maple copy node + * @wr_mas: The left write maple state + * @sib: The maple state of the sibling. + * + * Note: @cp->data is a size and not indexed by 0. @sib->end may be set to 0 to + * indicate it will not be used. + * + */ +static inline void rebalance_data(struct maple_copy *cp, + struct ma_wr_state *wr_mas, struct ma_state *sib, + struct ma_state *parent) +{ + cp_data_calc(cp, wr_mas, wr_mas); + sib->end = 0; + if (cp->data > mt_slots[wr_mas->type]) { + push_data_sib(cp, wr_mas->mas, sib, parent); + if (sib->end) + goto use_sib; + } else if (cp->data <= mt_min_slots[wr_mas->type]) { + if ((wr_mas->mas->min != 0) || + (wr_mas->mas->max != ULONG_MAX)) { + rebalance_sib(parent, sib); + goto use_sib; + } + } + + return; + +use_sib: + + cp->data += sib->end + 1; +} + /* * spanning_data() - Calculate the @cp data and populate @sib if insufficient * @cp: The maple copy node @@ -3412,6 +3531,55 @@ static bool spanning_ascend(struct maple_copy *cp, struct ma_state *mas, return true; } +/* + * rebalance_ascend() - Ascend the tree and set up for the next loop - if + * necessary + * + * Return: True if there another rebalancing operation on the next level is + * needed, false otherwise. + */ +static inline bool rebalance_ascend(struct maple_copy *cp, + struct ma_wr_state *wr_mas, struct ma_state *sib, + struct ma_state *parent) +{ + struct ma_state *mas; + unsigned long min, max; + + mas = wr_mas->mas; + if (!sib->end) { + min = mas->min; + max = mas->max; + } else if (sib->min > mas->max) { /* Move right succeeded */ + min = mas->min; + max = sib->max; + wr_mas->offset_end = parent->offset + 1; + } else { + min = sib->min; + max = mas->max; + wr_mas->offset_end = parent->offset; + parent->offset--; + } + + cp_dst_to_slots(cp, min, max, mas); + if (cp_is_new_root(cp, mas)) + return false; + + if (cp->d_count == 1 && !sib->end) { + cp->dst[0].node->parent = ma_parent_ptr(mas_mn(mas)->parent); + return false; + } + + cp->height++; + mas->node = parent->node; + mas->offset = parent->offset; + mas->min = parent->min; + mas->max = parent->max; + mas->end = parent->end; + mas->depth = parent->depth; + wr_mas_setup(wr_mas, mas); + return true; +} + /* * mas_rebalance() - Rebalance a given node. * @mas: The maple state @@ -4379,16 +4547,47 @@ static noinline_for_kasan void mas_wr_split(struct ma_wr_state *wr_mas) * mas_wr_rebalance() - Insufficient data in one node needs to either get data * from a sibling or absorb a sibling all together. * @wr_mas: The write maple state + * + * Rebalance is different than a spanning store in that the write state is + * already at the leaf node that's being altered. */ -static noinline_for_kasan void mas_wr_rebalance(struct ma_wr_state *wr_mas) +static void mas_wr_rebalance(struct ma_wr_state *wr_mas) { - struct maple_big_node b_node; + struct maple_enode *old_enode; + struct ma_state parent; + struct ma_state *mas; + struct maple_copy cp; + struct ma_state sib; - trace_ma_write(__func__, wr_mas->mas, 0, wr_mas->entry); - memset(&b_node, 0, sizeof(struct maple_big_node)); - mas_store_b_node(wr_mas, &b_node, wr_mas->offset_end); - WARN_ON_ONCE(wr_mas->mas->store_type != wr_rebalance); - return mas_rebalance(wr_mas->mas, &b_node); + /* + * Rebalancing occurs if a node is insufficient. Data is rebalanced + * against the node to the right if it exists, otherwise the node to the + * left of this node is rebalanced against this node. If rebalancing + * causes just one node to be produced instead of two, then the parent + * is also examined and rebalanced if it is insufficient. Every level + * tries to combine the data in the same way. If one node contains the + * entire range of the tree, then that node is used as a new root node. + */ + + mas = wr_mas->mas; + trace_ma_op(TP_FCT, mas); + parent = *mas; + cp_leaf_init(&cp, mas, wr_mas, wr_mas); + do { + if (!mte_is_root(parent.node)) { + mas_ascend(&parent); + parent.end = mas_data_end(&parent); + } + rebalance_data(&cp, wr_mas, &sib, &parent); + multi_src_setup(&cp, wr_mas, wr_mas, &sib); + dst_setup(&cp, mas, wr_mas->type); + cp_data_write(&cp, mas); + } while (rebalance_ascend(&cp, wr_mas, &sib, &parent)); + + old_enode = mas->node; + mas->node = mt_slot_locked(mas->tree, cp.slot, 0); + mas_wmb_replace(mas, old_enode, cp.height); + mtree_range_walk(mas); } /* -- cgit From 0abff2081983e5dfa7642ab1a794afc0a8417070 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Fri, 30 Jan 2026 15:59:29 -0500 Subject: maple_tree: add copy_tree_location() helper Extract the copying of the tree location from one maple state to another into its own function. This is used more later. Link: https://lkml.kernel.org/r/20260130205935.2559335-25-Liam.Howlett@oracle.com Signed-off-by: Liam R. Howlett Cc: Alice Ryhl Cc: Andrew Ballance Cc: Arnd Bergmann Cc: Christian Kujau Cc: Geert Uytterhoeven Cc: Kuninori Morimoto Cc: Matthew Wilcox (Oracle) Cc: SeongJae Park Cc: Sidhartha Kumar Cc: Suren Baghdasaryan Cc: Vlastimil Babka Signed-off-by: Andrew Morton --- lib/maple_tree.c | 18 ++++++++++++------ 1 file changed, 12 insertions(+), 6 deletions(-) (limited to 'lib') diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 7ce7c0a33943..86072bfc2419 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -3531,6 +3531,17 @@ static bool spanning_ascend(struct maple_copy *cp, struct ma_state *mas, return true; } +static inline +void copy_tree_location(const struct ma_state *src, struct ma_state *dst) +{ + dst->node = src->node; + dst->offset = src->offset; + dst->min = src->min; + dst->max = src->max; + dst->end = src->end; + dst->depth = src->depth; +} + /* * rebalance_ascend() - Ascend the tree and set up for the next loop - if * necessary @@ -3570,12 +3581,7 @@ static inline bool rebalance_ascend(struct maple_copy *cp, } cp->height++; - mas->node = parent->node; - mas->offset = parent->offset; - mas->min = parent->min; - mas->max = parent->max; - mas->end = parent->end; - mas->depth = parent->depth; + copy_tree_location(parent, mas); wr_mas_setup(wr_mas, mas); return true; } -- cgit From 11e7f22f5e85058b09ca90e74002a3b82f50e940 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Fri, 30 Jan 2026 15:59:30 -0500 Subject: maple_tree: add cp_converged() helper When the maple copy node converges into a single entry, then certain operations can stop ascending the tree. This is used more later. Link: https://lkml.kernel.org/r/20260130205935.2559335-26-Liam.Howlett@oracle.com Signed-off-by: Liam R. Howlett Cc: Alice Ryhl Cc: Andrew Ballance Cc: Arnd Bergmann Cc: Christian Kujau Cc: Geert Uytterhoeven Cc: Kuninori Morimoto Cc: Matthew Wilcox (Oracle) Cc: SeongJae Park Cc: Sidhartha Kumar Cc: Suren Baghdasaryan Cc: Vlastimil Babka Signed-off-by: Andrew Morton --- lib/maple_tree.c | 14 +++++++++++--- 1 file changed, 11 insertions(+), 3 deletions(-) (limited to 'lib') diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 86072bfc2419..3e0469d365e6 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -3493,6 +3493,16 @@ static inline bool cp_is_new_root(struct maple_copy *cp, struct ma_state *mas) return true; } +static inline bool cp_converged(struct maple_copy *cp, struct ma_state *mas, + struct ma_state *sib) +{ + if (cp->d_count != 1 || sib->end) + return false; + + cp->dst[0].node->parent = ma_parent_ptr(mas_mn(mas)->parent); + return true; +} + /* * spanning_ascend() - See if a spanning store operation has to keep walking up * the tree @@ -3575,10 +3585,8 @@ static inline bool rebalance_ascend(struct maple_copy *cp, if (cp_is_new_root(cp, mas)) return false; - if (cp->d_count == 1 && !sib->end) { - cp->dst[0].node->parent = ma_parent_ptr(mas_mn(mas)->parent); + if (cp_converged(cp, mas, sib)) return false; - } cp->height++; copy_tree_location(parent, mas); -- cgit From 280b792cac62ddadca2935766ca870b438c86323 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Fri, 30 Jan 2026 15:59:31 -0500 Subject: maple_tree: use maple copy node for mas_wr_split() Instead of using the maple big node, use the maple copy node for reduced stack usage and aligning with mas_wr_rebalance() and mas_wr_spanning_store(). Splitting a node is similar to rebalancing, but a new evaluation of when to ascend is needed. The only other difference is that the data is pushed and never rebalanced at each level. The testing must also align with the changes to this commit to ensure the test suite continues to pass. Link: https://lkml.kernel.org/r/20260130205935.2559335-27-Liam.Howlett@oracle.com Signed-off-by: Liam R. Howlett Cc: Alice Ryhl Cc: Andrew Ballance Cc: Arnd Bergmann Cc: Christian Kujau Cc: Geert Uytterhoeven Cc: Kuninori Morimoto Cc: Matthew Wilcox (Oracle) Cc: SeongJae Park Cc: Sidhartha Kumar Cc: Suren Baghdasaryan Cc: Vlastimil Babka Signed-off-by: Andrew Morton --- lib/maple_tree.c | 99 +++++++++++++++++++++++++++++++++++++--- lib/test_maple_tree.c | 55 ++++++++++++++++++---- tools/testing/radix-tree/maple.c | 11 +++++ 3 files changed, 149 insertions(+), 16 deletions(-) (limited to 'lib') diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 3e0469d365e6..68ea6c3c9260 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -4542,19 +4542,106 @@ static inline void mas_wr_append(struct ma_wr_state *wr_mas, trace_ma_write(TP_FCT, mas, new_end, wr_mas->entry); } +/* + * split_ascend() - See if a split operation has to keep walking up the tree + * @cp: The maple_copy node + * @wr_mas: The maple write state + * @sib: the maple state of the sibling + * + * Return: true if another split operation on the next level is needed, false + * otherwise + */ +static inline bool split_ascend(struct maple_copy *cp, + struct ma_wr_state *wr_mas, struct ma_state *sib, + struct ma_state *parent) +{ + struct ma_state *mas; + unsigned long min, max; + + mas = wr_mas->mas; + min = mas->min; /* push right, or normal split */ + max = mas->max; + wr_mas->offset_end = parent->offset; + if (sib->end) { + if (sib->max < mas->min) { + min = sib->min; /* push left */ + parent->offset--; + } else { + max = sib->max; /* push right */ + wr_mas->offset_end++; + } + } + + cp_dst_to_slots(cp, min, max, mas); + if (cp_is_new_root(cp, mas)) + return false; + + if (cp_converged(cp, mas, sib)) + return false; + + cp->height++; + copy_tree_location(parent, mas); + wr_mas_setup(wr_mas, mas); + return true; +} + +/* + * split_data() - Calculate the @cp data, populate @sib if the data can be + * pushed into a sibling. + * @cp: The maple copy node + * @wr_mas: The left write maple state + * @sib: The maple state of the sibling. + * + * Note: @cp->data is a size and not indexed by 0. @sib->end may be set to 0 to + * indicate it will not be used. + * + */ +static inline void split_data(struct maple_copy *cp, + struct ma_wr_state *wr_mas, struct ma_state *sib, + struct ma_state *parent) +{ + cp_data_calc(cp, wr_mas, wr_mas); + if (cp->data <= mt_slots[wr_mas->type]) { + sib->end = 0; + return; + } + + push_data_sib(cp, wr_mas->mas, sib, parent); + if (sib->end) + cp->data += sib->end + 1; +} + /* * mas_wr_split() - Expand one node into two * @wr_mas: The write maple state */ -static noinline_for_kasan void mas_wr_split(struct ma_wr_state *wr_mas) +static void mas_wr_split(struct ma_wr_state *wr_mas) { - struct maple_big_node b_node; + struct maple_enode *old_enode; + struct ma_state parent; + struct ma_state *mas; + struct maple_copy cp; + struct ma_state sib; + mas = wr_mas->mas; trace_ma_write(TP_FCT, wr_mas->mas, 0, wr_mas->entry); - memset(&b_node, 0, sizeof(struct maple_big_node)); - mas_store_b_node(wr_mas, &b_node, wr_mas->offset_end); - WARN_ON_ONCE(wr_mas->mas->store_type != wr_split_store); - return mas_split(wr_mas->mas, &b_node); + parent = *mas; + cp_leaf_init(&cp, mas, wr_mas, wr_mas); + do { + if (!mte_is_root(parent.node)) { + mas_ascend(&parent); + parent.end = mas_data_end(&parent); + } + split_data(&cp, wr_mas, &sib, &parent); + multi_src_setup(&cp, wr_mas, wr_mas, &sib); + dst_setup(&cp, mas, wr_mas->type); + cp_data_write(&cp, mas); + } while (split_ascend(&cp, wr_mas, &sib, &parent)); + + old_enode = mas->node; + mas->node = mt_slot_locked(mas->tree, cp.slot, 0); + mas_wmb_replace(mas, old_enode, cp.height); + mtree_range_walk(mas); } /* diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c index a182e48b5f5e..434d8a2fdd99 100644 --- a/lib/test_maple_tree.c +++ b/lib/test_maple_tree.c @@ -1024,6 +1024,7 @@ static noinline void __init check_ranges(struct maple_tree *mt) mt_set_non_kernel(10); check_store_range(mt, r[10], r[11], xa_mk_value(r[10]), 0); MT_BUG_ON(mt, !mt_height(mt)); + mt_validate(mt); mtree_destroy(mt); /* Create tree of 1-200 */ @@ -1031,11 +1032,13 @@ static noinline void __init check_ranges(struct maple_tree *mt) /* Store 45-168 */ check_store_range(mt, r[10], r[11], xa_mk_value(r[10]), 0); MT_BUG_ON(mt, !mt_height(mt)); + mt_validate(mt); mtree_destroy(mt); check_seq(mt, 30, false); check_store_range(mt, 6, 18, xa_mk_value(6), 0); MT_BUG_ON(mt, !mt_height(mt)); + mt_validate(mt); mtree_destroy(mt); /* Overwrite across multiple levels. */ @@ -1061,6 +1064,7 @@ static noinline void __init check_ranges(struct maple_tree *mt) check_load(mt, r[13] + 1, xa_mk_value(r[13] + 1)); check_load(mt, 135, NULL); check_load(mt, 140, NULL); + mt_validate(mt); mt_set_non_kernel(0); MT_BUG_ON(mt, !mt_height(mt)); mtree_destroy(mt); @@ -1285,14 +1289,20 @@ static noinline void __init check_ranges(struct maple_tree *mt) MT_BUG_ON(mt, mt_height(mt) >= 4); } /* Cause a 3 child split all the way up the tree. */ - for (i = 5; i < 215; i += 10) + for (i = 5; i < 215; i += 10) { check_store_range(mt, 11450 + i, 11450 + i + 1, NULL, 0); - for (i = 5; i < 65; i += 10) + mt_validate(mt); + } + for (i = 5; i < 65; i += 10) { check_store_range(mt, 11770 + i, 11770 + i + 1, NULL, 0); + mt_validate(mt); + } MT_BUG_ON(mt, mt_height(mt) >= 4); - for (i = 5; i < 45; i += 10) + for (i = 5; i < 45; i += 10) { check_store_range(mt, 11700 + i, 11700 + i + 1, NULL, 0); + mt_validate(mt); + } if (!MAPLE_32BIT) MT_BUG_ON(mt, mt_height(mt) < 4); mtree_destroy(mt); @@ -1304,17 +1314,42 @@ static noinline void __init check_ranges(struct maple_tree *mt) val2 = (i+1)*10; check_store_range(mt, val, val2, xa_mk_value(val), 0); MT_BUG_ON(mt, mt_height(mt) >= 4); + mt_validate(mt); + } + /* Fill parents and leaves before split. */ + val = 7660; + for (i = 5; i < 490; i += 5) { + val += 5; + check_store_range(mt, val, val + 1, NULL, 0); + mt_validate(mt); + MT_BUG_ON(mt, mt_height(mt) >= 4); } + + val = 9460; /* Fill parents and leaves before split. */ - for (i = 5; i < 455; i += 10) - check_store_range(mt, 7800 + i, 7800 + i + 1, NULL, 0); + for (i = 1; i < 10; i++) { + val++; + check_store_range(mt, val, val + 1, xa_mk_value(val), 0); + mt_validate(mt); + } - for (i = 1; i < 16; i++) - check_store_range(mt, 8185 + i, 8185 + i + 1, - xa_mk_value(8185+i), 0); - MT_BUG_ON(mt, mt_height(mt) >= 4); + val = 8000; + for (i = 1; i < 14; i++) { + val++; + check_store_range(mt, val, val + 1, xa_mk_value(val), 0); + mt_validate(mt); + } + + + check_store_range(mt, 8051, 8051, xa_mk_value(8081), 0); + check_store_range(mt, 8052, 8052, xa_mk_value(8082), 0); + check_store_range(mt, 8083, 8083, xa_mk_value(8083), 0); + check_store_range(mt, 8084, 8084, xa_mk_value(8084), 0); + check_store_range(mt, 8085, 8085, xa_mk_value(8085), 0); /* triple split across multiple levels. */ - check_store_range(mt, 8184, 8184, xa_mk_value(8184), 0); + check_store_range(mt, 8099, 8100, xa_mk_value(1), 0); + + mt_validate(mt); if (!MAPLE_32BIT) MT_BUG_ON(mt, mt_height(mt) != 4); } diff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/maple.c index 5ea45d67556a..feedd5ab7058 100644 --- a/tools/testing/radix-tree/maple.c +++ b/tools/testing/radix-tree/maple.c @@ -35406,7 +35406,18 @@ static noinline void __init check_spanning_write(struct maple_tree *mt) mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); for (i = 0; i <= max; i++) mtree_test_store_range(mt, i * 10, i * 10 + 5, &i); + mtree_lock(mt); + if (MAPLE_32BIT) { + i = 47811; + do { + mas_set(&mas, i); + mas_store_gfp(&mas, check_spanning_write, GFP_KERNEL); + i++; + mas_ascend(&mas); + } while (mas_data_end(&mas) < mt_slot_count(mas.node) - 1); + } + mas_set(&mas, 47606); mas_store_gfp(&mas, check_spanning_write, GFP_KERNEL); mas_set(&mas, 47607); -- cgit From b8852ef30c67318d40e69d295e28f6cab5174862 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Fri, 30 Jan 2026 15:59:32 -0500 Subject: maple_tree: remove maple big node and subtree structs Now that no one uses the structures and functions, drop the dead code. Link: https://lkml.kernel.org/r/20260130205935.2559335-28-Liam.Howlett@oracle.com Signed-off-by: Liam R. Howlett Cc: Alice Ryhl Cc: Andrew Ballance Cc: Arnd Bergmann Cc: Christian Kujau Cc: Geert Uytterhoeven Cc: Kuninori Morimoto Cc: Matthew Wilcox (Oracle) Cc: SeongJae Park Cc: Sidhartha Kumar Cc: Suren Baghdasaryan Cc: Vlastimil Babka Signed-off-by: Andrew Morton --- lib/maple_tree.c | 1184 ------------------------------------------------------ 1 file changed, 1184 deletions(-) (limited to 'lib') diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 68ea6c3c9260..51ff311ff5b6 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -133,45 +133,6 @@ static const unsigned char mt_min_slots[] = { }; #define mt_min_slot_count(x) mt_min_slots[mte_node_type(x)] -#define MAPLE_BIG_NODE_SLOTS (MAPLE_RANGE64_SLOTS * 2 + 2) -#define MAPLE_BIG_NODE_GAPS (MAPLE_ARANGE64_SLOTS * 2 + 1) - -struct maple_big_node { - unsigned long pivot[MAPLE_BIG_NODE_SLOTS - 1]; - union { - struct maple_enode *slot[MAPLE_BIG_NODE_SLOTS]; - struct { - unsigned long padding[MAPLE_BIG_NODE_GAPS]; - unsigned long gap[MAPLE_BIG_NODE_GAPS]; - }; - }; - unsigned char b_end; - enum maple_type type; -}; - -/* - * The maple_subtree_state is used to build a tree to replace a segment of an - * existing tree in a more atomic way. Any walkers of the older tree will hit a - * dead node and restart on updates. - */ -struct maple_subtree_state { - struct ma_state *orig_l; /* Original left side of subtree */ - struct ma_state *orig_r; /* Original right side of subtree */ - struct ma_state *l; /* New left side of subtree */ - struct ma_state *m; /* New middle of subtree (rare) */ - struct ma_state *r; /* New right side of subtree */ - struct ma_topiary *free; /* nodes to be freed */ - struct ma_topiary *destroy; /* Nodes to be destroyed (walked and freed) */ - struct maple_big_node *bn; -}; - -#ifdef CONFIG_KASAN_STACK -/* Prevent mas_wr_bnode() from exceeding the stack frame limit */ -#define noinline_for_kasan noinline_for_stack -#else -#define noinline_for_kasan inline -#endif - /* Functions */ static inline struct maple_node *mt_alloc_one(gfp_t gfp) { @@ -1669,169 +1630,6 @@ static inline bool mas_find_child(struct ma_state *mas, struct ma_state *child) return false; } -/* - * mab_shift_right() - Shift the data in mab right. Note, does not clean out the - * old data or set b_node->b_end. - * @b_node: the maple_big_node - * @shift: the shift count - */ -static inline void mab_shift_right(struct maple_big_node *b_node, - unsigned char shift) -{ - unsigned long size = b_node->b_end * sizeof(unsigned long); - - memmove(b_node->pivot + shift, b_node->pivot, size); - memmove(b_node->slot + shift, b_node->slot, size); - if (b_node->type == maple_arange_64) - memmove(b_node->gap + shift, b_node->gap, size); -} - -/* - * mab_middle_node() - Check if a middle node is needed (unlikely) - * @b_node: the maple_big_node that contains the data. - * @split: the potential split location - * @slot_count: the size that can be stored in a single node being considered. - * - * Return: true if a middle node is required. - */ -static inline bool mab_middle_node(struct maple_big_node *b_node, int split, - unsigned char slot_count) -{ - unsigned char size = b_node->b_end; - - if (size >= 2 * slot_count) - return true; - - if (!b_node->slot[split] && (size >= 2 * slot_count - 1)) - return true; - - return false; -} - -/* - * mab_no_null_split() - ensure the split doesn't fall on a NULL - * @b_node: the maple_big_node with the data - * @split: the suggested split location - * @slot_count: the number of slots in the node being considered. - * - * Return: the split location. - */ -static inline int mab_no_null_split(struct maple_big_node *b_node, - unsigned char split, unsigned char slot_count) -{ - if (!b_node->slot[split]) { - /* - * If the split is less than the max slot && the right side will - * still be sufficient, then increment the split on NULL. - */ - if ((split < slot_count - 1) && - (b_node->b_end - split) > (mt_min_slots[b_node->type])) - split++; - else - split--; - } - return split; -} - -/* - * mab_calc_split() - Calculate the split location and if there needs to be two - * splits. - * @mas: The maple state - * @bn: The maple_big_node with the data - * @mid_split: The second split, if required. 0 otherwise. - * - * Return: The first split location. The middle split is set in @mid_split. - */ -static inline int mab_calc_split(struct ma_state *mas, - struct maple_big_node *bn, unsigned char *mid_split) -{ - unsigned char b_end = bn->b_end; - int split = b_end / 2; /* Assume equal split. */ - unsigned char slot_count = mt_slots[bn->type]; - - /* - * To support gap tracking, all NULL entries are kept together and a node cannot - * end on a NULL entry, with the exception of the left-most leaf. The - * limitation means that the split of a node must be checked for this condition - * and be able to put more data in one direction or the other. - * - * Although extremely rare, it is possible to enter what is known as the 3-way - * split scenario. The 3-way split comes about by means of a store of a range - * that overwrites the end and beginning of two full nodes. The result is a set - * of entries that cannot be stored in 2 nodes. Sometimes, these two nodes can - * also be located in different parent nodes which are also full. This can - * carry upwards all the way to the root in the worst case. - */ - if (unlikely(mab_middle_node(bn, split, slot_count))) { - split = b_end / 3; - *mid_split = split * 2; - } else { - *mid_split = 0; - } - - /* Avoid ending a node on a NULL entry */ - split = mab_no_null_split(bn, split, slot_count); - - if (unlikely(*mid_split)) - *mid_split = mab_no_null_split(bn, *mid_split, slot_count); - - return split; -} - -/* - * mas_mab_cp() - Copy data from a maple state inclusively to a maple_big_node - * and set @b_node->b_end to the next free slot. - * @mas: The maple state - * @mas_start: The starting slot to copy - * @mas_end: The end slot to copy (inclusively) - * @b_node: The maple_big_node to place the data - * @mab_start: The starting location in maple_big_node to store the data. - */ -static inline void mas_mab_cp(struct ma_state *mas, unsigned char mas_start, - unsigned char mas_end, struct maple_big_node *b_node, - unsigned char mab_start) -{ - enum maple_type mt; - struct maple_node *node; - void __rcu **slots; - unsigned long *pivots, *gaps; - int i = mas_start, j = mab_start; - unsigned char piv_end; - - node = mas_mn(mas); - mt = mte_node_type(mas->node); - pivots = ma_pivots(node, mt); - if (!i) { - b_node->pivot[j] = pivots[i++]; - if (unlikely(i > mas_end)) - goto complete; - j++; - } - - piv_end = min(mas_end, mt_pivots[mt]); - for (; i < piv_end; i++, j++) { - b_node->pivot[j] = pivots[i]; - if (unlikely(!b_node->pivot[j])) - goto complete; - - if (unlikely(mas->max == b_node->pivot[j])) - goto complete; - } - - b_node->pivot[j] = mas_safe_pivot(mas, pivots, i, mt); - -complete: - b_node->b_end = ++j; - j -= mab_start; - slots = ma_slots(node, mt); - memcpy(b_node->slot + mab_start, slots + mas_start, sizeof(void *) * j); - if (!ma_is_leaf(mt) && mt_is_alloc(mas->tree)) { - gaps = ma_gaps(node, mt); - memcpy(b_node->gap + mab_start, gaps + mas_start, - sizeof(unsigned long) * j); - } -} - /* * mas_leaf_set_meta() - Set the metadata of a leaf if possible. * @node: The maple node @@ -1845,134 +1643,6 @@ static inline void mas_leaf_set_meta(struct maple_node *node, ma_set_meta(node, mt, 0, end); } -/* - * mab_mas_cp() - Copy data from maple_big_node to a maple encoded node. - * @b_node: the maple_big_node that has the data - * @mab_start: the start location in @b_node. - * @mab_end: The end location in @b_node (inclusively) - * @mas: The maple state with the maple encoded node. - */ -static inline void mab_mas_cp(struct maple_big_node *b_node, - unsigned char mab_start, unsigned char mab_end, - struct ma_state *mas, bool new_max) -{ - int i, j = 0; - enum maple_type mt = mte_node_type(mas->node); - struct maple_node *node = mte_to_node(mas->node); - void __rcu **slots = ma_slots(node, mt); - unsigned long *pivots = ma_pivots(node, mt); - unsigned long *gaps = NULL; - unsigned char end; - - if (mab_end - mab_start > mt_pivots[mt]) - mab_end--; - - if (!pivots[mt_pivots[mt] - 1]) - slots[mt_pivots[mt]] = NULL; - - i = mab_start; - do { - pivots[j++] = b_node->pivot[i++]; - } while (i <= mab_end && likely(b_node->pivot[i])); - - memcpy(slots, b_node->slot + mab_start, - sizeof(void *) * (i - mab_start)); - - if (new_max) - mas->max = b_node->pivot[i - 1]; - - end = j - 1; - if (likely(!ma_is_leaf(mt) && mt_is_alloc(mas->tree))) { - unsigned long max_gap = 0; - unsigned char offset = 0; - - gaps = ma_gaps(node, mt); - do { - gaps[--j] = b_node->gap[--i]; - if (gaps[j] > max_gap) { - offset = j; - max_gap = gaps[j]; - } - } while (j); - - ma_set_meta(node, mt, offset, end); - } else { - mas_leaf_set_meta(node, mt, end); - } -} - -/* - * mas_store_b_node() - Store an @entry into the b_node while also copying the - * data from a maple encoded node. - * @wr_mas: the maple write state - * @b_node: the maple_big_node to fill with data - * @offset_end: the offset to end copying - * - * Return: The actual end of the data stored in @b_node - */ -static noinline_for_kasan void mas_store_b_node(struct ma_wr_state *wr_mas, - struct maple_big_node *b_node, unsigned char offset_end) -{ - unsigned char slot; - unsigned char b_end; - /* Possible underflow of piv will wrap back to 0 before use. */ - unsigned long piv; - struct ma_state *mas = wr_mas->mas; - - b_node->type = wr_mas->type; - b_end = 0; - slot = mas->offset; - if (slot) { - /* Copy start data up to insert. */ - mas_mab_cp(mas, 0, slot - 1, b_node, 0); - b_end = b_node->b_end; - piv = b_node->pivot[b_end - 1]; - } else - piv = mas->min - 1; - - if (piv + 1 < mas->index) { - /* Handle range starting after old range */ - b_node->slot[b_end] = wr_mas->content; - if (!wr_mas->content) - b_node->gap[b_end] = mas->index - 1 - piv; - b_node->pivot[b_end++] = mas->index - 1; - } - - /* Store the new entry. */ - mas->offset = b_end; - b_node->slot[b_end] = wr_mas->entry; - b_node->pivot[b_end] = mas->last; - - /* Appended. */ - if (mas->last >= mas->max) - goto b_end; - - /* Handle new range ending before old range ends */ - piv = mas_safe_pivot(mas, wr_mas->pivots, offset_end, wr_mas->type); - if (piv > mas->last) { - if (offset_end != slot) - wr_mas->content = mas_slot_locked(mas, wr_mas->slots, - offset_end); - - b_node->slot[++b_end] = wr_mas->content; - if (!wr_mas->content) - b_node->gap[b_end] = piv - mas->last + 1; - b_node->pivot[b_end] = piv; - } - - slot = offset_end + 1; - if (slot > mas->end) - goto b_end; - - /* Copy end data to the end of the node. */ - mas_mab_cp(mas, slot, mas->end + 1, b_node, ++b_end); - b_node->b_end--; - return; - -b_end: - b_node->b_end = b_end; -} - /* * mas_prev_sibling() - Find the previous node with the same parent. * @mas: the maple state @@ -2017,25 +1687,6 @@ static inline bool mas_next_sibling(struct ma_state *mas) return true; } -/* - * mas_node_or_none() - Set the enode and state. - * @mas: the maple state - * @enode: The encoded maple node. - * - * Set the node to the enode and the status. - */ -static inline void mas_node_or_none(struct ma_state *mas, - struct maple_enode *enode) -{ - if (enode) { - mas->node = enode; - mas->status = ma_active; - } else { - mas->node = NULL; - mas->status = ma_none; - } -} - /* * mas_wr_node_walk() - Find the correct offset for the index in the @mas. * If @mas->index cannot be found within the containing @@ -2069,242 +1720,6 @@ static inline void mas_wr_node_walk(struct ma_wr_state *wr_mas) wr_mas->offset_end = mas->offset = offset; } -/* - * mast_rebalance_next() - Rebalance against the next node - * @mast: The maple subtree state - */ -static inline void mast_rebalance_next(struct maple_subtree_state *mast) -{ - unsigned char b_end = mast->bn->b_end; - - mas_mab_cp(mast->orig_r, 0, mt_slot_count(mast->orig_r->node), - mast->bn, b_end); - mast->orig_r->last = mast->orig_r->max; -} - -/* - * mast_rebalance_prev() - Rebalance against the previous node - * @mast: The maple subtree state - */ -static inline void mast_rebalance_prev(struct maple_subtree_state *mast) -{ - unsigned char end = mas_data_end(mast->orig_l) + 1; - unsigned char b_end = mast->bn->b_end; - - mab_shift_right(mast->bn, end); - mas_mab_cp(mast->orig_l, 0, end - 1, mast->bn, 0); - mast->l->min = mast->orig_l->min; - mast->orig_l->index = mast->orig_l->min; - mast->bn->b_end = end + b_end; - mast->l->offset += end; -} - -/* - * mast_spanning_rebalance() - Rebalance nodes with nearest neighbour favouring - * the node to the right. Checking the nodes to the right then the left at each - * level upwards until root is reached. - * Data is copied into the @mast->bn. - * @mast: The maple_subtree_state. - */ -static inline -bool mast_spanning_rebalance(struct maple_subtree_state *mast) -{ - struct ma_state r_tmp = *mast->orig_r; - struct ma_state l_tmp = *mast->orig_l; - unsigned char depth = 0; - - do { - mas_ascend(mast->orig_r); - mas_ascend(mast->orig_l); - depth++; - if (mast->orig_r->offset < mas_data_end(mast->orig_r)) { - mast->orig_r->offset++; - do { - mas_descend(mast->orig_r); - mast->orig_r->offset = 0; - } while (--depth); - - mast_rebalance_next(mast); - *mast->orig_l = l_tmp; - return true; - } else if (mast->orig_l->offset != 0) { - mast->orig_l->offset--; - do { - mas_descend(mast->orig_l); - mast->orig_l->offset = - mas_data_end(mast->orig_l); - } while (--depth); - - mast_rebalance_prev(mast); - *mast->orig_r = r_tmp; - return true; - } - } while (!mte_is_root(mast->orig_r->node)); - - *mast->orig_r = r_tmp; - *mast->orig_l = l_tmp; - return false; -} - -/* - * mast_ascend() - Ascend the original left and right maple states. - * @mast: the maple subtree state. - * - * Ascend the original left and right sides. Set the offsets to point to the - * data already in the new tree (@mast->l and @mast->r). - */ -static inline void mast_ascend(struct maple_subtree_state *mast) -{ - MA_WR_STATE(wr_mas, mast->orig_r, NULL); - mas_ascend(mast->orig_l); - mas_ascend(mast->orig_r); - - mast->orig_r->offset = 0; - mast->orig_r->index = mast->r->max; - /* last should be larger than or equal to index */ - if (mast->orig_r->last < mast->orig_r->index) - mast->orig_r->last = mast->orig_r->index; - - wr_mas.type = mte_node_type(mast->orig_r->node); - mas_wr_node_walk(&wr_mas); - /* Set up the left side of things */ - mast->orig_l->offset = 0; - mast->orig_l->index = mast->l->min; - wr_mas.mas = mast->orig_l; - wr_mas.type = mte_node_type(mast->orig_l->node); - mas_wr_node_walk(&wr_mas); - - mast->bn->type = wr_mas.type; -} - -/* - * mas_new_ma_node() - Create and return a new maple node. Helper function. - * @mas: the maple state with the allocations. - * @b_node: the maple_big_node with the type encoding. - * - * Use the node type from the maple_big_node to allocate a new node from the - * ma_state. This function exists mainly for code readability. - * - * Return: A new maple encoded node - */ -static inline struct maple_enode -*mas_new_ma_node(struct ma_state *mas, struct maple_big_node *b_node) -{ - return mt_mk_node(ma_mnode_ptr(mas_pop_node(mas)), b_node->type); -} - -/* - * mas_mab_to_node() - Set up right and middle nodes - * - * @mas: the maple state that contains the allocations. - * @b_node: the node which contains the data. - * @left: The pointer which will have the left node - * @right: The pointer which may have the right node - * @middle: the pointer which may have the middle node (rare) - * @mid_split: the split location for the middle node - * - * Return: the split of left. - */ -static inline unsigned char mas_mab_to_node(struct ma_state *mas, - struct maple_big_node *b_node, struct maple_enode **left, - struct maple_enode **right, struct maple_enode **middle, - unsigned char *mid_split) -{ - unsigned char split = 0; - unsigned char slot_count = mt_slots[b_node->type]; - - *left = mas_new_ma_node(mas, b_node); - *right = NULL; - *middle = NULL; - *mid_split = 0; - - if (b_node->b_end < slot_count) { - split = b_node->b_end; - } else { - split = mab_calc_split(mas, b_node, mid_split); - *right = mas_new_ma_node(mas, b_node); - } - - if (*mid_split) - *middle = mas_new_ma_node(mas, b_node); - - return split; - -} - -/* - * mab_set_b_end() - Add entry to b_node at b_node->b_end and increment the end - * pointer. - * @b_node: the big node to add the entry - * @mas: the maple state to get the pivot (mas->max) - * @entry: the entry to add, if NULL nothing happens. - */ -static inline void mab_set_b_end(struct maple_big_node *b_node, - struct ma_state *mas, - void *entry) -{ - if (!entry) - return; - - b_node->slot[b_node->b_end] = entry; - if (mt_is_alloc(mas->tree)) - b_node->gap[b_node->b_end] = mas_max_gap(mas); - b_node->pivot[b_node->b_end++] = mas->max; -} - -/* - * mas_set_split_parent() - combine_then_separate helper function. Sets the parent - * of @mas->node to either @left or @right, depending on @slot and @split - * - * @mas: the maple state with the node that needs a parent - * @left: possible parent 1 - * @right: possible parent 2 - * @slot: the slot the mas->node was placed - * @split: the split location between @left and @right - */ -static inline void mas_set_split_parent(struct ma_state *mas, - struct maple_enode *left, - struct maple_enode *right, - unsigned char *slot, unsigned char split) -{ - if (mas_is_none(mas)) - return; - - if ((*slot) <= split) - mas_set_parent(mas, mas->node, left, *slot); - else if (right) - mas_set_parent(mas, mas->node, right, (*slot) - split - 1); - - (*slot)++; -} - -/* - * mte_mid_split_check() - Check if the next node passes the mid-split - * @l: Pointer to left encoded maple node. - * @m: Pointer to middle encoded maple node. - * @r: Pointer to right encoded maple node. - * @slot: The offset - * @split: The split location. - * @mid_split: The middle split. - */ -static inline void mte_mid_split_check(struct maple_enode **l, - struct maple_enode **r, - struct maple_enode *right, - unsigned char slot, - unsigned char *split, - unsigned char mid_split) -{ - if (*r == right) - return; - - if (slot < mid_split) - return; - - *l = *r; - *r = right; - *split = mid_split; -} - static inline void rebalance_sib(struct ma_state *parent, struct ma_state *sib) { *sib = *parent; @@ -2356,43 +1771,6 @@ void spanning_sib(struct ma_wr_state *l_wr_mas, WARN_ON_ONCE(1); } -/* - * mast_set_split_parents() - Helper function to set three nodes parents. Slot - * is taken from @mast->l. - * @mast: the maple subtree state - * @left: the left node - * @right: the right node - * @split: the split location. - */ -static inline void mast_set_split_parents(struct maple_subtree_state *mast, - struct maple_enode *left, - struct maple_enode *middle, - struct maple_enode *right, - unsigned char split, - unsigned char mid_split) -{ - unsigned char slot; - struct maple_enode *l = left; - struct maple_enode *r = right; - - if (mas_is_none(mast->l)) - return; - - if (middle) - r = middle; - - slot = mast->l->offset; - - mte_mid_split_check(&l, &r, right, slot, &split, mid_split); - mas_set_split_parent(mast->l, l, r, &slot, split); - - mte_mid_split_check(&l, &r, right, slot, &split, mid_split); - mas_set_split_parent(mast->m, l, r, &slot, split); - - mte_mid_split_check(&l, &r, right, slot, &split, mid_split); - mas_set_split_parent(mast->r, l, r, &slot, split); -} - /* * mas_topiary_node() - Dispose of a single node * @mas: The maple state for pushing nodes @@ -2648,103 +2026,6 @@ void node_finalise(struct maple_node *node, enum maple_type mt, ma_set_meta(node, mt, gap_slot, end - 1); } -/* - * mast_cp_to_nodes() - Copy data out to nodes. - * @mast: The maple subtree state - * @left: The left encoded maple node - * @middle: The middle encoded maple node - * @right: The right encoded maple node - * @split: The location to split between left and (middle ? middle : right) - * @mid_split: The location to split between middle and right. - */ -static inline void mast_cp_to_nodes(struct maple_subtree_state *mast, - struct maple_enode *left, struct maple_enode *middle, - struct maple_enode *right, unsigned char split, unsigned char mid_split) -{ - bool new_lmax = true; - - mas_node_or_none(mast->l, left); - mas_node_or_none(mast->m, middle); - mas_node_or_none(mast->r, right); - - mast->l->min = mast->orig_l->min; - if (split == mast->bn->b_end) { - mast->l->max = mast->orig_r->max; - new_lmax = false; - } - - mab_mas_cp(mast->bn, 0, split, mast->l, new_lmax); - - if (middle) { - mab_mas_cp(mast->bn, 1 + split, mid_split, mast->m, true); - mast->m->min = mast->bn->pivot[split] + 1; - split = mid_split; - } - - mast->r->max = mast->orig_r->max; - if (right) { - mab_mas_cp(mast->bn, 1 + split, mast->bn->b_end, mast->r, false); - mast->r->min = mast->bn->pivot[split] + 1; - } -} - -/* - * mast_combine_cp_left - Copy in the original left side of the tree into the - * combined data set in the maple subtree state big node. - * @mast: The maple subtree state - */ -static inline void mast_combine_cp_left(struct maple_subtree_state *mast) -{ - unsigned char l_slot = mast->orig_l->offset; - - if (!l_slot) - return; - - mas_mab_cp(mast->orig_l, 0, l_slot - 1, mast->bn, 0); -} - -/* - * mast_combine_cp_right: Copy in the original right side of the tree into the - * combined data set in the maple subtree state big node. - * @mast: The maple subtree state - */ -static inline void mast_combine_cp_right(struct maple_subtree_state *mast) -{ - if (mast->bn->pivot[mast->bn->b_end - 1] >= mast->orig_r->max) - return; - - mas_mab_cp(mast->orig_r, mast->orig_r->offset + 1, - mt_slot_count(mast->orig_r->node), mast->bn, - mast->bn->b_end); - mast->orig_r->last = mast->orig_r->max; -} - -/* - * mast_sufficient: Check if the maple subtree state has enough data in the big - * node to create at least one sufficient node - * @mast: the maple subtree state - */ -static inline bool mast_sufficient(struct maple_subtree_state *mast) -{ - if (mast->bn->b_end > mt_min_slot_count(mast->orig_l->node)) - return true; - - return false; -} - -/* - * mast_overflow: Check if there is too much data in the subtree state for a - * single node. - * @mast: The maple subtree state - */ -static inline bool mast_overflow(struct maple_subtree_state *mast) -{ - if (mast->bn->b_end > mt_slot_count(mast->orig_l->node)) - return true; - - return false; -} - static inline void *mtree_range_walk(struct ma_state *mas) { unsigned long *pivots; @@ -3304,158 +2585,6 @@ static inline void cp_dst_to_slots(struct maple_copy *cp, unsigned long min, cp->max = max; } -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; - - /* - * 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 - * rippling up the tree to limit the amount of churn. Once a new sub-section of - * the tree is created, there may be a mix of new and old nodes. The old nodes - * will have the incorrect parent pointers and currently be in two trees: the - * original tree and the partially new tree. To remedy the parent pointers in - * the old tree, the new data is swapped into the active tree and a walk down - * the tree is performed and the parent pointers are updated. - * See mas_topiary_replace() for more information. - */ - while (count--) { - mast->bn->b_end--; - mast->bn->type = mte_node_type(mast->orig_l->node); - split = mas_mab_to_node(mas, mast->bn, &left, &right, &middle, - &mid_split); - mast_set_split_parents(mast, left, middle, right, split, - mid_split); - mast_cp_to_nodes(mast, left, middle, right, split, mid_split); - new_height++; - - /* - * Copy data from next level in the tree to mast->bn from next - * iteration - */ - memset(mast->bn, 0, sizeof(struct maple_big_node)); - mast->bn->type = mte_node_type(left); - - /* Root already stored in l->node. */ - if (mas_is_root_limits(mast->l)) - goto new_root; - - mast_ascend(mast); - mast_combine_cp_left(mast); - 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); - mast->orig_l->last = mast->orig_l->max; - - if (mast_sufficient(mast)) { - if (mast_overflow(mast)) - continue; - - if (mast->orig_l->node == mast->orig_r->node) { - /* - * The data in b_node should be stored in one - * node and in the tree - */ - slot = mast->l->offset; - break; - } - - continue; - } - - /* May be a new root stored in mast->bn */ - if (mas_is_root_limits(mast->orig_l)) - break; - - mast_spanning_rebalance(mast); - - /* rebalancing from other nodes may require another loop. */ - if (!count) - count++; - } - - 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, mast->l, true); - new_height++; - mas_set_parent(mas, left, mast->l->node, slot); - if (middle) - mas_set_parent(mas, middle, mast->l->node, ++slot); - - if (right) - mas_set_parent(mas, right, mast->l->node, ++slot); - - if (mas_is_root_limits(mast->l)) { -new_root: - mas_mn(mast->l)->parent = ma_parent_ptr(mas_tree_parent(mas)); - while (!mte_is_root(mast->orig_l->node)) - mast_ascend(mast); - } else { - mas_mn(mast->l)->parent = mas_mn(mast->orig_l)->parent; - } - - old_enode = mast->orig_l->node; - 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); -} - -/* - * 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); -} - static inline bool cp_is_new_root(struct maple_copy *cp, struct ma_state *mas) { if (cp->min || cp->max != ULONG_MAX) @@ -3594,319 +2723,6 @@ static inline bool rebalance_ascend(struct maple_copy *cp, return true; } -/* - * mas_rebalance() - Rebalance a given node. - * @mas: The maple state - * @b_node: The big maple node. - * - * Rebalance two nodes into a single node or two new nodes that are sufficient. - * Continue upwards until tree is sufficient. - */ -static inline void mas_rebalance(struct ma_state *mas, - struct maple_big_node *b_node) -{ - char empty_count = mas_mt_height(mas); - struct maple_subtree_state mast; - unsigned char shift, b_end = ++b_node->b_end; - - MA_STATE(l_mas, mas->tree, mas->index, mas->last); - MA_STATE(r_mas, mas->tree, mas->index, mas->last); - - trace_ma_op(TP_FCT, mas); - - /* - * Rebalancing occurs if a node is insufficient. Data is rebalanced - * against the node to the right if it exists, otherwise the node to the - * left of this node is rebalanced against this node. If rebalancing - * causes just one node to be produced instead of two, then the parent - * is also examined and rebalanced if it is insufficient. Every level - * tries to combine the data in the same way. If one node contains the - * entire range of the tree, then that node is used as a new root node. - */ - - mast.orig_l = &l_mas; - mast.orig_r = &r_mas; - mast.bn = b_node; - mast.bn->type = mte_node_type(mas->node); - - l_mas = r_mas = *mas; - - if (mas_next_sibling(&r_mas)) { - mas_mab_cp(&r_mas, 0, mt_slot_count(r_mas.node), b_node, b_end); - r_mas.last = r_mas.index = r_mas.max; - } else { - mas_prev_sibling(&l_mas); - shift = mas_data_end(&l_mas) + 1; - mab_shift_right(b_node, shift); - mas->offset += shift; - mas_mab_cp(&l_mas, 0, shift - 1, b_node, 0); - b_node->b_end = shift + b_end; - l_mas.index = l_mas.last = l_mas.min; - } - - return mas_spanning_rebalance(mas, &mast, empty_count); -} - -/* - * mas_split_final_node() - Split the final node in a subtree operation. - * @mast: the maple subtree state - * @mas: The maple state - */ -static inline void mas_split_final_node(struct maple_subtree_state *mast, - struct ma_state *mas) -{ - struct maple_enode *ancestor; - - if (mte_is_root(mas->node)) { - if (mt_is_alloc(mas->tree)) - mast->bn->type = maple_arange_64; - else - mast->bn->type = maple_range_64; - } - /* - * Only a single node is used here, could be root. - * The Big_node data should just fit in a single node. - */ - ancestor = mas_new_ma_node(mas, mast->bn); - mas_set_parent(mas, mast->l->node, ancestor, mast->l->offset); - mas_set_parent(mas, mast->r->node, ancestor, mast->r->offset); - mte_to_node(ancestor)->parent = mas_mn(mas)->parent; - - mast->l->node = ancestor; - mab_mas_cp(mast->bn, 0, mt_slots[mast->bn->type] - 1, mast->l, true); - mas->offset = mast->bn->b_end - 1; -} - -/* - * mast_fill_bnode() - Copy data into the big node in the subtree state - * @mast: The maple subtree state - * @mas: the maple state - * @skip: The number of entries to skip for new nodes insertion. - */ -static inline void mast_fill_bnode(struct maple_subtree_state *mast, - struct ma_state *mas, - unsigned char skip) -{ - bool cp = true; - unsigned char split; - - memset(mast->bn, 0, sizeof(struct maple_big_node)); - - if (mte_is_root(mas->node)) { - cp = false; - } else { - mas_ascend(mas); - mas->offset = mte_parent_slot(mas->node); - } - - if (cp && mast->l->offset) - mas_mab_cp(mas, 0, mast->l->offset - 1, mast->bn, 0); - - split = mast->bn->b_end; - mab_set_b_end(mast->bn, mast->l, mast->l->node); - mast->r->offset = mast->bn->b_end; - mab_set_b_end(mast->bn, mast->r, mast->r->node); - if (mast->bn->pivot[mast->bn->b_end - 1] == mas->max) - cp = false; - - if (cp) - mas_mab_cp(mas, split + skip, mt_slot_count(mas->node) - 1, - mast->bn, mast->bn->b_end); - - mast->bn->b_end--; - mast->bn->type = mte_node_type(mas->node); -} - -/* - * mast_split_data() - Split the data in the subtree state big node into regular - * nodes. - * @mast: The maple subtree state - * @mas: The maple state - * @split: The location to split the big node - */ -static inline void mast_split_data(struct maple_subtree_state *mast, - struct ma_state *mas, unsigned char split) -{ - unsigned char p_slot; - - mab_mas_cp(mast->bn, 0, split, mast->l, true); - mte_set_pivot(mast->r->node, 0, mast->r->max); - mab_mas_cp(mast->bn, split + 1, mast->bn->b_end, mast->r, false); - mast->l->offset = mte_parent_slot(mas->node); - mast->l->max = mast->bn->pivot[split]; - mast->r->min = mast->l->max + 1; - if (mte_is_leaf(mas->node)) - return; - - p_slot = mast->orig_l->offset; - mas_set_split_parent(mast->orig_l, mast->l->node, mast->r->node, - &p_slot, split); - mas_set_split_parent(mast->orig_r, mast->l->node, mast->r->node, - &p_slot, split); -} - -/* - * mas_push_data() - Instead of splitting a node, it is beneficial to push the - * data to the right or left node if there is room. - * @mas: The maple state - * @mast: The maple subtree state - * @left: Push left or not. - * - * Keeping the height of the tree low means faster lookups. - * - * Return: True if pushed, false otherwise. - */ -static inline bool mas_push_data(struct ma_state *mas, - struct maple_subtree_state *mast, bool left) -{ - unsigned char slot_total = mast->bn->b_end; - unsigned char end, space, split; - - MA_STATE(tmp_mas, mas->tree, mas->index, mas->last); - tmp_mas = *mas; - tmp_mas.depth = mast->l->depth; - - if (left && !mas_prev_sibling(&tmp_mas)) - return false; - else if (!left && !mas_next_sibling(&tmp_mas)) - return false; - - end = mas_data_end(&tmp_mas); - slot_total += end; - space = 2 * mt_slot_count(mas->node) - 2; - /* -2 instead of -1 to ensure there isn't a triple split */ - if (ma_is_leaf(mast->bn->type)) - space--; - - if (mas->max == ULONG_MAX) - space--; - - if (slot_total >= space) - return false; - - /* Get the data; Fill mast->bn */ - mast->bn->b_end++; - if (left) { - mab_shift_right(mast->bn, end + 1); - mas_mab_cp(&tmp_mas, 0, end, mast->bn, 0); - mast->bn->b_end = slot_total + 1; - } else { - mas_mab_cp(&tmp_mas, 0, end, mast->bn, mast->bn->b_end); - } - - /* Configure mast for splitting of mast->bn */ - split = mt_slots[mast->bn->type] - 2; - if (left) { - /* Switch mas to prev node */ - *mas = tmp_mas; - /* Start using mast->l for the left side. */ - tmp_mas.node = mast->l->node; - *mast->l = tmp_mas; - } else { - tmp_mas.node = mast->r->node; - *mast->r = tmp_mas; - split = slot_total - split; - } - split = mab_no_null_split(mast->bn, split, mt_slots[mast->bn->type]); - /* Update parent slot for split calculation. */ - if (left) - mast->orig_l->offset += end + 1; - - mast_split_data(mast, mas, split); - mast_fill_bnode(mast, mas, 2); - mas_split_final_node(mast, mas); - return true; -} - -/* - * mas_split() - Split data that is too big for one node into two. - * @mas: The maple state - * @b_node: The maple big node - */ -static void mas_split(struct ma_state *mas, struct maple_big_node *b_node) -{ - struct maple_subtree_state mast; - int height = 0; - unsigned int orig_height = mas_mt_height(mas); - unsigned char mid_split, split = 0; - struct maple_enode *old; - - /* - * Splitting is handled differently from any other B-tree; the Maple - * Tree splits upwards. Splitting up means that the split operation - * occurs when the walk of the tree hits the leaves and not on the way - * down. The reason for splitting up is that it is impossible to know - * how much space will be needed until the leaf is (or leaves are) - * reached. Since overwriting data is allowed and a range could - * overwrite more than one range or result in changing one entry into 3 - * entries, it is impossible to know if a split is required until the - * data is examined. - * - * Splitting is a balancing act between keeping allocations to a minimum - * and avoiding a 'jitter' event where a tree is expanded to make room - * for an entry followed by a contraction when the entry is removed. To - * accomplish the balance, there are empty slots remaining in both left - * and right nodes after a split. - */ - MA_STATE(l_mas, mas->tree, mas->index, mas->last); - MA_STATE(r_mas, mas->tree, mas->index, mas->last); - MA_STATE(prev_l_mas, mas->tree, mas->index, mas->last); - MA_STATE(prev_r_mas, mas->tree, mas->index, mas->last); - - trace_ma_op(TP_FCT, mas); - - mast.l = &l_mas; - mast.r = &r_mas; - mast.orig_l = &prev_l_mas; - mast.orig_r = &prev_r_mas; - mast.bn = b_node; - - while (height++ <= orig_height) { - if (mt_slots[b_node->type] > b_node->b_end) { - mas_split_final_node(&mast, mas); - break; - } - - l_mas = r_mas = *mas; - l_mas.node = mas_new_ma_node(mas, b_node); - r_mas.node = mas_new_ma_node(mas, b_node); - /* - * Another way that 'jitter' is avoided is to terminate a split up early if the - * left or right node has space to spare. This is referred to as "pushing left" - * or "pushing right" and is similar to the B* tree, except the nodes left or - * right can rarely be reused due to RCU, but the ripple upwards is halted which - * is a significant savings. - */ - /* Try to push left. */ - if (mas_push_data(mas, &mast, true)) { - height++; - break; - } - /* Try to push right. */ - if (mas_push_data(mas, &mast, false)) { - height++; - break; - } - - split = mab_calc_split(mas, b_node, &mid_split); - mast_split_data(&mast, mas, split); - /* - * Usually correct, mab_mas_cp in the above call overwrites - * r->max. - */ - mast.r->max = mas->max; - mast_fill_bnode(&mast, mas, 1); - prev_l_mas = *mast.l; - prev_r_mas = *mast.r; - } - - /* Set the original node as dead */ - old = mas->node; - mas->node = l_mas.node; - mas_wmb_replace(mas, old, height); - mtree_range_walk(mas); -} - /* * mas_root_expand() - Expand a root to a node * @mas: The maple state -- cgit From 2969241fa22e39f0c751e96d2f53b1d9dfac19ba Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Fri, 30 Jan 2026 15:59:33 -0500 Subject: maple_tree: pass maple copy node to mas_wmb_replace() mas_wmb_replace() is called in three places with the same setup, move the setup into the function itself. The function needs to be relocated as it calls mtree_range_walk(). Link: https://lkml.kernel.org/r/20260130205935.2559335-29-Liam.Howlett@oracle.com Signed-off-by: Liam R. Howlett Cc: Alice Ryhl Cc: Andrew Ballance Cc: Arnd Bergmann Cc: Christian Kujau Cc: Geert Uytterhoeven Cc: Kuninori Morimoto Cc: Matthew Wilcox (Oracle) Cc: SeongJae Park Cc: Sidhartha Kumar Cc: Suren Baghdasaryan Cc: Vlastimil Babka Signed-off-by: Andrew Morton --- lib/maple_tree.c | 60 +++++++++++++++++++++++--------------------------------- 1 file changed, 25 insertions(+), 35 deletions(-) (limited to 'lib') diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 51ff311ff5b6..fe8424f4657d 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -1900,26 +1900,6 @@ static inline void mas_topiary_replace(struct ma_state *mas, mas_mat_destroy(mas, &subtrees); } -/* - * mas_wmb_replace() - Write memory barrier and replace - * @mas: The maple state - * @old_enode: The old maple encoded node that is being replaced. - * @new_height: The new height of the tree as a result of the operation - * - * Updates gap as necessary. - */ -static inline void mas_wmb_replace(struct ma_state *mas, - struct maple_enode *old_enode, unsigned char new_height) -{ - /* Insert the new data in the tree */ - mas_topiary_replace(mas, old_enode, new_height); - - if (mte_is_leaf(mas->node)) - return; - - mas_update_gap(mas); -} - /* * node_copy() - Copy from one node to another. * @@ -2086,6 +2066,28 @@ dead_node: return NULL; } +/* + * mas_wmb_replace() - Write memory barrier and replace + * @mas: The maple state + * @cp: The maple copy node + * + * Updates gap as necessary. + */ +static inline void mas_wmb_replace(struct ma_state *mas, struct maple_copy *cp) +{ + struct maple_enode *old_enode; + + old_enode = mas->node; + 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); + + mtree_range_walk(mas); +} + + /* * cp_leaf_init() - Initialize a maple_copy node for the leaf level of a * spanning store @@ -3044,7 +3046,6 @@ done: */ static void mas_wr_spanning_store(struct ma_wr_state *wr_mas) { - struct maple_enode *old_enode; struct maple_copy cp; struct ma_state *mas; struct ma_state sib; @@ -3112,10 +3113,7 @@ static void mas_wr_spanning_store(struct ma_wr_state *wr_mas) cp_data_write(&cp, mas); } while (spanning_ascend(&cp, mas, wr_mas, &r_wr_mas, &sib)); - old_enode = mas->node; - mas->node = mt_slot_locked(mas->tree, cp.slot, 0); - mas_wmb_replace(mas, old_enode, cp.height); - mtree_range_walk(mas); + mas_wmb_replace(mas, &cp); } /* @@ -3433,7 +3431,6 @@ static inline void split_data(struct maple_copy *cp, */ static void mas_wr_split(struct ma_wr_state *wr_mas) { - struct maple_enode *old_enode; struct ma_state parent; struct ma_state *mas; struct maple_copy cp; @@ -3454,10 +3451,7 @@ static void mas_wr_split(struct ma_wr_state *wr_mas) cp_data_write(&cp, mas); } while (split_ascend(&cp, wr_mas, &sib, &parent)); - old_enode = mas->node; - mas->node = mt_slot_locked(mas->tree, cp.slot, 0); - mas_wmb_replace(mas, old_enode, cp.height); - mtree_range_walk(mas); + mas_wmb_replace(mas, &cp); } /* @@ -3470,7 +3464,6 @@ static void mas_wr_split(struct ma_wr_state *wr_mas) */ static void mas_wr_rebalance(struct ma_wr_state *wr_mas) { - struct maple_enode *old_enode; struct ma_state parent; struct ma_state *mas; struct maple_copy cp; @@ -3501,10 +3494,7 @@ static void mas_wr_rebalance(struct ma_wr_state *wr_mas) cp_data_write(&cp, mas); } while (rebalance_ascend(&cp, wr_mas, &sib, &parent)); - old_enode = mas->node; - mas->node = mt_slot_locked(mas->tree, cp.slot, 0); - mas_wmb_replace(mas, old_enode, cp.height); - mtree_range_walk(mas); + mas_wmb_replace(mas, &cp); } /* -- cgit From b82f4c811e4d22b308dccf9f7b0a382b0105c190 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Fri, 30 Jan 2026 15:59:34 -0500 Subject: maple_tree: don't pass end to mas_wr_append() Figure out the end internally. This is necessary for future cleanups. Link: https://lkml.kernel.org/r/20260130205935.2559335-30-Liam.Howlett@oracle.com Signed-off-by: Liam R. Howlett Cc: Alice Ryhl Cc: Andrew Ballance Cc: Arnd Bergmann Cc: Christian Kujau Cc: Geert Uytterhoeven Cc: Kuninori Morimoto Cc: Matthew Wilcox (Oracle) Cc: SeongJae Park Cc: Sidhartha Kumar Cc: Suren Baghdasaryan Cc: Vlastimil Babka Signed-off-by: Andrew Morton --- lib/maple_tree.c | 7 +++---- 1 file changed, 3 insertions(+), 4 deletions(-) (limited to 'lib') diff --git a/lib/maple_tree.c b/lib/maple_tree.c index fe8424f4657d..46111912b26b 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -3309,18 +3309,17 @@ static inline unsigned char mas_wr_new_end(struct ma_wr_state *wr_mas) /* * mas_wr_append: Attempt to append * @wr_mas: the maple write state - * @new_end: The end of the node after the modification * * This is currently unsafe in rcu mode since the end of the node may be cached * by readers while the node contents may be updated which could result in * inaccurate information. */ -static inline void mas_wr_append(struct ma_wr_state *wr_mas, - unsigned char new_end) +static inline void mas_wr_append(struct ma_wr_state *wr_mas) { struct ma_state *mas = wr_mas->mas; void __rcu **slots; unsigned char end = mas->end; + unsigned char new_end = mas_wr_new_end(wr_mas); if (new_end < mt_pivots[wr_mas->type]) { wr_mas->pivots[new_end] = wr_mas->pivots[end]; @@ -3513,7 +3512,7 @@ static inline void mas_wr_store_entry(struct ma_wr_state *wr_mas) mas_update_gap(mas); break; case wr_append: - mas_wr_append(wr_mas, new_end); + mas_wr_append(wr_mas); break; case wr_slot_store: mas_wr_slot_store(wr_mas); -- cgit From 0e8cf9a31a8c3f996c48b633a673076d6997b093 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Fri, 30 Jan 2026 15:59:35 -0500 Subject: maple_tree: clean up mas_wr_node_store() The new_end does not need to be passed in as the data is already being checked. This allows for other areas to skip getting the node new_end in the calling function. The type was incorrectly void * instead of void __rcu *, which isn't an issue but is technically incorrect. Move the variable assignment to after the declarations to clean up the initial setup. Ensure there is something to copy before calling memcpy(). Link: https://lkml.kernel.org/r/20260130205935.2559335-31-Liam.Howlett@oracle.com Signed-off-by: Liam R. Howlett Cc: Alice Ryhl Cc: Andrew Ballance Cc: Arnd Bergmann Cc: Christian Kujau Cc: Geert Uytterhoeven Cc: Kuninori Morimoto Cc: Matthew Wilcox (Oracle) Cc: SeongJae Park Cc: Sidhartha Kumar Cc: Suren Baghdasaryan Cc: Vlastimil Babka Signed-off-by: Andrew Morton --- lib/maple_tree.c | 42 ++++++++++++++++++++++++++---------------- 1 file changed, 26 insertions(+), 16 deletions(-) (limited to 'lib') diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 46111912b26b..d18d7ed9ab67 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -3122,20 +3122,28 @@ static void mas_wr_spanning_store(struct ma_wr_state *wr_mas) * * Attempts to reuse the node, but may allocate. */ -static inline void mas_wr_node_store(struct ma_wr_state *wr_mas, - unsigned char new_end) +static inline void mas_wr_node_store(struct ma_wr_state *wr_mas) { - struct ma_state *mas = wr_mas->mas; - void __rcu **dst_slots; - unsigned long *dst_pivots; - unsigned char dst_offset, offset_end = wr_mas->offset_end; + unsigned char dst_offset, offset_end; + unsigned char copy_size, node_pivots; struct maple_node reuse, *newnode; - unsigned char copy_size, node_pivots = mt_pivots[wr_mas->type]; - bool in_rcu = mt_in_rcu(mas->tree); - unsigned char height = mas_mt_height(mas); + unsigned long *dst_pivots; + void __rcu **dst_slots; + unsigned char new_end; + struct ma_state *mas; + bool in_rcu; - if (mas->last == wr_mas->end_piv) + mas = wr_mas->mas; + trace_ma_op(TP_FCT, mas); + in_rcu = mt_in_rcu(mas->tree); + offset_end = wr_mas->offset_end; + node_pivots = mt_pivots[wr_mas->type]; + /* Assume last adds an entry */ + new_end = mas->end + 1 - offset_end + mas->offset; + if (mas->last == wr_mas->end_piv) { offset_end++; /* don't copy this offset */ + new_end--; + } /* set up node. */ if (in_rcu) { @@ -3149,13 +3157,16 @@ static inline void mas_wr_node_store(struct ma_wr_state *wr_mas, dst_pivots = ma_pivots(newnode, wr_mas->type); dst_slots = ma_slots(newnode, wr_mas->type); /* Copy from start to insert point */ - memcpy(dst_pivots, wr_mas->pivots, sizeof(unsigned long) * mas->offset); - memcpy(dst_slots, wr_mas->slots, sizeof(void *) * mas->offset); + if (mas->offset) { + memcpy(dst_pivots, wr_mas->pivots, sizeof(unsigned long) * mas->offset); + memcpy(dst_slots, wr_mas->slots, sizeof(void __rcu *) * mas->offset); + } /* Handle insert of new range starting after old range */ if (wr_mas->r_min < mas->index) { rcu_assign_pointer(dst_slots[mas->offset], wr_mas->content); dst_pivots[mas->offset++] = mas->index - 1; + new_end++; } /* Store the new entry and range end. */ @@ -3174,7 +3185,7 @@ static inline void mas_wr_node_store(struct ma_wr_state *wr_mas, /* Copy to the end of node if necessary. */ copy_size = mas->end - offset_end + 1; memcpy(dst_slots + dst_offset, wr_mas->slots + offset_end, - sizeof(void *) * copy_size); + sizeof(void __rcu *) * copy_size); memcpy(dst_pivots + dst_offset, wr_mas->pivots + offset_end, sizeof(unsigned long) * (copy_size - 1)); @@ -3187,7 +3198,7 @@ done: struct maple_enode *old_enode = mas->node; mas->node = mt_mk_node(newnode, wr_mas->type); - mas_replace_node(mas, old_enode, height); + mas_replace_node(mas, old_enode, mas_mt_height(mas)); } else { memcpy(wr_mas->node, newnode, sizeof(struct maple_node)); } @@ -3503,7 +3514,6 @@ static void mas_wr_rebalance(struct ma_wr_state *wr_mas) static inline void mas_wr_store_entry(struct ma_wr_state *wr_mas) { struct ma_state *mas = wr_mas->mas; - unsigned char new_end = mas_wr_new_end(wr_mas); switch (mas->store_type) { case wr_exact_fit: @@ -3518,7 +3528,7 @@ static inline void mas_wr_store_entry(struct ma_wr_state *wr_mas) mas_wr_slot_store(wr_mas); break; case wr_node_store: - mas_wr_node_store(wr_mas, new_end); + mas_wr_node_store(wr_mas); break; case wr_spanning_store: mas_wr_spanning_store(wr_mas); -- cgit From 32bc7fe4a6f4d359b6de96cbc106d2cac695154e Mon Sep 17 00:00:00 2001 From: "David Hildenbrand (Arm)" Date: Fri, 27 Feb 2026 21:08:43 +0100 Subject: mm: rename zap_vma_pages() to zap_vma() Let's rename it to an even simpler name. While at it, add some simplistic kernel doc. Link: https://lkml.kernel.org/r/20260227200848.114019-13-david@kernel.org Signed-off-by: David Hildenbrand (Arm) Reviewed-by: Lorenzo Stoakes (Oracle) Cc: Alexander Gordeev Cc: Alexei Starovoitov Cc: Alice Ryhl Cc: Andrii Nakryiko Cc: Andy Lutomirski Cc: Arnaldo Carvalho de Melo Cc: Arnd Bergmann Cc: Arve Cc: "Borislav Petkov (AMD)" Cc: Carlos Llamas Cc: Christian Borntraeger Cc: Christian Brauner Cc: Claudio Imbrenda Cc: Daniel Borkman Cc: Dave Airlie Cc: David Ahern Cc: David Rientjes Cc: David S. Miller Cc: Dimitri Sivanich Cc: Eric Dumazet Cc: Gerald Schaefer Cc: Greg Kroah-Hartman Cc: Hartley Sweeten Cc: Heiko Carstens Cc: Ian Abbott Cc: Ingo Molnar Cc: Jakub Kacinski Cc: Jani Nikula Cc: Jann Horn Cc: Janosch Frank Cc: Jarkko Sakkinen Cc: Jason Gunthorpe Cc: Jonas Lahtinen Cc: Leon Romanovsky Cc: Liam Howlett Cc: Madhavan Srinivasan Cc: Matthew Wilcox (Oracle) Cc: Michael Ellerman Cc: Michal Hocko Cc: Miguel Ojeda Cc: Mike Rapoport Cc: Namhyung kim Cc: Neal Cardwell Cc: Paolo Abeni Cc: Pedro Falcato Cc: Peter Zijlstra Cc: Rodrigo Vivi Cc: Shakeel Butt Cc: Suren Baghdasaryan Cc: Todd Kjos Cc: Tvrtko Ursulin Cc: Vasily Gorbik Cc: Vincenzo Frascino Signed-off-by: Andrew Morton --- arch/powerpc/platforms/book3s/vas-api.c | 2 +- arch/powerpc/platforms/pseries/vas.c | 2 +- include/linux/mm.h | 6 +++++- lib/vdso/datastore.c | 2 +- mm/page-writeback.c | 2 +- 5 files changed, 9 insertions(+), 5 deletions(-) (limited to 'lib') diff --git a/arch/powerpc/platforms/book3s/vas-api.c b/arch/powerpc/platforms/book3s/vas-api.c index ea4ffa63f043..e96d79db69fe 100644 --- a/arch/powerpc/platforms/book3s/vas-api.c +++ b/arch/powerpc/platforms/book3s/vas-api.c @@ -414,7 +414,7 @@ static vm_fault_t vas_mmap_fault(struct vm_fault *vmf) /* * When the LPAR lost credits due to core removal or during * migration, invalidate the existing mapping for the current - * paste addresses and set windows in-active (zap_vma_pages in + * paste addresses and set windows in-active (zap_vma() in * reconfig_close_windows()). * New mapping will be done later after migration or new credits * available. So continue to receive faults if the user space diff --git a/arch/powerpc/platforms/pseries/vas.c b/arch/powerpc/platforms/pseries/vas.c index ceb0a8788c0a..fa05f04364fe 100644 --- a/arch/powerpc/platforms/pseries/vas.c +++ b/arch/powerpc/platforms/pseries/vas.c @@ -807,7 +807,7 @@ static int reconfig_close_windows(struct vas_caps *vcap, int excess_creds, * is done before the original mmap() and after the ioctl. */ if (vma) - zap_vma_pages(vma); + zap_vma(vma); mutex_unlock(&task_ref->mmap_mutex); mmap_write_unlock(task_ref->mm); diff --git a/include/linux/mm.h b/include/linux/mm.h index 488a144c9161..60c13d40c65c 100644 --- a/include/linux/mm.h +++ b/include/linux/mm.h @@ -2806,7 +2806,11 @@ void zap_vma_ptes(struct vm_area_struct *vma, unsigned long address, unsigned long size); void zap_page_range_single(struct vm_area_struct *vma, unsigned long address, unsigned long size); -static inline void zap_vma_pages(struct vm_area_struct *vma) +/** + * zap_vma - zap all page table entries in a vma + * @vma: The vma to zap. + */ +static inline void zap_vma(struct vm_area_struct *vma) { zap_page_range_single(vma, vma->vm_start, vma->vm_end - vma->vm_start); } diff --git a/lib/vdso/datastore.c b/lib/vdso/datastore.c index a565c30c71a0..222c143aebf7 100644 --- a/lib/vdso/datastore.c +++ b/lib/vdso/datastore.c @@ -121,7 +121,7 @@ int vdso_join_timens(struct task_struct *task, struct time_namespace *ns) mmap_read_lock(mm); for_each_vma(vmi, vma) { if (vma_is_special_mapping(vma, &vdso_vvar_mapping)) - zap_vma_pages(vma); + zap_vma(vma); } mmap_read_unlock(mm); diff --git a/mm/page-writeback.c b/mm/page-writeback.c index 1009bb042ba4..8dc47b59ca18 100644 --- a/mm/page-writeback.c +++ b/mm/page-writeback.c @@ -2645,7 +2645,7 @@ void folio_account_cleaned(struct folio *folio, struct bdi_writeback *wb) * while this function is in progress, although it may have been truncated * before this function is called. Most callers have the folio locked. * A few have the folio blocked from truncation through other means (e.g. - * zap_vma_pages() has it mapped and is holding the page table lock). + * zap_vma() has it mapped and is holding the page table lock). * When called from mark_buffer_dirty(), the filesystem should hold a * reference to the buffer_head that is being marked dirty, which causes * try_to_free_buffers() to fail. -- cgit From d7651089939bf00fe033845e662905ce750b1f18 Mon Sep 17 00:00:00 2001 From: Arnd Bergmann Date: Fri, 6 Mar 2026 16:05:49 +0100 Subject: ubsan: turn off kmsan inside of ubsan instrumentation The structure initialization in the two type mismatch handling functions causes a call to __msan_memset() to be generated inside of a UACCESS block, which in turn leads to an objtool warning about possibly leaking uaccess-enabled state: lib/ubsan.o: warning: objtool: __ubsan_handle_type_mismatch+0xda: call to __msan_memset() with UACCESS enabled lib/ubsan.o: warning: objtool: __ubsan_handle_type_mismatch_v1+0xf4: call to __msan_memset() with UACCESS enabled Most likely __msan_memset() is safe to be called here and could be added to the uaccess_safe_builtin[] list of safe functions, but seeing that the ubsan file itself already has kasan, ubsan and kcsan disabled itself, it is probably a good idea to also turn off kmsan here, in particular this also avoids the risk of recursing between ubsan and kcsan checks in other functions of this file. I saw this happen while testing randconfig builds with clang-22, but did not try older versions, or attempt to see which kernel change introduced the warning. Link: https://lkml.kernel.org/r/20260306150613.350029-1-arnd@kernel.org Signed-off-by: Arnd Bergmann Acked-by: Andrey Ryabinin Cc: Kees Cook Cc: Marco Elver Cc: Andrey Konovalov Cc: Bill Wendling Cc: Justin Stitt Cc: Nathan Chancellor Cc: Peter Zijlstra Signed-off-by: Andrew Morton --- lib/Makefile | 1 + 1 file changed, 1 insertion(+) (limited to 'lib') diff --git a/lib/Makefile b/lib/Makefile index 1b9ee167517f..ce3ae929ae8c 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -307,6 +307,7 @@ obj-$(CONFIG_UBSAN) += ubsan.o UBSAN_SANITIZE_ubsan.o := n KASAN_SANITIZE_ubsan.o := n KCSAN_SANITIZE_ubsan.o := n +KMSAN_SANITIZE_ubsan.o := n CFLAGS_ubsan.o := -fno-stack-protector $(DISABLE_KSTACK_ERASE) obj-$(CONFIG_SBITMAP) += sbitmap.o -- cgit From d2fd4225d8de3b9dccf46a7a021869c65152a044 Mon Sep 17 00:00:00 2001 From: Arnd Bergmann Date: Mon, 23 Mar 2026 21:55:16 +0100 Subject: bug: avoid format attribute warning for clang as well Like gcc, clang-22 now also warns about a function that it incorrectly identifies as a printf-style format: lib/bug.c:190:22: error: diagnostic behavior may be improved by adding the 'format(printf, 1, 0)' attribute to the declaration of '__warn_printf' [-Werror,-Wmissing-format-attribute] 179 | static void __warn_printf(const char *fmt, struct pt_regs *regs) | __attribute__((format(printf, 1, 0))) 180 | { 181 | if (!fmt) 182 | return; 183 | 184 | #ifdef HAVE_ARCH_BUG_FORMAT_ARGS 185 | if (regs) { 186 | struct arch_va_list _args; 187 | va_list *args = __warn_args(&_args, regs); 188 | 189 | if (args) { 190 | vprintk(fmt, *args); | ^ Revert the change that added a gcc-specific workaround, and instead add the generic annotation that avoid the warning. Link: https://lkml.kernel.org/r/20260323205534.1284284-1-arnd@kernel.org Fixes: d36067d6ea00 ("bug: Hush suggest-attribute=format for __warn_printf()") Suggested-by: Andy Shevchenko Suggested-by: Brendan Jackman Link: https://lore.kernel.org/all/20251208141618.2805983-1-andriy.shevchenko@linux.intel.com/T/#u Signed-off-by: Arnd Bergmann Reviewed-by: Brendan Jackman Reviewed-by: Andy Shevchenko Cc: Bill Wendling Cc: Ingo Molnar Cc: Justin Stitt Cc: Nathan Chancellor Cc: Peter Zijlstra Signed-off-by: Andrew Morton --- lib/bug.c | 7 ++----- 1 file changed, 2 insertions(+), 5 deletions(-) (limited to 'lib') diff --git a/lib/bug.c b/lib/bug.c index 623c467a8b76..aab9e6a40c5f 100644 --- a/lib/bug.c +++ b/lib/bug.c @@ -173,10 +173,8 @@ struct bug_entry *find_bug(unsigned long bugaddr) return module_find_bug(bugaddr); } -__diag_push(); -__diag_ignore(GCC, all, "-Wsuggest-attribute=format", - "Not a valid __printf() conversion candidate."); -static void __warn_printf(const char *fmt, struct pt_regs *regs) +static __printf(1, 0) +void __warn_printf(const char *fmt, struct pt_regs *regs) { if (!fmt) return; @@ -195,7 +193,6 @@ static void __warn_printf(const char *fmt, struct pt_regs *regs) printk("%s", fmt); } -__diag_pop(); static enum bug_trap_type __report_bug(struct bug_entry *bug, unsigned long bugaddr, struct pt_regs *regs) { -- cgit