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