Re: [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(-)