Commit | Line | Data |
---|---|---|
1da177e4 LT |
1 | /* |
2 | * Copyright (C) 2001 Momchil Velikov | |
3 | * Portions Copyright (C) 2001 Christoph Hellwig | |
7cf9c2c7 | 4 | * Copyright (C) 2006 Nick Piggin |
1da177e4 LT |
5 | * |
6 | * This program is free software; you can redistribute it and/or | |
7 | * modify it under the terms of the GNU General Public License as | |
8 | * published by the Free Software Foundation; either version 2, or (at | |
9 | * your option) any later version. | |
10 | * | |
11 | * This program is distributed in the hope that it will be useful, but | |
12 | * WITHOUT ANY WARRANTY; without even the implied warranty of | |
13 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
14 | * General Public License for more details. | |
15 | * | |
16 | * You should have received a copy of the GNU General Public License | |
17 | * along with this program; if not, write to the Free Software | |
18 | * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. | |
19 | */ | |
20 | #ifndef _LINUX_RADIX_TREE_H | |
21 | #define _LINUX_RADIX_TREE_H | |
22 | ||
23 | #include <linux/preempt.h> | |
24 | #include <linux/types.h> | |
7cf9c2c7 NP |
25 | #include <linux/kernel.h> |
26 | #include <linux/rcupdate.h> | |
27 | ||
28 | /* | |
c0bc9875 NP |
29 | * An indirect pointer (root->rnode pointing to a radix_tree_node, rather |
30 | * than a data item) is signalled by the low bit set in the root->rnode | |
31 | * pointer. | |
7cf9c2c7 | 32 | * |
c0bc9875 NP |
33 | * In this case root->height is > 0, but the indirect pointer tests are |
34 | * needed for RCU lookups (because root->height is unreliable). The only | |
35 | * time callers need worry about this is when doing a lookup_slot under | |
36 | * RCU. | |
27d20fdd NP |
37 | * |
38 | * Indirect pointer in fact is also used to tag the last pointer of a node | |
39 | * when it is shrunk, before we rcu free the node. See shrink code for | |
40 | * details. | |
7cf9c2c7 | 41 | */ |
c0bc9875 | 42 | #define RADIX_TREE_INDIRECT_PTR 1 |
7cf9c2c7 | 43 | |
a1115570 AB |
44 | #define radix_tree_indirect_to_ptr(ptr) \ |
45 | radix_tree_indirect_to_ptr((void __force *)(ptr)) | |
7cf9c2c7 | 46 | |
c0bc9875 | 47 | static inline int radix_tree_is_indirect_ptr(void *ptr) |
7cf9c2c7 | 48 | { |
c0bc9875 | 49 | return (int)((unsigned long)ptr & RADIX_TREE_INDIRECT_PTR); |
7cf9c2c7 NP |
50 | } |
51 | ||
52 | /*** radix-tree API starts here ***/ | |
1da177e4 | 53 | |
f446daae | 54 | #define RADIX_TREE_MAX_TAGS 3 |
612d6c19 NP |
55 | |
56 | /* root tags are stored in gfp_mask, shifted by __GFP_BITS_SHIFT */ | |
1da177e4 LT |
57 | struct radix_tree_root { |
58 | unsigned int height; | |
fd4f2df2 | 59 | gfp_t gfp_mask; |
a1115570 | 60 | struct radix_tree_node __rcu *rnode; |
1da177e4 LT |
61 | }; |
62 | ||
63 | #define RADIX_TREE_INIT(mask) { \ | |
64 | .height = 0, \ | |
65 | .gfp_mask = (mask), \ | |
66 | .rnode = NULL, \ | |
67 | } | |
68 | ||
69 | #define RADIX_TREE(name, mask) \ | |
70 | struct radix_tree_root name = RADIX_TREE_INIT(mask) | |
71 | ||
72 | #define INIT_RADIX_TREE(root, mask) \ | |
73 | do { \ | |
74 | (root)->height = 0; \ | |
75 | (root)->gfp_mask = (mask); \ | |
76 | (root)->rnode = NULL; \ | |
77 | } while (0) | |
78 | ||
7cf9c2c7 NP |
79 | /** |
80 | * Radix-tree synchronization | |
81 | * | |
82 | * The radix-tree API requires that users provide all synchronisation (with | |
83 | * specific exceptions, noted below). | |
84 | * | |
85 | * Synchronization of access to the data items being stored in the tree, and | |
86 | * management of their lifetimes must be completely managed by API users. | |
87 | * | |
88 | * For API usage, in general, | |
59c51591 | 89 | * - any function _modifying_ the tree or tags (inserting or deleting |
eb8dc5e7 | 90 | * items, setting or clearing tags) must exclude other modifications, and |
7cf9c2c7 | 91 | * exclude any functions reading the tree. |
59c51591 | 92 | * - any function _reading_ the tree or tags (looking up items or tags, |
7cf9c2c7 NP |
93 | * gang lookups) must exclude modifications to the tree, but may occur |
94 | * concurrently with other readers. | |
95 | * | |
96 | * The notable exceptions to this rule are the following functions: | |
97 | * radix_tree_lookup | |
47feff2c | 98 | * radix_tree_lookup_slot |
7cf9c2c7 NP |
99 | * radix_tree_tag_get |
100 | * radix_tree_gang_lookup | |
47feff2c | 101 | * radix_tree_gang_lookup_slot |
7cf9c2c7 | 102 | * radix_tree_gang_lookup_tag |
47feff2c | 103 | * radix_tree_gang_lookup_tag_slot |
7cf9c2c7 NP |
104 | * radix_tree_tagged |
105 | * | |
47feff2c | 106 | * The first 7 functions are able to be called locklessly, using RCU. The |
7cf9c2c7 NP |
107 | * caller must ensure calls to these functions are made within rcu_read_lock() |
108 | * regions. Other readers (lock-free or otherwise) and modifications may be | |
109 | * running concurrently. | |
110 | * | |
111 | * It is still required that the caller manage the synchronization and lifetimes | |
112 | * of the items. So if RCU lock-free lookups are used, typically this would mean | |
113 | * that the items have their own locks, or are amenable to lock-free access; and | |
114 | * that the items are freed by RCU (or only freed after having been deleted from | |
115 | * the radix tree *and* a synchronize_rcu() grace period). | |
116 | * | |
117 | * (Note, rcu_assign_pointer and rcu_dereference are not needed to control | |
118 | * access to data items when inserting into or looking up from the radix tree) | |
119 | * | |
ce82653d DH |
120 | * Note that the value returned by radix_tree_tag_get() may not be relied upon |
121 | * if only the RCU read lock is held. Functions to set/clear tags and to | |
122 | * delete nodes running concurrently with it may affect its result such that | |
123 | * two consecutive reads in the same locked section may return different | |
124 | * values. If reliability is required, modification functions must also be | |
125 | * excluded from concurrency. | |
126 | * | |
7cf9c2c7 NP |
127 | * radix_tree_tagged is able to be called without locking or RCU. |
128 | */ | |
129 | ||
130 | /** | |
131 | * radix_tree_deref_slot - dereference a slot | |
132 | * @pslot: pointer to slot, returned by radix_tree_lookup_slot | |
133 | * Returns: item that was stored in that slot with any direct pointer flag | |
134 | * removed. | |
135 | * | |
136 | * For use with radix_tree_lookup_slot(). Caller must hold tree at least read | |
27d20fdd NP |
137 | * locked across slot lookup and dereference. Not required if write lock is |
138 | * held (ie. items cannot be concurrently inserted). | |
139 | * | |
140 | * radix_tree_deref_retry must be used to confirm validity of the pointer if | |
141 | * only the read lock is held. | |
7cf9c2c7 NP |
142 | */ |
143 | static inline void *radix_tree_deref_slot(void **pslot) | |
144 | { | |
27d20fdd | 145 | return rcu_dereference(*pslot); |
7cf9c2c7 | 146 | } |
27d20fdd | 147 | |
29c1f677 MG |
148 | /** |
149 | * radix_tree_deref_slot_protected - dereference a slot without RCU lock but with tree lock held | |
150 | * @pslot: pointer to slot, returned by radix_tree_lookup_slot | |
151 | * Returns: item that was stored in that slot with any direct pointer flag | |
152 | * removed. | |
153 | * | |
154 | * Similar to radix_tree_deref_slot but only used during migration when a pages | |
155 | * mapping is being moved. The caller does not hold the RCU read lock but it | |
156 | * must hold the tree lock to prevent parallel updates. | |
157 | */ | |
158 | static inline void *radix_tree_deref_slot_protected(void **pslot, | |
159 | spinlock_t *treelock) | |
160 | { | |
161 | return rcu_dereference_protected(*pslot, lockdep_is_held(treelock)); | |
162 | } | |
163 | ||
27d20fdd NP |
164 | /** |
165 | * radix_tree_deref_retry - check radix_tree_deref_slot | |
166 | * @arg: pointer returned by radix_tree_deref_slot | |
167 | * Returns: 0 if retry is not required, otherwise retry is required | |
168 | * | |
169 | * radix_tree_deref_retry must be used with radix_tree_deref_slot. | |
170 | */ | |
171 | static inline int radix_tree_deref_retry(void *arg) | |
172 | { | |
173 | return unlikely((unsigned long)arg & RADIX_TREE_INDIRECT_PTR); | |
174 | } | |
175 | ||
7cf9c2c7 NP |
176 | /** |
177 | * radix_tree_replace_slot - replace item in a slot | |
178 | * @pslot: pointer to slot, returned by radix_tree_lookup_slot | |
179 | * @item: new item to store in the slot. | |
180 | * | |
181 | * For use with radix_tree_lookup_slot(). Caller must hold tree write locked | |
182 | * across slot lookup and replacement. | |
183 | */ | |
184 | static inline void radix_tree_replace_slot(void **pslot, void *item) | |
185 | { | |
c0bc9875 NP |
186 | BUG_ON(radix_tree_is_indirect_ptr(item)); |
187 | rcu_assign_pointer(*pslot, item); | |
7cf9c2c7 NP |
188 | } |
189 | ||
1da177e4 LT |
190 | int radix_tree_insert(struct radix_tree_root *, unsigned long, void *); |
191 | void *radix_tree_lookup(struct radix_tree_root *, unsigned long); | |
a4331366 | 192 | void **radix_tree_lookup_slot(struct radix_tree_root *, unsigned long); |
1da177e4 LT |
193 | void *radix_tree_delete(struct radix_tree_root *, unsigned long); |
194 | unsigned int | |
195 | radix_tree_gang_lookup(struct radix_tree_root *root, void **results, | |
196 | unsigned long first_index, unsigned int max_items); | |
47feff2c NP |
197 | unsigned int |
198 | radix_tree_gang_lookup_slot(struct radix_tree_root *root, void ***results, | |
199 | unsigned long first_index, unsigned int max_items); | |
6df8ba4f FW |
200 | unsigned long radix_tree_next_hole(struct radix_tree_root *root, |
201 | unsigned long index, unsigned long max_scan); | |
dc566127 WF |
202 | unsigned long radix_tree_prev_hole(struct radix_tree_root *root, |
203 | unsigned long index, unsigned long max_scan); | |
dd0fc66f | 204 | int radix_tree_preload(gfp_t gfp_mask); |
1da177e4 LT |
205 | void radix_tree_init(void); |
206 | void *radix_tree_tag_set(struct radix_tree_root *root, | |
daff89f3 | 207 | unsigned long index, unsigned int tag); |
1da177e4 | 208 | void *radix_tree_tag_clear(struct radix_tree_root *root, |
daff89f3 | 209 | unsigned long index, unsigned int tag); |
1da177e4 | 210 | int radix_tree_tag_get(struct radix_tree_root *root, |
daff89f3 | 211 | unsigned long index, unsigned int tag); |
1da177e4 LT |
212 | unsigned int |
213 | radix_tree_gang_lookup_tag(struct radix_tree_root *root, void **results, | |
daff89f3 JC |
214 | unsigned long first_index, unsigned int max_items, |
215 | unsigned int tag); | |
47feff2c NP |
216 | unsigned int |
217 | radix_tree_gang_lookup_tag_slot(struct radix_tree_root *root, void ***results, | |
218 | unsigned long first_index, unsigned int max_items, | |
219 | unsigned int tag); | |
ebf8aa44 JK |
220 | unsigned long radix_tree_range_tag_if_tagged(struct radix_tree_root *root, |
221 | unsigned long *first_indexp, unsigned long last_index, | |
222 | unsigned long nr_to_tag, | |
223 | unsigned int fromtag, unsigned int totag); | |
daff89f3 | 224 | int radix_tree_tagged(struct radix_tree_root *root, unsigned int tag); |
1da177e4 LT |
225 | |
226 | static inline void radix_tree_preload_end(void) | |
227 | { | |
228 | preempt_enable(); | |
229 | } | |
230 | ||
231 | #endif /* _LINUX_RADIX_TREE_H */ |