linux-toradex.git/lib/maple_tree.c, branch v6.5-rc4

maple_tree: set the node limit when creating a new root node

2023-07-17T19:53:22+00:00

Set the node limit of the root node so that the last pivot of all nodes is
the node limit (if the node is not full).

This patch also fixes a bug in mas_rev_awalk().  Effectively, always
setting a maximum makes mas_logical_pivot() behave as mas_safe_pivot(). 
Without this fix, it is possible that very small tasks would fail to find
the correct gap.  Although this has not been observed with real tasks, it
has been reported to happen in m68k nommu running the maple tree tests.

Link: https://lkml.kernel.org/r/20230711035444.526-1-zhangpeng.00@bytedance.com
Link: https://lore.kernel.org/linux-mm/CAMuHMdV4T53fOw7VPoBgPR7fP6RYqf=CBhD_y_vOg53zZX_DnA@mail.gmail.com/
Link: https://lkml.kernel.org/r/20230711035444.526-2-zhangpeng.00@bytedance.com
Fixes: 54a611b60590 ("Maple Tree: add new data structure")
Signed-off-by: Peng Zhang 
Reviewed-by: Liam R. Howlett 
Tested-by: Geert Uytterhoeven 
Cc: 
Signed-off-by: Andrew Morton

maple_tree: simplify and clean up mas_wr_node_store()

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

Simplify and clean up mas_wr_node_store(), remove unnecessary code.

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

maple_tree: rework mas_wr_slot_store() to be cleaner and more efficient.

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

Get whether the two gaps to be overwritten are empty to avoid calling
mas_update_gap() all the time.  Also clean up the code and add comments.

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

maple_tree: add comments and some minor cleanups to mas_wr_append()

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

Add comment for mas_wr_append(), move mas_update_gap() into
mas_wr_append(), and other cleanups to make mas_wr_modify() cleaner.

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

maple_tree: add mas_wr_new_end() to calculate new_end accurately

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

The previous new_end calculation is inaccurate, because it assumes that
two new pivots must be added (this is inaccurate), and sometimes it will
miss the fast path and enter the slow path.  Add mas_wr_new_end() to
accurately calculate new_end to make the conditions for entering the fast
path more accurate.

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

maple_tree: make the code symmetrical in mas_wr_extend_null()

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

Just make the code symmetrical to improve readability.

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

maple_tree: simplify mas_is_span_wr()

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

Make the code for detecting spanning writes more concise.

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

maple_tree: fix the arguments to __must_hold()

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

Fix the arguments to __must_hold() to make sparse work.

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

maple_tree: drop mas_{rev_}alloc() and mas_fill_gap()

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

mas_{rev_}alloc() and mas_fill_gap() are no longer used, delete them.

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

maple_tree: rework mtree_alloc_{range,rrange}()

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

Patch series "Clean ups for maple tree", v4.

Some clean ups, mainly to make the code of maple tree more concise.
This patchset has passed the self-test.


This patch (of 10):

Use mas_empty_area{_rev}() to refactor mtree_alloc_{range,rrange}()

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