xarray.c

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