[v2,00/36] Maple tree mas_{next,prev}_range() and cleanup

Message

Liam R. Howlett May 5, 2023, 5:41 p.m. UTC

This patch set contains a number of clean ups to the code to make it
more usable (next/prev range), the addition of debug output formatting,
the addition of printing the maple state information in the
WARN_ON/BUG_ON code.

There is also work done here to keep nodes active during iterations to
reduce the necessity of re-walking the tree.

Finally, there is a new interface added to move to the next or previous
range in the tree, even if it is empty.

The organisation of the patches is as follows:

0001-0004 - Small clean ups
0005-0018 - Additional debug options and WARN_ON/BUG_ON changes
0019      - Test module __init and __exit addition
0020-0021 - More functional clean ups
0022-0026 - Changes to keep nodes active
0027-0034 - Add new mas_{prev,next}_range()
0035      - Use new mas_{prev,next}_range() in mmap_region()
0036      - Fix testing code of alloc_rev_range() testcase.

Changes since v1:
 - Changed mas_parent_enum() to mas_parent_type() - Thanks Peng Zhang
 - Fix the test code working without debug. - Thanks kernel test robot
   <[e-mail]> 
 - Change vma_iter_store() debug log to one line - Thanks Sergey
   Senozhatsky 
 - Change mas_walk() to return entry instead of mas_root() to avoid
   potential RCU issue. - Thanks Peng Zhang
 - Added fix for testing of mas_empty_area.
 - Added check for underflow to mas_prev_slot() - Thanks Peng Zhang
 - Fixed compile issue in mas_next_slot() interface patch - Thanks
   kernel test robot <[e-mail]>
 - Removed extra check in mas_next_node() - Thanks Peng Zhang
 - Added missing T's to commit message in two patchs - Thanks Petr
   Tesařík
 - Fix the change to the do_vmi_align_munmap() function to work with the
   new iterator - Thanks kernel test robot <[e-mail]>
 - Fix the testing of mas_{prev,next}_range() undeclared function names
   - Thanks kernel test robot <[e-mail]>
 - Fix typo in testing code of mas_{prev,next,walk} - Thanks Peng Zhang


v1: https://lore.kernel.org/linux-mm/[e-mail]/ 

Liam R. Howlett (36):
  maple_tree: Fix static analyser cppcheck issue
  maple_tree: Clean up mas_parent_enum() and rename to mas_parent_type()
  maple_tree: Avoid unnecessary ascending
  maple_tree: Clean up mas_dfs_postorder()
  maple_tree: Add format option to mt_dump()
  maple_tree: Add debug BUG_ON and WARN_ON variants
  maple_tree: Convert BUG_ON() to MT_BUG_ON()
  maple_tree: Change RCU checks to WARN_ON() instead of BUG_ON()
  maple_tree: Convert debug code to use MT_WARN_ON() and MAS_WARN_ON()
  maple_tree: Use MAS_BUG_ON() when setting a leaf node as a parent
  maple_tree: Use MAS_BUG_ON() in mas_set_height()
  maple_tree: Use MAS_BUG_ON() from mas_topiary_range()
  maple_tree: Use MAS_WR_BUG_ON() in mas_store_prealloc()
  maple_tree: Use MAS_BUG_ON() prior to calling mas_meta_gap()
  maple_tree: Return error on mte_pivots() out of range
  maple_tree: Make test code work without debug enabled
  mm: Update validate_mm() to use vma iterator
  mm: Update vma_iter_store() to use MAS_WARN_ON()
  maple_tree: Add __init and __exit to test module
  maple_tree: Remove unnecessary check from mas_destroy()
  maple_tree: mas_start() reset depth on dead node
  mm/mmap: Change do_vmi_align_munmap() for maple tree iterator changes
  maple_tree: Try harder to keep active node after mas_next()
  maple_tree: Try harder to keep active node with mas_prev()
  maple_tree: Revise limit checks in mas_empty_area{_rev}()
  maple_tree: Fix testing mas_empty_area()
  maple_tree: Introduce mas_next_slot() interface
  maple_tree: Add mas_next_range() and mas_find_range() interfaces
  maple_tree: Relocate mas_rewalk() and mas_rewalk_if_dead()
  maple_tree: Introduce mas_prev_slot() interface
  maple_tree: Add mas_prev_range() and mas_find_range_rev interface
  maple_tree: Clear up index and last setting in single entry tree
  maple_tree: Update testing code for mas_{next,prev,walk}
  mm: Add vma_iter_{next,prev}_range() to vma iterator
  mm: Avoid rewalk in mmap_region
  maple_tree: Add gap to check_alloc_rev_range() testcase

 include/linux/maple_tree.h            |  129 ++-
 include/linux/mm.h                    |   13 +
 include/linux/mmdebug.h               |   14 +
 lib/Kconfig.debug                     |   10 +-
 lib/maple_tree.c                      | 1175 ++++++++++++++-----------
 lib/test_maple_tree.c                 |  863 +++++++++++++++---
 mm/debug.c                            |    9 +
 mm/internal.h                         |   26 +-
 mm/mmap.c                             |  111 ++-
 tools/testing/radix-tree/linux/init.h |    1 +
 tools/testing/radix-tree/maple.c      |  164 ++--
 11 files changed, 1760 insertions(+), 755 deletions(-)