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

[Wei Yang]

On Sun, Oct 20, 2024 at 05:55:10PM -0400, Liam R. Howlett wrote:
>* Wei Yang <richard.weiyang at 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.
>

Thanks, I will put the explanation later.

>> 
>> 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?
>

Too much room? Or too much empty room? 

I may missed here.

>> 
>> 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.

Sure, will remote this part.

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

Per my understanding, a jitter is a removal which cause a deficient node which
is just created from a split, right?

>
>> 
>> Signed-off-by: Wei Yang <richard.weiyang at gmail.com>
>> CC: Liam R. Howlett <Liam.Howlett at Oracle.com>
>> CC: Sidhartha Kumar <sidhartha.kumar at oracle.com>
>> CC: Lorenzo Stoakes <lorenzo.stoakes at 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
>> 

-- 
Wei Yang
Help you, Help me