disable pwm7

hc

2024-05-10 23fa18eaa71266feff7ba8d83022d9e1cc83c65a

 kernel/lib/radix-tree.c
..
..
@@ -1,3 +1,4 @@
1
+// SPDX-License-Identifier: GPL-2.0-or-later
1
2
 /*
2
3
  * Copyright (C) 2001 Momchil Velikov
3
4
  * Portions Copyright (C) 2001 Christoph Hellwig
..
..
@@ -6,20 +7,6 @@
6
7
  * Copyright (C) 2012 Konstantin Khlebnikov
7
8
  * Copyright (C) 2016 Intel, Matthew Wilcox
8
9
  * Copyright (C) 2016 Intel, Ross Zwisler
9
- *
10
- * This program is free software; you can redistribute it and/or
11
- * modify it under the terms of the GNU General Public License as
12
- * published by the Free Software Foundation; either version 2, or (at
13
- * your option) any later version.
14
- *
15
- * This program is distributed in the hope that it will be useful, but
16
- * WITHOUT ANY WARRANTY; without even the implied warranty of
17
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
18
- * General Public License for more details.
19
- *
20
- * You should have received a copy of the GNU General Public License
21
- * along with this program; if not, write to the Free Software
22
- * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
23
10
  */
24
11
 
25
12
 #include <linux/bitmap.h>
..
..
@@ -38,15 +25,12 @@
38
25
 #include <linux/rcupdate.h>
39
26
 #include <linux/slab.h>
40
27
 #include <linux/string.h>
41
-
42
-
43
-/* Number of nodes in fully populated tree of given height */
44
-static unsigned long height_to_maxnodes[RADIX_TREE_MAX_PATH + 1] __read_mostly;
28
+#include <linux/xarray.h>
45
29
 
46
30
 /*
47
31
  * Radix tree node cache.
48
32
  */
49
-static struct kmem_cache *radix_tree_node_cachep;
33
+struct kmem_cache *radix_tree_node_cachep;
50
34
 
51
35
 /*
52
36
  * The radix tree is variable-height, so an insert operation not only has
..
..
@@ -71,22 +55,12 @@
71
55
 #define IDR_PRELOAD_SIZE	(IDR_MAX_PATH * 2 - 1)
72
56
 
73
57
 /*
74
- * The IDA is even shorter since it uses a bitmap at the last level.
75
- */
76
-#define IDA_INDEX_BITS		(8 * sizeof(int) - 1 - ilog2(IDA_BITMAP_BITS))
77
-#define IDA_MAX_PATH		(DIV_ROUND_UP(IDA_INDEX_BITS, \
78
-						RADIX_TREE_MAP_SHIFT))
79
-#define IDA_PRELOAD_SIZE	(IDA_MAX_PATH * 2 - 1)
80
-
81
-/*
82
58
  * Per-cpu pool of preloaded nodes
83
59
  */
84
-struct radix_tree_preload {
85
-	unsigned nr;
86
-	/* nodes->parent points to next preallocated node */
87
-	struct radix_tree_node *nodes;
60
+DEFINE_PER_CPU(struct radix_tree_preload, radix_tree_preloads) = {
61
+	.lock = INIT_LOCAL_LOCK(lock),
88
62
 };
89
-static DEFINE_PER_CPU(struct radix_tree_preload, radix_tree_preloads) = { 0, };
63
+EXPORT_PER_CPU_SYMBOL_GPL(radix_tree_preloads);
90
64
 
91
65
 static inline struct radix_tree_node *entry_to_node(void *ptr)
92
66
 {
..
..
@@ -98,24 +72,7 @@
98
72
 	return (void *)((unsigned long)ptr | RADIX_TREE_INTERNAL_NODE);
99
73
 }
100
74
 
101
-#define RADIX_TREE_RETRY	node_to_entry(NULL)
102
-
103
-#ifdef CONFIG_RADIX_TREE_MULTIORDER
104
-/* Sibling slots point directly to another slot in the same node */
105
-static inline
106
-bool is_sibling_entry(const struct radix_tree_node *parent, void *node)
107
-{
108
-	void __rcu **ptr = node;
109
-	return (parent->slots <= ptr) &&
110
-			(ptr < parent->slots + RADIX_TREE_MAP_SIZE);
111
-}
112
-#else
113
-static inline
114
-bool is_sibling_entry(const struct radix_tree_node *parent, void *node)
115
-{
116
-	return false;
117
-}
118
-#endif
75
+#define RADIX_TREE_RETRY	XA_RETRY_ENTRY
119
76
 
120
77
 static inline unsigned long
121
78
 get_slot_offset(const struct radix_tree_node *parent, void __rcu **slot)
..
..
@@ -129,24 +86,13 @@
129
86
 	unsigned int offset = (index >> parent->shift) & RADIX_TREE_MAP_MASK;
130
87
 	void __rcu **entry = rcu_dereference_raw(parent->slots[offset]);
131
88
 
132
-#ifdef CONFIG_RADIX_TREE_MULTIORDER
133
-	if (radix_tree_is_internal_node(entry)) {
134
-		if (is_sibling_entry(parent, entry)) {
135
-			void __rcu **sibentry;
136
-			sibentry = (void __rcu **) entry_to_node(entry);
137
-			offset = get_slot_offset(parent, sibentry);
138
-			entry = rcu_dereference_raw(*sibentry);
139
-		}
140
-	}
141
-#endif
142
-
143
89
 	*nodep = (void *)entry;
144
90
 	return offset;
145
91
 }
146
92
 
147
93
 static inline gfp_t root_gfp_mask(const struct radix_tree_root *root)
148
94
 {
149
-	return root->gfp_mask & (__GFP_BITS_MASK & ~GFP_ZONEMASK);
95
+	return root->xa_flags & (__GFP_BITS_MASK & ~GFP_ZONEMASK);
150
96
 }
151
97
 
152
98
 static inline void tag_set(struct radix_tree_node *node, unsigned int tag,
..
..
@@ -169,32 +115,32 @@
169
115
 
170
116
 static inline void root_tag_set(struct radix_tree_root *root, unsigned tag)
171
117
 {
172
-	root->gfp_mask |= (__force gfp_t)(1 << (tag + ROOT_TAG_SHIFT));
118
+	root->xa_flags |= (__force gfp_t)(1 << (tag + ROOT_TAG_SHIFT));
173
119
 }
174
120
 
175
121
 static inline void root_tag_clear(struct radix_tree_root *root, unsigned tag)
176
122
 {
177
-	root->gfp_mask &= (__force gfp_t)~(1 << (tag + ROOT_TAG_SHIFT));
123
+	root->xa_flags &= (__force gfp_t)~(1 << (tag + ROOT_TAG_SHIFT));
178
124
 }
179
125
 
180
126
 static inline void root_tag_clear_all(struct radix_tree_root *root)
181
127
 {
182
-	root->gfp_mask &= (1 << ROOT_TAG_SHIFT) - 1;
128
+	root->xa_flags &= (__force gfp_t)((1 << ROOT_TAG_SHIFT) - 1);
183
129
 }
184
130
 
185
131
 static inline int root_tag_get(const struct radix_tree_root *root, unsigned tag)
186
132
 {
187
-	return (__force int)root->gfp_mask & (1 << (tag + ROOT_TAG_SHIFT));
133
+	return (__force int)root->xa_flags & (1 << (tag + ROOT_TAG_SHIFT));
188
134
 }
189
135
 
190
136
 static inline unsigned root_tags_get(const struct radix_tree_root *root)
191
137
 {
192
-	return (__force unsigned)root->gfp_mask >> ROOT_TAG_SHIFT;
138
+	return (__force unsigned)root->xa_flags >> ROOT_TAG_SHIFT;
193
139
 }
194
140
 
195
141
 static inline bool is_idr(const struct radix_tree_root *root)
196
142
 {
197
-	return !!(root->gfp_mask & ROOT_IS_IDR);
143
+	return !!(root->xa_flags & ROOT_IS_IDR);
198
144
 }
199
145
 
200
146
 /*
..
..
@@ -254,7 +200,7 @@
254
200
 
255
201
 static unsigned int iter_offset(const struct radix_tree_iter *iter)
256
202
 {
257
-	return (iter->index >> iter_shift(iter)) & RADIX_TREE_MAP_MASK;
203
+	return iter->index & RADIX_TREE_MAP_MASK;
258
204
 }
259
205
 
260
206
 /*
..
..
@@ -277,99 +223,6 @@
277
223
 	return (index & ~node_maxindex(node)) + (offset << node->shift);
278
224
 }
279
225
 
280
-#ifndef __KERNEL__
281
-static void dump_node(struct radix_tree_node *node, unsigned long index)
282
-{
283
-	unsigned long i;
284
-
285
-	pr_debug("radix node: %p offset %d indices %lu-%lu parent %p tags %lx %lx %lx shift %d count %d exceptional %d\n",
286
-		node, node->offset, index, index | node_maxindex(node),
287
-		node->parent,
288
-		node->tags[0][0], node->tags[1][0], node->tags[2][0],
289
-		node->shift, node->count, node->exceptional);
290
-
291
-	for (i = 0; i < RADIX_TREE_MAP_SIZE; i++) {
292
-		unsigned long first = index | (i << node->shift);
293
-		unsigned long last = first | ((1UL << node->shift) - 1);
294
-		void *entry = node->slots[i];
295
-		if (!entry)
296
-			continue;
297
-		if (entry == RADIX_TREE_RETRY) {
298
-			pr_debug("radix retry offset %ld indices %lu-%lu parent %p\n",
299
-					i, first, last, node);
300
-		} else if (!radix_tree_is_internal_node(entry)) {
301
-			pr_debug("radix entry %p offset %ld indices %lu-%lu parent %p\n",
302
-					entry, i, first, last, node);
303
-		} else if (is_sibling_entry(node, entry)) {
304
-			pr_debug("radix sblng %p offset %ld indices %lu-%lu parent %p val %p\n",
305
-					entry, i, first, last, node,
306
-					*(void **)entry_to_node(entry));
307
-		} else {
308
-			dump_node(entry_to_node(entry), first);
309
-		}
310
-	}
311
-}
312
-
313
-/* For debug */
314
-static void radix_tree_dump(struct radix_tree_root *root)
315
-{
316
-	pr_debug("radix root: %p rnode %p tags %x\n",
317
-			root, root->rnode,
318
-			root->gfp_mask >> ROOT_TAG_SHIFT);
319
-	if (!radix_tree_is_internal_node(root->rnode))
320
-		return;
321
-	dump_node(entry_to_node(root->rnode), 0);
322
-}
323
-
324
-static void dump_ida_node(void *entry, unsigned long index)
325
-{
326
-	unsigned long i;
327
-
328
-	if (!entry)
329
-		return;
330
-
331
-	if (radix_tree_is_internal_node(entry)) {
332
-		struct radix_tree_node *node = entry_to_node(entry);
333
-
334
-		pr_debug("ida node: %p offset %d indices %lu-%lu parent %p free %lx shift %d count %d\n",
335
-			node, node->offset, index * IDA_BITMAP_BITS,
336
-			((index | node_maxindex(node)) + 1) *
337
-				IDA_BITMAP_BITS - 1,
338
-			node->parent, node->tags[0][0], node->shift,
339
-			node->count);
340
-		for (i = 0; i < RADIX_TREE_MAP_SIZE; i++)
341
-			dump_ida_node(node->slots[i],
342
-					index | (i << node->shift));
343
-	} else if (radix_tree_exceptional_entry(entry)) {
344
-		pr_debug("ida excp: %p offset %d indices %lu-%lu data %lx\n",
345
-				entry, (int)(index & RADIX_TREE_MAP_MASK),
346
-				index * IDA_BITMAP_BITS,
347
-				index * IDA_BITMAP_BITS + BITS_PER_LONG -
348
-					RADIX_TREE_EXCEPTIONAL_SHIFT,
349
-				(unsigned long)entry >>
350
-					RADIX_TREE_EXCEPTIONAL_SHIFT);
351
-	} else {
352
-		struct ida_bitmap *bitmap = entry;
353
-
354
-		pr_debug("ida btmp: %p offset %d indices %lu-%lu data", bitmap,
355
-				(int)(index & RADIX_TREE_MAP_MASK),
356
-				index * IDA_BITMAP_BITS,
357
-				(index + 1) * IDA_BITMAP_BITS - 1);
358
-		for (i = 0; i < IDA_BITMAP_LONGS; i++)
359
-			pr_cont(" %lx", bitmap->bitmap[i]);
360
-		pr_cont("\n");
361
-	}
362
-}
363
-
364
-static void ida_dump(struct ida *ida)
365
-{
366
-	struct radix_tree_root *root = &ida->ida_rt;
367
-	pr_debug("ida: %p node %p free %d\n", ida, root->rnode,
368
-				root->gfp_mask >> ROOT_TAG_SHIFT);
369
-	dump_ida_node(root->rnode, 0);
370
-}
371
-#endif
372
-
373
226
 /*
374
227
  * This assumes that the caller has performed appropriate preallocation, and
375
228
  * that the caller has pinned this thread of control to the current CPU.
..
..
@@ -378,7 +231,7 @@
378
231
 radix_tree_node_alloc(gfp_t gfp_mask, struct radix_tree_node *parent,
379
232
 			struct radix_tree_root *root,
380
233
 			unsigned int shift, unsigned int offset,
381
-			unsigned int count, unsigned int exceptional)
234
+			unsigned int count, unsigned int nr_values)
382
235
 {
383
236
 	struct radix_tree_node *ret = NULL;
384
237
 
..
..
@@ -425,14 +278,14 @@
425
278
 		ret->shift = shift;
426
279
 		ret->offset = offset;
427
280
 		ret->count = count;
428
-		ret->exceptional = exceptional;
281
+		ret->nr_values = nr_values;
429
282
 		ret->parent = parent;
430
-		ret->root = root;
283
+		ret->array = root;
431
284
 	}
432
285
 	return ret;
433
286
 }
434
287
 
435
-static void radix_tree_node_rcu_free(struct rcu_head *head)
288
+void radix_tree_node_rcu_free(struct rcu_head *head)
436
289
 {
437
290
 	struct radix_tree_node *node =
438
291
 			container_of(head, struct radix_tree_node, rcu_head);
..
..
@@ -471,19 +324,19 @@
471
324
 	int ret = -ENOMEM;
472
325
 
473
326
 	/*
474
-	 * Nodes preloaded by one cgroup can be be used by another cgroup, so
327
+	 * Nodes preloaded by one cgroup can be used by another cgroup, so
475
328
 	 * they should never be accounted to any particular memory cgroup.
476
329
 	 */
477
330
 	gfp_mask &= ~__GFP_ACCOUNT;
478
331
 
479
-	preempt_disable();
332
+	local_lock(&radix_tree_preloads.lock);
480
333
 	rtp = this_cpu_ptr(&radix_tree_preloads);
481
334
 	while (rtp->nr < nr) {
482
-		preempt_enable();
335
+		local_unlock(&radix_tree_preloads.lock);
483
336
 		node = kmem_cache_alloc(radix_tree_node_cachep, gfp_mask);
484
337
 		if (node == NULL)
485
338
 			goto out;
486
-		preempt_disable();
339
+		local_lock(&radix_tree_preloads.lock);
487
340
 		rtp = this_cpu_ptr(&radix_tree_preloads);
488
341
 		if (rtp->nr < nr) {
489
342
 			node->parent = rtp->nodes;
..
..
@@ -525,82 +378,15 @@
525
378
 	if (gfpflags_allow_blocking(gfp_mask))
526
379
 		return __radix_tree_preload(gfp_mask, RADIX_TREE_PRELOAD_SIZE);
527
380
 	/* Preloading doesn't help anything with this gfp mask, skip it */
528
-	preempt_disable();
381
+	local_lock(&radix_tree_preloads.lock);
529
382
 	return 0;
530
383
 }
531
384
 EXPORT_SYMBOL(radix_tree_maybe_preload);
532
385
 
533
-#ifdef CONFIG_RADIX_TREE_MULTIORDER
534
-/*
535
- * Preload with enough objects to ensure that we can split a single entry
536
- * of order @old_order into many entries of size @new_order
537
- */
538
-int radix_tree_split_preload(unsigned int old_order, unsigned int new_order,
539
-							gfp_t gfp_mask)
540
-{
541
-	unsigned top = 1 << (old_order % RADIX_TREE_MAP_SHIFT);
542
-	unsigned layers = (old_order / RADIX_TREE_MAP_SHIFT) -
543
-				(new_order / RADIX_TREE_MAP_SHIFT);
544
-	unsigned nr = 0;
545
-
546
-	WARN_ON_ONCE(!gfpflags_allow_blocking(gfp_mask));
547
-	BUG_ON(new_order >= old_order);
548
-
549
-	while (layers--)
550
-		nr = nr * RADIX_TREE_MAP_SIZE + 1;
551
-	return __radix_tree_preload(gfp_mask, top * nr);
552
-}
553
-#endif
554
-
555
-/*
556
- * The same as function above, but preload number of nodes required to insert
557
- * (1 << order) continuous naturally-aligned elements.
558
- */
559
-int radix_tree_maybe_preload_order(gfp_t gfp_mask, int order)
560
-{
561
-	unsigned long nr_subtrees;
562
-	int nr_nodes, subtree_height;
563
-
564
-	/* Preloading doesn't help anything with this gfp mask, skip it */
565
-	if (!gfpflags_allow_blocking(gfp_mask)) {
566
-		preempt_disable();
567
-		return 0;
568
-	}
569
-
570
-	/*
571
-	 * Calculate number and height of fully populated subtrees it takes to
572
-	 * store (1 << order) elements.
573
-	 */
574
-	nr_subtrees = 1 << order;
575
-	for (subtree_height = 0; nr_subtrees > RADIX_TREE_MAP_SIZE;
576
-			subtree_height++)
577
-		nr_subtrees >>= RADIX_TREE_MAP_SHIFT;
578
-
579
-	/*
580
-	 * The worst case is zero height tree with a single item at index 0 and
581
-	 * then inserting items starting at ULONG_MAX - (1 << order).
582
-	 *
583
-	 * This requires RADIX_TREE_MAX_PATH nodes to build branch from root to
584
-	 * 0-index item.
585
-	 */
586
-	nr_nodes = RADIX_TREE_MAX_PATH;
587
-
588
-	/* Plus branch to fully populated subtrees. */
589
-	nr_nodes += RADIX_TREE_MAX_PATH - subtree_height;
590
-
591
-	/* Root node is shared. */
592
-	nr_nodes--;
593
-
594
-	/* Plus nodes required to build subtrees. */
595
-	nr_nodes += nr_subtrees * height_to_maxnodes[subtree_height];
596
-
597
-	return __radix_tree_preload(gfp_mask, nr_nodes);
598
-}
599
-
600
386
 static unsigned radix_tree_load_root(const struct radix_tree_root *root,
601
387
 		struct radix_tree_node **nodep, unsigned long *maxindex)
602
388
 {
603
-	struct radix_tree_node *node = rcu_dereference_raw(root->rnode);
389
+	struct radix_tree_node *node = rcu_dereference_raw(root->xa_head);
604
390
 
605
391
 	*nodep = node;
606
392
 
..
..
@@ -629,7 +415,7 @@
629
415
 	while (index > shift_maxindex(maxshift))
630
416
 		maxshift += RADIX_TREE_MAP_SHIFT;
631
417
 
632
-	entry = rcu_dereference_raw(root->rnode);
418
+	entry = rcu_dereference_raw(root->xa_head);
633
419
 	if (!entry && (!is_idr(root) || root_tag_get(root, IDR_FREE)))
634
420
 		goto out;
635
421
 
..
..
@@ -656,9 +442,9 @@
656
442
 		BUG_ON(shift > BITS_PER_LONG);
657
443
 		if (radix_tree_is_internal_node(entry)) {
658
444
 			entry_to_node(entry)->parent = node;
659
-		} else if (radix_tree_exceptional_entry(entry)) {
660
-			/* Moving an exceptional root->rnode to a node */
661
-			node->exceptional = 1;
445
+		} else if (xa_is_value(entry)) {
446
+			/* Moving a value entry root->xa_head to a node */
447
+			node->nr_values = 1;
662
448
 		}
663
449
 		/*
664
450
 		 * entry was already in the radix tree, so we do not need
..
..
@@ -666,7 +452,7 @@
666
452
 		 */
667
453
 		node->slots[0] = (void __rcu *)entry;
668
454
 		entry = node_to_entry(node);
669
-		rcu_assign_pointer(root->rnode, entry);
455
+		rcu_assign_pointer(root->xa_head, entry);
670
456
 		shift += RADIX_TREE_MAP_SHIFT;
671
457
 	} while (shift <= maxshift);
672
458
 out:
..
..
@@ -677,13 +463,12 @@
677
463
  *	radix_tree_shrink    -    shrink radix tree to minimum height
678
464
  *	@root		radix tree root
679
465
  */
680
-static inline bool radix_tree_shrink(struct radix_tree_root *root,
681
-				     radix_tree_update_node_t update_node)
466
+static inline bool radix_tree_shrink(struct radix_tree_root *root)
682
467
 {
683
468
 	bool shrunk = false;
684
469
 
685
470
 	for (;;) {
686
-		struct radix_tree_node *node = rcu_dereference_raw(root->rnode);
471
+		struct radix_tree_node *node = rcu_dereference_raw(root->xa_head);
687
472
 		struct radix_tree_node *child;
688
473
 
689
474
 		if (!radix_tree_is_internal_node(node))
..
..
@@ -692,15 +477,20 @@
692
477
 
693
478
 		/*
694
479
 		 * The candidate node has more than one child, or its child
695
-		 * is not at the leftmost slot, or the child is a multiorder
696
-		 * entry, we cannot shrink.
480
+		 * is not at the leftmost slot, we cannot shrink.
697
481
 		 */
698
482
 		if (node->count != 1)
699
483
 			break;
700
484
 		child = rcu_dereference_raw(node->slots[0]);
701
485
 		if (!child)
702
486
 			break;
703
-		if (!radix_tree_is_internal_node(child) && node->shift)
487
+
488
+		/*
489
+		 * For an IDR, we must not shrink entry 0 into the root in
490
+		 * case somebody calls idr_replace() with a pointer that
491
+		 * appears to be an internal entry
492
+		 */
493
+		if (!node->shift && is_idr(root))
704
494
 			break;
705
495
 
706
496
 		if (radix_tree_is_internal_node(child))
..
..
@@ -711,9 +501,9 @@
711
501
 		 * moving the node from one part of the tree to another: if it
712
502
 		 * was safe to dereference the old pointer to it
713
503
 		 * (node->slots[0]), it will be safe to dereference the new
714
-		 * one (root->rnode) as far as dependent read barriers go.
504
+		 * one (root->xa_head) as far as dependent read barriers go.
715
505
 		 */
716
-		root->rnode = (void __rcu *)child;
506
+		root->xa_head = (void __rcu *)child;
717
507
 		if (is_idr(root) && !tag_get(node, IDR_FREE, 0))
718
508
 			root_tag_clear(root, IDR_FREE);
719
509
 
..
..
@@ -738,8 +528,6 @@
738
528
 		node->count = 0;
739
529
 		if (!radix_tree_is_internal_node(child)) {
740
530
 			node->slots[0] = (void __rcu *)RADIX_TREE_RETRY;
741
-			if (update_node)
742
-				update_node(node);
743
531
 		}
744
532
 
745
533
 		WARN_ON_ONCE(!list_empty(&node->private_list));
..
..
@@ -751,8 +539,7 @@
751
539
 }
752
540
 
753
541
 static bool delete_node(struct radix_tree_root *root,
754
-			struct radix_tree_node *node,
755
-			radix_tree_update_node_t update_node)
542
+			struct radix_tree_node *node)
756
543
 {
757
544
 	bool deleted = false;
758
545
 
..
..
@@ -761,9 +548,8 @@
761
548
 
762
549
 		if (node->count) {
763
550
 			if (node_to_entry(node) ==
764
-					rcu_dereference_raw(root->rnode))
765
-				deleted |= radix_tree_shrink(root,
766
-								update_node);
551
+					rcu_dereference_raw(root->xa_head))
552
+				deleted |= radix_tree_shrink(root);
767
553
 			return deleted;
768
554
 		}
769
555
 
..
..
@@ -778,7 +564,7 @@
778
564
 			 */
779
565
 			if (!is_idr(root))
780
566
 				root_tag_clear_all(root);
781
-			root->rnode = NULL;
567
+			root->xa_head = NULL;
782
568
 		}
783
569
 
784
570
 		WARN_ON_ONCE(!list_empty(&node->private_list));
..
..
@@ -795,7 +581,6 @@
795
581
  *	__radix_tree_create	-	create a slot in a radix tree
796
582
  *	@root:		radix tree root
797
583
  *	@index:		index key
798
- *	@order:		index occupies 2^order aligned slots
799
584
  *	@nodep:		returns node
800
585
  *	@slotp:		returns slot
801
586
  *
..
..
@@ -803,36 +588,34 @@
803
588
  *	at position @index in the radix tree @root.
804
589
  *
805
590
  *	Until there is more than one item in the tree, no nodes are
806
- *	allocated and @root->rnode is used as a direct slot instead of
591
+ *	allocated and @root->xa_head is used as a direct slot instead of
807
592
  *	pointing to a node, in which case *@nodep will be NULL.
808
593
  *
809
594
  *	Returns -ENOMEM, or 0 for success.
810
595
  */
811
-int __radix_tree_create(struct radix_tree_root *root, unsigned long index,
812
-			unsigned order, struct radix_tree_node **nodep,
813
-			void __rcu ***slotp)
596
+static int __radix_tree_create(struct radix_tree_root *root,
597
+		unsigned long index, struct radix_tree_node **nodep,
598
+		void __rcu ***slotp)
814
599
 {
815
600
 	struct radix_tree_node *node = NULL, *child;
816
-	void __rcu **slot = (void __rcu **)&root->rnode;
601
+	void __rcu **slot = (void __rcu **)&root->xa_head;
817
602
 	unsigned long maxindex;
818
603
 	unsigned int shift, offset = 0;
819
-	unsigned long max = index | ((1UL << order) - 1);
604
+	unsigned long max = index;
820
605
 	gfp_t gfp = root_gfp_mask(root);
821
606
 
822
607
 	shift = radix_tree_load_root(root, &child, &maxindex);
823
608
 
824
609
 	/* Make sure the tree is high enough.  */
825
-	if (order > 0 && max == ((1UL << order) - 1))
826
-		max++;
827
610
 	if (max > maxindex) {
828
611
 		int error = radix_tree_extend(root, gfp, max, shift);
829
612
 		if (error < 0)
830
613
 			return error;
831
614
 		shift = error;
832
-		child = rcu_dereference_raw(root->rnode);
615
+		child = rcu_dereference_raw(root->xa_head);
833
616
 	}
834
617
 
835
-	while (shift > order) {
618
+	while (shift > 0) {
836
619
 		shift -= RADIX_TREE_MAP_SHIFT;
837
620
 		if (child == NULL) {
838
621
 			/* Have to add a child node.  */
..
..
@@ -875,8 +658,7 @@
875
658
 
876
659
 	for (;;) {
877
660
 		void *entry = rcu_dereference_raw(child->slots[offset]);
878
-		if (radix_tree_is_internal_node(entry) &&
879
-					!is_sibling_entry(child, entry)) {
661
+		if (xa_is_node(entry) && child->shift) {
880
662
 			child = entry_to_node(entry);
881
663
 			offset = 0;
882
664
 			continue;
..
..
@@ -894,96 +676,30 @@
894
676
 	}
895
677
 }
896
678
 
897
-#ifdef CONFIG_RADIX_TREE_MULTIORDER
898
679
 static inline int insert_entries(struct radix_tree_node *node,
899
-		void __rcu **slot, void *item, unsigned order, bool replace)
900
-{
901
-	struct radix_tree_node *child;
902
-	unsigned i, n, tag, offset, tags = 0;
903
-
904
-	if (node) {
905
-		if (order > node->shift)
906
-			n = 1 << (order - node->shift);
907
-		else
908
-			n = 1;
909
-		offset = get_slot_offset(node, slot);
910
-	} else {
911
-		n = 1;
912
-		offset = 0;
913
-	}
914
-
915
-	if (n > 1) {
916
-		offset = offset & ~(n - 1);
917
-		slot = &node->slots[offset];
918
-	}
919
-	child = node_to_entry(slot);
920
-
921
-	for (i = 0; i < n; i++) {
922
-		if (slot[i]) {
923
-			if (replace) {
924
-				node->count--;
925
-				for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++)
926
-					if (tag_get(node, tag, offset + i))
927
-						tags |= 1 << tag;
928
-			} else
929
-				return -EEXIST;
930
-		}
931
-	}
932
-
933
-	for (i = 0; i < n; i++) {
934
-		struct radix_tree_node *old = rcu_dereference_raw(slot[i]);
935
-		if (i) {
936
-			rcu_assign_pointer(slot[i], child);
937
-			for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++)
938
-				if (tags & (1 << tag))
939
-					tag_clear(node, tag, offset + i);
940
-		} else {
941
-			rcu_assign_pointer(slot[i], item);
942
-			for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++)
943
-				if (tags & (1 << tag))
944
-					tag_set(node, tag, offset);
945
-		}
946
-		if (radix_tree_is_internal_node(old) &&
947
-					!is_sibling_entry(node, old) &&
948
-					(old != RADIX_TREE_RETRY))
949
-			radix_tree_free_nodes(old);
950
-		if (radix_tree_exceptional_entry(old))
951
-			node->exceptional--;
952
-	}
953
-	if (node) {
954
-		node->count += n;
955
-		if (radix_tree_exceptional_entry(item))
956
-			node->exceptional += n;
957
-	}
958
-	return n;
959
-}
960
-#else
961
-static inline int insert_entries(struct radix_tree_node *node,
962
-		void __rcu **slot, void *item, unsigned order, bool replace)
680
+		void __rcu **slot, void *item, bool replace)
963
681
 {
964
682
 	if (*slot)
965
683
 		return -EEXIST;
966
684
 	rcu_assign_pointer(*slot, item);
967
685
 	if (node) {
968
686
 		node->count++;
969
-		if (radix_tree_exceptional_entry(item))
970
-			node->exceptional++;
687
+		if (xa_is_value(item))
688
+			node->nr_values++;
971
689
 	}
972
690
 	return 1;
973
691
 }
974
-#endif
975
692
 
976
693
 /**
977
694
  *	__radix_tree_insert    -    insert into a radix tree
978
695
  *	@root:		radix tree root
979
696
  *	@index:		index key
980
- *	@order:		key covers the 2^order indices around index
981
697
  *	@item:		item to insert
982
698
  *
983
699
  *	Insert an item into the radix tree at position @index.
984
700
  */
985
-int __radix_tree_insert(struct radix_tree_root *root, unsigned long index,
986
-			unsigned order, void *item)
701
+int radix_tree_insert(struct radix_tree_root *root, unsigned long index,
702
+			void *item)
987
703
 {
988
704
 	struct radix_tree_node *node;
989
705
 	void __rcu **slot;
..
..
@@ -991,11 +707,11 @@
991
707
 
992
708
 	BUG_ON(radix_tree_is_internal_node(item));
993
709
 
994
-	error = __radix_tree_create(root, index, order, &node, &slot);
710
+	error = __radix_tree_create(root, index, &node, &slot);
995
711
 	if (error)
996
712
 		return error;
997
713
 
998
-	error = insert_entries(node, slot, item, order, false);
714
+	error = insert_entries(node, slot, item, false);
999
715
 	if (error < 0)
1000
716
 		return error;
1001
717
 
..
..
@@ -1010,7 +726,7 @@
1010
726
 
1011
727
 	return 0;
1012
728
 }
1013
-EXPORT_SYMBOL(__radix_tree_insert);
729
+EXPORT_SYMBOL(radix_tree_insert);
1014
730
 
1015
731
 /**
1016
732
  *	__radix_tree_lookup	-	lookup an item in a radix tree
..
..
@@ -1023,7 +739,7 @@
1023
739
  *	tree @root.
1024
740
  *
1025
741
  *	Until there is more than one item in the tree, no nodes are
1026
- *	allocated and @root->rnode is used as a direct slot instead of
742
+ *	allocated and @root->xa_head is used as a direct slot instead of
1027
743
  *	pointing to a node, in which case *@nodep will be NULL.
1028
744
  */
1029
745
 void *__radix_tree_lookup(const struct radix_tree_root *root,
..
..
@@ -1036,7 +752,7 @@
1036
752
 
1037
753
  restart:
1038
754
 	parent = NULL;
1039
-	slot = (void __rcu **)&root->rnode;
755
+	slot = (void __rcu **)&root->xa_head;
1040
756
 	radix_tree_load_root(root, &node, &maxindex);
1041
757
 	if (index > maxindex)
1042
758
 		return NULL;
..
..
@@ -1044,11 +760,13 @@
1044
760
 	while (radix_tree_is_internal_node(node)) {
1045
761
 		unsigned offset;
1046
762
 
1047
-		if (node == RADIX_TREE_RETRY)
1048
-			goto restart;
1049
763
 		parent = entry_to_node(node);
1050
764
 		offset = radix_tree_descend(parent, &node, index);
1051
765
 		slot = parent->slots + offset;
766
+		if (node == RADIX_TREE_RETRY)
767
+			goto restart;
768
+		if (parent->shift == 0)
769
+			break;
1052
770
 	}
1053
771
 
1054
772
 	if (nodep)
..
..
@@ -1100,36 +818,12 @@
1100
818
 }
1101
819
 EXPORT_SYMBOL(radix_tree_lookup);
1102
820
 
1103
-static inline void replace_sibling_entries(struct radix_tree_node *node,
1104
-				void __rcu **slot, int count, int exceptional)
1105
-{
1106
-#ifdef CONFIG_RADIX_TREE_MULTIORDER
1107
-	void *ptr = node_to_entry(slot);
1108
-	unsigned offset = get_slot_offset(node, slot) + 1;
1109
-
1110
-	while (offset < RADIX_TREE_MAP_SIZE) {
1111
-		if (rcu_dereference_raw(node->slots[offset]) != ptr)
1112
-			break;
1113
-		if (count < 0) {
1114
-			node->slots[offset] = NULL;
1115
-			node->count--;
1116
-		}
1117
-		node->exceptional += exceptional;
1118
-		offset++;
1119
-	}
1120
-#endif
1121
-}
1122
-
1123
821
 static void replace_slot(void __rcu **slot, void *item,
1124
-		struct radix_tree_node *node, int count, int exceptional)
822
+		struct radix_tree_node *node, int count, int values)
1125
823
 {
1126
-	if (WARN_ON_ONCE(radix_tree_is_internal_node(item)))
1127
-		return;
1128
-
1129
-	if (node && (count || exceptional)) {
824
+	if (node && (count || values)) {
1130
825
 		node->count += count;
1131
-		node->exceptional += exceptional;
1132
-		replace_sibling_entries(node, slot, count, exceptional);
826
+		node->nr_values += values;
1133
827
 	}
1134
828
 
1135
829
 	rcu_assign_pointer(*slot, item);
..
..
@@ -1172,37 +866,31 @@
1172
866
  * @node:		pointer to tree node
1173
867
  * @slot:		pointer to slot in @node
1174
868
  * @item:		new item to store in the slot.
1175
- * @update_node:	callback for changing leaf nodes
1176
869
  *
1177
870
  * For use with __radix_tree_lookup().  Caller must hold tree write locked
1178
871
  * across slot lookup and replacement.
1179
872
  */
1180
873
 void __radix_tree_replace(struct radix_tree_root *root,
1181
874
 			  struct radix_tree_node *node,
1182
-			  void __rcu **slot, void *item,
1183
-			  radix_tree_update_node_t update_node)
875
+			  void __rcu **slot, void *item)
1184
876
 {
1185
877
 	void *old = rcu_dereference_raw(*slot);
1186
-	int exceptional = !!radix_tree_exceptional_entry(item) -
1187
-				!!radix_tree_exceptional_entry(old);
878
+	int values = !!xa_is_value(item) - !!xa_is_value(old);
1188
879
 	int count = calculate_count(root, node, slot, item, old);
1189
880
 
1190
881
 	/*
1191
-	 * This function supports replacing exceptional entries and
882
+	 * This function supports replacing value entries and
1192
883
 	 * deleting entries, but that needs accounting against the
1193
-	 * node unless the slot is root->rnode.
884
+	 * node unless the slot is root->xa_head.
1194
885
 	 */
1195
-	WARN_ON_ONCE(!node && (slot != (void __rcu **)&root->rnode) &&
1196
-			(count || exceptional));
1197
-	replace_slot(slot, item, node, count, exceptional);
886
+	WARN_ON_ONCE(!node && (slot != (void __rcu **)&root->xa_head) &&
887
+			(count || values));
888
+	replace_slot(slot, item, node, count, values);
1198
889
 
1199
890
 	if (!node)
1200
891
 		return;
1201
892
 
1202
-	if (update_node)
1203
-		update_node(node);
1204
-
1205
-	delete_node(root, node, update_node);
893
+	delete_node(root, node);
1206
894
 }
1207
895
 
1208
896
 /**
..
..
@@ -1211,12 +899,12 @@
1211
899
  * @slot:	pointer to slot
1212
900
  * @item:	new item to store in the slot.
1213
901
  *
1214
- * For use with radix_tree_lookup_slot(), radix_tree_gang_lookup_slot(),
902
+ * For use with radix_tree_lookup_slot() and
1215
903
  * radix_tree_gang_lookup_tag_slot().  Caller must hold tree write locked
1216
904
  * across slot lookup and replacement.
1217
905
  *
1218
906
  * NOTE: This cannot be used to switch between non-entries (empty slots),
1219
- * regular entries, and exceptional entries, as that requires accounting
907
+ * regular entries, and value entries, as that requires accounting
1220
908
  * inside the radix tree node. When switching from one type of entry or
1221
909
  * deleting, use __radix_tree_lookup() and __radix_tree_replace() or
1222
910
  * radix_tree_iter_replace().
..
..
@@ -1224,7 +912,7 @@
1224
912
 void radix_tree_replace_slot(struct radix_tree_root *root,
1225
913
 			     void __rcu **slot, void *item)
1226
914
 {
1227
-	__radix_tree_replace(root, NULL, slot, item, NULL);
915
+	__radix_tree_replace(root, NULL, slot, item);
1228
916
 }
1229
917
 EXPORT_SYMBOL(radix_tree_replace_slot);
1230
918
 
..
..
@@ -1234,161 +922,15 @@
1234
922
  * @slot:	pointer to slot
1235
923
  * @item:	new item to store in the slot.
1236
924
  *
1237
- * For use with radix_tree_split() and radix_tree_for_each_slot().
1238
- * Caller must hold tree write locked across split and replacement.
925
+ * For use with radix_tree_for_each_slot().
926
+ * Caller must hold tree write locked.
1239
927
  */
1240
928
 void radix_tree_iter_replace(struct radix_tree_root *root,
1241
929
 				const struct radix_tree_iter *iter,
1242
930
 				void __rcu **slot, void *item)
1243
931
 {
1244
-	__radix_tree_replace(root, iter->node, slot, item, NULL);
932
+	__radix_tree_replace(root, iter->node, slot, item);
1245
933
 }
1246
-
1247
-#ifdef CONFIG_RADIX_TREE_MULTIORDER
1248
-/**
1249
- * radix_tree_join - replace multiple entries with one multiorder entry
1250
- * @root: radix tree root
1251
- * @index: an index inside the new entry
1252
- * @order: order of the new entry
1253
- * @item: new entry
1254
- *
1255
- * Call this function to replace several entries with one larger entry.
1256
- * The existing entries are presumed to not need freeing as a result of
1257
- * this call.
1258
- *
1259
- * The replacement entry will have all the tags set on it that were set
1260
- * on any of the entries it is replacing.
1261
- */
1262
-int radix_tree_join(struct radix_tree_root *root, unsigned long index,
1263
-			unsigned order, void *item)
1264
-{
1265
-	struct radix_tree_node *node;
1266
-	void __rcu **slot;
1267
-	int error;
1268
-
1269
-	BUG_ON(radix_tree_is_internal_node(item));
1270
-
1271
-	error = __radix_tree_create(root, index, order, &node, &slot);
1272
-	if (!error)
1273
-		error = insert_entries(node, slot, item, order, true);
1274
-	if (error > 0)
1275
-		error = 0;
1276
-
1277
-	return error;
1278
-}
1279
-
1280
-/**
1281
- * radix_tree_split - Split an entry into smaller entries
1282
- * @root: radix tree root
1283
- * @index: An index within the large entry
1284
- * @order: Order of new entries
1285
- *
1286
- * Call this function as the first step in replacing a multiorder entry
1287
- * with several entries of lower order.  After this function returns,
1288
- * loop over the relevant portion of the tree using radix_tree_for_each_slot()
1289
- * and call radix_tree_iter_replace() to set up each new entry.
1290
- *
1291
- * The tags from this entry are replicated to all the new entries.
1292
- *
1293
- * The radix tree should be locked against modification during the entire
1294
- * replacement operation.  Lock-free lookups will see RADIX_TREE_RETRY which
1295
- * should prompt RCU walkers to restart the lookup from the root.
1296
- */
1297
-int radix_tree_split(struct radix_tree_root *root, unsigned long index,
1298
-				unsigned order)
1299
-{
1300
-	struct radix_tree_node *parent, *node, *child;
1301
-	void __rcu **slot;
1302
-	unsigned int offset, end;
1303
-	unsigned n, tag, tags = 0;
1304
-	gfp_t gfp = root_gfp_mask(root);
1305
-
1306
-	if (!__radix_tree_lookup(root, index, &parent, &slot))
1307
-		return -ENOENT;
1308
-	if (!parent)
1309
-		return -ENOENT;
1310
-
1311
-	offset = get_slot_offset(parent, slot);
1312
-
1313
-	for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++)
1314
-		if (tag_get(parent, tag, offset))
1315
-			tags |= 1 << tag;
1316
-
1317
-	for (end = offset + 1; end < RADIX_TREE_MAP_SIZE; end++) {
1318
-		if (!is_sibling_entry(parent,
1319
-				rcu_dereference_raw(parent->slots[end])))
1320
-			break;
1321
-		for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++)
1322
-			if (tags & (1 << tag))
1323
-				tag_set(parent, tag, end);
1324
-		/* rcu_assign_pointer ensures tags are set before RETRY */
1325
-		rcu_assign_pointer(parent->slots[end], RADIX_TREE_RETRY);
1326
-	}
1327
-	rcu_assign_pointer(parent->slots[offset], RADIX_TREE_RETRY);
1328
-	parent->exceptional -= (end - offset);
1329
-
1330
-	if (order == parent->shift)
1331
-		return 0;
1332
-	if (order > parent->shift) {
1333
-		while (offset < end)
1334
-			offset += insert_entries(parent, &parent->slots[offset],
1335
-					RADIX_TREE_RETRY, order, true);
1336
-		return 0;
1337
-	}
1338
-
1339
-	node = parent;
1340
-
1341
-	for (;;) {
1342
-		if (node->shift > order) {
1343
-			child = radix_tree_node_alloc(gfp, node, root,
1344
-					node->shift - RADIX_TREE_MAP_SHIFT,
1345
-					offset, 0, 0);
1346
-			if (!child)
1347
-				goto nomem;
1348
-			if (node != parent) {
1349
-				node->count++;
1350
-				rcu_assign_pointer(node->slots[offset],
1351
-							node_to_entry(child));
1352
-				for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++)
1353
-					if (tags & (1 << tag))
1354
-						tag_set(node, tag, offset);
1355
-			}
1356
-
1357
-			node = child;
1358
-			offset = 0;
1359
-			continue;
1360
-		}
1361
-
1362
-		n = insert_entries(node, &node->slots[offset],
1363
-					RADIX_TREE_RETRY, order, false);
1364
-		BUG_ON(n > RADIX_TREE_MAP_SIZE);
1365
-
1366
-		for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++)
1367
-			if (tags & (1 << tag))
1368
-				tag_set(node, tag, offset);
1369
-		offset += n;
1370
-
1371
-		while (offset == RADIX_TREE_MAP_SIZE) {
1372
-			if (node == parent)
1373
-				break;
1374
-			offset = node->offset;
1375
-			child = node;
1376
-			node = node->parent;
1377
-			rcu_assign_pointer(node->slots[offset],
1378
-						node_to_entry(child));
1379
-			offset++;
1380
-		}
1381
-		if ((node == parent) && (offset == end))
1382
-			return 0;
1383
-	}
1384
-
1385
- nomem:
1386
-	/* Shouldn't happen; did user forget to preload? */
1387
-	/* TODO: free all the allocated nodes */
1388
-	WARN_ON(1);
1389
-	return -ENOMEM;
1390
-}
1391
-#endif
1392
934
 
1393
935
 static void node_tag_set(struct radix_tree_root *root,
1394
936
 				struct radix_tree_node *node,
..
..
@@ -1447,18 +989,6 @@
1447
989
 }
1448
990
 EXPORT_SYMBOL(radix_tree_tag_set);
1449
991
 
1450
-/**
1451
- * radix_tree_iter_tag_set - set a tag on the current iterator entry
1452
- * @root:	radix tree root
1453
- * @iter:	iterator state
1454
- * @tag:	tag to set
1455
- */
1456
-void radix_tree_iter_tag_set(struct radix_tree_root *root,
1457
-			const struct radix_tree_iter *iter, unsigned int tag)
1458
-{
1459
-	node_tag_set(root, iter->node, tag, iter_offset(iter));
1460
-}
1461
-
1462
992
 static void node_tag_clear(struct radix_tree_root *root,
1463
993
 				struct radix_tree_node *node,
1464
994
 				unsigned int tag, unsigned int offset)
..
..
@@ -1498,7 +1028,7 @@
1498
1028
 {
1499
1029
 	struct radix_tree_node *node, *parent;
1500
1030
 	unsigned long maxindex;
1501
-	int uninitialized_var(offset);
1031
+	int offset;
1502
1032
 
1503
1033
 	radix_tree_load_root(root, &node, &maxindex);
1504
1034
 	if (index > maxindex)
..
..
@@ -1574,14 +1104,6 @@
1574
1104
 }
1575
1105
 EXPORT_SYMBOL(radix_tree_tag_get);
1576
1106
 
1577
-static inline void __set_iter_shift(struct radix_tree_iter *iter,
1578
-					unsigned int shift)
1579
-{
1580
-#ifdef CONFIG_RADIX_TREE_MULTIORDER
1581
-	iter->shift = shift;
1582
-#endif
1583
-}
1584
-
1585
1107
 /* Construct iter->tags bit-mask from node->tags[tag] array */
1586
1108
 static void set_iter_tags(struct radix_tree_iter *iter,
1587
1109
 				struct radix_tree_node *node, unsigned offset,
..
..
@@ -1608,92 +1130,10 @@
1608
1130
 	}
1609
1131
 }
1610
1132
 
1611
-#ifdef CONFIG_RADIX_TREE_MULTIORDER
1612
-static void __rcu **skip_siblings(struct radix_tree_node **nodep,
1613
-			void __rcu **slot, struct radix_tree_iter *iter)
1614
-{
1615
-	while (iter->index < iter->next_index) {
1616
-		*nodep = rcu_dereference_raw(*slot);
1617
-		if (*nodep && !is_sibling_entry(iter->node, *nodep))
1618
-			return slot;
1619
-		slot++;
1620
-		iter->index = __radix_tree_iter_add(iter, 1);
1621
-		iter->tags >>= 1;
1622
-	}
1623
-
1624
-	*nodep = NULL;
1625
-	return NULL;
1626
-}
1627
-
1628
-void __rcu **__radix_tree_next_slot(void __rcu **slot,
1629
-				struct radix_tree_iter *iter, unsigned flags)
1630
-{
1631
-	unsigned tag = flags & RADIX_TREE_ITER_TAG_MASK;
1632
-	struct radix_tree_node *node;
1633
-
1634
-	slot = skip_siblings(&node, slot, iter);
1635
-
1636
-	while (radix_tree_is_internal_node(node)) {
1637
-		unsigned offset;
1638
-		unsigned long next_index;
1639
-
1640
-		if (node == RADIX_TREE_RETRY)
1641
-			return slot;
1642
-		node = entry_to_node(node);
1643
-		iter->node = node;
1644
-		iter->shift = node->shift;
1645
-
1646
-		if (flags & RADIX_TREE_ITER_TAGGED) {
1647
-			offset = radix_tree_find_next_bit(node, tag, 0);
1648
-			if (offset == RADIX_TREE_MAP_SIZE)
1649
-				return NULL;
1650
-			slot = &node->slots[offset];
1651
-			iter->index = __radix_tree_iter_add(iter, offset);
1652
-			set_iter_tags(iter, node, offset, tag);
1653
-			node = rcu_dereference_raw(*slot);
1654
-		} else {
1655
-			offset = 0;
1656
-			slot = &node->slots[0];
1657
-			for (;;) {
1658
-				node = rcu_dereference_raw(*slot);
1659
-				if (node)
1660
-					break;
1661
-				slot++;
1662
-				offset++;
1663
-				if (offset == RADIX_TREE_MAP_SIZE)
1664
-					return NULL;
1665
-			}
1666
-			iter->index = __radix_tree_iter_add(iter, offset);
1667
-		}
1668
-		if ((flags & RADIX_TREE_ITER_CONTIG) && (offset > 0))
1669
-			goto none;
1670
-		next_index = (iter->index | shift_maxindex(iter->shift)) + 1;
1671
-		if (next_index < iter->next_index)
1672
-			iter->next_index = next_index;
1673
-	}
1674
-
1675
-	return slot;
1676
- none:
1677
-	iter->next_index = 0;
1678
-	return NULL;
1679
-}
1680
-EXPORT_SYMBOL(__radix_tree_next_slot);
1681
-#else
1682
-static void __rcu **skip_siblings(struct radix_tree_node **nodep,
1683
-			void __rcu **slot, struct radix_tree_iter *iter)
1684
-{
1685
-	return slot;
1686
-}
1687
-#endif
1688
-
1689
1133
 void __rcu **radix_tree_iter_resume(void __rcu **slot,
1690
1134
 					struct radix_tree_iter *iter)
1691
1135
 {
1692
-	struct radix_tree_node *node;
1693
-
1694
-	slot++;
1695
1136
 	iter->index = __radix_tree_iter_add(iter, 1);
1696
-	skip_siblings(&node, slot, iter);
1697
1137
 	iter->next_index = iter->index;
1698
1138
 	iter->tags = 0;
1699
1139
 	return NULL;
..
..
@@ -1744,8 +1184,7 @@
1744
1184
 		iter->next_index = maxindex + 1;
1745
1185
 		iter->tags = 1;
1746
1186
 		iter->node = NULL;
1747
-		__set_iter_shift(iter, 0);
1748
-		return (void __rcu **)&root->rnode;
1187
+		return (void __rcu **)&root->xa_head;
1749
1188
 	}
1750
1189
 
1751
1190
 	do {
..
..
@@ -1765,8 +1204,6 @@
1765
1204
 				while (++offset	< RADIX_TREE_MAP_SIZE) {
1766
1205
 					void *slot = rcu_dereference_raw(
1767
1206
 							node->slots[offset]);
1768
-					if (is_sibling_entry(node, slot))
1769
-						continue;
1770
1207
 					if (slot)
1771
1208
 						break;
1772
1209
 				}
..
..
@@ -1784,13 +1221,12 @@
1784
1221
 			goto restart;
1785
1222
 		if (child == RADIX_TREE_RETRY)
1786
1223
 			break;
1787
-	} while (radix_tree_is_internal_node(child));
1224
+	} while (node->shift && radix_tree_is_internal_node(child));
1788
1225
 
1789
1226
 	/* Update the iterator state */
1790
-	iter->index = (index &~ node_maxindex(node)) | (offset << node->shift);
1227
+	iter->index = (index &~ node_maxindex(node)) | offset;
1791
1228
 	iter->next_index = (index | node_maxindex(node)) + 1;
1792
1229
 	iter->node = node;
1793
-	__set_iter_shift(iter, node->shift);
1794
1230
 
1795
1231
 	if (flags & RADIX_TREE_ITER_TAGGED)
1796
1232
 		set_iter_tags(iter, node, offset, tag);
..
..
@@ -1845,48 +1281,6 @@
1845
1281
 	return ret;
1846
1282
 }
1847
1283
 EXPORT_SYMBOL(radix_tree_gang_lookup);
1848
-
1849
-/**
1850
- *	radix_tree_gang_lookup_slot - perform multiple slot lookup on radix tree
1851
- *	@root:		radix tree root
1852
- *	@results:	where the results of the lookup are placed
1853
- *	@indices:	where their indices should be placed (but usually NULL)
1854
- *	@first_index:	start the lookup from this key
1855
- *	@max_items:	place up to this many items at *results
1856
- *
1857
- *	Performs an index-ascending scan of the tree for present items.  Places
1858
- *	their slots at *@results and returns the number of items which were
1859
- *	placed at *@results.
1860
- *
1861
- *	The implementation is naive.
1862
- *
1863
- *	Like radix_tree_gang_lookup as far as RCU and locking goes. Slots must
1864
- *	be dereferenced with radix_tree_deref_slot, and if using only RCU
1865
- *	protection, radix_tree_deref_slot may fail requiring a retry.
1866
- */
1867
-unsigned int
1868
-radix_tree_gang_lookup_slot(const struct radix_tree_root *root,
1869
-			void __rcu ***results, unsigned long *indices,
1870
-			unsigned long first_index, unsigned int max_items)
1871
-{
1872
-	struct radix_tree_iter iter;
1873
-	void __rcu **slot;
1874
-	unsigned int ret = 0;
1875
-
1876
-	if (unlikely(!max_items))
1877
-		return 0;
1878
-
1879
-	radix_tree_for_each_slot(slot, root, &iter, first_index) {
1880
-		results[ret] = slot;
1881
-		if (indices)
1882
-			indices[ret] = iter.index;
1883
-		if (++ret == max_items)
1884
-			break;
1885
-	}
1886
-
1887
-	return ret;
1888
-}
1889
-EXPORT_SYMBOL(radix_tree_gang_lookup_slot);
1890
1284
 
1891
1285
 /**
1892
1286
  *	radix_tree_gang_lookup_tag - perform multiple lookup on a radix tree
..
..
@@ -1964,28 +1358,11 @@
1964
1358
 }
1965
1359
 EXPORT_SYMBOL(radix_tree_gang_lookup_tag_slot);
1966
1360
 
1967
-/**
1968
- *	__radix_tree_delete_node    -    try to free node after clearing a slot
1969
- *	@root:		radix tree root
1970
- *	@node:		node containing @index
1971
- *	@update_node:	callback for changing leaf nodes
1972
- *
1973
- *	After clearing the slot at @index in @node from radix tree
1974
- *	rooted at @root, call this function to attempt freeing the
1975
- *	node and shrinking the tree.
1976
- */
1977
-void __radix_tree_delete_node(struct radix_tree_root *root,
1978
-			      struct radix_tree_node *node,
1979
-			      radix_tree_update_node_t update_node)
1980
-{
1981
-	delete_node(root, node, update_node);
1982
-}
1983
-
1984
1361
 static bool __radix_tree_delete(struct radix_tree_root *root,
1985
1362
 				struct radix_tree_node *node, void __rcu **slot)
1986
1363
 {
1987
1364
 	void *old = rcu_dereference_raw(*slot);
1988
-	int exceptional = radix_tree_exceptional_entry(old) ? -1 : 0;
1365
+	int values = xa_is_value(old) ? -1 : 0;
1989
1366
 	unsigned offset = get_slot_offset(node, slot);
1990
1367
 	int tag;
1991
1368
 
..
..
@@ -1995,8 +1372,8 @@
1995
1372
 		for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++)
1996
1373
 			node_tag_clear(root, node, tag, offset);
1997
1374
 
1998
-	replace_slot(slot, NULL, node, -1, exceptional);
1999
-	return node && delete_node(root, node, NULL);
1375
+	replace_slot(slot, NULL, node, -1, values);
1376
+	return node && delete_node(root, node);
2000
1377
 }
2001
1378
 
2002
1379
 /**
..
..
@@ -2068,19 +1445,6 @@
2068
1445
 }
2069
1446
 EXPORT_SYMBOL(radix_tree_delete);
2070
1447
 
2071
-void radix_tree_clear_tags(struct radix_tree_root *root,
2072
-			   struct radix_tree_node *node,
2073
-			   void __rcu **slot)
2074
-{
2075
-	if (node) {
2076
-		unsigned int tag, offset = get_slot_offset(node, slot);
2077
-		for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++)
2078
-			node_tag_clear(root, node, tag, offset);
2079
-	} else {
2080
-		root_tag_clear_all(root);
2081
-	}
2082
-}
2083
-
2084
1448
 /**
2085
1449
  *	radix_tree_tagged - test whether any items in the tree are tagged
2086
1450
  *	@root:		radix tree root
..
..
@@ -2102,37 +1466,16 @@
2102
1466
 void idr_preload(gfp_t gfp_mask)
2103
1467
 {
2104
1468
 	if (__radix_tree_preload(gfp_mask, IDR_PRELOAD_SIZE))
2105
-		preempt_disable();
1469
+		local_lock(&radix_tree_preloads.lock);
2106
1470
 }
2107
1471
 EXPORT_SYMBOL(idr_preload);
2108
-
2109
-int ida_pre_get(struct ida *ida, gfp_t gfp)
2110
-{
2111
-	/*
2112
-	 * The IDA API has no preload_end() equivalent.  Instead,
2113
-	 * ida_get_new() can return -EAGAIN, prompting the caller
2114
-	 * to return to the ida_pre_get() step.
2115
-	 */
2116
-	if (!__radix_tree_preload(gfp, IDA_PRELOAD_SIZE))
2117
-		preempt_enable();
2118
-
2119
-	if (!this_cpu_read(ida_bitmap)) {
2120
-		struct ida_bitmap *bitmap = kzalloc(sizeof(*bitmap), gfp);
2121
-		if (!bitmap)
2122
-			return 0;
2123
-		if (this_cpu_cmpxchg(ida_bitmap, NULL, bitmap))
2124
-			kfree(bitmap);
2125
-	}
2126
-
2127
-	return 1;
2128
-}
2129
1472
 
2130
1473
 void __rcu **idr_get_free(struct radix_tree_root *root,
2131
1474
 			      struct radix_tree_iter *iter, gfp_t gfp,
2132
1475
 			      unsigned long max)
2133
1476
 {
2134
1477
 	struct radix_tree_node *node = NULL, *child;
2135
-	void __rcu **slot = (void __rcu **)&root->rnode;
1478
+	void __rcu **slot = (void __rcu **)&root->xa_head;
2136
1479
 	unsigned long maxindex, start = iter->next_index;
2137
1480
 	unsigned int shift, offset = 0;
2138
1481
 
..
..
@@ -2148,8 +1491,10 @@
2148
1491
 		if (error < 0)
2149
1492
 			return ERR_PTR(error);
2150
1493
 		shift = error;
2151
-		child = rcu_dereference_raw(root->rnode);
1494
+		child = rcu_dereference_raw(root->xa_head);
2152
1495
 	}
1496
+	if (start == 0 && shift == 0)
1497
+		shift = RADIX_TREE_MAP_SHIFT;
2153
1498
 
2154
1499
 	while (shift) {
2155
1500
 		shift -= RADIX_TREE_MAP_SHIFT;
..
..
@@ -2192,7 +1537,6 @@
2192
1537
 	else
2193
1538
 		iter->next_index = 1;
2194
1539
 	iter->node = node;
2195
-	__set_iter_shift(iter, shift);
2196
1540
 	set_iter_tags(iter, node, offset, IDR_FREE);
2197
1541
 
2198
1542
 	return slot;
..
..
@@ -2211,10 +1555,10 @@
2211
1555
  */
2212
1556
 void idr_destroy(struct idr *idr)
2213
1557
 {
2214
-	struct radix_tree_node *node = rcu_dereference_raw(idr->idr_rt.rnode);
1558
+	struct radix_tree_node *node = rcu_dereference_raw(idr->idr_rt.xa_head);
2215
1559
 	if (radix_tree_is_internal_node(node))
2216
1560
 		radix_tree_free_nodes(node);
2217
-	idr->idr_rt.rnode = NULL;
1561
+	idr->idr_rt.xa_head = NULL;
2218
1562
 	root_tag_set(&idr->idr_rt, IDR_FREE);
2219
1563
 }
2220
1564
 EXPORT_SYMBOL(idr_destroy);
..
..
@@ -2226,31 +1570,6 @@
2226
1570
 
2227
1571
 	memset(node, 0, sizeof(*node));
2228
1572
 	INIT_LIST_HEAD(&node->private_list);
2229
-}
2230
-
2231
-static __init unsigned long __maxindex(unsigned int height)
2232
-{
2233
-	unsigned int width = height * RADIX_TREE_MAP_SHIFT;
2234
-	int shift = RADIX_TREE_INDEX_BITS - width;
2235
-
2236
-	if (shift < 0)
2237
-		return ~0UL;
2238
-	if (shift >= BITS_PER_LONG)
2239
-		return 0UL;
2240
-	return ~0UL >> shift;
2241
-}
2242
-
2243
-static __init void radix_tree_init_maxnodes(void)
2244
-{
2245
-	unsigned long height_to_maxindex[RADIX_TREE_MAX_PATH + 1];
2246
-	unsigned int i, j;
2247
-
2248
-	for (i = 0; i < ARRAY_SIZE(height_to_maxindex); i++)
2249
-		height_to_maxindex[i] = __maxindex(i);
2250
-	for (i = 0; i < ARRAY_SIZE(height_to_maxnodes); i++) {
2251
-		for (j = i; j > 0; j--)
2252
-			height_to_maxnodes[i] += height_to_maxindex[j - 1] + 1;
2253
-	}
2254
1573
 }
2255
1574
 
2256
1575
 static int radix_tree_cpu_dead(unsigned int cpu)
..
..
@@ -2266,8 +1585,6 @@
2266
1585
 		kmem_cache_free(radix_tree_node_cachep, node);
2267
1586
 		rtp->nr--;
2268
1587
 	}
2269
-	kfree(per_cpu(ida_bitmap, cpu));
2270
-	per_cpu(ida_bitmap, cpu) = NULL;
2271
1588
 	return 0;
2272
1589
 }
2273
1590
 
..
..
@@ -2277,11 +1594,11 @@
2277
1594
 
2278
1595
 	BUILD_BUG_ON(RADIX_TREE_MAX_TAGS + __GFP_BITS_SHIFT > 32);
2279
1596
 	BUILD_BUG_ON(ROOT_IS_IDR & ~GFP_ZONEMASK);
1597
+	BUILD_BUG_ON(XA_CHUNK_SIZE > 255);
2280
1598
 	radix_tree_node_cachep = kmem_cache_create("radix_tree_node",
2281
1599
 			sizeof(struct radix_tree_node), 0,
2282
1600
 			SLAB_PANIC | SLAB_RECLAIM_ACCOUNT,
2283
1601
 			radix_tree_node_ctor);
2284
-	radix_tree_init_maxnodes();
2285
1602
 	ret = cpuhp_setup_state_nocalls(CPUHP_RADIX_DEAD, "lib/radix:dead",
2286
1603
 					NULL, radix_tree_cpu_dead);
2287
1604
 	WARN_ON(ret < 0);