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