include/linux/maple_tree.h

   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 */