linux-stable.git/lib/maple_tree.c, branch linux-6.8.y

maple_tree: Add mtree_alloc_cyclic()

2024-05-30T07:48:59+00:00

[ Upstream commit 9b6713cc75229f25552c643083cbdbfb771e5bca ]

I need a cyclic allocator for the simple_offset implementation in
fs/libfs.c.

Signed-off-by: Chuck Lever 
Link: https://lore.kernel.org/r/170820144179.6328.12838600511394432325.stgit@91.116.238.104.host.secureserver.net
Signed-off-by: Christian Brauner 
Stable-dep-of: 23cdd0eed3f1 ("libfs: Fix simple_offset_rename_exchange()")
Signed-off-by: Sasha Levin

maple_tree: fix mas_empty_area_rev() null pointer dereference

2024-05-17T10:15:01+00:00

commit 955a923d2809803980ff574270f81510112be9cf upstream.

Currently the code calls mas_start() followed by mas_data_end() if the
maple state is MA_START, but mas_start() may return with the maple state
node == NULL.  This will lead to a null pointer dereference when checking
information in the NULL node, which is done in mas_data_end().

Avoid setting the offset if there is no node by waiting until after the
maple state is checked for an empty or single entry state.

A user could trigger the events to cause a kernel oops by unmapping all
vmas to produce an empty maple tree, then mapping a vma that would cause
the scenario described above.

Link: https://lkml.kernel.org/r/20240422203349.2418465-1-Liam.Howlett@oracle.com
Fixes: 54a611b60590 ("Maple Tree: add new data structure")
Signed-off-by: Liam R. Howlett 
Reported-by: Marius Fleischer 
Closes: https://lore.kernel.org/lkml/CAJg=8jyuSxDL6XvqEXY_66M20psRK2J53oBTP+fjV5xpW2-R6w@mail.gmail.com/
Link: https://lore.kernel.org/lkml/CAJg=8jyuSxDL6XvqEXY_66M20psRK2J53oBTP+fjV5xpW2-R6w@mail.gmail.com/
Tested-by: Marius Fleischer 
Tested-by: Sidhartha Kumar 
Cc: 
Signed-off-by: Andrew Morton 
Signed-off-by: Greg Kroah-Hartman

maple_tree: avoid checking other gaps after getting the largest gap

2023-12-20T22:48:14+00:00

The last range stored in maple tree is typically quite large.  By checking
if it exceeds the sum of the remaining ranges in that node, it is possible
to avoid checking all other gaps.

Running the maple tree test suite in user mode almost always results in a
near 100% hit rate for this optimization.

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

maple_tree: fix typos/spellos etc

2023-12-20T22:48:12+00:00

Fix typos/grammar and spellos in documentation.

Link: https://lkml.kernel.org/r/20231210063839.29967-1-rdunlap@infradead.org
Signed-off-by: Randy Dunlap 
Reviewed-by: Matthew Wilcox (Oracle) 
Cc: Liam R. Howlett 
Signed-off-by: Andrew Morton

lib/maple_tree.c: fix build error due to hotfix alteration

2023-12-20T22:48:11+00:00

Commit 0de56e38b307 ("maple_tree: use maple state end for write
operations") was broken by a later patch "maple_tree: do not preallocate
nodes for slot stores".  But the later patch was scheduled ahead of
0de56e38b307, for 6.7-rc.

This fixlet undoes the damage.

Fixes: 0de56e38b307 ("maple_tree: use maple state end for write operations")
Cc: Liam R. Howlett 
Cc: Sidhartha Kumar 
Signed-off-by: Andrew Morton

sync mm-stable with mm-hotfixes-stable to pick up depended-upon changes

2023-12-20T22:47:18+00:00

maple_tree: do not preallocate nodes for slot stores

2023-12-20T21:46:19+00:00

mas_preallocate() defaults to requesting 1 node for preallocation and then
,depending on the type of store, will update the request variable.  There
isn't a check for a slot store type, so slot stores are preallocating the
default 1 node.  Slot stores do not require any additional nodes, so add a
check for the slot store case that will bypass node_count_gfp().  Update
the tests to reflect that slot stores do not require allocations.

User visible effects of this bug include increased memory usage from the
unneeded node that was allocated.

Link: https://lkml.kernel.org/r/20231213205058.386589-1-sidhartha.kumar@oracle.com
Fixes: 0b8bb544b1a7 ("maple_tree: update mas_preallocate() testing")
Signed-off-by: Sidhartha Kumar 
Cc: Liam R. Howlett 
Cc: Matthew Wilcox (Oracle) 
Cc: Peng Zhang 
Cc: 	[6.6+]
Signed-off-by: Andrew Morton

maple_tree: change return type of mas_split_final_node as void.

2023-12-12T18:57:09+00:00

mas_split_final_node() always returns true and its return value is never
checked.

Change return type to void.

Link: https://lkml.kernel.org/r/20231109160821.16248-2-ppbuk5246@gmail.com
Signed-off-by: Levi Yun 
Reviewed-by: Liam R. Howlett 
Signed-off-by: Andrew Morton

maple_tree: simplify mas_leaf_set_meta()

2023-12-12T18:57:01+00:00

Now it seems that the incoming 'end' is already pointing to the last item,
so we can simplify this function, considering only whether the last slot
is being used.  This has passed the maple tree test suite.

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

maple_tree: delete one of the two identical checks

2023-12-12T18:57:00+00:00

There are two identical checks, delete one of them.

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