Blame view
lib/radix-tree.c
43.1 KB
de6cc6515 treewide: Replace... |
1 |
// SPDX-License-Identifier: GPL-2.0-or-later |
1da177e4c Linux-2.6.12-rc2 |
2 3 4 |
/* * Copyright (C) 2001 Momchil Velikov * Portions Copyright (C) 2001 Christoph Hellwig |
cde535359 Christoph has moved |
5 |
* Copyright (C) 2005 SGI, Christoph Lameter |
7cf9c2c76 [PATCH] radix-tre... |
6 |
* Copyright (C) 2006 Nick Piggin |
78c1d7848 radix-tree: intro... |
7 |
* Copyright (C) 2012 Konstantin Khlebnikov |
6b053b8e5 radix-tree: add c... |
8 9 |
* Copyright (C) 2016 Intel, Matthew Wilcox * Copyright (C) 2016 Intel, Ross Zwisler |
1da177e4c Linux-2.6.12-rc2 |
10 |
*/ |
0a835c4f0 Reimplement IDR a... |
11 12 |
#include <linux/bitmap.h> #include <linux/bitops.h> |
460488c58 idr: Remove idr_a... |
13 |
#include <linux/bug.h> |
e157b5559 radix-tree: add r... |
14 |
#include <linux/cpu.h> |
1da177e4c Linux-2.6.12-rc2 |
15 |
#include <linux/errno.h> |
0a835c4f0 Reimplement IDR a... |
16 17 |
#include <linux/export.h> #include <linux/idr.h> |
1da177e4c Linux-2.6.12-rc2 |
18 19 |
#include <linux/init.h> #include <linux/kernel.h> |
0a835c4f0 Reimplement IDR a... |
20 |
#include <linux/kmemleak.h> |
1da177e4c Linux-2.6.12-rc2 |
21 |
#include <linux/percpu.h> |
0a835c4f0 Reimplement IDR a... |
22 23 24 |
#include <linux/preempt.h> /* in_interrupt() */ #include <linux/radix-tree.h> #include <linux/rcupdate.h> |
1da177e4c Linux-2.6.12-rc2 |
25 |
#include <linux/slab.h> |
1da177e4c Linux-2.6.12-rc2 |
26 |
#include <linux/string.h> |
02c02bf12 xarray: Change de... |
27 |
#include <linux/xarray.h> |
1da177e4c Linux-2.6.12-rc2 |
28 |
|
26fb1589c fix the max path ... |
29 |
/* |
1da177e4c Linux-2.6.12-rc2 |
30 31 |
* Radix tree node cache. */ |
58d6ea308 xarray: Add XArra... |
32 |
struct kmem_cache *radix_tree_node_cachep; |
1da177e4c Linux-2.6.12-rc2 |
33 34 |
/* |
553680529 radix-tree: fix p... |
35 36 37 38 39 40 41 42 43 44 45 46 47 |
* 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... |
48 49 50 51 52 53 54 55 56 |
* 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) /* |
1da177e4c Linux-2.6.12-rc2 |
57 58 |
* Per-cpu pool of preloaded nodes */ |
cfa6705d8 radix-tree: Use l... |
59 60 |
DEFINE_PER_CPU(struct radix_tree_preload, radix_tree_preloads) = { .lock = INIT_LOCAL_LOCK(lock), |
1da177e4c Linux-2.6.12-rc2 |
61 |
}; |
cfa6705d8 radix-tree: Use l... |
62 |
EXPORT_PER_CPU_SYMBOL_GPL(radix_tree_preloads); |
1da177e4c Linux-2.6.12-rc2 |
63 |
|
148deab22 radix-tree: impro... |
64 65 66 67 |
static inline struct radix_tree_node *entry_to_node(void *ptr) { return (void *)((unsigned long)ptr & ~RADIX_TREE_INTERNAL_NODE); } |
a4db4dcea radix-tree: renam... |
68 |
static inline void *node_to_entry(void *ptr) |
27d20fddc radix-tree: fix R... |
69 |
{ |
30ff46ccb radix-tree: renam... |
70 |
return (void *)((unsigned long)ptr | RADIX_TREE_INTERNAL_NODE); |
27d20fddc radix-tree: fix R... |
71 |
} |
02c02bf12 xarray: Change de... |
72 |
#define RADIX_TREE_RETRY XA_RETRY_ENTRY |
db050f292 radix-tree: add m... |
73 |
|
d7b627277 radix-tree: Fix _... |
74 75 |
static inline unsigned long get_slot_offset(const struct radix_tree_node *parent, void __rcu **slot) |
db050f292 radix-tree: add m... |
76 |
{ |
76f070b41 radix-tree: Fix U... |
77 |
return parent ? slot - parent->slots : 0; |
db050f292 radix-tree: add m... |
78 |
} |
35534c869 radix tree: const... |
79 |
static unsigned int radix_tree_descend(const struct radix_tree_node *parent, |
9e85d8111 radix-tree: make ... |
80 |
struct radix_tree_node **nodep, unsigned long index) |
db050f292 radix-tree: add m... |
81 |
{ |
9e85d8111 radix-tree: make ... |
82 |
unsigned int offset = (index >> parent->shift) & RADIX_TREE_MAP_MASK; |
d7b627277 radix-tree: Fix _... |
83 |
void __rcu **entry = rcu_dereference_raw(parent->slots[offset]); |
db050f292 radix-tree: add m... |
84 |
|
db050f292 radix-tree: add m... |
85 86 87 |
*nodep = (void *)entry; return offset; } |
35534c869 radix tree: const... |
88 |
static inline gfp_t root_gfp_mask(const struct radix_tree_root *root) |
612d6c19d [PATCH] radix-tre... |
89 |
{ |
f8d5d0cc1 xarray: Add defin... |
90 |
return root->xa_flags & (__GFP_BITS_MASK & ~GFP_ZONEMASK); |
612d6c19d [PATCH] radix-tre... |
91 |
} |
643b52b9c radix-tree: fix s... |
92 93 94 95 96 97 98 99 100 101 102 |
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... |
103 |
static inline int tag_get(const struct radix_tree_node *node, unsigned int tag, |
643b52b9c radix-tree: fix s... |
104 105 106 107 |
int offset) { return test_bit(offset, node->tags[tag]); } |
35534c869 radix tree: const... |
108 |
static inline void root_tag_set(struct radix_tree_root *root, unsigned tag) |
643b52b9c radix-tree: fix s... |
109 |
{ |
f8d5d0cc1 xarray: Add defin... |
110 |
root->xa_flags |= (__force gfp_t)(1 << (tag + ROOT_TAG_SHIFT)); |
643b52b9c radix-tree: fix s... |
111 |
} |
2fcd9005c radix-tree: misce... |
112 |
static inline void root_tag_clear(struct radix_tree_root *root, unsigned tag) |
643b52b9c radix-tree: fix s... |
113 |
{ |
f8d5d0cc1 xarray: Add defin... |
114 |
root->xa_flags &= (__force gfp_t)~(1 << (tag + ROOT_TAG_SHIFT)); |
643b52b9c radix-tree: fix s... |
115 116 117 118 |
} static inline void root_tag_clear_all(struct radix_tree_root *root) { |
f8d5d0cc1 xarray: Add defin... |
119 |
root->xa_flags &= (__force gfp_t)((1 << ROOT_TAG_SHIFT) - 1); |
643b52b9c radix-tree: fix s... |
120 |
} |
35534c869 radix tree: const... |
121 |
static inline int root_tag_get(const struct radix_tree_root *root, unsigned tag) |
643b52b9c radix-tree: fix s... |
122 |
{ |
f8d5d0cc1 xarray: Add defin... |
123 |
return (__force int)root->xa_flags & (1 << (tag + ROOT_TAG_SHIFT)); |
643b52b9c radix-tree: fix s... |
124 |
} |
35534c869 radix tree: const... |
125 |
static inline unsigned root_tags_get(const struct radix_tree_root *root) |
643b52b9c radix-tree: fix s... |
126 |
{ |
f8d5d0cc1 xarray: Add defin... |
127 |
return (__force unsigned)root->xa_flags >> ROOT_TAG_SHIFT; |
643b52b9c radix-tree: fix s... |
128 |
} |
0a835c4f0 Reimplement IDR a... |
129 |
static inline bool is_idr(const struct radix_tree_root *root) |
7b60e9ad5 radix-tree: fix m... |
130 |
{ |
f8d5d0cc1 xarray: Add defin... |
131 |
return !!(root->xa_flags & ROOT_IS_IDR); |
7b60e9ad5 radix-tree: fix m... |
132 |
} |
643b52b9c radix-tree: fix s... |
133 134 135 136 |
/* * Returns 1 if any slot in the node has this tag set. * Otherwise returns 0. */ |
35534c869 radix tree: const... |
137 138 |
static inline int any_tag_set(const struct radix_tree_node *node, unsigned int tag) |
643b52b9c radix-tree: fix s... |
139 |
{ |
2fcd9005c radix-tree: misce... |
140 |
unsigned idx; |
643b52b9c radix-tree: fix s... |
141 142 143 144 145 146 |
for (idx = 0; idx < RADIX_TREE_TAG_LONGS; idx++) { if (node->tags[tag][idx]) return 1; } return 0; } |
78c1d7848 radix-tree: intro... |
147 |
|
0a835c4f0 Reimplement IDR a... |
148 149 150 151 |
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... |
152 153 154 155 156 157 158 159 160 161 162 163 |
/** * 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 ... |
164 165 |
radix_tree_find_next_bit(struct radix_tree_node *node, unsigned int tag, unsigned long offset) |
78c1d7848 radix-tree: intro... |
166 |
{ |
bc412fca6 radix-tree: make ... |
167 |
const unsigned long *addr = node->tags[tag]; |
78c1d7848 radix-tree: intro... |
168 |
|
bc412fca6 radix-tree: make ... |
169 |
if (offset < RADIX_TREE_MAP_SIZE) { |
78c1d7848 radix-tree: intro... |
170 171 172 173 174 175 176 |
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 ... |
177 |
while (offset < RADIX_TREE_MAP_SIZE) { |
78c1d7848 radix-tree: intro... |
178 179 180 181 182 183 |
tmp = *++addr; if (tmp) return __ffs(tmp) + offset; offset += BITS_PER_LONG; } } |
bc412fca6 radix-tree: make ... |
184 |
return RADIX_TREE_MAP_SIZE; |
78c1d7848 radix-tree: intro... |
185 |
} |
268f42de7 radix-tree: delet... |
186 187 |
static unsigned int iter_offset(const struct radix_tree_iter *iter) { |
3a08cd52c radix tree: Remov... |
188 |
return iter->index & RADIX_TREE_MAP_MASK; |
268f42de7 radix-tree: delet... |
189 |
} |
218ed7503 radix-tree: impro... |
190 191 192 193 194 195 196 |
/* * 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... |
197 |
static inline unsigned long node_maxindex(const struct radix_tree_node *node) |
218ed7503 radix-tree: impro... |
198 199 200 |
{ return shift_maxindex(node->shift); } |
0a835c4f0 Reimplement IDR a... |
201 202 203 204 205 206 |
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); } |
1da177e4c Linux-2.6.12-rc2 |
207 208 209 210 211 |
/* * 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... |
212 |
radix_tree_node_alloc(gfp_t gfp_mask, struct radix_tree_node *parent, |
d58275bc9 radix-tree: Store... |
213 |
struct radix_tree_root *root, |
e8de43407 radix-tree: ensur... |
214 |
unsigned int shift, unsigned int offset, |
01959dfe7 xarray: Define st... |
215 |
unsigned int count, unsigned int nr_values) |
1da177e4c Linux-2.6.12-rc2 |
216 |
{ |
e2848a0ef radix-tree: avoid... |
217 |
struct radix_tree_node *ret = NULL; |
1da177e4c Linux-2.6.12-rc2 |
218 |
|
5e4c0d974 lib/radix-tree.c:... |
219 |
/* |
2fcd9005c radix-tree: misce... |
220 221 222 |
* 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:... |
223 |
*/ |
d0164adc8 mm, page_alloc: d... |
224 |
if (!gfpflags_allow_blocking(gfp_mask) && !in_interrupt()) { |
1da177e4c Linux-2.6.12-rc2 |
225 |
struct radix_tree_preload *rtp; |
e2848a0ef radix-tree: avoid... |
226 |
/* |
58e698af4 radix-tree: accou... |
227 |
* Even if the caller has preloaded, try to allocate from the |
05eb6e726 radix-tree: accou... |
228 229 |
* cache first for the new node to get accounted to the memory * cgroup. |
58e698af4 radix-tree: accou... |
230 231 |
*/ ret = kmem_cache_alloc(radix_tree_node_cachep, |
05eb6e726 radix-tree: accou... |
232 |
gfp_mask | __GFP_NOWARN); |
58e698af4 radix-tree: accou... |
233 234 235 236 |
if (ret) goto out; /* |
e2848a0ef radix-tree: avoid... |
237 238 239 240 |
* 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... |
241 |
rtp = this_cpu_ptr(&radix_tree_preloads); |
1da177e4c Linux-2.6.12-rc2 |
242 |
if (rtp->nr) { |
9d2a8da00 radix-tree: repla... |
243 |
ret = rtp->nodes; |
1293d5c5f radix-tree: Chain... |
244 |
rtp->nodes = ret->parent; |
1da177e4c Linux-2.6.12-rc2 |
245 246 |
rtp->nr--; } |
ce80b067d lib/radix-tree.c:... |
247 248 249 250 251 |
/* * Update the allocation stack trace as this is more useful * for debugging. */ kmemleak_update_trace(ret); |
58e698af4 radix-tree: accou... |
252 |
goto out; |
1da177e4c Linux-2.6.12-rc2 |
253 |
} |
05eb6e726 radix-tree: accou... |
254 |
ret = kmem_cache_alloc(radix_tree_node_cachep, gfp_mask); |
58e698af4 radix-tree: accou... |
255 |
out: |
b194d16c2 radix-tree: renam... |
256 |
BUG_ON(radix_tree_is_internal_node(ret)); |
e8de43407 radix-tree: ensur... |
257 |
if (ret) { |
e8de43407 radix-tree: ensur... |
258 259 260 |
ret->shift = shift; ret->offset = offset; ret->count = count; |
01959dfe7 xarray: Define st... |
261 |
ret->nr_values = nr_values; |
d58275bc9 radix-tree: Store... |
262 |
ret->parent = parent; |
01959dfe7 xarray: Define st... |
263 |
ret->array = root; |
e8de43407 radix-tree: ensur... |
264 |
} |
1da177e4c Linux-2.6.12-rc2 |
265 266 |
return ret; } |
58d6ea308 xarray: Add XArra... |
267 |
void radix_tree_node_rcu_free(struct rcu_head *head) |
7cf9c2c76 [PATCH] radix-tre... |
268 269 270 |
{ struct radix_tree_node *node = container_of(head, struct radix_tree_node, rcu_head); |
643b52b9c radix-tree: fix s... |
271 272 |
/* |
175542f57 radix-tree: add r... |
273 274 275 |
* 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... |
276 |
*/ |
175542f57 radix-tree: add r... |
277 278 |
memset(node->slots, 0, sizeof(node->slots)); memset(node->tags, 0, sizeof(node->tags)); |
91d9c05ac radix-tree: move ... |
279 |
INIT_LIST_HEAD(&node->private_list); |
643b52b9c radix-tree: fix s... |
280 |
|
7cf9c2c76 [PATCH] radix-tre... |
281 282 |
kmem_cache_free(radix_tree_node_cachep, node); } |
1da177e4c Linux-2.6.12-rc2 |
283 284 285 |
static inline void radix_tree_node_free(struct radix_tree_node *node) { |
7cf9c2c76 [PATCH] radix-tre... |
286 |
call_rcu(&node->rcu_head, radix_tree_node_rcu_free); |
1da177e4c Linux-2.6.12-rc2 |
287 288 289 290 291 292 293 |
} /* * 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... |
294 295 |
* * To make use of this facility, the radix tree must be initialised without |
d0164adc8 mm, page_alloc: d... |
296 |
* __GFP_DIRECT_RECLAIM being passed to INIT_RADIX_TREE(). |
1da177e4c Linux-2.6.12-rc2 |
297 |
*/ |
bc9ae2247 radix-tree: must ... |
298 |
static __must_check int __radix_tree_preload(gfp_t gfp_mask, unsigned nr) |
1da177e4c Linux-2.6.12-rc2 |
299 300 301 302 |
{ struct radix_tree_preload *rtp; struct radix_tree_node *node; int ret = -ENOMEM; |
05eb6e726 radix-tree: accou... |
303 |
/* |
e0656501a lib: radix-tree: ... |
304 |
* Nodes preloaded by one cgroup can be used by another cgroup, so |
05eb6e726 radix-tree: accou... |
305 306 307 |
* they should never be accounted to any particular memory cgroup. */ gfp_mask &= ~__GFP_ACCOUNT; |
cfa6705d8 radix-tree: Use l... |
308 |
local_lock(&radix_tree_preloads.lock); |
7c8e0181e mm: replace __get... |
309 |
rtp = this_cpu_ptr(&radix_tree_preloads); |
c78c66d1d radix-tree: imple... |
310 |
while (rtp->nr < nr) { |
cfa6705d8 radix-tree: Use l... |
311 |
local_unlock(&radix_tree_preloads.lock); |
488514d17 Remove set_migrat... |
312 |
node = kmem_cache_alloc(radix_tree_node_cachep, gfp_mask); |
1da177e4c Linux-2.6.12-rc2 |
313 314 |
if (node == NULL) goto out; |
cfa6705d8 radix-tree: Use l... |
315 |
local_lock(&radix_tree_preloads.lock); |
7c8e0181e mm: replace __get... |
316 |
rtp = this_cpu_ptr(&radix_tree_preloads); |
c78c66d1d radix-tree: imple... |
317 |
if (rtp->nr < nr) { |
1293d5c5f radix-tree: Chain... |
318 |
node->parent = rtp->nodes; |
9d2a8da00 radix-tree: repla... |
319 320 321 |
rtp->nodes = node; rtp->nr++; } else { |
1da177e4c Linux-2.6.12-rc2 |
322 |
kmem_cache_free(radix_tree_node_cachep, node); |
9d2a8da00 radix-tree: repla... |
323 |
} |
1da177e4c Linux-2.6.12-rc2 |
324 325 326 327 328 |
} ret = 0; out: return ret; } |
5e4c0d974 lib/radix-tree.c:... |
329 330 331 332 333 334 335 336 |
/* * 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... |
337 |
* __GFP_DIRECT_RECLAIM being passed to INIT_RADIX_TREE(). |
5e4c0d974 lib/radix-tree.c:... |
338 339 340 341 |
*/ int radix_tree_preload(gfp_t gfp_mask) { /* Warn on non-sensical use... */ |
d0164adc8 mm, page_alloc: d... |
342 |
WARN_ON_ONCE(!gfpflags_allow_blocking(gfp_mask)); |
c78c66d1d radix-tree: imple... |
343 |
return __radix_tree_preload(gfp_mask, RADIX_TREE_PRELOAD_SIZE); |
5e4c0d974 lib/radix-tree.c:... |
344 |
} |
d7f0923d8 [LIB]: export rad... |
345 |
EXPORT_SYMBOL(radix_tree_preload); |
1da177e4c Linux-2.6.12-rc2 |
346 |
|
6e954b9e9 [PATCH] radix tre... |
347 |
/* |
5e4c0d974 lib/radix-tree.c:... |
348 349 350 351 352 353 |
* 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... |
354 |
if (gfpflags_allow_blocking(gfp_mask)) |
c78c66d1d radix-tree: imple... |
355 |
return __radix_tree_preload(gfp_mask, RADIX_TREE_PRELOAD_SIZE); |
5e4c0d974 lib/radix-tree.c:... |
356 |
/* Preloading doesn't help anything with this gfp mask, skip it */ |
cfa6705d8 radix-tree: Use l... |
357 |
local_lock(&radix_tree_preloads.lock); |
5e4c0d974 lib/radix-tree.c:... |
358 359 360 |
return 0; } EXPORT_SYMBOL(radix_tree_maybe_preload); |
35534c869 radix tree: const... |
361 |
static unsigned radix_tree_load_root(const struct radix_tree_root *root, |
1456a439f radix-tree: intro... |
362 363 |
struct radix_tree_node **nodep, unsigned long *maxindex) { |
f8d5d0cc1 xarray: Add defin... |
364 |
struct radix_tree_node *node = rcu_dereference_raw(root->xa_head); |
1456a439f radix-tree: intro... |
365 366 |
*nodep = node; |
b194d16c2 radix-tree: renam... |
367 |
if (likely(radix_tree_is_internal_node(node))) { |
4dd6c0987 radix-tree: renam... |
368 |
node = entry_to_node(node); |
1456a439f radix-tree: intro... |
369 |
*maxindex = node_maxindex(node); |
c12e51b07 radix-tree: repla... |
370 |
return node->shift + RADIX_TREE_MAP_SHIFT; |
1456a439f radix-tree: intro... |
371 372 373 374 375 |
} *maxindex = 0; return 0; } |
1da177e4c Linux-2.6.12-rc2 |
376 377 378 |
/* * Extend a radix tree so it can store key @index. */ |
0a835c4f0 Reimplement IDR a... |
379 |
static int radix_tree_extend(struct radix_tree_root *root, gfp_t gfp, |
d0891265b radix-tree: remov... |
380 |
unsigned long index, unsigned int shift) |
1da177e4c Linux-2.6.12-rc2 |
381 |
{ |
d7b627277 radix-tree: Fix _... |
382 |
void *entry; |
d0891265b radix-tree: remov... |
383 |
unsigned int maxshift; |
1da177e4c Linux-2.6.12-rc2 |
384 |
int tag; |
d0891265b radix-tree: remov... |
385 386 387 388 |
/* 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 |
389 |
|
f8d5d0cc1 xarray: Add defin... |
390 |
entry = rcu_dereference_raw(root->xa_head); |
d7b627277 radix-tree: Fix _... |
391 |
if (!entry && (!is_idr(root) || root_tag_get(root, IDR_FREE))) |
1da177e4c Linux-2.6.12-rc2 |
392 |
goto out; |
1da177e4c Linux-2.6.12-rc2 |
393 |
|
1da177e4c Linux-2.6.12-rc2 |
394 |
do { |
0a835c4f0 Reimplement IDR a... |
395 |
struct radix_tree_node *node = radix_tree_node_alloc(gfp, NULL, |
d58275bc9 radix-tree: Store... |
396 |
root, shift, 0, 1, 0); |
2fcd9005c radix-tree: misce... |
397 |
if (!node) |
1da177e4c Linux-2.6.12-rc2 |
398 |
return -ENOMEM; |
0a835c4f0 Reimplement IDR a... |
399 400 401 402 403 404 405 406 407 408 409 410 |
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 |
411 |
} |
d0891265b radix-tree: remov... |
412 |
BUG_ON(shift > BITS_PER_LONG); |
d7b627277 radix-tree: Fix _... |
413 414 |
if (radix_tree_is_internal_node(entry)) { entry_to_node(entry)->parent = node; |
3159f943a xarray: Replace e... |
415 |
} else if (xa_is_value(entry)) { |
01959dfe7 xarray: Define st... |
416 417 |
/* Moving a value entry root->xa_head to a node */ node->nr_values = 1; |
f7942430e lib: radix-tree: ... |
418 |
} |
d7b627277 radix-tree: Fix _... |
419 420 421 422 423 424 |
/* * 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); |
f8d5d0cc1 xarray: Add defin... |
425 |
rcu_assign_pointer(root->xa_head, entry); |
d0891265b radix-tree: remov... |
426 |
shift += RADIX_TREE_MAP_SHIFT; |
d0891265b radix-tree: remov... |
427 |
} while (shift <= maxshift); |
1da177e4c Linux-2.6.12-rc2 |
428 |
out: |
d0891265b radix-tree: remov... |
429 |
return maxshift + RADIX_TREE_MAP_SHIFT; |
1da177e4c Linux-2.6.12-rc2 |
430 431 432 |
} /** |
f4b109c6d lib: radix-tree: ... |
433 434 435 |
* radix_tree_shrink - shrink radix tree to minimum height * @root radix tree root */ |
1cf56f9d6 radix tree: Remov... |
436 |
static inline bool radix_tree_shrink(struct radix_tree_root *root) |
f4b109c6d lib: radix-tree: ... |
437 |
{ |
0ac398ef3 radix-tree: Add r... |
438 |
bool shrunk = false; |
f4b109c6d lib: radix-tree: ... |
439 |
for (;;) { |
f8d5d0cc1 xarray: Add defin... |
440 |
struct radix_tree_node *node = rcu_dereference_raw(root->xa_head); |
f4b109c6d lib: radix-tree: ... |
441 442 443 444 445 446 447 448 |
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 |
3a08cd52c radix tree: Remov... |
449 |
* is not at the leftmost slot, we cannot shrink. |
f4b109c6d lib: radix-tree: ... |
450 451 452 |
*/ if (node->count != 1) break; |
12320d0ff radix-tree: Add r... |
453 |
child = rcu_dereference_raw(node->slots[0]); |
f4b109c6d lib: radix-tree: ... |
454 455 |
if (!child) break; |
f4b109c6d lib: radix-tree: ... |
456 |
|
66ee620f0 idr: Permit any v... |
457 458 459 460 461 462 463 |
/* * For an IDR, we must not shrink entry 0 into the root in * case somebody calls idr_replace() with a pointer that * appears to be an internal entry */ if (!node->shift && is_idr(root)) break; |
f4b109c6d lib: radix-tree: ... |
464 465 466 467 468 469 470 471 |
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 |
f8d5d0cc1 xarray: Add defin... |
472 |
* one (root->xa_head) as far as dependent read barriers go. |
f4b109c6d lib: radix-tree: ... |
473 |
*/ |
f8d5d0cc1 xarray: Add defin... |
474 |
root->xa_head = (void __rcu *)child; |
0a835c4f0 Reimplement IDR a... |
475 476 |
if (is_idr(root) && !tag_get(node, IDR_FREE, 0)) root_tag_clear(root, IDR_FREE); |
f4b109c6d lib: radix-tree: ... |
477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 |
/* * 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: ... |
496 497 |
node->count = 0; if (!radix_tree_is_internal_node(child)) { |
d7b627277 radix-tree: Fix _... |
498 |
node->slots[0] = (void __rcu *)RADIX_TREE_RETRY; |
4d693d086 lib: radix-tree: ... |
499 |
} |
f4b109c6d lib: radix-tree: ... |
500 |
|
ea07b862a mm: workingset: f... |
501 |
WARN_ON_ONCE(!list_empty(&node->private_list)); |
f4b109c6d lib: radix-tree: ... |
502 |
radix_tree_node_free(node); |
0ac398ef3 radix-tree: Add r... |
503 |
shrunk = true; |
f4b109c6d lib: radix-tree: ... |
504 |
} |
0ac398ef3 radix-tree: Add r... |
505 506 |
return shrunk; |
f4b109c6d lib: radix-tree: ... |
507 |
} |
0ac398ef3 radix-tree: Add r... |
508 |
static bool delete_node(struct radix_tree_root *root, |
1cf56f9d6 radix tree: Remov... |
509 |
struct radix_tree_node *node) |
f4b109c6d lib: radix-tree: ... |
510 |
{ |
0ac398ef3 radix-tree: Add r... |
511 |
bool deleted = false; |
f4b109c6d lib: radix-tree: ... |
512 513 514 515 |
do { struct radix_tree_node *parent; if (node->count) { |
12320d0ff radix-tree: Add r... |
516 |
if (node_to_entry(node) == |
f8d5d0cc1 xarray: Add defin... |
517 |
rcu_dereference_raw(root->xa_head)) |
1cf56f9d6 radix tree: Remov... |
518 |
deleted |= radix_tree_shrink(root); |
0ac398ef3 radix-tree: Add r... |
519 |
return deleted; |
f4b109c6d lib: radix-tree: ... |
520 521 522 523 524 525 526 |
} parent = node->parent; if (parent) { parent->slots[node->offset] = NULL; parent->count--; } else { |
0a835c4f0 Reimplement IDR a... |
527 528 529 530 531 532 |
/* * Shouldn't the tags already have all been cleared * by the caller? */ if (!is_idr(root)) root_tag_clear_all(root); |
f8d5d0cc1 xarray: Add defin... |
533 |
root->xa_head = NULL; |
f4b109c6d lib: radix-tree: ... |
534 |
} |
ea07b862a mm: workingset: f... |
535 |
WARN_ON_ONCE(!list_empty(&node->private_list)); |
f4b109c6d lib: radix-tree: ... |
536 |
radix_tree_node_free(node); |
0ac398ef3 radix-tree: Add r... |
537 |
deleted = true; |
f4b109c6d lib: radix-tree: ... |
538 539 540 |
node = parent; } while (node); |
0ac398ef3 radix-tree: Add r... |
541 542 |
return deleted; |
f4b109c6d lib: radix-tree: ... |
543 544 545 |
} /** |
139e56166 lib: radix_tree: ... |
546 |
* __radix_tree_create - create a slot in a radix tree |
1da177e4c Linux-2.6.12-rc2 |
547 548 |
* @root: radix tree root * @index: index key |
139e56166 lib: radix_tree: ... |
549 550 |
* @nodep: returns node * @slotp: returns slot |
1da177e4c Linux-2.6.12-rc2 |
551 |
* |
139e56166 lib: radix_tree: ... |
552 553 554 555 |
* 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 |
f8d5d0cc1 xarray: Add defin... |
556 |
* allocated and @root->xa_head is used as a direct slot instead of |
139e56166 lib: radix_tree: ... |
557 558 559 |
* pointing to a node, in which case *@nodep will be NULL. * * Returns -ENOMEM, or 0 for success. |
1da177e4c Linux-2.6.12-rc2 |
560 |
*/ |
74d609585 page cache: Add a... |
561 |
static int __radix_tree_create(struct radix_tree_root *root, |
3a08cd52c radix tree: Remov... |
562 563 |
unsigned long index, struct radix_tree_node **nodep, void __rcu ***slotp) |
1da177e4c Linux-2.6.12-rc2 |
564 |
{ |
89148aa40 radix-tree: tidy ... |
565 |
struct radix_tree_node *node = NULL, *child; |
f8d5d0cc1 xarray: Add defin... |
566 |
void __rcu **slot = (void __rcu **)&root->xa_head; |
49ea6ebcd radix-tree: fix e... |
567 |
unsigned long maxindex; |
89148aa40 radix-tree: tidy ... |
568 |
unsigned int shift, offset = 0; |
3a08cd52c radix tree: Remov... |
569 |
unsigned long max = index; |
0a835c4f0 Reimplement IDR a... |
570 |
gfp_t gfp = root_gfp_mask(root); |
49ea6ebcd radix-tree: fix e... |
571 |
|
89148aa40 radix-tree: tidy ... |
572 |
shift = radix_tree_load_root(root, &child, &maxindex); |
1da177e4c Linux-2.6.12-rc2 |
573 574 |
/* Make sure the tree is high enough. */ |
49ea6ebcd radix-tree: fix e... |
575 |
if (max > maxindex) { |
0a835c4f0 Reimplement IDR a... |
576 |
int error = radix_tree_extend(root, gfp, max, shift); |
49ea6ebcd radix-tree: fix e... |
577 |
if (error < 0) |
1da177e4c Linux-2.6.12-rc2 |
578 |
return error; |
49ea6ebcd radix-tree: fix e... |
579 |
shift = error; |
f8d5d0cc1 xarray: Add defin... |
580 |
child = rcu_dereference_raw(root->xa_head); |
1da177e4c Linux-2.6.12-rc2 |
581 |
} |
3a08cd52c radix tree: Remov... |
582 |
while (shift > 0) { |
c12e51b07 radix-tree: repla... |
583 |
shift -= RADIX_TREE_MAP_SHIFT; |
89148aa40 radix-tree: tidy ... |
584 |
if (child == NULL) { |
1da177e4c Linux-2.6.12-rc2 |
585 |
/* Have to add a child node. */ |
d58275bc9 radix-tree: Store... |
586 |
child = radix_tree_node_alloc(gfp, node, root, shift, |
e8de43407 radix-tree: ensur... |
587 |
offset, 0, 0); |
89148aa40 radix-tree: tidy ... |
588 |
if (!child) |
1da177e4c Linux-2.6.12-rc2 |
589 |
return -ENOMEM; |
89148aa40 radix-tree: tidy ... |
590 591 |
rcu_assign_pointer(*slot, node_to_entry(child)); if (node) |
1da177e4c Linux-2.6.12-rc2 |
592 |
node->count++; |
89148aa40 radix-tree: tidy ... |
593 |
} else if (!radix_tree_is_internal_node(child)) |
e61452365 radix_tree: add s... |
594 |
break; |
1da177e4c Linux-2.6.12-rc2 |
595 596 |
/* Go a level down */ |
89148aa40 radix-tree: tidy ... |
597 |
node = entry_to_node(child); |
9e85d8111 radix-tree: make ... |
598 |
offset = radix_tree_descend(node, &child, index); |
89148aa40 radix-tree: tidy ... |
599 |
slot = &node->slots[offset]; |
e61452365 radix_tree: add s... |
600 |
} |
175542f57 radix-tree: add r... |
601 602 603 604 605 606 |
if (nodep) *nodep = node; if (slotp) *slotp = slot; return 0; } |
175542f57 radix-tree: add r... |
607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 |
/* * 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... |
622 |
void *entry = rcu_dereference_raw(child->slots[offset]); |
02c02bf12 xarray: Change de... |
623 |
if (xa_is_node(entry) && child->shift) { |
175542f57 radix-tree: add r... |
624 625 626 627 628 629 630 631 632 |
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... |
633 |
WARN_ON_ONCE(!list_empty(&old->private_list)); |
175542f57 radix-tree: add r... |
634 635 636 637 638 639 |
radix_tree_node_free(old); if (old == entry_to_node(node)) return; } } } |
d7b627277 radix-tree: Fix _... |
640 |
static inline int insert_entries(struct radix_tree_node *node, |
3a08cd52c radix tree: Remov... |
641 |
void __rcu **slot, void *item, bool replace) |
175542f57 radix-tree: add r... |
642 643 644 645 646 647 |
{ if (*slot) return -EEXIST; rcu_assign_pointer(*slot, item); if (node) { node->count++; |
3159f943a xarray: Replace e... |
648 |
if (xa_is_value(item)) |
01959dfe7 xarray: Define st... |
649 |
node->nr_values++; |
175542f57 radix-tree: add r... |
650 651 652 |
} return 1; } |
139e56166 lib: radix_tree: ... |
653 654 |
/** |
e61452365 radix_tree: add s... |
655 |
* __radix_tree_insert - insert into a radix tree |
139e56166 lib: radix_tree: ... |
656 657 658 659 660 661 |
* @root: radix tree root * @index: index key * @item: item to insert * * Insert an item into the radix tree at position @index. */ |
3a08cd52c radix tree: Remov... |
662 663 |
int radix_tree_insert(struct radix_tree_root *root, unsigned long index, void *item) |
139e56166 lib: radix_tree: ... |
664 665 |
{ struct radix_tree_node *node; |
d7b627277 radix-tree: Fix _... |
666 |
void __rcu **slot; |
139e56166 lib: radix_tree: ... |
667 |
int error; |
b194d16c2 radix-tree: renam... |
668 |
BUG_ON(radix_tree_is_internal_node(item)); |
139e56166 lib: radix_tree: ... |
669 |
|
3a08cd52c radix tree: Remov... |
670 |
error = __radix_tree_create(root, index, &node, &slot); |
139e56166 lib: radix_tree: ... |
671 672 |
if (error) return error; |
175542f57 radix-tree: add r... |
673 |
|
3a08cd52c radix tree: Remov... |
674 |
error = insert_entries(node, slot, item, false); |
175542f57 radix-tree: add r... |
675 676 |
if (error < 0) return error; |
201b6264f [PATCH] radix-tre... |
677 |
|
612d6c19d [PATCH] radix-tre... |
678 |
if (node) { |
7b60e9ad5 radix-tree: fix m... |
679 |
unsigned offset = get_slot_offset(node, slot); |
7b60e9ad5 radix-tree: fix m... |
680 681 682 |
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... |
683 |
} else { |
7b60e9ad5 radix-tree: fix m... |
684 |
BUG_ON(root_tags_get(root)); |
612d6c19d [PATCH] radix-tre... |
685 |
} |
1da177e4c Linux-2.6.12-rc2 |
686 |
|
1da177e4c Linux-2.6.12-rc2 |
687 688 |
return 0; } |
3a08cd52c radix tree: Remov... |
689 |
EXPORT_SYMBOL(radix_tree_insert); |
1da177e4c Linux-2.6.12-rc2 |
690 |
|
139e56166 lib: radix_tree: ... |
691 692 693 694 695 696 697 698 699 700 701 |
/** * __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 |
f8d5d0cc1 xarray: Add defin... |
702 |
* allocated and @root->xa_head is used as a direct slot instead of |
139e56166 lib: radix_tree: ... |
703 |
* pointing to a node, in which case *@nodep will be NULL. |
7cf9c2c76 [PATCH] radix-tre... |
704 |
*/ |
35534c869 radix tree: const... |
705 706 |
void *__radix_tree_lookup(const struct radix_tree_root *root, unsigned long index, struct radix_tree_node **nodep, |
d7b627277 radix-tree: Fix _... |
707 |
void __rcu ***slotp) |
1da177e4c Linux-2.6.12-rc2 |
708 |
{ |
139e56166 lib: radix_tree: ... |
709 |
struct radix_tree_node *node, *parent; |
858299544 radix-tree: rewri... |
710 |
unsigned long maxindex; |
d7b627277 radix-tree: Fix _... |
711 |
void __rcu **slot; |
612d6c19d [PATCH] radix-tre... |
712 |
|
858299544 radix-tree: rewri... |
713 714 |
restart: parent = NULL; |
f8d5d0cc1 xarray: Add defin... |
715 |
slot = (void __rcu **)&root->xa_head; |
9e85d8111 radix-tree: make ... |
716 |
radix_tree_load_root(root, &node, &maxindex); |
858299544 radix-tree: rewri... |
717 |
if (index > maxindex) |
1da177e4c Linux-2.6.12-rc2 |
718 |
return NULL; |
b194d16c2 radix-tree: renam... |
719 |
while (radix_tree_is_internal_node(node)) { |
858299544 radix-tree: rewri... |
720 |
unsigned offset; |
1da177e4c Linux-2.6.12-rc2 |
721 |
|
4dd6c0987 radix-tree: renam... |
722 |
parent = entry_to_node(node); |
9e85d8111 radix-tree: make ... |
723 |
offset = radix_tree_descend(parent, &node, index); |
858299544 radix-tree: rewri... |
724 |
slot = parent->slots + offset; |
eff3860bb radix tree: Don't... |
725 726 |
if (node == RADIX_TREE_RETRY) goto restart; |
66ee620f0 idr: Permit any v... |
727 728 |
if (parent->shift == 0) break; |
858299544 radix-tree: rewri... |
729 |
} |
1da177e4c Linux-2.6.12-rc2 |
730 |
|
139e56166 lib: radix_tree: ... |
731 732 733 734 735 |
if (nodep) *nodep = parent; if (slotp) *slotp = slot; return node; |
b72b71c6c lib: do code opti... |
736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 |
} /** * 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 _... |
751 |
void __rcu **radix_tree_lookup_slot(const struct radix_tree_root *root, |
35534c869 radix tree: const... |
752 |
unsigned long index) |
b72b71c6c lib: do code opti... |
753 |
{ |
d7b627277 radix-tree: Fix _... |
754 |
void __rcu **slot; |
139e56166 lib: radix_tree: ... |
755 756 757 758 |
if (!__radix_tree_lookup(root, index, NULL, &slot)) return NULL; return slot; |
a43313668 [PATCH] reiser4: ... |
759 |
} |
a43313668 [PATCH] reiser4: ... |
760 761 762 763 764 765 766 767 |
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... |
768 769 770 771 772 |
* * 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: ... |
773 |
*/ |
35534c869 radix tree: const... |
774 |
void *radix_tree_lookup(const struct radix_tree_root *root, unsigned long index) |
a43313668 [PATCH] reiser4: ... |
775 |
{ |
139e56166 lib: radix_tree: ... |
776 |
return __radix_tree_lookup(root, index, NULL, NULL); |
1da177e4c Linux-2.6.12-rc2 |
777 778 |
} EXPORT_SYMBOL(radix_tree_lookup); |
d7b627277 radix-tree: Fix _... |
779 |
static void replace_slot(void __rcu **slot, void *item, |
01959dfe7 xarray: Define st... |
780 |
struct radix_tree_node *node, int count, int values) |
f7942430e lib: radix-tree: ... |
781 |
{ |
01959dfe7 xarray: Define st... |
782 |
if (node && (count || values)) { |
f4b109c6d lib: radix-tree: ... |
783 |
node->count += count; |
01959dfe7 xarray: Define st... |
784 |
node->nr_values += values; |
f4b109c6d lib: radix-tree: ... |
785 |
} |
f7942430e lib: radix-tree: ... |
786 787 788 |
rcu_assign_pointer(*slot, item); } |
0a835c4f0 Reimplement IDR a... |
789 790 791 |
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... |
792 |
{ |
0a835c4f0 Reimplement IDR a... |
793 794 795 796 |
if (node) return tag_get(node, tag, offset); return root_tag_get(root, tag); } |
a90eb3a2a radix-tree: fix r... |
797 |
|
0a835c4f0 Reimplement IDR a... |
798 799 800 801 802 803 804 805 |
/* * 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 _... |
806 |
struct radix_tree_node *node, void __rcu **slot, |
0a835c4f0 Reimplement IDR a... |
807 808 809 810 811 812 813 814 815 |
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... |
816 |
} |
0a835c4f0 Reimplement IDR a... |
817 |
return !!item - !!old; |
a90eb3a2a radix-tree: fix r... |
818 |
} |
f7942430e lib: radix-tree: ... |
819 |
/** |
6d75f366b lib: radix-tree: ... |
820 |
* __radix_tree_replace - replace item in a slot |
4d693d086 lib: radix-tree: ... |
821 822 823 824 |
* @root: radix tree root * @node: pointer to tree node * @slot: pointer to slot in @node * @item: new item to store in the slot. |
6d75f366b lib: radix-tree: ... |
825 826 827 828 829 830 |
* * 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, |
1cf56f9d6 radix tree: Remov... |
831 |
void __rcu **slot, void *item) |
6d75f366b lib: radix-tree: ... |
832 |
{ |
0a835c4f0 Reimplement IDR a... |
833 |
void *old = rcu_dereference_raw(*slot); |
01959dfe7 xarray: Define st... |
834 |
int values = !!xa_is_value(item) - !!xa_is_value(old); |
0a835c4f0 Reimplement IDR a... |
835 |
int count = calculate_count(root, node, slot, item, old); |
6d75f366b lib: radix-tree: ... |
836 |
/* |
01959dfe7 xarray: Define st... |
837 |
* This function supports replacing value entries and |
f4b109c6d lib: radix-tree: ... |
838 |
* deleting entries, but that needs accounting against the |
f8d5d0cc1 xarray: Add defin... |
839 |
* node unless the slot is root->xa_head. |
6d75f366b lib: radix-tree: ... |
840 |
*/ |
f8d5d0cc1 xarray: Add defin... |
841 |
WARN_ON_ONCE(!node && (slot != (void __rcu **)&root->xa_head) && |
01959dfe7 xarray: Define st... |
842 843 |
(count || values)); replace_slot(slot, item, node, count, values); |
f4b109c6d lib: radix-tree: ... |
844 |
|
4d693d086 lib: radix-tree: ... |
845 846 |
if (!node) return; |
1cf56f9d6 radix tree: Remov... |
847 |
delete_node(root, node); |
6d75f366b lib: radix-tree: ... |
848 849 850 851 852 853 854 855 |
} /** * 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. * |
7b8d046fb shmem: Convert sh... |
856 |
* For use with radix_tree_lookup_slot() and |
6d75f366b lib: radix-tree: ... |
857 858 859 860 |
* 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), |
01959dfe7 xarray: Define st... |
861 |
* regular entries, and value entries, as that requires accounting |
f4b109c6d lib: radix-tree: ... |
862 |
* inside the radix tree node. When switching from one type of entry or |
e157b5559 radix-tree: add r... |
863 864 |
* deleting, use __radix_tree_lookup() and __radix_tree_replace() or * radix_tree_iter_replace(). |
6d75f366b lib: radix-tree: ... |
865 866 |
*/ void radix_tree_replace_slot(struct radix_tree_root *root, |
d7b627277 radix-tree: Fix _... |
867 |
void __rcu **slot, void *item) |
6d75f366b lib: radix-tree: ... |
868 |
{ |
1cf56f9d6 radix tree: Remov... |
869 |
__radix_tree_replace(root, NULL, slot, item); |
6d75f366b lib: radix-tree: ... |
870 |
} |
10257d719 EXPORT_SYMBOL rad... |
871 |
EXPORT_SYMBOL(radix_tree_replace_slot); |
6d75f366b lib: radix-tree: ... |
872 |
|
e157b5559 radix-tree: add r... |
873 874 875 876 877 878 |
/** * 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. * |
2956c6644 radix tree: Remov... |
879 880 |
* For use with radix_tree_for_each_slot(). * Caller must hold tree write locked. |
e157b5559 radix-tree: add r... |
881 882 |
*/ void radix_tree_iter_replace(struct radix_tree_root *root, |
d7b627277 radix-tree: Fix _... |
883 884 |
const struct radix_tree_iter *iter, void __rcu **slot, void *item) |
e157b5559 radix-tree: add r... |
885 |
{ |
1cf56f9d6 radix tree: Remov... |
886 |
__radix_tree_replace(root, iter->node, slot, item); |
e157b5559 radix-tree: add r... |
887 |
} |
30b888ba9 radix-tree: Add r... |
888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 |
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 |
903 904 905 906 |
/** * radix_tree_tag_set - set a tag on a radix tree node * @root: radix tree root * @index: index key |
2fcd9005c radix-tree: misce... |
907 |
* @tag: tag index |
1da177e4c Linux-2.6.12-rc2 |
908 |
* |
daff89f32 [PATCH] radix-tre... |
909 910 |
* 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 |
911 912 |
* the root all the way down to the leaf node. * |
2fcd9005c radix-tree: misce... |
913 |
* Returns the address of the tagged item. Setting a tag on a not-present |
1da177e4c Linux-2.6.12-rc2 |
914 915 916 |
* item is a bug. */ void *radix_tree_tag_set(struct radix_tree_root *root, |
daff89f32 [PATCH] radix-tre... |
917 |
unsigned long index, unsigned int tag) |
1da177e4c Linux-2.6.12-rc2 |
918 |
{ |
fb969909d radix-tree: rewri... |
919 920 |
struct radix_tree_node *node, *parent; unsigned long maxindex; |
1da177e4c Linux-2.6.12-rc2 |
921 |
|
9e85d8111 radix-tree: make ... |
922 |
radix_tree_load_root(root, &node, &maxindex); |
fb969909d radix-tree: rewri... |
923 |
BUG_ON(index > maxindex); |
1da177e4c Linux-2.6.12-rc2 |
924 |
|
b194d16c2 radix-tree: renam... |
925 |
while (radix_tree_is_internal_node(node)) { |
fb969909d radix-tree: rewri... |
926 |
unsigned offset; |
1da177e4c Linux-2.6.12-rc2 |
927 |
|
4dd6c0987 radix-tree: renam... |
928 |
parent = entry_to_node(node); |
9e85d8111 radix-tree: make ... |
929 |
offset = radix_tree_descend(parent, &node, index); |
fb969909d radix-tree: rewri... |
930 931 932 933 |
BUG_ON(!node); if (!tag_get(parent, tag, offset)) tag_set(parent, tag, offset); |
1da177e4c Linux-2.6.12-rc2 |
934 |
} |
612d6c19d [PATCH] radix-tre... |
935 |
/* set the root's tag bit */ |
fb969909d radix-tree: rewri... |
936 |
if (!root_tag_get(root, tag)) |
612d6c19d [PATCH] radix-tre... |
937 |
root_tag_set(root, tag); |
fb969909d radix-tree: rewri... |
938 |
return node; |
1da177e4c Linux-2.6.12-rc2 |
939 940 |
} EXPORT_SYMBOL(radix_tree_tag_set); |
d604c3245 radix-tree: intro... |
941 942 943 944 945 946 947 948 949 950 951 952 953 954 955 956 957 958 959 |
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... |
960 |
/** |
1da177e4c Linux-2.6.12-rc2 |
961 962 963 |
* radix_tree_tag_clear - clear a tag on a radix tree node * @root: radix tree root * @index: index key |
2fcd9005c radix-tree: misce... |
964 |
* @tag: tag index |
1da177e4c Linux-2.6.12-rc2 |
965 |
* |
daff89f32 [PATCH] radix-tre... |
966 |
* Clear the search tag (which must be < RADIX_TREE_MAX_TAGS) |
2fcd9005c radix-tree: misce... |
967 968 |
* 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 |
969 970 971 972 973 974 |
* 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... |
975 |
unsigned long index, unsigned int tag) |
1da177e4c Linux-2.6.12-rc2 |
976 |
{ |
00f47b581 radix-tree: rewri... |
977 978 |
struct radix_tree_node *node, *parent; unsigned long maxindex; |
3f649ab72 treewide: Remove ... |
979 |
int offset; |
1da177e4c Linux-2.6.12-rc2 |
980 |
|
9e85d8111 radix-tree: make ... |
981 |
radix_tree_load_root(root, &node, &maxindex); |
00f47b581 radix-tree: rewri... |
982 983 |
if (index > maxindex) return NULL; |
1da177e4c Linux-2.6.12-rc2 |
984 |
|
00f47b581 radix-tree: rewri... |
985 |
parent = NULL; |
1da177e4c Linux-2.6.12-rc2 |
986 |
|
b194d16c2 radix-tree: renam... |
987 |
while (radix_tree_is_internal_node(node)) { |
4dd6c0987 radix-tree: renam... |
988 |
parent = entry_to_node(node); |
9e85d8111 radix-tree: make ... |
989 |
offset = radix_tree_descend(parent, &node, index); |
1da177e4c Linux-2.6.12-rc2 |
990 |
} |
d604c3245 radix-tree: intro... |
991 992 |
if (node) node_tag_clear(root, parent, tag, offset); |
1da177e4c Linux-2.6.12-rc2 |
993 |
|
00f47b581 radix-tree: rewri... |
994 |
return node; |
1da177e4c Linux-2.6.12-rc2 |
995 996 |
} EXPORT_SYMBOL(radix_tree_tag_clear); |
1da177e4c Linux-2.6.12-rc2 |
997 |
/** |
30b888ba9 radix-tree: Add r... |
998 999 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 |
* 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... |
1010 1011 1012 |
* radix_tree_tag_get - get a tag on a radix tree node * @root: radix tree root * @index: index key |
2fcd9005c radix-tree: misce... |
1013 |
* @tag: tag index (< RADIX_TREE_MAX_TAGS) |
1da177e4c Linux-2.6.12-rc2 |
1014 |
* |
32605a181 [PATCH] radix_tag... |
1015 |
* Return values: |
1da177e4c Linux-2.6.12-rc2 |
1016 |
* |
612d6c19d [PATCH] radix-tre... |
1017 1018 |
* 0: tag not present or not set * 1: tag set |
ce82653d6 radix_tree_tag_ge... |
1019 1020 1021 1022 |
* * 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 |
1023 |
*/ |
35534c869 radix tree: const... |
1024 |
int radix_tree_tag_get(const struct radix_tree_root *root, |
daff89f32 [PATCH] radix-tre... |
1025 |
unsigned long index, unsigned int tag) |
1da177e4c Linux-2.6.12-rc2 |
1026 |
{ |
4589ba6d0 radix-tree: rewri... |
1027 1028 |
struct radix_tree_node *node, *parent; unsigned long maxindex; |
1da177e4c Linux-2.6.12-rc2 |
1029 |
|
612d6c19d [PATCH] radix-tre... |
1030 1031 |
if (!root_tag_get(root, tag)) return 0; |
9e85d8111 radix-tree: make ... |
1032 |
radix_tree_load_root(root, &node, &maxindex); |
4589ba6d0 radix-tree: rewri... |
1033 1034 |
if (index > maxindex) return 0; |
7cf9c2c76 [PATCH] radix-tre... |
1035 |
|
b194d16c2 radix-tree: renam... |
1036 |
while (radix_tree_is_internal_node(node)) { |
9e85d8111 radix-tree: make ... |
1037 |
unsigned offset; |
1da177e4c Linux-2.6.12-rc2 |
1038 |
|
4dd6c0987 radix-tree: renam... |
1039 |
parent = entry_to_node(node); |
9e85d8111 radix-tree: make ... |
1040 |
offset = radix_tree_descend(parent, &node, index); |
1da177e4c Linux-2.6.12-rc2 |
1041 |
|
4589ba6d0 radix-tree: rewri... |
1042 |
if (!tag_get(parent, tag, offset)) |
3fa36acbc radix_tree: clean... |
1043 |
return 0; |
4589ba6d0 radix-tree: rewri... |
1044 1045 |
if (node == RADIX_TREE_RETRY) break; |
1da177e4c Linux-2.6.12-rc2 |
1046 |
} |
4589ba6d0 radix-tree: rewri... |
1047 1048 |
return 1; |
1da177e4c Linux-2.6.12-rc2 |
1049 1050 |
} EXPORT_SYMBOL(radix_tree_tag_get); |
1da177e4c Linux-2.6.12-rc2 |
1051 |
|
148deab22 radix-tree: impro... |
1052 1053 1054 1055 1056 1057 1058 |
/* 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... |
1059 1060 1061 1062 |
if (!node) { iter->tags = 1; return; } |
148deab22 radix-tree: impro... |
1063 1064 1065 1066 1067 1068 1069 1070 1071 1072 1073 1074 |
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); } } |
d7b627277 radix-tree: Fix _... |
1075 1076 |
void __rcu **radix_tree_iter_resume(void __rcu **slot, struct radix_tree_iter *iter) |
148deab22 radix-tree: impro... |
1077 |
{ |
148deab22 radix-tree: impro... |
1078 1079 |
slot++; iter->index = __radix_tree_iter_add(iter, 1); |
148deab22 radix-tree: impro... |
1080 1081 1082 1083 1084 |
iter->next_index = iter->index; iter->tags = 0; return NULL; } EXPORT_SYMBOL(radix_tree_iter_resume); |
6df8ba4f8 radixtree: introd... |
1085 |
/** |
78c1d7848 radix-tree: intro... |
1086 1087 1088 1089 1090 1091 1092 |
* 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 _... |
1093 |
void __rcu **radix_tree_next_chunk(const struct radix_tree_root *root, |
78c1d7848 radix-tree: intro... |
1094 1095 |
struct radix_tree_iter *iter, unsigned flags) { |
9e85d8111 radix-tree: make ... |
1096 |
unsigned tag = flags & RADIX_TREE_ITER_TAG_MASK; |
8c1244de0 radix-tree: tidy ... |
1097 |
struct radix_tree_node *node, *child; |
21ef53393 radix-tree: add s... |
1098 |
unsigned long index, offset, maxindex; |
78c1d7848 radix-tree: intro... |
1099 1100 1101 1102 1103 1104 1105 1106 1107 |
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... |
1108 1109 |
* * This condition also used by radix_tree_next_slot() to stop |
91b9677c4 radix-tree: fix typo |
1110 |
* contiguous iterating, and forbid switching to the next chunk. |
78c1d7848 radix-tree: intro... |
1111 1112 1113 1114 |
*/ index = iter->next_index; if (!index && iter->index) return NULL; |
21ef53393 radix-tree: add s... |
1115 |
restart: |
9e85d8111 radix-tree: make ... |
1116 |
radix_tree_load_root(root, &child, &maxindex); |
21ef53393 radix-tree: add s... |
1117 1118 |
if (index > maxindex) return NULL; |
8c1244de0 radix-tree: tidy ... |
1119 1120 |
if (!child) return NULL; |
21ef53393 radix-tree: add s... |
1121 |
|
8c1244de0 radix-tree: tidy ... |
1122 |
if (!radix_tree_is_internal_node(child)) { |
78c1d7848 radix-tree: intro... |
1123 |
/* Single-slot tree */ |
21ef53393 radix-tree: add s... |
1124 1125 |
iter->index = index; iter->next_index = maxindex + 1; |
78c1d7848 radix-tree: intro... |
1126 |
iter->tags = 1; |
268f42de7 radix-tree: delet... |
1127 |
iter->node = NULL; |
f8d5d0cc1 xarray: Add defin... |
1128 |
return (void __rcu **)&root->xa_head; |
8c1244de0 radix-tree: tidy ... |
1129 |
} |
21ef53393 radix-tree: add s... |
1130 |
|
8c1244de0 radix-tree: tidy ... |
1131 1132 |
do { node = entry_to_node(child); |
9e85d8111 radix-tree: make ... |
1133 |
offset = radix_tree_descend(node, &child, index); |
21ef53393 radix-tree: add s... |
1134 |
|
78c1d7848 radix-tree: intro... |
1135 |
if ((flags & RADIX_TREE_ITER_TAGGED) ? |
8c1244de0 radix-tree: tidy ... |
1136 |
!tag_get(node, tag, offset) : !child) { |
78c1d7848 radix-tree: intro... |
1137 1138 1139 1140 1141 |
/* Hole detected */ if (flags & RADIX_TREE_ITER_CONTIG) return NULL; if (flags & RADIX_TREE_ITER_TAGGED) |
bc412fca6 radix-tree: make ... |
1142 |
offset = radix_tree_find_next_bit(node, tag, |
78c1d7848 radix-tree: intro... |
1143 1144 1145 |
offset + 1); else while (++offset < RADIX_TREE_MAP_SIZE) { |
12320d0ff radix-tree: Add r... |
1146 1147 |
void *slot = rcu_dereference_raw( node->slots[offset]); |
21ef53393 radix-tree: add s... |
1148 |
if (slot) |
78c1d7848 radix-tree: intro... |
1149 1150 |
break; } |
8c1244de0 radix-tree: tidy ... |
1151 |
index &= ~node_maxindex(node); |
9e85d8111 radix-tree: make ... |
1152 |
index += offset << node->shift; |
78c1d7848 radix-tree: intro... |
1153 1154 1155 1156 1157 |
/* Overflow after ~0UL */ if (!index) return NULL; if (offset == RADIX_TREE_MAP_SIZE) goto restart; |
8c1244de0 radix-tree: tidy ... |
1158 |
child = rcu_dereference_raw(node->slots[offset]); |
78c1d7848 radix-tree: intro... |
1159 |
} |
e157b5559 radix-tree: add r... |
1160 |
if (!child) |
78c1d7848 radix-tree: intro... |
1161 |
goto restart; |
e157b5559 radix-tree: add r... |
1162 1163 |
if (child == RADIX_TREE_RETRY) break; |
66ee620f0 idr: Permit any v... |
1164 |
} while (node->shift && radix_tree_is_internal_node(child)); |
78c1d7848 radix-tree: intro... |
1165 1166 |
/* Update the iterator state */ |
3a08cd52c radix tree: Remov... |
1167 |
iter->index = (index &~ node_maxindex(node)) | offset; |
8c1244de0 radix-tree: tidy ... |
1168 |
iter->next_index = (index | node_maxindex(node)) + 1; |
268f42de7 radix-tree: delet... |
1169 |
iter->node = node; |
78c1d7848 radix-tree: intro... |
1170 |
|
148deab22 radix-tree: impro... |
1171 1172 |
if (flags & RADIX_TREE_ITER_TAGGED) set_iter_tags(iter, node, offset, tag); |
78c1d7848 radix-tree: intro... |
1173 1174 1175 1176 1177 1178 |
return node->slots + offset; } EXPORT_SYMBOL(radix_tree_next_chunk); /** |
1da177e4c Linux-2.6.12-rc2 |
1179 1180 1181 1182 1183 1184 1185 1186 1187 1188 1189 |
* 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... |
1190 1191 1192 |
* * 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... |
1193 1194 1195 1196 |
* 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 |
1197 1198 |
*/ unsigned int |
35534c869 radix tree: const... |
1199 |
radix_tree_gang_lookup(const struct radix_tree_root *root, void **results, |
1da177e4c Linux-2.6.12-rc2 |
1200 1201 |
unsigned long first_index, unsigned int max_items) { |
cebbd29e1 radix-tree: rewri... |
1202 |
struct radix_tree_iter iter; |
d7b627277 radix-tree: Fix _... |
1203 |
void __rcu **slot; |
cebbd29e1 radix-tree: rewri... |
1204 |
unsigned int ret = 0; |
7cf9c2c76 [PATCH] radix-tre... |
1205 |
|
cebbd29e1 radix-tree: rewri... |
1206 |
if (unlikely(!max_items)) |
7cf9c2c76 [PATCH] radix-tre... |
1207 |
return 0; |
1da177e4c Linux-2.6.12-rc2 |
1208 |
|
cebbd29e1 radix-tree: rewri... |
1209 |
radix_tree_for_each_slot(slot, root, &iter, first_index) { |
46437f9a5 radix-tree: fix r... |
1210 |
results[ret] = rcu_dereference_raw(*slot); |
cebbd29e1 radix-tree: rewri... |
1211 1212 |
if (!results[ret]) continue; |
b194d16c2 radix-tree: renam... |
1213 |
if (radix_tree_is_internal_node(results[ret])) { |
46437f9a5 radix-tree: fix r... |
1214 1215 1216 |
slot = radix_tree_iter_retry(&iter); continue; } |
cebbd29e1 radix-tree: rewri... |
1217 |
if (++ret == max_items) |
1da177e4c Linux-2.6.12-rc2 |
1218 |
break; |
1da177e4c Linux-2.6.12-rc2 |
1219 |
} |
7cf9c2c76 [PATCH] radix-tre... |
1220 |
|
1da177e4c Linux-2.6.12-rc2 |
1221 1222 1223 |
return ret; } EXPORT_SYMBOL(radix_tree_gang_lookup); |
47feff2c8 radix-tree: add g... |
1224 |
/** |
1da177e4c Linux-2.6.12-rc2 |
1225 1226 1227 1228 1229 1230 |
* 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... |
1231 |
* @tag: the tag index (< RADIX_TREE_MAX_TAGS) |
1da177e4c Linux-2.6.12-rc2 |
1232 1233 1234 1235 1236 1237 |
* * 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... |
1238 |
radix_tree_gang_lookup_tag(const struct radix_tree_root *root, void **results, |
daff89f32 [PATCH] radix-tre... |
1239 1240 |
unsigned long first_index, unsigned int max_items, unsigned int tag) |
1da177e4c Linux-2.6.12-rc2 |
1241 |
{ |
cebbd29e1 radix-tree: rewri... |
1242 |
struct radix_tree_iter iter; |
d7b627277 radix-tree: Fix _... |
1243 |
void __rcu **slot; |
cebbd29e1 radix-tree: rewri... |
1244 |
unsigned int ret = 0; |
612d6c19d [PATCH] radix-tre... |
1245 |
|
cebbd29e1 radix-tree: rewri... |
1246 |
if (unlikely(!max_items)) |
7cf9c2c76 [PATCH] radix-tre... |
1247 |
return 0; |
cebbd29e1 radix-tree: rewri... |
1248 |
radix_tree_for_each_tagged(slot, root, &iter, first_index, tag) { |
46437f9a5 radix-tree: fix r... |
1249 |
results[ret] = rcu_dereference_raw(*slot); |
cebbd29e1 radix-tree: rewri... |
1250 1251 |
if (!results[ret]) continue; |
b194d16c2 radix-tree: renam... |
1252 |
if (radix_tree_is_internal_node(results[ret])) { |
46437f9a5 radix-tree: fix r... |
1253 1254 1255 |
slot = radix_tree_iter_retry(&iter); continue; } |
cebbd29e1 radix-tree: rewri... |
1256 |
if (++ret == max_items) |
1da177e4c Linux-2.6.12-rc2 |
1257 |
break; |
1da177e4c Linux-2.6.12-rc2 |
1258 |
} |
7cf9c2c76 [PATCH] radix-tre... |
1259 |
|
1da177e4c Linux-2.6.12-rc2 |
1260 1261 1262 1263 1264 |
return ret; } EXPORT_SYMBOL(radix_tree_gang_lookup_tag); /** |
47feff2c8 radix-tree: add g... |
1265 1266 1267 1268 1269 1270 1271 1272 1273 1274 1275 1276 1277 |
* 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... |
1278 |
radix_tree_gang_lookup_tag_slot(const struct radix_tree_root *root, |
d7b627277 radix-tree: Fix _... |
1279 |
void __rcu ***results, unsigned long first_index, |
35534c869 radix tree: const... |
1280 |
unsigned int max_items, unsigned int tag) |
47feff2c8 radix-tree: add g... |
1281 |
{ |
cebbd29e1 radix-tree: rewri... |
1282 |
struct radix_tree_iter iter; |
d7b627277 radix-tree: Fix _... |
1283 |
void __rcu **slot; |
cebbd29e1 radix-tree: rewri... |
1284 |
unsigned int ret = 0; |
47feff2c8 radix-tree: add g... |
1285 |
|
cebbd29e1 radix-tree: rewri... |
1286 |
if (unlikely(!max_items)) |
47feff2c8 radix-tree: add g... |
1287 |
return 0; |
cebbd29e1 radix-tree: rewri... |
1288 1289 1290 |
radix_tree_for_each_tagged(slot, root, &iter, first_index, tag) { results[ret] = slot; if (++ret == max_items) |
47feff2c8 radix-tree: add g... |
1291 |
break; |
47feff2c8 radix-tree: add g... |
1292 1293 1294 1295 1296 |
} return ret; } EXPORT_SYMBOL(radix_tree_gang_lookup_tag_slot); |
0ac398ef3 radix-tree: Add r... |
1297 |
static bool __radix_tree_delete(struct radix_tree_root *root, |
d7b627277 radix-tree: Fix _... |
1298 |
struct radix_tree_node *node, void __rcu **slot) |
0ac398ef3 radix-tree: Add r... |
1299 |
{ |
0a835c4f0 Reimplement IDR a... |
1300 |
void *old = rcu_dereference_raw(*slot); |
01959dfe7 xarray: Define st... |
1301 |
int values = xa_is_value(old) ? -1 : 0; |
0ac398ef3 radix-tree: Add r... |
1302 1303 |
unsigned offset = get_slot_offset(node, slot); int tag; |
0a835c4f0 Reimplement IDR a... |
1304 1305 1306 1307 1308 |
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... |
1309 |
|
01959dfe7 xarray: Define st... |
1310 |
replace_slot(slot, NULL, node, -1, values); |
1cf56f9d6 radix tree: Remov... |
1311 |
return node && delete_node(root, node); |
0ac398ef3 radix-tree: Add r... |
1312 |
} |
139e56166 lib: radix_tree: ... |
1313 |
/** |
0ac398ef3 radix-tree: Add r... |
1314 1315 1316 1317 |
* 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 |
1318 |
* |
0ac398ef3 radix-tree: Add r... |
1319 1320 1321 1322 1323 1324 1325 |
* 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 _... |
1326 |
struct radix_tree_iter *iter, void __rcu **slot) |
0ac398ef3 radix-tree: Add r... |
1327 1328 1329 1330 |
{ if (__radix_tree_delete(root, iter->node, slot)) iter->index = iter->next_index; } |
d1b48c1e7 drm/i915: Replace... |
1331 |
EXPORT_SYMBOL(radix_tree_iter_delete); |
0ac398ef3 radix-tree: Add r... |
1332 1333 1334 1335 1336 1337 |
/** * 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 |
1338 |
* |
0ac398ef3 radix-tree: Add r... |
1339 |
* Remove @item at @index from the radix tree rooted at @root. |
1da177e4c Linux-2.6.12-rc2 |
1340 |
* |
0ac398ef3 radix-tree: Add r... |
1341 1342 |
* 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 |
1343 |
*/ |
53c59f262 lib: radix-tree: ... |
1344 1345 |
void *radix_tree_delete_item(struct radix_tree_root *root, unsigned long index, void *item) |
1da177e4c Linux-2.6.12-rc2 |
1346 |
{ |
0a835c4f0 Reimplement IDR a... |
1347 |
struct radix_tree_node *node = NULL; |
7a4deea1a idr: fix invalid ... |
1348 |
void __rcu **slot = NULL; |
139e56166 lib: radix_tree: ... |
1349 |
void *entry; |
1da177e4c Linux-2.6.12-rc2 |
1350 |
|
139e56166 lib: radix_tree: ... |
1351 |
entry = __radix_tree_lookup(root, index, &node, &slot); |
7a4deea1a idr: fix invalid ... |
1352 1353 |
if (!slot) return NULL; |
0a835c4f0 Reimplement IDR a... |
1354 1355 |
if (!entry && (!is_idr(root) || node_tag_get(root, node, IDR_FREE, get_slot_offset(node, slot)))) |
139e56166 lib: radix_tree: ... |
1356 |
return NULL; |
1da177e4c Linux-2.6.12-rc2 |
1357 |
|
139e56166 lib: radix_tree: ... |
1358 1359 |
if (item && entry != item) return NULL; |
0ac398ef3 radix-tree: Add r... |
1360 |
__radix_tree_delete(root, node, slot); |
612d6c19d [PATCH] radix-tre... |
1361 |
|
139e56166 lib: radix_tree: ... |
1362 |
return entry; |
1da177e4c Linux-2.6.12-rc2 |
1363 |
} |
53c59f262 lib: radix-tree: ... |
1364 1365 1366 |
EXPORT_SYMBOL(radix_tree_delete_item); /** |
0ac398ef3 radix-tree: Add r... |
1367 1368 1369 |
* radix_tree_delete - delete an entry from a radix tree * @root: radix tree root * @index: index key |
53c59f262 lib: radix-tree: ... |
1370 |
* |
0ac398ef3 radix-tree: Add r... |
1371 |
* Remove the entry at @index from the radix tree rooted at @root. |
53c59f262 lib: radix-tree: ... |
1372 |
* |
0ac398ef3 radix-tree: Add r... |
1373 |
* Return: The deleted entry, or %NULL if it was not present. |
53c59f262 lib: radix-tree: ... |
1374 1375 1376 1377 1378 |
*/ 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 |
1379 1380 1381 1382 1383 1384 1385 |
EXPORT_SYMBOL(radix_tree_delete); /** * radix_tree_tagged - test whether any items in the tree are tagged * @root: radix tree root * @tag: tag to test */ |
35534c869 radix tree: const... |
1386 |
int radix_tree_tagged(const struct radix_tree_root *root, unsigned int tag) |
1da177e4c Linux-2.6.12-rc2 |
1387 |
{ |
612d6c19d [PATCH] radix-tre... |
1388 |
return root_tag_get(root, tag); |
1da177e4c Linux-2.6.12-rc2 |
1389 1390 |
} EXPORT_SYMBOL(radix_tree_tagged); |
0a835c4f0 Reimplement IDR a... |
1391 1392 1393 1394 1395 1396 1397 1398 1399 |
/** * 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 ... |
1400 |
if (__radix_tree_preload(gfp_mask, IDR_PRELOAD_SIZE)) |
cfa6705d8 radix-tree: Use l... |
1401 |
local_lock(&radix_tree_preloads.lock); |
0a835c4f0 Reimplement IDR a... |
1402 1403 |
} EXPORT_SYMBOL(idr_preload); |
460488c58 idr: Remove idr_a... |
1404 |
void __rcu **idr_get_free(struct radix_tree_root *root, |
388f79fda idr: Add new APIs... |
1405 1406 |
struct radix_tree_iter *iter, gfp_t gfp, unsigned long max) |
0a835c4f0 Reimplement IDR a... |
1407 1408 |
{ struct radix_tree_node *node = NULL, *child; |
f8d5d0cc1 xarray: Add defin... |
1409 |
void __rcu **slot = (void __rcu **)&root->xa_head; |
0a835c4f0 Reimplement IDR a... |
1410 |
unsigned long maxindex, start = iter->next_index; |
0a835c4f0 Reimplement IDR a... |
1411 1412 1413 1414 1415 1416 1417 1418 1419 1420 1421 1422 1423 1424 |
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; |
f8d5d0cc1 xarray: Add defin... |
1425 |
child = rcu_dereference_raw(root->xa_head); |
0a835c4f0 Reimplement IDR a... |
1426 |
} |
66ee620f0 idr: Permit any v... |
1427 1428 |
if (start == 0 && shift == 0) shift = RADIX_TREE_MAP_SHIFT; |
0a835c4f0 Reimplement IDR a... |
1429 1430 1431 1432 1433 |
while (shift) { shift -= RADIX_TREE_MAP_SHIFT; if (child == NULL) { /* Have to add a child node. */ |
d58275bc9 radix-tree: Store... |
1434 1435 |
child = radix_tree_node_alloc(gfp, node, root, shift, offset, 0, 0); |
0a835c4f0 Reimplement IDR a... |
1436 1437 1438 1439 1440 1441 1442 1443 1444 1445 1446 1447 1448 1449 1450 |
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); |
b7e9728f3 idr: Fix idr_allo... |
1451 |
if (start > max || start == 0) |
0a835c4f0 Reimplement IDR a... |
1452 1453 1454 1455 1456 1457 1458 1459 1460 1461 1462 1463 1464 1465 1466 1467 1468 1469 1470 |
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; |
0a835c4f0 Reimplement IDR a... |
1471 1472 1473 1474 1475 1476 1477 1478 1479 1480 1481 1482 1483 1484 1485 1486 1487 1488 |
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) { |
f8d5d0cc1 xarray: Add defin... |
1489 |
struct radix_tree_node *node = rcu_dereference_raw(idr->idr_rt.xa_head); |
0a835c4f0 Reimplement IDR a... |
1490 1491 |
if (radix_tree_is_internal_node(node)) radix_tree_free_nodes(node); |
f8d5d0cc1 xarray: Add defin... |
1492 |
idr->idr_rt.xa_head = NULL; |
0a835c4f0 Reimplement IDR a... |
1493 1494 1495 |
root_tag_set(&idr->idr_rt, IDR_FREE); } EXPORT_SYMBOL(idr_destroy); |
1da177e4c Linux-2.6.12-rc2 |
1496 |
static void |
449dd6984 mm: keep page cac... |
1497 |
radix_tree_node_ctor(void *arg) |
1da177e4c Linux-2.6.12-rc2 |
1498 |
{ |
449dd6984 mm: keep page cac... |
1499 1500 1501 1502 |
struct radix_tree_node *node = arg; memset(node, 0, sizeof(*node)); INIT_LIST_HEAD(&node->private_list); |
1da177e4c Linux-2.6.12-rc2 |
1503 |
} |
d544abd5f lib/radix-tree: C... |
1504 |
static int radix_tree_cpu_dead(unsigned int cpu) |
1da177e4c Linux-2.6.12-rc2 |
1505 |
{ |
2fcd9005c radix-tree: misce... |
1506 1507 1508 1509 |
struct radix_tree_preload *rtp; struct radix_tree_node *node; /* Free per-cpu pool of preloaded nodes */ |
d544abd5f lib/radix-tree: C... |
1510 1511 1512 |
rtp = &per_cpu(radix_tree_preloads, cpu); while (rtp->nr) { node = rtp->nodes; |
1293d5c5f radix-tree: Chain... |
1513 |
rtp->nodes = node->parent; |
d544abd5f lib/radix-tree: C... |
1514 1515 |
kmem_cache_free(radix_tree_node_cachep, node); rtp->nr--; |
2fcd9005c radix-tree: misce... |
1516 |
} |
d544abd5f lib/radix-tree: C... |
1517 |
return 0; |
1da177e4c Linux-2.6.12-rc2 |
1518 |
} |
1da177e4c Linux-2.6.12-rc2 |
1519 1520 1521 |
void __init radix_tree_init(void) { |
d544abd5f lib/radix-tree: C... |
1522 |
int ret; |
7e7844226 lockdep: allow to... |
1523 1524 |
BUILD_BUG_ON(RADIX_TREE_MAX_TAGS + __GFP_BITS_SHIFT > 32); |
fa290cda1 radix tree: use G... |
1525 |
BUILD_BUG_ON(ROOT_IS_IDR & ~GFP_ZONEMASK); |
02c02bf12 xarray: Change de... |
1526 |
BUILD_BUG_ON(XA_CHUNK_SIZE > 255); |
1da177e4c Linux-2.6.12-rc2 |
1527 1528 |
radix_tree_node_cachep = kmem_cache_create("radix_tree_node", sizeof(struct radix_tree_node), 0, |
488514d17 Remove set_migrat... |
1529 1530 |
SLAB_PANIC | SLAB_RECLAIM_ACCOUNT, radix_tree_node_ctor); |
d544abd5f lib/radix-tree: C... |
1531 1532 1533 |
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 |
1534 |
} |