Blame view
include/linux/radix-tree.h
21.8 KB
1da177e4c Linux-2.6.12-rc2 |
1 2 3 |
/* * Copyright (C) 2001 Momchil Velikov * Portions Copyright (C) 2001 Christoph Hellwig |
7cf9c2c76 [PATCH] radix-tre... |
4 |
* Copyright (C) 2006 Nick Piggin |
78c1d7848 radix-tree: intro... |
5 |
* Copyright (C) 2012 Konstantin Khlebnikov |
1da177e4c Linux-2.6.12-rc2 |
6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
* * 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. */ #ifndef _LINUX_RADIX_TREE_H #define _LINUX_RADIX_TREE_H |
f67c07f07 radix-tree: add a... |
23 |
#include <linux/bitops.h> |
187f1882b BUG: headers with... |
24 |
#include <linux/bug.h> |
7cf9c2c76 [PATCH] radix-tre... |
25 |
#include <linux/kernel.h> |
15f2e88dd radix tree: Add s... |
26 27 |
#include <linux/list.h> #include <linux/preempt.h> |
7cf9c2c76 [PATCH] radix-tre... |
28 |
#include <linux/rcupdate.h> |
15f2e88dd radix tree: Add s... |
29 30 |
#include <linux/spinlock.h> #include <linux/types.h> |
7cf9c2c76 [PATCH] radix-tre... |
31 32 |
/* |
3bcadd6fa radix-tree: free ... |
33 34 |
* The bottom two bits of the slot determine how the remaining bits in the * slot are interpreted: |
7cf9c2c76 [PATCH] radix-tre... |
35 |
* |
3bcadd6fa radix-tree: free ... |
36 37 38 |
* 00 - data pointer * 01 - internal entry * 10 - exceptional entry |
a23216a2f radix-tree: fix c... |
39 |
* 11 - this bit combination is currently unused/reserved |
3bcadd6fa radix-tree: free ... |
40 41 42 43 44 45 46 |
* * The internal entry may be a pointer to the next level in the tree, a * sibling entry, or an indicator that the entry in this slot has been moved * to another location in the tree and the lookup should be restarted. While * NULL fits the 'data pointer' pattern, it means that there is no entry in * the tree for this index (no matter what level of the tree it is found at). * This means that you cannot store NULL in the tree as a value for the index. |
7cf9c2c76 [PATCH] radix-tre... |
47 |
*/ |
3bcadd6fa radix-tree: free ... |
48 49 |
#define RADIX_TREE_ENTRY_MASK 3UL #define RADIX_TREE_INTERNAL_NODE 1UL |
30ff46ccb radix-tree: renam... |
50 |
|
6328650bb radix_tree: excep... |
51 |
/* |
3bcadd6fa radix-tree: free ... |
52 53 54 |
* Most users of the radix tree store pointers but shmem/tmpfs stores swap * entries in the same tree. They are marked as exceptional entries to * distinguish them from pointers to struct page. |
6328650bb radix_tree: excep... |
55 56 57 58 |
* EXCEPTIONAL_ENTRY tests the bit, EXCEPTIONAL_SHIFT shifts content past it. */ #define RADIX_TREE_EXCEPTIONAL_ENTRY 2 #define RADIX_TREE_EXCEPTIONAL_SHIFT 2 |
7cf9c2c76 [PATCH] radix-tre... |
59 |
|
3bcadd6fa radix-tree: free ... |
60 |
static inline bool radix_tree_is_internal_node(void *ptr) |
7cf9c2c76 [PATCH] radix-tre... |
61 |
{ |
3bcadd6fa radix-tree: free ... |
62 63 |
return ((unsigned long)ptr & RADIX_TREE_ENTRY_MASK) == RADIX_TREE_INTERNAL_NODE; |
7cf9c2c76 [PATCH] radix-tre... |
64 65 66 |
} /*** radix-tree API starts here ***/ |
1da177e4c Linux-2.6.12-rc2 |
67 |
|
f446daaea mm: implement wri... |
68 |
#define RADIX_TREE_MAX_TAGS 3 |
612d6c19d [PATCH] radix-tre... |
69 |
|
97d778b2d radix tree test s... |
70 |
#ifndef RADIX_TREE_MAP_SHIFT |
139e56166 lib: radix_tree: ... |
71 |
#define RADIX_TREE_MAP_SHIFT (CONFIG_BASE_SMALL ? 4 : 6) |
139e56166 lib: radix_tree: ... |
72 73 74 75 76 77 78 |
#endif #define RADIX_TREE_MAP_SIZE (1UL << RADIX_TREE_MAP_SHIFT) #define RADIX_TREE_MAP_MASK (RADIX_TREE_MAP_SIZE-1) #define RADIX_TREE_TAG_LONGS \ ((RADIX_TREE_MAP_SIZE + BITS_PER_LONG - 1) / BITS_PER_LONG) |
449dd6984 mm: keep page cac... |
79 80 81 |
#define RADIX_TREE_INDEX_BITS (8 /* CHAR_BIT */ * sizeof(unsigned long)) #define RADIX_TREE_MAX_PATH (DIV_ROUND_UP(RADIX_TREE_INDEX_BITS, \ RADIX_TREE_MAP_SHIFT)) |
e157b5559 radix-tree: add r... |
82 83 84 85 86 87 88 89 |
/* * @count is the count of every non-NULL element in the ->slots array * whether that is an exceptional entry, a retry entry, a user pointer, * a sibling entry or a pointer to the next level of the tree. * @exceptional is the count of every element in ->slots which is * either radix_tree_exceptional_entry() or is a sibling entry for an * exceptional entry. */ |
139e56166 lib: radix_tree: ... |
90 |
struct radix_tree_node { |
f7942430e lib: radix-tree: ... |
91 92 |
unsigned char shift; /* Bits remaining in each slot */ unsigned char offset; /* Slot offset in parent */ |
14b468791 mm: workingset: m... |
93 |
unsigned char count; /* Total entry count */ |
f7942430e lib: radix-tree: ... |
94 |
unsigned char exceptional; /* Exceptional entry count */ |
91d9c05ac radix-tree: move ... |
95 |
struct radix_tree_node *parent; /* Used when ascending tree */ |
d58275bc9 radix-tree: Store... |
96 |
struct radix_tree_root *root; /* The tree we belong to */ |
139e56166 lib: radix_tree: ... |
97 |
union { |
91d9c05ac radix-tree: move ... |
98 99 |
struct list_head private_list; /* For tree user */ struct rcu_head rcu_head; /* Used when freeing node */ |
139e56166 lib: radix_tree: ... |
100 101 102 103 |
}; void __rcu *slots[RADIX_TREE_MAP_SIZE]; unsigned long tags[RADIX_TREE_MAX_TAGS][RADIX_TREE_TAG_LONGS]; }; |
0a835c4f0 Reimplement IDR a... |
104 105 106 |
/* The top bits of gfp_mask are used to store the root tags and the IDR flag */ #define ROOT_IS_IDR ((__force gfp_t)(1 << __GFP_BITS_SHIFT)) #define ROOT_TAG_SHIFT (__GFP_BITS_SHIFT + 1) |
1da177e4c Linux-2.6.12-rc2 |
107 |
struct radix_tree_root { |
fd4f2df24 [PATCH] gfp_t: lib/* |
108 |
gfp_t gfp_mask; |
a1115570b radix-tree: __rcu... |
109 |
struct radix_tree_node __rcu *rnode; |
1da177e4c Linux-2.6.12-rc2 |
110 111 112 |
}; #define RADIX_TREE_INIT(mask) { \ |
1da177e4c Linux-2.6.12-rc2 |
113 114 115 116 117 118 119 120 121 |
.gfp_mask = (mask), \ .rnode = NULL, \ } #define RADIX_TREE(name, mask) \ struct radix_tree_root name = RADIX_TREE_INIT(mask) #define INIT_RADIX_TREE(root, mask) \ do { \ |
1da177e4c Linux-2.6.12-rc2 |
122 123 124 |
(root)->gfp_mask = (mask); \ (root)->rnode = NULL; \ } while (0) |
35534c869 radix tree: const... |
125 |
static inline bool radix_tree_empty(const struct radix_tree_root *root) |
e9256efcc radix-tree: intro... |
126 127 128 |
{ return root->rnode == NULL; } |
7cf9c2c76 [PATCH] radix-tre... |
129 |
/** |
268f42de7 radix-tree: delet... |
130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 |
* struct radix_tree_iter - radix tree iterator state * * @index: index of current slot * @next_index: one beyond the last index for this chunk * @tags: bit-mask for tag-iterating * @node: node that contains current slot * @shift: shift for the node that holds our slots * * This radix tree iterator works in terms of "chunks" of slots. A chunk is a * subinterval of slots contained within one radix tree leaf node. It is * described by a pointer to its first slot and a struct radix_tree_iter * which holds the chunk's position in the tree and its size. For tagged * iteration radix_tree_iter also holds the slots' bit-mask for one chosen * radix tree tag. */ struct radix_tree_iter { unsigned long index; unsigned long next_index; unsigned long tags; struct radix_tree_node *node; #ifdef CONFIG_RADIX_TREE_MULTIORDER unsigned int shift; #endif }; static inline unsigned int iter_shift(const struct radix_tree_iter *iter) { #ifdef CONFIG_RADIX_TREE_MULTIORDER return iter->shift; #else return 0; #endif } /** |
7cf9c2c76 [PATCH] radix-tre... |
165 166 167 168 169 170 171 172 173 |
* Radix-tree synchronization * * The radix-tree API requires that users provide all synchronisation (with * specific exceptions, noted below). * * Synchronization of access to the data items being stored in the tree, and * management of their lifetimes must be completely managed by API users. * * For API usage, in general, |
59c51591a Fix occurrences o... |
174 |
* - any function _modifying_ the tree or tags (inserting or deleting |
eb8dc5e7b radix_tree.h triv... |
175 |
* items, setting or clearing tags) must exclude other modifications, and |
7cf9c2c76 [PATCH] radix-tre... |
176 |
* exclude any functions reading the tree. |
59c51591a Fix occurrences o... |
177 |
* - any function _reading_ the tree or tags (looking up items or tags, |
7cf9c2c76 [PATCH] radix-tre... |
178 179 180 181 |
* gang lookups) must exclude modifications to the tree, but may occur * concurrently with other readers. * * The notable exceptions to this rule are the following functions: |
139e56166 lib: radix_tree: ... |
182 |
* __radix_tree_lookup |
7cf9c2c76 [PATCH] radix-tre... |
183 |
* radix_tree_lookup |
47feff2c8 radix-tree: add g... |
184 |
* radix_tree_lookup_slot |
7cf9c2c76 [PATCH] radix-tre... |
185 186 |
* radix_tree_tag_get * radix_tree_gang_lookup |
47feff2c8 radix-tree: add g... |
187 |
* radix_tree_gang_lookup_slot |
7cf9c2c76 [PATCH] radix-tre... |
188 |
* radix_tree_gang_lookup_tag |
47feff2c8 radix-tree: add g... |
189 |
* radix_tree_gang_lookup_tag_slot |
7cf9c2c76 [PATCH] radix-tre... |
190 191 |
* radix_tree_tagged * |
243c2137c include/linux/rad... |
192 |
* The first 8 functions are able to be called locklessly, using RCU. The |
7cf9c2c76 [PATCH] radix-tre... |
193 194 195 196 197 198 199 200 201 202 203 204 205 |
* caller must ensure calls to these functions are made within rcu_read_lock() * regions. Other readers (lock-free or otherwise) and modifications may be * running concurrently. * * It is still required that the caller manage the synchronization and lifetimes * of the items. So if RCU lock-free lookups are used, typically this would mean * that the items have their own locks, or are amenable to lock-free access; and * that the items are freed by RCU (or only freed after having been deleted from * the radix tree *and* a synchronize_rcu() grace period). * * (Note, rcu_assign_pointer and rcu_dereference are not needed to control * access to data items when inserting into or looking up from the radix tree) * |
ce82653d6 radix_tree_tag_ge... |
206 207 208 209 210 211 212 |
* Note that the value returned by radix_tree_tag_get() may not be relied upon * if only the RCU read lock is held. Functions to set/clear tags and to * delete nodes running concurrently with it may affect its result such that * two consecutive reads in the same locked section may return different * values. If reliability is required, modification functions must also be * excluded from concurrency. * |
7cf9c2c76 [PATCH] radix-tre... |
213 214 215 216 |
* radix_tree_tagged is able to be called without locking or RCU. */ /** |
d7b627277 radix-tree: Fix _... |
217 218 |
* radix_tree_deref_slot - dereference a slot * @slot: slot pointer, returned by radix_tree_lookup_slot |
7cf9c2c76 [PATCH] radix-tre... |
219 220 |
* * For use with radix_tree_lookup_slot(). Caller must hold tree at least read |
27d20fddc radix-tree: fix R... |
221 222 223 224 225 |
* locked across slot lookup and dereference. Not required if write lock is * held (ie. items cannot be concurrently inserted). * * radix_tree_deref_retry must be used to confirm validity of the pointer if * only the read lock is held. |
d7b627277 radix-tree: Fix _... |
226 227 |
* * Return: entry stored in that slot. |
7cf9c2c76 [PATCH] radix-tre... |
228 |
*/ |
d7b627277 radix-tree: Fix _... |
229 |
static inline void *radix_tree_deref_slot(void __rcu **slot) |
7cf9c2c76 [PATCH] radix-tre... |
230 |
{ |
d7b627277 radix-tree: Fix _... |
231 |
return rcu_dereference(*slot); |
7cf9c2c76 [PATCH] radix-tre... |
232 |
} |
27d20fddc radix-tree: fix R... |
233 234 |
/** |
d7b627277 radix-tree: Fix _... |
235 236 237 238 239 |
* radix_tree_deref_slot_protected - dereference a slot with tree lock held * @slot: slot pointer, returned by radix_tree_lookup_slot * * Similar to radix_tree_deref_slot. The caller does not hold the RCU read * lock but it must hold the tree lock to prevent parallel updates. |
29c1f677d mm: migration: us... |
240 |
* |
d7b627277 radix-tree: Fix _... |
241 |
* Return: entry stored in that slot. |
29c1f677d mm: migration: us... |
242 |
*/ |
d7b627277 radix-tree: Fix _... |
243 |
static inline void *radix_tree_deref_slot_protected(void __rcu **slot, |
29c1f677d mm: migration: us... |
244 245 |
spinlock_t *treelock) { |
d7b627277 radix-tree: Fix _... |
246 |
return rcu_dereference_protected(*slot, lockdep_is_held(treelock)); |
29c1f677d mm: migration: us... |
247 248 249 |
} /** |
27d20fddc radix-tree: fix R... |
250 251 252 253 254 255 256 257 |
* radix_tree_deref_retry - check radix_tree_deref_slot * @arg: pointer returned by radix_tree_deref_slot * Returns: 0 if retry is not required, otherwise retry is required * * radix_tree_deref_retry must be used with radix_tree_deref_slot. */ static inline int radix_tree_deref_retry(void *arg) { |
b194d16c2 radix-tree: renam... |
258 |
return unlikely(radix_tree_is_internal_node(arg)); |
27d20fddc radix-tree: fix R... |
259 |
} |
7cf9c2c76 [PATCH] radix-tre... |
260 |
/** |
6328650bb radix_tree: excep... |
261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 |
* radix_tree_exceptional_entry - radix_tree_deref_slot gave exceptional entry? * @arg: value returned by radix_tree_deref_slot * Returns: 0 if well-aligned pointer, non-0 if exceptional entry. */ static inline int radix_tree_exceptional_entry(void *arg) { /* Not unlikely because radix_tree_exception often tested first */ return (unsigned long)arg & RADIX_TREE_EXCEPTIONAL_ENTRY; } /** * radix_tree_exception - radix_tree_deref_slot returned either exception? * @arg: value returned by radix_tree_deref_slot * Returns: 0 if well-aligned pointer, non-0 if either kind of exception. */ static inline int radix_tree_exception(void *arg) { |
3bcadd6fa radix-tree: free ... |
278 |
return unlikely((unsigned long)arg & RADIX_TREE_ENTRY_MASK); |
6328650bb radix_tree: excep... |
279 |
} |
d7b627277 radix-tree: Fix _... |
280 |
int __radix_tree_create(struct radix_tree_root *, unsigned long index, |
e61452365 radix_tree: add s... |
281 |
unsigned order, struct radix_tree_node **nodep, |
d7b627277 radix-tree: Fix _... |
282 |
void __rcu ***slotp); |
e61452365 radix_tree: add s... |
283 284 285 286 287 288 289 |
int __radix_tree_insert(struct radix_tree_root *, unsigned long index, unsigned order, void *); static inline int radix_tree_insert(struct radix_tree_root *root, unsigned long index, void *entry) { return __radix_tree_insert(root, index, 0, entry); } |
35534c869 radix tree: const... |
290 |
void *__radix_tree_lookup(const struct radix_tree_root *, unsigned long index, |
d7b627277 radix-tree: Fix _... |
291 |
struct radix_tree_node **nodep, void __rcu ***slotp); |
35534c869 radix tree: const... |
292 |
void *radix_tree_lookup(const struct radix_tree_root *, unsigned long); |
d7b627277 radix-tree: Fix _... |
293 294 |
void __rcu **radix_tree_lookup_slot(const struct radix_tree_root *, unsigned long index); |
4d693d086 lib: radix-tree: ... |
295 |
typedef void (*radix_tree_update_node_t)(struct radix_tree_node *, void *); |
d7b627277 radix-tree: Fix _... |
296 297 |
void __radix_tree_replace(struct radix_tree_root *, struct radix_tree_node *, void __rcu **slot, void *entry, |
4d693d086 lib: radix-tree: ... |
298 |
radix_tree_update_node_t update_node, void *private); |
e157b5559 radix-tree: add r... |
299 |
void radix_tree_iter_replace(struct radix_tree_root *, |
d7b627277 radix-tree: Fix _... |
300 301 302 303 304 |
const struct radix_tree_iter *, void __rcu **slot, void *entry); void radix_tree_replace_slot(struct radix_tree_root *, void __rcu **slot, void *entry); void __radix_tree_delete_node(struct radix_tree_root *, struct radix_tree_node *, |
ea07b862a mm: workingset: f... |
305 306 |
radix_tree_update_node_t update_node, void *private); |
0ac398ef3 radix-tree: Add r... |
307 |
void radix_tree_iter_delete(struct radix_tree_root *, |
d7b627277 radix-tree: Fix _... |
308 |
struct radix_tree_iter *iter, void __rcu **slot); |
53c59f262 lib: radix-tree: ... |
309 |
void *radix_tree_delete_item(struct radix_tree_root *, unsigned long, void *); |
1da177e4c Linux-2.6.12-rc2 |
310 |
void *radix_tree_delete(struct radix_tree_root *, unsigned long); |
d7b627277 radix-tree: Fix _... |
311 312 |
void radix_tree_clear_tags(struct radix_tree_root *, struct radix_tree_node *, void __rcu **slot); |
35534c869 radix tree: const... |
313 |
unsigned int radix_tree_gang_lookup(const struct radix_tree_root *, |
d604c3245 radix-tree: intro... |
314 315 |
void **results, unsigned long first_index, unsigned int max_items); |
35534c869 radix tree: const... |
316 |
unsigned int radix_tree_gang_lookup_slot(const struct radix_tree_root *, |
d7b627277 radix-tree: Fix _... |
317 |
void __rcu ***results, unsigned long *indices, |
47feff2c8 radix-tree: add g... |
318 |
unsigned long first_index, unsigned int max_items); |
dd0fc66fb [PATCH] gfp flags... |
319 |
int radix_tree_preload(gfp_t gfp_mask); |
5e4c0d974 lib/radix-tree.c:... |
320 |
int radix_tree_maybe_preload(gfp_t gfp_mask); |
c78c66d1d radix-tree: imple... |
321 |
int radix_tree_maybe_preload_order(gfp_t gfp_mask, int order); |
1da177e4c Linux-2.6.12-rc2 |
322 |
void radix_tree_init(void); |
d7b627277 radix-tree: Fix _... |
323 |
void *radix_tree_tag_set(struct radix_tree_root *, |
daff89f32 [PATCH] radix-tre... |
324 |
unsigned long index, unsigned int tag); |
d7b627277 radix-tree: Fix _... |
325 |
void *radix_tree_tag_clear(struct radix_tree_root *, |
daff89f32 [PATCH] radix-tre... |
326 |
unsigned long index, unsigned int tag); |
35534c869 radix tree: const... |
327 |
int radix_tree_tag_get(const struct radix_tree_root *, |
daff89f32 [PATCH] radix-tre... |
328 |
unsigned long index, unsigned int tag); |
30b888ba9 radix-tree: Add r... |
329 330 331 |
void radix_tree_iter_tag_set(struct radix_tree_root *, const struct radix_tree_iter *iter, unsigned int tag); void radix_tree_iter_tag_clear(struct radix_tree_root *, |
268f42de7 radix-tree: delet... |
332 |
const struct radix_tree_iter *iter, unsigned int tag); |
d7b627277 radix-tree: Fix _... |
333 334 335 336 337 338 339 |
unsigned int radix_tree_gang_lookup_tag(const struct radix_tree_root *, void **results, unsigned long first_index, unsigned int max_items, unsigned int tag); unsigned int radix_tree_gang_lookup_tag_slot(const struct radix_tree_root *, void __rcu ***results, unsigned long first_index, unsigned int max_items, unsigned int tag); int radix_tree_tagged(const struct radix_tree_root *, unsigned int tag); |
1da177e4c Linux-2.6.12-rc2 |
340 341 342 343 344 |
static inline void radix_tree_preload_end(void) { preempt_enable(); } |
2791653a6 radix-tree: add r... |
345 |
int radix_tree_split_preload(unsigned old_order, unsigned new_order, gfp_t); |
e157b5559 radix-tree: add r... |
346 347 |
int radix_tree_split(struct radix_tree_root *, unsigned long index, unsigned new_order); |
175542f57 radix-tree: add r... |
348 349 |
int radix_tree_join(struct radix_tree_root *, unsigned long index, unsigned new_order, void *); |
388f79fda idr: Add new APIs... |
350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 |
void __rcu **idr_get_free_cmn(struct radix_tree_root *root, struct radix_tree_iter *iter, gfp_t gfp, unsigned long max); static inline void __rcu **idr_get_free(struct radix_tree_root *root, struct radix_tree_iter *iter, gfp_t gfp, int end) { return idr_get_free_cmn(root, iter, gfp, end > 0 ? end - 1 : INT_MAX); } static inline void __rcu **idr_get_free_ext(struct radix_tree_root *root, struct radix_tree_iter *iter, gfp_t gfp, unsigned long end) { return idr_get_free_cmn(root, iter, gfp, end - 1); } |
175542f57 radix-tree: add r... |
369 |
|
0a835c4f0 Reimplement IDR a... |
370 371 372 373 374 |
enum { RADIX_TREE_ITER_TAG_MASK = 0x0f, /* tag index in lower nybble */ RADIX_TREE_ITER_TAGGED = 0x10, /* lookup tagged slots */ RADIX_TREE_ITER_CONTIG = 0x20, /* stop at first hole */ }; |
78c1d7848 radix-tree: intro... |
375 376 377 378 379 380 381 382 |
/** * radix_tree_iter_init - initialize radix tree iterator * * @iter: pointer to iterator state * @start: iteration starting index * Returns: NULL */ |
d7b627277 radix-tree: Fix _... |
383 |
static __always_inline void __rcu ** |
78c1d7848 radix-tree: intro... |
384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 |
radix_tree_iter_init(struct radix_tree_iter *iter, unsigned long start) { /* * Leave iter->tags uninitialized. radix_tree_next_chunk() will fill it * in the case of a successful tagged chunk lookup. If the lookup was * unsuccessful or non-tagged then nobody cares about ->tags. * * Set index to zero to bypass next_index overflow protection. * See the comment in radix_tree_next_chunk() for details. */ iter->index = 0; iter->next_index = start; return NULL; } /** * 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 there no more left * * This function looks up the next chunk in the radix tree starting from * @iter->next_index. It returns a pointer to the chunk's first slot. * Also it fills @iter with data about chunk: position in the tree (index), * its end (next_index), and constructs a bit mask for tagged iterating (tags). */ |
d7b627277 radix-tree: Fix _... |
412 |
void __rcu **radix_tree_next_chunk(const struct radix_tree_root *, |
78c1d7848 radix-tree: intro... |
413 414 415 |
struct radix_tree_iter *iter, unsigned flags); /** |
0a835c4f0 Reimplement IDR a... |
416 417 418 419 420 421 422 423 424 |
* radix_tree_iter_lookup - look up an index in the radix tree * @root: radix tree root * @iter: iterator state * @index: key to look up * * If @index is present in the radix tree, this function returns the slot * containing it and updates @iter to describe the entry. If @index is not * present, it returns NULL. */ |
d7b627277 radix-tree: Fix _... |
425 426 |
static inline void __rcu ** radix_tree_iter_lookup(const struct radix_tree_root *root, |
0a835c4f0 Reimplement IDR a... |
427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 |
struct radix_tree_iter *iter, unsigned long index) { radix_tree_iter_init(iter, index); return radix_tree_next_chunk(root, iter, RADIX_TREE_ITER_CONTIG); } /** * radix_tree_iter_find - find a present entry * @root: radix tree root * @iter: iterator state * @index: start location * * This function returns the slot containing the entry with the lowest index * which is at least @index. If @index is larger than any present entry, this * function returns NULL. The @iter is updated to describe the entry found. */ |
d7b627277 radix-tree: Fix _... |
443 444 |
static inline void __rcu ** radix_tree_iter_find(const struct radix_tree_root *root, |
0a835c4f0 Reimplement IDR a... |
445 446 447 448 449 450 451 |
struct radix_tree_iter *iter, unsigned long index) { radix_tree_iter_init(iter, index); return radix_tree_next_chunk(root, iter, 0); } /** |
46437f9a5 radix-tree: fix r... |
452 453 454 455 456 457 458 459 460 |
* radix_tree_iter_retry - retry this chunk of the iteration * @iter: iterator state * * If we iterate over a tree protected only by the RCU lock, a race * against deletion or creation may result in seeing a slot for which * radix_tree_deref_retry() returns true. If so, call this function * and continue the iteration. */ static inline __must_check |
d7b627277 radix-tree: Fix _... |
461 |
void __rcu **radix_tree_iter_retry(struct radix_tree_iter *iter) |
46437f9a5 radix-tree: fix r... |
462 463 |
{ iter->next_index = iter->index; |
3cb9185c6 radix-tree: fix r... |
464 |
iter->tags = 0; |
46437f9a5 radix-tree: fix r... |
465 466 |
return NULL; } |
21ef53393 radix-tree: add s... |
467 468 469 470 471 |
static inline unsigned long __radix_tree_iter_add(struct radix_tree_iter *iter, unsigned long slots) { return iter->index + (slots << iter_shift(iter)); } |
46437f9a5 radix-tree: fix r... |
472 |
/** |
148deab22 radix-tree: impro... |
473 474 475 476 |
* radix_tree_iter_resume - resume iterating when the chunk may be invalid * @slot: pointer to current slot * @iter: iterator state * Returns: New slot pointer |
7165092fe radix-tree,shmem:... |
477 478 479 |
* * If the iterator needs to release then reacquire a lock, the chunk may * have been invalidated by an insertion or deletion. Call this function |
148deab22 radix-tree: impro... |
480 |
* before releasing the lock to continue the iteration from the next index. |
7165092fe radix-tree,shmem:... |
481 |
*/ |
d7b627277 radix-tree: Fix _... |
482 |
void __rcu **__must_check radix_tree_iter_resume(void __rcu **slot, |
148deab22 radix-tree: impro... |
483 |
struct radix_tree_iter *iter); |
7165092fe radix-tree,shmem:... |
484 485 |
/** |
78c1d7848 radix-tree: intro... |
486 487 488 489 490 |
* radix_tree_chunk_size - get current chunk size * * @iter: pointer to radix tree iterator * Returns: current chunk size */ |
732042821 radix-tree: fix o... |
491 |
static __always_inline long |
78c1d7848 radix-tree: intro... |
492 493 |
radix_tree_chunk_size(struct radix_tree_iter *iter) { |
21ef53393 radix-tree: add s... |
494 495 |
return (iter->next_index - iter->index) >> iter_shift(iter); } |
148deab22 radix-tree: impro... |
496 |
#ifdef CONFIG_RADIX_TREE_MULTIORDER |
d7b627277 radix-tree: Fix _... |
497 498 |
void __rcu **__radix_tree_next_slot(void __rcu **slot, struct radix_tree_iter *iter, unsigned flags); |
148deab22 radix-tree: impro... |
499 500 |
#else /* Can't happen without sibling entries, but the compiler can't tell that */ |
d7b627277 radix-tree: Fix _... |
501 |
static inline void __rcu **__radix_tree_next_slot(void __rcu **slot, |
148deab22 radix-tree: impro... |
502 |
struct radix_tree_iter *iter, unsigned flags) |
21ef53393 radix-tree: add s... |
503 |
{ |
148deab22 radix-tree: impro... |
504 |
return slot; |
78c1d7848 radix-tree: intro... |
505 |
} |
148deab22 radix-tree: impro... |
506 |
#endif |
78c1d7848 radix-tree: intro... |
507 508 509 510 511 512 513 514 515 516 517 |
/** * radix_tree_next_slot - find next slot in chunk * * @slot: pointer to current slot * @iter: pointer to interator state * @flags: RADIX_TREE_ITER_*, should be constant * Returns: pointer to next slot, or NULL if there no more left * * This function updates @iter->index in the case of a successful lookup. * For tagged lookup it also eats @iter->tags. |
915045fe1 radix-tree: 'slot... |
518 519 |
* * There are several cases where 'slot' can be passed in as NULL to this |
148deab22 radix-tree: impro... |
520 |
* function. These cases result from the use of radix_tree_iter_resume() or |
915045fe1 radix-tree: 'slot... |
521 522 523 524 525 |
* radix_tree_iter_retry(). In these cases we don't end up dereferencing * 'slot' because either: * a) we are doing tagged iteration and iter->tags has been set to 0, or * b) we are doing non-tagged iteration, and iter->index and iter->next_index * have been set up so that radix_tree_chunk_size() returns 1 or 0. |
78c1d7848 radix-tree: intro... |
526 |
*/ |
d7b627277 radix-tree: Fix _... |
527 528 |
static __always_inline void __rcu **radix_tree_next_slot(void __rcu **slot, struct radix_tree_iter *iter, unsigned flags) |
78c1d7848 radix-tree: intro... |
529 530 531 |
{ if (flags & RADIX_TREE_ITER_TAGGED) { iter->tags >>= 1; |
21ef53393 radix-tree: add s... |
532 533 |
if (unlikely(!iter->tags)) return NULL; |
78c1d7848 radix-tree: intro... |
534 |
if (likely(iter->tags & 1ul)) { |
21ef53393 radix-tree: add s... |
535 |
iter->index = __radix_tree_iter_add(iter, 1); |
148deab22 radix-tree: impro... |
536 537 |
slot++; goto found; |
78c1d7848 radix-tree: intro... |
538 |
} |
21ef53393 radix-tree: add s... |
539 |
if (!(flags & RADIX_TREE_ITER_CONTIG)) { |
78c1d7848 radix-tree: intro... |
540 |
unsigned offset = __ffs(iter->tags); |
148deab22 radix-tree: impro... |
541 542 543 544 |
iter->tags >>= offset++; iter->index = __radix_tree_iter_add(iter, offset); slot += offset; goto found; |
78c1d7848 radix-tree: intro... |
545 546 |
} } else { |
21ef53393 radix-tree: add s... |
547 |
long count = radix_tree_chunk_size(iter); |
78c1d7848 radix-tree: intro... |
548 |
|
21ef53393 radix-tree: add s... |
549 |
while (--count > 0) { |
78c1d7848 radix-tree: intro... |
550 |
slot++; |
21ef53393 radix-tree: add s... |
551 |
iter->index = __radix_tree_iter_add(iter, 1); |
78c1d7848 radix-tree: intro... |
552 |
if (likely(*slot)) |
148deab22 radix-tree: impro... |
553 |
goto found; |
fffaee365 radix-tree: fix c... |
554 555 556 |
if (flags & RADIX_TREE_ITER_CONTIG) { /* forbid switching to the next chunk */ iter->next_index = 0; |
78c1d7848 radix-tree: intro... |
557 |
break; |
fffaee365 radix-tree: fix c... |
558 |
} |
78c1d7848 radix-tree: intro... |
559 560 561 |
} } return NULL; |
148deab22 radix-tree: impro... |
562 563 |
found: |
12320d0ff radix-tree: Add r... |
564 |
if (unlikely(radix_tree_is_internal_node(rcu_dereference_raw(*slot)))) |
148deab22 radix-tree: impro... |
565 566 |
return __radix_tree_next_slot(slot, iter, flags); return slot; |
78c1d7848 radix-tree: intro... |
567 568 569 |
} /** |
78c1d7848 radix-tree: intro... |
570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 |
* radix_tree_for_each_slot - iterate over non-empty slots * * @slot: the void** variable for pointer to slot * @root: the struct radix_tree_root pointer * @iter: the struct radix_tree_iter pointer * @start: iteration starting index * * @slot points to radix tree slot, @iter->index contains its index. */ #define radix_tree_for_each_slot(slot, root, iter, start) \ for (slot = radix_tree_iter_init(iter, start) ; \ slot || (slot = radix_tree_next_chunk(root, iter, 0)) ; \ slot = radix_tree_next_slot(slot, iter, 0)) /** * radix_tree_for_each_contig - iterate over contiguous slots * * @slot: the void** variable for pointer to slot * @root: the struct radix_tree_root pointer * @iter: the struct radix_tree_iter pointer * @start: iteration starting index * * @slot points to radix tree slot, @iter->index contains its index. */ #define radix_tree_for_each_contig(slot, root, iter, start) \ for (slot = radix_tree_iter_init(iter, start) ; \ slot || (slot = radix_tree_next_chunk(root, iter, \ RADIX_TREE_ITER_CONTIG)) ; \ slot = radix_tree_next_slot(slot, iter, \ RADIX_TREE_ITER_CONTIG)) /** * radix_tree_for_each_tagged - iterate over tagged slots * * @slot: the void** variable for pointer to slot * @root: the struct radix_tree_root pointer * @iter: the struct radix_tree_iter pointer * @start: iteration starting index * @tag: tag index * * @slot points to radix tree slot, @iter->index contains its index. */ #define radix_tree_for_each_tagged(slot, root, iter, start, tag) \ for (slot = radix_tree_iter_init(iter, start) ; \ slot || (slot = radix_tree_next_chunk(root, iter, \ RADIX_TREE_ITER_TAGGED | tag)) ; \ slot = radix_tree_next_slot(slot, iter, \ |
148deab22 radix-tree: impro... |
617 |
RADIX_TREE_ITER_TAGGED | tag)) |
78c1d7848 radix-tree: intro... |
618 |
|
1da177e4c Linux-2.6.12-rc2 |
619 |
#endif /* _LINUX_RADIX_TREE_H */ |