Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 1 | /* |
| 2 | * Copyright (C) 2001 Momchil Velikov |
| 3 | * Portions Copyright (C) 2001 Christoph Hellwig |
Christoph Lameter | 201b626 | 2005-09-06 15:16:46 -0700 | [diff] [blame] | 4 | * Copyright (C) 2005 SGI, Christoph Lameter <clameter@sgi.com> |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 5 | * |
| 6 | * This program is free software; you can redistribute it and/or |
| 7 | * modify it under the terms of the GNU General Public License as |
| 8 | * published by the Free Software Foundation; either version 2, or (at |
| 9 | * your option) any later version. |
| 10 | * |
| 11 | * This program is distributed in the hope that it will be useful, but |
| 12 | * WITHOUT ANY WARRANTY; without even the implied warranty of |
| 13 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
| 14 | * General Public License for more details. |
| 15 | * |
| 16 | * You should have received a copy of the GNU General Public License |
| 17 | * along with this program; if not, write to the Free Software |
| 18 | * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. |
| 19 | */ |
| 20 | |
| 21 | #include <linux/errno.h> |
| 22 | #include <linux/init.h> |
| 23 | #include <linux/kernel.h> |
| 24 | #include <linux/module.h> |
| 25 | #include <linux/radix-tree.h> |
| 26 | #include <linux/percpu.h> |
| 27 | #include <linux/slab.h> |
| 28 | #include <linux/notifier.h> |
| 29 | #include <linux/cpu.h> |
| 30 | #include <linux/gfp.h> |
| 31 | #include <linux/string.h> |
| 32 | #include <linux/bitops.h> |
| 33 | |
| 34 | |
| 35 | #ifdef __KERNEL__ |
| 36 | #define RADIX_TREE_MAP_SHIFT 6 |
| 37 | #else |
| 38 | #define RADIX_TREE_MAP_SHIFT 3 /* For more stressful testing */ |
| 39 | #endif |
| 40 | #define RADIX_TREE_TAGS 2 |
| 41 | |
| 42 | #define RADIX_TREE_MAP_SIZE (1UL << RADIX_TREE_MAP_SHIFT) |
| 43 | #define RADIX_TREE_MAP_MASK (RADIX_TREE_MAP_SIZE-1) |
| 44 | |
| 45 | #define RADIX_TREE_TAG_LONGS \ |
| 46 | ((RADIX_TREE_MAP_SIZE + BITS_PER_LONG - 1) / BITS_PER_LONG) |
| 47 | |
| 48 | struct radix_tree_node { |
| 49 | unsigned int count; |
| 50 | void *slots[RADIX_TREE_MAP_SIZE]; |
| 51 | unsigned long tags[RADIX_TREE_TAGS][RADIX_TREE_TAG_LONGS]; |
| 52 | }; |
| 53 | |
| 54 | struct radix_tree_path { |
Christoph Lameter | 201b626 | 2005-09-06 15:16:46 -0700 | [diff] [blame] | 55 | struct radix_tree_node *node; |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 56 | int offset; |
| 57 | }; |
| 58 | |
| 59 | #define RADIX_TREE_INDEX_BITS (8 /* CHAR_BIT */ * sizeof(unsigned long)) |
| 60 | #define RADIX_TREE_MAX_PATH (RADIX_TREE_INDEX_BITS/RADIX_TREE_MAP_SHIFT + 2) |
| 61 | |
Christoph Lameter | 6c03652 | 2005-07-07 17:56:59 -0700 | [diff] [blame] | 62 | static unsigned long height_to_maxindex[RADIX_TREE_MAX_PATH] __read_mostly; |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 63 | |
| 64 | /* |
| 65 | * Radix tree node cache. |
| 66 | */ |
| 67 | static kmem_cache_t *radix_tree_node_cachep; |
| 68 | |
| 69 | /* |
| 70 | * Per-cpu pool of preloaded nodes |
| 71 | */ |
| 72 | struct radix_tree_preload { |
| 73 | int nr; |
| 74 | struct radix_tree_node *nodes[RADIX_TREE_MAX_PATH]; |
| 75 | }; |
| 76 | DEFINE_PER_CPU(struct radix_tree_preload, radix_tree_preloads) = { 0, }; |
| 77 | |
| 78 | /* |
| 79 | * This assumes that the caller has performed appropriate preallocation, and |
| 80 | * that the caller has pinned this thread of control to the current CPU. |
| 81 | */ |
| 82 | static struct radix_tree_node * |
| 83 | radix_tree_node_alloc(struct radix_tree_root *root) |
| 84 | { |
| 85 | struct radix_tree_node *ret; |
| 86 | |
| 87 | ret = kmem_cache_alloc(radix_tree_node_cachep, root->gfp_mask); |
| 88 | if (ret == NULL && !(root->gfp_mask & __GFP_WAIT)) { |
| 89 | struct radix_tree_preload *rtp; |
| 90 | |
| 91 | rtp = &__get_cpu_var(radix_tree_preloads); |
| 92 | if (rtp->nr) { |
| 93 | ret = rtp->nodes[rtp->nr - 1]; |
| 94 | rtp->nodes[rtp->nr - 1] = NULL; |
| 95 | rtp->nr--; |
| 96 | } |
| 97 | } |
| 98 | return ret; |
| 99 | } |
| 100 | |
| 101 | static inline void |
| 102 | radix_tree_node_free(struct radix_tree_node *node) |
| 103 | { |
| 104 | kmem_cache_free(radix_tree_node_cachep, node); |
| 105 | } |
| 106 | |
| 107 | /* |
| 108 | * Load up this CPU's radix_tree_node buffer with sufficient objects to |
| 109 | * ensure that the addition of a single element in the tree cannot fail. On |
| 110 | * success, return zero, with preemption disabled. On error, return -ENOMEM |
| 111 | * with preemption not disabled. |
| 112 | */ |
Al Viro | dd0fc66 | 2005-10-07 07:46:04 +0100 | [diff] [blame] | 113 | int radix_tree_preload(gfp_t gfp_mask) |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 114 | { |
| 115 | struct radix_tree_preload *rtp; |
| 116 | struct radix_tree_node *node; |
| 117 | int ret = -ENOMEM; |
| 118 | |
| 119 | preempt_disable(); |
| 120 | rtp = &__get_cpu_var(radix_tree_preloads); |
| 121 | while (rtp->nr < ARRAY_SIZE(rtp->nodes)) { |
| 122 | preempt_enable(); |
| 123 | node = kmem_cache_alloc(radix_tree_node_cachep, gfp_mask); |
| 124 | if (node == NULL) |
| 125 | goto out; |
| 126 | preempt_disable(); |
| 127 | rtp = &__get_cpu_var(radix_tree_preloads); |
| 128 | if (rtp->nr < ARRAY_SIZE(rtp->nodes)) |
| 129 | rtp->nodes[rtp->nr++] = node; |
| 130 | else |
| 131 | kmem_cache_free(radix_tree_node_cachep, node); |
| 132 | } |
| 133 | ret = 0; |
| 134 | out: |
| 135 | return ret; |
| 136 | } |
| 137 | |
| 138 | static inline void tag_set(struct radix_tree_node *node, int tag, int offset) |
| 139 | { |
| 140 | if (!test_bit(offset, &node->tags[tag][0])) |
| 141 | __set_bit(offset, &node->tags[tag][0]); |
| 142 | } |
| 143 | |
| 144 | static inline void tag_clear(struct radix_tree_node *node, int tag, int offset) |
| 145 | { |
| 146 | __clear_bit(offset, &node->tags[tag][0]); |
| 147 | } |
| 148 | |
| 149 | static inline int tag_get(struct radix_tree_node *node, int tag, int offset) |
| 150 | { |
| 151 | return test_bit(offset, &node->tags[tag][0]); |
| 152 | } |
| 153 | |
| 154 | /* |
Nick Piggin | 6e954b9 | 2006-01-08 01:01:40 -0800 | [diff] [blame^] | 155 | * Returns 1 if any slot in the node has this tag set. |
| 156 | * Otherwise returns 0. |
| 157 | */ |
| 158 | static inline int any_tag_set(struct radix_tree_node *node, int tag) |
| 159 | { |
| 160 | int idx; |
| 161 | for (idx = 0; idx < RADIX_TREE_TAG_LONGS; idx++) { |
| 162 | if (node->tags[tag][idx]) |
| 163 | return 1; |
| 164 | } |
| 165 | return 0; |
| 166 | } |
| 167 | |
| 168 | /* |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 169 | * Return the maximum key which can be store into a |
| 170 | * radix tree with height HEIGHT. |
| 171 | */ |
| 172 | static inline unsigned long radix_tree_maxindex(unsigned int height) |
| 173 | { |
| 174 | return height_to_maxindex[height]; |
| 175 | } |
| 176 | |
| 177 | /* |
| 178 | * Extend a radix tree so it can store key @index. |
| 179 | */ |
| 180 | static int radix_tree_extend(struct radix_tree_root *root, unsigned long index) |
| 181 | { |
| 182 | struct radix_tree_node *node; |
| 183 | unsigned int height; |
| 184 | char tags[RADIX_TREE_TAGS]; |
| 185 | int tag; |
| 186 | |
| 187 | /* Figure out what the height should be. */ |
| 188 | height = root->height + 1; |
| 189 | while (index > radix_tree_maxindex(height)) |
| 190 | height++; |
| 191 | |
| 192 | if (root->rnode == NULL) { |
| 193 | root->height = height; |
| 194 | goto out; |
| 195 | } |
| 196 | |
| 197 | /* |
| 198 | * Prepare the tag status of the top-level node for propagation |
| 199 | * into the newly-pushed top-level node(s) |
| 200 | */ |
| 201 | for (tag = 0; tag < RADIX_TREE_TAGS; tag++) { |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 202 | tags[tag] = 0; |
Nick Piggin | 6e954b9 | 2006-01-08 01:01:40 -0800 | [diff] [blame^] | 203 | if (any_tag_set(root->rnode, tag)) |
| 204 | tags[tag] = 1; |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 205 | } |
| 206 | |
| 207 | do { |
| 208 | if (!(node = radix_tree_node_alloc(root))) |
| 209 | return -ENOMEM; |
| 210 | |
| 211 | /* Increase the height. */ |
| 212 | node->slots[0] = root->rnode; |
| 213 | |
| 214 | /* Propagate the aggregated tag info into the new root */ |
| 215 | for (tag = 0; tag < RADIX_TREE_TAGS; tag++) { |
| 216 | if (tags[tag]) |
| 217 | tag_set(node, tag, 0); |
| 218 | } |
| 219 | |
| 220 | node->count = 1; |
| 221 | root->rnode = node; |
| 222 | root->height++; |
| 223 | } while (height > root->height); |
| 224 | out: |
| 225 | return 0; |
| 226 | } |
| 227 | |
| 228 | /** |
| 229 | * radix_tree_insert - insert into a radix tree |
| 230 | * @root: radix tree root |
| 231 | * @index: index key |
| 232 | * @item: item to insert |
| 233 | * |
| 234 | * Insert an item into the radix tree at position @index. |
| 235 | */ |
| 236 | int radix_tree_insert(struct radix_tree_root *root, |
| 237 | unsigned long index, void *item) |
| 238 | { |
Christoph Lameter | 201b626 | 2005-09-06 15:16:46 -0700 | [diff] [blame] | 239 | struct radix_tree_node *node = NULL, *slot; |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 240 | unsigned int height, shift; |
| 241 | int offset; |
| 242 | int error; |
| 243 | |
| 244 | /* Make sure the tree is high enough. */ |
| 245 | if ((!index && !root->rnode) || |
| 246 | index > radix_tree_maxindex(root->height)) { |
| 247 | error = radix_tree_extend(root, index); |
| 248 | if (error) |
| 249 | return error; |
| 250 | } |
| 251 | |
Christoph Lameter | 201b626 | 2005-09-06 15:16:46 -0700 | [diff] [blame] | 252 | slot = root->rnode; |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 253 | height = root->height; |
| 254 | shift = (height-1) * RADIX_TREE_MAP_SHIFT; |
| 255 | |
| 256 | offset = 0; /* uninitialised var warning */ |
| 257 | while (height > 0) { |
Christoph Lameter | 201b626 | 2005-09-06 15:16:46 -0700 | [diff] [blame] | 258 | if (slot == NULL) { |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 259 | /* Have to add a child node. */ |
Christoph Lameter | 201b626 | 2005-09-06 15:16:46 -0700 | [diff] [blame] | 260 | if (!(slot = radix_tree_node_alloc(root))) |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 261 | return -ENOMEM; |
Christoph Lameter | 201b626 | 2005-09-06 15:16:46 -0700 | [diff] [blame] | 262 | if (node) { |
| 263 | node->slots[offset] = slot; |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 264 | node->count++; |
Christoph Lameter | 201b626 | 2005-09-06 15:16:46 -0700 | [diff] [blame] | 265 | } else |
| 266 | root->rnode = slot; |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 267 | } |
| 268 | |
| 269 | /* Go a level down */ |
| 270 | offset = (index >> shift) & RADIX_TREE_MAP_MASK; |
Christoph Lameter | 201b626 | 2005-09-06 15:16:46 -0700 | [diff] [blame] | 271 | node = slot; |
| 272 | slot = node->slots[offset]; |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 273 | shift -= RADIX_TREE_MAP_SHIFT; |
| 274 | height--; |
| 275 | } |
| 276 | |
Christoph Lameter | 201b626 | 2005-09-06 15:16:46 -0700 | [diff] [blame] | 277 | if (slot != NULL) |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 278 | return -EEXIST; |
Christoph Lameter | 201b626 | 2005-09-06 15:16:46 -0700 | [diff] [blame] | 279 | |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 280 | if (node) { |
| 281 | node->count++; |
Christoph Lameter | 201b626 | 2005-09-06 15:16:46 -0700 | [diff] [blame] | 282 | node->slots[offset] = item; |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 283 | BUG_ON(tag_get(node, 0, offset)); |
| 284 | BUG_ON(tag_get(node, 1, offset)); |
Christoph Lameter | 201b626 | 2005-09-06 15:16:46 -0700 | [diff] [blame] | 285 | } else |
| 286 | root->rnode = item; |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 287 | |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 288 | return 0; |
| 289 | } |
| 290 | EXPORT_SYMBOL(radix_tree_insert); |
| 291 | |
Hans Reiser | a433136 | 2005-11-07 00:59:29 -0800 | [diff] [blame] | 292 | static inline void **__lookup_slot(struct radix_tree_root *root, |
| 293 | unsigned long index) |
| 294 | { |
| 295 | unsigned int height, shift; |
| 296 | struct radix_tree_node **slot; |
| 297 | |
| 298 | height = root->height; |
| 299 | if (index > radix_tree_maxindex(height)) |
| 300 | return NULL; |
| 301 | |
| 302 | shift = (height-1) * RADIX_TREE_MAP_SHIFT; |
| 303 | slot = &root->rnode; |
| 304 | |
| 305 | while (height > 0) { |
| 306 | if (*slot == NULL) |
| 307 | return NULL; |
| 308 | |
| 309 | slot = (struct radix_tree_node **) |
| 310 | ((*slot)->slots + |
| 311 | ((index >> shift) & RADIX_TREE_MAP_MASK)); |
| 312 | shift -= RADIX_TREE_MAP_SHIFT; |
| 313 | height--; |
| 314 | } |
| 315 | |
| 316 | return (void **)slot; |
| 317 | } |
| 318 | |
| 319 | /** |
| 320 | * radix_tree_lookup_slot - lookup a slot in a radix tree |
| 321 | * @root: radix tree root |
| 322 | * @index: index key |
| 323 | * |
| 324 | * Lookup the slot corresponding to the position @index in the radix tree |
| 325 | * @root. This is useful for update-if-exists operations. |
| 326 | */ |
| 327 | void **radix_tree_lookup_slot(struct radix_tree_root *root, unsigned long index) |
| 328 | { |
| 329 | return __lookup_slot(root, index); |
| 330 | } |
| 331 | EXPORT_SYMBOL(radix_tree_lookup_slot); |
| 332 | |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 333 | /** |
| 334 | * radix_tree_lookup - perform lookup operation on a radix tree |
| 335 | * @root: radix tree root |
| 336 | * @index: index key |
| 337 | * |
| 338 | * Lookup the item at the position @index in the radix tree @root. |
| 339 | */ |
| 340 | void *radix_tree_lookup(struct radix_tree_root *root, unsigned long index) |
| 341 | { |
Hans Reiser | a433136 | 2005-11-07 00:59:29 -0800 | [diff] [blame] | 342 | void **slot; |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 343 | |
Hans Reiser | a433136 | 2005-11-07 00:59:29 -0800 | [diff] [blame] | 344 | slot = __lookup_slot(root, index); |
| 345 | return slot != NULL ? *slot : NULL; |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 346 | } |
| 347 | EXPORT_SYMBOL(radix_tree_lookup); |
| 348 | |
| 349 | /** |
| 350 | * radix_tree_tag_set - set a tag on a radix tree node |
| 351 | * @root: radix tree root |
| 352 | * @index: index key |
| 353 | * @tag: tag index |
| 354 | * |
| 355 | * Set the search tag corresponging to @index in the radix tree. From |
| 356 | * the root all the way down to the leaf node. |
| 357 | * |
| 358 | * Returns the address of the tagged item. Setting a tag on a not-present |
| 359 | * item is a bug. |
| 360 | */ |
| 361 | void *radix_tree_tag_set(struct radix_tree_root *root, |
| 362 | unsigned long index, int tag) |
| 363 | { |
| 364 | unsigned int height, shift; |
Christoph Lameter | 201b626 | 2005-09-06 15:16:46 -0700 | [diff] [blame] | 365 | struct radix_tree_node *slot; |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 366 | |
| 367 | height = root->height; |
| 368 | if (index > radix_tree_maxindex(height)) |
| 369 | return NULL; |
| 370 | |
| 371 | shift = (height - 1) * RADIX_TREE_MAP_SHIFT; |
Christoph Lameter | 201b626 | 2005-09-06 15:16:46 -0700 | [diff] [blame] | 372 | slot = root->rnode; |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 373 | |
| 374 | while (height > 0) { |
| 375 | int offset; |
| 376 | |
| 377 | offset = (index >> shift) & RADIX_TREE_MAP_MASK; |
Christoph Lameter | 201b626 | 2005-09-06 15:16:46 -0700 | [diff] [blame] | 378 | tag_set(slot, tag, offset); |
| 379 | slot = slot->slots[offset]; |
| 380 | BUG_ON(slot == NULL); |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 381 | shift -= RADIX_TREE_MAP_SHIFT; |
| 382 | height--; |
| 383 | } |
| 384 | |
Christoph Lameter | 201b626 | 2005-09-06 15:16:46 -0700 | [diff] [blame] | 385 | return slot; |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 386 | } |
| 387 | EXPORT_SYMBOL(radix_tree_tag_set); |
| 388 | |
| 389 | /** |
| 390 | * radix_tree_tag_clear - clear a tag on a radix tree node |
| 391 | * @root: radix tree root |
| 392 | * @index: index key |
| 393 | * @tag: tag index |
| 394 | * |
| 395 | * Clear the search tag corresponging to @index in the radix tree. If |
| 396 | * this causes the leaf node to have no tags set then clear the tag in the |
| 397 | * next-to-leaf node, etc. |
| 398 | * |
| 399 | * Returns the address of the tagged item on success, else NULL. ie: |
| 400 | * has the same return value and semantics as radix_tree_lookup(). |
| 401 | */ |
| 402 | void *radix_tree_tag_clear(struct radix_tree_root *root, |
| 403 | unsigned long index, int tag) |
| 404 | { |
| 405 | struct radix_tree_path path[RADIX_TREE_MAX_PATH], *pathp = path; |
Christoph Lameter | 201b626 | 2005-09-06 15:16:46 -0700 | [diff] [blame] | 406 | struct radix_tree_node *slot; |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 407 | unsigned int height, shift; |
| 408 | void *ret = NULL; |
| 409 | |
| 410 | height = root->height; |
| 411 | if (index > radix_tree_maxindex(height)) |
| 412 | goto out; |
| 413 | |
| 414 | shift = (height - 1) * RADIX_TREE_MAP_SHIFT; |
| 415 | pathp->node = NULL; |
Christoph Lameter | 201b626 | 2005-09-06 15:16:46 -0700 | [diff] [blame] | 416 | slot = root->rnode; |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 417 | |
| 418 | while (height > 0) { |
| 419 | int offset; |
| 420 | |
Christoph Lameter | 201b626 | 2005-09-06 15:16:46 -0700 | [diff] [blame] | 421 | if (slot == NULL) |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 422 | goto out; |
| 423 | |
| 424 | offset = (index >> shift) & RADIX_TREE_MAP_MASK; |
| 425 | pathp[1].offset = offset; |
Christoph Lameter | 201b626 | 2005-09-06 15:16:46 -0700 | [diff] [blame] | 426 | pathp[1].node = slot; |
| 427 | slot = slot->slots[offset]; |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 428 | pathp++; |
| 429 | shift -= RADIX_TREE_MAP_SHIFT; |
| 430 | height--; |
| 431 | } |
| 432 | |
Christoph Lameter | 201b626 | 2005-09-06 15:16:46 -0700 | [diff] [blame] | 433 | ret = slot; |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 434 | if (ret == NULL) |
| 435 | goto out; |
| 436 | |
| 437 | do { |
Christoph Lameter | 201b626 | 2005-09-06 15:16:46 -0700 | [diff] [blame] | 438 | tag_clear(pathp->node, tag, pathp->offset); |
Nick Piggin | 6e954b9 | 2006-01-08 01:01:40 -0800 | [diff] [blame^] | 439 | if (any_tag_set(pathp->node, tag)) |
| 440 | goto out; |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 441 | pathp--; |
Christoph Lameter | 201b626 | 2005-09-06 15:16:46 -0700 | [diff] [blame] | 442 | } while (pathp->node); |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 443 | out: |
| 444 | return ret; |
| 445 | } |
| 446 | EXPORT_SYMBOL(radix_tree_tag_clear); |
| 447 | |
| 448 | #ifndef __KERNEL__ /* Only the test harness uses this at present */ |
| 449 | /** |
Marcelo Tosatti | 32605a1 | 2005-09-06 15:16:48 -0700 | [diff] [blame] | 450 | * radix_tree_tag_get - get a tag on a radix tree node |
| 451 | * @root: radix tree root |
| 452 | * @index: index key |
| 453 | * @tag: tag index |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 454 | * |
Marcelo Tosatti | 32605a1 | 2005-09-06 15:16:48 -0700 | [diff] [blame] | 455 | * Return values: |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 456 | * |
Marcelo Tosatti | 32605a1 | 2005-09-06 15:16:48 -0700 | [diff] [blame] | 457 | * 0: tag not present |
| 458 | * 1: tag present, set |
| 459 | * -1: tag present, unset |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 460 | */ |
| 461 | int radix_tree_tag_get(struct radix_tree_root *root, |
| 462 | unsigned long index, int tag) |
| 463 | { |
| 464 | unsigned int height, shift; |
Christoph Lameter | 201b626 | 2005-09-06 15:16:46 -0700 | [diff] [blame] | 465 | struct radix_tree_node *slot; |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 466 | int saw_unset_tag = 0; |
| 467 | |
| 468 | height = root->height; |
| 469 | if (index > radix_tree_maxindex(height)) |
| 470 | return 0; |
| 471 | |
| 472 | shift = (height - 1) * RADIX_TREE_MAP_SHIFT; |
Christoph Lameter | 201b626 | 2005-09-06 15:16:46 -0700 | [diff] [blame] | 473 | slot = root->rnode; |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 474 | |
| 475 | for ( ; ; ) { |
| 476 | int offset; |
| 477 | |
Christoph Lameter | 201b626 | 2005-09-06 15:16:46 -0700 | [diff] [blame] | 478 | if (slot == NULL) |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 479 | return 0; |
| 480 | |
| 481 | offset = (index >> shift) & RADIX_TREE_MAP_MASK; |
| 482 | |
| 483 | /* |
| 484 | * This is just a debug check. Later, we can bale as soon as |
| 485 | * we see an unset tag. |
| 486 | */ |
Christoph Lameter | 201b626 | 2005-09-06 15:16:46 -0700 | [diff] [blame] | 487 | if (!tag_get(slot, tag, offset)) |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 488 | saw_unset_tag = 1; |
| 489 | if (height == 1) { |
Christoph Lameter | 201b626 | 2005-09-06 15:16:46 -0700 | [diff] [blame] | 490 | int ret = tag_get(slot, tag, offset); |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 491 | |
| 492 | BUG_ON(ret && saw_unset_tag); |
Marcelo Tosatti | 32605a1 | 2005-09-06 15:16:48 -0700 | [diff] [blame] | 493 | return ret ? 1 : -1; |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 494 | } |
Christoph Lameter | 201b626 | 2005-09-06 15:16:46 -0700 | [diff] [blame] | 495 | slot = slot->slots[offset]; |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 496 | shift -= RADIX_TREE_MAP_SHIFT; |
| 497 | height--; |
| 498 | } |
| 499 | } |
| 500 | EXPORT_SYMBOL(radix_tree_tag_get); |
| 501 | #endif |
| 502 | |
| 503 | static unsigned int |
| 504 | __lookup(struct radix_tree_root *root, void **results, unsigned long index, |
| 505 | unsigned int max_items, unsigned long *next_index) |
| 506 | { |
| 507 | unsigned int nr_found = 0; |
Christoph Lameter | 201b626 | 2005-09-06 15:16:46 -0700 | [diff] [blame] | 508 | unsigned int shift, height; |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 509 | struct radix_tree_node *slot; |
Christoph Lameter | 201b626 | 2005-09-06 15:16:46 -0700 | [diff] [blame] | 510 | unsigned long i; |
| 511 | |
| 512 | height = root->height; |
| 513 | if (height == 0) |
| 514 | goto out; |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 515 | |
| 516 | shift = (height-1) * RADIX_TREE_MAP_SHIFT; |
| 517 | slot = root->rnode; |
| 518 | |
Christoph Lameter | 201b626 | 2005-09-06 15:16:46 -0700 | [diff] [blame] | 519 | for ( ; height > 1; height--) { |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 520 | |
Christoph Lameter | 201b626 | 2005-09-06 15:16:46 -0700 | [diff] [blame] | 521 | for (i = (index >> shift) & RADIX_TREE_MAP_MASK ; |
| 522 | i < RADIX_TREE_MAP_SIZE; i++) { |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 523 | if (slot->slots[i] != NULL) |
| 524 | break; |
| 525 | index &= ~((1UL << shift) - 1); |
| 526 | index += 1UL << shift; |
| 527 | if (index == 0) |
| 528 | goto out; /* 32-bit wraparound */ |
| 529 | } |
| 530 | if (i == RADIX_TREE_MAP_SIZE) |
| 531 | goto out; |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 532 | |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 533 | shift -= RADIX_TREE_MAP_SHIFT; |
| 534 | slot = slot->slots[i]; |
| 535 | } |
Christoph Lameter | 201b626 | 2005-09-06 15:16:46 -0700 | [diff] [blame] | 536 | |
| 537 | /* Bottom level: grab some items */ |
| 538 | for (i = index & RADIX_TREE_MAP_MASK; i < RADIX_TREE_MAP_SIZE; i++) { |
| 539 | index++; |
| 540 | if (slot->slots[i]) { |
| 541 | results[nr_found++] = slot->slots[i]; |
| 542 | if (nr_found == max_items) |
| 543 | goto out; |
| 544 | } |
| 545 | } |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 546 | out: |
| 547 | *next_index = index; |
| 548 | return nr_found; |
| 549 | } |
| 550 | |
| 551 | /** |
| 552 | * radix_tree_gang_lookup - perform multiple lookup on a radix tree |
| 553 | * @root: radix tree root |
| 554 | * @results: where the results of the lookup are placed |
| 555 | * @first_index: start the lookup from this key |
| 556 | * @max_items: place up to this many items at *results |
| 557 | * |
| 558 | * Performs an index-ascending scan of the tree for present items. Places |
| 559 | * them at *@results and returns the number of items which were placed at |
| 560 | * *@results. |
| 561 | * |
| 562 | * The implementation is naive. |
| 563 | */ |
| 564 | unsigned int |
| 565 | radix_tree_gang_lookup(struct radix_tree_root *root, void **results, |
| 566 | unsigned long first_index, unsigned int max_items) |
| 567 | { |
| 568 | const unsigned long max_index = radix_tree_maxindex(root->height); |
| 569 | unsigned long cur_index = first_index; |
| 570 | unsigned int ret = 0; |
| 571 | |
| 572 | while (ret < max_items) { |
| 573 | unsigned int nr_found; |
| 574 | unsigned long next_index; /* Index of next search */ |
| 575 | |
| 576 | if (cur_index > max_index) |
| 577 | break; |
| 578 | nr_found = __lookup(root, results + ret, cur_index, |
| 579 | max_items - ret, &next_index); |
| 580 | ret += nr_found; |
| 581 | if (next_index == 0) |
| 582 | break; |
| 583 | cur_index = next_index; |
| 584 | } |
| 585 | return ret; |
| 586 | } |
| 587 | EXPORT_SYMBOL(radix_tree_gang_lookup); |
| 588 | |
| 589 | /* |
| 590 | * FIXME: the two tag_get()s here should use find_next_bit() instead of |
| 591 | * open-coding the search. |
| 592 | */ |
| 593 | static unsigned int |
| 594 | __lookup_tag(struct radix_tree_root *root, void **results, unsigned long index, |
| 595 | unsigned int max_items, unsigned long *next_index, int tag) |
| 596 | { |
| 597 | unsigned int nr_found = 0; |
| 598 | unsigned int shift; |
| 599 | unsigned int height = root->height; |
| 600 | struct radix_tree_node *slot; |
| 601 | |
| 602 | shift = (height - 1) * RADIX_TREE_MAP_SHIFT; |
| 603 | slot = root->rnode; |
| 604 | |
| 605 | while (height > 0) { |
| 606 | unsigned long i = (index >> shift) & RADIX_TREE_MAP_MASK; |
| 607 | |
| 608 | for ( ; i < RADIX_TREE_MAP_SIZE; i++) { |
| 609 | if (tag_get(slot, tag, i)) { |
| 610 | BUG_ON(slot->slots[i] == NULL); |
| 611 | break; |
| 612 | } |
| 613 | index &= ~((1UL << shift) - 1); |
| 614 | index += 1UL << shift; |
| 615 | if (index == 0) |
| 616 | goto out; /* 32-bit wraparound */ |
| 617 | } |
| 618 | if (i == RADIX_TREE_MAP_SIZE) |
| 619 | goto out; |
| 620 | height--; |
| 621 | if (height == 0) { /* Bottom level: grab some items */ |
| 622 | unsigned long j = index & RADIX_TREE_MAP_MASK; |
| 623 | |
| 624 | for ( ; j < RADIX_TREE_MAP_SIZE; j++) { |
| 625 | index++; |
| 626 | if (tag_get(slot, tag, j)) { |
| 627 | BUG_ON(slot->slots[j] == NULL); |
| 628 | results[nr_found++] = slot->slots[j]; |
| 629 | if (nr_found == max_items) |
| 630 | goto out; |
| 631 | } |
| 632 | } |
| 633 | } |
| 634 | shift -= RADIX_TREE_MAP_SHIFT; |
| 635 | slot = slot->slots[i]; |
| 636 | } |
| 637 | out: |
| 638 | *next_index = index; |
| 639 | return nr_found; |
| 640 | } |
| 641 | |
| 642 | /** |
| 643 | * radix_tree_gang_lookup_tag - perform multiple lookup on a radix tree |
| 644 | * based on a tag |
| 645 | * @root: radix tree root |
| 646 | * @results: where the results of the lookup are placed |
| 647 | * @first_index: start the lookup from this key |
| 648 | * @max_items: place up to this many items at *results |
| 649 | * @tag: the tag index |
| 650 | * |
| 651 | * Performs an index-ascending scan of the tree for present items which |
| 652 | * have the tag indexed by @tag set. Places the items at *@results and |
| 653 | * returns the number of items which were placed at *@results. |
| 654 | */ |
| 655 | unsigned int |
| 656 | radix_tree_gang_lookup_tag(struct radix_tree_root *root, void **results, |
| 657 | unsigned long first_index, unsigned int max_items, int tag) |
| 658 | { |
| 659 | const unsigned long max_index = radix_tree_maxindex(root->height); |
| 660 | unsigned long cur_index = first_index; |
| 661 | unsigned int ret = 0; |
| 662 | |
| 663 | while (ret < max_items) { |
| 664 | unsigned int nr_found; |
| 665 | unsigned long next_index; /* Index of next search */ |
| 666 | |
| 667 | if (cur_index > max_index) |
| 668 | break; |
| 669 | nr_found = __lookup_tag(root, results + ret, cur_index, |
| 670 | max_items - ret, &next_index, tag); |
| 671 | ret += nr_found; |
| 672 | if (next_index == 0) |
| 673 | break; |
| 674 | cur_index = next_index; |
| 675 | } |
| 676 | return ret; |
| 677 | } |
| 678 | EXPORT_SYMBOL(radix_tree_gang_lookup_tag); |
| 679 | |
| 680 | /** |
| 681 | * radix_tree_delete - delete an item from a radix tree |
| 682 | * @root: radix tree root |
| 683 | * @index: index key |
| 684 | * |
| 685 | * Remove the item at @index from the radix tree rooted at @root. |
| 686 | * |
| 687 | * Returns the address of the deleted item, or NULL if it was not present. |
| 688 | */ |
| 689 | void *radix_tree_delete(struct radix_tree_root *root, unsigned long index) |
| 690 | { |
| 691 | struct radix_tree_path path[RADIX_TREE_MAX_PATH], *pathp = path; |
| 692 | struct radix_tree_path *orig_pathp; |
Christoph Lameter | 201b626 | 2005-09-06 15:16:46 -0700 | [diff] [blame] | 693 | struct radix_tree_node *slot; |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 694 | unsigned int height, shift; |
| 695 | void *ret = NULL; |
| 696 | char tags[RADIX_TREE_TAGS]; |
| 697 | int nr_cleared_tags; |
| 698 | |
| 699 | height = root->height; |
| 700 | if (index > radix_tree_maxindex(height)) |
| 701 | goto out; |
| 702 | |
| 703 | shift = (height - 1) * RADIX_TREE_MAP_SHIFT; |
| 704 | pathp->node = NULL; |
Christoph Lameter | 201b626 | 2005-09-06 15:16:46 -0700 | [diff] [blame] | 705 | slot = root->rnode; |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 706 | |
Christoph Lameter | 201b626 | 2005-09-06 15:16:46 -0700 | [diff] [blame] | 707 | for ( ; height > 0; height--) { |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 708 | int offset; |
| 709 | |
Christoph Lameter | 201b626 | 2005-09-06 15:16:46 -0700 | [diff] [blame] | 710 | if (slot == NULL) |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 711 | goto out; |
| 712 | |
| 713 | offset = (index >> shift) & RADIX_TREE_MAP_MASK; |
| 714 | pathp[1].offset = offset; |
Christoph Lameter | 201b626 | 2005-09-06 15:16:46 -0700 | [diff] [blame] | 715 | pathp[1].node = slot; |
| 716 | slot = slot->slots[offset]; |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 717 | pathp++; |
| 718 | shift -= RADIX_TREE_MAP_SHIFT; |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 719 | } |
| 720 | |
Christoph Lameter | 201b626 | 2005-09-06 15:16:46 -0700 | [diff] [blame] | 721 | ret = slot; |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 722 | if (ret == NULL) |
| 723 | goto out; |
| 724 | |
| 725 | orig_pathp = pathp; |
| 726 | |
| 727 | /* |
| 728 | * Clear all tags associated with the just-deleted item |
| 729 | */ |
| 730 | memset(tags, 0, sizeof(tags)); |
| 731 | do { |
| 732 | int tag; |
| 733 | |
| 734 | nr_cleared_tags = RADIX_TREE_TAGS; |
| 735 | for (tag = 0; tag < RADIX_TREE_TAGS; tag++) { |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 736 | if (tags[tag]) |
| 737 | continue; |
| 738 | |
Christoph Lameter | 201b626 | 2005-09-06 15:16:46 -0700 | [diff] [blame] | 739 | tag_clear(pathp->node, tag, pathp->offset); |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 740 | |
Nick Piggin | 6e954b9 | 2006-01-08 01:01:40 -0800 | [diff] [blame^] | 741 | if (any_tag_set(pathp->node, tag)) { |
| 742 | tags[tag] = 1; |
| 743 | nr_cleared_tags--; |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 744 | } |
| 745 | } |
| 746 | pathp--; |
Christoph Lameter | 201b626 | 2005-09-06 15:16:46 -0700 | [diff] [blame] | 747 | } while (pathp->node && nr_cleared_tags); |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 748 | |
Christoph Lameter | 201b626 | 2005-09-06 15:16:46 -0700 | [diff] [blame] | 749 | /* Now free the nodes we do not need anymore */ |
| 750 | for (pathp = orig_pathp; pathp->node; pathp--) { |
| 751 | pathp->node->slots[pathp->offset] = NULL; |
| 752 | if (--pathp->node->count) |
| 753 | goto out; |
| 754 | |
| 755 | /* Node with zero slots in use so free it */ |
| 756 | radix_tree_node_free(pathp->node); |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 757 | } |
Christoph Lameter | 201b626 | 2005-09-06 15:16:46 -0700 | [diff] [blame] | 758 | root->rnode = NULL; |
| 759 | root->height = 0; |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 760 | out: |
| 761 | return ret; |
| 762 | } |
| 763 | EXPORT_SYMBOL(radix_tree_delete); |
| 764 | |
| 765 | /** |
| 766 | * radix_tree_tagged - test whether any items in the tree are tagged |
| 767 | * @root: radix tree root |
| 768 | * @tag: tag to test |
| 769 | */ |
| 770 | int radix_tree_tagged(struct radix_tree_root *root, int tag) |
| 771 | { |
Nick Piggin | 6e954b9 | 2006-01-08 01:01:40 -0800 | [diff] [blame^] | 772 | struct radix_tree_node *rnode; |
| 773 | rnode = root->rnode; |
| 774 | if (!rnode) |
| 775 | return 0; |
| 776 | return any_tag_set(rnode, tag); |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 777 | } |
| 778 | EXPORT_SYMBOL(radix_tree_tagged); |
| 779 | |
| 780 | static void |
| 781 | radix_tree_node_ctor(void *node, kmem_cache_t *cachep, unsigned long flags) |
| 782 | { |
| 783 | memset(node, 0, sizeof(struct radix_tree_node)); |
| 784 | } |
| 785 | |
| 786 | static __init unsigned long __maxindex(unsigned int height) |
| 787 | { |
| 788 | unsigned int tmp = height * RADIX_TREE_MAP_SHIFT; |
| 789 | unsigned long index = (~0UL >> (RADIX_TREE_INDEX_BITS - tmp - 1)) >> 1; |
| 790 | |
| 791 | if (tmp >= RADIX_TREE_INDEX_BITS) |
| 792 | index = ~0UL; |
| 793 | return index; |
| 794 | } |
| 795 | |
| 796 | static __init void radix_tree_init_maxindex(void) |
| 797 | { |
| 798 | unsigned int i; |
| 799 | |
| 800 | for (i = 0; i < ARRAY_SIZE(height_to_maxindex); i++) |
| 801 | height_to_maxindex[i] = __maxindex(i); |
| 802 | } |
| 803 | |
| 804 | #ifdef CONFIG_HOTPLUG_CPU |
| 805 | static int radix_tree_callback(struct notifier_block *nfb, |
| 806 | unsigned long action, |
| 807 | void *hcpu) |
| 808 | { |
| 809 | int cpu = (long)hcpu; |
| 810 | struct radix_tree_preload *rtp; |
| 811 | |
| 812 | /* Free per-cpu pool of perloaded nodes */ |
| 813 | if (action == CPU_DEAD) { |
| 814 | rtp = &per_cpu(radix_tree_preloads, cpu); |
| 815 | while (rtp->nr) { |
| 816 | kmem_cache_free(radix_tree_node_cachep, |
| 817 | rtp->nodes[rtp->nr-1]); |
| 818 | rtp->nodes[rtp->nr-1] = NULL; |
| 819 | rtp->nr--; |
| 820 | } |
| 821 | } |
| 822 | return NOTIFY_OK; |
| 823 | } |
| 824 | #endif /* CONFIG_HOTPLUG_CPU */ |
| 825 | |
| 826 | void __init radix_tree_init(void) |
| 827 | { |
| 828 | radix_tree_node_cachep = kmem_cache_create("radix_tree_node", |
| 829 | sizeof(struct radix_tree_node), 0, |
| 830 | SLAB_PANIC, radix_tree_node_ctor, NULL); |
| 831 | radix_tree_init_maxindex(); |
| 832 | hotcpu_notifier(radix_tree_callback, 0); |
| 833 | } |