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