Re: [PATCH 1/4] maple_tree: current split may result in deficient node

["Liam R. Howlett" <Liam.Howlett@oracle.com>]

* Wei Yang <richard.weiyang@gmail.com> [241019 22:46]:
> Current split would result in deficient node in rare case.
> 
> For example:
> 
> 	mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE)
> 	for (count = 0; count < 10; count++) {
> 		mas_set(&mas, count);
> 		mas_store(&mas, xa_mk_value(count));
> 	}
> 
> 	for (count = 20; count < 39; count++) {
> 		mas_set(&mas, count);
> 		mas_store(&mas, xa_mk_value(count));
> 	}
> 
> 	for (count = 10; count < 12; count++) {
> 		mas_set(&mas, count);
> 		mas_store(&mas, xa_mk_value(count));
> 	}
> 	mt_validate(mt);
> 
> The validation would report deficient node.

I think you can explain it better than this?

If we fill a left node with the right node being already full, the split
of the left node will result in the new middle node being insufficient.

> 
> The reason is we don't leave enough room for the right node.

The reason is we don't leave enough data for the node on the right of
the split.  The node on the right has too much room from what I see?

> 
> The deficient check is (end < mt_min_slot[]), which means a node must
> have at least (mt_min_slot[] + 1) number of data. The right node's index
> range is [split + 1, b_end], which means the number of data in right
> node is (b_end - (split + 1) + 1) = (b_end - split).
> 
> Then the check between the number of data and (mt_min_slot[] + 1) is
> (b_end - split) > (mt_min_slot[] + 1), which leads to
> (b_end - split - 1) > (mt_min_slot[]).

Don't state the code, it's stated below.

I am still concerned about jitter that this patch set may cause.

> 
> Signed-off-by: Wei Yang <richard.weiyang@gmail.com>
> CC: Liam R. Howlett <Liam.Howlett@Oracle.com>
> CC: Sidhartha Kumar <sidhartha.kumar@oracle.com>
> CC: Lorenzo Stoakes <lorenzo.stoakes@oracle.com>
> ---
>  lib/maple_tree.c | 4 ++--
>  1 file changed, 2 insertions(+), 2 deletions(-)
> 
> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> index 1205a5208cfe..894dc5e9436e 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -1831,7 +1831,7 @@ static inline int mab_no_null_split(struct maple_big_node *b_node,
>  		 * 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]))
> +		    (b_node->b_end - split - 1) > (mt_min_slots[b_node->type]))
>  			split++;
>  		else
>  			split--;
> @@ -1896,7 +1896,7 @@ static inline int mab_calc_split(struct ma_state *mas,
>  		 */
>  		while ((split < slot_count - 1) &&
>  		       ((bn->pivot[split] - min) < slot_count - 1) &&
> -		       (b_end - split > slot_min))
> +		       (b_end - split - 1 > slot_min))
>  			split++;
>  	}
>  
> -- 
> 2.34.1
>