linux - lib/maple

7204 lines · 174.5 KiB

1	// SPDX-License-Identifier: GPL-2.0+
2	/*
3	* Maple Tree implementation
4	* Copyright (c) 2018-2022 Oracle Corporation
5	* Authors: Liam R. Howlett <[email protected]>
6	* Matthew Wilcox <[email protected]>
7	* Copyright (c) 2023 ByteDance
8	* Author: Peng Zhang <[email protected]>
9	*/
10
11	/*
12	* DOC: Interesting implementation details of the Maple Tree
13	*
14	* Each node type has a number of slots for entries and a number of slots for
15	* pivots. In the case of dense nodes, the pivots are implied by the position
16	* and are simply the slot index + the minimum of the node.
17	*
18	* In regular B-Tree terms, pivots are called keys. The term pivot is used to
19	* indicate that the tree is specifying ranges. Pivots may appear in the
20	* subtree with an entry attached to the value whereas keys are unique to a
21	* specific position of a B-tree. Pivot values are inclusive of the slot with
22	* the same index.
23	*
24	*
25	* The following illustrates the layout of a range64 nodes slots and pivots.
26	*
27	*
28	* Slots -> \| 0 \| 1 \| 2 \| ... \| 12 \| 13 \| 14 \| 15 \|
29	* ┬ ┬ ┬ ┬ ┬ ┬ ┬ ┬ ┬
30	* │ │ │ │ │ │ │ │ └─ Implied maximum
31	* │ │ │ │ │ │ │ └─ Pivot 14
32	* │ │ │ │ │ │ └─ Pivot 13
33	* │ │ │ │ │ └─ Pivot 12
34	* │ │ │ │ └─ Pivot 11
35	* │ │ │ └─ Pivot 2
36	* │ │ └─ Pivot 1
37	* │ └─ Pivot 0
38	* └─ Implied minimum
39	*
40	* Slot contents:
41	* Internal (non-leaf) nodes contain pointers to other nodes.
42	* Leaf nodes contain entries.
43	*
44	* The location of interest is often referred to as an offset. All offsets have
45	* a slot, but the last offset has an implied pivot from the node above (or
46	* UINT_MAX for the root node.
47	*
48	* Ranges complicate certain write activities. When modifying any of
49	* the B-tree variants, it is known that one entry will either be added or
50	* deleted. When modifying the Maple Tree, one store operation may overwrite
51	* the entire data set, or one half of the tree, or the middle half of the tree.
52	*
53	*/
54
55
56	#include <linux/maple_tree.h>
57	#include <linux/xarray.h>
58	#include <linux/types.h>
59	#include <linux/export.h>
60	#include <linux/slab.h>
61	#include <linux/limits.h>
62	#include <asm/barrier.h>
63
64	#define CREATE_TRACE_POINTS
65	#include <trace/events/maple_tree.h>
66
67	#define TP_FCT tracepoint_string(__func__)
68
69	/*
70	* Kernel pointer hashing renders much of the maple tree dump useless as tagged
71	* pointers get hashed to arbitrary values.
72	*
73	* If CONFIG_DEBUG_VM_MAPLE_TREE is set we are in a debug mode where it is
74	* permissible to bypass this. Otherwise remain cautious and retain the hashing.
75	*
76	* Userland doesn't know about %px so also use %p there.
77	*/
78	#if defined(__KERNEL__) && defined(CONFIG_DEBUG_VM_MAPLE_TREE)
79	#define PTR_FMT "%px"
80	#else
81	#define PTR_FMT "%p"
82	#endif
83
84	#define MA_ROOT_PARENT 1
85
86	/*
87	* Maple state flags
88	* * MA_STATE_PREALLOC - Preallocated nodes, WARN_ON allocation
89	*/
90	#define MA_STATE_PREALLOC 1
91
92	#define ma_parent_ptr(x) ((struct maple_pnode *)(x))
93	#define mas_tree_parent(x) ((unsigned long)(x->tree) \| MA_ROOT_PARENT)
94	#define ma_mnode_ptr(x) ((struct maple_node *)(x))
95	#define ma_enode_ptr(x) ((struct maple_enode *)(x))
96	static struct kmem_cache *maple_node_cache;
97
98	#ifdef CONFIG_DEBUG_MAPLE_TREE
99	static const unsigned long mt_max[] = {
100	[maple_dense] = MAPLE_NODE_SLOTS,
101	[maple_leaf_64] = ULONG_MAX,
102	[maple_range_64] = ULONG_MAX,
103	[maple_arange_64] = ULONG_MAX,
104	[maple_copy] = ULONG_MAX,
105	};
106	#define mt_node_max(x) mt_max[mte_node_type(x)]
107	#endif
108
109	static const unsigned char mt_slots[] = {
110	[maple_dense] = MAPLE_NODE_SLOTS,
111	[maple_leaf_64] = MAPLE_RANGE64_SLOTS,
112	[maple_range_64] = MAPLE_RANGE64_SLOTS,
113	[maple_arange_64] = MAPLE_ARANGE64_SLOTS,
114	[maple_copy] = 3,
115	};
116	#define mt_slot_count(x) mt_slots[mte_node_type(x)]
117
118	static const unsigned char mt_pivots[] = {
119	[maple_dense] = 0,
120	[maple_leaf_64] = MAPLE_RANGE64_SLOTS - 1,
121	[maple_range_64] = MAPLE_RANGE64_SLOTS - 1,
122	[maple_arange_64] = MAPLE_ARANGE64_SLOTS - 1,
123	[maple_copy] = 3,
124	};
125	#define mt_pivot_count(x) mt_pivots[mte_node_type(x)]
126
127	static const unsigned char mt_min_slots[] = {
128	[maple_dense] = MAPLE_NODE_SLOTS / 2,
129	[maple_leaf_64] = (MAPLE_RANGE64_SLOTS / 2) - 2,
130	[maple_range_64] = (MAPLE_RANGE64_SLOTS / 2) - 2,
131	[maple_arange_64] = (MAPLE_ARANGE64_SLOTS / 2) - 1,
132	[maple_copy] = 1, /* Should never be used */
133	};
134	#define mt_min_slot_count(x) mt_min_slots[mte_node_type(x)]
135
136	/* Functions */
137	static inline struct maple_node *mt_alloc_one(gfp_t gfp)
138	{
139	return kmem_cache_alloc(maple_node_cache, gfp);
140	}
141
142	static inline void mt_free_bulk(size_t size, void __rcu **nodes)
143	{
144	kmem_cache_free_bulk(maple_node_cache, size, (void **)nodes);
145	}
146
147	static void mt_return_sheaf(struct slab_sheaf *sheaf)
148	{
149	kmem_cache_return_sheaf(maple_node_cache, GFP_NOWAIT, sheaf);
150	}
151
152	static struct slab_sheaf *mt_get_sheaf(gfp_t gfp, int count)
153	{
154	return kmem_cache_prefill_sheaf(maple_node_cache, gfp, count);
155	}
156
157	static int mt_refill_sheaf(gfp_t gfp, struct slab_sheaf **sheaf,
158	unsigned int size)
159	{
160	return kmem_cache_refill_sheaf(maple_node_cache, gfp, sheaf, size);
161	}
162
163	/*
164	* ma_free_rcu() - Use rcu callback to free a maple node
165	* @node: The node to free
166	*
167	* The maple tree uses the parent pointer to indicate this node is no longer in
168	* use and will be freed.
169	*/
170	static void ma_free_rcu(struct maple_node *node)
171	{
172	WARN_ON(node->parent != ma_parent_ptr(node));
173	kfree_rcu(node, rcu);
174	}
175
176	static void mt_set_height(struct maple_tree *mt, unsigned char height)
177	{
178	unsigned int new_flags = mt->ma_flags;
179
180	new_flags &= ~MT_FLAGS_HEIGHT_MASK;
181	MT_BUG_ON(mt, height > MAPLE_HEIGHT_MAX);
182	new_flags \|= height << MT_FLAGS_HEIGHT_OFFSET;
183	mt->ma_flags = new_flags;
184	}
185
186	static unsigned int mas_mt_height(struct ma_state *mas)
187	{
188	return mt_height(mas->tree);
189	}
190
191	static inline unsigned int mt_attr(struct maple_tree *mt)
192	{
193	return mt->ma_flags & ~MT_FLAGS_HEIGHT_MASK;
194	}
195
196	static __always_inline enum maple_type mte_node_type(
197	const struct maple_enode *entry)
198	{
199	return ((unsigned long)entry >> MAPLE_NODE_TYPE_SHIFT) &
200	MAPLE_NODE_TYPE_MASK;
201	}
202
203	static __always_inline bool ma_is_dense(const enum maple_type type)
204	{
205	return type < maple_leaf_64;
206	}
207
208	static __always_inline bool ma_is_leaf(const enum maple_type type)
209	{
210	return type < maple_range_64;
211	}
212
213	static __always_inline bool mte_is_leaf(const struct maple_enode *entry)
214	{
215	return ma_is_leaf(mte_node_type(entry));
216	}
217
218	/*
219	* We also reserve values with the bottom two bits set to '10' which are
220	* below 4096
221	*/
222	static __always_inline bool mt_is_reserved(const void *entry)
223	{
224	return ((unsigned long)entry < MAPLE_RESERVED_RANGE) &&
225	xa_is_internal(entry);
226	}
227
228	static __always_inline void mas_set_err(struct ma_state *mas, long err)
229	{
230	mas->node = MA_ERROR(err);
231	mas->status = ma_error;
232	}
233
234	static __always_inline bool mas_is_ptr(const struct ma_state *mas)
235	{
236	return mas->status == ma_root;
237	}
238
239	static __always_inline bool mas_is_start(const struct ma_state *mas)
240	{
241	return mas->status == ma_start;
242	}
243
244	static __always_inline bool mas_is_none(const struct ma_state *mas)
245	{
246	return mas->status == ma_none;
247	}
248
249	static __always_inline bool mas_is_paused(const struct ma_state *mas)
250	{
251	return mas->status == ma_pause;
252	}
253
254	static __always_inline bool mas_is_overflow(struct ma_state *mas)
255	{
256	return mas->status == ma_overflow;
257	}
258
259	static inline bool mas_is_underflow(struct ma_state *mas)
260	{
261	return mas->status == ma_underflow;
262	}
263
264	static inline void mas_make_walkable(struct ma_state *mas)
265	{
266	if (!mas_is_active(mas) && !mas_is_start(mas))
267	mas->status = ma_start;
268	}
269
270	static __always_inline struct maple_node *mte_to_node(
271	const struct maple_enode *entry)
272	{
273	return (struct maple_node *)((unsigned long)entry & ~MAPLE_NODE_MASK);
274	}
275
276	/*
277	* mte_to_mat() - Convert a maple encoded node to a maple topiary node.
278	* @entry: The maple encoded node
279	*
280	* Return: a maple topiary pointer
281	*/
282	static inline struct maple_topiary mte_to_mat(const struct maple_enode entry)
283	{
284	return (struct maple_topiary *)
285	((unsigned long)entry & ~MAPLE_NODE_MASK);
286	}
287
288	/*
289	* mas_mn() - Get the maple state node.
290	* @mas: The maple state
291	*
292	* Return: the maple node (not encoded - bare pointer).
293	*/
294	static inline struct maple_node mas_mn(const struct ma_state mas)
295	{
296	return mte_to_node(mas->node);
297	}
298
299	/*
300	* mte_set_node_dead() - Set a maple encoded node as dead.
301	* @mn: The maple encoded node.
302	*/
303	static inline void mte_set_node_dead(struct maple_enode *mn)
304	{
305	mte_to_node(mn)->parent = ma_parent_ptr(mte_to_node(mn));
306	smp_wmb(); /* Needed for RCU */
307	}
308
309	/* Bit 1 indicates the root is a node */
310	#define MAPLE_ROOT_NODE 0x02
311	/* maple_type stored bit 3-6 */
312	#define MAPLE_ENODE_TYPE_SHIFT 0x03
313	/* Bit 2 means a NULL somewhere below */
314	#define MAPLE_ENODE_NULL 0x04
315
316	static inline struct maple_enode mt_mk_node(const struct maple_node node,
317	enum maple_type type)
318	{
319	return (void *)((unsigned long)node \|
320	(type << MAPLE_ENODE_TYPE_SHIFT) \| MAPLE_ENODE_NULL);
321	}
322
323	static inline void ma_init_slot(void __rcu *slot, const struct maple_node mn,
324	const enum maple_type mt)
325	{
326	/* WARNING: this is unsafe if the slot is exposed to readers. */
327	RCU_INIT_POINTER(slot, (void )mt_mk_node(mn, mt));
328	}
329
330	static inline void mte_mk_root(const struct maple_enode node)
331	{
332	return (void *)((unsigned long)node \| MAPLE_ROOT_NODE);
333	}
334
335	static inline void mte_safe_root(const struct maple_enode node)
336	{
337	return (void *)((unsigned long)node & ~MAPLE_ROOT_NODE);
338	}
339
340	static inline void __maybe_unused mte_set_full(const struct maple_enode node)
341	{
342	return (void *)((unsigned long)node & ~MAPLE_ENODE_NULL);
343	}
344
345	static inline void __maybe_unused mte_clear_full(const struct maple_enode node)
346	{
347	return (void *)((unsigned long)node \| MAPLE_ENODE_NULL);
348	}
349
350	static inline bool __maybe_unused mte_has_null(const struct maple_enode *node)
351	{
352	return (unsigned long)node & MAPLE_ENODE_NULL;
353	}
354
355	static __always_inline bool ma_is_root(struct maple_node *node)
356	{
357	return ((unsigned long)node->parent & MA_ROOT_PARENT);
358	}
359
360	static __always_inline bool mte_is_root(const struct maple_enode *node)
361	{
362	return ma_is_root(mte_to_node(node));
363	}
364
365	static __always_inline bool mt_is_alloc(struct maple_tree *mt)
366	{
367	return (mt->ma_flags & MT_FLAGS_ALLOC_RANGE);
368	}
369
370	/*
371	* The Parent Pointer
372	* Excluding root, the parent pointer is 256B aligned like all other tree nodes.
373	* When storing a 32 or 64 bit values, the offset can fit into 5 bits. The 16
374	* bit values need an extra bit to store the offset. This extra bit comes from
375	* a reuse of the last bit in the node type. This is possible by using bit 1 to
376	* indicate if bit 2 is part of the type or the slot.
377	*
378	* Node types:
379	* 0b??1 = Root
380	* 0b?00 = 16 bit nodes
381	* 0b010 = 32 bit nodes
382	* 0b110 = 64 bit nodes
383	*
384	* Slot size and alignment
385	* 0b??1 : Root
386	* 0b?00 : 16 bit values, type in 0-1, slot in 2-7
387	* 0b010 : 32 bit values, type in 0-2, slot in 3-7
388	* 0b110 : 64 bit values, type in 0-2, slot in 3-7
389	*/
390
391	#define MAPLE_PARENT_ROOT 0x01
392
393	#define MAPLE_PARENT_SLOT_SHIFT 0x03
394	#define MAPLE_PARENT_SLOT_MASK 0xF8
395
396	#define MAPLE_PARENT_16B_SLOT_SHIFT 0x02
397	#define MAPLE_PARENT_16B_SLOT_MASK 0xFC
398
399	#define MAPLE_PARENT_RANGE64 0x06
400	#define MAPLE_PARENT_RANGE32 0x02
401	#define MAPLE_PARENT_NOT_RANGE16 0x02
402
403	/*
404	* mte_parent_shift() - Get the parent shift for the slot storage.
405	* @parent: The parent pointer cast as an unsigned long
406	* Return: The shift into that pointer to the star to of the slot
407	*/
408	static inline unsigned long mte_parent_shift(unsigned long parent)
409	{
410	/* Note bit 1 == 0 means 16B */
411	if (likely(parent & MAPLE_PARENT_NOT_RANGE16))
412	return MAPLE_PARENT_SLOT_SHIFT;
413
414	return MAPLE_PARENT_16B_SLOT_SHIFT;
415	}
416
417	/*
418	* mte_parent_slot_mask() - Get the slot mask for the parent.
419	* @parent: The parent pointer cast as an unsigned long.
420	* Return: The slot mask for that parent.
421	*/
422	static inline unsigned long mte_parent_slot_mask(unsigned long parent)
423	{
424	/* Note bit 1 == 0 means 16B */
425	if (likely(parent & MAPLE_PARENT_NOT_RANGE16))
426	return MAPLE_PARENT_SLOT_MASK;
427
428	return MAPLE_PARENT_16B_SLOT_MASK;
429	}
430
431	/*
432	* mas_parent_type() - Return the maple_type of the parent from the stored
433	* parent type.
434	* @mas: The maple state
435	* @enode: The maple_enode to extract the parent's enum
436	* Return: The node->parent maple_type
437	*/
438	static inline
439	enum maple_type mas_parent_type(struct ma_state mas, struct maple_enode enode)
440	{
441	unsigned long p_type;
442
443	p_type = (unsigned long)mte_to_node(enode)->parent;
444	if (WARN_ON(p_type & MAPLE_PARENT_ROOT))
445	return 0;
446
447	p_type &= MAPLE_NODE_MASK;
448	p_type &= ~mte_parent_slot_mask(p_type);
449	switch (p_type) {
450	case MAPLE_PARENT_RANGE64: /* or MAPLE_PARENT_ARANGE64 */
451	if (mt_is_alloc(mas->tree))
452	return maple_arange_64;
453	return maple_range_64;
454	}
455
456	return 0;
457	}
458
459	/*
460	* mte_parent_slot() - get the parent slot of @enode.
461	* @enode: The encoded maple node.
462	*
463	* Return: The slot in the parent node where @enode resides.
464	*/
465	static __always_inline
466	unsigned int mte_parent_slot(const struct maple_enode *enode)
467	{
468	unsigned long val = (unsigned long)mte_to_node(enode)->parent;
469
470	if (unlikely(val & MA_ROOT_PARENT))
471	return 0;
472
473	/*
474	* Okay to use MAPLE_PARENT_16B_SLOT_MASK as the last bit will be lost
475	* by shift if the parent shift is MAPLE_PARENT_SLOT_SHIFT
476	*/
477	return (val & MAPLE_PARENT_16B_SLOT_MASK) >> mte_parent_shift(val);
478	}
479
480	/*
481	* mte_parent() - Get the parent of @node.
482	* @enode: The encoded maple node.
483	*
484	* Return: The parent maple node.
485	*/
486	static __always_inline
487	struct maple_node mte_parent(const struct maple_enode enode)
488	{
489	return (void *)((unsigned long)
490	(mte_to_node(enode)->parent) & ~MAPLE_NODE_MASK);
491	}
492
493	/*
494	* ma_dead_node() - check if the @enode is dead.
495	* @enode: The encoded maple node
496	*
497	* Return: true if dead, false otherwise.
498	*/
499	static __always_inline bool ma_dead_node(const struct maple_node *node)
500	{
501	struct maple_node *parent;
502
503	/* Do not reorder reads from the node prior to the parent check */
504	smp_rmb();
505	parent = (void *)((unsigned long) node->parent & ~MAPLE_NODE_MASK);
506	return (parent == node);
507	}
508
509	/*
510	* mte_dead_node() - check if the @enode is dead.
511	* @enode: The encoded maple node
512	*
513	* Return: true if dead, false otherwise.
514	*/
515	static __always_inline bool mte_dead_node(const struct maple_enode *enode)
516	{
517	struct maple_node *node;
518
519	node = mte_to_node(enode);
520	return ma_dead_node(node);
521	}
522
523	/*
524	* ma_pivots() - Get a pointer to the maple node pivots.
525	* @node: the maple node
526	* @type: the node type
527	*
528	* In the event of a dead node, this array may be %NULL
529	*
530	* Return: A pointer to the maple node pivots
531	*/
532	static inline unsigned long ma_pivots(struct maple_node node,
533	enum maple_type type)
534	{
535	switch (type) {
536	case maple_arange_64:
537	return node->ma64.pivot;
538	case maple_range_64:
539	case maple_leaf_64:
540	return node->mr64.pivot;
541	case maple_copy:
542	return node->cp.pivot;
543	case maple_dense:
544	return NULL;
545	}
546	return NULL;
547	}
548
549	/*
550	* ma_gaps() - Get a pointer to the maple node gaps.
551	* @node: the maple node
552	* @type: the node type
553	*
554	* Return: A pointer to the maple node gaps
555	*/
556	static inline unsigned long ma_gaps(struct maple_node node,
557	enum maple_type type)
558	{
559	switch (type) {
560	case maple_arange_64:
561	return node->ma64.gap;
562	case maple_copy:
563	return node->cp.gap;
564	case maple_range_64:
565	case maple_leaf_64:
566	case maple_dense:
567	return NULL;
568	}
569	return NULL;
570	}
571
572	/*
573	* mas_safe_pivot() - get the pivot at @piv or mas->max.
574	* @mas: The maple state
575	* @pivots: The pointer to the maple node pivots
576	* @piv: The pivot to fetch
577	* @type: The maple node type
578	*
579	* Return: The pivot at @piv within the limit of the @pivots array, @mas->max
580	* otherwise.
581	*/
582	static __always_inline unsigned long
583	mas_safe_pivot(const struct ma_state mas, unsigned long pivots,
584	unsigned char piv, enum maple_type type)
585	{
586	if (piv >= mt_pivots[type])
587	return mas->max;
588
589	return pivots[piv];
590	}
591
592	/*
593	* mas_safe_min() - Return the minimum for a given offset.
594	* @mas: The maple state
595	* @pivots: The pointer to the maple node pivots
596	* @offset: The offset into the pivot array
597	*
598	* Return: The minimum range value that is contained in @offset.
599	*/
600	static inline unsigned long
601	mas_safe_min(struct ma_state mas, unsigned long pivots, unsigned char offset)
602	{
603	if (likely(offset))
604	return pivots[offset - 1] + 1;
605
606	return mas->min;
607	}
608
609	/*
610	* mte_set_pivot() - Set a pivot to a value in an encoded maple node.
611	* @mn: The encoded maple node
612	* @piv: The pivot offset
613	* @val: The value of the pivot
614	*/
615	static inline void mte_set_pivot(struct maple_enode *mn, unsigned char piv,
616	unsigned long val)
617	{
618	struct maple_node *node = mte_to_node(mn);
619	enum maple_type type = mte_node_type(mn);
620
621	BUG_ON(piv >= mt_pivots[type]);
622	switch (type) {
623	case maple_range_64:
624	case maple_leaf_64:
625	node->mr64.pivot[piv] = val;
626	break;
627	case maple_arange_64:
628	node->ma64.pivot[piv] = val;
629	break;
630	case maple_copy:
631	case maple_dense:
632	break;
633	}
634
635	}
636
637	/*
638	* ma_slots() - Get a pointer to the maple node slots.
639	* @mn: The maple node
640	* @mt: The maple node type
641	*
642	* Return: A pointer to the maple node slots
643	*/
644	static inline void __rcu *ma_slots(struct maple_node mn, enum maple_type mt)
645	{
646	switch (mt) {
647	case maple_arange_64:
648	return mn->ma64.slot;
649	case maple_range_64:
650	case maple_leaf_64:
651	return mn->mr64.slot;
652	case maple_copy:
653	return mn->cp.slot;
654	case maple_dense:
655	return mn->slot;
656	}
657
658	return NULL;
659	}
660
661	static inline bool mt_write_locked(const struct maple_tree *mt)
662	{
663	return mt_external_lock(mt) ? mt_write_lock_is_held(mt) :
664	lockdep_is_held(&mt->ma_lock);
665	}
666
667	static __always_inline bool mt_locked(const struct maple_tree *mt)
668	{
669	return mt_external_lock(mt) ? mt_lock_is_held(mt) :
670	lockdep_is_held(&mt->ma_lock);
671	}
672
673	static __always_inline void mt_slot(const struct maple_tree mt,
674	void __rcu **slots, unsigned char offset)
675	{
676	return rcu_dereference_check(slots[offset], mt_locked(mt));
677	}
678
679	static __always_inline void mt_slot_locked(struct maple_tree mt,
680	void __rcu **slots, unsigned char offset)
681	{
682	return rcu_dereference_protected(slots[offset], mt_write_locked(mt));
683	}
684	/*
685	* mas_slot_locked() - Get the slot value when holding the maple tree lock.
686	* @mas: The maple state
687	* @slots: The pointer to the slots
688	* @offset: The offset into the slots array to fetch
689	*
690	* Return: The entry stored in @slots at the @offset.
691	*/
692	static __always_inline void mas_slot_locked(struct ma_state mas,
693	void __rcu **slots, unsigned char offset)
694	{
695	return mt_slot_locked(mas->tree, slots, offset);
696	}
697
698	/*
699	* mas_slot() - Get the slot value when not holding the maple tree lock.
700	* @mas: The maple state
701	* @slots: The pointer to the slots
702	* @offset: The offset into the slots array to fetch
703	*
704	* Return: The entry stored in @slots at the @offset
705	*/
706	static __always_inline void mas_slot(struct ma_state mas, void __rcu **slots,
707	unsigned char offset)
708	{
709	return mt_slot(mas->tree, slots, offset);
710	}
711
712	/*
713	* mas_root() - Get the maple tree root.
714	* @mas: The maple state.
715	*
716	* Return: The pointer to the root of the tree
717	*/
718	static __always_inline void mas_root(struct ma_state mas)
719	{
720	return rcu_dereference_check(mas->tree->ma_root, mt_locked(mas->tree));
721	}
722
723	static inline void mt_root_locked(struct maple_tree mt)
724	{
725	return rcu_dereference_protected(mt->ma_root, mt_write_locked(mt));
726	}
727
728	/*
729	* mas_root_locked() - Get the maple tree root when holding the maple tree lock.
730	* @mas: The maple state.
731	*
732	* Return: The pointer to the root of the tree
733	*/
734	static inline void mas_root_locked(struct ma_state mas)
735	{
736	return mt_root_locked(mas->tree);
737	}
738
739	static inline struct maple_metadata ma_meta(struct maple_node mn,
740	enum maple_type mt)
741	{
742	switch (mt) {
743	case maple_arange_64:
744	return &mn->ma64.meta;
745	default:
746	return &mn->mr64.meta;
747	}
748	}
749
750	/*
751	* ma_set_meta() - Set the metadata information of a node.
752	* @mn: The maple node
753	* @mt: The maple node type
754	* @offset: The offset of the highest sub-gap in this node.
755	* @end: The end of the data in this node.
756	*/
757	static inline void ma_set_meta(struct maple_node *mn, enum maple_type mt,
758	unsigned char offset, unsigned char end)
759	{
760	struct maple_metadata *meta = ma_meta(mn, mt);
761
762	meta->gap = offset;
763	meta->end = end;
764	}
765
766	/*
767	* mt_clear_meta() - clear the metadata information of a node, if it exists
768	* @mt: The maple tree
769	* @mn: The maple node
770	* @type: The maple node type
771	*/
772	static inline void mt_clear_meta(struct maple_tree mt, struct maple_node mn,
773	enum maple_type type)
774	{
775	struct maple_metadata *meta;
776	unsigned long *pivots;
777	void __rcu **slots;
778	void *next;
779
780	switch (type) {
781	case maple_range_64:
782	pivots = mn->mr64.pivot;
783	if (unlikely(pivots[MAPLE_RANGE64_SLOTS - 2])) {
784	slots = mn->mr64.slot;
785	next = mt_slot_locked(mt, slots,
786	MAPLE_RANGE64_SLOTS - 1);
787	if (unlikely((mte_to_node(next) &&
788	mte_node_type(next))))
789	return; /* no metadata, could be node */
790	}
791	fallthrough;
792	case maple_arange_64:
793	meta = ma_meta(mn, type);
794	break;
795	default:
796	return;
797	}
798
799	meta->gap = 0;
800	meta->end = 0;
801	}
802
803	/*
804	* ma_meta_end() - Get the data end of a node from the metadata
805	* @mn: The maple node
806	* @mt: The maple node type
807	*/
808	static inline unsigned char ma_meta_end(struct maple_node *mn,
809	enum maple_type mt)
810	{
811	struct maple_metadata *meta = ma_meta(mn, mt);
812
813	return meta->end;
814	}
815
816	/*
817	* ma_meta_gap() - Get the largest gap location of a node from the metadata
818	* @mn: The maple node
819	*/
820	static inline unsigned char ma_meta_gap(struct maple_node *mn)
821	{
822	return mn->ma64.meta.gap;
823	}
824
825	/*
826	* ma_set_meta_gap() - Set the largest gap location in a nodes metadata
827	* @mn: The maple node
828	* @mt: The maple node type
829	* @offset: The location of the largest gap.
830	*/
831	static inline void ma_set_meta_gap(struct maple_node *mn, enum maple_type mt,
832	unsigned char offset)
833	{
834
835	struct maple_metadata *meta = ma_meta(mn, mt);
836
837	meta->gap = offset;
838	}
839
840	/*
841	* mas_set_parent_slots() - Bulk operation to set many slot parent pointers
842	* @mas: The maple state
843	* @parent: The encoded maple node that is the parent of @enode.
844	* @slot: The slot that of the @enode.
845	* @start_slot: The offset into @slot
846	* @count: The number of slots to set (eg: exclusive)
847	*/
848	static inline
849	void mas_set_parent_slots(struct ma_state mas, struct maple_enode parent,
850	void __rcu **slots, unsigned char start_slot, unsigned char count)
851	{
852	unsigned long val;
853	unsigned long shift;
854	unsigned long type;
855	enum maple_type p_type = mte_node_type(parent);
856	unsigned char i;
857
858	MAS_BUG_ON(mas, p_type != maple_range_64 &&
859	p_type != maple_arange_64);
860
861	shift = MAPLE_PARENT_SLOT_SHIFT;
862	type = MAPLE_PARENT_RANGE64;
863
864	val = (unsigned long)parent;
865	val &= ~MAPLE_NODE_MASK;
866
867	for (i = 0; i < count; i++) {
868	unsigned long pval = val \| ((start_slot + i) << shift) \| type;
869	struct maple_enode *child;
870
871	child = mt_slot_locked(mas->tree, slots, i);
872	mte_to_node(child)->parent = ma_parent_ptr(pval);
873	}
874	}
875
876	/*
877	* mat_add() - Add a @dead_enode to the ma_topiary of a list of dead nodes.
878	* @mat: the ma_topiary, a linked list of dead nodes.
879	* @dead_enode: the node to be marked as dead and added to the tail of the list
880	*
881	* Add the @dead_enode to the linked list in @mat.
882	*/
883	static inline void mat_add(struct ma_topiary *mat,
884	struct maple_enode *dead_enode)
885	{
886	mte_set_node_dead(dead_enode);
887	mte_to_mat(dead_enode)->next = NULL;
888	if (!mat->tail) {
889	mat->tail = mat->head = dead_enode;
890	return;
891	}
892
893	mte_to_mat(mat->tail)->next = dead_enode;
894	mat->tail = dead_enode;
895	}
896
897	static void mt_free_walk(struct rcu_head *head);
898	static void mt_destroy_walk(struct maple_enode enode, struct maple_tree mt,
899	bool free);
900	/*
901	* mas_mat_destroy() - Free all nodes and subtrees in a dead list.
902	* @mas: the maple state
903	* @mat: the ma_topiary linked list of dead nodes to free.
904	*
905	* Destroy walk a dead list.
906	*/
907	static void mas_mat_destroy(struct ma_state mas, struct ma_topiary mat)
908	{
909	struct maple_enode *next;
910	struct maple_node *node;
911	bool in_rcu = mt_in_rcu(mas->tree);
912
913	while (mat->head) {
914	next = mte_to_mat(mat->head)->next;
915	node = mte_to_node(mat->head);
916	mt_destroy_walk(mat->head, mas->tree, !in_rcu);
917	if (in_rcu)
918	call_rcu(&node->rcu, mt_free_walk);
919	mat->head = next;
920	}
921	}
922	/*
923	* mas_descend() - Descend into the slot stored in the ma_state.
924	* @mas: the maple state.
925	*
926	* Note: Not RCU safe, only use in write side or debug code.
927	*/
928	static inline void mas_descend(struct ma_state *mas)
929	{
930	enum maple_type type;
931	unsigned long *pivots;
932	struct maple_node *node;
933	void __rcu **slots;
934
935	node = mas_mn(mas);
936	type = mte_node_type(mas->node);
937	pivots = ma_pivots(node, type);
938	slots = ma_slots(node, type);
939
940	if (mas->offset)
941	mas->min = pivots[mas->offset - 1] + 1;
942	mas->max = mas_safe_pivot(mas, pivots, mas->offset, type);
943	mas->node = mas_slot(mas, slots, mas->offset);
944	}
945
946	/*
947	* mas_ascend() - Walk up a level of the tree.
948	* @mas: The maple state
949	*
950	* Sets the @mas->max and @mas->min for the parent node of mas->node. This
951	* may cause several levels of walking up to find the correct min and max.
952	* May find a dead node which will cause a premature return.
953	* Return: 1 on dead node, 0 otherwise
954	*/
955	static int mas_ascend(struct ma_state *mas)
956	{
957	struct maple_enode p_enode; / parent enode. */
958	struct maple_enode a_enode; / ancestor enode. */
959	struct maple_node a_node; / ancestor node. */
960	struct maple_node p_node; / parent node. */
961	unsigned char a_slot;
962	enum maple_type a_type;
963	unsigned long min, max;
964	unsigned long *pivots;
965	bool set_max = false, set_min = false;
966
967	a_node = mas_mn(mas);
968	if (ma_is_root(a_node)) {
969	mas->offset = 0;
970	return 0;
971	}
972
973	p_node = mte_parent(mas->node);
974	if (unlikely(a_node == p_node))
975	return 1;
976
977	a_type = mas_parent_type(mas, mas->node);
978	mas->offset = mte_parent_slot(mas->node);
979	a_enode = mt_mk_node(p_node, a_type);
980
981	/* Check to make sure all parent information is still accurate */
982	if (p_node != mte_parent(mas->node))
983	return 1;
984
985	mas->node = a_enode;
986
987	if (mte_is_root(a_enode)) {
988	mas->max = ULONG_MAX;
989	mas->min = 0;
990	return 0;
991	}
992
993	min = 0;
994	max = ULONG_MAX;
995
996	/*
997	* !mas->offset implies that parent node min == mas->min.
998	* mas->offset > 0 implies that we need to walk up to find the
999	* implied pivot min.
1000	*/
1001	if (!mas->offset) {
1002	min = mas->min;
1003	set_min = true;
1004	}
1005
1006	if (mas->max == ULONG_MAX)
1007	set_max = true;
1008
1009	do {
1010	p_enode = a_enode;
1011	a_type = mas_parent_type(mas, p_enode);
1012	a_node = mte_parent(p_enode);
1013	a_slot = mte_parent_slot(p_enode);
1014	a_enode = mt_mk_node(a_node, a_type);
1015	pivots = ma_pivots(a_node, a_type);
1016
1017	if (unlikely(ma_dead_node(a_node)))
1018	return 1;
1019
1020	if (!set_min && a_slot) {
1021	set_min = true;
1022	min = pivots[a_slot - 1] + 1;
1023	}
1024
1025	if (!set_max && a_slot < mt_pivots[a_type]) {
1026	set_max = true;
1027	max = pivots[a_slot];
1028	}
1029
1030	if (unlikely(ma_dead_node(a_node)))
1031	return 1;
1032
1033	if (unlikely(ma_is_root(a_node)))
1034	break;
1035
1036	} while (!set_min \|\| !set_max);
1037
1038	mas->max = max;
1039	mas->min = min;
1040	return 0;
1041	}
1042
1043	/*
1044	* mas_pop_node() - Get a previously allocated maple node from the maple state.
1045	* @mas: The maple state
1046	*
1047	* Return: A pointer to a maple node.
1048	*/
1049	static __always_inline struct maple_node mas_pop_node(struct ma_state mas)
1050	{
1051	struct maple_node *ret;
1052
1053	if (mas->alloc) {
1054	ret = mas->alloc;
1055	mas->alloc = NULL;
1056	goto out;
1057	}
1058
1059	if (WARN_ON_ONCE(!mas->sheaf))
1060	return NULL;
1061
1062	ret = kmem_cache_alloc_from_sheaf(maple_node_cache, GFP_NOWAIT, mas->sheaf);
1063
1064	out:
1065	memset(ret, 0, sizeof(*ret));
1066	return ret;
1067	}
1068
1069	/*
1070	* mas_alloc_nodes() - Allocate nodes into a maple state
1071	* @mas: The maple state
1072	* @gfp: The GFP Flags
1073	*/
1074	static inline void mas_alloc_nodes(struct ma_state *mas, gfp_t gfp)
1075	{
1076	if (!mas->node_request)
1077	return;
1078
1079	if (mas->node_request == 1) {
1080	if (mas->sheaf)
1081	goto use_sheaf;
1082
1083	if (mas->alloc)
1084	return;
1085
1086	mas->alloc = mt_alloc_one(gfp);
1087	if (!mas->alloc)
1088	goto error;
1089
1090	mas->node_request = 0;
1091	return;
1092	}
1093
1094	use_sheaf:
1095	if (unlikely(mas->alloc)) {
1096	kfree(mas->alloc);
1097	mas->alloc = NULL;
1098	}
1099
1100	if (mas->sheaf) {
1101	unsigned long refill;
1102
1103	refill = mas->node_request;
1104	if (kmem_cache_sheaf_size(mas->sheaf) >= refill) {
1105	mas->node_request = 0;
1106	return;
1107	}
1108
1109	if (mt_refill_sheaf(gfp, &mas->sheaf, refill))
1110	goto error;
1111
1112	mas->node_request = 0;
1113	return;
1114	}
1115
1116	mas->sheaf = mt_get_sheaf(gfp, mas->node_request);
1117	if (likely(mas->sheaf)) {
1118	mas->node_request = 0;
1119	return;
1120	}
1121
1122	error:
1123	mas_set_err(mas, -ENOMEM);
1124	}
1125
1126	static inline void mas_empty_nodes(struct ma_state *mas)
1127	{
1128	mas->node_request = 0;
1129	if (mas->sheaf) {
1130	mt_return_sheaf(mas->sheaf);
1131	mas->sheaf = NULL;
1132	}
1133
1134	if (mas->alloc) {
1135	kfree(mas->alloc);
1136	mas->alloc = NULL;
1137	}
1138	}
1139
1140	/*
1141	* mas_free() - Free an encoded maple node
1142	* @mas: The maple state
1143	* @used: The encoded maple node to free.
1144	*
1145	* Uses rcu free if necessary, pushes @used back on the maple state allocations
1146	* otherwise.
1147	*/
1148	static inline void mas_free(struct ma_state mas, struct maple_enode used)
1149	{
1150	ma_free_rcu(mte_to_node(used));
1151	}
1152
1153
1154	#ifdef CONFIG_LOCKDEP
1155	static struct lockdep_map mas_lockdep_map(struct ma_state mas)
1156	{
1157	struct maple_tree *mt = mas->tree;
1158
1159	if (mt_external_lock(mt))
1160	return mt->ma_external_lock;
1161
1162	return &(mt->ma_lock).dep_map;
1163	}
1164
1165	#endif
1166
1167	static void mas_lock_check(struct ma_state *mas)
1168	{
1169	#ifdef CONFIG_LOCKDEP
1170	struct lockdep_map *map;
1171	u32 seq;
1172
1173	if (!mas_is_active(mas))
1174	return;
1175
1176	#ifdef CONFIG_RCU_STRICT_GRACE_PERIOD
1177	if (!mt_locked(mas->tree)) {
1178	if (mt_in_rcu(mas->tree))
1179	WARN_ON_ONCE(poll_state_synchronize_rcu(mas->rcu_gp));
1180	}
1181	#endif /* CONFIG_RCU_STRICT_GRACE_PERIOD */
1182
1183	map = mas_lockdep_map(mas);
1184	if (!map)
1185	return;
1186
1187	seq = lock_sequence(map);
1188	if (seq != UINT_MAX && mas->ld_seq != UINT_MAX)
1189	WARN_ON_ONCE(mas->ld_seq != seq);
1190	#endif /* CONFIG_LOCKDEP */
1191
1192	}
1193
1194	static void mas_init_lock_check(struct ma_state *mas)
1195	{
1196	#ifdef CONFIG_LOCKDEP
1197	struct lockdep_map *map;
1198	#ifdef CONFIG_RCU_STRICT_GRACE_PERIOD
1199	if (!mt_locked(mas->tree)) {
1200	if (mt_in_rcu(mas->tree))
1201	mas->rcu_gp = get_state_synchronize_rcu();
1202	return;
1203	}
1204	#endif /* CONFIG_RCU_STRICT_GRACE_PERIOD */
1205
1206	map = mas_lockdep_map(mas);
1207	if (map) /* Update regardless of lock state */
1208	mas->ld_seq = lock_sequence(map);
1209	#endif /* CONFIG_LOCKDEP */
1210
1211	}
1212
1213	static void mas_may_init_lock_check(struct ma_state *mas)
1214	{
1215	#ifdef CONFIG_LOCKDEP
1216	#ifdef CONFIG_RCU_STRICT_GRACE_PERIOD
1217	if (mas_is_start(mas) \|\| mas_is_paused(mas)) {
1218	mas_init_lock_check(mas);
1219	return;
1220	}
1221	#endif /* CONFIG_RCU_STRICT_GRACE_PERIOD */
1222	mas_lock_check(mas);
1223	#endif /* CONFIG_LOCKDEP */
1224	}
1225
1226	/*
1227	* mas_start() - Sets up maple state for operations.
1228	* @mas: The maple state.
1229	*
1230	* If mas->status == ma_start, then set the min, max and depth to
1231	* defaults.
1232	*
1233	* Return:
1234	* - If mas->node is an error or not mas_start, return NULL.
1235	* - If it's an empty tree: NULL & mas->status == ma_none
1236	* - If it's a single entry: The entry & mas->status == ma_root
1237	* - If it's a tree: NULL & mas->status == ma_active
1238	*/
1239	static inline struct maple_enode mas_start(struct ma_state mas)
1240	{
1241	if (likely(mas_is_start(mas))) {
1242	struct maple_enode *root;
1243
1244	mas_init_lock_check(mas);
1245	mas->min = 0;
1246	mas->max = ULONG_MAX;
1247
1248	retry:
1249	mas->depth = 0;
1250	root = mas_root(mas);
1251	/* Tree with nodes */
1252	if (likely(xa_is_node(root))) {
1253	mas->depth = 0;
1254	mas->status = ma_active;
1255	mas->node = mte_safe_root(root);
1256	mas->offset = 0;
1257	if (mte_dead_node(mas->node))
1258	goto retry;
1259
1260	return NULL;
1261	}
1262
1263	mas->node = NULL;
1264	/* empty tree */
1265	if (unlikely(!root)) {
1266	mas->status = ma_none;
1267	mas->offset = MAPLE_NODE_SLOTS;
1268	return NULL;
1269	}
1270
1271	/* Single entry tree */
1272	mas->status = ma_root;
1273	mas->offset = MAPLE_NODE_SLOTS;
1274
1275	/* Single entry tree. */
1276	if (mas->index > 0)
1277	return NULL;
1278
1279	return root;
1280	}
1281
1282	return NULL;
1283	}
1284
1285	/*
1286	* ma_data_end() - Find the end of the data in a node.
1287	* @node: The maple node
1288	* @type: The maple node type
1289	* @pivots: The array of pivots in the node
1290	* @max: The maximum value in the node
1291	*
1292	* Uses metadata to find the end of the data when possible.
1293	* Return: The zero indexed last slot with data (may be null).
1294	*/
1295	static __always_inline unsigned char ma_data_end(struct maple_node *node,
1296	enum maple_type type, unsigned long *pivots, unsigned long max)
1297	{
1298	unsigned char offset;
1299
1300	if (!pivots)
1301	return 0;
1302
1303	if (type == maple_arange_64)
1304	return ma_meta_end(node, type);
1305
1306	offset = mt_pivots[type] - 1;
1307	if (likely(!pivots[offset]))
1308	return ma_meta_end(node, type);
1309
1310	if (likely(pivots[offset] == max))
1311	return offset;
1312
1313	return mt_pivots[type];
1314	}
1315
1316	/*
1317	* mas_data_end() - Find the end of the data (slot).
1318	* @mas: the maple state
1319	*
1320	* This method is optimized to check the metadata of a node if the node type
1321	* supports data end metadata.
1322	*
1323	* Return: The zero indexed last slot with data (may be null).
1324	*/
1325	static inline unsigned char mas_data_end(struct ma_state *mas)
1326	{
1327	enum maple_type type;
1328	struct maple_node *node;
1329	unsigned char offset;
1330	unsigned long *pivots;
1331
1332	type = mte_node_type(mas->node);
1333	node = mas_mn(mas);
1334	if (type == maple_arange_64)
1335	return ma_meta_end(node, type);
1336
1337	pivots = ma_pivots(node, type);
1338	if (unlikely(ma_dead_node(node)))
1339	return 0;
1340
1341	offset = mt_pivots[type] - 1;
1342	if (likely(!pivots[offset]))
1343	return ma_meta_end(node, type);
1344
1345	if (likely(pivots[offset] == mas->max))
1346	return offset;
1347
1348	return mt_pivots[type];
1349	}
1350
1351	static inline
1352	void wr_mas_setup(struct ma_wr_state wr_mas, struct ma_state mas)
1353	{
1354	wr_mas->node = mas_mn(mas);
1355	wr_mas->type = mte_node_type(mas->node);
1356	wr_mas->pivots = ma_pivots(wr_mas->node, wr_mas->type);
1357	wr_mas->slots = ma_slots(wr_mas->node, wr_mas->type);
1358	wr_mas->r_min = mas_safe_min(mas, wr_mas->pivots, mas->offset);
1359	wr_mas->r_max = mas_safe_pivot(mas, wr_mas->pivots, mas->offset,
1360	wr_mas->type);
1361	}
1362
1363	static inline
1364	void wr_mas_ascend(struct ma_wr_state *wr_mas)
1365	{
1366	struct ma_state *mas = wr_mas->mas;
1367
1368	mas_ascend(mas);
1369	wr_mas_setup(wr_mas, mas);
1370	mas->end = ma_data_end(wr_mas->node, wr_mas->type, wr_mas->pivots,
1371	mas->max);
1372	/* Careful, this may be wrong.. */
1373	wr_mas->end_piv = wr_mas->r_max;
1374	wr_mas->offset_end = mas->offset;
1375	}
1376
1377	static inline unsigned long ma_leaf_max_gap(struct maple_node *mn,
1378	enum maple_type mt, unsigned long min, unsigned long max,
1379	unsigned long pivots, void __rcu *slots)
1380	{
1381	unsigned long pstart, gap, max_gap;
1382	unsigned char i;
1383	unsigned char max_piv;
1384
1385	max_gap = 0;
1386	if (unlikely(ma_is_dense(mt))) {
1387	gap = 0;
1388	for (i = 0; i < mt_slots[mt]; i++) {
1389	if (slots[i]) {
1390	if (gap > max_gap)
1391	max_gap = gap;
1392	gap = 0;
1393	} else {
1394	gap++;
1395	}
1396	}
1397	if (gap > max_gap)
1398	max_gap = gap;
1399	return max_gap;
1400	}
1401
1402	/*
1403	* Check the first implied pivot optimizes the loop below and slot 1 may
1404	* be skipped if there is a gap in slot 0.
1405	*/
1406	if (likely(!slots[0])) {
1407	max_gap = pivots[0] - min + 1;
1408	i = 2;
1409	} else {
1410	i = 1;
1411	}
1412
1413	/* reduce max_piv as the special case is checked before the loop */
1414	max_piv = ma_data_end(mn, mt, pivots, max) - 1;
1415	/*
1416	* Check end implied pivot which can only be a gap on the right most
1417	* node.
1418	*/
1419	if (unlikely(max == ULONG_MAX) && !slots[max_piv + 1]) {
1420	gap = ULONG_MAX - pivots[max_piv];
1421	if (gap > max_gap)
1422	max_gap = gap;
1423
1424	if (max_gap > pivots[max_piv] - min)
1425	return max_gap;
1426	}
1427
1428	for (; i <= max_piv; i++) {
1429	/* data == no gap. */
1430	if (likely(slots[i]))
1431	continue;
1432
1433	pstart = pivots[i - 1];
1434	gap = pivots[i] - pstart;
1435	if (gap > max_gap)
1436	max_gap = gap;
1437
1438	/* There cannot be two gaps in a row. */
1439	i++;
1440	}
1441	return max_gap;
1442	}
1443
1444	/*
1445	* mas_leaf_max_gap() - Returns the largest gap in a leaf node
1446	* @mas: the maple state
1447	*
1448	* Return: The maximum gap in the leaf.
1449	*/
1450	static inline unsigned long mas_leaf_max_gap(struct ma_state *mas)
1451	{
1452	enum maple_type mt;
1453	struct maple_node *mn;
1454	unsigned long *pivots;
1455	void __rcu **slots;
1456
1457	mn = mas_mn(mas);
1458	mt = mte_node_type(mas->node);
1459	slots = ma_slots(mn, mt);
1460	pivots = ma_pivots(mn, mt);
1461
1462	return ma_leaf_max_gap(mn, mt, mas->min, mas->max, pivots, slots);
1463	}
1464
1465	/*
1466	* ma_max_gap() - Get the maximum gap in a maple node (non-leaf)
1467	* @node: The maple node
1468	* @gaps: The pointer to the gaps
1469	* @mt: The maple node type
1470	* @off: Pointer to store the offset location of the gap.
1471	*
1472	* Uses the metadata data end to scan backwards across set gaps.
1473	*
1474	* Return: The maximum gap value
1475	*/
1476	static inline unsigned long
1477	ma_max_gap(struct maple_node node, unsigned long gaps, enum maple_type mt,
1478	unsigned char *off)
1479	{
1480	unsigned char offset, i;
1481	unsigned long max_gap = 0;
1482
1483	i = offset = ma_meta_end(node, mt);
1484	do {
1485	if (gaps[i] > max_gap) {
1486	max_gap = gaps[i];
1487	offset = i;
1488	}
1489	} while (i--);
1490
1491	*off = offset;
1492	return max_gap;
1493	}
1494
1495	/*
1496	* mas_max_gap() - find the largest gap in a non-leaf node and set the slot.
1497	* @mas: The maple state.
1498	*
1499	* Return: The gap value.
1500	*/
1501	static inline unsigned long mas_max_gap(struct ma_state *mas)
1502	{
1503	unsigned long *gaps;
1504	unsigned char offset;
1505	enum maple_type mt;
1506	struct maple_node *node;
1507
1508	mt = mte_node_type(mas->node);
1509	if (ma_is_leaf(mt))
1510	return mas_leaf_max_gap(mas);
1511
1512	node = mas_mn(mas);
1513	MAS_BUG_ON(mas, mt != maple_arange_64);
1514	offset = ma_meta_gap(node);
1515	gaps = ma_gaps(node, mt);
1516	return gaps[offset];
1517	}
1518
1519	/*
1520	* mas_parent_gap() - Set the parent gap and any gaps above, as needed
1521	* @mas: The maple state
1522	* @offset: The gap offset in the parent to set
1523	* @new: The new gap value.
1524	*
1525	* Set the parent gap then continue to set the gap upwards, using the metadata
1526	* of the parent to see if it is necessary to check the node above.
1527	*/
1528	static inline void mas_parent_gap(struct ma_state *mas, unsigned char offset,
1529	unsigned long new)
1530	{
1531	unsigned long meta_gap = 0;
1532	struct maple_node *pnode;
1533	struct maple_enode *penode;
1534	unsigned long *pgaps;
1535	unsigned char meta_offset;
1536	enum maple_type pmt;
1537
1538	pnode = mte_parent(mas->node);
1539	pmt = mas_parent_type(mas, mas->node);
1540	penode = mt_mk_node(pnode, pmt);
1541	pgaps = ma_gaps(pnode, pmt);
1542
1543	ascend:
1544	MAS_BUG_ON(mas, pmt != maple_arange_64);
1545	meta_offset = ma_meta_gap(pnode);
1546	meta_gap = pgaps[meta_offset];
1547
1548	pgaps[offset] = new;
1549
1550	if (meta_gap == new)
1551	return;
1552
1553	if (offset != meta_offset) {
1554	if (meta_gap > new)
1555	return;
1556
1557	ma_set_meta_gap(pnode, pmt, offset);
1558	} else if (new < meta_gap) {
1559	new = ma_max_gap(pnode, pgaps, pmt, &meta_offset);
1560	ma_set_meta_gap(pnode, pmt, meta_offset);
1561	}
1562
1563	if (ma_is_root(pnode))
1564	return;
1565
1566	/* Go to the parent node. */
1567	pnode = mte_parent(penode);
1568	pmt = mas_parent_type(mas, penode);
1569	pgaps = ma_gaps(pnode, pmt);
1570	offset = mte_parent_slot(penode);
1571	penode = mt_mk_node(pnode, pmt);
1572	goto ascend;
1573	}
1574
1575	static __always_inline void mas_update_gap_known(struct ma_state *mas,
1576	unsigned long gap)
1577	{
1578	unsigned char pslot;
1579	unsigned long p_gap;
1580
1581	pslot = mte_parent_slot(mas->node);
1582	p_gap = ma_gaps(mte_parent(mas->node),
1583	mas_parent_type(mas, mas->node))[pslot];
1584
1585	if (p_gap != gap)
1586	mas_parent_gap(mas, pslot, gap);
1587	}
1588
1589	/*
1590	* mas_update_gap() - Update a nodes gaps and propagate up if necessary.
1591	* @mas: the maple state.
1592	*/
1593	static inline void mas_update_gap(struct ma_state *mas)
1594	{
1595	unsigned long max_gap;
1596
1597	if (!mt_is_alloc(mas->tree))
1598	return;
1599
1600	if (mte_is_root(mas->node))
1601	return;
1602
1603	max_gap = mas_max_gap(mas);
1604	mas_update_gap_known(mas, max_gap);
1605	}
1606
1607	/*
1608	* mas_adopt_children() - Set the parent pointer of all nodes in @parent to
1609	* @parent with the slot encoded.
1610	* @mas: the maple state (for the tree)
1611	* @parent: the maple encoded node containing the children.
1612	*/
1613	static inline void mas_adopt_children(struct ma_state *mas,
1614	struct maple_enode *parent)
1615	{
1616	enum maple_type type = mte_node_type(parent);
1617	struct maple_node *node = mte_to_node(parent);
1618	void __rcu **slots = ma_slots(node, type);
1619	unsigned long *pivots = ma_pivots(node, type);
1620	unsigned char end;
1621
1622	end = ma_data_end(node, type, pivots, mas->max);
1623	mas_set_parent_slots(mas, parent, slots, 0, end + 1);
1624	}
1625
1626	/*
1627	* mas_put_in_tree() - Put a new node in the tree, smp_wmb(), and mark the old
1628	* node as dead.
1629	* @mas: the maple state with the new node
1630	* @old_enode: The old maple encoded node to replace.
1631	* @new_height: if we are inserting a root node, update the height of the tree
1632	*/
1633	static inline void mas_put_in_tree(struct ma_state *mas,
1634	struct maple_enode *old_enode, char new_height)
1635	__must_hold(mas->tree->ma_lock)
1636	{
1637	unsigned char offset;
1638	void __rcu **slots;
1639
1640	if (mte_is_root(mas->node)) {
1641	mas_mn(mas)->parent = ma_parent_ptr(mas_tree_parent(mas));
1642	rcu_assign_pointer(mas->tree->ma_root, mte_mk_root(mas->node));
1643	mt_set_height(mas->tree, new_height);
1644	} else {
1645
1646	offset = mte_parent_slot(mas->node);
1647	slots = ma_slots(mte_parent(mas->node),
1648	mas_parent_type(mas, mas->node));
1649	rcu_assign_pointer(slots[offset], mas->node);
1650	}
1651
1652	mte_set_node_dead(old_enode);
1653	}
1654
1655	/*
1656	* mas_replace_node() - Replace a node by putting it in the tree, marking it
1657	* dead, and freeing it.
1658	* the parent encoding to locate the maple node in the tree.
1659	* @mas: the ma_state with @mas->node pointing to the new node.
1660	* @old_enode: The old maple encoded node.
1661	* @new_height: The new height of the tree as a result of the operation
1662	*/
1663	static inline void mas_replace_node(struct ma_state *mas,
1664	struct maple_enode *old_enode, unsigned char new_height)
1665	__must_hold(mas->tree->ma_lock)
1666	{
1667	mas_put_in_tree(mas, old_enode, new_height);
1668	mas_free(mas, old_enode);
1669	}
1670
1671	/*
1672	* mas_find_child() - Find a child who has the parent @mas->node.
1673	* @mas: the maple state with the parent.
1674	* @child: the maple state to store the child.
1675	*/
1676	static inline bool mas_find_child(struct ma_state mas, struct ma_state child)
1677	__must_hold(mas->tree->ma_lock)
1678	{
1679	enum maple_type mt;
1680	unsigned char offset;
1681	unsigned char end;
1682	unsigned long *pivots;
1683	struct maple_enode *entry;
1684	struct maple_node *node;
1685	void __rcu **slots;
1686
1687	mt = mte_node_type(mas->node);
1688	node = mas_mn(mas);
1689	slots = ma_slots(node, mt);
1690	pivots = ma_pivots(node, mt);
1691	end = ma_data_end(node, mt, pivots, mas->max);
1692	for (offset = mas->offset; offset <= end; offset++) {
1693	entry = mas_slot_locked(mas, slots, offset);
1694	if (mte_parent(entry) == node) {
1695	child = mas;
1696	mas->offset = offset + 1;
1697	child->offset = offset;
1698	mas_descend(child);
1699	child->offset = 0;
1700	return true;
1701	}
1702	}
1703	return false;
1704	}
1705
1706	/*
1707	* mas_leaf_set_meta() - Set the metadata of a leaf if possible.
1708	* @node: The maple node
1709	* @mt: The maple type
1710	* @end: The node end
1711	*/
1712	static inline void mas_leaf_set_meta(struct maple_node *node,
1713	enum maple_type mt, unsigned char end)
1714	{
1715	if (end < mt_slots[mt] - 1)
1716	ma_set_meta(node, mt, 0, end);
1717	}
1718
1719	/*
1720	* mas_prev_sibling() - Find the previous node with the same parent.
1721	* @mas: the maple state
1722	*
1723	* Return: True if there is a previous sibling, false otherwise.
1724	*/
1725	static inline bool mas_prev_sibling(struct ma_state *mas)
1726	{
1727	unsigned int p_slot = mte_parent_slot(mas->node);
1728
1729	/* For root node, p_slot is set to 0 by mte_parent_slot(). */
1730	if (!p_slot)
1731	return false;
1732
1733	mas_ascend(mas);
1734	mas->offset = p_slot - 1;
1735	mas_descend(mas);
1736	return true;
1737	}
1738
1739	/*
1740	* mas_next_sibling() - Find the next node with the same parent.
1741	* @mas: the maple state
1742	*
1743	* Return: true if there is a next sibling, false otherwise.
1744	*/
1745	static inline bool mas_next_sibling(struct ma_state *mas)
1746	{
1747	MA_STATE(parent, mas->tree, mas->index, mas->last);
1748
1749	if (mte_is_root(mas->node))
1750	return false;
1751
1752	parent = *mas;
1753	mas_ascend(&parent);
1754	parent.offset = mte_parent_slot(mas->node) + 1;
1755	if (parent.offset > mas_data_end(&parent))
1756	return false;
1757
1758	*mas = parent;
1759	mas_descend(mas);
1760	return true;
1761	}
1762
1763	/*
1764	* mas_wr_node_walk() - Find the correct offset for the index in the @mas.
1765	* If @mas->index cannot be found within the containing
1766	* node, we traverse to the last entry in the node.
1767	* @wr_mas: The maple write state
1768	*
1769	* Uses mas_slot_locked() and does not need to worry about dead nodes.
1770	*/
1771	static inline void mas_wr_node_walk(struct ma_wr_state *wr_mas)
1772	{
1773	struct ma_state *mas = wr_mas->mas;
1774	unsigned char count, offset;
1775
1776	if (unlikely(ma_is_dense(wr_mas->type))) {
1777	wr_mas->r_max = wr_mas->r_min = mas->index;
1778	mas->offset = mas->index = mas->min;
1779	return;
1780	}
1781
1782	wr_mas->node = mas_mn(wr_mas->mas);
1783	wr_mas->pivots = ma_pivots(wr_mas->node, wr_mas->type);
1784	count = mas->end = ma_data_end(wr_mas->node, wr_mas->type,
1785	wr_mas->pivots, mas->max);
1786	offset = mas->offset;
1787
1788	while (offset < count && mas->index > wr_mas->pivots[offset])
1789	offset++;
1790
1791	wr_mas->r_max = offset < count ? wr_mas->pivots[offset] : mas->max;
1792	wr_mas->r_min = mas_safe_min(mas, wr_mas->pivots, offset);
1793	wr_mas->offset_end = mas->offset = offset;
1794	}
1795
1796	static inline void rebalance_sib(struct ma_state parent, struct ma_state sib)
1797	{
1798	sib = parent;
1799	/* Prioritize move right to pull data left */
1800	if (sib->offset < sib->end)
1801	sib->offset++;
1802	else
1803	sib->offset--;
1804
1805	mas_descend(sib);
1806	sib->end = mas_data_end(sib);
1807	}
1808
1809	static inline
1810	void spanning_sib(struct ma_wr_state *l_wr_mas,
1811	struct ma_wr_state r_wr_mas, struct ma_state nneighbour)
1812	{
1813	struct ma_state l_tmp = *l_wr_mas->mas;
1814	struct ma_state r_tmp = *r_wr_mas->mas;
1815	unsigned char depth = 0;
1816
1817	do {
1818	mas_ascend(&r_tmp);
1819	mas_ascend(&l_tmp);
1820	depth++;
1821	if (r_tmp.offset < mas_data_end(&r_tmp)) {
1822	r_tmp.offset++;
1823	mas_descend(&r_tmp);
1824	r_tmp.offset = 0;
1825	while (--depth)
1826	mas_descend(&r_tmp);
1827
1828	r_tmp.end = mas_data_end(&r_tmp);
1829	*nneighbour = r_tmp;
1830	return;
1831	} else if (l_tmp.offset) {
1832	l_tmp.offset--;
1833	do {
1834	mas_descend(&l_tmp);
1835	l_tmp.offset = mas_data_end(&l_tmp);
1836	} while (--depth);
1837
1838	l_tmp.end = l_tmp.offset;
1839	*nneighbour = l_tmp;
1840	return;
1841	}
1842	} while (!mte_is_root(r_tmp.node));
1843
1844	WARN_ON_ONCE(1);
1845	}
1846
1847	/*
1848	* mas_topiary_node() - Dispose of a single node
1849	* @mas: The maple state for pushing nodes
1850	* @in_rcu: If the tree is in rcu mode
1851	*
1852	* The node will either be RCU freed or pushed back on the maple state.
1853	*/
1854	static inline void mas_topiary_node(struct ma_state *mas,
1855	struct ma_state *tmp_mas, bool in_rcu)
1856	{
1857	struct maple_node *tmp;
1858	struct maple_enode *enode;
1859
1860	if (mas_is_none(tmp_mas))
1861	return;
1862
1863	enode = tmp_mas->node;
1864	tmp = mte_to_node(enode);
1865	mte_set_node_dead(enode);
1866	ma_free_rcu(tmp);
1867	}
1868
1869	/*
1870	* mas_topiary_replace() - Replace the data with new data, then repair the
1871	* parent links within the new tree. Iterate over the dead sub-tree and collect
1872	* the dead subtrees and topiary the nodes that are no longer of use.
1873	*
1874	* The new tree will have up to three children with the correct parent. Keep
1875	* track of the new entries as they need to be followed to find the next level
1876	* of new entries.
1877	*
1878	* The old tree will have up to three children with the old parent. Keep track
1879	* of the old entries as they may have more nodes below replaced. Nodes within
1880	* [index, last] are dead subtrees, others need to be freed and followed.
1881	*
1882	* @mas: The maple state pointing at the new data
1883	* @old_enode: The maple encoded node being replaced
1884	* @new_height: The new height of the tree as a result of the operation
1885	*
1886	*/
1887	static inline void mas_topiary_replace(struct ma_state *mas,
1888	struct maple_enode *old_enode, unsigned char new_height)
1889	{
1890	struct ma_state tmp[3], tmp_next[3];
1891	MA_TOPIARY(subtrees, mas->tree);
1892	bool in_rcu;
1893	int i, n;
1894
1895	/* Place data in tree & then mark node as old */
1896	mas_put_in_tree(mas, old_enode, new_height);
1897
1898	/* Update the parent pointers in the tree */
1899	tmp[0] = *mas;
1900	tmp[0].offset = 0;
1901	tmp[1].status = ma_none;
1902	tmp[2].status = ma_none;
1903	while (!mte_is_leaf(tmp[0].node)) {
1904	n = 0;
1905	for (i = 0; i < 3; i++) {
1906	if (mas_is_none(&tmp[i]))
1907	continue;
1908
1909	while (n < 3) {
1910	if (!mas_find_child(&tmp[i], &tmp_next[n]))
1911	break;
1912	n++;
1913	}
1914
1915	mas_adopt_children(&tmp[i], tmp[i].node);
1916	}
1917
1918	if (MAS_WARN_ON(mas, n == 0))
1919	break;
1920
1921	while (n < 3)
1922	tmp_next[n++].status = ma_none;
1923
1924	for (i = 0; i < 3; i++)
1925	tmp[i] = tmp_next[i];
1926	}
1927
1928	/* Collect the old nodes that need to be discarded */
1929	if (mte_is_leaf(old_enode))
1930	return mas_free(mas, old_enode);
1931
1932	tmp[0] = *mas;
1933	tmp[0].offset = 0;
1934	tmp[0].node = old_enode;
1935	tmp[1].status = ma_none;
1936	tmp[2].status = ma_none;
1937	in_rcu = mt_in_rcu(mas->tree);
1938	do {
1939	n = 0;
1940	for (i = 0; i < 3; i++) {
1941	if (mas_is_none(&tmp[i]))
1942	continue;
1943
1944	while (n < 3) {
1945	if (!mas_find_child(&tmp[i], &tmp_next[n]))
1946	break;
1947
1948	if ((tmp_next[n].min >= tmp_next->index) &&
1949	(tmp_next[n].max <= tmp_next->last)) {
1950	mat_add(&subtrees, tmp_next[n].node);
1951	tmp_next[n].status = ma_none;
1952	} else {
1953	n++;
1954	}
1955	}
1956	}
1957
1958	if (MAS_WARN_ON(mas, n == 0))
1959	break;
1960
1961	while (n < 3)
1962	tmp_next[n++].status = ma_none;
1963
1964	for (i = 0; i < 3; i++) {
1965	mas_topiary_node(mas, &tmp[i], in_rcu);
1966	tmp[i] = tmp_next[i];
1967	}
1968	} while (!mte_is_leaf(tmp[0].node));
1969
1970	for (i = 0; i < 3; i++)
1971	mas_topiary_node(mas, &tmp[i], in_rcu);
1972
1973	mas_mat_destroy(mas, &subtrees);
1974	}
1975
1976	/*
1977	* node_copy() - Copy from one node to another.
1978	*
1979	* @mas: The maple state
1980	* @src: The source node
1981	* @start: The offset into the src to start copying
1982	* @size: The size to copy (non-zero)
1983	* @s_max: The source node max
1984	* @s_mt: The source maple node type
1985	* @dst: The destination
1986	* @d_start: The start location in the destination node
1987	* @d_mt: The destination maple node type
1988	*/
1989	static inline
1990	unsigned long node_copy(struct ma_state mas, struct maple_node src,
1991	unsigned char start, unsigned char size, unsigned long s_max,
1992	enum maple_type s_mt, struct maple_node *dst, unsigned char d_start,
1993	enum maple_type d_mt)
1994	{
1995	unsigned long s_pivots, d_pivots;
1996	void __rcu s_slots, d_slots;
1997	unsigned long s_gaps, d_gaps;
1998	unsigned long d_max;
1999
2000	d_slots = ma_slots(dst, d_mt) + d_start;
2001	d_pivots = ma_pivots(dst, d_mt) + d_start;
2002	s_slots = ma_slots(src, s_mt) + start;
2003	s_pivots = ma_pivots(src, s_mt) + start;
2004	memcpy(d_slots, s_slots, size * sizeof(void __rcu *));
2005
2006	if (!ma_is_leaf(d_mt) && s_mt == maple_copy)
2007	mas_set_parent_slots(mas, mt_mk_node(dst, d_mt),
2008	d_slots, d_start, size);
2009
2010	d_gaps = ma_gaps(dst, d_mt);
2011	if (d_gaps) {
2012	s_gaps = ma_gaps(src, s_mt) + start;
2013	d_gaps += d_start;
2014	memcpy(d_gaps, s_gaps, size * sizeof(unsigned long));
2015	}
2016
2017	if (start + size - 1 < mt_pivots[s_mt])
2018	d_max = s_pivots[size - 1];
2019	else
2020	d_max = s_max;
2021
2022	if (d_start + size <= mt_pivots[d_mt])
2023	d_pivots[size - 1] = d_max;
2024
2025	size--;
2026	if (size)
2027	memcpy(d_pivots, s_pivots, size * sizeof(unsigned long));
2028
2029	return d_max;
2030	}
2031
2032	/*
2033	* node_finalise() - Zero out unused area and populate metadata
2034	* @node: The maple node
2035	* @mt: The maple node type
2036	* @end: The end of the used area
2037	*/
2038	static inline
2039	void node_finalise(struct maple_node *node, enum maple_type mt,
2040	unsigned char end)
2041	{
2042	unsigned char max_end = mt_slots[mt];
2043	unsigned char size;
2044	unsigned long *gaps;
2045	unsigned char gap_slot;
2046
2047	gaps = ma_gaps(node, mt);
2048	if (end < max_end - 1) {
2049	size = max_end - end;
2050	memset(ma_slots(node, mt) + end, 0, size * sizeof(void *));
2051
2052	if (gaps)
2053	memset(gaps + end, 0, size * sizeof(unsigned long));
2054
2055	if (--size)
2056	memset(ma_pivots(node, mt) + end, 0, size * sizeof(unsigned long));
2057	}
2058
2059	gap_slot = 0;
2060	if (gaps && !ma_is_leaf(mt)) {
2061	unsigned long max_gap;
2062
2063	max_gap = 0;
2064	for (int i = 0; i <= end; i++)
2065	if (gaps[i] > max_gap) {
2066	gap_slot = i;
2067	max_gap = gaps[i];
2068	}
2069	}
2070
2071	if (mt == maple_arange_64)
2072	ma_set_meta(node, mt, gap_slot, end - 1);
2073	else if (end <= max_end - 1)
2074	ma_set_meta(node, mt, gap_slot, end - 1);
2075	}
2076
2077	static inline void mtree_range_walk(struct ma_state mas)
2078	{
2079	unsigned long *pivots;
2080	unsigned char offset;
2081	struct maple_node *node;
2082	struct maple_enode next, last;
2083	enum maple_type type;
2084	void __rcu **slots;
2085	unsigned char end;
2086	unsigned long max, min;
2087	unsigned long prev_max, prev_min;
2088
2089	next = mas->node;
2090	min = mas->min;
2091	max = mas->max;
2092	do {
2093	last = next;
2094	node = mte_to_node(next);
2095	type = mte_node_type(next);
2096	pivots = ma_pivots(node, type);
2097	end = ma_data_end(node, type, pivots, max);
2098	prev_min = min;
2099	prev_max = max;
2100	if (pivots[0] >= mas->index) {
2101	offset = 0;
2102	max = pivots[0];
2103	goto next;
2104	}
2105
2106	offset = 1;
2107	while (offset < end) {
2108	if (pivots[offset] >= mas->index) {
2109	max = pivots[offset];
2110	break;
2111	}
2112	offset++;
2113	}
2114
2115	min = pivots[offset - 1] + 1;
2116	next:
2117	slots = ma_slots(node, type);
2118	next = mt_slot(mas->tree, slots, offset);
2119	if (unlikely(ma_dead_node(node)))
2120	goto dead_node;
2121	} while (!ma_is_leaf(type));
2122
2123	mas->end = end;
2124	mas->offset = offset;
2125	mas->index = min;
2126	mas->last = max;
2127	mas->min = prev_min;
2128	mas->max = prev_max;
2129	mas->node = last;
2130	return (void *)next;
2131
2132	dead_node:
2133	mas_reset(mas);
2134	return NULL;
2135	}
2136
2137	/*
2138	* mas_wmb_replace() - Write memory barrier and replace
2139	* @mas: The maple state
2140	* @cp: The maple copy node
2141	*
2142	* Updates gap as necessary.
2143	*/
2144	static inline void mas_wmb_replace(struct ma_state mas, struct maple_copy cp)
2145	{
2146	struct maple_enode *old_enode;
2147
2148	old_enode = mas->node;
2149	mas->node = mt_slot_locked(mas->tree, cp->slot, 0);
2150	/* Insert the new data in the tree */
2151	mas_topiary_replace(mas, old_enode, cp->height);
2152	if (mt_is_alloc(mas->tree) && !mte_is_root(mas->node))
2153	mas_update_gap_known(mas, cp->gap[0]);
2154
2155	mtree_range_walk(mas);
2156	}
2157
2158
2159	/*
2160	* cp_leaf_init() - Initialize a maple_copy node for the leaf level of a
2161	* spanning store
2162	* @cp: The maple copy node
2163	* @mas: The maple state
2164	* @l_wr_mas: The left write state of the spanning store
2165	* @r_wr_mas: The right write state of the spanning store
2166	*/
2167	static inline void cp_leaf_init(struct maple_copy *cp,
2168	struct ma_state mas, struct ma_wr_state l_wr_mas,
2169	struct ma_wr_state *r_wr_mas)
2170	{
2171	unsigned char end = 0;
2172
2173	/*
2174	* WARNING: The use of RCU_INIT_POINTER() makes it extremely important
2175	* to not expose the maple_copy node to any readers. Exposure may
2176	* result in buggy code when a compiler reorders the instructions.
2177	*/
2178
2179	cp->height = 1;
2180	/* Create entries to insert including split entries to left and right */
2181	if (l_wr_mas->r_min < mas->index) {
2182	end++;
2183	RCU_INIT_POINTER(cp->slot[0], l_wr_mas->content);
2184	cp->pivot[0] = mas->index - 1;
2185	}
2186	RCU_INIT_POINTER(cp->slot[end], l_wr_mas->entry);
2187	cp->pivot[end] = mas->last;
2188
2189	if (r_wr_mas->end_piv > mas->last) {
2190	end++;
2191	RCU_INIT_POINTER(cp->slot[end],
2192	r_wr_mas->slots[r_wr_mas->offset_end]);
2193	cp->pivot[end] = r_wr_mas->end_piv;
2194	}
2195
2196	cp->min = l_wr_mas->r_min;
2197	cp->max = cp->pivot[end];
2198	cp->end = end;
2199	}
2200
2201	/*
2202	* cp_data_calc() - Calculate the size of the data (1 indexed).
2203	* @cp: The maple copy struct with the new data populated.
2204	* @l_wr_mas: The maple write state containing the data to the left of the write
2205	* @r_wr_mas: The maple write state containing the data to the right of the
2206	* write
2207	*
2208	* cp->data is a size (not indexed by 0).
2209	*/
2210	static inline void cp_data_calc(struct maple_copy *cp,
2211	struct ma_wr_state l_wr_mas, struct ma_wr_state r_wr_mas)
2212	{
2213
2214	/* Add 1 every time for the 0th element */
2215	cp->data = l_wr_mas->mas->offset;
2216	/* Add the new data and any partial overwrites */
2217	cp->data += cp->end + 1;
2218	/* Data from right (offset + 1 to end), +1 for zero */
2219	cp->data += r_wr_mas->mas->end - r_wr_mas->offset_end;
2220	}
2221
2222	static bool data_fits(struct ma_state sib, struct ma_state mas,
2223	struct maple_copy *cp)
2224	{
2225	unsigned char new_data;
2226	enum maple_type type;
2227	unsigned char space;
2228	unsigned char end;
2229
2230	type = mte_node_type(mas->node);
2231	space = 2 * mt_slots[type];
2232	end = sib->end;
2233
2234	new_data = end + 1 + cp->data;
2235	if (new_data > space)
2236	return false;
2237
2238	/*
2239	* This is off by one by design. The extra space is left to reduce
2240	* jitter in operations that add then remove two entries.
2241	*
2242	* end is an index while new space and data are both sizes. Adding one
2243	* to end to convert the index to a size means that the below
2244	* calculation should be <=, but we want to keep an extra space in nodes
2245	* to reduce jitter.
2246	*
2247	* Note that it is still possible to get a full node on the left by the
2248	* NULL landing exactly on the split. The NULL ending of a node happens
2249	* in the dst_setup() function, where we will either increase the split
2250	* by one or decrease it by one, if possible. In the case of split
2251	* (this case), it is always possible to shift the spilt by one - again
2252	* because there is at least one slot free by the below checking.
2253	*/
2254	if (new_data < space)
2255	return true;
2256
2257	return false;
2258	}
2259
2260	static inline void push_data_sib(struct maple_copy cp, struct ma_state mas,
2261	struct ma_state sib, struct ma_state parent)
2262	{
2263
2264	if (mte_is_root(mas->node))
2265	goto no_push;
2266
2267
2268	sib = parent;
2269	if (sib->offset) {
2270	sib->offset--;
2271	mas_descend(sib);
2272	sib->end = mas_data_end(sib);
2273	if (data_fits(sib, mas, cp)) /* Push left */
2274	return;
2275
2276	sib = parent;
2277	}
2278
2279	if (sib->offset >= sib->end)
2280	goto no_push;
2281
2282	sib->offset++;
2283	mas_descend(sib);
2284	sib->end = mas_data_end(sib);
2285	if (data_fits(sib, mas, cp)) /* Push right*/
2286	return;
2287
2288	no_push:
2289	sib->end = 0;
2290	}
2291
2292	/*
2293	* rebalance_data() - Calculate the @cp data, populate @sib if insufficient or
2294	* if the data can be pushed into a sibling.
2295	* @cp: The maple copy node
2296	* @wr_mas: The left write maple state
2297	* @sib: The maple state of the sibling.
2298	*
2299	* Note: @cp->data is a size and not indexed by 0. @sib->end may be set to 0 to
2300	* indicate it will not be used.
2301	*
2302	*/
2303	static inline void rebalance_data(struct maple_copy *cp,
2304	struct ma_wr_state wr_mas, struct ma_state sib,
2305	struct ma_state *parent)
2306	{
2307	cp_data_calc(cp, wr_mas, wr_mas);
2308	sib->end = 0;
2309	if (cp->data > mt_slots[wr_mas->type]) {
2310	push_data_sib(cp, wr_mas->mas, sib, parent);
2311	if (sib->end)
2312	goto use_sib;
2313	} else if (cp->data <= mt_min_slots[wr_mas->type]) {
2314	if ((wr_mas->mas->min != 0) \|\|
2315	(wr_mas->mas->max != ULONG_MAX)) {
2316	rebalance_sib(parent, sib);
2317	goto use_sib;
2318	}
2319	}
2320
2321	return;
2322
2323	use_sib:
2324
2325	cp->data += sib->end + 1;
2326	}
2327
2328	/*
2329	* spanning_data() - Calculate the @cp data and populate @sib if insufficient
2330	* @cp: The maple copy node
2331	* @l_wr_mas: The left write maple state
2332	* @r_wr_mas: The right write maple state
2333	* @sib: The maple state of the sibling.
2334	*
2335	* Note: @cp->data is a size and not indexed by 0. @sib->end may be set to 0 to
2336	* indicate it will not be used.
2337	*/
2338	static inline void spanning_data(struct maple_copy *cp,
2339	struct ma_wr_state l_wr_mas, struct ma_wr_state r_wr_mas,
2340	struct ma_state *sib)
2341	{
2342	cp_data_calc(cp, l_wr_mas, r_wr_mas);
2343	if (((l_wr_mas->mas->min != 0) \|\| (r_wr_mas->mas->max != ULONG_MAX)) &&
2344	(cp->data <= mt_min_slots[l_wr_mas->type])) {
2345	spanning_sib(l_wr_mas, r_wr_mas, sib);
2346	cp->data += sib->end + 1;
2347	} else {
2348	sib->end = 0;
2349	}
2350	}
2351
2352	/*
2353	* dst_setup() - Set up one or more destinations for the new data.
2354	* @cp: The maple copy node
2355	* @mas: The maple state
2356	* @mt: The source node type
2357	*/
2358	static inline
2359	void dst_setup(struct maple_copy cp, struct ma_state mas, enum maple_type mt)
2360	{
2361	/* Data is 1 indexed, every src has +1 added. */
2362
2363	if (cp->data <= mt_slots[mt]) {
2364	cp->split = cp->data - 1;
2365	cp->d_count = 1;
2366	goto node_setup;
2367	}
2368
2369	cp->split = (cp->data - 1) / 2;
2370	cp->d_count = 2;
2371	if (cp->data < mt_slots[mt] * 2)
2372	goto node_setup;
2373
2374	if (cp->data == mt_slots[mt] * 2) {
2375	unsigned char off;
2376	unsigned char s;
2377
2378	if (!ma_is_leaf(mt))
2379	goto node_setup;
2380
2381	/*
2382	* Leaf nodes are a bit tricky because we cannot assume the data
2383	* can fit due to the NULL limitation on node ends.
2384	*/
2385	off = cp->split;
2386	for (s = 0; s < cp->s_count; s++) {
2387	unsigned char s_off;
2388
2389	s_off = cp->src[s].end - cp->src[s].start;
2390	if (s_off >= off)
2391	break;
2392
2393	s_off++;
2394	off -= s_off;
2395	}
2396
2397	off += cp->src[s].start;
2398	if (ma_slots(cp->src[s].node, cp->src[s].mt)[off])
2399	goto node_setup;
2400
2401	cp->split++;
2402	if (cp->split < mt_slots[mt])
2403	goto node_setup;
2404
2405	cp->split -= 2;
2406	if (cp->data - 2 - cp->split < mt_slots[mt])
2407	goto node_setup;
2408
2409	}
2410
2411	/* No other choice but to 3-way split the data */
2412	cp->split = (cp->data + 2) / 3;
2413	cp->d_count = 3;
2414
2415	node_setup:
2416	for (int i = 0; i < cp->d_count; i++) {
2417	cp->dst[i].mt = mt;
2418	cp->dst[i].node = ma_mnode_ptr(mas_pop_node(mas));
2419	}
2420	}
2421
2422	static inline void append_mas_cp(struct maple_copy *cp,
2423	struct ma_state *mas, unsigned char start, unsigned char end)
2424	{
2425	struct maple_node *node;
2426	enum maple_type mt;
2427	unsigned char count;
2428
2429	count = cp->s_count;
2430	node = mas_mn(mas);
2431	mt = mte_node_type(mas->node);
2432	cp->src[count].node = node;
2433	cp->src[count].mt = mt;
2434	if (mas->end <= end)
2435	cp->src[count].max = mas->max;
2436	else
2437	cp->src[count].max = ma_pivots(node, mt)[end];
2438
2439	cp->src[count].start = start;
2440	cp->src[count].end = end;
2441	cp->s_count++;
2442	}
2443
2444	static inline void append_wr_mas_cp(struct maple_copy *cp,
2445	struct ma_wr_state *wr_mas, unsigned char start, unsigned char end)
2446	{
2447	unsigned char count;
2448
2449	count = cp->s_count;
2450	cp->src[count].node = wr_mas->node;
2451	cp->src[count].mt = wr_mas->type;
2452	if (wr_mas->mas->end <= end)
2453	cp->src[count].max = wr_mas->mas->max;
2454	else
2455	cp->src[count].max = wr_mas->pivots[end];
2456
2457	cp->src[count].start = start;
2458	cp->src[count].end = end;
2459	cp->s_count++;
2460	}
2461
2462	static inline void init_cp_src(struct maple_copy *cp)
2463	{
2464	cp->src[cp->s_count].node = ma_mnode_ptr(cp);
2465	cp->src[cp->s_count].mt = maple_copy;
2466	cp->src[cp->s_count].max = cp->max;
2467	cp->src[cp->s_count].start = 0;
2468	cp->src[cp->s_count].end = cp->end;
2469	cp->s_count++;
2470	}
2471
2472	/*
2473	* multi_src_setup() - Set the @cp node up with multiple sources to copy from.
2474	* @cp: The maple copy node
2475	* @l_wr_mas: The left write maple state
2476	* @r_wr_mas: The right write maple state
2477	* @sib: The sibling maple state
2478	*
2479	* Note: @sib->end == 0 indicates no sibling will be used.
2480	*/
2481	static inline
2482	void multi_src_setup(struct maple_copy cp, struct ma_wr_state l_wr_mas,
2483	struct ma_wr_state r_wr_mas, struct ma_state sib)
2484	{
2485	cp->s_count = 0;
2486	if (sib->end && sib->max < l_wr_mas->mas->min)
2487	append_mas_cp(cp, sib, 0, sib->end);
2488
2489	/* Copy left 0 - offset */
2490	if (l_wr_mas->mas->offset) {
2491	unsigned char off = l_wr_mas->mas->offset - 1;
2492
2493	append_wr_mas_cp(cp, l_wr_mas, 0, off);
2494	cp->src[cp->s_count - 1].max = cp->min - 1;
2495	}
2496
2497	init_cp_src(cp);
2498
2499	/* Copy right either from offset or offset + 1 pending on r_max */
2500	if (r_wr_mas->mas->end != r_wr_mas->offset_end)
2501	append_wr_mas_cp(cp, r_wr_mas, r_wr_mas->offset_end + 1,
2502	r_wr_mas->mas->end);
2503
2504	if (sib->end && sib->min > r_wr_mas->mas->max)
2505	append_mas_cp(cp, sib, 0, sib->end);
2506	}
2507
2508	static inline
2509	void cp_data_write(struct maple_copy cp, struct ma_state mas)
2510	{
2511	struct maple_node dst, src;
2512	unsigned char s, d;
2513	unsigned char dst_offset;
2514	unsigned char data_offset;
2515	unsigned char src_end, s_offset;
2516	unsigned char split;
2517	unsigned long s_max, d_max;
2518	unsigned char dst_size;
2519	enum maple_type s_mt, d_mt;
2520
2521	data_offset = 0;
2522	s = d = 0;
2523	/* Readability help */
2524	src = cp->src[s].node;
2525	dst = cp->dst[d].node;
2526	s_offset = cp->src[s].start;
2527	src_end = cp->src[s].end;
2528	split = cp->split;
2529	s_max = cp->src[s].max;
2530	s_mt = cp->src[s].mt;
2531	d_mt = cp->dst[d].mt;
2532	do {
2533	dst_offset = 0;
2534	d_max = 0;
2535	dst = cp->dst[d].node;
2536	d_mt = cp->dst[d].mt;
2537	dst_size = split + 1;
2538
2539	while (dst_size) {
2540	unsigned char size;
2541
2542	if (src_end - s_offset + 1 < dst_size)
2543	size = src_end - s_offset + 1;
2544	else
2545	size = dst_size;
2546
2547	d_max = node_copy(mas, src, s_offset, size, s_max, s_mt,
2548	dst, dst_offset, d_mt);
2549
2550	dst_offset += size;
2551	s_offset += size;
2552	if (s_offset > src_end) {
2553	/* This source is exhausted */
2554	s++;
2555	if (s >= cp->s_count) {
2556	cp->dst[d].max = d_max;
2557	node_finalise(dst, d_mt, dst_offset);
2558	return;
2559	}
2560	/* Reset local src */
2561	src = cp->src[s].node;
2562	s_offset = cp->src[s].start;
2563	src_end = cp->src[s].end;
2564	s_max = cp->src[s].max;
2565	s_mt = cp->src[s].mt;
2566	}
2567
2568	dst_size -= size;
2569	data_offset += size;
2570	}
2571
2572	split = cp->split;
2573	cp->dst[d].max = d_max;
2574	/* Handle null entries */
2575	if (cp->dst[d].max != ULONG_MAX &&
2576	!ma_slots(dst, d_mt)[dst_offset - 1]) {
2577	if (s_offset == cp->src[s].start) {
2578	s--;
2579	src = cp->src[s].node;
2580	src_end = cp->src[s].end;
2581	s_max = cp->src[s].max;
2582	s_mt = cp->src[s].mt;
2583	s_offset = src_end;
2584	} else {
2585	s_offset--;
2586	}
2587	/* Set dst max and clear pivot */
2588	split++;
2589	data_offset--;
2590	dst_offset--;
2591	cp->dst[d].max = ma_pivots(dst, d_mt)[dst_offset - 1];
2592	}
2593
2594	node_finalise(dst, d_mt, dst_offset);
2595	++d; /* Next destination */
2596	if (d == cp->d_count - 1)
2597	split = cp->data - data_offset;
2598
2599	if (d >= cp->d_count) {
2600	WARN_ON(data_offset < cp->data);
2601	return;
2602	}
2603
2604	} while (data_offset <= cp->data);
2605	}
2606
2607	/*
2608	* cp_dst_to_slots() - Migrate the maple copy destination to the maple copy
2609	* slots
2610	* @cp: The maple copy node
2611	* @min: The minimal value represented
2612	* @max: The maximum value represented
2613	* @mas: The maple state
2614	*/
2615	static inline void cp_dst_to_slots(struct maple_copy *cp, unsigned long min,
2616	unsigned long max, struct ma_state *mas)
2617	{
2618	unsigned char d;
2619	unsigned long slot_min = min;
2620
2621	for (d = 0; d < cp->d_count; d++) {
2622	struct maple_node *mn = cp->dst[d].node;
2623	enum maple_type mt = cp->dst[d].mt;
2624	unsigned long slot_max = cp->dst[d].max;
2625
2626	/*
2627	* Warning, see cp_leaf_init() comment and rcu_assign_pointer()
2628	* documentation. Since these are new nodes, there are no
2629	* read-side operations that can view them until they are
2630	* inserted into the tree after an rcu_assign_pointer() call.
2631	*/
2632	ma_init_slot(&cp->slot[d], mn, mt);
2633	cp->pivot[d] = slot_max;
2634	if (mt_is_alloc(mas->tree)) {
2635	if (ma_is_leaf(mt)) {
2636	cp->gap[d] = ma_leaf_max_gap(mn, mt, slot_min,
2637	slot_max, ma_pivots(mn, mt),
2638	ma_slots(mn, mt));
2639	} else {
2640	unsigned long *gaps = ma_gaps(mn, mt);
2641
2642	if (gaps) {
2643	unsigned char gap_slot;
2644
2645	gap_slot = ma_meta_gap(mn);
2646	cp->gap[d] = gaps[gap_slot];
2647	}
2648	}
2649	}
2650	slot_min = slot_max + 1;
2651	}
2652
2653	cp->end = cp->d_count - 1;
2654	cp->min = min;
2655	cp->max = max;
2656	}
2657
2658	static inline bool cp_is_new_root(struct maple_copy cp, struct ma_state mas)
2659	{
2660	if (cp->min \|\| cp->max != ULONG_MAX)
2661	return false;
2662
2663	if (cp->d_count != 1) {
2664	enum maple_type mt = maple_arange_64;
2665
2666	if (!mt_is_alloc(mas->tree))
2667	mt = maple_range_64;
2668
2669	cp->data = cp->d_count;
2670	cp->s_count = 0;
2671	dst_setup(cp, mas, mt);
2672	init_cp_src(cp);
2673	node_copy(mas, cp->src[0].node, 0, cp->data, cp->max, maple_copy,
2674	cp->dst[0].node, 0, mt);
2675	node_finalise(cp->dst[0].node, mt, cp->end + 1);
2676	/*
2677	* Warning, see cp_leaf_init() comment and rcu_assign_pointer()
2678	* documentation. Since this is a new root, there are no
2679	* read-side operations that can view it until it is insert into
2680	* the tree after an rcu_assign_pointer() call.
2681	*/
2682	ma_init_slot(&cp->slot[0], cp->dst[0].node, mt);
2683	cp->height++;
2684	}
2685	WARN_ON_ONCE(cp->dst[0].node != mte_to_node(
2686	mt_slot_locked(mas->tree, cp->slot, 0)));
2687	cp->dst[0].node->parent = ma_parent_ptr(mas_tree_parent(mas));
2688	mas->min = 0;
2689	mas->max = ULONG_MAX;
2690	mas->depth = 0;
2691	mas->node = mas_root_locked(mas);
2692	return true;
2693	}
2694
2695	static inline bool cp_converged(struct maple_copy cp, struct ma_state mas,
2696	struct ma_state *sib)
2697	{
2698	if (cp->d_count != 1 \|\| sib->end)
2699	return false;
2700
2701	cp->dst[0].node->parent = ma_parent_ptr(mas_mn(mas)->parent);
2702	return true;
2703	}
2704
2705	/*
2706	* spanning_ascend() - See if a spanning store operation has to keep walking up
2707	* the tree
2708	* @cp: The maple_copy node
2709	* @l_wr_mas: The left maple write state
2710	* @r_wr_mas: The right maple write state
2711	* @sib: the maple state of the sibling
2712	*
2713	* Returns: True if another iteration is necessary.
2714	*/
2715	static bool spanning_ascend(struct maple_copy cp, struct ma_state mas,
2716	struct ma_wr_state l_wr_mas, struct ma_wr_state r_wr_mas,
2717	struct ma_state *sib)
2718	{
2719	if (sib->end) {
2720	if (sib->max < l_wr_mas->mas->min)
2721	l_wr_mas->mas = sib;
2722	else
2723	r_wr_mas->mas = sib;
2724	}
2725
2726	cp_dst_to_slots(cp, l_wr_mas->mas->min, r_wr_mas->mas->max, mas);
2727	if (cp_is_new_root(cp, mas))
2728	return false;
2729
2730	/* Converged and has a single destination */
2731	if ((cp->d_count == 1) &&
2732	(l_wr_mas->mas->node == r_wr_mas->mas->node)) {
2733	cp->dst[0].node->parent = ma_parent_ptr(mas_mn(mas)->parent);
2734	return false;
2735	}
2736
2737	cp->height++;
2738	wr_mas_ascend(l_wr_mas);
2739	wr_mas_ascend(r_wr_mas);
2740	return true;
2741	}
2742
2743	static inline
2744	void copy_tree_location(const struct ma_state src, struct ma_state dst)
2745	{
2746	dst->node = src->node;
2747	dst->offset = src->offset;
2748	dst->min = src->min;
2749	dst->max = src->max;
2750	dst->end = src->end;
2751	dst->depth = src->depth;
2752	}
2753
2754	/*
2755	* rebalance_ascend() - Ascend the tree and set up for the next loop - if
2756	* necessary
2757	*
2758	* Return: True if there another rebalancing operation on the next level is
2759	* needed, false otherwise.
2760	*/
2761	static inline bool rebalance_ascend(struct maple_copy *cp,
2762	struct ma_wr_state wr_mas, struct ma_state sib,
2763	struct ma_state *parent)
2764	{
2765	struct ma_state *mas;
2766	unsigned long min, max;
2767
2768	mas = wr_mas->mas;
2769	if (!sib->end) {
2770	min = mas->min;
2771	max = mas->max;
2772	} else if (sib->min > mas->max) { /* Move right succeeded */
2773	min = mas->min;
2774	max = sib->max;
2775	wr_mas->offset_end = parent->offset + 1;
2776	} else {
2777	min = sib->min;
2778	max = mas->max;
2779	wr_mas->offset_end = parent->offset;
2780	parent->offset--;
2781	}
2782
2783	cp_dst_to_slots(cp, min, max, mas);
2784	if (cp_is_new_root(cp, mas))
2785	return false;
2786
2787	if (cp_converged(cp, mas, sib))
2788	return false;
2789
2790	cp->height++;
2791	copy_tree_location(parent, mas);
2792	wr_mas_setup(wr_mas, mas);
2793	return true;
2794	}
2795
2796	/*
2797	* mas_root_expand() - Expand a root to a node
2798	* @mas: The maple state
2799	* @entry: The entry to store into the tree
2800	*/
2801	static inline void mas_root_expand(struct ma_state mas, void entry)
2802	{
2803	void *contents = mas_root_locked(mas);
2804	enum maple_type type = maple_leaf_64;
2805	struct maple_node *node;
2806	void __rcu **slots;
2807	unsigned long *pivots;
2808	int slot = 0;
2809
2810	node = mas_pop_node(mas);
2811	pivots = ma_pivots(node, type);
2812	slots = ma_slots(node, type);
2813	node->parent = ma_parent_ptr(mas_tree_parent(mas));
2814	mas->node = mt_mk_node(node, type);
2815	mas->status = ma_active;
2816
2817	if (mas->index) {
2818	if (contents) {
2819	rcu_assign_pointer(slots[slot], contents);
2820	if (likely(mas->index > 1))
2821	slot++;
2822	}
2823	pivots[slot++] = mas->index - 1;
2824	}
2825
2826	rcu_assign_pointer(slots[slot], entry);
2827	mas->offset = slot;
2828	pivots[slot] = mas->last;
2829	if (mas->last != ULONG_MAX)
2830	pivots[++slot] = ULONG_MAX;
2831
2832	mt_set_height(mas->tree, 1);
2833	ma_set_meta(node, maple_leaf_64, 0, slot);
2834	/* swap the new root into the tree */
2835	rcu_assign_pointer(mas->tree->ma_root, mte_mk_root(mas->node));
2836	}
2837
2838	/*
2839	* mas_store_root() - Storing value into root.
2840	* @mas: The maple state
2841	* @entry: The entry to store.
2842	*
2843	* There is no root node now and we are storing a value into the root - this
2844	* function either assigns the pointer or expands into a node.
2845	*/
2846	static inline void mas_store_root(struct ma_state mas, void entry)
2847	{
2848	if (!entry) {
2849	if (!mas->index)
2850	rcu_assign_pointer(mas->tree->ma_root, NULL);
2851	} else if (likely((mas->last != 0) \|\| (mas->index != 0)))
2852	mas_root_expand(mas, entry);
2853	else if (((unsigned long) (entry) & 3) == 2)
2854	mas_root_expand(mas, entry);
2855	else {
2856	rcu_assign_pointer(mas->tree->ma_root, entry);
2857	mas->status = ma_start;
2858	}
2859	}
2860
2861	/*
2862	* mas_is_span_wr() - Check if the write needs to be treated as a write that
2863	* spans the node.
2864	* @wr_mas: The maple write state
2865	*
2866	* Spanning writes are writes that start in one node and end in another OR if
2867	* the write of a %NULL will cause the node to end with a %NULL.
2868	*
2869	* Return: True if this is a spanning write, false otherwise.
2870	*/
2871	static bool mas_is_span_wr(struct ma_wr_state *wr_mas)
2872	{
2873	unsigned long max = wr_mas->r_max;
2874	unsigned long last = wr_mas->mas->last;
2875	enum maple_type type = wr_mas->type;
2876	void *entry = wr_mas->entry;
2877
2878	/* Contained in this pivot, fast path */
2879	if (last < max)
2880	return false;
2881
2882	if (ma_is_leaf(type)) {
2883	max = wr_mas->mas->max;
2884	if (last < max)
2885	return false;
2886	}
2887
2888	if (last == max) {
2889	/*
2890	* The last entry of leaf node cannot be NULL unless it is the
2891	* rightmost node (writing ULONG_MAX), otherwise it spans slots.
2892	*/
2893	if (entry \|\| last == ULONG_MAX)
2894	return false;
2895	}
2896
2897	trace_ma_write(TP_FCT, wr_mas->mas, wr_mas->r_max, entry);
2898	return true;
2899	}
2900
2901	static inline void mas_wr_walk_descend(struct ma_wr_state *wr_mas)
2902	{
2903	wr_mas->type = mte_node_type(wr_mas->mas->node);
2904	mas_wr_node_walk(wr_mas);
2905	wr_mas->slots = ma_slots(wr_mas->node, wr_mas->type);
2906	}
2907
2908	static inline void mas_wr_walk_traverse(struct ma_wr_state *wr_mas)
2909	{
2910	wr_mas->mas->max = wr_mas->r_max;
2911	wr_mas->mas->min = wr_mas->r_min;
2912	wr_mas->mas->node = wr_mas->content;
2913	wr_mas->mas->offset = 0;
2914	wr_mas->mas->depth++;
2915	}
2916	/*
2917	* mas_wr_walk() - Walk the tree for a write.
2918	* @wr_mas: The maple write state
2919	*
2920	* Uses mas_slot_locked() and does not need to worry about dead nodes.
2921	*
2922	* Return: True if it's contained in a node, false on spanning write.
2923	*/
2924	static bool mas_wr_walk(struct ma_wr_state *wr_mas)
2925	{
2926	struct ma_state *mas = wr_mas->mas;
2927
2928	while (true) {
2929	mas_wr_walk_descend(wr_mas);
2930	if (unlikely(mas_is_span_wr(wr_mas)))
2931	return false;
2932
2933	wr_mas->content = mas_slot_locked(mas, wr_mas->slots,
2934	mas->offset);
2935	if (ma_is_leaf(wr_mas->type))
2936	return true;
2937
2938	if (mas->end < mt_slots[wr_mas->type] - 1)
2939	wr_mas->vacant_height = mas->depth + 1;
2940
2941	if (ma_is_root(mas_mn(mas))) {
2942	/* root needs more than 2 entries to be sufficient + 1 */
2943	if (mas->end > 2)
2944	wr_mas->sufficient_height = 1;
2945	} else if (mas->end > mt_min_slots[wr_mas->type] + 1)
2946	wr_mas->sufficient_height = mas->depth + 1;
2947
2948	mas_wr_walk_traverse(wr_mas);
2949	}
2950
2951	return true;
2952	}
2953
2954	static void mas_wr_walk_index(struct ma_wr_state *wr_mas)
2955	{
2956	struct ma_state *mas = wr_mas->mas;
2957
2958	while (true) {
2959	mas_wr_walk_descend(wr_mas);
2960	wr_mas->content = mas_slot_locked(mas, wr_mas->slots,
2961	mas->offset);
2962	if (ma_is_leaf(wr_mas->type))
2963	return;
2964	mas_wr_walk_traverse(wr_mas);
2965	}
2966	}
2967	/*
2968	* mas_extend_spanning_null() - Extend a store of a %NULL to include surrounding %NULLs.
2969	* @l_wr_mas: The left maple write state
2970	* @r_wr_mas: The right maple write state
2971	*/
2972	static inline void mas_extend_spanning_null(struct ma_wr_state *l_wr_mas,
2973	struct ma_wr_state *r_wr_mas)
2974	{
2975	struct ma_state *r_mas = r_wr_mas->mas;
2976	struct ma_state *l_mas = l_wr_mas->mas;
2977	unsigned char l_slot;
2978
2979	l_slot = l_mas->offset;
2980	if (!l_wr_mas->content)
2981	l_mas->index = l_wr_mas->r_min;
2982
2983	if ((l_mas->index == l_wr_mas->r_min) &&
2984	(l_slot &&
2985	!mas_slot_locked(l_mas, l_wr_mas->slots, l_slot - 1))) {
2986	if (l_slot > 1)
2987	l_mas->index = l_wr_mas->pivots[l_slot - 2] + 1;
2988	else
2989	l_mas->index = l_mas->min;
2990
2991	l_mas->offset = l_slot - 1;
2992	l_wr_mas->r_min = l_mas->index;
2993	}
2994
2995	if (!r_wr_mas->content) {
2996	if (r_mas->last < r_wr_mas->r_max)
2997	r_mas->last = r_wr_mas->r_max;
2998	r_mas->offset++;
2999	}
3000	}
3001
3002	static inline void mas_state_walk(struct ma_state mas)
3003	{
3004	void *entry;
3005
3006	entry = mas_start(mas);
3007	if (mas_is_none(mas))
3008	return NULL;
3009
3010	if (mas_is_ptr(mas))
3011	return entry;
3012
3013	return mtree_range_walk(mas);
3014	}
3015
3016	/*
3017	* mtree_lookup_walk() - Internal quick lookup that does not keep maple state up
3018	* to date.
3019	*
3020	* @mas: The maple state.
3021	*
3022	* Note: Leaves mas in undesirable state.
3023	* Return: The entry for @mas->index or %NULL on dead node.
3024	*/
3025	static inline void mtree_lookup_walk(struct ma_state mas)
3026	{
3027	unsigned long *pivots;
3028	unsigned char offset;
3029	struct maple_node *node;
3030	struct maple_enode *next;
3031	enum maple_type type;
3032	void __rcu **slots;
3033	unsigned char end;
3034
3035	next = mas->node;
3036	do {
3037	node = mte_to_node(next);
3038	type = mte_node_type(next);
3039	pivots = ma_pivots(node, type);
3040	end = mt_pivots[type];
3041	offset = 0;
3042	do {
3043	if (pivots[offset] >= mas->index)
3044	break;
3045	} while (++offset < end);
3046
3047	slots = ma_slots(node, type);
3048	next = mt_slot(mas->tree, slots, offset);
3049	if (unlikely(ma_dead_node(node)))
3050	goto dead_node;
3051	} while (!ma_is_leaf(type));
3052
3053	return (void *)next;
3054
3055	dead_node:
3056	mas_reset(mas);
3057	return NULL;
3058	}
3059
3060	static void mte_destroy_walk(struct maple_enode , struct maple_tree );
3061	/*
3062	* mas_new_root() - Create a new root node that only contains the entry passed
3063	* in.
3064	* @mas: The maple state
3065	* @entry: The entry to store.
3066	*
3067	* Only valid when the index == 0 and the last == ULONG_MAX
3068	*/
3069	static inline void mas_new_root(struct ma_state mas, void entry)
3070	{
3071	struct maple_enode *root = mas_root_locked(mas);
3072	enum maple_type type = maple_leaf_64;
3073	struct maple_node *node;
3074	void __rcu **slots;
3075	unsigned long *pivots;
3076
3077	WARN_ON_ONCE(mas->index \|\| mas->last != ULONG_MAX);
3078
3079	if (!entry) {
3080	mt_set_height(mas->tree, 0);
3081	rcu_assign_pointer(mas->tree->ma_root, entry);
3082	mas->status = ma_start;
3083	goto done;
3084	}
3085
3086	node = mas_pop_node(mas);
3087	pivots = ma_pivots(node, type);
3088	slots = ma_slots(node, type);
3089	node->parent = ma_parent_ptr(mas_tree_parent(mas));
3090	mas->node = mt_mk_node(node, type);
3091	mas->status = ma_active;
3092	rcu_assign_pointer(slots[0], entry);
3093	pivots[0] = mas->last;
3094	mt_set_height(mas->tree, 1);
3095	rcu_assign_pointer(mas->tree->ma_root, mte_mk_root(mas->node));
3096
3097	done:
3098	if (xa_is_node(root))
3099	mte_destroy_walk(root, mas->tree);
3100	}
3101	/*
3102	* mas_wr_spanning_store() - Create a subtree with the store operation completed
3103	* and new nodes where necessary, then place the sub-tree in the actual tree.
3104	* Note that mas is expected to point to the node which caused the store to
3105	* span.
3106	* @wr_mas: The maple write state
3107	*/
3108	static void mas_wr_spanning_store(struct ma_wr_state *wr_mas)
3109	{
3110	struct maple_copy cp;
3111	struct ma_state *mas;
3112	struct ma_state sib;
3113
3114	/* Left and Right side of spanning store */
3115	MA_STATE(r_mas, NULL, 0, 0);
3116	MA_WR_STATE(r_wr_mas, &r_mas, wr_mas->entry);
3117
3118	/*
3119	* A store operation that spans multiple nodes is called a spanning
3120	* store and is handled early in the store call stack by the function
3121	* mas_is_span_wr(). When a spanning store is identified, the maple
3122	* state is duplicated. The first maple state walks the left tree path
3123	* to ``index``, the duplicate walks the right tree path to ``last``.
3124	* The data in the two nodes are combined into a single node, two nodes,
3125	* or possibly three nodes (see the 3-way split above). A ``NULL``
3126	* written to the last entry of a node is considered a spanning store as
3127	* a rebalance is required for the operation to complete and an overflow
3128	* of data may happen.
3129	*/
3130	mas = wr_mas->mas;
3131	trace_ma_op(TP_FCT, mas);
3132
3133	if (unlikely(!mas->index && mas->last == ULONG_MAX))
3134	return mas_new_root(mas, wr_mas->entry);
3135	/*
3136	* Node rebalancing may occur due to this store, so there may be three new
3137	* entries per level plus a new root.
3138	*/
3139
3140	/*
3141	* Set up right side. Need to get to the next offset after the spanning
3142	* store to ensure it's not NULL and to combine both the next node and
3143	* the node with the start together.
3144	*/
3145	r_mas = *mas;
3146	/* Avoid overflow, walk to next slot in the tree. */
3147	if (r_mas.last + 1)
3148	r_mas.last++;
3149
3150	r_mas.index = r_mas.last;
3151	mas_wr_walk_index(&r_wr_mas);
3152	r_mas.last = r_mas.index = mas->last;
3153	r_wr_mas.end_piv = r_wr_mas.r_max;
3154
3155	/* Set up left side. */
3156	mas_wr_walk_index(wr_mas);
3157
3158	if (!wr_mas->entry) {
3159	mas_extend_spanning_null(wr_mas, &r_wr_mas);
3160	mas->last = r_mas.last;
3161	}
3162
3163	/* expanding NULLs may make this cover the entire range */
3164	if (!mas->index && r_mas.last == ULONG_MAX) {
3165	mas_set_range(mas, 0, ULONG_MAX);
3166	return mas_new_root(mas, wr_mas->entry);
3167	}
3168
3169	cp_leaf_init(&cp, mas, wr_mas, &r_wr_mas);
3170	do {
3171	spanning_data(&cp, wr_mas, &r_wr_mas, &sib);
3172	multi_src_setup(&cp, wr_mas, &r_wr_mas, &sib);
3173	dst_setup(&cp, mas, wr_mas->type);
3174	cp_data_write(&cp, mas);
3175	} while (spanning_ascend(&cp, mas, wr_mas, &r_wr_mas, &sib));
3176
3177	mas_wmb_replace(mas, &cp);
3178	}
3179
3180	/*
3181	* mas_wr_node_store() - Attempt to store the value in a node
3182	* @wr_mas: The maple write state
3183	*
3184	* Attempts to reuse the node, but may allocate.
3185	*/
3186	static inline void mas_wr_node_store(struct ma_wr_state *wr_mas)
3187	{
3188	unsigned char dst_offset, offset_end;
3189	unsigned char copy_size, node_pivots, node_slots;
3190	struct maple_node reuse, *newnode;
3191	unsigned long *dst_pivots;
3192	void __rcu **dst_slots;
3193	unsigned char new_end;
3194	struct ma_state *mas;
3195	bool in_rcu;
3196
3197	mas = wr_mas->mas;
3198	trace_ma_op(TP_FCT, mas);
3199	in_rcu = mt_in_rcu(mas->tree);
3200	offset_end = wr_mas->offset_end;
3201	node_pivots = mt_pivots[wr_mas->type];
3202	node_slots = mt_slots[wr_mas->type];
3203	/* Assume last adds an entry */
3204	new_end = mas->end + 1 - offset_end + mas->offset;
3205	if (mas->last == wr_mas->end_piv) {
3206	offset_end++; /* don't copy this offset */
3207	new_end--;
3208	}
3209
3210	/* set up node. */
3211	if (in_rcu) {
3212	newnode = mas_pop_node(mas);
3213	} else {
3214	newnode = &reuse;
3215	}
3216
3217	newnode->parent = mas_mn(mas)->parent;
3218	dst_pivots = ma_pivots(newnode, wr_mas->type);
3219	dst_slots = ma_slots(newnode, wr_mas->type);
3220	/* Copy from start to insert point */
3221	if (mas->offset) {
3222	memcpy(dst_pivots, wr_mas->pivots, sizeof(unsigned long) * mas->offset);
3223	memcpy(dst_slots, wr_mas->slots, sizeof(void __rcu ) mas->offset);
3224	}
3225
3226	/* Handle insert of new range starting after old range */
3227	if (wr_mas->r_min < mas->index) {
3228	rcu_assign_pointer(dst_slots[mas->offset], wr_mas->content);
3229	dst_pivots[mas->offset++] = mas->index - 1;
3230	new_end++;
3231	}
3232
3233	/* Store the new entry and range end. */
3234	if (mas->offset < node_pivots)
3235	dst_pivots[mas->offset] = mas->last;
3236	rcu_assign_pointer(dst_slots[mas->offset], wr_mas->entry);
3237
3238	/*
3239	* this range wrote to the end of the node or it overwrote the rest of
3240	* the data
3241	*/
3242	if (offset_end > mas->end)
3243	goto done;
3244
3245	dst_offset = mas->offset + 1;
3246	/* Copy to the end of node if necessary. */
3247	copy_size = mas->end - offset_end + 1;
3248	memcpy(dst_slots + dst_offset, wr_mas->slots + offset_end,
3249	sizeof(void __rcu ) copy_size);
3250	memcpy(dst_pivots + dst_offset, wr_mas->pivots + offset_end,
3251	sizeof(unsigned long) * (copy_size - 1));
3252
3253	if (new_end < node_pivots)
3254	dst_pivots[new_end] = mas->max;
3255
3256	done:
3257	if (!in_rcu && new_end + 2 < node_slots) {
3258	unsigned char clear_from = new_end + 1;
3259
3260	/*
3261	* Note that the last slot is never cleared, since the metadata
3262	* will be stored there or it has a value.
3263	*/
3264	memset(dst_slots + clear_from, 0,
3265	sizeof(void __rcu ) (node_slots - clear_from));
3266	if (clear_from < node_pivots)
3267	memset(dst_pivots + clear_from, 0,
3268	sizeof(unsigned long) * (node_pivots - clear_from));
3269	}
3270
3271	mas_leaf_set_meta(newnode, wr_mas->type, new_end);
3272	if (in_rcu) {
3273	struct maple_enode *old_enode = mas->node;
3274
3275	mas->node = mt_mk_node(newnode, wr_mas->type);
3276	mas_replace_node(mas, old_enode, mas_mt_height(mas));
3277	} else {
3278	memcpy(wr_mas->node, newnode, sizeof(struct maple_node));
3279	}
3280	trace_ma_write(TP_FCT, mas, 0, wr_mas->entry);
3281	mas_update_gap(mas);
3282	mas->end = new_end;
3283	}
3284
3285	/*
3286	* mas_wr_slot_store: Attempt to store a value in a slot.
3287	* @wr_mas: the maple write state
3288	*/
3289	static inline void mas_wr_slot_store(struct ma_wr_state *wr_mas)
3290	{
3291	struct ma_state *mas = wr_mas->mas;
3292	unsigned char offset = mas->offset;
3293	void __rcu **slots = wr_mas->slots;
3294	bool gap = false;
3295
3296	gap \|= !wr_mas->content;
3297	gap \|= !mt_slot_locked(mas->tree, slots, offset + 1);
3298
3299	if (wr_mas->offset_end - offset == 1) {
3300	if (mas->index == wr_mas->r_min) {
3301	/* Overwriting the range and a part of the next one */
3302	rcu_assign_pointer(slots[offset], wr_mas->entry);
3303	wr_mas->pivots[offset] = mas->last;
3304	} else {
3305	/* Overwriting a part of the range and the next one */
3306	rcu_assign_pointer(slots[offset + 1], wr_mas->entry);
3307	wr_mas->pivots[offset] = mas->index - 1;
3308	mas->offset++; /* Keep mas accurate. */
3309	}
3310	} else {
3311	WARN_ON_ONCE(mt_in_rcu(mas->tree));
3312	/*
3313	* Expand the range, only partially overwriting the previous and
3314	* next ranges
3315	*/
3316	gap \|= !mt_slot_locked(mas->tree, slots, offset + 2);
3317	rcu_assign_pointer(slots[offset + 1], wr_mas->entry);
3318	wr_mas->pivots[offset] = mas->index - 1;
3319	wr_mas->pivots[offset + 1] = mas->last;
3320	mas->offset++; /* Keep mas accurate. */
3321	}
3322
3323	trace_ma_write(TP_FCT, mas, 0, wr_mas->entry);
3324	/*
3325	* Only update gap when the new entry is empty or there is an empty
3326	* entry in the original two ranges.
3327	*/
3328	if (!wr_mas->entry \|\| gap)
3329	mas_update_gap(mas);
3330	}
3331
3332	static inline void mas_wr_extend_null(struct ma_wr_state *wr_mas)
3333	{
3334	struct ma_state *mas = wr_mas->mas;
3335
3336	if (!wr_mas->slots[wr_mas->offset_end]) {
3337	/* If this one is null, the next and prev are not */
3338	mas->last = wr_mas->end_piv;
3339	} else {
3340	/* Check next slot(s) if we are overwriting the end */
3341	if ((mas->last == wr_mas->end_piv) &&
3342	(mas->end != wr_mas->offset_end) &&
3343	!wr_mas->slots[wr_mas->offset_end + 1]) {
3344	wr_mas->offset_end++;
3345	if (wr_mas->offset_end == mas->end)
3346	mas->last = mas->max;
3347	else
3348	mas->last = wr_mas->pivots[wr_mas->offset_end];
3349	wr_mas->end_piv = mas->last;
3350	}
3351	}
3352
3353	if (!wr_mas->content) {
3354	/* If this one is null, the next and prev are not */
3355	mas->index = wr_mas->r_min;
3356	} else {
3357	/* Check prev slot if we are overwriting the start */
3358	if (mas->index == wr_mas->r_min && mas->offset &&
3359	!wr_mas->slots[mas->offset - 1]) {
3360	mas->offset--;
3361	wr_mas->r_min = mas->index =
3362	mas_safe_min(mas, wr_mas->pivots, mas->offset);
3363	wr_mas->r_max = wr_mas->pivots[mas->offset];
3364	}
3365	}
3366	}
3367
3368	static inline void mas_wr_end_piv(struct ma_wr_state *wr_mas)
3369	{
3370	while ((wr_mas->offset_end < wr_mas->mas->end) &&
3371	(wr_mas->mas->last > wr_mas->pivots[wr_mas->offset_end]))
3372	wr_mas->offset_end++;
3373
3374	if (wr_mas->offset_end < wr_mas->mas->end)
3375	wr_mas->end_piv = wr_mas->pivots[wr_mas->offset_end];
3376	else
3377	wr_mas->end_piv = wr_mas->mas->max;
3378	}
3379
3380	static inline unsigned char mas_wr_new_end(struct ma_wr_state *wr_mas)
3381	{
3382	struct ma_state *mas = wr_mas->mas;
3383	unsigned char new_end = mas->end + 2;
3384
3385	new_end -= wr_mas->offset_end - mas->offset;
3386	if (wr_mas->r_min == mas->index)
3387	new_end--;
3388
3389	if (wr_mas->end_piv == mas->last)
3390	new_end--;
3391
3392	return new_end;
3393	}
3394
3395	/*
3396	* mas_wr_append: Attempt to append
3397	* @wr_mas: the maple write state
3398	*
3399	* This is currently unsafe in rcu mode since the end of the node may be cached
3400	* by readers while the node contents may be updated which could result in
3401	* inaccurate information.
3402	*/
3403	static inline void mas_wr_append(struct ma_wr_state *wr_mas)
3404	{
3405	struct ma_state *mas = wr_mas->mas;
3406	void __rcu **slots;
3407	unsigned char end = mas->end;
3408	unsigned char new_end = mas_wr_new_end(wr_mas);
3409
3410	if (new_end < mt_pivots[wr_mas->type]) {
3411	wr_mas->pivots[new_end] = wr_mas->pivots[end];
3412	ma_set_meta(wr_mas->node, wr_mas->type, 0, new_end);
3413	}
3414
3415	slots = wr_mas->slots;
3416	if (new_end == end + 1) {
3417	if (mas->last == wr_mas->r_max) {
3418	/* Append to end of range */
3419	rcu_assign_pointer(slots[new_end], wr_mas->entry);
3420	wr_mas->pivots[end] = mas->index - 1;
3421	mas->offset = new_end;
3422	} else {
3423	/* Append to start of range */
3424	rcu_assign_pointer(slots[new_end], wr_mas->content);
3425	wr_mas->pivots[end] = mas->last;
3426	rcu_assign_pointer(slots[end], wr_mas->entry);
3427	}
3428	} else {
3429	/* Append to the range without touching any boundaries. */
3430	rcu_assign_pointer(slots[new_end], wr_mas->content);
3431	wr_mas->pivots[end + 1] = mas->last;
3432	rcu_assign_pointer(slots[end + 1], wr_mas->entry);
3433	wr_mas->pivots[end] = mas->index - 1;
3434	mas->offset = end + 1;
3435	}
3436
3437	if (!wr_mas->content \|\| !wr_mas->entry)
3438	mas_update_gap(mas);
3439
3440	mas->end = new_end;
3441	trace_ma_write(TP_FCT, mas, new_end, wr_mas->entry);
3442	}
3443
3444	/*
3445	* split_ascend() - See if a split operation has to keep walking up the tree
3446	* @cp: The maple_copy node
3447	* @wr_mas: The maple write state
3448	* @sib: the maple state of the sibling
3449	*
3450	* Return: true if another split operation on the next level is needed, false
3451	* otherwise
3452	*/
3453	static inline bool split_ascend(struct maple_copy *cp,
3454	struct ma_wr_state wr_mas, struct ma_state sib,
3455	struct ma_state *parent)
3456	{
3457	struct ma_state *mas;
3458	unsigned long min, max;
3459
3460	mas = wr_mas->mas;
3461	min = mas->min; /* push right, or normal split */
3462	max = mas->max;
3463	wr_mas->offset_end = parent->offset;
3464	if (sib->end) {
3465	if (sib->max < mas->min) {
3466	min = sib->min; /* push left */
3467	parent->offset--;
3468	} else {
3469	max = sib->max; /* push right */
3470	wr_mas->offset_end++;
3471	}
3472	}
3473
3474	cp_dst_to_slots(cp, min, max, mas);
3475	if (cp_is_new_root(cp, mas))
3476	return false;
3477
3478	if (cp_converged(cp, mas, sib))
3479	return false;
3480
3481	cp->height++;
3482	copy_tree_location(parent, mas);
3483	wr_mas_setup(wr_mas, mas);
3484	return true;
3485	}
3486
3487	/*
3488	* split_data() - Calculate the @cp data, populate @sib if the data can be
3489	* pushed into a sibling.
3490	* @cp: The maple copy node
3491	* @wr_mas: The left write maple state
3492	* @sib: The maple state of the sibling.
3493	*
3494	* Note: @cp->data is a size and not indexed by 0. @sib->end may be set to 0 to
3495	* indicate it will not be used.
3496	*
3497	*/
3498	static inline void split_data(struct maple_copy *cp,
3499	struct ma_wr_state wr_mas, struct ma_state sib,
3500	struct ma_state *parent)
3501	{
3502	cp_data_calc(cp, wr_mas, wr_mas);
3503	if (cp->data <= mt_slots[wr_mas->type]) {
3504	sib->end = 0;
3505	return;
3506	}
3507
3508	push_data_sib(cp, wr_mas->mas, sib, parent);
3509	if (sib->end)
3510	cp->data += sib->end + 1;
3511	}
3512
3513	/*
3514	* mas_wr_split() - Expand one node into two
3515	* @wr_mas: The write maple state
3516	*/
3517	static void mas_wr_split(struct ma_wr_state *wr_mas)
3518	{
3519	struct ma_state parent;
3520	struct ma_state *mas;
3521	struct maple_copy cp;
3522	struct ma_state sib;
3523
3524	mas = wr_mas->mas;
3525	trace_ma_write(TP_FCT, wr_mas->mas, 0, wr_mas->entry);
3526	parent = *mas;
3527	cp_leaf_init(&cp, mas, wr_mas, wr_mas);
3528	do {
3529	if (!mte_is_root(parent.node)) {
3530	mas_ascend(&parent);
3531	parent.end = mas_data_end(&parent);
3532	}
3533	split_data(&cp, wr_mas, &sib, &parent);
3534	multi_src_setup(&cp, wr_mas, wr_mas, &sib);
3535	dst_setup(&cp, mas, wr_mas->type);
3536	cp_data_write(&cp, mas);
3537	} while (split_ascend(&cp, wr_mas, &sib, &parent));
3538
3539	mas_wmb_replace(mas, &cp);
3540	}
3541
3542	/*
3543	* mas_wr_rebalance() - Insufficient data in one node needs to either get data
3544	* from a sibling or absorb a sibling all together.
3545	* @wr_mas: The write maple state
3546	*
3547	* Rebalance is different than a spanning store in that the write state is
3548	* already at the leaf node that's being altered.
3549	*/
3550	static void mas_wr_rebalance(struct ma_wr_state *wr_mas)
3551	{
3552	struct ma_state parent;
3553	struct ma_state *mas;
3554	struct maple_copy cp;
3555	struct ma_state sib;
3556
3557	/*
3558	* Rebalancing occurs if a node is insufficient. Data is rebalanced
3559	* against the node to the right if it exists, otherwise the node to the
3560	* left of this node is rebalanced against this node. If rebalancing
3561	* causes just one node to be produced instead of two, then the parent
3562	* is also examined and rebalanced if it is insufficient. Every level
3563	* tries to combine the data in the same way. If one node contains the
3564	* entire range of the tree, then that node is used as a new root node.
3565	*/
3566
3567	mas = wr_mas->mas;
3568	trace_ma_op(TP_FCT, mas);
3569	parent = *mas;
3570	cp_leaf_init(&cp, mas, wr_mas, wr_mas);
3571	do {
3572	if (!mte_is_root(parent.node)) {
3573	mas_ascend(&parent);
3574	parent.end = mas_data_end(&parent);
3575	}
3576	rebalance_data(&cp, wr_mas, &sib, &parent);
3577	multi_src_setup(&cp, wr_mas, wr_mas, &sib);
3578	dst_setup(&cp, mas, wr_mas->type);
3579	cp_data_write(&cp, mas);
3580	} while (rebalance_ascend(&cp, wr_mas, &sib, &parent));
3581
3582	mas_wmb_replace(mas, &cp);
3583	}
3584
3585	/*
3586	* mas_wr_store_entry() - Internal call to store a value
3587	* @wr_mas: The maple write state
3588	*/
3589	static inline void mas_wr_store_entry(struct ma_wr_state *wr_mas)
3590	{
3591	struct ma_state *mas = wr_mas->mas;
3592
3593	switch (mas->store_type) {
3594	case wr_exact_fit:
3595	rcu_assign_pointer(wr_mas->slots[mas->offset], wr_mas->entry);
3596	if (!!wr_mas->entry ^ !!wr_mas->content)
3597	mas_update_gap(mas);
3598	break;
3599	case wr_append:
3600	mas_wr_append(wr_mas);
3601	break;
3602	case wr_slot_store:
3603	mas_wr_slot_store(wr_mas);
3604	break;
3605	case wr_node_store:
3606	mas_wr_node_store(wr_mas);
3607	break;
3608	case wr_spanning_store:
3609	mas_wr_spanning_store(wr_mas);
3610	break;
3611	case wr_split_store:
3612	mas_wr_split(wr_mas);
3613	break;
3614	case wr_rebalance:
3615	mas_wr_rebalance(wr_mas);
3616	break;
3617	case wr_new_root:
3618	mas_new_root(mas, wr_mas->entry);
3619	break;
3620	case wr_store_root:
3621	mas_store_root(mas, wr_mas->entry);
3622	break;
3623	case wr_invalid:
3624	MT_BUG_ON(mas->tree, 1);
3625	}
3626	}
3627
3628	static inline void mas_wr_prealloc_setup(struct ma_wr_state *wr_mas)
3629	{
3630	struct ma_state *mas = wr_mas->mas;
3631
3632	if (!mas_is_active(mas)) {
3633	if (mas_is_start(mas))
3634	goto set_content;
3635
3636	if (unlikely(mas_is_paused(mas)))
3637	goto reset;
3638
3639	if (unlikely(mas_is_none(mas)))
3640	goto reset;
3641
3642	if (unlikely(mas_is_overflow(mas)))
3643	goto reset;
3644
3645	if (unlikely(mas_is_underflow(mas)))
3646	goto reset;
3647	}
3648
3649	/*
3650	* A less strict version of mas_is_span_wr() where we allow spanning
3651	* writes within this node. This is to stop partial walks in
3652	* mas_prealloc() from being reset.
3653	*/
3654	if (mas->last > mas->max)
3655	goto reset;
3656
3657	if (wr_mas->entry)
3658	goto set_content;
3659
3660	if (mte_is_leaf(mas->node) && mas->last == mas->max)
3661	goto reset;
3662
3663	goto set_content;
3664
3665	reset:
3666	mas_reset(mas);
3667	set_content:
3668	wr_mas->content = mas_start(mas);
3669	}
3670
3671	/**
3672	* mas_prealloc_calc() - Calculate number of nodes needed for a
3673	* given store operation
3674	* @wr_mas: The maple write state
3675	* @entry: The entry to store into the tree
3676	*
3677	* Return: Number of nodes required for preallocation.
3678	*/
3679	static inline void mas_prealloc_calc(struct ma_wr_state wr_mas, void entry)
3680	{
3681	struct ma_state *mas = wr_mas->mas;
3682	unsigned char height = mas_mt_height(mas);
3683	int ret = height * 3 + 1;
3684	unsigned char delta = height - wr_mas->vacant_height;
3685
3686	switch (mas->store_type) {
3687	case wr_exact_fit:
3688	case wr_append:
3689	case wr_slot_store:
3690	ret = 0;
3691	break;
3692	case wr_spanning_store:
3693	if (wr_mas->sufficient_height < wr_mas->vacant_height)
3694	ret = (height - wr_mas->sufficient_height) * 3 + 1;
3695	else
3696	ret = delta * 3 + 1;
3697	break;
3698	case wr_split_store:
3699	ret = delta * 2 + 1;
3700	break;
3701	case wr_rebalance:
3702	if (wr_mas->sufficient_height < wr_mas->vacant_height)
3703	ret = (height - wr_mas->sufficient_height) * 2 + 1;
3704	else
3705	ret = delta * 2 + 1;
3706	break;
3707	case wr_node_store:
3708	ret = mt_in_rcu(mas->tree) ? 1 : 0;
3709	break;
3710	case wr_new_root:
3711	ret = 1;
3712	break;
3713	case wr_store_root:
3714	if (likely((mas->last != 0) \|\| (mas->index != 0)))
3715	ret = 1;
3716	else if (((unsigned long) (entry) & 3) == 2)
3717	ret = 1;
3718	else
3719	ret = 0;
3720	break;
3721	case wr_invalid:
3722	WARN_ON_ONCE(1);
3723	}
3724
3725	mas->node_request = ret;
3726	}
3727
3728	/*
3729	* mas_wr_store_type() - Determine the store type for a given
3730	* store operation.
3731	* @wr_mas: The maple write state
3732	*
3733	* Return: the type of store needed for the operation
3734	*/
3735	static inline enum store_type mas_wr_store_type(struct ma_wr_state *wr_mas)
3736	{
3737	struct ma_state *mas = wr_mas->mas;
3738	unsigned char new_end;
3739	bool appending;
3740	bool one_slot;
3741	bool in_rcu;
3742
3743	if (unlikely(mas_is_none(mas) \|\| mas_is_ptr(mas)))
3744	return wr_store_root;
3745
3746	if (unlikely(!mas_wr_walk(wr_mas)))
3747	return wr_spanning_store;
3748
3749	/* At this point, we are at the leaf node that needs to be altered. */
3750	mas_wr_end_piv(wr_mas);
3751	if (!wr_mas->entry)
3752	mas_wr_extend_null(wr_mas);
3753
3754	if ((wr_mas->r_min == mas->index) && (wr_mas->r_max == mas->last))
3755	return wr_exact_fit;
3756
3757	if (unlikely(!mas->index && mas->last == ULONG_MAX))
3758	return wr_new_root;
3759
3760	new_end = mas_wr_new_end(wr_mas);
3761	in_rcu = mt_in_rcu(mas->tree);
3762	appending = mas->offset == mas->end;
3763	one_slot = wr_mas->offset_end - mas->offset == 1;
3764
3765	/* Potential spanning rebalance collapsing a node */
3766	if (new_end < mt_min_slots[wr_mas->type]) {
3767	if (!mte_is_root(mas->node))
3768	return wr_rebalance;
3769	if (!in_rcu) {
3770	if (appending)
3771	return wr_append;
3772	else if (mas->end == new_end && one_slot)
3773	return wr_slot_store;
3774	}
3775	return wr_node_store;
3776	}
3777
3778	if (new_end >= mt_slots[wr_mas->type])
3779	return wr_split_store;
3780
3781	if (!in_rcu && appending)
3782	return wr_append;
3783
3784	if (new_end == mas->end && (!in_rcu \|\| one_slot))
3785	return wr_slot_store;
3786
3787	return wr_node_store;
3788	}
3789
3790	/**
3791	* mas_wr_preallocate() - Preallocate enough nodes for a store operation
3792	* @wr_mas: The maple write state
3793	* @entry: The entry that will be stored
3794	*
3795	*/
3796	static inline void mas_wr_preallocate(struct ma_wr_state wr_mas, void entry)
3797	{
3798	struct ma_state *mas = wr_mas->mas;
3799
3800	mas_wr_prealloc_setup(wr_mas);
3801	mas->store_type = mas_wr_store_type(wr_mas);
3802	mas_prealloc_calc(wr_mas, entry);
3803	if (!mas->node_request)
3804	return;
3805
3806	mas_alloc_nodes(mas, GFP_NOWAIT);
3807	}
3808
3809	/**
3810	* mas_insert() - Internal call to insert a value
3811	* @mas: The maple state
3812	* @entry: The entry to store
3813	*
3814	* Return: %NULL or the contents that already exists at the requested index
3815	* otherwise. The maple state needs to be checked for error conditions.
3816	*/
3817	static inline void mas_insert(struct ma_state mas, void *entry)
3818	{
3819	MA_WR_STATE(wr_mas, mas, entry);
3820
3821	/*
3822	* Inserting a new range inserts either 0, 1, or 2 pivots within the
3823	* tree. If the insert fits exactly into an existing gap with a value
3824	* of NULL, then the slot only needs to be written with the new value.
3825	* If the range being inserted is adjacent to another range, then only a
3826	* single pivot needs to be inserted (as well as writing the entry). If
3827	* the new range is within a gap but does not touch any other ranges,
3828	* then two pivots need to be inserted: the start - 1, and the end. As
3829	* usual, the entry must be written. Most operations require a new node
3830	* to be allocated and replace an existing node to ensure RCU safety,
3831	* when in RCU mode. The exception to requiring a newly allocated node
3832	* is when inserting at the end of a node (appending). When done
3833	* carefully, appending can reuse the node in place.
3834	*/
3835	wr_mas.content = mas_start(mas);
3836	if (wr_mas.content)
3837	goto exists;
3838
3839	mas_wr_preallocate(&wr_mas, entry);
3840	if (mas_is_err(mas))
3841	return NULL;
3842
3843	/* spanning writes always overwrite something */
3844	if (mas->store_type == wr_spanning_store)
3845	goto exists;
3846
3847	/* At this point, we are at the leaf node that needs to be altered. */
3848	if (mas->store_type != wr_new_root && mas->store_type != wr_store_root) {
3849	wr_mas.offset_end = mas->offset;
3850	wr_mas.end_piv = wr_mas.r_max;
3851
3852	if (wr_mas.content \|\| (mas->last > wr_mas.r_max))
3853	goto exists;
3854	}
3855
3856	mas_wr_store_entry(&wr_mas);
3857	return wr_mas.content;
3858
3859	exists:
3860	mas_set_err(mas, -EEXIST);
3861	return wr_mas.content;
3862
3863	}
3864
3865	/**
3866	* mas_alloc_cyclic() - Internal call to find somewhere to store an entry
3867	* @mas: The maple state.
3868	* @startp: Pointer to ID.
3869	* @range_lo: Lower bound of range to search.
3870	* @range_hi: Upper bound of range to search.
3871	* @entry: The entry to store.
3872	* @next: Pointer to next ID to allocate.
3873	* @gfp: The GFP_FLAGS to use for allocations.
3874	*
3875	* Return: 0 if the allocation succeeded without wrapping, 1 if the
3876	* allocation succeeded after wrapping, or -EBUSY if there are no
3877	* free entries.
3878	*/
3879	int mas_alloc_cyclic(struct ma_state mas, unsigned long startp,
3880	void *entry, unsigned long range_lo, unsigned long range_hi,
3881	unsigned long *next, gfp_t gfp)
3882	{
3883	int ret;
3884	unsigned long min;
3885
3886	min = range_lo;
3887	do {
3888	range_lo = max(min, *next);
3889	ret = mas_empty_area(mas, range_lo, range_hi, 1);
3890	if (ret < 0 && range_lo > min) {
3891	mas_reset(mas);
3892	ret = mas_empty_area(mas, min, range_hi, 1);
3893	if (ret == 0)
3894	ret = 1;
3895	}
3896	if (ret < 0)
3897	goto out;
3898
3899	mas_insert(mas, entry);
3900	} while (mas_nomem(mas, gfp));
3901
3902	if (mas_is_err(mas)) {
3903	ret = xa_err(mas->node);
3904	goto out;
3905	}
3906
3907	if ((mas->tree->ma_flags & MT_FLAGS_ALLOC_WRAPPED) && ret == 0) {
3908	mas->tree->ma_flags &= ~MT_FLAGS_ALLOC_WRAPPED;
3909	ret = 1;
3910	}
3911	*startp = mas->index;
3912	next = startp + 1;
3913	if (*next == 0)
3914	mas->tree->ma_flags \|= MT_FLAGS_ALLOC_WRAPPED;
3915
3916	out:
3917	mas_destroy(mas);
3918	return ret;
3919	}
3920	EXPORT_SYMBOL(mas_alloc_cyclic);
3921
3922	static __always_inline void mas_rewalk(struct ma_state *mas, unsigned long index)
3923	{
3924	retry:
3925	mas_set(mas, index);
3926	mas_state_walk(mas);
3927	if (mas_is_start(mas))
3928	goto retry;
3929	}
3930
3931	static __always_inline bool mas_rewalk_if_dead(struct ma_state *mas,
3932	struct maple_node *node, const unsigned long index)
3933	{
3934	if (unlikely(ma_dead_node(node))) {
3935	mas_rewalk(mas, index);
3936	return true;
3937	}
3938	return false;
3939	}
3940
3941	/*
3942	* mas_prev_node() - Find the prev non-null entry at the same level in the
3943	* tree. The prev value will be mas->node[mas->offset] or the status will be
3944	* ma_none.
3945	* @mas: The maple state
3946	* @min: The lower limit to search
3947	*
3948	* The prev node value will be mas->node[mas->offset] or the status will be
3949	* ma_none.
3950	* Return: 1 if the node is dead, 0 otherwise.
3951	*/
3952	static int mas_prev_node(struct ma_state *mas, unsigned long min)
3953	{
3954	enum maple_type mt;
3955	int offset, level;
3956	void __rcu **slots;
3957	struct maple_node *node;
3958	unsigned long *pivots;
3959	unsigned long max;
3960
3961	node = mas_mn(mas);
3962	if (!mas->min)
3963	goto no_entry;
3964
3965	max = mas->min - 1;
3966	if (max < min)
3967	goto no_entry;
3968
3969	level = 0;
3970	do {
3971	if (ma_is_root(node))
3972	goto no_entry;
3973
3974	/* Walk up. */
3975	if (unlikely(mas_ascend(mas)))
3976	return 1;
3977	offset = mas->offset;
3978	level++;
3979	node = mas_mn(mas);
3980	} while (!offset);
3981
3982	offset--;
3983	mt = mte_node_type(mas->node);
3984	while (level > 1) {
3985	level--;
3986	slots = ma_slots(node, mt);
3987	mas->node = mas_slot(mas, slots, offset);
3988	if (unlikely(ma_dead_node(node)))
3989	return 1;
3990
3991	mt = mte_node_type(mas->node);
3992	node = mas_mn(mas);
3993	pivots = ma_pivots(node, mt);
3994	offset = ma_data_end(node, mt, pivots, max);
3995	if (unlikely(ma_dead_node(node)))
3996	return 1;
3997	}
3998
3999	slots = ma_slots(node, mt);
4000	mas->node = mas_slot(mas, slots, offset);
4001	pivots = ma_pivots(node, mt);
4002	if (unlikely(ma_dead_node(node)))
4003	return 1;
4004
4005	if (likely(offset))
4006	mas->min = pivots[offset - 1] + 1;
4007	mas->max = max;
4008	mas->offset = mas_data_end(mas);
4009	if (unlikely(mte_dead_node(mas->node)))
4010	return 1;
4011
4012	mas->end = mas->offset;
4013	return 0;
4014
4015	no_entry:
4016	if (unlikely(ma_dead_node(node)))
4017	return 1;
4018
4019	mas->status = ma_underflow;
4020	return 0;
4021	}
4022
4023	/*
4024	* mas_prev_slot() - Get the entry in the previous slot
4025	*
4026	* @mas: The maple state
4027	* @min: The minimum starting range
4028	* @empty: Can be empty
4029	*
4030	* Return: The entry in the previous slot which is possibly NULL
4031	*/
4032	static void mas_prev_slot(struct ma_state mas, unsigned long min, bool empty)
4033	{
4034	void *entry;
4035	void __rcu **slots;
4036	unsigned long pivot;
4037	enum maple_type type;
4038	unsigned long *pivots;
4039	struct maple_node *node;
4040	unsigned long save_point = mas->index;
4041
4042	retry:
4043	node = mas_mn(mas);
4044	type = mte_node_type(mas->node);
4045	pivots = ma_pivots(node, type);
4046	if (unlikely(mas_rewalk_if_dead(mas, node, save_point)))
4047	goto retry;
4048
4049	if (mas->min <= min) {
4050	pivot = mas_safe_min(mas, pivots, mas->offset);
4051
4052	if (unlikely(mas_rewalk_if_dead(mas, node, save_point)))
4053	goto retry;
4054
4055	if (pivot <= min)
4056	goto underflow;
4057	}
4058
4059	again:
4060	if (likely(mas->offset)) {
4061	mas->offset--;
4062	mas->last = mas->index - 1;
4063	mas->index = mas_safe_min(mas, pivots, mas->offset);
4064	} else {
4065	if (mas->index <= min)
4066	goto underflow;
4067
4068	if (mas_prev_node(mas, min)) {
4069	mas_rewalk(mas, save_point);
4070	goto retry;
4071	}
4072
4073	if (WARN_ON_ONCE(mas_is_underflow(mas)))
4074	return NULL;
4075
4076	mas->last = mas->max;
4077	node = mas_mn(mas);
4078	type = mte_node_type(mas->node);
4079	pivots = ma_pivots(node, type);
4080	mas->index = pivots[mas->offset - 1] + 1;
4081	}
4082
4083	slots = ma_slots(node, type);
4084	entry = mas_slot(mas, slots, mas->offset);
4085	if (unlikely(mas_rewalk_if_dead(mas, node, save_point)))
4086	goto retry;
4087
4088	if (likely(entry))
4089	return entry;
4090
4091	if (!empty) {
4092	if (mas->index <= min)
4093	goto underflow;
4094
4095	goto again;
4096	}
4097
4098	return entry;
4099
4100	underflow:
4101	mas->status = ma_underflow;
4102	return NULL;
4103	}
4104
4105	/*
4106	* mas_next_node() - Get the next node at the same level in the tree.
4107	* @mas: The maple state
4108	* @node: The maple node
4109	* @max: The maximum pivot value to check.
4110	*
4111	* The next value will be mas->node[mas->offset] or the status will have
4112	* overflowed.
4113	* Return: 1 on dead node, 0 otherwise.
4114	*/
4115	static int mas_next_node(struct ma_state mas, struct maple_node node,
4116	unsigned long max)
4117	{
4118	unsigned long min;
4119	unsigned long *pivots;
4120	struct maple_enode *enode;
4121	struct maple_node *tmp;
4122	int level = 0;
4123	unsigned char node_end;
4124	enum maple_type mt;
4125	void __rcu **slots;
4126
4127	if (mas->max >= max)
4128	goto overflow;
4129
4130	min = mas->max + 1;
4131	level = 0;
4132	do {
4133	if (ma_is_root(node))
4134	goto overflow;
4135
4136	/* Walk up. */
4137	if (unlikely(mas_ascend(mas)))
4138	return 1;
4139
4140	level++;
4141	node = mas_mn(mas);
4142	mt = mte_node_type(mas->node);
4143	pivots = ma_pivots(node, mt);
4144	node_end = ma_data_end(node, mt, pivots, mas->max);
4145	if (unlikely(ma_dead_node(node)))
4146	return 1;
4147
4148	} while (unlikely(mas->offset == node_end));
4149
4150	slots = ma_slots(node, mt);
4151	mas->offset++;
4152	enode = mas_slot(mas, slots, mas->offset);
4153	if (unlikely(ma_dead_node(node)))
4154	return 1;
4155
4156	if (level > 1)
4157	mas->offset = 0;
4158
4159	while (unlikely(level > 1)) {
4160	level--;
4161	mas->node = enode;
4162	node = mas_mn(mas);
4163	mt = mte_node_type(mas->node);
4164	slots = ma_slots(node, mt);
4165	enode = mas_slot(mas, slots, 0);
4166	if (unlikely(ma_dead_node(node)))
4167	return 1;
4168	}
4169
4170	if (!mas->offset)
4171	pivots = ma_pivots(node, mt);
4172
4173	mas->max = mas_safe_pivot(mas, pivots, mas->offset, mt);
4174	tmp = mte_to_node(enode);
4175	mt = mte_node_type(enode);
4176	pivots = ma_pivots(tmp, mt);
4177	mas->end = ma_data_end(tmp, mt, pivots, mas->max);
4178	if (unlikely(ma_dead_node(node)))
4179	return 1;
4180
4181	mas->node = enode;
4182	mas->min = min;
4183	return 0;
4184
4185	overflow:
4186	if (unlikely(ma_dead_node(node)))
4187	return 1;
4188
4189	mas->status = ma_overflow;
4190	return 0;
4191	}
4192
4193	/*
4194	* mas_next_slot() - Get the entry in the next slot
4195	*
4196	* @mas: The maple state
4197	* @max: The maximum starting range
4198	* @empty: Can be empty
4199	*
4200	* Return: The entry in the next slot which is possibly NULL
4201	*/
4202	static void mas_next_slot(struct ma_state mas, unsigned long max, bool empty)
4203	{
4204	void __rcu **slots;
4205	unsigned long *pivots;
4206	unsigned long pivot;
4207	enum maple_type type;
4208	struct maple_node *node;
4209	unsigned long save_point = mas->last;
4210	void *entry;
4211
4212	retry:
4213	node = mas_mn(mas);
4214	type = mte_node_type(mas->node);
4215	pivots = ma_pivots(node, type);
4216	if (unlikely(mas_rewalk_if_dead(mas, node, save_point)))
4217	goto retry;
4218
4219	if (mas->max >= max) {
4220	if (likely(mas->offset < mas->end))
4221	pivot = pivots[mas->offset];
4222	else
4223	pivot = mas->max;
4224
4225	if (unlikely(mas_rewalk_if_dead(mas, node, save_point)))
4226	goto retry;
4227
4228	if (pivot >= max) { /* Was at the limit, next will extend beyond */
4229	mas->status = ma_overflow;
4230	return NULL;
4231	}
4232	}
4233
4234	if (likely(mas->offset < mas->end)) {
4235	mas->index = pivots[mas->offset] + 1;
4236	again:
4237	mas->offset++;
4238	if (likely(mas->offset < mas->end))
4239	mas->last = pivots[mas->offset];
4240	else
4241	mas->last = mas->max;
4242	} else {
4243	if (mas->last >= max) {
4244	mas->status = ma_overflow;
4245	return NULL;
4246	}
4247
4248	if (mas_next_node(mas, node, max)) {
4249	mas_rewalk(mas, save_point);
4250	goto retry;
4251	}
4252
4253	if (WARN_ON_ONCE(mas_is_overflow(mas)))
4254	return NULL;
4255
4256	mas->offset = 0;
4257	mas->index = mas->min;
4258	node = mas_mn(mas);
4259	type = mte_node_type(mas->node);
4260	pivots = ma_pivots(node, type);
4261	mas->last = pivots[0];
4262	}
4263
4264	slots = ma_slots(node, type);
4265	entry = mt_slot(mas->tree, slots, mas->offset);
4266	if (unlikely(mas_rewalk_if_dead(mas, node, save_point)))
4267	goto retry;
4268
4269	if (entry)
4270	return entry;
4271
4272
4273	if (!empty) {
4274	if (mas->last >= max) {
4275	mas->status = ma_overflow;
4276	return NULL;
4277	}
4278
4279	mas->index = mas->last + 1;
4280	goto again;
4281	}
4282
4283	return entry;
4284	}
4285
4286	/*
4287	* mas_rev_awalk() - Internal function. Reverse allocation walk. Find the
4288	* highest gap address of a given size in a given node and descend.
4289	* @mas: The maple state
4290	* @size: The needed size.
4291	*
4292	* Return: True if found in a leaf, false otherwise.
4293	*
4294	*/
4295	static bool mas_rev_awalk(struct ma_state *mas, unsigned long size,
4296	unsigned long gap_min, unsigned long gap_max)
4297	{
4298	enum maple_type type = mte_node_type(mas->node);
4299	struct maple_node *node = mas_mn(mas);
4300	unsigned long pivots, gaps;
4301	void __rcu **slots;
4302	unsigned long gap = 0;
4303	unsigned long max, min;
4304	unsigned char offset;
4305
4306	if (unlikely(mas_is_err(mas)))
4307	return true;
4308
4309	if (ma_is_dense(type)) {
4310	/* dense nodes. */
4311	mas->offset = (unsigned char)(mas->index - mas->min);
4312	return true;
4313	}
4314
4315	pivots = ma_pivots(node, type);
4316	slots = ma_slots(node, type);
4317	gaps = ma_gaps(node, type);
4318	offset = mas->offset;
4319	min = mas_safe_min(mas, pivots, offset);
4320	/* Skip out of bounds. */
4321	while (mas->last < min)
4322	min = mas_safe_min(mas, pivots, --offset);
4323
4324	max = mas_safe_pivot(mas, pivots, offset, type);
4325	while (mas->index <= max) {
4326	gap = 0;
4327	if (gaps)
4328	gap = gaps[offset];
4329	else if (!mas_slot(mas, slots, offset))
4330	gap = max - min + 1;
4331
4332	if (gap) {
4333	if ((size <= gap) && (size <= mas->last - min + 1))
4334	break;
4335
4336	if (!gaps) {
4337	/* Skip the next slot, it cannot be a gap. */
4338	if (offset < 2)
4339	goto ascend;
4340
4341	offset -= 2;
4342	max = pivots[offset];
4343	min = mas_safe_min(mas, pivots, offset);
4344	continue;
4345	}
4346	}
4347
4348	if (!offset)
4349	goto ascend;
4350
4351	offset--;
4352	max = min - 1;
4353	min = mas_safe_min(mas, pivots, offset);
4354	}
4355
4356	if (unlikely((mas->index > max) \|\| (size - 1 > max - mas->index)))
4357	goto no_space;
4358
4359	if (unlikely(ma_is_leaf(type))) {
4360	mas->offset = offset;
4361	*gap_min = min;
4362	*gap_max = min + gap - 1;
4363	return true;
4364	}
4365
4366	/* descend, only happens under lock. */
4367	mas->node = mas_slot(mas, slots, offset);
4368	mas->min = min;
4369	mas->max = max;
4370	mas->offset = mas_data_end(mas);
4371	return false;
4372
4373	ascend:
4374	if (!mte_is_root(mas->node))
4375	return false;
4376
4377	no_space:
4378	mas_set_err(mas, -EBUSY);
4379	return false;
4380	}
4381
4382	static inline bool mas_anode_descend(struct ma_state *mas, unsigned long size)
4383	{
4384	enum maple_type type = mte_node_type(mas->node);
4385	unsigned long pivot, min, gap = 0;
4386	unsigned char offset, data_end;
4387	unsigned long gaps, pivots;
4388	void __rcu **slots;
4389	struct maple_node *node;
4390	bool found = false;
4391
4392	if (ma_is_dense(type)) {
4393	mas->offset = (unsigned char)(mas->index - mas->min);
4394	return true;
4395	}
4396
4397	node = mas_mn(mas);
4398	pivots = ma_pivots(node, type);
4399	slots = ma_slots(node, type);
4400	gaps = ma_gaps(node, type);
4401	offset = mas->offset;
4402	min = mas_safe_min(mas, pivots, offset);
4403	data_end = ma_data_end(node, type, pivots, mas->max);
4404	for (; offset <= data_end; offset++) {
4405	pivot = mas_safe_pivot(mas, pivots, offset, type);
4406
4407	/* Not within lower bounds */
4408	if (mas->index > pivot)
4409	goto next_slot;
4410
4411	if (gaps)
4412	gap = gaps[offset];
4413	else if (!mas_slot(mas, slots, offset))
4414	gap = min(pivot, mas->last) - max(mas->index, min) + 1;
4415	else
4416	goto next_slot;
4417
4418	if (gap >= size) {
4419	if (ma_is_leaf(type)) {
4420	found = true;
4421	break;
4422	}
4423
4424	mas->node = mas_slot(mas, slots, offset);
4425	mas->min = min;
4426	mas->max = pivot;
4427	offset = 0;
4428	break;
4429	}
4430	next_slot:
4431	min = pivot + 1;
4432	if (mas->last <= pivot) {
4433	mas_set_err(mas, -EBUSY);
4434	return true;
4435	}
4436	}
4437
4438	mas->offset = offset;
4439	return found;
4440	}
4441
4442	/**
4443	* mas_walk() - Search for @mas->index in the tree.
4444	* @mas: The maple state.
4445	*
4446	* mas->index and mas->last will be set to the range if there is a value. If
4447	* mas->status is ma_none, reset to ma_start
4448	*
4449	* Return: the entry at the location or %NULL.
4450	*/
4451	void mas_walk(struct ma_state mas)
4452	{
4453	void *entry;
4454
4455	mas_may_init_lock_check(mas);
4456	mas_make_walkable(mas);
4457	retry:
4458	entry = mas_state_walk(mas);
4459	if (mas_is_start(mas)) {
4460	goto retry;
4461	} else if (mas_is_none(mas)) {
4462	mas->index = 0;
4463	mas->last = ULONG_MAX;
4464	} else if (mas_is_ptr(mas)) {
4465	if (!mas->index) {
4466	mas->last = 0;
4467	return entry;
4468	}
4469
4470	mas->index = 1;
4471	mas->last = ULONG_MAX;
4472	mas->status = ma_none;
4473	return NULL;
4474	}
4475
4476	return entry;
4477	}
4478	EXPORT_SYMBOL_GPL(mas_walk);
4479
4480	static inline bool mas_rewind_node(struct ma_state *mas)
4481	{
4482	unsigned char slot;
4483
4484	do {
4485	if (mte_is_root(mas->node)) {
4486	slot = mas->offset;
4487	if (!slot)
4488	return false;
4489	} else {
4490	mas_ascend(mas);
4491	slot = mas->offset;
4492	}
4493	} while (!slot);
4494
4495	mas->offset = --slot;
4496	return true;
4497	}
4498
4499	/*
4500	* mas_skip_node() - Internal function. Skip over a node.
4501	* @mas: The maple state.
4502	*
4503	* Return: true if there is another node, false otherwise.
4504	*/
4505	static inline bool mas_skip_node(struct ma_state *mas)
4506	{
4507	if (mas_is_err(mas))
4508	return false;
4509
4510	do {
4511	if (mte_is_root(mas->node)) {
4512	if (mas->offset >= mas_data_end(mas)) {
4513	mas_set_err(mas, -EBUSY);
4514	return false;
4515	}
4516	} else {
4517	mas_ascend(mas);
4518	}
4519	} while (mas->offset >= mas_data_end(mas));
4520
4521	mas->offset++;
4522	return true;
4523	}
4524
4525	/*
4526	* mas_awalk() - Allocation walk. Search from low address to high, for a gap of
4527	* @size
4528	* @mas: The maple state
4529	* @size: The size of the gap required
4530	*
4531	* Search between @mas->index and @mas->last for a gap of @size.
4532	*/
4533	static inline void mas_awalk(struct ma_state *mas, unsigned long size)
4534	{
4535	struct maple_enode *last = NULL;
4536
4537	/*
4538	* There are 4 options:
4539	* go to child (descend)
4540	* go back to parent (ascend)
4541	* no gap found. (return, error == -EBUSY)
4542	* found the gap. (return)
4543	*/
4544	while (!mas_is_err(mas) && !mas_anode_descend(mas, size)) {
4545	if (last == mas->node)
4546	mas_skip_node(mas);
4547	else
4548	last = mas->node;
4549	}
4550	}
4551
4552	/*
4553	* mas_sparse_area() - Internal function. Return upper or lower limit when
4554	* searching for a gap in an empty tree.
4555	* @mas: The maple state
4556	* @min: the minimum range
4557	* @max: The maximum range
4558	* @size: The size of the gap
4559	* @fwd: Searching forward or back
4560	*/
4561	static inline int mas_sparse_area(struct ma_state *mas, unsigned long min,
4562	unsigned long max, unsigned long size, bool fwd)
4563	{
4564	if (!unlikely(mas_is_none(mas)) && min == 0) {
4565	min++;
4566	/*
4567	* At this time, min is increased, we need to recheck whether
4568	* the size is satisfied.
4569	*/
4570	if (min > max \|\| max - min + 1 < size)
4571	return -EBUSY;
4572	}
4573	/* mas_is_ptr */
4574
4575	if (fwd) {
4576	mas->index = min;
4577	mas->last = min + size - 1;
4578	} else {
4579	mas->last = max;
4580	mas->index = max - size + 1;
4581	}
4582	return 0;
4583	}
4584
4585	/*
4586	* mas_empty_area() - Get the lowest address within the range that is
4587	* sufficient for the size requested.
4588	* @mas: The maple state
4589	* @min: The lowest value of the range
4590	* @max: The highest value of the range
4591	* @size: The size needed
4592	*/
4593	int mas_empty_area(struct ma_state *mas, unsigned long min,
4594	unsigned long max, unsigned long size)
4595	{
4596	unsigned char offset;
4597	unsigned long *pivots;
4598	enum maple_type mt;
4599	struct maple_node *node;
4600
4601	if (min > max)
4602	return -EINVAL;
4603
4604	if (size == 0 \|\| max - min < size - 1)
4605	return -EINVAL;
4606
4607	if (mas_is_start(mas))
4608	mas_start(mas);
4609	else if (mas->offset >= 2)
4610	mas->offset -= 2;
4611	else if (!mas_skip_node(mas))
4612	return -EBUSY;
4613
4614	/* Empty set */
4615	if (mas_is_none(mas) \|\| mas_is_ptr(mas))
4616	return mas_sparse_area(mas, min, max, size, true);
4617
4618	/* The start of the window can only be within these values */
4619	mas->index = min;
4620	mas->last = max;
4621	mas_awalk(mas, size);
4622
4623	if (unlikely(mas_is_err(mas)))
4624	return xa_err(mas->node);
4625
4626	offset = mas->offset;
4627	node = mas_mn(mas);
4628	mt = mte_node_type(mas->node);
4629	pivots = ma_pivots(node, mt);
4630	min = mas_safe_min(mas, pivots, offset);
4631	if (mas->index < min)
4632	mas->index = min;
4633	mas->last = mas->index + size - 1;
4634	mas->end = ma_data_end(node, mt, pivots, mas->max);
4635	return 0;
4636	}
4637	EXPORT_SYMBOL_GPL(mas_empty_area);
4638
4639	/*
4640	* mas_empty_area_rev() - Get the highest address within the range that is
4641	* sufficient for the size requested.
4642	* @mas: The maple state
4643	* @min: The lowest value of the range
4644	* @max: The highest value of the range
4645	* @size: The size needed
4646	*/
4647	int mas_empty_area_rev(struct ma_state *mas, unsigned long min,
4648	unsigned long max, unsigned long size)
4649	{
4650	struct maple_enode *last = mas->node;
4651
4652	if (min > max)
4653	return -EINVAL;
4654
4655	if (size == 0 \|\| max - min < size - 1)
4656	return -EINVAL;
4657
4658	if (mas_is_start(mas))
4659	mas_start(mas);
4660	else if ((mas->offset < 2) && (!mas_rewind_node(mas)))
4661	return -EBUSY;
4662
4663	if (unlikely(mas_is_none(mas) \|\| mas_is_ptr(mas)))
4664	return mas_sparse_area(mas, min, max, size, false);
4665	else if (mas->offset >= 2)
4666	mas->offset -= 2;
4667	else
4668	mas->offset = mas_data_end(mas);
4669
4670
4671	/* The start of the window can only be within these values. */
4672	mas->index = min;
4673	mas->last = max;
4674
4675	while (!mas_rev_awalk(mas, size, &min, &max)) {
4676	if (last == mas->node) {
4677	if (!mas_rewind_node(mas))
4678	return -EBUSY;
4679	} else {
4680	last = mas->node;
4681	}
4682	}
4683
4684	if (mas_is_err(mas))
4685	return xa_err(mas->node);
4686
4687	if (unlikely(mas->offset == MAPLE_NODE_SLOTS))
4688	return -EBUSY;
4689
4690	/* Trim the upper limit to the max. */
4691	if (max < mas->last)
4692	mas->last = max;
4693
4694	mas->index = mas->last - size + 1;
4695	mas->end = mas_data_end(mas);
4696	return 0;
4697	}
4698	EXPORT_SYMBOL_GPL(mas_empty_area_rev);
4699
4700	/*
4701	* mte_dead_leaves() - Mark all leaves of a node as dead.
4702	* @enode: the encoded node
4703	* @mt: the maple tree
4704	* @slots: Pointer to the slot array
4705	*
4706	* Must hold the write lock.
4707	*
4708	* Return: The number of leaves marked as dead.
4709	*/
4710	static inline
4711	unsigned char mte_dead_leaves(struct maple_enode enode, struct maple_tree mt,
4712	void __rcu **slots)
4713	{
4714	struct maple_node *node;
4715	enum maple_type type;
4716	void *entry;
4717	int offset;
4718
4719	for (offset = 0; offset < mt_slot_count(enode); offset++) {
4720	entry = mt_slot(mt, slots, offset);
4721	type = mte_node_type(entry);
4722	node = mte_to_node(entry);
4723	/* Use both node and type to catch LE & BE metadata */
4724	if (!node \|\| !type)
4725	break;
4726
4727	mte_set_node_dead(entry);
4728	node->type = type;
4729	rcu_assign_pointer(slots[offset], node);
4730	}
4731
4732	return offset;
4733	}
4734
4735	/**
4736	* mte_dead_walk() - Walk down a dead tree to just before the leaves
4737	* @enode: The maple encoded node
4738	* @offset: The starting offset
4739	*
4740	* Note: This can only be used from the RCU callback context.
4741	*/
4742	static void __rcu mte_dead_walk(struct maple_enode enode, unsigned char offset)
4743	{
4744	struct maple_node node, next;
4745	void __rcu **slots = NULL;
4746
4747	next = mte_to_node(*enode);
4748	do {
4749	*enode = ma_enode_ptr(next);
4750	node = mte_to_node(*enode);
4751	slots = ma_slots(node, node->type);
4752	next = rcu_dereference_protected(slots[offset],
4753	lock_is_held(&rcu_callback_map));
4754	offset = 0;
4755	} while (!ma_is_leaf(next->type));
4756
4757	return slots;
4758	}
4759
4760	/**
4761	* mt_free_walk() - Walk & free a tree in the RCU callback context
4762	* @head: The RCU head that's within the node.
4763	*
4764	* Note: This can only be used from the RCU callback context.
4765	*/
4766	static void mt_free_walk(struct rcu_head *head)
4767	{
4768	void __rcu **slots;
4769	struct maple_node node, start;
4770	struct maple_enode *enode;
4771	unsigned char offset;
4772	enum maple_type type;
4773
4774	node = container_of(head, struct maple_node, rcu);
4775
4776	if (ma_is_leaf(node->type))
4777	goto free_leaf;
4778
4779	start = node;
4780	enode = mt_mk_node(node, node->type);
4781	slots = mte_dead_walk(&enode, 0);
4782	node = mte_to_node(enode);
4783	do {
4784	mt_free_bulk(node->slot_len, slots);
4785	offset = node->parent_slot + 1;
4786	enode = node->piv_parent;
4787	if (mte_to_node(enode) == node)
4788	goto free_leaf;
4789
4790	type = mte_node_type(enode);
4791	slots = ma_slots(mte_to_node(enode), type);
4792	if ((offset < mt_slots[type]) &&
4793	rcu_dereference_protected(slots[offset],
4794	lock_is_held(&rcu_callback_map)))
4795	slots = mte_dead_walk(&enode, offset);
4796	node = mte_to_node(enode);
4797	} while ((node != start) \|\| (node->slot_len < offset));
4798
4799	slots = ma_slots(node, node->type);
4800	mt_free_bulk(node->slot_len, slots);
4801
4802	free_leaf:
4803	kfree(node);
4804	}
4805
4806	static inline void __rcu mte_destroy_descend(struct maple_enode enode,
4807	struct maple_tree mt, struct maple_enode prev, unsigned char offset)
4808	{
4809	struct maple_node *node;
4810	struct maple_enode next = enode;
4811	void __rcu **slots = NULL;
4812	enum maple_type type;
4813	unsigned char next_offset = 0;
4814
4815	do {
4816	*enode = next;
4817	node = mte_to_node(*enode);
4818	type = mte_node_type(*enode);
4819	slots = ma_slots(node, type);
4820	next = mt_slot_locked(mt, slots, next_offset);
4821	if ((mte_dead_node(next)))
4822	next = mt_slot_locked(mt, slots, ++next_offset);
4823
4824	mte_set_node_dead(*enode);
4825	node->type = type;
4826	node->piv_parent = prev;
4827	node->parent_slot = offset;
4828	offset = next_offset;
4829	next_offset = 0;
4830	prev = *enode;
4831	} while (!mte_is_leaf(next));
4832
4833	return slots;
4834	}
4835
4836	static void mt_destroy_walk(struct maple_enode enode, struct maple_tree mt,
4837	bool free)
4838	{
4839	void __rcu **slots;
4840	struct maple_node *node = mte_to_node(enode);
4841	struct maple_enode *start;
4842
4843	if (mte_is_leaf(enode)) {
4844	mte_set_node_dead(enode);
4845	node->type = mte_node_type(enode);
4846	goto free_leaf;
4847	}
4848
4849	start = enode;
4850	slots = mte_destroy_descend(&enode, mt, start, 0);
4851	node = mte_to_node(enode); // Updated in the above call.
4852	do {
4853	enum maple_type type;
4854	unsigned char offset;
4855	struct maple_enode parent, tmp;
4856
4857	node->slot_len = mte_dead_leaves(enode, mt, slots);
4858	if (free)
4859	mt_free_bulk(node->slot_len, slots);
4860	offset = node->parent_slot + 1;
4861	enode = node->piv_parent;
4862	if (mte_to_node(enode) == node)
4863	goto free_leaf;
4864
4865	type = mte_node_type(enode);
4866	slots = ma_slots(mte_to_node(enode), type);
4867	if (offset >= mt_slots[type])
4868	goto next;
4869
4870	tmp = mt_slot_locked(mt, slots, offset);
4871	if (mte_node_type(tmp) && mte_to_node(tmp)) {
4872	parent = enode;
4873	enode = tmp;
4874	slots = mte_destroy_descend(&enode, mt, parent, offset);
4875	}
4876	next:
4877	node = mte_to_node(enode);
4878	} while (start != enode);
4879
4880	node = mte_to_node(enode);
4881	node->slot_len = mte_dead_leaves(enode, mt, slots);
4882	if (free)
4883	mt_free_bulk(node->slot_len, slots);
4884
4885	free_leaf:
4886	if (free)
4887	kfree(node);
4888	else
4889	mt_clear_meta(mt, node, node->type);
4890	}
4891
4892	/*
4893	* mte_destroy_walk() - Free a tree or sub-tree.
4894	* @enode: the encoded maple node (maple_enode) to start
4895	* @mt: the tree to free - needed for node types.
4896	*
4897	* Must hold the write lock.
4898	*/
4899	static inline void mte_destroy_walk(struct maple_enode *enode,
4900	struct maple_tree *mt)
4901	{
4902	struct maple_node *node = mte_to_node(enode);
4903
4904	if (mt_in_rcu(mt)) {
4905	mt_destroy_walk(enode, mt, false);
4906	call_rcu(&node->rcu, mt_free_walk);
4907	} else {
4908	mt_destroy_walk(enode, mt, true);
4909	}
4910	}
4911	/* Interface */
4912
4913	/**
4914	* mas_store() - Store an @entry.
4915	* @mas: The maple state.
4916	* @entry: The entry to store.
4917	*
4918	* The @mas->index and @mas->last is used to set the range for the @entry.
4919	*
4920	* Return: the first entry between mas->index and mas->last or %NULL.
4921	*/
4922	void mas_store(struct ma_state mas, void *entry)
4923	{
4924	MA_WR_STATE(wr_mas, mas, entry);
4925
4926	mas_may_init_lock_check(mas);
4927	trace_ma_write(TP_FCT, mas, 0, entry);
4928	#ifdef CONFIG_DEBUG_MAPLE_TREE
4929	if (MAS_WARN_ON(mas, mas->index > mas->last))
4930	pr_err("Error %lX > %lX " PTR_FMT "\n", mas->index, mas->last,
4931	entry);
4932
4933	if (mas->index > mas->last) {
4934	mas_set_err(mas, -EINVAL);
4935	return NULL;
4936	}
4937
4938	#endif
4939
4940	/*
4941	* Storing is the same operation as insert with the added caveat that it
4942	* can overwrite entries. Although this seems simple enough, one may
4943	* want to examine what happens if a single store operation was to
4944	* overwrite multiple entries within a self-balancing B-Tree.
4945	*/
4946	mas_wr_prealloc_setup(&wr_mas);
4947	mas->store_type = mas_wr_store_type(&wr_mas);
4948	if (mas->mas_flags & MA_STATE_PREALLOC) {
4949	mas_wr_store_entry(&wr_mas);
4950	MAS_WR_BUG_ON(&wr_mas, mas_is_err(mas));
4951	return wr_mas.content;
4952	}
4953
4954	mas_prealloc_calc(&wr_mas, entry);
4955	if (!mas->node_request)
4956	goto store;
4957
4958	mas_alloc_nodes(mas, GFP_NOWAIT);
4959	if (mas_is_err(mas))
4960	return NULL;
4961
4962	store:
4963	mas_wr_store_entry(&wr_mas);
4964	mas_destroy(mas);
4965	return wr_mas.content;
4966	}
4967	EXPORT_SYMBOL_GPL(mas_store);
4968
4969	/**
4970	* mas_store_gfp() - Store a value into the tree.
4971	* @mas: The maple state
4972	* @entry: The entry to store
4973	* @gfp: The GFP_FLAGS to use for allocations if necessary.
4974	*
4975	* Return: 0 on success, -EINVAL on invalid request, -ENOMEM if memory could not
4976	* be allocated.
4977	*/
4978	int mas_store_gfp(struct ma_state mas, void entry, gfp_t gfp)
4979	{
4980	unsigned long index = mas->index;
4981	unsigned long last = mas->last;
4982	MA_WR_STATE(wr_mas, mas, entry);
4983	int ret = 0;
4984
4985	mas_may_init_lock_check(mas);
4986	retry:
4987	mas_wr_preallocate(&wr_mas, entry);
4988	if (unlikely(mas_nomem(mas, gfp))) {
4989	if (!entry)
4990	__mas_set_range(mas, index, last);
4991	goto retry;
4992	}
4993
4994	if (mas_is_err(mas)) {
4995	ret = xa_err(mas->node);
4996	goto out;
4997	}
4998
4999	mas_wr_store_entry(&wr_mas);
5000	out:
5001	mas_destroy(mas);
5002	return ret;
5003	}
5004	EXPORT_SYMBOL_GPL(mas_store_gfp);
5005
5006	/**
5007	* mas_store_prealloc() - Store a value into the tree using memory
5008	* preallocated in the maple state.
5009	* @mas: The maple state
5010	* @entry: The entry to store.
5011	*/
5012	void mas_store_prealloc(struct ma_state mas, void entry)
5013	{
5014	MA_WR_STATE(wr_mas, mas, entry);
5015
5016	mas_lock_check(mas);
5017	if (mas->store_type == wr_store_root) {
5018	mas_wr_prealloc_setup(&wr_mas);
5019	goto store;
5020	}
5021
5022	mas_wr_walk_descend(&wr_mas);
5023	if (mas->store_type != wr_spanning_store) {
5024	/* set wr_mas->content to current slot */
5025	wr_mas.content = mas_slot_locked(mas, wr_mas.slots, mas->offset);
5026	mas_wr_end_piv(&wr_mas);
5027	}
5028
5029	store:
5030	trace_ma_write(TP_FCT, mas, 0, entry);
5031	mas_wr_store_entry(&wr_mas);
5032	MAS_WR_BUG_ON(&wr_mas, mas_is_err(mas));
5033	mas_destroy(mas);
5034	}
5035	EXPORT_SYMBOL_GPL(mas_store_prealloc);
5036
5037	/**
5038	* mas_preallocate() - Preallocate enough nodes for a store operation
5039	* @mas: The maple state
5040	* @entry: The entry that will be stored
5041	* @gfp: The GFP_FLAGS to use for allocations.
5042	*
5043	* Return: 0 on success, -ENOMEM if memory could not be allocated.
5044	*/
5045	int mas_preallocate(struct ma_state mas, void entry, gfp_t gfp)
5046	{
5047	MA_WR_STATE(wr_mas, mas, entry);
5048
5049	mas_may_init_lock_check(mas);
5050	mas_wr_prealloc_setup(&wr_mas);
5051	mas->store_type = mas_wr_store_type(&wr_mas);
5052	mas_prealloc_calc(&wr_mas, entry);
5053	if (!mas->node_request)
5054	goto set_flag;
5055
5056	mas->mas_flags &= ~MA_STATE_PREALLOC;
5057	mas_alloc_nodes(mas, gfp);
5058	if (mas_is_err(mas)) {
5059	int ret = xa_err(mas->node);
5060
5061	mas->node_request = 0;
5062	mas_destroy(mas);
5063	mas_reset(mas);
5064	return ret;
5065	}
5066
5067	set_flag:
5068	mas->mas_flags \|= MA_STATE_PREALLOC;
5069	return 0;
5070	}
5071	EXPORT_SYMBOL_GPL(mas_preallocate);
5072
5073	/*
5074	* mas_destroy() - destroy a maple state.
5075	* @mas: The maple state
5076	*
5077	* Upon completion, check the left-most node and rebalance against the node to
5078	* the right if necessary. Frees any allocated nodes associated with this maple
5079	* state.
5080	*/
5081	void mas_destroy(struct ma_state *mas)
5082	{
5083	mas->mas_flags &= ~MA_STATE_PREALLOC;
5084	mas_empty_nodes(mas);
5085	}
5086	EXPORT_SYMBOL_GPL(mas_destroy);
5087
5088	static void mas_may_activate(struct ma_state *mas)
5089	{
5090	if (!mas->node) {
5091	mas->status = ma_start;
5092	} else if (mas->index > mas->max \|\| mas->index < mas->min) {
5093	mas->status = ma_start;
5094	} else {
5095	mas->status = ma_active;
5096	mas_lock_check(mas);
5097	}
5098	}
5099
5100	static bool mas_next_setup(struct ma_state *mas, unsigned long max,
5101	void **entry)
5102	{
5103	bool was_none = mas_is_none(mas);
5104
5105	if (unlikely(mas->last >= max)) {
5106	mas->status = ma_overflow;
5107	return true;
5108	}
5109
5110	switch (mas->status) {
5111	case ma_active:
5112	return false;
5113	case ma_none:
5114	fallthrough;
5115	case ma_pause:
5116	mas->status = ma_start;
5117	fallthrough;
5118	case ma_start:
5119	mas_walk(mas); /* Retries on dead nodes handled by mas_walk */
5120	break;
5121	case ma_overflow:
5122	/* Overflowed before, but the max changed */
5123	mas_may_activate(mas);
5124	break;
5125	case ma_underflow:
5126	/* The user expects the mas to be one before where it is */
5127	mas_may_activate(mas);
5128	*entry = mas_walk(mas);
5129	if (*entry)
5130	return true;
5131	break;
5132	case ma_root:
5133	break;
5134	case ma_error:
5135	return true;
5136	}
5137
5138	if (likely(mas_is_active(mas))) /* Fast path */
5139	return false;
5140
5141	if (mas_is_ptr(mas)) {
5142	*entry = NULL;
5143	if (was_none && mas->index == 0) {
5144	mas->index = mas->last = 0;
5145	return true;
5146	}
5147	mas->index = 1;
5148	mas->last = ULONG_MAX;
5149	mas->status = ma_none;
5150	return true;
5151	}
5152
5153	if (mas_is_none(mas))
5154	return true;
5155
5156	return false;
5157	}
5158
5159	/**
5160	* mas_next() - Get the next entry.
5161	* @mas: The maple state
5162	* @max: The maximum index to check.
5163	*
5164	* Returns the next entry after @mas->index.
5165	* Must hold rcu_read_lock or the write lock.
5166	* Can return the zero entry.
5167	*
5168	* Return: The next entry or %NULL
5169	*/
5170	void mas_next(struct ma_state mas, unsigned long max)
5171	{
5172	void *entry = NULL;
5173
5174	mas_may_init_lock_check(mas);
5175	if (mas_next_setup(mas, max, &entry))
5176	return entry;
5177
5178	/* Retries on dead nodes handled by mas_next_slot */
5179	return mas_next_slot(mas, max, false);
5180	}
5181	EXPORT_SYMBOL_GPL(mas_next);
5182
5183	/**
5184	* mas_next_range() - Advance the maple state to the next range
5185	* @mas: The maple state
5186	* @max: The maximum index to check.
5187	*
5188	* Sets @mas->index and @mas->last to the range.
5189	* Must hold rcu_read_lock or the write lock.
5190	* Can return the zero entry.
5191	*
5192	* Return: The next entry or %NULL
5193	*/
5194	void mas_next_range(struct ma_state mas, unsigned long max)
5195	{
5196	void *entry = NULL;
5197
5198	mas_may_init_lock_check(mas);
5199	if (mas_next_setup(mas, max, &entry))
5200	return entry;
5201
5202	/* Retries on dead nodes handled by mas_next_slot */
5203	return mas_next_slot(mas, max, true);
5204	}
5205	EXPORT_SYMBOL_GPL(mas_next_range);
5206
5207	/**
5208	* mt_next() - get the next value in the maple tree
5209	* @mt: The maple tree
5210	* @index: The start index
5211	* @max: The maximum index to check
5212	*
5213	* Takes RCU read lock internally to protect the search, which does not
5214	* protect the returned pointer after dropping RCU read lock.
5215	* See also: Documentation/core-api/maple_tree.rst
5216	*
5217	* Return: The entry higher than @index or %NULL if nothing is found.
5218	*/
5219	void mt_next(struct maple_tree mt, unsigned long index, unsigned long max)
5220	{
5221	void *entry = NULL;
5222	MA_STATE(mas, mt, index, index);
5223
5224	rcu_read_lock();
5225	entry = mas_next(&mas, max);
5226	rcu_read_unlock();
5227	return entry;
5228	}
5229	EXPORT_SYMBOL_GPL(mt_next);
5230
5231	static bool mas_prev_setup(struct ma_state mas, unsigned long min, void *entry)
5232	{
5233	if (unlikely(mas->index <= min)) {
5234	mas->status = ma_underflow;
5235	return true;
5236	}
5237
5238	switch (mas->status) {
5239	case ma_active:
5240	return false;
5241	case ma_start:
5242	break;
5243	case ma_none:
5244	fallthrough;
5245	case ma_pause:
5246	mas->status = ma_start;
5247	break;
5248	case ma_underflow:
5249	/* underflowed before but the min changed */
5250	mas_may_activate(mas);
5251	break;
5252	case ma_overflow:
5253	/* User expects mas to be one after where it is */
5254	mas_may_activate(mas);
5255	*entry = mas_walk(mas);
5256	if (*entry)
5257	return true;
5258	break;
5259	case ma_root:
5260	break;
5261	case ma_error:
5262	return true;
5263	}
5264
5265	if (mas_is_start(mas))
5266	mas_walk(mas);
5267
5268	if (unlikely(mas_is_ptr(mas))) {
5269	if (!mas->index) {
5270	mas->status = ma_none;
5271	return true;
5272	}
5273	mas->index = mas->last = 0;
5274	*entry = mas_root(mas);
5275	return true;
5276	}
5277
5278	if (mas_is_none(mas)) {
5279	if (mas->index) {
5280	/* Walked to out-of-range pointer? */
5281	mas->index = mas->last = 0;
5282	mas->status = ma_root;
5283	*entry = mas_root(mas);
5284	return true;
5285	}
5286	return true;
5287	}
5288
5289	return false;
5290	}
5291
5292	/**
5293	* mas_prev() - Get the previous entry
5294	* @mas: The maple state
5295	* @min: The minimum value to check.
5296	*
5297	* Must hold rcu_read_lock or the write lock.
5298	* Will reset mas to ma_start if the status is ma_none. Will stop on not
5299	* searchable nodes.
5300	*
5301	* Return: the previous value or %NULL.
5302	*/
5303	void mas_prev(struct ma_state mas, unsigned long min)
5304	{
5305	void *entry = NULL;
5306
5307	mas_may_init_lock_check(mas);
5308	if (mas_prev_setup(mas, min, &entry))
5309	return entry;
5310
5311	return mas_prev_slot(mas, min, false);
5312	}
5313	EXPORT_SYMBOL_GPL(mas_prev);
5314
5315	/**
5316	* mas_prev_range() - Advance to the previous range
5317	* @mas: The maple state
5318	* @min: The minimum value to check.
5319	*
5320	* Sets @mas->index and @mas->last to the range.
5321	* Must hold rcu_read_lock or the write lock.
5322	* Will reset mas to ma_start if the node is ma_none. Will stop on not
5323	* searchable nodes.
5324	*
5325	* Return: the previous value or %NULL.
5326	*/
5327	void mas_prev_range(struct ma_state mas, unsigned long min)
5328	{
5329	void *entry = NULL;
5330
5331	mas_may_init_lock_check(mas);
5332	if (mas_prev_setup(mas, min, &entry))
5333	return entry;
5334
5335	return mas_prev_slot(mas, min, true);
5336	}
5337	EXPORT_SYMBOL_GPL(mas_prev_range);
5338
5339	/**
5340	* mt_prev() - get the previous value in the maple tree
5341	* @mt: The maple tree
5342	* @index: The start index
5343	* @min: The minimum index to check
5344	*
5345	* Takes RCU read lock internally to protect the search, which does not
5346	* protect the returned pointer after dropping RCU read lock.
5347	* See also: Documentation/core-api/maple_tree.rst
5348	*
5349	* Return: The entry before @index or %NULL if nothing is found.
5350	*/
5351	void mt_prev(struct maple_tree mt, unsigned long index, unsigned long min)
5352	{
5353	void *entry = NULL;
5354	MA_STATE(mas, mt, index, index);
5355
5356	rcu_read_lock();
5357	entry = mas_prev(&mas, min);
5358	rcu_read_unlock();
5359	return entry;
5360	}
5361	EXPORT_SYMBOL_GPL(mt_prev);
5362
5363	/**
5364	* mas_pause() - Pause a mas_find/mas_for_each to drop the lock.
5365	* @mas: The maple state to pause
5366	*
5367	* Some users need to pause a walk and drop the lock they're holding in
5368	* order to yield to a higher priority thread or carry out an operation
5369	* on an entry. Those users should call this function before they drop
5370	* the lock. It resets the @mas to be suitable for the next iteration
5371	* of the loop after the user has reacquired the lock. If most entries
5372	* found during a walk require you to call mas_pause(), the mt_for_each()
5373	* iterator may be more appropriate.
5374	*
5375	*/
5376	void mas_pause(struct ma_state *mas)
5377	{
5378	mas_lock_check(mas);
5379	mas->status = ma_pause;
5380	mas->node = NULL;
5381	}
5382	EXPORT_SYMBOL_GPL(mas_pause);
5383
5384	/**
5385	* mas_find_setup() - Internal function to set up mas_find*().
5386	* @mas: The maple state
5387	* @max: The maximum index
5388	* @entry: Pointer to the entry
5389	*
5390	* Returns: True if entry is the answer, false otherwise.
5391	*/
5392	static __always_inline bool mas_find_setup(struct ma_state mas, unsigned long max, void *entry)
5393	{
5394	switch (mas->status) {
5395	case ma_active:
5396	if (mas->last < max)
5397	return false;
5398	return true;
5399	case ma_start:
5400	break;
5401	case ma_pause:
5402	if (unlikely(mas->last >= max))
5403	return true;
5404
5405	mas->index = ++mas->last;
5406	mas->status = ma_start;
5407	break;
5408	case ma_none:
5409	if (unlikely(mas->last >= max))
5410	return true;
5411
5412	mas->index = mas->last;
5413	mas->status = ma_start;
5414	break;
5415	case ma_underflow:
5416	/* mas is pointing at entry before unable to go lower */
5417	if (unlikely(mas->index >= max)) {
5418	mas->status = ma_overflow;
5419	return true;
5420	}
5421
5422	mas_may_activate(mas);
5423	*entry = mas_walk(mas);
5424	if (*entry)
5425	return true;
5426	break;
5427	case ma_overflow:
5428	if (unlikely(mas->last >= max))
5429	return true;
5430
5431	mas_may_activate(mas);
5432	*entry = mas_walk(mas);
5433	if (*entry)
5434	return true;
5435	break;
5436	case ma_root:
5437	break;
5438	case ma_error:
5439	return true;
5440	}
5441
5442	if (mas_is_start(mas)) {
5443	/* First run or continue */
5444	if (mas->index > max)
5445	return true;
5446
5447	*entry = mas_walk(mas);
5448	if (*entry)
5449	return true;
5450
5451	}
5452
5453	if (unlikely(mas_is_ptr(mas)))
5454	goto ptr_out_of_range;
5455
5456	if (unlikely(mas_is_none(mas)))
5457	return true;
5458
5459	if (mas->index == max)
5460	return true;
5461
5462	return false;
5463
5464	ptr_out_of_range:
5465	mas->status = ma_none;
5466	mas->index = 1;
5467	mas->last = ULONG_MAX;
5468	return true;
5469	}
5470
5471	/**
5472	* mas_find() - On the first call, find the entry at or after mas->index up to
5473	* %max. Otherwise, find the entry after mas->index.
5474	* @mas: The maple state
5475	* @max: The maximum value to check.
5476	*
5477	* Must hold rcu_read_lock or the write lock.
5478	* If an entry exists, last and index are updated accordingly.
5479	* May set @mas->status to ma_overflow.
5480	*
5481	* Return: The entry or %NULL.
5482	*/
5483	void mas_find(struct ma_state mas, unsigned long max)
5484	{
5485	void *entry = NULL;
5486
5487	mas_may_init_lock_check(mas);
5488	if (mas_find_setup(mas, max, &entry))
5489	return entry;
5490
5491	/* Retries on dead nodes handled by mas_next_slot */
5492	entry = mas_next_slot(mas, max, false);
5493	/* Ignore overflow */
5494	mas->status = ma_active;
5495	return entry;
5496	}
5497	EXPORT_SYMBOL_GPL(mas_find);
5498
5499	/**
5500	* mas_find_range() - On the first call, find the entry at or after
5501	* mas->index up to %max. Otherwise, advance to the next slot mas->index.
5502	* @mas: The maple state
5503	* @max: The maximum value to check.
5504	*
5505	* Must hold rcu_read_lock or the write lock.
5506	* If an entry exists, last and index are updated accordingly.
5507	* May set @mas->status to ma_overflow.
5508	*
5509	* Return: The entry or %NULL.
5510	*/
5511	void mas_find_range(struct ma_state mas, unsigned long max)
5512	{
5513	void *entry = NULL;
5514
5515	mas_may_init_lock_check(mas);
5516	if (mas_find_setup(mas, max, &entry))
5517	return entry;
5518
5519	/* Retries on dead nodes handled by mas_next_slot */
5520	return mas_next_slot(mas, max, true);
5521	}
5522	EXPORT_SYMBOL_GPL(mas_find_range);
5523
5524	/**
5525	* mas_find_rev_setup() - Internal function to set up mas_find_*_rev()
5526	* @mas: The maple state
5527	* @min: The minimum index
5528	* @entry: Pointer to the entry
5529	*
5530	* Returns: True if entry is the answer, false otherwise.
5531	*/
5532	static bool mas_find_rev_setup(struct ma_state *mas, unsigned long min,
5533	void **entry)
5534	{
5535	switch (mas->status) {
5536	case ma_active:
5537	goto active;
5538	case ma_start:
5539	break;
5540	case ma_pause:
5541	if (unlikely(mas->index <= min)) {
5542	mas->status = ma_underflow;
5543	return true;
5544	}
5545	mas->last = --mas->index;
5546	mas->status = ma_start;
5547	break;
5548	case ma_none:
5549	if (mas->index <= min)
5550	goto none;
5551
5552	mas->last = mas->index;
5553	mas->status = ma_start;
5554	break;
5555	case ma_overflow: /* user expects the mas to be one after where it is */
5556	if (unlikely(mas->index <= min)) {
5557	mas->status = ma_underflow;
5558	return true;
5559	}
5560
5561	mas->status = ma_active;
5562	break;
5563	case ma_underflow: /* user expects the mas to be one before where it is */
5564	if (unlikely(mas->index <= min))
5565	return true;
5566
5567	mas->status = ma_active;
5568	break;
5569	case ma_root:
5570	break;
5571	case ma_error:
5572	return true;
5573	}
5574
5575	if (mas_is_start(mas)) {
5576	/* First run or continue */
5577	if (mas->index < min)
5578	return true;
5579
5580	*entry = mas_walk(mas);
5581	if (*entry)
5582	return true;
5583	}
5584
5585	if (unlikely(mas_is_ptr(mas)))
5586	goto none;
5587
5588	if (unlikely(mas_is_none(mas))) {
5589	/*
5590	* Walked to the location, and there was nothing so the previous
5591	* location is 0.
5592	*/
5593	mas->last = mas->index = 0;
5594	mas->status = ma_root;
5595	*entry = mas_root(mas);
5596	return true;
5597	}
5598
5599	active:
5600	if (mas->index < min)
5601	return true;
5602
5603	return false;
5604
5605	none:
5606	mas->status = ma_none;
5607	return true;
5608	}
5609
5610	/**
5611	* mas_find_rev: On the first call, find the first non-null entry at or below
5612	* mas->index down to %min. Otherwise find the first non-null entry below
5613	* mas->index down to %min.
5614	* @mas: The maple state
5615	* @min: The minimum value to check.
5616	*
5617	* Must hold rcu_read_lock or the write lock.
5618	* If an entry exists, last and index are updated accordingly.
5619	* May set @mas->status to ma_underflow.
5620	*
5621	* Return: The entry or %NULL.
5622	*/
5623	void mas_find_rev(struct ma_state mas, unsigned long min)
5624	{
5625	void *entry = NULL;
5626
5627	mas_may_init_lock_check(mas);
5628	if (mas_find_rev_setup(mas, min, &entry))
5629	return entry;
5630
5631	/* Retries on dead nodes handled by mas_prev_slot */
5632	return mas_prev_slot(mas, min, false);
5633
5634	}
5635	EXPORT_SYMBOL_GPL(mas_find_rev);
5636
5637	/**
5638	* mas_find_range_rev: On the first call, find the first non-null entry at or
5639	* below mas->index down to %min. Otherwise advance to the previous slot after
5640	* mas->index down to %min.
5641	* @mas: The maple state
5642	* @min: The minimum value to check.
5643	*
5644	* Must hold rcu_read_lock or the write lock.
5645	* If an entry exists, last and index are updated accordingly.
5646	* May set @mas->status to ma_underflow.
5647	*
5648	* Return: The entry or %NULL.
5649	*/
5650	void mas_find_range_rev(struct ma_state mas, unsigned long min)
5651	{
5652	void *entry = NULL;
5653
5654	mas_may_init_lock_check(mas);
5655	if (mas_find_rev_setup(mas, min, &entry))
5656	return entry;
5657
5658	/* Retries on dead nodes handled by mas_prev_slot */
5659	return mas_prev_slot(mas, min, true);
5660	}
5661	EXPORT_SYMBOL_GPL(mas_find_range_rev);
5662
5663	/**
5664	* mas_erase() - Find the range in which index resides and erase the entire
5665	* range.
5666	* @mas: The maple state
5667	*
5668	* Must hold the write lock.
5669	* Searches for @mas->index, sets @mas->index and @mas->last to the range and
5670	* erases that range.
5671	*
5672	* Note that erase requires allocations and will use GFP_KERNEL \| __GFP_NOFAIL
5673	* to do so if necessary. If the allocation fails, the internal lock will be
5674	* dropped to retry. An externally locked tree must be protected by a lock that
5675	* allows blocking for this API.
5676	*
5677	* Return: the entry that was erased or %NULL, @mas->index and @mas->last are updated.
5678	*/
5679	void mas_erase(struct ma_state mas)
5680	{
5681	void *entry;
5682	unsigned long index = mas->index;
5683	MA_WR_STATE(wr_mas, mas, NULL);
5684
5685	/*
5686	* In low memory situations, the allocation is retried with the gfp flag
5687	* GFP_KERNEL \| __GFP_NOFAIL. The internal spinlock is dropped in
5688	* mas_nomem_nofail(), however the external lock is not dropped.
5689	*/
5690	if (mt_external_lock(mas->tree))
5691	might_alloc(GFP_KERNEL);
5692
5693	mas_make_walkable(mas);
5694	write_retry:
5695	entry = mas_state_walk(mas);
5696	if (!entry)
5697	goto out;
5698
5699	/* Must reset to ensure spanning writes of last slot are detected */
5700	mas_reset(mas);
5701	mas_wr_preallocate(&wr_mas, NULL);
5702	if (mas_nomem_nofail(mas, index, index))
5703	goto write_retry;
5704
5705	mas_wr_store_entry(&wr_mas);
5706	out:
5707	mas_destroy(mas);
5708	return entry;
5709	}
5710	EXPORT_SYMBOL_GPL(mas_erase);
5711
5712	/**
5713	* mas_nomem() - Check if there was an error allocating and do the allocation
5714	* if necessary.
5715	*
5716	* @mas: The maple state
5717	* @gfp: The GFP_FLAGS to use for allocations
5718	* Return: False on no memory. True otherwise (partial success as well)
5719	*/
5720	bool mas_nomem(struct ma_state *mas, gfp_t gfp)
5721	__must_hold(mas->tree->ma_lock)
5722	{
5723	if (likely(mas->node != MA_ERROR(-ENOMEM)))
5724	return false;
5725
5726	/* Allocations can fail, don't do this. */
5727	WARN_ON_ONCE(!gfpflags_allow_blocking(gfp) &&
5728	mt_external_lock(mas->tree));
5729
5730	if (gfpflags_allow_blocking(gfp) && !mt_external_lock(mas->tree)) {
5731	mtree_unlock(mas->tree);
5732	mas_alloc_nodes(mas, gfp);
5733	mtree_lock(mas->tree);
5734	} else {
5735	mas_alloc_nodes(mas, gfp);
5736	}
5737
5738	/*
5739	* Return false on zero forward progress. Partial allocations are kept
5740	* so the retry path will attempt to get the rest. The failure should
5741	* not happen as we try our best to reclaim. The user would need an
5742	* external lock with a non-blocking gfp in a low memory situation.
5743	*/
5744	if (!mas->sheaf && !mas->alloc)
5745	return false;
5746
5747	mas_reset(mas);
5748	return true;
5749	}
5750
5751	/**
5752	* mas_nomem_nofail() - Retry allocations with __GFP_NOFAIL, if the maple state
5753	* has stored the -ENOMEM error.
5754	* @mas: The maple state
5755	* @index: The start of the range for the @mas reset
5756	* @last: The end of the range for the @mas reset
5757	*
5758	* Return: false if @mas isn't in an -ENOMEM state. True if the allocation
5759	* happens, the state is reset. The internal lock will be dropped and external
5760	* locks must allow blocking.
5761	*/
5762	bool mas_nomem_nofail(struct ma_state *mas, unsigned long index,
5763	unsigned long last)
5764	__must_hold(mas->tree->ma_lock)
5765	{
5766	gfp_t gfp;
5767
5768	if (likely(mas->node != MA_ERROR(-ENOMEM)))
5769	return false;
5770
5771	gfp = GFP_KERNEL \| __GFP_NOFAIL;
5772	if (!mt_external_lock(mas->tree)) {
5773	mtree_unlock(mas->tree);
5774	mas_alloc_nodes(mas, gfp);
5775	mtree_lock(mas->tree);
5776	} else {
5777	mas_alloc_nodes(mas, gfp);
5778	}
5779
5780	mas_set_range(mas, index, last);
5781	return true;
5782	}
5783
5784	void __init maple_tree_init(void)
5785	{
5786	struct kmem_cache_args args = {
5787	.align = sizeof(struct maple_node),
5788	.sheaf_capacity = 32,
5789	};
5790
5791	maple_node_cache = kmem_cache_create("maple_node",
5792	sizeof(struct maple_node), &args,
5793	SLAB_PANIC);
5794	}
5795
5796	/**
5797	* mtree_load() - Load a value stored in a maple tree
5798	* @mt: The maple tree
5799	* @index: The index to load
5800	*
5801	* Return: the entry or %NULL
5802	*/
5803	void mtree_load(struct maple_tree mt, unsigned long index)
5804	{
5805	MA_STATE(mas, mt, index, index);
5806	void *entry;
5807
5808	trace_ma_read(TP_FCT, &mas);
5809	rcu_read_lock();
5810	retry:
5811	entry = mas_start(&mas);
5812	if (unlikely(mas_is_none(&mas)))
5813	goto unlock;
5814
5815	if (unlikely(mas_is_ptr(&mas))) {
5816	if (index)
5817	entry = NULL;
5818
5819	goto unlock;
5820	}
5821
5822	entry = mtree_lookup_walk(&mas);
5823	if (!entry && unlikely(mas_is_start(&mas)))
5824	goto retry;
5825	unlock:
5826	rcu_read_unlock();
5827	if (xa_is_zero(entry))
5828	return NULL;
5829
5830	return entry;
5831	}
5832	EXPORT_SYMBOL(mtree_load);
5833
5834	/**
5835	* mtree_store_range() - Store an entry at a given range.
5836	* @mt: The maple tree
5837	* @index: The start of the range
5838	* @last: The end of the range
5839	* @entry: The entry to store
5840	* @gfp: The GFP_FLAGS to use for allocations
5841	*
5842	* Return: 0 on success, -EINVAL on invalid request, -ENOMEM if memory could not
5843	* be allocated.
5844	*/
5845	int mtree_store_range(struct maple_tree *mt, unsigned long index,
5846	unsigned long last, void *entry, gfp_t gfp)
5847	{
5848	MA_STATE(mas, mt, index, last);
5849	int ret = 0;
5850
5851	trace_ma_write(TP_FCT, &mas, 0, entry);
5852	if (WARN_ON_ONCE(xa_is_advanced(entry)))
5853	return -EINVAL;
5854
5855	if (index > last)
5856	return -EINVAL;
5857
5858	mtree_lock(mt);
5859	ret = mas_store_gfp(&mas, entry, gfp);
5860	mtree_unlock(mt);
5861
5862	return ret;
5863	}
5864	EXPORT_SYMBOL(mtree_store_range);
5865
5866	/**
5867	* mtree_store() - Store an entry at a given index.
5868	* @mt: The maple tree
5869	* @index: The index to store the value
5870	* @entry: The entry to store
5871	* @gfp: The GFP_FLAGS to use for allocations
5872	*
5873	* Return: 0 on success, -EINVAL on invalid request, -ENOMEM if memory could not
5874	* be allocated.
5875	*/
5876	int mtree_store(struct maple_tree mt, unsigned long index, void entry,
5877	gfp_t gfp)
5878	{
5879	return mtree_store_range(mt, index, index, entry, gfp);
5880	}
5881	EXPORT_SYMBOL(mtree_store);
5882
5883	/**
5884	* mtree_insert_range() - Insert an entry from [first, last] at a given range
5885	* if there is no value.
5886	* @mt: The maple tree
5887	* @first: The start of the range
5888	* @last: The end of the range (inclusive)
5889	* @entry: The entry to store
5890	* @gfp: The GFP_FLAGS to use for allocations.
5891	*
5892	* Note that @last is inclusive. That is, @last = @first + length - 1;
5893	*
5894	* Return: 0 on success, -EEXISTS if the range is occupied, -EINVAL on invalid
5895	* request, -ENOMEM if memory could not be allocated.
5896	*/
5897	int mtree_insert_range(struct maple_tree *mt, unsigned long first,
5898	unsigned long last, void *entry, gfp_t gfp)
5899	{
5900	MA_STATE(ms, mt, first, last);
5901	int ret = 0;
5902
5903	if (WARN_ON_ONCE(xa_is_advanced(entry)))
5904	return -EINVAL;
5905
5906	if (first > last)
5907	return -EINVAL;
5908
5909	mtree_lock(mt);
5910	retry:
5911	mas_insert(&ms, entry);
5912	if (mas_nomem(&ms, gfp))
5913	goto retry;
5914
5915	mtree_unlock(mt);
5916	if (mas_is_err(&ms))
5917	ret = xa_err(ms.node);
5918
5919	mas_destroy(&ms);
5920	return ret;
5921	}
5922	EXPORT_SYMBOL(mtree_insert_range);
5923
5924	/**
5925	* mtree_insert() - Insert an entry at a given index if there is no value.
5926	* @mt: The maple tree
5927	* @index : The index to store the value
5928	* @entry: The entry to store
5929	* @gfp: The GFP_FLAGS to use for allocations.
5930	*
5931	* Return: 0 on success, -EEXISTS if the range is occupied, -EINVAL on invalid
5932	* request, -ENOMEM if memory could not be allocated.
5933	*/
5934	int mtree_insert(struct maple_tree mt, unsigned long index, void entry,
5935	gfp_t gfp)
5936	{
5937	return mtree_insert_range(mt, index, index, entry, gfp);
5938	}
5939	EXPORT_SYMBOL(mtree_insert);
5940
5941	int mtree_alloc_range(struct maple_tree mt, unsigned long startp,
5942	void *entry, unsigned long size, unsigned long min,
5943	unsigned long max, gfp_t gfp)
5944	{
5945	int ret = 0;
5946
5947	MA_STATE(mas, mt, 0, 0);
5948	if (!mt_is_alloc(mt))
5949	return -EINVAL;
5950
5951	if (WARN_ON_ONCE(mt_is_reserved(entry)))
5952	return -EINVAL;
5953
5954	mtree_lock(mt);
5955	retry:
5956	ret = mas_empty_area(&mas, min, max, size);
5957	if (ret)
5958	goto unlock;
5959
5960	mas_insert(&mas, entry);
5961	/*
5962	* mas_nomem() may release the lock, causing the allocated area
5963	* to be unavailable, so try to allocate a free area again.
5964	*/
5965	if (mas_nomem(&mas, gfp))
5966	goto retry;
5967
5968	if (mas_is_err(&mas))
5969	ret = xa_err(mas.node);
5970	else
5971	*startp = mas.index;
5972
5973	unlock:
5974	mtree_unlock(mt);
5975	mas_destroy(&mas);
5976	return ret;
5977	}
5978	EXPORT_SYMBOL(mtree_alloc_range);
5979
5980	/**
5981	* mtree_alloc_cyclic() - Find somewhere to store this entry in the tree.
5982	* @mt: The maple tree.
5983	* @startp: Pointer to ID.
5984	* @range_lo: Lower bound of range to search.
5985	* @range_hi: Upper bound of range to search.
5986	* @entry: The entry to store.
5987	* @next: Pointer to next ID to allocate.
5988	* @gfp: The GFP_FLAGS to use for allocations.
5989	*
5990	* Finds an empty entry in @mt after @next, stores the new index into
5991	* the @id pointer, stores the entry at that index, then updates @next.
5992	*
5993	* @mt must be initialized with the MT_FLAGS_ALLOC_RANGE flag.
5994	*
5995	* Context: Any context. Takes and releases the mt.lock. May sleep if
5996	* the @gfp flags permit.
5997	*
5998	* Return: 0 if the allocation succeeded without wrapping, 1 if the
5999	* allocation succeeded after wrapping, -ENOMEM if memory could not be
6000	* allocated, -EINVAL if @mt cannot be used, or -EBUSY if there are no
6001	* free entries.
6002	*/
6003	int mtree_alloc_cyclic(struct maple_tree mt, unsigned long startp,
6004	void *entry, unsigned long range_lo, unsigned long range_hi,
6005	unsigned long *next, gfp_t gfp)
6006	{
6007	int ret;
6008
6009	MA_STATE(mas, mt, 0, 0);
6010
6011	if (!mt_is_alloc(mt))
6012	return -EINVAL;
6013	if (WARN_ON_ONCE(mt_is_reserved(entry)))
6014	return -EINVAL;
6015	mtree_lock(mt);
6016	ret = mas_alloc_cyclic(&mas, startp, entry, range_lo, range_hi,
6017	next, gfp);
6018	mtree_unlock(mt);
6019	return ret;
6020	}
6021	EXPORT_SYMBOL(mtree_alloc_cyclic);
6022
6023	int mtree_alloc_rrange(struct maple_tree mt, unsigned long startp,
6024	void *entry, unsigned long size, unsigned long min,
6025	unsigned long max, gfp_t gfp)
6026	{
6027	int ret = 0;
6028
6029	MA_STATE(mas, mt, 0, 0);
6030	if (!mt_is_alloc(mt))
6031	return -EINVAL;
6032
6033	if (WARN_ON_ONCE(mt_is_reserved(entry)))
6034	return -EINVAL;
6035
6036	mtree_lock(mt);
6037	retry:
6038	ret = mas_empty_area_rev(&mas, min, max, size);
6039	if (ret)
6040	goto unlock;
6041
6042	mas_insert(&mas, entry);
6043	/*
6044	* mas_nomem() may release the lock, causing the allocated area
6045	* to be unavailable, so try to allocate a free area again.
6046	*/
6047	if (mas_nomem(&mas, gfp))
6048	goto retry;
6049
6050	if (mas_is_err(&mas))
6051	ret = xa_err(mas.node);
6052	else
6053	*startp = mas.index;
6054
6055	unlock:
6056	mtree_unlock(mt);
6057	mas_destroy(&mas);
6058	return ret;
6059	}
6060	EXPORT_SYMBOL(mtree_alloc_rrange);
6061
6062	/**
6063	* mtree_erase() - Find an index and erase the entire range.
6064	* @mt: The maple tree
6065	* @index: The index to erase
6066	*
6067	* Erasing is the same as a walk to an entry then a store of a NULL to that
6068	* ENTIRE range. In fact, it is implemented as such using the advanced API.
6069	*
6070	* Note that erase requires allocations and will use GFP_KERNEL \| __GFP_NOFAIL
6071	* to do so if necessary. If the allocation fails, the internal lock will be
6072	* dropped to retry.
6073	*
6074	* Return: The entry stored at the @index or %NULL
6075	*/
6076	void mtree_erase(struct maple_tree mt, unsigned long index)
6077	{
6078	void *entry = NULL;
6079
6080	MA_STATE(mas, mt, index, index);
6081	trace_ma_op(TP_FCT, &mas);
6082
6083	might_alloc(GFP_KERNEL);
6084	mtree_lock(mt);
6085	entry = mas_erase(&mas);
6086	mtree_unlock(mt);
6087
6088	return entry;
6089	}
6090	EXPORT_SYMBOL(mtree_erase);
6091
6092	/*
6093	* mas_dup_free() - Free an incomplete duplication of a tree.
6094	* @mas: The maple state of a incomplete tree.
6095	*
6096	* The parameter @mas->node passed in indicates that the allocation failed on
6097	* this node. This function frees all nodes starting from @mas->node in the
6098	* reverse order of mas_dup_build(). There is no need to hold the source tree
6099	* lock at this time.
6100	*/
6101	static void mas_dup_free(struct ma_state *mas)
6102	{
6103	struct maple_node *node;
6104	enum maple_type type;
6105	void __rcu **slots;
6106	unsigned char count, i;
6107
6108	/* Maybe the first node allocation failed. */
6109	if (mas_is_none(mas))
6110	return;
6111
6112	while (!mte_is_root(mas->node)) {
6113	mas_ascend(mas);
6114	if (mas->offset) {
6115	mas->offset--;
6116	do {
6117	mas_descend(mas);
6118	mas->offset = mas_data_end(mas);
6119	} while (!mte_is_leaf(mas->node));
6120
6121	mas_ascend(mas);
6122	}
6123
6124	node = mte_to_node(mas->node);
6125	type = mte_node_type(mas->node);
6126	slots = ma_slots(node, type);
6127	count = mas_data_end(mas) + 1;
6128	for (i = 0; i < count; i++)
6129	((unsigned long *)slots)[i] &= ~MAPLE_NODE_MASK;
6130	mt_free_bulk(count, slots);
6131	}
6132
6133	node = mte_to_node(mas->node);
6134	kfree(node);
6135	}
6136
6137	/*
6138	* mas_copy_node() - Copy a maple node and replace the parent.
6139	* @mas: The maple state of source tree.
6140	* @new_mas: The maple state of new tree.
6141	* @parent: The parent of the new node.
6142	*
6143	* Copy @mas->node to @new_mas->node, set @parent to be the parent of
6144	* @new_mas->node. If memory allocation fails, @mas is set to -ENOMEM.
6145	*/
6146	static inline void mas_copy_node(struct ma_state mas, struct ma_state new_mas,
6147	struct maple_pnode *parent)
6148	{
6149	struct maple_node *node = mte_to_node(mas->node);
6150	struct maple_node *new_node = mte_to_node(new_mas->node);
6151	unsigned long val;
6152
6153	/* Copy the node completely. */
6154	memcpy(new_node, node, sizeof(struct maple_node));
6155	/* Update the parent node pointer. */
6156	val = (unsigned long)node->parent & MAPLE_NODE_MASK;
6157	new_node->parent = ma_parent_ptr(val \| (unsigned long)parent);
6158	}
6159
6160	/*
6161	* mas_dup_alloc() - Allocate child nodes for a maple node.
6162	* @mas: The maple state of source tree.
6163	* @new_mas: The maple state of new tree.
6164	* @gfp: The GFP_FLAGS to use for allocations.
6165	*
6166	* This function allocates child nodes for @new_mas->node during the duplication
6167	* process. If memory allocation fails, @mas is set to -ENOMEM.
6168	*/
6169	static inline void mas_dup_alloc(struct ma_state mas, struct ma_state new_mas,
6170	gfp_t gfp)
6171	{
6172	struct maple_node *node = mte_to_node(mas->node);
6173	struct maple_node *new_node = mte_to_node(new_mas->node);
6174	enum maple_type type;
6175	unsigned char count, i;
6176	void __rcu **slots;
6177	void __rcu **new_slots;
6178	unsigned long val;
6179
6180	/* Allocate memory for child nodes. */
6181	type = mte_node_type(mas->node);
6182	new_slots = ma_slots(new_node, type);
6183	count = mas->node_request = mas_data_end(mas) + 1;
6184	mas_alloc_nodes(mas, gfp);
6185	if (unlikely(mas_is_err(mas)))
6186	return;
6187
6188	slots = ma_slots(node, type);
6189	for (i = 0; i < count; i++) {
6190	val = (unsigned long)mt_slot_locked(mas->tree, slots, i);
6191	val &= MAPLE_NODE_MASK;
6192	/*
6193	* Warning, see rcu_assign_pointer() documentation. Since this
6194	* is a duplication of a tree, there are no readers walking the
6195	* tree until after the rcu_assign_pointer() call in
6196	* mas_dup_build().
6197	*/
6198	RCU_INIT_POINTER(new_slots[i],
6199	ma_mnode_ptr((unsigned long)mas_pop_node(mas) \|
6200	val));
6201	}
6202	}
6203
6204	/*
6205	* mas_dup_build() - Build a new maple tree from a source tree
6206	* @mas: The maple state of source tree, need to be in MAS_START state.
6207	* @new_mas: The maple state of new tree, need to be in MAS_START state.
6208	* @gfp: The GFP_FLAGS to use for allocations.
6209	*
6210	* This function builds a new tree in DFS preorder. If the memory allocation
6211	* fails, the error code -ENOMEM will be set in @mas, and @new_mas points to the
6212	* last node. mas_dup_free() will free the incomplete duplication of a tree.
6213	*
6214	* Note that the attributes of the two trees need to be exactly the same, and the
6215	* new tree needs to be empty, otherwise -EINVAL will be set in @mas.
6216	*/
6217	static inline void mas_dup_build(struct ma_state mas, struct ma_state new_mas,
6218	gfp_t gfp)
6219	{
6220	struct maple_node *node;
6221	struct maple_pnode *parent = NULL;
6222	struct maple_enode *root;
6223	enum maple_type type;
6224
6225	if (unlikely(mt_attr(mas->tree) != mt_attr(new_mas->tree)) \|\|
6226	unlikely(!mtree_empty(new_mas->tree))) {
6227	mas_set_err(mas, -EINVAL);
6228	return;
6229	}
6230
6231	root = mas_start(mas);
6232	if (mas_is_ptr(mas) \|\| mas_is_none(mas))
6233	goto set_new_tree;
6234
6235	node = mt_alloc_one(gfp);
6236	if (!node) {
6237	new_mas->status = ma_none;
6238	mas_set_err(mas, -ENOMEM);
6239	return;
6240	}
6241
6242	type = mte_node_type(mas->node);
6243	root = mt_mk_node(node, type);
6244	new_mas->node = root;
6245	new_mas->min = 0;
6246	new_mas->max = ULONG_MAX;
6247	root = mte_mk_root(root);
6248	while (1) {
6249	mas_copy_node(mas, new_mas, parent);
6250	if (!mte_is_leaf(mas->node)) {
6251	/* Only allocate child nodes for non-leaf nodes. */
6252	mas_dup_alloc(mas, new_mas, gfp);
6253	if (unlikely(mas_is_err(mas)))
6254	goto empty_mas;
6255	} else {
6256	/*
6257	* This is the last leaf node and duplication is
6258	* completed.
6259	*/
6260	if (mas->max == ULONG_MAX)
6261	goto done;
6262
6263	/* This is not the last leaf node and needs to go up. */
6264	do {
6265	mas_ascend(mas);
6266	mas_ascend(new_mas);
6267	} while (mas->offset == mas_data_end(mas));
6268
6269	/* Move to the next subtree. */
6270	mas->offset++;
6271	new_mas->offset++;
6272	}
6273
6274	mas_descend(mas);
6275	parent = ma_parent_ptr(mte_to_node(new_mas->node));
6276	mas_descend(new_mas);
6277	mas->offset = 0;
6278	new_mas->offset = 0;
6279	}
6280	done:
6281	/* Specially handle the parent of the root node. */
6282	mte_to_node(root)->parent = ma_parent_ptr(mas_tree_parent(new_mas));
6283	set_new_tree:
6284	/* Make them the same height */
6285	new_mas->tree->ma_flags = mas->tree->ma_flags;
6286	rcu_assign_pointer(new_mas->tree->ma_root, root);
6287	empty_mas:
6288	mas_empty_nodes(mas);
6289	}
6290
6291	/**
6292	* __mt_dup(): Duplicate an entire maple tree
6293	* @mt: The source maple tree
6294	* @new: The new maple tree
6295	* @gfp: The GFP_FLAGS to use for allocations
6296	*
6297	* This function duplicates a maple tree in Depth-First Search (DFS) pre-order
6298	* traversal. It uses memcpy() to copy nodes in the source tree and allocate
6299	* new child nodes in non-leaf nodes. The new node is exactly the same as the
6300	* source node except for all the addresses stored in it. It will be faster than
6301	* traversing all elements in the source tree and inserting them one by one into
6302	* the new tree.
6303	* The user needs to ensure that the attributes of the source tree and the new
6304	* tree are the same, and the new tree needs to be an empty tree, otherwise
6305	* -EINVAL will be returned.
6306	* Note that the user needs to manually lock the source tree and the new tree.
6307	*
6308	* Return: 0 on success, -ENOMEM if memory could not be allocated, -EINVAL If
6309	* the attributes of the two trees are different or the new tree is not an empty
6310	* tree.
6311	*/
6312	int __mt_dup(struct maple_tree mt, struct maple_tree new, gfp_t gfp)
6313	{
6314	int ret = 0;
6315	MA_STATE(mas, mt, 0, 0);
6316	MA_STATE(new_mas, new, 0, 0);
6317
6318	mas_dup_build(&mas, &new_mas, gfp);
6319	if (unlikely(mas_is_err(&mas))) {
6320	ret = xa_err(mas.node);
6321	if (ret == -ENOMEM)
6322	mas_dup_free(&new_mas);
6323	}
6324
6325	return ret;
6326	}
6327	EXPORT_SYMBOL(__mt_dup);
6328
6329	/**
6330	* mtree_dup(): Duplicate an entire maple tree
6331	* @mt: The source maple tree
6332	* @new: The new maple tree
6333	* @gfp: The GFP_FLAGS to use for allocations
6334	*
6335	* This function duplicates a maple tree in Depth-First Search (DFS) pre-order
6336	* traversal. It uses memcpy() to copy nodes in the source tree and allocate
6337	* new child nodes in non-leaf nodes. The new node is exactly the same as the
6338	* source node except for all the addresses stored in it. It will be faster than
6339	* traversing all elements in the source tree and inserting them one by one into
6340	* the new tree.
6341	* The user needs to ensure that the attributes of the source tree and the new
6342	* tree are the same, and the new tree needs to be an empty tree, otherwise
6343	* -EINVAL will be returned.
6344	*
6345	* Return: 0 on success, -ENOMEM if memory could not be allocated, -EINVAL If
6346	* the attributes of the two trees are different or the new tree is not an empty
6347	* tree.
6348	*/
6349	int mtree_dup(struct maple_tree mt, struct maple_tree new, gfp_t gfp)
6350	{
6351	int ret = 0;
6352	MA_STATE(mas, mt, 0, 0);
6353	MA_STATE(new_mas, new, 0, 0);
6354
6355	mas_lock(&new_mas);
6356	mas_lock_nested(&mas, SINGLE_DEPTH_NESTING);
6357	mas_dup_build(&mas, &new_mas, gfp);
6358	mas_unlock(&mas);
6359	if (unlikely(mas_is_err(&mas))) {
6360	ret = xa_err(mas.node);
6361	if (ret == -ENOMEM)
6362	mas_dup_free(&new_mas);
6363	}
6364
6365	mas_unlock(&new_mas);
6366	return ret;
6367	}
6368	EXPORT_SYMBOL(mtree_dup);
6369
6370	/**
6371	* __mt_destroy() - Walk and free all nodes of a locked maple tree.
6372	* @mt: The maple tree
6373	*
6374	* Note: Does not handle locking.
6375	*/
6376	void __mt_destroy(struct maple_tree *mt)
6377	{
6378	void *root = mt_root_locked(mt);
6379
6380	rcu_assign_pointer(mt->ma_root, NULL);
6381	if (xa_is_node(root))
6382	mte_destroy_walk(root, mt);
6383
6384	mt->ma_flags = mt_attr(mt);
6385	}
6386	EXPORT_SYMBOL_GPL(__mt_destroy);
6387
6388	/**
6389	* mtree_destroy() - Destroy a maple tree
6390	* @mt: The maple tree
6391	*
6392	* Frees all resources used by the tree. Handles locking.
6393	*/
6394	void mtree_destroy(struct maple_tree *mt)
6395	{
6396	mtree_lock(mt);
6397	__mt_destroy(mt);
6398	mtree_unlock(mt);
6399	}
6400	EXPORT_SYMBOL(mtree_destroy);
6401
6402	/**
6403	* mt_find() - Search from the start up until an entry is found.
6404	* @mt: The maple tree
6405	* @index: Pointer which contains the start location of the search
6406	* @max: The maximum value of the search range
6407	*
6408	* Takes RCU read lock internally to protect the search, which does not
6409	* protect the returned pointer after dropping RCU read lock.
6410	* See also: Documentation/core-api/maple_tree.rst
6411	*
6412	* In case that an entry is found @index is updated to point to the next
6413	* possible entry independent whether the found entry is occupying a
6414	* single index or a range if indices.
6415	*
6416	* Return: The entry at or after the @index or %NULL
6417	*/
6418	void mt_find(struct maple_tree mt, unsigned long *index, unsigned long max)
6419	{
6420	MA_STATE(mas, mt, index, index);
6421	void *entry;
6422	#ifdef CONFIG_DEBUG_MAPLE_TREE
6423	unsigned long copy = *index;
6424	#endif
6425
6426	trace_ma_read(TP_FCT, &mas);
6427
6428	if ((*index) > max)
6429	return NULL;
6430
6431	rcu_read_lock();
6432	retry:
6433	entry = mas_state_walk(&mas);
6434	if (mas_is_start(&mas))
6435	goto retry;
6436
6437	if (unlikely(xa_is_zero(entry)))
6438	entry = NULL;
6439
6440	if (entry)
6441	goto unlock;
6442
6443	while (mas_is_active(&mas) && (mas.last < max)) {
6444	entry = mas_next_slot(&mas, max, false);
6445	if (likely(entry && !xa_is_zero(entry)))
6446	break;
6447	}
6448
6449	if (unlikely(xa_is_zero(entry)))
6450	entry = NULL;
6451	unlock:
6452	rcu_read_unlock();
6453	if (likely(entry)) {
6454	*index = mas.last + 1;
6455	#ifdef CONFIG_DEBUG_MAPLE_TREE
6456	if (MT_WARN_ON(mt, (index) && ((index) <= copy)))
6457	pr_err("index not increased! %lx <= %lx\n",
6458	*index, copy);
6459	#endif
6460	}
6461
6462	return entry;
6463	}
6464	EXPORT_SYMBOL(mt_find);
6465
6466	/**
6467	* mt_find_after() - Search from the start up until an entry is found.
6468	* @mt: The maple tree
6469	* @index: Pointer which contains the start location of the search
6470	* @max: The maximum value to check
6471	*
6472	* Same as mt_find() except that it checks @index for 0 before
6473	* searching. If @index == 0, the search is aborted. This covers a wrap
6474	* around of @index to 0 in an iterator loop.
6475	*
6476	* Return: The entry at or after the @index or %NULL
6477	*/
6478	void mt_find_after(struct maple_tree mt, unsigned long *index,
6479	unsigned long max)
6480	{
6481	if (!(*index))
6482	return NULL;
6483
6484	return mt_find(mt, index, max);
6485	}
6486	EXPORT_SYMBOL(mt_find_after);
6487
6488	#ifdef CONFIG_DEBUG_MAPLE_TREE
6489	atomic_t maple_tree_tests_run;
6490	EXPORT_SYMBOL_GPL(maple_tree_tests_run);
6491	atomic_t maple_tree_tests_passed;
6492	EXPORT_SYMBOL_GPL(maple_tree_tests_passed);
6493
6494	#ifndef __KERNEL__
6495	extern void kmem_cache_set_non_kernel(struct kmem_cache *, unsigned int);
6496	void mt_set_non_kernel(unsigned int val)
6497	{
6498	kmem_cache_set_non_kernel(maple_node_cache, val);
6499	}
6500
6501	extern void kmem_cache_set_callback(struct kmem_cache *cachep,
6502	void (callback)(void ));
6503	void mt_set_callback(void (callback)(void ))
6504	{
6505	kmem_cache_set_callback(maple_node_cache, callback);
6506	}
6507
6508	extern void kmem_cache_set_private(struct kmem_cache cachep, void private);
6509	void mt_set_private(void *private)
6510	{
6511	kmem_cache_set_private(maple_node_cache, private);
6512	}
6513
6514	extern unsigned long kmem_cache_get_alloc(struct kmem_cache *);
6515	unsigned long mt_get_alloc_size(void)
6516	{
6517	return kmem_cache_get_alloc(maple_node_cache);
6518	}
6519
6520	extern void kmem_cache_zero_nr_tallocated(struct kmem_cache *);
6521	void mt_zero_nr_tallocated(void)
6522	{
6523	kmem_cache_zero_nr_tallocated(maple_node_cache);
6524	}
6525
6526	extern unsigned int kmem_cache_nr_tallocated(struct kmem_cache *);
6527	unsigned int mt_nr_tallocated(void)
6528	{
6529	return kmem_cache_nr_tallocated(maple_node_cache);
6530	}
6531
6532	extern unsigned int kmem_cache_nr_allocated(struct kmem_cache *);
6533	unsigned int mt_nr_allocated(void)
6534	{
6535	return kmem_cache_nr_allocated(maple_node_cache);
6536	}
6537
6538	void mt_cache_shrink(void)
6539	{
6540	}
6541	#else
6542	/*
6543	* mt_cache_shrink() - For testing, don't use this.
6544	*
6545	* Certain testcases can trigger an OOM when combined with other memory
6546	* debugging configuration options. This function is used to reduce the
6547	* possibility of an out of memory even due to kmem_cache objects remaining
6548	* around for longer than usual.
6549	*/
6550	void mt_cache_shrink(void)
6551	{
6552	kmem_cache_shrink(maple_node_cache);
6553
6554	}
6555	EXPORT_SYMBOL_GPL(mt_cache_shrink);
6556
6557	#endif /* not defined __KERNEL__ */
6558	/*
6559	* mas_get_slot() - Get the entry in the maple state node stored at @offset.
6560	* @mas: The maple state
6561	* @offset: The offset into the slot array to fetch.
6562	*
6563	* Return: The entry stored at @offset.
6564	*/
6565	static inline struct maple_enode mas_get_slot(struct ma_state mas,
6566	unsigned char offset)
6567	{
6568	return mas_slot(mas, ma_slots(mas_mn(mas), mte_node_type(mas->node)),
6569	offset);
6570	}
6571
6572	/* Depth first search, post-order */
6573	static void mas_dfs_postorder(struct ma_state *mas, unsigned long max)
6574	{
6575
6576	struct maple_enode p, mn = mas->node;
6577	unsigned long p_min, p_max;
6578
6579	mas_next_node(mas, mas_mn(mas), max);
6580	if (!mas_is_overflow(mas))
6581	return;
6582
6583	if (mte_is_root(mn))
6584	return;
6585
6586	mas->node = mn;
6587	mas_ascend(mas);
6588	do {
6589	p = mas->node;
6590	p_min = mas->min;
6591	p_max = mas->max;
6592	mas_prev_node(mas, 0);
6593	} while (!mas_is_underflow(mas));
6594
6595	mas->node = p;
6596	mas->max = p_max;
6597	mas->min = p_min;
6598	}
6599
6600	/* Tree validations */
6601	static void mt_dump_node(const struct maple_tree mt, void entry,
6602	unsigned long min, unsigned long max, unsigned int depth,
6603	enum mt_dump_format format);
6604	static void mt_dump_range(unsigned long min, unsigned long max,
6605	unsigned int depth, enum mt_dump_format format)
6606	{
6607	static const char spaces[] = " ";
6608
6609	switch (format) {
6610	case mt_dump_hex:
6611	if (min == max)
6612	pr_info("%.s%lx: ", depth 2, spaces, min);
6613	else
6614	pr_info("%.s%lx-%lx: ", depth 2, spaces, min, max);
6615	break;
6616	case mt_dump_dec:
6617	if (min == max)
6618	pr_info("%.s%lu: ", depth 2, spaces, min);
6619	else
6620	pr_info("%.s%lu-%lu: ", depth 2, spaces, min, max);
6621	}
6622	}
6623
6624	static void mt_dump_entry(void *entry, unsigned long min, unsigned long max,
6625	unsigned int depth, enum mt_dump_format format)
6626	{
6627	mt_dump_range(min, max, depth, format);
6628
6629	if (xa_is_value(entry))
6630	pr_cont("value %ld (0x%lx) [" PTR_FMT "]\n", xa_to_value(entry),
6631	xa_to_value(entry), entry);
6632	else if (xa_is_zero(entry))
6633	pr_cont("zero (%ld)\n", xa_to_internal(entry));
6634	else if (mt_is_reserved(entry))
6635	pr_cont("UNKNOWN ENTRY (" PTR_FMT ")\n", entry);
6636	else
6637	pr_cont(PTR_FMT "\n", entry);
6638	}
6639
6640	static void mt_dump_range64(const struct maple_tree mt, void entry,
6641	unsigned long min, unsigned long max, unsigned int depth,
6642	enum mt_dump_format format)
6643	{
6644	struct maple_range_64 *node = &mte_to_node(entry)->mr64;
6645	bool leaf = mte_is_leaf(entry);
6646	unsigned long first = min;
6647	int i;
6648
6649	pr_cont(" contents: ");
6650	for (i = 0; i < MAPLE_RANGE64_SLOTS - 1; i++) {
6651	switch (format) {
6652	case mt_dump_hex:
6653	pr_cont(PTR_FMT " %lX ", node->slot[i], node->pivot[i]);
6654	break;
6655	case mt_dump_dec:
6656	pr_cont(PTR_FMT " %lu ", node->slot[i], node->pivot[i]);
6657	}
6658	}
6659	pr_cont(PTR_FMT "\n", node->slot[i]);
6660	for (i = 0; i < MAPLE_RANGE64_SLOTS; i++) {
6661	unsigned long last = max;
6662
6663	if (i < (MAPLE_RANGE64_SLOTS - 1))
6664	last = node->pivot[i];
6665	else if (!node->slot[i] && max != mt_node_max(entry))
6666	break;
6667	if (last == 0 && i > 0)
6668	break;
6669	if (leaf)
6670	mt_dump_entry(mt_slot(mt, node->slot, i),
6671	first, last, depth + 1, format);
6672	else if (node->slot[i])
6673	mt_dump_node(mt, mt_slot(mt, node->slot, i),
6674	first, last, depth + 1, format);
6675
6676	if (last == max)
6677	break;
6678	if (last > max) {
6679	switch (format) {
6680	case mt_dump_hex:
6681	pr_err("node " PTR_FMT " last (%lx) > max (%lx) at pivot %d!\n",
6682	node, last, max, i);
6683	break;
6684	case mt_dump_dec:
6685	pr_err("node " PTR_FMT " last (%lu) > max (%lu) at pivot %d!\n",
6686	node, last, max, i);
6687	}
6688	}
6689	first = last + 1;
6690	}
6691	}
6692
6693	static void mt_dump_arange64(const struct maple_tree mt, void entry,
6694	unsigned long min, unsigned long max, unsigned int depth,
6695	enum mt_dump_format format)
6696	{
6697	struct maple_arange_64 *node = &mte_to_node(entry)->ma64;
6698	unsigned long first = min;
6699	int i;
6700
6701	pr_cont(" contents: ");
6702	for (i = 0; i < MAPLE_ARANGE64_SLOTS; i++) {
6703	switch (format) {
6704	case mt_dump_hex:
6705	pr_cont("%lx ", node->gap[i]);
6706	break;
6707	case mt_dump_dec:
6708	pr_cont("%lu ", node->gap[i]);
6709	}
6710	}
6711	pr_cont("\| %02X %02X\| ", node->meta.end, node->meta.gap);
6712	for (i = 0; i < MAPLE_ARANGE64_SLOTS - 1; i++) {
6713	switch (format) {
6714	case mt_dump_hex:
6715	pr_cont(PTR_FMT " %lX ", node->slot[i], node->pivot[i]);
6716	break;
6717	case mt_dump_dec:
6718	pr_cont(PTR_FMT " %lu ", node->slot[i], node->pivot[i]);
6719	}
6720	}
6721	pr_cont(PTR_FMT "\n", node->slot[i]);
6722	for (i = 0; i < MAPLE_ARANGE64_SLOTS; i++) {
6723	unsigned long last = max;
6724
6725	if (i < (MAPLE_ARANGE64_SLOTS - 1))
6726	last = node->pivot[i];
6727	else if (!node->slot[i])
6728	break;
6729	if (last == 0 && i > 0)
6730	break;
6731	if (node->slot[i])
6732	mt_dump_node(mt, mt_slot(mt, node->slot, i),
6733	first, last, depth + 1, format);
6734
6735	if (last == max)
6736	break;
6737	if (last > max) {
6738	switch (format) {
6739	case mt_dump_hex:
6740	pr_err("node " PTR_FMT " last (%lx) > max (%lx) at pivot %d!\n",
6741	node, last, max, i);
6742	break;
6743	case mt_dump_dec:
6744	pr_err("node " PTR_FMT " last (%lu) > max (%lu) at pivot %d!\n",
6745	node, last, max, i);
6746	}
6747	}
6748	first = last + 1;
6749	}
6750	}
6751
6752	static void mt_dump_node(const struct maple_tree mt, void entry,
6753	unsigned long min, unsigned long max, unsigned int depth,
6754	enum mt_dump_format format)
6755	{
6756	struct maple_node *node = mte_to_node(entry);
6757	unsigned int type = mte_node_type(entry);
6758	unsigned int i;
6759
6760	mt_dump_range(min, max, depth, format);
6761
6762	pr_cont("node " PTR_FMT " depth %d type %d parent " PTR_FMT, node,
6763	depth, type, node ? node->parent : NULL);
6764	switch (type) {
6765	case maple_dense:
6766	pr_cont("\n");
6767	for (i = 0; i < MAPLE_NODE_SLOTS; i++) {
6768	if (min + i > max)
6769	pr_cont("OUT OF RANGE: ");
6770	mt_dump_entry(mt_slot(mt, node->slot, i),
6771	min + i, min + i, depth, format);
6772	}
6773	break;
6774	case maple_leaf_64:
6775	case maple_range_64:
6776	mt_dump_range64(mt, entry, min, max, depth, format);
6777	break;
6778	case maple_arange_64:
6779	mt_dump_arange64(mt, entry, min, max, depth, format);
6780	break;
6781
6782	default:
6783	pr_cont(" UNKNOWN TYPE\n");
6784	}
6785	}
6786
6787	void mt_dump(const struct maple_tree *mt, enum mt_dump_format format)
6788	{
6789	void *entry = rcu_dereference_check(mt->ma_root, mt_locked(mt));
6790
6791	pr_info("maple_tree(" PTR_FMT ") flags %X, height %u root " PTR_FMT "\n",
6792	mt, mt->ma_flags, mt_height(mt), entry);
6793	if (xa_is_node(entry))
6794	mt_dump_node(mt, entry, 0, mt_node_max(entry), 0, format);
6795	else if (entry)
6796	mt_dump_entry(entry, 0, 0, 0, format);
6797	else
6798	pr_info("(empty)\n");
6799	}
6800	EXPORT_SYMBOL_GPL(mt_dump);
6801
6802	/*
6803	* Calculate the maximum gap in a node and check if that's what is reported in
6804	* the parent (unless root).
6805	*/
6806	static void mas_validate_gaps(struct ma_state *mas)
6807	{
6808	struct maple_enode *mte = mas->node;
6809	struct maple_node p_mn, node = mte_to_node(mte);
6810	enum maple_type mt = mte_node_type(mas->node);
6811	unsigned long gap = 0, max_gap = 0;
6812	unsigned long p_end, p_start = mas->min;
6813	unsigned char p_slot, offset;
6814	unsigned long *gaps = NULL;
6815	unsigned long *pivots = ma_pivots(node, mt);
6816	unsigned int i;
6817
6818	if (ma_is_dense(mt)) {
6819	for (i = 0; i < mt_slot_count(mte); i++) {
6820	if (mas_get_slot(mas, i)) {
6821	if (gap > max_gap)
6822	max_gap = gap;
6823	gap = 0;
6824	continue;
6825	}
6826	gap++;
6827	}
6828	goto counted;
6829	}
6830
6831	gaps = ma_gaps(node, mt);
6832	for (i = 0; i < mt_slot_count(mte); i++) {
6833	p_end = mas_safe_pivot(mas, pivots, i, mt);
6834
6835	if (!gaps) {
6836	if (!mas_get_slot(mas, i))
6837	gap = p_end - p_start + 1;
6838	} else {
6839	void *entry = mas_get_slot(mas, i);
6840
6841	gap = gaps[i];
6842	MT_BUG_ON(mas->tree, !entry);
6843
6844	if (gap > p_end - p_start + 1) {
6845	pr_err(PTR_FMT "[%u] %lu >= %lu - %lu + 1 (%lu)\n",
6846	mas_mn(mas), i, gap, p_end, p_start,
6847	p_end - p_start + 1);
6848	MT_BUG_ON(mas->tree, gap > p_end - p_start + 1);
6849	}
6850	}
6851
6852	if (gap > max_gap)
6853	max_gap = gap;
6854
6855	p_start = p_end + 1;
6856	if (p_end >= mas->max)
6857	break;
6858	}
6859
6860	counted:
6861	if (mt == maple_arange_64) {
6862	MT_BUG_ON(mas->tree, !gaps);
6863	offset = ma_meta_gap(node);
6864	if (offset > i) {
6865	pr_err("gap offset " PTR_FMT "[%u] is invalid\n", node, offset);
6866	MT_BUG_ON(mas->tree, 1);
6867	}
6868
6869	if (gaps[offset] != max_gap) {
6870	pr_err("gap " PTR_FMT "[%u] is not the largest gap %lu\n",
6871	node, offset, max_gap);
6872	MT_BUG_ON(mas->tree, 1);
6873	}
6874
6875	for (i++ ; i < mt_slot_count(mte); i++) {
6876	if (gaps[i] != 0) {
6877	pr_err("gap " PTR_FMT "[%u] beyond node limit != 0\n",
6878	node, i);
6879	MT_BUG_ON(mas->tree, 1);
6880	}
6881	}
6882	}
6883
6884	if (mte_is_root(mte))
6885	return;
6886
6887	p_slot = mte_parent_slot(mas->node);
6888	p_mn = mte_parent(mte);
6889	MT_BUG_ON(mas->tree, max_gap > mas->max);
6890	if (ma_gaps(p_mn, mas_parent_type(mas, mte))[p_slot] != max_gap) {
6891	pr_err("gap " PTR_FMT "[%u] != %lu\n", p_mn, p_slot, max_gap);
6892	mt_dump(mas->tree, mt_dump_hex);
6893	MT_BUG_ON(mas->tree, 1);
6894	}
6895	}
6896
6897	static void mas_validate_parent_slot(struct ma_state *mas)
6898	{
6899	struct maple_node *parent;
6900	struct maple_enode *node;
6901	enum maple_type p_type;
6902	unsigned char p_slot;
6903	void __rcu **slots;
6904	int i;
6905
6906	if (mte_is_root(mas->node))
6907	return;
6908
6909	p_slot = mte_parent_slot(mas->node);
6910	p_type = mas_parent_type(mas, mas->node);
6911	parent = mte_parent(mas->node);
6912	slots = ma_slots(parent, p_type);
6913	MT_BUG_ON(mas->tree, mas_mn(mas) == parent);
6914
6915	/* Check prev/next parent slot for duplicate node entry */
6916
6917	for (i = 0; i < mt_slots[p_type]; i++) {
6918	node = mas_slot(mas, slots, i);
6919	if (i == p_slot) {
6920	if (node != mas->node)
6921	pr_err("parent " PTR_FMT "[%u] does not have " PTR_FMT "\n",
6922	parent, i, mas_mn(mas));
6923	MT_BUG_ON(mas->tree, node != mas->node);
6924	} else if (node == mas->node) {
6925	pr_err("Invalid child " PTR_FMT " at parent " PTR_FMT "[%u] p_slot %u\n",
6926	mas_mn(mas), parent, i, p_slot);
6927	MT_BUG_ON(mas->tree, node == mas->node);
6928	}
6929	}
6930	}
6931
6932	static void mas_validate_child_slot(struct ma_state *mas)
6933	{
6934	enum maple_type type = mte_node_type(mas->node);
6935	void __rcu **slots = ma_slots(mte_to_node(mas->node), type);
6936	unsigned long *pivots = ma_pivots(mte_to_node(mas->node), type);
6937	struct maple_enode *child;
6938	unsigned char i;
6939
6940	if (mte_is_leaf(mas->node))
6941	return;
6942
6943	for (i = 0; i < mt_slots[type]; i++) {
6944	child = mas_slot(mas, slots, i);
6945
6946	if (!child) {
6947	pr_err("Non-leaf node lacks child at " PTR_FMT "[%u]\n",
6948	mas_mn(mas), i);
6949	MT_BUG_ON(mas->tree, 1);
6950	}
6951
6952	if (mte_parent_slot(child) != i) {
6953	pr_err("Slot error at " PTR_FMT "[%u]: child " PTR_FMT " has pslot %u\n",
6954	mas_mn(mas), i, mte_to_node(child),
6955	mte_parent_slot(child));
6956	MT_BUG_ON(mas->tree, 1);
6957	}
6958
6959	if (mte_parent(child) != mte_to_node(mas->node)) {
6960	pr_err("child " PTR_FMT " has parent " PTR_FMT " not " PTR_FMT "\n",
6961	mte_to_node(child), mte_parent(child),
6962	mte_to_node(mas->node));
6963	MT_BUG_ON(mas->tree, 1);
6964	}
6965
6966	if (i < mt_pivots[type] && pivots[i] == mas->max)
6967	break;
6968	}
6969	}
6970
6971	/*
6972	* Validate all pivots are within mas->min and mas->max, check metadata ends
6973	* where the maximum ends and ensure there is no slots or pivots set outside of
6974	* the end of the data.
6975	*/
6976	static void mas_validate_limits(struct ma_state *mas)
6977	{
6978	int i;
6979	unsigned long prev_piv = 0;
6980	enum maple_type type = mte_node_type(mas->node);
6981	void __rcu **slots = ma_slots(mte_to_node(mas->node), type);
6982	unsigned long *pivots = ma_pivots(mas_mn(mas), type);
6983
6984	for (i = 0; i < mt_slots[type]; i++) {
6985	unsigned long piv;
6986
6987	piv = mas_safe_pivot(mas, pivots, i, type);
6988
6989	if (!piv && (i != 0)) {
6990	pr_err("Missing node limit pivot at " PTR_FMT "[%u]",
6991	mas_mn(mas), i);
6992	MAS_WARN_ON(mas, 1);
6993	}
6994
6995	if (prev_piv > piv) {
6996	pr_err(PTR_FMT "[%u] piv %lu < prev_piv %lu\n",
6997	mas_mn(mas), i, piv, prev_piv);
6998	MAS_WARN_ON(mas, piv < prev_piv);
6999	}
7000
7001	if (piv < mas->min) {
7002	pr_err(PTR_FMT "[%u] %lu < %lu\n", mas_mn(mas), i,
7003	piv, mas->min);
7004	MAS_WARN_ON(mas, piv < mas->min);
7005	}
7006	if (piv > mas->max) {
7007	pr_err(PTR_FMT "[%u] %lu > %lu\n", mas_mn(mas), i,
7008	piv, mas->max);
7009	MAS_WARN_ON(mas, piv > mas->max);
7010	}
7011	prev_piv = piv;
7012	if (piv == mas->max)
7013	break;
7014	}
7015
7016	if (mas_data_end(mas) != i) {
7017	pr_err("node" PTR_FMT ": data_end %u != the last slot offset %u\n",
7018	mas_mn(mas), mas_data_end(mas), i);
7019	MT_BUG_ON(mas->tree, 1);
7020	}
7021
7022	for (i += 1; i < mt_slots[type]; i++) {
7023	void *entry = mas_slot(mas, slots, i);
7024
7025	if (entry && (i != mt_slots[type] - 1)) {
7026	pr_err(PTR_FMT "[%u] should not have entry " PTR_FMT "\n",
7027	mas_mn(mas), i, entry);
7028	MT_BUG_ON(mas->tree, entry != NULL);
7029	}
7030
7031	if (i < mt_pivots[type]) {
7032	unsigned long piv = pivots[i];
7033
7034	if (!piv)
7035	continue;
7036
7037	pr_err(PTR_FMT "[%u] should not have piv %lu\n",
7038	mas_mn(mas), i, piv);
7039	MAS_WARN_ON(mas, i < mt_pivots[type] - 1);
7040	}
7041	}
7042	}
7043
7044	static void mt_validate_nulls(struct maple_tree *mt)
7045	{
7046	void entry, last = (void *)1;
7047	unsigned char offset = 0;
7048	void __rcu **slots;
7049	MA_STATE(mas, mt, 0, 0);
7050
7051	mas_start(&mas);
7052	if (mas_is_none(&mas) \|\| (mas_is_ptr(&mas)))
7053	return;
7054
7055	while (!mte_is_leaf(mas.node))
7056	mas_descend(&mas);
7057
7058	slots = ma_slots(mte_to_node(mas.node), mte_node_type(mas.node));
7059	do {
7060	entry = mas_slot(&mas, slots, offset);
7061	if (!last && !entry) {
7062	pr_err("Sequential nulls end at " PTR_FMT "[%u]\n",
7063	mas_mn(&mas), offset);
7064	}
7065	MT_BUG_ON(mt, !last && !entry);
7066	last = entry;
7067	if (offset == mas_data_end(&mas)) {
7068	mas_next_node(&mas, mas_mn(&mas), ULONG_MAX);
7069	if (mas_is_overflow(&mas))
7070	return;
7071	offset = 0;
7072	slots = ma_slots(mte_to_node(mas.node),
7073	mte_node_type(mas.node));
7074	} else {
7075	offset++;
7076	}
7077
7078	} while (!mas_is_overflow(&mas));
7079	}
7080
7081	/*
7082	* validate a maple tree by checking:
7083	* 1. The limits (pivots are within mas->min to mas->max)
7084	* 2. The gap is correctly set in the parents
7085	*/
7086	void mt_validate(struct maple_tree *mt)
7087	__must_hold(mas->tree->ma_lock)
7088	{
7089	unsigned char end;
7090
7091	MA_STATE(mas, mt, 0, 0);
7092	mas_start(&mas);
7093	if (!mas_is_active(&mas))
7094	return;
7095
7096	while (!mte_is_leaf(mas.node))
7097	mas_descend(&mas);
7098
7099	while (!mas_is_overflow(&mas)) {
7100	MAS_WARN_ON(&mas, mte_dead_node(mas.node));
7101	end = mas_data_end(&mas);
7102	if (MAS_WARN_ON(&mas, (end < mt_min_slot_count(mas.node)) &&
7103	(!mte_is_root(mas.node)))) {
7104	pr_err("Invalid size %u of " PTR_FMT "\n",
7105	end, mas_mn(&mas));
7106	}
7107
7108	mas_validate_parent_slot(&mas);
7109	mas_validate_limits(&mas);
7110	mas_validate_child_slot(&mas);
7111	if (mt_is_alloc(mt))
7112	mas_validate_gaps(&mas);
7113	mas_dfs_postorder(&mas, ULONG_MAX);
7114	}
7115	mt_validate_nulls(mt);
7116	}
7117	EXPORT_SYMBOL_GPL(mt_validate);
7118
7119	void mas_dump(const struct ma_state *mas)
7120	{
7121	pr_err("MAS: tree=" PTR_FMT " enode=" PTR_FMT " ",
7122	mas->tree, mas->node);
7123	switch (mas->status) {
7124	case ma_active:
7125	pr_err("(ma_active)");
7126	break;
7127	case ma_none:
7128	pr_err("(ma_none)");
7129	break;
7130	case ma_root:
7131	pr_err("(ma_root)");
7132	break;
7133	case ma_start:
7134	pr_err("(ma_start) ");
7135	break;
7136	case ma_pause:
7137	pr_err("(ma_pause) ");
7138	break;
7139	case ma_overflow:
7140	pr_err("(ma_overflow) ");
7141	break;
7142	case ma_underflow:
7143	pr_err("(ma_underflow) ");
7144	break;
7145	case ma_error:
7146	pr_err("(ma_error) ");
7147	break;
7148	}
7149
7150	pr_err("Store Type: ");
7151	switch (mas->store_type) {
7152	case wr_invalid:
7153	pr_err("invalid store type\n");
7154	break;
7155	case wr_new_root:
7156	pr_err("new_root\n");
7157	break;
7158	case wr_store_root:
7159	pr_err("store_root\n");
7160	break;
7161	case wr_exact_fit:
7162	pr_err("exact_fit\n");
7163	break;
7164	case wr_split_store:
7165	pr_err("split_store\n");
7166	break;
7167	case wr_slot_store:
7168	pr_err("slot_store\n");
7169	break;
7170	case wr_append:
7171	pr_err("append\n");
7172	break;
7173	case wr_node_store:
7174	pr_err("node_store\n");
7175	break;
7176	case wr_spanning_store:
7177	pr_err("spanning_store\n");
7178	break;
7179	case wr_rebalance:
7180	pr_err("rebalance\n");
7181	break;
7182	}
7183
7184	pr_err("[%u/%u] index=%lx last=%lx\n", mas->offset, mas->end,
7185	mas->index, mas->last);
7186	pr_err(" min=%lx max=%lx sheaf=" PTR_FMT ", request %lu depth=%u, flags=%x\n",
7187	mas->min, mas->max, mas->sheaf, mas->node_request, mas->depth,
7188	mas->mas_flags);
7189	if (mas->index > mas->last)
7190	pr_err("Check index & last\n");
7191	}
7192	EXPORT_SYMBOL_GPL(mas_dump);
7193
7194	void mas_wr_dump(const struct ma_wr_state *wr_mas)
7195	{
7196	pr_err("WR_MAS: node=" PTR_FMT " r_min=%lx r_max=%lx\n",
7197	wr_mas->node, wr_mas->r_min, wr_mas->r_max);
7198	pr_err(" type=%u off_end=%u, node_end=%u, end_piv=%lx\n",
7199	wr_mas->type, wr_mas->offset_end, wr_mas->mas->end,
7200	wr_mas->end_piv);
7201	}
7202	EXPORT_SYMBOL_GPL(mas_wr_dump);
7203
7204	#endif /* CONFIG_DEBUG_MAPLE_TREE */