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 | */ |
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 | |
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 */ |
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 */ |
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 */ |
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 | */ |
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 | */ |
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 |
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 | */ |
596 | static inline void mas_set(struct ma_state *mas, unsigned long index) |
597 | { |
598 | |
599 | mas_set_range(mas, start: index, last: index); |
600 | } |
601 | |
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 | */ |
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 | */ |
633 | static inline void mt_init(struct maple_tree *mt) |
634 | { |
635 | mt_init_flags(mt, flags: 0); |
636 | } |
637 | |
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 | */ |
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 | */ |
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 | |
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 | |