/root/src/xen/xen/common/radix-tree.c
Line | Count | Source (jump to first uncovered line) |
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 | | * |
7 | | * This program is free software; you can redistribute it and/or |
8 | | * modify it under the terms of the GNU General Public License as |
9 | | * published by the Free Software Foundation; either version 2, or (at |
10 | | * your option) any later version. |
11 | | * |
12 | | * This program is distributed in the hope that it will be useful, but |
13 | | * WITHOUT ANY WARRANTY; without even the implied warranty of |
14 | | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
15 | | * General Public License for more details. |
16 | | * |
17 | | * You should have received a copy of the GNU General Public License |
18 | | * along with this program; If not, see <http://www.gnu.org/licenses/>. |
19 | | */ |
20 | | |
21 | | #include <xen/init.h> |
22 | | #include <xen/radix-tree.h> |
23 | | #include <xen/errno.h> |
24 | | |
25 | | struct radix_tree_path { |
26 | | struct radix_tree_node *node; |
27 | | int offset; |
28 | | }; |
29 | | |
30 | 12 | #define RADIX_TREE_INDEX_BITS (8 /* CHAR_BIT */ * sizeof(unsigned long)) |
31 | | #define RADIX_TREE_MAX_PATH (DIV_ROUND_UP(RADIX_TREE_INDEX_BITS, \ |
32 | | RADIX_TREE_MAP_SHIFT)) |
33 | | |
34 | | /* |
35 | | * The height_to_maxindex array needs to be one deeper than the maximum |
36 | | * path as height 0 holds only 1 entry. |
37 | | */ |
38 | | static unsigned long height_to_maxindex[RADIX_TREE_MAX_PATH + 1] __read_mostly; |
39 | | |
40 | | static inline void *ptr_to_indirect(void *ptr) |
41 | 4 | { |
42 | 4 | return (void *)((unsigned long)ptr | RADIX_TREE_INDIRECT_PTR); |
43 | 4 | } |
44 | | |
45 | | static inline void *indirect_to_ptr(void *ptr) |
46 | 35.9k | { |
47 | 35.9k | return (void *)((unsigned long)ptr & ~RADIX_TREE_INDIRECT_PTR); |
48 | 35.9k | } |
49 | | |
50 | | struct rcu_node { |
51 | | struct radix_tree_node node; |
52 | | struct rcu_head rcu_head; |
53 | | }; |
54 | | |
55 | | static struct radix_tree_node *rcu_node_alloc(void *arg) |
56 | 6 | { |
57 | 6 | struct rcu_node *rcu_node = xmalloc(struct rcu_node); |
58 | 6 | return rcu_node ? &rcu_node->node : NULL; |
59 | 6 | } |
60 | | |
61 | | static void _rcu_node_free(struct rcu_head *head) |
62 | 0 | { |
63 | 0 | struct rcu_node *rcu_node = |
64 | 0 | container_of(head, struct rcu_node, rcu_head); |
65 | 0 | xfree(rcu_node); |
66 | 0 | } |
67 | | |
68 | | static void rcu_node_free(struct radix_tree_node *node, void *arg) |
69 | 0 | { |
70 | 0 | struct rcu_node *rcu_node = container_of(node, struct rcu_node, node); |
71 | 0 | call_rcu(&rcu_node->rcu_head, _rcu_node_free); |
72 | 0 | } |
73 | | |
74 | | static struct radix_tree_node *radix_tree_node_alloc( |
75 | | struct radix_tree_root *root) |
76 | 6 | { |
77 | 6 | struct radix_tree_node *ret; |
78 | 6 | ret = root->node_alloc(root->node_alloc_free_arg); |
79 | 6 | if (ret) |
80 | 6 | memset(ret, 0, sizeof(*ret)); |
81 | 6 | return ret; |
82 | 6 | } |
83 | | |
84 | | static void radix_tree_node_free( |
85 | | struct radix_tree_root *root, struct radix_tree_node *node) |
86 | 0 | { |
87 | 0 | root->node_free(node, root->node_alloc_free_arg); |
88 | 0 | } |
89 | | |
90 | | /* |
91 | | * Return the maximum key which can be store into a |
92 | | * radix tree with height HEIGHT. |
93 | | */ |
94 | | static inline unsigned long radix_tree_maxindex(unsigned int height) |
95 | 18.3k | { |
96 | 18.3k | return height_to_maxindex[height]; |
97 | 18.3k | } |
98 | | |
99 | | /* |
100 | | * Extend a radix tree so it can store key @index. |
101 | | */ |
102 | | static int radix_tree_extend(struct radix_tree_root *root, unsigned long index) |
103 | 4 | { |
104 | 4 | struct radix_tree_node *node; |
105 | 4 | unsigned int height; |
106 | 4 | |
107 | 4 | /* Figure out what the height should be. */ |
108 | 4 | height = root->height + 1; |
109 | 4 | while (index > radix_tree_maxindex(height)) |
110 | 0 | height++; |
111 | 4 | |
112 | 4 | if (root->rnode == NULL) { |
113 | 2 | root->height = height; |
114 | 2 | goto out; |
115 | 2 | } |
116 | 4 | |
117 | 2 | do { |
118 | 2 | unsigned int newheight; |
119 | 2 | if (!(node = radix_tree_node_alloc(root))) |
120 | 0 | return -ENOMEM; |
121 | 2 | |
122 | 2 | /* Increase the height. */ |
123 | 2 | node->slots[0] = indirect_to_ptr(root->rnode); |
124 | 2 | |
125 | 2 | newheight = root->height+1; |
126 | 2 | node->height = newheight; |
127 | 2 | node->count = 1; |
128 | 2 | node = ptr_to_indirect(node); |
129 | 2 | rcu_assign_pointer(root->rnode, node); |
130 | 2 | root->height = newheight; |
131 | 2 | } while (height > root->height); |
132 | 4 | out: |
133 | 4 | return 0; |
134 | 2 | } |
135 | | |
136 | | /** |
137 | | * radix_tree_insert - insert into a radix tree |
138 | | * @root: radix tree root |
139 | | * @index: index key |
140 | | * @item: item to insert |
141 | | * |
142 | | * Insert an item into the radix tree at position @index. |
143 | | */ |
144 | | int radix_tree_insert(struct radix_tree_root *root, |
145 | | unsigned long index, void *item) |
146 | 97 | { |
147 | 97 | struct radix_tree_node *node = NULL, *slot; |
148 | 97 | unsigned int height, shift; |
149 | 97 | int offset; |
150 | 97 | int error; |
151 | 97 | |
152 | 97 | BUG_ON(radix_tree_is_indirect_ptr(item)); |
153 | 97 | |
154 | 97 | /* Make sure the tree is high enough. */ |
155 | 97 | if (index > radix_tree_maxindex(root->height)) { |
156 | 4 | error = radix_tree_extend(root, index); |
157 | 4 | if (error) |
158 | 0 | return error; |
159 | 4 | } |
160 | 97 | |
161 | 97 | slot = indirect_to_ptr(root->rnode); |
162 | 97 | |
163 | 97 | height = root->height; |
164 | 97 | shift = (height-1) * RADIX_TREE_MAP_SHIFT; |
165 | 97 | |
166 | 97 | offset = 0; /* uninitialised var warning */ |
167 | 268 | while (height > 0) { |
168 | 171 | if (slot == NULL) { |
169 | 4 | /* Have to add a child node. */ |
170 | 4 | if (!(slot = radix_tree_node_alloc(root))) |
171 | 0 | return -ENOMEM; |
172 | 4 | slot->height = height; |
173 | 4 | if (node) { |
174 | 2 | rcu_assign_pointer(node->slots[offset], slot); |
175 | 2 | node->count++; |
176 | 2 | } else |
177 | 2 | rcu_assign_pointer(root->rnode, ptr_to_indirect(slot)); |
178 | 4 | } |
179 | 171 | |
180 | 171 | /* Go a level down */ |
181 | 171 | offset = (index >> shift) & RADIX_TREE_MAP_MASK; |
182 | 171 | node = slot; |
183 | 171 | slot = node->slots[offset]; |
184 | 171 | shift -= RADIX_TREE_MAP_SHIFT; |
185 | 171 | height--; |
186 | 171 | } |
187 | 97 | |
188 | 97 | if (slot != NULL) |
189 | 0 | return -EEXIST; |
190 | 97 | |
191 | 97 | if (node) { |
192 | 96 | node->count++; |
193 | 96 | rcu_assign_pointer(node->slots[offset], item); |
194 | 1 | } else { |
195 | 1 | rcu_assign_pointer(root->rnode, item); |
196 | 1 | } |
197 | 97 | |
198 | 97 | return 0; |
199 | 97 | } |
200 | | EXPORT_SYMBOL(radix_tree_insert); |
201 | | |
202 | | /* |
203 | | * is_slot == 1 : search for the slot. |
204 | | * is_slot == 0 : search for the node. |
205 | | */ |
206 | | static void *radix_tree_lookup_element(struct radix_tree_root *root, |
207 | | unsigned long index, int is_slot) |
208 | 150k | { |
209 | 150k | unsigned int height, shift; |
210 | 150k | struct radix_tree_node *node, **slot; |
211 | 150k | |
212 | 150k | node = rcu_dereference(root->rnode); |
213 | 150k | if (node == NULL) |
214 | 304 | return NULL; |
215 | 150k | |
216 | 150k | if (!radix_tree_is_indirect_ptr(node)) { |
217 | 132k | if (index > 0) |
218 | 8.08k | return NULL; |
219 | 124k | return is_slot ? (void *)&root->rnode : node; |
220 | 132k | } |
221 | 18.2k | node = indirect_to_ptr(node); |
222 | 18.2k | |
223 | 18.2k | height = node->height; |
224 | 18.2k | if (index > radix_tree_maxindex(height)) |
225 | 301 | return NULL; |
226 | 18.2k | |
227 | 17.9k | shift = (height-1) * RADIX_TREE_MAP_SHIFT; |
228 | 17.9k | |
229 | 35.8k | do { |
230 | 35.8k | slot = (struct radix_tree_node **) |
231 | 35.8k | (node->slots + ((index>>shift) & RADIX_TREE_MAP_MASK)); |
232 | 35.8k | node = rcu_dereference(*slot); |
233 | 35.8k | if (node == NULL) |
234 | 307 | return NULL; |
235 | 35.8k | |
236 | 35.5k | shift -= RADIX_TREE_MAP_SHIFT; |
237 | 35.5k | height--; |
238 | 35.5k | } while (height > 0); |
239 | 17.9k | |
240 | 17.6k | return is_slot ? (void *)slot : indirect_to_ptr(node); |
241 | 17.9k | } |
242 | | |
243 | | /** |
244 | | * radix_tree_lookup_slot - lookup a slot in a radix tree |
245 | | * @root: radix tree root |
246 | | * @index: index key |
247 | | * |
248 | | * Returns: the slot corresponding to the position @index in the |
249 | | * radix tree @root. This is useful for update-if-exists operations. |
250 | | * |
251 | | * This function can be called under rcu_read_lock iff the slot is not |
252 | | * modified by radix_tree_replace_slot, otherwise it must be called |
253 | | * exclusive from other writers. Any dereference of the slot must be done |
254 | | * using radix_tree_deref_slot. |
255 | | */ |
256 | | void **radix_tree_lookup_slot(struct radix_tree_root *root, unsigned long index) |
257 | 48 | { |
258 | 48 | return (void **)radix_tree_lookup_element(root, index, 1); |
259 | 48 | } |
260 | | EXPORT_SYMBOL(radix_tree_lookup_slot); |
261 | | |
262 | | /** |
263 | | * radix_tree_lookup - perform lookup operation on a radix tree |
264 | | * @root: radix tree root |
265 | | * @index: index key |
266 | | * |
267 | | * Lookup the item at the position @index in the radix tree @root. |
268 | | * |
269 | | * This function can be called under rcu_read_lock, however the caller |
270 | | * must manage lifetimes of leaf nodes (eg. RCU may also be used to free |
271 | | * them safely). No RCU barriers are required to access or modify the |
272 | | * returned item, however. |
273 | | */ |
274 | | void *radix_tree_lookup(struct radix_tree_root *root, unsigned long index) |
275 | 150k | { |
276 | 150k | return radix_tree_lookup_element(root, index, 0); |
277 | 150k | } |
278 | | EXPORT_SYMBOL(radix_tree_lookup); |
279 | | |
280 | | /** |
281 | | * radix_tree_next_hole - find the next hole (not-present entry) |
282 | | * @root: tree root |
283 | | * @index: index key |
284 | | * @max_scan: maximum range to search |
285 | | * |
286 | | * Search the set [index, min(index+max_scan-1, MAX_INDEX)] for the lowest |
287 | | * indexed hole. |
288 | | * |
289 | | * Returns: the index of the hole if found, otherwise returns an index |
290 | | * outside of the set specified (in which case 'return - index >= max_scan' |
291 | | * will be true). In rare cases of index wrap-around, 0 will be returned. |
292 | | * |
293 | | * radix_tree_next_hole may be called under rcu_read_lock. However, like |
294 | | * radix_tree_gang_lookup, this will not atomically search a snapshot of |
295 | | * the tree at a single point in time. For example, if a hole is created |
296 | | * at index 5, then subsequently a hole is created at index 10, |
297 | | * radix_tree_next_hole covering both indexes may return 10 if called |
298 | | * under rcu_read_lock. |
299 | | */ |
300 | | unsigned long radix_tree_next_hole(struct radix_tree_root *root, |
301 | | unsigned long index, unsigned long max_scan) |
302 | 0 | { |
303 | 0 | unsigned long i; |
304 | 0 |
|
305 | 0 | for (i = 0; i < max_scan; i++) { |
306 | 0 | if (!radix_tree_lookup(root, index)) |
307 | 0 | break; |
308 | 0 | index++; |
309 | 0 | if (index == 0) |
310 | 0 | break; |
311 | 0 | } |
312 | 0 |
|
313 | 0 | return index; |
314 | 0 | } |
315 | | EXPORT_SYMBOL(radix_tree_next_hole); |
316 | | |
317 | | /** |
318 | | * radix_tree_prev_hole - find the prev hole (not-present entry) |
319 | | * @root: tree root |
320 | | * @index: index key |
321 | | * @max_scan: maximum range to search |
322 | | * |
323 | | * Search backwards in the range [max(index-max_scan+1, 0), index] |
324 | | * for the first hole. |
325 | | * |
326 | | * Returns: the index of the hole if found, otherwise returns an index |
327 | | * outside of the set specified (in which case 'index - return >= max_scan' |
328 | | * will be true). In rare cases of wrap-around, ULONG_MAX will be returned. |
329 | | * |
330 | | * radix_tree_next_hole may be called under rcu_read_lock. However, like |
331 | | * radix_tree_gang_lookup, this will not atomically search a snapshot of |
332 | | * the tree at a single point in time. For example, if a hole is created |
333 | | * at index 10, then subsequently a hole is created at index 5, |
334 | | * radix_tree_prev_hole covering both indexes may return 5 if called under |
335 | | * rcu_read_lock. |
336 | | */ |
337 | | unsigned long radix_tree_prev_hole(struct radix_tree_root *root, |
338 | | unsigned long index, unsigned long max_scan) |
339 | 0 | { |
340 | 0 | unsigned long i; |
341 | 0 |
|
342 | 0 | for (i = 0; i < max_scan; i++) { |
343 | 0 | if (!radix_tree_lookup(root, index)) |
344 | 0 | break; |
345 | 0 | index--; |
346 | 0 | if (index == ULONG_MAX) |
347 | 0 | break; |
348 | 0 | } |
349 | 0 |
|
350 | 0 | return index; |
351 | 0 | } |
352 | | EXPORT_SYMBOL(radix_tree_prev_hole); |
353 | | |
354 | | static unsigned int |
355 | | __lookup(struct radix_tree_node *slot, void ***results, unsigned long index, |
356 | | unsigned int max_items, unsigned long *next_index) |
357 | 0 | { |
358 | 0 | unsigned int nr_found = 0; |
359 | 0 | unsigned int shift, height; |
360 | 0 | unsigned long i; |
361 | 0 |
|
362 | 0 | height = slot->height; |
363 | 0 | if (height == 0) |
364 | 0 | goto out; |
365 | 0 | shift = (height-1) * RADIX_TREE_MAP_SHIFT; |
366 | 0 |
|
367 | 0 | for ( ; height > 1; height--) { |
368 | 0 | i = (index >> shift) & RADIX_TREE_MAP_MASK; |
369 | 0 | for (;;) { |
370 | 0 | if (slot->slots[i] != NULL) |
371 | 0 | break; |
372 | 0 | index &= ~((1UL << shift) - 1); |
373 | 0 | index += 1UL << shift; |
374 | 0 | if (index == 0) |
375 | 0 | goto out; /* 32-bit wraparound */ |
376 | 0 | i++; |
377 | 0 | if (i == RADIX_TREE_MAP_SIZE) |
378 | 0 | goto out; |
379 | 0 | } |
380 | 0 |
|
381 | 0 | shift -= RADIX_TREE_MAP_SHIFT; |
382 | 0 | slot = rcu_dereference(slot->slots[i]); |
383 | 0 | if (slot == NULL) |
384 | 0 | goto out; |
385 | 0 | } |
386 | 0 |
|
387 | 0 | /* Bottom level: grab some items */ |
388 | 0 | for (i = index & RADIX_TREE_MAP_MASK; i < RADIX_TREE_MAP_SIZE; i++) { |
389 | 0 | index++; |
390 | 0 | if (slot->slots[i]) { |
391 | 0 | results[nr_found++] = &(slot->slots[i]); |
392 | 0 | if (nr_found == max_items) |
393 | 0 | goto out; |
394 | 0 | } |
395 | 0 | } |
396 | 0 | out: |
397 | 0 | *next_index = index; |
398 | 0 | return nr_found; |
399 | 0 | } |
400 | | |
401 | | /** |
402 | | * radix_tree_gang_lookup - perform multiple lookup on a radix tree |
403 | | * @root: radix tree root |
404 | | * @results: where the results of the lookup are placed |
405 | | * @first_index: start the lookup from this key |
406 | | * @max_items: place up to this many items at *results |
407 | | * |
408 | | * Performs an index-ascending scan of the tree for present items. Places |
409 | | * them at *@results and returns the number of items which were placed at |
410 | | * *@results. |
411 | | * |
412 | | * The implementation is naive. |
413 | | * |
414 | | * Like radix_tree_lookup, radix_tree_gang_lookup may be called under |
415 | | * rcu_read_lock. In this case, rather than the returned results being |
416 | | * an atomic snapshot of the tree at a single point in time, the semantics |
417 | | * of an RCU protected gang lookup are as though multiple radix_tree_lookups |
418 | | * have been issued in individual locks, and results stored in 'results'. |
419 | | */ |
420 | | unsigned int |
421 | | radix_tree_gang_lookup(struct radix_tree_root *root, void **results, |
422 | | unsigned long first_index, unsigned int max_items) |
423 | 122k | { |
424 | 122k | unsigned long max_index; |
425 | 122k | struct radix_tree_node *node; |
426 | 122k | unsigned long cur_index = first_index; |
427 | 122k | unsigned int ret; |
428 | 122k | |
429 | 122k | node = rcu_dereference(root->rnode); |
430 | 122k | if (!node) |
431 | 0 | return 0; |
432 | 122k | |
433 | 122k | if (!radix_tree_is_indirect_ptr(node)) { |
434 | 122k | if (first_index > 0) |
435 | 114k | return 0; |
436 | 8.08k | results[0] = node; |
437 | 8.08k | return 1; |
438 | 122k | } |
439 | 0 | node = indirect_to_ptr(node); |
440 | 0 |
|
441 | 0 | max_index = radix_tree_maxindex(node->height); |
442 | 0 |
|
443 | 0 | ret = 0; |
444 | 0 | while (ret < max_items) { |
445 | 0 | unsigned int nr_found, slots_found, i; |
446 | 0 | unsigned long next_index; /* Index of next search */ |
447 | 0 |
|
448 | 0 | if (cur_index > max_index) |
449 | 0 | break; |
450 | 0 | slots_found = __lookup(node, (void ***)results + ret, cur_index, |
451 | 0 | max_items - ret, &next_index); |
452 | 0 | nr_found = 0; |
453 | 0 | for (i = 0; i < slots_found; i++) { |
454 | 0 | struct radix_tree_node *slot; |
455 | 0 | slot = *(((void ***)results)[ret + i]); |
456 | 0 | if (!slot) |
457 | 0 | continue; |
458 | 0 | results[ret + nr_found] = |
459 | 0 | indirect_to_ptr(rcu_dereference(slot)); |
460 | 0 | nr_found++; |
461 | 0 | } |
462 | 0 | ret += nr_found; |
463 | 0 | if (next_index == 0) |
464 | 0 | break; |
465 | 0 | cur_index = next_index; |
466 | 0 | } |
467 | 0 |
|
468 | 0 | return ret; |
469 | 122k | } |
470 | | EXPORT_SYMBOL(radix_tree_gang_lookup); |
471 | | |
472 | | /** |
473 | | * radix_tree_gang_lookup_slot - perform multiple slot lookup on radix tree |
474 | | * @root: radix tree root |
475 | | * @results: where the results of the lookup are placed |
476 | | * @first_index: start the lookup from this key |
477 | | * @max_items: place up to this many items at *results |
478 | | * |
479 | | * Performs an index-ascending scan of the tree for present items. Places |
480 | | * their slots at *@results and returns the number of items which were |
481 | | * placed at *@results. |
482 | | * |
483 | | * The implementation is naive. |
484 | | * |
485 | | * Like radix_tree_gang_lookup as far as RCU and locking goes. Slots must |
486 | | * be dereferenced with radix_tree_deref_slot, and if using only RCU |
487 | | * protection, radix_tree_deref_slot may fail requiring a retry. |
488 | | */ |
489 | | unsigned int |
490 | | radix_tree_gang_lookup_slot(struct radix_tree_root *root, void ***results, |
491 | | unsigned long first_index, unsigned int max_items) |
492 | 0 | { |
493 | 0 | unsigned long max_index; |
494 | 0 | struct radix_tree_node *node; |
495 | 0 | unsigned long cur_index = first_index; |
496 | 0 | unsigned int ret; |
497 | 0 |
|
498 | 0 | node = rcu_dereference(root->rnode); |
499 | 0 | if (!node) |
500 | 0 | return 0; |
501 | 0 |
|
502 | 0 | if (!radix_tree_is_indirect_ptr(node)) { |
503 | 0 | if (first_index > 0) |
504 | 0 | return 0; |
505 | 0 | results[0] = (void **)&root->rnode; |
506 | 0 | return 1; |
507 | 0 | } |
508 | 0 | node = indirect_to_ptr(node); |
509 | 0 |
|
510 | 0 | max_index = radix_tree_maxindex(node->height); |
511 | 0 |
|
512 | 0 | ret = 0; |
513 | 0 | while (ret < max_items) { |
514 | 0 | unsigned int slots_found; |
515 | 0 | unsigned long next_index; /* Index of next search */ |
516 | 0 |
|
517 | 0 | if (cur_index > max_index) |
518 | 0 | break; |
519 | 0 | slots_found = __lookup(node, results + ret, cur_index, |
520 | 0 | max_items - ret, &next_index); |
521 | 0 | ret += slots_found; |
522 | 0 | if (next_index == 0) |
523 | 0 | break; |
524 | 0 | cur_index = next_index; |
525 | 0 | } |
526 | 0 |
|
527 | 0 | return ret; |
528 | 0 | } |
529 | | EXPORT_SYMBOL(radix_tree_gang_lookup_slot); |
530 | | |
531 | | /** |
532 | | * radix_tree_shrink - shrink height of a radix tree to minimal |
533 | | * @root radix tree root |
534 | | */ |
535 | | static inline void radix_tree_shrink(struct radix_tree_root *root) |
536 | 0 | { |
537 | 0 | /* try to shrink tree height */ |
538 | 0 | while (root->height > 0) { |
539 | 0 | struct radix_tree_node *to_free = root->rnode; |
540 | 0 | void *newptr; |
541 | 0 |
|
542 | 0 | BUG_ON(!radix_tree_is_indirect_ptr(to_free)); |
543 | 0 | to_free = indirect_to_ptr(to_free); |
544 | 0 |
|
545 | 0 | /* |
546 | 0 | * The candidate node has more than one child, or its child |
547 | 0 | * is not at the leftmost slot, we cannot shrink. |
548 | 0 | */ |
549 | 0 | if (to_free->count != 1) |
550 | 0 | break; |
551 | 0 | if (!to_free->slots[0]) |
552 | 0 | break; |
553 | 0 |
|
554 | 0 | /* |
555 | 0 | * We don't need rcu_assign_pointer(), since we are simply |
556 | 0 | * moving the node from one part of the tree to another: if it |
557 | 0 | * was safe to dereference the old pointer to it |
558 | 0 | * (to_free->slots[0]), it will be safe to dereference the new |
559 | 0 | * one (root->rnode) as far as dependent read barriers go. |
560 | 0 | */ |
561 | 0 | newptr = to_free->slots[0]; |
562 | 0 | if (root->height > 1) |
563 | 0 | newptr = ptr_to_indirect(newptr); |
564 | 0 | root->rnode = newptr; |
565 | 0 | root->height--; |
566 | 0 |
|
567 | 0 | /* |
568 | 0 | * We have a dilemma here. The node's slot[0] must not be |
569 | 0 | * NULLed in case there are concurrent lookups expecting to |
570 | 0 | * find the item. However if this was a bottom-level node, |
571 | 0 | * then it may be subject to the slot pointer being visible |
572 | 0 | * to callers dereferencing it. If item corresponding to |
573 | 0 | * slot[0] is subsequently deleted, these callers would expect |
574 | 0 | * their slot to become empty sooner or later. |
575 | 0 | * |
576 | 0 | * For example, lockless pagecache will look up a slot, deref |
577 | 0 | * the page pointer, and if the page is 0 refcount it means it |
578 | 0 | * was concurrently deleted from pagecache so try the deref |
579 | 0 | * again. Fortunately there is already a requirement for logic |
580 | 0 | * to retry the entire slot lookup -- the indirect pointer |
581 | 0 | * problem (replacing direct root node with an indirect pointer |
582 | 0 | * also results in a stale slot). So tag the slot as indirect |
583 | 0 | * to force callers to retry. |
584 | 0 | */ |
585 | 0 | if (root->height == 0) |
586 | 0 | *((unsigned long *)&to_free->slots[0]) |= |
587 | 0 | RADIX_TREE_INDIRECT_PTR; |
588 | 0 |
|
589 | 0 | radix_tree_node_free(root, to_free); |
590 | 0 | } |
591 | 0 | } |
592 | | |
593 | | /** |
594 | | * radix_tree_delete - delete an item from a radix tree |
595 | | * @root: radix tree root |
596 | | * @index: index key |
597 | | * |
598 | | * Remove the item at @index from the radix tree rooted at @root. |
599 | | * |
600 | | * Returns the address of the deleted item, or NULL if it was not present. |
601 | | */ |
602 | | void *radix_tree_delete(struct radix_tree_root *root, unsigned long index) |
603 | 0 | { |
604 | 0 | /* |
605 | 0 | * The radix tree path needs to be one longer than the maximum path |
606 | 0 | * since the "list" is null terminated. |
607 | 0 | */ |
608 | 0 | struct radix_tree_path path[RADIX_TREE_MAX_PATH + 1], *pathp = path; |
609 | 0 | struct radix_tree_node *slot = NULL; |
610 | 0 | struct radix_tree_node *to_free; |
611 | 0 | unsigned int height, shift; |
612 | 0 | int offset; |
613 | 0 |
|
614 | 0 | height = root->height; |
615 | 0 | if (index > radix_tree_maxindex(height)) |
616 | 0 | goto out; |
617 | 0 |
|
618 | 0 | slot = root->rnode; |
619 | 0 | if (height == 0) { |
620 | 0 | root->rnode = NULL; |
621 | 0 | goto out; |
622 | 0 | } |
623 | 0 | slot = indirect_to_ptr(slot); |
624 | 0 |
|
625 | 0 | shift = (height - 1) * RADIX_TREE_MAP_SHIFT; |
626 | 0 | pathp->node = NULL; |
627 | 0 |
|
628 | 0 | do { |
629 | 0 | if (slot == NULL) |
630 | 0 | goto out; |
631 | 0 |
|
632 | 0 | pathp++; |
633 | 0 | offset = (index >> shift) & RADIX_TREE_MAP_MASK; |
634 | 0 | pathp->offset = offset; |
635 | 0 | pathp->node = slot; |
636 | 0 | slot = slot->slots[offset]; |
637 | 0 | shift -= RADIX_TREE_MAP_SHIFT; |
638 | 0 | height--; |
639 | 0 | } while (height > 0); |
640 | 0 |
|
641 | 0 | if (slot == NULL) |
642 | 0 | goto out; |
643 | 0 |
|
644 | 0 | to_free = NULL; |
645 | 0 | /* Now free the nodes we do not need anymore */ |
646 | 0 | while (pathp->node) { |
647 | 0 | pathp->node->slots[pathp->offset] = NULL; |
648 | 0 | pathp->node->count--; |
649 | 0 | /* |
650 | 0 | * Queue the node for deferred freeing after the |
651 | 0 | * last reference to it disappears (set NULL, above). |
652 | 0 | */ |
653 | 0 | if (to_free) |
654 | 0 | radix_tree_node_free(root, to_free); |
655 | 0 |
|
656 | 0 | if (pathp->node->count) { |
657 | 0 | if (pathp->node == indirect_to_ptr(root->rnode)) |
658 | 0 | radix_tree_shrink(root); |
659 | 0 | goto out; |
660 | 0 | } |
661 | 0 |
|
662 | 0 | /* Node with zero slots in use so free it */ |
663 | 0 | to_free = pathp->node; |
664 | 0 | pathp--; |
665 | 0 |
|
666 | 0 | } |
667 | 0 | root->height = 0; |
668 | 0 | root->rnode = NULL; |
669 | 0 | if (to_free) |
670 | 0 | radix_tree_node_free(root, to_free); |
671 | 0 |
|
672 | 0 | out: |
673 | 0 | return slot; |
674 | 0 | } |
675 | | EXPORT_SYMBOL(radix_tree_delete); |
676 | | |
677 | | static void |
678 | | radix_tree_node_destroy( |
679 | | struct radix_tree_root *root, struct radix_tree_node *node, |
680 | | void (*slot_free)(void *)) |
681 | 0 | { |
682 | 0 | int i; |
683 | 0 |
|
684 | 0 | for (i = 0; i < RADIX_TREE_MAP_SIZE; i++) { |
685 | 0 | struct radix_tree_node *slot = node->slots[i]; |
686 | 0 | BUG_ON(radix_tree_is_indirect_ptr(slot)); |
687 | 0 | if (slot == NULL) |
688 | 0 | continue; |
689 | 0 | if (node->height == 1) { |
690 | 0 | if (slot_free) |
691 | 0 | slot_free(slot); |
692 | 0 | } else { |
693 | 0 | radix_tree_node_destroy(root, slot, slot_free); |
694 | 0 | } |
695 | 0 | } |
696 | 0 |
|
697 | 0 | radix_tree_node_free(root, node); |
698 | 0 | } |
699 | | |
700 | | void radix_tree_destroy( |
701 | | struct radix_tree_root *root, |
702 | | void (*slot_free)(void *)) |
703 | 0 | { |
704 | 0 | struct radix_tree_node *node = root->rnode; |
705 | 0 | if (node == NULL) |
706 | 0 | return; |
707 | 0 | if (!radix_tree_is_indirect_ptr(node)) { |
708 | 0 | if (slot_free) |
709 | 0 | slot_free(node); |
710 | 0 | } else { |
711 | 0 | node = indirect_to_ptr(node); |
712 | 0 | radix_tree_node_destroy(root, node, slot_free); |
713 | 0 | } |
714 | 0 | radix_tree_init(root); |
715 | 0 | } |
716 | | |
717 | | void radix_tree_init(struct radix_tree_root *root) |
718 | 4 | { |
719 | 4 | memset(root, 0, sizeof(*root)); |
720 | 4 | root->node_alloc = rcu_node_alloc; |
721 | 4 | root->node_free = rcu_node_free; |
722 | 4 | } |
723 | | |
724 | | void radix_tree_set_alloc_callbacks( |
725 | | struct radix_tree_root *root, |
726 | | radix_tree_alloc_fn_t *node_alloc, |
727 | | radix_tree_free_fn_t *node_free, |
728 | | void *node_alloc_free_arg) |
729 | 0 | { |
730 | 0 | root->node_alloc = node_alloc; |
731 | 0 | root->node_free = node_free; |
732 | 0 | root->node_alloc_free_arg = node_alloc_free_arg; |
733 | 0 | } |
734 | | |
735 | | static __init unsigned long __maxindex(unsigned int height) |
736 | 12 | { |
737 | 12 | unsigned int width = height * RADIX_TREE_MAP_SHIFT; |
738 | 12 | int shift = RADIX_TREE_INDEX_BITS - width; |
739 | 12 | |
740 | 12 | if (shift < 0) |
741 | 1 | return ~0UL; |
742 | 11 | if (shift >= BITS_PER_LONG) |
743 | 1 | return 0UL; |
744 | 10 | return ~0UL >> shift; |
745 | 11 | } |
746 | | |
747 | | static __init int radix_tree_init_maxindex(void) |
748 | 1 | { |
749 | 1 | unsigned int i; |
750 | 1 | |
751 | 13 | for (i = 0; i < ARRAY_SIZE(height_to_maxindex); i++) |
752 | 12 | height_to_maxindex[i] = __maxindex(i); |
753 | 1 | |
754 | 1 | return 0; |
755 | 1 | } |
756 | | /* pre-SMP just so it runs before 'normal' initcalls */ |
757 | | presmp_initcall(radix_tree_init_maxindex); |