Documentation/core-api/maple_tree.rst | 23 +- include/linux/lockdep.h | 3 + include/linux/lockdep_types.h | 3 +- include/linux/maple_tree.h | 12 +- include/linux/sched.h | 1 + kernel/locking/lockdep.c | 58 +++- lib/maple_tree.c | 394 ++++++++++++++++++-------- tools/testing/radix-tree/maple.c | 4 +- 8 files changed, 366 insertions(+), 132 deletions(-)
In this series: 1. Try to detect lock issues A number of syzbot reports are incorrectly pointing to the mm exit as a source of the locking error. The first three patches attempt to help users detect errors in their locking - but they still have to use LOCKDEP. I guess it's still down to hope and prayers. 2. Documentation fixes The documentation was lacking clarity, there are updates to try and help the users, especially around the erase() cases. 3. Two benign issues The cyclic allocator may have a race, although no in-kernel user can hit it. The erase functions may cause allocation issues if used with the incorrect locking type, but none are present in-tree. 4. The erase gfp uses mas_erase() and mtree_erase() do not take a gfp argument. To improve reliability of the erase, the first attempt to allocate will be GFP_NOWAIT, followed by a retry (if necessary of GFP_KERNEL | GFP_NOFAIL. This will ensure the data is gone. I've updated the documentation to make it more clear as well. mas_store() is not addressed in the same way, but may need to be updated at a later date, but that may require changing callers so it is out of scope here. Beyond these goals there are some test fixes, some general speed-up patches targeting extra work and cycles, and dropping dead code. v2: https://lore.kernel.org/all/20260630190843.3563858-1-liam@infradead.org/ v1: https://lore.kernel.org/all/20260629144145.1572283-1-liam@infradead.org/ Changes since v2: - Added a mas_nomem_nofail() function for mas_erase() - Thanks Jason, Vlastimil, and Pedro. - Dropped the WARN_ON() that was triggered by syzbot and questioned by Andrew - Thanks Andrew (and the syzbot) Liam R. Howlett (Oracle) (19): maple_tree: Add rcu locking check when LOCKDEP is enabled locking/lockdep: Add sequence counter to held_lock maple_tree: Add write lock checking with lockdep sequence numbers maple_tree: Documentation fix maple_tree: Drop dead code from mas_extend_spanning_null() maple_tree: Drop MAPLE_ALLOC_SLOTS maple_tree: Clarify comments on mas_nomem() maple_tree: Use prefetched value in mas_wr_store_type() maple_tree: Optimise mas_wr_node_store() when not in rcu mode maple_tree: micro optimisation of mas_wr_store_type() maple_tree: Add bulk parent set helper maple_tree: Catch race in mas_alloc_cyclic() maple_tree: Document that erase may use GFP_KERNEL for allocations maple_tree: Avoid mas_erase() and mtree_erase() failures maple_tree: Document erase and allocations better maple_tree: Change two GFP flags in tests maple_tree: Fix argument name in header maple_tree: Avoid extra gap calculation maple_tree: Add helper mas_make_walkable() Documentation/core-api/maple_tree.rst | 23 +- include/linux/lockdep.h | 3 + include/linux/lockdep_types.h | 3 +- include/linux/maple_tree.h | 12 +- include/linux/sched.h | 1 + kernel/locking/lockdep.c | 58 +++- lib/maple_tree.c | 394 ++++++++++++++++++-------- tools/testing/radix-tree/maple.c | 4 +- 8 files changed, 366 insertions(+), 132 deletions(-) -- 2.47.3
On Fri, 21 Aug 2026 15:26:08 -0400 "Liam R. Howlett (Oracle)" <liam@infradead.org> wrote:
> In this series:
> 1. Try to detect lock issues
> A number of syzbot reports are incorrectly pointing to the mm exit as
> a source of the locking error. The first three patches attempt to
> help users detect errors in their locking - but they still have to use
> LOCKDEP. I guess it's still down to hope and prayers.
>
> 2. Documentation fixes
> The documentation was lacking clarity, there are updates to try and
> help the users, especially around the erase() cases.
>
> 3. Two benign issues
> The cyclic allocator may have a race, although no in-kernel user can
> hit it.
> The erase functions may cause allocation issues if used with the
> incorrect locking type, but none are present in-tree.
>
> 4. The erase gfp uses
> mas_erase() and mtree_erase() do not take a gfp argument. To improve
> reliability of the erase, the first attempt to allocate will be
> GFP_NOWAIT, followed by a retry (if necessary of GFP_KERNEL |
> GFP_NOFAIL. This will ensure the data is gone. I've updated the
> documentation to make it more clear as well. mas_store() is not
> addressed in the same way, but may need to be updated at a later date,
> but that may require changing callers so it is out of scope here.
>
> Beyond these goals there are some test fixes, some general speed-up
> patches targeting extra work and cycles, and dropping dead code.
Thanks, I updated mm.git's mm-unstable branch to this version.
I added a -fix for [13/19], per your discussion with Jason:
--- a/Documentation/core-api/maple_tree.rst~maple_tree-document-erase-and-allocations-better-fix
+++ a/Documentation/core-api/maple_tree.rst
@@ -75,7 +75,8 @@ given index. You can use mtree_erase()
knowing one value within that range, or mtree_store() call with an entry of
NULL may be used to partially erase a range or many ranges at once. Note that
mtree_erase() may use GFP_KERNEL | __GFP_NOFAIL for allocations and cannot
-fail, but may need to sleep - do not use mtree_erase() from a blocking context.
+fail. mtree_erase() can sleep, so it must not be called from an atomic
+context.
If you want to only store a new entry to a range (or index) if that range is
currently ``NULL``, you can use mtree_insert_range() or mtree_insert() which
_
Sashiko said a few things which I think are new since v2.
https://sashiko.dev/#/patchset/20260821192627.4085470-1-liam@infradead.org
> Changes since v2:
> - Added a mas_nomem_nofail() function for mas_erase() - Thanks Jason,
> Vlastimil, and Pedro.
> - Dropped the WARN_ON() that was triggered by syzbot and questioned by
> Andrew - Thanks Andrew (and the syzbot)
Here's how v3 altered mm.git:
Documentation/core-api/maple_tree.rst | 9 ++-
include/linux/maple_tree.h | 2
lib/maple_tree.c | 65 ++++++++++++++++--------
3 files changed, 53 insertions(+), 23 deletions(-)
--- a/Documentation/core-api/maple_tree.rst~b
+++ a/Documentation/core-api/maple_tree.rst
@@ -74,7 +74,9 @@ but takes a range. mtree_load() is used
given index. You can use mtree_erase() to erase an entire range by only
knowing one value within that range, or mtree_store() call with an entry of
NULL may be used to partially erase a range or many ranges at once. Note that
-mtree_erase() may use GFP_KERNEL on allocations.
+mtree_erase() may use GFP_KERNEL | __GFP_NOFAIL for allocations and cannot
+fail. mtree_erase() can sleep, so it must not be called from an atomic
+context.
If you want to only store a new entry to a range (or index) if that range is
currently ``NULL``, you can use mtree_insert_range() or mtree_insert() which
@@ -174,8 +176,9 @@ You can use mas_erase() to erase an enti
last of the maple state to the desired range to erase. This will erase
the first range that is found in that range, set the maple state index
and last as the range that was erased and return the entry that existed
-at that location. Note that mas_erase() may allocate with the GFP_KERNEL flag.
-If this is not okay, consider using mas_store_gfp() and pass it a ``NULL``,
+at that location. Note that mas_erase() may allocate with the GFP_KERNEL
+__GFP_NOFAIL and cannot fail, but may sleep. If this is not okay, consider
+using mas_store_gfp() and pass it a ``NULL``,
after setting up the correct range by walking to the entry.
You can walk each entry within a range by using mas_for_each(). If you want
--- a/include/linux/maple_tree.h~b
+++ a/include/linux/maple_tree.h
@@ -570,6 +570,8 @@ int mas_alloc_cyclic(struct ma_state *ma
unsigned long *next, gfp_t gfp);
bool mas_nomem(struct ma_state *mas, gfp_t gfp);
+bool mas_nomem_nofail(struct ma_state *mas, unsigned long index,
+ unsigned long last);
void mas_pause(struct ma_state *mas);
void maple_tree_init(void);
void mas_destroy(struct ma_state *mas);
--- a/lib/maple_tree.c~b
+++ a/lib/maple_tree.c
@@ -5669,9 +5669,10 @@ EXPORT_SYMBOL_GPL(mas_find_range_rev);
* Searches for @mas->index, sets @mas->index and @mas->last to the range and
* erases that range.
*
- * Note that erase requires allocations and will use GFP_KERNEL to do so if
- * necessary. If the allocation fails, the internal lock will be dropped to
- * retry.
+ * Note that erase requires allocations and will use GFP_KERNEL | __GFP_NOFAIL
+ * to do so if necessary. If the allocation fails, the internal lock will be
+ * dropped to retry. An externally locked tree must be protected by a lock that
+ * allows blocking for this API.
*
* Return: the entry that was erased or %NULL, @mas->index and @mas->last are updated.
*/
@@ -5683,8 +5684,8 @@ void *mas_erase(struct ma_state *mas)
/*
* In low memory situations, the allocation is retried with the gfp flag
- * GFP_KERNEL. The internal spinlock is dropped in mas_nomem(), however
- * the external lock is not dropped.
+ * GFP_KERNEL | __GFP_NOFAIL. The internal spinlock is dropped in
+ * mas_nomem_nofail(), however the external lock is not dropped.
*/
if (mt_external_lock(mas->tree))
might_alloc(GFP_KERNEL);
@@ -5698,16 +5699,8 @@ write_retry:
/* Must reset to ensure spanning writes of last slot are detected */
mas_reset(mas);
mas_wr_preallocate(&wr_mas, NULL);
- if (mas_nomem(mas, GFP_KERNEL)) {
- /* in case the range of entry changed when unlocked */
- mas->index = mas->last = index;
+ if (mas_nomem_nofail(mas, index, index))
goto write_retry;
- }
-
- if (mas_is_err(mas)) {
- entry = NULL;
- goto out;
- }
mas_wr_store_entry(&wr_mas);
out:
@@ -5746,16 +5739,48 @@ bool mas_nomem(struct ma_state *mas, gfp
* Return false on zero forward progress. Partial allocations are kept
* so the retry path will attempt to get the rest. The failure should
* not happen as we try our best to reclaim. The user would need an
- * external lock with a non-blocking gfp in a low memory situation -
- * which would have triggered the first warning in this function.
+ * external lock with a non-blocking gfp in a low memory situation.
*/
- if (WARN_ON_ONCE(!mas->sheaf && !mas->alloc))
+ if (!mas->sheaf && !mas->alloc)
return false;
mas_reset(mas);
return true;
}
+/**
+ * mas_nomem_nofail() - Retry allocations with __GFP_NOFAIL, if the maple state
+ * has stored the -ENOMEM error.
+ * @mas: The maple state
+ * @index: The start of the range for the @mas reset
+ * @last: The end of the range for the @mas reset
+ *
+ * Return: false if @mas isn't in an -ENOMEM state. True if the allocation
+ * happens, the state is reset. The internal lock will be dropped and external
+ * locks must allow blocking.
+ */
+bool mas_nomem_nofail(struct ma_state *mas, unsigned long index,
+ unsigned long last)
+ __must_hold(mas->tree->ma_lock)
+{
+ gfp_t gfp;
+
+ if (likely(mas->node != MA_ERROR(-ENOMEM)))
+ return false;
+
+ gfp = GFP_KERNEL | __GFP_NOFAIL;
+ if (!mt_external_lock(mas->tree)) {
+ mtree_unlock(mas->tree);
+ mas_alloc_nodes(mas, gfp);
+ mtree_lock(mas->tree);
+ } else {
+ mas_alloc_nodes(mas, gfp);
+ }
+
+ mas_set_range(mas, index, last);
+ return true;
+}
+
void __init maple_tree_init(void)
{
struct kmem_cache_args args = {
@@ -6042,9 +6067,9 @@ EXPORT_SYMBOL(mtree_alloc_rrange);
* Erasing is the same as a walk to an entry then a store of a NULL to that
* ENTIRE range. In fact, it is implemented as such using the advanced API.
*
- * Note that erase requires allocations and will use GFP_KERNEL to do so if
- * necessary. If the allocation fails, the internal lock will be dropped to
- * retry.
+ * Note that erase requires allocations and will use GFP_KERNEL | __GFP_NOFAIL
+ * to do so if necessary. If the allocation fails, the internal lock will be
+ * dropped to retry.
*
* Return: The entry stored at the @index or %NULL
*/
_
On 26/08/21 03:26PM, Liam R. Howlett (Oracle) wrote: > In this series: > 1. Try to detect lock issues > A number of syzbot reports are incorrectly pointing to the mm exit as > a source of the locking error. The first three patches attempt to > help users detect errors in their locking - but they still have to use > LOCKDEP. I guess it's still down to hope and prayers. > > 2. Documentation fixes > The documentation was lacking clarity, there are updates to try and > help the users, especially around the erase() cases. > > 3. Two benign issues > The cyclic allocator may have a race, although no in-kernel user can > hit it. > The erase functions may cause allocation issues if used with the > incorrect locking type, but none are present in-tree. > > 4. The erase gfp uses > mas_erase() and mtree_erase() do not take a gfp argument. To improve > reliability of the erase, the first attempt to allocate will be > GFP_NOWAIT, followed by a retry (if necessary of GFP_KERNEL | > GFP_NOFAIL. This will ensure the data is gone. I've updated the > documentation to make it more clear as well. mas_store() is not > addressed in the same way, but may need to be updated at a later date, > but that may require changing callers so it is out of scope here. > > Beyond these goals there are some test fixes, some general speed-up > patches targeting extra work and cycles, and dropping dead code. > > v2: https://lore.kernel.org/all/20260630190843.3563858-1-liam@infradead.org/ > v1: https://lore.kernel.org/all/20260629144145.1572283-1-liam@infradead.org/ > > Changes since v2: > - Added a mas_nomem_nofail() function for mas_erase() - Thanks Jason, > Vlastimil, and Pedro. > - Dropped the WARN_ON() that was triggered by syzbot and questioned by > Andrew - Thanks Andrew (and the syzbot) Sorry, I forgot Breno Leitao's help with the lockdep testing. Thanks Breno, I appreciate the testing and help with that (and for working on debian)! > > Liam R. Howlett (Oracle) (19): > maple_tree: Add rcu locking check when LOCKDEP is enabled > locking/lockdep: Add sequence counter to held_lock > maple_tree: Add write lock checking with lockdep sequence numbers > maple_tree: Documentation fix > maple_tree: Drop dead code from mas_extend_spanning_null() > maple_tree: Drop MAPLE_ALLOC_SLOTS > maple_tree: Clarify comments on mas_nomem() > maple_tree: Use prefetched value in mas_wr_store_type() > maple_tree: Optimise mas_wr_node_store() when not in rcu mode > maple_tree: micro optimisation of mas_wr_store_type() > maple_tree: Add bulk parent set helper > maple_tree: Catch race in mas_alloc_cyclic() > maple_tree: Document that erase may use GFP_KERNEL for allocations > maple_tree: Avoid mas_erase() and mtree_erase() failures > maple_tree: Document erase and allocations better > maple_tree: Change two GFP flags in tests > maple_tree: Fix argument name in header > maple_tree: Avoid extra gap calculation > maple_tree: Add helper mas_make_walkable() > > Documentation/core-api/maple_tree.rst | 23 +- > include/linux/lockdep.h | 3 + > include/linux/lockdep_types.h | 3 +- > include/linux/maple_tree.h | 12 +- > include/linux/sched.h | 1 + > kernel/locking/lockdep.c | 58 +++- > lib/maple_tree.c | 394 ++++++++++++++++++-------- > tools/testing/radix-tree/maple.c | 4 +- > 8 files changed, 366 insertions(+), 132 deletions(-) > > -- > 2.47.3 >
© 2016 - 2026 Red Hat, Inc.