[PATCH 3/5] maple_tree: use vacant nodes to reduce worst case allocations

[Sidhartha Kumar]

On 11/15/24 2:52 AM, Wei Yang wrote:
> On Thu, Nov 14, 2024 at 12:05:22PM -0500, Sidhartha Kumar wrote:
>> In order to determine the store type for a maple tree operation, a walk
>> of the tree is done through mas_wr_walk(). This function descends the
>> tree until a spanning write is detected or we reach a leaf node. While
>> descending, keep track of the height at which we encounter a node with
>> available space. This is done by checking if mas->end is less than the
>> number of slots a given node type can fit.
>>
>> Now that the height of the vacant node is tracked, we can use the
>> difference between the height of the tree and the height of the vacant
>> node to know how many levels we will have to propagate creating new
>> nodes. Update mas_prealloc_calc() to consider the vacant height and
>> reduce the number of worst allocations.
>>
>> Rebalancing stores are not supported and fall back to using the full
>> height of the tree for allocations.
>>
>> Update preallocation testing assertions to take into account vacant
>> height.
>>
>> Signed-off-by: Sidhartha <sidhartha.kumar at oracle.com>
>> ---
>> include/linux/maple_tree.h       |  2 +
>> lib/maple_tree.c                 | 13 +++--
>> tools/testing/radix-tree/maple.c | 97 +++++++++++++++++++++++++++++---
>> 3 files changed, 100 insertions(+), 12 deletions(-)
>>
>> diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h
>> index cbbcd18d4186..7d777aa2d9ed 100644
>> --- a/include/linux/maple_tree.h
>> +++ b/include/linux/maple_tree.h
>> @@ -463,6 +463,7 @@ struct ma_wr_state {
>> 	void __rcu **slots;		/* mas->node->slots pointer */
>> 	void *entry;			/* The entry to write */
>> 	void *content;			/* The existing entry that is being overwritten */
>> +	unsigned char vacant_height;	/* Depth of lowest node with free space */
>                               ^^^           ^^^
> 
> Would this be a little misleading?
> 

Could you elaborate on how its misleading?

>> };
>>
>> #define mas_lock(mas)           spin_lock(&((mas)->tree->ma_lock))
>> @@ -498,6 +499,7 @@ struct ma_wr_state {
>> 		.mas = ma_state,					\
>> 		.content = NULL,					\
>> 		.entry = wr_entry,					\
>> +		.vacant_height = 0					\
>> 	}
>>
>> #define MA_TOPIARY(name, tree)						\
>> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
>> index 21289e350382..f14d70c171c2 100644
>> --- a/lib/maple_tree.c
>> +++ b/lib/maple_tree.c
>> @@ -3545,6 +3545,9 @@ static bool mas_wr_walk(struct ma_wr_state *wr_mas)
>> 		if (ma_is_leaf(wr_mas->type))
>> 			return true;
>>
>> +		if (mas->end < mt_slots[wr_mas->type] - 1)
>> +			wr_mas->vacant_height = mas->depth + 1;
> 
> For some cases in rebalance, we may split data into three parts, which means
> we need 2 extra vacant slot.
> 
> Maybe this check is not accurate?
> 

The triple split scenario which you are describing comes from the 
spanning store case not on the wr_rebalance case. There is a check 
before we set vacant height to return if is_span_wr() so I believe this 
is correct still.

>> +
>> 		mas_wr_walk_traverse(wr_mas);
>> 	}
>>
>> @@ -4159,7 +4162,9 @@ static inline void mas_wr_prealloc_setup(struct ma_wr_state *wr_mas)
>> static inline int mas_prealloc_calc(struct ma_wr_state *wr_mas, void *entry)
>> {
>> 	struct ma_state *mas = wr_mas->mas;
>> -	int ret = mas_mt_height(mas) * 3 + 1;
>> +	unsigned char height = mas_mt_height(mas);
>> +	int ret = height * 3 + 1;
>> +	unsigned char delta = height - wr_mas->vacant_height;
>>
>> 	switch (mas->store_type) {
>> 	case wr_invalid:
>> @@ -4177,13 +4182,13 @@ static inline int mas_prealloc_calc(struct ma_wr_state *wr_mas, void *entry)
>> 			ret = 0;
>> 		break;
>> 	case wr_spanning_store:
>> -		ret =  mas_mt_height(mas) * 3 + 1;
>> +		ret = delta * 3 + 1;
> 
> Hmm... I am afraid we need to put this patch after next one.
> 
> Without the change in next patch, we still need to go up the tree till root to
> rebalance.
> 

I think you are right here as mas_wr_spanning_store() calls 
mas_spanning_rebalance(), I'll switch the order of patch 3 and patch 4.

>> 		break;
>> 	case wr_split_store:
>> -		ret =  mas_mt_height(mas) * 2 + 1;
>> +		ret = delta * 2 + 1;
>> 		break;
>> 	case wr_rebalance:
>> -		ret =  mas_mt_height(mas) * 2 - 1;
>> +		ret = height * 2 + 1;
> 
> Looks current calculation is not correct?
> If so, do we need to have a fix to be backported?
> 

This was a typo, it can remain as height * 2 -1.

Thanks for taking a look,
Sidhartha Kumar

>