[PATCH 0/5] Track node vacancy to reduce worst case allocation counts

[Sidhartha Kumar]

On 11/19/24 3:59 AM, Wei Yang wrote:
> On Thu, Nov 14, 2024 at 04:39:00PM -0500, Sid Kumar wrote:
>>
>> On 11/14/24 12:05 PM, Sidhartha Kumar wrote:
> [...]
>>> ================ results =========================
>>> Bpftrace was used to profile the allocation path for requesting new maple
>>> nodes while running the ./mmap1_processes test from mmtests. The two paths
>>> for allocation are requests for a single node and the bulk allocation path.
>>> The histogram represents the number of calls to these paths and a shows the
>>> distribution of the number of nodes requested for the bulk allocation path.
>>>
>>>
>>> mm-unstable 11/13/24
>>> @bulk_alloc_req:
>>> [2, 4)                10 |@@@@@@@@@@@@@                                       |
>>> [4, 8)                38 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@|
>>> [8, 16)               19 |@@@@@@@@@@@@@@@@@@@@@@@@@@                          |
>>>
>>>
>>> mm-unstable 11/13/24 + this series
>>> @bulk_alloc_req:
>>> [2, 4)                 9 |@@@@@@@@@@                                          |
>>> [4, 8)                43 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@|
>>> [8, 16)               15 |@@@@@@@@@@@@@@@@@@                                  |
>>>
>>> We can see the worst case bulk allocations of [8,16) nodes are reduced after
>>> this series.
>>
>>From running the ./malloc1_threads test case we eliminate almost all bulk
>> allocation requests that
>>
>> fall between 8 and 16 nodes
>>
>> ./malloc1_threads -t 8 -s 100
>> mm-unstable + this series
>> @bulk_alloc_req:
>> [2, 4)                 2 |
>> |
>> [4, 8)              3381
>> |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@|
>> [8, 16)                2 |
>> |
>>
> 
> This is impressive. But I come up one thing not clear.
> 
> For mmap related code, we usually have the following usage:
> 
>    vma_iter_prealloc(vmi, vma);
>      mas_preallocate(vmi->mas, vma);
>        MA_WR_STATE(wr_mas, );
>        mas_wr_store_type(&wr_mas);       --- (1)
>    vma_iter_store(vmi, vma);
> 
> Locaton (1) is where we try to get a better estimation of allocations.
> The estimation is based on we walk down the tree and try to meet a proper
> node.
> 
> In mmap related code, we usually have already walked down the
> tree to leaf, by vma_find() or related iteration operation, and the mas.status
> is set to ma_active. To me, I don't expect mas_preallocate() would traverse
> the tree again.
> 
> But from your result, it seems most cases do traverse the tree again to get a
> more precise height.
> 
Hello,

 From looking at mas_wr_prealloc_setup(), when mas_is_active():
we reset in two scenarios:

	if (mas->last > mas->max)
		goto reset;

	if (wr_mas->entry)
		goto set_content;

	if (mte_is_leaf(mas->node) && mas->last == mas->max)
		goto reset;

it could be that this test case specifically hits these two cases. In 
testing brk() I did not see the same gains that this malloc test had so 
in that case we are probably not traversing the tree again as you say.

Thanks,
Sid


> Which part do you think I have missed?
> 
>>
>> mm-unstable
>> @bulk_alloc_req:
>> [2, 4)                 1 |
>> |
>> [4, 8)              1427 |@@@@@@@@@@@@@@@@@@@@@@@@@@
>> |
>> [8, 16)             2790
>> |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@|
>>
>>
>>>
>>> Sidhartha Kumar (5):
>>>     maple_tree: convert mas_prealloc_calc() to take in a maple write state
>>>     maple_tree: use height and depth consistently
>>>     maple_tree: use vacant nodes to reduce worst case allocations
>>>     maple_tree: break on convergence in mas_spanning_rebalance()
>>>     maple_tree: add sufficient height
>>>
>>>    include/linux/maple_tree.h       |   4 +
>>>    lib/maple_tree.c                 |  89 +++++++++++++---------
>>>    tools/testing/radix-tree/maple.c | 125 +++++++++++++++++++++++++++++--
>>>    3 files changed, 176 insertions(+), 42 deletions(-)
>>>
>