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