1 /* 2 * Copyright (C) 2001 Momchil Velikov 3 * Portions Copyright (C) 2001 Christoph Hellwig 4 * Copyright (C) 2005 SGI, Christoph Lameter 5 * Copyright (C) 2006 Nick Piggin 6 * 7 * This program is free software; you can redistribute it and/or 8 * modify it under the terms of the GNU General Public License as 9 * published by the Free Software Foundation; either version 2, or (at 10 * your option) any later version. 11 * 12 * This program is distributed in the hope that it will be useful, but 13 * WITHOUT ANY WARRANTY; without even the implied warranty of 14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 15 * General Public License for more details. 16 * 17 * You should have received a copy of the GNU General Public License 18 * along with this program; if not, write to the Free Software 19 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. 20 */ 21 22 #include <linux/errno.h> 23 #include <linux/init.h> 24 #include <linux/kernel.h> 25 #include <linux/module.h> 26 #include <linux/radix-tree.h> 27 #include <linux/percpu.h> 28 #include <linux/slab.h> 29 #include <linux/notifier.h> 30 #include <linux/cpu.h> 31 #include <linux/string.h> 32 #include <linux/bitops.h> 33 #include <linux/rcupdate.h> 34 35 36 #ifdef __KERNEL__ 37 #define RADIX_TREE_MAP_SHIFT (CONFIG_BASE_SMALL ? 4 : 6) 38 #else 39 #define RADIX_TREE_MAP_SHIFT 3 /* For more stressful testing */ 40 #endif 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 height; /* Height from the bottom */ 50 unsigned int count; 51 struct rcu_head rcu_head; 52 void __rcu *slots[RADIX_TREE_MAP_SIZE]; 53 unsigned long tags[RADIX_TREE_MAX_TAGS][RADIX_TREE_TAG_LONGS]; 54 }; 55 56 struct radix_tree_path { 57 struct radix_tree_node *node; 58 int offset; 59 }; 60 61 #define RADIX_TREE_INDEX_BITS (8 /* CHAR_BIT */ * sizeof(unsigned long)) 62 #define RADIX_TREE_MAX_PATH (DIV_ROUND_UP(RADIX_TREE_INDEX_BITS, \ 63 RADIX_TREE_MAP_SHIFT)) 64 65 /* 66 * The height_to_maxindex array needs to be one deeper than the maximum 67 * path as height 0 holds only 1 entry. 68 */ 69 static unsigned long height_to_maxindex[RADIX_TREE_MAX_PATH + 1] __read_mostly; 70 71 /* 72 * Radix tree node cache. 73 */ 74 static struct kmem_cache *radix_tree_node_cachep; 75 76 /* 77 * Per-cpu pool of preloaded nodes 78 */ 79 struct radix_tree_preload { 80 int nr; 81 struct radix_tree_node *nodes[RADIX_TREE_MAX_PATH]; 82 }; 83 static DEFINE_PER_CPU(struct radix_tree_preload, radix_tree_preloads) = { 0, }; 84 85 static inline void *ptr_to_indirect(void *ptr) 86 { 87 return (void *)((unsigned long)ptr | RADIX_TREE_INDIRECT_PTR); 88 } 89 90 static inline void *indirect_to_ptr(void *ptr) 91 { 92 return (void *)((unsigned long)ptr & ~RADIX_TREE_INDIRECT_PTR); 93 } 94 95 static inline gfp_t root_gfp_mask(struct radix_tree_root *root) 96 { 97 return root->gfp_mask & __GFP_BITS_MASK; 98 } 99 100 static inline void tag_set(struct radix_tree_node *node, unsigned int tag, 101 int offset) 102 { 103 __set_bit(offset, node->tags[tag]); 104 } 105 106 static inline void tag_clear(struct radix_tree_node *node, unsigned int tag, 107 int offset) 108 { 109 __clear_bit(offset, node->tags[tag]); 110 } 111 112 static inline int tag_get(struct radix_tree_node *node, unsigned int tag, 113 int offset) 114 { 115 return test_bit(offset, node->tags[tag]); 116 } 117 118 static inline void root_tag_set(struct radix_tree_root *root, unsigned int tag) 119 { 120 root->gfp_mask |= (__force gfp_t)(1 << (tag + __GFP_BITS_SHIFT)); 121 } 122 123 static inline void root_tag_clear(struct radix_tree_root *root, unsigned int tag) 124 { 125 root->gfp_mask &= (__force gfp_t)~(1 << (tag + __GFP_BITS_SHIFT)); 126 } 127 128 static inline void root_tag_clear_all(struct radix_tree_root *root) 129 { 130 root->gfp_mask &= __GFP_BITS_MASK; 131 } 132 133 static inline int root_tag_get(struct radix_tree_root *root, unsigned int tag) 134 { 135 return (__force unsigned)root->gfp_mask & (1 << (tag + __GFP_BITS_SHIFT)); 136 } 137 138 /* 139 * Returns 1 if any slot in the node has this tag set. 140 * Otherwise returns 0. 141 */ 142 static inline int any_tag_set(struct radix_tree_node *node, unsigned int tag) 143 { 144 int idx; 145 for (idx = 0; idx < RADIX_TREE_TAG_LONGS; idx++) { 146 if (node->tags[tag][idx]) 147 return 1; 148 } 149 return 0; 150 } 151 /* 152 * This assumes that the caller has performed appropriate preallocation, and 153 * that the caller has pinned this thread of control to the current CPU. 154 */ 155 static struct radix_tree_node * 156 radix_tree_node_alloc(struct radix_tree_root *root) 157 { 158 struct radix_tree_node *ret = NULL; 159 gfp_t gfp_mask = root_gfp_mask(root); 160 161 if (!(gfp_mask & __GFP_WAIT)) { 162 struct radix_tree_preload *rtp; 163 164 /* 165 * Provided the caller has preloaded here, we will always 166 * succeed in getting a node here (and never reach 167 * kmem_cache_alloc) 168 */ 169 rtp = &__get_cpu_var(radix_tree_preloads); 170 if (rtp->nr) { 171 ret = rtp->nodes[rtp->nr - 1]; 172 rtp->nodes[rtp->nr - 1] = NULL; 173 rtp->nr--; 174 } 175 } 176 if (ret == NULL) 177 ret = kmem_cache_alloc(radix_tree_node_cachep, gfp_mask); 178 179 BUG_ON(radix_tree_is_indirect_ptr(ret)); 180 return ret; 181 } 182 183 static void radix_tree_node_rcu_free(struct rcu_head *head) 184 { 185 struct radix_tree_node *node = 186 container_of(head, struct radix_tree_node, rcu_head); 187 int i; 188 189 /* 190 * must only free zeroed nodes into the slab. radix_tree_shrink 191 * can leave us with a non-NULL entry in the first slot, so clear 192 * that here to make sure. 193 */ 194 for (i = 0; i < RADIX_TREE_MAX_TAGS; i++) 195 tag_clear(node, i, 0); 196 197 node->slots[0] = NULL; 198 node->count = 0; 199 200 kmem_cache_free(radix_tree_node_cachep, node); 201 } 202 203 static inline void 204 radix_tree_node_free(struct radix_tree_node *node) 205 { 206 call_rcu(&node->rcu_head, radix_tree_node_rcu_free); 207 } 208 209 /* 210 * Load up this CPU's radix_tree_node buffer with sufficient objects to 211 * ensure that the addition of a single element in the tree cannot fail. On 212 * success, return zero, with preemption disabled. On error, return -ENOMEM 213 * with preemption not disabled. 214 * 215 * To make use of this facility, the radix tree must be initialised without 216 * __GFP_WAIT being passed to INIT_RADIX_TREE(). 217 */ 218 int radix_tree_preload(gfp_t gfp_mask) 219 { 220 struct radix_tree_preload *rtp; 221 struct radix_tree_node *node; 222 int ret = -ENOMEM; 223 224 preempt_disable(); 225 rtp = &__get_cpu_var(radix_tree_preloads); 226 while (rtp->nr < ARRAY_SIZE(rtp->nodes)) { 227 preempt_enable(); 228 node = kmem_cache_alloc(radix_tree_node_cachep, gfp_mask); 229 if (node == NULL) 230 goto out; 231 preempt_disable(); 232 rtp = &__get_cpu_var(radix_tree_preloads); 233 if (rtp->nr < ARRAY_SIZE(rtp->nodes)) 234 rtp->nodes[rtp->nr++] = node; 235 else 236 kmem_cache_free(radix_tree_node_cachep, node); 237 } 238 ret = 0; 239 out: 240 return ret; 241 } 242 EXPORT_SYMBOL(radix_tree_preload); 243 244 /* 245 * Return the maximum key which can be store into a 246 * radix tree with height HEIGHT. 247 */ 248 static inline unsigned long radix_tree_maxindex(unsigned int height) 249 { 250 return height_to_maxindex[height]; 251 } 252 253 /* 254 * Extend a radix tree so it can store key @index. 255 */ 256 static int radix_tree_extend(struct radix_tree_root *root, unsigned long index) 257 { 258 struct radix_tree_node *node; 259 unsigned int height; 260 int tag; 261 262 /* Figure out what the height should be. */ 263 height = root->height + 1; 264 while (index > radix_tree_maxindex(height)) 265 height++; 266 267 if (root->rnode == NULL) { 268 root->height = height; 269 goto out; 270 } 271 272 do { 273 unsigned int newheight; 274 if (!(node = radix_tree_node_alloc(root))) 275 return -ENOMEM; 276 277 /* Increase the height. */ 278 node->slots[0] = indirect_to_ptr(root->rnode); 279 280 /* Propagate the aggregated tag info into the new root */ 281 for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) { 282 if (root_tag_get(root, tag)) 283 tag_set(node, tag, 0); 284 } 285 286 newheight = root->height+1; 287 node->height = newheight; 288 node->count = 1; 289 node = ptr_to_indirect(node); 290 rcu_assign_pointer(root->rnode, node); 291 root->height = newheight; 292 } while (height > root->height); 293 out: 294 return 0; 295 } 296 297 /** 298 * radix_tree_insert - insert into a radix tree 299 * @root: radix tree root 300 * @index: index key 301 * @item: item to insert 302 * 303 * Insert an item into the radix tree at position @index. 304 */ 305 int radix_tree_insert(struct radix_tree_root *root, 306 unsigned long index, void *item) 307 { 308 struct radix_tree_node *node = NULL, *slot; 309 unsigned int height, shift; 310 int offset; 311 int error; 312 313 BUG_ON(radix_tree_is_indirect_ptr(item)); 314 315 /* Make sure the tree is high enough. */ 316 if (index > radix_tree_maxindex(root->height)) { 317 error = radix_tree_extend(root, index); 318 if (error) 319 return error; 320 } 321 322 slot = indirect_to_ptr(root->rnode); 323 324 height = root->height; 325 shift = (height-1) * RADIX_TREE_MAP_SHIFT; 326 327 offset = 0; /* uninitialised var warning */ 328 while (height > 0) { 329 if (slot == NULL) { 330 /* Have to add a child node. */ 331 if (!(slot = radix_tree_node_alloc(root))) 332 return -ENOMEM; 333 slot->height = height; 334 if (node) { 335 rcu_assign_pointer(node->slots[offset], slot); 336 node->count++; 337 } else 338 rcu_assign_pointer(root->rnode, ptr_to_indirect(slot)); 339 } 340 341 /* Go a level down */ 342 offset = (index >> shift) & RADIX_TREE_MAP_MASK; 343 node = slot; 344 slot = node->slots[offset]; 345 shift -= RADIX_TREE_MAP_SHIFT; 346 height--; 347 } 348 349 if (slot != NULL) 350 return -EEXIST; 351 352 if (node) { 353 node->count++; 354 rcu_assign_pointer(node->slots[offset], item); 355 BUG_ON(tag_get(node, 0, offset)); 356 BUG_ON(tag_get(node, 1, offset)); 357 } else { 358 rcu_assign_pointer(root->rnode, item); 359 BUG_ON(root_tag_get(root, 0)); 360 BUG_ON(root_tag_get(root, 1)); 361 } 362 363 return 0; 364 } 365 EXPORT_SYMBOL(radix_tree_insert); 366 367 /* 368 * is_slot == 1 : search for the slot. 369 * is_slot == 0 : search for the node. 370 */ 371 static void *radix_tree_lookup_element(struct radix_tree_root *root, 372 unsigned long index, int is_slot) 373 { 374 unsigned int height, shift; 375 struct radix_tree_node *node, **slot; 376 377 node = rcu_dereference_raw(root->rnode); 378 if (node == NULL) 379 return NULL; 380 381 if (!radix_tree_is_indirect_ptr(node)) { 382 if (index > 0) 383 return NULL; 384 return is_slot ? (void *)&root->rnode : node; 385 } 386 node = indirect_to_ptr(node); 387 388 height = node->height; 389 if (index > radix_tree_maxindex(height)) 390 return NULL; 391 392 shift = (height-1) * RADIX_TREE_MAP_SHIFT; 393 394 do { 395 slot = (struct radix_tree_node **) 396 (node->slots + ((index>>shift) & RADIX_TREE_MAP_MASK)); 397 node = rcu_dereference_raw(*slot); 398 if (node == NULL) 399 return NULL; 400 401 shift -= RADIX_TREE_MAP_SHIFT; 402 height--; 403 } while (height > 0); 404 405 return is_slot ? (void *)slot : indirect_to_ptr(node); 406 } 407 408 /** 409 * radix_tree_lookup_slot - lookup a slot in a radix tree 410 * @root: radix tree root 411 * @index: index key 412 * 413 * Returns: the slot corresponding to the position @index in the 414 * radix tree @root. This is useful for update-if-exists operations. 415 * 416 * This function can be called under rcu_read_lock iff the slot is not 417 * modified by radix_tree_replace_slot, otherwise it must be called 418 * exclusive from other writers. Any dereference of the slot must be done 419 * using radix_tree_deref_slot. 420 */ 421 void **radix_tree_lookup_slot(struct radix_tree_root *root, unsigned long index) 422 { 423 return (void **)radix_tree_lookup_element(root, index, 1); 424 } 425 EXPORT_SYMBOL(radix_tree_lookup_slot); 426 427 /** 428 * radix_tree_lookup - perform lookup operation on a radix tree 429 * @root: radix tree root 430 * @index: index key 431 * 432 * Lookup the item at the position @index in the radix tree @root. 433 * 434 * This function can be called under rcu_read_lock, however the caller 435 * must manage lifetimes of leaf nodes (eg. RCU may also be used to free 436 * them safely). No RCU barriers are required to access or modify the 437 * returned item, however. 438 */ 439 void *radix_tree_lookup(struct radix_tree_root *root, unsigned long index) 440 { 441 return radix_tree_lookup_element(root, index, 0); 442 } 443 EXPORT_SYMBOL(radix_tree_lookup); 444 445 /** 446 * radix_tree_tag_set - set a tag on a radix tree node 447 * @root: radix tree root 448 * @index: index key 449 * @tag: tag index 450 * 451 * Set the search tag (which must be < RADIX_TREE_MAX_TAGS) 452 * corresponding to @index in the radix tree. From 453 * the root all the way down to the leaf node. 454 * 455 * Returns the address of the tagged item. Setting a tag on a not-present 456 * item is a bug. 457 */ 458 void *radix_tree_tag_set(struct radix_tree_root *root, 459 unsigned long index, unsigned int tag) 460 { 461 unsigned int height, shift; 462 struct radix_tree_node *slot; 463 464 height = root->height; 465 BUG_ON(index > radix_tree_maxindex(height)); 466 467 slot = indirect_to_ptr(root->rnode); 468 shift = (height - 1) * RADIX_TREE_MAP_SHIFT; 469 470 while (height > 0) { 471 int offset; 472 473 offset = (index >> shift) & RADIX_TREE_MAP_MASK; 474 if (!tag_get(slot, tag, offset)) 475 tag_set(slot, tag, offset); 476 slot = slot->slots[offset]; 477 BUG_ON(slot == NULL); 478 shift -= RADIX_TREE_MAP_SHIFT; 479 height--; 480 } 481 482 /* set the root's tag bit */ 483 if (slot && !root_tag_get(root, tag)) 484 root_tag_set(root, tag); 485 486 return slot; 487 } 488 EXPORT_SYMBOL(radix_tree_tag_set); 489 490 /** 491 * radix_tree_tag_clear - clear a tag on a radix tree node 492 * @root: radix tree root 493 * @index: index key 494 * @tag: tag index 495 * 496 * Clear the search tag (which must be < RADIX_TREE_MAX_TAGS) 497 * corresponding to @index in the radix tree. If 498 * this causes the leaf node to have no tags set then clear the tag in the 499 * next-to-leaf node, etc. 500 * 501 * Returns the address of the tagged item on success, else NULL. ie: 502 * has the same return value and semantics as radix_tree_lookup(). 503 */ 504 void *radix_tree_tag_clear(struct radix_tree_root *root, 505 unsigned long index, unsigned int tag) 506 { 507 /* 508 * The radix tree path needs to be one longer than the maximum path 509 * since the "list" is null terminated. 510 */ 511 struct radix_tree_path path[RADIX_TREE_MAX_PATH + 1], *pathp = path; 512 struct radix_tree_node *slot = NULL; 513 unsigned int height, shift; 514 515 height = root->height; 516 if (index > radix_tree_maxindex(height)) 517 goto out; 518 519 shift = (height - 1) * RADIX_TREE_MAP_SHIFT; 520 pathp->node = NULL; 521 slot = indirect_to_ptr(root->rnode); 522 523 while (height > 0) { 524 int offset; 525 526 if (slot == NULL) 527 goto out; 528 529 offset = (index >> shift) & RADIX_TREE_MAP_MASK; 530 pathp[1].offset = offset; 531 pathp[1].node = slot; 532 slot = slot->slots[offset]; 533 pathp++; 534 shift -= RADIX_TREE_MAP_SHIFT; 535 height--; 536 } 537 538 if (slot == NULL) 539 goto out; 540 541 while (pathp->node) { 542 if (!tag_get(pathp->node, tag, pathp->offset)) 543 goto out; 544 tag_clear(pathp->node, tag, pathp->offset); 545 if (any_tag_set(pathp->node, tag)) 546 goto out; 547 pathp--; 548 } 549 550 /* clear the root's tag bit */ 551 if (root_tag_get(root, tag)) 552 root_tag_clear(root, tag); 553 554 out: 555 return slot; 556 } 557 EXPORT_SYMBOL(radix_tree_tag_clear); 558 559 /** 560 * radix_tree_tag_get - get a tag on a radix tree node 561 * @root: radix tree root 562 * @index: index key 563 * @tag: tag index (< RADIX_TREE_MAX_TAGS) 564 * 565 * Return values: 566 * 567 * 0: tag not present or not set 568 * 1: tag set 569 * 570 * Note that the return value of this function may not be relied on, even if 571 * the RCU lock is held, unless tag modification and node deletion are excluded 572 * from concurrency. 573 */ 574 int radix_tree_tag_get(struct radix_tree_root *root, 575 unsigned long index, unsigned int tag) 576 { 577 unsigned int height, shift; 578 struct radix_tree_node *node; 579 int saw_unset_tag = 0; 580 581 /* check the root's tag bit */ 582 if (!root_tag_get(root, tag)) 583 return 0; 584 585 node = rcu_dereference_raw(root->rnode); 586 if (node == NULL) 587 return 0; 588 589 if (!radix_tree_is_indirect_ptr(node)) 590 return (index == 0); 591 node = indirect_to_ptr(node); 592 593 height = node->height; 594 if (index > radix_tree_maxindex(height)) 595 return 0; 596 597 shift = (height - 1) * RADIX_TREE_MAP_SHIFT; 598 599 for ( ; ; ) { 600 int offset; 601 602 if (node == NULL) 603 return 0; 604 605 offset = (index >> shift) & RADIX_TREE_MAP_MASK; 606 607 /* 608 * This is just a debug check. Later, we can bale as soon as 609 * we see an unset tag. 610 */ 611 if (!tag_get(node, tag, offset)) 612 saw_unset_tag = 1; 613 if (height == 1) 614 return !!tag_get(node, tag, offset); 615 node = rcu_dereference_raw(node->slots[offset]); 616 shift -= RADIX_TREE_MAP_SHIFT; 617 height--; 618 } 619 } 620 EXPORT_SYMBOL(radix_tree_tag_get); 621 622 /** 623 * radix_tree_range_tag_if_tagged - for each item in given range set given 624 * tag if item has another tag set 625 * @root: radix tree root 626 * @first_indexp: pointer to a starting index of a range to scan 627 * @last_index: last index of a range to scan 628 * @nr_to_tag: maximum number items to tag 629 * @iftag: tag index to test 630 * @settag: tag index to set if tested tag is set 631 * 632 * This function scans range of radix tree from first_index to last_index 633 * (inclusive). For each item in the range if iftag is set, the function sets 634 * also settag. The function stops either after tagging nr_to_tag items or 635 * after reaching last_index. 636 * 637 * The tags must be set from the leaf level only and propagated back up the 638 * path to the root. We must do this so that we resolve the full path before 639 * setting any tags on intermediate nodes. If we set tags as we descend, then 640 * we can get to the leaf node and find that the index that has the iftag 641 * set is outside the range we are scanning. This reults in dangling tags and 642 * can lead to problems with later tag operations (e.g. livelocks on lookups). 643 * 644 * The function returns number of leaves where the tag was set and sets 645 * *first_indexp to the first unscanned index. 646 * WARNING! *first_indexp can wrap if last_index is ULONG_MAX. Caller must 647 * be prepared to handle that. 648 */ 649 unsigned long radix_tree_range_tag_if_tagged(struct radix_tree_root *root, 650 unsigned long *first_indexp, unsigned long last_index, 651 unsigned long nr_to_tag, 652 unsigned int iftag, unsigned int settag) 653 { 654 unsigned int height = root->height; 655 struct radix_tree_path path[height]; 656 struct radix_tree_path *pathp = path; 657 struct radix_tree_node *slot; 658 unsigned int shift; 659 unsigned long tagged = 0; 660 unsigned long index = *first_indexp; 661 662 last_index = min(last_index, radix_tree_maxindex(height)); 663 if (index > last_index) 664 return 0; 665 if (!nr_to_tag) 666 return 0; 667 if (!root_tag_get(root, iftag)) { 668 *first_indexp = last_index + 1; 669 return 0; 670 } 671 if (height == 0) { 672 *first_indexp = last_index + 1; 673 root_tag_set(root, settag); 674 return 1; 675 } 676 677 shift = (height - 1) * RADIX_TREE_MAP_SHIFT; 678 slot = indirect_to_ptr(root->rnode); 679 680 /* 681 * we fill the path from (root->height - 2) to 0, leaving the index at 682 * (root->height - 1) as a terminator. Zero the node in the terminator 683 * so that we can use this to end walk loops back up the path. 684 */ 685 path[height - 1].node = NULL; 686 687 for (;;) { 688 int offset; 689 690 offset = (index >> shift) & RADIX_TREE_MAP_MASK; 691 if (!slot->slots[offset]) 692 goto next; 693 if (!tag_get(slot, iftag, offset)) 694 goto next; 695 if (height > 1) { 696 /* Go down one level */ 697 height--; 698 shift -= RADIX_TREE_MAP_SHIFT; 699 path[height - 1].node = slot; 700 path[height - 1].offset = offset; 701 slot = slot->slots[offset]; 702 continue; 703 } 704 705 /* tag the leaf */ 706 tagged++; 707 tag_set(slot, settag, offset); 708 709 /* walk back up the path tagging interior nodes */ 710 pathp = &path[0]; 711 while (pathp->node) { 712 /* stop if we find a node with the tag already set */ 713 if (tag_get(pathp->node, settag, pathp->offset)) 714 break; 715 tag_set(pathp->node, settag, pathp->offset); 716 pathp++; 717 } 718 719 next: 720 /* Go to next item at level determined by 'shift' */ 721 index = ((index >> shift) + 1) << shift; 722 /* Overflow can happen when last_index is ~0UL... */ 723 if (index > last_index || !index) 724 break; 725 if (tagged >= nr_to_tag) 726 break; 727 while (((index >> shift) & RADIX_TREE_MAP_MASK) == 0) { 728 /* 729 * We've fully scanned this node. Go up. Because 730 * last_index is guaranteed to be in the tree, what 731 * we do below cannot wander astray. 732 */ 733 slot = path[height - 1].node; 734 height++; 735 shift += RADIX_TREE_MAP_SHIFT; 736 } 737 } 738 /* 739 * We need not to tag the root tag if there is no tag which is set with 740 * settag within the range from *first_indexp to last_index. 741 */ 742 if (tagged > 0) 743 root_tag_set(root, settag); 744 *first_indexp = index; 745 746 return tagged; 747 } 748 EXPORT_SYMBOL(radix_tree_range_tag_if_tagged); 749 750 751 /** 752 * radix_tree_next_hole - find the next hole (not-present entry) 753 * @root: tree root 754 * @index: index key 755 * @max_scan: maximum range to search 756 * 757 * Search the set [index, min(index+max_scan-1, MAX_INDEX)] for the lowest 758 * indexed hole. 759 * 760 * Returns: the index of the hole if found, otherwise returns an index 761 * outside of the set specified (in which case 'return - index >= max_scan' 762 * will be true). In rare cases of index wrap-around, 0 will be returned. 763 * 764 * radix_tree_next_hole may be called under rcu_read_lock. However, like 765 * radix_tree_gang_lookup, this will not atomically search a snapshot of 766 * the tree at a single point in time. For example, if a hole is created 767 * at index 5, then subsequently a hole is created at index 10, 768 * radix_tree_next_hole covering both indexes may return 10 if called 769 * under rcu_read_lock. 770 */ 771 unsigned long radix_tree_next_hole(struct radix_tree_root *root, 772 unsigned long index, unsigned long max_scan) 773 { 774 unsigned long i; 775 776 for (i = 0; i < max_scan; i++) { 777 if (!radix_tree_lookup(root, index)) 778 break; 779 index++; 780 if (index == 0) 781 break; 782 } 783 784 return index; 785 } 786 EXPORT_SYMBOL(radix_tree_next_hole); 787 788 /** 789 * radix_tree_prev_hole - find the prev hole (not-present entry) 790 * @root: tree root 791 * @index: index key 792 * @max_scan: maximum range to search 793 * 794 * Search backwards in the range [max(index-max_scan+1, 0), index] 795 * for the first hole. 796 * 797 * Returns: the index of the hole if found, otherwise returns an index 798 * outside of the set specified (in which case 'index - return >= max_scan' 799 * will be true). In rare cases of wrap-around, ULONG_MAX will be returned. 800 * 801 * radix_tree_next_hole may be called under rcu_read_lock. However, like 802 * radix_tree_gang_lookup, this will not atomically search a snapshot of 803 * the tree at a single point in time. For example, if a hole is created 804 * at index 10, then subsequently a hole is created at index 5, 805 * radix_tree_prev_hole covering both indexes may return 5 if called under 806 * rcu_read_lock. 807 */ 808 unsigned long radix_tree_prev_hole(struct radix_tree_root *root, 809 unsigned long index, unsigned long max_scan) 810 { 811 unsigned long i; 812 813 for (i = 0; i < max_scan; i++) { 814 if (!radix_tree_lookup(root, index)) 815 break; 816 index--; 817 if (index == ULONG_MAX) 818 break; 819 } 820 821 return index; 822 } 823 EXPORT_SYMBOL(radix_tree_prev_hole); 824 825 static unsigned int 826 __lookup(struct radix_tree_node *slot, void ***results, unsigned long *indices, 827 unsigned long index, unsigned int max_items, unsigned long *next_index) 828 { 829 unsigned int nr_found = 0; 830 unsigned int shift, height; 831 unsigned long i; 832 833 height = slot->height; 834 if (height == 0) 835 goto out; 836 shift = (height-1) * RADIX_TREE_MAP_SHIFT; 837 838 for ( ; height > 1; height--) { 839 i = (index >> shift) & RADIX_TREE_MAP_MASK; 840 for (;;) { 841 if (slot->slots[i] != NULL) 842 break; 843 index &= ~((1UL << shift) - 1); 844 index += 1UL << shift; 845 if (index == 0) 846 goto out; /* 32-bit wraparound */ 847 i++; 848 if (i == RADIX_TREE_MAP_SIZE) 849 goto out; 850 } 851 852 shift -= RADIX_TREE_MAP_SHIFT; 853 slot = rcu_dereference_raw(slot->slots[i]); 854 if (slot == NULL) 855 goto out; 856 } 857 858 /* Bottom level: grab some items */ 859 for (i = index & RADIX_TREE_MAP_MASK; i < RADIX_TREE_MAP_SIZE; i++) { 860 if (slot->slots[i]) { 861 results[nr_found] = &(slot->slots[i]); 862 if (indices) 863 indices[nr_found] = index; 864 if (++nr_found == max_items) { 865 index++; 866 goto out; 867 } 868 } 869 index++; 870 } 871 out: 872 *next_index = index; 873 return nr_found; 874 } 875 876 /** 877 * radix_tree_gang_lookup - perform multiple lookup on a radix tree 878 * @root: radix tree root 879 * @results: where the results of the lookup are placed 880 * @first_index: start the lookup from this key 881 * @max_items: place up to this many items at *results 882 * 883 * Performs an index-ascending scan of the tree for present items. Places 884 * them at *@results and returns the number of items which were placed at 885 * *@results. 886 * 887 * The implementation is naive. 888 * 889 * Like radix_tree_lookup, radix_tree_gang_lookup may be called under 890 * rcu_read_lock. In this case, rather than the returned results being 891 * an atomic snapshot of the tree at a single point in time, the semantics 892 * of an RCU protected gang lookup are as though multiple radix_tree_lookups 893 * have been issued in individual locks, and results stored in 'results'. 894 */ 895 unsigned int 896 radix_tree_gang_lookup(struct radix_tree_root *root, void **results, 897 unsigned long first_index, unsigned int max_items) 898 { 899 unsigned long max_index; 900 struct radix_tree_node *node; 901 unsigned long cur_index = first_index; 902 unsigned int ret; 903 904 node = rcu_dereference_raw(root->rnode); 905 if (!node) 906 return 0; 907 908 if (!radix_tree_is_indirect_ptr(node)) { 909 if (first_index > 0) 910 return 0; 911 results[0] = node; 912 return 1; 913 } 914 node = indirect_to_ptr(node); 915 916 max_index = radix_tree_maxindex(node->height); 917 918 ret = 0; 919 while (ret < max_items) { 920 unsigned int nr_found, slots_found, i; 921 unsigned long next_index; /* Index of next search */ 922 923 if (cur_index > max_index) 924 break; 925 slots_found = __lookup(node, (void ***)results + ret, NULL, 926 cur_index, max_items - ret, &next_index); 927 nr_found = 0; 928 for (i = 0; i < slots_found; i++) { 929 struct radix_tree_node *slot; 930 slot = *(((void ***)results)[ret + i]); 931 if (!slot) 932 continue; 933 results[ret + nr_found] = 934 indirect_to_ptr(rcu_dereference_raw(slot)); 935 nr_found++; 936 } 937 ret += nr_found; 938 if (next_index == 0) 939 break; 940 cur_index = next_index; 941 } 942 943 return ret; 944 } 945 EXPORT_SYMBOL(radix_tree_gang_lookup); 946 947 /** 948 * radix_tree_gang_lookup_slot - perform multiple slot lookup on radix tree 949 * @root: radix tree root 950 * @results: where the results of the lookup are placed 951 * @indices: where their indices should be placed (but usually NULL) 952 * @first_index: start the lookup from this key 953 * @max_items: place up to this many items at *results 954 * 955 * Performs an index-ascending scan of the tree for present items. Places 956 * their slots at *@results and returns the number of items which were 957 * placed at *@results. 958 * 959 * The implementation is naive. 960 * 961 * Like radix_tree_gang_lookup as far as RCU and locking goes. Slots must 962 * be dereferenced with radix_tree_deref_slot, and if using only RCU 963 * protection, radix_tree_deref_slot may fail requiring a retry. 964 */ 965 unsigned int 966 radix_tree_gang_lookup_slot(struct radix_tree_root *root, 967 void ***results, unsigned long *indices, 968 unsigned long first_index, unsigned int max_items) 969 { 970 unsigned long max_index; 971 struct radix_tree_node *node; 972 unsigned long cur_index = first_index; 973 unsigned int ret; 974 975 node = rcu_dereference_raw(root->rnode); 976 if (!node) 977 return 0; 978 979 if (!radix_tree_is_indirect_ptr(node)) { 980 if (first_index > 0) 981 return 0; 982 results[0] = (void **)&root->rnode; 983 if (indices) 984 indices[0] = 0; 985 return 1; 986 } 987 node = indirect_to_ptr(node); 988 989 max_index = radix_tree_maxindex(node->height); 990 991 ret = 0; 992 while (ret < max_items) { 993 unsigned int slots_found; 994 unsigned long next_index; /* Index of next search */ 995 996 if (cur_index > max_index) 997 break; 998 slots_found = __lookup(node, results + ret, 999 indices ? indices + ret : NULL, 1000 cur_index, max_items - ret, &next_index); 1001 ret += slots_found; 1002 if (next_index == 0) 1003 break; 1004 cur_index = next_index; 1005 } 1006 1007 return ret; 1008 } 1009 EXPORT_SYMBOL(radix_tree_gang_lookup_slot); 1010 1011 /* 1012 * FIXME: the two tag_get()s here should use find_next_bit() instead of 1013 * open-coding the search. 1014 */ 1015 static unsigned int 1016 __lookup_tag(struct radix_tree_node *slot, void ***results, unsigned long index, 1017 unsigned int max_items, unsigned long *next_index, unsigned int tag) 1018 { 1019 unsigned int nr_found = 0; 1020 unsigned int shift, height; 1021 1022 height = slot->height; 1023 if (height == 0) 1024 goto out; 1025 shift = (height-1) * RADIX_TREE_MAP_SHIFT; 1026 1027 while (height > 0) { 1028 unsigned long i = (index >> shift) & RADIX_TREE_MAP_MASK ; 1029 1030 for (;;) { 1031 if (tag_get(slot, tag, i)) 1032 break; 1033 index &= ~((1UL << shift) - 1); 1034 index += 1UL << shift; 1035 if (index == 0) 1036 goto out; /* 32-bit wraparound */ 1037 i++; 1038 if (i == RADIX_TREE_MAP_SIZE) 1039 goto out; 1040 } 1041 height--; 1042 if (height == 0) { /* Bottom level: grab some items */ 1043 unsigned long j = index & RADIX_TREE_MAP_MASK; 1044 1045 for ( ; j < RADIX_TREE_MAP_SIZE; j++) { 1046 index++; 1047 if (!tag_get(slot, tag, j)) 1048 continue; 1049 /* 1050 * Even though the tag was found set, we need to 1051 * recheck that we have a non-NULL node, because 1052 * if this lookup is lockless, it may have been 1053 * subsequently deleted. 1054 * 1055 * Similar care must be taken in any place that 1056 * lookup ->slots[x] without a lock (ie. can't 1057 * rely on its value remaining the same). 1058 */ 1059 if (slot->slots[j]) { 1060 results[nr_found++] = &(slot->slots[j]); 1061 if (nr_found == max_items) 1062 goto out; 1063 } 1064 } 1065 } 1066 shift -= RADIX_TREE_MAP_SHIFT; 1067 slot = rcu_dereference_raw(slot->slots[i]); 1068 if (slot == NULL) 1069 break; 1070 } 1071 out: 1072 *next_index = index; 1073 return nr_found; 1074 } 1075 1076 /** 1077 * radix_tree_gang_lookup_tag - perform multiple lookup on a radix tree 1078 * based on a tag 1079 * @root: radix tree root 1080 * @results: where the results of the lookup are placed 1081 * @first_index: start the lookup from this key 1082 * @max_items: place up to this many items at *results 1083 * @tag: the tag index (< RADIX_TREE_MAX_TAGS) 1084 * 1085 * Performs an index-ascending scan of the tree for present items which 1086 * have the tag indexed by @tag set. Places the items at *@results and 1087 * returns the number of items which were placed at *@results. 1088 */ 1089 unsigned int 1090 radix_tree_gang_lookup_tag(struct radix_tree_root *root, void **results, 1091 unsigned long first_index, unsigned int max_items, 1092 unsigned int tag) 1093 { 1094 struct radix_tree_node *node; 1095 unsigned long max_index; 1096 unsigned long cur_index = first_index; 1097 unsigned int ret; 1098 1099 /* check the root's tag bit */ 1100 if (!root_tag_get(root, tag)) 1101 return 0; 1102 1103 node = rcu_dereference_raw(root->rnode); 1104 if (!node) 1105 return 0; 1106 1107 if (!radix_tree_is_indirect_ptr(node)) { 1108 if (first_index > 0) 1109 return 0; 1110 results[0] = node; 1111 return 1; 1112 } 1113 node = indirect_to_ptr(node); 1114 1115 max_index = radix_tree_maxindex(node->height); 1116 1117 ret = 0; 1118 while (ret < max_items) { 1119 unsigned int nr_found, slots_found, i; 1120 unsigned long next_index; /* Index of next search */ 1121 1122 if (cur_index > max_index) 1123 break; 1124 slots_found = __lookup_tag(node, (void ***)results + ret, 1125 cur_index, max_items - ret, &next_index, tag); 1126 nr_found = 0; 1127 for (i = 0; i < slots_found; i++) { 1128 struct radix_tree_node *slot; 1129 slot = *(((void ***)results)[ret + i]); 1130 if (!slot) 1131 continue; 1132 results[ret + nr_found] = 1133 indirect_to_ptr(rcu_dereference_raw(slot)); 1134 nr_found++; 1135 } 1136 ret += nr_found; 1137 if (next_index == 0) 1138 break; 1139 cur_index = next_index; 1140 } 1141 1142 return ret; 1143 } 1144 EXPORT_SYMBOL(radix_tree_gang_lookup_tag); 1145 1146 /** 1147 * radix_tree_gang_lookup_tag_slot - perform multiple slot lookup on a 1148 * radix tree based on a tag 1149 * @root: radix tree root 1150 * @results: where the results of the lookup are placed 1151 * @first_index: start the lookup from this key 1152 * @max_items: place up to this many items at *results 1153 * @tag: the tag index (< RADIX_TREE_MAX_TAGS) 1154 * 1155 * Performs an index-ascending scan of the tree for present items which 1156 * have the tag indexed by @tag set. Places the slots at *@results and 1157 * returns the number of slots which were placed at *@results. 1158 */ 1159 unsigned int 1160 radix_tree_gang_lookup_tag_slot(struct radix_tree_root *root, void ***results, 1161 unsigned long first_index, unsigned int max_items, 1162 unsigned int tag) 1163 { 1164 struct radix_tree_node *node; 1165 unsigned long max_index; 1166 unsigned long cur_index = first_index; 1167 unsigned int ret; 1168 1169 /* check the root's tag bit */ 1170 if (!root_tag_get(root, tag)) 1171 return 0; 1172 1173 node = rcu_dereference_raw(root->rnode); 1174 if (!node) 1175 return 0; 1176 1177 if (!radix_tree_is_indirect_ptr(node)) { 1178 if (first_index > 0) 1179 return 0; 1180 results[0] = (void **)&root->rnode; 1181 return 1; 1182 } 1183 node = indirect_to_ptr(node); 1184 1185 max_index = radix_tree_maxindex(node->height); 1186 1187 ret = 0; 1188 while (ret < max_items) { 1189 unsigned int slots_found; 1190 unsigned long next_index; /* Index of next search */ 1191 1192 if (cur_index > max_index) 1193 break; 1194 slots_found = __lookup_tag(node, results + ret, 1195 cur_index, max_items - ret, &next_index, tag); 1196 ret += slots_found; 1197 if (next_index == 0) 1198 break; 1199 cur_index = next_index; 1200 } 1201 1202 return ret; 1203 } 1204 EXPORT_SYMBOL(radix_tree_gang_lookup_tag_slot); 1205 1206 #if defined(CONFIG_SHMEM) && defined(CONFIG_SWAP) 1207 #include <linux/sched.h> /* for cond_resched() */ 1208 1209 /* 1210 * This linear search is at present only useful to shmem_unuse_inode(). 1211 */ 1212 static unsigned long __locate(struct radix_tree_node *slot, void *item, 1213 unsigned long index, unsigned long *found_index) 1214 { 1215 unsigned int shift, height; 1216 unsigned long i; 1217 1218 height = slot->height; 1219 shift = (height-1) * RADIX_TREE_MAP_SHIFT; 1220 1221 for ( ; height > 1; height--) { 1222 i = (index >> shift) & RADIX_TREE_MAP_MASK; 1223 for (;;) { 1224 if (slot->slots[i] != NULL) 1225 break; 1226 index &= ~((1UL << shift) - 1); 1227 index += 1UL << shift; 1228 if (index == 0) 1229 goto out; /* 32-bit wraparound */ 1230 i++; 1231 if (i == RADIX_TREE_MAP_SIZE) 1232 goto out; 1233 } 1234 1235 shift -= RADIX_TREE_MAP_SHIFT; 1236 slot = rcu_dereference_raw(slot->slots[i]); 1237 if (slot == NULL) 1238 goto out; 1239 } 1240 1241 /* Bottom level: check items */ 1242 for (i = 0; i < RADIX_TREE_MAP_SIZE; i++) { 1243 if (slot->slots[i] == item) { 1244 *found_index = index + i; 1245 index = 0; 1246 goto out; 1247 } 1248 } 1249 index += RADIX_TREE_MAP_SIZE; 1250 out: 1251 return index; 1252 } 1253 1254 /** 1255 * radix_tree_locate_item - search through radix tree for item 1256 * @root: radix tree root 1257 * @item: item to be found 1258 * 1259 * Returns index where item was found, or -1 if not found. 1260 * Caller must hold no lock (since this time-consuming function needs 1261 * to be preemptible), and must check afterwards if item is still there. 1262 */ 1263 unsigned long radix_tree_locate_item(struct radix_tree_root *root, void *item) 1264 { 1265 struct radix_tree_node *node; 1266 unsigned long max_index; 1267 unsigned long cur_index = 0; 1268 unsigned long found_index = -1; 1269 1270 do { 1271 rcu_read_lock(); 1272 node = rcu_dereference_raw(root->rnode); 1273 if (!radix_tree_is_indirect_ptr(node)) { 1274 rcu_read_unlock(); 1275 if (node == item) 1276 found_index = 0; 1277 break; 1278 } 1279 1280 node = indirect_to_ptr(node); 1281 max_index = radix_tree_maxindex(node->height); 1282 if (cur_index > max_index) 1283 break; 1284 1285 cur_index = __locate(node, item, cur_index, &found_index); 1286 rcu_read_unlock(); 1287 cond_resched(); 1288 } while (cur_index != 0 && cur_index <= max_index); 1289 1290 return found_index; 1291 } 1292 #else 1293 unsigned long radix_tree_locate_item(struct radix_tree_root *root, void *item) 1294 { 1295 return -1; 1296 } 1297 #endif /* CONFIG_SHMEM && CONFIG_SWAP */ 1298 1299 /** 1300 * radix_tree_shrink - shrink height of a radix tree to minimal 1301 * @root radix tree root 1302 */ 1303 static inline void radix_tree_shrink(struct radix_tree_root *root) 1304 { 1305 /* try to shrink tree height */ 1306 while (root->height > 0) { 1307 struct radix_tree_node *to_free = root->rnode; 1308 void *newptr; 1309 1310 BUG_ON(!radix_tree_is_indirect_ptr(to_free)); 1311 to_free = indirect_to_ptr(to_free); 1312 1313 /* 1314 * The candidate node has more than one child, or its child 1315 * is not at the leftmost slot, we cannot shrink. 1316 */ 1317 if (to_free->count != 1) 1318 break; 1319 if (!to_free->slots[0]) 1320 break; 1321 1322 /* 1323 * We don't need rcu_assign_pointer(), since we are simply 1324 * moving the node from one part of the tree to another: if it 1325 * was safe to dereference the old pointer to it 1326 * (to_free->slots[0]), it will be safe to dereference the new 1327 * one (root->rnode) as far as dependent read barriers go. 1328 */ 1329 newptr = to_free->slots[0]; 1330 if (root->height > 1) 1331 newptr = ptr_to_indirect(newptr); 1332 root->rnode = newptr; 1333 root->height--; 1334 1335 /* 1336 * We have a dilemma here. The node's slot[0] must not be 1337 * NULLed in case there are concurrent lookups expecting to 1338 * find the item. However if this was a bottom-level node, 1339 * then it may be subject to the slot pointer being visible 1340 * to callers dereferencing it. If item corresponding to 1341 * slot[0] is subsequently deleted, these callers would expect 1342 * their slot to become empty sooner or later. 1343 * 1344 * For example, lockless pagecache will look up a slot, deref 1345 * the page pointer, and if the page is 0 refcount it means it 1346 * was concurrently deleted from pagecache so try the deref 1347 * again. Fortunately there is already a requirement for logic 1348 * to retry the entire slot lookup -- the indirect pointer 1349 * problem (replacing direct root node with an indirect pointer 1350 * also results in a stale slot). So tag the slot as indirect 1351 * to force callers to retry. 1352 */ 1353 if (root->height == 0) 1354 *((unsigned long *)&to_free->slots[0]) |= 1355 RADIX_TREE_INDIRECT_PTR; 1356 1357 radix_tree_node_free(to_free); 1358 } 1359 } 1360 1361 /** 1362 * radix_tree_delete - delete an item from a radix tree 1363 * @root: radix tree root 1364 * @index: index key 1365 * 1366 * Remove the item at @index from the radix tree rooted at @root. 1367 * 1368 * Returns the address of the deleted item, or NULL if it was not present. 1369 */ 1370 void *radix_tree_delete(struct radix_tree_root *root, unsigned long index) 1371 { 1372 /* 1373 * The radix tree path needs to be one longer than the maximum path 1374 * since the "list" is null terminated. 1375 */ 1376 struct radix_tree_path path[RADIX_TREE_MAX_PATH + 1], *pathp = path; 1377 struct radix_tree_node *slot = NULL; 1378 struct radix_tree_node *to_free; 1379 unsigned int height, shift; 1380 int tag; 1381 int offset; 1382 1383 height = root->height; 1384 if (index > radix_tree_maxindex(height)) 1385 goto out; 1386 1387 slot = root->rnode; 1388 if (height == 0) { 1389 root_tag_clear_all(root); 1390 root->rnode = NULL; 1391 goto out; 1392 } 1393 slot = indirect_to_ptr(slot); 1394 1395 shift = (height - 1) * RADIX_TREE_MAP_SHIFT; 1396 pathp->node = NULL; 1397 1398 do { 1399 if (slot == NULL) 1400 goto out; 1401 1402 pathp++; 1403 offset = (index >> shift) & RADIX_TREE_MAP_MASK; 1404 pathp->offset = offset; 1405 pathp->node = slot; 1406 slot = slot->slots[offset]; 1407 shift -= RADIX_TREE_MAP_SHIFT; 1408 height--; 1409 } while (height > 0); 1410 1411 if (slot == NULL) 1412 goto out; 1413 1414 /* 1415 * Clear all tags associated with the just-deleted item 1416 */ 1417 for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) { 1418 if (tag_get(pathp->node, tag, pathp->offset)) 1419 radix_tree_tag_clear(root, index, tag); 1420 } 1421 1422 to_free = NULL; 1423 /* Now free the nodes we do not need anymore */ 1424 while (pathp->node) { 1425 pathp->node->slots[pathp->offset] = NULL; 1426 pathp->node->count--; 1427 /* 1428 * Queue the node for deferred freeing after the 1429 * last reference to it disappears (set NULL, above). 1430 */ 1431 if (to_free) 1432 radix_tree_node_free(to_free); 1433 1434 if (pathp->node->count) { 1435 if (pathp->node == indirect_to_ptr(root->rnode)) 1436 radix_tree_shrink(root); 1437 goto out; 1438 } 1439 1440 /* Node with zero slots in use so free it */ 1441 to_free = pathp->node; 1442 pathp--; 1443 1444 } 1445 root_tag_clear_all(root); 1446 root->height = 0; 1447 root->rnode = NULL; 1448 if (to_free) 1449 radix_tree_node_free(to_free); 1450 1451 out: 1452 return slot; 1453 } 1454 EXPORT_SYMBOL(radix_tree_delete); 1455 1456 /** 1457 * radix_tree_tagged - test whether any items in the tree are tagged 1458 * @root: radix tree root 1459 * @tag: tag to test 1460 */ 1461 int radix_tree_tagged(struct radix_tree_root *root, unsigned int tag) 1462 { 1463 return root_tag_get(root, tag); 1464 } 1465 EXPORT_SYMBOL(radix_tree_tagged); 1466 1467 static void 1468 radix_tree_node_ctor(void *node) 1469 { 1470 memset(node, 0, sizeof(struct radix_tree_node)); 1471 } 1472 1473 static __init unsigned long __maxindex(unsigned int height) 1474 { 1475 unsigned int width = height * RADIX_TREE_MAP_SHIFT; 1476 int shift = RADIX_TREE_INDEX_BITS - width; 1477 1478 if (shift < 0) 1479 return ~0UL; 1480 if (shift >= BITS_PER_LONG) 1481 return 0UL; 1482 return ~0UL >> shift; 1483 } 1484 1485 static __init void radix_tree_init_maxindex(void) 1486 { 1487 unsigned int i; 1488 1489 for (i = 0; i < ARRAY_SIZE(height_to_maxindex); i++) 1490 height_to_maxindex[i] = __maxindex(i); 1491 } 1492 1493 static int radix_tree_callback(struct notifier_block *nfb, 1494 unsigned long action, 1495 void *hcpu) 1496 { 1497 int cpu = (long)hcpu; 1498 struct radix_tree_preload *rtp; 1499 1500 /* Free per-cpu pool of perloaded nodes */ 1501 if (action == CPU_DEAD || action == CPU_DEAD_FROZEN) { 1502 rtp = &per_cpu(radix_tree_preloads, cpu); 1503 while (rtp->nr) { 1504 kmem_cache_free(radix_tree_node_cachep, 1505 rtp->nodes[rtp->nr-1]); 1506 rtp->nodes[rtp->nr-1] = NULL; 1507 rtp->nr--; 1508 } 1509 } 1510 return NOTIFY_OK; 1511 } 1512 1513 void __init radix_tree_init(void) 1514 { 1515 radix_tree_node_cachep = kmem_cache_create("radix_tree_node", 1516 sizeof(struct radix_tree_node), 0, 1517 SLAB_PANIC | SLAB_RECLAIM_ACCOUNT, 1518 radix_tree_node_ctor); 1519 radix_tree_init_maxindex(); 1520 hotcpu_notifier(radix_tree_callback, 0); 1521 } 1522