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_ARANGE64_META_MAX 15 /* Out of range for metadata */
33#define MAPLE_ALLOC_SLOTS (MAPLE_NODE_SLOTS - 1)
34#else
35/* 32bit sizes */
36#define MAPLE_NODE_SLOTS 63 /* 256 bytes including ->parent */
37#define MAPLE_RANGE64_SLOTS 32 /* 256 bytes */
38#define MAPLE_ARANGE64_SLOTS 21 /* 240 bytes */
39#define MAPLE_ARANGE64_META_MAX 31 /* Out of range for metadata */
40#define MAPLE_ALLOC_SLOTS (MAPLE_NODE_SLOTS - 2)
41#endif /* defined(CONFIG_64BIT) || defined(BUILD_VDSO32_64) */
42
43#define MAPLE_NODE_MASK 255UL
44
45/*
46 * The node->parent of the root node has bit 0 set and the rest of the pointer
47 * is a pointer to the tree itself. No more bits are available in this pointer
48 * (on m68k, the data structure may only be 2-byte aligned).
49 *
50 * Internal non-root nodes can only have maple_range_* nodes as parents. The
51 * parent pointer is 256B aligned like all other tree nodes. When storing a 32
52 * or 64 bit values, the offset can fit into 4 bits. The 16 bit values need an
53 * extra bit to store the offset. This extra bit comes from a reuse of the last
54 * bit in the node type. This is possible by using bit 1 to indicate if bit 2
55 * is part of the type or the slot.
56 *
57 * Once the type is decided, the decision of an allocation range type or a range
58 * type is done by examining the immutable tree flag for the MAPLE_ALLOC_RANGE
59 * flag.
60 *
61 * Node types:
62 * 0x??1 = Root
63 * 0x?00 = 16 bit nodes
64 * 0x010 = 32 bit nodes
65 * 0x110 = 64 bit nodes
66 *
67 * Slot size and location in the parent pointer:
68 * type : slot location
69 * 0x??1 : Root
70 * 0x?00 : 16 bit values, type in 0-1, slot in 2-6
71 * 0x010 : 32 bit values, type in 0-2, slot in 3-6
72 * 0x110 : 64 bit values, type in 0-2, slot in 3-6
73 */
74
75/*
76 * This metadata is used to optimize the gap updating code and in reverse
77 * searching for gaps or any other code that needs to find the end of the data.
78 */
79struct maple_metadata {
80 unsigned char end;
81 unsigned char gap;
82};
83
84/*
85 * Leaf nodes do not store pointers to nodes, they store user data. Users may
86 * store almost any bit pattern. As noted above, the optimisation of storing an
87 * entry at 0 in the root pointer cannot be done for data which have the bottom
88 * two bits set to '10'. We also reserve values with the bottom two bits set to
89 * '10' which are below 4096 (ie 2, 6, 10 .. 4094) for internal use. Some APIs
90 * return errnos as a negative errno shifted right by two bits and the bottom
91 * two bits set to '10', and while choosing to store these values in the array
92 * is not an error, it may lead to confusion if you're testing for an error with
93 * mas_is_err().
94 *
95 * Non-leaf nodes store the type of the node pointed to (enum maple_type in bits
96 * 3-6), bit 2 is reserved. That leaves bits 0-1 unused for now.
97 *
98 * In regular B-Tree terms, pivots are called keys. The term pivot is used to
99 * indicate that the tree is specifying ranges, Pivots may appear in the
100 * subtree with an entry attached to the value whereas keys are unique to a
101 * specific position of a B-tree. Pivot values are inclusive of the slot with
102 * the same index.
103 */
104
105struct maple_range_64 {
106 struct maple_pnode *parent;
107 unsigned long pivot[MAPLE_RANGE64_SLOTS - 1];
108 union {
109 void __rcu *slot[MAPLE_RANGE64_SLOTS];
110 struct {
111 void __rcu *pad[MAPLE_RANGE64_SLOTS - 1];
112 struct maple_metadata meta;
113 };
114 };
115};
116
117/*
118 * At tree creation time, the user can specify that they're willing to trade off
119 * storing fewer entries in a tree in return for storing more information in
120 * each node.
121 *
122 * The maple tree supports recording the largest range of NULL entries available
123 * in this node, also called gaps. This optimises the tree for allocating a
124 * range.
125 */
126struct maple_arange_64 {
127 struct maple_pnode *parent;
128 unsigned long pivot[MAPLE_ARANGE64_SLOTS - 1];
129 void __rcu *slot[MAPLE_ARANGE64_SLOTS];
130 unsigned long gap[MAPLE_ARANGE64_SLOTS];
131 struct maple_metadata meta;
132};
133
134struct maple_alloc {
135 unsigned long total;
136 unsigned char node_count;
137 unsigned int request_count;
138 struct maple_alloc *slot[MAPLE_ALLOC_SLOTS];
139};
140
141struct maple_topiary {
142 struct maple_pnode *parent;
143 struct maple_enode *next; /* Overlaps the pivot */
144};
145
146enum maple_type {
147 maple_dense,
148 maple_leaf_64,
149 maple_range_64,
150 maple_arange_64,
151};
152
153
154/**
155 * DOC: Maple tree flags
156 *
157 * * MT_FLAGS_ALLOC_RANGE - Track gaps in this tree
158 * * MT_FLAGS_USE_RCU - Operate in RCU mode
159 * * MT_FLAGS_HEIGHT_OFFSET - The position of the tree height in the flags
160 * * MT_FLAGS_HEIGHT_MASK - The mask for the maple tree height value
161 * * MT_FLAGS_LOCK_MASK - How the mt_lock is used
162 * * MT_FLAGS_LOCK_IRQ - Acquired irq-safe
163 * * MT_FLAGS_LOCK_BH - Acquired bh-safe
164 * * MT_FLAGS_LOCK_EXTERN - mt_lock is not used
165 *
166 * MAPLE_HEIGHT_MAX The largest height that can be stored
167 */
168#define MT_FLAGS_ALLOC_RANGE 0x01
169#define MT_FLAGS_USE_RCU 0x02
170#define MT_FLAGS_HEIGHT_OFFSET 0x02
171#define MT_FLAGS_HEIGHT_MASK 0x7C
172#define MT_FLAGS_LOCK_MASK 0x300
173#define MT_FLAGS_LOCK_IRQ 0x100
174#define MT_FLAGS_LOCK_BH 0x200
175#define MT_FLAGS_LOCK_EXTERN 0x300
176
177#define MAPLE_HEIGHT_MAX 31
178
179
180#define MAPLE_NODE_TYPE_MASK 0x0F
181#define MAPLE_NODE_TYPE_SHIFT 0x03
182
183#define MAPLE_RESERVED_RANGE 4096
184
185#ifdef CONFIG_LOCKDEP
186typedef struct lockdep_map *lockdep_map_p;
187#define mt_lock_is_held(mt) lock_is_held(mt->ma_external_lock)
188#define mt_set_external_lock(mt, lock) \
189 (mt)->ma_external_lock = &(lock)->dep_map
190#else
191typedef struct { /* nothing */ } lockdep_map_p;
192#define mt_lock_is_held(mt) 1
193#define mt_set_external_lock(mt, lock) do { } while (0)
194#endif
195
196/*
197 * If the tree contains a single entry at index 0, it is usually stored in
198 * tree->ma_root. To optimise for the page cache, an entry which ends in '00',
199 * '01' or '11' is stored in the root, but an entry which ends in '10' will be
200 * stored in a node. Bits 3-6 are used to store enum maple_type.
201 *
202 * The flags are used both to store some immutable information about this tree
203 * (set at tree creation time) and dynamic information set under the spinlock.
204 *
205 * Another use of flags are to indicate global states of the tree. This is the
206 * case with the MAPLE_USE_RCU flag, which indicates the tree is currently in
207 * RCU mode. This mode was added to allow the tree to reuse nodes instead of
208 * re-allocating and RCU freeing nodes when there is a single user.
209 */
210struct maple_tree {
211 union {
212 spinlock_t ma_lock;
213 lockdep_map_p ma_external_lock;
214 };
215 void __rcu *ma_root;
216 unsigned int ma_flags;
217};
218
219/**
220 * MTREE_INIT() - Initialize a maple tree
221 * @name: The maple tree name
222 * @__flags: The maple tree flags
223 *
224 */
225#define MTREE_INIT(name, __flags) { \
226 .ma_lock = __SPIN_LOCK_UNLOCKED((name).ma_lock), \
227 .ma_flags = __flags, \
228 .ma_root = NULL, \
229}
230
231/**
232 * MTREE_INIT_EXT() - Initialize a maple tree with an external lock.
233 * @name: The tree name
234 * @__flags: The maple tree flags
235 * @__lock: The external lock
236 */
237#ifdef CONFIG_LOCKDEP
238#define MTREE_INIT_EXT(name, __flags, __lock) { \
239 .ma_external_lock = &(__lock).dep_map, \
240 .ma_flags = (__flags), \
241 .ma_root = NULL, \
242}
243#else
244#define MTREE_INIT_EXT(name, __flags, __lock) MTREE_INIT(name, __flags)
245#endif
246
247#define DEFINE_MTREE(name) \
248 struct maple_tree name = MTREE_INIT(name, 0)
249
250#define mtree_lock(mt) spin_lock((&(mt)->ma_lock))
251#define mtree_unlock(mt) spin_unlock((&(mt)->ma_lock))
252
253/*
254 * The Maple Tree squeezes various bits in at various points which aren't
255 * necessarily obvious. Usually, this is done by observing that pointers are
256 * N-byte aligned and thus the bottom log_2(N) bits are available for use. We
257 * don't use the high bits of pointers to store additional information because
258 * we don't know what bits are unused on any given architecture.
259 *
260 * Nodes are 256 bytes in size and are also aligned to 256 bytes, giving us 8
261 * low bits for our own purposes. Nodes are currently of 4 types:
262 * 1. Single pointer (Range is 0-0)
263 * 2. Non-leaf Allocation Range nodes
264 * 3. Non-leaf Range nodes
265 * 4. Leaf Range nodes All nodes consist of a number of node slots,
266 * pivots, and a parent pointer.
267 */
268
269struct maple_node {
270 union {
271 struct {
272 struct maple_pnode *parent;
273 void __rcu *slot[MAPLE_NODE_SLOTS];
274 };
275 struct {
276 void *pad;
277 struct rcu_head rcu;
278 struct maple_enode *piv_parent;
279 unsigned char parent_slot;
280 enum maple_type type;
281 unsigned char slot_len;
282 unsigned int ma_flags;
283 };
284 struct maple_range_64 mr64;
285 struct maple_arange_64 ma64;
286 struct maple_alloc alloc;
287 };
288};
289
290/*
291 * More complicated stores can cause two nodes to become one or three and
292 * potentially alter the height of the tree. Either half of the tree may need
293 * to be rebalanced against the other. The ma_topiary struct is used to track
294 * which nodes have been 'cut' from the tree so that the change can be done
295 * safely at a later date. This is done to support RCU.
296 */
297struct ma_topiary {
298 struct maple_enode *head;
299 struct maple_enode *tail;
300 struct maple_tree *mtree;
301};
302
303void *mtree_load(struct maple_tree *mt, unsigned long index);
304
305int mtree_insert(struct maple_tree *mt, unsigned long index,
306 void *entry, gfp_t gfp);
307int mtree_insert_range(struct maple_tree *mt, unsigned long first,
308 unsigned long last, void *entry, gfp_t gfp);
309int mtree_alloc_range(struct maple_tree *mt, unsigned long *startp,
310 void *entry, unsigned long size, unsigned long min,
311 unsigned long max, gfp_t gfp);
312int mtree_alloc_rrange(struct maple_tree *mt, unsigned long *startp,
313 void *entry, unsigned long size, unsigned long min,
314 unsigned long max, gfp_t gfp);
315
316int mtree_store_range(struct maple_tree *mt, unsigned long first,
317 unsigned long last, void *entry, gfp_t gfp);
318int mtree_store(struct maple_tree *mt, unsigned long index,
319 void *entry, gfp_t gfp);
320void *mtree_erase(struct maple_tree *mt, unsigned long index);
321
322void mtree_destroy(struct maple_tree *mt);
323void __mt_destroy(struct maple_tree *mt);
324
325/**
326 * mtree_empty() - Determine if a tree has any present entries.
327 * @mt: Maple Tree.
328 *
329 * Context: Any context.
330 * Return: %true if the tree contains only NULL pointers.
331 */
332static inline bool mtree_empty(const struct maple_tree *mt)
333{
334 return mt->ma_root == NULL;
335}
336
337/* Advanced API */
338
339/*
340 * The maple state is defined in the struct ma_state and is used to keep track
341 * of information during operations, and even between operations when using the
342 * advanced API.
343 *
344 * If state->node has bit 0 set then it references a tree location which is not
345 * a node (eg the root). If bit 1 is set, the rest of the bits are a negative
346 * errno. Bit 2 (the 'unallocated slots' bit) is clear. Bits 3-6 indicate the
347 * node type.
348 *
349 * state->alloc either has a request number of nodes or an allocated node. If
350 * stat->alloc has a requested number of nodes, the first bit will be set (0x1)
351 * and the remaining bits are the value. If state->alloc is a node, then the
352 * node will be of type maple_alloc. maple_alloc has MAPLE_NODE_SLOTS - 1 for
353 * storing more allocated nodes, a total number of nodes allocated, and the
354 * node_count in this node. node_count is the number of allocated nodes in this
355 * node. The scaling beyond MAPLE_NODE_SLOTS - 1 is handled by storing further
356 * nodes into state->alloc->slot[0]'s node. Nodes are taken from state->alloc
357 * by removing a node from the state->alloc node until state->alloc->node_count
358 * is 1, when state->alloc is returned and the state->alloc->slot[0] is promoted
359 * to state->alloc. Nodes are pushed onto state->alloc by putting the current
360 * state->alloc into the pushed node's slot[0].
361 *
362 * The state also contains the implied min/max of the state->node, the depth of
363 * this search, and the offset. The implied min/max are either from the parent
364 * node or are 0-oo for the root node. The depth is incremented or decremented
365 * every time a node is walked down or up. The offset is the slot/pivot of
366 * interest in the node - either for reading or writing.
367 *
368 * When returning a value the maple state index and last respectively contain
369 * the start and end of the range for the entry. Ranges are inclusive in the
370 * Maple Tree.
371 */
372struct ma_state {
373 struct maple_tree *tree; /* The tree we're operating in */
374 unsigned long index; /* The index we're operating on - range start */
375 unsigned long last; /* The last index we're operating on - range end */
376 struct maple_enode *node; /* The node containing this entry */
377 unsigned long min; /* The minimum index of this node - implied pivot min */
378 unsigned long max; /* The maximum index of this node - implied pivot max */
379 struct maple_alloc *alloc; /* Allocated nodes for this operation */
380 unsigned char depth; /* depth of tree descent during write */
381 unsigned char offset;
382 unsigned char mas_flags;
383};
384
385struct ma_wr_state {
386 struct ma_state *mas;
387 struct maple_node *node; /* Decoded mas->node */
388 unsigned long r_min; /* range min */
389 unsigned long r_max; /* range max */
390 enum maple_type type; /* mas->node type */
391 unsigned char offset_end; /* The offset where the write ends */
392 unsigned char node_end; /* mas->node end */
393 unsigned long *pivots; /* mas->node->pivots pointer */
394 unsigned long end_piv; /* The pivot at the offset end */
395 void __rcu **slots; /* mas->node->slots pointer */
396 void *entry; /* The entry to write */
397 void *content; /* The existing entry that is being overwritten */
398};
399
400#define mas_lock(mas) spin_lock(&((mas)->tree->ma_lock))
401#define mas_unlock(mas) spin_unlock(&((mas)->tree->ma_lock))
402
403
404/*
405 * Special values for ma_state.node.
406 * MAS_START means we have not searched the tree.
407 * MAS_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 * MAS_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_ERROR represents an errno. After dropping the lock and attempting
416 * to resolve the error, the walk would have to be restarted from the
417 * top of the tree as the tree may have been modified.
418 */
419#define MAS_START ((struct maple_enode *)1UL)
420#define MAS_ROOT ((struct maple_enode *)5UL)
421#define MAS_NONE ((struct maple_enode *)9UL)
422#define MAS_PAUSE ((struct maple_enode *)17UL)
423#define MA_ERROR(err) \
424 ((struct maple_enode *)(((unsigned long)err << 2) | 2UL))
425
426#define MA_STATE(name, mt, first, end) \
427 struct ma_state name = { \
428 .tree = mt, \
429 .index = first, \
430 .last = end, \
431 .node = MAS_START, \
432 .min = 0, \
433 .max = ULONG_MAX, \
434 .alloc = NULL, \
435 .mas_flags = 0, \
436 }
437
438#define MA_WR_STATE(name, ma_state, wr_entry) \
439 struct ma_wr_state name = { \
440 .mas = ma_state, \
441 .content = NULL, \
442 .entry = wr_entry, \
443 }
444
445#define MA_TOPIARY(name, tree) \
446 struct ma_topiary name = { \
447 .head = NULL, \
448 .tail = NULL, \
449 .mtree = tree, \
450 }
451
452void *mas_walk(struct ma_state *mas);
453void *mas_store(struct ma_state *mas, void *entry);
454void *mas_erase(struct ma_state *mas);
455int mas_store_gfp(struct ma_state *mas, void *entry, gfp_t gfp);
456void mas_store_prealloc(struct ma_state *mas, void *entry);
457void *mas_find(struct ma_state *mas, unsigned long max);
458void *mas_find_rev(struct ma_state *mas, unsigned long min);
459int mas_preallocate(struct ma_state *mas, gfp_t gfp);
460bool mas_is_err(struct ma_state *mas);
461
462bool mas_nomem(struct ma_state *mas, gfp_t gfp);
463void mas_pause(struct ma_state *mas);
464void maple_tree_init(void);
465void mas_destroy(struct ma_state *mas);
466int mas_expected_entries(struct ma_state *mas, unsigned long nr_entries);
467
468void *mas_prev(struct ma_state *mas, unsigned long min);
469void *mas_next(struct ma_state *mas, unsigned long max);
470
471int mas_empty_area(struct ma_state *mas, unsigned long min, unsigned long max,
472 unsigned long size);
473
474static inline void mas_init(struct ma_state *mas, struct maple_tree *tree,
475 unsigned long addr)
476{
477 memset(s: mas, c: 0, n: sizeof(struct ma_state));
478 mas->tree = tree;
479 mas->index = mas->last = addr;
480 mas->max = ULONG_MAX;
481 mas->node = MAS_START;
482}
483
484/* Checks if a mas has not found anything */
485static inline bool mas_is_none(struct ma_state *mas)
486{
487 return mas->node == MAS_NONE;
488}
489
490/* Checks if a mas has been paused */
491static inline bool mas_is_paused(struct ma_state *mas)
492{
493 return mas->node == MAS_PAUSE;
494}
495
496/*
497 * This finds an empty area from the highest address to the lowest.
498 * AKA "Topdown" version,
499 */
500int mas_empty_area_rev(struct ma_state *mas, unsigned long min,
501 unsigned long max, unsigned long size);
502/**
503 * mas_reset() - Reset a Maple Tree operation state.
504 * @mas: Maple Tree operation state.
505 *
506 * Resets the error or walk state of the @mas so future walks of the
507 * array will start from the root. Use this if you have dropped the
508 * lock and want to reuse the ma_state.
509 *
510 * Context: Any context.
511 */
512static inline void mas_reset(struct ma_state *mas)
513{
514 mas->node = MAS_START;
515}
516
517/**
518 * mas_for_each() - Iterate over a range of the maple tree.
519 * @__mas: Maple Tree operation state (maple_state)
520 * @__entry: Entry retrieved from the tree
521 * @__max: maximum index to retrieve from the tree
522 *
523 * When returned, mas->index and mas->last will hold the entire range for the
524 * entry.
525 *
526 * Note: may return the zero entry.
527 */
528#define mas_for_each(__mas, __entry, __max) \
529 while (((__entry) = mas_find((__mas), (__max))) != NULL)
530
531
532/**
533 * mas_set_range() - Set up Maple Tree operation state for a different index.
534 * @mas: Maple Tree operation state.
535 * @start: New start of range in the Maple Tree.
536 * @last: New end of range in the Maple Tree.
537 *
538 * Move the operation state to refer to a different range. This will
539 * have the effect of starting a walk from the top; see mas_next()
540 * to move to an adjacent index.
541 */
542static inline
543void mas_set_range(struct ma_state *mas, unsigned long start, unsigned long last)
544{
545 mas->index = start;
546 mas->last = last;
547 mas->node = MAS_START;
548}
549
550/**
551 * mas_set() - Set up Maple Tree operation state for a different index.
552 * @mas: Maple Tree operation state.
553 * @index: New index into the Maple Tree.
554 *
555 * Move the operation state to refer to a different index. This will
556 * have the effect of starting a walk from the top; see mas_next()
557 * to move to an adjacent index.
558 */
559static inline void mas_set(struct ma_state *mas, unsigned long index)
560{
561
562 mas_set_range(mas, start: index, last: index);
563}
564
565static inline bool mt_external_lock(const struct maple_tree *mt)
566{
567 return (mt->ma_flags & MT_FLAGS_LOCK_MASK) == MT_FLAGS_LOCK_EXTERN;
568}
569
570/**
571 * mt_init_flags() - Initialise an empty maple tree with flags.
572 * @mt: Maple Tree
573 * @flags: maple tree flags.
574 *
575 * If you need to initialise a Maple Tree with special flags (eg, an
576 * allocation tree), use this function.
577 *
578 * Context: Any context.
579 */
580static inline void mt_init_flags(struct maple_tree *mt, unsigned int flags)
581{
582 mt->ma_flags = flags;
583 if (!mt_external_lock(mt))
584 spin_lock_init(&mt->ma_lock);
585 rcu_assign_pointer(mt->ma_root, NULL);
586}
587
588/**
589 * mt_init() - Initialise an empty maple tree.
590 * @mt: Maple Tree
591 *
592 * An empty Maple Tree.
593 *
594 * Context: Any context.
595 */
596static inline void mt_init(struct maple_tree *mt)
597{
598 mt_init_flags(mt, flags: 0);
599}
600
601static inline bool mt_in_rcu(struct maple_tree *mt)
602{
603#ifdef CONFIG_MAPLE_RCU_DISABLED
604 return false;
605#endif
606 return mt->ma_flags & MT_FLAGS_USE_RCU;
607}
608
609/**
610 * mt_clear_in_rcu() - Switch the tree to non-RCU mode.
611 * @mt: The Maple Tree
612 */
613static inline void mt_clear_in_rcu(struct maple_tree *mt)
614{
615 if (!mt_in_rcu(mt))
616 return;
617
618 if (mt_external_lock(mt)) {
619 BUG_ON(!mt_lock_is_held(mt));
620 mt->ma_flags &= ~MT_FLAGS_USE_RCU;
621 } else {
622 mtree_lock(mt);
623 mt->ma_flags &= ~MT_FLAGS_USE_RCU;
624 mtree_unlock(mt);
625 }
626}
627
628/**
629 * mt_set_in_rcu() - Switch the tree to RCU safe mode.
630 * @mt: The Maple Tree
631 */
632static inline void mt_set_in_rcu(struct maple_tree *mt)
633{
634 if (mt_in_rcu(mt))
635 return;
636
637 if (mt_external_lock(mt)) {
638 BUG_ON(!mt_lock_is_held(mt));
639 mt->ma_flags |= MT_FLAGS_USE_RCU;
640 } else {
641 mtree_lock(mt);
642 mt->ma_flags |= MT_FLAGS_USE_RCU;
643 mtree_unlock(mt);
644 }
645}
646
647static inline unsigned int mt_height(const struct maple_tree *mt)
648{
649 return (mt->ma_flags & MT_FLAGS_HEIGHT_MASK) >> MT_FLAGS_HEIGHT_OFFSET;
650}
651
652void *mt_find(struct maple_tree *mt, unsigned long *index, unsigned long max);
653void *mt_find_after(struct maple_tree *mt, unsigned long *index,
654 unsigned long max);
655void *mt_prev(struct maple_tree *mt, unsigned long index, unsigned long min);
656void *mt_next(struct maple_tree *mt, unsigned long index, unsigned long max);
657
658/**
659 * mt_for_each - Iterate over each entry starting at index until max.
660 * @__tree: The Maple Tree
661 * @__entry: The current entry
662 * @__index: The index to update to track the location in the tree
663 * @__max: The maximum limit for @index
664 *
665 * Note: Will not return the zero entry.
666 */
667#define mt_for_each(__tree, __entry, __index, __max) \
668 for (__entry = mt_find(__tree, &(__index), __max); \
669 __entry; __entry = mt_find_after(__tree, &(__index), __max))
670
671
672#ifdef CONFIG_DEBUG_MAPLE_TREE
673extern atomic_t maple_tree_tests_run;
674extern atomic_t maple_tree_tests_passed;
675
676void mt_dump(const struct maple_tree *mt);
677void mt_validate(struct maple_tree *mt);
678void mt_cache_shrink(void);
679#define MT_BUG_ON(__tree, __x) do { \
680 atomic_inc(&maple_tree_tests_run); \
681 if (__x) { \
682 pr_info("BUG at %s:%d (%u)\n", \
683 __func__, __LINE__, __x); \
684 mt_dump(__tree); \
685 pr_info("Pass: %u Run:%u\n", \
686 atomic_read(&maple_tree_tests_passed), \
687 atomic_read(&maple_tree_tests_run)); \
688 dump_stack(); \
689 } else { \
690 atomic_inc(&maple_tree_tests_passed); \
691 } \
692} while (0)
693#else
694#define MT_BUG_ON(__tree, __x) BUG_ON(__x)
695#endif /* CONFIG_DEBUG_MAPLE_TREE */
696
697#endif /*_LINUX_MAPLE_TREE_H */
698

source code of linux/include/linux/maple_tree.h