forked from ~ljy/RK356X_SDK_RELEASE

blame | history | patch | commit | commitdiff
hc
2024-10-22 8ac6c7a54ed1b98d142dce24b11c6de6a1e239a5 
 kernel/lib/radix-tree.c
....@@ -1,3 +1,4 @@
1
+// SPDX-License-Identifier: GPL-2.0-or-later
12 /*
23  * Copyright (C) 2001 Momchil Velikov
34  * Portions Copyright (C) 2001 Christoph Hellwig
....@@ -6,20 +7,6 @@
67  * Copyright (C) 2012 Konstantin Khlebnikov
78  * Copyright (C) 2016 Intel, Matthew Wilcox
89  * 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.
2310  */
2411 
2512 #include <linux/bitmap.h>
....@@ -38,15 +25,12 @@
3825 #include <linux/rcupdate.h>
3926 #include <linux/slab.h>
4027 #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>
4529 
4630 /*
4731  * Radix tree node cache.
4832  */
49
-static struct kmem_cache *radix_tree_node_cachep;
33
+struct kmem_cache *radix_tree_node_cachep;
5034 
5135 /*
5236  * The radix tree is variable-height, so an insert operation not only has
....@@ -71,22 +55,12 @@
7155 #define IDR_PRELOAD_SIZE	(IDR_MAX_PATH * 2 - 1)
7256 
7357 /*
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
-/*
8258  * Per-cpu pool of preloaded nodes
8359  */
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),
8862 };
89
-static DEFINE_PER_CPU(struct radix_tree_preload, radix_tree_preloads) = { 0, };
63
+EXPORT_PER_CPU_SYMBOL_GPL(radix_tree_preloads);
9064 
9165 static inline struct radix_tree_node *entry_to_node(void *ptr)
9266 {
....@@ -98,24 +72,7 @@
9872 	return (void *)((unsigned long)ptr | RADIX_TREE_INTERNAL_NODE);
9973 }
10074 
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
11976 
12077 static inline unsigned long
12178 get_slot_offset(const struct radix_tree_node *parent, void __rcu **slot)
....@@ -129,24 +86,13 @@
12986 	unsigned int offset = (index >> parent->shift) & RADIX_TREE_MAP_MASK;
13087 	void __rcu **entry = rcu_dereference_raw(parent->slots[offset]);
13188 
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
-
14389 	*nodep = (void *)entry;
14490 	return offset;
14591 }
14692 
14793 static inline gfp_t root_gfp_mask(const struct radix_tree_root *root)
14894 {
149
-	return root->gfp_mask & (__GFP_BITS_MASK & ~GFP_ZONEMASK);
95
+	return root->xa_flags & (__GFP_BITS_MASK & ~GFP_ZONEMASK);
15096 }
15197 
15298 static inline void tag_set(struct radix_tree_node *node, unsigned int tag,
....@@ -169,32 +115,32 @@
169115 
170116 static inline void root_tag_set(struct radix_tree_root *root, unsigned tag)
171117 {
172
-	root->gfp_mask |= (__force gfp_t)(1 << (tag + ROOT_TAG_SHIFT));
118
+	root->xa_flags |= (__force gfp_t)(1 << (tag + ROOT_TAG_SHIFT));
173119 }
174120 
175121 static inline void root_tag_clear(struct radix_tree_root *root, unsigned tag)
176122 {
177
-	root->gfp_mask &= (__force gfp_t)~(1 << (tag + ROOT_TAG_SHIFT));
123
+	root->xa_flags &= (__force gfp_t)~(1 << (tag + ROOT_TAG_SHIFT));
178124 }
179125 
180126 static inline void root_tag_clear_all(struct radix_tree_root *root)
181127 {
182
-	root->gfp_mask &= (1 << ROOT_TAG_SHIFT) - 1;
128
+	root->xa_flags &= (__force gfp_t)((1 << ROOT_TAG_SHIFT) - 1);
183129 }
184130 
185131 static inline int root_tag_get(const struct radix_tree_root *root, unsigned tag)
186132 {
187
-	return (__force int)root->gfp_mask & (1 << (tag + ROOT_TAG_SHIFT));
133
+	return (__force int)root->xa_flags & (1 << (tag + ROOT_TAG_SHIFT));
188134 }
189135 
190136 static inline unsigned root_tags_get(const struct radix_tree_root *root)
191137 {
192
-	return (__force unsigned)root->gfp_mask >> ROOT_TAG_SHIFT;
138
+	return (__force unsigned)root->xa_flags >> ROOT_TAG_SHIFT;
193139 }
194140 
195141 static inline bool is_idr(const struct radix_tree_root *root)
196142 {
197
-	return !!(root->gfp_mask & ROOT_IS_IDR);
143
+	return !!(root->xa_flags & ROOT_IS_IDR);
198144 }
199145 
200146 /*
....@@ -254,7 +200,7 @@
254200 
255201 static unsigned int iter_offset(const struct radix_tree_iter *iter)
256202 {
257
-	return (iter->index >> iter_shift(iter)) & RADIX_TREE_MAP_MASK;
203
+	return iter->index & RADIX_TREE_MAP_MASK;
258204 }
259205 
260206 /*
....@@ -277,99 +223,6 @@
277223 	return (index & ~node_maxindex(node)) + (offset << node->shift);
278224 }
279225 
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
-
373226 /*
374227  * This assumes that the caller has performed appropriate preallocation, and
375228  * that the caller has pinned this thread of control to the current CPU.
....@@ -378,7 +231,7 @@
378231 radix_tree_node_alloc(gfp_t gfp_mask, struct radix_tree_node *parent,
379232 			struct radix_tree_root *root,
380233 			unsigned int shift, unsigned int offset,
381
-			unsigned int count, unsigned int exceptional)
234
+			unsigned int count, unsigned int nr_values)
382235 {
383236 	struct radix_tree_node *ret = NULL;
384237 
....@@ -425,14 +278,14 @@
425278 		ret->shift = shift;
426279 		ret->offset = offset;
427280 		ret->count = count;
428
-		ret->exceptional = exceptional;
281
+		ret->nr_values = nr_values;
429282 		ret->parent = parent;
430
-		ret->root = root;
283
+		ret->array = root;
431284 	}
432285 	return ret;
433286 }
434287 
435
-static void radix_tree_node_rcu_free(struct rcu_head *head)
288
+void radix_tree_node_rcu_free(struct rcu_head *head)
436289 {
437290 	struct radix_tree_node *node =
438291 			container_of(head, struct radix_tree_node, rcu_head);
....@@ -471,19 +324,19 @@
471324 	int ret = -ENOMEM;
472325 
473326 	/*
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
475328 	 * they should never be accounted to any particular memory cgroup.
476329 	 */
477330 	gfp_mask &= ~__GFP_ACCOUNT;
478331 
479
-	preempt_disable();
332
+	local_lock(&radix_tree_preloads.lock);
480333 	rtp = this_cpu_ptr(&radix_tree_preloads);
481334 	while (rtp->nr < nr) {
482
-		preempt_enable();
335
+		local_unlock(&radix_tree_preloads.lock);
483336 		node = kmem_cache_alloc(radix_tree_node_cachep, gfp_mask);
484337 		if (node == NULL)
485338 			goto out;
486
-		preempt_disable();
339
+		local_lock(&radix_tree_preloads.lock);
487340 		rtp = this_cpu_ptr(&radix_tree_preloads);
488341 		if (rtp->nr < nr) {
489342 			node->parent = rtp->nodes;
....@@ -525,82 +378,15 @@
525378 	if (gfpflags_allow_blocking(gfp_mask))
526379 		return __radix_tree_preload(gfp_mask, RADIX_TREE_PRELOAD_SIZE);
527380 	/* Preloading doesn't help anything with this gfp mask, skip it */
528
-	preempt_disable();
381
+	local_lock(&radix_tree_preloads.lock);
529382 	return 0;
530383 }
531384 EXPORT_SYMBOL(radix_tree_maybe_preload);
532385 
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
-
600386 static unsigned radix_tree_load_root(const struct radix_tree_root *root,
601387 		struct radix_tree_node **nodep, unsigned long *maxindex)
602388 {
603
-	struct radix_tree_node *node = rcu_dereference_raw(root->rnode);
389
+	struct radix_tree_node *node = rcu_dereference_raw(root->xa_head);
604390 
605391 	*nodep = node;
606392 
....@@ -629,7 +415,7 @@
629415 	while (index > shift_maxindex(maxshift))
630416 		maxshift += RADIX_TREE_MAP_SHIFT;
631417 
632
-	entry = rcu_dereference_raw(root->rnode);
418
+	entry = rcu_dereference_raw(root->xa_head);
633419 	if (!entry && (!is_idr(root) || root_tag_get(root, IDR_FREE)))
634420 		goto out;
635421 
....@@ -656,9 +442,9 @@
656442 		BUG_ON(shift > BITS_PER_LONG);
657443 		if (radix_tree_is_internal_node(entry)) {
658444 			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;
662448 		}
663449 		/*
664450 		 * entry was already in the radix tree, so we do not need
....@@ -666,7 +452,7 @@
666452 		 */
667453 		node->slots[0] = (void __rcu *)entry;
668454 		entry = node_to_entry(node);
669
-		rcu_assign_pointer(root->rnode, entry);
455
+		rcu_assign_pointer(root->xa_head, entry);
670456 		shift += RADIX_TREE_MAP_SHIFT;
671457 	} while (shift <= maxshift);
672458 out:
....@@ -677,13 +463,12 @@
677463  *	radix_tree_shrink    -    shrink radix tree to minimum height
678464  *	@root		radix tree root
679465  */
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)
682467 {
683468 	bool shrunk = false;
684469 
685470 	for (;;) {
686
-		struct radix_tree_node *node = rcu_dereference_raw(root->rnode);
471
+		struct radix_tree_node *node = rcu_dereference_raw(root->xa_head);
687472 		struct radix_tree_node *child;
688473 
689474 		if (!radix_tree_is_internal_node(node))
....@@ -692,15 +477,20 @@
692477 
693478 		/*
694479 		 * 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.
697481 		 */
698482 		if (node->count != 1)
699483 			break;
700484 		child = rcu_dereference_raw(node->slots[0]);
701485 		if (!child)
702486 			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))
704494 			break;
705495 
706496 		if (radix_tree_is_internal_node(child))
....@@ -711,9 +501,9 @@
711501 		 * moving the node from one part of the tree to another: if it
712502 		 * was safe to dereference the old pointer to it
713503 		 * (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.
715505 		 */
716
-		root->rnode = (void __rcu *)child;
506
+		root->xa_head = (void __rcu *)child;
717507 		if (is_idr(root) && !tag_get(node, IDR_FREE, 0))
718508 			root_tag_clear(root, IDR_FREE);
719509 
....@@ -738,8 +528,6 @@
738528 		node->count = 0;
739529 		if (!radix_tree_is_internal_node(child)) {
740530 			node->slots[0] = (void __rcu *)RADIX_TREE_RETRY;
741
-			if (update_node)
742
-				update_node(node);
743531 		}
744532 
745533 		WARN_ON_ONCE(!list_empty(&node->private_list));
....@@ -751,8 +539,7 @@
751539 }
752540 
753541 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)
756543 {
757544 	bool deleted = false;
758545 
....@@ -761,9 +548,8 @@
761548 
762549 		if (node->count) {
763550 			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);
767553 			return deleted;
768554 		}
769555 
....@@ -778,7 +564,7 @@
778564 			 */
779565 			if (!is_idr(root))
780566 				root_tag_clear_all(root);
781
-			root->rnode = NULL;
567
+			root->xa_head = NULL;
782568 		}
783569 
784570 		WARN_ON_ONCE(!list_empty(&node->private_list));
....@@ -795,7 +581,6 @@
795581  *	__radix_tree_create	-	create a slot in a radix tree
796582  *	@root:		radix tree root
797583  *	@index:		index key
798
- *	@order:		index occupies 2^order aligned slots
799584  *	@nodep:		returns node
800585  *	@slotp:		returns slot
801586  *
....@@ -803,36 +588,34 @@
803588  *	at position @index in the radix tree @root.
804589  *
805590  *	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
807592  *	pointing to a node, in which case *@nodep will be NULL.
808593  *
809594  *	Returns -ENOMEM, or 0 for success.
810595  */
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)
814599 {
815600 	struct radix_tree_node *node = NULL, *child;
816
-	void __rcu **slot = (void __rcu **)&root->rnode;
601
+	void __rcu **slot = (void __rcu **)&root->xa_head;
817602 	unsigned long maxindex;
818603 	unsigned int shift, offset = 0;
819
-	unsigned long max = index | ((1UL << order) - 1);
604
+	unsigned long max = index;
820605 	gfp_t gfp = root_gfp_mask(root);
821606 
822607 	shift = radix_tree_load_root(root, &child, &maxindex);
823608 
824609 	/* Make sure the tree is high enough.  */
825
-	if (order > 0 && max == ((1UL << order) - 1))
826
-		max++;
827610 	if (max > maxindex) {
828611 		int error = radix_tree_extend(root, gfp, max, shift);
829612 		if (error < 0)
830613 			return error;
831614 		shift = error;
832
-		child = rcu_dereference_raw(root->rnode);
615
+		child = rcu_dereference_raw(root->xa_head);
833616 	}
834617 
835
-	while (shift > order) {
618
+	while (shift > 0) {
836619 		shift -= RADIX_TREE_MAP_SHIFT;
837620 		if (child == NULL) {
838621 			/* Have to add a child node.  */
....@@ -875,8 +658,7 @@
875658 
876659 	for (;;) {
877660 		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) {
880662 			child = entry_to_node(entry);
881663 			offset = 0;
882664 			continue;
....@@ -894,96 +676,30 @@
894676 	}
895677 }
896678 
897
-#ifdef CONFIG_RADIX_TREE_MULTIORDER
898679 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)
963681 {
964682 	if (*slot)
965683 		return -EEXIST;
966684 	rcu_assign_pointer(*slot, item);
967685 	if (node) {
968686 		node->count++;
969
-		if (radix_tree_exceptional_entry(item))
970
-			node->exceptional++;
687
+		if (xa_is_value(item))
688
+			node->nr_values++;
971689 	}
972690 	return 1;
973691 }
974
-#endif
975692 
976693 /**
977694  *	__radix_tree_insert    -    insert into a radix tree
978695  *	@root:		radix tree root
979696  *	@index:		index key
980
- *	@order:		key covers the 2^order indices around index
981697  *	@item:		item to insert
982698  *
983699  *	Insert an item into the radix tree at position @index.
984700  */
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)
987703 {
988704 	struct radix_tree_node *node;
989705 	void __rcu **slot;
....@@ -991,11 +707,11 @@
991707 
992708 	BUG_ON(radix_tree_is_internal_node(item));
993709 
994
-	error = __radix_tree_create(root, index, order, &node, &slot);
710
+	error = __radix_tree_create(root, index, &node, &slot);
995711 	if (error)
996712 		return error;
997713 
998
-	error = insert_entries(node, slot, item, order, false);
714
+	error = insert_entries(node, slot, item, false);
999715 	if (error < 0)
1000716 		return error;
1001717 
....@@ -1010,7 +726,7 @@
1010726 
1011727 	return 0;
1012728 }
1013
-EXPORT_SYMBOL(__radix_tree_insert);
729
+EXPORT_SYMBOL(radix_tree_insert);
1014730 
1015731 /**
1016732  *	__radix_tree_lookup	-	lookup an item in a radix tree
....@@ -1023,7 +739,7 @@
1023739  *	tree @root.
1024740  *
1025741  *	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
1027743  *	pointing to a node, in which case *@nodep will be NULL.
1028744  */
1029745 void *__radix_tree_lookup(const struct radix_tree_root *root,
....@@ -1036,7 +752,7 @@
1036752 
1037753  restart:
1038754 	parent = NULL;
1039
-	slot = (void __rcu **)&root->rnode;
755
+	slot = (void __rcu **)&root->xa_head;
1040756 	radix_tree_load_root(root, &node, &maxindex);
1041757 	if (index > maxindex)
1042758 		return NULL;
....@@ -1044,11 +760,13 @@
1044760 	while (radix_tree_is_internal_node(node)) {
1045761 		unsigned offset;
1046762 
1047
-		if (node == RADIX_TREE_RETRY)
1048
-			goto restart;
1049763 		parent = entry_to_node(node);
1050764 		offset = radix_tree_descend(parent, &node, index);
1051765 		slot = parent->slots + offset;
766
+		if (node == RADIX_TREE_RETRY)
767
+			goto restart;
768
+		if (parent->shift == 0)
769
+			break;
1052770 	}
1053771 
1054772 	if (nodep)
....@@ -1100,36 +818,12 @@
1100818 }
1101819 EXPORT_SYMBOL(radix_tree_lookup);
1102820 
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
-
1123821 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)
1125823 {
1126
-	if (WARN_ON_ONCE(radix_tree_is_internal_node(item)))
1127
-		return;
1128
-
1129
-	if (node && (count || exceptional)) {
824
+	if (node && (count || values)) {
1130825 		node->count += count;
1131
-		node->exceptional += exceptional;
1132
-		replace_sibling_entries(node, slot, count, exceptional);
826
+		node->nr_values += values;
1133827 	}
1134828 
1135829 	rcu_assign_pointer(*slot, item);
....@@ -1172,37 +866,31 @@
1172866  * @node:		pointer to tree node
1173867  * @slot:		pointer to slot in @node
1174868  * @item:		new item to store in the slot.
1175
- * @update_node:	callback for changing leaf nodes
1176869  *
1177870  * For use with __radix_tree_lookup().  Caller must hold tree write locked
1178871  * across slot lookup and replacement.
1179872  */
1180873 void __radix_tree_replace(struct radix_tree_root *root,
1181874 			  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)
1184876 {
1185877 	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);
1188879 	int count = calculate_count(root, node, slot, item, old);
1189880 
1190881 	/*
1191
-	 * This function supports replacing exceptional entries and
882
+	 * This function supports replacing value entries and
1192883 	 * 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.
1194885 	 */
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);
1198889 
1199890 	if (!node)
1200891 		return;
1201892 
1202
-	if (update_node)
1203
-		update_node(node);
1204
-
1205
-	delete_node(root, node, update_node);
893
+	delete_node(root, node);
1206894 }
1207895 
1208896 /**
....@@ -1211,12 +899,12 @@
1211899  * @slot:	pointer to slot
1212900  * @item:	new item to store in the slot.
1213901  *
1214
- * For use with radix_tree_lookup_slot(), radix_tree_gang_lookup_slot(),
902
+ * For use with radix_tree_lookup_slot() and
1215903  * radix_tree_gang_lookup_tag_slot().  Caller must hold tree write locked
1216904  * across slot lookup and replacement.
1217905  *
1218906  * 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
1220908  * inside the radix tree node. When switching from one type of entry or
1221909  * deleting, use __radix_tree_lookup() and __radix_tree_replace() or
1222910  * radix_tree_iter_replace().
....@@ -1224,7 +912,7 @@
1224912 void radix_tree_replace_slot(struct radix_tree_root *root,
1225913 			     void __rcu **slot, void *item)
1226914 {
1227
-	__radix_tree_replace(root, NULL, slot, item, NULL);
915
+	__radix_tree_replace(root, NULL, slot, item);
1228916 }
1229917 EXPORT_SYMBOL(radix_tree_replace_slot);
1230918 
....@@ -1234,161 +922,15 @@
1234922  * @slot:	pointer to slot
1235923  * @item:	new item to store in the slot.
1236924  *
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.
1239927  */
1240928 void radix_tree_iter_replace(struct radix_tree_root *root,
1241929 				const struct radix_tree_iter *iter,
1242930 				void __rcu **slot, void *item)
1243931 {
1244
-	__radix_tree_replace(root, iter->node, slot, item, NULL);
932
+	__radix_tree_replace(root, iter->node, slot, item);
1245933 }
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
1392934 
1393935 static void node_tag_set(struct radix_tree_root *root,
1394936 				struct radix_tree_node *node,
....@@ -1447,18 +989,6 @@
1447989 }
1448990 EXPORT_SYMBOL(radix_tree_tag_set);
1449991 
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
-
1462992 static void node_tag_clear(struct radix_tree_root *root,
1463993 				struct radix_tree_node *node,
1464994 				unsigned int tag, unsigned int offset)
....@@ -1498,7 +1028,7 @@
14981028 {
14991029 	struct radix_tree_node *node, *parent;
15001030 	unsigned long maxindex;
1501
-	int uninitialized_var(offset);
1031
+	int offset;
15021032 
15031033 	radix_tree_load_root(root, &node, &maxindex);
15041034 	if (index > maxindex)
....@@ -1574,14 +1104,6 @@
15741104 }
15751105 EXPORT_SYMBOL(radix_tree_tag_get);
15761106 
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
-
15851107 /* Construct iter->tags bit-mask from node->tags[tag] array */
15861108 static void set_iter_tags(struct radix_tree_iter *iter,
15871109 				struct radix_tree_node *node, unsigned offset,
....@@ -1608,92 +1130,10 @@
16081130 	}
16091131 }
16101132 
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
-
16891133 void __rcu **radix_tree_iter_resume(void __rcu **slot,
16901134 					struct radix_tree_iter *iter)
16911135 {
1692
-	struct radix_tree_node *node;
1693
-
1694
-	slot++;
16951136 	iter->index = __radix_tree_iter_add(iter, 1);
1696
-	skip_siblings(&node, slot, iter);
16971137 	iter->next_index = iter->index;
16981138 	iter->tags = 0;
16991139 	return NULL;
....@@ -1744,8 +1184,7 @@
17441184 		iter->next_index = maxindex + 1;
17451185 		iter->tags = 1;
17461186 		iter->node = NULL;
1747
-		__set_iter_shift(iter, 0);
1748
-		return (void __rcu **)&root->rnode;
1187
+		return (void __rcu **)&root->xa_head;
17491188 	}
17501189 
17511190 	do {
....@@ -1765,8 +1204,6 @@
17651204 				while (++offset	< RADIX_TREE_MAP_SIZE) {
17661205 					void *slot = rcu_dereference_raw(
17671206 							node->slots[offset]);
1768
-					if (is_sibling_entry(node, slot))
1769
-						continue;
17701207 					if (slot)
17711208 						break;
17721209 				}
....@@ -1784,13 +1221,12 @@
17841221 			goto restart;
17851222 		if (child == RADIX_TREE_RETRY)
17861223 			break;
1787
-	} while (radix_tree_is_internal_node(child));
1224
+	} while (node->shift && radix_tree_is_internal_node(child));
17881225 
17891226 	/* Update the iterator state */
1790
-	iter->index = (index &~ node_maxindex(node)) | (offset << node->shift);
1227
+	iter->index = (index &~ node_maxindex(node)) | offset;
17911228 	iter->next_index = (index | node_maxindex(node)) + 1;
17921229 	iter->node = node;
1793
-	__set_iter_shift(iter, node->shift);
17941230 
17951231 	if (flags & RADIX_TREE_ITER_TAGGED)
17961232 		set_iter_tags(iter, node, offset, tag);
....@@ -1845,48 +1281,6 @@
18451281 	return ret;
18461282 }
18471283 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);
18901284 
18911285 /**
18921286  *	radix_tree_gang_lookup_tag - perform multiple lookup on a radix tree
....@@ -1964,28 +1358,11 @@
19641358 }
19651359 EXPORT_SYMBOL(radix_tree_gang_lookup_tag_slot);
19661360 
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
-
19841361 static bool __radix_tree_delete(struct radix_tree_root *root,
19851362 				struct radix_tree_node *node, void __rcu **slot)
19861363 {
19871364 	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;
19891366 	unsigned offset = get_slot_offset(node, slot);
19901367 	int tag;
19911368 
....@@ -1995,8 +1372,8 @@
19951372 		for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++)
19961373 			node_tag_clear(root, node, tag, offset);
19971374 
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);
20001377 }
20011378 
20021379 /**
....@@ -2068,19 +1445,6 @@
20681445 }
20691446 EXPORT_SYMBOL(radix_tree_delete);
20701447 
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
-
20841448 /**
20851449  *	radix_tree_tagged - test whether any items in the tree are tagged
20861450  *	@root:		radix tree root
....@@ -2102,37 +1466,16 @@
21021466 void idr_preload(gfp_t gfp_mask)
21031467 {
21041468 	if (__radix_tree_preload(gfp_mask, IDR_PRELOAD_SIZE))
2105
-		preempt_disable();
1469
+		local_lock(&radix_tree_preloads.lock);
21061470 }
21071471 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
-}
21291472 
21301473 void __rcu **idr_get_free(struct radix_tree_root *root,
21311474 			      struct radix_tree_iter *iter, gfp_t gfp,
21321475 			      unsigned long max)
21331476 {
21341477 	struct radix_tree_node *node = NULL, *child;
2135
-	void __rcu **slot = (void __rcu **)&root->rnode;
1478
+	void __rcu **slot = (void __rcu **)&root->xa_head;
21361479 	unsigned long maxindex, start = iter->next_index;
21371480 	unsigned int shift, offset = 0;
21381481 
....@@ -2148,8 +1491,10 @@
21481491 		if (error < 0)
21491492 			return ERR_PTR(error);
21501493 		shift = error;
2151
-		child = rcu_dereference_raw(root->rnode);
1494
+		child = rcu_dereference_raw(root->xa_head);
21521495 	}
1496
+	if (start == 0 && shift == 0)
1497
+		shift = RADIX_TREE_MAP_SHIFT;
21531498 
21541499 	while (shift) {
21551500 		shift -= RADIX_TREE_MAP_SHIFT;
....@@ -2192,7 +1537,6 @@
21921537 	else
21931538 		iter->next_index = 1;
21941539 	iter->node = node;
2195
-	__set_iter_shift(iter, shift);
21961540 	set_iter_tags(iter, node, offset, IDR_FREE);
21971541 
21981542 	return slot;
....@@ -2211,10 +1555,10 @@
22111555  */
22121556 void idr_destroy(struct idr *idr)
22131557 {
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);
22151559 	if (radix_tree_is_internal_node(node))
22161560 		radix_tree_free_nodes(node);
2217
-	idr->idr_rt.rnode = NULL;
1561
+	idr->idr_rt.xa_head = NULL;
22181562 	root_tag_set(&idr->idr_rt, IDR_FREE);
22191563 }
22201564 EXPORT_SYMBOL(idr_destroy);
....@@ -2226,31 +1570,6 @@
22261570 
22271571 	memset(node, 0, sizeof(*node));
22281572 	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
-	}
22541573 }
22551574 
22561575 static int radix_tree_cpu_dead(unsigned int cpu)
....@@ -2266,8 +1585,6 @@
22661585 		kmem_cache_free(radix_tree_node_cachep, node);
22671586 		rtp->nr--;
22681587 	}
2269
-	kfree(per_cpu(ida_bitmap, cpu));
2270
-	per_cpu(ida_bitmap, cpu) = NULL;
22711588 	return 0;
22721589 }
22731590 
....@@ -2277,11 +1594,11 @@
22771594 
22781595 	BUILD_BUG_ON(RADIX_TREE_MAX_TAGS + __GFP_BITS_SHIFT > 32);
22791596 	BUILD_BUG_ON(ROOT_IS_IDR & ~GFP_ZONEMASK);
1597
+	BUILD_BUG_ON(XA_CHUNK_SIZE > 255);
22801598 	radix_tree_node_cachep = kmem_cache_create("radix_tree_node",
22811599 			sizeof(struct radix_tree_node), 0,
22821600 			SLAB_PANIC | SLAB_RECLAIM_ACCOUNT,
22831601 			radix_tree_node_ctor);
2284
-	radix_tree_init_maxnodes();
22851602 	ret = cpuhp_setup_state_nocalls(CPUHP_RADIX_DEAD, "lib/radix:dead",
22861603 					NULL, radix_tree_cpu_dead);
22871604 	WARN_ON(ret < 0);