| lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
|
Open Source and information security mailing list archives
| ||
|
Message-ID: <qs2hawh4p3knbajm3uxrw3esh26fbx4vm54ck5nvdg52fzn3tg@6f27fet5fh3w>
Date: Tue, 8 Apr 2025 14:08:46 -0400
From: "Liam R. Howlett" <Liam.Howlett@...cle.com>
To: Sidhartha Kumar <sidhartha.kumar@...cle.com>
Cc: linux-kernel@...r.kernel.org, maple-tree@...ts.infradead.org,
linux-mm@...ck.org, akpm@...ux-foundation.org, willy@...radead.org
Subject: Re: [PATCH v4 3/6] maple_tree: use vacant nodes to reduce worst case
allocations
* Sidhartha Kumar <sidhartha.kumar@...cle.com> [250407 14:41]:
> 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 Kumar <sidhartha.kumar@...cle.com>
Nit below in the comments.
Reviewed-by: Liam R. Howlett <Liam.Howlett@...cle.com>
> ---
> include/linux/maple_tree.h | 2 +
> lib/maple_tree.c | 13 ++++--
> tools/testing/radix-tree/maple.c | 79 ++++++++++++++++++++++++++++----
> 3 files changed, 82 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; /* Depth of lowest node with free space */
^^^^
"height" as it's depth + 1.
> };
>
> #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 236f0579ca53..203a1a529884 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -3539,6 +3539,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);
> }
>
> @@ -4154,7 +4157,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:
> @@ -4172,13 +4177,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;
> + WARN_ON_ONCE(ret != height * 3 + 1);
> 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 e0f8fabe8821..e37a3ab2e921 100644
> --- a/tools/testing/radix-tree/maple.c
> +++ b/tools/testing/radix-tree/maple.c
> @@ -35475,15 +35475,65 @@ static void check_dfs_preorder(struct maple_tree *mt)
> }
> /* End of depth first search tests */
>
> +/* get height of the lowest non-leaf node with free space */
> +static unsigned char get_vacant_height(struct ma_wr_state *wr_mas, void *entry)
> +{
> + struct ma_state *mas = wr_mas->mas;
> + char vacant_height = 0;
> + enum maple_type type;
> + unsigned long *pivots;
> + unsigned long min = 0;
> + unsigned long max = ULONG_MAX;
> + unsigned char offset;
> +
> + /* start traversal */
> + mas_reset(mas);
> + mas_start(mas);
> + if (!xa_is_node(mas_root(mas)))
> + return 0;
> +
> + type = mte_node_type(mas->node);
> + wr_mas->type = type;
> + while (!ma_is_leaf(type)) {
> + mas_node_walk(mas, mte_to_node(mas->node), type, &min, &max);
> + offset = mas->offset;
> + mas->end = mas_data_end(mas);
> + pivots = ma_pivots(mte_to_node(mas->node), type);
> +
> + if (pivots) {
> + if (offset)
> + min = pivots[mas->offset - 1];
> + if (offset < mas->end)
> + max = pivots[mas->offset];
> + }
> + wr_mas->r_max = offset < mas->end ? pivots[offset] : mas->max;
> +
> + /* detect spanning write */
> + if (mas_is_span_wr(wr_mas))
> + 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);
> + MA_WR_STATE(wr_mas, &mas, ptr);
>
> mt_set_non_kernel(1000);
> for (i = 0; i <= max; i++)
> @@ -35494,8 +35544,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(&wr_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 +35554,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(&wr_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 +35566,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(&wr_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 +35580,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(&wr_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 +35594,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(&wr_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 +35608,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(&wr_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 +35634,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(&wr_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 +35652,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(&wr_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
>
Powered by blists - more mailing lists