path: root/lib/radix-tree.c (plain)
blob: 8e6d552c40ddfc7fa745a8a8acf34ee17f02bc3d

1	/*
2	* Copyright (C) 2001 Momchil Velikov
3	* Portions Copyright (C) 2001 Christoph Hellwig
4	* Copyright (C) 2005 SGI, Christoph Lameter
5	* Copyright (C) 2006 Nick Piggin
6	* Copyright (C) 2012 Konstantin Khlebnikov
7	* Copyright (C) 2016 Intel, Matthew Wilcox
8	* 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	*/
24
25	#include <linux/errno.h>
26	#include <linux/init.h>
27	#include <linux/kernel.h>
28	#include <linux/export.h>
29	#include <linux/radix-tree.h>
30	#include <linux/percpu.h>
31	#include <linux/slab.h>
32	#include <linux/kmemleak.h>
33	#include <linux/notifier.h>
34	#include <linux/cpu.h>
35	#include <linux/string.h>
36	#include <linux/bitops.h>
37	#include <linux/rcupdate.h>
38	#include <linux/preempt.h> /* in_interrupt() */
39
40
41	/* Number of nodes in fully populated tree of given height */
42	static unsigned long height_to_maxnodes[RADIX_TREE_MAX_PATH + 1] __read_mostly;
43
44	/*
45	* Radix tree node cache.
46	*/
47	static struct kmem_cache *radix_tree_node_cachep;
48
49	/*
50	* The radix tree is variable-height, so an insert operation not only has
51	* to build the branch to its corresponding item, it also has to build the
52	* branch to existing items if the size has to be increased (by
53	* radix_tree_extend).
54	*
55	* The worst case is a zero height tree with just a single item at index 0,
56	* and then inserting an item at index ULONG_MAX. This requires 2 new branches
57	* of RADIX_TREE_MAX_PATH size to be created, with only the root node shared.
58	* Hence:
59	*/
60	#define RADIX_TREE_PRELOAD_SIZE (RADIX_TREE_MAX_PATH * 2 - 1)
61
62	/*
63	* Per-cpu pool of preloaded nodes
64	*/
65	struct radix_tree_preload {
66	unsigned nr;
67	/* nodes->private_data points to next preallocated node */
68	struct radix_tree_node *nodes;
69	};
70	static DEFINE_PER_CPU(struct radix_tree_preload, radix_tree_preloads) = { 0, };
71
72	static inline void *node_to_entry(void *ptr)
73	{
74	return (void *)((unsigned long)ptr | RADIX_TREE_INTERNAL_NODE);
75	}
76
77	#define RADIX_TREE_RETRY node_to_entry(NULL)
78
79	#ifdef CONFIG_RADIX_TREE_MULTIORDER
80	/* Sibling slots point directly to another slot in the same node */
81	static inline bool is_sibling_entry(struct radix_tree_node *parent, void *node)
82	{
83	void **ptr = node;
84	return (parent->slots <= ptr) &&
85	(ptr < parent->slots + RADIX_TREE_MAP_SIZE);
86	}
87	#else
88	static inline bool is_sibling_entry(struct radix_tree_node *parent, void *node)
89	{
90	return false;
91	}
92	#endif
93
94	static inline unsigned long get_slot_offset(struct radix_tree_node *parent,
95	void **slot)
96	{
97	return slot - parent->slots;
98	}
99
100	static unsigned int radix_tree_descend(struct radix_tree_node *parent,
101	struct radix_tree_node **nodep, unsigned long index)
102	{
103	unsigned int offset = (index >> parent->shift) & RADIX_TREE_MAP_MASK;
104	void **entry = rcu_dereference_raw(parent->slots[offset]);
105
106	#ifdef CONFIG_RADIX_TREE_MULTIORDER
107	if (radix_tree_is_internal_node(entry)) {
108	if (is_sibling_entry(parent, entry)) {
109	void **sibentry = (void **) entry_to_node(entry);
110	offset = get_slot_offset(parent, sibentry);
111	entry = rcu_dereference_raw(*sibentry);
112	}
113	}
114	#endif
115
116	*nodep = (void *)entry;
117	return offset;
118	}
119
120	static inline gfp_t root_gfp_mask(struct radix_tree_root *root)
121	{
122	return root->gfp_mask & __GFP_BITS_MASK;
123	}
124
125	static inline void tag_set(struct radix_tree_node *node, unsigned int tag,
126	int offset)
127	{
128	__set_bit(offset, node->tags[tag]);
129	}
130
131	static inline void tag_clear(struct radix_tree_node *node, unsigned int tag,
132	int offset)
133	{
134	__clear_bit(offset, node->tags[tag]);
135	}
136
137	static inline int tag_get(struct radix_tree_node *node, unsigned int tag,
138	int offset)
139	{
140	return test_bit(offset, node->tags[tag]);
141	}
142
143	static inline void root_tag_set(struct radix_tree_root *root, unsigned int tag)
144	{
145	root->gfp_mask |= (__force gfp_t)(1 << (tag + __GFP_BITS_SHIFT));
146	}
147
148	static inline void root_tag_clear(struct radix_tree_root *root, unsigned tag)
149	{
150	root->gfp_mask &= (__force gfp_t)~(1 << (tag + __GFP_BITS_SHIFT));
151	}
152
153	static inline void root_tag_clear_all(struct radix_tree_root *root)
154	{
155	root->gfp_mask &= __GFP_BITS_MASK;
156	}
157
158	static inline int root_tag_get(struct radix_tree_root *root, unsigned int tag)
159	{
160	return (__force int)root->gfp_mask & (1 << (tag + __GFP_BITS_SHIFT));
161	}
162
163	static inline unsigned root_tags_get(struct radix_tree_root *root)
164	{
165	return (__force unsigned)root->gfp_mask >> __GFP_BITS_SHIFT;
166	}
167
168	/*
169	* Returns 1 if any slot in the node has this tag set.
170	* Otherwise returns 0.
171	*/
172	static inline int any_tag_set(struct radix_tree_node *node, unsigned int tag)
173	{
174	unsigned idx;
175	for (idx = 0; idx < RADIX_TREE_TAG_LONGS; idx++) {
176	if (node->tags[tag][idx])
177	return 1;
178	}
179	return 0;
180	}
181
182	/**
183	* radix_tree_find_next_bit - find the next set bit in a memory region
184	*
185	* @addr: The address to base the search on
186	* @size: The bitmap size in bits
187	* @offset: The bitnumber to start searching at
188	*
189	* Unrollable variant of find_next_bit() for constant size arrays.
190	* Tail bits starting from size to roundup(size, BITS_PER_LONG) must be zero.
191	* Returns next bit offset, or size if nothing found.
192	*/
193	static __always_inline unsigned long
194	radix_tree_find_next_bit(const unsigned long *addr,
195	unsigned long size, unsigned long offset)
196	{
197	if (!__builtin_constant_p(size))
198	return find_next_bit(addr, size, offset);
199
200	if (offset < size) {
201	unsigned long tmp;
202
203	addr += offset / BITS_PER_LONG;
204	tmp = *addr >> (offset % BITS_PER_LONG);
205	if (tmp)
206	return __ffs(tmp) + offset;
207	offset = (offset + BITS_PER_LONG) & ~(BITS_PER_LONG - 1);
208	while (offset < size) {
209	tmp = *++addr;
210	if (tmp)
211	return __ffs(tmp) + offset;
212	offset += BITS_PER_LONG;
213	}
214	}
215	return size;
216	}
217
218	#ifndef __KERNEL__
219	static void dump_node(struct radix_tree_node *node, unsigned long index)
220	{
221	unsigned long i;
222
223	pr_debug("radix node: %p offset %d tags %lx %lx %lx shift %d count %d parent %p\n",
224	node, node->offset,
225	node->tags[0][0], node->tags[1][0], node->tags[2][0],
226	node->shift, node->count, node->parent);
227
228	for (i = 0; i < RADIX_TREE_MAP_SIZE; i++) {
229	unsigned long first = index | (i << node->shift);
230	unsigned long last = first | ((1UL << node->shift) - 1);
231	void *entry = node->slots[i];
232	if (!entry)
233	continue;
234	if (is_sibling_entry(node, entry)) {
235	pr_debug("radix sblng %p offset %ld val %p indices %ld-%ld\n",
236	entry, i,
237	*(void **)entry_to_node(entry),
238	first, last);
239	} else if (!radix_tree_is_internal_node(entry)) {
240	pr_debug("radix entry %p offset %ld indices %ld-%ld\n",
241	entry, i, first, last);
242	} else {
243	dump_node(entry_to_node(entry), first);
244	}
245	}
246	}
247
248	/* For debug */
249	static void radix_tree_dump(struct radix_tree_root *root)
250	{
251	pr_debug("radix root: %p rnode %p tags %x\n",
252	root, root->rnode,
253	root->gfp_mask >> __GFP_BITS_SHIFT);
254	if (!radix_tree_is_internal_node(root->rnode))
255	return;
256	dump_node(entry_to_node(root->rnode), 0);
257	}
258	#endif
259
260	/*
261	* This assumes that the caller has performed appropriate preallocation, and
262	* that the caller has pinned this thread of control to the current CPU.
263	*/
264	static struct radix_tree_node *
265	radix_tree_node_alloc(struct radix_tree_root *root)
266	{
267	struct radix_tree_node *ret = NULL;
268	gfp_t gfp_mask = root_gfp_mask(root);
269
270	/*
271	* Preload code isn't irq safe and it doesn't make sense to use
272	* preloading during an interrupt anyway as all the allocations have
273	* to be atomic. So just do normal allocation when in interrupt.
274	*/
275	if (!gfpflags_allow_blocking(gfp_mask) && !in_interrupt()) {
276	struct radix_tree_preload *rtp;
277
278	/*
279	* Even if the caller has preloaded, try to allocate from the
280	* cache first for the new node to get accounted to the memory
281	* cgroup.
282	*/
283	ret = kmem_cache_alloc(radix_tree_node_cachep,
284	gfp_mask | __GFP_NOWARN);
285	if (ret)
286	goto out;
287
288	/*
289	* Provided the caller has preloaded here, we will always
290	* succeed in getting a node here (and never reach
291	* kmem_cache_alloc)
292	*/
293	rtp = this_cpu_ptr(&radix_tree_preloads);
294	if (rtp->nr) {
295	ret = rtp->nodes;
296	rtp->nodes = ret->private_data;
297	ret->private_data = NULL;
298	rtp->nr--;
299	}
300	/*
301	* Update the allocation stack trace as this is more useful
302	* for debugging.
303	*/
304	kmemleak_update_trace(ret);
305	goto out;
306	}
307	ret = kmem_cache_alloc(radix_tree_node_cachep, gfp_mask);
308	out:
309	BUG_ON(radix_tree_is_internal_node(ret));
310	return ret;
311	}
312
313	static void radix_tree_node_rcu_free(struct rcu_head *head)
314	{
315	struct radix_tree_node *node =
316	container_of(head, struct radix_tree_node, rcu_head);
317	int i;
318
319	/*
320	* must only free zeroed nodes into the slab. radix_tree_shrink
321	* can leave us with a non-NULL entry in the first slot, so clear
322	* that here to make sure.
323	*/
324	for (i = 0; i < RADIX_TREE_MAX_TAGS; i++)
325	tag_clear(node, i, 0);
326
327	node->slots[0] = NULL;
328	node->count = 0;
329
330	kmem_cache_free(radix_tree_node_cachep, node);
331	}
332
333	static inline void
334	radix_tree_node_free(struct radix_tree_node *node)
335	{
336	call_rcu(&node->rcu_head, radix_tree_node_rcu_free);
337	}
338
339	/*
340	* Load up this CPU's radix_tree_node buffer with sufficient objects to
341	* ensure that the addition of a single element in the tree cannot fail. On
342	* success, return zero, with preemption disabled. On error, return -ENOMEM
343	* with preemption not disabled.
344	*
345	* To make use of this facility, the radix tree must be initialised without
346	* __GFP_DIRECT_RECLAIM being passed to INIT_RADIX_TREE().
347	*/
348	static int __radix_tree_preload(gfp_t gfp_mask, int nr)
349	{
350	struct radix_tree_preload *rtp;
351	struct radix_tree_node *node;
352	int ret = -ENOMEM;
353
354	/*
355	* Nodes preloaded by one cgroup can be be used by another cgroup, so
356	* they should never be accounted to any particular memory cgroup.
357	*/
358	gfp_mask &= ~__GFP_ACCOUNT;
359
360	preempt_disable();
361	rtp = this_cpu_ptr(&radix_tree_preloads);
362	while (rtp->nr < nr) {
363	preempt_enable();
364	node = kmem_cache_alloc(radix_tree_node_cachep, gfp_mask);
365	if (node == NULL)
366	goto out;
367	preempt_disable();
368	rtp = this_cpu_ptr(&radix_tree_preloads);
369	if (rtp->nr < nr) {
370	node->private_data = rtp->nodes;
371	rtp->nodes = node;
372	rtp->nr++;
373	} else {
374	kmem_cache_free(radix_tree_node_cachep, node);
375	}
376	}
377	ret = 0;
378	out:
379	return ret;
380	}
381
382	/*
383	* Load up this CPU's radix_tree_node buffer with sufficient objects to
384	* ensure that the addition of a single element in the tree cannot fail. On
385	* success, return zero, with preemption disabled. On error, return -ENOMEM
386	* with preemption not disabled.
387	*
388	* To make use of this facility, the radix tree must be initialised without
389	* __GFP_DIRECT_RECLAIM being passed to INIT_RADIX_TREE().
390	*/
391	int radix_tree_preload(gfp_t gfp_mask)
392	{
393	/* Warn on non-sensical use... */
394	WARN_ON_ONCE(!gfpflags_allow_blocking(gfp_mask));
395	return __radix_tree_preload(gfp_mask, RADIX_TREE_PRELOAD_SIZE);
396	}
397	EXPORT_SYMBOL(radix_tree_preload);
398
399	/*
400	* The same as above function, except we don't guarantee preloading happens.
401	* We do it, if we decide it helps. On success, return zero with preemption
402	* disabled. On error, return -ENOMEM with preemption not disabled.
403	*/
404	int radix_tree_maybe_preload(gfp_t gfp_mask)
405	{
406	if (gfpflags_allow_blocking(gfp_mask))
407	return __radix_tree_preload(gfp_mask, RADIX_TREE_PRELOAD_SIZE);
408	/* Preloading doesn't help anything with this gfp mask, skip it */
409	preempt_disable();
410	return 0;
411	}
412	EXPORT_SYMBOL(radix_tree_maybe_preload);
413
414	/*
415	* The same as function above, but preload number of nodes required to insert
416	* (1 << order) continuous naturally-aligned elements.
417	*/
418	int radix_tree_maybe_preload_order(gfp_t gfp_mask, int order)
419	{
420	unsigned long nr_subtrees;
421	int nr_nodes, subtree_height;
422
423	/* Preloading doesn't help anything with this gfp mask, skip it */
424	if (!gfpflags_allow_blocking(gfp_mask)) {
425	preempt_disable();
426	return 0;
427	}
428
429	/*
430	* Calculate number and height of fully populated subtrees it takes to
431	* store (1 << order) elements.
432	*/
433	nr_subtrees = 1 << order;
434	for (subtree_height = 0; nr_subtrees > RADIX_TREE_MAP_SIZE;
435	subtree_height++)
436	nr_subtrees >>= RADIX_TREE_MAP_SHIFT;
437
438	/*
439	* The worst case is zero height tree with a single item at index 0 and
440	* then inserting items starting at ULONG_MAX - (1 << order).
441	*
442	* This requires RADIX_TREE_MAX_PATH nodes to build branch from root to
443	* 0-index item.
444	*/
445	nr_nodes = RADIX_TREE_MAX_PATH;
446
447	/* Plus branch to fully populated subtrees. */
448	nr_nodes += RADIX_TREE_MAX_PATH - subtree_height;
449
450	/* Root node is shared. */
451	nr_nodes--;
452
453	/* Plus nodes required to build subtrees. */
454	nr_nodes += nr_subtrees * height_to_maxnodes[subtree_height];
455
456	return __radix_tree_preload(gfp_mask, nr_nodes);
457	}
458
459	/*
460	* The maximum index which can be stored in a radix tree
461	*/
462	static inline unsigned long shift_maxindex(unsigned int shift)
463	{
464	return (RADIX_TREE_MAP_SIZE << shift) - 1;
465	}
466
467	static inline unsigned long node_maxindex(struct radix_tree_node *node)
468	{
469	return shift_maxindex(node->shift);
470	}
471
472	static unsigned radix_tree_load_root(struct radix_tree_root *root,
473	struct radix_tree_node **nodep, unsigned long *maxindex)
474	{
475	struct radix_tree_node *node = rcu_dereference_raw(root->rnode);
476
477	*nodep = node;
478
479	if (likely(radix_tree_is_internal_node(node))) {
480	node = entry_to_node(node);
481	*maxindex = node_maxindex(node);
482	return node->shift + RADIX_TREE_MAP_SHIFT;
483	}
484
485	*maxindex = 0;
486	return 0;
487	}
488
489	/*
490	* Extend a radix tree so it can store key @index.
491	*/
492	static int radix_tree_extend(struct radix_tree_root *root,
493	unsigned long index, unsigned int shift)
494	{
495	struct radix_tree_node *slot;
496	unsigned int maxshift;
497	int tag;
498
499	/* Figure out what the shift should be. */
500	maxshift = shift;
501	while (index > shift_maxindex(maxshift))
502	maxshift += RADIX_TREE_MAP_SHIFT;
503
504	slot = root->rnode;
505	if (!slot)
506	goto out;
507
508	do {
509	struct radix_tree_node *node = radix_tree_node_alloc(root);
510
511	if (!node)
512	return -ENOMEM;
513
514	/* Propagate the aggregated tag info into the new root */
515	for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) {
516	if (root_tag_get(root, tag))
517	tag_set(node, tag, 0);
518	}
519
520	BUG_ON(shift > BITS_PER_LONG);
521	node->shift = shift;
522	node->offset = 0;
523	node->count = 1;
524	node->parent = NULL;
525	if (radix_tree_is_internal_node(slot))
526	entry_to_node(slot)->parent = node;
527	node->slots[0] = slot;
528	slot = node_to_entry(node);
529	rcu_assign_pointer(root->rnode, slot);
530	shift += RADIX_TREE_MAP_SHIFT;
531	} while (shift <= maxshift);
532	out:
533	return maxshift + RADIX_TREE_MAP_SHIFT;
534	}
535
536	/**
537	* __radix_tree_create - create a slot in a radix tree
538	* @root: radix tree root
539	* @index: index key
540	* @order: index occupies 2^order aligned slots
541	* @nodep: returns node
542	* @slotp: returns slot
543	*
544	* Create, if necessary, and return the node and slot for an item
545	* at position @index in the radix tree @root.
546	*
547	* Until there is more than one item in the tree, no nodes are
548	* allocated and @root->rnode is used as a direct slot instead of
549	* pointing to a node, in which case *@nodep will be NULL.
550	*
551	* Returns -ENOMEM, or 0 for success.
552	*/
553	int __radix_tree_create(struct radix_tree_root *root, unsigned long index,
554	unsigned order, struct radix_tree_node **nodep,
555	void ***slotp)
556	{
557	struct radix_tree_node *node = NULL, *child;
558	void **slot = (void **)&root->rnode;
559	unsigned long maxindex;
560	unsigned int shift, offset = 0;
561	unsigned long max = index | ((1UL << order) - 1);
562
563	shift = radix_tree_load_root(root, &child, &maxindex);
564
565	/* Make sure the tree is high enough. */
566	if (max > maxindex) {
567	int error = radix_tree_extend(root, max, shift);
568	if (error < 0)
569	return error;
570	shift = error;
571	child = root->rnode;
572	if (order == shift)
573	shift += RADIX_TREE_MAP_SHIFT;
574	}
575
576	while (shift > order) {
577	shift -= RADIX_TREE_MAP_SHIFT;
578	if (child == NULL) {
579	/* Have to add a child node. */
580	child = radix_tree_node_alloc(root);
581	if (!child)
582	return -ENOMEM;
583	child->shift = shift;
584	child->offset = offset;
585	child->parent = node;
586	rcu_assign_pointer(*slot, node_to_entry(child));
587	if (node)
588	node->count++;
589	} else if (!radix_tree_is_internal_node(child))
590	break;
591
592	/* Go a level down */
593	node = entry_to_node(child);
594	offset = radix_tree_descend(node, &child, index);
595	slot = &node->slots[offset];
596	}
597
598	#ifdef CONFIG_RADIX_TREE_MULTIORDER
599	/* Insert pointers to the canonical entry */
600	if (order > shift) {
601	unsigned i, n = 1 << (order - shift);
602	offset = offset & ~(n - 1);
603	slot = &node->slots[offset];
604	child = node_to_entry(slot);
605	for (i = 0; i < n; i++) {
606	if (slot[i])
607	return -EEXIST;
608	}
609
610	for (i = 1; i < n; i++) {
611	rcu_assign_pointer(slot[i], child);
612	node->count++;
613	}
614	}
615	#endif
616
617	if (nodep)
618	*nodep = node;
619	if (slotp)
620	*slotp = slot;
621	return 0;
622	}
623
624	/**
625	* __radix_tree_insert - insert into a radix tree
626	* @root: radix tree root
627	* @index: index key
628	* @order: key covers the 2^order indices around index
629	* @item: item to insert
630	*
631	* Insert an item into the radix tree at position @index.
632	*/
633	int __radix_tree_insert(struct radix_tree_root *root, unsigned long index,
634	unsigned order, void *item)
635	{
636	struct radix_tree_node *node;
637	void **slot;
638	int error;
639
640	BUG_ON(radix_tree_is_internal_node(item));
641
642	error = __radix_tree_create(root, index, order, &node, &slot);
643	if (error)
644	return error;
645	if (*slot != NULL)
646	return -EEXIST;
647	rcu_assign_pointer(*slot, item);
648
649	if (node) {
650	unsigned offset = get_slot_offset(node, slot);
651	node->count++;
652	BUG_ON(tag_get(node, 0, offset));
653	BUG_ON(tag_get(node, 1, offset));
654	BUG_ON(tag_get(node, 2, offset));
655	} else {
656	BUG_ON(root_tags_get(root));
657	}
658
659	return 0;
660	}
661	EXPORT_SYMBOL(__radix_tree_insert);
662
663	/**
664	* __radix_tree_lookup - lookup an item in a radix tree
665	* @root: radix tree root
666	* @index: index key
667	* @nodep: returns node
668	* @slotp: returns slot
669	*
670	* Lookup and return the item at position @index in the radix
671	* tree @root.
672	*
673	* Until there is more than one item in the tree, no nodes are
674	* allocated and @root->rnode is used as a direct slot instead of
675	* pointing to a node, in which case *@nodep will be NULL.
676	*/
677	void *__radix_tree_lookup(struct radix_tree_root *root, unsigned long index,
678	struct radix_tree_node **nodep, void ***slotp)
679	{
680	struct radix_tree_node *node, *parent;
681	unsigned long maxindex;
682	void **slot;
683
684	restart:
685	parent = NULL;
686	slot = (void **)&root->rnode;
687	radix_tree_load_root(root, &node, &maxindex);
688	if (index > maxindex)
689	return NULL;
690
691	while (radix_tree_is_internal_node(node)) {
692	unsigned offset;
693
694	if (node == RADIX_TREE_RETRY)
695	goto restart;
696	parent = entry_to_node(node);
697	offset = radix_tree_descend(parent, &node, index);
698	slot = parent->slots + offset;
699	}
700
701	if (nodep)
702	*nodep = parent;
703	if (slotp)
704	*slotp = slot;
705	return node;
706	}
707
708	/**
709	* radix_tree_lookup_slot - lookup a slot in a radix tree
710	* @root: radix tree root
711	* @index: index key
712	*
713	* Returns: the slot corresponding to the position @index in the
714	* radix tree @root. This is useful for update-if-exists operations.
715	*
716	* This function can be called under rcu_read_lock iff the slot is not
717	* modified by radix_tree_replace_slot, otherwise it must be called
718	* exclusive from other writers. Any dereference of the slot must be done
719	* using radix_tree_deref_slot.
720	*/
721	void **radix_tree_lookup_slot(struct radix_tree_root *root, unsigned long index)
722	{
723	void **slot;
724
725	if (!__radix_tree_lookup(root, index, NULL, &slot))
726	return NULL;
727	return slot;
728	}
729	EXPORT_SYMBOL(radix_tree_lookup_slot);
730
731	/**
732	* radix_tree_lookup - perform lookup operation on a radix tree
733	* @root: radix tree root
734	* @index: index key
735	*
736	* Lookup the item at the position @index in the radix tree @root.
737	*
738	* This function can be called under rcu_read_lock, however the caller
739	* must manage lifetimes of leaf nodes (eg. RCU may also be used to free
740	* them safely). No RCU barriers are required to access or modify the
741	* returned item, however.
742	*/
743	void *radix_tree_lookup(struct radix_tree_root *root, unsigned long index)
744	{
745	return __radix_tree_lookup(root, index, NULL, NULL);
746	}
747	EXPORT_SYMBOL(radix_tree_lookup);
748
749	/**
750	* radix_tree_tag_set - set a tag on a radix tree node
751	* @root: radix tree root
752	* @index: index key
753	* @tag: tag index
754	*
755	* Set the search tag (which must be < RADIX_TREE_MAX_TAGS)
756	* corresponding to @index in the radix tree. From
757	* the root all the way down to the leaf node.
758	*
759	* Returns the address of the tagged item. Setting a tag on a not-present
760	* item is a bug.
761	*/
762	void *radix_tree_tag_set(struct radix_tree_root *root,
763	unsigned long index, unsigned int tag)
764	{
765	struct radix_tree_node *node, *parent;
766	unsigned long maxindex;
767
768	radix_tree_load_root(root, &node, &maxindex);
769	BUG_ON(index > maxindex);
770
771	while (radix_tree_is_internal_node(node)) {
772	unsigned offset;
773
774	parent = entry_to_node(node);
775	offset = radix_tree_descend(parent, &node, index);
776	BUG_ON(!node);
777
778	if (!tag_get(parent, tag, offset))
779	tag_set(parent, tag, offset);
780	}
781
782	/* set the root's tag bit */
783	if (!root_tag_get(root, tag))
784	root_tag_set(root, tag);
785
786	return node;
787	}
788	EXPORT_SYMBOL(radix_tree_tag_set);
789
790	static void node_tag_clear(struct radix_tree_root *root,
791	struct radix_tree_node *node,
792	unsigned int tag, unsigned int offset)
793	{
794	while (node) {
795	if (!tag_get(node, tag, offset))
796	return;
797	tag_clear(node, tag, offset);
798	if (any_tag_set(node, tag))
799	return;
800
801	offset = node->offset;
802	node = node->parent;
803	}
804
805	/* clear the root's tag bit */
806	if (root_tag_get(root, tag))
807	root_tag_clear(root, tag);
808	}
809
810	/**
811	* radix_tree_tag_clear - clear a tag on a radix tree node
812	* @root: radix tree root
813	* @index: index key
814	* @tag: tag index
815	*
816	* Clear the search tag (which must be < RADIX_TREE_MAX_TAGS)
817	* corresponding to @index in the radix tree. If this causes
818	* the leaf node to have no tags set then clear the tag in the
819	* next-to-leaf node, etc.
820	*
821	* Returns the address of the tagged item on success, else NULL. ie:
822	* has the same return value and semantics as radix_tree_lookup().
823	*/
824	void *radix_tree_tag_clear(struct radix_tree_root *root,
825	unsigned long index, unsigned int tag)
826	{
827	struct radix_tree_node *node, *parent;
828	unsigned long maxindex;
829	int uninitialized_var(offset);
830
831	radix_tree_load_root(root, &node, &maxindex);
832	if (index > maxindex)
833	return NULL;
834
835	parent = NULL;
836
837	while (radix_tree_is_internal_node(node)) {
838	parent = entry_to_node(node);
839	offset = radix_tree_descend(parent, &node, index);
840	}
841
842	if (node)
843	node_tag_clear(root, parent, tag, offset);
844
845	return node;
846	}
847	EXPORT_SYMBOL(radix_tree_tag_clear);
848
849	/**
850	* radix_tree_tag_get - get a tag on a radix tree node
851	* @root: radix tree root
852	* @index: index key
853	* @tag: tag index (< RADIX_TREE_MAX_TAGS)
854	*
855	* Return values:
856	*
857	* 0: tag not present or not set
858	* 1: tag set
859	*
860	* Note that the return value of this function may not be relied on, even if
861	* the RCU lock is held, unless tag modification and node deletion are excluded
862	* from concurrency.
863	*/
864	int radix_tree_tag_get(struct radix_tree_root *root,
865	unsigned long index, unsigned int tag)
866	{
867	struct radix_tree_node *node, *parent;
868	unsigned long maxindex;
869
870	if (!root_tag_get(root, tag))
871	return 0;
872
873	radix_tree_load_root(root, &node, &maxindex);
874	if (index > maxindex)
875	return 0;
876	if (node == NULL)
877	return 0;
878
879	while (radix_tree_is_internal_node(node)) {
880	unsigned offset;
881
882	parent = entry_to_node(node);
883	offset = radix_tree_descend(parent, &node, index);
884
885	if (!node)
886	return 0;
887	if (!tag_get(parent, tag, offset))
888	return 0;
889	if (node == RADIX_TREE_RETRY)
890	break;
891	}
892
893	return 1;
894	}
895	EXPORT_SYMBOL(radix_tree_tag_get);
896
897	static inline void __set_iter_shift(struct radix_tree_iter *iter,
898	unsigned int shift)
899	{
900	#ifdef CONFIG_RADIX_TREE_MULTIORDER
901	iter->shift = shift;
902	#endif
903	}
904
905	/**
906	* radix_tree_next_chunk - find next chunk of slots for iteration
907	*
908	* @root: radix tree root
909	* @iter: iterator state
910	* @flags: RADIX_TREE_ITER_* flags and tag index
911	* Returns: pointer to chunk first slot, or NULL if iteration is over
912	*/
913	void **radix_tree_next_chunk(struct radix_tree_root *root,
914	struct radix_tree_iter *iter, unsigned flags)
915	{
916	unsigned tag = flags & RADIX_TREE_ITER_TAG_MASK;
917	struct radix_tree_node *node, *child;
918	unsigned long index, offset, maxindex;
919
920	if ((flags & RADIX_TREE_ITER_TAGGED) && !root_tag_get(root, tag))
921	return NULL;
922
923	/*
924	* Catch next_index overflow after ~0UL. iter->index never overflows
925	* during iterating; it can be zero only at the beginning.
926	* And we cannot overflow iter->next_index in a single step,
927	* because RADIX_TREE_MAP_SHIFT < BITS_PER_LONG.
928	*
929	* This condition also used by radix_tree_next_slot() to stop
930	* contiguous iterating, and forbid swithing to the next chunk.
931	*/
932	index = iter->next_index;
933	if (!index && iter->index)
934	return NULL;
935
936	restart:
937	radix_tree_load_root(root, &child, &maxindex);
938	if (index > maxindex)
939	return NULL;
940	if (!child)
941	return NULL;
942
943	if (!radix_tree_is_internal_node(child)) {
944	/* Single-slot tree */
945	iter->index = index;
946	iter->next_index = maxindex + 1;
947	iter->tags = 1;
948	__set_iter_shift(iter, 0);
949	return (void **)&root->rnode;
950	}
951
952	do {
953	node = entry_to_node(child);
954	offset = radix_tree_descend(node, &child, index);
955
956	if ((flags & RADIX_TREE_ITER_TAGGED) ?
957	!tag_get(node, tag, offset) : !child) {
958	/* Hole detected */
959	if (flags & RADIX_TREE_ITER_CONTIG)
960	return NULL;
961
962	if (flags & RADIX_TREE_ITER_TAGGED)
963	offset = radix_tree_find_next_bit(
964	node->tags[tag],
965	RADIX_TREE_MAP_SIZE,
966	offset + 1);
967	else
968	while (++offset < RADIX_TREE_MAP_SIZE) {
969	void *slot = node->slots[offset];
970	if (is_sibling_entry(node, slot))
971	continue;
972	if (slot)
973	break;
974	}
975	index &= ~node_maxindex(node);
976	index += offset << node->shift;
977	/* Overflow after ~0UL */
978	if (!index)
979	return NULL;
980	if (offset == RADIX_TREE_MAP_SIZE)
981	goto restart;
982	child = rcu_dereference_raw(node->slots[offset]);
983	}
984
985	if ((child == NULL) || (child == RADIX_TREE_RETRY))
986	goto restart;
987	} while (radix_tree_is_internal_node(child));
988
989	/* Update the iterator state */
990	iter->index = (index &~ node_maxindex(node)) | (offset << node->shift);
991	iter->next_index = (index | node_maxindex(node)) + 1;
992	__set_iter_shift(iter, node->shift);
993
994	/* Construct iter->tags bit-mask from node->tags[tag] array */
995	if (flags & RADIX_TREE_ITER_TAGGED) {
996	unsigned tag_long, tag_bit;
997
998	tag_long = offset / BITS_PER_LONG;
999	tag_bit = offset % BITS_PER_LONG;
1000	iter->tags = node->tags[tag][tag_long] >> tag_bit;
1001	/* This never happens if RADIX_TREE_TAG_LONGS == 1 */
1002	if (tag_long < RADIX_TREE_TAG_LONGS - 1) {
1003	/* Pick tags from next element */
1004	if (tag_bit)
1005	iter->tags |= node->tags[tag][tag_long + 1] <<
1006	(BITS_PER_LONG - tag_bit);
1007	/* Clip chunk size, here only BITS_PER_LONG tags */
1008	iter->next_index = index + BITS_PER_LONG;
1009	}
1010	}
1011
1012	return node->slots + offset;
1013	}
1014	EXPORT_SYMBOL(radix_tree_next_chunk);
1015
1016	/**
1017	* radix_tree_range_tag_if_tagged - for each item in given range set given
1018	* tag if item has another tag set
1019	* @root: radix tree root
1020	* @first_indexp: pointer to a starting index of a range to scan
1021	* @last_index: last index of a range to scan
1022	* @nr_to_tag: maximum number items to tag
1023	* @iftag: tag index to test
1024	* @settag: tag index to set if tested tag is set
1025	*
1026	* This function scans range of radix tree from first_index to last_index
1027	* (inclusive). For each item in the range if iftag is set, the function sets
1028	* also settag. The function stops either after tagging nr_to_tag items or
1029	* after reaching last_index.
1030	*
1031	* The tags must be set from the leaf level only and propagated back up the
1032	* path to the root. We must do this so that we resolve the full path before
1033	* setting any tags on intermediate nodes. If we set tags as we descend, then
1034	* we can get to the leaf node and find that the index that has the iftag
1035	* set is outside the range we are scanning. This reults in dangling tags and
1036	* can lead to problems with later tag operations (e.g. livelocks on lookups).
1037	*
1038	* The function returns the number of leaves where the tag was set and sets
1039	* *first_indexp to the first unscanned index.
1040	* WARNING! *first_indexp can wrap if last_index is ULONG_MAX. Caller must
1041	* be prepared to handle that.
1042	*/
1043	unsigned long radix_tree_range_tag_if_tagged(struct radix_tree_root *root,
1044	unsigned long *first_indexp, unsigned long last_index,
1045	unsigned long nr_to_tag,
1046	unsigned int iftag, unsigned int settag)
1047	{
1048	struct radix_tree_node *parent, *node, *child;
1049	unsigned long maxindex;
1050	unsigned long tagged = 0;
1051	unsigned long index = *first_indexp;
1052
1053	radix_tree_load_root(root, &child, &maxindex);
1054	last_index = min(last_index, maxindex);
1055	if (index > last_index)
1056	return 0;
1057	if (!nr_to_tag)
1058	return 0;
1059	if (!root_tag_get(root, iftag)) {
1060	*first_indexp = last_index + 1;
1061	return 0;
1062	}
1063	if (!radix_tree_is_internal_node(child)) {
1064	*first_indexp = last_index + 1;
1065	root_tag_set(root, settag);
1066	return 1;
1067	}
1068
1069	node = entry_to_node(child);
1070
1071	for (;;) {
1072	unsigned offset = radix_tree_descend(node, &child, index);
1073	if (!child)
1074	goto next;
1075	if (!tag_get(node, iftag, offset))
1076	goto next;
1077	/* Sibling slots never have tags set on them */
1078	if (radix_tree_is_internal_node(child)) {
1079	node = entry_to_node(child);
1080	continue;
1081	}
1082
1083	/* tag the leaf */
1084	tagged++;
1085	tag_set(node, settag, offset);
1086
1087	/* walk back up the path tagging interior nodes */
1088	parent = node;
1089	for (;;) {
1090	offset = parent->offset;
1091	parent = parent->parent;
1092	if (!parent)
1093	break;
1094	/* stop if we find a node with the tag already set */
1095	if (tag_get(parent, settag, offset))
1096	break;
1097	tag_set(parent, settag, offset);
1098	}
1099	next:
1100	/* Go to next entry in node */
1101	index = ((index >> node->shift) + 1) << node->shift;
1102	/* Overflow can happen when last_index is ~0UL... */
1103	if (index > last_index || !index)
1104	break;
1105	offset = (index >> node->shift) & RADIX_TREE_MAP_MASK;
1106	while (offset == 0) {
1107	/*
1108	* We've fully scanned this node. Go up. Because
1109	* last_index is guaranteed to be in the tree, what
1110	* we do below cannot wander astray.
1111	*/
1112	node = node->parent;
1113	offset = (index >> node->shift) & RADIX_TREE_MAP_MASK;
1114	}
1115	if (is_sibling_entry(node, node->slots[offset]))
1116	goto next;
1117	if (tagged >= nr_to_tag)
1118	break;
1119	}
1120	/*
1121	* We need not to tag the root tag if there is no tag which is set with
1122	* settag within the range from *first_indexp to last_index.
1123	*/
1124	if (tagged > 0)
1125	root_tag_set(root, settag);
1126	*first_indexp = index;
1127
1128	return tagged;
1129	}
1130	EXPORT_SYMBOL(radix_tree_range_tag_if_tagged);
1131
1132	/**
1133	* radix_tree_gang_lookup - perform multiple lookup on a radix tree
1134	* @root: radix tree root
1135	* @results: where the results of the lookup are placed
1136	* @first_index: start the lookup from this key
1137	* @max_items: place up to this many items at *results
1138	*
1139	* Performs an index-ascending scan of the tree for present items. Places
1140	* them at *@results and returns the number of items which were placed at
1141	* *@results.
1142	*
1143	* The implementation is naive.
1144	*
1145	* Like radix_tree_lookup, radix_tree_gang_lookup may be called under
1146	* rcu_read_lock. In this case, rather than the returned results being
1147	* an atomic snapshot of the tree at a single point in time, the
1148	* semantics of an RCU protected gang lookup are as though multiple
1149	* radix_tree_lookups have been issued in individual locks, and results
1150	* stored in 'results'.
1151	*/
1152	unsigned int
1153	radix_tree_gang_lookup(struct radix_tree_root *root, void **results,
1154	unsigned long first_index, unsigned int max_items)
1155	{
1156	struct radix_tree_iter iter;
1157	void **slot;
1158	unsigned int ret = 0;
1159
1160	if (unlikely(!max_items))
1161	return 0;
1162
1163	radix_tree_for_each_slot(slot, root, &iter, first_index) {
1164	results[ret] = rcu_dereference_raw(*slot);
1165	if (!results[ret])
1166	continue;
1167	if (radix_tree_is_internal_node(results[ret])) {
1168	slot = radix_tree_iter_retry(&iter);
1169	continue;
1170	}
1171	if (++ret == max_items)
1172	break;
1173	}
1174
1175	return ret;
1176	}
1177	EXPORT_SYMBOL(radix_tree_gang_lookup);
1178
1179	/**
1180	* radix_tree_gang_lookup_slot - perform multiple slot lookup on radix tree
1181	* @root: radix tree root
1182	* @results: where the results of the lookup are placed
1183	* @indices: where their indices should be placed (but usually NULL)
1184	* @first_index: start the lookup from this key
1185	* @max_items: place up to this many items at *results
1186	*
1187	* Performs an index-ascending scan of the tree for present items. Places
1188	* their slots at *@results and returns the number of items which were
1189	* placed at *@results.
1190	*
1191	* The implementation is naive.
1192	*
1193	* Like radix_tree_gang_lookup as far as RCU and locking goes. Slots must
1194	* be dereferenced with radix_tree_deref_slot, and if using only RCU
1195	* protection, radix_tree_deref_slot may fail requiring a retry.
1196	*/
1197	unsigned int
1198	radix_tree_gang_lookup_slot(struct radix_tree_root *root,
1199	void ***results, unsigned long *indices,
1200	unsigned long first_index, unsigned int max_items)
1201	{
1202	struct radix_tree_iter iter;
1203	void **slot;
1204	unsigned int ret = 0;
1205
1206	if (unlikely(!max_items))
1207	return 0;
1208
1209	radix_tree_for_each_slot(slot, root, &iter, first_index) {
1210	results[ret] = slot;
1211	if (indices)
1212	indices[ret] = iter.index;
1213	if (++ret == max_items)
1214	break;
1215	}
1216
1217	return ret;
1218	}
1219	EXPORT_SYMBOL(radix_tree_gang_lookup_slot);
1220
1221	/**
1222	* radix_tree_gang_lookup_tag - perform multiple lookup on a radix tree
1223	* based on a tag
1224	* @root: radix tree root
1225	* @results: where the results of the lookup are placed
1226	* @first_index: start the lookup from this key
1227	* @max_items: place up to this many items at *results
1228	* @tag: the tag index (< RADIX_TREE_MAX_TAGS)
1229	*
1230	* Performs an index-ascending scan of the tree for present items which
1231	* have the tag indexed by @tag set. Places the items at *@results and
1232	* returns the number of items which were placed at *@results.
1233	*/
1234	unsigned int
1235	radix_tree_gang_lookup_tag(struct radix_tree_root *root, void **results,
1236	unsigned long first_index, unsigned int max_items,
1237	unsigned int tag)
1238	{
1239	struct radix_tree_iter iter;
1240	void **slot;
1241	unsigned int ret = 0;
1242
1243	if (unlikely(!max_items))
1244	return 0;
1245
1246	radix_tree_for_each_tagged(slot, root, &iter, first_index, tag) {
1247	results[ret] = rcu_dereference_raw(*slot);
1248	if (!results[ret])
1249	continue;
1250	if (radix_tree_is_internal_node(results[ret])) {
1251	slot = radix_tree_iter_retry(&iter);
1252	continue;
1253	}
1254	if (++ret == max_items)
1255	break;
1256	}
1257
1258	return ret;
1259	}
1260	EXPORT_SYMBOL(radix_tree_gang_lookup_tag);
1261
1262	/**
1263	* radix_tree_gang_lookup_tag_slot - perform multiple slot lookup on a
1264	* radix tree based on a tag
1265	* @root: radix tree root
1266	* @results: where the results of the lookup are placed
1267	* @first_index: start the lookup from this key
1268	* @max_items: place up to this many items at *results
1269	* @tag: the tag index (< RADIX_TREE_MAX_TAGS)
1270	*
1271	* Performs an index-ascending scan of the tree for present items which
1272	* have the tag indexed by @tag set. Places the slots at *@results and
1273	* returns the number of slots which were placed at *@results.
1274	*/
1275	unsigned int
1276	radix_tree_gang_lookup_tag_slot(struct radix_tree_root *root, void ***results,
1277	unsigned long first_index, unsigned int max_items,
1278	unsigned int tag)
1279	{
1280	struct radix_tree_iter iter;
1281	void **slot;
1282	unsigned int ret = 0;
1283
1284	if (unlikely(!max_items))
1285	return 0;
1286
1287	radix_tree_for_each_tagged(slot, root, &iter, first_index, tag) {
1288	results[ret] = slot;
1289	if (++ret == max_items)
1290	break;
1291	}
1292
1293	return ret;
1294	}
1295	EXPORT_SYMBOL(radix_tree_gang_lookup_tag_slot);
1296
1297	#if defined(CONFIG_SHMEM) && defined(CONFIG_SWAP)
1298	#include <linux/sched.h> /* for cond_resched() */
1299
1300	struct locate_info {
1301	unsigned long found_index;
1302	bool stop;
1303	};
1304
1305	/*
1306	* This linear search is at present only useful to shmem_unuse_inode().
1307	*/
1308	static unsigned long __locate(struct radix_tree_node *slot, void *item,
1309	unsigned long index, struct locate_info *info)
1310	{
1311	unsigned long i;
1312
1313	do {
1314	unsigned int shift = slot->shift;
1315
1316	for (i = (index >> shift) & RADIX_TREE_MAP_MASK;
1317	i < RADIX_TREE_MAP_SIZE;
1318	i++, index += (1UL << shift)) {
1319	struct radix_tree_node *node =
1320	rcu_dereference_raw(slot->slots[i]);
1321	if (node == RADIX_TREE_RETRY)
1322	goto out;
1323	if (!radix_tree_is_internal_node(node)) {
1324	if (node == item) {
1325	info->found_index = index;
1326	info->stop = true;
1327	goto out;
1328	}
1329	continue;
1330	}
1331	node = entry_to_node(node);
1332	if (is_sibling_entry(slot, node))
1333	continue;
1334	slot = node;
1335	break;
1336	}
1337	} while (i < RADIX_TREE_MAP_SIZE);
1338
1339	out:
1340	if ((index == 0) && (i == RADIX_TREE_MAP_SIZE))
1341	info->stop = true;
1342	return index;
1343	}
1344
1345	/**
1346	* radix_tree_locate_item - search through radix tree for item
1347	* @root: radix tree root
1348	* @item: item to be found
1349	*
1350	* Returns index where item was found, or -1 if not found.
1351	* Caller must hold no lock (since this time-consuming function needs
1352	* to be preemptible), and must check afterwards if item is still there.
1353	*/
1354	unsigned long radix_tree_locate_item(struct radix_tree_root *root, void *item)
1355	{
1356	struct radix_tree_node *node;
1357	unsigned long max_index;
1358	unsigned long cur_index = 0;
1359	struct locate_info info = {
1360	.found_index = -1,
1361	.stop = false,
1362	};
1363
1364	do {
1365	rcu_read_lock();
1366	node = rcu_dereference_raw(root->rnode);
1367	if (!radix_tree_is_internal_node(node)) {
1368	rcu_read_unlock();
1369	if (node == item)
1370	info.found_index = 0;
1371	break;
1372	}
1373
1374	node = entry_to_node(node);
1375
1376	max_index = node_maxindex(node);
1377	if (cur_index > max_index) {
1378	rcu_read_unlock();
1379	break;
1380	}
1381
1382	cur_index = __locate(node, item, cur_index, &info);
1383	rcu_read_unlock();
1384	cond_resched();
1385	} while (!info.stop && cur_index <= max_index);
1386
1387	return info.found_index;
1388	}
1389	#else
1390	unsigned long radix_tree_locate_item(struct radix_tree_root *root, void *item)
1391	{
1392	return -1;
1393	}
1394	#endif /* CONFIG_SHMEM && CONFIG_SWAP */
1395
1396	/**
1397	* radix_tree_shrink - shrink radix tree to minimum height
1398	* @root radix tree root
1399	*/
1400	static inline bool radix_tree_shrink(struct radix_tree_root *root)
1401	{
1402	bool shrunk = false;
1403
1404	for (;;) {
1405	struct radix_tree_node *node = root->rnode;
1406	struct radix_tree_node *child;
1407
1408	if (!radix_tree_is_internal_node(node))
1409	break;
1410	node = entry_to_node(node);
1411
1412	/*
1413	* The candidate node has more than one child, or its child
1414	* is not at the leftmost slot, or the child is a multiorder
1415	* entry, we cannot shrink.
1416	*/
1417	if (node->count != 1)
1418	break;
1419	child = node->slots[0];
1420	if (!child)
1421	break;
1422	if (!radix_tree_is_internal_node(child) && node->shift)
1423	break;
1424
1425	if (radix_tree_is_internal_node(child))
1426	entry_to_node(child)->parent = NULL;
1427
1428	/*
1429	* We don't need rcu_assign_pointer(), since we are simply
1430	* moving the node from one part of the tree to another: if it
1431	* was safe to dereference the old pointer to it
1432	* (node->slots[0]), it will be safe to dereference the new
1433	* one (root->rnode) as far as dependent read barriers go.
1434	*/
1435	root->rnode = child;
1436
1437	/*
1438	* We have a dilemma here. The node's slot[0] must not be
1439	* NULLed in case there are concurrent lookups expecting to
1440	* find the item. However if this was a bottom-level node,
1441	* then it may be subject to the slot pointer being visible
1442	* to callers dereferencing it. If item corresponding to
1443	* slot[0] is subsequently deleted, these callers would expect
1444	* their slot to become empty sooner or later.
1445	*
1446	* For example, lockless pagecache will look up a slot, deref
1447	* the page pointer, and if the page has 0 refcount it means it
1448	* was concurrently deleted from pagecache so try the deref
1449	* again. Fortunately there is already a requirement for logic
1450	* to retry the entire slot lookup -- the indirect pointer
1451	* problem (replacing direct root node with an indirect pointer
1452	* also results in a stale slot). So tag the slot as indirect
1453	* to force callers to retry.
1454	*/
1455	if (!radix_tree_is_internal_node(child))
1456	node->slots[0] = RADIX_TREE_RETRY;
1457
1458	radix_tree_node_free(node);
1459	shrunk = true;
1460	}
1461
1462	return shrunk;
1463	}
1464
1465	/**
1466	* __radix_tree_delete_node - try to free node after clearing a slot
1467	* @root: radix tree root
1468	* @node: node containing @index
1469	*
1470	* After clearing the slot at @index in @node from radix tree
1471	* rooted at @root, call this function to attempt freeing the
1472	* node and shrinking the tree.
1473	*
1474	* Returns %true if @node was freed, %false otherwise.
1475	*/
1476	bool __radix_tree_delete_node(struct radix_tree_root *root,
1477	struct radix_tree_node *node)
1478	{
1479	bool deleted = false;
1480
1481	do {
1482	struct radix_tree_node *parent;
1483
1484	if (node->count) {
1485	if (node == entry_to_node(root->rnode))
1486	deleted |= radix_tree_shrink(root);
1487	return deleted;
1488	}
1489
1490	parent = node->parent;
1491	if (parent) {
1492	parent->slots[node->offset] = NULL;
1493	parent->count--;
1494	} else {
1495	root_tag_clear_all(root);
1496	root->rnode = NULL;
1497	}
1498
1499	radix_tree_node_free(node);
1500	deleted = true;
1501
1502	node = parent;
1503	} while (node);
1504
1505	return deleted;
1506	}
1507
1508	static inline void delete_sibling_entries(struct radix_tree_node *node,
1509	void *ptr, unsigned offset)
1510	{
1511	#ifdef CONFIG_RADIX_TREE_MULTIORDER
1512	int i;
1513	for (i = 1; offset + i < RADIX_TREE_MAP_SIZE; i++) {
1514	if (node->slots[offset + i] != ptr)
1515	break;
1516	node->slots[offset + i] = NULL;
1517	node->count--;
1518	}
1519	#endif
1520	}
1521
1522	/**
1523	* radix_tree_delete_item - delete an item from a radix tree
1524	* @root: radix tree root
1525	* @index: index key
1526	* @item: expected item
1527	*
1528	* Remove @item at @index from the radix tree rooted at @root.
1529	*
1530	* Returns the address of the deleted item, or NULL if it was not present
1531	* or the entry at the given @index was not @item.
1532	*/
1533	void *radix_tree_delete_item(struct radix_tree_root *root,
1534	unsigned long index, void *item)
1535	{
1536	struct radix_tree_node *node;
1537	unsigned int offset;
1538	void **slot;
1539	void *entry;
1540	int tag;
1541
1542	entry = __radix_tree_lookup(root, index, &node, &slot);
1543	if (!entry)
1544	return NULL;
1545
1546	if (item && entry != item)
1547	return NULL;
1548
1549	if (!node) {
1550	root_tag_clear_all(root);
1551	root->rnode = NULL;
1552	return entry;
1553	}
1554
1555	offset = get_slot_offset(node, slot);
1556
1557	/* Clear all tags associated with the item to be deleted. */
1558	for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++)
1559	node_tag_clear(root, node, tag, offset);
1560
1561	delete_sibling_entries(node, node_to_entry(slot), offset);
1562	node->slots[offset] = NULL;
1563	node->count--;
1564
1565	__radix_tree_delete_node(root, node);
1566
1567	return entry;
1568	}
1569	EXPORT_SYMBOL(radix_tree_delete_item);
1570
1571	/**
1572	* radix_tree_delete - delete an item from a radix tree
1573	* @root: radix tree root
1574	* @index: index key
1575	*
1576	* Remove the item at @index from the radix tree rooted at @root.
1577	*
1578	* Returns the address of the deleted item, or NULL if it was not present.
1579	*/
1580	void *radix_tree_delete(struct radix_tree_root *root, unsigned long index)
1581	{
1582	return radix_tree_delete_item(root, index, NULL);
1583	}
1584	EXPORT_SYMBOL(radix_tree_delete);
1585
1586	void radix_tree_clear_tags(struct radix_tree_root *root,
1587	struct radix_tree_node *node,
1588	void **slot)
1589	{
1590	if (node) {
1591	unsigned int tag, offset = get_slot_offset(node, slot);
1592	for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++)
1593	node_tag_clear(root, node, tag, offset);
1594	} else {
1595	/* Clear root node tags */
1596	root->gfp_mask &= __GFP_BITS_MASK;
1597	}
1598	}
1599
1600	/**
1601	* radix_tree_tagged - test whether any items in the tree are tagged
1602	* @root: radix tree root
1603	* @tag: tag to test
1604	*/
1605	int radix_tree_tagged(struct radix_tree_root *root, unsigned int tag)
1606	{
1607	return root_tag_get(root, tag);
1608	}
1609	EXPORT_SYMBOL(radix_tree_tagged);
1610
1611	static void
1612	radix_tree_node_ctor(void *arg)
1613	{
1614	struct radix_tree_node *node = arg;
1615
1616	memset(node, 0, sizeof(*node));
1617	INIT_LIST_HEAD(&node->private_list);
1618	}
1619
1620	static __init unsigned long __maxindex(unsigned int height)
1621	{
1622	unsigned int width = height * RADIX_TREE_MAP_SHIFT;
1623	int shift = RADIX_TREE_INDEX_BITS - width;
1624
1625	if (shift < 0)
1626	return ~0UL;
1627	if (shift >= BITS_PER_LONG)
1628	return 0UL;
1629	return ~0UL >> shift;
1630	}
1631
1632	static __init void radix_tree_init_maxnodes(void)
1633	{
1634	unsigned long height_to_maxindex[RADIX_TREE_MAX_PATH + 1];
1635	unsigned int i, j;
1636
1637	for (i = 0; i < ARRAY_SIZE(height_to_maxindex); i++)
1638	height_to_maxindex[i] = __maxindex(i);
1639	for (i = 0; i < ARRAY_SIZE(height_to_maxnodes); i++) {
1640	for (j = i; j > 0; j--)
1641	height_to_maxnodes[i] += height_to_maxindex[j - 1] + 1;
1642	}
1643	}
1644
1645	static int radix_tree_callback(struct notifier_block *nfb,
1646	unsigned long action, void *hcpu)
1647	{
1648	int cpu = (long)hcpu;
1649	struct radix_tree_preload *rtp;
1650	struct radix_tree_node *node;
1651
1652	/* Free per-cpu pool of preloaded nodes */
1653	if (action == CPU_DEAD || action == CPU_DEAD_FROZEN) {
1654	rtp = &per_cpu(radix_tree_preloads, cpu);
1655	while (rtp->nr) {
1656	node = rtp->nodes;
1657	rtp->nodes = node->private_data;
1658	kmem_cache_free(radix_tree_node_cachep, node);
1659	rtp->nr--;
1660	}
1661	}
1662	return NOTIFY_OK;
1663	}
1664
1665	void __init radix_tree_init(void)
1666	{
1667	radix_tree_node_cachep = kmem_cache_create("radix_tree_node",
1668	sizeof(struct radix_tree_node), 0,
1669	SLAB_PANIC | SLAB_RECLAIM_ACCOUNT,
1670	radix_tree_node_ctor);
1671	radix_tree_init_maxnodes();
1672	hotcpu_notifier(radix_tree_callback, 0);
1673	}
1674