Skip to content

Reduce preallocations for maple tree

Liam R. Howlett linux-mm lkml 3 versions – Applied

Status from this message: [merged mm-stable] maple_tree-refine-mas_preallocate-node-calculations.patch removed from -mm tree

Get series with b4
b4 am [email protected]

Versions newest first · linked by author and title

  1. v3 Latest15 patches 6 repliesApplied 15/15
  2. v216 patches 19 repliesSuperseded
  3. v114 patches 19 repliesSuperseded

Changes in v3 from the cover letter

- No longer moving the unmap_vmas() definition - Thanks Mike Kravetz
- Rebase on top of stack changes in do_vmi_align_munmap()

Patches in v3 All 15 applied

#Subject and filesSizeRepliesApplied
1/15maple_tree: Add benchmarking for mas_for_eachlib/test_maple_tree.c+39 -00 repliesApplied
2/15maple_tree: Add benchmarking for mas_prev()lib/test_maple_tree.c+37 -00 repliesApplied
3/15mm: Change do_vmi_align_munmap() tracking of VMAs to removeinclude/linux/mm.h mm/internal.h mm/memory.c +1 more+34 -290 repliesApplied
4/15mm: Remove prev check from do_vmi_align_munmap()mm/mmap.c+0 -20 repliesApplied
5/15maple_tree: Introduce __mas_set_range()include/linux/maple_tree.h+18 -30 repliesApplied
6/15mm: Remove re-walk from mmap_region()mm/internal.h mm/mmap.c+18 -50 repliesApplied
7/15maple_tree: Re-introduce entry to mas_preallocate() argumentsinclude/linux/maple_tree.h lib/maple_tree.c mm/internal.h +2 more+22 -210 repliesApplied
8/15maple_tree: Adjust node allocation on mas_rebalance()lib/maple_tree.c+1 -10 repliesApplied
9/15mm: Use vma_iter_clear_gfp() in nommumm/internal.h mm/mmap.c mm/nommu.c+16 -200 repliesApplied
10/15mm: Set up vma iterator for vma_iter_prealloc() callsfs/exec.c mm/internal.h mm/mmap.c +1 more+64 -570 repliesApplied
11/15maple_tree: Move mas_wr_end_piv() below mas_wr_extend_null()lib/maple_tree.c+15 -160 repliesApplied
12/15maple_tree: Update mas_preallocate() testingtools/testing/radix-tree/maple.c+16 -110 repliesApplied
13/15maple_tree: Refine mas_preallocate() node calculationslib/maple_tree.c+43 -10 repliesApplied
14/15maple_tree: Reduce resets during store setuplib/maple_tree.c+26 -110 repliesApplied
15/15mm/mmap: Change vma iteration order in do_vmi_align_munmap()mm/mmap.c+13 -146 repliesApplied

Reviews trailers per patch

No Reviewed-by, Acked-by or Tested-by trailers for v3 yet.

Read the v3 thread

Cover letter [PATCH v3 00/15] Reduce preallocations for maple tree

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 of the VMAs to be indexed by the count, starting at 0.

Re-introduce the entry argument to mas_preallocate() so that a more intelligent guess of the node count can be made.

Implement the more intelligent guess of the node count, although there is more work to be done.

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: Reduction of maple node allocation in sidetree
0004: Small cleanup of do_vmi_align_munmap()
0005-0014: mas_preallocate() calculation change
0015: Change the vma iterator order

Changes since v2:
- No longer moving the unmap_vmas() definition - Thanks Mike Kravetz
- Rebase on top of stack changes in do_vmi_align_munmap()

v2: https://lore.kernel.org/linux-mm/[email protected]/
v1: https://lore.kernel.org/lkml/[email protected]/

Liam R. Howlett (15):
maple_tree: Add benchmarking for mas_for_each
maple_tree: Add benchmarking for mas_prev()
mm: Change do_vmi_align_munmap() tracking of VMAs to remove
mm: Remove prev check from do_vmi_align_munmap()
maple_tree: Introduce __mas_set_range()
mm: Remove re-walk from mmap_region()
maple_tree: Re-introduce entry to mas_preallocate() arguments
maple_tree: Adjust node allocation on mas_rebalance()
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                 | 117 +++++++++++++++------
 lib/test_maple_tree.c            |  76 ++++++++++++++
 mm/internal.h                    |  36 +++++--
 mm/memory.c                      |  16 ++-
 mm/mmap.c                        | 170 +++++++++++++++++--------------
 mm/nommu.c                       |  45 ++++----
 tools/testing/radix-tree/maple.c |  59 ++++++-----
 10 files changed, 359 insertions(+), 188 deletions(-)
Signature · 1 line
2.39.2