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