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 mas_tree_parent(x) ((unsigned long)(x->tree) | MA_ROOT_PARENT)
79 #define ma_mnode_ptr(x) ((struct maple_node *)(x))
80 #define ma_enode_ptr(x) ((struct maple_enode *)(x))
81 static struct kmem_cache
*maple_node_cache
;
83 #ifdef CONFIG_DEBUG_MAPLE_TREE
84 static const unsigned long mt_max
[] = {
85 [maple_dense
] = MAPLE_NODE_SLOTS
,
86 [maple_leaf_64
] = ULONG_MAX
,
87 [maple_range_64
] = ULONG_MAX
,
88 [maple_arange_64
] = ULONG_MAX
,
90 #define mt_node_max(x) mt_max[mte_node_type(x)]
93 static const unsigned char mt_slots
[] = {
94 [maple_dense
] = MAPLE_NODE_SLOTS
,
95 [maple_leaf_64
] = MAPLE_RANGE64_SLOTS
,
96 [maple_range_64
] = MAPLE_RANGE64_SLOTS
,
97 [maple_arange_64
] = MAPLE_ARANGE64_SLOTS
,
99 #define mt_slot_count(x) mt_slots[mte_node_type(x)]
101 static const unsigned char mt_pivots
[] = {
103 [maple_leaf_64
] = MAPLE_RANGE64_SLOTS
- 1,
104 [maple_range_64
] = MAPLE_RANGE64_SLOTS
- 1,
105 [maple_arange_64
] = MAPLE_ARANGE64_SLOTS
- 1,
107 #define mt_pivot_count(x) mt_pivots[mte_node_type(x)]
109 static const unsigned char mt_min_slots
[] = {
110 [maple_dense
] = MAPLE_NODE_SLOTS
/ 2,
111 [maple_leaf_64
] = (MAPLE_RANGE64_SLOTS
/ 2) - 2,
112 [maple_range_64
] = (MAPLE_RANGE64_SLOTS
/ 2) - 2,
113 [maple_arange_64
] = (MAPLE_ARANGE64_SLOTS
/ 2) - 1,
115 #define mt_min_slot_count(x) mt_min_slots[mte_node_type(x)]
117 #define MAPLE_BIG_NODE_SLOTS (MAPLE_RANGE64_SLOTS * 2 + 2)
118 #define MAPLE_BIG_NODE_GAPS (MAPLE_ARANGE64_SLOTS * 2 + 1)
120 struct maple_big_node
{
121 struct maple_pnode
*parent
;
122 unsigned long pivot
[MAPLE_BIG_NODE_SLOTS
- 1];
124 struct maple_enode
*slot
[MAPLE_BIG_NODE_SLOTS
];
126 unsigned long padding
[MAPLE_BIG_NODE_GAPS
];
127 unsigned long gap
[MAPLE_BIG_NODE_GAPS
];
131 enum maple_type type
;
135 * The maple_subtree_state is used to build a tree to replace a segment of an
136 * existing tree in a more atomic way. Any walkers of the older tree will hit a
137 * dead node and restart on updates.
139 struct maple_subtree_state
{
140 struct ma_state
*orig_l
; /* Original left side of subtree */
141 struct ma_state
*orig_r
; /* Original right side of subtree */
142 struct ma_state
*l
; /* New left side of subtree */
143 struct ma_state
*m
; /* New middle of subtree (rare) */
144 struct ma_state
*r
; /* New right side of subtree */
145 struct ma_topiary
*free
; /* nodes to be freed */
146 struct ma_topiary
*destroy
; /* Nodes to be destroyed (walked and freed) */
147 struct maple_big_node
*bn
;
150 #ifdef CONFIG_KASAN_STACK
151 /* Prevent mas_wr_bnode() from exceeding the stack frame limit */
152 #define noinline_for_kasan noinline_for_stack
154 #define noinline_for_kasan inline
158 static inline struct maple_node
*mt_alloc_one(gfp_t gfp
)
160 return kmem_cache_alloc(maple_node_cache
, gfp
);
163 static inline int mt_alloc_bulk(gfp_t gfp
, size_t size
, void **nodes
)
165 return kmem_cache_alloc_bulk(maple_node_cache
, gfp
, size
, nodes
);
168 static inline void mt_free_bulk(size_t size
, void __rcu
**nodes
)
170 kmem_cache_free_bulk(maple_node_cache
, size
, (void **)nodes
);
173 static void mt_free_rcu(struct rcu_head
*head
)
175 struct maple_node
*node
= container_of(head
, struct maple_node
, rcu
);
177 kmem_cache_free(maple_node_cache
, node
);
181 * ma_free_rcu() - Use rcu callback to free a maple node
182 * @node: The node to free
184 * The maple tree uses the parent pointer to indicate this node is no longer in
185 * use and will be freed.
187 static void ma_free_rcu(struct maple_node
*node
)
189 WARN_ON(node
->parent
!= ma_parent_ptr(node
));
190 call_rcu(&node
->rcu
, mt_free_rcu
);
193 static void mas_set_height(struct ma_state
*mas
)
195 unsigned int new_flags
= mas
->tree
->ma_flags
;
197 new_flags
&= ~MT_FLAGS_HEIGHT_MASK
;
198 MAS_BUG_ON(mas
, mas
->depth
> MAPLE_HEIGHT_MAX
);
199 new_flags
|= mas
->depth
<< MT_FLAGS_HEIGHT_OFFSET
;
200 mas
->tree
->ma_flags
= new_flags
;
203 static unsigned int mas_mt_height(struct ma_state
*mas
)
205 return mt_height(mas
->tree
);
208 static inline enum maple_type
mte_node_type(const struct maple_enode
*entry
)
210 return ((unsigned long)entry
>> MAPLE_NODE_TYPE_SHIFT
) &
211 MAPLE_NODE_TYPE_MASK
;
214 static inline bool ma_is_dense(const enum maple_type type
)
216 return type
< maple_leaf_64
;
219 static inline bool ma_is_leaf(const enum maple_type type
)
221 return type
< maple_range_64
;
224 static inline bool mte_is_leaf(const struct maple_enode
*entry
)
226 return ma_is_leaf(mte_node_type(entry
));
230 * We also reserve values with the bottom two bits set to '10' which are
233 static inline bool mt_is_reserved(const void *entry
)
235 return ((unsigned long)entry
< MAPLE_RESERVED_RANGE
) &&
236 xa_is_internal(entry
);
239 static inline void mas_set_err(struct ma_state
*mas
, long err
)
241 mas
->node
= MA_ERROR(err
);
244 static inline bool mas_is_ptr(const struct ma_state
*mas
)
246 return mas
->node
== MAS_ROOT
;
249 static inline bool mas_is_start(const struct ma_state
*mas
)
251 return mas
->node
== MAS_START
;
254 bool mas_is_err(struct ma_state
*mas
)
256 return xa_is_err(mas
->node
);
259 static __always_inline
bool mas_is_overflow(struct ma_state
*mas
)
261 if (unlikely(mas
->node
== MAS_OVERFLOW
))
267 static __always_inline
bool mas_is_underflow(struct ma_state
*mas
)
269 if (unlikely(mas
->node
== MAS_UNDERFLOW
))
275 static inline bool mas_searchable(struct ma_state
*mas
)
277 if (mas_is_none(mas
))
286 static inline struct maple_node
*mte_to_node(const struct maple_enode
*entry
)
288 return (struct maple_node
*)((unsigned long)entry
& ~MAPLE_NODE_MASK
);
292 * mte_to_mat() - Convert a maple encoded node to a maple topiary node.
293 * @entry: The maple encoded node
295 * Return: a maple topiary pointer
297 static inline struct maple_topiary
*mte_to_mat(const struct maple_enode
*entry
)
299 return (struct maple_topiary
*)
300 ((unsigned long)entry
& ~MAPLE_NODE_MASK
);
304 * mas_mn() - Get the maple state node.
305 * @mas: The maple state
307 * Return: the maple node (not encoded - bare pointer).
309 static inline struct maple_node
*mas_mn(const struct ma_state
*mas
)
311 return mte_to_node(mas
->node
);
315 * mte_set_node_dead() - Set a maple encoded node as dead.
316 * @mn: The maple encoded node.
318 static inline void mte_set_node_dead(struct maple_enode
*mn
)
320 mte_to_node(mn
)->parent
= ma_parent_ptr(mte_to_node(mn
));
321 smp_wmb(); /* Needed for RCU */
324 /* Bit 1 indicates the root is a node */
325 #define MAPLE_ROOT_NODE 0x02
326 /* maple_type stored bit 3-6 */
327 #define MAPLE_ENODE_TYPE_SHIFT 0x03
328 /* Bit 2 means a NULL somewhere below */
329 #define MAPLE_ENODE_NULL 0x04
331 static inline struct maple_enode
*mt_mk_node(const struct maple_node
*node
,
332 enum maple_type type
)
334 return (void *)((unsigned long)node
|
335 (type
<< MAPLE_ENODE_TYPE_SHIFT
) | MAPLE_ENODE_NULL
);
338 static inline void *mte_mk_root(const struct maple_enode
*node
)
340 return (void *)((unsigned long)node
| MAPLE_ROOT_NODE
);
343 static inline void *mte_safe_root(const struct maple_enode
*node
)
345 return (void *)((unsigned long)node
& ~MAPLE_ROOT_NODE
);
348 static inline void *mte_set_full(const struct maple_enode
*node
)
350 return (void *)((unsigned long)node
& ~MAPLE_ENODE_NULL
);
353 static inline void *mte_clear_full(const struct maple_enode
*node
)
355 return (void *)((unsigned long)node
| MAPLE_ENODE_NULL
);
358 static inline bool mte_has_null(const struct maple_enode
*node
)
360 return (unsigned long)node
& MAPLE_ENODE_NULL
;
363 static inline bool ma_is_root(struct maple_node
*node
)
365 return ((unsigned long)node
->parent
& MA_ROOT_PARENT
);
368 static inline bool mte_is_root(const struct maple_enode
*node
)
370 return ma_is_root(mte_to_node(node
));
373 static inline bool mas_is_root_limits(const struct ma_state
*mas
)
375 return !mas
->min
&& mas
->max
== ULONG_MAX
;
378 static inline bool mt_is_alloc(struct maple_tree
*mt
)
380 return (mt
->ma_flags
& MT_FLAGS_ALLOC_RANGE
);
385 * Excluding root, the parent pointer is 256B aligned like all other tree nodes.
386 * When storing a 32 or 64 bit values, the offset can fit into 5 bits. The 16
387 * bit values need an extra bit to store the offset. This extra bit comes from
388 * a reuse of the last bit in the node type. This is possible by using bit 1 to
389 * indicate if bit 2 is part of the type or the slot.
393 * 0x?00 = 16 bit nodes
394 * 0x010 = 32 bit nodes
395 * 0x110 = 64 bit nodes
397 * Slot size and alignment
399 * 0b?00 : 16 bit values, type in 0-1, slot in 2-7
400 * 0b010 : 32 bit values, type in 0-2, slot in 3-7
401 * 0b110 : 64 bit values, type in 0-2, slot in 3-7
404 #define MAPLE_PARENT_ROOT 0x01
406 #define MAPLE_PARENT_SLOT_SHIFT 0x03
407 #define MAPLE_PARENT_SLOT_MASK 0xF8
409 #define MAPLE_PARENT_16B_SLOT_SHIFT 0x02
410 #define MAPLE_PARENT_16B_SLOT_MASK 0xFC
412 #define MAPLE_PARENT_RANGE64 0x06
413 #define MAPLE_PARENT_RANGE32 0x04
414 #define MAPLE_PARENT_NOT_RANGE16 0x02
417 * mte_parent_shift() - Get the parent shift for the slot storage.
418 * @parent: The parent pointer cast as an unsigned long
419 * Return: The shift into that pointer to the star to of the slot
421 static inline unsigned long mte_parent_shift(unsigned long parent
)
423 /* Note bit 1 == 0 means 16B */
424 if (likely(parent
& MAPLE_PARENT_NOT_RANGE16
))
425 return MAPLE_PARENT_SLOT_SHIFT
;
427 return MAPLE_PARENT_16B_SLOT_SHIFT
;
431 * mte_parent_slot_mask() - Get the slot mask for the parent.
432 * @parent: The parent pointer cast as an unsigned long.
433 * Return: The slot mask for that parent.
435 static inline unsigned long mte_parent_slot_mask(unsigned long parent
)
437 /* Note bit 1 == 0 means 16B */
438 if (likely(parent
& MAPLE_PARENT_NOT_RANGE16
))
439 return MAPLE_PARENT_SLOT_MASK
;
441 return MAPLE_PARENT_16B_SLOT_MASK
;
445 * mas_parent_type() - Return the maple_type of the parent from the stored
447 * @mas: The maple state
448 * @enode: The maple_enode to extract the parent's enum
449 * Return: The node->parent maple_type
452 enum maple_type
mas_parent_type(struct ma_state
*mas
, struct maple_enode
*enode
)
454 unsigned long p_type
;
456 p_type
= (unsigned long)mte_to_node(enode
)->parent
;
457 if (WARN_ON(p_type
& MAPLE_PARENT_ROOT
))
460 p_type
&= MAPLE_NODE_MASK
;
461 p_type
&= ~mte_parent_slot_mask(p_type
);
463 case MAPLE_PARENT_RANGE64
: /* or MAPLE_PARENT_ARANGE64 */
464 if (mt_is_alloc(mas
->tree
))
465 return maple_arange_64
;
466 return maple_range_64
;
473 * mas_set_parent() - Set the parent node and encode the slot
474 * @enode: The encoded maple node.
475 * @parent: The encoded maple node that is the parent of @enode.
476 * @slot: The slot that @enode resides in @parent.
478 * Slot number is encoded in the enode->parent bit 3-6 or 2-6, depending on the
482 void mas_set_parent(struct ma_state
*mas
, struct maple_enode
*enode
,
483 const struct maple_enode
*parent
, unsigned char slot
)
485 unsigned long val
= (unsigned long)parent
;
488 enum maple_type p_type
= mte_node_type(parent
);
490 MAS_BUG_ON(mas
, p_type
== maple_dense
);
491 MAS_BUG_ON(mas
, p_type
== maple_leaf_64
);
495 case maple_arange_64
:
496 shift
= MAPLE_PARENT_SLOT_SHIFT
;
497 type
= MAPLE_PARENT_RANGE64
;
506 val
&= ~MAPLE_NODE_MASK
; /* Clear all node metadata in parent */
507 val
|= (slot
<< shift
) | type
;
508 mte_to_node(enode
)->parent
= ma_parent_ptr(val
);
512 * mte_parent_slot() - get the parent slot of @enode.
513 * @enode: The encoded maple node.
515 * Return: The slot in the parent node where @enode resides.
517 static inline unsigned int mte_parent_slot(const struct maple_enode
*enode
)
519 unsigned long val
= (unsigned long)mte_to_node(enode
)->parent
;
521 if (val
& MA_ROOT_PARENT
)
525 * Okay to use MAPLE_PARENT_16B_SLOT_MASK as the last bit will be lost
526 * by shift if the parent shift is MAPLE_PARENT_SLOT_SHIFT
528 return (val
& MAPLE_PARENT_16B_SLOT_MASK
) >> mte_parent_shift(val
);
532 * mte_parent() - Get the parent of @node.
533 * @node: The encoded maple node.
535 * Return: The parent maple node.
537 static inline struct maple_node
*mte_parent(const struct maple_enode
*enode
)
539 return (void *)((unsigned long)
540 (mte_to_node(enode
)->parent
) & ~MAPLE_NODE_MASK
);
544 * ma_dead_node() - check if the @enode is dead.
545 * @enode: The encoded maple node
547 * Return: true if dead, false otherwise.
549 static inline bool ma_dead_node(const struct maple_node
*node
)
551 struct maple_node
*parent
;
553 /* Do not reorder reads from the node prior to the parent check */
555 parent
= (void *)((unsigned long) node
->parent
& ~MAPLE_NODE_MASK
);
556 return (parent
== node
);
560 * mte_dead_node() - check if the @enode is dead.
561 * @enode: The encoded maple node
563 * Return: true if dead, false otherwise.
565 static inline bool mte_dead_node(const struct maple_enode
*enode
)
567 struct maple_node
*parent
, *node
;
569 node
= mte_to_node(enode
);
570 /* Do not reorder reads from the node prior to the parent check */
572 parent
= mte_parent(enode
);
573 return (parent
== node
);
577 * mas_allocated() - Get the number of nodes allocated in a maple state.
578 * @mas: The maple state
580 * The ma_state alloc member is overloaded to hold a pointer to the first
581 * allocated node or to the number of requested nodes to allocate. If bit 0 is
582 * set, then the alloc contains the number of requested nodes. If there is an
583 * allocated node, then the total allocated nodes is in that node.
585 * Return: The total number of nodes allocated
587 static inline unsigned long mas_allocated(const struct ma_state
*mas
)
589 if (!mas
->alloc
|| ((unsigned long)mas
->alloc
& 0x1))
592 return mas
->alloc
->total
;
596 * mas_set_alloc_req() - Set the requested number of allocations.
597 * @mas: the maple state
598 * @count: the number of allocations.
600 * The requested number of allocations is either in the first allocated node,
601 * located in @mas->alloc->request_count, or directly in @mas->alloc if there is
602 * no allocated node. Set the request either in the node or do the necessary
603 * encoding to store in @mas->alloc directly.
605 static inline void mas_set_alloc_req(struct ma_state
*mas
, unsigned long count
)
607 if (!mas
->alloc
|| ((unsigned long)mas
->alloc
& 0x1)) {
611 mas
->alloc
= (struct maple_alloc
*)(((count
) << 1U) | 1U);
615 mas
->alloc
->request_count
= count
;
619 * mas_alloc_req() - get the requested number of allocations.
620 * @mas: The maple state
622 * The alloc count is either stored directly in @mas, or in
623 * @mas->alloc->request_count if there is at least one node allocated. Decode
624 * the request count if it's stored directly in @mas->alloc.
626 * Return: The allocation request count.
628 static inline unsigned int mas_alloc_req(const struct ma_state
*mas
)
630 if ((unsigned long)mas
->alloc
& 0x1)
631 return (unsigned long)(mas
->alloc
) >> 1;
633 return mas
->alloc
->request_count
;
638 * ma_pivots() - Get a pointer to the maple node pivots.
639 * @node - the maple node
640 * @type - the node type
642 * In the event of a dead node, this array may be %NULL
644 * Return: A pointer to the maple node pivots
646 static inline unsigned long *ma_pivots(struct maple_node
*node
,
647 enum maple_type type
)
650 case maple_arange_64
:
651 return node
->ma64
.pivot
;
654 return node
->mr64
.pivot
;
662 * ma_gaps() - Get a pointer to the maple node gaps.
663 * @node - the maple node
664 * @type - the node type
666 * Return: A pointer to the maple node gaps
668 static inline unsigned long *ma_gaps(struct maple_node
*node
,
669 enum maple_type type
)
672 case maple_arange_64
:
673 return node
->ma64
.gap
;
683 * mas_pivot() - Get the pivot at @piv of the maple encoded node.
684 * @mas: The maple state.
687 * Return: the pivot at @piv of @mn.
689 static inline unsigned long mas_pivot(struct ma_state
*mas
, unsigned char piv
)
691 struct maple_node
*node
= mas_mn(mas
);
692 enum maple_type type
= mte_node_type(mas
->node
);
694 if (MAS_WARN_ON(mas
, piv
>= mt_pivots
[type
])) {
695 mas_set_err(mas
, -EIO
);
700 case maple_arange_64
:
701 return node
->ma64
.pivot
[piv
];
704 return node
->mr64
.pivot
[piv
];
712 * mas_safe_pivot() - get the pivot at @piv or mas->max.
713 * @mas: The maple state
714 * @pivots: The pointer to the maple node pivots
715 * @piv: The pivot to fetch
716 * @type: The maple node type
718 * Return: The pivot at @piv within the limit of the @pivots array, @mas->max
721 static inline unsigned long
722 mas_safe_pivot(const struct ma_state
*mas
, unsigned long *pivots
,
723 unsigned char piv
, enum maple_type type
)
725 if (piv
>= mt_pivots
[type
])
732 * mas_safe_min() - Return the minimum for a given offset.
733 * @mas: The maple state
734 * @pivots: The pointer to the maple node pivots
735 * @offset: The offset into the pivot array
737 * Return: The minimum range value that is contained in @offset.
739 static inline unsigned long
740 mas_safe_min(struct ma_state
*mas
, unsigned long *pivots
, unsigned char offset
)
743 return pivots
[offset
- 1] + 1;
749 * mte_set_pivot() - Set a pivot to a value in an encoded maple node.
750 * @mn: The encoded maple node
751 * @piv: The pivot offset
752 * @val: The value of the pivot
754 static inline void mte_set_pivot(struct maple_enode
*mn
, unsigned char piv
,
757 struct maple_node
*node
= mte_to_node(mn
);
758 enum maple_type type
= mte_node_type(mn
);
760 BUG_ON(piv
>= mt_pivots
[type
]);
765 node
->mr64
.pivot
[piv
] = val
;
767 case maple_arange_64
:
768 node
->ma64
.pivot
[piv
] = val
;
777 * ma_slots() - Get a pointer to the maple node slots.
778 * @mn: The maple node
779 * @mt: The maple node type
781 * Return: A pointer to the maple node slots
783 static inline void __rcu
**ma_slots(struct maple_node
*mn
, enum maple_type mt
)
787 case maple_arange_64
:
788 return mn
->ma64
.slot
;
791 return mn
->mr64
.slot
;
797 static inline bool mt_write_locked(const struct maple_tree
*mt
)
799 return mt_external_lock(mt
) ? mt_write_lock_is_held(mt
) :
800 lockdep_is_held(&mt
->ma_lock
);
803 static inline bool mt_locked(const struct maple_tree
*mt
)
805 return mt_external_lock(mt
) ? mt_lock_is_held(mt
) :
806 lockdep_is_held(&mt
->ma_lock
);
809 static inline void *mt_slot(const struct maple_tree
*mt
,
810 void __rcu
**slots
, unsigned char offset
)
812 return rcu_dereference_check(slots
[offset
], mt_locked(mt
));
815 static inline void *mt_slot_locked(struct maple_tree
*mt
, void __rcu
**slots
,
816 unsigned char offset
)
818 return rcu_dereference_protected(slots
[offset
], mt_write_locked(mt
));
821 * mas_slot_locked() - Get the slot value when holding the maple tree lock.
822 * @mas: The maple state
823 * @slots: The pointer to the slots
824 * @offset: The offset into the slots array to fetch
826 * Return: The entry stored in @slots at the @offset.
828 static inline void *mas_slot_locked(struct ma_state
*mas
, void __rcu
**slots
,
829 unsigned char offset
)
831 return mt_slot_locked(mas
->tree
, slots
, offset
);
835 * mas_slot() - Get the slot value when not holding the maple tree lock.
836 * @mas: The maple state
837 * @slots: The pointer to the slots
838 * @offset: The offset into the slots array to fetch
840 * Return: The entry stored in @slots at the @offset
842 static inline void *mas_slot(struct ma_state
*mas
, void __rcu
**slots
,
843 unsigned char offset
)
845 return mt_slot(mas
->tree
, slots
, offset
);
849 * mas_root() - Get the maple tree root.
850 * @mas: The maple state.
852 * Return: The pointer to the root of the tree
854 static inline void *mas_root(struct ma_state
*mas
)
856 return rcu_dereference_check(mas
->tree
->ma_root
, mt_locked(mas
->tree
));
859 static inline void *mt_root_locked(struct maple_tree
*mt
)
861 return rcu_dereference_protected(mt
->ma_root
, mt_write_locked(mt
));
865 * mas_root_locked() - Get the maple tree root when holding the maple tree lock.
866 * @mas: The maple state.
868 * Return: The pointer to the root of the tree
870 static inline void *mas_root_locked(struct ma_state
*mas
)
872 return mt_root_locked(mas
->tree
);
875 static inline struct maple_metadata
*ma_meta(struct maple_node
*mn
,
879 case maple_arange_64
:
880 return &mn
->ma64
.meta
;
882 return &mn
->mr64
.meta
;
887 * ma_set_meta() - Set the metadata information of a node.
888 * @mn: The maple node
889 * @mt: The maple node type
890 * @offset: The offset of the highest sub-gap in this node.
891 * @end: The end of the data in this node.
893 static inline void ma_set_meta(struct maple_node
*mn
, enum maple_type mt
,
894 unsigned char offset
, unsigned char end
)
896 struct maple_metadata
*meta
= ma_meta(mn
, mt
);
903 * mt_clear_meta() - clear the metadata information of a node, if it exists
904 * @mt: The maple tree
905 * @mn: The maple node
906 * @type: The maple node type
907 * @offset: The offset of the highest sub-gap in this node.
908 * @end: The end of the data in this node.
910 static inline void mt_clear_meta(struct maple_tree
*mt
, struct maple_node
*mn
,
911 enum maple_type type
)
913 struct maple_metadata
*meta
;
914 unsigned long *pivots
;
920 pivots
= mn
->mr64
.pivot
;
921 if (unlikely(pivots
[MAPLE_RANGE64_SLOTS
- 2])) {
922 slots
= mn
->mr64
.slot
;
923 next
= mt_slot_locked(mt
, slots
,
924 MAPLE_RANGE64_SLOTS
- 1);
925 if (unlikely((mte_to_node(next
) &&
926 mte_node_type(next
))))
927 return; /* no metadata, could be node */
930 case maple_arange_64
:
931 meta
= ma_meta(mn
, type
);
942 * ma_meta_end() - Get the data end of a node from the metadata
943 * @mn: The maple node
944 * @mt: The maple node type
946 static inline unsigned char ma_meta_end(struct maple_node
*mn
,
949 struct maple_metadata
*meta
= ma_meta(mn
, mt
);
955 * ma_meta_gap() - Get the largest gap location of a node from the metadata
956 * @mn: The maple node
957 * @mt: The maple node type
959 static inline unsigned char ma_meta_gap(struct maple_node
*mn
,
962 return mn
->ma64
.meta
.gap
;
966 * ma_set_meta_gap() - Set the largest gap location in a nodes metadata
967 * @mn: The maple node
968 * @mn: The maple node type
969 * @offset: The location of the largest gap.
971 static inline void ma_set_meta_gap(struct maple_node
*mn
, enum maple_type mt
,
972 unsigned char offset
)
975 struct maple_metadata
*meta
= ma_meta(mn
, mt
);
981 * mat_add() - Add a @dead_enode to the ma_topiary of a list of dead nodes.
982 * @mat - the ma_topiary, a linked list of dead nodes.
983 * @dead_enode - the node to be marked as dead and added to the tail of the list
985 * Add the @dead_enode to the linked list in @mat.
987 static inline void mat_add(struct ma_topiary
*mat
,
988 struct maple_enode
*dead_enode
)
990 mte_set_node_dead(dead_enode
);
991 mte_to_mat(dead_enode
)->next
= NULL
;
993 mat
->tail
= mat
->head
= dead_enode
;
997 mte_to_mat(mat
->tail
)->next
= dead_enode
;
998 mat
->tail
= dead_enode
;
1001 static void mt_free_walk(struct rcu_head
*head
);
1002 static void mt_destroy_walk(struct maple_enode
*enode
, struct maple_tree
*mt
,
1005 * mas_mat_destroy() - Free all nodes and subtrees in a dead list.
1006 * @mas - the maple state
1007 * @mat - the ma_topiary linked list of dead nodes to free.
1009 * Destroy walk a dead list.
1011 static void mas_mat_destroy(struct ma_state
*mas
, struct ma_topiary
*mat
)
1013 struct maple_enode
*next
;
1014 struct maple_node
*node
;
1015 bool in_rcu
= mt_in_rcu(mas
->tree
);
1018 next
= mte_to_mat(mat
->head
)->next
;
1019 node
= mte_to_node(mat
->head
);
1020 mt_destroy_walk(mat
->head
, mas
->tree
, !in_rcu
);
1022 call_rcu(&node
->rcu
, mt_free_walk
);
1027 * mas_descend() - Descend into the slot stored in the ma_state.
1028 * @mas - the maple state.
1030 * Note: Not RCU safe, only use in write side or debug code.
1032 static inline void mas_descend(struct ma_state
*mas
)
1034 enum maple_type type
;
1035 unsigned long *pivots
;
1036 struct maple_node
*node
;
1040 type
= mte_node_type(mas
->node
);
1041 pivots
= ma_pivots(node
, type
);
1042 slots
= ma_slots(node
, type
);
1045 mas
->min
= pivots
[mas
->offset
- 1] + 1;
1046 mas
->max
= mas_safe_pivot(mas
, pivots
, mas
->offset
, type
);
1047 mas
->node
= mas_slot(mas
, slots
, mas
->offset
);
1051 * mte_set_gap() - Set a maple node gap.
1052 * @mn: The encoded maple node
1053 * @gap: The offset of the gap to set
1054 * @val: The gap value
1056 static inline void mte_set_gap(const struct maple_enode
*mn
,
1057 unsigned char gap
, unsigned long val
)
1059 switch (mte_node_type(mn
)) {
1062 case maple_arange_64
:
1063 mte_to_node(mn
)->ma64
.gap
[gap
] = val
;
1069 * mas_ascend() - Walk up a level of the tree.
1070 * @mas: The maple state
1072 * Sets the @mas->max and @mas->min to the correct values when walking up. This
1073 * may cause several levels of walking up to find the correct min and max.
1074 * May find a dead node which will cause a premature return.
1075 * Return: 1 on dead node, 0 otherwise
1077 static int mas_ascend(struct ma_state
*mas
)
1079 struct maple_enode
*p_enode
; /* parent enode. */
1080 struct maple_enode
*a_enode
; /* ancestor enode. */
1081 struct maple_node
*a_node
; /* ancestor node. */
1082 struct maple_node
*p_node
; /* parent node. */
1083 unsigned char a_slot
;
1084 enum maple_type a_type
;
1085 unsigned long min
, max
;
1086 unsigned long *pivots
;
1087 bool set_max
= false, set_min
= false;
1089 a_node
= mas_mn(mas
);
1090 if (ma_is_root(a_node
)) {
1095 p_node
= mte_parent(mas
->node
);
1096 if (unlikely(a_node
== p_node
))
1099 a_type
= mas_parent_type(mas
, mas
->node
);
1100 mas
->offset
= mte_parent_slot(mas
->node
);
1101 a_enode
= mt_mk_node(p_node
, a_type
);
1103 /* Check to make sure all parent information is still accurate */
1104 if (p_node
!= mte_parent(mas
->node
))
1107 mas
->node
= a_enode
;
1109 if (mte_is_root(a_enode
)) {
1110 mas
->max
= ULONG_MAX
;
1118 if (mas
->max
== ULONG_MAX
)
1125 a_type
= mas_parent_type(mas
, p_enode
);
1126 a_node
= mte_parent(p_enode
);
1127 a_slot
= mte_parent_slot(p_enode
);
1128 a_enode
= mt_mk_node(a_node
, a_type
);
1129 pivots
= ma_pivots(a_node
, a_type
);
1131 if (unlikely(ma_dead_node(a_node
)))
1134 if (!set_min
&& a_slot
) {
1136 min
= pivots
[a_slot
- 1] + 1;
1139 if (!set_max
&& a_slot
< mt_pivots
[a_type
]) {
1141 max
= pivots
[a_slot
];
1144 if (unlikely(ma_dead_node(a_node
)))
1147 if (unlikely(ma_is_root(a_node
)))
1150 } while (!set_min
|| !set_max
);
1158 * mas_pop_node() - Get a previously allocated maple node from the maple state.
1159 * @mas: The maple state
1161 * Return: A pointer to a maple node.
1163 static inline struct maple_node
*mas_pop_node(struct ma_state
*mas
)
1165 struct maple_alloc
*ret
, *node
= mas
->alloc
;
1166 unsigned long total
= mas_allocated(mas
);
1167 unsigned int req
= mas_alloc_req(mas
);
1169 /* nothing or a request pending. */
1170 if (WARN_ON(!total
))
1174 /* single allocation in this ma_state */
1180 if (node
->node_count
== 1) {
1181 /* Single allocation in this node. */
1182 mas
->alloc
= node
->slot
[0];
1183 mas
->alloc
->total
= node
->total
- 1;
1188 ret
= node
->slot
[--node
->node_count
];
1189 node
->slot
[node
->node_count
] = NULL
;
1195 mas_set_alloc_req(mas
, req
);
1198 memset(ret
, 0, sizeof(*ret
));
1199 return (struct maple_node
*)ret
;
1203 * mas_push_node() - Push a node back on the maple state allocation.
1204 * @mas: The maple state
1205 * @used: The used maple node
1207 * Stores the maple node back into @mas->alloc for reuse. Updates allocated and
1208 * requested node count as necessary.
1210 static inline void mas_push_node(struct ma_state
*mas
, struct maple_node
*used
)
1212 struct maple_alloc
*reuse
= (struct maple_alloc
*)used
;
1213 struct maple_alloc
*head
= mas
->alloc
;
1214 unsigned long count
;
1215 unsigned int requested
= mas_alloc_req(mas
);
1217 count
= mas_allocated(mas
);
1219 reuse
->request_count
= 0;
1220 reuse
->node_count
= 0;
1221 if (count
&& (head
->node_count
< MAPLE_ALLOC_SLOTS
)) {
1222 head
->slot
[head
->node_count
++] = reuse
;
1228 if ((head
) && !((unsigned long)head
& 0x1)) {
1229 reuse
->slot
[0] = head
;
1230 reuse
->node_count
= 1;
1231 reuse
->total
+= head
->total
;
1237 mas_set_alloc_req(mas
, requested
- 1);
1241 * mas_alloc_nodes() - Allocate nodes into a maple state
1242 * @mas: The maple state
1243 * @gfp: The GFP Flags
1245 static inline void mas_alloc_nodes(struct ma_state
*mas
, gfp_t gfp
)
1247 struct maple_alloc
*node
;
1248 unsigned long allocated
= mas_allocated(mas
);
1249 unsigned int requested
= mas_alloc_req(mas
);
1251 void **slots
= NULL
;
1252 unsigned int max_req
= 0;
1257 mas_set_alloc_req(mas
, 0);
1258 if (mas
->mas_flags
& MA_STATE_PREALLOC
) {
1261 WARN_ON(!allocated
);
1264 if (!allocated
|| mas
->alloc
->node_count
== MAPLE_ALLOC_SLOTS
) {
1265 node
= (struct maple_alloc
*)mt_alloc_one(gfp
);
1270 node
->slot
[0] = mas
->alloc
;
1271 node
->node_count
= 1;
1273 node
->node_count
= 0;
1277 node
->total
= ++allocated
;
1282 node
->request_count
= 0;
1284 max_req
= MAPLE_ALLOC_SLOTS
- node
->node_count
;
1285 slots
= (void **)&node
->slot
[node
->node_count
];
1286 max_req
= min(requested
, max_req
);
1287 count
= mt_alloc_bulk(gfp
, max_req
, slots
);
1291 if (node
->node_count
== 0) {
1292 node
->slot
[0]->node_count
= 0;
1293 node
->slot
[0]->request_count
= 0;
1296 node
->node_count
+= count
;
1298 node
= node
->slot
[0];
1301 mas
->alloc
->total
= allocated
;
1305 /* Clean up potential freed allocations on bulk failure */
1306 memset(slots
, 0, max_req
* sizeof(unsigned long));
1308 mas_set_alloc_req(mas
, requested
);
1309 if (mas
->alloc
&& !(((unsigned long)mas
->alloc
& 0x1)))
1310 mas
->alloc
->total
= allocated
;
1311 mas_set_err(mas
, -ENOMEM
);
1315 * mas_free() - Free an encoded maple node
1316 * @mas: The maple state
1317 * @used: The encoded maple node to free.
1319 * Uses rcu free if necessary, pushes @used back on the maple state allocations
1322 static inline void mas_free(struct ma_state
*mas
, struct maple_enode
*used
)
1324 struct maple_node
*tmp
= mte_to_node(used
);
1326 if (mt_in_rcu(mas
->tree
))
1329 mas_push_node(mas
, tmp
);
1333 * mas_node_count() - Check if enough nodes are allocated and request more if
1334 * there is not enough nodes.
1335 * @mas: The maple state
1336 * @count: The number of nodes needed
1337 * @gfp: the gfp flags
1339 static void mas_node_count_gfp(struct ma_state
*mas
, int count
, gfp_t gfp
)
1341 unsigned long allocated
= mas_allocated(mas
);
1343 if (allocated
< count
) {
1344 mas_set_alloc_req(mas
, count
- allocated
);
1345 mas_alloc_nodes(mas
, gfp
);
1350 * mas_node_count() - Check if enough nodes are allocated and request more if
1351 * there is not enough nodes.
1352 * @mas: The maple state
1353 * @count: The number of nodes needed
1355 * Note: Uses GFP_NOWAIT | __GFP_NOWARN for gfp flags.
1357 static void mas_node_count(struct ma_state
*mas
, int count
)
1359 return mas_node_count_gfp(mas
, count
, GFP_NOWAIT
| __GFP_NOWARN
);
1363 * mas_start() - Sets up maple state for operations.
1364 * @mas: The maple state.
1366 * If mas->node == MAS_START, then set the min, max and depth to
1370 * - If mas->node is an error or not MAS_START, return NULL.
1371 * - If it's an empty tree: NULL & mas->node == MAS_NONE
1372 * - If it's a single entry: The entry & mas->node == MAS_ROOT
1373 * - If it's a tree: NULL & mas->node == safe root node.
1375 static inline struct maple_enode
*mas_start(struct ma_state
*mas
)
1377 if (likely(mas_is_start(mas
))) {
1378 struct maple_enode
*root
;
1381 mas
->max
= ULONG_MAX
;
1385 root
= mas_root(mas
);
1386 /* Tree with nodes */
1387 if (likely(xa_is_node(root
))) {
1389 mas
->node
= mte_safe_root(root
);
1391 if (mte_dead_node(mas
->node
))
1398 if (unlikely(!root
)) {
1399 mas
->node
= MAS_NONE
;
1400 mas
->offset
= MAPLE_NODE_SLOTS
;
1404 /* Single entry tree */
1405 mas
->node
= MAS_ROOT
;
1406 mas
->offset
= MAPLE_NODE_SLOTS
;
1408 /* Single entry tree. */
1419 * ma_data_end() - Find the end of the data in a node.
1420 * @node: The maple node
1421 * @type: The maple node type
1422 * @pivots: The array of pivots in the node
1423 * @max: The maximum value in the node
1425 * Uses metadata to find the end of the data when possible.
1426 * Return: The zero indexed last slot with data (may be null).
1428 static inline unsigned char ma_data_end(struct maple_node
*node
,
1429 enum maple_type type
,
1430 unsigned long *pivots
,
1433 unsigned char offset
;
1438 if (type
== maple_arange_64
)
1439 return ma_meta_end(node
, type
);
1441 offset
= mt_pivots
[type
] - 1;
1442 if (likely(!pivots
[offset
]))
1443 return ma_meta_end(node
, type
);
1445 if (likely(pivots
[offset
] == max
))
1448 return mt_pivots
[type
];
1452 * mas_data_end() - Find the end of the data (slot).
1453 * @mas: the maple state
1455 * This method is optimized to check the metadata of a node if the node type
1456 * supports data end metadata.
1458 * Return: The zero indexed last slot with data (may be null).
1460 static inline unsigned char mas_data_end(struct ma_state
*mas
)
1462 enum maple_type type
;
1463 struct maple_node
*node
;
1464 unsigned char offset
;
1465 unsigned long *pivots
;
1467 type
= mte_node_type(mas
->node
);
1469 if (type
== maple_arange_64
)
1470 return ma_meta_end(node
, type
);
1472 pivots
= ma_pivots(node
, type
);
1473 if (unlikely(ma_dead_node(node
)))
1476 offset
= mt_pivots
[type
] - 1;
1477 if (likely(!pivots
[offset
]))
1478 return ma_meta_end(node
, type
);
1480 if (likely(pivots
[offset
] == mas
->max
))
1483 return mt_pivots
[type
];
1487 * mas_leaf_max_gap() - Returns the largest gap in a leaf node
1488 * @mas - the maple state
1490 * Return: The maximum gap in the leaf.
1492 static unsigned long mas_leaf_max_gap(struct ma_state
*mas
)
1495 unsigned long pstart
, gap
, max_gap
;
1496 struct maple_node
*mn
;
1497 unsigned long *pivots
;
1500 unsigned char max_piv
;
1502 mt
= mte_node_type(mas
->node
);
1504 slots
= ma_slots(mn
, mt
);
1506 if (unlikely(ma_is_dense(mt
))) {
1508 for (i
= 0; i
< mt_slots
[mt
]; i
++) {
1523 * Check the first implied pivot optimizes the loop below and slot 1 may
1524 * be skipped if there is a gap in slot 0.
1526 pivots
= ma_pivots(mn
, mt
);
1527 if (likely(!slots
[0])) {
1528 max_gap
= pivots
[0] - mas
->min
+ 1;
1534 /* reduce max_piv as the special case is checked before the loop */
1535 max_piv
= ma_data_end(mn
, mt
, pivots
, mas
->max
) - 1;
1537 * Check end implied pivot which can only be a gap on the right most
1540 if (unlikely(mas
->max
== ULONG_MAX
) && !slots
[max_piv
+ 1]) {
1541 gap
= ULONG_MAX
- pivots
[max_piv
];
1546 for (; i
<= max_piv
; i
++) {
1547 /* data == no gap. */
1548 if (likely(slots
[i
]))
1551 pstart
= pivots
[i
- 1];
1552 gap
= pivots
[i
] - pstart
;
1556 /* There cannot be two gaps in a row. */
1563 * ma_max_gap() - Get the maximum gap in a maple node (non-leaf)
1564 * @node: The maple node
1565 * @gaps: The pointer to the gaps
1566 * @mt: The maple node type
1567 * @*off: Pointer to store the offset location of the gap.
1569 * Uses the metadata data end to scan backwards across set gaps.
1571 * Return: The maximum gap value
1573 static inline unsigned long
1574 ma_max_gap(struct maple_node
*node
, unsigned long *gaps
, enum maple_type mt
,
1577 unsigned char offset
, i
;
1578 unsigned long max_gap
= 0;
1580 i
= offset
= ma_meta_end(node
, mt
);
1582 if (gaps
[i
] > max_gap
) {
1593 * mas_max_gap() - find the largest gap in a non-leaf node and set the slot.
1594 * @mas: The maple state.
1596 * Return: The gap value.
1598 static inline unsigned long mas_max_gap(struct ma_state
*mas
)
1600 unsigned long *gaps
;
1601 unsigned char offset
;
1603 struct maple_node
*node
;
1605 mt
= mte_node_type(mas
->node
);
1607 return mas_leaf_max_gap(mas
);
1610 MAS_BUG_ON(mas
, mt
!= maple_arange_64
);
1611 offset
= ma_meta_gap(node
, mt
);
1612 gaps
= ma_gaps(node
, mt
);
1613 return gaps
[offset
];
1617 * mas_parent_gap() - Set the parent gap and any gaps above, as needed
1618 * @mas: The maple state
1619 * @offset: The gap offset in the parent to set
1620 * @new: The new gap value.
1622 * Set the parent gap then continue to set the gap upwards, using the metadata
1623 * of the parent to see if it is necessary to check the node above.
1625 static inline void mas_parent_gap(struct ma_state
*mas
, unsigned char offset
,
1628 unsigned long meta_gap
= 0;
1629 struct maple_node
*pnode
;
1630 struct maple_enode
*penode
;
1631 unsigned long *pgaps
;
1632 unsigned char meta_offset
;
1633 enum maple_type pmt
;
1635 pnode
= mte_parent(mas
->node
);
1636 pmt
= mas_parent_type(mas
, mas
->node
);
1637 penode
= mt_mk_node(pnode
, pmt
);
1638 pgaps
= ma_gaps(pnode
, pmt
);
1641 MAS_BUG_ON(mas
, pmt
!= maple_arange_64
);
1642 meta_offset
= ma_meta_gap(pnode
, pmt
);
1643 meta_gap
= pgaps
[meta_offset
];
1645 pgaps
[offset
] = new;
1647 if (meta_gap
== new)
1650 if (offset
!= meta_offset
) {
1654 ma_set_meta_gap(pnode
, pmt
, offset
);
1655 } else if (new < meta_gap
) {
1656 new = ma_max_gap(pnode
, pgaps
, pmt
, &meta_offset
);
1657 ma_set_meta_gap(pnode
, pmt
, meta_offset
);
1660 if (ma_is_root(pnode
))
1663 /* Go to the parent node. */
1664 pnode
= mte_parent(penode
);
1665 pmt
= mas_parent_type(mas
, penode
);
1666 pgaps
= ma_gaps(pnode
, pmt
);
1667 offset
= mte_parent_slot(penode
);
1668 penode
= mt_mk_node(pnode
, pmt
);
1673 * mas_update_gap() - Update a nodes gaps and propagate up if necessary.
1674 * @mas - the maple state.
1676 static inline void mas_update_gap(struct ma_state
*mas
)
1678 unsigned char pslot
;
1679 unsigned long p_gap
;
1680 unsigned long max_gap
;
1682 if (!mt_is_alloc(mas
->tree
))
1685 if (mte_is_root(mas
->node
))
1688 max_gap
= mas_max_gap(mas
);
1690 pslot
= mte_parent_slot(mas
->node
);
1691 p_gap
= ma_gaps(mte_parent(mas
->node
),
1692 mas_parent_type(mas
, mas
->node
))[pslot
];
1694 if (p_gap
!= max_gap
)
1695 mas_parent_gap(mas
, pslot
, max_gap
);
1699 * mas_adopt_children() - Set the parent pointer of all nodes in @parent to
1700 * @parent with the slot encoded.
1701 * @mas - the maple state (for the tree)
1702 * @parent - the maple encoded node containing the children.
1704 static inline void mas_adopt_children(struct ma_state
*mas
,
1705 struct maple_enode
*parent
)
1707 enum maple_type type
= mte_node_type(parent
);
1708 struct maple_node
*node
= mte_to_node(parent
);
1709 void __rcu
**slots
= ma_slots(node
, type
);
1710 unsigned long *pivots
= ma_pivots(node
, type
);
1711 struct maple_enode
*child
;
1712 unsigned char offset
;
1714 offset
= ma_data_end(node
, type
, pivots
, mas
->max
);
1716 child
= mas_slot_locked(mas
, slots
, offset
);
1717 mas_set_parent(mas
, child
, parent
, offset
);
1722 * mas_put_in_tree() - Put a new node in the tree, smp_wmb(), and mark the old
1724 * @mas - the maple state with the new node
1725 * @old_enode - The old maple encoded node to replace.
1727 static inline void mas_put_in_tree(struct ma_state
*mas
,
1728 struct maple_enode
*old_enode
)
1729 __must_hold(mas
->tree
->ma_lock
)
1731 unsigned char offset
;
1734 if (mte_is_root(mas
->node
)) {
1735 mas_mn(mas
)->parent
= ma_parent_ptr(mas_tree_parent(mas
));
1736 rcu_assign_pointer(mas
->tree
->ma_root
, mte_mk_root(mas
->node
));
1737 mas_set_height(mas
);
1740 offset
= mte_parent_slot(mas
->node
);
1741 slots
= ma_slots(mte_parent(mas
->node
),
1742 mas_parent_type(mas
, mas
->node
));
1743 rcu_assign_pointer(slots
[offset
], mas
->node
);
1746 mte_set_node_dead(old_enode
);
1750 * mas_replace_node() - Replace a node by putting it in the tree, marking it
1751 * dead, and freeing it.
1752 * the parent encoding to locate the maple node in the tree.
1753 * @mas - the ma_state with @mas->node pointing to the new node.
1754 * @old_enode - The old maple encoded node.
1756 static inline void mas_replace_node(struct ma_state
*mas
,
1757 struct maple_enode
*old_enode
)
1758 __must_hold(mas
->tree
->ma_lock
)
1760 mas_put_in_tree(mas
, old_enode
);
1761 mas_free(mas
, old_enode
);
1765 * mas_find_child() - Find a child who has the parent @mas->node.
1766 * @mas: the maple state with the parent.
1767 * @child: the maple state to store the child.
1769 static inline bool mas_find_child(struct ma_state
*mas
, struct ma_state
*child
)
1770 __must_hold(mas
->tree
->ma_lock
)
1773 unsigned char offset
;
1775 unsigned long *pivots
;
1776 struct maple_enode
*entry
;
1777 struct maple_node
*node
;
1780 mt
= mte_node_type(mas
->node
);
1782 slots
= ma_slots(node
, mt
);
1783 pivots
= ma_pivots(node
, mt
);
1784 end
= ma_data_end(node
, mt
, pivots
, mas
->max
);
1785 for (offset
= mas
->offset
; offset
<= end
; offset
++) {
1786 entry
= mas_slot_locked(mas
, slots
, offset
);
1787 if (mte_parent(entry
) == node
) {
1789 mas
->offset
= offset
+ 1;
1790 child
->offset
= offset
;
1800 * mab_shift_right() - Shift the data in mab right. Note, does not clean out the
1801 * old data or set b_node->b_end.
1802 * @b_node: the maple_big_node
1803 * @shift: the shift count
1805 static inline void mab_shift_right(struct maple_big_node
*b_node
,
1806 unsigned char shift
)
1808 unsigned long size
= b_node
->b_end
* sizeof(unsigned long);
1810 memmove(b_node
->pivot
+ shift
, b_node
->pivot
, size
);
1811 memmove(b_node
->slot
+ shift
, b_node
->slot
, size
);
1812 if (b_node
->type
== maple_arange_64
)
1813 memmove(b_node
->gap
+ shift
, b_node
->gap
, size
);
1817 * mab_middle_node() - Check if a middle node is needed (unlikely)
1818 * @b_node: the maple_big_node that contains the data.
1819 * @size: the amount of data in the b_node
1820 * @split: the potential split location
1821 * @slot_count: the size that can be stored in a single node being considered.
1823 * Return: true if a middle node is required.
1825 static inline bool mab_middle_node(struct maple_big_node
*b_node
, int split
,
1826 unsigned char slot_count
)
1828 unsigned char size
= b_node
->b_end
;
1830 if (size
>= 2 * slot_count
)
1833 if (!b_node
->slot
[split
] && (size
>= 2 * slot_count
- 1))
1840 * mab_no_null_split() - ensure the split doesn't fall on a NULL
1841 * @b_node: the maple_big_node with the data
1842 * @split: the suggested split location
1843 * @slot_count: the number of slots in the node being considered.
1845 * Return: the split location.
1847 static inline int mab_no_null_split(struct maple_big_node
*b_node
,
1848 unsigned char split
, unsigned char slot_count
)
1850 if (!b_node
->slot
[split
]) {
1852 * If the split is less than the max slot && the right side will
1853 * still be sufficient, then increment the split on NULL.
1855 if ((split
< slot_count
- 1) &&
1856 (b_node
->b_end
- split
) > (mt_min_slots
[b_node
->type
]))
1865 * mab_calc_split() - Calculate the split location and if there needs to be two
1867 * @bn: The maple_big_node with the data
1868 * @mid_split: The second split, if required. 0 otherwise.
1870 * Return: The first split location. The middle split is set in @mid_split.
1872 static inline int mab_calc_split(struct ma_state
*mas
,
1873 struct maple_big_node
*bn
, unsigned char *mid_split
, unsigned long min
)
1875 unsigned char b_end
= bn
->b_end
;
1876 int split
= b_end
/ 2; /* Assume equal split. */
1877 unsigned char slot_min
, slot_count
= mt_slots
[bn
->type
];
1880 * To support gap tracking, all NULL entries are kept together and a node cannot
1881 * end on a NULL entry, with the exception of the left-most leaf. The
1882 * limitation means that the split of a node must be checked for this condition
1883 * and be able to put more data in one direction or the other.
1885 if (unlikely((mas
->mas_flags
& MA_STATE_BULK
))) {
1887 split
= b_end
- mt_min_slots
[bn
->type
];
1889 if (!ma_is_leaf(bn
->type
))
1892 mas
->mas_flags
|= MA_STATE_REBALANCE
;
1893 if (!bn
->slot
[split
])
1899 * Although extremely rare, it is possible to enter what is known as the 3-way
1900 * split scenario. The 3-way split comes about by means of a store of a range
1901 * that overwrites the end and beginning of two full nodes. The result is a set
1902 * of entries that cannot be stored in 2 nodes. Sometimes, these two nodes can
1903 * also be located in different parent nodes which are also full. This can
1904 * carry upwards all the way to the root in the worst case.
1906 if (unlikely(mab_middle_node(bn
, split
, slot_count
))) {
1908 *mid_split
= split
* 2;
1910 slot_min
= mt_min_slots
[bn
->type
];
1914 * Avoid having a range less than the slot count unless it
1915 * causes one node to be deficient.
1916 * NOTE: mt_min_slots is 1 based, b_end and split are zero.
1918 while ((split
< slot_count
- 1) &&
1919 ((bn
->pivot
[split
] - min
) < slot_count
- 1) &&
1920 (b_end
- split
> slot_min
))
1924 /* Avoid ending a node on a NULL entry */
1925 split
= mab_no_null_split(bn
, split
, slot_count
);
1927 if (unlikely(*mid_split
))
1928 *mid_split
= mab_no_null_split(bn
, *mid_split
, slot_count
);
1934 * mas_mab_cp() - Copy data from a maple state inclusively to a maple_big_node
1935 * and set @b_node->b_end to the next free slot.
1936 * @mas: The maple state
1937 * @mas_start: The starting slot to copy
1938 * @mas_end: The end slot to copy (inclusively)
1939 * @b_node: The maple_big_node to place the data
1940 * @mab_start: The starting location in maple_big_node to store the data.
1942 static inline void mas_mab_cp(struct ma_state
*mas
, unsigned char mas_start
,
1943 unsigned char mas_end
, struct maple_big_node
*b_node
,
1944 unsigned char mab_start
)
1947 struct maple_node
*node
;
1949 unsigned long *pivots
, *gaps
;
1950 int i
= mas_start
, j
= mab_start
;
1951 unsigned char piv_end
;
1954 mt
= mte_node_type(mas
->node
);
1955 pivots
= ma_pivots(node
, mt
);
1957 b_node
->pivot
[j
] = pivots
[i
++];
1958 if (unlikely(i
> mas_end
))
1963 piv_end
= min(mas_end
, mt_pivots
[mt
]);
1964 for (; i
< piv_end
; i
++, j
++) {
1965 b_node
->pivot
[j
] = pivots
[i
];
1966 if (unlikely(!b_node
->pivot
[j
]))
1969 if (unlikely(mas
->max
== b_node
->pivot
[j
]))
1973 if (likely(i
<= mas_end
))
1974 b_node
->pivot
[j
] = mas_safe_pivot(mas
, pivots
, i
, mt
);
1977 b_node
->b_end
= ++j
;
1979 slots
= ma_slots(node
, mt
);
1980 memcpy(b_node
->slot
+ mab_start
, slots
+ mas_start
, sizeof(void *) * j
);
1981 if (!ma_is_leaf(mt
) && mt_is_alloc(mas
->tree
)) {
1982 gaps
= ma_gaps(node
, mt
);
1983 memcpy(b_node
->gap
+ mab_start
, gaps
+ mas_start
,
1984 sizeof(unsigned long) * j
);
1989 * mas_leaf_set_meta() - Set the metadata of a leaf if possible.
1990 * @mas: The maple state
1991 * @node: The maple node
1992 * @pivots: pointer to the maple node pivots
1993 * @mt: The maple type
1994 * @end: The assumed end
1996 * Note, end may be incremented within this function but not modified at the
1997 * source. This is fine since the metadata is the last thing to be stored in a
1998 * node during a write.
2000 static inline void mas_leaf_set_meta(struct ma_state
*mas
,
2001 struct maple_node
*node
, unsigned long *pivots
,
2002 enum maple_type mt
, unsigned char end
)
2004 /* There is no room for metadata already */
2005 if (mt_pivots
[mt
] <= end
)
2008 if (pivots
[end
] && pivots
[end
] < mas
->max
)
2011 if (end
< mt_slots
[mt
] - 1)
2012 ma_set_meta(node
, mt
, 0, end
);
2016 * mab_mas_cp() - Copy data from maple_big_node to a maple encoded node.
2017 * @b_node: the maple_big_node that has the data
2018 * @mab_start: the start location in @b_node.
2019 * @mab_end: The end location in @b_node (inclusively)
2020 * @mas: The maple state with the maple encoded node.
2022 static inline void mab_mas_cp(struct maple_big_node
*b_node
,
2023 unsigned char mab_start
, unsigned char mab_end
,
2024 struct ma_state
*mas
, bool new_max
)
2027 enum maple_type mt
= mte_node_type(mas
->node
);
2028 struct maple_node
*node
= mte_to_node(mas
->node
);
2029 void __rcu
**slots
= ma_slots(node
, mt
);
2030 unsigned long *pivots
= ma_pivots(node
, mt
);
2031 unsigned long *gaps
= NULL
;
2034 if (mab_end
- mab_start
> mt_pivots
[mt
])
2037 if (!pivots
[mt_pivots
[mt
] - 1])
2038 slots
[mt_pivots
[mt
]] = NULL
;
2042 pivots
[j
++] = b_node
->pivot
[i
++];
2043 } while (i
<= mab_end
&& likely(b_node
->pivot
[i
]));
2045 memcpy(slots
, b_node
->slot
+ mab_start
,
2046 sizeof(void *) * (i
- mab_start
));
2049 mas
->max
= b_node
->pivot
[i
- 1];
2052 if (likely(!ma_is_leaf(mt
) && mt_is_alloc(mas
->tree
))) {
2053 unsigned long max_gap
= 0;
2054 unsigned char offset
= 0;
2056 gaps
= ma_gaps(node
, mt
);
2058 gaps
[--j
] = b_node
->gap
[--i
];
2059 if (gaps
[j
] > max_gap
) {
2065 ma_set_meta(node
, mt
, offset
, end
);
2067 mas_leaf_set_meta(mas
, node
, pivots
, mt
, end
);
2072 * mas_bulk_rebalance() - Rebalance the end of a tree after a bulk insert.
2073 * @mas: The maple state
2074 * @end: The maple node end
2075 * @mt: The maple node type
2077 static inline void mas_bulk_rebalance(struct ma_state
*mas
, unsigned char end
,
2080 if (!(mas
->mas_flags
& MA_STATE_BULK
))
2083 if (mte_is_root(mas
->node
))
2086 if (end
> mt_min_slots
[mt
]) {
2087 mas
->mas_flags
&= ~MA_STATE_REBALANCE
;
2093 * mas_store_b_node() - Store an @entry into the b_node while also copying the
2094 * data from a maple encoded node.
2095 * @wr_mas: the maple write state
2096 * @b_node: the maple_big_node to fill with data
2097 * @offset_end: the offset to end copying
2099 * Return: The actual end of the data stored in @b_node
2101 static noinline_for_kasan
void mas_store_b_node(struct ma_wr_state
*wr_mas
,
2102 struct maple_big_node
*b_node
, unsigned char offset_end
)
2105 unsigned char b_end
;
2106 /* Possible underflow of piv will wrap back to 0 before use. */
2108 struct ma_state
*mas
= wr_mas
->mas
;
2110 b_node
->type
= wr_mas
->type
;
2114 /* Copy start data up to insert. */
2115 mas_mab_cp(mas
, 0, slot
- 1, b_node
, 0);
2116 b_end
= b_node
->b_end
;
2117 piv
= b_node
->pivot
[b_end
- 1];
2121 if (piv
+ 1 < mas
->index
) {
2122 /* Handle range starting after old range */
2123 b_node
->slot
[b_end
] = wr_mas
->content
;
2124 if (!wr_mas
->content
)
2125 b_node
->gap
[b_end
] = mas
->index
- 1 - piv
;
2126 b_node
->pivot
[b_end
++] = mas
->index
- 1;
2129 /* Store the new entry. */
2130 mas
->offset
= b_end
;
2131 b_node
->slot
[b_end
] = wr_mas
->entry
;
2132 b_node
->pivot
[b_end
] = mas
->last
;
2135 if (mas
->last
>= mas
->max
)
2138 /* Handle new range ending before old range ends */
2139 piv
= mas_safe_pivot(mas
, wr_mas
->pivots
, offset_end
, wr_mas
->type
);
2140 if (piv
> mas
->last
) {
2141 if (piv
== ULONG_MAX
)
2142 mas_bulk_rebalance(mas
, b_node
->b_end
, wr_mas
->type
);
2144 if (offset_end
!= slot
)
2145 wr_mas
->content
= mas_slot_locked(mas
, wr_mas
->slots
,
2148 b_node
->slot
[++b_end
] = wr_mas
->content
;
2149 if (!wr_mas
->content
)
2150 b_node
->gap
[b_end
] = piv
- mas
->last
+ 1;
2151 b_node
->pivot
[b_end
] = piv
;
2154 slot
= offset_end
+ 1;
2155 if (slot
> wr_mas
->node_end
)
2158 /* Copy end data to the end of the node. */
2159 mas_mab_cp(mas
, slot
, wr_mas
->node_end
+ 1, b_node
, ++b_end
);
2164 b_node
->b_end
= b_end
;
2168 * mas_prev_sibling() - Find the previous node with the same parent.
2169 * @mas: the maple state
2171 * Return: True if there is a previous sibling, false otherwise.
2173 static inline bool mas_prev_sibling(struct ma_state
*mas
)
2175 unsigned int p_slot
= mte_parent_slot(mas
->node
);
2177 if (mte_is_root(mas
->node
))
2184 mas
->offset
= p_slot
- 1;
2190 * mas_next_sibling() - Find the next node with the same parent.
2191 * @mas: the maple state
2193 * Return: true if there is a next sibling, false otherwise.
2195 static inline bool mas_next_sibling(struct ma_state
*mas
)
2197 MA_STATE(parent
, mas
->tree
, mas
->index
, mas
->last
);
2199 if (mte_is_root(mas
->node
))
2203 mas_ascend(&parent
);
2204 parent
.offset
= mte_parent_slot(mas
->node
) + 1;
2205 if (parent
.offset
> mas_data_end(&parent
))
2214 * mte_node_or_node() - Return the encoded node or MAS_NONE.
2215 * @enode: The encoded maple node.
2217 * Shorthand to avoid setting %NULLs in the tree or maple_subtree_state.
2219 * Return: @enode or MAS_NONE
2221 static inline struct maple_enode
*mte_node_or_none(struct maple_enode
*enode
)
2226 return ma_enode_ptr(MAS_NONE
);
2230 * mas_wr_node_walk() - Find the correct offset for the index in the @mas.
2231 * @wr_mas: The maple write state
2233 * Uses mas_slot_locked() and does not need to worry about dead nodes.
2235 static inline void mas_wr_node_walk(struct ma_wr_state
*wr_mas
)
2237 struct ma_state
*mas
= wr_mas
->mas
;
2238 unsigned char count
, offset
;
2240 if (unlikely(ma_is_dense(wr_mas
->type
))) {
2241 wr_mas
->r_max
= wr_mas
->r_min
= mas
->index
;
2242 mas
->offset
= mas
->index
= mas
->min
;
2246 wr_mas
->node
= mas_mn(wr_mas
->mas
);
2247 wr_mas
->pivots
= ma_pivots(wr_mas
->node
, wr_mas
->type
);
2248 count
= wr_mas
->node_end
= ma_data_end(wr_mas
->node
, wr_mas
->type
,
2249 wr_mas
->pivots
, mas
->max
);
2250 offset
= mas
->offset
;
2252 while (offset
< count
&& mas
->index
> wr_mas
->pivots
[offset
])
2255 wr_mas
->r_max
= offset
< count
? wr_mas
->pivots
[offset
] : mas
->max
;
2256 wr_mas
->r_min
= mas_safe_min(mas
, wr_mas
->pivots
, offset
);
2257 wr_mas
->offset_end
= mas
->offset
= offset
;
2261 * mast_rebalance_next() - Rebalance against the next node
2262 * @mast: The maple subtree state
2263 * @old_r: The encoded maple node to the right (next node).
2265 static inline void mast_rebalance_next(struct maple_subtree_state
*mast
)
2267 unsigned char b_end
= mast
->bn
->b_end
;
2269 mas_mab_cp(mast
->orig_r
, 0, mt_slot_count(mast
->orig_r
->node
),
2271 mast
->orig_r
->last
= mast
->orig_r
->max
;
2275 * mast_rebalance_prev() - Rebalance against the previous node
2276 * @mast: The maple subtree state
2277 * @old_l: The encoded maple node to the left (previous node)
2279 static inline void mast_rebalance_prev(struct maple_subtree_state
*mast
)
2281 unsigned char end
= mas_data_end(mast
->orig_l
) + 1;
2282 unsigned char b_end
= mast
->bn
->b_end
;
2284 mab_shift_right(mast
->bn
, end
);
2285 mas_mab_cp(mast
->orig_l
, 0, end
- 1, mast
->bn
, 0);
2286 mast
->l
->min
= mast
->orig_l
->min
;
2287 mast
->orig_l
->index
= mast
->orig_l
->min
;
2288 mast
->bn
->b_end
= end
+ b_end
;
2289 mast
->l
->offset
+= end
;
2293 * mast_spanning_rebalance() - Rebalance nodes with nearest neighbour favouring
2294 * the node to the right. Checking the nodes to the right then the left at each
2295 * level upwards until root is reached.
2296 * Data is copied into the @mast->bn.
2297 * @mast: The maple_subtree_state.
2300 bool mast_spanning_rebalance(struct maple_subtree_state
*mast
)
2302 struct ma_state r_tmp
= *mast
->orig_r
;
2303 struct ma_state l_tmp
= *mast
->orig_l
;
2304 unsigned char depth
= 0;
2306 r_tmp
= *mast
->orig_r
;
2307 l_tmp
= *mast
->orig_l
;
2309 mas_ascend(mast
->orig_r
);
2310 mas_ascend(mast
->orig_l
);
2312 if (mast
->orig_r
->offset
< mas_data_end(mast
->orig_r
)) {
2313 mast
->orig_r
->offset
++;
2315 mas_descend(mast
->orig_r
);
2316 mast
->orig_r
->offset
= 0;
2319 mast_rebalance_next(mast
);
2320 *mast
->orig_l
= l_tmp
;
2322 } else if (mast
->orig_l
->offset
!= 0) {
2323 mast
->orig_l
->offset
--;
2325 mas_descend(mast
->orig_l
);
2326 mast
->orig_l
->offset
=
2327 mas_data_end(mast
->orig_l
);
2330 mast_rebalance_prev(mast
);
2331 *mast
->orig_r
= r_tmp
;
2334 } while (!mte_is_root(mast
->orig_r
->node
));
2336 *mast
->orig_r
= r_tmp
;
2337 *mast
->orig_l
= l_tmp
;
2342 * mast_ascend() - Ascend the original left and right maple states.
2343 * @mast: the maple subtree state.
2345 * Ascend the original left and right sides. Set the offsets to point to the
2346 * data already in the new tree (@mast->l and @mast->r).
2348 static inline void mast_ascend(struct maple_subtree_state
*mast
)
2350 MA_WR_STATE(wr_mas
, mast
->orig_r
, NULL
);
2351 mas_ascend(mast
->orig_l
);
2352 mas_ascend(mast
->orig_r
);
2354 mast
->orig_r
->offset
= 0;
2355 mast
->orig_r
->index
= mast
->r
->max
;
2356 /* last should be larger than or equal to index */
2357 if (mast
->orig_r
->last
< mast
->orig_r
->index
)
2358 mast
->orig_r
->last
= mast
->orig_r
->index
;
2360 wr_mas
.type
= mte_node_type(mast
->orig_r
->node
);
2361 mas_wr_node_walk(&wr_mas
);
2362 /* Set up the left side of things */
2363 mast
->orig_l
->offset
= 0;
2364 mast
->orig_l
->index
= mast
->l
->min
;
2365 wr_mas
.mas
= mast
->orig_l
;
2366 wr_mas
.type
= mte_node_type(mast
->orig_l
->node
);
2367 mas_wr_node_walk(&wr_mas
);
2369 mast
->bn
->type
= wr_mas
.type
;
2373 * mas_new_ma_node() - Create and return a new maple node. Helper function.
2374 * @mas: the maple state with the allocations.
2375 * @b_node: the maple_big_node with the type encoding.
2377 * Use the node type from the maple_big_node to allocate a new node from the
2378 * ma_state. This function exists mainly for code readability.
2380 * Return: A new maple encoded node
2382 static inline struct maple_enode
2383 *mas_new_ma_node(struct ma_state
*mas
, struct maple_big_node
*b_node
)
2385 return mt_mk_node(ma_mnode_ptr(mas_pop_node(mas
)), b_node
->type
);
2389 * mas_mab_to_node() - Set up right and middle nodes
2391 * @mas: the maple state that contains the allocations.
2392 * @b_node: the node which contains the data.
2393 * @left: The pointer which will have the left node
2394 * @right: The pointer which may have the right node
2395 * @middle: the pointer which may have the middle node (rare)
2396 * @mid_split: the split location for the middle node
2398 * Return: the split of left.
2400 static inline unsigned char mas_mab_to_node(struct ma_state
*mas
,
2401 struct maple_big_node
*b_node
, struct maple_enode
**left
,
2402 struct maple_enode
**right
, struct maple_enode
**middle
,
2403 unsigned char *mid_split
, unsigned long min
)
2405 unsigned char split
= 0;
2406 unsigned char slot_count
= mt_slots
[b_node
->type
];
2408 *left
= mas_new_ma_node(mas
, b_node
);
2413 if (b_node
->b_end
< slot_count
) {
2414 split
= b_node
->b_end
;
2416 split
= mab_calc_split(mas
, b_node
, mid_split
, min
);
2417 *right
= mas_new_ma_node(mas
, b_node
);
2421 *middle
= mas_new_ma_node(mas
, b_node
);
2428 * mab_set_b_end() - Add entry to b_node at b_node->b_end and increment the end
2430 * @b_node - the big node to add the entry
2431 * @mas - the maple state to get the pivot (mas->max)
2432 * @entry - the entry to add, if NULL nothing happens.
2434 static inline void mab_set_b_end(struct maple_big_node
*b_node
,
2435 struct ma_state
*mas
,
2441 b_node
->slot
[b_node
->b_end
] = entry
;
2442 if (mt_is_alloc(mas
->tree
))
2443 b_node
->gap
[b_node
->b_end
] = mas_max_gap(mas
);
2444 b_node
->pivot
[b_node
->b_end
++] = mas
->max
;
2448 * mas_set_split_parent() - combine_then_separate helper function. Sets the parent
2449 * of @mas->node to either @left or @right, depending on @slot and @split
2451 * @mas - the maple state with the node that needs a parent
2452 * @left - possible parent 1
2453 * @right - possible parent 2
2454 * @slot - the slot the mas->node was placed
2455 * @split - the split location between @left and @right
2457 static inline void mas_set_split_parent(struct ma_state
*mas
,
2458 struct maple_enode
*left
,
2459 struct maple_enode
*right
,
2460 unsigned char *slot
, unsigned char split
)
2462 if (mas_is_none(mas
))
2465 if ((*slot
) <= split
)
2466 mas_set_parent(mas
, mas
->node
, left
, *slot
);
2468 mas_set_parent(mas
, mas
->node
, right
, (*slot
) - split
- 1);
2474 * mte_mid_split_check() - Check if the next node passes the mid-split
2475 * @**l: Pointer to left encoded maple node.
2476 * @**m: Pointer to middle encoded maple node.
2477 * @**r: Pointer to right encoded maple node.
2479 * @*split: The split location.
2480 * @mid_split: The middle split.
2482 static inline void mte_mid_split_check(struct maple_enode
**l
,
2483 struct maple_enode
**r
,
2484 struct maple_enode
*right
,
2486 unsigned char *split
,
2487 unsigned char mid_split
)
2492 if (slot
< mid_split
)
2501 * mast_set_split_parents() - Helper function to set three nodes parents. Slot
2502 * is taken from @mast->l.
2503 * @mast - the maple subtree state
2504 * @left - the left node
2505 * @right - the right node
2506 * @split - the split location.
2508 static inline void mast_set_split_parents(struct maple_subtree_state
*mast
,
2509 struct maple_enode
*left
,
2510 struct maple_enode
*middle
,
2511 struct maple_enode
*right
,
2512 unsigned char split
,
2513 unsigned char mid_split
)
2516 struct maple_enode
*l
= left
;
2517 struct maple_enode
*r
= right
;
2519 if (mas_is_none(mast
->l
))
2525 slot
= mast
->l
->offset
;
2527 mte_mid_split_check(&l
, &r
, right
, slot
, &split
, mid_split
);
2528 mas_set_split_parent(mast
->l
, l
, r
, &slot
, split
);
2530 mte_mid_split_check(&l
, &r
, right
, slot
, &split
, mid_split
);
2531 mas_set_split_parent(mast
->m
, l
, r
, &slot
, split
);
2533 mte_mid_split_check(&l
, &r
, right
, slot
, &split
, mid_split
);
2534 mas_set_split_parent(mast
->r
, l
, r
, &slot
, split
);
2538 * mas_topiary_node() - Dispose of a singe node
2539 * @mas: The maple state for pushing nodes
2540 * @enode: The encoded maple node
2541 * @in_rcu: If the tree is in rcu mode
2543 * The node will either be RCU freed or pushed back on the maple state.
2545 static inline void mas_topiary_node(struct ma_state
*mas
,
2546 struct maple_enode
*enode
, bool in_rcu
)
2548 struct maple_node
*tmp
;
2550 if (enode
== MAS_NONE
)
2553 tmp
= mte_to_node(enode
);
2554 mte_set_node_dead(enode
);
2558 mas_push_node(mas
, tmp
);
2562 * mas_topiary_replace() - Replace the data with new data, then repair the
2563 * parent links within the new tree. Iterate over the dead sub-tree and collect
2564 * the dead subtrees and topiary the nodes that are no longer of use.
2566 * The new tree will have up to three children with the correct parent. Keep
2567 * track of the new entries as they need to be followed to find the next level
2570 * The old tree will have up to three children with the old parent. Keep track
2571 * of the old entries as they may have more nodes below replaced. Nodes within
2572 * [index, last] are dead subtrees, others need to be freed and followed.
2574 * @mas: The maple state pointing at the new data
2575 * @old_enode: The maple encoded node being replaced
2578 static inline void mas_topiary_replace(struct ma_state
*mas
,
2579 struct maple_enode
*old_enode
)
2581 struct ma_state tmp
[3], tmp_next
[3];
2582 MA_TOPIARY(subtrees
, mas
->tree
);
2586 /* Place data in tree & then mark node as old */
2587 mas_put_in_tree(mas
, old_enode
);
2589 /* Update the parent pointers in the tree */
2592 tmp
[1].node
= MAS_NONE
;
2593 tmp
[2].node
= MAS_NONE
;
2594 while (!mte_is_leaf(tmp
[0].node
)) {
2596 for (i
= 0; i
< 3; i
++) {
2597 if (mas_is_none(&tmp
[i
]))
2601 if (!mas_find_child(&tmp
[i
], &tmp_next
[n
]))
2606 mas_adopt_children(&tmp
[i
], tmp
[i
].node
);
2609 if (MAS_WARN_ON(mas
, n
== 0))
2613 tmp_next
[n
++].node
= MAS_NONE
;
2615 for (i
= 0; i
< 3; i
++)
2616 tmp
[i
] = tmp_next
[i
];
2619 /* Collect the old nodes that need to be discarded */
2620 if (mte_is_leaf(old_enode
))
2621 return mas_free(mas
, old_enode
);
2625 tmp
[0].node
= old_enode
;
2626 tmp
[1].node
= MAS_NONE
;
2627 tmp
[2].node
= MAS_NONE
;
2628 in_rcu
= mt_in_rcu(mas
->tree
);
2631 for (i
= 0; i
< 3; i
++) {
2632 if (mas_is_none(&tmp
[i
]))
2636 if (!mas_find_child(&tmp
[i
], &tmp_next
[n
]))
2639 if ((tmp_next
[n
].min
>= tmp_next
->index
) &&
2640 (tmp_next
[n
].max
<= tmp_next
->last
)) {
2641 mat_add(&subtrees
, tmp_next
[n
].node
);
2642 tmp_next
[n
].node
= MAS_NONE
;
2649 if (MAS_WARN_ON(mas
, n
== 0))
2653 tmp_next
[n
++].node
= MAS_NONE
;
2655 for (i
= 0; i
< 3; i
++) {
2656 mas_topiary_node(mas
, tmp
[i
].node
, in_rcu
);
2657 tmp
[i
] = tmp_next
[i
];
2659 } while (!mte_is_leaf(tmp
[0].node
));
2661 for (i
= 0; i
< 3; i
++)
2662 mas_topiary_node(mas
, tmp
[i
].node
, in_rcu
);
2664 mas_mat_destroy(mas
, &subtrees
);
2668 * mas_wmb_replace() - Write memory barrier and replace
2669 * @mas: The maple state
2670 * @old: The old maple encoded node that is being replaced.
2672 * Updates gap as necessary.
2674 static inline void mas_wmb_replace(struct ma_state
*mas
,
2675 struct maple_enode
*old_enode
)
2677 /* Insert the new data in the tree */
2678 mas_topiary_replace(mas
, old_enode
);
2680 if (mte_is_leaf(mas
->node
))
2683 mas_update_gap(mas
);
2687 * mast_cp_to_nodes() - Copy data out to nodes.
2688 * @mast: The maple subtree state
2689 * @left: The left encoded maple node
2690 * @middle: The middle encoded maple node
2691 * @right: The right encoded maple node
2692 * @split: The location to split between left and (middle ? middle : right)
2693 * @mid_split: The location to split between middle and right.
2695 static inline void mast_cp_to_nodes(struct maple_subtree_state
*mast
,
2696 struct maple_enode
*left
, struct maple_enode
*middle
,
2697 struct maple_enode
*right
, unsigned char split
, unsigned char mid_split
)
2699 bool new_lmax
= true;
2701 mast
->l
->node
= mte_node_or_none(left
);
2702 mast
->m
->node
= mte_node_or_none(middle
);
2703 mast
->r
->node
= mte_node_or_none(right
);
2705 mast
->l
->min
= mast
->orig_l
->min
;
2706 if (split
== mast
->bn
->b_end
) {
2707 mast
->l
->max
= mast
->orig_r
->max
;
2711 mab_mas_cp(mast
->bn
, 0, split
, mast
->l
, new_lmax
);
2714 mab_mas_cp(mast
->bn
, 1 + split
, mid_split
, mast
->m
, true);
2715 mast
->m
->min
= mast
->bn
->pivot
[split
] + 1;
2719 mast
->r
->max
= mast
->orig_r
->max
;
2721 mab_mas_cp(mast
->bn
, 1 + split
, mast
->bn
->b_end
, mast
->r
, false);
2722 mast
->r
->min
= mast
->bn
->pivot
[split
] + 1;
2727 * mast_combine_cp_left - Copy in the original left side of the tree into the
2728 * combined data set in the maple subtree state big node.
2729 * @mast: The maple subtree state
2731 static inline void mast_combine_cp_left(struct maple_subtree_state
*mast
)
2733 unsigned char l_slot
= mast
->orig_l
->offset
;
2738 mas_mab_cp(mast
->orig_l
, 0, l_slot
- 1, mast
->bn
, 0);
2742 * mast_combine_cp_right: Copy in the original right side of the tree into the
2743 * combined data set in the maple subtree state big node.
2744 * @mast: The maple subtree state
2746 static inline void mast_combine_cp_right(struct maple_subtree_state
*mast
)
2748 if (mast
->bn
->pivot
[mast
->bn
->b_end
- 1] >= mast
->orig_r
->max
)
2751 mas_mab_cp(mast
->orig_r
, mast
->orig_r
->offset
+ 1,
2752 mt_slot_count(mast
->orig_r
->node
), mast
->bn
,
2754 mast
->orig_r
->last
= mast
->orig_r
->max
;
2758 * mast_sufficient: Check if the maple subtree state has enough data in the big
2759 * node to create at least one sufficient node
2760 * @mast: the maple subtree state
2762 static inline bool mast_sufficient(struct maple_subtree_state
*mast
)
2764 if (mast
->bn
->b_end
> mt_min_slot_count(mast
->orig_l
->node
))
2771 * mast_overflow: Check if there is too much data in the subtree state for a
2773 * @mast: The maple subtree state
2775 static inline bool mast_overflow(struct maple_subtree_state
*mast
)
2777 if (mast
->bn
->b_end
>= mt_slot_count(mast
->orig_l
->node
))
2783 static inline void *mtree_range_walk(struct ma_state
*mas
)
2785 unsigned long *pivots
;
2786 unsigned char offset
;
2787 struct maple_node
*node
;
2788 struct maple_enode
*next
, *last
;
2789 enum maple_type type
;
2792 unsigned long max
, min
;
2793 unsigned long prev_max
, prev_min
;
2801 node
= mte_to_node(next
);
2802 type
= mte_node_type(next
);
2803 pivots
= ma_pivots(node
, type
);
2804 end
= ma_data_end(node
, type
, pivots
, max
);
2805 if (unlikely(ma_dead_node(node
)))
2808 if (pivots
[offset
] >= mas
->index
) {
2811 max
= pivots
[offset
];
2817 } while ((offset
< end
) && (pivots
[offset
] < mas
->index
));
2820 min
= pivots
[offset
- 1] + 1;
2822 if (likely(offset
< end
&& pivots
[offset
]))
2823 max
= pivots
[offset
];
2826 slots
= ma_slots(node
, type
);
2827 next
= mt_slot(mas
->tree
, slots
, offset
);
2828 if (unlikely(ma_dead_node(node
)))
2830 } while (!ma_is_leaf(type
));
2832 mas
->offset
= offset
;
2835 mas
->min
= prev_min
;
2836 mas
->max
= prev_max
;
2838 return (void *)next
;
2846 * mas_spanning_rebalance() - Rebalance across two nodes which may not be peers.
2847 * @mas: The starting maple state
2848 * @mast: The maple_subtree_state, keeps track of 4 maple states.
2849 * @count: The estimated count of iterations needed.
2851 * Follow the tree upwards from @l_mas and @r_mas for @count, or until the root
2852 * is hit. First @b_node is split into two entries which are inserted into the
2853 * next iteration of the loop. @b_node is returned populated with the final
2854 * iteration. @mas is used to obtain allocations. orig_l_mas keeps track of the
2855 * nodes that will remain active by using orig_l_mas->index and orig_l_mas->last
2856 * to account of what has been copied into the new sub-tree. The update of
2857 * orig_l_mas->last is used in mas_consume to find the slots that will need to
2858 * be either freed or destroyed. orig_l_mas->depth keeps track of the height of
2859 * the new sub-tree in case the sub-tree becomes the full tree.
2861 * Return: the number of elements in b_node during the last loop.
2863 static int mas_spanning_rebalance(struct ma_state
*mas
,
2864 struct maple_subtree_state
*mast
, unsigned char count
)
2866 unsigned char split
, mid_split
;
2867 unsigned char slot
= 0;
2868 struct maple_enode
*left
= NULL
, *middle
= NULL
, *right
= NULL
;
2869 struct maple_enode
*old_enode
;
2871 MA_STATE(l_mas
, mas
->tree
, mas
->index
, mas
->index
);
2872 MA_STATE(r_mas
, mas
->tree
, mas
->index
, mas
->last
);
2873 MA_STATE(m_mas
, mas
->tree
, mas
->index
, mas
->index
);
2876 * The tree needs to be rebalanced and leaves need to be kept at the same level.
2877 * Rebalancing is done by use of the ``struct maple_topiary``.
2882 l_mas
.node
= r_mas
.node
= m_mas
.node
= MAS_NONE
;
2884 /* Check if this is not root and has sufficient data. */
2885 if (((mast
->orig_l
->min
!= 0) || (mast
->orig_r
->max
!= ULONG_MAX
)) &&
2886 unlikely(mast
->bn
->b_end
<= mt_min_slots
[mast
->bn
->type
]))
2887 mast_spanning_rebalance(mast
);
2892 * Each level of the tree is examined and balanced, pushing data to the left or
2893 * right, or rebalancing against left or right nodes is employed to avoid
2894 * rippling up the tree to limit the amount of churn. Once a new sub-section of
2895 * the tree is created, there may be a mix of new and old nodes. The old nodes
2896 * will have the incorrect parent pointers and currently be in two trees: the
2897 * original tree and the partially new tree. To remedy the parent pointers in
2898 * the old tree, the new data is swapped into the active tree and a walk down
2899 * the tree is performed and the parent pointers are updated.
2900 * See mas_topiary_replace() for more information.
2904 mast
->bn
->type
= mte_node_type(mast
->orig_l
->node
);
2905 split
= mas_mab_to_node(mas
, mast
->bn
, &left
, &right
, &middle
,
2906 &mid_split
, mast
->orig_l
->min
);
2907 mast_set_split_parents(mast
, left
, middle
, right
, split
,
2909 mast_cp_to_nodes(mast
, left
, middle
, right
, split
, mid_split
);
2912 * Copy data from next level in the tree to mast->bn from next
2915 memset(mast
->bn
, 0, sizeof(struct maple_big_node
));
2916 mast
->bn
->type
= mte_node_type(left
);
2919 /* Root already stored in l->node. */
2920 if (mas_is_root_limits(mast
->l
))
2924 mast_combine_cp_left(mast
);
2925 l_mas
.offset
= mast
->bn
->b_end
;
2926 mab_set_b_end(mast
->bn
, &l_mas
, left
);
2927 mab_set_b_end(mast
->bn
, &m_mas
, middle
);
2928 mab_set_b_end(mast
->bn
, &r_mas
, right
);
2930 /* Copy anything necessary out of the right node. */
2931 mast_combine_cp_right(mast
);
2932 mast
->orig_l
->last
= mast
->orig_l
->max
;
2934 if (mast_sufficient(mast
))
2937 if (mast_overflow(mast
))
2940 /* May be a new root stored in mast->bn */
2941 if (mas_is_root_limits(mast
->orig_l
))
2944 mast_spanning_rebalance(mast
);
2946 /* rebalancing from other nodes may require another loop. */
2951 l_mas
.node
= mt_mk_node(ma_mnode_ptr(mas_pop_node(mas
)),
2952 mte_node_type(mast
->orig_l
->node
));
2954 mab_mas_cp(mast
->bn
, 0, mt_slots
[mast
->bn
->type
] - 1, &l_mas
, true);
2955 mas_set_parent(mas
, left
, l_mas
.node
, slot
);
2957 mas_set_parent(mas
, middle
, l_mas
.node
, ++slot
);
2960 mas_set_parent(mas
, right
, l_mas
.node
, ++slot
);
2962 if (mas_is_root_limits(mast
->l
)) {
2964 mas_mn(mast
->l
)->parent
= ma_parent_ptr(mas_tree_parent(mas
));
2965 while (!mte_is_root(mast
->orig_l
->node
))
2968 mas_mn(&l_mas
)->parent
= mas_mn(mast
->orig_l
)->parent
;
2971 old_enode
= mast
->orig_l
->node
;
2972 mas
->depth
= l_mas
.depth
;
2973 mas
->node
= l_mas
.node
;
2974 mas
->min
= l_mas
.min
;
2975 mas
->max
= l_mas
.max
;
2976 mas
->offset
= l_mas
.offset
;
2977 mas_wmb_replace(mas
, old_enode
);
2978 mtree_range_walk(mas
);
2979 return mast
->bn
->b_end
;
2983 * mas_rebalance() - Rebalance a given node.
2984 * @mas: The maple state
2985 * @b_node: The big maple node.
2987 * Rebalance two nodes into a single node or two new nodes that are sufficient.
2988 * Continue upwards until tree is sufficient.
2990 * Return: the number of elements in b_node during the last loop.
2992 static inline int mas_rebalance(struct ma_state
*mas
,
2993 struct maple_big_node
*b_node
)
2995 char empty_count
= mas_mt_height(mas
);
2996 struct maple_subtree_state mast
;
2997 unsigned char shift
, b_end
= ++b_node
->b_end
;
2999 MA_STATE(l_mas
, mas
->tree
, mas
->index
, mas
->last
);
3000 MA_STATE(r_mas
, mas
->tree
, mas
->index
, mas
->last
);
3002 trace_ma_op(__func__
, mas
);
3005 * Rebalancing occurs if a node is insufficient. Data is rebalanced
3006 * against the node to the right if it exists, otherwise the node to the
3007 * left of this node is rebalanced against this node. If rebalancing
3008 * causes just one node to be produced instead of two, then the parent
3009 * is also examined and rebalanced if it is insufficient. Every level
3010 * tries to combine the data in the same way. If one node contains the
3011 * entire range of the tree, then that node is used as a new root node.
3013 mas_node_count(mas
, empty_count
* 2 - 1);
3014 if (mas_is_err(mas
))
3017 mast
.orig_l
= &l_mas
;
3018 mast
.orig_r
= &r_mas
;
3020 mast
.bn
->type
= mte_node_type(mas
->node
);
3022 l_mas
= r_mas
= *mas
;
3024 if (mas_next_sibling(&r_mas
)) {
3025 mas_mab_cp(&r_mas
, 0, mt_slot_count(r_mas
.node
), b_node
, b_end
);
3026 r_mas
.last
= r_mas
.index
= r_mas
.max
;
3028 mas_prev_sibling(&l_mas
);
3029 shift
= mas_data_end(&l_mas
) + 1;
3030 mab_shift_right(b_node
, shift
);
3031 mas
->offset
+= shift
;
3032 mas_mab_cp(&l_mas
, 0, shift
- 1, b_node
, 0);
3033 b_node
->b_end
= shift
+ b_end
;
3034 l_mas
.index
= l_mas
.last
= l_mas
.min
;
3037 return mas_spanning_rebalance(mas
, &mast
, empty_count
);
3041 * mas_destroy_rebalance() - Rebalance left-most node while destroying the maple
3043 * @mas: The maple state
3044 * @end: The end of the left-most node.
3046 * During a mass-insert event (such as forking), it may be necessary to
3047 * rebalance the left-most node when it is not sufficient.
3049 static inline void mas_destroy_rebalance(struct ma_state
*mas
, unsigned char end
)
3051 enum maple_type mt
= mte_node_type(mas
->node
);
3052 struct maple_node reuse
, *newnode
, *parent
, *new_left
, *left
, *node
;
3053 struct maple_enode
*eparent
, *old_eparent
;
3054 unsigned char offset
, tmp
, split
= mt_slots
[mt
] / 2;
3055 void __rcu
**l_slots
, **slots
;
3056 unsigned long *l_pivs
, *pivs
, gap
;
3057 bool in_rcu
= mt_in_rcu(mas
->tree
);
3059 MA_STATE(l_mas
, mas
->tree
, mas
->index
, mas
->last
);
3062 mas_prev_sibling(&l_mas
);
3066 /* Allocate for both left and right as well as parent. */
3067 mas_node_count(mas
, 3);
3068 if (mas_is_err(mas
))
3071 newnode
= mas_pop_node(mas
);
3077 newnode
->parent
= node
->parent
;
3078 slots
= ma_slots(newnode
, mt
);
3079 pivs
= ma_pivots(newnode
, mt
);
3080 left
= mas_mn(&l_mas
);
3081 l_slots
= ma_slots(left
, mt
);
3082 l_pivs
= ma_pivots(left
, mt
);
3083 if (!l_slots
[split
])
3085 tmp
= mas_data_end(&l_mas
) - split
;
3087 memcpy(slots
, l_slots
+ split
+ 1, sizeof(void *) * tmp
);
3088 memcpy(pivs
, l_pivs
+ split
+ 1, sizeof(unsigned long) * tmp
);
3089 pivs
[tmp
] = l_mas
.max
;
3090 memcpy(slots
+ tmp
, ma_slots(node
, mt
), sizeof(void *) * end
);
3091 memcpy(pivs
+ tmp
, ma_pivots(node
, mt
), sizeof(unsigned long) * end
);
3093 l_mas
.max
= l_pivs
[split
];
3094 mas
->min
= l_mas
.max
+ 1;
3095 old_eparent
= mt_mk_node(mte_parent(l_mas
.node
),
3096 mas_parent_type(&l_mas
, l_mas
.node
));
3099 unsigned char max_p
= mt_pivots
[mt
];
3100 unsigned char max_s
= mt_slots
[mt
];
3103 memset(pivs
+ tmp
, 0,
3104 sizeof(unsigned long) * (max_p
- tmp
));
3106 if (tmp
< mt_slots
[mt
])
3107 memset(slots
+ tmp
, 0, sizeof(void *) * (max_s
- tmp
));
3109 memcpy(node
, newnode
, sizeof(struct maple_node
));
3110 ma_set_meta(node
, mt
, 0, tmp
- 1);
3111 mte_set_pivot(old_eparent
, mte_parent_slot(l_mas
.node
),
3114 /* Remove data from l_pivs. */
3116 memset(l_pivs
+ tmp
, 0, sizeof(unsigned long) * (max_p
- tmp
));
3117 memset(l_slots
+ tmp
, 0, sizeof(void *) * (max_s
- tmp
));
3118 ma_set_meta(left
, mt
, 0, split
);
3119 eparent
= old_eparent
;
3124 /* RCU requires replacing both l_mas, mas, and parent. */
3125 mas
->node
= mt_mk_node(newnode
, mt
);
3126 ma_set_meta(newnode
, mt
, 0, tmp
);
3128 new_left
= mas_pop_node(mas
);
3129 new_left
->parent
= left
->parent
;
3130 mt
= mte_node_type(l_mas
.node
);
3131 slots
= ma_slots(new_left
, mt
);
3132 pivs
= ma_pivots(new_left
, mt
);
3133 memcpy(slots
, l_slots
, sizeof(void *) * split
);
3134 memcpy(pivs
, l_pivs
, sizeof(unsigned long) * split
);
3135 ma_set_meta(new_left
, mt
, 0, split
);
3136 l_mas
.node
= mt_mk_node(new_left
, mt
);
3138 /* replace parent. */
3139 offset
= mte_parent_slot(mas
->node
);
3140 mt
= mas_parent_type(&l_mas
, l_mas
.node
);
3141 parent
= mas_pop_node(mas
);
3142 slots
= ma_slots(parent
, mt
);
3143 pivs
= ma_pivots(parent
, mt
);
3144 memcpy(parent
, mte_to_node(old_eparent
), sizeof(struct maple_node
));
3145 rcu_assign_pointer(slots
[offset
], mas
->node
);
3146 rcu_assign_pointer(slots
[offset
- 1], l_mas
.node
);
3147 pivs
[offset
- 1] = l_mas
.max
;
3148 eparent
= mt_mk_node(parent
, mt
);
3150 gap
= mas_leaf_max_gap(mas
);
3151 mte_set_gap(eparent
, mte_parent_slot(mas
->node
), gap
);
3152 gap
= mas_leaf_max_gap(&l_mas
);
3153 mte_set_gap(eparent
, mte_parent_slot(l_mas
.node
), gap
);
3157 mas_replace_node(mas
, old_eparent
);
3158 mas_adopt_children(mas
, mas
->node
);
3161 mas_update_gap(mas
);
3165 * mas_split_final_node() - Split the final node in a subtree operation.
3166 * @mast: the maple subtree state
3167 * @mas: The maple state
3168 * @height: The height of the tree in case it's a new root.
3170 static inline bool mas_split_final_node(struct maple_subtree_state
*mast
,
3171 struct ma_state
*mas
, int height
)
3173 struct maple_enode
*ancestor
;
3175 if (mte_is_root(mas
->node
)) {
3176 if (mt_is_alloc(mas
->tree
))
3177 mast
->bn
->type
= maple_arange_64
;
3179 mast
->bn
->type
= maple_range_64
;
3180 mas
->depth
= height
;
3183 * Only a single node is used here, could be root.
3184 * The Big_node data should just fit in a single node.
3186 ancestor
= mas_new_ma_node(mas
, mast
->bn
);
3187 mas_set_parent(mas
, mast
->l
->node
, ancestor
, mast
->l
->offset
);
3188 mas_set_parent(mas
, mast
->r
->node
, ancestor
, mast
->r
->offset
);
3189 mte_to_node(ancestor
)->parent
= mas_mn(mas
)->parent
;
3191 mast
->l
->node
= ancestor
;
3192 mab_mas_cp(mast
->bn
, 0, mt_slots
[mast
->bn
->type
] - 1, mast
->l
, true);
3193 mas
->offset
= mast
->bn
->b_end
- 1;
3198 * mast_fill_bnode() - Copy data into the big node in the subtree state
3199 * @mast: The maple subtree state
3200 * @mas: the maple state
3201 * @skip: The number of entries to skip for new nodes insertion.
3203 static inline void mast_fill_bnode(struct maple_subtree_state
*mast
,
3204 struct ma_state
*mas
,
3208 unsigned char split
;
3210 memset(mast
->bn
->gap
, 0, sizeof(unsigned long) * ARRAY_SIZE(mast
->bn
->gap
));
3211 memset(mast
->bn
->slot
, 0, sizeof(unsigned long) * ARRAY_SIZE(mast
->bn
->slot
));
3212 memset(mast
->bn
->pivot
, 0, sizeof(unsigned long) * ARRAY_SIZE(mast
->bn
->pivot
));
3213 mast
->bn
->b_end
= 0;
3215 if (mte_is_root(mas
->node
)) {
3219 mas
->offset
= mte_parent_slot(mas
->node
);
3222 if (cp
&& mast
->l
->offset
)
3223 mas_mab_cp(mas
, 0, mast
->l
->offset
- 1, mast
->bn
, 0);
3225 split
= mast
->bn
->b_end
;
3226 mab_set_b_end(mast
->bn
, mast
->l
, mast
->l
->node
);
3227 mast
->r
->offset
= mast
->bn
->b_end
;
3228 mab_set_b_end(mast
->bn
, mast
->r
, mast
->r
->node
);
3229 if (mast
->bn
->pivot
[mast
->bn
->b_end
- 1] == mas
->max
)
3233 mas_mab_cp(mas
, split
+ skip
, mt_slot_count(mas
->node
) - 1,
3234 mast
->bn
, mast
->bn
->b_end
);
3237 mast
->bn
->type
= mte_node_type(mas
->node
);
3241 * mast_split_data() - Split the data in the subtree state big node into regular
3243 * @mast: The maple subtree state
3244 * @mas: The maple state
3245 * @split: The location to split the big node
3247 static inline void mast_split_data(struct maple_subtree_state
*mast
,
3248 struct ma_state
*mas
, unsigned char split
)
3250 unsigned char p_slot
;
3252 mab_mas_cp(mast
->bn
, 0, split
, mast
->l
, true);
3253 mte_set_pivot(mast
->r
->node
, 0, mast
->r
->max
);
3254 mab_mas_cp(mast
->bn
, split
+ 1, mast
->bn
->b_end
, mast
->r
, false);
3255 mast
->l
->offset
= mte_parent_slot(mas
->node
);
3256 mast
->l
->max
= mast
->bn
->pivot
[split
];
3257 mast
->r
->min
= mast
->l
->max
+ 1;
3258 if (mte_is_leaf(mas
->node
))
3261 p_slot
= mast
->orig_l
->offset
;
3262 mas_set_split_parent(mast
->orig_l
, mast
->l
->node
, mast
->r
->node
,
3264 mas_set_split_parent(mast
->orig_r
, mast
->l
->node
, mast
->r
->node
,
3269 * mas_push_data() - Instead of splitting a node, it is beneficial to push the
3270 * data to the right or left node if there is room.
3271 * @mas: The maple state
3272 * @height: The current height of the maple state
3273 * @mast: The maple subtree state
3274 * @left: Push left or not.
3276 * Keeping the height of the tree low means faster lookups.
3278 * Return: True if pushed, false otherwise.
3280 static inline bool mas_push_data(struct ma_state
*mas
, int height
,
3281 struct maple_subtree_state
*mast
, bool left
)
3283 unsigned char slot_total
= mast
->bn
->b_end
;
3284 unsigned char end
, space
, split
;
3286 MA_STATE(tmp_mas
, mas
->tree
, mas
->index
, mas
->last
);
3288 tmp_mas
.depth
= mast
->l
->depth
;
3290 if (left
&& !mas_prev_sibling(&tmp_mas
))
3292 else if (!left
&& !mas_next_sibling(&tmp_mas
))
3295 end
= mas_data_end(&tmp_mas
);
3297 space
= 2 * mt_slot_count(mas
->node
) - 2;
3298 /* -2 instead of -1 to ensure there isn't a triple split */
3299 if (ma_is_leaf(mast
->bn
->type
))
3302 if (mas
->max
== ULONG_MAX
)
3305 if (slot_total
>= space
)
3308 /* Get the data; Fill mast->bn */
3311 mab_shift_right(mast
->bn
, end
+ 1);
3312 mas_mab_cp(&tmp_mas
, 0, end
, mast
->bn
, 0);
3313 mast
->bn
->b_end
= slot_total
+ 1;
3315 mas_mab_cp(&tmp_mas
, 0, end
, mast
->bn
, mast
->bn
->b_end
);
3318 /* Configure mast for splitting of mast->bn */
3319 split
= mt_slots
[mast
->bn
->type
] - 2;
3321 /* Switch mas to prev node */
3323 /* Start using mast->l for the left side. */
3324 tmp_mas
.node
= mast
->l
->node
;
3327 tmp_mas
.node
= mast
->r
->node
;
3329 split
= slot_total
- split
;
3331 split
= mab_no_null_split(mast
->bn
, split
, mt_slots
[mast
->bn
->type
]);
3332 /* Update parent slot for split calculation. */
3334 mast
->orig_l
->offset
+= end
+ 1;
3336 mast_split_data(mast
, mas
, split
);
3337 mast_fill_bnode(mast
, mas
, 2);
3338 mas_split_final_node(mast
, mas
, height
+ 1);
3343 * mas_split() - Split data that is too big for one node into two.
3344 * @mas: The maple state
3345 * @b_node: The maple big node
3346 * Return: 1 on success, 0 on failure.
3348 static int mas_split(struct ma_state
*mas
, struct maple_big_node
*b_node
)
3350 struct maple_subtree_state mast
;
3352 unsigned char mid_split
, split
= 0;
3353 struct maple_enode
*old
;
3356 * Splitting is handled differently from any other B-tree; the Maple
3357 * Tree splits upwards. Splitting up means that the split operation
3358 * occurs when the walk of the tree hits the leaves and not on the way
3359 * down. The reason for splitting up is that it is impossible to know
3360 * how much space will be needed until the leaf is (or leaves are)
3361 * reached. Since overwriting data is allowed and a range could
3362 * overwrite more than one range or result in changing one entry into 3
3363 * entries, it is impossible to know if a split is required until the
3366 * Splitting is a balancing act between keeping allocations to a minimum
3367 * and avoiding a 'jitter' event where a tree is expanded to make room
3368 * for an entry followed by a contraction when the entry is removed. To
3369 * accomplish the balance, there are empty slots remaining in both left
3370 * and right nodes after a split.
3372 MA_STATE(l_mas
, mas
->tree
, mas
->index
, mas
->last
);
3373 MA_STATE(r_mas
, mas
->tree
, mas
->index
, mas
->last
);
3374 MA_STATE(prev_l_mas
, mas
->tree
, mas
->index
, mas
->last
);
3375 MA_STATE(prev_r_mas
, mas
->tree
, mas
->index
, mas
->last
);
3377 trace_ma_op(__func__
, mas
);
3378 mas
->depth
= mas_mt_height(mas
);
3379 /* Allocation failures will happen early. */
3380 mas_node_count(mas
, 1 + mas
->depth
* 2);
3381 if (mas_is_err(mas
))
3386 mast
.orig_l
= &prev_l_mas
;
3387 mast
.orig_r
= &prev_r_mas
;
3390 while (height
++ <= mas
->depth
) {
3391 if (mt_slots
[b_node
->type
] > b_node
->b_end
) {
3392 mas_split_final_node(&mast
, mas
, height
);
3396 l_mas
= r_mas
= *mas
;
3397 l_mas
.node
= mas_new_ma_node(mas
, b_node
);
3398 r_mas
.node
= mas_new_ma_node(mas
, b_node
);
3400 * Another way that 'jitter' is avoided is to terminate a split up early if the
3401 * left or right node has space to spare. This is referred to as "pushing left"
3402 * or "pushing right" and is similar to the B* tree, except the nodes left or
3403 * right can rarely be reused due to RCU, but the ripple upwards is halted which
3404 * is a significant savings.
3406 /* Try to push left. */
3407 if (mas_push_data(mas
, height
, &mast
, true))
3410 /* Try to push right. */
3411 if (mas_push_data(mas
, height
, &mast
, false))
3414 split
= mab_calc_split(mas
, b_node
, &mid_split
, prev_l_mas
.min
);
3415 mast_split_data(&mast
, mas
, split
);
3417 * Usually correct, mab_mas_cp in the above call overwrites
3420 mast
.r
->max
= mas
->max
;
3421 mast_fill_bnode(&mast
, mas
, 1);
3422 prev_l_mas
= *mast
.l
;
3423 prev_r_mas
= *mast
.r
;
3426 /* Set the original node as dead */
3428 mas
->node
= l_mas
.node
;
3429 mas_wmb_replace(mas
, old
);
3430 mtree_range_walk(mas
);
3435 * mas_reuse_node() - Reuse the node to store the data.
3436 * @wr_mas: The maple write state
3437 * @bn: The maple big node
3438 * @end: The end of the data.
3440 * Will always return false in RCU mode.
3442 * Return: True if node was reused, false otherwise.
3444 static inline bool mas_reuse_node(struct ma_wr_state
*wr_mas
,
3445 struct maple_big_node
*bn
, unsigned char end
)
3447 /* Need to be rcu safe. */
3448 if (mt_in_rcu(wr_mas
->mas
->tree
))
3451 if (end
> bn
->b_end
) {
3452 int clear
= mt_slots
[wr_mas
->type
] - bn
->b_end
;
3454 memset(wr_mas
->slots
+ bn
->b_end
, 0, sizeof(void *) * clear
--);
3455 memset(wr_mas
->pivots
+ bn
->b_end
, 0, sizeof(void *) * clear
);
3457 mab_mas_cp(bn
, 0, bn
->b_end
, wr_mas
->mas
, false);
3462 * mas_commit_b_node() - Commit the big node into the tree.
3463 * @wr_mas: The maple write state
3464 * @b_node: The maple big node
3465 * @end: The end of the data.
3467 static noinline_for_kasan
int mas_commit_b_node(struct ma_wr_state
*wr_mas
,
3468 struct maple_big_node
*b_node
, unsigned char end
)
3470 struct maple_node
*node
;
3471 struct maple_enode
*old_enode
;
3472 unsigned char b_end
= b_node
->b_end
;
3473 enum maple_type b_type
= b_node
->type
;
3475 old_enode
= wr_mas
->mas
->node
;
3476 if ((b_end
< mt_min_slots
[b_type
]) &&
3477 (!mte_is_root(old_enode
)) &&
3478 (mas_mt_height(wr_mas
->mas
) > 1))
3479 return mas_rebalance(wr_mas
->mas
, b_node
);
3481 if (b_end
>= mt_slots
[b_type
])
3482 return mas_split(wr_mas
->mas
, b_node
);
3484 if (mas_reuse_node(wr_mas
, b_node
, end
))
3487 mas_node_count(wr_mas
->mas
, 1);
3488 if (mas_is_err(wr_mas
->mas
))
3491 node
= mas_pop_node(wr_mas
->mas
);
3492 node
->parent
= mas_mn(wr_mas
->mas
)->parent
;
3493 wr_mas
->mas
->node
= mt_mk_node(node
, b_type
);
3494 mab_mas_cp(b_node
, 0, b_end
, wr_mas
->mas
, false);
3495 mas_replace_node(wr_mas
->mas
, old_enode
);
3497 mas_update_gap(wr_mas
->mas
);
3502 * mas_root_expand() - Expand a root to a node
3503 * @mas: The maple state
3504 * @entry: The entry to store into the tree
3506 static inline int mas_root_expand(struct ma_state
*mas
, void *entry
)
3508 void *contents
= mas_root_locked(mas
);
3509 enum maple_type type
= maple_leaf_64
;
3510 struct maple_node
*node
;
3512 unsigned long *pivots
;
3515 mas_node_count(mas
, 1);
3516 if (unlikely(mas_is_err(mas
)))
3519 node
= mas_pop_node(mas
);
3520 pivots
= ma_pivots(node
, type
);
3521 slots
= ma_slots(node
, type
);
3522 node
->parent
= ma_parent_ptr(mas_tree_parent(mas
));
3523 mas
->node
= mt_mk_node(node
, type
);
3527 rcu_assign_pointer(slots
[slot
], contents
);
3528 if (likely(mas
->index
> 1))
3531 pivots
[slot
++] = mas
->index
- 1;
3534 rcu_assign_pointer(slots
[slot
], entry
);
3536 pivots
[slot
] = mas
->last
;
3537 if (mas
->last
!= ULONG_MAX
)
3538 pivots
[++slot
] = ULONG_MAX
;
3541 mas_set_height(mas
);
3542 ma_set_meta(node
, maple_leaf_64
, 0, slot
);
3543 /* swap the new root into the tree */
3544 rcu_assign_pointer(mas
->tree
->ma_root
, mte_mk_root(mas
->node
));
3548 static inline void mas_store_root(struct ma_state
*mas
, void *entry
)
3550 if (likely((mas
->last
!= 0) || (mas
->index
!= 0)))
3551 mas_root_expand(mas
, entry
);
3552 else if (((unsigned long) (entry
) & 3) == 2)
3553 mas_root_expand(mas
, entry
);
3555 rcu_assign_pointer(mas
->tree
->ma_root
, entry
);
3556 mas
->node
= MAS_START
;
3561 * mas_is_span_wr() - Check if the write needs to be treated as a write that
3563 * @mas: The maple state
3564 * @piv: The pivot value being written
3565 * @type: The maple node type
3566 * @entry: The data to write
3568 * Spanning writes are writes that start in one node and end in another OR if
3569 * the write of a %NULL will cause the node to end with a %NULL.
3571 * Return: True if this is a spanning write, false otherwise.
3573 static bool mas_is_span_wr(struct ma_wr_state
*wr_mas
)
3575 unsigned long max
= wr_mas
->r_max
;
3576 unsigned long last
= wr_mas
->mas
->last
;
3577 enum maple_type type
= wr_mas
->type
;
3578 void *entry
= wr_mas
->entry
;
3580 /* Contained in this pivot, fast path */
3584 if (ma_is_leaf(type
)) {
3585 max
= wr_mas
->mas
->max
;
3592 * The last entry of leaf node cannot be NULL unless it is the
3593 * rightmost node (writing ULONG_MAX), otherwise it spans slots.
3595 if (entry
|| last
== ULONG_MAX
)
3599 trace_ma_write(__func__
, wr_mas
->mas
, wr_mas
->r_max
, entry
);
3603 static inline void mas_wr_walk_descend(struct ma_wr_state
*wr_mas
)
3605 wr_mas
->type
= mte_node_type(wr_mas
->mas
->node
);
3606 mas_wr_node_walk(wr_mas
);
3607 wr_mas
->slots
= ma_slots(wr_mas
->node
, wr_mas
->type
);
3610 static inline void mas_wr_walk_traverse(struct ma_wr_state
*wr_mas
)
3612 wr_mas
->mas
->max
= wr_mas
->r_max
;
3613 wr_mas
->mas
->min
= wr_mas
->r_min
;
3614 wr_mas
->mas
->node
= wr_mas
->content
;
3615 wr_mas
->mas
->offset
= 0;
3616 wr_mas
->mas
->depth
++;
3619 * mas_wr_walk() - Walk the tree for a write.
3620 * @wr_mas: The maple write state
3622 * Uses mas_slot_locked() and does not need to worry about dead nodes.
3624 * Return: True if it's contained in a node, false on spanning write.
3626 static bool mas_wr_walk(struct ma_wr_state
*wr_mas
)
3628 struct ma_state
*mas
= wr_mas
->mas
;
3631 mas_wr_walk_descend(wr_mas
);
3632 if (unlikely(mas_is_span_wr(wr_mas
)))
3635 wr_mas
->content
= mas_slot_locked(mas
, wr_mas
->slots
,
3637 if (ma_is_leaf(wr_mas
->type
))
3640 mas_wr_walk_traverse(wr_mas
);
3646 static bool mas_wr_walk_index(struct ma_wr_state
*wr_mas
)
3648 struct ma_state
*mas
= wr_mas
->mas
;
3651 mas_wr_walk_descend(wr_mas
);
3652 wr_mas
->content
= mas_slot_locked(mas
, wr_mas
->slots
,
3654 if (ma_is_leaf(wr_mas
->type
))
3656 mas_wr_walk_traverse(wr_mas
);
3662 * mas_extend_spanning_null() - Extend a store of a %NULL to include surrounding %NULLs.
3663 * @l_wr_mas: The left maple write state
3664 * @r_wr_mas: The right maple write state
3666 static inline void mas_extend_spanning_null(struct ma_wr_state
*l_wr_mas
,
3667 struct ma_wr_state
*r_wr_mas
)
3669 struct ma_state
*r_mas
= r_wr_mas
->mas
;
3670 struct ma_state
*l_mas
= l_wr_mas
->mas
;
3671 unsigned char l_slot
;
3673 l_slot
= l_mas
->offset
;
3674 if (!l_wr_mas
->content
)
3675 l_mas
->index
= l_wr_mas
->r_min
;
3677 if ((l_mas
->index
== l_wr_mas
->r_min
) &&
3679 !mas_slot_locked(l_mas
, l_wr_mas
->slots
, l_slot
- 1))) {
3681 l_mas
->index
= l_wr_mas
->pivots
[l_slot
- 2] + 1;
3683 l_mas
->index
= l_mas
->min
;
3685 l_mas
->offset
= l_slot
- 1;
3688 if (!r_wr_mas
->content
) {
3689 if (r_mas
->last
< r_wr_mas
->r_max
)
3690 r_mas
->last
= r_wr_mas
->r_max
;
3692 } else if ((r_mas
->last
== r_wr_mas
->r_max
) &&
3693 (r_mas
->last
< r_mas
->max
) &&
3694 !mas_slot_locked(r_mas
, r_wr_mas
->slots
, r_mas
->offset
+ 1)) {
3695 r_mas
->last
= mas_safe_pivot(r_mas
, r_wr_mas
->pivots
,
3696 r_wr_mas
->type
, r_mas
->offset
+ 1);
3701 static inline void *mas_state_walk(struct ma_state
*mas
)
3705 entry
= mas_start(mas
);
3706 if (mas_is_none(mas
))
3709 if (mas_is_ptr(mas
))
3712 return mtree_range_walk(mas
);
3716 * mtree_lookup_walk() - Internal quick lookup that does not keep maple state up
3719 * @mas: The maple state.
3721 * Note: Leaves mas in undesirable state.
3722 * Return: The entry for @mas->index or %NULL on dead node.
3724 static inline void *mtree_lookup_walk(struct ma_state
*mas
)
3726 unsigned long *pivots
;
3727 unsigned char offset
;
3728 struct maple_node
*node
;
3729 struct maple_enode
*next
;
3730 enum maple_type type
;
3739 node
= mte_to_node(next
);
3740 type
= mte_node_type(next
);
3741 pivots
= ma_pivots(node
, type
);
3742 end
= ma_data_end(node
, type
, pivots
, max
);
3743 if (unlikely(ma_dead_node(node
)))
3746 if (pivots
[offset
] >= mas
->index
) {
3747 max
= pivots
[offset
];
3750 } while (++offset
< end
);
3752 slots
= ma_slots(node
, type
);
3753 next
= mt_slot(mas
->tree
, slots
, offset
);
3754 if (unlikely(ma_dead_node(node
)))
3756 } while (!ma_is_leaf(type
));
3758 return (void *)next
;
3765 static void mte_destroy_walk(struct maple_enode
*, struct maple_tree
*);
3767 * mas_new_root() - Create a new root node that only contains the entry passed
3769 * @mas: The maple state
3770 * @entry: The entry to store.
3772 * Only valid when the index == 0 and the last == ULONG_MAX
3774 * Return 0 on error, 1 on success.
3776 static inline int mas_new_root(struct ma_state
*mas
, void *entry
)
3778 struct maple_enode
*root
= mas_root_locked(mas
);
3779 enum maple_type type
= maple_leaf_64
;
3780 struct maple_node
*node
;
3782 unsigned long *pivots
;
3784 if (!entry
&& !mas
->index
&& mas
->last
== ULONG_MAX
) {
3786 mas_set_height(mas
);
3787 rcu_assign_pointer(mas
->tree
->ma_root
, entry
);
3788 mas
->node
= MAS_START
;
3792 mas_node_count(mas
, 1);
3793 if (mas_is_err(mas
))
3796 node
= mas_pop_node(mas
);
3797 pivots
= ma_pivots(node
, type
);
3798 slots
= ma_slots(node
, type
);
3799 node
->parent
= ma_parent_ptr(mas_tree_parent(mas
));
3800 mas
->node
= mt_mk_node(node
, type
);
3801 rcu_assign_pointer(slots
[0], entry
);
3802 pivots
[0] = mas
->last
;
3804 mas_set_height(mas
);
3805 rcu_assign_pointer(mas
->tree
->ma_root
, mte_mk_root(mas
->node
));
3808 if (xa_is_node(root
))
3809 mte_destroy_walk(root
, mas
->tree
);
3814 * mas_wr_spanning_store() - Create a subtree with the store operation completed
3815 * and new nodes where necessary, then place the sub-tree in the actual tree.
3816 * Note that mas is expected to point to the node which caused the store to
3818 * @wr_mas: The maple write state
3820 * Return: 0 on error, positive on success.
3822 static inline int mas_wr_spanning_store(struct ma_wr_state
*wr_mas
)
3824 struct maple_subtree_state mast
;
3825 struct maple_big_node b_node
;
3826 struct ma_state
*mas
;
3827 unsigned char height
;
3829 /* Left and Right side of spanning store */
3830 MA_STATE(l_mas
, NULL
, 0, 0);
3831 MA_STATE(r_mas
, NULL
, 0, 0);
3832 MA_WR_STATE(r_wr_mas
, &r_mas
, wr_mas
->entry
);
3833 MA_WR_STATE(l_wr_mas
, &l_mas
, wr_mas
->entry
);
3836 * A store operation that spans multiple nodes is called a spanning
3837 * store and is handled early in the store call stack by the function
3838 * mas_is_span_wr(). When a spanning store is identified, the maple
3839 * state is duplicated. The first maple state walks the left tree path
3840 * to ``index``, the duplicate walks the right tree path to ``last``.
3841 * The data in the two nodes are combined into a single node, two nodes,
3842 * or possibly three nodes (see the 3-way split above). A ``NULL``
3843 * written to the last entry of a node is considered a spanning store as
3844 * a rebalance is required for the operation to complete and an overflow
3845 * of data may happen.
3848 trace_ma_op(__func__
, mas
);
3850 if (unlikely(!mas
->index
&& mas
->last
== ULONG_MAX
))
3851 return mas_new_root(mas
, wr_mas
->entry
);
3853 * Node rebalancing may occur due to this store, so there may be three new
3854 * entries per level plus a new root.
3856 height
= mas_mt_height(mas
);
3857 mas_node_count(mas
, 1 + height
* 3);
3858 if (mas_is_err(mas
))
3862 * Set up right side. Need to get to the next offset after the spanning
3863 * store to ensure it's not NULL and to combine both the next node and
3864 * the node with the start together.
3867 /* Avoid overflow, walk to next slot in the tree. */
3871 r_mas
.index
= r_mas
.last
;
3872 mas_wr_walk_index(&r_wr_mas
);
3873 r_mas
.last
= r_mas
.index
= mas
->last
;
3875 /* Set up left side. */
3877 mas_wr_walk_index(&l_wr_mas
);
3879 if (!wr_mas
->entry
) {
3880 mas_extend_spanning_null(&l_wr_mas
, &r_wr_mas
);
3881 mas
->offset
= l_mas
.offset
;
3882 mas
->index
= l_mas
.index
;
3883 mas
->last
= l_mas
.last
= r_mas
.last
;
3886 /* expanding NULLs may make this cover the entire range */
3887 if (!l_mas
.index
&& r_mas
.last
== ULONG_MAX
) {
3888 mas_set_range(mas
, 0, ULONG_MAX
);
3889 return mas_new_root(mas
, wr_mas
->entry
);
3892 memset(&b_node
, 0, sizeof(struct maple_big_node
));
3893 /* Copy l_mas and store the value in b_node. */
3894 mas_store_b_node(&l_wr_mas
, &b_node
, l_wr_mas
.node_end
);
3895 /* Copy r_mas into b_node. */
3896 if (r_mas
.offset
<= r_wr_mas
.node_end
)
3897 mas_mab_cp(&r_mas
, r_mas
.offset
, r_wr_mas
.node_end
,
3898 &b_node
, b_node
.b_end
+ 1);
3902 /* Stop spanning searches by searching for just index. */
3903 l_mas
.index
= l_mas
.last
= mas
->index
;
3906 mast
.orig_l
= &l_mas
;
3907 mast
.orig_r
= &r_mas
;
3908 /* Combine l_mas and r_mas and split them up evenly again. */
3909 return mas_spanning_rebalance(mas
, &mast
, height
+ 1);
3913 * mas_wr_node_store() - Attempt to store the value in a node
3914 * @wr_mas: The maple write state
3916 * Attempts to reuse the node, but may allocate.
3918 * Return: True if stored, false otherwise
3920 static inline bool mas_wr_node_store(struct ma_wr_state
*wr_mas
,
3921 unsigned char new_end
)
3923 struct ma_state
*mas
= wr_mas
->mas
;
3924 void __rcu
**dst_slots
;
3925 unsigned long *dst_pivots
;
3926 unsigned char dst_offset
, offset_end
= wr_mas
->offset_end
;
3927 struct maple_node reuse
, *newnode
;
3928 unsigned char copy_size
, node_pivots
= mt_pivots
[wr_mas
->type
];
3929 bool in_rcu
= mt_in_rcu(mas
->tree
);
3931 /* Check if there is enough data. The room is enough. */
3932 if (!mte_is_root(mas
->node
) && (new_end
<= mt_min_slots
[wr_mas
->type
]) &&
3933 !(mas
->mas_flags
& MA_STATE_BULK
))
3936 if (mas
->last
== wr_mas
->end_piv
)
3937 offset_end
++; /* don't copy this offset */
3938 else if (unlikely(wr_mas
->r_max
== ULONG_MAX
))
3939 mas_bulk_rebalance(mas
, wr_mas
->node_end
, wr_mas
->type
);
3943 mas_node_count(mas
, 1);
3944 if (mas_is_err(mas
))
3947 newnode
= mas_pop_node(mas
);
3949 memset(&reuse
, 0, sizeof(struct maple_node
));
3953 newnode
->parent
= mas_mn(mas
)->parent
;
3954 dst_pivots
= ma_pivots(newnode
, wr_mas
->type
);
3955 dst_slots
= ma_slots(newnode
, wr_mas
->type
);
3956 /* Copy from start to insert point */
3957 memcpy(dst_pivots
, wr_mas
->pivots
, sizeof(unsigned long) * mas
->offset
);
3958 memcpy(dst_slots
, wr_mas
->slots
, sizeof(void *) * mas
->offset
);
3960 /* Handle insert of new range starting after old range */
3961 if (wr_mas
->r_min
< mas
->index
) {
3962 rcu_assign_pointer(dst_slots
[mas
->offset
], wr_mas
->content
);
3963 dst_pivots
[mas
->offset
++] = mas
->index
- 1;
3966 /* Store the new entry and range end. */
3967 if (mas
->offset
< node_pivots
)
3968 dst_pivots
[mas
->offset
] = mas
->last
;
3969 rcu_assign_pointer(dst_slots
[mas
->offset
], wr_mas
->entry
);
3972 * this range wrote to the end of the node or it overwrote the rest of
3975 if (offset_end
> wr_mas
->node_end
)
3978 dst_offset
= mas
->offset
+ 1;
3979 /* Copy to the end of node if necessary. */
3980 copy_size
= wr_mas
->node_end
- offset_end
+ 1;
3981 memcpy(dst_slots
+ dst_offset
, wr_mas
->slots
+ offset_end
,
3982 sizeof(void *) * copy_size
);
3983 memcpy(dst_pivots
+ dst_offset
, wr_mas
->pivots
+ offset_end
,
3984 sizeof(unsigned long) * (copy_size
- 1));
3986 if (new_end
< node_pivots
)
3987 dst_pivots
[new_end
] = mas
->max
;
3990 mas_leaf_set_meta(mas
, newnode
, dst_pivots
, maple_leaf_64
, new_end
);
3992 struct maple_enode
*old_enode
= mas
->node
;
3994 mas
->node
= mt_mk_node(newnode
, wr_mas
->type
);
3995 mas_replace_node(mas
, old_enode
);
3997 memcpy(wr_mas
->node
, newnode
, sizeof(struct maple_node
));
3999 trace_ma_write(__func__
, mas
, 0, wr_mas
->entry
);
4000 mas_update_gap(mas
);
4005 * mas_wr_slot_store: Attempt to store a value in a slot.
4006 * @wr_mas: the maple write state
4008 * Return: True if stored, false otherwise
4010 static inline bool mas_wr_slot_store(struct ma_wr_state
*wr_mas
)
4012 struct ma_state
*mas
= wr_mas
->mas
;
4013 unsigned char offset
= mas
->offset
;
4014 void __rcu
**slots
= wr_mas
->slots
;
4017 gap
|= !mt_slot_locked(mas
->tree
, slots
, offset
);
4018 gap
|= !mt_slot_locked(mas
->tree
, slots
, offset
+ 1);
4020 if (wr_mas
->offset_end
- offset
== 1) {
4021 if (mas
->index
== wr_mas
->r_min
) {
4022 /* Overwriting the range and a part of the next one */
4023 rcu_assign_pointer(slots
[offset
], wr_mas
->entry
);
4024 wr_mas
->pivots
[offset
] = mas
->last
;
4026 /* Overwriting a part of the range and the next one */
4027 rcu_assign_pointer(slots
[offset
+ 1], wr_mas
->entry
);
4028 wr_mas
->pivots
[offset
] = mas
->index
- 1;
4029 mas
->offset
++; /* Keep mas accurate. */
4031 } else if (!mt_in_rcu(mas
->tree
)) {
4033 * Expand the range, only partially overwriting the previous and
4036 gap
|= !mt_slot_locked(mas
->tree
, slots
, offset
+ 2);
4037 rcu_assign_pointer(slots
[offset
+ 1], wr_mas
->entry
);
4038 wr_mas
->pivots
[offset
] = mas
->index
- 1;
4039 wr_mas
->pivots
[offset
+ 1] = mas
->last
;
4040 mas
->offset
++; /* Keep mas accurate. */
4045 trace_ma_write(__func__
, mas
, 0, wr_mas
->entry
);
4047 * Only update gap when the new entry is empty or there is an empty
4048 * entry in the original two ranges.
4050 if (!wr_mas
->entry
|| gap
)
4051 mas_update_gap(mas
);
4056 static inline void mas_wr_extend_null(struct ma_wr_state
*wr_mas
)
4058 struct ma_state
*mas
= wr_mas
->mas
;
4060 if (!wr_mas
->slots
[wr_mas
->offset_end
]) {
4061 /* If this one is null, the next and prev are not */
4062 mas
->last
= wr_mas
->end_piv
;
4064 /* Check next slot(s) if we are overwriting the end */
4065 if ((mas
->last
== wr_mas
->end_piv
) &&
4066 (wr_mas
->node_end
!= wr_mas
->offset_end
) &&
4067 !wr_mas
->slots
[wr_mas
->offset_end
+ 1]) {
4068 wr_mas
->offset_end
++;
4069 if (wr_mas
->offset_end
== wr_mas
->node_end
)
4070 mas
->last
= mas
->max
;
4072 mas
->last
= wr_mas
->pivots
[wr_mas
->offset_end
];
4073 wr_mas
->end_piv
= mas
->last
;
4077 if (!wr_mas
->content
) {
4078 /* If this one is null, the next and prev are not */
4079 mas
->index
= wr_mas
->r_min
;
4081 /* Check prev slot if we are overwriting the start */
4082 if (mas
->index
== wr_mas
->r_min
&& mas
->offset
&&
4083 !wr_mas
->slots
[mas
->offset
- 1]) {
4085 wr_mas
->r_min
= mas
->index
=
4086 mas_safe_min(mas
, wr_mas
->pivots
, mas
->offset
);
4087 wr_mas
->r_max
= wr_mas
->pivots
[mas
->offset
];
4092 static inline void mas_wr_end_piv(struct ma_wr_state
*wr_mas
)
4094 while ((wr_mas
->offset_end
< wr_mas
->node_end
) &&
4095 (wr_mas
->mas
->last
> wr_mas
->pivots
[wr_mas
->offset_end
]))
4096 wr_mas
->offset_end
++;
4098 if (wr_mas
->offset_end
< wr_mas
->node_end
)
4099 wr_mas
->end_piv
= wr_mas
->pivots
[wr_mas
->offset_end
];
4101 wr_mas
->end_piv
= wr_mas
->mas
->max
;
4104 mas_wr_extend_null(wr_mas
);
4107 static inline unsigned char mas_wr_new_end(struct ma_wr_state
*wr_mas
)
4109 struct ma_state
*mas
= wr_mas
->mas
;
4110 unsigned char new_end
= wr_mas
->node_end
+ 2;
4112 new_end
-= wr_mas
->offset_end
- mas
->offset
;
4113 if (wr_mas
->r_min
== mas
->index
)
4116 if (wr_mas
->end_piv
== mas
->last
)
4123 * mas_wr_append: Attempt to append
4124 * @wr_mas: the maple write state
4125 * @new_end: The end of the node after the modification
4127 * This is currently unsafe in rcu mode since the end of the node may be cached
4128 * by readers while the node contents may be updated which could result in
4129 * inaccurate information.
4131 * Return: True if appended, false otherwise
4133 static inline bool mas_wr_append(struct ma_wr_state
*wr_mas
,
4134 unsigned char new_end
)
4136 struct ma_state
*mas
;
4141 if (mt_in_rcu(mas
->tree
))
4144 if (mas
->offset
!= wr_mas
->node_end
)
4147 end
= wr_mas
->node_end
;
4148 if (mas
->offset
!= end
)
4151 if (new_end
< mt_pivots
[wr_mas
->type
]) {
4152 wr_mas
->pivots
[new_end
] = wr_mas
->pivots
[end
];
4153 ma_set_meta(wr_mas
->node
, wr_mas
->type
, 0, new_end
);
4156 slots
= wr_mas
->slots
;
4157 if (new_end
== end
+ 1) {
4158 if (mas
->last
== wr_mas
->r_max
) {
4159 /* Append to end of range */
4160 rcu_assign_pointer(slots
[new_end
], wr_mas
->entry
);
4161 wr_mas
->pivots
[end
] = mas
->index
- 1;
4162 mas
->offset
= new_end
;
4164 /* Append to start of range */
4165 rcu_assign_pointer(slots
[new_end
], wr_mas
->content
);
4166 wr_mas
->pivots
[end
] = mas
->last
;
4167 rcu_assign_pointer(slots
[end
], wr_mas
->entry
);
4170 /* Append to the range without touching any boundaries. */
4171 rcu_assign_pointer(slots
[new_end
], wr_mas
->content
);
4172 wr_mas
->pivots
[end
+ 1] = mas
->last
;
4173 rcu_assign_pointer(slots
[end
+ 1], wr_mas
->entry
);
4174 wr_mas
->pivots
[end
] = mas
->index
- 1;
4175 mas
->offset
= end
+ 1;
4178 if (!wr_mas
->content
|| !wr_mas
->entry
)
4179 mas_update_gap(mas
);
4181 trace_ma_write(__func__
, mas
, new_end
, wr_mas
->entry
);
4186 * mas_wr_bnode() - Slow path for a modification.
4187 * @wr_mas: The write maple state
4189 * This is where split, rebalance end up.
4191 static void mas_wr_bnode(struct ma_wr_state
*wr_mas
)
4193 struct maple_big_node b_node
;
4195 trace_ma_write(__func__
, wr_mas
->mas
, 0, wr_mas
->entry
);
4196 memset(&b_node
, 0, sizeof(struct maple_big_node
));
4197 mas_store_b_node(wr_mas
, &b_node
, wr_mas
->offset_end
);
4198 mas_commit_b_node(wr_mas
, &b_node
, wr_mas
->node_end
);
4201 static inline void mas_wr_modify(struct ma_wr_state
*wr_mas
)
4203 struct ma_state
*mas
= wr_mas
->mas
;
4204 unsigned char new_end
;
4206 /* Direct replacement */
4207 if (wr_mas
->r_min
== mas
->index
&& wr_mas
->r_max
== mas
->last
) {
4208 rcu_assign_pointer(wr_mas
->slots
[mas
->offset
], wr_mas
->entry
);
4209 if (!!wr_mas
->entry
^ !!wr_mas
->content
)
4210 mas_update_gap(mas
);
4215 * new_end exceeds the size of the maple node and cannot enter the fast
4218 new_end
= mas_wr_new_end(wr_mas
);
4219 if (new_end
>= mt_slots
[wr_mas
->type
])
4222 /* Attempt to append */
4223 if (mas_wr_append(wr_mas
, new_end
))
4226 if (new_end
== wr_mas
->node_end
&& mas_wr_slot_store(wr_mas
))
4229 if (mas_wr_node_store(wr_mas
, new_end
))
4232 if (mas_is_err(mas
))
4236 mas_wr_bnode(wr_mas
);
4240 * mas_wr_store_entry() - Internal call to store a value
4241 * @mas: The maple state
4242 * @entry: The entry to store.
4244 * Return: The contents that was stored at the index.
4246 static inline void *mas_wr_store_entry(struct ma_wr_state
*wr_mas
)
4248 struct ma_state
*mas
= wr_mas
->mas
;
4250 wr_mas
->content
= mas_start(mas
);
4251 if (mas_is_none(mas
) || mas_is_ptr(mas
)) {
4252 mas_store_root(mas
, wr_mas
->entry
);
4253 return wr_mas
->content
;
4256 if (unlikely(!mas_wr_walk(wr_mas
))) {
4257 mas_wr_spanning_store(wr_mas
);
4258 return wr_mas
->content
;
4261 /* At this point, we are at the leaf node that needs to be altered. */
4262 mas_wr_end_piv(wr_mas
);
4263 /* New root for a single pointer */
4264 if (unlikely(!mas
->index
&& mas
->last
== ULONG_MAX
)) {
4265 mas_new_root(mas
, wr_mas
->entry
);
4266 return wr_mas
->content
;
4269 mas_wr_modify(wr_mas
);
4270 return wr_mas
->content
;
4274 * mas_insert() - Internal call to insert a value
4275 * @mas: The maple state
4276 * @entry: The entry to store
4278 * Return: %NULL or the contents that already exists at the requested index
4279 * otherwise. The maple state needs to be checked for error conditions.
4281 static inline void *mas_insert(struct ma_state
*mas
, void *entry
)
4283 MA_WR_STATE(wr_mas
, mas
, entry
);
4286 * Inserting a new range inserts either 0, 1, or 2 pivots within the
4287 * tree. If the insert fits exactly into an existing gap with a value
4288 * of NULL, then the slot only needs to be written with the new value.
4289 * If the range being inserted is adjacent to another range, then only a
4290 * single pivot needs to be inserted (as well as writing the entry). If
4291 * the new range is within a gap but does not touch any other ranges,
4292 * then two pivots need to be inserted: the start - 1, and the end. As
4293 * usual, the entry must be written. Most operations require a new node
4294 * to be allocated and replace an existing node to ensure RCU safety,
4295 * when in RCU mode. The exception to requiring a newly allocated node
4296 * is when inserting at the end of a node (appending). When done
4297 * carefully, appending can reuse the node in place.
4299 wr_mas
.content
= mas_start(mas
);
4303 if (mas_is_none(mas
) || mas_is_ptr(mas
)) {
4304 mas_store_root(mas
, entry
);
4308 /* spanning writes always overwrite something */
4309 if (!mas_wr_walk(&wr_mas
))
4312 /* At this point, we are at the leaf node that needs to be altered. */
4313 wr_mas
.offset_end
= mas
->offset
;
4314 wr_mas
.end_piv
= wr_mas
.r_max
;
4316 if (wr_mas
.content
|| (mas
->last
> wr_mas
.r_max
))
4322 mas_wr_modify(&wr_mas
);
4323 return wr_mas
.content
;
4326 mas_set_err(mas
, -EEXIST
);
4327 return wr_mas
.content
;
4331 static inline void mas_rewalk(struct ma_state
*mas
, unsigned long index
)
4334 mas_set(mas
, index
);
4335 mas_state_walk(mas
);
4336 if (mas_is_start(mas
))
4340 static inline bool mas_rewalk_if_dead(struct ma_state
*mas
,
4341 struct maple_node
*node
, const unsigned long index
)
4343 if (unlikely(ma_dead_node(node
))) {
4344 mas_rewalk(mas
, index
);
4351 * mas_prev_node() - Find the prev non-null entry at the same level in the
4352 * tree. The prev value will be mas->node[mas->offset] or MAS_NONE.
4353 * @mas: The maple state
4354 * @min: The lower limit to search
4356 * The prev node value will be mas->node[mas->offset] or MAS_NONE.
4357 * Return: 1 if the node is dead, 0 otherwise.
4359 static inline int mas_prev_node(struct ma_state
*mas
, unsigned long min
)
4364 struct maple_node
*node
;
4365 unsigned long *pivots
;
4378 if (ma_is_root(node
))
4382 if (unlikely(mas_ascend(mas
)))
4384 offset
= mas
->offset
;
4390 mt
= mte_node_type(mas
->node
);
4393 slots
= ma_slots(node
, mt
);
4394 mas
->node
= mas_slot(mas
, slots
, offset
);
4395 if (unlikely(ma_dead_node(node
)))
4398 mt
= mte_node_type(mas
->node
);
4400 pivots
= ma_pivots(node
, mt
);
4401 offset
= ma_data_end(node
, mt
, pivots
, max
);
4402 if (unlikely(ma_dead_node(node
)))
4406 slots
= ma_slots(node
, mt
);
4407 mas
->node
= mas_slot(mas
, slots
, offset
);
4408 pivots
= ma_pivots(node
, mt
);
4409 if (unlikely(ma_dead_node(node
)))
4413 mas
->min
= pivots
[offset
- 1] + 1;
4415 mas
->offset
= mas_data_end(mas
);
4416 if (unlikely(mte_dead_node(mas
->node
)))
4422 if (unlikely(ma_dead_node(node
)))
4425 mas
->node
= MAS_NONE
;
4430 * mas_prev_slot() - Get the entry in the previous slot
4432 * @mas: The maple state
4433 * @max: The minimum starting range
4434 * @empty: Can be empty
4435 * @set_underflow: Set the @mas->node to underflow state on limit.
4437 * Return: The entry in the previous slot which is possibly NULL
4439 static void *mas_prev_slot(struct ma_state
*mas
, unsigned long min
, bool empty
,
4444 unsigned long pivot
;
4445 enum maple_type type
;
4446 unsigned long *pivots
;
4447 struct maple_node
*node
;
4448 unsigned long save_point
= mas
->index
;
4452 type
= mte_node_type(mas
->node
);
4453 pivots
= ma_pivots(node
, type
);
4454 if (unlikely(mas_rewalk_if_dead(mas
, node
, save_point
)))
4457 if (mas
->min
<= min
) {
4458 pivot
= mas_safe_min(mas
, pivots
, mas
->offset
);
4460 if (unlikely(mas_rewalk_if_dead(mas
, node
, save_point
)))
4468 if (likely(mas
->offset
)) {
4470 mas
->last
= mas
->index
- 1;
4471 mas
->index
= mas_safe_min(mas
, pivots
, mas
->offset
);
4473 if (mas_prev_node(mas
, min
)) {
4474 mas_rewalk(mas
, save_point
);
4478 if (mas_is_none(mas
))
4481 mas
->last
= mas
->max
;
4483 type
= mte_node_type(mas
->node
);
4484 pivots
= ma_pivots(node
, type
);
4485 mas
->index
= pivots
[mas
->offset
- 1] + 1;
4488 slots
= ma_slots(node
, type
);
4489 entry
= mas_slot(mas
, slots
, mas
->offset
);
4490 if (unlikely(mas_rewalk_if_dead(mas
, node
, save_point
)))
4497 if (mas
->index
<= min
)
4507 mas
->node
= MAS_UNDERFLOW
;
4512 * mas_next_node() - Get the next node at the same level in the tree.
4513 * @mas: The maple state
4514 * @max: The maximum pivot value to check.
4516 * The next value will be mas->node[mas->offset] or MAS_NONE.
4517 * Return: 1 on dead node, 0 otherwise.
4519 static inline int mas_next_node(struct ma_state
*mas
, struct maple_node
*node
,
4523 unsigned long *pivots
;
4524 struct maple_enode
*enode
;
4526 unsigned char node_end
;
4530 if (mas
->max
>= max
)
4536 if (ma_is_root(node
))
4540 if (unlikely(mas_ascend(mas
)))
4545 mt
= mte_node_type(mas
->node
);
4546 pivots
= ma_pivots(node
, mt
);
4547 node_end
= ma_data_end(node
, mt
, pivots
, mas
->max
);
4548 if (unlikely(ma_dead_node(node
)))
4551 } while (unlikely(mas
->offset
== node_end
));
4553 slots
= ma_slots(node
, mt
);
4555 enode
= mas_slot(mas
, slots
, mas
->offset
);
4556 if (unlikely(ma_dead_node(node
)))
4562 while (unlikely(level
> 1)) {
4566 mt
= mte_node_type(mas
->node
);
4567 slots
= ma_slots(node
, mt
);
4568 enode
= mas_slot(mas
, slots
, 0);
4569 if (unlikely(ma_dead_node(node
)))
4574 pivots
= ma_pivots(node
, mt
);
4576 mas
->max
= mas_safe_pivot(mas
, pivots
, mas
->offset
, mt
);
4577 if (unlikely(ma_dead_node(node
)))
4585 if (unlikely(ma_dead_node(node
)))
4588 mas
->node
= MAS_NONE
;
4593 * mas_next_slot() - Get the entry in the next slot
4595 * @mas: The maple state
4596 * @max: The maximum starting range
4597 * @empty: Can be empty
4598 * @set_overflow: Should @mas->node be set to overflow when the limit is
4601 * Return: The entry in the next slot which is possibly NULL
4603 static void *mas_next_slot(struct ma_state
*mas
, unsigned long max
, bool empty
,
4607 unsigned long *pivots
;
4608 unsigned long pivot
;
4609 enum maple_type type
;
4610 struct maple_node
*node
;
4611 unsigned char data_end
;
4612 unsigned long save_point
= mas
->last
;
4617 type
= mte_node_type(mas
->node
);
4618 pivots
= ma_pivots(node
, type
);
4619 data_end
= ma_data_end(node
, type
, pivots
, mas
->max
);
4620 if (unlikely(mas_rewalk_if_dead(mas
, node
, save_point
)))
4623 if (mas
->max
>= max
) {
4624 if (likely(mas
->offset
< data_end
))
4625 pivot
= pivots
[mas
->offset
];
4629 if (unlikely(mas_rewalk_if_dead(mas
, node
, save_point
)))
4636 if (likely(mas
->offset
< data_end
)) {
4637 mas
->index
= pivots
[mas
->offset
] + 1;
4640 if (likely(mas
->offset
< data_end
))
4641 mas
->last
= pivots
[mas
->offset
];
4643 mas
->last
= mas
->max
;
4645 if (mas_next_node(mas
, node
, max
)) {
4646 mas_rewalk(mas
, save_point
);
4650 if (WARN_ON_ONCE(mas_is_none(mas
))) {
4651 mas
->node
= MAS_OVERFLOW
;
4657 mas
->index
= mas
->min
;
4659 type
= mte_node_type(mas
->node
);
4660 pivots
= ma_pivots(node
, type
);
4661 mas
->last
= pivots
[0];
4664 slots
= ma_slots(node
, type
);
4665 entry
= mt_slot(mas
->tree
, slots
, mas
->offset
);
4666 if (unlikely(mas_rewalk_if_dead(mas
, node
, save_point
)))
4673 if (mas
->last
>= max
)
4676 mas
->index
= mas
->last
+ 1;
4677 /* Node cannot end on NULL, so it's safe to short-cut here */
4685 mas
->node
= MAS_OVERFLOW
;
4690 * mas_next_entry() - Internal function to get the next entry.
4691 * @mas: The maple state
4692 * @limit: The maximum range start.
4694 * Set the @mas->node to the next entry and the range_start to
4695 * the beginning value for the entry. Does not check beyond @limit.
4696 * Sets @mas->index and @mas->last to the range, Does not update @mas->index and
4697 * @mas->last on overflow.
4698 * Restarts on dead nodes.
4700 * Return: the next entry or %NULL.
4702 static inline void *mas_next_entry(struct ma_state
*mas
, unsigned long limit
)
4704 if (mas
->last
>= limit
) {
4705 mas
->node
= MAS_OVERFLOW
;
4709 return mas_next_slot(mas
, limit
, false, true);
4713 * mas_rev_awalk() - Internal function. Reverse allocation walk. Find the
4714 * highest gap address of a given size in a given node and descend.
4715 * @mas: The maple state
4716 * @size: The needed size.
4718 * Return: True if found in a leaf, false otherwise.
4721 static bool mas_rev_awalk(struct ma_state
*mas
, unsigned long size
,
4722 unsigned long *gap_min
, unsigned long *gap_max
)
4724 enum maple_type type
= mte_node_type(mas
->node
);
4725 struct maple_node
*node
= mas_mn(mas
);
4726 unsigned long *pivots
, *gaps
;
4728 unsigned long gap
= 0;
4729 unsigned long max
, min
;
4730 unsigned char offset
;
4732 if (unlikely(mas_is_err(mas
)))
4735 if (ma_is_dense(type
)) {
4737 mas
->offset
= (unsigned char)(mas
->index
- mas
->min
);
4741 pivots
= ma_pivots(node
, type
);
4742 slots
= ma_slots(node
, type
);
4743 gaps
= ma_gaps(node
, type
);
4744 offset
= mas
->offset
;
4745 min
= mas_safe_min(mas
, pivots
, offset
);
4746 /* Skip out of bounds. */
4747 while (mas
->last
< min
)
4748 min
= mas_safe_min(mas
, pivots
, --offset
);
4750 max
= mas_safe_pivot(mas
, pivots
, offset
, type
);
4751 while (mas
->index
<= max
) {
4755 else if (!mas_slot(mas
, slots
, offset
))
4756 gap
= max
- min
+ 1;
4759 if ((size
<= gap
) && (size
<= mas
->last
- min
+ 1))
4763 /* Skip the next slot, it cannot be a gap. */
4768 max
= pivots
[offset
];
4769 min
= mas_safe_min(mas
, pivots
, offset
);
4779 min
= mas_safe_min(mas
, pivots
, offset
);
4782 if (unlikely((mas
->index
> max
) || (size
- 1 > max
- mas
->index
)))
4785 if (unlikely(ma_is_leaf(type
))) {
4786 mas
->offset
= offset
;
4788 *gap_max
= min
+ gap
- 1;
4792 /* descend, only happens under lock. */
4793 mas
->node
= mas_slot(mas
, slots
, offset
);
4796 mas
->offset
= mas_data_end(mas
);
4800 if (!mte_is_root(mas
->node
))
4804 mas_set_err(mas
, -EBUSY
);
4808 static inline bool mas_anode_descend(struct ma_state
*mas
, unsigned long size
)
4810 enum maple_type type
= mte_node_type(mas
->node
);
4811 unsigned long pivot
, min
, gap
= 0;
4812 unsigned char offset
, data_end
;
4813 unsigned long *gaps
, *pivots
;
4815 struct maple_node
*node
;
4818 if (ma_is_dense(type
)) {
4819 mas
->offset
= (unsigned char)(mas
->index
- mas
->min
);
4824 pivots
= ma_pivots(node
, type
);
4825 slots
= ma_slots(node
, type
);
4826 gaps
= ma_gaps(node
, type
);
4827 offset
= mas
->offset
;
4828 min
= mas_safe_min(mas
, pivots
, offset
);
4829 data_end
= ma_data_end(node
, type
, pivots
, mas
->max
);
4830 for (; offset
<= data_end
; offset
++) {
4831 pivot
= mas_safe_pivot(mas
, pivots
, offset
, type
);
4833 /* Not within lower bounds */
4834 if (mas
->index
> pivot
)
4839 else if (!mas_slot(mas
, slots
, offset
))
4840 gap
= min(pivot
, mas
->last
) - max(mas
->index
, min
) + 1;
4845 if (ma_is_leaf(type
)) {
4849 if (mas
->index
<= pivot
) {
4850 mas
->node
= mas_slot(mas
, slots
, offset
);
4859 if (mas
->last
<= pivot
) {
4860 mas_set_err(mas
, -EBUSY
);
4865 if (mte_is_root(mas
->node
))
4868 mas
->offset
= offset
;
4873 * mas_walk() - Search for @mas->index in the tree.
4874 * @mas: The maple state.
4876 * mas->index and mas->last will be set to the range if there is a value. If
4877 * mas->node is MAS_NONE, reset to MAS_START.
4879 * Return: the entry at the location or %NULL.
4881 void *mas_walk(struct ma_state
*mas
)
4885 if (!mas_is_active(mas
) || !mas_is_start(mas
))
4886 mas
->node
= MAS_START
;
4888 entry
= mas_state_walk(mas
);
4889 if (mas_is_start(mas
)) {
4891 } else if (mas_is_none(mas
)) {
4893 mas
->last
= ULONG_MAX
;
4894 } else if (mas_is_ptr(mas
)) {
4901 mas
->last
= ULONG_MAX
;
4902 mas
->node
= MAS_NONE
;
4908 EXPORT_SYMBOL_GPL(mas_walk
);
4910 static inline bool mas_rewind_node(struct ma_state
*mas
)
4915 if (mte_is_root(mas
->node
)) {
4925 mas
->offset
= --slot
;
4930 * mas_skip_node() - Internal function. Skip over a node.
4931 * @mas: The maple state.
4933 * Return: true if there is another node, false otherwise.
4935 static inline bool mas_skip_node(struct ma_state
*mas
)
4937 if (mas_is_err(mas
))
4941 if (mte_is_root(mas
->node
)) {
4942 if (mas
->offset
>= mas_data_end(mas
)) {
4943 mas_set_err(mas
, -EBUSY
);
4949 } while (mas
->offset
>= mas_data_end(mas
));
4956 * mas_awalk() - Allocation walk. Search from low address to high, for a gap of
4958 * @mas: The maple state
4959 * @size: The size of the gap required
4961 * Search between @mas->index and @mas->last for a gap of @size.
4963 static inline void mas_awalk(struct ma_state
*mas
, unsigned long size
)
4965 struct maple_enode
*last
= NULL
;
4968 * There are 4 options:
4969 * go to child (descend)
4970 * go back to parent (ascend)
4971 * no gap found. (return, slot == MAPLE_NODE_SLOTS)
4972 * found the gap. (return, slot != MAPLE_NODE_SLOTS)
4974 while (!mas_is_err(mas
) && !mas_anode_descend(mas
, size
)) {
4975 if (last
== mas
->node
)
4983 * mas_sparse_area() - Internal function. Return upper or lower limit when
4984 * searching for a gap in an empty tree.
4985 * @mas: The maple state
4986 * @min: the minimum range
4987 * @max: The maximum range
4988 * @size: The size of the gap
4989 * @fwd: Searching forward or back
4991 static inline int mas_sparse_area(struct ma_state
*mas
, unsigned long min
,
4992 unsigned long max
, unsigned long size
, bool fwd
)
4994 if (!unlikely(mas_is_none(mas
)) && min
== 0) {
4997 * At this time, min is increased, we need to recheck whether
4998 * the size is satisfied.
5000 if (min
> max
|| max
- min
+ 1 < size
)
5007 mas
->last
= min
+ size
- 1;
5010 mas
->index
= max
- size
+ 1;
5016 * mas_empty_area() - Get the lowest address within the range that is
5017 * sufficient for the size requested.
5018 * @mas: The maple state
5019 * @min: The lowest value of the range
5020 * @max: The highest value of the range
5021 * @size: The size needed
5023 int mas_empty_area(struct ma_state
*mas
, unsigned long min
,
5024 unsigned long max
, unsigned long size
)
5026 unsigned char offset
;
5027 unsigned long *pivots
;
5033 if (size
== 0 || max
- min
< size
- 1)
5036 if (mas_is_start(mas
))
5038 else if (mas
->offset
>= 2)
5040 else if (!mas_skip_node(mas
))
5044 if (mas_is_none(mas
) || mas_is_ptr(mas
))
5045 return mas_sparse_area(mas
, min
, max
, size
, true);
5047 /* The start of the window can only be within these values */
5050 mas_awalk(mas
, size
);
5052 if (unlikely(mas_is_err(mas
)))
5053 return xa_err(mas
->node
);
5055 offset
= mas
->offset
;
5056 if (unlikely(offset
== MAPLE_NODE_SLOTS
))
5059 mt
= mte_node_type(mas
->node
);
5060 pivots
= ma_pivots(mas_mn(mas
), mt
);
5061 min
= mas_safe_min(mas
, pivots
, offset
);
5062 if (mas
->index
< min
)
5064 mas
->last
= mas
->index
+ size
- 1;
5067 EXPORT_SYMBOL_GPL(mas_empty_area
);
5070 * mas_empty_area_rev() - Get the highest address within the range that is
5071 * sufficient for the size requested.
5072 * @mas: The maple state
5073 * @min: The lowest value of the range
5074 * @max: The highest value of the range
5075 * @size: The size needed
5077 int mas_empty_area_rev(struct ma_state
*mas
, unsigned long min
,
5078 unsigned long max
, unsigned long size
)
5080 struct maple_enode
*last
= mas
->node
;
5085 if (size
== 0 || max
- min
< size
- 1)
5088 if (mas_is_start(mas
)) {
5090 mas
->offset
= mas_data_end(mas
);
5091 } else if (mas
->offset
>= 2) {
5093 } else if (!mas_rewind_node(mas
)) {
5098 if (mas_is_none(mas
) || mas_is_ptr(mas
))
5099 return mas_sparse_area(mas
, min
, max
, size
, false);
5101 /* The start of the window can only be within these values. */
5105 while (!mas_rev_awalk(mas
, size
, &min
, &max
)) {
5106 if (last
== mas
->node
) {
5107 if (!mas_rewind_node(mas
))
5114 if (mas_is_err(mas
))
5115 return xa_err(mas
->node
);
5117 if (unlikely(mas
->offset
== MAPLE_NODE_SLOTS
))
5120 /* Trim the upper limit to the max. */
5121 if (max
< mas
->last
)
5124 mas
->index
= mas
->last
- size
+ 1;
5127 EXPORT_SYMBOL_GPL(mas_empty_area_rev
);
5130 * mte_dead_leaves() - Mark all leaves of a node as dead.
5131 * @mas: The maple state
5132 * @slots: Pointer to the slot array
5133 * @type: The maple node type
5135 * Must hold the write lock.
5137 * Return: The number of leaves marked as dead.
5140 unsigned char mte_dead_leaves(struct maple_enode
*enode
, struct maple_tree
*mt
,
5143 struct maple_node
*node
;
5144 enum maple_type type
;
5148 for (offset
= 0; offset
< mt_slot_count(enode
); offset
++) {
5149 entry
= mt_slot(mt
, slots
, offset
);
5150 type
= mte_node_type(entry
);
5151 node
= mte_to_node(entry
);
5152 /* Use both node and type to catch LE & BE metadata */
5156 mte_set_node_dead(entry
);
5158 rcu_assign_pointer(slots
[offset
], node
);
5165 * mte_dead_walk() - Walk down a dead tree to just before the leaves
5166 * @enode: The maple encoded node
5167 * @offset: The starting offset
5169 * Note: This can only be used from the RCU callback context.
5171 static void __rcu
**mte_dead_walk(struct maple_enode
**enode
, unsigned char offset
)
5173 struct maple_node
*node
, *next
;
5174 void __rcu
**slots
= NULL
;
5176 next
= mte_to_node(*enode
);
5178 *enode
= ma_enode_ptr(next
);
5179 node
= mte_to_node(*enode
);
5180 slots
= ma_slots(node
, node
->type
);
5181 next
= rcu_dereference_protected(slots
[offset
],
5182 lock_is_held(&rcu_callback_map
));
5184 } while (!ma_is_leaf(next
->type
));
5190 * mt_free_walk() - Walk & free a tree in the RCU callback context
5191 * @head: The RCU head that's within the node.
5193 * Note: This can only be used from the RCU callback context.
5195 static void mt_free_walk(struct rcu_head
*head
)
5198 struct maple_node
*node
, *start
;
5199 struct maple_enode
*enode
;
5200 unsigned char offset
;
5201 enum maple_type type
;
5203 node
= container_of(head
, struct maple_node
, rcu
);
5205 if (ma_is_leaf(node
->type
))
5209 enode
= mt_mk_node(node
, node
->type
);
5210 slots
= mte_dead_walk(&enode
, 0);
5211 node
= mte_to_node(enode
);
5213 mt_free_bulk(node
->slot_len
, slots
);
5214 offset
= node
->parent_slot
+ 1;
5215 enode
= node
->piv_parent
;
5216 if (mte_to_node(enode
) == node
)
5219 type
= mte_node_type(enode
);
5220 slots
= ma_slots(mte_to_node(enode
), type
);
5221 if ((offset
< mt_slots
[type
]) &&
5222 rcu_dereference_protected(slots
[offset
],
5223 lock_is_held(&rcu_callback_map
)))
5224 slots
= mte_dead_walk(&enode
, offset
);
5225 node
= mte_to_node(enode
);
5226 } while ((node
!= start
) || (node
->slot_len
< offset
));
5228 slots
= ma_slots(node
, node
->type
);
5229 mt_free_bulk(node
->slot_len
, slots
);
5232 mt_free_rcu(&node
->rcu
);
5235 static inline void __rcu
**mte_destroy_descend(struct maple_enode
**enode
,
5236 struct maple_tree
*mt
, struct maple_enode
*prev
, unsigned char offset
)
5238 struct maple_node
*node
;
5239 struct maple_enode
*next
= *enode
;
5240 void __rcu
**slots
= NULL
;
5241 enum maple_type type
;
5242 unsigned char next_offset
= 0;
5246 node
= mte_to_node(*enode
);
5247 type
= mte_node_type(*enode
);
5248 slots
= ma_slots(node
, type
);
5249 next
= mt_slot_locked(mt
, slots
, next_offset
);
5250 if ((mte_dead_node(next
)))
5251 next
= mt_slot_locked(mt
, slots
, ++next_offset
);
5253 mte_set_node_dead(*enode
);
5255 node
->piv_parent
= prev
;
5256 node
->parent_slot
= offset
;
5257 offset
= next_offset
;
5260 } while (!mte_is_leaf(next
));
5265 static void mt_destroy_walk(struct maple_enode
*enode
, struct maple_tree
*mt
,
5269 struct maple_node
*node
= mte_to_node(enode
);
5270 struct maple_enode
*start
;
5272 if (mte_is_leaf(enode
)) {
5273 node
->type
= mte_node_type(enode
);
5278 slots
= mte_destroy_descend(&enode
, mt
, start
, 0);
5279 node
= mte_to_node(enode
); // Updated in the above call.
5281 enum maple_type type
;
5282 unsigned char offset
;
5283 struct maple_enode
*parent
, *tmp
;
5285 node
->slot_len
= mte_dead_leaves(enode
, mt
, slots
);
5287 mt_free_bulk(node
->slot_len
, slots
);
5288 offset
= node
->parent_slot
+ 1;
5289 enode
= node
->piv_parent
;
5290 if (mte_to_node(enode
) == node
)
5293 type
= mte_node_type(enode
);
5294 slots
= ma_slots(mte_to_node(enode
), type
);
5295 if (offset
>= mt_slots
[type
])
5298 tmp
= mt_slot_locked(mt
, slots
, offset
);
5299 if (mte_node_type(tmp
) && mte_to_node(tmp
)) {
5302 slots
= mte_destroy_descend(&enode
, mt
, parent
, offset
);
5305 node
= mte_to_node(enode
);
5306 } while (start
!= enode
);
5308 node
= mte_to_node(enode
);
5309 node
->slot_len
= mte_dead_leaves(enode
, mt
, slots
);
5311 mt_free_bulk(node
->slot_len
, slots
);
5315 mt_free_rcu(&node
->rcu
);
5317 mt_clear_meta(mt
, node
, node
->type
);
5321 * mte_destroy_walk() - Free a tree or sub-tree.
5322 * @enode: the encoded maple node (maple_enode) to start
5323 * @mt: the tree to free - needed for node types.
5325 * Must hold the write lock.
5327 static inline void mte_destroy_walk(struct maple_enode
*enode
,
5328 struct maple_tree
*mt
)
5330 struct maple_node
*node
= mte_to_node(enode
);
5332 if (mt_in_rcu(mt
)) {
5333 mt_destroy_walk(enode
, mt
, false);
5334 call_rcu(&node
->rcu
, mt_free_walk
);
5336 mt_destroy_walk(enode
, mt
, true);
5340 static void mas_wr_store_setup(struct ma_wr_state
*wr_mas
)
5342 if (!mas_is_active(wr_mas
->mas
)) {
5343 if (mas_is_start(wr_mas
->mas
))
5346 if (unlikely(mas_is_paused(wr_mas
->mas
)))
5349 if (unlikely(mas_is_none(wr_mas
->mas
)))
5352 if (unlikely(mas_is_overflow(wr_mas
->mas
)))
5355 if (unlikely(mas_is_underflow(wr_mas
->mas
)))
5360 * A less strict version of mas_is_span_wr() where we allow spanning
5361 * writes within this node. This is to stop partial walks in
5362 * mas_prealloc() from being reset.
5364 if (wr_mas
->mas
->last
> wr_mas
->mas
->max
)
5370 if (mte_is_leaf(wr_mas
->mas
->node
) &&
5371 wr_mas
->mas
->last
== wr_mas
->mas
->max
)
5377 mas_reset(wr_mas
->mas
);
5383 * mas_store() - Store an @entry.
5384 * @mas: The maple state.
5385 * @entry: The entry to store.
5387 * The @mas->index and @mas->last is used to set the range for the @entry.
5388 * Note: The @mas should have pre-allocated entries to ensure there is memory to
5389 * store the entry. Please see mas_expected_entries()/mas_destroy() for more details.
5391 * Return: the first entry between mas->index and mas->last or %NULL.
5393 void *mas_store(struct ma_state
*mas
, void *entry
)
5395 MA_WR_STATE(wr_mas
, mas
, entry
);
5397 trace_ma_write(__func__
, mas
, 0, entry
);
5398 #ifdef CONFIG_DEBUG_MAPLE_TREE
5399 if (MAS_WARN_ON(mas
, mas
->index
> mas
->last
))
5400 pr_err("Error %lX > %lX %p\n", mas
->index
, mas
->last
, entry
);
5402 if (mas
->index
> mas
->last
) {
5403 mas_set_err(mas
, -EINVAL
);
5410 * Storing is the same operation as insert with the added caveat that it
5411 * can overwrite entries. Although this seems simple enough, one may
5412 * want to examine what happens if a single store operation was to
5413 * overwrite multiple entries within a self-balancing B-Tree.
5415 mas_wr_store_setup(&wr_mas
);
5416 mas_wr_store_entry(&wr_mas
);
5417 return wr_mas
.content
;
5419 EXPORT_SYMBOL_GPL(mas_store
);
5422 * mas_store_gfp() - Store a value into the tree.
5423 * @mas: The maple state
5424 * @entry: The entry to store
5425 * @gfp: The GFP_FLAGS to use for allocations if necessary.
5427 * Return: 0 on success, -EINVAL on invalid request, -ENOMEM if memory could not
5430 int mas_store_gfp(struct ma_state
*mas
, void *entry
, gfp_t gfp
)
5432 MA_WR_STATE(wr_mas
, mas
, entry
);
5434 mas_wr_store_setup(&wr_mas
);
5435 trace_ma_write(__func__
, mas
, 0, entry
);
5437 mas_wr_store_entry(&wr_mas
);
5438 if (unlikely(mas_nomem(mas
, gfp
)))
5441 if (unlikely(mas_is_err(mas
)))
5442 return xa_err(mas
->node
);
5446 EXPORT_SYMBOL_GPL(mas_store_gfp
);
5449 * mas_store_prealloc() - Store a value into the tree using memory
5450 * preallocated in the maple state.
5451 * @mas: The maple state
5452 * @entry: The entry to store.
5454 void mas_store_prealloc(struct ma_state
*mas
, void *entry
)
5456 MA_WR_STATE(wr_mas
, mas
, entry
);
5458 mas_wr_store_setup(&wr_mas
);
5459 trace_ma_write(__func__
, mas
, 0, entry
);
5460 mas_wr_store_entry(&wr_mas
);
5461 MAS_WR_BUG_ON(&wr_mas
, mas_is_err(mas
));
5464 EXPORT_SYMBOL_GPL(mas_store_prealloc
);
5467 * mas_preallocate() - Preallocate enough nodes for a store operation
5468 * @mas: The maple state
5469 * @entry: The entry that will be stored
5470 * @gfp: The GFP_FLAGS to use for allocations.
5472 * Return: 0 on success, -ENOMEM if memory could not be allocated.
5474 int mas_preallocate(struct ma_state
*mas
, void *entry
, gfp_t gfp
)
5476 MA_WR_STATE(wr_mas
, mas
, entry
);
5477 unsigned char node_size
;
5482 if (unlikely(!mas
->index
&& mas
->last
== ULONG_MAX
))
5485 mas_wr_store_setup(&wr_mas
);
5486 wr_mas
.content
= mas_start(mas
);
5488 if (unlikely(mas_is_none(mas
) || mas_is_ptr(mas
)))
5491 if (unlikely(!mas_wr_walk(&wr_mas
))) {
5492 /* Spanning store, use worst case for now */
5493 request
= 1 + mas_mt_height(mas
) * 3;
5497 /* At this point, we are at the leaf node that needs to be altered. */
5498 /* Exact fit, no nodes needed. */
5499 if (wr_mas
.r_min
== mas
->index
&& wr_mas
.r_max
== mas
->last
)
5502 mas_wr_end_piv(&wr_mas
);
5503 node_size
= mas_wr_new_end(&wr_mas
);
5504 if (node_size
>= mt_slots
[wr_mas
.type
]) {
5505 /* Split, worst case for now. */
5506 request
= 1 + mas_mt_height(mas
) * 2;
5510 /* New root needs a singe node */
5511 if (unlikely(mte_is_root(mas
->node
)))
5514 /* Potential spanning rebalance collapsing a node, use worst-case */
5515 if (node_size
- 1 <= mt_min_slots
[wr_mas
.type
])
5516 request
= mas_mt_height(mas
) * 2 - 1;
5518 /* node store, slot store needs one node */
5520 mas_node_count_gfp(mas
, request
, gfp
);
5521 mas
->mas_flags
|= MA_STATE_PREALLOC
;
5522 if (likely(!mas_is_err(mas
)))
5525 mas_set_alloc_req(mas
, 0);
5526 ret
= xa_err(mas
->node
);
5532 EXPORT_SYMBOL_GPL(mas_preallocate
);
5535 * mas_destroy() - destroy a maple state.
5536 * @mas: The maple state
5538 * Upon completion, check the left-most node and rebalance against the node to
5539 * the right if necessary. Frees any allocated nodes associated with this maple
5542 void mas_destroy(struct ma_state
*mas
)
5544 struct maple_alloc
*node
;
5545 unsigned long total
;
5548 * When using mas_for_each() to insert an expected number of elements,
5549 * it is possible that the number inserted is less than the expected
5550 * number. To fix an invalid final node, a check is performed here to
5551 * rebalance the previous node with the final node.
5553 if (mas
->mas_flags
& MA_STATE_REBALANCE
) {
5557 mtree_range_walk(mas
);
5558 end
= mas_data_end(mas
) + 1;
5559 if (end
< mt_min_slot_count(mas
->node
) - 1)
5560 mas_destroy_rebalance(mas
, end
);
5562 mas
->mas_flags
&= ~MA_STATE_REBALANCE
;
5564 mas
->mas_flags
&= ~(MA_STATE_BULK
|MA_STATE_PREALLOC
);
5566 total
= mas_allocated(mas
);
5569 mas
->alloc
= node
->slot
[0];
5570 if (node
->node_count
> 1) {
5571 size_t count
= node
->node_count
- 1;
5573 mt_free_bulk(count
, (void __rcu
**)&node
->slot
[1]);
5576 kmem_cache_free(maple_node_cache
, node
);
5582 EXPORT_SYMBOL_GPL(mas_destroy
);
5585 * mas_expected_entries() - Set the expected number of entries that will be inserted.
5586 * @mas: The maple state
5587 * @nr_entries: The number of expected entries.
5589 * This will attempt to pre-allocate enough nodes to store the expected number
5590 * of entries. The allocations will occur using the bulk allocator interface
5591 * for speed. Please call mas_destroy() on the @mas after inserting the entries
5592 * to ensure any unused nodes are freed.
5594 * Return: 0 on success, -ENOMEM if memory could not be allocated.
5596 int mas_expected_entries(struct ma_state
*mas
, unsigned long nr_entries
)
5598 int nonleaf_cap
= MAPLE_ARANGE64_SLOTS
- 2;
5599 struct maple_enode
*enode
= mas
->node
;
5604 * Sometimes it is necessary to duplicate a tree to a new tree, such as
5605 * forking a process and duplicating the VMAs from one tree to a new
5606 * tree. When such a situation arises, it is known that the new tree is
5607 * not going to be used until the entire tree is populated. For
5608 * performance reasons, it is best to use a bulk load with RCU disabled.
5609 * This allows for optimistic splitting that favours the left and reuse
5610 * of nodes during the operation.
5613 /* Optimize splitting for bulk insert in-order */
5614 mas
->mas_flags
|= MA_STATE_BULK
;
5617 * Avoid overflow, assume a gap between each entry and a trailing null.
5618 * If this is wrong, it just means allocation can happen during
5619 * insertion of entries.
5621 nr_nodes
= max(nr_entries
, nr_entries
* 2 + 1);
5622 if (!mt_is_alloc(mas
->tree
))
5623 nonleaf_cap
= MAPLE_RANGE64_SLOTS
- 2;
5625 /* Leaves; reduce slots to keep space for expansion */
5626 nr_nodes
= DIV_ROUND_UP(nr_nodes
, MAPLE_RANGE64_SLOTS
- 2);
5627 /* Internal nodes */
5628 nr_nodes
+= DIV_ROUND_UP(nr_nodes
, nonleaf_cap
);
5629 /* Add working room for split (2 nodes) + new parents */
5630 mas_node_count_gfp(mas
, nr_nodes
+ 3, GFP_KERNEL
);
5632 /* Detect if allocations run out */
5633 mas
->mas_flags
|= MA_STATE_PREALLOC
;
5635 if (!mas_is_err(mas
))
5638 ret
= xa_err(mas
->node
);
5644 EXPORT_SYMBOL_GPL(mas_expected_entries
);
5646 static inline bool mas_next_setup(struct ma_state
*mas
, unsigned long max
,
5649 bool was_none
= mas_is_none(mas
);
5651 if (unlikely(mas
->last
>= max
)) {
5652 mas
->node
= MAS_OVERFLOW
;
5656 if (mas_is_active(mas
))
5659 if (mas_is_none(mas
) || mas_is_paused(mas
)) {
5660 mas
->node
= MAS_START
;
5661 } else if (mas_is_overflow(mas
)) {
5662 /* Overflowed before, but the max changed */
5663 mas
->node
= MAS_START
;
5664 } else if (mas_is_underflow(mas
)) {
5665 mas
->node
= MAS_START
;
5666 *entry
= mas_walk(mas
);
5671 if (mas_is_start(mas
))
5672 *entry
= mas_walk(mas
); /* Retries on dead nodes handled by mas_walk */
5674 if (mas_is_ptr(mas
)) {
5676 if (was_none
&& mas
->index
== 0) {
5677 mas
->index
= mas
->last
= 0;
5681 mas
->last
= ULONG_MAX
;
5682 mas
->node
= MAS_NONE
;
5686 if (mas_is_none(mas
))
5693 * mas_next() - Get the next entry.
5694 * @mas: The maple state
5695 * @max: The maximum index to check.
5697 * Returns the next entry after @mas->index.
5698 * Must hold rcu_read_lock or the write lock.
5699 * Can return the zero entry.
5701 * Return: The next entry or %NULL
5703 void *mas_next(struct ma_state
*mas
, unsigned long max
)
5707 if (mas_next_setup(mas
, max
, &entry
))
5710 /* Retries on dead nodes handled by mas_next_slot */
5711 return mas_next_slot(mas
, max
, false, true);
5713 EXPORT_SYMBOL_GPL(mas_next
);
5716 * mas_next_range() - Advance the maple state to the next range
5717 * @mas: The maple state
5718 * @max: The maximum index to check.
5720 * Sets @mas->index and @mas->last to the range.
5721 * Must hold rcu_read_lock or the write lock.
5722 * Can return the zero entry.
5724 * Return: The next entry or %NULL
5726 void *mas_next_range(struct ma_state
*mas
, unsigned long max
)
5730 if (mas_next_setup(mas
, max
, &entry
))
5733 /* Retries on dead nodes handled by mas_next_slot */
5734 return mas_next_slot(mas
, max
, true, true);
5736 EXPORT_SYMBOL_GPL(mas_next_range
);
5739 * mt_next() - get the next value in the maple tree
5740 * @mt: The maple tree
5741 * @index: The start index
5742 * @max: The maximum index to check
5744 * Takes RCU read lock internally to protect the search, which does not
5745 * protect the returned pointer after dropping RCU read lock.
5746 * See also: Documentation/core-api/maple_tree.rst
5748 * Return: The entry higher than @index or %NULL if nothing is found.
5750 void *mt_next(struct maple_tree
*mt
, unsigned long index
, unsigned long max
)
5753 MA_STATE(mas
, mt
, index
, index
);
5756 entry
= mas_next(&mas
, max
);
5760 EXPORT_SYMBOL_GPL(mt_next
);
5762 static inline bool mas_prev_setup(struct ma_state
*mas
, unsigned long min
,
5765 if (unlikely(mas
->index
<= min
)) {
5766 mas
->node
= MAS_UNDERFLOW
;
5770 if (mas_is_active(mas
))
5773 if (mas_is_overflow(mas
)) {
5774 mas
->node
= MAS_START
;
5775 *entry
= mas_walk(mas
);
5780 if (mas_is_none(mas
) || mas_is_paused(mas
)) {
5781 mas
->node
= MAS_START
;
5782 } else if (mas_is_underflow(mas
)) {
5783 /* underflowed before but the min changed */
5784 mas
->node
= MAS_START
;
5787 if (mas_is_start(mas
))
5790 if (unlikely(mas_is_ptr(mas
))) {
5793 mas
->index
= mas
->last
= 0;
5794 *entry
= mas_root(mas
);
5798 if (mas_is_none(mas
)) {
5800 /* Walked to out-of-range pointer? */
5801 mas
->index
= mas
->last
= 0;
5802 mas
->node
= MAS_ROOT
;
5803 *entry
= mas_root(mas
);
5812 mas
->node
= MAS_NONE
;
5817 * mas_prev() - Get the previous entry
5818 * @mas: The maple state
5819 * @min: The minimum value to check.
5821 * Must hold rcu_read_lock or the write lock.
5822 * Will reset mas to MAS_START if the node is MAS_NONE. Will stop on not
5825 * Return: the previous value or %NULL.
5827 void *mas_prev(struct ma_state
*mas
, unsigned long min
)
5831 if (mas_prev_setup(mas
, min
, &entry
))
5834 return mas_prev_slot(mas
, min
, false, true);
5836 EXPORT_SYMBOL_GPL(mas_prev
);
5839 * mas_prev_range() - Advance to the previous range
5840 * @mas: The maple state
5841 * @min: The minimum value to check.
5843 * Sets @mas->index and @mas->last to the range.
5844 * Must hold rcu_read_lock or the write lock.
5845 * Will reset mas to MAS_START if the node is MAS_NONE. Will stop on not
5848 * Return: the previous value or %NULL.
5850 void *mas_prev_range(struct ma_state
*mas
, unsigned long min
)
5854 if (mas_prev_setup(mas
, min
, &entry
))
5857 return mas_prev_slot(mas
, min
, true, true);
5859 EXPORT_SYMBOL_GPL(mas_prev_range
);
5862 * mt_prev() - get the previous value in the maple tree
5863 * @mt: The maple tree
5864 * @index: The start index
5865 * @min: The minimum index to check
5867 * Takes RCU read lock internally to protect the search, which does not
5868 * protect the returned pointer after dropping RCU read lock.
5869 * See also: Documentation/core-api/maple_tree.rst
5871 * Return: The entry before @index or %NULL if nothing is found.
5873 void *mt_prev(struct maple_tree
*mt
, unsigned long index
, unsigned long min
)
5876 MA_STATE(mas
, mt
, index
, index
);
5879 entry
= mas_prev(&mas
, min
);
5883 EXPORT_SYMBOL_GPL(mt_prev
);
5886 * mas_pause() - Pause a mas_find/mas_for_each to drop the lock.
5887 * @mas: The maple state to pause
5889 * Some users need to pause a walk and drop the lock they're holding in
5890 * order to yield to a higher priority thread or carry out an operation
5891 * on an entry. Those users should call this function before they drop
5892 * the lock. It resets the @mas to be suitable for the next iteration
5893 * of the loop after the user has reacquired the lock. If most entries
5894 * found during a walk require you to call mas_pause(), the mt_for_each()
5895 * iterator may be more appropriate.
5898 void mas_pause(struct ma_state
*mas
)
5900 mas
->node
= MAS_PAUSE
;
5902 EXPORT_SYMBOL_GPL(mas_pause
);
5905 * mas_find_setup() - Internal function to set up mas_find*().
5906 * @mas: The maple state
5907 * @max: The maximum index
5908 * @entry: Pointer to the entry
5910 * Returns: True if entry is the answer, false otherwise.
5912 static inline bool mas_find_setup(struct ma_state
*mas
, unsigned long max
,
5915 if (mas_is_active(mas
)) {
5916 if (mas
->last
< max
)
5922 if (mas_is_paused(mas
)) {
5923 if (unlikely(mas
->last
>= max
))
5926 mas
->index
= ++mas
->last
;
5927 mas
->node
= MAS_START
;
5928 } else if (mas_is_none(mas
)) {
5929 if (unlikely(mas
->last
>= max
))
5932 mas
->index
= mas
->last
;
5933 mas
->node
= MAS_START
;
5934 } else if (mas_is_overflow(mas
) || mas_is_underflow(mas
)) {
5935 if (mas
->index
> max
) {
5936 mas
->node
= MAS_OVERFLOW
;
5940 mas
->node
= MAS_START
;
5943 if (mas_is_start(mas
)) {
5944 /* First run or continue */
5945 if (mas
->index
> max
)
5948 *entry
= mas_walk(mas
);
5954 if (unlikely(!mas_searchable(mas
))) {
5955 if (unlikely(mas_is_ptr(mas
)))
5956 goto ptr_out_of_range
;
5961 if (mas
->index
== max
)
5967 mas
->node
= MAS_NONE
;
5969 mas
->last
= ULONG_MAX
;
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
)
5989 if (mas_find_setup(mas
, max
, &entry
))
5992 /* Retries on dead nodes handled by mas_next_slot */
5993 return mas_next_slot(mas
, max
, false, false);
5995 EXPORT_SYMBOL_GPL(mas_find
);
5998 * mas_find_range() - On the first call, find the entry at or after
5999 * mas->index up to %max. Otherwise, advance to the next slot mas->index.
6000 * @mas: The maple state
6001 * @max: The maximum value to check.
6003 * Must hold rcu_read_lock or the write lock.
6004 * If an entry exists, last and index are updated accordingly.
6005 * May set @mas->node to MAS_NONE.
6007 * Return: The entry or %NULL.
6009 void *mas_find_range(struct ma_state
*mas
, unsigned long max
)
6013 if (mas_find_setup(mas
, max
, &entry
))
6016 /* Retries on dead nodes handled by mas_next_slot */
6017 return mas_next_slot(mas
, max
, true, false);
6019 EXPORT_SYMBOL_GPL(mas_find_range
);
6022 * mas_find_rev_setup() - Internal function to set up mas_find_*_rev()
6023 * @mas: The maple state
6024 * @min: The minimum index
6025 * @entry: Pointer to the entry
6027 * Returns: True if entry is the answer, false otherwise.
6029 static inline bool mas_find_rev_setup(struct ma_state
*mas
, unsigned long min
,
6032 if (mas_is_active(mas
)) {
6033 if (mas
->index
> min
)
6039 if (mas_is_paused(mas
)) {
6040 if (unlikely(mas
->index
<= min
)) {
6041 mas
->node
= MAS_NONE
;
6044 mas
->node
= MAS_START
;
6045 mas
->last
= --mas
->index
;
6046 } else if (mas_is_none(mas
)) {
6047 if (mas
->index
<= min
)
6050 mas
->last
= mas
->index
;
6051 mas
->node
= MAS_START
;
6052 } else if (mas_is_underflow(mas
) || mas_is_overflow(mas
)) {
6053 if (mas
->last
<= min
) {
6054 mas
->node
= MAS_UNDERFLOW
;
6058 mas
->node
= MAS_START
;
6061 if (mas_is_start(mas
)) {
6062 /* First run or continue */
6063 if (mas
->index
< min
)
6066 *entry
= mas_walk(mas
);
6071 if (unlikely(!mas_searchable(mas
))) {
6072 if (mas_is_ptr(mas
))
6075 if (mas_is_none(mas
)) {
6077 * Walked to the location, and there was nothing so the
6078 * previous location is 0.
6080 mas
->last
= mas
->index
= 0;
6081 mas
->node
= MAS_ROOT
;
6082 *entry
= mas_root(mas
);
6087 if (mas
->index
< min
)
6093 mas
->node
= MAS_NONE
;
6098 * mas_find_rev: On the first call, find the first non-null entry at or below
6099 * mas->index down to %min. Otherwise find the first non-null entry below
6100 * mas->index down to %min.
6101 * @mas: The maple state
6102 * @min: The minimum value to check.
6104 * Must hold rcu_read_lock or the write lock.
6105 * If an entry exists, last and index are updated accordingly.
6106 * May set @mas->node to MAS_NONE.
6108 * Return: The entry or %NULL.
6110 void *mas_find_rev(struct ma_state
*mas
, unsigned long min
)
6114 if (mas_find_rev_setup(mas
, min
, &entry
))
6117 /* Retries on dead nodes handled by mas_prev_slot */
6118 return mas_prev_slot(mas
, min
, false, false);
6121 EXPORT_SYMBOL_GPL(mas_find_rev
);
6124 * mas_find_range_rev: On the first call, find the first non-null entry at or
6125 * below mas->index down to %min. Otherwise advance to the previous slot after
6126 * mas->index down to %min.
6127 * @mas: The maple state
6128 * @min: The minimum value to check.
6130 * Must hold rcu_read_lock or the write lock.
6131 * If an entry exists, last and index are updated accordingly.
6132 * May set @mas->node to MAS_NONE.
6134 * Return: The entry or %NULL.
6136 void *mas_find_range_rev(struct ma_state
*mas
, unsigned long min
)
6140 if (mas_find_rev_setup(mas
, min
, &entry
))
6143 /* Retries on dead nodes handled by mas_prev_slot */
6144 return mas_prev_slot(mas
, min
, true, false);
6146 EXPORT_SYMBOL_GPL(mas_find_range_rev
);
6149 * mas_erase() - Find the range in which index resides and erase the entire
6151 * @mas: The maple state
6153 * Must hold the write lock.
6154 * Searches for @mas->index, sets @mas->index and @mas->last to the range and
6155 * erases that range.
6157 * Return: the entry that was erased or %NULL, @mas->index and @mas->last are updated.
6159 void *mas_erase(struct ma_state
*mas
)
6162 MA_WR_STATE(wr_mas
, mas
, NULL
);
6164 if (mas_is_none(mas
) || mas_is_paused(mas
))
6165 mas
->node
= MAS_START
;
6167 /* Retry unnecessary when holding the write lock. */
6168 entry
= mas_state_walk(mas
);
6173 /* Must reset to ensure spanning writes of last slot are detected */
6175 mas_wr_store_setup(&wr_mas
);
6176 mas_wr_store_entry(&wr_mas
);
6177 if (mas_nomem(mas
, GFP_KERNEL
))
6182 EXPORT_SYMBOL_GPL(mas_erase
);
6185 * mas_nomem() - Check if there was an error allocating and do the allocation
6186 * if necessary If there are allocations, then free them.
6187 * @mas: The maple state
6188 * @gfp: The GFP_FLAGS to use for allocations
6189 * Return: true on allocation, false otherwise.
6191 bool mas_nomem(struct ma_state
*mas
, gfp_t gfp
)
6192 __must_hold(mas
->tree
->ma_lock
)
6194 if (likely(mas
->node
!= MA_ERROR(-ENOMEM
))) {
6199 if (gfpflags_allow_blocking(gfp
) && !mt_external_lock(mas
->tree
)) {
6200 mtree_unlock(mas
->tree
);
6201 mas_alloc_nodes(mas
, gfp
);
6202 mtree_lock(mas
->tree
);
6204 mas_alloc_nodes(mas
, gfp
);
6207 if (!mas_allocated(mas
))
6210 mas
->node
= MAS_START
;
6214 void __init
maple_tree_init(void)
6216 maple_node_cache
= kmem_cache_create("maple_node",
6217 sizeof(struct maple_node
), sizeof(struct maple_node
),
6222 * mtree_load() - Load a value stored in a maple tree
6223 * @mt: The maple tree
6224 * @index: The index to load
6226 * Return: the entry or %NULL
6228 void *mtree_load(struct maple_tree
*mt
, unsigned long index
)
6230 MA_STATE(mas
, mt
, index
, index
);
6233 trace_ma_read(__func__
, &mas
);
6236 entry
= mas_start(&mas
);
6237 if (unlikely(mas_is_none(&mas
)))
6240 if (unlikely(mas_is_ptr(&mas
))) {
6247 entry
= mtree_lookup_walk(&mas
);
6248 if (!entry
&& unlikely(mas_is_start(&mas
)))
6252 if (xa_is_zero(entry
))
6257 EXPORT_SYMBOL(mtree_load
);
6260 * mtree_store_range() - Store an entry at a given range.
6261 * @mt: The maple tree
6262 * @index: The start of the range
6263 * @last: The end of the range
6264 * @entry: The entry to store
6265 * @gfp: The GFP_FLAGS to use for allocations
6267 * Return: 0 on success, -EINVAL on invalid request, -ENOMEM if memory could not
6270 int mtree_store_range(struct maple_tree
*mt
, unsigned long index
,
6271 unsigned long last
, void *entry
, gfp_t gfp
)
6273 MA_STATE(mas
, mt
, index
, last
);
6274 MA_WR_STATE(wr_mas
, &mas
, entry
);
6276 trace_ma_write(__func__
, &mas
, 0, entry
);
6277 if (WARN_ON_ONCE(xa_is_advanced(entry
)))
6285 mas_wr_store_entry(&wr_mas
);
6286 if (mas_nomem(&mas
, gfp
))
6290 if (mas_is_err(&mas
))
6291 return xa_err(mas
.node
);
6295 EXPORT_SYMBOL(mtree_store_range
);
6298 * mtree_store() - Store an entry at a given index.
6299 * @mt: The maple tree
6300 * @index: The index to store the value
6301 * @entry: The entry to store
6302 * @gfp: The GFP_FLAGS to use for allocations
6304 * Return: 0 on success, -EINVAL on invalid request, -ENOMEM if memory could not
6307 int mtree_store(struct maple_tree
*mt
, unsigned long index
, void *entry
,
6310 return mtree_store_range(mt
, index
, index
, entry
, gfp
);
6312 EXPORT_SYMBOL(mtree_store
);
6315 * mtree_insert_range() - Insert an entry at a given range if there is no value.
6316 * @mt: The maple tree
6317 * @first: The start of the range
6318 * @last: The end of the range
6319 * @entry: The entry to store
6320 * @gfp: The GFP_FLAGS to use for allocations.
6322 * Return: 0 on success, -EEXISTS if the range is occupied, -EINVAL on invalid
6323 * request, -ENOMEM if memory could not be allocated.
6325 int mtree_insert_range(struct maple_tree
*mt
, unsigned long first
,
6326 unsigned long last
, void *entry
, gfp_t gfp
)
6328 MA_STATE(ms
, mt
, first
, last
);
6330 if (WARN_ON_ONCE(xa_is_advanced(entry
)))
6338 mas_insert(&ms
, entry
);
6339 if (mas_nomem(&ms
, gfp
))
6343 if (mas_is_err(&ms
))
6344 return xa_err(ms
.node
);
6348 EXPORT_SYMBOL(mtree_insert_range
);
6351 * mtree_insert() - Insert an entry at a given index if there is no value.
6352 * @mt: The maple tree
6353 * @index : The index to store the value
6354 * @entry: The entry to store
6355 * @gfp: The GFP_FLAGS to use for allocations.
6357 * Return: 0 on success, -EEXISTS if the range is occupied, -EINVAL on invalid
6358 * request, -ENOMEM if memory could not be allocated.
6360 int mtree_insert(struct maple_tree
*mt
, unsigned long index
, void *entry
,
6363 return mtree_insert_range(mt
, index
, index
, entry
, gfp
);
6365 EXPORT_SYMBOL(mtree_insert
);
6367 int mtree_alloc_range(struct maple_tree
*mt
, unsigned long *startp
,
6368 void *entry
, unsigned long size
, unsigned long min
,
6369 unsigned long max
, gfp_t gfp
)
6373 MA_STATE(mas
, mt
, 0, 0);
6374 if (!mt_is_alloc(mt
))
6377 if (WARN_ON_ONCE(mt_is_reserved(entry
)))
6382 ret
= mas_empty_area(&mas
, min
, max
, size
);
6386 mas_insert(&mas
, entry
);
6388 * mas_nomem() may release the lock, causing the allocated area
6389 * to be unavailable, so try to allocate a free area again.
6391 if (mas_nomem(&mas
, gfp
))
6394 if (mas_is_err(&mas
))
6395 ret
= xa_err(mas
.node
);
6397 *startp
= mas
.index
;
6403 EXPORT_SYMBOL(mtree_alloc_range
);
6405 int mtree_alloc_rrange(struct maple_tree
*mt
, unsigned long *startp
,
6406 void *entry
, unsigned long size
, unsigned long min
,
6407 unsigned long max
, gfp_t gfp
)
6411 MA_STATE(mas
, mt
, 0, 0);
6412 if (!mt_is_alloc(mt
))
6415 if (WARN_ON_ONCE(mt_is_reserved(entry
)))
6420 ret
= mas_empty_area_rev(&mas
, min
, max
, size
);
6424 mas_insert(&mas
, entry
);
6426 * mas_nomem() may release the lock, causing the allocated area
6427 * to be unavailable, so try to allocate a free area again.
6429 if (mas_nomem(&mas
, gfp
))
6432 if (mas_is_err(&mas
))
6433 ret
= xa_err(mas
.node
);
6435 *startp
= mas
.index
;
6441 EXPORT_SYMBOL(mtree_alloc_rrange
);
6444 * mtree_erase() - Find an index and erase the entire range.
6445 * @mt: The maple tree
6446 * @index: The index to erase
6448 * Erasing is the same as a walk to an entry then a store of a NULL to that
6449 * ENTIRE range. In fact, it is implemented as such using the advanced API.
6451 * Return: The entry stored at the @index or %NULL
6453 void *mtree_erase(struct maple_tree
*mt
, unsigned long index
)
6457 MA_STATE(mas
, mt
, index
, index
);
6458 trace_ma_op(__func__
, &mas
);
6461 entry
= mas_erase(&mas
);
6466 EXPORT_SYMBOL(mtree_erase
);
6469 * __mt_destroy() - Walk and free all nodes of a locked maple tree.
6470 * @mt: The maple tree
6472 * Note: Does not handle locking.
6474 void __mt_destroy(struct maple_tree
*mt
)
6476 void *root
= mt_root_locked(mt
);
6478 rcu_assign_pointer(mt
->ma_root
, NULL
);
6479 if (xa_is_node(root
))
6480 mte_destroy_walk(root
, mt
);
6484 EXPORT_SYMBOL_GPL(__mt_destroy
);
6487 * mtree_destroy() - Destroy a maple tree
6488 * @mt: The maple tree
6490 * Frees all resources used by the tree. Handles locking.
6492 void mtree_destroy(struct maple_tree
*mt
)
6498 EXPORT_SYMBOL(mtree_destroy
);
6501 * mt_find() - Search from the start up until an entry is found.
6502 * @mt: The maple tree
6503 * @index: Pointer which contains the start location of the search
6504 * @max: The maximum value of the search range
6506 * Takes RCU read lock internally to protect the search, which does not
6507 * protect the returned pointer after dropping RCU read lock.
6508 * See also: Documentation/core-api/maple_tree.rst
6510 * In case that an entry is found @index is updated to point to the next
6511 * possible entry independent whether the found entry is occupying a
6512 * single index or a range if indices.
6514 * Return: The entry at or after the @index or %NULL
6516 void *mt_find(struct maple_tree
*mt
, unsigned long *index
, unsigned long max
)
6518 MA_STATE(mas
, mt
, *index
, *index
);
6520 #ifdef CONFIG_DEBUG_MAPLE_TREE
6521 unsigned long copy
= *index
;
6524 trace_ma_read(__func__
, &mas
);
6531 entry
= mas_state_walk(&mas
);
6532 if (mas_is_start(&mas
))
6535 if (unlikely(xa_is_zero(entry
)))
6541 while (mas_searchable(&mas
) && (mas
.last
< max
)) {
6542 entry
= mas_next_entry(&mas
, max
);
6543 if (likely(entry
&& !xa_is_zero(entry
)))
6547 if (unlikely(xa_is_zero(entry
)))
6551 if (likely(entry
)) {
6552 *index
= mas
.last
+ 1;
6553 #ifdef CONFIG_DEBUG_MAPLE_TREE
6554 if (MT_WARN_ON(mt
, (*index
) && ((*index
) <= copy
)))
6555 pr_err("index not increased! %lx <= %lx\n",
6562 EXPORT_SYMBOL(mt_find
);
6565 * mt_find_after() - Search from the start up until an entry is found.
6566 * @mt: The maple tree
6567 * @index: Pointer which contains the start location of the search
6568 * @max: The maximum value to check
6570 * Same as mt_find() except that it checks @index for 0 before
6571 * searching. If @index == 0, the search is aborted. This covers a wrap
6572 * around of @index to 0 in an iterator loop.
6574 * Return: The entry at or after the @index or %NULL
6576 void *mt_find_after(struct maple_tree
*mt
, unsigned long *index
,
6582 return mt_find(mt
, index
, max
);
6584 EXPORT_SYMBOL(mt_find_after
);
6586 #ifdef CONFIG_DEBUG_MAPLE_TREE
6587 atomic_t maple_tree_tests_run
;
6588 EXPORT_SYMBOL_GPL(maple_tree_tests_run
);
6589 atomic_t maple_tree_tests_passed
;
6590 EXPORT_SYMBOL_GPL(maple_tree_tests_passed
);
6593 extern void kmem_cache_set_non_kernel(struct kmem_cache
*, unsigned int);
6594 void mt_set_non_kernel(unsigned int val
)
6596 kmem_cache_set_non_kernel(maple_node_cache
, val
);
6599 extern unsigned long kmem_cache_get_alloc(struct kmem_cache
*);
6600 unsigned long mt_get_alloc_size(void)
6602 return kmem_cache_get_alloc(maple_node_cache
);
6605 extern void kmem_cache_zero_nr_tallocated(struct kmem_cache
*);
6606 void mt_zero_nr_tallocated(void)
6608 kmem_cache_zero_nr_tallocated(maple_node_cache
);
6611 extern unsigned int kmem_cache_nr_tallocated(struct kmem_cache
*);
6612 unsigned int mt_nr_tallocated(void)
6614 return kmem_cache_nr_tallocated(maple_node_cache
);
6617 extern unsigned int kmem_cache_nr_allocated(struct kmem_cache
*);
6618 unsigned int mt_nr_allocated(void)
6620 return kmem_cache_nr_allocated(maple_node_cache
);
6624 * mas_dead_node() - Check if the maple state is pointing to a dead node.
6625 * @mas: The maple state
6626 * @index: The index to restore in @mas.
6628 * Used in test code.
6629 * Return: 1 if @mas has been reset to MAS_START, 0 otherwise.
6631 static inline int mas_dead_node(struct ma_state
*mas
, unsigned long index
)
6633 if (unlikely(!mas_searchable(mas
) || mas_is_start(mas
)))
6636 if (likely(!mte_dead_node(mas
->node
)))
6639 mas_rewalk(mas
, index
);
6643 void mt_cache_shrink(void)
6648 * mt_cache_shrink() - For testing, don't use this.
6650 * Certain testcases can trigger an OOM when combined with other memory
6651 * debugging configuration options. This function is used to reduce the
6652 * possibility of an out of memory even due to kmem_cache objects remaining
6653 * around for longer than usual.
6655 void mt_cache_shrink(void)
6657 kmem_cache_shrink(maple_node_cache
);
6660 EXPORT_SYMBOL_GPL(mt_cache_shrink
);
6662 #endif /* not defined __KERNEL__ */
6664 * mas_get_slot() - Get the entry in the maple state node stored at @offset.
6665 * @mas: The maple state
6666 * @offset: The offset into the slot array to fetch.
6668 * Return: The entry stored at @offset.
6670 static inline struct maple_enode
*mas_get_slot(struct ma_state
*mas
,
6671 unsigned char offset
)
6673 return mas_slot(mas
, ma_slots(mas_mn(mas
), mte_node_type(mas
->node
)),
6677 /* Depth first search, post-order */
6678 static void mas_dfs_postorder(struct ma_state
*mas
, unsigned long max
)
6681 struct maple_enode
*p
= MAS_NONE
, *mn
= mas
->node
;
6682 unsigned long p_min
, p_max
;
6684 mas_next_node(mas
, mas_mn(mas
), max
);
6685 if (!mas_is_none(mas
))
6688 if (mte_is_root(mn
))
6697 mas_prev_node(mas
, 0);
6698 } while (!mas_is_none(mas
));
6705 /* Tree validations */
6706 static void mt_dump_node(const struct maple_tree
*mt
, void *entry
,
6707 unsigned long min
, unsigned long max
, unsigned int depth
,
6708 enum mt_dump_format format
);
6709 static void mt_dump_range(unsigned long min
, unsigned long max
,
6710 unsigned int depth
, enum mt_dump_format format
)
6712 static const char spaces
[] = " ";
6717 pr_info("%.*s%lx: ", depth
* 2, spaces
, min
);
6719 pr_info("%.*s%lx-%lx: ", depth
* 2, spaces
, min
, max
);
6724 pr_info("%.*s%lu: ", depth
* 2, spaces
, min
);
6726 pr_info("%.*s%lu-%lu: ", depth
* 2, spaces
, min
, max
);
6730 static void mt_dump_entry(void *entry
, unsigned long min
, unsigned long max
,
6731 unsigned int depth
, enum mt_dump_format format
)
6733 mt_dump_range(min
, max
, depth
, format
);
6735 if (xa_is_value(entry
))
6736 pr_cont("value %ld (0x%lx) [%p]\n", xa_to_value(entry
),
6737 xa_to_value(entry
), entry
);
6738 else if (xa_is_zero(entry
))
6739 pr_cont("zero (%ld)\n", xa_to_internal(entry
));
6740 else if (mt_is_reserved(entry
))
6741 pr_cont("UNKNOWN ENTRY (%p)\n", entry
);
6743 pr_cont("%p\n", entry
);
6746 static void mt_dump_range64(const struct maple_tree
*mt
, void *entry
,
6747 unsigned long min
, unsigned long max
, unsigned int depth
,
6748 enum mt_dump_format format
)
6750 struct maple_range_64
*node
= &mte_to_node(entry
)->mr64
;
6751 bool leaf
= mte_is_leaf(entry
);
6752 unsigned long first
= min
;
6755 pr_cont(" contents: ");
6756 for (i
= 0; i
< MAPLE_RANGE64_SLOTS
- 1; i
++) {
6759 pr_cont("%p %lX ", node
->slot
[i
], node
->pivot
[i
]);
6763 pr_cont("%p %lu ", node
->slot
[i
], node
->pivot
[i
]);
6766 pr_cont("%p\n", node
->slot
[i
]);
6767 for (i
= 0; i
< MAPLE_RANGE64_SLOTS
; i
++) {
6768 unsigned long last
= max
;
6770 if (i
< (MAPLE_RANGE64_SLOTS
- 1))
6771 last
= node
->pivot
[i
];
6772 else if (!node
->slot
[i
] && max
!= mt_node_max(entry
))
6774 if (last
== 0 && i
> 0)
6777 mt_dump_entry(mt_slot(mt
, node
->slot
, i
),
6778 first
, last
, depth
+ 1, format
);
6779 else if (node
->slot
[i
])
6780 mt_dump_node(mt
, mt_slot(mt
, node
->slot
, i
),
6781 first
, last
, depth
+ 1, format
);
6788 pr_err("node %p last (%lx) > max (%lx) at pivot %d!\n",
6789 node
, last
, max
, i
);
6793 pr_err("node %p last (%lu) > max (%lu) at pivot %d!\n",
6794 node
, last
, max
, i
);
6801 static void mt_dump_arange64(const struct maple_tree
*mt
, void *entry
,
6802 unsigned long min
, unsigned long max
, unsigned int depth
,
6803 enum mt_dump_format format
)
6805 struct maple_arange_64
*node
= &mte_to_node(entry
)->ma64
;
6806 bool leaf
= mte_is_leaf(entry
);
6807 unsigned long first
= min
;
6810 pr_cont(" contents: ");
6811 for (i
= 0; i
< MAPLE_ARANGE64_SLOTS
; i
++) {
6814 pr_cont("%lx ", node
->gap
[i
]);
6818 pr_cont("%lu ", node
->gap
[i
]);
6821 pr_cont("| %02X %02X| ", node
->meta
.end
, node
->meta
.gap
);
6822 for (i
= 0; i
< MAPLE_ARANGE64_SLOTS
- 1; i
++) {
6825 pr_cont("%p %lX ", node
->slot
[i
], node
->pivot
[i
]);
6829 pr_cont("%p %lu ", node
->slot
[i
], node
->pivot
[i
]);
6832 pr_cont("%p\n", node
->slot
[i
]);
6833 for (i
= 0; i
< MAPLE_ARANGE64_SLOTS
; i
++) {
6834 unsigned long last
= max
;
6836 if (i
< (MAPLE_ARANGE64_SLOTS
- 1))
6837 last
= node
->pivot
[i
];
6838 else if (!node
->slot
[i
])
6840 if (last
== 0 && i
> 0)
6843 mt_dump_entry(mt_slot(mt
, node
->slot
, i
),
6844 first
, last
, depth
+ 1, format
);
6845 else if (node
->slot
[i
])
6846 mt_dump_node(mt
, mt_slot(mt
, node
->slot
, i
),
6847 first
, last
, depth
+ 1, format
);
6852 pr_err("node %p last (%lu) > max (%lu) at pivot %d!\n",
6853 node
, last
, max
, i
);
6860 static void mt_dump_node(const struct maple_tree
*mt
, void *entry
,
6861 unsigned long min
, unsigned long max
, unsigned int depth
,
6862 enum mt_dump_format format
)
6864 struct maple_node
*node
= mte_to_node(entry
);
6865 unsigned int type
= mte_node_type(entry
);
6868 mt_dump_range(min
, max
, depth
, format
);
6870 pr_cont("node %p depth %d type %d parent %p", node
, depth
, type
,
6871 node
? node
->parent
: NULL
);
6875 for (i
= 0; i
< MAPLE_NODE_SLOTS
; i
++) {
6877 pr_cont("OUT OF RANGE: ");
6878 mt_dump_entry(mt_slot(mt
, node
->slot
, i
),
6879 min
+ i
, min
+ i
, depth
, format
);
6883 case maple_range_64
:
6884 mt_dump_range64(mt
, entry
, min
, max
, depth
, format
);
6886 case maple_arange_64
:
6887 mt_dump_arange64(mt
, entry
, min
, max
, depth
, format
);
6891 pr_cont(" UNKNOWN TYPE\n");
6895 void mt_dump(const struct maple_tree
*mt
, enum mt_dump_format format
)
6897 void *entry
= rcu_dereference_check(mt
->ma_root
, mt_locked(mt
));
6899 pr_info("maple_tree(%p) flags %X, height %u root %p\n",
6900 mt
, mt
->ma_flags
, mt_height(mt
), entry
);
6901 if (!xa_is_node(entry
))
6902 mt_dump_entry(entry
, 0, 0, 0, format
);
6904 mt_dump_node(mt
, entry
, 0, mt_node_max(entry
), 0, format
);
6906 EXPORT_SYMBOL_GPL(mt_dump
);
6909 * Calculate the maximum gap in a node and check if that's what is reported in
6910 * the parent (unless root).
6912 static void mas_validate_gaps(struct ma_state
*mas
)
6914 struct maple_enode
*mte
= mas
->node
;
6915 struct maple_node
*p_mn
, *node
= mte_to_node(mte
);
6916 enum maple_type mt
= mte_node_type(mas
->node
);
6917 unsigned long gap
= 0, max_gap
= 0;
6918 unsigned long p_end
, p_start
= mas
->min
;
6919 unsigned char p_slot
, offset
;
6920 unsigned long *gaps
= NULL
;
6921 unsigned long *pivots
= ma_pivots(node
, mt
);
6924 if (ma_is_dense(mt
)) {
6925 for (i
= 0; i
< mt_slot_count(mte
); i
++) {
6926 if (mas_get_slot(mas
, i
)) {
6937 gaps
= ma_gaps(node
, mt
);
6938 for (i
= 0; i
< mt_slot_count(mte
); i
++) {
6939 p_end
= mas_safe_pivot(mas
, pivots
, i
, mt
);
6942 if (!mas_get_slot(mas
, i
))
6943 gap
= p_end
- p_start
+ 1;
6945 void *entry
= mas_get_slot(mas
, i
);
6948 MT_BUG_ON(mas
->tree
, !entry
);
6950 if (gap
> p_end
- p_start
+ 1) {
6951 pr_err("%p[%u] %lu >= %lu - %lu + 1 (%lu)\n",
6952 mas_mn(mas
), i
, gap
, p_end
, p_start
,
6953 p_end
- p_start
+ 1);
6954 MT_BUG_ON(mas
->tree
, gap
> p_end
- p_start
+ 1);
6961 p_start
= p_end
+ 1;
6962 if (p_end
>= mas
->max
)
6967 if (mt
== maple_arange_64
) {
6968 offset
= ma_meta_gap(node
, mt
);
6970 pr_err("gap offset %p[%u] is invalid\n", node
, offset
);
6971 MT_BUG_ON(mas
->tree
, 1);
6974 if (gaps
[offset
] != max_gap
) {
6975 pr_err("gap %p[%u] is not the largest gap %lu\n",
6976 node
, offset
, max_gap
);
6977 MT_BUG_ON(mas
->tree
, 1);
6980 MT_BUG_ON(mas
->tree
, !gaps
);
6981 for (i
++ ; i
< mt_slot_count(mte
); i
++) {
6983 pr_err("gap %p[%u] beyond node limit != 0\n",
6985 MT_BUG_ON(mas
->tree
, 1);
6990 if (mte_is_root(mte
))
6993 p_slot
= mte_parent_slot(mas
->node
);
6994 p_mn
= mte_parent(mte
);
6995 MT_BUG_ON(mas
->tree
, max_gap
> mas
->max
);
6996 if (ma_gaps(p_mn
, mas_parent_type(mas
, mte
))[p_slot
] != max_gap
) {
6997 pr_err("gap %p[%u] != %lu\n", p_mn
, p_slot
, max_gap
);
6998 mt_dump(mas
->tree
, mt_dump_hex
);
6999 MT_BUG_ON(mas
->tree
, 1);
7003 static void mas_validate_parent_slot(struct ma_state
*mas
)
7005 struct maple_node
*parent
;
7006 struct maple_enode
*node
;
7007 enum maple_type p_type
;
7008 unsigned char p_slot
;
7012 if (mte_is_root(mas
->node
))
7015 p_slot
= mte_parent_slot(mas
->node
);
7016 p_type
= mas_parent_type(mas
, mas
->node
);
7017 parent
= mte_parent(mas
->node
);
7018 slots
= ma_slots(parent
, p_type
);
7019 MT_BUG_ON(mas
->tree
, mas_mn(mas
) == parent
);
7021 /* Check prev/next parent slot for duplicate node entry */
7023 for (i
= 0; i
< mt_slots
[p_type
]; i
++) {
7024 node
= mas_slot(mas
, slots
, i
);
7026 if (node
!= mas
->node
)
7027 pr_err("parent %p[%u] does not have %p\n",
7028 parent
, i
, mas_mn(mas
));
7029 MT_BUG_ON(mas
->tree
, node
!= mas
->node
);
7030 } else if (node
== mas
->node
) {
7031 pr_err("Invalid child %p at parent %p[%u] p_slot %u\n",
7032 mas_mn(mas
), parent
, i
, p_slot
);
7033 MT_BUG_ON(mas
->tree
, node
== mas
->node
);
7038 static void mas_validate_child_slot(struct ma_state
*mas
)
7040 enum maple_type type
= mte_node_type(mas
->node
);
7041 void __rcu
**slots
= ma_slots(mte_to_node(mas
->node
), type
);
7042 unsigned long *pivots
= ma_pivots(mte_to_node(mas
->node
), type
);
7043 struct maple_enode
*child
;
7046 if (mte_is_leaf(mas
->node
))
7049 for (i
= 0; i
< mt_slots
[type
]; i
++) {
7050 child
= mas_slot(mas
, slots
, i
);
7053 pr_err("Non-leaf node lacks child at %p[%u]\n",
7055 MT_BUG_ON(mas
->tree
, 1);
7058 if (mte_parent_slot(child
) != i
) {
7059 pr_err("Slot error at %p[%u]: child %p has pslot %u\n",
7060 mas_mn(mas
), i
, mte_to_node(child
),
7061 mte_parent_slot(child
));
7062 MT_BUG_ON(mas
->tree
, 1);
7065 if (mte_parent(child
) != mte_to_node(mas
->node
)) {
7066 pr_err("child %p has parent %p not %p\n",
7067 mte_to_node(child
), mte_parent(child
),
7068 mte_to_node(mas
->node
));
7069 MT_BUG_ON(mas
->tree
, 1);
7072 if (i
< mt_pivots
[type
] && pivots
[i
] == mas
->max
)
7078 * Validate all pivots are within mas->min and mas->max, check metadata ends
7079 * where the maximum ends and ensure there is no slots or pivots set outside of
7080 * the end of the data.
7082 static void mas_validate_limits(struct ma_state
*mas
)
7085 unsigned long prev_piv
= 0;
7086 enum maple_type type
= mte_node_type(mas
->node
);
7087 void __rcu
**slots
= ma_slots(mte_to_node(mas
->node
), type
);
7088 unsigned long *pivots
= ma_pivots(mas_mn(mas
), type
);
7090 for (i
= 0; i
< mt_slots
[type
]; i
++) {
7093 piv
= mas_safe_pivot(mas
, pivots
, i
, type
);
7095 if (!piv
&& (i
!= 0)) {
7096 pr_err("Missing node limit pivot at %p[%u]",
7098 MAS_WARN_ON(mas
, 1);
7101 if (prev_piv
> piv
) {
7102 pr_err("%p[%u] piv %lu < prev_piv %lu\n",
7103 mas_mn(mas
), i
, piv
, prev_piv
);
7104 MAS_WARN_ON(mas
, piv
< prev_piv
);
7107 if (piv
< mas
->min
) {
7108 pr_err("%p[%u] %lu < %lu\n", mas_mn(mas
), i
,
7110 MAS_WARN_ON(mas
, piv
< mas
->min
);
7112 if (piv
> mas
->max
) {
7113 pr_err("%p[%u] %lu > %lu\n", mas_mn(mas
), i
,
7115 MAS_WARN_ON(mas
, piv
> mas
->max
);
7118 if (piv
== mas
->max
)
7122 if (mas_data_end(mas
) != i
) {
7123 pr_err("node%p: data_end %u != the last slot offset %u\n",
7124 mas_mn(mas
), mas_data_end(mas
), i
);
7125 MT_BUG_ON(mas
->tree
, 1);
7128 for (i
+= 1; i
< mt_slots
[type
]; i
++) {
7129 void *entry
= mas_slot(mas
, slots
, i
);
7131 if (entry
&& (i
!= mt_slots
[type
] - 1)) {
7132 pr_err("%p[%u] should not have entry %p\n", mas_mn(mas
),
7134 MT_BUG_ON(mas
->tree
, entry
!= NULL
);
7137 if (i
< mt_pivots
[type
]) {
7138 unsigned long piv
= pivots
[i
];
7143 pr_err("%p[%u] should not have piv %lu\n",
7144 mas_mn(mas
), i
, piv
);
7145 MAS_WARN_ON(mas
, i
< mt_pivots
[type
] - 1);
7150 static void mt_validate_nulls(struct maple_tree
*mt
)
7152 void *entry
, *last
= (void *)1;
7153 unsigned char offset
= 0;
7155 MA_STATE(mas
, mt
, 0, 0);
7158 if (mas_is_none(&mas
) || (mas
.node
== MAS_ROOT
))
7161 while (!mte_is_leaf(mas
.node
))
7164 slots
= ma_slots(mte_to_node(mas
.node
), mte_node_type(mas
.node
));
7166 entry
= mas_slot(&mas
, slots
, offset
);
7167 if (!last
&& !entry
) {
7168 pr_err("Sequential nulls end at %p[%u]\n",
7169 mas_mn(&mas
), offset
);
7171 MT_BUG_ON(mt
, !last
&& !entry
);
7173 if (offset
== mas_data_end(&mas
)) {
7174 mas_next_node(&mas
, mas_mn(&mas
), ULONG_MAX
);
7175 if (mas_is_none(&mas
))
7178 slots
= ma_slots(mte_to_node(mas
.node
),
7179 mte_node_type(mas
.node
));
7184 } while (!mas_is_none(&mas
));
7188 * validate a maple tree by checking:
7189 * 1. The limits (pivots are within mas->min to mas->max)
7190 * 2. The gap is correctly set in the parents
7192 void mt_validate(struct maple_tree
*mt
)
7196 MA_STATE(mas
, mt
, 0, 0);
7199 if (!mas_searchable(&mas
))
7202 while (!mte_is_leaf(mas
.node
))
7205 while (!mas_is_none(&mas
)) {
7206 MAS_WARN_ON(&mas
, mte_dead_node(mas
.node
));
7207 end
= mas_data_end(&mas
);
7208 if (MAS_WARN_ON(&mas
, (end
< mt_min_slot_count(mas
.node
)) &&
7209 (mas
.max
!= ULONG_MAX
))) {
7210 pr_err("Invalid size %u of %p\n", end
, mas_mn(&mas
));
7213 mas_validate_parent_slot(&mas
);
7214 mas_validate_limits(&mas
);
7215 mas_validate_child_slot(&mas
);
7216 if (mt_is_alloc(mt
))
7217 mas_validate_gaps(&mas
);
7218 mas_dfs_postorder(&mas
, ULONG_MAX
);
7220 mt_validate_nulls(mt
);
7225 EXPORT_SYMBOL_GPL(mt_validate
);
7227 void mas_dump(const struct ma_state
*mas
)
7229 pr_err("MAS: tree=%p enode=%p ", mas
->tree
, mas
->node
);
7230 if (mas_is_none(mas
))
7231 pr_err("(MAS_NONE) ");
7232 else if (mas_is_ptr(mas
))
7233 pr_err("(MAS_ROOT) ");
7234 else if (mas_is_start(mas
))
7235 pr_err("(MAS_START) ");
7236 else if (mas_is_paused(mas
))
7237 pr_err("(MAS_PAUSED) ");
7239 pr_err("[%u] index=%lx last=%lx\n", mas
->offset
, mas
->index
, mas
->last
);
7240 pr_err(" min=%lx max=%lx alloc=%p, depth=%u, flags=%x\n",
7241 mas
->min
, mas
->max
, mas
->alloc
, mas
->depth
, mas
->mas_flags
);
7242 if (mas
->index
> mas
->last
)
7243 pr_err("Check index & last\n");
7245 EXPORT_SYMBOL_GPL(mas_dump
);
7247 void mas_wr_dump(const struct ma_wr_state
*wr_mas
)
7249 pr_err("WR_MAS: node=%p r_min=%lx r_max=%lx\n",
7250 wr_mas
->node
, wr_mas
->r_min
, wr_mas
->r_max
);
7251 pr_err(" type=%u off_end=%u, node_end=%u, end_piv=%lx\n",
7252 wr_mas
->type
, wr_mas
->offset_end
, wr_mas
->node_end
,
7255 EXPORT_SYMBOL_GPL(mas_wr_dump
);
7257 #endif /* CONFIG_DEBUG_MAPLE_TREE */