1 // SPDX-License-Identifier: GPL-2.0+
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>
10 * DOC: Interesting implementation details of the Maple Tree
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.
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
23 * The following illustrates the layout of a range64 nodes slots and pivots.
26 * Slots -> | 0 | 1 | 2 | ... | 12 | 13 | 14 | 15 |
28 * │ │ │ │ │ │ │ │ └─ Implied maximum
29 * │ │ │ │ │ │ │ └─ Pivot 14
30 * │ │ │ │ │ │ └─ Pivot 13
31 * │ │ │ │ │ └─ Pivot 12
39 * Internal (non-leaf) nodes contain pointers to other nodes.
40 * Leaf nodes contain entries.
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.
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.
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>
62 #define CREATE_TRACE_POINTS
63 #include <trace/events/maple_tree.h>
65 #define MA_ROOT_PARENT 1
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
73 #define MA_STATE_BULK 1
74 #define MA_STATE_REBALANCE 2
75 #define MA_STATE_PREALLOC 4
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;
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,
89 #define mt_node_max(x) mt_max[mte_node_type(x)]
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,
98 #define mt_slot_count(x) mt_slots[mte_node_type(x)]
100 static const unsigned char mt_pivots[] = {
102 [maple_leaf_64] = MAPLE_RANGE64_SLOTS - 1,
103 [maple_range_64] = MAPLE_RANGE64_SLOTS - 1,
104 [maple_arange_64] = MAPLE_ARANGE64_SLOTS - 1,
106 #define mt_pivot_count(x) mt_pivots[mte_node_type(x)]
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,
114 #define mt_min_slot_count(x) mt_min_slots[mte_node_type(x)]
116 #define MAPLE_BIG_NODE_SLOTS (MAPLE_RANGE64_SLOTS * 2 + 2)
117 #define MAPLE_BIG_NODE_GAPS (MAPLE_ARANGE64_SLOTS * 2 + 1)
119 struct maple_big_node {
120 struct maple_pnode *parent;
121 unsigned long pivot[MAPLE_BIG_NODE_SLOTS - 1];
123 struct maple_enode *slot[MAPLE_BIG_NODE_SLOTS];
125 unsigned long padding[MAPLE_BIG_NODE_GAPS];
126 unsigned long gap[MAPLE_BIG_NODE_GAPS];
130 enum maple_type type;
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.
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;
150 static inline struct maple_node *mt_alloc_one(gfp_t gfp)
152 return kmem_cache_alloc(maple_node_cache, gfp);
155 static inline int mt_alloc_bulk(gfp_t gfp, size_t size, void **nodes)
157 return kmem_cache_alloc_bulk(maple_node_cache, gfp, size, nodes);
160 static inline void mt_free_bulk(size_t size, void __rcu **nodes)
162 kmem_cache_free_bulk(maple_node_cache, size, (void **)nodes);
165 static void mt_free_rcu(struct rcu_head *head)
167 struct maple_node *node = container_of(head, struct maple_node, rcu);
169 kmem_cache_free(maple_node_cache, node);
173 * ma_free_rcu() - Use rcu callback to free a maple node
174 * @node: The node to free
176 * The maple tree uses the parent pointer to indicate this node is no longer in
177 * use and will be freed.
179 static void ma_free_rcu(struct maple_node *node)
181 node->parent = ma_parent_ptr(node);
182 call_rcu(&node->rcu, mt_free_rcu);
186 static void mas_set_height(struct ma_state *mas)
188 unsigned int new_flags = mas->tree->ma_flags;
190 new_flags &= ~MT_FLAGS_HEIGHT_MASK;
191 BUG_ON(mas->depth > MAPLE_HEIGHT_MAX);
192 new_flags |= mas->depth << MT_FLAGS_HEIGHT_OFFSET;
193 mas->tree->ma_flags = new_flags;
196 static unsigned int mas_mt_height(struct ma_state *mas)
198 return mt_height(mas->tree);
201 static inline enum maple_type mte_node_type(const struct maple_enode *entry)
203 return ((unsigned long)entry >> MAPLE_NODE_TYPE_SHIFT) &
204 MAPLE_NODE_TYPE_MASK;
207 static inline bool ma_is_dense(const enum maple_type type)
209 return type < maple_leaf_64;
212 static inline bool ma_is_leaf(const enum maple_type type)
214 return type < maple_range_64;
217 static inline bool mte_is_leaf(const struct maple_enode *entry)
219 return ma_is_leaf(mte_node_type(entry));
223 * We also reserve values with the bottom two bits set to '10' which are
226 static inline bool mt_is_reserved(const void *entry)
228 return ((unsigned long)entry < MAPLE_RESERVED_RANGE) &&
229 xa_is_internal(entry);
232 static inline void mas_set_err(struct ma_state *mas, long err)
234 mas->node = MA_ERROR(err);
237 static inline bool mas_is_ptr(struct ma_state *mas)
239 return mas->node == MAS_ROOT;
242 static inline bool mas_is_start(struct ma_state *mas)
244 return mas->node == MAS_START;
247 bool mas_is_err(struct ma_state *mas)
249 return xa_is_err(mas->node);
252 static inline bool mas_searchable(struct ma_state *mas)
254 if (mas_is_none(mas))
263 static inline struct maple_node *mte_to_node(const struct maple_enode *entry)
265 return (struct maple_node *)((unsigned long)entry & ~MAPLE_NODE_MASK);
269 * mte_to_mat() - Convert a maple encoded node to a maple topiary node.
270 * @entry: The maple encoded node
272 * Return: a maple topiary pointer
274 static inline struct maple_topiary *mte_to_mat(const struct maple_enode *entry)
276 return (struct maple_topiary *)
277 ((unsigned long)entry & ~MAPLE_NODE_MASK);
281 * mas_mn() - Get the maple state node.
282 * @mas: The maple state
284 * Return: the maple node (not encoded - bare pointer).
286 static inline struct maple_node *mas_mn(const struct ma_state *mas)
288 return mte_to_node(mas->node);
292 * mte_set_node_dead() - Set a maple encoded node as dead.
293 * @mn: The maple encoded node.
295 static inline void mte_set_node_dead(struct maple_enode *mn)
297 mte_to_node(mn)->parent = ma_parent_ptr(mte_to_node(mn));
298 smp_wmb(); /* Needed for RCU */
301 /* Bit 1 indicates the root is a node */
302 #define MAPLE_ROOT_NODE 0x02
303 /* maple_type stored bit 3-6 */
304 #define MAPLE_ENODE_TYPE_SHIFT 0x03
305 /* Bit 2 means a NULL somewhere below */
306 #define MAPLE_ENODE_NULL 0x04
308 static inline struct maple_enode *mt_mk_node(const struct maple_node *node,
309 enum maple_type type)
311 return (void *)((unsigned long)node |
312 (type << MAPLE_ENODE_TYPE_SHIFT) | MAPLE_ENODE_NULL);
315 static inline void *mte_mk_root(const struct maple_enode *node)
317 return (void *)((unsigned long)node | MAPLE_ROOT_NODE);
320 static inline void *mte_safe_root(const struct maple_enode *node)
322 return (void *)((unsigned long)node & ~MAPLE_ROOT_NODE);
325 static inline void mte_set_full(const struct maple_enode *node)
327 node = (void *)((unsigned long)node & ~MAPLE_ENODE_NULL);
330 static inline void mte_clear_full(const struct maple_enode *node)
332 node = (void *)((unsigned long)node | MAPLE_ENODE_NULL);
335 static inline bool ma_is_root(struct maple_node *node)
337 return ((unsigned long)node->parent & MA_ROOT_PARENT);
340 static inline bool mte_is_root(const struct maple_enode *node)
342 return ma_is_root(mte_to_node(node));
345 static inline bool mas_is_root_limits(const struct ma_state *mas)
347 return !mas->min && mas->max == ULONG_MAX;
350 static inline bool mt_is_alloc(struct maple_tree *mt)
352 return (mt->ma_flags & MT_FLAGS_ALLOC_RANGE);
357 * Excluding root, the parent pointer is 256B aligned like all other tree nodes.
358 * When storing a 32 or 64 bit values, the offset can fit into 5 bits. The 16
359 * bit values need an extra bit to store the offset. This extra bit comes from
360 * a reuse of the last bit in the node type. This is possible by using bit 1 to
361 * indicate if bit 2 is part of the type or the slot.
365 * 0x?00 = 16 bit nodes
366 * 0x010 = 32 bit nodes
367 * 0x110 = 64 bit nodes
369 * Slot size and alignment
371 * 0b?00 : 16 bit values, type in 0-1, slot in 2-7
372 * 0b010 : 32 bit values, type in 0-2, slot in 3-7
373 * 0b110 : 64 bit values, type in 0-2, slot in 3-7
376 #define MAPLE_PARENT_ROOT 0x01
378 #define MAPLE_PARENT_SLOT_SHIFT 0x03
379 #define MAPLE_PARENT_SLOT_MASK 0xF8
381 #define MAPLE_PARENT_16B_SLOT_SHIFT 0x02
382 #define MAPLE_PARENT_16B_SLOT_MASK 0xFC
384 #define MAPLE_PARENT_RANGE64 0x06
385 #define MAPLE_PARENT_RANGE32 0x04
386 #define MAPLE_PARENT_NOT_RANGE16 0x02
389 * mte_parent_shift() - Get the parent shift for the slot storage.
390 * @parent: The parent pointer cast as an unsigned long
391 * Return: The shift into that pointer to the star to of the slot
393 static inline unsigned long mte_parent_shift(unsigned long parent)
395 /* Note bit 1 == 0 means 16B */
396 if (likely(parent & MAPLE_PARENT_NOT_RANGE16))
397 return MAPLE_PARENT_SLOT_SHIFT;
399 return MAPLE_PARENT_16B_SLOT_SHIFT;
403 * mte_parent_slot_mask() - Get the slot mask for the parent.
404 * @parent: The parent pointer cast as an unsigned long.
405 * Return: The slot mask for that parent.
407 static inline unsigned long mte_parent_slot_mask(unsigned long parent)
409 /* Note bit 1 == 0 means 16B */
410 if (likely(parent & MAPLE_PARENT_NOT_RANGE16))
411 return MAPLE_PARENT_SLOT_MASK;
413 return MAPLE_PARENT_16B_SLOT_MASK;
417 * mas_parent_enum() - Return the maple_type of the parent from the stored
419 * @mas: The maple state
420 * @node: The maple_enode to extract the parent's enum
421 * Return: The node->parent maple_type
424 enum maple_type mte_parent_enum(struct maple_enode *p_enode,
425 struct maple_tree *mt)
427 unsigned long p_type;
429 p_type = (unsigned long)p_enode;
430 if (p_type & MAPLE_PARENT_ROOT)
431 return 0; /* Validated in the caller. */
433 p_type &= MAPLE_NODE_MASK;
434 p_type = p_type & ~(MAPLE_PARENT_ROOT | mte_parent_slot_mask(p_type));
437 case MAPLE_PARENT_RANGE64: /* or MAPLE_PARENT_ARANGE64 */
439 return maple_arange_64;
440 return maple_range_64;
447 enum maple_type mas_parent_enum(struct ma_state *mas, struct maple_enode *enode)
449 return mte_parent_enum(ma_enode_ptr(mte_to_node(enode)->parent), mas->tree);
453 * mte_set_parent() - Set the parent node and encode the slot
454 * @enode: The encoded maple node.
455 * @parent: The encoded maple node that is the parent of @enode.
456 * @slot: The slot that @enode resides in @parent.
458 * Slot number is encoded in the enode->parent bit 3-6 or 2-6, depending on the
462 void mte_set_parent(struct maple_enode *enode, const struct maple_enode *parent,
465 unsigned long val = (unsigned long) parent;
468 enum maple_type p_type = mte_node_type(parent);
470 BUG_ON(p_type == maple_dense);
471 BUG_ON(p_type == maple_leaf_64);
475 case maple_arange_64:
476 shift = MAPLE_PARENT_SLOT_SHIFT;
477 type = MAPLE_PARENT_RANGE64;
486 val &= ~MAPLE_NODE_MASK; /* Clear all node metadata in parent */
487 val |= (slot << shift) | type;
488 mte_to_node(enode)->parent = ma_parent_ptr(val);
492 * mte_parent_slot() - get the parent slot of @enode.
493 * @enode: The encoded maple node.
495 * Return: The slot in the parent node where @enode resides.
497 static inline unsigned int mte_parent_slot(const struct maple_enode *enode)
499 unsigned long val = (unsigned long) mte_to_node(enode)->parent;
506 * Okay to use MAPLE_PARENT_16B_SLOT_MASK as the last bit will be lost
507 * by shift if the parent shift is MAPLE_PARENT_SLOT_SHIFT
509 return (val & MAPLE_PARENT_16B_SLOT_MASK) >> mte_parent_shift(val);
513 * mte_parent() - Get the parent of @node.
514 * @node: The encoded maple node.
516 * Return: The parent maple node.
518 static inline struct maple_node *mte_parent(const struct maple_enode *enode)
520 return (void *)((unsigned long)
521 (mte_to_node(enode)->parent) & ~MAPLE_NODE_MASK);
525 * ma_dead_node() - check if the @enode is dead.
526 * @enode: The encoded maple node
528 * Return: true if dead, false otherwise.
530 static inline bool ma_dead_node(const struct maple_node *node)
532 struct maple_node *parent = (void *)((unsigned long)
533 node->parent & ~MAPLE_NODE_MASK);
535 return (parent == node);
538 * mte_dead_node() - check if the @enode is dead.
539 * @enode: The encoded maple node
541 * Return: true if dead, false otherwise.
543 static inline bool mte_dead_node(const struct maple_enode *enode)
545 struct maple_node *parent, *node;
547 node = mte_to_node(enode);
548 parent = mte_parent(enode);
549 return (parent == node);
553 * mas_allocated() - Get the number of nodes allocated in a maple state.
554 * @mas: The maple state
556 * The ma_state alloc member is overloaded to hold a pointer to the first
557 * allocated node or to the number of requested nodes to allocate. If bit 0 is
558 * set, then the alloc contains the number of requested nodes. If there is an
559 * allocated node, then the total allocated nodes is in that node.
561 * Return: The total number of nodes allocated
563 static inline unsigned long mas_allocated(const struct ma_state *mas)
565 if (!mas->alloc || ((unsigned long)mas->alloc & 0x1))
568 return mas->alloc->total;
572 * mas_set_alloc_req() - Set the requested number of allocations.
573 * @mas: the maple state
574 * @count: the number of allocations.
576 * The requested number of allocations is either in the first allocated node,
577 * located in @mas->alloc->request_count, or directly in @mas->alloc if there is
578 * no allocated node. Set the request either in the node or do the necessary
579 * encoding to store in @mas->alloc directly.
581 static inline void mas_set_alloc_req(struct ma_state *mas, unsigned long count)
583 if (!mas->alloc || ((unsigned long)mas->alloc & 0x1)) {
587 mas->alloc = (struct maple_alloc *)(((count) << 1U) | 1U);
591 mas->alloc->request_count = count;
595 * mas_alloc_req() - get the requested number of allocations.
596 * @mas: The maple state
598 * The alloc count is either stored directly in @mas, or in
599 * @mas->alloc->request_count if there is at least one node allocated. Decode
600 * the request count if it's stored directly in @mas->alloc.
602 * Return: The allocation request count.
604 static inline unsigned int mas_alloc_req(const struct ma_state *mas)
606 if ((unsigned long)mas->alloc & 0x1)
607 return (unsigned long)(mas->alloc) >> 1;
609 return mas->alloc->request_count;
614 * ma_pivots() - Get a pointer to the maple node pivots.
615 * @node - the maple node
616 * @type - the node type
618 * Return: A pointer to the maple node pivots
620 static inline unsigned long *ma_pivots(struct maple_node *node,
621 enum maple_type type)
624 case maple_arange_64:
625 return node->ma64.pivot;
628 return node->mr64.pivot;
636 * ma_gaps() - Get a pointer to the maple node gaps.
637 * @node - the maple node
638 * @type - the node type
640 * Return: A pointer to the maple node gaps
642 static inline unsigned long *ma_gaps(struct maple_node *node,
643 enum maple_type type)
646 case maple_arange_64:
647 return node->ma64.gap;
657 * mte_pivot() - Get the pivot at @piv of the maple encoded node.
658 * @mn: The maple encoded node.
661 * Return: the pivot at @piv of @mn.
663 static inline unsigned long mte_pivot(const struct maple_enode *mn,
666 struct maple_node *node = mte_to_node(mn);
667 enum maple_type type = mte_node_type(mn);
669 if (piv >= mt_pivots[type]) {
674 case maple_arange_64:
675 return node->ma64.pivot[piv];
678 return node->mr64.pivot[piv];
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
692 * Return: The pivot at @piv within the limit of the @pivots array, @mas->max
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)
699 if (piv >= mt_pivots[type])
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
711 * Return: The minimum range value that is contained in @offset.
713 static inline unsigned long
714 mas_safe_min(struct ma_state *mas, unsigned long *pivots, unsigned char offset)
717 return pivots[offset - 1] + 1;
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
729 * When there is no value at a pivot (beyond the end of the data), then the
730 * pivot is actually @mas->max.
732 * Return: the logical pivot of a given @offset.
734 static inline unsigned long
735 mas_logical_pivot(struct ma_state *mas, unsigned long *pivots,
736 unsigned char offset, enum maple_type type)
738 unsigned long lpiv = mas_safe_pivot(mas, pivots, offset, type);
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
755 static inline void mte_set_pivot(struct maple_enode *mn, unsigned char piv,
758 struct maple_node *node = mte_to_node(mn);
759 enum maple_type type = mte_node_type(mn);
761 BUG_ON(piv >= mt_pivots[type]);
766 node->mr64.pivot[piv] = val;
768 case maple_arange_64:
769 node->ma64.pivot[piv] = val;
778 * ma_slots() - Get a pointer to the maple node slots.
779 * @mn: The maple node
780 * @mt: The maple node type
782 * Return: A pointer to the maple node slots
784 static inline void __rcu **ma_slots(struct maple_node *mn, enum maple_type mt)
788 case maple_arange_64:
789 return mn->ma64.slot;
792 return mn->mr64.slot;
798 static inline bool mt_locked(const struct maple_tree *mt)
800 return mt_external_lock(mt) ? mt_lock_is_held(mt) :
801 lockdep_is_held(&mt->ma_lock);
804 static inline void *mt_slot(const struct maple_tree *mt,
805 void __rcu **slots, unsigned char offset)
807 return rcu_dereference_check(slots[offset], mt_locked(mt));
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
816 * Return: The entry stored in @slots at the @offset.
818 static inline void *mas_slot_locked(struct ma_state *mas, void __rcu **slots,
819 unsigned char offset)
821 return rcu_dereference_protected(slots[offset], mt_locked(mas->tree));
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
830 * Return: The entry stored in @slots at the @offset
832 static inline void *mas_slot(struct ma_state *mas, void __rcu **slots,
833 unsigned char offset)
835 return mt_slot(mas->tree, slots, offset);
839 * mas_root() - Get the maple tree root.
840 * @mas: The maple state.
842 * Return: The pointer to the root of the tree
844 static inline void *mas_root(struct ma_state *mas)
846 return rcu_dereference_check(mas->tree->ma_root, mt_locked(mas->tree));
849 static inline void *mt_root_locked(struct maple_tree *mt)
851 return rcu_dereference_protected(mt->ma_root, mt_locked(mt));
855 * mas_root_locked() - Get the maple tree root when holding the maple tree lock.
856 * @mas: The maple state.
858 * Return: The pointer to the root of the tree
860 static inline void *mas_root_locked(struct ma_state *mas)
862 return mt_root_locked(mas->tree);
865 static inline struct maple_metadata *ma_meta(struct maple_node *mn,
869 case maple_arange_64:
870 return &mn->ma64.meta;
872 return &mn->mr64.meta;
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.
883 static inline void ma_set_meta(struct maple_node *mn, enum maple_type mt,
884 unsigned char offset, unsigned char end)
886 struct maple_metadata *meta = ma_meta(mn, mt);
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
897 static inline unsigned char ma_meta_end(struct maple_node *mn,
900 struct maple_metadata *meta = ma_meta(mn, mt);
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
910 static inline unsigned char ma_meta_gap(struct maple_node *mn,
913 BUG_ON(mt != maple_arange_64);
915 return mn->ma64.meta.gap;
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.
924 static inline void ma_set_meta_gap(struct maple_node *mn, enum maple_type mt,
925 unsigned char offset)
928 struct maple_metadata *meta = ma_meta(mn, mt);
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
938 * Add the @dead_enode to the linked list in @mat.
940 static inline void mat_add(struct ma_topiary *mat,
941 struct maple_enode *dead_enode)
943 mte_set_node_dead(dead_enode);
944 mte_to_mat(dead_enode)->next = NULL;
946 mat->tail = mat->head = dead_enode;
950 mte_to_mat(mat->tail)->next = dead_enode;
951 mat->tail = dead_enode;
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);
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.
962 * Free walk a dead list.
964 static void mas_mat_free(struct ma_state *mas, struct ma_topiary *mat)
966 struct maple_enode *next;
969 next = mte_to_mat(mat->head)->next;
970 mas_free(mas, mat->head);
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.
980 * Destroy walk a dead list.
982 static void mas_mat_destroy(struct ma_state *mas, struct ma_topiary *mat)
984 struct maple_enode *next;
987 next = mte_to_mat(mat->head)->next;
988 mte_destroy_walk(mat->head, mat->mtree);
993 * mas_descend() - Descend into the slot stored in the ma_state.
994 * @mas - the maple state.
996 * Note: Not RCU safe, only use in write side or debug code.
998 static inline void mas_descend(struct ma_state *mas)
1000 enum maple_type type;
1001 unsigned long *pivots;
1002 struct maple_node *node;
1006 type = mte_node_type(mas->node);
1007 pivots = ma_pivots(node, type);
1008 slots = ma_slots(node, type);
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);
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
1022 static inline void mte_set_gap(const struct maple_enode *mn,
1023 unsigned char gap, unsigned long val)
1025 switch (mte_node_type(mn)) {
1028 case maple_arange_64:
1029 mte_to_node(mn)->ma64.gap[gap] = val;
1035 * mas_ascend() - Walk up a level of the tree.
1036 * @mas: The maple state
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
1043 static int mas_ascend(struct ma_state *mas)
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;
1056 a_node = mas_mn(mas);
1057 if (ma_is_root(a_node)) {
1062 p_node = mte_parent(mas->node);
1063 if (unlikely(a_node == p_node))
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);
1069 /* Check to make sure all parent information is still accurate */
1070 if (p_node != mte_parent(mas->node))
1073 mas->node = a_enode;
1074 mas->offset = offset;
1076 if (mte_is_root(a_enode)) {
1077 mas->max = ULONG_MAX;
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);
1092 if (!set_min && a_slot) {
1094 min = pivots[a_slot - 1] + 1;
1097 if (!set_max && a_slot < mt_pivots[a_type]) {
1099 max = pivots[a_slot];
1102 if (unlikely(ma_dead_node(a_node)))
1105 if (unlikely(ma_is_root(a_node)))
1108 } while (!set_min || !set_max);
1116 * mas_pop_node() - Get a previously allocated maple node from the maple state.
1117 * @mas: The maple state
1119 * Return: A pointer to a maple node.
1121 static inline struct maple_node *mas_pop_node(struct ma_state *mas)
1123 struct maple_alloc *ret, *node = mas->alloc;
1124 unsigned long total = mas_allocated(mas);
1125 unsigned int req = mas_alloc_req(mas);
1127 /* nothing or a request pending. */
1128 if (WARN_ON(!total))
1132 /* single allocation in this ma_state */
1138 if (node->node_count == 1) {
1139 /* Single allocation in this node. */
1140 mas->alloc = node->slot[0];
1141 mas->alloc->total = node->total - 1;
1146 ret = node->slot[--node->node_count];
1147 node->slot[node->node_count] = NULL;
1153 mas_set_alloc_req(mas, req);
1156 memset(ret, 0, sizeof(*ret));
1157 return (struct maple_node *)ret;
1161 * mas_push_node() - Push a node back on the maple state allocation.
1162 * @mas: The maple state
1163 * @used: The used maple node
1165 * Stores the maple node back into @mas->alloc for reuse. Updates allocated and
1166 * requested node count as necessary.
1168 static inline void mas_push_node(struct ma_state *mas, struct maple_node *used)
1170 struct maple_alloc *reuse = (struct maple_alloc *)used;
1171 struct maple_alloc *head = mas->alloc;
1172 unsigned long count;
1173 unsigned int requested = mas_alloc_req(mas);
1175 count = mas_allocated(mas);
1177 reuse->request_count = 0;
1178 reuse->node_count = 0;
1179 if (count && (head->node_count < MAPLE_ALLOC_SLOTS)) {
1180 head->slot[head->node_count++] = reuse;
1186 if ((head) && !((unsigned long)head & 0x1)) {
1187 reuse->slot[0] = head;
1188 reuse->node_count = 1;
1189 reuse->total += head->total;
1195 mas_set_alloc_req(mas, requested - 1);
1199 * mas_alloc_nodes() - Allocate nodes into a maple state
1200 * @mas: The maple state
1201 * @gfp: The GFP Flags
1203 static inline void mas_alloc_nodes(struct ma_state *mas, gfp_t gfp)
1205 struct maple_alloc *node;
1206 unsigned long allocated = mas_allocated(mas);
1207 unsigned int requested = mas_alloc_req(mas);
1209 void **slots = NULL;
1210 unsigned int max_req = 0;
1215 mas_set_alloc_req(mas, 0);
1216 if (mas->mas_flags & MA_STATE_PREALLOC) {
1219 WARN_ON(!allocated);
1222 if (!allocated || mas->alloc->node_count == MAPLE_ALLOC_SLOTS) {
1223 node = (struct maple_alloc *)mt_alloc_one(gfp);
1228 node->slot[0] = mas->alloc;
1229 node->node_count = 1;
1231 node->node_count = 0;
1235 node->total = ++allocated;
1240 node->request_count = 0;
1242 max_req = MAPLE_ALLOC_SLOTS;
1243 if (node->node_count) {
1244 unsigned int offset = node->node_count;
1246 slots = (void **)&node->slot[offset];
1249 slots = (void **)&node->slot;
1252 max_req = min(requested, max_req);
1253 count = mt_alloc_bulk(gfp, max_req, slots);
1257 node->node_count += count;
1259 node = node->slot[0];
1260 node->node_count = 0;
1261 node->request_count = 0;
1264 mas->alloc->total = allocated;
1268 /* Clean up potential freed allocations on bulk failure */
1269 memset(slots, 0, max_req * sizeof(unsigned long));
1271 mas_set_alloc_req(mas, requested);
1272 if (mas->alloc && !(((unsigned long)mas->alloc & 0x1)))
1273 mas->alloc->total = allocated;
1274 mas_set_err(mas, -ENOMEM);
1280 * mas_free() - Free an encoded maple node
1281 * @mas: The maple state
1282 * @used: The encoded maple node to free.
1284 * Uses rcu free if necessary, pushes @used back on the maple state allocations
1287 static inline void mas_free(struct ma_state *mas, struct maple_enode *used)
1289 struct maple_node *tmp = mte_to_node(used);
1291 if (mt_in_rcu(mas->tree))
1294 mas_push_node(mas, tmp);
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
1304 static void mas_node_count_gfp(struct ma_state *mas, int count, gfp_t gfp)
1306 unsigned long allocated = mas_allocated(mas);
1308 if (allocated < count) {
1309 mas_set_alloc_req(mas, count - allocated);
1310 mas_alloc_nodes(mas, gfp);
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
1320 * Note: Uses GFP_NOWAIT | __GFP_NOWARN for gfp flags.
1322 static void mas_node_count(struct ma_state *mas, int count)
1324 return mas_node_count_gfp(mas, count, GFP_NOWAIT | __GFP_NOWARN);
1328 * mas_start() - Sets up maple state for operations.
1329 * @mas: The maple state.
1331 * If mas->node == MAS_START, then set the min, max, depth, and offset to
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.
1340 static inline struct maple_enode *mas_start(struct ma_state *mas)
1342 if (likely(mas_is_start(mas))) {
1343 struct maple_enode *root;
1345 mas->node = MAS_NONE;
1347 mas->max = ULONG_MAX;
1351 root = mas_root(mas);
1352 /* Tree with nodes */
1353 if (likely(xa_is_node(root))) {
1355 mas->node = mte_safe_root(root);
1360 if (unlikely(!root)) {
1361 mas->offset = MAPLE_NODE_SLOTS;
1365 /* Single entry tree */
1366 mas->node = MAS_ROOT;
1367 mas->offset = MAPLE_NODE_SLOTS;
1369 /* Single entry tree. */
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
1386 * Uses metadata to find the end of the data when possible.
1387 * Return: The zero indexed last slot with data (may be null).
1389 static inline unsigned char ma_data_end(struct maple_node *node,
1390 enum maple_type type,
1391 unsigned long *pivots,
1394 unsigned char offset;
1396 if (type == maple_arange_64)
1397 return ma_meta_end(node, type);
1399 offset = mt_pivots[type] - 1;
1400 if (likely(!pivots[offset]))
1401 return ma_meta_end(node, type);
1403 if (likely(pivots[offset] == max))
1406 return mt_pivots[type];
1410 * mas_data_end() - Find the end of the data (slot).
1411 * @mas: the maple state
1413 * This method is optimized to check the metadata of a node if the node type
1414 * supports data end metadata.
1416 * Return: The zero indexed last slot with data (may be null).
1418 static inline unsigned char mas_data_end(struct ma_state *mas)
1420 enum maple_type type;
1421 struct maple_node *node;
1422 unsigned char offset;
1423 unsigned long *pivots;
1425 type = mte_node_type(mas->node);
1427 if (type == maple_arange_64)
1428 return ma_meta_end(node, type);
1430 pivots = ma_pivots(node, type);
1431 offset = mt_pivots[type] - 1;
1432 if (likely(!pivots[offset]))
1433 return ma_meta_end(node, type);
1435 if (likely(pivots[offset] == mas->max))
1438 return mt_pivots[type];
1442 * mas_leaf_max_gap() - Returns the largest gap in a leaf node
1443 * @mas - the maple state
1445 * Return: The maximum gap in the leaf.
1447 static unsigned long mas_leaf_max_gap(struct ma_state *mas)
1450 unsigned long pstart, gap, max_gap;
1451 struct maple_node *mn;
1452 unsigned long *pivots;
1455 unsigned char max_piv;
1457 mt = mte_node_type(mas->node);
1459 slots = ma_slots(mn, mt);
1461 if (unlikely(ma_is_dense(mt))) {
1463 for (i = 0; i < mt_slots[mt]; i++) {
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.
1481 pivots = ma_pivots(mn, mt);
1482 if (likely(!slots[0])) {
1483 max_gap = pivots[0] - mas->min + 1;
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;
1492 * Check end implied pivot which can only be a gap on the right most
1495 if (unlikely(mas->max == ULONG_MAX) && !slots[max_piv + 1]) {
1496 gap = ULONG_MAX - pivots[max_piv];
1501 for (; i <= max_piv; i++) {
1502 /* data == no gap. */
1503 if (likely(slots[i]))
1506 pstart = pivots[i - 1];
1507 gap = pivots[i] - pstart;
1511 /* There cannot be two gaps in a row. */
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.
1524 * Uses the metadata data end to scan backwards across set gaps.
1526 * Return: The maximum gap value
1528 static inline unsigned long
1529 ma_max_gap(struct maple_node *node, unsigned long *gaps, enum maple_type mt,
1532 unsigned char offset, i;
1533 unsigned long max_gap = 0;
1535 i = offset = ma_meta_end(node, mt);
1537 if (gaps[i] > max_gap) {
1548 * mas_max_gap() - find the largest gap in a non-leaf node and set the slot.
1549 * @mas: The maple state.
1551 * If the metadata gap is set to MAPLE_ARANGE64_META_MAX, there is no gap.
1553 * Return: The gap value.
1555 static inline unsigned long mas_max_gap(struct ma_state *mas)
1557 unsigned long *gaps;
1558 unsigned char offset;
1560 struct maple_node *node;
1562 mt = mte_node_type(mas->node);
1564 return mas_leaf_max_gap(mas);
1567 offset = ma_meta_gap(node, mt);
1568 if (offset == MAPLE_ARANGE64_META_MAX)
1571 gaps = ma_gaps(node, mt);
1572 return gaps[offset];
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.
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.
1584 static inline void mas_parent_gap(struct ma_state *mas, unsigned char offset,
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;
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);
1600 meta_offset = ma_meta_gap(pnode, pmt);
1601 if (meta_offset == MAPLE_ARANGE64_META_MAX)
1604 meta_gap = pgaps[meta_offset];
1606 pgaps[offset] = new;
1608 if (meta_gap == new)
1611 if (offset != meta_offset) {
1615 ma_set_meta_gap(pnode, pmt, offset);
1616 } else if (new < meta_gap) {
1618 new = ma_max_gap(pnode, pgaps, pmt, &meta_offset);
1619 ma_set_meta_gap(pnode, pmt, meta_offset);
1622 if (ma_is_root(pnode))
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);
1635 * mas_update_gap() - Update a nodes gaps and propagate up if necessary.
1636 * @mas - the maple state.
1638 static inline void mas_update_gap(struct ma_state *mas)
1640 unsigned char pslot;
1641 unsigned long p_gap;
1642 unsigned long max_gap;
1644 if (!mt_is_alloc(mas->tree))
1647 if (mte_is_root(mas->node))
1650 max_gap = mas_max_gap(mas);
1652 pslot = mte_parent_slot(mas->node);
1653 p_gap = ma_gaps(mte_parent(mas->node),
1654 mas_parent_enum(mas, mas->node))[pslot];
1656 if (p_gap != max_gap)
1657 mas_parent_gap(mas, pslot, max_gap);
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.
1666 static inline void mas_adopt_children(struct ma_state *mas,
1667 struct maple_enode *parent)
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;
1676 offset = ma_data_end(node, type, pivots, mas->max);
1678 child = mas_slot_locked(mas, slots, offset);
1679 mte_set_parent(child, parent, offset);
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.
1690 static inline void mas_replace(struct ma_state *mas, bool advanced)
1691 __must_hold(mas->tree->lock)
1693 struct maple_node *mn = mas_mn(mas);
1694 struct maple_enode *old_enode;
1695 unsigned char offset = 0;
1696 void __rcu **slots = NULL;
1698 if (ma_is_root(mn)) {
1699 old_enode = mas_root_locked(mas);
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);
1707 if (!advanced && !mte_is_leaf(mas->node))
1708 mas_adopt_children(mas, mas->node);
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);
1716 rcu_assign_pointer(slots[offset], mas->node);
1720 mas_free(mas, old_enode);
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.
1728 static inline bool mas_new_child(struct ma_state *mas, struct ma_state *child)
1729 __must_hold(mas->tree->lock)
1732 unsigned char offset;
1734 unsigned long *pivots;
1735 struct maple_enode *entry;
1736 struct maple_node *node;
1739 mt = mte_node_type(mas->node);
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) {
1748 mas->offset = offset + 1;
1749 child->offset = offset;
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
1764 static inline void mab_shift_right(struct maple_big_node *b_node,
1765 unsigned char shift)
1767 unsigned long size = b_node->b_end * sizeof(unsigned long);
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);
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.
1782 * Return: true if a middle node is required.
1784 static inline bool mab_middle_node(struct maple_big_node *b_node, int split,
1785 unsigned char slot_count)
1787 unsigned char size = b_node->b_end;
1789 if (size >= 2 * slot_count)
1792 if (!b_node->slot[split] && (size >= 2 * slot_count - 1))
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.
1804 * Return: the split location.
1806 static inline int mab_no_null_split(struct maple_big_node *b_node,
1807 unsigned char split, unsigned char slot_count)
1809 if (!b_node->slot[split]) {
1811 * If the split is less than the max slot && the right side will
1812 * still be sufficient, then increment the split on NULL.
1814 if ((split < slot_count - 1) &&
1815 (b_node->b_end - split) > (mt_min_slots[b_node->type]))
1824 * mab_calc_split() - Calculate the split location and if there needs to be two
1826 * @bn: The maple_big_node with the data
1827 * @mid_split: The second split, if required. 0 otherwise.
1829 * Return: The first split location. The middle split is set in @mid_split.
1831 static inline int mab_calc_split(struct ma_state *mas,
1832 struct maple_big_node *bn, unsigned char *mid_split, unsigned long min)
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];
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.
1844 if (unlikely((mas->mas_flags & MA_STATE_BULK))) {
1846 split = b_end - mt_min_slots[bn->type];
1848 if (!ma_is_leaf(bn->type))
1851 mas->mas_flags |= MA_STATE_REBALANCE;
1852 if (!bn->slot[split])
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.
1865 if (unlikely(mab_middle_node(bn, split, slot_count))) {
1867 *mid_split = split * 2;
1869 slot_min = mt_min_slots[bn->type];
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.
1877 while (((bn->pivot[split] - min) < slot_count - 1) &&
1878 (split < slot_count - 1) && (b_end - split > slot_min))
1882 /* Avoid ending a node on a NULL entry */
1883 split = mab_no_null_split(bn, split, slot_count);
1887 *mid_split = mab_no_null_split(bn, *mid_split, slot_count);
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.
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)
1906 struct maple_node *node;
1908 unsigned long *pivots, *gaps;
1909 int i = mas_start, j = mab_start;
1910 unsigned char piv_end;
1913 mt = mte_node_type(mas->node);
1914 pivots = ma_pivots(node, mt);
1916 b_node->pivot[j] = pivots[i++];
1917 if (unlikely(i > mas_end))
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]))
1928 if (unlikely(mas->max == b_node->pivot[j]))
1932 if (likely(i <= mas_end))
1933 b_node->pivot[j] = mas_safe_pivot(mas, pivots, i, mt);
1936 b_node->b_end = ++j;
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);
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
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.
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)
1963 /* There is no room for metadata already */
1964 if (mt_pivots[mt] <= end)
1967 if (pivots[end] && pivots[end] < mas->max)
1970 if (end < mt_slots[mt] - 1)
1971 ma_set_meta(node, mt, 0, end);
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.
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)
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;
1993 if (mab_end - mab_start > mt_pivots[mt])
1996 if (!pivots[mt_pivots[mt] - 1])
1997 slots[mt_pivots[mt]] = NULL;
2001 pivots[j++] = b_node->pivot[i++];
2002 } while (i <= mab_end && likely(b_node->pivot[i]));
2004 memcpy(slots, b_node->slot + mab_start,
2005 sizeof(void *) * (i - mab_start));
2008 mas->max = b_node->pivot[i - 1];
2011 if (likely(!ma_is_leaf(mt) && mt_is_alloc(mas->tree))) {
2012 unsigned long max_gap = 0;
2013 unsigned char offset = 15;
2015 gaps = ma_gaps(node, mt);
2017 gaps[--j] = b_node->gap[--i];
2018 if (gaps[j] > max_gap) {
2024 ma_set_meta(node, mt, offset, end);
2026 mas_leaf_set_meta(mas, node, pivots, mt, end);
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.
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
2039 static inline void mas_descend_adopt(struct ma_state *mas)
2041 struct ma_state list[3], next[3];
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.
2049 for (i = 0; i < 3; i++) {
2056 while (!mte_is_leaf(list[0].node)) {
2058 for (i = 0; i < 3; i++) {
2059 if (mas_is_none(&list[i]))
2062 if (i && list[i-1].node == list[i].node)
2065 while ((n < 3) && (mas_new_child(&list[i], &next[n])))
2068 mas_adopt_children(&list[i], list[i].node);
2072 next[n++].node = MAS_NONE;
2074 /* descend by setting the list to the children */
2075 for (i = 0; i < 3; i++)
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
2086 static inline void mas_bulk_rebalance(struct ma_state *mas, unsigned char end,
2089 if (!(mas->mas_flags & MA_STATE_BULK))
2092 if (mte_is_root(mas->node))
2095 if (end > mt_min_slots[mt]) {
2096 mas->mas_flags &= ~MA_STATE_REBALANCE;
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
2108 * Return: The actual end of the data stored in @b_node
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)
2114 unsigned char b_end;
2115 /* Possible underflow of piv will wrap back to 0 before use. */
2117 struct ma_state *mas = wr_mas->mas;
2119 b_node->type = wr_mas->type;
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];
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;
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;
2144 if (mas->last >= mas->max)
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);
2153 if (offset_end != slot)
2154 wr_mas->content = mas_slot_locked(mas, wr_mas->slots,
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;
2163 slot = offset_end + 1;
2164 if (slot > wr_mas->node_end)
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);
2173 b_node->b_end = b_end;
2177 * mas_prev_sibling() - Find the previous node with the same parent.
2178 * @mas: the maple state
2180 * Return: True if there is a previous sibling, false otherwise.
2182 static inline bool mas_prev_sibling(struct ma_state *mas)
2184 unsigned int p_slot = mte_parent_slot(mas->node);
2186 if (mte_is_root(mas->node))
2193 mas->offset = p_slot - 1;
2199 * mas_next_sibling() - Find the next node with the same parent.
2200 * @mas: the maple state
2202 * Return: true if there is a next sibling, false otherwise.
2204 static inline bool mas_next_sibling(struct ma_state *mas)
2206 MA_STATE(parent, mas->tree, mas->index, mas->last);
2208 if (mte_is_root(mas->node))
2212 mas_ascend(&parent);
2213 parent.offset = mte_parent_slot(mas->node) + 1;
2214 if (parent.offset > mas_data_end(&parent))
2223 * mte_node_or_node() - Return the encoded node or MAS_NONE.
2224 * @enode: The encoded maple node.
2226 * Shorthand to avoid setting %NULLs in the tree or maple_subtree_state.
2228 * Return: @enode or MAS_NONE
2230 static inline struct maple_enode *mte_node_or_none(struct maple_enode *enode)
2235 return ma_enode_ptr(MAS_NONE);
2239 * mas_wr_node_walk() - Find the correct offset for the index in the @mas.
2240 * @wr_mas: The maple write state
2242 * Uses mas_slot_locked() and does not need to worry about dead nodes.
2244 static inline void mas_wr_node_walk(struct ma_wr_state *wr_mas)
2246 struct ma_state *mas = wr_mas->mas;
2247 unsigned char count;
2248 unsigned char offset;
2249 unsigned long index, min, max;
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;
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))
2266 max = wr_mas->pivots[offset];
2268 if (unlikely(index <= max))
2271 if (unlikely(!max && offset))
2275 while (++offset < count) {
2276 max = wr_mas->pivots[offset];
2279 else if (unlikely(!max))
2288 wr_mas->r_max = max;
2289 wr_mas->r_min = min;
2290 wr_mas->offset_end = mas->offset = offset;
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
2300 static inline void mas_topiary_range(struct ma_state *mas,
2301 struct ma_topiary *destroy, unsigned char start, unsigned char end)
2304 unsigned char offset;
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);
2311 if (mte_dead_node(enode))
2314 mat_add(destroy, enode);
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.
2323 static inline void mast_topiary(struct maple_subtree_state *mast)
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;
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);
2336 r_end = mast->orig_r->offset;
2341 l_slots = ma_slots(mas_mn(mast->orig_l),
2342 mte_node_type(mast->orig_l->node));
2344 r_slots = ma_slots(mas_mn(mast->orig_r),
2345 mte_node_type(mast->orig_r->node));
2347 if ((l_start < l_end) &&
2348 mte_dead_node(mas_slot_locked(mast->orig_l, l_slots, l_start))) {
2352 if (mte_dead_node(mas_slot_locked(mast->orig_r, r_slots, r_end))) {
2357 if ((l_start > r_end) && (mast->orig_l->node == mast->orig_r->node))
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,
2366 /* mast->orig_r is different and consumed. */
2367 if (mte_is_leaf(mast->orig_r->node))
2370 if (mte_dead_node(mas_slot_locked(mast->orig_l, l_slots, l_end)))
2374 if (l_start <= l_end)
2375 mas_topiary_range(mast->orig_l, mast->destroy, l_start, l_end);
2377 if (mte_dead_node(mas_slot_locked(mast->orig_r, r_slots, r_start)))
2380 if (r_start <= r_end)
2381 mas_topiary_range(mast->orig_r, mast->destroy, 0, r_end);
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).
2389 static inline void mast_rebalance_next(struct maple_subtree_state *mast)
2391 unsigned char b_end = mast->bn->b_end;
2393 mas_mab_cp(mast->orig_r, 0, mt_slot_count(mast->orig_r->node),
2395 mast->orig_r->last = mast->orig_r->max;
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)
2403 static inline void mast_rebalance_prev(struct maple_subtree_state *mast)
2405 unsigned char end = mas_data_end(mast->orig_l) + 1;
2406 unsigned char b_end = mast->bn->b_end;
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;
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.
2424 bool mast_spanning_rebalance(struct maple_subtree_state *mast)
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;
2432 r_tmp = *mast->orig_r;
2433 l_tmp = *mast->orig_l;
2435 mas_ascend(mast->orig_r);
2436 mas_ascend(mast->orig_l);
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;
2445 if (mast->orig_r->offset < mas_data_end(mast->orig_r)) {
2447 ancestor = mast->orig_r->node;
2451 mast->orig_r->offset++;
2453 mas_descend(mast->orig_r);
2454 mast->orig_r->offset = 0;
2458 mast_rebalance_next(mast);
2460 unsigned char l_off = 0;
2461 struct maple_enode *child = r_tmp.node;
2464 if (ancestor == r_tmp.node)
2470 if (l_off < r_tmp.offset)
2471 mas_topiary_range(&r_tmp, mast->destroy,
2472 l_off, r_tmp.offset);
2474 if (l_tmp.node != child)
2475 mat_add(mast->free, child);
2477 } while (r_tmp.node != ancestor);
2479 *mast->orig_l = l_tmp;
2482 } else if (mast->orig_l->offset != 0) {
2484 ancestor = mast->orig_l->node;
2485 end = mas_data_end(mast->orig_l);
2488 mast->orig_l->offset--;
2490 mas_descend(mast->orig_l);
2491 mast->orig_l->offset =
2492 mas_data_end(mast->orig_l);
2496 mast_rebalance_prev(mast);
2498 unsigned char r_off;
2499 struct maple_enode *child = l_tmp.node;
2502 if (ancestor == l_tmp.node)
2505 r_off = mas_data_end(&l_tmp);
2507 if (l_tmp.offset < r_off)
2510 if (l_tmp.offset < r_off)
2511 mas_topiary_range(&l_tmp, mast->destroy,
2512 l_tmp.offset, r_off);
2514 if (r_tmp.node != child)
2515 mat_add(mast->free, child);
2517 } while (l_tmp.node != ancestor);
2519 *mast->orig_r = r_tmp;
2522 } while (!mte_is_root(mast->orig_r->node));
2524 *mast->orig_r = r_tmp;
2525 *mast->orig_l = l_tmp;
2530 * mast_ascend_free() - Add current original maple state nodes to the free list
2532 * @mast: the maple subtree state.
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.
2538 mast_ascend_free(struct maple_subtree_state *mast)
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;
2544 mas_ascend(mast->orig_l);
2545 mas_ascend(mast->orig_r);
2546 mat_add(mast->free, left);
2549 mat_add(mast->free, right);
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;
2557 * The node may not contain the value so set slot to ensure all
2558 * of the nodes contents are freed or destroyed.
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);
2569 mast->bn->type = wr_mas.type;
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.
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.
2580 * Return: A new maple encoded node
2582 static inline struct maple_enode
2583 *mas_new_ma_node(struct ma_state *mas, struct maple_big_node *b_node)
2585 return mt_mk_node(ma_mnode_ptr(mas_pop_node(mas)), b_node->type);
2589 * mas_mab_to_node() - Set up right and middle nodes
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
2598 * Return: the split of left.
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)
2605 unsigned char split = 0;
2606 unsigned char slot_count = mt_slots[b_node->type];
2608 *left = mas_new_ma_node(mas, b_node);
2613 if (b_node->b_end < slot_count) {
2614 split = b_node->b_end;
2616 split = mab_calc_split(mas, b_node, mid_split, min);
2617 *right = mas_new_ma_node(mas, b_node);
2621 *middle = mas_new_ma_node(mas, b_node);
2628 * mab_set_b_end() - Add entry to b_node at b_node->b_end and increment the end
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.
2634 static inline void mab_set_b_end(struct maple_big_node *b_node,
2635 struct ma_state *mas,
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;
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
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
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)
2662 if (mas_is_none(mas))
2665 if ((*slot) <= split)
2666 mte_set_parent(mas->node, left, *slot);
2668 mte_set_parent(mas->node, right, (*slot) - split - 1);
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.
2679 * @*split: The split location.
2680 * @mid_split: The middle split.
2682 static inline void mte_mid_split_check(struct maple_enode **l,
2683 struct maple_enode **r,
2684 struct maple_enode *right,
2686 unsigned char *split,
2687 unsigned char mid_split)
2692 if (slot < mid_split)
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.
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)
2716 struct maple_enode *l = left;
2717 struct maple_enode *r = right;
2719 if (mas_is_none(mast->l))
2725 slot = mast->l->offset;
2727 mte_mid_split_check(&l, &r, right, slot, &split, mid_split);
2728 mas_set_split_parent(mast->l, l, r, &slot, split);
2730 mte_mid_split_check(&l, &r, right, slot, &split, mid_split);
2731 mas_set_split_parent(mast->m, l, r, &slot, split);
2733 mte_mid_split_check(&l, &r, right, slot, &split, mid_split);
2734 mas_set_split_parent(mast->r, l, r, &slot, split);
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)
2743 * Updates gap as necessary.
2745 static inline void mas_wmb_replace(struct ma_state *mas,
2746 struct ma_topiary *free,
2747 struct ma_topiary *destroy)
2749 /* All nodes must see old data as dead prior to replacing that data */
2750 smp_wmb(); /* Needed for RCU */
2752 /* Insert the new data in the tree */
2753 mas_replace(mas, true);
2755 if (!mte_is_leaf(mas->node))
2756 mas_descend_adopt(mas);
2758 mas_mat_free(mas, free);
2761 mas_mat_destroy(mas, destroy);
2763 if (mte_is_leaf(mas->node))
2766 mas_update_gap(mas);
2770 * mast_new_root() - Set a new tree root during subtree creation
2771 * @mast: The maple subtree state
2772 * @mas: The maple state
2774 static inline void mast_new_root(struct maple_subtree_state *mast,
2775 struct ma_state *mas)
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)) {
2782 mast_ascend_free(mast);
2784 } while (!mte_is_root(mast->orig_l->node));
2786 if ((mast->orig_l->node != mas->node) &&
2787 (mast->l->depth > mas_mt_height(mas))) {
2788 mat_add(mast->free, mas->node);
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.
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)
2805 bool new_lmax = true;
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);
2811 mast->l->min = mast->orig_l->min;
2812 if (split == mast->bn->b_end) {
2813 mast->l->max = mast->orig_r->max;
2817 mab_mas_cp(mast->bn, 0, split, mast->l, new_lmax);
2820 mab_mas_cp(mast->bn, 1 + split, mid_split, mast->m, true);
2821 mast->m->min = mast->bn->pivot[split] + 1;
2825 mast->r->max = mast->orig_r->max;
2827 mab_mas_cp(mast->bn, 1 + split, mast->bn->b_end, mast->r, false);
2828 mast->r->min = mast->bn->pivot[split] + 1;
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
2837 static inline void mast_combine_cp_left(struct maple_subtree_state *mast)
2839 unsigned char l_slot = mast->orig_l->offset;
2844 mas_mab_cp(mast->orig_l, 0, l_slot - 1, mast->bn, 0);
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
2852 static inline void mast_combine_cp_right(struct maple_subtree_state *mast)
2854 if (mast->bn->pivot[mast->bn->b_end - 1] >= mast->orig_r->max)
2857 mas_mab_cp(mast->orig_r, mast->orig_r->offset + 1,
2858 mt_slot_count(mast->orig_r->node), mast->bn,
2860 mast->orig_r->last = mast->orig_r->max;
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
2868 static inline bool mast_sufficient(struct maple_subtree_state *mast)
2870 if (mast->bn->b_end > mt_min_slot_count(mast->orig_l->node))
2877 * mast_overflow: Check if there is too much data in the subtree state for a
2879 * @mast: The maple subtree state
2881 static inline bool mast_overflow(struct maple_subtree_state *mast)
2883 if (mast->bn->b_end >= mt_slot_count(mast->orig_l->node))
2889 static inline void *mtree_range_walk(struct ma_state *mas)
2891 unsigned long *pivots;
2892 unsigned char offset;
2893 struct maple_node *node;
2894 struct maple_enode *next, *last;
2895 enum maple_type type;
2898 unsigned long max, min;
2899 unsigned long prev_max, prev_min;
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)))
2914 if (pivots[offset] >= mas->index) {
2917 max = pivots[offset];
2923 } while ((offset < end) && (pivots[offset] < mas->index));
2926 min = pivots[offset - 1] + 1;
2928 if (likely(offset < end && pivots[offset]))
2929 max = pivots[offset];
2932 slots = ma_slots(node, type);
2933 next = mt_slot(mas->tree, slots, offset);
2934 if (unlikely(ma_dead_node(node)))
2936 } while (!ma_is_leaf(type));
2938 mas->offset = offset;
2941 mas->min = prev_min;
2942 mas->max = prev_max;
2944 return (void *) next;
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.
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.
2967 * Return: the number of elements in b_node during the last loop.
2969 static int mas_spanning_rebalance(struct ma_state *mas,
2970 struct maple_subtree_state *mast, unsigned char count)
2972 unsigned char split, mid_split;
2973 unsigned char slot = 0;
2974 struct maple_enode *left = NULL, *middle = NULL, *right = NULL;
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);
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``.
2990 mast->destroy = &destroy;
2991 l_mas.node = r_mas.node = m_mas.node = MAS_NONE;
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);
2998 mast->orig_l->depth = 0;
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..
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,
3018 mast_cp_to_nodes(mast, left, middle, right, split, mid_split);
3021 * Copy data from next level in the tree to mast->bn from next
3024 memset(mast->bn, 0, sizeof(struct maple_big_node));
3025 mast->bn->type = mte_node_type(left);
3026 mast->orig_l->depth++;
3028 /* Root already stored in l->node. */
3029 if (mas_is_root_limits(mast->l))
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);
3039 /* Copy anything necessary out of the right node. */
3040 mast_combine_cp_right(mast);
3042 mast->orig_l->last = mast->orig_l->max;
3044 if (mast_sufficient(mast))
3047 if (mast_overflow(mast))
3050 /* May be a new root stored in mast->bn */
3051 if (mas_is_root_limits(mast->orig_l))
3054 mast_spanning_rebalance(mast);
3056 /* rebalancing from other nodes may require another loop. */
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);
3067 mte_set_parent(middle, l_mas.node, ++slot);
3070 mte_set_parent(right, l_mas.node, ++slot);
3072 if (mas_is_root_limits(mast->l)) {
3074 mast_new_root(mast, mas);
3076 mas_mn(&l_mas)->parent = mas_mn(mast->orig_l)->parent;
3079 if (!mte_dead_node(mast->orig_l->node))
3080 mat_add(&free, mast->orig_l->node);
3082 mas->depth = mast->orig_l->depth;
3083 *mast->orig_l = l_mas;
3084 mte_set_node_dead(mas->node);
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;
3096 * mas_rebalance() - Rebalance a given node.
3097 * @mas: The maple state
3098 * @b_node: The big maple node.
3100 * Rebalance two nodes into a single node or two new nodes that are sufficient.
3101 * Continue upwards until tree is sufficient.
3103 * Return: the number of elements in b_node during the last loop.
3105 static inline int mas_rebalance(struct ma_state *mas,
3106 struct maple_big_node *b_node)
3108 char empty_count = mas_mt_height(mas);
3109 struct maple_subtree_state mast;
3110 unsigned char shift, b_end = ++b_node->b_end;
3112 MA_STATE(l_mas, mas->tree, mas->index, mas->last);
3113 MA_STATE(r_mas, mas->tree, mas->index, mas->last);
3115 trace_ma_op(__func__, mas);
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.
3126 mas_node_count(mas, 1 + empty_count * 3);
3127 if (mas_is_err(mas))
3130 mast.orig_l = &l_mas;
3131 mast.orig_r = &r_mas;
3133 mast.bn->type = mte_node_type(mas->node);
3135 l_mas = r_mas = *mas;
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;
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;
3150 return mas_spanning_rebalance(mas, &mast, empty_count);
3154 * mas_destroy_rebalance() - Rebalance left-most node while destroying the maple
3156 * @mas: The maple state
3157 * @end: The end of the left-most node.
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.
3162 static inline void mas_destroy_rebalance(struct ma_state *mas, unsigned char end)
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);
3172 MA_STATE(l_mas, mas->tree, mas->index, mas->last);
3175 mas_prev_sibling(&l_mas);
3179 /* Allocate for both left and right as well as parent. */
3180 mas_node_count(mas, 3);
3181 if (mas_is_err(mas))
3184 newnode = mas_pop_node(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])
3198 tmp = mas_data_end(&l_mas) - split;
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);
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));
3212 unsigned char max_p = mt_pivots[mt];
3213 unsigned char max_s = mt_slots[mt];
3216 memset(pivs + tmp, 0,
3217 sizeof(unsigned long *) * (max_p - tmp));
3219 if (tmp < mt_slots[mt])
3220 memset(slots + tmp, 0, sizeof(void *) * (max_s - tmp));
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),
3227 /* Remove data from l_pivs. */
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);
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);
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);
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);
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);
3269 mas_replace(mas, false);
3271 mas_update_gap(mas);
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.
3280 static inline bool mas_split_final_node(struct maple_subtree_state *mast,
3281 struct ma_state *mas, int height)
3283 struct maple_enode *ancestor;
3285 if (mte_is_root(mas->node)) {
3286 if (mt_is_alloc(mas->tree))
3287 mast->bn->type = maple_arange_64;
3289 mast->bn->type = maple_range_64;
3290 mas->depth = height;
3293 * Only a single node is used here, could be root.
3294 * The Big_node data should just fit in a single node.
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;
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;
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.
3313 static inline void mast_fill_bnode(struct maple_subtree_state *mast,
3314 struct ma_state *mas,
3318 struct maple_enode *old = mas->node;
3319 unsigned char split;
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;
3326 if (mte_is_root(mas->node)) {
3330 mat_add(mast->free, old);
3331 mas->offset = mte_parent_slot(mas->node);
3334 if (cp && mast->l->offset)
3335 mas_mab_cp(mas, 0, mast->l->offset - 1, mast->bn, 0);
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)
3345 mas_mab_cp(mas, split + skip, mt_slot_count(mas->node) - 1,
3346 mast->bn, mast->bn->b_end);
3349 mast->bn->type = mte_node_type(mas->node);
3353 * mast_split_data() - Split the data in the subtree state big node into regular
3355 * @mast: The maple subtree state
3356 * @mas: The maple state
3357 * @split: The location to split the big node
3359 static inline void mast_split_data(struct maple_subtree_state *mast,
3360 struct ma_state *mas, unsigned char split)
3362 unsigned char p_slot;
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))
3373 p_slot = mast->orig_l->offset;
3374 mas_set_split_parent(mast->orig_l, mast->l->node, mast->r->node,
3376 mas_set_split_parent(mast->orig_r, mast->l->node, mast->r->node,
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.
3388 * Keeping the height of the tree low means faster lookups.
3390 * Return: True if pushed, false otherwise.
3392 static inline bool mas_push_data(struct ma_state *mas, int height,
3393 struct maple_subtree_state *mast, bool left)
3395 unsigned char slot_total = mast->bn->b_end;
3396 unsigned char end, space, split;
3398 MA_STATE(tmp_mas, mas->tree, mas->index, mas->last);
3400 tmp_mas.depth = mast->l->depth;
3402 if (left && !mas_prev_sibling(&tmp_mas))
3404 else if (!left && !mas_next_sibling(&tmp_mas))
3407 end = mas_data_end(&tmp_mas);
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))
3414 if (mas->max == ULONG_MAX)
3417 if (slot_total >= space)
3420 /* Get the data; Fill mast->bn */
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;
3427 mas_mab_cp(&tmp_mas, 0, end, mast->bn, mast->bn->b_end);
3430 /* Configure mast for splitting of mast->bn */
3431 split = mt_slots[mast->bn->type] - 2;
3433 /* Switch mas to prev node */
3434 mat_add(mast->free, mas->node);
3436 /* Start using mast->l for the left side. */
3437 tmp_mas.node = mast->l->node;
3440 mat_add(mast->free, tmp_mas.node);
3441 tmp_mas.node = mast->r->node;
3443 split = slot_total - split;
3445 split = mab_no_null_split(mast->bn, split, mt_slots[mast->bn->type]);
3446 /* Update parent slot for split calculation. */
3448 mast->orig_l->offset += end + 1;
3450 mast_split_data(mast, mas, split);
3451 mast_fill_bnode(mast, mas, 2);
3452 mas_split_final_node(mast, mas, height + 1);
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.
3462 static int mas_split(struct ma_state *mas, struct maple_big_node *b_node)
3465 struct maple_subtree_state mast;
3467 unsigned char mid_split, split = 0;
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
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.
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);
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))
3501 mast.orig_l = &prev_l_mas;
3502 mast.orig_r = &prev_r_mas;
3506 while (height++ <= mas->depth) {
3507 if (mt_slots[b_node->type] > b_node->b_end) {
3508 mas_split_final_node(&mast, mas, height);
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);
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.
3522 /* Try to push left. */
3523 if (mas_push_data(mas, height, &mast, true))
3526 /* Try to push right. */
3527 if (mas_push_data(mas, height, &mast, false))
3530 split = mab_calc_split(mas, b_node, &mid_split, prev_l_mas.min);
3531 mast_split_data(&mast, mas, split);
3533 * Usually correct, mab_mas_cp in the above call overwrites
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;
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);
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.
3556 * Will always return false in RCU mode.
3558 * Return: True if node was reused, false otherwise.
3560 static inline bool mas_reuse_node(struct ma_wr_state *wr_mas,
3561 struct maple_big_node *bn, unsigned char end)
3563 /* Need to be rcu safe. */
3564 if (mt_in_rcu(wr_mas->mas->tree))
3567 if (end > bn->b_end) {
3568 int clear = mt_slots[wr_mas->type] - bn->b_end;
3570 memset(wr_mas->slots + bn->b_end, 0, sizeof(void *) * clear--);
3571 memset(wr_mas->pivots + bn->b_end, 0, sizeof(void *) * clear);
3573 mab_mas_cp(bn, 0, bn->b_end, wr_mas->mas, false);
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.
3583 static inline int mas_commit_b_node(struct ma_wr_state *wr_mas,
3584 struct maple_big_node *b_node, unsigned char end)
3586 struct maple_node *node;
3587 unsigned char b_end = b_node->b_end;
3588 enum maple_type b_type = b_node->type;
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);
3595 if (b_end >= mt_slots[b_type])
3596 return mas_split(wr_mas->mas, b_node);
3598 if (mas_reuse_node(wr_mas, b_node, end))
3601 mas_node_count(wr_mas->mas, 1);
3602 if (mas_is_err(wr_mas->mas))
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);
3611 mas_update_gap(wr_mas->mas);
3616 * mas_root_expand() - Expand a root to a node
3617 * @mas: The maple state
3618 * @entry: The entry to store into the tree
3620 static inline int mas_root_expand(struct ma_state *mas, void *entry)
3622 void *contents = mas_root_locked(mas);
3623 enum maple_type type = maple_leaf_64;
3624 struct maple_node *node;
3626 unsigned long *pivots;
3629 mas_node_count(mas, 1);
3630 if (unlikely(mas_is_err(mas)))
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);
3642 rcu_assign_pointer(slots[slot], contents);
3643 if (likely(mas->index > 1))
3646 pivots[slot++] = mas->index - 1;
3649 rcu_assign_pointer(slots[slot], entry);
3651 pivots[slot] = mas->last;
3652 if (mas->last != ULONG_MAX)
3655 mas_set_height(mas);
3656 ma_set_meta(node, maple_leaf_64, 0, slot);
3657 /* swap the new root into the tree */
3658 rcu_assign_pointer(mas->tree->ma_root, mte_mk_root(mas->node));
3662 static inline void mas_store_root(struct ma_state *mas, void *entry)
3664 if (likely((mas->last != 0) || (mas->index != 0)))
3665 mas_root_expand(mas, entry);
3666 else if (((unsigned long) (entry) & 3) == 2)
3667 mas_root_expand(mas, entry);
3669 rcu_assign_pointer(mas->tree->ma_root, entry);
3670 mas->node = MAS_START;
3675 * mas_is_span_wr() - Check if the write needs to be treated as a write that
3677 * @mas: The maple state
3678 * @piv: The pivot value being written
3679 * @type: The maple node type
3680 * @entry: The data to write
3682 * Spanning writes are writes that start in one node and end in another OR if
3683 * the write of a %NULL will cause the node to end with a %NULL.
3685 * Return: True if this is a spanning write, false otherwise.
3687 static bool mas_is_span_wr(struct ma_wr_state *wr_mas)
3690 unsigned long last = wr_mas->mas->last;
3691 unsigned long piv = wr_mas->r_max;
3692 enum maple_type type = wr_mas->type;
3693 void *entry = wr_mas->entry;
3695 /* Contained in this pivot */
3699 max = wr_mas->mas->max;
3700 if (unlikely(ma_is_leaf(type))) {
3701 /* Fits in the node, but may span slots. */
3705 /* Writes to the end of the node but not null. */
3706 if ((last == max) && entry)
3710 * Writing ULONG_MAX is not a spanning write regardless of the
3711 * value being written as long as the range fits in the node.
3713 if ((last == ULONG_MAX) && (last == max))
3715 } else if (piv == last) {
3719 /* Detect spanning store wr walk */
3720 if (last == ULONG_MAX)
3724 trace_ma_write(__func__, wr_mas->mas, piv, entry);
3729 static inline void mas_wr_walk_descend(struct ma_wr_state *wr_mas)
3731 wr_mas->type = mte_node_type(wr_mas->mas->node);
3732 mas_wr_node_walk(wr_mas);
3733 wr_mas->slots = ma_slots(wr_mas->node, wr_mas->type);
3736 static inline void mas_wr_walk_traverse(struct ma_wr_state *wr_mas)
3738 wr_mas->mas->max = wr_mas->r_max;
3739 wr_mas->mas->min = wr_mas->r_min;
3740 wr_mas->mas->node = wr_mas->content;
3741 wr_mas->mas->offset = 0;
3742 wr_mas->mas->depth++;
3745 * mas_wr_walk() - Walk the tree for a write.
3746 * @wr_mas: The maple write state
3748 * Uses mas_slot_locked() and does not need to worry about dead nodes.
3750 * Return: True if it's contained in a node, false on spanning write.
3752 static bool mas_wr_walk(struct ma_wr_state *wr_mas)
3754 struct ma_state *mas = wr_mas->mas;
3757 mas_wr_walk_descend(wr_mas);
3758 if (unlikely(mas_is_span_wr(wr_mas)))
3761 wr_mas->content = mas_slot_locked(mas, wr_mas->slots,
3763 if (ma_is_leaf(wr_mas->type))
3766 mas_wr_walk_traverse(wr_mas);
3772 static bool mas_wr_walk_index(struct ma_wr_state *wr_mas)
3774 struct ma_state *mas = wr_mas->mas;
3777 mas_wr_walk_descend(wr_mas);
3778 wr_mas->content = mas_slot_locked(mas, wr_mas->slots,
3780 if (ma_is_leaf(wr_mas->type))
3782 mas_wr_walk_traverse(wr_mas);
3788 * mas_extend_spanning_null() - Extend a store of a %NULL to include surrounding %NULLs.
3789 * @l_wr_mas: The left maple write state
3790 * @r_wr_mas: The right maple write state
3792 static inline void mas_extend_spanning_null(struct ma_wr_state *l_wr_mas,
3793 struct ma_wr_state *r_wr_mas)
3795 struct ma_state *r_mas = r_wr_mas->mas;
3796 struct ma_state *l_mas = l_wr_mas->mas;
3797 unsigned char l_slot;
3799 l_slot = l_mas->offset;
3800 if (!l_wr_mas->content)
3801 l_mas->index = l_wr_mas->r_min;
3803 if ((l_mas->index == l_wr_mas->r_min) &&
3805 !mas_slot_locked(l_mas, l_wr_mas->slots, l_slot - 1))) {
3807 l_mas->index = l_wr_mas->pivots[l_slot - 2] + 1;
3809 l_mas->index = l_mas->min;
3811 l_mas->offset = l_slot - 1;
3814 if (!r_wr_mas->content) {
3815 if (r_mas->last < r_wr_mas->r_max)
3816 r_mas->last = r_wr_mas->r_max;
3818 } else if ((r_mas->last == r_wr_mas->r_max) &&
3819 (r_mas->last < r_mas->max) &&
3820 !mas_slot_locked(r_mas, r_wr_mas->slots, r_mas->offset + 1)) {
3821 r_mas->last = mas_safe_pivot(r_mas, r_wr_mas->pivots,
3822 r_wr_mas->type, r_mas->offset + 1);
3827 static inline void *mas_state_walk(struct ma_state *mas)
3831 entry = mas_start(mas);
3832 if (mas_is_none(mas))
3835 if (mas_is_ptr(mas))
3838 return mtree_range_walk(mas);
3842 * mtree_lookup_walk() - Internal quick lookup that does not keep maple state up
3845 * @mas: The maple state.
3847 * Note: Leaves mas in undesirable state.
3848 * Return: The entry for @mas->index or %NULL on dead node.
3850 static inline void *mtree_lookup_walk(struct ma_state *mas)
3852 unsigned long *pivots;
3853 unsigned char offset;
3854 struct maple_node *node;
3855 struct maple_enode *next;
3856 enum maple_type type;
3865 node = mte_to_node(next);
3866 type = mte_node_type(next);
3867 pivots = ma_pivots(node, type);
3868 end = ma_data_end(node, type, pivots, max);
3869 if (unlikely(ma_dead_node(node)))
3872 if (pivots[offset] >= mas->index) {
3873 max = pivots[offset];
3876 } while (++offset < end);
3878 slots = ma_slots(node, type);
3879 next = mt_slot(mas->tree, slots, offset);
3880 if (unlikely(ma_dead_node(node)))
3882 } while (!ma_is_leaf(type));
3884 return (void *) next;
3892 * mas_new_root() - Create a new root node that only contains the entry passed
3894 * @mas: The maple state
3895 * @entry: The entry to store.
3897 * Only valid when the index == 0 and the last == ULONG_MAX
3899 * Return 0 on error, 1 on success.
3901 static inline int mas_new_root(struct ma_state *mas, void *entry)
3903 struct maple_enode *root = mas_root_locked(mas);
3904 enum maple_type type = maple_leaf_64;
3905 struct maple_node *node;
3907 unsigned long *pivots;
3909 if (!entry && !mas->index && mas->last == ULONG_MAX) {
3911 mas_set_height(mas);
3912 rcu_assign_pointer(mas->tree->ma_root, entry);
3913 mas->node = MAS_START;
3917 mas_node_count(mas, 1);
3918 if (mas_is_err(mas))
3921 node = mas_pop_node(mas);
3922 pivots = ma_pivots(node, type);
3923 slots = ma_slots(node, type);
3924 node->parent = ma_parent_ptr(
3925 ((unsigned long)mas->tree | MA_ROOT_PARENT));
3926 mas->node = mt_mk_node(node, type);
3927 rcu_assign_pointer(slots[0], entry);
3928 pivots[0] = mas->last;
3930 mas_set_height(mas);
3931 rcu_assign_pointer(mas->tree->ma_root, mte_mk_root(mas->node));
3934 if (xa_is_node(root))
3935 mte_destroy_walk(root, mas->tree);
3940 * mas_wr_spanning_store() - Create a subtree with the store operation completed
3941 * and new nodes where necessary, then place the sub-tree in the actual tree.
3942 * Note that mas is expected to point to the node which caused the store to
3944 * @wr_mas: The maple write state
3946 * Return: 0 on error, positive on success.
3948 static inline int mas_wr_spanning_store(struct ma_wr_state *wr_mas)
3950 struct maple_subtree_state mast;
3951 struct maple_big_node b_node;
3952 struct ma_state *mas;
3953 unsigned char height;
3955 /* Left and Right side of spanning store */
3956 MA_STATE(l_mas, NULL, 0, 0);
3957 MA_STATE(r_mas, NULL, 0, 0);
3959 MA_WR_STATE(r_wr_mas, &r_mas, wr_mas->entry);
3960 MA_WR_STATE(l_wr_mas, &l_mas, wr_mas->entry);
3963 * A store operation that spans multiple nodes is called a spanning
3964 * store and is handled early in the store call stack by the function
3965 * mas_is_span_wr(). When a spanning store is identified, the maple
3966 * state is duplicated. The first maple state walks the left tree path
3967 * to ``index``, the duplicate walks the right tree path to ``last``.
3968 * The data in the two nodes are combined into a single node, two nodes,
3969 * or possibly three nodes (see the 3-way split above). A ``NULL``
3970 * written to the last entry of a node is considered a spanning store as
3971 * a rebalance is required for the operation to complete and an overflow
3972 * of data may happen.
3975 trace_ma_op(__func__, mas);
3977 if (unlikely(!mas->index && mas->last == ULONG_MAX))
3978 return mas_new_root(mas, wr_mas->entry);
3980 * Node rebalancing may occur due to this store, so there may be three new
3981 * entries per level plus a new root.
3983 height = mas_mt_height(mas);
3984 mas_node_count(mas, 1 + height * 3);
3985 if (mas_is_err(mas))
3989 * Set up right side. Need to get to the next offset after the spanning
3990 * store to ensure it's not NULL and to combine both the next node and
3991 * the node with the start together.
3994 /* Avoid overflow, walk to next slot in the tree. */
3998 r_mas.index = r_mas.last;
3999 mas_wr_walk_index(&r_wr_mas);
4000 r_mas.last = r_mas.index = mas->last;
4002 /* Set up left side. */
4004 mas_wr_walk_index(&l_wr_mas);
4006 if (!wr_mas->entry) {
4007 mas_extend_spanning_null(&l_wr_mas, &r_wr_mas);
4008 mas->offset = l_mas.offset;
4009 mas->index = l_mas.index;
4010 mas->last = l_mas.last = r_mas.last;
4013 /* expanding NULLs may make this cover the entire range */
4014 if (!l_mas.index && r_mas.last == ULONG_MAX) {
4015 mas_set_range(mas, 0, ULONG_MAX);
4016 return mas_new_root(mas, wr_mas->entry);
4019 memset(&b_node, 0, sizeof(struct maple_big_node));
4020 /* Copy l_mas and store the value in b_node. */
4021 mas_store_b_node(&l_wr_mas, &b_node, l_wr_mas.node_end);
4022 /* Copy r_mas into b_node. */
4023 if (r_mas.offset <= r_wr_mas.node_end)
4024 mas_mab_cp(&r_mas, r_mas.offset, r_wr_mas.node_end,
4025 &b_node, b_node.b_end + 1);
4029 /* Stop spanning searches by searching for just index. */
4030 l_mas.index = l_mas.last = mas->index;
4033 mast.orig_l = &l_mas;
4034 mast.orig_r = &r_mas;
4035 /* Combine l_mas and r_mas and split them up evenly again. */
4036 return mas_spanning_rebalance(mas, &mast, height + 1);
4040 * mas_wr_node_store() - Attempt to store the value in a node
4041 * @wr_mas: The maple write state
4043 * Attempts to reuse the node, but may allocate.
4045 * Return: True if stored, false otherwise
4047 static inline bool mas_wr_node_store(struct ma_wr_state *wr_mas)
4049 struct ma_state *mas = wr_mas->mas;
4050 void __rcu **dst_slots;
4051 unsigned long *dst_pivots;
4052 unsigned char dst_offset;
4053 unsigned char new_end = wr_mas->node_end;
4054 unsigned char offset;
4055 unsigned char node_slots = mt_slots[wr_mas->type];
4056 struct maple_node reuse, *newnode;
4057 unsigned char copy_size, max_piv = mt_pivots[wr_mas->type];
4058 bool in_rcu = mt_in_rcu(mas->tree);
4060 offset = mas->offset;
4061 if (mas->last == wr_mas->r_max) {
4062 /* runs right to the end of the node */
4063 if (mas->last == mas->max)
4065 /* don't copy this offset */
4066 wr_mas->offset_end++;
4067 } else if (mas->last < wr_mas->r_max) {
4068 /* new range ends in this range */
4069 if (unlikely(wr_mas->r_max == ULONG_MAX))
4070 mas_bulk_rebalance(mas, wr_mas->node_end, wr_mas->type);
4074 if (wr_mas->end_piv == mas->last)
4075 wr_mas->offset_end++;
4077 new_end -= wr_mas->offset_end - offset - 1;
4080 /* new range starts within a range */
4081 if (wr_mas->r_min < mas->index)
4084 /* Not enough room */
4085 if (new_end >= node_slots)
4088 /* Not enough data. */
4089 if (!mte_is_root(mas->node) && (new_end <= mt_min_slots[wr_mas->type]) &&
4090 !(mas->mas_flags & MA_STATE_BULK))
4095 mas_node_count(mas, 1);
4096 if (mas_is_err(mas))
4099 newnode = mas_pop_node(mas);
4101 memset(&reuse, 0, sizeof(struct maple_node));
4105 newnode->parent = mas_mn(mas)->parent;
4106 dst_pivots = ma_pivots(newnode, wr_mas->type);
4107 dst_slots = ma_slots(newnode, wr_mas->type);
4108 /* Copy from start to insert point */
4109 memcpy(dst_pivots, wr_mas->pivots, sizeof(unsigned long) * (offset + 1));
4110 memcpy(dst_slots, wr_mas->slots, sizeof(void *) * (offset + 1));
4111 dst_offset = offset;
4113 /* Handle insert of new range starting after old range */
4114 if (wr_mas->r_min < mas->index) {
4116 rcu_assign_pointer(dst_slots[dst_offset], wr_mas->content);
4117 dst_pivots[dst_offset++] = mas->index - 1;
4120 /* Store the new entry and range end. */
4121 if (dst_offset < max_piv)
4122 dst_pivots[dst_offset] = mas->last;
4123 mas->offset = dst_offset;
4124 rcu_assign_pointer(dst_slots[dst_offset], wr_mas->entry);
4127 * this range wrote to the end of the node or it overwrote the rest of
4130 if (wr_mas->offset_end > wr_mas->node_end || mas->last >= mas->max) {
4131 new_end = dst_offset;
4136 /* Copy to the end of node if necessary. */
4137 copy_size = wr_mas->node_end - wr_mas->offset_end + 1;
4138 memcpy(dst_slots + dst_offset, wr_mas->slots + wr_mas->offset_end,
4139 sizeof(void *) * copy_size);
4140 if (dst_offset < max_piv) {
4141 if (copy_size > max_piv - dst_offset)
4142 copy_size = max_piv - dst_offset;
4144 memcpy(dst_pivots + dst_offset,
4145 wr_mas->pivots + wr_mas->offset_end,
4146 sizeof(unsigned long) * copy_size);
4149 if ((wr_mas->node_end == node_slots - 1) && (new_end < node_slots - 1))
4150 dst_pivots[new_end] = mas->max;
4153 mas_leaf_set_meta(mas, newnode, dst_pivots, maple_leaf_64, new_end);
4155 mas->node = mt_mk_node(newnode, wr_mas->type);
4156 mas_replace(mas, false);
4158 memcpy(wr_mas->node, newnode, sizeof(struct maple_node));
4160 trace_ma_write(__func__, mas, 0, wr_mas->entry);
4161 mas_update_gap(mas);
4166 * mas_wr_slot_store: Attempt to store a value in a slot.
4167 * @wr_mas: the maple write state
4169 * Return: True if stored, false otherwise
4171 static inline bool mas_wr_slot_store(struct ma_wr_state *wr_mas)
4173 struct ma_state *mas = wr_mas->mas;
4174 unsigned long lmax; /* Logical max. */
4175 unsigned char offset = mas->offset;
4177 if ((wr_mas->r_max > mas->last) && ((wr_mas->r_min != mas->index) ||
4178 (offset != wr_mas->node_end)))
4181 if (offset == wr_mas->node_end - 1)
4184 lmax = wr_mas->pivots[offset + 1];
4186 /* going to overwrite too many slots. */
4187 if (lmax < mas->last)
4190 if (wr_mas->r_min == mas->index) {
4191 /* overwriting two or more ranges with one. */
4192 if (lmax == mas->last)
4195 /* Overwriting all of offset and a portion of offset + 1. */
4196 rcu_assign_pointer(wr_mas->slots[offset], wr_mas->entry);
4197 wr_mas->pivots[offset] = mas->last;
4201 /* Doesn't end on the next range end. */
4202 if (lmax != mas->last)
4205 /* Overwriting a portion of offset and all of offset + 1 */
4206 if ((offset + 1 < mt_pivots[wr_mas->type]) &&
4207 (wr_mas->entry || wr_mas->pivots[offset + 1]))
4208 wr_mas->pivots[offset + 1] = mas->last;
4210 rcu_assign_pointer(wr_mas->slots[offset + 1], wr_mas->entry);
4211 wr_mas->pivots[offset] = mas->index - 1;
4212 mas->offset++; /* Keep mas accurate. */
4215 trace_ma_write(__func__, mas, 0, wr_mas->entry);
4216 mas_update_gap(mas);
4220 static inline void mas_wr_end_piv(struct ma_wr_state *wr_mas)
4222 while ((wr_mas->mas->last > wr_mas->end_piv) &&
4223 (wr_mas->offset_end < wr_mas->node_end))
4224 wr_mas->end_piv = wr_mas->pivots[++wr_mas->offset_end];
4226 if (wr_mas->mas->last > wr_mas->end_piv)
4227 wr_mas->end_piv = wr_mas->mas->max;
4230 static inline void mas_wr_extend_null(struct ma_wr_state *wr_mas)
4232 struct ma_state *mas = wr_mas->mas;
4234 if (mas->last < wr_mas->end_piv && !wr_mas->slots[wr_mas->offset_end])
4235 mas->last = wr_mas->end_piv;
4237 /* Check next slot(s) if we are overwriting the end */
4238 if ((mas->last == wr_mas->end_piv) &&
4239 (wr_mas->node_end != wr_mas->offset_end) &&
4240 !wr_mas->slots[wr_mas->offset_end + 1]) {
4241 wr_mas->offset_end++;
4242 if (wr_mas->offset_end == wr_mas->node_end)
4243 mas->last = mas->max;
4245 mas->last = wr_mas->pivots[wr_mas->offset_end];
4246 wr_mas->end_piv = mas->last;
4249 if (!wr_mas->content) {
4250 /* If this one is null, the next and prev are not */
4251 mas->index = wr_mas->r_min;
4253 /* Check prev slot if we are overwriting the start */
4254 if (mas->index == wr_mas->r_min && mas->offset &&
4255 !wr_mas->slots[mas->offset - 1]) {
4257 wr_mas->r_min = mas->index =
4258 mas_safe_min(mas, wr_mas->pivots, mas->offset);
4259 wr_mas->r_max = wr_mas->pivots[mas->offset];
4264 static inline bool mas_wr_append(struct ma_wr_state *wr_mas)
4266 unsigned char end = wr_mas->node_end;
4267 unsigned char new_end = end + 1;
4268 struct ma_state *mas = wr_mas->mas;
4269 unsigned char node_pivots = mt_pivots[wr_mas->type];
4271 if ((mas->index != wr_mas->r_min) && (mas->last == wr_mas->r_max)) {
4272 if (new_end < node_pivots)
4273 wr_mas->pivots[new_end] = wr_mas->pivots[end];
4275 if (new_end < node_pivots)
4276 ma_set_meta(wr_mas->node, maple_leaf_64, 0, new_end);
4278 rcu_assign_pointer(wr_mas->slots[new_end], wr_mas->entry);
4279 mas->offset = new_end;
4280 wr_mas->pivots[end] = mas->index - 1;
4285 if ((mas->index == wr_mas->r_min) && (mas->last < wr_mas->r_max)) {
4286 if (new_end < node_pivots)
4287 wr_mas->pivots[new_end] = wr_mas->pivots[end];
4289 rcu_assign_pointer(wr_mas->slots[new_end], wr_mas->content);
4290 if (new_end < node_pivots)
4291 ma_set_meta(wr_mas->node, maple_leaf_64, 0, new_end);
4293 wr_mas->pivots[end] = mas->last;
4294 rcu_assign_pointer(wr_mas->slots[end], wr_mas->entry);
4302 * mas_wr_bnode() - Slow path for a modification.
4303 * @wr_mas: The write maple state
4305 * This is where split, rebalance end up.
4307 static void mas_wr_bnode(struct ma_wr_state *wr_mas)
4309 struct maple_big_node b_node;
4311 trace_ma_write(__func__, wr_mas->mas, 0, wr_mas->entry);
4312 memset(&b_node, 0, sizeof(struct maple_big_node));
4313 mas_store_b_node(wr_mas, &b_node, wr_mas->offset_end);
4314 mas_commit_b_node(wr_mas, &b_node, wr_mas->node_end);
4317 static inline void mas_wr_modify(struct ma_wr_state *wr_mas)
4319 unsigned char node_slots;
4320 unsigned char node_size;
4321 struct ma_state *mas = wr_mas->mas;
4323 /* Direct replacement */
4324 if (wr_mas->r_min == mas->index && wr_mas->r_max == mas->last) {
4325 rcu_assign_pointer(wr_mas->slots[mas->offset], wr_mas->entry);
4326 if (!!wr_mas->entry ^ !!wr_mas->content)
4327 mas_update_gap(mas);
4331 /* Attempt to append */
4332 node_slots = mt_slots[wr_mas->type];
4333 node_size = wr_mas->node_end - wr_mas->offset_end + mas->offset + 2;
4334 if (mas->max == ULONG_MAX)
4337 /* slot and node store will not fit, go to the slow path */
4338 if (unlikely(node_size >= node_slots))
4341 if (wr_mas->entry && (wr_mas->node_end < node_slots - 1) &&
4342 (mas->offset == wr_mas->node_end) && mas_wr_append(wr_mas)) {
4343 if (!wr_mas->content || !wr_mas->entry)
4344 mas_update_gap(mas);
4348 if ((wr_mas->offset_end - mas->offset <= 1) && mas_wr_slot_store(wr_mas))
4350 else if (mas_wr_node_store(wr_mas))
4353 if (mas_is_err(mas))
4357 mas_wr_bnode(wr_mas);
4361 * mas_wr_store_entry() - Internal call to store a value
4362 * @mas: The maple state
4363 * @entry: The entry to store.
4365 * Return: The contents that was stored at the index.
4367 static inline void *mas_wr_store_entry(struct ma_wr_state *wr_mas)
4369 struct ma_state *mas = wr_mas->mas;
4371 wr_mas->content = mas_start(mas);
4372 if (mas_is_none(mas) || mas_is_ptr(mas)) {
4373 mas_store_root(mas, wr_mas->entry);
4374 return wr_mas->content;
4377 if (unlikely(!mas_wr_walk(wr_mas))) {
4378 mas_wr_spanning_store(wr_mas);
4379 return wr_mas->content;
4382 /* At this point, we are at the leaf node that needs to be altered. */
4383 wr_mas->end_piv = wr_mas->r_max;
4384 mas_wr_end_piv(wr_mas);
4387 mas_wr_extend_null(wr_mas);
4389 /* New root for a single pointer */
4390 if (unlikely(!mas->index && mas->last == ULONG_MAX)) {
4391 mas_new_root(mas, wr_mas->entry);
4392 return wr_mas->content;
4395 mas_wr_modify(wr_mas);
4396 return wr_mas->content;
4400 * mas_insert() - Internal call to insert a value
4401 * @mas: The maple state
4402 * @entry: The entry to store
4404 * Return: %NULL or the contents that already exists at the requested index
4405 * otherwise. The maple state needs to be checked for error conditions.
4407 static inline void *mas_insert(struct ma_state *mas, void *entry)
4409 MA_WR_STATE(wr_mas, mas, entry);
4412 * Inserting a new range inserts either 0, 1, or 2 pivots within the
4413 * tree. If the insert fits exactly into an existing gap with a value
4414 * of NULL, then the slot only needs to be written with the new value.
4415 * If the range being inserted is adjacent to another range, then only a
4416 * single pivot needs to be inserted (as well as writing the entry). If
4417 * the new range is within a gap but does not touch any other ranges,
4418 * then two pivots need to be inserted: the start - 1, and the end. As
4419 * usual, the entry must be written. Most operations require a new node
4420 * to be allocated and replace an existing node to ensure RCU safety,
4421 * when in RCU mode. The exception to requiring a newly allocated node
4422 * is when inserting at the end of a node (appending). When done
4423 * carefully, appending can reuse the node in place.
4425 wr_mas.content = mas_start(mas);
4429 if (mas_is_none(mas) || mas_is_ptr(mas)) {
4430 mas_store_root(mas, entry);
4434 /* spanning writes always overwrite something */
4435 if (!mas_wr_walk(&wr_mas))
4438 /* At this point, we are at the leaf node that needs to be altered. */
4439 wr_mas.offset_end = mas->offset;
4440 wr_mas.end_piv = wr_mas.r_max;
4442 if (wr_mas.content || (mas->last > wr_mas.r_max))
4448 mas_wr_modify(&wr_mas);
4449 return wr_mas.content;
4452 mas_set_err(mas, -EEXIST);
4453 return wr_mas.content;
4458 * mas_prev_node() - Find the prev non-null entry at the same level in the
4459 * tree. The prev value will be mas->node[mas->offset] or MAS_NONE.
4460 * @mas: The maple state
4461 * @min: The lower limit to search
4463 * The prev node value will be mas->node[mas->offset] or MAS_NONE.
4464 * Return: 1 if the node is dead, 0 otherwise.
4466 static inline int mas_prev_node(struct ma_state *mas, unsigned long min)
4471 struct maple_node *node;
4472 struct maple_enode *enode;
4473 unsigned long *pivots;
4475 if (mas_is_none(mas))
4481 if (ma_is_root(node))
4485 if (unlikely(mas_ascend(mas)))
4487 offset = mas->offset;
4492 mt = mte_node_type(mas->node);
4494 slots = ma_slots(node, mt);
4495 pivots = ma_pivots(node, mt);
4496 mas->max = pivots[offset];
4498 mas->min = pivots[offset - 1] + 1;
4499 if (unlikely(ma_dead_node(node)))
4507 enode = mas_slot(mas, slots, offset);
4508 if (unlikely(ma_dead_node(node)))
4512 mt = mte_node_type(mas->node);
4514 slots = ma_slots(node, mt);
4515 pivots = ma_pivots(node, mt);
4516 offset = ma_data_end(node, mt, pivots, mas->max);
4518 mas->min = pivots[offset - 1] + 1;
4520 if (offset < mt_pivots[mt])
4521 mas->max = pivots[offset];
4527 mas->node = mas_slot(mas, slots, offset);
4528 if (unlikely(ma_dead_node(node)))
4531 mas->offset = mas_data_end(mas);
4532 if (unlikely(mte_dead_node(mas->node)))
4538 mas->offset = offset;
4540 mas->min = pivots[offset - 1] + 1;
4542 if (unlikely(ma_dead_node(node)))
4545 mas->node = MAS_NONE;
4550 * mas_next_node() - Get the next node at the same level in the tree.
4551 * @mas: The maple state
4552 * @max: The maximum pivot value to check.
4554 * The next value will be mas->node[mas->offset] or MAS_NONE.
4555 * Return: 1 on dead node, 0 otherwise.
4557 static inline int mas_next_node(struct ma_state *mas, struct maple_node *node,
4560 unsigned long min, pivot;
4561 unsigned long *pivots;
4562 struct maple_enode *enode;
4564 unsigned char offset;
4568 if (mas->max >= max)
4573 if (ma_is_root(node))
4580 if (unlikely(mas_ascend(mas)))
4583 offset = mas->offset;
4586 mt = mte_node_type(mas->node);
4587 pivots = ma_pivots(node, mt);
4588 } while (unlikely(offset == ma_data_end(node, mt, pivots, mas->max)));
4590 slots = ma_slots(node, mt);
4591 pivot = mas_safe_pivot(mas, pivots, ++offset, mt);
4592 while (unlikely(level > 1)) {
4593 /* Descend, if necessary */
4594 enode = mas_slot(mas, slots, offset);
4595 if (unlikely(ma_dead_node(node)))
4601 mt = mte_node_type(mas->node);
4602 slots = ma_slots(node, mt);
4603 pivots = ma_pivots(node, mt);
4608 enode = mas_slot(mas, slots, offset);
4609 if (unlikely(ma_dead_node(node)))
4618 if (unlikely(ma_dead_node(node)))
4621 mas->node = MAS_NONE;
4626 * mas_next_nentry() - Get the next node entry
4627 * @mas: The maple state
4628 * @max: The maximum value to check
4629 * @*range_start: Pointer to store the start of the range.
4631 * Sets @mas->offset to the offset of the next node entry, @mas->last to the
4632 * pivot of the entry.
4634 * Return: The next entry, %NULL otherwise
4636 static inline void *mas_next_nentry(struct ma_state *mas,
4637 struct maple_node *node, unsigned long max, enum maple_type type)
4639 unsigned char count;
4640 unsigned long pivot;
4641 unsigned long *pivots;
4645 if (mas->last == mas->max) {
4646 mas->index = mas->max;
4650 pivots = ma_pivots(node, type);
4651 slots = ma_slots(node, type);
4652 mas->index = mas_safe_min(mas, pivots, mas->offset);
4653 count = ma_data_end(node, type, pivots, mas->max);
4654 if (ma_dead_node(node))
4657 if (mas->index > max)
4660 if (mas->offset > count)
4663 while (mas->offset < count) {
4664 pivot = pivots[mas->offset];
4665 entry = mas_slot(mas, slots, mas->offset);
4666 if (ma_dead_node(node))
4675 mas->index = pivot + 1;
4679 if (mas->index > mas->max) {
4680 mas->index = mas->last;
4684 pivot = mas_safe_pivot(mas, pivots, mas->offset, type);
4685 entry = mas_slot(mas, slots, mas->offset);
4686 if (ma_dead_node(node))
4700 static inline void mas_rewalk(struct ma_state *mas, unsigned long index)
4704 mas_set(mas, index);
4705 mas_state_walk(mas);
4706 if (mas_is_start(mas))
4714 * mas_next_entry() - Internal function to get the next entry.
4715 * @mas: The maple state
4716 * @limit: The maximum range start.
4718 * Set the @mas->node to the next entry and the range_start to
4719 * the beginning value for the entry. Does not check beyond @limit.
4720 * Sets @mas->index and @mas->last to the limit if it is hit.
4721 * Restarts on dead nodes.
4723 * Return: the next entry or %NULL.
4725 static inline void *mas_next_entry(struct ma_state *mas, unsigned long limit)
4728 struct maple_enode *prev_node;
4729 struct maple_node *node;
4730 unsigned char offset;
4734 if (mas->index > limit) {
4735 mas->index = mas->last = limit;
4741 offset = mas->offset;
4742 prev_node = mas->node;
4744 mt = mte_node_type(mas->node);
4746 if (unlikely(mas->offset >= mt_slots[mt])) {
4747 mas->offset = mt_slots[mt] - 1;
4751 while (!mas_is_none(mas)) {
4752 entry = mas_next_nentry(mas, node, limit, mt);
4753 if (unlikely(ma_dead_node(node))) {
4754 mas_rewalk(mas, last);
4761 if (unlikely((mas->index > limit)))
4765 prev_node = mas->node;
4766 offset = mas->offset;
4767 if (unlikely(mas_next_node(mas, node, limit))) {
4768 mas_rewalk(mas, last);
4773 mt = mte_node_type(mas->node);
4776 mas->index = mas->last = limit;
4777 mas->offset = offset;
4778 mas->node = prev_node;
4783 * mas_prev_nentry() - Get the previous node entry.
4784 * @mas: The maple state.
4785 * @limit: The lower limit to check for a value.
4787 * Return: the entry, %NULL otherwise.
4789 static inline void *mas_prev_nentry(struct ma_state *mas, unsigned long limit,
4790 unsigned long index)
4792 unsigned long pivot, min;
4793 unsigned char offset;
4794 struct maple_node *mn;
4796 unsigned long *pivots;
4805 mt = mte_node_type(mas->node);
4806 offset = mas->offset - 1;
4807 if (offset >= mt_slots[mt])
4808 offset = mt_slots[mt] - 1;
4810 slots = ma_slots(mn, mt);
4811 pivots = ma_pivots(mn, mt);
4812 if (offset == mt_pivots[mt])
4815 pivot = pivots[offset];
4817 if (unlikely(ma_dead_node(mn))) {
4818 mas_rewalk(mas, index);
4822 while (offset && ((!mas_slot(mas, slots, offset) && pivot >= limit) ||
4824 pivot = pivots[--offset];
4826 min = mas_safe_min(mas, pivots, offset);
4827 entry = mas_slot(mas, slots, offset);
4828 if (unlikely(ma_dead_node(mn))) {
4829 mas_rewalk(mas, index);
4833 if (likely(entry)) {
4834 mas->offset = offset;
4841 static inline void *mas_prev_entry(struct ma_state *mas, unsigned long min)
4845 if (mas->index < min) {
4846 mas->index = mas->last = min;
4851 while (likely(!mas_is_none(mas))) {
4852 entry = mas_prev_nentry(mas, min, mas->index);
4853 if (unlikely(mas->last < min))
4859 if (unlikely(mas_prev_node(mas, min))) {
4860 mas_rewalk(mas, mas->index);
4869 mas->index = mas->last = min;
4874 * mas_rev_awalk() - Internal function. Reverse allocation walk. Find the
4875 * highest gap address of a given size in a given node and descend.
4876 * @mas: The maple state
4877 * @size: The needed size.
4879 * Return: True if found in a leaf, false otherwise.
4882 static bool mas_rev_awalk(struct ma_state *mas, unsigned long size)
4884 enum maple_type type = mte_node_type(mas->node);
4885 struct maple_node *node = mas_mn(mas);
4886 unsigned long *pivots, *gaps;
4888 unsigned long gap = 0;
4889 unsigned long max, min;
4890 unsigned char offset;
4892 if (unlikely(mas_is_err(mas)))
4895 if (ma_is_dense(type)) {
4897 mas->offset = (unsigned char)(mas->index - mas->min);
4901 pivots = ma_pivots(node, type);
4902 slots = ma_slots(node, type);
4903 gaps = ma_gaps(node, type);
4904 offset = mas->offset;
4905 min = mas_safe_min(mas, pivots, offset);
4906 /* Skip out of bounds. */
4907 while (mas->last < min)
4908 min = mas_safe_min(mas, pivots, --offset);
4910 max = mas_safe_pivot(mas, pivots, offset, type);
4911 while (mas->index <= max) {
4915 else if (!mas_slot(mas, slots, offset))
4916 gap = max - min + 1;
4919 if ((size <= gap) && (size <= mas->last - min + 1))
4923 /* Skip the next slot, it cannot be a gap. */
4928 max = pivots[offset];
4929 min = mas_safe_min(mas, pivots, offset);
4939 min = mas_safe_min(mas, pivots, offset);
4942 if (unlikely((mas->index > max) || (size - 1 > max - mas->index)))
4945 if (unlikely(ma_is_leaf(type))) {
4946 mas->offset = offset;
4948 mas->max = min + gap - 1;
4952 /* descend, only happens under lock. */
4953 mas->node = mas_slot(mas, slots, offset);
4956 mas->offset = mas_data_end(mas);
4960 if (!mte_is_root(mas->node))
4964 mas_set_err(mas, -EBUSY);
4968 static inline bool mas_anode_descend(struct ma_state *mas, unsigned long size)
4970 enum maple_type type = mte_node_type(mas->node);
4971 unsigned long pivot, min, gap = 0;
4972 unsigned char offset;
4973 unsigned long *gaps;
4974 unsigned long *pivots = ma_pivots(mas_mn(mas), type);
4975 void __rcu **slots = ma_slots(mas_mn(mas), type);
4978 if (ma_is_dense(type)) {
4979 mas->offset = (unsigned char)(mas->index - mas->min);
4983 gaps = ma_gaps(mte_to_node(mas->node), type);
4984 offset = mas->offset;
4985 min = mas_safe_min(mas, pivots, offset);
4986 for (; offset < mt_slots[type]; offset++) {
4987 pivot = mas_safe_pivot(mas, pivots, offset, type);
4988 if (offset && !pivot)
4991 /* Not within lower bounds */
4992 if (mas->index > pivot)
4997 else if (!mas_slot(mas, slots, offset))
4998 gap = min(pivot, mas->last) - max(mas->index, min) + 1;
5003 if (ma_is_leaf(type)) {
5007 if (mas->index <= pivot) {
5008 mas->node = mas_slot(mas, slots, offset);
5017 if (mas->last <= pivot) {
5018 mas_set_err(mas, -EBUSY);
5023 if (mte_is_root(mas->node))
5026 mas->offset = offset;
5031 * mas_walk() - Search for @mas->index in the tree.
5032 * @mas: The maple state.
5034 * mas->index and mas->last will be set to the range if there is a value. If
5035 * mas->node is MAS_NONE, reset to MAS_START.
5037 * Return: the entry at the location or %NULL.
5039 void *mas_walk(struct ma_state *mas)
5044 entry = mas_state_walk(mas);
5045 if (mas_is_start(mas))
5048 if (mas_is_ptr(mas)) {
5053 mas->last = ULONG_MAX;
5058 if (mas_is_none(mas)) {
5060 mas->last = ULONG_MAX;
5065 EXPORT_SYMBOL_GPL(mas_walk);
5067 static inline bool mas_rewind_node(struct ma_state *mas)
5072 if (mte_is_root(mas->node)) {
5082 mas->offset = --slot;
5087 * mas_skip_node() - Internal function. Skip over a node.
5088 * @mas: The maple state.
5090 * Return: true if there is another node, false otherwise.
5092 static inline bool mas_skip_node(struct ma_state *mas)
5094 if (mas_is_err(mas))
5098 if (mte_is_root(mas->node)) {
5099 if (mas->offset >= mas_data_end(mas)) {
5100 mas_set_err(mas, -EBUSY);
5106 } while (mas->offset >= mas_data_end(mas));
5113 * mas_awalk() - Allocation walk. Search from low address to high, for a gap of
5115 * @mas: The maple state
5116 * @size: The size of the gap required
5118 * Search between @mas->index and @mas->last for a gap of @size.
5120 static inline void mas_awalk(struct ma_state *mas, unsigned long size)
5122 struct maple_enode *last = NULL;
5125 * There are 4 options:
5126 * go to child (descend)
5127 * go back to parent (ascend)
5128 * no gap found. (return, slot == MAPLE_NODE_SLOTS)
5129 * found the gap. (return, slot != MAPLE_NODE_SLOTS)
5131 while (!mas_is_err(mas) && !mas_anode_descend(mas, size)) {
5132 if (last == mas->node)
5140 * mas_fill_gap() - Fill a located gap with @entry.
5141 * @mas: The maple state
5142 * @entry: The value to store
5143 * @slot: The offset into the node to store the @entry
5144 * @size: The size of the entry
5145 * @index: The start location
5147 static inline void mas_fill_gap(struct ma_state *mas, void *entry,
5148 unsigned char slot, unsigned long size, unsigned long *index)
5150 MA_WR_STATE(wr_mas, mas, entry);
5151 unsigned char pslot = mte_parent_slot(mas->node);
5152 struct maple_enode *mn = mas->node;
5153 unsigned long *pivots;
5154 enum maple_type ptype;
5156 * mas->index is the start address for the search
5157 * which may no longer be needed.
5158 * mas->last is the end address for the search
5161 *index = mas->index;
5162 mas->last = mas->index + size - 1;
5165 * It is possible that using mas->max and mas->min to correctly
5166 * calculate the index and last will cause an issue in the gap
5167 * calculation, so fix the ma_state here
5170 ptype = mte_node_type(mas->node);
5171 pivots = ma_pivots(mas_mn(mas), ptype);
5172 mas->max = mas_safe_pivot(mas, pivots, pslot, ptype);
5173 mas->min = mas_safe_min(mas, pivots, pslot);
5176 mas_wr_store_entry(&wr_mas);
5180 * mas_sparse_area() - Internal function. Return upper or lower limit when
5181 * searching for a gap in an empty tree.
5182 * @mas: The maple state
5183 * @min: the minimum range
5184 * @max: The maximum range
5185 * @size: The size of the gap
5186 * @fwd: Searching forward or back
5188 static inline void mas_sparse_area(struct ma_state *mas, unsigned long min,
5189 unsigned long max, unsigned long size, bool fwd)
5191 unsigned long start = 0;
5193 if (!unlikely(mas_is_none(mas)))
5202 mas->last = start + size - 1;
5210 * mas_empty_area() - Get the lowest address within the range that is
5211 * sufficient for the size requested.
5212 * @mas: The maple state
5213 * @min: The lowest value of the range
5214 * @max: The highest value of the range
5215 * @size: The size needed
5217 int mas_empty_area(struct ma_state *mas, unsigned long min,
5218 unsigned long max, unsigned long size)
5220 unsigned char offset;
5221 unsigned long *pivots;
5224 if (mas_is_start(mas))
5226 else if (mas->offset >= 2)
5228 else if (!mas_skip_node(mas))
5232 if (mas_is_none(mas) || mas_is_ptr(mas)) {
5233 mas_sparse_area(mas, min, max, size, true);
5237 /* The start of the window can only be within these values */
5240 mas_awalk(mas, size);
5242 if (unlikely(mas_is_err(mas)))
5243 return xa_err(mas->node);
5245 offset = mas->offset;
5246 if (unlikely(offset == MAPLE_NODE_SLOTS))
5249 mt = mte_node_type(mas->node);
5250 pivots = ma_pivots(mas_mn(mas), mt);
5252 mas->min = pivots[offset - 1] + 1;
5254 if (offset < mt_pivots[mt])
5255 mas->max = pivots[offset];
5257 if (mas->index < mas->min)
5258 mas->index = mas->min;
5260 mas->last = mas->index + size - 1;
5263 EXPORT_SYMBOL_GPL(mas_empty_area);
5266 * mas_empty_area_rev() - Get the highest address within the range that is
5267 * sufficient for the size requested.
5268 * @mas: The maple state
5269 * @min: The lowest value of the range
5270 * @max: The highest value of the range
5271 * @size: The size needed
5273 int mas_empty_area_rev(struct ma_state *mas, unsigned long min,
5274 unsigned long max, unsigned long size)
5276 struct maple_enode *last = mas->node;
5278 if (mas_is_start(mas)) {
5280 mas->offset = mas_data_end(mas);
5281 } else if (mas->offset >= 2) {
5283 } else if (!mas_rewind_node(mas)) {
5288 if (mas_is_none(mas) || mas_is_ptr(mas)) {
5289 mas_sparse_area(mas, min, max, size, false);
5293 /* The start of the window can only be within these values. */
5297 while (!mas_rev_awalk(mas, size)) {
5298 if (last == mas->node) {
5299 if (!mas_rewind_node(mas))
5306 if (mas_is_err(mas))
5307 return xa_err(mas->node);
5309 if (unlikely(mas->offset == MAPLE_NODE_SLOTS))
5313 * mas_rev_awalk() has set mas->min and mas->max to the gap values. If
5314 * the maximum is outside the window we are searching, then use the last
5315 * location in the search.
5316 * mas->max and mas->min is the range of the gap.
5317 * mas->index and mas->last are currently set to the search range.
5320 /* Trim the upper limit to the max. */
5321 if (mas->max <= mas->last)
5322 mas->last = mas->max;
5324 mas->index = mas->last - size + 1;
5327 EXPORT_SYMBOL_GPL(mas_empty_area_rev);
5329 static inline int mas_alloc(struct ma_state *mas, void *entry,
5330 unsigned long size, unsigned long *index)
5335 if (mas_is_none(mas) || mas_is_ptr(mas)) {
5336 mas_root_expand(mas, entry);
5337 if (mas_is_err(mas))
5338 return xa_err(mas->node);
5341 return mte_pivot(mas->node, 0);
5342 return mte_pivot(mas->node, 1);
5345 /* Must be walking a tree. */
5346 mas_awalk(mas, size);
5347 if (mas_is_err(mas))
5348 return xa_err(mas->node);
5350 if (mas->offset == MAPLE_NODE_SLOTS)
5354 * At this point, mas->node points to the right node and we have an
5355 * offset that has a sufficient gap.
5359 min = mte_pivot(mas->node, mas->offset - 1) + 1;
5361 if (mas->index < min)
5364 mas_fill_gap(mas, entry, mas->offset, size, index);
5371 static inline int mas_rev_alloc(struct ma_state *mas, unsigned long min,
5372 unsigned long max, void *entry,
5373 unsigned long size, unsigned long *index)
5377 ret = mas_empty_area_rev(mas, min, max, size);
5381 if (mas_is_err(mas))
5382 return xa_err(mas->node);
5384 if (mas->offset == MAPLE_NODE_SLOTS)
5387 mas_fill_gap(mas, entry, mas->offset, size, index);
5395 * mas_dead_leaves() - Mark all leaves of a node as dead.
5396 * @mas: The maple state
5397 * @slots: Pointer to the slot array
5399 * Must hold the write lock.
5401 * Return: The number of leaves marked as dead.
5404 unsigned char mas_dead_leaves(struct ma_state *mas, void __rcu **slots)
5406 struct maple_node *node;
5407 enum maple_type type;
5411 for (offset = 0; offset < mt_slot_count(mas->node); offset++) {
5412 entry = mas_slot_locked(mas, slots, offset);
5413 type = mte_node_type(entry);
5414 node = mte_to_node(entry);
5415 /* Use both node and type to catch LE & BE metadata */
5419 mte_set_node_dead(entry);
5420 smp_wmb(); /* Needed for RCU */
5422 rcu_assign_pointer(slots[offset], node);
5428 static void __rcu **mas_dead_walk(struct ma_state *mas, unsigned char offset)
5430 struct maple_node *node, *next;
5431 void __rcu **slots = NULL;
5435 mas->node = ma_enode_ptr(next);
5437 slots = ma_slots(node, node->type);
5438 next = mas_slot_locked(mas, slots, offset);
5440 } while (!ma_is_leaf(next->type));
5445 static void mt_free_walk(struct rcu_head *head)
5448 struct maple_node *node, *start;
5449 struct maple_tree mt;
5450 unsigned char offset;
5451 enum maple_type type;
5452 MA_STATE(mas, &mt, 0, 0);
5454 node = container_of(head, struct maple_node, rcu);
5456 if (ma_is_leaf(node->type))
5459 mt_init_flags(&mt, node->ma_flags);
5462 mas.node = mt_mk_node(node, node->type);
5463 slots = mas_dead_walk(&mas, 0);
5464 node = mas_mn(&mas);
5466 mt_free_bulk(node->slot_len, slots);
5467 offset = node->parent_slot + 1;
5468 mas.node = node->piv_parent;
5469 if (mas_mn(&mas) == node)
5470 goto start_slots_free;
5472 type = mte_node_type(mas.node);
5473 slots = ma_slots(mte_to_node(mas.node), type);
5474 if ((offset < mt_slots[type]) && (slots[offset]))
5475 slots = mas_dead_walk(&mas, offset);
5477 node = mas_mn(&mas);
5478 } while ((node != start) || (node->slot_len < offset));
5480 slots = ma_slots(node, node->type);
5481 mt_free_bulk(node->slot_len, slots);
5486 mt_free_rcu(&node->rcu);
5489 static inline void __rcu **mas_destroy_descend(struct ma_state *mas,
5490 struct maple_enode *prev, unsigned char offset)
5492 struct maple_node *node;
5493 struct maple_enode *next = mas->node;
5494 void __rcu **slots = NULL;
5499 slots = ma_slots(node, mte_node_type(mas->node));
5500 next = mas_slot_locked(mas, slots, 0);
5501 if ((mte_dead_node(next)))
5502 next = mas_slot_locked(mas, slots, 1);
5504 mte_set_node_dead(mas->node);
5505 node->type = mte_node_type(mas->node);
5506 node->piv_parent = prev;
5507 node->parent_slot = offset;
5510 } while (!mte_is_leaf(next));
5515 static void mt_destroy_walk(struct maple_enode *enode, unsigned char ma_flags,
5519 struct maple_node *node = mte_to_node(enode);
5520 struct maple_enode *start;
5521 struct maple_tree mt;
5523 MA_STATE(mas, &mt, 0, 0);
5525 if (mte_is_leaf(enode))
5528 mt_init_flags(&mt, ma_flags);
5531 mas.node = start = enode;
5532 slots = mas_destroy_descend(&mas, start, 0);
5533 node = mas_mn(&mas);
5535 enum maple_type type;
5536 unsigned char offset;
5537 struct maple_enode *parent, *tmp;
5539 node->slot_len = mas_dead_leaves(&mas, slots);
5541 mt_free_bulk(node->slot_len, slots);
5542 offset = node->parent_slot + 1;
5543 mas.node = node->piv_parent;
5544 if (mas_mn(&mas) == node)
5545 goto start_slots_free;
5547 type = mte_node_type(mas.node);
5548 slots = ma_slots(mte_to_node(mas.node), type);
5549 if (offset >= mt_slots[type])
5552 tmp = mas_slot_locked(&mas, slots, offset);
5553 if (mte_node_type(tmp) && mte_to_node(tmp)) {
5556 slots = mas_destroy_descend(&mas, parent, offset);
5559 node = mas_mn(&mas);
5560 } while (start != mas.node);
5562 node = mas_mn(&mas);
5563 node->slot_len = mas_dead_leaves(&mas, slots);
5565 mt_free_bulk(node->slot_len, slots);
5572 mt_free_rcu(&node->rcu);
5576 * mte_destroy_walk() - Free a tree or sub-tree.
5577 * @enode - the encoded maple node (maple_enode) to start
5578 * @mn - the tree to free - needed for node types.
5580 * Must hold the write lock.
5582 static inline void mte_destroy_walk(struct maple_enode *enode,
5583 struct maple_tree *mt)
5585 struct maple_node *node = mte_to_node(enode);
5587 if (mt_in_rcu(mt)) {
5588 mt_destroy_walk(enode, mt->ma_flags, false);
5589 call_rcu(&node->rcu, mt_free_walk);
5591 mt_destroy_walk(enode, mt->ma_flags, true);
5595 static void mas_wr_store_setup(struct ma_wr_state *wr_mas)
5597 if (!mas_is_start(wr_mas->mas)) {
5598 if (mas_is_none(wr_mas->mas)) {
5599 mas_reset(wr_mas->mas);
5601 wr_mas->r_max = wr_mas->mas->max;
5602 wr_mas->type = mte_node_type(wr_mas->mas->node);
5603 if (mas_is_span_wr(wr_mas))
5604 mas_reset(wr_mas->mas);
5613 * mas_store() - Store an @entry.
5614 * @mas: The maple state.
5615 * @entry: The entry to store.
5617 * The @mas->index and @mas->last is used to set the range for the @entry.
5618 * Note: The @mas should have pre-allocated entries to ensure there is memory to
5619 * store the entry. Please see mas_expected_entries()/mas_destroy() for more details.
5621 * Return: the first entry between mas->index and mas->last or %NULL.
5623 void *mas_store(struct ma_state *mas, void *entry)
5625 MA_WR_STATE(wr_mas, mas, entry);
5627 trace_ma_write(__func__, mas, 0, entry);
5628 #ifdef CONFIG_DEBUG_MAPLE_TREE
5629 if (mas->index > mas->last)
5630 pr_err("Error %lu > %lu %p\n", mas->index, mas->last, entry);
5631 MT_BUG_ON(mas->tree, mas->index > mas->last);
5632 if (mas->index > mas->last) {
5633 mas_set_err(mas, -EINVAL);
5640 * Storing is the same operation as insert with the added caveat that it
5641 * can overwrite entries. Although this seems simple enough, one may
5642 * want to examine what happens if a single store operation was to
5643 * overwrite multiple entries within a self-balancing B-Tree.
5645 mas_wr_store_setup(&wr_mas);
5646 mas_wr_store_entry(&wr_mas);
5647 return wr_mas.content;
5649 EXPORT_SYMBOL_GPL(mas_store);
5652 * mas_store_gfp() - Store a value into the tree.
5653 * @mas: The maple state
5654 * @entry: The entry to store
5655 * @gfp: The GFP_FLAGS to use for allocations if necessary.
5657 * Return: 0 on success, -EINVAL on invalid request, -ENOMEM if memory could not
5660 int mas_store_gfp(struct ma_state *mas, void *entry, gfp_t gfp)
5662 MA_WR_STATE(wr_mas, mas, entry);
5664 mas_wr_store_setup(&wr_mas);
5665 trace_ma_write(__func__, mas, 0, entry);
5667 mas_wr_store_entry(&wr_mas);
5668 if (unlikely(mas_nomem(mas, gfp)))
5671 if (unlikely(mas_is_err(mas)))
5672 return xa_err(mas->node);
5676 EXPORT_SYMBOL_GPL(mas_store_gfp);
5679 * mas_store_prealloc() - Store a value into the tree using memory
5680 * preallocated in the maple state.
5681 * @mas: The maple state
5682 * @entry: The entry to store.
5684 void mas_store_prealloc(struct ma_state *mas, void *entry)
5686 MA_WR_STATE(wr_mas, mas, entry);
5688 mas_wr_store_setup(&wr_mas);
5689 trace_ma_write(__func__, mas, 0, entry);
5690 mas_wr_store_entry(&wr_mas);
5691 BUG_ON(mas_is_err(mas));
5694 EXPORT_SYMBOL_GPL(mas_store_prealloc);
5697 * mas_preallocate() - Preallocate enough nodes for a store operation
5698 * @mas: The maple state
5699 * @entry: The entry that will be stored
5700 * @gfp: The GFP_FLAGS to use for allocations.
5702 * Return: 0 on success, -ENOMEM if memory could not be allocated.
5704 int mas_preallocate(struct ma_state *mas, void *entry, gfp_t gfp)
5708 mas_node_count_gfp(mas, 1 + mas_mt_height(mas) * 3, gfp);
5709 mas->mas_flags |= MA_STATE_PREALLOC;
5710 if (likely(!mas_is_err(mas)))
5713 mas_set_alloc_req(mas, 0);
5714 ret = xa_err(mas->node);
5722 * mas_destroy() - destroy a maple state.
5723 * @mas: The maple state
5725 * Upon completion, check the left-most node and rebalance against the node to
5726 * the right if necessary. Frees any allocated nodes associated with this maple
5729 void mas_destroy(struct ma_state *mas)
5731 struct maple_alloc *node;
5732 unsigned long total;
5735 * When using mas_for_each() to insert an expected number of elements,
5736 * it is possible that the number inserted is less than the expected
5737 * number. To fix an invalid final node, a check is performed here to
5738 * rebalance the previous node with the final node.
5740 if (mas->mas_flags & MA_STATE_REBALANCE) {
5743 if (mas_is_start(mas))
5746 mtree_range_walk(mas);
5747 end = mas_data_end(mas) + 1;
5748 if (end < mt_min_slot_count(mas->node) - 1)
5749 mas_destroy_rebalance(mas, end);
5751 mas->mas_flags &= ~MA_STATE_REBALANCE;
5753 mas->mas_flags &= ~(MA_STATE_BULK|MA_STATE_PREALLOC);
5755 total = mas_allocated(mas);
5758 mas->alloc = node->slot[0];
5759 if (node->node_count > 1) {
5760 size_t count = node->node_count - 1;
5762 mt_free_bulk(count, (void __rcu **)&node->slot[1]);
5765 kmem_cache_free(maple_node_cache, node);
5771 EXPORT_SYMBOL_GPL(mas_destroy);
5774 * mas_expected_entries() - Set the expected number of entries that will be inserted.
5775 * @mas: The maple state
5776 * @nr_entries: The number of expected entries.
5778 * This will attempt to pre-allocate enough nodes to store the expected number
5779 * of entries. The allocations will occur using the bulk allocator interface
5780 * for speed. Please call mas_destroy() on the @mas after inserting the entries
5781 * to ensure any unused nodes are freed.
5783 * Return: 0 on success, -ENOMEM if memory could not be allocated.
5785 int mas_expected_entries(struct ma_state *mas, unsigned long nr_entries)
5787 int nonleaf_cap = MAPLE_ARANGE64_SLOTS - 2;
5788 struct maple_enode *enode = mas->node;
5793 * Sometimes it is necessary to duplicate a tree to a new tree, such as
5794 * forking a process and duplicating the VMAs from one tree to a new
5795 * tree. When such a situation arises, it is known that the new tree is
5796 * not going to be used until the entire tree is populated. For
5797 * performance reasons, it is best to use a bulk load with RCU disabled.
5798 * This allows for optimistic splitting that favours the left and reuse
5799 * of nodes during the operation.
5802 /* Optimize splitting for bulk insert in-order */
5803 mas->mas_flags |= MA_STATE_BULK;
5806 * Avoid overflow, assume a gap between each entry and a trailing null.
5807 * If this is wrong, it just means allocation can happen during
5808 * insertion of entries.
5810 nr_nodes = max(nr_entries, nr_entries * 2 + 1);
5811 if (!mt_is_alloc(mas->tree))
5812 nonleaf_cap = MAPLE_RANGE64_SLOTS - 2;
5814 /* Leaves; reduce slots to keep space for expansion */
5815 nr_nodes = DIV_ROUND_UP(nr_nodes, MAPLE_RANGE64_SLOTS - 2);
5816 /* Internal nodes */
5817 nr_nodes += DIV_ROUND_UP(nr_nodes, nonleaf_cap);
5818 /* Add working room for split (2 nodes) + new parents */
5819 mas_node_count(mas, nr_nodes + 3);
5821 /* Detect if allocations run out */
5822 mas->mas_flags |= MA_STATE_PREALLOC;
5824 if (!mas_is_err(mas))
5827 ret = xa_err(mas->node);
5833 EXPORT_SYMBOL_GPL(mas_expected_entries);
5836 * mas_next() - Get the next entry.
5837 * @mas: The maple state
5838 * @max: The maximum index to check.
5840 * Returns the next entry after @mas->index.
5841 * Must hold rcu_read_lock or the write lock.
5842 * Can return the zero entry.
5844 * Return: The next entry or %NULL
5846 void *mas_next(struct ma_state *mas, unsigned long max)
5848 if (mas_is_none(mas) || mas_is_paused(mas))
5849 mas->node = MAS_START;
5851 if (mas_is_start(mas))
5852 mas_walk(mas); /* Retries on dead nodes handled by mas_walk */
5854 if (mas_is_ptr(mas)) {
5857 mas->last = ULONG_MAX;
5862 if (mas->last == ULONG_MAX)
5865 /* Retries on dead nodes handled by mas_next_entry */
5866 return mas_next_entry(mas, max);
5868 EXPORT_SYMBOL_GPL(mas_next);
5871 * mt_next() - get the next value in the maple tree
5872 * @mt: The maple tree
5873 * @index: The start index
5874 * @max: The maximum index to check
5876 * Return: The entry at @index or higher, or %NULL if nothing is found.
5878 void *mt_next(struct maple_tree *mt, unsigned long index, unsigned long max)
5881 MA_STATE(mas, mt, index, index);
5884 entry = mas_next(&mas, max);
5888 EXPORT_SYMBOL_GPL(mt_next);
5891 * mas_prev() - Get the previous entry
5892 * @mas: The maple state
5893 * @min: The minimum value to check.
5895 * Must hold rcu_read_lock or the write lock.
5896 * Will reset mas to MAS_START if the node is MAS_NONE. Will stop on not
5899 * Return: the previous value or %NULL.
5901 void *mas_prev(struct ma_state *mas, unsigned long min)
5904 /* Nothing comes before 0 */
5909 if (unlikely(mas_is_ptr(mas)))
5912 if (mas_is_none(mas) || mas_is_paused(mas))
5913 mas->node = MAS_START;
5915 if (mas_is_start(mas)) {
5921 if (mas_is_ptr(mas)) {
5927 mas->index = mas->last = 0;
5928 return mas_root_locked(mas);
5930 return mas_prev_entry(mas, min);
5932 EXPORT_SYMBOL_GPL(mas_prev);
5935 * mt_prev() - get the previous value in the maple tree
5936 * @mt: The maple tree
5937 * @index: The start index
5938 * @min: The minimum index to check
5940 * Return: The entry at @index or lower, or %NULL if nothing is found.
5942 void *mt_prev(struct maple_tree *mt, unsigned long index, unsigned long min)
5945 MA_STATE(mas, mt, index, index);
5948 entry = mas_prev(&mas, min);
5952 EXPORT_SYMBOL_GPL(mt_prev);
5955 * mas_pause() - Pause a mas_find/mas_for_each to drop the lock.
5956 * @mas: The maple state to pause
5958 * Some users need to pause a walk and drop the lock they're holding in
5959 * order to yield to a higher priority thread or carry out an operation
5960 * on an entry. Those users should call this function before they drop
5961 * the lock. It resets the @mas to be suitable for the next iteration
5962 * of the loop after the user has reacquired the lock. If most entries
5963 * found during a walk require you to call mas_pause(), the mt_for_each()
5964 * iterator may be more appropriate.
5967 void mas_pause(struct ma_state *mas)
5969 mas->node = MAS_PAUSE;
5971 EXPORT_SYMBOL_GPL(mas_pause);
5974 * mas_find() - On the first call, find the entry at or after mas->index up to
5975 * %max. Otherwise, find the entry after mas->index.
5976 * @mas: The maple state
5977 * @max: The maximum value to check.
5979 * Must hold rcu_read_lock or the write lock.
5980 * If an entry exists, last and index are updated accordingly.
5981 * May set @mas->node to MAS_NONE.
5983 * Return: The entry or %NULL.
5985 void *mas_find(struct ma_state *mas, unsigned long max)
5987 if (unlikely(mas_is_paused(mas))) {
5988 if (unlikely(mas->last == ULONG_MAX)) {
5989 mas->node = MAS_NONE;
5992 mas->node = MAS_START;
5993 mas->index = ++mas->last;
5996 if (unlikely(mas_is_start(mas))) {
5997 /* First run or continue */
6000 if (mas->index > max)
6003 entry = mas_walk(mas);
6008 if (unlikely(!mas_searchable(mas)))
6011 /* Retries on dead nodes handled by mas_next_entry */
6012 return mas_next_entry(mas, max);
6014 EXPORT_SYMBOL_GPL(mas_find);
6017 * mas_find_rev: On the first call, find the first non-null entry at or below
6018 * mas->index down to %min. Otherwise find the first non-null entry below
6019 * mas->index down to %min.
6020 * @mas: The maple state
6021 * @min: The minimum value to check.
6023 * Must hold rcu_read_lock or the write lock.
6024 * If an entry exists, last and index are updated accordingly.
6025 * May set @mas->node to MAS_NONE.
6027 * Return: The entry or %NULL.
6029 void *mas_find_rev(struct ma_state *mas, unsigned long min)
6031 if (unlikely(mas_is_paused(mas))) {
6032 if (unlikely(mas->last == ULONG_MAX)) {
6033 mas->node = MAS_NONE;
6036 mas->node = MAS_START;
6037 mas->last = --mas->index;
6040 if (unlikely(mas_is_start(mas))) {
6041 /* First run or continue */
6044 if (mas->index < min)
6047 entry = mas_walk(mas);
6052 if (unlikely(!mas_searchable(mas)))
6055 if (mas->index < min)
6058 /* Retries on dead nodes handled by mas_next_entry */
6059 return mas_prev_entry(mas, min);
6061 EXPORT_SYMBOL_GPL(mas_find_rev);
6064 * mas_erase() - Find the range in which index resides and erase the entire
6066 * @mas: The maple state
6068 * Must hold the write lock.
6069 * Searches for @mas->index, sets @mas->index and @mas->last to the range and
6070 * erases that range.
6072 * Return: the entry that was erased or %NULL, @mas->index and @mas->last are updated.
6074 void *mas_erase(struct ma_state *mas)
6077 MA_WR_STATE(wr_mas, mas, NULL);
6079 if (mas_is_none(mas) || mas_is_paused(mas))
6080 mas->node = MAS_START;
6082 /* Retry unnecessary when holding the write lock. */
6083 entry = mas_state_walk(mas);
6088 /* Must reset to ensure spanning writes of last slot are detected */
6090 mas_wr_store_setup(&wr_mas);
6091 mas_wr_store_entry(&wr_mas);
6092 if (mas_nomem(mas, GFP_KERNEL))
6097 EXPORT_SYMBOL_GPL(mas_erase);
6100 * mas_nomem() - Check if there was an error allocating and do the allocation
6101 * if necessary If there are allocations, then free them.
6102 * @mas: The maple state
6103 * @gfp: The GFP_FLAGS to use for allocations
6104 * Return: true on allocation, false otherwise.
6106 bool mas_nomem(struct ma_state *mas, gfp_t gfp)
6107 __must_hold(mas->tree->lock)
6109 if (likely(mas->node != MA_ERROR(-ENOMEM))) {
6114 if (gfpflags_allow_blocking(gfp) && !mt_external_lock(mas->tree)) {
6115 mtree_unlock(mas->tree);
6116 mas_alloc_nodes(mas, gfp);
6117 mtree_lock(mas->tree);
6119 mas_alloc_nodes(mas, gfp);
6122 if (!mas_allocated(mas))
6125 mas->node = MAS_START;
6129 void __init maple_tree_init(void)
6131 maple_node_cache = kmem_cache_create("maple_node",
6132 sizeof(struct maple_node), sizeof(struct maple_node),
6137 * mtree_load() - Load a value stored in a maple tree
6138 * @mt: The maple tree
6139 * @index: The index to load
6141 * Return: the entry or %NULL
6143 void *mtree_load(struct maple_tree *mt, unsigned long index)
6145 MA_STATE(mas, mt, index, index);
6148 trace_ma_read(__func__, &mas);
6151 entry = mas_start(&mas);
6152 if (unlikely(mas_is_none(&mas)))
6155 if (unlikely(mas_is_ptr(&mas))) {
6162 entry = mtree_lookup_walk(&mas);
6163 if (!entry && unlikely(mas_is_start(&mas)))
6167 if (xa_is_zero(entry))
6172 EXPORT_SYMBOL(mtree_load);
6175 * mtree_store_range() - Store an entry at a given range.
6176 * @mt: The maple tree
6177 * @index: The start of the range
6178 * @last: The end of the range
6179 * @entry: The entry to store
6180 * @gfp: The GFP_FLAGS to use for allocations
6182 * Return: 0 on success, -EINVAL on invalid request, -ENOMEM if memory could not
6185 int mtree_store_range(struct maple_tree *mt, unsigned long index,
6186 unsigned long last, void *entry, gfp_t gfp)
6188 MA_STATE(mas, mt, index, last);
6189 MA_WR_STATE(wr_mas, &mas, entry);
6191 trace_ma_write(__func__, &mas, 0, entry);
6192 if (WARN_ON_ONCE(xa_is_advanced(entry)))
6200 mas_wr_store_entry(&wr_mas);
6201 if (mas_nomem(&mas, gfp))
6205 if (mas_is_err(&mas))
6206 return xa_err(mas.node);
6210 EXPORT_SYMBOL(mtree_store_range);
6213 * mtree_store() - Store an entry at a given index.
6214 * @mt: The maple tree
6215 * @index: The index to store the value
6216 * @entry: The entry to store
6217 * @gfp: The GFP_FLAGS to use for allocations
6219 * Return: 0 on success, -EINVAL on invalid request, -ENOMEM if memory could not
6222 int mtree_store(struct maple_tree *mt, unsigned long index, void *entry,
6225 return mtree_store_range(mt, index, index, entry, gfp);
6227 EXPORT_SYMBOL(mtree_store);
6230 * mtree_insert_range() - Insert an entry at a give range if there is no value.
6231 * @mt: The maple tree
6232 * @first: The start of the range
6233 * @last: The end of the range
6234 * @entry: The entry to store
6235 * @gfp: The GFP_FLAGS to use for allocations.
6237 * Return: 0 on success, -EEXISTS if the range is occupied, -EINVAL on invalid
6238 * request, -ENOMEM if memory could not be allocated.
6240 int mtree_insert_range(struct maple_tree *mt, unsigned long first,
6241 unsigned long last, void *entry, gfp_t gfp)
6243 MA_STATE(ms, mt, first, last);
6245 if (WARN_ON_ONCE(xa_is_advanced(entry)))
6253 mas_insert(&ms, entry);
6254 if (mas_nomem(&ms, gfp))
6258 if (mas_is_err(&ms))
6259 return xa_err(ms.node);
6263 EXPORT_SYMBOL(mtree_insert_range);
6266 * mtree_insert() - Insert an entry at a give index if there is no value.
6267 * @mt: The maple tree
6268 * @index : The index to store the value
6269 * @entry: The entry to store
6270 * @gfp: The FGP_FLAGS to use for allocations.
6272 * Return: 0 on success, -EEXISTS if the range is occupied, -EINVAL on invalid
6273 * request, -ENOMEM if memory could not be allocated.
6275 int mtree_insert(struct maple_tree *mt, unsigned long index, void *entry,
6278 return mtree_insert_range(mt, index, index, entry, gfp);
6280 EXPORT_SYMBOL(mtree_insert);
6282 int mtree_alloc_range(struct maple_tree *mt, unsigned long *startp,
6283 void *entry, unsigned long size, unsigned long min,
6284 unsigned long max, gfp_t gfp)
6288 MA_STATE(mas, mt, min, max - size);
6289 if (!mt_is_alloc(mt))
6292 if (WARN_ON_ONCE(mt_is_reserved(entry)))
6308 mas.last = max - size;
6309 ret = mas_alloc(&mas, entry, size, startp);
6310 if (mas_nomem(&mas, gfp))
6316 EXPORT_SYMBOL(mtree_alloc_range);
6318 int mtree_alloc_rrange(struct maple_tree *mt, unsigned long *startp,
6319 void *entry, unsigned long size, unsigned long min,
6320 unsigned long max, gfp_t gfp)
6324 MA_STATE(mas, mt, min, max - size);
6325 if (!mt_is_alloc(mt))
6328 if (WARN_ON_ONCE(mt_is_reserved(entry)))
6342 ret = mas_rev_alloc(&mas, min, max, entry, size, startp);
6343 if (mas_nomem(&mas, gfp))
6349 EXPORT_SYMBOL(mtree_alloc_rrange);
6352 * mtree_erase() - Find an index and erase the entire range.
6353 * @mt: The maple tree
6354 * @index: The index to erase
6356 * Erasing is the same as a walk to an entry then a store of a NULL to that
6357 * ENTIRE range. In fact, it is implemented as such using the advanced API.
6359 * Return: The entry stored at the @index or %NULL
6361 void *mtree_erase(struct maple_tree *mt, unsigned long index)
6365 MA_STATE(mas, mt, index, index);
6366 trace_ma_op(__func__, &mas);
6369 entry = mas_erase(&mas);
6374 EXPORT_SYMBOL(mtree_erase);
6377 * __mt_destroy() - Walk and free all nodes of a locked maple tree.
6378 * @mt: The maple tree
6380 * Note: Does not handle locking.
6382 void __mt_destroy(struct maple_tree *mt)
6384 void *root = mt_root_locked(mt);
6386 rcu_assign_pointer(mt->ma_root, NULL);
6387 if (xa_is_node(root))
6388 mte_destroy_walk(root, mt);
6392 EXPORT_SYMBOL_GPL(__mt_destroy);
6395 * mtree_destroy() - Destroy a maple tree
6396 * @mt: The maple tree
6398 * Frees all resources used by the tree. Handles locking.
6400 void mtree_destroy(struct maple_tree *mt)
6406 EXPORT_SYMBOL(mtree_destroy);
6409 * mt_find() - Search from the start up until an entry is found.
6410 * @mt: The maple tree
6411 * @index: Pointer which contains the start location of the search
6412 * @max: The maximum value to check
6414 * Handles locking. @index will be incremented to one beyond the range.
6416 * Return: The entry at or after the @index or %NULL
6418 void *mt_find(struct maple_tree *mt, unsigned long *index, unsigned long max)
6420 MA_STATE(mas, mt, *index, *index);
6422 #ifdef CONFIG_DEBUG_MAPLE_TREE
6423 unsigned long copy = *index;
6426 trace_ma_read(__func__, &mas);
6433 entry = mas_state_walk(&mas);
6434 if (mas_is_start(&mas))
6437 if (unlikely(xa_is_zero(entry)))
6443 while (mas_searchable(&mas) && (mas.index < max)) {
6444 entry = mas_next_entry(&mas, max);
6445 if (likely(entry && !xa_is_zero(entry)))
6449 if (unlikely(xa_is_zero(entry)))
6453 if (likely(entry)) {
6454 *index = mas.last + 1;
6455 #ifdef CONFIG_DEBUG_MAPLE_TREE
6456 if ((*index) && (*index) <= copy)
6457 pr_err("index not increased! %lx <= %lx\n",
6459 MT_BUG_ON(mt, (*index) && ((*index) <= copy));
6465 EXPORT_SYMBOL(mt_find);
6468 * mt_find_after() - Search from the start up until an entry is found.
6469 * @mt: The maple tree
6470 * @index: Pointer which contains the start location of the search
6471 * @max: The maximum value to check
6473 * Handles locking, detects wrapping on index == 0
6475 * Return: The entry at or after the @index or %NULL
6477 void *mt_find_after(struct maple_tree *mt, unsigned long *index,
6483 return mt_find(mt, index, max);
6485 EXPORT_SYMBOL(mt_find_after);
6487 #ifdef CONFIG_DEBUG_MAPLE_TREE
6488 atomic_t maple_tree_tests_run;
6489 EXPORT_SYMBOL_GPL(maple_tree_tests_run);
6490 atomic_t maple_tree_tests_passed;
6491 EXPORT_SYMBOL_GPL(maple_tree_tests_passed);
6494 extern void kmem_cache_set_non_kernel(struct kmem_cache *, unsigned int);
6495 void mt_set_non_kernel(unsigned int val)
6497 kmem_cache_set_non_kernel(maple_node_cache, val);
6500 extern unsigned long kmem_cache_get_alloc(struct kmem_cache *);
6501 unsigned long mt_get_alloc_size(void)
6503 return kmem_cache_get_alloc(maple_node_cache);
6506 extern void kmem_cache_zero_nr_tallocated(struct kmem_cache *);
6507 void mt_zero_nr_tallocated(void)
6509 kmem_cache_zero_nr_tallocated(maple_node_cache);
6512 extern unsigned int kmem_cache_nr_tallocated(struct kmem_cache *);
6513 unsigned int mt_nr_tallocated(void)
6515 return kmem_cache_nr_tallocated(maple_node_cache);
6518 extern unsigned int kmem_cache_nr_allocated(struct kmem_cache *);
6519 unsigned int mt_nr_allocated(void)
6521 return kmem_cache_nr_allocated(maple_node_cache);
6525 * mas_dead_node() - Check if the maple state is pointing to a dead node.
6526 * @mas: The maple state
6527 * @index: The index to restore in @mas.
6529 * Used in test code.
6530 * Return: 1 if @mas has been reset to MAS_START, 0 otherwise.
6532 static inline int mas_dead_node(struct ma_state *mas, unsigned long index)
6534 if (unlikely(!mas_searchable(mas) || mas_is_start(mas)))
6537 if (likely(!mte_dead_node(mas->node)))
6540 mas_rewalk(mas, index);
6544 void mt_cache_shrink(void)
6549 * mt_cache_shrink() - For testing, don't use this.
6551 * Certain testcases can trigger an OOM when combined with other memory
6552 * debugging configuration options. This function is used to reduce the
6553 * possibility of an out of memory even due to kmem_cache objects remaining
6554 * around for longer than usual.
6556 void mt_cache_shrink(void)
6558 kmem_cache_shrink(maple_node_cache);
6561 EXPORT_SYMBOL_GPL(mt_cache_shrink);
6563 #endif /* not defined __KERNEL__ */
6565 * mas_get_slot() - Get the entry in the maple state node stored at @offset.
6566 * @mas: The maple state
6567 * @offset: The offset into the slot array to fetch.
6569 * Return: The entry stored at @offset.
6571 static inline struct maple_enode *mas_get_slot(struct ma_state *mas,
6572 unsigned char offset)
6574 return mas_slot(mas, ma_slots(mas_mn(mas), mte_node_type(mas->node)),
6580 * mas_first_entry() - Go the first leaf and find the first entry.
6581 * @mas: the maple state.
6582 * @limit: the maximum index to check.
6583 * @*r_start: Pointer to set to the range start.
6585 * Sets mas->offset to the offset of the entry, r_start to the range minimum.
6587 * Return: The first entry or MAS_NONE.
6589 static inline void *mas_first_entry(struct ma_state *mas, struct maple_node *mn,
6590 unsigned long limit, enum maple_type mt)
6594 unsigned long *pivots;
6598 mas->index = mas->min;
6599 if (mas->index > limit)
6604 while (likely(!ma_is_leaf(mt))) {
6605 MT_BUG_ON(mas->tree, mte_dead_node(mas->node));
6606 slots = ma_slots(mn, mt);
6607 pivots = ma_pivots(mn, mt);
6609 entry = mas_slot(mas, slots, 0);
6610 if (unlikely(ma_dead_node(mn)))
6614 mt = mte_node_type(mas->node);
6616 MT_BUG_ON(mas->tree, mte_dead_node(mas->node));
6619 slots = ma_slots(mn, mt);
6620 entry = mas_slot(mas, slots, 0);
6621 if (unlikely(ma_dead_node(mn)))
6624 /* Slot 0 or 1 must be set */
6625 if (mas->index > limit)
6631 pivots = ma_pivots(mn, mt);
6632 mas->index = pivots[0] + 1;
6634 entry = mas_slot(mas, slots, 1);
6635 if (unlikely(ma_dead_node(mn)))
6638 if (mas->index > limit)
6645 if (likely(!ma_dead_node(mn)))
6646 mas->node = MAS_NONE;
6650 /* Depth first search, post-order */
6651 static void mas_dfs_postorder(struct ma_state *mas, unsigned long max)
6654 struct maple_enode *p = MAS_NONE, *mn = mas->node;
6655 unsigned long p_min, p_max;
6657 mas_next_node(mas, mas_mn(mas), max);
6658 if (!mas_is_none(mas))
6661 if (mte_is_root(mn))
6666 while (mas->node != MAS_NONE) {
6670 mas_prev_node(mas, 0);
6681 /* Tree validations */
6682 static void mt_dump_node(const struct maple_tree *mt, void *entry,
6683 unsigned long min, unsigned long max, unsigned int depth);
6684 static void mt_dump_range(unsigned long min, unsigned long max,
6687 static const char spaces[] = " ";
6690 pr_info("%.*s%lu: ", depth * 2, spaces, min);
6692 pr_info("%.*s%lu-%lu: ", depth * 2, spaces, min, max);
6695 static void mt_dump_entry(void *entry, unsigned long min, unsigned long max,
6698 mt_dump_range(min, max, depth);
6700 if (xa_is_value(entry))
6701 pr_cont("value %ld (0x%lx) [%p]\n", xa_to_value(entry),
6702 xa_to_value(entry), entry);
6703 else if (xa_is_zero(entry))
6704 pr_cont("zero (%ld)\n", xa_to_internal(entry));
6705 else if (mt_is_reserved(entry))
6706 pr_cont("UNKNOWN ENTRY (%p)\n", entry);
6708 pr_cont("%p\n", entry);
6711 static void mt_dump_range64(const struct maple_tree *mt, void *entry,
6712 unsigned long min, unsigned long max, unsigned int depth)
6714 struct maple_range_64 *node = &mte_to_node(entry)->mr64;
6715 bool leaf = mte_is_leaf(entry);
6716 unsigned long first = min;
6719 pr_cont(" contents: ");
6720 for (i = 0; i < MAPLE_RANGE64_SLOTS - 1; i++)
6721 pr_cont("%p %lu ", node->slot[i], node->pivot[i]);
6722 pr_cont("%p\n", node->slot[i]);
6723 for (i = 0; i < MAPLE_RANGE64_SLOTS; i++) {
6724 unsigned long last = max;
6726 if (i < (MAPLE_RANGE64_SLOTS - 1))
6727 last = node->pivot[i];
6728 else if (!node->slot[i] && max != mt_max[mte_node_type(entry)])
6730 if (last == 0 && i > 0)
6733 mt_dump_entry(mt_slot(mt, node->slot, i),
6734 first, last, depth + 1);
6735 else if (node->slot[i])
6736 mt_dump_node(mt, mt_slot(mt, node->slot, i),
6737 first, last, depth + 1);
6742 pr_err("node %p last (%lu) > max (%lu) at pivot %d!\n",
6743 node, last, max, i);
6750 static void mt_dump_arange64(const struct maple_tree *mt, void *entry,
6751 unsigned long min, unsigned long max, unsigned int depth)
6753 struct maple_arange_64 *node = &mte_to_node(entry)->ma64;
6754 bool leaf = mte_is_leaf(entry);
6755 unsigned long first = min;
6758 pr_cont(" contents: ");
6759 for (i = 0; i < MAPLE_ARANGE64_SLOTS; i++)
6760 pr_cont("%lu ", node->gap[i]);
6761 pr_cont("| %02X %02X| ", node->meta.end, node->meta.gap);
6762 for (i = 0; i < MAPLE_ARANGE64_SLOTS - 1; i++)
6763 pr_cont("%p %lu ", node->slot[i], node->pivot[i]);
6764 pr_cont("%p\n", node->slot[i]);
6765 for (i = 0; i < MAPLE_ARANGE64_SLOTS; i++) {
6766 unsigned long last = max;
6768 if (i < (MAPLE_ARANGE64_SLOTS - 1))
6769 last = node->pivot[i];
6770 else if (!node->slot[i])
6772 if (last == 0 && i > 0)
6775 mt_dump_entry(mt_slot(mt, node->slot, i),
6776 first, last, depth + 1);
6777 else if (node->slot[i])
6778 mt_dump_node(mt, mt_slot(mt, node->slot, i),
6779 first, last, depth + 1);
6784 pr_err("node %p last (%lu) > max (%lu) at pivot %d!\n",
6785 node, last, max, i);
6792 static void mt_dump_node(const struct maple_tree *mt, void *entry,
6793 unsigned long min, unsigned long max, unsigned int depth)
6795 struct maple_node *node = mte_to_node(entry);
6796 unsigned int type = mte_node_type(entry);
6799 mt_dump_range(min, max, depth);
6801 pr_cont("node %p depth %d type %d parent %p", node, depth, type,
6802 node ? node->parent : NULL);
6806 for (i = 0; i < MAPLE_NODE_SLOTS; i++) {
6808 pr_cont("OUT OF RANGE: ");
6809 mt_dump_entry(mt_slot(mt, node->slot, i),
6810 min + i, min + i, depth);
6814 case maple_range_64:
6815 mt_dump_range64(mt, entry, min, max, depth);
6817 case maple_arange_64:
6818 mt_dump_arange64(mt, entry, min, max, depth);
6822 pr_cont(" UNKNOWN TYPE\n");
6826 void mt_dump(const struct maple_tree *mt)
6828 void *entry = rcu_dereference_check(mt->ma_root, mt_locked(mt));
6830 pr_info("maple_tree(%p) flags %X, height %u root %p\n",
6831 mt, mt->ma_flags, mt_height(mt), entry);
6832 if (!xa_is_node(entry))
6833 mt_dump_entry(entry, 0, 0, 0);
6835 mt_dump_node(mt, entry, 0, mt_max[mte_node_type(entry)], 0);
6837 EXPORT_SYMBOL_GPL(mt_dump);
6840 * Calculate the maximum gap in a node and check if that's what is reported in
6841 * the parent (unless root).
6843 static void mas_validate_gaps(struct ma_state *mas)
6845 struct maple_enode *mte = mas->node;
6846 struct maple_node *p_mn;
6847 unsigned long gap = 0, max_gap = 0;
6848 unsigned long p_end, p_start = mas->min;
6849 unsigned char p_slot;
6850 unsigned long *gaps = NULL;
6851 unsigned long *pivots = ma_pivots(mte_to_node(mte), mte_node_type(mte));
6854 if (ma_is_dense(mte_node_type(mte))) {
6855 for (i = 0; i < mt_slot_count(mte); i++) {
6856 if (mas_get_slot(mas, i)) {
6867 gaps = ma_gaps(mte_to_node(mte), mte_node_type(mte));
6868 for (i = 0; i < mt_slot_count(mte); i++) {
6869 p_end = mas_logical_pivot(mas, pivots, i, mte_node_type(mte));
6872 if (mas_get_slot(mas, i)) {
6877 gap += p_end - p_start + 1;
6879 void *entry = mas_get_slot(mas, i);
6883 if (gap != p_end - p_start + 1) {
6884 pr_err("%p[%u] -> %p %lu != %lu - %lu + 1\n",
6886 mas_get_slot(mas, i), gap,
6890 MT_BUG_ON(mas->tree,
6891 gap != p_end - p_start + 1);
6894 if (gap > p_end - p_start + 1) {
6895 pr_err("%p[%u] %lu >= %lu - %lu + 1 (%lu)\n",
6896 mas_mn(mas), i, gap, p_end, p_start,
6897 p_end - p_start + 1);
6898 MT_BUG_ON(mas->tree,
6899 gap > p_end - p_start + 1);
6907 p_start = p_end + 1;
6908 if (p_end >= mas->max)
6913 if (mte_is_root(mte))
6916 p_slot = mte_parent_slot(mas->node);
6917 p_mn = mte_parent(mte);
6918 MT_BUG_ON(mas->tree, max_gap > mas->max);
6919 if (ma_gaps(p_mn, mas_parent_enum(mas, mte))[p_slot] != max_gap) {
6920 pr_err("gap %p[%u] != %lu\n", p_mn, p_slot, max_gap);
6924 MT_BUG_ON(mas->tree,
6925 ma_gaps(p_mn, mas_parent_enum(mas, mte))[p_slot] != max_gap);
6928 static void mas_validate_parent_slot(struct ma_state *mas)
6930 struct maple_node *parent;
6931 struct maple_enode *node;
6932 enum maple_type p_type = mas_parent_enum(mas, mas->node);
6933 unsigned char p_slot = mte_parent_slot(mas->node);
6937 if (mte_is_root(mas->node))
6940 parent = mte_parent(mas->node);
6941 slots = ma_slots(parent, p_type);
6942 MT_BUG_ON(mas->tree, mas_mn(mas) == parent);
6944 /* Check prev/next parent slot for duplicate node entry */
6946 for (i = 0; i < mt_slots[p_type]; i++) {
6947 node = mas_slot(mas, slots, i);
6949 if (node != mas->node)
6950 pr_err("parent %p[%u] does not have %p\n",
6951 parent, i, mas_mn(mas));
6952 MT_BUG_ON(mas->tree, node != mas->node);
6953 } else if (node == mas->node) {
6954 pr_err("Invalid child %p at parent %p[%u] p_slot %u\n",
6955 mas_mn(mas), parent, i, p_slot);
6956 MT_BUG_ON(mas->tree, node == mas->node);
6961 static void mas_validate_child_slot(struct ma_state *mas)
6963 enum maple_type type = mte_node_type(mas->node);
6964 void __rcu **slots = ma_slots(mte_to_node(mas->node), type);
6965 unsigned long *pivots = ma_pivots(mte_to_node(mas->node), type);
6966 struct maple_enode *child;
6969 if (mte_is_leaf(mas->node))
6972 for (i = 0; i < mt_slots[type]; i++) {
6973 child = mas_slot(mas, slots, i);
6974 if (!pivots[i] || pivots[i] == mas->max)
6980 if (mte_parent_slot(child) != i) {
6981 pr_err("Slot error at %p[%u]: child %p has pslot %u\n",
6982 mas_mn(mas), i, mte_to_node(child),
6983 mte_parent_slot(child));
6984 MT_BUG_ON(mas->tree, 1);
6987 if (mte_parent(child) != mte_to_node(mas->node)) {
6988 pr_err("child %p has parent %p not %p\n",
6989 mte_to_node(child), mte_parent(child),
6990 mte_to_node(mas->node));
6991 MT_BUG_ON(mas->tree, 1);
6997 * Validate all pivots are within mas->min and mas->max.
6999 static void mas_validate_limits(struct ma_state *mas)
7002 unsigned long prev_piv = 0;
7003 enum maple_type type = mte_node_type(mas->node);
7004 void __rcu **slots = ma_slots(mte_to_node(mas->node), type);
7005 unsigned long *pivots = ma_pivots(mas_mn(mas), type);
7007 /* all limits are fine here. */
7008 if (mte_is_root(mas->node))
7011 for (i = 0; i < mt_slots[type]; i++) {
7014 piv = mas_safe_pivot(mas, pivots, i, type);
7016 if (!piv && (i != 0))
7019 if (!mte_is_leaf(mas->node)) {
7020 void *entry = mas_slot(mas, slots, i);
7023 pr_err("%p[%u] cannot be null\n",
7026 MT_BUG_ON(mas->tree, !entry);
7029 if (prev_piv > piv) {
7030 pr_err("%p[%u] piv %lu < prev_piv %lu\n",
7031 mas_mn(mas), i, piv, prev_piv);
7032 MT_BUG_ON(mas->tree, piv < prev_piv);
7035 if (piv < mas->min) {
7036 pr_err("%p[%u] %lu < %lu\n", mas_mn(mas), i,
7038 MT_BUG_ON(mas->tree, piv < mas->min);
7040 if (piv > mas->max) {
7041 pr_err("%p[%u] %lu > %lu\n", mas_mn(mas), i,
7043 MT_BUG_ON(mas->tree, piv > mas->max);
7046 if (piv == mas->max)
7049 for (i += 1; i < mt_slots[type]; i++) {
7050 void *entry = mas_slot(mas, slots, i);
7052 if (entry && (i != mt_slots[type] - 1)) {
7053 pr_err("%p[%u] should not have entry %p\n", mas_mn(mas),
7055 MT_BUG_ON(mas->tree, entry != NULL);
7058 if (i < mt_pivots[type]) {
7059 unsigned long piv = pivots[i];
7064 pr_err("%p[%u] should not have piv %lu\n",
7065 mas_mn(mas), i, piv);
7066 MT_BUG_ON(mas->tree, i < mt_pivots[type] - 1);
7071 static void mt_validate_nulls(struct maple_tree *mt)
7073 void *entry, *last = (void *)1;
7074 unsigned char offset = 0;
7076 MA_STATE(mas, mt, 0, 0);
7079 if (mas_is_none(&mas) || (mas.node == MAS_ROOT))
7082 while (!mte_is_leaf(mas.node))
7085 slots = ma_slots(mte_to_node(mas.node), mte_node_type(mas.node));
7087 entry = mas_slot(&mas, slots, offset);
7088 if (!last && !entry) {
7089 pr_err("Sequential nulls end at %p[%u]\n",
7090 mas_mn(&mas), offset);
7092 MT_BUG_ON(mt, !last && !entry);
7094 if (offset == mas_data_end(&mas)) {
7095 mas_next_node(&mas, mas_mn(&mas), ULONG_MAX);
7096 if (mas_is_none(&mas))
7099 slots = ma_slots(mte_to_node(mas.node),
7100 mte_node_type(mas.node));
7105 } while (!mas_is_none(&mas));
7109 * validate a maple tree by checking:
7110 * 1. The limits (pivots are within mas->min to mas->max)
7111 * 2. The gap is correctly set in the parents
7113 void mt_validate(struct maple_tree *mt)
7117 MA_STATE(mas, mt, 0, 0);
7120 if (!mas_searchable(&mas))
7123 mas_first_entry(&mas, mas_mn(&mas), ULONG_MAX, mte_node_type(mas.node));
7124 while (!mas_is_none(&mas)) {
7125 MT_BUG_ON(mas.tree, mte_dead_node(mas.node));
7126 if (!mte_is_root(mas.node)) {
7127 end = mas_data_end(&mas);
7128 if ((end < mt_min_slot_count(mas.node)) &&
7129 (mas.max != ULONG_MAX)) {
7130 pr_err("Invalid size %u of %p\n", end,
7132 MT_BUG_ON(mas.tree, 1);
7136 mas_validate_parent_slot(&mas);
7137 mas_validate_child_slot(&mas);
7138 mas_validate_limits(&mas);
7139 if (mt_is_alloc(mt))
7140 mas_validate_gaps(&mas);
7141 mas_dfs_postorder(&mas, ULONG_MAX);
7143 mt_validate_nulls(mt);
7148 EXPORT_SYMBOL_GPL(mt_validate);
7150 #endif /* CONFIG_DEBUG_MAPLE_TREE */