Initial work on preallocations showed no regression in performance during testing, but recently some users (both on [1] and off [android] list) have reported that preallocating the worst-case number of nodes has caused some slow down. This patch set addresses the number of allocations in a few ways. During munmap() most munmap() operations will remove a single VMA, so leverage the fact that the maple tree can place a single pointer at range 0 - 0 without allocating. This is done by changing the index in the 'sidetree'. Re-introduce the entry argument to mas_preallocate() so that a more intelligent guess of the node count can be made. During development of v2 of this patch set, I also noticed that the number of nodes being allocated for a rebalance was beyond what could possibly be needed. This is addressed in patch 0008. Patches are in the following order: 0001-0002: Testing framework for benchmarking some operations 0003-0004: Reduction of maple node allocation in sidetree 0005: Small cleanup of do_vmi_align_munmap() 0006-0015: mas_preallocate() calculation change 0016: Change the vma iterator order Changes since v1: - Reduced preallocations for append and slot store - Thanks Peng Zhang - Added patch to reduce node allocations for mas_rebalance() (patch 0008) - Reduced resets during store setup to avoid duplicate walking (patch 0015) v1: https://lore.kernel.org/lkml/20230601021605.2823123-1-Liam.Howlett@xxxxxxxxxx/ [1] https://lore.kernel.org/linux-mm/202305061457.ac15990c-yujie.liu@xxxxxxxxx/ Liam R. Howlett (16): maple_tree: Add benchmarking for mas_for_each maple_tree: Add benchmarking for mas_prev() mm: Move unmap_vmas() declaration to internal header mm: Change do_vmi_align_munmap() side tree index mm: Remove prev check from do_vmi_align_munmap() maple_tree: Introduce __mas_set_range() mm: Remove re-walk from mmap_region() maple_tree: Adjust node allocation on mas_rebalance() maple_tree: Re-introduce entry to mas_preallocate() arguments mm: Use vma_iter_clear_gfp() in nommu mm: Set up vma iterator for vma_iter_prealloc() calls maple_tree: Move mas_wr_end_piv() below mas_wr_extend_null() maple_tree: Update mas_preallocate() testing maple_tree: Refine mas_preallocate() node calculations maple_tree: Reduce resets during store setup mm/mmap: Change vma iteration order in do_vmi_align_munmap() fs/exec.c | 1 + include/linux/maple_tree.h | 23 ++++- include/linux/mm.h | 4 - lib/maple_tree.c | 121 ++++++++++++++++------ lib/test_maple_tree.c | 74 +++++++++++++ mm/internal.h | 40 ++++++-- mm/memory.c | 19 ++-- mm/mmap.c | 171 ++++++++++++++++--------------- mm/nommu.c | 45 ++++---- tools/testing/radix-tree/maple.c | 59 ++++++----- 10 files changed, 364 insertions(+), 193 deletions(-) -- 2.39.2
