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