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