* Sidhartha Kumar <sidhartha.kumar@xxxxxxxxxx> [250221 11:36]:
> In order to determine the store type for a maple tree operation, a walk
> of the tree is done through mas_wr_walk(). This function descends the
> tree until a spanning write is detected or we reach a leaf node. While
> descending, keep track of the height at which we encounter a node with
> available space. This is done by checking if mas->end is less than the
> number of slots a given node type can fit.
>
> Now that the height of the vacant node is tracked, we can use the
> difference between the height of the tree and the height of the vacant
> node to know how many levels we will have to propagate creating new
> nodes. Update mas_prealloc_calc() to consider the vacant height and
> reduce the number of worst-case allocations.
>
> Rebalancing and spanning stores are not supported and fall back to using
> the full height of the tree for allocations.
>
> Update preallocation testing assertions to take into account vacant
> height.
>
> Signed-off-by: Sidhartha <sidhartha.kumar@xxxxxxxxxx>
> ---
> include/linux/maple_tree.h | 2 +
> lib/maple_tree.c | 13 ++--
> tools/testing/radix-tree/maple.c | 102 ++++++++++++++++++++++++++++---
> 3 files changed, 105 insertions(+), 12 deletions(-)
>
> diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h
> index cbbcd18d4186..7d777aa2d9ed 100644
> --- a/include/linux/maple_tree.h
> +++ b/include/linux/maple_tree.h
> @@ -463,6 +463,7 @@ struct ma_wr_state {
> void __rcu **slots; /* mas->node->slots pointer */
> void *entry; /* The entry to write */
> void *content; /* The existing entry that is being overwritten */
> + unsigned char vacant_height; /* Height of lowest node with free space */
> };
>
> #define mas_lock(mas) spin_lock(&((mas)->tree->ma_lock))
> @@ -498,6 +499,7 @@ struct ma_wr_state {
> .mas = ma_state, \
> .content = NULL, \
> .entry = wr_entry, \
> + .vacant_height = 0 \
> }
>
> #define MA_TOPIARY(name, tree) \
> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> index d7dac3119748..ef71af0529f4 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -3542,6 +3542,9 @@ static bool mas_wr_walk(struct ma_wr_state *wr_mas)
> if (ma_is_leaf(wr_mas->type))
> return true;
>
> + if (mas->end < mt_slots[wr_mas->type] - 1)
> + wr_mas->vacant_height = mas->depth + 1;
> +
> mas_wr_walk_traverse(wr_mas);
> }
>
> @@ -4157,7 +4160,9 @@ static inline void mas_wr_prealloc_setup(struct ma_wr_state *wr_mas)
> static inline int mas_prealloc_calc(struct ma_wr_state *wr_mas, void *entry)
> {
> struct ma_state *mas = wr_mas->mas;
> - int ret = mas_mt_height(mas) * 3 + 1;
> + unsigned char height = mas_mt_height(mas);
> + int ret = height * 3 + 1;
> + unsigned char delta = height - wr_mas->vacant_height;
>
> switch (mas->store_type) {
> case wr_invalid:
> @@ -4175,13 +4180,13 @@ static inline int mas_prealloc_calc(struct ma_wr_state *wr_mas, void *entry)
> ret = 0;
> break;
> case wr_spanning_store:
> - ret = mas_mt_height(mas) * 3 + 1;
> + ret = height * 3 + 1;
ret is already height * 3 + 1, you could add a WARN_ON_ONCE or such to
ensure that's the case here and it's not missed in updates to the code.
> break;
> case wr_split_store:
> - ret = mas_mt_height(mas) * 2 + 1;
> + ret = delta * 2 + 1;
> break;
> case wr_rebalance:
> - ret = mas_mt_height(mas) * 2 - 1;
> + ret = height * 2 + 1;
> break;
> case wr_node_store:
> ret = mt_in_rcu(mas->tree) ? 1 : 0;
> diff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/maple.c
> index bc30050227fd..d22c1008dffe 100644
> --- a/tools/testing/radix-tree/maple.c
> +++ b/tools/testing/radix-tree/maple.c
> @@ -35475,12 +35475,85 @@ static void check_dfs_preorder(struct maple_tree *mt)
> }
> /* End of depth first search tests */
>
> +/* same implementation as mas_is_span_wr() in lib/maple_tree.c */
Is this needed then? At the start of this file we have:
#include "../../../lib/maple_tree.c" so I would think you could use the
one already defined?
> +static bool is_span_wr(struct ma_state *mas, unsigned long r_max,
> + enum maple_type type, void *entry)
> +{
> + unsigned long max = r_max;
> + unsigned long last = mas->last;
> +
> + /* Contained in this pivot, fast path */
> + if (last < max)
> + return false;
> +
> + if (ma_is_leaf(type)) {
> + max = mas->max;
> + if (last < max)
> + return false;
> + }
> +
> + if (last == max) {
> + /*
> + * The last entry of leaf node cannot be NULL unless it is the
> + * rightmost node (writing ULONG_MAX), otherwise it spans slots.
> + */
> + if (entry || last == ULONG_MAX)
> + return false;
> + }
> +
> + return true;
> +}
> +
> +/* get height of the lowest non-leaf node with free space */
> +static unsigned char get_vacant_height(struct ma_state *mas, void *entry)
> +{
> + char vacant_height = 0;
> + enum maple_type type;
> + unsigned long *pivots;
> + unsigned long min = 0;
> + unsigned long max = ULONG_MAX;
> +
> + /* start traversal */
> + mas_reset(mas);
> + mas_start(mas);
> + if (!xa_is_node(mas_root(mas)))
> + return 0;
> +
> + type = mte_node_type(mas->node);
> + while (!ma_is_leaf(type)) {
> + mas_node_walk(mas, mte_to_node(mas->node), type, &min, &max);
> + mas->end = mas_data_end(mas);
> + pivots = ma_pivots(mte_to_node(mas->node), type);
> +
> + if (pivots) {
> + if (mas->offset)
> + min = pivots[mas->offset - 1];
> + if (mas->offset < mas->end)
> + max = pivots[mas->offset];
> + }
> +
> + /* detect spanning write */
> + if (is_span_wr(mas, max, type, entry))
> + break;
> +
> + if (mas->end < mt_slot_count(mas->node) - 1)
> + vacant_height = mas->depth + 1;
> +
> + mas_descend(mas);
> + type = mte_node_type(mas->node);
> + mas->depth++;
> + }
> +
> + return vacant_height;
> +}
> +
> /* Preallocation testing */
> static noinline void __init check_prealloc(struct maple_tree *mt)
> {
> unsigned long i, max = 100;
> unsigned long allocated;
> unsigned char height;
> + unsigned char vacant_height;
> struct maple_node *mn;
> void *ptr = check_prealloc;
> MA_STATE(mas, mt, 10, 20);
> @@ -35494,8 +35567,9 @@ static noinline void __init check_prealloc(struct maple_tree *mt)
> MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0);
> allocated = mas_allocated(&mas);
> height = mas_mt_height(&mas);
> + vacant_height = get_vacant_height(&mas, ptr);
> MT_BUG_ON(mt, allocated == 0);
> - MT_BUG_ON(mt, allocated != 1 + height * 3);
> + MT_BUG_ON(mt, allocated != 1 + (height - vacant_height) * 3);
> mas_destroy(&mas);
> allocated = mas_allocated(&mas);
> MT_BUG_ON(mt, allocated != 0);
> @@ -35503,8 +35577,9 @@ static noinline void __init check_prealloc(struct maple_tree *mt)
> MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0);
> allocated = mas_allocated(&mas);
> height = mas_mt_height(&mas);
> + vacant_height = get_vacant_height(&mas, ptr);
> MT_BUG_ON(mt, allocated == 0);
> - MT_BUG_ON(mt, allocated != 1 + height * 3);
> + MT_BUG_ON(mt, allocated != 1 + (height - vacant_height) * 3);
> MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0);
> mas_destroy(&mas);
> allocated = mas_allocated(&mas);
> @@ -35514,7 +35589,8 @@ static noinline void __init check_prealloc(struct maple_tree *mt)
> MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0);
> allocated = mas_allocated(&mas);
> height = mas_mt_height(&mas);
> - MT_BUG_ON(mt, allocated != 1 + height * 3);
> + vacant_height = get_vacant_height(&mas, ptr);
> + MT_BUG_ON(mt, allocated != 1 + (height - vacant_height) * 3);
> mn = mas_pop_node(&mas);
> MT_BUG_ON(mt, mas_allocated(&mas) != allocated - 1);
> mn->parent = ma_parent_ptr(mn);
> @@ -35527,7 +35603,8 @@ static noinline void __init check_prealloc(struct maple_tree *mt)
> MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0);
> allocated = mas_allocated(&mas);
> height = mas_mt_height(&mas);
> - MT_BUG_ON(mt, allocated != 1 + height * 3);
> + vacant_height = get_vacant_height(&mas, ptr);
> + MT_BUG_ON(mt, allocated != 1 + (height - vacant_height) * 3);
> mn = mas_pop_node(&mas);
> MT_BUG_ON(mt, mas_allocated(&mas) != allocated - 1);
> MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0);
> @@ -35540,7 +35617,8 @@ static noinline void __init check_prealloc(struct maple_tree *mt)
> MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0);
> allocated = mas_allocated(&mas);
> height = mas_mt_height(&mas);
> - MT_BUG_ON(mt, allocated != 1 + height * 3);
> + vacant_height = get_vacant_height(&mas, ptr);
> + MT_BUG_ON(mt, allocated != 1 + (height - vacant_height) * 3);
> mn = mas_pop_node(&mas);
> MT_BUG_ON(mt, mas_allocated(&mas) != allocated - 1);
> mas_push_node(&mas, mn);
> @@ -35553,7 +35631,8 @@ static noinline void __init check_prealloc(struct maple_tree *mt)
> MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0);
> allocated = mas_allocated(&mas);
> height = mas_mt_height(&mas);
> - MT_BUG_ON(mt, allocated != 1 + height * 3);
> + vacant_height = get_vacant_height(&mas, ptr);
> + MT_BUG_ON(mt, allocated != 1 + (height - vacant_height) * 3);
> mas_store_prealloc(&mas, ptr);
> MT_BUG_ON(mt, mas_allocated(&mas) != 0);
>
> @@ -35578,7 +35657,8 @@ static noinline void __init check_prealloc(struct maple_tree *mt)
> MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0);
> allocated = mas_allocated(&mas);
> height = mas_mt_height(&mas);
> - MT_BUG_ON(mt, allocated != 1 + height * 2);
> + vacant_height = get_vacant_height(&mas, ptr);
> + MT_BUG_ON(mt, allocated != 1 + (height - vacant_height) * 2);
> mas_store_prealloc(&mas, ptr);
> MT_BUG_ON(mt, mas_allocated(&mas) != 0);
> mt_set_non_kernel(1);
> @@ -35595,8 +35675,14 @@ static noinline void __init check_prealloc(struct maple_tree *mt)
> MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0);
> allocated = mas_allocated(&mas);
> height = mas_mt_height(&mas);
> + vacant_height = get_vacant_height(&mas, ptr);
> MT_BUG_ON(mt, allocated == 0);
> - MT_BUG_ON(mt, allocated != 1 + height * 3);
> + /*
> + * vacant height cannot be used to compute the number of nodes needed
> + * as the root contains two entries which means it is on the verge of
> + * insufficiency. The worst case full height of the tree is needed.
> + */
> + MT_BUG_ON(mt, allocated != height * 3 + 1);
> mas_store_prealloc(&mas, ptr);
> MT_BUG_ON(mt, mas_allocated(&mas) != 0);
> mas_set_range(&mas, 0, 200);
> --
> 2.43.0
>
