On Sun, Oct 20, 2024 at 05:55:10PM -0400, Liam R. Howlett wrote:
>* Wei Yang <richard.weiyang@xxxxxxxxx> [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@xxxxxxxxx>
>> CC: Liam R. Howlett <Liam.Howlett@xxxxxxxxxx>
>> CC: Sidhartha Kumar <sidhartha.kumar@xxxxxxxxxx>
>> CC: Lorenzo Stoakes <lorenzo.stoakes@xxxxxxxxxx>
>> ---
>> 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
