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