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

maple_tree: fix mt_destroy_walk() on root leaf node

2025-07-17T16:43:51+00:00

commit ea9b77f98d94c4d5c1bd1ac1db078f78b40e8bf5 upstream.

On destroy, we should set each node dead.  But current code miss this when
the maple tree has only the root node.

The reason is mt_destroy_walk() leverage mte_destroy_descend() to set node
dead, but this is skipped since the only root node is a leaf.

Fixes this by setting the node dead if it is a leaf.

Link: https://lore.kernel.org/all/20250407231354.11771-1-richard.weiyang@gmail.com/
Link: https://lkml.kernel.org/r/20250624191841.64682-1-Liam.Howlett@oracle.com
Fixes: 54a611b60590 ("Maple Tree: add new data structure")
Signed-off-by: Wei Yang 
Signed-off-by: Liam R. Howlett 
Reviewed-by: Dev Jain 
Cc: 
Signed-off-by: Andrew Morton 
Signed-off-by: Greg Kroah-Hartman

maple_tree: fix MA_STATE_PREALLOC flag in mas_preallocate()

2025-07-06T09:04:19+00:00

commit fba46a5d83ca8decb338722fb4899026d8d9ead2 upstream.

Temporarily clear the preallocation flag when explicitly requesting
allocations.  Pre-existing allocations are already counted against the
request through mas_node_count_gfp(), but the allocations will not happen
if the MA_STATE_PREALLOC flag is set.  This flag is meant to avoid
re-allocating in bulk allocation mode, and to detect issues with
preallocation calculations.

The MA_STATE_PREALLOC flag should also always be set on zero allocations
so that detection of underflow allocations will print a WARN_ON() during
consumption.

User visible effect of this flaw is a WARN_ON() followed by a null pointer
dereference when subsequent requests for larger number of nodes is
ignored, such as the vma merge retry in mmap_region() caused by drivers
altering the vma flags (which happens in v6.6, at least)

Link: https://lkml.kernel.org/r/20250616184521.3382795-3-Liam.Howlett@oracle.com
Fixes: 54a611b60590 ("Maple Tree: add new data structure")
Signed-off-by: Liam R. Howlett 
Reported-by: Zhaoyang Huang 
Reported-by: Hailong Liu 
Link: https://lore.kernel.org/all/1652f7eb-a51b-4fee-8058-c73af63bacd1@oppo.com/
Link: https://lore.kernel.org/all/20250428184058.1416274-1-Liam.Howlett@oracle.com/
Link: https://lore.kernel.org/all/20250429014754.1479118-1-Liam.Howlett@oracle.com/
Cc: Lorenzo Stoakes 
Cc: Suren Baghdasaryan 
Cc: Hailong Liu 
Cc: zhangpeng.00@bytedance.com 
Cc: Steve Kang 
Cc: Matthew Wilcox 
Cc: Sidhartha Kumar 
Cc: 
Signed-off-by: Andrew Morton 
Signed-off-by: Greg Kroah-Hartman

maple_tree: remove a BUG_ON() in mas_alloc_nodes()

2025-03-17T05:06:15+00:00

Remove a BUG_ON() right before a WARN_ON() with the same condition.

Calling WARN_ON() and BUG_ON() here is definitely wrong.  Since the goal is
generally to remove BUG_ON() invocations from the kernel, keep only the
WARN_ON().

Link: https://lkml.kernel.org/r/20250213114453.1078318-1-ptesarik@suse.com
Fixes: 067311d33e65 ("maple_tree: separate ma_state node from status")
Signed-off-by: Petr Tesarik 
Reviewed-by: Liam R. Howlett 
Signed-off-by: Andrew Morton

maple_tree: use ma_dead_node() in mte_dead_node()

2025-03-17T05:06:13+00:00

Utilize ma_dead_node() in mte_dead_node().  It can prevent decoding the
maple enode for a second time.  Use the "node" to find parent for
comparison.

Link: https://lkml.kernel.org/r/20250211071850.330632-1-richard120310@gmail.com
Signed-off-by: I Hsin Cheng 
Reviewed-by: Liam R. Howlett 
Cc: Ching-Chun (Jim) Huang 
Cc: Shuah khan 
Signed-off-by: Andrew Morton

maple_tree: correct comment for mas_start()

2025-03-17T05:06:10+00:00

There's no mas->status of "mas_start", what the function is checking is
whether mas->status equals to "ma_start".  Correct the comment for the
function.

Link: https://lkml.kernel.org/r/20250209181023.228856-1-richard120310@gmail.com
Signed-off-by: I Hsin Cheng 
Reviewed-by: Liam R. Howlett 
Signed-off-by: Andrew Morton

maple_tree: only root node could be deficient

2025-01-14T06:40:41+00:00

Each level's rightmost node should have (max == ULONG_MAX).  This means
current validation skips the right most node on each level.

Only the root node may be below the minimum data threshold.

Link: https://lkml.kernel.org/r/20241113031616.10530-4-richard.weiyang@gmail.com
Signed-off-by: Wei Yang 
Reviewed-by: Liam R. Howlett 
Cc: Sidhartha Kumar 
Cc: Lorenzo Stoakes 
Signed-off-by: Andrew Morton

maple_tree: simplify split calculation

2025-01-14T06:40:41+00:00

Patch series "simplify split calculation", v3.


This patch (of 3):

The current calculation for splitting nodes tries to enforce a minimum
span on the leaf nodes.  This code is complex and never worked correctly
to begin with, due to the min value being passed as 0 for all leaves.

The calculation should just split the data as equally as possible
between the new nodes.  Note that b_end will be one more than the data,
so the left side is still favoured in the calculation.

The current code may also lead to a deficient node by not leaving enough
data for the right side of the split. This issue is also addressed with
the split calculation change.

[Liam.Howlett@Oracle.com: rephrase the change log]
Link: https://lkml.kernel.org/r/20241113031616.10530-1-richard.weiyang@gmail.com
Link: https://lkml.kernel.org/r/20241113031616.10530-2-richard.weiyang@gmail.com
Fixes: 54a611b60590 ("Maple Tree: add new data structure")
Signed-off-by: Wei Yang 
Reviewed-by: Liam R. Howlett 
Cc: Sidhartha Kumar 
Cc: Lorenzo Stoakes 
Cc: 
Signed-off-by: Andrew Morton

maple_tree: we don't set offset to MAPLE_NODE_SLOTS on error

2025-01-14T06:40:39+00:00

When mas_anode_descend() not find gap, it sets -EBUSY instead of setting
offset to MAPLE_NODE_SLOTS.

Link: https://lkml.kernel.org/r/20241116014805.11547-4-richard.weiyang@gmail.com
Signed-off-by: Wei Yang 
Reviewed-by: Liam R. Howlett 
Cc: Lorenzo Stoakes 
Cc: Sidhartha Kumar 
Signed-off-by: Andrew Morton

maple_tree: not possible to be a root node after loop

2025-01-14T06:40:39+00:00

Empty tree and single entry tree is handled else whether, so the maple
tree here must be a tree with nodes.

If the height is 1 and we found the gap, it will jump to *done* since it
is also a leaf.

If the height is more than one, and there may be an available range, we
will descend the tree, which is not root anymore.

If there is no available range, we will set error and return.

This means the check for root node here is not necessary.

Link: https://lkml.kernel.org/r/20241116014805.11547-3-richard.weiyang@gmail.com
Signed-off-by: Wei Yang 
Reviewed-by: Liam R. Howlett 
Cc: Lorenzo Stoakes 
Cc: Sidhartha Kumar 
Signed-off-by: Andrew Morton

maple_tree: index has been checked to be smaller than pivot

2025-01-14T06:40:39+00:00

Patch series "mas_anode_descend() related cleanup".

Some cleanup related to mas_anode_descend().


This patch (of 3):

At the beginning of loop, it has checked the range is in lower bounds.

Link: https://lkml.kernel.org/r/20241116014805.11547-1-richard.weiyang@gmail.com
Link: https://lkml.kernel.org/r/20241116014805.11547-2-richard.weiyang@gmail.com
Signed-off-by: Wei Yang 
Reviewed-by: Liam R. Howlett 
Cc: Lorenzo Stoakes 
Cc: Sidhartha Kumar 
Signed-off-by: Andrew Morton