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