[PATCH v2 4/5] maple_tree: refine mas_root_expand() on storing NULL

[Wei Yang]

On Thu, Oct 17, 2024 at 10:10:20AM -0400, Liam R. Howlett wrote:
>* Wei Yang <richard.weiyang at gmail.com> [241017 09:46]:
>> Currently, when storing NULL on mas_root_expand(), the behavior could be
>> improved.
>> 
>> For example possible cases are:
>> 
>>   * store NULL at any range result a new node
>>   * store NULL at range [m, n] where m > 0 to a single entry tree result
>>     a new node with range [m, n] set to NULL
>>   * store NULL at range [m, n] where m > 0 to an empty tree result
>>     consecutive NULL slot
>> 
>> This patch tries to improve in:
>> 
>>   * memory efficient by setting to empty tree instead of using a node
>>   * remove the possibility of consecutive NULL slot which will prohibit
>>     extended null in later operation
>> 
>> 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 | 18 ++++++++++++++++++
>>  1 file changed, 18 insertions(+)
>> 
>> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
>> index a90c29156fe2..15d2124acc36 100644
>> --- a/lib/maple_tree.c
>> +++ b/lib/maple_tree.c
>> @@ -3335,6 +3335,24 @@ static inline void mas_root_expand(struct ma_state *mas, void *entry)
>>  	unsigned long *pivots;
>>  	int slot = 0;
>>  
>> +	if (!entry) {
>> +		/*
>> +		 * We come here in two cases:
>> +		 * 1. This is an empty tree
>> +		 * 2. This is a single entry tree with range [0, 0]
>> +		 *
>> +		 * If this is an empty tree, the result should still be an
>> +		 * empty tree no matter what the range is.
>> +		 *
>> +		 * If this is a single entry tree, we should set it to an
>> +		 * empty tree if the range cover [0, 0]. Otherwise, we don't
>> +		 * need to change it.
>> +		 */
>> +		if (!mas->index && contents)
>> +			rcu_assign_pointer(mas->tree->ma_root, NULL);
>> +		return;
>> +	}
>> +
>
>This fix should be done in mas_store_root(), which will probably reduce
>or remove your lengthy comment.
>
>mas_root_expand() should... expand the root, and this isn't what is
>happening now.
>

Right, will move it.

Thanks

>>  	node = mas_pop_node(mas);
>>  	pivots = ma_pivots(node, type);
>>  	slots = ma_slots(node, type);
>> -- 
>> 2.34.1
>> 

-- 
Wei Yang
Help you, Help me