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 | */ |
79 | struct 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 | |
105 | struct 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 | */ |
126 | struct 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 | |
134 | struct 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 | |
141 | struct maple_topiary { |
142 | struct maple_pnode *parent; |
143 | struct maple_enode *next; /* Overlaps the pivot */ |
144 | }; |
145 | |
146 | enum 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 |
186 | typedef 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 |
191 | typedef 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 | */ |
210 | struct 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 | |
269 | struct 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 | */ |
297 | struct ma_topiary { |
298 | struct maple_enode *head; |
299 | struct maple_enode *tail; |
300 | struct maple_tree *mtree; |
301 | }; |
302 | |
303 | void *mtree_load(struct maple_tree *mt, unsigned long index); |
304 | |
305 | int mtree_insert(struct maple_tree *mt, unsigned long index, |
306 | void *entry, gfp_t gfp); |
307 | int mtree_insert_range(struct maple_tree *mt, unsigned long first, |
308 | unsigned long last, void *entry, gfp_t gfp); |
309 | int 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); |
312 | int 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 | |
316 | int mtree_store_range(struct maple_tree *mt, unsigned long first, |
317 | unsigned long last, void *entry, gfp_t gfp); |
318 | int mtree_store(struct maple_tree *mt, unsigned long index, |
319 | void *entry, gfp_t gfp); |
320 | void *mtree_erase(struct maple_tree *mt, unsigned long index); |
321 | |
322 | void mtree_destroy(struct maple_tree *mt); |
323 | void __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 | */ |
332 | static 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 | */ |
372 | struct 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 | |
385 | struct 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 | |
452 | void *mas_walk(struct ma_state *mas); |
453 | void *mas_store(struct ma_state *mas, void *entry); |
454 | void *mas_erase(struct ma_state *mas); |
455 | int mas_store_gfp(struct ma_state *mas, void *entry, gfp_t gfp); |
456 | void mas_store_prealloc(struct ma_state *mas, void *entry); |
457 | void *mas_find(struct ma_state *mas, unsigned long max); |
458 | void *mas_find_rev(struct ma_state *mas, unsigned long min); |
459 | int mas_preallocate(struct ma_state *mas, gfp_t gfp); |
460 | bool mas_is_err(struct ma_state *mas); |
461 | |
462 | bool mas_nomem(struct ma_state *mas, gfp_t gfp); |
463 | void mas_pause(struct ma_state *mas); |
464 | void maple_tree_init(void); |
465 | void mas_destroy(struct ma_state *mas); |
466 | int mas_expected_entries(struct ma_state *mas, unsigned long nr_entries); |
467 | |
468 | void *mas_prev(struct ma_state *mas, unsigned long min); |
469 | void *mas_next(struct ma_state *mas, unsigned long max); |
470 | |
471 | int mas_empty_area(struct ma_state *mas, unsigned long min, unsigned long max, |
472 | unsigned long size); |
473 | |
474 | static 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 */ |
485 | static 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 */ |
491 | static 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 | */ |
500 | int 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 | */ |
512 | static 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 | */ |
542 | static inline |
543 | void 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 | */ |
559 | static inline void mas_set(struct ma_state *mas, unsigned long index) |
560 | { |
561 | |
562 | mas_set_range(mas, start: index, last: index); |
563 | } |
564 | |
565 | static 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 | */ |
580 | static 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 | */ |
596 | static inline void mt_init(struct maple_tree *mt) |
597 | { |
598 | mt_init_flags(mt, flags: 0); |
599 | } |
600 | |
601 | static 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 | */ |
613 | static 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 | */ |
632 | static 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 | |
647 | static 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 | |
652 | void *mt_find(struct maple_tree *mt, unsigned long *index, unsigned long max); |
653 | void *mt_find_after(struct maple_tree *mt, unsigned long *index, |
654 | unsigned long max); |
655 | void *mt_prev(struct maple_tree *mt, unsigned long index, unsigned long min); |
656 | void *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 |
673 | extern atomic_t maple_tree_tests_run; |
674 | extern atomic_t maple_tree_tests_passed; |
675 | |
676 | void mt_dump(const struct maple_tree *mt); |
677 | void mt_validate(struct maple_tree *mt); |
678 | void 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 | |