From nobody Mon Sep 28 12:34:03 2026 Received: from bombadil.infradead.org (bombadil.infradead.org [198.137.202.133]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 55B83375ADE for ; Fri, 21 Aug 2026 19:26:41 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=198.137.202.133 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1787340405; cv=none; b=inRGhtZRWKnfgBilE6W5dM9hwAVXNdcBzooxjAeaEzNGuCWmRX4+GeNKRvlYzvSJtPCPFIXM4IF5LMSl50UYNch/Jg5PtT1h2lDDyyVwq1N9bQYmxp22uk3TvfIsG+cjzSeLcXO7FHbt4Ht1v+c1mw2qP3/FtjmW+rYstbJta4Y= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1787340405; c=relaxed/simple; bh=ACPTqc+0Jm7pYsEd4zsvTkwo9a1z5yDO+6KpnVM1/QI=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=MFBBBim7m8FYNkOK5tz9vvJ3SVTGXAR54dihlRXO/p1QHZI1zBZq3VgGojbd6qLuPCrLYXg+IrlTSXj/Nsoe9KSNkPAHf/DNV9vzZ7EMW4KCBul45+ieoxK919wWNK5Lp6MMAhtr6vRwtCawKcmLLRc8ZBGGeGys5AZD3rOZwME= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=infradead.org; spf=pass smtp.mailfrom=infradead.org; dkim=pass (2048-bit key) header.d=infradead.org header.i=@infradead.org header.b=32o2EnzM; arc=none smtp.client-ip=198.137.202.133 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=infradead.org Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=infradead.org Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=infradead.org header.i=@infradead.org header.b="32o2EnzM" DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=infradead.org; s=bombadil.20210309; h=Content-Transfer-Encoding: MIME-Version:References:In-Reply-To:Message-ID:Date:Subject:Cc:To:From:Sender :Reply-To:Content-Type:Content-ID:Content-Description; bh=MCSEVpnnxOwqJ8ef4Eh5CcwT/xjoltglmElmLRbIhj4=; b=32o2EnzMAsHKO7xUxv6rnRv327 oEbLEi1tbaA8L9OJJpQAcVJgddGmeU0x7qc2je74luSjaXmp48pdUAzzuHa+VrNkotkmisLyzja4N tNOVwIwdHJfXN6tPe3oeGfP3zRsjulcoWwcvdbGD3YDSgdK3cnv9H0Y2dQvg5oeFArvr6esFguWIW BfutAqhxw1LLY0dKzWwU+DNV0cLJ8N3zk/r5h7e8O8XZNlJw6KN2JNGWI4fGY1iPTA4zv8jQ8p6vp hLfnC5YiDsWqgUTvEqc0BwSlZTdabEg46xQ5B2sz/6PusO4+3IFuComVACqInRGCZG1NwvGSpoXdO T2CcCGtA==; Received: from [38.23.173.23] (helo=localhost) by bombadil.infradead.org with esmtpsa (Exim 4.99.1 #2 (Red Hat Linux)) id 1wxUsz-0000000E0gW-0HAo; Fri, 21 Aug 2026 19:26:41 +0000 From: "Liam R. Howlett (Oracle)" To: Andrew Morton Cc: linux-mm@kvack.org, linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org, "Liam R. Howlett (Oracle)" Subject: [PATCH v3 01/19] maple_tree: Add rcu locking check when LOCKDEP is enabled Date: Fri, 21 Aug 2026 15:26:09 -0400 Message-ID: <20260821192627.4085470-2-liam@infradead.org> X-Mailer: git-send-email 2.47.3 In-Reply-To: <20260821192627.4085470-1-liam@infradead.org> References: <20260821192627.4085470-1-liam@infradead.org> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" When CONFIG_LOCKDEP and CONFIG_RCU_STRICT_GRACE_PERIOD is enabled, check for rcu locking issues by recording the grace period in the maple state and checking the rcu window is still valid whenever the maple state is reused with a state that is not MA_START or MA_PAUSED. Signed-off-by: Liam R. Howlett (Oracle) --- include/linux/maple_tree.h | 3 +++ lib/maple_tree.c | 50 +++++++++++++++++++++++++++++++++++++- 2 files changed, 52 insertions(+), 1 deletion(-) diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h index 1b3014377105c..1acf932fcd33c 100644 --- a/include/linux/maple_tree.h +++ b/include/linux/maple_tree.h @@ -484,6 +484,9 @@ 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 operatio= n */ +#if IS_ENABLED(CONFIG_LOCKDEP) && IS_ENABLED(CONFIG_RCU_STRICT_GRACE_PERIO= D) + unsigned long rcu_gp; +#endif }; =20 struct ma_wr_state { diff --git a/lib/maple_tree.c b/lib/maple_tree.c index a0542b491bc23..6d805521beddf 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -1148,6 +1148,42 @@ static inline void mas_free(struct ma_state *mas, st= ruct maple_enode *used) ma_free_rcu(mte_to_node(used)); } =20 +void mas_lock_check(struct ma_state *mas) +{ + +#if IS_ENABLED(CONFIG_LOCKDEP) && IS_ENABLED(CONFIG_RCU_STRICT_GRACE_PERIO= D) + if (!mas_is_active(mas)) + return; + + if (!mt_locked(mas->tree)) { + if (mt_in_rcu(mas->tree)) + WARN_ON_ONCE(poll_state_synchronize_rcu(mas->rcu_gp)); + } +#endif + +} + +void mas_init_lock_check(struct ma_state *mas) +{ +#if IS_ENABLED(CONFIG_LOCKDEP) && IS_ENABLED(CONFIG_RCU_STRICT_GRACE_PERIO= D) + if (!mt_locked(mas->tree)) { + if (mt_in_rcu(mas->tree)) + mas->rcu_gp =3D get_state_synchronize_rcu(); + } +#endif + +} + +static void mas_may_init_lock_check(struct ma_state *mas) +{ +#if IS_ENABLED(CONFIG_LOCKDEP) && IS_ENABLED(CONFIG_RCU_STRICT_GRACE_PERIO= D) + if (mas_is_start(mas) || mas_is_paused(mas)) + mas_init_lock_check(mas); + else + mas_lock_check(mas); +#endif +} + /* * mas_start() - Sets up maple state for operations. * @mas: The maple state. @@ -1166,6 +1202,7 @@ static inline struct maple_enode *mas_start(struct ma= _state *mas) if (likely(mas_is_start(mas))) { struct maple_enode *root; =20 + mas_init_lock_check(mas); mas->min =3D 0; mas->max =3D ULONG_MAX; =20 @@ -4355,6 +4392,7 @@ void *mas_walk(struct ma_state *mas) { void *entry; =20 + mas_may_init_lock_check(mas); if (!mas_is_active(mas) && !mas_is_start(mas)) mas->status =3D ma_start; retry: @@ -4992,6 +5030,7 @@ static void mas_may_activate(struct ma_state *mas) mas->status =3D ma_start; } else { mas->status =3D ma_active; + mas_lock_check(mas); } } =20 @@ -5069,6 +5108,7 @@ void *mas_next(struct ma_state *mas, unsigned long ma= x) { void *entry =3D NULL; =20 + mas_may_init_lock_check(mas); if (mas_next_setup(mas, max, &entry)) return entry; =20 @@ -5092,6 +5132,7 @@ void *mas_next_range(struct ma_state *mas, unsigned l= ong max) { void *entry =3D NULL; =20 + mas_may_init_lock_check(mas); if (mas_next_setup(mas, max, &entry)) return entry; =20 @@ -5200,6 +5241,7 @@ void *mas_prev(struct ma_state *mas, unsigned long mi= n) { void *entry =3D NULL; =20 + mas_may_init_lock_check(mas); if (mas_prev_setup(mas, min, &entry)) return entry; =20 @@ -5223,6 +5265,7 @@ void *mas_prev_range(struct ma_state *mas, unsigned l= ong min) { void *entry =3D NULL; =20 + mas_may_init_lock_check(mas); if (mas_prev_setup(mas, min, &entry)) return entry; =20 @@ -5269,6 +5312,7 @@ EXPORT_SYMBOL_GPL(mt_prev); */ void mas_pause(struct ma_state *mas) { + mas_lock_check(mas); mas->status =3D ma_pause; mas->node =3D NULL; } @@ -5377,6 +5421,7 @@ void *mas_find(struct ma_state *mas, unsigned long ma= x) { void *entry =3D NULL; =20 + mas_may_init_lock_check(mas); if (mas_find_setup(mas, max, &entry)) return entry; =20 @@ -5404,6 +5449,7 @@ void *mas_find_range(struct ma_state *mas, unsigned l= ong max) { void *entry =3D NULL; =20 + mas_may_init_lock_check(mas); if (mas_find_setup(mas, max, &entry)) return entry; =20 @@ -5516,6 +5562,7 @@ void *mas_find_rev(struct ma_state *mas, unsigned lon= g min) { void *entry =3D NULL; =20 + mas_may_init_lock_check(mas); if (mas_find_rev_setup(mas, min, &entry)) return entry; =20 @@ -5542,6 +5589,7 @@ void *mas_find_range_rev(struct ma_state *mas, unsign= ed long min) { void *entry =3D NULL; =20 + mas_may_init_lock_check(mas); if (mas_find_rev_setup(mas, min, &entry)) return entry; =20 @@ -5618,7 +5666,7 @@ bool mas_nomem(struct ma_state *mas, gfp_t gfp) if (!mas->sheaf && !mas->alloc) return false; =20 - mas->status =3D ma_start; + mas_reset(mas); return true; } =20 --=20 2.47.3 From nobody Mon Sep 28 12:34:03 2026 Received: from bombadil.infradead.org (bombadil.infradead.org [198.137.202.133]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 4D19F3DAACF for ; Fri, 21 Aug 2026 19:26:44 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=198.137.202.133 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1787340407; cv=none; b=AVwrCkw4oxDb1FnE2FJofzZiwGD1yg14+d1cfWoPf5C8Hkcycc1UcYGGsZhh9tOlzRIGbz9GwKorRSEfs7zDaBOtOeEvfMMXQVTwMAFX7yff5bb76Q7+iJN5WmVfJwTmox4XdWg0/fy2JfvjeHnPLH3YpVRB4/1edbUjSICSXXQ= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1787340407; c=relaxed/simple; bh=ngQJSLJbSFJaBGv8Z/q3TOwlPDXiqkMHlNT6OawwoEw=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=ketZzqd8m8ab1vmp5bSMGLwEaY4gbWyFEBsRFmplbKyhoFedxk8lJ2EWE9KdX5LX9+blXgBfhVuyH6GMtREF8NxF0+Ciu+aWSXCPClOizUT0XL7/iuNXHt8vR3axlYOy4IkEbWLe/l4PLTaO9jWeFFuYqm0q7PDwjQsY9Zovyn8= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=infradead.org; spf=pass smtp.mailfrom=infradead.org; dkim=pass (2048-bit key) header.d=infradead.org header.i=@infradead.org header.b=UfQis+QH; arc=none smtp.client-ip=198.137.202.133 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=infradead.org Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=infradead.org Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=infradead.org header.i=@infradead.org header.b="UfQis+QH" DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=infradead.org; s=bombadil.20210309; h=Content-Transfer-Encoding: MIME-Version:References:In-Reply-To:Message-ID:Date:Subject:Cc:To:From:Sender :Reply-To:Content-Type:Content-ID:Content-Description; bh=O4S/rOt0mQDvJh08Ktp/PKJyybrhsHg85P0NQ476Smw=; b=UfQis+QHg+fplNIjHjjLL8k/B4 U5+RrmWAZYfBcOyZKIhgZMPSyGzEuPZN9CmsxG6853PjMDVEXEG3JJAeDxAGhHNqHEJqSFokgBI1C q3mXWuUK+xYkdwegJbsih+56fVa80ZpqKo9Hmj7rQt6rXg86Jxb/UnkUDkJ+u4ySrgyhHZYASUc6f zb+qrRx5inOaR5slZhmvpm/zhCBCn+ny+6p3wWvoAwr1Pkt42KGX9SWPtNo7yyXBGkoS0aQy7l2h+ AJZ0tGeUtQCOZYY8hoEoGlUZVlAtVFGjS2LXosMzSiIoqjOOiR5FfNJbOtgXvN3Xu05Gz4dpTAqWU dK1aJcTw==; Received: from [38.23.173.23] (helo=localhost) by bombadil.infradead.org with esmtpsa (Exim 4.99.1 #2 (Red Hat Linux)) id 1wxUt1-0000000E0gr-04gn; Fri, 21 Aug 2026 19:26:43 +0000 From: "Liam R. Howlett (Oracle)" To: Andrew Morton Cc: linux-mm@kvack.org, linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org, "Liam R. Howlett (Oracle)" , Ingo Molnar , Will Deacon , Boqun Feng , Waiman Long , Peter Zijlstra Subject: [PATCH v3 02/19] locking/lockdep: Add sequence counter to held_lock Date: Fri, 21 Aug 2026 15:26:10 -0400 Message-ID: <20260821192627.4085470-3-liam@infradead.org> X-Mailer: git-send-email 2.47.3 In-Reply-To: <20260821192627.4085470-1-liam@infradead.org> References: <20260821192627.4085470-1-liam@infradead.org> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Add an 8 bit small sequence counter to the held_lock struct to detect if the lock as been dropped and reacquired. This is useful when a data structure depends on a constant locking context, but is not able to detect locking and unlocking of the lock through its own API. Since the __lock_unpin_lock() will no longer detect underflow by casting the unsigned int to a signed int, update the casting code to use a temp variable for calculations using a signed int. Cc: Ingo Molnar Cc: Will Deacon Cc: Boqun Feng Cc: Waiman Long Link: https://lore.kernel.org/all/h3tpnj5kzcrxms5picmimtkpg4aypcpip5wbd6bt2= rpdj5k7eb@nhtzs3lefrkq/ Suggested-by: Peter Zijlstra Signed-off-by: Liam R. Howlett (Oracle) --- include/linux/lockdep.h | 3 ++ include/linux/lockdep_types.h | 3 +- include/linux/sched.h | 1 + kernel/locking/lockdep.c | 58 ++++++++++++++++++++++++++++++----- 4 files changed, 57 insertions(+), 8 deletions(-) diff --git a/include/linux/lockdep.h b/include/linux/lockdep.h index 621566345406d..a6451ecbbe9a0 100644 --- a/include/linux/lockdep.h +++ b/include/linux/lockdep.h @@ -273,6 +273,9 @@ extern struct pin_cookie lock_pin_lock(struct lockdep_m= ap *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); =20 +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) =20 #define lockdep_assert(cond) \ diff --git a/include/linux/lockdep_types.h b/include/linux/lockdep_types.h index eae115a264885..55c4b152fedf7 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; }; =20 #else /* !CONFIG_LOCKDEP */ diff --git a/include/linux/sched.h b/include/linux/sched.h index 373bcc0598d10..14d5ce8dd6136 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 =20 diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c index 2d4c5bab5af88..a69567bdd7912 100644 --- a/kernel/locking/lockdep.c +++ b/kernel/locking/lockdep.c @@ -5077,7 +5077,7 @@ static int __lock_is_held(const struct lockdep_map *l= ock, 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 =3D current; struct lock_class *class =3D NULL; @@ -5183,6 +5183,7 @@ static int __lock_acquire(struct lockdep_map *lock, u= nsigned int subclass, hlock->holdtime_stamp =3D lockstat_clock(); #endif hlock->pin_count =3D pin_count; + hlock->seq_count =3D seq; =20 if (check_wait_context(curr, hlock)) return 0; @@ -5388,7 +5389,7 @@ static int reacquire_held_locks(struct task_struct *c= urr, 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: @@ -5669,14 +5670,17 @@ static void __lock_unpin_lock(struct lockdep_map *l= ock, struct pin_cookie cookie struct held_lock *hlock =3D curr->held_locks + i; =20 if (match_held_lock(hlock, lock)) { + int pin_count; + if (WARN(!hlock->pin_count, "unpinning an unpinned lock\n")) return; =20 - hlock->pin_count -=3D cookie.val; + pin_count =3D hlock->pin_count - cookie.val; =20 - if (WARN((int)hlock->pin_count < 0, "pin count corrupted\n")) - hlock->pin_count =3D 0; + if (WARN(pin_count < 0, "pin count corrupted\n")) + pin_count =3D 0; =20 + hlock->pin_count =3D pin_count; return; } } @@ -5684,6 +5688,24 @@ static void __lock_unpin_lock(struct lockdep_map *lo= ck, struct pin_cookie cookie WARN(1, "unpinning an unheld lock\n"); } =20 +static u32 __lock_sequence(struct lockdep_map *lock) +{ + struct task_struct *curr =3D current; + int i; + + if (unlikely(!debug_locks)) + return ~0; + + for (i =3D 0; i < curr->lockdep_depth; i++) { + struct held_lock *hlock =3D 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 +5888,8 @@ void lock_acquire(struct lockdep_map *lock, unsigned = int subclass, =20 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 +5937,8 @@ void lock_sync(struct lockdep_map *lock, unsigned sub= class, int read, =20 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 +6024,26 @@ void lock_unpin_lock(struct lockdep_map *lock, struc= t pin_cookie cookie) } EXPORT_SYMBOL_GPL(lock_unpin_lock); =20 +u32 lock_sequence(struct lockdep_map *lock) +{ + unsigned long flags; + u32 seq =3D ~0; + + if (unlikely(!lockdep_enabled())) + return seq; + + raw_local_irq_save(flags); + check_flags(flags); + + lockdep_recursion_inc(); + seq =3D __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, --=20 2.47.3 From nobody Mon Sep 28 12:34:03 2026 Received: from bombadil.infradead.org (bombadil.infradead.org [198.137.202.133]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 680C0409295 for ; Fri, 21 Aug 2026 19:26:45 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=198.137.202.133 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1787340407; cv=none; b=UmRjm5mRKEFB9dNjhf1GRN5w+qNhHiLRf1icLJhkc/zzoAUoZrHmU6zJ08cn2tzn3ETaNZEzUDTtVgmcgc5zLDDFNqGoOCqrbCIynQQYXGAxDX0TE1syiq+0fU97c0Lx6ledt4Rqb2HQMY5H11B9PHb+clCBSG/lZRjUIY/2bvU= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1787340407; c=relaxed/simple; bh=b++KMbiNl61yr+0xhm26TyrUwTQm6sgaX4h+u4uUpHU=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=FpDRJdR3rf5plEGI7J5k75yWo1DHvv0GGjLdOjJKtwMD5LPfjlJwCbtted8YXHDpj8xAuOCAH3D/uLtoAj04zKQnHn7bYuDbbjCQFbZrblScx1PaBtPpCfkQPlcnk4SUg7rVBpEvuk6t2ErZpuQPqi9bTJCrmMpGUxW5jMzbvIE= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=infradead.org; spf=pass smtp.mailfrom=infradead.org; dkim=pass (2048-bit key) header.d=infradead.org header.i=@infradead.org header.b=QB+QLwVc; arc=none smtp.client-ip=198.137.202.133 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=infradead.org Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=infradead.org Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=infradead.org header.i=@infradead.org header.b="QB+QLwVc" DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=infradead.org; s=bombadil.20210309; h=Content-Transfer-Encoding: MIME-Version:References:In-Reply-To:Message-ID:Date:Subject:Cc:To:From:Sender :Reply-To:Content-Type:Content-ID:Content-Description; bh=7Lbf6JfpagQh1GCndXTynKeDQ4f9QWf34QEeyRmktqc=; b=QB+QLwVcBP3g0s6SZK3D985tGB mJhNSQFbbWOIviFGNjXmE4+59EKZOWbzAwlmvtGsIb0n00o+CksqqIl3SAOqViyM6VUjZb1s9dDDK ynKjCTul4aHj1sqeTHTAIPw8wt0tVv3KnBEVSexxjEIoHu5qjZHT+eoYb43tbSjSN9X5xBrIMa9OJ hm7hfObx9biFci1oPT2genYoPpgLga4wAWxwN6KM6gVUVK5WsegKcvtvWn2W6NaUJE9vE5kYWNYsn KBOXVT5TQ50toEY3Z/5nKwHsp1npENKNHVVDDbg48yJTQ/pMgysJ7U/1z/UZUvjHwZ8JfyedD4Fo8 Qrd+0sVQ==; Received: from [38.23.173.23] (helo=localhost) by bombadil.infradead.org with esmtpsa (Exim 4.99.1 #2 (Red Hat Linux)) id 1wxUt2-0000000E0hD-2uyi; Fri, 21 Aug 2026 19:26:44 +0000 From: "Liam R. Howlett (Oracle)" To: Andrew Morton Cc: linux-mm@kvack.org, linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org, "Liam R. Howlett (Oracle)" , Breno Leitao Subject: [PATCH v3 03/19] maple_tree: Add write lock checking with lockdep sequence numbers Date: Fri, 21 Aug 2026 15:26:11 -0400 Message-ID: <20260821192627.4085470-4-liam@infradead.org> X-Mailer: git-send-email 2.47.3 In-Reply-To: <20260821192627.4085470-1-liam@infradead.org> References: <20260821192627.4085470-1-liam@infradead.org> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Use the lockdep sequence numbers to ensure the write lock is not dropped between write operations. The lockdep sequence is recorded on any walk that starts from the top of the tree and re-checked prior to any operation using an active node. When lockdep detects an issue, it sets debug_locks to 0 disabling further reports. __lock_sequnece() will return u32 ~0 when debug_locks is zero, and the real sequnece count cannot return such a high value as it is less than 32bits. By always updating the sequence number, regardless of lock state and by ignoring ~0 value in the sequence number will avoid ever printing a WARN_ON when lockdep sets debug_locks to 0. Cc: Breno Leitao Tested-by: Breno Leitao Signed-off-by: Liam R. Howlett (Oracle) --- include/linux/maple_tree.h | 7 +++-- lib/maple_tree.c | 64 +++++++++++++++++++++++++++++++------- 2 files changed, 57 insertions(+), 14 deletions(-) diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h index 1acf932fcd33c..d63ac92208d02 100644 --- a/include/linux/maple_tree.h +++ b/include/linux/maple_tree.h @@ -484,9 +484,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 operatio= n */ -#if IS_ENABLED(CONFIG_LOCKDEP) && IS_ENABLED(CONFIG_RCU_STRICT_GRACE_PERIO= D) +#ifdef CONFIG_LOCKDEP + u32 ld_seq; +#ifdef CONFIG_RCU_STRICT_GRACE_PERIOD unsigned long rcu_gp; -#endif +#endif /* CONFIG_RCU_STRICT_GRACE_PERIOD */ +#endif /* CONFIG_LOCKDEP */ }; =20 struct ma_wr_state { diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 6d805521beddf..d8c826e1ca0cf 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -1148,40 +1148,77 @@ static inline void mas_free(struct ma_state *mas, s= truct maple_enode *used) ma_free_rcu(mte_to_node(used)); } =20 -void mas_lock_check(struct ma_state *mas) + +#ifdef CONFIG_LOCKDEP +static struct lockdep_map *mas_lockdep_map(struct ma_state *mas) { + struct maple_tree *mt =3D 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 + struct lockdep_map *map; + u32 seq; =20 -#if IS_ENABLED(CONFIG_LOCKDEP) && IS_ENABLED(CONFIG_RCU_STRICT_GRACE_PERIO= D) if (!mas_is_active(mas)) return; =20 +#ifdef CONFIG_RCU_STRICT_GRACE_PERIOD if (!mt_locked(mas->tree)) { if (mt_in_rcu(mas->tree)) WARN_ON_ONCE(poll_state_synchronize_rcu(mas->rcu_gp)); } -#endif +#endif /* CONFIG_RCU_STRICT_GRACE_PERIOD */ + + map =3D mas_lockdep_map(mas); + if (!map) + return; + + seq =3D lock_sequence(map); + if (seq !=3D UINT_MAX && mas->ld_seq !=3D UINT_MAX) + WARN_ON_ONCE(mas->ld_seq !=3D seq); +#endif /* CONFIG_LOCKDEP */ =20 } =20 -void mas_init_lock_check(struct ma_state *mas) +static void mas_init_lock_check(struct ma_state *mas) { -#if IS_ENABLED(CONFIG_LOCKDEP) && IS_ENABLED(CONFIG_RCU_STRICT_GRACE_PERIO= D) +#ifdef CONFIG_LOCKDEP + struct lockdep_map *map; +#ifdef CONFIG_RCU_STRICT_GRACE_PERIOD if (!mt_locked(mas->tree)) { if (mt_in_rcu(mas->tree)) mas->rcu_gp =3D get_state_synchronize_rcu(); + return; } -#endif +#endif /* CONFIG_RCU_STRICT_GRACE_PERIOD */ + + map =3D mas_lockdep_map(mas); + if (map) /* Update regardless of lock state */ + mas->ld_seq =3D lock_sequence(map); +#endif /* CONFIG_LOCKDEP */ =20 } =20 static void mas_may_init_lock_check(struct ma_state *mas) { -#if IS_ENABLED(CONFIG_LOCKDEP) && IS_ENABLED(CONFIG_RCU_STRICT_GRACE_PERIO= D) - if (mas_is_start(mas) || mas_is_paused(mas)) +#ifdef CONFIG_LOCKDEP +#ifdef CONFIG_RCU_STRICT_GRACE_PERIOD + if (mas_is_start(mas) || mas_is_paused(mas)) { mas_init_lock_check(mas); - else - mas_lock_check(mas); -#endif + return; + } +#endif /* CONFIG_RCU_STRICT_GRACE_PERIOD */ + mas_lock_check(mas); +#endif /* CONFIG_LOCKDEP */ } =20 /* @@ -4864,6 +4901,7 @@ void *mas_store(struct ma_state *mas, void *entry) { MA_WR_STATE(wr_mas, mas, entry); =20 + 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)) @@ -4922,6 +4960,7 @@ int mas_store_gfp(struct ma_state *mas, void *entry, = gfp_t gfp) MA_WR_STATE(wr_mas, mas, entry); int ret =3D 0; =20 + mas_may_init_lock_check(mas); retry: mas_wr_preallocate(&wr_mas, entry); if (unlikely(mas_nomem(mas, gfp))) { @@ -4952,6 +4991,7 @@ void mas_store_prealloc(struct ma_state *mas, void *e= ntry) { MA_WR_STATE(wr_mas, mas, entry); =20 + mas_lock_check(mas); if (mas->store_type =3D=3D wr_store_root) { mas_wr_prealloc_setup(&wr_mas); goto store; @@ -4984,6 +5024,7 @@ int mas_preallocate(struct ma_state *mas, void *entry= , gfp_t gfp) { MA_WR_STATE(wr_mas, mas, entry); =20 + mas_may_init_lock_check(mas); mas_wr_prealloc_setup(&wr_mas); mas->store_type =3D mas_wr_store_type(&wr_mas); mas_prealloc_calc(&wr_mas, entry); @@ -5469,7 +5510,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; --=20 2.47.3 From nobody Mon Sep 28 12:34:03 2026 Received: from bombadil.infradead.org (bombadil.infradead.org [198.137.202.133]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 95B6140A95F for ; Fri, 21 Aug 2026 19:26:46 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=198.137.202.133 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1787340409; cv=none; b=eMwqwXybS+WwkrAOW8WMowseEGpzX/lsiXDVaePNMp1PFdYFk+WNGXYIZkHI1RRQ/pishD+nrfg5NlakwLmf95HAg6FnwTovCO4wND+5uhLe6IA88Q0swbLErUs7ZFKjyfS2uiSxG3coDeDm0sJOVsCQB+7tR9DdJTIDk4LGNbs= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1787340409; c=relaxed/simple; bh=X4MSNCiMX2uQFQg/ni1LRQ5BS72KYqtrOVt3pr7LeHg=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=c+Yjmqiv/xwQSP7JIunEr5HG8COkUktagBlNhsuVlSZYTOQIB1J5w+Xf5l5+RqP+mDxxp3QzjT9XumWDHwoHQTlXMiuw3OVGGEB3t3ylc38k0Uo1l2qyp4raCKll8Q6gZqWwhBZc3A5QN6cZFWiPsIhDtbiB0gVyuX34RUzaMVY= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=infradead.org; spf=pass smtp.mailfrom=infradead.org; dkim=pass (2048-bit key) header.d=infradead.org header.i=@infradead.org header.b=k2x9HoMA; arc=none smtp.client-ip=198.137.202.133 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=infradead.org Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=infradead.org Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=infradead.org header.i=@infradead.org header.b="k2x9HoMA" DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=infradead.org; s=bombadil.20210309; h=Content-Transfer-Encoding: MIME-Version:References:In-Reply-To:Message-ID:Date:Subject:Cc:To:From:Sender :Reply-To:Content-Type:Content-ID:Content-Description; bh=bme1R0KydCT471vE89SzSzHkPBH2aH3edsvHBOUIvRE=; b=k2x9HoMAcdulhKEol/uXLoykNm h6mGyqpaRKbTyIT+/+X2eqUGuDyy5rEVmpKbYigIj5KKMf1pR2HXAeIajJSt4qklGzo2mvO09wLuD ntzwgXxSE1XyXG9SqJ+rrIpJ4xeCLTHlNRNKE9KEU/L+uTAO4Zvnd6Phs9ugC5oHC04st++jyl6Lw oqr/mJcxEs4Ce670WrhBrmIiGwCvICfkOgXoviH9f/zI6HV9RAhv5DZ9U2UzqfKI8s7aSN5fXwSQ1 z+sfvDuOaclMtAd02dkopHEhb02iR+ZW0bCiurdQ2Z4xIGUau23vVMH/Y0uM1Uq3kqi1GJQOgMs8j eA/lAuSg==; Received: from [38.23.173.23] (helo=localhost) by bombadil.infradead.org with esmtpsa (Exim 4.99.1 #2 (Red Hat Linux)) id 1wxUt4-0000000E0i6-1H2q; Fri, 21 Aug 2026 19:26:46 +0000 From: "Liam R. Howlett (Oracle)" To: Andrew Morton Cc: linux-mm@kvack.org, linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org, "Liam R. Howlett (Oracle)" Subject: [PATCH v3 04/19] maple_tree: Documentation fix Date: Fri, 21 Aug 2026 15:26:12 -0400 Message-ID: <20260821192627.4085470-5-liam@infradead.org> X-Mailer: git-send-email 2.47.3 In-Reply-To: <20260821192627.4085470-1-liam@infradead.org> References: <20260821192627.4085470-1-liam@infradead.org> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Don't include the word flag in the quotes with the actual flag. Signed-off-by: Liam R. Howlett (Oracle) --- Documentation/core-api/maple_tree.rst | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/Documentation/core-api/maple_tree.rst b/Documentation/core-api= /maple_tree.rst index ccdd1615cf974..34964ec88d179 100644 --- a/Documentation/core-api/maple_tree.rst +++ b/Documentation/core-api/maple_tree.rst @@ -211,7 +211,7 @@ Advanced Locking =20 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 initializ= ed -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. =20 Functions and structures --=20 2.47.3 From nobody Mon Sep 28 12:34:03 2026 Received: from bombadil.infradead.org (bombadil.infradead.org [198.137.202.133]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 9F9403DFC6B for ; Fri, 21 Aug 2026 19:26:48 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=198.137.202.133 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1787340412; cv=none; b=Yo/iJplYnPYDnRvGQBQspKvkXDHskjuMOMB262XDcjOg79k09kit13IC0kJc1+qEgOaQQYjmAyR+0qMNkFIJaLpiDaHipNKnKf98yPnkiQ+N5rdfm0bkDe35Ajz+0Vw5Fv9b2dU0/QZXPAl9DekqTBMMtAKj6kn1NfwwCCIJlyw= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1787340412; c=relaxed/simple; bh=6BiYH7gG4hPjZH2P51oqBW2kCDUywWtXqhV0Ri660q4=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=j5JoiWzqJIHac9bsycCE43KG2WLbtTVp8JdqjsryGQysYVodC26IEMQyR/lj37gC7cgBZqDdb/CNDu3EBvruOz9OQrVZj47vfcg2FmFl9LIg+BlPeGtD2OlGojPAVmk+tNYEQJUxwsiXB/QVrmOs0u0kW9cbete0mI0uTKEVngs= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=infradead.org; spf=pass smtp.mailfrom=infradead.org; dkim=pass (2048-bit key) header.d=infradead.org header.i=@infradead.org header.b=nStR2H0A; arc=none smtp.client-ip=198.137.202.133 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=infradead.org Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=infradead.org Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=infradead.org header.i=@infradead.org header.b="nStR2H0A" DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=infradead.org; s=bombadil.20210309; h=Content-Transfer-Encoding: MIME-Version:References:In-Reply-To:Message-ID:Date:Subject:Cc:To:From:Sender :Reply-To:Content-Type:Content-ID:Content-Description; bh=D4onz/HeLHxxoamf9Krig4BuT4qb4mm5o9pd3xPJqPk=; b=nStR2H0Ae1bs9Y6uxQZGKGdovU 2zk9HtD4tM1Uve2MzmH4YBzWAHnnx2KBPOCN/rs3rQeuY6BgLA0oWmM4GYHby8+VLWZpWvr/7SZ+l 3II6QraqCuOkNPgGqVXss2aoZl+IB1MSruhvHvNbRpUyNBa3YrQPlnmoUyAInqBPJL5IIz/jmKekV SpZNFW0L4yfvLYbWXM3gGqJ3jOQ8+cT4JiWJBy3odNcynL9ipcphjX4YewPT36nQe+B5NbFjgzRtB Jqm2lnwRkOqVyybv5k5PV8MjpRdFDx7pa2tu+5x2fAY/HnrDgv9GKmgZdMfC6RET2eAPfPx/dwc5X 1+yJQKqw==; Received: from [38.23.173.23] (helo=localhost) by bombadil.infradead.org with esmtpsa (Exim 4.99.1 #2 (Red Hat Linux)) id 1wxUt5-0000000E0iX-3r8f; Fri, 21 Aug 2026 19:26:48 +0000 From: "Liam R. Howlett (Oracle)" To: Andrew Morton Cc: linux-mm@kvack.org, linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org, "Liam R. Howlett (Oracle)" Subject: [PATCH v3 05/19] maple_tree: Drop dead code from mas_extend_spanning_null() Date: Fri, 21 Aug 2026 15:26:13 -0400 Message-ID: <20260821192627.4085470-6-liam@infradead.org> X-Mailer: git-send-email 2.47.3 In-Reply-To: <20260821192627.4085470-1-liam@infradead.org> References: <20260821192627.4085470-1-liam@infradead.org> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" mas_extend_spanning_null() had a clause if the end of the range being written (mas->last) is the same as the end of the existing range it is overwriting (wr_mas->r_max), action will be taken. This code path is not possible because the only calling function increments mas->last (unless it's ULONG_MAX) to walk to one beyond the write and then resets the value back to the initial value. In the case of mas->last =3D=3D ULONG_MAX, then the second part of the statement will always be false - mas->last cannot be less than the node max. This code never executed and is flawed anyways (the arguments are incorrectly ordered), so removing it is the safest action. Since the code never executes, it is not fixing any issue so Fixes tag is not given. Signed-off-by: Liam R. Howlett (Oracle) --- lib/maple_tree.c | 7 ------- 1 file changed, 7 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index d8c826e1ca0cf..3509e293c84f9 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -2997,13 +2997,6 @@ static inline void mas_extend_spanning_null(struct m= a_wr_state *l_wr_mas, if (r_mas->last < r_wr_mas->r_max) r_mas->last =3D r_wr_mas->r_max; r_mas->offset++; - } else if ((r_mas->last =3D=3D 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 =3D 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 =3D r_mas->last; } } =20 --=20 2.47.3 From nobody Mon Sep 28 12:34:03 2026 Received: from bombadil.infradead.org (bombadil.infradead.org [198.137.202.133]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id BCC803F20FC for ; Fri, 21 Aug 2026 19:26:52 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=198.137.202.133 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1787340415; cv=none; b=ad06xbhcFwy5vry6V3gfUxEGNPVtM57R8gs7pUU4Ttw62Y3J91uUKXp3MUOk3vyKUdqT7je0PSwTbq2OXW5nwwHEOoJvlZcWrDKLkSVpQQexU5BeyPQ3706AioH6tZxbraF3LsQabYDVje1qtAcMoDn2cNVKdKtwo50om4geTS4= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1787340415; c=relaxed/simple; bh=8DiLhxDsuvv9b0ZmH5eksyvd0ESCW3up3LZRbVnxwyo=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=E06T+RuZgJxIPCnzH1b/I6rw7zuQEnA1d+5hMM2QrgsaCmRhXySVx6dpsji8n6CF9apcoPivj8EqmvoWEYb1ITwcXfpSmqgfHtvmom4gXgBjxgW+SXH+mi7CvN4IFZNgELTA5lobkAmCRziXLnOzFQSG5Py+2kV74VIxI9hYqLc= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=infradead.org; spf=pass smtp.mailfrom=infradead.org; dkim=pass (2048-bit key) header.d=infradead.org header.i=@infradead.org header.b=rhhf1W07; arc=none smtp.client-ip=198.137.202.133 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=infradead.org Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=infradead.org Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=infradead.org header.i=@infradead.org header.b="rhhf1W07" DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=infradead.org; s=bombadil.20210309; h=Content-Transfer-Encoding: MIME-Version:References:In-Reply-To:Message-ID:Date:Subject:Cc:To:From:Sender :Reply-To:Content-Type:Content-ID:Content-Description; bh=hPfPuTck0yc0sCY/+xYg9mTu/vOl9PIPQA/wAMsFBps=; b=rhhf1W071Rr2NkkyrSQzYJw0HA JTRL7EPwtrSs11Ff+RqwJd+SsfIdB8fNa6uZ6jCKEPsEQcELxmyYWKd9PXIQ9bCtz1eqtaGsdp/UZ idh9vSbga4Rbqfb8c2TjmNjEZJ6MGbpXuOAWBFS/VSmw/x9va6CgByfUhAtwYeMKy8j69NoPDX3Yx W7+kpt3gqug17Yu9a8xO6nSqsCxu+P8QK9MNnMAkRMdl5grvVuiawxn1pgToeazEOgKYy537flLgu HdevUMjnUvDnzfd2sm8e4G6EuorprhHOyfB9IsmbAbYiVO3GcNtA7e0cq7Nt/BC0PqL/+ZT71WVYV dFCn0HXg==; Received: from [38.23.173.23] (helo=localhost) by bombadil.infradead.org with esmtpsa (Exim 4.99.1 #2 (Red Hat Linux)) id 1wxUt7-0000000E0j6-2HAk; Fri, 21 Aug 2026 19:26:49 +0000 From: "Liam R. Howlett (Oracle)" To: Andrew Morton Cc: linux-mm@kvack.org, linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org, "Liam R. Howlett (Oracle)" Subject: [PATCH v3 06/19] maple_tree: Drop MAPLE_ALLOC_SLOTS Date: Fri, 21 Aug 2026 15:26:14 -0400 Message-ID: <20260821192627.4085470-7-liam@infradead.org> X-Mailer: git-send-email 2.47.3 In-Reply-To: <20260821192627.4085470-1-liam@infradead.org> References: <20260821192627.4085470-1-liam@infradead.org> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" MAPLE_ALLOC_SLOTS is no longer used, so remove it. Signed-off-by: Liam R. Howlett (Oracle) --- include/linux/maple_tree.h | 2 -- 1 file changed, 2 deletions(-) diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h index d63ac92208d02..14ca9ac775d99 100644 --- a/include/linux/maple_tree.h +++ b/include/linux/maple_tree.h @@ -28,13 +28,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) */ =20 #define MAPLE_NODE_MASK 255UL --=20 2.47.3 From nobody Mon Sep 28 12:34:03 2026 Received: from bombadil.infradead.org (bombadil.infradead.org [198.137.202.133]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 7E875409E12 for ; Fri, 21 Aug 2026 19:26:53 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=198.137.202.133 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1787340414; cv=none; b=YppCxay1vb6z8oFLTYfEJRiwcxEysXU4iBrBGIJhXL10R0O2RmyKh+P42bXbFTveouaifdaPGdis1HajPRvWGoXp2Oz9sCiSfP+hLTIxHrnKFcwsThHMDiiA5p4PUVu8LNrGUY2i8vK5ijb0yJtD1e22OteckxMok6JqXPrf6SM= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1787340414; c=relaxed/simple; bh=ZmAonhA48maLYRhwuDHuIV9qft9BSevY8h1eNTYeXXg=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=RN1GD0TgtngBbQvjlMVdXsZu4OlsmMk562CkaJz5DV0ZdeMimHiM6nqNeTx5N/eUAINVP906ffguCY5Mp/z1KWpEIGZSoDch35KzfU0w59ZBZzbj7typi7iMQjCOgFns2KutX7Btv4/Dsz59PFdopPg7ebRZkHqQgMEj0DZx4WU= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=infradead.org; spf=pass smtp.mailfrom=infradead.org; dkim=pass (2048-bit key) header.d=infradead.org header.i=@infradead.org header.b=LybhbZbV; arc=none smtp.client-ip=198.137.202.133 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=infradead.org Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=infradead.org Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=infradead.org header.i=@infradead.org header.b="LybhbZbV" DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=infradead.org; s=bombadil.20210309; h=Content-Transfer-Encoding: MIME-Version:References:In-Reply-To:Message-ID:Date:Subject:Cc:To:From:Sender :Reply-To:Content-Type:Content-ID:Content-Description; bh=pk599fpJe4g3OOOhG/1qwXP3ndv15oabFg8bnXYjU1g=; b=LybhbZbVSG4/L63q4HPXuHeFdO B2SOynWj41QtQnJ4vx923V8FDq4p/VL9FoQzwUxQ+5RmWL+yhKCqMvg6J8iH19dfN4gR/nYTqbQa5 iKw3xmRtu1KjgVaXQCVBrOdg/SJIP1R+FnAUPy8MF6it6Sxff6uRAigRUIEP882ZsMTqAX1v01dpP nKhKqqvyqtlayWJ5g7WdAUUgmvU7dlbRQa9tY8HsCo1fIcVLpc03XtLUNrhUe5aH7sALsxeQhgDES oZHLgiiMyZGbd7JuzSNFSVM92m9Ci5y+a3gzjpABq1famvZsD8uZe71AGbp53Yu1sswBBoVmKlSQO ITfAz3kg==; Received: from [38.23.173.23] (helo=localhost) by bombadil.infradead.org with esmtpsa (Exim 4.99.1 #2 (Red Hat Linux)) id 1wxUt9-0000000E0jm-0fLj; Fri, 21 Aug 2026 19:26:51 +0000 From: "Liam R. Howlett (Oracle)" To: Andrew Morton Cc: linux-mm@kvack.org, linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org, "Liam R. Howlett (Oracle)" Subject: [PATCH v3 07/19] maple_tree: Clarify comments on mas_nomem() Date: Fri, 21 Aug 2026 15:26:15 -0400 Message-ID: <20260821192627.4085470-8-liam@infradead.org> X-Mailer: git-send-email 2.47.3 In-Reply-To: <20260821192627.4085470-1-liam@infradead.org> References: <20260821192627.4085470-1-liam@infradead.org> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" When an allocation completely fails, the return is false. If the allocation succeeds or partially succeeds, return true to indicate a retry of the operation. Note that since the lock may have been dropped, the operation is retried from the start - including potentially allocating more memory. Signed-off-by: Liam R. Howlett (Oracle) --- lib/maple_tree.c | 9 +++++++-- 1 file changed, 7 insertions(+), 2 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 3509e293c84f9..baaaa128594c2 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -5677,10 +5677,11 @@ EXPORT_SYMBOL_GPL(mas_erase); =20 /** * mas_nomem() - Check if there was an error allocating and do the allocat= ion - * 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) @@ -5696,6 +5697,10 @@ bool mas_nomem(struct ma_state *mas, gfp_t gfp) mas_alloc_nodes(mas, gfp); } =20 + /* + * Return false on zero forward progress. Partial allocations are kept + * so the retry path will attempt to get the rest. + */ if (!mas->sheaf && !mas->alloc) return false; =20 --=20 2.47.3 From nobody Mon Sep 28 12:34:03 2026 Received: from bombadil.infradead.org (bombadil.infradead.org [198.137.202.133]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 7E7D240963A for ; Fri, 21 Aug 2026 19:26:53 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=198.137.202.133 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1787340414; cv=none; b=qFc3fJGcYOgIyMy3YuSn0Oi81CPd5tkF02DWYZhQwCjEpTVQ51y2VSz6SVLGGHLfKOA4SOxkMG3Pb3vbABVPAVaRVqhg1IVoHSX1OZHmRxNCqnFdqQgm2UW1nnwb3LIgKKtLdNfL5j4pFrMM7EA11Wvws/U1zMVsazyIUsw7o1M= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1787340414; c=relaxed/simple; bh=HP0oabb2PuRtnBtAJlq0lKSudTEcFbZexjPIPDalle8=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=prhIgYepgWPquv3ycAB9t4txDaFlfxlFfLNcOdsOkDqwJsj6UeMvddLWRveiHizpDYdx19NtKZEH17y7UHEI6ARBzVNhBdMJc9iBLMUFn8pEZi3hFu0+4ISK8aYT1Ax1CbS95fhP+DwPRGX+YjiZhdbdRYVSHZT6Nt6AHjyTVYU= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=infradead.org; spf=pass smtp.mailfrom=infradead.org; dkim=pass (2048-bit key) header.d=infradead.org header.i=@infradead.org header.b=Nlo7RAsv; arc=none smtp.client-ip=198.137.202.133 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=infradead.org Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=infradead.org Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=infradead.org header.i=@infradead.org header.b="Nlo7RAsv" DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=infradead.org; s=bombadil.20210309; h=Content-Transfer-Encoding: MIME-Version:References:In-Reply-To:Message-ID:Date:Subject:Cc:To:From:Sender :Reply-To:Content-Type:Content-ID:Content-Description; bh=HuCMNZFX29nK0huvkCpXKIwQOO+TOzQ1a8HPZnuSBHE=; b=Nlo7RAsvW5ogeTKJalkhOFmKuB ax+0nGH4da5jAqa2xbz7XC2xHJ37nXGZINH9wOLcfo1VyP6PugLCkoD4Sij3tKpgHd9dArPZDNs3O QKqzR12bwjSGrzc/uT0cpz0ia5p9CRp1nWZ3b6anlMMnZXkSJuBt9az4aFB8o/z9jHgfHUlYtqjeA UBnbYE/mV2CG1yWAigrkIcc9fB6gNubXSyAzATrz5+7JgB8IPNCibXL8DD958MIxGAOe/ikjKwPXr Yn8eaWu3VPvx9ob6OEi/mOzL7hIzTnCyIM3gaBRX4+u0lHH6X8RcTJy9/aVtKGVvfXpbMY2M7IxBt Fyywh4eA==; Received: from [38.23.173.23] (helo=localhost) by bombadil.infradead.org with esmtpsa (Exim 4.99.1 #2 (Red Hat Linux)) id 1wxUtA-0000000E0kA-3G8m; Fri, 21 Aug 2026 19:26:52 +0000 From: "Liam R. Howlett (Oracle)" To: Andrew Morton Cc: linux-mm@kvack.org, linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org, "Liam R. Howlett (Oracle)" Subject: [PATCH v3 08/19] maple_tree: Use prefetched value in mas_wr_store_type() Date: Fri, 21 Aug 2026 15:26:16 -0400 Message-ID: <20260821192627.4085470-9-liam@infradead.org> X-Mailer: git-send-email 2.47.3 In-Reply-To: <20260821192627.4085470-1-liam@infradead.org> References: <20260821192627.4085470-1-liam@infradead.org> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" The slot contents exist in wr_mas->content, which has less overhead than reading the slot again. Signed-off-by: Liam R. Howlett (Oracle) --- lib/maple_tree.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index baaaa128594c2..d5fa85bc7aab0 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -3280,7 +3280,7 @@ static inline void mas_wr_slot_store(struct ma_wr_sta= te *wr_mas) void __rcu **slots =3D wr_mas->slots; bool gap =3D false; =20 - gap |=3D !mt_slot_locked(mas->tree, slots, offset); + gap |=3D !wr_mas->content; gap |=3D !mt_slot_locked(mas->tree, slots, offset + 1); =20 if (wr_mas->offset_end - offset =3D=3D 1) { --=20 2.47.3 From nobody Mon Sep 28 12:34:03 2026 Received: from bombadil.infradead.org (bombadil.infradead.org [198.137.202.133]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 73CF640B11D for ; Fri, 21 Aug 2026 19:26:55 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=198.137.202.133 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1787340417; cv=none; b=Pj3SiKCqIuv8wEs+7Oc9reziNW0D1qx4YSOUCqBMo4LOe/jUGkw+AMEGAzGNgHfbWiqseFd2gS2rGmEBtQNrCZv+jZeD/YxAC3jyMMUkN4nVteUce7Flw4OlWoeqZvhrTHF+lEXnEJYLbnD5iKEazkG3nQm8pr4ug/jNm2rtH6g= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1787340417; c=relaxed/simple; bh=qKCuTZmpfFXNZnYGMmWO5WOXN7GlC0nX70fZc061Ea0=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=qPcm22mV5ib4Gqqb/uzLnoLuwgureEjdXHOrtYsXLsDSpZd0APjNkAnUAPSCjFVx5vv/DhR0yRWQapFrLUVxkupuKq8S3/j4USbPkpRdZNyFS3SH5YTb28y39HqRWq4T5IlENE1FqoEtH0ToEl2Q6KJhMhhycr3dVfoNQpe6iVI= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=infradead.org; spf=pass smtp.mailfrom=infradead.org; dkim=pass (2048-bit key) header.d=infradead.org header.i=@infradead.org header.b=KPbl5FfP; arc=none smtp.client-ip=198.137.202.133 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=infradead.org Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=infradead.org Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=infradead.org header.i=@infradead.org header.b="KPbl5FfP" DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=infradead.org; s=bombadil.20210309; h=Content-Transfer-Encoding: MIME-Version:References:In-Reply-To:Message-ID:Date:Subject:Cc:To:From:Sender :Reply-To:Content-Type:Content-ID:Content-Description; bh=2d28P310C6D2ve/ZJPwUucplUmheyc9XSDUTHvPY7I8=; b=KPbl5FfPeocKsYvWyv2koCPuyg tacL0UmdP8tjY56HjfHcF3gC+SQ9c55m+HgJQczv0P1EwY1A5JY+1FIjzu5RecY5/xk2q9bTaT/Fc xBSQaFez1eZwtir/2isFXS5EIK+Dy9qOw/kQW7MlLK8E8R9akTuM5C24yBbMbCpF6/+bgsVja4l1O 2AKFzXek5fP/dXSBgncG7RKf8eTU/MfqEssHwGWwnx1RCQ5xbNXaYsVKxsQWSCANsKJzD/n4esw3E 4/5Au13QzHukDFWLr1lcRwDEXkvnKrwGi3b3MH8SMcjy4Ra2OwJXi8lNnDYlbFCmHsnu9x+AIhfx8 tHkj/YYw==; Received: from [38.23.173.23] (helo=localhost) by bombadil.infradead.org with esmtpsa (Exim 4.99.1 #2 (Red Hat Linux)) id 1wxUtC-0000000E0l2-1Zqs; Fri, 21 Aug 2026 19:26:54 +0000 From: "Liam R. Howlett (Oracle)" To: Andrew Morton Cc: linux-mm@kvack.org, linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org, "Liam R. Howlett (Oracle)" Subject: [PATCH v3 09/19] maple_tree: Optimise mas_wr_node_store() when not in rcu mode Date: Fri, 21 Aug 2026 15:26:17 -0400 Message-ID: <20260821192627.4085470-10-liam@infradead.org> X-Mailer: git-send-email 2.47.3 In-Reply-To: <20260821192627.4085470-1-liam@infradead.org> References: <20260821192627.4085470-1-liam@infradead.org> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Clearing the entire node on the stack is unnecessary since most of the node will be overwritten anyways. Just clear what isn't used after the data is in place. Benchmarking shows a speedup of 0.67% on a height 4 tree with 2048 entries. Signed-off-by: Liam R. Howlett (Oracle) --- lib/maple_tree.c | 20 +++++++++++++++++--- 1 file changed, 17 insertions(+), 3 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index d5fa85bc7aab0..56812db8b0efe 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -3187,7 +3187,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; @@ -3200,6 +3200,7 @@ static inline void mas_wr_node_store(struct ma_wr_sta= te *wr_mas) in_rcu =3D mt_in_rcu(mas->tree); offset_end =3D wr_mas->offset_end; node_pivots =3D mt_pivots[wr_mas->type]; + node_slots =3D mt_slots[wr_mas->type]; /* Assume last adds an entry */ new_end =3D mas->end + 1 - offset_end + mas->offset; if (mas->last =3D=3D wr_mas->end_piv) { @@ -3211,7 +3212,6 @@ static inline void mas_wr_node_store(struct ma_wr_sta= te *wr_mas) if (in_rcu) { newnode =3D mas_pop_node(mas); } else { - memset(&reuse, 0, sizeof(struct maple_node)); newnode =3D &reuse; } =20 @@ -3255,7 +3255,21 @@ static inline void mas_wr_node_store(struct ma_wr_st= ate *wr_mas) dst_pivots[new_end] =3D mas->max; =20 done: - mas_leaf_set_meta(newnode, maple_leaf_64, new_end); + if (!in_rcu && new_end + 2 < node_slots) { + unsigned char clear_from =3D new_end + 1; + + /* + * Note that the last slot is never cleared, since the metadata + * will be stored there or it has a value. + */ + 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 =3D mas->node; =20 --=20 2.47.3 From nobody Mon Sep 28 12:34:03 2026 Received: from bombadil.infradead.org (bombadil.infradead.org [198.137.202.133]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id D250740D594 for ; Fri, 21 Aug 2026 19:26:56 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=198.137.202.133 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1787340418; cv=none; b=cy8mAxPbpE5Kok3FCWeqiqNT4gMZhwo6Qn1hDM3CJnJtHPcsyvIQmXqfLu4Y/zTn3fhRI792TrKFcve+ZVUybxOvqOJweewHz3X9WO6zq6Lj4M/Tguv3IloUS5mN7qHdbOjRujtCSSs6zUdd21Ce7nQSdWwbRnCDFJnUFslQkY8= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1787340418; c=relaxed/simple; bh=KAss5IaOoUfePNNtq2p3/cy4JiTLV4UObRrryjZo5MQ=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=IZEVCjzU5PpvrCULcq4mcrUpA6Kc1Mbm2st/BHWPM98L4vNVDsGNDrdXDGPDg4nMAOPICVAvxektG/DtagTGH9Z3osH6C0FFKhBX+VGaBFrpvgGmpOOx5Qc7fl3bgSRrOUXxmuEG5z2pXWolbYuMxHnetARPGDNLQKGQesh+/x8= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=infradead.org; spf=pass smtp.mailfrom=infradead.org; dkim=pass (2048-bit key) header.d=infradead.org header.i=@infradead.org header.b=tMLRcrtc; arc=none smtp.client-ip=198.137.202.133 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=infradead.org Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=infradead.org Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=infradead.org header.i=@infradead.org header.b="tMLRcrtc" DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=infradead.org; s=bombadil.20210309; h=Content-Transfer-Encoding: MIME-Version:References:In-Reply-To:Message-ID:Date:Subject:Cc:To:From:Sender :Reply-To:Content-Type:Content-ID:Content-Description; bh=4lvNvcVkXjeJSX/bJKiTiyE3aeJDISmDpXcWfTd+q7s=; b=tMLRcrtcEUpVdicE7qbOk6pS1v bBQ3HNHStLVVKfIBFlFDG8VEIdOnLfMeWT+WWpIS3LNkRbBm8nP9EDlspExkErPJhMUR5gkOj1k/L aIv2RK/Av74U1mBfNTsD666YM0N1TF2e6/CbNIFIjCP8eGbkrUJt/iSrQgb3rCJ97y8paA9GL/S98 dtc+xRzPJ/OPye/D9/t0uLsYJLim2ccXHx0geldZj1diUyVQ7pOWp7dRaaPHHjy+k8RprGMV5sQMl P7cy7dbkQy0RJKMPdwUH6BDab9kylls5JznmVsVIsCv2eE9fg/6XGp1TnrQ3EVNb+FTiPL6iKssPv 1JUvBkHQ==; Received: from [38.23.173.23] (helo=localhost) by bombadil.infradead.org with esmtpsa (Exim 4.99.1 #2 (Red Hat Linux)) id 1wxUtD-0000000E0lu-46Ad; Fri, 21 Aug 2026 19:26:56 +0000 From: "Liam R. Howlett (Oracle)" To: Andrew Morton Cc: linux-mm@kvack.org, linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org, "Liam R. Howlett (Oracle)" Subject: [PATCH v3 10/19] maple_tree: micro optimisation of mas_wr_store_type() Date: Fri, 21 Aug 2026 15:26:18 -0400 Message-ID: <20260821192627.4085470-11-liam@infradead.org> X-Mailer: git-send-email 2.47.3 In-Reply-To: <20260821192627.4085470-1-liam@infradead.org> References: <20260821192627.4085470-1-liam@infradead.org> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Use three new local booleans instead of reading other structures. This has shown an increase of 0.62% on a 2048 entry tree of height 4. Signed-off-by: Liam R. Howlett (Oracle) --- lib/maple_tree.c | 18 +++++++++++++++--- 1 file changed, 15 insertions(+), 3 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 56812db8b0efe..e2c780a64c9c1 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -3737,6 +3737,9 @@ static inline enum store_type mas_wr_store_type(struc= t ma_wr_state *wr_mas) { struct ma_state *mas =3D wr_mas->mas; unsigned char new_end; + bool appending; + bool one_slot; + bool in_rcu; =20 if (unlikely(mas_is_none(mas) || mas_is_ptr(mas))) return wr_store_root; @@ -3756,21 +3759,30 @@ static inline enum store_type mas_wr_store_type(str= uct ma_wr_state *wr_mas) return wr_new_root; =20 new_end =3D mas_wr_new_end(wr_mas); + in_rcu =3D mt_in_rcu(mas->tree); + appending =3D mas->offset =3D=3D mas->end; + one_slot =3D wr_mas->offset_end - mas->offset =3D=3D 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 =3D=3D new_end && one_slot) + return wr_slot_store; + } return wr_node_store; } =20 if (new_end >=3D mt_slots[wr_mas->type]) return wr_split_store; =20 - if (!mt_in_rcu(mas->tree) && (mas->offset =3D=3D mas->end)) + if (!in_rcu && appending) return wr_append; =20 - if ((new_end =3D=3D mas->end) && (!mt_in_rcu(mas->tree) || - (wr_mas->offset_end - mas->offset =3D=3D 1))) + if (new_end =3D=3D mas->end && (!in_rcu || one_slot)) return wr_slot_store; =20 return wr_node_store; --=20 2.47.3 From nobody Mon Sep 28 12:34:03 2026 Received: from bombadil.infradead.org (bombadil.infradead.org [198.137.202.133]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 941BD40F725 for ; Fri, 21 Aug 2026 19:26:58 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=198.137.202.133 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1787340420; cv=none; b=LYSljH/SbeWVrszJd7bxnkCEEG61wH7ShhrgUCGluQg1heTOsQtSxe6LuwtwxmPb9BsbHIz7Op5XZ1U41Sw7gpd+ZeIlHcPJ7x/QbQ7iNO88M+82dmWUSE86PSqBkDHJltNlHQVtKyO+xhWomeHErwoeuBhuABtlcP528PKx1n8= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1787340420; c=relaxed/simple; bh=pCwu+YTNnemCARf9PMXOjNdMTVE4jLUGdI4tuCKmS6s=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=TbnmC/fU7r63RQLLXYitJITYyrrdKkFilDMHHgX4SOqDTL9Qtp5i3P9rMkbfK7+T43ADd8e8t3/EWvO5sNPShh/7Lj8wwBkR1x5rb7a4vKB9EMp19sbB5sc4g1s3CCNsjzC4SyltMG18Y7/xWZh0LN0ORWaHOcNn6q0r0TgPS6E= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=infradead.org; spf=pass smtp.mailfrom=infradead.org; dkim=pass (2048-bit key) header.d=infradead.org header.i=@infradead.org header.b=dZ2bksNC; arc=none smtp.client-ip=198.137.202.133 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=infradead.org Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=infradead.org Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=infradead.org header.i=@infradead.org header.b="dZ2bksNC" DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=infradead.org; s=bombadil.20210309; h=Content-Transfer-Encoding: MIME-Version:References:In-Reply-To:Message-ID:Date:Subject:Cc:To:From:Sender :Reply-To:Content-Type:Content-ID:Content-Description; bh=xqdYYgN8ZpCZL9nerQOBM+1M3s8bu34Pe4LUXUsonbM=; b=dZ2bksNCqTdqfXzxPsB6Gw3BkW INaq2fsW61sNS5rhzWEi4XfH0XXomvq1KSjWQWjoBCpslU7PQmHM8o1mj9La7OQ+jtqRQgDTiG4EJ j2WpwIiCZUjn1pY1azwvhSrZNmLMlFLuFYOT8vRxUw9JNvZp4ZcqFn7qKb3ILp2/v/4WQXJ63xxY6 wrQjYMLXdIJMCwqYW2aiy5pE+dbuhWyGP8wNM8L5IIcwLS+FnKuR1J8EsoKS7kTCi39V2BAjp1nwo fX8uLuIchbH9twcKWLOdfGyWBIPJjL/zoY/Ev5kgEbR26AcKj/9/2bizr2ypRchTtbIpCdNQ01JHL z1sHuGFg==; Received: from [38.23.173.23] (helo=localhost) by bombadil.infradead.org with esmtpsa (Exim 4.99.1 #2 (Red Hat Linux)) id 1wxUtF-0000000E0mS-2CyS; Fri, 21 Aug 2026 19:26:57 +0000 From: "Liam R. Howlett (Oracle)" To: Andrew Morton Cc: linux-mm@kvack.org, linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org, "Liam R. Howlett (Oracle)" Subject: [PATCH v3 11/19] maple_tree: Add bulk parent set helper Date: Fri, 21 Aug 2026 15:26:19 -0400 Message-ID: <20260821192627.4085470-12-liam@infradead.org> X-Mailer: git-send-email 2.47.3 In-Reply-To: <20260821192627.4085470-1-liam@infradead.org> References: <20260821192627.4085470-1-liam@infradead.org> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Instead of calculating the parent pointer each time for a child, cache the majority of the parent pointer and only change the slot per child. Drop the mas_set_parent() function since the last user has been removed. Testing on a tree containing 2048 entries of height 4 had an increased gain of 3.51% on nodes tracking gaps. Signed-off-by: Liam R. Howlett (Oracle) --- lib/maple_tree.c | 97 +++++++++++++++++++++--------------------------- 1 file changed, 42 insertions(+), 55 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index e2c780a64c9c1..c968e25bea0ae 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -450,46 +450,6 @@ enum maple_type mas_parent_type(struct ma_state *mas, = struct maple_enode *enode) return 0; } =20 -/* - * mas_set_parent() - Set the parent node and encode the slot - * @mas: The maple state - * @enode: The encoded maple node. - * @parent: The encoded maple node that is the parent of @enode. - * @slot: The slot that @enode resides in @parent. - * - * Slot number is encoded in the enode->parent bit 3-6 or 2-6, depending o= n the - * parent type. - */ -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 =3D (unsigned long)parent; - unsigned long shift; - unsigned long type; - enum maple_type p_type =3D mte_node_type(parent); - - MAS_BUG_ON(mas, p_type =3D=3D maple_dense); - MAS_BUG_ON(mas, p_type =3D=3D maple_leaf_64); - - switch (p_type) { - case maple_range_64: - case maple_arange_64: - shift =3D MAPLE_PARENT_SLOT_SHIFT; - type =3D MAPLE_PARENT_RANGE64; - break; - default: - case maple_dense: - case maple_leaf_64: - shift =3D type =3D 0; - break; - } - - val &=3D ~MAPLE_NODE_MASK; /* Clear all node metadata in parent */ - val |=3D (slot << shift) | type; - mte_to_node(enode)->parent =3D ma_parent_ptr(val); -} - /* * mte_parent_slot() - get the parent slot of @enode. * @enode: The encoded maple node. @@ -871,6 +831,42 @@ static inline void ma_set_meta_gap(struct maple_node *= mn, enum maple_type mt, meta->gap =3D offset; } =20 +/* + * 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 =3D mte_node_type(parent); + unsigned char i; + + MAS_BUG_ON(mas, p_type !=3D maple_range_64 && + p_type !=3D maple_arange_64); + + shift =3D MAPLE_PARENT_SLOT_SHIFT; + type =3D MAPLE_PARENT_RANGE64; + + val =3D (unsigned long)parent; + val &=3D ~MAPLE_NODE_MASK; + + for (i =3D 0; i < count; i++) { + unsigned long pval =3D val | ((start_slot + i) << shift) | type; + struct maple_enode *child; + + child =3D mt_slot_locked(mas->tree, slots, i); + mte_to_node(child)->parent =3D ma_parent_ptr(pval); + } +} + /* * mat_add() - Add a @dead_enode to the ma_topiary of a list of dead nodes. * @mat: the ma_topiary, a linked list of dead nodes. @@ -1609,14 +1605,10 @@ static inline void mas_adopt_children(struct ma_sta= te *mas, struct maple_node *node =3D mte_to_node(parent); void __rcu **slots =3D ma_slots(node, type); unsigned long *pivots =3D ma_pivots(node, type); - struct maple_enode *child; - unsigned char offset; + unsigned char end; =20 - offset =3D ma_data_end(node, type, pivots, mas->max); - do { - child =3D mas_slot_locked(mas, slots, offset); - mas_set_parent(mas, child, parent, offset); - } while (offset--); + end =3D ma_data_end(node, type, pivots, mas->max); + mas_set_parent_slots(mas, parent, slots, 0, end + 1); } =20 /* @@ -1998,15 +1990,10 @@ unsigned long node_copy(struct ma_state *mas, struc= t maple_node *src, s_slots =3D ma_slots(src, s_mt) + start; s_pivots =3D ma_pivots(src, s_mt) + start; memcpy(d_slots, s_slots, size * sizeof(void __rcu *)); - if (!ma_is_leaf(d_mt) && s_mt =3D=3D maple_copy) { - struct maple_enode *edst =3D mt_mk_node(dst, d_mt); - =20 - for (int i =3D 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 =3D=3D maple_copy) + mas_set_parent_slots(mas, mt_mk_node(dst, d_mt), + d_slots, d_start, size); =20 d_gaps =3D ma_gaps(dst, d_mt); if (d_gaps) { --=20 2.47.3 From nobody Mon Sep 28 12:34:03 2026 Received: from bombadil.infradead.org (bombadil.infradead.org [198.137.202.133]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 414F140B373 for ; Fri, 21 Aug 2026 19:26:59 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=198.137.202.133 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1787340421; cv=none; b=ll9Oj8URV2fAaVlqlq/NGUfIK9gfoJula7WOQM5DWvnxwD+nRaZ8UCkZ+6CILJ25nph6YZU+2Y1CDb7VWrR1b29ZOWX6EWNgWKKaSzQC9sbZL/ZxGt1CrGa8yIlLgdp2AEanEGT48hGf4QHzVtl0HKXg7DeM+YYOIvuc1NI/vCs= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1787340421; c=relaxed/simple; bh=DOwrCnpEKfuDB90gRcnnnUzRtvVdo0J6Kt8Z3KAl8D0=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=JLoeBpOArmux6CEYVrSRD/HXMP9ESLvJXa3V10TnAwXzCwcqpFyGzPTYp93+KgvppCYdlb4SSx3+QPpamUaSafip1hsrNeMeBJal+a3wfcfzzVNxIIIheLTHkIDSUw6yopvLHfXGnjZYeqJXMXiKxfJj1iNH+XaHUKj5oeWiE8o= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=infradead.org; spf=pass smtp.mailfrom=infradead.org; dkim=pass (2048-bit key) header.d=infradead.org header.i=@infradead.org header.b=NguBtBU3; arc=none smtp.client-ip=198.137.202.133 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=infradead.org Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=infradead.org Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=infradead.org header.i=@infradead.org header.b="NguBtBU3" DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=infradead.org; s=bombadil.20210309; h=Content-Transfer-Encoding: MIME-Version:References:In-Reply-To:Message-ID:Date:Subject:Cc:To:From:Sender :Reply-To:Content-Type:Content-ID:Content-Description; bh=ndoP4i63wdabh88dsKMNw2v1ljVqTGEjtzg/L3kwkpQ=; b=NguBtBU3ldiCLGgAXMv57qEO04 JInGROQa6FRKw2zUmjS9QicFWUdcNuFuWA69nR+HTDAd3OGV/42F0h2WKXr9nSi/txC064OyAEtym WrBoRAd7I9kFz/MhNNZp6A6TwzFgks3OzLlhbeXI9XQ1jTnIMQDiwKEWGb5r2Hy7RYH3uzkoAA5g3 sWedWXvAJca5UZqnn8m1Se6qbtuPB0xwPkJZAXbiSDhx1OFf6NrumVkmGDC/FL3+s29uYYuhrTZWF 8X1ZawAd7iHZBOOyfoSbWF64J1LXm7q+bRdV4PunQvLkHz6+SCeTaGg+AGrSXFmZYBwu4MMg6jFMG zxyZI/yw==; Received: from [38.23.173.23] (helo=localhost) by bombadil.infradead.org with esmtpsa (Exim 4.99.1 #2 (Red Hat Linux)) id 1wxUtH-0000000E0nH-1K1R; Fri, 21 Aug 2026 19:26:59 +0000 From: "Liam R. Howlett (Oracle)" To: Andrew Morton Cc: linux-mm@kvack.org, linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org, "Liam R. Howlett (Oracle)" , Chris Mason , Chuck Lever Subject: [PATCH v3 12/19] maple_tree: Catch race in mas_alloc_cyclic() Date: Fri, 21 Aug 2026 15:26:20 -0400 Message-ID: <20260821192627.4085470-13-liam@infradead.org> X-Mailer: git-send-email 2.47.3 In-Reply-To: <20260821192627.4085470-1-liam@infradead.org> References: <20260821192627.4085470-1-liam@infradead.org> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" If mas_alloc_cyclic() is called during a low memory situation, it is possible the lock may be dropped so reclaim can occur. There is a window where some other task may allocate the same id and cause the mas_insert() to fail with -EEXIST. In this scenario the function will return -EEXIST, which is not expected. Modifying the retry on mas_nomem() to re-search for a slot means that any race with other writes will not matter as the lock will be held between finding the index and writing the index. Moving the flag logic avoids cases where the flag is modified on drop lock/reacquire or when the write fails after clearing the flag. No existing users are exposed to this issue. Fixes: 9b6713cc75229 ("maple_tree: Add mtree_alloc_cyclic()") Reported-by: Chris Mason Cc: Chuck Lever Reviewed-by: Chuck Lever Signed-off-by: Liam R. Howlett (Oracle) --- lib/maple_tree.c | 43 ++++++++++++++++++++++++------------------- 1 file changed, 24 insertions(+), 19 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index c968e25bea0ae..190f480d68502 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -3868,35 +3868,40 @@ 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 =3D range_lo; - int ret =3D 0; - - range_lo =3D max(min, *next); - ret =3D mas_empty_area(mas, range_lo, range_hi, 1); - if ((mas->tree->ma_flags & MT_FLAGS_ALLOC_WRAPPED) && ret =3D=3D 0) { - mas->tree->ma_flags &=3D ~MT_FLAGS_ALLOC_WRAPPED; - ret =3D 1; - } - if (ret < 0 && range_lo > min) { - mas_reset(mas); - ret =3D mas_empty_area(mas, min, range_hi, 1); - if (ret =3D=3D 0) - ret =3D 1; - } - if (ret < 0) - return ret; + int ret; + unsigned long min; =20 + min =3D range_lo; do { + range_lo =3D max(min, *next); + ret =3D mas_empty_area(mas, range_lo, range_hi, 1); + if (ret < 0 && range_lo > min) { + mas_reset(mas); + ret =3D mas_empty_area(mas, min, range_hi, 1); + if (ret =3D=3D 0) + ret =3D 1; + } + if (ret < 0) + goto out; + mas_insert(mas, entry); } while (mas_nomem(mas, gfp)); - if (mas_is_err(mas)) - return xa_err(mas->node); =20 + if (mas_is_err(mas)) { + ret =3D xa_err(mas->node); + goto out; + } + + if ((mas->tree->ma_flags & MT_FLAGS_ALLOC_WRAPPED) && ret =3D=3D 0) { + mas->tree->ma_flags &=3D ~MT_FLAGS_ALLOC_WRAPPED; + ret =3D 1; + } *startp =3D mas->index; *next =3D *startp + 1; if (*next =3D=3D 0) mas->tree->ma_flags |=3D MT_FLAGS_ALLOC_WRAPPED; =20 +out: mas_destroy(mas); return ret; } --=20 2.47.3 From nobody Mon Sep 28 12:34:03 2026 Received: from bombadil.infradead.org (bombadil.infradead.org [198.137.202.133]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 095B3411F93 for ; Fri, 21 Aug 2026 19:27:02 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=198.137.202.133 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1787340423; cv=none; b=cL0xYrN4/ETifesk9MwrsBxMkp/IBDG2I26Y1+1yogQ6jQqEqtFJkRAbme+Mqc0wZmpAELj8h7UcjwJv9QHkS015ouFI3Cd56C0Kkp8r9qkQq75jBYpIElWisD/5YM0AuYQX/ZdTxsEp6yIdLEL1+6UI5/+NLaW9cmYUSnXwI9A= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1787340423; c=relaxed/simple; bh=WCw4PPQYjOQf4hkO9D82QdcGB6E8noJMfoO0iMrjKvM=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=Abm8Wugi5iGJnBJgQ/WOxW8PKGsCeGaAJuGxkNXE4czfbZVpVMJyffGJAVcpUD3zZq69+dYxHjtX9ACpY9RzrIfuD91sg+cW44tt4paa1CBE9aNFoS79wu4h+IFercZFLyiYmdM46LjpjUnfoXwqj8n/LesvRs+S4HAyBOx1kJc= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=infradead.org; spf=pass smtp.mailfrom=infradead.org; dkim=pass (2048-bit key) header.d=infradead.org header.i=@infradead.org header.b=nbrGzFhC; arc=none smtp.client-ip=198.137.202.133 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=infradead.org Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=infradead.org Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=infradead.org header.i=@infradead.org header.b="nbrGzFhC" DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=infradead.org; s=bombadil.20210309; h=Content-Transfer-Encoding: MIME-Version:References:In-Reply-To:Message-ID:Date:Subject:Cc:To:From:Sender :Reply-To:Content-Type:Content-ID:Content-Description; bh=pS9OYDuK7fUXcF58dN1XuFhTjUyENn2k+dqhzY97MNw=; b=nbrGzFhC0B2cyJWDmv8JCSTzit 4UfILEj0QGRQqP1acEHW69DAUrvaeN176eCAXHg2SbokyM/YwcDfMjX1YXtELKFL9X9Dz+JD8Sv4b Ukm+j32KsZJTDhBKDAHo0skKOsNJ3uNnEPrPpl1UriFCn8Qm4i2+/eCujehxYiv+bUD2yI0/d3D+9 8t0CmXKgivXWt5KzFwsGLoX1mpctjAXh59lIR82/qsq3N1kO4/OzEucMTJd3pi9Q2eSAXcM9OmKjc KuCvtFpuCi492uGQpNscvXgM+MmgK06cIsrb+XjR4mC2V+ygG95sU+5gTYGrwdiMHVzwoGsm28Crq rzulBrOA==; Received: from [38.23.173.23] (helo=localhost) by bombadil.infradead.org with esmtpsa (Exim 4.99.1 #2 (Red Hat Linux)) id 1wxUtJ-0000000E0oA-0PVu; Fri, 21 Aug 2026 19:27:01 +0000 From: "Liam R. Howlett (Oracle)" To: Andrew Morton Cc: linux-mm@kvack.org, linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org, "Liam R. Howlett (Oracle)" , Jason Gunthorpe , Rik van Riel Subject: [PATCH v3 13/19] maple_tree: Document that erase may use GFP_KERNEL for allocations Date: Fri, 21 Aug 2026 15:26:21 -0400 Message-ID: <20260821192627.4085470-14-liam@infradead.org> X-Mailer: git-send-email 2.47.3 In-Reply-To: <20260821192627.4085470-1-liam@infradead.org> References: <20260821192627.4085470-1-liam@infradead.org> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" State that the mas_erase() and mtree_erase() functions may use GFP_KERNEL on allocation retry. Don't just depend on people reading the documentation by adding a check that will warn of the use. Cc: Jason Gunthorpe Cc: Rik van Riel Signed-off-by: Liam R. Howlett (Oracle) Reviewed-by: Rik van Riel --- lib/maple_tree.c | 23 +++++++++++++++++++++-- 1 file changed, 21 insertions(+), 2 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 190f480d68502..440863bdea267 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -5658,6 +5658,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) @@ -5666,13 +5670,21 @@ void *mas_erase(struct ma_state *mas) unsigned long index =3D mas->index; MA_WR_STATE(wr_mas, mas, NULL); =20 + /* + * 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 =3D ma_start; =20 write_retry: entry =3D mas_state_walk(mas); if (!entry) - return NULL; + goto out; =20 /* Must reset to ensure spanning writes of last slot are detected */ mas_reset(mas); @@ -5683,8 +5695,10 @@ void *mas_erase(struct ma_state *mas) goto write_retry; } =20 - if (mas_is_err(mas)) + if (mas_is_err(mas)) { + entry =3D NULL; goto out; + } =20 mas_wr_store_entry(&wr_mas); out: @@ -6012,6 +6026,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 AP= I. * + * 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) @@ -6021,6 +6039,7 @@ void *mtree_erase(struct maple_tree *mt, unsigned lon= g index) MA_STATE(mas, mt, index, index); trace_ma_op(TP_FCT, &mas); =20 + might_alloc(GFP_KERNEL); mtree_lock(mt); entry =3D mas_erase(&mas); mtree_unlock(mt); --=20 2.47.3 From nobody Mon Sep 28 12:34:03 2026 Received: from bombadil.infradead.org (bombadil.infradead.org [198.137.202.133]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id BD60D414A05 for ; Fri, 21 Aug 2026 19:27:03 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=198.137.202.133 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1787340425; cv=none; b=fRnORxvNYtMPynEDkJOTzrAxqaKo9+Sftmu4hC3gBKO2RDs9quQnmX4FVFvFxBpOFSaq63KxpazUXChB/cJG+SQk1hdicVi3xIz9OVMP6IZ059fTD9Xa6PITZIS+4GfnPkn7dI3OuZt/tA7DVez7eFUyNZhHjTDR5Vto6rOYeD0= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1787340425; c=relaxed/simple; bh=8+OAkWh8F5VbemHWqjtldhOk7+PiKEUz5v1+4T/KnJ8=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=Mis61BXhkuDKQ3Jzags9vG+UJue3TWoNNFT3XpYNG6d1hTMH5TlQAWSVqhKh45EB5CtRPZKlAI6eS22kYGjzx7TI1c1KSI6AUhlXKrk18ToR1kVXZoPQLwrJGP9TVVJdMV+wLe0fTDYzXtQ69fqRYP+usEkm4CSJ0van3hyMbgo= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=infradead.org; spf=pass smtp.mailfrom=infradead.org; dkim=pass (2048-bit key) header.d=infradead.org header.i=@infradead.org header.b=zgerzV/N; arc=none smtp.client-ip=198.137.202.133 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=infradead.org Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=infradead.org Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=infradead.org header.i=@infradead.org header.b="zgerzV/N" DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=infradead.org; s=bombadil.20210309; h=Content-Transfer-Encoding: MIME-Version:References:In-Reply-To:Message-ID:Date:Subject:Cc:To:From:Sender :Reply-To:Content-Type:Content-ID:Content-Description; bh=qojg5moAHir/aPJEcXeYOPUXGyzZ1v9tB3WPUjtAaWk=; b=zgerzV/NWPll85Q6h4jy9kZ1Bk tyvf5/TgvYXM0FWCf3BEmBX0aYiDesylTU6S72e0YfVIZI73zryLG1EfoiOy4zvexaZAjpzVa2pfd wQ5fZ4uBMIEYQgNl7nInGVLQKzizHLGQP53BTkjH9PGgp6uFDMYRciUkJ90PNf/N4IlVMFoR+jV6O 6eAQwn8SPQpHTp5I7dbPvuEbb2nR6znvroxt6rlpr2omHsAaxOuSMP8BzyOsedXjLkj0+n9llgY7A 31ULM7rwOulO1DDxeqjnSQZnMIxiqjNy3yVtaihfFOUNrqgTKPB2TrR26a0qhEyVRL0Jc3rRWG360 QKBhAE5A==; Received: from [38.23.173.23] (helo=localhost) by bombadil.infradead.org with esmtpsa (Exim 4.99.1 #2 (Red Hat Linux)) id 1wxUtK-0000000E0od-47tv; Fri, 21 Aug 2026 19:27:03 +0000 From: "Liam R. Howlett (Oracle)" To: Andrew Morton Cc: linux-mm@kvack.org, linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org, "Liam R. Howlett (Oracle)" , Rik van Riel , Jason Gunthorpe Subject: [PATCH v3 14/19] maple_tree: Avoid mas_erase() and mtree_erase() failures Date: Fri, 21 Aug 2026 15:26:22 -0400 Message-ID: <20260821192627.4085470-15-liam@infradead.org> X-Mailer: git-send-email 2.47.3 In-Reply-To: <20260821192627.4085470-1-liam@infradead.org> References: <20260821192627.4085470-1-liam@infradead.org> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Failures to remove entries using the two APIs to erase the entries may result in allocation failures. The failures may go unnoticed and an unexpected entry may remain. Instead, fall back to retrying with GFP_KERNEL | __GFP_NOFAIL so that the entry will be removed. Cc: Rik van Riel Cc: Jason Gunthorpe Signed-off-by: Liam R. Howlett (Oracle) --- include/linux/maple_tree.h | 2 ++ lib/maple_tree.c | 68 ++++++++++++++++++++++++++++---------- 2 files changed, 52 insertions(+), 18 deletions(-) diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h index 14ca9ac775d99..173602e87c14b 100644 --- a/include/linux/maple_tree.h +++ b/include/linux/maple_tree.h @@ -570,6 +570,8 @@ int mas_alloc_cyclic(struct ma_state *mas, unsigned lon= g *startp, unsigned long *next, gfp_t gfp); =20 bool mas_nomem(struct ma_state *mas, gfp_t gfp); +bool mas_nomem_nofail(struct ma_state *mas, unsigned long index, + unsigned long last); void mas_pause(struct ma_state *mas); void maple_tree_init(void); void mas_destroy(struct ma_state *mas); diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 440863bdea267..d47d4304f781e 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -5658,9 +5658,10 @@ EXPORT_SYMBOL_GPL(mas_find_range_rev); * Searches for @mas->index, sets @mas->index and @mas->last to the range = and * erases that range. * - * Note that erase requires allocations and will use GFP_KERNEL to do so if - * necessary. If the allocation fails, the internal lock will be dropped = to - * retry. + * Note that erase requires allocations and will use GFP_KERNEL | __GFP_NO= FAIL + * to do so if necessary. If the allocation fails, the internal lock will= be + * dropped to retry. An externally locked tree must be protected by a loc= k that + * allows blocking for this API. * * Return: the entry that was erased or %NULL, @mas->index and @mas->last = are updated. */ @@ -5672,8 +5673,8 @@ void *mas_erase(struct ma_state *mas) =20 /* * In low memory situations, the allocation is retried with the gfp flag - * GFP_KERNEL. The internal spinlock is dropped in mas_nomem(), however - * the external lock is not dropped. + * GFP_KERNEL | __GFP_NOFAIL. The internal spinlock is dropped in + * mas_nomem_nofail(), however the external lock is not dropped. */ if (mt_external_lock(mas->tree)) might_alloc(GFP_KERNEL); @@ -5689,16 +5690,8 @@ void *mas_erase(struct ma_state *mas) /* Must reset to ensure spanning writes of last slot are detected */ mas_reset(mas); mas_wr_preallocate(&wr_mas, NULL); - if (mas_nomem(mas, GFP_KERNEL)) { - /* in case the range of entry changed when unlocked */ - mas->index =3D mas->last =3D index; + if (mas_nomem_nofail(mas, index, index)) goto write_retry; - } - - if (mas_is_err(mas)) { - entry =3D NULL; - goto out; - } =20 mas_wr_store_entry(&wr_mas); out: @@ -5721,6 +5714,10 @@ bool mas_nomem(struct ma_state *mas, gfp_t gfp) if (likely(mas->node !=3D MA_ERROR(-ENOMEM))) return false; =20 + /* 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); @@ -5731,7 +5728,9 @@ bool mas_nomem(struct ma_state *mas, gfp_t gfp) =20 /* * Return false on zero forward progress. Partial allocations are kept - * so the retry path will attempt to get the rest. + * 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. */ if (!mas->sheaf && !mas->alloc) return false; @@ -5740,6 +5739,39 @@ bool mas_nomem(struct ma_state *mas, gfp_t gfp) return true; } =20 +/** + * mas_nomem_nofail() - Retry allocations with __GFP_NOFAIL, if the maple = state + * has stored the -ENOMEM error. + * @mas: The maple state + * @index: The start of the range for the @mas reset + * @last: The end of the range for the @mas reset + * + * Return: false if @mas isn't in an -ENOMEM state. True if the allocation + * happens, the state is reset. The internal lock will be dropped and ext= ernal + * locks must allow blocking. + */ +bool mas_nomem_nofail(struct ma_state *mas, unsigned long index, + unsigned long last) + __must_hold(mas->tree->ma_lock) +{ + gfp_t gfp; + + if (likely(mas->node !=3D MA_ERROR(-ENOMEM))) + return false; + + gfp =3D GFP_KERNEL | __GFP_NOFAIL; + if (!mt_external_lock(mas->tree)) { + mtree_unlock(mas->tree); + mas_alloc_nodes(mas, gfp); + mtree_lock(mas->tree); + } else { + mas_alloc_nodes(mas, gfp); + } + + mas_set_range(mas, index, last); + return true; +} + void __init maple_tree_init(void) { struct kmem_cache_args args =3D { @@ -6026,9 +6058,9 @@ EXPORT_SYMBOL(mtree_alloc_rrange); * Erasing is the same as a walk to an entry then a store of a NULL to that * ENTIRE range. In fact, it is implemented as such using the advanced AP= I. * - * Note that erase requires allocations and will use GFP_KERNEL to do so if - * necessary. If the allocation fails, the internal lock will be dropped = to - * retry. + * Note that erase requires allocations and will use GFP_KERNEL | __GFP_NO= FAIL + * 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 */ --=20 2.47.3 From nobody Mon Sep 28 12:34:03 2026 Received: from bombadil.infradead.org (bombadil.infradead.org [198.137.202.133]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 800C840DB24 for ; Fri, 21 Aug 2026 19:27:05 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=198.137.202.133 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1787340426; cv=none; b=swzdCC8WQvbw7/QV2xHqY7eli6ZpVIbqxLmrwMydg2UrhJiiZV5VQQiBzyUL4zCN/Kg+wgCRVuWvnExtDWEUPiHjTvTvGzTlKEWPsiovsl2pjJQa2lds9H6dJf9CgrhKqM6JNav5Xy31sdSauv/Zz33eL1wysQAAVmO2ABkPSQY= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1787340426; c=relaxed/simple; bh=I74KgCyy6kq1/SvkyO/Mkc5bbAztjkOn9gA4Q+medkw=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=r1KJlhSWACQvnOKxJV/OaOsV3EQu1hnwdzpGvE85c97zBnrlszm84hnBx1dlx00fCZ25TEAWAa/99sT2PVfCs+f8ABJWV2njL8BmVcdm4KF0tl6u20MLgybvqZult4+YNojazhPANdjTSw4NDBZELj9viU67ii2m9bfW2HP+y8U= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=infradead.org; spf=pass smtp.mailfrom=infradead.org; dkim=pass (2048-bit key) header.d=infradead.org header.i=@infradead.org header.b=btUYTavh; arc=none smtp.client-ip=198.137.202.133 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=infradead.org Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=infradead.org Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=infradead.org header.i=@infradead.org header.b="btUYTavh" DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=infradead.org; s=bombadil.20210309; h=Content-Transfer-Encoding: MIME-Version:References:In-Reply-To:Message-ID:Date:Subject:Cc:To:From:Sender :Reply-To:Content-Type:Content-ID:Content-Description; bh=Wii7sR2plTGuVvt+wvs8knQaryx0fB5P6mCwLY4qJzU=; b=btUYTavhOcn4GJZM9OGN+NX44q gcijcMEjrwA7RU/LAMHx7UFgipxnj/a/w8cRbP68UaWo/wbKIvdwUb00jmMCJX6LalTUc4ihj0C5J GUfDjTHV0m51Q7ZoLrcyv4Cz09SsvW8paqd+DbWLOg9gldN+iIJgMAegscP0Td9CRxb4IgXtqxi6v IK+vxT/pt7hwMZBCGxa4/UqeEVSnxz2WfdIk/ghg8M/G/sAf9QhTZasvYBbMHN9KiTX8fhKwnh3h+ Q360dn2SYA6lKOf7KngOtgFoCIb7+Cwz4fZWDFcYKkmj2lnL1Yc3OUEdVjR0JezfCKcBZzw+W7sir GjDFjITw==; Received: from [38.23.173.23] (helo=localhost) by bombadil.infradead.org with esmtpsa (Exim 4.99.1 #2 (Red Hat Linux)) id 1wxUtM-0000000E0p8-34rx; Fri, 21 Aug 2026 19:27:04 +0000 From: "Liam R. Howlett (Oracle)" To: Andrew Morton Cc: linux-mm@kvack.org, linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org, "Liam R. Howlett (Oracle)" , Jason Gunthorpe , Rik van Riel Subject: [PATCH v3 15/19] maple_tree: Document erase and allocations better Date: Fri, 21 Aug 2026 15:26:23 -0400 Message-ID: <20260821192627.4085470-16-liam@infradead.org> X-Mailer: git-send-email 2.47.3 In-Reply-To: <20260821192627.4085470-1-liam@infradead.org> References: <20260821192627.4085470-1-liam@infradead.org> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" During a discussion on the maple tree erase process and GFP flags, Jason suggested there be an amendment to the documentation to clarify the situation on allocations within the tree. The added text is an attempt to better explain that the tree may allocate, even when erasing, and provide some guidance on how to work around such issues. Link: https://lore.kernel.org/all/20260617180419.GA231643@ziepe.ca/ Suggested-by: Jason Gunthorpe Cc: Rik van Riel Signed-off-by: Liam R. Howlett (Oracle) --- Documentation/core-api/maple_tree.rst | 21 ++++++++++++++++++--- 1 file changed, 18 insertions(+), 3 deletions(-) diff --git a/Documentation/core-api/maple_tree.rst b/Documentation/core-api= /maple_tree.rst index 34964ec88d179..9b08a61131e1b 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 t= he previous or next entry in a cache-efficient manner. The tree can also be put into an RCU-s= afe 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 lock= s may +interfere with allocations in a low memory situation. =20 The Maple Tree maintains a small memory footprint and was designed to use modern processor cache efficiently. The majority of the users will be abl= e 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. =20 +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: =20 Normal API @@ -63,7 +73,9 @@ 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 | __GFP_NOFAIL for allocations and cannot +fail, but may need to sleep - do not use mtree_erase() from a blocking con= text. =20 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() whi= ch @@ -163,7 +175,10 @@ You can use mas_erase() to erase an entire range by se= tting 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 +__GFP_NOFAIL and cannot fail, but may sleep. If this is not okay, consider +using mas_store_gfp() and pass it a ``NULL``, +after setting up the correct range by walking to the entry. =20 You can walk each entry within a range by using mas_for_each(). If you wa= nt to walk each element of the tree then ``0`` and ``ULONG_MAX`` may be used = as --=20 2.47.3 From nobody Mon Sep 28 12:34:03 2026 Received: from bombadil.infradead.org (bombadil.infradead.org [198.137.202.133]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 325DB429036 for ; Fri, 21 Aug 2026 19:27:07 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=198.137.202.133 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1787340428; cv=none; b=ey5dxyl+1+30SYqxqHj0eijTPJIhdl+4vzRW2vd2+uBFenP9x5uJBWKwVyhdG7mtXdPkWstPEB3A9vL7meZb6uJDQflnLnXB9LVcgPIjEAt4wvEMjjFGCIHUL8BxgR/eqKvTA/11V8Lw7aZe6FpNdNtZt8t/YVfwbbsSzgH2YpM= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1787340428; c=relaxed/simple; bh=FS9FVDoSljj7vDAdBiUk2IU6yqq/3+a/1vOfKA+wXEw=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=Zqgu7po03rksYkhJYXY/0ngD7HgjYkUPF0tmu89+ExQJ9Dz7aUYvLzEXwPUPgOdF37BlgBOsdKzcIBMJlvGw94zZWZim72ze2iTEKuBY3ChofVLYlboqTnoTEHUtb00WXiCdLKWit1xF1LwZ1k5o+oGJ4zUiPsjEZVrqf01x+yc= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=infradead.org; spf=pass smtp.mailfrom=infradead.org; dkim=pass (2048-bit key) header.d=infradead.org header.i=@infradead.org header.b=hKNAlr+8; arc=none smtp.client-ip=198.137.202.133 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=infradead.org Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=infradead.org Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=infradead.org header.i=@infradead.org header.b="hKNAlr+8" DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=infradead.org; s=bombadil.20210309; h=Content-Transfer-Encoding: MIME-Version:References:In-Reply-To:Message-ID:Date:Subject:Cc:To:From:Sender :Reply-To:Content-Type:Content-ID:Content-Description; bh=ySvyaqBnJby490O44Q0qs0efkhX6UCzOyNrGR/pLA+A=; b=hKNAlr+8anoTJUphOAb5RwFLj+ DVr+GQIEDDnvqink6wk94R8x4ThlEb8OyVBCSS7GpSBkGBCSZ7D2DAlL8DL9Mdyq5ZZSo/U86IeAJ ZV2Xd1QSbxRYk2996ok+56kthBfg/VkgsRTTSHoIUMFLLupRB3KQyMk4lHtwdjc7sg/+TWojdNxi0 NE+HtBZW7e6iCOOveSu5jVcJPNvVo3rdOSee0RXl1YMftEk2SoCI2pX/2rvWpzDSakONrUB7pW2Iz zeypJ+k1e73WjMUacFPAyBYgT3W0EwM0LEjoQWvDJU1Of24jkUvXJ2skOqL7ifoFhFd3lu1ojO/NT TXaHLa+Q==; Received: from [38.23.173.23] (helo=localhost) by bombadil.infradead.org with esmtpsa (Exim 4.99.1 #2 (Red Hat Linux)) id 1wxUtO-0000000E0pv-1p6g; Fri, 21 Aug 2026 19:27:06 +0000 From: "Liam R. Howlett (Oracle)" To: Andrew Morton Cc: linux-mm@kvack.org, linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org, "Liam R. Howlett (Oracle)" , Joe Perches Subject: [PATCH v3 16/19] maple_tree: Change two GFP flags in tests Date: Fri, 21 Aug 2026 15:26:24 -0400 Message-ID: <20260821192627.4085470-17-liam@infradead.org> X-Mailer: git-send-email 2.47.3 In-Reply-To: <20260821192627.4085470-1-liam@infradead.org> References: <20260821192627.4085470-1-liam@infradead.org> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" The GFP flags in two tests are obviously incorrect. Make the tests correctly run by updating the GFP flags. Link: https://lore.kernel.org/all/d9cbb89faa5bdb71d451781d214a51ce8923a83e.= camel@perches.com/ Reported-by: Joe Perches Signed-off-by: Liam R. Howlett (Oracle) --- tools/testing/radix-tree/maple.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/ma= ple.c index 0607913a3022d..d967e76a3c065 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 m= aple_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) =3D=3D = 0); + MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_NOWAIT) =3D=3D 0); allocated =3D mas_allocated(&mas); height =3D mas_mt_height(&mas); MT_BUG_ON(mt, allocated !=3D 0); @@ -35257,7 +35257,7 @@ static noinline void __init check_prealloc(struct m= aple_tree *mt) MT_BUG_ON(mt, mas_allocated(&mas) !=3D 0); mas_set_range(&mas, 0, 200); mt_set_non_kernel(1); - MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL & GFP_NOWAIT) =3D=3D = 0); + MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_NOWAIT) =3D=3D 0); allocated =3D mas_allocated(&mas); height =3D mas_mt_height(&mas); MT_BUG_ON(mt, allocated !=3D 0); --=20 2.47.3 From nobody Mon Sep 28 12:34:03 2026 Received: from bombadil.infradead.org (bombadil.infradead.org [198.137.202.133]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id DF0B542E417 for ; Fri, 21 Aug 2026 19:27:08 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=198.137.202.133 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1787340430; cv=none; b=p6ITi73QPP6zY5HHKAnRJoun6ghbzLt+pJAfLbkqzt3sVSdq/M+c2ihjvvMNRgb4Xl45K75rWuKMcaTcPI5oTptFZhEew7RXJe7b+hrNokQLzPceioztfYofhhVQLnNdaXVxVFjz4iVKUMW0pqoy4cVMgm0RnPqsnF8cjidkV00= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1787340430; c=relaxed/simple; bh=9+lpXHC7PM95II5ODOSu19GiRB5Iteh3RP9TSISKTQc=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=dEWi58ac+pehYaBy0OD8Mi7kBCTRaaBgRysTkMrLy1BerP8PHfPWV5fqTM+CQtUBFFIx0ve4uBbdxuq9KtaJWRp6RIt5+snU9P6EGoz6KUns/QNvS5gHVC+Mu8Z4pGqOMaz++WygY/+uM4eipO7FUUH09GxzLXtBgrqrjPzSiYs= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=infradead.org; spf=pass smtp.mailfrom=infradead.org; dkim=pass (2048-bit key) header.d=infradead.org header.i=@infradead.org header.b=NPFoLcBn; arc=none smtp.client-ip=198.137.202.133 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=infradead.org Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=infradead.org Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=infradead.org header.i=@infradead.org header.b="NPFoLcBn" DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=infradead.org; s=bombadil.20210309; h=Content-Transfer-Encoding: MIME-Version:References:In-Reply-To:Message-ID:Date:Subject:Cc:To:From:Sender :Reply-To:Content-Type:Content-ID:Content-Description; bh=ZRNn+Qndzrl6cCjDNpfrHvrdmbmDeZl+l7zc8rWP1Aw=; b=NPFoLcBnvY18i6WdSpaoMwowFe J42L1f21HcbEyCpBrR0snlIQEJl6UzA/Ck6k4YR3fvKnfBvPQQUevnhT5Fam8ix0HjtZlDDTYbBnl HtxxJtZPEotDMX2BYlJfJBgheY/RNwg/tnHuYZe61mbMKwY4Fciy8c4HIlMeO+JbIivRwtMX+IXDf QtHKuyQ/ucrvxCthxoUq82ieLqtuYk2Hi5PeWIdi2boxKwmi1Q8xfke2ZChFAH3HmsmZDd5s5DOH8 ogQo5KtlMskrNzgQ1X3jDGUz0Kl7E2SSmzrhzlMLBgeaRxOQzGo0LNfdJ2T/7SLAO2C1ta6w1EP7b yTsPmCCg==; Received: from [38.23.173.23] (helo=localhost) by bombadil.infradead.org with esmtpsa (Exim 4.99.1 #2 (Red Hat Linux)) id 1wxUtQ-0000000E0rE-03IF; Fri, 21 Aug 2026 19:27:08 +0000 From: "Liam R. Howlett (Oracle)" To: Andrew Morton Cc: linux-mm@kvack.org, linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org, "Liam R. Howlett (Oracle)" Subject: [PATCH v3 17/19] maple_tree: Fix argument name in header Date: Fri, 21 Aug 2026 15:26:25 -0400 Message-ID: <20260821192627.4085470-18-liam@infradead.org> X-Mailer: git-send-email 2.47.3 In-Reply-To: <20260821192627.4085470-1-liam@infradead.org> References: <20260821192627.4085470-1-liam@infradead.org> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" The mas_prev_range() function takes a min and not a max. Fixes: 6b9e93e010204 ("maple_tree: add mas_prev_range() and mas_find_range_= rev interface") Signed-off-by: Liam R. Howlett (Oracle) --- include/linux/maple_tree.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h index 173602e87c14b..e595ae5cd0eed 100644 --- a/include/linux/maple_tree.h +++ b/include/linux/maple_tree.h @@ -577,7 +577,7 @@ void maple_tree_init(void); void mas_destroy(struct ma_state *mas); =20 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); =20 --=20 2.47.3 From nobody Mon Sep 28 12:34:03 2026 Received: from bombadil.infradead.org (bombadil.infradead.org [198.137.202.133]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 7FB4540A928 for ; Fri, 21 Aug 2026 19:27:10 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=198.137.202.133 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1787340432; cv=none; b=PtPKmyYiyffTNyiRz6pwhtAQfW4ayFMZJnxy5+r32dY+3VNqpQa0ckK9Q5nRrjFnM4FOtwB9OE2kNCpTlnK4JJ+AElGXM71FOx+s1od7+Hrj5Roe8arNuSh4t6fRbN9gab0RilVjAUtLlLmGhcfY7PgwghXLizGpDtsOegOCbVg= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1787340432; c=relaxed/simple; bh=AQUURmp98rmOdPgVaUIvb78a+5gmhPq4H4Te/tmSsO0=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=uKneR/n3yVJm4xnYNAVH44zTI1eXNNAhfDvsGAVOCWGD3bL219wmTssvPH2wCnKiPvtid0o0z+fPDcV2msIdKYDsqhEiUYRIUYuaeAXZDkYBBzgmWYsIAZKjCIU1l71ajHc6fKnMhJ4D195Clk3pLwhY8fw+BmwLVUB2t6FbNFQ= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=infradead.org; spf=pass smtp.mailfrom=infradead.org; dkim=pass (2048-bit key) header.d=infradead.org header.i=@infradead.org header.b=Ar4sqSP1; arc=none smtp.client-ip=198.137.202.133 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=infradead.org Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=infradead.org Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=infradead.org header.i=@infradead.org header.b="Ar4sqSP1" DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=infradead.org; s=bombadil.20210309; h=Content-Transfer-Encoding: MIME-Version:References:In-Reply-To:Message-ID:Date:Subject:Cc:To:From:Sender :Reply-To:Content-Type:Content-ID:Content-Description; bh=udDJnal3U0OEHVtLg9YU9KDptajuVWhrqXaSm/28e6Y=; b=Ar4sqSP1LYl+2U64zJFCmX26jZ 5NSXlZCFDzRLlT2YnhZSShubjYh7TgaoC5TBNLxPBihkQvq9MkDWQvBszSSBU+PtrcRXb+MgjQYaZ gojD7o338BxnNsLOCsL0RMTyrRi19JNbMphRDja7FR1aCGGYnMpZLZnWhfITW8UBlK0NpBDquLKtX njfa8ckmw85Yk/Mps1b3jbrO5FBQjZ53IcCMrlv5irlJ9fOj+FyFLlywb0A7u465t7b9zdbYv9s5L 0RF2mXXDBx8Zg5cM//zP0Nvs0fl2cmmCWKK87TPGzCEPv4KWnHYmww75pn/feNM6oXDCSvGazYeVw 1103lbxw==; Received: from [38.23.173.23] (helo=localhost) by bombadil.infradead.org with esmtpsa (Exim 4.99.1 #2 (Red Hat Linux)) id 1wxUtR-0000000E0s2-2qAP; Fri, 21 Aug 2026 19:27:09 +0000 From: "Liam R. Howlett (Oracle)" To: Andrew Morton Cc: linux-mm@kvack.org, linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org, "Liam R. Howlett (Oracle)" Subject: [PATCH v3 18/19] maple_tree: Avoid extra gap calculation Date: Fri, 21 Aug 2026 15:26:26 -0400 Message-ID: <20260821192627.4085470-19-liam@infradead.org> X-Mailer: git-send-email 2.47.3 In-Reply-To: <20260821192627.4085470-1-liam@infradead.org> References: <20260821192627.4085470-1-liam@infradead.org> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Prior to ending the ascension loop of larger operations like split, rebalance, and spanning store the gap in the node had been calculated. Once the node is inserted into the tree, the gap is recalculated in mas_update_gap(). This can be avoided by creating a helper for mas_update_gap() that accepts the known gap value, which reduces the operations required for gap updating path. Signed-off-by: Liam R. Howlett (Oracle) --- lib/maple_tree.c | 28 +++++++++++++++++----------- 1 file changed, 17 insertions(+), 11 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index d47d4304f781e..b43e2ce129b30 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -1566,14 +1566,26 @@ static inline void mas_parent_gap(struct ma_state *= mas, unsigned char offset, goto ascend; } =20 +static __always_inline void mas_update_gap_known(struct ma_state *mas, + unsigned long gap) +{ + unsigned char pslot; + unsigned long p_gap; + + pslot =3D mte_parent_slot(mas->node); + p_gap =3D ma_gaps(mte_parent(mas->node), + mas_parent_type(mas, mas->node))[pslot]; + + if (p_gap !=3D 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; =20 if (!mt_is_alloc(mas->tree)) @@ -1583,13 +1595,7 @@ static inline void mas_update_gap(struct ma_state *m= as) return; =20 max_gap =3D mas_max_gap(mas); - - pslot =3D mte_parent_slot(mas->node); - p_gap =3D ma_gaps(mte_parent(mas->node), - mas_parent_type(mas, mas->node))[pslot]; - - if (p_gap !=3D max_gap) - mas_parent_gap(mas, pslot, max_gap); + mas_update_gap_known(mas, max_gap); } =20 /* @@ -2137,8 +2143,8 @@ static inline void mas_wmb_replace(struct ma_state *m= as, struct maple_copy *cp) mas->node =3D 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]); =20 mtree_range_walk(mas); } --=20 2.47.3 From nobody Mon Sep 28 12:34:03 2026 Received: from bombadil.infradead.org (bombadil.infradead.org [198.137.202.133]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 03F7342E430 for ; Fri, 21 Aug 2026 19:27:11 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=198.137.202.133 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1787340433; cv=none; b=QaQuhcCFrkGQPv+WmP7RTH+0kXg+dK1i7L09D7al4aVGN5bJYfWEE90LJYhigqokHyUDFYcvfPcRJNfsjdkhmotghwO/iBfvnzQZuzkgU4EhLye39iLOhnIyFzSxHgssVJm2XmzaHwSni8NS+PuStNg4xTalo5qAr8oD5kW9130= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1787340433; c=relaxed/simple; bh=DVkSgzE4tdUY+zU5gmN/xmC21teObW4ofKYJUapJMJI=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=t976o+YWz/Rl9zSb/iSDWRdOmJTTk89N8dRRILHIU7ykJWWvcyBPmw6RpK0KslDl45hYJXg4fDzhofltAksGYX1orwddG+yMZrpEpf98HvBCN1rp/+vl9mO03a+StjRQmhW7923EvmuwYGaKS27eQnriNu+Tz38HM2IGJM4MN68= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=infradead.org; spf=pass smtp.mailfrom=infradead.org; dkim=pass (2048-bit key) header.d=infradead.org header.i=@infradead.org header.b=KkrpeCqP; arc=none smtp.client-ip=198.137.202.133 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=infradead.org Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=infradead.org Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=infradead.org header.i=@infradead.org header.b="KkrpeCqP" DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=infradead.org; s=bombadil.20210309; h=Content-Transfer-Encoding: MIME-Version:References:In-Reply-To:Message-ID:Date:Subject:Cc:To:From:Sender :Reply-To:Content-Type:Content-ID:Content-Description; bh=s7XvHKqluwtAwKNSJOQ6OxYbkemecBatRbSPiv+AXJc=; b=KkrpeCqP54zVTNvPzrW30XaDvi h7Rqq0W1cah7m6RxPfkg2HxoIbEM5SNLSGmaZCIImsU67NQY9dieT47/+3aHPenK7P+AOu+iYnxr5 4kRSZqCjcqZSc1noJRvIPguVsW13/YZE/CKpLXSEBzH4lMBBL41rW23da/oYfW7ba4QWxBofQdppM +8Qwe6yI6RQCA5X0ypqwAJHhf/6UZrhjMUT/hAHxLnTFnpWiv6DfVbjXb/CuF6Ct4s32JS4xcU2oi 0r3zobDrKLKN9CxPEx/1qvxOvl2dqFH6KNRLQwEPZf5v4Xjgrgr9m+7sb9FzaR+s1eMlOgLn9IxG2 8696Q2eQ==; Received: from [38.23.173.23] (helo=localhost) by bombadil.infradead.org with esmtpsa (Exim 4.99.1 #2 (Red Hat Linux)) id 1wxUtT-0000000E0sW-1EHU; Fri, 21 Aug 2026 19:27:11 +0000 From: "Liam R. Howlett (Oracle)" To: Andrew Morton Cc: linux-mm@kvack.org, linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org, "Liam R. Howlett (Oracle)" Subject: [PATCH v3 19/19] maple_tree: Add helper mas_make_walkable() Date: Fri, 21 Aug 2026 15:26:27 -0400 Message-ID: <20260821192627.4085470-20-liam@infradead.org> X-Mailer: git-send-email 2.47.3 In-Reply-To: <20260821192627.4085470-1-liam@infradead.org> References: <20260821192627.4085470-1-liam@infradead.org> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" A check in mas_walk() was incorrect and caused inefficient use of the maple state. The same issue existed in mas_erase(), but was left unfixed. Making a helper function is the obvious answer. Signed-off-by: Liam R. Howlett (Oracle) --- lib/maple_tree.c | 13 ++++++++----- 1 file changed, 8 insertions(+), 5 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index b43e2ce129b30..1aba6cced7130 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -261,6 +261,12 @@ static inline bool mas_is_underflow(struct ma_state *m= as) return mas->status =3D=3D ma_underflow; } =20 +static inline void mas_make_walkable(struct ma_state *mas) +{ + if (!mas_is_active(mas) && !mas_is_start(mas)) + mas->status =3D ma_start; +} + static __always_inline struct maple_node *mte_to_node( const struct maple_enode *entry) { @@ -4447,8 +4453,7 @@ void *mas_walk(struct ma_state *mas) void *entry; =20 mas_may_init_lock_check(mas); - if (!mas_is_active(mas) && !mas_is_start(mas)) - mas->status =3D ma_start; + mas_make_walkable(mas); retry: entry =3D mas_state_walk(mas); if (mas_is_start(mas)) { @@ -5685,9 +5690,7 @@ void *mas_erase(struct ma_state *mas) if (mt_external_lock(mas->tree)) might_alloc(GFP_KERNEL); =20 - if (!mas_is_active(mas) || !mas_is_start(mas)) - mas->status =3D ma_start; - + mas_make_walkable(mas); write_retry: entry =3D mas_state_walk(mas); if (!entry) --=20 2.47.3