linux-stable.git/include/linux/maple_tree.h, branch v6.5.2

maple_tree: relocate the declaration of mas_empty_area_rev().

2023-06-09T23:25:46+00:00

Relocate the declaration of mas_empty_area_rev() so that mas_empty_area()
and mas_empty_area_rev() are together.

Link: https://lkml.kernel.org/r/20230524031247.65949-11-zhangpeng.00@bytedance.com
Signed-off-by: Peng Zhang 
Reviewed-by: Liam R. Howlett 
Signed-off-by: Andrew Morton

maple_tree: add mas_prev_range() and mas_find_range_rev interface

2023-06-09T23:25:34+00:00

Some users of the maple tree may want to move to the previous range
regardless of the value stored there.  Add this interface as well as the
'find' variant to support walking to the first value, then iterating over
the previous ranges.

Link: https://lkml.kernel.org/r/20230518145544.1722059-32-Liam.Howlett@oracle.com
Signed-off-by: Liam R. Howlett 
Cc: Vernon Yang 
Cc: David Binderman 
Cc: Peng Zhang 
Cc: Sergey Senozhatsky 
Cc: Wei Yang 
Signed-off-by: Andrew Morton

maple_tree: add mas_next_range() and mas_find_range() interfaces

2023-06-09T23:25:34+00:00

Some users of the maple tree may want to move to the next range in the
tree, even if it stores a NULL.  This family of function provides that
functionality by advancing one slot at a time and returning the result,
while mas_contiguous() will iterate over the range and stop on
encountering the first NULL.

Link: https://lkml.kernel.org/r/20230518145544.1722059-29-Liam.Howlett@oracle.com
Signed-off-by: Liam R. Howlett 
Cc: David Binderman 
Cc: Peng Zhang 
Cc: Sergey Senozhatsky 
Cc: Vernon Yang 
Cc: Wei Yang 
Signed-off-by: Andrew Morton

maple_tree: change RCU checks to WARN_ON() instead of BUG_ON()

2023-06-09T23:25:29+00:00

If RCU is enabled and the tree isn't locked, just warn the user and avoid
crashing the kernel.

Link: https://lkml.kernel.org/r/20230518145544.1722059-9-Liam.Howlett@oracle.com
Signed-off-by: Liam R. Howlett 
Cc: David Binderman 
Cc: Peng Zhang 
Cc: Sergey Senozhatsky 
Cc: Vernon Yang 
Cc: Wei Yang 
Signed-off-by: Andrew Morton

maple_tree: add debug BUG_ON and WARN_ON variants

2023-06-09T23:25:28+00:00

Add debug macros to dump the maple state and/or the tree for both warning
and bug_on calls.

Link: https://lkml.kernel.org/r/20230518145544.1722059-7-Liam.Howlett@oracle.com
Signed-off-by: Liam R. Howlett 
Cc: David Binderman 
Cc: Peng Zhang 
Cc: Sergey Senozhatsky 
Cc: Vernon Yang 
Cc: Wei Yang 
Signed-off-by: Andrew Morton

maple_tree: add format option to mt_dump()

2023-06-09T23:25:28+00:00

Allow different formatting strings to be used when dumping the tree. 
Currently supports hex and decimal.

Link: https://lkml.kernel.org/r/20230518145544.1722059-6-Liam.Howlett@oracle.com
Signed-off-by: Liam R. Howlett 
Cc: David Binderman 
Cc: Peng Zhang 
Cc: Sergey Senozhatsky 
Cc: Vernon Yang 
Cc: Wei Yang 
Signed-off-by: Andrew Morton

maple_tree: add mas_init() function

2023-02-10T00:51:30+00:00

Patch series "VMA tree type safety and remove __vma_adjust()", v4.

This patchset does two things: 1.  Clean up, including removal of
__vma_adjust() and 2.  Extends the VMA iterator API to provide type safety
to the VMA operations using the maple tree, as requested by Linus [1].

It also addresses another issue of usability brought up by Linus about
needing to modify the maple state within the loops.  The maple state has
been replaced by the VMA iterator and the iterator is now modified within
the MM code so the caller should not need to worry about doing the work
themselves when tree modifications occur.

This brought up a potential inconsistency of the iterator state and what
the user expects, so the inconsistency is addressed to keep the VMA
iterator safe for use after the looping over a VMA range.  This is
addressed in patch 3 ("maple_tree: Reduce user error potential") and 4
("test_maple_tree: Test modifications while iterating").

While cleaning up the state, the duplicate locking code in mm/mmap.c
introduced by the maple tree has been address by abstracting it to two
functions: vma_prepare() and vma_complete().  These abstractions allowed
for a much simpler __vma_adjust(), which eventually leads to the removal
of the __vma_adjust() function by placing the logic into the vma_merge()
function itself.

1. https://lore.kernel.org/linux-mm/CAHk-=wg9WQXBGkNdKD2bqocnN73rDswuWsavBB7T-tekykEn_A@mail.gmail.com/


This patch (of 49):

Add a function that will zero out the maple state struct and set some
basic defaults.

Link: https://lkml.kernel.org/r/20230120162650.984577-1-Liam.Howlett@oracle.com
Link: https://lkml.kernel.org/r/20230120162650.984577-2-Liam.Howlett@oracle.com
Signed-off-by: Liam R. Howlett 
Signed-off-by: Andrew Morton

maple_tree: remove the parameter entry of mas_preallocate

2023-02-03T06:32:52+00:00

The parameter entry of mas_preallocate is not used, so drop it.

Link: https://lkml.kernel.org/r/20230110154211.1758562-1-vernon2gm@gmail.com
Signed-off-by: Vernon Yang 
Cc: Liam Howlett 
Cc: Matthew Wilcox 
Signed-off-by: Andrew Morton

maple_tree: remove the redundant code

2023-01-19T01:12:46+00:00

The macros CONFIG_DEBUG_MAPLE_TREE_VERBOSE no one uses, functions
mas_dup_tree() and mas_dup_store() are not implemented, just function
declaration, so drop it.

Link: https://lkml.kernel.org/r/20221221060058.609003-6-vernon2gm@gmail.com
Signed-off-by: Vernon Yang 
Reviewed-by: Liam R. Howlett 
Signed-off-by: Andrew Morton

maple_tree: remove extra space and blank line

2023-01-19T01:12:46+00:00

Patch series "Clean up and refinement for maple tree", v2.

This patchset cleans up and refines some maple tree code.  A few small
changes make the code easier to understand and for better readability.


This patch (of 7):

These extra space and blank lines are unnecessary, so drop them.

Link: https://lkml.kernel.org/r/20221221060058.609003-1-vernon2gm@gmail.com
Link: https://lkml.kernel.org/r/20221221060058.609003-2-vernon2gm@gmail.com
Signed-off-by: Vernon Yang 
Reviewed-by: Liam R. Howlett 
Signed-off-by: Andrew Morton