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

[Sidhartha Kumar]

================ overview ========================
Currently, the maple tree preallocates the worst case number of nodes for
given store type by taking into account the whole height of the tree. This
comes from a worst case scenario of every node in the tree being full and
having to propagate node allocation upwards until we reach the root of the
tree. This can be optimized if there are vacancies in nodes that are at a
lower depth than the root node. This series implements tracking the level
at which there is a vacant node so we only need to allocate until this
level is reached, rather than always using the full height of the tree.
The ma_wr_state struct is modified to add a field which keeps track of the
vacant height and is updated during walks of the tree. This value is then
read in mas_prealloc_calc() when we decide how many nodes to allocate.

For rebalancing stores, we also need to track the lowest height at which
a node has 1 more entry than the minimum sufficient number of entries.
This is because rebalancing can cause a parent node to become insufficient
which results in further node allocations. In this case, we need to use
the sufficient height as the worst case rather than the vacant height.

patch 1-2: preparatory patches
patch 3: implement vacant height tracking + update the tests
patch 4: support vacant height tracking for rebalacning writes
patch 5: implement sufficient height tracking

================ 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.


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(-)

-- 
2.43.0