Blame view
lib/radix-tree.c
62.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 |
* * 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. */ |
0a835c4f0 Reimplement IDR a... |
24 25 |
#include <linux/bitmap.h> #include <linux/bitops.h> |
e157b5559 radix-tree: add r... |
26 |
#include <linux/cpu.h> |
1da177e4c Linux-2.6.12-rc2 |
27 |
#include <linux/errno.h> |
0a835c4f0 Reimplement IDR a... |
28 29 |
#include <linux/export.h> #include <linux/idr.h> |
1da177e4c Linux-2.6.12-rc2 |
30 31 |
#include <linux/init.h> #include <linux/kernel.h> |
0a835c4f0 Reimplement IDR a... |
32 |
#include <linux/kmemleak.h> |
1da177e4c Linux-2.6.12-rc2 |
33 |
#include <linux/percpu.h> |
0a835c4f0 Reimplement IDR a... |
34 35 36 |
#include <linux/preempt.h> /* in_interrupt() */ #include <linux/radix-tree.h> #include <linux/rcupdate.h> |
1da177e4c Linux-2.6.12-rc2 |
37 |
#include <linux/slab.h> |
1da177e4c Linux-2.6.12-rc2 |
38 |
#include <linux/string.h> |
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) /* |
0a835c4f0 Reimplement IDR a... |
61 62 63 64 65 66 67 68 69 |
* The IDR does not have to be as high as the radix tree since it uses * signed integers, not unsigned longs. */ #define IDR_INDEX_BITS (8 /* CHAR_BIT */ * sizeof(int) - 1) #define IDR_MAX_PATH (DIV_ROUND_UP(IDR_INDEX_BITS, \ RADIX_TREE_MAP_SHIFT)) #define IDR_PRELOAD_SIZE (IDR_MAX_PATH * 2 - 1) /* |
7ad3d4d85 ida: Move ida_bit... |
70 71 72 73 74 75 76 77 |
* The IDA is even shorter since it uses a bitmap at the last level. */ #define IDA_INDEX_BITS (8 * sizeof(int) - 1 - ilog2(IDA_BITMAP_BITS)) #define IDA_MAX_PATH (DIV_ROUND_UP(IDA_INDEX_BITS, \ RADIX_TREE_MAP_SHIFT)) #define IDA_PRELOAD_SIZE (IDA_MAX_PATH * 2 - 1) /* |
1da177e4c Linux-2.6.12-rc2 |
78 79 80 |
* Per-cpu pool of preloaded nodes */ struct radix_tree_preload { |
2fcd9005c radix-tree: misce... |
81 |
unsigned nr; |
1293d5c5f radix-tree: Chain... |
82 |
/* nodes->parent points to next preallocated node */ |
9d2a8da00 radix-tree: repla... |
83 |
struct radix_tree_node *nodes; |
1da177e4c Linux-2.6.12-rc2 |
84 |
}; |
8cef7d57a lib: radix_tree.c... |
85 |
static DEFINE_PER_CPU(struct radix_tree_preload, radix_tree_preloads) = { 0, }; |
1da177e4c Linux-2.6.12-rc2 |
86 |
|
148deab22 radix-tree: impro... |
87 88 89 90 |
static inline struct radix_tree_node *entry_to_node(void *ptr) { return (void *)((unsigned long)ptr & ~RADIX_TREE_INTERNAL_NODE); } |
a4db4dcea radix-tree: renam... |
91 |
static inline void *node_to_entry(void *ptr) |
27d20fddc radix-tree: fix R... |
92 |
{ |
30ff46ccb radix-tree: renam... |
93 |
return (void *)((unsigned long)ptr | RADIX_TREE_INTERNAL_NODE); |
27d20fddc radix-tree: fix R... |
94 |
} |
a4db4dcea radix-tree: renam... |
95 |
#define RADIX_TREE_RETRY node_to_entry(NULL) |
afe0e395b radix-tree: fix s... |
96 |
|
db050f292 radix-tree: add m... |
97 98 |
#ifdef CONFIG_RADIX_TREE_MULTIORDER /* Sibling slots point directly to another slot in the same node */ |
35534c869 radix tree: const... |
99 100 |
static inline bool is_sibling_entry(const struct radix_tree_node *parent, void *node) |
db050f292 radix-tree: add m... |
101 |
{ |
d7b627277 radix-tree: Fix _... |
102 |
void __rcu **ptr = node; |
db050f292 radix-tree: add m... |
103 104 105 106 |
return (parent->slots <= ptr) && (ptr < parent->slots + RADIX_TREE_MAP_SIZE); } #else |
35534c869 radix tree: const... |
107 108 |
static inline bool is_sibling_entry(const struct radix_tree_node *parent, void *node) |
db050f292 radix-tree: add m... |
109 110 111 112 |
{ return false; } #endif |
d7b627277 radix-tree: Fix _... |
113 114 |
static inline unsigned long get_slot_offset(const struct radix_tree_node *parent, void __rcu **slot) |
db050f292 radix-tree: add m... |
115 116 117 |
{ return slot - parent->slots; } |
35534c869 radix tree: const... |
118 |
static unsigned int radix_tree_descend(const struct radix_tree_node *parent, |
9e85d8111 radix-tree: make ... |
119 |
struct radix_tree_node **nodep, unsigned long index) |
db050f292 radix-tree: add m... |
120 |
{ |
9e85d8111 radix-tree: make ... |
121 |
unsigned int offset = (index >> parent->shift) & RADIX_TREE_MAP_MASK; |
d7b627277 radix-tree: Fix _... |
122 |
void __rcu **entry = rcu_dereference_raw(parent->slots[offset]); |
db050f292 radix-tree: add m... |
123 124 |
#ifdef CONFIG_RADIX_TREE_MULTIORDER |
b194d16c2 radix-tree: renam... |
125 |
if (radix_tree_is_internal_node(entry)) { |
8d2c0d36d radix tree: fix s... |
126 |
if (is_sibling_entry(parent, entry)) { |
d7b627277 radix-tree: Fix _... |
127 128 |
void __rcu **sibentry; sibentry = (void __rcu **) entry_to_node(entry); |
8d2c0d36d radix tree: fix s... |
129 130 |
offset = get_slot_offset(parent, sibentry); entry = rcu_dereference_raw(*sibentry); |
db050f292 radix-tree: add m... |
131 132 133 134 135 136 137 |
} } #endif *nodep = (void *)entry; return offset; } |
35534c869 radix tree: const... |
138 |
static inline gfp_t root_gfp_mask(const struct radix_tree_root *root) |
612d6c19d [PATCH] radix-tre... |
139 140 141 |
{ return root->gfp_mask & __GFP_BITS_MASK; } |
643b52b9c radix-tree: fix s... |
142 143 144 145 146 147 148 149 150 151 152 |
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]); } |
35534c869 radix tree: const... |
153 |
static inline int tag_get(const struct radix_tree_node *node, unsigned int tag, |
643b52b9c radix-tree: fix s... |
154 155 156 157 |
int offset) { return test_bit(offset, node->tags[tag]); } |
35534c869 radix tree: const... |
158 |
static inline void root_tag_set(struct radix_tree_root *root, unsigned tag) |
643b52b9c radix-tree: fix s... |
159 |
{ |
0a835c4f0 Reimplement IDR a... |
160 |
root->gfp_mask |= (__force gfp_t)(1 << (tag + ROOT_TAG_SHIFT)); |
643b52b9c radix-tree: fix s... |
161 |
} |
2fcd9005c radix-tree: misce... |
162 |
static inline void root_tag_clear(struct radix_tree_root *root, unsigned tag) |
643b52b9c radix-tree: fix s... |
163 |
{ |
0a835c4f0 Reimplement IDR a... |
164 |
root->gfp_mask &= (__force gfp_t)~(1 << (tag + ROOT_TAG_SHIFT)); |
643b52b9c radix-tree: fix s... |
165 166 167 168 |
} static inline void root_tag_clear_all(struct radix_tree_root *root) { |
0a835c4f0 Reimplement IDR a... |
169 |
root->gfp_mask &= (1 << ROOT_TAG_SHIFT) - 1; |
643b52b9c radix-tree: fix s... |
170 |
} |
35534c869 radix tree: const... |
171 |
static inline int root_tag_get(const struct radix_tree_root *root, unsigned tag) |
643b52b9c radix-tree: fix s... |
172 |
{ |
0a835c4f0 Reimplement IDR a... |
173 |
return (__force int)root->gfp_mask & (1 << (tag + ROOT_TAG_SHIFT)); |
643b52b9c radix-tree: fix s... |
174 |
} |
35534c869 radix tree: const... |
175 |
static inline unsigned root_tags_get(const struct radix_tree_root *root) |
643b52b9c radix-tree: fix s... |
176 |
{ |
0a835c4f0 Reimplement IDR a... |
177 |
return (__force unsigned)root->gfp_mask >> ROOT_TAG_SHIFT; |
643b52b9c radix-tree: fix s... |
178 |
} |
0a835c4f0 Reimplement IDR a... |
179 |
static inline bool is_idr(const struct radix_tree_root *root) |
7b60e9ad5 radix-tree: fix m... |
180 |
{ |
0a835c4f0 Reimplement IDR a... |
181 |
return !!(root->gfp_mask & ROOT_IS_IDR); |
7b60e9ad5 radix-tree: fix m... |
182 |
} |
643b52b9c radix-tree: fix s... |
183 184 185 186 |
/* * Returns 1 if any slot in the node has this tag set. * Otherwise returns 0. */ |
35534c869 radix tree: const... |
187 188 |
static inline int any_tag_set(const struct radix_tree_node *node, unsigned int tag) |
643b52b9c radix-tree: fix s... |
189 |
{ |
2fcd9005c radix-tree: misce... |
190 |
unsigned idx; |
643b52b9c radix-tree: fix s... |
191 192 193 194 195 196 |
for (idx = 0; idx < RADIX_TREE_TAG_LONGS; idx++) { if (node->tags[tag][idx]) return 1; } return 0; } |
78c1d7848 radix-tree: intro... |
197 |
|
0a835c4f0 Reimplement IDR a... |
198 199 200 201 |
static inline void all_tag_set(struct radix_tree_node *node, unsigned int tag) { bitmap_fill(node->tags[tag], RADIX_TREE_MAP_SIZE); } |
78c1d7848 radix-tree: intro... |
202 203 204 205 206 207 208 209 210 211 212 213 |
/** * 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 |
bc412fca6 radix-tree: make ... |
214 215 |
radix_tree_find_next_bit(struct radix_tree_node *node, unsigned int tag, unsigned long offset) |
78c1d7848 radix-tree: intro... |
216 |
{ |
bc412fca6 radix-tree: make ... |
217 |
const unsigned long *addr = node->tags[tag]; |
78c1d7848 radix-tree: intro... |
218 |
|
bc412fca6 radix-tree: make ... |
219 |
if (offset < RADIX_TREE_MAP_SIZE) { |
78c1d7848 radix-tree: intro... |
220 221 222 223 224 225 226 |
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); |
bc412fca6 radix-tree: make ... |
227 |
while (offset < RADIX_TREE_MAP_SIZE) { |
78c1d7848 radix-tree: intro... |
228 229 230 231 232 233 |
tmp = *++addr; if (tmp) return __ffs(tmp) + offset; offset += BITS_PER_LONG; } } |
bc412fca6 radix-tree: make ... |
234 |
return RADIX_TREE_MAP_SIZE; |
78c1d7848 radix-tree: intro... |
235 |
} |
268f42de7 radix-tree: delet... |
236 237 238 239 |
static unsigned int iter_offset(const struct radix_tree_iter *iter) { return (iter->index >> iter_shift(iter)) & RADIX_TREE_MAP_MASK; } |
218ed7503 radix-tree: impro... |
240 241 242 243 244 245 246 |
/* * The maximum index which can be stored in a radix tree */ static inline unsigned long shift_maxindex(unsigned int shift) { return (RADIX_TREE_MAP_SIZE << shift) - 1; } |
35534c869 radix tree: const... |
247 |
static inline unsigned long node_maxindex(const struct radix_tree_node *node) |
218ed7503 radix-tree: impro... |
248 249 250 |
{ return shift_maxindex(node->shift); } |
0a835c4f0 Reimplement IDR a... |
251 252 253 254 255 256 |
static unsigned long next_index(unsigned long index, const struct radix_tree_node *node, unsigned long offset) { return (index & ~node_maxindex(node)) + (offset << node->shift); } |
0796c5832 radix-tree: fix r... |
257 |
#ifndef __KERNEL__ |
d0891265b radix-tree: remov... |
258 |
static void dump_node(struct radix_tree_node *node, unsigned long index) |
7cf19af4d radix_tree: add r... |
259 |
{ |
0796c5832 radix-tree: fix r... |
260 |
unsigned long i; |
7cf19af4d radix_tree: add r... |
261 |
|
218ed7503 radix-tree: impro... |
262 263 264 265 |
pr_debug("radix node: %p offset %d indices %lu-%lu parent %p tags %lx %lx %lx shift %d count %d exceptional %d ", node, node->offset, index, index | node_maxindex(node), node->parent, |
0796c5832 radix-tree: fix r... |
266 |
node->tags[0][0], node->tags[1][0], node->tags[2][0], |
218ed7503 radix-tree: impro... |
267 |
node->shift, node->count, node->exceptional); |
0796c5832 radix-tree: fix r... |
268 269 |
for (i = 0; i < RADIX_TREE_MAP_SIZE; i++) { |
d0891265b radix-tree: remov... |
270 271 |
unsigned long first = index | (i << node->shift); unsigned long last = first | ((1UL << node->shift) - 1); |
0796c5832 radix-tree: fix r... |
272 273 274 |
void *entry = node->slots[i]; if (!entry) continue; |
218ed7503 radix-tree: impro... |
275 276 277 278 |
if (entry == RADIX_TREE_RETRY) { pr_debug("radix retry offset %ld indices %lu-%lu parent %p ", i, first, last, node); |
b194d16c2 radix-tree: renam... |
279 |
} else if (!radix_tree_is_internal_node(entry)) { |
218ed7503 radix-tree: impro... |
280 281 282 283 284 285 286 287 |
pr_debug("radix entry %p offset %ld indices %lu-%lu parent %p ", entry, i, first, last, node); } else if (is_sibling_entry(node, entry)) { pr_debug("radix sblng %p offset %ld indices %lu-%lu parent %p val %p ", entry, i, first, last, node, *(void **)entry_to_node(entry)); |
0796c5832 radix-tree: fix r... |
288 |
} else { |
4dd6c0987 radix-tree: renam... |
289 |
dump_node(entry_to_node(entry), first); |
0796c5832 radix-tree: fix r... |
290 291 |
} } |
7cf19af4d radix_tree: add r... |
292 293 294 295 296 |
} /* For debug */ static void radix_tree_dump(struct radix_tree_root *root) { |
d0891265b radix-tree: remov... |
297 298 299 |
pr_debug("radix root: %p rnode %p tags %x ", root, root->rnode, |
0a835c4f0 Reimplement IDR a... |
300 |
root->gfp_mask >> ROOT_TAG_SHIFT); |
b194d16c2 radix-tree: renam... |
301 |
if (!radix_tree_is_internal_node(root->rnode)) |
7cf19af4d radix_tree: add r... |
302 |
return; |
4dd6c0987 radix-tree: renam... |
303 |
dump_node(entry_to_node(root->rnode), 0); |
7cf19af4d radix_tree: add r... |
304 |
} |
0a835c4f0 Reimplement IDR a... |
305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 |
static void dump_ida_node(void *entry, unsigned long index) { unsigned long i; if (!entry) return; if (radix_tree_is_internal_node(entry)) { struct radix_tree_node *node = entry_to_node(entry); pr_debug("ida node: %p offset %d indices %lu-%lu parent %p free %lx shift %d count %d ", node, node->offset, index * IDA_BITMAP_BITS, ((index | node_maxindex(node)) + 1) * IDA_BITMAP_BITS - 1, node->parent, node->tags[0][0], node->shift, node->count); for (i = 0; i < RADIX_TREE_MAP_SIZE; i++) dump_ida_node(node->slots[i], index | (i << node->shift)); |
d37cacc5a ida: Use exceptio... |
326 327 328 329 330 331 332 333 334 |
} else if (radix_tree_exceptional_entry(entry)) { pr_debug("ida excp: %p offset %d indices %lu-%lu data %lx ", entry, (int)(index & RADIX_TREE_MAP_MASK), index * IDA_BITMAP_BITS, index * IDA_BITMAP_BITS + BITS_PER_LONG - RADIX_TREE_EXCEPTIONAL_SHIFT, (unsigned long)entry >> RADIX_TREE_EXCEPTIONAL_SHIFT); |
0a835c4f0 Reimplement IDR a... |
335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 |
} else { struct ida_bitmap *bitmap = entry; pr_debug("ida btmp: %p offset %d indices %lu-%lu data", bitmap, (int)(index & RADIX_TREE_MAP_MASK), index * IDA_BITMAP_BITS, (index + 1) * IDA_BITMAP_BITS - 1); for (i = 0; i < IDA_BITMAP_LONGS; i++) pr_cont(" %lx", bitmap->bitmap[i]); pr_cont(" "); } } static void ida_dump(struct ida *ida) { struct radix_tree_root *root = &ida->ida_rt; |
7ad3d4d85 ida: Move ida_bit... |
352 353 354 |
pr_debug("ida: %p node %p free %d ", ida, root->rnode, root->gfp_mask >> ROOT_TAG_SHIFT); |
0a835c4f0 Reimplement IDR a... |
355 356 |
dump_ida_node(root->rnode, 0); } |
7cf19af4d radix_tree: add r... |
357 |
#endif |
1da177e4c Linux-2.6.12-rc2 |
358 359 360 361 362 |
/* * 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 * |
0a835c4f0 Reimplement IDR a... |
363 |
radix_tree_node_alloc(gfp_t gfp_mask, struct radix_tree_node *parent, |
d58275bc9 radix-tree: Store... |
364 |
struct radix_tree_root *root, |
e8de43407 radix-tree: ensur... |
365 366 |
unsigned int shift, unsigned int offset, unsigned int count, unsigned int exceptional) |
1da177e4c Linux-2.6.12-rc2 |
367 |
{ |
e2848a0ef radix-tree: avoid... |
368 |
struct radix_tree_node *ret = NULL; |
1da177e4c Linux-2.6.12-rc2 |
369 |
|
5e4c0d974 lib/radix-tree.c:... |
370 |
/* |
2fcd9005c radix-tree: misce... |
371 372 373 |
* 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:... |
374 |
*/ |
d0164adc8 mm, page_alloc: d... |
375 |
if (!gfpflags_allow_blocking(gfp_mask) && !in_interrupt()) { |
1da177e4c Linux-2.6.12-rc2 |
376 |
struct radix_tree_preload *rtp; |
e2848a0ef radix-tree: avoid... |
377 |
/* |
58e698af4 radix-tree: accou... |
378 |
* Even if the caller has preloaded, try to allocate from the |
05eb6e726 radix-tree: accou... |
379 380 |
* cache first for the new node to get accounted to the memory * cgroup. |
58e698af4 radix-tree: accou... |
381 382 |
*/ ret = kmem_cache_alloc(radix_tree_node_cachep, |
05eb6e726 radix-tree: accou... |
383 |
gfp_mask | __GFP_NOWARN); |
58e698af4 radix-tree: accou... |
384 385 386 387 |
if (ret) goto out; /* |
e2848a0ef radix-tree: avoid... |
388 389 390 391 |
* 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... |
392 |
rtp = this_cpu_ptr(&radix_tree_preloads); |
1da177e4c Linux-2.6.12-rc2 |
393 |
if (rtp->nr) { |
9d2a8da00 radix-tree: repla... |
394 |
ret = rtp->nodes; |
1293d5c5f radix-tree: Chain... |
395 |
rtp->nodes = ret->parent; |
1da177e4c Linux-2.6.12-rc2 |
396 397 |
rtp->nr--; } |
ce80b067d lib/radix-tree.c:... |
398 399 400 401 402 |
/* * Update the allocation stack trace as this is more useful * for debugging. */ kmemleak_update_trace(ret); |
58e698af4 radix-tree: accou... |
403 |
goto out; |
1da177e4c Linux-2.6.12-rc2 |
404 |
} |
05eb6e726 radix-tree: accou... |
405 |
ret = kmem_cache_alloc(radix_tree_node_cachep, gfp_mask); |
58e698af4 radix-tree: accou... |
406 |
out: |
b194d16c2 radix-tree: renam... |
407 |
BUG_ON(radix_tree_is_internal_node(ret)); |
e8de43407 radix-tree: ensur... |
408 |
if (ret) { |
e8de43407 radix-tree: ensur... |
409 410 411 412 |
ret->shift = shift; ret->offset = offset; ret->count = count; ret->exceptional = exceptional; |
d58275bc9 radix-tree: Store... |
413 414 |
ret->parent = parent; ret->root = root; |
e8de43407 radix-tree: ensur... |
415 |
} |
1da177e4c Linux-2.6.12-rc2 |
416 417 |
return ret; } |
7cf9c2c76 [PATCH] radix-tre... |
418 419 420 421 |
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); |
643b52b9c radix-tree: fix s... |
422 423 |
/* |
175542f57 radix-tree: add r... |
424 425 426 |
* Must only free zeroed nodes into the slab. We can be left with * non-NULL entries by radix_tree_free_nodes, so clear the entries * and tags here. |
643b52b9c radix-tree: fix s... |
427 |
*/ |
175542f57 radix-tree: add r... |
428 429 |
memset(node->slots, 0, sizeof(node->slots)); memset(node->tags, 0, sizeof(node->tags)); |
91d9c05ac radix-tree: move ... |
430 |
INIT_LIST_HEAD(&node->private_list); |
643b52b9c radix-tree: fix s... |
431 |
|
7cf9c2c76 [PATCH] radix-tre... |
432 433 |
kmem_cache_free(radix_tree_node_cachep, node); } |
1da177e4c Linux-2.6.12-rc2 |
434 435 436 |
static inline void radix_tree_node_free(struct radix_tree_node *node) { |
7cf9c2c76 [PATCH] radix-tre... |
437 |
call_rcu(&node->rcu_head, radix_tree_node_rcu_free); |
1da177e4c Linux-2.6.12-rc2 |
438 439 440 441 442 443 444 |
} /* * 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... |
445 446 |
* * To make use of this facility, the radix tree must be initialised without |
d0164adc8 mm, page_alloc: d... |
447 |
* __GFP_DIRECT_RECLAIM being passed to INIT_RADIX_TREE(). |
1da177e4c Linux-2.6.12-rc2 |
448 |
*/ |
bc9ae2247 radix-tree: must ... |
449 |
static __must_check int __radix_tree_preload(gfp_t gfp_mask, unsigned nr) |
1da177e4c Linux-2.6.12-rc2 |
450 451 452 453 |
{ struct radix_tree_preload *rtp; struct radix_tree_node *node; int ret = -ENOMEM; |
05eb6e726 radix-tree: accou... |
454 455 456 457 458 |
/* * 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 |
459 |
preempt_disable(); |
7c8e0181e mm: replace __get... |
460 |
rtp = this_cpu_ptr(&radix_tree_preloads); |
c78c66d1d radix-tree: imple... |
461 |
while (rtp->nr < nr) { |
1da177e4c Linux-2.6.12-rc2 |
462 |
preempt_enable(); |
488514d17 Remove set_migrat... |
463 |
node = kmem_cache_alloc(radix_tree_node_cachep, gfp_mask); |
1da177e4c Linux-2.6.12-rc2 |
464 465 466 |
if (node == NULL) goto out; preempt_disable(); |
7c8e0181e mm: replace __get... |
467 |
rtp = this_cpu_ptr(&radix_tree_preloads); |
c78c66d1d radix-tree: imple... |
468 |
if (rtp->nr < nr) { |
1293d5c5f radix-tree: Chain... |
469 |
node->parent = rtp->nodes; |
9d2a8da00 radix-tree: repla... |
470 471 472 |
rtp->nodes = node; rtp->nr++; } else { |
1da177e4c Linux-2.6.12-rc2 |
473 |
kmem_cache_free(radix_tree_node_cachep, node); |
9d2a8da00 radix-tree: repla... |
474 |
} |
1da177e4c Linux-2.6.12-rc2 |
475 476 477 478 479 |
} ret = 0; out: return ret; } |
5e4c0d974 lib/radix-tree.c:... |
480 481 482 483 484 485 486 487 |
/* * 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... |
488 |
* __GFP_DIRECT_RECLAIM being passed to INIT_RADIX_TREE(). |
5e4c0d974 lib/radix-tree.c:... |
489 490 491 492 |
*/ int radix_tree_preload(gfp_t gfp_mask) { /* Warn on non-sensical use... */ |
d0164adc8 mm, page_alloc: d... |
493 |
WARN_ON_ONCE(!gfpflags_allow_blocking(gfp_mask)); |
c78c66d1d radix-tree: imple... |
494 |
return __radix_tree_preload(gfp_mask, RADIX_TREE_PRELOAD_SIZE); |
5e4c0d974 lib/radix-tree.c:... |
495 |
} |
d7f0923d8 [LIB]: export rad... |
496 |
EXPORT_SYMBOL(radix_tree_preload); |
1da177e4c Linux-2.6.12-rc2 |
497 |
|
6e954b9e9 [PATCH] radix tre... |
498 |
/* |
5e4c0d974 lib/radix-tree.c:... |
499 500 501 502 503 504 |
* 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... |
505 |
if (gfpflags_allow_blocking(gfp_mask)) |
c78c66d1d radix-tree: imple... |
506 |
return __radix_tree_preload(gfp_mask, RADIX_TREE_PRELOAD_SIZE); |
5e4c0d974 lib/radix-tree.c:... |
507 508 509 510 511 |
/* Preloading doesn't help anything with this gfp mask, skip it */ preempt_disable(); return 0; } EXPORT_SYMBOL(radix_tree_maybe_preload); |
2791653a6 radix-tree: add r... |
512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 |
#ifdef CONFIG_RADIX_TREE_MULTIORDER /* * Preload with enough objects to ensure that we can split a single entry * of order @old_order into many entries of size @new_order */ int radix_tree_split_preload(unsigned int old_order, unsigned int new_order, gfp_t gfp_mask) { unsigned top = 1 << (old_order % RADIX_TREE_MAP_SHIFT); unsigned layers = (old_order / RADIX_TREE_MAP_SHIFT) - (new_order / RADIX_TREE_MAP_SHIFT); unsigned nr = 0; WARN_ON_ONCE(!gfpflags_allow_blocking(gfp_mask)); BUG_ON(new_order >= old_order); while (layers--) nr = nr * RADIX_TREE_MAP_SIZE + 1; return __radix_tree_preload(gfp_mask, top * nr); } #endif |
5e4c0d974 lib/radix-tree.c:... |
533 |
/* |
c78c66d1d radix-tree: imple... |
534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 |
* 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); } |
35534c869 radix tree: const... |
577 |
static unsigned radix_tree_load_root(const struct radix_tree_root *root, |
1456a439f radix-tree: intro... |
578 579 580 581 582 |
struct radix_tree_node **nodep, unsigned long *maxindex) { struct radix_tree_node *node = rcu_dereference_raw(root->rnode); *nodep = node; |
b194d16c2 radix-tree: renam... |
583 |
if (likely(radix_tree_is_internal_node(node))) { |
4dd6c0987 radix-tree: renam... |
584 |
node = entry_to_node(node); |
1456a439f radix-tree: intro... |
585 |
*maxindex = node_maxindex(node); |
c12e51b07 radix-tree: repla... |
586 |
return node->shift + RADIX_TREE_MAP_SHIFT; |
1456a439f radix-tree: intro... |
587 588 589 590 591 |
} *maxindex = 0; return 0; } |
1da177e4c Linux-2.6.12-rc2 |
592 593 594 |
/* * Extend a radix tree so it can store key @index. */ |
0a835c4f0 Reimplement IDR a... |
595 |
static int radix_tree_extend(struct radix_tree_root *root, gfp_t gfp, |
d0891265b radix-tree: remov... |
596 |
unsigned long index, unsigned int shift) |
1da177e4c Linux-2.6.12-rc2 |
597 |
{ |
d7b627277 radix-tree: Fix _... |
598 |
void *entry; |
d0891265b radix-tree: remov... |
599 |
unsigned int maxshift; |
1da177e4c Linux-2.6.12-rc2 |
600 |
int tag; |
d0891265b radix-tree: remov... |
601 602 603 604 |
/* 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 |
605 |
|
d7b627277 radix-tree: Fix _... |
606 607 |
entry = rcu_dereference_raw(root->rnode); if (!entry && (!is_idr(root) || root_tag_get(root, IDR_FREE))) |
1da177e4c Linux-2.6.12-rc2 |
608 |
goto out; |
1da177e4c Linux-2.6.12-rc2 |
609 |
|
1da177e4c Linux-2.6.12-rc2 |
610 |
do { |
0a835c4f0 Reimplement IDR a... |
611 |
struct radix_tree_node *node = radix_tree_node_alloc(gfp, NULL, |
d58275bc9 radix-tree: Store... |
612 |
root, shift, 0, 1, 0); |
2fcd9005c radix-tree: misce... |
613 |
if (!node) |
1da177e4c Linux-2.6.12-rc2 |
614 |
return -ENOMEM; |
0a835c4f0 Reimplement IDR a... |
615 616 617 618 619 620 621 622 623 624 625 626 |
if (is_idr(root)) { all_tag_set(node, IDR_FREE); if (!root_tag_get(root, IDR_FREE)) { tag_clear(node, IDR_FREE, 0); root_tag_set(root, IDR_FREE); } } else { /* Propagate the aggregated tag info to the new child */ for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) { if (root_tag_get(root, tag)) tag_set(node, tag, 0); } |
1da177e4c Linux-2.6.12-rc2 |
627 |
} |
d0891265b radix-tree: remov... |
628 |
BUG_ON(shift > BITS_PER_LONG); |
d7b627277 radix-tree: Fix _... |
629 630 631 |
if (radix_tree_is_internal_node(entry)) { entry_to_node(entry)->parent = node; } else if (radix_tree_exceptional_entry(entry)) { |
f7942430e lib: radix-tree: ... |
632 |
/* Moving an exceptional root->rnode to a node */ |
e8de43407 radix-tree: ensur... |
633 |
node->exceptional = 1; |
f7942430e lib: radix-tree: ... |
634 |
} |
d7b627277 radix-tree: Fix _... |
635 636 637 638 639 640 641 |
/* * entry was already in the radix tree, so we do not need * rcu_assign_pointer here */ node->slots[0] = (void __rcu *)entry; entry = node_to_entry(node); rcu_assign_pointer(root->rnode, entry); |
d0891265b radix-tree: remov... |
642 |
shift += RADIX_TREE_MAP_SHIFT; |
d0891265b radix-tree: remov... |
643 |
} while (shift <= maxshift); |
1da177e4c Linux-2.6.12-rc2 |
644 |
out: |
d0891265b radix-tree: remov... |
645 |
return maxshift + RADIX_TREE_MAP_SHIFT; |
1da177e4c Linux-2.6.12-rc2 |
646 647 648 |
} /** |
f4b109c6d lib: radix-tree: ... |
649 650 651 |
* radix_tree_shrink - shrink radix tree to minimum height * @root radix tree root */ |
0ac398ef3 radix-tree: Add r... |
652 |
static inline bool radix_tree_shrink(struct radix_tree_root *root, |
4d693d086 lib: radix-tree: ... |
653 654 |
radix_tree_update_node_t update_node, void *private) |
f4b109c6d lib: radix-tree: ... |
655 |
{ |
0ac398ef3 radix-tree: Add r... |
656 |
bool shrunk = false; |
f4b109c6d lib: radix-tree: ... |
657 |
for (;;) { |
12320d0ff radix-tree: Add r... |
658 |
struct radix_tree_node *node = rcu_dereference_raw(root->rnode); |
f4b109c6d lib: radix-tree: ... |
659 660 661 662 663 664 665 666 667 668 669 670 671 |
struct radix_tree_node *child; if (!radix_tree_is_internal_node(node)) break; node = entry_to_node(node); /* * The candidate node has more than one child, or its child * is not at the leftmost slot, or the child is a multiorder * entry, we cannot shrink. */ if (node->count != 1) break; |
12320d0ff radix-tree: Add r... |
672 |
child = rcu_dereference_raw(node->slots[0]); |
f4b109c6d lib: radix-tree: ... |
673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 |
if (!child) break; if (!radix_tree_is_internal_node(child) && node->shift) break; if (radix_tree_is_internal_node(child)) entry_to_node(child)->parent = NULL; /* * We don't need rcu_assign_pointer(), since we are simply * moving the node from one part of the tree to another: if it * was safe to dereference the old pointer to it * (node->slots[0]), it will be safe to dereference the new * one (root->rnode) as far as dependent read barriers go. */ |
d7b627277 radix-tree: Fix _... |
688 |
root->rnode = (void __rcu *)child; |
0a835c4f0 Reimplement IDR a... |
689 690 |
if (is_idr(root) && !tag_get(node, IDR_FREE, 0)) root_tag_clear(root, IDR_FREE); |
f4b109c6d lib: radix-tree: ... |
691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 |
/* * 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 * the page pointer, and if the page has 0 refcount it means it * 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. */ |
4d693d086 lib: radix-tree: ... |
710 711 |
node->count = 0; if (!radix_tree_is_internal_node(child)) { |
d7b627277 radix-tree: Fix _... |
712 |
node->slots[0] = (void __rcu *)RADIX_TREE_RETRY; |
4d693d086 lib: radix-tree: ... |
713 714 715 |
if (update_node) update_node(node, private); } |
f4b109c6d lib: radix-tree: ... |
716 |
|
ea07b862a mm: workingset: f... |
717 |
WARN_ON_ONCE(!list_empty(&node->private_list)); |
f4b109c6d lib: radix-tree: ... |
718 |
radix_tree_node_free(node); |
0ac398ef3 radix-tree: Add r... |
719 |
shrunk = true; |
f4b109c6d lib: radix-tree: ... |
720 |
} |
0ac398ef3 radix-tree: Add r... |
721 722 |
return shrunk; |
f4b109c6d lib: radix-tree: ... |
723 |
} |
0ac398ef3 radix-tree: Add r... |
724 |
static bool delete_node(struct radix_tree_root *root, |
4d693d086 lib: radix-tree: ... |
725 726 |
struct radix_tree_node *node, radix_tree_update_node_t update_node, void *private) |
f4b109c6d lib: radix-tree: ... |
727 |
{ |
0ac398ef3 radix-tree: Add r... |
728 |
bool deleted = false; |
f4b109c6d lib: radix-tree: ... |
729 730 731 732 |
do { struct radix_tree_node *parent; if (node->count) { |
12320d0ff radix-tree: Add r... |
733 734 |
if (node_to_entry(node) == rcu_dereference_raw(root->rnode)) |
0ac398ef3 radix-tree: Add r... |
735 736 737 |
deleted |= radix_tree_shrink(root, update_node, private); return deleted; |
f4b109c6d lib: radix-tree: ... |
738 739 740 741 742 743 744 |
} parent = node->parent; if (parent) { parent->slots[node->offset] = NULL; parent->count--; } else { |
0a835c4f0 Reimplement IDR a... |
745 746 747 748 749 750 |
/* * Shouldn't the tags already have all been cleared * by the caller? */ if (!is_idr(root)) root_tag_clear_all(root); |
f4b109c6d lib: radix-tree: ... |
751 752 |
root->rnode = NULL; } |
ea07b862a mm: workingset: f... |
753 |
WARN_ON_ONCE(!list_empty(&node->private_list)); |
f4b109c6d lib: radix-tree: ... |
754 |
radix_tree_node_free(node); |
0ac398ef3 radix-tree: Add r... |
755 |
deleted = true; |
f4b109c6d lib: radix-tree: ... |
756 757 758 |
node = parent; } while (node); |
0ac398ef3 radix-tree: Add r... |
759 760 |
return deleted; |
f4b109c6d lib: radix-tree: ... |
761 762 763 |
} /** |
139e56166 lib: radix_tree: ... |
764 |
* __radix_tree_create - create a slot in a radix tree |
1da177e4c Linux-2.6.12-rc2 |
765 766 |
* @root: radix tree root * @index: index key |
e61452365 radix_tree: add s... |
767 |
* @order: index occupies 2^order aligned slots |
139e56166 lib: radix_tree: ... |
768 769 |
* @nodep: returns node * @slotp: returns slot |
1da177e4c Linux-2.6.12-rc2 |
770 |
* |
139e56166 lib: radix_tree: ... |
771 772 773 774 775 776 777 778 |
* 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 |
779 |
*/ |
139e56166 lib: radix_tree: ... |
780 |
int __radix_tree_create(struct radix_tree_root *root, unsigned long index, |
e61452365 radix_tree: add s... |
781 |
unsigned order, struct radix_tree_node **nodep, |
d7b627277 radix-tree: Fix _... |
782 |
void __rcu ***slotp) |
1da177e4c Linux-2.6.12-rc2 |
783 |
{ |
89148aa40 radix-tree: tidy ... |
784 |
struct radix_tree_node *node = NULL, *child; |
d7b627277 radix-tree: Fix _... |
785 |
void __rcu **slot = (void __rcu **)&root->rnode; |
49ea6ebcd radix-tree: fix e... |
786 |
unsigned long maxindex; |
89148aa40 radix-tree: tidy ... |
787 |
unsigned int shift, offset = 0; |
49ea6ebcd radix-tree: fix e... |
788 |
unsigned long max = index | ((1UL << order) - 1); |
0a835c4f0 Reimplement IDR a... |
789 |
gfp_t gfp = root_gfp_mask(root); |
49ea6ebcd radix-tree: fix e... |
790 |
|
89148aa40 radix-tree: tidy ... |
791 |
shift = radix_tree_load_root(root, &child, &maxindex); |
1da177e4c Linux-2.6.12-rc2 |
792 793 |
/* Make sure the tree is high enough. */ |
175542f57 radix-tree: add r... |
794 795 |
if (order > 0 && max == ((1UL << order) - 1)) max++; |
49ea6ebcd radix-tree: fix e... |
796 |
if (max > maxindex) { |
0a835c4f0 Reimplement IDR a... |
797 |
int error = radix_tree_extend(root, gfp, max, shift); |
49ea6ebcd radix-tree: fix e... |
798 |
if (error < 0) |
1da177e4c Linux-2.6.12-rc2 |
799 |
return error; |
49ea6ebcd radix-tree: fix e... |
800 |
shift = error; |
12320d0ff radix-tree: Add r... |
801 |
child = rcu_dereference_raw(root->rnode); |
1da177e4c Linux-2.6.12-rc2 |
802 |
} |
e61452365 radix_tree: add s... |
803 |
while (shift > order) { |
c12e51b07 radix-tree: repla... |
804 |
shift -= RADIX_TREE_MAP_SHIFT; |
89148aa40 radix-tree: tidy ... |
805 |
if (child == NULL) { |
1da177e4c Linux-2.6.12-rc2 |
806 |
/* Have to add a child node. */ |
d58275bc9 radix-tree: Store... |
807 |
child = radix_tree_node_alloc(gfp, node, root, shift, |
e8de43407 radix-tree: ensur... |
808 |
offset, 0, 0); |
89148aa40 radix-tree: tidy ... |
809 |
if (!child) |
1da177e4c Linux-2.6.12-rc2 |
810 |
return -ENOMEM; |
89148aa40 radix-tree: tidy ... |
811 812 |
rcu_assign_pointer(*slot, node_to_entry(child)); if (node) |
1da177e4c Linux-2.6.12-rc2 |
813 |
node->count++; |
89148aa40 radix-tree: tidy ... |
814 |
} else if (!radix_tree_is_internal_node(child)) |
e61452365 radix_tree: add s... |
815 |
break; |
1da177e4c Linux-2.6.12-rc2 |
816 817 |
/* Go a level down */ |
89148aa40 radix-tree: tidy ... |
818 |
node = entry_to_node(child); |
9e85d8111 radix-tree: make ... |
819 |
offset = radix_tree_descend(node, &child, index); |
89148aa40 radix-tree: tidy ... |
820 |
slot = &node->slots[offset]; |
e61452365 radix_tree: add s... |
821 |
} |
175542f57 radix-tree: add r... |
822 823 824 825 826 827 |
if (nodep) *nodep = node; if (slotp) *slotp = slot; return 0; } |
175542f57 radix-tree: add r... |
828 829 830 831 832 833 834 835 836 837 838 839 840 841 842 |
/* * Free any nodes below this node. The tree is presumed to not need * shrinking, and any user data in the tree is presumed to not need a * destructor called on it. If we need to add a destructor, we can * add that functionality later. Note that we may not clear tags or * slots from the tree as an RCU walker may still have a pointer into * this subtree. We could replace the entries with RADIX_TREE_RETRY, * but we'll still have to clear those in rcu_free. */ static void radix_tree_free_nodes(struct radix_tree_node *node) { unsigned offset = 0; struct radix_tree_node *child = entry_to_node(node); for (;;) { |
12320d0ff radix-tree: Add r... |
843 |
void *entry = rcu_dereference_raw(child->slots[offset]); |
175542f57 radix-tree: add r... |
844 845 846 847 848 849 850 851 852 853 854 |
if (radix_tree_is_internal_node(entry) && !is_sibling_entry(child, entry)) { child = entry_to_node(entry); offset = 0; continue; } offset++; while (offset == RADIX_TREE_MAP_SIZE) { struct radix_tree_node *old = child; offset = child->offset + 1; child = child->parent; |
dd040b6f6 radix-tree: fix p... |
855 |
WARN_ON_ONCE(!list_empty(&old->private_list)); |
175542f57 radix-tree: add r... |
856 857 858 859 860 861 |
radix_tree_node_free(old); if (old == entry_to_node(node)) return; } } } |
0a835c4f0 Reimplement IDR a... |
862 |
#ifdef CONFIG_RADIX_TREE_MULTIORDER |
d7b627277 radix-tree: Fix _... |
863 864 |
static inline int insert_entries(struct radix_tree_node *node, void __rcu **slot, void *item, unsigned order, bool replace) |
175542f57 radix-tree: add r... |
865 866 867 868 869 |
{ struct radix_tree_node *child; unsigned i, n, tag, offset, tags = 0; if (node) { |
e157b5559 radix-tree: add r... |
870 871 872 873 |
if (order > node->shift) n = 1 << (order - node->shift); else n = 1; |
175542f57 radix-tree: add r... |
874 875 876 877 878 879 880 |
offset = get_slot_offset(node, slot); } else { n = 1; offset = 0; } if (n > 1) { |
e61452365 radix_tree: add s... |
881 |
offset = offset & ~(n - 1); |
89148aa40 radix-tree: tidy ... |
882 |
slot = &node->slots[offset]; |
175542f57 radix-tree: add r... |
883 884 885 886 887 888 889 890 891 892 893 |
} child = node_to_entry(slot); for (i = 0; i < n; i++) { if (slot[i]) { if (replace) { node->count--; for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) if (tag_get(node, tag, offset + i)) tags |= 1 << tag; } else |
e61452365 radix_tree: add s... |
894 895 |
return -EEXIST; } |
175542f57 radix-tree: add r... |
896 |
} |
e61452365 radix_tree: add s... |
897 |
|
175542f57 radix-tree: add r... |
898 |
for (i = 0; i < n; i++) { |
12320d0ff radix-tree: Add r... |
899 |
struct radix_tree_node *old = rcu_dereference_raw(slot[i]); |
175542f57 radix-tree: add r... |
900 |
if (i) { |
89148aa40 radix-tree: tidy ... |
901 |
rcu_assign_pointer(slot[i], child); |
175542f57 radix-tree: add r... |
902 903 904 905 906 907 908 909 |
for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) if (tags & (1 << tag)) tag_clear(node, tag, offset + i); } else { rcu_assign_pointer(slot[i], item); for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) if (tags & (1 << tag)) tag_set(node, tag, offset); |
e61452365 radix_tree: add s... |
910 |
} |
175542f57 radix-tree: add r... |
911 |
if (radix_tree_is_internal_node(old) && |
e157b5559 radix-tree: add r... |
912 913 |
!is_sibling_entry(node, old) && (old != RADIX_TREE_RETRY)) |
175542f57 radix-tree: add r... |
914 915 916 |
radix_tree_free_nodes(old); if (radix_tree_exceptional_entry(old)) node->exceptional--; |
612d6c19d [PATCH] radix-tre... |
917 |
} |
175542f57 radix-tree: add r... |
918 919 920 921 922 923 |
if (node) { node->count += n; if (radix_tree_exceptional_entry(item)) node->exceptional += n; } return n; |
139e56166 lib: radix_tree: ... |
924 |
} |
175542f57 radix-tree: add r... |
925 |
#else |
d7b627277 radix-tree: Fix _... |
926 927 |
static inline int insert_entries(struct radix_tree_node *node, void __rcu **slot, void *item, unsigned order, bool replace) |
175542f57 radix-tree: add r... |
928 929 930 931 932 933 934 935 936 937 938 939 |
{ if (*slot) return -EEXIST; rcu_assign_pointer(*slot, item); if (node) { node->count++; if (radix_tree_exceptional_entry(item)) node->exceptional++; } return 1; } #endif |
139e56166 lib: radix_tree: ... |
940 941 |
/** |
e61452365 radix_tree: add s... |
942 |
* __radix_tree_insert - insert into a radix tree |
139e56166 lib: radix_tree: ... |
943 944 |
* @root: radix tree root * @index: index key |
e61452365 radix_tree: add s... |
945 |
* @order: key covers the 2^order indices around index |
139e56166 lib: radix_tree: ... |
946 947 948 949 |
* @item: item to insert * * Insert an item into the radix tree at position @index. */ |
e61452365 radix_tree: add s... |
950 951 |
int __radix_tree_insert(struct radix_tree_root *root, unsigned long index, unsigned order, void *item) |
139e56166 lib: radix_tree: ... |
952 953 |
{ struct radix_tree_node *node; |
d7b627277 radix-tree: Fix _... |
954 |
void __rcu **slot; |
139e56166 lib: radix_tree: ... |
955 |
int error; |
b194d16c2 radix-tree: renam... |
956 |
BUG_ON(radix_tree_is_internal_node(item)); |
139e56166 lib: radix_tree: ... |
957 |
|
e61452365 radix_tree: add s... |
958 |
error = __radix_tree_create(root, index, order, &node, &slot); |
139e56166 lib: radix_tree: ... |
959 960 |
if (error) return error; |
175542f57 radix-tree: add r... |
961 962 963 964 |
error = insert_entries(node, slot, item, order, false); if (error < 0) return error; |
201b6264f [PATCH] radix-tre... |
965 |
|
612d6c19d [PATCH] radix-tre... |
966 |
if (node) { |
7b60e9ad5 radix-tree: fix m... |
967 |
unsigned offset = get_slot_offset(node, slot); |
7b60e9ad5 radix-tree: fix m... |
968 969 970 |
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... |
971 |
} else { |
7b60e9ad5 radix-tree: fix m... |
972 |
BUG_ON(root_tags_get(root)); |
612d6c19d [PATCH] radix-tre... |
973 |
} |
1da177e4c Linux-2.6.12-rc2 |
974 |
|
1da177e4c Linux-2.6.12-rc2 |
975 976 |
return 0; } |
e61452365 radix_tree: add s... |
977 |
EXPORT_SYMBOL(__radix_tree_insert); |
1da177e4c Linux-2.6.12-rc2 |
978 |
|
139e56166 lib: radix_tree: ... |
979 980 981 982 983 984 985 986 987 988 989 990 991 |
/** * __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... |
992 |
*/ |
35534c869 radix tree: const... |
993 994 |
void *__radix_tree_lookup(const struct radix_tree_root *root, unsigned long index, struct radix_tree_node **nodep, |
d7b627277 radix-tree: Fix _... |
995 |
void __rcu ***slotp) |
1da177e4c Linux-2.6.12-rc2 |
996 |
{ |
139e56166 lib: radix_tree: ... |
997 |
struct radix_tree_node *node, *parent; |
858299544 radix-tree: rewri... |
998 |
unsigned long maxindex; |
d7b627277 radix-tree: Fix _... |
999 |
void __rcu **slot; |
612d6c19d [PATCH] radix-tre... |
1000 |
|
858299544 radix-tree: rewri... |
1001 1002 |
restart: parent = NULL; |
d7b627277 radix-tree: Fix _... |
1003 |
slot = (void __rcu **)&root->rnode; |
9e85d8111 radix-tree: make ... |
1004 |
radix_tree_load_root(root, &node, &maxindex); |
858299544 radix-tree: rewri... |
1005 |
if (index > maxindex) |
1da177e4c Linux-2.6.12-rc2 |
1006 |
return NULL; |
b194d16c2 radix-tree: renam... |
1007 |
while (radix_tree_is_internal_node(node)) { |
858299544 radix-tree: rewri... |
1008 |
unsigned offset; |
1da177e4c Linux-2.6.12-rc2 |
1009 |
|
858299544 radix-tree: rewri... |
1010 1011 |
if (node == RADIX_TREE_RETRY) goto restart; |
4dd6c0987 radix-tree: renam... |
1012 |
parent = entry_to_node(node); |
9e85d8111 radix-tree: make ... |
1013 |
offset = radix_tree_descend(parent, &node, index); |
858299544 radix-tree: rewri... |
1014 1015 |
slot = parent->slots + offset; } |
1da177e4c Linux-2.6.12-rc2 |
1016 |
|
139e56166 lib: radix_tree: ... |
1017 1018 1019 1020 1021 |
if (nodep) *nodep = parent; if (slotp) *slotp = slot; return node; |
b72b71c6c lib: do code opti... |
1022 1023 1024 1025 1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 1036 |
} /** * 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. */ |
d7b627277 radix-tree: Fix _... |
1037 |
void __rcu **radix_tree_lookup_slot(const struct radix_tree_root *root, |
35534c869 radix tree: const... |
1038 |
unsigned long index) |
b72b71c6c lib: do code opti... |
1039 |
{ |
d7b627277 radix-tree: Fix _... |
1040 |
void __rcu **slot; |
139e56166 lib: radix_tree: ... |
1041 1042 1043 1044 |
if (!__radix_tree_lookup(root, index, NULL, &slot)) return NULL; return slot; |
a43313668 [PATCH] reiser4: ... |
1045 |
} |
a43313668 [PATCH] reiser4: ... |
1046 1047 1048 1049 1050 1051 1052 1053 |
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... |
1054 1055 1056 1057 1058 |
* * 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: ... |
1059 |
*/ |
35534c869 radix tree: const... |
1060 |
void *radix_tree_lookup(const struct radix_tree_root *root, unsigned long index) |
a43313668 [PATCH] reiser4: ... |
1061 |
{ |
139e56166 lib: radix_tree: ... |
1062 |
return __radix_tree_lookup(root, index, NULL, NULL); |
1da177e4c Linux-2.6.12-rc2 |
1063 1064 |
} EXPORT_SYMBOL(radix_tree_lookup); |
0a835c4f0 Reimplement IDR a... |
1065 |
static inline void replace_sibling_entries(struct radix_tree_node *node, |
d7b627277 radix-tree: Fix _... |
1066 |
void __rcu **slot, int count, int exceptional) |
a90eb3a2a radix-tree: fix r... |
1067 |
{ |
a90eb3a2a radix-tree: fix r... |
1068 1069 |
#ifdef CONFIG_RADIX_TREE_MULTIORDER void *ptr = node_to_entry(slot); |
0a835c4f0 Reimplement IDR a... |
1070 |
unsigned offset = get_slot_offset(node, slot) + 1; |
a90eb3a2a radix-tree: fix r... |
1071 |
|
0a835c4f0 Reimplement IDR a... |
1072 |
while (offset < RADIX_TREE_MAP_SIZE) { |
12320d0ff radix-tree: Add r... |
1073 |
if (rcu_dereference_raw(node->slots[offset]) != ptr) |
a90eb3a2a radix-tree: fix r... |
1074 |
break; |
0a835c4f0 Reimplement IDR a... |
1075 1076 1077 1078 1079 1080 |
if (count < 0) { node->slots[offset] = NULL; node->count--; } node->exceptional += exceptional; offset++; |
a90eb3a2a radix-tree: fix r... |
1081 1082 |
} #endif |
a90eb3a2a radix-tree: fix r... |
1083 |
} |
d7b627277 radix-tree: Fix _... |
1084 1085 |
static void replace_slot(void __rcu **slot, void *item, struct radix_tree_node *node, int count, int exceptional) |
f7942430e lib: radix-tree: ... |
1086 |
{ |
0a835c4f0 Reimplement IDR a... |
1087 1088 |
if (WARN_ON_ONCE(radix_tree_is_internal_node(item))) return; |
f7942430e lib: radix-tree: ... |
1089 |
|
0a835c4f0 Reimplement IDR a... |
1090 |
if (node && (count || exceptional)) { |
f4b109c6d lib: radix-tree: ... |
1091 |
node->count += count; |
0a835c4f0 Reimplement IDR a... |
1092 1093 |
node->exceptional += exceptional; replace_sibling_entries(node, slot, count, exceptional); |
f4b109c6d lib: radix-tree: ... |
1094 |
} |
f7942430e lib: radix-tree: ... |
1095 1096 1097 |
rcu_assign_pointer(*slot, item); } |
0a835c4f0 Reimplement IDR a... |
1098 1099 1100 |
static bool node_tag_get(const struct radix_tree_root *root, const struct radix_tree_node *node, unsigned int tag, unsigned int offset) |
a90eb3a2a radix-tree: fix r... |
1101 |
{ |
0a835c4f0 Reimplement IDR a... |
1102 1103 1104 1105 |
if (node) return tag_get(node, tag, offset); return root_tag_get(root, tag); } |
a90eb3a2a radix-tree: fix r... |
1106 |
|
0a835c4f0 Reimplement IDR a... |
1107 1108 1109 1110 1111 1112 1113 1114 |
/* * IDR users want to be able to store NULL in the tree, so if the slot isn't * free, don't adjust the count, even if it's transitioning between NULL and * non-NULL. For the IDA, we mark slots as being IDR_FREE while they still * have empty bits, but it only stores NULL in slots when they're being * deleted. */ static int calculate_count(struct radix_tree_root *root, |
d7b627277 radix-tree: Fix _... |
1115 |
struct radix_tree_node *node, void __rcu **slot, |
0a835c4f0 Reimplement IDR a... |
1116 1117 1118 1119 1120 1121 1122 1123 1124 |
void *item, void *old) { if (is_idr(root)) { unsigned offset = get_slot_offset(node, slot); bool free = node_tag_get(root, node, IDR_FREE, offset); if (!free) return 0; if (!old) return 1; |
a90eb3a2a radix-tree: fix r... |
1125 |
} |
0a835c4f0 Reimplement IDR a... |
1126 |
return !!item - !!old; |
a90eb3a2a radix-tree: fix r... |
1127 |
} |
f7942430e lib: radix-tree: ... |
1128 |
/** |
6d75f366b lib: radix-tree: ... |
1129 |
* __radix_tree_replace - replace item in a slot |
4d693d086 lib: radix-tree: ... |
1130 1131 1132 1133 1134 1135 |
* @root: radix tree root * @node: pointer to tree node * @slot: pointer to slot in @node * @item: new item to store in the slot. * @update_node: callback for changing leaf nodes * @private: private data to pass to @update_node |
6d75f366b lib: radix-tree: ... |
1136 1137 1138 1139 1140 1141 |
* * For use with __radix_tree_lookup(). Caller must hold tree write locked * across slot lookup and replacement. */ void __radix_tree_replace(struct radix_tree_root *root, struct radix_tree_node *node, |
d7b627277 radix-tree: Fix _... |
1142 |
void __rcu **slot, void *item, |
4d693d086 lib: radix-tree: ... |
1143 |
radix_tree_update_node_t update_node, void *private) |
6d75f366b lib: radix-tree: ... |
1144 |
{ |
0a835c4f0 Reimplement IDR a... |
1145 1146 1147 1148 |
void *old = rcu_dereference_raw(*slot); int exceptional = !!radix_tree_exceptional_entry(item) - !!radix_tree_exceptional_entry(old); int count = calculate_count(root, node, slot, item, old); |
6d75f366b lib: radix-tree: ... |
1149 |
/* |
f4b109c6d lib: radix-tree: ... |
1150 1151 1152 |
* This function supports replacing exceptional entries and * deleting entries, but that needs accounting against the * node unless the slot is root->rnode. |
6d75f366b lib: radix-tree: ... |
1153 |
*/ |
d7b627277 radix-tree: Fix _... |
1154 |
WARN_ON_ONCE(!node && (slot != (void __rcu **)&root->rnode) && |
0a835c4f0 Reimplement IDR a... |
1155 1156 |
(count || exceptional)); replace_slot(slot, item, node, count, exceptional); |
f4b109c6d lib: radix-tree: ... |
1157 |
|
4d693d086 lib: radix-tree: ... |
1158 1159 1160 1161 1162 1163 1164 |
if (!node) return; if (update_node) update_node(node, private); delete_node(root, node, update_node, private); |
6d75f366b lib: radix-tree: ... |
1165 1166 1167 1168 1169 1170 1171 1172 1173 1174 1175 1176 1177 1178 |
} /** * radix_tree_replace_slot - replace item in a slot * @root: radix tree root * @slot: pointer to slot * @item: new item to store in the slot. * * For use with radix_tree_lookup_slot(), radix_tree_gang_lookup_slot(), * radix_tree_gang_lookup_tag_slot(). Caller must hold tree write locked * across slot lookup and replacement. * * NOTE: This cannot be used to switch between non-entries (empty slots), * regular entries, and exceptional entries, as that requires accounting |
f4b109c6d lib: radix-tree: ... |
1179 |
* inside the radix tree node. When switching from one type of entry or |
e157b5559 radix-tree: add r... |
1180 1181 |
* deleting, use __radix_tree_lookup() and __radix_tree_replace() or * radix_tree_iter_replace(). |
6d75f366b lib: radix-tree: ... |
1182 1183 |
*/ void radix_tree_replace_slot(struct radix_tree_root *root, |
d7b627277 radix-tree: Fix _... |
1184 |
void __rcu **slot, void *item) |
6d75f366b lib: radix-tree: ... |
1185 |
{ |
0a835c4f0 Reimplement IDR a... |
1186 |
__radix_tree_replace(root, NULL, slot, item, NULL, NULL); |
6d75f366b lib: radix-tree: ... |
1187 |
} |
10257d719 EXPORT_SYMBOL rad... |
1188 |
EXPORT_SYMBOL(radix_tree_replace_slot); |
6d75f366b lib: radix-tree: ... |
1189 |
|
e157b5559 radix-tree: add r... |
1190 1191 1192 1193 1194 1195 1196 1197 1198 1199 |
/** * radix_tree_iter_replace - replace item in a slot * @root: radix tree root * @slot: pointer to slot * @item: new item to store in the slot. * * For use with radix_tree_split() and radix_tree_for_each_slot(). * Caller must hold tree write locked across split and replacement. */ void radix_tree_iter_replace(struct radix_tree_root *root, |
d7b627277 radix-tree: Fix _... |
1200 1201 |
const struct radix_tree_iter *iter, void __rcu **slot, void *item) |
e157b5559 radix-tree: add r... |
1202 1203 1204 |
{ __radix_tree_replace(root, iter->node, slot, item, NULL, NULL); } |
175542f57 radix-tree: add r... |
1205 1206 1207 1208 1209 1210 1211 1212 1213 1214 1215 1216 1217 1218 1219 1220 1221 1222 1223 |
#ifdef CONFIG_RADIX_TREE_MULTIORDER /** * radix_tree_join - replace multiple entries with one multiorder entry * @root: radix tree root * @index: an index inside the new entry * @order: order of the new entry * @item: new entry * * Call this function to replace several entries with one larger entry. * The existing entries are presumed to not need freeing as a result of * this call. * * The replacement entry will have all the tags set on it that were set * on any of the entries it is replacing. */ int radix_tree_join(struct radix_tree_root *root, unsigned long index, unsigned order, void *item) { struct radix_tree_node *node; |
d7b627277 radix-tree: Fix _... |
1224 |
void __rcu **slot; |
175542f57 radix-tree: add r... |
1225 1226 1227 1228 1229 1230 1231 1232 1233 1234 1235 1236 |
int error; BUG_ON(radix_tree_is_internal_node(item)); error = __radix_tree_create(root, index, order, &node, &slot); if (!error) error = insert_entries(node, slot, item, order, true); if (error > 0) error = 0; return error; } |
e157b5559 radix-tree: add r... |
1237 1238 1239 1240 1241 1242 1243 1244 1245 1246 1247 1248 1249 1250 1251 1252 1253 1254 1255 1256 1257 1258 |
/** * radix_tree_split - Split an entry into smaller entries * @root: radix tree root * @index: An index within the large entry * @order: Order of new entries * * Call this function as the first step in replacing a multiorder entry * with several entries of lower order. After this function returns, * loop over the relevant portion of the tree using radix_tree_for_each_slot() * and call radix_tree_iter_replace() to set up each new entry. * * The tags from this entry are replicated to all the new entries. * * The radix tree should be locked against modification during the entire * replacement operation. Lock-free lookups will see RADIX_TREE_RETRY which * should prompt RCU walkers to restart the lookup from the root. */ int radix_tree_split(struct radix_tree_root *root, unsigned long index, unsigned order) { struct radix_tree_node *parent, *node, *child; |
d7b627277 radix-tree: Fix _... |
1259 |
void __rcu **slot; |
e157b5559 radix-tree: add r... |
1260 1261 |
unsigned int offset, end; unsigned n, tag, tags = 0; |
0a835c4f0 Reimplement IDR a... |
1262 |
gfp_t gfp = root_gfp_mask(root); |
e157b5559 radix-tree: add r... |
1263 1264 1265 1266 1267 1268 1269 1270 1271 1272 1273 1274 1275 |
if (!__radix_tree_lookup(root, index, &parent, &slot)) return -ENOENT; if (!parent) return -ENOENT; offset = get_slot_offset(parent, slot); for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) if (tag_get(parent, tag, offset)) tags |= 1 << tag; for (end = offset + 1; end < RADIX_TREE_MAP_SIZE; end++) { |
12320d0ff radix-tree: Add r... |
1276 1277 |
if (!is_sibling_entry(parent, rcu_dereference_raw(parent->slots[end]))) |
e157b5559 radix-tree: add r... |
1278 1279 1280 1281 1282 1283 1284 1285 1286 1287 1288 1289 1290 1291 1292 1293 1294 1295 1296 1297 1298 1299 1300 |
break; for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) if (tags & (1 << tag)) tag_set(parent, tag, end); /* rcu_assign_pointer ensures tags are set before RETRY */ rcu_assign_pointer(parent->slots[end], RADIX_TREE_RETRY); } rcu_assign_pointer(parent->slots[offset], RADIX_TREE_RETRY); parent->exceptional -= (end - offset); if (order == parent->shift) return 0; if (order > parent->shift) { while (offset < end) offset += insert_entries(parent, &parent->slots[offset], RADIX_TREE_RETRY, order, true); return 0; } node = parent; for (;;) { if (node->shift > order) { |
d58275bc9 radix-tree: Store... |
1301 |
child = radix_tree_node_alloc(gfp, node, root, |
e8de43407 radix-tree: ensur... |
1302 1303 |
node->shift - RADIX_TREE_MAP_SHIFT, offset, 0, 0); |
e157b5559 radix-tree: add r... |
1304 1305 |
if (!child) goto nomem; |
e157b5559 radix-tree: add r... |
1306 1307 |
if (node != parent) { node->count++; |
12320d0ff radix-tree: Add r... |
1308 1309 |
rcu_assign_pointer(node->slots[offset], node_to_entry(child)); |
e157b5559 radix-tree: add r... |
1310 1311 1312 1313 1314 1315 1316 1317 1318 1319 1320 1321 1322 1323 1324 1325 1326 1327 1328 1329 1330 1331 1332 1333 1334 1335 1336 1337 1338 1339 1340 1341 1342 1343 1344 1345 1346 1347 1348 |
for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) if (tags & (1 << tag)) tag_set(node, tag, offset); } node = child; offset = 0; continue; } n = insert_entries(node, &node->slots[offset], RADIX_TREE_RETRY, order, false); BUG_ON(n > RADIX_TREE_MAP_SIZE); for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) if (tags & (1 << tag)) tag_set(node, tag, offset); offset += n; while (offset == RADIX_TREE_MAP_SIZE) { if (node == parent) break; offset = node->offset; child = node; node = node->parent; rcu_assign_pointer(node->slots[offset], node_to_entry(child)); offset++; } if ((node == parent) && (offset == end)) return 0; } nomem: /* Shouldn't happen; did user forget to preload? */ /* TODO: free all the allocated nodes */ WARN_ON(1); return -ENOMEM; } |
175542f57 radix-tree: add r... |
1349 |
#endif |
30b888ba9 radix-tree: Add r... |
1350 1351 1352 1353 1354 1355 1356 1357 1358 1359 1360 1361 1362 1363 1364 |
static void node_tag_set(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_set(node, tag, offset); offset = node->offset; node = node->parent; } if (!root_tag_get(root, tag)) root_tag_set(root, tag); } |
1da177e4c Linux-2.6.12-rc2 |
1365 1366 1367 1368 |
/** * radix_tree_tag_set - set a tag on a radix tree node * @root: radix tree root * @index: index key |
2fcd9005c radix-tree: misce... |
1369 |
* @tag: tag index |
1da177e4c Linux-2.6.12-rc2 |
1370 |
* |
daff89f32 [PATCH] radix-tre... |
1371 1372 |
* 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 |
1373 1374 |
* the root all the way down to the leaf node. * |
2fcd9005c radix-tree: misce... |
1375 |
* Returns the address of the tagged item. Setting a tag on a not-present |
1da177e4c Linux-2.6.12-rc2 |
1376 1377 1378 |
* item is a bug. */ void *radix_tree_tag_set(struct radix_tree_root *root, |
daff89f32 [PATCH] radix-tre... |
1379 |
unsigned long index, unsigned int tag) |
1da177e4c Linux-2.6.12-rc2 |
1380 |
{ |
fb969909d radix-tree: rewri... |
1381 1382 |
struct radix_tree_node *node, *parent; unsigned long maxindex; |
1da177e4c Linux-2.6.12-rc2 |
1383 |
|
9e85d8111 radix-tree: make ... |
1384 |
radix_tree_load_root(root, &node, &maxindex); |
fb969909d radix-tree: rewri... |
1385 |
BUG_ON(index > maxindex); |
1da177e4c Linux-2.6.12-rc2 |
1386 |
|
b194d16c2 radix-tree: renam... |
1387 |
while (radix_tree_is_internal_node(node)) { |
fb969909d radix-tree: rewri... |
1388 |
unsigned offset; |
1da177e4c Linux-2.6.12-rc2 |
1389 |
|
4dd6c0987 radix-tree: renam... |
1390 |
parent = entry_to_node(node); |
9e85d8111 radix-tree: make ... |
1391 |
offset = radix_tree_descend(parent, &node, index); |
fb969909d radix-tree: rewri... |
1392 1393 1394 1395 |
BUG_ON(!node); if (!tag_get(parent, tag, offset)) tag_set(parent, tag, offset); |
1da177e4c Linux-2.6.12-rc2 |
1396 |
} |
612d6c19d [PATCH] radix-tre... |
1397 |
/* set the root's tag bit */ |
fb969909d radix-tree: rewri... |
1398 |
if (!root_tag_get(root, tag)) |
612d6c19d [PATCH] radix-tre... |
1399 |
root_tag_set(root, tag); |
fb969909d radix-tree: rewri... |
1400 |
return node; |
1da177e4c Linux-2.6.12-rc2 |
1401 1402 |
} EXPORT_SYMBOL(radix_tree_tag_set); |
30b888ba9 radix-tree: Add r... |
1403 1404 1405 1406 1407 1408 1409 1410 1411 1412 1413 |
/** * radix_tree_iter_tag_set - set a tag on the current iterator entry * @root: radix tree root * @iter: iterator state * @tag: tag to set */ void radix_tree_iter_tag_set(struct radix_tree_root *root, const struct radix_tree_iter *iter, unsigned int tag) { node_tag_set(root, iter->node, tag, iter_offset(iter)); } |
d604c3245 radix-tree: intro... |
1414 1415 1416 1417 1418 1419 1420 1421 1422 1423 1424 1425 1426 1427 1428 1429 1430 1431 1432 |
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); } |
268f42de7 radix-tree: delet... |
1433 |
/** |
1da177e4c Linux-2.6.12-rc2 |
1434 1435 1436 |
* radix_tree_tag_clear - clear a tag on a radix tree node * @root: radix tree root * @index: index key |
2fcd9005c radix-tree: misce... |
1437 |
* @tag: tag index |
1da177e4c Linux-2.6.12-rc2 |
1438 |
* |
daff89f32 [PATCH] radix-tre... |
1439 |
* Clear the search tag (which must be < RADIX_TREE_MAX_TAGS) |
2fcd9005c radix-tree: misce... |
1440 1441 |
* 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 |
1442 1443 1444 1445 1446 1447 |
* 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... |
1448 |
unsigned long index, unsigned int tag) |
1da177e4c Linux-2.6.12-rc2 |
1449 |
{ |
00f47b581 radix-tree: rewri... |
1450 1451 |
struct radix_tree_node *node, *parent; unsigned long maxindex; |
e2bdb933a radix_tree: take ... |
1452 |
int uninitialized_var(offset); |
1da177e4c Linux-2.6.12-rc2 |
1453 |
|
9e85d8111 radix-tree: make ... |
1454 |
radix_tree_load_root(root, &node, &maxindex); |
00f47b581 radix-tree: rewri... |
1455 1456 |
if (index > maxindex) return NULL; |
1da177e4c Linux-2.6.12-rc2 |
1457 |
|
00f47b581 radix-tree: rewri... |
1458 |
parent = NULL; |
1da177e4c Linux-2.6.12-rc2 |
1459 |
|
b194d16c2 radix-tree: renam... |
1460 |
while (radix_tree_is_internal_node(node)) { |
4dd6c0987 radix-tree: renam... |
1461 |
parent = entry_to_node(node); |
9e85d8111 radix-tree: make ... |
1462 |
offset = radix_tree_descend(parent, &node, index); |
1da177e4c Linux-2.6.12-rc2 |
1463 |
} |
d604c3245 radix-tree: intro... |
1464 1465 |
if (node) node_tag_clear(root, parent, tag, offset); |
1da177e4c Linux-2.6.12-rc2 |
1466 |
|
00f47b581 radix-tree: rewri... |
1467 |
return node; |
1da177e4c Linux-2.6.12-rc2 |
1468 1469 |
} EXPORT_SYMBOL(radix_tree_tag_clear); |
1da177e4c Linux-2.6.12-rc2 |
1470 |
/** |
30b888ba9 radix-tree: Add r... |
1471 1472 1473 1474 1475 1476 1477 1478 1479 1480 1481 1482 |
* radix_tree_iter_tag_clear - clear a tag on the current iterator entry * @root: radix tree root * @iter: iterator state * @tag: tag to clear */ void radix_tree_iter_tag_clear(struct radix_tree_root *root, const struct radix_tree_iter *iter, unsigned int tag) { node_tag_clear(root, iter->node, tag, iter_offset(iter)); } /** |
32605a181 [PATCH] radix_tag... |
1483 1484 1485 |
* radix_tree_tag_get - get a tag on a radix tree node * @root: radix tree root * @index: index key |
2fcd9005c radix-tree: misce... |
1486 |
* @tag: tag index (< RADIX_TREE_MAX_TAGS) |
1da177e4c Linux-2.6.12-rc2 |
1487 |
* |
32605a181 [PATCH] radix_tag... |
1488 |
* Return values: |
1da177e4c Linux-2.6.12-rc2 |
1489 |
* |
612d6c19d [PATCH] radix-tre... |
1490 1491 |
* 0: tag not present or not set * 1: tag set |
ce82653d6 radix_tree_tag_ge... |
1492 1493 1494 1495 |
* * 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 |
1496 |
*/ |
35534c869 radix tree: const... |
1497 |
int radix_tree_tag_get(const struct radix_tree_root *root, |
daff89f32 [PATCH] radix-tre... |
1498 |
unsigned long index, unsigned int tag) |
1da177e4c Linux-2.6.12-rc2 |
1499 |
{ |
4589ba6d0 radix-tree: rewri... |
1500 1501 |
struct radix_tree_node *node, *parent; unsigned long maxindex; |
1da177e4c Linux-2.6.12-rc2 |
1502 |
|
612d6c19d [PATCH] radix-tre... |
1503 1504 |
if (!root_tag_get(root, tag)) return 0; |
9e85d8111 radix-tree: make ... |
1505 |
radix_tree_load_root(root, &node, &maxindex); |
4589ba6d0 radix-tree: rewri... |
1506 1507 |
if (index > maxindex) return 0; |
7cf9c2c76 [PATCH] radix-tre... |
1508 |
|
b194d16c2 radix-tree: renam... |
1509 |
while (radix_tree_is_internal_node(node)) { |
9e85d8111 radix-tree: make ... |
1510 |
unsigned offset; |
1da177e4c Linux-2.6.12-rc2 |
1511 |
|
4dd6c0987 radix-tree: renam... |
1512 |
parent = entry_to_node(node); |
9e85d8111 radix-tree: make ... |
1513 |
offset = radix_tree_descend(parent, &node, index); |
1da177e4c Linux-2.6.12-rc2 |
1514 |
|
4589ba6d0 radix-tree: rewri... |
1515 |
if (!tag_get(parent, tag, offset)) |
3fa36acbc radix_tree: clean... |
1516 |
return 0; |
4589ba6d0 radix-tree: rewri... |
1517 1518 |
if (node == RADIX_TREE_RETRY) break; |
1da177e4c Linux-2.6.12-rc2 |
1519 |
} |
4589ba6d0 radix-tree: rewri... |
1520 1521 |
return 1; |
1da177e4c Linux-2.6.12-rc2 |
1522 1523 |
} EXPORT_SYMBOL(radix_tree_tag_get); |
1da177e4c Linux-2.6.12-rc2 |
1524 |
|
21ef53393 radix-tree: add s... |
1525 1526 1527 1528 1529 1530 1531 |
static inline void __set_iter_shift(struct radix_tree_iter *iter, unsigned int shift) { #ifdef CONFIG_RADIX_TREE_MULTIORDER iter->shift = shift; #endif } |
148deab22 radix-tree: impro... |
1532 1533 1534 1535 1536 1537 1538 |
/* Construct iter->tags bit-mask from node->tags[tag] array */ static void set_iter_tags(struct radix_tree_iter *iter, struct radix_tree_node *node, unsigned offset, unsigned tag) { unsigned tag_long = offset / BITS_PER_LONG; unsigned tag_bit = offset % BITS_PER_LONG; |
0a835c4f0 Reimplement IDR a... |
1539 1540 1541 1542 |
if (!node) { iter->tags = 1; return; } |
148deab22 radix-tree: impro... |
1543 1544 1545 1546 1547 1548 1549 1550 1551 1552 1553 1554 1555 1556 |
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 = __radix_tree_iter_add(iter, BITS_PER_LONG); } } #ifdef CONFIG_RADIX_TREE_MULTIORDER |
d7b627277 radix-tree: Fix _... |
1557 1558 |
static void __rcu **skip_siblings(struct radix_tree_node **nodep, void __rcu **slot, struct radix_tree_iter *iter) |
148deab22 radix-tree: impro... |
1559 |
{ |
148deab22 radix-tree: impro... |
1560 1561 |
while (iter->index < iter->next_index) { *nodep = rcu_dereference_raw(*slot); |
572e2385a radix tree: fix m... |
1562 |
if (*nodep && !is_sibling_entry(iter->node, *nodep)) |
148deab22 radix-tree: impro... |
1563 1564 1565 1566 1567 1568 1569 1570 1571 |
return slot; slot++; iter->index = __radix_tree_iter_add(iter, 1); iter->tags >>= 1; } *nodep = NULL; return NULL; } |
d7b627277 radix-tree: Fix _... |
1572 1573 |
void __rcu **__radix_tree_next_slot(void __rcu **slot, struct radix_tree_iter *iter, unsigned flags) |
148deab22 radix-tree: impro... |
1574 1575 |
{ unsigned tag = flags & RADIX_TREE_ITER_TAG_MASK; |
572e2385a radix tree: fix m... |
1576 |
struct radix_tree_node *node; |
148deab22 radix-tree: impro... |
1577 1578 1579 1580 1581 1582 1583 1584 1585 1586 |
slot = skip_siblings(&node, slot, iter); while (radix_tree_is_internal_node(node)) { unsigned offset; unsigned long next_index; if (node == RADIX_TREE_RETRY) return slot; node = entry_to_node(node); |
268f42de7 radix-tree: delet... |
1587 |
iter->node = node; |
148deab22 radix-tree: impro... |
1588 1589 1590 1591 1592 1593 1594 1595 1596 1597 1598 1599 1600 1601 1602 1603 1604 1605 1606 1607 1608 1609 1610 1611 1612 1613 1614 1615 1616 1617 1618 1619 1620 1621 1622 1623 1624 1625 |
iter->shift = node->shift; if (flags & RADIX_TREE_ITER_TAGGED) { offset = radix_tree_find_next_bit(node, tag, 0); if (offset == RADIX_TREE_MAP_SIZE) return NULL; slot = &node->slots[offset]; iter->index = __radix_tree_iter_add(iter, offset); set_iter_tags(iter, node, offset, tag); node = rcu_dereference_raw(*slot); } else { offset = 0; slot = &node->slots[0]; for (;;) { node = rcu_dereference_raw(*slot); if (node) break; slot++; offset++; if (offset == RADIX_TREE_MAP_SIZE) return NULL; } iter->index = __radix_tree_iter_add(iter, offset); } if ((flags & RADIX_TREE_ITER_CONTIG) && (offset > 0)) goto none; next_index = (iter->index | shift_maxindex(iter->shift)) + 1; if (next_index < iter->next_index) iter->next_index = next_index; } return slot; none: iter->next_index = 0; return NULL; } EXPORT_SYMBOL(__radix_tree_next_slot); #else |
d7b627277 radix-tree: Fix _... |
1626 1627 |
static void __rcu **skip_siblings(struct radix_tree_node **nodep, void __rcu **slot, struct radix_tree_iter *iter) |
148deab22 radix-tree: impro... |
1628 1629 1630 1631 |
{ return slot; } #endif |
d7b627277 radix-tree: Fix _... |
1632 1633 |
void __rcu **radix_tree_iter_resume(void __rcu **slot, struct radix_tree_iter *iter) |
148deab22 radix-tree: impro... |
1634 1635 1636 1637 1638 |
{ struct radix_tree_node *node; slot++; iter->index = __radix_tree_iter_add(iter, 1); |
148deab22 radix-tree: impro... |
1639 1640 1641 1642 1643 1644 |
skip_siblings(&node, slot, iter); iter->next_index = iter->index; iter->tags = 0; return NULL; } EXPORT_SYMBOL(radix_tree_iter_resume); |
6df8ba4f8 radixtree: introd... |
1645 |
/** |
78c1d7848 radix-tree: intro... |
1646 1647 1648 1649 1650 1651 1652 |
* 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 */ |
d7b627277 radix-tree: Fix _... |
1653 |
void __rcu **radix_tree_next_chunk(const struct radix_tree_root *root, |
78c1d7848 radix-tree: intro... |
1654 1655 |
struct radix_tree_iter *iter, unsigned flags) { |
9e85d8111 radix-tree: make ... |
1656 |
unsigned tag = flags & RADIX_TREE_ITER_TAG_MASK; |
8c1244de0 radix-tree: tidy ... |
1657 |
struct radix_tree_node *node, *child; |
21ef53393 radix-tree: add s... |
1658 |
unsigned long index, offset, maxindex; |
78c1d7848 radix-tree: intro... |
1659 1660 1661 1662 1663 1664 1665 1666 1667 |
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... |
1668 1669 |
* * This condition also used by radix_tree_next_slot() to stop |
91b9677c4 radix-tree: fix typo |
1670 |
* contiguous iterating, and forbid switching to the next chunk. |
78c1d7848 radix-tree: intro... |
1671 1672 1673 1674 |
*/ index = iter->next_index; if (!index && iter->index) return NULL; |
21ef53393 radix-tree: add s... |
1675 |
restart: |
9e85d8111 radix-tree: make ... |
1676 |
radix_tree_load_root(root, &child, &maxindex); |
21ef53393 radix-tree: add s... |
1677 1678 |
if (index > maxindex) return NULL; |
8c1244de0 radix-tree: tidy ... |
1679 1680 |
if (!child) return NULL; |
21ef53393 radix-tree: add s... |
1681 |
|
8c1244de0 radix-tree: tidy ... |
1682 |
if (!radix_tree_is_internal_node(child)) { |
78c1d7848 radix-tree: intro... |
1683 |
/* Single-slot tree */ |
21ef53393 radix-tree: add s... |
1684 1685 |
iter->index = index; iter->next_index = maxindex + 1; |
78c1d7848 radix-tree: intro... |
1686 |
iter->tags = 1; |
268f42de7 radix-tree: delet... |
1687 |
iter->node = NULL; |
8c1244de0 radix-tree: tidy ... |
1688 |
__set_iter_shift(iter, 0); |
d7b627277 radix-tree: Fix _... |
1689 |
return (void __rcu **)&root->rnode; |
8c1244de0 radix-tree: tidy ... |
1690 |
} |
21ef53393 radix-tree: add s... |
1691 |
|
8c1244de0 radix-tree: tidy ... |
1692 1693 |
do { node = entry_to_node(child); |
9e85d8111 radix-tree: make ... |
1694 |
offset = radix_tree_descend(node, &child, index); |
21ef53393 radix-tree: add s... |
1695 |
|
78c1d7848 radix-tree: intro... |
1696 |
if ((flags & RADIX_TREE_ITER_TAGGED) ? |
8c1244de0 radix-tree: tidy ... |
1697 |
!tag_get(node, tag, offset) : !child) { |
78c1d7848 radix-tree: intro... |
1698 1699 1700 1701 1702 |
/* Hole detected */ if (flags & RADIX_TREE_ITER_CONTIG) return NULL; if (flags & RADIX_TREE_ITER_TAGGED) |
bc412fca6 radix-tree: make ... |
1703 |
offset = radix_tree_find_next_bit(node, tag, |
78c1d7848 radix-tree: intro... |
1704 1705 1706 |
offset + 1); else while (++offset < RADIX_TREE_MAP_SIZE) { |
12320d0ff radix-tree: Add r... |
1707 1708 |
void *slot = rcu_dereference_raw( node->slots[offset]); |
21ef53393 radix-tree: add s... |
1709 1710 1711 |
if (is_sibling_entry(node, slot)) continue; if (slot) |
78c1d7848 radix-tree: intro... |
1712 1713 |
break; } |
8c1244de0 radix-tree: tidy ... |
1714 |
index &= ~node_maxindex(node); |
9e85d8111 radix-tree: make ... |
1715 |
index += offset << node->shift; |
78c1d7848 radix-tree: intro... |
1716 1717 1718 1719 1720 |
/* Overflow after ~0UL */ if (!index) return NULL; if (offset == RADIX_TREE_MAP_SIZE) goto restart; |
8c1244de0 radix-tree: tidy ... |
1721 |
child = rcu_dereference_raw(node->slots[offset]); |
78c1d7848 radix-tree: intro... |
1722 |
} |
e157b5559 radix-tree: add r... |
1723 |
if (!child) |
78c1d7848 radix-tree: intro... |
1724 |
goto restart; |
e157b5559 radix-tree: add r... |
1725 1726 |
if (child == RADIX_TREE_RETRY) break; |
8c1244de0 radix-tree: tidy ... |
1727 |
} while (radix_tree_is_internal_node(child)); |
78c1d7848 radix-tree: intro... |
1728 1729 |
/* Update the iterator state */ |
8c1244de0 radix-tree: tidy ... |
1730 1731 |
iter->index = (index &~ node_maxindex(node)) | (offset << node->shift); iter->next_index = (index | node_maxindex(node)) + 1; |
268f42de7 radix-tree: delet... |
1732 |
iter->node = node; |
9e85d8111 radix-tree: make ... |
1733 |
__set_iter_shift(iter, node->shift); |
78c1d7848 radix-tree: intro... |
1734 |
|
148deab22 radix-tree: impro... |
1735 1736 |
if (flags & RADIX_TREE_ITER_TAGGED) set_iter_tags(iter, node, offset, tag); |
78c1d7848 radix-tree: intro... |
1737 1738 1739 1740 1741 1742 |
return node->slots + offset; } EXPORT_SYMBOL(radix_tree_next_chunk); /** |
1da177e4c Linux-2.6.12-rc2 |
1743 1744 1745 1746 1747 1748 1749 1750 1751 1752 1753 |
* 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... |
1754 1755 1756 |
* * 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... |
1757 1758 1759 1760 |
* 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 |
1761 1762 |
*/ unsigned int |
35534c869 radix tree: const... |
1763 |
radix_tree_gang_lookup(const struct radix_tree_root *root, void **results, |
1da177e4c Linux-2.6.12-rc2 |
1764 1765 |
unsigned long first_index, unsigned int max_items) { |
cebbd29e1 radix-tree: rewri... |
1766 |
struct radix_tree_iter iter; |
d7b627277 radix-tree: Fix _... |
1767 |
void __rcu **slot; |
cebbd29e1 radix-tree: rewri... |
1768 |
unsigned int ret = 0; |
7cf9c2c76 [PATCH] radix-tre... |
1769 |
|
cebbd29e1 radix-tree: rewri... |
1770 |
if (unlikely(!max_items)) |
7cf9c2c76 [PATCH] radix-tre... |
1771 |
return 0; |
1da177e4c Linux-2.6.12-rc2 |
1772 |
|
cebbd29e1 radix-tree: rewri... |
1773 |
radix_tree_for_each_slot(slot, root, &iter, first_index) { |
46437f9a5 radix-tree: fix r... |
1774 |
results[ret] = rcu_dereference_raw(*slot); |
cebbd29e1 radix-tree: rewri... |
1775 1776 |
if (!results[ret]) continue; |
b194d16c2 radix-tree: renam... |
1777 |
if (radix_tree_is_internal_node(results[ret])) { |
46437f9a5 radix-tree: fix r... |
1778 1779 1780 |
slot = radix_tree_iter_retry(&iter); continue; } |
cebbd29e1 radix-tree: rewri... |
1781 |
if (++ret == max_items) |
1da177e4c Linux-2.6.12-rc2 |
1782 |
break; |
1da177e4c Linux-2.6.12-rc2 |
1783 |
} |
7cf9c2c76 [PATCH] radix-tre... |
1784 |
|
1da177e4c Linux-2.6.12-rc2 |
1785 1786 1787 |
return ret; } EXPORT_SYMBOL(radix_tree_gang_lookup); |
47feff2c8 radix-tree: add g... |
1788 1789 1790 1791 |
/** * 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... |
1792 |
* @indices: where their indices should be placed (but usually NULL) |
47feff2c8 radix-tree: add g... |
1793 1794 1795 1796 1797 1798 1799 1800 1801 1802 1803 1804 1805 1806 |
* @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 |
35534c869 radix tree: const... |
1807 |
radix_tree_gang_lookup_slot(const struct radix_tree_root *root, |
d7b627277 radix-tree: Fix _... |
1808 |
void __rcu ***results, unsigned long *indices, |
47feff2c8 radix-tree: add g... |
1809 1810 |
unsigned long first_index, unsigned int max_items) { |
cebbd29e1 radix-tree: rewri... |
1811 |
struct radix_tree_iter iter; |
d7b627277 radix-tree: Fix _... |
1812 |
void __rcu **slot; |
cebbd29e1 radix-tree: rewri... |
1813 |
unsigned int ret = 0; |
47feff2c8 radix-tree: add g... |
1814 |
|
cebbd29e1 radix-tree: rewri... |
1815 |
if (unlikely(!max_items)) |
47feff2c8 radix-tree: add g... |
1816 |
return 0; |
cebbd29e1 radix-tree: rewri... |
1817 1818 |
radix_tree_for_each_slot(slot, root, &iter, first_index) { results[ret] = slot; |
6328650bb radix_tree: excep... |
1819 |
if (indices) |
cebbd29e1 radix-tree: rewri... |
1820 1821 |
indices[ret] = iter.index; if (++ret == max_items) |
47feff2c8 radix-tree: add g... |
1822 |
break; |
47feff2c8 radix-tree: add g... |
1823 1824 1825 1826 1827 |
} return ret; } EXPORT_SYMBOL(radix_tree_gang_lookup_slot); |
1da177e4c Linux-2.6.12-rc2 |
1828 1829 1830 1831 1832 1833 1834 |
/** * 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... |
1835 |
* @tag: the tag index (< RADIX_TREE_MAX_TAGS) |
1da177e4c Linux-2.6.12-rc2 |
1836 1837 1838 1839 1840 1841 |
* * 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 |
35534c869 radix tree: const... |
1842 |
radix_tree_gang_lookup_tag(const struct radix_tree_root *root, void **results, |
daff89f32 [PATCH] radix-tre... |
1843 1844 |
unsigned long first_index, unsigned int max_items, unsigned int tag) |
1da177e4c Linux-2.6.12-rc2 |
1845 |
{ |
cebbd29e1 radix-tree: rewri... |
1846 |
struct radix_tree_iter iter; |
d7b627277 radix-tree: Fix _... |
1847 |
void __rcu **slot; |
cebbd29e1 radix-tree: rewri... |
1848 |
unsigned int ret = 0; |
612d6c19d [PATCH] radix-tre... |
1849 |
|
cebbd29e1 radix-tree: rewri... |
1850 |
if (unlikely(!max_items)) |
7cf9c2c76 [PATCH] radix-tre... |
1851 |
return 0; |
cebbd29e1 radix-tree: rewri... |
1852 |
radix_tree_for_each_tagged(slot, root, &iter, first_index, tag) { |
46437f9a5 radix-tree: fix r... |
1853 |
results[ret] = rcu_dereference_raw(*slot); |
cebbd29e1 radix-tree: rewri... |
1854 1855 |
if (!results[ret]) continue; |
b194d16c2 radix-tree: renam... |
1856 |
if (radix_tree_is_internal_node(results[ret])) { |
46437f9a5 radix-tree: fix r... |
1857 1858 1859 |
slot = radix_tree_iter_retry(&iter); continue; } |
cebbd29e1 radix-tree: rewri... |
1860 |
if (++ret == max_items) |
1da177e4c Linux-2.6.12-rc2 |
1861 |
break; |
1da177e4c Linux-2.6.12-rc2 |
1862 |
} |
7cf9c2c76 [PATCH] radix-tre... |
1863 |
|
1da177e4c Linux-2.6.12-rc2 |
1864 1865 1866 1867 1868 |
return ret; } EXPORT_SYMBOL(radix_tree_gang_lookup_tag); /** |
47feff2c8 radix-tree: add g... |
1869 1870 1871 1872 1873 1874 1875 1876 1877 1878 1879 1880 1881 |
* 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 |
35534c869 radix tree: const... |
1882 |
radix_tree_gang_lookup_tag_slot(const struct radix_tree_root *root, |
d7b627277 radix-tree: Fix _... |
1883 |
void __rcu ***results, unsigned long first_index, |
35534c869 radix tree: const... |
1884 |
unsigned int max_items, unsigned int tag) |
47feff2c8 radix-tree: add g... |
1885 |
{ |
cebbd29e1 radix-tree: rewri... |
1886 |
struct radix_tree_iter iter; |
d7b627277 radix-tree: Fix _... |
1887 |
void __rcu **slot; |
cebbd29e1 radix-tree: rewri... |
1888 |
unsigned int ret = 0; |
47feff2c8 radix-tree: add g... |
1889 |
|
cebbd29e1 radix-tree: rewri... |
1890 |
if (unlikely(!max_items)) |
47feff2c8 radix-tree: add g... |
1891 |
return 0; |
cebbd29e1 radix-tree: rewri... |
1892 1893 1894 |
radix_tree_for_each_tagged(slot, root, &iter, first_index, tag) { results[ret] = slot; if (++ret == max_items) |
47feff2c8 radix-tree: add g... |
1895 |
break; |
47feff2c8 radix-tree: add g... |
1896 1897 1898 1899 1900 |
} return ret; } EXPORT_SYMBOL(radix_tree_gang_lookup_tag_slot); |
47feff2c8 radix-tree: add g... |
1901 |
/** |
139e56166 lib: radix_tree: ... |
1902 1903 |
* __radix_tree_delete_node - try to free node after clearing a slot * @root: radix tree root |
139e56166 lib: radix_tree: ... |
1904 |
* @node: node containing @index |
ea07b862a mm: workingset: f... |
1905 1906 |
* @update_node: callback for changing leaf nodes * @private: private data to pass to @update_node |
139e56166 lib: radix_tree: ... |
1907 1908 1909 1910 |
* * 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. |
139e56166 lib: radix_tree: ... |
1911 |
*/ |
14b468791 mm: workingset: m... |
1912 |
void __radix_tree_delete_node(struct radix_tree_root *root, |
ea07b862a mm: workingset: f... |
1913 1914 1915 |
struct radix_tree_node *node, radix_tree_update_node_t update_node, void *private) |
139e56166 lib: radix_tree: ... |
1916 |
{ |
ea07b862a mm: workingset: f... |
1917 |
delete_node(root, node, update_node, private); |
139e56166 lib: radix_tree: ... |
1918 |
} |
0ac398ef3 radix-tree: Add r... |
1919 |
static bool __radix_tree_delete(struct radix_tree_root *root, |
d7b627277 radix-tree: Fix _... |
1920 |
struct radix_tree_node *node, void __rcu **slot) |
0ac398ef3 radix-tree: Add r... |
1921 |
{ |
0a835c4f0 Reimplement IDR a... |
1922 1923 |
void *old = rcu_dereference_raw(*slot); int exceptional = radix_tree_exceptional_entry(old) ? -1 : 0; |
0ac398ef3 radix-tree: Add r... |
1924 1925 |
unsigned offset = get_slot_offset(node, slot); int tag; |
0a835c4f0 Reimplement IDR a... |
1926 1927 1928 1929 1930 |
if (is_idr(root)) node_tag_set(root, node, IDR_FREE, offset); else for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) node_tag_clear(root, node, tag, offset); |
0ac398ef3 radix-tree: Add r... |
1931 |
|
0a835c4f0 Reimplement IDR a... |
1932 |
replace_slot(slot, NULL, node, -1, exceptional); |
0ac398ef3 radix-tree: Add r... |
1933 1934 |
return node && delete_node(root, node, NULL, NULL); } |
139e56166 lib: radix_tree: ... |
1935 |
/** |
0ac398ef3 radix-tree: Add r... |
1936 1937 1938 1939 |
* radix_tree_iter_delete - delete the entry at this iterator position * @root: radix tree root * @iter: iterator state * @slot: pointer to slot |
1da177e4c Linux-2.6.12-rc2 |
1940 |
* |
0ac398ef3 radix-tree: Add r... |
1941 1942 1943 1944 1945 1946 1947 |
* Delete the entry at the position currently pointed to by the iterator. * This may result in the current node being freed; if it is, the iterator * is advanced so that it will not reference the freed memory. This * function may be called without any locking if there are no other threads * which can access this tree. */ void radix_tree_iter_delete(struct radix_tree_root *root, |
d7b627277 radix-tree: Fix _... |
1948 |
struct radix_tree_iter *iter, void __rcu **slot) |
0ac398ef3 radix-tree: Add r... |
1949 1950 1951 1952 |
{ if (__radix_tree_delete(root, iter->node, slot)) iter->index = iter->next_index; } |
d1b48c1e7 drm/i915: Replace... |
1953 |
EXPORT_SYMBOL(radix_tree_iter_delete); |
0ac398ef3 radix-tree: Add r... |
1954 1955 1956 1957 1958 1959 |
/** * radix_tree_delete_item - delete an item from a radix tree * @root: radix tree root * @index: index key * @item: expected item |
1da177e4c Linux-2.6.12-rc2 |
1960 |
* |
0ac398ef3 radix-tree: Add r... |
1961 |
* Remove @item at @index from the radix tree rooted at @root. |
1da177e4c Linux-2.6.12-rc2 |
1962 |
* |
0ac398ef3 radix-tree: Add r... |
1963 1964 |
* Return: the deleted entry, or %NULL if it was not present * or the entry at the given @index was not @item. |
1da177e4c Linux-2.6.12-rc2 |
1965 |
*/ |
53c59f262 lib: radix-tree: ... |
1966 1967 |
void *radix_tree_delete_item(struct radix_tree_root *root, unsigned long index, void *item) |
1da177e4c Linux-2.6.12-rc2 |
1968 |
{ |
0a835c4f0 Reimplement IDR a... |
1969 |
struct radix_tree_node *node = NULL; |
0472f94ce idr: fix invalid ... |
1970 |
void __rcu **slot = NULL; |
139e56166 lib: radix_tree: ... |
1971 |
void *entry; |
1da177e4c Linux-2.6.12-rc2 |
1972 |
|
139e56166 lib: radix_tree: ... |
1973 |
entry = __radix_tree_lookup(root, index, &node, &slot); |
0472f94ce idr: fix invalid ... |
1974 1975 |
if (!slot) return NULL; |
0a835c4f0 Reimplement IDR a... |
1976 1977 |
if (!entry && (!is_idr(root) || node_tag_get(root, node, IDR_FREE, get_slot_offset(node, slot)))) |
139e56166 lib: radix_tree: ... |
1978 |
return NULL; |
1da177e4c Linux-2.6.12-rc2 |
1979 |
|
139e56166 lib: radix_tree: ... |
1980 1981 |
if (item && entry != item) return NULL; |
0ac398ef3 radix-tree: Add r... |
1982 |
__radix_tree_delete(root, node, slot); |
612d6c19d [PATCH] radix-tre... |
1983 |
|
139e56166 lib: radix_tree: ... |
1984 |
return entry; |
1da177e4c Linux-2.6.12-rc2 |
1985 |
} |
53c59f262 lib: radix-tree: ... |
1986 1987 1988 |
EXPORT_SYMBOL(radix_tree_delete_item); /** |
0ac398ef3 radix-tree: Add r... |
1989 1990 1991 |
* radix_tree_delete - delete an entry from a radix tree * @root: radix tree root * @index: index key |
53c59f262 lib: radix-tree: ... |
1992 |
* |
0ac398ef3 radix-tree: Add r... |
1993 |
* Remove the entry at @index from the radix tree rooted at @root. |
53c59f262 lib: radix-tree: ... |
1994 |
* |
0ac398ef3 radix-tree: Add r... |
1995 |
* Return: The deleted entry, or %NULL if it was not present. |
53c59f262 lib: radix-tree: ... |
1996 1997 1998 1999 2000 |
*/ 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 |
2001 |
EXPORT_SYMBOL(radix_tree_delete); |
d3798ae8c mm: filemap: don'... |
2002 2003 |
void radix_tree_clear_tags(struct radix_tree_root *root, struct radix_tree_node *node, |
d7b627277 radix-tree: Fix _... |
2004 |
void __rcu **slot) |
d604c3245 radix-tree: intro... |
2005 |
{ |
d604c3245 radix-tree: intro... |
2006 2007 2008 2009 2010 |
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 { |
0a835c4f0 Reimplement IDR a... |
2011 |
root_tag_clear_all(root); |
d604c3245 radix-tree: intro... |
2012 |
} |
d604c3245 radix-tree: intro... |
2013 |
} |
1da177e4c Linux-2.6.12-rc2 |
2014 2015 2016 2017 2018 |
/** * radix_tree_tagged - test whether any items in the tree are tagged * @root: radix tree root * @tag: tag to test */ |
35534c869 radix tree: const... |
2019 |
int radix_tree_tagged(const struct radix_tree_root *root, unsigned int tag) |
1da177e4c Linux-2.6.12-rc2 |
2020 |
{ |
612d6c19d [PATCH] radix-tre... |
2021 |
return root_tag_get(root, tag); |
1da177e4c Linux-2.6.12-rc2 |
2022 2023 |
} EXPORT_SYMBOL(radix_tree_tagged); |
0a835c4f0 Reimplement IDR a... |
2024 2025 2026 2027 2028 2029 2030 2031 2032 |
/** * idr_preload - preload for idr_alloc() * @gfp_mask: allocation mask to use for preloading * * Preallocate memory to use for the next call to idr_alloc(). This function * returns with preemption disabled. It will be enabled by idr_preload_end(). */ void idr_preload(gfp_t gfp_mask) { |
bc9ae2247 radix-tree: must ... |
2033 2034 |
if (__radix_tree_preload(gfp_mask, IDR_PRELOAD_SIZE)) preempt_disable(); |
0a835c4f0 Reimplement IDR a... |
2035 2036 |
} EXPORT_SYMBOL(idr_preload); |
7ad3d4d85 ida: Move ida_bit... |
2037 2038 2039 2040 2041 2042 2043 2044 2045 2046 |
/** * ida_pre_get - reserve resources for ida allocation * @ida: ida handle * @gfp: memory allocation flags * * This function should be called before calling ida_get_new_above(). If it * is unable to allocate memory, it will return %0. On success, it returns %1. */ int ida_pre_get(struct ida *ida, gfp_t gfp) { |
7ad3d4d85 ida: Move ida_bit... |
2047 2048 2049 2050 2051 |
/* * The IDA API has no preload_end() equivalent. Instead, * ida_get_new() can return -EAGAIN, prompting the caller * to return to the ida_pre_get() step. */ |
bc9ae2247 radix-tree: must ... |
2052 2053 |
if (!__radix_tree_preload(gfp, IDA_PRELOAD_SIZE)) preempt_enable(); |
7ad3d4d85 ida: Move ida_bit... |
2054 2055 2056 2057 2058 |
if (!this_cpu_read(ida_bitmap)) { struct ida_bitmap *bitmap = kmalloc(sizeof(*bitmap), gfp); if (!bitmap) return 0; |
4ecd9542d ida: Free correct... |
2059 2060 |
if (this_cpu_cmpxchg(ida_bitmap, NULL, bitmap)) kfree(bitmap); |
7ad3d4d85 ida: Move ida_bit... |
2061 2062 2063 2064 2065 |
} return 1; } EXPORT_SYMBOL(ida_pre_get); |
388f79fda idr: Add new APIs... |
2066 2067 2068 |
void __rcu **idr_get_free_cmn(struct radix_tree_root *root, struct radix_tree_iter *iter, gfp_t gfp, unsigned long max) |
0a835c4f0 Reimplement IDR a... |
2069 2070 |
{ struct radix_tree_node *node = NULL, *child; |
d7b627277 radix-tree: Fix _... |
2071 |
void __rcu **slot = (void __rcu **)&root->rnode; |
0a835c4f0 Reimplement IDR a... |
2072 |
unsigned long maxindex, start = iter->next_index; |
0a835c4f0 Reimplement IDR a... |
2073 2074 2075 2076 2077 2078 2079 2080 2081 2082 2083 2084 2085 2086 2087 2088 2089 2090 2091 2092 2093 |
unsigned int shift, offset = 0; grow: shift = radix_tree_load_root(root, &child, &maxindex); if (!radix_tree_tagged(root, IDR_FREE)) start = max(start, maxindex + 1); if (start > max) return ERR_PTR(-ENOSPC); if (start > maxindex) { int error = radix_tree_extend(root, gfp, start, shift); if (error < 0) return ERR_PTR(error); shift = error; child = rcu_dereference_raw(root->rnode); } while (shift) { shift -= RADIX_TREE_MAP_SHIFT; if (child == NULL) { /* Have to add a child node. */ |
d58275bc9 radix-tree: Store... |
2094 2095 |
child = radix_tree_node_alloc(gfp, node, root, shift, offset, 0, 0); |
0a835c4f0 Reimplement IDR a... |
2096 2097 2098 2099 2100 2101 2102 2103 2104 2105 2106 2107 2108 2109 2110 2111 2112 2113 2114 2115 2116 2117 2118 2119 2120 2121 2122 2123 2124 2125 2126 2127 2128 2129 2130 2131 2132 2133 2134 2135 2136 2137 2138 2139 2140 2141 2142 2143 2144 2145 2146 2147 2148 2149 2150 2151 2152 2153 2154 2155 2156 |
if (!child) return ERR_PTR(-ENOMEM); all_tag_set(child, IDR_FREE); rcu_assign_pointer(*slot, node_to_entry(child)); if (node) node->count++; } else if (!radix_tree_is_internal_node(child)) break; node = entry_to_node(child); offset = radix_tree_descend(node, &child, start); if (!tag_get(node, IDR_FREE, offset)) { offset = radix_tree_find_next_bit(node, IDR_FREE, offset + 1); start = next_index(start, node, offset); if (start > max) return ERR_PTR(-ENOSPC); while (offset == RADIX_TREE_MAP_SIZE) { offset = node->offset + 1; node = node->parent; if (!node) goto grow; shift = node->shift; } child = rcu_dereference_raw(node->slots[offset]); } slot = &node->slots[offset]; } iter->index = start; if (node) iter->next_index = 1 + min(max, (start | node_maxindex(node))); else iter->next_index = 1; iter->node = node; __set_iter_shift(iter, shift); set_iter_tags(iter, node, offset, IDR_FREE); return slot; } /** * idr_destroy - release all internal memory from an IDR * @idr: idr handle * * After this function is called, the IDR is empty, and may be reused or * the data structure containing it may be freed. * * A typical clean-up sequence for objects stored in an idr tree will use * idr_for_each() to free all objects, if necessary, then idr_destroy() to * free the memory used to keep track of those objects. */ void idr_destroy(struct idr *idr) { struct radix_tree_node *node = rcu_dereference_raw(idr->idr_rt.rnode); if (radix_tree_is_internal_node(node)) radix_tree_free_nodes(node); idr->idr_rt.rnode = NULL; root_tag_set(&idr->idr_rt, IDR_FREE); } EXPORT_SYMBOL(idr_destroy); |
1da177e4c Linux-2.6.12-rc2 |
2157 |
static void |
449dd6984 mm: keep page cac... |
2158 |
radix_tree_node_ctor(void *arg) |
1da177e4c Linux-2.6.12-rc2 |
2159 |
{ |
449dd6984 mm: keep page cac... |
2160 2161 2162 2163 |
struct radix_tree_node *node = arg; memset(node, 0, sizeof(*node)); INIT_LIST_HEAD(&node->private_list); |
1da177e4c Linux-2.6.12-rc2 |
2164 |
} |
c78c66d1d radix-tree: imple... |
2165 2166 2167 2168 2169 2170 2171 2172 2173 2174 2175 2176 2177 2178 2179 2180 2181 2182 2183 2184 2185 2186 2187 2188 |
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; } } |
d544abd5f lib/radix-tree: C... |
2189 |
static int radix_tree_cpu_dead(unsigned int cpu) |
1da177e4c Linux-2.6.12-rc2 |
2190 |
{ |
2fcd9005c radix-tree: misce... |
2191 2192 2193 2194 |
struct radix_tree_preload *rtp; struct radix_tree_node *node; /* Free per-cpu pool of preloaded nodes */ |
d544abd5f lib/radix-tree: C... |
2195 2196 2197 |
rtp = &per_cpu(radix_tree_preloads, cpu); while (rtp->nr) { node = rtp->nodes; |
1293d5c5f radix-tree: Chain... |
2198 |
rtp->nodes = node->parent; |
d544abd5f lib/radix-tree: C... |
2199 2200 |
kmem_cache_free(radix_tree_node_cachep, node); rtp->nr--; |
2fcd9005c radix-tree: misce... |
2201 |
} |
7ad3d4d85 ida: Move ida_bit... |
2202 2203 |
kfree(per_cpu(ida_bitmap, cpu)); per_cpu(ida_bitmap, cpu) = NULL; |
d544abd5f lib/radix-tree: C... |
2204 |
return 0; |
1da177e4c Linux-2.6.12-rc2 |
2205 |
} |
1da177e4c Linux-2.6.12-rc2 |
2206 2207 2208 |
void __init radix_tree_init(void) { |
d544abd5f lib/radix-tree: C... |
2209 |
int ret; |
7e7844226 lockdep: allow to... |
2210 2211 |
BUILD_BUG_ON(RADIX_TREE_MAX_TAGS + __GFP_BITS_SHIFT > 32); |
1da177e4c Linux-2.6.12-rc2 |
2212 2213 |
radix_tree_node_cachep = kmem_cache_create("radix_tree_node", sizeof(struct radix_tree_node), 0, |
488514d17 Remove set_migrat... |
2214 2215 |
SLAB_PANIC | SLAB_RECLAIM_ACCOUNT, radix_tree_node_ctor); |
c78c66d1d radix-tree: imple... |
2216 |
radix_tree_init_maxnodes(); |
d544abd5f lib/radix-tree: C... |
2217 2218 2219 |
ret = cpuhp_setup_state_nocalls(CPUHP_RADIX_DEAD, "lib/radix:dead", NULL, radix_tree_cpu_dead); WARN_ON(ret < 0); |
1da177e4c Linux-2.6.12-rc2 |
2220 |
} |