RCU readers may hit a NULL dereference if the tree is emptied while the walker is restarted from a dead node. Avoid the NULL dereference by checking for an emptied/pointer tree (0->ptr, 1-ULONG_MAX -> NULL) and set the maple state limits correctly. Initial fix was generated by LLM and sent by Chris Mason in private. Cc: Fixes: fff4a58cc00b ("maple_tree: introduce mas_next_slot() interface") Reported-by: Chris Mason Signed-off-by: Liam R. Howlett (Google) --- lib/maple_tree.c | 110 +++++++++++++++++++++++++++++++++++------------ 1 file changed, 83 insertions(+), 27 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 0b0036c9f8489..22812ed49be5a 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -3891,14 +3891,54 @@ static __always_inline void mas_rewalk(struct ma_state *mas, unsigned long index goto retry; } -static __always_inline bool mas_rewalk_if_dead(struct ma_state *mas, - struct maple_node *node, const unsigned long index) +/* + * mas_next_no_node() - Finish a next walk that restarted into a tree without + * nodes. + * @mas: The inactive maple state (ma_none or ma_root) + * + * The arrival here is either because there is a root value or nothing. Either + * way, the next entry is nothing. So set the limits and overwrite the status. + * + * Return: NULL + */ +static inline void *mas_next_no_node(struct ma_state *mas) { - if (unlikely(ma_dead_node(node))) { - mas_rewalk(mas, index); - return true; + if (mas_is_ptr(mas)) + mas->index = 1; + else + mas->index = 0; + + mas->last = ULONG_MAX; + mas->status = ma_none; + return NULL; +} + +/* + * mas_prev_no_node() - Finish a prev walk that restarted into a tree without + * nodes. + * @mas: The inactive maple state (ma_none or ma_root) + * @min: The lowest index to return + * + * The arrival here is either because there is a root value or nothing. With + * nothing, leave the limits mas_walk() sets for an empty tree. A root value + * sits at 0, before the saved index: stop on it as mas_prev_setup() does. + * + * Return: The root entry if @min allows it, NULL otherwise. A node if the + * root changed again since the walk; the caller restarts. + */ +static inline void *mas_prev_no_node(struct ma_state *mas, unsigned long min) +{ + mas->index = 0; + if (mas_is_none(mas)) { + mas->last = ULONG_MAX; + return NULL; } - return false; + + mas->last = 0; + if (min) + return NULL; + + return mas_root(mas); } /* @@ -4006,14 +4046,14 @@ static void *mas_prev_slot(struct ma_state *mas, unsigned long min, bool empty) node = mas_mn(mas); type = mte_node_type(mas->node); pivots = ma_pivots(node, type); - if (unlikely(mas_rewalk_if_dead(mas, node, save_point))) - goto retry; + if (unlikely(ma_dead_node(node))) + goto dead; if (mas->min <= min) { pivot = mas_safe_min(mas, pivots, mas->offset); - if (unlikely(mas_rewalk_if_dead(mas, node, save_point))) - goto retry; + if (unlikely(ma_dead_node(node))) + goto dead; if (pivot <= min) goto underflow; @@ -4028,10 +4068,8 @@ static void *mas_prev_slot(struct ma_state *mas, unsigned long min, bool empty) if (mas->index <= min) goto underflow; - if (mas_prev_node(mas, min)) { - mas_rewalk(mas, save_point); - goto retry; - } + if (mas_prev_node(mas, min)) + goto dead; if (WARN_ON_ONCE(mas_is_underflow(mas))) return NULL; @@ -4045,8 +4083,8 @@ static void *mas_prev_slot(struct ma_state *mas, unsigned long min, bool empty) slots = ma_slots(node, type); entry = mas_slot(mas, slots, mas->offset); - if (unlikely(mas_rewalk_if_dead(mas, node, save_point))) - goto retry; + if (unlikely(ma_dead_node(node))) + goto dead; if (likely(entry)) return entry; @@ -4063,6 +4101,17 @@ static void *mas_prev_slot(struct ma_state *mas, unsigned long min, bool empty) underflow: mas->status = ma_underflow; return NULL; + +dead: + mas_rewalk(mas, save_point); + if (likely(mas_is_active(mas))) + goto retry; + + entry = mas_prev_no_node(mas, min); + if (unlikely(xa_is_node(entry))) /* The root changed again */ + goto dead; + + return entry; } /* @@ -4176,8 +4225,8 @@ static void *mas_next_slot(struct ma_state *mas, unsigned long max, bool empty) node = mas_mn(mas); type = mte_node_type(mas->node); pivots = ma_pivots(node, type); - if (unlikely(mas_rewalk_if_dead(mas, node, save_point))) - goto retry; + if (unlikely(ma_dead_node(node))) + goto dead; if (mas->max >= max) { if (likely(mas->offset < mas->end)) @@ -4185,8 +4234,8 @@ static void *mas_next_slot(struct ma_state *mas, unsigned long max, bool empty) else pivot = mas->max; - if (unlikely(mas_rewalk_if_dead(mas, node, save_point))) - goto retry; + if (unlikely(ma_dead_node(node))) + goto dead; if (pivot >= max) { /* Was at the limit, next will extend beyond */ mas->status = ma_overflow; @@ -4208,10 +4257,8 @@ static void *mas_next_slot(struct ma_state *mas, unsigned long max, bool empty) return NULL; } - if (mas_next_node(mas, node, max)) { - mas_rewalk(mas, save_point); - goto retry; - } + if (mas_next_node(mas, node, max)) + goto dead; if (WARN_ON_ONCE(mas_is_overflow(mas))) return NULL; @@ -4226,8 +4273,8 @@ static void *mas_next_slot(struct ma_state *mas, unsigned long max, bool empty) slots = ma_slots(node, type); entry = mt_slot(mas->tree, slots, mas->offset); - if (unlikely(mas_rewalk_if_dead(mas, node, save_point))) - goto retry; + if (unlikely(ma_dead_node(node))) + goto dead; if (entry) return entry; @@ -4244,6 +4291,13 @@ static void *mas_next_slot(struct ma_state *mas, unsigned long max, bool empty) } return entry; + +dead: + mas_rewalk(mas, save_point); + if (likely(mas_is_active(mas))) + goto retry; + + return mas_next_no_node(mas); } /* @@ -5450,7 +5504,9 @@ void *mas_find(struct ma_state *mas, unsigned long max) /* Retries on dead nodes handled by mas_next_slot */ entry = mas_next_slot(mas, max, false); /* Ignore overflow */ - mas->status = ma_active; + if (mas_is_overflow(mas)) + mas->status = ma_active; + return entry; } EXPORT_SYMBOL_GPL(mas_find); -- 2.47.3 Add a test case for the rcu reader being restarted by emptying the tree. Signed-off-by: Liam R. Howlett (Google) --- lib/test_maple_tree.c | 129 ++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 129 insertions(+) diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c index fb40e193a3cb7..894f5893e1be2 100644 --- a/lib/test_maple_tree.c +++ b/lib/test_maple_tree.c @@ -3740,6 +3740,134 @@ static noinline void __init check_range64_in_rcu(struct maple_tree *mt) rcu_barrier(); } +/* + * A reader that restarts after its leaf died may find a tree without nodes: + * emptied, or emptied and then given a single entry at 0. Each case starts + * from a tree with nodes, built by check_seq(). The stores run while the + * reader holds rcu_read_lock, so they use GFP_ATOMIC. + */ +static noinline void __init check_restart_no_node(struct maple_tree *mt) +{ + void *ptr = xa_mk_value(1234); + void *entry; + MA_STATE(mas, mt, 0, 0); + + MT_BUG_ON(mt, !mtree_empty(mt)); + mt_set_non_kernel(99999); + + /* find: the tree is emptied */ + mt_init_flags(mt, MT_FLAGS_USE_RCU); + check_seq(mt, 100, false); + rcu_read_lock(); + mas_set(&mas, 0); + entry = mas_find(&mas, ULONG_MAX); + MT_BUG_ON(mt, entry != xa_mk_value(0)); + MT_BUG_ON(mt, mtree_store_range(mt, 0, ULONG_MAX, NULL, GFP_ATOMIC)); + entry = mas_find(&mas, ULONG_MAX); + MT_BUG_ON(mt, entry != NULL); + MT_BUG_ON(mt, mas.status != ma_none); + MT_BUG_ON(mt, mas.index != 0); + MT_BUG_ON(mt, mas.last != ULONG_MAX); + entry = mas_find(&mas, ULONG_MAX); + MT_BUG_ON(mt, entry != NULL); + MT_BUG_ON(mt, mas.status != ma_none); + rcu_read_unlock(); + mtree_destroy(mt); + rcu_barrier(); + + /* next: the tree is emptied */ + mt_init_flags(mt, MT_FLAGS_USE_RCU); + check_seq(mt, 100, false); + rcu_read_lock(); + mas_set(&mas, 0); + entry = mas_find(&mas, ULONG_MAX); + MT_BUG_ON(mt, entry != xa_mk_value(0)); + MT_BUG_ON(mt, mtree_store_range(mt, 0, ULONG_MAX, NULL, GFP_ATOMIC)); + entry = mas_next(&mas, ULONG_MAX); + MT_BUG_ON(mt, entry != NULL); + MT_BUG_ON(mt, mas.status != ma_none); + MT_BUG_ON(mt, mas.index != 0); + MT_BUG_ON(mt, mas.last != ULONG_MAX); + rcu_read_unlock(); + mtree_destroy(mt); + rcu_barrier(); + + /* find: the tree is emptied, then holds one entry at 0 */ + mt_init_flags(mt, MT_FLAGS_USE_RCU); + check_seq(mt, 100, false); + rcu_read_lock(); + mas_set(&mas, 0); + entry = mas_find(&mas, ULONG_MAX); + MT_BUG_ON(mt, entry != xa_mk_value(0)); + MT_BUG_ON(mt, mtree_store_range(mt, 0, ULONG_MAX, NULL, GFP_ATOMIC)); + MT_BUG_ON(mt, mtree_store(mt, 0, ptr, GFP_ATOMIC)); + entry = mas_find(&mas, ULONG_MAX); + MT_BUG_ON(mt, entry != NULL); + MT_BUG_ON(mt, mas.status != ma_none); + MT_BUG_ON(mt, mas.index != 1); + MT_BUG_ON(mt, mas.last != ULONG_MAX); + rcu_read_unlock(); + mtree_destroy(mt); + rcu_barrier(); + + /* find_rev: the tree is emptied */ + mt_init_flags(mt, MT_FLAGS_USE_RCU); + check_seq(mt, 100, false); + rcu_read_lock(); + mas_set(&mas, ULONG_MAX); + entry = mas_find_rev(&mas, 0); + MT_BUG_ON(mt, entry != xa_mk_value(100)); + MT_BUG_ON(mt, mtree_store_range(mt, 0, ULONG_MAX, NULL, GFP_ATOMIC)); + entry = mas_find_rev(&mas, 0); + MT_BUG_ON(mt, entry != NULL); + MT_BUG_ON(mt, mas.status != ma_none); + MT_BUG_ON(mt, mas.index != 0); + MT_BUG_ON(mt, mas.last != ULONG_MAX); + entry = mas_find_rev(&mas, 0); + MT_BUG_ON(mt, entry != NULL); + MT_BUG_ON(mt, mas.status != ma_none); + rcu_read_unlock(); + mtree_destroy(mt); + rcu_barrier(); + + /* prev: the tree is emptied, then holds one entry at 0 */ + mt_init_flags(mt, MT_FLAGS_USE_RCU); + check_seq(mt, 100, false); + rcu_read_lock(); + mas_set(&mas, ULONG_MAX); + entry = mas_find_rev(&mas, 0); + MT_BUG_ON(mt, entry != xa_mk_value(100)); + MT_BUG_ON(mt, mtree_store_range(mt, 0, ULONG_MAX, NULL, GFP_ATOMIC)); + MT_BUG_ON(mt, mtree_store(mt, 0, ptr, GFP_ATOMIC)); + entry = mas_prev(&mas, 0); + MT_BUG_ON(mt, entry != ptr); + MT_BUG_ON(mt, mas.status != ma_root); + MT_BUG_ON(mt, mas.index != 0); + MT_BUG_ON(mt, mas.last != 0); + rcu_read_unlock(); + mtree_destroy(mt); + rcu_barrier(); + + /* find_rev: the entry at 0 is below the minimum */ + mt_init_flags(mt, MT_FLAGS_USE_RCU); + check_seq(mt, 100, false); + rcu_read_lock(); + mas_set(&mas, ULONG_MAX); + entry = mas_find_rev(&mas, 1); + MT_BUG_ON(mt, entry != xa_mk_value(100)); + MT_BUG_ON(mt, mtree_store_range(mt, 0, ULONG_MAX, NULL, GFP_ATOMIC)); + MT_BUG_ON(mt, mtree_store(mt, 0, ptr, GFP_ATOMIC)); + entry = mas_find_rev(&mas, 1); + MT_BUG_ON(mt, entry != NULL); + MT_BUG_ON(mt, mas.status != ma_root); + MT_BUG_ON(mt, mas.index != 0); + MT_BUG_ON(mt, mas.last != 0); + rcu_read_unlock(); + mtree_destroy(mt); + rcu_barrier(); + mt_set_non_kernel(0); +} + static DEFINE_MTREE(tree); static int __init maple_tree_seed(void) { @@ -4031,6 +4159,7 @@ static int __init maple_tree_seed(void) check_range64_in_rcu(&tree); + check_restart_no_node(&tree); #if defined(BENCH) skip: -- 2.47.3 When CONFIG_DEBUG_MAPLE_TREE is set, call the WARN_ON_ONCE() after the custom information is dumped about the tree. Without using the kernel's WARN_ON calls, syzbot will not catch issues detected by this code. Update the non-debug code to call WARN_ON_ONCE() as well. Cc: Reported-by: Lorenzo Stoakes Fixes: bf857ddd21d0b ("maple_tree: move debug check to __mas_set_range()") Signed-off-by: Liam R. Howlett (Google) --- include/linux/maple_tree.h | 54 +++++++++++++++++++++----------------- 1 file changed, 30 insertions(+), 24 deletions(-) diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h index e30e57f5f3df9..0f96f1f19eb95 100644 --- a/include/linux/maple_tree.h +++ b/include/linux/maple_tree.h @@ -680,7 +680,7 @@ void mt_cache_shrink(void); pr_info("Pass: %u Run:%u\n", \ atomic_read(&maple_tree_tests_passed), \ atomic_read(&maple_tree_tests_run)); \ - dump_stack(); \ + BUG_ON(1); \ } else { \ atomic_inc(&maple_tree_tests_passed); \ } \ @@ -696,7 +696,7 @@ void mt_cache_shrink(void); pr_info("Pass: %u Run:%u\n", \ atomic_read(&maple_tree_tests_passed), \ atomic_read(&maple_tree_tests_run)); \ - dump_stack(); \ + BUG_ON(1); \ } else { \ atomic_inc(&maple_tree_tests_passed); \ } \ @@ -713,62 +713,68 @@ void mt_cache_shrink(void); pr_info("Pass: %u Run:%u\n", \ atomic_read(&maple_tree_tests_passed), \ atomic_read(&maple_tree_tests_run)); \ - dump_stack(); \ + BUG_ON(1); \ } else { \ atomic_inc(&maple_tree_tests_passed); \ } \ } while (0) #define MT_WARN_ON(__tree, __x) ({ \ + static bool __warned; \ int ret = !!(__x); \ atomic_inc(&maple_tree_tests_run); \ - if (ret) { \ - pr_info("WARN at %s:%d (%u)\n", \ - __func__, __LINE__, __x); \ + if (!ret) { \ + atomic_inc(&maple_tree_tests_passed); \ + } else if (!__warned) { \ + __warned = true; \ + pr_info("WARN at %s:%d\n", \ + __func__, __LINE__); \ mt_dump(__tree, mt_dump_hex); \ pr_info("Pass: %u Run:%u\n", \ atomic_read(&maple_tree_tests_passed), \ atomic_read(&maple_tree_tests_run)); \ - dump_stack(); \ - } else { \ - atomic_inc(&maple_tree_tests_passed); \ + WARN_ON(1); \ } \ unlikely(ret); \ }) #define MAS_WARN_ON(__mas, __x) ({ \ + static bool __warned; \ int ret = !!(__x); \ atomic_inc(&maple_tree_tests_run); \ - if (ret) { \ - pr_info("WARN at %s:%d (%u)\n", \ - __func__, __LINE__, __x); \ + if (!ret) { \ + atomic_inc(&maple_tree_tests_passed); \ + } else if (!__warned) { \ + __warned = true; \ + pr_info("WARN at %s:%d\n", \ + __func__, __LINE__); \ mas_dump(__mas); \ mt_dump((__mas)->tree, mt_dump_hex); \ pr_info("Pass: %u Run:%u\n", \ atomic_read(&maple_tree_tests_passed), \ atomic_read(&maple_tree_tests_run)); \ - dump_stack(); \ - } else { \ - atomic_inc(&maple_tree_tests_passed); \ + WARN_ON(1); \ } \ unlikely(ret); \ }) #define MAS_WR_WARN_ON(__wrmas, __x) ({ \ + static bool __warned; \ int ret = !!(__x); \ atomic_inc(&maple_tree_tests_run); \ - if (ret) { \ - pr_info("WARN at %s:%d (%u)\n", \ - __func__, __LINE__, __x); \ + if (!ret) { \ + atomic_inc(&maple_tree_tests_passed); \ + } else if (!__warned) { \ + __warned = true; \ + pr_info("WARN at %s:%d\n", \ + __func__, __LINE__); \ mas_wr_dump(__wrmas); \ mas_dump((__wrmas)->mas); \ mt_dump((__wrmas)->mas->tree, mt_dump_hex); \ pr_info("Pass: %u Run:%u\n", \ atomic_read(&maple_tree_tests_passed), \ atomic_read(&maple_tree_tests_run)); \ - dump_stack(); \ - } else { \ - atomic_inc(&maple_tree_tests_passed); \ + WARN_ON(1); \ } \ unlikely(ret); \ }) @@ -776,9 +782,9 @@ void mt_cache_shrink(void); #define MT_BUG_ON(__tree, __x) BUG_ON(__x) #define MAS_BUG_ON(__mas, __x) BUG_ON(__x) #define MAS_WR_BUG_ON(__mas, __x) BUG_ON(__x) -#define MT_WARN_ON(__tree, __x) WARN_ON(__x) -#define MAS_WARN_ON(__mas, __x) WARN_ON(__x) -#define MAS_WR_WARN_ON(__mas, __x) WARN_ON(__x) +#define MT_WARN_ON(__tree, __x) WARN_ON_ONCE(__x) +#define MAS_WARN_ON(__mas, __x) WARN_ON_ONCE(__x) +#define MAS_WR_WARN_ON(__mas, __x) WARN_ON_ONCE(__x) #endif /* CONFIG_DEBUG_MAPLE_TREE */ /** -- 2.47.3 From: Chris Mason An unprivileged user can deadlock two CPUs by filling the forwarding database (FDB) of a bridge in their own network namespace. A peer that floods a bridge port with frames from new source addresses can fill the FDB too. The flood alone was never seen to cause a deadlock. Together with local tasks that call vmalloc() in a loop on the CPU that receives the frames, it can deadlock that CPU. Other CPUs that call vmalloc() or vfree() after that can hang too. The FDB holds the MAC addresses that the bridge knows. It is an rhashtable, a hash table that grows as it fills. An rhashtable normally grows from a worker. If an insert finds the table too full before the worker has run, rhashtable_insert_rehash() allocates the larger table immediately, with GFP_ATOMIC, in the context of the insert. bucket_table_alloc() uses kvmalloc() for that. kvmalloc() tries kmalloc() first. Since v6.19, if kmalloc() fails, it falls back to vmalloc() for non-blocking GFP flags too, and kmalloc() always fails above KMALLOC_MAX_SIZE. vmalloc() and vfree() take their spinlocks with bottom halves enabled. Such a lock must not be taken in a softirq, or while holding a lock that a softirq takes. In the bridge, an insert that falls back to vmalloc() breaks the second rule: the bridge inserts into its FDB under br->hash_lock, and its receive softirq takes br->hash_lock as well. Below, one CPU adds an FDB entry for an RTM_NEWNEIGH netlink request, while another CPU is inside vmalloc() or vfree(): RTM_NEWNEIGH vmalloc() or vfree() ============ ==================== spin_lock_bh(&br->hash_lock) spin_lock(&vn->busy.lock) rhashtable_insert_rehash() kvmalloc(GFP_ATOMIC) vmalloc() spin_lock(&vn->busy.lock) waits for the other CPU softirq: a frame for the bridge spin_lock(&br->hash_lock) waits for RTM_NEWNEIGH The receive softirq also inserts into the FDB itself: on a learning port, br_fdb_update() adds the source address of a frame if the FDB does not have it yet. If that insert falls back to vmalloc(), it breaks the first rule. The CPU then deadlocks with itself if the softirq has interrupted a task that holds the same vmalloc lock. Reproduced on x86-64 under emulation, with three things going on at the same time: - RTM_NEWNEIGH requests filled an FDB past 262,144 entries, where the next table is too large for kmalloc() on x86-64. - Frames arrived on a veth port. - Tasks called vmalloc() in a loop. Two CPUs ended up spinning on each other's lock. The softirq path was reproduced too, on x86-64 under emulation and with RPS set by root. Repeated floods of 280,000 source addresses on a veth port, while tasks called vmalloc() in a loop on the CPU that received the frames, ended in a soft lockup in alloc_vmap_area() in 6 of 6 boots. Without these tasks, on a kernel with no debug options, none of 33 floods reached vmalloc(). Fix this by calling kmalloc() instead of kvmalloc() in bucket_table_alloc() if the GFP flags do not allow blocking. Known gaps: - By code inspection, bpf_iter_tcp_realloc_batch() and the dm-bufio clients that set no_sleep also call a non-blocking vmalloc() under spin_lock_bh(), and can still deadlock in the same way. The later commit "mm/vmalloc: fix deadlock in softirq and BH-off callers" fixes them. - If kmalloc() fails, the atomic rehash falls back to a nested table, as before v6.19. A nested table is built from single pages, so it needs no large allocation. An insert then fails in two cases. If the nested table cannot get a page, the insert fails with -ENOMEM or -EBUSY. If the new table has 512 buckets, that is too few for a nested table, and the insert fails with -ENOMEM. - A lookup in a nested table follows up to three more pointers until the worker has rehashed once more. Changes from the LLM patch: Dropped the __GFP_NOWARN from the kmalloc_noprof() when gfpflags_allow_blocking() is false since the only non-blocking caller already sets the flag. Tried to make the alloc_hooks_tag() multi-line call more readable (whitespace changes only). Cc: Fixes: c6307674ed82 ("mm: kvmalloc: add non-blocking support for vmalloc") Assisted-by: LLM Signed-off-by: Chris Mason Signed-off-by: David Hildenbrand (Arm) Signed-off-by: Liam R. Howlett (Google) --- lib/rhashtable.c | 18 +++++++++++++++--- 1 file changed, 15 insertions(+), 3 deletions(-) diff --git a/lib/rhashtable.c b/lib/rhashtable.c index 6362896e4f099..f8ec85bc6e8af 100644 --- a/lib/rhashtable.c +++ b/lib/rhashtable.c @@ -193,9 +193,21 @@ static struct bucket_table *bucket_table_alloc(struct rhashtable *ht, int i; static struct lock_class_key __key; - tbl = alloc_hooks_tag(ht->alloc_tag, - kvmalloc_node_align_noprof(struct_size(tbl, buckets, nbuckets), - 1, gfp|__GFP_ZERO, NUMA_NO_NODE)); + /* + * vmalloc() takes locks that are not safe against interrupts, and the + * emergency rehash runs in whatever context the insert runs in. So a + * caller that cannot block gets slab memory, or else a nested table. + */ + if (gfpflags_allow_blocking(gfp)) + tbl = alloc_hooks_tag(ht->alloc_tag, + kvmalloc_node_align_noprof( + struct_size(tbl, buckets, nbuckets), + 1, gfp | __GFP_ZERO, NUMA_NO_NODE)); + else + tbl = alloc_hooks_tag(ht->alloc_tag, + kmalloc_noprof( + struct_size(tbl, buckets, nbuckets), + gfp | __GFP_ZERO)); size = nbuckets; -- 2.47.3