| 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: <adwnvy44e3x52u2f2qng2ltkvimjlibdt4n4hk3ws7w7rxuqou@jjunrlaqnwam>
Date: Tue, 25 Feb 2025 10:39:58 -0500
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,
richard.weiyang@...il.com
Subject: Re: [PATCH v2 2/6] maple_tree: use height and depth consistently
* Sidhartha Kumar <sidhartha.kumar@...cle.com> [250221 11:36]:
> For the maple tree, the root node is defined to have a depth of 0 with a
> height of 1. Each level down from the node, these values are incremented
> by 1. Various code paths define a root with depth 1 which is inconsisent
> with the definition. Modify the code to be consistent with this
> definition.
>
> Signed-off-by: Sidhartha Kumar <sidhartha.kumar@...cle.com>
> ---
> lib/maple_tree.c | 85 +++++++++++++++++++++++++-----------------------
> 1 file changed, 45 insertions(+), 40 deletions(-)
>
> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> index 0410e13a099e..d7dac3119748 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -211,14 +211,14 @@ static void ma_free_rcu(struct maple_node *node)
> call_rcu(&node->rcu, mt_free_rcu);
> }
>
> -static void mas_set_height(struct ma_state *mas)
> +static void mt_set_height(struct maple_tree *mt, unsigned char height)
> {
> - unsigned int new_flags = mas->tree->ma_flags;
> + unsigned int new_flags = mt->ma_flags;
>
> new_flags &= ~MT_FLAGS_HEIGHT_MASK;
> - MAS_BUG_ON(mas, mas->depth > MAPLE_HEIGHT_MAX);
> - new_flags |= mas->depth << MT_FLAGS_HEIGHT_OFFSET;
> - mas->tree->ma_flags = new_flags;
> + MT_BUG_ON(mt, height > MAPLE_HEIGHT_MAX);
> + new_flags |= height << MT_FLAGS_HEIGHT_OFFSET;
> + mt->ma_flags = new_flags;
> }
>
> static unsigned int mas_mt_height(struct ma_state *mas)
> @@ -1375,7 +1375,7 @@ static inline struct maple_enode *mas_start(struct ma_state *mas)
> root = mas_root(mas);
> /* Tree with nodes */
> if (likely(xa_is_node(root))) {
> - mas->depth = 1;
> + mas->depth = 0;
> mas->status = ma_active;
> mas->node = mte_safe_root(root);
> mas->offset = 0;
> @@ -1716,9 +1716,10 @@ static inline void mas_adopt_children(struct ma_state *mas,
> * node as dead.
> * @mas: the maple state with the new node
> * @old_enode: The old maple encoded node to replace.
> + * @new_height: if we are inserting a root node, update the height of the tree
> */
> static inline void mas_put_in_tree(struct ma_state *mas,
> - struct maple_enode *old_enode)
> + struct maple_enode *old_enode, char new_height)
> __must_hold(mas->tree->ma_lock)
> {
> unsigned char offset;
> @@ -1727,7 +1728,7 @@ static inline void mas_put_in_tree(struct ma_state *mas,
> if (mte_is_root(mas->node)) {
> mas_mn(mas)->parent = ma_parent_ptr(mas_tree_parent(mas));
> rcu_assign_pointer(mas->tree->ma_root, mte_mk_root(mas->node));
> - mas_set_height(mas);
> + mt_set_height(mas->tree, new_height);
> } else {
>
> offset = mte_parent_slot(mas->node);
> @@ -1747,10 +1748,10 @@ static inline void mas_put_in_tree(struct ma_state *mas,
> * @old_enode: The old maple encoded node.
> */
> static inline void mas_replace_node(struct ma_state *mas,
> - struct maple_enode *old_enode)
> + struct maple_enode *old_enode, unsigned char new_height)
> __must_hold(mas->tree->ma_lock)
> {
> - mas_put_in_tree(mas, old_enode);
> + mas_put_in_tree(mas, old_enode, new_height);
> mas_free(mas, old_enode);
> }
>
> @@ -2543,7 +2544,7 @@ static inline void mas_topiary_node(struct ma_state *mas,
> *
> */
> static inline void mas_topiary_replace(struct ma_state *mas,
> - struct maple_enode *old_enode)
> + struct maple_enode *old_enode, unsigned char new_height)
> {
> struct ma_state tmp[3], tmp_next[3];
> MA_TOPIARY(subtrees, mas->tree);
> @@ -2551,7 +2552,7 @@ static inline void mas_topiary_replace(struct ma_state *mas,
> int i, n;
>
> /* Place data in tree & then mark node as old */
> - mas_put_in_tree(mas, old_enode);
> + mas_put_in_tree(mas, old_enode, new_height);
>
> /* Update the parent pointers in the tree */
> tmp[0] = *mas;
> @@ -2639,10 +2640,10 @@ static inline void mas_topiary_replace(struct ma_state *mas,
> * Updates gap as necessary.
> */
> static inline void mas_wmb_replace(struct ma_state *mas,
> - struct maple_enode *old_enode)
> + struct maple_enode *old_enode, unsigned char new_height)
> {
> /* Insert the new data in the tree */
> - mas_topiary_replace(mas, old_enode);
> + mas_topiary_replace(mas, old_enode, new_height);
>
> if (mte_is_leaf(mas->node))
> return;
> @@ -2828,6 +2829,7 @@ static void mas_spanning_rebalance(struct ma_state *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;
>
> @@ -2877,7 +2879,7 @@ static void mas_spanning_rebalance(struct ma_state *mas,
> */
> memset(mast->bn, 0, sizeof(struct maple_big_node));
> mast->bn->type = mte_node_type(left);
> - l_mas.depth++;
> + new_height++;
>
> /* Root already stored in l->node. */
> if (mas_is_root_limits(mast->l))
> @@ -2901,8 +2903,10 @@ static void mas_spanning_rebalance(struct ma_state *mas,
> continue;
>
> /* May be a new root stored in mast->bn */
> - if (mas_is_root_limits(mast->orig_l))
> + if (mas_is_root_limits(mast->orig_l)) {
> + new_height++;
> break;
> + }
>
> mast_spanning_rebalance(mast);
>
> @@ -2913,7 +2917,7 @@ static void mas_spanning_rebalance(struct ma_state *mas,
>
> l_mas.node = mt_mk_node(ma_mnode_ptr(mas_pop_node(mas)),
> mte_node_type(mast->orig_l->node));
> - l_mas.depth++;
> +
> mab_mas_cp(mast->bn, 0, mt_slots[mast->bn->type] - 1, &l_mas, true);
> mas_set_parent(mas, left, l_mas.node, slot);
> if (middle)
> @@ -2937,7 +2941,7 @@ static void mas_spanning_rebalance(struct ma_state *mas,
> mas->min = l_mas.min;
> mas->max = l_mas.max;
> mas->offset = l_mas.offset;
> - mas_wmb_replace(mas, old_enode);
> + mas_wmb_replace(mas, old_enode, new_height);
> mtree_range_walk(mas);
> return;
> }
> @@ -3013,6 +3017,7 @@ static inline void mas_destroy_rebalance(struct ma_state *mas, unsigned char end
> void __rcu **l_slots, **slots;
> unsigned long *l_pivs, *pivs, gap;
> bool in_rcu = mt_in_rcu(mas->tree);
> + unsigned char new_height = mas_mt_height(mas);
>
> MA_STATE(l_mas, mas->tree, mas->index, mas->last);
>
> @@ -3107,7 +3112,7 @@ static inline void mas_destroy_rebalance(struct ma_state *mas, unsigned char end
> mas_ascend(mas);
>
> if (in_rcu) {
> - mas_replace_node(mas, old_eparent);
> + mas_replace_node(mas, old_eparent, new_height);
> mas_adopt_children(mas, mas->node);
> }
>
> @@ -3118,10 +3123,9 @@ static inline void mas_destroy_rebalance(struct ma_state *mas, unsigned char end
> * mas_split_final_node() - Split the final node in a subtree operation.
> * @mast: the maple subtree state
> * @mas: The maple state
> - * @height: The height of the tree in case it's a new root.
> */
> static inline void mas_split_final_node(struct maple_subtree_state *mast,
> - struct ma_state *mas, int height)
> + struct ma_state *mas)
> {
> struct maple_enode *ancestor;
>
> @@ -3130,7 +3134,6 @@ static inline void mas_split_final_node(struct maple_subtree_state *mast,
> mast->bn->type = maple_arange_64;
> else
> mast->bn->type = maple_range_64;
> - mas->depth = height;
> }
> /*
> * Only a single node is used here, could be root.
> @@ -3153,8 +3156,7 @@ static inline void mas_split_final_node(struct maple_subtree_state *mast,
> * @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)
> + struct ma_state *mas, unsigned char skip, int *height)
Update the argument list in the comments?
> {
> bool cp = true;
> unsigned char split;
> @@ -3226,7 +3228,7 @@ static inline void mast_split_data(struct maple_subtree_state *mast,
> *
> * Return: True if pushed, false otherwise.
> */
> -static inline bool mas_push_data(struct ma_state *mas, int height,
> +static inline bool mas_push_data(struct ma_state *mas, int *height,
> struct maple_subtree_state *mast, bool left)
Update the argument list in the comments?
> {
> unsigned char slot_total = mast->bn->b_end;
> @@ -3283,8 +3285,8 @@ static inline bool mas_push_data(struct ma_state *mas, int height,
> mast->orig_l->offset += end + 1;
>
> mast_split_data(mast, mas, split);
> - mast_fill_bnode(mast, mas, 2);
> - mas_split_final_node(mast, mas, height + 1);
> + mast_fill_bnode(mast, mas, 2, height);
> + mas_split_final_node(mast, mas);
> return true;
> }
>
> @@ -3297,6 +3299,7 @@ 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;
>
> @@ -3323,7 +3326,7 @@ static void mas_split(struct ma_state *mas, struct maple_big_node *b_node)
> MA_STATE(prev_r_mas, mas->tree, mas->index, mas->last);
>
> trace_ma_op(__func__, mas);
> - mas->depth = mas_mt_height(mas);
> + mas->depth = orig_height;
Why is this still needed? It might be worth adding a comment or
removing it?
>
> mast.l = &l_mas;
> mast.r = &r_mas;
> @@ -3333,7 +3336,7 @@ static void mas_split(struct ma_state *mas, struct maple_big_node *b_node)
>
> while (height++ <= mas->depth) {
> if (mt_slots[b_node->type] > b_node->b_end) {
> - mas_split_final_node(&mast, mas, height);
> + mas_split_final_node(&mast, mas);
> break;
> }
>
> @@ -3348,11 +3351,15 @@ static void mas_split(struct ma_state *mas, struct maple_big_node *b_node)
> * is a significant savings.
> */
> /* Try to push left. */
> - if (mas_push_data(mas, height, &mast, true))
> + if (mas_push_data(mas, &height, &mast, true)) {
> + height++;
> break;
> + }
> /* Try to push right. */
> - if (mas_push_data(mas, height, &mast, false))
> + if (mas_push_data(mas, &height, &mast, false)) {
> + height++;
> break;
> + }
>
> split = mab_calc_split(mas, b_node, &mid_split);
> mast_split_data(&mast, mas, split);
> @@ -3361,7 +3368,7 @@ static void mas_split(struct ma_state *mas, struct maple_big_node *b_node)
> * r->max.
> */
> mast.r->max = mas->max;
> - mast_fill_bnode(&mast, mas, 1);
> + mast_fill_bnode(&mast, mas, 1, &height);
> prev_l_mas = *mast.l;
> prev_r_mas = *mast.r;
> }
> @@ -3369,7 +3376,7 @@ static void mas_split(struct ma_state *mas, struct maple_big_node *b_node)
> /* Set the original node as dead */
> old = mas->node;
> mas->node = l_mas.node;
> - mas_wmb_replace(mas, old);
> + mas_wmb_replace(mas, old, height);
> mtree_range_walk(mas);
> return;
> }
> @@ -3428,8 +3435,7 @@ static inline void mas_root_expand(struct ma_state *mas, void *entry)
> if (mas->last != ULONG_MAX)
> pivots[++slot] = ULONG_MAX;
>
> - mas->depth = 1;
> - mas_set_height(mas);
> + mt_set_height(mas->tree, 1);
> 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));
> @@ -3673,8 +3679,7 @@ static inline void mas_new_root(struct ma_state *mas, void *entry)
> WARN_ON_ONCE(mas->index || mas->last != ULONG_MAX);
>
> if (!entry) {
> - mas->depth = 0;
> - mas_set_height(mas);
> + mt_set_height(mas->tree, 0);
> rcu_assign_pointer(mas->tree->ma_root, entry);
> mas->status = ma_start;
> goto done;
> @@ -3688,8 +3693,7 @@ static inline void mas_new_root(struct ma_state *mas, void *entry)
> mas->status = ma_active;
> rcu_assign_pointer(slots[0], entry);
> pivots[0] = mas->last;
> - mas->depth = 1;
> - mas_set_height(mas);
> + mt_set_height(mas->tree, 1);
> rcu_assign_pointer(mas->tree->ma_root, mte_mk_root(mas->node));
>
> done:
> @@ -3808,6 +3812,7 @@ static inline void mas_wr_node_store(struct ma_wr_state *wr_mas,
> 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);
>
> if (mas->last == wr_mas->end_piv)
> offset_end++; /* don't copy this offset */
> @@ -3864,7 +3869,7 @@ static inline void mas_wr_node_store(struct ma_wr_state *wr_mas,
> struct maple_enode *old_enode = mas->node;
>
> mas->node = mt_mk_node(newnode, wr_mas->type);
> - mas_replace_node(mas, old_enode);
> + mas_replace_node(mas, old_enode, height);
> } else {
> memcpy(wr_mas->node, newnode, sizeof(struct maple_node));
> }
> --
> 2.43.0
>
Powered by blists - more mailing lists