projects/linux·blob v5.1-rc7 · refs

2052 lines · 52.5 KiB

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