Linux kernel mirror (for testing)
git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git
kernel
os
linux
1/* SPDX-License-Identifier: GPL-2.0+ */
2#ifndef _LINUX_MAPLE_TREE_H
3#define _LINUX_MAPLE_TREE_H
4/*
5 * Maple Tree - An RCU-safe adaptive tree for storing ranges
6 * Copyright (c) 2018-2022 Oracle
7 * Authors: Liam R. Howlett <liam@infradead.org>
8 * Matthew Wilcox <willy@infradead.org>
9 */
10
11#include <linux/kernel.h>
12#include <linux/rcupdate.h>
13#include <linux/spinlock.h>
14/* #define CONFIG_MAPLE_RCU_DISABLED */
15
16/*
17 * Allocated nodes are mutable until they have been inserted into the tree,
18 * at which time they cannot change their type until they have been removed
19 * from the tree and an RCU grace period has passed.
20 *
21 * Removed nodes have their ->parent set to point to themselves. RCU readers
22 * check ->parent before relying on the value that they loaded from the
23 * slots array. This lets us reuse the slots array for the RCU head.
24 *
25 * Nodes in the tree point to their parent unless bit 0 is set.
26 */
27#if defined(CONFIG_64BIT) || defined(BUILD_VDSO32_64)
28/* 64bit sizes */
29#define MAPLE_NODE_SLOTS 31 /* 256 bytes including ->parent */
30#define MAPLE_RANGE64_SLOTS 16 /* 256 bytes */
31#define MAPLE_ARANGE64_SLOTS 10 /* 240 bytes */
32#define MAPLE_ALLOC_SLOTS (MAPLE_NODE_SLOTS - 1)
33#else
34/* 32bit sizes */
35#define MAPLE_NODE_SLOTS 63 /* 256 bytes including ->parent */
36#define MAPLE_RANGE64_SLOTS 32 /* 256 bytes */
37#define MAPLE_ARANGE64_SLOTS 21 /* 240 bytes */
38#define MAPLE_ALLOC_SLOTS (MAPLE_NODE_SLOTS - 2)
39#endif /* defined(CONFIG_64BIT) || defined(BUILD_VDSO32_64) */
40
41#define MAPLE_NODE_MASK 255UL
42
43/*
44 * The node->parent of the root node has bit 0 set and the rest of the pointer
45 * is a pointer to the tree itself. No more bits are available in this pointer
46 * (on m68k, the data structure may only be 2-byte aligned).
47 *
48 * Internal non-root nodes can only have maple_range_* nodes as parents. The
49 * parent pointer is 256B aligned like all other tree nodes. When storing a 32
50 * or 64 bit values, the offset can fit into 4 bits. The 16 bit values need an
51 * extra bit to store the offset. This extra bit comes from a reuse of the last
52 * bit in the node type. This is possible by using bit 1 to indicate if bit 2
53 * is part of the type or the slot.
54 *
55 * Once the type is decided, the decision of an allocation range type or a
56 * range type is done by examining the immutable tree flag for the
57 * MT_FLAGS_ALLOC_RANGE flag.
58 *
59 * Node types:
60 * 0b??1 = Root
61 * 0b?00 = 16 bit nodes
62 * 0b010 = 32 bit nodes
63 * 0b110 = 64 bit nodes
64 *
65 * Slot size and location in the parent pointer:
66 * type : slot location
67 * 0b??1 : Root
68 * 0b?00 : 16 bit values, type in 0-1, slot in 2-6
69 * 0b010 : 32 bit values, type in 0-2, slot in 3-6
70 * 0b110 : 64 bit values, type in 0-2, slot in 3-6
71 */
72
73/*
74 * This metadata is used to optimize the gap updating code and in reverse
75 * searching for gaps or any other code that needs to find the end of the data.
76 */
77struct maple_metadata {
78 unsigned char end; /* end of data */
79 unsigned char gap; /* offset of largest gap */
80};
81
82/*
83 * Leaf nodes do not store pointers to nodes, they store user data. Users may
84 * store almost any bit pattern. As noted above, the optimisation of storing an
85 * entry at 0 in the root pointer cannot be done for data which have the bottom
86 * two bits set to '10'. We also reserve values with the bottom two bits set to
87 * '10' which are below 4096 (ie 2, 6, 10 .. 4094) for internal use. Some APIs
88 * return errnos as a negative errno shifted right by two bits and the bottom
89 * two bits set to '10', and while choosing to store these values in the array
90 * is not an error, it may lead to confusion if you're testing for an error with
91 * mas_is_err().
92 *
93 * Non-leaf nodes store the type of the node pointed to (enum maple_type in bits
94 * 3-6), bit 2 is reserved. That leaves bits 0-1 unused for now.
95 *
96 * In regular B-Tree terms, pivots are called keys. The term pivot is used to
97 * indicate that the tree is specifying ranges, Pivots may appear in the
98 * subtree with an entry attached to the value whereas keys are unique to a
99 * specific position of a B-tree. Pivot values are inclusive of the slot with
100 * the same index.
101 */
102
103struct maple_range_64 {
104 struct maple_pnode *parent;
105 unsigned long pivot[MAPLE_RANGE64_SLOTS - 1];
106 union {
107 void __rcu *slot[MAPLE_RANGE64_SLOTS];
108 struct {
109 void __rcu *pad[MAPLE_RANGE64_SLOTS - 1];
110 struct maple_metadata meta;
111 };
112 };
113};
114
115/*
116 * At tree creation time, the user can specify that they're willing to trade off
117 * storing fewer entries in a tree in return for storing more information in
118 * each node.
119 *
120 * The maple tree supports recording the largest range of NULL entries available
121 * in this node, also called gaps. This optimises the tree for allocating a
122 * range.
123 */
124struct maple_arange_64 {
125 struct maple_pnode *parent;
126 unsigned long pivot[MAPLE_ARANGE64_SLOTS - 1];
127 void __rcu *slot[MAPLE_ARANGE64_SLOTS];
128 unsigned long gap[MAPLE_ARANGE64_SLOTS];
129 struct maple_metadata meta;
130};
131
132struct maple_topiary {
133 struct maple_pnode *parent;
134 struct maple_enode *next; /* Overlaps the pivot */
135};
136
137enum maple_type {
138 maple_dense,
139 maple_leaf_64,
140 maple_range_64,
141 maple_arange_64,
142 maple_copy,
143};
144
145enum store_type {
146 wr_invalid,
147 wr_new_root,
148 wr_store_root,
149 wr_exact_fit,
150 wr_spanning_store,
151 wr_split_store,
152 wr_rebalance,
153 wr_append,
154 wr_node_store,
155 wr_slot_store,
156};
157
158struct maple_copy {
159 /*
160 * min, max, and pivots are values
161 * start, end, split are indexes into arrays
162 * data is a size
163 */
164
165 struct {
166 struct maple_node *node;
167 unsigned long max;
168 enum maple_type mt;
169 } dst[3];
170 struct {
171 struct maple_node *node;
172 unsigned long max;
173 unsigned char start;
174 unsigned char end;
175 enum maple_type mt;
176 } src[4];
177 /* Simulated node */
178 void __rcu *slot[3];
179 unsigned long gap[3];
180 unsigned long min;
181 union {
182 unsigned long pivot[3];
183 struct {
184 void *_pad[2];
185 unsigned long max;
186 };
187 };
188 unsigned char end;
189
190 /*Avoid passing these around */
191 unsigned char s_count;
192 unsigned char d_count;
193 unsigned char split;
194 unsigned char data;
195 unsigned char height;
196};
197
198/**
199 * DOC: Maple tree flags
200 *
201 * * MT_FLAGS_ALLOC_RANGE - Track gaps in this tree
202 * * MT_FLAGS_USE_RCU - Operate in RCU mode
203 * * MT_FLAGS_HEIGHT_OFFSET - The position of the tree height in the flags
204 * * MT_FLAGS_HEIGHT_MASK - The mask for the maple tree height value
205 * * MT_FLAGS_LOCK_MASK - How the mt_lock is used
206 * * MT_FLAGS_LOCK_IRQ - Acquired irq-safe
207 * * MT_FLAGS_LOCK_BH - Acquired bh-safe
208 * * MT_FLAGS_LOCK_EXTERN - mt_lock is not used
209 *
210 * MAPLE_HEIGHT_MAX The largest height that can be stored
211 */
212#define MT_FLAGS_ALLOC_RANGE 0x01
213#define MT_FLAGS_USE_RCU 0x02
214#define MT_FLAGS_HEIGHT_OFFSET 0x02
215#define MT_FLAGS_HEIGHT_MASK 0x7C
216#define MT_FLAGS_LOCK_MASK 0x300
217#define MT_FLAGS_LOCK_IRQ 0x100
218#define MT_FLAGS_LOCK_BH 0x200
219#define MT_FLAGS_LOCK_EXTERN 0x300
220#define MT_FLAGS_ALLOC_WRAPPED 0x0800
221
222#define MAPLE_HEIGHT_MAX 31
223
224
225#define MAPLE_NODE_TYPE_MASK 0x0F
226#define MAPLE_NODE_TYPE_SHIFT 0x03
227
228#define MAPLE_RESERVED_RANGE 4096
229
230#ifdef CONFIG_LOCKDEP
231#define mt_lock_is_held(mt) \
232 (!(mt)->ma_external_lock || lock_is_held((mt)->ma_external_lock))
233
234#define mt_write_lock_is_held(mt) \
235 (!(mt)->ma_external_lock || \
236 lock_is_held_type((mt)->ma_external_lock, 0))
237
238#define mt_set_external_lock(mt, lock) \
239 (mt)->ma_external_lock = &(lock)->dep_map
240
241#define mt_on_stack(mt) (mt).ma_external_lock = NULL
242#else
243#define mt_lock_is_held(mt) 1
244#define mt_write_lock_is_held(mt) 1
245#define mt_set_external_lock(mt, lock) do { } while (0)
246#define mt_on_stack(mt) do { } while (0)
247#endif
248
249/*
250 * If the tree contains a single entry at index 0, it is usually stored in
251 * tree->ma_root. To optimise for the page cache, an entry which ends in '00',
252 * '01' or '11' is stored in the root, but an entry which ends in '10' will be
253 * stored in a node. Bits 3-6 are used to store enum maple_type.
254 *
255 * The flags are used both to store some immutable information about this tree
256 * (set at tree creation time) and dynamic information set under the spinlock.
257 *
258 * Another use of flags are to indicate global states of the tree. This is the
259 * case with the MT_FLAGS_USE_RCU flag, which indicates the tree is currently in
260 * RCU mode. This mode was added to allow the tree to reuse nodes instead of
261 * re-allocating and RCU freeing nodes when there is a single user.
262 */
263struct maple_tree {
264 union {
265 spinlock_t ma_lock;
266#ifdef CONFIG_LOCKDEP
267 struct lockdep_map *ma_external_lock;
268#endif
269 };
270 unsigned int ma_flags;
271 void __rcu *ma_root;
272};
273
274/**
275 * MTREE_INIT() - Initialize a maple tree
276 * @name: The maple tree name
277 * @__flags: The maple tree flags
278 *
279 */
280#define MTREE_INIT(name, __flags) { \
281 .ma_lock = __SPIN_LOCK_UNLOCKED((name).ma_lock), \
282 .ma_flags = __flags, \
283 .ma_root = NULL, \
284}
285
286/**
287 * MTREE_INIT_EXT() - Initialize a maple tree with an external lock.
288 * @name: The tree name
289 * @__flags: The maple tree flags
290 * @__lock: The external lock
291 */
292#ifdef CONFIG_LOCKDEP
293#define MTREE_INIT_EXT(name, __flags, __lock) { \
294 .ma_external_lock = &(__lock).dep_map, \
295 .ma_flags = (__flags), \
296 .ma_root = NULL, \
297}
298#else
299#define MTREE_INIT_EXT(name, __flags, __lock) MTREE_INIT(name, __flags)
300#endif
301
302#define DEFINE_MTREE(name) \
303 struct maple_tree name = MTREE_INIT(name, 0)
304
305#define mtree_lock(mt) spin_lock((&(mt)->ma_lock))
306#define mtree_lock_nested(mas, subclass) \
307 spin_lock_nested((&(mt)->ma_lock), subclass)
308#define mtree_unlock(mt) spin_unlock((&(mt)->ma_lock))
309
310/*
311 * The Maple Tree squeezes various bits in at various points which aren't
312 * necessarily obvious. Usually, this is done by observing that pointers are
313 * N-byte aligned and thus the bottom log_2(N) bits are available for use. We
314 * don't use the high bits of pointers to store additional information because
315 * we don't know what bits are unused on any given architecture.
316 *
317 * Nodes are 256 bytes in size and are also aligned to 256 bytes, giving us 8
318 * low bits for our own purposes. Nodes are currently of 4 types:
319 * 1. Single pointer (Range is 0-0)
320 * 2. Non-leaf Allocation Range nodes
321 * 3. Non-leaf Range nodes
322 * 4. Leaf Range nodes All nodes consist of a number of node slots,
323 * pivots, and a parent pointer.
324 */
325
326struct maple_node {
327 union {
328 struct {
329 struct maple_pnode *parent;
330 void __rcu *slot[MAPLE_NODE_SLOTS];
331 };
332 struct {
333 void *pad;
334 struct rcu_head rcu;
335 struct maple_enode *piv_parent;
336 unsigned char parent_slot;
337 enum maple_type type;
338 unsigned char slot_len;
339 unsigned int ma_flags;
340 };
341 struct maple_range_64 mr64;
342 struct maple_arange_64 ma64;
343 struct maple_copy cp;
344 };
345};
346
347/*
348 * More complicated stores can cause two nodes to become one or three and
349 * potentially alter the height of the tree. Either half of the tree may need
350 * to be rebalanced against the other. The ma_topiary struct is used to track
351 * which nodes have been 'cut' from the tree so that the change can be done
352 * safely at a later date. This is done to support RCU.
353 */
354struct ma_topiary {
355 struct maple_enode *head;
356 struct maple_enode *tail;
357 struct maple_tree *mtree;
358};
359
360void *mtree_load(struct maple_tree *mt, unsigned long index);
361
362int mtree_insert(struct maple_tree *mt, unsigned long index,
363 void *entry, gfp_t gfp);
364int mtree_insert_range(struct maple_tree *mt, unsigned long first,
365 unsigned long last, void *entry, gfp_t gfp);
366int mtree_alloc_range(struct maple_tree *mt, unsigned long *startp,
367 void *entry, unsigned long size, unsigned long min,
368 unsigned long max, gfp_t gfp);
369int mtree_alloc_cyclic(struct maple_tree *mt, unsigned long *startp,
370 void *entry, unsigned long range_lo, unsigned long range_hi,
371 unsigned long *next, gfp_t gfp);
372int mtree_alloc_rrange(struct maple_tree *mt, unsigned long *startp,
373 void *entry, unsigned long size, unsigned long min,
374 unsigned long max, gfp_t gfp);
375
376int mtree_store_range(struct maple_tree *mt, unsigned long first,
377 unsigned long last, void *entry, gfp_t gfp);
378int mtree_store(struct maple_tree *mt, unsigned long index,
379 void *entry, gfp_t gfp);
380void *mtree_erase(struct maple_tree *mt, unsigned long index);
381
382int mtree_dup(struct maple_tree *mt, struct maple_tree *new, gfp_t gfp);
383int __mt_dup(struct maple_tree *mt, struct maple_tree *new, gfp_t gfp);
384
385void mtree_destroy(struct maple_tree *mt);
386void __mt_destroy(struct maple_tree *mt);
387
388/**
389 * mtree_empty() - Determine if a tree has any present entries.
390 * @mt: Maple Tree.
391 *
392 * Context: Any context.
393 * Return: %true if the tree contains only NULL pointers.
394 */
395static inline bool mtree_empty(const struct maple_tree *mt)
396{
397 return mt->ma_root == NULL;
398}
399
400/* Advanced API */
401
402/*
403 * Maple State Status
404 * ma_active means the maple state is pointing to a node and offset and can
405 * continue operating on the tree.
406 * ma_start means we have not searched the tree.
407 * ma_root means we have searched the tree and the entry we found lives in
408 * the root of the tree (ie it has index 0, length 1 and is the only entry in
409 * the tree).
410 * ma_none means we have searched the tree and there is no node in the
411 * tree for this entry. For example, we searched for index 1 in an empty
412 * tree. Or we have a tree which points to a full leaf node and we
413 * searched for an entry which is larger than can be contained in that
414 * leaf node.
415 * ma_pause means the data within the maple state may be stale, restart the
416 * operation
417 * ma_overflow means the search has reached the upper limit of the search
418 * ma_underflow means the search has reached the lower limit of the search
419 * ma_error means there was an error, check the node for the error number.
420 */
421enum maple_status {
422 ma_active,
423 ma_start,
424 ma_root,
425 ma_none,
426 ma_pause,
427 ma_overflow,
428 ma_underflow,
429 ma_error,
430};
431
432/*
433 * The maple state is defined in the struct ma_state and is used to keep track
434 * of information during operations, and even between operations when using the
435 * advanced API.
436 *
437 * If state->node has bit 0 set then it references a tree location which is not
438 * a node (eg the root). If bit 1 is set, the rest of the bits are a negative
439 * errno. Bit 2 (the 'unallocated slots' bit) is clear. Bits 3-6 indicate the
440 * node type.
441 *
442 * state->alloc either has a request number of nodes or an allocated node. If
443 * stat->alloc has a requested number of nodes, the first bit will be set (0x1)
444 * and the remaining bits are the value. If state->alloc is a node, then the
445 * node will be of type maple_alloc. maple_alloc has MAPLE_NODE_SLOTS - 1 for
446 * storing more allocated nodes, a total number of nodes allocated, and the
447 * node_count in this node. node_count is the number of allocated nodes in this
448 * node. The scaling beyond MAPLE_NODE_SLOTS - 1 is handled by storing further
449 * nodes into state->alloc->slot[0]'s node. Nodes are taken from state->alloc
450 * by removing a node from the state->alloc node until state->alloc->node_count
451 * is 1, when state->alloc is returned and the state->alloc->slot[0] is promoted
452 * to state->alloc. Nodes are pushed onto state->alloc by putting the current
453 * state->alloc into the pushed node's slot[0].
454 *
455 * The state also contains the implied min/max of the state->node, the depth of
456 * this search, and the offset. The implied min/max are either from the parent
457 * node or are 0-oo for the root node. The depth is incremented or decremented
458 * every time a node is walked down or up. The offset is the slot/pivot of
459 * interest in the node - either for reading or writing.
460 *
461 * When returning a value the maple state index and last respectively contain
462 * the start and end of the range for the entry. Ranges are inclusive in the
463 * Maple Tree.
464 *
465 * The status of the state is used to determine how the next action should treat
466 * the state. For instance, if the status is ma_start then the next action
467 * should start at the root of the tree and walk down. If the status is
468 * ma_pause then the node may be stale data and should be discarded. If the
469 * status is ma_overflow, then the last action hit the upper limit.
470 *
471 */
472struct ma_state {
473 struct maple_tree *tree; /* The tree we're operating in */
474 unsigned long index; /* The index we're operating on - range start */
475 unsigned long last; /* The last index we're operating on - range end */
476 struct maple_enode *node; /* The node containing this entry */
477 unsigned long min; /* The minimum index of this node - implied pivot min */
478 unsigned long max; /* The maximum index of this node - implied pivot max */
479 struct slab_sheaf *sheaf; /* Allocated nodes for this operation */
480 struct maple_node *alloc; /* A single allocated node for fast path writes */
481 unsigned long node_request; /* The number of nodes to allocate for this operation */
482 enum maple_status status; /* The status of the state (active, start, none, etc) */
483 unsigned char depth; /* depth of tree descent during write */
484 unsigned char offset;
485 unsigned char mas_flags;
486 unsigned char end; /* The end of the node */
487 enum store_type store_type; /* The type of store needed for this operation */
488};
489
490struct ma_wr_state {
491 struct ma_state *mas;
492 struct maple_node *node; /* Decoded mas->node */
493 unsigned long r_min; /* range min */
494 unsigned long r_max; /* range max */
495 enum maple_type type; /* mas->node type */
496 unsigned char offset_end; /* The offset where the write ends */
497 unsigned long *pivots; /* mas->node->pivots pointer */
498 unsigned long end_piv; /* The pivot at the offset end */
499 void __rcu **slots; /* mas->node->slots pointer */
500 void *entry; /* The entry to write */
501 void *content; /* The existing entry that is being overwritten */
502 unsigned char vacant_height; /* Height of lowest node with free space */
503 unsigned char sufficient_height;/* Height of lowest node with min sufficiency + 1 nodes */
504};
505
506#define mas_lock(mas) spin_lock(&((mas)->tree->ma_lock))
507#define mas_lock_nested(mas, subclass) \
508 spin_lock_nested(&((mas)->tree->ma_lock), subclass)
509#define mas_unlock(mas) spin_unlock(&((mas)->tree->ma_lock))
510
511/*
512 * Special values for ma_state.node.
513 * MA_ERROR represents an errno. After dropping the lock and attempting
514 * to resolve the error, the walk would have to be restarted from the
515 * top of the tree as the tree may have been modified.
516 */
517#define MA_ERROR(err) \
518 ((struct maple_enode *)(((unsigned long)err << 2) | 2UL))
519
520/*
521 * When changing MA_STATE, remember to also change rust/kernel/maple_tree.rs
522 */
523#define MA_STATE(name, mt, first, end) \
524 struct ma_state name = { \
525 .tree = mt, \
526 .index = first, \
527 .last = end, \
528 .node = NULL, \
529 .status = ma_start, \
530 .min = 0, \
531 .max = ULONG_MAX, \
532 .sheaf = NULL, \
533 .alloc = NULL, \
534 .node_request = 0, \
535 .mas_flags = 0, \
536 .store_type = wr_invalid, \
537 }
538
539#define MA_WR_STATE(name, ma_state, wr_entry) \
540 struct ma_wr_state name = { \
541 .mas = ma_state, \
542 .content = NULL, \
543 .entry = wr_entry, \
544 .vacant_height = 0, \
545 .sufficient_height = 0 \
546 }
547
548#define MA_TOPIARY(name, tree) \
549 struct ma_topiary name = { \
550 .head = NULL, \
551 .tail = NULL, \
552 .mtree = tree, \
553 }
554
555void *mas_walk(struct ma_state *mas);
556void *mas_store(struct ma_state *mas, void *entry);
557void *mas_erase(struct ma_state *mas);
558int mas_store_gfp(struct ma_state *mas, void *entry, gfp_t gfp);
559void mas_store_prealloc(struct ma_state *mas, void *entry);
560void *mas_find(struct ma_state *mas, unsigned long max);
561void *mas_find_range(struct ma_state *mas, unsigned long max);
562void *mas_find_rev(struct ma_state *mas, unsigned long min);
563void *mas_find_range_rev(struct ma_state *mas, unsigned long max);
564int mas_preallocate(struct ma_state *mas, void *entry, gfp_t gfp);
565int mas_alloc_cyclic(struct ma_state *mas, unsigned long *startp,
566 void *entry, unsigned long range_lo, unsigned long range_hi,
567 unsigned long *next, gfp_t gfp);
568
569bool mas_nomem(struct ma_state *mas, gfp_t gfp);
570void mas_pause(struct ma_state *mas);
571void maple_tree_init(void);
572void mas_destroy(struct ma_state *mas);
573
574void *mas_prev(struct ma_state *mas, unsigned long min);
575void *mas_prev_range(struct ma_state *mas, unsigned long max);
576void *mas_next(struct ma_state *mas, unsigned long max);
577void *mas_next_range(struct ma_state *mas, unsigned long max);
578
579int mas_empty_area(struct ma_state *mas, unsigned long min, unsigned long max,
580 unsigned long size);
581/*
582 * This finds an empty area from the highest address to the lowest.
583 * AKA "Topdown" version,
584 */
585int mas_empty_area_rev(struct ma_state *mas, unsigned long min,
586 unsigned long max, unsigned long size);
587
588static inline void mas_init(struct ma_state *mas, struct maple_tree *tree,
589 unsigned long addr)
590{
591 memset(mas, 0, sizeof(struct ma_state));
592 mas->tree = tree;
593 mas->index = mas->last = addr;
594 mas->max = ULONG_MAX;
595 mas->status = ma_start;
596 mas->node = NULL;
597}
598
599static inline bool mas_is_active(struct ma_state *mas)
600{
601 return mas->status == ma_active;
602}
603
604static inline bool mas_is_err(struct ma_state *mas)
605{
606 return mas->status == ma_error;
607}
608
609/**
610 * mas_reset() - Reset a Maple Tree operation state.
611 * @mas: Maple Tree operation state.
612 *
613 * Resets the error or walk state of the @mas so future walks of the
614 * array will start from the root. Use this if you have dropped the
615 * lock and want to reuse the ma_state.
616 *
617 * Context: Any context.
618 */
619static __always_inline void mas_reset(struct ma_state *mas)
620{
621 mas->status = ma_start;
622 mas->node = NULL;
623}
624
625/**
626 * mas_for_each() - Iterate over a range of the maple tree.
627 * @__mas: Maple Tree operation state (maple_state)
628 * @__entry: Entry retrieved from the tree
629 * @__max: maximum index to retrieve from the tree
630 *
631 * When returned, mas->index and mas->last will hold the entire range for the
632 * entry.
633 *
634 * Note: may return the zero entry.
635 */
636#define mas_for_each(__mas, __entry, __max) \
637 while (((__entry) = mas_find((__mas), (__max))) != NULL)
638
639/**
640 * mas_for_each_rev() - Iterate over a range of the maple tree in reverse order.
641 * @__mas: Maple Tree operation state (maple_state)
642 * @__entry: Entry retrieved from the tree
643 * @__min: minimum index to retrieve from the tree
644 *
645 * When returned, mas->index and mas->last will hold the entire range for the
646 * entry.
647 *
648 * Note: may return the zero entry.
649 */
650#define mas_for_each_rev(__mas, __entry, __min) \
651 while (((__entry) = mas_find_rev((__mas), (__min))) != NULL)
652
653#ifdef CONFIG_DEBUG_MAPLE_TREE
654enum mt_dump_format {
655 mt_dump_dec,
656 mt_dump_hex,
657};
658
659extern atomic_t maple_tree_tests_run;
660extern atomic_t maple_tree_tests_passed;
661
662void mt_dump(const struct maple_tree *mt, enum mt_dump_format format);
663void mas_dump(const struct ma_state *mas);
664void mas_wr_dump(const struct ma_wr_state *wr_mas);
665void mt_validate(struct maple_tree *mt);
666void mt_cache_shrink(void);
667#define MT_BUG_ON(__tree, __x) do { \
668 atomic_inc(&maple_tree_tests_run); \
669 if (__x) { \
670 pr_info("BUG at %s:%d (%u)\n", \
671 __func__, __LINE__, __x); \
672 mt_dump(__tree, mt_dump_hex); \
673 pr_info("Pass: %u Run:%u\n", \
674 atomic_read(&maple_tree_tests_passed), \
675 atomic_read(&maple_tree_tests_run)); \
676 dump_stack(); \
677 } else { \
678 atomic_inc(&maple_tree_tests_passed); \
679 } \
680} while (0)
681
682#define MAS_BUG_ON(__mas, __x) do { \
683 atomic_inc(&maple_tree_tests_run); \
684 if (__x) { \
685 pr_info("BUG at %s:%d (%u)\n", \
686 __func__, __LINE__, __x); \
687 mas_dump(__mas); \
688 mt_dump((__mas)->tree, mt_dump_hex); \
689 pr_info("Pass: %u Run:%u\n", \
690 atomic_read(&maple_tree_tests_passed), \
691 atomic_read(&maple_tree_tests_run)); \
692 dump_stack(); \
693 } else { \
694 atomic_inc(&maple_tree_tests_passed); \
695 } \
696} while (0)
697
698#define MAS_WR_BUG_ON(__wrmas, __x) do { \
699 atomic_inc(&maple_tree_tests_run); \
700 if (__x) { \
701 pr_info("BUG at %s:%d (%u)\n", \
702 __func__, __LINE__, __x); \
703 mas_wr_dump(__wrmas); \
704 mas_dump((__wrmas)->mas); \
705 mt_dump((__wrmas)->mas->tree, mt_dump_hex); \
706 pr_info("Pass: %u Run:%u\n", \
707 atomic_read(&maple_tree_tests_passed), \
708 atomic_read(&maple_tree_tests_run)); \
709 dump_stack(); \
710 } else { \
711 atomic_inc(&maple_tree_tests_passed); \
712 } \
713} while (0)
714
715#define MT_WARN_ON(__tree, __x) ({ \
716 int ret = !!(__x); \
717 atomic_inc(&maple_tree_tests_run); \
718 if (ret) { \
719 pr_info("WARN at %s:%d (%u)\n", \
720 __func__, __LINE__, __x); \
721 mt_dump(__tree, mt_dump_hex); \
722 pr_info("Pass: %u Run:%u\n", \
723 atomic_read(&maple_tree_tests_passed), \
724 atomic_read(&maple_tree_tests_run)); \
725 dump_stack(); \
726 } else { \
727 atomic_inc(&maple_tree_tests_passed); \
728 } \
729 unlikely(ret); \
730})
731
732#define MAS_WARN_ON(__mas, __x) ({ \
733 int ret = !!(__x); \
734 atomic_inc(&maple_tree_tests_run); \
735 if (ret) { \
736 pr_info("WARN at %s:%d (%u)\n", \
737 __func__, __LINE__, __x); \
738 mas_dump(__mas); \
739 mt_dump((__mas)->tree, mt_dump_hex); \
740 pr_info("Pass: %u Run:%u\n", \
741 atomic_read(&maple_tree_tests_passed), \
742 atomic_read(&maple_tree_tests_run)); \
743 dump_stack(); \
744 } else { \
745 atomic_inc(&maple_tree_tests_passed); \
746 } \
747 unlikely(ret); \
748})
749
750#define MAS_WR_WARN_ON(__wrmas, __x) ({ \
751 int ret = !!(__x); \
752 atomic_inc(&maple_tree_tests_run); \
753 if (ret) { \
754 pr_info("WARN at %s:%d (%u)\n", \
755 __func__, __LINE__, __x); \
756 mas_wr_dump(__wrmas); \
757 mas_dump((__wrmas)->mas); \
758 mt_dump((__wrmas)->mas->tree, mt_dump_hex); \
759 pr_info("Pass: %u Run:%u\n", \
760 atomic_read(&maple_tree_tests_passed), \
761 atomic_read(&maple_tree_tests_run)); \
762 dump_stack(); \
763 } else { \
764 atomic_inc(&maple_tree_tests_passed); \
765 } \
766 unlikely(ret); \
767})
768#else
769#define MT_BUG_ON(__tree, __x) BUG_ON(__x)
770#define MAS_BUG_ON(__mas, __x) BUG_ON(__x)
771#define MAS_WR_BUG_ON(__mas, __x) BUG_ON(__x)
772#define MT_WARN_ON(__tree, __x) WARN_ON(__x)
773#define MAS_WARN_ON(__mas, __x) WARN_ON(__x)
774#define MAS_WR_WARN_ON(__mas, __x) WARN_ON(__x)
775#endif /* CONFIG_DEBUG_MAPLE_TREE */
776
777/**
778 * __mas_set_range() - Set up Maple Tree operation state to a sub-range of the
779 * current location.
780 * @mas: Maple Tree operation state.
781 * @start: New start of range in the Maple Tree.
782 * @last: New end of range in the Maple Tree.
783 *
784 * set the internal maple state values to a sub-range.
785 * Please use mas_set_range() if you do not know where you are in the tree.
786 */
787static inline void __mas_set_range(struct ma_state *mas, unsigned long start,
788 unsigned long last)
789{
790 /* Ensure the range starts within the current slot */
791 MAS_WARN_ON(mas, mas_is_active(mas) &&
792 (mas->index > start || mas->last < start));
793 mas->index = start;
794 mas->last = last;
795}
796
797/**
798 * mas_set_range() - Set up Maple Tree operation state for a different index.
799 * @mas: Maple Tree operation state.
800 * @start: New start of range in the Maple Tree.
801 * @last: New end of range in the Maple Tree.
802 *
803 * Move the operation state to refer to a different range. This will
804 * have the effect of starting a walk from the top; see mas_next()
805 * to move to an adjacent index.
806 */
807static inline
808void mas_set_range(struct ma_state *mas, unsigned long start, unsigned long last)
809{
810 mas_reset(mas);
811 __mas_set_range(mas, start, last);
812}
813
814/**
815 * mas_set() - Set up Maple Tree operation state for a different index.
816 * @mas: Maple Tree operation state.
817 * @index: New index into the Maple Tree.
818 *
819 * Move the operation state to refer to a different index. This will
820 * have the effect of starting a walk from the top; see mas_next()
821 * to move to an adjacent index.
822 */
823static inline void mas_set(struct ma_state *mas, unsigned long index)
824{
825
826 mas_set_range(mas, index, index);
827}
828
829static inline bool mt_external_lock(const struct maple_tree *mt)
830{
831 return (mt->ma_flags & MT_FLAGS_LOCK_MASK) == MT_FLAGS_LOCK_EXTERN;
832}
833
834/**
835 * mt_init_flags() - Initialise an empty maple tree with flags.
836 * @mt: Maple Tree
837 * @flags: maple tree flags.
838 *
839 * If you need to initialise a Maple Tree with special flags (eg, an
840 * allocation tree), use this function.
841 *
842 * Context: Any context.
843 */
844static inline void mt_init_flags(struct maple_tree *mt, unsigned int flags)
845{
846 mt->ma_flags = flags;
847 if (!mt_external_lock(mt))
848 spin_lock_init(&mt->ma_lock);
849 rcu_assign_pointer(mt->ma_root, NULL);
850}
851
852/**
853 * mt_init() - Initialise an empty maple tree.
854 * @mt: Maple Tree
855 *
856 * An empty Maple Tree.
857 *
858 * Context: Any context.
859 */
860static inline void mt_init(struct maple_tree *mt)
861{
862 mt_init_flags(mt, 0);
863}
864
865static inline bool mt_in_rcu(struct maple_tree *mt)
866{
867#ifdef CONFIG_MAPLE_RCU_DISABLED
868 return false;
869#endif
870 return mt->ma_flags & MT_FLAGS_USE_RCU;
871}
872
873/**
874 * mt_clear_in_rcu() - Switch the tree to non-RCU mode.
875 * @mt: The Maple Tree
876 */
877static inline void mt_clear_in_rcu(struct maple_tree *mt)
878{
879 if (!mt_in_rcu(mt))
880 return;
881
882 if (mt_external_lock(mt)) {
883 WARN_ON(!mt_lock_is_held(mt));
884 mt->ma_flags &= ~MT_FLAGS_USE_RCU;
885 } else {
886 mtree_lock(mt);
887 mt->ma_flags &= ~MT_FLAGS_USE_RCU;
888 mtree_unlock(mt);
889 }
890}
891
892/**
893 * mt_set_in_rcu() - Switch the tree to RCU safe mode.
894 * @mt: The Maple Tree
895 */
896static inline void mt_set_in_rcu(struct maple_tree *mt)
897{
898 if (mt_in_rcu(mt))
899 return;
900
901 if (mt_external_lock(mt)) {
902 WARN_ON(!mt_lock_is_held(mt));
903 mt->ma_flags |= MT_FLAGS_USE_RCU;
904 } else {
905 mtree_lock(mt);
906 mt->ma_flags |= MT_FLAGS_USE_RCU;
907 mtree_unlock(mt);
908 }
909}
910
911static inline unsigned int mt_height(const struct maple_tree *mt)
912{
913 return (mt->ma_flags & MT_FLAGS_HEIGHT_MASK) >> MT_FLAGS_HEIGHT_OFFSET;
914}
915
916void *mt_find(struct maple_tree *mt, unsigned long *index, unsigned long max);
917void *mt_find_after(struct maple_tree *mt, unsigned long *index,
918 unsigned long max);
919void *mt_prev(struct maple_tree *mt, unsigned long index, unsigned long min);
920void *mt_next(struct maple_tree *mt, unsigned long index, unsigned long max);
921
922/**
923 * mt_for_each - Iterate over each entry starting at index until max.
924 * @__tree: The Maple Tree
925 * @__entry: The current entry
926 * @__index: The index to start the search from. Subsequently used as iterator.
927 * @__max: The maximum limit for @index
928 *
929 * This iterator skips all entries, which resolve to a NULL pointer,
930 * e.g. entries which has been reserved with XA_ZERO_ENTRY.
931 */
932#define mt_for_each(__tree, __entry, __index, __max) \
933 for (__entry = mt_find(__tree, &(__index), __max); \
934 __entry; __entry = mt_find_after(__tree, &(__index), __max))
935
936#endif /*_LINUX_MAPLE_TREE_H */