1 /*
2 * Copyright (C) 2001 Momchil Velikov
3 * Portions Copyright (C) 2001 Christoph Hellwig
4 * Copyright (C) 2006 Nick Piggin
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>
25 #include <linux/kernel.h>
26 #include <linux/rcupdate.h>
27
28 /*
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.
32 *
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.
37 */
38 #define RADIX_TREE_INDIRECT_PTR 1
39 #define RADIX_TREE_RETRY ((void *)-1UL)
40
41 static inline void *radix_tree_ptr_to_indirect(void *ptr)
42 {
43 return (void *)((unsigned long)ptr | RADIX_TREE_INDIRECT_PTR);
44 }
45
46 static inline void *radix_tree_indirect_to_ptr(void *ptr)
47 {
48 return (void *)((unsigned long)ptr & ~RADIX_TREE_INDIRECT_PTR);
49 }
50
51 static inline int radix_tree_is_indirect_ptr(void *ptr)
52 {
53 return (int)((unsigned long)ptr & RADIX_TREE_INDIRECT_PTR);
54 }
55
56 /*** radix-tree API starts here ***/
57
58 #define RADIX_TREE_MAX_TAGS 2
59
60 /* root tags are stored in gfp_mask, shifted by __GFP_BITS_SHIFT */
61 struct radix_tree_root {
62 unsigned int height;
63 gfp_t gfp_mask;
64 struct radix_tree_node *rnode;
65 spinlock_t lock;
66 };
67
68 #define RADIX_TREE_INIT(mask) { \
69 .height = 0, \
70 .gfp_mask = (mask), \
71 .rnode = NULL, \
72 .lock = __SPIN_LOCK_UNLOCKED(radix_tree_root.lock), \
73 }
74
75 #define RADIX_TREE(name, mask) \
76 struct radix_tree_root name = RADIX_TREE_INIT(mask)
77
78 static inline void INIT_RADIX_TREE(struct radix_tree_root *root, gfp_t gfp_mask)
79 {
80 root->height = 0;
81 root->gfp_mask = gfp_mask;
82 root->rnode = NULL;
83 spin_lock_init(&root->lock);
84 }
85
86 struct radix_tree_context {
87 struct radix_tree_root *tree;
88 struct radix_tree_root *root;
89 #ifdef CONFIG_RADIX_TREE_CONCURRENT
90 spinlock_t *locked;
91 #endif
92 };
93
94 #ifdef CONFIG_RADIX_TREE_CONCURRENT
95 #define RADIX_CONTEXT_ROOT(context) \
96 ((struct radix_tree_root *)(((unsigned long)context) + 1))
97
98 #define __RADIX_TREE_CONTEXT_INIT(context, _tree) \
99 .tree = RADIX_CONTEXT_ROOT(&context), \
100 .locked = NULL,
101 #else
102 #define __RADIX_TREE_CONTEXT_INIT(context, _tree) \
103 .tree = (_tree),
104 #endif
105
106 #define DEFINE_RADIX_TREE_CONTEXT(context, _tree) \
107 struct radix_tree_context context = { \
108 .root = (_tree), \
109 __RADIX_TREE_CONTEXT_INIT(context, _tree) \
110 }
111
112 static inline void
113 init_radix_tree_context(struct radix_tree_context *ctx,
114 struct radix_tree_root *root)
115 {
116 ctx->root = root;
117 #ifdef CONFIG_RADIX_TREE_CONCURRENT
118 ctx->tree = RADIX_CONTEXT_ROOT(ctx);
119 ctx->locked = NULL;
120 #else
121 ctx->tree = root;
122 #endif
123 }
124
125 /**
126 * Radix-tree synchronization
127 *
128 * The radix-tree API requires that users provide all synchronisation (with
129 * specific exceptions, noted below).
130 *
131 * Synchronization of access to the data items being stored in the tree, and
132 * management of their lifetimes must be completely managed by API users.
133 *
134 * For API usage, in general,
135 * - any function _modifying_ the tree or tags (inserting or deleting
136 * items, setting or clearing tags) must exclude other modifications, and
137 * exclude any functions reading the tree.
138 * - any function _reading_ the tree or tags (looking up items or tags,
139 * gang lookups) must exclude modifications to the tree, but may occur
140 * concurrently with other readers.
141 *
142 * The notable exceptions to this rule are the following functions:
143 * radix_tree_lookup
144 * radix_tree_lookup_slot
145 * radix_tree_tag_get
146 * radix_tree_gang_lookup
147 * radix_tree_gang_lookup_slot
148 * radix_tree_gang_lookup_tag
149 * radix_tree_gang_lookup_tag_slot
150 * radix_tree_tagged
151 *
152 * The first 7 functions are able to be called locklessly, using RCU. The
153 * caller must ensure calls to these functions are made within rcu_read_lock()
154 * regions. Other readers (lock-free or otherwise) and modifications may be
155 * running concurrently.
156 *
157 * It is still required that the caller manage the synchronization and lifetimes
158 * of the items. So if RCU lock-free lookups are used, typically this would mean
159 * that the items have their own locks, or are amenable to lock-free access; and
160 * that the items are freed by RCU (or only freed after having been deleted from
161 * the radix tree *and* a synchronize_rcu() grace period).
162 *
163 * (Note, rcu_assign_pointer and rcu_dereference are not needed to control
164 * access to data items when inserting into or looking up from the radix tree)
165 *
166 * radix_tree_tagged is able to be called without locking or RCU.
167 */
168
169 /**
170 * radix_tree_deref_slot - dereference a slot
171 * @pslot: pointer to slot, returned by radix_tree_lookup_slot
172 * Returns: item that was stored in that slot with any direct pointer flag
173 * removed.
174 *
175 * For use with radix_tree_lookup_slot(). Caller must hold tree at least read
176 * locked across slot lookup and dereference. More likely, will be used with
177 * radix_tree_replace_slot(), as well, so caller will hold tree write locked.
178 */
179 static inline void *radix_tree_deref_slot(void **pslot)
180 {
181 void *ret = *pslot;
182 if (unlikely(radix_tree_is_indirect_ptr(ret)))
183 ret = RADIX_TREE_RETRY;
184 return ret;
185 }
186 /**
187 * radix_tree_replace_slot - replace item in a slot
188 * @pslot: pointer to slot, returned by radix_tree_lookup_slot
189 * @item: new item to store in the slot.
190 *
191 * For use with radix_tree_lookup_slot(). Caller must hold tree write locked
192 * across slot lookup and replacement.
193 */
194 static inline void radix_tree_replace_slot(void **pslot, void *item)
195 {
196 BUG_ON(radix_tree_is_indirect_ptr(item));
197 rcu_assign_pointer(*pslot, item);
198 }
199
200 #if defined(CONFIG_RADIX_TREE_OPTIMISTIC)
201 static inline void radix_tree_lock(struct radix_tree_context *context)
202 {
203 rcu_read_lock();
204 BUG_ON(context->locked);
205 }
206 #elif defined(CONFIG_RADIX_TREE_CONCURRENT)
207 static inline void radix_tree_lock(struct radix_tree_context *context)
208 {
209 struct radix_tree_root *root = context->root;
210
211 rcu_read_lock();
212 spin_lock(&root->lock);
213 BUG_ON(context->locked);
214 context->locked = &root->lock;
215 }
216 #else
217 static inline void radix_tree_lock(struct radix_tree_context *context)
218 {
219 struct radix_tree_root *root = context->root;
220
221 rcu_read_lock();
222 spin_lock(&root->lock);
223 }
224 #endif
225
226 #if defined(CONFIG_RADIX_TREE_CONCURRENT)
227 static inline void radix_tree_unlock(struct radix_tree_context *context)
228 {
229 BUG_ON(!context->locked);
230 spin_unlock(context->locked);
231 context->locked = NULL;
232 rcu_read_unlock();
233 }
234 #else
235 static inline void radix_tree_unlock(struct radix_tree_context *context)
236 {
237 spin_unlock(&context->root->lock);
238 rcu_read_unlock();
239 }
240 #endif
241
242 int radix_tree_insert(struct radix_tree_root *, unsigned long, void *);
243 void *radix_tree_lookup(struct radix_tree_root *, unsigned long);
244 void **radix_tree_lookup_slot(struct radix_tree_root *, unsigned long);
245 void *radix_tree_delete(struct radix_tree_root *, unsigned long);
246 unsigned int
247 radix_tree_gang_lookup(struct radix_tree_root *root, void **results,
248 unsigned long first_index, unsigned int max_items);
249 unsigned int
250 radix_tree_gang_lookup_slot(struct radix_tree_root *root, void ***results,
251 unsigned long first_index, unsigned int max_items);
252 unsigned long radix_tree_next_hole(struct radix_tree_root *root,
253 unsigned long index, unsigned long max_scan);
254 /*
255 * On a mutex based kernel we can freely schedule within the radix code:
256 */
257 #ifdef CONFIG_PREEMPT_RT
258 static inline int radix_tree_preload(gfp_t gfp_mask)
259 {
260 return 0;
261 }
262 #else
263 int radix_tree_preload(gfp_t gfp_mask);
264 #endif
265
266 void radix_tree_init(void);
267 void *radix_tree_tag_set(struct radix_tree_root *root,
268 unsigned long index, unsigned int tag);
269 void *radix_tree_tag_clear(struct radix_tree_root *root,
270 unsigned long index, unsigned int tag);
271 int radix_tree_tag_get(struct radix_tree_root *root,
272 unsigned long index, unsigned int tag);
273 unsigned int
274 radix_tree_gang_lookup_tag(struct radix_tree_root *root, void **results,
275 unsigned long first_index, unsigned int max_items,
276 unsigned int tag);
277 unsigned int
278 radix_tree_gang_lookup_tag_slot(struct radix_tree_root *root, void ***results,
279 unsigned long first_index, unsigned int max_items,
280 unsigned int tag);
281 int radix_tree_tagged(struct radix_tree_root *root, unsigned int tag);
282
283 static inline void radix_tree_preload_end(void)
284 {
285 #ifndef CONFIG_PREEMPT_RT
286 preempt_enable();
287 #endif
288 }
289
290 #endif /* _LINUX_RADIX_TREE_H */
291
|
This page was automatically generated by the
LXR engine.
|