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.Howlett@Oracle.com>
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 range
56  * type is done by examining the immutable tree flag for the MAPLE_ALLOC_RANGE
57  * flag.
58  *
59  *  Node types:
60  *   0x??1 = Root
61  *   0x?00 = 16 bit nodes
62  *   0x010 = 32 bit nodes
63  *   0x110 = 64 bit nodes
64  *
65  *  Slot size and location in the parent pointer:
66  *   type  : slot location
67  *   0x??1 : Root
68  *   0x?00 : 16 bit values, type in 0-1, slot in 2-6
69  *   0x010 : 32 bit values, type in 0-2, slot in 3-6
70  *   0x110 : 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  */
77 struct maple_metadata {
78 	unsigned char end;
79 	unsigned char 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 
103 struct 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  */
124 struct 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 
132 struct maple_alloc {
133 	unsigned long total;
134 	unsigned char node_count;
135 	unsigned int request_count;
136 	struct maple_alloc *slot[MAPLE_ALLOC_SLOTS];
137 };
138 
139 struct maple_topiary {
140 	struct maple_pnode *parent;
141 	struct maple_enode *next; /* Overlaps the pivot */
142 };
143 
144 enum maple_type {
145 	maple_dense,
146 	maple_leaf_64,
147 	maple_range_64,
148 	maple_arange_64,
149 };
150 
151 
152 /**
153  * DOC: Maple tree flags
154  *
155  * * MT_FLAGS_ALLOC_RANGE	- Track gaps in this tree
156  * * MT_FLAGS_USE_RCU		- Operate in RCU mode
157  * * MT_FLAGS_HEIGHT_OFFSET	- The position of the tree height in the flags
158  * * MT_FLAGS_HEIGHT_MASK	- The mask for the maple tree height value
159  * * MT_FLAGS_LOCK_MASK		- How the mt_lock is used
160  * * MT_FLAGS_LOCK_IRQ		- Acquired irq-safe
161  * * MT_FLAGS_LOCK_BH		- Acquired bh-safe
162  * * MT_FLAGS_LOCK_EXTERN	- mt_lock is not used
163  *
164  * MAPLE_HEIGHT_MAX	The largest height that can be stored
165  */
166 #define MT_FLAGS_ALLOC_RANGE	0x01
167 #define MT_FLAGS_USE_RCU	0x02
168 #define MT_FLAGS_HEIGHT_OFFSET	0x02
169 #define MT_FLAGS_HEIGHT_MASK	0x7C
170 #define MT_FLAGS_LOCK_MASK	0x300
171 #define MT_FLAGS_LOCK_IRQ	0x100
172 #define MT_FLAGS_LOCK_BH	0x200
173 #define MT_FLAGS_LOCK_EXTERN	0x300
174 
175 #define MAPLE_HEIGHT_MAX	31
176 
177 
178 #define MAPLE_NODE_TYPE_MASK	0x0F
179 #define MAPLE_NODE_TYPE_SHIFT	0x03
180 
181 #define MAPLE_RESERVED_RANGE	4096
182 
183 #ifdef CONFIG_LOCKDEP
184 typedef struct lockdep_map *lockdep_map_p;
185 #define mt_lock_is_held(mt)                                             \
186 	(!(mt)->ma_external_lock || lock_is_held((mt)->ma_external_lock))
187 
188 #define mt_write_lock_is_held(mt)					\
189 	(!(mt)->ma_external_lock ||					\
190 	 lock_is_held_type((mt)->ma_external_lock, 0))
191 
192 #define mt_set_external_lock(mt, lock)					\
193 	(mt)->ma_external_lock = &(lock)->dep_map
194 
195 #define mt_on_stack(mt)			(mt).ma_external_lock = NULL
196 #else
197 typedef struct { /* nothing */ } lockdep_map_p;
198 #define mt_lock_is_held(mt)		1
199 #define mt_write_lock_is_held(mt)	1
200 #define mt_set_external_lock(mt, lock)	do { } while (0)
201 #define mt_on_stack(mt)			do { } while (0)
202 #endif
203 
204 /*
205  * If the tree contains a single entry at index 0, it is usually stored in
206  * tree->ma_root.  To optimise for the page cache, an entry which ends in '00',
207  * '01' or '11' is stored in the root, but an entry which ends in '10' will be
208  * stored in a node.  Bits 3-6 are used to store enum maple_type.
209  *
210  * The flags are used both to store some immutable information about this tree
211  * (set at tree creation time) and dynamic information set under the spinlock.
212  *
213  * Another use of flags are to indicate global states of the tree.  This is the
214  * case with the MAPLE_USE_RCU flag, which indicates the tree is currently in
215  * RCU mode.  This mode was added to allow the tree to reuse nodes instead of
216  * re-allocating and RCU freeing nodes when there is a single user.
217  */
218 struct maple_tree {
219 	union {
220 		spinlock_t	ma_lock;
221 		lockdep_map_p	ma_external_lock;
222 	};
223 	unsigned int	ma_flags;
224 	void __rcu      *ma_root;
225 };
226 
227 /**
228  * MTREE_INIT() - Initialize a maple tree
229  * @name: The maple tree name
230  * @__flags: The maple tree flags
231  *
232  */
233 #define MTREE_INIT(name, __flags) {					\
234 	.ma_lock = __SPIN_LOCK_UNLOCKED((name).ma_lock),		\
235 	.ma_flags = __flags,						\
236 	.ma_root = NULL,						\
237 }
238 
239 /**
240  * MTREE_INIT_EXT() - Initialize a maple tree with an external lock.
241  * @name: The tree name
242  * @__flags: The maple tree flags
243  * @__lock: The external lock
244  */
245 #ifdef CONFIG_LOCKDEP
246 #define MTREE_INIT_EXT(name, __flags, __lock) {				\
247 	.ma_external_lock = &(__lock).dep_map,				\
248 	.ma_flags = (__flags),						\
249 	.ma_root = NULL,						\
250 }
251 #else
252 #define MTREE_INIT_EXT(name, __flags, __lock)	MTREE_INIT(name, __flags)
253 #endif
254 
255 #define DEFINE_MTREE(name)						\
256 	struct maple_tree name = MTREE_INIT(name, 0)
257 
258 #define mtree_lock(mt)		spin_lock((&(mt)->ma_lock))
259 #define mtree_unlock(mt)	spin_unlock((&(mt)->ma_lock))
260 
261 /*
262  * The Maple Tree squeezes various bits in at various points which aren't
263  * necessarily obvious.  Usually, this is done by observing that pointers are
264  * N-byte aligned and thus the bottom log_2(N) bits are available for use.  We
265  * don't use the high bits of pointers to store additional information because
266  * we don't know what bits are unused on any given architecture.
267  *
268  * Nodes are 256 bytes in size and are also aligned to 256 bytes, giving us 8
269  * low bits for our own purposes.  Nodes are currently of 4 types:
270  * 1. Single pointer (Range is 0-0)
271  * 2. Non-leaf Allocation Range nodes
272  * 3. Non-leaf Range nodes
273  * 4. Leaf Range nodes All nodes consist of a number of node slots,
274  *    pivots, and a parent pointer.
275  */
276 
277 struct maple_node {
278 	union {
279 		struct {
280 			struct maple_pnode *parent;
281 			void __rcu *slot[MAPLE_NODE_SLOTS];
282 		};
283 		struct {
284 			void *pad;
285 			struct rcu_head rcu;
286 			struct maple_enode *piv_parent;
287 			unsigned char parent_slot;
288 			enum maple_type type;
289 			unsigned char slot_len;
290 			unsigned int ma_flags;
291 		};
292 		struct maple_range_64 mr64;
293 		struct maple_arange_64 ma64;
294 		struct maple_alloc alloc;
295 	};
296 };
297 
298 /*
299  * More complicated stores can cause two nodes to become one or three and
300  * potentially alter the height of the tree.  Either half of the tree may need
301  * to be rebalanced against the other.  The ma_topiary struct is used to track
302  * which nodes have been 'cut' from the tree so that the change can be done
303  * safely at a later date.  This is done to support RCU.
304  */
305 struct ma_topiary {
306 	struct maple_enode *head;
307 	struct maple_enode *tail;
308 	struct maple_tree *mtree;
309 };
310 
311 void *mtree_load(struct maple_tree *mt, unsigned long index);
312 
313 int mtree_insert(struct maple_tree *mt, unsigned long index,
314 		void *entry, gfp_t gfp);
315 int mtree_insert_range(struct maple_tree *mt, unsigned long first,
316 		unsigned long last, void *entry, gfp_t gfp);
317 int mtree_alloc_range(struct maple_tree *mt, unsigned long *startp,
318 		void *entry, unsigned long size, unsigned long min,
319 		unsigned long max, gfp_t gfp);
320 int mtree_alloc_rrange(struct maple_tree *mt, unsigned long *startp,
321 		void *entry, unsigned long size, unsigned long min,
322 		unsigned long max, gfp_t gfp);
323 
324 int mtree_store_range(struct maple_tree *mt, unsigned long first,
325 		      unsigned long last, void *entry, gfp_t gfp);
326 int mtree_store(struct maple_tree *mt, unsigned long index,
327 		void *entry, gfp_t gfp);
328 void *mtree_erase(struct maple_tree *mt, unsigned long index);
329 
330 void mtree_destroy(struct maple_tree *mt);
331 void __mt_destroy(struct maple_tree *mt);
332 
333 /**
334  * mtree_empty() - Determine if a tree has any present entries.
335  * @mt: Maple Tree.
336  *
337  * Context: Any context.
338  * Return: %true if the tree contains only NULL pointers.
339  */
mtree_empty(const struct maple_tree * mt)340 static inline bool mtree_empty(const struct maple_tree *mt)
341 {
342 	return mt->ma_root == NULL;
343 }
344 
345 /* Advanced API */
346 
347 /*
348  * The maple state is defined in the struct ma_state and is used to keep track
349  * of information during operations, and even between operations when using the
350  * advanced API.
351  *
352  * If state->node has bit 0 set then it references a tree location which is not
353  * a node (eg the root).  If bit 1 is set, the rest of the bits are a negative
354  * errno.  Bit 2 (the 'unallocated slots' bit) is clear.  Bits 3-6 indicate the
355  * node type.
356  *
357  * state->alloc either has a request number of nodes or an allocated node.  If
358  * stat->alloc has a requested number of nodes, the first bit will be set (0x1)
359  * and the remaining bits are the value.  If state->alloc is a node, then the
360  * node will be of type maple_alloc.  maple_alloc has MAPLE_NODE_SLOTS - 1 for
361  * storing more allocated nodes, a total number of nodes allocated, and the
362  * node_count in this node.  node_count is the number of allocated nodes in this
363  * node.  The scaling beyond MAPLE_NODE_SLOTS - 1 is handled by storing further
364  * nodes into state->alloc->slot[0]'s node.  Nodes are taken from state->alloc
365  * by removing a node from the state->alloc node until state->alloc->node_count
366  * is 1, when state->alloc is returned and the state->alloc->slot[0] is promoted
367  * to state->alloc.  Nodes are pushed onto state->alloc by putting the current
368  * state->alloc into the pushed node's slot[0].
369  *
370  * The state also contains the implied min/max of the state->node, the depth of
371  * this search, and the offset. The implied min/max are either from the parent
372  * node or are 0-oo for the root node.  The depth is incremented or decremented
373  * every time a node is walked down or up.  The offset is the slot/pivot of
374  * interest in the node - either for reading or writing.
375  *
376  * When returning a value the maple state index and last respectively contain
377  * the start and end of the range for the entry.  Ranges are inclusive in the
378  * Maple Tree.
379  */
380 struct ma_state {
381 	struct maple_tree *tree;	/* The tree we're operating in */
382 	unsigned long index;		/* The index we're operating on - range start */
383 	unsigned long last;		/* The last index we're operating on - range end */
384 	struct maple_enode *node;	/* The node containing this entry */
385 	unsigned long min;		/* The minimum index of this node - implied pivot min */
386 	unsigned long max;		/* The maximum index of this node - implied pivot max */
387 	struct maple_alloc *alloc;	/* Allocated nodes for this operation */
388 	unsigned char depth;		/* depth of tree descent during write */
389 	unsigned char offset;
390 	unsigned char mas_flags;
391 };
392 
393 struct ma_wr_state {
394 	struct ma_state *mas;
395 	struct maple_node *node;	/* Decoded mas->node */
396 	unsigned long r_min;		/* range min */
397 	unsigned long r_max;		/* range max */
398 	enum maple_type type;		/* mas->node type */
399 	unsigned char offset_end;	/* The offset where the write ends */
400 	unsigned char node_end;		/* mas->node end */
401 	unsigned long *pivots;		/* mas->node->pivots pointer */
402 	unsigned long end_piv;		/* The pivot at the offset end */
403 	void __rcu **slots;		/* mas->node->slots pointer */
404 	void *entry;			/* The entry to write */
405 	void *content;			/* The existing entry that is being overwritten */
406 };
407 
408 #define mas_lock(mas)           spin_lock(&((mas)->tree->ma_lock))
409 #define mas_unlock(mas)         spin_unlock(&((mas)->tree->ma_lock))
410 
411 
412 /*
413  * Special values for ma_state.node.
414  * MAS_START means we have not searched the tree.
415  * MAS_ROOT means we have searched the tree and the entry we found lives in
416  * the root of the tree (ie it has index 0, length 1 and is the only entry in
417  * the tree).
418  * MAS_NONE means we have searched the tree and there is no node in the
419  * tree for this entry.  For example, we searched for index 1 in an empty
420  * tree.  Or we have a tree which points to a full leaf node and we
421  * searched for an entry which is larger than can be contained in that
422  * leaf node.
423  * MA_ERROR represents an errno.  After dropping the lock and attempting
424  * to resolve the error, the walk would have to be restarted from the
425  * top of the tree as the tree may have been modified.
426  */
427 #define MAS_START	((struct maple_enode *)1UL)
428 #define MAS_ROOT	((struct maple_enode *)5UL)
429 #define MAS_NONE	((struct maple_enode *)9UL)
430 #define MAS_PAUSE	((struct maple_enode *)17UL)
431 #define MAS_OVERFLOW	((struct maple_enode *)33UL)
432 #define MAS_UNDERFLOW	((struct maple_enode *)65UL)
433 #define MA_ERROR(err) \
434 		((struct maple_enode *)(((unsigned long)err << 2) | 2UL))
435 
436 #define MA_STATE(name, mt, first, end)					\
437 	struct ma_state name = {					\
438 		.tree = mt,						\
439 		.index = first,						\
440 		.last = end,						\
441 		.node = MAS_START,					\
442 		.min = 0,						\
443 		.max = ULONG_MAX,					\
444 		.alloc = NULL,						\
445 		.mas_flags = 0,						\
446 	}
447 
448 #define MA_WR_STATE(name, ma_state, wr_entry)				\
449 	struct ma_wr_state name = {					\
450 		.mas = ma_state,					\
451 		.content = NULL,					\
452 		.entry = wr_entry,					\
453 	}
454 
455 #define MA_TOPIARY(name, tree)						\
456 	struct ma_topiary name = {					\
457 		.head = NULL,						\
458 		.tail = NULL,						\
459 		.mtree = tree,						\
460 	}
461 
462 void *mas_walk(struct ma_state *mas);
463 void *mas_store(struct ma_state *mas, void *entry);
464 void *mas_erase(struct ma_state *mas);
465 int mas_store_gfp(struct ma_state *mas, void *entry, gfp_t gfp);
466 void mas_store_prealloc(struct ma_state *mas, void *entry);
467 void *mas_find(struct ma_state *mas, unsigned long max);
468 void *mas_find_range(struct ma_state *mas, unsigned long max);
469 void *mas_find_rev(struct ma_state *mas, unsigned long min);
470 void *mas_find_range_rev(struct ma_state *mas, unsigned long max);
471 int mas_preallocate(struct ma_state *mas, void *entry, gfp_t gfp);
472 bool mas_is_err(struct ma_state *mas);
473 
474 bool mas_nomem(struct ma_state *mas, gfp_t gfp);
475 void mas_pause(struct ma_state *mas);
476 void maple_tree_init(void);
477 void mas_destroy(struct ma_state *mas);
478 int mas_expected_entries(struct ma_state *mas, unsigned long nr_entries);
479 
480 void *mas_prev(struct ma_state *mas, unsigned long min);
481 void *mas_prev_range(struct ma_state *mas, unsigned long max);
482 void *mas_next(struct ma_state *mas, unsigned long max);
483 void *mas_next_range(struct ma_state *mas, unsigned long max);
484 
485 int mas_empty_area(struct ma_state *mas, unsigned long min, unsigned long max,
486 		   unsigned long size);
487 /*
488  * This finds an empty area from the highest address to the lowest.
489  * AKA "Topdown" version,
490  */
491 int mas_empty_area_rev(struct ma_state *mas, unsigned long min,
492 		       unsigned long max, unsigned long size);
493 
mas_init(struct ma_state * mas,struct maple_tree * tree,unsigned long addr)494 static inline void mas_init(struct ma_state *mas, struct maple_tree *tree,
495 			    unsigned long addr)
496 {
497 	memset(mas, 0, sizeof(struct ma_state));
498 	mas->tree = tree;
499 	mas->index = mas->last = addr;
500 	mas->max = ULONG_MAX;
501 	mas->node = MAS_START;
502 }
503 
504 /* Checks if a mas has not found anything */
mas_is_none(const struct ma_state * mas)505 static inline bool mas_is_none(const struct ma_state *mas)
506 {
507 	return mas->node == MAS_NONE;
508 }
509 
510 /* Checks if a mas has been paused */
mas_is_paused(const struct ma_state * mas)511 static inline bool mas_is_paused(const struct ma_state *mas)
512 {
513 	return mas->node == MAS_PAUSE;
514 }
515 
516 /* Check if the mas is pointing to a node or not */
mas_is_active(struct ma_state * mas)517 static inline bool mas_is_active(struct ma_state *mas)
518 {
519 	if ((unsigned long)mas->node >= MAPLE_RESERVED_RANGE)
520 		return true;
521 
522 	return false;
523 }
524 
525 /**
526  * mas_reset() - Reset a Maple Tree operation state.
527  * @mas: Maple Tree operation state.
528  *
529  * Resets the error or walk state of the @mas so future walks of the
530  * array will start from the root.  Use this if you have dropped the
531  * lock and want to reuse the ma_state.
532  *
533  * Context: Any context.
534  */
mas_reset(struct ma_state * mas)535 static inline void mas_reset(struct ma_state *mas)
536 {
537 	mas->node = MAS_START;
538 }
539 
540 /**
541  * mas_for_each() - Iterate over a range of the maple tree.
542  * @__mas: Maple Tree operation state (maple_state)
543  * @__entry: Entry retrieved from the tree
544  * @__max: maximum index to retrieve from the tree
545  *
546  * When returned, mas->index and mas->last will hold the entire range for the
547  * entry.
548  *
549  * Note: may return the zero entry.
550  */
551 #define mas_for_each(__mas, __entry, __max) \
552 	while (((__entry) = mas_find((__mas), (__max))) != NULL)
553 /**
554  * __mas_set_range() - Set up Maple Tree operation state to a sub-range of the
555  * current location.
556  * @mas: Maple Tree operation state.
557  * @start: New start of range in the Maple Tree.
558  * @last: New end of range in the Maple Tree.
559  *
560  * set the internal maple state values to a sub-range.
561  * Please use mas_set_range() if you do not know where you are in the tree.
562  */
__mas_set_range(struct ma_state * mas,unsigned long start,unsigned long last)563 static inline void __mas_set_range(struct ma_state *mas, unsigned long start,
564 		unsigned long last)
565 {
566 	mas->index = start;
567 	mas->last = last;
568 }
569 
570 /**
571  * mas_set_range() - Set up Maple Tree operation state for a different index.
572  * @mas: Maple Tree operation state.
573  * @start: New start of range in the Maple Tree.
574  * @last: New end of range in the Maple Tree.
575  *
576  * Move the operation state to refer to a different range.  This will
577  * have the effect of starting a walk from the top; see mas_next()
578  * to move to an adjacent index.
579  */
580 static inline
mas_set_range(struct ma_state * mas,unsigned long start,unsigned long last)581 void mas_set_range(struct ma_state *mas, unsigned long start, unsigned long last)
582 {
583 	__mas_set_range(mas, start, last);
584 	mas->node = MAS_START;
585 }
586 
587 /**
588  * mas_set() - Set up Maple Tree operation state for a different index.
589  * @mas: Maple Tree operation state.
590  * @index: New index into the Maple Tree.
591  *
592  * Move the operation state to refer to a different index.  This will
593  * have the effect of starting a walk from the top; see mas_next()
594  * to move to an adjacent index.
595  */
mas_set(struct ma_state * mas,unsigned long index)596 static inline void mas_set(struct ma_state *mas, unsigned long index)
597 {
598 
599 	mas_set_range(mas, index, index);
600 }
601 
mt_external_lock(const struct maple_tree * mt)602 static inline bool mt_external_lock(const struct maple_tree *mt)
603 {
604 	return (mt->ma_flags & MT_FLAGS_LOCK_MASK) == MT_FLAGS_LOCK_EXTERN;
605 }
606 
607 /**
608  * mt_init_flags() - Initialise an empty maple tree with flags.
609  * @mt: Maple Tree
610  * @flags: maple tree flags.
611  *
612  * If you need to initialise a Maple Tree with special flags (eg, an
613  * allocation tree), use this function.
614  *
615  * Context: Any context.
616  */
mt_init_flags(struct maple_tree * mt,unsigned int flags)617 static inline void mt_init_flags(struct maple_tree *mt, unsigned int flags)
618 {
619 	mt->ma_flags = flags;
620 	if (!mt_external_lock(mt))
621 		spin_lock_init(&mt->ma_lock);
622 	rcu_assign_pointer(mt->ma_root, NULL);
623 }
624 
625 /**
626  * mt_init() - Initialise an empty maple tree.
627  * @mt: Maple Tree
628  *
629  * An empty Maple Tree.
630  *
631  * Context: Any context.
632  */
mt_init(struct maple_tree * mt)633 static inline void mt_init(struct maple_tree *mt)
634 {
635 	mt_init_flags(mt, 0);
636 }
637 
mt_in_rcu(struct maple_tree * mt)638 static inline bool mt_in_rcu(struct maple_tree *mt)
639 {
640 #ifdef CONFIG_MAPLE_RCU_DISABLED
641 	return false;
642 #endif
643 	return mt->ma_flags & MT_FLAGS_USE_RCU;
644 }
645 
646 /**
647  * mt_clear_in_rcu() - Switch the tree to non-RCU mode.
648  * @mt: The Maple Tree
649  */
mt_clear_in_rcu(struct maple_tree * mt)650 static inline void mt_clear_in_rcu(struct maple_tree *mt)
651 {
652 	if (!mt_in_rcu(mt))
653 		return;
654 
655 	if (mt_external_lock(mt)) {
656 		WARN_ON(!mt_lock_is_held(mt));
657 		mt->ma_flags &= ~MT_FLAGS_USE_RCU;
658 	} else {
659 		mtree_lock(mt);
660 		mt->ma_flags &= ~MT_FLAGS_USE_RCU;
661 		mtree_unlock(mt);
662 	}
663 }
664 
665 /**
666  * mt_set_in_rcu() - Switch the tree to RCU safe mode.
667  * @mt: The Maple Tree
668  */
mt_set_in_rcu(struct maple_tree * mt)669 static inline void mt_set_in_rcu(struct maple_tree *mt)
670 {
671 	if (mt_in_rcu(mt))
672 		return;
673 
674 	if (mt_external_lock(mt)) {
675 		WARN_ON(!mt_lock_is_held(mt));
676 		mt->ma_flags |= MT_FLAGS_USE_RCU;
677 	} else {
678 		mtree_lock(mt);
679 		mt->ma_flags |= MT_FLAGS_USE_RCU;
680 		mtree_unlock(mt);
681 	}
682 }
683 
mt_height(const struct maple_tree * mt)684 static inline unsigned int mt_height(const struct maple_tree *mt)
685 {
686 	return (mt->ma_flags & MT_FLAGS_HEIGHT_MASK) >> MT_FLAGS_HEIGHT_OFFSET;
687 }
688 
689 void *mt_find(struct maple_tree *mt, unsigned long *index, unsigned long max);
690 void *mt_find_after(struct maple_tree *mt, unsigned long *index,
691 		    unsigned long max);
692 void *mt_prev(struct maple_tree *mt, unsigned long index,  unsigned long min);
693 void *mt_next(struct maple_tree *mt, unsigned long index, unsigned long max);
694 
695 /**
696  * mt_for_each - Iterate over each entry starting at index until max.
697  * @__tree: The Maple Tree
698  * @__entry: The current entry
699  * @__index: The index to start the search from. Subsequently used as iterator.
700  * @__max: The maximum limit for @index
701  *
702  * This iterator skips all entries, which resolve to a NULL pointer,
703  * e.g. entries which has been reserved with XA_ZERO_ENTRY.
704  */
705 #define mt_for_each(__tree, __entry, __index, __max) \
706 	for (__entry = mt_find(__tree, &(__index), __max); \
707 		__entry; __entry = mt_find_after(__tree, &(__index), __max))
708 
709 
710 #ifdef CONFIG_DEBUG_MAPLE_TREE
711 enum mt_dump_format {
712 	mt_dump_dec,
713 	mt_dump_hex,
714 };
715 
716 extern atomic_t maple_tree_tests_run;
717 extern atomic_t maple_tree_tests_passed;
718 
719 void mt_dump(const struct maple_tree *mt, enum mt_dump_format format);
720 void mas_dump(const struct ma_state *mas);
721 void mas_wr_dump(const struct ma_wr_state *wr_mas);
722 void mt_validate(struct maple_tree *mt);
723 void mt_cache_shrink(void);
724 #define MT_BUG_ON(__tree, __x) do {					\
725 	atomic_inc(&maple_tree_tests_run);				\
726 	if (__x) {							\
727 		pr_info("BUG at %s:%d (%u)\n",				\
728 		__func__, __LINE__, __x);				\
729 		mt_dump(__tree, mt_dump_hex);				\
730 		pr_info("Pass: %u Run:%u\n",				\
731 			atomic_read(&maple_tree_tests_passed),		\
732 			atomic_read(&maple_tree_tests_run));		\
733 		dump_stack();						\
734 	} else {							\
735 		atomic_inc(&maple_tree_tests_passed);			\
736 	}								\
737 } while (0)
738 
739 #define MAS_BUG_ON(__mas, __x) do {					\
740 	atomic_inc(&maple_tree_tests_run);				\
741 	if (__x) {							\
742 		pr_info("BUG at %s:%d (%u)\n",				\
743 		__func__, __LINE__, __x);				\
744 		mas_dump(__mas);					\
745 		mt_dump((__mas)->tree, mt_dump_hex);			\
746 		pr_info("Pass: %u Run:%u\n",				\
747 			atomic_read(&maple_tree_tests_passed),		\
748 			atomic_read(&maple_tree_tests_run));		\
749 		dump_stack();						\
750 	} else {							\
751 		atomic_inc(&maple_tree_tests_passed);			\
752 	}								\
753 } while (0)
754 
755 #define MAS_WR_BUG_ON(__wrmas, __x) do {				\
756 	atomic_inc(&maple_tree_tests_run);				\
757 	if (__x) {							\
758 		pr_info("BUG at %s:%d (%u)\n",				\
759 		__func__, __LINE__, __x);				\
760 		mas_wr_dump(__wrmas);					\
761 		mas_dump((__wrmas)->mas);				\
762 		mt_dump((__wrmas)->mas->tree, mt_dump_hex);		\
763 		pr_info("Pass: %u Run:%u\n",				\
764 			atomic_read(&maple_tree_tests_passed),		\
765 			atomic_read(&maple_tree_tests_run));		\
766 		dump_stack();						\
767 	} else {							\
768 		atomic_inc(&maple_tree_tests_passed);			\
769 	}								\
770 } while (0)
771 
772 #define MT_WARN_ON(__tree, __x)  ({					\
773 	int ret = !!(__x);						\
774 	atomic_inc(&maple_tree_tests_run);				\
775 	if (ret) {							\
776 		pr_info("WARN at %s:%d (%u)\n",				\
777 		__func__, __LINE__, __x);				\
778 		mt_dump(__tree, mt_dump_hex);				\
779 		pr_info("Pass: %u Run:%u\n",				\
780 			atomic_read(&maple_tree_tests_passed),		\
781 			atomic_read(&maple_tree_tests_run));		\
782 		dump_stack();						\
783 	} else {							\
784 		atomic_inc(&maple_tree_tests_passed);			\
785 	}								\
786 	unlikely(ret);							\
787 })
788 
789 #define MAS_WARN_ON(__mas, __x) ({					\
790 	int ret = !!(__x);						\
791 	atomic_inc(&maple_tree_tests_run);				\
792 	if (ret) {							\
793 		pr_info("WARN at %s:%d (%u)\n",				\
794 		__func__, __LINE__, __x);				\
795 		mas_dump(__mas);					\
796 		mt_dump((__mas)->tree, mt_dump_hex);			\
797 		pr_info("Pass: %u Run:%u\n",				\
798 			atomic_read(&maple_tree_tests_passed),		\
799 			atomic_read(&maple_tree_tests_run));		\
800 		dump_stack();						\
801 	} else {							\
802 		atomic_inc(&maple_tree_tests_passed);			\
803 	}								\
804 	unlikely(ret);							\
805 })
806 
807 #define MAS_WR_WARN_ON(__wrmas, __x) ({					\
808 	int ret = !!(__x);						\
809 	atomic_inc(&maple_tree_tests_run);				\
810 	if (ret) {							\
811 		pr_info("WARN at %s:%d (%u)\n",				\
812 		__func__, __LINE__, __x);				\
813 		mas_wr_dump(__wrmas);					\
814 		mas_dump((__wrmas)->mas);				\
815 		mt_dump((__wrmas)->mas->tree, mt_dump_hex);		\
816 		pr_info("Pass: %u Run:%u\n",				\
817 			atomic_read(&maple_tree_tests_passed),		\
818 			atomic_read(&maple_tree_tests_run));		\
819 		dump_stack();						\
820 	} else {							\
821 		atomic_inc(&maple_tree_tests_passed);			\
822 	}								\
823 	unlikely(ret);							\
824 })
825 #else
826 #define MT_BUG_ON(__tree, __x)		BUG_ON(__x)
827 #define MAS_BUG_ON(__mas, __x)		BUG_ON(__x)
828 #define MAS_WR_BUG_ON(__mas, __x)	BUG_ON(__x)
829 #define MT_WARN_ON(__tree, __x)		WARN_ON(__x)
830 #define MAS_WARN_ON(__mas, __x)		WARN_ON(__x)
831 #define MAS_WR_WARN_ON(__mas, __x)	WARN_ON(__x)
832 #endif /* CONFIG_DEBUG_MAPLE_TREE */
833 
834 #endif /*_LINUX_MAPLE_TREE_H */
835