lib/xarray.c

   1 // SPDX-License-Identifier: GPL-2.0+
   2 /*
   3  * XArray implementation
   4  * Copyright (c) 2017 Microsoft Corporation
   5  * Author: Matthew Wilcox <willy@infradead.org>
   6  */
   7
   8 #include <linux/bitmap.h>
   9 #include <linux/export.h>
  10 #include <linux/list.h>
  11 #include <linux/slab.h>
  12 #include <linux/xarray.h>
  13
  14 /*
  15  * Coding conventions in this file:
  16  *
  17  * @xa is used to refer to the entire xarray.
  18  * @xas is the 'xarray operation state'.  It may be either a pointer to
  19  * an xa_state, or an xa_state stored on the stack.  This is an unfortunate
  20  * ambiguity.
  21  * @index is the index of the entry being operated on
  22  * @mark is an xa_mark_t; a small number indicating one of the mark bits.
  23  * @node refers to an xa_node; usually the primary one being operated on by
  24  * this function.
  25  * @offset is the index into the slots array inside an xa_node.
  26  * @parent refers to the @xa_node closer to the head than @node.
  27  * @entry refers to something stored in a slot in the xarray
  28  */
  29
  30 static inline unsigned int xa_lock_type(const struct xarray *xa)
  31 {
  32         return (__force unsigned int)xa->xa_flags & 3;
  33 }
  34
  35 static inline void xas_lock_type(struct xa_state *xas, unsigned int lock_type)
  36 {
  37         if (lock_type == XA_LOCK_IRQ)
  38                 xas_lock_irq(xas);
  39         else if (lock_type == XA_LOCK_BH)
  40                 xas_lock_bh(xas);
  41         else
  42                 xas_lock(xas);
  43 }
  44
  45 static inline void xas_unlock_type(struct xa_state *xas, unsigned int lock_type)
  46 {
  47         if (lock_type == XA_LOCK_IRQ)
  48                 xas_unlock_irq(xas);
  49         else if (lock_type == XA_LOCK_BH)
  50                 xas_unlock_bh(xas);
  51         else
  52                 xas_unlock(xas);
  53 }
  54
  55 static inline bool xa_track_free(const struct xarray *xa)
  56 {
  57         return xa->xa_flags & XA_FLAGS_TRACK_FREE;
  58 }
  59
  60 static inline bool xa_zero_busy(const struct xarray *xa)
  61 {
  62         return xa->xa_flags & XA_FLAGS_ZERO_BUSY;
  63 }
  64
  65 static inline void xa_mark_set(struct xarray *xa, xa_mark_t mark)
  66 {
  67         if (!(xa->xa_flags & XA_FLAGS_MARK(mark)))
  68                 xa->xa_flags |= XA_FLAGS_MARK(mark);
  69 }
  70
  71 static inline void xa_mark_clear(struct xarray *xa, xa_mark_t mark)
  72 {
  73         if (xa->xa_flags & XA_FLAGS_MARK(mark))
  74                 xa->xa_flags &= ~(XA_FLAGS_MARK(mark));
  75 }
  76
  77 static inline unsigned long *node_marks(struct xa_node *node, xa_mark_t mark)
  78 {
  79         return node->marks[(__force unsigned)mark];
  80 }
  81
  82 static inline bool node_get_mark(struct xa_node *node,
  83                 unsigned int offset, xa_mark_t mark)
  84 {
  85         return test_bit(offset, node_marks(node, mark));
  86 }
  87
  88 /* returns true if the bit was set */
  89 static inline bool node_set_mark(struct xa_node *node, unsigned int offset,
  90                                 xa_mark_t mark)
  91 {
  92         return __test_and_set_bit(offset, node_marks(node, mark));
  93 }
  94
  95 /* returns true if the bit was set */
  96 static inline bool node_clear_mark(struct xa_node *node, unsigned int offset,
  97                                 xa_mark_t mark)
  98 {
  99         return __test_and_clear_bit(offset, node_marks(node, mark));
 100 }
 101
 102 static inline bool node_any_mark(struct xa_node *node, xa_mark_t mark)
 103 {
 104         return !bitmap_empty(node_marks(node, mark), XA_CHUNK_SIZE);
 105 }
 106
 107 static inline void node_mark_all(struct xa_node *node, xa_mark_t mark)
 108 {
 109         bitmap_fill(node_marks(node, mark), XA_CHUNK_SIZE);
 110 }
 111
 112 #define mark_inc(mark) do { \
 113         mark = (__force xa_mark_t)((__force unsigned)(mark) + 1); \
 114 } while (0)
 115
 116 /*
 117  * xas_squash_marks() - Merge all marks to the first entry
 118  * @xas: Array operation state.
 119  *
 120  * Set a mark on the first entry if any entry has it set.  Clear marks on
 121  * all sibling entries.
 122  */
 123 static void xas_squash_marks(const struct xa_state *xas)
 124 {
 125         unsigned int mark = 0;
 126         unsigned int limit = xas->xa_offset + xas->xa_sibs + 1;
 127
 128         if (!xas->xa_sibs)
 129                 return;
 130
 131         do {
 132                 unsigned long *marks = xas->xa_node->marks[mark];
 133                 if (find_next_bit(marks, limit, xas->xa_offset + 1) == limit)
 134                         continue;
 135                 __set_bit(xas->xa_offset, marks);
 136                 bitmap_clear(marks, xas->xa_offset + 1, xas->xa_sibs);
 137         } while (mark++ != (__force unsigned)XA_MARK_MAX);
 138 }
 139
 140 /* extracts the offset within this node from the index */
 141 static unsigned int get_offset(unsigned long index, struct xa_node *node)
 142 {
 143         return (index >> node->shift) & XA_CHUNK_MASK;
 144 }
 145
 146 static void xas_set_offset(struct xa_state *xas)
 147 {
 148         xas->xa_offset = get_offset(xas->xa_index, xas->xa_node);
 149 }
 150
 151 /* move the index either forwards (find) or backwards (sibling slot) */
 152 static void xas_move_index(struct xa_state *xas, unsigned long offset)
 153 {
 154         unsigned int shift = xas->xa_node->shift;
 155         xas->xa_index &= ~XA_CHUNK_MASK << shift;
 156         xas->xa_index += offset << shift;
 157 }
 158
 159 static void xas_advance(struct xa_state *xas)
 160 {
 161         xas->xa_offset++;
 162         xas_move_index(xas, xas->xa_offset);
 163 }
 164
 165 static void *set_bounds(struct xa_state *xas)
 166 {
 167         xas->xa_node = XAS_BOUNDS;
 168         return NULL;
 169 }
 170
 171 /*
 172  * Starts a walk.  If the @xas is already valid, we assume that it's on
 173  * the right path and just return where we've got to.  If we're in an
 174  * error state, return NULL.  If the index is outside the current scope
 175  * of the xarray, return NULL without changing @xas->xa_node.  Otherwise
 176  * set @xas->xa_node to NULL and return the current head of the array.
 177  */
 178 static void *xas_start(struct xa_state *xas)
 179 {
 180         void *entry;
 181
 182         if (xas_valid(xas))
 183                 return xas_reload(xas);
 184         if (xas_error(xas))
 185                 return NULL;
 186
 187         entry = xa_head(xas->xa);
 188         if (!xa_is_node(entry)) {
 189                 if (xas->xa_index)
 190                         return set_bounds(xas);
 191         } else {
 192                 if ((xas->xa_index >> xa_to_node(entry)->shift) > XA_CHUNK_MASK)
 193                         return set_bounds(xas);
 194         }
 195
 196         xas->xa_node = NULL;
 197         return entry;
 198 }
 199
 200 static void *xas_descend(struct xa_state *xas, struct xa_node *node)
 201 {
 202         unsigned int offset = get_offset(xas->xa_index, node);
 203         void *entry = xa_entry(xas->xa, node, offset);
 204
 205         xas->xa_node = node;
 206         if (xa_is_sibling(entry)) {
 207                 offset = xa_to_sibling(entry);
 208                 entry = xa_entry(xas->xa, node, offset);
 209         }
 210
 211         xas->xa_offset = offset;
 212         return entry;
 213 }
 214
 215 /**
 216  * xas_load() - Load an entry from the XArray (advanced).
 217  * @xas: XArray operation state.
 218  *
 219  * Usually walks the @xas to the appropriate state to load the entry
 220  * stored at xa_index.  However, it will do nothing and return %NULL if
 221  * @xas is in an error state.  xas_load() will never expand the tree.
 222  *
 223  * If the xa_state is set up to operate on a multi-index entry, xas_load()
 224  * may return %NULL or an internal entry, even if there are entries
 225  * present within the range specified by @xas.
 226  *
 227  * Context: Any context.  The caller should hold the xa_lock or the RCU lock.
 228  * Return: Usually an entry in the XArray, but see description for exceptions.
 229  */
 230 void *xas_load(struct xa_state *xas)
 231 {
 232         void *entry = xas_start(xas);
 233
 234         while (xa_is_node(entry)) {
 235                 struct xa_node *node = xa_to_node(entry);
 236
 237                 if (xas->xa_shift > node->shift)
 238                         break;
 239                 entry = xas_descend(xas, node);
 240                 if (node->shift == 0)
 241                         break;
 242         }
 243         return entry;
 244 }
 245 EXPORT_SYMBOL_GPL(xas_load);
 246
 247 /* Move the radix tree node cache here */
 248 extern struct kmem_cache *radix_tree_node_cachep;
 249 extern void radix_tree_node_rcu_free(struct rcu_head *head);
 250
 251 #define XA_RCU_FREE     ((struct xarray *)1)
 252
 253 static void xa_node_free(struct xa_node *node)
 254 {
 255         XA_NODE_BUG_ON(node, !list_empty(&node->private_list));
 256         node->array = XA_RCU_FREE;
 257         call_rcu(&node->rcu_head, radix_tree_node_rcu_free);
 258 }
 259
 260 /*
 261  * xas_destroy() - Free any resources allocated during the XArray operation.
 262  * @xas: XArray operation state.
 263  *
 264  * This function is now internal-only.
 265  */
 266 static void xas_destroy(struct xa_state *xas)
 267 {
 268         struct xa_node *node = xas->xa_alloc;
 269
 270         if (!node)
 271                 return;
 272         XA_NODE_BUG_ON(node, !list_empty(&node->private_list));
 273         kmem_cache_free(radix_tree_node_cachep, node);
 274         xas->xa_alloc = NULL;
 275 }
 276
 277 /**
 278  * xas_nomem() - Allocate memory if needed.
 279  * @xas: XArray operation state.
 280  * @gfp: Memory allocation flags.
 281  *
 282  * If we need to add new nodes to the XArray, we try to allocate memory
 283  * with GFP_NOWAIT while holding the lock, which will usually succeed.
 284  * If it fails, @xas is flagged as needing memory to continue.  The caller
 285  * should drop the lock and call xas_nomem().  If xas_nomem() succeeds,
 286  * the caller should retry the operation.
 287  *
 288  * Forward progress is guaranteed as one node is allocated here and
 289  * stored in the xa_state where it will be found by xas_alloc().  More
 290  * nodes will likely be found in the slab allocator, but we do not tie
 291  * them up here.
 292  *
 293  * Return: true if memory was needed, and was successfully allocated.
 294  */
 295 bool xas_nomem(struct xa_state *xas, gfp_t gfp)
 296 {
 297         if (xas->xa_node != XA_ERROR(-ENOMEM)) {
 298                 xas_destroy(xas);
 299                 return false;
 300         }
 301         xas->xa_alloc = kmem_cache_alloc(radix_tree_node_cachep, gfp);
 302         if (!xas->xa_alloc)
 303                 return false;
 304         XA_NODE_BUG_ON(xas->xa_alloc, !list_empty(&xas->xa_alloc->private_list));
 305         xas->xa_node = XAS_RESTART;
 306         return true;
 307 }
 308 EXPORT_SYMBOL_GPL(xas_nomem);
 309
 310 /*
 311  * __xas_nomem() - Drop locks and allocate memory if needed.
 312  * @xas: XArray operation state.
 313  * @gfp: Memory allocation flags.
 314  *
 315  * Internal variant of xas_nomem().
 316  *
 317  * Return: true if memory was needed, and was successfully allocated.
 318  */
 319 static bool __xas_nomem(struct xa_state *xas, gfp_t gfp)
 320         __must_hold(xas->xa->xa_lock)
 321 {
 322         unsigned int lock_type = xa_lock_type(xas->xa);
 323
 324         if (xas->xa_node != XA_ERROR(-ENOMEM)) {
 325                 xas_destroy(xas);
 326                 return false;
 327         }
 328         if (gfpflags_allow_blocking(gfp)) {
 329                 xas_unlock_type(xas, lock_type);
 330                 xas->xa_alloc = kmem_cache_alloc(radix_tree_node_cachep, gfp);
 331                 xas_lock_type(xas, lock_type);
 332         } else {
 333                 xas->xa_alloc = kmem_cache_alloc(radix_tree_node_cachep, gfp);
 334         }
 335         if (!xas->xa_alloc)
 336                 return false;
 337         XA_NODE_BUG_ON(xas->xa_alloc, !list_empty(&xas->xa_alloc->private_list));
 338         xas->xa_node = XAS_RESTART;
 339         return true;
 340 }
 341
 342 static void xas_update(struct xa_state *xas, struct xa_node *node)
 343 {
 344         if (xas->xa_update)
 345                 xas->xa_update(node);
 346         else
 347                 XA_NODE_BUG_ON(node, !list_empty(&node->private_list));
 348 }
 349
 350 static void *xas_alloc(struct xa_state *xas, unsigned int shift)
 351 {
 352         struct xa_node *parent = xas->xa_node;
 353         struct xa_node *node = xas->xa_alloc;
 354
 355         if (xas_invalid(xas))
 356                 return NULL;
 357
 358         if (node) {
 359                 xas->xa_alloc = NULL;
 360         } else {
 361                 node = kmem_cache_alloc(radix_tree_node_cachep,
 362                                         GFP_NOWAIT | __GFP_NOWARN);
 363                 if (!node) {
 364                         xas_set_err(xas, -ENOMEM);
 365                         return NULL;
 366                 }
 367         }
 368
 369         if (parent) {
 370                 node->offset = xas->xa_offset;
 371                 parent->count++;
 372                 XA_NODE_BUG_ON(node, parent->count > XA_CHUNK_SIZE);
 373                 xas_update(xas, parent);
 374         }
 375         XA_NODE_BUG_ON(node, shift > BITS_PER_LONG);
 376         XA_NODE_BUG_ON(node, !list_empty(&node->private_list));
 377         node->shift = shift;
 378         node->count = 0;
 379         node->nr_values = 0;
 380         RCU_INIT_POINTER(node->parent, xas->xa_node);
 381         node->array = xas->xa;
 382
 383         return node;
 384 }
 385
 386 #ifdef CONFIG_XARRAY_MULTI
 387 /* Returns the number of indices covered by a given xa_state */
 388 static unsigned long xas_size(const struct xa_state *xas)
 389 {
 390         return (xas->xa_sibs + 1UL) << xas->xa_shift;
 391 }
 392 #endif
 393
 394 /*
 395  * Use this to calculate the maximum index that will need to be created
 396  * in order to add the entry described by @xas.  Because we cannot store a
 397  * multiple-index entry at index 0, the calculation is a little more complex
 398  * than you might expect.
 399  */
 400 static unsigned long xas_max(struct xa_state *xas)
 401 {
 402         unsigned long max = xas->xa_index;
 403
 404 #ifdef CONFIG_XARRAY_MULTI
 405         if (xas->xa_shift || xas->xa_sibs) {
 406                 unsigned long mask = xas_size(xas) - 1;
 407                 max |= mask;
 408                 if (mask == max)
 409                         max++;
 410         }
 411 #endif
 412
 413         return max;
 414 }
 415
 416 /* The maximum index that can be contained in the array without expanding it */
 417 static unsigned long max_index(void *entry)
 418 {
 419         if (!xa_is_node(entry))
 420                 return 0;
 421         return (XA_CHUNK_SIZE << xa_to_node(entry)->shift) - 1;
 422 }
 423
 424 static void xas_shrink(struct xa_state *xas)
 425 {
 426         struct xarray *xa = xas->xa;
 427         struct xa_node *node = xas->xa_node;
 428
 429         for (;;) {
 430                 void *entry;
 431
 432                 XA_NODE_BUG_ON(node, node->count > XA_CHUNK_SIZE);
 433                 if (node->count != 1)
 434                         break;
 435                 entry = xa_entry_locked(xa, node, 0);
 436                 if (!entry)
 437                         break;
 438                 if (!xa_is_node(entry) && node->shift)
 439                         break;
 440                 if (xa_is_zero(entry) && xa_zero_busy(xa))
 441                         entry = NULL;
 442                 xas->xa_node = XAS_BOUNDS;
 443
 444                 RCU_INIT_POINTER(xa->xa_head, entry);
 445                 if (xa_track_free(xa) && !node_get_mark(node, 0, XA_FREE_MARK))
 446                         xa_mark_clear(xa, XA_FREE_MARK);
 447
 448                 node->count = 0;
 449                 node->nr_values = 0;
 450                 if (!xa_is_node(entry))
 451                         RCU_INIT_POINTER(node->slots[0], XA_RETRY_ENTRY);
 452                 xas_update(xas, node);
 453                 xa_node_free(node);
 454                 if (!xa_is_node(entry))
 455                         break;
 456                 node = xa_to_node(entry);
 457                 node->parent = NULL;
 458         }
 459 }
 460
 461 /*
 462  * xas_delete_node() - Attempt to delete an xa_node
 463  * @xas: Array operation state.
 464  *
 465  * Attempts to delete the @xas->xa_node.  This will fail if xa->node has
 466  * a non-zero reference count.
 467  */
 468 static void xas_delete_node(struct xa_state *xas)
 469 {
 470         struct xa_node *node = xas->xa_node;
 471
 472         for (;;) {
 473                 struct xa_node *parent;
 474
 475                 XA_NODE_BUG_ON(node, node->count > XA_CHUNK_SIZE);
 476                 if (node->count)
 477                         break;
 478
 479                 parent = xa_parent_locked(xas->xa, node);
 480                 xas->xa_node = parent;
 481                 xas->xa_offset = node->offset;
 482                 xa_node_free(node);
 483
 484                 if (!parent) {
 485                         xas->xa->xa_head = NULL;
 486                         xas->xa_node = XAS_BOUNDS;
 487                         return;
 488                 }
 489
 490                 parent->slots[xas->xa_offset] = NULL;
 491                 parent->count--;
 492                 XA_NODE_BUG_ON(parent, parent->count > XA_CHUNK_SIZE);
 493                 node = parent;
 494                 xas_update(xas, node);
 495         }
 496
 497         if (!node->parent)
 498                 xas_shrink(xas);
 499 }
 500
 501 /**
 502  * xas_free_nodes() - Free this node and all nodes that it references
 503  * @xas: Array operation state.
 504  * @top: Node to free
 505  *
 506  * This node has been removed from the tree.  We must now free it and all
 507  * of its subnodes.  There may be RCU walkers with references into the tree,
 508  * so we must replace all entries with retry markers.
 509  */
 510 static void xas_free_nodes(struct xa_state *xas, struct xa_node *top)
 511 {
 512         unsigned int offset = 0;
 513         struct xa_node *node = top;
 514
 515         for (;;) {
 516                 void *entry = xa_entry_locked(xas->xa, node, offset);
 517
 518                 if (node->shift && xa_is_node(entry)) {
 519                         node = xa_to_node(entry);
 520                         offset = 0;
 521                         continue;
 522                 }
 523                 if (entry)
 524                         RCU_INIT_POINTER(node->slots[offset], XA_RETRY_ENTRY);
 525                 offset++;
 526                 while (offset == XA_CHUNK_SIZE) {
 527                         struct xa_node *parent;
 528
 529                         parent = xa_parent_locked(xas->xa, node);
 530                         offset = node->offset + 1;
 531                         node->count = 0;
 532                         node->nr_values = 0;
 533                         xas_update(xas, node);
 534                         xa_node_free(node);
 535                         if (node == top)
 536                                 return;
 537                         node = parent;
 538                 }
 539         }
 540 }
 541
 542 /*
 543  * xas_expand adds nodes to the head of the tree until it has reached
 544  * sufficient height to be able to contain @xas->xa_index
 545  */
 546 static int xas_expand(struct xa_state *xas, void *head)
 547 {
 548         struct xarray *xa = xas->xa;
 549         struct xa_node *node = NULL;
 550         unsigned int shift = 0;
 551         unsigned long max = xas_max(xas);
 552
 553         if (!head) {
 554                 if (max == 0)
 555                         return 0;
 556                 while ((max >> shift) >= XA_CHUNK_SIZE)
 557                         shift += XA_CHUNK_SHIFT;
 558                 return shift + XA_CHUNK_SHIFT;
 559         } else if (xa_is_node(head)) {
 560                 node = xa_to_node(head);
 561                 shift = node->shift + XA_CHUNK_SHIFT;
 562         }
 563         xas->xa_node = NULL;
 564
 565         while (max > max_index(head)) {
 566                 xa_mark_t mark = 0;
 567
 568                 XA_NODE_BUG_ON(node, shift > BITS_PER_LONG);
 569                 node = xas_alloc(xas, shift);
 570                 if (!node)
 571                         return -ENOMEM;
 572
 573                 node->count = 1;
 574                 if (xa_is_value(head))
 575                         node->nr_values = 1;
 576                 RCU_INIT_POINTER(node->slots[0], head);
 577
 578                 /* Propagate the aggregated mark info to the new child */
 579                 for (;;) {
 580                         if (xa_track_free(xa) && mark == XA_FREE_MARK) {
 581                                 node_mark_all(node, XA_FREE_MARK);
 582                                 if (!xa_marked(xa, XA_FREE_MARK)) {
 583                                         node_clear_mark(node, 0, XA_FREE_MARK);
 584                                         xa_mark_set(xa, XA_FREE_MARK);
 585                                 }
 586                         } else if (xa_marked(xa, mark)) {
 587                                 node_set_mark(node, 0, mark);
 588                         }
 589                         if (mark == XA_MARK_MAX)
 590                                 break;
 591                         mark_inc(mark);
 592                 }
 593
 594                 /*
 595                  * Now that the new node is fully initialised, we can add
 596                  * it to the tree
 597                  */
 598                 if (xa_is_node(head)) {
 599                         xa_to_node(head)->offset = 0;
 600                         rcu_assign_pointer(xa_to_node(head)->parent, node);
 601                 }
 602                 head = xa_mk_node(node);
 603                 rcu_assign_pointer(xa->xa_head, head);
 604                 xas_update(xas, node);
 605
 606                 shift += XA_CHUNK_SHIFT;
 607         }
 608
 609         xas->xa_node = node;
 610         return shift;
 611 }
 612
 613 /*
 614  * xas_create() - Create a slot to store an entry in.
 615  * @xas: XArray operation state.
 616  * @allow_root: %true if we can store the entry in the root directly
 617  *
 618  * Most users will not need to call this function directly, as it is called
 619  * by xas_store().  It is useful for doing conditional store operations
 620  * (see the xa_cmpxchg() implementation for an example).
 621  *
 622  * Return: If the slot already existed, returns the contents of this slot.
 623  * If the slot was newly created, returns %NULL.  If it failed to create the
 624  * slot, returns %NULL and indicates the error in @xas.
 625  */
 626 static void *xas_create(struct xa_state *xas, bool allow_root)
 627 {
 628         struct xarray *xa = xas->xa;
 629         void *entry;
 630         void __rcu **slot;
 631         struct xa_node *node = xas->xa_node;
 632         int shift;
 633         unsigned int order = xas->xa_shift;
 634
 635         if (xas_top(node)) {
 636                 entry = xa_head_locked(xa);
 637                 xas->xa_node = NULL;
 638                 if (!entry && xa_zero_busy(xa))
 639                         entry = XA_ZERO_ENTRY;
 640                 shift = xas_expand(xas, entry);
 641                 if (shift < 0)
 642                         return NULL;
 643                 if (!shift && !allow_root)
 644                         shift = XA_CHUNK_SHIFT;
 645                 entry = xa_head_locked(xa);
 646                 slot = &xa->xa_head;
 647         } else if (xas_error(xas)) {
 648                 return NULL;
 649         } else if (node) {
 650                 unsigned int offset = xas->xa_offset;
 651
 652                 shift = node->shift;
 653                 entry = xa_entry_locked(xa, node, offset);
 654                 slot = &node->slots[offset];
 655         } else {
 656                 shift = 0;
 657                 entry = xa_head_locked(xa);
 658                 slot = &xa->xa_head;
 659         }
 660
 661         while (shift > order) {
 662                 shift -= XA_CHUNK_SHIFT;
 663                 if (!entry) {
 664                         node = xas_alloc(xas, shift);
 665                         if (!node)
 666                                 break;
 667                         if (xa_track_free(xa))
 668                                 node_mark_all(node, XA_FREE_MARK);
 669                         rcu_assign_pointer(*slot, xa_mk_node(node));
 670                 } else if (xa_is_node(entry)) {
 671                         node = xa_to_node(entry);
 672                 } else {
 673                         break;
 674                 }
 675                 entry = xas_descend(xas, node);
 676                 slot = &node->slots[xas->xa_offset];
 677         }
 678
 679         return entry;
 680 }
 681
 682 /**
 683  * xas_create_range() - Ensure that stores to this range will succeed
 684  * @xas: XArray operation state.
 685  *
 686  * Creates all of the slots in the range covered by @xas.  Sets @xas to
 687  * create single-index entries and positions it at the beginning of the
 688  * range.  This is for the benefit of users which have not yet been
 689  * converted to use multi-index entries.
 690  */
 691 void xas_create_range(struct xa_state *xas)
 692 {
 693         unsigned long index = xas->xa_index;
 694         unsigned char shift = xas->xa_shift;
 695         unsigned char sibs = xas->xa_sibs;
 696
 697         xas->xa_index |= ((sibs + 1) << shift) - 1;
 698         if (xas_is_node(xas) && xas->xa_node->shift == xas->xa_shift)
 699                 xas->xa_offset |= sibs;
 700         xas->xa_shift = 0;
 701         xas->xa_sibs = 0;
 702
 703         for (;;) {
 704                 xas_create(xas, true);
 705                 if (xas_error(xas))
 706                         goto restore;
 707                 if (xas->xa_index <= (index | XA_CHUNK_MASK))
 708                         goto success;
 709                 xas->xa_index -= XA_CHUNK_SIZE;
 710
 711                 for (;;) {
 712                         struct xa_node *node = xas->xa_node;
 713                         xas->xa_node = xa_parent_locked(xas->xa, node);
 714                         xas->xa_offset = node->offset - 1;
 715                         if (node->offset != 0)
 716                                 break;
 717                 }
 718         }
 719
 720 restore:
 721         xas->xa_shift = shift;
 722         xas->xa_sibs = sibs;
 723         xas->xa_index = index;
 724         return;
 725 success:
 726         xas->xa_index = index;
 727         if (xas->xa_node)
 728                 xas_set_offset(xas);
 729 }
 730 EXPORT_SYMBOL_GPL(xas_create_range);
 731
 732 static void update_node(struct xa_state *xas, struct xa_node *node,
 733                 int count, int values)
 734 {
 735         if (!node || (!count && !values))
 736                 return;
 737
 738         node->count += count;
 739         node->nr_values += values;
 740         XA_NODE_BUG_ON(node, node->count > XA_CHUNK_SIZE);
 741         XA_NODE_BUG_ON(node, node->nr_values > XA_CHUNK_SIZE);
 742         xas_update(xas, node);
 743         if (count < 0)
 744                 xas_delete_node(xas);
 745 }
 746
 747 /**
 748  * xas_store() - Store this entry in the XArray.
 749  * @xas: XArray operation state.
 750  * @entry: New entry.
 751  *
 752  * If @xas is operating on a multi-index entry, the entry returned by this
 753  * function is essentially meaningless (it may be an internal entry or it
 754  * may be %NULL, even if there are non-NULL entries at some of the indices
 755  * covered by the range).  This is not a problem for any current users,
 756  * and can be changed if needed.
 757  *
 758  * Return: The old entry at this index.
 759  */
 760 void *xas_store(struct xa_state *xas, void *entry)
 761 {
 762         struct xa_node *node;
 763         void __rcu **slot = &xas->xa->xa_head;
 764         unsigned int offset, max;
 765         int count = 0;
 766         int values = 0;
 767         void *first, *next;
 768         bool value = xa_is_value(entry);
 769
 770         if (entry) {
 771                 bool allow_root = !xa_is_node(entry) && !xa_is_zero(entry);
 772                 first = xas_create(xas, allow_root);
 773         } else {
 774                 first = xas_load(xas);
 775         }
 776
 777         if (xas_invalid(xas))
 778                 return first;
 779         node = xas->xa_node;
 780         if (node && (xas->xa_shift < node->shift))
 781                 xas->xa_sibs = 0;
 782         if ((first == entry) && !xas->xa_sibs)
 783                 return first;
 784
 785         next = first;
 786         offset = xas->xa_offset;
 787         max = xas->xa_offset + xas->xa_sibs;
 788         if (node) {
 789                 slot = &node->slots[offset];
 790                 if (xas->xa_sibs)
 791                         xas_squash_marks(xas);
 792         }
 793         if (!entry)
 794                 xas_init_marks(xas);
 795
 796         for (;;) {
 797                 /*
 798                  * Must clear the marks before setting the entry to NULL,
 799                  * otherwise xas_for_each_marked may find a NULL entry and
 800                  * stop early.  rcu_assign_pointer contains a release barrier
 801                  * so the mark clearing will appear to happen before the
 802                  * entry is set to NULL.
 803                  */
 804                 rcu_assign_pointer(*slot, entry);
 805                 if (xa_is_node(next) && (!node || node->shift))
 806                         xas_free_nodes(xas, xa_to_node(next));
 807                 if (!node)
 808                         break;
 809                 count += !next - !entry;
 810                 values += !xa_is_value(first) - !value;
 811                 if (entry) {
 812                         if (offset == max)
 813                                 break;
 814                         if (!xa_is_sibling(entry))
 815                                 entry = xa_mk_sibling(xas->xa_offset);
 816                 } else {
 817                         if (offset == XA_CHUNK_MASK)
 818                                 break;
 819                 }
 820                 next = xa_entry_locked(xas->xa, node, ++offset);
 821                 if (!xa_is_sibling(next)) {
 822                         if (!entry && (offset > max))
 823                                 break;
 824                         first = next;
 825                 }
 826                 slot++;
 827         }
 828
 829         update_node(xas, node, count, values);
 830         return first;
 831 }
 832 EXPORT_SYMBOL_GPL(xas_store);
 833
 834 /**
 835  * xas_get_mark() - Returns the state of this mark.
 836  * @xas: XArray operation state.
 837  * @mark: Mark number.
 838  *
 839  * Return: true if the mark is set, false if the mark is clear or @xas
 840  * is in an error state.
 841  */
 842 bool xas_get_mark(const struct xa_state *xas, xa_mark_t mark)
 843 {
 844         if (xas_invalid(xas))
 845                 return false;
 846         if (!xas->xa_node)
 847                 return xa_marked(xas->xa, mark);
 848         return node_get_mark(xas->xa_node, xas->xa_offset, mark);
 849 }
 850 EXPORT_SYMBOL_GPL(xas_get_mark);
 851
 852 /**
 853  * xas_set_mark() - Sets the mark on this entry and its parents.
 854  * @xas: XArray operation state.
 855  * @mark: Mark number.
 856  *
 857  * Sets the specified mark on this entry, and walks up the tree setting it
 858  * on all the ancestor entries.  Does nothing if @xas has not been walked to
 859  * an entry, or is in an error state.
 860  */
 861 void xas_set_mark(const struct xa_state *xas, xa_mark_t mark)
 862 {
 863         struct xa_node *node = xas->xa_node;
 864         unsigned int offset = xas->xa_offset;
 865
 866         if (xas_invalid(xas))
 867                 return;
 868
 869         while (node) {
 870                 if (node_set_mark(node, offset, mark))
 871                         return;
 872                 offset = node->offset;
 873                 node = xa_parent_locked(xas->xa, node);
 874         }
 875
 876         if (!xa_marked(xas->xa, mark))
 877                 xa_mark_set(xas->xa, mark);
 878 }
 879 EXPORT_SYMBOL_GPL(xas_set_mark);
 880
 881 /**
 882  * xas_clear_mark() - Clears the mark on this entry and its parents.
 883  * @xas: XArray operation state.
 884  * @mark: Mark number.
 885  *
 886  * Clears the specified mark on this entry, and walks back to the head
 887  * attempting to clear it on all the ancestor entries.  Does nothing if
 888  * @xas has not been walked to an entry, or is in an error state.
 889  */
 890 void xas_clear_mark(const struct xa_state *xas, xa_mark_t mark)
 891 {
 892         struct xa_node *node = xas->xa_node;
 893         unsigned int offset = xas->xa_offset;
 894
 895         if (xas_invalid(xas))
 896                 return;
 897
 898         while (node) {
 899                 if (!node_clear_mark(node, offset, mark))
 900                         return;
 901                 if (node_any_mark(node, mark))
 902                         return;
 903
 904                 offset = node->offset;
 905                 node = xa_parent_locked(xas->xa, node);
 906         }
 907
 908         if (xa_marked(xas->xa, mark))
 909                 xa_mark_clear(xas->xa, mark);
 910 }
 911 EXPORT_SYMBOL_GPL(xas_clear_mark);
 912
 913 /**
 914  * xas_init_marks() - Initialise all marks for the entry
 915  * @xas: Array operations state.
 916  *
 917  * Initialise all marks for the entry specified by @xas.  If we're tracking
 918  * free entries with a mark, we need to set it on all entries.  All other
 919  * marks are cleared.
 920  *
 921  * This implementation is not as efficient as it could be; we may walk
 922  * up the tree multiple times.
 923  */
 924 void xas_init_marks(const struct xa_state *xas)
 925 {
 926         xa_mark_t mark = 0;
 927
 928         for (;;) {
 929                 if (xa_track_free(xas->xa) && mark == XA_FREE_MARK)
 930                         xas_set_mark(xas, mark);
 931                 else
 932                         xas_clear_mark(xas, mark);
 933                 if (mark == XA_MARK_MAX)
 934                         break;
 935                 mark_inc(mark);
 936         }
 937 }
 938 EXPORT_SYMBOL_GPL(xas_init_marks);
 939
 940 /**
 941  * xas_pause() - Pause a walk to drop a lock.
 942  * @xas: XArray operation state.
 943  *
 944  * Some users need to pause a walk and drop the lock they're holding in
 945  * order to yield to a higher priority thread or carry out an operation
 946  * on an entry.  Those users should call this function before they drop
 947  * the lock.  It resets the @xas to be suitable for the next iteration
 948  * of the loop after the user has reacquired the lock.  If most entries
 949  * found during a walk require you to call xas_pause(), the xa_for_each()
 950  * iterator may be more appropriate.
 951  *
 952  * Note that xas_pause() only works for forward iteration.  If a user needs
 953  * to pause a reverse iteration, we will need a xas_pause_rev().
 954  */
 955 void xas_pause(struct xa_state *xas)
 956 {
 957         struct xa_node *node = xas->xa_node;
 958
 959         if (xas_invalid(xas))
 960                 return;
 961
 962         if (node) {
 963                 unsigned int offset = xas->xa_offset;
 964                 while (++offset < XA_CHUNK_SIZE) {
 965                         if (!xa_is_sibling(xa_entry(xas->xa, node, offset)))
 966                                 break;
 967                 }
 968                 xas->xa_index += (offset - xas->xa_offset) << node->shift;
 969         } else {
 970                 xas->xa_index++;
 971         }
 972         xas->xa_node = XAS_RESTART;
 973 }
 974 EXPORT_SYMBOL_GPL(xas_pause);
 975
 976 /*
 977  * __xas_prev() - Find the previous entry in the XArray.
 978  * @xas: XArray operation state.
 979  *
 980  * Helper function for xas_prev() which handles all the complex cases
 981  * out of line.
 982  */
 983 void *__xas_prev(struct xa_state *xas)
 984 {
 985         void *entry;
 986
 987         if (!xas_frozen(xas->xa_node))
 988                 xas->xa_index--;
 989         if (xas_not_node(xas->xa_node))
 990                 return xas_load(xas);
 991
 992         if (xas->xa_offset != get_offset(xas->xa_index, xas->xa_node))
 993                 xas->xa_offset--;
 994
 995         while (xas->xa_offset == 255) {
 996                 xas->xa_offset = xas->xa_node->offset - 1;
 997                 xas->xa_node = xa_parent(xas->xa, xas->xa_node);
 998                 if (!xas->xa_node)
 999                         return set_bounds(xas);
1000         }
1001
1002         for (;;) {
1003                 entry = xa_entry(xas->xa, xas->xa_node, xas->xa_offset);
1004                 if (!xa_is_node(entry))
1005                         return entry;
1006
1007                 xas->xa_node = xa_to_node(entry);
1008                 xas_set_offset(xas);
1009         }
1010 }
1011 EXPORT_SYMBOL_GPL(__xas_prev);
1012
1013 /*
1014  * __xas_next() - Find the next entry in the XArray.
1015  * @xas: XArray operation state.
1016  *
1017  * Helper function for xas_next() which handles all the complex cases
1018  * out of line.
1019  */
1020 void *__xas_next(struct xa_state *xas)
1021 {
1022         void *entry;
1023
1024         if (!xas_frozen(xas->xa_node))
1025                 xas->xa_index++;
1026         if (xas_not_node(xas->xa_node))
1027                 return xas_load(xas);
1028
1029         if (xas->xa_offset != get_offset(xas->xa_index, xas->xa_node))
1030                 xas->xa_offset++;
1031
1032         while (xas->xa_offset == XA_CHUNK_SIZE) {
1033                 xas->xa_offset = xas->xa_node->offset + 1;
1034                 xas->xa_node = xa_parent(xas->xa, xas->xa_node);
1035                 if (!xas->xa_node)
1036                         return set_bounds(xas);
1037         }
1038
1039         for (;;) {
1040                 entry = xa_entry(xas->xa, xas->xa_node, xas->xa_offset);
1041                 if (!xa_is_node(entry))
1042                         return entry;
1043
1044                 xas->xa_node = xa_to_node(entry);
1045                 xas_set_offset(xas);
1046         }
1047 }
1048 EXPORT_SYMBOL_GPL(__xas_next);
1049
1050 /**
1051  * xas_find() - Find the next present entry in the XArray.
1052  * @xas: XArray operation state.
1053  * @max: Highest index to return.
1054  *
1055  * If the @xas has not yet been walked to an entry, return the entry
1056  * which has an index >= xas.xa_index.  If it has been walked, the entry
1057  * currently being pointed at has been processed, and so we move to the
1058  * next entry.
1059  *
1060  * If no entry is found and the array is smaller than @max, the iterator
1061  * is set to the smallest index not yet in the array.  This allows @xas
1062  * to be immediately passed to xas_store().
1063  *
1064  * Return: The entry, if found, otherwise %NULL.
1065  */
1066 void *xas_find(struct xa_state *xas, unsigned long max)
1067 {
1068         void *entry;
1069
1070         if (xas_error(xas))
1071                 return NULL;
1072
1073         if (!xas->xa_node) {
1074                 xas->xa_index = 1;
1075                 return set_bounds(xas);
1076         } else if (xas_top(xas->xa_node)) {
1077                 entry = xas_load(xas);
1078                 if (entry || xas_not_node(xas->xa_node))
1079                         return entry;
1080         } else if (!xas->xa_node->shift &&
1081                     xas->xa_offset != (xas->xa_index & XA_CHUNK_MASK)) {
1082                 xas->xa_offset = ((xas->xa_index - 1) & XA_CHUNK_MASK) + 1;
1083         }
1084
1085         xas_advance(xas);
1086
1087         while (xas->xa_node && (xas->xa_index <= max)) {
1088                 if (unlikely(xas->xa_offset == XA_CHUNK_SIZE)) {
1089                         xas->xa_offset = xas->xa_node->offset + 1;
1090                         xas->xa_node = xa_parent(xas->xa, xas->xa_node);
1091                         continue;
1092                 }
1093
1094                 entry = xa_entry(xas->xa, xas->xa_node, xas->xa_offset);
1095                 if (xa_is_node(entry)) {
1096                         xas->xa_node = xa_to_node(entry);
1097                         xas->xa_offset = 0;
1098                         continue;
1099                 }
1100                 if (entry && !xa_is_sibling(entry))
1101                         return entry;
1102
1103                 xas_advance(xas);
1104         }
1105
1106         if (!xas->xa_node)
1107                 xas->xa_node = XAS_BOUNDS;
1108         return NULL;
1109 }
1110 EXPORT_SYMBOL_GPL(xas_find);
1111
1112 /**
1113  * xas_find_marked() - Find the next marked entry in the XArray.
1114  * @xas: XArray operation state.
1115  * @max: Highest index to return.
1116  * @mark: Mark number to search for.
1117  *
1118  * If the @xas has not yet been walked to an entry, return the marked entry
1119  * which has an index >= xas.xa_index.  If it has been walked, the entry
1120  * currently being pointed at has been processed, and so we return the
1121  * first marked entry with an index > xas.xa_index.
1122  *
1123  * If no marked entry is found and the array is smaller than @max, @xas is
1124  * set to the bounds state and xas->xa_index is set to the smallest index
1125  * not yet in the array.  This allows @xas to be immediately passed to
1126  * xas_store().
1127  *
1128  * If no entry is found before @max is reached, @xas is set to the restart
1129  * state.
1130  *
1131  * Return: The entry, if found, otherwise %NULL.
1132  */
1133 void *xas_find_marked(struct xa_state *xas, unsigned long max, xa_mark_t mark)
1134 {
1135         bool advance = true;
1136         unsigned int offset;
1137         void *entry;
1138
1139         if (xas_error(xas))
1140                 return NULL;
1141
1142         if (!xas->xa_node) {
1143                 xas->xa_index = 1;
1144                 goto out;
1145         } else if (xas_top(xas->xa_node)) {
1146                 advance = false;
1147                 entry = xa_head(xas->xa);
1148                 xas->xa_node = NULL;
1149                 if (xas->xa_index > max_index(entry))
1150                         goto out;
1151                 if (!xa_is_node(entry)) {
1152                         if (xa_marked(xas->xa, mark))
1153                                 return entry;
1154                         xas->xa_index = 1;
1155                         goto out;
1156                 }
1157                 xas->xa_node = xa_to_node(entry);
1158                 xas->xa_offset = xas->xa_index >> xas->xa_node->shift;
1159         }
1160
1161         while (xas->xa_index <= max) {
1162                 if (unlikely(xas->xa_offset == XA_CHUNK_SIZE)) {
1163                         xas->xa_offset = xas->xa_node->offset + 1;
1164                         xas->xa_node = xa_parent(xas->xa, xas->xa_node);
1165                         if (!xas->xa_node)
1166                                 break;
1167                         advance = false;
1168                         continue;
1169                 }
1170
1171                 if (!advance) {
1172                         entry = xa_entry(xas->xa, xas->xa_node, xas->xa_offset);
1173                         if (xa_is_sibling(entry)) {
1174                                 xas->xa_offset = xa_to_sibling(entry);
1175                                 xas_move_index(xas, xas->xa_offset);
1176                         }
1177                 }
1178
1179                 offset = xas_find_chunk(xas, advance, mark);
1180                 if (offset > xas->xa_offset) {
1181                         advance = false;
1182                         xas_move_index(xas, offset);
1183                         /* Mind the wrap */
1184                         if ((xas->xa_index - 1) >= max)
1185                                 goto max;
1186                         xas->xa_offset = offset;
1187                         if (offset == XA_CHUNK_SIZE)
1188                                 continue;
1189                 }
1190
1191                 entry = xa_entry(xas->xa, xas->xa_node, xas->xa_offset);
1192                 if (!xa_is_node(entry))
1193                         return entry;
1194                 xas->xa_node = xa_to_node(entry);
1195                 xas_set_offset(xas);
1196         }
1197
1198 out:
1199         if (xas->xa_index > max)
1200                 goto max;
1201         return set_bounds(xas);
1202 max:
1203         xas->xa_node = XAS_RESTART;
1204         return NULL;
1205 }
1206 EXPORT_SYMBOL_GPL(xas_find_marked);
1207
1208 /**
1209  * xas_find_conflict() - Find the next present entry in a range.
1210  * @xas: XArray operation state.
1211  *
1212  * The @xas describes both a range and a position within that range.
1213  *
1214  * Context: Any context.  Expects xa_lock to be held.
1215  * Return: The next entry in the range covered by @xas or %NULL.
1216  */
1217 void *xas_find_conflict(struct xa_state *xas)
1218 {
1219         void *curr;
1220
1221         if (xas_error(xas))
1222                 return NULL;
1223
1224         if (!xas->xa_node)
1225                 return NULL;
1226
1227         if (xas_top(xas->xa_node)) {
1228                 curr = xas_start(xas);
1229                 if (!curr)
1230                         return NULL;
1231                 while (xa_is_node(curr)) {
1232                         struct xa_node *node = xa_to_node(curr);
1233                         curr = xas_descend(xas, node);
1234                 }
1235                 if (curr)
1236                         return curr;
1237         }
1238
1239         if (xas->xa_node->shift > xas->xa_shift)
1240                 return NULL;
1241
1242         for (;;) {
1243                 if (xas->xa_node->shift == xas->xa_shift) {
1244                         if ((xas->xa_offset & xas->xa_sibs) == xas->xa_sibs)
1245                                 break;
1246                 } else if (xas->xa_offset == XA_CHUNK_MASK) {
1247                         xas->xa_offset = xas->xa_node->offset;
1248                         xas->xa_node = xa_parent_locked(xas->xa, xas->xa_node);
1249                         if (!xas->xa_node)
1250                                 break;
1251                         continue;
1252                 }
1253                 curr = xa_entry_locked(xas->xa, xas->xa_node, ++xas->xa_offset);
1254                 if (xa_is_sibling(curr))
1255                         continue;
1256                 while (xa_is_node(curr)) {
1257                         xas->xa_node = xa_to_node(curr);
1258                         xas->xa_offset = 0;
1259                         curr = xa_entry_locked(xas->xa, xas->xa_node, 0);
1260                 }
1261                 if (curr)
1262                         return curr;
1263         }
1264         xas->xa_offset -= xas->xa_sibs;
1265         return NULL;
1266 }
1267 EXPORT_SYMBOL_GPL(xas_find_conflict);
1268
1269 /**
1270  * xa_load() - Load an entry from an XArray.
1271  * @xa: XArray.
1272  * @index: index into array.
1273  *
1274  * Context: Any context.  Takes and releases the RCU lock.
1275  * Return: The entry at @index in @xa.
1276  */
1277 void *xa_load(struct xarray *xa, unsigned long index)
1278 {
1279         XA_STATE(xas, xa, index);
1280         void *entry;
1281
1282         rcu_read_lock();
1283         do {
1284                 entry = xas_load(&xas);
1285                 if (xa_is_zero(entry))
1286                         entry = NULL;
1287         } while (xas_retry(&xas, entry));
1288         rcu_read_unlock();
1289
1290         return entry;
1291 }
1292 EXPORT_SYMBOL(xa_load);
1293
1294 static void *xas_result(struct xa_state *xas, void *curr)
1295 {
1296         if (xa_is_zero(curr))
1297                 return NULL;
1298         if (xas_error(xas))
1299                 curr = xas->xa_node;
1300         return curr;
1301 }
1302
1303 /**
1304  * __xa_erase() - Erase this entry from the XArray while locked.
1305  * @xa: XArray.
1306  * @index: Index into array.
1307  *
1308  * After this function returns, loading from @index will return %NULL.
1309  * If the index is part of a multi-index entry, all indices will be erased
1310  * and none of the entries will be part of a multi-index entry.
1311  *
1312  * Context: Any context.  Expects xa_lock to be held on entry.
1313  * Return: The entry which used to be at this index.
1314  */
1315 void *__xa_erase(struct xarray *xa, unsigned long index)
1316 {
1317         XA_STATE(xas, xa, index);
1318         return xas_result(&xas, xas_store(&xas, NULL));
1319 }
1320 EXPORT_SYMBOL(__xa_erase);
1321
1322 /**
1323  * xa_erase() - Erase this entry from the XArray.
1324  * @xa: XArray.
1325  * @index: Index of entry.
1326  *
1327  * After this function returns, loading from @index will return %NULL.
1328  * If the index is part of a multi-index entry, all indices will be erased
1329  * and none of the entries will be part of a multi-index entry.
1330  *
1331  * Context: Any context.  Takes and releases the xa_lock.
1332  * Return: The entry which used to be at this index.
1333  */
1334 void *xa_erase(struct xarray *xa, unsigned long index)
1335 {
1336         void *entry;
1337
1338         xa_lock(xa);
1339         entry = __xa_erase(xa, index);
1340         xa_unlock(xa);
1341
1342         return entry;
1343 }
1344 EXPORT_SYMBOL(xa_erase);
1345
1346 /**
1347  * __xa_store() - Store this entry in the XArray.
1348  * @xa: XArray.
1349  * @index: Index into array.
1350  * @entry: New entry.
1351  * @gfp: Memory allocation flags.
1352  *
1353  * You must already be holding the xa_lock when calling this function.
1354  * It will drop the lock if needed to allocate memory, and then reacquire
1355  * it afterwards.
1356  *
1357  * Context: Any context.  Expects xa_lock to be held on entry.  May
1358  * release and reacquire xa_lock if @gfp flags permit.
1359  * Return: The old entry at this index or xa_err() if an error happened.
1360  */
1361 void *__xa_store(struct xarray *xa, unsigned long index, void *entry, gfp_t gfp)
1362 {
1363         XA_STATE(xas, xa, index);
1364         void *curr;
1365
1366         if (WARN_ON_ONCE(xa_is_advanced(entry)))
1367                 return XA_ERROR(-EINVAL);
1368         if (xa_track_free(xa) && !entry)
1369                 entry = XA_ZERO_ENTRY;
1370
1371         do {
1372                 curr = xas_store(&xas, entry);
1373                 if (xa_track_free(xa))
1374                         xas_clear_mark(&xas, XA_FREE_MARK);
1375         } while (__xas_nomem(&xas, gfp));
1376
1377         return xas_result(&xas, curr);
1378 }
1379 EXPORT_SYMBOL(__xa_store);
1380
1381 /**
1382  * xa_store() - Store this entry in the XArray.
1383  * @xa: XArray.
1384  * @index: Index into array.
1385  * @entry: New entry.
1386  * @gfp: Memory allocation flags.
1387  *
1388  * After this function returns, loads from this index will return @entry.
1389  * Storing into an existing multislot entry updates the entry of every index.
1390  * The marks associated with @index are unaffected unless @entry is %NULL.
1391  *
1392  * Context: Any context.  Takes and releases the xa_lock.
1393  * May sleep if the @gfp flags permit.
1394  * Return: The old entry at this index on success, xa_err(-EINVAL) if @entry
1395  * cannot be stored in an XArray, or xa_err(-ENOMEM) if memory allocation
1396  * failed.
1397  */
1398 void *xa_store(struct xarray *xa, unsigned long index, void *entry, gfp_t gfp)
1399 {
1400         void *curr;
1401
1402         xa_lock(xa);
1403         curr = __xa_store(xa, index, entry, gfp);
1404         xa_unlock(xa);
1405
1406         return curr;
1407 }
1408 EXPORT_SYMBOL(xa_store);
1409
1410 /**
1411  * __xa_cmpxchg() - Store this entry in the XArray.
1412  * @xa: XArray.
1413  * @index: Index into array.
1414  * @old: Old value to test against.
1415  * @entry: New entry.
1416  * @gfp: Memory allocation flags.
1417  *
1418  * You must already be holding the xa_lock when calling this function.
1419  * It will drop the lock if needed to allocate memory, and then reacquire
1420  * it afterwards.
1421  *
1422  * Context: Any context.  Expects xa_lock to be held on entry.  May
1423  * release and reacquire xa_lock if @gfp flags permit.
1424  * Return: The old entry at this index or xa_err() if an error happened.
1425  */
1426 void *__xa_cmpxchg(struct xarray *xa, unsigned long index,
1427                         void *old, void *entry, gfp_t gfp)
1428 {
1429         XA_STATE(xas, xa, index);
1430         void *curr;
1431
1432         if (WARN_ON_ONCE(xa_is_advanced(entry)))
1433                 return XA_ERROR(-EINVAL);
1434
1435         do {
1436                 curr = xas_load(&xas);
1437                 if (curr == old) {
1438                         xas_store(&xas, entry);
1439                         if (xa_track_free(xa) && entry && !curr)
1440                                 xas_clear_mark(&xas, XA_FREE_MARK);
1441                 }
1442         } while (__xas_nomem(&xas, gfp));
1443
1444         return xas_result(&xas, curr);
1445 }
1446 EXPORT_SYMBOL(__xa_cmpxchg);
1447
1448 /**
1449  * __xa_insert() - Store this entry in the XArray if no entry is present.
1450  * @xa: XArray.
1451  * @index: Index into array.
1452  * @entry: New entry.
1453  * @gfp: Memory allocation flags.
1454  *
1455  * Inserting a NULL entry will store a reserved entry (like xa_reserve())
1456  * if no entry is present.  Inserting will fail if a reserved entry is
1457  * present, even though loading from this index will return NULL.
1458  *
1459  * Context: Any context.  Expects xa_lock to be held on entry.  May
1460  * release and reacquire xa_lock if @gfp flags permit.
1461  * Return: 0 if the store succeeded.  -EBUSY if another entry was present.
1462  * -ENOMEM if memory could not be allocated.
1463  */
1464 int __xa_insert(struct xarray *xa, unsigned long index, void *entry, gfp_t gfp)
1465 {
1466         XA_STATE(xas, xa, index);
1467         void *curr;
1468
1469         if (WARN_ON_ONCE(xa_is_advanced(entry)))
1470                 return -EINVAL;
1471         if (!entry)
1472                 entry = XA_ZERO_ENTRY;
1473
1474         do {
1475                 curr = xas_load(&xas);
1476                 if (!curr) {
1477                         xas_store(&xas, entry);
1478                         if (xa_track_free(xa))
1479                                 xas_clear_mark(&xas, XA_FREE_MARK);
1480                 } else {
1481                         xas_set_err(&xas, -EBUSY);
1482                 }
1483         } while (__xas_nomem(&xas, gfp));
1484
1485         return xas_error(&xas);
1486 }
1487 EXPORT_SYMBOL(__xa_insert);
1488
1489 #ifdef CONFIG_XARRAY_MULTI
1490 static void xas_set_range(struct xa_state *xas, unsigned long first,
1491                 unsigned long last)
1492 {
1493         unsigned int shift = 0;
1494         unsigned long sibs = last - first;
1495         unsigned int offset = XA_CHUNK_MASK;
1496
1497         xas_set(xas, first);
1498
1499         while ((first & XA_CHUNK_MASK) == 0) {
1500                 if (sibs < XA_CHUNK_MASK)
1501                         break;
1502                 if ((sibs == XA_CHUNK_MASK) && (offset < XA_CHUNK_MASK))
1503                         break;
1504                 shift += XA_CHUNK_SHIFT;
1505                 if (offset == XA_CHUNK_MASK)
1506                         offset = sibs & XA_CHUNK_MASK;
1507                 sibs >>= XA_CHUNK_SHIFT;
1508                 first >>= XA_CHUNK_SHIFT;
1509         }
1510
1511         offset = first & XA_CHUNK_MASK;
1512         if (offset + sibs > XA_CHUNK_MASK)
1513                 sibs = XA_CHUNK_MASK - offset;
1514         if ((((first + sibs + 1) << shift) - 1) > last)
1515                 sibs -= 1;
1516
1517         xas->xa_shift = shift;
1518         xas->xa_sibs = sibs;
1519 }
1520
1521 /**
1522  * xa_store_range() - Store this entry at a range of indices in the XArray.
1523  * @xa: XArray.
1524  * @first: First index to affect.
1525  * @last: Last index to affect.
1526  * @entry: New entry.
1527  * @gfp: Memory allocation flags.
1528  *
1529  * After this function returns, loads from any index between @first and @last,
1530  * inclusive will return @entry.
1531  * Storing into an existing multislot entry updates the entry of every index.
1532  * The marks associated with @index are unaffected unless @entry is %NULL.
1533  *
1534  * Context: Process context.  Takes and releases the xa_lock.  May sleep
1535  * if the @gfp flags permit.
1536  * Return: %NULL on success, xa_err(-EINVAL) if @entry cannot be stored in
1537  * an XArray, or xa_err(-ENOMEM) if memory allocation failed.
1538  */
1539 void *xa_store_range(struct xarray *xa, unsigned long first,
1540                 unsigned long last, void *entry, gfp_t gfp)
1541 {
1542         XA_STATE(xas, xa, 0);
1543
1544         if (WARN_ON_ONCE(xa_is_internal(entry)))
1545                 return XA_ERROR(-EINVAL);
1546         if (last < first)
1547                 return XA_ERROR(-EINVAL);
1548
1549         do {
1550                 xas_lock(&xas);
1551                 if (entry) {
1552                         unsigned int order = BITS_PER_LONG;
1553                         if (last + 1)
1554                                 order = __ffs(last + 1);
1555                         xas_set_order(&xas, last, order);
1556                         xas_create(&xas, true);
1557                         if (xas_error(&xas))
1558                                 goto unlock;
1559                 }
1560                 do {
1561                         xas_set_range(&xas, first, last);
1562                         xas_store(&xas, entry);
1563                         if (xas_error(&xas))
1564                                 goto unlock;
1565                         first += xas_size(&xas);
1566                 } while (first <= last);
1567 unlock:
1568                 xas_unlock(&xas);
1569         } while (xas_nomem(&xas, gfp));
1570
1571         return xas_result(&xas, NULL);
1572 }
1573 EXPORT_SYMBOL(xa_store_range);
1574 #endif /* CONFIG_XARRAY_MULTI */
1575
1576 /**
1577  * __xa_alloc() - Find somewhere to store this entry in the XArray.
1578  * @xa: XArray.
1579  * @id: Pointer to ID.
1580  * @limit: Range for allocated ID.
1581  * @entry: New entry.
1582  * @gfp: Memory allocation flags.
1583  *
1584  * Finds an empty entry in @xa between @limit.min and @limit.max,
1585  * stores the index into the @id pointer, then stores the entry at
1586  * that index.  A concurrent lookup will not see an uninitialised @id.
1587  *
1588  * Context: Any context.  Expects xa_lock to be held on entry.  May
1589  * release and reacquire xa_lock if @gfp flags permit.
1590  * Return: 0 on success, -ENOMEM if memory could not be allocated or
1591  * -EBUSY if there are no free entries in @limit.
1592  */
1593 int __xa_alloc(struct xarray *xa, u32 *id, void *entry,
1594                 struct xa_limit limit, gfp_t gfp)
1595 {
1596         XA_STATE(xas, xa, 0);
1597
1598         if (WARN_ON_ONCE(xa_is_advanced(entry)))
1599                 return -EINVAL;
1600         if (WARN_ON_ONCE(!xa_track_free(xa)))
1601                 return -EINVAL;
1602
1603         if (!entry)
1604                 entry = XA_ZERO_ENTRY;
1605
1606         do {
1607                 xas.xa_index = limit.min;
1608                 xas_find_marked(&xas, limit.max, XA_FREE_MARK);
1609                 if (xas.xa_node == XAS_RESTART)
1610                         xas_set_err(&xas, -EBUSY);
1611                 else
1612                         *id = xas.xa_index;
1613                 xas_store(&xas, entry);
1614                 xas_clear_mark(&xas, XA_FREE_MARK);
1615         } while (__xas_nomem(&xas, gfp));
1616
1617         return xas_error(&xas);
1618 }
1619 EXPORT_SYMBOL(__xa_alloc);
1620
1621 /**
1622  * __xa_alloc_cyclic() - Find somewhere to store this entry in the XArray.
1623  * @xa: XArray.
1624  * @id: Pointer to ID.
1625  * @entry: New entry.
1626  * @limit: Range of allocated ID.
1627  * @next: Pointer to next ID to allocate.
1628  * @gfp: Memory allocation flags.
1629  *
1630  * Finds an empty entry in @xa between @limit.min and @limit.max,
1631  * stores the index into the @id pointer, then stores the entry at
1632  * that index.  A concurrent lookup will not see an uninitialised @id.
1633  * The search for an empty entry will start at @next and will wrap
1634  * around if necessary.
1635  *
1636  * Context: Any context.  Expects xa_lock to be held on entry.  May
1637  * release and reacquire xa_lock if @gfp flags permit.
1638  * Return: 0 if the allocation succeeded without wrapping.  1 if the
1639  * allocation succeeded after wrapping, -ENOMEM if memory could not be
1640  * allocated or -EBUSY if there are no free entries in @limit.
1641  */
1642 int __xa_alloc_cyclic(struct xarray *xa, u32 *id, void *entry,
1643                 struct xa_limit limit, u32 *next, gfp_t gfp)
1644 {
1645         u32 min = limit.min;
1646         int ret;
1647
1648         limit.min = max(min, *next);
1649         ret = __xa_alloc(xa, id, entry, limit, gfp);
1650         if ((xa->xa_flags & XA_FLAGS_ALLOC_WRAPPED) && ret == 0) {
1651                 xa->xa_flags &= ~XA_FLAGS_ALLOC_WRAPPED;
1652                 ret = 1;
1653         }
1654
1655         if (ret < 0 && limit.min > min) {
1656                 limit.min = min;
1657                 ret = __xa_alloc(xa, id, entry, limit, gfp);
1658                 if (ret == 0)
1659                         ret = 1;
1660         }
1661
1662         if (ret >= 0) {
1663                 *next = *id + 1;
1664                 if (*next == 0)
1665                         xa->xa_flags |= XA_FLAGS_ALLOC_WRAPPED;
1666         }
1667         return ret;
1668 }
1669 EXPORT_SYMBOL(__xa_alloc_cyclic);
1670
1671 /**
1672  * __xa_set_mark() - Set this mark on this entry while locked.
1673  * @xa: XArray.
1674  * @index: Index of entry.
1675  * @mark: Mark number.
1676  *
1677  * Attempting to set a mark on a %NULL entry does not succeed.
1678  *
1679  * Context: Any context.  Expects xa_lock to be held on entry.
1680  */
1681 void __xa_set_mark(struct xarray *xa, unsigned long index, xa_mark_t mark)
1682 {
1683         XA_STATE(xas, xa, index);
1684         void *entry = xas_load(&xas);
1685
1686         if (entry)
1687                 xas_set_mark(&xas, mark);
1688 }
1689 EXPORT_SYMBOL(__xa_set_mark);
1690
1691 /**
1692  * __xa_clear_mark() - Clear this mark on this entry while locked.
1693  * @xa: XArray.
1694  * @index: Index of entry.
1695  * @mark: Mark number.
1696  *
1697  * Context: Any context.  Expects xa_lock to be held on entry.
1698  */
1699 void __xa_clear_mark(struct xarray *xa, unsigned long index, xa_mark_t mark)
1700 {
1701         XA_STATE(xas, xa, index);
1702         void *entry = xas_load(&xas);
1703
1704         if (entry)
1705                 xas_clear_mark(&xas, mark);
1706 }
1707 EXPORT_SYMBOL(__xa_clear_mark);
1708
1709 /**
1710  * xa_get_mark() - Inquire whether this mark is set on this entry.
1711  * @xa: XArray.
1712  * @index: Index of entry.
1713  * @mark: Mark number.
1714  *
1715  * This function uses the RCU read lock, so the result may be out of date
1716  * by the time it returns.  If you need the result to be stable, use a lock.
1717  *
1718  * Context: Any context.  Takes and releases the RCU lock.
1719  * Return: True if the entry at @index has this mark set, false if it doesn't.
1720  */
1721 bool xa_get_mark(struct xarray *xa, unsigned long index, xa_mark_t mark)
1722 {
1723         XA_STATE(xas, xa, index);
1724         void *entry;
1725
1726         rcu_read_lock();
1727         entry = xas_start(&xas);
1728         while (xas_get_mark(&xas, mark)) {
1729                 if (!xa_is_node(entry))
1730                         goto found;
1731                 entry = xas_descend(&xas, xa_to_node(entry));
1732         }
1733         rcu_read_unlock();
1734         return false;
1735  found:
1736         rcu_read_unlock();
1737         return true;
1738 }
1739 EXPORT_SYMBOL(xa_get_mark);
1740
1741 /**
1742  * xa_set_mark() - Set this mark on this entry.
1743  * @xa: XArray.
1744  * @index: Index of entry.
1745  * @mark: Mark number.
1746  *
1747  * Attempting to set a mark on a %NULL entry does not succeed.
1748  *
1749  * Context: Process context.  Takes and releases the xa_lock.
1750  */
1751 void xa_set_mark(struct xarray *xa, unsigned long index, xa_mark_t mark)
1752 {
1753         xa_lock(xa);
1754         __xa_set_mark(xa, index, mark);
1755         xa_unlock(xa);
1756 }
1757 EXPORT_SYMBOL(xa_set_mark);
1758
1759 /**
1760  * xa_clear_mark() - Clear this mark on this entry.
1761  * @xa: XArray.
1762  * @index: Index of entry.
1763  * @mark: Mark number.
1764  *
1765  * Clearing a mark always succeeds.
1766  *
1767  * Context: Process context.  Takes and releases the xa_lock.
1768  */
1769 void xa_clear_mark(struct xarray *xa, unsigned long index, xa_mark_t mark)
1770 {
1771         xa_lock(xa);
1772         __xa_clear_mark(xa, index, mark);
1773         xa_unlock(xa);
1774 }
1775 EXPORT_SYMBOL(xa_clear_mark);
1776
1777 /**
1778  * xa_find() - Search the XArray for an entry.
1779  * @xa: XArray.
1780  * @indexp: Pointer to an index.
1781  * @max: Maximum index to search to.
1782  * @filter: Selection criterion.
1783  *
1784  * Finds the entry in @xa which matches the @filter, and has the lowest
1785  * index that is at least @indexp and no more than @max.
1786  * If an entry is found, @indexp is updated to be the index of the entry.
1787  * This function is protected by the RCU read lock, so it may not find
1788  * entries which are being simultaneously added.  It will not return an
1789  * %XA_RETRY_ENTRY; if you need to see retry entries, use xas_find().
1790  *
1791  * Context: Any context.  Takes and releases the RCU lock.
1792  * Return: The entry, if found, otherwise %NULL.
1793  */
1794 void *xa_find(struct xarray *xa, unsigned long *indexp,
1795                         unsigned long max, xa_mark_t filter)
1796 {
1797         XA_STATE(xas, xa, *indexp);
1798         void *entry;
1799
1800         rcu_read_lock();
1801         do {
1802                 if ((__force unsigned int)filter < XA_MAX_MARKS)
1803                         entry = xas_find_marked(&xas, max, filter);
1804                 else
1805                         entry = xas_find(&xas, max);
1806         } while (xas_retry(&xas, entry));
1807         rcu_read_unlock();
1808
1809         if (entry)
1810                 *indexp = xas.xa_index;
1811         return entry;
1812 }
1813 EXPORT_SYMBOL(xa_find);
1814
1815 /**
1816  * xa_find_after() - Search the XArray for a present entry.
1817  * @xa: XArray.
1818  * @indexp: Pointer to an index.
1819  * @max: Maximum index to search to.
1820  * @filter: Selection criterion.
1821  *
1822  * Finds the entry in @xa which matches the @filter and has the lowest
1823  * index that is above @indexp and no more than @max.
1824  * If an entry is found, @indexp is updated to be the index of the entry.
1825  * This function is protected by the RCU read lock, so it may miss entries
1826  * which are being simultaneously added.  It will not return an
1827  * %XA_RETRY_ENTRY; if you need to see retry entries, use xas_find().
1828  *
1829  * Context: Any context.  Takes and releases the RCU lock.
1830  * Return: The pointer, if found, otherwise %NULL.
1831  */
1832 void *xa_find_after(struct xarray *xa, unsigned long *indexp,
1833                         unsigned long max, xa_mark_t filter)
1834 {
1835         XA_STATE(xas, xa, *indexp + 1);
1836         void *entry;
1837
1838         rcu_read_lock();
1839         for (;;) {
1840                 if ((__force unsigned int)filter < XA_MAX_MARKS)
1841                         entry = xas_find_marked(&xas, max, filter);
1842                 else
1843                         entry = xas_find(&xas, max);
1844                 if (xas.xa_node == XAS_BOUNDS)
1845                         break;
1846                 if (xas.xa_shift) {
1847                         if (xas.xa_index & ((1UL << xas.xa_shift) - 1))
1848                                 continue;
1849                 } else {
1850                         if (xas.xa_offset < (xas.xa_index & XA_CHUNK_MASK))
1851                                 continue;
1852                 }
1853                 if (!xas_retry(&xas, entry))
1854                         break;
1855         }
1856         rcu_read_unlock();
1857
1858         if (entry)
1859                 *indexp = xas.xa_index;
1860         return entry;
1861 }
1862 EXPORT_SYMBOL(xa_find_after);
1863
1864 static unsigned int xas_extract_present(struct xa_state *xas, void **dst,
1865                         unsigned long max, unsigned int n)
1866 {
1867         void *entry;
1868         unsigned int i = 0;
1869
1870         rcu_read_lock();
1871         xas_for_each(xas, entry, max) {
1872                 if (xas_retry(xas, entry))
1873                         continue;
1874                 dst[i++] = entry;
1875                 if (i == n)
1876                         break;
1877         }
1878         rcu_read_unlock();
1879
1880         return i;
1881 }
1882
1883 static unsigned int xas_extract_marked(struct xa_state *xas, void **dst,
1884                         unsigned long max, unsigned int n, xa_mark_t mark)
1885 {
1886         void *entry;
1887         unsigned int i = 0;
1888
1889         rcu_read_lock();
1890         xas_for_each_marked(xas, entry, max, mark) {
1891                 if (xas_retry(xas, entry))
1892                         continue;
1893                 dst[i++] = entry;
1894                 if (i == n)
1895                         break;
1896         }
1897         rcu_read_unlock();
1898
1899         return i;
1900 }
1901
1902 /**
1903  * xa_extract() - Copy selected entries from the XArray into a normal array.
1904  * @xa: The source XArray to copy from.
1905  * @dst: The buffer to copy entries into.
1906  * @start: The first index in the XArray eligible to be selected.
1907  * @max: The last index in the XArray eligible to be selected.
1908  * @n: The maximum number of entries to copy.
1909  * @filter: Selection criterion.
1910  *
1911  * Copies up to @n entries that match @filter from the XArray.  The
1912  * copied entries will have indices between @start and @max, inclusive.
1913  *
1914  * The @filter may be an XArray mark value, in which case entries which are
1915  * marked with that mark will be copied.  It may also be %XA_PRESENT, in
1916  * which case all entries which are not %NULL will be copied.
1917  *
1918  * The entries returned may not represent a snapshot of the XArray at a
1919  * moment in time.  For example, if another thread stores to index 5, then
1920  * index 10, calling xa_extract() may return the old contents of index 5
1921  * and the new contents of index 10.  Indices not modified while this
1922  * function is running will not be skipped.
1923  *
1924  * If you need stronger guarantees, holding the xa_lock across calls to this
1925  * function will prevent concurrent modification.
1926  *
1927  * Context: Any context.  Takes and releases the RCU lock.
1928  * Return: The number of entries copied.
1929  */
1930 unsigned int xa_extract(struct xarray *xa, void **dst, unsigned long start,
1931                         unsigned long max, unsigned int n, xa_mark_t filter)
1932 {
1933         XA_STATE(xas, xa, start);
1934
1935         if (!n)
1936                 return 0;
1937
1938         if ((__force unsigned int)filter < XA_MAX_MARKS)
1939                 return xas_extract_marked(&xas, dst, max, n, filter);
1940         return xas_extract_present(&xas, dst, max, n);
1941 }
1942 EXPORT_SYMBOL(xa_extract);
1943
1944 /**
1945  * xa_destroy() - Free all internal data structures.
1946  * @xa: XArray.
1947  *
1948  * After calling this function, the XArray is empty and has freed all memory
1949  * allocated for its internal data structures.  You are responsible for
1950  * freeing the objects referenced by the XArray.
1951  *
1952  * Context: Any context.  Takes and releases the xa_lock, interrupt-safe.
1953  */
1954 void xa_destroy(struct xarray *xa)
1955 {
1956         XA_STATE(xas, xa, 0);
1957         unsigned long flags;
1958         void *entry;
1959
1960         xas.xa_node = NULL;
1961         xas_lock_irqsave(&xas, flags);
1962         entry = xa_head_locked(xa);
1963         RCU_INIT_POINTER(xa->xa_head, NULL);
1964         xas_init_marks(&xas);
1965         if (xa_zero_busy(xa))
1966                 xa_mark_clear(xa, XA_FREE_MARK);
1967         /* lockdep checks we're still holding the lock in xas_free_nodes() */
1968         if (xa_is_node(entry))
1969                 xas_free_nodes(&xas, xa_to_node(entry));
1970         xas_unlock_irqrestore(&xas, flags);
1971 }
1972 EXPORT_SYMBOL(xa_destroy);
1973
1974 #ifdef XA_DEBUG
1975 void xa_dump_node(const struct xa_node *node)
1976 {
1977         unsigned i, j;
1978
1979         if (!node)
1980                 return;
1981         if ((unsigned long)node & 3) {
1982                 pr_cont("node %px\n", node);
1983                 return;
1984         }
1985
1986         pr_cont("node %px %s %d parent %px shift %d count %d values %d "
1987                 "array %px list %px %px marks",
1988                 node, node->parent ? "offset" : "max", node->offset,
1989                 node->parent, node->shift, node->count, node->nr_values,
1990                 node->array, node->private_list.prev, node->private_list.next);
1991         for (i = 0; i < XA_MAX_MARKS; i++)
1992                 for (j = 0; j < XA_MARK_LONGS; j++)
1993                         pr_cont(" %lx", node->marks[i][j]);
1994         pr_cont("\n");
1995 }
1996
1997 void xa_dump_index(unsigned long index, unsigned int shift)
1998 {
1999         if (!shift)
2000                 pr_info("%lu: ", index);
2001         else if (shift >= BITS_PER_LONG)
2002                 pr_info("0-%lu: ", ~0UL);
2003         else
2004                 pr_info("%lu-%lu: ", index, index | ((1UL << shift) - 1));
2005 }
2006
2007 void xa_dump_entry(const void *entry, unsigned long index, unsigned long shift)
2008 {
2009         if (!entry)
2010                 return;
2011
2012         xa_dump_index(index, shift);
2013
2014         if (xa_is_node(entry)) {
2015                 if (shift == 0) {
2016                         pr_cont("%px\n", entry);
2017                 } else {
2018                         unsigned long i;
2019                         struct xa_node *node = xa_to_node(entry);
2020                         xa_dump_node(node);
2021                         for (i = 0; i < XA_CHUNK_SIZE; i++)
2022                                 xa_dump_entry(node->slots[i],
2023                                       index + (i << node->shift), node->shift);
2024                 }
2025         } else if (xa_is_value(entry))
2026                 pr_cont("value %ld (0x%lx) [%px]\n", xa_to_value(entry),
2027                                                 xa_to_value(entry), entry);
2028         else if (!xa_is_internal(entry))
2029                 pr_cont("%px\n", entry);
2030         else if (xa_is_retry(entry))
2031                 pr_cont("retry (%ld)\n", xa_to_internal(entry));
2032         else if (xa_is_sibling(entry))
2033                 pr_cont("sibling (slot %ld)\n", xa_to_sibling(entry));
2034         else if (xa_is_zero(entry))
2035                 pr_cont("zero (%ld)\n", xa_to_internal(entry));
2036         else
2037                 pr_cont("UNKNOWN ENTRY (%px)\n", entry);
2038 }
2039
2040 void xa_dump(const struct xarray *xa)
2041 {
2042         void *entry = xa->xa_head;
2043         unsigned int shift = 0;
2044
2045         pr_info("xarray: %px head %px flags %x marks %d %d %d\n", xa, entry,
2046                         xa->xa_flags, xa_marked(xa, XA_MARK_0),
2047                         xa_marked(xa, XA_MARK_1), xa_marked(xa, XA_MARK_2));
2048         if (xa_is_node(entry))
2049                 shift = xa_to_node(entry)->shift + XA_CHUNK_SHIFT;
2050         xa_dump_entry(entry, 0, shift);
2051 }
2052 #endif