projects/linux·blob v4.20-rc6 · refs

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