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