kernel/linux.git/lib/maple_tree.c, branch v7.3-rc1

maple_tree: add helper mas_make_walkable()

2026-08-25T01:43:32+00:00

A check in mas_walk() was incorrect and caused inefficient use of the maple state. The same issue existed in mas_erase(), but was left unfixed. Making a helper function is the obvious answer. Link: https://lore.kernel.org/20260821192627.4085470-20-liam@infradead.org Signed-off-by: Liam R. Howlett (Oracle) Cc: Boqun Feng Cc: Breno Leitao Cc: Chris Mason Cc: Chuck Lever Cc: Ingo Molnar Cc: Jason Gunthorpe Cc: Joe Perches Cc: Peter Zijlstra Cc: Rik van Riel Cc: Waiman Long Cc: Will Deacon Signed-off-by: Andrew Morton

maple_tree: avoid extra gap calculation

2026-08-25T01:43:32+00:00

Prior to ending the ascension loop of larger operations like split, rebalance, and spanning store the gap in the node had been calculated. Once the node is inserted into the tree, the gap is recalculated in mas_update_gap(). This can be avoided by creating a helper for mas_update_gap() that accepts the known gap value, which reduces the operations required for gap updating path. Link: https://lore.kernel.org/20260821192627.4085470-19-liam@infradead.org Signed-off-by: Liam R. Howlett (Oracle) Cc: Boqun Feng Cc: Breno Leitao Cc: Chris Mason Cc: Chuck Lever Cc: Ingo Molnar Cc: Jason Gunthorpe Cc: Joe Perches Cc: Peter Zijlstra Cc: Rik van Riel Cc: Waiman Long Cc: Will Deacon Signed-off-by: Andrew Morton

maple_tree: avoid mas_erase() and mtree_erase() failures

2026-08-25T01:43:31+00:00

Failures to remove entries using the two APIs to erase the entries may result in allocation failures. The failures may go unnoticed and an unexpected entry may remain. Instead, fall back to retrying with GFP_KERNEL | __GFP_NOFAIL so that the entry will be removed. Link: https://lore.kernel.org/20260821192627.4085470-15-liam@infradead.org Signed-off-by: Liam R. Howlett (Oracle) Cc: Rik van Riel Cc: Jason Gunthorpe Cc: Boqun Feng Cc: Breno Leitao Cc: Chris Mason Cc: Chuck Lever Cc: Ingo Molnar Cc: Joe Perches Cc: Peter Zijlstra Cc: Waiman Long Cc: Will Deacon Signed-off-by: Andrew Morton

maple_tree: document that erase may use GFP_KERNEL for allocations

2026-08-25T01:43:31+00:00

State that the mas_erase() and mtree_erase() functions may use GFP_KERNEL on allocation retry. Don't just depend on people reading the documentation by adding a check that will warn of the use. Link: https://lore.kernel.org/20260821192627.4085470-14-liam@infradead.org Signed-off-by: Liam R. Howlett (Oracle) Reviewed-by: Rik van Riel Cc: Jason Gunthorpe Cc: Boqun Feng Cc: Breno Leitao Cc: Chris Mason Cc: Chuck Lever Cc: Ingo Molnar Cc: Joe Perches Cc: Peter Zijlstra Cc: Waiman Long Cc: Will Deacon Signed-off-by: Andrew Morton

maple_tree: catch race in mas_alloc_cyclic()

2026-08-25T01:43:30+00:00

If mas_alloc_cyclic() is called during a low memory situation, it is possible the lock may be dropped so reclaim can occur. There is a window where some other task may allocate the same id and cause the mas_insert() to fail with -EEXIST. In this scenario the function will return -EEXIST, which is not expected. Modifying the retry on mas_nomem() to re-search for a slot means that any race with other writes will not matter as the lock will be held between finding the index and writing the index. Moving the flag logic avoids cases where the flag is modified on drop lock/reacquire or when the write fails after clearing the flag. No existing users are exposed to this issue. Link: https://lore.kernel.org/20260821192627.4085470-13-liam@infradead.org Fixes: 9b6713cc7522 ("maple_tree: Add mtree_alloc_cyclic()") Signed-off-by: Liam R. Howlett (Oracle) Reported-by: Chris Mason Reviewed-by: Chuck Lever Cc: Boqun Feng Cc: Breno Leitao Cc: Ingo Molnar Cc: Jason Gunthorpe Cc: Joe Perches Cc: Peter Zijlstra Cc: Rik van Riel Cc: Waiman Long Cc: Will Deacon Signed-off-by: Andrew Morton

maple_tree: add bulk parent set helper

2026-08-25T01:43:30+00:00

Instead of calculating the parent pointer each time for a child, cache the majority of the parent pointer and only change the slot per child. Drop the mas_set_parent() function since the last user has been removed. Testing on a tree containing 2048 entries of height 4 had an increased gain of 3.51% on nodes tracking gaps. Link: https://lore.kernel.org/20260821192627.4085470-12-liam@infradead.org Signed-off-by: Liam R. Howlett (Oracle) Cc: Boqun Feng Cc: Breno Leitao Cc: Chris Mason Cc: Chuck Lever Cc: Ingo Molnar Cc: Jason Gunthorpe Cc: Joe Perches Cc: Peter Zijlstra Cc: Rik van Riel Cc: Waiman Long Cc: Will Deacon Signed-off-by: Andrew Morton

maple_tree: micro optimisation of mas_wr_store_type()

2026-08-25T01:43:30+00:00

Use three new local booleans instead of reading other structures. This has shown an increase of 0.62% on a 2048 entry tree of height 4. Link: https://lore.kernel.org/20260821192627.4085470-11-liam@infradead.org Signed-off-by: Liam R. Howlett (Oracle) Cc: Boqun Feng Cc: Breno Leitao Cc: Chris Mason Cc: Chuck Lever Cc: Ingo Molnar Cc: Jason Gunthorpe Cc: Joe Perches Cc: Peter Zijlstra Cc: Rik van Riel Cc: Waiman Long Cc: Will Deacon Signed-off-by: Andrew Morton

maple_tree: optimise mas_wr_node_store() when not in rcu mode

2026-08-25T01:43:30+00:00

Clearing the entire node on the stack is unnecessary since most of the node will be overwritten anyways. Just clear what isn't used after the data is in place. Benchmarking shows a speedup of 0.67% on a height 4 tree with 2048 entries. Link: https://lore.kernel.org/20260821192627.4085470-10-liam@infradead.org Signed-off-by: Liam R. Howlett (Oracle) Cc: Boqun Feng Cc: Breno Leitao Cc: Chris Mason Cc: Chuck Lever Cc: Ingo Molnar Cc: Jason Gunthorpe Cc: Joe Perches Cc: Peter Zijlstra Cc: Rik van Riel Cc: Waiman Long Cc: Will Deacon Signed-off-by: Andrew Morton

maple_tree: use prefetched value in mas_wr_store_type()

2026-08-25T01:43:29+00:00

The slot contents exist in wr_mas->content, which has less overhead than reading the slot again. Link: https://lore.kernel.org/20260821192627.4085470-9-liam@infradead.org Signed-off-by: Liam R. Howlett (Oracle) Cc: Boqun Feng Cc: Breno Leitao Cc: Chris Mason Cc: Chuck Lever Cc: Ingo Molnar Cc: Jason Gunthorpe Cc: Joe Perches Cc: Peter Zijlstra Cc: Rik van Riel Cc: Waiman Long Cc: Will Deacon Signed-off-by: Andrew Morton

maple_tree: clarify comments on mas_nomem()

2026-08-25T01:43:29+00:00

When an allocation completely fails, the return is false. If the allocation succeeds or partially succeeds, return true to indicate a retry of the operation. Note that since the lock may have been dropped, the operation is retried from the start - including potentially allocating more memory. Link: https://lore.kernel.org/20260821192627.4085470-8-liam@infradead.org Signed-off-by: Liam R. Howlett (Oracle) Cc: Boqun Feng Cc: Breno Leitao Cc: Chris Mason Cc: Chuck Lever Cc: Ingo Molnar Cc: Jason Gunthorpe Cc: Joe Perches Cc: Peter Zijlstra Cc: Rik van Riel Cc: Waiman Long Cc: Will Deacon Signed-off-by: Andrew Morton