| Seq | Timestamp | Type | Name | Duration |
|---|---|---|---|---|
| 0/0 | 2026/07/02 04:23 | flow | patch-triage |
0mArgs:null Results: {
"EnableConfigs": [
"DEBUG_MAPLE_TREE",
"PROVE_LOCKING",
"LOCKDEP"
],
"FocusSymbols": [
"mas_alloc_cyclic",
"mas_erase",
"mtree_erase",
"mas_nomem",
"lock_sequence"
],
"Reasoning": "The patch introduces lock sequence validation for maple tree operations using lockdep, and optimizes maple tree node store operations and parent pointer updates. It also fixes wrap-around handling in `mas_alloc_cyclic` and modifies memory allocation behavior in `mas_erase` and `mas_nomem`. These are functional changes to core kernel data structures and locking validation, which should be fuzzed to ensure correctness and prevent regressions.",
"WorthFuzzing": true
} |
| 1/1 | 2026/07/02 04:23 | action | read-patch-diff |
0mArgs:null Results: {
"PatchDiff": "commit f5aae681c73dae7feaab013c16095269c01fabaa\nAuthor: syz-cluster \u003ctriage@syzkaller.com\u003e\nDate: Thu Jul 2 04:23:44 2026 +0000\n\n syz-cluster: applied patch under review\n\ndiff --git a/Documentation/core-api/maple_tree.rst b/Documentation/core-api/maple_tree.rst\nindex ccdd1615cf974f..1eae24a9c18b4a 100644\n--- a/Documentation/core-api/maple_tree.rst\n+++ b/Documentation/core-api/maple_tree.rst\n@@ -17,7 +17,8 @@ supports iterating over a range of entries and going to the previous or next\n entry in a cache-efficient manner. The tree can also be put into an RCU-safe\n mode of operation which allows reading and writing concurrently. Writers must\n synchronize on a lock, which can be the default spinlock, or the user can set\n-the lock to an external lock of a different type.\n+the lock to an external lock of a different type. Note that external locks may\n+interfere with allocations in a low memory situation.\n \n The Maple Tree maintains a small memory footprint and was designed to use\n modern processor cache efficiently. The majority of the users will be able to\n@@ -42,6 +43,15 @@ successful store operation within a given\n code segment when allocating cannot be done. Allocations of nodes are\n relatively small at around 256 bytes.\n \n+Since the maple tree uses internal nodes that are allocated and has rules on\n+data density, erasing an entry may cause allocations to occur. That is,\n+erasing an entry may consume memory. Users must take care to ensure that they\n+do not violate the larger system constraints on when and how memory is\n+allocated. Most situations are fine to allocate, but the pre-allocation\n+support is provided as a mechanism to avoid trickier situations. There is also\n+the possibility of using special entries and clean up the tree later, in\n+extreme circumstances.\n+\n .. _maple-tree-normal-api:\n \n Normal API\n@@ -63,7 +73,8 @@ success or an error code otherwise. mtree_store_range() works in the same way\n but takes a range. mtree_load() is used to retrieve the entry stored at a\n given index. You can use mtree_erase() to erase an entire range by only\n knowing one value within that range, or mtree_store() call with an entry of\n-NULL may be used to partially erase a range or many ranges at once.\n+NULL may be used to partially erase a range or many ranges at once. Note that\n+mtree_erase() may use GFP_KERNEL on allocations.\n \n If you want to only store a new entry to a range (or index) if that range is\n currently ``NULL``, you can use mtree_insert_range() or mtree_insert() which\n@@ -163,7 +174,9 @@ You can use mas_erase() to erase an entire range by setting index and\n last of the maple state to the desired range to erase. This will erase\n the first range that is found in that range, set the maple state index\n and last as the range that was erased and return the entry that existed\n-at that location.\n+at that location. Note that mas_erase() may allocate with the GFP_KERNEL flag.\n+If this is not okay, consider using mas_store_gfp() and pass it a ``NULL``,\n+after setting up the correct range by walking to the entry.\n \n You can walk each entry within a range by using mas_for_each(). If you want\n to walk each element of the tree then ``0`` and ``ULONG_MAX`` may be used as\n@@ -211,7 +224,7 @@ Advanced Locking\n \n The maple tree uses a spinlock by default, but external locks can be used for\n tree updates as well. To use an external lock, the tree must be initialized\n-with the ``MT_FLAGS_LOCK_EXTERN flag``, this is usually done with the\n+with the ``MT_FLAGS_LOCK_EXTERN`` flag, this is usually done with the\n MTREE_INIT_EXT() #define, which takes an external lock as an argument.\n \n Functions and structures\ndiff --git a/include/linux/lockdep.h b/include/linux/lockdep.h\nindex 621566345406dd..a6451ecbbe9a05 100644\n--- a/include/linux/lockdep.h\n+++ b/include/linux/lockdep.h\n@@ -273,6 +273,9 @@ extern struct pin_cookie lock_pin_lock(struct lockdep_map *lock);\n extern void lock_repin_lock(struct lockdep_map *lock, struct pin_cookie);\n extern void lock_unpin_lock(struct lockdep_map *lock, struct pin_cookie);\n \n+extern u32 lock_sequence(struct lockdep_map *lock);\n+#define lockdep_sequence(lock)\tlock_sequence(\u0026(lock)-\u003edep_map)\n+\n #define lockdep_depth(tsk)\t(debug_locks ? (tsk)-\u003elockdep_depth : 0)\n \n #define lockdep_assert(cond)\t\t\\\ndiff --git a/include/linux/lockdep_types.h b/include/linux/lockdep_types.h\nindex eae115a2648856..55c4b152fedf7c 100644\n--- a/include/linux/lockdep_types.h\n+++ b/include/linux/lockdep_types.h\n@@ -253,7 +253,8 @@ struct held_lock {\n \tunsigned int hardirqs_off:1;\n \tunsigned int sync:1;\n \tunsigned int references:11;\t\t\t\t\t/* 32 bits */\n-\tunsigned int pin_count;\n+\tunsigned int pin_count:24;\n+\tunsigned int seq_count:8;\n };\n \n #else /* !CONFIG_LOCKDEP */\ndiff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h\nindex 4a5631906affb5..5e0bd2857d941e 100644\n--- a/include/linux/maple_tree.h\n+++ b/include/linux/maple_tree.h\n@@ -29,13 +29,11 @@\n #define MAPLE_NODE_SLOTS\t31\t/* 256 bytes including -\u003eparent */\n #define MAPLE_RANGE64_SLOTS\t16\t/* 256 bytes */\n #define MAPLE_ARANGE64_SLOTS\t10\t/* 240 bytes */\n-#define MAPLE_ALLOC_SLOTS\t(MAPLE_NODE_SLOTS - 1)\n #else\n /* 32bit sizes */\n #define MAPLE_NODE_SLOTS\t63\t/* 256 bytes including -\u003eparent */\n #define MAPLE_RANGE64_SLOTS\t32\t/* 256 bytes */\n #define MAPLE_ARANGE64_SLOTS\t21\t/* 240 bytes */\n-#define MAPLE_ALLOC_SLOTS\t(MAPLE_NODE_SLOTS - 2)\n #endif /* defined(CONFIG_64BIT) || defined(BUILD_VDSO32_64) */\n \n #define MAPLE_NODE_MASK\t\t255UL\n@@ -485,6 +483,12 @@ struct ma_state {\n \tunsigned char mas_flags;\n \tunsigned char end;\t\t/* The end of the node */\n \tenum store_type store_type;\t/* The type of store needed for this operation */\n+#ifdef CONFIG_LOCKDEP\n+\tu32 ld_seq;\n+#ifdef CONFIG_RCU_STRICT_GRACE_PERIOD\n+\tunsigned long rcu_gp;\n+#endif /* CONFIG_RCU_STRICT_GRACE_PERIOD */\n+#endif /* CONFIG_LOCKDEP */\n };\n \n struct ma_wr_state {\n@@ -572,7 +576,7 @@ void maple_tree_init(void);\n void mas_destroy(struct ma_state *mas);\n \n void *mas_prev(struct ma_state *mas, unsigned long min);\n-void *mas_prev_range(struct ma_state *mas, unsigned long max);\n+void *mas_prev_range(struct ma_state *mas, unsigned long min);\n void *mas_next(struct ma_state *mas, unsigned long max);\n void *mas_next_range(struct ma_state *mas, unsigned long max);\n \ndiff --git a/include/linux/sched.h b/include/linux/sched.h\nindex 373bcc0598d10b..14d5ce8dd61365 100644\n--- a/include/linux/sched.h\n+++ b/include/linux/sched.h\n@@ -1288,6 +1288,7 @@ struct task_struct {\n \tu64\t\t\t\tcurr_chain_key;\n \tint\t\t\t\tlockdep_depth;\n \tunsigned int\t\t\tlockdep_recursion;\n+\tunsigned int\t\t\tlockdep_seq;\n \tstruct held_lock\t\theld_locks[MAX_LOCK_DEPTH];\n #endif\n \ndiff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c\nindex 2d4c5bab5af887..b2b0a506960b16 100644\n--- a/kernel/locking/lockdep.c\n+++ b/kernel/locking/lockdep.c\n@@ -5077,7 +5077,7 @@ static int __lock_is_held(const struct lockdep_map *lock, int read);\n static int __lock_acquire(struct lockdep_map *lock, unsigned int subclass,\n \t\t\t int trylock, int read, int check, int hardirqs_off,\n \t\t\t struct lockdep_map *nest_lock, unsigned long ip,\n-\t\t\t int references, int pin_count, int sync)\n+\t\t\t int references, int pin_count, int sync, int seq)\n {\n \tstruct task_struct *curr = current;\n \tstruct lock_class *class = NULL;\n@@ -5183,6 +5183,7 @@ static int __lock_acquire(struct lockdep_map *lock, unsigned int subclass,\n \thlock-\u003eholdtime_stamp = lockstat_clock();\n #endif\n \thlock-\u003epin_count = pin_count;\n+\thlock-\u003eseq_count = seq;\n \n \tif (check_wait_context(curr, hlock))\n \t\treturn 0;\n@@ -5388,7 +5389,7 @@ static int reacquire_held_locks(struct task_struct *curr, unsigned int depth,\n \t\t\t\t hlock-\u003eread, hlock-\u003echeck,\n \t\t\t\t hlock-\u003ehardirqs_off,\n \t\t\t\t hlock-\u003enest_lock, hlock-\u003eacquire_ip,\n-\t\t\t\t hlock-\u003ereferences, hlock-\u003epin_count, 0)) {\n+\t\t\t\t hlock-\u003ereferences, hlock-\u003epin_count, 0, hlock-\u003eseq_count)) {\n \t\tcase 0:\n \t\t\treturn 1;\n \t\tcase 1:\n@@ -5684,6 +5685,24 @@ static void __lock_unpin_lock(struct lockdep_map *lock, struct pin_cookie cookie\n \tWARN(1, \"unpinning an unheld lock\\n\");\n }\n \n+static u32 __lock_sequence(struct lockdep_map *lock)\n+{\n+\tstruct task_struct *curr = current;\n+\tint i;\n+\n+\tif (unlikely(!debug_locks))\n+\t\treturn ~0;\n+\n+\tfor (i = 0; i \u003c curr-\u003elockdep_depth; i++) {\n+\t\tstruct held_lock *hlock = curr-\u003eheld_locks + i;\n+\n+\t\tif (match_held_lock(hlock, lock))\n+\t\t\treturn hlock-\u003eseq_count;\n+\t}\n+\n+\treturn ~0;\n+}\n+\n /*\n * Check whether we follow the irq-flags state precisely:\n */\n@@ -5866,7 +5885,8 @@ void lock_acquire(struct lockdep_map *lock, unsigned int subclass,\n \n \tlockdep_recursion_inc();\n \t__lock_acquire(lock, subclass, trylock, read, check,\n-\t\t irqs_disabled_flags(flags), nest_lock, ip, 0, 0, 0);\n+\t\t irqs_disabled_flags(flags), nest_lock, ip, 0, 0, 0,\n+\t\t ++current-\u003elockdep_seq);\n \tlockdep_recursion_finish();\n \traw_local_irq_restore(flags);\n }\n@@ -5914,7 +5934,8 @@ void lock_sync(struct lockdep_map *lock, unsigned subclass, int read,\n \n \tlockdep_recursion_inc();\n \t__lock_acquire(lock, subclass, 0, read, check,\n-\t\t irqs_disabled_flags(flags), nest_lock, ip, 0, 0, 1);\n+\t\t irqs_disabled_flags(flags), nest_lock, ip, 0, 0, 1,\n+\t\t ++current-\u003elockdep_seq);\n \tcheck_chain_key(current);\n \tlockdep_recursion_finish();\n \traw_local_irq_restore(flags);\n@@ -6000,6 +6021,26 @@ void lock_unpin_lock(struct lockdep_map *lock, struct pin_cookie cookie)\n }\n EXPORT_SYMBOL_GPL(lock_unpin_lock);\n \n+u32 lock_sequence(struct lockdep_map *lock)\n+{\n+\tunsigned long flags;\n+\tu32 seq = ~0;\n+\n+\tif (unlikely(!lockdep_enabled()))\n+\t\treturn seq;\n+\n+\traw_local_irq_save(flags);\n+\tcheck_flags(flags);\n+\n+\tlockdep_recursion_inc();\n+\tseq = __lock_sequence(lock);\n+\tlockdep_recursion_finish();\n+\traw_local_irq_restore(flags);\n+\n+\treturn seq;\n+}\n+EXPORT_SYMBOL_GPL(lock_sequence);\n+\n #ifdef CONFIG_LOCK_STAT\n static void print_lock_contention_bug(struct task_struct *curr,\n \t\t\t\t struct lockdep_map *lock,\ndiff --git a/lib/maple_tree.c b/lib/maple_tree.c\nindex e52876435b77f0..6d71fdc4147064 100644\n--- a/lib/maple_tree.c\n+++ b/lib/maple_tree.c\n@@ -469,7 +469,7 @@ static inline\n void mas_set_parent(struct ma_state *mas, struct maple_enode *enode,\n \t\t const struct maple_enode *parent, unsigned char slot)\n {\n-\tunsigned long val = (unsigned long)parent;\n+\tunsigned long val;\n \tunsigned long shift;\n \tunsigned long type;\n \tenum maple_type p_type = mte_node_type(parent);\n@@ -490,11 +490,47 @@ void mas_set_parent(struct ma_state *mas, struct maple_enode *enode,\n \t\tbreak;\n \t}\n \n+\tval = (unsigned long)parent;\n \tval \u0026= ~MAPLE_NODE_MASK; /* Clear all node metadata in parent */\n \tval |= (slot \u003c\u003c shift) | type;\n \tmte_to_node(enode)-\u003eparent = ma_parent_ptr(val);\n }\n \n+/*\n+ * mas_set_parent_slots() - Bulk operation to set many slot parent pointers\n+ * @mas: The maple state\n+ * @parent: The encoded maple node that is the parent of @enode.\n+ * @slot: The slot that of the @enode.\n+ * @start_slot: The offset into @slot\n+ * @count: The number of slots to set (eg: exclusive)\n+ */\n+static inline\n+void mas_set_parent_slots(struct ma_state *mas, struct maple_enode *parent,\n+\tvoid __rcu **slots, unsigned char start_slot, unsigned char count)\n+{\n+\tunsigned long val;\n+\tunsigned long shift;\n+\tunsigned long type;\n+\tenum maple_type p_type = mte_node_type(parent);\n+\tunsigned char i;\n+\n+\tMAS_BUG_ON(mas, p_type != maple_range_64 \u0026\u0026\n+\t\t\tp_type != maple_arange_64);\n+\n+\tshift = MAPLE_PARENT_SLOT_SHIFT;\n+\ttype = MAPLE_PARENT_RANGE64;\n+\n+\tval = (unsigned long)parent;\n+\tval \u0026= ~MAPLE_NODE_MASK;\n+\n+\tfor (i = 0; i \u003c count; i++) {\n+\t\tunsigned long pval = val | ((start_slot + i) \u003c\u003c shift) | type;\n+\t\tstruct maple_enode *child = (struct maple_enode *)slots[i];\n+\n+\t\tmte_to_node(child)-\u003eparent = ma_parent_ptr(pval);\n+\t}\n+}\n+\n /*\n * mte_parent_slot() - get the parent slot of @enode.\n * @enode: The encoded maple node.\n@@ -1153,6 +1189,70 @@ static inline void mas_free(struct ma_state *mas, struct maple_enode *used)\n \tma_free_rcu(mte_to_node(used));\n }\n \n+\n+#ifdef CONFIG_LOCKDEP\n+struct lockdep_map *mas_lockdep_map(struct ma_state *mas)\n+{\n+\tstruct maple_tree *mt = mas-\u003etree;\n+\n+\tif (mt_external_lock(mt))\n+\t\treturn mt-\u003ema_external_lock;\n+\n+\treturn \u0026(mt-\u003ema_lock).dep_map;\n+}\n+\n+#endif\n+\n+static void mas_lock_check(struct ma_state *mas)\n+{\n+\n+#ifdef CONFIG_LOCKDEP\n+\tif (!mas_is_active(mas))\n+\t\treturn;\n+\n+#ifdef CONFIG_RCU_STRICT_GRACE_PERIOD\n+\tif (!mt_lock_is_held(mas-\u003etree)) {\n+\t\tif (mt_in_rcu(mas-\u003etree))\n+\t\t\tWARN_ON_ONCE(poll_state_synchronize_rcu(mas-\u003ercu_gp));\n+\t}\n+#endif /* CONFIG_RCU_STRICT_GRACE_PERIOD */\n+\n+\tif (mt_lock_is_held(mas-\u003etree))\n+\t\tWARN_ON_ONCE(mas-\u003eld_seq != lock_sequence(mas_lockdep_map(mas)));\n+#endif /* CONFIG_LOCKDEP */\n+\n+}\n+\n+static void mas_init_lock_check(struct ma_state *mas)\n+{\n+#ifdef CONFIG_LOCKDEP\n+#ifdef CONFIG_RCU_STRICT_GRACE_PERIOD\n+\tif (!mt_lock_is_held(mas-\u003etree)) {\n+\t\tif (mt_in_rcu(mas-\u003etree))\n+\t\t\tmas-\u003ercu_gp = get_state_synchronize_rcu();\n+\t\treturn;\n+\t}\n+#endif /* CONFIG_RCU_STRICT_GRACE_PERIOD */\n+\n+\tif (mt_lock_is_held(mas-\u003etree))\n+\t\tmas-\u003eld_seq = lock_sequence(mas_lockdep_map(mas));\n+#endif /* CONFIG_LOCKDEP */\n+\n+}\n+\n+static void mas_may_init_lock_check(struct ma_state *mas)\n+{\n+#ifdef CONFIG_LOCKDEP\n+#ifdef CONFIG_RCU_STRICT_GRACE_PERIOD\n+\tif (mas_is_start(mas) || mas_is_paused(mas)) {\n+\t\tmas_init_lock_check(mas);\n+\t\treturn;\n+\t}\n+#endif /* CONFIG_RCU_STRICT_GRACE_PERIOD */\n+\tmas_lock_check(mas);\n+#endif /* CONFIG_LOCKDEP */\n+}\n+\n /*\n * mas_start() - Sets up maple state for operations.\n * @mas: The maple state.\n@@ -1171,6 +1271,7 @@ static inline struct maple_enode *mas_start(struct ma_state *mas)\n \tif (likely(mas_is_start(mas))) {\n \t\tstruct maple_enode *root;\n \n+\t\tmas_init_lock_check(mas);\n \t\tmas-\u003emin = 0;\n \t\tmas-\u003emax = ULONG_MAX;\n \n@@ -1501,14 +1602,26 @@ static inline void mas_parent_gap(struct ma_state *mas, unsigned char offset,\n \tgoto ascend;\n }\n \n+static __always_inline void mas_update_gap_known(struct ma_state *mas,\n+\t\tunsigned long gap)\n+{\n+\tunsigned char pslot;\n+\tunsigned long p_gap;\n+\n+\tpslot = mte_parent_slot(mas-\u003enode);\n+\tp_gap = ma_gaps(mte_parent(mas-\u003enode),\n+\t\t\tmas_parent_type(mas, mas-\u003enode))[pslot];\n+\n+\tif (p_gap != gap)\n+\t\tmas_parent_gap(mas, pslot, gap);\n+}\n+\n /*\n * mas_update_gap() - Update a nodes gaps and propagate up if necessary.\n * @mas: the maple state.\n */\n static inline void mas_update_gap(struct ma_state *mas)\n {\n-\tunsigned char pslot;\n-\tunsigned long p_gap;\n \tunsigned long max_gap;\n \n \tif (!mt_is_alloc(mas-\u003etree))\n@@ -1518,13 +1631,7 @@ static inline void mas_update_gap(struct ma_state *mas)\n \t\treturn;\n \n \tmax_gap = mas_max_gap(mas);\n-\n-\tpslot = mte_parent_slot(mas-\u003enode);\n-\tp_gap = ma_gaps(mte_parent(mas-\u003enode),\n-\t\t\tmas_parent_type(mas, mas-\u003enode))[pslot];\n-\n-\tif (p_gap != max_gap)\n-\t\tmas_parent_gap(mas, pslot, max_gap);\n+\tmas_update_gap_known(mas, max_gap);\n }\n \n /*\n@@ -1540,14 +1647,10 @@ static inline void mas_adopt_children(struct ma_state *mas,\n \tstruct maple_node *node = mte_to_node(parent);\n \tvoid __rcu **slots = ma_slots(node, type);\n \tunsigned long *pivots = ma_pivots(node, type);\n-\tstruct maple_enode *child;\n-\tunsigned char offset;\n+\tunsigned char end;\n \n-\toffset = ma_data_end(node, type, pivots, mas-\u003emax);\n-\tdo {\n-\t\tchild = mas_slot_locked(mas, slots, offset);\n-\t\tmas_set_parent(mas, child, parent, offset);\n-\t} while (offset--);\n+\tend = ma_data_end(node, type, pivots, mas-\u003emax);\n+\tmas_set_parent_slots(mas, parent, slots, 0, end + 1);\n }\n \n /*\n@@ -1929,15 +2032,10 @@ unsigned long node_copy(struct ma_state *mas, struct maple_node *src,\n \ts_slots = ma_slots(src, s_mt) + start;\n \ts_pivots = ma_pivots(src, s_mt) + start;\n \tmemcpy(d_slots, s_slots, size * sizeof(void __rcu *));\n-\tif (!ma_is_leaf(d_mt) \u0026\u0026 s_mt == maple_copy) {\n-\t\tstruct maple_enode *edst = mt_mk_node(dst, d_mt);\n \n-\n-\t\tfor (int i = 0; i \u003c size; i++)\n-\t\t\tmas_set_parent(mas,\n-\t\t\t\t mt_slot_locked(mas-\u003etree, d_slots, i),\n-\t\t\t\t edst, d_start + i);\n-\t}\n+\tif (!ma_is_leaf(d_mt) \u0026\u0026 s_mt == maple_copy)\n+\t\tmas_set_parent_slots(mas, mt_mk_node(dst, d_mt),\n+\t\t\t\t d_slots, d_start, size);\n \n \td_gaps = ma_gaps(dst, d_mt);\n \tif (d_gaps) {\n@@ -2081,8 +2179,8 @@ static inline void mas_wmb_replace(struct ma_state *mas, struct maple_copy *cp)\n \tmas-\u003enode = mt_slot_locked(mas-\u003etree, cp-\u003eslot, 0);\n \t/* Insert the new data in the tree */\n \tmas_topiary_replace(mas, old_enode, cp-\u003eheight);\n-\tif (!mte_is_leaf(mas-\u003enode))\n-\t\tmas_update_gap(mas);\n+\tif (mt_is_alloc(mas-\u003etree) \u0026\u0026 !mte_is_root(mas-\u003enode))\n+\t\tmas_update_gap_known(mas, cp-\u003egap[0]);\n \n \tmtree_range_walk(mas);\n }\n@@ -2928,13 +3026,6 @@ static inline void mas_extend_spanning_null(struct ma_wr_state *l_wr_mas,\n \t\tif (r_mas-\u003elast \u003c r_wr_mas-\u003er_max)\n \t\t\tr_mas-\u003elast = r_wr_mas-\u003er_max;\n \t\tr_mas-\u003eoffset++;\n-\t} else if ((r_mas-\u003elast == r_wr_mas-\u003er_max) \u0026\u0026\n-\t (r_mas-\u003elast \u003c r_mas-\u003emax) \u0026\u0026\n-\t !mas_slot_locked(r_mas, r_wr_mas-\u003eslots, r_mas-\u003eoffset + 1)) {\n-\t\tr_mas-\u003elast = mas_safe_pivot(r_mas, r_wr_mas-\u003epivots,\n-\t\t\t\t\t r_wr_mas-\u003etype, r_mas-\u003eoffset + 1);\n-\t\tr_mas-\u003eoffset++;\n-\t\tr_wr_mas-\u003er_max = r_mas-\u003elast;\n \t}\n }\n \n@@ -3125,7 +3216,7 @@ static void mas_wr_spanning_store(struct ma_wr_state *wr_mas)\n static inline void mas_wr_node_store(struct ma_wr_state *wr_mas)\n {\n \tunsigned char dst_offset, offset_end;\n-\tunsigned char copy_size, node_pivots;\n+\tunsigned char copy_size, node_pivots, node_slots;\n \tstruct maple_node reuse, *newnode;\n \tunsigned long *dst_pivots;\n \tvoid __rcu **dst_slots;\n@@ -3138,6 +3229,7 @@ static inline void mas_wr_node_store(struct ma_wr_state *wr_mas)\n \tin_rcu = mt_in_rcu(mas-\u003etree);\n \toffset_end = wr_mas-\u003eoffset_end;\n \tnode_pivots = mt_pivots[wr_mas-\u003etype];\n+\tnode_slots = mt_slots[wr_mas-\u003etype];\n \t/* Assume last adds an entry */\n \tnew_end = mas-\u003eend + 1 - offset_end + mas-\u003eoffset;\n \tif (mas-\u003elast == wr_mas-\u003eend_piv) {\n@@ -3149,7 +3241,6 @@ static inline void mas_wr_node_store(struct ma_wr_state *wr_mas)\n \tif (in_rcu) {\n \t\tnewnode = mas_pop_node(mas);\n \t} else {\n-\t\tmemset(\u0026reuse, 0, sizeof(struct maple_node));\n \t\tnewnode = \u0026reuse;\n \t}\n \n@@ -3193,7 +3284,17 @@ static inline void mas_wr_node_store(struct ma_wr_state *wr_mas)\n \t\tdst_pivots[new_end] = mas-\u003emax;\n \n done:\n-\tmas_leaf_set_meta(newnode, maple_leaf_64, new_end);\n+\tif (!in_rcu \u0026\u0026 new_end + 2 \u003c node_slots) {\n+\t\tunsigned char clear_from = new_end + 1;\n+\n+\t\tmemset(dst_slots + clear_from, 0,\n+\t\t sizeof(void __rcu *) * (node_slots - clear_from));\n+\t\tif (clear_from \u003c node_pivots)\n+\t\t\tmemset(dst_pivots + clear_from, 0,\n+\t\t\t sizeof(unsigned long) * (node_pivots - clear_from));\n+\t}\n+\n+\tmas_leaf_set_meta(newnode, wr_mas-\u003etype, new_end);\n \tif (in_rcu) {\n \t\tstruct maple_enode *old_enode = mas-\u003enode;\n \n@@ -3218,7 +3319,7 @@ static inline void mas_wr_slot_store(struct ma_wr_state *wr_mas)\n \tvoid __rcu **slots = wr_mas-\u003eslots;\n \tbool gap = false;\n \n-\tgap |= !mt_slot_locked(mas-\u003etree, slots, offset);\n+\tgap |= !wr_mas-\u003econtent;\n \tgap |= !mt_slot_locked(mas-\u003etree, slots, offset + 1);\n \n \tif (wr_mas-\u003eoffset_end - offset == 1) {\n@@ -3661,6 +3762,9 @@ static inline enum store_type mas_wr_store_type(struct ma_wr_state *wr_mas)\n {\n \tstruct ma_state *mas = wr_mas-\u003emas;\n \tunsigned char new_end;\n+\tbool appending;\n+\tbool one_slot;\n+\tbool in_rcu;\n \n \tif (unlikely(mas_is_none(mas) || mas_is_ptr(mas)))\n \t\treturn wr_store_root;\n@@ -3680,21 +3784,30 @@ static inline enum store_type mas_wr_store_type(struct ma_wr_state *wr_mas)\n \t\treturn wr_new_root;\n \n \tnew_end = mas_wr_new_end(wr_mas);\n+\tin_rcu = mt_in_rcu(mas-\u003etree);\n+\tappending = mas-\u003eoffset == mas-\u003eend;\n+\tone_slot = wr_mas-\u003eoffset_end - mas-\u003eoffset == 1;\n+\n \t/* Potential spanning rebalance collapsing a node */\n \tif (new_end \u003c mt_min_slots[wr_mas-\u003etype]) {\n \t\tif (!mte_is_root(mas-\u003enode))\n \t\t\treturn wr_rebalance;\n+\t\tif (!in_rcu) {\n+\t\t\tif (appending)\n+\t\t\t\treturn wr_append;\n+\t\t\telse if (mas-\u003eend == new_end \u0026\u0026 one_slot)\n+\t\t\t\treturn wr_slot_store;\n+\t\t}\n \t\treturn wr_node_store;\n \t}\n \n \tif (new_end \u003e= mt_slots[wr_mas-\u003etype])\n \t\treturn wr_split_store;\n \n-\tif (!mt_in_rcu(mas-\u003etree) \u0026\u0026 (mas-\u003eoffset == mas-\u003eend))\n+\tif (!in_rcu \u0026\u0026 appending)\n \t\treturn wr_append;\n \n-\tif ((new_end == mas-\u003eend) \u0026\u0026 (!mt_in_rcu(mas-\u003etree) ||\n-\t\t(wr_mas-\u003eoffset_end - mas-\u003eoffset == 1)))\n+\tif (new_end == mas-\u003eend \u0026\u0026 (!in_rcu || one_slot))\n \t\treturn wr_slot_store;\n \n \treturn wr_node_store;\n@@ -3793,27 +3906,29 @@ int mas_alloc_cyclic(struct ma_state *mas, unsigned long *startp,\n \t\tvoid *entry, unsigned long range_lo, unsigned long range_hi,\n \t\tunsigned long *next, gfp_t gfp)\n {\n-\tunsigned long min = range_lo;\n-\tint ret = 0;\n+\tint ret;\n+\tunsigned long min;\n \n-\trange_lo = max(min, *next);\n-\tret = mas_empty_area(mas, range_lo, range_hi, 1);\n-\tif ((mas-\u003etree-\u003ema_flags \u0026 MT_FLAGS_ALLOC_WRAPPED) \u0026\u0026 ret == 0) {\n-\t\tmas-\u003etree-\u003ema_flags \u0026= ~MT_FLAGS_ALLOC_WRAPPED;\n-\t\tret = 1;\n-\t}\n-\tif (ret \u003c 0 \u0026\u0026 range_lo \u003e min) {\n-\t\tmas_reset(mas);\n-\t\tret = mas_empty_area(mas, min, range_hi, 1);\n-\t\tif (ret == 0)\n+\tmin = range_lo;\n+\tdo {\n+\t\trange_lo = max(min, *next);\n+\t\tret = mas_empty_area(mas, range_lo, range_hi, 1);\n+\t\tif ((mas-\u003etree-\u003ema_flags \u0026 MT_FLAGS_ALLOC_WRAPPED) \u0026\u0026 ret == 0) {\n+\t\t\tmas-\u003etree-\u003ema_flags \u0026= ~MT_FLAGS_ALLOC_WRAPPED;\n \t\t\tret = 1;\n-\t}\n-\tif (ret \u003c 0)\n-\t\treturn ret;\n+\t\t}\n+\t\tif (ret \u003c 0 \u0026\u0026 range_lo \u003e min) {\n+\t\t\tmas_reset(mas);\n+\t\t\tret = mas_empty_area(mas, min, range_hi, 1);\n+\t\t\tif (ret == 0)\n+\t\t\t\tret = 1;\n+\t\t}\n+\t\tif (ret \u003c 0)\n+\t\t\treturn ret;\n \n-\tdo {\n \t\tmas_insert(mas, entry);\n \t} while (mas_nomem(mas, gfp));\n+\n \tif (mas_is_err(mas))\n \t\treturn xa_err(mas-\u003enode);\n \n@@ -4360,6 +4475,7 @@ void *mas_walk(struct ma_state *mas)\n {\n \tvoid *entry;\n \n+\tmas_may_init_lock_check(mas);\n \tif (!mas_is_active(mas) \u0026\u0026 !mas_is_start(mas))\n \t\tmas-\u003estatus = ma_start;\n retry:\n@@ -4831,6 +4947,7 @@ void *mas_store(struct ma_state *mas, void *entry)\n {\n \tMA_WR_STATE(wr_mas, mas, entry);\n \n+\tmas_may_init_lock_check(mas);\n \ttrace_ma_write(TP_FCT, mas, 0, entry);\n #ifdef CONFIG_DEBUG_MAPLE_TREE\n \tif (MAS_WARN_ON(mas, mas-\u003eindex \u003e mas-\u003elast))\n@@ -4889,6 +5006,7 @@ int mas_store_gfp(struct ma_state *mas, void *entry, gfp_t gfp)\n \tMA_WR_STATE(wr_mas, mas, entry);\n \tint ret = 0;\n \n+\tmas_may_init_lock_check(mas);\n retry:\n \tmas_wr_preallocate(\u0026wr_mas, entry);\n \tif (unlikely(mas_nomem(mas, gfp))) {\n@@ -4919,6 +5037,7 @@ void mas_store_prealloc(struct ma_state *mas, void *entry)\n {\n \tMA_WR_STATE(wr_mas, mas, entry);\n \n+\tmas_lock_check(mas);\n \tif (mas-\u003estore_type == wr_store_root) {\n \t\tmas_wr_prealloc_setup(\u0026wr_mas);\n \t\tgoto store;\n@@ -4951,6 +5070,7 @@ int mas_preallocate(struct ma_state *mas, void *entry, gfp_t gfp)\n {\n \tMA_WR_STATE(wr_mas, mas, entry);\n \n+\tmas_may_init_lock_check(mas);\n \tmas_wr_prealloc_setup(\u0026wr_mas);\n \tmas-\u003estore_type = mas_wr_store_type(\u0026wr_mas);\n \tmas_prealloc_calc(\u0026wr_mas, entry);\n@@ -5074,6 +5194,7 @@ void *mas_next(struct ma_state *mas, unsigned long max)\n {\n \tvoid *entry = NULL;\n \n+\tmas_may_init_lock_check(mas);\n \tif (mas_next_setup(mas, max, \u0026entry))\n \t\treturn entry;\n \n@@ -5097,6 +5218,7 @@ void *mas_next_range(struct ma_state *mas, unsigned long max)\n {\n \tvoid *entry = NULL;\n \n+\tmas_may_init_lock_check(mas);\n \tif (mas_next_setup(mas, max, \u0026entry))\n \t\treturn entry;\n \n@@ -5205,6 +5327,7 @@ void *mas_prev(struct ma_state *mas, unsigned long min)\n {\n \tvoid *entry = NULL;\n \n+\tmas_may_init_lock_check(mas);\n \tif (mas_prev_setup(mas, min, \u0026entry))\n \t\treturn entry;\n \n@@ -5228,6 +5351,7 @@ void *mas_prev_range(struct ma_state *mas, unsigned long min)\n {\n \tvoid *entry = NULL;\n \n+\tmas_may_init_lock_check(mas);\n \tif (mas_prev_setup(mas, min, \u0026entry))\n \t\treturn entry;\n \n@@ -5274,6 +5398,7 @@ EXPORT_SYMBOL_GPL(mt_prev);\n */\n void mas_pause(struct ma_state *mas)\n {\n+\tmas_lock_check(mas);\n \tmas-\u003estatus = ma_pause;\n \tmas-\u003enode = NULL;\n }\n@@ -5382,6 +5507,7 @@ void *mas_find(struct ma_state *mas, unsigned long max)\n {\n \tvoid *entry = NULL;\n \n+\tmas_may_init_lock_check(mas);\n \tif (mas_find_setup(mas, max, \u0026entry))\n \t\treturn entry;\n \n@@ -5409,6 +5535,7 @@ void *mas_find_range(struct ma_state *mas, unsigned long max)\n {\n \tvoid *entry = NULL;\n \n+\tmas_may_init_lock_check(mas);\n \tif (mas_find_setup(mas, max, \u0026entry))\n \t\treturn entry;\n \n@@ -5428,7 +5555,6 @@ EXPORT_SYMBOL_GPL(mas_find_range);\n static bool mas_find_rev_setup(struct ma_state *mas, unsigned long min,\n \t\tvoid **entry)\n {\n-\n \tswitch (mas-\u003estatus) {\n \tcase ma_active:\n \t\tgoto active;\n@@ -5521,6 +5647,7 @@ void *mas_find_rev(struct ma_state *mas, unsigned long min)\n {\n \tvoid *entry = NULL;\n \n+\tmas_may_init_lock_check(mas);\n \tif (mas_find_rev_setup(mas, min, \u0026entry))\n \t\treturn entry;\n \n@@ -5547,6 +5674,7 @@ void *mas_find_range_rev(struct ma_state *mas, unsigned long min)\n {\n \tvoid *entry = NULL;\n \n+\tmas_may_init_lock_check(mas);\n \tif (mas_find_rev_setup(mas, min, \u0026entry))\n \t\treturn entry;\n \n@@ -5564,6 +5692,10 @@ EXPORT_SYMBOL_GPL(mas_find_range_rev);\n * Searches for @mas-\u003eindex, sets @mas-\u003eindex and @mas-\u003elast to the range and\n * erases that range.\n *\n+ * Note that erase requires allocations and will use GFP_KERNEL to do so if\n+ * necessary. If the allocation fails, the internal lock will be dropped to\n+ * retry.\n+ *\n * Return: the entry that was erased or %NULL, @mas-\u003eindex and @mas-\u003elast are updated.\n */\n void *mas_erase(struct ma_state *mas)\n@@ -5572,6 +5704,14 @@ void *mas_erase(struct ma_state *mas)\n \tunsigned long index = mas-\u003eindex;\n \tMA_WR_STATE(wr_mas, mas, NULL);\n \n+\t/*\n+\t * In low memory situations, the allocation is retried with the gfp flag\n+\t * GFP_KERNEL. The internal spinlock is dropped in mas_nomem(), however\n+\t * the external lock is not dropped.\n+\t */\n+\tif (mt_external_lock(mas-\u003etree))\n+\t\tmight_alloc(GFP_KERNEL);\n+\n \tif (!mas_is_active(mas) || !mas_is_start(mas))\n \t\tmas-\u003estatus = ma_start;\n \n@@ -5601,10 +5741,11 @@ EXPORT_SYMBOL_GPL(mas_erase);\n \n /**\n * mas_nomem() - Check if there was an error allocating and do the allocation\n- * if necessary If there are allocations, then free them.\n+ * if necessary.\n+ *\n * @mas: The maple state\n * @gfp: The GFP_FLAGS to use for allocations\n- * Return: true on allocation, false otherwise.\n+ * Return: False on no memory. True otherwise (partial success as well)\n */\n bool mas_nomem(struct ma_state *mas, gfp_t gfp)\n \t__must_hold(mas-\u003etree-\u003ema_lock)\n@@ -5612,6 +5753,10 @@ bool mas_nomem(struct ma_state *mas, gfp_t gfp)\n \tif (likely(mas-\u003enode != MA_ERROR(-ENOMEM)))\n \t\treturn false;\n \n+\t/* Allocations can fail, don't do this. */\n+\tWARN_ON_ONCE(!gfpflags_allow_blocking(gfp) \u0026\u0026\n+\t\t mt_external_lock(mas-\u003etree));\n+\n \tif (gfpflags_allow_blocking(gfp) \u0026\u0026 !mt_external_lock(mas-\u003etree)) {\n \t\tmtree_unlock(mas-\u003etree);\n \t\tmas_alloc_nodes(mas, gfp);\n@@ -5620,10 +5765,17 @@ bool mas_nomem(struct ma_state *mas, gfp_t gfp)\n \t\tmas_alloc_nodes(mas, gfp);\n \t}\n \n-\tif (!mas-\u003esheaf \u0026\u0026 !mas-\u003ealloc)\n+\t/*\n+\t * Return false on zero forward progress. Partial allocations are kept\n+\t * so the retry path will attempt to get the rest. The failure should\n+\t * not happen as we try our best to reclaim. The user would need an\n+\t * external lock with a non-blocking gfp in a low memory situation -\n+\t * which would have triggered the first warning in this function.\n+\t */\n+\tif (WARN_ON_ONCE(!mas-\u003esheaf \u0026\u0026 !mas-\u003ealloc))\n \t\treturn false;\n \n-\tmas-\u003estatus = ma_start;\n+\tmas_reset(mas);\n \treturn true;\n }\n \n@@ -5913,6 +6065,10 @@ EXPORT_SYMBOL(mtree_alloc_rrange);\n * Erasing is the same as a walk to an entry then a store of a NULL to that\n * ENTIRE range. In fact, it is implemented as such using the advanced API.\n *\n+ * Note that erase requires allocations and will use GFP_KERNEL to do so if\n+ * necessary. If the allocation fails, the internal lock will be dropped to\n+ * retry.\n+ *\n * Return: The entry stored at the @index or %NULL\n */\n void *mtree_erase(struct maple_tree *mt, unsigned long index)\ndiff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/maple.c\nindex 0607913a3022d5..d967e76a3c0650 100644\n--- a/tools/testing/radix-tree/maple.c\n+++ b/tools/testing/radix-tree/maple.c\n@@ -35234,7 +35234,7 @@ static noinline void __init check_prealloc(struct maple_tree *mt)\n \tmt_set_non_kernel(1);\n \t/* Spanning store */\n \tmas_set_range(\u0026mas, 1, 100);\n-\tMT_BUG_ON(mt, mas_preallocate(\u0026mas, ptr, GFP_KERNEL \u0026 GFP_NOWAIT) == 0);\n+\tMT_BUG_ON(mt, mas_preallocate(\u0026mas, ptr, GFP_NOWAIT) == 0);\n \tallocated = mas_allocated(\u0026mas);\n \theight = mas_mt_height(\u0026mas);\n \tMT_BUG_ON(mt, allocated != 0);\n@@ -35257,7 +35257,7 @@ static noinline void __init check_prealloc(struct maple_tree *mt)\n \tMT_BUG_ON(mt, mas_allocated(\u0026mas) != 0);\n \tmas_set_range(\u0026mas, 0, 200);\n \tmt_set_non_kernel(1);\n-\tMT_BUG_ON(mt, mas_preallocate(\u0026mas, ptr, GFP_KERNEL \u0026 GFP_NOWAIT) == 0);\n+\tMT_BUG_ON(mt, mas_preallocate(\u0026mas, ptr, GFP_NOWAIT) == 0);\n \tallocated = mas_allocated(\u0026mas);\n \theight = mas_mt_height(\u0026mas);\n \tMT_BUG_ON(mt, allocated != 0);\n"
} |
| 2/1 | 2026/07/02 04:23 | agent | patch-evaluator |
0mModel:gemini-3.1-pro-preview Args: null Results: {
"EnableConfigs": [
"DEBUG_MAPLE_TREE",
"PROVE_LOCKING",
"LOCKDEP"
],
"FocusSymbols": [
"mas_alloc_cyclic",
"mas_erase",
"mtree_erase",
"mas_nomem",
"lock_sequence"
],
"Reasoning": "The patch introduces lock sequence validation for maple tree operations using lockdep, and optimizes maple tree node store operations and parent pointer updates. It also fixes wrap-around handling in `mas_alloc_cyclic` and modifies memory allocation behavior in `mas_erase` and `mas_nomem`. These are functional changes to core kernel data structures and locking validation, which should be fuzzed to ensure correctness and prevent regressions.",
"WorthFuzzing": true
}Instruction: You are an expert Linux kernel maintainer. Your job is to review a provided patch series and determine if it makes functional changes to the kernel that should be fuzzed. IMPORTANT: The changes have ALREADY been applied and committed as the HEAD commit in your workspace. Do NOT rely on your internal knowledge of the kernel. You must actively use your code access tools to examine the actual source code and confirm any assumptions. Return WorthFuzzing=false if the patch only contains: - Modifications to Documentation/, Kconfig files, or code comments. - Purely decorative changes, such as logging (e.g., pr_err, printk) or tracepoints. - Changes to numeric constants or macros that do not functionally alter execution flow. - Code paths that are impossible to reach in virtualized environments like GCE or QEMU, even when utilizing software-emulated hardware (e.g., usb gadget, mac80211_hwsim). If it modifies reachable core kernel logic, drivers, or architectures, use your code search tools to verify the code can be executed, then return WorthFuzzing=true. When returning WorthFuzzing=true, you MUST ALSO: 1. Extract any specific kernel functions that should be heavily fuzzed into FocusSymbols. Avoid listing generic hot-path functions to prevent skewed test distributions. 2. Identify any specific CONFIG_ options required to properly test this new/modified feature. Go and look into the Kconfig files and check for ifdefs around the code, do not make assumptions. Do not list too generic configs (we already have them enabled). Only list those that specifically cover the modified code. List them in the EnableConfigs output array, and DO NOT add a 'CONFIG_' prefix (e.g., return "NET_IPV4" instead of "CONFIG_NET_IPV4"). Prefer calling several tools at the same time to save round-trips. Use set-results tool to provide results of the analysis. It must be called exactly once before the final reply. Ignore results of this tool. Prompt: For your convenience, here is the diff of the changes:
commit f5aae681c73dae7feaab013c16095269c01fabaa
Author: syz-cluster <triage@syzkaller.com>
Date: Thu Jul 2 04:23:44 2026 +0000
syz-cluster: applied patch under review
diff --git a/Documentation/core-api/maple_tree.rst b/Documentation/core-api/maple_tree.rst
index ccdd1615cf974f..1eae24a9c18b4a 100644
--- a/Documentation/core-api/maple_tree.rst
+++ b/Documentation/core-api/maple_tree.rst
@@ -17,7 +17,8 @@ supports iterating over a range of entries and going to the previous or next
entry in a cache-efficient manner. The tree can also be put into an RCU-safe
mode of operation which allows reading and writing concurrently. Writers must
synchronize on a lock, which can be the default spinlock, or the user can set
-the lock to an external lock of a different type.
+the lock to an external lock of a different type. Note that external locks may
+interfere with allocations in a low memory situation.
The Maple Tree maintains a small memory footprint and was designed to use
modern processor cache efficiently. The majority of the users will be able to
@@ -42,6 +43,15 @@ successful store operation within a given
code segment when allocating cannot be done. Allocations of nodes are
relatively small at around 256 bytes.
+Since the maple tree uses internal nodes that are allocated and has rules on
+data density, erasing an entry may cause allocations to occur. That is,
+erasing an entry may consume memory. Users must take care to ensure that they
+do not violate the larger system constraints on when and how memory is
+allocated. Most situations are fine to allocate, but the pre-allocation
+support is provided as a mechanism to avoid trickier situations. There is also
+the possibility of using special entries and clean up the tree later, in
+extreme circumstances.
+
.. _maple-tree-normal-api:
Normal API
@@ -63,7 +73,8 @@ success or an error code otherwise. mtree_store_range() works in the same way
but takes a range. mtree_load() is used to retrieve the entry stored at a
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.
+NULL may be used to partially erase a range or many ranges at once. Note that
+mtree_erase() may use GFP_KERNEL on allocations.
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
@@ -163,7 +174,9 @@ You can use mas_erase() to erase an entire range by setting index and
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.
+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``,
+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
to walk each element of the tree then ``0`` and ``ULONG_MAX`` may be used as
@@ -211,7 +224,7 @@ Advanced Locking
The maple tree uses a spinlock by default, but external locks can be used for
tree updates as well. To use an external lock, the tree must be initialized
-with the ``MT_FLAGS_LOCK_EXTERN flag``, this is usually done with the
+with the ``MT_FLAGS_LOCK_EXTERN`` flag, this is usually done with the
MTREE_INIT_EXT() #define, which takes an external lock as an argument.
Functions and structures
diff --git a/include/linux/lockdep.h b/include/linux/lockdep.h
index 621566345406dd..a6451ecbbe9a05 100644
--- a/include/linux/lockdep.h
+++ b/include/linux/lockdep.h
@@ -273,6 +273,9 @@ extern struct pin_cookie lock_pin_lock(struct lockdep_map *lock);
extern void lock_repin_lock(struct lockdep_map *lock, struct pin_cookie);
extern void lock_unpin_lock(struct lockdep_map *lock, struct pin_cookie);
+extern u32 lock_sequence(struct lockdep_map *lock);
+#define lockdep_sequence(lock) lock_sequence(&(lock)->dep_map)
+
#define lockdep_depth(tsk) (debug_locks ? (tsk)->lockdep_depth : 0)
#define lockdep_assert(cond) \
diff --git a/include/linux/lockdep_types.h b/include/linux/lockdep_types.h
index eae115a2648856..55c4b152fedf7c 100644
--- a/include/linux/lockdep_types.h
+++ b/include/linux/lockdep_types.h
@@ -253,7 +253,8 @@ struct held_lock {
unsigned int hardirqs_off:1;
unsigned int sync:1;
unsigned int references:11; /* 32 bits */
- unsigned int pin_count;
+ unsigned int pin_count:24;
+ unsigned int seq_count:8;
};
#else /* !CONFIG_LOCKDEP */
diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h
index 4a5631906affb5..5e0bd2857d941e 100644
--- a/include/linux/maple_tree.h
+++ b/include/linux/maple_tree.h
@@ -29,13 +29,11 @@
#define MAPLE_NODE_SLOTS 31 /* 256 bytes including ->parent */
#define MAPLE_RANGE64_SLOTS 16 /* 256 bytes */
#define MAPLE_ARANGE64_SLOTS 10 /* 240 bytes */
-#define MAPLE_ALLOC_SLOTS (MAPLE_NODE_SLOTS - 1)
#else
/* 32bit sizes */
#define MAPLE_NODE_SLOTS 63 /* 256 bytes including ->parent */
#define MAPLE_RANGE64_SLOTS 32 /* 256 bytes */
#define MAPLE_ARANGE64_SLOTS 21 /* 240 bytes */
-#define MAPLE_ALLOC_SLOTS (MAPLE_NODE_SLOTS - 2)
#endif /* defined(CONFIG_64BIT) || defined(BUILD_VDSO32_64) */
#define MAPLE_NODE_MASK 255UL
@@ -485,6 +483,12 @@ struct ma_state {
unsigned char mas_flags;
unsigned char end; /* The end of the node */
enum store_type store_type; /* The type of store needed for this operation */
+#ifdef CONFIG_LOCKDEP
+ u32 ld_seq;
+#ifdef CONFIG_RCU_STRICT_GRACE_PERIOD
+ unsigned long rcu_gp;
+#endif /* CONFIG_RCU_STRICT_GRACE_PERIOD */
+#endif /* CONFIG_LOCKDEP */
};
struct ma_wr_state {
@@ -572,7 +576,7 @@ void maple_tree_init(void);
void mas_destroy(struct ma_state *mas);
void *mas_prev(struct ma_state *mas, unsigned long min);
-void *mas_prev_range(struct ma_state *mas, unsigned long max);
+void *mas_prev_range(struct ma_state *mas, unsigned long min);
void *mas_next(struct ma_state *mas, unsigned long max);
void *mas_next_range(struct ma_state *mas, unsigned long max);
diff --git a/include/linux/sched.h b/include/linux/sched.h
index 373bcc0598d10b..14d5ce8dd61365 100644
--- a/include/linux/sched.h
+++ b/include/linux/sched.h
@@ -1288,6 +1288,7 @@ struct task_struct {
u64 curr_chain_key;
int lockdep_depth;
unsigned int lockdep_recursion;
+ unsigned int lockdep_seq;
struct held_lock held_locks[MAX_LOCK_DEPTH];
#endif
diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index 2d4c5bab5af887..b2b0a506960b16 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -5077,7 +5077,7 @@ static int __lock_is_held(const struct lockdep_map *lock, int read);
static int __lock_acquire(struct lockdep_map *lock, unsigned int subclass,
int trylock, int read, int check, int hardirqs_off,
struct lockdep_map *nest_lock, unsigned long ip,
- int references, int pin_count, int sync)
+ int references, int pin_count, int sync, int seq)
{
struct task_struct *curr = current;
struct lock_class *class = NULL;
@@ -5183,6 +5183,7 @@ static int __lock_acquire(struct lockdep_map *lock, unsigned int subclass,
hlock->holdtime_stamp = lockstat_clock();
#endif
hlock->pin_count = pin_count;
+ hlock->seq_count = seq;
if (check_wait_context(curr, hlock))
return 0;
@@ -5388,7 +5389,7 @@ static int reacquire_held_locks(struct task_struct *curr, unsigned int depth,
hlock->read, hlock->check,
hlock->hardirqs_off,
hlock->nest_lock, hlock->acquire_ip,
- hlock->references, hlock->pin_count, 0)) {
+ hlock->references, hlock->pin_count, 0, hlock->seq_count)) {
case 0:
return 1;
case 1:
@@ -5684,6 +5685,24 @@ static void __lock_unpin_lock(struct lockdep_map *lock, struct pin_cookie cookie
WARN(1, "unpinning an unheld lock\n");
}
+static u32 __lock_sequence(struct lockdep_map *lock)
+{
+ struct task_struct *curr = current;
+ int i;
+
+ if (unlikely(!debug_locks))
+ return ~0;
+
+ for (i = 0; i < curr->lockdep_depth; i++) {
+ struct held_lock *hlock = curr->held_locks + i;
+
+ if (match_held_lock(hlock, lock))
+ return hlock->seq_count;
+ }
+
+ return ~0;
+}
+
/*
* Check whether we follow the irq-flags state precisely:
*/
@@ -5866,7 +5885,8 @@ void lock_acquire(struct lockdep_map *lock, unsigned int subclass,
lockdep_recursion_inc();
__lock_acquire(lock, subclass, trylock, read, check,
- irqs_disabled_flags(flags), nest_lock, ip, 0, 0, 0);
+ irqs_disabled_flags(flags), nest_lock, ip, 0, 0, 0,
+ ++current->lockdep_seq);
lockdep_recursion_finish();
raw_local_irq_restore(flags);
}
@@ -5914,7 +5934,8 @@ void lock_sync(struct lockdep_map *lock, unsigned subclass, int read,
lockdep_recursion_inc();
__lock_acquire(lock, subclass, 0, read, check,
- irqs_disabled_flags(flags), nest_lock, ip, 0, 0, 1);
+ irqs_disabled_flags(flags), nest_lock, ip, 0, 0, 1,
+ ++current->lockdep_seq);
check_chain_key(current);
lockdep_recursion_finish();
raw_local_irq_restore(flags);
@@ -6000,6 +6021,26 @@ void lock_unpin_lock(struct lockdep_map *lock, struct pin_cookie cookie)
}
EXPORT_SYMBOL_GPL(lock_unpin_lock);
+u32 lock_sequence(struct lockdep_map *lock)
+{
+ unsigned long flags;
+ u32 seq = ~0;
+
+ if (unlikely(!lockdep_enabled()))
+ return seq;
+
+ raw_local_irq_save(flags);
+ check_flags(flags);
+
+ lockdep_recursion_inc();
+ seq = __lock_sequence(lock);
+ lockdep_recursion_finish();
+ raw_local_irq_restore(flags);
+
+ return seq;
+}
+EXPORT_SYMBOL_GPL(lock_sequence);
+
#ifdef CONFIG_LOCK_STAT
static void print_lock_contention_bug(struct task_struct *curr,
struct lockdep_map *lock,
diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index e52876435b77f0..6d71fdc4147064 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -469,7 +469,7 @@ static inline
void mas_set_parent(struct ma_state *mas, struct maple_enode *enode,
const struct maple_enode *parent, unsigned char slot)
{
- unsigned long val = (unsigned long)parent;
+ unsigned long val;
unsigned long shift;
unsigned long type;
enum maple_type p_type = mte_node_type(parent);
@@ -490,11 +490,47 @@ void mas_set_parent(struct ma_state *mas, struct maple_enode *enode,
break;
}
+ val = (unsigned long)parent;
val &= ~MAPLE_NODE_MASK; /* Clear all node metadata in parent */
val |= (slot << shift) | type;
mte_to_node(enode)->parent = ma_parent_ptr(val);
}
+/*
+ * mas_set_parent_slots() - Bulk operation to set many slot parent pointers
+ * @mas: The maple state
+ * @parent: The encoded maple node that is the parent of @enode.
+ * @slot: The slot that of the @enode.
+ * @start_slot: The offset into @slot
+ * @count: The number of slots to set (eg: exclusive)
+ */
+static inline
+void mas_set_parent_slots(struct ma_state *mas, struct maple_enode *parent,
+ void __rcu **slots, unsigned char start_slot, unsigned char count)
+{
+ unsigned long val;
+ unsigned long shift;
+ unsigned long type;
+ enum maple_type p_type = mte_node_type(parent);
+ unsigned char i;
+
+ MAS_BUG_ON(mas, p_type != maple_range_64 &&
+ p_type != maple_arange_64);
+
+ shift = MAPLE_PARENT_SLOT_SHIFT;
+ type = MAPLE_PARENT_RANGE64;
+
+ val = (unsigned long)parent;
+ val &= ~MAPLE_NODE_MASK;
+
+ for (i = 0; i < count; i++) {
+ unsigned long pval = val | ((start_slot + i) << shift) | type;
+ struct maple_enode *child = (struct maple_enode *)slots[i];
+
+ mte_to_node(child)->parent = ma_parent_ptr(pval);
+ }
+}
+
/*
* mte_parent_slot() - get the parent slot of @enode.
* @enode: The encoded maple node.
@@ -1153,6 +1189,70 @@ static inline void mas_free(struct ma_state *mas, struct maple_enode *used)
ma_free_rcu(mte_to_node(used));
}
+
+#ifdef CONFIG_LOCKDEP
+struct lockdep_map *mas_lockdep_map(struct ma_state *mas)
+{
+ struct maple_tree *mt = mas->tree;
+
+ if (mt_external_lock(mt))
+ return mt->ma_external_lock;
+
+ return &(mt->ma_lock).dep_map;
+}
+
+#endif
+
+static void mas_lock_check(struct ma_state *mas)
+{
+
+#ifdef CONFIG_LOCKDEP
+ if (!mas_is_active(mas))
+ return;
+
+#ifdef CONFIG_RCU_STRICT_GRACE_PERIOD
+ if (!mt_lock_is_held(mas->tree)) {
+ if (mt_in_rcu(mas->tree))
+ WARN_ON_ONCE(poll_state_synchronize_rcu(mas->rcu_gp));
+ }
+#endif /* CONFIG_RCU_STRICT_GRACE_PERIOD */
+
+ if (mt_lock_is_held(mas->tree))
+ WARN_ON_ONCE(mas->ld_seq != lock_sequence(mas_lockdep_map(mas)));
+#endif /* CONFIG_LOCKDEP */
+
+}
+
+static void mas_init_lock_check(struct ma_state *mas)
+{
+#ifdef CONFIG_LOCKDEP
+#ifdef CONFIG_RCU_STRICT_GRACE_PERIOD
+ if (!mt_lock_is_held(mas->tree)) {
+ if (mt_in_rcu(mas->tree))
+ mas->rcu_gp = get_state_synchronize_rcu();
+ return;
+ }
+#endif /* CONFIG_RCU_STRICT_GRACE_PERIOD */
+
+ if (mt_lock_is_held(mas->tree))
+ mas->ld_seq = lock_sequence(mas_lockdep_map(mas));
+#endif /* CONFIG_LOCKDEP */
+
+}
+
+static void mas_may_init_lock_check(struct ma_state *mas)
+{
+#ifdef CONFIG_LOCKDEP
+#ifdef CONFIG_RCU_STRICT_GRACE_PERIOD
+ if (mas_is_start(mas) || mas_is_paused(mas)) {
+ mas_init_lock_check(mas);
+ return;
+ }
+#endif /* CONFIG_RCU_STRICT_GRACE_PERIOD */
+ mas_lock_check(mas);
+#endif /* CONFIG_LOCKDEP */
+}
+
/*
* mas_start() - Sets up maple state for operations.
* @mas: The maple state.
@@ -1171,6 +1271,7 @@ static inline struct maple_enode *mas_start(struct ma_state *mas)
if (likely(mas_is_start(mas))) {
struct maple_enode *root;
+ mas_init_lock_check(mas);
mas->min = 0;
mas->max = ULONG_MAX;
@@ -1501,14 +1602,26 @@ static inline void mas_parent_gap(struct ma_state *mas, unsigned char offset,
goto ascend;
}
+static __always_inline void mas_update_gap_known(struct ma_state *mas,
+ unsigned long gap)
+{
+ unsigned char pslot;
+ unsigned long p_gap;
+
+ pslot = mte_parent_slot(mas->node);
+ p_gap = ma_gaps(mte_parent(mas->node),
+ mas_parent_type(mas, mas->node))[pslot];
+
+ if (p_gap != gap)
+ mas_parent_gap(mas, pslot, gap);
+}
+
/*
* mas_update_gap() - Update a nodes gaps and propagate up if necessary.
* @mas: the maple state.
*/
static inline void mas_update_gap(struct ma_state *mas)
{
- unsigned char pslot;
- unsigned long p_gap;
unsigned long max_gap;
if (!mt_is_alloc(mas->tree))
@@ -1518,13 +1631,7 @@ static inline void mas_update_gap(struct ma_state *mas)
return;
max_gap = mas_max_gap(mas);
-
- pslot = mte_parent_slot(mas->node);
- p_gap = ma_gaps(mte_parent(mas->node),
- mas_parent_type(mas, mas->node))[pslot];
-
- if (p_gap != max_gap)
- mas_parent_gap(mas, pslot, max_gap);
+ mas_update_gap_known(mas, max_gap);
}
/*
@@ -1540,14 +1647,10 @@ static inline void mas_adopt_children(struct ma_state *mas,
struct maple_node *node = mte_to_node(parent);
void __rcu **slots = ma_slots(node, type);
unsigned long *pivots = ma_pivots(node, type);
- struct maple_enode *child;
- unsigned char offset;
+ unsigned char end;
- offset = ma_data_end(node, type, pivots, mas->max);
- do {
- child = mas_slot_locked(mas, slots, offset);
- mas_set_parent(mas, child, parent, offset);
- } while (offset--);
+ end = ma_data_end(node, type, pivots, mas->max);
+ mas_set_parent_slots(mas, parent, slots, 0, end + 1);
}
/*
@@ -1929,15 +2032,10 @@ unsigned long node_copy(struct ma_state *mas, struct maple_node *src,
s_slots = ma_slots(src, s_mt) + start;
s_pivots = ma_pivots(src, s_mt) + start;
memcpy(d_slots, s_slots, size * sizeof(void __rcu *));
- if (!ma_is_leaf(d_mt) && s_mt == maple_copy) {
- struct maple_enode *edst = mt_mk_node(dst, d_mt);
-
- for (int i = 0; i < size; i++)
- mas_set_parent(mas,
- mt_slot_locked(mas->tree, d_slots, i),
- edst, d_start + i);
- }
+ if (!ma_is_leaf(d_mt) && s_mt == maple_copy)
+ mas_set_parent_slots(mas, mt_mk_node(dst, d_mt),
+ d_slots, d_start, size);
d_gaps = ma_gaps(dst, d_mt);
if (d_gaps) {
@@ -2081,8 +2179,8 @@ static inline void mas_wmb_replace(struct ma_state *mas, struct maple_copy *cp)
mas->node = mt_slot_locked(mas->tree, cp->slot, 0);
/* Insert the new data in the tree */
mas_topiary_replace(mas, old_enode, cp->height);
- if (!mte_is_leaf(mas->node))
- mas_update_gap(mas);
+ if (mt_is_alloc(mas->tree) && !mte_is_root(mas->node))
+ mas_update_gap_known(mas, cp->gap[0]);
mtree_range_walk(mas);
}
@@ -2928,13 +3026,6 @@ static inline void mas_extend_spanning_null(struct ma_wr_state *l_wr_mas,
if (r_mas->last < r_wr_mas->r_max)
r_mas->last = r_wr_mas->r_max;
r_mas->offset++;
- } else if ((r_mas->last == r_wr_mas->r_max) &&
- (r_mas->last < r_mas->max) &&
- !mas_slot_locked(r_mas, r_wr_mas->slots, r_mas->offset + 1)) {
- r_mas->last = mas_safe_pivot(r_mas, r_wr_mas->pivots,
- r_wr_mas->type, r_mas->offset + 1);
- r_mas->offset++;
- r_wr_mas->r_max = r_mas->last;
}
}
@@ -3125,7 +3216,7 @@ static void mas_wr_spanning_store(struct ma_wr_state *wr_mas)
static inline void mas_wr_node_store(struct ma_wr_state *wr_mas)
{
unsigned char dst_offset, offset_end;
- unsigned char copy_size, node_pivots;
+ unsigned char copy_size, node_pivots, node_slots;
struct maple_node reuse, *newnode;
unsigned long *dst_pivots;
void __rcu **dst_slots;
@@ -3138,6 +3229,7 @@ static inline void mas_wr_node_store(struct ma_wr_state *wr_mas)
in_rcu = mt_in_rcu(mas->tree);
offset_end = wr_mas->offset_end;
node_pivots = mt_pivots[wr_mas->type];
+ node_slots = mt_slots[wr_mas->type];
/* Assume last adds an entry */
new_end = mas->end + 1 - offset_end + mas->offset;
if (mas->last == wr_mas->end_piv) {
@@ -3149,7 +3241,6 @@ static inline void mas_wr_node_store(struct ma_wr_state *wr_mas)
if (in_rcu) {
newnode = mas_pop_node(mas);
} else {
- memset(&reuse, 0, sizeof(struct maple_node));
newnode = &reuse;
}
@@ -3193,7 +3284,17 @@ static inline void mas_wr_node_store(struct ma_wr_state *wr_mas)
dst_pivots[new_end] = mas->max;
done:
- mas_leaf_set_meta(newnode, maple_leaf_64, new_end);
+ if (!in_rcu && new_end + 2 < node_slots) {
+ unsigned char clear_from = new_end + 1;
+
+ memset(dst_slots + clear_from, 0,
+ sizeof(void __rcu *) * (node_slots - clear_from));
+ if (clear_from < node_pivots)
+ memset(dst_pivots + clear_from, 0,
+ sizeof(unsigned long) * (node_pivots - clear_from));
+ }
+
+ mas_leaf_set_meta(newnode, wr_mas->type, new_end);
if (in_rcu) {
struct maple_enode *old_enode = mas->node;
@@ -3218,7 +3319,7 @@ static inline void mas_wr_slot_store(struct ma_wr_state *wr_mas)
void __rcu **slots = wr_mas->slots;
bool gap = false;
- gap |= !mt_slot_locked(mas->tree, slots, offset);
+ gap |= !wr_mas->content;
gap |= !mt_slot_locked(mas->tree, slots, offset + 1);
if (wr_mas->offset_end - offset == 1) {
@@ -3661,6 +3762,9 @@ static inline enum store_type mas_wr_store_type(struct ma_wr_state *wr_mas)
{
struct ma_state *mas = wr_mas->mas;
unsigned char new_end;
+ bool appending;
+ bool one_slot;
+ bool in_rcu;
if (unlikely(mas_is_none(mas) || mas_is_ptr(mas)))
return wr_store_root;
@@ -3680,21 +3784,30 @@ static inline enum store_type mas_wr_store_type(struct ma_wr_state *wr_mas)
return wr_new_root;
new_end = mas_wr_new_end(wr_mas);
+ in_rcu = mt_in_rcu(mas->tree);
+ appending = mas->offset == mas->end;
+ one_slot = wr_mas->offset_end - mas->offset == 1;
+
/* Potential spanning rebalance collapsing a node */
if (new_end < mt_min_slots[wr_mas->type]) {
if (!mte_is_root(mas->node))
return wr_rebalance;
+ if (!in_rcu) {
+ if (appending)
+ return wr_append;
+ else if (mas->end == new_end && one_slot)
+ return wr_slot_store;
+ }
return wr_node_store;
}
if (new_end >= mt_slots[wr_mas->type])
return wr_split_store;
- if (!mt_in_rcu(mas->tree) && (mas->offset == mas->end))
+ if (!in_rcu && appending)
return wr_append;
- if ((new_end == mas->end) && (!mt_in_rcu(mas->tree) ||
- (wr_mas->offset_end - mas->offset == 1)))
+ if (new_end == mas->end && (!in_rcu || one_slot))
return wr_slot_store;
return wr_node_store;
@@ -3793,27 +3906,29 @@ int mas_alloc_cyclic(struct ma_state *mas, unsigned long *startp,
void *entry, unsigned long range_lo, unsigned long range_hi,
unsigned long *next, gfp_t gfp)
{
- unsigned long min = range_lo;
- int ret = 0;
+ int ret;
+ unsigned long min;
- range_lo = max(min, *next);
- ret = mas_empty_area(mas, range_lo, range_hi, 1);
- if ((mas->tree->ma_flags & MT_FLAGS_ALLOC_WRAPPED) && ret == 0) {
- mas->tree->ma_flags &= ~MT_FLAGS_ALLOC_WRAPPED;
- ret = 1;
- }
- if (ret < 0 && range_lo > min) {
- mas_reset(mas);
- ret = mas_empty_area(mas, min, range_hi, 1);
- if (ret == 0)
+ min = range_lo;
+ do {
+ range_lo = max(min, *next);
+ ret = mas_empty_area(mas, range_lo, range_hi, 1);
+ if ((mas->tree->ma_flags & MT_FLAGS_ALLOC_WRAPPED) && ret == 0) {
+ mas->tree->ma_flags &= ~MT_FLAGS_ALLOC_WRAPPED;
ret = 1;
- }
- if (ret < 0)
- return ret;
+ }
+ if (ret < 0 && range_lo > min) {
+ mas_reset(mas);
+ ret = mas_empty_area(mas, min, range_hi, 1);
+ if (ret == 0)
+ ret = 1;
+ }
+ if (ret < 0)
+ return ret;
- do {
mas_insert(mas, entry);
} while (mas_nomem(mas, gfp));
+
if (mas_is_err(mas))
return xa_err(mas->node);
@@ -4360,6 +4475,7 @@ void *mas_walk(struct ma_state *mas)
{
void *entry;
+ mas_may_init_lock_check(mas);
if (!mas_is_active(mas) && !mas_is_start(mas))
mas->status = ma_start;
retry:
@@ -4831,6 +4947,7 @@ void *mas_store(struct ma_state *mas, void *entry)
{
MA_WR_STATE(wr_mas, mas, entry);
+ mas_may_init_lock_check(mas);
trace_ma_write(TP_FCT, mas, 0, entry);
#ifdef CONFIG_DEBUG_MAPLE_TREE
if (MAS_WARN_ON(mas, mas->index > mas->last))
@@ -4889,6 +5006,7 @@ int mas_store_gfp(struct ma_state *mas, void *entry, gfp_t gfp)
MA_WR_STATE(wr_mas, mas, entry);
int ret = 0;
+ mas_may_init_lock_check(mas);
retry:
mas_wr_preallocate(&wr_mas, entry);
if (unlikely(mas_nomem(mas, gfp))) {
@@ -4919,6 +5037,7 @@ void mas_store_prealloc(struct ma_state *mas, void *entry)
{
MA_WR_STATE(wr_mas, mas, entry);
+ mas_lock_check(mas);
if (mas->store_type == wr_store_root) {
mas_wr_prealloc_setup(&wr_mas);
goto store;
@@ -4951,6 +5070,7 @@ int mas_preallocate(struct ma_state *mas, void *entry, gfp_t gfp)
{
MA_WR_STATE(wr_mas, mas, entry);
+ mas_may_init_lock_check(mas);
mas_wr_prealloc_setup(&wr_mas);
mas->store_type = mas_wr_store_type(&wr_mas);
mas_prealloc_calc(&wr_mas, entry);
@@ -5074,6 +5194,7 @@ void *mas_next(struct ma_state *mas, unsigned long max)
{
void *entry = NULL;
+ mas_may_init_lock_check(mas);
if (mas_next_setup(mas, max, &entry))
return entry;
@@ -5097,6 +5218,7 @@ void *mas_next_range(struct ma_state *mas, unsigned long max)
{
void *entry = NULL;
+ mas_may_init_lock_check(mas);
if (mas_next_setup(mas, max, &entry))
return entry;
@@ -5205,6 +5327,7 @@ void *mas_prev(struct ma_state *mas, unsigned long min)
{
void *entry = NULL;
+ mas_may_init_lock_check(mas);
if (mas_prev_setup(mas, min, &entry))
return entry;
@@ -5228,6 +5351,7 @@ void *mas_prev_range(struct ma_state *mas, unsigned long min)
{
void *entry = NULL;
+ mas_may_init_lock_check(mas);
if (mas_prev_setup(mas, min, &entry))
return entry;
@@ -5274,6 +5398,7 @@ EXPORT_SYMBOL_GPL(mt_prev);
*/
void mas_pause(struct ma_state *mas)
{
+ mas_lock_check(mas);
mas->status = ma_pause;
mas->node = NULL;
}
@@ -5382,6 +5507,7 @@ void *mas_find(struct ma_state *mas, unsigned long max)
{
void *entry = NULL;
+ mas_may_init_lock_check(mas);
if (mas_find_setup(mas, max, &entry))
return entry;
@@ -5409,6 +5535,7 @@ void *mas_find_range(struct ma_state *mas, unsigned long max)
{
void *entry = NULL;
+ mas_may_init_lock_check(mas);
if (mas_find_setup(mas, max, &entry))
return entry;
@@ -5428,7 +5555,6 @@ EXPORT_SYMBOL_GPL(mas_find_range);
static bool mas_find_rev_setup(struct ma_state *mas, unsigned long min,
void **entry)
{
-
switch (mas->status) {
case ma_active:
goto active;
@@ -5521,6 +5647,7 @@ void *mas_find_rev(struct ma_state *mas, unsigned long min)
{
void *entry = NULL;
+ mas_may_init_lock_check(mas);
if (mas_find_rev_setup(mas, min, &entry))
return entry;
@@ -5547,6 +5674,7 @@ void *mas_find_range_rev(struct ma_state *mas, unsigned long min)
{
void *entry = NULL;
+ mas_may_init_lock_check(mas);
if (mas_find_rev_setup(mas, min, &entry))
return entry;
@@ -5564,6 +5692,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.
+ *
* Return: the entry that was erased or %NULL, @mas->index and @mas->last are updated.
*/
void *mas_erase(struct ma_state *mas)
@@ -5572,6 +5704,14 @@ void *mas_erase(struct ma_state *mas)
unsigned long index = mas->index;
MA_WR_STATE(wr_mas, mas, NULL);
+ /*
+ * 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.
+ */
+ if (mt_external_lock(mas->tree))
+ might_alloc(GFP_KERNEL);
+
if (!mas_is_active(mas) || !mas_is_start(mas))
mas->status = ma_start;
@@ -5601,10 +5741,11 @@ EXPORT_SYMBOL_GPL(mas_erase);
/**
* mas_nomem() - Check if there was an error allocating and do the allocation
- * if necessary If there are allocations, then free them.
+ * if necessary.
+ *
* @mas: The maple state
* @gfp: The GFP_FLAGS to use for allocations
- * Return: true on allocation, false otherwise.
+ * Return: False on no memory. True otherwise (partial success as well)
*/
bool mas_nomem(struct ma_state *mas, gfp_t gfp)
__must_hold(mas->tree->ma_lock)
@@ -5612,6 +5753,10 @@ bool mas_nomem(struct ma_state *mas, gfp_t gfp)
if (likely(mas->node != MA_ERROR(-ENOMEM)))
return false;
+ /* Allocations can fail, don't do this. */
+ WARN_ON_ONCE(!gfpflags_allow_blocking(gfp) &&
+ mt_external_lock(mas->tree));
+
if (gfpflags_allow_blocking(gfp) && !mt_external_lock(mas->tree)) {
mtree_unlock(mas->tree);
mas_alloc_nodes(mas, gfp);
@@ -5620,10 +5765,17 @@ bool mas_nomem(struct ma_state *mas, gfp_t gfp)
mas_alloc_nodes(mas, gfp);
}
- if (!mas->sheaf && !mas->alloc)
+ /*
+ * 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.
+ */
+ if (WARN_ON_ONCE(!mas->sheaf && !mas->alloc))
return false;
- mas->status = ma_start;
+ mas_reset(mas);
return true;
}
@@ -5913,6 +6065,10 @@ 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.
+ *
* Return: The entry stored at the @index or %NULL
*/
void *mtree_erase(struct maple_tree *mt, unsigned long index)
diff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/maple.c
index 0607913a3022d5..d967e76a3c0650 100644
--- a/tools/testing/radix-tree/maple.c
+++ b/tools/testing/radix-tree/maple.c
@@ -35234,7 +35234,7 @@ static noinline void __init check_prealloc(struct maple_tree *mt)
mt_set_non_kernel(1);
/* Spanning store */
mas_set_range(&mas, 1, 100);
- MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL & GFP_NOWAIT) == 0);
+ MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_NOWAIT) == 0);
allocated = mas_allocated(&mas);
height = mas_mt_height(&mas);
MT_BUG_ON(mt, allocated != 0);
@@ -35257,7 +35257,7 @@ static noinline void __init check_prealloc(struct maple_tree *mt)
MT_BUG_ON(mt, mas_allocated(&mas) != 0);
mas_set_range(&mas, 0, 200);
mt_set_non_kernel(1);
- MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL & GFP_NOWAIT) == 0);
+ MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_NOWAIT) == 0);
allocated = mas_allocated(&mas);
height = mas_mt_height(&mas);
MT_BUG_ON(mt, allocated != 0);
|
| 3/2 | 2026/07/02 04:23 | llm | patch-evaluator |
0mModel:gemini-3.1-pro-preview Args: null Results: null Tokens: input: 13118 output: 21 thoughts: 856 Thoughts: **Patch Evaluation for Fuzzing: Maple Tree and Lockdep Integration** Okay, so I've got this patch, and my initial assessment is that this warrants a deep dive for fuzzing. It's touching some pretty critical areas: the `Documentation`, `include` files for core locking and the `maple_tree`, and then, most significantly, the kernel implementation itself – specifically `lockdep.c` and `lib/maple_tree.c`, along with a test file. Given my expertise, I immediately recognize this as a functional change, not just a refactor. A new `lock_sequence()` function in `lockdep` is being introduced and then leveraged within the maple tree code to enforce lock ordering. This screams potential for interesting concurrency bugs if not handled perfectly. Absolutely, this is fuzz-worthy! Now, let's zoom in on the specific functions modified, particularly in `lib/maple_tree.c`. I need to understand the scope. I see it touches a *lot* of functions. Seems the patch has quite a broad impact on the locking semantics around the core maple tree operations. I see it impacts many functions: `mas_set_parent`, `mas_set_parent_slots`, `mas_lockdep_map`, `mas_lock_check`, `mas_init_lock_check`, `mas_may_init_lock_check`, `mas_start`, `mas_update_gap_known`, `mas_update_gap`, `mas_adopt_children`, `node_copy`, `mas_wmb_replace`, `mas_extend_spanning_null`, `mas_wr_node_store`, `mas_wr_slot_store`, `mas_wr_store_type`, `mas_alloc_cyclic`, `mas_walk`, `mas_store`, `mas_store_gfp`, `mas_store_prealloc`, `mas_preallocate`, `mas_next`, `mas_next_range`, `mas_prev`, `mas_prev_range`, `mas_pause`, `mas_find`, `mas_find_range`, `mas_find_rev_setup`, `mas_find_rev`, `mas_find_range_rev`, `mas_erase`, `mas_nomem`, `mtree_erase`. And then, looking at `kernel/locking/lockdep.c`, I see core locking functions are affected too, that can be a signal of a core issue: `__lock_acquire`, `reacquire_held_locks`, `__lock_sequence`, `lock_acquire`, `lock_sync`, `lock_sequence`. Therefore, I need to prioritize my fuzzing efforts. The focus should be on those maple tree functions and those lockdep sequence functions which are most likely to introduce a bug. Lockdep itself is a debugging tool, so the risk is somewhat lower in *it* but still possible to create bugs. But the maple tree is a core data structure, so I'll need to pay extra attention to that! Let me list some key maple tree functions to highlight these critical areas: `mas_alloc_cyclic`, `mas_erase`, `mtree_erase`, `mas_nomem`, `mas_wr_node_store`, `mas_wr_store_type`, `mas_update_gap_known`, `mas_set_parent_slots`. Now, before I launch into fuzzing, I need to make sure I get the configuration right. I'll need `CONFIG_LOCKDEP` enabled for these lock sequence checks to actually function. `CONFIG_DEBUG_MAPLE_TREE` *might* be helpful during analysis, but standard maple tree is almost always enabled. It is always good to check `lib/Kconfig.debug` to double check any helpful configurations there. Now, let's get fuzzing! |
| 4/2 | 2026/07/02 04:23 | tool | grepper |
0mArgs:{
"Expression": "config DEBUG_MAPLE_TREE"
}Results: {
"Output": "lib/Kconfig.debug=1825=config DEBUG_CLOSURES\n--\nlib/Kconfig.debug-1833-\nlib/Kconfig.debug:1834:config DEBUG_MAPLE_TREE\nlib/Kconfig.debug-1835-\tbool \"Debug maple trees\"\n"
} |
| 5/2 | 2026/07/02 04:24 | llm | patch-evaluator |
0mModel:gemini-3.1-pro-preview Args: null Results: null Tokens: input: 14899 output: 19 thoughts: 78 Thoughts: Okay, here's my take on those thoughts, framed as my own reasoning: **Checking Lockdep and Maple Tree Configuration** Right, so I see `DEBUG_MAPLE_TREE` listed as a configuration option, and I also note `PROVE_LOCKING` or `LOCKDEP` in the context of lockdep changes. That's the key. I need to dive into those lockdep modifications now. First, I need to confirm the primary settings. It looks like `lock_sequence` is exported, which is important for understanding how the locking works. Ah, here it is: `CONFIG_LOCKDEP` is the crucial configuration option. That's the main switch for enabling the lock dependency checker. That's the setting that tells the kernel to pay attention to potential lock problems. Now, let me shift gears a bit. I need to track down the usage of `mas_alloc_cyclic`. Let me see where that comes into play. It's related somehow to this lockdep stuff. |
| 6/2 | 2026/07/02 04:24 | tool | grepper |
0mArgs:{
"Expression": "mas_alloc_cyclic"
}Results: {
"Output": "include/linux/maple_tree.h=568=int mas_preallocate(struct ma_state *mas, void *entry, gfp_t gfp);\ninclude/linux/maple_tree.h:569:int mas_alloc_cyclic(struct ma_state *mas, unsigned long *startp,\ninclude/linux/maple_tree.h-570-\t\tvoid *entry, unsigned long range_lo, unsigned long range_hi,\n--\nlib/maple_tree.c=3843=static inline void *mas_insert(struct ma_state *mas, void *entry)\n--\nlib/maple_tree.c-3891-/**\nlib/maple_tree.c:3892: * mas_alloc_cyclic() - Internal call to find somewhere to store an entry\nlib/maple_tree.c-3893- * @mas: The maple state.\n--\nlib/maple_tree.c-3904- */\nlib/maple_tree.c:3905:int mas_alloc_cyclic(struct ma_state *mas, unsigned long *startp,\nlib/maple_tree.c-3906-\t\tvoid *entry, unsigned long range_lo, unsigned long range_hi,\n--\nlib/maple_tree.c-3942-}\nlib/maple_tree.c:3943:EXPORT_SYMBOL(mas_alloc_cyclic);\nlib/maple_tree.c-3944-\n--\nlib/maple_tree.c=6001=int mtree_alloc_cyclic(struct maple_tree *mt, unsigned long *startp,\n--\nlib/maple_tree.c-6013-\tmtree_lock(mt);\nlib/maple_tree.c:6014:\tret = mas_alloc_cyclic(\u0026mas, startp, entry, range_lo, range_hi,\nlib/maple_tree.c-6015-\t\t\t next, gfp);\n--\nlib/test_maple_tree.c=3646=static noinline void __init alloc_cyclic_testing(struct maple_tree *mt)\n--\nlib/test_maple_tree.c-3655-\tfor (int i = 0; i \u003c 100; i++) {\nlib/test_maple_tree.c:3656:\t\tmas_alloc_cyclic(\u0026mas, \u0026location, mt, 2, ULONG_MAX, \u0026next, GFP_KERNEL);\nlib/test_maple_tree.c-3657-\t\tMAS_BUG_ON(\u0026mas, i != location - 2);\n--\nlib/test_maple_tree.c-3679-\t * Exhausting the allocation area and forcing the search to wrap needs a\nlib/test_maple_tree.c:3680:\t * mas_reset() in mas_alloc_cyclic().\nlib/test_maple_tree.c-3681-\t */\n"
} |
| 7/2 | 2026/07/02 04:24 | llm | patch-evaluator |
0mModel:gemini-3.1-pro-preview Args: null Results: null Tokens: input: 15944 output: 17 thoughts: 11 Thoughts: Okay, let's dive into this. Here's how I'd approach summarizing the prompt, keeping in mind my expertise: **Checking `mas_erase` Usage** Alright, before I get too deep into this, I need to understand the context. The prompt is incredibly specific - it mentions `mas_erase`. My initial thought is to figure out *why* we're focusing on this particular function. Is there a specific problem that this suggests? It could be related to memory management, security vulnerabilities, or perhaps data sanitation. My mind immediately starts running through possible scenarios based on my experience. My next step would be to figure out if it's the right function to use, to confirm that it's the best option here. |
| 8/2 | 2026/07/02 04:24 | tool | grepper |
0mArgs:{
"Expression": "mas_erase"
}Results: {
"Output": "Documentation/core-api/maple_tree.rst=171=The range is passed in as members of the maple state: index and last.\nDocumentation/core-api/maple_tree.rst-172-\nDocumentation/core-api/maple_tree.rst:173:You can use mas_erase() to erase an entire range by setting index and\nDocumentation/core-api/maple_tree.rst-174-last of the maple state to the desired range to erase. This will erase\n--\nDocumentation/core-api/maple_tree.rst=176=and last as the range that was erased and return the entry that existed\nDocumentation/core-api/maple_tree.rst:177:at that location. Note that mas_erase() may allocate with the GFP_KERNEL flag.\nDocumentation/core-api/maple_tree.rst-178-If this is not okay, consider using mas_store_gfp() and pass it a ``NULL``,\n--\ndrivers/base/regmap/regcache-maple.c=107=static int regcache_maple_drop(struct regmap *map, unsigned int min,\n--\ndrivers/base/regmap/regcache-maple.c-159-\t\tmas_lock(\u0026mas);\ndrivers/base/regmap/regcache-maple.c:160:\t\tmas_erase(\u0026mas);\ndrivers/base/regmap/regcache-maple.c-161-\n--\ndrivers/block/ublk_drv.c=5311=static void ublk_buf_erase_ranges(struct ublk_device *ub, int buf_index)\n--\ndrivers/block/ublk_drv.c-5318-\t\tif (range-\u003ebuf_index == buf_index) {\ndrivers/block/ublk_drv.c:5319:\t\t\tmas_erase(\u0026mas);\ndrivers/block/ublk_drv.c-5320-\t\t\tkfree(range);\n--\ndrivers/block/ublk_drv.c=5480=static bool __ublk_shmem_remove_ranges(struct ublk_device *ub,\n--\ndrivers/block/ublk_drv.c-5504-\t\t\tgoto unlock;\ndrivers/block/ublk_drv.c:5505:\t\tmas_erase(\u0026mas);\ndrivers/block/ublk_drv.c-5506-\t\tkfree(range);\n--\ndrivers/gpu/drm/nouveau/nouveau_uvmm.c=323=nouveau_uvma_region_remove(struct nouveau_uvma_region *reg)\n--\ndrivers/gpu/drm/nouveau/nouveau_uvmm.c-327-\ndrivers/gpu/drm/nouveau/nouveau_uvmm.c:328:\tmas_erase(\u0026mas);\ndrivers/gpu/drm/nouveau/nouveau_uvmm.c-329-}\n--\ndrivers/gpu/drm/nouveau/nouveau_uvmm.c=1962=nouveau_uvmm_fini(struct nouveau_uvmm *uvmm)\n--\ndrivers/gpu/drm/nouveau/nouveau_uvmm.c-1990-\tmas_for_each(\u0026mas, reg, ULONG_MAX) {\ndrivers/gpu/drm/nouveau/nouveau_uvmm.c:1991:\t\tmas_erase(\u0026mas);\ndrivers/gpu/drm/nouveau/nouveau_uvmm.c-1992-\t\tnouveau_uvma_region_sparse_unref(reg);\n--\ndrivers/iommu/generic_pt/kunit_iommu_pt.h=287=static void unmap_collisions(struct kunit *test, struct maple_tree *mt,\n--\ndrivers/iommu/generic_pt/kunit_iommu_pt.h-299-\ndrivers/iommu/generic_pt/kunit_iommu_pt.h:300:\t\tmas_erase(\u0026mas);\ndrivers/iommu/generic_pt/kunit_iommu_pt.h-301-\t\tmas_pause(\u0026mas);\n--\ninclude/linux/maple_tree.h=560=void *mas_store(struct ma_state *mas, void *entry);\ninclude/linux/maple_tree.h:561:void *mas_erase(struct ma_state *mas);\ninclude/linux/maple_tree.h-562-int mas_store_gfp(struct ma_state *mas, void *entry, gfp_t gfp);\n--\nkernel/irq/irqdesc.c=198=static void delete_irq_desc(unsigned int irq)\n--\nkernel/irq/irqdesc.c-200-\tMA_STATE(mas, \u0026sparse_irqs, irq, irq);\nkernel/irq/irqdesc.c:201:\tmas_erase(\u0026mas);\nkernel/irq/irqdesc.c-202-}\n--\nlib/maple_tree.c=5684=EXPORT_SYMBOL_GPL(mas_find_range_rev);\n--\nlib/maple_tree.c-5686-/**\nlib/maple_tree.c:5687: * mas_erase() - Find the range in which index resides and erase the entire\nlib/maple_tree.c-5688- * range.\n--\nlib/maple_tree.c-5700- */\nlib/maple_tree.c:5701:void *mas_erase(struct ma_state *mas)\nlib/maple_tree.c-5702-{\n--\nlib/maple_tree.c-5739-}\nlib/maple_tree.c:5740:EXPORT_SYMBOL_GPL(mas_erase);\nlib/maple_tree.c-5741-\n--\nlib/maple_tree.c=6074=void *mtree_erase(struct maple_tree *mt, unsigned long index)\n--\nlib/maple_tree.c-6081-\tmtree_lock(mt);\nlib/maple_tree.c:6082:\tentry = mas_erase(\u0026mas);\nlib/maple_tree.c-6083-\tmtree_unlock(mt);\n--\nlib/test_maple_tree.c=387=static noinline void __init check_find(struct maple_tree *mt)\n--\nlib/test_maple_tree.c-578-\tmas.last = ULONG_MAX;\nlib/test_maple_tree.c:579:\tmas_erase(\u0026mas);\nlib/test_maple_tree.c-580-\n--\nmm/alloc_tag.c=373=static void clean_unused_module_areas_locked(void)\n--\nmm/alloc_tag.c-388-\t\tif (clean_unused_counters(start_tag, end_tag))\nmm/alloc_tag.c:389:\t\t\tmas_erase(\u0026mas);\nmm/alloc_tag.c-390-\t}\n--\nmm/alloc_tag.c=484=static void *reserve_module_tags(struct module *mod, unsigned long size,\n--\nmm/alloc_tag.c-533-\t\t\tmas.index = pad_start;\nmm/alloc_tag.c:534:\t\t\tmas_erase(\u0026mas);\nmm/alloc_tag.c-535-\t\t\tret = ERR_PTR(xa_err(mas.node));\n--\ntools/testing/radix-tree/maple.c=35902=static noinline void __init check_erase_rebalance(struct maple_tree *mt)\n--\ntools/testing/radix-tree/maple.c-35947-\twhile (mas_data_end(\u0026mas) \u003e 6) {\ntools/testing/radix-tree/maple.c:35948:\t\tmas_erase(\u0026mas);\ntools/testing/radix-tree/maple.c-35949-\t\tmas_next(\u0026mas, ULONG_MAX);\n--\ntools/testing/radix-tree/maple.c-35959-\twhile (mas_data_end(\u0026mas) \u003e 9) {\ntools/testing/radix-tree/maple.c:35960:\t\tmas_erase(\u0026mas);\ntools/testing/radix-tree/maple.c-35961-\t\tmas_next(\u0026mas, ULONG_MAX);\n--\ntools/testing/radix-tree/maple.c-35969-\t\tmas_set(\u0026mas, val);\ntools/testing/radix-tree/maple.c:35970:\t\tmas_erase(\u0026mas);\ntools/testing/radix-tree/maple.c-35971-\t\tmas_prev(\u0026mas, 0);\n--\ntools/testing/radix-tree/maple.c=36200=static void check_collapsing_rebalance(struct maple_tree *mt)\n--\ntools/testing/radix-tree/maple.c-36212-\tdo {\ntools/testing/radix-tree/maple.c:36213:\t\tmas_erase(\u0026mas);\ntools/testing/radix-tree/maple.c-36214-\t} while (mas_prev(\u0026mas, 0) != NULL);\n--\ntools/testing/radix-tree/maple.c=36240=static void check_nomem_writer_race(struct maple_tree *mt)\n--\ntools/testing/radix-tree/maple.c-36255-\t/* erase 0-5 */\ntools/testing/radix-tree/maple.c:36256:\tmas_erase(\u0026mas);\ntools/testing/radix-tree/maple.c-36257-\n"
} |
| 9/2 | 2026/07/02 04:24 | llm | patch-evaluator |
0mModel:gemini-3.1-pro-preview Args: null Results: null Tokens: input: 18567 output: 21 thoughts: 1811 Thoughts: **Maple Tree Lockdep and Store Optimization** Okay, so I've been digging into this patch, and here's my take on the changes. The initial addition of `mas_lock_check`, `mas_init_lock_check`, and `mas_may_init_lock_check`, all leveraging `lock_sequence`, are clearly about integrating lockdep into the Maple Tree. This is a solid move for improving debugging and ensuring proper locking behavior, which is critical for complex data structures like this. I'll need to remember that `CONFIG_LOCKDEP` and potentially `CONFIG_PROVE_LOCKING` (which enables `LOCKDEP`) and `CONFIG_DEBUG_MAPLE_TREE` (which depends on `DEBUG_KERNEL`) will be essential for testing this properly. The real meat of the changes, however, seems to be focused on optimizing the `mas_wr_node_store` and `mas_wr_store_type` functions. In `mas_wr_node_store`, instead of a full `memset` on `reuse` for the new node, there's a more targeted clearing of unused slots and pivots at the end of the node. This looks like a performance improvement by reducing unnecessary memory writes, which is always welcome. I need to pay close attention to the `node_slots` and `node_pivots` variables here, to be sure this is correct. `mas_wr_store_type` is also modified, to more intelligently classify store types. There's added logic to determine if the store is an append, a slot store, or rebalance based on factors like new_end, `in_rcu`, `appending`, and `one_slot`. This is a crucial area for performance, and the code looks like it makes these new checks properly. I will need to really focus on this code section for testing. I also see they have also modified `mas_alloc_cyclic`, and am not sure if it is a side effect of the other changes. The modifications to `mas_erase` are interesting, with the addition of the `might_alloc` call within an external lock check. This is designed for low-memory situations, and this looks like a reasonable approach. I need to make a note of this. Finally, the changes to `mas_nomem` are also important. The `WARN_ON_ONCE` and the logic around external locks and blocking GFP flags is crucial for preventing deadlocks and handling memory allocation failures gracefully. The new `mas_reset(mas)` call is added to handle this. So, overall, these patches are focused on performance improvements and robustness. The optimization of memory writes in the node store is good, and the improved store type determination looks beneficial. Lockdep integration is a solid addition, and the low-memory handling seems well thought out. I'll need to focus my fuzzing efforts on `mas_wr_node_store`, `mas_wr_store_type`, `mas_alloc_cyclic`, `mas_erase`, and `mas_nomem`. I will also have to add `mas_set_parent_slots` and `mas_update_gap_known` to my fuzz list to make sure I cover all changes. |
| 10/2 | 2026/07/02 04:24 | tool | grepper |
0mArgs:{
"Expression": "mas_set_parent_slots"
}Results: {
"Output": "lib/maple_tree.c=469=void mas_set_parent(struct ma_state *mas, struct maple_enode *enode,\n--\nlib/maple_tree.c-499-/*\nlib/maple_tree.c:500: * mas_set_parent_slots() - Bulk operation to set many slot parent pointers\nlib/maple_tree.c-501- * @mas: The maple state\n--\nlib/maple_tree.c=507=static inline\nlib/maple_tree.c:508:void mas_set_parent_slots(struct ma_state *mas, struct maple_enode *parent,\nlib/maple_tree.c-509-\tvoid __rcu **slots, unsigned char start_slot, unsigned char count)\n--\nlib/maple_tree.c=1643=static inline void mas_adopt_children(struct ma_state *mas,\n--\nlib/maple_tree.c-1652-\tend = ma_data_end(node, type, pivots, mas-\u003emax);\nlib/maple_tree.c:1653:\tmas_set_parent_slots(mas, parent, slots, 0, end + 1);\nlib/maple_tree.c-1654-}\n--\nlib/maple_tree.c=2020=unsigned long node_copy(struct ma_state *mas, struct maple_node *src,\n--\nlib/maple_tree.c-2036-\tif (!ma_is_leaf(d_mt) \u0026\u0026 s_mt == maple_copy)\nlib/maple_tree.c:2037:\t\tmas_set_parent_slots(mas, mt_mk_node(dst, d_mt),\nlib/maple_tree.c-2038-\t\t\t\t d_slots, d_start, size);\n"
} |
| 11/2 | 2026/07/02 04:24 | llm | patch-evaluator |
0mModel:gemini-3.1-pro-preview Args: null Results: null Tokens: input: 21557 output: 170 thoughts: 933 Thoughts: **Refining the Focus for Maple Tree Lock Sequence Validation and Optimization** Okay, let's break this down. My initial thought was to consider the following symbols, particularly given the context of lock sequence validation and optimization within the Maple Tree: `mas_wr_node_store`, `mas_wr_store_type`, `mas_alloc_cyclic`, `mas_erase`, `mas_nomem`, `mas_set_parent_slots`, `mas_update_gap_known`, `mas_lock_check`, `mas_init_lock_check`, and `mas_may_init_lock_check`. However, since some are `static` or `static inline`, they might be inlined, so they're not useful entry points for analysis. I know this patch is introducing lock sequence validation using `lockdep`, optimizing store operations, and fixing wrap-around in memory allocation, specifically in the Maple Tree implementation. So, I decided to focus on the following non-inline or exported functions: `mas_alloc_cyclic`, `mas_erase`, `mtree_erase`, `mas_nomem`, and `lock_sequence`. I also initially identified the functions that call the static inline functions like `mas_store`, `mas_store_gfp`, `mas_store_prealloc`, and `mas_preallocate`, but these are likely hot path functions. Avoiding hot paths is important here. So, I need to focus on the functions I just listed: `mas_alloc_cyclic`, `mas_erase`, `mtree_erase`, `mas_nomem`, and `lock_sequence`. I'm verifying that `mas_alloc_cyclic` is used in `mtree_alloc_cyclic`, `mas_erase` is used in `mtree_erase` and a few drivers, and `mas_nomem` is used in memory allocation failure cases. The configurations of interest are `DEBUG_MAPLE_TREE`, `PROVE_LOCKING`, and `LOCKDEP`. These functions and configs represent a good starting point for detailed inspection and possible fuzzing efforts. |
| 12/2 | 2026/07/02 04:24 | tool | set-results |
0mArgs:{
"EnableConfigs": [
"DEBUG_MAPLE_TREE",
"PROVE_LOCKING",
"LOCKDEP"
],
"FocusSymbols": [
"mas_alloc_cyclic",
"mas_erase",
"mtree_erase",
"mas_nomem",
"lock_sequence"
],
"Reasoning": "The patch introduces lock sequence validation for maple tree operations using lockdep, and optimizes maple tree node store operations and parent pointer updates. It also fixes wrap-around handling in `mas_alloc_cyclic` and modifies memory allocation behavior in `mas_erase` and `mas_nomem`. These are functional changes to core kernel data structures and locking validation, which should be fuzzed to ensure correctness and prevent regressions.",
"WorthFuzzing": true
}Results: {
"EnableConfigs": [
"DEBUG_MAPLE_TREE",
"PROVE_LOCKING",
"LOCKDEP"
],
"FocusSymbols": [
"mas_alloc_cyclic",
"mas_erase",
"mtree_erase",
"mas_nomem",
"lock_sequence"
],
"Reasoning": "The patch introduces lock sequence validation for maple tree operations using lockdep, and optimizes maple tree node store operations and parent pointer updates. It also fixes wrap-around handling in `mas_alloc_cyclic` and modifies memory allocation behavior in `mas_erase` and `mas_nomem`. These are functional changes to core kernel data structures and locking validation, which should be fuzzed to ensure correctness and prevent regressions.",
"WorthFuzzing": true
} |
| Total Calls | Total Tokens | Avg Tokens | Total Duration (Seconds) | Avg Duration (Seconds) |
|---|
| Total Calls | Total Duration (Seconds) | Avg Duration (Seconds) |
|---|