1de6cc651SThomas Gleixner /* SPDX-License-Identifier: GPL-2.0-or-later */
21da177e4SLinus Torvalds /*
31da177e4SLinus Torvalds * Copyright (C) 2001 Momchil Velikov
41da177e4SLinus Torvalds * Portions Copyright (C) 2001 Christoph Hellwig
57cf9c2c7SNick Piggin * Copyright (C) 2006 Nick Piggin
678c1d784SKonstantin Khlebnikov * Copyright (C) 2012 Konstantin Khlebnikov
71da177e4SLinus Torvalds */
81da177e4SLinus Torvalds #ifndef _LINUX_RADIX_TREE_H
91da177e4SLinus Torvalds #define _LINUX_RADIX_TREE_H
101da177e4SLinus Torvalds
11f67c07f0SMatthew Wilcox #include <linux/bitops.h>
12*9f162193SYury Norov #include <linux/gfp_types.h>
1315f2e88dSMatthew Wilcox #include <linux/list.h>
1498e1385eSAndy Shevchenko #include <linux/lockdep.h>
1598e1385eSAndy Shevchenko #include <linux/math.h>
16dd841a74SMatthew Wilcox (Oracle) #include <linux/percpu.h>
1715f2e88dSMatthew Wilcox #include <linux/preempt.h>
187cf9c2c7SNick Piggin #include <linux/rcupdate.h>
1915f2e88dSMatthew Wilcox #include <linux/spinlock.h>
2015f2e88dSMatthew Wilcox #include <linux/types.h>
213159f943SMatthew Wilcox #include <linux/xarray.h>
22cfa6705dSSebastian Andrzej Siewior #include <linux/local_lock.h>
237cf9c2c7SNick Piggin
24f8d5d0ccSMatthew Wilcox /* Keep unconverted code working */
25f8d5d0ccSMatthew Wilcox #define radix_tree_root xarray
2601959dfeSMatthew Wilcox #define radix_tree_node xa_node
27f8d5d0ccSMatthew Wilcox
28cfa6705dSSebastian Andrzej Siewior struct radix_tree_preload {
29cfa6705dSSebastian Andrzej Siewior local_lock_t lock;
30cfa6705dSSebastian Andrzej Siewior unsigned nr;
31cfa6705dSSebastian Andrzej Siewior /* nodes->parent points to next preallocated node */
32cfa6705dSSebastian Andrzej Siewior struct radix_tree_node *nodes;
33cfa6705dSSebastian Andrzej Siewior };
34cfa6705dSSebastian Andrzej Siewior DECLARE_PER_CPU(struct radix_tree_preload, radix_tree_preloads);
35cfa6705dSSebastian Andrzej Siewior
367cf9c2c7SNick Piggin /*
373bcadd6fSMatthew Wilcox * The bottom two bits of the slot determine how the remaining bits in the
383bcadd6fSMatthew Wilcox * slot are interpreted:
397cf9c2c7SNick Piggin *
403bcadd6fSMatthew Wilcox * 00 - data pointer
413159f943SMatthew Wilcox * 10 - internal entry
423159f943SMatthew Wilcox * x1 - value entry
433bcadd6fSMatthew Wilcox *
443bcadd6fSMatthew Wilcox * The internal entry may be a pointer to the next level in the tree, a
453bcadd6fSMatthew Wilcox * sibling entry, or an indicator that the entry in this slot has been moved
463bcadd6fSMatthew Wilcox * to another location in the tree and the lookup should be restarted. While
473bcadd6fSMatthew Wilcox * NULL fits the 'data pointer' pattern, it means that there is no entry in
483bcadd6fSMatthew Wilcox * the tree for this index (no matter what level of the tree it is found at).
493159f943SMatthew Wilcox * This means that storing a NULL entry in the tree is the same as deleting
503159f943SMatthew Wilcox * the entry from the tree.
517cf9c2c7SNick Piggin */
523bcadd6fSMatthew Wilcox #define RADIX_TREE_ENTRY_MASK 3UL
533159f943SMatthew Wilcox #define RADIX_TREE_INTERNAL_NODE 2UL
547cf9c2c7SNick Piggin
radix_tree_is_internal_node(void * ptr)553bcadd6fSMatthew Wilcox static inline bool radix_tree_is_internal_node(void *ptr)
567cf9c2c7SNick Piggin {
573bcadd6fSMatthew Wilcox return ((unsigned long)ptr & RADIX_TREE_ENTRY_MASK) ==
583bcadd6fSMatthew Wilcox RADIX_TREE_INTERNAL_NODE;
597cf9c2c7SNick Piggin }
607cf9c2c7SNick Piggin
617cf9c2c7SNick Piggin /*** radix-tree API starts here ***/
621da177e4SLinus Torvalds
6302c02bf1SMatthew Wilcox #define RADIX_TREE_MAP_SHIFT XA_CHUNK_SHIFT
64139e5616SJohannes Weiner #define RADIX_TREE_MAP_SIZE (1UL << RADIX_TREE_MAP_SHIFT)
65139e5616SJohannes Weiner #define RADIX_TREE_MAP_MASK (RADIX_TREE_MAP_SIZE-1)
66139e5616SJohannes Weiner
6701959dfeSMatthew Wilcox #define RADIX_TREE_MAX_TAGS XA_MAX_MARKS
6801959dfeSMatthew Wilcox #define RADIX_TREE_TAG_LONGS XA_MARK_LONGS
69139e5616SJohannes Weiner
70139e5616SJohannes Weiner #define RADIX_TREE_INDEX_BITS (8 /* CHAR_BIT */ * sizeof(unsigned long))
71139e5616SJohannes Weiner #define RADIX_TREE_MAX_PATH (DIV_ROUND_UP(RADIX_TREE_INDEX_BITS, \
72139e5616SJohannes Weiner RADIX_TREE_MAP_SHIFT))
73139e5616SJohannes Weiner
74f8d5d0ccSMatthew Wilcox /* The IDR tag is stored in the low bits of xa_flags */
75fa290cdaSMatthew Wilcox #define ROOT_IS_IDR ((__force gfp_t)4)
76f8d5d0ccSMatthew Wilcox /* The top bits of xa_flags are used to store the root tags */
77fa290cdaSMatthew Wilcox #define ROOT_TAG_SHIFT (__GFP_BITS_SHIFT)
780a835c4fSMatthew Wilcox
79f8d5d0ccSMatthew Wilcox #define RADIX_TREE_INIT(name, mask) XARRAY_INIT(name, mask)
801da177e4SLinus Torvalds
811da177e4SLinus Torvalds #define RADIX_TREE(name, mask) \
82f6bb2a2cSMatthew Wilcox struct radix_tree_root name = RADIX_TREE_INIT(name, mask)
831da177e4SLinus Torvalds
84f8d5d0ccSMatthew Wilcox #define INIT_RADIX_TREE(root, mask) xa_init_flags(root, mask)
851da177e4SLinus Torvalds
radix_tree_empty(const struct radix_tree_root * root)8635534c86SMatthew Wilcox static inline bool radix_tree_empty(const struct radix_tree_root *root)
87e9256efcSMatthew Wilcox {
88f8d5d0ccSMatthew Wilcox return root->xa_head == NULL;
89e9256efcSMatthew Wilcox }
90e9256efcSMatthew Wilcox
917cf9c2c7SNick Piggin /**
92268f42deSMatthew Wilcox * struct radix_tree_iter - radix tree iterator state
93268f42deSMatthew Wilcox *
94268f42deSMatthew Wilcox * @index: index of current slot
95268f42deSMatthew Wilcox * @next_index: one beyond the last index for this chunk
96268f42deSMatthew Wilcox * @tags: bit-mask for tag-iterating
97268f42deSMatthew Wilcox * @node: node that contains current slot
98268f42deSMatthew Wilcox *
99268f42deSMatthew Wilcox * This radix tree iterator works in terms of "chunks" of slots. A chunk is a
100268f42deSMatthew Wilcox * subinterval of slots contained within one radix tree leaf node. It is
101268f42deSMatthew Wilcox * described by a pointer to its first slot and a struct radix_tree_iter
102268f42deSMatthew Wilcox * which holds the chunk's position in the tree and its size. For tagged
103268f42deSMatthew Wilcox * iteration radix_tree_iter also holds the slots' bit-mask for one chosen
104268f42deSMatthew Wilcox * radix tree tag.
105268f42deSMatthew Wilcox */
106268f42deSMatthew Wilcox struct radix_tree_iter {
107268f42deSMatthew Wilcox unsigned long index;
108268f42deSMatthew Wilcox unsigned long next_index;
109268f42deSMatthew Wilcox unsigned long tags;
110268f42deSMatthew Wilcox struct radix_tree_node *node;
111268f42deSMatthew Wilcox };
112268f42deSMatthew Wilcox
113268f42deSMatthew Wilcox /**
1147cf9c2c7SNick Piggin * Radix-tree synchronization
1157cf9c2c7SNick Piggin *
1167cf9c2c7SNick Piggin * The radix-tree API requires that users provide all synchronisation (with
1177cf9c2c7SNick Piggin * specific exceptions, noted below).
1187cf9c2c7SNick Piggin *
1197cf9c2c7SNick Piggin * Synchronization of access to the data items being stored in the tree, and
1207cf9c2c7SNick Piggin * management of their lifetimes must be completely managed by API users.
1217cf9c2c7SNick Piggin *
1227cf9c2c7SNick Piggin * For API usage, in general,
12359c51591SMichael Opdenacker * - any function _modifying_ the tree or tags (inserting or deleting
124eb8dc5e7STim Pepper * items, setting or clearing tags) must exclude other modifications, and
1257cf9c2c7SNick Piggin * exclude any functions reading the tree.
12659c51591SMichael Opdenacker * - any function _reading_ the tree or tags (looking up items or tags,
1277cf9c2c7SNick Piggin * gang lookups) must exclude modifications to the tree, but may occur
1287cf9c2c7SNick Piggin * concurrently with other readers.
1297cf9c2c7SNick Piggin *
1307cf9c2c7SNick Piggin * The notable exceptions to this rule are the following functions:
131139e5616SJohannes Weiner * __radix_tree_lookup
1327cf9c2c7SNick Piggin * radix_tree_lookup
13347feff2cSNick Piggin * radix_tree_lookup_slot
1347cf9c2c7SNick Piggin * radix_tree_tag_get
1357cf9c2c7SNick Piggin * radix_tree_gang_lookup
1367cf9c2c7SNick Piggin * radix_tree_gang_lookup_tag
13747feff2cSNick Piggin * radix_tree_gang_lookup_tag_slot
1387cf9c2c7SNick Piggin * radix_tree_tagged
1397cf9c2c7SNick Piggin *
1407b8d046fSMatthew Wilcox * The first 7 functions are able to be called locklessly, using RCU. The
1417cf9c2c7SNick Piggin * caller must ensure calls to these functions are made within rcu_read_lock()
1427cf9c2c7SNick Piggin * regions. Other readers (lock-free or otherwise) and modifications may be
1437cf9c2c7SNick Piggin * running concurrently.
1447cf9c2c7SNick Piggin *
1457cf9c2c7SNick Piggin * It is still required that the caller manage the synchronization and lifetimes
1467cf9c2c7SNick Piggin * of the items. So if RCU lock-free lookups are used, typically this would mean
1477cf9c2c7SNick Piggin * that the items have their own locks, or are amenable to lock-free access; and
1487cf9c2c7SNick Piggin * that the items are freed by RCU (or only freed after having been deleted from
1497cf9c2c7SNick Piggin * the radix tree *and* a synchronize_rcu() grace period).
1507cf9c2c7SNick Piggin *
1517cf9c2c7SNick Piggin * (Note, rcu_assign_pointer and rcu_dereference are not needed to control
1527cf9c2c7SNick Piggin * access to data items when inserting into or looking up from the radix tree)
1537cf9c2c7SNick Piggin *
154ce82653dSDavid Howells * Note that the value returned by radix_tree_tag_get() may not be relied upon
155ce82653dSDavid Howells * if only the RCU read lock is held. Functions to set/clear tags and to
156ce82653dSDavid Howells * delete nodes running concurrently with it may affect its result such that
157ce82653dSDavid Howells * two consecutive reads in the same locked section may return different
158ce82653dSDavid Howells * values. If reliability is required, modification functions must also be
159ce82653dSDavid Howells * excluded from concurrency.
160ce82653dSDavid Howells *
1617cf9c2c7SNick Piggin * radix_tree_tagged is able to be called without locking or RCU.
1627cf9c2c7SNick Piggin */
1637cf9c2c7SNick Piggin
1647cf9c2c7SNick Piggin /**
1657cf9c2c7SNick Piggin * radix_tree_deref_slot - dereference a slot
166d7b62727SMatthew Wilcox * @slot: slot pointer, returned by radix_tree_lookup_slot
1677cf9c2c7SNick Piggin *
1687cf9c2c7SNick Piggin * For use with radix_tree_lookup_slot(). Caller must hold tree at least read
16927d20fddSNick Piggin * locked across slot lookup and dereference. Not required if write lock is
17027d20fddSNick Piggin * held (ie. items cannot be concurrently inserted).
17127d20fddSNick Piggin *
17227d20fddSNick Piggin * radix_tree_deref_retry must be used to confirm validity of the pointer if
17327d20fddSNick Piggin * only the read lock is held.
174d7b62727SMatthew Wilcox *
175d7b62727SMatthew Wilcox * Return: entry stored in that slot.
1767cf9c2c7SNick Piggin */
radix_tree_deref_slot(void __rcu ** slot)177d7b62727SMatthew Wilcox static inline void *radix_tree_deref_slot(void __rcu **slot)
1787cf9c2c7SNick Piggin {
179d7b62727SMatthew Wilcox return rcu_dereference(*slot);
1807cf9c2c7SNick Piggin }
18127d20fddSNick Piggin
18227d20fddSNick Piggin /**
183d7b62727SMatthew Wilcox * radix_tree_deref_slot_protected - dereference a slot with tree lock held
184d7b62727SMatthew Wilcox * @slot: slot pointer, returned by radix_tree_lookup_slot
18529c1f677SMel Gorman *
186d7b62727SMatthew Wilcox * Similar to radix_tree_deref_slot. The caller does not hold the RCU read
187d7b62727SMatthew Wilcox * lock but it must hold the tree lock to prevent parallel updates.
188d7b62727SMatthew Wilcox *
189d7b62727SMatthew Wilcox * Return: entry stored in that slot.
19029c1f677SMel Gorman */
radix_tree_deref_slot_protected(void __rcu ** slot,spinlock_t * treelock)191d7b62727SMatthew Wilcox static inline void *radix_tree_deref_slot_protected(void __rcu **slot,
19229c1f677SMel Gorman spinlock_t *treelock)
19329c1f677SMel Gorman {
194d7b62727SMatthew Wilcox return rcu_dereference_protected(*slot, lockdep_is_held(treelock));
19529c1f677SMel Gorman }
19629c1f677SMel Gorman
19729c1f677SMel Gorman /**
19827d20fddSNick Piggin * radix_tree_deref_retry - check radix_tree_deref_slot
19927d20fddSNick Piggin * @arg: pointer returned by radix_tree_deref_slot
20027d20fddSNick Piggin * Returns: 0 if retry is not required, otherwise retry is required
20127d20fddSNick Piggin *
20227d20fddSNick Piggin * radix_tree_deref_retry must be used with radix_tree_deref_slot.
20327d20fddSNick Piggin */
radix_tree_deref_retry(void * arg)20427d20fddSNick Piggin static inline int radix_tree_deref_retry(void *arg)
20527d20fddSNick Piggin {
206b194d16cSMatthew Wilcox return unlikely(radix_tree_is_internal_node(arg));
20727d20fddSNick Piggin }
20827d20fddSNick Piggin
2097cf9c2c7SNick Piggin /**
2106328650bSHugh Dickins * radix_tree_exception - radix_tree_deref_slot returned either exception?
2116328650bSHugh Dickins * @arg: value returned by radix_tree_deref_slot
2126328650bSHugh Dickins * Returns: 0 if well-aligned pointer, non-0 if either kind of exception.
2136328650bSHugh Dickins */
radix_tree_exception(void * arg)2146328650bSHugh Dickins static inline int radix_tree_exception(void *arg)
2156328650bSHugh Dickins {
2163bcadd6fSMatthew Wilcox return unlikely((unsigned long)arg & RADIX_TREE_ENTRY_MASK);
2176328650bSHugh Dickins }
2186328650bSHugh Dickins
2193a08cd52SMatthew Wilcox int radix_tree_insert(struct radix_tree_root *, unsigned long index,
2203a08cd52SMatthew Wilcox void *);
22135534c86SMatthew Wilcox void *__radix_tree_lookup(const struct radix_tree_root *, unsigned long index,
222d7b62727SMatthew Wilcox struct radix_tree_node **nodep, void __rcu ***slotp);
22335534c86SMatthew Wilcox void *radix_tree_lookup(const struct radix_tree_root *, unsigned long);
224d7b62727SMatthew Wilcox void __rcu **radix_tree_lookup_slot(const struct radix_tree_root *,
225d7b62727SMatthew Wilcox unsigned long index);
226d7b62727SMatthew Wilcox void __radix_tree_replace(struct radix_tree_root *, struct radix_tree_node *,
2271cf56f9dSMatthew Wilcox void __rcu **slot, void *entry);
228e157b555SMatthew Wilcox void radix_tree_iter_replace(struct radix_tree_root *,
229d7b62727SMatthew Wilcox const struct radix_tree_iter *, void __rcu **slot, void *entry);
230d7b62727SMatthew Wilcox void radix_tree_replace_slot(struct radix_tree_root *,
231d7b62727SMatthew Wilcox void __rcu **slot, void *entry);
2320ac398efSMatthew Wilcox void radix_tree_iter_delete(struct radix_tree_root *,
233d7b62727SMatthew Wilcox struct radix_tree_iter *iter, void __rcu **slot);
23453c59f26SJohannes Weiner void *radix_tree_delete_item(struct radix_tree_root *, unsigned long, void *);
2351da177e4SLinus Torvalds void *radix_tree_delete(struct radix_tree_root *, unsigned long);
23635534c86SMatthew Wilcox unsigned int radix_tree_gang_lookup(const struct radix_tree_root *,
237d604c324SMatthew Wilcox void **results, unsigned long first_index,
238d604c324SMatthew Wilcox unsigned int max_items);
239dd0fc66fSAl Viro int radix_tree_preload(gfp_t gfp_mask);
2405e4c0d97SJan Kara int radix_tree_maybe_preload(gfp_t gfp_mask);
2411da177e4SLinus Torvalds void radix_tree_init(void);
242d7b62727SMatthew Wilcox void *radix_tree_tag_set(struct radix_tree_root *,
243daff89f3SJonathan Corbet unsigned long index, unsigned int tag);
244d7b62727SMatthew Wilcox void *radix_tree_tag_clear(struct radix_tree_root *,
245daff89f3SJonathan Corbet unsigned long index, unsigned int tag);
24635534c86SMatthew Wilcox int radix_tree_tag_get(const struct radix_tree_root *,
247daff89f3SJonathan Corbet unsigned long index, unsigned int tag);
24830b888baSMatthew Wilcox void radix_tree_iter_tag_clear(struct radix_tree_root *,
249268f42deSMatthew Wilcox const struct radix_tree_iter *iter, unsigned int tag);
250d7b62727SMatthew Wilcox unsigned int radix_tree_gang_lookup_tag(const struct radix_tree_root *,
251d7b62727SMatthew Wilcox void **results, unsigned long first_index,
252d7b62727SMatthew Wilcox unsigned int max_items, unsigned int tag);
253d7b62727SMatthew Wilcox unsigned int radix_tree_gang_lookup_tag_slot(const struct radix_tree_root *,
254d7b62727SMatthew Wilcox void __rcu ***results, unsigned long first_index,
255d7b62727SMatthew Wilcox unsigned int max_items, unsigned int tag);
256d7b62727SMatthew Wilcox int radix_tree_tagged(const struct radix_tree_root *, unsigned int tag);
2571da177e4SLinus Torvalds
radix_tree_preload_end(void)2581da177e4SLinus Torvalds static inline void radix_tree_preload_end(void)
2591da177e4SLinus Torvalds {
260cfa6705dSSebastian Andrzej Siewior local_unlock(&radix_tree_preloads.lock);
2611da177e4SLinus Torvalds }
2621da177e4SLinus Torvalds
263460488c5SMatthew Wilcox void __rcu **idr_get_free(struct radix_tree_root *root,
264388f79fdSChris Mi struct radix_tree_iter *iter, gfp_t gfp,
265388f79fdSChris Mi unsigned long max);
266175542f5SMatthew Wilcox
2670a835c4fSMatthew Wilcox enum {
2680a835c4fSMatthew Wilcox RADIX_TREE_ITER_TAG_MASK = 0x0f, /* tag index in lower nybble */
2690a835c4fSMatthew Wilcox RADIX_TREE_ITER_TAGGED = 0x10, /* lookup tagged slots */
2700a835c4fSMatthew Wilcox RADIX_TREE_ITER_CONTIG = 0x20, /* stop at first hole */
2710a835c4fSMatthew Wilcox };
27278c1d784SKonstantin Khlebnikov
27378c1d784SKonstantin Khlebnikov /**
27478c1d784SKonstantin Khlebnikov * radix_tree_iter_init - initialize radix tree iterator
27578c1d784SKonstantin Khlebnikov *
27678c1d784SKonstantin Khlebnikov * @iter: pointer to iterator state
27778c1d784SKonstantin Khlebnikov * @start: iteration starting index
27878c1d784SKonstantin Khlebnikov * Returns: NULL
27978c1d784SKonstantin Khlebnikov */
280d7b62727SMatthew Wilcox static __always_inline void __rcu **
radix_tree_iter_init(struct radix_tree_iter * iter,unsigned long start)28178c1d784SKonstantin Khlebnikov radix_tree_iter_init(struct radix_tree_iter *iter, unsigned long start)
28278c1d784SKonstantin Khlebnikov {
28378c1d784SKonstantin Khlebnikov /*
28478c1d784SKonstantin Khlebnikov * Leave iter->tags uninitialized. radix_tree_next_chunk() will fill it
28578c1d784SKonstantin Khlebnikov * in the case of a successful tagged chunk lookup. If the lookup was
28678c1d784SKonstantin Khlebnikov * unsuccessful or non-tagged then nobody cares about ->tags.
28778c1d784SKonstantin Khlebnikov *
28878c1d784SKonstantin Khlebnikov * Set index to zero to bypass next_index overflow protection.
28978c1d784SKonstantin Khlebnikov * See the comment in radix_tree_next_chunk() for details.
29078c1d784SKonstantin Khlebnikov */
29178c1d784SKonstantin Khlebnikov iter->index = 0;
29278c1d784SKonstantin Khlebnikov iter->next_index = start;
29378c1d784SKonstantin Khlebnikov return NULL;
29478c1d784SKonstantin Khlebnikov }
29578c1d784SKonstantin Khlebnikov
29678c1d784SKonstantin Khlebnikov /**
29778c1d784SKonstantin Khlebnikov * radix_tree_next_chunk - find next chunk of slots for iteration
29878c1d784SKonstantin Khlebnikov *
29978c1d784SKonstantin Khlebnikov * @root: radix tree root
30078c1d784SKonstantin Khlebnikov * @iter: iterator state
30178c1d784SKonstantin Khlebnikov * @flags: RADIX_TREE_ITER_* flags and tag index
30278c1d784SKonstantin Khlebnikov * Returns: pointer to chunk first slot, or NULL if there no more left
30378c1d784SKonstantin Khlebnikov *
30478c1d784SKonstantin Khlebnikov * This function looks up the next chunk in the radix tree starting from
30578c1d784SKonstantin Khlebnikov * @iter->next_index. It returns a pointer to the chunk's first slot.
30678c1d784SKonstantin Khlebnikov * Also it fills @iter with data about chunk: position in the tree (index),
30778c1d784SKonstantin Khlebnikov * its end (next_index), and constructs a bit mask for tagged iterating (tags).
30878c1d784SKonstantin Khlebnikov */
309d7b62727SMatthew Wilcox void __rcu **radix_tree_next_chunk(const struct radix_tree_root *,
31078c1d784SKonstantin Khlebnikov struct radix_tree_iter *iter, unsigned flags);
31178c1d784SKonstantin Khlebnikov
31278c1d784SKonstantin Khlebnikov /**
3130a835c4fSMatthew Wilcox * radix_tree_iter_lookup - look up an index in the radix tree
3140a835c4fSMatthew Wilcox * @root: radix tree root
3150a835c4fSMatthew Wilcox * @iter: iterator state
3160a835c4fSMatthew Wilcox * @index: key to look up
3170a835c4fSMatthew Wilcox *
3180a835c4fSMatthew Wilcox * If @index is present in the radix tree, this function returns the slot
3190a835c4fSMatthew Wilcox * containing it and updates @iter to describe the entry. If @index is not
3200a835c4fSMatthew Wilcox * present, it returns NULL.
3210a835c4fSMatthew Wilcox */
322d7b62727SMatthew Wilcox static inline void __rcu **
radix_tree_iter_lookup(const struct radix_tree_root * root,struct radix_tree_iter * iter,unsigned long index)323d7b62727SMatthew Wilcox radix_tree_iter_lookup(const struct radix_tree_root *root,
3240a835c4fSMatthew Wilcox struct radix_tree_iter *iter, unsigned long index)
3250a835c4fSMatthew Wilcox {
3260a835c4fSMatthew Wilcox radix_tree_iter_init(iter, index);
3270a835c4fSMatthew Wilcox return radix_tree_next_chunk(root, iter, RADIX_TREE_ITER_CONTIG);
3280a835c4fSMatthew Wilcox }
3290a835c4fSMatthew Wilcox
3300a835c4fSMatthew Wilcox /**
33146437f9aSMatthew Wilcox * radix_tree_iter_retry - retry this chunk of the iteration
33246437f9aSMatthew Wilcox * @iter: iterator state
33346437f9aSMatthew Wilcox *
33446437f9aSMatthew Wilcox * If we iterate over a tree protected only by the RCU lock, a race
33546437f9aSMatthew Wilcox * against deletion or creation may result in seeing a slot for which
33646437f9aSMatthew Wilcox * radix_tree_deref_retry() returns true. If so, call this function
33746437f9aSMatthew Wilcox * and continue the iteration.
33846437f9aSMatthew Wilcox */
33946437f9aSMatthew Wilcox static inline __must_check
radix_tree_iter_retry(struct radix_tree_iter * iter)340d7b62727SMatthew Wilcox void __rcu **radix_tree_iter_retry(struct radix_tree_iter *iter)
34146437f9aSMatthew Wilcox {
34246437f9aSMatthew Wilcox iter->next_index = iter->index;
3433cb9185cSAndrey Ryabinin iter->tags = 0;
34446437f9aSMatthew Wilcox return NULL;
34546437f9aSMatthew Wilcox }
34646437f9aSMatthew Wilcox
34721ef5339SRoss Zwisler static inline unsigned long
__radix_tree_iter_add(struct radix_tree_iter * iter,unsigned long slots)34821ef5339SRoss Zwisler __radix_tree_iter_add(struct radix_tree_iter *iter, unsigned long slots)
34921ef5339SRoss Zwisler {
3503a08cd52SMatthew Wilcox return iter->index + slots;
35121ef5339SRoss Zwisler }
35221ef5339SRoss Zwisler
35346437f9aSMatthew Wilcox /**
354148deab2SMatthew Wilcox * radix_tree_iter_resume - resume iterating when the chunk may be invalid
355148deab2SMatthew Wilcox * @slot: pointer to current slot
3567165092fSMatthew Wilcox * @iter: iterator state
357148deab2SMatthew Wilcox * Returns: New slot pointer
3587165092fSMatthew Wilcox *
3597165092fSMatthew Wilcox * If the iterator needs to release then reacquire a lock, the chunk may
3607165092fSMatthew Wilcox * have been invalidated by an insertion or deletion. Call this function
361148deab2SMatthew Wilcox * before releasing the lock to continue the iteration from the next index.
3627165092fSMatthew Wilcox */
363d7b62727SMatthew Wilcox void __rcu **__must_check radix_tree_iter_resume(void __rcu **slot,
364148deab2SMatthew Wilcox struct radix_tree_iter *iter);
3657165092fSMatthew Wilcox
3667165092fSMatthew Wilcox /**
36778c1d784SKonstantin Khlebnikov * radix_tree_chunk_size - get current chunk size
36878c1d784SKonstantin Khlebnikov *
36978c1d784SKonstantin Khlebnikov * @iter: pointer to radix tree iterator
37078c1d784SKonstantin Khlebnikov * Returns: current chunk size
37178c1d784SKonstantin Khlebnikov */
37273204282SKonstantin Khlebnikov static __always_inline long
radix_tree_chunk_size(struct radix_tree_iter * iter)37378c1d784SKonstantin Khlebnikov radix_tree_chunk_size(struct radix_tree_iter *iter)
37478c1d784SKonstantin Khlebnikov {
3753a08cd52SMatthew Wilcox return iter->next_index - iter->index;
37621ef5339SRoss Zwisler }
37721ef5339SRoss Zwisler
37878c1d784SKonstantin Khlebnikov /**
37978c1d784SKonstantin Khlebnikov * radix_tree_next_slot - find next slot in chunk
38078c1d784SKonstantin Khlebnikov *
38178c1d784SKonstantin Khlebnikov * @slot: pointer to current slot
382f78b8250SHui Su * @iter: pointer to iterator state
38378c1d784SKonstantin Khlebnikov * @flags: RADIX_TREE_ITER_*, should be constant
38478c1d784SKonstantin Khlebnikov * Returns: pointer to next slot, or NULL if there no more left
38578c1d784SKonstantin Khlebnikov *
38678c1d784SKonstantin Khlebnikov * This function updates @iter->index in the case of a successful lookup.
38778c1d784SKonstantin Khlebnikov * For tagged lookup it also eats @iter->tags.
388915045feSRoss Zwisler *
389915045feSRoss Zwisler * There are several cases where 'slot' can be passed in as NULL to this
390148deab2SMatthew Wilcox * function. These cases result from the use of radix_tree_iter_resume() or
391915045feSRoss Zwisler * radix_tree_iter_retry(). In these cases we don't end up dereferencing
392915045feSRoss Zwisler * 'slot' because either:
393915045feSRoss Zwisler * a) we are doing tagged iteration and iter->tags has been set to 0, or
394915045feSRoss Zwisler * b) we are doing non-tagged iteration, and iter->index and iter->next_index
395915045feSRoss Zwisler * have been set up so that radix_tree_chunk_size() returns 1 or 0.
39678c1d784SKonstantin Khlebnikov */
radix_tree_next_slot(void __rcu ** slot,struct radix_tree_iter * iter,unsigned flags)397d7b62727SMatthew Wilcox static __always_inline void __rcu **radix_tree_next_slot(void __rcu **slot,
398d7b62727SMatthew Wilcox struct radix_tree_iter *iter, unsigned flags)
39978c1d784SKonstantin Khlebnikov {
40078c1d784SKonstantin Khlebnikov if (flags & RADIX_TREE_ITER_TAGGED) {
40178c1d784SKonstantin Khlebnikov iter->tags >>= 1;
40221ef5339SRoss Zwisler if (unlikely(!iter->tags))
40321ef5339SRoss Zwisler return NULL;
40478c1d784SKonstantin Khlebnikov if (likely(iter->tags & 1ul)) {
40521ef5339SRoss Zwisler iter->index = __radix_tree_iter_add(iter, 1);
406148deab2SMatthew Wilcox slot++;
407148deab2SMatthew Wilcox goto found;
40878c1d784SKonstantin Khlebnikov }
40921ef5339SRoss Zwisler if (!(flags & RADIX_TREE_ITER_CONTIG)) {
41078c1d784SKonstantin Khlebnikov unsigned offset = __ffs(iter->tags);
41178c1d784SKonstantin Khlebnikov
412148deab2SMatthew Wilcox iter->tags >>= offset++;
413148deab2SMatthew Wilcox iter->index = __radix_tree_iter_add(iter, offset);
414148deab2SMatthew Wilcox slot += offset;
415148deab2SMatthew Wilcox goto found;
41678c1d784SKonstantin Khlebnikov }
41778c1d784SKonstantin Khlebnikov } else {
41821ef5339SRoss Zwisler long count = radix_tree_chunk_size(iter);
41978c1d784SKonstantin Khlebnikov
42021ef5339SRoss Zwisler while (--count > 0) {
42178c1d784SKonstantin Khlebnikov slot++;
42221ef5339SRoss Zwisler iter->index = __radix_tree_iter_add(iter, 1);
42321ef5339SRoss Zwisler
42478c1d784SKonstantin Khlebnikov if (likely(*slot))
425148deab2SMatthew Wilcox goto found;
426fffaee36SKonstantin Khlebnikov if (flags & RADIX_TREE_ITER_CONTIG) {
427fffaee36SKonstantin Khlebnikov /* forbid switching to the next chunk */
428fffaee36SKonstantin Khlebnikov iter->next_index = 0;
42978c1d784SKonstantin Khlebnikov break;
43078c1d784SKonstantin Khlebnikov }
43178c1d784SKonstantin Khlebnikov }
432fffaee36SKonstantin Khlebnikov }
43378c1d784SKonstantin Khlebnikov return NULL;
434148deab2SMatthew Wilcox
435148deab2SMatthew Wilcox found:
436148deab2SMatthew Wilcox return slot;
43778c1d784SKonstantin Khlebnikov }
43878c1d784SKonstantin Khlebnikov
43978c1d784SKonstantin Khlebnikov /**
44078c1d784SKonstantin Khlebnikov * radix_tree_for_each_slot - iterate over non-empty slots
44178c1d784SKonstantin Khlebnikov *
44278c1d784SKonstantin Khlebnikov * @slot: the void** variable for pointer to slot
44378c1d784SKonstantin Khlebnikov * @root: the struct radix_tree_root pointer
44478c1d784SKonstantin Khlebnikov * @iter: the struct radix_tree_iter pointer
44578c1d784SKonstantin Khlebnikov * @start: iteration starting index
44678c1d784SKonstantin Khlebnikov *
44778c1d784SKonstantin Khlebnikov * @slot points to radix tree slot, @iter->index contains its index.
44878c1d784SKonstantin Khlebnikov */
44978c1d784SKonstantin Khlebnikov #define radix_tree_for_each_slot(slot, root, iter, start) \
45078c1d784SKonstantin Khlebnikov for (slot = radix_tree_iter_init(iter, start) ; \
45178c1d784SKonstantin Khlebnikov slot || (slot = radix_tree_next_chunk(root, iter, 0)) ; \
45278c1d784SKonstantin Khlebnikov slot = radix_tree_next_slot(slot, iter, 0))
45378c1d784SKonstantin Khlebnikov
45478c1d784SKonstantin Khlebnikov /**
45578c1d784SKonstantin Khlebnikov * radix_tree_for_each_tagged - iterate over tagged slots
45678c1d784SKonstantin Khlebnikov *
45778c1d784SKonstantin Khlebnikov * @slot: the void** variable for pointer to slot
45878c1d784SKonstantin Khlebnikov * @root: the struct radix_tree_root pointer
45978c1d784SKonstantin Khlebnikov * @iter: the struct radix_tree_iter pointer
46078c1d784SKonstantin Khlebnikov * @start: iteration starting index
46178c1d784SKonstantin Khlebnikov * @tag: tag index
46278c1d784SKonstantin Khlebnikov *
46378c1d784SKonstantin Khlebnikov * @slot points to radix tree slot, @iter->index contains its index.
46478c1d784SKonstantin Khlebnikov */
46578c1d784SKonstantin Khlebnikov #define radix_tree_for_each_tagged(slot, root, iter, start, tag) \
46678c1d784SKonstantin Khlebnikov for (slot = radix_tree_iter_init(iter, start) ; \
46778c1d784SKonstantin Khlebnikov slot || (slot = radix_tree_next_chunk(root, iter, \
46878c1d784SKonstantin Khlebnikov RADIX_TREE_ITER_TAGGED | tag)) ; \
46978c1d784SKonstantin Khlebnikov slot = radix_tree_next_slot(slot, iter, \
470148deab2SMatthew Wilcox RADIX_TREE_ITER_TAGGED | tag))
47178c1d784SKonstantin Khlebnikov
4721da177e4SLinus Torvalds #endif /* _LINUX_RADIX_TREE_H */
473