Commit | Line | Data |
---|---|---|
54a611b6 LH |
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 */ | |
54a611b6 LH |
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, \ | |
e7f43ca9 | 435 | .mas_flags = 0, \ |
54a611b6 LH |
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); | |
c5d5546e | 459 | int mas_preallocate(struct ma_state *mas, gfp_t gfp); |
54a611b6 LH |
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 | ||
e7f43ca9 LH |
474 | static inline void mas_init(struct ma_state *mas, struct maple_tree *tree, |
475 | unsigned long addr) | |
476 | { | |
477 | memset(mas, 0, 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 | ||
54a611b6 LH |
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 | ||
54a611b6 LH |
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. | |
54a611b6 LH |
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, index, 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, 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 | ||
120b1162 | 647 | static inline unsigned int mt_height(const struct maple_tree *mt) |
120b1162 LH |
648 | { |
649 | return (mt->ma_flags & MT_FLAGS_HEIGHT_MASK) >> MT_FLAGS_HEIGHT_OFFSET; | |
650 | } | |
651 | ||
54a611b6 LH |
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); | |
120b1162 | 678 | void mt_cache_shrink(void); |
54a611b6 LH |
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 */ |